Irodalmi megjegyzések

A korai osztályozási rendszereket objektumok nagy gyűjteményeinek a megszervezésére fejlesztették ki. Például a Dewey-féle tizedes osztályozás (Dewey Decimal) és a Kongresszusi Könyvtár (Library of Congress) osztályozási rendszereket arra a célra tervezték, hogy nagy számú könyvtári könyvet katalogizáljanak és indexeljenek. A kategóriákat általában kézi úton, szakterületi szakértők segítségével azonosítják.

Az automatizált osztályozás már régóta intenzív kutatások tárgya. A klasszikus statisztikában az osztályozás vizsgálatát diszkriminancia-analízisnek (discriminant analysis) nevezik, ahol a cél az, hogy előrejelezzük egy objektum csoporttagságát prediktív változók egy halmaza alapján. A jól ismert klasszikus módszer a Fisher-féle lineáris diszkriminancia analízis [4745], amelynek célja az adatok azon lineáris vetületének megtalálása, amelynél a legnagyobb a különbség a különböző osztályokba tartozó objektumok között.

Sok alakfelismerési probléma szintén megköveteli eltérő osztályokból való objektumok megkülönböztetését. Ilyen például a beszédfelismerés, kézzel írt karakterek azonosítása és képek osztályozása. Azok az olvasók, akik az osztályozási módszerek alakfelismerésben való alkalmazása iránt érdeklődnek Jain és társai [4783], valamint Kulkarni és társai [4802] áttekintő cikkeihez, vagy a Bishop [4693], Duda és társai [4732] és Fukunaga [4751] klasszikus alakfelismerési könyveihez fordulhatnak. Az osztályozás fontos kutatási téma a neurális hálók, a statisztikai tanulás és a gépi tanulás területeken is. A különböző osztályozási módszerek részletes tárgyalását adják a következő könyvek: Cherkassky és Mulier [4713], Hastie és társai [4769], Michie és társai [4827], valamint Mitchell [4831].

A döntési fa következtetési algoritmusok egy áttekintése található a következő tanulmányokban: Buntine [4704], Moret [4832], Murthy [4837], valamint Safavian és társai [4867]. Néhány jól ismert döntési fa algoritmusra példa többek között a CART [4701], az ID3 [4859], a C4.5 [4858] és a CHAID [4795]. Az ID3 és a C4.5 egyaránt az entrópia mértéket alkalmazza vágó függvényként. A C4.5 döntési fa algoritmus egy mélyreható tárgyalását adja Quinlan [4858]. Emellett elmagyarázza döntési fák építésének és metszésének a módszertanát. Quinlan [4858] azt is leírja, hogy hogyan lehet úgy módosítani az algoritmust, hogy az hiányzó értékekkel bíró adatállományokat is kezelni tudjon. A CART algoritmust, amely a Gini-indexet használja vágó függvényként, Breiman és társai [4701] fejlesztették ki. A CHAID [4795] a statisztikai χ 2 próbát használja a legjobb vágás meghatározására a faépítési folyamat során.

Az e fejezetben bemutatott döntési fa algoritmus azt feltételezi, hogy a vágási feltételt egy időben egy attribútum határozza meg. Egy ferde döntési fa több attribútumot is használhat az attribútum tesztfeltétel kialakítására a belső csúcsokban [4771, 4908]. Breiman és társai [4701] CART implementációjukban lehetőséget biztosítanak az attribútumok lineáris kombinációinak használatára. Más megközelítéseket javasoltak ferde döntési fák építésére Heath és társai [4771], Murthy és társai [4838], Cantú-Paz és Kamath [4707], valamint Utgoff és Brodley [4908]. Bár a ferde döntési fák segítségével javítható egy döntési fa reprezentáció kifejezőképessége, a megfelelő tesztfeltétel megtanulása minden egyes csúcsban számításigényes kihívást jelent. Egy másik módja, hogy ferde döntési fák használata nélkül javítsuk egy döntési fa kifejezőképességét, a konstruktív indukció [4825] néven ismert módszer alkalmazása. Ez a módszer azzal könnyíti meg bonyolult vágó függvények tanulásának a feladatát, hogy összetett jellemzőket hoz létre az eredeti attribútumokból.

A felülről lefelé haladó megközelítés mellett egyéb döntési fa építő stratégiák többek között az alulról felfelé haladó megközelítés (lásd Landeweerd és társai [4808], valamint Pattipati és Alexandridis [4849]), továbbá Kim és Landgrebe [4796] kétirányú megközelítése. Schuermann és Doster [4875], illetve Wang és Suen [4914] javasolta a puha vágó kritériumot (soft splitting criterion) az adattöredezettségi probléma kezelésére. Ebben a megközelítésben minden rekord különböző valószínűségekkel van hozzárendelve a döntési fa különböző ágaihoz.

A modell túlillesztés egy olyan fontos kérdés, amellyel foglalkozni kell annak biztosítása érdekében, hogy a döntési fa osztályozó egyformán jól teljesítsen korábban ismeretlen rekordokon. A modell túlillesztési problémát már számos szerző vizsgálta, többek között Breiman és társai [4701], Schaffer [4872], Mingers [4829], valamint Jensen és Cohen [4786]. Míg a zaj jelenlétét gyakran tekintik a túlillesztés egyik fő okának [4829, 4840], Jensen és Cohen [4786] úgy érvelt, hogy a túlillesztés a helytelen hipotézis vizsgálatok alkalmazásának az eredménye a többszörös összehasonlítási eljárás során.

Schapire [4873] úgy definiálta az általánosítási hibát, mint ``egy új eset téves osztályozásának a valószínűsége’’, a tesztelési hibát pedig mint egy ``újonnan mintavételezett teszthalmaz tévedési aránya’’. Az általánosítási hiba ezért úgy tekinthető, mint egy osztályozó várható tesztelési hibája. Az általánosítási hibára néha úgy hivatkoznak, mint egy modell igazi hibája [4831], azaz ugyanabból a populáció eloszlásból véletlenszerűen húzott adatpontok várható hibája, mint amiből a tanulóhalmazt vettük. Ezek a definíciók valójában ekvivalensek, ha a tanuló- és a teszthalmazok egyaránt ugyanabból a populáció eloszlásból származnak, ami gyakran előfordul számos adatbányászati és gépi tanulási alkalmazásnál.

Az Occam borotvája elvet általában William Occam filozófusnak tulajdonítják. Domingos [4727] óva int Occam borotvájának olyan téves értelmezésétől, miszerint általánosítási hibák helyett hasonló tanítási hibájú modelleket hasonlítsunk össze. A túlillesztés elkerülését szolgáló döntési fa metszési módszerek egy áttekintése Breslow és Aha [4689], illetve Esposito és társai [4738]. Néhány jellegzetes metszési módszer közé tartozik a csökkentett hibanyesés [4860], a pesszimista hibanyesés [4841], a kritikus értékű metszés [4830] a költség-bonyolultság metszés [4701] és a hiba-alapú metszés [4858]. Quinlan és Rivest javasolta a minimális leíró hossz elvét döntési fák metszésére [4861]-ban.

Kohavi [4798] kiterjedt empirikus tanulmányában az olyan különböző becslési módszerekkel kapott teljesítmény mérőszámokat hasonlította össze, mint a véletlen alulmintavételezés, a bootstrap és a k -szoros keresztellenőrzés. Eredményei azt sugallják, hogy a legjobb becslési módszer a tízszeres rétegzett keresztellenőrzésen alapszik. Efron és Tibshirani [4736] a keresztellenőrzés és a 632+ szabály néven ismert bootstrap módszer elméleti és empirikus összehasonlítását adta.

A jelenlegi módszerek, mint a C4.5, megkövetelik, hogy a teljes tanuló adatállomány elférjen a memóriában. Jelentős erőfeszítések történtek döntési fa következtetési algoritmusok párhuzamos és skálázható változatának kifejlesztése irányában. Néhány javasolt algoritmus többek között a SLIQ Mehta és társai [4823] által, a SPRINT Shafer és társai [4882] által, a CMP Wang és Zaniolo [4911] révén, a CLOUDS Alsabti és társai [4659] révén, a RainForest Gehrke és társai [4753] által, végül a ScalParC Joshi és társai [4791] révén. Egy általános áttekintés található [4803]-ben az adatbányászat számára kifejlesztett párhuzamos algoritmusokról.