Sem vložte zadání Vaší práce

Sem vložte zadání Vaší práce.

České vysoké učení technické v Praze Fakulta informačních technologií Katedra teoretické informatiky

Diplomová práce

Moderní metody klasifikace zpravodajských článků Bc. Martin Pirkl

Vedoucí práce: Ing. Pavel Kordík, Ph.D.

6. května 2014

Poděkování Chtěl bych poděkovat vedoucímu práce Pavlu Kordíkovi za spolupráci, podporu a možnost podílet se na řešení zajímavého problému.

Prohlášení Prohlašuji, že jsem předloženou práci vypracoval(a) samostatně a že jsem uvedl(a) veškeré použité informační zdroje v souladu s Metodickým pokynem o etické přípravě vysokoškolských závěrečných prací. Beru na vědomí, že se na moji práci vztahují práva a povinnosti vyplývající ze zákona č. 121/2000 Sb., autorského zákona, ve znění pozdějších předpisů, zejména skutečnost, že České vysoké učení technické v Praze má právo na uzavření licenční smlouvy o užití této práce jako školního díla podle § 60 odst. 1 autorského zákona.

V Praze dne 6. května 2014

.....................

České vysoké učení technické v Praze Fakulta informačních technologií c 2014 Martin Pirkl. Všechna práva vyhrazena.

Tato práce vznikla jako školní dílo na Českém vysokém učení technickém v Praze, Fakultě informačních technologií. Práce je chráněna právními předpisy a mezinárodními úmluvami o právu autorském a právech souvisejících s právem autorským. K jejímu užití, s výjimkou bezúplatných zákonných licencí, je nezbytný souhlas autora.

Odkaz na tuto práci Pirkl, Martin. Moderní metody klasifikace zpravodajských článků. Diplomová práce. Praha: České vysoké učení technické v Praze, Fakulta informačních technologií, 2014.

Abstrakt Tato práce obsahuje přehled poznatků a metod multi-label klasifikace zaměřený hlavně na textové dokumenty. Dále pracuje se zpravodajskými články z portálu Blesk.cz, analyzuje a popisuje jejich specifika. Na základě vzešlých poznatků je navrhnut a implementován systém sloužící ke správě zpravodajských článků a rubrik, včetně vícenásobné kategorizace a detekce nových témat. Klíčová slova multi-label klasifikace, zpravodajské články, ML-kNN

Abstract This work contains an overview and methods of multi-label classification focused on text documents. Newspaper articles from the Czech portal Blesk.cz are used, analyzed and their characteristics are described. Based on the outcomes, the system for managing news articles and columns is designed and implemented, including multi-label categorization and detection of new topics. Keywords multi-label text classification, newspaper articles, ML-kNN ix

Obsah Úvod

1

1 Teoretický úvod do problematiky 1.1 Klasifikační problém . . . . . . . . . . . 1.2 Druhy klasifikačních modelů . . . . . . . 1.3 Druhy klasifikace podle charakteru tříd 1.4 Text mining . . . . . . . . . . . . . . . . 1.5 Metody multi-label klasifikace textových 1.6 Aktivní učení . . . . . . . . . . . . . . . 2 Návrh 2.1 Architektura aplikace . . . . 2.2 Funkce uživatelského rozhraní 2.3 Předzpracování dat . . . . . . 2.4 Konstrukce klasifikátoru . . . 2.5 Proces klasifikace . . . . . . . 3 Implementace 3.1 Modul downloader . 3.2 Modul preprocessing 3.3 Modul MLkNN . . . 3.4 Modul GUI . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . dokumentů . . . . . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . .

. . . . . .

. . . . .

. . . .

. . . . . .

3 3 4 6 11 18 23

. . . . .

25 25 26 28 29 30

. . . .

33 33 33 34 36

4 Analýza a vyhodnocení reálných dat 39 4.1 Analýza zpravodajských článků z portálu Blesk.cz . . . . . . . 39 4.2 Testování klasifikátoru . . . . . . . . . . . . . . . . . . . . . . . 46 xi

Závěr

53

Literatura

55

A Obsah přiloženého CD

59

xii

Seznam obrázků 1.1 1.2 1.3

Transformace hierarchické struktury na plošnou . . . . . . . . . . . Rozklad struktury na lokální hierarchie . . . . . . . . . . . . . . . Příklad matice reprezentované metodou komprimovaných řádků . .

9 10 18

2.1 2.2 2.3 2.4

Návrh architektury aplikace . . . . . . . . . . . . . . . . . . . . . Náčrt uživatelského rozhraní pro správu článků . . . . . . . . . . Výčet 30ti rubrik s nejvyšším procentuálním zastoupením článků Integrovaný proces klasifikace . . . . . . . . . . . . . . . . . . . .

. . . .

26 27 28 31

3.1 3.2 3.3

Ukázka grafického uživatelsého rozhraní 1 . . . . . . . . . . . . . . Ukázka grafického uživatelského rozhraní 2 . . . . . . . . . . . . . Ukázka grafického uživatelksého rozhraní 3 . . . . . . . . . . . . .

36 37 38

4.1

Zobrazení originálně kategorizovaných článků v prostoru s využitím kosinové podobnosti . . . . . . . . . . . . . . . . . . . . . . . . Podíl jednotlivých rubrik ve vizualizované množině článků . . . . . Export zobrazení originálně kategorizovaných článků do webového rozhraní . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Zobrazení kategorizovaných článků v prostoru pomocí algoritmu na detekci shluků [22] . . . . . . . . . . . . . . . . . . . . . . . . . Zobrazení originálně kategorizovaných článků v prostoru s využitím kosinové podobnosti (nahoře) v porovnání se stejnými články klasifikovanými pomocí ML-kNN (dole) . . . . . . . . . . . . . . . Podíl jednotlivých rubrik v nově kategorizované množině článků . Podíl skupin rubrik v nově kategorizované množině článků . . . . . Detekovaný shluk článků týkajících se sportu . . . . . . . . . . . . Detekovaný shluk článků týkajících se Microsoftu . . . . . . . . . .

4.2 4.3 4.4 4.5

4.6 4.7 4.8 4.9

xiii

40 40 42 44

47 48 48 50 51

Seznam tabulek 1.1 1.2 1.3

Lemmatizace – ztráta významu x redukce dimenzionality . . . . . Příklad multi-label datasetu . . . . . . . . . . . . . . . . . . . . . . Tři datasety vytvořené metodou binary relevance . . . . . . . . . .

15 19 20

4.1 4.2 4.3

Nejčastěji se vyskytující termy ve vybraných rubrikách . . . . . . Zastoupení rubrik v 10ti nejobjemnějších shlucích na obrázku 4.4 . Experimentální výsledky výkonu ML-kNN klasifikátoru na datech popsaných výše . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43 45

xv

49

Úvod S roustoucím objemem znalostí a dostupných informací se klasifikace textových dokumentů stává stále žádanější a objevují se stále nové případy, kde se tato technika může uplatnit. To způsobuje, že jsou kladeny nové nároky, které jsou poměrně specifické v závislosti na doméně problému. Zajímavým odvětvím, o kterém pojednává tato práce, je klasifikace článků ze zpravodajských serverů v českém jazyce. Jedním z přínosů klasifikace textových dokumentů je, že odpadá potřeba, aby někdo všechny texty postupně přečetl, zamyslel se nad nimi, a zařadil je do příslušných kategorií podle jejich obsahu. Toto je samozřejmně při dnešním množství informací časově velmi náročná a hlavně neefektivní metoda. Co se týče zpravodajských článků, zde má ve většině případů autor jasno o čem píše a dovede článek správně zařadit. Ne vždy se ale článek týká pouze jedné rubriky, do které byl původně úmysl ho zařadit. Nehledě na to, že většina českých zpravodajských portálů zařazuje příspěvky právě do jedné z rubrik. Navíc témata, o kterých se píše a na které jsou rubriky vázány, se neustále mění, vznikají nová a stará zanikají. Toto všechno bývá momentálně manuálně v režii redaktorů, což může být při velkém množství článků v takto dynamickém prostředí nepraktické. Cílem této práce je najít a ověřit metody, které by vedly k automatické kategorizaci českých zpravodajských článků do více rubrik a to na konkrétních datech z českého zpravodajského serveru Blesk.cz a tím ulehčit a upřesnit manuální kategorizaci. Aby toto vůbec bylo možné, je potřeba tato data analyzovat, tedy zjistit jejich charakter, což povede k lepšímu určení těchto metod. Dalším cílem je zjistit, jestli na základě již existujících a kategorizovaných zpravodajských lze nabídnout uživateli určitou nápovědu, kam nový 1

Úvod příspěvek zařadit, popřípadě upozornit na možnost nové rubriky na základě dektekce nového tématu, o kterém se aktuálně začalo psát. Také by bylo žádoucí, aby všechny tyto funkce byly implementované v jednom komplexním systému, který by dokázal při vložení nového článku text zpracovat a nabídnout příslušné rubriky a následně je nechat manuálně editovat a tím ovlivnit nabídku u ostatních stávajících či v budoucnu vložených článků. Jinými slovy vložit danou funkcionalitu do systému použitelném v produkčním prostředí. Takto zpracovávané články by dále mohly být například lepším podkladem pro doporučovací systém, tedy algoritmus, který nabízí související články poté, co si uživatel nějaký konkrétní zobrazí. Ten by poté nezávisel pouze na společné rubrice či několika společných klíčových slovech, ale nabídl by související články v širším kontextu. První kapitola popisuje teoretický přehled poznatků o klasifikaci, definuje problém klasifikace, druhy klasifikace a klasifikačních modelů, hlouběji je zde rozebrána multi-label klasifikace a jsou zde popsány a vysvělteny některé známé metody zaměřené hlavně na klasifikaci textových dokumentů. Druhá část kapitoly rozebírá text-mining a aktivní učení. Druhá kapitola se zabývá návrhem aplikace, která vznikla v rámci této práce. Jsou zde rozebrány požadavky, shodující se s cílem práce a navrženo jejich řešení a způsob implementace. Dále je zde popsána konstrukce klasifikátoru, na základě charakteristiky zpracovávaných dat a návrh vlastního procesu klasifikace integrovaném v systému. Třetí kapitola popisuje konkrétní implementaci systému, který zaobaluje správu článků a rubrik na základě poznatků z předešlé kapitoly. Čtvrtá kapitola analyzuje konkrétní data ze zpravodajského portálu Blesk.cz a testuje klasifikátor implementovaný v předchozí kapitole v několika experimentech.

2

Kapitola

Teoretický úvod do problematiky 1.1

Klasifikační problém

Klasifikace je proces data miningu, který je zaměřen na konstrukci a využití modelů pro třídění a doplnění dat, založený na jejich informačním obsahu. Klasifikační problém definujeme nad databází D = t1 , ..., tn n-tic představujících záznamy a pro třídy C = C1 , ..., Cm jako problém nalezení mapování f : D → C, které každému ti přiřazuje alespoň jednu třídu. Třída Cj pak obsahuje záznamy mapované do ní, tedy: Cj = ti |f (ti ) = Cj , ∀1 ≤ i ≤ n, ∀t ∈ D Proces klasifikace je složen ze dvou kroků:

1. fáze učení - vytvoření klasifikačního modelu, který je schopen klasifikovat předložená data pomocí trénovacích dat (vzorky dat u kterých známe výsledek klasifikace, tedy třídu do které patří). 2. fáze vlastní klasifikace: použití modelu pro klasifikaci nových dat, tedy rozhodnutí o jejich zařazení do jednotlivých tříd. Abychom docílili přesnějších výsledků, je před zahájením klasifikace většinou nutné provést následující úpravy dat: 1. čištění dat – odstranění šumu nebo alespoň snižení jeho míry. 2. určení relevance dat – odstranění irelevantních a redundantních dat, vzorky mohou případně být ohodnoceny váhou jejich významu. 3

1

1. Teoretický úvod do problematiky 3. transformace dat – generalizace a normalizace dat za účelem přizpůsobení použitému klasifikačnímu modelu.

1.2

Druhy klasifikačních modelů

V této časti jsou uvedeny a popsány základní druhy klasifikačních modelů.

1.2.1

Rozhodovací stromy

Rozhodovací strom můžeme definovat jako strom, kde každý nelistový uzel stromu představuje test na hodnotu atributu a větve vedoucí z tohoto uzlu možné výsledky testu. Listové uzly stromu jsou ohodnoceny identifikátory tříd, tedy výsledky klasifikace. Vlastní klasifikace pomocí rozhodovacího stromu probíhá cestou vzorku od kořene stromu k jeho listu. V každém kroku je vzorek otestován podle testovacího pravidla v aktuálním uzlu rozhodovacího stromu a dále pokračuje po větvi, která reflektuje výsledek testu. Pokud takto záznam dojde až do listového uzlu, je oklasifikován třídou, která je s ním spjatá. Z charakteru rozhodovacích stromů a průběhu klasifikace je patrné, že pomocí rozhodovacích stromů je možné predikovat pouze diskrétní hodnoty a výsledky testů v jednotlivých uzlech musí být též diskrétního typu.

1.2.2

Systémy klasifikačních pravidel

Klasifikační pravidla jsou lineárním zápisem rozhodovacích stromů a skládají se z podmínky a závěru. Množina pravidel vznikne z rozhodovacího stromu transformací, při které je každá cesta z kořene do listu stromu vyjádřena jako pravidlo, kde podmínka pravidla je logický součin všech podmínek po cestě z kořene do listu a závěr pravidla je klasifikace záznamu třídou v listu rozhodovacího stromu. Vlastní klasifikace pak probíhá vyhodnocením rozhodovacích pravidel na testovaném vzorku. Pravidla jsou vyhodnocována obvykle v sestupném pořadí podle jejich váhy.

1.2.3

Statistické metody

Ze statistických metod se nejčastěji používá regrese a Bayesovská klasifikace. V případě regrese predikujeme spojitý atribut – počítáme závisle nějakou proměnnou se zahrnutím chyby ε, kterou se následně snažíme minimalizovat. 4

1.2. Druhy klasifikačních modelů Bayesovská klasifikace využívá důsledků Bayesovy věty 1 pro klasifikaci vzorku přiřazením třídy z množiny možných tříd. Proces naivní (jednoduché) Bayesovské klasifikace přiřadí záznamu X jednu ze tříd C1 , ..., Cm , právě tehdy když pravděpodobnost tohoto jevu nastane s největší posteriori pravděpodobností:

P (Ci |X) > P (Cj |X), ∀1 ≤ j ≤ m, j 6= i

1.2.4

(1.1)

Neuronové sítě

Neuronová síť je neorientovaný graf s uzly strukturovanými do několika vrstev, kde hrany spojují jen uzly sousedních vrstev. První vrstva neuronové sítě je vstupní vrstva, poslední vrstva je označována jako výstupní vrstva. Vrstvy mezi vstupní a výstupní vrstvou jsou nazývány skryté vrstvy. Hrany grafu neuronové sítě jsou označeny vahami. Vstup dat do neuronové sítě probíhá přes vstupní vrstvu, kde je vstupem každého uzlu hodnota části analyzovaného záznamu. Typicky odpovídá jeden uzel vstupní vrstvy jednomu atributu spojitého typu normalizovaného do intervalu od 0 do 1. Výstup dat je realizován přes uzly výstupní vrstvy neuronové sítě. Při klasifikaci záznamu je příslušnost k m-té třídě reprezentována hodnotou 1 na m-tém uzlu výstupní vrstvy a hodnotou 0 na ostatních. Vlastní klasifikace a učení neuronové sítě probíhá opakovaně v těchto krocích: 1. dopředná propagace – Vstupní hodnoty uzlů vstupní vrstvy jsou předány na jejich výstup bez změny. Vstupní hodnoty každého uzlu skryté vrstvy a výstupní vrstvy jsou lineárně nakombinovány a předány aktivační funkci, jejíž výsledek je předán na výstup uzlu. 2. zpětná propagace – Výsledek klasifikace je porovnán s očekávaným výsledkem a hodnota chyby se propaguje zpět od výstupní vrstvy po vrstvu vstupní. Při zpětné propagaci hodnota chyby ovlivní hodnoty zkreslení uzlů a váhy hran grafu neuronové sítě. Algoritmus skončí pokud jsou korekce vah hran nebo chyba příliš malé nebo pokud byl proveden nastavený maximální počet iterací. 1 Definice Bayesovy věty je uvedena zde: http://plato.stanford.edu/entries/bayestheorem

5

1. Teoretický úvod do problematiky

1.2.5

Využití vzdálenosti

Metody klasifikace založené na vzdálenosti využívají skutečnosti, že pokud jsou dva vzorky klasifikovány do stejné třídy, tak musí mít něco společného, neboli musí si být podobné. Klasifikace pak spočívá ve zvolení vhodné metriky podobnosti (více v kapitole 1.4.3). Testovaný vzorek je klasifikován do třídy, která obsahuje jemu nejbližší vzorky podle zvolené metriky.

1.3

Druhy klasifikace podle charakteru tříd

Klasifikace dat právě do jedné z předem daných tříd (single-label) znamená, že jednomu vzorku je přiřazena právě jedna třída c z množiny disjunktních tříd C, kde |C| > 1. Pokud |C| = 2, hovoříme o problému binární klasifikace nebo také filtrování, jinak pokud |C| > 2, pak se problému říká klasifikace multiclass. Pokud je jednotlivým vzorkům přiřazena množina tříd Y ⊆ C, poté se klasifikaci říká multi-label, tedy klasifikace prvků do více tříd současně.V určitých případech mohou být třídy, do kterých klasifikujeme, uspořádány v hierarchické struktuře. Pokud do takto uspořádaných kategorií klasifikujeme, říkáme tomu hierarchická klasifikace. Pokud je navíc každému vzorku přiřazeno více prvků z hierarchie současně, hovoříme o vícenásobné hierarchické klasifikaci. Pokud klasifikujeme do více tříd současně, mužeme přiřazené třídy seřadit podle toho, která je pro daný vzorek nejvíce relevantní a tento problém se nazývá ranking.

1.3.1 1.3.1.1

Multi-label klasifikace Jak moc je dataset multi-label?

V některých aplikacích je počet labelů přiřazených jednotlivým prvkům velmi malý v porovnání ku |L|, někdy je tomu naopak. Tato vlastnost může hrát velkou roli při ovlivnění výkonu jednotlivých klasifikačních metod. Můžeme jí vyjádřit metrikami, které se nezývají kardinalita a hustota labelů v datasetu. Nechť D je multi-label dataset skládající se z |D| prvků (xi , Yi ), i = 1..|D|. Kardinalita labelů v D je průměrný počet přiřazených labelů na jeden prvek v D.

|D|

1 X |Yi | LC(D) = |D| i=1 6

(1.2)

1.3. Druhy klasifikace podle charakteru tříd Hustota labelů v D je je průměrný počet přiřazených labelů vydělených počtem všech labelů v D

|D|

LC(D) =

1 X |Yi | |D| i=1 |L|

(1.3)

Kardinalita je nezávislá na počtu všech labelů v D a používá se k vyčíslení počtu různých labelů, které charakterizují prvnky datasetu. Hustota navíc ještě uvažuje počet všech labelů v datasetu. Dva datasety se stejnou kardinalitou a výrazně odlišnou hustotou labelů nemusí vykazovat stejné vlastnosti, jednotlivé klasifikační metody se na nich mohou chovat rozdílně. Vztah mezi těmato dvěma metrikami lze také výjadřit následujícím způsobem:

LC(D) = |L| ∗ LD(D)

1.3.1.2

(1.4)

Metriky pro hodnocení výkonu multi-label klasifikátorů

U single-label klasifikátorů je přesnost jejich klasifikace určena jednoduše tím, jestli je jejich predikce správná nebo chybná a je dána počtem správně oklasifikovaných testovacích instancí ku celkovému testovacích počtu instancí. V případě multi-label klasifikátorů neexistují jen tyto dva stavy, ale jsou zohledněny i případy, kdy je instance správně klasifikována jen do některých z tříd, do kterých spadá. Nechť H je klasifikátor, D je dataset testovacích dat skládající se z |D| instancí (xi , Yi ), kde i = 1..|D|, Yi ⊆ L. L je disjunktní množina všech vyskytujících se tříd. Zi = H(xi ) je množina predikovaných tříd pro instanci x klasifikátorem H, 4 je operátor symetrické diference. Hammingova chybová funkce [1] udává procento špatně klasifikovaných tříd ku celkovému počtu tříd, kterými byla data v testovacím datasetu anotována:

|D|

1 X Yi 4 ∩Zi HammingLoss(H, D) = |D| i=1 |L|

(1.5)

Tato chybová funkce byla modifikována i pro hierarchickou strukturu tříd [2]. Postupně je ověřena správnost predikovaných tříd od horních pater hie7

1. Teoretický úvod do problematiky rarchie, přičemž objeví-li se chybně klasifikovaná třída, celý její podstrom již není dále do výpočtu chybové funkce zahrnut. Nechť anc(l) je množina všech uzlů následníků uzlu l v hierarchii, potom je tato chybová funkce definována následovně:

1 X |l : l ∈ Yi 4 Zi , anc(l) ∩ (Yi 4 Zi ) = θ| |D| (1.6) Další běžně používané metriky [11]:

HierarchicalLoss(H, D) =

|D|

Accuracy(H, D) =

1 X Yi ∩ Zi |D| i=1 Yi ∪ Zi

(1.7)

|D|

1 X Yi ∩ Zi P recision(H, D) = |D| i=1 Yi

(1.8)

|D|

Recall(H, D) =

1 X Yi ∩ Zi |D| i=1 Zi

(1.9)

Dále existují metriky [11] pro ranking predikovaných tříd jako je: 1. One-Error – udává kolikrát není třída predikovaná jako nejrelevantnější vůbec obsažena v množinách tříd do kterých instance spadají 2. Coverage – udává, jak daleko průměrně musíme postoupit v seřazeném seznamu predikovaných labelů, abychom pokryli všechny relevantní 3. Ranking loss – vyjadřuje, jak často jsou nerelevantní třídy řazeny výše než relevatní

1.3.2

Hierarchická klasifikace

V této časti jsou popsány základní přistupy ke klasifikaco do hierarchicky uspořádaných tříd. 8

1.3. Druhy klasifikace podle charakteru tříd 1.3.2.1

Transformace problému

Jedna z možností, jak se vypořádat s hierarchicky uspořádanými třídami je transformovat hierarchii na plošnou strukturu, pro kterou je navrženo mnoho známých algoritmů, které jsou schopny dosáhnout dobrých výsledků. Tento přístup však nevyužívá všechny informace, které poskytuje hierarchie tříd, neboť jedním během algoritmu rovnou rozhodne o příslušnosti do tříd v nejnižším patře a tím pádem do všech jejich nadtříd.

Obrázek 1.1: Transformace hierarchické struktury na plošnou

1.3.2.2

Lokální hierarchie

Použitím této metody dekomponujeme problém na několik samostatných na sebe navazujících klasifikačních problémů. 9

1. Teoretický úvod do problematiky

Obrázek 1.2: Rozklad struktury na lokální hierarchie

Pro každé patro hierarchie, krom posledního, je sestrojeno tolik klasifikátorů, kolik obsahuje tříd a tyto klasifikátory rozhodují o příslušnosti instance pouze do tříd, které jsou přímými potomky daných tříd. Tedy první klasifikátor rozhodne o příslušnosti do nějakých z tříd A,B,. . . K a řekněme, že určil třídy A a B jako relevantní. Poté jsou zavolány klasifikátory, které rozhodnou, do kterých z přímých potomků tříd A resp. B daná instance spadá a tento postup se opakuje až do nejnižších pater hierarchie. Stejně jako v prvním případě se zde uplatňují algoritmy určené pro plošnou strukturu kategorií. Nevýhodou tohoto přístupu je šíření chyby, tedy pokud se klasifikátor zmýlí v horním patře hierarchie, je chyba propagována až do pater nejnižších.

1.3.2.3

Globální hierarchie

Při použití tohoto přístupu, je s hierarchií tříd pracováno jako s celkem a je vytrénován pouze jeden klasifikátor, který rozhodne o příslušnosti do všech relevantních tříd pro danou instanci. Navíc oproti první metodě, kde byla metoda pouze transformována na plošnou strukturu, jsou zde zachovány informace o hierarchických vztazích mezi třídami a nelze použít algoritmy určené pro plošnou strukturu kategorií. Konstrukce klasifikátoru je značně složitější, než v předchozích případech a při každé změně struktury hierarchie je klasifikátor nutné vytrénovat znovu. 10

1.4. Text mining

1.4

Text mining

Text mining spadá do souboru dataminingových metod, tyto metody však pracují s čísly, případně s nominálními hodnotami, zatímco text mining pracuje s nestrukturovaným textem, lze ho tedy definovat jako proces vytěžení cenné informace z textu. Základními úlohami text miningu jsou klasifikace textových dokumentů a shlukování.

1.4.1

Klasifikace textových dokumentů

Klasifikace textových dokumentů je příkladem supervizovaného učení, kdy se snažíme vytvořit pravděpodobnostní model funkce, která mapuje dokumenty do jednotlivých předem daných tříd. U supervizovaného učení je potřeba algoritmu nejdříve předložit sadu vzorků, které jsou již oklasifikovány. Tato množina se nazývá trénovací data. Obecně platí, že čím více jsou trénovací data reprezentativní, tím lepšího výkonu klasifikátoru dosáhneme. Dále je také často lepší, zahrnout co největší sadu vzorků, protože je pravděpodobné, že poté bude trénovací množina více odrážet skutečné rozložení dat jako celku. Sada vzorků, která je použita pro testování výkonu klasifikátorů, se nazývá testovací množina a tyto vzorky nesmí být obsaženy v množině trénovací. Aby bylo možné lépe měřit přesnost klasifikace modelu, je původní sada dat rozdělena do několika oddílů, ze kterých jsou pak různě skládána trénovací a testovací data pro jednotlivé modely. Chyba klasifikace je pak spočtena jako průměrná chyba všech vytvořených modelů. Tomuto postupu se říká křížová validace a pokud je původní soubor dat rozdělen například na 5 částí, hovoříme o 5ti násobné křížové validaci.

1.4.2

Shlukování textových dokumentů

Shlukování textových dokumentů je proces, který nespoléhá na trénovací množinu dat. Místo toho využívá metriky vyjadřující podobnost či rozdíl vzorků, která je postavena čistě na obsahu porovnávaných vzorků. Pokud se po ohodnocení dat jejich vzájemnou podobností objeví nějaké shluky, tedy skupiny vzorků které si jsou vzájemně podobné a zároveň rozdílné od ostatních, jsou tyto vzorky klasifikovány na základě příslušnosti do určitého shluku, který vyjadřuje nějakou ze tříd (ne nutně předem danou). 11

1. Teoretický úvod do problematiky

1.4.3

Metriky podobnosti textových dokumentů

Pokud chceme porovnávat textové dokumenty nebo obecně data s velkou přesností, je potřeba definovat správnou metriku, která dokáže vzdálenost resp. podobnost každé dvojice vzorků. Existuje několik různých definic podobnosti, které se k tomuto účelu používají jako například nejznámější Euklidovská vzdálenost. V případě textových dokumentů není úplně zřejmé, která z metrik je nejefektivnější, velmi záleží na charakteru dat. V [21] byl proveden experiment, který porovnává několik často používaných metrik na několika datasetech s různými vlastnostmi obsahující textové dokumenty a ukazuje se že Jaccardův koeficient a kosinová podobnost jsou velmi vhodné, naopak Euklidovská příliš ne. Většinou je efektivita metriky závislá na typu dat či kontextu problému, takže neexistuje žádná univerzálně nejlepší pro všechny problémy textminingu. Abychom mohli daný výpočet vzdálenosti považovat za metriku, musí splňovat následující podmínky: 1. Vzdálenost mezi dvěma body musí být nezáporná, tedy d(x, y) ≥ 0. 2. Vzdálenost mezi dvěma body je 0 pouze pokud jsou identické. 3. Vzdálenost musí být symetrická, tedy d(x, y) = d(y, x). 4. Musí být splněna trojúhelnkíková nerovnost, tedy d(x, z) ≤ d(x, y) ≤ d(y, z).

12

1.4. Text mining 1.4.3.1

Euklidovská vzdálenost

Euklidovská vzdálenost je standardní metrika používaná pro geometrické problémy. Je definována jako:

m X

De (ta , tb ) = (

|wt,a − wt,b |2 )1/2

(1.10)

t=1

kde T = t1 , ..., tm je se množina slov. 1.4.3.2

Kosinová podobnost

Pokud jsou dokumenty vyjádřeny jako vektory, podobnost dvou dokumentů odpovídá jejich korelaci a ta je zde vyjádřena jako kosinus úhlu, který svírají. Kosinová podobnost je nejčastější metrika aplikovaná při porovnávání textových dokumentů. Máme-li dva dokumenty ta a tb , potom jejich kosinová podobnost je vyjádřena jako:

SIMc (ta , tb ) =

ta ∗ tb |ta | × |tb |

(1.11)

kde ta a tb jsou m-dimenzionální vektory z množiny slov T = t1 , ..., tm . Výsledkem je tedy nezáporné číslo ohraničené hodnotami 0 a 1 včetně. Velmi důležitou vlastností kosinové podobnosti je, že její hodnota nezáleží na délce dokumentů, jinými slovy pokud spojíme několik identických kopií do jednoho dokumentu, bude kosinová podobnost každé kopie a nově vytvořeného dokumentu nulová. Dále vememe-li nový, odlišný dokument, bude jeho vzdálenost jak od jednotlivých kopií, tak od dokumentu vzniklého jejich spojením stejná.

13

1. Teoretický úvod do problematiky 1.4.3.3

Jaccardův koeficient

Jaccardův koeficient vyjadřuje podobnost jako podíl průniku a sjednocení dvou objektů. U textových dokumentů porovnává součet vah společných slov ku součtu vah slov, které se vyskytují právě v jednom z dokumentů.

SIMJ (ta , tb ) =

ta · tb |ta |2 + |tb |2 − ta · tb

(1.12)

Výsledkem je jako u předchozí metriky také nezáporné číslo mezi 0 a 1 včetně. Pokud je to 0, ta = tb , pokud 1 tak dokumenty nemají žádná společná slova. 1.4.3.4

Pearsonův korelační koeficient

Pearsonův korelační koeficient lze v kontextu textových dokummnetů formulovat jako:

m SIMP (ta , tb ) = s [m

m P

t=1 m P t=1

kde T Fa =

m P t=1

wt,a a T Fb =

2 × wt − T F × T F wt,a a b b

2 wt,a

m P

−

T Fa2 ][m

m P t=1

(1.13) 2 wt,b

−

T Fb2 ]

wt,b . Výsledkem jsou hodnoty mezi -1 a 1

t=1

včetně, kde 1 znamená, že prvky jsou identické.

1.4.4

Transformace textových dokumentů

Tato část popisuje obvyklé kroky nutné k převedení kolekce textových dokumentů na jejich vektorovou reprezentaci, která je vstupem pro klasifikační či shlukovací algoritmy. 1.4.4.1

Lexikální analýza a stop-slova

Lexikální analýza identifikuje jednotlivá slova a sousloví v textu dokumentu. Pro získání použitelných dat pro text minig je nutné z textu odstranit interpunkční znaménka, netisknutelné znaky a stop-slova a převést tak dokument na sadu jednotlivých termů. 14

1.4. Text mining Stop-slova jsou slova, která nemají žádnou informační hodnotu. Jde především o spojky, přeložky, částice nebo neplnovýznamová slovesa. Příkladem často odstraňovaných slov, které nenesou v češtině žádný význam jsou: a, u, i, v, z, k, že, se, než, tímto, budeš, budem, byli, jseš, můj, svým, tomto, tohle, tuto, tyto, jej, zda, proč, máte, tato, kam, tohoto, kteří, mi, nám, tomu, tomuto, mít, nic, proto, kterou , byla, toho, protože, asi, ho, naši, tím, takže, svých, její, svými, jist, tu, této, bylo, kde, ke, právě, ji, nad, nejsou, pod, mezi, přes, ty, pak, vám, ani, když, jsem, aby, jsme... 1.4.4.2

Lemmatizace a stemování

Lematizace je proces, který se snaží slova a sousloví vyskytující se v textu v různých tvarech daných gramatickými kategoriemi (pád, číslo, rod,...) převést na jejich základní gramatický tvar (lemma). Stemování je proces, který se snaží slova a sousloví vyskytující se v textu v různých tvarech daných gramatickými kategoriemi převést až na kořen či kmen slova. Odstranění stop-slov a převedení zbylých termů na lemmata popř. až na kořen či kmen slova slouží k redukci dimenzionality vstupních dat pro algoritmy text miningu. Vstupní slovo

Lemma

Kmen slova

Kořen slova

stroj

stroj

stroj

stroj

stroje

stroj

stroj

stroj

strojní

strojní

strojní

stroj

strojníci

strojník

strojník

stroj

strojaři

strojař

strojař

stroj

nástrojařce

nástrojařka

nástrojařka

stroj

strojovně

strojovna

strojovn

stroj

nástrojem

nástroj

nástroj

stroj

výstroje

výstroj

výstroj

stroj

nejnastrojenější

nastrojený

nastrojen

stroj

nestrojil se

nestrojit

stroj

stroj

Tabulka 1.1: Lemmatizace – ztráta významu x redukce dimenzionality

U řídkých dat je otázka, jak moc dimenzionalitu redukovat, na jednu stranu 15

1. Teoretický úvod do problematiky je vhodné zachovat určitou rozličnost a význam slov, což převedením na základní tvar můžeme částečně ztratit, na druhou stranu to zase pomůže v určování podobnosti mezi dokumenty, která se jinak u řídkých dat hůře určuje. Tabulka 1.1 ukazuje příklad převodu původně různě odlišných slov až na jejich společný kořen. Pokud převedeme vstupní slovo pouze na lemma, význam zůstane přesně zachován, ale u řídkých dat, tedy v tomto případě u krátkých článků je velká pravděpodobnost, že nebude nalezena dostatečná podobnost v článcích, které se týkají podobného tématu. Například vstupní slova strojník a strojovna mají odlišná lemmata a kořen slova stejný, přitom články obsahující tato slova budou pravděpodobně hovořit o stejném tématu, a proto by bylo vhodné převádět v tomto případě až na kořen slova. Opačným příkladem ale může být například nestrojit se a nástrojem, zde jsou opět lemmata různá ale kořen slova stejný, ale zde by naopak bylo spíše vhodné vstupní slova převést pouze na lemmata, neboť na základě těchto slov pravděpodobně články o stejném tématu hovořit nebudou. 1.4.4.3

Tvorba příznakových vektorů

Důležitou vlastností je, jak je vůbec dokument reprezentován. Typickou reprezentací jsou množiny disjunktních slov, kde každé slovo odpovídá jedné dimenzi ve výsledném prostoru a každý dokument se pak stává vektrorem obsahujícím nezáporná čísla v každé dimenzi. Zde se používá například frekvence jednotlivého slova v rámci dokumentu jako váha dané dimenze. Pokud tedy D = d1 , ..., dn je množina dokumentů a T = t1 , ..., tm je množina disjuktních termů vyskytujících se v D, poté je je dokument reprezentován m-dimensionálním vektorem td . Pokud tf (d, t) udává frekvenci slova t v dokumentu d, poté vektorová reprezentace dokumentu d je

td = (tf (d, t1 ), ..., tf (d, tm ))

(1.14)

Počet výskytů slova v dokumentu však nemusí být vždy důležitý k určování podobnosti. Například existují slova, která se v textech vyskytují často jako například slovo „být“ ve všech jeho tvarech a mohou tak ovlivňovat výpočet podobnosti popsaný výše. Proto se často používá sofistikovanější způsob reprezentace vah jednotlivých slov TF-IDF, což je podíl četnosti slova v dokumentu a převrácené četnosti slova ve všech dokumentech. TF složka vyjadřuje, jak často se slovo vyskytuje v dokumentu. Idf složka reprezentuje 16

1.4. Text mining „důležitost“ slova. Čím častěji se slovo vyskytuje v dokumentech, tím méně je důležité (slovo, které se vyskytuje ve všech dokumentech, jako například v angličtině člen „the“ nebo české již uvedené „být“, je většinou pro vyhledávání nepoužitelné). IDF pro slovo t spočítáme podle vzorce [4]:

idft = log

|D| |{j : tt ∈ dj }|

(1.15)

kde |D| je počet dokumentů, ve kterých hledáme a |{j : tt ∈ dj }| je počet dokumentů, které obsahují slovo t.

1.4.5

Řídké matice a jejich ukládání

Řídká matice není matematický pojem, ale říká se že matice je řídká právě tehdy, když má nejvýše 5% nenulových prvků. Obecně řídkými maticemi rozumíme matice, která mají velké procento nulových prvků. Těmito maticeni se zabýváme obvykle pokud mají rozměry v řádech tisíců, desetitisíců či vyšších. Výpočty s takto velkými strukturami jsou velice náročné, a to jak z hlediska paměti, tak i potřebného výpočetního času. Pokud zpracovávané matice jsou ve výše uvedeném smyslu řídké, výpočet vede k ukládání velkého množství nul do paměti a k následnému plýtvání výpočetním časem, čemuž lze zamezit efektivní reprezentací těchto matic. Existuje několik způsobů, jak řídké matice efektivně reprezentovat, jednou z typických je metoda komprimovaných řádků, kterou jsem se také rozhodl využít v této práci, neboť příznakové vektory, které reprezentují textové dokumenty jsou zpravidla velmi řídké. Informace jsou uloženy v polích, tedy v souvislých paměťových blocích. Pole val obsahuje jednotlivé nenulové prvky matice seřazeny řádek po řádku tak jako v původní matici. Pole col_ind obsahuje sloupcové indexy příslušných prvků matice z pole val. Pokud val(k) = ai,j , poté col_ind(k) = j. Pole row_ptr obsahuje pozice v poli val, které udávají začátky nových řádků a platí, že pokud val(k) = ai,j , poté row_ptr ≤ i < row_ptr(i + 1). 17

1. Teoretický úvod do problematiky                

10 0 0 0 −2 3

9 0 0

0

0

7 8 7

0

3

0 8 7

5

0

9 0 9

9

0

4 0 0

2



0   3  

    0    13   

0 

−1

Obrázek 1.3: Příklad matice reprezentované metodou komprimovaných řádků

Z obrázku 1.3 je vidět, že v tomto případě moc paměti uspořeno nebylo, naopak použití metody komprimovaných řádků v tomto případě je spíše paměťově kontraproduktivní, tento příklad slouží pouze pro ilustraci principu. Budeme-li mít matice či vektory mnohonásobně vyšší dimenze, což v případě shlukování textových dokumentů máme a pracujeme-li s množinou slov z přirozeného lidského jazyka, tedy matice(vektory) jsou i velmi řídké, je tento způsob reprezentace velmi efektivní.

1.5

Metody multi-label klasifikace textových dokumentů

Metody multi-label klasifikace obvykle dělíme do dvou skupin: transformace problému a adaptování algoritmu. Metody založené na transformaci problému převádí problém na jeden nebo více problémů, které klasifikují single-label data, tedy pouze do jedné z tříd. Po převedení jsou data klasifikována vytvořenými klasifikátory a výsledky jejich predikce převedeny zpět na multi-label predikci. Metody založené na adaptaci algoritmu upravují již známé algoritmy 18

1.5. Metody multi-label klasifikace textových dokumentů pro klasifikaci single-label dat tak, aby mohly klasifikovat do více tříd současně bez nutnosti problém nějak transformovat.

1.5.1

Transformace problému

Nechť L = λj : j = 1..M značí konečnou množinu tříd v problému multi-label klasifikace a D = (xi , Yi ), i = 1..N značí množinu trénovacích dat, kde x je příznakový vektor a Yi ⊆ L je množina tříd i-tého prvku. Existuje několik poměrně jednoduchých transformací, které lze použít k tomu, abychom převedli multi-label problém na single-label problém.

1. Transformace ignore – vynechá všechny prvky patřící do více tříd 2. Transformace copy – nahradí každý prvek (xi , Yi ) spadající do více tříd, |Yi | prvkama (xi , λj ) pro všechna λj z Yi 3. Trasformace select – množina Yi nahrazena jedním z jejích prvků například nejpočetnějším napříč všemi (select-max), nejméně početným (select-min) nebo náhodným z množiny Yi (select-random)

Užitím všech výše zmíněných přístupů však přicházíme o informace, čili výkon klasifikátorů založený na těchto metodách není příliš optimální.

1.5.1.1

Binary relevance

Základní transformační metoda, kde nedochází ke ztrátě informací. Je založená na vytvoření |L| binárních klasifikátorů Hc : X → c, ¬c pro každý feature vektor. Původní dataset je transformován do |L| datasetů, kde každý obsahuje všechny původní příznakové vektory označené c pokud prvek spadal do třídy c a ¬c pokud nespadal. Vzorek

Třída 1

Třída 2

1

x

x

2

x

Třída 3

x

Tabulka 1.2: Příklad multi-label datasetu

19

1. Teoretický úvod do problematiky Vzorek

Třída 1

1

x

¬Třída 1

2

Vzorek

Třída 2

1

x

x

Vzorek

2

Třída 3

x

¬Třída 3

1 2

¬Třída 2

x x

Tabulka 1.3: Tři datasety vytvořené metodou binary relevance

Pokud klasifikujeme nový vzorek x touto metodou, dostaneme sjednocení výstupů všech |L| klasifikátorů, tedy:

H(x) =

[

l : Hl (x) = l

(1.16)

l∈L

1.5.1.2

Label powerset

Další poměrně rozšířená metoda, která zachází s každou množinou tříd, do které jednotlivé trénovací vzory spadají jako s jednou třídou. Pokud klasifikujeme nový vzorek, klasifikátor vrátí nejpravděpodobnější třídu (odpovídající jedné z množin tříd do kterých spadají trénovací vzory). V [13] je navržen algoritmus RAKEL, pro snížení výpočetní složitosti této metody, která je jinak až exponenciální. 1.5.1.3

Ranking by pairwise comparison

Metoda, která transformuje dataset na datasetů, kde každý obsahuje právě jednu z dvojic tříd (ci , cj ), 1 ≤ i ≤ j ≤ N . Každý ze vzorů v těchto datasetech je označen jako příslušný právě do jedné ze dvou daných tříd. Pro každý dataset je vytvořen a vytrénován binární klasifikátor. Pokud klasifikujeme nový prvek, použijeme všechny klasifikátory, čímž dostaneme výslednou množinu tříd, do kterých daný prvek spadá, která je navíc seřazená podle jejich rele20

1.5. Metody multi-label klasifikace textových dokumentů vance k danému prvku a to podle počtu klasifikátorů, které pro dané třídy rozhodly.

1.5.2

Adaptace algoritmu

V této části jsou uvedeny metody, které jsou založené na adaptaci již existujícího algoritmu pracujícího se single-label daty, používají se k práci s textovými dokumenty. 1.5.2.1

ML-kNN

ML-kNN [12] je verze klasického kNN algoritmu uzpůsobená pro multi-label data. Modelově se tato metoda chová jako Binary relevance, ale navíc používá kNN algoritmus nezávisle pro každou třídu c. Najde k nejbližších sousedů testovacímu prvku s tím, že uvažuje pouze ty, u kterých je jedna z tříd do které spadají právě c. Hlavním rozdílem oproti klasickému algoritmu kNN použitému na problém transformovaný pomocí Binary relevance je to, že používá tzv. prior a posterior probabilities. Tato metoda je také schopná seřadit predikované třídy u testovacích prvků podle jejich relevance k danému prvku, tedy řešit problém rankingu. Nechť prvek x spadá do množiny Y ⊆ L labelů a yx je vektor kategorií prvku x, kde l-tá složka yx (l)(l ∈ L) nabývá hodnoty 1 pokud l ∈ Y jinak nabývá hodnoty 0. Dále nechť N (x) je množina k nejbližších sousedů prvku x nalezená v množině trénovacích dat. Poté je na základě labelů těchto sousedů vektor definovaný jako:

Cx (l) =

X

ya (l), l ∈ L

(1.17)

a∈N (x)

kde Cx (l) značí počet sousedů prvku x patřících do l-té třídy. Nechť H1l je vlastnost, že x spadá do kategorie l a H0l , že x nespadá do kategorie l. Dále nechť Ejl (j ∈ 0, 1, ..., k) značí vlastnost, že mezi k nejbližšími sousedy x je přesně j instancí, které mají label l, T je trénovací množina dat, t je testovaný prvek a s je parametr udávající vliv prior pravděpodobnosti. Pseudokód ML-kNN lze poté zapsat následovně:

[yt , rt ] = M L − KN N (T, k, t, s) 21

1. Teoretický úvod do problematiky %Výpočet priori pravděpodobností P (Hbl ) (1) for l ∈ Y do m P

(2) P (H1l ) = (s +

i=1

yx (l))/(s × 2 + m); P (H0l ) = 1 − P (H1l );

%Výpočet posteriori pravděpodobností P (Ejl |Pbl ) (3) Identify N (xi ), i ∈ {1, 2, ..., m}; (4) for l ∈ Y do (5)

for j ∈ {0, ..., k} do

(6)

c[j] = 0; c0 [j] = 0;

(7)

for i ∈ {1, ..., m} do P

a ∈ N (xi )ya (l)

(8)

δ = Cx (l) =

(9)

if (yxi (l) == 1) then c[δ] = c[δ] + 1;

(10)

else c0 [δ] = c0 [δ] + 1;

(11) (12)

(13)

for j ∈ {0, ..., k} do P (Ejl |H1l ) = (s + c[j])/(s × (k + 1) +

k P

c[p]);

p=0

P (Ejl |H10 ) = (s + c0 [j])/(s × (k + 1) +

k P c0 [p]); p=0

%Výpočet yt a rt (14) Identify N (t) (15) for l ∈ Y do (16)

Ct (l) =

P

ya (l);

a∈N (t)

(17)

yt (l) = argmaxb∈0,1 P (Hbl )P (ECl t (l) |Hbl )

(18)

rt (l) = P (H1l |ECl t (l) ) = (P (H1l )P (ECl t (l) |H1l ))/P (ECl t (l) ) = (P (H1l )P (ECl t (l) |H1l ))/(

22

P b∈{0,1}

P (Hbl )P/P (ECl t (l) |Hbl )

1.6. Aktivní učení 1.5.2.2

MLSVM

V [10] byl přizpůsoben algoritmus Support vector machines pro multi-label klasifikaci. Hlavní myšlenkou je v první fázi rozšířit původní dataset o |L| příznaků obsahujících predikce binárních klasifikátorů. V druhé fázi je vytrénováno |L| nových binárních klasifikátorů pomocí už rozšířeného datasetu z první fáze. Pro klasifikaci nové instance jsou použity nejdříve klasifikátory z první fáze, a potom na jejich výstupy aplikovány klasifikátory z druhé fáze, tedy jedná se kombinaci více klasifikátorů nazývanou též stacking [16]. 1.5.2.3

RankSVM

RankSVM [17] je algoritmus založený na SVM [17], který řeší problém problém rankingu, tedy seřazení predikovaných tříd pro instanci podle jejich relevance. Je založen na lineárním modelu, který se snaží minimalizovat cenovou funkci a přitom udržovat maximální okraj (margin) [15] mezi separovanými oblastmi. Jako cenová funkce je zde použita RankingLoss. Nevýhodou ranking algoritmů je to, že neprodukují množinu labelů, ale dokáží ji pouze seřadit. 1.5.2.4

BoosTexter

BoosTexter [20] je obecný systém pro kategorizaci textu, který používá techniku kombinaci modelů boosting. Hlavní myšlenkou je zkombinovat několik jednoduchých ale velice přesných kategorizačních pravidel do jednoho vysoce přesného a komplexního. Tyto pravidla jsou trénovány postupně, každé obvykle na vzorcích, které bylo obtížné klasifikovat předcházejícím pravidlem. Je založen na algoritmu AdaBoost, konktrétně jeho multi-label rozšířeních AdaBoost.MH a AdaBoost.MR.

1.6

Aktivní učení

Kategorizovat trénovací data, tedy přiřadit jim odpovídající labely, je poměrně časově náročné, obzvláště pokud bychom to měli dělat manuálně, což je v případě textových dokumentů někdy nevyhnutelné. Aktivní učení je metoda, která pomáhá minimalizovat toto usilí tím, že k trénovací množině kategorizovaných dat je přidána další, obvykle mnohem větší množina nekategorizovaných dat. Na kategorizovaných datech je vytrénován klasifikátor. Z nekategorizovaných dat jsou poté iterativně vybírány vzorky podle různých selekčních strategií, oklasifikovány a přidány do první množiny. V principu jsou vybírány právě ty vzorky, u kterých je nejnižší pravděpodobnost, že budou klasifikovány 23

1. Teoretický úvod do problematiky chybně. Existuje už poměrně mnoho prací zabývajících se aktivním učením v případě single-label dat [17] [18], kde se předpokládá, že každý vzorek může být klasifikován právě do jedné třídy. Velmi často se k určení pravděpodobnosti příslušnosti vzorku do daných tříd používá metoda one-vs-all [3] a to i u multi-label problémů. V [9] je navržena na multi-label textových datech úspěšná metoda, která k výběru vzorků, které mají být klasifikovány používá multi-label verzi SVM algoritmu.

24

Kapitola

Návrh Tato část rozebírá postupy a rozhodnutí, které jsem učinil v závislosti na požadavcích a cílech této práce. Tedy navrhnout a implementovat systém, který by byl schopen spravovat zpravodajské články a jejich zařazení do rubrik, s tím, že hlavním přínosem je automatická kategorizace článků do více rubrik současně a také detekce nových témat či spojitostí, o kterých se aktuálně píše například i napříč různými rubrikami.

2.1

Architektura aplikace

První otázkou je volba architektury aplikace. Vzhledem k tomu, jeden z hlavních požadavků byl, aby celý proces od předzpracování dat, až po publikaci výsledků na webu probíhal v rámci jedné akce, je nutné vytvořit poměrně komplexní systém, jehož součástí musí být webový server. Zde je vhodné uložit hlavní datový zdroj, kde budou umístěny všechny články v surovém i předzpracovaném stavu, tedy jak originální texty, tak jejich vektorové reprezentace a také rubriky, které jim jsou přiřazovány. Výhodou tohoto modelu je, že výsledná data mohou být v reálném čase k dispozici na webu. Jelikož předzpracování dat a trénovaní klasifikačního modelu jsou poměrně výkonově i paměťově náročné operace, tak jsem se vzhledem k mým možnostem rozhodl vytvořit tuto část aplikace jako desktopového klienta, který vzdálený datový zdroj pouze žádá o data a vrací výsledky jejich zpracování. Zde by bylo elegantnější, avšak mnohem nákladnější, použít cloudovou službu, kde je možné poskytovaný výkon serveru poměrně dobře škálovat v závislosti na aktuálních potřebách aplikace a zároveň by bylo vše pohodlně dostupné z webového rozhraní. 25

2

2. Návrh

Obrázek 2.1: Návrh architektury aplikace

2.2

Funkce uživatelského rozhraní

Základní funkcí uživatelského rozhraní by měl být určitě přehled o článcích v systému a možnost s nimi manipulovat. Myslím, že by zde tedy nesmí chybět seznam všech dostupných rubrik v systému a přehled článků v nich obsažených. Dále možnost zobrazit si detaily jednotlivých článků, které musí obsahovat titulek, text článku a rubriky, do kterých daný článek spadá. Všechny tyto údaje jsou editovatelné. Dále je nutné u detailu článku zobrazit doplňující informace jako je autor, datum publikace a odkaz na web. Také je potřeba vkládat a mazat nové články a rubriky. 26

2.2. Funkce uživatelského rozhraní

Obrázek 2.2: Náčrt uživatelského rozhraní pro správu článků

Na obrázku 2.2 je náčrt uživatelského rozhraní, které jsem navrhl pro účely správy článků a rubrik popsané výše. Veškeré ovládací prvky jsem pro přehlednost a rychlou manipulovatelnost vložil do jednoho formuláře. Dále je nutné, aby systém dokázal nově vložený článek, případně sadu článků, vícenásobně kategorizovat do dostupných rubrik. Klasifikace musí být ovliněna aktuálními daty v systému, čili je důležité brát ohled na veškeré uživatelem manuálně provedené změny, za účelem zpřesnění budoucí klasifikace modelu. Těmto požadavkům jsem přizpůsobil proces klasifikace popsaný v kapitole 2.5. Poslední požadovanou funkcionalitou je detekce témat, o kterých se aktuálně píše, jak v rámci tak i napříč rubrikami. Na základě toho by měl mít uživatel možnost vytvořit novou rubriku a přiřadit do ní příslušné články vztahující se k nalezenému tématu. Zde jsem navrhl vyjít z podobnosti článků, vložených do systému za poslední týden a detekovat nové shluky tak, že jsou mezi nimi vyhledávány skupiny článků jejichž vzájemná podobnost a přesahuje určitou mez. Ta je nastavitelná, a určuje citlivost detekce. Dále je nastavitelný i minimální počet detekovaných článků. Pro tuto funkci volím pouze textovou formu výpisu a uživateli jsou po každém přetrénování modelu prezentovány detekované shluky ve formě seznamu článků a 10ti nejčastějších klíčových slov, které je spojují. 27

2. Návrh

2.2.1

Charakteristika zpracovávaných dat

Zdrojová data, která jsem použil v této práci, jsou příkladem reálného obrazu rozložení zpravodajských článků na českém zpravodajském portálu. Je použito 1570 článků získaných z webu portálu Blesk.cz. Jedná se o články umístěné na webu, které jsou dostupné přes hypertextové odkazy. Nejstarší články jsou z roku 2012. Všechny články jsou v českém jazyce a obsahují průměrně kolem 250ti slov a spadají do 72 různých rubrik podle obsahu. Data jsou kategorizována tak, že každý článek spadá právě do jedné rubriky.

Obrázek 2.3: Výčet 30ti rubrik s nejvyšším procentuálním zastoupením článků

Z obrázku 2.3 je vidět, že procentuální rozložení článků v jednotlivých rubrikách je velmi nerovnoměrné. Nejvíce článků obsahují velmi obecné rubriky, naopak specifické rubriky obsahují článků pouze několik. Rubriky jsou organizovány hierarchicky do dvou úrovní. První úroveň je velmi obecná například zprávy, celebrity či rádce. Druhá úroveň je již specifičtější, ale do jaké míry, to je velmi rozdílné, například podkategorie události, počasí či královské rodiny. Do událostí by se tématicky nejspíše dala zařadit polovina všech zpravodajských článků. Všechny články jsou zařazeny pouze do rubrik v druhém patře hierarchie.

2.3

Předzpracování dat

Pro předzpracování dat jsem zvolil použití běžných postupů pro text mining popsaných v kapitole 1.4.4. Tedy tokenizovat text, odstranit nečistoty a stop28

2.4. Konstrukce klasifikátoru slova, zbylé termy lemmatizovat a jednotlivé dokumenty reprezentovat jako vektory nesoucí hodnoty tf-idf obsažených termů. Dalšími kroky, jak redukovat dimenzionalitu těchto vektorů by mohlo být odstranění diakritiky či převedení lemmat až na kořen slova. Toto sice vede ke ztrátě významu, ale je to zároveň velká šance, jak u takto krátkých článků nalézt alespoň nějakou míru podobnosti, čili jsem se vydal touto cestou. Jelikož čeština obsahuje zhruba 300 000 slovních kořenů, a každý článek průměrně kolem 100 slovních kořenů, pročež počet používaných slovních kořenů ve zpracovávaných zpravodajských článcích je kolem 60 – 70 000, je zřejmé, že vektory reprezentující články jsou velmi řídké, tedy plné nul. Reprezentovat je prvek po prvku včetně těch nulových by bylo jak paměťově, tak i operovat s nimi výkonově velmi náročné a proto jsem pro jejich reprezentaci zvolil použití metody komprimovaných řádků viz kapitola 1.4.5.

2.4

Konstrukce klasifikátoru

V této části zvolím a popíšu přístup, jak zpravodajské články popsané v kapitole 2.2.1 klasifikovat do více rubrik současně.

2.4.1

Volba algoritmu

Nalezení algoritmu, který by dosahoval nejlepších výsledků v doméně zpravodajských článků není jednoznačné a velmi záleží na konkrétních datech, s kterými pracuje. V [6] jsou testovány některé metody multi-label hierarchické klasifikace a je zde ukázáno, že tento typ klasifikace je vhodné použít na ryze multi-label a hierarchicky uspořádaná data. V případě dat, s kterými pracuji v této práci není zřejmé, zda obě tyto vlastnosti splňují. Proto jsem některým článkům přiřadil další labely na základě podobnosti s jinými články, které se týkají rozdílného tématu. Tento postup je detailněji popsán v kapitole 4.2.1. Co se týče hierarchického přístupu ke klasifikaci, pro účely této práce určtě nebude vhodné použít globální hierarchie popsané v kapitole 1.3.2.1, kvůli jejich komplexitě a časové náročnosti. Efektivnější a vhodnější je použít rozklad struktury ma lokální hierachie, který je popsán v kapitole 1.3.2.2 a který má podle [6] velmi dobré výsledky na zkoumaných textových dokumentech, avšak pro mnohem vyšší počet kategorií a textových dokumentů v nich obsažených. Pro krátké textové doumenty podle [8] a pro jednodušší hierarchické struktury podle [7] dosahuje dobrých výsledků přístup, který transformuje hierarchii kategorií na plošnou strukturu popsaný v kapitole 1.3.2.1. Vzhledem 29

2. Návrh k jeho nejnižší časové složitosti a také charakteru zpracovávaných dat jsem se rozhodl pro následující implementaci použít tento přístup. Algoritmů pracujících s multi-label daty, které lze uplatnit na plošnou strukturu kategorií existuje velké množství. Kapitola 1.5 popisuje jak ty klasické, tedy které vznikly dříve a multi-label problém transformují na |L| singlelabel problémů, tak i některé modernější přístupy, které dosáhly zajímavých výsledků při klasifikaci textových dokumentů. Jedním z posledních zástupců a také často používaným a testovaným je ML-kNN popsaný v kapitole 1.5.2.1, který v případě klasifikace textových dokumentů dosahuje dobrých výsledků [12][6][11] a na základě toho jsem ho zařadil do implementace.

2.4.2

Trénovací množina dat

Nejdůležitější součástí klasifikace je trénovací množina dat. Je velmi důležité, aby obsahovala sadu článků, které pokrývají co nejrozličnější množinu kombinací rubrik. Pokud trénovací množina nebude obsahovat dostatek článků nebo nebudou rovnoměrně rozložené skrz celé spektrum rubrik, nebude klasifikátor pracovat správně popřípadě dojde k přeučení, tedy budou preferovány nejpočetněji zastoupené rubriky v trénovacích datech. Pokud multi-label klasifikátor bude mět oklasifikovat nějaký prvek dvěma kategoriemi, pak v množině osahující i single-label trénovací data bude existovat několik velmi podobných prvků, kde část bude označena jednou a část druhou z kategorií.

2.5

Proces klasifikace

Pro dosažení požadované funcionality (viz. kapitola 2.2) jsem navrhl následující postup, který je opakován při vložení nového článku do systému, případně manuální editaci článku již vloženého. Není však podmínkou, aby byl opakován po každé z uvedených akcí, může být aplikován i na sadu těchto akcí najednou. 30

2.5. Proces klasifikace

Obrázek 2.4: Integrovaný proces klasifikace

Jako trénovací data jsem zvolil určitý počet unikátních nejmladších článků z každé rubriky, tak aby pokud jeden článek spadá do více rubrik se neobjevil v trénovacích datech vícekrát. Důležité je, aby tento počet, byl u každé rubriky pokud možno stejný, čímž se částečně předejde preučení klasifikátoru, tedy nadměrného vlivu nejpočetněji zastoupených rubrik. Bohužel při vzniku nových rubrik, které obsahují malý počet článků, tento problém nastane. Zde je možné příslušnost do jednotlivých rubrik korigovat manuálně nebo použít nižší hodnotu parametru k, tedy počtu uvažovaných sousedů v algoritmu ML-kNN, čímž se zmenší vliv rubrik, jejichž reprezentati převládají v okolí klasifikovaného vzorku počtem, ale nikoliv podobností. Testovací (klasifikovaná) data jsou nově přidané články, které ještě nebyly klasifikovány popřípadě články, které uživatel manuálně označí znovu ke klasifikaci. Trénovací množina dat se tedy mění jednak s novými články s systému a hlavně také s editací již vložených, ať už se jedná o manuální editaci již přiřazených rubrik nebo změny v textu. Tímto způsobem tedy lze dosáhnout toho, že uživatel může poskytnout klasifikačnímu modelu lepší trénovací data, tedy klasifikovaná podle jeho přání a ovlivnit tak budoucí klasifikaci. Tento přístup také napomáhá tomu, aby největší vliv měly témata, o kterých se v dané rubrice právě píše nebo v blízké minulosti psalo. U takto poměrně krátkých textů je velmi pravděpodobné, že budou chybně klasifikovány články, které se týkají stejných vlastních jmen ci místopisných názvů, ikdyž jinak pojednávají o úplne jiném tématu. Další výhodou tohoto přístupu je 31

2. Návrh částečná eliminace tohoto problému, avšak za cenu menší trénovací množiny.

32

Kapitola

Implementace Celou aplikaci jsem postavil na platformě .NET a je vytvořená tak, aby mohla fungovat samostatně bez použití dalších vzdálených služeb, na jejichž dostupnosti či změnách by byla nějak závislá. Některé náročnější matematické operace včetně trénování a testování modelu jsem napsal v Matlabu a zdrojový kód jsem zkompiloval do dll knihoven v C++, které už mohou být z platformy .NET přímo volány.

3.1

Modul downloader

Tento modul slouží pro hromadné stahování článků z webu, základní zpracování a uložení do databáze. Vstupem je mapa webu vygenerovaná web crawlerem Xenu2 . Z webových stránek je pomocí konfigurovatelných XPath výrazů získáván titulek článku, text, datum publikování a z url poté kategorie. Bylo nutné dbát na to, aby se některé články nestahovaly vícekrát, neboť odkazy na stránkách jsou často cyklické. Po stažení jsou z dat odstraněny případné HTML značky a speciální znaky, aby výsledkem byl opravdu jen surový text.

3.2

Modul preprocessing

Tento modul slouží k předzpracování textů článků a vygenerování jejich příznakových vektorů. Prvním krokem je rozdělit text dokumentů jednotlivé termy pomocí regulárních výrazů, konkrétně podle mezer, tabulátorů, závorek a interpunkčních znamének. Všechny tyto a případné další speciální znaky a nečistoty jsou následně odstraněny. Dále jsem odstranil i čísla, neboť u takto 2

Domovská stránka projektu http://home.snafu.de/tilman/xenulink.html

33

3

3. Implementace poměrně krátkých textových dokumentů by mohla stejná čísla, ikdyž použitá v úplně jiném kontextu, vnášet do porovnání textů velkou míru podobnosti a velmi to tak ovlinit. Dalším krokem je odstranění stop-slov, tedy českých slov nenesoucích žádný význam. Seznam použitých slov je uložen v souboru stopwords.txt na přiloženém CD. Nyní je čas na lemmatizaci zbylých termů, tedy jejich převedení na základní tvar. K tomu jsem použil část open-source knihovny LemmaGen3 , vyvinutou původně pouze pro slovinštinu, avšak následně dále portovanou i pro dalších 11 jazyků včetně češtiny. Stemming jsem implementoval pomocí portace stemmeru pro český jazyk v rámci projektu Snowball4 Příznakové vektory jednotlivých článků jsou vyjádřeny v tf-idf. Tento výpočet je z celého předzpracování textů časově nejnáročnější a při velkém množství zpracovávaných článků je zde na místě určitá optimalizace, která se mi povedla jen z části a to voláním obdoby této funkce v MATLABu, avšak čas potřebný ke zpracování několika tisíc článků stále jde do řádu minut. V tomto formátu jsou data připravená k použití při trénování popř. testování klasifikačního modelu. Je důležité podotknout, že dojde-li ke změně textu libovolného článku, či je vložen do systému vložen článek nový, je třeba celou množinu článků, s kterými bude klasifikátor pracovat, předzpracovat znovu. Zde také vidím prostor pro optimalizaci, neboť při velkém množství článků je při každé drobné změně v datech vše znovu předzpracovávat velmi nákladné.

3.3

Modul MLkNN

Tuto část aplikace jsem napsal v Matlabu, a obsahuje dvě funkce na trénování a testování klasifikátoru pomocí metody ML-kNN, která je popsána v kapitole 1.5.2.1. Algoritmus5 jsem převzal tak jak byl navržen a implementován v [12] s několika úpravami. První úprava se týká metriky podobnosti vektorů, kdy jsem místo originální Euklidovské vzdálenosti zvolil kosinovou podobnost, která se pro tuto doménu hodí více. Dále jsem algoritmus upravil, aby na vstupu přijímal a dále pak zpracovával všechny matice a vektory jako řídké viz kapitola 1.4.5, což by mělo s daty tohoto charakteru zabezpečit rychlejší práci klasifikátoru. 3

Domovská stránka projektu http://lemmatise.ijs.si/ Domovská stránka projektu: http://snowball.tartarus.org/ 5 Originální zdrojový kód ML-kNN algoritmu dostupný z: http://cse.seu.edu.cn/ people/zhangml/files/ML-kNN.rar 4

34

3.3. Modul MLkNN Celý modul jsem zkompiloval do jazyka C++ do dll knihovny, kterou je možné volat z prostředí .NET, tedy tento modul je přímo svázán se zbytkem aplikace.

3.3.1

Funkce train

Tato funkce slouží k trénování ML-kNN klasifikátoru a má tvar: function [Prior, PriorN, Cond, CondN ]= MLKNN_train(train_data, train_target, Num, Smooth) train_data - dvourozměrné pole obsahující jednotlivé příznakové vektory trénovacích prvků train_target - dvourozměrné pole obsahující příslušnost trénovacích prvků do jednotlivých kategorií, train_target(j,i) = 1 pokud i-tý prvek spadá do j-té kategorie jinak train_target(j,i) = -1 Num - počet uvažovaných sousedů Smooth - parametr udávající vliv priori pravděpodobnosti Prior - prior pravděpodobnosti jednotlivých tříd PriorN - negace priori pravděpodobností jednotlivých tříd Cond - pravděpodobnosti pro instance v jednotlivých třídách, že jejich 1,2,...,k sousedů bude patřit do dané třídy CondN - negace pravděpodobností z Cond

3.3.2

Funkce test

Tato funkce slouží k testování ML-kNN klasifikátoru a má tvar: function [Outputs, Pre_Labels] = MLKNN_test(train_data, train_target, test_data, test_target, Num, Prior, PriorN, Cond, CondN) kde train_data,train_target,test_data,test_target jsou stejná data, respektive analogie pro testovací prvky, jako u metody train. Parametry Prior, PriorN, Cond, CondN jsou výstupy funkce train. Outputs - dvourozměrné pole obsahující pravděpodobnosti příslušností testovacích instancí do jednotlivých tříd 35

3. Implementace Pre_Labels - predikované třídy pro jednotlivé testovací instance na základě Outputs

3.4

Modul GUI

Tato část aplikace zaobaluje grafické uživatelské rozhraní, které jsem vytvořil v prostředí Windows Forms. Propojuje funkcionalitu předchozích modulů a uživatelských ovládacích prvků.

Obrázek 3.1: Ukázka grafického uživatelsého rozhraní 1

První částí je výpis rubrik a článků v nich obsažených. Články je možno filtrovat buď podle jednotlivých rubrik, nebo zobrazit výpis všech najednou. Tlačítko „Retrain classifier“ slouží k přetrénování klasifikátoru pomocí aktu36

3.4. Modul GUI álních článků v systému a je spuštěn proces odpovídající návrhu v kapitole 2.5.

Obrázek 3.2: Ukázka grafického uživatelského rozhraní 2

Na obrázku 3.2 je uživatelské rozhraní, které odpovídá návrhu v kapitole 2.2, zobrazující detaily jednotlivých článků. Je zde možné manuálně měnit titulek a text článku a také jeho příslušnost do jednotlivých rubrik. Potom také volba, zda-li má být článek při příštím přetrénování klasifikačního modelu znovu oklasifikován. Tato funkce slouží spíše k testovacím účelům. Dále je přes tuto část rozhraní možné přidávat nové články. 37

3. Implementace

Obrázek 3.3: Ukázka grafického uživatelksého rozhraní 3 Poslední částí formuláře je výpis skupin článků z posledních dní,který jsem vytvořil podle návrhu v kapitole 2.2. Tento výpis napomáhá k detekci nových témat, o kterých se aktuálně píše, a obsahuje články, kterých se téma týká, rubriky do kterých spadají a nejčastější společná klíčová slova, která je charakterizují. Aktuálně je tento časový interval nastaven na týden. Tato funkce napomáhá detekci nových témat napříč všemi rubrikami a na jejím základě je možné poté například založit novou rubriku a inkriminované články do ní přiřadit. Momentálně jsou detekovány shluky o minimální velikosti 3 a všechny články si musí vzájemně odpovídat s kosinovou podobností minimálně 0.075.

38

Kapitola

Analýza a vyhodnocení reálných dat 4.1

4.1.1

Analýza zpravodajských článků z portálu Blesk.cz Vizualizace zdrojových dat

V této části jsem zobrazil data popsaná v kapitole 2.2.1 v prostoru s využitím kosinové podobnosti, jejíž použití je pro klasifikaci textových dokumentů nejběžnější. Ke zpracování textů článků na příznakové vektory je použit modul Preprocessing, který byl popsán v kapitole 3.2. Na obrázku 4.1 je vidět vizualizace těchto článků v prostoru, kterou jsem vytvořil v programu Gephi. 6 Co se týče počtu článků, nejsou zde zobrazeny všechny, ale vzhledem k technickým možnostem tohoto nástroje a také pro větší přehlednost jsem vybral náhodně polovinu článků tak, aby zůstaly poměrově zastoupeny v jednotlivých rubrikách. Uzly vyjadřují články a jejich barva značí rubriku, do které spadají. Tato rubrika je přezata z originální kategorizace na webu potálu Blesk.cz. Bohužel se nepodařilo docílit dostatečné barevné rozmanitosti pro 72 rubrik, proto některé rubriky jsou označeny velmi podobnou barvou, avšak tak, aby ty s největším počtem článků byly dostatečně barevně odlišené.

6

Gephi, open-source software určený pro vizualizaci grafů dostupný z https://gephi.org

39

4

4. Analýza a vyhodnocení reálných dat

Obrázek 4.1: Zobrazení originálně kategorizovaných článků v prostoru s využitím kosinové podobnosti

Obrázek 4.2: Podíl jednotlivých rubrik ve vizualizované množině článků

Jednotlivé hrany mezi uzly udávají míru jejich podobnosti, pro jejíž výpočet jsem použil kosinovou podobnost. Spojeny hranou jsou ty uzly (články), jejichž kosinová podobnost je větší než 0,14. Tato hranice je závislá na charak40

4.1. Analýza zpravodajských článků z portálu Blesk.cz teru dat, pokud zvolím příliš nízkou, při grafickém zobrazení budou jednotlivé shluky splývat. Naopak při vyšším prahu kosinové podobnosti vyjdou najevo jen ty opravdu výrazné shluky. Pro rozložení uzlů ve vizualizaci je použit layout Force Atlas, který přibližuje případně oddaluje uzly úměrně vahám hran, které je spojují. Dále jsou z obrázku 4.1 jsou patrné některé opravdu výrazné shluky, jejichž umístění je mimo hlavní masu článků. Jedná se o články, které se tématicky odlišují od ostatních, čili mezi jejich shlukem a zbytkem článků je minimum vazeb a zároveň jsou si v rámci shluků tématicky velmi podobně. Jinými slovy v rámci shluku obsahují články mnoho společných termů, které se ve zbytku článků příliš nevyskytují. Jedná se napříkad o velkou část článků z kategorie týkající se počasí (červený vpravo), poté několik okrových, zelených a růžových shluků v dolní části pojednávající o nějaké celebritě, kauze kde vytupuje stále několik jmen, politické události či skandálu, jsou to zpravidla silné shluky, které spojují jména osobností. Dalším zajímavým shlukem je skupina článků z několika různých kategorií, které spojují různé násilné události a jejich vyšetřování. Všechny tyto články, ač spadají do rozličných kategorií jsou si vzájemně velmi podobné a tvoří velký silný shluk v levé části. Poté je zde ještě několik malých shluků, kde se také ale vyskytují velmi podobné články a to nejčastěji na témata cestování, věda a technika a kulura. Další skupinou jsou články cca uprostřed grafu, které vytváří velký poměrně řídký shluk a většina z nich má sotva pár sousedů, jejichž podobnost sotva přesahuje určenou mez. Toto jsou bohužel články, které bude velmi obtížné automaticky kategorizovat s momentálně dostupnými daty. Jejich nemalý počet je dán určitě řídkostí dat, všechny články jsou poměrně krátké. Třetí skupinou a to velmi zajímavou z hlediska multi-label klasifikace jsou články ležící na pomezí nekterých ze shluků. V praxi například článek pojednávající o žebříčku nejstahovanějích seriálů na internetu leží mezi shluky týkající se krimi zpráv, kultury a digitálních technologií. Nebo článek o tom, jak bezpečně řídit v mlze, která má v nejbližších dnech nastat stojící na pomezí článků o předpovědi počasí a článků přinášejích rady kolem auta. Pro lepší interpretaci a možnost prohlížení vizualizace jsem graf exportoval a vystavil na webu7 , kde je možné ho lépe prohlížet, maximalizovat a zobrazit si titulky jednotlivých článků, kategorie a při rozkliknutí jsou zvýrazněny hrany, kterými je daný článek svázán s ostatními. 7 Vizualizace rubrik podmnožiny zpravodajských článků dostupná z http://pirklmardp.ulikeit.cz/index.html#Articles2.gexf

41

4. Analýza a vyhodnocení reálných dat

Obrázek 4.3: Export zobrazení originálně kategorizovaných článků do webového rozhraní

4.1.2

Statistika klíčových slov

Tabulka 4.1 zachycuje nejčastěji se vyskytující termy v rámci jednotlivých rubrik. Jedná se o výběr 17 rubrik, které mají největší zastoupení článků. Rubriky, které jsou poměrně konkrétně specifikované většinou obsahují mezi nejčastěji se vyskytujícími slovy pojmy specifické pro danou oblast. Například identifikovat kategorii zpávy-počasí, sport-blesk-sport či digital-internet podle klíčových slov v tabulce by asi nebylo příliš složité. Pak jsou zde ale spíše obecně specifikované kategorie jako celebrity-světové-celebrity nebo zprávyudálosti, které už nespojují klíčová slova, která by jednoznačně vystihla danou oblast. Už jen proto, že například v kategorii zprávy-události si můžeme představit velmi rozličné množství článků, které se navíc budou tématicky prolínat s velkou částí ostatních rubrik.

42

4.1. Analýza zpravodajských článků z portálu Blesk.cz

Kategorie

Nejčastější termy

celebrity-kralovske-rodiny

kate, princ, královský, rodina, vévodkyně, princezna, william, george

celebrity-modni-policie

český, stát, módní, móda, žena

celebrity-svetove-celebrity

herec, fotografie, autor, zpěvák, moci

digital-internet

facebook, google, člověk, sociální, uživatel, síť, autor, moci, fotografie, velký

live-kultura

rok, let, snímek, film, český, jenž, výstava, život, uvést, festival

radce-auto

auto, vůz, moci, řidič, autor, škoda, motor, pojišťovna, rok, muset

radce-cestovani

autor, moci, město, velký, dovolit, dovolený, cena, ostrov, trh, moře

radce-zdravi-a-zivotni-styl-zdravi

bolest, dítě, moci, hlava, problém, zubní, muž, často, člověk, zub

sport-blesk-sport

olympijský, velký, londýn, český, chtít, bolt, metr, všechno, zlatý, hodně

zpravy-chat

den, dobrý, děkovat, chtít, všechno, moci, moc, můj, operace, muset

zpravy-kauza-methanol

alkohol, metanol, člověk, muž, policie, fian, likérka, smrtící

zpravy-krimi

policie, muž, řeknout, policista, žena, soud, vražda, moci, dva

zpravy-pocasi

teplota, stupeň, týden, meteorolog, místo, počasí, den, vítr, noc, sníh

zpravy-politika

blesk, ministr, prezident, ods, vláda, zeman, strana, stát, chtít, moci

zpravy-udalosti

rok, člověk, řeknout, soud, moci, chtít, dítě, stát, autor, český

Tabulka 4.1: Nejčastěji se vyskytující termy ve vybraných rubrikách

43

4. Analýza a vyhodnocení reálných dat

4.1.3

Modularita zdrojových dat

Obrázek 4.4 zachycuje výsledek experimentu, kdy jsem na vizualizaci článků v prostoru užitím kosinové podobnosti z obrázku 4.1 aplikoval algoritmus [22] implementovaný v Gephi, abych porovnal jak moc originální kategorie odpovídají skutečným shlukům. Výsledek experimentu není úplně komplexní, zahrnul jsem pouze 15 rubrik, tedy ty které obsahují minimálně 20 článků a dále je nutné si uvědomit, že metrika, kterou je určována jejich podobnost tedy následně detekovány i shluky vyjadřuje lexikografickou podobnost textů nikoli sémantickou.

Obrázek 4.4: Zobrazení kategorizovaných článků v prostoru pomocí algoritmu na detekci shluků [22]

44

4.1. Analýza zpravodajských článků z portálu Blesk.cz

Shluk

Článků

Zastoupení rubrik

1

172

zpravy-politika (72%) celebrity-ceske-celebrity (12%)

4

151

zpravy-politika (32%) zpravy-krimi (26%) celebrity-ceske-celebrity (21%)

2

94

zpravy-krimi (43%) zpravy-obcansky-zakonik (37%)

3

83

zpravy-krimi (24%) zpravy-udalosti (28%) celebrity-ceske-celebrity (17%) zpravy-politika (13%)

5

52

zpravy-počasí (87%)

6

47

celebrity-ceske-celebrity (78%) zpravy-udalosti (11%)

7

43

celebrity-kralovske-rodiny (85%)

8

38

zpravy-udalosti (63%) zpravy-krimi (28%)

9

32

celebrity-ceske-celebrity (100%)

10

23

celebrity-modni-policie (92%)

Tabulka 4.2: Zastoupení rubrik v 10ti nejobjemnějších shlucích na obrázku 4.4

Tabulka 4.2 ukazuje zastoupení rubrik v 10ti nejobjemnějších shlucích detekovaných algoritmem v předešlém experimentu. V tabulce jsou uvedeny pouze rubriky v nichž je alespoň 10% článků pro snadnější interpretaci. Výsledná vizualizace8 celého experimentu je pro lepší interpretaci umístěna na webu. Jednotlivé barvy uzlů představují detekované shluky. Je zřejmé, že zhruba polovina článků byla zařazena do shluku, kde převládá jedna nebo dvě rubriky. To značí, že pokud bychom na těchto datech vytrénovali klasifikátor, bude pro asi polovinu článků šance, že jim budou s jistotou přiřazeny relevantní labely. Dále to také značí, zvláště u silných shluků, že tam existuje 8 Vizualizace dostupná z index.html#ArticlesModularityClasses.gexf

http://pirklmar-dp.ulikeit.cz/

45

4. Analýza a vyhodnocení reálných dat určité procento článků, které tématicky spadají s větší pravděpodobností do jiné kategorie, než jsou originálně kategorizovány. Například shluk 5 obsahuje 52článků a 87% z nich spadá do kategorie zpravy-pocasi, je tedy velmi pravděpodobné, že zbylých 13% článků se bude počasí také týkat a zasloužili by si kromě své originální kategorie současně spadat i do rubriky zpravy-pocasi. Druhá polovina článků (nezahrnuté v tabulce 4.2)spadá do velmi malých shluků. Z 350ti v detekovaných shluků 330 obsahuje méně jak 7 článků. Tyto články budou naopak pro klasifikátor vytrénovaný na těchto datech velmi těžko správně zařaditelné.

4.2

Testování klasifikátoru

V této sekci jsou provedeny dva experimenty s klasifikátorem, který byl implementován podle poznatků z předchozích částí.

4.2.1

Ohodnocení článků více rubrikami

Tento experiment jsem provedl na datech popsaných v kapitole 2.2.1 a k jejich předzpracování použil modul Preprocessing z kapitoly 3.2. K určení přesnějších výsledků jsem použil 2-násobnou křížovou validaci, tedy jsem data náhodně rozdělil na 2 části , avšak tak, aby zůstalo poměrové zastoupení članků v jednotlivých rubrikách. První polovina sloužila jako trénovací data pro multilabel klasifikátor popsaný v kapitole 1.5.2.1. Jako míru podobnosti jsem použil kosinová podobnost a počet sousedů v ML-kNN algoritmu jsem nastavil na 8. Druhá polovina článků byla klasifikátoru předána jako testovací data. Pokud klasifikátor článku přiřadil nějakou rubriku, která se lišila od té originální s pravděpodobností vyšší než 40%, byla ve výsledku přiřazena článku jako další rubrika, do které spadá. Originální manuálně přiřazené rubriky článkům jsem ponechal. Poté jsem celý experiment provedl ještě jednou, avšak s prohozenými množinami trénovacích a testovacích dat. Na obrázku 4.5 jsou vizualizovány výsledky předchozího experimentu. Barva uzlů značí nejpravděpodobnější rubriku určenou algoritmem ML-kNN. Pokud článek nebyl zařazen do žádné z rubrik alespoň se 40% pravděpodobností, poté barva značí originální rubriku článku. Z obrázku je oproti vizualizaci originálních rubrik v 4.3 vidět, jak silné shluky ovlivnily rubriky, které v nich převládají. Pro větší přehlednost je k dispozici export grafu do webového rozhraní9 . 9

Vizualizace dostupná z http://pirklmar-dp.ulikeit.cz/index.html#mlknn.gexf

46

4.2. Testování klasifikátoru

Obrázek 4.5: Zobrazení originálně kategorizovaných článků v prostoru s využitím kosinové podobnosti (nahoře) v porovnání se stejnými články klasifikovanými pomocí ML-kNN (dole)

47

4. Analýza a vyhodnocení reálných dat

Obrázek 4.6: Podíl jednotlivých rubrik v nově kategorizované množině článků

Obrázek 4.7: Podíl skupin rubrik v nově kategorizované množině článků

Z obrázků 4.6 a 4.7 je vidět, že mnohem více článků bylo zařazeno do rubriky celebrity-ceske-celebrity (27.64%) oproti původním (16.18%). Tento trend nejvíce souvisí s vlastními jmény a místopisnými názvy. Naopak výrazně méně článku bylo klasifikováno do rubriky zpravy-události (11.66%), což je způsobeno obecností a rozličností témat, o kterých se v ní píše. Celkem bylo článkům nově přiřazeno 358mi rubrik, a kardinalita celého datasetu stoupla z 1 (single-label) na 1,28.

4.2.2

Výkon klasifikátoru

Experiment jsem provedl na datech, která vznikla postupem popsaným v předchozí kapitole 4.2.1. Aby nedošlo k přetrénování klasifikátoru vlivem nevyváženého poměru článků v jednotlivých rubrikách, vybral jsem 19 rubrik, tedy všechny, které obsahují alespoň 40 článků. Z každé rubriky jsem 40 článků náhodně vzal a rozdělil na dvě poloviny, trénovací a testovací data. Celkem tedy trénovací a testovací množina obsahovaly každá 380 článků. Z výsledků klasifikace jsem spočítal metriky popisující výkonnost multi-label klasifikátoru, 48

4.2. Testování klasifikátoru které jsou vypsány v tabulce 4.3. Hodnoty v tabulce jsou průměrné, vyběr náhodných článků byl opakován 5-krát. Dále jsem také metriky vypočetl pro různé hodnoty parametru k ML-kNN algoritmu. k

Hamming Loss

Ranking Loss

One Error

Coverage

Average Precision

4

0.086

0.37

0.6

8.56

0.41

5

0.084

0.37

0.59

8.49

0.41

6

0.075

0.37

0.58

8.54

0.42

7

0.077

0.37

0.6

8.47

0.41

8

0.077

0.36

0.64

8.15

0.42

Tabulka 4.3: Experimentální výsledky výkonu ML-kNN klasifikátoru na datech popsaných výše

Nejlepších výsledků dosahuje klasifikátor na daných datech pro k=6. Poslední sloupec udává, kolik % článků bylo klasifikováno do všech relevantních rubrik a do žádných jiných.

4.2.3

Práce klasifikátoru v produkčnim prostředí

K tomuto experimentu jsem použit systém popsaný v kapitole 3, do kterého jsem vložil data, vzniklá výsledkem experimentu v 4.2.1. Pro přehlednost jsem vybral 6 rubrik - zpravy-udalosti, zpravy-krimi, zpravy-politika, zpravypocasi, digital-internet a celebrity-ceske-celebrity. Pro parametr k pro MLkNN klasifikátor jsem zvolil hodnotu 6 na základě výsledků z kapitoly 4.2.2. Do každé rubriky jsem vložil 30 nejmladších článků stažených z webu portálu Blesk.cz 15.4.2014. Behěm experimetu jsem vkládal do systému zpravodajské články publikované v posledních dnech a následně jsem pozoroval chování systému. Názvy rubrik za symbolem → značí klasifikátorem predikované rubriky. Čisla v závorce značí identifikátor nově vkládaného článku. (1) Tajemství krásy Bagarové odhaleno, její máma vypadá jako její sestra10 → celebrity − ceske − celebrity, zpravy − udalosti 10 http://www.blesk.cz/clanek/celebrity-ceske-celebrity/236433/tajemstvikrasy-bagarove-odhaleno-jeji-mama-vypada-jako-jeji-sestra.html

49

4. Analýza a vyhodnocení reálných dat (2) Sebevražda Bartošové: Rychtářovi napsala dopis na rozloučenou11 → celebrity − ceske − celebrity, zpravy − udalosti (3) Příští týden bude pršet: Pak srážek ubude a ochladí se12 → zpravy − pocasi (4) Lvi jsou nažhavení na finále KHL: Jaký mají program před zápasem?13 → celebrity − ceske − celebrity, zpravy − udalosti (5) Kouč Magnitogorsku zuřil! Po prohře se Lvem se sápal na sudí14 → zpravy − udalosti, zpravy − krimi (6) Česká sedmnáctka v kvalifikaci ME padla s Anglií 0:1 15 → zpravy − udalosti (7) Murray měl sen, finále se Štěpánkem! Jestli vyhrál, to netuší ani on16 → celebrity − ceske − celebrity, zpravy − krimi (8) Jágr zůstane v NHL. Už jsem se dohodl s Devils, oznámil v Praze17 → celebrity − ceske − celebrity, zpravy − udalosti V detekci shluků se objevil následující záznam:

Obrázek 4.8: Detekovaný shluk článků týkajících se sportu

Na základě toho byla vytvořena rubrika sport a články (4) (5) (6) (7) (8) do ní byly manuálně zařazeny. 11

http://www.blesk.cz/clanek/celebrity-smrt-ivety-bartosove/248440/ sebevrazda-bartosove-rychtarovi-napsala-dopis-na-rozloucenou.html 12 http://www.blesk.cz/clanek/zpravy-pocasi/247990/pristi-tyden-bude-prsetpak-srazek-ubude-a-ochladi-se.html 13 http://isport.blesk.cz/clanek/blesk-sport/202503/lvi-jsou-nazhaveni-nasedme-finale-khl-jaky-maji-program-pred-zapasem.html 14 http://isport.blesk.cz/clanek/hokej-khl-lev-praha/202398/koucmagnitogorsku-zuril-po-prohre-se-lvem-se-sapal-na-sudi.html 15 http://isport.blesk.cz/clanek/fotbal-reprezentace-mladeznicke-vybery/ 199198/ceska-sedmnactka-v-kvalifikaci-me-padla-s-anglii-0-1-a-postup-jedaleko.html 16 http://isport.blesk.cz/clanek/tenis-wimbledon/176289/murray-mel-senfinale-se-stepankem-jestli-vyhral-to-netusi-ani-on.html 17 http://isport.blesk.cz/clanek/hokej-nhl/202448/jagr-zustane-v-nhl-uz-jsemse-dohodl-s-devils-oznamil-v-praze.html

50

4.2. Testování klasifikátoru (9) PŘEHLED: Kdo pojede na MS v Minsku a kdo ještě musí zabojovat?18 → celebrity − ceske − celebrity, sport (10) Jágr pojede na MS! Hrát bude už na turnaji ve Švédsku19 → celebrity − ceske − celebrity, sport (11) Politici o 3 letech pro kmotra: Janoušek není výjimečný, spravedlnost platí pro všechny!20 → zpravy − politika (12) Nokia končí. Kdysi největšího výrobce mobilů koupil Microsoft21 → celebrity − ceske − celebrity, digital − internet V detekci shluků se objevil následující záznam:

Obrázek 4.9: Detekovaný shluk článků týkajících se Microsoftu

(13) Češka popsala život v Sýrii: Zvykla jsem si na to, že každý den můžu umřít22 → celebrity − ceske − celebrity, zpravy − krimi Články (9) a (10) byly klasifikovány původně pouze do rubriky celebrityceske-celebrity. Jelikož rubrika sport obsahovala zatím jen 5 článků, trénovací množina nebyla nejspíš dostatečně velká, ikdyž jsou tyto články tématicky velmi podobné těm vloženým. Lepších výsledků bylo v tomto případě dosaženo snížením parametru k na hodnotu 3. Obecně z toho lze usoudit, že rubriky s vysokým počtem článků ovlivní při velkém k klasifikaci v jejich prospěch u článků, které by měly spadat do rubrik s malým počtem článků. 18

http://isport.blesk.cz/clanek/hokej-reprezentace-ms-2014/202488/prehledkdo-pojede-na-ms-v-minsku-a-kdo-jeste-musi-zabojovat.html 19 http://isport.blesk.cz/clanek/hokej-reprezentace-ms-2014/202430/jagrpojede-na-ms-hrat-bude-uz-na-turnaji-ve-svedsku.html 20 http://www.blesk.cz/clanek/zpravy-politika/248695/politici-o-3-letech-prokmotra-janousek-neni-vyjimecny-spravedlnost-plati-pro-vsechny.html 21 http://www.blesk.cz/clanek/digital-mobily/247972/nokia-konci-kdysinejvetsiho-vyrobce-mobilu-koupil-microsoft.html 22 http://www.blesk.cz/clanek/zpravy-udalosti/249305/ceska-popsala-zivot-vsyrii-zvykla-jsem-si-na-to-ze-kazdy-den-muzu-umrit.html

51

4. Analýza a vyhodnocení reálných dat Celkově systém prokazuje ve většině případů relevantní výsledky klasifikace, avšak tato vlastnost je plně závislá na volbě trénovacích dat a počtu rubrik v systému.

52

Závěr V rámci této práce se mi podařilo navrhnout a implementovat systém sloužicí pro správu zpravodajských článků a rubrik. Co se týče automatické kategorizace článků do jednotlivých rubrik, zde se mi z implementačního hlediska podařilo integrovat klasifikátor a předzpracování dat do systému tak, že je vše prováděno v rámci jedné akce. Pokud je zpracováváno řádově stovky článků, je doba zpracování únosná a pohybuje se okolo 10 - 30 sekund, pro zpracovávání většího počtu článků vidím v tomto směru určitě prostor pro optimalizaci. Z výzkumného hlediska je, co se týče metod a přístupu ke klasifikaci zpravodajských článků, určitě také ještě prostor pro další bádání. Jako další směr vývoje vidím možnost použití lokálních hierarchií při klasifikaci, což by mělo vést k lepším výsledkům u vysokého počtu článků a rubrik. Dále vidím u aktuálního řešení slabinu v tom, že pojímá články čistě lexikograficky, což podle výsledků experimentů v této práci nejspíš nestačí, neboť u takto krátkých textů mají velký vliv na podobnost článků vlastní jména a místopisné názvy. I přesto se mi podařilo pomocí algoritmu ML-kNN v kombinaci s tranformací hierarchické struktury rubrik na plochou dosáhnout plně relevantních výsledků u 42% testovaných článků. V rámci této práce jsem navíc nalezl a implementoval možnost, jak vizualizovat a prohlížet grafové struktury zobrazující aktuální rozložení zpravodajských článků v prostoru.

53

Literatura [1] Hamming Loss definition[online, cit. 15. 4. 2014]. Dostupné z WWW: https://www.kaggle.com/wiki/HammingLoss [2] Hierarchical Loss definition[online, cit. 15. 4. 2014]. Dostupné z WWW: http://homes.di.unimi.it/~cesabian/Pubblicazioni/J23.pdf [3] One-vs-All classification method[online, cit. 15. 4. 2014]. Dostupné z WWW: http://machinelearning.wustl.edu/mlpapers/paper_files/ RifkinK03.pdf [4] TF-IDF definition[online, cit. 15. 4. 2014]. Dostupné z WWW: http:// en.wikipedia.org/wiki/Tf%E2%80%93idf [5] Liao B, Li Y, Jiang Y, Cai L (2014) Using Multi-Instance Hierarchical Clustering Learning System to Predict Yeast Gene Function. PLoS ONE 9(3): e90962. doi:10.1371/journal.pone.0090962 [6] Multilabel hierarchical text classification using the ACM taxonomy[online, cit. 18. 4. 2014]. Dostupné z WWW: http://epia2009.web.ua.pt/ onlineEdition/553.pdf [7] Yang, Y.: An evaluation of statistical approaches to text categorization. Journal of Information Retrieval Vol.1, No.1/2 (1999) [8] Koller, D., Sahami, M.: Hierarchically classifying documents using very few words. In Proceedings of 14th International Conference on Machine Learning ICML-97, pp.170– 178 (1997) 55

Literatura [9] Effective Multi-Label Active Learning for Text Classification[online, cit. 15. 4. 2014]. Dostupné z WWW: http://research.microsoft.com/pubs/ 81064/sigkdd09-yang.pdf [10] SVM kernel method for multi-labelled classification[online, cit. 20. 4. 2014]. Dostupné z WWW: http://cse.seu.edu.cn/people/zhangml/ files/NIPS02.pdf [11] Multi-label classification, an overview[online, cit. 18. 4. 2014]. Dostupné z WWW: http://talos.csd.auth.gr/tsoumakas/publications/J6.pdf [12] ML-kNN: A Lazy Learning Approach to Multi-Label Learning[online, cit. 19. 3. 2014]. Dostupné z WWW: http://cs.nju.edu.cn/zhouzh/ zhouzh.files/publication/pr07.pdf [13] Support vector machines[online, cit. 20. 4. 2014]. Dostupné z WWW: http://www.support-vector-machines.org/ [14] Discriminative methods for multi-label classification[online, cit. 18. 4. 2014]. Dostupné z WWW: http://www.godbole.net/shantanu/pubs/ multilabelsvm-pakdd04.pdf [15] SVM margin maximization[online, cit. 18. 4. 2014]. Dostupné z WWW: https://www.cs.cmu.edu/~tom/10701_sp11/slides/ Kernels_SVM2_04_12_2011-ann.pdf [16] Model combination[online, cit. 18. 4. 2014]. Dostupné z WWW: http://cui.unige.ch/AI-group/teaching/dmc/09-10/cours/dm11ensembles.pdf [17] S. Tong and D. Koller. Support vector machine active learning with applications to text classification. Journal of Machine Learning Research, pages 45-66, 2002. [18] D. D. Lewis and W. A. Gale. A sequential algorithm for training text classifiers. In Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval(SIGIR’94), pages 3-12, 1994 [19] RAndom-K-LAbelsets[online, cit. 15. 4. 2014]. Dostupné z WWW: http: //lpis.csd.auth.gr/publications/tsoumakas-tkde10.pdf 56

Literatura [20] BoosTexter[online, cit. 15. 4. 2014]. Dostupné z WWW: http:// citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.145.7890&rep= rep1&type=pdf [21] Similarity measures for text document clustering[online, cit. 22. 4. 2014]. Dostupné z WWW: http:// www.milanmirkovic.com/wp-content/uploads/2012/10/ pg049_Similarity_Measures_for_Text_Document_Clustering.pdf [22] Fast unfolding of communities in large networks[online, cit. 25. 4. 2014]. Dostupné z WWW: http://lanl.arxiv.org/abs/0803.0476

57

Příloha

Obsah přiloženého CD

readme.txt...................................stručný popis obsahu CD exe ....................... adresář se spustitelnou formou implementace src impl...................................zdrojové kódy implementace thesis ...................... zdrojová forma práce ve formátu LATEX text ....................................................... text práce thesis.pdf ............................. text práce ve formátu PDF 59

A