FP-Рост (Рост часто встречаемых паттернов)
- Автор метода
- Jiawei Han, Jian Pei & Yiwen Yin
- Год
- 2000
- Тип
- Frequent-itemset mining algorithm
- Семейство
- Pattern mining
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
FP-Growth, представленный Цзявэем Ханом, Цзянь Пэем и Ивэнь Инь в 2000 году, извлекает частые наборы элементов из транзакционных данных без генерации кандидатных наборов — дорогостоящего этапа, замедляющего классический алгоритм Apriori.
Он сжимает базу данных в дерево частых паттернов (FP-tree) за два прохода, а затем рекурсивно строит частые паттерны из этой структуры, что делает его значительно быстрее Apriori на больших, плотных наборах данных.
Интуиция метода
Apriori находит частые наборы элементов путем многократной генерации и тестирования кандидатных комбинаций — дорогостоящего, интенсивно сканирующего процесса, который взрывается на плотных данных. FP-Growth идет другим путем: он сжимает всю базу данных транзакций в компактное дерево, где общие префиксы хранятся один раз, так что общие паттерны перекрываются и сжимаются. Затем, вместо генерации кандидатов, он считывает частые паттерны непосредственно из дерева, следуя путям, ведущим к каждому элементу, и рекурсивно извлекая меньшие «условные» деревья. Два прохода по данным и хитрая структура данных заменяют многочисленные проходы Apriori и комбинаторный взрыв кандидатов.
История
Хан, Пэй и Инь представили FP-Growth на SIGMOD 2000 как альтернативу Apriori без генерации кандидатов, с расширенным описанием в их статье 2004 года в Data Mining and Knowledge Discovery. Идея дерева частых паттернов — сжатие транзакций в общую префиксную структуру и ее рекурсивное извлечение — стала фундаментальной техникой в извлечении паттернов, наряду с Apriori (на основе кандидатов) и ECLAT (вертикальный формат). Он остается стандартным, высокопроизводительным майнером наборов элементов в библиотеках интеллектуального анализа данных.
Когда применять
Используйте FP-Growth для извлечения частых наборов элементов (и, далее, ассоциативных правил) из транзакционных данных — анализа рыночной корзины, анализа веб-использования и кликстрима, рекомендаций и анализа совместной встречаемости в биоинформатике — особенно на больших или плотных наборах данных, где генерация кандидатов Apriori слишком медленна. Он требует всего два прохода по базе данных и обычно значительно превосходит Apriori. Его затраты: FP-tree должен помещаться в памяти (ограничение для очень больших или чрезвычайно разреженных данных, где дерево плохо сжимается), рекурсия может быть сложна в реализации, и, как и все извлечение на основе поддержки, он чувствителен к минимальному порогу поддержки (слишком низкий порог вызывает взрыв выходных данных, слишком высокий порог пропускает паттерны). ECLAT (пересечение вертикальных наборов идентификаторов) является альтернативой; для самих правил, сочетайте с генерацией ассоциативных правил.
Ограничения и замечания
- FP-tree должен помещаться в памяти; очень большие наборы данных могут не подойти.
- На разреженных данных дерево плохо сжимается, сводя на нет преимущество.
- Рекурсивное построение условного дерева относительно сложно в реализации.
- Чувствителен к минимальному порогу поддержки, как и все методы извлечения частых наборов элементов.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Отсутствие генерации кандидатов — намного быстрее, чем Apriori на больших/плотных данных.
- Всего два прохода по базе данных, независимо от длины паттерна.
- FP-tree сжимает общую структуру, экономя память и время на плотных данных.
- Масштабируется до длинных частых паттернов, которые перегружают методы, основанные на кандидатах.
Применение
- Анализ рыночной корзины и майнинг ассоциативных правил в розничной торговле.
- Анализ веб-использования и паттернов кликстрима.
- Рекомендации на основе часто совместно встречающихся элементов.
- Анализ совместной встречаемости и поиск мотивов в биоинформатике.
- Любая крупномасштабная задача извлечения частых наборов элементов, где Apriori слишком медлен.
Как это работает
Как это работает
Первый проход по базе данных подсчитывает поддержку каждого элемента и отбрасывает те, которые ниже минимального порога поддержки. Выжившие частые элементы сортируются по убыванию частоты — этот порядок позволяет транзакциям совместно использовать префиксы дерева и сохраняет FP-tree компактным.
Формула
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}Второй проход вставляет каждую транзакцию (ее частые элементы в отсортированном порядке) в FP-tree, увеличивая счетчики вдоль общих префиксных путей и добавляя новые ветви по мере необходимости. Заголовочная таблица связывает все вхождения каждого элемента, поэтому дерево компактно представляет частую структуру всего набора данных.
Формула
\text{second scan: insert each transaction's frequent items into the FP-tree}Для каждого частого элемента (обрабатываемого от наименее частого к наиболее частому) алгоритм собирает его условную базу паттернов — набор префиксных путей в дереве, которые совместно встречаются с этим элементом, каждый взвешенный по его счету. Это захватывает контекст, в котором элемент встречается часто.
Формула
\text{for each item: collect its conditional pattern base (prefix paths)}Из каждой условной базы паттернов строится и рекурсивно извлекается меньшее условное FP-tree, наращивая более длинные частые наборы элементов путем добавления элемента к паттернам, найденным в его условном дереве. Рекурсия завершается на однопутевых деревьях, комбинации элементов которых перечисляются напрямую — выдавая все частые наборы элементов без генерации кандидатов.
Формула
\text{build conditional FP-trees recursively to grow frequent patterns}Частые ошибки
- Установка минимальной поддержки слишком низкой, что приводит к взрыву наборов элементов.
- Предположение, что он всегда превосходит Apriori — на малых или разреженных данных выигрыш невелик.
- Забывание, что частые наборы элементов — это не правила; генерация правил — отдельный шаг.
- Упущение ограничений памяти, когда FP-tree не может быть помещен в ОЗУ.
Часто задаваемые вопросы
Почему FP-Growth быстрее, чем Apriori?
Apriori многократно генерирует и тестирует кандидатные наборы элементов, многократно сканируя базу данных. FP-Growth полностью избегает генерации кандидатов: он сжимает данные в FP-tree за два прохода и рекурсивно извлекает паттерны из него. Это устраняет комбинаторный взрыв кандидатов, обеспечивая значительное ускорение на плотных данных.
Что такое FP-tree?
Сжатое префиксное дерево частых элементов базы данных. Транзакции, имеющие общий префикс, разделяют путь, причем счетчики узлов записывают поддержку, а заголовочная таблица связывает вхождения каждого элемента. Он компактно хранит частую структуру набора данных, так что паттерны могут быть считаны без повторного сканирования данных.
Как FP-Growth связан с ECLAT и ассоциативными правилами?
FP-Growth, ECLAT и Apriori находят частые наборы элементов; ECLAT использует подход вертикального пересечения наборов идентификаторов вместо дерева. Нахождение частых наборов элементов — это только первый этап; ассоциативные правила (с уверенностью/подъемом) генерируются из этих наборов элементов на отдельном шаге.
Похожие методы
Источники
Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.
Открыть ссылку DOIСкопировано.Han, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(1), 53–87.
Открыть ссылку DOIСкопировано.