Труды КНЦ (Технические науки вып. 3/2024(15))

Аналогично предыдущему шагу удаляем лишние строки (помечены цветом в табл. 8 ). Полученный результат см. в табл. 9. Таблица 9 Вертикальное представление (TID) базы транзакций Труды Кольского научного центра РАН. Серия: Технические науки. 2024. Т. 15, № 3. С. 82-96. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2024. Vol. 15, No. 3. P. 82-96. Элемент № транзакции Поддержка a, b, с 8 , 9 2 a, b, e 1 , 8 2 На следующем шаге получаем единственный четырехэлементный паттерн (a, b, с, е) с поддержкой 1 , тогда как заданное значение минимальной поддержки равно 2 . Работа алгоритма закончена. Получаем набор частых элементов {{a}, {b}, {с}, {d}, {e}}, а также получаем двухэлементные частые наборы: {{ a , b }, { a , с }, { a , e }, { b , с }, { b , d }, { b , e }}, и два трехэлементных набора: {{ a , b , с }, { a , b , e }}. Таким образом, получаем ассоциативные правила, представленные в табл. 3. Полученные правила аналогичны тем, которые были получены при помощи алгоритмов Априори и FP-GROWTH. Достоинства алгоритма [3]: — простота; — поддержка для любого элемента рассчитывается без сканирования базового набора; — число сканирований базового набора сокращено до одного раза. Преимущества перед алгоритмом Априори: 1) требования к памяти: алгоритм ECLAT использует меньше памяти, чем алгоритм Априори; 2) скорость: алгоритм ECLAT обычно быстрее, чем алгоритм Априори; 3) количество вычислений: алгоритм ECLAT не предполагает многократного сканирования данных для расчета отдельных значений поддержки. Недостатки алгоритма: — TID-множества могут оказаться слишком большими, поэтому операции с ними могут занимать длительное время; — большое число сгенерированных кандидатов при малом уровне минимальной поддержки. Описание одной из оптимальных программных реализаций можно найти в работе [9]. Далее рассмотрим алгоритм, также позволяющий получать ассоциативные правила, но основанный на анализе формальных понятий. Алгоритм «замыкай по одному» (Close by One - CbO) Анализ формальных понятий (АФП, Formal Concept Analysis — FCA) — это прикладная ветвь теории решеток, математической дисциплины, которая возникла в начале 1980-х гг. За последние три десятилетия АФП стал популярным, ориентированным на человека инструментом для представления знаний и анализа данных с многочисленными приложениями, в областях поиска информации с акцентом на аспекты визуализации, машинного обучения, интеллектуального анализа данных и обнаружения знаний, интеллектуального анализа текста и др. Важным достоинством разбираемого в разделе алгоритма CbO является то, что он позволяет получать не просто частые паттерны, а частые замкнутые паттерны (для замкнутых паттернов не существует паттернов меньшей размерности с такой же поддержкой). Обычно среди замкнутых паттернов осуществляется поиск интересных зависимостей, поскольку они представляют сосбой своеобразный базис в пространстве паттернов. При использовании математического аппарата АФП [10, 11] для решения обозначенного класса задач интеллектуального анализа данных термину «замкнутый паттерн» соответствует термин «содержание формального понятия» (intent), а термину «окрытие замкнутого паттерна» — термин «объем формального понятия» (extent). Транзакционная база данных в АФП называется контекстом. Формальные понятия определяются с помощью соответствия Галуа и представляют собой пары © Зуенко А. А., Фридман О. В., 2024 90