Beslutningstre

Beslutningstre (engelsk: decision tree) er innenfor kunstig intelligens en av de enklere læringsalgoritmene. Det brukes ofte innenfor induktiv læring, som er prosessen for å lære ved hjelp av eksempler og er svært enkel å implementere. Dette blir brukt når et system skal opprette regler for å tolke det som er observert. Beslutningtre er hardfør overfor «støyende data» (eng.: «noisy data»), det vil si informasjon som ikke kan tolkes direkte av en datamaskin (slik som tekstdokumenter og mediefiler). For at systemet skal kunne lære, bruker det beslutningstreet for å tolke informasjonen ved å utføre tester på hvert «trinn» og opprette nye grener på treet for å komme frem til et resultat.

 Ytelseskriterier 
Et beslutningstre tar imot objekter eller situasjoner som beskrives av et sett av egenskaper (også kalt attributter), og skal si noe om hvordan tilstanden er (for eksempel har vær attributter som sol, regn og overskyet). Ved å returnere en handling basert på regler blir det opprettet nye noder, output og input. Disse kan enten være diskrete (se diskret matematikk) som i et tastetrykk, eller kontinuerlige, det vil si data i forandring. Det finnes flere metoder for å lære diskrete funksjoner, disse kalles for classification learning og for å finne kontinuerlige data som er regresjon.

Et beslutningstre finner løsninger ved å utføre en rekke tester. Hver interne node i treet tilhører en slik test, hvor egenskapen av foregående verdi står som resultat. Ut fra denne noden (se: Grafteori) vil alle kantene bestå av mulige verdier av testen. I logikk kan man for eksempel finne et målpredikat (eng.: goal predicate ) som kan være VilVentePå i et domene med navn bussen. I denne modellen skal predikatet finne frem til egenskapene i dette domenet.

 NR  Node Tekst  1 Alternativ transport (AT) Finnes alternativ transport, buss-taxi-tog, ja eller nei? 2 Neste avgang  Hvor lang tid til neste avgang, kort eller lang? 3 Temperatur Hva er temperaturen der du står, kaldt eller ok? 4 Økonomi  Penger, lite eller nok til AT? 5 Avstand  Hvor langt skal du, innenfor rimelig gå avstand, ja eller nei? 6 Transport  Går det buss her?

Ved hjelp av et enkelt beslutningstre kan man finne ut om vi vil vente på bussen eller ikke.

 Ekspressivitet av beslutningstre 
Bortimot alle hypoteser for VilVentePå kan bruke et beslutningstre form tilsvarende denne:

∀(s) VilVentePå(s) ⇔ (P¹(s) V (p²(s) V...V Pⁿ(s))

hvor hver tilstand Pi(s) er sammensatt av tester som tilsvarer stien fra treets root til en kant (og neste node) med et positivt resultat. Et beslutningstre beskriver relasjonen mellom VilVentePå og noen logiske kombinasjoner av egenskapenes verdier.

Derimot kan man ikke bruke et beslutningstre for å representere tester som viser til to eller flere forskjellige objekter, for eksempel hvor r representerer "restaurant":

∃ r ∃ r²  Nærheten(r, r²) ∧ Pris(r, p) ∧ Pris(r², p²) ∧ Billigere (p, p²)

(Finnes det er restaurant i nærheten som er billigere?)

Ved bruk at boolske uttrykk og egenskaper kan man addere bruk av flere objekter, men dette vil være nærmest uløselig med tanke på alle egenskapene som må legges til.

Enhver boolsk variabel eller funksjon kan skrives i en beslutningstre-algoritme og er trivielt med at hver rad i en sannhetstabell tilsvarer funksjonens sti i treet (rot til node til kant til node osv.). Dette vil imidlertid føre til en eksponentielt lang tre representasjon, fordi sannhetstabellen vil ha eksponentielt mange rader, eksempel som ved bruk av en algoritme slik som ID3 og hvor rot noden representerer et dato felt, vil et bredde-først-søk føre til mange rader på første nivå.

 Induktiv beslutning ved hjelp av eksempler 

I et eksempelkan en vektorisert variabel x gi informasjon om hvert attributt og danne grunnlag for videre iterasjon av treet. Et slikt eksempelsett kalles gjerne for «treningssett», og ved hjelp av verdiene kan man finne neste node i iterasjonen.

 Eksempel nr.  Attributter       Goal   Transport  Neste avgang  Temperatur  Økonomi  Avstand  AT  VilVentePÅ X1  YES  < 10  Kaldt  OK  Langt  NO  YES X2  YES  < 10  Kaldt  OK  Kort  NO  NO X3  YES  10-30  Komfortabelt  0  Langt  YES  NO X4  NO  0  Kaldt  OK  Kort  YES  NO X5  YES  > 60  Varmt  OK  Medium  YES  YES

For å finne neste node i treet kan man bruke entropi, en metode for å finne noe som er målbart gitt en usikkerhet i en tilfeldig variabel. Gitt et datasett S, som inneholder både positive (TRUE/YES) og negative (FALSE/NO) verdier, blir entropien relativ til settet:
Entropi(S) = - p(positive) log² p(positive) - p(negative) log² p(negative)
hvor p er proporsjonen til positive og negative eksempler i settet delt på det totale antall av eksempler.

I entropikalkylen, hvor 0 log 0, er p alltid 0.
Entropien  for eksempel S blir:
Entropi([2+, 3-]) = -(2/5) log²(2/5) - (3/5) log²(3/5) = 0.970 
(Dette kan også vises slik: -(2/5)*log(2/5,2)-(3/5)*log(3/5,2))

Entropien gir altså muligheten for å måle tributtens effektivitet, slik at man kan sammenligne de forskjellige attributter og velge den høyeste verdien som grunnlag for neste node.

 Kilder 
Prenhall,com

 Litteratur 

Kategori:Informatikk
Kategori:Algoritmer
Kategori:Kunstig intelligens