Částečně řízené učení algoritmů strojového učení (semi-supervised learning)

Mendelova univerzita v Brně Provozně ekonomická fakulta

Částečně řízené učení algoritmů strojového učení (semi-supervised learning) Diplomová práce

Vedoucí práce: doc. Ing. Jan Žižka, CSc.

Bc. Karel Burda

2014

Zde se nachází originální zadání práce.

Na tomto místě bych rád poděkoval především svému vedoucímu práce, panu doc. Ing. Janu Žižkovi, CSc., za vedení práce, cenné rady a vstřícný přístup během celé tvorby diplomové práce.

Čestné prohlášení Prohlašuji, že jsem tuto práci: Částečně řízené učení algoritmů strojového učení (semi-supervised learning) vypracoval samostatně a veškeré použité prameny a informace jsou uvedeny v seznamu použité literatury. Souhlasím, aby moje práce byla zveřejněna v souladu s § 47b zákona č. 111/1998 Sb., o vysokých školách ve znění pozdějších předpisů, a v souladu s platnou Směrnicí o zveřejňování vysokoškolských závěrečných prací. Jsem si vědom, že se na moji práci vztahuje zákon č. 121/2000 Sb., autorský zákon, a že Mendelova univerzita v Brně má právo na uzavření licenční smlouvy a užití této práce jako školního díla podle § 60 odst. 1 Autorského zákona. Dále se zavazuji, že před sepsáním licenční smlouvy o využití díla jinou osobou (subjektem) si vyžádám písemné stanovisko univerzity o tom, že předmětná licenční smlouva není v rozporu s oprávněnými zájmy univerzity, a zavazuji se uhradit případný příspěvek na úhradu nákladů spojených se vznikem díla, a to až do jejich skutečné výše.

V Brně dne 21. května 2014

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

6

Abstract Burda, K. Semi-supervised Machine Learning Algorithms. Master Thesis. Brno 2014. The final thesis summarizes in its theoretical part basic knowledge of machine learning algorithms that involves supervised, semi-supervised, and unsupervised learning. Experiments with textual data in natural spoken language involving different machine learning methods and parameterization are carried out in its practical part. Conclusions made in the thesis may be of use to individuals that are at least slightly interested in this domain.

Abstrakt Burda, K. Částečně řízené učení algoritmů strojového učení (semi-supervised learning). Diplomová práce. Brno 2014. Závěrečná práce shrnuje v teoretickém aparátu základní poznatky o strojovém učení, které zahrnuje řízené, částečně řízené a neřízené učení. V praktické části jsou provedeny experimenty týkající se metod strojového učení na textových datech v přirozeném jazyce, jež jsou pořízeny z prostředí Internetu. Závěry vyvozené v práci mohou posloužit všem osobám, které se o problematiku a oblast strojového učení alespoň částečně zajímají.

7

OBSAH

Obsah 1 Úvod a cíl práce 1.1 Úvodní slovo . 1.2 Záměr práce . . 1.3 Struktura práce 1.4 Historie . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

2 Teoretický aparát 2.1 Úvod do problematiky . . . . . . . 2.2 Řízené učení . . . . . . . . . . . . . 2.3 Částečně řízené učení . . . . . . . . 2.4 Neřízené učení . . . . . . . . . . . . 2.5 Termy . . . . . . . . . . . . . . . . 2.6 Reprezentace textových dokumentů 2.7 Rozhodovací strom . . . . . . . . . 2.8 Podobnost textových dokumentů . 2.9 Shlukovací algoritmy . . . . . . . . 2.10 Kriteriální funkce . . . . . . . . . . 2.11 Klasifikační algoritmy . . . . . . . 2.12 Normalizační algoritmy . . . . . . . 2.13 Evaluační metriky strojového učení 2.14 Kolekce dat . . . . . . . . . . . . .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

. . . .

12 12 13 14 15

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

17 17 18 18 21 23 25 29 32 35 38 38 49 50 52

3 Analýza současného stavu 53 3.1 Aktuální dostupné nástroje . . . . . . . . . . . . . . . . . . . . . . . 53 4 Zdrojová data 4.1 Použitá data

57 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5 Metodika řešení 5.1 Postup . . . . . . . . . . . 5.2 Zvolené množiny dat . . . 5.3 Proces řízeného a částečně 5.4 Neřízené učení . . . . . . . 5.5 Použité technologie . . . .

. . . . . . . . . . řízeného . . . . . . . . . .

. . . . . . . . učení . . . . . . . . .

6 Výsledky a diskuse 6.1 Značení . . . . . . . . . . . . . . . . 6.2 Srovnání parametrizací v rámci SSL . 6.3 Srovnání metod strojového učení . . 6.4 Implementovaný programový systém 6.5 Diskuse . . . . . . . . . . . . . . . . 6.6 Návrh dalšího postupu . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . .

60 60 62 65 66 68

. . . . . .

70 70 72 74 80 82 83

OBSAH

8

7 Závěr 84 7.1 Zhodnocení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 8 Literatura

85

Přílohy

91

A Zjednodušený diagram tříd programového systému

92

B Metriky kódu

93

C Parametrizační soubor přiloženého programového systému

94

D Ukázka výstupu programového nástroje

95

E Ukázka zdrojové kódu

96

F Zdrojový kód skriptu extract.pl

97

G Zdrojový kód skriptu svm_prepare.pl

99

H Zdrojový kód skriptu transform.pl

104

9

SEZNAM OBRÁZKŮ

Seznam obrázků 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Rozdělení strojového učení . . . . . . . . . . . . . . . . . . . . . . . Rozdělení shlukování do kategorií . . . . . . . . . . . . . . . . . . . Příklad rozhodovacího stromu . . . . . . . . . . . . . . . . . . . . . Kosinus dvou normalizovaných vektorů jakožto měřítko podobnosti ve dvourozměrném prostoru . . . . . . . . . . . . . . . . . . . . . . Euklidovská vzdálenost mezi dvěma vektory . . . . . . . . . . . . . Dendrogram znázorňující postup hierarchického shlukování . . . . . Algoritmus k-means, pohyb středů . . . . . . . . . . . . . . . . . . Metoda k–nejbližších sousedů . . . . . . . . . . . . . . . . . . . . . Znázornění Support Vector Machines . . . . . . . . . . . . . . . . . Model umělého neuronu – perceptronu . . . . . . . . . . . . . . . . Grafická reprezentace umělé neuronové sítě . . . . . . . . . . . . . . Průměrná Accuracy pro „60 (50,50) : 823 (77,23)” . . . . . . . . . . . Průměrná Accuracy pro „80 (50,50) : 1002 (57,43)” . . . . . . . . . . Průměrná Accuracy pro „500 (50,50) : 11632 (74,26)” . . . . . . . . . Průměrná Accuracy pro „500 (50,50) : 32191 (74,26)” . . . . . . . . . Schéma funkcionality programového systému . . . . . . . . . . . . . Zjednodušený diagram tříd programového systému . . . . . . . . .

. 17 . 23 . 30 . . . . . . . . . . . . . .

33 34 35 37 44 45 46 47 75 76 77 78 81 92

SEZNAM TABULEK

10

Seznam tabulek Tabulka 1: Příklad matice document-term

27

Tabulka 2: Zdrojová trénovací množina pro rozhodovací strom

30

Tabulka 3: Zdrojová tabulka pro modelový příklad algoritmu NB

40

Tabulka 4: Zdrojová tabulka s vlastnostmi textů pro modelový příklad metody NB 40 Tabulka 5: Pravděpodobnosti příslušnosti pro modelový příklad metody NB 41 Tabulka 6: Zdrojová tabulka pro modelový příklad algoritmu MNB

42

Tabulka 7: Zdrojová tabulka popisující slova a jejich vlastnosti v příkladě 42 Tabulka 8: Příklad trénovacích dat algoritmu C4.5

48

Tabulka 9: Statistické informace pro příspěvky ze skupiny positivních ohlasů 58 Tabulka 10: Statistické informace pro negativní příspěvky

58

Tabulka 11: Použité poměry počtu dokumentů pro učící algoritmy

62

Tabulka 12: Accuracy pro modelový případ „100 (50,50) : 1000 (70,30)” 71 Tabulka 13: Výsledky parametrizací algoritmu Self-training pro případ „60 (50,50) : 823 (77,23)” 72 Tabulka 14: Metrika Accuracy pro případ „60 (50,50) : 823 (77,23)”

75

Tabulka 15: Metrika Accuracy pro případ „80 (50,50) : 1002 (57,43)”

76

Tabulka 16: Metrika Accuracy pro případ „500 (50,50) : 11632 (74,26)” 77 Tabulka 17: Metrika Accuracy pro případ „500 (50,50) : 32191 (74,26)” 78 Tabulka 18: Okamžitá Accuracy algoritmu Self-training v jednotlivých iteracích pro případ „60 (50,50) : 823 (77,23)” 80 Tabulka 19: Metriky kódu

93

SEZNAM ZKRATEK A PŘELOŽENÝCH POJMŮ

11

Seznam zkratek a přeložených pojmů ARFF Attribute-Relation File Format, typ textového souboru CSV Comma Separated Values, typ textového souboru EM Expectation-Maximization, algoritmus strojového učení kNN k–Nearest Neighbors, algoritmus k–nejbližších sousedů Machine Learning Strojové učení MNB Multinomiální Naivní Bayes, klasifikační algoritmus NB Naivní Bayes, klasifikační algoritmus OOP Object-oriented Programming, objektově orientované programování SSL Semi-supervised Learning, částečně řízené strojové učení Supervised learning Řízené učení, učení s učitelem SVM Support Vector Machines, algoritmus strojového učení Unsupervised learning Neřízené učení, učení bez učitele, nejčastěji shlukování VSM Vector Space Model, model reprezentace objektu

1

ÚVOD A CÍL PRÁCE

1 1.1

12

Úvod a cíl práce Úvodní slovo

Diplomová práce se zabývá algoritmy strojového učení s využitím množství dílčích algoritmů aplikovaných na textová data v přirozeném jazyce. Závěrečná práce pracuje s algoritmy řízeného, částečně řízeného a neřízeného učení. Strojové učení citelně pomáhá v oblasti dolování z textových dat (anglicky Text Mining, Text Data Mining), kde by člověk nebyl schopen zpracování velkého množství údajů nebo získání samotné informace ze zdrojových dat. Dolování z textových dat, neboli také získávání dat z textových databází je v obecné rovině proces extrakce relevantních a ne-triviálních vzorů nebo znalostí z nestrukturovaných textových dat či dokumentů. Jedná se ve své podstatě o rozšíření obecnějšího dolování z dat nebo získávání znalostí ze strukturovaných databází (Chapelle, Schölkopf, Zien, 2006). Protože nejpřirozenější (a jednou z nejstarších forem) uchovávání informace je text, dolování z textových dat má velmi vysoký potenciál a uplatnění v komerční soukromé sféře. Studie z několika posledních let ukazují, že přibližně 80 % firemních informací (nebo informací, jež firma vlastní) je uloženo v textové podobě (Chapelle, Schölkopf, Zien, 2006). Je faktem, že dolování z textových dat je obecně náročnějším úkolem než obecné dolování z dat. Je to především způsobeno nestrukturovaným, neurčitým a obecně nepříliš exaktním charakterem textové informace či textových údajů obecně. Dolování z textových dat je také multidisciplinárním oborem, který zahrnuje teorii informace, získávání informace, textovou analýzu, extrakci dat, shlukování, kategorizaci, vizualizaci, databázové systémy, strojové učení a dolování z dat (Abney, 2008). Shlukování textů, nebo-li anglicky text clustering je poměrně nový vědní, převážně informatický obor. Jak již napovídá název, principem je shlukování textů do určitých skupin (shluků – clusterů), kde tyto texty sdílejí určité společné znaky. Shlukování je typickým zástupcem algoritmů neřízeného učení, neboli učení bez učitele. Od neřízeného učení se liší částečně řízené učení. Zájem o částečně řízené učení se objevil prakticky ihned poté, co se dostaly metody strojového učení na textových datech do širšího povědomí na konci 80. a začátkem 90. let. Hybnou sílou pro rozvoj částečně řízených učících algoritmů byly lingvistické aplikace – především klasifikace textových dat a extrakce informace, které podnítili zájem badatelů v oblasti strojového učení. Statistické metody, jež kombinují zařazená (označená) a nezařazená (neoznačená) data se však datují již do 60. let, avšak zvláště v posledních několika letech se dočkávají mohutného rozvoje. Právě tento překotný vývoj posledních let v této oblasti přispěl k tomu, že mnoho badatelů a zájemců o oblast strojového učení začalo s algoritmy částečně řízeného učení takříkajíc ztrácet krok.

1.2

Záměr práce

13

Důležitým faktem je to, že částečně řízené učení není vůbec omezeno jen na textová data. Jedná se o problematiku, která je stejně jako obecné strojové učení, aplikovatelná na mnoho odvětví. V současné době bylo částečně řízené učení úspěšně aplikováno v oborech jako je zpracování obrazu, bioinformatika, třídění a klasifikace dat, hodnocení bezpečnosti a mnoho dalších (Abney, 2008). Použití v jiných oborech není ničím omezeno, jen vůlí a představivostí. Pochopení principu oblasti částečně řízeného učení není možné bez nezbytného teoretického základu řízeného učení, potažmo obecnějšího dolování z textových dat, na kterém částečně řízené učení stojí. Z tohoto důvodu je v diplomové práci věnována velká část teoretickému základu počínaje reprezentací textových dat, základním popisem fungování algoritmů dolování z dat, metod třídění dokumentů, metrik účinnosti učícího procesu a dalších relevantních informací. Jak již bylo řečeno výše, částečně řízené učení prodělává v posledních letech nejmohutnější vývoj a pro mnohé výzkumníky se jedná o novou vzrušující oblast. V podstatě má hodně společného s postupy, jak provádět inferenci z dostupných dat. Klasická a velmi častá situace je taková, že je v jeden časový okamžik k dispozici pouze několik trénovacích (zařazených) bodů (příkladů), ale mnohem mohutnější množství neoznačených či nezařazených. V mnoha případech je také velmi nákladné nebo velmi složité získat určitá korektně označená data (například automatická klasifikace webových stránek) (Chapelle, Schölkopf, Zien, 2006). Částečně řízené učení proto využívá rozličné množství různých nástrojů a ilustruje, v menším rozsahu, sofistikované metody a algoritmy vyvinuté v jiných odvětvích, než je informatické strojové učení – ve statistice, matematice, anebo obecně informatice. Autor práce se taktéž podílel na odborných článcích především z oblasti neřízeného učení jako je „Grouping of Customer Opinions Written in Natural Language Using Unsupervised Machine Learning” (Dařena, Žižka, Burda, 2012), „Mining Opinion-Clusters from Very Large Unstructured Real-World Textual Data” (Žižka, Burda, Dařena, 2012) nebo „Clustering a Very Large Number of Textual Unstructured Customers’ Reviews in English” (Žižka, Burda, Dařena, 2012). Výzkum a zkušenosti získané ze zmíněných publikací jistojistě přispěly k samotné diplomové práci, i když byly zaměřené především na oblast neřízených algoritmů strojového učení.

1.2

Záměr práce

Diplomová práce je experimentálního rázu, jsou zde empiricky vyhodnoceny metody strojového učení na konkrétních datech. Cíle práce zahrnují: • seznámení se s algoritmy částečně řízeného strojového učení, • výběr vhodných rozsáhlých textových dat v přirozeném jazyce, • provedení série experimentů s textovými daty za použití klasifikace, shlukování a částečně řízeného učení,

1.3

Struktura práce

14

• formulaci a interpretaci výsledků. Teoretický základ má v závěrečné práci poměrně silné zastoupení. Dosažené výsledky diplomové práce jsou podrobeny analýze a diskusi. V neposlední řadě je nutné analyzovat současný stav v dané problematice, ten je v práci také stručně popsán a vyhodnocen. Záměrem diplomové práce je ale především porovnání výše zmíněných metod strojového učení na textových datech. Klade si za cíl interpretovat dosažené výsledky a zjistit důležité poznatky, které by mohly vést k úspěšnému cíli i v kontextu jiných reálných (ne nutně textových) dat. Na cestě k naplnění cíle si autor kladl za úkol provést množství podpůrných operací zahrnující extrakci, či jinou transformaci zdrojových dat. Tyto operace jsou zajištěny dílčími pomocnými skripty, jež samozřejmě také snad přijdou k užitku budoucím studentům nebo badatelům. Autorův další záměr zněl, aby sekundárním výstupem diplomové byl také programový nástroj, jež by také implementoval autor práce, a v tomto nástroji byly provedeny experimenty se zdrojovými daty. Diplomová práce s potřebným aparátem byla od začátku tvořena autorem s vizí, že práce najde svoje praktické využití v budoucnosti, ať už v akademické nebo soukromé sféře. Technologický aparát práce, který tvoří podpůrné skripty, přiložený programový systém a další sounáležitosti, je proto alespoň základně zdokumentován a popsán. Diplomová práce snad poslouží i budoucím studentům zajímající se o oblast strojového učení, a možná jim i usnadní některé dílčí kroky vedoucí k cíli jejich snažení, lhostejno, zda pouze s přípravou dat či celým procesem. Detailní popis implementovaného programového systému je však již nad rámec závěrečné práce, která by tak již citelně překročila zadaný rozsah.

1.3

Struktura práce

Tato kapitola představuje úvod k diplomové práci a stanovuje záměr odborné práce. V této části autor také popisuje, jakým způsobem se dostal do kontaktu s danou problematikou, resp. jak vznikla základní myšlenka a koncept. Následuje teoretická část, která představuje teoretický základ k metodám strojového učení, reprezentaci textových množin v přirozeném jazyce a konkrétním algoritmům. Metody strojového učení zahrnují řízené učení (supervised learning), částečně řízené učení (semi-supervised learning) a neřízené učení – nejčastěji shlukování (anglicky clustering). V teoretické části je provedena analýza současného stavu v této oblasti. Třetí stručná kapitola shrnuje současný stav problematiky a dostupné programové nástroje. Následující čtvrtá kapitola pak uvozuje a obecně popisuje použitá reálná zdrojová data v přirozeném jazyce, včetně představení konkrétních příkladů dat, kde se ozřejmuje charakter zvolených zdrojových dat.

1.4

Historie

15

Metodika řešení má vyhrazenou další samostatnou kapitolu, kde autor představuje metodický postup vedoucí k naplnění záměru diplomové práce. Především konkrétně popisuje sekvenci operací nutných k úspěšnému provedené experimentů (a vyhodnocení výsledků) se zdrojovými daty. Ve zmíněné kapitole se jedná především o podpůrné skripty (krátké programy) pro extrakci, transformaci a obecně přípravu dat včetně způsobu řešení a vyhodnocení. Výsledky a diskuse tvoří stěžejní kapitolou experimentálně zaměřené práce. Kapitola prezentuje výsledky experimentů, diskutuje je a vyvozuje z nich v kontextu zvolených textových dat závěry. V této časti je stručně představena architektura vytvořeného programového systému. Kapitola pokračuje shrnutím přínosů a poznatků diplomové práce. Druhou polovinu práce doplňuje kapitola Literatura, která uvádí seznam zdrojů a pramenů použitých v práci, kde jsou rovnocenně zastoupeny jak zdroje elektronické, tak klasické. Práci uzavírá množství příloh, což zahrnuje zdrojové kódy podpůrných skriptů, diagramy, návrhy, nákresy, atp.

1.4

Historie

K myšlence zabývat se problematikou strojového učení mě přivedl pan docent Jan Žižka, CSc. Oslovil mě na podzim roku 2011, zda bych se nechtěl podílet na výzkumu shlukování textů na Ústavu informatiky na Provozně ekonomické fakultě Mendelovy univerzity v Brně. Tato vědní oblast mě zaujala a pan docent mě podpořil odbornou literaturou a potřebným teoretickým základem k problematice. Krátce poté mi představil volně dostupný software pro shlukovací analýzu – Cluto – na který existovaly velice dobré reference. Na oblasti shlukování autor také založil bakalářskou práci (Burda, 2012). Téma autorovi bakalářské práce zní „Aplikace pokročilých shlukovacích metod na textová nestrukturovaná data v přirozeném jazyce”. Závěrečná práce je zaměřena experimentálně a empiricky, zabývá se shlukovacím procesem (shlukováním, angl. clustering) volně dostupných textových dat v přirozeném jazyce – konkrétně v anglickém jazyce. Veškeré experimenty v bakalářské práci jsou provedeny ve výše zmíněném programovém systému Cluto. Série experimentů je v bakalářské práci podrobena analýze a diskusi, je zjištěna optimální parametrizace shlukovacího procesu pro daná textová data. Tato parametrizace se projevila jako optimální i pro odlišnou množinu textových dat v přirozeném jazyce (Žižka, Burda, Dařena, 2012). Ukázalo se tedy, že závěry v práci vyvozené nejsou příliš úzce zaměřené pouze na konkrétní separátní množinu textů použitých v bakalářské práci, ale dají se aplikovat i na data podobného charakteru. Pokračováním v oblasti strojového učení pod panem docentem Žižkou bylo samozřejmým krokem a logickým vyústěním výše popsaných událostí. Proto začal autor na jaře roku 2013 pracovat na této diplomové práci, jež má za cíl otestovat

1.4

Historie

16

algoritmy částečně řízeného strojového učení a porovnat s ostatními význačnými metodami strojového učení. Důraz byl kladen na experimentální charakter práce a zúročení zkušeností s prací s rozsáhlými textovými daty v přirozeném jazyce. Zvláštní poděkování patří proto panu docentovi Janu Žižkovi, CSc., jež dokázal autora nadchnout pro problematiku strojového učení, objasnit veškeré autorovy nejasnosti a v neposlední řadě se zájmem, relevantními připomínkami a návrhy průběžně konzultovat dosažené dílčí výsledky.

2

17

TEORETICKÝ APARÁT

2 2.1

Teoretický aparát Úvod do problematiky

Strojové učení je de facto strojové získávání určitých informací z doménových dat. Formy strojového učení zahrnují tyto směry (Abney, 2008; Alpaydin, 2004): 1. řízené učení (anglicky supervised learning), 2. částečně řízené (semi-supervised learning), 3. neřízené (unsupervised). Metody strojového učení mohou být tedy znázorněny jednoduchým stromem takto: Strojové učení

Řízené

Částečně řízené

Neřízené

Obrázek 1: Rozdělení strojového učení Trénovací množina je konečná množina objektů, u nichž je známá třída, ke které dokumenty náleží – objekty, např. dokumenty, jsou zařazené a označené. Autor práce chápe testovací množinu jako konečnou množinu objektů, u nichž není známa příslušná třída a úkolem algoritmů strojového učení použitých v této práci je označit tyto objekty (v kontextu této práce dokumenty) – zařadit je nějakým způsobem do konečné množiny tříd. Induktivní učení reprezentuje formu strojového učení, kde lze z trénovací množiny odvodit pravidla, jež lze poté aplikovat na neznámá data. Mějme trénovací příklad (Zhu, Goldberg, 2009) {(xi , yj )}li=1 , {xj }l+u j=l+1

(1)

Induktivní učení se naučí funkci f : X 7→ Y , takže f by mělo dobře předpovídat nadcházející data, i za hranici {xj }l+u j=l+1 . Účinnost algoritmu je pak možno zjistit na separátní trénovací množině, např. objektu {(xk , yk )}m k=l , který není známý nebo dostupný při trénovacím procesu. Transduktivní strojové učení je forma učení, kdy se stroj naučí ze specifických (trénovacích) dat aplikací na specifická (testovací) data. Mějme stejný trénovací příklad jak je uvedený v rovnici 1. Transduktivní učení se naučí funkci f : X l+u 7→ Y l+u , takže f by mělo dobře předpovídat neoznačená (unlabeled) data, za {xj }l+u j=l+1 . Důležitý je fakt, že f je definováno jenom pro trénovací vzorek a nemusí provádět predikce mimo tento vzorek, jedná se tedy o jednodušší funkci, než při induktivním učení (Zhu, Goldberg, 2009).

2.2

Řízené učení

18

(Zhu, Goldberg, 2009) uvádí zajímavou analogii ve vztahu k induktivnímu a transduktivnímu učícímu procesu. Jádrem myšlenky je to, že induktivní učení se podobá zkoušce ve třídě, kde nejsou známy žádné možné otázky předem a student se musí připravit na všechny možné varianty. Naproti tomu transduktivní učení se podobá spíše zkoušce, kterou student vypracovává z domova, zná předem otázky a nemusí se připravovat na jiné varianty. Induktivní forma strojového učení je tedy proces, kdy stroj z vysledovaných trénovacích dat inferuje určitá obecná pravidla, která jsou potom aplikována na testovací případy. Nejpodstatnější rozdíl je tedy fakt, že transduktivní forma učení umí pracovat s označenými i neoznačenými daty, ale neporadí si na rozdíl od induktivního učení s daty, která algoritmus ještě nikdy neviděl (Yang, Zhu, 2013).

2.2

Řízené učení

Algoritmy řízeného učení (neboli učení s učitelem) jsou jednou z nejznámějších metod strojového učení a zahrnují metody klasifikace a regrese. Cílem klasifikace je zjistit (naučit se) předpis funkce f (x) jejíž hodnota je nominální – tedy z určité konečné množiny hodnot. Tato naučená funkce se nazývá klasifikátorem. Klasifikátoru je možno dát za vstup určitou instanci objektu x, který patří do určité třídy i z možných n tříd. Klasifikátor pak rozhodne, do které třídy instance objektu náleží; hodnota f (x) je de facto predikce klasifikátoru pro určitou třídu instance (Abney, 2008). Příkladem objevujícím se i v této práci je například dokument (tedy množina slov), který tvoří vstup do procesu učení a jako takový je předán klasifikátoru C, který vyhodnotí predikci, do jaké třídy dokument náleží, na základě svého funkčního předpisu f (x). Cílem regrese je také nalezení f (x), tato hodnota však není nominální, ale reálná – není spojitá nebo z určité konečné množiny hodnot. Klasickým výstupem regresního klasifikátoru mohou být hodnoty jako předpokládaná cena, metrická vzdálenost, atd. – reálné hodnoty, kde třídy nejsou diskrétní, nýbrž spojité.

2.3

Částečně řízené učení

Částečně řízené učení je de facto kombinací řízeného a neřízeného učení – stojí pomyslně na půli cesty. Tvorba, potažmo získání označených (anglicky labeled, zařazených) dat je činnost velice časově náročná. Získat samotná zdrojová data není ve většině úloh problémem, problémem je fakt, že expert v dané oblasti musí zařadit množinu vstupů nebo objektů (dokumentů) do korektních tříd. Z výše uvedeného popudu vznikla myšlenka využití nezařazených (anglicky unlabeled, neoznačených) dat. Jak již bylo vyřčeno, na rozdíl od neřízeného učení, částečně řízené učení využívá kombinaci označených a neoznačených množin.

2.3


19

V praxi bývá naprostá většina dat v částečně řízeném učícím procesu na počátku neoznačena, ale ona nepoměrně méně mohutná množina označených dat je nepostradatelná, protože poskytuje určitou obecnou charakterizaci zdrojových dat. V současné době existují dva hlavní směry či metody částečně řízeného učení učení: Self-training a Co-training. Self-training Self-training je metoda, která existovala již dříve, než vznikl samotný název částečně řízeného učení (anglicky pojem Semi-supervised learning), v oblasti výpočetní lingvistiky (Abney, 2008). Do vzniku pojmu částečně řízeného učení se však tento algoritmus netěšil velké známosti vědeckých pracovníků v oblasti strojového učení. Algoritmus Self-training je velice jednoduchý, a to je také jeden z důvodů jeho všeobecné oblíbenosti. Metoda se naučí z trénovacích dat a aplikuje naučený klasifikátor C konkrétní iterace j na neoznačená (testovací) data. Tam, kde si je klasifikátor Cj nejvíce jistý z pravděpodobnostního hlediska (hodnota překonala určitou hranici, anglicky threshold), zda určitý objekt o patří do třídy i, přidá tento objekt do trénovací (označené) množiny. Tímto krokem byla označená data expandována, algoritmus naučí nový klasifikátor Cj+1 z těchto expandovaných trénovacích dat. Proces iteruje tak dlouho, dokud není splněna určitá ukončující podmínka (anglicky stopping criterion). Algoritmus pracuje v základní formě schematicky následovně (Abney, 2008, str. 20): procedure S e l f T r a i n ( L0 ,U) L0 t v o r i o z n a c e n a data , U j s o u n e o z n a c e n a C := t r a i n ( L0 ) loop u n t i l n e n i s p l n e n a u k o n c u j i c i podminka L := L0 + s e l e c t ( l a b e l (U, C) ) C := t r a i n ( L ) end loop return C ; Funkce label aplikuje klasifikátor C na každou instanci z množiny U , pro každou dvojici jeden pár (y, s), kde y je označení (třída) a s je confidence score – pravděpodobnost příslušnosti do třídy y podle klasikifátoru C. Metoda select bere za vstup množinu pravděpodobnostní příslušnosti instancí do tříd a vybere pouze ty záznamy, kde je pravděpodobnostní příslušnost „dostatečně vysoká”. Výstupem funkce select je označená (labeled) množina, která má nižší mohutnost než vstupní množina (v extrémním případě stejnou). Metoda train reprezentuje konkrétní algoritmus strojového učení, který je v kontextu částečně řízeného učení nazýván anglicky jako base learner. Do tohoto vstupují

2.3


20

označená (angl. labeled) data a výstupem je klasifikátor s pravděpodobnostmi zařazení do diskrétních tříd. Proces trénování a učení trvá tak dlouho, dokud není splněna ukončující podmínka. Nejčastěji je postačující podmínkou fakt, že se v iteracích nějakým způsobem mění trénovací množina dat (Abney, 2008). Parametry a varianty Existuje samozřejmě široká škála parametrizace a variant tohoto algoritmu. Kardinálním je volba nově označených (labeled) dat: • využití okamžitého (anglicky intermediate) klasifikátoru, který vyprodukuje takzvaná hard-labeled data, • užití označených (labeled) dat, které označil klasifikátor, k natrénování vylepšeného klasifikátoru. Pojmem „hard-labeled” se rozumí to, že neoznačeným (unlabeled) instancím jsou přiřazeny konečné třídy (labels), v kontrastu s pravděpodobnostním rozložením, které je přítomné ve druhém případě. Diplomová práce zachovává ve své praktické části pravděpodobnostní rozložení. Parametrizace a varianty algoritmu ještě zahrnují volbu řízeného učícího algoritmu, způsob konečné podmínky (stopping criterion), určení hranice (threshold) a dalších. Co se týče základního učícího algoritmu (anglicky base learner), lze použít prakticky libovolný učící algoritmus z kontextu řízeného učení – ten bude pak implementovat schematickou funkci train (viz zápis algoritmu Self-training v části 2.3). Jedinou postačující podmínku je, aby klasifikátor algoritmu byl schopen dávat ve svém výstupu pravděpodobnost příslušnosti k existujícím třídám. Co-training Co-training je metoda, za jejímž zrodem stojí pánové Blum a Mitchell (Blum, Mitchell, 1998), vědci zabývající se oblastí strojového učení, zejména klasifikací. Schematicky je možno vyjádřit Co-training jako (Abney, 2008, str. 29):

2.4

Neřízené učení

21

procedure CoTrain ( L ,U) L0 t v o r i o z n a c e n a data , U j s o u n e o z n a c e n a P := nahodna s e l e k c e z U loop n e n i s p l n e n a u k o n c u j i c i podminka f1 := t r a i n ( view1 ( L ) ) f2 := t r a i n ( view2 ( L ) ) L := L + s e l e c t ( l a b e l (P , f1 ) ) + s e l e c t ( l a b e l (P , f2 ) ) Odstran o z n a c e n e i n s t a n c e z P a d o p l n P z U end loop view1 a view2 jsou různé pohledy na data, na kterých jsou natrénovány (metoda train) dva klasifikátory, resp. jejich funkční předpisy f1 a f2 . Co-training tedy vyžaduje dva pohledy na zdrojová data, přičemž každý jeden z nich musí být dostatečný, aby se klasifikátor byl schopen na datech uspokojivě natrénovat. Analogicky jako u Self-training, funkce label aplikuje klasifikátor c na každou instanci z množiny U , pro každou dvojici jeden pár (y, s), kde y je označení (třída) a s je confidence score – pravděpodobnost příslušnosti do třídy y podle klasikifátoru c. Metoda select bere za vstup množinu pravděpodobnostní příslušnosti instancí do tříd a vybere pouze ty záznamy, kde je pravděpodobnostní příslušnost „dostatečně vysoká” dle threshold. Výstupem funkce select je označená (labeled) množina, která má nižší mohutnost než vstupní množina (v extrémním případě stejnou). V reálném světě však dva disjunktní a přitom dostatečné pohledy často neexistují, Co-training tedy může nabývat mnoha variant jako je například (Wang, 2007): • umělé náhodné rozdělení trénovacích dat na dvě poloviny, • místo dvou různých pohledů využít dva různé klasifikátory, • využít jeden typ klasifikátoru s různou dvojí parametrizací, • a další … V diplomové práci je využit také dvojí pohled na data, a to z hlediska četnosti výskytu termů v dokumentu.

2.4

Neřízené učení

Neřízené učení, neboli učení bez učitele, tvoří další oblast strojového učení. Nejčastější formou neřízeného učení je shlukování. Shlukování (clustering) je oblast, která navazuje na oblast dolování z dat, potažmo dolování z textových dat. Shlukování je také nejvíce rozšířenou metodou tzv. učení bez učitele (unsupervised learning) (Žižka, Burda, Dařena, 2012). Primárním

2.4

Neřízené učení

22

cílem shlukování je roztřídit určité prvky do podmnožin, které nejsou předem definovány, a to na základě určité interní podobnosti prvků. Shlukování úzce souvisí s klasifikací textových dokumentů; hlavní rozdíl tkví ovšem v tom, že na rozdíl od klasifikace není při shlukování k dispozici žádná trénovací množina – množina správně zařazených dat. Neřízené učení je vlastně protějšek k řízenému učení; cílem algoritmu je přiřadit konečnou množinu instancí ke konečné množině tříd, ale přitom zná pouze instance, ale nezná správnou odpověď (náležící třídu) k ani jedné z těchto instancí (Abney, 2008). Jednotlivé shluky (clustery) jsou ve své podstatě třídy vytvořené algoritmem a konkrétní instance se nazývají datové body (anglicky data points). Účel řízeného i neřízeného učení je stejný, liší se tedy především v otázce trénovacích zdrojových dat – řízené učení má trénovací data označená, neřízené učení disponuje pouze neoznačenými daty (anebo trénovací data nemá k dispozici vůbec, záleží na úhlu pohledu). Na tomto místě si autor dovoluje pro ilustraci složitosti shlukování citovat z knihy (Konchady, 2006). „Představme si 50 objektů, které musí být rozděleny do 5 různých kategorií. Předdefinovaná velikost kategorií je: 20, 10, 10, 5, 5. Pakliže budeme vybírat objekty do kategorií sestupně podle velikosti, dostáváme 4, 7 · 1034 způsobů výběru 5 skupin z 50 objektů. Pokud by se počet těchto objektů zvýšil na 100, počet způsobů výběru by pak tvořil číslo 7, 9 · 1069 ”. Existují dvě základní metody shlukování: 1. hierarchické (hierarchical), 2. nehierarchické (ploché, partitional, flat). Hierarchické metody dosahují obecně lepších výsledků, ale nehodí se pro velké kolekce dokumentů pro svou relativní složitost – a tedy i časovou náročnost (Li, Chung, Holt, 2008; Li, Lin, 2011). V diplomové práci je prakticky použita hierarchická ( ) metoda shlukování. ( ) Paměťová složitost hierarchických metod je O n2 , časová pak O n3 (Ševčík, 2010; Downs, Barnard, 1995). ( ) Na druhé straně stojí nehierarchické metody s paměťovou složitostí O n a ča( 2) (Downs, Barnard, 1995). sovou O n Hierarchické metody se dále podle (Gan, Ma, Wu, 2007) dělí na: 1. aglomerativní (agglomerative), 2. divizní (division). Rozdíl mezi oběma metodami je v prvotním přístupu k prvkům. Divizní metody přistupují na začátku ke všem dokumentům jako by patřily k jednomu shluku. Postupně pak tento shluk dělí na menší podmnožiny (Gan, Ma, Wu, 2007).

2.5

23

Termy

Na druhé straně metody aglomerativní postupují takovým způsobem, že na začátku je každý prvek samostatným shlukem sám o sobě, a teprve postupným shlukováním dokumentů dochází k vytváření větších shluků (Gan, Ma, Wu, 2007; Ševčík, 2010). Rozdělení shlukování může být znázorněno ilustrací stromu (Gan, Ma, Wu, 2007): Shlukovací algoritmy Nehierarchické

Hierarchické Divizní Aglomerativní

Obrázek 2: Rozdělení shlukování do kategorií Jedním z hlavních cílů shlukování je rychle nalézt různé relevantní dokumenty. Například v případě internetového vyhledávání na určitém portálu je po zadání hledaných klíčových slov uživateli zobrazena nehomogenní kolekce, kterou je uživatel nucen postupně procházet celou, což je do značné míry neefektivní. Tato kolekce výsledků může být v reálném čase podrobena shlukovací analýze online – tímto se kolekce rozdělí do jednotlivých shluků – tedy skupin dokumentů (výsledků) s určitou podobností, a tímto je celý proces pro uživatele jednodušší (Konchady, 2006). Tyto shluky sice nemají vlastní název, ale mají určitou podobnost, kterou je uživatel schopen rozeznat, což je velmi užitečné.

2.5

Termy

Termy (anglicky terms) tvoří jednotlivé sémantické části dokumentu. Ve většině případů se jedná o konkrétní slova. Termy tvoří základ každého textového dokumentu a je na nich postavena reprezentace dokumentů, které vstupují do shlukovacího procesu. Stemming Stemming je rozšířená metoda pro extrakci termů (Dařena, 2011). Principem je převedení slov (termů) na určitý společný kořen. Příkladem mohou být slova „preview”, „viewer”, anebo „viewed”, která jsou po procesu stemmingu převedena na term „view” (Silva, Ribeiro, 2010).

2.5

Termy

24

Nejznámějším algoritmem provádějící stemming je Porterův algoritmus (Porter, 1980), který pracuje s anglickými texty. Detaily stemmingu se samozřejmě liší. Pro anglický jazyk je velmi časté například odebírání „ing” přípony za slovesem: interesting → interest fishing → fish Podobně existují odlišné algoritmy i pro jiné jazyky. Lemmatizace Lemmatizace je proces, kdy se slovo transformuje do své normální formy (normalizuje) (Plisson, Lavrac, Mladenić, 2004). Lemmatizace je používána v oblasti lingvistiky, dolování z textových dat a mnoho dalších. Jedná se o proces velmi podobný stemmingu, ale na rozdíl od něj není nutné zdrojové slovo transformovat na kmen slova, ale spíše nahradit příponu slova za určitou jinou posloupnost znaků, i prázdnou. Často tak dochází k převodu slova do tvaru infinitivu. Lemmatizace transformuje například slova (Plisson, Lavrac, Mladenić, 2004): computes, computing, computed → compute Výsledkem je řetězec compute – infinitiv. Kdežto výsledkem procesu stemmingu na výše uvedená zdrojová slova by byl řetězec comput. Lemmatizaci musí předcházet morfologická analýza, protože musí být jasné, do jakého základní kanonického tvaru (tzv. lemma) má být vstupní slovo převedeno (Novák, 2013). Proces lemmatizace je náročnější než algoritmus stemmingu (Novák, 2013). Odstranění určitých termů Další metodou zvýšení kvality bag-of-words (popř. vektorové reprezentace, viz dále) textových dokumentů je odstranění určitých jednotlivých termů. Jedná se především o odstranění termů s příliš vysokou nebo nízkou četností. V případě příliš vysoké frekvence se pravděpodobně jedná o nevýznamnou informaci, v případě příliš nízké o překlep (Dařena, 2011). Touto cestou je možné dosáhnout jak redukci prostoru pro vektorovou reprezentaci, tak i zlepšení kvality reprezentace jako takové. Metoda odstranění určitých termů nebyla v diplomové práci použita, jelikož systém Cluto tento algoritmus nativně neimplementuje. Stopslova Stopslova jsou slova (termy), která se objevují v textech v přirozeném jazyce naprosto běžně v jakémkoliv kontextu a nenesou žádnou zásadní sémantickou infor-

2.6

Reprezentace textových dokumentů

25

maci (Dařena, 2011). Jedná se o běžně používaná slovesa, spojky, předložky, či členy (Torkkola, 2004). Odstraněním těchto stopslov (stop words) se teoreticky zvyšuje kvalita reprezentace dokumentu. Algoritmus pracuje s premisou, že termy s vysokou frekvencí nejsou pro reprezentaci užitečné (signifikantní). Tyto přebytečné termy se hledají jednoduchým způsobem, kdy se najde x % termů ze slovníku (seznamu termů), které jsou nejčastější. Tyto termy jsou pak zcela odstraněny pro zvýšení výkonu i paměťového místa (Konchady, 2006). Komplikací je však vybrat vhodné x. Pokud je x příliš vysoké, je odebráno mnoho termů, které mohou být pro dokument určitým způsobem signifikantní. Naopak, pokud je hodnota x příliš nízká, mohou být některá přebytečná stop-slova zůstat přítomna. Tuto mezní hodnotu x je třeba vybrat na základě typu zdrojových dat a jejich kontextu (Konchady, 2006). Jako příklady těchto stop-slov je možné v anglickém jazyce uvést (Konchady, 2006, str. 96): about, add, ago, very, via, himself, could, be, at, want, still, since, not, now, must, my, never, their, … V praxi se používají celé seznamy těchto slov, které se nazývají seznamy stopslov (stop word list). V systému Cluto je možné připojit vlastní seznam stop-slov. Výše uvedená slova jsou obecná stop-slova v anglickém jazyce. Je samozřejmě výhodné použít, pokud to situace umožňuje, i konkrétnější stop-slova na základě oblasti zdrojových dat. Pro příklad jsou uvedena stop-slova pro zdrojová data, kde se dokumenty zabývají webovou problematikou (Konchady, 2006, str. 97): address, adobe, bin, www, spam, web, jpg, ftp, foreground, … Komplikace při použití stop-slov mohou nastat při zpracování určitých dokumentů. Manu Konchady uvádí, že některé fráze jako například „to be or not to be” jsou celé složeny ze stop-slov (Konchady, 2006, str. 97). Při zpracování tak mohou být všechny termy odstraněny a s dokumentem se nakládá, jako kdyby byl sám prázdným řetězcem. Metoda odstranění stopslov opět není implementována v systému Cluto, tudíž nebyla použita v experimentech. Do jisté míry ji ale v systému Cluto nahrazuje algoritmus, který automaticky odstraňuje termy s délkou tří nebo méně písmen (slova jako „and”, „but”, …) a termy složené pouze z číslovek. Stejný princip uplatňuje i implementovaný programový systém využitý v diplomové práci.

2.6


Aby mohly být dokumenty podrobeny shlukování, je třeba je určitým způsobem vhodně interpretovat. Existuje mnoho různých způsobů reprezentace textových dokumentů.

2.6


26

Bag-of-words Bag-of-words je ve své podstatě nejzákladnější reprezentací textových dokumentů. Podstatou metody je převod dokumentu na posloupnost termů (povětšinou jeden term tvoří jedno slovo), kde pořadí nehraje roli. Tato reprezentace je nejjednodušší, nejrychlejší a nejpoužívanější (Zhang, Jin, Zhou, 2010, str. 43-52), nicméně bývá kritizována právě pro svoji ignoraci sémantiky dokumentu (Zhang, Yoshida, Tang, 2008, str. 879-886). V této reprezentaci nehraje žádnou roli interpunkce, slova jsou extrahována a ztrácejí svoji gramatickou informaci (Srivastava, Sahami, 2009). Uvedený fakt implikuje, že z bag-of-words nelze sestavit původní dokument (Srivastava, Sahami, 2009). Někdy se tato reprezentace nazývá bag-of-terms nebo bag-of-keypoints (Pratikakis et al., 2011), popř. bag-of-features (Srivastava, Sahami, 2009). Vektorová reprezentace Vektorová reprezentace (vector space model, VSM ) je nejčastějším způsobem reprezentace textových dokumentů pro shlukování. Tato reprezentace byla poprvé představena v odborné publikaci v roce 1975 (Salton, Wong, Yang, 1975). Princip vychází z bag-of-words reprezentace, ale na místě určitého termu je číslo, které je prvkem vektoru. Ve své podstatě se jedná o to, že každému termu je přiřazen určitý příznak. S těmito vektory se pak pracuje ve vektorovém prostoru, kde každý dokument tvoří právě jeden vektor. Tímto způsobem mohou být dokumenty v podobě vektorů jednoduše porovnávány a může být zjišťována jejich vzájemná podobnost. V souvislosti s vektorovou reprezentací je zavedena určitá terminologie, jež je čerpána z knihy (Konchady, 2006). Korpus (anglicky corpus) je určitá množina dokumentů; slovník (dictionary) je pak množina termů, která se v dokumentech vyskytuje. Na dokumenty můžeme ve vektorové reprezentaci nahlížet jako na bag-of-terms (viz oddíl 2.6), tato reprezentace představuje vektor, kde je každý prvek asociován s prvkem ve slovníku (Srivastava, Sahami, 2009). Jestliže slovník obsahuje N termů, dokument je převeden do N -rozměrného prostoru. Toto N je většinou velké a produkuje řídkou (sparse) VSM reprezentaci, kde je pouze několik prvků nenulových. Tento fakt implikuje, že v kontextu větších množin textových dokumentů v přirozeném jazyce je vektor většinou z 99 % řídký (Srivastava, Sahami, 2009). To také znamená, že korpus je zpravidla menší než velikost slovníku. Korpus může být reprezentován několika způsoby ve formě matice: • document-term (term-document) matice D′ , • term-term matice D′ D, • matice document-document DD′ .

2.6

27


U matice document-term D′ tvoří řádky jednotlivé indexované dokumenty. Sloupce jsou pak tvořeny reprezentacemi jednotlivých termů – počtem výskytů termů, přítomností termů, popř. jakoukoliv jinou váhou (číslem). Prvky vektoru značí počet výskytu termu v dokument. Tabulka 1: Příklad matice document-term

sun mad

location

expect

dokument 1

0

1

2

0

dokument 2

1

0

0

0

dokument 3

0

0

1

2

dokument 4

0

1

0

0

        

prvky vektoru

Matice term-term D′ D je symetrická, řádky i sloupce tvoří jednotlivé termy (Kontostathis, Pottenger, 2002). Matice znázorňuje podobnost mezi jednotlivými termy. Existuje mnoho modifikací, které se liší ve způsobu vážení této reprezentace (Kontostathis, Pottenger, 2002). Matice document-document DD′ je taktéž symetrická a je možné ji vytvořit na základě matice document-term D′ . Tato matice DD′ znázorňuje podobnost (similarity) mezi jednotlivými dokumenty. Dále je možné rozeznat dva základní typy matice podle způsobu reprezentace prvků ve vektorech (Karypis, 2003). 1. řídká (sparse), 2. hustá (dense). Definice výše uvedených pojmů se poměrně liší (Nečas, 1978). V kontextu systému Cluto je řídkou maticí chápána matice, která má většinu prvků nulových. Při definici prvků matice tak stačí pouze uvést pozici prvku v řádku a konkrétní hodnotu. S nedefinovanými prvky (kterých je v mnohorozměrném prostoru při práci s textovými daty naprostá většina) se pak zachází jako s nulovými. Tento systém tudíž přináší znatelnou úsporu místa. Program Cluto umožňuje zobrazit oba typy reprezentací, standardně však pracuje s maticí řídkou. Jak již bylo řečeno výše, vektorový model má řadu výhod i nevýhod. Mezi největší nevýhody patří: • ztráta sémantické informace, • nemožnost vytvořit původní dokument, • nezohlednění synonym.

2.6

28


Synonyma mohou být v tomto případě například zařazena do odlišných shluků, přestože jakožto jednotlivé termy obsahují z hlediska reprezentace naprosto stejnou informaci. V praxi je obvykle každý vektor normalizován na stejnou velikost (délku). Každý prvek vektoru je reprezentován určitým číslem a délka vektoru d⃗i je stejná jako velikost slovníku dict (viz vztah 2). |d⃗i | = |dict|

(2)

Následují konkrétní používané typy reprezentací vektorového modelu. Term Presence Term Presence (TP, přítomnost termu) je velmi jednoduchý způsob vektorové reprezentace textového dokumentu. Každý prvek vektoru je reprezentován binárním číslem 0 nebo 1. Číslo 1 značí, že daný term je v dokumentu přítomen alespoň jednou. Naopak, číslo 0 ukazuje na nepřítomnost termu. Proto je tato reprezentace označována jako binární. Term Frequency Term Frequency (TF, frekvence termu) je rozšířený způsob vektorové reprezentace textových dokumentů. Pracuje na jednoduchém principu počtu výskytů termů. Jedná se o to, že každý prvek vektoru je reprezentován celým přirozeným číslem, jež reprezentuje počet výskytů termu v dokumentu. Tato reprezentace je často používána se škálováním Inverse Document Frequency (viz dále); samotná Term Frequency se při shlukování příliš nevyužívá, resp. vykazuje špatné výsledky pro textové dokumenty v přirozeném jazyce (Žižka, Burda, Dařena, 2012). Složku TF – tedy relativní významnost termu i v určitém dokumentu j, lze zapsat rovnicí nij T Fij = ∑ (3) nij ∑ kde nij určuje počet výskytů i-tého term v j-tém dokumentu a nij je počet výskytu všech termů v dokumentu j. Inverse Document Frequency Ve většině případů je nutné brát v potaz různou délku dokumentů. Při použití „čisté” Term Frequency by byly delší dokumenty nebo dokumenty obsahující vícekrát určitý term, nadhodnoceny. Z toho důvodu je potřeba provést vážení či škálování termů – toto provádí Inverse Document Frequency. Výpočet složky IDF termu i v j-tém dokumentu pak probíhá dle rovnice 4 IDFij = log

N nij

(4)

přičemž N představuje celkový počet dokumentů, nij pak značí počet dokumentů obsahujících daný term ij.

2.7

29

Rozhodovací strom

Term Frequency-Inverse Document Frequency Reprezentace Term FrequencyInverse Document Frequency (TF-IDF) je hojně využívána v mnoha aplikacích (Baeza-Yates, Ribeiro, 1999). TF-IDF je velmi efektivní při shlukování takřka jakéhokoli množství dat. Výpočet váhy každého termu i v j-tém dokumentu je dán jednoduchou rovnicí, kterou tvoří součin složky TF a složky IDF: N nij · log T F -IDFij = T Fij · IDFij = ∑ nij nij

(5)

N-tice slov Do jisté míry lze vektorovu reprezentaci textového dokumentu vylepšit používáním n-tic termů (slov) místo jednotlivých termů (slov). V tomto případě tedy term netvoří jedno slovo, ale n slov. Nelze ovšem předpokládat, že použitím n-tic slov lze automaticky dosáhnout lepší kontextové (sémantické) informace; tyto n-tice je nutno vybrat pečlivě (Zhang, Jin, Zhou, 2010). Dalším problémem, který může nastat, je příliš velký rozměr vektoru (tedy velikost slovníku je velká) a tedy i pravděpodobnost řídkosti jednotlivých vektorů. S touto komplikací se pojí i vysoké nároky na paměť pro uložení. V kontextu n-tic slov jsou rozlišeny bi-gramy (pokud platí, že n = 2), případně n-gramy (v případě, že n > 2).

2.7

Rozhodovací strom

Rozhodovací strom je de facto množina rozhodovacích pravidel pro jakýkoliv vstup. Protože se jedná schematicky o strom, je tvořen kořenem, větvemi a listy. Rozhodovací pravidla, které jsou nejblíže kořenu, jsou obyčejně nejdůležitější. Důležitost daného pravidla – pravidlo je vlastně tvořeno větví nebo listem stromu – klesá s rostoucí vzdáleností od kořene. Autor si dovoluje představit fungování rozhodovacího stromu na jednoduchém příkladu, který je převzatý ze zdroje (Quinlan, 1993). Mějme zdrojovou trénovací tabulku, která obsahuje údaje o počasí a venkovních podmínkách a ke každému konkrétnímu případu je přiřazena buďto třída hrát, anebo nehrát:

2.7

30

Rozhodovací strom

Tabulka 2: Zdrojová trénovací množina pro rozhodovací strom

Obloha

Teplota (° F)

Vlhkost (%)

Větrno?

Třída

Slunečno Slunečno Slunečno Slunečno Slunečno Zataženo Zataženo Zataženo Zataženo Déšť Déšť Déšť Déšť Déšť

75 80 85 72 69 72 83 64 81 71 65 75 68 70

70 90 85 95 70 90 78 65 75 80 70 80 80 96

Ano Ano Ne Ne Ne Ano Ne Ano Ne Ano Ano Ne Ne Ne

Hrát NEhrát NErát NEhrát Hrát Hrát Hrát Hrát Hrát NEhrát NEhrát Hrát Hrát Hrát

Rozhodovací strom je schopen vytvořit následující strukturu s pravidly, která jsou odvozena od údajů obsažených v trénovacích datech. Ilustrace je na obrázku 2.7.

Obrázek 3: Příklad rozhodovacího stromu Rozhodovací stromy netvoří samy o sobě nějaký konkrétní algoritmus, jedná se spíše o množiny algoritmů, které fungují velice podobně. Konkrétní implementace

2.7

Rozhodovací strom

31

rozhodovacích stromů tvoří například algoritmy jako C4.5 (popsáno v části 2.11), GRI, SLIQ, ID3 a další. (Srivastava, Han, Kumar, Singh, 2002) Formát CSV CSV je zkrácenina z anglického Comma Separated Values. Původně se jednalo o výměnný souborový formát ke sdílení souborů mezi tabulkovými procesory. Formát se díky své obecnosti a tím, že je možné ním popsat samotná data i strukturu zároveň, stal jedním z nejznámějších formátů pro uchování (a volitelně deskripci) dat. Formát se podle RFC (Shafranovich, 2005) řídí těmito základními pravidly: • každý jednotlivý záznam se nachází na samostatném řádku (záznamy jsou odděleny znakem nového řadku), • jednotlivé složky (datové členy, záznamy) jsou odděleny libovolným oddělovačem – obvykle se jedná o znaky jako „,”, „;”, tabulátor, mezera, atp., • za poslední složkou záznamu již není oddělovač, následuje za ním hned znak nového řádku, • každý záznam by měl mít stejný počet členů, tedy i oddělovačů, • CSV formát může mít na prvním řádku názvy pro hodnoty pro konkrétní sloupce. Formát ARFF ARFF je nativní formát textových dat systému Weka (viz strana 53). Informace jsou v tomto odstavci čerpány především z (Weka, 2012). Zkratka ARFF znamená Attribute-Relation File Format. Formát definuje datovou množinu v rámci relace (tabulky), která sestává z atributů nebo také sloupců. Datové typy použité v konkrétních sloupcích, jejich názvy a název celé relace jsou definovány v hlavičce ARFF formátu, která tvoří první část ARFF souboru. Datové typy mohou nabývat typů jako jsou čísla (celá, reálná), výčty a řetězce. Jednotlivé datové typy mohou mít nastaveny svůj vlastní obor hodnot. To je signifikantní odlišnost od formátu CSV. Po hlavičce následuje samotné tělo ARFF souboru, kde jsou konkrétní data a hodnoty. Příklad jednoduchého ARFF souboru následuje: @relation golf @attribute outlook { sunny, overcast, rain} @attribute temperature real [0.0,100] @attribute humidity real @attribute windy { true, false} @attribute class { Play, 'Dont Play' } @data

2.8

Podobnost textových dokumentů

32

% 14 instances follow sunny, 85, 85, false, 'Dont Play' sunny, 80, 90, true, 'Dont Play' overcast, 83, 78, false, Play rain, 70, 96, false, Play rain, 68, 80, false, Play rain, 65, 70, true, 'Dont Play' overcast, 64, 65, true, Play sunny, 72, 95, false, 'Dont Play' sunny, 69, 70, false, Play rain, 75, 80, false, Play sunny, 75, 70, true, Play overcast, 72, 90, true, Play overcast, 81, 75, false, Play rain, 71, 80, true, 'Dont Play' Formát ARFF byl spolu s CSV zvolen především proto, že ho podporuje celá řada nástrojů a programových systémů z oblasti strojového učení.

2.8


Tato sekce pojednává o podobnosti textových dokumentů z hlediska shlukování. Podobnost textových dokumentů z hlediska řízeného a neřízeného učení záleží na klasifikátoru – viz pozdější kapitola Klasifikační algoritmy. Způsob, jakým jsou dokumenty navzájem porovnávány, je ve shlukovací analýze naprosto klíčový. Ve své podstatě totiž určuje, do kterého shluku bude porovnávaný dokument zařazen. V této sekci jsou popsány nejpoužívanější metriky (funkce) podobnosti textových dokumentů. Všechny tyto metriky pracují s vektory, tudíž textové dokumenty musí být převedeny do vektorové podoby a optimálně i normalizovány na stejnou délku. Následující podsekce představují metriky podobnosti textových dokumentů, jež nachází největší uplatnění v oblasti neřízeného učení. Kosinová podobnost Kosinová podobnost je nejpoužívanější metrikou podobnosti mezi vektorovými reprezentacemi (Huang, 2008; Žižka, Burda, Dařena, 2012). Protože se jedná o vektorový kosinus, je tato funkce dána součtem součinu společných termů ku součinu délek obou vektorů (Konchady, 2006). Proto je tato metrika ve své podstatě „běžným” kosinem úhlu mezi vektory v prostoru.

2.8

33


Kosinus cos je i jednou z nejjednodušších metod podobnosti. Tato funkce je dána předpisem Da · Db cos(Da , Db ) = = cos(α) (6) ⃗a ||D ⃗ b| |D kde Da and Db jsou vektorovými reprezentacemi dvou dokumentů a α tvoří úhel mezi nimi.

Obrázek 4: Kosinus dvou normalizovaných vektorů jakožto měřítko podobnosti ve dvourozměrném prostoru Kosinová podobnost bere samozřejmě do úvahy pouze velikost úhlu mezi vektory, na velikosti vektorů nezáleží. Euklidovská vzdálenost Euklidovská vzdálenost je další známá metrika, která se běžně používá v geometrii (Huang, 2008). Tato metrika bere do úvahy jak směr vektorů, tak i jejich délku (v systémech Cluto jsou ovšem vektory normalizovány, tudíž mají délku stejnou). Euklidovská vzdálenost d mezi vektory Da a Db se vypočte podle vzorce (Dařena, 2011, str. 30) v u n u∑ ⃗a , D ⃗ b) = t d(D (Dai − Dbi )2 (7) i=1

kde Dai a Dbi tvoří souřadnice vektorů Da a Db pro dimenzi (rozměr) i. Pro vektory, které mají mnoho nebo naopak velmi málo dimenzí, se toto měřítko podobnosti pro shlukovací analýzu příliš nehodí (Karypis, 2003).

2.8


34

Obrázek 5: Euklidovská vzdálenost mezi dvěma vektory Pearsonův korelační koeficient Pearsonův korelační koeficient je ve své podstatě variací na kosinus. Operuje se dvěma vektory, od kterých nejprve odečte jejich průměr a pak na tyto vektory aplikuje kosinovou funkci (Karypis, 2003). Protože Pearsonův korelační koeficient vychází z kosinové podobnosti, nezávisí na délce vektorů (Karypis, 2003). Obor hodnot Pearsonova korelačního koeficientu je na rozdíl od kosinu < 0, 1 >. Ačkoliv Pearsonův korelační koeficient není příliš rozšířenou metrikou, Cluto tento algoritmus implementuje. Jaccardův koeficient Jaccardův koeficient je poměrně jednoduchou a intuitivní metrikou využívající se ve shlukovací analýze. Pro vysvětlení principu této podobnosti uvažujme množinu dokumentů A a B, kde oba dokumenty obsahují klíčové slovo (term). Jaccardův koeficient jacc je pak dán poměrem jejich průniku k jejich sjednocení (Konchady, 2006, str. 269) A∩B jacc(A, B) = (8) A∪B Po vztažení do roviny konkrétní vektorové reprezentace obou dokumentů – Da a Db – se dvěma klíčovými slovy (termy) lze vztah znázornit jako (Konchady, 2006, str. 270) jacc(Da , Db ) =

Dax Dbx + Day Dby Dax + Dbx + Day + Dby − Dax Dbx − Day Dby

(9)

kde x a y jsou souřadnicemi pro jednotlivé rozměry vektorů (v tomto případě dva). Jaccardův koeficient se využívá především v lékařství (Saad, Iglesia, Bell, 2006).

2.9

2.9

Shlukovací algoritmy

35


Shlukovací algoritmy tvoří přirozeně základ celého shlukování. Určují způsob, jakým se budou dokumenty na základě vzájemné podobnosti přiřazovat do shluků. Pravděpodobně největším problém je určení počtu shluků k, jelikož před zahájením shlukovacího procesu neexistuje, ve většině případů, příliš informací o rozložení dokumentů v kolekci (Konchady, 2006, str. 276). Aglomerativní metody Aglomerativní metody patří do hierarchických shlukovacích metod a pracují na začátku algoritmu se všemi dokumenty jako s jednotlivými shluky. Poté se tyto prvotní shluky postupně spojují podle principu dendrogramu (stromového diagramu, viz 6) do dalších shluků tak dlouho, dokud není dosaženo k konečných shluků (Srivastava, Sahami, 2009). Aglomerativní metody postupují podle principu „zespodu nahoru” (bottom-up). Existuje řada aglomerativních metod: UPGMA, Single-link, Cure, Rock a další (Zhao, Karypsis, 2006). Vztah dokumentů 1-10 v kolekci je ilustrován dendrogramem, příklad je na obrázku 6. Dokumenty jsou na základě své podobnosti postupně spojovány do shluků. Ve většině případů je výhodnější použít divizní metody (např. opakovanou bisekci, viz dále), jelikož aglomerativní metody provádějí shlukovací rozhodnutí na základě lokální podobnosti sousedních prvků a neberou v potaz globální rozložení podobnosti. Jakmile jsou dva shluky spojeny v jeden, algoritmus se už nemůže vrátit (Manning, Raghavan, Schütze, 2008).

Obrázek 6: Dendrogram znázorňující postup hierarchického shlukování

2.9


36

Výběr dvojice shluků, které jsou při každému kroku spojovány, závisí na použité metodě podobnosti (viz 2.8) a dále také na kriteriální funkci (2.10). k-means Algoritmus k-means patří mezi nejjednodušší algoritmy shlukovací analýzy, tudíž má velmi krátkou dobu provádění. k-means je typickým zástupcem nehierarchických metod shlukování (Barbakh, Fyfe, 2008; Ševčík, 2010). Na začátku je nutno vybrat určitým způsobem k dokumentů, které budou označeny jakožto reprezentanti k shluků. Principem algoritmu je pak pohyb středů (centroidů) těchto shluků napříč kolekcí dokumentů a na základě nejvyšší míry podobnosti jsou do shluku přesunuty jednotlivé dokumenty z kolekce. Základní algoritmus k-means může být popsán v následujících krocích (Konchady, 2006, str. 277-278): 1. vyber počátečních k dokumentů z kolekce pro vytvoření k shluků, 2. opakuj následující pod-kroky, dokud nejsou splněny ukončovací podmínky, 2.1 pro každý dokument d najdi shluk i, jehož centroid je nejblíže (dokument je nejvíce podobný centroidu shluku), pak přiřaď dokument d do shluku i, 2.2 pro každý shluk i přepočítej jeho aktuální centroid (střed) na základě stávajících dokumentů, jež obsahuje, 2.3 zkontroluj výstupní (ukončovací) podmínky – minimální nebo žádné změny v přiřazení dokumentů do shluků, 3. vrať seznam shluků a dokumentů k nim přiřazených. Centroid, který je danému dokumentu „nejblíže”, určuje metrika podobnosti (kosinus, euklidovská vzdálenost apod., viz 2.8).

2.9


37

Obrázek 7: Algoritmus k-means, pohyb středů Základní algoritmus k-means má pouze logaritmickou časovou složitost (Konchady, 2006), na rozdíl od mnoha dalších. Existuje mnoho variací, optimalizací nebo úprav algoritmu k-means jako např. HMRF-kMeans, k-means-C, k-means-C-D-R, a další (Srivastava, Sahami, 2009; Barbakh, Fyfe, 2008). V systému Cluto se tento algoritmus (metoda) shlukování nazývá přímou metodou (direct). Samotný manuál programu Cluto uvádí, že pro k menší než 10-20 je k-means nejvýhodnější, v rámci textových dokumentů v přirozeném jazyce (Karypis, 2003). Opakovaná bisekce Metoda opakované bisekce (repeated bisection) je zástupcem divizního hierarchického přístupu (Ševčík, 2010). Nejprve je matice rozdělena do dvou shluků, poté je jeden shluk vybrán a dělen dále. Tento proces pokračuje až do doby, než je dosaženo požadovaného počtu shluků. Pro vytvoření k shluků je provedeno k−1 bisekcí. Protože algoritmus patří do hierarchických metod, jeho postup může být znázorněn dendrogramem (viz obrázek 6). Klíčové je při této metodě rozhodnutí, který ze shluků dále rozdělit (Saad, Iglesia, Bell, 2006). Fuzzy shlukování Fuzzy shlukování tvoří množinu shlukovacích algoritmů, kde datové body (data points) nepatří do jednotlivých shluků s příslušností 1, 0 – tedy buď do daného shluků patří, anebo nepatří vůbec – ale s příslušností v intervalu < 0, 1 >.

2.10

Kriteriální funkce

38

Datový bod tedy může například patřit do jednoho shluku s příslušností 0, 3 a do druhého s příslušností 0, 7. Již z názvu je patrné, že charakter je založen na fuzzy logice1 . Fuzzy shlukování se také často nazývá měkké (soft) (Baraldi, Blonda, 1999). Autor si dovoluje odkázat zájemce o tyto algoritmy na zdroj (Baraldi, Blonda, 1999). Grafové metody Grafové metody (graph-partitioning based methods) pracují s dokumenty v kolekci jako s grafem. Vrcholy grafu jsou představeny jednotlivými dokumenty a každý vrchol je spojen hranou s nejbližšími (nejvíce podobnými) sousedy. Poté je graf v iteracích rozdělen do k shluků s využití minimálního řezu (minimum cut) (Karypis, 2003). Pro informace o minimálním řezu viz (Demel, 2002, str. 131). Umělé neuronové sítě Shlukování za využití umělých neuronových sítí je také časté. Neuronové sítě jsou stručně popsány v části 2.11 na straně 45.

2.10

Kriteriální funkce

Obecné informace Účelem kriteriálních funkcí (criterion functions) je stanovení vzdálenosti mezi jednotlivými shluky v rámci každého kroku shlukovacího algoritmu (Zhao, Karypsis, 2006). Kriteriální funkce mají určitý vliv na kvalitu řešení, potažmo výpočetní náročnost (Karypis, 2003). Program Cluto umožňuje použít celkem sedm různých kriteriálních funkcí pro hierarchické i nehierarchické shlukování: I1 , I2 , E1 , G1 , G′1 , H1 , H2 . Manuál systému Cluto uvádí, že kriteriální funkce I2 a H2 vedou k velmi dobrým výsledkům pro textová data. Na druhé straně funkce E1 a G1 vedou ke shlukům, které mají podobnou velikost (Karypis, 2003). Vliv kriteriálních funkcí je empiricky zjišťován v praktické části. ( ) H1 ) a H2 je časová složitost kubická O n3 , pro ostatní funkce platí ( Pro O n2 · log n (Zhao, Karypsis, 2006). Detaily fungování kriteriálních funkcí jsou mimo rámec diplomové práce, pro další informace autor odkazuje na zdroj (Zhao, Karypsis, 2006).

2.11

Klasifikační algoritmy

V sekci jsou popsány klasifikační algoritmy, které je možné aplikovat v rámci řízeného a částečně řízeného učení. 1

Více informací na http://www.cs.cmu.edu/Groups/AI/html/faqs/ai/fuzzy/part1/faq-doc-2.html

2.11

39


V rámci diplomové práce byly použity či implementovány metody Naivní Bayes (a jeho variace Multinomiální Naivní Bayes), k–nejbližších sousedů a Support Vector Machines. Další algoritmy jsou zmíněny a popsány také v následujícím textu. Naivní Bayes Algoritmus Naivního Bayese, v angličtině Naive Bayes, anebo také Independence Bayes, je jedním z nejjednodušších a zároveň také nejpoužívanějších algoritmů řízeného učení (Kumar, Wu, 2009). Díky své jednoduchosti (a tedy i operační efektivitě) je algoritmus vhodný i pro velmi velké kolekce dat. Přes svou jednoduchost je algoritmus velice efektivní v mnoha oblastech (Abney, 2008). „Naivita” algoritmu spočívá v tom, že Naivní Bayes apriori předpokládá vzájemnou nezávislost prvků ve vektoru, který popisuje textová data jako např. větu. V případě kolekcí textových dat v přirozeném jazyce tedy předpokládá, že například slova ve větě (vyjádřena prvky vektoru) mezi sebou nemají žádnou relaci, i když je intuitivně jasné, že relace mezi prvky je velmi vysoká kvůli gramatice jazyka. Zdroj (Kumar, Wu, 2009) uvádí, že algoritmus Naivního Bayese je možno úspěšně aplikovat na prakticky jakákoliv data, takže algoritmus je vysoce obecný a robustní. Kvůli své obecnosti je využíván velmi často jak v akademické sféře, tak v praxi. Nechť P (i | x) je pravděpodobnost, že objekt popsaný vektorem x = (x1 , ..., xp ) patří do třídy i, f (x | i) je podmíněná distribuce x pro třídu i. P (i) je pravděpodobnost, že objekt bude náležet ke třídě i (bez jakékoliv předchozí znalosti). f (x) je kombinace (anglicky overall mixture) těchto tříd. Předpokládejme dvě třídy: f (x) = f (x | 0) · P (0) + f (x | 1) · P (1)

(10)

Výsledná pravděpodobnost P (i | x), že objekt x patří do třídy i se vyjádří dle rovnice (Kumar, Wu, 2009): P (i | x) =

f (x | i) · P (i) f (x)

(11)

Naivní Bayes rozhoduje příslušnost objektu do třídy i z konečné množiny možných tříd, jejichž počet je roven n, na základě prvků vektoru P , kde P0 značí pravděpodobnost náležitosti do třídy i: P⃗ = (P0 , P1 , ..., Pn )

(12)

Hodnoty prvků vektorů jsou již normalizované do intervalu < 0, 1 >. Mezní hodnota (anglicky threshold), kde se rozhoduje finální predikce klasifikátoru pro konkrétní dokument, je obyčejně nastavena na hodnotu 0, 5 (Kumar, Wu, 2009). Pokud je tedy pravděpodobnost příslušnosti pro třídu 0 P0 rovna 0, 51, znamená to, že algoritmus vyhodnotil, že objekt náleží do třídy 0 a již není nutné zkoumat další hodnoty vektoru. Existují ale i varianty algoritmu, kde mezní hodnota může být odlišná od

2.11

40


zmíněné hodnoty 0.5 a které berou do úvahy například anomálie konkrétní kolekce dat, atp. Algoritmus Naivního Bayese je díky své obecnosti možno aplikovat na n tříd přímo, to znamená nikoliv pouze v binární klasifikaci. V diplomové práci je použita nejběžnější varianta algoritmu s mezní hodnotou 0, 5. Autor si zde dovoluje uvedení krátkého příkladu převzatého ze zdroje (Kelcey, 2010). Tabulka 3 uvozuje jednotlivé texty, jež jsou zařazeny buď do třídy Ano nebo ne. Tabulka 3: Zdrojová tabulka pro modelový příklad algoritmu NB

Text

Třída

on the linux cat on ferrari on the holywood lamborghini on cat holywood cat the lamborghini cat on linux

Ano Ne Ne Ano Ne Ano Ano

Pro ilustraci fungování algoritmu Naivního Bayese autor presentuje tabulkové hodnoty, kde první sloupec uvozuje konkrétní text, poslední dva sloupce značí příslušnosti ke třídě a zbytek sloupců mezi těmito dvěma tvoří jednotlivé termy. V tabulkovém poli je uvedena binární hodnota, kde A značí třídu Ano a N představuje Ne. Tabulka 4: Zdrojová tabulka s vlastnostmi textů pro modelový příklad metody NB

Text

on

the

linux

cat

ferrari

holywood

lambo...

Ano

Ne

on the linux cat on ferrari on the holywood lamborghini on cat holywood cat on the linux the lamborghini cat on linux

A A A A N A N A

A N A N N A A N

A N N N N A N A

N A N A A N N A

N A N N N N N N

N N A N A N N N

N N N A N N A N

A N N A N A A A

N A A N A N N N

Z uvedené tabulky je možné jednoduše zjistit dílčí pravděpodobnosti pro jednotlivé termy i třídy. Dostáváme tedy v tabulce 5 hodnoty pravděpodobností, kde

2.11

41


P (x | trida) značí příslušnost objektu x do třídy trida. Jsou zde presentovány hodnoty pravděpodobností, přičemž hodnota úplně napravo je hodnota po normalizaci (viz část 2.12, strana 49, rovnice 19). Tabulka 5: Pravděpodobnosti příslušnosti pro modelový příklad metody NB

Pravděpodobnost P (′ the′ | ′ Ano′ ) P (′ holywood′ | ′ Ano′ ) P (′ lamborghini′ | ′ Ano′ ) P (′ Ano′ ) P (′ the′ | ′ N e′ ) P (′ holywood′ | ′ N e′ ) P (′ lamborghini′ | ′ N e′ ) P (′ N e′ )

Hodnota

Po normalizaci

2 4 0 4 2 4 4 7 1 3 2 3 0 3 3 7

3 7 1 7 3 7 — 2 6 3 6

—

Protože z rovnice 10 platí, že pravděpodobnost, že text „the holywood lamborghini” náleží do třídy Ano je: P (′ the holywood lamborghini′ | ′ Ano′ ) =P (′ the′ | ′ Ano′ ) · P (′ holywood′ | ′ Ano′ )· ·P (′ lamborghini′ | ′ Ano′ ) V případě hodnot v tabulce 5 by to znamenalo, že: 3 1 3 4 . · · · = 0, 0149 7 7 7 7 . Pokud by například platilo, že P (′ the holywood lamborghini′ | ′ N e′ ) = 0, 0119, je možné dedukovat, že pravděpodobnost příslušnosti textu do třídy Ano je vyšší, než pravděpodobnost, že patří do Ne. ( ) Operační náročnost algoritmu Naivního Bayese ( )je O m · N při procesu trénování, kde N je počet trénovacích dokumentů, a O n při procesu klasifikace (Metsis, Androutsopoulos, Paliouras, 2006). P (′ the holywood lamborghini′ | ′ Ano′ ) =

Multinomiální Naivní Bayes Variací algoritmu je pak Multinomial Naive Bayes, do českého jazyka by se dalo pojmenování přeložit jako mnohočlenný Naivní Bayes. Rozdíl je ve faktu, že mno-

2.11

42


hočlenný Naivní Bayes využívá mnohočlenné distribuce (rozložení) příznaků – v kontextu dat diplomové práce tedy jednotlivých termů (Kibriya et al., 2005). Ve zkratce se dá říci, že zatímco Naivní Bayes bere do úvahy informaci, kolik objektů z různé třídy obsahuje termy dané vstupním objektem, tak Multinomiální Naivní Bayes se zajímá, kolik termů je obsaženo v různých třídách Autor by si zde dovolil krátký příklad převzatý z internetového zdroje (Kelcey, 2010); mějme tabulku 6, kde jsou krátké texty zařazeny buď do třídy Ano nebo Ne. Tabulka 6: Zdrojová tabulka pro modelový příklad algoritmu MNB

Text

Třída

linux on the linux cat on ferrari on the holywood on lamborgini on cat holywood cat

Ano Ne Ne Ano Ne

Z těchto zdrojových dat je možno udělat jednoduchou tabulku (tabulka 7) popisující termy a jejich vlastnosti v kontextu dat. Výraz n (Ano) znamená celkový počet výskytu slova na řádku ve třídě Ano, analogicky to stejné platí pro n (N e) a Ne. Pro názornost byla vynechána některá slova. Tabulka 7: Zdrojová tabulka popisující slova a jejich vlastnosti v příkladě

Slovo

Výskytů n (Ano) n (N e)

on linux the holywood

6 3 3 2

4 3 2 0

2 0 1 2

Nechť výraz P (objekt | Ano) představuje pravděpodobnost dle klasifikátoru, že entita objekt patří do třídy Ano. Dále uvažujme, že N je počet termů v objektu (dokumentu) a f (wn ) představuje frekvenci slova (termu) wn . Pak pro Multinomiálního Naivního Bayese platí, že: P (objekt | Ano) = N ! · ·

P (w1 | Ano)f (w1 ) P (w2 | Ano)f (w2 ) · ... f (w1 )! f (w2 )! P (wn | Ano)f (wn ) f (wn )!

Například P (w1 | Ano) představuje pravděpodobnost pro term w1 , že náleží do Ano.

2.11

43


Proto tedy například pravděpodobnost, že text „linux the linux” patří do třídy Ano je následující: P (′ linux′ | Ano)2 P (′ the′ | Ano)1 P ( linux the linux | Ano) = N ! · · 2! 1! 2 = 27 ′

′

Analogicky se vypočte hodnota P (′ linux the linux′ | N e) a poměrem obou výsledků se vypočte klasifikační pravděpodobnost příslušnosti k oběma třídám. k–nejbližších sousedů Metoda k–nejbližších sousedů (nebo také kNN, či anglicky k–Nearest Neighbors) je dalším hojně využívaným algoritmem strojového učení. Algoritmus najde v množině trénovacích dat k objektů, které jsou v n-rozměrném prostoru „nejblíže” testovanému objektu – jsou podle určité metriky podobnosti testovanému objektu nejvíce podobné – a na základě tříd, ke kterým těchto k objektů náleží, je přiřazena třída i testovanému objektu (Kumar, Wu, 2009). Kardinálními faktory algoritmu jsou proto (Kumar, Wu, 2009): 1. množina objektů, ze které jsou vybíráni nejbližší sousedi (Nemusí to být celá trénovací množina), 2. metrika podobnosti objektů, 3. hodnota k, 4. způsob, podle kterého je testovanému objektu podle k sousedů přiřazena třída. ( ) Prostorová složitost algoritmu je O n( ,)kde n je počet objektů v trénovací zdrojové množině. Časová složitost je také O n , protože vzdálenost musí být počítána mezi testovaným objektem a všemi trénovacími. Není zde však vzít do úvahy čas nutný k vytvoření klasifikačního modelu. Proto je algoritmus kNN v tomto odlišný od většiny ostatních klasifikačních algoritmů, které mají poměrně složitou pasáž vytvoření klasifikačního modelu, ale velmi nenáročnou složitost samotné klasifikace testovaného dokumentu (Kumar, Wu, 2009). Schéma algoritmu například pro 5 nejbližších sousedů je znázorněno na 2.11:

2.11

44


Obrázek 8: Metoda k–nejbližších sousedů V případě ilustrace by testovanému subjektu byla obvykle přiřazena příslušnost ke třídě representovaná znakem „–”, protože 3 nejbližší sousedi spadají do stejné třídě, kdežto zbývající 2 sousedu patří do množiny „x”. Další teoretické základy algoritmus jsou k nalezení ve zdroji (Kumar, Wu, 2009) nebo (Abney, 2008). Support Vector Machines Support Vector Machines (neboli SVM ) zahrnuje obvykle Support Vector klasifikátor (Support Vector Classifier – SVC) a Support Vector Regressor (SVR) a patří mezi nejpřesnější a nejrobustnější algoritmy využívané v oblasti dolování z dat (Kumar, Wu, 2009). Za zakladatele algoritmu SVM je považován Vapnik, který s algoritmem přišel v roce 1990 (Vapnik, 2000). Metoda SVM prodělala poměrně znatelný vývoj od svého vzniku. Cílem klasifikátoru SVC je najít optimální nadrovinu mezi dvěma lineárně oddělitelnými množinami tak, aby mezi daty a nadrovinou byla vzdálenost co nejdelší. Na grafu 2.11 je znázorněna optimální nadrovina mezi daty ve dvourozměrném prostoru. Předpokládejme, že w je faktor váhy (weight factor), b je odchylka optimální nadroviny. Tato nadrovina může být definována jako (Kumar, Wu, 2009) wT x + b = 0

(13)

Žádaná geometrická vzdálenost r optimální nadroviny od bodu x je pak (Kumar, Wu, 2009): r = f racg(x)||w|| (14) kde g(x) = xT +b je diskriminační funkce (Kumar, Wu, 2009) definovaná nadrovinou. Také se nazývá v angličtině functional margin (Kumar, Wu, 2009).

2.11

45


V návaznosti na to se SVM snaží najít takové parametry w a b pro optimální nadrovinu, aby byla maximalizována separace okrajů (anglicky margin of separation) ρ (rovnice 15), která je dána nejkratší geometrickou vzdáleností r∗ od těchto dvou tříd, proto se SVM nazývá také v angličtině maximal margin classifier. Z rovnice 14 je zřejmé, že margin of separation je ρ = 2r∗ =

2 ||w||

(15)

Aby byla vzdálenost nadrovinu od okrajů co největší, snaží se SVC maximalizovat ρ s ohledem na w a b 2 w, b ||w|| takova, ze yi (wt xi ) ≥ 1, i = 1, ..., n max

V ilustraci 2.11 jsou znázorněny jak podpůrné vektory (support vectors), tak maximalizace okrajů (margin).

Obrázek 9: Znázornění Support Vector Machines Metoda SVM má silné základy ve statistice a obvykle si vystačí s poměrně malou trénovací množinou. Algoritmus je necitlivý k počtu dimenzí (Kumar, Wu, 2009). ( ) Operační složitost algoritmu je ve většině případů O n3 (Chapelle, Schölkopf, Zien, 2006). Informace o algoritmu SVM lze čerpat z odborné literatury (Kumar, Wu, 2009) a (Veropoulos, Campbell, Cristianini, 1999). Umělé neuronové sítě Umělé neuronové sítě (anglicky artificial neural networks) představují metody strojového učení, kde klasifikátor modeluje takovou funkci f (x), která je v rámci mož-

2.11

46


ností podobná způsobu uvažování lidského mozku. Algoritmus tak nemusí připomínat přímočarou logiku uvažování počítače. Tak jako lidský mozek obsahuje obrovské množství nervových buněk neuronů, které jsou navzájem propojeny tak, že každý neuron může být nervově spojen s mnoha ostatními, je podobně modelována neuronová síť. Celý tento systém tvoří velice komplexní síť, která je schopna určitým způsobem šířit signály. Podstata systému leží ve faktu, že pokud součet síly signálu vstupů do neuronu překročí určitou danou hranici (anglicky „threshold”), tak neuron vyšle signál i do všech svých výstupů (které zase vedou do jiných neuronů) (Borglin, 2011). Umělý neuron se v informatice nazývá perceptron. Síla signálu, který je schopen perceptron vyslat, bývá obvykle v rozsahu < 0, 1 >, anebo také < −1, 1 >. Tento výstupní signál je možné vyjádřit následující rovnicí 16 (Borglin, 2011). n (∑ ) wi xi + b y=Φ

(16)

i=1

kde y představuje výstupní signál, Φ je aktivační funkce, proměnná n představuje počet vstupů do perceptronu, wi je váha neuronové spojení i. xi je potom hodnota i-tého spojení a b tvoří hranici (threshold). Hodnota k nemusí být pouze konstantní (Borglin, 2011).

Obrázek 10: Model umělého neuronu – perceptronu Ilustrace 10 je velice elementární. V praxi se využívají vícevrstvé neuronové sítě (anglicky multilayer neural network), kde vynikne síla více perceptronů, které jsou spojené a pracují společně. Tyto perceptrony jsou organizovány do několika vrstev, kde každá vrstva bere vstup z předchozí vrstvy, aplikuje váhu a poté emituje signál do další vrstvy (pokud byly splněny určité podmínky nebo pokud nějaká další vrstva vůbec existuje) (Borglin, 2011). Ilustrace 11 znázorňuje vícevrstvou neuronovou síť.

2.11

47


Obrázek 11: Grafická reprezentace umělé neuronové sítě Expectation-Maximization EM je zkratkou pojmů Expectation-Maximization a tvoří velice obecný algoritmus, který je obecně aplikovatelný na jakákoliv nekompletní data. Algoritmus nabývá podle (Kumar, Wu, 2009) na popularitě především v posledních deseti letech. Algoritmus EM patří do rodiny iterativních algoritmů, kde jsou v každé iteraci provedeny dva kroky: 1. Expectation step (E-step), 2. Maximizační krok (Maximization step, M-step). Nechť je ⃗y = (y1T , ..., ynT ) vektor popisující známá kompletní data a ⃗z popisuje nekompletní data (Kumar, Wu, 2009). Vektor s kompletními daty je definován jako ⃗x = (y T , z T )T

(17)

Jedna z nevýhod algoritmu EM spočívá v tom, že neprodukuje automaticky odhad matice kovariance, popř. je tato konvergence velice pomalá. V některých aplikacích může být E- nebo M- krok analyticky nezvladatelný (Kumar, Wu, 2009). S dalšími informacemi o algoritmu Expectation-Maximization si autor dovoluje odkázat na odborný zdroj (Kumar, Wu, 2009). C4.5 Algoritmus C4.5 tvoří spíše množinou algoritmů než jeden. Algoritmy C4.5 jsou určeny pro řízené učení, kde se tyto metody naučí mapování (přiřazení) určité kolekce atributů určitých instancí (objektů) na konečnou množinu vzájemně exkluzivních tříd (Kumar, Wu, 2009). Algoritmy C4.5 spadají pod metody rozhodovacího stromu, viz 2.7.

2.11

48


Běžný vstup lze ilustrovat tabulkou 8, kde atributy tvoří jednotlivé dny v roce, počasí a podmínky okolního prostředí v daný den, a konečně pak binární atribut, který značí, zda v daný den hrál golf či ne. Tabulka je převzata ze zdroje (Kumar, Wu, 2009, str. 3). Tabulka 8: Příklad trénovacích dat algoritmu C4.5

Den

Počasí

Teplota (° F)

Vlhkost (%)

1 2 3 4 5

slunečno slunečno zataženo déšť …

85 80 83 70 …

85 90 78 96 …

Větrno? Třída Ne Ano Ne Ne …

Ne Ne Ano Ano …

Algoritmus C4.5 je založen na růstu stromu, kde kořen stromu tvoří nejprve výchozí danou množinu. Algoritmus poté rekurzivně rozděluje množinu na menší podmnožiny na základě testování jednotlivých atributů každého uzlu. Proces pokračuje tak dlouho, dokud nejsou všechny podmnožiny dostatečně homogenní (Kumar, Wu, 2009). Algoritmicky lze zapsat postup algoritmu takto: procedure C4 . 5 ( D ) D j e mnozina a t r i b u t u Tree := {} i f D j e ” c i s t e ” OR s p l n e n a u k o n c u j i c i podminka then terminate end i f f o r a l l a t t r i b u t e a ∈ D do Vypocitej informacne t e o r e t i c k e k r i t e r i a , pokud r o z d e l i m e a end f o r abest := N e j l e p s i a t r i b u t p o d l e v y s e v y p o c t e n y c h k r i t e r i i Tree := Vytvoreny r o z h o d o v a c i strom , k t e r y t e s t u j e abest j a k o k o r e n Dv := Indukovane podmnoziny z D z a l o z e n y na abest f o r add Dv do T reev := C4 . 5 ( Dv ) P r i p o j T reev ke k o r e s p o n d u j i c i v e t v i stromu Tree end f o r return Tree

2.12

49

Normalizační algoritmy

Kde Tree tvoří výsledný indukční strom. Termín „ciste” označuje stav, kdy pro vstupní argument D platí, že všechny instance v této podmnožině patří do stejné třídy. Pokud je tento (anebo jiný určený) předpoklad splněn, růst stromu je zastaven – volání terminate. Růst stromu je zde řešen rekurzivním voláním metody C4.5.

2.12

Normalizační algoritmy

Normalizačními algoritmy míní autor práce metody vyrovnávání se s nulovými hodnotami, popř. řešení existence nulových hodnot, které jsou známy z teorie statistiky. Aditivní Laplaceovská (neboli také aditivní) transformace je velice jednoduchá metoda normalizace takový množin hodnot, kde se vyskytují nějaké nulové výrazy. Za zakladatele této konkrétní je považován matematik Laplace (Manning, Raghavan, Schütze, 2008). Předpokládejme, že máme k dispozici vektor hodnot ⃗x = (x0 , x1 , . . . , xd ), které mohou tvořit například distribuci určitých hodnot pro jednotlivé termy v textové entitě. Mějme funkční hodnotu f , kde je f (x) rovno f (x) =

xi N

(18)

kde N je jmenovatelem v předchozím jednoduchém zlomku. f (x) může nabývat nulové hodnoty pokud je i xi rovno nule. Pokud by hodnota f (x) násobila nějaký jiný výraz, nutně by výsledný výraz musel být také nulový, což obyčejně není u klasifikačních (nebo statistických) metod žádoucí. Aditivní metoda proto transformuje f (x) do podoby rovnice 19 podle zdroje (Manning, Raghavan, Schütze, 2008). f (x) =

xi + α N +α·d

(19)

kde pro hodnotu α platí formálně α ≥ 0; v praxi většinou však α > 0, protože pokud by α bylo rovno 0, nejedná se o normalizační techniku (Manning, Raghavan, Schütze, 2008). Obyčejně platí, že α ∈ (0, 1 >, d je pak mohutnost vektoru ⃗x. V závěrečné práci je postaveno, že α = 1. Ostatní normalizační metody Mezi ostatní normalizační metody je vhodné zařadit i prosté připočtení konstanty k k hodnotě funkční hodnoty f (x) za předpokladu, že f (x) = 0. Formálně by tedy platila indukce f (x) = 0 ⇒ f (x) = f (x) + 1 (20)

2.13

Evaluační metriky strojového učení

2.13

50


TP, FP, TN, FN TP (True Positive), FP (False Positive), TN (True Negative), TN (True Negative) jsou výkonnostní metriky klasifikačních algoritmů v rámci binární klasifikace (Veropoulos, Campbell, Cristianini, 1999). Pro vysvětlení nechť je vznesen předpoklad, že existují dokumenty, které jsou zařazeny buď do množiny positivních, anebo negativních dokumentů (na názvu třídy nezáleží, pojmenování tříd může být samozřejmě libovolné). Metriky pak značí: • True Positive – značí počet dokumentů, které byly po klasifikačním procesu označeny příslušností k positivní třídě a ve skutečnosti také patří do positivní třídy, • False Positive – představuje počet dokumentů, které byly označeny jako positivní, ale správně patří do negativní množiny, • True Negative – určuje počet dokumentů, které byly označeny jako negativní a také patří do negativní množiny, • False Negative – počet dokumentů označených klasifikátorem jako negativní, ale správně spadají do positivní množiny. Accuracy Accuracy je jednou z nejpoužívanějších metrik hodnocení klasifikátorů (Brodersen et al, 2010). Jestliže máme k dispozici klasifikátor c, u něhož známe správné zařazení objektů do svých tříd (množin) – tedy jsou k dispozici ukazatele True Positive (T P (c)), False Positive (F P (c)), True Negative (T N (c)), False Negative(F N (c)), hodnota Accuracy Acc klasifikátoru c lze vyjádřit jednoduchým vzorcem (Brodersen et al, 2010) Acc (c) =

T P (c) + T N (c) T P (c) + F P (c) + F N (c) + T N (c)

(21)

Hodnota Accuracy tedy nabývá hodnot v intervalu < 0, 1 >, přičemž 1 znamená, že klasifikátor korektně klasifikoval všechny vstupní instance. Diplomová práce využívá primárně právě metriku Accuracy, vynásobenou kvůli procentuálnímu vyjádření číslem 100. Precision Precision je další hojně používanou metrikou strojového učení. Na rozdíl od Accuracy se jedná v podstatě o poměr správně klasifikovaných True Positives (T P (c)) vůči všem „positivním” dokumentům (anebo dokumentům

2.13

51


v binární klasifikaci patřící ke stejné právě jedné třídě). Předpokládejme stejné značení jako v předchozím odstavci u Accuracy, pak je Precision P re(c) definována jako (Brodersen et al, 2010): P re(c) =

T P (c) T P (c) + F P (c)

(22)

Hodnocení shlukování Existuje mnoho známých metod či ukazatelů, které se dají použít k ohodnocení (změření) kvality výsledků shlukování. Mezi ty nejznámější patří (Dařena, 2011, str. 33-34): • entropie (anglicky entropy), • čistota (purity), • přesnost (accuracy), • F-measure. Entropie je pravděpodobně nejpoužívanější hledisko hodnocení v rámci shlukování. Je to do jisté míry dáno faktem, že entropie je hojně používána i v jiných odvětvích než je informatika. Entropie se dá definovat jako množství neurčitosti (Wang, 2009). Hodnocení kvality za použití entropie je v rámci shlukování ve většině případů komplexnější, než použití čistoty (purity), protože je více vypovídající (Bavi et al., 2010; Strehl, Ghosh, Mooney, 2000). V autorově bakalářské práci (Burda, 2012) je použita vážená entropie, která je definována jako vážená suma jednotlivých entropií konkrétních shluků (Karypis, 2003). Entropie E(Sr ) pro jednotlivé shluky je dána vzorcem podle (Zhao, Karypsis, 2006): q 1 ∑ nir ni E(Sr ) = − log r (23) log q i=1 nr nr V rovnici 23 představuje Sr určitý shluk, q znamená celkový počet tříd v kolekci, nr je počet dokumentů v r-tém shluku (velikost shluku), nir je počet dokumentů i-té třídy, které byly přiřazeny do r-tého shluku, i pak tvoří i-tý dokument. Celková vážená entropie E je pak definována sumou jednotlivých entropií (Zhao, Karypsis, 2006): k ∑ nr E= E(Sr ) (24) n r=1 kde k je počet shluků, nr zastupuje počet dokumentů v r-tém shluku a n je celkový počet dokumentů v kolekci.

2.14

Kolekce dat

52

V ideálním případě by shluk obsahoval dokumenty náležící právě do jedné třídy a entropie E by byla rovna jedné. Vztah entropie a pravděpodobnosti samozřejmě není lineární a v určitých hodnotách může docházet ke skokovým změnám hodnot. Jelikož další měřítka hodnocení kvality shlukování buďto nejsou v práci použita, anebo podle názoru autora nejsou k práci relevantní, nejsou zde popsána. Tyto ukazatele jsou definovány a popsány v odborné literatuře (Dařena, 2011; Srivastava, Sahami, 2009).

2.14

Kolekce dat

Obecné kolekce Kolekce dat může být definována jako množina dat. V kontextu dolování z textů, se kolekcí dat rozumí množina textových dat. Na internetu existuje velké množství volně dostupných kolekcí dat pro nekomerční použití – například pro experimenty. Jednotlivé dokumenty jsou v kolekcích zařazeny do určité třídy – skupiny, takže je možné empiricky ověřit výsledky klasifikace nebo shlukování. Mezi nejznámější zástupce volně dostupných kolekcí patří (Srivastava, Sahami, 2009): 20 Newsgroups, Classic3, Simulated, Slashdot a další. Diplomová práce se zabývá kolekcí dat obsahující recenze na konkrétní hotely v anglickém jazyce, konkrétněji jsou data představena v kapitole Zdrojová data.

3

ANALÝZA SOUČASNÉHO STAVU

3

53

Analýza současného stavu

3.1

Aktuální dostupné nástroje

V současné době je shlukování velmi progresivní podmnožinou odvětví dolování z dat. Poptávka po systémech pro shlukování dat existuje především v soukromé sféře, kde shlukování textových dokumentů již našlo svoje ekonomické uplatnění. Typickým příkladem této možnosti je osoba hoteliéra, který má k dispozici určitou rozsáhlou množinu ohlasů (reakcí) svých hostů, a jeho hlavním cílem je zjistit konkrétní pozitiva nebo naopak negativa. Algoritmy řízeného strojového učení jsou využívány v praxi ještě častěji, i takový filtr pro nevyžádanou poštu často implementuje interně určitý klasifikační algoritmus. Shlukovací analýzu úspěšně používají mnohé státní i soukromé organizace (Anon, 2012), shlukování se dá provádět online i offline (Zhang, Dong, 2004). Příkladem online shlukování může být portál americké vlády2 , kde je shlukování aplikováno na výsledky vyhledávání, které jsou automaticky seskupeny do různých skupin (kategorií) (Anon, 2012). Mnohé specializované vyhledávače nebo internetové obchody taktéž využívají shlukování textů online pro vytvoření automatických skupin (v tomto případě kategorií bez názvu), kde každý shluk obsahuje určité výsledky k hledané frázi (Anon, 2012; Zhang, Dong, 2004). Níže si autor dovoluje představit aktuální dostupné softwarové systémy, jež poskytují algoritmy řízeného, částečně řízeného, neřízeného učení, anebo jejich kombinaci. V současné době je mnoho dostupných programových systémů. Část zmíněných programových nástrojů byla čerpána z (Yang, Zhu, 2013). Nástroj pro shlukovací analýzu, jež je použit v této práci, je systém Cluto (viz 3.1). Weka Mezi další volně dostupné nástroje patří software Weka3 . Tento softwarový systém poskytuje i rozsáhlé množství algoritmů jak řízeného, tak neřízeného učení. Jedná se tedy o velice komplexní programový systém poskytující algoritmy a operace strojového učení. Weka v podstatě poskytuje algoritmy pro před-zpracování dat, klasifikaci, regresi, asociační pravidla, shlukování a vizualizaci. Mezi přednosti systému patří modularita, kdy je možné funkcionalitu rozšiřovat o volně dostupné moduly. Další výhodou je možnost přímé integrace komponent Weky (algoritmy, klasifikátory) s programovacím jazykem Java. Je proto pro vývojáře jednoduché provázat svůj zdrojový kód s komponenty systému Weka a provádět tak komplexní operace a výstupy. 2 3

Dostupný z: http://www.usa.gov Dostupný z: http://www.cs.waikato.ac.nz/ml/weka/

3.1


54

Systém Weka využívá pro strojového učení z textových dat formát ARFF (popsán na straně 31). Fakt, že systém Weka je celý implementován v jazyku Java, činí systému problémy při zpracování většího množství dat (například klasifikace statisíců dokumentů) z důvodu charakteru interpretovaného spuštění Javy. Cluster 3.0 Software Cluster 3.0 4 , který byl původně vytvořen Michaelem Eisenem (Eisen, 2013), je dalším zástupcem volně dostupného software. Cluster 3.0 je k dispozici pro většinu známých platforem a jeho poslední verze je z konce roku 2010. SVMLight SVMLight je nástroj zaměřený pouze na jeden klasifikační algoritmus – Support Vector Machines (viz strana 44), ale je implementován precizně. Program je napsán v jazyce C, je výborně optimalizovaný (využívá optimalizované algoritmy, úsporné matice, cache) a umožňuje jako klasifikační, tak regresní výpočty (Joachims, 2008). PASW Modeler Komplexní framework PASW Modeler (dříve známý jako SPSS Modeler) 5 integruje celou řadu nástrojů strojového učení, mimo jiné i algoritmy známé jako Apriori, GRI, CARMA, apod. Programový systém není volně dostupný, je placený a využívá se v komerční a akademické sféře (zde pro výukové účely). Software umožňuje širokou škálu vizualizace dat, integruje probabilistické metody a mnoho způsobů extrakce dat. Systém Cluto Protože pro algoritmus učení bez učitele je zde využit jediný programový nástroj – systém Cluto – je mu zde vyhrazena samostatná část. Jedná se o hojně používaný nástroj pro shlukovací analýzu. Přestože poslední verze je z roku 2006, stále se systém těší oblibě (především v akademické obci). Jedná se pravděpodobně o nejrozšířenější nástroj pro shlukování, který je volně dostupný6 , autorem je George Karypis. Výhodou programu Cluto je jeho multiplatformní charakter – spustitelné verze jsou k dispozici na Microsoft Windows, Linux i na systémy rodiny OS X. Systém Cluto obsahuje ještě dvě nadstavby – rozšíření; jedná se o gCluto a wCluto. gCluto je ve své podstatě grafickou nadstavbou programu Cluto. Ne4

Dostupný z: http://bonsai.hgc.jp/ mdehoon/software/cluster/software.htm Informace k dispozici na http://www.spss.com.hk/software/modeling/modeler 6 Dostupný na: http://glaros.dtc.umn.edu/gkhome/views/cluto 5

3.1


55

přidává prakticky žádnou novou funkcionalitu, pouze grafické uživatelské rozhraní. wCluto tvoří nadstavbu zaměřenou na webovou analýzu (Karypis, 2006). Možnosti parametrizace systému jsou široké, patří mezi ně mimo jiné: • množství shlukovacích algoritmů (k-means, repeated bisection, …), • řada metrik podobnosti (kosinová, euklidovská vzdálenost, …), • převod vektorových reprezentací, • zobrazení signifikantních termů pro shluk, • široké možnosti vizualizace řešení, shlukovacího procesu a shluků. Aleph Aleph Machine Learning Framework je multiplatformní programový systém, jež poskytuje metody řízeného a částečně řízeného učení. Škála jeho funkcí je poměrně rozsáhlá a zahrnuje například (Iria, 2009): • logistickou lineární regresi, • statistické metody, • propagace označení (angl. label) objektu v grafu, • SVM, • a další. Programový systém však neintegruje základní klasifikační algoritmy, jako je k– nejbližších sousedů, či Naivní Bayes nebo Multinomiální Naivní Bayes. Poslední dva zmíněné algoritmy jsou obzvlášť vhodné pro strojové učení nad použitými zdrojovými textovými daty v přirozeném jazyce. Aleph je implementován v jazyce Java a mohou zde nastat potíže se zpracováním skutečně rozsáhlých dat. Software je však velice dobře dokumentován. Dualist Dualist je systém využívající částečně řízeného učení a je zaměřen na textová data (Settles, 2012). Algoritmus poskytuje velice omezenou množinu klasifikátorů pro částečně řízené učení. Zajímavý je tím, že je platformě nezávislý, protože běží ve webovém prohlížeči a umožňuje vysokou míru interaktivity od uživatele, práce s ním je za pomocí GUI7 velice pohodlná. Nevýhodami jsou omezená množina klasifikačních algoritmů a relativní pomalá operační rychlost způsobená charakterem nástroje. 7

Graphical User Interface, grafické uživatelské rozhraní

3.1


56

Ostatní programové systémy Známý matematický systém Matlab také integruje nástroje a algoritmy strojového učení, ovšem již není volně dostupný. Software BayesiaLab, jehož funkcionalita je velmi rozsáhlá, je určen pro komerční použití. BayesiaLab je zaměřen spíše na dolování z dat a pozdější analýzu dat (Bayesia, 2012). Fast GP-LVM je volně dostupný programový skript, jež poskytuje částečně řízené učení za využití Gausového procesu. Nejedená se o samostatně spustitelný nástroj, jedná se o skript pro Matlab. Waffles je další z řady nástrojů s podporou strojového učení implementovaný v jazyce C++. Program umožňuje základní metody řízeného učení, shlukování, vizualizaci, ale i práci se zvukovými daty, transformační skripty (promíchání řádků, výměna hodnot ve sloupcích za hodnoty v řádcích atp.) (Gashler, Moyer, 2005). Aplikace má přístupný zdrojový kód. Autor práce nenašel programový nástroj, který by umožňoval ucelenou práci s metodami jak řízeného, tak částečně řízeného učení, se zaměřením na textová data – tedy přímou podporu formátů CSV a ARFF.

4

ZDROJOVÁ DATA

4 4.1

57

Zdrojová data Použitá data

Obecné informace Použitá data pochází z rozsáhlé množiny textových příspěvků portálu booking.com. Tuto kolekci dat tvoří jednotlivé recenze nejrůznějších hotelů po celém světě, přičemž recenzi na hotel může napsat po vyplnění data pobytu kdokoliv. Nejedná se o volně dostupnou kolekci dat v pravém slova smyslu, protože množina dat neexistuje nikde volně ke stažení „pohromadě” – všechna data byla automatizovaně získána za využití skriptovacího jazyka. Tato základní extrakce dat byla provedena panem docentem Františkem Dařenou. Celkový počet příspěvků, jež měl autor práce k dispozici, tvoří zhruba dva miliony anglických příspěvků. Uživatel ještě v recenzi přidává k textovému popisu ohodnocení, které může být neutrální (neutrální recenze nejsou v práci použity), positivní (zcela positivní, anebo spíše positivní), anebo negativní (spíše negativní nebo zcela negativní). Je nutno podotknout, že příspěvky v určité skupině (třídě) jsou navzájem disjunktní, tedy patří právě do jedné třídy – buďto positivní, anebo negativní. Jedná o reálná textová data v přirozeném jazyce, proto obsahují příspěvky mnoho překlepů, gramatických nebo sémantických chyb, či jiných nejasností. Charakter textových dat Obě množiny dat mají velmi podobné vlastnosti jako je průměrná délka příspěvku, hodnota rozptylu, atd. Obsahují i typicky velmi mnoho záporů před přídavnými jmény (positivní množina obsahuje velmi mnoho příspěvků, kde se nachází term „good” – přídavné jméno „dobrý”, ale i v negativní množině je mnoho výskytu tohoto slova např. ve formách „not good”, tedy přídavné jméno „nedobrý”). Statistické informace Je velmi zajímavé porovnat určité statistické vlastnosti použitých zdrojových dat, jako je průměrná délka příspěvku, nejdelší příspěvek v konkrétní třídě, rozptyl délky příspěvků, atp. Některé z těchto statistických informací pro třídu positivních a negativních příspěvků jsou uvedeny dále. Tabulka 9 uvádí positivní příspěvky.

4.1

58

Použitá data

Tabulka 9: Statistické informace pro příspěvky ze skupiny positivních ohlasů

Celkem příspěvků Nejdelší příspěvek Průměrná délka příspěvku Rozptyl

1 190 949 391 slov 22 slov 403

Statistické informace pro dokumenty s negativním vyjádřením jsou uvedeny v tabulce 10. Tabulka 10: Statistické informace pro negativní příspěvky

Celkem příspěvků Nejdelší příspěvek Průměrná délka příspěvku Rozptyl

741 092 396 slov 26 slov 618

Ukázka dat V rámci této podkapitoly jsou prezentovány zástupci příspěvků obou zdrojových množin. Jedná se o formu, v jaké byla data extrahována z prostředí internetu a jsou na nich již provedeny základní operace jako převod na malá písmena a odstranění interpunkce. Jedná se o příklady víceméně typických zástupců zdrojových množin.

what i found really good was receiving a call prior to our arrival to say that they could not accomdate all oiur requirements and we were free to find somewhere else to stay if this was not to our likeing. once we arrived we found hotel staff where nice, helpful and accomodating. the rooms were spacious and comfy with a nice walk-in shower. breakfast was lovely and worthwhile. would come back again.

we liked the high standard of service from hotel staff. the staff were very attentative and thorough. the room was huge and furnished to a very high standard. all the comforts you could want.

staff were friendly and helpful. clean and comfortable guest house.

4.1

Použitá data

lovely hotel in an idyllic location with a fabulous view overlooking the harbour. every member of staff was friendly and no request was too much trouble. our room was serviced regularly. the included breakfast was lovely. i would definitely recommend this hotel to my friends!

husband liked the way all hand pump beers were eccelently kept also enjoyed relaxed meal first evening a little short on hot water

there was nothing we did not like and would stay there again.

rooms need updating and shower poor. also very difficult to find.

I dont like buffet breafast only warm no table service for tea coffee after cereal went for cooked breafast and staff took our knife forks and juice away but with alot of breakfasts to cook it does make senseto do it that way

59

5

METODIKA ŘEŠENÍ

5 5.1

60

Metodika řešení Postup

V rámci diplomové práce byla provedena řada experimentů s textovými daty v anglickém přirozeném jazyce. Experimenty byly prováděny na dokumentech, které patřily ke dvěma různým třídách – jednalo se o úlohy binárního strojového učení. Ve všech případech byla náhodně vybrána určitá množina textových dat tvořená podmnožinami trénovacích a testovacích dat v určitém počtu. Parametrizace jako počet dokumentů a poměr zastoupení tříd se samozřejmě v rámci diplomové práce měnila, v rámci konkrétního experimentu je však konstantní. Na každé této množině byly provedeny metody strojového učení: 1. řízeného, 2. částečně řízeného, 3. neřízeného. Množina trénovacích a testovacích dat je vzájemně disjunktní. V rámci učení bez učitele (unsupervised learning) se v kontextu práce jedná o shlukování, konkrétně za využití algoritmu k-means s určitou parametrizací, která se ukázala na zvolených textových datech jako nejvýkonnější (Žižka, Burda, Dařena, 2012). Cílem diplomové práce bylo porovnání výkonnosti, vhodnosti a přesnosti metod strojového učení, ale vzhledem k tomu, že bylo empiricky zjištěno, že shlukování, dle očekávání autora, dosahuje nejhorších výsledků, nebyl důvod provádět experimenty s jinými parametry pro shlukování. To je také spolu se závěry článku (Žižka, Burda, Dařena, 2012) důvodem, proč je shlukování provedeno pouze s jedinou parametrizací. Částečně řízené učení je v diplomové práci reprezentováno dvěma hlavními proudy: • Self-training, • Co-training. Implementace metody Self-training je zvolena standardní tak, jak je popsána v teoretické části v oddílu 2.3, strana 19. Co-training vyžaduje dva různé pohledy na zdrojová data. Po konzultaci s vedoucím práce zvolil autor následující pohledy na textový dokument, a to z následujících pohledů na jednotlivá slova: 1. hledisko termů s vyšší absolutní frekvencí, 2. termy s nižší absolutní frekvencí.

5.1

61

Postup

Implementačně výše uvedené pohledy implikují fakt, že algoritmus Co-training vyprodukuje klasifikátor C, kde symbolicky platí, že: C = C1 ∪ C2

(25)

kde C1 tvoří naučený klasifikátor, který natrénuje takovou funkci f1 (x), kde jsou do úvahy brány pouze takové termy, které jsou v horní polovině žebříčku absolutní četnosti z hlediska množiny trénovacích dokumentů. Analogicky C2 je klasifikátor, který při procesu učení klasifikační funkce f2 (x) bere do úvahy pouze termy s nižší absolutní frekvencí termů, anebo takovou frekvencí, jež tvoří přesně střed pomyslného žebříčku četnosti. Implementace vzájemného naučení obou klasifikátorů je řešena následujícím způsobem. Mějme klasifikátor C1 a dokument D z určité třídy. Jedná se o binární klasifikaci, takže předpokládejme určitou pravděpodobnost příslušnosti dokumentu D do třídy s označením A. Tedy může například platit, že: P1 (A) = 0, 75. Analogicky klasifikátor C2 představuje např. P2 (A) = 0, 25. Jedná se o operaci sjednocení, která reprezentuje vzájemné naučení obou klasifikátorů, proto bude pro výsledný klasifikátor C, dokument D a příslušnost P k třídě A platit: P (A) = P1 (A) · P2 (A)

(26)

Pro hodnoty uvedené výše dostáváme: P (A) = 0, 25 · 0, 75 =

3 16

(27)

Každý experiment (měření) konkrétního učícího algoritmu nad zdrojovými daty byl opakován v n opakováních, kde n = 4. Při každém opakování byla náhodně vybrána nová trénovací množina, která zachovává poměr a zastoupení objektů. Testovací množina byla v rámci experimentu vždy konstantní. V každém sudém (tj. 2. a 4.) měření jsou odstraněna stop-slova, viz strana 6.1 a 2.5. Při každém experimentu (měření) bylo potřeba provést následující kroky: 1. provést náhodnou selekci dokumentů v potřebném počtu a poměru rozložení tříd, 2. transformovat data do potřebné interní reprezentace, 3. provést výše uvedené metody strojového učení a vyhodnotit dosažené výsledky na konkrétní množině dat. Textové dokumenty byly převáděny v rámci transformace dat (mimo jiné) do formátů CSV (sekce 2.7) nebo ARFF (popsáno v 2.7).

5.2

5.2

62

Zvolené množiny dat


Experimentálně byly zvoleny určité množiny a poměry dat, na kterých budou prováděny algoritmy strojového učení. V tabulce 11 jsou uvedeny konkrétní poměry počtu dokumentů pro dokumenty patřící do dvou různých tříd. Výraz „Poměr” znamená poměr počtu dokumentů (positivní ku negativním) a „Počet” je pak celkový počet dokumentů vstupujících do procesu strojového učení. Tabulka 11: Použité poměry počtu dokumentů pro učící algoritmy

Poměr

Počet

80:1 002 500:11 632 500:32 191

1 082 12 132 32 691

Mohutnost dat přechází postupně z menších množin do větších. Příprava dat Příprava dat je kardinálním krokem celého procesu učícího procesu, protože od kvality přípravy dat se odvíjí další postup a i dosažené výsledky. Pro přípravu dat bylo použito množství skriptů, jejichž autorem je (až na výjimku v podobě skriptu „doc2mat.pl”) autor diplomové práce. Skripty jsou implementovány v platformě nezávislém interpretovaném jazyku Perl (sekce 5.5, strana 68). Konkrétní parametrizace příkazů a skriptů je uvedena dále. Pojmem „surový” soubor rozumí autor takový textový soubor, kde každý řádek souboru představuje právě jeden příspěvek (dokument), který je ukončen znakem nového řádku. extract.pl Skript vybere náhodným způsobem předem zvolený počet dokumentů z určeného souboru a vybrané dokumenty zkopíruje do cílového adresáře. doc2mat.pl Skript převede „surový” textový soubor do vektorové reprezentace v podobě maticového souboru, se kterým pracuje programový systém Cluto. Tento skript je potřebný pouze pro operaci shlukování. transform.pl Skript, který bere za vstup soubor s textovými dokumenty. Skript převede veškeré dokumenty do zvoleného textového formátu (buď CSV, anebo ARFF).

5.2


63

svm_prepare.pl Cílem skriptu je převod trénovací a testovací množiny dokumentů, které jsou již ve formátu CSV nebo ARFF, do formátu používaného programovým systémem SVMLight (sekce 3.1). randomize.pl Skript provede randomizaci textových dokumentů – je náhodně změněno pořadí dokumentů v množině dat. Výběr dat Protože zvolená textová data v přirozeném jazyce mohou spadat pouze do dvou sémantických tříd (positivní, anebo negativní), bylo možné se soustředit pouze na správný poměr zastoupení dokumentů. Ze všech zdrojových dat byly dále odstraněny termy, které sestávají pouze z numerických hodnot, a dále všechny termy, jejichž délka je kratší než 3 znaky. Výběr dat z konkrétních dvou sémantických tříd je prováděn náhodně a zajišťuje ho skript, jenž nabývá následující parametrizace. Skript se spouští příkazem: e x t r a c t . pl ⟨zdrojovy_soubor⟩ ⟨cilovy_soubor⟩ ⟨pocet_positivni⟩ ⟨pocet_negativni⟩ kde zdrojovy_soubor je soubor, který obsahuje dokumenty jakékoliv třídy, pocet_positivni je počet dokumentů pro výběr z třídy positivních příspěvků (analogicky naopak i pocet_negativni), cilovy_soubor pak představuje cílovou cestu, kam jsou vybrané dokumenty umístěny. Převod dokumentů do formy CSV nebo ARFF Předchozí krok zajišťuje výběr textových dat. Tento krok zajistí, aby každý dokument (příspěvek) byl převeden do formátu CSV nebo ARFF. Parametrizace skriptu „transform.pl”: transform . pl ⟨ z d r o j ⟩ ⟨ c i l ⟩ ⟨format⟩ ⟨odstranit_stop_slova⟩ kde zdroj tvoří zdrojový soubor, kde se nachází zvolená množina dokumentů. Trénovací a testovací množina dokumentů je ukládána separátně, skript proto bude obyčejně spuštěn dvakrát – jednou pro trénovací množinu a podruhé pro testovací. cil je cesta k výslednému souboru, parametr format může nabývat buď hodnot „csv”, anebo „arff”. Parametr odstranit_stop_slova buď může být nahrazen logickou nulou, anebo jedničkou, značící ponechání, resp. odstranění stop-slov (oddíl 2.5). Množina stop-slov je přiložena ve formě textového souboru „stop-words.txt”, který musí existovat v aktuálním adresáři, odkud je skript spuštěn. Randomizace dokumentů V tomto kroku jsou dokumenty ve zdrojovém souboru náhodně promíchány, aby se minimalizovalo riziko ovlivnění procesu strojového učení.

5.2


64

Dále je vytvořen textový soubor, který vhodně popisuje příslušnost konkrétních testovaných dokumentů k různým třídám (oblastem). Tento soubor je vstupním souborem pro systém Cluto a slouží k zpětné kontrole kvality shlukování (např. možnost určení entropie, atp.). rand omi ze . p l ⟨ z d r o j _ c i l ⟩ Prvek zdroj_cil určuje zdrojový i cílový adresář, kde se nachází „surový” soubor a taktéž adresář, kde má být vytvořen výstupní soubor. Převod do vektorové reprezentace Převod do vektorové reprezentace formátu document-term (viz 2.6) je důležitý krok, který vede k vytvoření vektorového souboru, který vyžaduje software Cluto. doc2mat . p l ⟨ z d r o j _ s o u b o r ⟩ ( parametry ) ⟨ c i l _ s o u b o r ⟩ Zdroj_soubor je zdrojový „surový” soubor (viz předchozí krok), cil_soubor je cílový soubor obsahující vektorovou reprezentaci množiny všech dokumentů. Soubor s termy je taktéž vytvořen a nese stejný název, ovšem liší se příponou. Výraz parametry představuje parametrizaci skriptu. Skript byl vždy spouštěn s parametry: -nlskip=1, -skipnumeric, -nostem Parametr nlskip=1 značí, že skript má pro vytvoření vektorové reprezentace přeskakovat první sloupec – ten obsahuje meta informaci o konkrétním řádku (příslušnosti dokumentu k třídě). Nastavení skipnumeric zapíná přeskakování termů, které jsou tvořeny pouze číslicemi. Poslední parametr nostem vypíná algoritmus stemmingu, který je dodávaný standardně se skriptem. Příprava pro algoritmus SVM Pro účely striktního vstupu, který požaduje programový systém SVMLight, byl vytvořen skript, do kterého vstupuje cesta k trénovacímu a testovacímu souboru, a minimální délka slova (v rámci této práce nastavena minimální délka slova konstantně na hodnotu 3). Skript vytvoří pro trénovací i testovací množinu ve zdrojovém adresáři ekvivalent dat v požadovaném formátu. Tato data jsou umístěna stejně jako zdrojová data, ale mají příponu „dat”. Skript se spouští následovně: svm_prepare . p l ⟨ t r _ s o u b o r ⟩ ⟨ t s t _ s o u b o r ⟩ ⟨min_delka⟩ kde tr_soubor a tst_soubor tvoří zdrojové soubory trénovací a testovací množiny. min_delka představuje minimální délku slova, aby bylo slovo vzato v potaz.

5.3

Proces řízeného a částečně řízeného učení

65

Zjištění dodatečných informací V tomto kroku byly prováděny určité dodatečné operace se zdrojovými daty. Jedná se především o zjištění nejrůznějších statistických informací, které jsou uvedeny v části 4.1 – nejdelší příspěvek, průměrný počet slov příspěvku, rozptyl, atd.

5.3

Proces řízeného a částečně řízeného učení

Programový nástroj s podporou řízeného a částečně řízeného učení, který vznikl v rámci diplomové práce, využívá jednotný vstup dat v podobě souboru s názvem „params.txt”, který musí být umístěn ve stejném adresáři jako spustitelný soubor programu. Konkrétní forma vstupního souboru je uvedena v příloze práce na straně 94. Vstupy Vstupy do programového systému lze charakterizovat jako • cesta k trénovací množině dat (formát CSV nebo ARFF), • cesta k souboru s testovací množinou dat (formát CSV nebo ARFF), • forma strojového učení (řízené, částečně řízené, neřízené), • zvolený klasifikátor C (Naivní Bayes, Mutinomiální Naivní Bayes, k–nejbližších sousedů, SVM), • způsob normalizace nulových hodnot (viz 2.12 na straně 49), • minimální délka termu (slova), aby byl brán v potaz – v rámci práce nastaveno na hodnotu 3, • volitelně logování do souboru, • volitelně tvorba maticového souboru s termy v reprezentace TP (viz 2.6), • specifická parametrizace pro konkrétní klasifikátor (např. hodnota N u klasifikátoru kNN ). Výstupy Výstup programového systému je realizován textovým souborem output.txt. Výstup zahrnuje: • parametrizaci spuštění (měření), • počet dokumentů a termů, • metriku Accuracy (část 2.13), • další odvozené metriky – True Positives, True Negatives, atp. (oddíl 2.13),

5.4

Neřízené učení

66

• seznam testovacích dokumentů s dílčími pravděpodobnostmi příslušnosti ke konkrétní třídě a třídu i, kterou dokumentu přiřadil klasifikátor C.

5.4

Neřízené učení

V tomto oddíle autor popisuje vstupy a výstupy programového systému pro shlukování – Cluto. Vstupy Vstupy do systému Cluto tvoří: • soubor vektorové reprezentace (přípona .mat), • soubor s popisy řádků (s příponou .rlabel), • soubor s popisem sloupců (soubor má příponu .clabel), • soubor kontrolních tříd (přípona .rclass). Všechny soubory spolu souvisí a tvoří jednolitý vstup do systému. Soubor s popisy řádků tvoří jednotlivé termy. Popisem sloupců se rozumí určitá meta informace o souboru na konkrétním (právě jednom) řádku. Jedná se o identifikátor příslušnosti dokumentu k třídě – např. „P” jako „positivní příspěvky”. Pro samotnou shlukovací analýzu je povinný pouze soubor s vektorovou reprezentací. Ostatní soubory slouží k zjištění dalších informací o shlukování (nejčastější termy, entropie, apod.). Další soubory tvoří textový soubor s popisem řádků, soubor s popisem sloupců a soubor s třídami, do kterých jednotlivé dokumenty náleží. Tento poslední soubor je zde pro kontrolu kvality shlukování a s jeho pomocí je odvozována entropie a další údaje. Systém se spouští spustitelným souborem vcluster (u platformy Windows s příponou „exe”). Program je možné suplovat řadou nepovinných parametrů; základní syntaxe při spuštění je však v c l u s t e r ( parametry ) ⟨ v e k t o r o v y _ s o u b o r ⟩ ⟨ p o c e t _ s h l u k u ⟩ kde parametry představují konkrétní parametrizaci shlukování, vektorovy_soubor je soubor s document-term vektorovou reprezentací jednotlivých dokumentů ve formě matice (jeden řádek je tvořen jednou vektorovou reprezentací) a počet_shluku je počet požadovaných shluků. parametry mohou zastupovat pestrou škálu nastavení, parametrizace může vypadat například následovně: v c l u s t e r −clmethod=rb s i n=c o s i n e −s h o w f e a t u r e s − r c l a s s f i l e =./ c l a s s e s . r c l a s s . / data . mat 2

5.4

Neřízené učení

67

Výše uvedený zápis znamená použití algoritmu repeated bisection (zkratka „rb”), použití kosinové metriky podobnosti a zobrazení signifikantních termů shlukovacího procesu. Hlavním vstupem je vektorový soubor „data.mat”, soubor s kontrolními třídami (příslušností dokumentů ke třídám) je k dispozici v podobě „classes.rclass”. Požadovaný počet shluků je 2, k dispozici jsou dva druhy dokumentů. Cluto poskytuje vlastní knihovnu funkcí, která umožňuje programátorům třetích stran využití veškerých aplikačních funkcí programu ve svých vlastních programech. V diplomové práci byla použita základní textová verze 2.1.2 z roku 2006. Výstupy Mezi výstupy systému Cluto patří: • entropie a čistota, • vnitřní podobnost, • velikost shluků, • konkrétní dokumenty v každém shluku, • další množina informací o proběhlém shlukovacím procesu. Sledované ukazatele V rámci bakalářské práce bylo za pomocí experimentů sledováno několik ukazatelů. Mezi sledované veličiny patřily: • vliv shlukovacích algoritmů na kvalitu shlukování, • dopad metrik podobnosti, • vliv kriteriálních funkcí, • kvalita shlukování, • další ukazatele (poměr/počet dokumentů v jednotlivých shlucích apod.). Aby byla zachována konzistence využitých metrik i v diplomové práci, k hodnocení účinnosti shlukování je využito hledisko Accuracy, viz 2.13. Shlukovací algoritmy Mezi testované algoritmy shlukovací analýzy (oddíl 2.9) byla zahrnuty pouze metoda k-means, která je v systému Cluto pojmenována jako „direct”. Důvod je popsán v 5.1.

5.5

Použité technologie

68

Metody podobnosti V bakalářské práci byl na daných datech testován kosinus, Pearsonův korelační koeficient, Jaccardův koeficient a Euklidovská vzdálenost. Protože zdroje jako (Burda, 2012), (Žižka, Burda, Dařena, 2012) a (Dařena, Žižka, Burda, 2012) ukázaly, že na zvolených zdrojových datech je optimální z hlediska účinnosti shlukování metrika kosinu, je využit v diplomové práci pouze kosinus. Kvalita shlukování Kvalita shlukování je zde posuzována primárně z hlediska metriky Accuracy, jež je popsána v oddíle 2.13.

5.5


V rámci diplomové práce bylo použito větší množství různých softwarových technologií. Níže je stručně uveden software, který byl v průběhu využit (kromě systému Cluto, který je popsán v části 3.1). Perl Pro přípravu dat byl použit vysokoúrovňový programovací jazyk Perl ve verzi 5. Jedná se o vhodný programovací jazyk pro práci s textovými daty. Perl byl použit v celé části přípravy dat – od výběru dokumentů, přípravu do surové reprezentace, generování kontrolních tříd až po různé převody. LATEX Pro sazbu této závěrečné práce byl použit systém LATEX, konkrétně grafické vývojové prostředí distribuce TexMaker pro platformy na bázi operačních systémů Unix. Jedná se volně dostupnou distribuci verze 4.0.38 , která integruje velké množství balíčků. QTree QTree je volně dostupný balíček pro systémy LATEX. Je velmi podobný známějšímu balíčku PSTricks; pomocí QTree lze jednoduše sázet stromové vizuální struktury. Balík je dostupný na webu (Dimitriadis, 2008). lstlistings lstlistings je balík pro systémy LATEX, který umožňuje pohodlně sázet zdrojové kódy programů či skriptů. Balík podporuje automatické zvýrazňování syntaxe, čísla řádků a množství dalších funkcí. Informace o balíku lze nalézt na internetu (Heinz, Moses, 2007). C++ Programovací jazyk C++ je jeden z nejpoužívanějších programovacích jazyků dnešní doby. Jedná se vysoko-úrovňový (high-level) programovací jazyk, kde se vývojář nemusí zabývat nízko-úrovňovými operacemi – vývoj v tomto jazyce je tedy velice efektivní. 8

Dostupné z: http://www.xm1math.net/texmaker/

5.5


69

Zdrojový kód C++ je kompilovaný, to znamená, že se přeloží do strojového kódu stroje, na kterém kompilace (překlad, sestavení) proběhla. Na rozdíl od interpretovaných jazyků je tedy provádění kódu a instrukcí velice rychlé a proto je možné C++ použít prakticky na jakoukoliv technickou úlohu. Za zakladatele jazyka C++ je považován Bjarne Stroustrup, jež jazyk vytvořil v roce 1980 (Coleman, 2006). Původní myšlenka byla obohatit jazyk C o přímou podporu OOP (objektově-orientovaného programování) (Coleman, 2006), dnes se však jedná o jazyk velmi odlišný od C. C++ je de facto nadmnožinou jazyka C, proto je možné v C++ využívat i všechny konstrukce a algoritmy z jazyka C. Boost Závěrečná práce využívá volně dostupnou knihovnu Boost pro C++, která za dlouhou dobu své existence integruje množství optimalizací a algoritmů. Mezi zmíněnou funkcionalitu patří například optimalizované výpočty pro lineární algebru, rozsáhlá programová podpora paralelizace, regulární výrazy, zpracování obrazu, atd. (Karlsson, 2005). Git Git je jeden z nejpoužívanějších systémů pro verzování. Je velice flexibilní, jednoduchý, robustní a decentralizovaný. Za projektem Git stojí známý vývojář Linus Torvalds, který systém Git vytvořil při vývoji Linuxového jádra. Mezi klíčové vlastnosti Gitu patří (Loeliger, McCullough, 2012): • zjednodušení distribuovaného vývoje, • jednoduchost použití, • rychlost a efektivita, • integrita, • neměnnost jádra systému Git, • atomické transakce, • silná podpora vývojových větví, • čistý design systému, • decentralizovanost. SVMLight

SVMLight byl využit pro algoritmus SVM, více v 3.1 na straně 54.

ANN ANN je volně dostupná 9 programová statická knihovna v jazyce C++. Je možné využití jako statické knihovny a volat funkce modulu ANN přímo z autorova kódu. 9

Dostupný z: http://www.cs.umd.edu/~mount/ANN/

6

VÝSLEDKY A DISKUSE

6

70

Výsledky a diskuse

Kapitola presentuje dosažené výsledky praktické části – tedy především naměřené výsledky experimentů, kde nedílnou součástí tvoří diskuse nad dosaženými závěry. Kapitola taktéž stručně popisuje programový systém, jež byl vytvořen v rámci diplomové práce. Kapitolu uzavírá autorův návrh dalšího postupu, či propozice dalšího pokračování nebo rozšíření.

6.1

Značení

V rámci této sekce je popsáno značení dále využité v této diplomové práci. Zavedené zkratky a označení V praktické části je zavedeno určité značení, jež je použito v tabulkách a grafických znázorněních. Výraz „P:N” představuje poměr počtu dokumentů, jež jsou positivního rázu (jedná se veskrze o kladné recenze) a příspěvků negativního charakteru. Analogii pak představuje výraz „N:P”. Označení „X:Y” representuje poměr počtu dokumentů množin z trénovacích („X”) a testovacích dat („Y”); následuje často po výrazu „P:N”. Následující příklad proto znamená: 100 (50,50) : 1000 (70,30) představuje 100 trénovacích dokumentů, kde poměr positivních a negativních recenzí lze vyjádřit procentuálně jako 50:50. Testovací množina čítala 1000 dokumentů, poměr positivních a negativních příspěvků lze vyjádřit jako 70% positivních, 30% negativních. Ostatní použité zkratky jako NB, MNB, kNN nebo SVM jsou vysvětleny na straně 11. Jedná se v postupném pořadí o algoritmy Naivní Bayes, Multinomiální Naivní Bayes, k–nejbližších sousedů a Support Vector Machines. Modelový příklad Tato sekce uvádí modelový příklad tabulky, kde je vysvětlena a rozebrána její struktura a značení. Tabulky představující naměřené hodnoty experimentů (měření) se nachází právě v této kapitole. Modelová tabulka ilustruje výsledky algoritmů strojové učení pro příspěvky ze skupin positivních a negativních hotelových recenzí. Značení je vysvětleno na hlavičce tabulky, který obsahuje konkrétní hodnoty. Zeleně jsou označeny hodnoty buněk, jež representují nejlepší dosažený výsledek pro dané měření.

6.1

71

Značení

Tabulka 12: Accuracy pro modelový případ „100 (50,50) : 1000 (70,30)”

100 (50,50) : 1000 (70,30) Algoritmus

Měření

supervised NB MNB kNN SVM

0,84 0,80 0,81 0,80 0,80 0,81 — — — 0,75 0,65 0,74

0,84 0,80 — 0,73

clustering k-means

0,71

0,71

0,71

0,71

0,83

0,74

0,78

0,79

0,77

0,71

0,70

0,65

semi-supervised self-training NB co-training NB

Z výrazu „60 (50,50) : 823(77,23)” lze vyrozumět, že do procesu experimentu vstupovalo 60 trénovacích dokumentů, množinu testovacích dokumentů tvořilo 823 objektů. Trénovací množina má positivní a negativní příspěvky v procentuálním poměru 50:50 (%). Testovací množina obsahuje 77 % dokumentů ve prospěch příspěvků s positivním ohlasem. První sloupec představuje testovaný algoritmus strojového učení. Jsou použity konkrétní klasifikační algoritmy pro řízené (supervised), částečně řízené (semisupervised) a neřízené učení (zde shlukování – clustering). Druhý až pátý sloupec uvozuje hodnoty Accuracy naměřené při konkrétním pokusu. Ve výše uvedeném případě byl každý algoritmus testován čtyřikrát a vždy na jiných náhodně vybraných trénovacích datech, přitom samozřejmě byly zachovány konkrétní počty a poměry zastoupení tříd. Vybraná testovací množina zůstala zachována. Zeleně označené hodnoty označují nejlepší výsledek daného měření (de facto nejlepší hodnotu sloupce). Buňky označené symbolem „—” jsou pro daný případ algoritmu a měření neaplikovatelné, či nebyly nijak změřeny. V každém sudém měření (tj. 2. a 4. měření) jsou ze zdrojových dat odstraněna stop-slova, aby byla parametrizace měření širší 10 . 10

Seznam použitých stop-slov je dostupný na http://akela.mendelu.cz/~xburda2/mt/stoplist.txt

6.2

6.2

72

Srovnání parametrizací v rámci SSL


Oddíl srovnává rozličné parametrizace částečně řízeného strojové učení, dopady specifických nastavení a celkovou parametrizaci v obecné rovině. Nejprve se podkapitola zaměřuje na algoritmus Self-training, poté přechází k metodě Co-training. Self-training Následující tabulka 13 představuje naměřenou hodnotu Accuracy pro rozličné parametrizace metody Self-training spadající pod částečně řízené učící algoritmy. Hodnota v úplně pravém sloupci je průměrná Accuracy pro 4 opakovaná měření, s náhodně vybranými trénovacími daty. Výsledky byly získány na následujících konfiguracích trénovacích dat: • 60 (50,50) : 823 (77,23), • 80 (50,50) : 1020 (57,43), • 500 (50,50) : 11632 (74,26), • 140 (50,50) : 5237 (80,20). Byla použita kombinace následující parametrizací (potřebná teorie je popsána v 2.3): • hodnota Threshold, • Balancing, • Throttling. Tabulka 13: Výsledky „60 (50,50) : 823 (77,23)”

parametrizací

algoritmu

Self-training

pro

Threshold (%)

Balancing

Throttling (%)

Accuracy (∅)

80 80 80 95 95 95 99 99 99

Ne Ano Ne Ne Ano Ne Ne Ano Ne

Ne Ne 80 Ne 80 80 Ne Ne 80

0,77 0,76 0,78 0,79 0,78 0,78 0,78 0,78 0,78

případ

6.2


73

Dosažené výsledky implikují domněnku, že pro zvolená textová data v přirozeném jazyce nemá parametrizace metody Self-training prakticky žádný význam. Zajímavé je to z toho pohledu, že uvedená testovací data nemají procentuální poměr zastoupení 50:50, ale spíše 75:25; přesto nemá nastavení Balancing vliv. Parametrizace Throttling je, vzhledem k dosaženým výsledkům, k výkonnosti Selftrainingu irelevantní. Autor se domnívá, že na základě série předchozího měření na rozličných množinách testovacích dat lze stanovit podmínku, že ve všech následujících experimentech, kde se porovnávají metody strojového učení, bude při algoritmu Self-training použita varianta: • Threshold nastaveno na 95 %, • Balancing nepoužívat, • Throttling nevyužívat. Co-training Jak je popsáno v části 2.3, algoritmus Co-training byl implementován na základě dvou pohledů na data: 1. pohled na základě četnějších termů, 2. pohled na základě méně četných termů. Autor prováděl i sérii experimentů s jinými dvěma pohledy na data, a to s náhodným rozdělením každého vstupního dokumentu na dvě poloviny, čímž vznikly dvě množiny termů se stejnou nebo téměř stejnou mohutností. Na každé polovině byl poté natrénován samostatný klasifikátor s C1 , resp. C2 . Autor však výše uvedený postup vyloučil kvůli zřejmé nedeterminističnosti – při každém opakování algoritmů se účinnost algoritmu Co-training (metrika Accuracy) mohla lišit až o 15%. Algoritmus Co-training (a v jistých případech i Self-training) se nepodařilo provést s algoritmem kNN, na vině je příliš velká množina dimenzí vstupních dat, se kterými se použitá knihovna ANN špatně vyrovnává.

6.3

6.3

Srovnání metod strojového učení

74


Následující část se snaží o komplexní porovnání metodik strojového učení z hlediska chybovosti klasifikace, konkrétně se opět zaměřuje na metriku Accuracy. V rámci sekce jsou provedeny experimenty s využitím všech nástrojů uvedených v Metodice řešení na zdrojových datech. Poměry a počty jsou uvedeny u každého experimentu zvlášť, avšak seznam popisující použité počty je k nalezení v části 11 na straně 62. Autor nejprve uvádí početně nejméně mohutná data, jedná se o experiment na množině zhruba 900 dokumentů. Průměrné hodnoty pro jednotlivé algoritmy a metody jsou vyneseny na grafu 6.3. Následují výsledky experimentu pro podobně mohutná data, jedná se o asi 1 100 hotelových recenzí. Naměřené výsledky pro algoritmy strojového učení jsou vyneseny na grafu 6.3. Práce se v další části dostává k datům většího objemu, autor prováděl testování s asi 12 000 dokumenty a prováděl na nich strojové učení. Práce presentuje výsledky série měření na datech „500 (50,50) : 11632 (74,26)” v tabulce 16. Empiricky zjištěné metriky klasifikační úspěšnosti pro případ „500 (50,50) : 11632 (74,26)” uvádí graf 6.3. Sekci ukončuje experiment s největší množinou zdrojových dat, konkrétně zhruba 33 000 zdrojových dokumentů. Práce prezentuje výsledky experimentu pro data „500 (50,50) : 32191 (74,26)”, konkrétně tabulka 17. Graf 6.3 představuje vizualizaci výše uvedené tabulky v rámci aritmetického průměru jednotlivých učících metod. Naměřené výsledky jsou rozebrány a podrobeny diskusi po uvedení jejich dílčích výsledků, shrnutí se nachází na straně 79.

6.3

75



60 (50,50) : 823 (77,23) Algoritmus supervised NB MNB kNN SVM

0,84 0,80 0,37 0,75

0,80 0,80 0,37 0,65

0,81 0,81 0,37 0,74

0,84 0,80 0,68 0,73

clustering k-means

0,71

0,71

0,71

0,71

0,83 0,80 0,37 0,75

0,74 0,80 0,37 0,65

0,78 0,72 0,37 0,74

0,79 0,74 0,68 0,68

0,77 0,39 — 0,62

0,79 0,79 — 0,61

0,78 0,80 — 0,70

0,80 0,78 — 0,68

semi-supervised self-training NB MNB kNN SVM co-training NB MNB kNN SVM

Správně zařazeno (%)

Měření

90 80 70 60 50 40 30 20 10 0

NB

MNB kNN SVM k-means

supervised

self-training

co-training

clustering

Obrázek 12: Průměrná Accuracy pro „60 (50,50) : 823 (77,23)”

6.3

76




0,71 0,79 0,39 0,82

0,75 0,82 0,35 0,84

0,74 0,81 0,37 0,84

0,81 0,82 0,63 0,83

clustering k-means

0,80

0,83

0,84

0,86

0,80 0,77 0,37 0,82

0,84 0,80 0,37 0,84

0,88 0,81 0,37 0,84

0,89 0,82 0,63 0,85

0,72 0,77 — 0,79

0,75 0,73 — 0,78

0,74 0,72 — 0,77

0,76 0,80 — 0,77



Měření

90 80 70 60 50 40 30 20 10 0

NB

MNB kNN SVM k-means

supervised

self-training

co-training

clustering


6.3

77




0,89 0,87 — 0,82

0,89 0,87 — 0,82

0,89 0,89 — 0,81

0,86 0,87 — 0,80

clustering k-means

0,73

0,70

0,73

0,72

0,83 0,87 — 0,82

0,89 0,87 — 0,82

0,89 0,86 — 0,81

0,86 0,86 — 0,80

0,88 0,86 — 0,71

0,88 0,87 — 0,72

0,85 0,86 — 0,74

0,85 0,85 — 0,79



Měření

90 80 70 60 50 40 30 20 10 0

NB

MNB kNN SVM k-means

supervised

self-training

co-training

clustering


6.3

78




0,88 0,87 — 0,80

0,88 0,86 — 0,79

0,87 0,84 — 0,82

0,85 0,85 — 0,81

clustering k-means

0,73

0,70

0,71

0,71

0,82 0,83 — 0,80

0,83 0,84 — 0,80

0,82 0,84 — 0,82

0,84 0,83 — 0,81

0,86 0,86 — 0,70

0,84 0,85 — 0,73

0,87 0,87 — 0,71

0,82 0,84 — 0,72



Měření

90 80 70 60 50 40 30 20 10 0

NB

MNB kNN SVM k-means

supervised

self-training

co-training

clustering


6.3


79

Parametrizace dat „60 (50,50) : 823 (77,23)” je nejméně mohutnou množinou experimentu. Z hlediska chybovosti klasifikace se zde dobře presentují všechny otestované algoritmy strojového učení. Z pohledu konkrétních klasifikátorů je na tom nejhůře algoritmus k–nejbližších sousedů. Případ „80 (50,50) : 1002(57,43)” je velice zajímavý faktem, že shlukování zde produkovalo velmi dobré výsledky – dávalo vyšší Accuracy než klasifikační algoritmus Naive Bayes. Autor připisuje uvedenou skutečnost faktu, že testovací data mají velmi podobné rozložení tříd (procentuálně 57:43). Pokud by se rozložení tříd neblížilo 50:50, bude zcela jistě tento algoritmus neřízeného učení dávat horší výsledky z hlediska metriky Accuracy (Žižka, Burda, Dařena, 2012). Na výsledcích experimentu s množinou „500 (50,50) : 11632 (74,26)” je vidět, že pokud jsou k dispozici takto obsáhlá data (především velká databáze trénovacích dat), jsou výsledky algoritmů strojového učení vynikající. Opět vyniká algoritmus Naivního Bayese s úspěšností klasifikace takřka 90 %. Klasické algoritmy klasifikace zde překonávají své protějšky z oblasti částečně řízeného učení. Shlukování vykazuje úspěšnost správného přiřazení dokumentů z testovací množiny do tříd od 70 % do 80 %. Výsledky série experimentů s nejobsáhlejší využitou množinou dat – „500 (50,50) : 32191 (74,26)” – jsou takřka identické s výsledky předchozích experimentů s množinou „500 (50,50) : 11632 (74,26)”. V obou případech jde už o poměrně rozsáhlá data a z hlediska účinnosti algoritmů strojového učení nehraje roli mohutnost trénovací množiny, ale především rozsáhlost trénovacích dat. Z hlediska chybovosti klasifikace se nejlépe presentuje klasifikační algoritmus Naivní Bayes, kde metrika Accuracy osciluje kolem 87 %. Z dosažených výsledků lze konstatovat, že výkonnost řízeného i částečně řízeného učení je z hlediska chybovosti klasifikace velice podobná. Shlukování podává dle autorova názoru také použitelné výsledky, vzhledem ke svému charakteru neexistence jakékoliv trénovací množiny. V kontextu samotných klasifikátorů dosahuje nejlepších výsledků klasický algoritmus Naivního Bayese, který takřka ve všech případech a parametrizacích překonává ostatní klasifikační metody.

6.4

80

Implementovaný programový systém

Vývoj v iteracích Je zajímavé pozorovat naměřený ukazatel Accuracy metod částečně řízeného učení v jednotlivých iteracích. Dá se konstatovat, že nad zdrojovými daty se Accuracy v jednotlivých iteracích může měnit poměrně výrazně. Tabulka 18 reprezentuje experimentálně zjištěné okamžité hodnoty metriky Accuracy v jednotlivých iteracích. Jednotlivé sloupce tvoří konkrétní iterace algoritmu Self-training, řádky jsou tvořeny různými množinami dat případu „60 (50,50) : 823 (77,23)”. Oranžová barva označuje konečnou hodnotu Accuracy algoritmu Self-training pro danou množinu dat. Jako klasifikátor byl použit Naivní Bayes. Tabulka 18: Okamžitá Accuracy algoritmu Self-training v jednotlivých iteracích pro případ „60 (50,50) : 823 (77,23)”

Číslo iterace Data Data Data Data Data

1.

2.

1 0,84 0,73 2 0,80 0,64 3 0,81 0,71 4 0,84 0,68

3.

4.

5.

0,83 0,75 0,79 0,80

0,83 0,74 0,78 0,79

— 0,74 0,78 —

První iterace je ekvivalentní algoritmu řízeného učení za použití klasické klasifikace. Ve všech případech je konečná hodnota Accuracy horší, než po počáteční iteraci. Algoritmus Self-training se zastavil ve všech případech z důvodu, že již neprobíhaly žádné změny v dynamické trénovací množině – algoritmus na základě hodnoty threshold nemohl přidat do trénovací množiny žádné dokumenty, které by tam již nebyly přítomny. Konkrétní parametrizace Self-trainingu je popsána v 6.2 na straně 73.

6.4


V rámci diplomové práce byl autorem implementován programový systém umožňující řízené a částečně řízené učení. Vstupy a výstupy programového systému jsou dostatečně popsány v části 5.3 na straně 65. Diagram tříd a programových komponent je k dispozici v příloze A, metriky kódu jsou uvedené v příloze B. Kompletní zdrojový kód lze nalézt na přiloženém médiu. Programový systém byl od začátku zamýšlen jako snadno rozšiřitelný, a proto je možné rozšiřovat jeho funkcionalitu pomocí vlastních tříd při dodržení třídního modelu OOP. Program nemá grafické uživatelské rozhraní.

6.4


81

Nástroj byl implementován v jazyce C++ s využitím normy jazyka z roku 2011, což byl v době tvorby diplomové práce nejnovější oficiální standard. Níže na ilustraci 6.4 je znázorněno schéma programového systému s funkcionalitou řízeného a částečně řízeného učení.

Obrázek 16: Schéma funkcionality programového systému Algoritmy strojového učení jsou reprezentovány zkratkou a jejich význam je vysvětlen v na straně 11. Vstupem do systému je diskrétní množina trénovacích a testovacích dat ve formátu CSV nebo ARFF. Výstupem je textový soubor s informacemi o proběhlém strojovém učení a predikce algoritmu pro jednotlivé dokumenty – predikce příslušnosti ke třídám.

6.5

6.5

Diskuse

82

Diskuse

Oblast dolování z textových dat je velice náročná nejen z časového hlediska a často k dosažení výsledku vyžaduje zapojení více technických disciplín. I z tohoto pohledu se autor práce domnívá, že výsledky algoritmů strojového učení jsou více než uspokojivé z hlediska kvality výsledků. Je potřeba zdůraznit, že použitá textová data v přirozeném jazyce jsou naprosto reálná, a proto mohou při zpracování činit mnoho problémů – jednotlivé dokumenty jsou subjektivně velice krátké, nepřesné a obsahují gramatické chyby. Přesto se ukázalo, že všechny algoritmy strojového učení jsou i v tomto případě prakticky použitelné. Z hlediska metriky kvality strojového učení, v tomto případě z hlediska Accuracy, implikovaly nejlepší výsledky klasické algoritmy řízeného učení (učení s učitelem, supervised learning), konkrétně klasifikace. Při všech konfiguracích experimentů se prostý algoritmus Naive Bayes s metrikou Accuracy nedostal pod 80 % správně klasifikovaných objektů; v některých případech dokonce úspěšnost překračuje hranici 90 %. Naivní Bayes ve formě klasifikace byl stabilně ve všech experimentech jako jeden z nejlepších z hlediska chybovosti. Dynamicky se rozvíjející odvětví částečně řízeného učení v rámci zvolených textových dat také nedopadlo špatně. Ve srovnání s klasickou klasifikací ovšem takřka bez výjimky vždy přineslo horší výsledek, než učení stroje s učitelem metodou klasifikace; konečný rozdíl v účinnosti algoritmu byl však poměrně zanedbatelný. Autor se domnívá, že výše uvedený fakt způsobuje především skutečnost, že klasifikátor použitý v částečně řízeném učení po nulté iteraci vybere chybně určité procentu dokumentů, kde si je dostatečně jistý, že dokument by opravdu mohl náležet k dané třídě. Tyto dokumenty jsou pak samozřejmě přiřazeny k trénovací množině (klasifikátor se na tyto dokumenty dívá jako na „bernou minci”) a především v případech, kde je výchozí trénovací množina – tedy množina již správně označených dokumentů, z kterých se klasifikátor naučí v úplně počáteční fázi – velmi malá, má tento fakt chybně zvolených dokumentů kardinální vliv. Dá se konstatovat, že v mnoha případech se tento fakt pak dále prohlubuje a na základě chybně zvolených dokumentů jsou opět chybně zvoleny další dokumenty do trénovací množiny, a tak se chybovost šíří dále. Na druhou stranu se nedá říci, že by s rostoucím počtem iterací klesala v každé jednotlivé iteraci i metrika Accuracy. V každém případě záleželo na konkrétních datech – dokumentech. Zde si autor dovoluje odkázat na oddíl 6.3. Výjimku z tohoto pravidla tvoří samozřejmě nultá (úplně první) iterace, která je ve své podstatě ekvivalentní klasifikaci. Pokud autor tvrdí, že klasifikační algoritmy dávaly vždy lepší výsledky než algoritmy částečně řízeného učení, tak je samozřejmé, že například druhá a třetí iterace částečně řízeného učení byla vždy horší, než ta úplně první. Popřením této skutečnosti by se de facto negoval závěr, že obyčejná klasifikace přinesla lepší výsledky než částečně řízené učení.

6.6

Návrh dalšího postupu

83

Z hlediska operační časové náročnosti algoritmů je nejnáročnější strojové učení Co-training z důvodu použitých pohledů na data, které se zakládají na frekvenci termů, kterou je nutné vypočítat. A už při řádově tisícovkách záznamů je tato operace citelná. Toto je ovšem samozřejmě pouze záležitostí autorovy implementace algoritmu – pokud by algoritmus Co-training dostal data již připravená a rozdělená na dvě množiny, operační náročnost by byla srovnatelná s ostatními algoritmy. Časová operační doba ostatních algoritmů je velice podobná a rozdíly jsou, při výkonu dnešních počítačů, zanedbatelné. Empiricky byl potvrzen předpoklad, že shlukování dává horší výsledky při nevyváženosti vstupních dat, konkrétně při nevyváženosti zařazení dokumentů do tříd. V kontextu využitých reálných textových dat dával algoritmus shlukování horší ve všech případech, což však bylo očekáváno. Při procentuální nevyváženosti například 60:40 ve prospěch jedné třídy jsou výsledky horší. S ještě citelnější nevyvážeností chybovost shlukování přímo úměrně rostla.

6.6

Návrh dalšího postupu

Diplomová práce v jistém smyslu navazuje na autorovu předchozí bakalářskou práci (Burda, 2012). Na této diplomové práci lze taktéž pokračovat nebo na ní stavět. Použitý programový systém na provádění strojového učení lze také poměrně snadno rozšířit díky mechanismu OOP o další funkcionalitu. Jedinou podmínkou pro toto je implementace v jazyce C++. Díky velkému rozsahu metodik částečně řízeného učení by bylo vhodné empiricky ověřit větší množství parametrizací algoritmů Self-training a Co-training. Nabízí se zde i možnost integrace některého z řady jiných klasifikačních algoritmů jako jsou C4.5, formy rozhodovacích stromů, Expectation-Maximization, neuronové sítě, ID3 klasifikátor a mnoho dalších.

7

ZÁVĚR

7 7.1

84

Závěr Zhodnocení

Autor se domnívá, že práce splnila zadání a závěry mohou posloužit i dalším autorům, studentům nebo zájemcům o oblast strojového učení. Analýza současného stavu problematiky se nachází v části 3.1, teoretický aparát problematiky je vysvětlen ve druhé kapitole. Dalším cílem diplomové práce bylo seznámení se s algoritmy částečně řízeného učení a vybrat vhodná volně dostupná data, což bylo splněno a použitá data jsou popsána v části Zdrojová data. V kapitole Metodika řešení autor popisuje systém automatizace experimentů a předzpracování dat s využitím vlastních skriptů v jazyce Perl. Dále stručně popisuje proces vlastního strojové učení v programovém nástroji, který byl vytvořen v rámci diplomové práce za využitím jazyka C++. Autor se domnívá, že tento cíl byl také naplněn. Hlavní zaměření práce – empirické zjištění chybovosti jednotlivých metodik strojového učení – pokrývá většinu praktické části. Vyvození příslušných závěrů a doporučení je realizováno také v rámci kapitoly Praktická část v oddílu Diskuse (číselně označena 6.5). Provedené experimenty a jejich výsledky implikují určité závěry ohledně algoritmů strojového učení a především jeho formy a parametrizace. Na poznatcích diplomové práce lze stavět v budoucnu a může sloužit jako určitý základní, stručný a ucelený informační zdroj o dané problematice. Autorem vytvořené skripty jsou použitelné a najdou své využití při předzpracování a výběru dat v rozličných programových systémech a scénářích. Vytvořený programový nástroj nebyl cílem diplomové práce, ale je taktéž použitelný a díky svému modelu a charakteru i poměrně snadno rozšiřitelný.

8

8

LITERATURA

85

Literatura

Burda, K., 2012. Aplikace pokročilých shlukovacích metod na textová nestrukturovaná data v přirozeném jazyce. Brno. Bakalářská práce. Mendelova univerzita v Brně. 57 s. Vedoucí práce doc. Ing. Jan Žižka, CSc. Dařena., F., Žižka, J., Burda, K., 2012. Grouping of Customer Opinions Written in Natural Language Using Unsupervised Machine Learning. In: Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2012 14th International Symposium, strany 265–270. Žižka, J., Burda, K., Dařena, F., 2012. Mining Opinion-Clusters from Very Large Unstructured Real-World Textual Data. Lecture Notes in Computer Science, vydání 7557, strany 38–47. Žižka, J., Burda, K., Dařena, F., 2012. Clustering a Very Large Number of Textual Unstructured Customers’ Reviews in English. Artificial Intelligence: Methodology, Systems, and Applications, Springer, strany 38–47. Abney, S., 2008. Semisupervised Learning for Computational Linguistics. New York: Chapman Hall/CRC. ISBN 978-1-58488-559-7. Alpaydin, E., 2004. Introduction to machine learning. Cambridge: MIT Press. 415 s. ISBN 978-0-26201-211-9. Baeza-Yates, R., Ribeiro-Neto, B., 1999. Modern Information Retrieval. New York: ACM Press. ISBN 978-0201398298. Baraldi, A., Blonda, P, 1999. A survey of fuzzy clustering algorithms for pattern recognition. I. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 29(6), strany 778–785. Barbakh, W., Fyfe, C., 2008. Online Clustering Algorithms. International Journal of Neural Systems, 18(03), strany 185–194. Bavi, V., Beirne, T., Bone, N., Mohr J., Neal B., 2010. Comparison of Document Similarity Metrics. In: Winter 2010 Information Retrieval. Western Washington University. Dostupné z: http://wiki.cs.wwu.edu/2010/Winter/CSCI517M/Comparison_of_Document_ Similarity_Metrics_%28Write_Up%29. Bayesia SAS, 2012. Bayesia: Make the Best Decisions [online], [vid. 10. 5. 2012]. Dostupné z: http://www.bayesia.com. Blum, A., Mitchell, T., 1998. Combining labeled and unlabeled data with cotraining. In: Proceedings of the eleventh annual conference on Computational learning theory. ACM. Strany 92–100.

8

LITERATURA

86

Borglin, J., 2011. Classification of hand movements using multi-channel EMG. Gothenburg, 2011. Diplomová práce. Chalmers University of Technology. 68 s. Brodersen, K. H., Ong, Ch. S., Klaas, E. S., Buhmann, J. M., 2010. The Balanced Accuracy and Its Posterior Distribution. In: Pattern Recognition (ICPR), 2010 20th International Conference, strany 3121–3124. Coleman, R., 2006. History of the C++ Programming Language [online], The University of Alabama. Dostupné z: http://www.cs.uah.edu/~rcoleman/Common/History/HistoryOfCPP.html. Dařena, F., 2011. Vybrané přístupy k dolování znalostí ze sociálních médií. Brno. Habilitační práce. Mendelova univerzita v Brně. 163 s. Demel, J., 2002. Grafy a jejich aplikace. Praha: Academia. 1. vyd. ISBN 80-200-0990-6. Dimitriadis, A., 2008. Qtree download directory [online], [vid. 14. 3. 2012]. Dostupné z: http://www.ling.upenn.edu/advice/latex/qtree/. Document clustering, 2009 [online], [vid. 12. 3. 2012]. Dostupné z: http://en.wikipedia.org/wiki/Document_clustering. Downs, G., M., Barnard, J. M., 1995. Hierarchical and non-Hierarchical Clustering. In: Daylight EUROMUG meeting. Stannington, UK. Dostupné z: http://www.daylight.com/meetings/mug96/barnard/E-MUG95.html. Eisen, M., 2013. Cluster 3.0 – Open Source Slustering Software [online], [vid. 3. 1.013]. Dostupné z: http://bonsai.hgc.jp/~mdehoon/software/cluster/software.htmctv. Gan, G., Ma, C., Wu, J., 2007. Data Clustering: Theory, Algorithms, and Applications. Philadelphia: SIAM, Society for Industrial and Applied Mathematics and American Statistical Association. ISBN 978-0-898716-23-8. Gashler, M., Moyer, E., 2005. Waffles – A machine learning toolkit [online], [vid. 1. 11.013] Dostupné z: http://waffles.sourceforge.net/index.html. Heinz, C., Moses B., 2007. Listings package [online], [vid. 16. 3. 2012]. Dostupné z: ftp://ftp.tex.ac.uk/tex-archive/macros/latex/contrib/listings/. Huang, A., 2008. Similarity Measures for Text Document Clustering. In: Proceedings of the sixth new zealand computer science research student conference (NZCSRSC2008), Christchurch, New Zealand, strany 49–56. Chapelle, O., Schölkopf, B., Zien, A., 2006. Semi-Supervised Learning. Cambridge: The MIT Press. 525 s. ISBN 978-0262514125.

8

LITERATURA

87

Chec, S., Goodman, J., 1996. An empirical study of smoothing techniques for language modeling. In: Proceedings of the 34th annual meeting on Association for Computational Linguistics, strany 310-318. Iria, J., 2009. Aleph – a multi-platform machine learning framework aimed at simplicity and performance [online], [vid. 3. 1.013]. Dostupné z: http://aleph-ml.sourceforge.net. Joachims, T., 2008. SVM-Light Support Vector Machine [online], poslední revize 14 .8. 2008 [cit. 1 .2. 2014]. Dostupné z: http://svmlight.joachims.org. Karlsson, B., 2005. Beyond the C++ Standard Library. Boston: Addison-Wesley. 432 s. ISBN 978-0321133540. Karypis, G., 2003. Cluto – A Clustering Toolkit. Minnesota. Dostupné z: http://glaros.dtc.umn.edu/gkhome/fetch/sw/cluto/manual.pdf. Karypis, G., 2006. Karypis Lab [online], [vid. 3. 2.012]. Dostupné z: http://glaros.dtc.umn.edu/gkhome. Kelcey, M., 2010. Should I Read It? The Naive Bayes Method, [online], [vid. 1. 4. 2014]. Dostupné z: http://matpalm.com/rss.feed/p3/. Kelcey, M., 2010. Should I Read It? Multinomial Bayes [online], [vid. 1. 4. 2014]. Dostupné z: http://matpalm.com/rss.feed/p4/. Kibriya, A., Frank, E., Pfahringer, B., Holmes, G., 2005. Multinomial Naive Bayes for Text Categorization Revisited. AI 2004: Advances in Artificial Intelligence, strany 488–499. Konchady, M., 2006. Text Mining Application Programming. Boston: Thomson. 412 s. ISBN 978-1-58450-460-3. Kontostathis, A., Pottenger, W. M., 2002. Detecting Patterns in the LSI Term-Term Matrix. In: Workshop on the Foundation of Data Mining and Discovery, IEEE International Conference on Data Mining, Lehigh University. Dostupné z: http://www3.lehigh.edu/images/userImages/cdh3/Page3456/LU-CSE02-010.pdf. Kumar, V., Wu, X., 2009. The Top Ten Algorithms in Data Mining. Kentucky: Taylor & Francis Group. 215 s. ISBN 978-1-4200-8964-6. Li, C., Lin, N., 2011. A Novel Text Clustering Algorithm. In: Energy Procedia, 13, strany 3583–3588. Li, N., Wu, D. D., 2010. Using text mining and sentiment analysis for online forums hotspot detection and forecast. Decision Support Systems, 48(2), strany 354–368.

8

LITERATURA

88

Li, Y., Chung, S. M. , Holt, J. D., 2008. Text document clustering based on frequent word meaning sequences. In: Data & Knowledge Engineering, 64(1), strany 381-404. Loeliger, J., McCullough, M., 2012. Version Control with Git: Powerful tools and techniques for collaborative software development. Sebastopol: O’Reilly Media, Inc. 456 s. ISBN 978-1449316389. Manning, D., Raghavan, P., Schütze, H., 2008. Introduction to Information Retrieval. Cambridge: Cambridge University Press. ISBN 978-0521865715. Metsis, V., Androutsopoulos, I., Paliouras, G., 2006. Spam filtering with naive bayes – which naive bayes?, In: CEAS, strany 27–28.. Novák, Z., 2013. Aplikování paralelismu při dolování znalostí z textových dat. Brno. Diplomová práce. Mendelova univerzita v Brně. 70 s. Nečas, J., 1978. Aplikovaná matematika. M-Z. Praha: SNTL, 1. vyd. Plisson, J., Lavrac, N., Mladenić, D., 2004. A rule based approach to word lemmatization. Jožef Stefan Institute, Department of Knowledge Technologies. Dostupné z: http://eprints.pascal-network.org/archive/00000715/01/Pillson-Lematization.pdf. Porter, M. F., 1980. An Algorithm for Suffix Stripping [program]. Pratikakis, I., Bolovinou, A., Gatos, B., Perantonis, S., 2011. Semantics extraction from images. Knowledge-driven multimedia information extraction and ontology evolution, strany 50–88. Quinlan, JR., 1993. C4.5: Programs for Machine Learning. USA: Springer. ISBN 0885-6125. Saad, F. H., Iglesia, B., Bell, G. D., 2006. A Comparison of Two Document Clustering Approaches for Clustering Medical Documents. In: DMIN, strany 425–431. Salton, G., Wong, A., Yang, C. S., 1975. A vector space model for automatic indexing. In: Communications of the ACM, 18(11), strany 613–620. ISBN 18(11):613-620. Shafranovich, Y., 2005. Common Format and MIME Type for Comma-Separated Values (CSV) Files [online], [vid. 1. 3. 2014]. Dostupné z: http://tools.ietf.org/html/rfc4180.html. Settles, B., 2012. dualist – Interactive machine learning for text analysis [online], poslední revize 8 .3. 2012 [cit. 20 .4. 2014]. Dostupné z: http://code.google.com/p/dualist.

8

LITERATURA

89

Silva, C., Ribeiro, B., 2010. Inductive Inference for Large Scale Text Classification: Kernel Approaches and Techniques. USA: Springer. ISBN 978-3-642-04533-2. Srivastava, A., Han, EH., Kumar, V., Singh, V., 2002. Parallel formulations of decision-tree classification algorithms. USA: Springer. 237 s. ISBN 978-0-7923-7745-0. Srivastava, A., Sahami, M., 2009. Text Mining: Classification, Clustering, and Applications. Minneapolis, Minnesota, USA: CRC Press. 290 s. ISBN 978-1-4200-5940-3. Strehl, A., Ghosh, J., Mooney, R., 2000. Impact of Similarity Measures on Web-page Clustering. In: Workshop on Artificial Intelligence for Web Search (AAAI 2000), strany 58-64. Ševčík, R., 2010. Klasifikace elektronických dokumentů s využitím shlukové analýzy. Praha. Diplomová práce. Vysoká škola ekonomická v Praze. 78 s. Torkkola, K., 2004. Discriminative features for text document classification. Formal Pattern Analysis & Applications, strany 301–308. Vapnik V., 2000. The Nature of Statistical Learning Theory: Second Edition. USA: Springer. ISBN: 978-0387987804. Veropoulos, K., Campbell, C., Cristianini, N., 1999. Controlling the sensitivity of support vector machines. In: Proceedings of the international joint conference on artificial intelligence, strany 55–60. Wang W., Zhou, Z., 2007. Analyzing co-training style algorithms. Machine Learning: ECML 2007, strany 454–465. Wang Y., 2009. Novel approaches in cognitive informatics and natural intelligence. Hershey: IGI Global. ISBN 978-1-60566-171-1. Weka, 2012. weka – ARFF [online] Dostupné z: http://www.cs.waikato.ac.nz/ml/weka/arff.html. Yang, J., Zhu, X., 2013. Semi-Supervised Learning Software. [online], poslední revize 18 .3. 2013 [cit. 20 .11. 2013]. Dostupné z: http://pages.cs.wisc.edu/ jerryzhu/ssl/software.html. Zhang, D., Dong, Y., 2004. Semantic, Hierarchical, Online Clustering of Web Search Results. Advanced Web Technologies and Applications, strany 69–78. ISBN 978-3-540-24655-8. Zhang, W., Yoshida, T., Tang, X., 2008. Text classification based on multi-word with support vector machine. Knowledge-Based Systems, 21(8), strany 879–886.

8

LITERATURA

90

Zhang, Y., Jin, R., Zhou, Z., 2010. Understanding bag-of-words model: a statistical framework. In: International Journal of Machine Learning and Cybernetics, 1(1–4), strany 43–52. Zhao, Y., Karypis, G., 2006. Criterion Functions for Document Clustering. University of Minnesota. Zhu, X., 2006. Semi-supervised learning literature survey. Computer Science, University of Wisconsin-Madison. Wisconsin: USA, 2. vydání. Zhu, X., Goldberg, A., 2009. Introduction to Semi-Supervised Learning: Synthesis Lectures on Artificial Intelligence and Machine Learning. California: Morgan and Claypool Publishers. 116 stran. ISBN 978-1-5982-9547-4.

Přílohy

A

A

ZJEDNODUŠENÝ DIAGRAM TŘÍD PROGRAMOVÉHO SYSTÉMU

92

Zjednodušený diagram tříd programového systému

Obrázek 17: Zjednodušený diagram tříd programového systému

B

B

93

METRIKY KÓDU

Metriky kódu

Následuje krátká tabulka shrnující metriky zdrojové kódu. Velikost binárního souboru je uvedena pro operační systém typu Unix s architekturou 32-bit. Tabulka 19: Metriky kódu

Počet souborů Počet řádků Velikost statických dat Velikost binárního souboru

54 4 600 198 kB 403 kB

C

PARAMETRIZAČNÍ SOUBOR PŘILOŽENÉHO PROGRAMOVÉHO SYSTÉMU

94

C Parametrizační soubor přiloženého programového systému # classifier # s u p e r v i s e d : nb , mnb , knn , svm # semi−s u p e r v i s e d : snb , smnb , sknn , ssvm , conb , comnb , coknn , cosvm # cosvm # smoother of v a l u e s : l p ( l a p l a c e a n smoothing ) , ad ( a d d i t i v e +1 smoothing ) , # or no ( no smoothing ) lp # t r a i n f i l e ( path , for t h e SVM and SSVM i t has to be in format # e . g . ”20_60/ t r a i n . c s v .DAT” ) 60_823/ t r a i n . c s v . dat # t e s t f i l e ( path ) 60_823/ t e s t . c s v . dat # t h r e s h o l d ( fo r s s l ) 95.0 # t h r o t t l i n g ( for s s l ) 0.0 # b a l a n c i n g ( fo r s s l ) 0 # knn ( number of n e a r e s t n e i g h b o r s fo r t h e kNN a l g o r i t h m ) 1 # min−word l e n g t h 3 # l o g g i n g ( 1 = enabled , 0 = d i s a b l e d ) 1 # matrix f i l e ( 0 / 1 ) 0

D

UKÁZKA VÝSTUPU PROGRAMOVÉHO NÁSTROJE

D

95

Ukázka výstupu programového nástroje

c l a s s i f i e r = Naive Bayes ( S e l f −t r a i n i n g ) , smoother = Laplacean , min word l e n g t h = 3 , l e a r n i n g t h r e s h o l d = 9 5 , b e s t i t e r a t i o n = 0 ( 8 4 , 7 3 , 8 3 , 8 3 , ) , t h r o t t l i n g = 0 , b a l a n c i n g = no documents = 883(60+823) , terms = 4 3 1 , c o r r e c t = 6 9 4 ( 8 4 . 3 % ) , i n c o r r e c t = 1 2 9 ( 1 5 . 6 % ) p o s i t i v e , P=0.500000 , TP=1108 , TN=−543, FP=160 , FN=98 n e g a t i v e , P=0.500000 , TP=280 , TN=285 , FP=98 , FN=160

X

X X X X

X X X

0 ,P( p o s i t i v e )=3.00761 e −22 ( 7 9 . 6 8 0 7 % ) , P( n e g a t i v e )=7.66967 e −23 ( 2 0 . 3 1 9 3 % ) => ’ p o s i t i v e ’ , r e a l = ’ p o s i t i v e ’ 1 ,P( p o s i t i v e )=1.76745 e −35 ( 9 9 . 6 2 2 6 % ) , P( n e g a t i v e )=6.69585 e −38 ( 0 . 3 7 7 4 1 3 % ) => ’ p o s i t i v e ’ , r e a l = ’ p o s i t i v e ’ 2 ,P( p o s i t i v e )=4.252 e −16 ( 0 . 2 3 8 4 0 1 % ) , P( n e g a t i v e )=1.7793 e −13 ( 9 9 . 7 6 1 6 % ) => ’ n e g a t i v e ’ , r e a l = ’ n e g a t i v e ’ 3 ,P( p o s i t i v e )=2.49966 e −09 ( 8 9 . 1 2 5 8 % ) , P( n e g a t i v e )=3.04982 e −10 ( 1 0 . 8 7 4 2 % ) => ’ p o s i t i v e ’ , r e a l = ’ p o s i t i v e ’ 4 ,P( p o s i t i v e )=3.35364 e −13 ( 2 9 . 4 1 1 8 % ) , P( n e g a t i v e )=8.04874 e −13 ( 7 0 . 5 8 8 2 % ) => ’ n e g a t i v e ’ , r e a l = ’ n e g a t i v e ’ 5 ,P( p o s i t i v e )=8.63305 e −190 ( 8 6 . 7 7 9 7 % ) , P( n e g a t i v e )=1.31518 e −190 ( 1 3 . 2 2 0 3 % ) => ’ p o s i t i v e ’ , r e a l = ’ p o s i t i v e ’ 6 ,P( p o s i t i v e )=0.00407407 ( 9 6 . 0 6 3 3 % ) , P( n e g a t i v e )=0.000166959 ( 3 . 9 3 6 7 5 % ) => ’ p o s i t i v e ’ , r e a l = ’ p o s i t i v e ’ 7 ,P( p o s i t i v e )=4.19202 e −23 ( 6 0 . 4 6 5 1 % ) , P( n e g a t i v e )=2.74093 e −23 ( 3 9 . 5 3 4 9 % ) => ’ p o s i t i v e ’ , r e a l = ’ n e g a t i v e ’ 8 ,P( p o s i t i v e )=6.44887 e −14 ( 4 2 . 2 2 8 9 % ) , P( n e g a t i v e )=8.82236 e −14 ( 5 7 . 7 7 1 1 % ) => ’ n e g a t i v e ’ , r e a l = ’ n e g a t i v e ’ 9 ,P( p o s i t i v e )=1.19472 e −19 ( 8 9 . 9 2 7 4 % ) , P( n e g a t i v e )=1.33819 e −20 ( 1 0 . 0 7 2 6 % ) => ’ p o s i t i v e ’ , r e a l = ’ n e g a t i v e ’ 1 0 ,P( p o s i t i v e )=5.98652 e −05 ( 5 0 . 6 3 2 9 % ) , P( n e g a t i v e )=5.83686 e −05 ( 4 9 . 3 6 7 1 % ) => ’ p o s i t i v e ’ , r e a l = ’ n e g a t i v e ’ 1 1 ,P( p o s i t i v e )=1.62564 e −24 ( 8 7 . 6 8 5 2 % ) , P( n e g a t i v e )=2.2831 e −25 ( 1 2 . 3 1 4 8 % ) => ’ p o s i t i v e ’ , r e a l = ’ n e g a t i v e ’ 1 2 ,P( p o s i t i v e )=5.56529 e −05 (40%) , P( n e g a t i v e )=8.34794 e −05 (60%) => ’ n e g a t i v e ’ , r e a l = ’ p o s i t i v e ’ 1 3 ,P( p o s i t i v e )=1.51603 e −21 ( 9 9 . 9 9 6 8 % ) , P( n e g a t i v e )=4.91139 e −26 ( 0 . 0 0 3 2 3 9 5 3 % ) => ’ p o s i t i v e ’ , r e a l = ’ p o s i t i v e ’ 1 4 ,P( p o s i t i v e )=2.65116 e −06 ( 9 5 . 4 7 2 9 % ) , P( n e g a t i v e )=1.25711 e −07 ( 4 . 5 2 7 0 7 % ) => ’ p o s i t i v e ’ , r e a l = ’ p o s i t i v e ’ 1 5 ,P( p o s i t i v e )=1.50953 e −36 ( 2 5 . 1 3 9 6 % ) , P( n e g a t i v e )=4.49507 e −36 ( 7 4 . 8 6 0 4 % ) => ’ n e g a t i v e ’ , r e a l = ’ n e g a t i v e ’ 1 6 ,P( p o s i t i v e )=0.00622222 ( 8 6 . 8 0 1 7 % ) , P( n e g a t i v e )=0.0009461 ( 1 3 . 1 9 8 3 % ) => ’ p o s i t i v e ’ , r e a l = ’ p o s i t i v e ’ 1 7 ,P( p o s i t i v e )=1.73888 e −124 ( 3 1 . 3 5 0 3 % ) , P( n e g a t i v e )=3.80773 e −124 ( 6 8 . 6 4 9 7 % ) => ’ n e g a t i v e ’ , r e a l = ’ p o s i t i v e ’ 1 8 ,P( p o s i t i v e )=1.39427 e −133 ( 6 7 . 1 0 5 % ) , P( n e g a t i v e )=6.83475 e −134 ( 3 2 . 8 9 5 % ) => ’ p o s i t i v e ’ , r e a l = ’ n e g a t i v e ’ 1 9 ,P( p o s i t i v e )=1.57013 e −17 ( 9 0 . 9 5 7 4 % ) , P( n e g a t i v e )=1.56094 e −18 ( 9 . 0 4 2 5 5 % ) => ’ p o s i t i v e ’ , r e a l = ’ n e g a t i v e ’

(...)

E UKÁZKA ZDROJOVÉ KÓDU

96

E Ukázka zdrojové kódu Níže je uvedená ukázka části zdrojového kódu implementující algoritmus Self-training. (...) s i z e _ t o l d S i z e = ( * this−>i n n e r C l a s s i f i e r −>t r a i n i n g D o c s ) . s i z e ( ) ; // go t h r o u g h t h e new u n l a b e l e d d o c s and f i n d t h e b e s t f i t t i n g fo r ( s i z e _ t j =0; j <(* this−>i n n e r C l a s s i f i e r −>t e s t i n g D o c s ) . s i z e ( ) ; j ++) { Document * doc = &((* this−>i n n e r C l a s s i f i e r −>t e s t i n g D o c s ) . a t ( j ) ) ; // go t h r o u g h t h e doc ’ s p r o b a b i l i t i e s fo r ( s i z e _ t n=0; n<(* this−>i n n e r C l a s s i f i e r −>c l a s s e s ) . s i z e ( ) ; n++) { i f ( doc−>g e t C l a s s P r o b a b i l i t y F o r C l a s s ( n ) > this−>l e a r n i n g T h r e s h o l d ) { GenericMethods : : l o g ( ” p us hi n g ” + s t d : : t o _ s t r i n g ( j ) ) ; i n d e x e s T o D e l e t e −>push_back ( j ) ; // add c l a s s t o t h a t document doc−>className = doc−>g e t P r e d i c t e d C l a s s N a m e ( ) ; toAdd−>push_back ( * doc ) ; break ; } } } // l e t ’ s add t h i s document t o t h e t r a i n i n g s e t this−>addToLabeledDocs (&*toAdd ) ; (...)

F ZDROJOVÝ KÓD SKRIPTU EXTRACT.PL

97

F Zdrojový kód skriptu extract.pl # Karel Burda , 2013 #! / u s r / b i n / p e r l # S c r i p t t a k e s raw f i l e and s e l e c t d e s i r e d number o f p o s i t i v e / n e g a t i v e d o c s # from i t and p u s h e s i t t o t h e d s t use F i l e : : Basename ; use s t r i c t ; use war n in gs ; i f ($#ARGV < 3 ) { print ” Usage : s e l e c t . p l [ s r c ] [ d s t ] [ number_positive ] [ number_negative ] \ n” ; exit ; } open F , ” <: u t f 8 ” , $ARGV[ 0 ] o r die ” E r r o r w h i l e o p e n i n g t h e f i l e ” ; open OUT, ” >: u t f 8 ” , $ARGV [ 1 ] ; print ” Reading f i l e . . . \ n” ; my @ l i n e s = ; my $count_pos = int ($ARGV[ 2 ] ) + 1 ; my $count_neg = int ($ARGV[ 3 ] ) + 1 ; my $ p o s i t i v e s = 0 ; my $ n e g a t i v e s = 0 ; my @randomIndexes = ( ) ; i f ( $count_pos > $# l i n e s | | $count_neg > $# l i n e s ) { print ” count i s b i g g e r than $# l i n e s \n” ; exi t ; } print ” G e n e r a t i n g i n d e x e s . . . \ n” ; fo r ( ; ; ) { my $ i n d e x = int ( rand($# l i n e s ) ) ; print ” pos : $ p o s i t i v e s , n e g a t i v e s : $ n e g a t i v e s , $count_pos , $count_neg \n” ; i f ( ” $ i n d e x ” ~~ @randomIndexes ) { #p r i n t ” A l r e a d y e x i s t i n g in de x , g e n e r a t i n g new\n ” ; next ; } i f ( $ p o s i t i v e s +1 == $count_pos && $ n e g a t i v e s +1 == $count_neg ) { print ”Done\n” ; last ; } # t e s t for the desired class my $ l i n e = $ l i n e s [ $ i n d e x ] ;

F ZDROJOVÝ KÓD SKRIPTU EXTRACT.PL

i f ( $ l i n e =~ m/^p .+/) { $ p o s i t i v e s ++; } i f ( $ l i n e =~ m/^n .+/) { $ n e g a t i v e s ++; }

i f ( $ p o s i t i v e s == $count_pos | | $ p o s i t i v e s > $count_pos ) { $ p o s i t i v e s −−; next ; } i f ( $ n e g a t i v e s == $count_neg | | $ n e g a t i v e s > $count_neg ) { $ n e g a t i v e s −−; next ; }

push ( @randomIndexes , $ i n d e x ) ; }

print ” P r i n t i n g d o c s i n t o t h e d s t . . . \ n” ; foreach my $ i n d e x ( @randomIndexes ) { print OUT ” $ l i n e s [ $ i n d e x ] ” ; } close F ; c l o s e OUT;

98

G

ZDROJOVÝ KÓD SKRIPTU SVM_PREPARE.PL

G

99

Zdrojový kód skriptu svm_prepare.pl

# Karel Burda , 2014 #! / u s r / b i n / p e r l # S c r i p t t a k e s two CSVs f i l e ( t e s t i n g and t r a i n i n g s a m p l e s ) and p r e p a r e s # them f o r t h e SVM format # Output : words . t x t and SVMLight d a t a f i l e use use use use

F i l e : : Basename ; S t o r a b l e qw( d c l o n e ) ; strict ; war n i n gs ;

i f (($#ARGV+1) != 3 ) { print ” Usage : svm_prepare . p l [ t r a i n _ c s v ] [ t e s t _ c s v ] [ min_word_length ] \ n” ; exi t ; } # H e l p e r methods sub t r i m ( $ ) { my $ s t r i n g = s h i f t ; $ s t r i n g =~ s /^\ s +//; $ s t r i n g =~ s /\ s+$ / / ; return $ s t r i n g ; } sub l o g 1 0 ( $ ) { my $n = s h i f t ; return log ( $n ) / log ( 1 0 ) ; } open open open open open

IN_TRAIN, ” <: u t f 8 ” , $ARGV[ 0 ] o r die ” E r r o r w h i l e o p e n i n g t h e f i l e \n” ; IN_TEST, ” <: u t f 8 ” , $ARGV[ 1 ] o r die ” E r r o r w h i l e o p e n i n g t h e f i l e \n” ; OUT_TRAIN, ” >: u t f 8 ” , $ARGV[ 0 ] . ” . dat ” ; OUT_TEST, ” >: u t f 8 ” , $ARGV[ 1 ] . ” . dat ” ; WORDS, ” >: u t f 8 ” , dirname ($ARGV [ 1 ] ) . ” / ” . ” words ” ;

print ” Reading $ARGV[ 0 ] f i l e . . . \ n” ; my @ l i n e s _ t r a i n = ; print ”Done\n” ; print ” Reading $ARGV[ 1 ] f i l e . . . \ n” ; my @ l i n e s _ t e s t = ; print ”Done\n” ; my @parts = ( ) ; my @terms = ( ) ; my %words = ( ) ; my $MIN_LENGTH = int ($ARGV [ 2 ] ) ; # r e l a t e d methods

G


100

sub read_documents { foreach my $ l i n e (@{$_ [ 0 ] } ) { $ l i n e = trim ( $ l i n e ) ; @parts = s p l i t ( / , / , $ l i n e ) ; @terms = s p l i t ( / \ s +/, $ p a r t s [ 1 ] ) ; foreach my $word ( @terms ) { i f ( length ( $word ) < $MIN_LENGTH) { next ; } # i n c r e a s e number o f o c c u r e n c e s i n t h e a r g hash $words { $word}++; # debug #p r i n t ” $word \n ” ; } } } sub get_number_of_docs_containing_term { return 1 ; } sub print_documents ( $ ) { my $ a r g = s h i f t ; my @arr = ( ) ; my $ h a n d l e = \*OUT_TRAIN; # t r a i n or t e s t documents i f ( $ a r g eq ” t r a i n ” ) { @arr = @ l i n e s _ t r a i n ; } i f ( $ a r g eq ” t e s t ” ) { @arr = @ l i n e s _ t e s t ; $ h a n d l e = \*OUT_TEST; } my $ c o u n t e r = 1 ; foreach my $ l i n e ( @arr ) { i f ( $ c o u n t e r %100 == 0 ) { print ” $ c o u n t e r l i n e s a r e done \n” ; } $ l i n e = trim ( $ l i n e ) ; @parts = s p l i t ( / , / , $ l i n e ) ; i f (($# p a r t s +1) != 3 ) {

G


101

print ” Line s h o u l d be i n t h e format ID ,WORDS, CLASS\n” ; print ” ( Li ne = $ l i n e ) \ n” ; } @terms = s p l i t ( / \ s +/, $ p a r t s [ 1 ] ) ; # print class i f ( $ p a r t s [ 2 ] eq ” p o s i t i v e ” ) { print $ h a n d l e ” 1 ” ; } else { print $ h a n d l e ”−1 ” ; } # a hash r e p r e s e n t i n g words i n t h e documents i t s e l f # ( needed f o r t h e number o f o c c u r e n c e s ) my %tmp = ( ) ; foreach my $word ( @terms ) { $tmp{ $word}++; } # a hash r e p r e s i n g t h e t u p l e s ( e . g . word_index => t f −i d f === 110 −> 0 . 9 9 6 ) my %f e a t u r e s = ( ) ; foreach my $word ( @terms ) { i f ( length ( $word ) < $MIN_LENGTH) { next ; } my $ t f =

$tmp{ $word }/($# terms +1);

# cou n t t h e number o f d o c s t h a t c o n t a i n s t h e term my $number_of_docs_containing_term = 1 ; foreach my $ l i n e ( @arr ) { $ l i n e = trim ( $ l i n e ) ; my @parts = s p l i t ( / , / , $ l i n e ) ; my @terms = s p l i t ( / \ s +/, $ p a r t s [ 1 ] ) ; i f ( grep (/^ $word$ / , @terms ) ) { $number_of_docs_containing_term++; next ; } } #p r i n t ”num = $number_of_docs_containing_term \n ” ; my $ i d f = l o g 1 0 (($# a r r +1)/ $number_of_docs_containing_term ) ; my $ t f i d f = $ t f * $ i d f ; # i f t f −i d f i s n e g a t i v e ( i t s h o u l n ’ t be . . . ) i f ( $ t f i d f < 0) { print ” N e g a t i v e TF−IDF a t a r g=$arg , word=$word , t f −i d f=$ t f i d f , t f=$ t f , i d f=$ i d f , (nom/denom)=

G


102

( ” . ($# a r r +1) . ” / ” . $number_of_docs_containing_term . ”)=” . ($# a r r +1)/ $number_of_docs_containing_term . ” ) \ n” ; } # f i n d t h e i n d e x o f t h e word i n t h e hash my $word_index = −1; my $ j = 0 ; my @keys = keys %words ; for my $w ( @keys ) { #p r i n t ” $word == $w\n ” ; i f ( $word eq $w) { $word_index = $ j ; last ; } $ j ++; } i f ( $word_index == −1) { print ”Word $word was not found i n t h e hash ! \ n” ; } $word_index++; #p r i n t ” $word ( $word_index ) − $ t f − $ i d f − $ t f i d f \n ” ; $ f e a t u r e s { $word_index } = $ t f i d f ; } # now s o r t t h e f e a t u r e s ( n e c c e s s a r y f o r SVMLight ) foreach ( sort { $a <=> $b } keys(% f e a t u r e s ) ) { #p r i n t ” key : $_ v a l u e : $ f e a t u r e s {$_}\n ” ; print $ h a n d l e ($_ . ” : $ f e a t u r e s {$_} ” ) ; } # p r i n t document ID print $ h a n d l e ”#$ p a r t s [ 0 ] ” ; # end t h e l i n e print $ h a n d l e ” \n” ; $ c o u n t e r ++; } } # MAIN # f i l l i n t h e hash o f t h e words from t r a i n read_documents ( \ @ l i n e s _ t r a i n ) ; # f i l l i n t h e hash o f t h e words from t e s t read_documents ( \ @ l i n e s _ t e s t ) ; # p r i n t words

G


fo r my $w ( keys %words ) { # debug # p r i n t WORDS ”$w − $words {$w}\n ” ; print WORDS ”$w\n” ; }

# p r i n t the data print ” C o n s t r u c t i n g t h e t r a i n documents . . . \ n” ; print_documents ( ” t r a i n ” ) ; print ” C o n s t r u c t i n g t h e t e s t documents . . . \ n” ; print_documents ( ” t e s t ” ) ;

close close close close close

IN_TRAIN ; IN_TEST ; OUT_TRAIN; OUT_TEST; WORDS;

103

H

H

ZDROJOVÝ KÓD SKRIPTU TRANSFORM.PL

104

Zdrojový kód skriptu transform.pl

# Karel Burda , 2011 #! / u s r / b i n / p e r l use F i l e : : Basename ; use s t r i c t ; use war n in gs ; i f (($#ARGV−1) < 4 ) { print ” Usage : t r a n s f o r m . p l [ s r c ] [ d s t ] [ format ] [ remove_stop_words ] \ n” ; exi t ; } open F , ” <: u t f 8 ” , $ARGV[ 0 ] o r die ” E r r o r w h i l e o p e n i n g t h e f i l e \n” ; open OUT, ” >: u t f 8 ” , $ARGV [ 1 ] ; my my my my my my my my my my

@ l i n e s = ; @parts = ( ) ; @sentences = ( ) ; $i = 0; $j = 0; $delim = ” , ” ; $format = $ARGV [ 2 ] ; $sen ; $remove_stop_words = int ($ARGV [ 3 ] ) ; @stop_words = ( ) ;

i f ( $remove_stop_words == 1 ) { open STOP, ” <: u t f 8 ” , ” s t o p l i s t . t x t ” o r die ” Cannot open s t o p l i s t \n” ; @stop_words = <STOP>; c l o s e STOP; } sub t r i m ( $ ) { my $ s t r i n g = s h i f t ; $ s t r i n g =~ s /^\ s +//; $ s t r i n g =~ s /\ s+$ / / ; return $ s t r i n g ; } i f ( $format eq ” c s v ” ) { #p r i n t OUT ” id , l i n e , c l a s s \n ” ; } foreach my $ l i n e ( @ l i n e s ) { $ l i n e = trim ( $ l i n e ) ; my $ t r u e = 1 ; @parts = s p l i t ( / \ s +/, $ l i n e ) ;

H


i f ( index ( $ p a r t s [ 0 ] , ”p” ) != −1) { $true = 1; } else { $true = 0; }

print OUT ” $ i $ d e l i m ” ; $j = 0; for (my $k =1; $k<=$#p a r t s ; $k++) { # s t r i p a l l punctuation $ p a r t s [ $k ] =~ s / +/ / g ; $ p a r t s [ $k ] =~ s / [ [ : punct : ] ] / / g ; i f ( length ( $ p a r t s [ $k ] ) == 0 ) { next ; } # i s t h i s a s t o p −word ? i f ( grep ( /^ $ p a r t s [ $k ] $ / , @stop_words ) ) { print ” $ p a r t s [ k ] found ont s t o p l i s t \n” ; next ; } i f ( $k == 1 ) { $ s e n .= ” ’ ” ; } $ s e n .= ” $ p a r t s [ $k ] ” ; i f ( $k == $#p a r t s ) { $ s e n .= ” ’ ” ; i f ( $ i < $# l i n e s ) { $ s e n .= ” $ d e l i m ” ; } } } $sen = trim ( $sen ) ; push @sentences , $ s e n ; $sen = ”” ; my $count = $#p a r t s ; my $k = 0 ; foreach my $ p a r t ( @parts ) { i f ( length ( $ p a r t ) == 0 ) { s p l i c e @parts , $k , 1 ; $count −−; } $k++; }

105

H

106


foreach my $ p a r t ( @parts ) { i f ( $format eq ” a r f f ” && ( $ j == 1 ) ) { print OUT ” ’ ” ; } i f ( $ j != 0 ) { print OUT $ p a r t ; } i f ( $ j != 0 && $ j != $count ) { print OUT ” ” ; } i f ( $format eq ” a r f f ” && $ j == $count ) { print OUT ” ’ ” ; } $ j ++; } i f ( $ t r u e == 1 ) { print OUT ” $ d e l i m ” ; i f ( $format eq ” a r f f ” ) print OUT ” ’ ” ; } print OUT ” p o s i t i v e ” ; i f ( $format eq ” a r f f ” ) print OUT ” ’ ” ; } } else { print OUT ” $ d e l i m ” ; i f ( $format eq ” a r f f ” ) print OUT ” ’ ” ; } print OUT ” n e g a t i v e ” ; i f ( $format eq ” a r f f ” ) print OUT ” ’ ” ; } }

{

{

{

{

print OUT ” \n” ; $ i ++; } c l o s e OUT; i f ( $format eq ” a r f f ” ) { open F , ” <: u t f 8 ” , $ARGV[ 1 ] o r die ” E r r o r w h i l e o p e n i n g t h e f i l e ” ; open OUT, ” >: u t f 8 ” , $ARGV[ 1 ] . ” . o l d ” ;

H


@ l i n e s = ; # print additional info print OUT ” \ @ r e l a t i o n DP\n\n” ; print OUT ” \ @ a t t r i b u t e i d numeric \n” ; print OUT ” \ @ a t t r i b u t e t e x t { ” ; foreach my $ s e n t e n c e ( @ s e n t e n c e s ) { print OUT $ s e n t e n c e ; } print OUT ” }\n” ; print OUT ” \ @ a t t r i b u t e c l a s s { ’ p o s i t i v e ’ , ’ n e g a t i v e ’ } \ n\n” ; print OUT ” \@data\n” ; # print a l l the old l i n e s foreach my $ l i n e ( @ l i n e s ) { $ l i n e =~ s / ( \ s ’ ) / ’ /g ; print OUT $ l i n e ; } c l o s e OUT; rename $ARGV[ 1 ] . ” . o l d ” , $ARGV [ 1 ] ; }

107

Částečně řízené učení algoritmů strojového učení (semi-supervised learning)

Recommend Documents