Megértés végrehajtással: Döntési fa

A kép szerzője

Számos fejlett gépi tanulási modell, például véletlenszerű erdők vagy gradiensnövelő algoritmusok, például XGBoost, CatBoost vagy LightGBM (és még automatikus kódolók!) egy kulcsfontosságú közös összetevőre támaszkodnak: a döntési fa!

A döntési fák megértése nélkül lehetetlen megérteni a fent említett fejlett zsákolási vagy gradiensnövelő algoritmusok egyikét sem, ami minden adattudós számára szégyen! Tehát tisztázzuk a döntési fa belső működését oly módon, hogy implementáljuk a Pythonban.

Ebből a cikkből megtudhatja

• miért és hogyan osztja fel a döntési fa az adatokat,
• az információszerzés, és
• hogyan lehet döntési fákat implementálni Pythonban a NumPy használatával.

A kódot megtalálod az én Githubom.

Az előrejelzésekhez a döntési fák támaszkodnak hasítás az adatkészletet rekurzív módon kisebb részekre bontani.

A kép szerzője

A fenti képen láthat egy példát a felosztásra – az eredeti adatkészlet két részre válik szét. A következő lépésben mindkét rész ismét ketté válik, és így tovább. Ez addig folytatódik, amíg nem teljesül valamilyen leállítási feltétel, pl.

• ha a felosztás eredményeként egy rész üres lesz
• ha elértünk egy bizonyos rekurziós mélységet
• ha (korábbi felosztások után) az adatkészlet csak néhány elemből áll, így szükségtelenné válik a további felosztás.

Hogyan találjuk meg ezeket a szakadásokat? És miért is érdekel minket? Találjuk ki.

Motiváció

Tegyük fel, hogy meg akarjuk oldani a kétkomponensű osztályozási probléma amit most létrehozunk:

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)

A kétdimenziós adatok így néznek ki:

A kép szerzője

Láthatjuk, hogy két különböző osztály létezik: lila az esetek 75%-ában és sárga az esetek körülbelül 25%-ában. Ha ezeket az adatokat egy döntési fába táplálja osztályozó, ennek a fának kezdetben a következő gondolatai vannak:

„Két különböző címke van, ami számomra túl kócos. Úgy szeretném felszámolni ezt a rendetlenséget, hogy az adatokat két részre osztom – ezeknek a részeknek tisztábbnak kell lenniük, mint a teljes adatok korábban.” — eszméletlen fa

És a fa is ezt teszi.

A kép szerzője

A fa úgy dönt, hogy körülbelül a mentén hasít x-tengely. Ennek az a hatása, hogy az adatok felső része most már tökéletes tiszta, vagyis csak találsz egyetlen osztály (ebben az esetben lila) ott.

Az alsó rész azonban még mindig rendetlen, bizonyos értelemben még rendetlenebb, mint korábban. Az osztályarány korábban 75:25 körül mozgott a teljes adathalmazban, de ezen a kisebb részben 50:50 körül van, ami annyira kevert, amennyire csak lehet.

 Jegyzet: Itt nem mindegy, hogy a lila és a sárga szépen elválik a képen. Csak a nyers mennyiség a különböző címkékből a két részben számítanak.

A kép szerzője

Ennek ellenére ez elég jó első lépésnek a fának, és így megy tovább. Bár ez nem hozna létre újabb felosztást a csúcson, ragadozó ölyv része többé, újabb hasítást hozhat létre az alsó részben, hogy megtisztítsa.

A kép szerzője

Et voilà, a három különálló rész mindegyike teljesen tiszta, mivel alkatrészenként csak egyetlen színt (címkét) találunk.

Nagyon könnyű most jósolni: ha új adatpont érkezik, csak ellenőrizze, hogy melyik három részből áll hazudik, és adja meg a megfelelő színt. Ez most olyan jól működik, mert mindegyik rész az ragadozó ölyv. Könnyű, igaz?

A kép szerzője

Rendben, beszéltünk róla ragadozó ölyv és a rendetlen adatok, de ezek a szavak eddig csak valami homályos elképzelést képviselnek. Ahhoz, hogy bármit is megvalósíthassunk, meg kell találnunk a definíció módját tisztaság.

Tisztasági intézkedések

Tegyük fel, hogy van például néhány címkénk

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]

Intuitív módon, y₁ a legtisztább címkekészlet, amelyet követ y₂ és azután y₃. Eddig minden rendben volt, de hogyan lehet számot adni erre a viselkedésre? Talán a következő jut eszünkbe a legkönnyebben:

Csak számolja meg a nullák és az egyesek számát. Számítsd ki ezek abszolút különbségét! Hogy szebb legyen, normalizáld úgy, hogy elosztod a tömbök hosszával.

Például, y₂ összesen 8 bejegyzés van – 6 nulla és 2 egyes. Ezért a mi egyénileg meghatározott tisztasági pontszám lenne |6 – 2| / 8 = 0.5. Könnyű kiszámítani, hogy a tisztasági pontszámok y₁ és a y₃ 1.0 és 0.0. Itt láthatjuk az általános képletet:

A kép szerzője

Itt, n₀ és a nXNUMX a nullák és egyesek számai, n = nXNUMX + nXNUMX a tömb hossza és pXNUMX = nl/n az 1 címkék részesedése.

Ezzel a képlettel az a probléma, hogy az kifejezetten két osztály esetére szabva, de nagyon gyakran érdekel minket a többosztályos besorolás. Az egyik nagyon jól működő képlet a Gini-szennyeződés mértéke:

A kép szerzője

vagy általános eset:

A kép szerzője

Olyan jól működik, hogy scikit-learn alapértelmezett intézkedésként fogadta el annak DecisionTreeClassifier osztály.

A kép szerzője

 Jegyzet: Gini méri rendetlenség tisztaság helyett. Példa: ha egy lista csak egyetlen osztályt tartalmaz (=nagyon tiszta adat!), akkor az összegben szereplő összes tag nulla, tehát az összeg nulla. A legrosszabb eset, ha minden osztály pontosan annyiszor jelenik meg, ebben az esetben a Gini 1-1/C ahol C az osztályok száma.

Most, hogy megvan a tisztaság/rendetlenség mértéke, nézzük meg, hogyan használható fel a jó osztások megtalálására.

Szakadások keresése

Sok felosztás közül választhatunk, de melyik a jó? Használjuk újra a kezdeti adatkészletünket a Gini-szennyeződés mértékével együtt.

A kép szerzője

A pontokat most nem számoljuk, de tegyük fel, hogy 75% lila és 25% sárga. A Gini definícióját használva a teljes adatkészlet szennyezettsége az

A kép szerzője

Ha az adathalmazt a mentén felosztjuk x-tengely, mint korábban:

A kép szerzője

A a felső részen 0.0 Gini-szennyeződés található és az alsó része

A kép szerzője

Átlagosan a két rész Gini-szennyeződése (0.0 + 0.5) / 2 = 0.25, ami jobb, mint a teljes adatkészlet korábbi 0.375-ös értéke. Kifejezhetjük úgy is, hogy ún információszerzés:

Ennek a felosztásnak az információnyeresége 0.375 – 0.25 = 0.125.

Ilyen könnyű. Minél nagyobb az információnyereség (azaz minél kisebb a Gini-szennyeződés), annál jobb.

Jegyzet: Egy másik ugyanolyan jó kezdeti felosztás az y tengely mentén lenne.

Fontos szem előtt tartani, hogy hasznos mérjük le az alkatrészek Gini-szennyeződéseit az alkatrészek méretével. Például tegyük fel, hogy

• az 1. rész 50 adatpontból áll, és Gini-szennyeződése 0.0 és
• a 2. rész 450 adatpontból áll, és 0.5-ös Gini-szennyeződést tartalmaz,

akkor az átlagos Gini-szennyeződés ne legyen (0.0 + 0.5) / 2 = 0.25, hanem inkább 50 / (50 + 450) * 0.0 + 450 / (50 + 450) * 0.5 = 0.45.

Oké, és hogyan találjuk meg a legjobb felosztást? Az egyszerű, de kijózanító válasz:

Csak próbálja ki az összes felosztást, és válassza ki azt, amelyik a legtöbb információhoz jut. Ez alapvetően egy brute-force megközelítés.

Pontosabban, szabványos döntési fákat használnak a koordinátatengelyek mentén hasít, azaz xᵢ = c valamilyen funkcióhoz i és küszöb c. Ez azt jelenti, hogy

• a felosztott adatok egy része az összes adatpontból áll x val vel xᵢ cés a
• az összes pont másik része x val vel xᵢ ≥ c.

Ezek az egyszerű felosztási szabályok elég jónak bizonyultak a gyakorlatban, de természetesen ezt a logikát is kiterjesztheti más felosztások létrehozására (pl. átlós vonalak, pl. xᵢ + 2xⱼ = 3, például).

Nagyszerű, ezek mind az összetevők, amelyekre most szükségünk van!

Most végrehajtjuk a döntési fát. Mivel csomópontokból áll, definiáljuk a Node osztály első.

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

Egy csomópont ismeri a felosztáshoz használt szolgáltatást (feature), valamint a felosztási értéket (value). value tárolóként is szolgál a döntési fa végső előrejelzéséhez. Mivel bináris fát fogunk építeni, minden csomópontnak ismernie kell a bal és a jobb oldali gyermekeit, ahogyan benne vannak left és a right .

Most végezzük el a tényleges döntési fa megvalósítását. Scikit-learn kompatibilissé teszem, ezért használok néhány osztályt sklearn.base . Ha nem ismeri ezt, nézze meg a cikkemet hogyan építsünk scikit-learn-kompatibilis modelleket.

Valósítsuk meg!

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])

És ez az! Most mindent megtehetsz, amit a scikit-learnben szeretsz:

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

Mivel a fa szabálytalan, nagyon túl van rajta szerelve, ezért a tökéletes vonatpontszám. A nem látott adatok pontossága rosszabb lenne. Azt is ellenőrizhetjük, hogyan néz ki a fa via

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
# )
# )

Képként ez lenne:

A kép szerzője

Ebben a cikkben részletesen megnéztük, hogyan működnek a döntési fák. Néhány homályos, mégis intuitív ötlettel kezdtük, és képleteket és algoritmusokat alakítottunk ki. Végül egy döntési fát a semmiből tudtunk megvalósítani.

Egy óvatosság azonban: a döntési fánk még nem rendszeresíthető. Általában olyan paramétereket szeretnénk megadni, mint pl

• maximális mélység
• levél mérete
• és minimális információszerzés

sok más között. Szerencsére ezeket a dolgokat nem olyan nehéz megvalósítani, így ez egy tökéletes házi feladat az Ön számára. Például, ha megadja leaf_size=10 paraméterként, akkor a 10-nél több mintát tartalmazó csomópontokat többé nem szabad felosztani. Ezenkívül ez a megvalósítás nem hatékony. Általában nem az adatkészletek részeit szeretné csomópontokban tárolni, hanem csak az indexeket. Tehát a (potenciálisan nagy) adatkészlet csak egyszer van a memóriában.

Az a jó, hogy most megőrülhetsz ezzel a döntési fa sablonnal. Tudsz:

• átlós felosztást valósítson meg, pl xᵢ + 2xⱼ = 3 ahelyett, hogy csak xᵢ = 3,
• változtassa meg a levelek belsejében előforduló logikát, azaz minden egyes levélen belül logisztikus regressziót hajthat végre ahelyett, hogy csak többségi szavazást tenne, ami egy vonalas fa
• módosítsa a felosztási eljárást, azaz a nyers erő alkalmazása helyett próbáljon ki néhány véletlenszerű kombinációt, és válassza ki a legjobbat, ami extra fa osztályozó
• és így tovább.

 
 
Dr. Kübler Róbert a Publicis Media adattudósa és a Towards Data Science szerzője.

 
eredeti. Engedéllyel újra közzétéve.
 

• SEO által támogatott tartalom és PR terjesztés. Erősödjön még ma.
• Platoblockchain. Web3 metaverzum intelligencia. Felerősített tudás. Hozzáférés itt.
• Forrás: https://www.kdnuggets.com/2023/02/understanding-implementing-decision-tree.html?utm_source=rss&utm_medium=rss&utm_campaign=understanding-by-implementing-decision-tree