Arusaamine juurutamise teel: otsustuspuu

Pilt autorilt

Paljud täiustatud masinõppemudelid, nagu juhuslikud metsad või gradiendi võimendamise algoritmid, nagu XGBoost, CatBoost või LightGBM (ja isegi autoenkoodrid!) tugineda olulisele ühisele koostisosale: otsustuspuu!

Otsustuspuid mõistmata on võimatu mõista ka ühtki eelnimetatud täiustatud kottimise või gradiendi suurendamise algoritmi, mis on iga andmeteadlase jaoks häbiväärne! Niisiis, demüstifitseerigem otsustuspuu sisemised toimimised, rakendades selle Pythonis.

Sellest artiklist saate teada

• miks ja kuidas otsustuspuu andmeid jagab,
• teabe saamine ja
• kuidas rakendada Pythonis NumPy abil otsustuspuid.

Koodi leiate aadressilt minu Github.

Ennustuste tegemiseks tuginevad otsustuspuud tükeldamine andmestiku rekursiivselt väiksemateks osadeks.

Pilt autorilt

Ülaltoodud pildil näete ühte näidet jagamisest – algne andmestik jagatakse kaheks osaks. Järgmises etapis jagunevad mõlemad osad uuesti ja nii edasi. See jätkub seni, kuni on täidetud mingisugune peatumiskriteerium, näiteks

• kui jagamise tulemusena jääb osa tühjaks
• kui saavutati teatud rekursiooni sügavus
• kui (pärast eelnevaid poolitusi) koosneb andmestik vaid mõnest elemendist, mistõttu pole edasisi poolitusi vaja teha.

Kuidas me need lõhed leiame? Ja miks me üldse hoolime? Uurime välja.

Motiveerimine

Oletame, et tahame lahendada a binaarne klassifikatsiooni probleem mida me praegu ise loome:

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)

Kahemõõtmelised andmed näevad välja järgmised:

Pilt autorilt

Näeme, et on kaks erinevat klassi - lilla umbes 75% ja kollane umbes 25% juhtudest. Kui sisestate need andmed otsustuspuusse klassifikaator, sellel puul on esialgu järgmised mõtted:

"Seal on kaks erinevat silti, mis on minu jaoks liiga segane. Ma tahan selle segaduse puhastada, jagades andmed kaheks osaks – need osad peaksid olema puhtamad kui kõik andmed. — teadvusele tulnud puu

Ja nii teeb puu.

Pilt autorilt

Puu otsustab teha lõhe umbes piki x-telg. Selle tulemusel on andmete ülemine osa nüüd täiuslik puhas, mis tähendab, et sa ainult leiad üksainus klass (antud juhul lilla) seal.

Alumine osa on aga alles räpane, mõnes mõttes isegi segasem kui varem. Varem oli klassisuhe täielikus andmekogumis umbes 75:25, kuid selles väiksemas osas on see umbes 50:50, mis on nii segane kui olla saab.

 Märge: Siin pole vahet, et lilla ja kollane on pildil ilusti eraldatud. Lihtsalt toores kogus erinevatest siltidest kahes osas arvestada.

Pilt autorilt

Siiski on see puu jaoks esimeseks sammuks piisavalt hea ja nii see jätkub. Kuigi see ei tekitaks tippu uut lõhet, puhastama osa enam, võib see puhastamiseks tekitada alumisse ossa uue lõhe.

Pilt autorilt

Et voilà, kõik kolm eraldi osa on täiesti puhtad, kuna leiame ainult ühe värvi (sildi) osa kohta.

Praegu on tõesti lihtne ennustada: kui saabub uus andmepunkt, kontrollige lihtsalt, milline neist kolm osa see valetab ja annab sellele vastava värvi. See töötab nüüd nii hästi, sest iga osa on puhastama. Lihtne, eks?

Pilt autorilt

Olgu, me rääkisime sellest puhastama ja räpane andmed, kuid seni esindavad need sõnad vaid mingit ebamäärast ideed. Selleks, et midagi ellu viia, peame leidma viisi defineerimiseks puhtus.

Meetmed puhtuse tagamiseks

Oletame, et meil on näiteks mõned sildid

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]

Intuitiivselt y₁ on puhtaim siltide komplekt, millele järgneb y₂ ja siis y₃. Siiani on kõik hästi, aga kuidas me saame selle käitumise kohta numbreid panna? Võib-olla on kõige lihtsam asi, mis meelde tuleb:

Lihtsalt loendage nullide arv ja ühtede arv. Arvutage nende absoluutne erinevus. Selle ilusamaks muutmiseks normaliseerige see massiivi pikkusega jagades.

Näiteks y₂ on kokku 8 kirjet — 6 nulli ja 2 ühte. Seega meie kohandatud määratletud puhtuse hinne oleks |6 – 2| / 8 = 0.5. Seda puhtuseskoori on lihtne välja arvutada y₁ ja y₃ on vastavalt 1.0 ja 0.0. Siin näeme üldist valemit:

Pilt autorilt

Siin n₀ ja n₁ on vastavalt numbrid nullid ja ühed, n = n0 + n1 on massiivi pikkus ja p1 = nl/n on 1 siltide osakaal.

Selle valemi probleem seisneb selles, et see on nii spetsiaalselt kahe klassi jaoks kohandatud, kuid väga sageli oleme huvitatud mitme klassi klassifikatsioonist. Üks valem, mis töötab üsna hästi, on Gini lisandite mõõt:

Pilt autorilt

või üldine juhtum:

Pilt autorilt

See töötab nii hästi, et scikit-learn võttis selle vaikimisi meetmena selle eest DecisionTreeClassifier klass.

Pilt autorilt

 Märge: Gini mõõdud segadus puhtuse asemel. Näide: kui loendis on ainult üks klass (=väga puhtad andmed!), siis on kõik summas olevad liikmed nullid, seega on summa null. Halvimal juhul on see, kui kõik klassid ilmuvad täpselt nii palju kordi, kui Gini on 1–1/C kus C on klasside arv.

Nüüd, kui meil on puhtuse/sagaduse mõõt, vaatame, kuidas seda kasutada heade lõhede leidmiseks.

Lõhede leidmine

Meil on palju jaotusi, kuid milline on hea? Kasutagem uuesti oma esialgset andmekogumit koos Gini lisandite mõõtmisega.

Pilt autorilt

Punkte me nüüd ei loe, aga oletame, et 75% on lillad ja 25% kollased. Gini määratlust kasutades on kogu andmestiku lisand

Pilt autorilt

Kui jagame andmestiku piki x-telg, nagu varem tehtud:

Pilt autorilt

. ülemises osas on Gini lisand 0.0 ja alumine osa

Pilt autorilt

Keskmiselt on kahe osa Gini lisand (0.0 + 0.5) / 2 = 0.25, mis on parem kui kogu andmestiku 0.375 varem. Võime seda väljendada ka nn info saamine:

Selle jaotuse teabekasv on 0.375 – 0.25 = 0.125.

Nii lihtne. Mida suurem on infovõimendus (st mida väiksem on Gini lisand), seda parem.

Märge: Teine sama hea esialgne jaotus oleks piki y-telge.

Oluline on meeles pidada, et see on kasulik kaaluge osade Gini lisandeid osade suuruse järgi. Oletame näiteks, et

• osa 1 koosneb 50 andmepunktist ja selle Gini lisand on 0.0 ja
• osa 2 koosneb 450 andmepunktist ja selle Gini lisandi väärtus on 0.5,

siis ei tohiks Gini keskmine lisand olla (0.0 + 0.5) / 2 = 0.25, vaid pigem 50 / (50 + 450) * 0.0 + 450 / (50 + 450) * 0.5 = 0.45.

Olgu, ja kuidas me leiame parima jaotuse? Lihtne, kuid kainestav vastus on:

Proovige lihtsalt kõiki jaotusi ja valige see, millel on suurim teabekasv. Põhimõtteliselt on see julma jõuga lähenemine.

Täpsemalt kasutatakse standardseid otsustuspuid poolitab piki koordinaattelgesid, st xᵢ = c mõne funktsiooni jaoks i ja lävi c. See tähendab, et

• üks osa jagatud andmetest koosneb kõigist andmepunktidest x koos xᵢ cja
• kõigi punktide teine ​​osa x koos xᵢ ≥ c.

Need lihtsad tükeldamise reeglid on praktikas osutunud piisavalt heaks, kuid loomulikult saate seda loogikat laiendada ka muude poolituste (nt diagonaaljoonte nagu xᵢ + 2xⱼ = 3, näiteks).

Suurepärane, need on kõik koostisosad, mida me nüüd vajame!

Rakendame praegu otsuste puud. Kuna see koosneb sõlmedest, siis defineerime a Node klass esimene.

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

Sõlm teab funktsiooni, mida ta kasutab poolitamiseks (feature) samuti jagamise väärtus (value). value kasutatakse ka salvestusruumina otsustuspuu lõplikuks ennustamiseks. Kuna me ehitame binaarpuu, peab iga sõlm teadma oma vasakut ja paremat järglasi, nagu see on salvestatud left ja right .

Nüüd teeme tegeliku otsustuspuu juurutamise. Muudan selle scikit-learniga ühilduvaks, seetõttu kasutan mõnda klassi alates sklearn.base . Kui te pole sellega tuttav, vaadake minu artiklit selle kohta kuidas luua scikit-learniga ühilduvaid mudeleid.

Viime ellu!

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

Ja see ongi kõik! Nüüd saate teha kõike, mis teile scikit-learni juures meeldib.

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

Kuna puu on ebaregulaarne, sobib see palju üle, seega ideaalne rongiskoor. Nähtamatute andmete puhul oleks täpsus halvem. Samuti saame vaadata, kuidas puu välja näeb 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
# )
# )

Pildina oleks see järgmine:

Pilt autorilt

Selles artiklis oleme üksikasjalikult näinud, kuidas otsustuspuud töötavad. Alustasime mõne ebamäärase, kuid intuitiivse ideega ning muutsime need valemiteks ja algoritmideks. Lõpuks saime otsustuspuu nullist juurutada.

Ettevaatust siiski: meie otsustuspuud ei saa veel seadustada. Tavaliselt sooviksime täpsustada selliseid parameetreid nagu

• max sügavus
• lehe suurus
• ja minimaalne teabekasum

paljude teiste seas. Õnneks pole neid asju nii keeruline rakendada, mistõttu on see teie jaoks ideaalne kodutöö. Näiteks kui täpsustate leaf_size=10 parameetrina ei tohiks enam kui 10 näidist sisaldavaid sõlme enam poolitada. Samuti on see teostus ei ole tõhus. Tavaliselt ei soovi te sõlmedesse salvestada andmekogude osi, vaid selle asemel ainult indekseid. Seega on teie (potentsiaalselt suur) andmestik mälus ainult üks kord.

Hea on see, et selle otsustuspuu malliga saate nüüd hulluks minna. Sa saad:

• rakendada diagonaallõhesid, st xᵢ + 2xⱼ = 3 mitte lihtsalt xᵢ = 3,
• muutke lehtede sees toimuvat loogikat, st saate teha igas lehes logistilise regressiooni, selle asemel, et teha lihtsalt enamushäält, mis annab teile lineaarne puu
• muutke poolitamise protseduuri, st toore jõu asemel proovige mõnda juhuslikku kombinatsiooni ja valige parim, mis annab teile ekstra-puu klassifikaator
• ja rohkem.

 
 
Dr Robert Kübler on Publicis Media andmeteadlane ja Towards Data Science'i autor.

 
Originaal. Loaga uuesti postitatud.
 

• SEO-põhise sisu ja PR-levi. Võimenduge juba täna.
• Platoblockchain. Web3 metaversiooni intelligentsus. Täiustatud teadmised. Juurdepääs siia.
• Allikas: https://www.kdnuggets.com/2023/02/understanding-implementing-decision-tree.html?utm_source=rss&utm_medium=rss&utm_campaign=understanding-by-implementing-decision-tree