Лекція 7. Ординарні методи класифікації. Дерева рішень #

Огляд #

У Лекції 6 ми розв’язали задачу класифікації методом $k$ найближчих сусідів: об’єкт відносили до того класу, який переважає серед його найближчих «сусідів» у просторі ознак. Такий класифікатор не будує моделі — він щоразу переглядає всю навчальну вибірку. У цій лекції ми переходимо до методів, які навчають явну модель — набір правил, за якими об’єкт класифікують без звертання до вихідних даних.

Почнемо з найпростішого можливого класифікатора — одновимірного, що приймає рішення за одним атрибутом (алгоритм One Rule). Він задає планку, з якою порівнюють складніші моделі, і водночас показує ключову ідею: атрибути не рівноцінні — один поділяє дані на класи краще за інший. Далі ми узагальнимо цю ідею до дерев рішень — ієрархії перевірок атрибутів — і розберемо три класичні алгоритми їх побудови: ID3 (на основі ентропії та приросту інформації), C4.5 (що виправляє зміщення ID3 через коефіцієнт приросту) і CART (на основі індексу Джині та бінарних розбиттів). Наступна Лекція 8 продовжить тему ймовірнісним підходом — наївним баєсовим класифікатором.

Практичний бік. Ентропію, приріст інформації та індекс Джині ви обчислюватимете «руками», а дерево рішень алгоритмом ID3 — програмою в Лабораторній роботі 7.

Наскрізний приклад лекції — навчальна вибірка «Спортивний канал»: за трьома ознаками глядача (стать, дохід, чи він студент) треба передбачити, чи підписав він спортивний телеканал.

Клас-цільова ознака «Спортивний канал?» має два значення. У вибірці 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$.

Кроки алгоритму #

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 на вибірці «Спортивний канал») #

Побудуємо для кожного предиктора таблицю «значення → розподіл класів → найчастіший клас → похибка».

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

• Стать: $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{Ні}.$$

Оскільки два з трьох значень дають клас «Так», правило зручно згорнути в компактну форму:

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

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

Щоб зрозуміти характер помилок, а не лише їх кількість, будують матрицю помилок (плутанини, англ. confusion matrix) — так само, як для kNN у Лекції 6. Приймемо «Так» за позитивний клас. Прогони правило по всіх 10 об’єктах: воно передбачає «Ні» для трьох об’єктів із низьким доходом (рядки 3, 4, 9 — усі справді «Ні») і «Так» для решти семи (з них рядки 2 і 10 насправді «Ні»).

Розшифруємо чотири граничні показники (позначення з Лекції 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.

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{біт}.$$

Розбивши $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$):

Найменшу ентропію (найбільший приріст) дає Дохід — його й беруть коренем дерева. Це узгоджується з інтуїцією: дохід одразу «вирізає» два чистих листи (Високий $\to$ усі «Так», Низький $\to$ усі «Ні»), і лише значення «Середній» лишається змішаним.

Приклад 7.3 (добудова дерева) #

Після кореневого розбиття за доходом маємо:

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

Для підмножини «Середній» обчислимо ентропії розбиттів:

Обидва атрибути дають однакову ентропію $0.551$ — це нічия; за домовленістю беремо перший, Стать. Тоді:

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

Дерево повністю чисте — воно безпомилково класифікує всю навчальну вибірку:

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

Типова помилка (плутати основу логарифма). Ентропію в теорії дерев рішень рахують за основою 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.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.$$

Дохід (три бінарні варіанти, бо три значення):

Студент? (розбиття Так | Ні): $G(\text{Так}) = G(\text{Ні}) = 0.480$, тож $G(D \mid \text{Студент?}) = 0.480$.

Найменший зважений індекс Джині — $\mathbf{0.286}$ — дає розбиття доходу на {Низький} проти {Високий, Середній}. CART обирає саме його коренем: низькодохідні глядачі одразу утворюють чистий лист «Ні», а решта сімох об’єктів (5 «Так», 2 «Ні») ідуть у другу гілку для подальшого розщеплення.

Зауваження (CART може повторно використовувати атрибут). На відміну від ID3/C4.5, бінарне розбиття «розділяє» лише частину значень атрибута. Значення {Високий} і {Середній} у прикладі ще не розрізнені, тож дохід можна знову взяти для розгалуження глибше в дереві. Тому в CART атрибути не вилучають зі списку доступних.

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

Застосування в аналітиці даних #

• Прозорі правила рішень. Дерево рішень читається як набір умов «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 може повторно використати атрибут «Дохід»?

Lectures/DA-L07.md · 41.8 KB · updated 2026-08-05 09:27