Læring ved hjelp av beslutningstrær

I Høit nr 2 1999 hadde Ky Van Ha artikkelen Information Measurement. Sentralt i den var begrepet entropi. Dette er et velkjent begrep som er brukt i mange sammenhenger. Arrtikkelen ga en innføring samt anvendelser av teorien. Jeg ble inspirert av den til å vise en annen anvendelse der det kun gjøres bruk av definisjonen på begrepet. Det medfører at man ikke trenger allverdens matematiske kunnskaper for å tilegne seg denne artikkel.

Når det foreligger informasjon og man ønsker å strukturere den i et beslutningstre, så kan dette gjøres på svært mange måter. Mangfoldet vil inneholde korte, lange/dype, breie og smale trær. Det vil da være lite lurt å pukke ut et tre på måfå for videre bruk. Det vil derfor være ønskelig å få fatt i det treet som er mest mulig kompakt og informativt - kort og godt et optimalt tre. Det er naturlig å la en datamaskin gjøre jobben. Algoritmen i denne sammenheng vil gjøre bruk av entropibegrepet. Så snart beslutningstreet er funnet, kan systemet blant annet bruke det til å lære. Vår anvendelse ligger i denne gaten. For at systemet skal lære om et problem, må det få tilført informasjon. I en læreprosess er det svært vanlig å kjøre flere treningseksempler som blir da informasjonskilden om det foreliggende problemet og dermed basis for trekonstruksjonen.

Innføring: Informasjonsteori

Vi starter med en enkel innføring i informasjonsteori. La X være en diskret stokastisk variabel som kan anta verdiene/tilstandene i mengden {x₁, x₂, ..., x_n}. Det er vanlig ikke å bruke indeks på x for å få det mer generelt. Sannsynligheten for at X antar en av verdiene i mengden skriver vi P(X = x), som igjen forkortes til p(x). Entropien til X er definert ved

H(X) = -         (1)

der det summeres over alle verdier x som X kan anta. Grunntallet i logaritmen kan for eksempel være e (naturlige logaritmer) eller 2. (Entropien er den gjennomsnittlige usikkerhet for spesielle verdier x som X kan anta, der usikkerheten er målt ved ( - log p( x)). Det er med andre ord den gjennomsnittlige størrelsen på den oppnådde informasjon gitt at X antar verdien x dersom p( x) er kjent på forhånd.)

Begrepet entropi er hentet fra termodynamikken og ble i sin tid tilpasset dataverden og telematikk med 2 som sentralt grunntall. Derfor bruker man ofte begrepet informasjonsinnholdet, I, i stedet for entropi (H). En justering av (1) blir da: Dersom hvert mulig svar, s_i (i = 1, 2, 3, ..., n), på et spørsmål har sannsynligheten p( s_i), så vil I for det aktuelle svar være gitt ved

I( p( s₁), p( s₂), ..., p( s_n)) = - p( s_i)log₂ ( p( s_i))         (2)

der (- log₂ ( p( s_i))) har som formål å veie den tilhørende sannsynlighet.

Hva sier nå en slik formel? La oss anvende den på det å kaste krone/mynt med et pengestykke. Hva er informasjonen i å gjøre et slikt kast? Det er bare to utfall for et kast: enten krone eller mynt. Er pengestykket korrekt, er sannsynligheten for å få krone ½ og den negerte hendelsen mynt har dermed sannsynligheten (1- ½) = ½. Informasjonsinnholdet som ligger i utfallet å kaste et pengestykke, vil da ifølge (2) i tekst være:

I( kaste et pengestykke) = I( sannsynlighet for krone, sannsynlighet for mynt)

= - p( krone)log₂ ( p( krone)) - p( mynt)log₂ ( p(mynt))

som i tallform blir:

I(,) = - ()log₂ () - ()log₂ () = - ()(-1) - ()(-1) = 1         (3)

Dersom vi kaster et skadd pengestykke, der erfaring har vist at ¾ av kastene gir krone og dermed ¼ av kastene mynt, vil informasjonsinnholdet for utgangen for dette kastet være tilsvarende som (3):

I(,) = - ()log₂ () - ()log₂ () = - ()(-0,415) - ()(-2) = 0,811         (4)

Definisjonen i (1) er slik at desto lavere verdi desto mindre "kaos" (da økende entropi forteller noe om økende "kaos" i universet og dermed er begrepet blant annet knyttet til miljøforurensning). Dersom man vil satse penger på utfallet av et pengestykke, er et veddemål der det skadde pengestykket brukes å foretrekke fordi verdien i (4) er lavest. (Dette var selvsagt ikke noe overraskende, men hensikten med eksemplet var å gi en begrunnelse for at formelen er et bra mål for innformasjonsinnholdet.)

(Det er vanlig å angi verdien formelen i (2) gir ved å tilføye "enheten" bit. Svaret i (3) blir da 1 bit og det i (4) 0,811 bits.)

Beslutningstrær

Læring ved hjelp av beslutningstrær er en av de enkleste og likevel mest suksessfulle former for læremetoder. Vi vil belyse metoden gjennom et (svært forenklet) eksempel. En høgskole er plassert i en tre-etasjes bygning. Ved høgskolen er det flere avdelinger der hver avdeling disponerer auditorier, laboratorier og grupperom. I enkelte av rommene er det plassert minst en datamaskin. Et dataprogram har som mål å få en oversikt over hvilke rom som har datakraft og kjører i den forbindelse åtte treningseksempler. Når programmet kjører et eksempel, så har den visse forhold å forholde seg til. Programmet velger følgende forhold, kalt attributter: avdeling, romstørrelse, romtype og etasje. Til hvert attributt knyttes det verdier: 1) avdeling har to verdier som angir avdelingene ved høgskolen: data og kjemi, 2) romstørrelse har tre verdier som angir størrelsen på et rom: lite, middels og stort, 3) romtype har følgende verdier: auditorium, laboratorium og grupperom og 4) verdier av etasje er: første, andre og tredje. Resultatene av treningseksemplene er gitt i figur 1 der det også er angitt målet - om et rom har en datamaskin eller ei.

I et beslutningstre vil et attributt være en node og grenene (nedover) fra noden vil være verdiene til attributtet. Skal programmet danne seg et bilde på grunnlag av treningseksemplene, må den velge seg ut et attributt fra tabellen i figur 1. Den velger å starte med avdeling. På neste nivå i treet må den velge et nytt attributt (som brukes på flere av nodene) eller flere forskjellige nye attributter. Denne prosessen gjentas inntil målene til programmet kommer fram som bladnoder. Et forslag til beslutningstre er vist i figur 2 der de bladnoder som gir ingen informasjon angående datamaskin er sløyfet. (Spørsmålstegnene bak attributtene skal vi kommentere litt senere.) I bladnodene har vi markert både romnummer og om et rom har datamaskin. Problemet med treet er at det er ikke særlig nyttig til å generere nye eksempler. For eksempel forteller det ingen ting om størrelsen på rommene på kjemiavdelingen. Et annet forslag til beslutningstre er vist i figur 3 ved at det er brukt attributtet romtype i startnoden. Dette treet har tilsvarende mangler som det i figur 2 da det mangler informasjon som er tilgjengelig i figur 1, men det har en klar styrke i forhold til det første - det er mer kompakt - og dermed å foretrekke. Det er verd å merke seg at disse to trærne, samt alle de andre som kan dannes

Figur 2

på grunnlag av figur 1, er konsistente med treningsdataene. Ved at det gjøres et valg, så er det brukt partiskhet. I dette tilfellet er den basert på et prinsipp, som er svært mye brukt, Occams barberhøvel oppkalt etter den engelske logikeren William of Occam i det 14. århundre. En forenklet beskrivelse av prinsippet sier: Den enkleste hypotesen som er konsistent med observasjonene skal velges.

Figur 3

Vi skal se litt nærmere på hvorfor treet i figur 3 ble så mye enklere enn det i figur 2. Et viktig valg er det første attributtet som velges ut. I figur 1 er det fire attributter å velge mellom. La oss bare

forholde oss til attributtene avdeling og romtype. I henholdsvis figur 4(a) og figur 4(b) har vi i tillegg til å tegne inn rotnoden og grenene har vi dessuten angitt de målene som er positive og de som er negative, dvs de rommene med datamaskin har fått notasjonen ja og de uten nei. På neste nivå i trærne ser vi klar forskjell. I treet i figur 4(a) har ingen mål blitt skilt ut, mens det i figur 4(b) får skilt ut hele fem mål og dermed gjenstår bare tre igjen. Den videre gang for hvert av de to påbegynte trærne har vi ikke tatt med, men sluttresultatene kan bli de som er angitt i figur 2 og 3 eller andre.

La oss anta et beslutningstre for et problem basert på treningseksempler foreligger. La oss så anta det dukker opp et nytt ukjent eksempel. Vi ønsker å klassifisere eksemplet ved hjelp av det foreliggende beslutningstre. I bladnodene til treet ligger svaret. Det ukjente eksemplet blir da klassifisert når det faller sammen med en av bladnodene. For å komme dit må vi starte i rotnoden. I rotnoden er det et attributt og medfører følgende spørsmål: Hvilken verdi har attributtet til det ukjente eksemplet? Svaret her medfører at vi følger en bestemt gren (nedover) fra rotnoden og kommer til en ny node og dermed et nytt spørsmål. Slik gjentas det hele inntil vi havner i en bladnode og dermed er eksemplet klassifisert. Vi skjønner at jo dypere et tre er desto flere spørsmål må vi besvare. Dette er en av grunnene til at vi ønsker et tre så kompakt som mulig.

Utvikle et kompakt beslutningstre

Nå skal vi anvende teorien på de åtte treningseksemplene i figur 1 og vise at metoden gir beslutningstreet i figur 3 som det beste treet for dette problemet.

Skal læring ved hjelp av beslutningstre fungere tilfredsstillende, må beslutningstreet være korrekt.

De situasjonene som vi skal knytte sannsynlighet til, er av tilsvarende karakter som det å kaste med et pengestykke eller trekke en kule fra en urne. Dersom det kjøres et bestemt antall treningseksempler for et problem der antall positive eksempler er p og antall negative eksempler er n, så er sannsynligheten for et positiv svar (p/(p + n)), dvs antall positive eksempler dividert med samlet antall eksempler, og dermed må sannsynligheten for et negativt svar være (n/(p + n)). Da vil ifølge (2) informasjonsinnholdet i korrekt svar være:

            (5)

der I( 1, 0) = I( 0, 1) = 0. For problemet i figur 1 må p = 4 og n = 4 fordi det er fire rom som har datamaskin og fire som ikke har. Dermed blir informasjonsinnholdet i denne figur ifølge (5) lik det i (3).

Informasjonsinnholdet i (5) må korrigeres fordi det må tas høyde for informasjonen som ligger i attributtene. La oss starte med et attributt A i roten. En test på A vil vanligvis ikke gi så mye informasjon, men dog noe. Vi kan måle eksakt hvor mye ved å studere hvor mye informasjon vi får etter testingen av attributtet. Ser vi for eksempel på figur 4(b), blir treningseksemplene delt opp i tre undermengder etter at attributtet romtype (i roten) er besvart. Navnene på grenene gir svarene på attributtet. Det betyr at informasjon ligger i de undermengdene som oppstår etter at et attributt er besvart. Går vi igjen tilbake til figur 4(b), ser vi at dersom svaret er auditorium vil den tilhørende undermengde bestå av to positive eksempler og et negativt eksempel. Denne betraktningsmåte kan vi lett gjøre generell.

La attributtet A resultere i en oppsplitting i undermengdene U₁, U₂, ..., U_m. Hver undermengde U_i (i = 1, 2, ..., m) vil ha p_i positive eksempler og n_i negative eksempler, så dersom vi går (nedover) den tilhørende gren trenger vi en tilleggsinformasjon I( p_i/(p_i + n_i), n_i/(p_i + n_i)), som regnes ut tilsvarende som (5)), til å svare på spørsmålet. Siden antall eksempler i roten er (p + n), vil sannsynligheten for at undermengden U_i skal inntreffe være (p_i + n_i)/(p + n). Den forventede informasjon som trengs for å fullføre treet når A er plassert i roten er:

E( A) =             (6)

Informasjonsgevinsten fra attributtet A er definert ved

gevinst( A) = I( - E( A)             (7)

Dersom det er flere attributter å velge mellom, så skal det attributtet velges som har høyest gevinst.

La oss konkretisere dette ved å bruke treningseksemplene i figur 1 til å finne ut hvilke rom på høgskolen som har datamaskin. Figuren viser som sagt at p = 4 og n = 4. Vi starter med roten i beslutningstreet som skal utvikles. Siden vi har fire attributter (avdeling, romstørrelse, romtype og etasje), må vi regne ut gevinsten for hvert av dem. Vi velger å gjennomføre fullstendig regning på attributtet romtype. Vi kan i den forbindelse støtte oss på figur 4(b). Oppdelingen av treningseksemplene gir følgende tre undermengder: U₁ = ( {ja: C2, B3}, {nei: A3}), dvs p₁ = 2 og n₁ = 1, U₂ = ( {ja: }, {nei: B1, C1, A2}), dvs p₂ = 0 og n₂ = 3, U₃ = ( {ja: A1, B2}, {nei: }), dvs p₃ = 2 og n₃ = 0. (7) sammen med (6) gir

gevinst( romtype) = I(,) - [             (8)

Siden I( 1, 0) = I( 0, 1) = 0 og dessuten kommer (3) oss til hjelp, trenger vi bare å regne ut I( 2/3, 1/3) ved å bruke (5). (8) blir da

gevinst( romtype) = 1 - [0,918 + 0 + 0] = 0,656             (9)

Dernest blir det å gjennomføre samme regning for de tre andre attributtene. Resultatene blir henholdsvis

gevinst( avdeling) = 0; gevinst( romstørrelse) = 0,062; gevinst( avdeling) = 0,062             (10)

Sammenlikner vi verdiene i (9) og (10), slutter vi at det må velges attributtet romtype i roten. Dermed har vi fått fram at det mest kompakte beslutningstre framkommer ved å videreutvikle treet i figur 4(b). (Vi ser også at det dårligste treet får vi ved å videreutvikle treet i figur 4(a).)

Resultatet så langt er treet i figur 4(b). Vi må dernest bestemme attributtet i hvert av de tre nye

nodene. Hver av de tre nodene behandles som en "rotnode" og dermed blir det tre helt tilsvarende beregninger som ovenfor. Men vi oppdager fort at her slipper vi svært billig fra det. Det er bare den ene noden som trengs videreutvikles (U₁ = ( {ja: C2, B3}, {nei: A3})). Gjennomføres så regningen, så vil det gi at attributtet skal være avdeling. Treet som framkommer er det i figur 3, som er det mest kompakte beslutningstreet for problemet på høgskolen: hvilket rom har datamaskin.

Selv om denne algoritme gir enkle beslutningstrær, er det ikke øyensynlig at slike trær vil være effektive når nye ukjente eksempler skal klassifiseres. Algoritmen har vært testet i både kontrollerte tester og anvendelser og har vist seg å fungere bra i praksis. Innen helsesektoren har man gjort bruk av beslutningstrær i en rekke forbindelser med bra suksess. Leger har brukt beslutningstrær ved diagnostisering av hjerteinfarkt. Ved pleie og behandling av slike pasienter har man også brukt slike trær.