Forståelse ved å implementere: Beslutningstre

Bilde av forfatter

Mange avanserte maskinlæringsmodeller som tilfeldige skoger eller gradientforsterkende algoritmer som XGBoost, CatBoost eller LightGBM (og til og med autoenkodere!) stole på en viktig felles ingrediens: den beslutningstre!

Uten å forstå beslutningstrær er det umulig å forstå noen av de nevnte avanserte bagging- eller gradientforsterkende algoritmene også, noe som er en skam for enhver dataforsker! Så la oss avmystifisere den indre funksjonen til et beslutningstre ved å implementere en i Python.

I denne artikkelen vil du lære

• hvorfor og hvordan et beslutningstre deler data,
• informasjonsgevinsten, og
• hvordan implementere beslutningstrær i Python ved hjelp av NumPy.

Du finner koden på min Github.

For å lage spådommer er beslutningstrær avhengige av splitting datasettet i mindre deler på en rekursiv måte.

Bilde av forfatter

På bildet ovenfor kan du se ett eksempel på en splittelse - det originale datasettet deles i to deler. I neste trinn splittes begge disse delene igjen, og så videre. Dette fortsetter inntil et slags stoppkriterium er oppfylt, f.eks.

• hvis delingen resulterer i at en del er tom
• hvis en viss rekursjonsdybde ble nådd
• hvis (etter tidligere delinger) datasettet bare består av noen få elementer, noe som gjør ytterligere oppdelinger unødvendig.

Hvordan finner vi disse splittelsene? Og hvorfor bryr vi oss i det hele tatt? La oss finne det ut.

Motivasjon

La oss anta at vi ønsker å løse en binære klassifiseringsproblem som vi lager selv nå:

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)

De todimensjonale dataene ser slik ut:

Bilde av forfatter

Vi kan se at det er to forskjellige klasser - lilla i omtrent 75 % og gul i omtrent 25 % av tilfellene. Hvis du mater disse dataene til et beslutningstre klassifikator, har dette treet følgende tanker i utgangspunktet:

"Det er to forskjellige merker, som er for rotete for meg. Jeg vil rydde opp i dette rotet ved å dele dataene i to deler – disse delene bør være renere enn de fullstendige dataene før.» — tre som fikk bevissthet

Og det gjør treet.

Bilde av forfatter

Treet bestemmer seg for å lage en klyv omtrent langs x-akser. Dette har den effekten at den øverste delen av dataene nå er perfekt ren, betyr at du bare finner en enkelt klasse (lilla i dette tilfellet) der.

Den nederste delen er imidlertid fortsatt rotete, enda rotete enn før på en måte. Klasseforholdet pleide å være rundt 75:25 i hele datasettet, men i denne mindre delen er det omtrent 50:50, som er så blandet som det kan bli

 OBS: Her spiller det ingen rolle at det lilla og gule er pent atskilt på bildet. Bare rå mengder av forskjellige etiketter i de to delene teller.

Bilde av forfatter

Likevel er dette godt nok som et første skritt for treet, og slik fortsetter det. Selv om det ikke ville skape en ny splittelse i toppen, ren del lenger, kan den lage en annen splitt i bunndelen for å rydde opp.

Bilde av forfatter

Et voilà, hver av de tre separate delene er helt rene, da vi bare finner en enkelt farge (etikett) per del.

Det er veldig enkelt å lage spådommer nå: Hvis et nytt datapunkt kommer inn, sjekker du bare inn hvilket av tre deler den ligger og gi den tilsvarende farge. Dette fungerer så bra nå fordi hver del er det ren. Enkelt, ikke sant?

Bilde av forfatter

Ok, vi snakket om ren og rotete data, men så langt representerer disse ordene bare en vag idé. For å implementere noe, må vi finne en måte å definere renslighet.

Tiltak for renslighet

La oss anta at vi for eksempel har noen etiketter

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]

Intuitivt, y₁ er det reneste settet med etiketter, etterfulgt av y₂ og deretter y₃. Så langt så bra, men hvordan kan vi sette tall på denne oppførselen? Kanskje det enkleste du tenker på er følgende:

Bare tell antall nuller og antall enere. Beregn deres absolutte forskjell. For å gjøre det finere, normaliser det ved å dele gjennom lengden på arrayene.

For eksempel, y₂ har 8 oppføringer totalt — 6 nuller og 2 enere. Derfor vår spesialdefinerte renslighetspoeng ville være |6 – 2| / 8 = 0.5. Det er lett å beregne at renslighet score på y₁ og y₃ er henholdsvis 1.0 og 0.0. Her kan vi se den generelle formelen:

Bilde av forfatter

Her n₀ og n₁ er tallene på henholdsvis nuller og enere, n = nXNUMX + nXNUMX er lengden på matrisen og pXNUMX = nXNUMX/n er andelen av 1-etikettene.

Problemet med denne formelen er at den er det spesielt skreddersydd for to klasser, men veldig ofte er vi interessert i flerklasseklassifisering. En formel som fungerer ganske bra er Gini-urenhetsmål:

Bilde av forfatter

eller det generelle tilfellet:

Bilde av forfatter

Det fungerer så bra at scikit-learn vedtok det som standardtiltak for sin DecisionTreeClassifier klasse.

Bilde av forfatter

 OBS: Gini måler rotete i stedet for renslighet. Eksempel: hvis en liste bare inneholder en enkelt klasse (=veldig rene data!), så er alle ledd i summen null, derfor er summen null. Det verste tilfellet er hvis alle klasser vises nøyaktig antall ganger, i så fall er Gini 1–1/C hvor C er antall klasser.

Nå som vi har et mål for renslighet/rotete, la oss se hvordan det kan brukes til å finne gode klyvninger.

Finne splittelser

Det er mange splitter vi velger mellom, men hvilken er en god? La oss bruke vårt første datasett igjen, sammen med Gini-urenhetsmålet.

Bilde av forfatter

Vi teller ikke poengene nå, men la oss anta at 75 % er lilla og 25 % er gule. Ved å bruke definisjonen av Gini, er urenheten i hele datasettet

Bilde av forfatter

Hvis vi deler datasettet langs x-akse, som gjort før:

Bilde av forfatter

De toppdelen har en Gini-urenhet på 0.0 og den nederste delen

Bilde av forfatter

I gjennomsnitt har de to delene en Gini-urenhet på (0.0 + 0.5) / 2 = 0.25, som er bedre enn hele datasettet sine 0.375 fra før. Vi kan også uttrykke det i form av den såkalte informasjonsgevinst:

Informasjonsgevinsten for denne delingen er 0.375 – 0.25 = 0.125.

Enkelt som det. Jo høyere informasjonsgevinst (dvs. jo lavere Gini-urenhet), jo bedre.

OBS: En annen like god innledende splittelse vil være langs y-aksen.

En viktig ting å huske på er at det er nyttig å veie Gini-urenhetene til delene etter størrelsen på delene. La oss for eksempel anta det

• del 1 består av 50 datapunkter og har en Gini-urenhet på 0.0 og
• del 2 består av 450 datapunkter og har en Gini-urenhet på 0.5,

da bør den gjennomsnittlige Gini-urenheten ikke være (0.0 + 0.5) / 2 = 0.25, men heller 50 / (50 + 450) * 0.0 + 450 / (50 + 450) * 0.5 = 0.45.

Ok, og hvordan finner vi den beste splittelsen? Det enkle, men nøkterne svaret er:

Bare prøv alle delingene og velg den med høyest informasjonsgevinst. Det er i bunn og grunn en brute-force-tilnærming.

For å være mer presis bruker standard beslutningstrær deler seg langs koordinataksene, Dvs. xᵢ = c for noen funksjoner i og terskel c. Dette betyr at

• en del av de delte dataene består av alle datapunkter x med xᵢ cog
• den andre delen av alle punkter x med xᵢ ≥ c.

Disse enkle splittereglene har vist seg gode nok i praksis, men du kan selvfølgelig også utvide denne logikken til å lage andre splittelser (dvs. diagonale linjer som f.eks. xᵢ + 2xⱼ = 3, for eksempel).

Flott, dette er alle ingrediensene vi trenger for å komme i gang nå!

Vi skal implementere beslutningstreet nå. Siden den består av noder, la oss definere en Node klasse først.

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

En node kjenner funksjonen den bruker for å dele (feature) samt splittingsverdien (value). value brukes også som et lager for den endelige prediksjonen av beslutningstreet. Siden vi skal bygge et binært tre, må hver node kjenne sine venstre og høyre barn, som lagret i left og right .

La oss nå gjennomføre selve beslutningstreet. Jeg gjør det scikit-learn-kompatibelt, derfor bruker jeg noen klasser fra sklearn.base . Hvis du ikke er kjent med det, sjekk ut artikkelen min om hvordan bygge scikit-learn-kompatible modeller.

La oss implementere!

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

Og det er det! Du kan gjøre alle tingene du liker med scikit-learn nå:

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

Siden treet er uregulert, er det overfitting mye, derav den perfekte togscore. Nøyaktigheten ville være dårligere på usett data. Vi kan også sjekke hvordan treet ser ut 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
# )
# )

Som et bilde vil det være dette:

Bilde av forfatter

I denne artikkelen har vi sett hvordan beslutningstrær fungerer i detalj. Vi startet med noen vage, men likevel intuitive ideer og gjorde dem om til formler og algoritmer. Til slutt klarte vi å implementere et beslutningstre fra bunnen av.

Et ord til forsiktighet imidlertid: Beslutningstreet vårt kan ikke regulariseres ennå. Vanligvis vil vi spesifisere parametere som

• maks dybde
• bladstørrelse
• og minimal informasjonsgevinst

blant mange andre. Heldigvis er disse tingene ikke så vanskelige å implementere, noe som gjør dette til en perfekt lekse for deg. For eksempel hvis du spesifiserer leaf_size=10 som en parameter, bør noder som inneholder mer enn 10 prøver ikke deles lenger. Også denne implementeringen er ikke effektiv. Vanligvis vil du ikke lagre deler av datasettene i noder, men bare indeksene i stedet. Så ditt (potensielt store) datasett er i minnet bare én gang.

Det gode er at du kan bli gal nå med denne beslutningstremalen. Du kan:

• implementere diagonalspalter, dvs xᵢ + 2xⱼ = 3 i stedet for bare xᵢ = 3,
• endre logikken som skjer på innsiden av bladene, dvs. du kan kjøre en logistisk regresjon innenfor hvert blad i stedet for bare å gjøre en flertall, som gir deg en lineært tre
• endre splittingsprosedyren, dvs. i stedet for å bruke brute force, prøv noen tilfeldige kombinasjoner og velg den beste, som gir deg en klassifiserer for ekstra tre
• og mer.

 
 
Dr. Robert Kübler er dataforsker ved Publicis Media og forfatter ved Towards Data Science.

 
original. Ompostet med tillatelse.
 

• SEO-drevet innhold og PR-distribusjon. Bli forsterket i dag.
• Platoblokkkjede. Web3 Metaverse Intelligence. Kunnskap forsterket. Tilgang her.
• kilde: https://www.kdnuggets.com/2023/02/understanding-implementing-decision-tree.html?utm_source=rss&utm_medium=rss&utm_campaign=understanding-by-implementing-decision-tree