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

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

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

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

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

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

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

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

• Стать: $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 обирає його. Правило:

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

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

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

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

Відповідь: найкращий предиктор — Дохід (точність $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.$$

Зведемо:

Відповідь: $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$. Розбиття:

Обидва атрибути дають ентропію $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$ лист «Ні».

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

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

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

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

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

Laboratory/Laboratory7/3classroom.md · 10.8 KB · updated 2026-08-05 09:28