CART (algoritmi)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 2. elokuuta 2020 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

CART (Classification and Regression Tree) -algoritmi , kuten nimestä voi päätellä, ratkaisee luokittelu- ja regressioongelmat rakentamalla päätöspuun. Sen kehittivät vuosina 1974-1984 neljä tilastotieteen professoria: Leo Breiman ( Berkeley ), Jerome Friedman( Stanford ), Charles Stone (Charles Stone, Berkeley ) ja Richard Olshen (Richard A. Olshen, Stanford ).

Tähän mennessä on olemassa suuri määrä algoritmeja, jotka toteuttavat päätöspuita: CART , C4.5 , CHAID, CN2, NewId , ITrule ja muut [1] .

Algoritmin perusmerkitys

CART-algoritmi on suunniteltu rakentamaan binäärinen päätöspuu. Binääripuut (binääripuut) ovat puita, joiden jokaisella solmulla on jaettuna vain kaksi lasta. CART-algoritmissa valitun ryhmän kohteiden "käyttäytyminen" tarkoittaa osuutta lähtöominaisuuden modaalisesta (yleisimmästä) arvosta. Valitut ryhmät ovat sellaisia, joissa tämä osuus on melko korkea. Jokaisessa puun rakentamisen vaiheessa solmuun muodostettu sääntö jakaa annetun esimerkkijoukon kahteen osaan - osaan, jossa sääntö on tosi (lapsi - oikea) ja osaan, jossa sääntö ei ole tosi (lapsi - vasen). [2]

CART-algoritmin etuna on tietty takuu siitä, että jos halutut määritykset ovat olemassa tutkittavassa populaatiossa, ne paljastuvat. Lisäksi CART antaa sinun olla "sulkematta" yhdestä lähtöominaisuuden arvosta, vaan etsiä kaikkia sellaisia arvoja, joille löydät vastaavan selittävän lausekkeen. [3]

CART-menetelmää käytetään nimellisille (yleensä kaksitasoisille) ja ordinaalisille ennustajamuuttujille. Tässä menetelmässä jokaisen solmun kaikki mahdolliset haarautumisvaihtoehdot luetellaan ja valitaan se ennustajamuuttuja, jolle estimaattori antaa parhaan pistemäärän.

Osiointisäännöt

Nimelliselle ennustajamuuttujalle , joka ottaa k arvoa tietyssä solmussa, on tasan 2 (k-1) −1 vaihtoehtoa sen arvojen joukon jakamiseksi kahteen osaan.

Järjestysennustajalle , jolla on k eri tasoa tietyssä solmussa, on k-1 pistettä, jotka erottavat eri tasot. Tarkasteltavien eri haaroitusvaihtoehtojen määrä tulee olemaan erittäin suuri: jos tehtävässä on monta ennustajaa, niin niillä on monta arvotasoa, mikä tarkoittaa, että puussa on useita päätepisteitä. Lisäksi tällä menetelmällä on taipumus valita haaroittamiseen niitä ennustajamuuttujia, joilla on enemmän tasoja, joten tarvitaan indikaattori, joka mahdollistaisi konstruoidun mallin laadun arvioinnin. [neljä]

Mallin laadun arviointi

CART-algoritmin käyttämä arviointitoiminto perustuu intuitiiviseen ajatukseen solmun epävarmuuden (heterogeenisyyden) vähentämisestä. Harkitse esimerkkinä ongelmaa, jossa on kaksi luokkaa ja solmu, jossa on 50 esiintymää kustakin luokasta. Solmulla on suurin epävarmuus. Jos löydetään osio, joka jakaa tiedot kahteen alaryhmään, joissa toisessa on 40:5 esimerkkiä ja toisessa 10:45, heterogeenisuus vähenee intuitiivisesti. Se katoaa kokonaan, kun löydetään jako, joka luo alaryhmät 50:0 ja 0:50. CART-algoritmissa epävarmuuden idea on muotoiltu Gini -indeksiin . Jos tietojoukko T sisältää n luokkatietoa, Gini -indeksi määritellään seuraavasti [5]

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

, jossa pi on luokan i todennäköisyys (suhteellinen esiintyvyys ) T :ssä . Jos joukko T jaetaan kahteen osaan T1 ja T2 esimerkkien lukumäärällä kummassakin N1 ja N2 vastaavasti, niin jakamisen laatuindeksi on yhtä suuri:

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

Paras osio on se, jolle Ginisplit(T) on minimaalinen. Olkoon N esi-isolmussa olevien esimerkkien lukumäärä, L , R ovat esimerkkien lukumäärä vasemmassa ja oikeassa lapsissa, li ja ri ovat i :nnen luokan esiintymien lukumäärä vasemmassa/oikeassa lapsissa. Sitten osion laatu arvioidaan seuraavalla kaavalla:

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

Laskelmien määrän vähentämiseksi kaava voidaan muuntaa:

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

Koska kertomisella vakiolla ei ole merkitystä minimoinnissa:

{\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}\right)\to \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}}

Tämän seurauksena paras osio on se, jonka arvo on suurin. Näin ollen CART-menetelmällä ”päätöspuuta” rakennettaessa etsitään sellainen haarautumisvaihtoehto, jossa indikaattorin Ginisplit(T) arvo pienenee mahdollisimman paljon .

Leikkausmekanismi

Tämä mekanismi, jota kutsutaan minimaalisen kustannus-monimutkaisuuden puun karsimiseksi (katso englanninkielisen Wikipedian Karsinta -artikkeli), CART-algoritmi eroaa olennaisesti joistakin muista päätöspuun rakennusalgoritmeista. Tarkasteltavana olevassa algoritmissa karsiminen on kompromissi "oikean kokoisen" puun ja tarkimman luokitusarvion välillä. Karsiminen (harvennus) on tärkeää paitsi puiden yksinkertaistamiseksi, myös liiallisen istutuksen välttämiseksi . Menetelmä koostuu vähenevien puiden sarjan hankkimisesta, mutta kaikkia puita ei oteta huomioon, vaan vain "parhaat edustajat". [yksi]

Ristivahvistus

Ristiinvalidointi on CART-algoritmin monimutkaisin ja samalla alkuperäinen osa. Se on tapa valita lopullinen puu edellyttäen, että tietojoukko on pieni tai tietojoukon tietueet ovat niin spesifisiä, ettei joukkoa ole mahdollista jakaa harjoitus- ja testijoukkoon [1] .

Menetelmän edut ja haitat

Edut:

Tämä menetelmä on ei- parametrinen , mikä tarkoittaa, että sen soveltamista varten ei tarvitse laskea erilaisia todennäköisyysjakauman parametreja.
CART-algoritmin soveltamiseksi ei tarvitse etukäteen valita analyysiin osallistuvia muuttujia: muuttujat valitaan suoraan analyysin aikana Gini -indeksin arvon perusteella .
CART taistelee helposti poikkeavia tekijöitä vastaan: algoritmiin upotettu "jako"mekanismi (englanniksi Splitting) yksinkertaisesti sijoittaa "päästöt" erilliseen solmuun, jonka avulla voit poistaa käytettävissä olevat tiedot melusta.
Tämän algoritmin soveltamiseksi mitään oletuksia tai oletuksia ei tarvitse ottaa huomioon ennen analyysiä.
Suuri etu on algoritmin nopeus.

Virheet:

Algoritmin ehdottamat päätöspuut eivät ole stabiileja: yhdestä näytteestä saatu tulos ei ole toistettavissa toisella (puu voi kasvaa, kutistua, sisältää muita ennustajia jne.)
Siinä tapauksessa, että on tarpeen rakentaa puu, jolla on monimutkaisempi rakenne, on parempi käyttää muita algoritmeja, koska CART ei välttämättä tunnista oikeaa tietorakennetta.

Muistiinpanot

↑ 1 2 3 Chubukova I. A. Data Mining. M.: Binom, 2008
↑ Breiman L., Friedman JH, Olshen RA, & Stone CJ Luokittelu- ja regressiopuut. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1984
↑ Tolstova Yu.N. Sosiologisen tiedon analyysi. M.: Tieteellinen maailma, 2000
↑ Päätöspuut - CART-matemaattinen laite. Osa #1 // http://www.basegroup.ru/trees/math_cart_part1.htm Arkistoitu 22. tammikuuta 2008 Wayback Machinessa
↑ Sähköinen oppikirja "Statistica" // http://www.statsoft.ru/home/textbook.htm (linkki ei ole käytettävissä)

Kirjallisuus

Paklin N.B., Oreshkov V.I. Luku 9. // Liiketoimintaanalytiikka: Datasta tietoon (+CD): Opetusohjelma. 2. painos - Pietari. : Peter, 2013. - S. 459-465. - ISBN 978-5-459-00717-6 .