AIML-SR: 3.7 Stablo odlučivanja (Decision tree)

Stabla odlučivanja su svestrani algoritmi mašinskog učenja koji mogu obavljati i zadatke klasifikacije i regresije, pa čak i zadatke sa više izlaza. Oni su veoma moćni algoritmi, sposobni da uklope složene skupove podataka.

Stablo odlučivanja je struktura stabla nalik dijagramu toka gde unutrašnji čvor predstavlja funkciju (ili atribut), grana predstavlja pravilo odlučivanja, a svaki čvor lista predstavlja ishod.

Najviši čvor u stablu odlučivanja poznat je kao korenski čvor. Uči da deli na osnovu vrednosti atributa. On particioniše stablo na rekurzivni način koji se zove rekurzivna particija. Ova struktura nalik dijagramu toka pomaže vam u donošenju odluka. To je vizualizacija poput dijagrama toka koji lako oponaša razmišljanje na ljudskom nivou. Zato su stabla odlučivanja lako razumljiva i interpretirana.

Stablo odlučivanja je tip bele kutije ML algoritma. Deli unutrašnju logiku donošenja odluka, koja nije dostupna u algoritmima crne kutije, kao što je neuronska mreža. Vreme obuke je brže u poređenju sa algoritmom neuronske mreže.

Vremenska složenost stabala odlučivanja je funkcija broja zapisa i atributa u datim podacima. Stablo odlučivanja je distribucija bez ili ne-parametarski metod koji ne zavisi od pretpostavki distribucije verovatnoće. Stabla odlučivanja mogu da rukuju visokodimenzionalnim podacima sa dobrom preciznošću.

Kako funkcioniše algoritam stabla odlučivanja?

Osnovna ideja iza bilo kog algoritma stabla odlučivanja je sledeća:

Izaberite najbolji atribut koristeći Attribute Selection Measures (ASM) da biste podelili zapise.
Napravite taj atribut čvor odluke i razbija skup podataka u manje podskupove.
Započnite izgradnju stabla ponavljajući ovaj proces rekurzivno za svako dete dok se jedan od uslova ne podudara:

Sve torke pripadaju istoj vrednosti atributa.
Nema više preostalih atributa.
Nema više slučajeva.

Mere za izbor atributa

Mera izbora atributa je heuristika za odabir kriterijuma razdvajanja koji particionira podatke na najbolji mogući način. Poznat je i kao pravila razdvajanja jer nam pomaže da odredimo tačke prekida za torke na datom čvoru. ASM obezbeđuje rang za svaku funkciju (ili atribut) objašnjavajući datu skup podataka. Atribut najboljeg rezultata će biti izabran kao atribut razdvajanja . U slučaju atributa kontinuirane vrednosti, podelne tačke za grane takođe treba da definišu. Najpopularnije mere selekcije su informacije Dobitak, Gain Ratio, i Gini indeks.

Dobitak informacija

Claude Shannon je izmislio koncept entropije, koji meri nečistoću ulaznog skupa. U fizici i matematici, entropija se naziva slučajnost ili nečistoća u sistemu. U teoriji informacija, to se odnosi na nečistoću u grupi primera. Informacioni dobitak je smanjenje entropije. Dobitak informacija izračunava razliku između entropije pre podele i prosečne entropije nakon podele skupa podataka na osnovu datih vrednosti atributa. ID3 (Iterativni Dichotomiser) algoritam stabla odlučivanja koristi dobitak informacija.

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

Gde je Pi verovatnoća da proizvoljna torka u D pripada klasi Ci.

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

Gde:

Info(D) je prosečna količina informacija potrebnih za identifikaciju oznake klase torke u D.
|Dj|/|D| deluje kao težina JTH particije.
InfoA(D) je očekivana informacija potrebna za klasifikaciju torke od D na osnovu podele od strane A.

Atribut A sa najvećim dobitkom informacija, Gain(A), izabran je kao atribut razdvajanja na čvoru N().

Odnos pojačanja

Dobitak informacija je pristrasan za atribut sa mnogim ishodima. To znači da preferira atribut sa velikim brojem različitih vrednosti. Na primer, razmotrite atribut sa jedinstvenim identifikatorom, kao što je customer_ID, koji ima nula info(D) zbog čiste particije. Ovo maksimizira dobijanje informacija i stvara beskorisno particioniranje.

C4.5, poboljšanje ID3, koristi proširenje za dobijanje informacija poznato kao odnos dobitka. Gain odnos bavi pitanje pristrasnosti normalizacijom informacioni dobitak koristeći Split Info. Java implementacija C4.5 algoritma je poznat kao J48, koji je dostupan u VEKA rudarstvu podataka alat.

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

Gde:

\( \frac{|D_j|}{|D|} \) deluje kao težina J-te particije.
v je broj diskretnih vrednosti u atributu A.
Odnos pojačanja može se definisati kao

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

Atribut sa najvećim odnosom pojačanja je izabran kao atribut razdvajanja (Izvor).

Gini indeks

Još jedan algoritam stabla odlučivanja CART (Klasifikacija i regresijsko stablo) koristi Gini metod za kreiranje podelnih tačaka.

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

Gde je pi verovatnoća da torka u D pripada klasi Ci.

Gini indeks razmatra binarni podelu za svaki atribut. Možete izračunati ponderisanu sumu nečistoće svake particije. Ako binarna podela na atribut A podeljuje podatke D u D1 i D2, Gini indeks D je:

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

U slučaju atributa diskretne vrednosti, podskup koji daje minimalni gini indeks za taj izabrani je izabran kao atribut razdvajanja. U slučaju atributa kontinuirane vrednosti, strategija je da se svaki par susednih vrednosti izabere kao moguća tačka razdvajanja, a tačka sa manjim gini indeksom je izabrana kao tačka razdvajanja.

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

Atribut sa minimalnim Gini indeksom je izabran kao atribut razdvajanja.

Kreiranje klasifikatora stabla odlučivanja u Scikit-learn

Uvoz potrebnih biblioteka

Hajde da prvo učitamo potrebne biblioteke.

# 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

Učitavanje podataka

Hajde da prvo učitamo potreban Pima indijski dijabetes skup podataka koristeći pande 'čitati CSV funkciju. Možete preuzeti skup podataka Kaggle da biste pratili.

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

Izbor funkcija

Da bi razumeli performanse modela, podela skupa podataka u skup za obuku i test skup je dobra strategija.

Hajde da podelimo skup podataka pomoću funkcije train_test_split(). Potrebno je da prođe tri parametra funkcije; cilj, i test_set veličina.

# Split dataset into training set and test set
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

Kreiranje modela stabla odlučivanja

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

Evaluacija modela

Hajde da procenimo koliko tačno klasifikator ili model može da predvidi vrstu sorti.

Tačnost se može izračunati upoređivanjem stvarnih vrednosti testa i predviđenih vrednosti.

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

Accuracy: 0.6753246753246753

Dobili smo stopu klasifikacije od 67,53%, što se smatra dobrom tačnošću. Možete poboljšati ovu tačnost podešavanjem parametara u algoritmu stabla odlučivanja.

Vizualizacija stabala odlučivanja

Možete koristiti funkciju export_graphviz Scikit-learn za prikaz stabla u Jupiter notebooku. Za crtanje stabla, takođe morate da instalirate graphviz i pidotplus.

pip install graphviz

pip install pydotplus

Funkcija export_graphviz pretvara klasifikator stabla odlučivanja u tačkastu datoteku, a pidotplus pretvara ovu tačkastu datoteku u png ili prikazni oblik na Jupyter-u.

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

U grafikonu stabla odlučivanja, svaki unutrašnji čvor ima pravilo odluke koje deli podatke. Gini, koji se naziva Gini odnos, meri nečistoću čvora. Možete reći da je čvor čist kada svi njegovi zapisi pripadaju istoj klasi, takvi čvorovi poznati kao čvor lista.

Ovde, rezultujuće drvo je neorezano. Ovo neobrezano drvo je neobjašnjivo i nije lako razumeti. U sledećem odeljku, hajde da ga optimizujemo obrezivanjem.

Optimizacija performansi stabla odlučivanja

kriterijum : opciono (default = "gini") ili Izaberite meru za izbor atributa. Ovaj parametar nam omogućava da koristimo različitu meru izbora atributa. Podržani kriterijumi su "gini" za Gini indeks i "entropija" za dobijanje informacija.
splitter : string, opciono (default = "best") ili Split Strategi. Ovaj parametar nam omogućava da izaberemo strategiju razdvajanja. Podržane strategije su "najbolji" da izaberete najbolju podelu i "slučajno" da izaberete najbolju slučajnu podelu.
max_depth : int ili None, opciono (podrazumevano = Ništa) ili Maksimalna dubina stabla. Maksimalna dubina drveta. Ako nema, onda se čvorovi proširuju sve dok svi listovi ne sadrže manje od min_samples_split uzoraka. Veća vrednost maksimalne dubine izaziva overfitting, a niža vrednost izaziva underfitting (Izvor).

U Scikit-learn, optimizacija klasifikatora stabla odlučivanja vrši samo pre-rezidba. Maksimalna dubina stabla može se koristiti kao kontrolna varijabla za pred-orezivanje. U sledećem primeru, možete iscrtati stablo odlučivanja na istim podacima sa max_depth=3. Osim parametara pre orezivanja, Takođe možete probati i druge mere selekcije atributa, kao što je entropija.

# 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

Pa, stopa klasifikacije porasla je na 77,05%, što je bolja tačnost od prethodnog modela.

Vizualizacija stabala odlučivanja

Hajde da učinimo naše stablo odlučivanja malo lakšim za razumevanje pomoću sledećeg koda:

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

Ovde smo završili sledeće korake:

Uvezene potrebne biblioteke.
Kreiran StringIO objekat pod nazivom dot_data da drži tekstualnu reprezentaciju stabla odlučivanja.
Izvozi stablo odlučivanja u format tačke pomoću funkcije export_graphviz i upisivanje izlaza u bafer dot_data.
Kreiran je pitotplus graf objekat iz tačkastog formata reprezentacije stabla odlučivanja koje se čuva u dot_data baferu.
Napisao je generisani grafikon u PNG datoteku pod nazivom "diabetes.png".
Prikazana je generisana PNG slika stabla odlučivanja pomoću objekta Slika iz modula IPython.display.

Kao što vidite, ovaj orezani model je manje složen, objašnjiviji i lakši za razumevanje od prethodnog modela stabla odlučivanja.

Prednosti stable odlučivanja

Stabla odlučivanja su jednostavna za tumačenje i vizualizaciju.
Lako može da uhvati nelinearne obrasce.
To zahteva manje predobrade podataka od korisnika, na primer, nema potrebe za normalizacijom kolona.
Može se koristiti za inženjering karakteristika, kao što je predviđanje nedostajućih vrednosti, pogodnih za izbor varijabli.
Stablo odlučivanja nema pretpostavke o distribuciji zbog neparametarske prirode algoritma. (Izvor)

Mane stable odlučivanja

Osetljiv na bučne podatke. Može da pretera bučne podatke.
Mala varijacija (ili varijansa) u podacima može dovesti do različitog stabla odlučivanja. Ovo se može smanjiti pakovanjem i pojačavanjem algoritama.
Stabla odlučivanja su pristrasna sa skupom podataka neravnoteže, pa se preporučuje da se uravnoteži skup podataka pre kreiranja stabla odlučivanja.

Last modified: Saturday, 21 June 2025, 9:27 PM