Arborele de decizie

Un arbore de decizie (numit și arbore de clasificare sau arbore de regresie) este un instrument de asistență pentru decizii utilizat în învățarea automată , analiza datelor și statistici . Structura unui copac este „frunze” și „ramuri”. Pe marginile („ramuri”) ale arborelui de decizie sunt scrise caracteristicile de care depinde funcția obiectiv, valorile funcției obiectiv sunt scrise în „frunze” , iar în nodurile rămase sunt caracteristicile prin care cazurile difera. Pentru a clasifica un nou caz, trebuie să coborâți arborele până la o frunză și să returnați valoarea corespunzătoare.

Astfel de arbori de decizie sunt utilizați pe scară largă în data mining. Scopul este de a crea un model care prezice valoarea variabilei țintă pe baza mai multor variabile de intrare.

Fiecare frunză reprezintă valoarea variabilei țintă pe măsură ce se schimbă de la rădăcină de-a lungul marginilor copacului la frunză. Fiecare nod intern este mapat la una dintre variabilele de intrare.

Arborele poate fi, de asemenea, „învățat” împărțind seturile originale de variabile în subseturi pe baza verificării valorilor caracteristicilor. Această acțiune se repetă pe fiecare dintre subseturile rezultate. Recursiunea se termină atunci când un subset dintr-un nod are aceleași valori variabile țintă, deci nu adaugă nicio valoare predicțiilor. Procesul de sus în jos, inducerea arborelui de decizie (TDIDT) [1] , este un exemplu de algoritm absorbant lacom și este de departe cea mai comună strategie de arbore de decizie pentru date, dar nu este singura strategie posibilă.

În mineritul de date, arborii de decizie pot fi utilizați ca tehnici matematice și de calcul pentru a ajuta la descrierea, clasificarea și generalizarea unui set de date, care poate fi scris după cum urmează:

Variabila dependentă Y este variabila țintă care trebuie analizată, clasificată și rezumată. Vectorul este format din variabilele de intrare , etc., care sunt folosite pentru a finaliza această sarcină .

Definiții de bază

Analiza arborelui decizional folosește un instrument vizual și analitic de sprijin pentru decizii pentru a calcula valorile așteptate (sau beneficiile așteptate) ale alternativelor concurente.

Arborele de decizie este format din trei tipuri de noduri:

• Nodurile de decizie - de obicei reprezentate prin pătrate
• Nodurile de probabilitate - reprezentate ca un cerc
• Nodurile de închidere - reprezentate ca un triunghi

În figura de mai sus, arborele de decizie ar trebui citit de la stânga la dreapta. Arborele de decizie nu poate conține elemente ciclice, adică fiecare frunză nouă se poate diviza ulterior, nu există căi convergente. Astfel, atunci când construim un arbore manual, ne putem confrunta cu problema dimensiunii acestuia, prin urmare, de regulă, putem obține un arbore de decizie folosind software specializat. De obicei, un arbore de decizie este prezentat sub forma unui desen schematic, ceea ce face mai ușor de înțeles și analizat.

Tipologia arborilor

Arborii de decizie utilizați în data mining sunt de două tipuri principale:

• Un arbore de clasificat când rezultatul prezis este clasa căreia îi aparțin datele;
• Arborele pentru regresie atunci când rezultatul prezis poate fi considerat ca un număr real (de exemplu, prețul unei case sau durata șederii unui pacient într-un spital).

Termenii menționați mai sus au fost introduși pentru prima dată de Breiman și colab.. [2] Tipurile enumerate au unele asemănări (algoritmi de construcție recursive), precum și unele diferențe, precum criteriile de alegere a unei partiții la fiecare nod. [2]

Unele metode vă permit să construiți mai mult de un arbore de decizie (ansambluri de arbori de decizie):

1. Punerea în pungă peste arbori de decizie, cea mai timpurie abordare . Construiește mai mulți arbori de decizie, interpolând în mod repetat datele cu înlocuire ( bootstrap ), iar ca răspuns de consens dă votul arborilor (predicția lor medie); [3]
2. Clasificatorul Random Forest se bazează pe bagging , cu toate acestea, pe lângă acesta, selectează aleatoriu un subset de caracteristici la fiecare nod pentru a face copacii mai independenți;
3. Tree boosting poate fi folosit atât pentru probleme de regresie, cât și pentru probleme de clasificare. [4] O implementare a tree boosting, algoritmul XGBoost , a fost folosită în mod repetat de câștigătorii competițiilor de analiză a datelor.
4. „Rotația pădurilor” - arbori în care fiecare arbore de decizie este analizat prin prima aplicare a analizei componentelor principale (PCA) pe subseturi aleatoare de caracteristici de intrare. [5]

Algoritmi de construcție a arborilor

Există mai multe moduri de a selecta următoarea caracteristică:

• Algoritmul ID3 , unde alegerea unei caracteristici are loc pe baza câștigului de informații ( ing.  Câștig ) sau pe baza criteriului Gini .
• Algoritmul C4.5 (versiunea îmbunătățită a ID3), în care selecția caracteristicilor se bazează pe câștigul de informații normalizat ( Gain Ratio ) . 
• Algoritmul CART și modificările acestuia — IndCART, DB-CART.
• Detector automat de interacțiune chi-pătrat (CHAID). Efectuează separarea pe mai multe niveluri la calcularea clasificării arborilor; [6]
• MARS: extinde arborii de decizie pentru a îmbunătăți procesarea datelor digitale.

În practică, ca urmare a acestor algoritmi, arborii sunt adesea prea detaliați, care, atunci când sunt aplicați în continuare, dau multe erori. Acest lucru se datorează fenomenului de supraadaptare . Pentru a reduce copacii, se folosește pruning ( engleză  pruning ).

Avantajele metodei

Spre deosebire de alte metode de data mining, metoda arborelui de decizie are mai multe avantaje:

• Ușor de înțeles și interpretat.
• Nu necesită pregătirea specială a datelor, cum ar fi normalizarea datelor, adăugarea de variabile fictive și eliminarea datelor lipsă.
• Capabil să lucreze atât cu variabile categorice, cât și cu variabile de interval. (Alte metode funcționează numai cu date unde există un singur tip de variabilă. De exemplu, metoda raportului poate fi aplicată numai variabilelor nominale, iar metoda rețelei neuronale doar variabilelor măsurate pe o scară de interval.)
• Folosește un model „cutie albă”, adică dacă în model se observă o anumită situație, atunci poate fi explicată folosind logica booleană. Un exemplu de „cutie neagră” poate fi o rețea neuronală artificială , deoarece rezultatele obținute sunt greu de explicat.
• Vă permite să evaluați modelul folosind teste statistice. Acest lucru face posibilă evaluarea fiabilității modelului.
• Metoda funcționează bine chiar dacă ipotezele originale incluse în model au fost încălcate.
• Vă permite să lucrați cu o cantitate mare de informații fără proceduri pregătitoare speciale. Această metodă nu necesită echipamente speciale pentru a lucra cu baze de date mari.

Dezavantajele metodei

• Problema obținerii unui arbore de decizie optim este o problemă NP-completă , în ceea ce privește unele aspecte ale optimității chiar și pentru probleme simple [7] [8] . Astfel, aplicarea practică a algoritmului arborelui de decizie se bazează pe algoritmi euristici, precum algoritmul „greedy”, unde singura soluție optimă este aleasă local la fiecare nod. Astfel de algoritmi nu pot asigura optimitatea întregului arbore în ansamblu.
• Procesul de construire a unui arbore de decizie poate crea structuri prea complexe care nu reprezintă pe deplin datele. Această problemă se numește supraajustare [9] . Pentru a o evita, este necesar să se folosească metoda de „reglare a adâncimii copacului”.
• Există concepte greu de înțeles din model, deoarece modelul le descrie într-un mod complex. Acest fenomen poate fi cauzat de probleme XOR, paritate sau multiplexor. În acest caz, avem de-a face cu copaci prohibitiv de mari. Există mai multe abordări pentru rezolvarea acestei probleme, de exemplu, o încercare de a schimba reprezentarea conceptului în model (întocmirea unor noi judecăți) [10] , sau utilizarea algoritmilor care descriu și reprezintă mai complet conceptul (de exemplu , metoda relaţiilor statistice, logica programării inductive).
• Pentru datele care includ variabile categoriale cu un set mare de niveluri (închideri), se atribuie mai multă pondere informațională acelor caracteristici care au mai multe niveluri [11] .

Controlul adâncimii arborelui

Reglarea adâncimii arborelui este o tehnică care vă permite să reduceți dimensiunea unui arbore de decizie prin îndepărtarea părților copacului care au greutate mică.

Una dintre întrebările care se ridică în algoritmul arborelui de decizie este dimensiunea optimă a arborelui final. Astfel, un copac mic poate să nu capteze una sau alta informație importantă despre spațiul eșantion. Cu toate acestea, este dificil de spus când ar trebui să se oprească algoritmul, deoarece este imposibil de prezis ce adăugare de nod va reduce semnificativ eroarea. Această problemă este cunoscută sub numele de „efectul orizont”. Cu toate acestea, strategia generală de restricție a arborelui este păstrată, adică eliminarea nodurilor este implementată dacă acestea nu oferă informații suplimentare [12] .

Ajustarea adâncimii arborelui ar trebui să reducă dimensiunea modelului arborelui de antrenament fără a reduce acuratețea predicției sau prin validare încrucișată. Există multe metode de ajustare a adâncimii unui arbore care diferă în măsurarea optimizării performanței.

Metode de reglementare

Tăierea copacilor se poate face de sus în jos sau de jos în sus. De sus în jos - tăierea începe de la rădăcină, de jos în sus - numărul de frunze ale copacului este redus. Una dintre cele mai simple metode de control este reducerea erorii de constrângere a arborelui. Începând cu frunze, fiecare nod este înlocuit cu cea mai populară clasă. Dacă modificarea nu afectează acuratețea predicției, atunci aceasta este salvată.

Exemplu de problemă

Să presupunem că suntem interesați dacă echipa noastră de fotbal favorită va câștiga următorul meci. Știm că acest lucru depinde de o serie de parametri; enumerarea lor pe toate este o sarcină fără speranță, așa că ne vom limita la cele principale:

• dacă adversarul este mai sus în clasament;
• dacă meciul se joacă acasă;
• dacă vreunul dintre liderii echipei ratează meciul;
• ploua.

Avem câteva statistici despre asta:

Aș dori să înțeleg dacă echipa noastră va câștiga în meciul următor.

Vezi și

• Random forest  - un clasificator bazat pe utilizarea comitetelor din arbori de decizie
• Recalificare
• Învățarea automată  este o clasă de metode de inteligență artificială , a cărei trăsătură caracteristică nu este soluția directă a problemei, ci învățarea în procesul de aplicare a soluțiilor la multe probleme similare.
• Tabel de decizie

Note

1. ↑ Quinlan, JR Inducerea arborilor de decizie  //  Învățare automată. - Kluwer Academic Publishers, 1986. - Nr. 1 . - P. 81-106 . Arhivat din original pe 20 ianuarie 2022.
2. ↑ 1 2 Breiman, Leu; Friedman, JH, Olshen, RA și Stone, CJ Arbori de clasificare și regresie  . - Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1984. - ISBN 978-0-412-04841-8 .
3. ↑ Breiman, L. Bagging Predictors  //  Machine Learning. - 1996. - Nr. 24 . - P. 123-140 .
4. ↑ Friedman, JH Amplificarea gradientului  stocastic . - Universitatea Stanford, 1999.
5. ↑ Hastie, T., Tibshirani, R., Friedman, JH Elementele învățării statistice : extragerea datelor, inferența și predicția  . — New York: Springer Verlag, 2001.
6. ↑ Kas ,  G.V. _  Seria C (Statistici aplicate). — Vol. 29 , nr. 2 . - P. 119-127 . - doi : 10.2307/2986296 . Arhivat din original pe 2 aprilie 2022.
7. ↑ Hyafil, Laurent; Rivest, R.L. Construirea arborilor de decizie binară optimă este NP-complet  //  Litere de procesare a informațiilor. - 1976. - Vol. 5 , nr. 1 . - P. 15-17 . - doi : 10.1016/0020-0190(76)90095-8 .
8. ↑ Murthy S. Construcția automată a arborilor de decizie din date: Un sondaj multidisciplinar  //  Data Mining and Knowledge Discovery. - 1998. - Nr. 2 . - P. 345-389 . Arhivat din original pe 2 aprilie 2022.
9. ↑ Max Bramer. Principiile minării datelor  . - Springer, 2007. - ISBN 978-1-84628-765-7 .
10. ↑ Programare logică inductivă  / Horváth, Tamás; Yamamoto, Akihiro, eds. - Springer, 2003. - ISBN 978-3-540-20144-1 .
11. ↑ Deng, H., Runger, G., Tuv, E. Bias of Importance Measures for Multi-valued Attributes and Solutions // Artificial Neural Networks and Machine Learning - ICANN 2011. ICANN 2011. Lecture Notes in Computer Science, vol 6792  ( ( engleză) / Honkela, T., Duch, W., Girolami, M., Kaski, S. (eds). - Berlin, Heidelberg: Springer, 2011. - ISBN 978-3-642-21737-1 .
12. ↑ Algoritmul rapid, de jos în sus de tăiere a arborelui de decizie

Link -uri

• Note de curs despre arbori de decizie
• Appletul Arbore de decizie oferă mai multe seturi de date eșantion de exemple de învățat și clasificat

Literatură

• Levitin A. V. Capitolul 10. Limitele de putere ale algoritmilor: arbori de decizie // Algoritmi. Introducere în dezvoltare și analiză - M .: Williams , 2006. - S. 409-417. — 576 p. — ISBN 978-5-8459-0987-9
• Paklin N.B., Oreshkov V.I. Capitolul 9. // Business Analytics: From Data to Knowledge (+CD): Tutorial. Ed. a II-a - Sankt Petersburg. : Petru, 2013. - S. 428-472. - ISBN 978-5-459-00717-6 .