znalostí z textových dat

Mendelova univerzita v Brnˇe Provoznˇe ekonomická fakulta

Aplikov´ an´ı paralelismu pˇri dolov´ an´ı znalost´ı z textov´ ych dat Diplomov´ a pr´ ace

Vedouc´ı práce:

Bc. Zdenˇek Novák

doc. Ing. Frantiˇsek Daˇrena, Ph.D.

Brno 2013

list originalniho zadani prace

Dˇekuji vedouc´ımu práce, doc. Ing. Frantiˇsku Daˇrenovi, Ph.D., za veden´ı pˇri zpracován´ı diplomové práce a za poskytnut´ı nezbytn´ ych podklad˚ u, pomoci a cenn´ ych rad. ˇ zkovi, CSc., za seznámen´ı s problematikou text miningu Dˇekuji také doc. Ing. Janu Ziˇ a pomoci pˇri vyprácován´ı této práce.

Prohlaˇsuji, ˇze jsem tuto práci vypracoval zcela samostatnˇe s pouˇzit´ım v´ yhradnˇe tˇech zdroj˚ u, které jsou souhrnnˇe uvedeny v seznamu literatury.

Brno, 23. kvˇetna 2013

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

5

Abstract Zdenˇek Novák, Application of parallel approach to text mining. Diploma thesis. Brno, 2013. The diploma thesis deals with mining knowledge from large collections of textual data using parallelism as a possible solution of problems related to high computational complexity of this process. It describes issues associated with preprocessing of textual data and usage of machine learning algorithms. The outcome is represented by the results of experiments that compare a traditional approach to text classification with a parallel approach. For the purpose of realizing these experiments an application (using some popular libraries (sometimes modified) and software) was implemented. The applied classification algorithms include neural networks, support vector machines, and k-nearest neighbours. The results demonstrate that a parallel approach enables to reduce the time complexity of the process while maintaining sufficient values of classification performance metrics. Keywords text mining, machine learning, classification, parallelism, neural networks, support vector machines, k-nearest neighbours

Abstrakt Zdenˇek Novák, Aplikován´ı paralelismu pˇri dolován´ı znalost´ı z textov´ ych dat. Diplomová práce. Brno, 2013. Diplomová práce se zab´ yvá problematikou dolován´ı znalost´ı z rozsáhl´ ych kolekc´ı textov´ ych dat a moˇzn´ ym ˇreˇsen´ım tohoto v´ ypoˇcetnˇe nároˇcného procesu v podobˇe paralelizace. Popisuje problematiku spojenou s pˇr´ıpravou textov´ ych dat a jejich následn´ ym zpracován´ım algoritmy strojového uˇcen´ı. V´ ystupem jsou v´ ysledky experiment˚ u, které porovnávaj´ı tradiˇcn´ı sekvenˇcn´ı pˇr´ıstup klasifkiace dat s paraleln´ım ˇreˇsen´ım. Pro u ´ˇcely realizace tˇechto experiment˚ u byla implementována aplikace (s vyuˇzit´ım znám´ ych knihoven (ˇca´steˇcnˇe upraven´ ych) a softwaru). Pouˇzité klasifikaˇcn´ı algoritmy zahrnuj´ı neuronové s´ıtˇe, podp˚ urné vektory a k-nejbliˇzˇs´ıch soused˚ u. V´ ysledky ukazuj´ı, ˇze pouˇzit´ı paraleln´ıho pˇr´ıstupu umoˇzn ˇuje sn´ıˇzen´ı ˇcasové nároˇcnosti procesu se souˇcasn´ ym zachován´ım dostateˇcn´ ych hodnot metrik pro zhodnocen´ı pˇresnosti klasifikace. Kl´ıˇ cov´ a slova dolován´ı znalost´ı z textov´ ych dat, strojové uˇcen´ı, klasifikace, paralelismus, neuronové s´ıtˇe, porp˚ urné vektory, k-nejbliˇzˇs´ıch soused˚ u

6

OBSAH

Obsah ´ 1 Uvod a c´ıl pr´ ace ´ 1.1 Uvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 C´ıl práce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Souˇ casn´ y stav 2.1 Text mining . . . . . . . 2.2 Reprezentace dokument˚ u 2.3 Klasifikace dokument˚ u . 2.4 Hodnocen´ı u ´spˇeˇsnost´ı . . 2.5 Paraleln´ı zpracován´ı . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

3 Metodika zpracov´ an´ı 3.1 Data . . . . . . . . . . . . . . . . . 3.1.1 Standardn´ı zdroje textov´ ych 3.1.2 Vytvoˇren´ı nové kolekce . . . 3.2 Algoritmy strojového uˇcen´ı . . . . . 3.3 V´ ybˇer mnoˇziny dat a jej´ı rozdˇelˇen´ı 3.4 Technologie pro implementaci . . . 3.4.1 V´ ybˇer knihoven . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . kolekc´ı . . . . . . . . . . . . . . . . . . . . . . . . . .

4 V´ ysledky 4.1 Návrh experiment˚ u . . . . . . . . . . . . 4.2 Návrh aplikace pro realizaci experiment˚ u 4.3 Implementace . . . . . . . . . . . . . . . 4.3.1 Adresáˇrová struktura . . . . . . . 4.3.2 Rozˇs´ıˇren´ı modulu TextMining . . 4.3.3 Rozˇs´ıˇren´ı knihovny FANN . . . . 4.3.4 Formát pro binárn´ı uchován´ı dat 4.3.5 Nejbliˇzˇs´ı soused . . . . . . . . . . 4.4 Experimenty . . . . . . . . . . . . . . . . 4.4.1 Neuronové s´ıtˇe . . . . . . . . . . 4.4.2 Podp˚ urné vektory . . . . . . . . . 4.4.3 Nejbl´ıˇzˇs´ı soused . . . . . . . . . . 4.4.4 Shrnut´ı v´ ysledk˚ u . . . . . . . . .

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

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

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

8 8 8

. . . . .

9 13 14 28 37 39

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

40 40 40 41 42 42 43 44

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

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

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

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

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

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

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

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

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

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

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

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

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

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

48 48 48 49 52 52 54 56 58 58 59 61 61 63

5 Diskuze 65 5.1 Nedostatky implementace . . . . . . . . . . . . . . . . . . . . . . . . 65 5.2 Moˇznosti navázán´ı na práci . . . . . . . . . . . . . . . . . . . . . . . 65 5.3 Moˇznosti vyuˇzit´ı v praxi . . . . . . . . . . . . . . . . . . . . . . . . . 65 6 Z´ avˇ er

66

OBSAH

7

A Pˇ r´ıloha 1

67

B Literatura

68

1

´ ´ UVOD A C´ıL PRACE

1 1.1

8

´ Uvod a c´ıl pr´ ace ´ Uvod

Jiˇz nˇekolik des´ıtek let jsou známé modely a navrˇzené inteligentn´ı algoritmy, jejichˇz pouˇzit´ı ale nebylo do nedávné doby moˇzné. Kupˇr´ıkladu model umˇelého neuronu byl poprvé pˇredstaven na zaˇcátku druhé poloviny minulého stolet´ı (Rosenblatt, 1957), ale jeho praktická realizace nebyla v dané dobˇe kv˚ uli neodstateˇcné v´ ypoˇcetn´ı technice moˇzná. Teprve v nedávné dobˇe umoˇznilo neustálé zvyˇsován´ı v´ ypoˇcetn´ıch moˇznost´ı jeho reálné vyuˇzit´ı a obecnˇe rozvoj umˇelé inteligence, která si klade za c´ıl stvoˇrit inteligentn´ı program ˇci stroj. Jde o velice zaj´ımav´ y obor v oblasti poˇc´ıtaˇcové ˇ vˇedy, kter´ y pˇritahuje znaˇcné mnoˇzstv´ı lid´ı. Casto jsou vˇsak souˇcasné moˇznosti stále omezeny dostupnou v´ ypoˇcetn´ı kapacitou, a proto nˇekterá u ´sil´ı smˇeˇruj´ı k hledán´ı zp˚ usob˚ u, jak tyto nároky na poˇc´ıtaˇcovou techniku sn´ıˇzit. Jednou z mnoha oblast´ı umˇelé inteligence je dolován´ı znalost´ı z dat, jehoˇz princip spoˇc´ıvá v prohledáván´ı velkého mnoˇzstv´ı sebran´ ych u ´daj˚ u s c´ılem odhalit v tˇechto datech nové, skryté in’ formace. Zvláˇst n´ım pˇr´ıpadem je dolován´ı znalost´ı z textov´ ych dat. S reáln´ ymi aplikacemi z této oblasti se vˇetˇsina lid´ı setkává kaˇzd´ y den, napˇr. pˇri vyhledáván´ı pˇres celosvˇetov´ y vyhledávaˇc Google. Jde tedy o velice zaj´ımavou oblast hromadného zpracován´ı dat, protoˇze d´ıky dneˇsn´ımu rozˇs´ıˇren´ı internetu a moˇznostech, které nejr˚ uznˇejˇs´ı webové aplikace nab´ızej´ı, je k dispozici obrovské mnoˇzstv´ı textov´ ych dat. Nˇekteré aplikace nemus´ı d´ıky malému mnoˇzstv´ı dat dostupn´ ych ke zpracován´ı dosahovat kvalitn´ıch v´ ysledk˚ u a jedn´ım ze zp˚ usob˚ u, jak v´ ysledky vylepˇsit, je právˇe vˇetˇs´ı mnoˇzstv´ı dat (Banko, Brill, 2001). S mnoˇzstv´ım dat nen´ı u dolován´ı z text˚ u problém, ale narozd´ıl od klasického dolován´ı jsou nároky na v´ ypoˇcetn´ı v´ ykon vyˇsˇs´ı. M˚ uˇze za to právˇe povaha textov´ ych dat. D˚ usledkem je tedy nemoˇznost zpracovávat v rozumném ˇcase velká mnoˇzstv´ı textov´ ych dat, pˇrestoˇze jsou dostupná a mohla by tak b´ yt nˇejak´ ym zp˚ usobem vyuˇzita. Moˇzn´ ym ˇreˇsen´ım, kter´ ym se zab´ yvá také tato diplomová práce, je aplikován´ı paraleln´ıho pˇr´ıstupu. Ten umoˇzn ˇuje sn´ıˇzit v´ ypoˇcetn´ı nároky kladené na poˇc´ıtaˇcovou techniku pˇri zpracován´ı rozsáhl´ ych kolekc´ı textov´ ych dokument˚ u ˇ zka, Daˇrena, 2012). Pˇredevˇs´ım jde o zjiˇstˇen´ı moˇznost´ı nasazen´ı konkrétn´ıch al(Ziˇ goritm˚ u pˇri paraleln´ım zpracován´ı a jak´ y bude m´ıt tento pˇr´ıstup dopad na jejich schopnost poskytovat správné v´ ysledky v rozumném ˇcase.

1.2

C´ıl pr´ ace

C´ılem práce je prozkoumat moˇznosti aplikován´ı paraleln´ıho pˇr´ıstupu pˇri dolován´ı znalost´ı z rozsáhl´ ych kolekc´ı textov´ ych dat. Hlavn´ı snaˇzen´ı bude smˇeˇrovat na porovnán´ı vlivu tohoto pˇr´ıstupu na pˇresnost a v´ ypoˇcetn´ı nároˇcnost r˚ uzn´ ych algoritm˚ u strojového uˇcen´ı, které jsou pouˇz´ıvány pro klasifikaci textov´ ych dat. Pro tyto u ´ˇcely bude nutné realizovat sadu experiment˚ u, které poskytnou v´ ysledky vhodné pro tato srovnán´ı. V práci bude navrˇzen formát tˇechto experiment˚ u a z´ıskané v´ ysledky vyhodnoceny. Pro jejich realizaci bude také implementována aplikace.

2

ˇ ´ STAV SOUCASN Y

2

9

Souˇ casn´ y stav

Umˇelá inteligence je v dneˇsn´ı dobˇe samostatn´ ym vˇedn´ım oborem, kter´ y si od svého vzniku v roce 1987 proˇsel obdob´ımi velikého nadˇsen´ı a vkládán´ı mnoha nadˇej´ı i neutuchaj´ıc´ı skepse a odm´ıtán´ı. Samotné základy poloˇzil v roce 1956 na univerzitˇe v Princetonu John McCarthy, a to uspoˇra´dán´ım prvn´ı mezinárodn´ı konference, jej´ımˇz tématem byla právˇe umˇelá inteligence. Za své pˇrispˇen´ı na poli tohoto nového vˇedn´ıho oboru pak v roce 1985 obdrˇzel Turingovu cenu (AI Basics). Mezi u ´ˇcastn´ıky této konference byl i Marvin Minsky, kter´ y je také povaˇzován za jednoho z otc˚ u modern´ı umˇelé inteligence. On sám ji pak definuje jako vˇedu, jej´ımˇz c´ılem je tvorba stroj˚ u na dˇelán´ı vˇec´ı, pro jejichˇz vykonáván´ı je vyˇzadována urˇcitá inteligence, provád´ı-li je ˇclovˇek (Whitby, 1996). Toto samozˇrejmˇe nen´ı jediná z definic, na které lze pˇri nahlédnut´ı do r˚ uzn´ ych uˇcebnic, vˇedeck´ ych ˇclánk˚ u ˇci internetu narazit. Dokonce je moˇzné se na umˇelou inteligenci d´ıvat nikoliv jako na vˇedn´ı obor, n´ ybrˇz jako na urˇcitou vlastnost umˇelého (ve smyslu neˇzivého) objektu, která mu umoˇzn ˇuje se inteligentnˇe rozhodovat nejen na základˇe vjem˚ u, které z´ıskává ze svého okol´ı, ale také na základˇe vlastn´ıch znalost´ı, které má uchovány ve své pamˇeti. Samotn´ y pojem inteligentn´ı rozhodován´ı je vˇsak pomˇernˇe vágn´ı. Intuitivnˇe si pod t´ımto lze pˇredstavit napˇr´ıklad to, ˇze inteligentnˇe se rozhoduj´ıc´ı stroj by mˇel docházet k podobn´ ym závˇer˚ um, ke kter´ ym by za stejn´ ych okolnost´ı dospˇel ˇclovˇek. Definitivn´ı rozhodnut´ı o tom, zda je stroj inteligentn´ı nebo nikoliv, je moˇzné uˇcinit na základˇe tzv. Turingova testu, pojmenovaném po britském matematikovi Alanu Turingovi. Ten se ve svém ˇclánku Computing machinery and intelligence (1950) zaob´ıral otázkou, zda je moˇzné uvaˇzovat nad t´ım, jestli mohou stroje myslet. M´ısto pokus˚ u o jej´ı zodpovˇezen´ı, kv˚ uli v´ıcev´ yznamnosti slov stroj a myslet, navrhl jin´ y pˇr´ıstup k formulaci tohoto problému, a to ve formˇe hry. Této se u ´ˇcastn´ı celkem tˇri osoby: muˇz, ˇzena a tazatel. Tazatel z˚ ustává v oddˇelené m´ıstnosti a obˇema osobám ´ pokládá otázky, pˇriˇcemˇz jejich odpovˇedi pak dostává v tiˇstˇené podobˇe. Ukolem tazatele je rozpoznat, kdo je muˇz a kdo ˇzena, a oba dva se snaˇz´ı tazatele pˇresvˇedˇcit, ˇze jsou ˇzena, tzn. ˇze muˇz zámˇernˇe lˇze, zat´ımco ˇzena ˇr´ıká pravdu. K tomuto je vˇsak tˇreba urˇcit´ ym zp˚ usobem myslet a inteligentnˇe odpov´ıdat. Muˇz je poté v pr˚ ubˇehu hry nahrazen umˇelou inteligenc´ı a pokud stroj zvládne svou u ´lohu a obelˇze tazatele, tak t´ımto testem proˇsel. Jeho chován´ı tud´ıˇz lze oznaˇcit za inteligentn´ı. Dodnes se to vˇsak ˇza´dnému stroji zcela nepodaˇrilo. Nejbl´ıˇze tomu byl program Josepha Weizenbauma (1966),1 kter´ y je i nˇekter´ ymi lidmi povaˇzován za prvn´ı, kter´ y testem proˇsel. Princip spoˇc´ıvá v jednoduchém hledán´ı kl´ıˇcov´ ych slov v pr˚ ubˇehu konverzace, na základˇe kter´ ych pak sestavuje svoje odpovˇedi a nové otázky. Pokud nen´ı k dispozici dostatek informac´ı pro sestaven´ı odpovˇedi, program opakuje dˇr´ıvˇejˇs´ı v´ yroky nebo pouˇz´ıvá obecné odpovˇedi – tento postup je zaloˇzen na tzv. rogeriánské psychoterapii. D´ıky tˇemto princip˚ um program dokázal tazatele v Turingovˇe testu pˇresvˇedˇcit o tom, ˇze je ˇclovˇek. 1

dnes jsou podobné programy zn´ amé pod názvem chatterbot

2


10

Umˇelá inteligence – jako vˇedn´ı obor – v dneˇsn´ı dobˇe v podstatˇe zastˇreˇsuje celou ˇradu r˚ uzn´ ych pˇr´ıstup˚ u ˇreˇsen´ı této problematiky. D˚ uvodem je to, ˇze narozd´ıl od konkrétn´ıch implementac´ı umˇelé inteligence hraj´ıc´ı napˇr´ıklad ˇsachy, tak vytvoˇren´ı obecné umˇelé inteligence, která by sv´ ymi kvalitami byla alespoˇ n srovnatelná s lidsk´ ym myˇslen´ım, se velice brzo ukázalo jako témˇeˇr neˇreˇsiteln´ y problém. Proto se souˇcasná snaha zamˇeˇruje zejména na hledán´ı d´ılˇc´ıch ˇreˇsen´ı. Technologie a pˇr´ıstupy, které se se pro tyto u ´ˇcely vyuˇz´ıvaj´ı jsou (Russell, Norvig, 1995): • strojové uˇcen´ı, • expertn´ı systémy, • fuzzy logika, • neuronové s´ıtˇe, • genetické programován´ı, • procházen´ı stavového prostoru, • dolován´ı z dat. Expertn´ı systémy jsou jedn´ım z typ˚ u tzv. znalostn´ıch systém˚ u, coˇz jsou ve své podstatˇe programové systémy, které maj´ı v nˇejaké konkrétn´ı podobˇe uloˇzeny znalosti z urˇcité problémové oblasti a vyuˇz´ıvaj´ı je k hledán´ı ˇreˇsen´ı na problémy spadaj´ıc´ı do stejné oblasti (Koneˇcn´ y, Trenz, 2010). Expertn´ı systémy se vˇsak odliˇsuj´ı t´ım, ˇze dokáˇz´ı nalezené ˇreˇsen´ı zd˚ uvodnit. D˚ uvodem jejich tvorby je pˇredevˇs´ım nedostatek expert˚ u, jejichˇz sluˇzby b´ yvaj´ı jednak drahé, ale také nemus´ı b´ yt kv˚ uli ˇcasové vyt´ıˇzenosti experta v˚ ubec dostupné. Vytvoˇren´ım systému jsou pak znalosti snadno kdykoliv dostupné, jeho u ´drˇzba je levnˇejˇs´ı, zaruˇcuje urˇcitou u ´roveˇ n bezchybnosti a uchovává data po neomezenˇe dlouhou dobu. Asi nejvˇetˇs´ı problém vˇsak spoˇc´ıvá právˇe v z´ıskán´ı potˇrebn´ ych znalost´ı od expert˚ u. Ti mus´ı formulovat tzv. rozhodovac´ı pravidla, která jsou následnˇe pˇrevedena do podoby srozumitelné pro expertn´ı systém. Princip fungován´ı systému spoˇc´ıvá v pouˇzit´ı inferenˇcn´ıho (odvozovac´ıho) mechanismu, kter´ y na základˇe báze znalost´ı sestávaj´ıc´ı z fakt˚ u (atomická pravdivá tvrzen´ı) a pravidel, metodou zpˇetného ˇretezen´ı odvod´ı jednotlivé podc´ıle a poˇrad´ı jejich ˇreˇsen´ı. C´ılem fuzzy logiky je umoˇznit práci s tzv. vágn´ımi pojmy, coˇz jsou hodnoty vyjádˇrené slovnˇe nikoliv konkrétn´ı ˇc´ıselnou hodnotou. Své uplatnˇen´ı nalezla ve fuzzy expertn´ıch systémech, u kter´ ych jsou pravidla formulována slovn´ımi hodnotami (Koneˇcn´ y, Trenz, 2010). Tyto hodnoty zastupuj´ı urˇcit´ y interval ˇc´ıseln´ ych hodnot a zároveˇ n definuj´ı i jistotu, s jakou konkrétn´ı prvek nebo hodnota do daného intervalu patˇr´ı ˇci ne. Jin´ ym oznaˇcen´ım pro tyto intervaly hodnot jsou fuzzy mnoˇziny. Genetické programován´ı je zaloˇzené na principech prob´ıhaj´ıc´ıch v pˇr´ırodˇe na u ´rovni biologické evoluce. Zakladn´ı myˇslenka je inspirována Darwinovou teori´ı o v´ yvoji ˇzivoˇciˇsn´ ych druh˚ u, tedy ˇze zjednoduˇsenˇe pˇreˇzij´ı jen ti nejsilnˇejˇs´ı, potaˇzmo nejlepˇs´ı, jedinci. Princip spoˇc´ıvá ve vygenerován´ı populace nˇejak´ ych ˇreˇsen´ı pro urˇcit´ y

2


11

problém. D˚ uleˇzité je, aby poˇca´teˇcn´ı populace byla dostateˇcnˇe poˇcetná, jinak by mohlo doj´ıt k degenerován´ı ˇreˇsen´ı. Na ˇcleny populace jsou pak v kaˇzdé iteraci, pˇredstavujic´ı jednu generaci populace, aplikovány tˇri základn´ı operace, a to kˇr´ıˇzen´ı, mutace a v´ ybˇer nejlepˇs´ıch jedinc˚ u (Koza, 1990). Je tedy nutné nˇejak´ ym zp˚ usobem zajistit srovnatelnost jednotliv´ ych ˇclen˚ u populace. Ti jsou reprezentováni chromozomy skládaj´ıc´ı se z urˇcitého poˇctu gen˚ u. Kvalitu jedince pak urˇcuje tzv. funkce 2 pˇrizp˚ usobivosti. Lépe ohodnocen´ı jedinci maj´ı pak vyˇsˇs´ı ˇsanci, ˇze budou vybráni do procesu kˇr´ıˇzen´ı, a t´ım pˇr´ıpadnˇe pˇrenesou alespoˇ n ˇca´st své kvality na potomky. H˚ uˇre ohodnocen´ı jedinci nejsou z v´ ybˇeru zcela vyˇrazeni, ale jejich ˇsance na participaci jsou v´ yraznˇe menˇs´ı. Proces mutace, pˇredstavuj´ıc´ı náhodnou zmˇenu gen˚ u jedince, je do jednotliv´ ych generac´ı populace zaveden kv˚ uli tomu, aby dˇr´ıv nebo pozdˇeji nedocházelo k degeneraci, coˇz odpov´ıdá uv´ıznut´ı v lokáln´ım extrému. Ideáln´ı ˇreˇsen´ı se tedy naproti tomu nacház´ı v globáln´ım extrému. V´ yhodou genetick´ ych algoritm˚ u je, ˇze se pˇri hledán´ı ˇreˇsen´ı nemus´ı vyh´ ybat lokáln´ım extrém˚ um, narozd´ıl od mnoha jin´ ych algoritm˚ u jako neuronové s´ıtˇe, které v lokáln´ım extrému snadno uv´ıznou. Nˇekteˇr´ı jedinci populace naopak obsad´ı tyto extrémy a jejich potomci pak budou pˇredstavovat ˇreˇsen´ı jiná. Genetické algoritmy lze pouˇz´ıt na ˇreˇsen´ı celé ˇrady problém˚ u, kupˇr´ıkladu aproximace funkce, problém obchodn´ıho cestuj´ıc´ıho nebo i generován´ı zdrojového kódu. Procházen´ı stavového prostoru je jednou z d˚ uleˇzit´ ych ˇcást´ı umˇelé inteligence, jelikoˇz pˇredstavuje jeden ze základn´ıch u ´kon˚ u, které je potˇreba ˇreˇsit. Ani se souˇcasn´ ym v´ ypoˇcetn´ım v´ ykonem nen´ı moˇzné, aby programy prohledávaly vˇsechny moˇzné kombinace hodnot jednotliv´ ych promˇenn´ ych, dokud nenaraz´ı na správné ˇreˇsen´ı. Z tohoto d˚ uvodu je nutné hledat ˇreˇsen´ı inteligentnˇejˇs´ım zp˚ usobem, a to pomoc´ı stavového prostoru. Jednotlivé kombinace hodnot promˇenn´ ych pˇredstavuj´ı konkrétn´ı stavy, pˇriˇcemˇz existuj´ı dva v´ yznaˇcné stavy, a to poˇca´teˇcn´ı, odkud zaˇc´ıná proces prohledáván´ı stavového prostoru, a stav koncov´ y, kter´ y vyhovuje podm´ınkám na poˇzadované ˇreˇsen´ı problému. Aby bylo moˇzné pˇrecházet mezi jednotliv´ ymi stavy, tak jsou zavedeny tzv. operace, jejichˇz realizac´ı se stroj pohybuje stavov´ ym prostorem a prohledává dostupné stavy. Cel´ y statov´ y prostor je moˇzné znázornit pomoc´ı orientovaného grafu, ve kterém uzly pˇredstavuj´ı stavy a hrany operace. Zpravidla se stavov´ y prostor nikdy neuchovává v pamˇeti stroje cel´ y, protoˇze pro komplexnejˇs´ı typ u ´loh to zkrátka nen´ı moˇzné. M´ısto toho se následuj´ıc´ı stavy generuj´ı na základˇe aktuáln´ıho stavu a operac´ı, které je moˇzné z tohoto stavu realizovat. Stroj si pak vyb´ırá, do kterého stavu pˇrejde na základˇe hodnot´ıc´ı funkce, která stanov´ı, jak´ y uˇzitek3 dan´ y stav pˇrinese. Typick´ ym pˇr´ıkladem u ´lohy, jej´ıˇz ˇreˇsen´ı je zaloˇzené právˇe na procházen´ı stavového prostoru, je hra misionáˇri a kanibalové. Ta spoˇc´ıvá v pˇrepraven´ı tˇr´ı kanibal˚ u a tˇr´ı misionáˇr˚ u na druh´ y bˇreh pomoc´ı lod’ky, která uveze maximálnˇe dvˇe osoby. D˚ uleˇzité vˇsak je aby, na jednom z bˇreh˚ u nebyli kanibalové v poˇcetn´ı pˇrevaze. Stavy zde pˇredstavuj´ı pozici lod’ky a poˇcty kanibal˚ u a misionáˇr˚ u na obou bˇrez´ıch. Operace pak jsou moˇzné pˇrevozy z jednoho bˇrehu na druh´ y. Zde 2 3

v origin´ ale fitness function programy pracuj´ıc´ı t´ımto zp˚ usobem jsou oznaˇcovány jako uˇzitkovˇe zamˇeˇren´ı agenti

2


12

je stavov´ y prostor natolik mal´ y (pokud ukládáme pouze unikátn´ı stavy), ˇze nic nebrán´ı tomu, naj´ıt ˇreˇsen´ı prohledán´ım vˇsech moˇzn´ ych stav˚ u. Oproti tomu hra v ˇsachy tento pˇr´ıstup jiˇz neumoˇzn ˇuje. Stavy zde pˇredstavuj´ı rozestaven´ı figurek na ˇsachovnici a operace moˇzné tahy. Odhaduje se, ˇze pokud by byl pro uloˇzen´ı kaˇzdého stavu pouˇzit atom ve vesm´ıru, pak stejnˇe nebude moˇzné uchovat vˇsechny moˇzné stavy. Poˇc´ıtaˇcov´ y hráˇc tedy m˚ uˇze zjednoduˇsenˇe fungovat tak, ˇze nˇejak´ ym zp˚ usobem hodnot´ı kvalitu, kterou mi pˇrenesou jednotlivé tahy, a rozhoduje se na základˇe procházen´ı pouze ˇcásti stavového prostoru. Nároˇcnost poˇc´ıtaˇcového hráˇce pak m˚ uˇze b´ yt urˇcena poˇctem budouc´ıch tah˚ u, které m˚ uˇze pˇri svém rozhodován´ı prohledat. Dolován´ı z dat nelze zcela jednoznaˇcnˇe oznaˇcit jako souˇcást umˇelé inteligence, ale v podstatˇe s n´ı u ´zce souvis´ı. V procesu dolován´ı z dat jsou totiˇz velice ˇcasto pouˇz´ıvány právˇe technologie a pˇr´ıstupy známé z umˇelé inteligence, potaˇzmo strojového uˇcen´ı. Samotné dolován´ı je tedy zamˇeˇreno na hledán´ı nebo odkr´ yván´ı znalost´ı, které mohou b´ yt v datech skrytˇe obsaˇzené. V knize Data Mining: Practical Machine Learning Tools and Techniques (Witten, Eibe, 2005) je dolován´ı z dat definováno jako proces odhalován´ı vzor˚ u v datech, pˇriˇcemˇz proces samotn´ y mus´ı b´ yt automatick´ y nebo alespoˇ n poloautomatick´ y a odhalené vzory mus´ı b´ yt natolik smysluplné, aby dokázaly poskytnout urˇcitou v´ yhodou, zpravidla ekonomickou. Tato definice zohledˇ nuje i ekonomick´ y rozmˇer z´ıskan´ ych v´ ysledk˚ u. Ve firmen´ım svˇetˇe je totiˇz dolován´ı jiˇz pomˇernˇe bˇeˇznou prax´ı, a to v rámci business inteligence aplikac´ı, kdy se z dat, které firma z´ıskala napˇr´ıklad od sv´ ych zákazn´ık˚ u, mohou zjiˇst’ovat nové skuteˇcnosti, ˇclenit zákazn´ıky do r˚ uzn´ ych skupin podle jejich preferenc´ı nebo vzor˚ u v jejich nákupn´ım chován´ı. Pˇri tomto pˇr´ıstupu se zpravidla vyuˇz´ıvaj´ı vˇsechny moˇzná dostupná data, která má firma k dispozici. Tato data jsou strukturovaná a pˇreváˇznˇe vyjadˇruj´ı nˇejaké ˇc´ıslené hodnoty, napˇr´ıklad celkové pen´ıze utracené zákazn´ıkem za urˇcité skupiny produkt˚ u, ˇcetnost jeho nákup˚ u, poˇcty nakoupen´ ych poloˇzek v d´ılˇc´ıch nákupech nebo pˇr´ısluˇsnost produktu do urˇcité kategorie vyjádˇrená ˇ ast dat vˇsak z˚ ˇc´ıseln´ ym identifikátorem. C´ ustává v rámci klasického dolován´ı z dat nevyuˇzita a je tedy nutné hledat jiné pˇr´ıstupy ˇci metody, které by tuto mezeru dokázaly zaplnit. Jednou takovou zvláˇstn´ı oblast´ı je pak dolován´ı z textov´ ych dat, které se bˇeˇznˇe oznaˇcuje jako text mining, pˇr´ıpadnˇe text data mining. Téma této práce spadá právˇe do oblasti dolován´ı z textov´ ych dat, a proto bude nˇekolik kapitol vˇenováno bliˇzˇs´ımu pˇredstaven´ı souˇcasn´ ych postup˚ u pouˇz´ıvan´ ych pˇri text miningu. ´ celem tohoto obecného u Uˇ ´vodu bylo alespoˇ n velice povrchovˇe ˇctenáˇri nast´ınit historick´ y v´ yvoj v oblasti inteligentn´ıch algoritm˚ u, v jakém kontextu se souˇcasné technologie nacház´ı, k ˇcemu a jak se vyuˇz´ıvaj´ı a pˇredevˇs´ım poskytnout pˇribliˇznou pˇredstavu o postaven´ı text miningu mezi tˇemito pˇr´ıstupy. Dalˇs´ı kapitoly se jiˇz ˇcistˇe zamˇeˇr´ı právˇe na problematiku dolován´ı z textov´ ych dat.

2.1

2.1

Text mining

13

Text mining

Text mining, neboli téˇz dolován´ı z textov´ ych dat, je chápán jako proces odvozován´ı vysoce kvalitn´ıch informac´ı z textu, pˇriˇcemˇz vysoká kvalita je chápána jako kombinace v´ yznamnosti, novoty a zaj´ımavosti novˇe z´ıskan´ ych informac´ı (Konchady, 2006). Své uplatnˇen´ı nalézá v ˇradˇe r˚ uzn´ ych oblast´ı jako je bioinformatika, webové sluˇzby, ˇr´ızen´ı vztahu se zákazn´ıkem nebo pro akademické u ´ˇcely (Text Mining Science, 2012). Jak jiˇz bylo zm´ınˇeno, jde o urˇcitou odnoˇz data miningu, která se zamˇeˇruje ˇcistˇe na textová data. Toto je hlavn´ı rozd´ıl oproti klasick´ ym pˇr´ıstup˚ um dolován´ı z dat, které vyˇzaduj´ı dobˇre strukturovaná data. Neznamená to vˇsak, ˇze jde o naprosto odliˇsné oblasti, opak je pravdou. Pˇri práci s textov´ ymi daty jsou totiˇz velice ˇcasto pouˇz´ıvány tytéˇz postupy a metody jako pˇri zpracován´ı strukturovan´ ych dat. Aby to vˇsak bylo moˇzné, je nutné textová data vhodnˇe pˇredzpracovat a pˇrevést je do podoby poˇzadované tˇemito metodami, tedy do ˇc´ıselné reprezentace. Pokud se na data pro dolován´ı ˇclovˇek pod´ıvá jako na tabulku hodnot, známou napˇr´ıklad z programu Microsoft Excel, jednotlivé ˇrádky pˇredstavuj´ı konkrétn´ı instance dˇr´ıve zaznamenan´ ych pˇr´ıpad˚ u. Kaˇzdá buˇ nka tabulky pak urˇcuje jeden atribut, kter´ y má jasnˇe definovanou svou doménu. Jeden ze základn´ıch problém˚ u, kter´ y se mus´ı pˇri práci se strukturovan´ ymi daty ˇreˇsit, je právˇe nutnost dodrˇzen´ı pˇr´ısluˇsnosti hodnot kaˇzdého atributu do odpov´ıdaj´ıc´ı domény, a to samozˇrejmˇe u vˇsech uchovávan´ ych záznam˚ u. Stejnˇe tak problematické mohou b´ yt (a zpravidla také jsou) ne´ uplné záznamy, kdy nˇekteré atributy nemaj´ı zadány svou hodnotu. Oba dva je tˇreba nˇejak´ ym zp˚ usobem ˇreˇsit. Vˇetˇsinou se to dˇeje v rámci pˇr´ıpravy dat pro samotné dolován´ı, kdy ne´ uplné záznamy mohou b´ yt napˇr´ıklad zcela vyˇrazeny nebo doplnˇeny pr˚ umˇern´ ymi hodnotami. Pˇri práci s texty nen´ı nutné tˇemto komplikac´ım ˇcelit. Je to dáno t´ım, ˇze textová data pˇredstavuj´ı tzv. kolekci dokument˚ u a kaˇzd´ y jednotliv´ y dokument se bere jako jedna instance, tedy ˇra´dek v tabulce. Jako atributy dokument˚ u jsou pak pouˇz´ıvány vˇsechna slova, která se v rámci celé kolekce dokument˚ u objev´ı. T´ım pádem odpadá problém s neupln´ ymi záznamy, jelikoˇz slovo se vˇzdy v daném dokumentu bud’ vyskytuje nebo nevyskytuje. Stejnˇe tak nejsou komplikace se sjednocován´ım domén jednotliv´ ych atribut˚ u napˇr´ıˇc vˇsemi záznamy, protoˇze informace o v´ yskytu slova se vˇzdy vyjadˇruje stejnou hodnotou. Zde je nav´ıc moˇzné vypozorovat dalˇs´ı zaj´ımavou charakteristiku textov´ ych dat. Hodnoty jsou ve celé tabulce pouze kladné (Konchady, 2006), opˇet narozd´ıl od dat, se kter´ ymi se pracuje pˇri klasickém dolován´ı, kde napˇr´ıklad stav u ´ˇctu m˚ uˇze nab´ yvat i záporn´ ych hodnot. I pˇres tyto urˇcité v´ yhody, které s sebou pˇrináˇs´ı práce s textov´ ymi daty, stále je samotn´ y proces pˇredzpracován´ı text˚ u ˇcasto mnohem nároˇcnˇejˇs´ı, neˇz je tomu u strukturovan´ ych dat (Neto, Santos, Kaestner, Freitas, 2000). Jako dalˇs´ı u ´skal´ı text˚ u a práce s nimi je uvádˇena napˇr´ıklad uˇz samotná abstrakce ˇci nejednoznaˇcnost, která se za textem skr´ yvá. To v podstatˇe souvis´ı s dalˇs´ım problémem, kter´ y sk´ ytá r˚ uznorodost vyjadˇrován´ı se pomoc´ı pˇrirozeného jazyka, kdy stejnou vˇec je moˇzné pojmenovat r˚ uzn´ ymi slovy se stejn´ ym nebo velice podobn´ ym v´ yznamem. Z hlediska poˇc´ıtaˇce jsou vˇsak tato synonyma automaticky brána jako r˚ uzné atributy.

2.2

14

Reprezentace dokument˚ u

Stejnˇe tak zhorˇsuj´ı ˇreˇsen´ı problému homonyma, coˇz jsou naopak mnohov´ yznamová slova. Pˇr´ıkladem m˚ uˇze b´ yt ˇceské slovo mˇes´ıc, které lze chápat jako mˇes´ıc kalendáˇrn´ı ˇ ˇci jako vesm´ırné tˇeleso. Clovˇek snadno pochop´ı v´ yznam slova na základˇe kontextu, v jakém se slovo nacház´ı, a rozpoznal by jej tedy jako dva odliˇsné atributy dokumentu, poˇc´ıtaˇc uˇz nikoliv. Základn´ı pracovn´ı postup pˇri dolován´ı z textov´ ych dat je

relacni databaze

Predzpracovani textovych dat

diskove uloziste

Dolovani

Ziskana znalost

Kolekce dokumentu

internet

Obrázek 1: Schéma postupu pˇri dolován´ı z textov´ ych dat

schématicky znároznˇen na obrázku 1. Prvn´ım krokem je z´ıskán´ı kolekce dokument˚ u. Zdrojem mohou b´ yt relaˇcn´ı databáze, internetové stránky, elektronické ˇclánky atd. Po ukonˇcen´ı sbˇeru dat je tˇreba veˇskeré dokumenty pˇredzpracovat dle poˇzadavk˚ u technologi´ı a algoritm˚ u, které budou pouˇzity pˇri samotném dolován´ı. Tento proces m˚ uˇze b´ yt pomˇernˇe pˇr´ımoˇcar´ y a jednoduch´ y, kdy dojde pouze k transformaci nestrukturovan´ ych text˚ u do strukturované podoby (jak bylo ve zkratce popsáno dˇr´ıve). Samozˇrejmˇe je také moˇzné zvolit mnohem sofistikovanˇejˇs´ı pˇr´ıstup, kdy budou odstranˇena nˇekterá slova ˇci celé dokumenty, provedeny r˚ uzné v´ ypoˇcty pro transformaci ˇc´ıseln´ ych hodnot charakterizuj´ıc´ı jednotlivé dokumenty, obohacován´ı ˇci naopak zmenˇsován´ı dokument˚ u apod. Nejˇcastˇeji pouˇz´ıvané pˇr´ıstupy pro tuto fázi procesu budou popsány v následuj´ıc´ıch kapitolách. Posledn´ım krokem pak uˇz je realizace samotného dolován´ı, jehoˇz v´ ystupem by mˇela b´ yt urˇcitá netriviáln´ı znalost, napˇr´ıklad nauˇcen´ y klasifikátor nebo odhalen´ı spoleˇcn´ ych vzor˚ u mezi jednotliv´ ymi dokumenty. Novˇe z´ıskanou znalost je vˇetˇsinou potˇrebné nˇejak´ ym zp˚ usobem zhodnotit. Ke zmˇeˇren´ı kvality znalosti se pouˇz´ıvá nˇekolik r˚ uzn´ ych zp˚ usob˚ u, které budou také bl´ıˇze pˇredstave ve zvláˇstn´ı kapitole. Ve zkratce prob´ıhá proces zhodnocen´ı kvality znalosti tak, ˇze se vytvoˇr´ı tzv. testovac´ı mnoˇzina dokument˚ u a znalost je na této mnoˇzinˇe otestována. Z v´ ysledk˚ u testu jsou následnˇe vypoˇc´ıtány r˚ uzné metriky pˇresnosti, které pomáhaj´ı zhodnotit kvalitu odhalené znalosti (Manning, Raghavan, Sch¨ utze, 2008).

2.2


Textová data je nezbytné transformovat do podoby, která je vhodná pro algoritmus pouˇz´ıvan´ y ve fázi dolován´ı. Tato ˇca´st procesu zpracován´ı text˚ u je velice d˚ uleˇzitá

2.2


15

a zvolené postupy pˇri transformaci dat do strukturované podoby maj´ı znaˇcn´ y vliv na v´ yslednou kvalitu z´ıskan´ ych znalost´ı. Pˇr´ıkladem, na kterém lze ilustrovat dopad nevhodnˇe zvolené podoby vstupn´ıch dat na v´ ysledek a samotn´ y pr˚ ubˇeh hledán´ı v´ ysledku, m˚ uˇze b´ yt algoritmus slézán´ı kopce (anglicky gradient descent). Pro jednoduchost m˚ uˇzeme uvaˇzovat, ˇze pouˇzijeme pouze data o dvou atributech, pˇriˇcemˇz jejich hodnoty se nacházej´ı v rozd´ıln´ ych intervalech (napˇr. 1–5 a 1800–2400). Tyto hodnoty slouˇz´ı jako vstup pro hodnot´ıc´ı funkci, která pˇriˇrad´ı dané dvojici hodnot konkrétn´ı cenu. Cenové ohodnocen´ı se vypoˇc´ıtá pro urˇcité mnoˇzstv´ı kombinac´ı hodnot v dan´ ych rozsahech. Pokud tato data zobraz´ıme pomoc´ı konturového grafu, budou m´ıt jednotlivé izolinie tvar velice u ´zk´ ych elips (Ng, 2012). Pro algoritmus bude v takovémto pˇr´ıpadˇe mnohem obt´ıˇznˇejˇs´ı nalézt cestu do hledaného minima. Pokud jsou vˇsak hodnoty pˇrepoˇc´ıtány do shodného mˇeˇr´ıtka (rozsah hodnot bude pak pro oba atributy stejn´ y), dostanou izolinie pˇribliˇznˇe kruhov´ y tvar a algoritmus zkonverguje mnohem rychleji. Tento jev je ilustraˇcnˇe znázornˇen na obrázku 2. Podobn´ ym zp˚ usobem se lze d´ıvat na pˇr´ıpravu textov´ ych dat. Nevhodná reprezentace m˚ uˇze negativnˇe ovlivnit proces dolován´ı a z´ıskáné v´ ysledky nemus´ı dosahovat dostateˇcné kvality. Proto je d˚ uleˇzité vˇenovat pˇr´ıpravˇe dostateˇcnou pozornost a snaˇzit se o nalezen´ı co nejvhodnˇejˇs´ı reprezentace dat.

Obrázek 2: Zjednoduˇsen´ a ilustrace vlivu normalizace dat na pr˚ ubˇeh algoritmu gradient descent. Lev´ y konturov´ y graf zn´ azorˇ nuje v´ yraznˇe z´ uˇzené izolinie, které jsou typické pro hodnoty atribut˚ u z v´ yraznˇe odliˇsn´ ych interval˚ u. Prav´ y graf znázorˇ nuje moˇznou podobu izolini´ı po normalizaci hodnot do shodn´ ych interval˚ u.

Aby bylo moˇzné jednotlivé textové dokumenty transformovat do strukturované podoby, je tˇreba urˇcit nˇejakou základn´ı stavebn´ı jednotku, pomoc´ı které bude moˇzné dokument vyjádˇrit. Pˇrirozen´ ym a zároveˇ n nejpouˇz´ıvanˇejˇs´ım ˇreˇsen´ım je pouˇz´ıt´ı slov, která jsou dostateˇcnˇe srozumitelná. V´ yhodou je nav´ıc i fakt, ˇze zpracován´ı text˚ u do tohoto zp˚ usobu reprezentace je pomˇernˇe jednoduchá. Nen´ı to vˇsak jedin´ y pˇr´ıstup a stejnˇe jako pˇri klasickém dolován´ı, i zde je moˇzné vytváˇret z datov´ ych sloˇzek

2.2


16

sloˇzky nové. Pokud data obsahuj´ı napˇr. u ´daje o rozloze domu a jeho prodejn´ı cenˇe, je moˇzné na základˇe tˇechto hodnot vypoˇc´ıtat novou sloˇzku, a to cenu za metr ˇctvereˇcn´ı. Ta pak m˚ uˇze teoreticky pomoci pˇri samotném dolován´ı, kupˇr´ıkladu by mohla tato informace dobˇre poslouˇzit pˇri shlukován´ı. Obdobnˇe je moˇzné rozˇsiˇrovat moˇznosti pro strukturovan´ y popis textov´ ych dat. Model bag-of-words Základn´ım pˇr´ıstupem je tzv. bag of words reprezentace a pouˇzit´ı nalézá nejen pˇri práci s textov´ ymi dokumenty, ale také s obrazov´ ymi daty nebo s video daty. Kaˇzd´ y dokument je reprezentován skupinou slov. Tato mnoˇzina se také naz´ yvá slovn´ık. Nejjednoduˇsˇs´ı reprezentac´ı je vyjádˇren´ı dokument˚ u pomoc´ı pˇr´ıznaku v´ yskytu slova. Mnohem ˇcastˇeji se vˇsak m´ısto této binárn´ı hodnoty (slovo se v dokumentu nacház´ı nebo nenacház´ı) pouˇz´ıvá poˇcet v´ yskytu daného slova v dokumentu. Pak je moˇzné d´ıvat se na reprezentaci pomoc´ı bag-of-words jako na histogram slov pro konkrétn´ı dokument. D˚ uleˇzité je, ˇze kaˇzd´ y dokument, jakoˇzto uspoˇrádaná struktura slov, je transformován na neuspoˇrádánou mnoˇzinu slov, ˇc´ımˇz docház´ı ke ztrátˇe urˇcitého mnoˇzstv´ı informace. V podstatˇe se naivnˇe pˇredpokládá, ˇze v´ yskyty jednotliv´ ych slov jsou na sobˇe vzájemnˇe nezávislé a nen´ı tedy nutné uchovávat informaci o poˇrad´ı jednotliv´ ych slov (Zhang, Jin, Zhou, 2012). Obdobn´ ym zp˚ usobem je bag-of-words uplatˇ nováno i pro obrazová data, kde jsou slova nahrazena tzv. vizuáln´ımi slovy, coˇz jsou malé ˇca´sti obrazu, které b´ yvaj´ı také oznaˇcovány jako pˇr´ıznaky (angl. features). Je tedy moˇzné se setkat i s oznaˇcen´ım bag-of-features. Základn´ı podoba bag-of-words, ve které jsou pouˇzita pouze slova z dokument˚ u v p˚ uvodn´ım tvaru, je schopna poskytnout pomˇernˇe dobré v´ ysledky ˇ (Zhang, Jin, Zhou, 2012). Casto je vˇsak vyuˇz´ıváno r˚ uzn´ ych moˇznost´ı, jak reprezentaci dokumentu pomoc´ı bag-of-words zlepˇsit a dosáhnout tak kvalitnˇejˇs´ıch v´ ysledk˚ u. Tˇechto postup˚ u existuje nemalé mnoˇzstv´ı, a tak se m˚ uˇze proces transformace textu velice snadno skládat hned z nˇekolika d´ılˇc´ıch krok˚ u. Zároveˇ n je také tˇreba brát v potaz r˚ uzné problémy, které je tˇreba pˇri transformaci textu ˇreˇsit. Tokenizace Tokenizace je proces rozdˇelen´ı textu na jednotlivá slova a jde o d˚ uleˇzitou ˇca´st procesu zpracován´ı textu. (Manning, Raghavan, Sch¨ utze, 2008) Text dokumentu je tˇreba rozdˇelit na tzv. tokeny, coˇz jsou instance prvk˚ u ze slovn´ıku. Aˇckoliv by se mohlo ˇreˇsen´ı jevit jako pomˇernˇe jednoduché a pˇr´ımoˇcaré, tak i zde je moˇzné narazit na nˇekolik problém˚ u. Pokud se pracuje kupˇr´ıkladu s doslovn´ ym pˇrepisem ˇreˇci nˇejakého ˇclovˇeka, m˚ uˇze tento text obsahovat nedoˇreˇcená slova nebo neartikulované zvuky pouˇz´ıvané pˇri pauzách mezi ˇreˇc´ı. Budou i tyto ˇretˇezce povaˇzovány za slova ˇci nikoliv? Dalˇs´ı problém mohou zp˚ usobit obecnˇe v´ıceslovné názvy napˇr. mˇest nebo instituc´ı. Budou Královo pole nebo u ´stavn´ı soud brány jako jeden token nebo jak tokeny dva?

2.2


17

R˚ uzné jazyky mohou nav´ıc d´ıky sv´ ym vlastn´ım charakteristikám pˇrinést dalˇs´ı aspekty, které m˚ uˇze b´ yt vhodné nˇejak´ ym zp˚ usobem vyˇreˇsit. V angliˇctinˇe se napˇr´ıklad mohou objevit tzv. hovorové staˇzené tvary. Jde o zkrácen´ y zápis (nejˇcastˇeji podmˇetu a pˇr´ısudku). Pˇri zpracován´ı je tˇreba rozhodnout, jak´ ym zp˚ usobem se bude zacházat s podobn´ ymi zápisy. Zda-li se apostrof nahrad´ı za mezeru a vzniknou tak nekoreketn´ı slova, nebo se vˇse ponechá v p˚ uvodn´ım tvaru, pˇr´ıpadnˇe se zápis rozˇs´ıˇr´ı na kompletn´ı slova. I’m You’re don’t

---> ---> --->

I am You are do not

Dalˇs´ım zaj´ımav´ ym pˇr´ıkladem m˚ uˇze b´ yt japonˇstina, pro kterou je charakterisické psan´ı slov bez oddˇelen´ı mezerou. Pˇri zpracován´ı japonsky psaného textu je tedy nutné nˇejak´ ym zp˚ usobem rozdˇelit psanou vˇetu jednotlivé tokeny. Pro tyto u ´ˇcely dobˇre slouˇz´ı longest fit algoritmus (funguje na hladovém principu), kter´ y postupnˇe procház´ı text znak po znaku a hledá nejdelˇs´ı moˇznou shodu se nˇekter´ ym ze slov ve slovn´ıku. Vyuˇz´ıvá se zde dalˇs´ı zaj´ımavé charakteristiky japonˇstiny, a to pr˚ umˇerné délky slova, která je 2.4 znaku. Tento pomˇernˇe jednoduch´ y pˇr´ıstup vˇsak funguje velice dobˇre. V japonsky psaném textu je jeˇstˇe moˇzné narazit na celkem tˇri typy abeced, z nichˇz kaˇzdá slouˇz´ı pro jin´ yu ´ˇcel. ˇ ıny, vˇzdy jde o obsahová slova jako • Kanji – pouˇz´ıvá se pro slova prop˚ ujˇcená z C´ podstatná jména, pˇr´ıdavná jména nebo slovesa • Hiragana – pouˇz´ıvá se pro funkˇcn´ı slova, gramatické znaˇcky, skloˇ novac´ı koncovky a nˇekterá japonská slova nepsaná v Kanji • Katakana – tato abeceda se pouˇz´ıvá pro slova vyp˚ ujˇcená z ciz´ıch jazyk˚ u (kromˇe ˇc´ınˇstiny) Nˇekterá slova mohou b´ yt nav´ıc psána jako kombinace v´ıce abeced. Také se pro technické pˇrevzaté názvy bez vlastn´ıho pˇrekladu pouˇz´ıvá klasická latinka (Fung, Kan, Horita, 1996). V japonˇstinˇe se nav´ıc (narozd´ıl od angliˇctiny) vyskytuje velké mnoˇzstv´ı homonym a synonym, coˇz opˇet vyˇzaduje vˇenovat zv´ yˇsenou pozornost pˇri zpracován´ı a reprezentovat r˚ uzná slova se stejn´ ym v´ yznamem jedn´ım tokenem nebo stejná slova s r˚ uzn´ ym v´ yznamem v´ıce tokeny. Jak je vidˇet na nˇekolika málo pˇr´ıkladech, aˇckoliv se m˚ uˇze zdát samotné rozdˇelen´ı textu na slova velice snadnou u ´lohou, pro z´ıskán´ı opravdu kvalitn´ı reprezentace dokumentu je nutné oˇsetˇrit ˇradu mnohoznaˇcnost´ı a naopak nejednoznaˇcnost´ı textu psaného v pˇrirozeném jazyce. R˚ uzné jazyky pak mohou nav´ıc cel´ y proces jeˇstˇe zkomplikovat sv´ ymi charakteristick´ ym vlastnostmi, na které je také tˇreba brát pˇri zpracován´ı zˇretel.

2.2


18

Normalizace Stejnˇe jako v pˇr´ıpadˇe klasického dolován´ı, je i u textov´ ych dat nutné provést urˇcitou m´ıru normalizace. Jedná se o proces, ve kterém docház´ı ke sjednocen´ı zp˚ usobu reprezentace urˇcité informace (Manning, Raghavan, Sch¨ utze, 2008), a to napˇr´ıˇc celou datovou základnou. Zat´ımco u strukturovan´ ych dat se bˇehem normalizce jednotn´ ym zp˚ usobem vyjadˇruj´ı napˇr´ıklad data, penˇeˇzn´ı poloˇzky, adresy nebo jména, u textov´ ych dat docház´ı k normalizaci zápisu slov se stejn´ ym v´ yznamem, ale rozd´ıln´ ym zápisem. Typick´ ym pˇr´ıkladem mohou b´ yt r˚ uzné zkratky nebo názvy. Narodil jsem se v ˇ Cesk´ e republice. Po vystudov´ an´ ı jsem se rozhodl odcestovat z ˇ CR do zahraniˇ c´ ı. Let ˇ C.R.--U.S.A. bude odl´ etat za 15 minut. ˇ Ve v´ yˇse uveden´ ych vˇetách se vyskytuj´ı tˇri r˚ uzná oznaˇcen´ı pro Ceskou republiku. Bˇehem normalizce by tato slova mˇela b´ yt rozpoznána a nadále jiˇz vyjádˇrena vˇzdy stejn´ ym jedn´ım slovem. T´ım dojde jednak ke zmenˇsen´ı velikosti slovn´ıku, ale pˇredevˇs´ım budou slova vyjadˇruj´ıc´ı naprosto shodnou informaci zápsána stejn´ ym zp˚ usobem, coˇz by mˇelo m´ıt pozitivn´ı dopad na algoritmy pouˇzité pro samotné dolován´ı. Case folding Volnˇe psan´ y text b´ yvá velice ˇcasto neuhlazený. Jelikoˇz b´ yvaj´ı zpracovávaná data vˇetˇsinou kolekc´ı dokument˚ u z r˚ uzn´ ych zdroj˚ u, tak je velice pravdˇepodobné, ˇze jednotlivé dokumenty pocházej´ı od r˚ uzn´ ych lid´ı, s r˚ uzn´ ymi návyky pˇri psan´ı. Stejná slova tak mohou b´ yt zapsána r˚ uznˇe a jedn´ım z rozd´ıl˚ u m˚ uˇze b´ yt pouˇzitá forma p´ısma. V textov´ ych datech se tak vyskytuj´ı slova psaná jak minuskami, tak i verzálkami. Nˇekteré texty mohou b´ yt napsány celé pomoc´ı minusek, jinde mohou b´ yt nˇekterá slova nebo i celé texty psané naopak pouze verzálkami, nˇekdy se vyskytnou i slova obsahuj´ıc´ı p´ısmena psaná r˚ uznou formou zcela nahodile (nˇekdy oznaˇcováno jako mixed-case). Pokud by texty z˚ ustaly ve své p˚ uvodn´ı podobˇe, mohou b´ yt stejná slova se stejn´ ym v´ yznamem vyjádˇrena hned nˇekolika unikátn´ımi prvky slovn´ıku, ˇcemuˇz se snaˇz´ı case folding zabránit. Jde ve své podstatˇe o pomˇernˇe konkrétn´ı pˇr´ıpad pˇredcházej´ıc´ı normalizace, protoˇze docház´ı k sjednocován´ı pouˇzité formy p´ısma. Nejjednoduˇsˇs´ım pˇr´ıstupem je celou mnoˇzinu dokument˚ u sjednotit bud’ do lower-case nebo upper-case podoby. T´ım vˇsak m˚ uˇze doj´ıt i sjednocen´ı zp˚ usobu zápisu slov, která vyjadˇruj´ı r˚ uzné vˇeci a mˇely by tedy z˚ ustat rozliˇsitelné. Jack Black (jm´ eno herce) ---> jack black (pˇ reklad: hever ˇ cern´ y) F.E.D. (jm´ eno u ´r ˇadu) ---> fed (pˇ reklad: nakrmen´ y) Pˇr´ıkladem mohou b´ yt nejr˚ uznˇejˇs´ı názvy nebo jména, která b´ yvaj´ı ˇcasto odliˇsena od klasick´ ych slov právˇe pomoc´ı formy p´ısma. Je moˇzné pouˇz´ıt heuristick´ y pˇr´ıstup, kdy ke zmˇenˇe formy p´ısma dojde pouze u nadpis˚ u nebo zaˇcátk˚ u vˇet a slova uvnitˇr vˇet jsou ponechána v p˚ uvodn´ım tvaru. Ve vˇetˇsinˇe pˇr´ıpad˚ u by tento postup

2.2


19

mˇel dosáhnout pomˇernˇe dobr´ ych v´ ysledk˚ u, ale na prvn´ı pohled je vidˇet, ˇze rozhodnˇe nejde o bezchybn´ y pˇr´ıstup. Pokud budou jména nebo názvy uvedeny na zaˇcátku vˇet nebo v nadpisech, tak dojde k jejich chybnému pˇrepsán´ı do lower-case podoby a spoléhá se zde na správné pouˇz´ıván´ı formy p´ısma samotn´ ymi autory textu. Z tohoto d˚ uvodu b´ yvá transformace veˇskerého textu do lower-case nejefektivnˇejˇs´ı (Manning, Raghavan, Sch¨ utze, 2008). Oprava pravopisu Oprava pravopisu je dnes jiˇz pomˇernˇe rozˇs´ıˇrenou souˇca´st´ı celé ˇrady program˚ u nebo aplikac´ı, které vetˇsina lid´ı bˇeˇznˇe vyuˇz´ıvá. Na kontrolu pravopisu je moˇzné narazit pˇri vyhledáván´ı pomoc´ı internetového vyhledávaˇce Google, kter´ y podtrˇzen´ım zv´ yrazn´ı nesprávnˇe napsaná slova v dotazu a samotné vyhledáván´ı provede pro dotaz s opravami. Textov´ y procesor MS Word, kter´ y je souˇca´st´ı kanceláˇrského bal´ıku od firmy Microsoft, podobn´ ym zp˚ usobem zv´ yrazˇ nuje nesprávná slova, pˇr´ıpadnˇe pˇreklepy pˇr´ımo opravuje. A stejnˇe tak se oprava pravopisu nacház´ı i v chytr´ ych telefonech. V rámci dolován´ı z textov´ ych dat je motivac´ı pro pouˇzit´ı korekce pravopisu zredukován´ı velikosti slovn´ıku, kdy nejr˚ uznˇejˇs´ı pˇreklepy mohou vytvoˇrit celou ˇradu neplatn´ ych slov, která budou m´ıt n´ızkou frekvenci v´ yskytu (Daˇrena, 2011) a m˚ uˇze tak doj´ıt ke sn´ıˇzen´ı kvality z´ıskané znalosti. Cel´ y proces opravy pravopisu je moˇzné rozdˇelit na dvˇe u ´lohy, a to nalezen´ı chyby a jej´ı následná oprava (Manning, Raghavan, Sch¨ utze, 2008). Jednotlivé chyby v textov´ ych datech lze také rozdˇelit do dvou kategori´ı. Prvn´ı jsou chyby, jejichˇz d˚ usledkem vznikaj´ı nová neplatná (smyˇslená) slova. graffe

--->

giraffe

Nejjednoduˇsˇs´ım pˇr´ıstupem pro odhalen´ı podobn´ ych chyb je pouˇzit´ı rozsáhlého slovn´ıku. Pro proveden´ı opravy je vytvoˇren seznam moˇzn´ ych kandidát˚ u a vybrán je ten nejpravdˇepodobnˇejˇs´ı. Pravdˇepodobnost je moˇzné urˇcit na základˇe Levenshteinovi vzdálenosti (oznaˇcováno také jako minimal edit distance) nebo na základˇe tzv. noisy channel modelu (Kernignan, Church, Gale, 1990). Druhou skupinou jsou chyby, u kter´ ych dojde k zámˇenˇe jednoho slova za slovo jiné. To se m˚ uˇze stát u tzv. homofonn´ıch slov, která poslechovˇe znˇej´ı totoˇznˇe, ale maj´ı r˚ uzn´ y zápis, nebo pouh´ ym prohozen´ım p´ısmen nebo zámˇenou p´ısmen. too beer table fee

---> ---> ---> --->

two bear label free

U této skupiny chyb je jejich oprava velice podobná, ale o nˇeco komplikovanˇejˇs´ı, protoˇze nelze jednoznaˇcnˇe urˇcit, které slovo bylo zapsáno chybnˇe. Pro kaˇzdé slovo je tedy vygenerován seznam kandidát˚ u, do kterého je zahrnuto jednak slovo sa-

2.2

20


motné, vˇsechna korektn´ı slova, která lze z´ıskat vloˇzen´ım, smazán´ım nebo substituc´ı jednoho p´ısmene. Je moˇzné zahrnout i slova homofonn´ı. V´ ybˇer správného (nejpravdˇepodobnˇejˇs´ıho) slova pak prob´ıhá opˇet na základˇe noisy channel modelu. Lemmatizace Lemmatizace je proces, pˇri kterém docház´ı k pˇreveden´ı slova do základn´ıho (téˇz slovn´ıkového nebo kanonického) tvaru, tzv. lemma. Lemmatizace prob´ıhá na základˇe morfologické anal´ yzy, pomoc´ı které se urˇc´ı, do jakého konkrétn´ıho tvaru má b´ yt urˇcité slovo pˇrevedeno. Bˇehem anal´ yzy se tedy nepracuje pouze s jedn´ım slovem, ale je zahrnuta vˇetˇs´ı ˇcást textu, aby bylo moˇzné správnˇe pochopit v´ yznam slova, a t´ım pádem urˇcit i jeho základn´ı tvar. Slova se totiˇz ve vˇetˇsinˇe jazyk˚ u ’ pouˇz´ıvaj´ı bud v odvozen´ ych nebo skloˇ novan´ ych tvarech. Tyto tvary slov mohou m´ıt napˇr´ıklad shodn´ y zápis s jin´ ymi slovy, která vˇsak maj´ı odliˇsn´ y v´ yznam (Manning, Raghavan, Sch¨ utze, 2008). I saw your saw in garage. ---> i see your saw in garage Pˇr´ıkladem m˚ uˇze b´ yt tvar nepravidelného anglického slovesa see (vidˇet) ve tvaru pro minul´ y ˇcas saw, kter´ y by mˇel b´ yt pˇrepsán na tvar infinitivu. Kdeˇzto podstatné jméno saw (pila) by mˇelo z˚ ustat nezmˇenˇeno. Implementace lematizéru je vˇsak pomˇernˇe nároˇcná. Proto se ˇcasto m´ısto lemmatizace pouˇz´ıvá pro pˇrevádˇen´ı slov do základn´ıho tvaru jednoduˇsˇs´ı pˇr´ıstup stemming. Stemming C´ılem stemmingu je, stejnˇe jako v pˇr´ıpadˇe lemmatizace, pˇrepis slov do jejich základn´ıho tvaru. Snahou je tedy odstranit odvozené tvary a skloˇ nované koncovky slov. Toho vˇsak jiˇz nen´ı dosahováno morfologickou anal´ yzou, ale prost´ ym aplikován´ım sady pˇrepisovac´ıch pravidel. Jednoduchost tohoto postupu se samozˇrejmˇe odráˇz´ı i na celkovém ˇcase zpracován´ı, kdy pˇri morfologické anal´ yze je tˇreba pracovat s vˇetˇs´ım mnoˇzstv´ım textov´ ych dat, aby bylo moˇzné správnˇe urˇcit základn´ı tvar slova. Pˇri stemmingu se pracuje pouze s jednotliv´ ymi slovy a pokud vyhovuje urˇcitému tvaru, aplikuje se pˇrepisovac´ı pravidlo. To vˇsak m˚ uˇze vést k mnoha chybn´ ym u ´pravám, které mohou vytvoˇrit nekorektn´ı slova. walking king sing

---> ---> --->

walk k s

Velice tedy záleˇz´ı na poˇrad´ı a správné formulaci pravidel pro proveden´ı u ´pravy. Pˇr´ıklad se slovy king a sing ukazuje chybnˇe zapsané pravidlo, které odstran´ı posledn´ı tˇri p´ısmena, pokud má slovo koncovku ing. Lepˇs´ı tvar pravidla by slovo pˇrepsal pouze v pˇr´ıpadˇe, ˇze se nˇekde ve slovˇe nacház´ı také samohláska. Nejpouˇz´ıvanˇejˇs´ım implementac´ı pouˇz´ıvanou pro stemming anglického textu je Porter˚ uv algoritmus. Cel´ y proces je rozdˇelen na celkem ˇctyˇri ˇca´sti, pˇriˇcemˇz v prvn´ım

2.2

21


kroku se provád´ı pˇrepis slov v mnoˇzném ˇc´ısle a pˇr´ıˇcest´ı minulém. Následuj´ıc´ı pravidla4 tvoˇr´ı jednu ze skupin, která je aplikována právˇe v této fázi (Porter, 1980). SSES -> SS IES -> I SS S

-> SS ->

caresses ponies ties caress cats

-> -> -> -> ->

caress poni ti caress cat

Odstranˇ en´ı stop slov Stop slova tvoˇr´ı zvláˇstn´ı skupinu slov. Vˇsechna slova, které by bylo moˇzné oznaˇcit jako stop slova, nemaj´ı z hlediska urˇcen´ı celkového v´ yznamu psaného textu pˇr´ıliˇs velkou informaˇcn´ı hodnotu. Pˇresto se vˇsak jedná o slova, která se v textu vyskytuj´ı velice ˇcasto, protoˇze jde o obecná slova. Typick´ ym pˇr´ıkladem stop slov mohou b´ yt pˇredloˇzky nebo spojky. Tato slova b´ yvaj´ı proto odstraˇ nována ze slovn´ıku, ˇc´ımˇz dojde k redukci jeho velikosti a sn´ıˇz´ı se nároky na pamˇet’ potˇrebou pˇri dolován´ı. Dále je uveden pˇr´ıklad stop slov pro anglick´ y a ˇcesk´ y jazyk. a, an, the, be, and, so, to, then, with, where, why, ... a, byl, tak, tato, kdy, pak, proto, nebo, kdyz, jen, ... Tato slova b´ yvaj´ı definována v tzv. seznamu stop slov (angl. stop words list). Jedn´ım z moˇzn´ ych zp˚ usob˚ u, jak podobn´ y seznam z´ıskat, je spoˇc´ıtat frekvenci v´ yskytu vˇsech slov napˇr´ıˇc celou kolekc´ı dokument˚ u a do seznamu zaˇradit ty s nejvˇetˇs´ım poˇctem v´ yskytu. Problém vˇsak spoˇc´ıvá v tom urˇcit, kolik nejˇcastˇejˇs´ıch slov zaˇclenit do seznamu. Nˇekdy m˚ uˇze b´ yt odstranˇen´ı stop slov také neˇzádouc´ı. Pokud se pracuje s frázemi, ˇcasto b´ yvaj´ı právˇe stop slova pomˇernˇe d˚ uleˇzitá pro z´ıskán´ı korektn´ı fráze (Manning, Raghavan, Sch¨ utze, 2008). Pˇri konstrukci seznamu stop slov b´ yvá také vhodné zohlednit oblast, které se zpracovávaná textová data t´ ykaj´ı. Typick´ y seznam slov je tak moˇzné rozˇs´ıˇrit o dalˇs´ı ˇcasto pouˇz´ıvaná obecná slova bez v´ yznamové hodnoty, které jsou pro danou oblast specifické, nebo naopak nˇekterá ˇcastá, ale v´ yznamovˇe hodnotná slova ze seznamu vyˇradit. Odstranˇ en´ı slov dle frekvence v´ yskytu Stejnˇe jako v pˇr´ıpadˇe odstranˇen´ı stop slov, kdy jsou ze slovn´ıku vyˇrazena nejˇcastˇeji se vyskytuj´ıc´ı obecná slova, je moˇzné zredukovat velikost slovn´ıku odstranˇen´ım dalˇs´ıch slov, ˇcistˇe dle frekvence jejich v´ yskytu. T´ım opˇet dojde ke sn´ıˇzen´ı nároˇcnosti na ’ pamˇet a m˚ uˇze odj´ıt ke zlepˇsen´ı pr˚ ubˇehu dolován´ı. Odebrat ze slovn´ıku je moˇzné bud’ slova s pˇr´ıliˇs velkou ˇcetnost´ı, coˇz b´ yvaj´ı zpravidla obecnˇejˇs´ı slova s menˇs´ı v´ yznamovou nebo informaˇcn´ı hodnotou, nebo naopak slova s pˇr´ıliˇs n´ızkou frekvenc´ı v´ yskytu, kdy 4

pˇrevzato z ˇcl´ anku An algorithm for suffix stripping

2.2

22


m˚ uˇze j´ıt o velice specifická slova pouˇzitá ve velmi malém mnoˇzstv´ı dokument˚ u, která také nebudou z hlediska co nejefektivnˇejˇs´ıho odhalen´ı (obecné) znalosti pˇr´ıliˇs ˇ pˇr´ınosná. Casto se také m˚ uˇze jednat o pˇreklepy (Daˇrena, 2011). Rozˇs´ıˇren´ı o fr´ aze Vˇetˇsina pˇredchoz´ıch operac´ı provádˇen´ ych pˇri pˇredzpracován´ı textov´ ych dat se zamˇeˇruje na zredukován´ı velikosti slovn´ıku a souˇcasném zv´ yˇsen´ı kvality z´ıskané znalosti. Nˇekdy vˇsak m˚ uˇze b´ yt prospˇeˇsné slovn´ık naopak rozˇs´ıˇrit o fráze, neboli n-tice slov. Nejzákladnˇejˇs´ı podobou fráz´ı jsou tzv. bigramy sloˇzené ze dvou slov, pˇr´ıpadnˇe trigramy sloˇzené ze tˇr´ı slov. Je samozˇrejmˇe moˇzné vytváˇret i delˇs´ı fráze obecnˇe z n slov, tzv. n-gramy. Toto rozˇs´ıˇren´ı slovn´ıku vˇsak nen´ı dobré aplikovat globálnˇe a vytvoˇrit vˇsechny moˇzné varianty, protoˇze ˇc´ım vˇetˇs´ı bude slovn´ık, t´ım nároˇcnˇejˇs´ı bude následné hledán´ı znalosti. Proto se zpravidla pouˇz´ıváj´ı pouze v´ yznamné fráze, které jsou pro pouˇzitá textová data typické. Pouˇzit´ı fráz´ı m˚ uˇze b´ yt také vhodné pˇri práci s velmi krátk´ ymi dokumenty, kdy se za u ´ˇcelem zlepˇsen´ı reprezentace dat jednotlivé dokumenty umˇele rozˇsiˇruj´ı dalˇs´ım textem. Model vektorov´ eho prostoru Pˇri dolován´ı je c´ılem odhalit nˇejakou obecnou znalost, kterou pak lze aplikovat na dalˇs´ı dokumenty, které nebyly pˇri hledán´ı pouˇzity. Z´ıskanou znalost´ı mohou b´ yt napˇr´ıklad spoleˇcné znaky pro urˇcitou skupinu dokument˚ u, na základˇe kter´ ych pak lze identifikovat pˇr´ısluˇsnost urˇcitého dokumentu do dané skupiny. Jednotlivé dokumenty je tedy tˇreba mezi sebou nˇejak´ ym zp˚ usobem porovnávat a pro tyto u ´ˇcely je také nutné zvolit vhodnou reprezentaci dokumentu. Model vektorového prostuoru je jednou z reprezentac´ı, která je zaloˇzena na bag-of-words. Poprvé byl uveden v ˇclánku z roku 1975 (Salton, Wong, Yang, 1975). Vˇsechny dokumenty z celé kolekce pouˇzité pˇri dolován´ı tvoˇr´ı spoleˇcnˇe prostor dokument˚ u. Pokud by slovn´ık vytvoˇren´ y nad tˇemito dokumenty obsahoval celkem tˇri slova, bylo by moˇzné kaˇzd´ y takov´ y dokument znázornit jako bod pomoc´ı kartézského souˇradnicového systému, pˇriˇcemˇz tˇri slova ze slovn´ıku by pˇredstavovala tˇri základn´ı osy x, y a z. Dokument lze tedy vyjádˇrit jako vektor, jehoˇz jednotlivé sloˇzky pˇredstavuj´ı ˇcetnost v´ yskytu kaˇzdého slova ze slovn´ıku v daném dokumentu (Turney, Pantel, 2010). Dokumenty vˇsak zpravidla b´ yvaj´ı mnohem delˇs´ı a velikost vygenerovaného slovn´ıku b´ yvá tedy mnohonásobnˇe vˇetˇs´ı neˇz pouhá tˇri slova. M´ısto trojrozmˇerného prostoru se pracuje s prostorem o n rozmˇerech, pˇriˇcemˇz n je rovna velikosti slovn´ıku. Kaˇzd´ y dokument je pak vyjádˇren pomoc´ı vektoru o n sloˇzkách. n = |vocabulary| d ∈ Nn d = (w1 , w2 , w3 , ..., wn )

2.2

23


Tomuto vektoru se také nˇekdy ˇr´ıká pˇr´ıznakov´ y vektor (angl. feature vector). Jako hodnoty jednotliv´ ych pˇr´ıznak˚ u vektoru se nejˇcastˇeji pouˇz´ıvaj´ı frekvence v´ yskytu jednotliv´ ych slov v daném dokumentu, kter´ ym jsou vˇsak pˇriˇrazeny statistické váhy pro urˇcen´ı d˚ uleˇzitosti kaˇzdého slova (Wang, Zhang, Vassileva, 2010). Kaˇzd´ y vektor reprezentuj´ıc´ı konkrétn´ı dokument je vˇsak velmi ˇr´ıdk´ y. To je typickou charakteristikou pro reprezentaci textov´ ych dat pomoc´ı vektoru. Tuto skuteˇcnost lze ukázat na vzorku uˇzivatelsk´ ych recenz´ı dostupn´ ych u produkt˚ u prodávan´ ych elektronick´ ym obchodem Amazon. Nad kolekc´ı obsahuj´ıc´ı celkem sto tis´ıc recenz´ı byl vygenerován slovn´ık o velikosti 13 026 slov. Nejkratˇs´ı dokument obsahoval celkem dvˇe slova, nejdelˇs´ı 187 slov a pr˚ umˇerná délka dokumentu byla dvacet ˇ slov. R´ıdkost vektoru reprezentuj´ıc´ı dokument o pr˚ umˇerné délce tak ˇcin´ı zhruba 99,85 %, takˇze drtivá vˇetˇsina sloˇzek vektoru je rovna nule. Na základˇe zp˚ usobu uchováván´ı hodnot ve vektorech je tedy moˇzné rozliˇsit dva hlavn´ı typy reprezentace: • hustá (angl. dense), • ˇr´ıdká (angl. sparse). U hust´ ych vektor˚ u jsou ukládány vˇsechny sloˇzky vektoru. Pokud by tedy byl dokument z kolekce v´ yˇse popsan´ ych recenz´ı reprezentován pomoc´ı hustého vektoru, obsahoval by celkem 13 026 sloˇzek, ze kter´ ych by pouh´ ych dvacet bylo nenulov´ ych. V pˇr´ıpadˇe ˇr´ıdkého vektoru jsou nulové hodnoty vypuˇstˇeny a nenulové hodnoty jsou ukládány jako dvojice index sloˇzky vektoru a hodnota dané sloˇzky. Aby byl tento zp˚ usob reprezentace efektivn´ı, mus´ı b´ yt alespoˇ n polovina sloˇzek vektoru nulová. U ukázkové kolekce dokument˚ u je v´ıce jak 99 procent hodnot nulov´ ych, takˇze reprezentace textov´ ych dat ˇr´ıdk´ ymi vektory je mnohem efektivnˇejˇs´ı neˇz u hust´ ych vektor˚ u. Celou kolekci dokument˚ u je moˇzné znázornit pomoc´ı tzv. term-document matice, ve které ˇrádky pˇredstavuj´ı jednotlivé dokumenty a sloupce jednotlivá slova ze slovn´ıku, oznaˇcované také jako termy (viz tabulka 1). Váˇzen´ı frekvence v´ yskytu slov v dokumentu má za u ´kol lépe vyjádˇrit d˚ uleˇzitost daného slova. Pokud se slovo vyskytne v dokumentu desetkrát, bude pro urˇcen´ı dokumentu d˚ uleˇzitˇejˇs´ı v´ıce, neˇz kdyby se v dokumentu vyskytlo pouze jednou. D˚ uleˇzitost tohoto slova vˇsak nen´ı desetkrát vˇetˇs´ı. Jiˇz zm´ınˇená stop slova jsou velice obecná, a proto se v dokumentech vyskytuj´ı ve velk´ ych poˇctech. Jejich informaˇcn´ı hodˇ ım nota je vˇsak velice malá. To samé do urˇcité m´ıry plat´ı i pro ostatn´ı slova. C´ ˇcastˇeji se v dokumentu vyskytuj´ı, t´ım b´ yvaj´ı obecnˇejˇs´ı a jejich informaˇcn´ı hodnota sp´ıˇse klesá. D˚ uleˇzitost slova tedy neroste proporcionálnˇe s poˇctem jejich v´ yskytu. Zp˚ usob, jak tuto skuteˇcnost prom´ıtnout do vektorové reprezentace dokumentu, ukazuje následuj´ıc´ı rovnice. weightd,t =

local weightd,t · global weightt normalizationd,t

2.2

24


Tabulka 1: Reprezentace kolekce dokument˚ u pomoc´ı Term-document count matrix

t1

t2

t3

···

tj

···

tn

d1

w11

w12

w13

···

w1j

···

w1n

d2

w21

w22

w23

···

w2j

···

w2n

d3 .. .

w31 .. .

w32 .. .

w33 .. .

··· .. .

w3j .. .

··· .. .

w3n .. .

di .. .

wi1 .. .

wi2 .. .

wi3 .. .

··· ...

wij .. .

··· ...

win .. .

dm

wm1

wm2

wm3

···

wmj

···

wmn

V´ ysledná váha pro slovo t v dokumentu d je dána jako souˇcin jeho lokáln´ı váhy (v rámci daného dokumentu) a jeho globáln´ıho váhy (v rámci celé kolekce dokument˚ u). Z´ıskan´ y souˇcin vah je pak moˇzné pomoc´ı pod´ılu normalizovat. Mezi nejˇcastˇeji pouˇz´ıvané funkce pro urˇcen´ı lokáln´ı váhy termu patˇr´ı (Singhal, 1997): • term frequency: tato funkce vrac´ı poˇcet v´ yskyt˚ u termu v daném dokumentu. function term-frequency(term, dokument) returns frekvence vstupy: term // poˇ cı ´tan´ y term dokument // seznam slov lok´ aln´ ı promˇ enn´ e: frekvence // poˇ cet v´ yskytu termu frekvence <- 0 for each slovo in dokument do if slovo shodn´ e s term then nav´ ys ˇit frekvence done return frekvence • term presence: tato binárn´ı funkce zcela ignoruje poˇcet v´ yskyt˚ u a vrac´ı pouze pˇr´ıznak, zda se term v dokumetu vyskytuje nebo ne.   1 pokud term-frequencyd,t > 0 local weightd,t =  0 jinak Pokud by byla pouˇzita pouze tato metoda váˇzen´ı, tak by celá kolekce dokument˚ u byla reprezentována zvláˇstn´ım pˇr´ıpadem matice – incidenˇcn´ı matice term-document.

2.2

25


• logarithmic term frequency: v´ ysledek této funkce je v základn´ı podobˇe poˇc´ıtán pomoc´ı následuj´ıc´ıho vztahu   log term-frequency pokud term-frequencyd,t > 0 10 d,t local weightd,t =  0 jinak Pomoc´ı tohoto zp˚ usobu lokáln´ıho váˇzen´ı v´ yskytu termu je moˇzné zohlednit v´ yˇse popsan´ y problém s neproporcionáln´ım r˚ ustem d˚ uleˇzitosti termu vzhledem k frekvenci jeho v´ yskytu. D´ıky charakteristice logaritmické funkce se tedy s rostouc´ı frekvenc´ı v´ yskytu zpomaluje r˚ ust d˚ uleˇzitosti. Je moˇzné pouˇz´ıt i lehce upravenou variantu   1 + log term-frequency 10 d,t pokud term-frequencyd,t > 0 local weightd,t =  0 jinak vyuˇz´ıvaj´ıc´ı tzv. aditivn´ıho vyhlazován´ı (angl. add-one smoothing). • augmented term frequency: pˇri pouˇzit´ı této funkce docház´ı k zredukován´ı rozsahu pˇr´ır˚ ustk˚ u d˚ uleˇzitosti do urˇcitého intervalu, nejˇcastˇeji do rozmez´ı hodnot 0,5 a 1,0. Pracuje se s pˇredpokladem, ˇze pouhá pˇr´ıtomnost slova je ohodnocena základn´ı hodnotou k (obvykle 0,5). Za kaˇzd´ y dalˇs´ı v´ yskyt je tato hodnota lineárnˇe nav´ yˇsena aˇz po nejvyˇsˇs´ı frekvenci, pro kterou bude vrácena maximáln´ı hodnota intervalu (1,0). V´ ypoˇcet vypadá následovnˇe local weightd,t = k + (1 − k) ·

term-frequencyd,t max-term-frequencyd

• okapi’s term frequency: tato funkce je zaloˇzena na aproximaci 2-Poissonova modelu a jej´ı charakteristika je velice podobná funkci logarithmic term frequency. local weightd,t =

term-frequencyd,t 2 + term-frequencyd,t

Pro urˇcen´ı celkové váhy vˇsak pouhé lokáln´ı váˇzen´ı frekvence v´ yskytu termu nestaˇc´ı. Pˇri hodnocen´ı d˚ uleˇzitosti daného slova je nutné zohlednit nejen jeho v´ yznamnost v rámci dokumentu, ale také v rámci celé kolekce dokument˚ u. V opaˇcném pˇr´ıpadˇe by doˇslo k tomu, ˇze vˇsechna slova, i kdyˇz se vyskytnou v rámci celé kolekce pouze v jednom dokumentu, jsou brána jako informaˇcnˇe stejnˇe pˇr´ınosná. K tomuto rozliˇsen´ı slouˇz´ı globáln´ı váˇzen´ı termu. Moˇznost´ı je opˇet nˇekolik: • ˇzádné váˇzen´ı: zohlednˇen´ı globáln´ı váhy slova pˇri v´ ypoˇctu jeho celkové váhy je moˇzné vyruˇsit nastaven´ım jednotkové váhy global weightt = 1

2.2

26


• inverse document frequency: základem pro v´ ypoˇcet globáln´ı váhy termu je poˇcet dokument˚ u, ve kter´ ych se dan´ y term vyskytuje. function document-frequency(term, dokumenty) returns frekvence vstupy: term // poˇ cı ´tan´ y term dokumenty // seznam seznam˚ u slov lok´ aln´ ı promˇ enn´ e: frekvence // poˇ cet v´ yskytu termu frekvence <- 0 for each dokument in dokumenty do if dokument obsahuje term then nav´ ys ˇit frekvence done return frekvence C´ılem vˇsak je sn´ıˇz´ıt v´ yznamnost termu, kter´ y lze povaˇzovat za obecn´ y, tedy v ˇc´ım vˇetˇs´ım mnoˇzstv´ı dokument˚ u se term vyskytuje, t´ım niˇzˇs´ı by mˇela b´ yt jeho v´ yznamnost. Frekvence v´ yskytu slova v rámci dokumentu by tedy mˇela b´ yt redukována hodnotou, která roste s niˇzˇs´ım v´ yskytem termu v rámci kolekce dokument˚ u. Toho je moˇzné dosánout pouˇzit´ım inverzn´ı relativn´ı hodnoty v´ yskytu termu v kolekci. global weightt = log

m document-frequencyt

Logaritmus je zde, stejnˇe jako u frekvenci v´ yskytu termu v dokumentu, pouˇzit pro zredukován´ı r˚ ustu hodnot. Tento zp˚ usob váˇzen´ı je vˇetˇsinou oznaˇcován zkratkou IDF. • probabilistic inverse document frequency: tato funkce je velice podobná funkci IDF, ale v´ ypoˇcet d˚ uleˇzitosti termu je zaloˇzen na pravdˇepodobnosti relevance daného termu, coˇz je pod´ıl poˇctu dokument˚ u neobsahuj´ıc´ıch term v˚ uˇci poˇctu dokument˚ u obsahuj´ıc´ıch term. global weightt = log

m − document-frequencyt document-frequencyt

• global frequency inverse document frequency: tato funkce pˇriˇrazuje nejmenˇs´ı moˇzné hodnoty term˚ um, které se vyskytuj´ı ve vˇsech dokumentech. global weightt = log

global-frequencyt document-frequencyt

Pomoc´ı globáln´ıch vah je tedy moˇzné zohlednit frekvenci v´ yskytu termu v celé kolekci dokument˚ u a pˇridat tak na d˚ uleˇzitosti ménˇe pouˇz´ıvan´ ym slov˚ um a zároveˇ n ubrat na d˚ uleˇzitosti mnohem obecnˇejˇs´ım slov˚ um, která se objevuj´ı ve vˇetˇsinˇe dokument˚ u z kolekce. V´ ysledkem souˇcinu lokáln´ı a globáln´ı váhy je tedy celková váha termu. Posledn´ım krokem ve v´ ypoˇctu vektor˚ u je jejich normalizace. D˚ uvodem

2.2

27


provádˇen´ı normalizace je zajiˇstˇen´ı toho, aby dokumenty pouˇz´ıvaj´ıc´ı stejná slova byly ve vektorovém prostoru reprezentovány body leˇz´ıc´ımi bl´ızko sebe. Bez proveden´ı normalizace totiˇz mohou b´ yt dokumenty obsahuj´ıc´ı podobná slova od sebe znaˇcnˇe vzdáleny. D˚ uvodem mohou b´ yt jejich rozd´ılné délky, d´ıky kter´ ym jsou stejná slova vyjádˇrena rozd´ıln´ ymi (násobn´ ymi) hodnotami. Nav´ıc delˇs´ı dokumenty obsahuj´ı v´ıce slov a d˚ usledkem je opˇet prodluˇzován´ı vzdálenosti mezi dokumenty. Vliv pouˇzit´ı ˇci nepouˇzit´ı normalizace je moˇzné ukázat na jednoduchém pˇr´ıkladu, kdy je k dispozici zjednoduˇsená kolekce ˇctyˇr dokument˚ u, ve kter´ ych jsou pouˇzita pouze dvˇe slova. vocabulary = (dobre, rano) d_1 d_2 d_3 d_4

= = = =

"dobre rano" "dobre" "rano" "dobre rano dobre rano"

-> -> -> ->

d_1 d_2 d_3 d_4

= = = =

(1, (1, (0, (2,

1) 0) 1) 2)

-> -> -> ->

d_1 d_2 d_3 d_4

= = = =

(0.12, (0.12, (0.00, (0.24,

0.12) 0.00) 0.12) 0.24)

Z hlediska podobnosti by mˇel b´ yt prvn´ı dokument nejbl´ıˇze ke ˇctvrtému dokumentu, protoˇze obsahuj´ı v´ıce stejn´ ych slov, zat´ımco s dalˇs´ımi dvˇema dokumenty má spoleˇcné pouze jedno slovo. Na obrázku 3 jsou dokumenty zobrazeny ve dvourozmˇerném

Obrázek 3: Zn´ azornˇen´ı vzd´ alenosti dokument˚ u ve vektorovém prostoru vyjádˇren´ ych pomoc´ı TF-IDF

prostoru, spolu s jejich vzdálenost´ı od prvn´ıho dokumentu. Proveden´ım normalizace dojde k pˇrepoˇc´ıtán´ı jednotliv´ ych sloˇzek vektor˚ u, které pak budou náleˇzet do prostoru vyhrazeném jednotkov´ ym vektorem, ˇc´ımˇz dojde k pˇr´ıbl´ıˇzen´ı vektor˚ u se stejn´ ymi slovy, ale r˚ uzn´ ymi poˇcty v´ yskytu tˇechto slov. V pˇr´ıpadˇe ukázkové kolekce dokument˚ u budou vektory reprezentuj´ıc´ı prvn´ı a ˇctvrt´ y dokument po normalizaci totoˇzné. Dále jsou uvedeny nˇekteré techniky pro proveden´ı normalizace délky vektoru: • ˇzádná normalizace: stejnˇe jako u globáln´ı váhy je moˇzné potlaˇcit i efekt nor-

2.3

28

Klasifikace dokument˚ u

malizace a ponechat vektory v p˚ uvodn´ı podobˇe normalizationd,t = 1 • cosine normalization: kosinová normalizace patˇr´ı mezi nejpouˇz´ıvanˇejˇs´ı pˇr´ıstupy pro normalizaci délek vektor˚ u. Pro pˇreveden´ı vektoru do jednotkového prostoru se pouˇz´ıvá Eukleidovská délka daného vektoru. Aplikován´ım normalizace je pak ˇ ım jsou vyˇsˇs´ı hodnoty v´ kaˇzdá sloˇzka vektoru podˇelena jeho délkou. C´ yskytu slov v dokumentu, t´ım se celková délka vektoru prodluˇzuje a vyˇsˇs´ı dˇelitel tak v´ıce sniˇzuje váhu slova. Stejnˇe tak vˇetˇs´ı mnoˇzstv´ı slov v dokumentu prodluˇzuje délku jeho vektoru a opˇet navyˇsuje hodnotu dˇelitele. Tento zp˚ usob normalizace tedy zohledˇ nuje oba d˚ usledky delˇs´ıch dokument˚ u. v u n uX 2 wd,i normalizationd,t = t n=1

• maximum term-frequency normalization: normalizace vyuˇz´ıvaj´ıc´ı pro pˇrevod váh slov do jednotkového prostoru maximáln´ı váhu v dokumentu je principem totoˇzná s jiˇz zm´ınˇen´ ym zp˚ usobem v´ ypoˇctu globáln´ı váhy pomoc´ı funkce augmented term frequency. Ta pˇriˇrazovala urˇcitou základn´ı váhu minimáln´ı hodnotˇe frekvence slova v kolekci dokument˚ u a zbytek z jednotkového intervalu rovnomˇernˇe rozdˇelila mezi ostatn´ı hodnoty v´ yskytu. Slovo s maximáln´ım v´ yskytem tak bylo vˇzdy pˇrepoˇc´ıtáno na hodnotu 1. Stejn´ y princip je moˇzné pouˇz´ıt i pˇri normalizaci délky vektoru. normalizationd,t = max-weightd Nev´ yhodou tohoto pˇr´ıstupu je, ˇze pˇri normalizaci jsou ve v´ ypoˇctu zohlednˇeny pouze vyˇsˇs´ı hodnoty v´ yskytu slov v dokumentu. Problém s prodluˇzován´ım vzdálenosti v d˚ usledku vˇetˇs´ıho poˇctu slov u delˇs´ıch dokument˚ u tento zp˚ usob normalizce neˇreˇs´ı. Uveden´ y v´ yˇcet zp˚ usob˚ u v´ ypoˇctu váhy slova rozhodnˇe nepˇredstavuje kompletn´ı v´ yˇcet. C´ılem je sp´ıˇse poskytnout základn´ı pˇredstavu o moˇznostech reprezentace textov´ ych dat pomoc´ı vektor˚ u a nast´ınit v´ yhody a nev´ yhody r˚ uzn´ ych pˇr´ıstup˚ u. Obecnˇe se pro urˇcen´ı vah nejˇcastˇeji pouˇz´ıvá schéma Term frequency-Inverse Document Frequency, zkrácenˇe TF-IDF, a pˇri nutnosti normalizace délek v´ ysledn´ ych vektor˚ u je pouˇzita kosinová normalizace.

2.3


Klasifikace textov´ ych dokument˚ u je jedn´ım z typick´ ych problém˚ u, které lze v rámci dolován´ı znalost´ı z textov´ ych dat ˇreˇsit. Mimo klasifikaci jde také o predikci, vyhledáván´ı a extrakci informac´ı (Weiss et. 2010). Pˇred samotn´ ym formáln´ım popisem problému klasifikace dokument˚ u bude uvedeno nˇekolik reáln´ ych problém˚ u, pro jejichˇz ˇreˇsen´ı se vyuˇz´ıvá právˇe klasifikace.

2.3


29

Zˇrejmˇe nejrozˇs´ıˇrenˇejˇs´ım pˇr´ıkladem, se kter´ ym si dnes a dennˇe setkává vˇetˇsina lid´ı, je detekován´ı nevyˇza´dané poˇsty oznaˇcované jako spam. Vˇetˇsina elektronické poˇsty obsahuje pouze textová data, nˇekdy vˇsak b´ yvaj´ı obohaceny o HTML tagy. To samo o sobˇe uˇz m˚ uˇze slouˇzit jako atribut dokumentu, pomoc´ı kterého je moˇzné urˇcit, zda se jedná o spam ˇci nikoliv. Pˇri klasifikaci elektronické poˇsty je moˇzné kromˇe From: [email protected] Subject: M´ ame pro V´ as pen´ ıze zdarma - kdo si hraje, nezlob´ ı! Date: 15 November 2012 08:57:51 CET To: Zdenˇ ek Nov´ ak -----------------------------------------------------------------Vyuˇ zijte speci´ aln´ ı nab´ ıdky, jak z´ ıskat pen´ ıze. ˇ Cek´ a v´ as propracovan´ a grafika, napˇ et´ ı a z´ abava. Zahrajte si 50x zdarma obl´ ıbenou hru na internetu. Vˇ se, co vyhrajete si m˚ uz ˇete nechat! ZAˇ C´ IT HR´ AT

Obrázek 4: Uk´ azka elektronické poˇsty ozanˇcováné jako spam

samotného textu zprávy vyuˇz´ıt i dalˇs´ı atributy, jako adresa odes´ılatele nebo text pˇredmˇetu zprávy. Na ukázkovém mailu (viz obrázek 4) je vidˇet, ˇze pˇredmˇet obsahuje slova jako pen´ıze, zdarma, a také vykˇriˇcn´ık. Stejnˇe tak adresa odes´ılatele nemá u ´plnˇe typick´ y tvar a nenacház´ı-li se jiˇz v pˇr´ıjemcovˇe kontaktn´ım adresáˇri, m˚ uˇze pˇrispˇet ke klasifikaci zprávy jako nevyˇza´dané. Z hlediska klasifikace textu je vˇsak nejd˚ uleˇzitˇejˇs´ı text zprávy. Ten opˇet obsahuje slova jako speciáln´ı nab´ıdka, pen´ıze, zábava, zdarma, které jsou typické sp´ıˇse pro spam. Vˇsechny tyto atributy mailu mohou b´ yt vyuˇz´ıvány klasifikátorem, kter´ y na základˇe adresy odes´ılatele a pˇr´ıtomnosti urˇcit´ ych slov ve zprávˇe ˇci jej´ım pˇredmˇetu rozhodne, zda novˇe pˇr´ıchoz´ı poˇsta skonˇc´ı ve spamovém koˇsi. Dalˇs´ım pˇr´ıkladem klasifikaˇcn´ı u ´lohy je anal´ yza m´ınˇen´ı. Typick´ ym zástupcem anal´ yzy m´ınˇen´ı je kategorizace psan´ ych recenz´ı na pozitivn´ı a negativn´ı. Princip je stejn´ y jako v pˇr´ıpadˇe odhalován´ı nevyˇza´dané poˇsty. V textu recenze se hledaj´ı urˇcitá slova, která sv´ ym v´ yznamem pomohou urˇcit, jak´ y je v´ yznam celého textu. Ve dvou ˇ ukázkov´ ych recenz´ıch pˇrevzat´ ych z Cesko-Slovenské filmové databáze (viz obrázek 5) jsou tato slova na prvn´ı pohled snadno identifikovatelná. V prvn´ı recenzi jsou pouˇzita slova jako skvˇelý, výteˇcný, perfektn´ı nebo l´ıbit, která dávaj´ı vcelku jasn´ y signál o spokojenosti uˇzivatele s filmem. Oproti tomu v druhé recenzi jsou naopak slova s negativn´ım sentimentem jako nuda, straˇsné ˇci pˇrecenit. Tyto pˇr´ıklady

2.3


30

Skvˇ el´ y film, v´ ıteˇ cn´ y J.Nicholson. jak se dok´ azal pohybovat mezi bl´ azny a pefektnˇ e zahr´ at. Moc se mi to l´ ıbilo :-) 92% Nuda, nuda, straˇ sn´ a nuda. Nech´ apem, ako sa podarilo takto precenit’ tento film u takej vel’kej masy div´ akov... Z´ azrak. -----------------------------------------------------------------Film je zcela brilantn´ ım d´ ılem, naprost´ y skvost ve sv´ e kategorii, dosahuje t´ emˇ eˇ r stejn´ ych kvalit jako Catwoman s Halle Berry.

Obrázek 5: Uk´ azka uˇzivatelsk´ ych recenz´ı. Zdroj: http://www.csfd.cz/film/2982-prelet-nad-kukaccim-hnizdem/

slouˇz´ı vˇsak pouze pro ilustraci, protoˇze text m˚ uˇze ˇcasto obsahovat slova, která obrac´ı v´ yznam nˇekter´ ych pˇr´ıdavn´ ych jmen. Nejnároˇcnˇejˇs´ı mohou pro automatizovanou klasifikaci textu b´ yt ironické vˇety, které sice obsahuj´ı pozitivn´ı slova, ale jejich v´ yznam je pˇresnˇe opaˇcn´ y. Pro ˇclovˇeka by nemˇel b´ yt problém rozpoznat negativn´ı tón smyˇslené recenze (viz obrázek 5), avˇsak pokud nen´ı seznámen s velice negativn´ım popkulturn´ım m´ınˇen´ım o filmu Catwoman, na kter´ y se text recenze odvolává, m˚ uˇze i ˇclovˇek doj´ıt k mylnému závˇeru. Pro klasifikátor je situace v podstatˇe velice podobná a bez zahrnut´ı znalosti o kvalitách ostatn´ıch film˚ u je odkázán pouze na text recenze, kter´ y obsahuje pˇreváˇznˇe pozitivn´ı slova. Je tedy velice pravdˇepodbné, ˇze podobn´ y text by byl chybnˇe oznaˇcen jako pozitivn´ı. Klasifikace je vˇsak velice obecnou u ´lohou a aplikovat ji lze na celou ˇradu problém˚ u, nejen v oblasti zpracován´ı textov´ ych dat. Zde jsou uvedeny nˇekteré typické klasifikaˇcn´ı u ´lohy s textov´ ymi daty (Manning, Raghavan, Sch¨ utze, 2008): • detekce spamu, • anal´ yza m´ınˇen´ı, • pˇriˇrazen´ı autora, • identifikace jazyka, • rozliˇsen´ı pohlav´ı autora, • kategorizace ˇclánk˚ u dle tématu. C´ılem klasifikace textov´ ych dokument˚ u je umoˇznit automatické pˇr´ıˇrazován´ı dokumentu d do jedné z moˇzn´ ych tˇr´ıd c. Pokud definujeme mnoˇzinu moˇzn´ ych tˇr´ıd jako C = {c1 , c2 , c3 , ..., c|C| } a mnoˇzinu dokument˚ u jako D = {d1 , d2 , d3 , ..., d|D| }, tak je moˇzné klasifikaci formálnˇe definovat jako funkci, která pˇriˇrazuje kaˇzdé uspoˇra´dané dvojici (di , cj ) ∈ D × C logickou hodnotu pravda, pokud di náleˇz´ı

2.3


31

do cj a nepravda v opaˇcném pˇr´ıpadˇe. Po definovan´ı mnoˇziny logick´ ych hodnot L = {pravda, nepravda} je tedy moˇzné zapsat klasifikaˇcn´ı funkci v následuj´ıc´ım tvaru: Φ:D×C →L ˇ sen´ım klasifikaˇcn´ı u ˆ která je co nejpˇresnˇejˇs´ı aproReˇ ´lohy je vˇsak nalezen´ı funkce Φ, ximac´ı funkce Φ. Tato funkce je oznaˇcována jako klasifikátor (Sebastiani, 2005). D˚ uvodem, proˇc se zab´ yvat ˇreˇsen´ım automatické klasifikaci textov´ ych dokuˇ ek si pˇredevˇs´ım mus´ı cel´ ment˚ u, je pˇredevˇs´ım nároˇcnost ruˇcn´ıho tˇr´ıdˇen´ı text˚ u. Clovˇ y text pˇreˇc´ıst, aby plnˇe porozumˇel jeho obsahu a mohl jej správnˇe zaˇradit do nˇekteré ze tˇr´ıd. To sice nemus´ı b´ yt problém napˇr´ıklad u recenz´ı, které b´ yvaj´ı vˇetˇsinou krátké a jejich pˇreˇcten´ı tak zabere maximálnˇe nˇekolik málo minut, vˇetˇsinou jich vˇsak b´ yvá velké mnoˇzstv´ı. Klasifikace velkého mnoˇzstv´ı textov´ ych dokument˚ u ˇcistˇe lidsk´ ymi silami je tedy velice nároˇcná (Manning, Raghavan, Sch¨ utze, 2008). Pokud by bylo nutné dosáhnout v´ ysledk˚ u v co nejkratˇs´ım ˇcase, je tˇreba do klasifikace zaˇradit vˇetˇs´ı mnoˇzstv´ı lid´ı, mezi které by byly jednotlivé dokumenty rozdˇeleny. Tento pˇr´ıstup v sobˇe vˇsak skr´ yvá problém souvisej´ıc´ı s jednou z charakteristik klasifikace. Rozhodnut´ı o pˇr´ısluˇsnosti dokumentu do urˇcité tˇr´ıdy je ovlivnˇen zkuˇsenostmi jednotliv´ ych lid´ı a koneˇcné zaˇrazen´ı dokumentu je v´ ysledkem subjektivn´ıho rozhodnut´ı (Sebastiani, 2005). R˚ uzn´ı lidé se tak velice ˇcasto nemus´ı na pˇr´ısluˇsnosti dokumentu do tˇr´ıdy shodnout. Rozdˇelen´ım klasifikace skupiny dokument˚ u mezi v´ıce lid´ı tedy dojde ke ztrátˇe konzistence pˇri pˇridˇelován´ı tˇr´ıd. Pouˇzit´ım automatického klasifikátoru je tento problém eliminován. Dokument je v jednoduˇsˇs´ı variantˇe klasifikace zaˇrazován vˇzdy v´ yhradnˇe do jedné ze tˇr´ıd. Pro kaˇzd´ y dokument di ∈ D tedy plat´ı, ˇze má pˇriˇrazenu pouze jednu tˇr´ıdu cj ∈ C. Dokument je stejnˇe tak moˇzné klasifikovat do v´ıce tˇr´ıd, vˇcetnˇe nezaˇrazen´ı do ´ ˇza´dné ze tˇr´ıd. Nejˇcastˇeji b´ yvá klasifikaˇcn´ı u ´loha ˇreˇsena jako binárn´ı. Ukolem klasifikátoru je tedy zaˇradit dokument pouze do jedné ze dvou tˇr´ıd, coˇz lze pˇreformulovat na problém pˇriˇrazen´ı ˇci nepˇriˇrazen´ı do jedné tˇr´ıdy (druhou tˇr´ıdu pˇredstavuje doplnˇek tˇr´ıdy prvn´ı). Funkce binárn´ıho klasifikátoru je t´ım pádem definována jako aproximace funkce Φ : D → L. Binárn´ıho klasifikátoru je moˇzné vyuˇz´ıt i pro ˇreˇsen´ı klasifikaˇcn´ı u ´lohy s v´ıce tˇr´ıdami, a to tak, ˇze se pro kaˇzdou tˇr´ıdu vytvoˇr´ı zvláˇstn´ı binárn´ı klasifikátor. Koneˇcn´ y klasifikátor pro celou mnoˇzinu tˇr´ıd C tvoˇr´ı skupina tˇechto binárn´ıch klasifikátor˚ u. D˚ uvodem pro ˇreˇsen´ı v´ıcetˇr´ıdn´ı klasifikace t´ımto zp˚ usobem je menˇs´ı sloˇzitost tvorby binárn´ıho klasifikátoru. Pro nalezen´ı aproximaˇcn´ı funkce a vytvoˇren´ı klasifikátoru se pouˇz´ıvaj´ı r˚ uzné algoritmy strojového uˇcen´ı. Ty maj´ı za u ´kol automaticky odhalit na mnoˇzinˇe tzv. trénovac´ıch dat pravidla, pomoc´ı kter´ ych se následnˇe rozhoduje o pˇr´ısluˇsnosti dokumentu do urˇcité tˇr´ıdy. Aby bylo moˇzné tato pravidla v textov´ ych datech nalézt, je nutné poskytnout dostateˇcnˇe velkou mnoˇzinu trénovac´ıch dokument˚ u, ale zároveˇ n co nejv´ıce vyváˇzenou z hlediska poˇctu dokument˚ u zastupuj´ıc´ıch jednotlivé tˇr´ıdy. Z toho také plyne, ˇze vˇsechny dokumenty z trénovac´ı mnoˇziny mus´ı m´ıt pˇriˇrazenu nˇekterou ze tˇr´ıd, které chceme pomoc´ı klasifikátoru rozeznávat.

2.3

32


Bayesovsk´ y klasifik´ ator Naivn´ı Bayes˚ uv klasifikátor patˇr´ı k základn´ım algoritm˚ um strojového uˇcen´ı, které se pouˇz´ıvaj´ı pˇri klasifikaci textov´ ych dat. Jde o jednoduch´ ych pˇr´ıstup ke klasifikaci, jehoˇz základem je tzv. Bayesovsk´ y teorém (Manning, Raghavan, Sch¨ utze, 2008) P (cj |di ) =

P (di |cj )P (cj ) P (di )

Pˇri v´ ypoˇctu se pracuje s apriorn´ı pravdˇepodobnost´ı v´ ybˇeru klasifikaˇcn´ı tˇr´ıdy c P (cj ), tedy ˇze náhodnˇe vybran´ y dokument bude patˇrit do tˇr´ıdy c, dále s pravdˇepodobnost´ı v´ ybˇeru dokumentu d P (di ) a s pravdˇepodobnost´ı v´ yskytu dokumentu d ve tˇr´ıdˇe c P (di |cj ). V´ ysledkem v´ ypoˇctu je podm´ınˇená pravdˇepodobnost, ˇze pˇri v´ ybˇeru dokumentu d bude jeho klasifikaˇcn´ı tˇr´ıdou tˇr´ıda c. Aby tedy bylo moˇzné urˇcit tˇr´ıdu, do které náhodnˇe vybran´ y dokument patˇr´ı, je tˇreba z trénovac´ıch dat vypoˇc´ıta jednotlivé pravdˇepodobnosti P (cj ), P (di ) a P (di |cj ). Pro urˇcen´ı tˇr´ıdy neznámého dokumentu se následnˇe spoˇc´ıtaj´ı pravdˇepodobnosti P (c|d), a to pro vˇsechny moˇzné tˇr´ıdy. c = argmax P (cj |di ) cj ∈C

= argmax cj ∈C

P (di |cj )P (cj ) P (di )

= argmax P (di |cj )P (cj ) cj ∈C

Dokument je zaˇrazen do té tˇr´ıdy, která maximalizuje aposteriorn´ı pravdˇepodobnost P (c|d). Pˇri v´ ypoˇctu byl vypuˇstˇen dˇelitel s pravdˇepodobnost´ı dokumentu, protoˇze jde o konstantn´ı hodnotu a nemá tud´ıˇz na v´ ysledek ˇza´dn´ y vliv. Jelikoˇz jsou texty reprezentovány pomoc´ı pˇr´ıznako´ ych vektor˚ u, je ignorováno poˇrad´ı slov v daném dokumentu. Zároveˇ n se (naivnˇe) pˇredpokládá, ˇze jednotlivé pˇr´ıznaky jsou na sobˇe vzájmnˇe nezávislé. Pravdˇepodobnost P (di |cj ) je tedy dána jako souˇcin pravdˇepodobnosti v´ yskytu slov w ve tˇr´ıdˇe c. Y P (w1 , w2 , w3 , ..., wn |cj ) = P (wk |cj ) wk ∈di

c = argmax P (cj ) cj ∈C

Y

P (wk |cj )

wk ∈di

Rozhodovac´ı stromy Intuitivn´ım pˇr´ıstupem ke klasifikaci textov´ ych dat jsou rozhodovac´ı pravidla, kdy se na základˇe pˇr´ıtomnosti konkrétn´ıch slov rozhodne, do jaké tˇr´ıdy dokument patˇr´ı. Rozhodovac´ı stromy jsou implementac´ı tohoto pˇr´ıstupu. Jde o v´ yznaˇcn´ y typ grafu,

2.3

33


kter´ y obsahuje dva typy uzl˚ u, prvn´ım jsou rozhodovac´ı uzly, které pˇredstavuj´ı jednotlivá rozhodovac´ı pravidla. Dle moˇzn´ ych odpovˇed´ı na dané pravidlo vede z rozhodovac´ıho uzlu stejn´ y poˇcet hran. Druh´ ym typem uzlu jsou listy uchovávaj´ıc´ı tˇr´ıdu, do které je dokument klasifikován. Pˇri klasifikaci se postupuje od prvn´ıho pravidla (koˇrene stromu) a postupn´ ym vyhodnocován´ım pravidel se pˇres hrany dokument pˇresunuje do podstrom˚ u, aˇz doraz´ı k jednomu z list˚ u, ˇc´ımˇz dojde k pˇripˇrazen´ı dokumentu do tˇr´ıdy reprezentované dan´ ym listem (Russell, Norvig, 1995). Z trénovac´ıch dat se tedy pˇri dolován´ı extrahuj´ı pravidla a odpovˇedi, které vytvoˇr´ı rozhodovac´ı strom. Snahou je, aby bylo pravidel co nejménˇe a strom byl co nejjednoduˇsˇs´ı, tzn. aby odpovˇedi co nejv´ıce rozdˇelovaly data do jednotliv´ ych tˇr´ıd. Pokud je k dispozici mnoˇzina dokument˚ u obsahuj´ıc´ı 50 pˇr´ıklad˚ u za kaˇzdou ze dvou tˇr´ıd, tak by ˇspatné pravidlo tuto mnoˇzinu rozdˇelilo na podmnoˇziny, ve kter´ ych budou obˇe tˇr´ıdy zastoupeny opˇet stejn´ ym poˇctem dokument˚ u. Dobré pravidlo by naopak vytvoˇrilo v´ıce homogenn´ı podmnoˇziny, ve kter´ ych by v´ yraznˇeji pˇrevaˇzovala jedna tˇr´ıda. Vyuˇzit´ı zde tedy nalézá teorie informace. Pravidla jsou vytváˇrena tak, aby pokud moˇzno co nejv´ıce minimalizovala m´ıru nevˇedomosti ˇci chaosu poˇc´ıtanou pomoc´ı entropie. X H(X) = − pi log2 pi Atribut dat (v pˇr´ıpadˇe textu slovo) zvolen´ y jako rozdˇelovac´ı parametr mus´ı analogicky maximalizovat informaˇcn´ı zisk. Pro kaˇzd´ y atribut je tedy spoˇc´ıtána tato hodnota a pro rozdˇelen´ı se zvol´ı ten, kter´ y poskytne maximáln´ı informaˇcn´ı zisk. Ten se poˇc´ıtá jako váˇzen´ y souˇcet entropi´ı jednotliv´ ych podmnoˇzin odeˇcten´ y od nynejˇs´ı entropie. Neuronov´ e s´ıtˇ e Snahou algoritmu neuronov´ ych s´ıt´ı je napodobit princip fungován´ı lidského mozku, konkrétnˇeji zp˚ usobu, jak´ ym se mozek uˇc´ı nov´ ym znalostem. Základn´ı stavebn´ı jednotkou v mozku je buˇ nka zvaná neuron. Jeho u ´ˇcelem je pˇrij´ımán´ı nervov´ ych impuls˚ u pomoc´ı dendrit˚ u a naopak v´ ys´ılán´ı nervov´ ych impuls˚ u k ostatn´ım neuron˚ um skrze axony. V´ ystupn´ı signál je vˇsak neuronem vyslán pouze ve chv´ıli, kdy jeho vstupn´ı ˇıma, Neruda, 1996). Umˇelé neuronové signály pˇrekroˇc´ı urˇcitou prahovou hodnotu (S´ s´ıtˇe modeluj´ı biologickou neuronovou s´ıt’ a jej´ım základn´ım prvkem je tedy umˇel´ y neuron, oznaˇcován také jako perceptron. Princip fungován´ı je zcela totoˇzn´ y s biologick´ ym neuronem. Perceptron pˇrij´ımá na vstupech hodnoty s nimiˇz provede váˇzen´ y souˇcet (viz obrázek 6). V´ ysledek souˇctu je pouˇzit jako vstup pro aktivaˇcn´ı funkci neuronu, která pˇrevede souˇcet vstupn´ıch hodnot na velikost v´ ystupn´ıho signálu, kter´ y bude neuron vys´ılat do s´ıtˇe. Nejˇcastˇeji se pouˇz´ıvá logistická pˇrechodová funkce z(x) =

1 , 1 + e−x

je ale moˇzné pouˇz´ıt i funkce jiné (mezi dalˇs´ı ˇcasto pouˇz´ıvané patˇr´ı napˇr. skoková nebo lineárn´ı).

2.3

34


w1 x1 x2 x3

w2

Pn

i=0

w i xi

z(x)

w3 w0 x0 = 1

Obrázek 6: Model perceptronu

Pomoc´ı perceptronu je moˇzné nalézt lineárn´ı hranici mezi dvˇema skupinami prvk˚ u v prostoru. Pro nalezen´ı nelineárn´ı hranice, jsou neurony zapojovány do s´ıt´ı. Nejˇcastˇejˇs´ım zapojen´ım neuron˚ u je tˇr´ıvrstvá architektura (viz obrázek 7). S´ıt’ je rozdˇelena na tˇri vrstvy, prvn´ı je vstupn´ı vrstva, posledn´ı v´ ystupn´ı vrstva a mezi nimi se nacház´ı tzv. skrytá vrstva. Pokud se na dvˇe sousedn´ı vrstvy v neuronové s´ıti bude nahl´ıˇzet jako na graf s neurony reprezentuj´ıc´ı uzly a vazby mezi neurony hrany, tak zp˚ usob zapojen´ı neuron˚ u odpov´ıdá u ´plnému bipartitn´ımu grafu, tzn. ˇze kaˇzd´ y neuron z jedné vrstvy je vˇzdy propojen s kaˇzd´ ym neuronem z druhé vrstvy. Neuronovou s´ıt’

vstupn´ı vrstva

skrytá vrstva

v´ ystupn´ı vrstva

Obrázek 7: Schématické zn´ azornˇen´ı tˇr´ıvrstvé neuronové s´ıtˇe

je tˇreba nauˇcit nˇejaké znalosti. V souˇcasné dobˇe existuj´ı r˚ uzné pˇr´ıstupy k procesu uˇcen´ı s´ıtˇe, nejzákladnˇejˇs´ım a také nejˇcastˇeji pouˇz´ıvan´ ym algoritmem je zpˇetné ˇs´ıˇren´ı chyby (angl. backpropagation). Bˇehem uˇcen´ı docház´ı k aktualizaci vah vstup˚ u pro jednotlivé neurony tak, aby se minimalizovala chybová funkce. Pˇri práci s textov´ ymi daty jsou na vstup neuronové s´ıtˇe pˇredávány jednotlivé pˇr´ıznakové vektory. D´ıky dˇr´ıve uveden´ ym charakteristikám textov´ ych dat reprezen-

2.3


35

tovan´ ych pomoc´ı vektor˚ u tak mus´ı vzniknout s´ıt’ s ˇra´dovˇe nˇekolika tis´ıci neuron˚ u na vstupn´ı vrstvˇe. Poˇcet neuron˚ u ve v´ ystupn´ı vrstvˇe se odv´ıj´ı od klasifikaˇcn´ı u ´lohy. Pokud jsou rozliˇsovány pouze dvˇe tˇr´ıdy, postaˇc´ı jedin´ y neruon. V pˇr´ıpadˇe v´ıcetˇr´ıdn´ı klasifikace uˇz mus´ı b´ yt pˇr´ıtomno tolik neuron˚ u, kolik je rozliˇsováno tˇr´ıd. Velikost ˇ ım skryté vrstvy se vol´ı experimentálnˇe, podle kvality dosahovan´ ych v´ ysledk˚ u. C´ vyˇsˇs´ı je celkov´ y poˇcet neuron˚ u, t´ım roste ˇcasová nároˇcnost na proces uˇcen´ı neuronové s´ıtˇe, takˇze pro klasifikaci textov´ ych dat nemus´ı b´ yt pouˇzit´ı s´ıt´ı nejlepˇs´ı moˇznou variantou. Podp˚ urn´ e vektory Metoda podp˚ urn´ ych vektor˚ u (angl. support vector machines, zkrácenˇe SVM) slouˇz´ı pro rozdˇelen´ı bod˚ u ve v´ıcerozmˇerném prostoru do dvou skupin, a to bud’ lineárn´ı nebo nelineárn´ı hranic´ı. Jednotlivé body jsou od sebe oddˇeleny pomoc´ı hyperroviny, která je um´ıstˇena tak, aby hraniˇcn´ı pásmo mezi obˇema skupinami bylo co nejvˇetˇs´ı (viz obrázek 8), ˇc´ımˇz se dosáhne sn´ıˇzen´ı chybovosti pˇri klasifikován´ı náhodnˇe vybraného neznámého prvku (Vapnik, 1995). Problém tedy spoˇc´ıvá v nalezen´ı optimáln´ıho um´ıstˇen´ı roviny, protoˇze zp˚ usob˚ u jej´ıho um´ıstˇen´ı je teoreticky nekoneˇcnˇe mnoho. Pro hledán´ı rozdˇeluj´ıc´ı hyperroviny se pouˇz´ıváj´ı tzv. jádrové (kernel) funkce, kter´ ych existuje v´ıce druh˚ u. Základn´ı funkce umoˇzn ˇuje nalézt pouze linearn´ı hranici, podobnˇe jako napˇr. perceptron. Pouˇzit´ım polynomiáln´ı nebo radiáln´ı bázové funkce je moˇzné nalézt i hranici nelineárn´ı. Ta je nalezena pomoc´ı transformace

Obrázek 8: Uk´ azka hraniˇcn´ıho p´ asma a hyperroviny rozdˇeluj´ıc´ı dvˇe skupiny prvk˚ u. Zdroj: http://phaedrusdeinus.org/svm-lightning/

prvk˚ u do nového prostoru s v´ıce dimenzemi, kter´ y umoˇzn´ı nalezen´ı lineárn´ı hranice. Zpˇetnou transformac´ı se dostane hranice nelineárn´ı. Algoritmus podp˚ urn´ ych vektor˚ u je pro práci s textov´ ymi daty velice vhodn´ y (Joachims, 1998). Vektory reprezentuj´ıc´ı

2.3

36


textová data jsou velice ˇr´ıdké a skládáj´ı se z velkého mnoˇzstv´ı atribut˚ u. SVM má totiˇz tu vlastnost, ˇze schopnost nalezen´ı hranice m˚ uˇze b´ yt nezávislá na dimenzionalitˇe vektorového prostoru. Pokud tedy v datech existuje nˇejaké hraniˇcn´ı pásmo, je moˇzné generalizovat i vysoce dimenzionáln´ı data, coˇz je pˇresnˇe pˇr´ıpad vektor˚ u reprezentuj´ıc´ı textová data. Metoda nejbliˇ zˇs´ıho souseda Metoda nejbliˇzˇs´ıho souseda, potaˇzmo k nejbliˇzˇs´ıch soused˚ u, je zaloˇzena na porovnáván´ı dokument˚ u a v´ ypoˇctu jejich vzájemné podobnosti. M´ısto procesu uˇcen´ı, kter´ y z trénovac´ıch generalizuje nˇejakou znalost, jsou trénovac´ı pˇr´ıklady spolu s informac´ı o pˇr´ısluˇsnosti do nˇekteré ze tˇr´ıd ukládány do databáze a jednotlivé atributy slouˇz´ı jako souˇradnice ve v´ıce rozmˇerném prostoru, ˇc´ımˇz hodnoty tˇechto atribut˚ u urˇcuj´ı polohu dokumentu v daném prostoru (Manning, Raghavan, Sch¨ utze, 2008). Neznám´ y pˇr´ıpad je následnˇe porovnán se vˇsemi záznamy v databázi a jeho tˇr´ıda se urˇc´ı podle k nejbliˇzˇs´ıch (nejpodobnˇejˇs´ıch) pˇr´ıpad˚ u. Poˇcet uloˇzen´ ych dokument˚ u je d˚ uleˇzité peˇclivˇe vyb´ırat, protoˇze pˇri malém poˇctu nemus´ı b´ yt k dispozici dostatek informac´ı pro správné klasifikován´ı neznám´ ych pˇr´ıpad˚ u. Na druhou stranu velké mnoˇzstv´ı bude prodluˇzovat proces hledán´ı nejbliˇzˇs´ıch soused˚ u. V pˇr´ıpadˇe textov´ ych dat jsou dokumenty reprezentovány pˇr´ıznakov´ ymi vektory. Pˇredpokládá se, ˇze dokumenty ze stejné tˇr´ıdy budou do urˇcité m´ıry pouˇz´ıvat shodná slova, a tak budou i ve v´ıcerozmˇerném prostoru bl´ızko sebe. Pro mˇeˇren´ı podobnosti jednotliv´ ych dokument˚ u existuje celá ˇrada metrik. Nejzákladnˇejˇs´ı je Eukleidova vzdálenost. v u n uX δ(dt , dq ) = kdt − dq k = t (wt,i − wq,i )2 i=1

Ta mˇeˇr´ı rozd´ıl mezi dotazovan´ ym dokumentech dq a trénovac´ım dokumentem dt jako druhou odmocninu ze souˇctu ˇctverc˚ u. Pouˇzit´ı této vzdálenosti b´ yvá u vˇetˇsiny problém˚ u ˇreˇsen´ ych pomoc´ı metody nejbliˇzˇs´ıho souseda nejˇcastˇejˇs´ı. Dalˇs´ım pouˇz´ıvan´ ym typem je Manhattanská vzdálenost. δ(dt , dq ) = |dt − dq | =

n X

|wt,i − wq,i |

i=1

Podobnost dokument˚ u je poˇc´ıtána jako souˇcet absolutn´ıch rozd´ılu mezi jednotliv´ ymi pˇr´ıznaky vektor˚ u reprezentuj´ıc´ı dané dokumenty. Posledn´ım zde uveden´ ym zp˚ usobem v´ ypoˇctu podobnosti dokument˚ u je kosinová vzdálenost, kdy hodnota podobnosti dvou dokument˚ u je dána hodnotou kosinu u ´hlu, kter´ y spolu pˇr´ıznakové vektory tˇechto dokument˚ u sv´ıraj´ı. Pn dt,i dq,i dt · dq δ(dt , dq ) = = qP i=1 qP n n kdt kkdq k 2 2 i=1 wt,i i=1 wq,i

2.4

37

Hodnocen´ı u ´spˇeˇsnost´ı

Kosinová vzdálenost je pro hodnocen´ı podobnosti textov´ ych dat velice vhodná, 5 protoˇze nezohledˇ nuje rozsah hodnot jednotliv´ ych pˇr´ıznak˚ u obou vektor˚ u. Pokud dokumenty obsahuj´ı stejná slova, ale v r˚ uzn´ ych poˇctech, m˚ uˇze pˇri pouˇzit´ı Eukleidovské vzdálenosti vyj´ıt jako v´ıce podobn´ y dokument, kter´ y obsahuje menˇs´ı poˇcet stejn´ ych slov, ale v podobném mnoˇzstv´ı. Tuto situaci je moˇzné vidˇet na v´ yˇse uvedeném obrázku 3. Z hlediska kosinové vzdálenosti je vˇsak situace pˇresnˇe opaˇcná, protoˇze urˇcuj´ıc´ı je sv´ıran´ yu ´hel, nikoliv délka vektor˚ u.

2.4

Hodnocen´ı u ´spˇ eˇsnost´ı

Po nauˇcen´ı klasifikátoru je nutné nˇejak´ ym zp˚ usobem zmˇeˇrit kvalitu jeho klasifikaˇcn´ıch schopnost´ı. Proces uˇcen´ı je totiˇz ˇcasto zaloˇzen na minimalizaci chyby, které klasifikátor dosáhne na trénovac´ıch dat. Zde vˇsak hroz´ı problém tzv. pˇreuˇcen´ı (overfitting), kdy v´ ysledn´ y klasifikátor dosahuje vynikaj´ıc´ıch v´ ysledk˚ u na trénovac´ıch datech, nicménˇe na testovac´ıch datech bude jeho chybovost mnohem vyˇsˇs´ı v d˚ usledku nenauˇcen´ı znalosti zobecnitelné i na data nepouˇzitá v procesu uˇcen´ı. Opaˇcn´ ym problémem je naopak nedouˇcen´ı (underfitting), kdy je uˇcen´ı klasifikátoru zastaveno pˇr´ıliˇs brzy a tud´ıˇz z´ıská pouze malé mnoˇzstv´ı znalosti. Zhodnocen´ı kvality klasifikátoru se tedy provád´ı mˇeˇren´ım jeho v´ ykonnosti na testovac´ıch datech. Pro tyto u ´ˇcely existuj´ı r˚ uzné metriky, které umoˇzn ˇuj´ı vyjádˇrit kvalitu dosaˇzen´ ych v´ ysledk˚ u v ˇc´ıselné podobˇe a je tedy moˇzné mezi sebou jednotlivé klasifikátory porovnávat. Pomysln´ ym odrazov´ ym m˚ ustkem pro v´ ypoˇcet nˇekter´ ych metrik je kontingenˇcn´ı tabulka, v pˇr´ıpadˇe binárn´ı klasifikace o rozmˇerech 2 × 2, oznaˇcovaná také jako matice zámˇen. Na jedné z os jsou zaznamenávány dokumenty podle jejich skuteˇcné Tabulka 2: Matice z´ amˇen pro binárn´ı klasifikátor pozitivn´ıch recenz´ı

positive

negative

positive

TP

FP

negative

FN

TN

tˇr´ıdy a na druhé ose tˇr´ıdy, které byly dokument˚ um pˇriˇrazeny klasifikátorem (viz tabulka 2). Celkem tak mohou nastat ˇctyˇri zp˚ usoby klasifikace dokumentu. Pozitivn´ı dokument m˚ uˇze b´ yt oznaˇcen správnˇe jako pozitivn´ı, v takovém pˇr´ıpadˇe jde o True Positive klasifikaci, nebo nesprávnˇe jako negativn´ı, kdy jde o False Negative klasifikaci. Obdobnˇe pro negativn´ı recenze ozanˇcené správnˇe jako negativn´ı True Negative a nesprávnˇe jako pozitivn´ı False Positive. Poˇcet správnˇe klasifikovan´ ych dokument˚ u se tak nacház´ı na diagonále matice. acc = 5

TP + TN TP + FP + FN + TN

ve skuteˇcnosti hodnoty pˇrev´ ad´ı do jednotkového rozsahu, ˇc´ımˇz dojde k eliminaci vlivu r˚ uzn´ ych rozsah˚ u

2.4

38

Hodnocen´ı u ´spˇeˇsnost´ı

Základn´ı metrikou pro ohodnocen´ı celkové u ´spˇeˇsnosti klasifikace je accuracy, coˇz je pod´ıl správnˇe klasifikovan´ ych pˇr´ıpad˚ u ze vˇsech testovan´ ych. Tento zp˚ usob mˇeˇren´ı v´ ysledné pˇresnosti dokáˇze poskytnout základn´ı pˇredstavu o z´ıskaném klasifikátoru, avˇsak v nˇekter´ ych pˇr´ıpadech m˚ uˇze b´ yt tento zp˚ usob zhodnocen´ı velice nepˇresn´ y. Pokud jsou jednotlivé tˇr´ıdy v testovac´ı mnoˇzinˇe zastoupeny rovnomˇernˇe, je hodnocen´ı pomoc´ı acc v poˇra´dku. V pˇr´ıpadˇe znaˇcné pˇrevahy jedné ze tˇr´ıd nad druhou vˇsak m˚ uˇze nastat následuj´ıc´ı situace. Mnoˇzina o t´ısici dokumentech obsahuje pouze deset pozitivn´ıch pˇr´ıpad˚ u, které chceme pomoc´ı klasifikátoru rozeznat (viz tabulka 3. Pokud bude klasifikátor zcela ignorovat existenci pozitivn´ıch pˇr´ıpad˚ u a pro vˇsechny pˇr´ıpady urˇc´ı jako v´ yslednou tˇr´ıdu negativn´ı, bude dosahovat velice vysoké 99% pˇresnosti, pˇr´ıpadnˇe obrácen´ım vn´ımán´ı hodnoty pouze 1% chybovosti. ´ celem vˇsak je správnˇe rozeznat onˇech 10 pozitvn´ıch dokument˚ Uˇ u. Aby bylo moˇzné podobné pˇr´ıpady správnˇe zhodnotit, je nutné pouˇz´ıt i jiné metriky. Tˇemito metriTabulka 3: Matice z´ amˇen klasifikace nevyváˇzené testovac´ı mnoˇziny

positive

negative

positive

0

0

negative

10

990

kami, které dokáˇz´ı kvantifikovat u ´spˇeˇsnost klasifikátoru pˇri klasifikaci pozitivn´ıch pˇr´ıpad˚ u, jsou precision a recall. Precision udává pomˇer správnˇe klasifikovan´ ych pozitivn´ıch pˇr´ıpad˚ u na vˇsech pˇr´ıpadech klasifikovan´ ych jako pozitivn´ı. Recall naproti tomu vyjadˇruje pomˇer správnˇe klasifikovan´ ych pozitivn´ıch pˇr´ıpad˚ u na vˇsech skuteˇcnˇe pozitivn´ıch pˇr´ıpadech. prec =

TP TP + FP

rec =

TP TP + FN

Pouˇzit´ım tˇechto metrik na zhodnocen´ı v´ yˇse popsaného klasifikátoru se tedy vyruˇs´ı vliv drtivé vˇetˇsiny správnˇe negativn´ıch dokument˚ u, protoˇze v jejich v´ ypoˇctu ˇzádn´ ym zp˚ usobem nefiguruj´ı. V´ ysledné hodnoty jsou v obou pˇr´ıpadech nulové, na ˇcemˇz je jasnˇe vidˇet neschopnost klasifikátoru rozeznat pozitivn´ı dokumenty. Zlepˇsen´ı se dosáhne t´ım, ˇze nˇekteré z dokument˚ u budou klasifikovány jako pozitivn´ı. V pˇr´ıpadˇe nutnosti vyjádˇrit pˇresnost klasifikátoru pomoc´ı jediné ˇc´ıselné hodnoty je moˇzné pouˇz´ıt metriku F-measure, která kombinuje dohromady precision a recall, a to jako jejich harmonick´ y pr˚ umˇer. 2 · prec · rec F = prec + rec Pokud se klasifikuje do v´ıce neˇz dvou tˇr´ıd, je vhodné podobn´ ym zp˚ usobem vyjádˇrit kvalitu z´ıskané znalosti pomoc´ı jedné hodnoty (Manning, Raghavan, Sch¨ utze, 2008). Toho se dosahuje tzv. makropr˚ umˇerován´ım nebo mikropr˚ umˇerován´ım. V pˇr´ıpadˇe makropr˚ umˇerován´ı jsou pro kaˇzdou tˇr´ıdu zvláˇst’ spoˇc´ıtány jednotlivé metriky, které

2.5

Paraleln´ı zpracován´ı

39

jsou následnˇe zpr˚ umˇerovány. U mikropr˚ umˇerován´ı jsou matice zámˇen pro jednotlivé tˇr´ıdy seˇcteny do jedné spoleˇcné, ze které jsou následnˇe spoˇc´ıtány hodnot´ıc´ı metriky. Pokud je nˇekterá ze tˇr´ıd zastoupena ve vˇetˇs´ım mnoˇzstv´ı, bude pˇrenost dosahovaná nad touto tˇr´ıdou pˇri mikropr˚ umˇerován´ı pˇrevaˇzovat nad pˇresnostmi klasifikace ostatn´ıch, ménˇe zastoupen´ ych tˇr´ıd. V takovém pˇr´ıpadˇe je vhodnˇejˇs´ı pouˇz´ıt variantu makropr˚ umˇerován´ı, protoˇze do koneˇcného v´ ysledku pˇrisp´ıvaj´ı u ´spˇeˇsnosti klasifikace jednotliv´ ych tˇr´ıd stejn´ ym d´ılem.

2.5

Paraleln´ı zpracov´ an´ı

Paraleln´ı zpracován´ı v sobˇe skr´ yvá moˇznost sn´ıˇzit celkovou ˇcasovou nároˇcnost klasifikace na základˇe rozsáhl´ ych kolekc´ı textov´ ych dat. Rozdelˇen´ım celého problému na nˇekolik menˇs´ıch by mˇelo doj´ıt k rapidn´ımu sn´ıˇzen´ı ˇcasu, potˇrebného pro natrénován´ı klasifikátoru, protoˇze v´ ypoˇcetn´ı nároˇcnost zpravidla neroste u tˇechto typu problém˚ u lineárnˇe. Paralen´ı pˇr´ıstup jiˇz byl pro tyto u ´ˇcely pouˇzit, napˇr. pro detekci webov´ ych u ´tok˚ u byl pouˇzit klasifikátor zaloˇzen´ y na podobnosti dokument˚ u, pˇriˇcemˇz klasick´ y ˇ sekvenˇcn´ı pˇr´ıstup nebyl schopen zpracovat pˇr´ıchoz´ı data v reálném ˇcase. Reˇsen´ım problému bylo zparalelizován´ı tohoto procesu (Ulmer et al., 2011). Dalˇs´ım moˇzn´ ym pˇr´ıstupem bylo vytvoˇren´ı skupiny klasifikátor˚ u na základˇe d´ılˇc´ıch dimenz´ı rozsáhlé kolekce textov´ ych dat (Lertnattee, Theeramunkong, 2004). Na PEF byl realizován v´ yzkum zamˇeˇren´ y na zp˚ usob rozdˇelen´ı datové mnoˇziny na jednotlivé podmnoˇziny tak, aby byla co moˇzná nejv´ıce zachována kvalita v´ ysledné komise klasifikátor˚ u ˇ v˚ uˇci klasifikátoru nauˇceném na celém datovém souboru (Ziˇzka, Daˇrena, 2012). Tento konkrétn´ı v´ yzkum byl jedn´ım ze základn´ıch podklad˚ u pro vypracován´ı této práce.

3

´ ı METODIKA ZPRACOVAN´

3

40

Metodika zpracov´ an´ı

V´ ystupem diplomové práce je zrealizován´ı nˇekolika klasifikaˇcn´ıch experiment˚ u nad vˇetˇs´ı kolekc´ı textov´ ych dat, které budou slouˇzit k ovˇeˇren´ı hypotézy o moˇznosti aplikován´ı paralelizovaného pˇr´ıstupu pˇri uˇcen´ı klasifikátor˚ u nad rozsáhl´ ymi kolekcemi textov´ ych dokument˚ u. Pro z´ıskán´ı potˇrebn´ ych v´ ysledk˚ u bude nutné: • sebrat dostateˇcné mnoˇzstv´ı ohodnocen´ ych textov´ ych dat, • zvolit testované algoritmy strojového uˇcen´ı, • vybrat a rozdˇelit mnoˇzinu dokument˚ u pro paraleln´ı zpracován´ı, • pˇredzpracovat vhodn´ ym zp˚ usobem textové dokumenty, • nauˇcit a otestovat klasifikátor na celé vybrané mnoˇzinˇe a na rozdˇelen´ ych podmnoˇzinách.

3.1

Data

Základem pro uskuteˇcnˇen´ı potˇrebn´ ych experiment˚ u je dostateˇcné mnoˇzstv´ı textov´ ych dokument˚ u, vyjadˇruj´ıc´ı urˇcit´ y postoj autora textu nebo zab´ yvaj´ıc´ı se nˇejak´ ym tématem. Takov´ ych dat je na internetu dostupn´ ych pomˇernˇe velké mnoˇzstv´ı, ale z´ıskán´ı jejich dostateˇcnˇe velkého poˇctu nen´ı zcela triviáln´ı. Data totiˇz mus´ı b´ yt vhodnˇe ohodnocena, aby mohla b´ yt pouˇzita k vytváˇren´ı jednotliv´ ych klasifikátor˚ u pomoc´ı tzv. uˇcen´ı s uˇcitelem. Pro kaˇzd´ y dokument je nutné znát jeho pˇr´ısluˇsnost do klasifikaˇcn´ı tˇr´ıdy, a to i pro testovac´ı data, jelikoˇz v´ ysledné klasifikátory je tˇreba otestovat na datech nepouˇzit´ ych v procesu uˇcen´ı a porovnat tˇr´ıdu urˇcenou klasifikátorem se skuteˇcnou tˇr´ıdou dokumentu. Zp˚ usoby vytvoˇren´ı potˇrebné kolekce dokument˚ u jsou celkem dva. Prvn´ı je vyuˇzit´ı nˇekteré z jiˇz existuj´ıc´ıch kolekc´ı textov´ ych dokument˚ u a druh´ y je sestaven´ı vlastn´ı nové kolekce. 3.1.1

Standardn´ı zdroje textov´ ych kolekc´ı

V celé ˇradˇe vˇedeck´ ych prac´ıch zab´ yvaj´ıc´ıch se problematikou dolován´ı z textov´ ych dat, konkrétnˇe kategorizac´ı dokument˚ u, b´ yvaj´ı velice ˇcasto pouˇz´ıvány obecnˇe známé (angl. well-known) a zároveˇ n volnˇe dostupné kolekce ohodnocen´ ych dokument˚ u (Cardoso-Cachopo, 2007). 20 Newsgroups Tato kolekce dokument˚ u obsahuje zhruba dvacet tis´ıc pˇr´ıspˇevk˚ u, které jsou témˇeˇr rovnomnˇernˇe rozdˇeleny do dvaceti tˇr´ıd pˇredstavuj´ıc´ı r˚ uzná témata, kter´ ych se pˇr´ıspˇevky t´ ykaj´ı (baseball, hockey, electronics, atheism), pˇriˇcemˇz pˇr´ısluˇsnost dokumentu do tˇr´ıdy je exkluzivn´ı (patˇr´ı vˇzdy pouze do jedné tˇr´ıdy). Kromˇe samotného

3.1

Data

41

textu obsahuj´ı dokumenty ˇradu meta informac´ı, jako adresu a jméno odes´ılatele ˇci pˇr´ıjemce, název vlákna nebo pˇredmˇet zprávy (Rennie, 2008). Reuters-21578 Dalˇs´ı ˇcasto pouˇz´ıvaná kolekce Reuters-21578 obsahuje celkem 21578 dokument˚ u, z nichˇz zhruba polovina je ohodnocena alespoˇ n jednou tˇr´ıdou. Z celé kolekce je moˇzné pouˇz´ıt dvˇe menˇs´ı kolekce R10 a R90 obsahuj´ıc´ı dané dokumenty rozdˇelené do odpovádaj´ıc´ıho poˇctu tˇr´ıd (napˇr. grain, livestock, coffe, cpu). Dokumenty jsou uloˇzené v SGML formátu, takˇze obsahuj´ı nav´ıc strukturn´ı znaˇcky (Lewis, 2004). WebKB Kolekce WebKB obsahuje internetové stránky sebrané z r˚ uzn´ ych univerzit. Celkem je k dispozici pˇres 8 tis´ıc stránek, které byly ruˇcnˇe klasifikovány do následuj´ıc´ıch kategori´ı: student, faculty, staff, department, course, project, a other. Stránky jsou uloˇzeny pˇr´ımo v HTML formátu, takˇze podobnˇe jako u Reuters kolekce obsahuj´ı strukturn´ı znaˇcky. Nav´ıc je na zaˇca´tku kaˇzdého dokumentu uvedena MIME hlaviˇcka. Nˇekteré z uloˇzen´ ych stránek tak mohou obsahovat pouze informace pro prohl´ıˇzeˇc o pˇresmˇerován´ı na jinou adresu (Cardoso-Cachopo, 2007). V´ yhoda pouˇzit´ı nˇekteré z uveden´ ych kolekc´ı spoˇc´ıvá ve snadné srovnatelnosti z´ıskan´ ych v´ ysledk˚ u s ostatn´ımi v´ yzkumy, které tyto datové kolekce pˇri sv´ ych experimentech pouˇzily. Nˇekteré jsou nav´ıc dostupné i v urˇcitém prezpracovaném stavu, kupˇr´ıkladu jsou jiˇz odstranˇena stop slova nebo byl aplikován stemming, coˇz m˚ uˇze usnadnit proces pˇr´ıpravy dat. Pro potˇreby této práce jsou vˇsak tyto jinak velice vhodné kolekce nepouˇzitelné, a to kv˚ uli pˇr´ıliˇs malému mnoˇzstv´ı dokument˚ u. Pro vytvoˇren´ı dostateˇcnˇe rozsáhlé kolekce dat bude tedy nutné zvolit jin´ y zp˚ usob. 3.1.2

Vytvoˇren´ı nov´ e kolekce

Pokud z nˇejakého d˚ uvodu nen´ı moˇzné pouˇz´ıt pro experimenty standardnˇe pouˇz´ıvané kolekce dokument˚ u, mus´ı b´ yt pouˇzita nˇekterá prozat´ım obecnˇe nerozˇs´ıˇrená kolekce nebo vytvoˇrena zcela nová. Zdrojem textov´ ych dat s ohodnocen´ım mohou b´ yt nejr˚ uznˇejˇs´ı internetové stránky, na kter´ ych mohou návˇstˇevn´ıci psát do diskuz´ı, komentáˇr˚ u ˇci hodnocen´ı produkt˚ u a zároveˇ n pˇridat jeˇstˇe jin´ y zp˚ usob urˇcen´ı v´ yznamu napsaného textu, napˇr. plusové a minusové body nebo poˇcty hvˇezdiˇcek. Celosvˇetovˇe známé internetové stránky jako internetová filmová databáze IMBb nebo tˇreba elektronick´ y obchod Amazon maj´ı v souˇcasné dobˇe obrovskou základnu uˇzivatel˚ u, kteˇr´ı p´ıˇs´ı recenze na filmy ˇci produkty a poskytuj´ı tak nemalé mnoˇztsv´ı textov´ ych dat ohodnocen´ ych poˇctem hvˇezdiˇcek, pˇriˇrazen´ım k produktu ˇci filmu urˇcité kategorie, apod. Mohou tak slouˇzit jako dobr´ y zdroj pro z´ıskán´ı dostateˇcného mnoˇzstv´ı ohodnocen´ ych dat psan´ ych v pˇrirozeném jazyce. Vˇetˇsinou vˇsak nen´ı ˇcasovˇe nebo i finanˇcnˇe moˇzné ruˇcn´ım zp˚ usobem procházet podobné stránky a ukládat jednotlivé recenze do nové kolekce, která by mˇela obsaho-

3.2

42

Algoritmy strojového uˇcen´ı

vat ˇra´dovˇe nˇekolik des´ıtek, ne-li stovek tis´ıc dokument˚ u. Proces je moˇzné zautomatizovat vytvoˇren´ım programu, kter´ y bude na základˇe url stránky postupnˇe stahovat, extrahovat z nich potˇrebné u ´daje a ukládat je ve vhodném formátu pro následné pouˇzit´ı pˇri experimentech. Tabulka 4: Charakteristika dat hotelov´ ych recenz´ı

Nejkratˇs´ı recenze

1 slovo

Nejdelˇs´ı recenze

400 slov

Pr˚ umˇerná délka recenze

24 slov

V této diplomové práci by byl normálnˇe zvolen druh´ y zp˚ usob, protoˇze standardn´ı textové kolekce bohuˇzel neobsahuj´ı postaˇcuj´ıc´ı poˇcet dokument˚ u, kter´ y je pro realizaci zam´ yˇslen´ ych experiment˚ u bezpodm´ıneˇcnˇe nutn´ y. Vedouc´ım práce vˇsak byla ˇ zka, Daˇrena, 2010), která dána k dispozici jiˇz zkompletovaná kolekce dokument˚ u (Ziˇ má poˇzadované vlastnosti, tedy ohodnocen´ı textov´ ych dat a dostateˇcné mnoˇzstv´ı dokument˚ u. Jedná se o recenze hotel˚ u psan´ ych v anglickém jazyce a dle jejich obsahu jsou rozdˇeleny do dvou tˇr´ıd, pozitivn´ı a negativn´ı recenze, pˇriˇcemˇz jejich pˇr´ısluˇsnost do dan´ ych tˇr´ıd urˇcovali pˇr´ımo autoˇri recenz´ı. Nejzákladnˇejˇs´ı charektristiky tˇechto dat jsou uvedeny v tabulce 4.

3.2

Algoritmy strojov´ eho uˇ cen´ı

Na konci pˇredchoz´ı kapitoly byly krátce pˇredstaveny algoritmy, které se pro klasifikaci textov´ ych dat pouˇz´ıvaj´ı nejˇcastˇeji. Experimenty budou provedeny pouze s nˇekolika vybran´ ymi metodami, a to: • neuronové s´ıtˇe, • podp˚ urné vektory, • nejbliˇzˇs´ı soused. D˚ uvodem jejich v´ ybˇeru je pˇredevˇs´ım ˇcasová nároˇcnost, kterou by mˇelo b´ yt moˇzné d´ıky paraleln´ımu pˇr´ıstupu v´ yraznˇe sn´ıˇzit. D˚ uleˇzit´ ym faktorem vˇsak je, jak´ y bude vliv na celkovou u ´spˇeˇsnost z´ıskan´ ych klasifikátor˚ u a kter´ y ze zp˚ usob˚ u rozdˇelen´ı celkové mnoˇziny dat na podmnoˇziny bude poskytovat nejlepˇs´ı v´ ysledky.

3.3

V´ ybˇ er mnoˇ ziny dat a jej´ı rozdˇ elˇ en´ı

Základem pro srovnán´ı vlivu paralelizace dolován´ı z textov´ ych dat je rozsáhlá mnoˇzina dokument˚ u, na kterou budou aplikovány algoritmy strojového uˇcen´ı, a to jednak na celou mnoˇzinu a poté na jednotlivé podmnoˇziny, na které bude vybraná mnoˇzina rozdˇelena.

3.4

Technologie pro implementaci

43

V´ ysledné podmnoˇziny by mˇely zachovat pomˇer, v jakém se nacház´ı zastoupen´ı jednotliv´ ych tˇr´ıd v celé mnoˇzinˇe. V ideáln´ım pˇr´ıpadˇe by uˇz pˇri v´ ybˇeru hlavn´ı mnoˇziny mˇelo b´ yt zajiˇstˇeno rovnocenné zastoupen´ı vˇsech tˇr´ıd, aby byly klasifikaˇcn´ı algorimty natrénovány na stejném mnoˇzstv´ı pozitivn´ıch i negativn´ıch pˇr´ıpad˚ u a dokázaly se tak nauˇcit co nejlépe mezi obˇema pˇr´ıpady rozliˇsovat. To vˇsak v praxi ˇcasto nemus´ı b´ yt moˇzné a mˇelo by tedy pˇred rozdˇelen´ım nejdˇr´ıve doj´ıt ke zjiˇstˇen´ı pomˇeru, v jakém jsou tˇr´ıdy zastoupeny a rozdˇelen´ı na podmnoˇziny provést obdobn´ ym zp˚ usobem. Testován´ı z´ıskan´ ych klasifikátor˚ u mus´ı následnˇe prob´ıhat na shodné mnoˇzinˇe testovac´ıch dokument˚ u, která bude z hlediska jej´ı velikosti vytváˇrena v urˇcitém pˇredem daném pomˇeru v˚ uˇci hlavn´ı trénovac´ı mnoˇzinˇe.

3.4


Cel´ y proces pr˚ ubˇehu experiment˚ u je tˇreba rozdˇelit na dvˇe hlavn´ı ˇcásti: • pˇr´ıprava dat, • uˇcen´ı a testován´ı klasifikátoru. Vzhledem k obrovskému rozsahu zpracovávan´ ych dat nen´ı moˇzné ruˇcnˇe provádˇet jejich v´ ybˇer, ˇci dokonce pˇrevod dokument˚ u do vektorové podoby a pˇrepoˇc´ıtán´ı vah jednotliv´ ych pˇr´ıznak˚ u vektoru. Pro tyto u ´ˇcely bude nutné vytvoˇrit jednoduchou aplikaci, která se postará o v´ ybˇer dat, jejich následné rozdˇelen´ı na podmnoˇziny a pˇreveden´ı text˚ u do vektorové reprezentace. Pouˇzit´ y programovac´ı jazyk by tedy mˇel umoˇzn ˇovat pokud moˇzno co nejjednoduˇsˇs´ı práci s textov´ ymi daty a soubory, a to pokud moˇzno bez omezen´ı na velikost zpracovávan´ ych dat. Pro tyto u ´ˇcely je velice vhodn´ y programovac´ı jazyk Perl, kter´ y vznikl právˇe jako náhrada prostˇredk˚ u pro zpracován´ı textu, které v dobˇe jeho vzniku jiˇz nebyly pro tyto u ´ˇcely dostaˇcuj´ıc´ı (Daˇrena, 2005). Pˇredzpracován´ı textov´ ych dokument˚ u bude tedy realizováno pomoc´ı nˇekolika skript˚ u. Nauˇcen´ı klasifikátor˚ u a otestován´ı jejich znalosti vyˇzaduje obdobn´ y pˇr´ıstup. Je tˇreba vytvoˇrir aplikaci, která zpracuje pˇredpˇripravená data pomoc´ı zvoleného uˇc´ıc´ıho algoritmu a otestuje v´ ysledn´ y klasifikátor. Veˇsker´ y pr˚ ubˇeh bˇehu programu je nutné zaznámenávat do souboru (pro pozdˇejˇs´ı kontrolu dosaˇzen´ ych v´ ysledk˚ u). Stejnˇe tak testovac´ı ˇca´st by mˇela pˇredpovˇedi klasifikátoru zaznamenat do souboru, aby bylo moˇzné po proveden´ı vˇsech potˇrebn´ ych experiment˚ u v´ ysledky porovnat a vyhodnotit. Poˇzadavky na pouˇzit´ y programovac´ı jazyk tedy budou ponˇekud odliˇsné: • existence knihoven pro algoritmy strojového uˇcen´ı – i kdyˇz je moˇzné provést vlastn´ı implementaci vybran´ ych algoritm˚ u, nen´ı podobn´ y postup nejlepˇs´ım moˇzn´ ym ˇreˇsen´ım, protoˇze odladˇen´ı korektn´ıho fungován´ı by bylo ˇcasovˇe nároˇcné a nˇekteré moˇzné chyby, které by mohly m´ıt negativn´ı vliv na z´ıskané v´ ysledky, by se nemuselo podaˇrit ani odhalit, je tedy nutné vybrat takov´ y programovac´ı jazyk, pro kter´ y jsou jiˇz tyto algoritmy implementovány v podobˇe rozˇs´ıˇren´ ych a uˇzivateli ovˇeˇren´ ych knihoven,

3.4


44

• objektovˇe orientovan´ y pˇr´ıstup programován´ı, • rychlost – v´ ystupem vybraného jazyk by mˇela b´ yt aplikace bˇeˇz´ıc´ı co nejrychleji, ideálnˇe by tedy mˇelo j´ıt o jazyk kompilovan´ y, protoˇze bˇehem procesu uˇcen´ı klasifikátor˚ u docház´ı d´ıky rozsáhlosti zpracovávaného souboru dat (oˇcekává se zhruba sto tis´ıc dokument˚ u reprezetovan´ ych vektory s v´ıce jak deseti tis´ıci atributy) k znaˇcnému prodluˇzován´ı doby uˇcen´ı a také i doby potˇrebné pro odladˇen´ı celé aplikace a z´ıskán´ı koneˇcn´ ych v´ ysledk˚ u, • moˇznost práce s pamˇet´ı – stejnˇe jako má velikost zpracovávan´ ych dat vliv na dobu uˇcen´ı, roste i nároˇcnost na pamˇet’, takˇze vybran´ y jazyk by mˇel v pˇr´ıpadˇe nutnosti umoˇzn ˇovat správu pouˇz´ıvané pamˇeti, • typovˇe striktn´ı – neoˇcekávané chyby, které by mohly také negativnˇe ovlivnit z´ıskané v´ ysledky, je eliminovat d´ıky striktn´ı typové kontrole, • spustitelnost na libovolném operaˇcn´ım systému, • autorova znalost pouˇz´ıván´ı jazyka. Dle takto stanoven´ ych poˇzadavk˚ u byl pro implementaci zvolen programovac´ı jazyk C++. Ten je velice rozˇs´ıˇren´ y a umoˇzn ˇuje tak v´ ybˇer z ˇrady jiˇz pouˇz´ıvan´ ych a ovˇeˇren´ ych knihoven, které je moˇzné pouˇz´ıt pro implementaci klasifikátor˚ u. 3.4.1

V´ ybˇ er knihoven

Pokud by mˇela b´ yt provedena implementace vˇsech potˇrebn´ ych programov´ ych prostˇredk˚ u, které jsou nutné pro realizaci experiment˚ u, bylo by nutné vˇenovat velké mnoˇzstv´ı ˇcasu na odladˇen´ı r˚ uzn´ ych ˇca´st´ı aplikace a hledán´ı moˇzn´ ych chyb, které by mohly ovlivnit z´ıskané v´ ysledky. Z tohto d˚ uvodu budou pro nˇekteré kritické ˇca´sti aplikace pouˇzity knihovny, jejichˇz pouˇzit´ı by mˇelo zaruˇcit • oddladˇené a ovˇeˇrené ˇcásti zdrojového kódu, • implementaci od odborn´ık˚ u z dané oblasti, • ˇcasovou u ´sporu nutnou pro implementaci, • moˇznost ˇreˇsen´ı problém˚ u v rámci komunity pouˇz´ıvaj´ıc´ı knihovnu, • zpracovanou dokumentaci. Pouˇzit´ı knihoven pˇrináˇs´ı ˇradu v´ yhod a jedin´ ym problémem m˚ uˇze b´ yt absence urˇcité poˇzadované funkcionality, kterou je tˇreba vlastn´ımi silami doprogramovat. Pˇr´ıprava dat V prvn´ı ˇca´sti, urˇcené pro pˇr´ıpravu a pˇredzpracován´ı textov´ ych dokument˚ u, bude moˇzné vyuˇz´ıt programov´ y modul TextMining, jehoˇz autorem je vedouc´ı této diploˇ zka, Daˇrena, 2010). Tento modul poskytuje jednoduché rozhran´ı pro mové práce (Ziˇ

3.4


45

pˇrevod textov´ ych dokument˚ u do vektorové reprezentace. Pˇri transformaci textov´ ych dat je moˇzné volit z celé ˇrady váˇzen´ı hodnot ve v´ ysledn´ ych pˇr´ıznakov´ ych vektorech, a to jak pro lokáln´ı váhy, tak i pro globáln´ı váhy a normalizaci hodnot. Je moˇzné odfiltrovat i slova s n´ızk´ ym nebo naopak pˇr´ıliˇs vysok´ ym poˇctem v´ yskyt˚ u, opˇet na v´ıce u ´rovn´ıch – jednak v rámci jednotliv´ ych dokument˚ u, v rámci celého datového souboru, nebo podle poˇctu dokument˚ u, ve kter´ ych se jednotlivá slova vyskytuj´ı. D˚ uleˇzitou souˇca´st´ı je vytváˇren´ı slovn´ık˚ u nad zpracovávanou mnoˇzinou dokument˚ u, které je pak moˇzné pˇri pˇr´ıpravˇe jiné mnoˇziny textov´ ych dat naˇc´ıst, ˇc´ımˇz dojde ke sjednocen´ı reprezentace tˇechto dvou mnoˇzin pomoc´ı vektor˚ u se stejn´ ymi atributy. Jedin´ y poˇzadavek je kladen´ y na formát souboru vstupn´ıch dat, které mus´ı m´ıt následuj´ıc´ı tvar. CLASS \t DOCUMENT -------------------------------------------------------------NEGATIVE This is very dissapointing movie, don’t waste your time with it. POSITIVE Absolutely brilliant piece, perfect cast, gorgeous visuals and very catching story. Na kaˇzdém ˇra´dku vstupn´ıho souboru se nacház´ı dvojice hodnot tˇr´ıda a samotn´ y dokument vzájemnˇe od sebe oddˇelené znakem tabulátoru. Transformovaná data je moˇzné ukládát do nˇekolika r˚ uzn´ ych formát˚ u, napˇr. pro algoritmus C5 generuj´ıc´ı rozhodovac´ı strom, aplikaci Weka pro dolován´ı z dat vyvinuté na univerzitˇe Waikato, nebo programov´ y bal´ık pro shlukovac´ı u ´lohy CLUTO. Vyuˇzit´ı tohoto modulu je moˇzné dvˇema zp˚ usoby. Jednak jej lze zahrnout do vlastn´ıch skript˚ u a vyuˇz´ıt poskytnuté rozhran´ı pro nastaven´ı parametr˚ u pˇrevodn´ıho algoritmu a spuˇstˇen´ı transformace dat. Druh´ ym zp˚ usobem je pouˇzit´ı i grafické nadstavby nad t´ımto modulem, implementované pomoc´ı modulu pro grafické uˇzivatelské rozhran´ı Perl/Tk. Tato aplikace umoˇzn ˇuje uˇzivatelsky pˇr´ıvˇetivé zadáván´ı parametr˚ u a také validaci zadan´ ych hodnot (Novák, Daˇrena, 2012). Realizace experiment˚ u Druhou ˇcást implementace bude tvoˇrit aplikace pro realizaci samotn´ ych experiment˚ u. Zde budou kritickou ˇca´st tvoˇrit jednotlivé algoritmy strojového uˇcen´ı, které mus´ı b´ yt pro z´ıskán´ı nezávadn´ ych v´ ysledk˚ u ˇrádnˇe odladˇeny a zbaveny vˇsech chyb, které by mohly zp˚ usobit zkreslen´ı v´ ysledn´ ych hodnot. Je tedy pˇrirozené sáhnout po jiˇz existuj´ıc´ıch knihovnách, které poskytnou kvalitn´ı a ovˇeˇrenou implementaci tˇechto algoritm˚ u. Prvn´ım pouˇzit´ ym algoritmem jsou umˇelé neuronové s´ıtˇe. Na internetové stránce sourceforge.net slouˇz´ıc´ı jako u ´loˇzistˇe pro open source projekty je dle jednoduchého vyhledávac´ıho dotazu dostupn´ ych zhruba dvacet projekt˚ u, které implementuj´ı neuronové s´ıtˇe pro programovac´ı jazyk C++. Na v´ ybˇer je tedy z pomˇernˇe velkého mnoˇzstv´ı a popis vˇsech tˇechto moˇznost´ı by byl zbyteˇcnˇe dlouh´ y. Autor práce má jiˇz

3.4


46

zkuˇsenosti s pouˇz´ıván´ım knihovny Fast Artificial Neural Network (zkrácenˇe FANN), která je implementována v programovac´ım jazyku C. Dostupná je ale celá ˇrada bindings pro ostatn´ı programovac´ı jazyky, vˇcetnˇe pouˇz´ıvaného C++. Dle domovské stránky6 projektu poskytuje tato knihovna celou ˇradu funkc´ı: • v´ıcevrstvá architektura s´ıtˇe, • ˇctyˇri r˚ uzné uˇc´ıc´ı algoritmy, • plné ˇci ˇca´steˇcné propojen´ı neuron˚ u, • podpora dynamicky se upravuj´ıc´ı topologie, • snadná pouˇzitelnost, • vysoká rychlost (´ udajnˇe aˇz 150 násobek rychlosti jin´ ych knihoven), • rychlé ukládán´ı a naˇc´ıtán´ı natrénovan´ ych s´ıt´ı, • nadstavby s GUI, • jiˇz zm´ınˇené bindings do velkého mnoˇzstv´ı programovac´ıch jazyk˚ u. Tato knihovna tedy slibuje opravdu kvalitn´ı implementaci s r˚ uzn´ ymi moˇznostmi nastaven´ı topologie neuronové s´ıtˇe, zp˚ usobu propojen´ı neuron˚ u i r˚ uzn´ ych uˇc´ıc´ıch algoritm˚ u. Pokud by tedy mˇela v´ ysledná aplikace slouˇzit jako podklad pro dalˇs´ı v´ yzkum a experimenty, m˚ uˇze b´ yt pouˇzita ˇrada tˇechto rozliˇcn´ ych moˇznost´ı poskytované knihovnou FANN. Nejvˇetˇs´ım kladem je vˇsak slibovaná rychlost knihovny. Nejvˇetˇs´ı nev´ yhodou pˇri pouˇz´ıván´ı neuronov´ ych s´ıt´ı pˇri zpracován´ı textov´ ych dat je totiˇz právˇe velká ˇcasová nároˇcnost. Jak´ ykoliv zp˚ usob urychlen´ı celého procesu je tedy v´ıtan´ y a pro implementaci klasifikátoru neuronové s´ıtˇe bude pouˇzita knihovna FANN. Dále bude testován vliv paralelizace zpracován´ı dat na algoritmus podp˚ urn´ ych 7 vektor˚ u. Na internetovém portálu support vector machines je k dispozici velice rozsáhl´ y seznam knihoven a softwaru implementuj´ıc´ı podp˚ urné vektory, a to nejen pro programovac´ı jazyk C a C++. Uveden je zde tˇreba jiˇz dˇr´ıvˇe zm´ınˇen´ y bal´ık algoritm˚ u pro dolovan´ı z dat Weka, Java applety, toolbox pro Matlab, jazyk R ˇci Python. Nechyb´ı zde ani pomˇernˇe známá knihovna libsvm8 opˇet poskytuj´ıc´ı rozhran´ı do celé ˇrady jin´ ych programovac´ıch jazyk˚ u. Na domovské stránce knihovny je také uveden v´ yˇcet nˇekter´ ych v´ yznaˇcn´ ych vlastnost´ı implementace: • efektivn´ı klasfikace do v´ıce tˇr´ıd, • krosvalidace, • r˚ uzné jádrové (kernel) funkce, 6

http://leenissen.dk/fann/wp/ http://www.support-vector-machines.org/ 8 http://www.csie.ntu.edu.tw/~cjlin/libsvm/ 7

3.4


47

• demonstrativn´ı GUI aplikace, • automatické urˇcen´ı parametr˚ u. Na prvn´ım m´ıstˇe v seznamu SVM softwaru je vˇsak uvedena knihovna SVM light9 jej´ıˇz autorem Thorsten Joachims, kter´ y se zasadil rozˇs´ıˇren´ı pouˇzitelnosti podp˚ urn´ ych vektor˚ u pro klasifikiaci textov´ ych dat. Tato knihovna se ˇrad´ı mezi nejpouˇz´ıvanˇejˇs´ı. Poskytuje vysoce optimalizovanou implementaci, která umoˇzn ˇuje jej´ı pouˇzit´ı pro velice rozsáhlé datové soubory. K dispozici jsou také r˚ uzné jádrové funkce: • lineárn´ı, • polynomiáln´ı, • radiálnˇe bázová, • sigmoid tanh, • uˇzivatelem definovaná funkce. Vzhledem k tomu, ˇze Joachims pouˇz´ıval tuto knihovnu pro ˇradu vˇedeck´ ych ˇclánk˚ u zab´ yvaj´ıc´ıch se klasifikac´ı textov´ ych dat, bude pro implementaci tohoto algoritmu pouˇzita právˇe knihovna SVM light, která byla po konzultaci doporuˇcena i vedouc´ım práce. Posledn´ım algoritmem strojového uˇcen´ı je metoda nejbliˇzˇs´ıho souseda. Problém pˇri klasifikaci textov´ ych dat pomoc´ı tohoto pˇr´ıstupu spoˇc´ıvá obdobnˇe jako u neuronov´ ych s´ıt´ı ve velké ˇcasové nároˇcnosti, která roste s mnoˇzstv´ım zpracovávan´ ych dokument˚ u a souˇcasnˇe s velikost´ı slovn´ıku. Implementace samotného algoritmu nemus´ı b´ yt nikterak sloˇzitá, protoˇze docház´ı pouze k postupnému srovnáván´ı dotazovaného vektoru se vˇsemi vektory uloˇzen´ ymi v databázi. Tento základn´ı pˇr´ıstup vˇsak trp´ı zm´ınˇenou ˇcasovou nároˇcnost´ı. Proto existuj´ı modifikace, které umoˇzn´ı zmenˇsen´ı poˇctu záznam˚ u, se kter´ ymi je dotazovan´ y vektor porovnáván. Pro v´ ybˇer tˇechto vektor˚ u jsou pouˇzity K-D stromy, které rozdˇel´ı prostor na tzv. hyperkvádry a klasifikovan´ y vektor je porovnáván pouze s pˇr´ıpady ze stejného hyperkvádru. Knihovna ANN: A Library for Approximate Nearest Neighbor Searching10 implementuje tento typ nejbliˇzˇs´ıch soused˚ u. Bude pouˇzita pouze jako pˇredloha pro vlastn´ı implementaci tohoto typu klasifikátoru.

9 10

http://svmlight.joachims.org/ http://www.cs.umd.edu/~mount/ANN/

4

´ VYSLEDKY

4

48

V´ ysledky

V´ ysledkem této diplomové práce by mˇely b´ yt závˇery odvozené z v´ ysledk˚ u z´ıskan´ ych proveden´ım nˇekolika experiment˚ u, které jsou zamˇeˇreny na srovnán´ı dolován´ı znalost´ı z rozsáhlé textové kolekce a nˇekolika menˇs´ıch d´ılˇc´ıch kolekc´ı vzniknuvˇs´ıch rozdˇelen´ım p˚ uvodn´ı rozsáhlé kolekce dokument˚ u. Experimenty budou realizovány skrze aplikaci, která je pro tyto u ´ˇcely implementována, stejnˇe jako skripty vytvoˇrené pro usnadnˇen´ı pˇr´ıpravy textov´ ych dat. V´ ystupy práce jsou tedy: • v´ ysledky experiment˚ u, • skripty pro pˇr´ıpravu dat, • aplikace pro realizaci experiment˚ u.

4.1

N´ avrh experiment˚ u

C´ılem experiment˚ u je provˇeˇrit vliv paralelizovaného pˇr´ıstupu pˇri dolován´ı znalost´ı z rozsáhl´ ych kolekc´ı textov´ ych dat. Pˇredvˇs´ım pak jak´ y bude m´ıt vliv na v´ yslednou klasifikaci r˚ uzné rozdˇelen´ı trénovac´ıch dokument˚ u na menˇs´ı mnoˇziny a jaké budou rozd´ıly mezi jednotliv´ ymi algoritmy strojového uˇcen´ı, pouˇzité pro tvorbu klasifikátoru. D˚ uleˇzit´ y by také mohl b´ yt vliv r˚ uzn´ ych nastaven´ı pro jednotlivé typy klasifikátor˚ u, napˇr. jiná architektura neuronové s´ıtˇe nebo jin´ y typ jádrové funkce u podp˚ urn´ ych vektor˚ u. Na obrázku 9 je znázornˇeno schéma pr˚ ubˇehu experimentu. Z dostupné kolekce dokument˚ u je nutné nejdˇr´ıve vybrat vhodné mnoˇzstv´ı dat, které je poté rozdˇeleno na trénovac´ı a testovac´ı mnoˇzinu. Urˇcuj´ıc´ı je poˇzadovan´ y poˇcet dokument˚ u v trénovac´ı mnoˇzinˇe, takˇze testovac´ı dokumenty jsou vyb´ırány pomˇernˇe v˚ uˇci poˇctu trénovac´ıch dokument˚ u, a to v pomˇeru 1 : 3, takˇze na jeden testovac´ı dokument pˇripadaj´ı tˇri trénovac´ı dokumenty. Trénovac´ı mnoˇzina je následnˇe celá pouˇzita pro natrénován´ı jednoho klasifikátoru, kter´ y pˇredstavuje klasick´ y pˇr´ıstup ke klasifikaci textov´ ych dokument˚ u. Zároveˇ n je rozdˇelena na vzájemné disjunktn´ı podmnoˇziny, nad kter´ ymi jsou opˇet nauˇceny jednotlivé klasifikátory, které vytvoˇr´ı komisi. Z kaˇzdé trénovac´ı mnoˇziny je vytvoˇren slovn´ık, pomoc´ı kterého jsou transformována testovac´ı data a pˇr´ısluˇsn´ y klasifikátor je na tˇechto datech otestován. V pˇr´ıpadˇe komise je koneˇcná tˇr´ıda neznámého dokumentu urˇcena dle rozhodnut´ı vˇetˇsiny.

4.2

N´ avrh aplikace pro realizaci experiment˚ u

Aplikace pro realizaci experiment˚ u mus´ı slouˇzit jako nástroj, kter´ y umoˇzn´ı jeho uˇzivateli snadno definovat, jak´ y druh klasifikátoru bude pro klasifikaci pouˇzit a jaké hodnoty parametr˚ u, kter´ ymi je moˇzné ovlivnit pr˚ ubˇeh trénován´ı a testován´ı daného klasifikátoru, budou nastaveny. Také mus´ı b´ yt snadno nastavitelné, na jak´ ych datech bude klasifikátor trénován a na kter´ ych datech bude také testován. Veˇsker´ y pr˚ ubˇeh celého experimentu je nutné nˇejak´ ym zp˚ usobem zaznamenávat, takˇze je také nutné

4.3

Implementace

49

Obrázek 9: Schématické znazornˇen´ı hlavn´ıch krok˚ u experimentu. Expertem je jeden klasifikátor nauˇcen´ y na celé trénovac´ı mnoˇzinˇe a komisi tvoˇr´ı nˇekolik klasifikátor˚ u nauˇcen´ ych na trénovac´ıch podmnoˇzin´ ach.

umoˇznit nastaven´ı parametr˚ u, jako název souboru pro uchován´ı predikc´ı nauˇceného klasifikátoru nebo název souboru pro uloˇzen´ı z´ıskaného klasifikátoru. Aplikace by mˇela vˇsechna tato nastaven´ı naˇc´ıst, vytvoˇrit odpov´ıdaj´ıc´ı typ klasifikátoru, nastavit zadané parametry klasifikátoru, spustit uˇcen´ı nad zadan´ ymi trénovac´ımi daty a po ukonˇcen´ı trénovac´ı fáze otestovat nauˇcen´ y klasifikátor na souboru s testovac´ı mnoˇzinou dokument˚ u. Veˇskeré v´ ystupy na standardn´ı a chybov´ y v´ ystup by mˇely b´ yt zaznamenány do logovac´ıho souboru pro pozdˇejˇs´ı zkontrolován´ı pr˚ ubˇehu celého ’ experimentu. Zvláˇst by pak mˇely b´ yt uchovávány v´ ysledky z testován´ı z´ıskaného klasifikátoru, a to v podobˇe souboru obsahuj´ıc´ıho informace o tˇr´ıdˇe, do které testovac´ı dokument opravdu patˇr´ı, a tˇr´ıdˇe predikované dan´ ym klasifikátorem, aby mohly b´ yt po skonˇcen´ı experimentu vypoˇc´ıtány hodnot´ıc´ı metriky u ´spˇeˇsnosti.

4.3

Implementace

K implementaci byl vybrán programovac´ı jazyk C++ a jedn´ım z d˚ uvod˚ u tohoto v´ ybˇeru byla podpora objektového pˇr´ıstupu dan´ ym jazykem. Implementace aplikace tedy bude krátce popsána z hlediska jednotliv´ ych objekt˚ u, které celou aplikaci tvoˇr´ı.

4.3

50

Implementace

Experiment Základn´ı tˇr´ıda slouˇz´ıc´ı pro spuˇstˇen´ı celého experimentu. Stará se o vytvoˇren´ı objekt˚ u pro tisk zpráv a zpracován´ı konfiguraˇcn´ıho souboru, ve kterém jsou uloˇzena veˇskerá nastaven´ı konkrétn´ıho experimentu. Z tohoto souboru pˇreˇcte pouze typ pouˇz´ıvaného klasifikátoru a dle zadaného nastaven´ı vytvoˇr´ı objekt pro dan´ y algoritmus strojového uˇcen´ı. Po jeho vytvoˇren´ı je algoritmus spuˇstˇen. Algorithm Algorithm je abstraktn´ı tˇr´ıdou, pomoc´ı které jsou u tˇr´ıd pro konkrétn´ı algoritmy strojového uˇcen´ı vynucovány implementace dvou základn´ıch metod, volan´ ych skrze metody tˇr´ıdy Experiment. Prvn´ı metoda slouˇz´ı pro naˇcten´ı parametr˚ u z konfiguraˇcn´ıho souboru, jejichˇz ˇcást b´ yvá zpravidla specifická pro dan´ y algoritmus. Druhou metodou je implementováno spuˇstˇen´ı samotného algoritmu. Vˇsechny následuj´ıc´ı tˇr´ıdy reprezentuj´ıc´ı konkrétn´ı algoritmy jsou potomky této tˇr´ıdy (viz obrázek 10). ANNAlgorithm

SVMAlgorithm

KNNAlgorithm

# binary file

# docfile

# binary file

# test file

# testfile

# test file #k

# desired error # max epochs

# classify() # train()

# prepare ann()

+ load parameters()

# prepare subsets()

+ run()

# kdt depth # ktree dimensions # build kdtree()

# train ann()

# choose dimensions()

# test ann on data()

# search tree()

+ load parameters()

Algorithm

# sparse cosine() # split node()

+ run() # printer +load parameters()

+ load parameters() + run()

+run()

ˇ ast tˇr´ıdn´ıho diagramu zobrazuj´ıc´ı tˇr´ıdy reprezentuj´ıc´ı jednotlivé algoritmy. Obrázek 10: C´ Kv˚ uli rozsahu jsou uvedeny pouze vybrané metody a atributy bez datov´ ych typ˚ u a parametr˚ u.

ANNAlgorithm Tˇr´ıda reprezentuj´ıc´ı algoritmus neuronov´ ych s´ıt´ı umoˇzn ˇuje natrénován´ı a otestován´ı modelu s´ıtˇe oproti datovému souboru. Pro samotn´ y klasifikátor je pouˇz´ıvána knihovna FANN, rozˇs´ıˇrená o nˇekteré funkcionality, které knihovna sama o sobˇe neposkytuje.

4.3

Implementace

51

SVMAlgorithm Tato tˇr´ıda slouˇz´ı pro reprezentaci klasifikátoru podp˚ urn´ ych vektor˚ u. V implementaci je pouˇzita knihovna SVM light. Archiv, kter´ y je dostupn´ y na domovské stránce této knihovny, obsahuje zdrojové kódy pro knihovnu samotnou, ale také pro programy na nauˇcen´ı a otestován´ı podp˚ urn´ ych vektor˚ u. Tˇela metod train a classify jsou pˇrevzata ze soubor˚ u se zdrojov´ ym kódem tˇechto program˚ u a jsou pouze vhodnˇe upravena do objektové podoby. KNNAlgorithm Tˇr´ıda pro metodu nejbliˇzˇs´ıho souseda obstarává porovnán´ı testovac´ıch dokument˚ u s trénovac´ımi, v´ ypoˇcet vzdálenosti mezi dvˇema vektory reprezentuj´ıc´ı porovnávané dokumenty, v´ ybˇer k nejbliˇzˇs´ıch soused˚ u a urˇcen´ı predikované tˇr´ıdy na základˇe pˇr´ısluˇsnosti do tˇr´ıd u nejménˇe vzdálen´ ych dokument˚ u. Printer Velice jednoduchá abstraktn´ı tˇr´ıda slouˇz´ıc´ı jako pˇredloha pro tˇr´ıdy implementuj´ıc´ı jednotn´ y zp˚ usob v´ ypisu zpráv z pr˚ ubˇehu experimentu. Obˇe následuj´ıc´ı tˇr´ıdy jsou potomky této tˇr´ıdy, která vynucuje implementaci metod info, debug, warn a error. TerminalPrinter Tento potomek tˇr´ıdy Printer implementuje v´ ypis zpráv na standardn´ı v´ ystup a chybov´ ych zpráv na standardn´ı chybov´ y v´ ystup. Kaˇzdému ze ˇctyˇr typ˚ u zprávy je moˇzné nastavit hlaviˇcku, která bude vˇzdy pˇredcházet vypisovanému textu zprávy. Log4cPrinter Sofistikovanˇejˇs´ı zp˚ usob v´ ypisu zpráv, kter´ y veˇsker´ y v´ ystup zároveˇ n ukládá do souboru, implementuje tato tˇr´ıda, a to pomoc´ı knihovny Log4cplus11 urˇcené pro logován´ı v´ ystupu programu. Nastaven´ı celého logován´ı se provád´ı pomoc´ı konfiguraˇcn´ıho souboru. Ten je do programu pˇredán jako jeden z obecn´ ych parametr˚ u v konfiguraˇcn´ım souboru celého experimentu. Skripty pro pˇr´ıpravu dat Skripty pro pˇr´ıpravu dat slouˇz´ı pro hromadné zpracován´ı a pˇr´ıpravu kolekce textov´ ych dokument˚ u. Skripty pro pˇr´ıpravu prepare fann data a prepare svm data zajist´ı vytvoˇren´ı potˇrebn´ ych datov´ ych soubor˚ u pro realizaci experimentu na základˇe velikosti trénovac´ı mnoˇziny a poˇctu d´ılˇc´ıch podmnoˇzin. Pˇri svém bˇehu volaj´ı skripty split, slouˇz´ıc´ı pro rozdˇelen´ı dat na podmnoˇziny, a vectorize fann data nebo 11

http://log4cplus.sourceforge.net/

4.3

Implementace

52

vectorize svm data, které pouˇz´ıvaj´ı rozˇs´ıˇren´ y modul TextMining pro pˇrevod textov´ ych dat do vektorové podoby. 4.3.1

Adres´ aˇrov´ a struktura

Aplikace je do jisté m´ıry implementována na pevnˇe danou adresáˇrovou strukturu, ale názvy jednotliv´ ych sloˇzek a jejich um´ıstˇen´ı je moˇzné snadno zmˇenit, a to skrze hodnoty v konfiguraˇcn´ım souboru experimentu. V´ ychoz´ı struktura je znázornˇena následuj´ıc´ı: +-/ +-CPP/ | +-config/ | +-logs/ | +-results/ | +-src/ | +-include/ | +-convert | +-a.out +-output/ +-data +-_texts.text +-split/ +-experiment.sh +-generate_config_files.pl +-prepare_fann_data.sh +-prepare_svm_data.sh +-results.pl +-split.pl +-vectorize_fann_data.pl +-vectorize_svm_data.pl Nˇekolik perlovsk´ ych a shellovsk´ ych skript˚ u slouˇz´ı pouze pro pˇr´ıpravu dat a spouˇstˇen´ı sady experiment˚ u. Pˇri jejich implementaci jiˇz byla tato adresáˇrová struktura brána jako závazná a tud´ıˇz jsou potˇrebné datové soubory oˇcekávány ve sloˇzkách data a data/split nebo názvy a um´ıstˇen´ı program˚ u convert a a.out ve sloˇzce CPP. 4.3.2

Rozˇs´ıˇren´ı modulu TextMining

Transformace textov´ ych dokument˚ u do vektorové podoby spolu s pˇrepoˇc´ıtán´ım vah jednotliv´ ych term˚ u a následn´ ym uloˇzen´ım do souboru s uˇcit´ ym formátem obstarává programov´ y modul TextMining. Bohuˇzel neobsahuje podporu pro formáty, které jsou vyˇzadovány knihovnami pouˇzit´ ymi pro jednotlivé klasifikátory. Aby tedy bylo moˇzné modul pouˇz´ıt, je nutné rozˇs´ıˇrit jeho podporované v´ ystupn´ı formáty.

4.3

53

Implementace

Form´ at FANN Knihovna FANN pouˇz´ıvá pro uloˇzen´ı datov´ ych soubor˚ u vlastn´ı formát textového souboru, kde se na prvn´ım ˇra´dku nacház´ı mezerou oddˇelené základn´ı informace o datovém souboru, a to celkov´ y poˇcet pˇr´ıklad˚ u, poˇcet atribut˚ u vstupn´ıho vektoru a poˇcet atribut˚ u v´ ystupn´ıho vektoru. Dále jiˇz jsou v souboru uvedeny jednotlivé pˇr´ıklady, vˇzdy jako dvojice ˇrádk˚ u, kde na prvn´ım je uveden vstupn´ı vektor a na druhém v´ ystupn´ı vektor. Celkov´ y poˇcet ˇra´dk˚ u souboru je tedy 2n + 1, kde n je poˇcet pˇr´ıklad˚ u. Veˇskeré hodnoty vektor˚ u jsou od sebe oddˇeleny jednou mezerou. Zde je uveden obecn´ y zápis a jednoduch´ y pˇr´ıklad datového souboru pro funci XOR: data_length num_input num_output input-vector_1 output-vector_1 input-vector_2 output-vector_2 ... input-vector_n output-vector_n

4 2 1 1 1 1 0 1 0 ... 0 0 1

Form´ at FANN-SPARSE Vzhledem k rozsáhlosti jednotliv´ ych vektor˚ u, které mohou m´ıt v´ıce jak deset tis´ıc atribut˚ u z nichˇz drtivá vˇetˇsina nese nulovou hodnotu, je mnohem efektivnˇejˇs´ı ukládat datové soubory v tzv. ˇr´ıdkém formátu. Ukládány jsou pouze nenulové hodnoty, a to jako dvojice ˇc´ıslo atributu a hodnota. Formát souboru tedy z˚ ustává totoˇzn´ y s p˚ uvodn´ım formátem, pouze jednotlivé vektory jsou uloˇzeny v ˇr´ıdkém formátu, pˇriˇcemˇz vˇsechny ˇc´ıselné hodnot jsou od sebe oddˇeleny mezerou. Form´ at SVMlight Knihovna SVM light vyˇzaduje datové soubory uloˇzeny také ve svém vlastn´ım formátu. Jelikoˇz vˇsak byla implementována i za u ´ˇcelem klasifikace textov´ ych dokument˚ u pomoc´ı podp˚ urn´ ych vektor˚ u, je tomuto faktu uzp˚ usoben i samotn´ y formát datového souboru. Stejnˇe jako v pˇr´ıpadˇe knihovny FANN jde o textov´ y soubor, kter´ y na kaˇzdém ˇrádku uchovává jeden vektor. Vektory jsou vˇsak rovnou vyˇzadovány v ˇr´ıdkém formátu, coˇz eliminuje prostorovou nároˇcnost ukládán´ı textov´ ych dokument˚ u ve vektorové reprezentaci. Zde je uveden obecn´ y formát zápisu jednoho pˇr´ıkladu a konkrétn´ı pˇr´ıklad funkce XOR: class index:value index:value index:value ... +1 0:1 1:1 -1 0:0 1:1 -1 0:1 1:0 +1 0:0 0:0

4.3

Implementace

54

Na zaˇcátku kaˇzdého ˇra´dku je tedy nutné uvést tˇr´ıdu, do které pˇr´ıklad patˇr´ı, v pˇr´ıpadˇe binárn´ıho klasifikátoru jsou moˇzn´ ymi tˇr´ıdami pouze hodnoty +1 a −1. Dále jsou jiˇz zapsány pouze dvojteˇckou oddˇelená ˇc´ısla index atributu a hodnota, pˇriˇcemˇz tyto jednotlivé dvojice jsou od sebe navzájem oddˇeleny mezerou. Slovn´ık s parametry pro v´ aˇ zen´ı Pokud je klasifikátor nauˇcen na konkrétn´ı mnoˇzinˇe trénovac´ıch dokument˚ u, které byly pˇri transformaci do vektorové reprezentace urˇcit´ ym zp˚ usobem váˇzeny, je nutné stejn´ ym zp˚ usobem pˇredzpracovat i testovac´ı mnoˇzinu. Jednoduch´ ym pˇr´ıstupem by bylo vytvoˇrit jednu velkou mnoˇzinu dat slouˇcen´ı trénovac´ı i testovac´ı, pˇr´ıpadnˇe i validaˇcn´ı mnoˇziny, a tu zpracovat najednou. T´ım by vˇsak doˇslo ke stanoven´ı parametr˚ u pro váˇzen´ı hodnot term˚ u i na základˇe dokument˚ u v testovac´ı mnoˇzinˇe, coˇz nen´ı ˇza´dané, jelikoˇz urˇcuj´ıc´ı je pouze trénovac´ı mnoˇzina. Pokud by napˇr´ıklad testovac´ı mnoˇzina obsahovala slovo, které by se ve trénovac´ı mnoˇzinˇe nevyskytovalo, doˇslo by v pˇr´ıpadˇe zpracován´ı jedné velké mnoˇziny dokument˚ u k zahrnut´ı tohoto slova do pˇr´ıznakového vektoru, ale nikdy by tento pˇr´ıznak nebyl pˇri trénován´ı pouˇzit, protoˇze se v trénovac´ıch datech nevyskytuje ˇza´dn´ y dokument, kter´ y by mohl danému atributu pˇridˇelit nˇejakou hodnotu. Pokud vˇsak budou trénovac´ı data upravena na základˇe parametr˚ u pouze z trénovac´ı mnoˇziny, dojde k vyˇrazen´ı tohoto pro klasifikátor neznámého slova. Obdobná logika plat´ı i pro parametry pro váˇzen´ı jednotliv´ ych term˚ u. Pouˇzit´ y modul umoˇzn ˇuje zpracovávat textové dokumenty na základˇe zadaného slovn´ıku, kdy pˇri pˇrevodu do vektorové reprezentace dojde k vyˇrazen´ı tˇech slov, která se ve slovn´ıku nenacház´ı. Bohuˇzel vˇsak nejsou pˇrenáˇseny váˇz´ıc´ı parametry. Modul byl tedy rozˇs´ıˇren o moˇznost generován´ı slovn´ıku, kter´ y pro jednotlivá slova uchovává také potˇrebné váˇz´ıc´ı parametry, jako celkov´ y v´ yskyt slova v kolekci, minimáln´ı a maximáln´ı hodnota v´ yskytu slova apod. Pˇri zadán´ı tohoto upraveného slovn´ıku nejsou tedy tyto hodnoty zjiˇst’ovány ze zadaného vstupn´ıho datové souboru, ale ze slovn´ıku, ˇc´ımˇz je zajiˇstˇena shodná reprezentace hodnot trénovac´ı i testovac´ı mnoˇziny. 4.3.3

Rozˇs´ıˇren´ı knihovny FANN

Knihovna FANN poskytuje pro práci s neuronov´ ymi s´ıtˇemi pouze dvˇe tˇr´ıdy, které reprezentuj´ı: • neuronovou s´ıt’, • pouˇzitá data. Aby nebylo nutné v´ yraznˇe zasahovat do kódu knihovny, jsou od tˇechto dvou tˇr´ıd odvozeni potomci, kteˇr´ı implementuj´ı potˇrebná funkˇcn´ı rozˇs´ıˇren´ı.

4.3

Implementace

55

Rozdˇ elen´ı dat a normalizace Data pro neuronové s´ıtˇe je tˇreba rozdˇelit na celkem tˇri disjunktn´ı mnoˇziny, a to trénovac´ı, testovac´ı a validaˇcn´ı data. Knihovna FANN umoˇzn ˇuje naˇcten´ı jednoho datového souboru pro proces uˇcen´ı, pro testován´ı je poté moˇzné pouˇz´ıt zcela jin´ y soubor. V zájmu zachován´ı p˚ uvodn´ı podoby func´ı této knihovny, budou tyto tˇri mnoˇziny zahrnuty v jednom jediném souboru. Data bude tedy nutné internˇe vhodnˇe rozdˇelit. Pro tyto u ´ˇcely bylo implementováno nˇekolik funkc´ı, které jednak vypoˇc´ıtaj´ı hranice jednotliv´ ych mnoˇzin, umoˇzn´ı v´ ybˇer aktuálnˇe pouˇz´ıvané mnoˇziny a práci s urˇcitou podmnoˇzinou jako s jednolit´ ym datov´ ym souborem. Pˇri pouˇz´ıván´ı neuronov´ ych s´ıt´ı je nutné, stejnˇe jako u ostatn´ıch typ˚ u klasifikátor˚ u, ˇreˇsit normalizaci dat. Pokud by data z˚ ustala ve svém p˚ uvodn´ım tvaru, pro s´ıt’ by bylo mnohem nároˇcnˇejˇs´ı vhodnˇe upravovat váhy vazeb mezi neurony tak, aby chyba z˚ ustala co nejmenˇs´ı. Normalizaci dat je moˇzné pouˇz´ıt jiˇz pˇri pˇrevádˇen´ı dokument˚ u do vektorové reprezentace. Jelikoˇz by vˇsak kv˚ uli rozdˇelován´ı dat nen´ı pˇri pˇredzpracován´ı dat pˇredem jasné, které pˇr´ıklady budou patˇrit do jaké mnoˇziny, je i normalizace provádˇena pˇr´ımo pˇri bˇehu aplikace. Implementace tedy rozˇs´ıˇr´ıla moˇznosti knihovny FANN o následuj´ıc´ı funkcionalitu. Normalizaci dat je moˇzné zapnout zavolán´ım metody, která vypoˇc´ıtá a nastav´ı normalizaˇcn´ı parametry pro vˇsechny jednotlivé atributy vstupn´ıch dat, a to na základˇe aktuálnˇe vybrané mnoˇziny. Pokud nejsou data rozdˇelena, jsou parametry vypoˇc´ıtány z celého datového souboru. Tˇemito hodnotami jsou: • minimáln´ı hodnota, • maximáln´ı hodnota, • suma hodnot, • rozsah hodnot, • pr˚ umˇerná hodnota. Normalizovaná hodnota je vypoˇc´ıtána jako pod´ıl mezi rozd´ılem p˚ uvodn´ı hodnoty a pr˚ umˇerné hodnoty a rozsahu hodnot (rozd´ıl maximáln´ı a minimáln´ı hodnoty) pro dan´ y atribut. xi,j − avgj x0i,j = maxj − minj Data jsou do normalizované hodnoty pˇrevádˇena vˇzdy pˇri jejich v´ ybˇeru z datového souboru. Kombinac´ı v´ ybˇeru trénovac´ı mnoˇziny a následn´ ym zavolán´ım normalizaˇcn´ı metody je tedy dosaˇzeno aplikován´ı normalizaˇcn´ıch parametr˚ u pouze z trénovac´ı mnoˇziny na data v ostatn´ıch mnoˇzinách. Pokud je nutné normalizovat data ze zcela jiného datového souboru, je moˇzné mezi nimi pˇredat momentálnˇe pouˇz´ıvané normalizaˇcn´ı parametry.

4.3

Implementace

56

Validace bˇ ehem tr´ enov´ an´ı Pˇri uˇcen´ı neuronov´ ych s´ıt´ı m˚ uˇze doj´ıt k celkem dvˇema negativn´ım v´ ysledk˚ um. ’ Prvn´ım je nedouˇcen´ı, kdy dojde k tomu, ˇze nauˇcená s´ıt nedokázala bˇehem uˇcen´ı dostateˇcnˇe zobecnit znalost skrytou v trénovac´ıch datech, protoˇze byl tento proces ukonˇcen pˇr´ıliˇs brzy, nejˇcastˇeji v d˚ usledku pˇr´ıliˇs vysoké hodnoty poˇzadovanové chyby. Druh´ ym pˇr´ıpadem je pˇresn´ y opak. S´ıt’ se uˇc´ı na trénovac´ıch datech tak dlouho, aˇz zaˇcne ztrácet schopnost generalizace skryté znalosti a ze s´ıtˇe se stává expert pouze na trénovac´ı data. Na testovac´ıch datech tak bude v obou pˇr´ıpadech s´ıt’ dosahovat zpravidla n´ızké pˇresnosti. Zat´ımco nedouˇcen´ı je moˇzné relativnˇe snadno vyˇreˇsit zmˇenou parametr˚ u, zamezen´ı pˇreuˇcen´ı s´ıtˇe je o nˇeco sloˇzitˇejˇs´ı. Uˇcen´ı je tˇreba zastavit ve chv´ıli, kdy se zaˇcne zhorˇsovat schopnost s´ıtˇe generalizace, tzn. dojde ke zv´ yˇsen´ı chybovosti na tzv. validaˇcn´ı mnoˇzinˇe dat. Moˇznost validace bˇehem trénován´ı neuronové s´ıtˇe musela b´ yt doprogramována, aby mohlo b´ yt zabránˇeno pˇreuˇcen´ı klasifikátor˚ u. Knihovna FANN umoˇzn ˇuje implementaci callback funkce, která je volána bˇehem kaˇzdé trénovac´ı epochy a jej´ı návrátová hodnota je urˇcij´ıc´ı pro pokraˇcován´ı trénován´ı nebo jeho pˇreruˇsen´ı. Jde tedy o ideáln´ı zp˚ usob, jak rozˇs´ıˇrit funcionalitu knihovny o validaci. Zastavovac´ı pravidlo má následuj´ıc´ı podobu. Pokud dojde nˇekolikrát bezprostˇrednˇe po sobˇe ke zv´ yˇsen´ı chyby na validaˇcn´ı mnoˇzinˇe dat, uˇcen´ı s´ıtˇe bude pˇredˇcasnˇe zastaveno. Poˇcet zv´ yˇsen´ı validaˇcn´ı chyby je pak jedn´ım z parametr˚ u uˇcen´ı s´ıtˇe. V callback funkci dojde ke zmˇenˇe trénovac´ıch dat na validaˇcn´ı mnoˇzinu, uloˇz´ı se souˇcasná hodnota chyby (vypoˇc´ıtána pˇri trénován´ı), otestuje se souˇcasné nauˇcen´ı s´ıtˇe na validaˇcn´ıch datech a zkontroluje se nová chybovost s jej´ım historick´ ym v´ yvojem. Pokud doˇslo k pˇr´ıliˇs velkému poˇctu zv´ yˇsen´ı, funkce vrát´ı negativn´ı hodnotu, ˇc´ımˇz dojde k zastaven´ı trénován´ı. V opaˇcném pˇr´ıpadˇe se chyba uloˇz´ı, obnov´ı se dˇr´ıve uloˇzená trénovac´ı chyba a zmˇen´ı se mnoˇzina dat na trénovac´ı. Funkce v tomto pˇr´ıpadˇe vrát´ı pozitivn´ı hodnotu. ˇ ıdk´ R´ y form´ at dat Pˇrepracován byl rovnˇeˇz zp˚ usob reprezentace vstupn´ıch a v´ ystupn´ıch vektor˚ u z hustého tvaru na ˇr´ıdk´ y. T´ım dojde ke markantn´ımu sn´ıˇzen´ı prostorové nároˇcnosti celého algoritmu. Z implementaˇcn´ıho hlediska ˇslo o pomˇernˇe jednoduchou u ´pravu, kdy jsou z datovéhou souboru pˇreˇcteny a ve formˇe atribut˚ u objektu uchovány u ´daje o poˇzadované velikosti vstupn´ıch a v´ ystupn´ıch vektor˚ u, které jsou následnˇe pouˇzity pro sestaven´ı hust´ ych vektor˚ u z ˇr´ıdké reprezentace naˇctené z datového souboru. Data jsou tedy uchovávána a naˇc´ıtána efektivnˇe a k jejich rozˇs´ıˇren´ı do hustého tvaru docház´ı pouze ve chv´ıli v´ ypoˇctu pˇri uˇcen´ı neuronové s´ıtˇe. 4.3.4

Form´ at pro bin´ arn´ı uchov´ an´ı dat

Data, se kter´ ymi neuronové s´ıtˇe pracuj´ı, jsou vyjádˇrena ˇc´ıseln´ ymi hodnotami. Uloˇzen´ı ˇc´ıseln´ ych hodnot v textovém souboru je vˇsak neefektivn´ı a obecnˇe je práce

4.3

57

Implementace

s textov´ ym souborem nároˇcnˇejˇs´ı, pokud jde o pˇr´ıstup k r˚ uzn´ ym ˇcástem souboru. V´ yhodnˇejˇs´ı variantou je ukládán´ı tˇechto dat v podobˇe binárn´ıho souboru, kter´ y umoˇzn ˇuje dynamicky pˇristupovat k hodnotám na libovolném m´ıstˇe v souboru, bez komplikovaného ˇcten´ı a práci s textov´ ymi daty. Na obrázku 11 je znázornˇen formátu souboru, kter´ y byl implementován pro u ´ˇcely uchován´ı vektorové reprezentace textov´ ych dokument˚ u a dynamick´ y pˇr´ıstup k jednotliv´ ym vektor˚ um v pr˚ ubˇehu trénován´ı nebo testován´ı s´ıtˇe. Pouˇzit´ı tohoto souboru také usnadn´ı práci s rozdˇelen´ım datového souboru na trénovac´ı, testovac´ı a validaˇcn´ı podmnoˇziny. Rozhran´ı mezi +---+ | | <- jeden byte +---+

+===========+ | | <- v´ ıce byt˚ u +===========+

Bin´ arn´ ı soubor: +===========+================+======+ | meta_data | d´ elky_vektor˚ u | data | +===========+================+======+ Meta data: +---+---+---+---+---+---+---+---+---+---+---+---+ | poˇ cet_dat | pocˇ et_vstup˚ u | poˇ cet_v´ ystup˚ u | +---+---+---+---+---+---+---+---+---+---+---+---+ D´ elky vektor˚ u: +---+---+---+---+ d´ elka_dat x | d´ elka_vektoru | +---+---+---+---+ Data: +======================+---+---+---+---+ | r ˇı ´dk´ y_vstupn´ ı_vetkor |v´ ystupn´ ı_vektor| +======================+---+---+---+---+ ˇ Rı ´dk´ y vektor: +---+---+---+---+---+---+---+---+ d´ elka_vektoru x | index | hodnota | +---+---+---+---+---+---+---+---+ Obrázek 11: Schéma uspoˇr´ ad´ an´ı dat v binárn´ım souboru

binárn´ım souborem a tˇr´ıdou pro reprezentaci dat pouˇz´ıvan´ ych neuronovou s´ıt´ı zajiˇst’uje tˇr´ıda tie.

4.4

Experimenty

4.3.5

58

Nejbliˇ zˇs´ı soused

Posledn´ı implementovanou ˇca´st´ı je algoritmus nejbliˇzˇs´ıho souseda, kter´ y klasifikuje na základˇe podobnosti ˇci vzdálenosti jednotliv´ ych dokument˚ u. K vlastn´ı implementaci bylo pˇristoupeno z d˚ uvodu nemoˇznosti vyuˇzit´ı nˇekteré z dostupn´ ych knihoven, které naˇc´ıtaly celá vstupn´ı data do pamˇeti. V pˇr´ıpadˇe dat zpracovávan´ ych v této práci jde o bezmála 10 GB, coˇz nen´ı pro bˇeˇzné poˇc´ıtaˇce prostorovˇe u ńosné. Ve vlastn´ı implementaci budou tedy vyuˇzity jiˇz dostupné prostˇredky v podobˇe binárn´ıho souboru a ˇr´ıdké reprezentace dat. Pro dalˇs´ı sn´ıˇzen´ı nároˇcnosti je mnoˇzstv´ı prohledávan´ ych dokument˚ u zredukováno pomoc´ı tzv. k-dimenzionáln´ıho stromu, kter´ y rozdˇeluje prostor vstupn´ıch dat dle jednotliv´ ych dimenz´ı na menˇs´ı podprostory. T´ımto zp˚ usobem jsou vˇsechny trénovac´ı dokumenty rozdˇeleny do podmnoˇzin a pˇri klasifikaci neznámého dokumentu se nejdˇr´ıve zjist´ı, do které podmnoˇziny by dle sv´ ych hodnot atribut˚ u spadal, a následnˇe je porovnán pouze s dokumenty z této podmnoˇziny.

4.4

Experimenty

C´ılem experiment˚ u je prozkoumat moˇznost paraleln´ıho zpracován´ı rozsáhlé kolekce dokument˚ u a zjistit, jak´ y m˚ uˇze m´ıt podobn´ y pˇr´ıstup vliv na pˇresnost v´ ysledné klasifikace tˇechto textov´ ych dat. Experimenty jsou realizovány následuj´ıc´ım zp˚ usobem: jednak je nutné vyzkouˇset r˚ uzná rozdˇelen´ı trénovac´ı mnoˇziny a také r˚ uzné velikosti ˇ zka, Daˇrena, 2012) byl této mnoˇziny. Na základˇe jiˇz realizovan´ ych experiment˚ u (Ziˇ zvolen podobn´ y pˇr´ıstup, aby z´ıskané v´ ysledky bylo moˇzné porovnat. Hlavn´ı experiment bude realizován nad vybranou trénovac´ı mnoˇzinou o 200 000 dokumentech a tato kolekce bude rozdˇelena na 10, 5, 4, 3 a 2 disjunktn´ı podmnoˇziny. Stejn´ ym zp˚ usobem pak bude zpracována i mnoˇzina o 100 000 dokumentech, na které bude také otestován vliv zmˇeny parametr˚ u klasifikátor˚ u na v´ yslednou klasifikaci. Pro realizaci experiment˚ u byl pouˇzit domác´ı poˇc´ıtaˇc s pomˇernˇe star´ ym hardwarov´ ym vybaven´ım. Pouˇzit´ y stroj byl osazen tˇr´ıjádrov´ ym procesorem od firmy AMD a k dispozici bylo celkem 4 GB operaˇcn´ı pamˇeti. Tento poˇc´ıtaˇc poslouˇzil jako host pro vytvoˇren´ı dvou virtuáln´ıch stroj˚ u, na kter´ ych byly exeprimenty spouˇstˇeny. Obˇema virtuáln´ı stroj˚ um bylo pˇridˇeleno jedno jádro fyzického procesoru a 1 GB z dostupné operaˇcn´ı pamˇeti. Jako operaˇcn´ı systém byla pouˇzita linuxová distribuce Ubuntu 12.10 v tzv. minimáln´ı verzi. Pro vˇsechny experimenty jsou pouˇzity totoˇzné dokumenty, které jsou pouze reprezentovány r˚ uzn´ ym zp˚ usobem, a to podle pouˇzitého typu klasifikátoru. Z vybran´ ych dokument˚ u byla vyˇrazena slova, která se na globáln´ı u ´rovni – tzn. v rámci celé vybrané kolekce – vyskytuj´ı ménˇe neˇz tˇrikrát. Jin´ y zp˚ usob vyˇrazován´ı slov z vektorové reprezentace dokument˚ u nebyl pouˇzit. Data jsou také vyb´ırána tak, aby pomˇer mezi obˇema tˇr´ıdami byl vyrovnan´ y. D´ıky vyváˇzenosti obou tˇr´ıd v pouˇzit´ ych datech je moˇzné provést shodnocen´ı kvality z´ıskané znalosti pomoc´ı metriky Acc, stejnˇe tak jsou ale uvedeny i ostatn´ı v´ yˇse popsané indikátory pˇresnosti klasi-

4.4

Experimenty

59

fikátoru. Jelikoˇz byly vytvoˇreny komise klasifikátor˚ u se sud´ ym poˇctem, je dalˇs´ım ze sledovan´ ych parametr˚ u poˇcet testovac´ıch pˇr´ıpad˚ u, o kter´ ych komise nedokázala (v d˚ usledku shodného poˇctu hlas˚ u) rozhodnout. D˚ uleˇzit´ ym faktorem je také ˇcas, kter´ y je potˇrebn´ y pro natrénován´ı. 4.4.1

Neuronov´ e s´ıtˇ e

Narozd´ıl od ostatn´ıch pouˇzit´ ych klasifikátor˚ u vyˇzaduj´ı neuronové s´ıtˇe pro sv˚ uj bˇeh a z´ıskán´ı kvalitn´ıch v´ ysledk˚ u vyˇzaduj´ı pouˇzit´ı validaˇcn´ı mnoˇziny. Ta je vybrána stejn´ ym zp˚ usobem jako testovac´ı mnoˇzina, tzn. vzhledem k velikosti trénovac´ı mnoˇziny, a to v pomˇeru 3 : 1. Model neuronové s´ıtˇe bylo moˇzné parametrizovat ˇradou r˚ uzn´ ych nastaven´ı. Pˇri zpracován´ı dokument˚ u bylo pouˇzito následuj´ıc´ı nastaven´ı: • reprezentace dat: term-frequency, • poˇcet skryt´ ych vrstev: 1, • velikost skryt´ ych vrstev: 50 neuron˚ u, • uˇc´ıc´ı algoritmus: backpropagation, • pˇrechodové funkce: sigmoidáln´ı, • velikost chyby: 0.005, • validaˇcn´ı zastaven´ı: v´ıce jak 5 zv´ yˇsen´ı validaˇcn´ı chyby. S t´ımto nastaven´ım jsou nad jednotliv´ ymi trénovac´ımi mnoˇzinami vytvoˇreny potˇrebné klasifikátory a následnˇe vˇsechny otestovány na testovac´ı mnoˇzinˇe. Dosaˇzené ˇ v´ ysledky jsou zobrazeny v tabulce 5. Casov´ e hodnoty jsou zde uvedeny jako poˇcet minut, pˇriˇcemˇz jde o souˇcet ˇcasu potˇrebného pro nauˇcen´ı vˇsech klasifikátor˚ u v dané komisi. Ve sloupc´ıch jsou uvedeny hodnoty: poˇcet klasifikátor˚ u, ˇcas uˇcen´ı, metriky accuracy, recall, precision, f-measure, poˇcet dokument˚ u bez klasifikace a skóre komise (v´ ypoˇcet uveden dále). Na v´ ysledc´ıch je pomˇernˇe hezky vidˇet vliv nerozhodnosti klasifikátor˚ u, které tvoˇrily komisi se sud´ ym poˇctem ˇclen˚ u, ˇc´ımˇz mohlo docházet ke shodnému poˇctu hlas˚ u pro obˇe tˇr´ıdy, a proto nemohlo b´ yt rozhodnuto o koneˇcné klasifikaci testovaného dokumentu. Nejde vˇsak o velké mnoˇzstv´ı pˇr´ıpad˚ u, u nejhorˇs´ı varianty, kterou je dvouˇclenná komise, bylo takto nezaˇrazeno zhruba 1 % testovac´ıch pˇr´ıpad˚ u. S vyˇsˇs´ım poˇctem ˇclen˚ u komise se mnoˇzstv´ı neklasifikovan´ ych dokument˚ u zmenˇsuje, a to pˇribliˇznˇe ve stejném pomˇeru pro obˇe velikosti trénovac´ıch dat. Z hlediska pˇresnosti klasifikace jsou dosaˇzené v´ ysledky pˇribliˇznˇe stejné. V´ yjimku opˇet tvoˇr´ı dvouˇclenná komise, u které doˇslo k poklesu pˇresnosti o zhruba pˇet procent, coˇz je pˇreváˇznˇe d˚ usledek vˇetˇs´ıho mnoˇzstv´ı neklasifikovan´ ych dokument˚ u. V ostatn´ıch metrikách jsou jiˇz v´ ysledky mezi jednotliv´ ymi komisemi velice vyrovnané, rozd´ılnost se pohybuje maximálnˇe do dvou procent. Pˇresnosti je tedy za pomoc´ı komise moˇzné dosáhnout témˇeˇr totoˇzné, jako v pˇr´ıpadˇe jednoho klasifikátoru, dokonce je zpozo-

4.4

60

Experimenty

Tabulka 5: V´ ysledky dosaˇzené s klasifikátorem neuronové s´ıtˇe

100k N

ˇ [min] Cas

Acc

Rec

Prec

F

Scorek

Bez klasifikace

1

875

0.9195

0.9218

0.9173

0.9195

—

—

2

360

0.8671

0.9625

0.8973

0.9288

0.7658

2941

3

222

0.9256

0.9253

0.9259

0.9256

0.8765

—

4

168

0.9055

0.9520

0.9160

0.9337

0.8964

1454

5

130

0.9334

0.9503

0.9147

0.9322

0.9333

—

10

80

0.9228

0.9451

0.9258

0.9354

0.9561

658

200k 1

10560

0.9132

0.9007

0.9289

0.9146

—

—

2

1740

0.8564

0.9613

0.8990

0.9291

0.8865

6456

3

1080

0.9334

0.9399

0.9261

0.9330

0.9599

—

4

720

0.9061

0.9520

0.9252

0.9384

0.9620

3169

5

600

0.9373

0.9511

0.9220

0.9363

0.9848

—

10

240

0.9320

0.9554

0.9228

0.9388

0.9989

932

rováno i nepatrné zv´ yˇsen´ı. Nejvˇetˇs´ı rozd´ıly jsou vˇsak vidˇet v ˇcase potˇrebném pro sestaven´ı komise. V pˇr´ıpadˇe menˇs´ı varianty trénovac´ı mnoˇziny trvalo nauˇcen´ı jednoho klasifikátoru zhruba 14 hodin. Tento ˇcas je moˇzné zkrátit v´ıce jak o polovinu ´ jiˇz pouh´ ym rozdˇelen´ım na dvˇe podmnoˇziny. Uspora ˇcasu dále roste s velikost´ı komise. U varianty s vˇetˇs´ı trénovac´ı mnoˇzinou je ˇcasová u ´spora jeˇstˇe v´ yraznˇejˇs´ı. Samostatn´ y klasifikátor byl trénován zhruba sedm a p˚ ul dne, zat´ımco dvouˇclenná komise umoˇznila sn´ıˇzit potˇrebn´ y ˇcas na 29 hodin. S vyˇsˇs´ım poˇctem klasifikátor˚ u a vˇetˇs´ım mnoˇzstv´ım zpracovávan´ ych tedy v´ yraznˇe roste ˇcasová u ´spora. Pokud by bylo tˇreba vyjádˇrit jednou ˇc´ıselnou hodnotu kvalitu konkrétn´ı komise, zohledˇ nuj´ıc´ı ˇcas potˇrebn´ y na nauˇcen´ı, je nutné navrhnout v´ ypoˇcet této hodˇ ıselné vyjádˇren´ı by tedy mˇelo brát v potaz uˇsetˇrené mnoˇzstv´ı ˇcasu a zmˇenu noty. C´ pˇresnosti komise oproti jednomu klasifikátoru. Vzorec, navrhnovan´ y pro v´ ypoˇcet této hodnoty je následuj´ıc´ı: time1 Acc1 scorek = 0.5 · 1− + timek Acck Jde o pouhou pr˚ umˇernou hodnotu z pomˇer˚ u mezi ˇcasem a pˇresnost´ı komise a jednoho klasifikátoru, pˇriˇcemˇz ˇcas je pˇrepoˇc´ıtán na doplnˇek do jedné, aby vˇetˇs´ı u ´spora ˇcasu

4.4

Experimenty

61

mˇela pozitivn´ı vliv na v´ yslednou hodnotu skóre. Pouˇzit´ım tohoto zp˚ usobu vyjádˇren´ı kvality je moˇzné jednotlivé varianty mezi sebou snadno porovnat. Jako v´ yhodnˇejˇs´ı se tedy jev´ı komise s vyˇsˇs´ım poˇctem ˇclen˚ u, zjeména kv˚ uli v´ yrazn´ ym ˇcasov´ ym u ´sporám. Vzorec by dále bylo moˇzné upravit na váˇzen´ y pr˚ umˇer, pomoc´ı kterého by mohl b´ yt kladen vˇetˇs´ı d˚ uraz na zmˇenu pˇresnosti. 4.4.2

Podp˚ urn´ e vektory

Algoritmus podp˚ urn´ ych vektor˚ u je sám o sobˇe velice vhodn´ ym pro zpracován´ı textov´ ych dokument˚ u. Jednak je jeho proces uˇcen´ı mnohem rychlejˇs´ı neˇz u neuronov´ ych s´ıt´ı, ale také m˚ uˇze dosáhnout lepˇs´ı pˇresnosti. Aplikován´ı paraleln´ıho pˇr´ıstupu by tedy teoreticky mohlo také jeˇstˇe zv´ yˇsit pouˇzitelnost tohoto typu klasifikátoru pˇri zpracován´ı rozsáhl´ ych kolekc´ı. Joachims publikoval ˇradu ˇclánk˚ u, ve kter´ ych se vˇenoval pouˇzit´ı podp˚ urn´ ych vektor˚ u pˇri klasifikaci textov´ ych dokument˚ u. Parametrizace klasifikátoru tedy vycház´ı z doporuˇcen´ı uveden´ ych v tˇechto ˇclánc´ıch (Joachims, 1998). • reprezentace dat: tf-idf, • normalizace dat: kosinová, • jádrová funkce: polynomiáln´ı, • stupeˇ n polynomu: 3. Pr˚ ubˇeh je totoˇzn´ y jako u neuronov´ ych s´ıt´ı – kaˇzd´ y klasifikátor je s t´ımto nastaven´ım natrénován nad konkrétn´ı trénovac´ı mnoˇzinou a následnˇe otestován. V´ ysledky shrnuje tabulka 6, pˇriˇcemˇz ˇcas je tentokrát vyjádˇren jako poˇcet vteˇrin. Dosaˇzené v´ ysledky jsou velice podobné, jako v pˇr´ıpadˇe neuronov´ ych s´ıt´ı. Doˇslo vˇsak ke sn´ıˇzen´ı poˇctu neklasifikovan´ ych dokument˚ u a obecnˇe je dosahováno lepˇs´ıch hodnocen´ı. Pˇresnost mezi jednotliv´ ymi komisemi je vyrovnanˇejˇs´ı, ale v˚ uˇci jednomu klasifikátoru ˇ nedosáhla (narozd´ıl od s´ıt´ı) ˇza´dná komise lepˇs´ı pˇresnosti. Casov´ au ´spora, aˇckoliv je stále vzhledem k jednomu klasifikátoru pomˇernˇe velká (z necel´ ych 4 hodin na p˚ ul hodiny), nen´ı tak v´ yrazná jako u neuronov´ ych s´ıt´ı. Zde se tedy nab´ız´ı otázka, zda tato ˇcasová u ´spora stoj´ı jednoduˇse ˇreˇceno za námahu s pˇr´ıpravou dat pro d´ılˇc´ı klasifikátory. Rozd´ıl v pˇresnosti mezi komis´ı 10 klasifikátor˚ u a samostatného klasifikátoru ˇcin´ı 1 %, takˇze z´ıskaná znalost je teoreticky témˇeˇr totoˇzná a mnohem jednoduˇsˇs´ı je vytvoˇrit a pouˇz´ıvat klasifikátor jeden. Uplatnˇen´ım Occamovi bˇritvy by tedy mohl b´ yt jako nejlepˇs´ı ˇreˇsen´ı zvolen i navzdory ˇcasové u ´spoˇre samostatn´ y klasifikátor. Na základˇe skóre pro ohodnocen´ı komise jsou stejnˇe jako v pˇredchoz´ım pˇr´ıpadˇe v´ yhodnˇejˇs´ı skupiny s vyˇsˇs´ım poˇctem klasifikátor˚ u. 4.4.3

Nejbl´ıˇ zˇs´ı soused

Posledn´ım typem klasifikace dokument˚ u je metoda nejbliˇzˇs´ıho souseda. Jelikoˇz nebyl tento pˇr´ıstup implementován pomoc´ı knihovny, vycház´ı veˇskeré moˇznosti paramet-

4.4

62

Experimenty

Tabulka 6: V´ ysledky dosaˇzené s klasifikátorem podp˚ urn´ ych vektor˚ u

100k N

ˇ [sec] Cas

Acc

Rec

Prec

F

Scorek

Bez klasifikace

1

3945

0.9471

0.9657

0.9268

0.9459

—

—

2

2400

0.9299

0.9728

0.9065

0.9385

0.6867

819

3

1800

0.9422

0.9642

0.9185

0.9408

0.7693

—

4

1200

0.9337

0.9691

0.9074

0.9372

0.8408

492

5

1200

0.9401

0.9647

0.9137

0.9385

0.8442

—

10

500

0.9346

0.9679

0.9047

0.9352

0.9300

234

200k 1

14064

0.9506

0.9648

0.9352

0.9498

—

—

2

10800

0.9374

0.9731

0.9190

0.9453

0.6091

1396

3

7200

0.9480

0.9658

0.9290

0.9470

0.7427

—

4

5280

0.9409

0.9705

0.9201

0.9446

0.8072

796

5

3840

0.9458

0.9652

0.9250

0.9447

0.8610

—

10

2100

0.9393

0.9661

0.9150

0.9399

0.9194

402

rizace bˇehu z pomˇernˇe pˇr´ımoˇcaˇre pojaté implementace. • reprezentace dat: term-frequency, • mˇeˇren´ı podobnosti: kosinová podobnost, • poˇcet soused˚ u: 5, • poˇcet dˇel´ıc´ıch dimenz´ı: 10, • maximáln´ı hloubka K-D stromu: 8. Dosaˇzené v´ ysledky z´ıskané porovnán´ım dokument˚ u z testovac´ı mnoˇziny oproti jednotliv´ ym trénovac´ım mnoˇzinám jsou zobrazeny v tabulce 7, kde ˇcas je stejnˇe jako u neuronov´ ych s´ıt´ı vyjádˇren poˇctem minut. Oproti pˇredhoz´ım klasifikátor˚ um v´ yraznˇe vzrostl poˇcet neklasifikovan´ ych dokument˚ u, coˇz má také nezanedbateln´ y dopad na v´ yslednou pˇresnost komis´ı se sud´ ym poˇctem ˇclen˚ u. U dvouˇclenné komise nebylo moˇzné z celkového poˇctu testovan´ ych dokument˚ u pro v´ıce jak ˇctvrtinu urˇcit v´ yslednou tˇr´ıdu, coˇz má za následek v´ıce jak 10 % propad v pˇresnosti, ale zároveˇ n doˇslo k stejnému nár˚ ustu hodnoty metriky recall. Z hlediska ˇcasové nároˇcnosti doˇslo k malé u ´spoˇre v pˇr´ıpadˇe menˇs´ı trénovac´ı mnoˇziny u dvouˇclenné komise, v ostatn´ıch

4.4

63

Experimenty

Tabulka 7: V´ ysledky dosaˇzené s klasifikátorem nejbliˇzˇs´ıho souseda

100k N

ˇ [min] Cas

Acc

Rec

Prec

F

Scorek

Bez klasifikace

1

57

0.7728

0.7444

0.8331

0.7863

—

—

2

48

0.6344

0.8508

0.7064

0.7719

0.4894

8951

3

53

0.7999

0.7688

0.8579

0.8109

0.5526

—

4

52

0.7047

0.7904

0.8888

0.8367

0.4998

5247

5

61

0.8212

0.7729

0.9096

0.8357

0.4962

—

10

60

0.7948

0.8161

0.8979

0.8550

0.4879

2403

200k 1

370

0.7945

0.7524

0.8784

0.8105

—

—

2

250

0.6337

0.8507

0.7286

0.7850

0.5610

18132

3

232

0.8239

0.7847

0.8926

0.8352

0.7050

—

4

235

0.7448

0.8405

0.8606

0.8505

0.6512

9746

5

211

0.8334

0.7872

0.9137

0.8458

0.7393

—

10

270

0.8063

0.8209

0.9079

0.8622

0.6426

4326

pˇr´ıpadech byly ˇcasy velice podobné. U vˇetˇs´ı trénovac´ı mnoˇziny jiˇz doˇslo k urˇcit´ ym ˇcasov´ ym u ´sporám, avˇsak oproti pˇredchoz´ım variantám nikterak velk´ ym. Ohodnocen´ı jednotliv´ ych komis´ı pomoc´ı dˇr´ıve navrˇzeného vzorce jasnˇe ukazuje vliv neklasifikovan´ ych dat, kdy se rozd´ıl ve v´ ysledné hodnotˇe mezi komis´ı se sud´ ym a lich´ ym poˇctem hlas˚ u pohybuje mezi pˇeti a sedmnácti procenty, pˇriˇcemˇz lepˇs´ıch v´ ysledk˚ u dosahovali poˇcetnˇejˇs´ı komise. Pouˇzit´ım komise s lich´ ym poˇctem klasifikátor˚ u je tedy moˇzné dosáhnout urˇcité u ´spory ˇcasu a také zlepˇsen´ı pˇresnosti klasifikace. D˚ uvodem je porovnáván´ı neznámého dokumentu s vˇetˇs´ım poˇctem soused˚ u, neˇz je tomu u samostatného klasifikátoru. 4.4.4

Shrnut´ı v´ ysledk˚ u

Na základˇe z´ıskan´ ych v´ ysledk˚ u je moˇzné odvodit urˇcité závˇery o moˇznosti paralelizace zpracován´ı rozsáhl´ ych kolekc´ı textov´ ych dokument˚ u. Rozdelˇen´ım zpracovávané kolekce dokument˚ u na nˇekolik menˇs´ıch disjunktn´ıch mnoˇzin je moˇzné dosáhnout v´ yrazného sn´ıˇzen´ı ˇcasové nároˇcnosti, a to s velice mal´ ym sn´ıˇzen´ım schopnosti klasifikátoru správnˇe klasifikovat neznámé dokumenty. V´ yjimku tvoˇr´ı metoda nejbliˇzˇs´ıho souseda, u které bylo vypozorováno i m´ırné zv´ yˇsen´ı pˇresnosti, avˇsak stanoven´ı

4.4

Experimenty

64

konkrétn´ıho trendu ˇcasové u ´spory nen´ı jednoznaˇcné. Z experimentu s rozsáhlejˇs´ı trénovac´ı mnoˇzinou je vidˇet rostouc´ı u ´spora se zvyˇsuj´ıc´ım se poˇctem ˇclen˚ u komise, avˇsak tento závˇer naruˇsuje komise s deseti ˇcleny, kdy doˇslo naopak ke zv´ yˇsen´ı ˇcasu. U metody nejbliˇzˇs´ıho souseda byl také nejv´ıce patrn´ y negativn´ı dopad sudého poˇctu klasifikátor˚ u, kter´ y m˚ uˇze m´ıt za následek zhorˇsen´ı pˇresnosti kv˚ uli neklasifikovan´ ym dokument˚ um. Nejv´ yraznˇejˇs´ı ˇcasové u ´spory je moˇzné dosáhnout s neuronov´ ymi s´ıtˇemi, u kter´ ych má d´ıky velké ˇcasové nároˇcnosti roustouc´ı s poˇctem zpracovávan´ ych dat paraleln´ı zpracován´ı nejvˇetˇs´ı v´ yznam. Pro zjiˇstˇen´ı vlivu r˚ uzn´ ych parametr˚ u na v´ ysledky z´ıskané pˇri paraleln´ım zpracován´ı textov´ ych dat byly také realizovány experimenty s rozd´ıln´ ym nastaven´ım. Z ˇcasového hlediska byla pouˇzita pouze trénovac´ı mnoˇzina o 100 000 dokumentech. U neuronov´ ych s´ıt´ı byla zjednoduˇsena architektura a sn´ıˇzena poˇzadovaná chyba, u podp˚ urn´ ych vektor˚ u zmˇenˇena jádrová funkce na radiáln´ı a u nejbliˇzˇs´ıho souseda byl zv´ yˇsen poˇcet soused˚ u. Dosaˇzené v´ ysledky jsou velice podobné a obecn´ y trend ve sn´ıˇzen´ı ˇcasové nároˇcnosti se zanedbateln´ ym sn´ıˇzen´ım pˇresnosti plat´ı pro neuronové s´ıtˇe i podp˚ urné vektory. U nejbliˇzˇs´ıho souseda bylo dosaˇzeno také podobn´ ych v´ ysledk˚ u v podobˇe zv´ yˇsen´ı pˇresnosti pˇri pouˇzit´ı lichého poˇctu klasifikátor˚ u, ale nev´ yrazná ˇcasová u ´spora byla sp´ıˇse náhodná.

5

DISKUZE

5

65

Diskuze

V této diplomové práci bylo snahou prozkoumat moˇznosti paralelizovaného pˇr´ıstupu k dolován´ı znalost´ı z rozsáhl´ ych kolekc´ı textov´ ych dokument˚ u, které jsou pro své typické vlastnosti velice ˇcasovˇe i prostorovˇe nároˇcné na zpracován´ı. Z´ıskané v´ ysledky ukázaly, ˇze rozdˇelen´ım problému na nˇekolik menˇs´ıch d´ılˇc´ıch problém˚ u je moˇzné dosáhnout sn´ıˇzen´ı ˇcasové nároˇcnosti a neutrpˇet v´ yrazné sn´ıˇzen´ı pˇresnosti klasifikace. V´ yjimkou je algoritmus nejbliˇzˇs´ıho souseda, u kterého ke sn´ıˇzen´ı ˇcasu docházelo sp´ıˇse náhodnˇe, ale pokud byl poˇcet klasifikátor˚ u lich´ y, bylo moˇzné zv´ yˇsit celkovou pˇresnost. Rozhoduj´ıc´ım faktorem je velikost komise klasifikátor˚ u, která s vyˇsˇs´ım poˇctem ˇclen˚ u umoˇzn ˇuje vyˇsˇs´ı sn´ıˇzen´ı ˇcasové nároˇcnosti, pˇriˇcemˇz rozd´ıly v pˇresnosti byly vˇetˇsinou velice malé. V´ yhodnˇejˇs´ı je tedy pouˇzit´ı vyˇsˇs´ıho poˇctu klasifikátor˚ u, pokud moˇzno lichého poˇctu, aby nedocházelo k nerozhodnosti hlas˚ u komise pˇri klasifikaci neznámého dokumentu.

5.1

Nedostatky implementace

Nejvˇetˇs´ım nedostatkem je souˇcasná podoba objektového návrhu aplikace, kter´ y pouˇz´ıvá menˇs´ı mnoˇzstv´ı tˇr´ıd obsahuj´ıc´ı funkcionality, které by bylo moˇzné vyˇclenit a z´ıskat t´ım ˇcistˇs´ı návrh. Pokud by tedy aplikace mˇela slouˇzit jako podklad pro dalˇs´ı v´ yzkum nebo i praktické vyuˇzit´ı, bylo by velice vhodné provést refaktoring. Urˇcit´ ym nedostatkem m˚ uˇze b´ yt také vlastn´ı implementace algoritmu nejbliˇzˇs´ıho souseda a KD strom˚ u, které nebyly ovˇeˇreny vˇetˇs´ım mnoˇzstv´ım uˇzivatel˚ u, jako tomu b´ yvá u volnˇe dostupn´ ych knihoven.

5.2

Moˇ znosti nav´ az´ an´ı na pr´ aci

Práce se dané problematice vˇenuje jeˇstˇe na pomˇernˇe obecné u ´rovni a zkoumán byl pˇredevˇs´ım vliv paralelizace na r˚ uzné algoritmy. Moˇznost´ı, jak dále pˇristoupit k tomuto problému, je nˇekolik. Jednak by bylo vhodné pouˇz´ıt jin´ y typ textov´ ych dat, kter´ y by mˇel rozd´ılné charakteristiky, a porovnat z´ıskané v´ ysledky. Vliv parametrizace jednotliv´ ych algoritm˚ u byl v této práci také zahrnut, avˇsak z ˇcasov´ ych d˚ uvod˚ u bylo provedeno pouze malé mnoˇzstv´ı experiment˚ u s r˚ uzn´ ym nastaven´ım a vyvozené závˇery tedy nemus´ı m´ıt dostateˇcnou podporu v empirick´ ych datech.

5.3

Moˇ znosti vyuˇ zit´ı v praxi

D´ıky rozsáhl´ ym u ´sporám v ˇcase potˇrebném pro nauˇcen´ı klasifikátoru by mˇelo b´ yt moˇzné podobn´ y pˇr´ıstup vyuˇz´ıt pro zpracován´ı velice rozsáhl´ ych kolekc´ı textov´ ych dokument˚ u, a to i na bˇeˇzném domác´ım poˇc´ıtaˇci. V akademické a firemn´ı sféˇre je takto moˇzné uˇsetˇrit v´ yrazn´ ym zp˚ usobem v´ ypoˇcetn´ı prostˇredky pˇri nároˇcn´ ych v´ ypoˇctech spojen´ ych se zpracován´ım velkého mnoˇzstv´ı textov´ ych dat.

6

6

´ ER ˇ ZAV

66

Z´ avˇ er

C´ılem této diplomové práce bylo prozkoumat moˇznost aplikován´ı paraleln´ıho pˇr´ıstupu pˇri dolován´ı znalost´ı z textov´ ych dat. Práce se zamˇeˇrila pˇredevˇs´ım na rozd´ılnost ve v´ ysledc´ıch pro tˇri r˚ uzné klasifikaˇcn´ı algoritmy, a to neuronov´ ymi s´ıtˇemi, podp˚ urn´ ymi vektory a metodou nejbliˇzˇs´ıho souseda. Pˇri zpracován´ı práce byla nastudována problematika pˇredzpracován´ı textov´ ych dokument˚ u a jejich transformace do vektorové reprezentace, zp˚ usob fungován´ı klasifikátor˚ u pouˇz´ıvan´ ych pˇri práci s textov´ ymi daty a jiˇz dosaˇzné v´ ysledky v oblasti paralelizace tohoto typu problému. V práci samotné je popsána znaˇcná ˇcást teorie spojené se zpracován´ım textov´ ych dokument˚ u a jejich pˇr´ıpravou pro algoritmy strojového uˇcen´ı, stejnˇe tak i princip tˇechto algoritm˚ u a krátké shrnut´ı dosavadn´ıch poznatk˚ u paralelizován´ı zpracován´ı textov´ ych dat. Jako jeden z v´ ystup˚ u, nikoliv vˇsak hlavn´ı, byla vytvoˇrena aplikace pro realizaci experiment˚ u. Jedn´ım z hlavn´ıch problém˚ u pˇri implementaci byla prostorová ˇ nároˇcnost zpracován´ı textov´ ych dat. Reˇsen´ım byla u ´prava vybran´ ych knihoven tak, aby byly schopné pracovat s ˇr´ıdk´ ymi vektory, d´ıky kter´ ym bylo dosaˇzeno enormn´ıho sn´ıˇzen´ı poˇzadvaku na pamˇet’ové vybaven´ı poˇc´ıtaˇce, a experimenty tak mohly b´ yt realizovány i na bˇeˇzném domác´ım poˇc´ıtaˇci. Provedené u ´pravy by tedy bylo moˇzné dále vyuˇz´ıt pˇri jakékoliv u ´loze t´ ykaj´ıc´ı se klasifikace velkého mnoˇzstv´ı textov´ ych dat. Hlavn´ım v´ ystupem jsou v´ ysledky samotn´ ych experiment˚ u, které mˇely za u ´kol odhalit vliv paralelizace na u ´ˇspˇeˇsnost a nároˇcnost tvorby jednotliv´ ych klasifikátor˚ u. Snahou bylo rozˇs´ıˇrit poznatky a nast´ınit tak dalˇs´ı moˇznosti smˇerován´ı v´ yzkumného snaˇzen´ı v této oblasti.

A

A

ˇ ıLOHA 1 PR´

67

Pˇr´ıloha 1

Zdrojové kódy aplikace spolu s v´ ysledky experiment˚ u jsou k dispozici na pˇriloˇzeném DVD.

B

B

LITERATURA

68

Literatura

AI Basics John McCarthy Artificial intelligence: Manufactured Minds [online]. [cit. 2013-04-13]. Dostupné z WWW: http://library.thinkquest.org/05aug/01158/mccarthy.html. Banko, M., Brill, E. Scaling to Very Very Large Corpora for Natural Language Disambiguation Proceedings of the 39th Annual Meeting on Association for Computational Linguistics – ACL ’01 [online]. 2001, s. 26–33 [cit. 2013-05-03]. Dostupné z: doi:10.3115/1073012.1073017 . Cardoso-Cachopo, A. Datasets for single-label text categorization [online]. 2007 [cit. 2013-05-11]. Dostupné z WWW: http://web.ist.utl.pt/acardoso/datasets/. ˇena, F. Mysl´ıme v jazyku Perl Vyd. 1. Praha: Grada, 2005, 700 s. ISBN 80Dar 247-1147-8. ˇena, F. Vybrané pˇr´ıstupy k dolován´ı znalost´ı ze sociáln´ıch médi´ı 2011. HabiDar litaˇcn´ı práce. Mendelova univerzita v Brnˇe. Fung, P., Kan, M., Horita, Y. Extracting Japanese Domain and Technical Terms is Relatively Easy Computer Science Deparment, Columbia University, New York, 1996. Dostupné z: doi:10.1.1.151.278. Joachims, T. Text Categorization with Support Vector Machines: Learning with Many Relevant Features Proceeding of the European Conference on Machine Learning, Springer, 1998. Kernighan, M., Church, K., Gale, W. A spelling correction program based on a noisy channel model In Proc. ACL, 1990, s. 205–210. Konchady, M. Text Mining Application Programming Boston: Charles River Media, 2006, xix, 412 s. ISBN 978-1-58450-460-3. ˇ ny ´ , V., Trenz O. Umˇelá inteligence Brno: 2010. 120 s. Konec Koza, J. Genetic programming: A paradigm for genetically breeding populations of computer programs to solve problems Computer Science Department, Standford University [online]. 1990 [cit. 2013-04-13]. Dostupné z WWW: http://www.genetic-programming.com/jkpdf/tr1314.pdf. Lertnattee, V., Theeramunkong, T. Parallel text categorization for multidimensional data Lecture Notes in Computer Science, Vol. 3320, 2004, s. 38–41. Lewis, D. Reuters-21578 Text Categorization Test Collection [online]. 2007 [cit. 2013-05-11]. Dostupné z WWW: http://daviddlewis.com/resources/testcollections/reuters21578. ¨ tze, H. Introduction to Information Retrieval Manning, C., Raghavan, P., Schu Cambridge University Press, 2008.

B

LITERATURA

69

Neto, J., Santos, A., Kaestner, C., Freitas, A. Document Clustering and Text Summarization Pontificia Universidade Catolica do Parana, 2000. Dostupné z: doi:10.1.1.43.4634. Ng, A. Machine Learning Coursera [online]. Stanford University, [cit. 2013-05-03]. Dostupné z WWW: https://www.coursera.org/course/ml. ´ k, Z., Dar ˇena, F. Aplikace pro pˇr´ıpravu textových dat [CD-ROM]. In PEFNova net 2012. ISBN 978-80-7375-669-7. Porter, M. An algorithm for suffix stripping Program, 14(3), s. 130–137, 1980. Rennie, J. 20 Newsgroups [online]. 2008 [cit. 2013-05-11]. Dostupné z WWW: http://qwone.com/~jason/20Newsgroups/. Rosenblatt, F. The Perceptron–a perceiving and recognizing automation Report 85-460-1, Cornell Aeronautical Laboratory, 1957. Russel, S., Norvig, P. Artificial intelligence: A modern approach Englewood Cliffs, N.J.: Prentice Hall, 1995, xxviii, 932 s. ISBN 01-310-3805-2. Salton, G., Wong, A., Yang, C. A Vector Space Model for Automatic Indexing Communications of the ACM 18, 11 (November 1975), s. 613–620. Dostupné z: doi:10.1145/361219.361220. Sebastiani, F. Text categorization Text Mining and its Applications to Intelligence, CRM and Knowldge, WIT Press. 2005, s. 109–129. Singhal, A. Term weighting revisited [online]. 1997 [cit. 2013-05-10]. Disertaˇcn´ı práce. Cornell University. Dostupné z WWW: http://ecommons.cornell.edu/bitstream/1813/7281/1/97-1626.pdf. ˇ´ıma, J., Neruda, R. Teoretické otázky neuronových s´ıt´ı Praha: Matfyzpress, S 1996, 390 s. ISBN 80-858-6318-9. Text Mining Science Text Mining for Science [online]. 2012 [cit. 2013-04-16]. Dostupné z WWW: http://textminingscience.com/pages/text-mining-science. Turing, A. Computing machinery and intelligence [online]. [cit. 2013-04-13]. Dostupné z WWW: http://www.loebner.net/Prizef/TuringArticle.html. Turney, P., Pantel, P. From Frequency to Meaning: Vector Space Models of Semantics Journal of Artificial Intelligence Research 37, 2010, s. 141–188. Ulmer, C., Gokhale, M., Gallagher, B., Top, P., Eliassi-Rad, T. Massively parallel acceleration of a document-similarity classifier to detect web attacks Journal of Parallel and Distrubuted Computing, Vol. 71, No. 2, 2011, s. 225–235. Vapnik, V. The Nature of Statistical Learning Theory Springer, 1995.

B

LITERATURA

70

Wang, Y., Zhang, J., Vassileva, J. Towards Effective Recommendation of Social Data across Social Networking Sites In: Dicheva, D., Dochev, D. (eds.) Artificial Intelligence: Methodology, Systems, and Applications. Springer, 2010, s. 61–70. Weiss, S., Indurkhya, N., Zhang, T., Damerau, F. Text Mining: Predictive Methods for Analyzing Unstructured Information New York, Springer, 2010. ISBN 978-1-44192996-9. Weizenbaum, J. ELIZA—a computer program for the study of natural language communication between man and machine Communications of the ACM, v.9 n.1, p.36–45. Dostupné z: doi:10.1145/365153.365168. Whitby, B. Reflections on artificial intelligence Exeter: Intellect, 1996. ISBN 18715-1668-4. Witten, I., Eibe, F. Data Mining: Practical Machine Learning Tools and Techniques 2nd ed. Amsterdam: Morgan Kaufman, 2005. ISBN 978-008-0477-022. Zhang, Y., Jin, R., Zhou, Z. Understanding bag-of-words model: a statictical framework 2010. s. 43–52. Dostupné z: doi:10.1007/s13042-010-0001-0. ˇˇ ˇena F. Automatic Sentiment Analysis Using the Textual Pattern Zi zka, J., Dar Content Similarity in Natural Language Lecture Notes in Artificial Intelligence, 2010, 6231, 1: 224–231. ISSN 0302-9743. ˇˇ ˇena F. Parallel Processing of Very Many Textual Customers’ ReZi zka J., Dar views Freely Written Down in Natural Languages In IMMM 2012: The Second International Conference on Advances in Information Mining and Management. 2012, s. 147–153. ISBN 978-1-61208-227-1.

znalostí z textových dat

Recommend Documents