Дерево частых паттернов¶

Дерево частых паттернов (англ. Frequent Pattern Tree, FP-tree) — это структура данных в виде сжатого префиксного дерева, предназначенная для хранения множества транзакций (наборов элементов) в задачах анализа ассоциативных правил и поиска частых наборов (itemsets). FP-tree является ключевым компонентом алгоритма FP-Growth (Frequent Pattern Growth), который позволяет находить частые паттерны без явной генерации кандидатов, что существенно ускоряет обработку больших объёмов данных по сравнению с классическим алгоритмом Apriori.

¶История и предпосылки создания

Алгоритм Apriori, предложенный Рамешом Агравалом и Рамакришнаном Шрикантом в 1994 году, стал первым широко применяемым методом поиска частых наборов. Однако его главный недостаток — многократное сканирование базы данных и генерация огромного количества кандидатов (потенциально частых наборов), что приводило к экспоненциальному росту вычислительной сложности при увеличении числа элементов.

В 2000 году Цзянь Пэй (Jiawei Pei) и его коллеги из Университета Саймона Фрейзера (Канада) предложили альтернативный подход — алгоритм FP-Growth, основанный на структуре FP-tree. Вместо генерации кандидатов метод строит сжатое представление базы транзакций в виде дерева, а затем рекурсивно извлекает из него частые наборы. Это позволило сократить количество проходов по данным до двух и значительно уменьшить потребление памяти.

¶Устройство и принцип построения

¶Структура узла

Каждый узел FP-tree содержит:

• Имя элемента (item name) — идентификатор товара или атрибута.
• Счётчик (count) — количество транзакций, которые прошли через данный узел.
• Ссылки на дочерние узлы — обычно хранятся в виде списка или массива.
• Ссылка на следующий узел с тем же именем (node-link) — для организации связного списка всех узлов с одинаковым элементом.

Дополнительно ведётся таблица заголовков (header table), которая содержит для каждого элемента:

• Его имя.
• Общую частоту встречаемости (support count) во всей базе.
• Ссылку на первый узел в дереве с этим элементом (для обхода по node-link).

¶Алгоритм построения

1. Первое сканирование базы данных: подсчитывается частота каждого элемента. Элементы, частота которых ниже заданного порога минимальной поддержки (min_sup), отбрасываются. Оставшиеся элементы сортируются в порядке убывания частоты — это определяет порядок следования в дереве.
2. Второе сканирование: для каждой транзакции:

• Из неё удаляются нечастые элементы.
• Оставшиеся элементы упорядочиваются по убыванию частоты (согласно таблице заголовков).
• Начиная с корня дерева, для каждого элемента последовательно проверяется, существует ли дочерний узел с таким именем. Если существует — счётчик узла увеличивается на 1. Если нет — создаётся новый узел со счётчиком 1, и он связывается с родительским узлом, а также добавляется в связный список по node-link.

1. После обработки всех транзакций получается компактное дерево, в котором каждый путь соответствует одной или нескольким транзакциям, а узлы с одинаковыми именами объединены в цепочки.

¶Пример

Пусть база транзакций содержит:

• T1: {a, b, c}
• T2: {a, b, d}
• T3: {a, c, e}
• T4: {b, c, d}

При min_sup = 2 (элемент должен встречаться не менее чем в 2 транзакциях) частыми будут a (3), b (3), c (3), d (2). Элемент e (1) отбрасывается. Порядок по убыванию: a, b, c, d.

Построение:

• T1: a→b→c — все узлы новые, счётчики = 1.
• T2: a→b→d — a и b уже есть, их счётчики становятся 2; d — новый узел, счётчик = 1.
• T3: a→c — a уже есть (счётчик 3), c — новый узел (счётчик 1), но путь a→c не совпадает с a→b→c, поэтому c создаётся как отдельная ветвь.
• T4: b→c→d — b нет в корне, поэтому создаётся новая ветвь от корня: b (счётчик 1), c (счётчик 1), d (счётчик 1).

Итоговое дерево: корень, от него два дочерних узла: a (счётчик 3) и b (счётчик 1). От a: b (счётчик 2) и c (счётчик 1). От b (от корня): c (счётчик 1). От b (от a): d (счётчик 1). От c (от a): нет дочерних. От c (от b): d (счётчик 1). Таблица заголовков: a(3)→узел a, b(3)→узел b (от корня) и далее по node-link к узлу b (от a), c(3)→узел c (от a) и далее к узлу c (от b), d(2)→узел d (от a) и далее к узлу d (от b).

¶Алгоритм FP-Growth

После построения FP-tree выполняется рекурсивное извлечение частых наборов:

1. Для каждого элемента из таблицы заголовков (начиная с наименее частого) строится его условная база паттернов (conditional pattern base) — набор всех префиксных путей, ведущих к данному элементу. Префиксный путь — это путь от корня до родительского узла данного элемента, причём каждый узел в пути учитывается со счётчиком, равным счётчику узла элемента.
2. На основе условной базы строится условное FP-tree (conditional FP-tree) — то же самое дерево, но только для тех элементов, которые входят в условную базу и удовлетворяют порогу min_sup.
3. Рекурсивно повторяется шаг 1 для каждого элемента условного дерева, пока не останется элементов.
4. В результате получаются все частые наборы, содержащие данный элемент, которые объединяются с ним.

Например, для элемента d из предыдущего примера условная база: {a:1, b:1} (путь a→b→d) и {b:1, c:1} (путь b→c→d). После фильтрации по min_sup=2 ни один элемент не проходит, поэтому частые наборы с d — только {d} (поддержка 2). Для элемента c: условная база {a:2} (путь a→b→c) и {b:1} (путь b→c). После фильтрации a проходит (2 ≥ 2), b — нет. Строится условное дерево с a, из которого получается набор {a, c} (поддержка 2). Итоговые частые наборы: {a} (3), {b} (3), {c} (3), {d} (2), {a, b} (2), {a, c} (2), {b, c} (2).

¶Преимущества и недостатки

¶Преимущества

• Скорость: FP-Growth обычно работает в 10–100 раз быстрее Apriori на больших наборах данных, особенно при низких порогах поддержки.
• Экономия памяти: FP-tree сжимает данные, так как общие префиксы транзакций хранятся один раз. В реальных базах данных (например, супермаркетов) дерево часто оказывается значительно меньше исходного набора транзакций.
• Отсутствие генерации кандидатов: не требуется создавать и проверять огромные множества потенциальных частых наборов.
• Масштабируемость: алгоритм хорошо работает с тысячами и миллионами транзакций.

¶Недостатки

• Чувствительность к порядку элементов: производительность зависит от выбранного порядка сортировки (обычно по убыванию частоты, но возможны вариации).
• Память при высокой размерности: если каждый элемент встречается редко, дерево может стать разреженным и неэффективным.
• Сложность реализации: рекурсивное построение условных деревьев требует аккуратного управления памятью, особенно при больших глубинах.
• Не подходит для потоковой обработки: FP-tree строится за два прохода по статическому набору данных; для динамически меняющихся данных требуются модификации.

¶Применение

Деревья частых паттернов и алгоритм FP-Growth широко используются в:

• Анализе рыночной корзины (market basket analysis) — выявление товаров, которые часто покупаются вместе (например, «пиво и подгузники»). Это позволяет оптимизировать расположение товаров в магазинах, формировать рекомендации и планировать акции.
• Веб-аналитике — поиск часто встречающихся последовательностей посещения страниц, что помогает улучшить навигацию сайта.
• Биоинформатике — анализ экспрессии генов, поиск часто встречающихся комбинаций генетических маркеров.
• Системах рекомендаций — на основе частых наборов формируются рекомендации пользователям (например, «люди, купившие X, также купили Y»).
• Обнаружении мошенничества — выявление нетипичных комбинаций транзакций, которые могут указывать на мошеннические действия.
• Обработке текстов — поиск часто встречающихся словосочетаний (n-грамм) для анализа тональности или тематического моделирования.

¶Модификации и расширения

• **FP-Growth* (FP-Growth-star)** — оптимизация, при которой условные деревья строятся не рекурсивно, а с помощью итеративного подхода, что снижает накладные расходы.
• COFI-tree (Co-Occurrence Frequent Itemset tree) — альтернативная структура, которая строит отдельные деревья для каждого элемента, что может ускорить извлечение частых наборов.
• Parallel FP-Growth — распределённая версия алгоритма, реализованная в Apache Mahout и Spark MLlib, позволяющая обрабатывать терабайтные наборы данных на кластерах.
• Incremental FP-Growth — модификация для добавления новых транзакций в уже построенное дерево без полного перестроения.
• FP-Stream — адаптация для потоковых данных, где дерево обновляется с течением времени с учётом старения старых транзакций.

¶Сравнение с другими методами

FP-Growth считается одним из самых эффективных алгоритмов для поиска частых наборов в статических базах данных, особенно при низких порогах поддержки, когда Apriori становится непрактичным.

¶Интересные факты

• Название «FP-Growth» происходит от «Frequent Pattern Growth», что отражает идею «выращивания» частых паттернов из меньших наборов.
• Алгоритм был запатентован в 2001 году (патент US 20030065650 A1), но патент истёк, и сейчас метод свободно используется в академических и коммерческих проектах.
• В библиотеке scikit-learn (Python) нет встроенной реализации FP-Growth, но её можно найти в сторонних пакетах, таких как mlxtend и pyfpgrowth.
• В Apache Spark реализован параллельный FP-Growth, который может обрабатывать до 100 миллионов транзакций на стандартном кластере.

¶Источники

• Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.
• Han, J., Kamber, M., & Pei, J. (2011). Data Mining: Concepts and Techniques (3rd ed.). Morgan Kaufmann.
• Tan, P. N., Steinbach, M., & Kumar, V. (2005). Introduction to Data Mining. Addison-Wesley.
• Borgelt, C. (2005). An implementation of the FP-growth algorithm. Proceedings of the 1st International Workshop on Open Source Data Mining, 1–5.
• Apache Spark MLlib documentation: Frequent Pattern Mining — FP-Growth.