logo

Decision Tree Classification Algoritme

  • Decision Tree er en Veiledet læringsteknikk som kan brukes til både klassifiserings- og regresjonsproblemer, men foretrekkes for det meste for å løse klassifikasjonsproblemer. Det er en trestrukturert klassifisering, hvor interne noder representerer egenskapene til et datasett, grener representerer beslutningsreglene og hver bladnode representerer resultatet.
  • I et beslutningstre er det to noder, som er Beslutningsknutepunkt og Bladknutepunkt. Beslutningsnoder brukes til å ta en avgjørelse og har flere grener, mens bladnoder er resultatet av disse avgjørelsene og ikke inneholder flere grener.
  • Beslutningene eller testen utføres på grunnlag av funksjoner i det gitte datasettet.
  • Det er en grafisk fremstilling for å få alle mulige løsninger på et problem/beslutning basert på gitte forhold.
  • Det kalles et beslutningstre fordi det, i likhet med et tre, starter med rotnoden, som utvider seg på ytterligere grener og konstruerer en trelignende struktur.
  • For å bygge et tre bruker vi CART-algoritme, som står for Klassifiserings- og regresjonstre-algoritme.
  • Et beslutningstre stiller ganske enkelt et spørsmål, og basert på svaret (Ja/Nei) deler det treet ytterligere i undertrær.
  • Diagrammet nedenfor forklarer den generelle strukturen til et beslutningstre:

Merk: Et beslutningstre kan inneholde kategoriske data (JA/NEI) så vel som numeriske data.

Algorithm for klassifisering av beslutningstre

Hvorfor bruke Decision Trees?

Det finnes forskjellige algoritmer i maskinlæring, så å velge den beste algoritmen for det gitte datasettet og problemet er hovedpoenget å huske når du lager en maskinlæringsmodell. Nedenfor er de to grunnene til å bruke beslutningstreet:

  • Beslutningstrær etterligner vanligvis menneskelig tenkeevne mens de tar en beslutning, så det er lett å forstå.
  • Logikken bak beslutningstreet kan lett forstås fordi det viser en trelignende struktur.

Beslutningstreterminologier

Rotnode:Rotnoden er der beslutningstreet starter. Det representerer hele datasettet, som videre blir delt inn i to eller flere homogene sett.Bladknutepunkt:Bladnoder er den endelige utgangsnoden, og treet kan ikke segregeres ytterligere etter å ha fått en bladnode.Splitting:Splitting er prosessen med å dele opp beslutningsnoden/rotnoden i undernoder i henhold til de gitte betingelsene.Gren/undertre:Et tre dannet ved å splitte treet.Beskjæring:Beskjæring er prosessen med å fjerne uønskede grener fra treet.Foreldre/barn node:Rotnoden til treet kalles overordnet node, og andre noder kalles undernodene.

Hvordan fungerer beslutningstre-algoritmen?

I et beslutningstre, for å forutsi klassen til det gitte datasettet, starter algoritmen fra rotnoden til treet. Denne algoritmen sammenligner verdiene til rotattributtet med attributtet record (reelt datasett) og, basert på sammenligningen, følger grenen og hopper til neste node.

For neste node sammenligner algoritmen igjen attributtverdien med de andre undernodene og går videre. Den fortsetter prosessen til den når bladnoden til treet. Hele prosessen kan forstås bedre ved å bruke algoritmen nedenfor:

    Trinn 1:Begynn treet med rotnoden, sier S, som inneholder hele datasettet.Steg 2:Finn det beste attributtet i datasettet ved å bruke Attribut Selection Measure (ASM). Trinn-3:Del S i delsett som inneholder mulige verdier for de beste egenskapene.Trinn-4:Generer beslutningstre-noden, som inneholder det beste attributtet.Trinn-5:Lag nye beslutningstrær rekursivt ved å bruke delsettene til datasettet opprettet i trinn -3. Fortsett denne prosessen til et stadium er nådd hvor du ikke kan klassifisere nodene ytterligere og kalles den endelige noden som en bladnode.

Eksempel: Tenk deg at det er en kandidat som har et jobbtilbud og ønsker å bestemme om han skal akseptere tilbudet eller ikke. Så for å løse dette problemet starter beslutningstreet med rotnoden (lønnsattributt av ASM). Rotnoden deler seg videre i neste beslutningsnode (avstand fra kontoret) og en bladnode basert på de tilsvarende etikettene. Den neste beslutningsnoden deles videre i en beslutningsnode (Cab facility) og en bladnode. Til slutt deles beslutningsnoden i to bladnoder (aksepterte tilbud og avslått tilbud). Tenk på diagrammet nedenfor:

Algorithm for klassifisering av beslutningstre

Tiltak for attributtvalg

Når du implementerer et beslutningstre, oppstår hovedproblemet hvordan du velger det beste attributtet for rotnoden og undernodene. Så for å løse slike problemer er det en teknikk som kalles som Attributtvalgsmål eller ASM. Ved denne målingen kan vi enkelt velge det beste attributtet for nodene til treet. Det er to populære teknikker for ASM, som er:

    Informasjonsgevinst Gini-indeksen

1. Informasjonsgevinst:

  • Informasjonsgevinst er måling av endringer i entropi etter segmentering av et datasett basert på et attributt.
  • Den beregner hvor mye informasjon en funksjon gir oss om en klasse.
  • I henhold til verdien av informasjonsgevinst deler vi noden og bygger beslutningstreet.
  • En beslutningstrealgoritme prøver alltid å maksimere verdien av informasjonsgevinst, og en node/attributt som har den høyeste informasjonsgevinsten deles først. Det kan beregnes ved å bruke formelen nedenfor:
 Information Gain= Entropy(S)- [(Weighted Avg) *Entropy(each feature) 

Entropi: Entropi er en beregning for å måle urenheten i en gitt attributt. Den spesifiserer tilfeldighet i data. Entropi kan beregnes som:

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

Hvor,

    S= Totalt antall prøver P(ja)= sannsynlighet for ja P(no)= sannsynlighet for nei

2. Gini-indeks:

  • Gini-indeksen er et mål på urenhet eller renhet som brukes mens du oppretter et beslutningstre i CART(Classification and Regression Tree)-algoritmen.
  • Et attributt med lav Gini-indeks bør foretrekkes sammenlignet med høy Gini-indeks.
  • Den lager bare binære splittelser, og CART-algoritmen bruker Gini-indeksen til å lage binære splittelser.
  • Gini-indeksen kan beregnes ved å bruke formelen nedenfor:
 Gini Index= 1- &#x2211;<sub>j</sub>P<sub>j</sub><sup>2</sup> 

Beskjæring: Få et optimalt beslutningstre

Beskjæring er en prosess med å slette unødvendige noder fra et tre for å få det optimale beslutningstreet.

Et for stort tre øker risikoen for overtilpasning, og et lite tre fanger kanskje ikke opp alle de viktige egenskapene til datasettet. Derfor er en teknikk som reduserer størrelsen på læringstreet uten å redusere nøyaktigheten kjent som beskjæring. Det er hovedsakelig to typer tre beskjæring teknologi som brukes:

    Kostnadskompleksitet Beskjæring Redusert feilbeskjæring.

Fordeler med beslutningstreet

  • Det er enkelt å forstå ettersom det følger den samme prosessen som et menneske følger mens de tar en avgjørelse i det virkelige liv.
  • Det kan være svært nyttig for å løse beslutningsrelaterte problemer.
  • Det hjelper å tenke på alle mulige utfall for et problem.
  • Det er mindre krav til datarensing sammenlignet med andre algoritmer.

Ulemper med beslutningstreet

  • Beslutningstreet inneholder mange lag, noe som gjør det komplekst.
  • Det kan ha et overmonteringsproblem, som kan løses ved hjelp av Random Forest-algoritme.
  • For flere klasseetiketter kan den beregningsmessige kompleksiteten til beslutningstreet øke.

Python-implementering av beslutningstreet

Nå skal vi implementere beslutningstreet ved hjelp av Python. For dette vil vi bruke datasettet ' user_data.csv ,' som vi har brukt i tidligere klassifiseringsmodeller. Ved å bruke samme datasett kan vi sammenligne Decision tree klassifikatoren med andre klassifikasjonsmodeller som f.eks KNN SVM, Logistisk regresjon, etc.

Trinnene vil også forbli de samme, som er gitt nedenfor:

    Dataforbehandlingstrinn Tilpasning av en beslutningstre-algoritme til treningssettet Forutsi testresultatet Test nøyaktigheten av resultatet (oppretting av forvirringsmatrise) Visualisere testsettets resultat.

1. Dataforbehandlingstrinn:

Nedenfor er koden for forhåndsbehandlingstrinnet:

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

I koden ovenfor har vi forhåndsbehandlet dataene. Hvor vi har lastet inn datasettet, som er gitt som:

Decision Tree Classification Algoritme

2. Tilpasning av en beslutningstre-algoritme til treningssettet

Nå skal vi tilpasse modellen til treningssettet. For dette vil vi importere DecisionTreeClassifier klasse fra sklearn.tree bibliotek. Nedenfor er koden for det:

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

I koden ovenfor har vi laget et klassifiseringsobjekt, der vi har sendt to hovedparametere;

    'criterion='entropi':Kriterium brukes til å måle kvaliteten på splittelsen, som beregnes av informasjonsgevinst gitt av entropi.random_state=0':For å generere tilfeldige tilstander.

Nedenfor er utgangen for dette:

 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. Forutsi testresultatet

Nå vil vi forutsi testsettets resultat. Vi vil lage en ny prediksjonsvektor y_pred. Nedenfor er koden for det:

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

Produksjon:

I utdatabildet nedenfor er anslått utgang og reell testutgang gitt. Vi kan tydelig se at det er noen verdier i prediksjonsvektoren, som er forskjellige fra de virkelige vektorverdiene. Dette er prediksjonsfeil.

Decision Tree Classification Algoritme

4. Test nøyaktigheten av resultatet (oppretting av forvirringsmatrise)

I utgangen ovenfor har vi sett at det var noen feil spådommer, så hvis vi vil vite antall riktige og feil prediksjoner, må vi bruke forvirringsmatrisen. Nedenfor er koden for det:

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

Produksjon:

Decision Tree Classification Algoritme

I utdatabildet ovenfor kan vi se forvirringsmatrisen, som har 6+3= 9 feil spådommer og 62+29=91 riktige spådommer. Derfor kan vi si at sammenlignet med andre klassifiseringsmodeller gjorde Decision Tree-klassifikatoren en god prediksjon.

5. Visualisere resultatet av treningssettet:

Her skal vi visualisere treningssettets resultat. For å visualisere resultatet av treningssettet vil vi plotte en graf for beslutningstreklassifikatoren. Klassifisereren vil forutsi ja eller nei for brukerne som enten har kjøpt eller ikke kjøpt SUV-bilen slik vi gjorde i Logistic Regression. Nedenfor er koden for det:

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

Produksjon:

Algorithm for klassifisering av beslutningstre

Ovennevnte utgang er helt forskjellig fra resten av klassifiseringsmodellene. Den har både vertikale og horisontale linjer som deler opp datasettet i henhold til alder og estimert lønnsvariabel.

Som vi kan se, prøver treet å fange opp hvert datasett, som er tilfellet med overtilpasning.

6. Visualisere testsettets resultat:

Visualisering av testsettets resultat vil være lik visualiseringen av treningssettet bortsett fra at treningssettet vil bli erstattet med testsettet.

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

Produksjon:

Algorithm for klassifisering av beslutningstre

Som vi kan se i bildet ovenfor, er det noen grønne datapunkter i den lilla regionen og omvendt. Så dette er de uriktige spådommene som vi har diskutert i forvirringsmatrisen.