Rozhodovacie stromy sú všestranné algoritmy strojového učenia, ktoré dokážu vykonávať úlohy klasifikácie aj regresie a dokonca aj úlohy s viacerými výstupmi. Sú to veľmi výkonné algoritmy, schopné zmestiť zložité súbory údajov.

Rozhodovací strom je stromová štruktúra podobná vývojovému diagramu, kde vnútorný node predstavuje vlastnosť (alebo atribút), vetva predstavuje rozhodovacie pravidlo a každý listový uzol predstavuje výsledok.

Najvyšší uzol v rozhodovacom strome je známy ako koreňový uzol. Učí sa rozdeľovať na základe hodnoty atribútu. Rozdeľuje strom rekurzívnym spôsobom, ktorý sa nazýva rekurzívne rozdelenie. Táto štruktúra podobná vývojovému diagramu vám pomôže pri rozhodovaní. Je to vizualizácia ako vývojový diagram, ktorý ľahko napodobňuje myslenie na ľudskej úrovni. Preto sú rozhodovacie stromy ľahko pochopiteľné a interpretovateľné.

Rozhodovací strom je typ algoritmu strojového učenia s bielou skrinkou. Zdieľa internú rozhodovaciu logiku, ktorá nie je dostupná v algoritmoch typu čiernej skrinky, napríklad v neurónovej sieti. Jeho trénovací čas je v porovnaní s algoritmom neurónovej siete rýchlejší.

Časová náročnosť rozhodovacích stromov je funkciou počtu záznamov a atribútov v daných údajoch. Rozhodovací strom je bezdistribučná alebo neparametrická metóda, ktorá nezávisí od predpokladov rozdelenia pravdepodobnosti. Rozhodovacie stromy dokážu spracovať vysokorozmerné údaje s dobrou presnosťou.

Ako funguje algoritmus rozhodovacieho stromu?

Základná myšlienka každého algoritmu rozhodovacieho stromu je nasledovná:

  1. Vyberte najlepší atribút pomocou mier výberu atribútov (ASM) na rozdelenie záznamov.
  2. Urobte z tohto atribútu rozhodovací uzol a rozdeľte množinu údajov na menšie podmnožiny.
  3. Začnite budovanie stromu rekurzívnym opakovaním tohto procesu pre každé dieťa, kým sa nezhoduje jedna z podmienok:
    • Všetky n-tice patria k rovnakej hodnote atribútu.
    • Už nezostávajú žiadne atribúty.
    • Už nie sú žiadne prípady.

Miery výberu atribútov

Miera výberu atribútu je heuristika na výber kritéria rozdelenia, ktoré rozdeľuje údaje najlepším možným spôsobom. Je tiež známy ako pravidlá rozdelenia, pretože nám pomáha určiť body prerušenia pre n-tice v danom uzle. ASM poskytuje poradie každej funkcii (alebo atribútu) vysvetlením daného súboru údajov. Atribút najlepšieho skóre bude vybraný ako atribút rozdelenia. V prípade atribútu s spojitou hodnotou je potrebné definovať aj body rozdelenia pre vetvy. Najpopulárnejšími výberovými mierami sú Information Gain, Gain Ratio a Gini Index.

Získanie informácií

Claude Shannon vynašiel koncept entropie, ktorý meria nečistotu vstupnej množiny. Vo fyzike a matematike sa entropia označuje ako náhodnosť alebo nečistota v systéme. V teórii informácie sa vzťahuje na nečistotu v skupine príkladov. Informačný zisk je pokles entropie. Získanie informácií vypočíta rozdiel medzi entropiou pred rozdelením a priemernou entropiou po rozdelení množiny údajov na základe daných hodnôt atribútov. Algoritmus rozhodovacieho stromu ID3 (Iterative Dichotomiser) využíva zisk informácií.

\( Info(D)=-\sum\limits_{i=1}^{m} pi \cdot log_2 pi \)

Kde Pi je pravdepodobnosť, že ľubovoľná n-tica v D patrí do triedy Ci.

\( Info_A(D)=\sum\limits_{j=1}^{V} \frac{|{ Dj|}}{|D|}X Info(D_j) \)

\( Zisk(A)=Info(D)-Info_A(D) \)

Kde:

  • Info(D) je priemerné množstvo informácií potrebných na identifikáciu štítku triedy n-tice v D.
  • |Dj|/|D| Pôsobí ako hmotnosť J-tého oddielu.
  • InfoA(D) je očakávaná informácia potrebná na klasifikáciu n-tice z D na základe rozdelenia A.

Atribút A s najvyšším ziskom informácií, Gain(A), je zvolený ako atribút rozdelenia v uzle N().

Pomer zisku

Získavanie informácií je pre atribút skreslené s mnohými výsledkami. To znamená, že uprednostňuje atribút s veľkým počtom odlišných hodnôt. Predstavte si napríklad atribút s jedinečným identifikátorom, ako napríklad customer_ID, ktorý má nulové info(D) kvôli čistej oblasti. To maximalizuje získanie informácií a vytvára zbytočné rozdelenie.

C4.5, vylepšenie ID3, používa rozšírenie získania informácií známe ako pomer zisku. Pomer zisku rieši problém zaujatosti normalizáciou získavania informácií pomocou Split Info. Java implementácia algoritmu C4.5 je známa ako J48, ktorý je k dispozícii v nástroji na dolovanie údajov WEKA.

\( SplitInfo_A(D)=-\sum\limits_{j=1}^{V} \frac{|{ Dj|}}{|D|} \times log_2(\frac{|{ Dj|}}{|D|}) \)

Kde:

  • \( \frac{|D_j|}{|D|} \) funguje ako váha j-tého oddielu.
  • v je počet diskrétnych hodnôt v atribúte A.

Pomer zosilnenia možno definovať ako

\( GainRatio(A)=\frac{Gain(A)}{SplitInfo_A(D)} \)

Atribút s najvyšším pomerom zisku je zvolený ako atribút rozdelenia (Zdroj).

Giniho index

Ďalší algoritmus rozhodovacieho stromu CART (Classification and Regression Tree) používa Giniho metódu na vytvorenie bodov rozdelenia.

\( Gini(D)=1-\sum\limits_{i=1}^{m} Pi^2 \)

Kde pi je pravdepodobnosť, že n-tica v D patrí do triedy Ci.

Giniho index zohľadňuje binárne rozdelenie pre každý atribút. Môžete vypočítať vážený súčet nečistôt každej oblasti. Ak binárne rozdelenie atribútu A rozdelí údaje D na D1 a D2, Giniho index D je:

\( Gini_A(D)=\frac{|{ D_1|}}{|D|}Gini(D_1)+\frac{|{ D2|}}{|D|}Gini(D_2) \)

V prípade atribútu s diskrétnou hodnotou sa ako atribút rozdelenia vyberie podmnožina, ktorá poskytuje minimálny gini index pre vybraný atribút. V prípade atribútov s spojitou hodnotou je stratégiou vybrať každú dvojicu susediacich hodnôt ako možný bod rozdelenia a bod s menším gini indexom je zvolený ako bod rozdelenia.

\( \Delta Gini(A)=Gini(D)-Gini_A(D) \)

Ako atribút rozdelenia je zvolený atribút s minimálnym Giniho indexom.

Budova klasifikátora rozhodovacieho stromu v Scikit-learn

Import požadovaných knižníc

Najprv načítajme požadované knižnice.

# Load libraries
import pandas as pd
from sklearn.tree import DecisionTreeClassifier # Import Decision Tree Classifier
from sklearn.model_selection import train_test_split # Import train_test_split function
from sklearn import metrics #Import scikit-learn metrics module for accuracy calculation

Načítanie údajov

Najprv načítajme požadovanú množinu údajov Pima Indian Diabetes pomocou funkcie CSV čítania pand. Môžete si stiahnuť Kaggle data set a sledovať.

col_names = ['pregnant', 'glucose', 'bp', 'skin', 'insulin', 'bmi', 'pedigree', 'age', 'label']
# load dataset
pima = pd.read_csv("diabetes.csv", header=None, names=col_names)

pima.head()
  pregnant glucose bp skin insulin bmi pedigree age label
0 6 148 72 35 0 33.6 0.627 50 1
1 1 85 66 29 0 26.6 0.351 31 0
2 8 183 64 0 0 23.3 0.672 32 1
3 1 89 66 23 94 28.1 0.167 21 0
4 0 137 40 35 168 43.1 2.288 33 1

Výber funkcií

Ak chcete pochopiť výkon modelu, dobrou stratégiou je rozdelenie množiny údajov na trénovaciu množinu a testovaciu množinu.

Rozdeľme množinu údajov pomocou funkcie train_test_split(). Musíte odovzdať tri parametre; cieľ a test_set veľkosť.

# Rozdelenie množiny údajov na trénovaciu množinu a testovaciu množinu
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=1) # 70% training and 30% test

Building Decision Tree Model

# Create Decision Tree classifer object
clf = DecisionTreeClassifier()

# Train Decision Tree Classifer
clf = clf.fit(X_train,y_train)

#Predict the response for test dataset
y_pred = clf.predict(X_test)

Evaluating the Model

Odhadnime, ako presne môže klasifikátor alebo model predpovedať typ kultivarov.

Presnosť je možné vypočítať porovnaním skutočných hodnôt testovacích súborov a predpokladaných hodnôt.

# Model Accuracy, how often is the classifier correct?
print("Accuracy:",metrics.accuracy_score(y_test, y_pred))
Accuracy: 0.6753246753246753

Dostali sme mieru klasifikácie 67,53%, čo sa považuje za dobrú presnosť. Túto presnosť môžete zlepšiť vyladením parametrov v algoritme rozhodovacieho stromu.

Vizualizácia rozhodovacích stromov

Funkciu export_graphviz Scikit-learn môžete použiť  na zobrazenie stromu v poznámkovom bloku Jupyter. Na vykreslenie stromu je tiež potrebné nainštalovať graphviz a pydotplus.

pip install graphviz

pip install pydotplus

Funkcia export_graphviz konvertuje klasifikátor rozhodovacieho stromu na bodkový súbor a pydotplus konvertuje tento bodový súbor na png alebo zobraziteľný tvar na Jupyter.

from sklearn.tree import export_graphviz
from sklearn.externals.six import StringIO  
from IPython.display import Image  
import pydotplus

dot_data = StringIO()
export_graphviz(clf, out_file=dot_data,  
                filled=True, rounded=True,
                special_characters=True,feature_names = feature_cols,class_names=['0','1'])
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())  
graph.write_png('diabetes.png')
Image(graph.create_png())
 
Visualizing Decision Trees

V grafe rozhodovacieho stromu má každý interný uzol rozhodovacie pravidlo, ktoré rozdeľuje údaje. Gini, označovaný ako Giniho pomer, meria nečistotu uzla. Môžete povedať, že uzol je čistý, keď všetky jeho záznamy patria do rovnakej triedy, takéto uzly sú známe ako listový uzol.

Tu je výsledný strom neorezaný. Tento neorezaný strom je nevysvetliteľný a nie je ľahké ho pochopiť. V ďalšej časti ho optimalizujme prerezávaním.

Optimalizácia výkonu rozhodovacieho stromu

  • criterion : voliteľné (default="gini") alebo Vybrať mierku výberu atribútov. Tento parameter nám umožňuje použiť mierku výberu atribútov rôzno-odlišný. Podporované kritériá sú "gini" pre Giniho index a "entropia" pre informačný zisk.
  • rozdeľovač : reťazec, voliteľný (predvolený = "najlepší") alebo stratégia rozdelenia. Tento parameter nám umožňuje zvoliť stratégiu rozdelenia. Podporované stratégie sú "najlepšie" na výber najlepšieho rozdelenia a "náhodné" na výber najlepšieho náhodného rozdelenia.
  • max_depth : int alebo None, voliteľné (default=None) alebo Maximálna hĺbka stromu. Maximálna hĺbka stromu. Ak Žiadne, uzly sa rozširujú, až kým všetky listy neobsahujú menej ako min_samples_split vzoriek. Vyššia hodnota maximálnej hĺbky spôsobuje nadmerné prispôsobenie a nižšia hodnota spôsobuje nedostatočné prispôsobenie (Zdroj).

V Scikit-learn optimalizácia klasifikátora rozhodovacieho stromu sa vykonáva iba predbežným prerezávaním. Maximálnu hĺbku stromu je možné použiť ako kontrolnú premennú pre predrez. V nasledujúcom príklade môžete vykresliť rozhodovací strom na rovnakých údajoch s max_depth=3. Okrem parametrov pred prerezávaním môžete vyskúšať aj inú mieru výberu atribútov, ako je entropia.

# Create Decision Tree classifer object
clf = DecisionTreeClassifier(criterion="entropy", max_depth=3)

# Train Decision Tree Classifer
clf = clf.fit(X_train,y_train)

#Predict the response for test dataset
y_pred = clf.predict(X_test)

# Model Accuracy, how often is the classifier correct?
print("Accuracy:",metrics.accuracy_score(y_test, y_pred))
Accuracy: 0.7705627705627706

Miera klasifikácie sa zvýšila na 77,05%, čo je lepšia presnosť ako predchádzajúci model.

Vizualizácia rozhodovacích stromov

Urobme náš rozhodovací strom trochu ľahším na pochopenie pomocou nasledujúceho kódu:

from six import StringIO from IPython.display import Image  
from sklearn.tree import export_graphviz
import pydotplus
dot_data = StringIO()
export_graphviz(clf, out_file=dot_data,  
                filled=True, rounded=True,
                special_characters=True, feature_names = feature_cols,class_names=['0','1'])
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())  
graph.write_png('diabetes.png')
Image(graph.create_png())

Tu sme vykonali nasledujúce kroky:

  • Importovali sme požadované knižnice.
  • Vytvorený objekt StringIO s názvom dot_data na uloženie textovej reprezentácie rozhodovacieho stromu.
  • Exportoval rozhodovací strom do dot formátu pomocou funkcie export_graphviz a zapísal výstup do vyrovnávacej pamäte dot_data.
  • Vytvorený objekt grafu pydotplus z reprezentácie bodkového formátu rozhodovacieho stromu uloženého vo vyrovnávacej pamäti dot_data.
  • Vygenerovaný graf zapísal do súboru PNG s názvom "diabetes.png".
  • Zobrazenie vygenerovaného obrázka PNG rozhodovacieho stromu pomocou objektu Image z modulu IPython.display.Visualizing Decision Trees

Ako vidíte, tento orezaný model je menej zložitý, vysvetliteľnejší a ľahšie pochopiteľný ako predchádzajúci graf modelu rozhodovacieho stromu.

Výhody rozhodovacieho stromu

  • Rozhodovacie stromy sa dajú ľahko interpretovať a vizualizovať.
  • Dokáže ľahko zachytiť nelineárne vzory.
  • Vyžaduje to menej predbežného spracovania údajov od používateľa, napríklad nie je potrebné normalizovať stĺpce.
  • Môže byť použitý na inžinierstvo funkcií, ako je predpovedanie chýbajúcich hodnôt, vhodné pre výber premenných.
  • Rozhodovací strom nemá žiadne predpoklady o distribúcii kvôli neparametrickej povahe algoritmu. (Zdroj)

Nevýhody rozhodovacieho stromu

  • Citlivý na zašumené údaje. Môže prekonať hlučné údaje.
  • Malá odchýlka (alebo rozptyl) v údajoch môže mať za následok odlišný rozhodovací strom. To sa dá znížiť vrecovaním a posilňovaním algoritmov.
  • Rozhodovacie stromy sú skreslené množinou údajov o nerovnováhe, preto sa odporúča pred vytvorením rozhodovacieho stromu množinu údajov vyvážiť.
Last modified: Sunday, 23 March 2025, 7:41 AM