CART (algoritmus)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. augusztus 2-án felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A CART (Classification and Regression Tree) algoritmus , ahogy a neve is sugallja, döntési fa felépítésével oldja meg az osztályozási és regressziós problémákat. 1974-1984 között négy statisztikaprofesszor fejlesztette ki: Leo Breiman ( Berkeley ), Jerome Friedman( Stanford ), Charles Stone (Charles Stone, Berkeley ) és Richard Olshen (Richard A. Olshen, Stanford ).

A mai napig számos olyan algoritmus létezik, amely döntési fákat valósít meg: CART , C4.5 , CHAID, CN2, NewId , ITrule és mások [1] .

Az algoritmus alapvető jelentése

A CART algoritmust bináris döntési fa létrehozására tervezték. A bináris (bináris) fák olyan fák, amelyek mindegyik csomópontjának felosztása esetén csak két gyermeke van. A CART algoritmusnál a kiválasztott csoport objektumainak "viselkedése" a kimeneti jellemző modális (leggyakoribb) értékének arányát jelenti. A kiválasztott csoportok azok, amelyeknél ez az arány meglehetősen magas. A faépítés minden lépésében a csomópontban kialakított szabály két részre osztja az adott példakészletet - arra a részre, ahol a szabály igaz (gyermek - jobb), és arra a részre, ahol a szabály nem igaz (gyermek - bal). [2]

A CART algoritmus előnye, hogy bizonyos garancia arra, hogy ha a kívánt meghatározások megvannak a vizsgált populációban, akkor azok megjelennek. Ezenkívül a CART lehetővé teszi, hogy ne „bezárja” a kimeneti jellemző egyetlen értékét, hanem keressen minden olyan értéket, amelyhez megtalálja a megfelelő magyarázó kifejezést. [3]

A CART módszert nominális (általában kétszintű) és ordinális prediktorváltozókhoz használják. Ebben a módszerben minden egyes csomóponthoz tartozó összes lehetséges elágazási opciót felsoroljuk, és kiválasztjuk azt a prediktorváltozót, amelyre a becslő a legjobb pontszámot adja.

Particionálási szabályok

Egy névleges előrejelző változóhoz, amely egy adott csomópontban k értéket vesz fel, pontosan 2 (k-1) −1 lehetőség van az értékkészlet két részre osztására.

Egy adott csomóponton k különböző szinttel rendelkező ordinális előrejelző esetén k-1 pont választja el a különböző szinteket. A különböző elágazási lehetőségek száma, amelyeket meg kell tekinteni, nagyon nagy lesz: ha sok prediktor van a problémában, akkor sok értékük van, ami azt jelenti, hogy sok terminális csúcs van a fában. Ezen túlmenően ez a módszer inkább azokat a prediktorváltozókat választja elágazásra, amelyeknek több szintje van, ezért olyan indikátorra van szükség, amely lehetővé teszi a felépített modell minőségének értékelését. [négy]

A modell minőségének értékelése

A CART algoritmus által használt kiértékelési funkció azon az intuitív ötleten alapul, hogy csökkentsék egy csomópontban a bizonytalanságot (heterogenitást). Példaként vegyünk egy problémát két osztállyal és egy olyan csomóponttal, amelyik mindegyik osztályból 50 példányt tartalmaz. A csomópont maximális bizonytalansággal rendelkezik. Ha olyan partíciót találunk, amely az adatokat két 40:5 arányú, a másikban 10:45 arányú alcsoportra osztja, akkor a heterogenitás intuitív módon csökkenni fog. Teljesen eltűnik, ha olyan felosztást találunk, amely 50:0 és 0:50 alcsoportokat hoz létre. A CART algoritmusban a bizonytalanság gondolata a Gini -indexben formalizálódik . Ha a T adatkészlet n osztályadatot tartalmaz, akkor a Gini -indexet a következőképpen határozzuk meg [5]

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

, ahol pi az i osztály valószínűsége (relatív gyakorisága) T -ben . Ha a T halmazt két részre osztjuk T1 és T2 részre , mindegyik N1 és N2 példák számával , akkor a felosztási minőségi index egyenlő lesz:

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

A legjobb partíció az, amelyhez a Ginisplit(T) minimális. Legyen N az őscsomópontban lévő példák száma, L , R a bal és a jobb oldali gyermek példáinak száma, li és ri az i -edik osztály példányainak száma a bal/jobb gyermekben. Ezután a partíció minőségét a következő képlettel becsüljük meg:

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

A számítások mennyiségének csökkentése érdekében a képlet átalakítható:

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

Mivel a konstanssal való szorzás nem játszik szerepet a minimalizálásban:

{\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}}

Ennek eredményeként az lesz a legjobb partíció, amelynél az érték maximális. Így a „döntési fa” CART módszerrel történő felépítésénél olyan elágazási lehetőséget keresünk, amelyben a Ginisplit(T) mutató értéke a lehető legnagyobb mértékben csökken .

Vágó mechanizmus

Ez a minimális költség-komplexitású fametszésnek nevezett mechanizmus (lásd az angol Wikipédiában a Metszés című cikket ), a CART algoritmus alapvetően különbözik néhány más döntési fa építési algoritmustól. A vizsgált algoritmusban a metszés kompromisszum a "megfelelő méretű" fa és a legpontosabb osztályozási becslés között. A metszés (ritkítás) nemcsak a fák egyszerűsítése miatt fontos, hanem a túlillesztés elkerülése érdekében is . A módszer a csökkenő fák sorozatának megszerzéséből áll, de nem minden fát veszünk figyelembe, hanem csak a „legjobb képviselőket”. [egy]

Keresztellenőrzés

A keresztellenőrzés a CART algoritmus legösszetettebb és egyben eredeti része. Ez egy módja a végső fa kiválasztásának, feltéve, hogy az adathalmaz kicsi, vagy az adathalmaz rekordjai annyira specifikusak, hogy nem lehet a halmazt felosztani képzési és tesztkészletekre [1] .

A módszer előnyei és hátrányai

Előnyök:

Ez a módszer nem parametrikus , ami azt jelenti, hogy alkalmazásához nincs szükség a valószínűségi eloszlás különböző paramétereinek kiszámítására.
A CART algoritmus alkalmazásához nincs szükség az elemzésben részt vevő változók előzetes kiválasztására: a változók kiválasztása közvetlenül az elemzés során történik a Gini -index értéke alapján .
A CART könnyen felveszi a harcot a kiugrókkal: az algoritmusba ágyazott „felosztó” mechanizmus (az angolból. Splitting) egyszerűen egy külön csomópontba helyezi a „kibocsátásokat”, ami lehetővé teszi a rendelkezésre álló adatok megtisztítását a zajtól.
Ennek az algoritmusnak az alkalmazásához nem kell feltételezéseket vagy feltételezéseket figyelembe venni az elemzés előtt.
A nagy előnye az algoritmus gyorsasága.

Hibák:

Az algoritmus által javasolt döntési fák nem stabilak: az egyik mintán kapott eredmény nem reprodukálható a másikon (a fa nőhet, zsugorodhat, tartalmazhat más prediktorokat stb.)
Abban az esetben, ha bonyolultabb szerkezetű fát kell építeni, célszerű más algoritmusokat használni, mivel előfordulhat, hogy a CART nem azonosítja a megfelelő adatstruktúrát.

Jegyzetek

↑ 1 2 3 Chubukova I. A. Adatbányászat. M.: Binom, 2008
↑ Breiman L., Friedman JH, Olshen RA, & Stone CJ Osztályozási és regressziós fák. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1984
↑ Tolstova Yu.N. Szociológiai adatok elemzése. M.: Tudományos világ, 2000
↑ Döntési fák - CART matematikai apparátus. 1. rész // http://www.basegroup.ru/trees/math_cart_part1.htm Archiválva : 2008. január 22. a Wayback Machine -nél
↑ "Statistica" elektronikus tankönyv // http://www.statsoft.ru/home/textbook.htm (hozzáférhetetlen hivatkozás)

Irodalom

Paklin N.B., Oreshkov V.I. 9. fejezet // Üzleti elemzés: Az adatoktól a tudásig (+CD): oktatóanyag. 2. kiadás – Szentpétervár. : Péter, 2013. - S. 459-465. - ISBN 978-5-459-00717-6 .