Лекція 12. Алгоритм FP-Growth. Пошук частих наборів без генерації кандидатів #

Огляд #

У Лекції 11 ми звели пошук асоціативних правил до двох кроків, з яких обчислювально важкий — пошук усіх частих наборів (наборів із $\operatorname{supp} \ge s_{\min}$). Два алгоритми розв’язували цю задачу: Apriori (горизонтальний) будував кандидатів з’єднанням частих $(k{-}1)$-наборів, відсіював тих, у кого є нечаста підмножина, і рахував решту окремим проходом по базі на кожному рівні; Eclat (вертикальний) уникав повторних проходів, дістаючи підтримку перетином tid-множин.

Обидва працюють, але мають спільну ваду: вони так чи інакше перебирають кандидатів. На щільних базах із багатьма частими елементами кандидатів стає астрономічно багато, а Apriori ще й сканує базу знову й знову. У цій лекції ми розберемо третій, найпоширеніший на практиці метод — FP-Growth (англ. Frequent Pattern Growth, «нарощування частих образів»). Його ідея інша: стиснути всю базу в компактне дерево — FP-дерево (англ. frequent pattern tree) — за два проходи, а тоді видобувати часті набори безпосередньо з дерева, зовсім не породжуючи кандидатів.

Практичний бік. FP-дерево ви будуватимете й «обходитимете» руками, а потім реалізуєте FP-Growth програмою в Лабораторній роботі 12. Далі — Лекція 13.

Щоб порівняння з Apriori було прямим, ми беремо ту саму наскрізну транзакційну базу, що й у Лекції 11 (шість чеків над п’ятьма товарами):

Тут $N = 6$, множина товарів $I = \{\text{Хліб}, \text{Молоко}, \text{Масло}, \text{Яйця}, \text{Кава}\}$, а поріг залишаємо той самий — $s_{\min} = 0.5$ (набір частий, коли він є принаймні у $3$ з $6$ транзакцій). Наприкінці ми переконаємось, що FP-Growth знаходить точно ті самі часті набори, що й Apriori у Прикладі 11.5.

12.1 Обмеження Apriori #

Apriori простий і надійний, але два його місця стають вузькими на великих даних.

• Вартість кандидатів. На кожному рівні генерується багато кандидатів, і переважна більшість зрештою виявляється нечастими — тобто робота на їхнє породження й підрахунок витрачена намарно. Уже на другому рівні кандидатів-пар близько $\binom{|L_1|}{2}$; якщо частих 1-наборів тисячі, це мільйони пар. А в найгіршому разі, щоб знайти один частий набір довжини $m$, довелося б перебрати всі його $2^m - 1$ підмножин як кандидатів проміжних рівнів — експоненційний вибух.
• Багаторазові проходи по базі. Щоб порахувати підтримку кандидатів рівня $k$, Apriori сканує всю базу — і так на кожному рівні. Якщо найдовший частий набір має розмір $m$, база читається $m$ разів. На базі, що не вміщується в пам’ять, ці повторні читання з диска коштують найдорожче.

Eclat прибирає повторні проходи (вертикальний формат, підтримка через перетини), але його tid-множини на щільних базах стають великими й важкими за пам’яттю.

Ідея FP-Growth. Замість «породити кандидатів — перевірити базою» зробити навпаки: один раз стиснути базу в дерево, що зберігає всю потрібну для підрахунку інформацію, а тоді читати часті набори прямо з нього. Тоді проходів по базі лише два (порахувати частоти елементів; вставити транзакції в дерево), а кандидати не породжуються взагалі.

12.2 FP-дерево #

FP-дерево — це префіксне дерево транзакцій. Кожну транзакцію, залишивши в ній лише часті елементи й упорядкувавши їх за спаданням частоти, вставляють як шлях від кореня; транзакції зі спільним початком діляться спільними вузлами, а кожен вузол лічить, скільки транзакцій крізь нього пройшло.

Означення (FP-дерево). FP-дерево — це кореневе дерево, у якому: корінь позначено як null; кожен інший вузол зберігає елемент і лічильник (скільки транзакцій проходить крізь цей вузол цим шляхом); а транзакція, обмежена частими елементами й упорядкована за спільним порядком $\prec$, є шляхом від кореня. Вузли з тим самим елементом додатково з’єднані у список зв’язків між вузлами (англ. node-links).

Дерево будують за два проходи по базі.

• 1-й прохід — частоти й порядок. Порахувати підтримку кожного елемента, відкинути нечасті (за властивістю Apriori вони не ввійдуть у жоден частий набір), а решту впорядкувати за спаданням частоти. Цей упорядкований список частих елементів називають $F$-списком; саме його порядок $\prec$ використовують далі скрізь.
• 2-й прохід — вставлення транзакцій. Для кожної транзакції залишити лише часті елементи, відсортувати їх за $F$-списком і вставити як шлях від кореня: спільний із наявними гілками префікс нарощує лічильники вже наявних вузлів, а розбіжний «хвіст» додає нові вузли.

Чому саме за спаданням частоти? Тоді найпоширеніші елементи опиняються близько до кореня й діляться найбільшою кількістю транзакцій — це дає максимальне стиснення. Що частіше елементи трапляються разом, то компактніше дерево; у крайньому разі, коли всі транзакції однакові, воно вироджується в єдиний шлях.

Означення (заголовна таблиця). Заголовна таблиця (англ. header table) зберігає для кожного частого елемента його сумарну частоту й покажчик на перший його вузол у дереві. Усі вузли того самого елемента сполучено списком node-links. Таблиця дає змогу, узявши елемент, швидко обійти всі його появи в дереві — це основа етапу видобутку (§12.4–12.5).

Отже, FP-дерево + заголовна таблиця разом зберігають усю інформацію, потрібну для підрахунку підтримки будь-якого частого набору, — але вже без бази й без кандидатів.

12.3 Побудова FP-дерева (наскрізний приклад) #

Побудуймо FP-дерево для наскрізної бази за $s_{\min} = 0.5$ (лічильник $\ge 3$).

1-й прохід — частоти елементів. Це той самий підрахунок, що й у Кроці 1 Apriori:

Кава відпадає. Решту впорядковуємо за спаданням частоти; за рівних частот (Хліб і Молоко — обидва $5$) зберігаємо початковий порядок елементів. Дістаємо $F$-список:

$$\text{Хліб}(5) \ \prec\ \text{Молоко}(5) \ \prec\ \text{Масло}(4) \ \prec\ \text{Яйця}(3).$$

2-й прохід — упорядкування транзакцій. Викидаємо нечасті елементи (Кава) і сортуємо кожну транзакцію за $F$-списком:

Вставлення шляхів. Ідемо транзакціями по черзі. $t_1$ створює перший шлях Хліб→Молоко→Яйця (усі лічильники $1$). $t_2$ ділить із ним корінь-вузол Хліб (його лічильник стає $2$) і додає нову гілку Масло. $t_3$ подовжує гілку Хліб→Молоко й добудовує Масло→Яйця. $t_4$ — важливий випадок: вона починається з Молоко, а не з Хліб, тож спільного префікса з наявними гілками немає — з’являється новий вузол Молоко просто під коренем. $t_5$ і $t_6$ лягають уздовж наявної гілки Хліб→Молоко…, лише нарощуючи лічильники. Остаточне дерево:

null
├─ Хліб:5
│  ├─ Молоко:4
│  │  ├─ Яйця:2
│  │  └─ Масло:2
│  │     └─ Яйця:1
│  └─ Масло:1
└─ Молоко:1
   └─ Масло:1

Заголовна таблиця (частота елемента + його вузли, сполучені node-links):

Корисна перевірка: сума лічильників усіх вузлів одного елемента дорівнює його частоті. Молоко: $4 + 1 = 5$; Масло: $2 + 1 + 1 = 4$; Яйця: $2 + 1 = 3$ — усе збігається з 1-м проходом. Зверніть увагу на стиснення: якби кожну транзакцію зберігати окремим шляхом, часті елементи шести транзакцій зайняли б $3 + 2 + 4 + 2 + 3 + 3 = 17$ вузлів, а завдяки спільним префіксам їх лише вісім.

Типова помилка (не відсортувати транзакцію за $F$-списком). Якщо вставляти елементи транзакції у довільному порядку, транзакції зі спільними товарами підуть різними гілками, спільні префікси не зіллються, дерево розростеться, а заголовні зв’язки перестануть відповідати підтримкам. Єдиний спільний порядок $\prec$ (за спаданням частоти) — обов’язкова умова коректності й компактності.

12.4 Умовна база образів та умовне FP-дерево #

Дерево збудовано; тепер із нього треба видобути часті набори. FP-Growth робить це методом «поділяй і володарюй»: для кожного частого елемента $i$ (починаючи з найрідшого — знизу заголовної таблиці) він розглядає лише ті частини дерева, що ведуть до $i$, і зводить задачу до меншого дерева.

Означення (умовна база образів). Умовна база образів (англ. conditional pattern base) елемента $i$ — це множина префіксних шляхів усіх вузлів $i$ у дереві: для кожного вузла $i$ беруть шлях від кореня до нього, не включаючи сам $i$, і приписують цьому шляху лічильник самого вузла $i$.

Умовна база образів — це немовби «маленька транзакційна база», що описує, у якому оточенні трапляється $i$.

Означення (умовне FP-дерево). Умовне FP-дерево елемента $i$ — це FP-дерево, побудоване з його умовної бази образів (кожен префіксний шлях — «транзакція» зі своїм лічильником), у якому лишено тільки ті елементи, що лишаються частими вже в межах цієї бази (їхня сумарна частота $\ge s_{\min} N$).

Приклад 12.1 (умовна база й умовне дерево для Яйця). Найрідший частий елемент — Яйця (частота $3$). За заголовною таблицею його вузли:

• Яйця:2 — під Хліб→Молоко; префіксний шлях $(\text{Хліб}, \text{Молоко})$ з лічильником $2$;
• Яйця:1 — під Хліб→Молоко→Масло; префіксний шлях $(\text{Хліб}, \text{Молоко}, \text{Масло})$ з лічильником $1$.

Отже, умовна база образів Яйця:

$$(\text{Хліб}, \text{Молоко}) : 2, \qquad (\text{Хліб}, \text{Молоко}, \text{Масло}) : 1.$$

Порахуймо частоти елементів у цій базі: Хліб $= 2 + 1 = 3$, Молоко $= 2 + 1 = 3$, Масло $= 0 + 1 = 1$. Масло не набирає порога ($1 < 3$) — його відкидають. Лишаються Хліб($3$) і Молоко($3$), і умовне FP-дерево Яйця — єдиний шлях:

null
└─ Хліб:3
   └─ Молоко:3      (умовне дерево для Яйця)

Чому обхід іде знизу вгору (від найрідшого елемента)? Бо коли ми беремо $i$, усі елементи, що стоять у $F$-списку після нього, вже оброблено, і в префіксних шляхах їх немає — задача для $i$ чисто «дивиться вгору», на спільні префікси, і не перетинається з уже завершеними гілками.

12.5 Рекурсивний видобуток частих наборів #

Тепер алгоритм цілком. Часті набори «нарощують» від суфікса: маючи вже знайдений набір $\alpha$ (спершу порожній), для кожного елемента $i$ утворюють більший набір $\alpha \cup \{i\}$ і рекурсивно шукають, чим його ще можна доповнити — у його умовному дереві.

FP-Growth(Дерево, α):
  якщо Дерево — єдиний шлях P:
    для кожної непорожньої підмножини β вузлів шляху P:
       вивести набір  β ∪ α
         з підтримкою = найменший лічильник вузлів у β
  інакше:
    для кожного елемента i заголовної таблиці (знизу вгору):
       β <- α ∪ { i }
       вивести набір β з підтримкою = сумарний лічильник i
       побудувати умовну базу образів i та умовне FP-дерево Дерево_i
       якщо Дерево_i не порожнє:
          FP-Growth(Дерево_i, β)        # рекурсія: заглиблення

Гілка «єдиний шлях» — важлива оптимізація: якщо дерево (чи умовне дерево) виродилося в ланцюжок, часті набори з нього не треба шукати рекурсивно — можна одразу виписати всі комбінації його вузлів, а підтримкою комбінації є найменший з лічильників (найглибший вузол). Саме так закриється приклад із Яйця.

Приклад 12.2 (повний видобуток на наскрізній базі) #

Обходимо заголовну таблицю знизу вгору: Яйця, Масло, Молоко, Хліб.

Яйця. Виводимо $\{\text{Яйця}\}$ з підтримкою $3$. Умовне дерево Яйця (Приклад 12.1) — єдиний шлях Хліб:3 → Молоко:3. Виписуємо всі комбінації його вузлів, приєднавши суфікс Яйця:

$$\{\text{Хліб}, \text{Яйця}\}:3, \quad \{\text{Молоко}, \text{Яйця}\}:3, \quad \{\text{Хліб}, \text{Молоко}, \text{Яйця}\}:3.$$

Масло. Виводимо $\{\text{Масло}\}$ з підтримкою $4$. Вузли Масло дають умовну базу образів:

$$(\text{Хліб}):1, \qquad (\text{Хліб}, \text{Молоко}):2, \qquad (\text{Молоко}):1.$$

Частоти в базі: Хліб $= 1 + 2 = 3$, Молоко $= 2 + 1 = 3$ — обидва часті. Але умовне дерево Масло не є єдиним шляхом (Молоко трапляється і під Хліб, і під коренем):

null
├─ Хліб:3
│  └─ Молоко:2
└─ Молоко:1            (умовне дерево для Масло)

Тому рекурсуємо в ньому (знизу вгору: Молоко, потім Хліб):

• Молоко в умовному дереві Масло: виводимо $\{\text{Молоко}, \text{Масло}\}:3$. Його умовна база тут — $(\text{Хліб}):2$; Хліб має лічильник $2 < 3$, відпадає — далі порожньо.
• Хліб в умовному дереві Масло: виводимо $\{\text{Хліб}, \text{Масло}\}:3$. Хліб — під коренем, умовна база порожня.

Зверніть увагу: набір $\{\text{Хліб}, \text{Молоко}, \text{Масло}\}$ не з’явився — і правильно: він є лише в $t_3, t_5$ (підтримка $2 < 3$). Поріг $s_{\min}$ застосовується наново всередині кожного умовного дерева, і саме він відсіяв Хліб на під-кроці Молоко.

Молоко. Виводимо $\{\text{Молоко}\}:5$. Умовна база — $(\text{Хліб}):4$; умовне дерево — єдиний вузол Хліб:4, звідки $\{\text{Хліб}, \text{Молоко}\}:4$.

Хліб. Виводимо $\{\text{Хліб}\}:5$. Це найчастіший елемент, він завжди під коренем — умовна база порожня, рекурсії немає.

Усі знайдені часті набори (лічильник $\ge 3$) і звірка з Apriori (Приклад 11.5):

Це точно той самий список частих наборів, що його знайшов Apriori у Прикладі 11.5, — і єдиний частий 3-набір знову $\{\text{Хліб}, \text{Молоко}, \text{Яйця}\}$. Але FP-Growth дійшов до нього без жодного кандидата й лише за два проходи по базі. Далі з цих частих наборів правила генерують так само, як у §11.6 (крок дешевий — усі потрібні підтримки вже пораховано).

Типова помилка (не перерахувати частоти в умовній базі). Умовна база образів — це вже інша маленька база, і поріг $s_{\min}$ треба застосувати до неї заново. Якщо цього не зробити (лишити в умовному дереві елемент, що частий у всій базі, але не в цій умовній), з’являться зайві «часті» набори на кшталт $\{\text{Хліб}, \text{Молоко}, \text{Масло}\}$, яких насправді немає.

12.6 Порівняння: Apriori, Eclat, FP-Growth #

Усі три алгоритми знаходять той самий набір частих наборів — різняться лише тим, як вони рахують підтримку й чи породжують кандидатів.

Коротко про сильні й слабкі сторони:

• Apriori — найпростіший і найощадливіший за пам’яттю; страждає від вибуху кандидатів і багатьох проходів. Добрий для невеликих або дуже розріджених баз і як еталон для перевірки.
• Eclat — прибирає повторні проходи (підтримка через перетини); швидкий на розріджених базах, але його tid-множини роздуваються на щільних.
• FP-Growth — узагалі не породжує кандидатів і робить два проходи; на щільних базах із багатьма спільними префіксами дерево виходить дуже компактним, і метод зазвичай найшвидший. Слабке місце — навпаки, розріджені бази з малим спільним префіксом: тоді дерево майже не стискається (гілок майже стільки ж, скільки транзакцій), а рекурсія з безліччю умовних дерев дорога.

Коли який. На щільних базах (багато частих елементів, довгі часті набори) переможець зазвичай FP-Growth — стиснення в дерево окупається. На розріджених базах виграє Eclat (малі tid-множини) або й простий Apriori. Якщо потрібна проста, передбачувана за пам’яттю реалізація чи еталон для звірки — беруть Apriori. Результат (часті набори) у всіх трьох однаковий — обирають за швидкодією й пам’яттю під конкретні дані.

Застосування в аналітиці даних #

• Промисловий пошук частих наборів. Саме FP-Growth (та його паралельні версії) — стандарт для великих транзакційних баз рітейлу, де кандидати Apriori не поміщаються в пам’ять; він лежить в основі готових реалізацій частого аналізу образів у бібліотеках аналітики великих даних.
• Рекомендації й розкладка — у масштабі. Ті самі правила «з $X$ беруть $Y$» (Лекція 11), але дерево дає змогу знаходити часті набори на мільйонах чеків за прийнятний час.
• Веб-, лог- та текст-аналітика. Часті послідовності сторінок, спільні теги/слова, шаблони подій — щільні дані, де стиснення в дерево особливо вигідне.
• «Поділяй і володарюй» через умовні бази — загальний прийом: звести пошук образів до менших підзадач на стиснутому поданні даних; він застосовний і поза ринковим кошиком (часті підграфи, послідовності, епізоди).

Підсумок #

• FP-Growth шукає часті набори без генерації кандидатів і лише за два проходи по базі, стискаючи її у FP-дерево.
• FP-дерево — префіксне дерево транзакцій: часті елементи кожної транзакції сортують за спаданням частоти ($F$-список) і вставляють як шлях; спільні префікси діляться вузлами, кожен вузол має лічильник. Заголовна таблиця зі зв’язками між вузлами дає швидкий доступ до всіх появ елемента.
• Видобуток іде знизу вгору заголовною таблицею: для елемента $i$ будують умовну базу образів (префіксні шляхи його вузлів із їхніми лічильниками) та умовне FP-дерево (лишивши елементи, часті вже в цій базі), і рекурсивно повторюють; єдиний шлях дозволяє одразу виписати всі комбінації.
• Поріг $s_{\min}$ застосовують наново всередині кожного умовного дерева — це й відсіює несправжні набори.
• На наскрізній базі ($s_{\min} = 0.5$) FP-Growth дає ті самі десять частих наборів, що й Apriori, з єдиним частим 3-набором $\{\text{Хліб}, \text{Молоко}, \text{Яйця}\}$ — але без кандидатів.
• Apriori / Eclat / FP-Growth знаходять однакові часті набори; вибір — за щільністю бази: FP-Growth на щільних, Eclat/Apriori на розріджених.

Вправи #

Для розігріву #

1. Поясніть, навіщо в 1-му проході відкидають нечасті елементи ще до побудови дерева. На яку властивість (Лекція 11) це спирається?
2. Чому елементи в транзакції сортують саме за спаданням частоти, перш ніж вставляти в дерево? Що станеться зі стисненням, якщо взяти довільний порядок?
3. За готовим FP-деревом наскрізної бази (§12.3) випишіть умовну базу образів для елемента Молоко і побудуйте його умовне FP-дерево.

Стандартні #

4. Побудуйте FP-дерево для наскрізної бази за нижчим порогом $s_{\min} = \tfrac{1}{3}$ (лічильник $\ge 2$): наведіть новий $F$-список (тепер і Масло, і, можливо, інші пари стануть частими), відсортовані транзакції й остаточне дерево. Порівняйте з деревом за $s_{\min} = 0.5$.
5. Видобудьте всі часті набори з дерева, побудованого у вправі 4, обходячи заголовну таблицю знизу вгору. Чи стане частим набір $\{\text{Хліб}, \text{Молоко}, \text{Масло}\}$? Звірте результат з Apriori за тим самим порогом (вправа 5 Лекції 11).
6. Для елемента Масло (за $s_{\min} = 0.5$) покажіть, чому його умовне дерево не є єдиним шляхом, і простежте рекурсію крок за кроком. Поясніть, на якому під-кроці й чому відсівається Хліб.

Підвищеної складності #

7. Доведіть, що сума лічильників усіх вузлів одного елемента у FP-дереві дорівнює підтримці (лічильнику) цього елемента. Спираючись на це, поясніть, чому підтримка будь-якого частого набору коректно відновлюється з умовних дерев.
8. Оцініть кількість вузлів FP-дерева у двох крайніх випадках: (а) усі $N$ транзакцій однакові; (б) жодні дві транзакції не мають спільного префікса (після впорядкування). Як ці випадки пояснюють, чому FP-Growth виграє на щільних і програє на розріджених базах?
9. Порівняйте обсяг роботи Apriori та FP-Growth на наскрізній базі: скільки кандидатів порахував Apriori (Приклад 11.5) і скільки умовних дерев побудував FP-Growth (Приклад 12.2)? Запропонуйте, як експериментально виміряти їхню швидкодію на дедалі більших випадкових базах і на яких даних очікувати переваги кожного (див. високий рівень Лабораторної 12).

Lectures/DA-L12.md · 36.6 KB · updated 2026-08-05 09:44