Ein­füh­rung

Die Klas­si­fi­ka­tion beschreibt das Zuord­nen von Objek­ten oder Daten in vor­de­fi­nierte Kate­go­rien. Die Anwen­dun­gen rei­chen dabei von der Erken­nen von Spam E‑Mails, Kate­go­ri­sie­ren von Spe­zies bis hin zur Astro­no­mie und der Detek­tion von Neu­tri­nos. Ein decis­ion tree (zu Deutsch Ent­schei­dungs­baum) ist eines von meh­re­ren Bei­spie­len für einen auto­ma­ti­schen Klas­si­fi­zie­rer, der sich unter ande­rem dadurch aus­zeich­net, dass er ein­fach zu imple­men­tie­ren und visua­li­sie­ren ist. Im Fol­gen­dem wird die Funk­ti­ons­weise eines binä­ren decis­ion tree anhand des Bei­spiels von Dar­win­fin­ken erläu­tert. Dabei wird der CART (Clas­si­fi­ca­tion and Regres­sion Trees) Algo­rith­mus zum Erstel­len und Trai­nie­ren des Bau­mes verwendet.

Wie trai­niere ich einen Decis­ion Tree

Ange­nom­men Bio­lo­gen fin­den heute auf den Gala­pa­gos Inseln eine Vogel­art, die sie nicht ein­deu­tig einer schon bekann­ten Art zuord­nen kön­nen. Was sie aber besit­zen, sind Dar­wins Auf­zeich­nun­gen (siehe Tabelle 1) aus sei­ner Expe­di­tion von 1835. In die­sen Auf­zeich­nun­gen doku­men­tiert Dar­win die Vögel anhand der Schna­bel­größe und der Farbe des Gefie­ders. Diese Auf­zeich­nun­gen kön­nen als Trai­nings­da­ten für einen decis­ion tree dienen. 

Trai­nings­da­ten zeich­nen sich dadurch aus, dass diese ein Label (in die­sem Fall die Art) und Attri­bute (Schna­bel­größe und Farbe) besit­zen. Zum Ver­gleich haben die Bio­lo­gen von der neu ent­deck­ten Art ledig­lich nur die Attri­bute, mit denen man anschlie­ßend eine Aus­sage dar­über tref­fen kann, mit wel­cher Wahr­schein­lich­keit es sich um wel­che Art han­delt. Für die Klas­si­fi­ka­tion kön­nen jetzt anhand der Attri­bute True/­False-Fra­gen gestellt wer­den, die die Daten nach jeder Frage in zwei Teil­men­gen auf­tei­len. In einem decis­ion tree wer­den die Daten mit meh­re­rer sol­cher Fra­gen in einer hier­ar­chi­schen Rei­hen­folge auf­ge­teilt, bis am Ende keine wei­te­ren Teil­men­gen sepa­riert wer­den kön­nen. Die Abbil­dung 1 stellt einen decis­ion tree sche­ma­tisch dar. 

Die­ser besteht aus einem Wur­zel­kno­ten (engl. root node), wel­cher die gesamte Daten­menge ent­hält und den Start­punkt defi­niert. Anschlie­ßend wird an jedem Kno­ten eine Sepa­ra­tion der Daten­menge anhand einer true- oder false-Frage durch­ge­führt. Die zwei Teil­men­gen bil­den dann zwei wei­tere Kno­ten, die über die true- oder false-Äste mit den vor­he­ri­gen Kno­ten ver­bun­den sind. Die nach­kom­men­den Kno­ten kön­nen wie­derum zwei Äste besit­zen, die wie­derum auf Kno­ten zei­gen, was diese Kno­ten zu inter­nen Kno­ten (engl. inter­nal node) macht. Kann eine Teil­menge an einem Kno­ten nicht wei­ter auf­ge­teilt wer­den, wird der Kno­ten zu einem Blatt (engl. leaf ) und hat somit auch kein Fol­ge­kno­ten. Der nächste Schritt ist es her­aus­zu­fin­den, wel­che Frage an wel­cher Stelle zu stel­len ist. Dazu füh­ren wir zunächst den Begriff der Rein­heit (engl. purity) einer Daten­menge ein. Eine Mög­lich­keit die Rein­heit zu quan­ti­sie­ren ist der Gini-Index oder Gini-Koeffizient

der einen Zah­len­wert von 0 und 1 anneh­men kann und ein Maß für die Ungleich­ver­tei­lung ist. Dabei ent­spricht ein Gini-Index von 0 der größt­mög­li­chen Rein­heit. In unse­rem Bei­spiel beschreibt pipi die Wahr­schein­lich­keit ein bestimm­tes Label aus unse­ren Daten zu zie­hen. Unsere Test­da­ten haben ins­ge­samt fünf Ein­träge. Die Wahr­schein­lich­keit zufäl­lig das Label Geo­spitza Magni­rostris zu zie­hen beträgt p=2/5, weil die­ses zwei Mal vor­han­den ist. Der Gini-Index des Wur­zel­kno­tens ent­spricht damit:

Aus­ge­hend von der gestell­ten Frage, wird diese Daten­menge imWur­zel­kno­ten in zwei Teil­men­gen auf­ge­teilt, die dann jeweils einen ver­schie­de­nen Gini-Index in den Fol­ge­kno­ten besit­zen. Die mög­li­chen Fra­gen, die am Wur­zel­kno­ten gestellt wer­den kön­nen, erge­ben sich aus den Attributen:

1. Schna­bel >= 5?
2. Schna­bel >= 1?
3. Farbe == braun?
4. Farbe == schwarz?
5. Farbe == grün?

Die Abb. 2 und 3 stel­len die unter­schied­li­chen Ergeb­nisse für die Fra­gen 1 und 4 dar. Beide star­ten am Wur­zel­kno­ten mit dem Gini-Index L=0,64. Für die Frage ” Schna­bel >= 5 ” ergibt sich ein gewich­te­ter Gini-Index der bei­den Fol­ge­kno­ten von

Für die Frage ”Farbe ====schwarz ?” ergibt sich ein gewich­te­ter Gini-Index von

Um so höher I ist, desto bes­ser wird die Daten­menge bezüg­lich ihrer Rein­heit in zwei Teil­men­gen auf­ge­teilt. In die­sem Bei­spiel erge­ben sich zwei Werte I₅=0,37 und I_schwarz=0,17 und die Wahl für die erste Frage im decis­ion tree fällt auf  “Schna­bel >=5>=5 ?” (siehe Abb. 2). Für die Wei­ter­ent­wick­lung des Bau­mes wer­den jetzt die bei­den Kno­ten betrach­tet, die an dem false- und true-Ast ent­stan­den sind. Zunächst erst mal der false-Ast. Die­ser ent­hält Daten, die alle das­selbe Label (Cert­hidea Oli­va­cea) besit­zen. Aus den Attri­bu­ten (siehe Tab. 1) ent­nimmt man, dass es keine mög­li­che Fra­gen gibt, die diese Daten­menge wei­ter in Unter­men­gen auf­tei­len könnte. Die­ser Kno­ten wird damit zu einem Blatt. Der true-Ast besitzt eine Daten­menge, die noch wei­ter unter­teilt wer­den kann.

Ein Ver­gleich der Attri­bute der noch vor­han­de­nen Daten ergibt, dass nur noch eine mög­li­che Frage gestellt wer­den kann. Die Schna­bel­grö­ßen haben alle den Wert 55, aber in der Farbe des Gefie­ders gibt es noch Unter­schiede. Da es sich um ledig­lich zwei Far­ben (schwarz und braun) han­delt, sind die Fra­gen “== schwarz ?” und “== braun ?” äqui­va­lent und der Test nach dem infor­ma­tion gain red­un­dant. Wir wäh­len in die­sem Bei­spiel die Frage “== braun” (siehe Abb. 4).  Es ent­ste­hen wie­der zwei Kno­ten, wel­che die­ses Mal beide zu Blät­ter wer­den. Da keine wei­te­ren Kno­ten ent­ste­hen, an denen die Daten wei­ter sepa­riert wer­den kön­nen, ist der Baum somit kom­plett. Die Abb. 5 stellt den fer­ti­gen Baum dar. Ver­gleicht man die ein­zel­nen Blät­ter, erkennt man, dass zwei Blät­ter einen Gini-Index von L=0 und ein Blatt L=0,5 besit­zen. Das liegt daran, dass in unse­ren (bzw. Dar­wins) Test­da­ten zwei Fin­ken unter­schied­li­cher Art die sel­ben Attri­bute auf­wei­sen (Schna­bel = 5 und Farbe = schwarz).

Die anfangs erwähn­ten Bio­lo­gen kön­nen jetzt mit Hilfe die­ses Bau­mes die neu ent­deckte Art mit einer gewis­sen Wahr­schein­lich­keit oder einem gewis­sen Kon­fi­denz­ni­veau Dar­wins Daten zuord­nen. Ange­nom­men der ent­deckte Vogel hätte eine Schna­bel­größe von 6 und ein blaues Gefie­der, dann könnte man den Vogel mit einem Kon­fi­denz­ni­veau von 50% der Art Geo­spitza Magni­rostris oder Geo­spitza For­tis zuordnen.

Zusam­men­fas­sung und Ausblick

Anhand die­ses Bei­spiels erkennt man, wie ent­schei­dend die Trai­nings­da­ten für die Aus­sa­ge­kraft sind. Aller­dings tre­ten bei zu vie­len oder auch inkor­rek­ten Trai­nings­da­ten Arte­fakte auf, die beson­ders Behan­delt wer­den müs­sen. Beim pru­ning bei­spiels­weise kann die Länge eines Bau­mes vor­de­fi­niert wer­den, sodass die­ser nicht zu groß wird. Das Phä­no­men tritt vor allem bei kon­ti­nu­ier­li­chen Attri­but-Wer­ten auf, die Gegen­stand kom­ple­xe­rer Ent­schei­dungs­fin­dungs­stra­te­gien sind.