Exemple de algoritmi de arborele decizional în exploatarea datelor

decision tree algorithm examples data mining

Acest tutorial detaliat explică totul despre algoritmul arborelui decizional în exploatarea datelor. Veți afla despre exemplele arborelui decizional, algoritm și clasificare:

Ne-am uitat la câteva Exemple de minerit de date în tutorialul nostru anterior din Seria gratuită de instruire în domeniul mineritului de date .

Minarea arborelui decizional este un tip de tehnică de extragere a datelor care este utilizată pentru a construi modele de clasificare. Construiește modele de clasificare sub forma unei structuri asemănătoare copacilor, la fel ca și numele său. Acest tip de minerit aparține învățării claselor supravegheate.

În învățarea supravegheată, rezultatul țintă este deja cunoscut. Arborii de decizie pot fi folosiți atât pentru date categorice, cât și pentru date numerice. Datele categorice reprezintă sexul, starea civilă etc., în timp ce datele numerice reprezintă vârsta, temperatura etc.

care este cea mai bună aplicație de spionaj

Un exemplu de arbore de decizie cu setul de date este prezentat mai jos.

(imagine sursă )

Ce veți învăța:

• La ce folosește un arbore de decizie?
• Analiza clasificării
• Analiza regresiei
• Cum funcționează un arbore de decizie?
• Algoritmul de inducere a arborelui decizional
• Inducerea arborelui decizional
• CART
• Inducerea arborelui decizional pentru învățarea automată: ID3
• Ce este divizarea binară recursivă lacomă?
• Cum să selectați atributele pentru crearea unui arbore?
  • # 1) Câștig de informații
  • # 2) Raportul de câștig
  • # 3) Indicele Gini
• Suprapunerea în copacii de decizie
• Ce este tăierea copacilor?
• Ce este modelarea predictivă?
• Avantajele clasificării arborelui decizional
• Dezavantaje ale clasificării arborelui decizional
• Concluzie
• Lectură recomandată

La ce folosește un arbore de decizie?

Arborele decizional este utilizat pentru a construi modele de clasificare și regresie. Este folosit pentru a crea modele de date care vor prezice etichete de clasă sau valori pentru procesul decizional. Modelele sunt construite din setul de date de instruire alimentat către sistem (învățare supravegheată).

Folosind un arbore de decizie, putem vizualiza deciziile care îl fac ușor de înțeles și, prin urmare, este o tehnică populară de extragere a datelor.

Analiza clasificării

Clasificarea datelor este o formă de analiză care construiește un model care descrie variabile importante de clasă.De exemplu, un model construit pentru a clasifica cererile de împrumut bancar ca fiind sigure sau riscante. Metodele de clasificare sunt utilizate în învățarea automată și în recunoașterea modelelor.

Aplicarea clasificării include detectarea fraudelor, diagnosticarea medicală, marketingul țintă etc. Rezultatul problemei de clasificare este luat ca „Mod” al tuturor valorilor observate ale nodului terminal.

Este urmat un proces în doi pași, pentru a construi un model de clasificare.

1. În primul pas, adică învățarea: se construiește un model de clasificare bazat pe datele de instruire.
2. În al doilea pas, adică Clasificare, se verifică acuratețea modelului și apoi modelul este utilizat pentru a clasifica date noi. Etichetele claselor prezentate aici sunt sub formă de valori discrete, cum ar fi „da” sau „nu”, „sigur” sau „riscant”.

Abordarea generală pentru modelele de clasificare a clădirilor este dată mai jos:

(imagine sursă )

Analiza regresiei

Analiza de regresie este utilizată pentru predicția atributelor numerice.

Atributele numerice se mai numesc valori continue. Un model construit pentru a prezice valorile continue în locul etichetelor de clasă se numește model de regresie. Rezultatul analizei de regresie este „Media” tuturor valorilor observate ale nodului.

Cum funcționează un arbore de decizie?

Un arbore de decizie este un algoritm de învățare supravegheat care funcționează atât pentru variabile discrete, cât și pentru variabile continue. Împarte setul de date în subseturi pe baza celui mai semnificativ atribut din setul de date. Modul în care arborele decizional identifică acest atribut și modul în care se face această împărțire este decis de algoritmi.

Cel mai semnificativ predictor este desemnat ca nod rădăcină, împărțirea se face pentru a forma sub-noduri numite noduri de decizie, iar nodurile care nu se împart în continuare sunt noduri terminale sau frunze.

În arborele decizional, setul de date este împărțit în regiuni omogene și care nu se suprapun. Urmează o abordare de sus în jos, deoarece regiunea de sus prezintă toate observațiile într-un singur loc, care se împarte în două sau mai multe ramuri care se împart în continuare. Această abordare se mai numește și a abordare lacomă deoarece ia în considerare doar nodul curent dintre cele lucrate fără a se concentra asupra nodurilor viitoare.

Algoritmii arborelui decizional vor continua să ruleze până la atingerea unui criteriu de oprire, cum ar fi numărul minim de observații etc.

Odată ce un arbore de decizie este construit, multe noduri pot reprezenta valori anormale sau date zgomotoase. Metoda de tăiere a arborilor este aplicată pentru a elimina datele nedorite. Acest lucru, la rândul său, îmbunătățește precizia modelului de clasificare.

Pentru a găsi acuratețea modelului, se folosește un set de testare format din tupluri de testare și etichete de clasă. Procentele tuplurilor setului de testare sunt clasificate corect de model pentru a identifica acuratețea modelului. Dacă modelul se dovedește a fi corect, atunci este utilizat pentru a clasifica tuplurile de date pentru care etichetele de clasă nu sunt cunoscute.

Unii dintre algoritmii arborelui decizional includ algoritmul Hunt, ID3, CD4.5 și CART.

Exemplu de creare a unui arbore de decizie

(Exemplul este preluat din Data Mining Concepts: Han și Kimber)

# 1) Etapa de învățare: Datele de instruire sunt introduse în sistem pentru a fi analizate printr-un algoritm de clasificare. În acest exemplu, eticheta clasei este atributul adică „decizia de împrumut”. Modelul construit din aceste date de formare este reprezentat sub forma unor reguli de decizie.

# 2) Clasificare: Setul de date de testare este alimentat modelului pentru a verifica acuratețea regulii de clasificare. Dacă modelul oferă rezultate acceptabile, atunci acesta este aplicat unui nou set de date cu variabile de clasă necunoscute.

Algoritmul de inducere a arborelui decizional

Inducerea arborelui decizional

Inducerea arborelui de decizie este metoda de învățare a arborilor de decizie din setul de instruire. Setul de instruire este format din atribute și etichete de clasă. Aplicațiile inducerii arborelui decizional includ astronomie, analiză financiară, diagnostic medical, fabricare și producție.

Un arbore de decizie este o structură în formă de arbore a unui diagramă de flux, care este realizată din tupluri stabilite de antrenament. Setul de date este împărțit în subseturi mai mici și este prezent sub formă de noduri ale unui copac. Structura arborelui are un nod rădăcină, noduri interne sau noduri de decizie, nod frunze și ramuri.

Nodul rădăcină este cel mai de sus nod. Reprezintă cel mai bun atribut selectat pentru clasificare. Nodurile interne ale nodurilor de decizie reprezintă un test al unui atribut al nodului de frunze al setului de date sau al nodului terminal care reprezintă clasificarea sau eticheta de decizie. Ramurile arată rezultatul testului efectuat.

Unii arbori de decizie au doar noduri binare , asta înseamnă exact două ramuri ale unui nod, în timp ce unii arbori de decizie sunt non-binari.

Imaginea de mai jos arată arborele de decizie pentru setul de date Titanic pentru a prezice dacă pasagerul va supraviețui sau nu.

(imagine sursă )

CART

Modelul CART, adică modelele de clasificare și regresie, este un algoritm al arborelui decizional pentru construirea modelelor. Modelul Arborelui Decizional în care valorile țintă au o natură discretă se numește modele de clasificare.

O valoare discretă este un set finit sau infinit de valori, De exemplu, vârstă, dimensiune etc. Modelele în care valorile țintă sunt reprezentate de valori continue sunt de obicei numere care se numesc Modele de regresie. Variabilele continue sunt variabile în virgulă mobilă. Aceste două modele împreună sunt numite CART.

CART folosește Gini Index ca matrice de clasificare.

Inducerea arborelui decizional pentru învățarea automată: ID3

La sfârșitul anilor 1970 și începutul anilor 1980, J.Ross Quinlan a fost un cercetător care a construit un algoritm al arborelui decizional pentru învățarea automată. Acest algoritm este cunoscut sub numele de ID3, dicotomizator iterativ . Acest algoritm a fost o extensie a conceptelor de sisteme de învățare descrise de E.B Hunt, J și Marin.

ID3 a devenit ulterior cunoscut sub numele de C4.5. ID3 și C4.5 urmează o abordare lacomă de sus în jos pentru construirea arborilor de decizie. Algoritmul începe cu un set de date de antrenament cu etichete de clasă care sunt porționate în subseturi mai mici pe măsură ce arborele este construit.

# 1) Inițial, există trei parametri, adică lista de atribute, metoda de selectare a atributelor și partiția de date . Lista atributelor descrie atributele tuplurilor setului de antrenament.

#Două) Metoda de selectare a atributelor descrie metoda de selectare a celui mai bun atribut pentru discriminare între tupluri. Metodele folosite pentru selectarea atributelor pot fi fie Information Gain sau Gini Index.

# 3) Structura arborelui (binar sau non-binar) este decisă prin metoda de selectare a atributelor.

# 4) Când construiți un arbore de decizie, acesta începe ca un singur nod care reprezintă tuplurile.

# 5) Dacă tuplurile nodului rădăcină reprezintă etichete de clasă diferite, atunci apelează o metodă de selecție a atributelor pentru a împărți sau partiționa tuplele. Pasul va duce la formarea ramurilor și a nodurilor de decizie.

care este masca de subrețea adecvată pentru o rețea între două gazde

# 6) Metoda de împărțire va determina care este atributul care trebuie selectat pentru partiționarea tuplurilor de date. De asemenea, determină ramurile care trebuie cultivate de la nod în funcție de rezultatul testului. Principalul motiv al criteriilor de divizare este acela că partiția de la fiecare ramură a arborelui decizional ar trebui să reprezinte aceeași etichetă de clasă.

Un exemplu de atribut de împărțire este prezentat mai jos:

A. Porționarea de mai sus este discretă.

b. Porționarea de mai sus este pentru valoare continuă.

# 7) Pașii de partiționare de mai sus sunt urmați recursiv pentru a forma un arbore de decizie pentru tuplurile setului de date de antrenament.

# 8) Porționarea se oprește numai atunci când sunt făcute toate partițiile sau când tuplurile rămase nu pot fi partiționate în continuare.

# 9) Complexitatea algoritmului este descrisă de n * | D | * log | D | unde n este numărul de atribute din setul de date de antrenament D și | D | este numărul de tupluri.

Ce este divizarea binară recursivă lacomă?

În metoda de împărțire binară, tuplurile sunt împărțite și se calculează fiecare funcție de cost de împărțire. Este selectată cea mai mică împărțire a costurilor. Metoda de divizare este binară care este formată ca 2 ramuri. Este de natură recursivă, deoarece aceeași metodă (calcularea costului) este utilizată pentru împărțirea celorlalte tupluri ale setului de date.

Acest algoritm este numit la fel de lacom, deoarece se concentrează doar pe nodul curent. Se concentrează pe reducerea costurilor, în timp ce celelalte noduri sunt ignorate.

Cum să selectați atributele pentru crearea unui arbore?

Măsurile de selecție a atributelor se mai numesc reguli de împărțire pentru a decide cum se împart tuplurile. Criteriile de împărțire sunt utilizate pentru a particiona cel mai bine setul de date. Aceste măsuri oferă o clasificare a atributelor pentru partiționarea tupurilor de formare.

Cele mai populare metode de selectare a atributului sunt câștigul de informații, indicele Gini.

# 1) Câștig de informații

Această metodă este principala metodă care este utilizată pentru a construi arbori de decizie. Reduce informațiile necesare pentru clasificarea tuplurilor. Reduce numărul de teste necesare pentru clasificarea tuplului dat. Este selectat atributul cu cel mai mare câștig de informații.

Informațiile originale necesare pentru clasificarea unui tuplu în setul de date D sunt date de:

Unde p este probabilitatea ca tuplul să aparțină clasei C. Informațiile sunt codificate în biți, prin urmare, se folosește jurnalul la baza 2. E (s) reprezintă cantitatea medie de informații necesare pentru a afla eticheta clasei setului de date D. Acest câștig de informații este, de asemenea, numit Entropie .

Informațiile necesare pentru clasificarea exactă după porționare sunt date de formula:

Unde P (c) este greutatea partiției. Aceste informații reprezintă informațiile necesare pentru clasificarea setului de date D pe porționare cu X.

Câștigul de informații este diferența dintre informațiile originale și cele așteptate care sunt necesare pentru clasificarea tuplurilor setului de date D.

Câștigul este reducerea informației care este necesară prin cunoașterea valorii lui X. Atributul cu cel mai mare câștig de informație este ales ca „cel mai bun”.

# 2) Raportul de câștig

Câștigul de informații poate duce uneori la porționarea inutilă pentru clasificare. Cu toate acestea, raportul Câștig împarte setul de date de antrenament în partiții și ia în considerare numărul de tupluri ale rezultatului în raport cu totalul de tupluri. Atributul cu raportul maxim de câștig este utilizat ca atribut de împărțire.

# 3) Indicele Gini

Indicele Gini este calculat numai pentru variabilele binare. Măsoară impuritatea în instruirea tuplurilor setului de date D, ca

P este probabilitatea ca tuplul să aparțină clasei C. Indicele Gini care este calculat pentru setul de date binar împărțit D prin atributul A este dat de:

Unde n este a n-a partiție a setului de date D.

Reducerea impurității este dată de diferența dintre indicele Gini al setului de date original D și indicele Gini după partiție prin atributul A.

Reducerea maximă a impurității sau indicele Gini maxim este selectată ca cel mai bun atribut pentru împărțire.

Suprapunerea în copacii de decizie

Suprapunerea se întâmplă atunci când un arbore de decizie încearcă să fie cât mai perfect posibil prin creșterea adâncimii testelor și, prin urmare, reduce eroarea. Acest lucru are ca rezultat copaci foarte complecși și duce la supraadezionare.

Suprapunerea reduce natura predictivă a arborelui decizional. Abordările pentru a evita supraadaptarea copacilor includ tăierea pre și post tăierea.

Ce este tăierea copacilor?

Tunderea este metoda de îndepărtare a ramurilor neutilizate din arborele decizional. Unele ramuri ale arborelui decizional pot reprezenta date anormale sau date zgomotoase.

Tunderea copacilor este metoda de reducere a ramurilor nedorite ale copacului. Acest lucru va reduce complexitatea arborelui și va ajuta la o analiză predictivă eficientă. Reduce supraadaptarea, deoarece îndepărtează ramurile neimportante din copaci.

Există două moduri de tăiere a copacului:

# 1) Tundere : În această abordare, construcția arborelui decizional este oprită devreme. Înseamnă că s-a decis să nu mai partiționăm ramurile. Ultimul nod construit devine nodul frunzei și acest nod frunzei poate deține cea mai frecventă clasă dintre tupluri.

Măsurile de selectare a atributelor sunt utilizate pentru a afla ponderarea împărțirii. Valorile prag sunt prescrise pentru a decide care diviziuni sunt considerate utile. Dacă porționarea nodului are ca rezultat divizarea prin scăderea sub prag, atunci procesul este oprit.

# 2) Post-tăiere : Această metodă elimină ramurile exterioare dintr-un copac complet crescut. Ramurile nedorite sunt îndepărtate și înlocuite cu un nod de frunze care denotă cea mai frecventă etichetă de clasă. Această tehnică necesită mai multe calcule decât pre-tăiere, cu toate acestea, este mai fiabilă.

Copacii tăiați sunt mai preciși și compacți în comparație cu copacii tăiați, dar prezintă un dezavantaj de replicare și repetare.

Repetarea apare atunci când același atribut este testat din nou și din nou de-a lungul unei ramuri a unui copac. Replicare apare atunci când subarborii duplicat sunt prezenți în interiorul arborelui. Aceste probleme pot fi rezolvate prin divizări multivariate.

Imaginea de mai jos prezintă un copac netăiat și tăiat.

Exemplu de algoritm al arborelui decizional

Exemplu Sursă

Construirea unui arbore de decizie

Să luăm un exemplu al setului de date meteo din ultimele 10 zile cu atribute de perspectivă, temperatură, vânt și umiditate. Variabila rezultat va fi sau nu jocul de cricket. Vom folosi algoritmul ID3 pentru a construi arborele decizional.

Pasul 1: Primul pas va fi crearea unui nod rădăcină.

Pasul 2: Dacă toate rezultatele sunt da, atunci nodul frunzei „da” va fi returnat altfel nodul frunzei „nu” va fi returnat.

Pasul 3: Aflați Entropia tuturor observațiilor și entropiei cu atributul „x” care este E (S) și E (S, x).

Pasul 4: Aflați câștigul de informații și selectați atributul cu câștig de informații ridicat.

Pasul 5: Repetați pașii de mai sus până când toate atributele sunt acoperite.

Calculul entropiei:

da nu

9 5

Dacă entropia este zero, înseamnă că toți membrii aparțin aceleiași clase și dacă entropia este una, înseamnă că jumătate din tupluri aparțin unei clase și unul dintre ei aparține altei clase. 0,94 înseamnă distribuție echitabilă.

Găsiți atributul de câștig de informații care oferă un câștig maxim de informații.

De exemplu „Vânt”, are două valori: puternic și slab, prin urmare, x = {puternic, slab}.

Aflați H (x), P (x) pentru x = slab și x = puternic. H (S) este deja calculat mai sus.

cum se face o listă dublă legată java

Slab = 8

Puternic = 8

Pentru vântul „slab”, 6 dintre ei spun „Da” pentru a juca cricket și 2 dintre ei spun „Nu”. Deci, entropia va fi:

Pentru vântul „puternic”, 3 au spus „Nu” pentru a juca cricket și 3 au spus „Da”.

Aceasta arată o aleatorie perfectă, deoarece jumătate de obiecte aparțin unei clase și jumătatea rămasă aparține altora.

Calculați câștigul de informații,

În mod similar, câștigul de informații pentru alte atribute este:

Perspectiva atributului are cel mai mare câștig de informații de 0,246, astfel se alege ca rădăcină.

Înnorat are 3 valori: Însorit, Înnorat și Ploaie. Înnorat cu jocul de cricket este întotdeauna „Da”. Deci, se termină cu un nod frunză, „da”. Pentru celelalte valori „Soare” și „Ploaie”.

Tabelul pentru Outlook ca „Sunny” va fi:

Entropia pentru „Outlook” „Sunny” este:

Câștigul de informații pentru atributele cu privire la Sunny este:

Câștigul de informații pentru umiditate este cel mai mare, prin urmare este ales ca nodul următor. În mod similar, entropia este calculată pentru ploaie. Vântul oferă cel mai mare câștig de informații .

Arborele decizional ar arăta ca mai jos:

Ce este modelarea predictivă?

Modelele de clasificare pot fi utilizate pentru a prezice rezultatele unui set necunoscut de atribute.

Când un set de date cu etichete de clasă necunoscute este introdus în model, atunci îi va atribui automat eticheta de clasă. Această metodă de aplicare a probabilității pentru a prezice rezultatele se numește modelare predictivă.

Avantajele clasificării arborelui decizional

Mai jos sunt enumerate diferitele merite ale clasificării arborelui decizional:

1. Clasificarea arborelui decizional nu necesită cunoștințe de domeniu, prin urmare, este adecvată pentru procesul de descoperire a cunoștințelor.
2. Reprezentarea datelor sub forma arborelui este ușor de înțeles de către oameni și este intuitivă.
3. Poate gestiona date multidimensionale.
4. Este un proces rapid cu o precizie mare.

Dezavantaje ale clasificării arborelui decizional

Mai jos sunt prezentate diferitele erori ale clasificării arborelui decizional:

1. Uneori, arborii de decizie devin foarte complexi și aceștia sunt numiți copaci supra-echipați.
2. Este posibil ca algoritmul arborelui decizional să nu fie o soluție optimă.
3. Arborii de decizie pot returna o soluție părtinitoare dacă o etichetă de clasă o domină.

Concluzie

Arborii de decizie sunt tehnici de extragere a datelor pentru clasificare și analiză de regresie.

Această tehnică se întinde acum pe multe domenii, cum ar fi diagnosticul medical, marketingul țintă etc. Acești copaci sunt construiți urmând un algoritm precum ID3, CART. Acești algoritmi găsesc modalități diferite de a împărți datele în partiții.

Este cea mai cunoscută tehnică de învățare supravegheată care este utilizată în învățarea automată și analiza modelelor. Arborii de decizie prezic valorile variabilei țintă prin construirea de modele prin învățarea din setul de instruire furnizat sistemului.

Sperăm că ați aflat totul despre extracția arborelui decizional din acest tutorial informativ !!

PREV Tutorial | NEXT Tutorial

Lectură recomandată

• Exemple de minerit de date: cele mai frecvente aplicații ale mineritului de date 2021
• Tehnici de extragere a datelor: algoritm, metode și instrumente de top pentru extragerea datelor
• Data Mining: Proces, tehnici și probleme majore în analiza datelor
• Structura de date B Tree și B + Tree în C ++
• Structura de date a arborelui binar în C ++
• Procesul de extragere a datelor: modele, pași de proces și provocări implicate
• Arborele AVL și structura de date Heap în C ++
• Data Mining Vs Machine Learning Vs Intelligence Artificial Vs Deep Learning