2. Методичні вказівки #

Цей розділ самодостатній: у ньому зібрано теорію алгоритму FP-Growth — FP-дерево, умовну базу образів, умовне FP-дерево й рекурсивний видобуток — потрібну для аудиторних задач (3classroom.md) і домашньої програми (4task.md). Ширше цю саму теорію викладено в Лекції 12; означення асоціативних правил і мір інтересовності — у Лекції 11 та методичних вказівках Лабораторної 11.

2.1 Транзакційна база та часті набори (нагадування) #

Транзакційна база — множина транзакцій $D = \{t_1, \dots, t_N\}$ над множиною елементів $I$; кожна транзакція $t_i \subseteq I$ — набір елементів. Набір $X \subseteq I$ частий, якщо його підтримка

$$\operatorname{supp}(X) = \frac{|\{\, t \in D : X \subseteq t \,\}|}{N} \ge s_{\min}.$$

Зручно тримати лічильник $|\{t : X \subseteq t\}|$ і порівнювати його з $s_{\min}\cdot N$. Пошук асоціативних правил зводиться до пошуку всіх частих наборів (решта — генерація правил — дешева); саме цю важку частину й розв’язує FP-Growth.

2.2 Навіщо FP-Growth #

Apriori (Лабораторна 11) породжує кандидатів і сканує базу на кожному рівні — на щільних базах кандидатів стає надто багато, а повторні проходи дорогі. FP-Growth уникає обох вад:

Ідея FP-Growth. Стиснути всю базу в компактне FP-дерево за два проходи, а тоді видобувати часті набори прямо з дерева, не породжуючи кандидатів.

2.3 FP-дерево та його побудова #

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

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

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

Заголовна таблиця зберігає для кожного частого елемента його сумарну частоту й покажчик на перший вузол; усі вузли елемента сполучено node-links. Найпоширеніші елементи стоять близько до кореня — звідси стиснення.

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

Видобуток іде знизу вгору заголовною таблицею (від найрідшого елемента).

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

2.5 Рекурсивний видобуток (FP-Growth) #

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

Спершу викликають FP-Growth(усе_дерево, ∅). Гілка «єдиний шлях» — важлива оптимізація: із ланцюжка одразу виписують усі комбінації його вузлів (підтримка комбінації — найменший лічильник). Поріг $s_{\min}$ застосовують наново в кожному умовному дереві — це відсіює несправжні набори.

2.6 Apriori / Eclat / FP-Growth #

Усі три знаходять той самий набір частих наборів; різниця — у способі:

2.7 Демонстраційний приклад (на інших даних, ніж у задачах) #

Розгляньмо ту саму базу невеликої чайної крамниці, що й у Лабораторній 11 ($N = 5$) над елементами $I = \{\text{Чай}, \text{Цукор}, \text{Лимон}, \text{Мед}\}$ — і застосуймо до неї FP-Growth за тим самим порогом $s_{\min} = 0.4$ (лічильник $\ge 2$):

(а) 1-й прохід — $F$-список. Частоти: Чай $4$, Цукор $3$, Лимон $3$, Мед $2$ — усі часті ($\ge 2$). За спаданням частоти (рівні Цукор і Лимон — у початковому порядку):

$$\text{Чай}(4) \prec \text{Цукор}(3) \prec \text{Лимон}(3) \prec \text{Мед}(2).$$

(б) 2-й прохід — упорядковані транзакції й дерево.

Вставивши шляхи (транзакція $t_5$ починається з Лимон і дає нову гілку під коренем), дістаємо:

null
├─ Чай:4
│  ├─ Цукор:3
│  │  ├─ Лимон:1
│  │  └─ Мед:1
│  └─ Лимон:1
└─ Лимон:1
   └─ Мед:1

Заголовна таблиця: Чай($4$): Чай:4; Цукор($3$): Цукор:3; Лимон($3$): Лимон:1 → Лимон:1 → Лимон:1; Мед($2$): Мед:1 → Мед:1. Перевірка сум: Лимон $1+1+1 = 3$, Мед $1+1 = 2$ — збігається з частотами.

(в) Видобуток (знизу вгору: Мед, Лимон, Цукор, Чай).

• Мед — $\{\text{Мед}\}:2$. Умовна база образів: $(\text{Чай}, \text{Цукор}):1$ і $(\text{Лимон}):1$. Частоти в базі: Чай $1$, Цукор $1$, Лимон $1$ — усі $< 2$, тож умовне дерево порожнє. Жодної частої пари з Мед немає.
• Лимон — $\{\text{Лимон}\}:3$. Умовна база: $(\text{Чай}, \text{Цукор}):1$ і $(\text{Чай}):1$. Частоти: Чай $2$, Цукор $1$ — Цукор відпадає. Умовне дерево — єдиний вузол Чай:2, звідки $\{\text{Чай}, \text{Лимон}\}:2$.
• Цукор — $\{\text{Цукор}\}:3$. Умовна база: $(\text{Чай}):3$; умовне дерево Чай:3, звідки $\{\text{Чай}, \text{Цукор}\}:3$.
• Чай — $\{\text{Чай}\}:4$; під коренем, умовна база порожня.

Часті набори: 1-набори — Чай($4$), Цукор($3$), Лимон($3$), Мед($2$); 2-набори — $\{\text{Чай}, \text{Цукор}\}$($3$) і $\{\text{Чай}, \text{Лимон}\}$($2$); частих наборів розміру $\ge 3$ немає. Це точно той самий результат, що дав Apriori на цій базі в Лабораторній 11 (§2.8) — але без кандидатів.

2.8 Робочий контрольний список #

• Спершу зафіксуйте поріг $s_{\min}$ і переведіть його в лічильник $s_{\min}\cdot N$.
• 1-й прохід: порахуйте частоти, відкиньте нечасті, складіть $F$-список (за спаданням частоти; рівні — у сталому порядку).
• 2-й прохід: кожну транзакцію відсортуйте за $F$-списком перед вставленням — інакше спільні префікси не зіллються.
• Перевіряйте дерево: сума лічильників вузлів елемента $=$ його частота.
• Видобуток ведіть знизу вгору заголовною таблицею; для кожного елемента — умовна база образів $\to$ умовне дерево $\to$ рекурсія; єдиний шлях — одразу всі комбінації.
• Поріг $s_{\min}$ перевіряйте наново в кожній умовній базі.
• Наприкінці звірте список частих наборів із Apriori/Eclat — вони мають збігтися.

Laboratory/Laboratory12/2method.md · 12.1 KB · updated 2026-08-05 09:45