HTML dokumentumok hierarchikus osztályozása a WebClassII-vel
HTML dokumentumok hierarchikus osztályozása a WebClassII-vel Készítette: Novák György http://w3.netelek.hu/novakg 2003. 10. 01.
Tartalom A jellemzők kiválasztásának folyamata...............................................................................................1 Az osztályozás folyamata.....................................................................................................................2 Teszt eredmények.................................................................................................................................3 Konklúzió.............................................................................................................................................5 Forrás....................................................................................................................................................5
A jellemzők kiválasztásának folyamata A WebClassII-ben minden dokumentumot a jellemzőknek egy numerikus vektora reprezentál, amiben egy adott jellemző egy adott szó előfordulásainak számát jelenti a dokumentumban. A jellemzők halmaza minden kategória esetén egyedi, és automatikusan generálódik pozitív és negatív tanulási példák alapján. Minden tanuló dokumentumot tokenekre bontunk és kiszűrjük belőlük a HTML tag-eket, különleges karaktereket, számokat és a három karakternél rövidebb tokeneket. Még a jellemzők kiválasztása előtt elvégzünk néhány alapvető előfeldolgozási eljárást: 1. Eltávolítjuk a túl gyakran előforduló szavakat, mint amilyenek például a kötőszavak. Ezeket a szavakat a Glimpse nevű eszközből vesszük. 2. Megállapítjuk az azonos jelentésű szótöveket. (Porter algoritmus). Sok olyan módszert fejlesztettek ki a nyelvtannal foglalkozó emberek, amelyekkel információt nyerhetünk ki a szövegekből, azaz indexelni tudjuk azokat. A mi esetünkben azonban ezek a technikák nem igazán használhatóak, mivel mi nem az egyes dokumentumok tulajdonságaira vagyunk kíváncsiak, hanem azokra a jellemzőkre, amelyek a dokumentumok egy csoportját megkülönböztetik egy másik csoporttól. Általában az osztályozáshoz használt szavak halmaza sokkal kisebb, mint az indexeléshez használtaké. Lássuk a jellemzőkiválasztási eljárást (TF-IDF kiterjesztése)! Legyen c egy kategória és c' neki egy gyermeke a kategóriák hierarchiájában! Legyen d egy tanuló dokumentum c'-ből, w egy jellemző, mely d-ből származik (tokenizálás, szűrés és szótőképzés után), és TFd(w) w relatív gyakorisága d-ben! Ekkor ki tudjuk számolni a következőket: •
a TFd(w) maximális értékét a d dokumentumok között a c' kategóriában: TF c ' w= max
d ∈Tanulóc '
TF d w 1
HTML dokumentumok hierarchikus osztályozása a WebClassII-vel •
az oldalfrekvenciát, azaz a c' kategória dokumentumainak azon százalékát, amelyben előfordul a w jellemző: PF c ' w =
occ c ' w , Tanulóc '
ahol Tanuló(c') lehet egy rendes tanuló halmaz is, de lehet hierarchiára vonatkozó tanuló halmaz is a c' kategória dokumentumaira. Megjegyezzük, hogy csak olyan dokumentumokat használunk mindkét függvény kiszámításához, melyeket pozitív mintaként veszünk figyelembe c'-re. A c' weblapjaiból kinyert jellemzők halmazainak uniója egy empírikus kategória szótárat definiál, melyet a kategória által meghatározott topic-okban használnak a dokumentumok. A szótár elemeit jó lenne valamilyen szempont szerint sorbarendezni. A HTML oldalak készítői gyakran rejtenek el egy-két kulcsszót az oldalakon, hogy ezáltal azok előrébb szerepeljenek a keresések eredményeként kapott listákon. Amennyiben az egyes katergóriák szótárait a Tfc'(w)PFc'(w)2 szerint rendezzük, úgy ellenőrzés alatt tudjuk tartani ezt a jelenséget. Sőt, a c' dokumentumaiban használt gyakori szavak a megfelelő kategória szótárának első bejegyzéseiként fognak megjelenni. Ezeknek a szavaknak egy része a kategóriára jellemző, míg mások egyszerűen csak gyakori angol szavak. Hogy ezeket a számunkra érdektelen szavakat lejjebb mozgassuk a listában, nem kell mást tennünk, mint a Tfc'(w)PFc'(w)2 szorzatot megszoroznunk egy ICFc(w)=1/CFc(w) faktorral, ahol CFc(w) (kategória gyakoriság) c azon alkategóriáinak száma, amelyekben w előfordul. Ezek után azok a lényeges jellemzők, amelyek megkülönböztetik c' dokumentumait a testvér kategóriájába tartozó dokumentumoktól, azok c' kategóriaszótárának első bejegyzésein találhatók. Ha elkészítjük egy c kategória minden c' alkategórájához tartozó szótárat, akkor ezen szótárak unióját tekinthetjük a c szótárának. Ez a szótár olyan jellemzőket fog tartalmazni, amelyek az egyes alkategóriákon belül gyakran előfordulnak a dokumentumokban, de más alkategóriák dokumentumaiban viszont ritkán jelennek meg (a kategóriák jellemzőinek ortogonalitása). Ennek következtében arra nagyon jól használhatóak ezek a jellemzők, hogy egy dokumentumot besoroljunk a c kategóriába, ha az c valamely alkategórájába tartozónak bizonyul (azaz, ha a jellemzők alapján a dokumentum beletartozik c valamely alkategóriájába, akkor az c-be is beletartozik). Figyelemre méltó, hogy ez a megközelítés a felsőbb kategóriákhoz közel általános jellemzők halmazát adja (pl.: “math” és “mathemat”), míg a lejjebb elhelyezkedő kategóriákhoz specifikusabb jellmezők halmazát adja (pl.: “topolog”). Ha meghatároztuk a jellemzők halmazát, akkor a tanuló dokumentumok reprezentálhatjuk jellemző vektorokként, amelyben minden jellemző érték egy szó gyakorisága.
Az osztályozás folyamata Egy új dokumentum besorolása a hierarchia bejárásával történik. A rendszer a gyökértől indul, és az olyan csúcsokon megy tovább, amelyek esetén az osztályozó magasabb értéket ad vissza egy meghatározott küszöbnél. A folyamat végén az összes bejárt csúcsot, azaz kategóriát (akár levél, akár nem) figyelembe vesszük a végső döntésnél. A győztes az a bejárt kategória lesz, amelyre az osztályozó a legmagasabb ertéket adta. Ha a dokumentumot a gyökérbe sikerült besorolni, akkor az a dokumentum el lett utasítva. Érdemes megemlíteni, hogy egy osztályozó alkalmazását mindíg megelőzi a dokumentumok reprezentálásának megváltoztatása a kiválasztott jellmezőknek megfelelően. Mivel a kiválasztott jellemzőktől elvárjuk, hogy egyre specifikusabbak legyenek az alsóbb szinten lévő kategóriákban, ezért a a dokumentumok egyre alacsonyabb absztrakciós szinten lesznek reprezentálva az osztályozás folyamán. A reprezentációnak ez az automatikus változtatása igen 2
HTML dokumentumok hierarchikus osztályozása a WebClassII-vel kívánatos a hierarchikus osztályozásban.
Teszt eredmények Ebben a fejezetben a WebClassII teljesítményét tanulmányozzuk Web-oldalak egy halmazán. A teszteléshez használt adatforrás a Yahoo! ontológia. 1026 olyan dokumentumot vizsgáltunk, amelyek referenciái a http://dir.yahoo.con/Science Web könyvtár legfelső két szintjén találhatók. Az első szinten 7, a másodikon 28 kategória van. Az a dokumentum, amely a gyökérkategóriába lett besorolva, az “visszautasított”-nak tekintendő, mivel a tartalma nem tartozik a 35 alkategória egyikébe sem. Az adathalmazt egy “5 rekeszes kereszt-megerősítés”-nek nevezett módszer által elemeztük. Ez azt jelenti, hogy az adathalmazt először 5 közel azonos méretű “rekeszre” osztottuk, majd a WebClassII minden rekesz esetén egy tanulási folyamaton ment át a fennmaradó rekeszek dokumentumain, majd az eredményeket tesztelte a rekeszen. A rendszer teljesítményét a rekeszekre vonatkozó mérési eredmények átlagával jellemezzük. Több, különböző méretű jellemzőhalmazt készítettünk minden belső kategóriához, hogy ennek a hatását is meg tudjuk vizsgálni. Az egyes kategóriák esetén a jellemzőhalmazok mérete leginkább 5 és 50 közé esik. A jellemzőket hierarchikus tanulóhalmazok segítéségvel válogattuk ki. Ez elviekben garantálja, hogy olyan kategóriákhoz is tudjunk megfelelő jellemzőhalmazt rendelni, amelyekhez nincsenek megfelelő tanuló dokumentumok. Az összegyűjtött statisztikák olyan centroi-alapú vagy naív Bayes osztályozókra vonatkoznak, amelyek a következő három technika valamelyike szerint lettek tanítva: 1. egyszerű, azaz minden kategóriát összevonunk és figyelmen kívül hagyjuk a közöttük lévő kapcsolatokat 2. hierarchikus, megfelelő tanulóhalmazokkal, azaz mikor csak a c kategória elemeit soroljuk Training(c)-be 3. hierarchikus, hierarchikus tanulóhalmazokkal, azaz mikor mind a c kategória, mind annak alkategóriáiba tartozó dokumentumokat besorolunk a Training(c)-be. Az összehasonlítás alapját képező eredményeket az egyszerű technikával kaptuk. Mind az egyszerű, mind a hierarchikus osztályozó technikák esetén súlyozott átlagát veszünk a pontosságnak is és a visszavonásnak is. Egy c kategória pontossága azt mondja meg, hogy a c kategórába sorolt dokumetumoknak hány százaléka tartozik valójában oda, míg a visszavonás azt adja meg, hogy az összes olyan dokumentumnak, amelynek c-be kellene kerülnie , hány százaléka került oda ténylegesen. A teljes {c1, ..., cm} kategória tér esetén ezeket a súlyozott átlagokat a következőképpen számoljuk: m
∑ pontosság ci w i
pontosság= i=1
m
m
∑ visszavonásci w i
visszavonás= i=1
,
m
ahol wi a ci kategória dokumentumainak százaléka.
3
HTML dokumentumok hierarchikus osztályozása a WebClassII-vel A mérések eserményei azt mutatják, hogy az egyszerű technika túlteljesíti a hierarchikus technikákat a pontosság tekintetében, míg a hierarchinkus tanulási halmazzal dolgozó naív Bayesnek van a legjobb visszavonási értéke a növekvő jellmezőhalmaz méret mellett. Emellett a centroid alapú osztályozók majdnem mindíg kisebb pontosságot és visszavonási értéket mutatnak, mint a megfelelő naív Bayes osztályozók, az alkalmazott technikától (egyszerű, vagy hierarchikus) és a jellemzőhalmaz méretétől függetlenül. Egy másik érdekesség, hogy a hierarchikus tanulóhalmazok alklamazása mindkét teljesítménymutatót megnöveli, függetlenül a metódustól és a jellemzőhalmaz méretétől. Minden tanuló és teszt dokumentum a hierarchia ugyanazon kategóriájába tartozik, így elvárható lenne, hogy az elutasított dokumentumok száma alacsony legyen. Ennek ellenére csak a hierarchikus tanulóhalmazos naív Bayes metódus esetén maradt ez az érték 30% alatt. Ez azt jelenti, hogy a gyökér osztályozójához automatikusan meghatározott küszöb miatt a legtöbb dokumentum nem kerülhet a hierarchia alsóbb szintjeire az osztályozás során. Alacsonyabb küszöbérték mellett az elutasítási arány csökkenhet, de a rendszerünk hajlamosabbá válhat hibázni. Az olyan metódusok, melyek a dokumentumokat a megfelelő kategória helyett - tévesen egy ahhoz hasonló kategóriába sorolják be, azokat általában jobbnak tartjuk azoknál, amelyek a megfelelőtől teljesen eltérő kategóriába sorolják a szavakat. Éppen ezért három új mértéket definiálunk egy c kategóriához: 1. téves besorolás hibája: c dokumentumainak azon százaléka, amelyek olyan c' kategóriába lettek besorolva, amely teljesen független c-től 2. álatalánosítási hiba: c dokumentumainak azon százaléka, amelyek c valamely őskategóriájába lettek besorolva 3. specializációs hiba: c dokumentumainak azon százaléka, amelyek c valamely alkategóriájába lettek besorolva. Minden egyes kategória esetén a visszavonás, a téves besorolási hiba, a általánosítási hiba és a specializációs hiba összege egyenlő eggyel. A Bayes metódusok, amelyek az elutasított dokumetumok számánál a legkisebb értéket mutatták, a leghajlamosabbak a téves besorolási hibákra. Mindamellett a hierarchikus tanulóhalmazok esetén a téves besorolási hiba arányának növekedése a centroid alapú megközelítés tekintetében kb. 7%, míg az elutasítások arányának csökkenése 23%-on felüli az 50 jellemző/kategória esetén. Az egyszerű megközelítések adják a legkevesebb generalizációs hibát, mivel ők egyszerűen semmibe veszik a kategóriák közötti kapcsolatokat. A centorid alapú metódus hierarchikus tanulóhalmazzal hajlamos a túláltalánosításra. Ez a meghatározott “óvatos” küszöbök miatt van így. A másik oldalról nézve, minden metódusnak alacsony a specializációs hiba aránya. A teszt eredmények egy finomabb elemzését teszi lehetővé, ha a hierarchiában szintrőlszintre haladva vizsgáljuk a mérési eredményeket. Az egyszerű technika általában véve a legjobb mind a legfelső, mind a második szinten. A legfelső szinten minden hierarchikus technika esetén jobb a visszavonás, míg a második szinten csak a hierarchikus tanulóhalmazos naív Bayes-nek van jobb visszavonási értéke, mint az egyszerű technikáknak. Érdekes, hogy az első szinten a rendes tanulóhalmazokat használó metódusok jobban teljesítenek (mind a pontosságot, mind a visszavonást tekintve), mint a hierarchikus tanulóhalmazokat használó társaik, ugyanakkor a második szinten megfordul ez a helyzet. Más szavakkal, az alacsonyabb szinteken lévő kategóriák nagyobb hasznot húznak a hierarchikus tanulóhalmazokból. Végül meg kell említenünk, hogy a centroid alapú metódus csak az egyszerű megközelítésben számolásigényesebb a naív Bayes-nél, a hierarchikus esetben viszont közel 4
HTML dokumentumok hierarchikus osztályozása a WebClassII-vel azonos a tanulási idejük. Mindenesetre a hierarchikus technikák tanulási ideje kisebb az egyszerű technikákénál a metódustól függetlenül.
Konklúzió Ebben az írásban a HTML dokumentumok kategóriák hierarchiájába történő automatikus osztályozását vizsgáltuk, amihez a környezetet egy olyan kliens-szerver alkalmazás jelentette, mely a Web dokumentumok közös érdeklődésű felhasználók csoportjai közötti elosztását támogatja. Megvizsgáltuk, hogy mennyire hasznos a kategóriák hierarchiája a jellemzők kiválasztásánál, az osztályozók felépítésénél, vagy az osztályozás folyamatában. Ami a jellemzők kiválasztását illeti, bemutattunk egy újfajta technikát a lényeges jellemzők kiválogatására a tanuló dokumentumokból. A tanulási részhez két osztályozót tekintettünk, és ajánlottunk egy küszöbölő algoritmust egy elutasító osztály esetére. Az osztályozáshoz egy ?grafikus? kereső technikát mutattunk, ami minden lehetséges utat felderít. A tesztelést olyan dokumentumok halmazán végeztük, amelyek a Yahoo! ontológiában vannak indexelve. Három technikát hasonlítottunk össze: i) egyszerű osztályozás, ii) hierarchikus osztályozás rendes tanulóhalmazokkal és iii) hierarchikus osztályozás hierarchikus tanulóhalmazokkal. Az eredmények a Yahoo! dokumentumain nagy vonalakban a következők: 1. Növekvő jellemzőhalmaz-méret esetén a legjobb teljesítményt a naív Bayes osztályozók mutattak, mind egyszerű, mind hierarchikus tanulóhalmazokkal. 2. A Bayes-féle metódusok utasították el a dokumetumok legkisebb százalékát, de ugyanakkor ők követték el a legtöbb osztályozási hibát. Mindenesetre a visszautasítások arányának jelentős csökenése ellensúlyozza a hibás osztályozások arányának kismértékű növekedését. 3. Minél lejjebb járunk a kategóriák hierarchiájában, annál előnyösebbek a hierarchikus tanulóhalmazok. A szintről-szintre végrehajtott elemzés segít megérteni a hierarchikus és az egyszerű megközelítések eltérő viselkedését.
Forrás Michelangelo Ceci and Denato Malerba: Hierarchical Classification of HTML Documents with WebClassII. Springer-Verlag Berlin Heidelberg 2003
5
