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

Цей розділ **самодостатній**: у ньому зібрано теорію одновимірної класифікації
(One Rule) та дерев рішень (ID3, C4.5, CART), потрібну для аудиторних задач
([3classroom.md](3classroom.md)) і домашньої програми ([4task.md](4task.md)).
Ширше ту саму теорію викладено в [Лекції 7](../../Lectures/DA-L07.md).

## 2.1 Задача класифікації

**Класифікація** — побудова правила, що за значеннями **предикторів** (вхідних
атрибутів) об'єкта передбачає його **клас** (категоріальну цільову ознаку).
Правило навчають на **навчальній вибірці** — таблиці, де кожен рядок є об'єктом,
стовпці-атрибути відомі, і відомий справжній клас.

## 2.2 One Rule (одновимірне правило)

**One Rule** (OneR) будує найкраще правило за **одним** атрибутом. Для кожного
предиктора $X$ і кожного його значення $x$ визначають **найчастіший клас**
$c^{*}(x)$ серед об'єктів із $X = x$; правило має вигляд

$$ \text{if } X = x \ \text{ then } \ \text{клас} = c^{*}(x). $$

**Сумарна похибка** предиктора — кількість об'єктів вибірки, чий справжній клас
відрізняється від передбаченого. Обирають предиктор із **найменшою** похибкою.
**Точність** правила: $\text{ACC} = 1 - \dfrac{\text{похибка}}{n}$.

### Матриця помилок

Якість класифікатора описує **матриця помилок** (плутанини). Для двох класів
(позитивний / негативний) вона містить чотири числа: **TP** (правильно
передбачені позитивні), **TN** (правильно передбачені негативні), **FP**
(негативні, помилково названі позитивними) і **FN** (позитивні, пропущені).
Основні показники:

$$ \text{TPR (чутливість)} = \frac{TP}{TP+FN}, \qquad \text{TNR (специфічність)} = \frac{TN}{TN+FP}, $$
$$ \text{PPV} = \frac{TP}{TP+FP}, \qquad \text{NPV} = \frac{TN}{TN+FN}, \qquad \text{ACC} = \frac{TP+TN}{n}. $$

## 2.3 Дерево рішень і критерії неоднорідності

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

### Ентропія

**Ентропія** множини $D$ (у бітах) вимірює неоднорідність класів:

$$ H(D) = -\sum_{c} p_c \log_2 p_c, \qquad 0 \log_2 0 := 0, $$

де $p_c$ — частка класу $c$. Для двох класів $H = 0$ на чистій множині й $H = 1$
за рівних класів.

### Середньозважена ентропія та приріст інформації (ID3)

Розбивши $D$ за атрибутом $A$ на частини $D_1, \dots, D_v$ (по одній на значення):

$$ H(D \mid A) = \sum_{k=1}^{v} \frac{|D_k|}{|D|}\, H(D_k), \qquad
\mathrm{Gain}(D, A) = H(D) - H(D \mid A). $$

**ID3** обирає атрибут із **найбільшим** приростом (найменшою зваженою ентропією).

### Коефіцієнт приросту (C4.5)

ID3 зміщений на користь **багатозначних** атрибутів. **C4.5** нормує приріст на
**власну інформацію розбиття**:

$$ \mathrm{SplitInfo}(D, A) = -\sum_{k=1}^{v} \frac{|D_k|}{|D|}\, \log_2 \frac{|D_k|}{|D|}, \qquad
\mathrm{GainRatio}(D, A) = \frac{\mathrm{Gain}(D, A)}{\mathrm{SplitInfo}(D, A)}. $$

### Індекс Джині та бінарні розбиття (CART)

**CART** використовує **індекс Джині** й будує **бінарні** дерева:

$$ G(D) = 1 - \sum_{c} p_c^{2}, \qquad G(D \mid A) = \sum_{k} \frac{|D_k|}{|D|}\, G(D_k). $$

Для атрибута з $>2$ значеннями перебирають усі поділи значень на **дві** групи й
беруть розбиття з найменшим зваженим Джині.

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

Розглянемо навчальну вибірку **«Пікнік»**: за станом **неба** та силою **вітру**
передбачаємо, чи відбудеться пікнік.

| № | Небо | Вітер | Пікнік? |
|:--:|:--:|:--:|:--:|
| 1 | Ясно | Слабкий | Так |
| 2 | Ясно | Сильний | Так |
| 3 | Хмарно | Слабкий | Так |
| 4 | Хмарно | Сильний | Ні |
| 5 | Дощ | Слабкий | Ні |
| 6 | Дощ | Сильний | Ні |

Класи збалансовані: $3$ «Так», $3$ «Ні», тож
$H(D) = -\tfrac12\log_2\tfrac12 - \tfrac12\log_2\tfrac12 = 1.0$ і
$G(D) = 1 - (\tfrac12)^2 - (\tfrac12)^2 = 0.5$.

**(а) One Rule.**

| Предиктор | Значення | Так | Ні | $c^{*}$ | Похибка |
|---|:--:|:--:|:--:|:--:|:--:|
| Небо | Ясно | 2 | 0 | Так | 0 |
| | Хмарно | 1 | 1 | Так | 1 |
| | Дощ | 0 | 2 | Ні | 0 |
| Вітер | Слабкий | 2 | 1 | Так | 1 |
| | Сильний | 1 | 2 | Ні | 1 |

Похибка **Небо** $= 1$ ($\text{ACC} = 5/6 \approx 83.3\%$); похибка **Вітер**
$= 2$ ($\text{ACC} = 4/6 \approx 66.7\%$). OneR обирає **Небо**.

**(б) ID3 — приріст інформації.** Ентропії частин:

$$ H(\text{Ясно}) = 0, \quad H(\text{Дощ}) = 0, \quad
H(\text{Хмарно}) = -\tfrac12\log_2\tfrac12 - \tfrac12\log_2\tfrac12 = 1.0, $$
$$ H(D \mid \text{Небо}) = \tfrac{2}{6}(0) + \tfrac{2}{6}(1) + \tfrac{2}{6}(0) = 0.333, \quad \mathrm{Gain} = 1 - 0.333 = 0.667. $$

Для вітру обидві частини мають розподіл $2/1$ і $1/2$:

$$ H(\text{Слабкий}) = H(\text{Сильний}) = -\tfrac23\log_2\tfrac23 - \tfrac13\log_2\tfrac13 = 0.918, $$
$$ H(D \mid \text{Вітер}) = 0.918, \quad \mathrm{Gain} = 1 - 0.918 = 0.082. $$

Приріст **Небо** ($0.667$) набагато більший — його беруть **коренем**.

**(в) CART — індекс Джині.**

$$ G(D \mid \text{Небо}) = \tfrac{2}{6}(0) + \tfrac{2}{6}(0.5) + \tfrac{2}{6}(0) = 0.167, \qquad
G(D \mid \text{Вітер}) = \tfrac{2}{3}\cdot\ldots = 0.444. $$

(для вітру $G(\text{Слабкий}) = G(\text{Сильний}) = 1 - (\tfrac23)^2 - (\tfrac13)^2 = 0.444$.)
Знову перемагає **Небо** ($0.167 < 0.444$) — усі три критерії узгоджені.

**(г) Добудова дерева.** За коренем «Небо»:

- **Ясно** $\to$ $\{1, 2\}$, обидва «Так» $\Rightarrow$ **лист «Так»**;
- **Дощ** $\to$ $\{5, 6\}$, обидва «Ні» $\Rightarrow$ **лист «Ні»**;
- **Хмарно** $\to$ $\{3, 4\}$ (1 «Так», 1 «Ні») — рекурсуємо за останнім атрибутом
  **Вітер**: Слабкий $\to$ «Так», Сильний $\to$ «Ні». Обидві гілки чисті.

```text
Небо?
├── Ясно   -> Так
├── Дощ    -> Ні
└── Хмарно -> Вітер?
              ├── Слабкий -> Так
              └── Сильний -> Ні
```

Дерево безпомилково класифікує всю вибірку.

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

- Спершу обчисліть **ентропію всієї множини** $H(D)$ — це орієнтир, від якого
  відлічують приріст.
- Для кожного атрибута порахуйте ентропію **кожної** частини, потім
  **середньозважену** (не забудьте ваги $|D_k|/|D|$).
- Атрибут для розгалуження — з **найбільшим приростом** (ID3) або **найменшим**
  зваженим Джині (CART). За нічиєї — беріть будь-який (напр., перший за списком).
- Пам'ятайте $0\log_2 0 = 0$: чиста частина дає нульову ентропію, а не помилку.
- Рекурсію зупиняйте, коли підмножина **чиста**, **порожня** або **атрибути
  вичерпані**; у двох останніх випадках лист отримує найпоширеніший клас.