Begrijpen door te implementeren: beslissingsboom

Afbeelding door auteur

Veel geavanceerde modellen voor machine learning, zoals willekeurige forests of algoritmen voor het stimuleren van gradiënten, zoals XGBoost, CatBoost of LightGBM (en zelfs auto-encoders!) vertrouwen op een cruciaal gemeenschappelijk ingrediënt: de beslissingsboom!

Zonder de beslissingsbomen te begrijpen, is het onmogelijk om ook maar één van de bovengenoemde geavanceerde bagging- of gradiëntbevorderende algoritmen te begrijpen, wat een schande is voor elke datawetenschapper! Dus laten we de innerlijke werking van een beslissingsboom demystificeren door er een in Python te implementeren.

In dit artikel leer je

• waarom en hoe een beslisboom gegevens splitst,
• de informatiewinst, en
• hoe beslisbomen in Python te implementeren met behulp van NumPy.

Je vindt de code op mijn Github.

Om voorspellingen te doen, vertrouwen beslisbomen op splitsen de dataset recursief in kleinere delen.

Afbeelding door auteur

In de bovenstaande afbeelding ziet u een voorbeeld van een splitsing: de originele dataset wordt in twee delen gescheiden. In de volgende stap worden beide delen weer gesplitst, enzovoort. Dit gaat door totdat aan een bepaald stopcriterium is voldaan, bijvoorbeeld

• als de splitsing ertoe leidt dat een deel leeg is
• als een bepaalde recursiediepte is bereikt
• als (na eerdere splitsingen) de dataset slechts uit enkele elementen bestaat, waardoor verdere splitsingen niet nodig zijn.

Hoe vinden we deze splitsingen? En waarom kan het ons iets schelen? Dat zoeken we uit.

Motivatie

Laten we aannemen dat we a willen oplossen binair classificatieprobleem die we nu zelf creëren:

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 tweedimensionale gegevens zien er als volgt uit:

Afbeelding door auteur

We kunnen zien dat er twee verschillende klassen zijn: paars in ongeveer 75% en geel in ongeveer 25% van de gevallen. Als je deze data invoert in een beslisboom classificeren, deze boom heeft aanvankelijk de volgende gedachten:

“Er zijn twee verschillende labels, dat is te rommelig voor mij. Ik wil deze puinhoop opruimen door de gegevens in twee delen op te splitsen - deze delen zouden schoner moeten zijn dan de volledige gegevens ervoor. — boom die bij bewustzijn kwam

En dat doet de boom ook.

Afbeelding door auteur

De boom besluit ongeveer langs de splitsing een splitsing te maken x-as. Dit heeft als effect dat het bovenste deel van de data nu perfect is schoon, wat betekent dat je alleen vindt een enkele klas (paars in dit geval) daar.

Het onderste deel is echter nog steeds rommelig, zelfs slordiger dan voorheen in zekere zin. De klassenverhouding was vroeger rond de 75:25 in de volledige dataset, maar in dit kleinere deel is het ongeveer 50:50, wat zo verwarrend is als maar kan

 Opmerking: Hier maakt het niet uit dat paars en geel mooi gescheiden zijn op de foto. Alleen de ruwe hoeveelheid van verschillende labels in de twee delen tellen.

Afbeelding door auteur

Toch is dit goed genoeg als eerste stap voor de boom, en zo gaat hij verder. Hoewel het geen nieuwe splitsing in de top zou creëren, schoon deel niet meer, het kan een nieuwe splitsing in het onderste deel creëren om het op te ruimen.

Afbeelding door auteur

Et voilà, elk van de drie losse onderdelen is helemaal schoon, want we vinden maar één kleur (label) per onderdeel.

Het is nu heel eenvoudig om voorspellingen te doen: als er een nieuw datapunt binnenkomt, controleer je gewoon in welk van de drie delen het liegt en geef het de bijbehorende kleur. Dit werkt nu zo goed omdat elk onderdeel is schoon. Makkelijk, toch?

Afbeelding door auteur

Goed, we hadden het over schoon en rommelig gegevens, maar tot nu toe vertegenwoordigen deze woorden slechts een vaag idee. Om iets te implementeren, moeten we een manier vinden om te definiëren zindelijkheid.

Maatregelen voor netheid

Laten we aannemen dat we bijvoorbeeld enkele labels hebben

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]

Intuïtief, j₁ is de schoonste set labels, gevolgd door j₂ en j₃. Tot nu toe gaat het goed, maar hoe kunnen we cijfers op dit gedrag plakken? Misschien is het makkelijkste dat in je opkomt het volgende:

Tel gewoon het aantal nullen en het aantal enen. Bereken hun absolute verschil. Om het mooier te maken, normaliseer je het door de lengte van de arrays te delen.

Bijvoorbeeld j₂ heeft in totaal 8 ingangen - 6 nullen en 2 enen. Vandaar onze custom-defined reinheidsscore zou |6 – 2| zijn / 8 = 0.5. Het is eenvoudig om die netheidsscores te berekenen j₁ en j₃ zijn respectievelijk 1.0 en 0.0. Hier kunnen we de algemene formule zien:

Afbeelding door auteur

Hier nee en nee zijn respectievelijk de getallen nullen en enen, n = n₀ + n₁ is de lengte van de array en p₁ = n₁ / n is het aandeel van de 1 labels.

Het probleem met deze formule is dat het zo is specifiek afgestemd op het geval van twee klassen, maar heel vaak zijn we geïnteresseerd in classificatie met meerdere klassen. Een formule die best goed werkt, is de Gini-onzuiverheidsmeting:

Afbeelding door auteur

of het algemene geval:

Afbeelding door auteur

Het werkt zo goed dat scikit-learn nam het als standaardmaatregel aan voor de DecisionTreeClassifier klasse.

Afbeelding door auteur

 Opmerking: Gini maatregelen rommeligheid in plaats van reinheid. Voorbeeld: als een lijst maar één klasse bevat (=zeer schone data!), dan zijn alle termen in de som nul, dus de som is nul. Het slechtste geval is als alle klassen het exacte aantal keren voorkomen, in welk geval de Gini 1–1/ is.C WAAR C is het aantal klassen.

Nu we een maat hebben voor netheid/rommel, laten we eens kijken hoe die kan worden gebruikt om goede splitsingen te vinden.

Splitsingen zoeken

Er zijn veel splitsingen waar we uit kunnen kiezen, maar welke is een goede? Laten we onze initiële dataset opnieuw gebruiken, samen met de Gini-onzuiverheidsmaat.

Afbeelding door auteur

We gaan de punten nu niet tellen, maar laten we aannemen dat 75% paars is en 25% geel. Met behulp van de definitie van Gini is de onzuiverheid van de volledige dataset

Afbeelding door auteur

Als we de dataset splitsen langs de x-as, zoals eerder gedaan:

Afbeelding door auteur

De bovenste deel heeft een Gini onzuiverheid van 0.0 en het onderste gedeelte

Afbeelding door auteur

Gemiddeld hebben de twee delen een Gini-onzuiverheid van (0.0 + 0.5) / 2 = 0.25, wat beter is dan de 0.375 van de hele dataset van vroeger. We kunnen het ook uitdrukken in termen van de zogenaamde informatiewinst:

De informatiewinst van deze splitsing is 0.375 – 0.25 = 0.125.

Makkelijk als dat. Hoe hoger de informatiewinst (dwz hoe lager de Gini-onzuiverheid), hoe beter.

Opmerking: Een andere even goede initiële splitsing zou langs de y-as zijn.

Een belangrijk ding om in gedachten te houden is dat het nuttig is om weeg de Gini-onzuiverheden van de onderdelen af ​​op basis van de grootte van de onderdelen. Laten we daar bijvoorbeeld van uitgaan

• deel 1 bestaat uit 50 datapunten en heeft een Gini-onzuiverheid van 0.0 en
• deel 2 bestaat uit 450 datapunten en heeft een Gini-onzuiverheid van 0.5,

dan zou de gemiddelde Gini-onzuiverheid niet (0.0 + 0.5) / 2 = 0.25 moeten zijn maar eerder 50 / (50 + 450) * 0.0 + 450 / (50 + 450) * 0.5 = 0.45.

Oké, en hoe vinden we de beste splitsing? Het simpele maar ontnuchterende antwoord is:

Probeer gewoon alle splitsingen uit en kies degene met de hoogste informatiewinst. Het is eigenlijk een brute-force aanpak.

Om preciezer te zijn, gebruiken standaard beslisbomen splitst langs de coördinaatassen, Dwz xᵢ = c voor een bepaald kenmerk i en drempel c. Dit betekent dat

• een deel van de gesplitste gegevens bestaat uit alle gegevenspunten x Met xᵢ cen
• het andere deel van alle punten x Met xᵢ ≥ c.

Deze eenvoudige splitsingsregels zijn in de praktijk goed genoeg gebleken, maar je kunt deze logica natuurlijk ook uitbreiden om andere splitsingen te maken (diagonale lijnen zoals xᵢ + 2xⱼ = 3, bijvoorbeeld).

Mooi, dit zijn alle ingrediënten die we nodig hebben om nu aan de slag te gaan!

We gaan nu de beslisboom implementeren. Omdat het uit knooppunten bestaat, definiëren we a Node klasse eerst.

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

Een knooppunt kent de functie die het gebruikt voor het splitsen (feature) evenals de splitsingswaarde (value). value wordt ook gebruikt als opslag voor de uiteindelijke voorspelling van de beslisboom. Aangezien we een binaire boom gaan bouwen, moet elk knooppunt zijn linker- en rechterkinderen kennen, zoals opgeslagen in left en right .

Laten we nu de daadwerkelijke implementatie van de beslissingsboom doen. Ik maak het scikit-learn-compatibel, daarom gebruik ik enkele klassen van sklearn.base . Als je daar niet bekend mee bent, bekijk dan mijn artikel over hoe scikit-learn-compatibele modellen te bouwen.

Laten we implementeren!

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

En dat is het! Je kunt nu alle dingen doen die je leuk vindt aan scikit-learn:

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

Omdat de boom niet geregulariseerd is, past hij veel over, vandaar de perfecte treinscore. De nauwkeurigheid zou slechter zijn bij ongeziene gegevens. Ook kunnen we kijken hoe de boom eruit ziet 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
# )
# )

Als een foto zou het dit zijn:

Afbeelding door auteur

In dit artikel hebben we in detail gezien hoe beslisbomen werken. We begonnen met wat vage, maar toch intuïtieve ideeën en zetten die om in formules en algoritmen. Uiteindelijk hebben we een beslisboom vanaf nul kunnen implementeren.

Wel een waarschuwing: onze beslisboom kan nog niet geregulariseerd worden. Meestal willen we parameters specificeren zoals

• maximale diepte
• bladgrootte
• en minimale informatiewinst

onder vele anderen. Gelukkig zijn deze dingen niet zo moeilijk te implementeren, waardoor dit een perfect huiswerk voor jou is. Als u bijvoorbeeld opgeeft leaf_size=10 als parameter, dan mogen knooppunten met meer dan 10 samples niet meer worden gesplitst. Ook deze uitvoering is niet efficiënt. Meestal wilt u geen delen van de datasets in knooppunten opslaan, maar alleen de indices. Je (potentieel grote) dataset zit dus maar één keer in het geheugen.

Het mooie is dat je nu helemaal uit je dak kunt gaan met dit beslisboomsjabloon. Jij kan:

• diagonale splitsingen implementeren, dwz xᵢ + 2xⱼ = 3 in plaats van alleen xᵢ = 3,
• verander de logica die binnen de bladeren plaatsvindt, dwz u kunt een logistische regressie uitvoeren binnen elk blad in plaats van alleen een meerderheidsstemming uit te voeren, wat u een lineaire boom
• verander de splitsingsprocedure, dwz in plaats van brute kracht uit te oefenen, probeer een aantal willekeurige combinaties en kies de beste, die u een extra-boom classificatie
• en meer.

 
 
Dr. Robert Kübler is datawetenschapper bij Publicis Media en auteur bij Towards Data Science.

 
ORIGINELE. Met toestemming opnieuw gepost.
 

• Door SEO aangedreven content en PR-distributie. Word vandaag nog versterkt.
• Platoblockchain. Web3 Metaverse Intelligentie. Kennis versterkt. Toegang hier.
• Bron: https://www.kdnuggets.com/2023/02/understanding-implementing-decision-tree.html?utm_source=rss&utm_medium=rss&utm_campaign=understanding-by-implementing-decision-tree