logo

Algoritmus klasifikácie rozhodovacieho stromu

  • Rozhodovací strom je a Technika učenia pod dohľadom ktorý možno použiť pre klasifikačné aj regresné problémy, ale väčšinou sa uprednostňuje pri riešení klasifikačných problémov. Ide o stromovo štruktúrovaný klasifikátor, kde interné uzly predstavujú vlastnosti súboru údajov, vetvy predstavujú pravidlá rozhodovania a každý listový uzol predstavuje výsledok.
  • V rozhodovacom strome sú dva uzly, ktorými sú Rozhodovací uzol a Listový uzol. Rozhodovacie uzly sa používajú na prijímanie akéhokoľvek rozhodnutia a majú viacero vetiev, zatiaľ čo uzly Leaf sú výstupom týchto rozhodnutí a neobsahujú žiadne ďalšie vetvy.
  • Rozhodnutia alebo test sa vykonávajú na základe vlastností daného súboru údajov.
  • Je to grafické znázornenie na získanie všetkých možných riešení problému/rozhodnutia na základe daných podmienok.
  • Nazýva sa rozhodovací strom, pretože podobne ako strom začína koreňovým uzlom, ktorý sa rozširuje o ďalšie vetvy a vytvára štruktúru podobnú stromu.
  • Na stavbu stromu používame algoritmus CART, čo znamená Algoritmus klasifikačného a regresného stromu.
  • Rozhodovací strom jednoducho položí otázku a na základe odpovede (Áno/Nie) ďalej rozdeľuje strom na podstromy.
  • Nižšie uvedený diagram vysvetľuje všeobecnú štruktúru rozhodovacieho stromu:

Poznámka: Rozhodovací strom môže obsahovať kategorické údaje (ÁNO/NIE), ako aj číselné údaje.

Algoritmus klasifikácie rozhodovacieho stromu

Prečo používať rozhodovacie stromy?

V strojovom učení existujú rôzne algoritmy, takže výber najlepšieho algoritmu pre daný súbor údajov a problém je hlavným bodom, na ktorý treba pamätať pri vytváraní modelu strojového učenia. Nižšie sú uvedené dva dôvody na použitie rozhodovacieho stromu:

  • Rozhodovacie stromy zvyčajne napodobňujú schopnosť ľudského myslenia pri rozhodovaní, takže je ľahké ich pochopiť.
  • Logiku rozhodovacieho stromu možno ľahko pochopiť, pretože zobrazuje štruktúru podobnú stromu.

Terminológie rozhodovacieho stromu

Koreňový uzol:Koreňový uzol je miesto, kde začína rozhodovací strom. Predstavuje celý súbor údajov, ktorý sa ďalej delí na dva alebo viac homogénnych súborov.Listový uzol:Listové uzly sú konečným výstupným uzlom a strom po získaní listového uzla nemožno ďalej segregovať.Rozdelenie:Rozdelenie je proces rozdelenia rozhodovacieho uzla/koreňového uzla na poduzly podľa daných podmienok.Vetva/podstrom:Strom vytvorený rozštiepením stromu.Prerezávanie:Prerezávanie je proces odstraňovania nežiaducich konárov zo stromu.Rodičovský/podradený uzol:Koreňový uzol stromu sa nazýva rodičovský uzol a ostatné uzly sa nazývajú podriadené uzly.

Ako funguje algoritmus rozhodovacieho stromu?

parciálny derivát latexu

V rozhodovacom strome na predpovedanie triedy daného súboru údajov začína algoritmus od koreňového uzla stromu. Tento algoritmus porovnáva hodnoty koreňového atribútu s atribútom záznamu (reálnej množiny údajov) a na základe porovnania sleduje vetvu a skočí na ďalší uzol.

Pre ďalší uzol algoritmus opäť porovná hodnotu atribútu s ostatnými poduzlami a posunie sa ďalej. Pokračuje v procese, kým nedosiahne listový uzol stromu. Celý proces možno lepšie pochopiť pomocou nižšie uvedeného algoritmu:

    Krok 1:Začnite strom s koreňovým uzlom, hovorí S, ktorý obsahuje kompletný súbor údajov.Krok 2:Nájdite najlepší atribút v množine údajov pomocou Meranie výberu atribútov (ASM). Krok 3:Rozdeľte S do podmnožín, ktoré obsahujú možné hodnoty pre najlepšie atribúty.Krok 4:Vygenerujte uzol rozhodovacieho stromu, ktorý obsahuje najlepší atribút.Krok 5:Rekurzívne vytvorte nové rozhodovacie stromy pomocou podmnožín množiny údajov vytvorenej v kroku -3. Pokračujte v tomto procese, kým sa nedosiahne štádium, v ktorom nemôžete ďalej klasifikovať uzly a nazvaný konečný uzol ako listový uzol.

Príklad: Predpokladajme, že existuje kandidát, ktorý má pracovnú ponuku a chce sa rozhodnúť, či má ponuku prijať alebo nie. Aby sa tento problém vyriešil, rozhodovací strom začína koreňovým uzlom (atribút Plat podľa ASM). Koreňový uzol sa ďalej delí na nasledujúci rozhodovací uzol (vzdialenosť od kancelárie) a jeden listový uzol na základe zodpovedajúcich označení. Ďalší rozhodovací uzol sa ďalej rozdelí na jeden rozhodovací uzol (zariadenie kabíny) a jeden listový uzol. Nakoniec sa rozhodovací uzol rozdelí na dva listové uzly (Akceptované ponuky a Odmietnutá ponuka). Zvážte nasledujúci diagram:

Algoritmus klasifikácie rozhodovacieho stromu

Opatrenia na výber atribútov

Pri implementácii rozhodovacieho stromu vzniká hlavný problém, ako vybrať najlepší atribút pre koreňový uzol a pre poduzly. Takže na vyriešenie takýchto problémov existuje technika, ktorá sa nazýva ako Miera výberu atribútu alebo ASM. Týmto meraním môžeme ľahko vybrať najlepší atribút pre uzly stromu. Existujú dve populárne techniky pre ASM, ktoré sú:

    Zisk informácií Giniho index

1. Získanie informácií:

  • Informačný zisk je meranie zmien entropie po segmentácii súboru údajov na základe atribútu.
  • Vypočítava, koľko informácií nám funkcia poskytuje o triede.
  • Podľa hodnoty zisku informácií rozdelíme uzol a zostavíme rozhodovací strom.
  • Algoritmus rozhodovacieho stromu sa vždy snaží maximalizovať hodnotu informačného zisku a uzol/atribút s najvyšším informačným ziskom je rozdelený ako prvý. Dá sa vypočítať pomocou nasledujúceho vzorca:
 Information Gain= Entropy(S)- [(Weighted Avg) *Entropy(each feature) 

Entropia: Entropia je metrika na meranie nečistoty v danom atribúte. Špecifikuje náhodnosť v údajoch. Entropiu možno vypočítať takto:

Entropy(s)= -P(yes)log2 P(yes)- P(no) log2 P(no)

Kde,

    S= Celkový počet vzoriek P(áno)=pravdepodobnosť áno P(no)= pravdepodobnosť nie

2. Gini index:

  • Gini index je miera nečistoty alebo čistoty používaná pri vytváraní rozhodovacieho stromu v algoritme CART (Klasifikačný a regresný strom).
  • Atribút s nízkym Gini indexom by mal byť preferovaný v porovnaní s vysokým Gini indexom.
  • Vytvára iba binárne delenia a algoritmus CART používa Gini index na vytváranie binárnych delení.
  • Gini index možno vypočítať pomocou nasledujúceho vzorca:
 Gini Index= 1- &#x2211;<sub>j</sub>P<sub>j</sub><sup>2</sup> 

Prerezávanie: Získanie stromu optimálneho rozhodovania

Prerezávanie je proces odstraňovania nepotrebných uzlov zo stromu, aby sa získal optimálny rozhodovací strom.

Príliš veľký strom zvyšuje riziko nadmerného vybavenia a malý strom nemusí zachytiť všetky dôležité vlastnosti súboru údajov. Preto je technika, ktorá zmenšuje veľkosť učiaceho sa stromu bez zníženia presnosti, známa ako prerezávanie. Existujú hlavne dva druhy stromov prerezávanie použitá technológia:

    Prerezávanie zložitosti nákladov Znížené orezávanie chýb.

Výhody rozhodovacieho stromu

  • Je to jednoduché na pochopenie, pretože ide o rovnaký proces, ktorý človek sleduje pri rozhodovaní v reálnom živote.
  • Môže to byť veľmi užitočné pri riešení problémov súvisiacich s rozhodovaním.
  • Pomáha premýšľať o všetkých možných dôsledkoch problému.
  • V porovnaní s inými algoritmami je potrebné menej čistiť dáta.

Nevýhody rozhodovacieho stromu

  • Rozhodovací strom obsahuje veľa vrstiev, čo ho robí zložitým.
  • Môže sa vyskytnúť problém s nadmernou montážou, ktorý sa dá vyriešiť pomocou Algoritmus náhodného lesa.
  • Pre viac označení tried sa môže zvýšiť výpočtová zložitosť rozhodovacieho stromu.

Implementácia rozhodovacieho stromu v Pythone

Teraz budeme implementovať strom rozhodovania pomocou Pythonu. Na tento účel použijeme súbor údajov ' user_data.csv “, ktorý sme použili v predchádzajúcich klasifikačných modeloch. Použitím rovnakého datasetu môžeme porovnať klasifikátor rozhodovacieho stromu s inými klasifikačnými modelmi ako napr KNN SVM, LogisticRegression atď.

Kroky zostanú rovnaké, ktoré sú uvedené nižšie:

    Krok predbežného spracovania údajov Prispôsobenie algoritmu rozhodovacieho stromu k množine tréningu Predpovedanie výsledku testu Otestujte presnosť výsledku (Vytvorenie matice zmätku) Vizualizácia výsledku testovacej súpravy.

1. Krok predbežného spracovania údajov:

Nižšie je uvedený kód pre krok predbežného spracovania:

 # importing libraries import numpy as nm import matplotlib.pyplot as mtp import pandas as pd #importing datasets data_set= pd.read_csv(&apos;user_data.csv&apos;) #Extracting Independent and dependent Variable x= data_set.iloc[:, [2,3]].values y= data_set.iloc[:, 4].values # Splitting the dataset into training and test set. from sklearn.model_selection import train_test_split x_train, x_test, y_train, y_test= train_test_split(x, y, test_size= 0.25, random_state=0) #feature Scaling from sklearn.preprocessing import StandardScaler st_x= StandardScaler() x_train= st_x.fit_transform(x_train) x_test= st_x.transform(x_test) 

Vo vyššie uvedenom kóde sme predspracovali údaje. Kde sme načítali súbor údajov, ktorý je uvedený ako:

Algoritmus klasifikácie rozhodovacieho stromu

2. Prispôsobenie algoritmu rozhodovacieho stromu do tréningovej množiny

Teraz model prispôsobíme tréningovej súprave. Za týmto účelom budeme importovať DecisionTreeClassifier triedy od sklearn.strom knižnica. Nižšie je uvedený kód:

 #Fitting Decision Tree classifier to the training set From sklearn.tree import DecisionTreeClassifier classifier= DecisionTreeClassifier(criterion=&apos;entropy&apos;, random_state=0) classifier.fit(x_train, y_train) 

Vo vyššie uvedenom kóde sme vytvorili objekt klasifikátora, do ktorého sme odovzdali dva hlavné parametre;

    'criterion='entropia':Kritérium sa používa na meranie kvality rozdelenia, ktoré sa vypočítava z informačného zisku daného entropiou.random_state=0':Na generovanie náhodných stavov.

Nižšie je uvedený výstup pre toto:

 Out[8]: DecisionTreeClassifier(class_weight=None, criterion=&apos;entropy&apos;, max_depth=None, max_features=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, min_samples_leaf=1, min_samples_split=2, min_weight_fraction_leaf=0.0, presort=False, random_state=0, splitter=&apos;best&apos;) 

3. Predpovedanie výsledku testu

Teraz predpovedáme výsledok testovacej sady. Vytvoríme nový vektor predikcie y_pred. Nižšie je uvedený kód:

 #Predicting the test set result y_pred= classifier.predict(x_test) 

Výkon:

Na výstupnom obrázku nižšie je uvedený predpokladaný výstup a skutočný testovací výstup. Jasne vidíme, že v predikčnom vektore sú niektoré hodnoty, ktoré sa líšia od skutočných vektorových hodnôt. Toto sú chyby predikcie.

java trieda matematiky
Algoritmus klasifikácie rozhodovacieho stromu

4. Otestujte presnosť výsledku (Creation of Confusion matrix)

Vo vyššie uvedenom výstupe sme videli, že tam boli niektoré nesprávne predpovede, takže ak chceme poznať počet správnych a nesprávnych predpovedí, musíme použiť maticu zmätku. Nižšie je uvedený kód:

 #Creating the Confusion matrix from sklearn.metrics import confusion_matrix cm= confusion_matrix(y_test, y_pred) 

Výkon:

Algoritmus klasifikácie rozhodovacieho stromu

Na vyššie uvedenom výstupnom obrázku môžeme vidieť maticu zmätku, ktorá má 6+3= 9 nesprávnych predpovedí a 62+29=91 správnych predpovedí. Preto môžeme povedať, že v porovnaní s inými klasifikačnými modelmi urobil klasifikátor Decision Tree dobrú predpoveď.

5. Vizualizácia výsledku tréningovej zostavy:

Tu budeme vizualizovať výsledok tréningovej zostavy. Na vizualizáciu výsledku tréningovej množiny nakreslíme graf pre klasifikátor rozhodovacieho stromu. Klasifikátor predpovedá áno alebo nie používateľom, ktorí si kúpili alebo nezakúpili vozidlo SUV, ako sme to urobili v prípade logistickej regresie. Nižšie je uvedený kód:

 #Visulaizing the trianing set result from matplotlib.colors import ListedColormap x_set, y_set = x_train, y_train x1, x2 = nm.meshgrid(nm.arange(start = x_set[:, 0].min() - 1, stop = x_set[:, 0].max() + 1, step =0.01), nm.arange(start = x_set[:, 1].min() - 1, stop = x_set[:, 1].max() + 1, step = 0.01)) mtp.contourf(x1, x2, classifier.predict(nm.array([x1.ravel(), x2.ravel()]).T).reshape(x1.shape), alpha = 0.75, cmap = ListedColormap((&apos;purple&apos;,&apos;green&apos; ))) mtp.xlim(x1.min(), x1.max()) mtp.ylim(x2.min(), x2.max()) fori, j in enumerate(nm.unique(y_set)): mtp.scatter(x_set[y_set == j, 0], x_set[y_set == j, 1], c = ListedColormap((&apos;purple&apos;, &apos;green&apos;))(i), label = j) mtp.title(&apos;Decision Tree Algorithm (Training set)&apos;) mtp.xlabel(&apos;Age&apos;) mtp.ylabel(&apos;Estimated Salary&apos;) mtp.legend() mtp.show() 

Výkon:

Algoritmus klasifikácie rozhodovacieho stromu

Vyššie uvedený výstup je úplne odlišný od ostatných klasifikačných modelov. Má zvislé aj vodorovné čiary, ktoré rozdeľujú súbor údajov podľa veku a odhadovanej platovej premennej.

Ako môžeme vidieť, strom sa snaží zachytiť každý súbor údajov, čo je prípad nadmerného vybavenia.

6. Vizualizácia výsledku testovacej súpravy:

Vizualizácia výsledku testovacej sady bude podobná vizualizácii tréningovej sady s tým rozdielom, že tréningová sada bude nahradená testovacou sadou.

 #Visulaizing the test set result from matplotlib.colors import ListedColormap x_set, y_set = x_test, y_test x1, x2 = nm.meshgrid(nm.arange(start = x_set[:, 0].min() - 1, stop = x_set[:, 0].max() + 1, step =0.01), nm.arange(start = x_set[:, 1].min() - 1, stop = x_set[:, 1].max() + 1, step = 0.01)) mtp.contourf(x1, x2, classifier.predict(nm.array([x1.ravel(), x2.ravel()]).T).reshape(x1.shape), alpha = 0.75, cmap = ListedColormap((&apos;purple&apos;,&apos;green&apos; ))) mtp.xlim(x1.min(), x1.max()) mtp.ylim(x2.min(), x2.max()) fori, j in enumerate(nm.unique(y_set)): mtp.scatter(x_set[y_set == j, 0], x_set[y_set == j, 1], c = ListedColormap((&apos;purple&apos;, &apos;green&apos;))(i), label = j) mtp.title(&apos;Decision Tree Algorithm(Test set)&apos;) mtp.xlabel(&apos;Age&apos;) mtp.ylabel(&apos;Estimated Salary&apos;) mtp.legend() mtp.show() 

Výkon:

Algoritmus klasifikácie rozhodovacieho stromu

Ako môžeme vidieť na obrázku vyššie, vo fialovej oblasti sú nejaké zelené dátové body a naopak. Takže toto sú nesprávne predpovede, o ktorých sme diskutovali v matici zmätku.