Алгоритм поиска ассоциативных правил fp-growth пальмов С. В. кандидат технических наук доцент кафедры «Информационные системы и технологии»

Исходный набор данных 
N 
Предметный набор 
1 
a b c d e 
2 
a b c 
3 
a c d e 
4 
b c d e 
5 
b c
6 
b d e 
7 
c d e 

---

28 
Национальная ассоциация ученых (НАУ) # 10 (26), 2016 
Процесс работы алгоритм FPG 
1. На первом этапе строится FP-дерево пред-
ставляющее информация о часто встречающихся 
предметных наборах. 
1.1. Производится сканирование исходного 
набора данных и выделяется множество часто 
встречающихся наборов элементов, то есть набо-
ров, у которых поддержка больше или равна ми-
нимальной.
1.2. Строится FP-дерево, в котором наборы 
элементов будут упорядочиваться по убыванию 
значений их поддержки. [2] 
Правило построения 
Правило построения можно сформулировать 
следующим образом: если в дереве встречается 
одноименный с элементом узел, то новый узел не 
создаётся, а индекс соответствующего узла увели-
чивается на единицу; иначе - создаётся новый узел 
с индексом 1. 
Таким образом, после первого сканирования 
исходного набора, алгоритм построит компактное 
FP-дерево, которое представляет информацию о 
часто встречающиеся наборах элементов. Оно поз-
воляет эффективно извлекать данные при втором 
проходе исходного набора данных. 
2. Второй этап заключается в извлечении из 
FP-дерева часто встречающихся наборов элемен-
тов.
2.1. Выбирается какой-либо элемент из ис-
ходного набора, и находятся все возможные пути, 
которые ведут к узлам этого элемента. Далее про-
изводим подсчёт для каждого пути, сколько раз 
этот элемент встречается в нём. Например, для 
элемента a эта запись будет выглядеть так (cbdea, 
1), (cba, 1) и (cdea, 1). 
2.2. Удаляется сам элемент (суффикс набора) 
из ведущих к нему путей, т.е. (cbdea, cba, cdea) и 
остаются только (cbde, cb, cde). Проводим подсчет 
совпадений элементов в префиксах путей и распо-
лагаем их в порядке убывания, благодаря чему об-
разуется новая совокупность наборов.
2.3. На его основе строится новое FP-дерево - 
условное FP-дерево (conditional FP-tree); оно свя-
зано с одним объектом (в нашем случае, a). 
2.4. В этом FP-дереве присутствуют все узлы, 
поддержка которых больше или равна заданного 
минимального значения. Индексы узла суммиру-
ются, если элемент встречается с частотой, боль-
шей 2. 
2.5. Начиная с вершины, фиксируются пути 
до узлов, поддержка которых больше или равна 
заданной. Элемент, удалённый на втором шаге, 
возвращается назад, и рассчитывается результи-
рующее значение поддержки. 
Сравнение алгоритмов 
FPG обладает большей эффективностью, чем 
Apriori. Удобен он тем, что можно представить ис-
ходный набор данных в виде FP-дерева. Если в 
нём каждый элемент встречается многократно, то 
FP-дереве каждый элемент изображается в виде 
узла, индекс которого говорит о частоте встречае-
мости элемента. Т.е., другими словами, если эле-
мент встречается 200 раз, то можно создать узел в 
FP-дереве с индексом 200, тем самым упростив за-
дачу.
Сравнительные исследования классического 
алгоритма Аpriori и FPG показали, что с увеличе-
нием размеров исходного набора данных, времен-
ные затраты на поиск часто встречающихся набо-
ров элементов растут для FPG намного медленнее, 
чем для Аpriori (рис. 1) [3] 
 
Рисунок 1. Результаты сравнения