Hopp til innhold

Beslutningstre

Fra Wikipedia, den frie encyklopedi

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

[rediger | rediger kilde]

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

[rediger | rediger kilde]

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

[rediger | rediger kilde]

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.

Litteratur

[rediger | rediger kilde]
  • Stuart Russel og Peter Norvig (2003). Artificial Intelligence – a modern approach. Pearson Education. ISBN 0-13-080302-2.