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

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:

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ű.

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.

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.

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élig→Hü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é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.

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.

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 .

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.

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:

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ú k−1 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)

M−becslé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':A∧B→+ 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:

FOIL−fé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.

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: (p−n)/(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 ABCD→y 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.

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:

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:

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.

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:A→y 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.

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