CART (algoritm)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 2 augusti 2020; kontroller kräver 2 redigeringar .

CART - algoritmen (Classification and Regression Tree) löser, som namnet antyder, klassificerings- och regressionsproblem genom att bygga ett beslutsträd. Den utvecklades 1974-1984 av fyra professorer i statistik: Leo Breiman ( Berkeley ), Jerome Friedman( Stanford ), Charles Stone (Charles Stone, Berkeley ) och Richard Olshen (Richard A. Olshen, Stanford ).

Hittills finns det ett stort antal algoritmer som implementerar beslutsträd: CART , C4.5 , CHAIDCN2 _, NewId , ITrule och andra [1] .

Den grundläggande innebörden av algoritmen

CART-algoritmen är utformad för att bygga ett binärt beslutsträd. Binära (binära) träd är träd där varje nod, när de delas, bara har två barn. För CART-algoritmen betyder "beteendet" för objekten i den valda gruppen andelen av det modala (mest frekventa) värdet för utdatafunktionen. Utvalda grupper är de för vilka denna andel är ganska hög. Vid varje steg av trädkonstruktionen delar regeln som bildas i noden den givna uppsättningen av exempel i två delar - den del där regeln är sann (underordnad - höger) och den del där regeln inte är sann (barn - vänster). [2]

Fördelen med CART-algoritmen är en viss garanti för att om de önskade bestämningarna finns i den studerade populationen, kommer de att avslöjas. Dessutom tillåter CART dig att inte "stänga" på ett enda värde för utdatafunktionen, utan att söka efter alla sådana värden som du kan hitta motsvarande förklarande uttryck för. [3]

CART-metoden används för nominella (vanligtvis tvånivåer) och ordinala prediktorvariabler. I denna metod är alla möjliga förgreningsalternativ för varje nod uppräknade, och prediktorvariabeln väljs för vilken estimatorn ger bäst poäng.

Partitioneringsregler

För en nominell prediktorvariabel som tar k-värden i en given nod, finns det exakt 2 (k-1) -1 alternativ för att dela upp uppsättningen av dess värden i två delar.

För en ordinalprediktor som har k olika nivåer vid en given nod, finns det k-1 punkter som separerar olika nivåer. Antalet olika förgreningsalternativ som behöver ses kommer att vara mycket stort: om det finns många prediktorer i problemet, så har de många nivåer av värden, vilket betyder att det finns många terminala hörn i trädet. Dessutom tenderar denna metod att välja för förgrening av de prediktorvariabler som har fler nivåer, så en indikator behövs som skulle göra det möjligt att bedöma kvaliteten på den konstruerade modellen. [fyra]

Utvärdering av modellens kvalitet

Utvärderingsfunktionen som används av CART-algoritmen är baserad på den intuitiva idén att minska osäkerheten (heterogeniteten) i en nod. Som ett exempel, betrakta ett problem med två klasser och en nod som har 50 instanser av varje klass. Noden har maximal osäkerhet. Om en partition hittas som delar upp data i två undergrupper av 40:5 exempel i den ena och 10:45 i den andra, så kommer intuitivt heterogeniteten att minska. Den försvinner helt när en split hittas som skapar undergrupperna 50:0 och 0:50. I CART-algoritmen formaliseras idén om osäkerhet i Gini- indexet . Om datamängden T innehåller n klassdata, definieras Gini- indexet enligt följande [5]

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

, där pi är sannolikheten (relativ frekvens) för klass i i T . Om uppsättningen T är uppdelad i två delar T1 och T2 med antalet exempel i varje N1 respektive N2 , kommer delningskvalitetsindexet att vara lika med:

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

Den bästa partitionen är den för vilken Ginisplit(T) är minimal. Låt N vara antalet exempel i förfadernoden, L , R är antalet exempel i vänster respektive höger barn, li och ri är antalet instanser av den i :e klassen i vänster/höger barn. Sedan uppskattas kvaliteten på partitionen med följande formel:

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

För att minska mängden beräkningar kan formeln transformeras:

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

Eftersom multiplikation med en konstant inte spelar någon roll vid minimering:

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

Som ett resultat kommer den bästa partitionen att vara den för vilken värdet är maximalt. Sålunda, när man konstruerar ett "beslutsträd" med CART-metoden, söker man efter ett sådant förgreningsalternativ, där värdet på indikatorn Ginisplit(T) minskar så mycket som möjligt .

Klippmekanism

Denna mekanism, som kallas trädbeskärning med minimal kostnad och komplexitet (se artikeln om beskärning på engelska Wikipedia), CART-algoritmen skiljer sig fundamentalt från vissa andra beslutsträdskonstruktionsalgoritmer. I den aktuella algoritmen är beskärning en avvägning mellan att få trädet i "rätt storlek" och att få den mest exakta klassificeringsuppskattningen. Beskärning (gallring) är viktigt inte bara för att förenkla träd, utan också för att undvika övermontering . Metoden består i att erhålla en sekvens av minskande träd, men inte alla träd beaktas, utan endast de "bästa representanterna". [ett]

Korsvalidering

Korsvalidering är den mest komplexa och samtidigt den ursprungliga delen av CART-algoritmen. Det är ett sätt att välja det slutliga trädet, förutsatt att datamängden är liten eller att datauppsättningens poster är så specifika att det inte är möjligt att dela upp uppsättningen i tränings- och testuppsättningar [1] .

Fördelar och nackdelar med metoden

Fördelar:

Denna metod är icke- parametrisk , vilket innebär att det för dess tillämpning inte finns något behov av att beräkna olika parametrar för sannolikhetsfördelningen.
För att tillämpa CART-algoritmen behöver du inte förvälja de variabler som ska delta i analysen: variablerna väljs direkt under analysen baserat på värdet på Gini- indexet .
CART bekämpar enkelt extremvärden: "delnings"-mekanismen (från engelska. Splitting), inbäddad i algoritmen, placerar helt enkelt "emissioner" i en separat nod, vilket gör att du kan rensa tillgängliga data från brus.
För att tillämpa denna algoritm behöver inga antaganden eller antaganden tas i beaktande före analys.
Den stora fördelen är algoritmens hastighet.

Brister:

De beslutsträd som föreslås av algoritmen är inte stabila: resultatet som erhålls på ett prov är inte reproducerbart på ett annat (trädet kan växa, krympa, inkludera andra prediktorer, etc.)
I de fall där det är nödvändigt att bygga ett träd med en mer komplex struktur, är det bättre att använda andra algoritmer, eftersom CART kanske inte identifierar den korrekta datastrukturen.

Anteckningar

↑ 1 2 3 Chubukova I. A. Data Mining. M.: Binom, 2008
↑ Breiman L., Friedman JH, Olshen RA, & Stone CJ Klassificerings- och regressionsträd. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1984
↑ Tolstova Yu.N. Analys av sociologiska data. M.: Vetenskaplig värld, 2000
↑ Beslutsträd - CART matematisk apparat. Del #1 // http://www.basegroup.ru/trees/math_cart_part1.htm Arkiverad 22 januari 2008 på Wayback Machine
↑ Elektronisk lärobok "Statistica" // http://www.statsoft.ru/home/textbook.htm (otillgänglig länk)

Litteratur

Paklin N.B., Oreshkov V.I. Kapitel 9. // Business Analytics: From Data to Knowledge (+CD): Handledning. 2:a uppl. - St Petersburg. : Peter, 2013. - S. 459-465. - ISBN 978-5-459-00717-6 .