Nach­dem im letz­ten Teil ein Data Mining Algo­rith­mus als Bestand­teil eines Recom­men­da­tion Sys­tems erläu­tert wurde, soll der Algo­rith­mus die­ses Bei­tra­ges in der Lage sein Pre­dic­tions (dt. Vor­her­sa­gen) über das Nut­zer­ver­hal­ten zu tref­fen. Dafür betrach­ten wir Ran­dom Forest und die Vor­züge gegen­über Decis­ion Trees. Für einen Ein­stieg in Decis­ion Trees emp­feh­len wir vor dem Wei­ter­le­sen fol­gen­den Bei­trag in unse­rem Blog.

Gren­zen von Decis­ion Trees

Ran­dom Forest basiert auf Decis­ion Trees (dt. Ent­schei­dungs­bäu­men). Abs­trakt gespro­chen bil­den Ent­schei­dungs­bäume die mensch­li­che Ent­schei­dungs­fin­dung com­pu­ter­in­ter­pre­tier­bar nach. Ziel ist es, die Daten­menge in mög­lichst homo­gene Grup­pen ein­zu­tei­len, die unter­ein­an­der mög­lichst hete­ro­gen sind. Dabei tre­ten zwei Arten von Feh­lern auf. Um die bei­den Feh­ler­ty­pen zu ver­ste­hen, ist es wich­tig sich zu über­le­gen wie Ent­schei­dun­gen getrof­fen wer­den. Die Algo­rith­men ope­rie­ren auf Daten. Sie suchen nach häu­fig auf­tre­ten­den Mus­tern und deren Kor­re­la­tio­nen. Ver­läss­li­che Aus­sa­gen las­sen sich dabei nur auf Grund­lage von gro­ßen Daten­men­gen treffen.

Bei der mensch­li­chen Ent­schei­dungs­fin­dung gren­zen wir die Ergeb­nis­menge ein. Dabei gilt: Je stär­ker die Ergeb­nis­menge ein­ge­grenzt wer­den kann, desto genauer das Ergeb­nis. Was für uns eine logi­sche Schluss­fol­ge­rung ist, kann für den Rech­ner das Gegen­teil bewir­ken. Denn dem Rech­ner steht in Form von Daten nur ein begrenz­tes „Wis­sen“ zur Ver­fü­gung. Gren­zen wir die Ergeb­nis­menge wei­ter ein, ver­rin­gert sich die Daten­menge, also das „Wis­sen“. Trifft der Algo­rith­mus in folge des­sen Ent­schei­dun­gen auf die­ser gerin­gen Daten­menge, bewer­tet er eine Situa­tion ohne aus­rei­chende „Wis­sens­grund­lage“. Dies führt zum so genann­ten Over­fit­ting (dt. Über­an­pas­sung), weil sehr kleine Teil­men­gen über­pro­por­tio­nal bewer­tet wer­den. In Kon­se­quenz wer­den Vor­her­sa­gen für bereits bekannte Aus­gangs­si­tua­tio­nen sehr genau pro­gnos­ti­ziert, die Gene­ra­li­sie­rung der Ent­schei­dungs­re­geln auf unbe­kann­ten Daten lei­det jedoch. Im Ergeb­nis lernt der Algo­rith­mus die Trai­nings­da­ten auswendig.

Die fol­gende Abbil­dung visua­li­siert das Pro­blem des Over­fit­tings anhand eines Poly­nom drit­ten Grades:

Ein Ansatz, um Over­fit­ting zu ver­hin­dern, nennt man Pru­ning. Pru­ning bezeich­net die Begren­zung der Tiefe eines Ent­schei­dungs­bau­mes. Der Ansatz ist effek­tiv aber rigo­ros, denn er führt direkt zum zwei­ten Fehlertyp:

Um die Ergeb­nis­menge ein­zu­schrän­ken, bleibt nur die Mög­lich­keit Fra­gen bezüg­lich der Beschaf­fen­heit der Daten zu stel­len. In dem Moment, in dem sich jemand über­legt, wel­che Frage er stellt, um einen mög­lichst homo­ge­nen Teil der Daten zu selek­tie­ren, nimmt er Ein­fluss auf das Ergeb­nis. Die­ses Pro­blem beschreibt der Bias (dt. Befan­gen­heit). Wenn nun also mit­tels Pru­ning ein Teil des Ent­schei­dungs­bau­mes abge­schnit­ten wird, wird zwangs­läu­fig auch das Ergeb­nis manipuliert.

Ran­dom Forest

An die­ser Stelle kommt der Ran­dom Forest ins Spiel. Die­ser besteht aus einer Viel­zahl von Ent­schei­dungs­bäu­men (Forest), die zufäl­lig gene­riert wer­den (Ran­dom). Der Zufall wird dabei durch den Algo­rith­mus bestimmt, denn er bil­det aus den vor­ge­ge­be­nen Ent­schei­dungs­bäu­men eine Viel­zahl neuer, klei­ne­rer Ent­schei­dungs­bäume, die jeweils Teil­bäume der ursprüng­li­chen Ent­schei­dungs­bäume dar­stel­len. Durch den Ein­satz von Teil­bäu­men wird das Pro­blem des Over­fit­ting umgan­gen, wäh­rend die Menge an Teil­bäu­men den Bias redu­zie­ren, indem ein Mit­tel aus den Ent­schei­dun­gen vie­ler Teil­bäume gebil­det wird.

So viel zum Auf­bau des Ran­dom Forest, aber wie nutzt man den Algo­rith­mus zur Opti­mie­rung der Web­site? Ran­dom Forest wird bei­spiels­weise für Klas­si­fi­ka­ti­ons­pro­bleme ein­ge­setzt. Klas­si­fi­ka­ti­ons­pro­bleme bedür­fen einer appro­xi­mier­ten map­ping-Funk­tion, um von einem Start­zu­stand X zu einem defi­nier­ten End­zu­stand Y zu kom­men. Y wird dabei häu­fig als Klasse, Label oder Kate­go­rie bezeich­net, daher der Name Klas­si­fi­ka­ti­ons­pro­blem. Regres­si­ons­pro­bleme wer­den im Bei­spiel außen­vor gelassen.

Der Start­zu­stand wird in unse­rem Bei­spiel durch die Aus­prä­gun­gen der aktu­el­len Ses­sion eines Kun­den dar­ge­stellt, der End­zu­stand könnte z.B. eine bestimmte Pro­dukt­ka­te­go­rie oder ein ein­zel­nes Pro­dukt sein. Letz­ten Endes ist man damit in der Lage, den nächs­ten Klick des Kun­den zu pro­gnos­ti­zie­ren. Das Wis­sen über den nächs­ten Klick impli­ziert gleich­zei­tig das Inter­esse des Kun­den. In dem Moment in dem der Betrei­ber einer Web­site weiß für wel­che Pro­dukte sich ein Kunde inter­es­siert, ist er in der Lage seine Web­site dyna­misch anzu­pas­sen, um dem Kun­den die Dinge die er sucht auf einen Blick bereit­zu­stel­len oder ihn mit beson­de­ren Ange­bo­ten zu locken.

Fazit

In die­sem Arti­kel wur­den die Vor­züge eines Ran­dom Forest gegen­über ein­fa­chen Decis­ion Trees erläu­tert. Außer­dem haben wir gese­hen, dass Algo­rith­men in der Lage sind Nut­zer­ver­hal­ten zu pro­gnos­ti­zie­ren. Neben dem Vor­ge­stell­ten Algo­rith­mus gibt es eine Viel­zahl an Algo­rith­men die weit­rei­chende Opti­mie­rungs­mög­lich­kei­ten bie­ten. Als Aus­blick sol­len an die­ser Stelle Neu­ro­nale Netze genannt werden.

Neu­ro­nale Netze wer­den für ver­gleich­bare Pro­blem­stel­lun­gen wie klas­si­sche Machine Lear­ning Algo­rith­men ein­ge­setzt. Sie sind dabei jedoch leis­tungs­stär­ker und erzie­len bes­sere Ergeb­nisse. Im Gegen­satz zu den klas­si­schen Lösungs­an­sät­zen benö­ti­gen sie dafür deut­lich mehr Rechen­leis­tung. Dadurch gilt es im Ein­zel­fall zu ent­schei­den, wel­cher Algo­rith­mus die bes­sere Vari­ante ist.