Ассоциативный и причинный анализ и ассоциативные байесовские сети
Ключевые слова:
ассоциативные правила, негативные правила, недоопределенное вероятностное пространство, ассоциативные байесовские сетиАннотация
Поиск ассоциаций является одним из быстроразвивающихся разделов интеллектуальной обработки данных. К сожалению, традиционные подходы, развиваемые в этой области, например, при обнаружении часто встречающихся паттернов и ассоциативных правил, зачастую оказываются не в состоянии справиться с новыми приложениями, которые требуют несколько иного взгляда на методологию и технологию ассоциативного анализа. В данной работе для решения задач анализа ассоциаций привлекается неклассическая модель вероятностного пространства, которое задает класс распределений, удовлетворяющих тем ограничениям, которые накладываются доступной информацией о вероятностях некоторых, возможно, зависимых событий. В рамках этой модели, формализуемой в терминах нормированных булевых алгебр, нормированных решеток и их фрагментов, оказывается удобно решать ряд новых задач анализа ассоциаций, которые до сих пор принято относить к классу проблемных, хотя и актуальных. К их числу относятся задачи поиска редких, но сильных ассоциаций, негативных правил, а также задачи причинного анализа для принятия решений в задачах классификации. В работе предлагается единый алгоритм решения перечисленных задач, основанный на использовании структуры ассоциативной (алгебраической) сети. Этот алгоритм демонстрируется на примере.Литература
Биркгоф Г., Барти Т. Современная прикладная алгебра., М.: Мир, 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/
Association and Casual Rule Mining Using Associative Bayesian Networks
Abstract
Association rule search is one of the ever increasing areas of the intelligent data analysis and data mining. Unfortunately, traditional approaches of this area often are not capable to cope with new challenging problems emerging while dealing with new classes of modern applications. The latter require new viewpoint on methodology and technology of association analysis where "classical" ones fail. For efficient solution of emerging tasks of the association analysis, the paper proposes "non–classical" model of probabilistic space and its fragment called "sub–defined probabilistic space". While using algebraic view, the probabilistic models used are defined in terms of normalized Boolean algebra and lattices. Such a probabilistic model made it possible to cope with several challenging association analysis tasks. Between them, the proposed algorithm is capable of search for rare but "strong" association rules, mining negative rules of any forms and mining cause consequence rules. All these tasks are solved within the same framework called associative (algebraic) Bayesian network. The basic algorithm is demonstrated by simple case study, although the algorithm and corresponding software developed for this purpose were validated on an application of real life scale.Опубликован
2009-06-01
Как цитировать
Городецкий, В. И., & Самойлов, В. В. (2009). Ассоциативный и причинный анализ и ассоциативные байесовские сети. Труды СПИИРАН, (9), 13-65. https://doi.org/10.15622/sp.9.1
Выпуск
Раздел
Статьи
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
