Päätöksen puut ovat yksi intuitiivisimmista ja laajalti käytetyistä koneoppimisen algoritmeista sekä luokitteluun että regressioon. Ne toimivat jakamalla tietoa haaroihin, jotka perustuvat ominaisuusarvoihin, matkimalla tapaa, jolla ihmiset tekevät päätöksiä. Vaikka kirjastot kuten skikit-oppia tekevät rakennuspäätöksen puita triviaaleja, yhden toteuttaminen tyhjästä on erinomainen tapa aloittelijoille ymmärtää algoritmin . Tämä opetusohjelma ohjaa sinua läpi teorian ja koodin, joten voit rakentaa oman päätöspuun maasta ylös.

Mikä on päätöspuu?

Päätöspuu on vuokaaviomainen rakenne, jossa jokainen sisäinen solmu edustaa testiä ominaisuudella (esim. ...Onko ikä > 30?..), jokaisessa oksassa on kyseisen testin tulos ja jokaisella lehtisolmulla on luokkamerkintä tai jatkuva arvo. Tavoitteena on luoda malli, joka ennustaa tavoitemuuttujaa oppimalla yksinkertaisia päätöksentekosääntöjä, jotka perustuvat datan ominaisuuksiin.Päätöspuut ovat suosittuja, koska niitä on helppo tulkita ja vaatia vähän tietojen esikäsittelyä (ei skaalausta tai normalisointia).

Puu on rakennettu rekursiivisesti: alkaen juuresta, algoritmi valitsee parhaan ominaisuuden ja jakopisteen, joka erottaa tiedot puhtaimmin. Tämä prosessi toistetaan kunkin osajoukon kunnes pysäytys ehto täyttyy. Lisää tausta, Wikipedia ]entry on päätöspuun oppimista[ tarjoaa vankan yleiskuvan.

Sinun täytyy ymmärtää peruskäsitteet

Solmukkeet, oksat ja lehdet

Root-solmuke sisältää koko koulutuskokonaisuuden. Sisäiset solmut testaavat ominaisuuden ja jakavat tiedot kahteen tai useampaan lapsisolmukkeeseen. Haarat ovat yhteyksiä, jotka edustavat testin tulosta. Lehtisolmut (terminaalisolmut) lähdön lopullinen ennuste . Yleisin luokka luokittelussa tai keskiarvo regressiossa.

Jakamisperusteet

Puun rakentamiseen tarvitaan tapa mitata mahdollisen jaon laatua. Yleisimmät kriteerit ovat:

  • Gini epäpuhtaus ... ......................................................................................................................................................................................................................................
  • Entropia[ . ... mittaa häiriön tai epävarmuuden määrän. Tavoitteena on minimoida entropiaa jaon jälkeen (tiedon hyöty).
  • Varianssin vähennys[ . Regressiopuissa käytetty . Se laskee erotuksella saavutetun varianssin (tai keskimääräisen neliövirheen) vähenemisen.

Algoritmi arvioi jokaisen mahdollisen jaon jokaiselle ominaisuudelle ja valitsee sen, joka tuottaa suurimman epäpuhtauden (tai tiedon) vähenemisen.

Tiedon saanti- ja saantisuhde

Tietovoitto on ero emosolmun epäpuhtauden ja lasten epäpuhtauksien painotetun summan välillä. Vaikka se suosiikin ominaisuuksia, joilla on monia arvoja. Voittosuhde (käytetään C4.5) normalisoi tämän. Tätä opetusohjelmaa varten pysymme vakiotietona Gini-epäpuhtauden avulla, joka on oletus CART-ohjelmassa (luokitus ja regressiopuut).

Päätöksentekopuun vaihe vaiheelta

1. Valmistele tietosi

Tarvitset aineiston ominaisuuksia ja kohde tarroja. Yksinkertaisuuden, käytä binäärinen luokitus aineisto numeerisia ominaisuuksia. Esimerkiksi:

  • Ominaisuudet:[ Ikä, tulot
  • kohde:[ Hyväksytty (1) tai ei hyväksytty (0)

Puhdista tiedot: käsittele puuttuvat arvot, poista kaksoiskappaleet ja varmista numerotyypit. Päätöksenteon puut voivat käsitellä sekatyyppisiä tietotyyppejä, mutta me pysymme numeerisissa tiedoissa.

2. Määrittele jakoperuste toiminto

Toteutamme Gini epäpuhtautta. Gini-indeksi on:

[[LLT:0]]

jossa p i on osuus kohteita luokan i. Binääriosiossa, koko Gini on painotettu keskiarvo lapsisolmujen.

3. Toteuta jaetun arvioinnin

Kunkin ominaisuuden osalta lajittele yksilölliset arvot. Testaa jokainen mahdollinen raja-arvo (välipiste peräkkäisen lajitellun arvon välillä). Jaa kunkin ehdokaskynnyksen tiedot vasemmalle ja oikealle ryhmille, laske Gini ja seuraa parasta jakoa.

4. Rakenna puu rekursiivisesti

Luo toiminto, joka vie osajoukko dataa ja nykyisen syvyyden. Se tarkistaa pysäytysolosuhteet (esim., suurin syvyys saavutettu, vähimmäisnäytteet solmua kohti tai ei tietoa voittoa). Jos ehto täyttyy, luo lehtisolmu enemmistöluokan. Muuten, löytää paras split ja luoda sisäinen solmu, sitten rekursiivisesti kutsua funktio vasemmalla ja oikealla splits.

5. Tee ennusteita

Kun puu on rakennettu, ennuste on yksinkertainen: aloita juuresta, seuraa oksia arvioimalla ominaisuustestejä uudesta näytteestä ja palauta painosi.

Täysi toteutus Pythonissa

Alla on täydellinen, minimaalinen toteutus päätöspuun luokittelu Gini epäpuhtauden avulla. Tämä koodi on tarkoitettu oppimiseen .

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

Puun testaus

Käytä yksinkertaista dataa, kuten klassista iiris-dataa (kaksi ominaisuutta binääriluokitukseen). scikit-oppii Iris-data[] toimii hyvin. Vertaa puun tarkkuutta skit-earn. todentaa oikeellisuutta.

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}')

Kehittyneet tekniikat puun parantamiseksi

Leikkaus välttää Ylivarustelu

Täysin kasvanut puu voi muistaa melun harjoitustiedoissa. Pruning poistaa oksat, joilla on vähän ennustevoimaa. Yhteiset menetelmät ovat esikarsinta (kasvun pysäyttäminen varhaisessa vaiheessa tai ) ja jälkikarsinta (puun kasvattaminen ja oksien poistaminen validointi- tai kustannus-monimutkaisuus- karsintamenetelmällä). Toteutumisemme tukee jo valmiiksi leikkaamista.

Käsittely Jatkuvat ja kategoriakohtaiset ominaisuudet

Jatkuvan ominaisuuksien, käytimme midpoints välillä lajiteltujen arvojen kynnysarvot. Voit kategorisia ominaisuuksia (esim., ., .Color = punainen/vihreä/sininen.), jokainen luokka voi tulla erillinen haara (multi-way split) tai voit binary-encode ne. Useimmat modernit implementations (kuten skikit-oppia) käyttää binäärijakoja jopa kategorisia ominaisuuksia arvioimalla kaikki subsets.

Puuttuvat arvot

Real-world data on usein puuttuvat arvot. Yksinkertainen lähestymistapa on määrittää puuttuvat arvot yleisimpiin haara keskuudessa koulutus näytteitä, jotka ovat ominaisuus. C4.5 käyttää probabilistinen menetelmä. Koska tämä on aloittelija opetusohjelma, oletamme, että tiedot ovat täydellisiä.

Verrataan kirjastoihin ja jatkolukemiseen

Vaikka rakennus tyhjästä on opettavaista, tuotantojärjestelmät käyttävät kirjastoja kuten skikit-oppia, joka tarjoaa optimoituja C-toteutuksia. Voit oppia lisää viralliselta [ scikit-oppia päätöspuiden dokumentointi[]. Syvemmälle teorialle kirja .Hastie, Tibshirani ja Friedman ovat arvovaltaisia resursseja. Toinen erinomainen viite on alkuperäinen CART kirja Breiman et al.

Päätelmät

Rakentamalla päätöspuun naarmuuntumaton demystis yksi tärkeimmistä algoritmeista koneoppimisessa. Olet oppinut, miten yksinkertainen rekursiivinen jakomenetelmä voi tuottaa tehokkaan mallin. Kirjoittamalla koodi itse, saat syvemmän käsityksen epäpuhtauden toimenpiteistä, split selection, ja kompromissit välillä harha ja varianssi. Seuraavana askeleena, kokeile lisäämällä regressio tukea, karsiminen, tai käsittely kategorisia ominaisuuksia. Taidot kehität täällä palvelee sinua ja kun siirryt monimutkaisempiin ensemble menetelmiä, kuten satunnaiset metsät ja kaltevuus tehostamalla.