CART (algoritm)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 2 august 2020; verificările necesită 2 modificări .

Algoritmul CART (Arborele de clasificare și regresie) , după cum sugerează și numele, rezolvă problemele de clasificare și regresie prin construirea unui arbore de decizie. A fost dezvoltat în 1974-1984 de către patru profesori de statistică: Leo Breiman ( Berkeley ), Jerome Friedman( Stanford ), Charles Stone (Charles Stone, Berkeley ) și Richard Olshen (Richard A. Olshen, Stanford ).

Până în prezent, există un număr mare de algoritmi care implementează arbori de decizie: CART , C4.5 , CHAID, CN2, NewId , ITrule și altele [1] .

Sensul de bază al algoritmului

Algoritmul CART este conceput pentru a construi un arbore de decizie binar. Arborii binari (binari) sunt copaci, fiecare nod din care, atunci când este împărțit, are doar doi copii. Pentru algoritmul CART, „comportamentul” obiectelor grupului selectat înseamnă proporția din valoarea modală (cea mai frecventă) a caracteristicii de ieșire. Grupurile selectate sunt cele pentru care această proporție este destul de mare. La fiecare pas al construcției arborelui, regula formată în nod împarte setul dat de exemple în două părți — partea în care regula este adevărată (copil — dreapta) și partea în care regula nu este adevărată (copil — stânga). [2]

Avantajul algoritmului CART este o anumită garanție că dacă determinările dorite există în populația studiată, atunci acestea vor fi relevate. În plus, CART vă permite să nu „închideți” o singură valoare a caracteristicii de ieșire, ci să căutați toate astfel de valori pentru care puteți găsi expresia explicativă corespunzătoare. [3]

Metoda CART este utilizată pentru variabilele predictoare nominale (de obicei cu două niveluri) și ordinale . În această metodă, sunt enumerate toate opțiunile de ramificare posibile pentru fiecare nod și este selectată variabila predictor pentru care estimatorul dă cel mai bun scor.

Reguli de partiționare

Pentru o variabilă predictor nominală care ia k valori într-un nod dat, există exact 2 (k-1) -1 opțiuni pentru împărțirea setului valorilor sale în două părți.

Pentru un predictor ordinal care are k niveluri diferite la un nod dat, există k-1 puncte care separă diferite niveluri. Numărul de opțiuni de ramificare diferite care trebuie vizualizate va fi foarte mare: dacă există mulți predictori în problemă, atunci aceștia au multe niveluri de valori, ceea ce înseamnă că există multe vârfuri terminale în arbore. În plus, această metodă tinde să aleagă pentru ramificarea acelor variabile predictoare care au mai multe niveluri, deci este nevoie de un indicator care să permită evaluarea calității modelului construit. [patru]

Evaluarea calitatii modelului

Funcția de evaluare utilizată de algoritmul CART se bazează pe ideea intuitivă de reducere a incertitudinii (eterogenității) într-un nod. Ca exemplu, luați în considerare o problemă cu două clase și un nod care are 50 de instanțe ale fiecărei clase. Nodul are incertitudine maximă. Dacă se găsește o partiție care împarte datele în două subgrupe de exemple de 40:5 într-unul și 10:45 în celălalt, atunci intuitiv eterogenitatea va scădea. Va dispărea complet atunci când se găsește o divizare care va crea subgrupuri 50:0 și 0:50. În algoritmul CART, ideea de incertitudine este formalizată în indicele Gini . Dacă setul de date T conține n date de clasă, atunci indicele Gini este definit după cum urmează [5]

Gini(T)=1-\sum _{{i=1}}^{n}p_{i}^{2}

, unde pi este probabilitatea (frecvența relativă) a clasei i în T . Dacă setul T este împărțit în două părți T1 și T2 cu numărul de exemple în fiecare N1 și respectiv N2 , atunci indicele de calitate a împărțirii va fi egal cu:

Gini_{{\text{split}}}(T)={\frac {N_{1}}{N}}\cdot Gini(T_{1})+{\frac {N_{2}}{N}} \cdot Gini(T_{2})

Cea mai bună partiție este cea pentru care Ginisplit(T) este minim. Fie N numărul de exemple din nodul strămoș, L , R sunt numărul de exemple din copiii din stânga și din dreapta, respectiv, li și ri sunt numărul de instanțe ale clasei i -a din copiii din stânga/dreapta. Apoi, calitatea partiției este estimată prin următoarea formulă:

Gini_{{\text{split}}}={\frac {L}{N}}\cdot \left(1-\sum _{{i=1}}^{n}\left({\frac {l_ {i}}{L}}\right)^{2}\right)+{\frac {R}{N}}\cdot \left(1-\sum _{{i=1}}^{n} \left({\frac {r_{i}}{R}}\dreapta)^{2}\dreapta)\la \min

Pentru a reduce cantitatea de calcule, formula poate fi transformată:

Gini_{{\text{split}}}={\frac {1}{N}}\cdot \left(L\cdot \left(1-{\frac {1}{L^{2}}}\cdot \sum _{{i=1}}^{n}l_{i}^{2}\right)+R\cdot \left(1-{\frac {1}{R^{2}}}\cdot \sum _{{i=1}}^{n}r_{i}^{2}\right)\right)\to \min

Deoarece înmulțirea cu o constantă nu joacă un rol în minimizare:

{\begin{array}{l}\displaystyle Gini_{{\text{split}}}=L-{\frac {1}{L}}\cdot \sum _{{i=1}}^{n} l_{i}^{2}+R-{\frac {1}{R}}\cdot \sum _{{i=1}}^{n}r_{i}^{2}\to \min \ \\displaystyle Gini_{{\text{split}}}=N-\left({\frac {1}{L}}\cdot \sum _{{i=1}}^{n}l_{i}^ {2}+{\frac {1}{R}}\cdot \sum _{{i=1}}^{n}r_{i}^{2}\dreapta)\la \min \\\displaystyle { \tilde {G}}_{{\text{split}}}={\frac {1}{L}}\cdot \sum _{{i=1}}^{n}l_{i}^{2 }+{\frac {1}{R}}\cdot \sum _{{i=1}}^{n}r_{i}^{2}\to \max \end{array}}

Ca rezultat, cea mai bună partiție va fi cea pentru care valoarea este maximă. Astfel, la construirea unui „arbore de decizie” folosind metoda CART, se caută o astfel de opțiune de ramificare, în care valoarea indicatorului Ginisplit(T) scade cât mai mult posibil .

Mecanism de tăiere

Acest mecanism, numit tăierea arborelui cu complexitate minimă a costurilor (vezi articolul Pruning din Wikipedia în engleză), algoritmul CART este fundamental diferit de alți algoritmi de construcție a arborelui de decizie. În algoritmul luat în considerare, tăierea este un compromis între obținerea arborelui „dimensiune potrivită” și obținerea celei mai precise estimări de clasificare. Tunderea (rățierea) este importantă nu numai pentru a simplifica copacii, ci și pentru a evita supraadaptarea . Metoda constă în obținerea unei succesiuni de arbori în scădere, dar nu sunt considerați toți arborii, ci doar „cei mai buni reprezentanți”. [unu]

Validare încrucișată

Validarea încrucișată este cea mai complexă și, în același timp, partea originală a algoritmului CART. Este o modalitate de a selecta arborele final, cu condiția ca setul de date să fie mic sau înregistrările setului de date să fie atât de specifice încât să nu fie posibilă împărțirea setului în seturi de antrenament și de testare [1] .

Avantajele și dezavantajele metodei

Avantaje:

Această metodă este neparametrică , ceea ce înseamnă că pentru aplicarea ei nu este nevoie să se calculeze diverși parametri ai distribuției de probabilitate.
Pentru a aplica algoritmul CART, nu este nevoie să preselectați variabilele care vor participa la analiză: variabilele sunt selectate direct în timpul analizei pe baza valorii indicelui Gini .
CART luptă cu ușurință cu valorile aberante: mecanismul de „splitting” (din engleză. Splitting), încorporat în algoritm, plasează pur și simplu „emisiile” într-un nod separat, ceea ce vă permite să ștergeți datele disponibile de zgomot.
Pentru a aplica acest algoritm, nu trebuie luate în considerare ipoteze sau ipoteze înainte de analiză.
Marele avantaj este viteza algoritmului.

Defecte:

Arborii de decizie propuși de algoritm nu sunt stabili: rezultatul obținut pe o probă nu este reproductibil pe altul (arborele poate crește, micșora, include alți predictori etc.)
În cazul în care este necesar să construiți un arbore cu o structură mai complexă, este mai bine să utilizați alți algoritmi, deoarece CART poate să nu identifice structura corectă a datelor.

Note

↑ 1 2 3 Chubukova I. A. Data Mining. M.: Binom, 2008
↑ Breiman L., Friedman JH, Olshen RA și Stone CJ Arbori de clasificare și regresie. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1984
↑ Tolstova Yu.N. Analiza datelor sociologice. M.: Lumea științifică, 2000
↑ Arbori de decizie - aparate matematice CART. Partea #1 // http://www.basegroup.ru/trees/math_cart_part1.htm Arhivat 22 ianuarie 2008 la Wayback Machine
↑ Manual electronic „Statistica” // http://www.statsoft.ru/home/textbook.htm (link inaccesibil)

Literatură

Paklin N.B., Oreshkov V.I. Capitolul 9. // Business Analytics: From Data to Knowledge (+CD): Tutorial. Ed. a II-a - Sankt Petersburg. : Peter, 2013. - S. 459-465. - ISBN 978-5-459-00717-6 .