Redigerer 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 [[objekt]]er 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 [[Lineær regresjon|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.

{| class="wikitable"
|-
! 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))<br />'''

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²) <big>∧</big> Pris(r, p) <big>∧</big> Pris(r², p²) <big>∧</big> 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 [[sannhetstabell]]en 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.

{| class="wikitable"
|-
! 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 ===
*[http://www.prenhall.com Prenhall,com]

== Litteratur ==
*{{kilde bok
| forfatter=Stuart Russel og Peter Norvig
| år=2003
| tittel=Artificial Intelligence – a modern approach
| isbn=0-13-080302-2
| forlag=Pearson Education
}}

{{Autoritetsdata}}

[[Kategori:Informatikk]]
[[Kategori:Algoritmer]]
[[Kategori:Kunstig intelligens]]