Maskinlæringsteknikker for klassifisering

Abstract

This diploma thesis treats classification tasks in machine learning. It focuses on three types of classification algorithms: support vector machines, neural nets and decision trees. The scope of its treatment of neural nets is limited to feedforward nets (i.e. neural nets without internal feedback loops), trained by backpropagation. Several types of decision trees exist. This thesis focuses on an algorithm called C4.5. As a part of the thesis, a classification module was written in VisualWorks 3.0 Smalltalk. The module consists of three submodules, each implementing one of the classification techniques mentioned. The three modules were tested on non-trivial examples. Some of the experiments showed that the classifiers were able to learn the training data perfectly, and that their parameters could be set to achieve good generalisation as well.

Denne diplomoppgaven er gitt av Forsvarets Forskningsinstitutt. Oppgaven omhandler klassifisering i maskinlæring. Klassifisering i maskinlæring benyttes i f.eks mønstergjenkjenning og beslutningsstøtte. Klassifiseringsalgoritmene må kunne lære og de må kunne generalisere. Læringen kan foregå ved at klassifiseringsalgoritmene grupperer objekter som ligner på hverandre i klasser eller at de blir gitt eksempler på objekter som tilhører forskjellige klasser. Generaliseringen består i at klassifiseringsalgoritmene kan klassifisere objekter som de ikke har sett før. Denne diplomoppgaven omhandler tre typer klassifiseringsalgoritmer: Støttevektormaskiner, nevrale nettverk og beslutningstrær. Støttevektormaskiner er basert på å representere kunnskap som punkter i et egenskapsrom og separere forskjellige klasser ved hjelp av et optimalt plan som kalles hyperplan når det er mer enn tre egenskaper/dimensjoner. Nevrale nettverk er bygd opp av kunstige nevroner som etterlikner noe av funksjonaliteten til biologiske nevroner. Signalene som overføres mellom nevronene blir vektet. Når nettverket lærer, justeres denne vektingen. Dette kan sammenliknes med justeringen av koblingen mellom biologiske nevroner. Oppgaven omhandler nettverk uten interne tilbakekoblinger (“Feed Forward”-nettverk) som læres opp ved hjelp av tilbakepropagering (“Backpropagation”-algoritmen). Det fins flere typer beslutningstrær. I denne oppgaven fokuseres det på en algoritme som heter C4.5. Denne algoritmen benytter informasjonsteori for å konstruere beslutningstreet. Treet dannes ved å sammenligne nytten med hensyn til informasjonsverdi ved å splitte opp treningseksemplene på de mulige verdiene til en egenskap. Den egenskapen som gir best resultat velges som forgreningspunkt i treet og prosessen fortsetter rekursivt for de oppsplittede treningseksemplene. Som en del av oppgaven ble det skrevet en klassifiseringsmodul i Smalltalk/ VisualWorks3.0. Modulen består av tre moduler som implementerer hver av de omtalte klassifiseringsalgoritmene. Modulen som implementerer nevrale nettverk var skrevet fra før av ansatte ved FFI, så i forbindelse med den ble det bare skrevet kode som knytter den til resten av modulen. De tre modulene ble testet på ikke-trivielle eksempler. Resultatene viste at klassifiseringsmodulene hadde bra egenskaper med hensyn til å lære og til å klassifisere. Siden treningssettene var konsistente og uten støy, var det mulig å se om klassifiseringsalgoritmene var gode til å lære ved å lære dem opp og teste dem på samme datasett. Dette ga ingen feil. Generaliseringsevnen viste seg å være bra. Algoritmene feilklassifiserte mellom 3% og 11% av testdatasettet. Det nevrale nettverket viste best resultater.