Тип публикации: статья из журнала
Год издания: 2017
Идентификатор DOI: 10.17223/20710410/36/9
Ключевые слова: Galois connection, Closed sets, strong association rules, non-redundant, minimax basis, соответствия Галуа, замкнутые множества, строгие ассоциативные правила, неизбыточность, минимаксный базис
Аннотация: Ассоциативные правила - тип зависимостей между данными, которые отражают, какие признаки или события встречаются совместно и насколько часто это происходит. Строгие ассоциативные правила представляют интерес для тех приложений, где требуется высокая степень уверенности в установленных зависимостях между данными, например, в информаПоказать полностьюционной безопасности, анализе компьютерных сетей и медицине. Чрезмерно большое число выявленных правил существенно усложняет их экспертизу и применение. Для решения этой проблемы предложен алгоритм MClose, расширяющий возможности известного алгоритма Close. Алгоритм Close формирует минимаксный базис, в котором каждое строгое ассоциативное правило имеет минимальную посылку и максимальное следствие. Однако в минимаксном базисе остаются избыточные строгие ассоциативные правила. Алгоритм MClose в процессе построения минимаксного базиса распознаёт избыточные строгие ассоциативные правила и устраняет их. Предложенный алгоритм основан на свойствах замкнутых множеств. Доказаны выводимости, аргументирующие корректность алгоритма MClose. Associative rules are the type of dependencies between data that reflect which features or events occur together and how often this happens. Strong associative rules are of interest for those applications where a high degree of confidence of dependencies is required. For example, they are used in information security, computer network analysis and medicine. Excessively large number of identified rules significantly complicates their expert analysis and application. To reduce the severity of this problem, we propose the MClose algorithm, which extends the capabilities of the well-known algorithm Close. The Close algorithm forms a minimax basis in which each strong associative rule has a minimum premise and a maximal consequence. However, in the minimax basis, some redundant strong associative rules remain. The MClose algorithm recognizes and eliminates them in the process of constructing a minimax basis. The proposed algorithm is based on the properties of closed sets. Its correctness is proved by proving the reflexivity, additivity, projectivity, and transitivity properties of strong associative rules.
Журнал: Прикладная дискретная математика
Выпуск журнала: № 36
Номера страниц: 113-126
ISSN журнала: 20710410
Место издания: Томск
Издатель: Федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский Томский государственный университет"