Алгоритм FP-Growth

Алгоритм FP-Growth (от англ. Frequent Pattern Growth — «рост частых паттернов») — это метод интеллектуального анализа данных (data mining), предназначенный для поиска часто встречающихся наборов элементов (frequent itemsets) в наборах транзакционных данных. Алгоритм был предложен Цзявэй Ханем (Jiawei Han), Цзянь Пэем (Jian Pei) и Ивэнем Инем (Yiwen Yin) в 2000 году как альтернатива классическому алгоритму Apriori, отличающаяся более высокой производительностью за счёт отсутствия этапа генерации и тестирования кандидатов.

История

Разработка алгоритма FP-Growth была обусловлена необходимостью преодоления ограничений алгоритма Apriori, который требовал многократного сканирования базы данных и генерации огромного количества кандидатов на каждом шаге. В 2000 году группа исследователей под руководством Цзявэй Ханя опубликовала статью «Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach», в которой представила новый подход, основанный на сжатом представлении данных в виде дерева частых паттернов (FP-tree). Алгоритм быстро завоевал популярность в академической среде и промышленности благодаря своей эффективности при работе с большими объёмами данных.

Принцип работы

Алгоритм FP-Growth состоит из двух основных этапов: построение FP-дерева и извлечение из него частых паттернов.

Построение FP-дерева

1. Первое сканирование базы данных: Алгоритм подсчитывает частоту (поддержку) каждого отдельного элемента (item) во всех транзакциях. Элементы, частота которых ниже заданного порога минимальной поддержки (min_sup), отбрасываются как нерелевантные.
2. Сортировка: Оставшиеся элементы сортируются по убыванию частоты. Эта сортировка критична для эффективности последующего сжатия данных.
3. Второе сканирование: Для каждой транзакции строится путь в FP-дереве. Корень дерева обозначается как «null». Элементы транзакции вставляются в дерево в порядке убывания их глобальной частоты. Если узел с таким элементом уже существует в дереве, его счётчик увеличивается на единицу. Если нет — создаётся новый узел. Параллельно строится таблица заголовков (header table), которая связывает каждый элемент со списком всех его вхождений в дерево (через связи между узлами).

Полученное FP-дерево является компактным представлением исходных данных, так как общие префиксы транзакций объединяются в общие ветви.

Извлечение частых паттернов

Этот этап выполняется рекурсивно, начиная с наименее частого элемента в таблице заголовков.

1. Формирование условного FP-дерева: Для каждого элемента (например, «e») извлекаются все пути в FP-дереве, которые заканчиваются этим элементом. Эти пути, с учётом счётчика узла «e», образуют «условную базу данных паттернов» (conditional pattern base) для элемента «e». Из этой базы строится новое, меньшее FP-дерево — «условное FP-дерево» (conditional FP-tree).
2. Рекурсия: Если условное FP-дерево не пусто, алгоритм рекурсивно применяет к нему процедуру извлечения паттернов, комбинируя текущий элемент с элементами, найденными в условном дереве. Например, если в условном дереве для «e» есть элемент «a», то частым паттерном будет {a, e}. Если в условном дереве для «a, e» есть элемент «b», то паттерном будет {a, b, e}.
3. Завершение: Рекурсия завершается, когда условное FP-дерево для данного элемента становится пустым или содержит только один путь. В последнем случае все комбинации элементов этого пути с текущим элементом являются частыми паттернами.

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

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

• Высокая производительность: FP-Growth обычно значительно быстрее алгоритма Apriori, особенно на плотных наборах данных с длинными транзакциями. Он не генерирует кандидатов, что сокращает количество операций и потребление памяти.
• Меньшее количество сканирований базы данных: Требуется всего два полных сканирования исходных данных, в отличие от Apriori, который может сканировать базу данных многократно.
• Компактное представление данных: FP-дерево сжимает исходные данные, часто занимая меньше памяти, чем сама база транзакций.
• Масштабируемость: Алгоритм хорошо работает с большими наборами данных.

Недостатки

• Зависимость от порядка элементов: Эффективность построения и размер FP-дерева зависят от выбранного порядка сортировки элементов. Хотя сортировка по убыванию частоты является стандартной и эффективной, в некоторых случаях могут потребоваться другие стратегии.
• Потребление памяти: Для очень больших или разрежённых наборов данных FP-дерево может быть всё ещё велико, а рекурсивные вызовы для построения условных деревьев могут потреблять значительный объём оперативной памяти.
• Сложность реализации: Реализация FP-Growth, особенно рекурсивной части, сложнее, чем реализация Apriori.
• Чувствительность к минимальной поддержке: При очень низком пороге минимальной поддержки количество частых паттернов и, соответственно, размер дерева могут резко возрасти, что приведёт к снижению производительности.

Применение

Алгоритм FP-Growth широко применяется в задачах, где требуется анализ ассоциативных правил и поиск закономерностей в транзакционных данных:

• Анализ рыночной корзины (Market Basket Analysis): Выявление товаров, которые часто покупаются вместе. Например, анализ покупок в супермаркетах или интернет-магазинах для оптимизации выкладки товаров и рекомендаций.
• Анализ веб-трафика: Поиск часто встречающихся последовательностей страниц, которые посещают пользователи, для улучшения навигации по сайту.
• Биоинформатика: Анализ последовательностей ДНК и белков для выявления часто встречающихся мотивов.
• Медицинская диагностика: Поиск сочетаний симптомов, часто встречающихся у пациентов с определёнными заболеваниями.
• Обнаружение вторжений (Intrusion Detection): Выявление аномальных паттернов в сетевом трафике, которые могут указывать на атаки.
• Рекомендательные системы: Формирование списков рекомендуемых товаров или контента на основе истории покупок или просмотров пользователя.

Сравнение с алгоритмом Apriori

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

• Название алгоритма «FP-Growth» отражает его ключевую идею: «рост» (growth) частых паттернов из компактного представления данных — FP-дерева.
• Существуют модификации алгоритма, такие как H-Mine и COFI (COFI-tree), которые пытаются улучшить его производительность для определённых типов данных.
• Алгоритм FP-Growth лёг в основу многих библиотек для анализа данных, например, в пакете mlxtend для языка Python.

Источники

• Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1-12.
• Han, J., & Kamber, M. (2006). Data Mining: Concepts and Techniques (2nd ed.). Morgan Kaufmann.
• Tan, P. N., Steinbach, M., & Kumar, V. (2005). Introduction to Data Mining. Addison-Wesley.