Ассоциативный и причинный анализ и ассоциативные байесовские сети
Ключевые слова:
ассоциативные правила, негативные правила, недоопределенное вероятностное пространство, ассоциативные байесовские сетиАннотация
Поиск ассоциаций является одним из быстроразвивающихся разделов интеллектуальной обработки данных. К сожалению, традиционные подходы, развиваемые в этой области, например, при обнаружении часто встречающихся паттернов и ассоциативных правил, зачастую оказываются не в состоянии справиться с новыми приложениями, которые требуют несколько иного взгляда на методологию и технологию ассоциативного анализа. В данной работе для решения задач анализа ассоциаций привлекается неклассическая модель вероятностного пространства, которое задает класс распределений, удовлетворяющих тем ограничениям, которые накладываются доступной информацией о вероятностях некоторых, возможно, зависимых событий. В рамках этой модели, формализуемой в терминах нормированных булевых алгебр, нормированных решеток и их фрагментов, оказывается удобно решать ряд новых задач анализа ассоциаций, которые до сих пор принято относить к классу проблемных, хотя и актуальных. К их числу относятся задачи поиска редких, но сильных ассоциаций, негативных правил, а также задачи причинного анализа для принятия решений в задачах классификации. В работе предлагается единый алгоритм решения перечисленных задач, основанный на использовании структуры ассоциативной (алгебраической) сети. Этот алгоритм демонстрируется на примере.Литература
Биркгоф Г., Барти Т. Современная прикладная алгебра., М.: Мир, 1976. 370 с.
Городецкий В. И. Адаптация в экспертных системах// Изв. РАН Техническая кибернетика, 1993. № 5. C. 101-110.
Городецкий В. И. Алгебраические байесовские сети – новая парадигма экспертных систем// Юбилейный сб. тр. институтов Отделения информатики, вычислительной техники и автоматизации РАН. т.2. 1993.С. 120-141.
Городецкий В. И. Тулупьев А.Л. Формирование непротиворечивых баз знаний с неопределенностью//Изв. РАН, Теория и системы управления. 1997. № 5.
Городецкий В. И. Интервальные вероятностные меры неопределенности в инженерии знаний// Юбилейный сб. тр. СПИИРАН. СПб 1998.
Городецкий В. И. Моделирование недоопределенных знаний// Сб. докл. Междунар. конф. по мягким вычислениям (SCM’98). т.1. СПб. 1998. C. 98 – 102.
Городецкий В. И., Серебряков С.В. Методы и алгоритмы коллективного распознавания //Автоматика и Телемеханика. 2008. № 11. C. 3–40.
Яглом И.М. Булева структура и ее модели. М.: СовРадио. 1980. 192 C.
Adamo J.-M. Data Mining for Association Rules and Sequential Patterns. Springer, 2000.
Agrawal R., Sricant R. Fast Algorithm for Mining Association rules// Proc. of the 20th Intern. Conference on Very Large Databases. Santiago, Chile, 1994.
Agrawal R, Imielinski T., Swami A. Mining association rules between sets of items in large databases// Proc. of the ACM SIGMOD Conf. on Management of Data. Washington, D.C. 1993.
Brin S., Motwani R., Silverstein C. Beyond market baskets: generalizing association rules to correlations// Proc. of the ACM SIGMOD Intern. Conf. on Management of Data. 1997. P. 255–264.
Dzeroski S. Multi-relational data mining: An introduction// ACM SIGKDD Explorations Newsletter. Vol. 5, Issue 1. 2003. P. 1–16.
S.Dzeroski , N.Lavrac . Relational Data Mining. Springer, 2001.
Fagin R., Halpern J. Y., Megiddo N. A. Logic for Reasoning about Probabilities// Proc. of 3th IEEE Symposium on Logic and Computer Science. 1988.
Fagin R., Halpern J. Y. Uncertainty, Belief, and Probability// Proc. of 11th Intern. Joint Conf. on Artificial Intelligence. Detroit, Michigan, USA, 1989. P. 1161–1167.
Gorodetski V. I. Adaptation Problems in Expert Systems// Intern. J. of Adaptive Control and Signal Processing. 1992. Vol.6. P. 201-209.
Halpern J. Y. Reasoning about uncertainty. MIT Press: Cambridge. 2003.
Han J., Fu Y., Wang W., Koperski K., Zaiane O. DMQL: A Data Mining Query Language for Relational Databases// SIGMOD DMKD Workshop, 1996.
Han J., Kamber M. Data Mining: Concept and Techniques. Morgan Kaufman, 2000.
Han J., Pei J., Yin Y. Mining frequent patterns without candidate generation// Proc. of the ACM SIGMOD Intern. Conf. on Management of Data. 2000. P. 1–12.
Liu H., Lu H, Feng L., Hussain F. Efficient search of reliable exceptions// Proc. of the 3d Pacific Asia Conference on Knowledge Discovery and Data Mining, 1999. P. 194–204.
Morzy M. Efficient Mining of Dissociation Rules// Lecture Notes in Computer Sci 2006. Vol. 4081, 2006, Springer, P. 228–237.
Quinlan J. C4.5: Programs for Machine Learning// Elsevier Science & Technology Books, 1992. 316 P.
Piatetsky–Shapiro G. Discovery, analysis and presentation of strong rules// Knowledge Discovery in Databases. AAAI Press/MIT Press. 1991. P. 229–248. # Movylence. http://www.grouplens.org/node/73.
Movylence.http://www.grouplens.org/node/73.
Szathmary L., Napoli A., Valtchev P. Towards Rare Itemset Mining// Proc. of the 19th IEEE Intern. Conf. on Tools with Artificial Intelligence (ICTAI '07). Patras, Greece, Oct 2007. P. 305-312.
Shortliffe E. Computer–based medical consultations: MYSYN. N. Y.: Elsevier. 1976.
Tze A., Sim H., Zutshi S., Indrawan M., et al. The Discovery of Coherent Rules. IAENG Intern. J. of Computer Sci. 2008. Vol. 35, № 3.
Wu X., Zhang C., Zhang S. Efficient Mining of Both Positive and Negative Association Rules// ACM Trans. on Information Systems. 2004. Vol. 22, № 3.P. 381–405.
Zhang C., Zhang S. Association rule mining. Springer, 2002. 240 P.
Web site of LIS. http://spaec.iias.spb.su/ai/abn/
Городецкий В. И. Адаптация в экспертных системах// Изв. РАН Техническая кибернетика, 1993. № 5. C. 101-110.
Городецкий В. И. Алгебраические байесовские сети – новая парадигма экспертных систем// Юбилейный сб. тр. институтов Отделения информатики, вычислительной техники и автоматизации РАН. т.2. 1993.С. 120-141.
Городецкий В. И. Тулупьев А.Л. Формирование непротиворечивых баз знаний с неопределенностью//Изв. РАН, Теория и системы управления. 1997. № 5.
Городецкий В. И. Интервальные вероятностные меры неопределенности в инженерии знаний// Юбилейный сб. тр. СПИИРАН. СПб 1998.
Городецкий В. И. Моделирование недоопределенных знаний// Сб. докл. Междунар. конф. по мягким вычислениям (SCM’98). т.1. СПб. 1998. C. 98 – 102.
Городецкий В. И., Серебряков С.В. Методы и алгоритмы коллективного распознавания //Автоматика и Телемеханика. 2008. № 11. C. 3–40.
Яглом И.М. Булева структура и ее модели. М.: СовРадио. 1980. 192 C.
Adamo J.-M. Data Mining for Association Rules and Sequential Patterns. Springer, 2000.
Agrawal R., Sricant R. Fast Algorithm for Mining Association rules// Proc. of the 20th Intern. Conference on Very Large Databases. Santiago, Chile, 1994.
Agrawal R, Imielinski T., Swami A. Mining association rules between sets of items in large databases// Proc. of the ACM SIGMOD Conf. on Management of Data. Washington, D.C. 1993.
Brin S., Motwani R., Silverstein C. Beyond market baskets: generalizing association rules to correlations// Proc. of the ACM SIGMOD Intern. Conf. on Management of Data. 1997. P. 255–264.
Dzeroski S. Multi-relational data mining: An introduction// ACM SIGKDD Explorations Newsletter. Vol. 5, Issue 1. 2003. P. 1–16.
S.Dzeroski , N.Lavrac . Relational Data Mining. Springer, 2001.
Fagin R., Halpern J. Y., Megiddo N. A. Logic for Reasoning about Probabilities// Proc. of 3th IEEE Symposium on Logic and Computer Science. 1988.
Fagin R., Halpern J. Y. Uncertainty, Belief, and Probability// Proc. of 11th Intern. Joint Conf. on Artificial Intelligence. Detroit, Michigan, USA, 1989. P. 1161–1167.
Gorodetski V. I. Adaptation Problems in Expert Systems// Intern. J. of Adaptive Control and Signal Processing. 1992. Vol.6. P. 201-209.
Halpern J. Y. Reasoning about uncertainty. MIT Press: Cambridge. 2003.
Han J., Fu Y., Wang W., Koperski K., Zaiane O. DMQL: A Data Mining Query Language for Relational Databases// SIGMOD DMKD Workshop, 1996.
Han J., Kamber M. Data Mining: Concept and Techniques. Morgan Kaufman, 2000.
Han J., Pei J., Yin Y. Mining frequent patterns without candidate generation// Proc. of the ACM SIGMOD Intern. Conf. on Management of Data. 2000. P. 1–12.
Liu H., Lu H, Feng L., Hussain F. Efficient search of reliable exceptions// Proc. of the 3d Pacific Asia Conference on Knowledge Discovery and Data Mining, 1999. P. 194–204.
Morzy M. Efficient Mining of Dissociation Rules// Lecture Notes in Computer Sci 2006. Vol. 4081, 2006, Springer, P. 228–237.
Quinlan J. C4.5: Programs for Machine Learning// Elsevier Science & Technology Books, 1992. 316 P.
Piatetsky–Shapiro G. Discovery, analysis and presentation of strong rules// Knowledge Discovery in Databases. AAAI Press/MIT Press. 1991. P. 229–248. # Movylence. http://www.grouplens.org/node/73.
Movylence.http://www.grouplens.org/node/73.
Szathmary L., Napoli A., Valtchev P. Towards Rare Itemset Mining// Proc. of the 19th IEEE Intern. Conf. on Tools with Artificial Intelligence (ICTAI '07). Patras, Greece, Oct 2007. P. 305-312.
Shortliffe E. Computer–based medical consultations: MYSYN. N. Y.: Elsevier. 1976.
Tze A., Sim H., Zutshi S., Indrawan M., et al. The Discovery of Coherent Rules. IAENG Intern. J. of Computer Sci. 2008. Vol. 35, № 3.
Wu X., Zhang C., Zhang S. Efficient Mining of Both Positive and Negative Association Rules// ACM Trans. on Information Systems. 2004. Vol. 22, № 3.P. 381–405.
Zhang C., Zhang S. Association rule mining. Springer, 2002. 240 P.
Web site of LIS. http://spaec.iias.spb.su/ai/abn/
Опубликован
2009-06-01
Как цитировать
Городецкий, В. И., & Самойлов, В. В. (2009). Ассоциативный и причинный анализ и ассоциативные байесовские сети. Труды СПИИРАН, (9), 13-65. https://doi.org/10.15622/sp.9.1
Выпуск
Раздел
Статьи
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
