Arborii de decizie sunt unul dintre cele mai intuitive și utilizate algoritmi de învățare mașină de mare scară pentru atât clasificarea și regresie. Ei lucrează prin divizarea datelor în ramuri bazate pe valori caracteristice, imitarea modul în care oamenii iau decizii. În timp ce bibliotecile, cum ar fi scikit-learn face copacii de decizie de construcție trivial, implementarea unul de la zero este o modalitate excelentă pentru începători pentru a înțelege algoritmul ți funcționează interior. Acest tutorial vă va ghida prin teorie și cod, astfel încât să puteți construi propriul arbore de decizie de la sol în sus.

Ce este un copac al deciziei?

Un arbore decizional este o structură de tip flowchart, în care fiecare nod intern reprezintă un test pe o caracteristică (de exemplu,

Copacul este construit recursiv: pornind de la rădăcină, algoritmul selectează cea mai bună caracteristică și punct de divizare care separă datele cel mai curat. Acest proces este repetat pe fiecare subset până când este îndeplinită o condiție de oprire. Pentru mai mult fundal, Wikipedia

Concepte fundamentale trebuie să înțelegeți

Noduri, ramuri şi frunze

Nodul rădăcină conține întregul set de date de formare. Nodurile interne testa o caracteristică și împărțite datele în două sau mai multe noduri pentru copii. Ramurile sunt conexiunile care reprezintă rezultatul unui test. Noduri de frunze (noduri terminale) ieșire predicție finală

Criterii de divizare

Pentru a construi un copac, aveți nevoie de o modalitate de a măsura calitatea unei potențiale împărțiri. Cele mai comune criterii sunt:

  • Gini impurity[
  • Entropia
  • Reducere a variabilității

Algoritmul evaluează fiecare fragment posibil al fiecărei caracteristici și îl alege pe cel care produce cea mai mare reducere a impurităţii (sau câștigul în informații).

Rata de câștig și câștig a informațiilor

Câștigarea informațiilor este diferența dintre impuritatea nodului părinte și suma ponderată a impurităților copilului. Deși simplă, ea tinde să favorizeze caracteristicile cu multe valori. Raportul câștig (utilizat în C4.5) normalizează acest lucru. Pentru acest tutorial vom rămâne cu câștigul standard de informații folosind impuritate Gini, care este implicit în CART (Clasificare și Revenire Trees).

Construirea unui copac de decizie pas cu pas

1. Pregătiți datele

Aveți nevoie de un set de date cu caracteristici și etichete țintă. Pentru simplitate, utilizați un set de date binar de clasificare cu caracteristici numerice. De exemplu:

  • Caracteristici: Vârsta, venitul
  • Ţinta: Aprobat (1) sau neaprobat (0)

Curățați datele: mânuiți valorile lipsă, eliminați duplicatele și asigurați-vă că tipurile numerice. Arborii decizionali pot gestiona tipurile de date mixte, dar vom rămâne la numeric pentru implementare.

2. Definirea unei funcții de criteriu de divizare

Vom implementa impuritatea Gini. Indexul Gini pentru un set de elemente este:

unde p i este proporția de elemente din clasa i. Pentru o divizare binară, Gini este media ponderată a nodurilor pentru copii.

3. Punerea în aplicare a evaluării de divizare

Pentru fiecare caracteristică, sortați valorile unice. Testați fiecare prag posibil (mijlocul dintre valorile consecutive sortate). Pentru fiecare prag candidat, împărțiți datele în grupuri stânga și dreapta, calculați Gini și urmăriți cea mai bună împărțire.

4. Construi copacul recursiv

Creați o funcție care ia un subset de date și o adâncime curentă. Ea verifică condițiile de oprire (de exemplu, adâncimea maximă atinsă, eșantioane minime per nod sau niciun câștig de informații). Dacă o condiție este îndeplinită, creați un nod de frunze cu clasa majoritară. Altfel, găsiți cel mai bun despărțit și creați un nod intern, apoi apelați recursiv funcția pe partea stângă și dreapta se divide.

5. Face predicții

Odată ce copacul este construit, predicția este simplă: începeți de la rădăcină, urmați ramurile prin evaluarea testelor de caracteristici pe noua mostră, și returnați valoarea frunzei pe care aterizați.

Implementare completă în Python

Mai jos este o implementare completă, minimă a unui arbore decizional pentru clasificarea folosind impuritate Gini. Acest cod este destinat pentru învățare 

import numpy as np
from collections import Counter

class DecisionTree:
 def __init__(self, max_depth=None, min_samples_split=2):
 self.max_depth = max_depth
 self.min_samples_split = min_samples_split
 self.tree = None

 def fit(self, X, y):
 dataset = np.column_stack((X, y))
 self.tree = self._grow_tree(dataset)

 def _grow_tree(self, dataset, depth=0):
 X, y = dataset[:, :-1], dataset[:, -1]
 n_samples, n_features = X.shape
 n_labels = len(np.unique(y))

 # Stopping conditions
 if (n_labels == 1 or depth == self.max_depth or n_samples < self.min_samples_split):
 leaf_value = Counter(y).most_common(1)[0][0]
 return {'leaf': True, 'value': leaf_value}

 best_feature, best_threshold = self._best_split(dataset, n_features)
 if best_feature is None:
 leaf_value = Counter(y).most_common(1)[0][0]
 return {'leaf': True, 'value': leaf_value}

 left_idx, right_idx = self._split(dataset[:, best_feature], best_threshold)
 left_subtree = self._grow_tree(dataset[left_idx], depth+1)
 right_subtree = self._grow_tree(dataset[right_idx], depth+1)
 return {'leaf': False,
 'feature': best_feature,
 'threshold': best_threshold,
 'left': left_subtree,
 'right': right_subtree}

 def _best_split(self, dataset, n_features):
 best_gini = float('inf')
 best_feature, best_threshold = None, None
 for feature in range(n_features):
 thresholds = np.unique(dataset[:, feature])
 for i in range(len(thresholds)-1):
 thresh = (thresholds[i] + thresholds[i+1]) / 2
 left_idx, right_idx = self._split(dataset[:, feature], thresh)
 if len(left_idx) == 0 or len(right_idx) == 0:
 continue
 gini = self._gini_gain(dataset, left_idx, right_idx)
 if gini < best_gini:
 best_gini = gini
 best_feature = feature
 best_threshold = thresh
 return best_feature, best_threshold

 def _split(self, values, threshold):
 left_idx = np.where(values <= threshold)[0]
 right_idx = np.where(values > threshold)[0]
 return left_idx, right_idx

 def _gini_gain(self, dataset, left_idx, right_idx):
 total = len(left_idx) + len(right_idx)
 gini_left = self._gini(dataset[left_idx, -1])
 gini_right = self._gini(dataset[right_idx, -1])
 return (len(left_idx)/total) * gini_left + (len(right_idx)/total) * gini_right

 def _gini(self, labels):
 _, counts = np.unique(labels, return_counts=True)
 p = counts / np.sum(counts)
 return 1 - np.sum(p**2)

 def predict(self, X):
 return np.array([self._predict_row(x, self.tree) for x in X])

 def _predict_row(self, x, node):
 if node['leaf']:
 return node['value']
 if x[node['feature']] <= node['threshold']:
 return self._predict_row(x, node['left'])
 else:
 return self._predict_row(x, node['right'])

Testarea copacului

Utilizați un set de date simplu, cum ar fi setul clasic de iris (două caracteristici pentru clasificarea binară). scikit-learn Iris Set ] funcționează bine. Comparați precizia copacului dumneavoastră ți-s cu scikit-learn . pentru a verifica corectitudinea.

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

data = load_iris()
X = data.data[:100] # take only first two classes (binary)
y = data.target[:100]

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

tree = DecisionTree(max_depth=3)
tree.fit(X_train, y_train)
preds = tree.predict(X_test)
accuracy = np.mean(preds == y_test)
print(f'Accuracy: {accuracy:.2f}')

Tehnici avansate pentru a vă îmbunătăţi arborele

Prăjirea pentru a evita supraadaptarea

Un copac matur poate memora zgomotul în datele de formare. Prunning elimină ramurile care au putere predictivă mică. Metodele comune sunt pre-prunting (oprește creșterea timpurie prin sau ) și post-prunting (creștind arborele complet apoi eliminarea ramurilor folosind un set de validare sau de calcul al complexității costurilor). Implementarea noastră sprijină deja pre-prunting.

Manipularea caracteristicilor continue și categorii

Pentru caracteristici continue, am folosit punctele de mijloc între valorile sortate ca praguri. Pentru caracteristicile categorice (de exemplu,

Să ne ocupăm de valorile lipsă

Datele din lumea reală au adesea valori lipsă. O abordare simplă este de a atribui valorile lipsă celei mai frecvente ramuri dintre probele de formare care au caracteristica. C4.5 utilizează o metodă probabilistică. Deoarece acesta este un tutorial începător, presupunem că datele sunt complete.

Compararea cu bibliotecile şi citirea ulterioară

În timp ce construirea de la zero este educaţională, sistemele de producţie folosesc biblioteci cum ar fi scitit-learn care oferă implementări optimizate C. Puteţi afla mai multe de la oficial scikit-learn decizie copaci documentaţie. Pentru teoria mai profundă, cartea

Concluzie

Construirea unui copac de decizie de la zero demistifiază unul dintre algoritmii cei mai fundamentali în învățarea mașinii. Ați învățat cum o procedură simplă de divizare recursivă poate produce un model puternic. Prin scrierea codului singur, veți obține o înțelegere mai profundă a măsurilor de impuritate, selecție împărțită, și compromisurile între prejudecată și varianță. Ca un pas următor, încercați adăugarea suport de regresie, tăiere, sau manipularea caracteristicilor categorice. Abilitățile pe care le dezvoltați aici vă va servi bine și vă mutați la metode mai complexe ansamblu, cum ar fi pădurile aleatoare și creșterea gradientului.