formalnie:
Binarne drzewa decyzyjne
+ algorytm k-NN
Dorota Cendrowska
nieformalnie:
O mierzeniu zawartości cukru w cukrze (cd.)
+ dlaczego będąc wśród kruków trzeba krakać jak
one…
Plan wykładu
dyskretne drzewa decyzyjne
vs. binarne drzewa decyzyjne
„próg” w binarnych drzewach decyzyjnych dla:
atrybutów jakościowych o arności większej niż dwa,
dla atrybutów ciągłych
drzewa decyzyjne a brakujące wartości
liście probabilistyczne
przycinanie drzew
algorytm k-NN
własności
ograniczenia
drzewo decyzyjne
Drzewa decyzyjne [binarne]
ciepło
A4
OK
NOT
OK
A12
OK
NOT
OK
zimno
gorąco
nie pada
pada
drzewo decyzyjne
drzewo decyzyjne binarne
Drzewa decyzyjne [binarne]
ciepło
A4
OK
NOT
OK
A12
OK
NOT
OK
zimno
gorąco
nie pada
pada
low
A19
OK
med, high
A45
<=13
NOT
OK
>13
OK
Drzewa binarne: wybór progu
W ogólności atrybuty o wartościach
rzeczywistych można potraktować jako atrybuty
o arności równej |T|
Wybór atrybutu testowego oznacza ustalenie
„progu”
dla wszystkich atrybutów, których arność jest
większa niż dwa.
Drzewa binarne: wybór progu
W ogólności atrybuty o wartościach rzeczywistych
można potraktować jako atrybuty o arności równej |
T|
Wybór atrybutu testowego oznacza ustalenie „progu”
dla wszystkich atrybutów jakościowych, których
arność jest większa niż dwa.
W przypadku atrybutów ciągłych oznacza znalezienie
pierwszego progu w procesie dyskretyzacji (B.2)
Co w przypadku atrybutów porządkowych?
Co w przypadku atrybutów symbolicznych?
ważona entropia (B.2):
wybór progu:
można
wykorzystać fakt, że atrybut
jest atrybutem porządkowym
Wybór progu
(atrybuty jakościowe)
low
med high vhigh
ważona entropia (B.2):
wybór progu:
można wykorzystać fakt, że atrybut
jest atrybutem porządkowym
nie trzeba
wykorzystywać tej wiedzy,
jak wówczas „poukładać”
wartości na osi?
Wybór progu
(atrybuty jakościowe)
low
med high vhigh
low med high
vhigh
Wybór progu (atrybut porządkowy)
low
med high vhigh
Wybór progu (atrybut porządkowy)
low
med high vhigh
Wybór progu (atrybut porządkowy)
low
med
high vhigh
Wybór progu (atrybut porządkowy)
low
med
high
vhigh
Wybór progu (atrybut symboliczny)
low
med high vhigh
Wybór progu (atrybut symboliczny)
low med high
vhigh
Wybór progu (atrybut symboliczny)
low med high
vhigh
Wybór progu (atrybut symboliczny)
low
med high
vhigh
Wybór progu (atrybut symboliczny)
low
med
high
vhigh
Binarna dyskretyzacja atrybutów
(przykład)
Drzewa decyzyjne [binarne] (przykład)
low
A6
[20]
unacc
0/5
med, high
A4
[15]
2
unacc
0/3
4, more
A1
[12]
vhigh
unacc
0/1
low, med, high
A2
[11]
low
acc
0/2
med, high, vhigh
A3
[9]
2, 3, 4
acc
0/3
5more
A5
[6]
small
unacc
0/1
med, big
acc
0/5
A6
med
high
unacc
A5
small
med
big
unacc
acc
acc
A4
2
4
more
unacc
acc
acc
Drzewa z liśćmi probabilistycznymi
A6
[20]
unacc
0/5
atrybut
liczba przetwarzanych wierszy danych
ze zbioru uczącego
klasa
iloraz:
liczba wierszy danych ze zbioru uczącego (mianownik)
ile wierszy jest niepoprawnie klasyfikowanych (licznik)
low
A19
[123]
OK
0/23
med, high
NOT
OK
9/100
Drzewo binarne: dlaczego takie duże?
low
A6
[20]
unacc
0/5
med, high
A4
[15]
2
unacc
0/3
4, more
A1
[12]
vhigh
unacc
0/1
low, med, high
A2
[11]
low
acc
0/2
med, high, vhigh
A3
[9]
2, 3, 4
acc
0/3
5more
A5
[6]
small
unacc
0/1
med, big
acc
0/5
A6
med
high
unacc
A5
small
med
big
unacc
acc
acc
A4
2
4
more
unacc
acc
acc
low
A19
OK
med, high
A45
<=13
NOT
OK
>13
OK
Liście vs. liście probabilistyczne
Liście vs. liście probabilistyczne
low
A19
[123]
OK
0/23
med, high
A45
[100]
<=13
NOT
OK
0/91
>13
OK
0/9
low
A19
[123]
OK
0/23
med, high
NOT
OK
9/100
Liście vs. liście probabilistyczne
low
A19
[123]
OK
0/23
med, high
A45
[100]
<=13
NOT
OK
0/91
>13
OK
0/9
drzewa i „koszty”...
Które z tych drzew jest lepsze?
low
A19
[123]
OK
0/23
med, high
A45
[100]
<=13
NOT
OK
0/70
>13
OK
0/30
low
A19
OK
med, high
A45
<=13
NOT
OK
>13
OK
low
A19
[123]
OK
0/23
med, high
NOT
OK
9/100
cena drzewa: 3 500 zł
błąd klasyfikacji dla zbioru uczącego
=0.00
cena węzła 1000 zł, cena liścia 500 zł
cena drzewa: 2 000 zł
błąd klasyfikacji dla zbioru uczącego
=0.07
Nie ma nawet drzew idealnych...
życzenia:
aby drzewo było jak najmniejsze
(np. aby miało jak najmniej liści)
aby błąd klasyfikacji był jak najmniejszy
miara niedoskonałości drzewa T :
gdzie b jest liczbą błędnych klasyfikacji
przykładów
ze zbioru uczącego, zaś |Z| jego rozmiarem.
przycinanie drzewa: zastąpienie jego
wybranych poddrzew przez liście
dwie strony medalu:
pogorszenie klasyfikacji danych ze zbioru
uczącego (–)
[prawdopodobnie] polepszenie własności
klasyfikacji danych spoza zbioru uczącego (+)
mniejsze i prostsze drzewo (+)
oszczędność pamięci i większa efektywność
obliczeniowa (?)
Przycinanie
drzewa decyzyjnego
Zaniechanie kolejnych podziałów, gdy w węźle
jest mniej niż 5 przykładów, bądź mniej niż
procent całego zbioru uczącego.
Zaniechanie kolejnych podziałów, gdy procent
przykładów należy do tej samej klasy, np. =90%.
W obu przypadkach klasa(Z) oznacza
najczęściej reprezentowaną klasę w zbiorze Z.
Jest to
przycinanie drzewa
podczas jego
tworzenia
Kryterium stopu
strategie przycinania:
przycinanie podczas tworzenia drzewa (
pre-
pruning
)
[kryterium stopu]
przycinanie drzewa po utworzeniu pełnego
drzewa D (
post-pruning
)
[wymagane dwa zbiory Z uczący i P testowy
lub zastosowanie walidacji krzyżowej]
Przycinanie
drzewa decyzyjnego
post-pruning
:
minimalizacja kryterium kosztu-złożoności:
gdzie |T| jest rozmiarem drzewa.
Przycinanie
drzewa decyzyjnego
kryterium kosztu-złożoności dla =0, gdzie
funkcja oceny drzewa:
Przycinanie
drzewa decyzyjnego
(pseudokod)
Drzewo przytnij(T,P,akceptowanyJeszczeBłąd){
Lista<Drzewo> listaDrzewPozbawionychJednegoWezłaZJegoPodrzewem;
Drzewo minimalneDrzewo=T; // być może nie ma już lepszych drzew
błądMin=obliczWartośćKryteriumKosztuZłożoności(T,P);
for(Drzewo t: listaDrzewPozbawionychJednegoWezła){
błąd=obliczWartośćKryteriumKosztuZłożoności(t,P);
if (błąd<błądMin)
{ błądMinimalny=błąd; minimalneDrzewo=t; }
}
return minimalneDrzewo;
}
Przycinanie
drzewa decyzyjnego (przykład)
low
A6
[20]
unacc
0/5
med, high
A4
[15]
2
unacc
0/3
4, more
A1
[12]
vhigh
unacc
0/1
low, med, high
A2
[11]
low
acc
0/2
med, high, vhigh
A3
[9]
2, 3, 4
acc
0/3
5more
A5
[6]
small
unacc
0/1
med, big
acc
0/5
Przycinanie
drzewa decyzyjnego (przykład)
low
A6
[20]
unacc
0/5
med, high
A4
[15]
2
unacc
0/3
4, more
A1
[12]
vhigh
unacc
0/1
low, med, high
A2
[11]
low
acc
0/2
med, high, vhigh
A3
[9]
2, 3, 4
acc
0/3
5more
A5
[6]
small
unacc
0/1
med, big
acc
0/5
low
A6
[20]
unacc
0/5
med, high
A4
[15]
2
unacc
0/3
4, more
A1
[12]
vhigh
unacc
0/1
low, med, high
acc
1/11
błąd klasyfikacji
dla zbioru
uczącego =0.09
Podsumowanie, własności drzew
drzewa umożliwiają klasyfikowanie danych
z brakującymi wartościami, na przykład:
low
A6
[20]
unacc
0/5
med, high
A4
[15]
2
unacc
0/3
4, more
A1
[12]
vhigh
unacc
0/1
low, med, high
acc
1/11
?
Podsumowanie, własności drzew
drzewa umożliwiają klasyfikowanie danych
z brakującymi wartościami, na przykład:
low
A6
[20]
unacc
0/5
med, high
acc
4/15
!
low
A6
[20]
unacc
0/5
med, high
A4
[15]
2
unacc
0/3
4, more
A1
[12]
vhigh
unacc
0/1
low, med, high
acc
1/11
?
Podsumowanie, własności drzew
niewrażliwość na brakujące dane, (+)
niewrażliwość na typy atrybutów (porządkowe,
symboliczne, liczbowe), (+)
drzewa umożliwiają naturalną ocenę ważności
danego atrybutu ze względu na prowadzoną
klasyfikację, (+)
złożoność struktury drzewa (?)
„kształt” tworzonego drzewa
ściśle zależy od zbioru uczącego
(–)
Algorytm k-NN
algorytm k-NN (nearest neighbours),
algorytm k najbliższych sąsiadów
algorytm umożliwia klasyfikację
wynik działania algorytmu
ściśle zależy od zbioru uczącego
Algorytm k-NN
wartości atrybutów (n liczba atrybutów)
traktowane są jako punkt w n wymiarowej
hiperprzestrzeni
określona jest metryka obliczania odległości
między dwoma punktami w tej przestrzeni
algorytm k-NN
:
znajdź k punktów ze zbioru uczącego, które
znajdują się najbliżej punktu odpowiadającego
danym, które mamy zaklasyfikować
określ klasę do której należy większość z tych k
punktów
wyznaczona w ten sposób klasa jest również klasą
klasyfikowanych danych.
Algorytm k-NN (przykład)
?
Algorytm k-NN (przykład)
k=3
!
Algorytm k-NN (przykład)
k=5
!
własności algorytmu k-NN
im większy zbiór referencyjny (uczący) tym
bardziej własności tego algorytmu zbliżają się do
klasyfikatora co najwyżej dwukrotnie gorszego od
reguły Bayesa (+++)
własność klasyfikacji ściśle uzależniona od:
użytej metryki
zbioru uczącego
możliwy „remis”, gdy klas jest więcej niż dwie (–)
eksperymentalne określenie k (–)
wielkość zbioru uczącego ma wpływ na złożoność
obliczeniową algorytmu (–)
jak zwykle, zamiast zakończenia...
filozoficznie:
fragment okładki i książki pt.
„Paddington daje sobie
radę”
(autor: Michael Bond)
— Wie pani — powiedział do pani
Bird, gdy przyszła do jadalni, by
sprawdzić,
czy już zjadł grzankę z marmoladą —
nigdy dotąd nie zrobiłem
wszystkiego,
bo gdybym zrobił, to nie
czekałyby mnie już żadne
niespodzianki
.
Document Outline
- formalnie: Binarne drzewa decyzyjne + algorytm k-NN
- Plan wykładu
- Drzewa decyzyjne [binarne]
- Slide 4
- Drzewa binarne: wybór progu
- Slide 6
- Wybór progu (atrybuty jakościowe)
- Slide 8
- Wybór progu (atrybut porządkowy)
- Slide 10
- Slide 11
- Slide 12
- Wybór progu (atrybut symboliczny)
- Slide 14
- Slide 15
- Slide 16
- Slide 17
- Binarna dyskretyzacja atrybutów (przykład)
- Drzewa decyzyjne [binarne] (przykład)
- Drzewa z liśćmi probabilistycznymi
- Drzewo binarne: dlaczego takie duże?
- Liście vs. liście probabilistyczne
- Slide 23
- Slide 24
- drzewa i „koszty”...
- Nie ma nawet drzew idealnych...
- Przycinanie drzewa decyzyjnego
- Kryterium stopu
- Slide 29
- Slide 30
- Przycinanie drzewa decyzyjnego (pseudokod)
- Przycinanie drzewa decyzyjnego (przykład)
- Slide 33
- Podsumowanie, własności drzew
- Slide 35
- Slide 36
- Algorytm k-NN
- Slide 38
- Algorytm k-NN (przykład)
- Slide 40
- Slide 41
- własności algorytmu k-NN
- jak zwykle, zamiast zakończenia...
Wyszukiwarka
Podobne podstrony:
NAI B3 pytaniaKontrolne
sem2, Strategia b3
NAI A2 pytaniaKontrolne
NAI Regresja Nieliniowa
B3 F klamra
więcej podobnych podstron