Skip to content

FP-Growth

FP-Growth (Frequent Pattern Growth) — мощный алгоритм для поиска ассоциативных правил и часто встречающихся наборов элементов (itemsets) в транзакционных базах данных. Он используется в анализе корзин покупок (Market Basket Analysis), рекомендательных системах и других задачах, связанных с поиском ассоциативных правил.

Основные бласти применения

  1. Торговля (анализ корзин покупок, выявление ассоциативных правил типа "если X, то Y")
  2. Рекомендательные системы (подбор сопутствующих товаров, как в Amazon или Netflix)
  3. Биотехнологии и медицина (поиск частых сочетаний симптомов и заболеваний)
  4. Экономика и финансы (анализ подозрительных комбинаций операций в банковской сфере)
  5. Веб-аналитика (выявление паттернов поведения пользователей, например, последовательностей просмотренных страниц)

Основные Понятия

Частые Наборы (Frequent Itemsets)

Набор элементов называется частым, если он встречается в транзакциях не реже заданного минимального порога поддержки (min_support).

Дерево FP (FP-Tree)

FP-Growth строит сжатое префиксное дерево (FP-Tree), которое эффективно хранит информацию о часто встречающихся наборах.

Условные Базы (Conditional Pattern Bases)

Алгоритм рекурсивно строит условные FP-деревья для поиска всех частых наборов.

Пример на Python

Установим библиотеку:

pip install mlxtend

Построение частых наборов с FP-Growth

import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import fpgrowth

# Пример данных (транзакции в супермаркете)
transactions = [
    ['хлеб', 'молоко', 'яйца'],
    ['хлеб', 'печенье', 'кола'],
    ['молоко', 'печенье', 'кола'],
    ['хлеб', 'молоко', 'печенье', 'кола'],
    ['хлеб', 'молоко', 'печенье']
]

# Преобразуем в бинарную матрицу
te = TransactionEncoder()
te_ary = te.fit(transactions).transform(transactions)
df = pd.DataFrame(te_ary, columns=te.columns_)

# Находим частые наборы (min_support = 0.4)
frequent_itemsets = fpgrowth(df, min_support=0.4, use_colnames=True)
print(frequent_itemsets)

Вывод:

   support              itemsets
0      0.8               [хлеб]
1      0.8              [молоко]
2      0.8            [печенье]
3      0.6               [кола]
4      0.6        [хлеб, молоко]
5      0.6      [хлеб, печенье]
6      0.6     [молоко, печенье]
7      0.6  [хлеб, молоко, печенье]

Генерация ассоциативных правил

from mlxtend.frequent_patterns import association_rules

# Генерируем правила с минимальным доверием 0.7
rules = association_rules(frequent_itemsets, metric="confidence", min_threshold=0.7)
print(rules[['antecedents', 'consequents', 'support', 'confidence']])

Вывод:

        antecedents     consequents  support  confidence
0        (хлеб)         (молоко)      0.6    0.75
1        (молоко)        (хлеб)       0.6    0.75
2  (хлеб, печенье)      (молоко)      0.6    1.00
3  (молоко, печенье)     (хлеб)       0.6    1.00

Интерпретация:

  • Если покупатель берет хлеб и печенье, то с вероятностью 100% он купит и молоко (confidence = 1.0).

Плюсы и Минусы FP-Growth

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

  • Эффективнее Apriori (не требует генерации кандидатов).
  • Работает с большими наборами данных.
  • Хорошо масштабируется.

Недостатки:

  • Требует построения FP-дерева, что может затратно по памяти.
  • Чувствителен к выбору min_support.