1 nieformalnie: Prawie o tym jak mierzyć zawartość cukru w cukrze...formalnie: 4xD, czylii dyskretne drzewa decyzyjne + dyskretyzacja atrybutów (cz. II) Dorota Cendrowska nieformalnie: Prawie o tym jak mierzyć zawartość cukru w cukrze...
2 Plan wykładu o dyskretyzacji raz jeszcze entropia i jej własnościzastosowanie entropii jako miary różnorodności dyskretne drzewa klasyfikacyjne: niezbędne definicje struktura tworzenie
3 Prymitywne metody dyskretyzacji atrybutów ilościowych (numerycznych)technika „równych przedziałów”: technika „równoliczności” (r=3):
4 Dylemat dyskretyzacjimoże więc podział, który zapewnia: równomierność przykładów reprezentujących różne klasy (mniej więcej tyle samo przykładów z każdej klasy) (???);
5 Dylemat dyskretyzacjimoże więc podział, który zapewnia: równomierność przykładów reprezentujących różne klasy (mniej więcej tyle samo przykładów z każdej klasy) (???); co jest „dobrą” dyskretyzacją atrybutu ciągłego? „mała” liczba przedziałów, która umożliwia rozróżnienie przynależności przykładów do danej klasy
6 Dylemat dyskretyzacjimoże więc podział, który zapewnia: równomierność przykładów reprezentujących różne klasy (mniej więcej tyle samo przykładów z każdej klasy) (???); co jest „dobrą” dyskretyzacją atrybutu ciągłego? „mała” liczba przedziałów, która umożliwia rozróżnienie przynależności przykładów do danej klasy lepszy podział to taki, w którym przykłady reprezentujące pewną klasę dominują.
7 Nieprymitywne ale naiwne metody dyskretyzacji atrybutów ilościowychinformacja o przynależności do klas niewykorzystana: technika „równych przedziałów” technika „równoliczności” naiwne metody: jeden przedział
8 Nieprymitywne ale naiwne metody dyskretyzacji atrybutów ilościowychinformacja o przynależności do klas niewykorzystana: technika „równych przedziałów” technika „równoliczności” naiwne metody: jeden przedział technika równoliczności z r=1
9 Wady naiwnych metod dyskretyzacji atrybutówmetoda „jeden przedział”: gubimy różnorodność w obrębie atrybutu :( metoda „jeden reprezentant”: brak reprezentatywności wewnątrz zbioru uczącego :(
10 Jak sensownie wykonać dyskretyzację?życzenie: uwzględnić informację o przynależności do jednej z klas
11 Jak sensownie wykonań dyskretyzację?życzenie: uwzględnić informację o przynależności do jednej z klas liczba możliwych podziałów: przy podziale binarnym: przy podziale na k wartości:
12 Jak sensownie wykonań dyskretyzację?życzenie: uwzględnić informację o przynależności do jednej z klas liczba możliwych podziałów: przy podziale binarnym: przy podziale na k wartości: narzędzie (?): potrzebny „miernik”, czy podział dokonywany jest w „sensownym” miejscu
13 Co jest informacją? (A): Wszystkie koty nocą wydają się czarne(B): Wszystkie psy na świecie są różowe (C): Widziałem murzyna... (tfu)... afroamerykanina (D): Optymisto-pesymista wyrzuci reszkę.
14 Co jest informacją? (A): Wszystkie koty nocą wydają się czarne(B): Wszystkie psy na świecie są różowe (C): Widziałem murzyna... (tfu)... afroamerykanina (D): Optymisto-pesymista wyrzuci reszkę. PRAWDA, P(A)=1 FAŁSZ, P(B)=0 so-so, P(C)=0,0005
15 Jak mierzyć („ważyć”) informację?(A): Spotkałem człowieka będąc na PJWSTK. (B): Rzuciłem monetą i spadła. Entropia (teoria informacji) to średnia ilość informacji:
16 Jak mierzyć („ważyć”) informację?(A): Spotkałem człowieka będąc na PJWSTK... kobietę. (B): Rzuciłem monetą i spadła...rewersem do góry. Entropia (teoria informacji) to średnia ilość informacji: kobieta, mężczyzna
17 Entropia, własności Gdzie postawić kropkę w kwestii afroamerykanina?„Im większa wartość entropii, tym mniej można przewidzieć” (np. rozkład równomierny)
18 Algorytm dyskretyzacji zstępujacejstart: Z=T (zbiór uczący), a: atrybut do dyskretyzacji Lista dyskretyzuj(Z, a){ Lista wynik=null; if (!kryteriumStopu(Z, a){ próg=wybierzPróg(Z, a); prógLewejCzęści=dyskretyzuj(Za<=próg, a); prógPrawejCzęści=dyskretyzuj(Za>próg, a); if (prógLewejCzęści!=null) wynik.add(prógLewejCzęści); wynik.add(próg); if (prógPrawejCzęści!=null) wynik.add(prógPrawejCzęści); } return wynik;
19 Algorytm dyskretyzacji zstępujacej (ilustracja)start: Z=T (zbiór uczący), a: atrybut do dyskretyzacji Lista dyskretyzuj(Z, a){ Lista wynik=null; if (!kryteriumStopu(Z, a){ próg=wybierzPróg(Z, a); prógLewejCzęści=dyskretyzuj(Za<=próg, a); prógPrawejCzęści=dyskretyzuj(Za>próg, a); if (prógLewejCzęści!=null) wynik.add(prógLewejCzęści); wynik.add(próg); if (prógPrawejCzęści!=null) wynik.add(prógPrawejCzęści); } return wynik;
20 Algorytm dyskretyzacji zstępujacej (ilustracja)start: Z=T (zbiór uczący), a: atrybut do dyskretyzacji Lista dyskretyzuj(Z, a){ Lista wynik=null; if (!kryteriumStopu(Z, a){ próg=wybierzPróg(Z, a); prógLewejCzęści=dyskretyzuj(Za<=próg, a); prógPrawejCzęści=dyskretyzuj(Za>próg, a); if (prógLewejCzęści!=null) wynik.add(prógLewejCzęści); wynik.add(próg); if (prógPrawejCzęści!=null) wynik.add(prógPrawejCzęści); } return wynik;
21 Algorytm dyskretyzacji zstępujacej (ilustracja)start: Z=T (zbiór uczący), a: atrybut do dyskretyzacji Lista dyskretyzuj(Z, a){ Lista wynik=null; if (!kryteriumStopu(Z, a){ próg=wybierzPróg(Z, a); prógLewejCzęści=dyskretyzuj(Za<=próg, a); prógPrawejCzęści=dyskretyzuj(Za>próg, a); if (prógLewejCzęści!=null) wynik.add(prógLewejCzęści); wynik.add(próg); if (prógPrawejCzęści!=null) wynik.add(prógPrawejCzęści); } return wynik;
22 Algorytm dyskretyzacji zstępujacej (ilustracja)start: Z=T (zbiór uczący), a: atrybut do dyskretyzacji Lista dyskretyzuj(Z, a){ Lista wynik=null; if (!kryteriumStopu(Z, a){ próg=wybierzPróg(Z, a); prógLewejCzęści=dyskretyzuj(Za<=próg, a); prógPrawejCzęści=dyskretyzuj(Za>próg, a); if (prógLewejCzęści!=null) wynik.add(prógLewejCzęści); wynik.add(próg); if (prógPrawejCzęści!=null) wynik.add(prógPrawejCzęści); } return wynik;
23 Algorytm dyskretyzacji zstępujacej (ilustracja)start: Z=T (zbiór uczący), a: atrybut do dyskretyzacji Lista dyskretyzuj(Z, a){ Lista wynik=null; if (!kryteriumStopu(Z, a){ próg=wybierzPróg(Z, a); prógLewejCzęści=dyskretyzuj(Za<=próg, a); prógPrawejCzęści=dyskretyzuj(Za>próg, a); if (prógLewejCzęści!=null) wynik.add(prógLewejCzęści); wynik.add(próg); if (prógPrawejCzęści!=null) wynik.add(prógPrawejCzęści); } return wynik;
24 Algorytm dyskretyzacji zstępujacej (ilustracja)start: Z=T (zbiór uczący), a: atrybut do dyskretyzacji Lista dyskretyzuj(Z, a){ Lista wynik=null; if (!kryteriumStopu(Z, a){ próg=wybierzPróg(Z, a); prógLewejCzęści=dyskretyzuj(Za<=próg, a); prógPrawejCzęści=dyskretyzuj(Za>próg, a); if (prógLewejCzęści!=null) wynik.add(prógLewejCzęści); wynik.add(próg); if (prógPrawejCzęści!=null) wynik.add(prógPrawejCzęści); } return wynik;
25 Wybór progu (algorytm dyskretyzacji)ważona entropia zbioru przykładów Z ze względu na podział zakresu wartości atrybutu a na dwa przedziały:
26 Wybór progu (algorytm dyskretyzacji)ważona entropia zbioru przykładów Z ze względu na podział zakresu wartości atrybutu a na dwa przedziały:
27 Wybór progu (algorytm dyskretyzacji)ważona entropia zbioru przykładów Z ze względu na podział zakresu wartości atrybutu a na dwa przedziały: wybór progu:
28 Wybór progu (ilustracja)przykład (fragment obliczeń):
29 Wybór progu (ilustracja)przykład (fragment obliczeń):
30 Wybór progu (ilustracja)przykład (fragment obliczeń):
31 Wybór progu (ilustracja)przykład (fragment obliczeń):
32 Wybór progu (ilustracja)przykład (fragment obliczeń):
33 Wybór progu (ilustracja)przykład (fragment obliczeń):
34 Wybór progu (ilustracja)przykład (fragment obliczeń):
35 Kryterium stopu (algorytm dyskretyzacji)[trywialne] gdy przykłady w zbiorze Z należą do tej samej klasy kiedy dzielenie przedziału przestaje poprawiać ich informacyjną zawartość, czyli powiększać nierównomierność rozkładu kategorii: podział daje poprawę tylko wtedy, gdy ga,próg(Z)>0
36 Drzewa (definicje) jak wygląda drzewo każdy wie...drzewo „informatyczne” musi być inne: drzewo to graf bez cykli, w którym istnieje tylko jedna ścieżka między dwoma różnymi węzłami
37 Drzewa (elementy szczególne)drzewo to graf bez cykli, w którym istnieje tylko jedna ścieżka między dwoma różnymi węzłami węzły drzewa krawędzie wyróżnione węzły drzewa to: korzeń drzewa liście drzewa
38 Drzewo decyzyjne (definicja)drzewo decyzyjne to drzewo reprezentujące proces podziału zbioru przykładów na jednorodne klasy węzły opisują sposób dokonania podziału (test) liście odpowiadają klasom, do których należą przykłady krawędzie reprezentują wartości cech znajdujących się w węzłach, na podstawie których dokonano podziału
39 Algorytm tworzenia drzewa decyzyjnegoalgorytm rekurencyjny parametry startowe: Z — zbiór wszystkich przykładów ze zbioru uczącego T dostępneAtrybutyTestowe — Lista wszystkich atrybutów w zbiorze uczącym T istotne elementy algorytmu: wybór atrybutu testowego, będące kryterium podziału
40 Algorytm tworzenia drzewa decyzyjnegoWęzeł twórzDrzewoDecyzyjne(Z, Lista dostępneAtrybutyTestowe){ if (kryteriumStopu(Z,dostępneAtrybutyTestowe){ return new Węzeł(klasa(Z)); //utwórz i zwróć liść } Węzeł węzeł=new Węzeł(); atrybutA=wybierzAtrybutTestowy(dostępneAtrybutyTestowe); Lista nowaLista=dostępneAtrybutyTestowe.remove(atrybutA); węzeł.ustawTest(atrybutA); if (nowaLista!=null){ węzeł.ustawLiczbeGałęzi(atrybutA.podajKrotność()); for(String w: atrybutA.podajWartosci()){ Zw=utwórzPodzbiór(Z,aatrybutA,w); // dla których atrybut ma wartość w węzeł.ustawGałąź(w,twórzDrzewoDecyzyjne(Zw,nowaLista); return węzeł;
41 Kryterium stopu [na potrzeby tego wykładu] (tworzenie drzewa decyzyjnego)wszystkie przykłady w zbiorze Z reprezentują jedną klasę; pusta lista dostępnych atrybutów; wówczas klasa(Z) to klasa, która jest najliczniej reprezentowana przez przykłady ze zbioru Z. inne metody (wykład B.3)
42 Wybór atrybutu testowego (tworzenie drzewa decyzyjnego)na podstawie „pomiaru” zróżnicowania zbioru Z ze względu na atrybut A.
43 Wybór atrybutu testowego (tworzenie drzewa decyzyjnego)na podstawie „pomiaru” zróżnicowania zbioru Z ze względu na atrybut A. funkcja zróżnicowania: wybieramy atrybut, dla którego osiągamy maksymalną wartość funkcji zróżnicowania:
44 Wybór atrybutu testowego (tworzenie drzewa decyzyjnego)na podstawie „pomiaru” zróżnicowania zbioru Z ze względu na atrybut A. funkcja zróżnicowania: wybieramy atrybut, dla którego osiągamy maksymalną wartość funkcji zróżnicowania: lub w praktyce:
45 Tworzenie drzewa decyzyjnego (przykład)lista dostępnych atrybutów testowych: {A1, A2, A3, A4, A5, A6} Zbiór Z = zbiór T, |Z|=20:
46 Tworzenie drzewa decyzyjnego (przykład)szukamy:
47 Tworzenie drzewa decyzyjnego (przykład)
48 Tworzenie drzewa decyzyjnego (przykład)
49 Tworzenie drzewa decyzyjnego (przykład)
50 Tworzenie drzewa decyzyjnego (przykład)
51 Tworzenie drzewa decyzyjnego (przykład)
52 Tworzenie drzewa decyzyjnego (przykład)
53 Tworzenie drzewa decyzyjnego (przykład)
54 Tworzenie drzewa decyzyjnego (przykład)
55 Tworzenie drzewa decyzyjnego (przykład)
56 Tworzenie drzewa decyzyjnego (przykład)wybór atrybutu testowego:
57 Tworzenie drzewa decyzyjnego (przykład)wybór atrybutu testowego:
58 Tworzenie drzewa decyzyjnego (przykład)wybór atrybutu testowego:
59 Tworzenie drzewa decyzyjnego (przykład)wywołanie rekurencyjne dla: Z=ZA6=low, |Z|=5 lista atrybutów testowych: {A1, A2, A3, A4, A5}
60 Tworzenie drzewa decyzyjnego (przykład)wywołanie rekurencyjne dla: Z=ZA6=low, |Z|=5 lista atrybutów testowych: {A1, A2, A3, A4, A5} spełnione kryterium stopu
61 Tworzenie drzewa decyzyjnego (przykład)wywołanie rekurencyjne dla: Z=ZA6=low, |Z|=5 lista atrybutów testowych: {A1, A2, A3, A4, A5} spełnione kryterium stopu utworzony liść
62 Tworzenie drzewa decyzyjnego (przykład)wywołanie rekurencyjne dla: Z=ZA6=med, |Z|=7 lista atrybutów testowych: {A1, A2, A3, A4, A5}
63 Tworzenie drzewa decyzyjnego (przykład)wywołanie rekurencyjne dla: Z=ZA6=med, |Z|=7 lista atrybutów testowych: {A1, A2, A3, A4, A5} niespełnione kryterium stopu
64 Tworzenie drzewa decyzyjnego (przykład)wywołanie rekurencyjne dla: Z=ZA6=med, |Z|=7 lista atrybutów testowych: {A1, A2, A3, A4, A5}
65 Tworzenie drzewa decyzyjnego (przykład)wywołanie rekurencyjne dla: Z=ZA6=med, A5=small, |Z|=2 lista atrybutów testowych: {A1, A2, A3, A4} spełnione kryterium stopu
66 Tworzenie drzewa decyzyjnego (przykład)wywołanie rekurencyjne dla: Z=ZA6=med, A5=small, |Z|=2 lista atrybutów testowych: {A1, A2, A3, A4} spełnione kryterium stopu utwórz liść
67 Tworzenie drzewa decyzyjnego (przykład)wywołanie rekurencyjne dla: Z=ZA6=med, A5=med, |Z|=4 lista atrybutów testowych: {A1, A2, A3, A4} spełnione kryterium stopu utwórz liść
68 Tworzenie drzewa decyzyjnego (przykład)wywołanie rekurencyjne dla: Z=ZA6=med, A5=big, |Z|=1 lista atrybutów testowych: {A1, A2, A3, A4} spełnione kryterium stopu utwórz liść
69 Tworzenie drzewa decyzyjnego (przykład)wywołanie rekurencyjne dla: Z=ZA6=med, A5=big, |Z|=1 lista atrybutów testowych: {A1, A2, A3, A4} spełnione kryterium stopu utwórz liść
70 Tworzenie drzewa decyzyjnego (przykład)wywołanie rekurencyjne dla: Z=ZA6=high, |Z|=8 lista atrybutów testowych: {A1, A2, A3, A4, A5}
71 Tworzenie drzewa decyzyjnego (przykład do dokończenia...)wywołanie rekurencyjne dla: Z=ZA6=high, |Z|=8 lista atrybutów testowych: {A1, A2, A3, A4, A5} ?
72 jak zwykle, zamiast zakończenia...filozoficznie: — 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. fragment okładki i książki pt. „Paddington daje sobie radę” (autor: Michael Bond)