5. fejezet - Osztályozás: Alternatív módszerek

Tartalom

Szabályalapú osztályozó
A szabályalapú osztályozó működése
Szabályrendezési sémák
Szabályalapú osztályozó építése
Szabálykinyerés direkt módszerekkel
Szabálykinyerés indirekt módszerekkel
Szabályalapú osztályozók jellemzése
Legközelebbi szomszéd osztályozók
Algoritmus
A legközelebbi szomszéd osztályozó jellemzői
Bayes-féle osztályozók
Bayes-tétel
A Bayes-tétel felhasználása osztályozásra
Naiv Bayes-féle osztályozó
Bayes-féle hibaarány
Bayes-féle bizonyossághálók
Mesterséges neurális hálók
Perceptron
Többrétegű mesterséges neurális hálók
Az ANN jellemzői
Tartóvektor-gép (SVM)
Maximális margójú hipersíkok
Lineáris SVM: szeparálható eset
Lineáris SVM: nem szeparálható eset
Nemlináris SVM
Az SVM jellemzői
Együttes módszerek
Az együttes módszer magyarázata
Módszerek együttes osztályozó építésére
Torzítás-variancia felbontás
Zsákolás
Gyorsítás
Véletlen erdők
Együttes módszerek közötti empirikus összehasonlítás
Az osztály-kiegyensúlyozatlanság problémája
Alternatív metrikák
A vevő működési karakterisztika (ROC) görbe
Költségérzékeny tanulás
Mintavételezés-alapú módszerek
Többosztályos problémák
Irodalmi megjegyzések
Feladatok

Az előző fejezet egy egyszerű, mégis elég hatékony, döntési fa indukció nevű osztályozási módszert írt le. Részletesen tárgyalásra kerültek olyan kérdések is, mint a modell túlillesztés és az osztályozók kiértékelése. Ez a fejezet alternatív módszereket mutat be osztályozási modellek építéséhez, olyan egyszerű módszerekkel kezdve, mint a szabályalapú és legközelebbi szomszéd osztályozók, olyan fejlettebb módszerekig, mint a tartóvektor-gépek és együttes módszerek. További kulcsfontosságú kérdések is tárgyalásra kerülnek a fejezet végén, mint például az osztály-kiegyensúlyozatlanság és a többosztályos problémák.

Szabályalapú osztályozó

A szabályalapú osztályozó (rule-based classifier) egy módszer rekordok ``ha akkor '' szabályokkal való osztályozásához. Az 5.1. táblázatban egy olyan modellre látható példa, amelyet egy szabályalapú osztályozó generált a gerincesek osztályozási feladatához.

5.1. táblázat - Példa a gerincesek osztályozási feladatának szabályhalmazára

r 1 :

(Elevenszülő = nem) (Tud repülni = igen) Madarak

r 2 :

(Elevenszülő = nem) (Vízben él = igen) Halak

r 3 :

(Elevenszülő = igen) (Testhőmérséklet = melegvérű) Emlősők

r 4 :

(Elevenszülő = nem) (Tud repülni = nem) Hüllők

r 5 :

(Vízben él = félig) Kétéltűek


A modell szabályait egy R=( r 1 r 2 r k ) diszjunktív normálformában ábrázoljuk, ahol R úgynevezett szabályhalmaz (rule set), r i -k pedig osztályozási szabályok (classification rules) vagy diszjunktok (disjuncts). Minden osztályozási szabály az alábbi módon fejezhető ki:

r i :(Feltéte l i ) y i . (5.1)

A szabály bal oldalát szabály antecendensnek (rule antecedent) vagy előfeltételnek (precondition) nevezzük. Ez attribútumtesztek egy konjunkcióját tartalmazza:

Feltéte l i =( A 1   op   v 1 )( A 2   op   v 2 )( A k   op   v k ), (5.2)

ahol ( A j , v j ) egy attribútum-érték pár, op pedig egy a {=,,,,,} halmazból választott összehasonlító operátor. Az ( A j   op   v j ) attribútumteszteket konjunktoknak (conjuncts) nevezzük. Szabály következménynek (rule consequent) nevezzük a szabály jobb oldalát, amely az y i előrejelzett osztályt tartalmazza.

Az r szabály lefedi (covers) az x rekordot akkor, ha r előfeltétele illeszkedik x attribútumaira. Amikor r lefed egy adott rekordot, akkor azt is mondjuk, hogy tüzel vagy a rekord kiváltja. Szemléltetésként tekintsük 18 táblázatban adott r 1 szabályt, valamint két gerinces, a sólyom és a grizzly medve alábbi attribútumait.

Név

Test-

Bőr

Eleven-

Vízben

Tud

Van

Téli álmot

hőmérséklet

függelékei

szülő

él

repülni

lába

alszik

sólyom

melegvérű

toll

nem

nem

igen

igen

nem

grizzly medve

melegvérű

bunda

igen

nem

nem

igen

igen

Az r 1 szabály lefedi az első gerincest, mivel az előfeltételét kielégítik a sólyom attribútumai. A szabály nem fedi le a második gerincest, mivel a grizzly medvék elevenen szülik meg kicsinyeiket és nem tudnak repülni, így megsértik r 1 előfeltételét.

Az osztályozási szabályok minőségének értékeléséhez olyan mértékeket használhatunk, mint például a lefedettség (coverage) és pontosság (accuracy). Egy adott D adathalmaz és egy r:Ay osztályozási szabály esetén a szabály lefedettségét úgy definiáljuk, mint az r szabályt kiváltó D -beli rekordok arányát. Ugyanakkor a pontosságát vagy konfidencia faktorát (confidence factor) úgy definiáljuk, mit azon r által kiváltott rekordok arányát, amelyek osztálycímkéje y . Ezen mértékek formális definíciója:

Lefedettség(r)= |A| |D| ,

Pontosság(r)= |A y| |A| , (5.3)

ahol |A| a szabály antecendensét kielégítő rekordok száma, |A y| az antecendenst és a konzekvenst is kielégítő rekordok száma, |D| pedig a rekordok teljes száma.

5.1. Példa.

Tekintsük az 5.2. táblázatban látható adatokat. Az

(Elevenszülő = igen)(Testhőmérséklet = melegvérű)Emlősők

szabály lefedettsége 33%, mert a tizenöt rekord közül öt támasztja alá a szabály antecendensét. A szabály pontossága 100% , mert az általa lefedett mind az öt gerinces emlős.

5.2. táblázat - A gerincesek adatai

Név

Test-

Bőr

Eleven-

Vízben

Tud

Van

Téli álmot

Osztály-

hőmérséklet

függelékei

szülő

él

repülni

lába

alszik

címke

ember

melegvérű

szőr

igen

nem

nem

igen

nem

Emlősők

óriáskígyó

hidegvérű

pikkely

nem

nem

nem

nem

igen

Hüllők

lazac

hidegvérű

pikkely

nem

igen

nem

nem

nem

Halak

bálna

melegvérű

szőr

igen

igen

nem

nem

nem

Emlősők

béka

hidegvérű

nincs

nem

félig

nem

igyen

igen

Kétéltűek

komodói

hidegvérű

pikkely

nem

nem

nem

igen

nem

Hüllők

sárkány

denevér

melegvérű

szőr

igen

nem

igen

igen

igen

Emlősők

galamb

melegvérű

toll

nem

nem

igen

igen

nem

Madarak

macska

melegvérű

bunda

igen

nem

nem

igen

nem

Emlősők

guppi

hidegvérű

pikkely

igen

igen

nem

nem

nem

Halak

alligátor

hidegvérű

pikkely

nem

félig

nem

igen

nem

Hüllők

pingvin

melegvérű

toll

nem

félig

nem

igen

nem

Madarak

tarajos sül

melegvérű

tüske

igen

nem

nem

igen

nem

Emlősők

angolna

hidegvérű

pikkely

nem

igen

nem

nem

nem

Halak

szalamandra

hidegvérű

nincs

nem

félig

nem

igen

igen

Kétéltűek


A szabályalapú osztályozó működése

A szabályalapú osztályozó egy tesztrekordot a rekord által kiváltott szabály alapján osztályoz. A szabályalapú osztályozó működésének szemléltetéséhez tekintsük az 5.1. táblázatban adott szabályhalmazt és az alábbi gerinceseket:

Név

Test-

Bőr

Eleven-

Vízben

Tud

Van

Téli álmot

hőmérséklet

függelékei

szülő

él

repülni

lába

alszik

makimajom

melegvérű

bunda

igen

nem

nem

igen

igen

teknősbéka

hidegvérű

pikkely

nem

félig

nem

igen

nem

macskacápa

hidegvérű

pikkely

igen

igen

nem

nem

nem

  • Az első gerinces a makimajom, amely melegvérű és elevenen szüli meg a kicsinyeit. Ez az r 3 szabályt váltja ki, így tehát emlősként osztályozzuk.

  • A második gerinces a teknősbéka, amely az r 4 és r 5 szabályokat váltja ki. Mivel a szabályok által előrejelzett osztályok ellentmondóak (hüllők a kétéltűek ellenében), fel kell oldani az osztályok egymásnak ellentmondását.

  • Egyik szabály sem alkalmazható a macskacápára. Ebben az esetben biztosítanunk kell azt, hogy az osztályozó még ilyenkor is megbízható előrejelzést tudjon adni, bár a tesztrekordot egyetlen szabály sem fedi le.

Az előző példa a szabályalapú osztályozó által generált szabályhalmaz két fontos tulajdonságát szemlélteti.

Egymást kölcsönösen kizáró szabályok (mutually exclusive rules)

Az R szabályhalmaz szabályai egymást kölcsönösen kizáróak, ha egyetlen rekord sem vált ki két különböző szabályt. Ez a tulajdonság biztosítja azt, hogy minden rekordot legfeljebb egy R -beli szabály fed le. Az 5.3. táblázatban egy példa látható egymást kölcsönösen kizáró szabályokból álló szabályhalmazra.

Kimerítő szabályok (exhaustive rules)

Egy R szabályhalmaz kimerítő lefedettségű, ha az attribútumértékek minden kombinációjához van szabály. Ez a tulajdonság biztosítja azt, hogy minden rekordot legalább egy R -beli szabály lefed. Feltéve azt, hogy a Testhőmérséklet és Elevenszülő változók binárisak, az 5.3. táblázatban látható szabályhalmaz kimerítő lefedettségű.

5.3. táblázat - Példa kölcsönösen kizáró és kimerítő szabályhalmazra

r 1 : (Testhőmérséklet = hidegvérű) Nem emlősök

r 2 : (Testhőmérséklet = melegvérű) (Elevenszülő = igen) Emlősők

r 3 : (Testhőmérséklet = melegvérű) (Elevenszülő = nem) Nem emlősök


Ezek a tulajdonságok együtt azt biztosítják, hogy minden rekordot pontosan egy szabály fed le. Sajnos sok szabályalapú osztályozó -- köztük az 5.1. táblázatban látható -- nem rendelkezik ilyen tulajdonságokkal. Ha a szabályhalmaz nem kimerítő, akkor egy r d :  () y d alapértelmezett szabályt kell hozzáadni a fennmaradó esetek lefedéséhez. Az alapértelmezett szabály antecendense üres, és az váltja ki, ha az összes többi szabály kudarcot vallott. y d -t alapértelmezett osztálynak nevezzük és jellemzően a meglevő szabályok által nem lefedett tesztrekordok többségi osztályához rendeljük hozzá.

Ha a szabályhalmaz nem kölcsönösen kizáró, akkor egy rekordot több szabály fedhet le, amelyek közül némelyek ellentmondó osztályokat prediktálhatnak. Két mód van ennek a problémának a leküzdésére.

Rendezett szabályok (ordered rules)

Ennél a módszernél a szabályhalmaz szabályai prioritásuk szerint csökkenő sorrendbe rendezettek. A prioritás többféle módon definiálható, például pontosság, lefedettség, a teljes leíró hossz, vagy a szabályok generálásának sorrendje alapján. A rendezett szabályhalmazokat döntési listáknak (decision lists) is nevezzük. Egy tesztrekord osztályozása az azt lefedő legnagyobb prioritású szabály alapján történik. Így elkerüljük a több osztályozási szabály által előrejelzett ellentmondó osztályok problémáját.

Rendezetlen szabályok (unordered rules)

Ez a módszer lehetővé teszi, hogy egy tesztrekord több osztályozási szabályt váltson ki, és minden egyes szabály konzekvensét egy bizonyos osztályra szavazásnak tekinti. A szavazatokat ezután összeszámláljuk a tesztrekord osztálycímkéjének meghatározásához. A rekordot általában a legtöbb szavazatott kapott osztályhoz rendeljük hozzá. Bizonyos esetekben a szavazat a szabály pontosságával súlyozható. Előnyei és hátrányai is vannak annak, ha rendezetlen szabályokat használunk szabályalapú osztályozó építéséhez. A rendezetlen szabályok kevésbé érzékenyek a hibákra, amelyeket egy tesztrekord osztályozásához rosszul kiválasztott szabály okoz (eltérően a rendezett szabályokon alapuló osztályozóktól, amelyek érzékenyek a szabályrendezési kritérium megválasztására). A modellépítés is kevésbé költséges, mivel a szabályokat nem szükséges rendezett sorrendben tárolni. Mindazonáltal egy tesztrekord osztályozása elég költséges feladat lehet, mert a tesztrekord attribútumait a szabályhalmaz minden szabályának előfeltételével össze kell hasonlítani.

A szakasz további részében olyan szabályalapú osztályozókra összpontosítunk, amelyek rendezett szabályokat használnak.

Szabályrendezési sémák

A szabályrendezés megvalósítható szabályonként egyesével és osztályonként. Az ezek közötti eltérést az 5.1. ábra szemlélteti.

5.1. ábra - Szabályalapú és osztályalapú rendezési séma összehasonlítása

Szabályalapú és osztályalapú rendezési séma összehasonlítása

Szabályalapú rendezési séma (rule-based ordering scheme)

Ez a módszer az egyes szabályokat valamilyen minőségi mérték alapján rendezi. Ez a rendezési séma biztosítja azt, hogy minden tesztrekord osztályozása a ``legjobb'' azt lefedő szabály alapján történik. Ennek a sémának egy lehetséges hátránya az, hogy sokkal nehezebb az alacsonyabb rangú szabályok értelmezése, mivel ezek feltételezik az őket megelőző szabályok negációját. Az 5.1. ábrán például a szabályalapú rendezésnél látható negyedik szabály

Vízbenél=féligHüllők,

amely értelmezése a következő: Ha egy gerinces nem tollas vagy nem tud repülni, valamint hidegvérű és félig vízi, akkor hüllő. A további feltételek (melyek szerint a gerinces nem tollas vagy nem tud repülni, valamint hidegvérű) abból adódnak, hogy a gerinces nem elégíti ki az első három szabályt. Nagyszámú szabály esetén a lista végéhez közeli szabályok jelentésének értelmezése nehéz feladat lehet.

Osztályalapú rendezési séma (class-based ordering scheme)

Ennél a módszernél az ugyanahhoz az osztályhoz tartozó szabályok együtt jelennek meg az R szabályhalmazban. Ezután a szabályok az osztályinformáció alapján csoportosan kerülnek rendezésre. Az egy osztályhoz tartozó szabályok relatív sorrendje nem lényeges, amennyiben a szabályok egyike tüzel, az osztály hozzá lesz rendelve a tesztrekordhoz. Ez kissé megkönnyíti a szabályok értelmezését. El lehet siklani azonban egy jó minőségű szabály felett egy rosszabb minőségű szabály javára, amely véletlenül éppen a magasabb rangú osztályt prediktálja.

Mivel a legtöbb közismert szabályalapú osztályozó (mint például a C4.5rules és a RIPPER) az osztályalapú rendezést használja, a szakasz további részében a tárgyalás elsősorban erre a fajta rendezési sémára koncentrál.

Szabályalapú osztályozó építése

Szabályalapú osztályozó építéséhez ki kell nyerni szabályok egy olyan halmazát, amely az adathalmaz attribútumai és az osztálycímke közötti kulcsfontosságú összefüggéseket azonosítja. Az osztályozási szabályok kinyerésére szolgáló módszereknek két nagy osztálya van: (1) a direkt módszerek, amelyek az osztályozási szabályokat közvetlenül az adatokból nyerik ki, valamint (2) az indirekt módszerek, amelyek az osztályozási szabályokat más osztályozási modellekből (például döntési fákból és neurális hálókból) nyerik ki.

A direkt módszerek az attribútumteret kisebb alterekre osztják fel úgy, hogy az egy altérbe tartozó rekordok mindegyike egyetlen osztályozási szabállyal sorolható be. Az indirekt módszerek osztályozási szabályokat használnak arra, hogy összetettebb osztályozási modellekről adjanak tömör leírást. Ezeket a módszereket részletesen az 5.1.4. és az 5.1.5. szakaszok tárgyalják.

Szabálykinyerés direkt módszerekkel

A szekvenciális lefedés (sequential covering) egy gyakran használt algoritmus szabályok közvetlenül az adatokból való kinyeréséhez. A szabályok építése mohó módon történik egy bizonyos kiértékelési mérték alapján. A kettőnél több osztályt tartalmazó adathalmazokból az algoritmus osztályonként nyeri ki a szabályokat. A gerincesek osztályozási feladatához a szekvenciális lefedési algoritmus először a madarak osztályozására szolgáló szabályokat generálhatja, amelyeket az emlősök, kétéltűek, hüllők, végül pedig a halak osztályozására szolgáló szabályok követhetnek (lásd az 5.1. ábrát). Több tényezőtől függ az a kritérium, amellyel eldönthető, hogy először melyik osztályt kell generálni. Ilyen például az osztályok prevalenciája (azaz egy bizonyos osztályhoz tartozó tanulórekordok aránya) vagy az adott osztályból származó rekordok hibás osztályozásának költsége.

5.1. algoritmus. Szekvenciális lefedési algoritmus

1: Jelölje E a tanulórekordokat, A az attribútum-érték párok {( A j , v j )} halmazát

2: Jelölje Y o osztályok egy rendezett { y 1 , y 2 ,, y k } halmazát

3: Legyen R={  } a kiindulási szabálylista

4:for minden y Y o { y k } osztályra do

5: while nem teljesül a megállási feltétel do

6: r Tanul-Egy-Szabályt ( E , A , y )

7: Az r által lefedett tanulórekordok törlése E -ből

8: r hozzáadása a szabálylista végéhez: RRr

9: end while

10: end for

11: Az {} y k alapértelmezett szabály beszúrása az R szabálylista végére

A szekvenciális lefedési algoritmus összefoglalását az 5.1. algoritmus tartalmazza. Az algoritmus egy üres R döntési listával indul. Ezután a Tanul-Egy-Szabályt függvénnyel nyeri ki az y osztályhoz a legjobb szabályt, amely lefedi a tanulórekordok aktuális halmazát. A szabálykinyerés során az y osztály tanulórekordjait pozitív esetként tekintjük, míg a többi osztályhoz tartozókat pedig negatív esetként. Egy szabály akkor kívánatos, ha lefedi a pozitív esetek többségét és egyetlen negatív esetet sem fed le (vagy csak nagyon keveset). Amint egy ilyen szabályt találunk, az általa lefedett tanulórekordok eltávolításra kerülnek. Az új szabályt az R döntési lista végéhez adjuk hozzá. Az eljárást a megállási feltétel teljesüléséig ismételjük. Ezután az algoritmus továbblép a következő osztály szabályainak generálására.

Az 5.2. ábra a szekvenciális lefedési algoritmus működését szemlélteti pozitív és negatív eseteket tartalmazó adatokra. Az 5.2. (b) ábrán látható lefedettségű R1 szabály lesz először kinyerve, mivel ez fedi le a pozitív esetek legnagyobb részét. Az R1 által lefedett tanulórekordok ezt követően eltávolításra kerülnek és az algoritmus továbblép a következő legjobb szabály keresésére, amely R2 .

5.2. ábra - Példa a szekvenciális lefedési algoritmusra

Példa a szekvenciális lefedési algoritmusra

A Tanul-Egy-Szabályt függvény

A Tanul-Egy-Szabályt függvény célja egy olyan osztályozási szabály kinyerése, amely a tanulóhalmazban sok pozitív esetet fed le és egyetlen negatív esetet sem (vagy csak nagyon keveset). Optimális szabály meghatározása azonban számításigényes a keresési tér exponenciális mérete miatt. A Tanul-Egy-Szabályt függvény az exponenciális keresési probléma kezeléséhez a szabályokat mohó módon építi fel. Egy kiindulási r szabályt generál, amelyet egy adott megállási feltétel teljesüléséig finomít. A szabályt végül lenyessük, hogy javuljon az általánosítási hibája.

5.3. ábra - Specializáló és általánosító szabályépítési stratégia

Specializáló és általánosító szabályépítési stratégia

Szabályépítési stratégia (rule-growing strategy)

Két gyakori stratégia van osztályozási szabályok építéséhez: specializáló (general-to-specific) és általánosító (specific-to-general). A specializáló stratégia esetén egy r:{}y kiindulási szabály kerül létrehozásra, amelyben a bal oldal az üres halmaz, a jobb oldal pedig a célosztályt tartalmazza. A szabály gyenge minőségű, mivel minden esetet lefed a tanulóhalmazban. A minőség javításához a későbbiekben a szabályhoz új konjunktok adódnak hozzá. Az 5.3. (a) ábra a specializáló szabályépítési stratégiát mutatja be a gerincesek osztályozási feladatához. A szabály antecendens képzéséhez először a Testhőmérséklet = melegvérű konjunkt kerül kiválasztásra. Ezután az algoritmus feltárja az összes lehetséges jelöltet, és mohón választja a következő, Elevenszülő = igen konjunktot, hozzáadja az antecendenshez. Ez az eljárás a megállási feltétel teljesüléséig ismétlődik (például addig, amikor a konjunkt hozzáadása már nem javítja a szabály minőségét).

Az általánosító stratégiánál a pozitív esetek valamelyikét véletlenszerűen választjuk kezdőértékül a szabályépítési eljáráshoz. A finomítási lépésben a szabály általánosításra kerül valamelyik konjunkt eltávolításával úgy, hogy az több pozitív esetet tud lefedni. Az 5.3. (b) ábrán az általánosító módszer látható a gerincesek osztályozási feladatához. Tegyük fel, hogy kezdőértékül pozitív esetként egy emlőst választunk. A kiindulási szabály pontosan ugyanazokat a konjunktokat tartalmazza, mint a kezdőérték attribútumértékei. Lefedettségének javításához a szabály általánosításra kerül a Téli álmot alszik = nem konjunkt eltávolításával. A finomítási lépés a megállási feltétel teljesüléséig ismétlődik, például addig, amikor a szabály már negatív példákat kezd lefedni.

Az előző módszerek szuboptimális szabályokat állíthatnak elő a szabályok mohó módra való építése miatt. A probléma elkerüléséhez nyaláb keresés használható, ahol az algoritmus a k legjobbat tartja meg a szabályjelöltek közül. Minden egyes szabályjelölt építése külön történik, az antecendeshez egy konjunkt hozzáadásával, vagy belőle egy konjunkt törlésével. Kiértékeljük a jelöltek minőségét, és a legjobb k jelöltet választjuk ki a következő iterációhoz.

Szabálykiértékelés (rule evaluation)

Egy kiértékelési metrika szükséges annak meghatározásához, hogy melyik konjunkt hozzáadása (vagy törlése) szükséges a szabályépítő eljárás során. A pontosság egy kézenfekvő választás, mivel ez kifejezetten a szabály által helyesen osztályozott tanulóesetek arányát méri. Azonban a pontosság egy lehetséges korlátja az, hogy nem veszi figyelembe a szabály lefedettségét. Tekintsünk például egy olyan tanulóhalmazt, amely 60 pozitív esetet és 100 negatív esetet tartalmaz. Tegyük fel, hogy az alábbi két szabályjelöltet kapjuk:

r 1 szabály: 50 pozitív esetet és 5 negatív esetet fed le,

r 2 szabály: 2 pozitív esetet fed le és egyetlen negatív esetet sem.

Az r 1 és r 2 szabályok pontossága 90,9% illetve 100%. Azonban r 1 a jobb szabály a kisebb pontossága ellenére. Az r 2 szabály nagy pontossága potenciálisan megtévesztő, mivel a lefedettsége túl kicsi.

Az alábbi módszerek használhatóak ennek a problémának a kezelésére:

1. Statisztikai próba használható a gyenge lefedettségű szabályok lenyeséséhez. Kiszámítható például az alábbi likelihood-hányados statisztika:

R=2 i=1 k f i log( f i / e i ),

ahol k az osztályok száma, f i az i osztály azon eseteinek megfigyelt gyakorisága, amelyeket a szabály lefed, e i pedig egy véletlenszerű előrejelzéseket adó szabály várható gyakorisága. Megjegyezzük, hogy R χ 2 eloszlású k1 szabadsági fokkal. Nagy R érték azt jelzi, hogy a szabály általi helyes előrejelzések száma jelentősen nagyobb, mint véletlen találgatás esetén várható. Mivel például r 1 55 példát fed le, a pozitív osztály várható gyakorisága e + =55×60/160=20,625 , míg a negatív osztály várható gyakorisága e =55×100/160=34,375 . Így tehát r 1 likelihood-hányadosa

R( r 1 )=2×[50× log 2 (50/20,625)+5× log 2 (5/34,375)]=99,9.

Hasonlóan, a várható gyakoriságok r 2 -re e + =2×60/160=0,75 és e =2×100/160=1,25 . Így r 2 likelihood-hányados statisztikája

R( r 2 )=2×[2× log 2 (2/0,75)+0× log 2 (0/1,25)]=5,66.

A statisztika így azt jelzi, hogy r 1 jobb szabály, mint r 2 .

2. Használható a szabály lefedettségét figyelembe vevő kiértékelési metrika. Tekintsük a következő kiértékelési metrikákat:

Laplace= f + +1 n+k , (5.4)

Mbecslés= f + +k p + n+k , (5.5)

ahol n a szabály által lefedett minták száma, f + a szabály által lefedett pozitív példák száma, k az osztályok száma és p + a pozitív osztály a priori valószínűsége. Megjegyezzük, hogy az M -becslés p + =1/k választással ekvivalens a Laplace-mértékkel. A szabály lefedettségtől függve ezek a mértékek a szabály pontossága és a pozitív osztály a priori valószínűsége közötti kompromisszumot fejezik ki. Ha a szabály nem fed le egy tanulómintát sem, akkor a Laplace-mérték 1/k -ra egyszerűsödik, amely a pozitív osztály a priori valószínűsége egyenletes osztályeloszlást feltételezve. Az M -becslés is az a priori valószínűségre egyszerűsödik, ha n=0 . Mindazonáltal, ha a szabály lefedettsége nagy, akkor mindkét mérték aszimptotikusan tart az f + /n szabály pontossághoz. Visszatérve az előző példára, r 1 Laplace-mértéke 51/57=89,47% , amely nagyon közel van a pontosságához. Viszont r 2 Laplace-mértéke ( 75% ) jelentősen kisebb, mint a pontossága, mivel r 2 sokkal kisebb lefedettségű.

3. Használható egy olyan kiértékelési metrika is, amely figyelembe veszi a szabály támogatottsági számát. Egy ilyen metrika a FOIL-féle információ-nyereség (FOIL's information gain). Egy szabály támogatottsági száma (support count) a szabály által lefedett pozitív esetek számának felel meg. Tegyük fel, hogy az r:A+ szabály p 0 pozitív esetet és n 0 negatív esetet fed le. Egy új B konjunkt hozzáadása után az r':AB+ kibővített szabály p 1 pozitív esetet és n 1 negatív esetet fed le. Ha adott ez az információ, a kibővített szabály FOIL-féle információ-nyereségét a következő módon definiáljuk:

FOILféleinformációnyereség=

p 1 ×( log 2 p 1 p 1 + n 1 log 2 p 0 p 0 + n 0 ). (5.6)

Mivel a mérték a p 1 és p 1 /( p 1 + n 1 ) értékekkel arányos, a nagy támogatottsági számú és pontosságú szabályokat részesíti előnyben. A korábbi példában szereplő r 1 és r 2 szabályok FOIL-féle információ-nyeresége 63,87 és 2,83 . Ezért r 1 jobb szabály, mint r 2 .

Szabálynyesés (rule pruning)

A Tanul-Egy-Szabályt függvény által generált szabályokat le lehet nyesni az általánosítási hibájuk javításához. A 178. oldalon a 4.4. szakaszban leírt módszereket alkalmazhatjuk egy szabály általánosítási hibájának becsléséhez annak megállapítására, hogy szükség van-e nyesésre. Ha a nyesés után például csökken a validációs halmazon mért hiba, akkor az egyszerűsített szabályt kell megtartani. Egy másik módszer a szabály pesszimista hibájának összehasonlítása a nyesés előtt és után (lásd a 4.4.4. szakaszt a 185. oldalon). Ha a pesszimista hiba javul a nyesés után, akkor az egyszerűsített szabályt tartjuk meg az eredeti szabály helyett.

A szekvenciális lefedés magyarázata

Egy szabály kinyerése után a szekvenciális lefedési algoritmus el kell, hogy távolítsa a szabály által lefedett valamennyi pozitív és negatív esetet. Ennek indoklását adja meg a következő példa.

5.4. ábra - Tanulórekordok eltávolítása a szekvenciális algoritmussal. R1 , R2 és R3 három különböző szabály által lefedett régiókat reprezentálnak.

Tanulórekordok eltávolítása a szekvenciális algoritmussal. R1, R2 és R3 három különböző szabály által lefedett régiókat reprezentálnak.

Az 5.4. ábrán egy 29 pozitív esetet és 21 negatív eset tartalmazó adatokból kinyert három lehetséges szabály, R1 , R2 és R3 látható. R1 , R2 és R3 pontossága 12/15 (80%), 7/10 (70%) és 8/12 (66,7%). Először R1 -et generáljuk, mivel ez a legnagyobb pontosságú. R1 generálása után világos, hogy a szabály által lefedett pozitív eseteket el kell távolítani, hogy az algoritmus által generált következő szabály különbözzön R1 -től. Most tegyük fel, hogy az algoritmus megválaszthatja azt, hogy R2 -t vagy R3 -at generálja. Annak ellenére, hogy R2 nagyobb pontosságú, mint R3 , R1 és R3 együtt 18 pozitív és 5 negatív esetet fed le ( 78,3% -os pontosságot eredményezve), amíg R1 és R2 együtt 19 pozitív esetet és 6 negatív esetet fed le ( 76% -os pontosságot eredményezve). R2 vagy R3 járulékos hatása a pontosságra sokkal nyilvánvalóbb, ha az R1 által lefedett pozitív és negatív eseteket eltávolítjuk a pontosságuk kiszámítása előtt. Ha az R1 által lefedett pozitív eseteket nem távolítjuk el, akkor túlbecsülhetjük R3 tényleges pontosságát, ha pedig nem távolítjuk el a negatív eseteket, akkor alulbecsülhetjük R3 pontosságát. Az utóbbi esetben végül R2 R3 fölé helyezésére juthatunk annak ellenére, hogy az R3 által elkövetett hamis pozitív hibák felét az előző szabály, R1 számlájára írtuk.

RIPPER algoritmus

A közvetlen módszerek szemléltetéséhez a széles körben használt szabályindukciós RIPPER algoritmust tekintjük. Ez az algoritmus a tanulóesetek számával közel lineárisan skálázódik és különösen alkalmas modellek kiegyensúlyozatlan adatokból történő építésére. A RIPPER zajos adatokkal is jól működik, mivel a modell túlillesztés elkerüléséhez egy validációs halmazt használ.

Kétosztályos problémákhoz a RIPPER a többségi osztályt választja alapértelmezett osztályként és a kisebbségi osztály felismeréséhez tanulja meg a szabályokat. Többosztályos problémák esetén az osztályokat gyakoriság szerint rendezi. Jelölje ( y 1 , y 2 ,, y c ) a rendezett osztályokat, ahol y 1 a legkisebb, y c pedig a legnagyobb gyakoriságú osztály. Az első iterációban az y 1 osztályhoz tartozó példányokat pozitív esetként címkézzük, míg a többi osztályhoz tartozókat negatív esetként. A szekvenciális lefedési algoritmust használjuk a pozitív és negatív eseteket megkülönböztető szabályok generálásához. Ezután a RIPPER az y 2 -t a fennmaradó osztályoktól megkülönböztető szabályokat nyer ki. Az eljárást addig ismételjük, amíg y c nem marad, amelyet alapértelmezett osztályként jelölünk ki.

Szabályépítés

A RIPPER egy specializáló stratégiát alkalmaz a szabályok építéséhez és a FOIL-féle információ-nyereség mértéket alkalmazza az antecendeshez adandó legjobb konjunkt kiválasztásához. Akkor hagyja abba a konjunktok hozzáadását, amikor a szabály negatív eseteket kezd lefedni. Ezután az új szabályt lenyessük a validációs halmazon mért teljesítménye alapján. Az alábbi metrikát számítjuk ki annak megállapításához, hogy szükséges-e nyesés: (pn)/(p+n) , ahol p ( n ) a szabály által lefedett pozitív (negatív) esetek száma a validációs halmazban. Ez a metrika monoton kapcsolatban van a szabály validációs halmazon mért pontosságával. Ha a metrika javul a nyesés után, akkor a konjunktot eltávolítjuk. A nyesés a szabályhoz utoljára hozzáadott konjunkttal kezdve történik. Például ha egy ABCDy szabály adott, akkor a RIPPER először azt ellenőrzi, hogy le kell-e nyesni D -t, majd a CD , BCD stb. következnek. Míg az eredeti szabály csak pozitív eseteket fed le, a lenyesett szabály lefedheti a tanulóhalmaz negatív eseteinek egy részét is.

A szabályhalmaz építése

Egy szabály generálása után eltávolításra kerülnek az általa lefedett pozitív és negatív esetek. Ezután a szabályt hozzáadjuk a szabályhalmazhoz, feltéve, hogy ez nem sérti meg a megállási feltételt, amely a legrövidebb leíró hossz elvén alapul. Ha az új szabály legalább d bittel növeli a szabályhalmaz teljes leíró hosszát, akkor a RIPPER befejezi a szabályok hozzáadását a szabályhalmazhoz (alapértelmezés szerint d -t 64 bitnek választjuk). A RIPPER által használt egy másik megállási feltétel az, hogy a validációs halmazon mért hibaarány nem haladhatja meg az 50%-ot.

A RIPPER további optimalizációs lépéseket is végez annak megállapításához, hogy lehet-e a meglevő szabályok közül némelyeket jobb alternatív szabályokkal helyettesíteni. Az optimalizációs eljárás részletei iránt érdeklődő olvasók a fejezet végén idézett hivatkozáshoz fordulhatnak.

Szabálykinyerés indirekt módszerekkel

Ez a szakasz egy módszert mutat be szabályhalmaz generálására döntési fából. Elvileg minden a gyökércsúcsból a döntési fa egy levélcsúcsába vezető út kifejezhető egy osztályozási szabályként. Az út mentén található konjunktok alkotják az antecendenst, míg a levélcsúcs osztálycímkéjét a szabály konzekvenséhez rendeljük hozzá. Az 5.5. ábrán látható egy döntési fából generált szabályhalmaz. Vegyük észre, hogy a szabályhalmaz kimerítő és hogy egymást kölcsönösen kizáró szabályokat tartalmaz. Némelyik szabály azonban egyszerűsíthető, amint az a következő példában is látható.

5.2. Példa.

Tekintsük a következő három szabályt az 5.5. ábráról:

5.5. ábra - Döntési fa osztályozási szabályokká alakítása

Döntési fa osztályozási szabályokká alakítása

r2:(P=Nem)(Q=Igen)+

r3:(P=Igen)(R=Nem)+

r5:(P=Igen)(R=Igen)(Q=Igen)+

Vegyük észre, hogy a szabályhalmaz mindig pozitív osztályt prediktál, ha Q értéke Igen. Ezért a szabályokat az alábbiak szerint egyszerűsíthetjük:

r2':(Q=Igen)+

r3:(P=Igen)(R=Nem)+

Az r 3 szabályt megtartjuk a pozitív osztály megmaradó példányainak lefedéséhez. Bár az egyszerűsítés után nyert szabályok már nem egymást kölcsönösen kizáróak, azonban kevésbé bonyolultak és egyszerűbben értelmezhetőek.

Az alábbiakban egy olyan módszert mutatunk be, amelyet a C4.5rules algoritmus használ egy szabályhalmaz döntési fából való generálására. Az 5.6. ábrán láthatók az 5.2. táblázatban adott adatokhoz a döntési fa és a kapott osztályozási szabályok.

5.6. ábra - A gerincesek osztályozási feladatához készített döntési fából kinyert szabályok

A gerincesek osztályozási feladatához készített döntési fából kinyert szabályok

Szabálygenerálás

A döntési fa minden a gyökérből egy levélcsúcsba vezető útjához egy osztályozási szabályt nyerünk ki. Egy adott r:Ay osztályozási szabály esetén tekintsük az r':A'y egyszerűsített szabályokat, ahol A' -t egy konjunkt eltávolításával kapjuk A -ból. A legkisebb pesszimista hibaarányú egyszerűsített szabályt tartjuk meg, feltéve, hogy a hibaaránya kisebb, mint az eredeti szabályé. A szabálynyesési lépést addig ismételjük, amíg a szabály pesszimista hiabaaránya még javítható. Mivel a nyesés után a szabályok egy része azonossá válhat, a duplikált szabályokat el kell dobni.

Szabályrendezés

A szabályhalmaz generálása után a C4.5rules az osztályalapú rendezési sémát használja a kinyert szabályok rendezéséhez. Az ugyanazt az osztályt előrejelző szabályokat egy részhalmazba csoportosítja. Kiszámolja minden egyes részhalmaz teljes leíró hosszát, majd az osztályokat a teljes leíró hosszuk szerint növekvő sorrendbe rendezi. A legkisebb teljes leíró hosszú osztály kapja a legnagyobb prioritást, mivel várhatóan ez tartalmazza a legjobb szabályokat. Egy osztály teljes leíró hosszát L kivétel +g× L modell adja meg, ahol L kivétel a rosszul osztályozott esetek kódolásához szükséges bitek száma, L modell a modell kódolásához szükséges bitek száma, g pedig egy olyan hangoló paraméter, amelynek alapértelmezett értéke 0,5 . A hangoló paraméter a modellben jelenlevő redundáns attribútumok számától függ. A hangoló paraméter értéke kicsi akkor, ha a modell sok redundáns attribútumot tartalmaz.

Szabályalapú osztályozók jellemzése

A szabályalapú osztályozók az alábbi jellemzőkkel rendelkeznek:

  • A szabályhalmazok és a döntési fák kifejezőereje közel azonos, mivel a döntési fák ábrázolhatók egymást kölcsönösen kizáró és kimerítő szabályokkal. A szabályalapú és döntési fa osztályozók egyenesekkel jellemezhető attribútumtér-részeket alkotnak és minden egyes részhez egy osztályt rendelnek hozzá. Ha azonban a szabályalapú osztályozó lehetővé teszi több szabály kiváltását egy rekordhoz, akkor bonyolultabb döntési határ alkotható.

  • A szabályalapú osztályozókat általában olyan leíró modellek létrehozásához használják, amelyek értelmezése egyszerűbb, és amelyek a döntési fa osztályozókkal összemérhető teljesítményt nyújtanak.

  • A sok szabályalapú osztályozóba (például a RIPPER-be) beépített osztályalapú rendezési eljárás kiválóan alkalmas kiegyensúlyozatlan osztályeloszlású adatállományok kezelésére.