c2.pdf
(
438 KB
)
Pobierz
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
wiczenia2
!
1) Wygeneruj system decyzyjny za pomoc¡ programu ds generator.exe.
2) Z otrzymanego systemu zbuduj drzewo decyzyjne przy pomocy algorytmu ID3.
DrzewaDecyzyjne-algorytmID3:
Zacznijmy od bazowych informacji.
Podstawowateoria
Algorytm ID3 został zaprojektowany przez Rossa Quinlana, który nast¦pnie prze-
kształcił go w popularn¡ metod¦ C4.5 i C5.0. W metodzie ID3 budowane jest drzewo
decyzyjne z pewnego systemu decyzyjnego treningowego u»ywaj¡c poj¦cia zysku in-
formacyjnego (Information Gain) bazuj¡cego na entropii (Entrophy). Przy ka»dym
w¦¹le, algorytm ID3 wybiera atrybut, który najlepiej dzieli zbiór obiektów na kla-
sy decyzyjne daj¡c najwi¦kszy zysk informacyjny. Mówi¡c o zysku informacyjnym,
mamy na my±li ró»nic¦ entropii w¦zła głównego z entropiami podw¦złów (poziomu
ni»szego). Na podstawie zysku informacyjnego wybierany jest atrybut słu»¡cy do
podziału danych (wierzchołek). Atrybut z najwi¦kszym znormalizowanym zyskiem
informacyjnym jest wybierany do podejmowania decyzji. Algorytm ID3 działa re-
kurencyjnie dla mniejszych podsystemów decyzyjnych.
W algorytmie ID3 mo»emy napotka¢ kilka typowych sytuacji,
•
Je»eli wszystkie przykłady nale»¡ do tej samej klasy. W tym przypadku, pro-
sto tworzymy li±¢ drzewa decyzyjnego wybieraj¡c dan¡ klas¦ decyzyjn¡.
•
Gdy »adna z cech nie dostarcza jakiegokolwiek zysku informacyjnego, tworzymy
w¦zeł decyzyjny wy»ej o jeden poziom, u»ywaj¡c spodziewanej warto±ci klasy.
•
W przypadku gdy napotkamy niewidzian¡ wcze±niej klas¦ decyzyjn¡, tworzymy
w¦zeł decyzyjny wy»ej u»ywaj¡c stosownej warto±ci.
Zakładaj¡c, »e
•
p
jest proporcj¡ przykładów pozytywnych (ilo±¢ obiektów z decyzj¡ pozytyw-
n¡/ilo±¢ rozwa»anych obiektów)
•
p
proporcja przykładów negatywnych (ilo±¢ obiektów z decyzj¡ negatywn¡/ilo±¢
rozwa»anych obiektów)
Entropi¦ pewnego podziału na klasy decyzyjne
S
definiujemy jako
Entrophy
(
S
) =
−
p
log
2
p
−
p
log
2
p
Dla wi¦kszej ilo±ci klas
c
i
,i
= 1
,...,k
, entropi¦ mo»emy zdefiniowa¢ nast¦puj¡co
k
X
Entrophy
(
S
) =
−
p
i
log
2
p
i
i
=1
p
i
jest proporcj¡ S nale»¡c¡ do klasy
c
i
(ilo±¢ obiektów klasy
c
i
do wszystkich roz-
wa»anych)
Zysk informacyjny (information gain) definiujemy jako
Gain
(
S,A
) =
Entrophy
(
S
)
−
X
v
2
Values
(
A
)
S
v
S
Entrophy
(
S
v
)
P
v
2
Values
(
A
)
S
v
S
Entrophy
(
S
v
) jest spodziewan¡ warto±ci¡ entropii po podziale
S
przy pomocy atrybutu A.
V alues
(
A
) to zbiór mo»liwych warto±ci atrybutu
A
.
S
v
jest podzbiorem
S
definiowanym jako
S
v
=
{
s
2
S
|
A
(
s
) =
v
}
Własno±ci entropii,
•
Entropia jest równa 1 gdy mamy tyle samo przykładów negatywnych i pozytyw-
nych
•
Entropia jest równa 0 gdy wszystkie obiekty nale»¡ do tej samej klasy decyzyjnej
(s¡ pozytywne lub negatywne)
•
Je»eli podsystem zawiera nierówn¡ liczb¦ przykładów pozytywnych i negatywnych
entropia jest z przedziału (0,1) i jej wykres w zale»no±ci od proporcji przykładów
pozytywnych przedstawia si¦ nast¦puj¡co,
Rys1: Wykres Entropii
Przykładbudowaniadrzewadecyzyjnegozaproponowanyprzez
RossaQuinlana
Dzie«
Pogoda
Temperatura
Wilgotno±¢
Wiatr
Gram w Tenisa
D1
Słoneczna
Gor¡co
Wysoka
Słaby
Nie
D2
Słoneczna
Gor¡co
Wysoka
Mocny
Nie
D3
Pochmurna
Gor¡co
Wysoka
Słaby
Tak
D4
Deszczowa
Łagodnie
Wysoka
Słaby
Tak
D5
Deszczowa
Chłodno
Normalna
Słaby
Tak
D6
Deszczowa
Chłodno
Normalna
Mocny
Nie
D7
Pochmurna
Chłodno
Normalna
Mocny
Tak
D8
Słoneczna
Łagodnie
Wysoka
Słaby
Nie
D9
Słoneczna
Chłodno
Normalna
Słaby
Tak
D10
Deszczowa
Łagodnie
Normalna
Słaby
Tak
D11
Słoneczna
Łagodnie
Normalna
Mocny
Tak
D12
Pochmurna
Łagodnie
Wysoka
Mocny
Tak
D13
Pochmurna
Gor¡co
Normalna
Słaby
Tak
D14
Deszczowa
Łagodnie
Wysoka
Mocny
Nie
Zanim przejdziemy do szacowania entropii, warto przypomnie¢ własno±ci logaryt-
mów, przydatne w obliczeniach.
•
log
a
b
=
c
,
a
c
=
b
•
log
a
1 = 0
poniewa
»
a
0
= 1
•
log
a
a
= 1
poniewa
»
a
1
=
a
•
a
log
a
b
=
b
•
log
a
b
1
b
2
=
log
a
b
1
+
log
a
b
2
•
log
a
b
1
b
2
=
log
a
b
1
−
log
a
b
2
•
log
a
b
m
=
m
log
a
b
•
log
a
b
=
log
c
b
log
c
a
•
log
a
b
=
1
log
b
a
W naszym systemie decyzyjnym
S
mamy 14 przykładów, w tym 9 pozytywnych
z decyzj¡ Tak oraz 5 negatywnych z decyzj¡ Nie. Entropia
S
relatywna do klasyfi-
kacji Boolowskiej jest postaci:
S
: [9+
,
5
−
]
Entrophy
(
S
) =
−
p
log
2
p
−
p
log
2
p
9
14
5
14
5
14
Entrophy
(
S
) =
Entrophy
[9+
,
5
−
] =
−
9
14
log
2
9
14
−
5
14
log
2
5
14
=
−
(
log
2
(
9
14
))
=
−
log
2
(0
.
5211295762)
0
.
940
Dla Wilgotno±ci, entropi¦ warto±ci Wysoka oraz Normalna obliczamy nast¦puj¡-
co,
Entrophy
[3+
,
4
−
] =
−
3
7
log
2
3
7
−
4
7
log
2
4
7
=
−
(
log
2
(
3
7
3
7
4
7
4
7
)) =
−
log
2
(0
.
50514)
0
.
985
1
7
)) =
−
log
2
(0
.
6635730598)
0
.
992. Zobrazowanie podziału mo»emy zobaczy¢ na Rysunku 2.
6
7
1
7
Entrophy
[6+
,
1
−
] =
−
6
7
log
2
6
7
−
1
7
log
2
1
7
=
−
(
log
2
(
6
7
Podział determinuje zysk informacyjny postaci,
Gain
(
S,Wilgotno
±¢) = 0
.
940
−
(
7
14
0
.
985)
−
(
7
14
0
.
592) = 0
.
940
−
0
.
4935
−
0
.
296 =
0
.
151
Rys2: Wyliczanie entropii podziału na podstawie Wilgotno±ci
Wykonujemy analogiczne obliczenia dla podziałów na podstawie atrybutów: Wiatr,
Pogoda oraz Temperatura. Wyniki mo»emy zobaczy¢ na Rysunkach 3
,
4
,
5.
Gain
(
S,Wiatr
) = 0
.
940
−
(
8
14
0
.
811)
−
(
6
14
1
.
0) = 0
.
048
Rys3: Wyliczanie entropii podziału na podstawie Wiatru
Gain
(
S,Pogoda
) = 0
.
940
−
(
5
14
0
.
971)
−
(
5
14
0
.
971) = 0
.
246
Rys4: Wyliczanie entropii podziału na podstawie Pogody
Gain
(
S,Temperatura
) = 0
.
940
−
(
4
14
1
.
0)
−
(
4
14
0
.
811)
−
(
6
14
0
.
918) = 0
.
029
Rys5: Wyliczanie entropii podziału na podstawie Temperatury
Plik z chomika:
monibach
Inne pliki z tego folderu:
ds_generator.exe
(657 KB)
c2.pdf
(438 KB)
Inne foldery tego chomika:
Ćw 1
Ćw 10
Ćw 3
Ćw 4
Ćw 5
Zgłoś jeśli
naruszono regulamin