# Лекція 12. Алгоритм FP-Growth. Пошук частих наборів без генерації кандидатів ## Огляд У [Лекції 11](DA-L11.md) ми звели пошук асоціативних правил до двох кроків, з яких обчислювально важкий — **пошук усіх частих наборів** (наборів із $\operatorname{supp} \ge s_{\min}$). Два алгоритми розв'язували цю задачу: **Apriori** (горизонтальний) будував кандидатів з'єднанням частих $(k{-}1)$-наборів, відсіював тих, у кого є нечаста підмножина, і рахував решту **окремим проходом по базі на кожному рівні**; **Eclat** (вертикальний) уникав повторних проходів, дістаючи підтримку **перетином tid-множин**. Обидва працюють, але мають спільну ваду: вони так чи інакше **перебирають кандидатів**. На щільних базах із багатьма частими елементами кандидатів стає астрономічно багато, а Apriori ще й **сканує базу знову й знову**. У цій лекції ми розберемо третій, найпоширеніший на практиці метод — **FP-Growth** (англ. *Frequent Pattern Growth*, «нарощування частих образів»). Його ідея інша: **стиснути всю базу в компактне дерево** — **FP-дерево** (англ. *frequent pattern tree*) — за **два проходи**, а тоді видобувати часті набори **безпосередньо з дерева, зовсім не породжуючи кандидатів**. > **Практичний бік.** FP-дерево ви будуватимете й «обходитимете» руками, а потім > реалізуєте FP-Growth **програмою** в > [Лабораторній роботі 12](../Laboratory/Laboratory12/main.md). Далі — > [Лекція 13](DA-L13.md). Щоб порівняння з Apriori було **прямим**, ми беремо ту саму наскрізну **транзакційну базу**, що й у Лекції 11 (шість чеків над п'ятьма товарами): | Транзакція | Товари (набір елементів) | |:--:|---| | $t_1$ | Хліб, Молоко, Яйця | | $t_2$ | Хліб, Масло | | $t_3$ | Хліб, Молоко, Масло, Яйця | | $t_4$ | Молоко, Масло | | $t_5$ | Хліб, Молоко, Масло | | $t_6$ | Хліб, Молоко, Яйця, Кава | Тут $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 | так | | Молоко | 5 | так | | Масло | 4 | так | | Яйця | 3 | так | | Кава | 1 | **ні** | Кава відпадає. Решту впорядковуємо за спаданням частоти; за **рівних** частот (Хліб і Молоко — обидва $5$) зберігаємо початковий порядок елементів. Дістаємо **$F$-список**: $$ \text{Хліб}(5) \ \prec\ \text{Молоко}(5) \ \prec\ \text{Масло}(4) \ \prec\ \text{Яйця}(3). $$ ![Стовпчики частот елементів наскрізної бази з лінією порогу підтримки; Кава нечаста й відпадає, решта формують F-список](img/l12_flist.png) **2-й прохід — упорядкування транзакцій.** Викидаємо нечасті елементи (Кава) і сортуємо кожну транзакцію за $F$-списком: | Транзакція | Початково | Часті елементи за $F$-списком | |:--:|---|---| | $t_1$ | Хліб, Молоко, Яйця | Хліб, Молоко, Яйця | | $t_2$ | Хліб, Масло | Хліб, Масло | | $t_3$ | Хліб, Молоко, Масло, Яйця | Хліб, Молоко, Масло, Яйця | | $t_4$ | Молоко, Масло | Молоко, Масло | | $t_5$ | Хліб, Молоко, Масло | Хліб, Молоко, Масло | | $t_6$ | Хліб, Молоко, Яйця, Кава | Хліб, Молоко, Яйця | **Вставлення шляхів.** Ідемо транзакціями по черзі. $t_1$ створює перший шлях `Хліб→Молоко→Яйця` (усі лічильники $1$). $t_2$ ділить із ним корінь-вузол Хліб (його лічильник стає $2$) і додає нову гілку `Масло`. $t_3$ подовжує гілку `Хліб→Молоко` й добудовує `Масло→Яйця`. $t_4$ — важливий випадок: вона починається з **Молоко**, а не з Хліб, тож спільного префікса з наявними гілками немає — з'являється **новий вузол Молоко просто під коренем**. $t_5$ і $t_6$ лягають уздовж наявної гілки `Хліб→Молоко…`, лише нарощуючи лічильники. Остаточне дерево: ```text null ├─ Хліб:5 │ ├─ Молоко:4 │ │ ├─ Яйця:2 │ │ └─ Масло:2 │ │ └─ Яйця:1 │ └─ Масло:1 └─ Молоко:1 └─ Масло:1 ``` ![FP-дерево наскрізної бази: вузли «елемент: лічильник» від кореня null зі спільними префіксами](img/l12_fptree.png) **Заголовна таблиця** (частота елемента + його вузли, сполучені node-links): | Елемент | Частота | Вузли дерева (за зв'язками) | |---|:--:|---| | Хліб | 5 | Хліб:5 | | Молоко | 5 | Молоко:4 → Молоко:1 | | Масло | 4 | Масло:2 → Масло:1 → Масло:1 | | Яйця | 3 | Яйця:2 → Яйця:1 | ![Заголовна таблиця частих елементів і пунктирні зв'язки node-links до їхніх входжень у FP-дереві](img/l12_header.png) Корисна **перевірка**: сума лічильників усіх вузлів одного елемента дорівнює його частоті. Молоко: $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-дерево Яйця** — єдиний шлях: ```text null └─ Хліб:3 └─ Молоко:3 (умовне дерево для Яйця) ``` ![Умовна база образів та умовне FP-дерево елемента Яйця — єдиний шлях Хліб-Молоко](img/l12_conditional.png) Чому обхід іде **знизу вгору** (від найрідшого елемента)? Бо коли ми беремо $i$, усі елементи, що стоять у $F$-списку **після** нього, вже оброблено, і в префіксних шляхах їх немає — задача для $i$ чисто «дивиться вгору», на спільні префікси, і не перетинається з уже завершеними гілками. --- ## 12.5 Рекурсивний видобуток частих наборів Тепер алгоритм цілком. Часті набори «нарощують» від суфікса: маючи вже знайдений набір $\alpha$ (спершу порожній), для кожного елемента $i$ утворюють більший набір $\alpha \cup \{i\}$ і рекурсивно шукають, чим його ще можна доповнити — у **його умовному дереві**. ```text 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$ — обидва часті. Але умовне дерево Масло **не є** єдиним шляхом (Молоко трапляється і під Хліб, і під коренем): ```text null ├─ Хліб:3 │ └─ Молоко:2 └─ Молоко:1 (умовне дерево для Масло) ``` ![Умовна база образів та умовне FP-дерево елемента Масло — розгалужене дерево, не єдиний шлях](img/l12_condbutter.png) Тому **рекурсуємо** в ньому (знизу вгору: Молоко, потім Хліб): - **Молоко** в умовному дереві Масло: виводимо $\{\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): | Частий набір | Підтримка | Звідки у FP-Growth | Apriori (Л11) | |---|:--:|---|:--:| | $\{\text{Хліб}\}$ | $5$ | заголовна таблиця | так | | $\{\text{Молоко}\}$ | $5$ | заголовна таблиця | так | | $\{\text{Масло}\}$ | $4$ | заголовна таблиця | так | | $\{\text{Яйця}\}$ | $3$ | заголовна таблиця | так | | $\{\text{Хліб}, \text{Молоко}\}$ | $4$ | умовне дерево Молоко | так | | $\{\text{Хліб}, \text{Масло}\}$ | $3$ | умовне дерево Масло | так | | $\{\text{Молоко}, \text{Масло}\}$ | $3$ | умовне дерево Масло | так | | $\{\text{Хліб}, \text{Яйця}\}$ | $3$ | умовне дерево Яйця | так | | $\{\text{Молоко}, \text{Яйця}\}$ | $3$ | умовне дерево Яйця | так | | $\{\text{Хліб}, \text{Молоко}, \text{Яйця}\}$ | $3$ | умовне дерево Яйця | так | Це **точно той самий** список частих наборів, що його знайшов Apriori у Прикладі 11.5, — і єдиний частий 3-набір знову $\{\text{Хліб}, \text{Молоко}, \text{Яйця}\}$. Але FP-Growth дійшов до нього **без жодного кандидата** й лише за два проходи по базі. Далі з цих частих наборів **правила** генерують так само, як у §11.6 (крок дешевий — усі потрібні підтримки вже пораховано). > **Типова помилка (не перерахувати частоти в умовній базі).** Умовна база образів > — це вже **інша** маленька база, і поріг $s_{\min}$ треба застосувати до неї > **заново**. Якщо цього не зробити (лишити в умовному дереві елемент, що частий у > всій базі, але **не** в цій умовній), з'являться зайві «часті» набори на кшталт > $\{\text{Хліб}, \text{Молоко}, \text{Масло}\}$, яких насправді немає. --- ## 12.6 Порівняння: Apriori, Eclat, FP-Growth Усі три алгоритми знаходять **той самий** набір частих наборів — різняться лише тим, **як** вони рахують підтримку й **чи** породжують кандидатів. | Ознака | Apriori | Eclat | FP-Growth | |---|---|---|---| | Формат бази | горизонтальний | вертикальний | горизонтальний $\to$ дерево | | Генерація кандидатів | **так** (з'єднання + відсів) | немає (перетини tid-множин) | **немає** (умовні дерева) | | Проходів по базі | по одному на рівень ($\sim m$) | $\sim 1$ (побудова tid-множин) | **рівно $2$** | | Головна пам'ять | мала (лічильники) | tid-множини (великі на щільних) | FP-дерево (компактне на щільних) | | Спосіб підрахунку | прохід по базі щорівня | потужність перетину tid-множин | лічильники у вузлах дерева | ![Концептуальне порівняння Apriori та FP-Growth: багато кандидатів і проходів проти одного дерева за два проходи без кандидатів](img/l12_compare.png) Коротко про сильні й слабкі сторони: - **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](../Laboratory/Laboratory12/main.md)).