1
4. LECKE: DÖNTÉSI FÁK - OSZTÁLYOZÁS II. -- Előadás 4.1. Döntési fák [Concepts Chapter 11] A döntési fákon alapuló klasszifikációs eljárás nagy előnye, hogy az alkalmazása révén nemcsak egyedenkénti előrejelzést készíthetünk, hanem teljes képet kapunk az egyes adatbázis-szegmensek összetételről, ami például marketing kampányok tervezésénél döntő fontosságú. Az eljárás szabályokon (rules) alapul, amik lépésről lépésre növesztik az adatok csoportosítását definiáló fagráfot. Hasonló szabályokon alapulnak egyébként a klaszterezési algoritmusok és az asszociációs eljárások is. A döntési fánál a szabályok egyúttal definiálják az adott feltételhez tartozó előrejelzést, ami a szabály megfogalmazása után egyszerűen a többségi elven alapul. Az alábbi példa-ábra jól illusztrálja a lépéseket és a többségi elvet. A 0 jelenti azokat az ügyfeleket, akik nem fognak többet költeni, az 1 pedig azokat akik elképzelhető, hogy növelik költésüket.
4.1. ábra. A döntési fa egy egyszerű példán
A ”score” mutatja az előrejelzést az adott csoportra, a kis négyzetekben az egyes esetek tényleges esetszámai láthatóak. Az algoritmus legfontosabb lépése az egyes csomópontok esetleges további osztása, amely homogenitást mérő metrika alkalmazásával történik. Ugyanakkor, mivel az algoritmus tetszőlegesen sokáig tudja növeszteni a fát, leállási feltételek definiálására is szükség van. Ha ez nem történne meg, akkor a túlillesztés azt eredményezné, hogy a tanuló adathalmazra minden levélen 100%-os pontossággal jelzünk előre, de mivel ez jelentős részben a zaj megjelenése, a teszt adatbázison már közel sem érnénk el ilyen jó eredményeket. Az algoritmus ennek elkerülésére automatikus metszést alkalmaz (nem jönnek létre olyan vágások, amelyek révén az előrejelző erő nem nő szignifikánsan). Lényegesek azok a
2
határfeltételek is, amelyeket a program futtatása során módosíthatunk az adott feladat igényeinek és céljainknak megfelelően. Ezek részletes leírására a következő pontban visszatérünk.
4.2. Diagnosztika A felépített modell ellenőrzésére szolgál a teszt-adatbázis. A legegyszerűbb diagramok egyike a „Confusion matrix”, amely megmutatja, hogy az egyes osztályokhoz tartozó tényleges esetek közül hányszor volt egyezés és hányszor volt tévedés az előrejelzésben (a sorok tartalmazzák a tényadatokat, az oszlopok pedig az előrejelzéseket). Nyilván annál jobb a modell, minél nagyobb részarányban esnek a megfigyelések a főátlóra (ezek a helyes döntések). Ebből számolható a teljes pontosság (overall accuracy rate): a főátlóra eső esetek száma osztva az összes esetszámmal. A bináris célváltozó esetére számolható és grafikusan is megjeleníthető mérőszám a lift (emelés). Ha a célváltozó eredetileg nem lenne bináris, akkor is alkalmazható a módszer: előbb egy pozitívnak tekintett osztályt kell definiálnunk, majd a többi osztályt összevonva megkapjuk a szükséges bináris változót. A lift kiszámításához a pozitív célcsoportba esésük szerinti csökkenő valószínűségek alapján osztályokba soroljuk az eseteket (az első csoportba kerülnek tehát a legvalószínűbbek, és így tovább). Az osztályok száma az ODM-ben alapértelmezés szerint 10, de ez a felhasználó által módosítható. Először megkapjuk csoportonként a pozitív eseteket, ezek kumulált relatív gyakoriságát ábrázolja a „Cumulative Positive Cases Chart”, mint egy eloszlásfüggvényt a kvantilisek függvényében. Az ábra tehát azt adja meg, hogy az adott kvantilisig bezárólag a pozitív esetek hány százaléka volt megtalálható. Ebből adódik, hogy az utolsó kvantilisre az érték mindig 1.
4.2. ábra. A pozitív esetek kumulált diagramja
3
A fenti ábrán jól látható, hogy az első osztályokban nagyobb a pozitív esetek gyakorisága (nagyobb az eloszlásfüggvény meredeksége). Több hivatkozás ezt az ábrát nevezi lift diagramnak. A következő diagnosztika az ODM lift-ábra, amely azt mutatja meg, hogy az egyes csoportokban mennyit javított a modell az előrejelzésen: ha például az adott osztály 40%-a volt pozitív és az ő 80%-ukat sikerült pozitívnak előrejelezni, akkor a lift értéke 80/40=2. Az alábbi ábra mutatja kvantilisenként az előzőek szerinti kumulált lift értékeket.
4.3. ábra. A lift diagramja
Az ábrák mellett táblázatok is készülnek, amelyekben az ábrák adatainak számszerű értékei mellett a valószínűségi küszöbök is szerepelnek. Ezek osztályonként azt a minimális valószínűséget adják meg, ami ahhoz kell, hogy az osztály pozitív célértékei ebbe (vagy megelőző) csoportba kerüljenek. Az ODM teszt diagramjai közül talán a legjobban használható interaktív ábra az ROC görbe. Ez lehetővé teszi a különböző vágási szintek összehasonlítását. Az ábra a false positive (hamis pozitív) döntések részarányának függvényében ábrázolja a true positive (helyes pozitív) döntések részarányát. False positive esetek azok, amikor egy nem pozitív esetet pozitívnak jelzünk, míg true positive esetben a pozitív esetet jelezzük pozitívnak. A legóvatosabb esetben semmit sem definiálunk pozitívnak (ekkor mindkét érték és így a részarány is 0). Az ehhez tartozó valószínűségi szintet tekinthetjük 1-nek, hiszen csak az efölötti valószínűséggel pozitívnak bizonyult eseteket definiáljuk pozitívnak – azaz egyet sem. A másik véglet a legbátrabb eset, amikor minden megfigyelést pozitívnak deklarálunk. Ehhez a 0 valószínűségi szint tartozik, és mindkét részarány 1. Az ábrán ezeket a pontokat összekötő átlót is feltüntetik, mintegy hangsúlyozva azt a különbséget, ami ezen „véletlenszerű” és a modell által definiált szisztematikus klasszifikáció között van. Az interaktivitást az adja, hogy módunk van változtatni a valószínűségi szintet, azaz tetszés szerint állíthatjuk a hamis pozitív döntés részarányát – és láthatjuk az ehhez tartozó helyes pozitív döntések arányát. A program minden esetben ki is számolja az éppen aktuális arányokat és a költségfüggvény értéket.
4
4.4. ábra. Az ROC görbe
A legegyszerűbb diagnosztika a teljes populációra számított arány. Ha megfelelőnek találtuk a modellt, akkor alkalmazhatjuk a megfelelő struktúrájú teszttáblára. Az eredmény táblában minden sorra szerepel a becsült kategória és a hozzá tartozó valószínűség.
-- Gyakorlat 4.3. Döntési fák megvalósítása [Tutorial Chapter 7] A modellépítés-klasszifikáció menüpontban az első választási lehetőség a döntési fa. Itt is szokás szerint először az adattáblát, az egyedi azonosítót kell megadnunk és meg kell határoznunk a célváltozót (most: AFFINITY_CARD). Az „advanced settings” menüben a lehetőségek a következőek: Először a mintavételezést állíthatjuk be. Az alapbeállítás ezt nem alkalmazza, mert az Oracle adatbányász algoritmusai a program szerzői szerint bármilyen méretű adatbázis esetén elfogadható sebességgel működnek. De lehetnek hardver (vagy idő) korlátai a teljes
5
adatbázissal való munkának/kísérletezésnek, ezért gyakran érdemes a véletlen mintavételt alkalmazni. Itt először engedélyeznünk kell ezt a lépést, beállításaink csak ezután válnak valóban végrehajtandóvá. A teljesen véletlen mintavétel mellett a rétegzett modellt (stratified) is választhatjuk, ez különösen a ritka célértéknél (pl. csalások felderítése) lehet lényeges. Ekkor ugyanis az arányos mintavétel igen kicsi esetszámot biztosítana, ami nem teszi lehetővé a hatékony modellépítést. Ekkor a mintát úgy építi fel a program, hogy lehetőleg azonos legyen a célérték és a többi lehetséges érték gyakorisága. Van lehetőségünk a kiugró értékek (outliers) kezelésének beállítására is. Alapértelmezésben az adott változó átlagához képest háromszoros szóráson kívül eső értékeket helyettesíti ezzel a határral. Ennek lehet haszna akkor, amikor félünk, hogy ezek valójában hibás adatok, amelyek jelentősen torzíthatják az eredményeinket, ha eredeti értékükkel szerepelnek. Ugyanakkor a fordított eset is elképzelhető, azaz, hogy ezek az értékek mégiscsak pontosak és fontos információt hordoznak éppen szélsőségességükkel. Tehát ahogy azt már korábban is írtuk, nagyon fontos az adatok előzetes vizsgálata mielőtt az adatbányászat érdemi lépéseihez nekilátnánk. A következő kérdés a hiányzó értékek kezelése. Ez önmagában is egy fontos kérdés, szakkönyvek foglalkoznak a témával. Itt értelemszerűen nincs mód a részletekbe menni. Mindenesetre az óvatosság itt is hasznos. A program alapértelmezésként a folytonos változók hiányzó értékeit az átlagukkal, míg a kategorikus változókét a móduszukkal helyettesíti. Ez logikus lehet, de problémát okozhat akkor, ha a hiányzó értékek nem teljesen véletlenszerűek, hanem összefüggést mutatnak a számunkra fontos célváltozóval. Ezzel a helyettesítéssel az összefüggést teljesen elveszíthetjük. Ezért óvatosabb lehet a hiányzó értékeket már előzetesen külön kategóriaként definiálni és így itt a modell építésnél már nem marad teendő. Ezután eldönthetjük, hogy vajon normalizáljuk-e a folytonos skálán mért változókat. Ez a legtöbb esetben célszerű, mert különben a nagy ingadozást mutató változók túlságosan dominánssá válhatnak a modellben. Ugyanakkor ezt a kérdést sem szabad mechanikusan eldönteni, mert elképzelhető, hogy indokolt az egyes változók nagyobb szerepe. Tehát itt is érdemes lehet esetleg előzetesen, az adattranszformáció során változónkénti egyedi normálás végrehajtása. Itt a normalizálást vagy a minimum-maximum skálára (azaz gyakorlatilag a (0,1) intervallumra való transzformációval vagy a valószínűségszámításban szokásosabb standardizálással valósíthatjuk meg. Ezek után az adatok tanuló- és tesztadatbázisra történő szétosztását állíthatjuk be. Az alapértelmezés 60-40%, de sokszor inkább a 70-30%-ot szokták preferálni. A véletlenítés is alapértelmezett, ettől csak akkor érdemes eltérni, ha különböző módszereket szeretnénk összehasonlítani, mert akkor mindenképpen célszerű fix mintákkal dolgozni az összehasonlíthatóság érdekében. A fentiek mellett a modell algoritmusát is kiválaszthatjuk. A homogenitási metrika alapbeállításának értéke a Gini féle metrika, ami az ágak maximális homogenitását próbálja elérni. Ezen kívül választhatjuk még az entrópia-metrikát, ami az ágak kiegyensúlyozására és az eltérések maximalizálására egyidejűleg törekszik. Ezen kívül beállíthatjuk a fa maximális mélységét (alapbeállítás:7, ez a legtöbb esetben elegendő) a csomópontokban a minimális esetszámot (alapbeállítás: 10, ezt nagy adatbázisoknál érdemes lehet megemelni),
6
a minimális esetszám-százalékot a csomópontokban (alapbeállítás: 0,5, ezt viszont érdemes lehet csökkenteni, ha az esetleges kisebb homogén csoportokra is kíváncsiak vagyunk), a vágásnál a minimális rekordszámot (alapbeállítás: 20, ezt nagy adatbázisoknál érdemes lehet megemelni, összhangban a csomópontok minimális esetszámával) a minimális esetszám-százalékot a vágásoknál (alapbeállítás: 1, ezt is érdemes lehet csökkenteni, ha az esetleges kisebb homogén csoportokra is kíváncsiak vagyunk, összhangban a csomópontok minimális esetszám-részarányával). Az alapbeállításokkal eredményül kapott modellt mutatja a következő táblázat.
4.5. táblázat. Az alapbeállítással kapott döntési fa eredménye
Láthatók a fa-építés lépései: először a háztartás mérete alapján történt vágás, majd csoportoktól függően vagy a foglalkozás vagy a kor, vagy a családi állapot volt a következő szempont. A „Predicted” oszlopról leolvasható az adott osztályra előrejelzett „AFFINITY_CARD” érték, ami csak egyetlen esetben bizonyult 1-nek. A megbízhatóság (confidence) az adott csoportra számított előrejelzés helyességének valószínűsége (az esetszámok alapján a relatív gyakorisággal becsülve), a következő oszlop a csoport elemszáma, végül a támogatottság (support) a csoportba esés relatív gyakorisága. Nézzük meg, milyen eltérés adódik, ha az entrópia-metrikát választjuk.
7
4.6. táblázat. Az entrópia-metrikával kapott döntési fa eredménye
Látható, hogy nincs nagy különbség, csupán annyival egyszerűsödött a modell, hogy a családi állapot nem szerepel benne.
8
4.7. ábra. ROC görbe
Az ROC görbe és a statisztikák viszont ugyanazt az eredményt adják, mint az előző esetben, hiszen az az egy levél, ahol az 1-es csoportot jeleztük előre, változatlan maradt. Tehát ha választani kell, akkor az egyszerűbb modell mellett dönthetünk.
