# Лекція 7. Ординарні методи класифікації. Дерева рішень ## Огляд У [Лекції 6](DA-L06.md) ми розв'язали задачу класифікації методом $k$ найближчих сусідів: об'єкт відносили до того класу, який переважає серед його найближчих «сусідів» у просторі ознак. Такий класифікатор **не будує моделі** — він щоразу переглядає всю навчальну вибірку. У цій лекції ми переходимо до методів, які **навчають явну модель** — набір правил, за якими об'єкт класифікують без звертання до вихідних даних. Почнемо з найпростішого можливого класифікатора — **одновимірного**, що приймає рішення за **одним** атрибутом (алгоритм **One Rule**). Він задає планку, з якою порівнюють складніші моделі, і водночас показує ключову ідею: атрибути **не рівноцінні** — один поділяє дані на класи краще за інший. Далі ми узагальнимо цю ідею до **дерев рішень** — ієрархії перевірок атрибутів — і розберемо три класичні алгоритми їх побудови: **ID3** (на основі **ентропії** та **приросту інформації**), **C4.5** (що виправляє зміщення ID3 через **коефіцієнт приросту**) і **CART** (на основі **індексу Джині** та **бінарних розбиттів**). Наступна [Лекція 8](DA-L08.md) продовжить тему ймовірнісним підходом — наївним баєсовим класифікатором. > **Практичний бік.** Ентропію, приріст інформації та індекс Джині ви > обчислюватимете «руками», а дерево рішень алгоритмом ID3 — **програмою** в > [Лабораторній роботі 7](../Laboratory/Laboratory7/main.md). Наскрізний приклад лекції — навчальна вибірка **«Спортивний канал»**: за трьома ознаками глядача (**стать**, **дохід**, чи він **студент**) треба передбачити, чи підписав він спортивний телеканал. | № | Стать | Дохід | Студент? | Спортивний канал? | |:--:|:--:|:--:|:--:|:--:| | 1 | Ч | Високий | Так | Так | | 2 | Ж | Середній | Ні | Ні | | 3 | Ч | Низький | Так | Ні | | 4 | Ж | Низький | Ні | Ні | | 5 | Ч | Середній | Ні | Так | | 6 | Ж | Високий | Ні | Так | | 7 | Ж | Середній | Так | Так | | 8 | Ч | Середній | Так | Так | | 9 | Ж | Низький | Так | Ні | | 10 | Ж | Середній | Ні | Ні | Клас-цільова ознака **«Спортивний канал?»** має два значення. У вибірці **5** об'єктів класу «Так» і **5** класу «Ні» — класи ідеально збалансовані. --- ## 7.1 Одновимірна класифікація **Класифікація** — це побудова правила, яке за значеннями **предикторів** (вхідних атрибутів) об'єкта передбачає значення **цільової** категоріальної ознаки (класу). Найпростіший різновид — коли правило спирається лише на **один** предиктор. > **Означення (одновимірна класифікація).** **Одновимірною** називають > класифікацію, у якій рішення про клас об'єкта приймають за значенням **одного** > атрибута (предиктора). Ідея здається наївною, але вона має практичну цінність. По-перше, одновимірна модель — **прозора**: правило легко прочитати й перевірити. По-друге, вона задає **базовий рівень якості** (англ. *baseline*): якщо складна багатовимірна модель не перевершує одновимірну, її ускладнення не виправдане. Питання лише в тому, **який саме** атрибут обрати — і як порівняти атрибути між собою за якістю поділу на класи. --- ## 7.2 Алгоритм One Rule (OneR) **One Rule** (скорочено **OneR**, «одне правило») — це алгоритм, що будує найкращу **одновимірну** модель: для кожного предиктора він формує правило «значення → найчастіший клас», оцінює його похибку й обирає предиктор із найменшою похибкою. > **Означення (правило OneR).** Для фіксованого предиктора $X$ правило має вигляд > $$ \text{if } X = x \ \text{ then } \ \text{клас} = c^{*}(x), $$ > де $c^{*}(x)$ — **найчастіший клас** серед об'єктів, у яких $X = x$. ### Кроки алгоритму ```text OneR(навчальна вибірка D, предиктори A, цільовий клас y): для кожного предиктора X із A: для кожного значення x предиктора X: 1. підрахувати, скільки разів трапляється кожен клас серед об'єктів з X = x 2. знайти найчастіший клас c*(x) для цього значення 3. сформувати правило if X = x then y = c*(x) 4. похибка(X) = число об'єктів, чий справжній клас != c*(x) (сума за всіма x) 5. обрати предиктор X* із найменшою сумарною похибкою повернути набір правил для X* ``` Сумарна похибка предиктора — це кількість об'єктів навчальної вибірки, яких правило класифікує **неправильно**. **Точність** правила — частка правильно класифікованих: $\text{ACC} = 1 - \dfrac{\text{похибка}}{n}$. ### Приклад 7.1 (OneR на вибірці «Спортивний канал») Побудуємо для кожного предиктора таблицю «значення → розподіл класів → найчастіший клас → похибка». | Предиктор | Значення | Так | Ні | Найчастіший клас | Похибка | |---|:--:|:--:|:--:|:--:|:--:| | **Стать** | Ч | 3 | 1 | Так | 1 | | | Ж | 2 | 4 | Ні | 2 | | **Дохід** | Високий | 2 | 0 | Так | 0 | | | Середній | 3 | 2 | Так | 2 | | | Низький | 0 | 3 | Ні | 0 | | **Студент?** | Так | 3 | 2 | Так | 2 | | | Ні | 2 | 3 | Ні | 2 | Сумарна похибка й точність кожного предиктора: - **Стать:** $1 + 2 = 3$ помилки $\Rightarrow \text{ACC} = 7/10 = \mathbf{70\%}$. - **Дохід:** $0 + 2 + 0 = 2$ помилки $\Rightarrow \text{ACC} = 8/10 = \mathbf{80\%}$. - **Студент?:** $2 + 2 = 4$ помилки $\Rightarrow \text{ACC} = 6/10 = \mathbf{60\%}$. Найменшу похибку дає **Дохід**, тож OneR обирає саме його. Правило-переможець (записане у вигляді $c^{*}(x)$ для кожного значення): $$ \text{Високий} \to \text{Так}, \quad \text{Середній} \to \text{Так}, \quad \text{Низький} \to \text{Ні}. $$ Оскільки два з трьох значень дають клас «Так», правило зручно згорнути в компактну форму: ```text if Дохід == Низький then Спортивний канал = Ні else Спортивний канал = Так ``` ![Стовпчаста діаграма точності правила OneR за трьома предикторами: Стать 70%, Дохід 80%, Студент 60%; предиктор Дохід — переможець](img/l07_oner.png) ### Матриця помилок правила OneR Щоб зрозуміти **характер** помилок, а не лише їх кількість, будують **матрицю помилок** (плутанини, англ. *confusion matrix*) — так само, як для kNN у [Лекції 6](DA-L06.md). Приймемо «Так» за **позитивний** клас. Прогони правило по всіх 10 об'єктах: воно передбачає «Ні» для трьох об'єктів із низьким доходом (рядки 3, 4, 9 — усі справді «Ні») і «Так» для решти семи (з них рядки 2 і 10 насправді «Ні»). | | | Справжній: Ні | Справжній: Так | Прогностична значущість | |---|:--:|:--:|:--:|---| | **Прогноз** | **Ні** | 3 (TN) | 0 (FN) | $\text{NPV} = 3/3 = 1.0$ | | | **Так** | 2 (FP) | 5 (TP) | $\text{PPV} = 5/7 \approx 0.71$ | | | | $\text{TNR} = 3/5 = 0.6$ | $\text{TPR} = 5/5 = 1.0$ | $\text{ACC} = 8/10 = 0.8$ | ![Матриця помилок правила OneR за атрибутом Дохід: TP=5, FP=2, FN=0, TN=3; загальна правильність ACC=0.8](img/l07_confusion.png) Розшифруємо чотири граничні показники (позначення з Лекції 6): - **NPV** (значущість негативного результату) $= \dfrac{TN}{TN+FN} = \dfrac{3}{3} = 1.0$: усі об'єкти, для яких правило сказало «Ні», справді «Ні». - **PPV** (значущість позитивного результату, точність) $= \dfrac{TP}{TP+FP} = \dfrac{5}{7} \approx 0.71$. - **Специфічність** (TNR) $= \dfrac{TN}{TN+FP} = \dfrac{3}{5} = 0.6$: частка справжніх «Ні», які правило впізнало. - **Чутливість** (TPR, повнота) $= \dfrac{TP}{TP+FN} = \dfrac{5}{5} = 1.0$: усіх справжніх «Так» правило вловило. Загальна **правильність** $\text{ACC} = \dfrac{TP+TN}{n} = \dfrac{5+3}{10} = 0.8$ — ті самі 80 %, що й похибка передбачила. Правило ідеально розпізнає підписників (TPR $=1$), але «перестраховується»: два несхильні глядачі помилково зараховані до підписників (FP $=2$). > **Типова помилка (OneR «любить» багатозначні атрибути).** Якщо атрибут має дуже > багато різних значень (у крайньому разі — унікальний ідентифікатор), кожне > значення трапляється рідко, і правило «запам'ятовує» вибірку майже без похибок — > але на **нових** даних працює погано (перенавчання). OneR тому зазвичай обмежують > атрибутами з небагатьма значеннями або штрафують надмірну дрібність. Ту саму > пастку багатозначності ми побачимо в ID3 (§7.6). --- ## 7.3 Дерева рішень: базові поняття Одне правило рідко дає високу точність. Природне узагальнення — **послідовність** перевірок: спершу перевіряємо один атрибут, потім, залежно від його значення, — наступний, і так далі. Така структура і є **деревом рішень**. > **Означення (дерево рішень).** **Дерево рішень** — це деревоподібна модель, у > якій кожен **внутрішній вузол** перевіряє значення одного атрибута, кожне > **ребро** відповідає результату перевірки, а кожен **лист** приписує клас. > Класифікація об'єкта — це шлях від кореня до листа, що визначається значеннями > атрибутів об'єкта. Дерево будують **згори вниз**, рекурсивно розбиваючи навчальну вибірку на дедалі «чистіші» підмножини. Ключове питання на кожному кроці — **за яким атрибутом розгалужувати** (цьому присвячено §7.5–7.7) і **коли зупинятися**, оголосивши вузол листом. > **Означення (умови утворення листа).** Вузол стає **листом**, якщо виконано хоча > б одну з умов: > - **а)** відповідна вузлу підмножина містить об'єкти лише **одного** класу > (вузол «чистий»); > - **б)** підмножина **порожня** (жодного об'єкта не потрапило в цю гілку); > - **в)** **вичерпані всі** доступні для розгалуження атрибути; > - **г)** досягнуто задану розробником **умову зупинки** (напр., мінімальна > кількість об'єктів у вузлі або максимальна глибина). У випадках **б)–г)**, коли підмножина неоднорідна, листу приписують **найпоширеніший клас** серед його об'єктів (для порожньої гілки — найпоширеніший клас батьківського вузла). --- ## 7.4 Загальний алгоритм побудови Позначимо навчальний набір $D(X, y)$, де $X$ — вектор атрибутів $x_0, x_1, \dots, x_m$, $y_i$ — категорія (клас) $i$-го об'єкта, а $A = \{0, 1, \dots, m\}$ — множина доступних атрибутів. Побудова дерева — це рекурсивна процедура `GenerateTree`. ```text GenerateTree(D, A): створити вузол Node якщо всі об'єкти D належать одній категорії c: Node <- лист із класом c; повернути Node якщо A порожня (m = 0): Node <- лист із найпоширенішою категорією в D; повернути Node обрати найкращий атрибут для розгалуження s (за критерієм §7.5–7.7) позначити Node атрибутом s для кожного можливого значення k атрибута s: Dk <- підмножина об'єктів D, у яких s = k якщо Dk порожня: приєднати до Node лист із найпоширенішим класом у D інакше: приєднати до Node гілку GenerateTree(Dk, A \ {s}) повернути Node ``` Зверніть увагу на рядок `A \ {s}`: в ID3 і C4.5 атрибут, за яким уже розгалужено, **вилучають** зі списку доступних (по кожній гілці він має одне й те саме значення, тож більше не інформативний). Уся змістовна частина захована у виборі «найкращого атрибута $s$» — саме тут різняться алгоритми ID3, C4.5 і CART. --- ## 7.5 ID3: ентропія та приріст інформації **ID3** (*Iterative Dichotomiser 3*) обирає атрибут, що дає найбільший **приріст інформації** — тобто найсильніше зменшує **невизначеність** класу. Міру невизначеності дає **ентропія**. > **Означення (ентропія).** **Ентропія** множини $D$ відносно класової ознаки — > це > $$ H(D) = -\sum_{c} p_c \log_2 p_c, $$ > де $p_c$ — частка об'єктів класу $c$ у $D$ (за домовленістю $0 \log_2 0 = 0$). Ентропію вимірюють у **бітах** (логарифм за основою 2). Для двох класів вона дорівнює $0$, коли множина **чиста** (усі об'єкти одного класу), і максимальна ($=1$ біт), коли класи **порівну**. Для наскрізної вибірки з $5$ «Так» і $5$ «Ні»: $$ H(D) = -\tfrac{5}{10}\log_2\tfrac{5}{10} - \tfrac{5}{10}\log_2\tfrac{5}{10} = -0.5(-1) - 0.5(-1) = 1.0 \ \text{біт}. $$ ![Крива бінарної ентропії H(p): дорівнює нулю для чистої множини та досягає максимуму 1 біт при p=0.5, коли два класи представлені порівну](img/l07_entropy_curve.png) Розбивши $D$ за атрибутом $A$ на підмножини $D_1, \dots, D_v$ (по одній на кожне значення), обчислюють **середньозважену ентропію** розбиття — ентропії частин, зважені їхніми розмірами: > **Означення (середньозважена ентропія розбиття).** > $$ H(D \mid A) = \sum_{k=1}^{v} \frac{|D_k|}{|D|}\, H(D_k). $$ Різниця між ентропією до й після розбиття — це **приріст інформації**: > **Означення (приріст інформації).** > $$ \mathrm{Gain}(D, A) = H(D) - H(D \mid A). $$ > ID3 на кожному кроці обирає атрибут із **найбільшим** приростом (рівносильно — > з **найменшою** середньозваженою ентропією). ### Приклад 7.2 (перше розбиття алгоритмом ID3) Обчислимо середньозважену ентропію для кожного з трьох атрибутів. Спершу — ентропії частин. Для наочності: якщо в частині $a$ об'єктів «Так» і $b$ — «Ні», $n = a+b$, то $H = -\tfrac{a}{n}\log_2\tfrac{a}{n} - \tfrac{b}{n}\log_2\tfrac{b}{n}$. **Стать** ($D$ ділиться на Ч і Ж): $$ H(\text{Ч}) = -\tfrac{3}{4}\log_2\tfrac{3}{4} - \tfrac{1}{4}\log_2\tfrac{1}{4} = 0.811, \qquad H(\text{Ж}) = -\tfrac{2}{6}\log_2\tfrac{2}{6} - \tfrac{4}{6}\log_2\tfrac{4}{6} = 0.918. $$ $$ H(D \mid \text{Стать}) = \tfrac{4}{10}(0.811) + \tfrac{6}{10}(0.918) = \mathbf{0.875}. $$ **Дохід** (Високий, Середній, Низький): $$ H(\text{Високий}) = 0 \ (\text{2 «Так», 0 «Ні» — чиста}), \quad H(\text{Низький}) = 0 \ (\text{0/3 — чиста}), $$ $$ H(\text{Середній}) = -\tfrac{3}{5}\log_2\tfrac{3}{5} - \tfrac{2}{5}\log_2\tfrac{2}{5} = 0.971, $$ $$ H(D \mid \text{Дохід}) = \tfrac{2}{10}(0) + \tfrac{5}{10}(0.971) + \tfrac{3}{10}(0) = \mathbf{0.485}. $$ **Студент?** (Так, Ні): $$ H(\text{Так}) = -\tfrac{3}{5}\log_2\tfrac{3}{5} - \tfrac{2}{5}\log_2\tfrac{2}{5} = 0.971, \quad H(\text{Ні}) = -\tfrac{2}{5}\log_2\tfrac{2}{5} - \tfrac{3}{5}\log_2\tfrac{3}{5} = 0.971, $$ $$ H(D \mid \text{Студент?}) = \tfrac{5}{10}(0.971) + \tfrac{5}{10}(0.971) = \mathbf{0.971}. $$ Зведемо результати ($H(D) = 1.0$): | Атрибут | Середньозважена ентропія | Приріст інформації | |---|:--:|:--:| | Стать | $0.875$ | $0.125$ | | **Дохід** | $\mathbf{0.485}$ | $\mathbf{0.515}$ | | Студент? | $0.971$ | $0.029$ | ![Середньозважена ентропія розбиття вибірки за кожним атрибутом: Стать 0.875, Дохід 0.485, Студент 0.971; найменша ентропія у Доходу, тож він стає коренем дерева](img/l07_split_root.png) Найменшу ентропію (найбільший приріст) дає **Дохід** — його й беруть **коренем** дерева. Це узгоджується з інтуїцією: дохід одразу «вирізає» два чистих листи (Високий $\to$ усі «Так», Низький $\to$ усі «Ні»), і лише значення «Середній» лишається змішаним. ![Розбиття 10 об'єктів за атрибутом Дохід у вигляді складених стовпців класів: Високий 2 «Так», Середній 3 «Так» та 2 «Ні», Низький 3 «Ні»; гілки Високий і Низький чисті, Середній змішана](img/l07_partition.png) ### Приклад 7.3 (добудова дерева) Після кореневого розбиття за доходом маємо: - **Високий** $\to$ підмножина $\{1, 6\}$, обидва «Так» $\Rightarrow$ **лист «Так»**; - **Низький** $\to$ підмножина $\{3, 4, 9\}$, усі «Ні» $\Rightarrow$ **лист «Ні»**; - **Середній** $\to$ підмножина $\{2, 5, 7, 8, 10\}$ (3 «Так», 2 «Ні», $H = 0.971$) — неоднорідна, рекурсуємо серед решти атрибутів $\{\text{Стать}, \text{Студент?}\}$. Для підмножини «Середній» обчислимо ентропії розбиттів: | Атрибут | Розбиття (Так/Ні) | Середньозважена ентропія | |---|---|:--:| | Стать | Ч: 2/0 ($H=0$); Ж: 1/2 ($H=0.918$) | $\tfrac{2}{5}(0) + \tfrac{3}{5}(0.918) = 0.551$ | | Студент? | Так: 2/0 ($H=0$); Ні: 1/2 ($H=0.918$) | $\tfrac{2}{5}(0) + \tfrac{3}{5}(0.918) = 0.551$ | Обидва атрибути дають однакову ентропію $0.551$ — це **нічия**; за домовленістю беремо перший, **Стать**. Тоді: - **Стать = Ч** $\to$ об'єкти $\{5, 8\}$, обидва «Так» $\Rightarrow$ **лист «Так»**; - **Стать = Ж** $\to$ об'єкти $\{2, 7, 10\}$ (1 «Так», 2 «Ні») — рекурсуємо за останнім атрибутом **Студент?**: Так $\to \{7\}$ («Так»), Ні $\to \{2, 10\}$ (обидва «Ні»). Обидві гілки чисті ($H = 0$). Дерево повністю **чисте** — воно безпомилково класифікує всю навчальну вибірку: ```text Дохід? ├── Високий -> Так ├── Низький -> Ні └── Середній -> Стать? ├── Ч -> Так └── Ж -> Студент? ├── Так -> Так └── Ні -> Ні ``` ![Дерево рішень ID3 для вибірки «Спортивний канал»: корінь Дохід; Високий веде до листа «Так», Низький — до листа «Ні», Середній — до вузла Стать (Ч дає «Так», Ж — вузол Студент?: Так дає «Так», Ні дає «Ні»)](img/l07_tree.png) > **Типова помилка (плутати основу логарифма).** Ентропію в теорії дерев рішень > рахують за основою **2** (результат у бітах). Якщо взяти натуральний логарифм > ($\ln$), усі значення масштабуються сталим множником $1/\ln 2 \approx 1.443$ — > **порядок** атрибутів за приростом не зміниться, але числа не збігатимуться зі > стандартними таблицями. Тримайтеся $\log_2$. --- ## 7.6 C4.5: коефіцієнт приросту (gain ratio) ID3 має вроджене **зміщення на користь багатозначних атрибутів**. Приклад 7.1 уже натякнув чому: атрибут із багатьма значеннями дробить вибірку на дрібні (часто чисті) частини, і його приріст інформації штучно завищений. У крайньому разі атрибут-ідентифікатор (унікальний для кожного об'єкта) дає $H(D \mid A) = 0$ і **максимальний** приріст — хоча для класифікації нових об'єктів він марний. **C4.5** (наступник ID3) виправляє це, нормуючи приріст на **власну інформацію розбиття** — ентропію самого поділу за розмірами частин, незалежно від класу. > **Означення (інформація розбиття).** **Власна інформація розбиття** (англ. > *split information*, *intrinsic value*) атрибута $A$ — > $$ \mathrm{SplitInfo}(D, A) = -\sum_{k=1}^{v} \frac{|D_k|}{|D|}\, \log_2 \frac{|D_k|}{|D|}. $$ > Вона тим більша, чим на **більше** й чим **рівномірніше** частин ділить атрибут. > **Означення (коефіцієнт приросту).** **Коефіцієнт приросту** (англ. *gain ratio*) — > $$ \mathrm{GainRatio}(D, A) = \frac{\mathrm{Gain}(D, A)}{\mathrm{SplitInfo}(D, A)}. $$ > C4.5 обирає атрибут із найбільшим коефіцієнтом приросту. Ділення на > $\mathrm{SplitInfo}$ **штрафує** атрибути з багатьма значеннями: їхня велика > власна інформація зменшує відношення. ### Приклад 7.4 (коефіцієнт приросту на кореневому кроці) Візьмемо прирости з Прикладу 7.2 і обчислимо власну інформацію кожного атрибута за розмірами частин. **Стать** (частини 4 і 6): $$ \mathrm{SplitInfo} = -\tfrac{4}{10}\log_2\tfrac{4}{10} - \tfrac{6}{10}\log_2\tfrac{6}{10} = 0.971. $$ **Дохід** (частини 2, 5 і 3): $$ \mathrm{SplitInfo} = -\tfrac{2}{10}\log_2\tfrac{2}{10} - \tfrac{5}{10}\log_2\tfrac{5}{10} - \tfrac{3}{10}\log_2\tfrac{3}{10} = 1.485. $$ **Студент?** (частини 5 і 5): $$ \mathrm{SplitInfo} = -\tfrac{5}{10}\log_2\tfrac{5}{10} - \tfrac{5}{10}\log_2\tfrac{5}{10} = 1.0. $$ | Атрибут | Приріст | Власна інформація | Коефіцієнт приросту | |---|:--:|:--:|:--:| | Стать | $0.125$ | $0.971$ | $0.128$ | | **Дохід** | $0.515$ | $1.485$ | $\mathbf{0.347}$ | | Студент? | $0.029$ | $1.000$ | $0.029$ | Дохід має найбільшу власну інформацію (бо ділить на три частини), тож його перевагу «пригальмовано» — але він усе одно перемагає з коефіцієнтом $0.347$. На цій вибірці ID3 і C4.5 дають те саме коренове рішення; різниця виявилася б, якби серед атрибутів був штучно дрібний (напр., «№ глядача»): ID3 обрав би його, а C4.5 — ні. > **Типова помилка (ділення на нуль у GainRatio).** Якщо атрибут має одне-єдине > значення на підмножині, $\mathrm{SplitInfo} = 0$ і коефіцієнт не визначений. > Практичні реалізації C4.5 такий атрибут просто відкидають (він і так не > розбиває даних) або розглядають лише атрибути з приростом не нижчим за середній. C4.5 має й інші вдосконалення порівняно з ID3: він працює з **числовими** атрибутами (шукаючи поріг розбиття), опрацьовує **пропущені** значення й виконує **відсікання гілок** (*pruning*) для боротьби з перенавчанням. --- ## 7.7 CART: індекс Джині та бінарні розбиття **CART** (*Classification and Regression Trees*) відрізняється від ID3/C4.5 двома рисами: по-перше, за міру неоднорідності бере **індекс Джині** замість ентропії; по-друге, будує **строго бінарне** дерево — кожен вузол розщеплює дані рівно на **дві** гілки. > **Означення (індекс Джині).** **Індекс Джині** множини $D$ — > $$ G(D) = 1 - \sum_{c} p_c^{2}, $$ > де $p_c$ — частка класу $c$. Він дорівнює $0$ для чистої множини й максимальний > ($=0.5$ для двох класів), коли класи порівну. Індекс Джині можна тлумачити як **ймовірність помилки** випадкового вгадування: якщо навмання приписати об'єкту клас із розподілу $D$, то $G(D)$ — ймовірність не вгадати. Для наскрізної вибірки: $$ G(D) = 1 - \left(\tfrac{5}{10}\right)^2 - \left(\tfrac{5}{10}\right)^2 = 1 - 0.25 - 0.25 = 0.5. $$ **Зважений індекс Джині** розбиття означують так само, як середньозважену ентропію: $$ G(D \mid A) = \sum_{k} \frac{|D_k|}{|D|}\, G(D_k), $$ і CART обирає розбиття з **найменшим** зваженим Джині. Оскільки дерево бінарне, для атрибута з $>2$ значеннями перебирають усі способи розділити значення на **дві групи**. ### Приклад 7.5 (кореневе розбиття алгоритмом CART) Обчислимо зважений індекс Джині для всіх можливих бінарних розбиттів. Для частини з $a$ «Так» і $b$ «Ні» ($n=a+b$): $G = 1 - (a/n)^2 - (b/n)^2$. **Стать** (єдине розбиття Ч | Ж): $$ G(\text{Ч}) = 1 - (\tfrac34)^2 - (\tfrac14)^2 = 0.375, \quad G(\text{Ж}) = 1 - (\tfrac26)^2 - (\tfrac46)^2 = 0.444, $$ $$ G(D \mid \text{Стать}) = \tfrac{4}{10}(0.375) + \tfrac{6}{10}(0.444) = 0.417. $$ **Дохід** (три бінарні варіанти, бо три значення): | Розбиття | Частина 1 (Так/Ні, Джині) | Частина 2 (Так/Ні, Джині) | Зважений Джині | |---|---|---|:--:| | {Високий} \| {Середній, Низький} | 2/0 · $0$ | 3/5 · $0.469$ | $0.375$ | | {Середній} \| {Високий, Низький} | 3/2 · $0.480$ | 2/3 · $0.480$ | $0.480$ | | **{Низький} \| {Високий, Середній}** | 0/3 · $0$ | 5/2 · $0.408$ | $\mathbf{0.286}$ | **Студент?** (розбиття Так | Ні): $G(\text{Так}) = G(\text{Ні}) = 0.480$, тож $G(D \mid \text{Студент?}) = 0.480$. Найменший зважений індекс Джині — $\mathbf{0.286}$ — дає розбиття доходу на **{Низький}** проти **{Високий, Середній}**. CART обирає саме його коренем: низькодохідні глядачі одразу утворюють чистий лист «Ні», а решта сімох об'єктів (5 «Так», 2 «Ні») ідуть у другу гілку для подальшого розщеплення. ![Зважений індекс Джині кандидатних кореневих бінарних розбиттів CART: найменше значення 0.286 дає розбиття Дохід {Низький} проти {Високий, Середній} — його обирають коренем](img/l07_gini_root.png) > **Зауваження (CART може повторно використовувати атрибут).** На відміну від > ID3/C4.5, бінарне розбиття «розділяє» лише **частину** значень атрибута. > Значення {Високий} і {Середній} у прикладі ще не розрізнені, тож дохід можна > **знову** взяти для розгалуження глибше в дереві. Тому в CART атрибути **не > вилучають** зі списку доступних. Ентропія й індекс Джині — близькі міри: обидві мінімальні для чистих вузлів і максимальні для рівномірних. На практиці вони майже завжди дають однакові дерева; Джині трохи дешевший обчислювально (без логарифмів), тому його часто беруть за замовчуванням. ![Накладені криві бінарної ентропії H(p) та індексу Джині G(p)=2p(1−p): обидві дорівнюють нулю для чистого вузла й максимальні при p=0.5 (ентропія 1 біт, Джині 0.5)](img/l07_gini_vs_entropy.png) --- ## Застосування в аналітиці даних - **Прозорі правила рішень.** Дерево рішень читається як набір умов «if–then» — його легко пояснити замовнику, аудитору чи лікарю. Це головна причина популярності дерев там, де рішення треба **обґрунтувати** (кредитний скоринг, медична діагностика). - **Базовий рівень (OneR).** Одновимірне правило — обов'язковий орієнтир: складну модель варто впроваджувати, лише якщо вона відчутно перевершує OneR. - **Відбір ознак.** Приріст інформації та індекс Джині ранжують атрибути за корисністю — це самостійний інструмент **вибору ознак** навіть поза деревами. - **Ансамблі.** Окреме дерево схильне до перенавчання; на практиці будують **ансамблі** дерев — випадкові ліси (*random forest*) та градієнтний бустинг, — що є одними з найточніших методів для табличних даних. - **Регресія.** Замінивши ентропію/Джині на дисперсію цільового числа, ті самі алгоритми (CART) будують **регресійні** дерева, що прогнозують число, а не клас. ## Підсумок - **Одновимірна класифікація** приймає рішення за одним атрибутом; **OneR** обирає атрибут із найменшою сумарною похибкою правил «значення → найчастіший клас». - На вибірці «Спортивний канал» OneR обрав **Дохід** із точністю **80 %**; матриця помилок дала NPV $=1.0$, PPV $\approx 0.71$, специфічність $0.6$, чутливість $1.0$, правильність $0.8$. - **Дерево рішень** — ієрархія перевірок атрибутів; вузол стає **листом**, коли він чистий, порожній, атрибути вичерпані або спрацювала умова зупинки. Будують його рекурсивно (`GenerateTree`). - **ID3** обирає атрибут за **приростом інформації** $\mathrm{Gain} = H(D) - H(D \mid A)$, де $H(D) = -\sum p_c \log_2 p_c$. Коренем вибірки став **Дохід** (ентропія $0.485$, приріст $0.515$); повне дерево безпомилкове. - **C4.5** нормує приріст на власну інформацію розбиття — **коефіцієнт приросту** $\mathrm{Gain}/\mathrm{SplitInfo}$ — і тим виправляє зміщення ID3 на користь багатозначних атрибутів (Дохід: коефіцієнт $0.347$). - **CART** використовує **індекс Джині** $G(D) = 1 - \sum p_c^2$ і **бінарні** розбиття; кореневим стало розбиття Дохід **{Низький} \| {Високий, Середній}** (зважений Джині $0.286$). ## Вправи ### Для розігріву 1. Обчисліть ентропію множини з розподілом класів $3$ «Так» та $1$ «Ні». Чому вона менша за $1$? За якого розподілу двох класів ентропія максимальна? 2. Для тієї самої множини ($3/1$) обчисліть індекс Джині. Порівняйте з ентропією: яка з мір більша, яка менша за $0.5$? 3. Сформулюйте всі чотири умови, за яких вузол дерева оголошують листом. Що приписують листу в неоднорідному випадку? ### Стандартні 4. У вибірці «Спортивний канал» перевірте вручну, що OneR за атрибутом **Стать** дає рівно $3$ помилки, а за **Студент?** — $4$. Побудуйте матрицю помилок для правила за атрибутом Стать (позитивний клас — «Так»). 5. Для підмножини «Середній» ($\{2,5,7,8,10\}$) обчисліть приріст інформації атрибутів **Стать** і **Студент?** і переконайтесь, що вони рівні. Поясніть, чому виникла нічия, і як алгоритм її розв'язує. 6. Обчисліть зважений індекс Джині розбиття атрибута **Студент?** на всій вибірці й порівняйте його з розбиттям Дохід **{Низький} \| {решта}**. Який з них CART віддасть перевагу й чому? ### Підвищеної складності 7. Доведіть, що для двох класів ентропія $H(p) = -p\log_2 p - (1-p)\log_2(1-p)$ максимальна при $p = 1/2$ і дорівнює там $1$. *(Підказка: прирівняйте похідну до нуля.)* 8. Покажіть на прикладі штучного атрибута-ідентифікатора (унікальне значення для кожного з $10$ об'єктів), що його приріст інформації дорівнює $H(D)$ (максимальний), тоді як коефіцієнт приросту C4.5 малий. Обчисліть $\mathrm{SplitInfo}$ такого атрибута й поясніть, чому C4.5 його відкине. 9. Побудуйте повне дерево CART для вибірки «Спортивний канал», продовживши Приклад 7.5 (розщеплюйте гілку {Високий, Середній} далі за індексом Джині). Порівняйте отримане дерево з деревом ID3 з Прикладу 7.3: чи однакові вони? Чому CART може повторно використати атрибут «Дохід»?