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

Достоинства алгоритма [3]: — позволяет избежать затратной процедуры генерации кандидатов, характерной для алгоритма Априори; — сжатие базового набора в компактную структуру, обеспечивающее быстрое и полное извлечение предметных наборов; — число сканирования входного набора сокращено до двух; — размер дерева обычно меньше размера входного набора данных. Недостатки алгоритма: — построение дерева - затратная по времени операция; — в некоторых случаях, вследствие большого числа узлов и связей, размер FP-дерева может намного превышать размер входного набора данных. Существует множество модификаций алгоритма, направленных на улучшение тех или иных его свойств. Одна из наиболее быстрых реализаций алгоритма описана в работе [ 6 ], а вариант реализации, направленный на уменьшение объема занимаемой памяти, — в исследовании [7]. Далее рассмотрим еще один алгоритм, который также, как и предыдущий, является усовершенствованием алгоритма Априори. Алгоритм ECLAT Алгоритм ECLAT (Equivalence Class Clustering and bottom-up Lattice Traversal) является одним из популярных методов майнинга ассоциативных правил и представляет собой наиболее эффективную и масштабируемую версию алгоритма Априори. Рассматриваемые выше алгоритмы Априори и FP-growth используют так называемое горизонтальное представление множеств. Алгоритм ECLAT [ 8 ] на первом шаге своей работы преобразует горизонтальное представление в вертикальное (так называемое TID- представление) и в дальнейшем ведется именно его обработка. Шаги этого алгоритма аналогичны соответствующим шагам алгоритма Априори, кроме функции вычисления поддержки кандидата, которая теперь не требует сканирования базы. Основная идея состоит в том, чтобы использовать пересечения наборов идентификаторов транзакций (ТГО-множества) для вычисления значения поддержки кандидата и избежать создания подмножеств, которые не существуют в дереве префиксов. При первом вызове функции используются все отдельные элементы вместе с их наборами данных. Затем функция вызывается рекурсивно, и при каждом рекурсивном вызове каждая пара «элемент — TID-множество» проверяется и сопрягается с другими парами «элемент — TID-множество». Этот процесс продолжается до тех пор, пока удается получать новые пары «элемент — TID-множество». Рассмотрим задачу поиска частых паттернов при помощи алгоритма ECLAT на том же примере (исходные данные см. в табл. 1 , 2 ). В табл. 4 представлена база транзакций (табл. 1) с учетом введенных обозначений. Труды Кольского научного центра РАН. Серия: Технические науки. 2024. Т. 15, № 3. С. 82-96. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2024. Vol. 15, No. 3. P. 82-96. Таблица 4 Транзакции купленных товаров № транзакции Элемент 1 a, b, e 2 b, d 3 b, с 4 a, b, d 5 a, с 6 b, с 7 a, с 8 е с, b, a, 9 a, b, с © Зуенко А. А., Фридман О. В., 2024 88