Forståelse ved at implementere: Beslutningstræ

Billede af forfatter

Mange avancerede maskinlæringsmodeller såsom tilfældige skove eller gradientforstærkende algoritmer såsom XGBoost, CatBoost eller LightGBM (og endda autoencodere!) stole på en afgørende fælles ingrediens: den beslutning træ!

Uden at forstå beslutningstræer er det umuligt også at forstå nogen af ​​de førnævnte avancerede sække- eller gradientforstærkende algoritmer, hvilket er en skændsel for enhver dataforsker! Så lad os afmystificere den indre funktion af et beslutningstræ ved at implementere et i Python.

I denne artikel lærer du

• hvorfor og hvordan et beslutningstræ opdeler data,
• informationsgevinsten, og
• hvordan man implementerer beslutningstræer i Python ved hjælp af NumPy.

Du kan finde koden på min Github.

For at lave forudsigelser stoler beslutningstræer på opdeling datasættet i mindre dele på en rekursiv måde.

Billede af forfatter

På billedet ovenfor kan du se et eksempel på en opdeling - det originale datasæt bliver opdelt i to dele. I næste trin bliver begge disse dele splittet igen, og så videre. Dette fortsætter indtil et eller andet stopkriterium er opfyldt, f.eks.

• hvis opdelingen resulterer i, at en del er tom
• hvis en vis rekursionsdybde blev nået
• hvis (efter tidligere opdelinger) datasættet kun består af nogle få elementer, hvilket gør yderligere opdelinger unødvendige.

Hvordan finder vi disse opdelinger? Og hvorfor er vi ligeglade? Lad os finde ud af det.

Motivation

Lad os antage, at vi ønsker at løse en binær klassifikationsproblem som vi selv skaber nu:

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 todimensionelle data ser således ud:

Billede af forfatter

Vi kan se, at der er to forskellige klasser - lilla i omkring 75% og gul i omkring 25% af tilfældene. Hvis du fører disse data til et beslutningstræ klassifikator, dette træ har i første omgang følgende tanker:

"Der er to forskellige mærker, hvilket er for rodet for mig. Jeg vil rydde op i dette rod ved at opdele dataene i to dele - disse dele burde være renere end de komplette data før." - træ, der fik bevidsthed

Og det gør træet.

Billede af forfatter

Træet beslutter sig for at lave en kløft omtrent langs x-akse. Dette har den effekt, at den øverste del af dataene nu er perfekt ren, betyder, at du kun finder en enkelt klasse (lilla i dette tilfælde) der.

Den nederste del er dog stadig rodet, endnu mere rodet end før på en måde. Klasseforholdet plejede at være omkring 75:25 i det komplette datasæt, men i denne mindre del er det omkring 50:50, hvilket er så blandet, som det kan blive

 Bemærk: Her gør det ikke noget, at det lilla og gule er pænt adskilt på billedet. Bare den rå mængde af forskellige etiketter i de to dele tæller.

Billede af forfatter

Alligevel er dette godt nok som et første skridt for træet, og så fortsætter det. Selvom det ikke ville skabe endnu en opdeling i toppen, ren del længere, kan den skabe endnu en split i den nederste del for at rense den op.

Billede af forfatter

Et voilà, hver af de tre separate dele er fuldstændig ren, da vi kun finder en enkelt farve (label) pr.

Det er virkelig nemt at komme med forudsigelser nu: Hvis der kommer et nyt datapunkt ind, tjekker du bare hvilket af tre dele den ligger og giv den den tilsvarende farve. Dette fungerer så godt nu, fordi hver del er ren. Nemt, ikke?

Billede af forfatter

Okay, vi talte om ren , rodet data, men indtil videre repræsenterer disse ord kun en eller anden vag idé. For at implementere noget, er vi nødt til at finde en måde at definere renhed.

Foranstaltninger til renlighed

Lad os antage, at vi f.eks. har nogle 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 sæt etiketter, efterfulgt af y₂ og så y₃. Så langt så godt, men hvordan kan vi sætte tal på denne adfærd? Måske det nemmeste, der kommer til at tænke på, er følgende:

Tæl blot antallet af nuller og antallet af enere. Beregn deres absolutte forskel. For at gøre det pænere, normaliser det ved at dividere gennem længden af ​​arrays.

For eksempel: y₂ har 8 poster i alt - 6 nuller og 2 enere. Derfor vores specialdefinerede renhedsscore ville være |6 – 2| / 8 = 0.5. Det er let at beregne, at renlighed scorer på y₁ , y₃ er henholdsvis 1.0 og 0.0. Her kan vi se den generelle formel:

Billede af forfatter

Her, n₀ , nXNUMX er antallet af henholdsvis nuller og enere, n = nXNUMX + nXNUMX er længden af ​​arrayet og pXNUMX = nXNUMX/n er andelen af ​​de 1 etiketter.

Problemet med denne formel er, at det er det specielt skræddersyet til tilfældet med to klasser, men meget ofte er vi interesserede i multi-class klassificering. En formel, der fungerer ganske godt, er Gini-urenhedsmål:

Billede af forfatter

eller det generelle tilfælde:

Billede af forfatter

Det fungerer så godt, at scikit-learn vedtog det som standardforanstaltning for sin DecisionTreeClassifier klasse.

Billede af forfatter

 Bemærk: Gini måler rodet i stedet for renlighed. Eksempel: hvis en liste kun indeholder en enkelt klasse (=meget rene data!), så er alle led i summen nul, derfor er summen nul. Det værste tilfælde er, hvis alle klasser vises det nøjagtige antal gange, i hvilket tilfælde Gini er 1-1/C hvor C er antallet af klasser.

Nu hvor vi har et mål for renlighed/rod, så lad os se, hvordan det kan bruges til at finde gode spalter.

Finde spaltninger

Der er mange opdelinger, vi vælger imellem, men hvilken er en god? Lad os bruge vores oprindelige datasæt igen sammen med Gini-urenhedsmålet.

Billede af forfatter

Vi tæller ikke pointene nu, men lad os antage, at 75 % er lilla og 25 % er gule. Ved at bruge definitionen af ​​Gini er urenheden af ​​det komplette datasæt

Billede af forfatter

Hvis vi deler datasættet langs x-akse, som gjort før:

Billede af forfatter

 øverste del har en Gini-urenhed på 0.0 og den nederste del

Billede af forfatter

I gennemsnit har de to dele en Gini-urenhed på (0.0 + 0.5) / 2 = 0.25, hvilket er bedre end hele datasættets 0.375 fra før. Vi kan også udtrykke det i form af den såkaldte informationsgevinst:

Informationsgevinsten af ​​denne opdeling er 0.375 – 0.25 = 0.125.

Nemt som det. Jo højere informationsgevinst (dvs. jo lavere Gini-urenhed), jo bedre.

Bemærk: En anden lige så god indledende opdeling ville være langs y-aksen.

En vigtig ting at huske på er, at det er nyttigt at veje delenes Gini-urenheder efter delenes størrelse. Lad os for eksempel antage det

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

så skal den gennemsnitlige Gini-urenhed ikke være (0.0 + 0.5) / 2 = 0.25, men snarere 50 / (50 + 450) * 0.0 + 450 / (50 + 450) * 0.5 = 0.45.

Okay, og hvordan finder vi den bedste opdeling? Det enkle, men nøgterne svar er:

Prøv bare alle opdelingerne og vælg den med den højeste informationsgevinst. Det er dybest set en brute-force tilgang.

For at være mere præcis, bruger standard beslutningstræer deler sig langs koordinatakserne, dvs. xᵢ = c for nogle funktioner i og tærskel c. Dette betyder, at

• en del af de opdelte data består af alle datapunkter x med xᵢ c,
• den anden del af alle punkter x med xᵢ ≥ c.

Disse simple opdelingsregler har vist sig gode nok i praksis, men du kan selvfølgelig også udvide denne logik til at skabe andre opdelinger (dvs. diagonale linjer som f.eks. xᵢ + 2xⱼ = 3, for eksempel).

Fantastisk, det er alle de ingredienser, vi skal bruge for at komme i gang nu!

Vi vil implementere beslutningstræet nu. Da den består af noder, lad os 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 kender den funktion, den bruger til at opdele (feature) samt opdelingsværdien (value). value bruges også som et lager til den endelige forudsigelse af beslutningstræet. Da vi vil bygge et binært træ, skal hver node kende sine venstre og højre børn, som gemt i left , right .

Lad os nu udføre den faktiske implementering af beslutningstræet. Jeg gør det scikit-learn-kompatibelt, derfor bruger jeg nogle klasser fra sklearn.base . Hvis du ikke er bekendt med det, så tjek min artikel om hvordan man bygger scikit-learn-kompatible modeller.

Lad os 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 gøre alle de ting, du elsker ved scikit-learn nu:

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

Da træet er ureguleret, passer det meget, derfor den perfekte togscore. Nøjagtigheden ville være dårligere på usete data. Vi kan også tjekke hvordan træet ser ud 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 billede ville det være dette:

Billede af forfatter

I denne artikel har vi set, hvordan beslutningstræer fungerer i detaljer. Vi startede med nogle vage, men alligevel intuitive ideer og forvandlede dem til formler og algoritmer. I sidste ende var vi i stand til at implementere et beslutningstræ fra bunden.

Dog en advarsel: Vores beslutningstræ kan ikke reguleres endnu. Normalt vil vi gerne specificere parametre som

• max dybde
• bladstørrelse
• og minimal informationsgevinst

blandt mange andre. Heldigvis er disse ting ikke så svære at implementere, hvilket gør dette til et perfekt hjemmearbejde for dig. Hvis du f.eks. angiver leaf_size=10 som en parameter bør noder, der indeholder mere end 10 samples, ikke opdeles længere. Også denne implementering er ikke effektiv. Normalt vil du ikke gemme dele af datasættene i noder, men kun indekserne i stedet. Så dit (potentielt store) datasæt er kun i hukommelsen én gang.

Det gode er, at du kan gå amok nu med denne beslutningstræskabelon. Du kan:

• implementere diagonalspalter, dvs xᵢ + 2xⱼ = 3 i stedet for bare xᵢ = 3,
• ændre den logik, der sker inde i bladene, dvs. du kan køre en logistisk regression inden for hvert blad i stedet for blot at lave en flertalsafstemning, hvilket giver dig en lineært træ
• ændre opdelingsproceduren, dvs. i stedet for at udføre brute force, prøv nogle tilfældige kombinationer og vælg den bedste, hvilket giver dig en ekstra-træ klassificering
• og mere.

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

 
Original. Genopslået med tilladelse.
 

• SEO Powered Content & PR Distribution. Bliv forstærket i dag.
• Platoblokkæde. Web3 Metaverse Intelligence. Viden forstærket. Adgang 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