Osztályozó algoritmusok vizsgálata Önálló laboratórium beszámoló
Készítette: Kollár Nándor Konzulens: Kupcsik András
2009-12-14
Osztályozás A gépi tanulás, adatfeldolgozás területének egyik ága az osztályozás, amely egyfajta felügyelt tanulási módszer. Az osztályozás célja, hogy egy adott adathalmazból, amelyben az adatokat n darab attribútum és egy osztály (címke, cél attribútum) jellemez, olyan modell felépítése, amely képes új adatok (amelyeknek ismert minden attribútuma de ismeretlen az osztálya) osztályának megbízható, pontos meghatározására. Ennek szemléltetésére lássuk az 1. táblázatot. Adottak tehát ( x1 , c1 ) … ( x N , c N ) adatpontok, mindegyiknek ismert minden attribútuma és osztálya is. Kérdés, hogy egy új, ismeretlen osztályba tartozó, ( x N +1 , ?) pont osztályát hogyan tudjuk meghatározni? Ezzel a kérdéssel foglalkozik az osztályozás, és jelen dolgozatom is.
X1
…
Xn
C
( x1 , c 1 )
x11
…
x1n
c1
(x 2 , c 2 ) … N N (x , c )
x12 … x1N
… … …
xn2 … xnN
c2 … cN
( x N +1 , ?)
x1N +1
…
x1N +1
?
2. Táblázat
Az osztályozó algoritmusoknak számtalan gyakorlati alkalmazási területe van: osztályozó algoritmusokat használnak például idıjárás elırejelzésre a múltbeli idıjárás adatokat felhasználva, kézírás illetve beszéd felismerésére, pénzügyi adatok elemzésére, tızsdei elırejelzésre és még sok már egyéb területet lehetne említeni. Számos, különbözı bonyolultságú algoritmus fejlesztettek ki, néhány ezek közül: Bayes hálók, neurális hálok, support vektor gépek, K-legközelebbi szomszéd algoritmus, döntési fák. Az önálló laboratórium keretein belül utóbbi két algoritmussal ismerkedtem meg illetve implementáltam MATLAB környezetben. Az algoritmusokat a konzulensemtıl kapott teszt adatbázison ki is próbáltam. Az implementált algoritmusok teszteléséhez elkezdtem MATLAB környezetben egy keretrendszer írását. Ennek célja, hogy egyszerően lehessen új algoritmust integrálni, és tesztelni. A vezérlést megkönnyítendı létrehoztam egy grafikus felületet, errıl látható egy screenshot az 1. ábrán.
1. ábra
2
Osztályozó algoritmusok teljesítményének mérése Amikor elkészítünk egy adatbázis alapján osztályozó algoritmusokat, szükségünk van valamilyen módszerre azok teljesítményének összehasonlításához. Ehhez a félév során három módszert ismertem meg és implementáltam a keretrendszerbe. Egyszerő módszer A legegyszerőbb módszer a rendelkezésre álló adatokból egy modell felépítése, majd ezen adatokat használja fel a teljesítmény mérése is. Ezt illusztrálja a 2. ábra.
2. ábra
Az algoritmust a rendelkezésre álló adathalmazzal tanítjuk és teszteljük is. Ekkor a teszt hiba (és egyben a tanító hiba is) az elhibázott sorok (azoknak a sorok, ahol a tényleges osztály és az algoritmus által jósolt osztály különbözik) számának és az összes adatnak az arányaként 1 N számítható: PM = ∑ c i ! = cMi . N i=1 Tanító és teszt halmaz módszere Ezzel a módszerrel az adathalmazt két részre bontjuk: egy tanító és egy teszt halmazra. A tanító halmazt használjuk fel a modell építésére, a teszt halmazt pedig a kialakított modell teljesítményének mérésére. A módszer a 3. ábrán látható.
3. ábra
Ekkor két hibát definiálhatunk. A modell építése során fellépı hiba a tanító halmazon 1 N1 i elhibázott sorok aránya a tanítóhalmaz méretéhez viszonyítva: PMtrain = c ! = cMi . A ∑ N1 i =1 tesztelés során fellépı hiba a tesz halmazon elhibázott sorok aránya a tanítóhalmaz méretéhez 1 N − N1 N1 +i viszonyítva: PMtest = c ! = cMN1 +i . A módszer elınye, hogy az algoritmus ∑ N − N1 i =1
3
teljesítményét meg tudjuk vizsgálni új adatokon is. Hátránya viszont, hogy pazarló, hiszen csak az adatok egy részét használjuk tanításra. Kereszt validáció A kereszt validációt használva az adathalmazt k részre osztjuk. Ezután k lépésben alkalmazzuk a teszt és tanító halmazok módszerét: • Minden lépésben egy résszel, mint teszt halmazzal • A többi k-1 résszel, mint tanító halmazzal Ezt illusztrálja a 4. ábra.
4. ábra
1 k ∑ pi ahol pi az i. körben a teszt k i =1 halmazon a hiba. Az módszer elınye, hogy kevésbé számít, hogyan választjuk szét az adatokat. Hátránya, hogy futásideje hosszabb, mint az elıbbi módszeré, ugyanis k lépésben végezzük a tanítást és tesztelést.
Kereszt validációval a teljesítmény mértéke: PM =
A keretrendszerbe az ismertetett három teljesítményértékelı módszerbıl lehet választani egy lenyíló listából.
K-legközelebbi szomszéd (k-nearest negighbour) algoritmus Az egyik osztályozó algoritmus, amivel a félév során megismerkedetem és implementáltam, a k-legközelebbi szomszéd algoritmus volt. Ez egy egyszerő algoritmus, amely nem épít modellt, egy új, ismeretlen osztályú adatpontot a hozzá legközelebbi k adatpont osztálya alapján egyszerő többségi szavazással határozza meg. Amennyiben k páros, és döntetlen áll fenn (két osztályból ugyanannyi példány van), véletlen választással döntünk. Az paraméterei a k szám, illetve két pont távolságát meghatározó metódus. Néhány gyakori távolságfüggvény: Euklideszi távolság, Mahalanobis távolság, Hamming távolság. Az algoritmus lépései: Knn(k, ujPont, adatbázis) • Számoljuk ki az újPont és a többi pont (adatbázis) távolságát • Rendezzük a távolságokat növekvı sorrendbe
4
•
Az új pont osztály a hozzá legközelebbi k pont távolsága alapján többségi szavazással dıl el Az algoritmus MATLAB implementációja: function [y_train_pred, y_test_pred] = KNN(k, data) o = size(data.x, 1); y_train_pred = zeros(o, 1); y_test_pred = zeros(o, 1); % Elso oszlop : aktualis pont tavosaga a tobbitol % Masodik oszlop : a pontok osztálya distance = zeros(o-1, 2); % Az osszes pontra megvizsgalni... for i = 1:o point = data.x(i,:); y_train_pred(i, 1) = data.t(i); m=repmat(point, o-1, 1); distance(:,1) = euclidean(data.x([1:i-1,i+1:o],:), m); %distance(:,1) = mahalanobis(data.x([1:i-1,i+1:o],:), m); distance(:,2) = data.t([1:i-1,i+1:o],:); sorted=sortrows(distance, 1); y_test_pred(i, 1) = sign(sum(sorted(1:k,2))); if (y_test_pred(i, 1)==0) % If k is even, we randomly chose 1 y_test_pred(i, 1)=1; end end end % Euklideszi távolság function [dist] = euclidean(x, y) dist = sqrt(sum((x-y).^2, 2)); end
A mőködését egy orvosi adatokat tartalmazó mintaadatbázison teszteltem is. Az 5. ábra mutatja a hiba alakulását a k paraméter függvényében (1-tıl 200-ig, az adatbázis 262 rekordot tartalmazott), látható, hogy a legalacsonyabb hibát ezen az adatbázison k=20 környékén kapjuk, ekkor a hiba 24,33%. A tesztelés során Euklideszi távolságot használtam.
5
0.45
0.4
0.35
0.3
0.25
0.2
0
20
40
60
80
100
120
140
160
180
200
5. ábra
Döntési fák A másik algoritmus család, amivel a félév során foglalkoztam, a döntési fák voltak. Ezek az algoritmusok már modellen alapuló osztályozási módszerek, a modell egy fa, amelynek belsı csomópontjai döntési pontok, levelei pedig az osztályok. Döntési fák alkalmazásával bonyolult összefüggéseket egyszerő, elemi döntések sorozatával tudunk levezetni. Egy fa felépítésére többféle algoritmus létezik: ID3 (Ross Quinlan), C4.5 (Ross Quinlan) CART. Ezek közül az ID3 algoritmust implementáltam, ezért errıl írnék bıvebben. A 6. ábrán egy döntési fa látható annak eldöntésére, hogy menjünk-e teniszezni, vagy sem (forrás: [1]). Új adatpont esetén a gyökértıl indulva a döntési pontokban a megfelelı irányt választva eljutunk egy levélbe, amely meghatározza az új pont osztályát. A fent említett algoritmusok azzal foglalkoznak, hogy milyen módon lehet egy ilyen fát a rendelkezésre álló adatokból felépíteni úgy, hogy a fa mérete ne legyen túl nagy, és jól általánosítsa az adatokból kinyerhetı információt.
6. ábra
Az ID3 algoritmus
6
Az ID3 algoritmus feltételezi, hogy az attribútumok és a cél attribútum értékkészlete is diszkrét halmaz. Az algoritmus alapötlete, hogy minden lépésben egy olyan attribútumot választ a még nem vizsgáltak közül, amelyik „legjobban szétválasztja” az adatokat az osztályra nézve. Az algoritmus pszeudokódja: ID3(példák, cél_attribútum, attribútumok) • Készíts egy gyökér csomópontot • If (∀e ∈ példák pozitív ) , then RETURN gyökér(címke = +) • If (∀e ∈ példák negatív) , then RETURN gyökér(címke = -) • If (attribútumok üres) then RETURN gyökér(címke = leggyakoribb cél_attribútum érték a példákon) • Else o A := Az attribútumok közül az, amely legjobban szétválasztja a példákat. o Legyen a gyökér döntési attribútuma A o For (A attribútum minden lehetséges vi érékére) Adj egy új ágat a gyökér alá, amelyre A= vi Legyen példákvi a példák azon részhalmaza, melyekre az A attribútum értéke egyenlı vi
If ( példákvi üres) • •
• •
Then az új ág alá készíts egy új levél csomópontot, amelynek címkéje = leggyakoribb cél_attribútum érték a példákon Else készíts egy új részfát ezen ág alá: ID3( példákvi , cél_attribútum, attribútumok-{A})
End RETURN gyökér
Az algoritmus kulcs lépése az adatokat legjobban szétválasztó attribútum kiválasztása. Ezzel elérhetı, hogy a fa szintjeinek száma ne legyen túl nagy. A megfelelı attribútum kiválasztásához az ID3 az információ nyereséget (information gain) használja. Ennek megéréséhez elıször az entrópia fogalmát kell bevezetni. Egy S adathalmaz entrópiája: C
Entropy ( S ) = −∑ pi log 2 pi ahol C a cél attribútum értékkészletének mérete, pi pedig azon i =1
rekordok aránya az adathalmaz méretéhez képest, ahol a cél attribútum az i. értéket veszi fel. Ezek alapján egy A attribútum információ nyeresége: S Gain( S , A) = Entropy ( S ) − ∑ v Entropy ( S v ) ahol v az A attribútum egy értéke, S v az S v∈A S adathalmaz azon részhalmaza, ahol az A attribútum v értéket veszi fel. Az algoritmus mőködésére a ábrán látható döntési fa építésének egy lépével szemléletem (a példa forrása: [1]). Adottak a 3. táblázat adatai.
7
3. Táblázat
Elsı lépésben az algoritmus kiszámítja minden egyes attribútum (oszlop) információ nyereségét:
Látható, hogy az 1. oszlopnak a legnagyobb az információ nyereség értéke, így elsı lépésben ezen oszlop értékei szerint készíti az algoritmus az elágazásokat (7. ábra).
7. ábra
Így tehát az adatokat három részre bontottuk: egyik ágon napos, másik ágon felhıs, harmadik ágon esıs idı esteire. A napos és esıs idı esetén az adathalmaz nem homogén az osztályra (teniszezzünk-e) nézve, így ezeken az ágakon az algoritmus rekurzívan, a leszőkített
8
adathalmazzal tovább építi a fát, míg felhıs idı esetén már homogén az adathalmaz, így itt a fában egy levél csomóponthoz értünk, ahol a „teniszezzünk-e” kérdésre a válasz igenlı lesz. Az algoritmust implementáltam, és a minta adatbázison teszteltem is. A tesztelés során az egyszerő módszert használva, ugyanazon adatokon tanítva és tesztelve az algoritmust a hiba 2% körülire adódott. A teszt és tanító halmazok módszerével, illetve kereszt validációval a tanító halmazon továbbra is 2-4% körülire adódott a hiba, míg a teszt halmazon 35-45% körüli lett. A hiba növekedésének egy magyarázata lehet, hogy az adathalmaz szétbontása során egyes attribútumok lehetséges értékei kimaradnak a tanító halmazból. Ennek illusztrálására lássuk a 4. táblázatot. … … … … … …
X 9 9 6 2 …
… … … … … …
C 1 -1 1 -1 …
4. Táblázat
Az elsı 3 sorral, mint tanító halmazzal, a többivel, mint tesztadattal alkalmazzuk a teszt és tanító halmazok módszerét. Ekkor tegyük fel, az X attribútum információ nyeresége a legnagyobb. Ennek az attribútumnak az értékkészlete álljon az {2,6,9} elemekbıl álló halmazból. Amikor ezen attribútum szerint vágjuk szét az adathalmazt, létrehozunk új csomópontokat az X attribútum értékeinek megfelelıen. A tanító halmaz alapján viszont nem ismert, hogy az X=2 attribútum értékhez milyen osztály tartozik, így az algoritmus ehhez a csomóponthoz az osztályok közül a tanító halmazon leggyakoribb osztályt (azaz 1-et) rendeli. Ezt ábrázolja a ábra. Látható, hogy a X=9 ágon nem homogén az adathalmaz, így ezen az ágon tovább építi az algoritmus a fát, az X=6 ág a tanító halmazt tekintve, így ezen ágon egy levél csomóponthoz jutunk, ahol a cél attribútum értéke 1, míg az X=2 ágon szintén egy levél csomóponthoz jutunk, az osztály a tanító halmazon a leggyakoribb osztály (itt az algoritmus nem tud a tanító halmaz alapján ennél jobb becslést adni). Ez az eset láthatóan hibát eredményez a teszt halmazon, hiszen ekkor az X=2 attribútum értékő sorhoz C=-1 érték tartozik, ami nem egyezik az algoritmus által elıre jelzett C=1 értékkel. Ez a probléma kiküszöbölhetı a C4.5 algoritmus alkalmazásával.
X X=9
X=2 X=6
…
1
1
8. ábra
Boosting A félév során megismerkedtem még a boostinggal (Robert E. Schapire) is, bár az algoritmust idı hiányában végül nem implementáltam. A boosting tulajdonképpen egy meta-algoritmus, tehát felhasznál más osztályozó algoritmusokat. Alapötlete, hogy „gyenge” osztályozókat felhasználva egy olyan „erıs” osztályozót lehet készíteni, amely képes megbízhatóan, nagy pontossággal meghatározni ismeretlen példányok osztályát. A „gyenge” osztályozó
9
tulajdonképpen bármilyen osztályozó algoritmus lehet, amely a véletlen választásnál (bináris cél attribútum esetén 50%-nál) jobb hatékonyságot ér el. Ezeket a „gyenge” osztályozókat megfelelıen kombinálva létrehozható egy olyan „erıs” osztályozó, amely: • Pontos • A tanítás során a hiba nagyon gyorsan csökken • Nem szenved az algoritmus az „overfitting” jelenségétıl Az algoritmus ismertetett tulajdonságai miatt kézenfekvı megoldás lenne a már implementált ID3 algoritmus hatékonyságát boostinggal növelni elkerülve így az ID3-nál is fellépı „overfitting” jelenségét, illetve gyorsítva a tanulást. Az „overfitting” jelenségét a ábrán szemléltetem. A tanítás során az „idıvel” (például neurális hálózatok tanítási köreinek száma) növekedésével a tanítási hiba egyre csökken, míg a teszt hiba egy darabig szintén csökken, majd növekedni kezd. Ennek oka az, hogy a tanítási körök növekedésével az algoritmus elveszti általánosító képességét, és ahelyett, hogy az adatokba rejlı általános koncepciót kinyerné, egyszerően csak memorizálja az adatokat, és új adat érkezése esetén nem képes megfelelıen besorolni. Kevés tanító lépés esetén pedig nyilvánvalóan még nem tudja meghatározni az adatokban rejlı általános szabályokat. Így tehát a lépésszámnak van egy optimális értéke, ahol a tanító hiba és a teszt hiba is viszonylag alacsony. Ez látható a 9. ábrán.
9. ábra
Ez a jelenség boosting használatával elkerülhetı, amint az a 10. ábrán is látható. Az alsó görbe a tanító hibát, a felsı pedig a tesz hibát ábrázolja. Látható, hogy a tanító hiba nagyon gyorsan csökken, és jelen esetbe el is éri a nullát, míg a teszt hiba szintén csökken, és ugyan nem éri el a nullát, de nem is kezd emelkedni, mint a boosting alkalmazása nélkül.
10. ábra
Tervek további félévekre
10
A következı félévben tervezem az elkezdett keretrendszer további fejlesztését. Tervezem további osztályozó algoritmusok (C4.5, SVM) implementálását és integrálását. Az ID3 algoritmust felhasználva szeretném elkészíteni a boosting algoritmusok egy implementációját, az AdaBoost algoritmust. További tervem még a tanszéken folyó projektbe bekapcsolódni, amelynek célja a guminyomás csökkenést detektálása egy hatékony és olcsó megoldás kifejlesztése. Ehhez egy lehetséges irány az osztályozó algoritmusok használata, amely az autók olcsón mérhetı paraméterei alapján egy gyors (például AdaBoostot) használó osztályozó algoritmussal eldönti, hogy csökkent-e a guminyomás, vagy sem. Egy ilyen megoldással lehetségessé válik a hirtelen guminyomás detektálása és jelzése nem csak csúcs kategóriás, hanem a kis és közép kategóriás személyautók esetén is.
11
Irodalomjegyzék: [1] Tom M. Mitchell: Machine Learning [2] Robert E. Schapire: The Boosting Approach to Machine Learning [3] L. G. Valiant: A Theory of the Learnable [4] Nils J. Nilsson: Introduction to machine learning [5] Dr. Bodon Ferenc: Adatbányászati algoritmusok
12
