C4.5

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 26 maj 2021; verifiering kräver 1 redigering .

C4.5 är en algoritm för att bygga beslutsträd , utvecklad av John Quinlan ( eng. John Ross Quinlan ). C4.5 är en förbättrad version av ID3-algoritmen av samma författare. I synnerhet lades beskärning till i den nya versionen , möjligheten att arbeta med numeriska attribut och möjligheten att bygga ett träd från ett ofullständigt träningsprov som saknar värden för vissa attribut.

Datakrav

För att kunna bygga och tillämpa ett beslutsträd med C4.5 måste data uppfylla flera villkor.

Information om objekten som ska klassificeras bör presenteras som en ändlig uppsättning funktioner ( attribut ), som var och en har ett diskret eller numeriskt värde. Låt oss kalla en sådan uppsättning attribut för ett exempel . För alla exempel måste antalet attribut och deras sammansättning vara konstant.

Uppsättningen klasser som exemplen ska delas in i måste ha ett ändligt antal element, och varje exempel måste unikt referera till en viss klass. För fall av fuzzy logic , där exemplen tillhör en klass med viss sannolikhet, är C4.5 inte tillämpligt.

I träningsexemplet bör antalet exempel vara mycket större än antalet klasser, och varje exempel ska vara kopplat till sin klass i förväg. Av denna anledning är C4.5 en variant av övervakad maskininlärning .

Bygga ett träd

Låt oss vara ett träningsexempel och vara en uppsättning klasser som består av element. För varje exempel från är dess tillhörighet till någon av klasserna känd . $T$ $C$ $k$ $T$ $C_{1}\ldots C_{k}$

Konstruktionen av ett beslutsträd med C4.5-algoritmen skiljer sig inte fundamentalt från dess konstruktion i ID3 . I det första steget finns det en rot och en uppsättning kopplade till den , som måste delas upp i delmängder. För att göra detta måste du välja ett av attributen som en check. Det valda attributet har värden, vilket resulterar i delinställning. Därefter skapas avkomlingar till roten, som var och en tilldelas sin egen delmängd som erhålls genom att dela . Proceduren för att välja ett attribut och dela på det tillämpas rekursivt på alla avkomlingar och stopp i två fall: $T$ $A$ $n$ $n$ $n$ $T$ $n$

efter nästa gren visas exempel från en klass i spetsen (då blir det ett löv , och klassen som dess exempel tillhör blir lösningen av bladet),
vertexen visade sig vara associerad med den tomma uppsättningen (då blir det ett löv, och den vanligaste klassen av den omedelbara förfadern till denna vertex väljs som lösning).

Implementeringar

J48 är en Java-implementation , inkluderad i Weka -paketet [1] .
C5.0 (för Linux ) / See5 (för Windows ) är en C -implementering av Quinlan .

Anteckningar

↑ Weka.Classifiers.Trees: J48 . Dokumentation hos Sourceforge . Hämtad 18 februari 2012. Arkiverad från originalet 12 september 2012.

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. 444-459. - ISBN 978-5-459-00717-6 .
Quinlan JR Learning With Continuous Classes (engelska) // Proceedings of the 5th Australian Joint Conference on Artiﬁcial Intelligence. - 1992. - S. 343-348. - ISBN 978-9810-2125-06 .
Quinlan JR C4.5: Program för maskininlärning. - San Mateo : Morgan Kaufmann Publishers Inc., 1993. - 302 sid. — ISBN 1-5586-0238-0 . (Engelsk)
Quinlan JR Förbättrad användning av kontinuerliga attribut i C4.5 // Journal of Artificial Intelligence Research. - 1996. - Vol. 4. - S. 77-90. — ISSN 1076-9757 . - doi : 10.1613/jair.279 . Arkiverad från originalet den 21 oktober 2011.

Länkar

Datautvinningsverktyg Se5 och C5.0 . Rule Quest Research. Hämtad 16 februari 2012. Arkiverad från originalet 25 maj 2012.