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

Недостатки: — многократное сканирование базового набора; — большое число сгененированных кандидатов при слишком большом наборе данных или при слишком низкой поддержке. Алгоритм эффективен только для небольших наборов либо при высоком уровне минимальной поддержки. Для улучшения работы используются его модификации, направленные на уменьшение числа сканирований входного набора, числа сгенерированных кандидатов, распараллеливание [4, 5]. К сожалению, далеко не во всех случаях эти модифицированные алгоритмы позволяют исправить ситуацию. Далее рассмотрим еще два популярных алгоритма. Алгоритм FP-GROWTH Один из самых эффективных алгоритмов. Позволяет избежать не только затратной процедуры генерации кандидатов, но и многократного сканирования входного набора. Метод базируется на предварительной обработке входного набора и преобразование его в специальную компактную древовидную структуру FP-дерева (frequent pattern tree), и лишь затем происходит вычисление частых наборов [3]. В общем виде алгоритм можно представить следующей последовательностью шагов [4]: Шаг 1. Производится сканирование входного набора, и все элементы каждой транзакции сортируются в порядке убывания поддержки этих элементов во всем базовом наборе. Шаг 2. Фильтрация. Производится удаление тех элементов, для которых значение поддержки меньше заданного пользователем значения минимальной поддержки. Шаг 3. Построение префиксного FP-дерева из оставшихся элементов. Шаг 4. Извлечение частых паттернов. Узлом FP-дерева является структура, которая хранит значение узла, ссылки на все дочерние элементы и его значение поддержки для текущего узла. Построение префиксного дерева происходит в несколько этапов: Этап 1. Построение корневого узла. Этап 2. Для каждого элемента каждой отсортированной транзакции из входного набора строятся узлы по следующему правилу: если для очередного элемента в текущем узле есть потомок, содержащий этот элемент, то новый узел не создается, а поддержка этого потомка увеличивается на 1 , в противном случае создается новый узел-потомок с поддержкой 1. Текущим узлом при этом становится найденный или построенный узел. Для извлечения частых паттернов необходимо построить условные деревья для каждого элемента. Условное поддерево множества A — это FP-дерево, содержащее только транзакции, в которые входит множество A. Приведем описание алгоритма извлечения частых паттернов [3]. Для каждого элемента в дереве, начиная с элемента с наименьшей поддержкой, необходимо выполнить следущее. Шаг 1. Добавить этот элемент во множество A . Шаг 2. Построить условное дерево по этому элементу. В случае, если такое дерево оказывается пустым, то записать в результат элементы множества A (они и будут очередным популярным набором), иначе выполнить этот алгоритм для построенного условного дерева. Шаг 3. Исключить элемент из множества A . Шаг 4. Исключить элемент из дерева. Таким образом, дерево проходится рекурсивно снизу вверх полностью, и при этом генерируются все возможные популярные наборы. Рассмотрим работу этого алгоритма на простом примере, представленном выше. Выпишем элементы в порядке уменьшения поддержки (см. табл. 2): (b:7), (a: 6 ), (c: 6 ), (d:2), (e:2). Все элементы имеют поддержку большую или равную заданному значению минимальной поддержки. Анализируя транзакции (см. табл. 1), получаем начальные наборы: (b, a, e), (b, d), (b, c), (b, a, d), (a, c), (b, c), (a, c), (b, a, c, e), (b, a, c). Труды Кольского научного центра РАН. Серия: Технические науки. 2024. Т. 15, № 3. С. 82-96. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2024. Vol. 15, No. 3. P. 82-96. © Зуенко А. А., Фридман О. В., 2024 86