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

---

Национальная ассоциация ученых (НАУ) # 10 (26), 2016 
27 
АЛГОРИТМ ПОИСКА АССОЦИАТИВНЫХ ПРАВИЛ FP-GROWTH 
Пальмов С.В. 
кандидат технических наук 
доцент кафедры «Информационные системы и технологии» 
Поволжский государственный университет телекоммуникаций и 
информатики 
Россия, г. Самара 
Французова Е.Н. 
студент 
4 курс, факультет «Информационные системы и технологии» 
Россия, г. Самара
 
ASSOCIATION RULES MINING ALGORITHM FP-GROWTH 
Palmov S.V. 
Candidate of Science, assistant professor 
of Povolzhskiy State University of Telecommunication & Informatics
Russia, Samara 
Frantsuzova E.N. 
 student 
4
th
 year, faculty «Information Systems and Technology» 
Russia, Samara 
 
АННОТАЦИЯ 
В данной статье будет описан один из основных алгоритмов поиска ассоциативных правил. Дана 
краткая характеристика алгоритма FP-Growth и его работа. Так же будет проводиться сравнение алго-
ритм FP-Growth с Apriori. 
 
ABSTRACT 
This article will describe one of the basic algorithms for finding Association rules. A brief description of the 
algorithm FP-Growth and its work. Also will compare the algorithm of FP-Growth with Apriori. 
 
Ключевые слова :FP-Growth, Apriori, FP-дерево, Frequent-Pattern Tree.
 Keywords : FP-Growth, Apriori, FP-tree, Frequent-Pattern Tree. 
В предыдущей статье были описаны основные 
алгоритмы поиска ассоциативных правил [1]. В 
данной статье будет рассмотрен алгоритм FP-
Growth (FPG).  
FPG работает, в целом, более эффективно, 
чем Apriori. Главное отличие первого от последне-
го - предварительная обработка исходного набора 
данных, результатом которой является достаточно 
компактная древовидная структура - Frequent-
Pattern Tree (дерево популярных предметных 
наборов, FP-дерево). 
Основными достоинствами FPG являются: 
1. Сжатие исходного набора данных в ком-
пактную структуру, что обеспечивает эффектив-
ное и полное извлечение часто встречающихся 
предметных наборов. 
2. В процессе построения FP-дерева приме-
няется технология разделения и захвата (divide and 
conquer). Она позволяет выполнить декомпозицию 
одной сложной задачи на множество более про-
стых. 
3. Процедура генерации наборов-кандидатов 
занимает меньше времени. 
Основная цель алгоритма - найти в наборе 
данных все имеющиеся часто встречающиеся 
наборы с поддержкой, которая превышает мини-
мально заданную.
Рассмотрим работу алгоритма FPG на кон-
кретном примере. Пусть имеется исходный набор 
(табл. 1) [3] 
Таблица 1