Ассоциативные правила - тип зависимостей между данными, которые отражают, какие признаки или события встречаются совместно и насколько часто это происходит. Строгие ассоциативные правила представляют интерес для тех приложений, где требуется высокая степень уверенности в установленных зависимостях между данными, например, в информационной безопасности, анализе компьютерных сетей и медицине. Чрезмерно большое число выявленных правил существенно усложняет их экспертизу и применение. Для решения этой проблемы предложен алгоритм MClose, расширяющий возможности известного алгоритма Close. Алгоритм Close формирует минимаксный базис, в котором каждое строгое ассоциативное правило имеет минимальную посылку и максимальное следствие. Однако в минимаксном базисе остаются избыточные строгие ассоциативные правила. Алгоритм MClose в процессе построения минимаксного базиса распознаёт избыточные строгие ассоциативные правила и устраняет их. Предложенный алгоритм основан на свойствах замкнутых множеств. Доказаны выводимости, аргументирующие корректность алгоритма MClose.
Скачать электронную версию публикации
Загружен, раз: 237
- Title О неизбыточном представлении минимаксного базиса строгих ассоциативных правил
- Headline О неизбыточном представлении минимаксного базиса строгих ассоциативных правил
- Publesher
Tomsk State University
- Issue Прикладная дискретная математика 36
- Date:
- DOI 10.17223/20710410/36/9
Ключевые слова
соответствия Галуа, замкнутые множества, строгие ассоциативные правила, неизбыточность, минимаксный базис, Galois connection, closed sets, strong association rules, non-redundant, minimax basisАвторы
Ссылки
Витяев Е. Е., Демин А. В., Пономарев Д. К. Вероятностное обобщение формальных понятий // Программирование. 2012. №5. С. 18-34.
Городецкий В. И., Самойлов В. В. Ассоциативный и причинный анализ и ассоциативные байесовские сети // Тр. СПИИРАН. 2009. Вып. 9. С. 13-65.
Кузнецов С. О. Автоматическое обучение на основе анализа формальных понятий // Автоматика и телемеханика. 2001. №10. С. 3-27.
Биркгоф Г., Барти Т. Современная прикладная алгебра. СПб.: Лань, 2005. 400 с.
Гуров С. И. Булевы алгебры, упорядоченные множества, решетки: определения, свойства, примеры. М.: Книжный дом «ЛИБРОКОМ», 2013. 352 с.
Ganter B. and Wille R. Formal Concept Analyses: Mathematical Foundations. Springer Science and Business Media, 2012. 314 p.
Pasquier N., Bastide Y., TaouiR., and Lakhal L. Generating a condensed representation for association rules // J. Intelligent Inform. Systems. 2005. V. 24. No. 1. P. 29-60.
Майер Д. Теория реляционных баз данных. М.: Мир, 1987. 608 с.
Батура Т. В. Модели и методы анализа компьютерных социальных сетей // Программные продукты и системы. 2013. №3. С. 130-137.
Платонов В. В., Семенов П. О. Методы сокращения размерности в системах обнаружения сетевых атак // Проблемы информационной безопасности. Компьютерные системы. 2012. №3. С. 40-45.
Ilayaraja M. and Meyyappan T. Mining medical data to identify frequent diseases using Apriori algorithm // Pattern Recognition, Informatics and Mobile Engineering (PRIME), IEEE, 2013. P. 194-199.
Duquenne V. and Obiedkov S. A. Attribute-incremental construction of the canonical implication basis // Ann. Math. Artif. Intelligence. 2007. V.49. No. 1. P. 77-99.
Rudolph S. Some notes on pseudo-closed sets // LNCS. 2007. V.4390. P. 151-165.
Zaki M. J. and Hsiao C.-J. Efficient algorithms for mining closed itemsets and their lattice structure // IEEE Trans. Knowledge Data Eng. 2005. V. 17. No. 4. P. 462-478.
Uno T., Asai T., Uchida Y., and Arimura H. An efficient algorithm for enumerating closed patterns in transaction databases // LNCS. 2004. V. 3245. P. 16-31.
Zhang C. and Zhang S. Association Rules Mining. Springer, 2002. 240 p.
Geng L. and Hamilton H. J. Interestingness measures for data mining: a survey // ACM Computing Surveys. 2006. V. 38. No. 3. Article 9.

О неизбыточном представлении минимаксного базиса строгих ассоциативных правил | Прикладная дискретная математика. 2017. № 36. DOI: 10.17223/20710410/36/9
Скачать полнотекстовую версию
Загружен, раз: 721