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

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

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 Демонстраційний приклад (на інших даних, ніж у задачах) #

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

Класи збалансовані: $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.

Похибка Небо $= 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$ «Ні». Обидві гілки чисті.

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

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

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

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

Laboratory/Laboratory7/2method.md · 9.7 KB · updated 2026-08-04 23:32