# 3. Аудиторні задачі з розв'язаннями

Ці задачі розбирають **в аудиторії «руками»**. Вони показують ті самі обчислення,
що їх потім автоматизує домашня програма ([4task.md](4task.md)). Теорія й формули —
у [методичних вказівках](2method.md).

Усі три задачі спираються на спільну навчальну вибірку **«Спортивний канал»** (за
ознаками глядача передбачаємо, чи підписав він спортивний телеканал):

| № | Стать | Дохід | Студент? | Спортивний канал? |
|:--:|:--:|:--:|:--:|:--:|
| 1 | Ч | Високий | Так | Так |
| 2 | Ж | Середній | Ні | Ні |
| 3 | Ч | Низький | Так | Ні |
| 4 | Ж | Низький | Ні | Ні |
| 5 | Ч | Середній | Ні | Так |
| 6 | Ж | Високий | Ні | Так |
| 7 | Ж | Середній | Так | Так |
| 8 | Ч | Середній | Так | Так |
| 9 | Ж | Низький | Так | Ні |
| 10 | Ж | Середній | Ні | Ні |

Клас-цільова ознака має $5$ «Так» і $5$ «Ні» ($n = 10$).

## Задача 1. One Rule: найкращий предиктор і матриця помилок

**Дано** вибірку «Спортивний канал». **Знайти** точність правила OneR за кожним із
трьох предикторів, обрати найкращий, записати правило й побудувати його матрицю
помилок (позитивний клас — «Так»).

**Розв'язання.** Для кожного предиктора підрахуємо розподіл класів за значеннями,
знайдемо найчастіший клас $c^{*}$ і похибку.

| Предиктор | Значення | Так | Ні | $c^{*}$ | Похибка |
|---|:--:|:--:|:--:|:--:|:--:|
| **Стать** | Ч | 3 | 1 | Так | 1 |
| | Ж | 2 | 4 | Ні | 2 |
| **Дохід** | Високий | 2 | 0 | Так | 0 |
| | Середній | 3 | 2 | Так | 2 |
| | Низький | 0 | 3 | Ні | 0 |
| **Студент?** | Так | 3 | 2 | Так | 2 |
| | Ні | 2 | 3 | Ні | 2 |

Сумарна похибка й точність:

- **Стать:** $1 + 2 = 3$ помилки, $\text{ACC} = 7/10 = 70\%$;
- **Дохід:** $0 + 2 + 0 = 2$ помилки, $\text{ACC} = 8/10 = 80\%$;
- **Студент?:** $2 + 2 = 4$ помилки, $\text{ACC} = 6/10 = 60\%$.

![Точність правила OneR за предикторами вибірки «Спортивний канал»: Стать 70%, Дохід 80%, Студент 60%; переможець — Дохід](img/lab7_oner.png)

Найменша похибка — у **Доходу**, тож OneR обирає його. Правило:

$$ \text{Високий} \to \text{Так}, \quad \text{Середній} \to \text{Так}, \quad \text{Низький} \to \text{Ні}, $$

або компактно:

```text
if Дохід == Низький then Спортивний канал = Ні
                     else Спортивний канал = Так
```

**Матриця помилок.** Прогони правило по 10 об'єктах: «Ні» передбачено для рядків
$3, 4, 9$ (усі справді «Ні»), «Так» — для решти семи (з них рядки $2$ і $10$
насправді «Ні»). Отже $TP = 5$, $TN = 3$, $FP = 2$, $FN = 0$:

| | | Справжній: Ні | Справжній: Так | |
|---|:--:|:--:|:--:|---|
| **Прогноз** | **Ні** | 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$ |

**Відповідь:** найкращий предиктор — **Дохід** (точність $80\%$); правило
«Низький $\to$ Ні, інакше Так». Матриця помилок: чутливість $\text{TPR} = 1.0$
(усіх підписників впіймано), специфічність $\text{TNR} = 0.6$, $\text{NPV} = 1.0$,
$\text{PPV} \approx 0.71$, правильність $\text{ACC} = 0.8$.

## Задача 2. ID3: ентропія та вибір кореня

**Дано** ту саму вибірку. **Знайти** ентропію всієї множини $H(D)$, середньозважену
ентропію розбиття за кожним атрибутом і приріст інформації; обрати корінь дерева.

**Розв'язання.** Уся множина: $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{біт}. $$

**Стать.** Ч: $3$ «Так», $1$ «Ні»; Ж: $2$ «Так», $4$ «Ні».

$$ H(\text{Ч}) = -\tfrac34\log_2\tfrac34 - \tfrac14\log_2\tfrac14 = 0.811, \qquad
H(\text{Ж}) = -\tfrac26\log_2\tfrac26 - \tfrac46\log_2\tfrac46 = 0.918, $$
$$ H(D \mid \text{Стать}) = \tfrac{4}{10}(0.811) + \tfrac{6}{10}(0.918) = 0.875, \quad \mathrm{Gain} = 1 - 0.875 = 0.125. $$

**Дохід.** Високий: $2/0$; Середній: $3/2$; Низький: $0/3$.

$$ H(\text{Високий}) = 0, \quad H(\text{Низький}) = 0, \quad
H(\text{Середній}) = -\tfrac35\log_2\tfrac35 - \tfrac25\log_2\tfrac25 = 0.971, $$
$$ H(D \mid \text{Дохід}) = \tfrac{2}{10}(0) + \tfrac{5}{10}(0.971) + \tfrac{3}{10}(0) = 0.485, \quad \mathrm{Gain} = 1 - 0.485 = 0.515. $$

**Студент?** Так: $3/2$; Ні: $2/3$.

$$ H(\text{Так}) = H(\text{Ні}) = 0.971, \qquad
H(D \mid \text{Студент?}) = \tfrac{5}{10}(0.971) + \tfrac{5}{10}(0.971) = 0.971, \quad \mathrm{Gain} = 0.029. $$

Зведемо:

| Атрибут | Середньозважена ентропія | Приріст |
|---|:--:|:--:|
| Стать | $0.875$ | $0.125$ |
| **Дохід** | $\mathbf{0.485}$ | $\mathbf{0.515}$ |
| Студент? | $0.971$ | $0.029$ |

![Середньозважена ентропія кореневого розбиття за атрибутами: Стать 0.875, Дохід 0.485, Студент 0.971; мінімум у Доходу визначає корінь дерева](img/lab7_split_root.png)

**Відповідь:** $H(D) = 1.0$; найбільший приріст (найменша ентропія) — у
**Доходу**, тож коренем дерева стає атрибут **Дохід**.

## Задача 3. ID3: добудова дерева на підмножині «Середній»

**Дано** результат Задачі 2 (корінь — Дохід). **Завершити** побудову дерева,
рекурсуючи по гілках.

**Розв'язання.** Розіб'ємо вибірку за доходом:

- **Високий** $\to$ об'єкти $\{1, 6\}$ — обидва «Так» $\Rightarrow$ **лист «Так»**
  (чистий вузол);
- **Низький** $\to$ об'єкти $\{3, 4, 9\}$ — усі «Ні» $\Rightarrow$ **лист «Ні»**;
- **Середній** $\to$ об'єкти $\{2, 5, 7, 8, 10\}$ ($3$ «Так», $2$ «Ні») —
  неоднорідні, рекурсуємо серед решти атрибутів $\{\text{Стать}, \text{Студент?}\}$.

Ентропія підмножини «Середній»:
$H = -\tfrac35\log_2\tfrac35 - \tfrac25\log_2\tfrac25 = 0.971$. Розбиття:

| Атрибут | Розбиття (Так/Ні) | Середньозважена ентропія |
|---|---|:--:|
| Стать | Ч: 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$ (приріст $0.971 - 0.551 = 0.420$) —
**нічия**. За домовленістю беремо перший, **Стать**:

- **Стать = Ч** $\to$ об'єкти $\{5, 8\}$ — обидва «Так» $\Rightarrow$ **лист «Так»**;
- **Стать = Ж** $\to$ об'єкти $\{2, 7, 10\}$ ($1$ «Так», $2$ «Ні») — рекурсуємо за
  останнім атрибутом **Студент?**:
  - Студент? = Так $\to$ $\{7\}$ — «Так» $\Rightarrow$ **лист «Так»**;
  - Студент? = Ні $\to$ $\{2, 10\}$ — обидва «Ні» $\Rightarrow$ **лист «Ні»**.

Усі гілки завершилися чистими листами. Повне дерево:

```text
Дохід?
├── Високий  -> Так
├── Низький  -> Ні
└── Середній -> Стать?
                ├── Ч -> Так
                └── Ж -> Студент?
                         ├── Так -> Так
                         └── Ні  -> Ні
```

![Дерево рішень ID3 для вибірки «Спортивний канал» з коренем Дохід; гілка Середній розгалужується за Статтю, далі гілка Ж — за атрибутом Студент?](img/lab7_tree.png)

**Перевірка.** Прогнавши всі $10$ об'єктів деревом, дістаємо їхні справжні класи —
дерево класифікує навчальну вибірку **безпомилково** (ентропія всіх листів $= 0$).

**Відповідь:** дерево має корінь **Дохід**; гілки «Високий» і «Низький» одразу
дають листи «Так» і «Ні», а гілка «Середній» розгалужується за **Статтю**, після
чого гілка «Ж» — за **Студент?**. Дерево чисте.

> **Зв'язок із домашнім завданням.** Саме ці кроки — обчислити ентропію, для
> кожного атрибута знайти середньозважену ентропію, обрати атрибут із найбільшим
> приростом і рекурсивно повторити на підмножинах — виконуватиме ваша програма
> ID3 ([4task.md](4task.md)). Вибірка «Спортивний канал» — зручний **тест**:
> подайте її на вхід і переконайтесь, що програма будує саме це дерево з коренем
> «Дохід».