Skip to content
Назад к результатам поиска

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 слишком медлен.

Как это работает

Как это работает

1

Первый проход по базе данных подсчитывает поддержку каждого элемента и отбрасывает те, которые ниже минимального порога поддержки. Выжившие частые элементы сортируются по убыванию частоты — этот порядок позволяет транзакциям совместно использовать префиксы дерева и сохраняет FP-tree компактным.

Формула
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}
2

Второй проход вставляет каждую транзакцию (ее частые элементы в отсортированном порядке) в FP-tree, увеличивая счетчики вдоль общих префиксных путей и добавляя новые ветви по мере необходимости. Заголовочная таблица связывает все вхождения каждого элемента, поэтому дерево компактно представляет частую структуру всего набора данных.

Формула
\text{second scan: insert each transaction's frequent items into the FP-tree}
3

Для каждого частого элемента (обрабатываемого от наименее частого к наиболее частому) алгоритм собирает его условную базу паттернов — набор префиксных путей в дереве, которые совместно встречаются с этим элементом, каждый взвешенный по его счету. Это захватывает контекст, в котором элемент встречается часто.

Формула
\text{for each item: collect its conditional pattern base (prefix paths)}
4

Из каждой условной базы паттернов строится и рекурсивно извлекается меньшее условное 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 использует подход вертикального пересечения наборов идентификаторов вместо дерева. Нахождение частых наборов элементов — это только первый этап; ассоциативные правила (с уверенностью/подъемом) генерируются из этих наборов элементов на отдельном шаге.

Похожие методы

Источники

  1. Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.

    Открыть ссылку DOI
    Скопировано.
  2. 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
    Скопировано.