1 Zapadoceska univerzita v Plzni Fakulta aplikovanych ved Katedra informatiky a vypocetn techniky Diplomova prace Automaticka klasikace dokumentu s po...
Z apado cesk a univerzita v Plzni Fakulta aplikovan ych v ed Katedra informatiky a v ypo cetn techniky
Diplomova prace
Automaticka klasi kace dokument u s podobnym obsahem
Plze n, 2012
Michal Hrala
Podˇ ekov´ an´ı Dˇekuji Ing. Pavlu Kr´alovi, Ph.D. vedouc´ımu t´eto diplomov´e pr´ace za jeho ochotu, ˇcas a cenn´e pˇripom´ınky k obsahu i zpracov´an´ı. D´ale m´e d´ıky patˇr´ı vˇsem, kteˇr´ı byli ochotni poskytnou v´ ypoˇcetn´ı prostˇredky, bez kter´ ych by tato pr´ace tˇeˇzko mohla vzniknout. V neposledn´ı ˇradˇe bych tak´e r´ad podˇekoval rodiˇc˚ um za jejich nekoneˇcnou podporu pˇri studiu a kamar´ad˚ um, kteˇr´ı mi byli oporou a motivovali mˇe.
Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem diplomovou pr´aci vypracoval samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u.
V Plzni dne 11. kvˇetna 2012
........................... Michal Hrala
Abstract The main goal of this work is to study methods for a multi-label document classification and to propose a user friendly software solution for Czech News Agency ˇ (CTK). Multi-label classification is a task, where document is classified in to more than one class. Based on the literature, we have chosen three classifiers that are successfully used in the document classification field: Naive Bayes (NB), Support Vectors Machine (SVM) and Maximum Entropy classifier. We also study the possibility to use Part of Speech (POS) tagging for document word filtration and lemmatization to improve classification accuracy. For the feature selection, five methods are compared: Document Frequency (DF), Information Gain (IG), Mutual Information (MI), Chi-square and GSS methods. ˇ All methods are evaluated on the Czech corpus of CTK newspapers articles. An optimal classifier setting is proposed based on these results. The proposed software solution uses the MinorThird classification tool package as an implementation of the classification methods. We used the Mate tool for lemmatization and POS tagging. Keywords: feature selection, lemmatization, Maximum Entropy, Multi-label document classification, Naive Bayes, POS tagging, Support Vector Machine, text classification
Kapitola 1 ´ Uvod V dneˇsn´ı digit´aln´ı dobˇe jsme kaˇzd´ y den zahrnov´any stovkami nov´ ych dokument˚ u. M˚ uˇze se jednat napˇr´ıklad o digitalizovan´e archivn´ı materi´aly, novinov´e ˇcl´anky, pˇr´ıspˇevky na diskusn´ıch f´orech, elektronickou poˇstu, obsah webov´ ych str´anek ˇci elektronick´e knihy. Roste tak potˇreba tyto dokumenty zpracov´avat a oznaˇcovat metadaty 1 , napˇr´ıklad pro usnadnˇen´ı jejich vyhled´av´an´ı. Jedn´ım z proces˚ u, kter´ y lze ˇreˇsit programovˇe je tˇr´ıdˇen´ı dokument˚ u do kategori´ı, at’ uˇz podle jejich v´ yznamu, autora, ˇza´nru, ˇci jin´ ych krit´eri´ı. Tˇemito probl´emy se zab´ yv´a nˇekolik oblast´ı umˇel´e inteligence. Jedn´a se napˇr. o zpracov´an´ı pˇrirozen´eho jazyka (NLP – Natural Language Procesing) vyuˇz´ıvaj´ıc´ı obvykle metod strojov´eho uˇcen´ı (Machine Learning) a o metody dolov´an´ı dat (Data Mining). Vˇsechny tyto oblasti pracuj´ı v souˇcinnosti za jedin´ ym u ´ˇcelem a t´ım je nalezen´ı urˇcit´ ych vzor˚ u ˇci podobnost´ı v datech, na z´akladˇe kter´ ych je pot´e text tˇr´ıdˇen do kategori´ı. Tato pr´ace se zab´ yv´a klasifikac´ı novinov´ ych ˇcl´ank˚ u podle obsahu do jedn´e hlavn´ı kategorie (burzy, politika, ...) a nˇekolika vedlejˇs´ıch kategori´ı, kter´e bl´ıˇze ˇcl´anek upˇresˇ nuj´ı. Mezi vedlejˇs´ı kategorie mohou patˇrit napˇr´ıklad: burzy akciov´e, burzy komoditn´ı, dom´ac´ı politika, zahraniˇcn´ı politika, atd. Pr´ace je vytvoˇrena na z´akladˇe ˇ e tiskov´e kancel´aˇre (d´ale jen CTK) ˇ potˇreb Cesk´ a pˇredpokl´ad´a se jej´ı dalˇs´ı rozˇsiˇrov´an´ı na z´akladˇe poˇzadavk˚ u z testovac´ıho provozu. ˇ aˇr by po pˇreˇcten´ı t´eto pr´ace mˇel porozumˇet hlavn´ımu probl´emu klasifikace Cten´ dokument˚ u, metod´am v´ ybˇeru pˇr´ıznak˚ u pro klasifikaci a b´ yt schopen vyuˇz´ıt tyto informace pro nasazen´ı v jin´e oblasti (napˇr. detekce spamu v emailov´e poˇstˇe, detekce sentimentu, ˇci blokov´an´ı pornografie na webu). D´ale by mˇel b´ yt schopen konfigurovat vytvoˇrenou aplikaci, tr´enovat klasifik´ator a prov´adˇet tak vlastn´ı experimenty. 1
Strukturovan´e informace o datech.
1.1 Struˇcn´ y pˇrehled kapitol
1.1
2
Struˇ cn´ y pˇ rehled kapitol
Vu ´vodn´ı kapitole je ˇcten´aˇr sezn´amen s d˚ uvody, proˇc byla tato pr´ace ˇreˇsena a d´ale dostane informace o jej´ım vyuˇzit´ı. N´asleduj´ıc´ı kapitola objasˇ nuje probl´em klasifikace dokument˚ u a seznamuje ˇcten´aˇre s metodami v´ ybˇeru pˇr´ıznak˚ u a klasifik´ator˚ u pouˇzit´ ych v t´eto pr´aci. Tˇret´ı kapitola popisuje klasifikaˇcn´ı n´astroje a srovn´av´a je poˇ dle implementovan´ ych klasifik´ator˚ u. D´ale se sezn´am´ıme s datab´azemi CTK, struktuˇre zpracov´avan´ ych soubor˚ u a metrik pro vyhodnocen´ı u ´spˇeˇsnosti klasifikace. Dalˇs´ı kapiˇ aˇr zde tak´e tola popisuje ˇreˇsen´ı u ´lohy a grafick´e prostˇred´ı vytvoˇren´e aplikace. Cten´ dostane informace o struktuˇre vstupn´ıch a v´ ystupn´ıch soubor˚ u pro jednotliv´e f´aze klasifikace. Pˇredposledn´ı kapitola zobrazuje v´ ysledky experiment˚ u v pˇrehledn´ ych tabulk´ach a grafech, srovn´av´a obdrˇzen´e v´ ysledky s teori´ı a navrhuje nejlepˇs´ı ˇreˇsen´ı pro praktick´e vyuˇzit´ı. Kapitola z´avˇer shrnuje dosaˇzen´e v´ ysledky a navrhuje pˇr´ıpadn´a dalˇs´ı rozˇs´ıˇren´ı. V pˇr´ıloh´ach je obsaˇzena struktura pˇriloˇzen´eho DVD, UML diagram vytvoˇren´e apˇ likace, konfigurace n´astroje s pˇr´ıklady spuˇstˇen´ı, struktura textov´ ych datab´az´ı CTK a pˇrehled kategori´ı, do kter´ ych budeme ˇcl´anky zaˇrazovat.
3
Kapitola 2 Klasifikaˇ cn´ı u ´ loha ˇ aˇr se dozv´ı, jak´e Tato kapitola si klade za c´ıl objasnit probl´emy klasifikace text˚ u. Cten´ metody pˇredzpracov´an´ı dat se pouˇz´ıvaj´ı pro tuto u ´lohu a jak optimalizovat pˇr´ıznakov´ y vektor. D´ale je struˇcnˇe vysvˇetlen princip klasifik´ator˚ u, kter´e se bˇeˇznˇe pouˇz´ıvaj´ı k ˇreˇsen´ı t´eto u ´lohy.
2.1
Popis probl´ emu
Hlavn´ım probl´emem pˇri klasifikaci text˚ u 1 je v´ ybˇer vhodn´ ych pˇr´ıznak˚ u tak, aby dokument co nejl´epe vystihovaly. Samozˇrejmˇe m˚ uˇzeme jako pˇr´ıznakov´ y vektor pouˇz´ıt vˇsechna slova, kter´a dokument obsahuje. Obecnˇe ale m˚ uˇze m´ıt klasifikovan´ y dokument r˚ uznou velikost a pˇr´ıznakov´ y vektor by tak byl r˚ uznˇe velk´ y. Rozs´ahl´e dokumenty by bylo ˇcasovˇe n´aroˇcn´e zpracovat. Tr´enov´an´ı klasifik´atoru by se tak mohlo prodlouˇzit ˇra´dovˇe o hodiny s nejist´ ym v´ ysledkem. Z tohoto d˚ uvodu se prov´ad´ı pˇredzpracov´an´ı dokumentu, a to nejen kv˚ uli redukci pˇr´ıznakov´eho vektoru, ale tak´e kv˚ uli lepˇs´ımu popisu dokumentu, kdy jsou filtrov´any nepodstatn´e informace (slova).
2.1.1
Typy klasifikaˇ cn´ıch probl´ em˚ u
Samotnou klasifikaci dokument˚ u m˚ uˇzeme rozdˇelit na tˇri podmnoˇziny [15] podle toho, do kolika kategori´ı dokument zaˇrazujeme. Bin´ arn´ı klasifikace Pokud dokument patˇr´ı pˇresnˇe do dvou kategori´ı, prov´ad´ıme bin´arn´ı klasifikaci. M˚ uˇze se napˇr´ıklad jednat o klasifikaci typu je spam/nen´ı spam. Multi-class klasifikace Pokud pˇreddefinovan´ ych kategori´ı, do kter´ ych ˇcl´anek m˚ uˇze patˇrit, je v´ıce a kaˇzd´ y ˇcl´anek patˇr´ı pˇresnˇe do jedn´e z tˇechto kategori´ı, jedn´a se o tzv. Multi-class klasifikaci. 1
T´eˇz kategorizace/klasifikace text˚ u, dokument˚ u, ˇcl´ank˚ u, ...
2.2 Pˇredzpracov´an´ı dokumentu
4
Multi-label klasifikace Ve vˇetˇsinˇe pˇr´ıpad˚ u ale dokument nem´a stanovenu jednu kategorii do kter´e patˇr´ı. Obzvl´aˇst’ u novinov´ ych ˇcl´ank˚ u je pravdˇepodobn´e zaˇrazen´ı do v´ıce pˇredddefinovan´ ych kategori´ı. Tato kategorizace se naz´ yv´a Multi-label klasifikace a je hlavn´ım c´ılem t´eto pr´ace.
2.2
Pˇ redzpracov´ an´ı dokumentu
Pˇredzpracov´an´ı dokumentu m˚ uˇzeme rozdˇelit do nˇekolika krok˚ u, jak je vidˇet na obr´azku 2.1 s diagramem funkce klasifikaˇcn´ıho syst´emu. Naˇcten´ y dokument je tˇreba tokenizovat, tedy rozdˇelit na jednotliv´a slova, termy. V t´eto f´azi je prov´adˇena pomoc´ı regul´arn´ıho v´ yrazu i filtrace pˇr´ıpadn´ ych HTML tag˚ u ˇci vyjadˇrovac´ıch prostˇredk˚ u jin´eho jazyka (XML znaˇcek) vyskytuj´ıc´ıch se v dokumentech. V´ıme-li, ˇze v dokumentech existuj´ı slova, kter´a nemaj´ı na klasifikaci vliv, je moˇzn´e tato slova explicitnˇe odstranit aby neovlivˇ novala klasifikaci. Po tomto kroku m˚ uˇzeme prov´est morfologickou anal´ yzu, v naˇsem pˇr´ıpadˇe se bude jednat o urˇcen´ı slovn´ıch druh˚ u, tzv. POS-tagging (viz kapitola 2.2.1) a lemmatizaci (viz kapitola 2.2.2).
Novinové články
Tokenizace
Filtrace
Lemmatizace
Příznakový vektor
Trénování modelu
POS-tagger
Výběr příznaků
Klasifikátor
Model Testování modelu
Trénovací množina Pravděpodobnosti zařazení do tříd
Testovací množina
Obr´azek 2.1: Diagram funkce klasifikaˇcn´ıho syst´emu Proveden´ım lemmatizace se zbav´ıme stejn´ ych slov v r˚ uzn´e osobˇe, v r˚ uzn´em ˇcase a p´adˇe, jin´ ymi slovy pˇrevedeme slova na z´akladn´ı tvar, coˇz bude vhodn´e pˇri tvorbˇe frekvenˇcn´ıho slovn´ıku. Filtraci slov n´am v´ yraznˇe usnadn´ı POS-tagging. Umoˇzn´ı
2.2 Pˇredzpracov´an´ı dokumentu
5
n´am vyfiltrovat slova, kter´a maj´ı stejn´e pravdˇepodobnost´ı rozdˇelen´ı ve vˇsech dokumentech a ve vˇsech tˇr´ıd´ach, do kter´ ych klasifikujeme. Jedn´a se zejm´ena o interpunkˇcn´ı znaky, spojky a pˇredloˇzky. Proveden´ım POS-taggingu n´am odpad´a programov´a filtrace podle pˇredem urˇcen´eho vektoru (seznamu) slov tzv. STOP listu.
2.2.1
POS-tagging
Part of Speech (POS) tagov´an´ı, je metoda, kter´a kaˇzd´emu tokenu (d´ale jen slovu) pˇriˇrad´ı slovn´ı druh. T´ımto si zjednoduˇs´ıme filtraci slov pro klasifikaci, protoˇze napˇr´ıklad pˇredloˇzky a spojky jsou pro klasifikaci vˇetˇsinou nepodstatn´e. Pˇriˇrazen´ı slovn´ıho druhu bude prov´adˇeno n´astrojem Mate tool [4], kter´ y je distribuov´an pod licenc´ı GNU GPL a je tud´ıˇz moˇzn´e ho vyuˇz´ıt zdarma i pro komereˇcn´ı u ´ˇcely. Tento n´astroj byl pouˇzit jednak z licenˇcn´ıch d˚ uvod˚ u, byl mi doporuˇcen a jednak protoˇze dle literatury dosahoval dobr´ ych v´ ysledk˚ u. Oznaˇckov´an´ı slov je provedeno zkratkami z tabulky 2.1 pˇredstavuj´ıc´ı jednotliv´e slovn´ı druhy. POS tag N A P C V D R J I T Z X
ˇ Anglick´ y v´ yznam Cesk´ y v´ yznam noun podstatn´e jm´eno adjective pˇr´ıdavn´e jm´eno pronoun z´ajmeno numeral ˇc´ıslovka verb sloveso adverb pˇr´ıslovce preposition pˇredloˇzka conjunction spojka interjection citoslovce particle ˇca´stice punctuation, numeral figures, root of the tree ˇca´rky, teˇcky (unknown, unidentified) nezn´am´e Tabulka 2.1: V´ yznam POS tag˚ u
2.2.2
Lemmatizace
Lemmatizace oznaˇcuje proces pˇrevodu slov v dokumentu na jejich z´akladn´ı tvar, takt´eˇz slovn´ıkov´ y tvar. Podobn´ ym procesem je Stemming, kter´ y urˇcuje u slov jejich koˇren. Lemmatizace bude provedena takt´eˇz n´astrojem Mate tool [4] ze stejn´eho d˚ uvodu jako u POS-taggingu. Po proveden´ı lemmatizace napˇr´ıklad slova pracuj´ıc´ı, pracovn´ı budou nahrazena slovem pr´ace. Z´aroveˇ n se odstran´ı negativn´ı formy slov, takˇze napˇr´ıklad slovo neplat´ı bude nahrazeno slovem platit.
2.3 Volba pˇr´ıznak˚ u
6
V´ ysledkem jsou vˇsechna slova pˇrevedena na stejn´ y tvar pro vˇsechny dokumenty. Celkov´a mnoˇzina unik´atn´ıch slov napˇr´ıˇc tˇr´ıdami se zmenˇs´ı, v´ ybˇer slov pro klasifikaci tak bude efektivnˇejˇs´ı a u ´spˇeˇsnost klasifikace by mˇela vzr˚ ust za pˇredpokladu, ˇze r˚ uzn´e tvary slov se nevyskytuj´ı v r˚ uzn´ ych tˇr´ıd´ach.
2.3
Volba pˇ r´ıznak˚ u
Jak jsem jiˇz naznaˇcil v pˇredchoz´ı kapitole, hlavn´ım probl´emem klasifikace dokument˚ u je vysok´a dimenze pˇr´ıznakov´eho vektoru [22]. Z tohoto d˚ uvodu se pouˇz´ıvaj´ı metody, kter´e tento pˇr´ıznakov´ y vektor redukuj´ı jen na slova, kter´a jsou relevantn´ı pro u ´lohu klasifikace a nˇejak´ ym zp˚ usobem ji ovlivˇ nuj´ı. Samotn´e z´ısk´an´ı pˇr´ıznakov´eho vektoru lze prov´est nˇekolika zp˚ usoby. Nejˇcastˇeji je pouˇz´ıvan´a metoda, kdy kaˇzd´emu slovu v dokumentu je pˇriˇrazena frekvence jeho v´ yskytu. Podle [24] je ale mnohem lepˇs´ı pouˇz´ıt funkci inverzn´ı dokumentov´e frekvence, kter´a je poˇc´ıt´ana podle vztahu 2.1 a n´aslednˇe normov´ana kosinovou transformac´ı podle vztahu 2.2, tf idf (tk , dj ) = ϕ(tk , dj ). log
|Tr | ϕTr (tk )
tf idf (tk , dj ) tkj = qP |t| 2 i=1 tf idf (ti , dj )
(2.1) (2.2)
kde tk je k-t´e slovo (d´ale jen term) dokumentu dj , ϕ(tk , dj ) je frekvence v´ yskytu termu tk v dokumentu, |Tr | je velikost tr´enovac´ı mnoˇziny, tedy poˇcet dokument˚ u a ϕTr (tk ) je dokumentov´a frekvence termu tk , tedy poˇcet dokument˚ u v tr´enovac´ı mnoˇzinˇe ve kter´ ych se dan´ y term vyskytuje. Ale protoˇze i po v´ ypoˇctu inverzn´ı dokumentov´e frekvence je vektor term˚ u pˇr´ıliˇs dlouh´ y a ˇcas klasifikace by rostl, prov´ad´ı se jeho redukce metodami v´ ybˇeru pˇr´ıznak˚ u, kter´e vyberou jen termy, kter´e dok´aˇz´ı dokumenty v jednotliv´ ych kategori´ıch odliˇsit. Podle [29] jsou nejpouˇz´ıvanˇejˇs´ı n´asleduj´ıc´ı metody pro v´ ybˇer pˇr´ıznak˚ u, proto jsou v t´eto pr´aci testov´any.
2.3.1
Dokumentov´ a frekvence (DF)
Dokumentov´a frekvence ud´av´a, v kolika dokumentech se dan´ y term vyskytuje [29, 12, 24]. Je nutn´e pro kaˇzd´ y term proj´ıt vˇsechny dokumenty a spoˇc´ıtat frekvenci jeho v´ yskyt˚ u. N´aslednˇe je vybr´ano jako pˇr´ıznakov´ y vektor k term˚ u s nejvˇetˇs´ı hodnotou frekvence v´ yskyt˚ u. Vych´az´ıme z pˇredpokladu, ˇze slova s malou ˇcetnost´ı v´ yskyt˚ u nejsou pro spr´avn´e urˇcen´ı tˇr´ıdy relevantn´ı. Jedn´a se o nejjednoduˇs´ı formu redukce pˇr´ıznakov´eho vektoru. Nev´ yhodou t´eto metody je paradoxnˇe ignorov´an´ı m´enˇe ˇcast´ ych slov, kter´e mohou dokumenty odliˇsovat.
2.3 Volba pˇr´ıznak˚ u
2.3.2
7
Information Gain (IG)
Pˇred samotn´ ym vysvˇetlen´ım t´eto metody je nutno definovat term´ın entropie. Entropii m˚ uˇzeme definovat jako m´ıru neurˇcitosti. Tak´e m˚ uˇzeme pouˇz´ıt definici z informatiky, kter´a ˇr´ık´a, ˇze entropie je minim´aln´ı poˇcet bit˚ u potˇrebn´ ych k zak´odov´an´ı informace pˇri optim´aln´ım k´odov´an´ı. Obecn´ y vzorec 2.3 pro v´ ypoˇcet entropie je X H(s) = −pi · log2 pi (2.3) kde pi je pravdˇepodobnost i-t´eho mikrostavu. Metoda mˇeˇr´ı sn´ıˇzen´ı entropie zp˚ usobenou pˇr´ıtomnost´ı ˇci nepˇr´ıtomnost´ı slova [18, 29] a je moˇzno ji vypoˇc´ıtat dle vztahu 2.4 j=m
IG(tk ) = −
X
P (cj ) log P (cj )+
j=1 j=m
P (tk )
X
P (cj |tk ) log P (cj |tk )+
(2.4)
j=1 j=m
P (w) ¯
X
P (cj |t¯k ) log P (cj |t¯k )
j=1
kde c znaˇc´ı tˇr´ıdu, m = |C| poˇcet tˇr´ıd, tk term a P (t¯k ) = 1 − P (tk ) inverzn´ı pravdˇepodobnost v´ yskytu slova. Pokud je hodnota Information Gain vysok´a, je pˇr´ıznak povaˇzov´an za d˚ uleˇzit´ y a dan´e slovo se vztahuje k zaˇrazovan´e kategorii. V ostatn´ıch pˇr´ıpadech je pˇr´ıznak ignorov´an.
2.3.3
χ2 test
Jedn´a se o rozˇs´ıˇren´ y statistick´ y test, kter´ y mˇeˇr´ı z´avislost tˇr´ıdy cj na v´ yskytu termu tk za pˇredpokladu, ˇze v´ yskyt termu je nez´avisl´ y na tˇr´ıdˇe, do kter´e klasifikujeme [27]. Protoˇze se jedn´a o statistick´ y test, jeho chov´an´ı je nevyzpytateln´e pro slova s m´alo ˇcast´ ym v´ yskytem v dokumentech [12]. Vypoˇc´ıt´a se podle vzorce 2.5 uveden´eho napˇr´ıklad v [13, 27], χ2 (tk , cj ) =
|T r|(P (cj , tk )P (c¯j , t¯k ) − P (c¯j , tk )P (cj , t¯k )) p P (tk )P (t¯k )P (cj )P (c¯j )
(2.5)
kde P (cj ) je pravdˇepodobnost v´ yskytu tˇr´ıdy cj a P (cj , tk ) je pravdˇepodobnost, ˇze se vyskytne term tk pokud m´ame tˇr´ıdu cj . |T r| oznaˇcuje velikost tr´enovac´ı mnoˇziny, tedy celkov´ y poˇcet dokument˚ u.
2.4 Klasifikaˇcn´ı metody
2.3.4
8
Mutual Information (MI)
Dalˇs´ı rozˇs´ıˇrenou metodou pro v´ ybˇer pˇr´ıznak˚ u je metoda vz´ajemn´e informace (Mutual information) [18, 7]. Tato metoda tak´e zahrnuje pravdˇepodobnosti vzhledem ke kategori´ım. Mutual Information obecnˇe urˇcuje vz´ajemnou z´avislost mezi n´ahodn´ ymi promˇen´ ymi. V naˇsem pˇr´ıpadˇe pro kategorizaci text˚ u urˇcuje vz´ajemnou z´avislost tˇr´ıdy a slova. Pro v´ ypoˇcet M I(tk , cj ) tedy ˇze slovo tk odpov´ıd´a tˇr´ıdˇe cj m˚ uˇzeme pouˇz´ıt vztah 2.6 uveden´ y napˇr´ıklad v [7] nebo v [13], M I(tk , cj ) = log
P (tk , cj ) P (tk )P (cj )
(2.6)
kde P (tk , cj ) je sdruˇzen´a distribuˇcn´ı funkce. Stejnˇe jako u Information Gain jsou pro n´as zaj´ımav´e vyˇsˇs´ı hodnoty M I(tk , cj ).
2.3.5
GSS koeficient
Tato metoda v´ ybˇeru pˇr´ıznak˚ u je pojmenov´ana podle poˇc´ateˇcn´ıch jmen tv˚ urc˚ u, kter´ ymi jsou p´anov´e Gallavotti, Sebastiani a Simi. Podrobnˇe je metoda pops´ana v [13]. Vypoˇctena je podle vzorce 2.7 a jedn´a se v podstatˇe o zjednoduˇ senou formu p 2 metody χ , ze kter´e je odstranˇen jmenovatel. Odstranˇen´e hodnoty P (cj )P (c¯j ) p a P (tk )P (t¯k ) ze jmenovatele pouze zd˚ urazˇ novaly vz´acnˇe se vyskytuj´ıc´ı termy nebo m´alo ˇcast´e tˇr´ıdy. GSS(tk , cj ) = P (tk , cj )P (t¯k , c¯j ) − P (tk , c¯j )P (t¯k , cj )
2.4
(2.7)
Klasifikaˇ cn´ı metody
V t´eto kapitole pˇredstav´ım tˇri klasifikaˇcn´ı metody vybran´e pro danou u ´lohu. Na z´akladˇe pˇreˇcten´e literatury jsem se rozhodl pouˇz´ıt Naivn´ı Bayes˚ uv klasifik´ator, klasifik´ator Maxim´aln´ı entropie a metodu podp˚ urn´ych vektor˚ u (SVM - Support Vector Machine). Nejdˇr´ıve ale v n´asleduj´ıc´ı kapitole uvedu, jak´e typy uˇcen´ı se v t´eto u ´loze pouˇz´ıvaj´ı.
2.4.1
Typy uˇ cen´ı
Uˇ cen´ı s uˇ citelem (Supervised learning) Uˇcen´ı s uˇcitelem, neboli Supervised Learning je metoda, pˇri kter´e se ke tr´enov´an´ı klasifik´atoru pouˇz´ıvaj´ı data, kter´a maj´ı jiˇz oznaˇcenou tˇr´ıdu, do kter´e patˇr´ı. V naˇsem pˇr´ıpadˇe to znamen´a, ˇze klasifik´ator se natr´enuje dokumenty oznaˇcen´ ymi kategori´ı, do kter´e patˇr´ı. Klasifikace prob´ıh´a pˇriveden´ım testovac´ı mnoˇziny na natr´enovan´ y model klasifik´atoru, kter´ y urˇc´ı pravdˇepodobnosti zaˇrazen´ı dokumentu do jednotliv´ ych tˇr´ıd. Tato metoda bude pouˇzita pro tuto pr´aci.
2.4 Klasifikaˇcn´ı metody
9
Uˇ cen´ı bez uˇ citele (Unsupervised learning) Narozd´ıl od uˇcen´ı s uˇcitelem nem´ame u t´eto metody informace o zaˇrazen´ı do tˇr´ıd, m´ame jen vstupn´ı data. C´ılem tedy je nal´ezt podobnosti mezi dokumenty a na jej´ım z´akladˇe dokumenty klasifikovat. V´ıme, ˇze nad dokumenty existuje nˇejak´a skryt´a struktura, ve statistice naz´ yvan´a odhad hustoty, kter´a rozhoduje do jak´e tˇr´ıdy, kter´ y dokument patˇr´ı. Jedna z metod pro urˇcen´ı odhadu hustoty, kter´a nalezne skupiny ve vstupn´ıch datech je shlukov´an´ı. Shlukov´an´ı si m˚ uˇzeme vysvˇetlit na aplikaci komprese obr´azk˚ u. Jako vstup m´ame matici RGB hodnot. Program pak stejn´ ym nebo hodnˇe podobn´ ym pixel˚ um pˇriˇrazuje jednu barvu a touto jednou barvou (skupinou, tˇr´ıdou) jsou pak reprezentov´any nejˇcastˇeji se vyskytuj´ıc´ı pixely podobn´ ych barev (shluky barev). V´ ysledkem shlukov´an´ı jsou jednotliv´e tˇr´ıdy, u kter´ ych mus´ı ˇclovˇek rozhodnout, jak budou pojmenov´any. V kategorizaci novinov´ ych ˇcl´ank˚ u se m˚ uˇze jednat napˇr´ıklad o tˇr´ıdy (shluky) sport, m´oda, politika, .... V u ´loze kategorizace text˚ u se vˇsak metoda uˇcen´ı bez uˇcitele pˇr´ıliˇs nepouˇz´ıv´a, protoˇze klade vˇetˇs´ı n´aroky na uˇzivatele (mus´ı pojmenovat obdrˇzen´e shluky) a dosahuje horˇs´ıch v´ ysledk˚ u. Kombinovan´ a metoda (Semi-Supervised learning) Metoda kombinuje pˇredchoz´ı dvˇe metody uˇcen´ı. K tr´enov´an´ı klasifik´atoru se pouˇz´ıvaj´ı jak data anotovan´a uˇcitelem, tak data bez explicitnˇe pˇriˇrazen´e kategorie. T´eto metody se vyuˇz´ıv´a, pokud m´ame mal´e mnoˇzstv´ı anotovan´ ych dat a velk´e mnoˇzstv´ı dat neanotovan´ ych. Klasifikaˇcn´ı model je nejdˇr´ıve natr´enov´an na mnoˇzinˇe anotovan´ ych dat a na tomto modelu jsou pot´e klasifikovan´a neanotovan´a data. Z takto klasifikovan´ ych dokument˚ u se vyberou ty, kter´e obsahuj´ı nejvˇetˇs´ı pravdˇepodobnost zaˇrazen´ı do tˇr´ıdy a pˇridaj´ı se ke tr´enovac´ı mnoˇzinˇe a cel´ y model je pˇretr´enov´an, dokud nen´ı mnoˇzina nepˇriˇrazen´ ych dokument˚ u minim´aln´ı. Nev´ yhodou je ˇcasov´a n´aroˇcnost tr´enov´an´ı a ne vˇzdy se u ´spˇeˇsnost klasifikace zlepˇsuje.
2.4.2
Naivn´ı Bayes˚ uv klasifik´ ator
Pro u ´lohu automatick´e klasifikace dokument˚ u je nejˇcastˇeji v pˇreˇcten´e literatuˇre pouˇz´ıv´an tento klasifik´ator a to kv˚ uli sv´ ym vlastnostem. Mezi tyto vlastnosti uveden´e v [5] patˇr´ı napˇr´ıklad vlastnost inkrement´aln´ıho uˇcen´ı, je tedy moˇzn´e klasifik´ator dotr´enovat vˇetˇs´ı mnoˇzinou, relativn´ı jednoduchost, mal´a velikost a rychlost klasifikace. Pˇredpokladem pro tento klasifik´ator je nez´avislost pˇr´ıznak˚ u. Princip Mˇejme mnoˇzinu dokument˚ u D = {d1 , d2 , ..., dm }. Kaˇzd´ y dokument di je reprezentov´an pˇr´ıznakov´ ym vektorem, kde kaˇzd´a poloˇzka tohoto vektoru obsahuje pˇr´ıznak
2.4 Klasifikaˇcn´ı metody
10
pro konkr´etn´ı term tj ze slovn´ıku V = {t1 , t2 , ..., tn } obsahuj´ıc´ı n r˚ uzn´ ych term˚ u [22]. Pˇred uveden´ım samotn´ ych vztah˚ u pro tento klasifik´ator je nutn´e zm´ınit, ˇze kaˇzd´ y dokument di pˇr´ısluˇs´ı alespoˇ n jedn´e tˇr´ıdˇe cj z mnoˇziny vˇsech tˇr´ıd C = {c1 , c2 , ..., cc }. Zaˇrazen´ı nezn´am´eho dokumentu d do tˇr´ıdy pak prob´ıh´a v´ ypoˇctem podm´ınˇen´ ych pravdˇepodobnost´ı pro kaˇzdou tˇr´ıdu a v´ ybˇerem tˇr´ıdy s maxim´aln´ı aposteriorn´ı pravdˇepodobnost´ı. V´ ypoˇcet podm´ınˇen´e aposteriorn´ı pravdˇepodobnosti P (cj |d) (pravdˇepodobnost zaˇrazen´ı dokumentu d do tˇr´ıdy cj ) je proveden pouˇzit´ım Bayessova pravidla 2.8. P (cj |d) =
P (cj )P (d|cj ) P (d)
(2.8)
Apriorn´ı pravdˇepodobnost P (cj ) je vypoˇctena z mnoˇziny tr´enovac´ıch dat jako relativn´ı ˇcetnost v´ yskyt˚ u dokument˚ u patˇr´ıc´ıch do tˇr´ıdy cj (vztah 2.9). P (d) pak urˇcuje pravdˇepodobnost v´ yskyt dokumentu d. P (cj ) =
P ocet termu v cj Celkovy pocet termu v trenovaci mnozine
(2.9)
Podm´ınˇen´a pravdˇepodobnost P (d|cj ) dokumentu d vzhledem k tˇr´ıdˇe cj je vypoˇctena z pravdˇepodobnost´ı v´ yskytu jednotliv´ ych term˚ u pˇres vˇsechny termy nalezen´e v dokumentu d podle vztahu 2.10. P (d|cj ) = Q
Y |d|! P (t|cj )f (t,d) f (t, d)! t∈d t∈d
(2.10)
Hodnota f(t,d) v pˇredchoz´ım vzorci urˇcuje poˇcet v´ yskyt˚ u termu t v dokumentu d a |d| znaˇc´ı souˇcet frekvenc´ı vˇsech v´ yskyt˚ u term˚ u v dokumentu neboli celkovou d´elku dokumentu. Q |d|! pak znaˇc´ı vˇsechny moˇzn´e kombinace poˇrad´ı term˚ u. t∈d f (t,d)! Pravdˇepodobnosti jednotliv´ ych term˚ u vzhledem ke vˇsem term˚ um v dan´e tˇr´ıdˇe jsou vypoˇcteny podle vztahu 2.11 jako pod´ıl frekvence termu v dan´e tˇr´ıdˇe (f(t,c)) a souˇctu frekvenc´ı vˇsech term˚ u v dan´e tˇr´ıdˇe. f (t, cj ) 0 t0 ∈V f (t , cj )
P (t|cj ) = P
(2.11)
Zaˇrazen´ı dokumentu do tˇr´ıdy, jak jsem jiˇz uvedl, je provedeno v´ ybˇerem tˇr´ıdy s maxim´aln´ı aposteriorn´ı pravdˇepodobnost´ı P (cj |d) podle vztahu 2.12 uveden´em v [19]. cmax = arg max P (cj |d) = arg max P (cj ) cj ∈C
kde n je poˇcet slov v dokumentu.
cj ∈C
n Y k=1
P (tk |cj )
(2.12)
2.4 Klasifikaˇcn´ı metody
2.4.3
11
Support Vector Machine
Support Vector Machine (d´ale jen SVM) neboli metoda podp˚ urn´ ych vektor˚ u je druhou metodou strojov´eho uˇcen´ı, kterou budu v t´eto pr´aci vyuˇz´ıvat, a proto ji zde struˇcnˇe pˇredstav´ım. Informace obsaˇzen´e v t´eto kapitole byly ˇcerp´any pˇrev´aˇznˇe z [19] a doplnˇeny z [5], odkud byl tak´e pˇrekreslen a doplnˇen obr´azek 2.2. Omezme se pro jednoduchost a pro lepˇs´ı vysvˇetlen´ı na bin´arn´ı klasifik´ator. SVM pak funguje na principu hled´an´ı nadroviny v prostoru pˇr´ıznak˚ u oddˇeluj´ıc´ı od sebe data tak, aby minim´aln´ı vzd´alenost bod˚ u od nadroviny pro obˇe rozdˇelen´e mnoˇziny byla maxim´aln´ı. Grafick´e zn´azornˇen´ı metody je na obr´azku 2.2.
Obr´azek 2.2: Nejlepˇs´ı moˇzn´a oddˇelovac´ı nadrovina a podp˚ urn´e vektory ˇ Cerven´ e body na obr´azku oznaˇcuj´ı podp˚ urn´e vektory (support vectors), kter´e jsou d˚ uleˇzit´e pro urˇcen´ı optim´aln´ı nadroviny w · x − b = 0. Klasifikace je pak provedena podle nadrovin pro jednotliv´e tˇr´ıdy. Vˇsechny body splˇ nuj´ıc´ı podm´ınku w·x−b≥1 jsou zaˇrazeny do tˇr´ıdy ”troj´ uheln´ıˇck˚ u” (oznaˇcme jako y=+1) a vˇsechny body splˇ nuj´ıc´ı w · x − b ≤ −1 jsou naopak zaˇrazeny do tˇr´ıdy ”koleˇcek” (oznaˇcme jako y=-1). Body, kter´e se vyskytovaly mezi, jsou zaˇrazeny k nejbliˇzˇs´ı tˇr´ıdˇe. Za v´ yˇse uveden´ ych podm´ınek je hled´an´ı
´ Uloha se ale ve vˇetˇsinˇe pˇr´ıpad˚ u neˇreˇs´ı pˇr´ımo, ale vyuˇz´ıv´a se tzv. du´aln´ıho probl´emu. Du´ aln´ı pˇ r´ıpad Mnohem v´ ypoˇcetnˇe jednoduˇsˇs´ı je hledat parametry αi , kter´a jsou ˇreˇsen´ım rovnice 2.14. K ˇreˇsen´ı se pouˇz´ıv´a metody kvadratick´eho programov´an´ı. l l l X 1 XX αi αj yi yj (xi , xj )) α ~ = argmax( αi − 2 α ~ i=1 j=1 i=1
(2.14)
za podm´ınek αi ≥ 0, i = 1, 2...l
a
l X
ai y i = 0
i=1
Po vyˇreˇsen´ı rovnice pˇrejdeme zpˇet k pˇr´ım´emu ˇreˇsen´ı a pomoc´ı zjiˇstˇen´ ych parametr˚ u α vypoˇc´ıt´ame hodnotu w podle vzorce 2.15. w=
l X
αi yi xi
(2.15)
i=1
Neline´ arn´ı klasifikace Obr´azek 2.2 ale ilustruje pouze jednoduch´ y pˇr´ıpad, kdy jednotliv´e tˇr´ıdy jsou od sebe line´arnˇe separovateln´e. Prakticky tomu ale tak nen´ı, proto je neoddˇelitelnou souˇc´ast´ı t´eto metody j´adrov´a funkce (tzv. kernel function nebo tak´e kernel transformation), kter´a pˇrevede line´arnˇe neseparovatelnou u ´lohu na line´arnˇe separovatelnou pomoc´ı projekc´ı do vyˇsˇs´ı dimenze neˇz jsou vstupn´ı data. Protoˇze pro urˇcen´ı nadroviny a zaˇrazen´ı do tˇr´ıdy pro line´arnˇe separovatelnou u ´lohu vyuˇz´ıv´ame pouze skal´arn´ıch souˇcin˚ u, lze vyuˇz´ıt triku (tzv. kernel trick ) a pro urˇcen´ı nadroviny ve v´ıcedimenzion´aln´ım prostoru pouˇz´ıt skal´arn´ı souˇciny hodnot j´adrov´e funkce, zapsan´e jako K(~ xi , x~j ) = x~i T x~j
2.4 Klasifikaˇcn´ı metody
2.4.4
13
Maxim´ aln´ı entropie
Posledn´ım klasifik´atorem je klasifik´ator maxim´aln´ı entropie. V oblasti zpracov´an´ı textu se jedn´a o rozˇs´ıˇrenou metodu pouˇzitelnou napˇr. pro zjiˇstˇen´ı v´ yznamu slov, strojov´ y pˇreklad nebo oznaˇckov´an´ı textu. Veˇsker´e informace o tomto klasifik´atoru byly ˇcerp´any z [8], kter´ y velmi podrobnˇe popisuje tento klasifik´ator i s n´azorn´ ymi obr´azky pro pochopen´ı funkce. Existuje nˇekolik definic maxim´aln´ı entropie. Jedna z definic ˇr´ık´a, ˇze algoritmus maxim´aln´ı entropie m˚ uˇze b´ yt vyuˇzit k nalezen´ı jak´ehokoliv pravdˇepodobnostn´ıho rozdˇelen´ı [9]. Jin´a definice ˇr´ık´a, ˇze pokud nev´ıme o statistick´em rozdˇelen´ı v˚ ubec nic, nebo m´ame jen m´alo informac´ı, potom nejpravdˇepodobnˇejˇs´ı tvar rozdˇelen´ı je podle informac´ı, kter´e o rozdˇelen´ı m´ame a m´a nejvyˇsˇs´ı moˇznou entropii. To odpov´ıd´a principu Occamovy bˇritvy, kter´a se snaˇz´ı naj´ıt co nejjednoduˇs´ı popis na z´akladˇe toho, co zn´ame. Entropie se spoˇc´ıt´a podle vzorce 2.16 N X S=− (pi logpi )
(2.16)
i=1
Princip Tr´enovac´ı data se v tomto modelu vyuˇz´ıvaj´ı k omezen´ı rozloˇzen´ı, kter´e mus´ı b´ yt splnˇeno pˇri odhadu modelu. Pravdˇepodobnost pi z´ısk´ame jako funkci zaˇrazen´ı dan´eho slova do tˇr´ıdy, kter´a n´aleˇz´ı dat˚ um v tr´enovac´ı mnoˇzinˇe. Pˇredpokl´adejme, ˇze m´ame n-rozmˇern´ y vektor pˇr´ıznak˚ u, kter´ y odpov´ıd´a funkci fi (d, c) modeluj´ıc´ı rozloˇzen´ı pˇr´ıznak˚ u pro dan´ y dokument d a tˇr´ıdu c. Naˇs´ım c´ılem je nalezen´ı modelu, kter´ y bude tomuto rozloˇzen´ı pˇr´ıznak˚ u odpov´ıdat. Necht’ D je mnoˇzina vˇsech tr´enovac´ıch dat. N´ami hledan´a podm´ınˇen´a pravdˇepodobnost P (c|d) zaˇrazen´ı dokumentu d do tˇr´ıdy c mus´ı splˇ novat vlastnost 2.17. X X 1 X fi (d, c(d)) = P (d) P (c|d)fi (d, c) |D| d∈D c d
(2.17)
P(d) oznaˇcuje pravdˇepodobnostn´ı rozdˇelen´ı dokument˚ u, kter´e nezn´ame, proto n´as jeho modelov´an´ı nezaj´ım´a. Jako aproximaci t´eto hodnoty pouˇzijeme mnoˇzinu tr´enovac´ıch dokument˚ u 2.18. 1 X 1 XX fi (d, c(d)) = P (c|d)fi (d, c) (2.18) |D| d∈D |D| d∈D c Dalˇs´ım krokem je vypoˇcten´ı pˇr´ıznakov´ ych funkc´ı z tr´enovac´ıch dat, kter´e budou pouˇzity pro klasifikaci. Potom pro kaˇzd´ y pˇr´ıznak vypoˇc´ıtat nad tr´enovac´ımi daty oˇcek´avanou hodnotu, kter´a bude pouˇzita jako omezen´ı tr´enovan´eho modelu [21].
2.4 Klasifikaˇcn´ı metody
14
Parametrick´ a forma Pokud m´ame vypoˇctena vˇsechna omezen´ı, m´ame zaruˇceno, ˇze jsme nalezli jednoznaˇcn´ y model, kter´ y m´a maxim´aln´ı entropii. Dle [8] m˚ uˇze b´ yt uk´az´ano, ˇze rozdˇelen´ı m´a vˇzdy exponenci´aln´ı charakter (vzorec 2.19) P (c|d) =
X 1 exp( λi fi (d, c)) Z(d) i
(2.19)
kde fi (d, c) je model pˇr´ıznaku, λi odhadovan´ y parametr a Z(d) je normalizaˇcn´ı faktor pro zajiˇstˇen´ı spr´avn´e ˇc´ıseln´e hodnoty pravdˇepodobnosti vypoˇcten´ y podle 2.20. X X exp( Z(d) = λi fi (d, c)) (2.20) c
i
Po vypoˇcten´ı vˇsech omezen´ı je ˇreˇsen´ı maxim´aln´ı entropie stejn´e jako ˇreˇsen´ı du´aln´ıho vˇerohodnostn´ıho probl´emu (Maximum Likehood Problem) pro modely se stejnou exponenci´aln´ı funkc´ı. Obˇe ˇreˇsen´ı poskytuj´ı konvexn´ı funkci s jedn´ım glob´aln´ım maximem a ˇza´dn´ ym lok´aln´ım maximem. K ˇreˇsen´ı t´eto du´aln´ı u ´lohy se pouˇz´ıv´a horolezeck´ y algoritmus (HillClimbing algorithm), kter´ y z poˇc´ateˇcn´ıho odhadu nˇejak´eho zvolen´eho exponenci´aln´ıho rozdˇelen´ı konverguje k ˇreˇsen´ı vˇerohodnostn´ıho probl´emu, kter´e je z´aroveˇ n glob´aln´ım ˇreˇsen´ım maxim´aln´ı entropie [21].
15
Kapitola 3 Anal´ yza 3.1
N´ astroje pro klasifikaci text˚ u
Pro ˇreˇsen´ı t´eto u ´lohy jsem se na z´akladˇe pˇreˇcten´ ych ˇcl´ank˚ u, srovn´an´ı vlastnost´ı a v´ ysledk˚ u jednotliv´ ych klasifik´ator˚ u rozhodl vyzkouˇset celkem tˇri klasifikaˇcn´ı metody. Z´akladn´ım poˇzadavkem tedy bylo, aby vybran´ y n´astroj pokud moˇzno obsahoval vˇsechny poˇzadovan´e klasifikaˇcn´ı algoritmy, byl snadno konfigurovateln´ y, byly k nˇemu k dispozici zdrojov´e k´ody a abych jejich modifikac´ı neporuˇsil licenˇcn´ı ujedn´an´ı. Z´aroveˇ n jsem hledal n´astroj, kter´ y by bylo moˇzn´e vyuˇz´ıt pro komerˇcn´ı vyuˇzit´ı, nicm´enˇe uv´ad´ım zde i placen´e n´astroje, zejm´ena kv˚ uli poskytovan´e technick´e podpoˇre pˇri v´ yskytu probl´emu s klasifikac´ı. Nal´ezt n´astroj, kter´ y by obsahoval vˇsechny klasifik´atory, kter´e jsem chtˇel vyzkouˇset, se uk´azalo jako docela tˇeˇzk´ yu ´kol. Vˇetˇsina klasifikaˇcn´ıch n´astroj˚ u obsahovala pouze dva klasifikaˇcn´ı algoritmy z poˇzadovan´ ych tˇr´ı. Nakonec jsem nalezl n´astroj Minorthird, kter´ y jsem v t´eto pr´aci pouˇzil. V nˇekolika n´asleduj´ıc´ıch odstavc´ıch jsou pops´any vˇsechny n´astroje, o kter´ ych jsem uvaˇzoval. Popis obsahuje pˇrehled licenc´ı, klasifikaˇcn´ı algoritmy, kter´e obsahuj´ı a jin´e d˚ uleˇzit´e vlastnosti, kter´e stoj´ı za zm´ınku. Z´aroveˇ n je tato kapitola zakonˇcena tabulkou 3.1 pˇrehlednˇe zobrazuj´ıc´ı klasifik´atory, kter´e obsahuj´ı.
3.1.1
SVMlight
SVMlight [16] implementuje metodu Vapnik’s Support Vector Machine. Tento n´astroj jsem uvaˇzoval pro vyuˇzit´ı v kombinaci s jin´ ym n´astrojem, protoˇze vˇetˇsina aplikac´ı tuto metodu neobsahuje kv˚ uli implementaˇcn´ı sloˇzitosti. • Licence: - Academic Free • Cena: Pro vˇedeck´e pouˇzit´ı zdarma, pro komeˇcn´ı nutno svolen´ı autora • Programovac´ı jazyk: Java • Dokumentace: Ne
3.1 N´astroje pro klasifikaci text˚ u
16
• Tutori´ al: Ano
3.1.2
Mallet
Aplikace Mallet je dalˇs´ım bal´ıkem pro klasifikaci text˚ u jin´e u ´lohy strojov´eho uˇcen´ı a zpracov´an´ı pˇrirozen´eho jazyka [20]. N´astroj takt´eˇz obsahuje spousty pˇr´ıklad˚ u pouˇzit´ı a konfigurace. N´astroj bohuˇzel neobsahuje klasifik´ator SVM, proto jsem ho pˇri v´ ybˇeru neuvaˇzoval. • Licence: CPL (Common Public License) licence, OpenSource, moˇzno vyuˇz´ıt i pro komerˇcn´ı vyuˇzit´ı • Cena: Zdarma • Programovac´ı jazyk: Java • Dokumentace: API javadoc • Tutori´ al: Ano
3.1.3
RTextTools
Velmi podrobnˇe dokumentovan´ y open source projekt [25] vytvoˇren´ y v r´amci nˇekolika univerzit: University of California, University of Washington, Sciences Po Paris, Vrije Universiteit Amsterdam. Obsahuje celkem devˇet klasifik´ator˚ u, bohuˇzel neobsahuje ten nejjednoduˇs´ı a to Naive Bayes, coˇz byl hlavn´ı d˚ uvod, proˇc jsem ho nepouˇzil. • Licence: GNU GPL • Cena: Zdarma • Programovac´ı jazyk: Java • Dokumentace: Ano, javadoc i hodnˇe podrobn´a dokumentace • Tutori´ al: Ano
3.1.4
LingPipe
Bal´ık n´astroj˚ u LingPipe [1] je urˇcen pro zpracov´an´ı text˚ u vyuˇz´ıvaj´ıc´ı metod poˇc´ıtaˇcov´e lingvistiky. Velmi drah´ y n´astroj pro komerˇcn´ı vyuˇzit´ı, sloˇzit´a licence. Pomˇer cena/v´ ykon neodpov´ıd´a, proto byl n´astroj zavrˇzen. • Licence: Licence podle vyuˇzit´ı • Cena: Zdarma pro akademick´e pouˇzit´ı, 9500$ / 1 rok pro komerˇcn´ı pouˇzit´ı • Programovac´ı jazyk: Java • Dokumentace: Ano, javadoc, podrobn´a dokumentace • Tutori´ al: Ano
3.1 N´astroje pro klasifikaci text˚ u
3.1.5
17
The Dragon Toolkit
N´astroj [30] je bohuˇzel zdarma k dispozici pouze pro akademick´e pouˇzit´ı a jeho autoˇri komerˇcn´ı vyuˇzit´ı v˚ ubec nezmiˇ nuj´ı. Aplikace umoˇzn ˇuje vyuˇzit´ı pro klasifikaci text˚ u, clustering a pro sumarizaci text˚ u. V´ yhodou n´astroje je jeho ˇsk´alovatelnost. Narozd´ıl od n´astroj˚ u jako Weka se pˇredem poˇc´ıt´a s velk´ ymi objemy dat, takˇze data nejsou naˇc´ıt´ana do pamˇeti vˇsechna, ale postupnˇe, coˇz umoˇzn ˇuje pracovat s mnoha dokumenty v omezen´e pamˇeti. • Licence: - k dispozici online na str´ank´ach projektu 1 • Cena: Zdarma pro akademick´e pouˇzit´ı • Programovac´ı jazyk: Java • Dokumentace: Ano, javadoc i hodnˇe podrobn´a dokumentace • Tutori´ al: Ano
3.1.6
Stanford
N´astroj [11] byl vytvoˇren na univerzitˇe Stanford skupinou vˇedeck´ ych pracovn´ık˚ u. Vyuˇzit je zejm´ena pro rozpozn´av´an´ı pojmenovan´ ych entit, ale implementovan´e klasifik´atory lze vyuˇz´ıt i pro klasifikaci text˚ u. Tento n´astroj obsahuje zejm´ena Conditional Random Fields (CRF) klasifik´ator, jeˇz by ˇslo po spr´avn´e konfiguraci vyuˇz´ıt pro klasifikaci algoritmem Maximum Entropy. Takt´eˇz neobsahuje vˇsechny pouˇzadovan´e klasifik´atory, proto nebyl pouˇzit, nicm´enˇe ho uv´ad´ım protoˇze jiˇz s t´ımto n´astrojem m´am zkuˇsenosti. • Licence: GNU General Public License, moˇzno vyuˇz´ıt i pro komerˇcn´ı vyuˇzit´ı • Cena: Zdarma • Programovac´ı jazyk: Java • Dokumentace: API javadoc • Tutori´ al: Ano
3.1.7
Weka 3
N´astroj [14] vytvoˇren´ y na univerzitˇe Waikato. Obsahuje algoritmy strojov´eho uˇcen´ı pro vyuˇzit´ı zejm´ena v aplikaci pro dolov´an´ı dat z textu. Implementovan´e klasifik´atory je moˇzno vˇsak vyuˇz´ıt i pro n´aˇs u ´ˇcel, bohuˇzel takt´eˇz neobsahuje vˇsechny poˇzadovan´e. Dokumenty tak´e naˇc´ıt´a vˇsechny do pamˇeti, takˇze nen´ı vhodn´ y ani z hlediska pamˇet’ov´e optimalizace. 1
http://dragon.ischool.drexel.edu/
3.1 N´astroje pro klasifikaci text˚ u
18
• Licence: GNU General Public License. • Cena: Zdarma pro akademick´e pouˇzit´ı • Programovac´ı jazyk: Java • Dokumentace: Ano, javadoc i hodnˇe podrobn´a dokumentace • Tutori´ al: Ano
3.1.8
Minorthird
Soubor n´astroj˚ u vytvoˇren´ ych profesorem na univerzitˇe Carnegie Mellon [6]. Na str´ank´ach aplikace jsou k dispozici testovac´ı data s uk´azkami konfigurace. N´astroj obsahuje vˇsechny tˇri poˇzadovan´e klasifik´atory a mnoho dalˇs´ıch, jejichˇz v´ yˇcet je uveden v tabulce 3.1. • Licence: BSD licence, OpenSource, moˇzno vyuˇz´ıt i pro komerˇcn´ı vyuˇzit´ı • Cena: Zdarma • Programovac´ı jazyk: Java • Dokumentace: API javadoc
Neuronov´e s´ıtˇe
GLM net
Knn
HMM
CRF
Decision Trees
SVM
Maximum Entropy
N´astroj SVMlight — Mallet CPL RTextTools GPL-3 LingPipe — The Dragon Toolkit — Stanford GNU GPL Weka 3 GNU GPL Minorthird BSD
Naive Bayes
Licence
• Tutori´ al: Ano
×
×
× ×
× ×
× ×
×
× × ×
×
× ×
× ×
×
×
× × ×
× ×
×
Tabulka 3.1: Tabulka zobrazuj´ıc´ı implementovan´e klasifikaˇcn´ı algoritmy v klasifikaˇcn´ıch bal´ıc´ıch
ˇ 3.2 Struktura datab´aze CTK
3.2
19
ˇ Struktura datab´ aze CTK
ˇ InfoBanka CTK vyuˇz´ıv´a k uloˇzen´ı sv´ ych ˇcl´ank˚ u relaˇcn´ı a fulltextov´e datab´aze. Pro sv´e klienty z nich prov´ad´ı export do form´atu NewsML [28], kter´ y je zaloˇzen na XML. V´ yhodou tohoto form´atu je zejm´ena snadn´a transformace do jin´ ych form´at˚ u a pˇr´ım´e vyuˇzit´ı na webov´ ych str´ank´ach. D´ale je d´ıky volbˇe uloˇzen´ı v tomto form´atu moˇzno uchov´avat vˇetˇs´ı mnoˇzstv´ı metadat 2 , kter´a usnadˇ nuj´ı uˇzivateli dalˇs´ı pr´aci s dokumenty.
3.2.1
Rozdˇ elen´ı InfoBanky
Obsah InfoBanky (v´ıce viz [10]) lze rozdˇelit do nˇekolika ˇca´st´ı: • Aktu´aln´ı zpravodajstv´ı • Archivy • Fotobanka • Ud´alosti • Podnikov´a data • Faktografie (znalostn´ı datab´aze) • Sportovn´ı relaˇcn´ı datab´aze • Magaz´ınov´ y v´ ybˇer Plus • Monitoring m´edi´ı Podrobnˇejˇs´ı pˇrehled jednotliv´ ych datab´az´ı je pro pˇrehlednost pops´an v pˇr´ıloze D.
3.2.2
Struktura zpracov´ avan´ ych soubor˚ u
Kaˇzd´ y novinov´ y ˇcl´anek m´a pevnˇe dannou strukturu, kter´a je definov´ana exportem z textov´e datab´aze. Kromˇe samotn´e textov´e podoby jsou u kaˇzd´eho ˇcl´anku uvedena metadata. Jedn´a se napˇr´ıklad o datum, ˇcas, m´ısto a pro mˇe nejd˚ uleˇzitˇejˇs´ı hlavn´ı (hlavni kategorie) a vedlejˇs´ı kategorie (kategorie). Kaˇzd´ y ˇcl´anek m´a tedy pˇriˇrazen hlavn´ı kategorii a seznam vˇsech kategori´ı, do kter´ ych patˇr´ı. Vˇsechny kategorie maj´ı stejnou prioritu a jedn´a se o tzv. ploch´e sch´ema. Mezi kategoriemi tedy neexistuje ˇza´dn´a hierarchie a kaˇzd´ y ˇcl´anek m˚ uˇze spadat prakticky do libovoln´e, bez ohledu na existenci v jin´ ych kategori´ı. Na z´akladˇe tohoto poznatku n´am bude staˇcit pouze jeden natr´enovan´ y model pro kaˇzd´ y klasifik´ator. Podrobnˇejˇs´ı vysvˇetlen´ı vˇsech metadat, potaˇzmo XML element˚ u je uvedeno v tabulce 3.2. 2´
Udaje popisuj´ıc´ı vlastn´ı dokument.
ˇ 3.2 Struktura datab´aze CTK
20
<dokument />
element, kter´ y v sobˇe vnoˇruje jednotliv´e ˇcl´anky element obsahuj´ıc´ı identifik´ator ˇcl´anku a vnoˇruj´ıc´ı elementy s metadaty a samotn´ ym textem titulek ˇcl´anku datum vyd´an´ı ˇcl´anku ˇcas vyd´an´ı ˇcl´anku m´ısto ke kter´emu se ˇcl´anek vztahuje kl´ıˇcov´a slova hlavn´ı kategorie ˇcl´anku zaˇrazen´ı do vedlejˇs´ıch kategori´ı <priorita /> priorita ˇcl´anku <servis /> servisn´ı informace, napˇr. region ˇcl´anku samotn´ y textov´ y obsah zpr´avy Tabulka 3.2: XML elementy zpracov´avan´ ych soubor˚ u s novinov´ ymi ˇcl´anky Uk´ azka form´ atu vstupn´ıho souboru Vstupn´ı soubor pro zpracov´an´ı parserem je sestaven z XML element˚ u obsaˇzen´ ych v tabulce 3.2 a m´a n´asleduj´ıc´ı strukturu: <dokument> Torn´a do v USA z a b i l o ˇs e s t l i d´ı 01.01.2011 00:09 USA USA p o ˇc a s´ı torn´a do met met kat
4 <s e r v i s >mus Torn´a do v USA z a b i l o ˇs e s t l i d´ı
; Washington . . . s t r
...
3.3 Evaluaˇcn´ı metriky
3.2.3
21
Kategorie ˇ cl´ ank˚ u
Veˇsker´e kategorie ˇcl´ank˚ u do kter´ ych budeme ˇcl´anky klasifikovat jsou uvedeny v pˇr´ıloze E v tabulce E.1.
3.2.4
Textov´ y korpus
N´asleduj´ıc´ı statitiska v tabulce 3.3 ukazuje pˇrehled ruˇcnˇe anotovan´ ych (oznaˇcen´ ych) dokument˚ u, kter´e budou pouˇzity k tr´enov´an´ı modelu a k ovˇeˇren´ı u ´spˇeˇsnosti natr´enovan´eho modelu. Z cel´eho korpusu byly vybr´any kategorie, kter´e mˇely v´ıce jak 250 dokument˚ u. Z´aroveˇ n jich ale bylo z kaˇzd´e kategorie vybr´ano maxim´alnˇe 600, aby tr´enovac´ı data byla vyv´aˇzen´a. Vyhodnocen´ı bylo provedeno kˇr´ıˇzovou validac´ı3 Celkov´ y poˇcet dokument˚ u 11955 Velikost tr´enovac´ı mnoˇziny 80% korpusu vyhodnoceno kˇr´ıˇzovou validac´ı Hlavn´ıch kategori´ı 25 Vedlejˇs´ıch kategori´ı 60 Poˇcet slov 2974040 Poˇcet unik´atn´ıch slov 193399 Poˇcet unik´atn´ıch lemmat 152462 Poˇcet podstatn´ ych jmen 1243111 Poˇcet pˇr´ıdavn´ ych jmen 349932 Poˇcet z´ajmen 154232 Poˇcet ˇc´ıslovek 216986 Poˇcet sloves 366246 Poˇcet pˇr´ıslovc´ı 140726 Poˇcet pˇredloˇzek 346690 Poˇcet spojek 144648 Poˇcet citoslovc´ı 8 Poˇcet ˇca´stic 10983 Tabulka 3.3: Statistika textov´eho korpusu
3.3
Evaluaˇ cn´ı metriky
Pro vyhodnocen´ı, zda byl dokument spr´avnˇe klasifikov´an je potˇreba zn´at tˇr´ıdu nebo tˇr´ıdy, do kter´ ych dokument patˇr´ı. N´aslednˇe je pouˇzita nˇekter´a z n´asleduj´ıc´ıch evaluaˇcn´ı metod [19] pouˇz´ıvan´ ych pro danou u ´lohu k urˇcen´ı u ´spˇeˇsnosti klasifikace. V naˇsem pˇr´ıpadˇe se pro vysvˇetlen´ı metrik omez´ıme na bin´arn´ı klasifik´ator, tedy kategorizujeme do dvou tˇr´ıd. Z´akladem pro vˇetˇsinu metrik je urˇcen´ı konfuzn´ı ma3
Ang. Cross Validation, je statistick´a metoda vyhodnocov´an´ı u ´spˇeˇsnosti klasifikace.
3.3 Evaluaˇcn´ı metriky
22
tice velikosti 2x2 prvk˚ u. Matice a jej´ı jednotliv´e prvky jsou podrobnˇe vysvˇetleny tabulkou 3.4. spr´avn´a tˇr´ıda predikovan´a tˇr´ıda
Ano NE
Ano Ne tpc f pc f nc tnc
Tabulka 3.4: Konfuzn´ı matice bin´arn´ıho klasifik´atoru pro tˇr´ıdu c Jednotliv´e buˇ nky tabulky si m˚ uˇzeme vysvˇetlit n´asleduj´ıc´ım zp˚ usobem. Pt´ame 4 se, zda predikovan´a tˇr´ıda patˇr´ı ˇci nepatˇr´ı (Ano/Ne) do tˇr´ıdy c a oˇcek´av´ame odpovˇed’ Ano/Ne zda klasifik´ator rozhodl spr´avnˇe. Vysvˇetlen´ı d´ılˇc´ıch buˇ nek: • tpc (true positives) - kategorie dokumentu se shoduje se spr´avnou kategori´ı • f pc (false positives) - kategorie se neshoduje se spr´avnou kategori´ı, klasifik´ator zaˇradil dokument do ˇspatn´e kategorie • f nc (false negatives) - klasifik´ator nezaˇradil dokument do kategorie do kter´e skuteˇcnˇe patˇr´ı • tnc (true negatives) - klasifik´ator spr´avnˇe rozhodl o nezaˇrazen´ı do kategorie V ide´aln´ım pˇr´ıpadˇe budou hodnoty tpc a tnc rovny hodnotˇe 1 a zb´ yvaj´ıc´ı 0.
3.3.1
Pˇ resnost
Pˇresnost (Precision) urˇcuje, kolik dokument˚ u oznaˇcen´ ych klasifik´atorem bylo kategorizov´ano spr´avnˇe. Vypoˇcten´ı je podle vzorce 3.1. P =
3.3.2
tpc tpc + f pc
(3.1)
´ Uplnost
´ Uplnost (Recall ) oznaˇcuje, kolik dokument˚ u z celkov´eho mnoˇzstv´ı bylo klasifikov´ano spr´avnˇe. Urˇcen´ı u ´plnosti je podle vzorce 3.2. R= 4
V´ ysledek klasifik´ atoru
tpc tpc + f nc
(3.2)
3.3 Evaluaˇcn´ı metriky
3.3.3
23
F-measure
Metrika F-measure patˇr´ı obecnˇe k nejpouˇz´ıvanˇejˇs´ım metrik´am [19] pro zjiˇstˇen´ı spr´avnosti klasifikace. Tato metrika je poˇc´ıt´ana jako harmonick´ y pr˚ umˇer pˇresnosti au ´plnosti. Vzorec pro v´ ypoˇcet F-measure je d´an vztahem 3.3. F =
3.3.4
2P R 2tpc = P +R 2tpc + f pc + f nc
(3.3)
Cohenenova kappa statistika
Dalˇs´ı metrikou pro urˇcen´ı u ´spˇeˇsnosti klasifikace je Cohenenova kappa statistika [2]. Pokud m´ame vypoˇctenou konfuzn´ı matici, je jej´ı v´ ypoˇcet d´an jednoduch´ ym vzorcem 3.4 P0 − Pc (3.4) n − Pc ve kter´em je P0 vypoˇcteno podle vzorce 3.5, Pc pak podle vzorce 3.6 a n je souˇcet vˇsech prvk˚ u konfuzn´ı matice. V n´asleduj´ıc´ıch vzorc´ıch ni+ a n+i m´a v´ yznam 5 6 ˇr´adkov´e , resp. sloupcov´e pravdˇepodobnosti. κ=
P0 =
c X
nii
(3.5)
i=1
Pc =
c X ni+ ∗ n+i i=1
3.3.5
n
(3.6)
Chybovost - Error Rate
Dalˇs´ı metrikou pro urˇcen´ı u ´spˇeˇsnosti klasifikace je chybovost (Error Rate). Zat´ımco u pˇredchoz´ıch metod jsme pˇristuppovali k hodnocen´ı z pozitivn´ıho hlediska, tedy jak byl klasifik´ator u ´spˇeˇsn´ y (v procentech), u t´eto metody zjiˇstujeme, jak velk´e chyby jsme se dopustili. V´ ypoˇcet m˚ uˇzeme znovu prov´est z konfuzn´ı matice podle vzorce 3.7 a to vydˇelen´ım chybnˇe klasifikovan´ych 7 (E) poˇctem vˇsech klasifikovan´ ych dokument˚ u (N ). E (3.7) N Touto metodou m˚ uˇzeme vypoˇc´ıtat d´ılˇc´ı ER pro kaˇzdou kategorii, kdy poˇc´ıt´ame pouze z pˇr´ısluˇsn´e ˇra´dky (sloupce) konfuzn´ı matice. Tato metrika m´a souvislost s metrikou Accuracy popsanou v kapitole 3.3.7. Pro klasifikaci do jedn´e kategorie plat´ı vztah Acc = 1 − ER. ER =
5
Souˇcet pravdˇepodobnost´ı na ˇr´ adce v konfuzn´ı matici. Souˇcet pravdˇepodobnost´ı ve sloupci v konfuzn´ı matici. 7 Souˇcet vˇsech ˇc´ısel (poˇctu dokument˚ u) konfuzn´ı matice mimo diagon´alu. 6
3.3 Evaluaˇcn´ı metriky
3.3.6
24
Hammingovo metrika
Pˇredchoz´ı metriky jsou vhodn´e pˇredevˇs´ım pro kategorizaci do jedn´e kategorie. Pokud ale chceme dokumenty zaˇrazovat do v´ıce kategori´ı, je nutn´e pro vyhodnocen´ı u ´spˇeˇsnosti pouˇz´ıt jin´e metriky. Jednou z takov´ ychto metrik je Hamming Loss popsan´a v [26]. Tato metrika se vypoˇc´ıt´a podle vzorce 3.8 a ˇc´ım vyˇsˇs´ı hodnota, t´ım je klasifik´ator horˇs´ı. |D|
1 X |Yi ⊕ Zi | HammLoss = |D| i=1 |L|
(3.8)
Hodnota |D| vyjadˇruje poˇcet dokument˚ u v testovac´ı mnoˇzinˇe, Yi je mnoˇzina kategori´ı do kter´ ych ˇcl´anek patˇr´ı, Zi mnoˇzina kategori´ı do kter´ ych dokument zaˇradil klasifik´ator, |L| je velikost mnoˇziny do kter´ ych dokument patˇr´ı a ⊕ je symetrick´ y rozd´ıl dvou mnoˇzin neboli XOR operace zn´am´a z boolovsk´e logiky. Pokud napˇr´ıklad ˇcl´anek patˇr´ı do ˇctyˇr kategori´ı a klasifik´ator rozhodne o spr´avnosti zaˇrazen´ı do dvou, je Hammingova ztr´ata rovna hodnˇe 0.5, pokud vˇse klasifikuje spr´avnˇe, je hodnota nulov´a. Jedn´a se vlastnˇe o zobecnˇen´ı metriky Error Rate pro v´ıce kategori´ı, protoˇze pro klasifikaci do jedn´e kategorie je definice stejn´a.
3.3.7
Accurracy - pˇ resnost
Druhou metrikou, kterou vyuˇziji pro zhodnocen´ı u ´spˇeˇsnosti klasifikace do v´ıce kategori´ı je metrika Accuracy, pˇrekl´ad´ana t´eˇz jako pˇresnost. Protoˇze by ale mohlo doj´ıt k z´amˇenˇe s pˇresnost´ı jiˇz definovanou v´ yˇse, ponech´av´am anglick´ y n´azev. Metrika je pops´ana v [26] a definov´ana vzorcem 3.9. |D|
1 X |Yi ∩ Zi | Acc = |D| i=1 |Yi ∪ Zi |
(3.9)
Yi a Zi maj´ı stejn´ y v´ yznam jako v pˇredchoz´ım vzorci, tedy Yi je mnoˇzina kategori´ı do kter´ ych ˇcl´anek patˇr´ı a Zi mnoˇzina do kter´ ych n´am dokument zaˇradil klasifik´ator. ˇ C´ım vyˇsˇs´ı hodnota, t´ım byla klasifikace u ´spˇeˇsnˇejˇs´ı.
25
Kapitola 4 ˇ sen´ı klasifikaˇ Reˇ cn´ı u ´ lohy ˇ sen´ı bylo naprogramov´ano v programovac´ım jazyce Java jdk 1.7. Reˇ Kromˇe u ´prav n´astroje Minorthird tak, aby poskytoval v´ ysledky klasifikace v poˇzadovan´em form´atu, bylo potˇreba vytvoˇrit soubor tˇr´ıd, kter´e prov´ad´ı ˇcten´ı a parsov´an´ı vstupn´ıch XML soubor˚ u. D´ale bylo potˇreba vytvoˇrit tˇr´ıdy pro transformaci dat, pro lemmatizaci a POS-tagging, tˇr´ıdy filtruj´ıc´ı v´ ystupn´ı soubory z morfo1 logick´e anal´ yzy a tˇr´ıdy pro vytvoˇren´ı vstupn´ıch soubor˚ u pro klasifik´ator. Posledn´ı ˇc´ast´ı programov´eho ˇreˇsen´ı bylo vytvoˇren´ı GUI aplikace, ve kter´em je moˇzno klasifikovat jeden ˇcl´anek zkop´ırov´an´ım do okna aplikace, ˇci v´ıce ˇcl´ank˚ u naˇcten´ ych z XML souboru. V´ ysledek je opˇet zobrazen v oknˇe aplikace a vygenerov´an pˇr´ısluˇsn´ y v´ ystupn´ı XML soubor s pravdˇepodobnostn´ım zaˇrazen´ım ˇcl´anku do jednotliv´ ych kategori´ı.
4.1
N´ avrh aplikace
Program se zkl´ad´a z nˇekolika modul˚ u, kter´e jako celek tvoˇr´ı syst´em, umoˇzn ˇuj´ıc´ı pˇrevod XML soubor˚ u s novinov´ ymi ˇcl´anky na textov´e dokumenty vyuˇzit´e klasifikaˇcn´ım syst´emem MinorThird pro tr´enov´an´ı a klasifikaci. Kaˇzd´ y modul lze samostatnˇe spouˇstˇet a to s parametry popsan´ ymi v kapitole C.3. UML diagram nejd˚ uleˇzitˇejˇs´ıch komponent je zobrazen na obr´azku B.1 v pˇr´ıloze B. Prvn´ım modulem je modul preprocessing, kter´ y obsahuje metody pro pˇredzpracov´an´ı XML soubor˚ u pomoc´ı SAXu, parsuje naˇcten´e dokumenty a generuje vstupn´ı soubory pro morfologickou anal´ yzu ve form´atu CONLL (form´at CONLL pops´an v kapitole 4.5). D´ale tento modul spouˇst´ı lemmatizaci a POS-tagging z n´astroje MateTool. Dalˇs´ım modulem je modul featuresExtractor, kter´ y slouˇz´ı k naˇcten´ı v´ ystupn´ıch soubor˚ u z morfologick´e anal´ yzy. Obsah tˇechto soubor˚ u je filtrov´an podle POS tag˚ u uveden´ ych v konfiguraˇcn´ım souboru (viz pˇr´ıloha C.2). D´ale modul obsahuje metody pro spoˇc´ıt´an´ı statistiky v´ yskytu slov (lemmat) v jednotliv´ ych agenturn´ıch zpr´av´ach a napˇr´ıˇc kategoriemi. Z tˇechto statistik je pak podle vzorc˚ u pro jednotliv´e metody 1
V naˇsem pˇr´ıpadˇe jiˇz zmiˇ novan´ a lemmatizace a POS-tagging.
4.2 Struktura programu
26
v´ ybˇeru pˇr´ıznak˚ u vybr´an vektor slov, kter´ y bude pouˇzit pro klasifikaci. Hodnoty pˇr´ıznak˚ u jsou pot´e zaps´any do souboru (form´at v kapitole 4.6) pro klasifik´ator. Modul evaluation pak vyhodnocuje pˇr´ısluˇsn´ ymi metrikami v´ ystup klasifikace. Form´at soubor˚ u v´ ysledk˚ u klasifikace je pops´an v kapitole 4.7. Posledn´ım modulem je modul util, kter´ y obsahuje pomocn´e programy napˇr´ıklad pro v´ ypis statistik soubor˚ u s agenturn´ımi zpr´avami, prom´ıch´an´ı soubor˚ u a filtraci soubor˚ u podle identifik´atoru. D´ale implementuje program pro pˇrepoˇcten´ı v´ ysledk˚ u klasifikace vyj´adˇren´ ych koeficientem d˚ uvˇery na procentu´aln´ı u ´spˇeˇsnost pro Naivn´ı Bayes˚ uv klasifik´ator a klasifik´ator Maximum Entropy. Veˇsker´e moduly jsou pak propojeny programem Gui.java, ve kter´em lze vˇse konfigurovat z jednoho m´ısta. Kromˇe jin´eho umoˇzn ˇuje naˇcten´ı soubor˚ u s agenturn´ımi zpr´avami, naˇcten´ı v´ ysledk˚ u klasifikace, jejich proch´azen´ı v pˇrehledn´em oknˇe a ukl´ad´an´ı upraven´ ych v´ ysledk˚ u. D´ale umoˇzn ˇuje natr´enovat vybran´ y klasifik´ator a klasifikovat ˇcl´anky na tomto natr´enovan´em modelu.
4.2
Struktura programu
Program m˚ uˇzeme rozdˇelit do nˇekolika bal´ık˚ u obsahuj´ıc´ı tˇr´ıdy podle jejich funkce. Vˇsechny tˇr´ıdy vyuˇz´ıvaj´ı konfiguraˇcn´ı Java properties soubor, kter´ y se defaultnˇe jmenuje ”properties.properties”. Tento soubor jde pro kaˇzdou tˇr´ıdu zamˇenit za jin´ y, pomoc´ı voliteln´eho parametru. V´ yznam poloˇzek properties souboru je vysvˇetlen v pˇr´ıloze C.2, pˇr´ıklady spuˇstˇen´ı pak v pˇr´ıloze C.3. Seznam a v´ yznam spustiteln´ ych tˇr´ıd je zobrazen v n´asleduj´ıc´ı seznamov´e struktuˇre. Tˇr´ıdy, kter´e neimplementuj´ı main metodu zde popisov´any nebudou, jejich popis lze naj´ıt v javadoc dokumentaci na pˇriloˇzen´em DVD. • preprocessing: Preprocessing.java - obsahuje SAX parser vstupn´ıch XML soubor˚ u, filtruje 2 slova (termy) podle properties souboru a generuje soubor v Conll form´atu pro morfologickou anal´ yzu. Lemmatization.java - tˇr´ıda spouˇstˇej´ıc´ı n´astroj Mate tool, kter´ y provede lemmatizaci. POSTagging.java - tˇr´ıda spouˇstˇej´ıc´ı n´astroj Mate tool pro POS tagging. • featuresExtractor: FeaturesExtracor.java - tˇr´ıda naˇc´ıt´a v´ ystupn´ı soubory tˇr´ıd v bal´ıku preprocessing a podle properties souboru a parametr˚ u pˇr´ıkazov´e ˇra´dky generuje vstup pro klasifik´ator.
2
Conference on Computational Natural Language Learning - http://www.clips.ua.ac.be/conll/
4.3 GUI aplikace
27
• evaluation: Evaluation.java - tˇr´ıda naˇc´ıt´a v´ ystup klasifik´atoru, vyhodnocuje u ´spˇeˇsnost pro Multi-label klasifikaci metrikami Hamming Loss a Accuracy. Z´aroveˇ n vrac´ı optim´aln´ı parametr k automatick´emu pˇriˇrazen´ı spr´avn´ ych predikovan´ ych kategori´ı. • utils: Statistics.java - vrac´ı statistick´e informace lemmatizovan´eho a POS tagovan´eho souboru. Shuffle.java - prom´ıch´a ˇcl´anky ve v´ ystupn´ım souboru z tˇr´ıd bal´ıku preprocessing. Prom´ıch´an´ı souboru nen´ı nezbytnˇe nutn´e prov´adˇet. Je pouˇzito proto, aby tˇr´ıdy v souboru byly rovnomˇernˇe rozloˇzen´e. FiltrationOrderID.java - ponech´a z v´ ystupn´ıch soubor˚ u tˇr´ıd bal´ıku preprocessing pouze ˇcl´anky definovan´e ve zvl´aˇstn´ım soubor˚ u obsahuj´ıc´ı id ponech´avan´ ych dokument˚ u. ConvertXMLResults.java - pˇrevede soubory s u ´spˇeˇsnostmi klasifikace vyj´adˇren´ ymi koeficientem d˚ uvˇery na procentu´aln´ı u ´spˇeˇsnost. • gui: Gui.java - vykresl´ı GUI aplikace, ve kter´em lze prov´adˇet vˇsechny pˇredchoz´ı zm´ınˇen´e akce z centr´aln´ıho m´ısta. GUI aplikace je pops´ano v kapitole 4.3.
4.3
GUI aplikace
Uˇzivatelsk´e prostˇred´ı je zobrazeno na obr´azku 4.1 s podrobnˇejˇs´ım vysvˇetlen´ım n´ıˇze. Ovl´ad´an´ı programu je intuitivn´ı, proto zde nebudou pops´any vˇsechny funkce, kter´e poskytuje. V´ yznam oˇc´ıslovan´ ych komponent v GUI aplikace je n´asleduj´ıc´ı: • 1. Zobrazuje vˇsechna ID ˇcl´ank˚ u, kter´a byla naˇcten´a pomoc´ı Load XML z menu aplikace. Toto okno je zobrazeno pouze pokud vstupn´ı XML soubor obsahuje v´ıce neˇz jeden ˇcl´anek. Po kliknut´ı na konkr´etn´ı ID je zobrazen pˇr´ısluˇsn´ y ˇcl´anek v komponentˇe ˇc´ıslo 2. • 2. Zobrazuje ˇcl´anek po kliknut´ı na ID, umoˇzn ˇuje vloˇzit jak´ ykoliv vlastn´ı text ˇci zobrazuje ˇcl´anek naˇcten´ y z XML souboru. ˇ ıseln´a hodnota ve druh´em sloupci tabulky • 3. Zobrazen´ı v´ ysledku klasifikace. C´ ud´av´a procentu´aln´ı u ´spˇeˇsnost pro kategorii zobrazenou v prvn´ım sloupci. Tˇret´ı sloupec pak umoˇzn ˇuje uˇzivateli aplikace vlastn´ı v´ ybˇer kategori´ı. • 4. Logov´an´ı aplikace, zobrazuje prov´adˇen´e akce s ˇcasov´ ym raz´ıtkem. Logov´an´ı je z´aroveˇ n provedeno i do souboru log.txt
4.3 GUI aplikace
28
Obr´azek 4.1: GUI aplikace • 5. Klasifikuje pr´avˇe zobrazen´ y ˇcl´anek v oknˇe ˇc. 2. a meziv´ ysledky ukl´ad´a do soubor˚ u definovan´ ych v properties souboru. • 6. Klasifikuje vˇsechny naˇcten´e ˇcl´anky. • 7. Vybere nejpravdˇepodobnˇejˇs´ı kategorie na z´akladˇe ∆3 parametru uveden´eho v konfiguraci. • 8. Uloˇz´ı vybran´e kategorie do XML souboru ve form´atu popsan´em v druh´e ˇca´sti kapitoly 4.7. • 9. V´ ybˇer klasifik´atoru. • 10. ID ˇcl´anku, kter´ y je pr´avˇe zobrazen. Po spuˇstˇen´ı obsahuje n´ahodnˇe vygenerovanou hodnotu a pod touto hodnotou jsou takt´eˇz v´ ysledky uloˇzeny. • 11. Po v´ ybˇeru Settings z menu aplikace je zobrazena nab´ıdka, kde m˚ uˇzeme prov´est konfiguraci aplikace v´ ybˇerem poloˇzky Options a nebo natr´enovat poˇzadovan´ y klasifik´ator. Po v´ ybˇeru poloˇzky tr´enov´an´ı je zobrazeno okno na obr´azku 4.2. Tr´enov´an´ı zapoˇcne stiskem tlaˇc´ıtka OK, pr˚ ubˇeˇzn´e logy jsou vypisov´any do konzolov´eho okna (bod 4). 3ˇ
C´ıseln´ a hodnota ud´ avaj´ıc´ı prahovou hodnotu pro urˇcen´ı spr´avn´ ych tˇr´ıd z v´ ystupu klasifik´atoru. Pokud je rozd´ıl po sobˇe jdouc´ıch tˇr´ıd menˇs´ı neˇz ∆, je tˇr´ıda urˇcena jako spr´avn´a.
4.4 V´ ystup parseru
29
• 12. V´ ybˇerem Load xml z menu aplikace provedeme naˇcten´ı novinov´ ych ˇcl´ank˚ u do aplikace. Pokud uˇz m´ame k dispozici v´ ysledky klasifikace, m˚ uˇzeme tento soubor takt´eˇz nahr´at v´ ybˇerem poloˇzky Load results. Po kliknut´ı na identifik´ator ˇcl´anku v lev´em panelu je na pravo zobrazen pˇr´ısluˇsn´ y v´ ysledek klasifikace, kter´ y lze libovolnˇe mˇenit a zmˇeny potvrdit tlaˇc´ıtkem Save.
Obr´azek 4.2: Okno pro nastaven´ı parametr˚ u tr´enov´an´ı klasifik´atoru
4.4
V´ ystup parseru
Protoˇze ˇcl´anky obsahuj´ı ve sv´em textu HTML tagy, kter´e n´as nezaj´ımaj´ı, jsou pˇri parsov´an´ı automaticky odstranˇeny pomoc´ı regul´arn´ıho v´ yrazu. V´ ystupn´ı soubor parseru m´a n´asleduj´ıc´ı strukturu: 1 2 3 4 5 6 7 8
T201105010090101 : k a t Z e me tr e s e n o s l e 54 stupne z a s a h l o Kazachsta n
kat
Kaˇzd´ y ˇr´adek souboru se skl´ad´a ze dvou sloupc˚ u oddˇelen´ ych tabul´atorem. Prvn´ı sloupec ud´av´a poˇrad´ı slova v dokumentu, druh´ y sloupec slovo. Vyj´ımku tvoˇr´ı prvn´ı ˇra´dek kaˇzd´eho ˇcl´anku, kter´ y m´ısto slova obsahuje identifik´ator ˇcl´anku, za dvojteˇckou hlavn´ı kategorii a za dvˇema podtrˇz´ıtky vˇsechny kategorie, do kter´ ych ˇcl´anek patˇr´ı. Jednotliv´e ˇcl´anky jsou v dokumentu oddˇeleny pr´azdnou ˇra´dkou a pro kaˇzd´ y dokument zaˇc´ın´a ˇc´ıslov´an´ı v prvn´ım sloupci od hodnoty jedna. Soubor je navrˇzen tak, aby byl kompatibiln´ı s form´atem CONLL 2009 podrobnˇeji popsan´em v [23]. S t´ımto souborem pracuj´ı algoritmy morfologick´e anal´ yzy implementovan´e v n´astroji MateTool.
4.5 Morfologick´a anal´ yza
4.5
30
Morfologick´ a anal´ yza
Tr´ enov´ an´ı n´ astroje MateTool Tr´enovac´ı soubor pro morfologickou anal´ yzu je ve form´atu CONLL 2009 a m´a n´asleduj´ıc´ı strukturu: 1 2 3 4 5 6
Zatm vs ak k nemu n e d os l o a
zatm vs ak k−1 on−1 d o j t a−1
zatm vs ak k−1 on−1 d o j t a−1
D J R P V J
D J R P V J
V´ yznam prvn´ıho a druh´eho sloupeˇcku je stejn´ y jako v pˇredchoz´ı kapitole, tedy prvn´ı sloupeˇcek ud´av´a poˇrad´ı slova v dokumentu, druh´ y slovo. Tˇret´ı a ˇctvrt´ y sloupeˇcek oznaˇcuje lemma a posledn´ı dva sloupeˇcky slovn´ı druh, tedy POS tag. V´ yznam POS tag˚ u je uveden v kapitole 2.2.1. V´ ystup morfologick´ e anal´ yzy V´ ystup morfologick´e anal´ yzy je takt´eˇz jako vstup ve form´atu CONLL 2009. Form´at je podobn´ y jako tr´enovac´ı soubor v kapitole 4.5, pouze jsou v nˇem vynech´any nˇejak´e sloupeˇcky podle toho, zda jsme prov´adˇeli lemmatizaci nebo POS-tagging.
4.6
Vstup klasifik´ atoru
Form´at vstupn´ıho souboru pro klasifik´ator je ve tvaru: k k k k
reklamn =0.4495255053164 reklama =0.407131762840 nemocnice =0.5237997805152 a k u t n =0.401031908799 ekonomika =0.5120925109851 cn s k y =0.276210879360 kscm =0.40702740711870 k o n f l i k t =0.26838959499898
Prvn´ı pˇr´ıznak m˚ uˇze nab´ yvat dvou hodnot a to b pro bin´arn´ı klasifikaci 4 a k pro klasifikaci do v´ıce tˇr´ıd. V naˇsem pˇr´ıpadˇe bude hodnota vˇzdy k. Druh´e slovo obsahuje identifik´ator dokumentu. Tˇret´ı slovo oznaˇcuje kategorii do kter´e ˇcl´anek skuteˇcnˇe patˇr´ı. Pokud ˇcl´anek patˇr´ı do v´ıce kategori´ı, bude se cel´a ˇr´adka opakovat, pouze s touto zmˇenˇenou hodnotou. Za kategoriemi n´asleduj´ı samotn´e pˇr´ıznaky ve tvaru slovo=v´ aha oddˇelen´e mezerou. Pokud v´aha slova nen´ı uvedena, je automaticky rovna hodnotˇe jedna.
4
Klasifikace do dvou tˇr´ıd.
4.7 V´ ystup klasifik´atoru
4.7
31
V´ ystup klasifik´ atoru
Pro tuto u ´lohu bylo nutn´e pˇrizp˚ usobit n´astroj Minorthird tak, aby vracel pravdˇepodobnosti zaˇrazen´ı do vˇsech tˇr´ıd a ne jen jednu tˇr´ıdu. Takto upraven´ y n´astroj je k dispozici na pˇriloˇzen´em DVD, stejnˇe jako veˇsker´e v´ ystupy prov´adˇen´ ych experiment˚ u. N´astroj byl upraven tak, aby poskytoval dva moˇzn´e v´ ystupy. Prvn´ı v´ ystup Prvn´ım v´ ystupem je soubor, kter´ y m´a n´asleduj´ıc´ı strukturu: Class1 Class1 : 2 Class2 : 1 Class3 : 0 ...
Class2 0 1 2
Class3 0 1 0
−−−− e r r o r Rate : 0.121223 e r r o r Rate C l a s s 1 : 0 ... Kappa : 0.879908
−−−− [ Class1 , Class2 , C l a s s 3 ] ID1 C l a s s 1 [ C l a s s 1 =0.6450 , C l a s s 2 =0.2828 , C l a s s 3 =0.0153] C l a s s 1 ID2 C l a s s 2 [ C l a s s 2 =0.8234 , C l a s s 1 =0.7775 , C l a s s 3 =0.0736] C l a s s 1 ...
V prvn´ı ˇca´sti dokumentu je zobrazena konfuzn´ı matice, kter´a zobrazuje poˇcet spr´avnˇe/ˇspatnˇe klasifikovan´ ych ˇcl´ank˚ u. N´asleduje vypoˇcten´ı u ´spˇeˇsnosti klasifikace metrikou error rate pro celou testovac´ı mnoˇzinu, pro jednotliv´e kategorie a u ´spˇeˇsnost klasifikace metrikou Kappa. Posledn´ı ˇca´st´ı dokumentu jsou podrobnˇejˇs´ı v´ ysledky a zaˇrazen´ı jednotliv´ ych ˇcl´ank˚ u do kategori´ı. Prvn´ı ˇra´dka obsahuje seznam vˇsech kategori´ı vyskytuj´ıc´ıch se v testovac´ı mnoˇzinˇe. Kaˇzd´a dalˇs´ı ˇr´adka odpov´ıd´a jednomu klasifikovan´emu dokuˇ adka zaˇc´ın´a identifik´atorem dokumentu, n´asleduje predikovan´a tˇr´ıda, v mentu. R´ hranat´ ych z´avork´ach seˇrazen´e tˇr´ıdy podle nejpravdˇepodobnˇejˇs´ı a konˇc´ı tˇr´ıdou, do kter´e dokument skuteˇcnˇe patˇr´ı. Pravdˇepodobnost predikovan´ ych tˇr´ıd je pouze u SVM klasifik´atoru, pro ostatn´ı klasifik´atory je pravdˇepodobnost vyj´adˇrena koeficientem d˚ uvˇery.
4.7 V´ ystup klasifik´atoru
32
Druh´ y v´ ystup Druh´ ym v´ ystupem je XML soubor s n´asleduj´ıc´ı strukturou, <document> <doc i d =”953565” r e a l C a t e g o r y=”−”> 0.2818557290317149 0.1794240811363971 0.1794240811363971 ... ve kter´em je kaˇzd´ y dokument jednoznaˇcnˇe identifikov´an podle id a obsahuje XML elementy s predikovan´ ymi kategoriemi a jejich pravdˇepodobnostmi seˇrazen´e podle nejpravdˇepodobnˇejˇs´ı. Stejnˇe jako u pˇredchoz´ıho form´atu prvn´ıho v´ ystupu je pro klasifik´ator SVM pouˇzita pravdˇepodobnost a pro zbyl´e klasifik´atory koeficient d˚ uvˇery. Soubory s t´ımto koeficientem d˚ uvˇery lze pˇrev´est na soubory s vyj´adˇren´ım pravdˇepodobnosti pomoc´ı programu ConvertXMLResults.java bal´ıku utils.
33
Kapitola 5 Dosaˇ zen´ e v´ ysledky Pokud nen´ı uvedeno jinak, vˇsechny klasifik´atory byly tr´enov´any na mnoˇzinˇe obsahuj´ıc´ı 425 +/- 175 ˇcl´ank˚ u v kaˇzd´e kategorii. Toto omezen´ı jsem aplikoval z d˚ uvodu, aby byly tˇr´ıdy vyv´aˇzen´e a v´ ysledky nebyly zkreslen´e. Experiment´alnˇe bylo zjiˇstˇeno, ˇze vˇetˇs´ı poˇcet ˇcl´ank˚ u jiˇz nem´a na u ´spˇeˇsnost klasifikace vliv. U v´ıcetˇr´ıdn´ı klasifikace se vyvaˇzovalo pouze podle prvn´ı kategorie, nicm´enˇe i pˇres toto opatˇren´ı mˇely ˇcast´e kategorie jako napˇr´ıklad politika v´ıce ˇcl´ank˚ u. Na z´akladˇe pˇreˇcten´ ych prac´ı jsem se rozhodl vyzkouˇset celkem tˇri klasifik´atory, Naivn´ı Bayes˚ uv klasifik´ator, SVM a Maximum Entropy. Klasifik´atory byly vyb´ır´any podle nejpouˇz´ıvanˇejˇs´ıch a podle toho, jak´e u ´spˇeˇsnosti dosahovaly. Pokud bych mˇel srovnat u ´spˇeˇsnosti, nejlepˇs´ıch v´ ysledk˚ u by mˇel dosahovat klasifik´ator SVM a nejhorˇs´ıch v´ ysledk˚ u Naivn´ı Bayes˚ uv klasifik´ator. Samozˇrejmˇe nelze na z´akladˇe literatury pˇresnˇe srovnat v´ ysledky, protoˇze kaˇzd´ y ˇcl´anek pouˇz´ıval jin´e nastaven´ı klasifik´ator˚ u, r˚ uzn´e metody v´ ybˇeru pˇr´ıznak˚ u a byly pouˇz´ıv´any pro r˚ uzn´e poˇcty tˇr´ıd a jin´e druhy/mnoˇzstv´ı klasifikovan´ ych dokument˚ u. Pro v´ ybˇer vhodn´ ych pˇr´ıznak˚ u byly pouˇzity bˇeˇznˇe pouˇz´ıvan´e metody: Dokumentov´a frekvence, Mutual information, Information Gain, Chi-kvadr´at test a metoda GSS popsan´e v kapitole 2.3. Pro vyhodnocen´ı v´ ysledk˚ u byly v pˇr´ıpadˇe klasifikace do jedn´e kategorie pouˇzity metriky Error rate a Kappa statistika a pro pˇr´ıpad klasifikace do v´ıce kategori´ı pak Hammingova metrika a Accuracy (vˇse popsan´e v kapitole 3.3). Tyto metriky vyhodnocen´ı u ´spˇeˇsnosti klasifikace jsou bˇeˇznˇe pouˇz´ıv´any pro tento typ u ´lohy a Error rate a Kappa statistika byly jiˇz implementov´any v klasifikaˇcn´ım syst´emu, kter´ y byl pouˇzit. Veˇsker´e v´ ysledky experiment˚ u poch´azej´ı z kˇr´ıˇzov´e validace a to v pomˇeru 1:5. Tedy soubor s pˇr´ıznakov´ ymi vektory byl rozdˇelen na 5 stejn´ ych ˇc´ast´ı, kdy pro tr´enovan´ı byly pouˇzity 4/5 a pro testov´an´ı zb´ yvaj´ıc´ı ˇc´ast. Celkem tedy byla klasifikace pro kaˇzd´ y experiment spuˇstˇena 5x pro vˇsechny tr´enovac´ı kombinace a otestov´ana zb´ yvaj´ıc´ı ˇc´ast´ı. V´ ysledky kˇr´ıˇzov´e validace jsou zobrazeny v tabulk´ach obsaˇzen´ ych v podkapitol´ach n´ıˇze. Kˇr´ıˇzov´a validace je jiˇz implementov´ana v klasifikaˇcn´ım syst´emu.
5.1 Urˇcen´ı velikosti pˇr´ıznakov´eho vektoru
5.1
34
Urˇ cen´ı velikosti pˇ r´ıznakov´ eho vektoru
V t´eto kapitole jsou zobrazeny v´ ysledky vlivu velikosti vektoru pˇr´ıznak˚ u na u ´spˇeˇsnost klasifikace pro r˚ uzn´e metody v´ ybˇeru pˇr´ıznak˚ u. Pˇredem nutno zopakovat, ˇze vektor obsahuje mnoˇzinu slov spoleˇcnou pro vˇsechny kategorie, tedy testovac´ı soubor bude obsahovat pouze slova obsaˇzen´a v tomto vektoru, stejnˇe jako tr´enovac´ı soubor. Pro testovac´ı soubor je vektor slov naˇc´ıt´an ze souboru, kter´ y byl vytvoˇren pˇri vytv´aˇren´ı souboru pro tr´enov´an´ı klasifik´atoru. Na z´akladˇe v´ ysledk˚ u tˇechto experiment˚ u byly zvoleny velikosti pˇr´ıznakov´ ych vektor˚ u pro kaˇzd´ y klasifik´ator, kter´e budou pouˇzity v n´asleduj´ıc´ıch experimentech, vˇcetnˇe rozpozn´av´an´ı do v´ıce kategori´ı. Na z´akladˇe doporuˇcen´e literatury byla stanovena poˇca´teˇcn´ı konfigurace klasifik´atoru, kter´a by mˇela poskytovat nejlepˇs´ı v´ ysledky. V tomto testu byla pouˇzita lemmatizace (podle [19]) a filtrov´an´ı podle POS tag˚ u. Tr´enovac´ı / testovac´ı vektory obsahovaly pouze slova, jejichˇz POS tagy odpov´ıdaly podstatn´ ym jm´en˚ um, pˇr´ıdavn´ ym jm´en˚ um, pˇr´ıslovc˚ um a sloves˚ um (odpov´ıdaj´ıc´ı POS zkratk´am N, A, D, V ). Ostatn´ı slovn´ı druhy byly vynech´any, protoˇze by mˇely b´ yt pro klasifikaci irelevantn´ı, jak se lze doˇc´ıst napˇr´ıklad v [17] nebo ve [3], kde dokonce pouˇz´ıvaj´ı pouze podstatn´a jm´ena. V´ ysledky experimentu pro Naivn´ı Bayes˚ uv klasifik´ator jsou zobrazeny v % v tabulce 5.1, kde v prvn´ım sloupci je zobrazena d´elka pˇr´ıznakov´eho vektoru. Poloˇzka all v tomto sloupci znaˇc´ı, ˇze d´elka vektoru nebyla nijak omezena. Pro toto nastaven´ı by mˇely vˇsechny metody v´ ybˇeru pˇr´ıznak˚ u poskytovat stejn´e v´ ysledky, jelikoˇz vˇsechny poskytuj´ı vektor obsahuj´ıc´ı vˇsechna slova. Graf zobrazuj´ıc´ı z´avislost velikosti pˇr´ıznakov´eho vektoru na u ´spˇeˇsnost klasifikace pro jednotliv´e metody v´ ybˇeru pˇr´ıznak˚ u vyhodnocen´e metrikou Error rate je zobrazen klesaj´ıc´ımi kˇrivkami na obr´azku 5.1. Metrikou Kappa pak stejn´ ym grafem, rostouc´ımi kˇrivkami. Pro zb´ yvaj´ıc´ı dva klasifik´atory jsou grafy a tabulky obdobn´e. Pro klasifik´ator SVM jsou d´any tabulkou 5.2 a grafem na obr´azku 5.2, pro klasifik´ator Maximum Entropy pak tabulkou 5.3 a grafem 5.3.
5.1 Urˇcen´ı velikosti pˇr´ıznakov´eho vektoru
5.1.1
35
Naivn´ı Bayes˚ uv klasifik´ ator Metody v yb eru p r znak u [v ysledky v %]
velikost vektoru 50 100 200 500 1000 1500 2000 3000 4000 5000 6000 7000 all
Tabulka 5.3: Vliv velikosti pˇr´ıznakov´eho vektoru na u ´spˇeˇsnost klasifikace pro klasifik´ator Maximum Entropy
Vliv velikosti příznakového vektoru
[%] 100 90
DF Err. Rate
80
MI Err. Rate 70
IG Err. Rate CHI2 Err. Rate
60
GSS Err. Rate 50
DF Kappa
40
MI Kappa IG Kappa
30
CHI2 Kappa GSS Kappa
20 10 0
50
100
200
500 1000 1500 2000 3000 4000 5000 6000 7000
all
Obr´azek 5.3: Graf z´avislosti velikosti pˇr´ıznakov´eho vektoru na u ´spˇeˇsnost klasifikace pro klasifik´ator Maximum Entropy
5.2 V´ ybˇer vhodn´ ych POS tag˚ u
38
Zhodnocen´ı Nejhorˇs´ı v´ ysledky, dle oˇcek´av´an´ı poskytoval Bayes˚ uv klasifik´ator. Z graf˚ u je vidˇet, ˇze jeho Error rate kˇrivky jsou posunuty zhruba o 5% k niˇzˇs´ı u ´spˇeˇsnosti, nicm´enˇe ˇcas tr´enov´an´ı modelu byl oproti ostatn´ım klasifik´ator˚ um v´ yraznˇe kratˇs´ı (ˇra´dovˇe minuty). Naopak klasifik´atory SVM a Maximum Entropy dosahovaly podobn´ ych v´ ysledk˚ u, liˇsily se ˇra´dovˇe pouze o desetiny procent. Tr´enov´an´ı model˚ u pak trvalo ˇra´dovˇe hodiny, pˇriˇcemˇz klasifik´ator Maximum Entropy pak pˇribliˇznˇe trojn´asobnˇe delˇs´ı dobu oproti SVM. D´ale je z graf˚ u vidˇet, ˇze ˇc´ım delˇs´ı je d´elka vektoru, t´ım podobnˇejˇs´ı jsou v´ ysledky klasifikace pro jednotliv´e metody v´ ybˇeru pˇr´ıznak˚ u. Tato vlastnost je d´ana pˇredevˇs´ım velk´ ym poˇctem tˇr´ıd do kter´ ych klasifikujeme, protoˇze metody v´ ybˇeru pˇr´ıznak˚ u mohou preferovat slova jen z nˇejak´e mal´e vybran´e mnoˇziny tˇr´ıd. Na z´akladˇe v´ ysledk˚ u byla jako kompromis mezi ˇcasovou n´aroˇcnost´ı tr´enov´an´ı modelu a obdrˇzen´ ymi v´ ysledky stanovena n´asleduj´ıc´ı d´elka vektoru. Pro Bayes˚ uv klasifik´ator byl zvolen vektor d´elky 4000, pro zb´ yvaj´ıc´ı klasifik´atory se uk´azala jako vhodn´a d´elka 3000. N´asleduj´ıc´ı experimenty, pokud nebude ˇreˇceno jinak, jsou prov´adˇeny s t´ımto nastaven´ım, i kdyˇz se pravdˇepodobnosti jeˇstˇe o nˇeco m´alo zlepˇsuj´ı.
5.2
V´ ybˇ er vhodn´ ych POS tag˚ u
Dalˇs´ım prov´adˇen´ ym experimentem bylo zjiˇst’ov´an´ı, jak´ ym zp˚ usobem POS tagy ovlivˇ nuj´ı u ´spˇeˇsnost klasifikace. V tabulk´ach jsou uvedeny v´ ysledky klasifikace v % pro vˇsechny kombinace POS tag˚ u N, A, V, D, pˇriˇcemˇz podstatn´a jm´ena (N), jako ´ eˇsnosti slovn´ı druh ovlivˇ nuj´ıc´ı klasifikaci nejv´ıce (viz [3]), jsou pouˇzita vˇzdy. Uspˇ jednotliv´ ych klasifik´ator˚ u jsou vyneseny do graf˚ u v z´avislosti na pouˇzit´ ych kombinac´ıch POS tag˚ u. Kˇrivky u ´spˇeˇsnosti jsou stejn´e pro oba grafy pouˇzit´ ych metrik. D´elky vektor˚ u byly pouˇzity dle v´ ysledk˚ u z pˇredchoz´ı kapitoly.
5.2 V´ ybˇer vhodn´ ych POS tag˚ u
5.2.1
39
Naivn´ı Bayes˚ uv klasifik´ ator
V´ ysledky experimentu jsou zobrazeny v tabulce 5.4 a vyneseny na grafu 5.4. Metody v yb eru p r znak u [v ysledky v %]
Tabulka 5.6: Vliv kombinace POS tag˚ u na v´ ysledky klasifikace pro klasifik´ator Maximum Entropy
[%] 12,6
Error rate
[%] 88,9
Kappa
12,25
88,5
11,9
88,1
11,55
87,7
11,2
87,3
CHI2 Kappa
10,85
86,9
GSS Kappa
10,5
86,5
DF Kappa MI Kappa IG Kappa
Obr´azek 5.6: Graf z´avislosti kombinace POS tag˚ u na v´ysledky klasifikace pro klasifik´ator Maximum Entropy
Zhodnocen´ı Z graf˚ u pro jednotliv´e klasifik´atory je vidˇet, ˇze o nˇeco m´alo lepˇs´ı je volit kombinaci bez sloves oproti prvn´ımu experimentu v kapitole 5.1, tedy kombinaci s ponech´an´ım podstatn´ ych jmen, pˇr´ıdavn´ ych jmen a pˇr´ıslovc´ı (N, A, D). Veˇsker´e n´asleduj´ıc´ı experimenty budou prov´adˇeny s kombinac´ı tˇechto POS tag˚ u. D´ale se uk´azalo, ˇze nejlepˇs´ı je volit pro v´ ybˇer pˇr´ıznak˚ u metodu Mutual Information, kter´a dosahovala v pˇrev´aˇzn´e vˇetˇsinˇe experiment˚ u nepatrnˇe lepˇs´ıch v´ ysledk˚ u (pˇribliˇznˇe 0,5 % oproti dalˇs´ı nejlepˇs´ı). Nejlepˇs´ıch v´ ysledk˚ u bylo dosaˇzeno klasifik´atorem Maximum Entropy, kter´ y mˇel pˇribliˇznˇe o p˚ ul procenta lepˇs´ı u ´spˇeˇsnost neˇz klasifik´ator SVM. Naopak nejhorˇs´ı v´ ysledek mˇel Naivn´ı Bayes˚ uv klasifik´ator, kde byl rozd´ıl cca 7 %.
5.3 Vliv lemmat na u ´spˇeˇsnost klasifikace
5.3
42
Vliv lemmat na u ´ spˇ eˇ snost klasifikace
Tato kapitola zobrazuje v´ ysledky experimentu, pˇri kter´em byl zkoum´an vliv lemmat na u ´spˇeˇsnost klasifikace. V´ ysledky experimentu jsou zobrazeny v tabulce 5.7 a vyneseny do grafu 5.7. Druh´ y sloupec tabulky znaˇc´ı, zda byla v testu pouˇzita lemmata (znaˇcka ’l’ ) nebo slova (znaˇcka ’w’ ). Tento experiment zkoum´a pˇredpoklad, ˇze pouˇzit´ı lemmat poskytuje lepˇs´ı v´ ysledky neˇz pˇri pouˇzit´ı slov. V 1. experimentu (viz kapitola 5.1) byla na z´akladˇe tohoto pˇredpokladu pouˇzita lemmata rovnou. Metoda v yb eru p r znak u [v ysledky v %]
Tabulka 5.7: Vliv lemmat na u ´spˇeˇsnost klasifikace pro jednotliv´e klasifik´atory
Error Rate
Kappa Úspěšnost [%]
Úspěšnost [%] 19
88
17
86
15
84
13
82
11 9 DF
MI IG CHI2 GSS Metoda příznaků
Bayes slovo Bayes lemma MaxEnt slovo MaxEnt lemma SVM slovo SVM lemma
80 78 DF MI IG CHI2 GSS Metoda příznaků
SVM lemma SVM slovo MaxEnt lemma MaxEnt slovo Bayes lemma Bayes slovo
Obr´azek 5.7: Graf zobrazuj´ıc´ı vliv lemmat na u ´spˇeˇsnost klasifikace
Zhodnocen´ı Z tabulky 5.7 ˇci grafu 5.7 je vidˇet, ˇze pouˇzit´ı lemmat m´a drobn´ y vliv na u ´spˇeˇsnost ´ klasifikace. Uspˇeˇsnost se zlepˇsila pˇribliˇznˇe o 1%. Pokud se pod´ıv´ame do kapitoly
5.4 Klasifikace do hlavn´ı kategorie
43
3.2.4 na statistiku korpusu, vid´ıme, ˇze lemmatizace n´am poˇcet unik´atn´ıch slov zredukovala pˇribliˇznˇe o 20%, coˇz pˇri v´ ybˇeru vektoru slov o velikosti 3000 z mnoˇziny obsahuj´ıc´ı zhruba 150 000 slov je zanedbateln´e. Vzhledem k alespoˇ n drobn´emu zlepˇsen´ı u ´spˇeˇsnosti rozpozn´av´an´ı bude lemmatizace pouˇzita i v n´asleduj´ıc´ıch experimentech a bude z´aleˇzet na uˇzivateli aplikace, zda bude lemmatizaci vyuˇz´ıvat ˇci nikoliv.
5.4
Klasifikace do hlavn´ı kategorie
V tabulce 5.8 jsou uvedeny v´ ysledky klasifikace v procentech pˇri pouˇzit´ı r˚ uzn´ ych klasifik´ator˚ u pˇri optim´aln´ım v´ ybˇeru d´elky pˇr´ıznakov´eho vektoru z kapitoly 5.1 a pˇri neomezen´e d´elce pˇr´ıznakov´eho vektoru. D´ale byla pouˇzita lemmata a byly ponech´any pouze POS tagy (N, A, D), kter´e jak se uk´azalo v kapitole 5.2, dosahovaly nejlepˇs´ıch v´ ysledk˚ u. D´ale jsem se omezil jen na v´ ybˇer pˇr´ıznak˚ u pomoc´ı Mutual Information (MI) parametrizace, protoˇze v pˇredchoz´ım testov´an´ı pˇredˇcila ostatn´ı metody. Delka vektoru: Klasi kator: Error. rate Kappa
4000 Bayess 17,26 81,96
3000 SVM 10,78 88,73
3000 MaxEnt 10,92 88,58
neomezena Bayess 13,94 85,42
neomezena SVM 8,79 90,81
neomezena MaxEnt 9,1 90,48
´ eˇsnost klasifikace pro hlavn´ı kategorii pˇri pouˇzit´ı parametrizace MI Tabulka 5.8: Uspˇ vyhodnocen´a metrikou Error rate a Kappa
Zhodnocen´ı Z v´ ysledk˚ u je vidˇet, ˇze nejlepˇs´ı v´ ysledek poskytoval klasifik´ator SVM na neomezen´e d´elce vektoru. Nicm´enˇe pokud velikost omez´ıme na 3000 slov, u ´spˇeˇsnost se pˇr´ıliˇs nezhorˇs´ı a pomˇer cena / v´ykon v´ yraznˇe vzroste. Je nutn´e si uvˇedomit, ˇze tr´enov´an´ı modelu 1 na neomezen´e d´elce vektoru je ˇcasovˇe mnohem n´aroˇcnˇejˇs´ı, trv´a zhruba ˇ trojn´asobn´ y ˇcas oproti omezen´e d´elce. Casov´ a n´aroˇcnost tr´enov´an´ı model˚ u pro klasifikaci do v´ıce kategori´ı je v tabulce 5.12, pro klasifikaci do jedn´e kategorie je ˇcas zhruba 3x menˇs´ı.
5.5
Klasifikace do v´ıce kategori´ı
Pro vyhodnocen´ı u ´spˇeˇsnosti klasifikace do v´ıce kategori´ı jsem pouˇzil metriky Hamming loss a metriku Accuraccy popsan´e v kapitole 3.3. Velikost pˇr´ıznakov´eho vektoru byla pouˇzita stejn´a jako pˇri klasifikaci do jedn´e kategorie v pˇredchoz´ı kapitole 5.4. Testy jsem prov´adˇel pouze pro metodu v´ ybˇeru pˇr´ıznak˚ u MI, protoˇze ve vˇsech pˇredchoz´ıch testech dosahovala nejlepˇs´ıch v´ ysledk˚ u. V´ ysledky jsou zobrazeny v tabulce 5.9. 1
Tr´enov´ an´ı modelu prov´ adˇeno na stroji s konfigurac´ı v tabulce 5.11
´ eˇsnost klasifikace pro vˇsechny kategorie pˇri pouˇzit´ı parametrizace Tabulka 5.9: Uspˇ MI vyhodnocen´a metrikou Hamming Loss a Accuracy D´ale byly obdrˇzen´e v´ ysledky z klasifik´atoru vyhodnoceny se zahrnut´ım jedn´e kategorie nav´ıc, neˇz do kolika ˇcl´anek skuteˇcnˇe patˇr´ı. V´ ysledky jsou zobrazeny v tabulce 5.10. Delka vektoru: Klasi kator: Hamming Accuracy
4000 Bayess 13,3 79,49
3000 SVM 5,12 90,25
3000 MaxEnt 5,54 89,77
neomezena Bayess 11,47 82,49
neomezena SVM 5,57 89,71
neomezena MaxEnt 4,4 91,66
´ eˇsnost klasifikace pro vˇsechny kategorie pˇri pouˇzit´ı parametrizace Tabulka 5.10: Uspˇ MI se zahrnut´ım jedn´e kategorie nav´ıc vyhodnocen´a metrikou Hamming Loss a Accuracy
Zhodnocen´ı Pˇri klasifikov´an´ı do v´ıce kategori´ı znovu nejl´epe dopadl klasifik´ator SVM. Error rate byl v tomto pˇr´ıpadˇe 9,44 % a jiˇz zde nen´ı velk´ y rozd´ıl mezi omezen´ ym a neomezen´ ym vektorem (pˇribliˇznˇe 0,5 % pro SVM a 2 % pro zb´ yvaj´ıc´ı klasifik´atory). Tato vlastnost je pravdˇepodobnˇe zp˚ usobena vˇetˇs´ı tr´enovac´ı mnoˇzinou, protoˇze kaˇzd´ y ˇcl´anek se v tr´enovac´ı mnoˇzinˇe vyskytuje tolikr´at, do kolika tˇr´ıd patˇr´ı. Pokud do vyhodnocen´ı u ´spˇeˇsnosti zahrneme jeˇstˇe jednu predikovanou kategorii nav´ıc (viz tabulka 5.10, zjist´ıme, ˇze u ´spˇeˇsnost se zlepˇs´ı zhruba o 5 %. Jin´ ymi slovy, pˇribliˇznˇe 50 % chybnˇe rozpoznan´ ych kategori´ı se nach´az´ı o jednu kategorii d´ale neˇz by mˇelo, coˇz m˚ uˇze b´ yt zp˚ usobeno ne´ uplnˇe anotovan´ ymi daty. D´ale se uk´azalo, ˇze neomezen´a d´elka vektoru zbyteˇcnˇe prodluˇzuje dobu klasifikace bez v´ yznamn´eho zlepˇsen´ı u ´spˇeˇsnosti jak ukazuje n´asleduj´ıc´ı kapitola. Pokud u ´spˇeˇsnost klasifikace vyhodnot´ıme tak, ˇze zahrneme jeˇstˇe jednu predikovanou kategorii nav´ıc, neˇz do kolika ˇcl´anek patˇr´ı, u ´spˇeˇsnost se zv´ yˇs´ı cca. o 5 %.
5.5.1
ˇ Casov´ a n´ aroˇ cnost tr´ enov´ an´ı modelu
Dalˇs´ım krit´eriem pro v´ ybˇer klasifik´atoru je ˇcasov´a n´aroˇcnost tr´enov´an´ı modelu. Experimenty byly prov´adˇeny na poˇc´ıtaˇci jehoˇz konfigurace je uvedena v tabulce 5.11. ˇ Casov´ a n´aroˇcnost tr´enov´an´ı a vyhodnocen´ı modelu pro v´ ysledky experiment˚ u uveden´ ych v tabulce 5.10 je uvedena v tabulce 5.12.
5.6 Shrnut´ı v´ ysledk˚ u
45
Operaˇcn´ı syst´em Linux Ubuntu 2.6.31-23 CPU Intel(R) Core(TM)2 Quad CPU Q9550 @ 2.83GHz RAM 8 GB Tabulka 5.11: Konfigurace poˇc´ıtaˇce na kter´em byly prov´adˇeny experimenty Delka vektoru: Klasi kator: Cas
4000 Bayess 3,6 min
3000 SVM 4,5 h
3000 MaxEnt 11,89 h
neomezena Bayess 9,4 min
neomezena SVM 10,5 h
neomezena MaxEnt 31,8 h
ˇ Tabulka 5.12: Casov´ a n´aroˇcnost tr´enov´an´ı model˚ u pˇri dan´e konfiguraci experiment˚ u
5.6
Shrnut´ı v´ ysledk˚ u
Z prov´adˇen´ ych experiment˚ u v kapitole 5.1 byla zjiˇstˇena optim´aln´ı d´elka vektoru slov pro tr´enovac´ı a testovac´ı soubory. Tato d´elka odpov´ıd´a hodnotˇe 4000 pro Bayes˚ uv klasifik´ator a pro zb´ yvaj´ıc´ı klasifik´atory byla stanovena na hodnotu 3000. V kapitole 5.2 jsem se pak zamˇeˇril na v´ ybˇer vhodn´ ych POS tag˚ u. Na z´akladˇe pˇreˇcten´e literatury jsem vyb´ıral slova odpov´ıdaj´ıc´ı vˇsem kombinac´ım podstatn´ ych jmen, pˇr´ıdavn´ ych jmen, pˇr´ıslovc´ı a sloves, pˇriˇcemˇz podstatn´a jm´ena byla pˇr´ıtomna vˇzdy, protoˇze na klasifikaci maj´ı nejvˇetˇs´ı vliv. Doˇsel jsem k z´avˇeru, ˇze pro klasifikaci je lepˇs´ı pouˇz´ıt kombinaci bez sloves. V experimentu v podkapitole 5.3 jsem pak testoval vliv lemmat na klasifikaci. Pˇri pouˇzit´ı lemmat se u ´spˇeˇsnost jiˇz pˇr´ıliˇs nezlepˇsila, proto ji lze pˇr´ıpadnˇe pro urychlen´ı klasifikace vynechat. Na z´akladˇe tohoto a pˇredchoz´ıho experimentu byla tak´e vybr´ana metoda MI pro v´ ybˇer pˇr´ıznak˚ u, kter´a v testech dosahovala nejlepˇs´ıch v´ ysledk˚ u. Pˇri klasifikaci do jedn´e, hlavn´ı, kategorie se Error rate pohyboval kolem 17 % pro Naivn´ı Bayes˚ uv klasifik´ator a kolem 11 % pro ostatn´ı klasifik´atory na omezen´e d´elce vektoru. Pro neomezenou d´elku vektoru Error rate klesl zruba o 3 % pro Naivn´ı Bayes˚ uv a o 2 % pro ostatn´ı klasifik´atory. Tento v´ ysledek ale nen´ı pro tuto pr´aci natolik d˚ uleˇzit´ y, protoˇze hlavn´ı c´ıl je klasifikace do v´ıce kategori´ı. ´ eˇsnost klasifikace do v´ıce kategori´ı vyhodnocen´a metrikou Hamming loss Uspˇ dosahovala hodnoty 19 % pro Naivn´ı Bayes˚ uv klasifik´ator a hodnoty mezi 9,5 % 10 % pro ostatn´ı klasifik´atory na omezen´e d´elce vektoru. Pro neomezenou d´elku pak dokonce u klasifik´atoru Maximum Entropy klesl k 8 %. D´ale bylo zjiˇstˇeno, ˇze klasifikace pomoc´ı Naivn´ıho Bayesova klasifik´atoru trvala ˇr´adovˇe minuty, zat´ımco SVM v ˇr´adech hodin a Maximum Entropy pak dokonce 3x d´ele neˇz SVM. Samozˇrejmˇe doba tr´enov´an´ı a testov´an´ı je z´avisl´a na konfiguraci poˇc´ıtaˇce. Pro tuto pr´aci byla pouˇzita konfigurace zobrazen´a v tabulce 5.11. Z´ıskan´a data z klasifikace do v´ıce kategori´ı jsem jeˇstˇe vyhodnotil tak, ˇze jsem zahrnul jednu predikovanou kategorii nav´ıc, abych zjistil, jak se zmˇen´ı u ´spˇeˇsnost klasifikace. Bylo zjiˇstˇeno, ˇze u ´spˇeˇsnost se zlepˇsila zhruba o 5 %, coˇz pro klasifik´ator SVM a Maximum Entropy ˇcin´ı 50 % zlepˇsen´ı. Jin´ ymi slovy to znamen´a, ˇze 50 % chybnˇe klasifikovan´ ych ˇcl´ank˚ u se nach´az´ı o jednu kategorii d´ale neˇz by mˇelo.
5.6 Shrnut´ı v´ ysledk˚ u
46
Ve skuteˇcnosti je ale u ´spˇeˇsnost klasifikace mnohem vˇetˇs´ı. Nˇekter´e klasifikovan´e ˇcl´anky totiˇz obsahovaly pouze jednu ˇci dvˇe kr´atk´e vˇety a klasifik´ator pak nedok´azal spr´avnˇe urˇcit tˇr´ıdu klasifikace. Tyto ˇcl´anky nebyly z tr´enovac´ıch a testovac´ıch mnoˇzin filtrov´any, protoˇze c´ılem pr´ace nen´ı dos´ahnout co nejlepˇs´ı u ´spˇeˇsnosti z hlediska ˇc´ısel, ale co nejlepˇs´ı u ´spˇeˇsnosti pro praktick´e pouˇzit´ı. Chyba tak´e mohla b´ yt zp˚ usobena ne´ uplnou anotac´ı mnoˇziny tˇr´ıd, do kter´ ych ˇcl´anky ve skuteˇcnosti patˇr´ı. Chybˇej´ıc´ı tˇr´ıdy pak klasifik´ator urˇcil jako chybnˇe klasifikovan´e. Po pˇreˇcten´ı t´eto kapitoly by mˇelo b´ yt ˇcten´aˇri jasn´e, jakou kombinaci metod a nastaven´ı klasfikaˇcn´ıho syst´emu pouˇz´ıt jako kompromis mezi u ´spˇeˇsnost´ı a ˇcasovou n´aroˇcnost´ı. Osobnˇe doporuˇcuji pouˇz´ıt klasifik´ator SVM, metodu MI pro v´ ybˇer pˇr´ıznak˚ u na omezen´em vektoru d´elky 3000 a POS-tagging pro filtrov´an´ı pˇr´ıznak˚ u s vynech´an´ım lemmatizace, kter´a je ˇcasovˇe n´aroˇcn´a a zlepˇsen´ı je pouze v ˇr´adech desetin procenta.
47
Kapitola 6 Z´ avˇ er ˇ e tiskov´e kancel´aˇre, se kterou jsem ˇreˇsen´ı tak´e Toto t´ema vyplynulo z potˇreb Cesk´ konzultoval. C´ılem pr´ace bylo prozkoumat metody klasifikace ˇcl´ank˚ u s podobn´ ym obsahem a navrhnout programov´e ˇreˇsen´ı, kter´e by umoˇznilo klasifikovat dokumenty do v´ıce kategori´ı, tzv. Multi-label klasifikace. Pˇri v´ ybˇeru klasifik´ator˚ u a metod pro v´ ybˇer pˇr´ıznak˚ u byl kladen d˚ uraz na jejich u ´spˇeˇsnost, rychlost a dostupnost. Na z´akladˇe pˇreˇcten´e literatury bylo zvoleno pˇet metod v´ ybˇeru pˇr´ıznak˚ u (DF, MI, IG, CHI2, GSS) a tˇri klasifik´atory (Naivn´ı Bayes˚ uv, SVM a Maximum Entropy). D´ale byl zvolen klasifikaˇcn´ı n´astroj Minorthird pro implementaci vybran´ ych klasifik´ator˚ u. N´astroj byl vhodnˇe pˇrizp˚ usoben pro potˇreby t´eto pr´ace, aniˇz by byla poruˇsena licence a byly splnˇeny podm´ınky pro ˇ vyuˇzit´ı CTK. Pro zlepˇsen´ı u ´spˇeˇsnosti klasifikace byly pouˇzity metody morfologick´e anal´ yzy textu, konkr´etnˇe se jednalo o POS-tagging a lemmatizaci. Z v´ ysledk˚ u experiment˚ u v kapitole 5 se uk´azalo, ˇze lemmatizace nen´ı pro klasifikaci pˇr´ıliˇs d˚ uleˇzit´a. Zlepˇsovala u ´spˇeˇsnost pr˚ umˇernˇe o 1 %. Naopak POS-tagging se uk´azal jako velmi uˇziteˇcn´ y pro filtraci slov. Kombinace POS tag˚ u, kter´a poskytovala nejlepˇs´ı ˇreˇsen´ı byla podstatn´a jm´ena, pˇr´ıdavn´a jm´ena a pˇr´ıslovce. D´ale jsem uk´azal, ˇze dostateˇcn´a d´elka vektoru pˇr´ıznak˚ u je pro Naivn´ı Bayes˚ uv klasifik´ator 4000 a pro ostatn´ı klasifik´atory 3000. Pˇri vˇetˇs´ı d´elce vektoru se prodluˇzuje ˇcas klasifikace bez znateln´eho zlepˇsen´ı u ´spˇeˇsnosti. Pˇri prodluˇzuj´ıc´ı se d´elce vektoru se tak´e st´ıraj´ı rozd´ıly mezi metodami v´ ybˇeru pˇr´ıznak˚ u. Nejlepˇs´ı u ´spˇeˇsnosti bylo dosaˇzeno s klasifik´atorem SVM, kde metrika Hamming loss dosahovala vynikaj´ıc´ı hodnoty 9,44 %. Tento klasifik´ator je proto doporuˇcen ˇ CTK pro klasifikaci ˇcl´ank˚ u do v´ıce kategori´ı spolu s nastaven´ım uveden´ ym v kapitole 5.6. Nakonec byla implementov´ana aplikace s grafick´ ym rozhran´ım pro snadnou konfiguraci u ´lohy. ˇ CTK pˇredpokl´ad´a nasazen´ı a rozˇs´ıˇren´ı klasifikaˇcn´ıho syst´emu o metody anal´ yzy sentimentu. Pˇri dalˇs´ım v´ yvoji nebude m´ıt velk´ y smysl zkoumat dalˇs´ı metody v´ ybˇeru pˇr´ıznak˚ u. Sp´ıˇse by se pozornost mˇela vˇenovat v´ ybˇeru jin´ ych pˇr´ıznak˚ u, kter´e by od sebe kategorie dok´azaly l´epe separovat. Za zkouˇsku by st´alo prozkoumat moˇznost pouˇzit´ı syntaktick´e struktury vˇety, pojmenovan´ ych entit, atd.
48
Pˇ rehled term´ın˚ u a zkratek Anotace Ruˇcn´ı pˇriˇrazen´ı kategori´ı k dokument˚ um CRF Conditional random fields (podm´ınˇen´a n´ahodn´a pole) Cross-validation (kˇr´ıˇzov´a validace) Metodika rozdˇelov´an´ı dat na disjunktn´ı mnoˇziny pro tr´enov´an´ı a testov´an´ı klasifik´atoru ˇ a Tiskov´a Kancel´aˇr ˇ CTK Cesk´ DF Document Frequency (dokumentov´a frekvence) GSS Gallavotti, Sebastiani, Simi (metoda v´ ybˇeru pˇr´ıznak˚ u pojmenovan´a podle autor˚ u) HTML HyperText Markup Language (znaˇckovac´ı jazyk pro hypertext) CHI2 Chi-kvadr´at metoda pro v´ ybˇer pˇr´ıznak˚ u IG Information Gain (informaˇcn´ı zisk) Lemmatizace Lemmatization (proces urˇcov´an´ı z´akladn´ıho tvaru slov) Lemma Z´akladn´ı podoba lex´emu, tak´e slovn´ıkov´ y tvar Metadata Strukturovan´a data o datech MI Mutual Information (metoda vz´ajemn´e informace) Multi-class classification Klasifikace pr´avˇe do jedn´e mnoˇziny z mnoˇziny definovan´ ych tˇr´ıd Multi-label classification Klasifikace do v´ıce mnoˇzin z mnoˇziny definovan´ ych tˇr´ıd NLP Natural Language Procesing (zpracov´an´ı pˇrirozen´eho jazyka) POS Part of Speech (slovn´ı druhy) SAX Simple API for XML (jednoduch´e rozhran´ı pro proudov´e zpracov´an´ı XML) Stematizace Stematization (proces urˇcov´an´ı z´akladu slova)
49
STOP list Seznam slov, kter´a nebudou pˇri klasifikaci uvaˇzov´ana SVM Support Vector Machine (metoda podp˚ urn´ ych vektor˚ u) Term Ekvivalentn´ı v´ yraz pro Token Token Oznaˇcuje slovo dokumentu Tokenizace Pˇrevod novinov´eho ˇcl´anku na seznam token˚ u XML Extensible Markup Language (rozˇsiˇriteln´ y znaˇckovac´ı jazyk)
50
Literatura [1] ALIAS-I. LingPipe 4.1.0. 2008. Dostupn´e z: http://alias-i.com/lingpipe. [2] ARIE – BEN-DAVID. Comparison of classification accuracy using Cohen’s Weighted Kappa. Expert Systems with Applications. 2008, 34, 2, s. 825 – 832. ISSN 0957-4174. doi: 10.1016/j.eswa.2006.10.022. Dostupn´e z: http: //www.sciencedirect.com/science/article/pii/S0957417406003435. [3] BEIL, F. – ESTER, M. – XU, X. Frequent term-based text clustering. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, KDD ’02, s. 436–442, New York, NY, USA, 2002. ACM. doi: 10.1145/775047.775110. Dostupn´e z: http://doi.acm.org/ 10.1145/775047.775110. ISBN 1-58113-567-X. [4] BJ¨oRKELUND, A. – HAFDELL, L. – NUGUES, P. Multilingual semantic role labeling. In Proceedings of the Thirteenth Conference on Computational Natural Language Learning: Shared Task, CoNLL ’09, s. 43–48, Stroudsburg, PA, USA, 2009. Association for Computational Linguistics. Dostupn´e z: http: //dl.acm.org/citation.cfm?id=1596409.1596416. ISBN 978-1-932432-299. ˇ B. Exploiting structural information for semi[5] BRATKO, A. – FILIPIC, structured document categorization. In Information Processing and Management, s. 679–694, 2004. [6] COHEN, W. W. MinorThird: Methods for Identifying Names and Ontological Relations in Text using Heuristics for Inducing Regularities from Data. 2004. Dostupn´e z: http://minorthird.sourceforge.net. [7] COVER, T. – THOMAS, J. Elements of information theory. New York : Wiley, 1991. [8] DELLA PIETRA, S. – DELLA PIETRA, V. – LAFFERTY, J. Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence. 1997, 19, 4, s. 380–393. Dostupn´e z: http://ieeexplore.ieee. org/lpdocs/epic03/wrapper.htm?arnumber=588021. ˇ [9] DUSEK, O. Deep Automatic Analysis of English. Diplomov´a pr´ace, Charles University in Prague, Faculty of Mathematics and Physics, 2010.
Literatura
51
ˇ [10] EXPRIT. Copyright Exprit s.r.o. Technick´a dokumentace InfoBanky CTK. 1997. [11] FINKEL, J. Stanford Named Entity Recognizer. 2005. Dostupn´e z: http: //nlp.stanford.edu/software/CRF-NER.shtml. [12] FORMAN, G. – GUYON, I. – ELISSEEFF, A. An extensive empirical study of feature selection metrics for text classification. Journal of Machine Learning Research. 2003, 3, s. 1289–1305. [13] GALAVOTTI, L. – SEBASTIANI, F. – SIMI, M. Experiments on the Use of Feature Selection and Negative Evidence in Automated Text Categorization. In Proceedings of the 4th European Conference on Research and Advanced Technology for Digital Libraries, ECDL ’00, s. 59–68, London, UK, UK, 2000. Springer-Verlag. Dostupn´e z: http://dl.acm.org/citation.cfm?id=646633. 699638. ISBN 3-540-41023-6. [14] HALL, M. et al. The WEKA data mining software: an update. SIGKDD Explorations. November 2009, 11, 1, s. 10–18. ISSN 1931-0145. Dostupn´e z: http://dx.doi.org/10.1145/1656274.1656278. [15] JOACHIMS, J. T. Y. Y. Text categorization. Scholarpedia. 2008, 3, 5, s. 4242. [16] JOACHIMS, T. SVMlight: http://svmlight.joachims.org/, 2008.
Support
Vector
Machine.
[17] LIM, C. S. – LEE, K. J. – KIM, G. C. Multiple sets of features for automatic genre classification of web documents. Information Processing and Management. 2005, 41, 5, s. 1263 – 1276. ISSN 0306-4573. doi: 10.1016/j.ipm.2004.06. 004. Dostupn´e z: http://www.sciencedirect.com/science/article/pii/ S0306457304000676. [18] LUO, X. – ZINCIR-HEYWOOD, A. N. Incorporating Temporal Information for Document Classification. In ICDE Workshops, s. 780–789, 2007. [19] MANNING, C. D. – RAGHAVAN, P. – SCH¨ uTZE, H. Introduction to Information Retrieval. Cambridge University Press, 1 edition, July 2008. Dostupn´e z: http://www.amazon.com/exec/obidos/redirect?tag= citeulike07-20&path=ASIN/0521865719. ISBN 0521865719. [20] MCCALLUM, A. K. MALLET: A Machine Learning for Language Toolkit. http://mallet.cs.umass.edu, 2002. [21] NIGAM, K. Using maximum entropy for text classification. In In IJCAI-99 Workshop on Machine Learning for Information Filtering, s. 61–67, 1999. ˇ ´ J. – MAL´IK, A. – PUDIL, P. Feature Selection using Improved [22] NOVOVICOV A, Mutual Information for Text Classification, 3138, s. 1010–1017. Springer, 2004. Dostupn´e z: http://dx.doi.org/10.1007/978-3-540-27868-9_111.
Literatura
52
[23] FORMAL, I. – LINGUISTICS, A. CoNLL-2009 Shared Task Description [online]. 2008. [cit. 19. 3. 2012]. Dostupn´e z: http://ufal.mff.cuni.cz/ conll2009-st/task-description.html#Dataformat. [24] SEBASTIANI, F. Machine learning in automated text categorization. ACM Comput. Surv. March 2002, 34, 1, s. 1–47. ISSN 0360-0300. doi: 10.1145/ 505282.505283. Dostupn´e z: http://doi.acm.org/10.1145/505282.505283. [25] TIMOTHY P. JURKA, A. E. B. E. G. L. C. – ATTEVELDT, W. RTextTools: Automatic Text Classification via Supervised Learning. http://www.rtexttools.com, 2011. [26] TSOUMAKAS, G. – KATAKIS, I. Multi-label classification: An overview. International Journal of Data Warehousing and Mining. 2007, 3, 3, s. 1–13. Dostupn´e z: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1. 1.104.9401&rep=rep1&type=pdf. [27] UGUZ, H. A two-stage feature selection method for text categorization by using information gain, principal component analysis and genetic algorithm. Knowl.-Based Syst. 2011, 24, 7, s. 1024–1032. [28] WWW.IPTC.ORG. IPTC Web - NewsML, 2012. Dostupn´e z: http://www.iptc.org/cms/site/single.html?channel=CH0087&document= CMS1206527546450. [29] YANG, Y. – PEDERSEN, J. O. A Comparative Study on Feature Selection in Text Categorization. In Proceedings of the Fourteenth International Conference on Machine Learning, ICML ’97, s. 412–420, San Francisco, CA, USA, 1997. Morgan Kaufmann Publishers Inc. Dostupn´e z: http://dl.acm.org/ citation.cfm?id=645526.657137. ISBN 1-55860-486-3. [30] ZHOU, X. – ZHANG, X. – HU, X. Dragon Toolkit: Incorporating Auto-learned Semantic Knowledge into Large-Scale Text Retrieval and Mining. In Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2007. Dostupn´e z: http://dragon.ischool.drexel.edu/.
53
Pˇ r´ılohy
54
Pˇ r´ıloha A Struktura DVD Na pˇriloˇzen´em DVD se nach´az´ı n´asleduj´ıc´ı stromov´a struktura adres´aˇr˚ u: • adres´aˇr doc – adres´aˇr src – zdrojov´e LATEXov´e soubory t´eto pr´ace – adres´aˇr pdf – tato pr´ace v PDF form´atu • adres´aˇr classification – adres´aˇr se samotn´ ym programem – adres´aˇr bin – adres´aˇr s pˇreloˇzenou aplikac´ı – adres´aˇr config – obsahuje uk´azkov´ y konfiguraˇcn´ı soubor aplikace ˇ – adres´aˇr data – adres´aˇr s daty (pouze ve verzi pro CTK) – adres´aˇr jar – obsahuje jar soubory aplikace a upraven´eho n´astroje Minorthird – adres´aˇr javadoc – adres´aˇr s javadoc dokumentac´ı – adres´aˇr lib – knihovny vyuˇz´ıvan´e aplikac´ı – adres´aˇr models – natr´enovan´e modely – adres´aˇr src – zdrojov´e soubory aplikace – compile.bat – kompilace zdrojov´ ych soubor˚ u pro Windows – compile.sh – kompilace zdrojov´ ych soubor˚ u pro Linux – logging.properties – soubor pro nastaven´ı logov´an´ı – run.bat – spuˇstˇen´ı GUI aplikace pro Windows – run.sh – spuˇstˇen´ı GUI aplikace pro Linux • adres´aˇr scripts – adres´aˇr se skripty pro proveden´e experimenty • adres´aˇr results – adres´aˇr s v´ ysledky proveden´ ych experiment˚ u vˇcetnˇe souboru s grafy
55
Pˇ r´ıloha B UML diagram aplikace
Obr´azek B.1: UML diagram aplikace
56
Pˇ r´ıloha C Uˇ zivatelsk´ a pˇ r´ıruˇ cka Kapitola popisuje zp˚ usob pˇreloˇzen´ı programu, jeho konfiguraci a pˇr´ıklady spuˇstˇen´ı.
C.1
Pˇ reklad programu
Program lze pˇreloˇzit skriptem, kter´ y se nach´az´ı na pˇriloˇzen´em DVD v adres´aˇri classification. K dispozici jsou dva soubory, compile.bat pro operaˇcn´ı syst´em Windows a compile.sh pro operaˇcn´ı syst´em Linux.
C.2
Konfigurace programu
Konfigurace programu je velmi jednoduch´a a prov´ad´ı se pomoc´ı Java properties souboru. Jeho jednotliv´e poloˇzky jsou vysvˇetleny n´ıˇze. • POS FILTER - Seznam POS tag u, ktere budou ponechany. Oddelovac je mezera. • IGNORED CATEGORIES - Seznam kategori ktere budou ignorovany. • USE MULTI CAT - Hodnota true pro klasi kaci do vce kategori. • USE WORDS - Hodnota true pokud budou pouzita slova namsto lemmat. • USE POS TAG - Hodnota true pokud bude pouzit POS tagging. • STOP WORDS - Slova, ktera budou vy ltrovana. Oddelovac je mezera. • EOL - Znak ukoncen radku. • MIN DOC CAT - Minimaln pocet clank u na kategorii. • MAX DOC CAT - Maximaln pocet clank u na kategorii. • FEATURE SERIALIZATION - Soubor se serializovanymi statistikami. Soubor je vytvaren pri trenovan modelu.
C.2 Konfigurace programu • POS TAG MODEL - Cesta k natrenovanemu modelu pro POS-tagging. • LEMMA MODEL - Cesta k natrenovanemu modelu pro lemmatizaci. • BAYESS TRAINED MODEL - Cesta k natrenovanemu (pro ulozen) Baysovskemu modelu. • SVM TRAINED MODEL - Cesta k natrenovanemu (pro ulozen) SVM modelu. • MAXENT TRAINED MODEL - Cesta k natrenovanemu (pro ulozen) Max. Ent. modelu. • TEMP PARSER FILE - Cesta pro ulozen/nacten parsovaneho souboru. • TEMP FILE OUTPUT LEMMA - Cesta pro ulozen/nacten vystupu lemmatizatoru. • TEMP FILE OUTPUT POSS - Cesta pro ulozen/nacten vystupu POS taggeru. • FILE FOR CLASSIFICATOR - Cesta pro ulozen/nacten souboru pro klasi kator. • PREDICTED CATEGORY - Cesta pro ulozen vysledku klasi kace. • TRESHOLD - Prahova hodnota pro urcen spravnych kategori.
C.2.1
Uk´ azkov´ a konfigurace
POS FILTER=N A V D USE MULTI CAT=t r u e TEMP FILE OUTPUT LEMMA=temp/ temp output lemma . t x t STOP WORDS=. − , \ : ? \ ! " \ u201C \ u201E ) ( { } \= EOL=\ r \n MAX DOC CAT=600 FEATURE SERIALIZATION=w o r d s f e a t u r e . s e r SVM TRAINED MODEL=models /SvmModel . s e r USE WORDS=f a l s e FILE FOR CLASSIFICATOR=c l a s s . t x t TEMP PARSER FILE=temp/temp lemma . t x t BAYESS TRAINED MODEL=models / BayessModel . s e r PREDICTED CATEGORY=c l a s s . xml MAXENT TRAINED MODEL=models /MaxEntModel . s e r TEMP FILE OUTPUT POSS=temp/ temp output pos . t x t IGNORED CATEGORIES=xhs den p l a sue mnt eng bns MIN DOC CAT=250 USE POS TAG=t r u e POS TAG MODEL=models / tag−cz . model LEMMA MODEL=models /lemma−cz . model TRESHOLD=20
57
C.3 Pˇr´ıklady spuˇstˇen´ı
C.3
58
Pˇ r´ıklady spuˇ stˇ en´ı
Pˇr´ıklady spuˇstˇen´ı budou uk´az´any pro jar soubor s aplikac´ı, kter´ y v sobˇe obsahuje jiˇz zabalen´ y klasifik´ator a n´astroj pro morfologickou anal´ yzu. Tento soubor se nach´az´ı na pˇriloˇzen´em DVD na cestˇe classification/jar/Classification.jar. Aplikace umoˇzn ˇuje veˇsker´e experimenty konfigurovat a spouˇstˇet z grafick´eho prostˇred´ı. Pˇredpokl´adejme tedy, ˇze se nach´az´ıme v adres´aˇri classification. Spuˇstˇen´ı grafick´eho prostˇred´ı provedeme pˇr´ıkazem java -jar jar/Classification.jar config/prop.properties pˇr´ıpadnˇe m˚ uˇzeme pouˇz´ıt spouˇstˇec´ı skript run.bat pro OS Windows ˇci run.sh pro OS Linux. Pokud bychom nechtˇeli pracovat z grafick´eho rozhran´ı, m˚ uˇzeme cel´ y program od parsov´an´ı, lemmatizaci, POS-tagging, extrakci pˇr´ıznak˚ u aˇz po samotnou klasifikaci konfigurovat ve skriptech obsahuj´ıc´ıch spouˇstˇen´ı jednotliv´ ych podprogram˚ u. Toto pouˇzit´ı je tak´e doporuˇceno z d˚ uvodu rychlosti a konfigurace v´ıce experiment˚ u najednou. Pokud nebudeme cht´ıt explicitnˇe u kaˇzd´eho programu pˇri spuˇstˇen´ı uv´adˇet konfiguraˇcn´ı soubor, m˚ uˇzeme vytvoˇrit soubor properties.properties pˇr´ımo u jar souboru cel´e aplikace. Tento soubor bude pouˇzit jako defaultn´ı v pˇr´ıpadˇe, ˇze nebude specifikov´an jin´ y. • Parsov´an´ı XML souboru a vygenerov´an´ı vstupu pro lemmatiz´ator, POS-tagger nebo pro program extrahuj´ıc´ı pˇr´ıznaky m˚ uˇzeme prov´est pˇr´ıkazem java -cp jar/Classification.jar preprocessing.Preprocessing
