Új típusú döntési fa építés és annak alkalmazása többtényezős döntés területén Dombi József Szegedi Tudományegyetem
Bevezetés - ID3 (Iterative Dichotomiser 3)
Az ID algoritmusok egy elemhalmaz felhasználásával elemek egy osztályozására alkalmas döntési fát (decision tree) hoznak létre. Az elemeknek előre meghatározott, közös attribútumaik vannak, minden elem attribútumainak értéke ismert.
Feladat
magasság
hajszín
szemszín
osztály
1.
alacsony
szőke
kék
+
2.
magas
szőke
barna
-
3.
magas
vörös
kék
+
4.
alacsony
sötét
kék
-
5.
magas
sötét
kék
-
6.
magas
szőke
kék
+
7.
magas
sötét
barna
-
8.
alacsony
szőke
barna
-
Megoldás
Az algoritmus
Az algoritmus által létrehozott döntési fa bármely nem levél csomópontja egy attribútum alapján osztja szét az elemeket, az attribútum minden lehetséges értékéhez egy ágat rendelve. A fa leveleihez egy-egy osztályértéket rendelünk, amely az elem osztálya. Az algoritmus egy elemhalmazra eldönti a legalkalmasabb attribútumot, mely szerint az adott halmazt szétvágjuk, így rekurzívan felépíti a döntési fát.
Az algoritmus felépítése
1. Attribútum-kiválasztó szabály: a fa egy pontján meghatározzuk, hogy mely attribútummal érdemes a mintahalmazt felbontani. 2. Továbbontó szabály: rekurzívan tovább bontjuk a mintahalmazt, vagyis további fapontokat határozunk meg. 3. Befejező szabály: eldöntjük, hogy meddig kell bontani a mintahalmazt, vagyis mikor nevezünk el egy pontot levélnek. 4. Osztályozó szabály: minden levélhez egy osztályértéket rendelünk.
Variánsok
Az ID3 eljárásnak számos változata van, például olyanok, melyek kezelik a mintahalmazban található zajt, vagy a hiányos attribútumértékeket is, például I
ID3-IV,
I
GID3-IV,
I
CID3,
I
kombinált folytonos ID3 → C4.5....
Alkalmazás
Adottak páciensek, illetve vizsgálati eredményeik, szeretnénk eldönteni, hogy melyik páciens milyen betegségben szenved. Ekkor a fa csúcsait az egyes vizsgálatok fogják képezni, és az adott csúcsnak annyi gyereke lesz, ahány féle eredménye lehetséges a vizsgálatnak (pl. a vércukorszint lehet alacsony, normális és magas, a vércukorszint csomópontnak 3 gyereke lesz), A levelekben kétféle érték lehet: az adott betegségben szenved vagy nem.
Konstrukció
A faépítés egy hierarchikus eljárás, hiszen az attribútumokon tulajdonképpen egy sorrendet állítunk fel. A minimális döntési fa készítése NP nehéz feladat, így heurisztikát kell alkalmazni. A döntési fák tanulása, entrópia: a döntési fa fogalomtanulás diszkrét értékkészletű jellemzőkre. Ockham-borotvája: „A konzisztens hipotézisek közül a legegyszerűbb a legjobb.” Heurisztika: a heurisztika alapja az entrópia.
Entrópia értelmezései
Fizika: Boltzmann - A hőmozgást végző részecskék elmozdulásának valószínűsége alapján konstruált mennyiség az entrópia. Definiálható az idő iránya (hőhalál-elmélet). Informatika: Shannon nevéhez fűződik. Az információ mértékét jelenti, alakja ES = −k
X
pi log2 pi
Az ID3 algoritmus tulajdonságai
1. Bármilyen ellentmondásmentes példahalmazhoz képes konzisztens hipotézist találni. 2. Az egyes csúcsokban az attribútumokat mohó módon választja (nem képes visszalépésre, nem garantált, hogy globálisan optimális fát talál). 3. Nem érzékeny a zajokra 4. Az ellentmondó példákat is képes kezelni! 5. A tanulás eredményeképp a fát IF-THEN szabályokká lehet alakítani
Kiterjesztések hiányzó attribútumok esetén
I
I
Kiterjesztés osztályozásra I
A fa levelein +,- helyett osztálycímkék lesznek.
I
Az entrópia több érték esetére is definiált.
Kiterjesztés folytonos változókra I
Egy folytonos változó értékkészletét < , > feltételekkel intervallumokra bonthatjuk, így a folytonos változók elvileg kezelhetők.
I
A tanulóalgoritmus többféle módosítást igényel (pl. az intervallumok automatikus kialakítására a példák alapján)
Megjegyzés: Folytonos térben a módszer tengelyekkel párhuzamos téglalapok uniójával osztályoz.
Algoritmus
A Ck -k attribútumai: Sk1 , Sk2 . . . Sknk tehát Ck = {Sk1 . . . Sknk } C1
C2
...
Cm
R
a1 a2 .. . al .. . aN
rl
Jelölések
|S| összes példa száma (N) |S + | pozitív példák száma |S − | negatív példák száma |Ski+ | pozitív példák száma adott Ski értékre |Ski− | negatív példák száma adott Ski értékre
Jelölések
+ |Sk1 | + |S | + |Sk2 | = + |S |
− |Sk1 | − |S | − |Sk2 | = − |S |
+ − |Sk1 | = |Sk1 | + |Sk1 |
+ xk1 =
− xk1 =
+ − |Sk2 | = |Sk2 | + |Sk2 |
+ xk2
− xk2
.. . − + |Sknk | = |Skn | + |Skn | k k
|S| = |S + |+|S − |
.. .
+ xkn = k
w+ =
+ |Skn | k |S + |
|S + | |S|
− = xkn k
w− =
− |Skn | k
|S − |
|S − | |S|
Összefüggések
+
|S | =
nk X
|Ski+ |
i=1
i=1
xki+ = 1
|S | =
nk X
|Ski− |
i=1
w+ + w− = 1 nk X
−
nk X i=1
xki− = 1
w [0, 1] xki+ [0, 1], xki− [0, 1]
Entrópia és bizonytalansági mérték
E(x) = −k
n X
xi ln(xi )
i=1
E(x) = −
1 (xln(x) + (1 − x)ln(1 − x)) ln2
F(x) = 4x(1 − x)
Entrópia és bizonytalansági mérték 1,0
0,8
0,6
0,4
0,2
0 0
0,2
0,4
0,6
x
0,8
1,0
Entrópia és bizonytalansági mérték
1 I (S) = − ln2
|S + | |S + | |S − | |S − | ln + ln |S| |S| |S| |S|
|S + | J(S) = 4 |S|
|S + | 1− |S|
=4
|S + ||S − | |S|2
,
1. Számítás
J(Sk1 ) = 4
+ − |Sk1 ||Sk1 | 2 |Sk1 |
J(Sk2 ) = 4
+ − |Sk2 ||Sk2 | 2 |Sk2 |
.. . J(Sknk ) = 4
+ − ||Skn | |Skn k k
|Sknk |2
Átlagos bizonytalanság
E (Ck ) =
E (Ck ) = 4
|Sknk | |Sk2 | |Sk1 | J(Sk1 ) + J(Sk2 ) + . . . J(Sknk ) |S| |S| |S|
nk X |Ski | |S + ||S − | ki
i=1
|S|
|Ski
ki |2
n
k X |Ski+ ||Ski− | 4 = + |S | + |S − | |Ski+ | + |Ski− |
i=1
Új összefüggések
E (Ck ) =
nk X
cD (w + , xki− ; w − , xki+ ),
i=1
ahol cD a konjunktív Dombi operátor. nk xki+ xki− 4|S + ||S − | X E (Ck ) = + |S | + |S − | |S + |xki+ + |S − |xki− i=1 +
= 4w w
−
nk X
1
i=1
1−x − w + x −ki ki
1+
+ w−
+ 1−xki + xki
1. Példa - adatbázis
C1
C2
C3
R
1
B
3
b
+
2
A
3
a
-
3
A
2
b
+
4
B
1
b
-
5
A
1
b
-
6
A
3
b
+
7
A
1
a
-
8
B
3
a
-
1. Példa - megoldás
Gyors számítási eljárás
C1 z }| { A B
C2 z }| { 1 2 3
C3 z }| { a b
C4 z }| { r+ r−
1
0 1
0 0 1
0 1
1 0
2
1 0
0 0 1
1 0
0 1
3
1 0
0 1 0
0 1
1 0
4
0 1
1 0 0
0 1
0 1
5
1 0
1 0 0
0 1
0 1
6
1 0
0 0 1
0 1
1 0
7
1 0
1 0 0
1 0
0 1
8 P
0 1
0 0 1
1 0
0 1 3 5
r + szorzás
C1 z }| { + r (A) r+ (B)
C2 z }| { + + r (1) r (2) r+ (3)
C3 z }| { + r (a) r+ (b)
1
0
1
0
0
1
0
1
2
0
0
0
0
0
0
0
3
1
0
0
1
0
0
1
4
0
0
0
0
0
0
0
5
0
0
0
0
0
0
0
6
1
0
0
0
0
0
1
7
0
0
0
0
1
0
0
8 P
0
0
0
0
0
0
0
2 2 3
1 1 3
0 0 3
1 1 3
2 2 3
0 0 3
3 3 3
x+
r − szorzás
C1 z }| { − r (A) r− (B)
C2 z }| { − − r (1) r (2) r− (3)
C3 z }| { − r (a) r− (b)
1
0
0
0
0
0
0
0
2
1
0
0
0
1
1
0
3
0
0
0
0
0
0
0
4
0
1
1
0
0
0
1
5
1
0
1
0
0
0
1
6
0
0
0
0
0
0
0
7
1
0
1
0
0
1
0
8 P
0
1
0
0
1
1
0
3 3 5
2 2 5
3 3 5
0 0 5
2 2 5
3 3 5
2 2 5
x−
Ck = {α1k , α2k . . . αkkn }
0≤
αlki
Clk = {αlk1 , αlk2 . . . αlkk } n
nk X
≤1
αlki = 1
i=1
Clk = (0.3, 0.7, 0)
|Ski+ | =
M X l=1
rl αlki
|Ski− | =
M X l=1
rl (1 − αlki )
2. Példa - általánosítások
Adatbázis: C1 z }| { A B
{ 3
C3 z }| { a b
R
z 1
C2 }| 2
1
0.4 0.6
0.1 0.1 0.8
0.0 1.0
1
2
0.6 0.4
0.3 0.3 0.4
1.0 0.0
0
3
0.7 0.3
0.0 1.0 0.0
0.0 1.0
1
4
0.3 0.7
0.9 0.1 0.0
0.0 1.0
0
5
0.8 0.2
0.8 0.2 0.0
0.0 1.0
0
6
0.8 0.2
0.2 0.2 0.6
0.0 1.0
1
7
0.7 0.3
0.4 0.3 0.3
1.0 0.0
0
8
0.1 0.9
0.0 0.0 1.0
1.0 0.0
0
Megoldás
Folytonos eset
Folytonos eset
Definíció Legyen ga (x) > 0 egy egyenlőtlenség, ahol a a függvény paramétere. A felfújó erre az értékre δ (λ) (ga (x)) = λ a bizonytalansági paraméter.
1 1+
e −λga (x)
,
Felfújt egyenes
a0 + a1 x + a2 y > 0
1,0
-5,0 0,75
-2,5 0,0
0,5
y
2,5 5,0 -5,0
0,25 -2,5 0,0 0,0
2,5 5,0
x
Felfújt kör
(x − a1 )2 + (y − a2 )2
1
2
− a0 > 0
1
0
3
3
x
-1
C1
C2
R
1
0.4 0.6
0.1 0.1 0.8
1
3
0.7 0.3
0.0 1.0 0.0
1
4
0.3 0.7
0.9 0.1 0.0
0
5
0.8 0.2
0.8 0.2 0.0
0
6
0.8 0.2
0.2 0.2 0.6
1
C1
C2
R
a1
x1
y1
r1
a2 .. .
x2
y2
r2
an
xn
yn
rn
Köszönöm a figyelmet!!!!
