Розуміння шляхом впровадження: дерево рішень

Зображення автора

Багато просунутих моделей машинного навчання, таких як випадкові ліси або алгоритми посилення градієнта, такі як XGBoost, CatBoost або LightGBM (і навіть автокодери!) покладаються на важливий загальний інгредієнт: дерево рішень!

Не розуміючи дерева рішень, неможливо зрозуміти жодного з вищезгаданих передових алгоритмів пакетування або посилення градієнта, що є ганьбою для будь-якого дослідника даних! Отже, давайте демістифікуємо внутрішню роботу дерева рішень, реалізувавши його в Python.

З цієї статті ви дізнаєтеся

• чому і як дерево рішень розділяє дані,
• отримання інформації та
• як реалізувати дерева рішень у Python за допомогою NumPy.

Ви можете знайти код на мій Github.

Щоб робити прогнози, дерева рішень спираються на Розщеплення набір даних на менші частини рекурсивним способом.

Зображення автора

На малюнку вище ви можете побачити один із прикладів поділу — вихідний набір даних розділяється на дві частини. На наступному кроці обидві ці частини знову розділяють і так далі. Це продовжується, доки не буде виконано якийсь критерій зупинки, наприклад,

• якщо в результаті розбиття частина буде порожньою
• якщо була досягнута певна глибина рекурсії
• якщо (після попередніх поділів) набір даних складається лише з кількох елементів, що робить подальші поділи непотрібними.

Як знайти ці поділки? І чому це нас хвилює? Давай дізнаємось.

мотивація

Припустимо, що ми хочемо вирішити a двійковий проблема класифікації які ми зараз створюємо самі:

import numpy as np
np.random.seed(0) X = np.random.randn(100, 2) # features
y = ((X[:, 0] > 0) * (X[:, 1] < 0)) # labels (0 and 1)

Двовимірні дані виглядають так:

Зображення автора

Ми бачимо, що існує два різних класи — фіолетовий приблизно в 75% випадків і жовтий приблизно в 25% випадків. Якщо ви подасте ці дані в дерево рішень класифікатор, це дерево спочатку має такі думки:

«Є два різних етикетки, що для мене занадто безладно. Я хочу розчистити цей безлад, розділивши дані на дві частини — ці частини мають бути чистішими, ніж повні дані раніше». — дерево, що опритомніло

Так і робить дерево.

Зображення автора

Дерево вирішує зробити розкол приблизно вздовж x-вісь. Це призводить до того, що верхня частина даних тепер ідеальна чистий, означає, що ви тільки знаходите єдиний клас (у цьому випадку фіолетовий) там.

Проте нижня частина залишилася брудний, у певному сенсі навіть безладніше, ніж раніше. Співвідношення класів раніше було приблизно 75:25 у повному наборі даних, але в цій меншій частині воно становить приблизно 50:50, що є найбільшою плутаниною

 Примітка: Тут неважливо, що фіолетовий і жовтий гарно розділені на малюнку. Просто необхідна кількість різних міток у двох частинах кол.

Зображення автора

Тим не менш, це достатньо добре як перший крок для дерева, і тому воно продовжується. Хоча це не призведе до ще одного розколу верхівки, очистити більше, він може створити ще один розкол у нижній частині, щоб очистити її.

Зображення автора

І вуаля, кожна з трьох окремих частин абсолютно чиста, оскільки ми знаходимо лише один колір (етикетку) на частину.

Зараз дуже легко робити прогнози: якщо надходить нова точка даних, ви просто перевіряєте, яка з них три частини воно лежить і надати йому відповідного кольору. Зараз це так добре працює, тому що кожна частина є очистити. Легко, правда?

Зображення автора

Гаразд, ми говорили про очистити та  брудний дані, але поки що ці слова представляють лише деяку розпливчасту ідею. Щоб реалізувати щось, ми повинні знайти спосіб визначення чистота.

Заходи щодо чистоти

Припустімо, що у нас є, наприклад, деякі мітки

y_1 = [0, 0, 0, 0, 0, 0, 0, 0] y_2 = [1, 0, 0, 0, 0, 0, 1, 0]
y_3 = [1, 0, 1, 1, 0, 0, 1, 0]

Інтуїтивно зрозуміло, y₁ це найчистіший набір міток, за яким іде y₂ , А потім y₃. Поки що все добре, але як ми можемо підрахувати таку поведінку? Мабуть, найпростішим, що спадає на думку, є наступне:

Просто порахуйте кількість нулів і кількість одиниць. Обчисліть їх абсолютну різницю. Щоб зробити його кращим, нормалізуйте його, розділивши довжину масивів.

Наприклад, y₂ Всього 8 записів — 6 нулів і 2 одиниці. Отже, наш індивідуальний оцінка чистоти буде |6 – 2| / 8 = 0.5. Неважко підрахувати, що чистота набирає балів y₁ та  y₃ 1.0 і 0.0 відповідно. Тут ми бачимо загальну формулу:

Зображення автора

Тут, n₀ та  n₁ – числа нулів і одиниць відповідно, n = n₀ + n₁ довжина масиву і p₁ = n₁ / n це частка 1 міток.

Проблема цієї формули в тому, що вона є спеціально розроблений для двох класів, але дуже часто нас цікавить багатокласова класифікація. Однією з формул, яка працює досить добре, є Міра домішки Джіні:

Зображення автора

або загальний випадок:

Зображення автора

Це працює настільки добре, що scikit-learn прийняв його як стандартний захід для його DecisionTreeClassifier клас.

Зображення автора

 Примітка: Джині вимірює безладдя замість чистоти. Приклад: якщо список містить лише один клас (=дуже чисті дані!), тоді всі члени в сумі дорівнюють нулю, отже, сума дорівнює нулю. Найгірший випадок, якщо всі класи з’являються точну кількість разів, у цьому випадку Джині дорівнює 1–1/C де C – кількість класів.

Тепер, коли у нас є міра чистоти/безладдя, давайте подивимося, як її можна використати для пошуку хороших розбивок.

Пошук розколів

Ми вибираємо з багатьох варіантів поділу, але який із них кращий? Давайте знову використаємо наш початковий набір даних разом із мірою домішки Джіні.

Зображення автора

Не будемо зараз рахувати бали, але припустимо, що 75% фіолетових і 25% жовтих. Використовуючи визначення Джіні, домішка повного набору даних є

Зображення автора

Якщо ми розділимо набір даних уздовж x-вісь, як це було зроблено раніше:

Зображення автора

Команда верхня частина має домішку Джіні 0.0 і нижню частину

Зображення автора

У середньому дві частини мають домішку Джіні (0.0 + 0.5) / 2 = 0.25, що краще, ніж 0.375 для всього набору даних раніше. Ми також можемо виразити це в термінах т. зв отримання інформації:

Інформаційний приріст цього розщеплення становить 0.375 – 0.25 = 0.125.

Легко як це. Чим вищий інформаційний приріст (тобто чим менша домішка Джіні), тим краще.

Примітка: Інший не менш хороший початковий розподіл буде вздовж осі y.

Важливо пам’ятати, що це корисно для зважте домішки Джіні деталей за розміром частин. Наприклад, припустимо, що

• частина 1 складається з 50 точок даних і має домішку Джіні 0.0 і
• частина 2 складається з 450 точок даних і має домішку Джіні 0.5,

тоді середня домішка Джіні не повинна бути (0.0 + 0.5) / 2 = 0.25, а скоріше 50 / (50 + 450) * 0.0 + 450 / (50 + 450) * 0.5 = 0.45.

Гаразд, а як нам знайти найкращий розділ? Проста, але тверезна відповідь:

Просто спробуйте всі розділи та виберіть той із найбільшим приростом інформації. По суті, це підхід грубої сили.

Якщо бути більш точним, то використовують стандартні дерева рішень розбивається по осях координат, тобто xᵢ = c за якусь особливість i і поріг c. Це означає, що

• одна частина розділених даних складається з усіх точок даних x з xᵢ cта
• інша частина всіх пунктів x з xᵢ ≥ c.

Ці прості правила поділу довели себе достатньо добре на практиці, але ви, звичайно, також можете розширити цю логіку, щоб створити інші поділи (тобто діагональні лінії, такі як xᵢ + 2xⱼ = 3, наприклад).

Чудово, це всі інгредієнти, які нам зараз потрібні!

Зараз ми запровадимо дерево рішень. Оскільки він складається з вузлів, визначимо a Node клас перший.

from dataclasses import dataclass @dataclass
class Node: feature: int = None # feature for the split value: float = None # split threshold OR final prediction left: np.array = None # store one part of the data right: np.array = None # store the other part of the data

Вузол знає функцію, яку він використовує для розбиття (feature), а також значення розщеплення (value). value також використовується як сховище для остаточного прогнозу дерева рішень. Оскільки ми будемо будувати бінарне дерево, кожен вузол повинен знати своїх лівих і правих дочірніх елементів, як вони зберігаються в left та  right .

Тепер давайте займемося фактичною реалізацією дерева рішень. Я роблю його сумісним із scikit-learn, тому використовую деякі класи з sklearn.base . Якщо ви не знайомі з цим, перегляньте мою статтю про це як створити моделі, сумісні з scikit-learn.

Давайте реалізовувати!

import numpy as np
from sklearn.base import BaseEstimator, ClassifierMixin class DecisionTreeClassifier(BaseEstimator, ClassifierMixin): def __init__(self): self.root = Node() @staticmethod def _gini(y): """Gini impurity.""" counts = np.bincount(y) p = counts / counts.sum() return (p * (1 - p)).sum() def _split(self, X, y): """Bruteforce search over all features and splitting points.""" best_information_gain = float("-inf") best_feature = None best_split = None for feature in range(X.shape[1]): split_candidates = np.unique(X[:, feature]) for split in split_candidates: left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] information_gain = self._gini(y) - ( len(X_left) / len(X) * self._gini(y_left) + len(X_right) / len(X) * self._gini(y_right) ) if information_gain > best_information_gain: best_information_gain = information_gain best_feature = feature best_split = split return best_feature, best_split def _build_tree(self, X, y): """The heavy lifting.""" feature, split = self._split(X, y) left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] if len(X_left) == 0 or len(X_right) == 0: return Node(value=np.argmax(np.bincount(y))) else: return Node( feature, split, self._build_tree(X_left, y_left), self._build_tree(X_right, y_right), ) def _find_path(self, x, node): """Given a data point x, walk from the root to the corresponding leaf node. Output its value.""" if node.feature == None: return node.value else: if x[node.feature] node.value: return self._find_path(x, node.left) else: return self._find_path(x, node.right) def fit(self, X, y): self.root = self._build_tree(X, y) return self def predict(self, X): return np.array([self._find_path(x, self.root) for x in X])

І це все! Тепер ви можете робити все те, що вам подобається в scikit-learn:

dt = DecisionTreeClassifier().fit(X, y)
print(dt.score(X, y)) # accuracy # Output
# 1.0

Оскільки дерево нерегуляризоване, воно сильно переобладнується, отже, ідеальна оцінка поїзда. Точність була б гіршою на невидимих ​​даних. Ми також можемо перевірити, як виглядає дерево через

print(dt.root) # Output (prettified manually):
# Node(
# feature=1,
# value=-0.14963454032767076,
# left=Node(
# feature=0,
# value=0.04575851730144607,
# left=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# ),
# right=Node(
# feature=None,
# value=1,
# left=None,
# right=None
# )
# ),
# right=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# )
# )

На малюнку це буде так:

Зображення автора

У цій статті ми детально розглянули, як працюють дерева рішень. Ми почали з деяких нечітких, але інтуїтивно зрозумілих ідей і перетворили їх на формули та алгоритми. Зрештою, нам вдалося реалізувати дерево рішень з нуля.

Проте застереження: наше дерево рішень ще не можна врегулювати. Зазвичай ми хочемо вказати такі параметри, як

• максимальна глибина
• розмір листя
• і мінімальний приріст інформації

серед багатьох інших. На щастя, реалізувати ці речі не так вже й складно, тому це ідеальне домашнє завдання для вас. Наприклад, якщо вказати leaf_size=10 як параметр, то вузли, що містять більше 10 зразків, більше не слід розділяти. Також ця реалізація є не ефективний. Зазвичай вам не потрібно зберігати частини наборів даних у вузлах, а лише індекси. Отже, ваш (потенційно великий) набір даних знаходиться в пам’яті лише один раз.

Хороша річ у тому, що тепер ви можете збожеволіти з цим шаблоном дерева рішень. Ти можеш:

• реалізувати діагональні розбиття, тобто xᵢ + 2xⱼ = 3 замість просто xᵢ = 3,
• змінити логіку, яка відбувається всередині листків, тобто ви можете запустити логістичну регресію в межах кожного листка замість просто голосування більшістю, що дає вам лінійне дерево
• змініть процедуру поділу, тобто замість застосування грубої сили спробуйте кілька випадкових комбінацій і виберіть найкращу, що дає вам класифікатор додаткового дерева
• і багато іншого.

 
 
Доктор Роберт Кюблер є дослідником даних у Publicis Media та автором Towards Data Science.

 
Оригінал. Повідомлено з дозволу.
 

• Розповсюдження контенту та PR на основі SEO. Отримайте посилення сьогодні.
• Платоблокчейн. Web3 Metaverse Intelligence. Розширені знання. Доступ тут.
• джерело: https://www.kdnuggets.com/2023/02/understanding-implementing-decision-tree.html?utm_source=rss&utm_medium=rss&utm_campaign=understanding-by-implementing-decision-tree