Beslutningstre

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

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[1]. Kort sagt er dette når et system prøver å lage noe regler for å tolke det som er observert. Beslutningtre er hardfør ovenfor støyende data (eng.: noisy data) og dette betyr for eksempel at det som observeres ikke kan tolkes direkte av en datamaskin (tekstdokument, mediefiler o.l.). For at systemet skal kunne lære, bruker det beslutningstreet for å tolke informasjonen, dvs. utføre tester på hvert "trinn" og lage nye grener på treet for å komme frem til et resultat.

Denne artikkelen skal beskrive de grunnleggende elementene i et beslutningstre og gi en kort forklaring hvordan disse implementeres.

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: Været har atributter som sol, regn , overskyet osv.). Ved å returnerer en aksjon eller handling basert på regler lages det nye noder, output og input. Disse kan enten være diskrete (se diskret matematikk) som i et tastetrykk, eller kontinuerlige, som er data i/under forandring. Det finnes flere metoder for å lære diskrete funksjoner, disse kalles for classification learning og for å finne kontinuerlige data som er regresjon.

Denne artikkelen skal vise til en boolsk metode eller klassifisering, hvor eksemplene vil ha verdier som true (positive) eller false (negative).

Et beslutningstre finner løsninger ved å utføre en rekke tester. Hver interne node (se foto i artikkel) i treet tilhører en slik test, hvor egenskapen av foregående verdi står som resultat, utfra denne noden (se: Grafteori) vil alle kantene bestå av mulige verdier av testen. La oss ta et eksempel fra logikk og finne et mål predikat (eng.: goal predicate ) som kan være VilVentePå i et domene vi kaller bussen. Når vi setter opp dette predikatet som læringseksempel, bør vi finne 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?

Nå kan vi ved hjelp av et enkelt beslutningstre finne ut om vi vil vente på bussen eller ikke! (se foto til høyre)

Besluttningstre wiki oppg

Ekspressivitet av beslutningstre[rediger | rediger kilde]

Når vi snakker om logikk, så kan bortimot alle hypoteser for VilVentePå et beslutningstre bruke en 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. Det er verdt å legge merke til at et beslutningstre beskriver relasjonen mellom VilVentePå og noen logiske kombinasjoner av egenskapenes verdier.

Vi kan derimot 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?)

Denne artikkelen vil ikke gå nærmere inn på bruk av flere objekter, men det kan nevnes at 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 triviellt 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å.

Med andre ord så er beslutningstre bra for noen former for funksjoner, men ikke så bra for andre.

Induktiv beslutning ved hjelp av eksempler[rediger | rediger kilde]

Vi kan ved hjelp av eksempler hvor en vektorisert variabel x gir oss informasjon om hver atributt og danner grunnlag for videre iterasjon av treet. Et slikt eksempelsett kalles gjerne for treningssett og ved hjelp av verdiene kan vi 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 vi bruke det som man i informasjons teori kaller for entropi, en metode som brukes for å finne noe som er målbart når vi snakker om usikkerhet i en tilfeldig variabel. Gitt et datasett (som eksempelet ovenfor) S, som inneholder både positive (TRUE/YES) og negative (FALSE/NO) verdier, entropien blir da relativt til settet:

         Entropi(S) = - p(positive) log² p(positive) - p(negative) log² p(negative)  

Hvor p er proposjonen til positive og negative eksempler i settet delt på det totale antall av eksempler.

Husk på at i entropi kalkylen, hvor 0 log 0, er p alltid 0. Entropien blir da som følger for eksempel S:

        Entropi([2+, 3-]) = -(2/5) log²(2/5) - (3/5) log²(3/5)
             = 0.970 
            (kan også vises slik: -(2/5)*log(2/5,2)-(3/5)*log(3/5,2))  

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

Derivative Works Decision Tree

Referanser[rediger | rediger kilde]

[1]

  1. ^ a b www.prenhall.com

Litteratur[rediger | rediger kilde]

  • Stuart Russel & Peter Norvig (2003): Artificial Intelligence – a modern approach, ISBN: 0-13-080302-2, Pearson Education