ne-spam

´ padoc ˇeska ´ univerzita v Plzni Za ´ ch ve ˇd Fakulta aplikovany

Klasifikace textu do kategori´ı spam/ne-spam

KIV/PC

2. ledna 2015

Marek Zimmermann A12B0215P [email protected]

Obsah 1 Zad´ an´ı

2

2 Anal´ yza u ´ lohy 2.1 Klasifikaˇcn´ı algoritmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Datov´e struktury . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3 4

3 Popis implementace 3.1 Dictionary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Item . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Fungov´ an´ı programu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 7 7 8

4 Uˇ zivatelsk´ a pˇ r´ıruˇ cka 4.1 Pˇreklad programu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Spuˇstˇen´ı programu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10 10 10

5 Z´ avˇ er

12

1

Zad´ an´ı

Naprogramujte v ANSI C pˇrenositelnou konzolovou aplikaci, kter´a bude rozhodovat, zda u ´ sek textu (textov´ y soubor) je nebo nen´ı spam. Aplikace bude pˇrij´ımat z pˇr´ıkazov´e ˇr´adky sedm parametr˚ u: Prvn´ı dva parametry budou vzor jm´ena a poˇcet tr´enovac´ıch soubor˚ u obsahuj´ıc´ıch nevyˇz´adan´e zpr´avy (tzv. spam). Tˇret´ı a ˇctvrt´ y parametr budou vzor jm´ena a poˇcet tr´enovac´ıch soubor˚ u obsahuj´ıc´ıch vyˇz´adan´e zpr´avy (tzv. ham). P´ at´ y a ˇsest´ y parametr budou vzor jm´ena a poˇcet testovac´ıch soubor˚ u. Sedm´ y parametr pˇredstavuje jm´eno v´ ystupn´ıho textov´eho souboru, kter´ y bude po dokonˇcen´ı ˇcinnosti Vaˇs´ı aplikace obsahovat v´ ysledky klasifikace testovac´ıch soubor˚ u. Program se bude spouˇstˇet pˇr´ıkazem: classify.exe hspami hspam-cnti hhami hham-cnti htesti htest-cnti hout-filei Symboly hspami, hhami a htesti pˇredstavuj´ı vzory jm´ena vstupn´ıch soubor˚ u. Symboly hspam-cnti, hham-cnti a htest-cnti pˇredstavuj´ı poˇcty vstupn´ıch soubor˚ u. Vstupn´ı soubory maj´ı n´asleduj´ıc´ı pojmenov´ an´ı: vzorN, kde N je cel´e ˇc´ıslo z intervalu h1; N i. Pˇr´ıpona vˇsech vstupn´ıch soubor˚ u je .txt, pˇr´ıpona nen´ı souˇc´ast´ı vzoru. V´aˇs program tedy m˚ uˇze b´ yt bˇehem testov´an´ı spuˇstˇen napˇr´ıklad takto: ...\>classify.exe spam 10 ham 20 test 50 result.txt V´ ysledkem ˇcinnosti programu bude textov´ y soubor, kter´ y bude obsahovat seznam testovan´ ych soubor˚ u a jejich klasifikaci. Pokud nebude na pˇr´ıkazov´e ˇr´ adce uvedeno pr´avˇe sedm argument˚ u, vypiˇste chybov´e hl´aˇsen´ı a struˇcn´ y n´ avod k pouˇzit´ı programu v angliˇctinˇe podle bˇeˇzn´ ych zvyklost´ı (viz napˇr. uk´azkov´ a semestr´aln´ı pr´ ace na webu pˇredmˇetu Programov´an´ı v jazyce C). Vstupem programu jsou pouze argumenty na pˇ r´ıkazov´ eˇ r´ adce – interakce s uˇ zivatelem pomoc´ı kl´ avesnice ˇ ci myˇ si v pr˚ ubˇ ehu pr´ ace programu se neoˇ cek´ av´ a. Hotovou pr´ aci odevzdejte v jedin´em archivu typu ZIP prostˇrednictv´ım automatick´eho odevzd´avac´ıho a validaˇcn´ıho syst´emu. Archiv necht’ obsahuje vˇsechny zdrojov´e soubory potˇrebn´e k pˇreloˇzen´ı programu, makefile pro Windows i Linux (pro pˇreklad v Linuxu pˇripravte soubor pojmenovan´ y makefile a pro Windows makefile.win) a dokumentaci ve form´atu PDF vytvoˇrenou v typografick´em syst´emu TEX, resp. LATEX. Bude-li nˇekter´a z ˇc´ast´ı chybˇet, kontroln´ı skript Vaˇsi pr´ aci odm´ıtne1 .

1´ Upln´e znˇen´ı zad´ an´ı dostupn´e na webov´e adrese pˇredmˇetu KIV/PC: http://www.kiv.zcu.cz/studies/predmety/pc/doc/work/sw2014-03.pdf

2

2

Anal´ yza u ´ lohy

C´ılem programu je klasifikovat danou mnoˇzinu e–mail˚ u. Klasifikovat budeme do 2 kategori´ı: ham (vyˇz´ adan´ a poˇsta) nebo spam (nevyˇz´adan´a poˇsta). Poˇzadovan´a pˇresnost klasifikace je alespoˇ n 90%2 . Pˇri anal´ yze u ´lohy pak bude d˚ uleˇzit´a volba klasifikaˇcn´ıho algoritmu a struktury, kterou budeme vyuˇz´ıvat pro tr´enov´ an´ı a posl´eze klasifikaci.

2.1

Klasifikaˇ cn´ı algoritmy

Pro klasifikaci e–mail˚ u lze vyuˇz´ıt nˇekolika klasifik´ator˚ u: Support Vector Machine, naivn´ı Bayes˚ uv klasifik´ ator, klasifik´ ator Maxim´aln´ı entropie a dalˇs´ı. Support Vector Machines (SVM) je metoda strojov´eho uˇcen´ı, kter´a v u ´loze klasifikace hled´a nadrovinu, kter´ a v prostoru pˇr´ıznak˚ u rozdˇeluje data od sebe tak, aby minim´aln´ı vzd´alenost bod˚ u z n mnoˇzin byla maxim´ aln´ı (viz obr´azek 1). Toto plat´ı v pˇr´ıpadˇe, kdy jsou od sebe mnoˇziny line´ arnˇe separovateln´e. Pokud tomu tak nen´ı, vyuˇz´ıv´a se tzv. j´adrov´a funkce (kernel function, nebo tak´e kernel transformation), kter´a pˇrevede line´arnˇe neseparovatelnou u ´lohu na line´arnˇe separovatelnou pomoc´ı projekc´ı do vyˇsˇs´ı dimenze, neˇz jsou vstupn´ı data [1]).

Obr´azek 1: Bin´ arn´ı SVM klasifik´ ator, Zdroj: http://docs.opencv.org/doc/tutorials/ ml/introduction_to_svm/introduction_to_svm.html Naivn´ı Bayes˚ uv klasifik´ ator (NBC) je pravdˇepodobnostn´ı klasifik´ator, zaloˇzen´ y na aplikaci tzv. Bayesovy vˇety a pˇredpokladu nez´avislosti mezi dan´ ymi pˇr´ıznaky (coˇz v realitˇe vˇetˇsinou neplat´ı – proto naivn´ı“). Mezi jeho klady patˇr´ı schopnost inkrement´aln´ıho uˇcen´ı (je moˇzn´e ho ” po testov´an´ı dotr´enovat pomoc´ı nov´ ych dat) a tak´e je vhodn´ y pro klasifikaci velk´eho souboru dat d´ıky pˇredpokladu nez´ avislosti mezi dan´ ymi pˇr´ıznaky – tato vlastnost totiˇz zjednoduˇsuje vzorec potˇrebn´ y pro v´ ypoˇcet pravdˇepodobnosti. Jeho klasifikaˇcn´ı u ´spˇeˇsnost je v´ yraznˇe z´avisl´ a na kvalitˇe tr´enovac´ı mnoˇziny. Grafick´ a uk´azka klasifikace bodu podle jeho polohy je zachycena v obr´azku 2. Z tˇechto dvou algoritm˚ u, kter´e patˇr´ı mezi nejpouˇz´ıvanˇejˇs´ı v oblasti klasifikace e–mail˚ u, jsem se rozhodl zvolit NBC, nebot’ s n´ım lze dos´ahnout poˇzadovan´e u ´spˇeˇsnosti, byl doporuˇcen v zad´an´ı pr´ ace a pˇriˇsel mi jednoduˇsˇs´ı na implementaci. 2

Tedy napˇr´ıklad ze 100 klasifikovan´ ych dokument˚ u jich mus´ı b´ yt spr´ avnˇe klasifikov´ ano nejm´enˇe 90.

3

Obr´ azek 2: NBC – klasifikace b´ıl´eho bodu na z´akladˇe polohy, Zdroj: http://www.statsoft.com/textbook/naive-bayes-classifier

2.2

Datov´ e struktury

Pro dan´ y klasifik´ ator je pak tˇreba navrhnout vhodnou datovou strukturu, kter´a bude uchov´avat v´ ysledky tr´enov´ an´ı a posl´eze bude vyuˇzita pro klasifikaci testovac´ıch e–mail˚ u. Prvn´ı strukturou, kter´ a by mohla b´ yt pouˇzita, je bin´arn´ı vyhled´avac´ı strom (BST – Binary search tree). Ten se skl´ ad´ a z bin´ arn´ıho stromu, tj. orientovan´eho grafu s jedn´ım bodem jakoˇzto poˇc´atkem (tzv. koˇren), z nˇehoˇz lze naj´ıt cestu do jak´ehokoliv vrcholu, pˇriˇcemˇz kaˇzd´ y vrchol m´a maxim´ alnˇe dva potomky a pr´ avˇe jednoho pˇredka (pouze koˇren ˇz´adn´eho nem´a). Bin´arn´ı vyhled´avac´ı strom se od bin´ arn´ıho stromu liˇs´ı tak, ˇze kl´ıˇce, pˇriˇrazen´e kaˇzd´emu uzlu, jsou uspoˇr´ad´any tak, ˇze hodnota lev´eho podstromu uzlu je menˇs´ı neˇz hodnota uzlu a hodnota prav´eho podstromu je naopak vyˇsˇs´ı neˇz hodnota uzlu (viz obr´azek 3).

Obr´ azek 3: Uk´ azka jednoduch´eho BST, Zdroj: http: //cs.wikipedia.org/wiki/Bin%C3%A1rn%C3%AD_vyhled%C3%A1vac%C3%AD_strom Druhou strukturou vhodnou k pouˇzit´ı je hashovac´ı tabulka (hash table). Jej´ı princip spoˇc´ıv´a v tom, ˇze pro data, kter´ a chceme uloˇzit, z´ısk´ame kl´ıˇc pomoc´ı tzv. hashovac´ı funkce a data pak podle kl´ıˇce uloˇz´ıme. Kl´ıˇc pot´e rovnˇeˇz slouˇz´ı k nalezen´ı dat v dan´e tabulce. Jako struktura pro uloˇzen´ı tabulky se nejˇcastˇeji pouˇz´ıv´a pole. Pˇri vkl´ad´an´ı dat m˚ uˇze d´ıky pˇriˇrazen´ı stejn´eho kl´ıˇce r˚ uzn´ ym dat˚ um nastat kolize, kterou lze ˇreˇsit nˇekolika zp˚ usoby. Nejjednoduˇsˇs´ım ˇreˇsen´ım je tzv. zˇretˇezen´ı z´ aznam˚ u (separate chaining), kdy kaˇzd´a poloˇzka tabulky je seznamem prvk˚ u se stejn´ ym kl´ıˇcem. Dalˇs´ım zp˚ usobem pak m˚ uˇze b´ yt otevˇren´a adresace (nebo tak´e otevˇren´e rozptylov´ an´ı, anglicky open addressing), kde data, kter´a by mˇela b´ yt um´ıstˇena na jiˇz obsazen´e m´ısto, jsou um´ıstˇena na jin´e voln´e m´ısto, kter´e urˇc´ı zvolen´ y algoritmus. Rozd´ıl je zobrazen na obr´ azku 4. Dalˇs´ı strukturou, kter´ a by mohla b´ yt vhodn´a pro uchov´av´an´ı dat, je trie. Strukturou je velmi podobn´ a BVS, avˇsak vrchol zde nemus´ı m´ıt nejv´ yˇse dva potomky (m˚ uˇze jich m´ıt tolik, kolik potˇrebujeme) a jako kl´ıˇc se zde hojnˇe vyuˇz´ıvaj´ı ˇretˇezce (popˇr. znaky z jednotliv´ ych 4

Obr´azek 4: Zˇretˇezen´ı z´ aznam˚ u (vlevo) a otevˇren´a adresace (vpravo) u hashovac´ı tabulky, Zdroj: http://en.wikipedia.org/wiki/Hash_table ˇretˇezc˚ u). Vˇsichni n´ asledn´ıci uzlu maj´ı spoleˇcn´ y prefix, kter´ y je shodn´ y s ˇretˇezcem pˇriˇrazen´ ym k dan´emu uzlu. Koˇren je asociovan´ y s pr´azdn´ ym ˇretˇezcem. Kaˇzd´ y uzel si s sebou nese informaci, zda je nebo nen´ı koncov´ ym p´ısmenem nˇejak´eho slova. Trie b´ yv´a velmi ˇcasto pouˇz´ıv´ana pro uloˇzen´ı slovn´ık˚ u, kde vynik´ a kromˇe rychlosti i v pˇr´ızniv´ ych n´aroc´ıch na pamˇet’, a to t´ım v´ıce, ˇc´ım v´ıce je ve slovn´ıku slov se stejn´ ym prefixem. Na obr´azku 5 m˚ uˇzeme vidˇet uloˇzen´ı dan´ ych slov ze slovn´ıku tak, ˇze pro slova s celkov´ ym souˇctem osmn´acti znak˚ u staˇc´ı v trie pouze jeden´ act uzl˚ u.

Obr´ azek 5: Trie pro slova A“, to“, tea“, ted“, ten“, i“, in“ a inn“, ” ” ” ” ” ” ” ” Zdroj: http://en.wikipedia.org/wiki/Trie U n´ami zvolen´e struktury klademe d˚ uraz zejm´ena na operace vloˇzen´ı a hled´an´ı prvku, nebot’ pˇri tr´enov´ an´ı budeme do struktury pouze vkl´adat, nebo ji hledat (abychom j´ı upravili) a pˇri klasifikaci jiˇz pouze hledat (pro ˇcten´ı uloˇzen´ ych informac´ı). V tabulce 1 lze vidˇet, ˇze dobr´e v´ ysledky v tˇechto operac´ıch by mˇela pod´avat zejm´ena hashtable[2] a trie. V nejhorˇs´ım pˇr´ıpadˇe m´ a u operac´ı vkl´ ad´ an´ı a hled´ an´ı BVS a hashtable sloˇzitost O(n), kde n je poˇcet prvk˚ u ve stromu ˇci tabulce a trie O(m), kde m je poˇcet uzl˚ u vedouc´ı k prvku (tedy poˇcet p´ısmen ve slovˇe). Zde by tedy mˇela b´ yt v´ıtˇezem trie[3]. Ze dvou vhodn´ ych kandid´ at˚ u jsem se nakonec rozhodl zvolit hashovac´ı tabulku se zˇretˇe5

Operace BVS Hled´ an´ı O(log n) Vkl´ ad´ an´ı O(log n)

Hashtable O(1) O(n)

Trie O(m) O(m)

Tabulka 1: Pr˚ umˇern´ a asymptotick´a sloˇzitost operac´ı u BVS, hashtable a trie zen´ım z´aznam˚ u jakoˇzto dobr´ y kompromis mezi pamˇet’ovou a v´ ypoˇcetn´ı n´aroˇcnost´ı a jednoduchost´ı implementace.

6

3

Popis implementace

3.1

Dictionary

Struktura Dictionary (viz zdrojov´ y k´od 1) v sobˇe uchov´av´a slova ve formˇe hashtabulky (pole ukazatel˚ u na strukturu Item o velikosti DICT ARRAY SIZE3 ), poˇcet zpracovan´ ych slov ze spamov´ ych (spam words) a hamov´ ych (ham words) soubor˚ u vˇcetnˇe duplicit, poˇcet unik´atn´ıch zpracovan´ ych slov z obou kategori´ı (unique words) a poˇcet zpracovan´ ych spamov´ ych a hamov´ ych soubor˚ u (spam files a ham files). Zdrojov´ y k´od 1: Struktura Dictionary typedef struct { Item ∗ words [ DICT ARRAY SIZE ] ; int spam words ; int ham words ; int u n i q u e w o r d s ; int s p a m f i l e s ; int h a m f i l e s ; } Dictionary ;

3.2

Item

Struktura Item (viz zdrojov´ y k´ od 2) uchov´av´a dan´e slovo (word), informace o poˇctu v´ yskyt˚ u dan´eho slova ve spamu (spam occur) a v hamu (ham occur), hodnoty pravdˇepodobnosti v´ yskytu slova v dan´e kategorii (spam prob a ham prob), a protoˇze je tato struktura koncipov´ana z´ aroveˇ n jako poloˇzka spojov´eho seznamu, uchov´av´a i ukazatel na dalˇs´ı prvek (next). Zdrojov´ y k´od 2: Struktura Item typedef struct ITEM { char ∗word ; int spam occur ; int ham occur ; double spam prob ; double ham prob ; struct ITEM ∗ next ; } Item ; 3

Konkr´etn´ı velikost pole pops´ ana v sekci 5

7

3.3

Fungov´ an´ı programu

Program nejprve zkontroluje vstupn´ı parametry programu – jejich spr´avn´ y poˇcet (mus´ı jich b´ yt pˇresnˇe sedm) a zda je druh´ y, ˇctvrt´ y a ˇsest´ y parametr cel´e ˇc´ıslo. V pˇr´ıpadˇe, ˇze nˇekter´ a z kontrol selˇze, program vyp´ıˇse chybu, n´apovˇedu a ukonˇc´ı se. Pokud kontrola probˇehla v poˇr´ adku, program se pokus´ı alokovat m´ısto pro slovn´ık (strukturu Dictionary). V pˇr´ıpadˇe ne´ uspˇeˇsn´eho pokusu se zobraz´ı v´ ypis chyby a program se ukonˇc´ı. Pokud do t´eto chv´ıle probˇehlo vˇse v poˇr´adku, zaˇc´ın´a tr´enov´an´ı. E–maily jsou pˇredzpracov´any do soubor˚ u s pˇr´ıponou .txt tak, ˇze jeden soubor je roven jednomu e–mailu. Soubor se pak skl´ad´a ze slov oddˇelen´ ych mezerou. Vˇsechna slova jsou na jedn´e ˇr´adce, konec ˇr´adky je 4 tedy i koncem souboru . Program postupnˇe otevˇre kaˇzd´ y soubor, naˇcte jeho obsah do bufferu a postupnˇe z nˇej zpracuje kaˇzd´e slovo. Pr´ avˇe zpracov´ avan´e slovo zkus´ı naj´ıt ve slovn´ıku. V pˇr´ıpadˇe jeho nalezen´ı zv´ yˇs´ı o jedna potˇrebn´e ˇc´ıtaˇce. Pokud slovo nenajde, pokus´ı se ho vytvoˇrit a uloˇzit do slovn´ıku. Pokud dojde k chybˇe u zpracov´ an´ı souboru, program vyp´ıˇse chybu a jej´ı struˇcn´ y popis a ukonˇc´ı se. Tento postup byl zvolen, protoˇze pokud by doˇslo k chybn´emu natr´enov´an´ı d´ıky chybˇej´ıc´ım dat˚ um, mohlo by nastat v´ yrazn´e ovlivnˇen´ı klasifikace testovac´ıch soubor˚ u. Jako hashovac´ı funkce bylo zvoleno seˇcten´ı ASCII hodnot p´ısmen dan´eho slova modulo velikost´ı slovn´ıku. Protoˇze program pracuje ve stylu naˇcti, natr´enuj, klasifikuj, ukonˇci se“ a nevyuˇz´ıv´ a ” tedy jednu z vlastnost´ı NBC (viz sekce 2) – schopnost inkrement´aln´ıho uˇcen´ı – m˚ uˇzeme jeˇstˇe pˇred samotnou klasifikac´ı prov´est malou optimalizaci. Aby program nemusel pro kaˇzd´e slovo opakovanˇe poˇc´ıtat hodnotu pravdˇepodobnosti v dan´e kategorii, m˚ uˇzeme si tyto hodnoty pˇredem vypoˇc´ıtat a uloˇzit do samotn´e struktury dan´eho slova5 (viz spam prob a ham prob v podsekci 3.2). V tuto chv´ıli m˚ uˇze zaˇc´ıt klasifikace testovac´ıch soubor˚ u. Kaˇzd´ y testovac´ı soubor je otevˇren, jeho obsah je naˇcten a zpracov´ an. Standardnˇe by se pro v´ ypoˇcet pravdˇepodobnosti, ˇze dan´ y soubor patˇr´ı do dan´e kategorie, pouˇzil vzorec 1, kde PC je pravdˇepodobnost v´ yskytu dan´e kategorie (zpracovan´e soubory podˇelen´e vˇsemi soubory) a P (wordi |C) je pravdˇepodobnost v´ yskytu slova v dan´e kategorii. PS = PC ×

n Y

P (wordi |C)

(1)

i=0

Protoˇze by zde vˇsak doˇslo k tzv. podteˇcen´ı (ztr´ata pˇresnosti, zde d´ıky n´asoben´ı velmi mal´ ych hodnot mezi sebou), pravdˇepodobnosti zlogaritmujeme a seˇcteme (viz vzorec 2), ˇc´ımˇz doc´ıl´ıme spr´ avn´eho v´ ysledku, nebot’ mal´e hodnoty se zde sˇc´ıtaj´ı a k podteˇcen´ı tak nedojde. Ps = log (PC ) +

n X

log (P (wordi |C))

(2)

i=0

Pravdˇepodobnost v´ yskytu slova v dan´e kategorii se spoˇcte dle vzorce 3, kde ni je poˇcet v´ yskyt˚ u slova v dan´e kategorii zv´ yˇsen´ y o jedna (aby v logaritmu nebyla nula), DC je celkov´ y poˇcet slov zpracovan´ y slovn´ıkem v dan´e kategorii a DU je celkov´ y poˇcet unik´atn´ıch slov zpracovan´ y slovn´ıkem. P (wordi |C) = 4 5

ni + 1 DC + DU

Pˇresnˇeji: soubory neobsahuj´ı ˇza ´dn´ y znak pro ukonˇcen´ı ˇra ´dky, obsahuj´ı pouze znak konce souboru. V´ ysledky proveden´e optimalizace viz sekce 5

8

(3)

Po v´ ypoˇctu pravdˇepodobnosti souboru v obou kategori´ıch se dle vyˇsˇs´ı hodnoty jedn´e z nich rozhodne, zda jde o spam nebo ham. V´ ysledky se pak zapisuj´ı do souboru, jehoˇz n´azev byl zad´an jako sedm´ y parametr pˇri spuˇstˇen´ı. Na kaˇzd´ y ˇr´adek souboru je zaps´an jeden v´ ysledek ve form´atu: n´ azev souboru, tabul´ ator, H (signalizuj´ıc´ı ham) nebo S (signalizuj´ıc´ı spam) a konec ˇr´adky. Pokud se nˇekter´ a z ˇc´ ast´ı programu nevykon´a spr´avnˇe a program je nucen ukonˇcit svou ˇcinnost, kromˇe struˇcn´eho v´ ypisu chyby z´ısk´ame i n´avratov´ y k´od chyby. K´ody jsou rozdˇeleny n´asledovnˇe: • 0 – program probˇehl spr´ avnˇe (bez chyb), • 1 – ˇspatnˇe zadan´e nebo ˇz´ adn´e vstupn´ı parametry, • 2 – probl´em s alokac´ı pamˇeti pˇri vytv´aˇren´ı struktury Dictionary, • 3 – I/O chyba (nezdaˇrilo se otevˇren´ı souboru, z´apis do souboru, soubor neexistuje ...), • 4 – jin´e probl´emy s alokac´ı pamˇeti (napˇr. struktury Item pro nov´e slovo)

9

4

Uˇ zivatelsk´ a pˇ r´ıruˇ cka

4.1

Pˇ reklad programu

Program mus´ı b´ yt pˇred pouˇzit´ım pˇreloˇzen. Pro zjednoduˇsen´ı jsou pˇripraveny dva makefile soubory (makefile pro Linux a makefile.win pro Windows). Oba dva vyˇzaduj´ı m´ıt na dan´em syst´emu zprovoznˇen´ y make a gcc pˇrekladaˇc. V Linuxu se tohoto stavu d´a doc´ılit prost´ ym nainstalov´ an´ım bal´ıˇck˚ u make a gcc6 . Ve Windows bude potˇreba nainstalovat MinGW7 nebo CygWin a (pokud to bude nutn´e) pˇridat um´ıstˇen´ı dan´eho programu do syst´emov´e promˇenn´e PATH. Na Linuxu m˚ uˇzeme program pˇreloˇzit v dan´em adres´aˇri pˇr´ıkazem: make Pokud pˇreklad prob´ıh´ a na Windows, pˇreloˇz´ıme program pomoc´ı: make −f m a k e f i l e . win

4.2

Spuˇ stˇ en´ı programu

Po pˇrekladu se ve stejn´em adres´ aˇri objev´ı soubor classify.exe. Program se pouˇst´ı pˇres konzoli v n´ asleduj´ıc´ım form´ atu: classify.exe hspami hspam-cnti hhami hham-cnti htesti htest-cnti hout-filei Prvn´ım parametrem je vzorov´e jm´eno tr´enovac´ıch spamov´ ych soubor˚ u (napˇr pro vzor spam“ ” m˚ uˇze b´ yt jeden ze soubor˚ u spam3.txt“). Druh´ ym parametrem je pak poˇcet tˇechto soubor˚ u. ” Tˇret´ım parametrem je vzorov´e jm´eno tr´enovac´ıch hamov´ ych soubor˚ u, ˇctvrt´ ym pak jejich poˇcet. P´at´ ym je vzorov´e jm´eno soubor˚ u, kter´e maj´ı b´ yt klasifikov´any, ˇsest´ ym parametrem je pak jejich poˇcet. Posledn´ım (sedm´ ym) parametrem je pak n´azev souboru, do kter´eho se budou zapisovat v´ ysledky klasifikace jednotliv´ ych testovan´ ych soubor˚ u. Na obr´azku 6 lze vidˇet chov´an´ı pˇri spuˇstˇen´ı s korektn´ımi parametry.

Obr´ azek 6: Uk´ azka v´ ystupu spr´avn´eho bˇehu programu Pokud jsou vstupn´ı parametry ˇspatn´e nebo pˇri bˇehu nastane chyba, program struˇcnˇe vyp´ıˇse kde nastala chyba a ukonˇc´ı sv˚ uj bˇeh. Pokud jsou zad´any chybn´e parametry, program 6 7

Pˇreklad otestov´ an na gcc ve verzi 4.9.1 na operaˇcn´ım syst´emu Debian GNU/Linux 8.0 (64 bit). Pˇreklad otestov´ an za pomoc´ı MinGW verze 4.8.1 na operaˇcn´ım syst´emu Windows 7 Professional 64 bit.

10

kromˇe v´ ypisu probl´emu s parametry zobraz´ı i n´apovˇedu. Pro uk´azku bˇehu programu pˇri chybˇej´ıc´ım tr´enovac´ım souboru viz obr´azek 7.

Obr´ azek 7: Uk´ azka v´ ystupu programu, pokud chyb´ı testovac´ı soubor

11

5

Z´ avˇ er

Program splnil zad´ an´ı, jeho u ´spˇeˇsnost klasifikace byla 98 % (z dodan´ ych 200 testovan´ ych soubor˚ u 3 ham soubory klasifikoval jako spamy a 1 spam jako ham). ˇ Casy bˇehu programu na Linuxu (tabulka 2) ukazuj´ı pˇribliˇznˇe 4 aˇz 5 % zrychlen´ı programu vlivem optimalizace (viz sekce 3.3) a m´ırn´e urychlov´an´ı bˇehu pˇri zvyˇsov´an´ı velikosti hashovac´ı tabulky, kromˇe posledn´ı hodnoty 5000, kter´a se t´emˇeˇr rovnala v´ ysledk˚ um u velikosti 1500. Pokud se pod´ıv´ ame na ˇcasy bˇehu programu ve Windows (tabulka 3), ukazuj´ı v´ıcem´enˇe podobn´ y trend, pouze hodnoty u velikosti 1500 jsou neoˇcek´avanˇe vysok´e. Pravdˇepodobnˇe se na jejich v´ ysledc´ıch projevily sluˇzby bˇeˇz´ıc´ı na pozad´ı (a to i pˇres to, ˇze kaˇzd´a v´ ysledn´a hodnota pˇredstavuje pr˚ umˇer z 10 mˇeˇren´ı). Bohuˇzel, hodnoty pro porovn´ an´ı bˇehu se stejn´ ym nastaven´ım v Linuxu a ve Windows nejsou porovnateln´e, nebot’ pˇri mˇeˇren´ı bˇehu na Windows byl omylem zapnut´ y debug reˇzim (zajiˇst’uj´ıc´ı detailnˇejˇs´ı v´ ypisy bˇehu programu), coˇz pravdˇepodobnˇe ovlivnilo v´ ysledn´ y ˇcas. ˇ Casy jsou tak vz´ ajemnˇe porovnateln´e pouze v r´amci stejn´eho syst´emu. Dle m´eho n´azoru vˇsak nebylo ovlivnˇen´ı natolik velk´e, aby se nedalo konstatovat, ˇze program bˇeˇzel rychleji na Linuxu. ˇ bˇehu programu v z´ Cas avislosti na optimalizaci a velikosti hash tabulky Velikost hashovac´ı tabulky 500 1000 1500 5000 Bez optimalizace 0,138 s 0,126 s 0,122 s 0,123 s S optimalizac´ı 0,131 s 0,122 s 0,116 s 0,117 s Tabulka 2: Mˇeˇren´ı ˇcasu bˇehu programu – Linux ˇ bˇehu programu v z´ Cas avislosti na optimalizaci a velikosti hash tabulky Velikost hashovac´ı tabulky 500 1000 1500 5000 Bez optimalizace 0,280 s 0,268 s 0,274 s 0,271 s S optimalizac´ı 0,275 s 0,271 s 0,270 s 0,270 s Tabulka 3: Mˇeˇren´ı ˇcasu bˇehu programu – Windows Program by samozˇrejmˇe mohl b´ yt jeˇstˇe vylepˇsen. Ke kontrole parametr˚ u by ˇslo pˇridat i kontrolu existence samotn´ ych soubor˚ u potˇrebn´ ych pro bˇeh programu (tak, aby program nebyl pˇreruˇsen kv˚ uli tomuto probl´emu uprostˇred uˇcen´ı ˇci klasifikace). Urychlen´ı by mohlo pˇrin´est implementov´ an´ı datov´e struktury jakoˇzto trie za cenu zv´ yˇsen´e pamˇet’ov´e n´aroˇcnosti, coˇz dnes nen´ı ˇz´ adn´ y probl´em, nebot’ pamˇeti b´ yv´a obecnˇe v´ıce neˇz procesorov´eho v´ ykonu. Pokud z˚ ustaneme u hashovac´ı tabulky, bylo by vhodn´e vymyslet algoritmus, kter´ y by jej´ı velikost vypoˇc´ıtal v z´ avislosti na vstupn´ıch datech a pak ji dynamicky vytv´aˇrel. Nyn´ı je vytv´aˇrena staticky s velikost´ı, kter´ a byla optimalizov´ana pro testovac´ı data, ale nemus´ı b´ yt stejnˇe efektivn´ı pro jin´ y (jinak velk´ y) soubor dat. Zrychlen´ı programu by tak´e mohla pˇrin´est lepˇs´ı hashovac´ı funkce, kter´ a by rovnomˇernˇeji zaplˇ novala tabulku (m´enˇe pr´azdn´ ych ˇr´adk˚ u a m´enˇe nebo ˇz´ adn´e kolize na nˇekter´ ych ˇr´adc´ıch). Program u ´spˇeˇsnˇe proˇsel testov´ an´ım pomoc´ı Valgrindu (nebyly detekov´any ˇz´adn´e u ´niky pamˇeti) a kontrolou pomoc´ı Splint, kter´ y nakonec nahl´asil pouze jedno varov´an´ı ohlednˇe pouˇz´ıv´an´ı funkce sprintf a radil nahrazen´ı bezpeˇcnˇejˇs´ı funkc´ı snprintf. Tuto chybu bohuˇzel nebylo moˇzn´e opravit, nebot’ snprintf nen´ı souˇc´ast´ı standardu ANSI C. Program byl vˇsak konstruov´an tak, ˇze by k pˇreteˇcen´ı u funkce sprintf nikdy nemˇelo doj´ıt. 12

Reference [1] Autor: Michal Hrala, N´azev publikace: Automatick´ a klasifikace dokument˚ u s podobn´ym obsahem. Vydavatel: Z´ apadoˇcesk´ a univerzita v Plzni, Rok: 2012, URI: http://hdl.handle.net/11025/3054 [2] URL: http://bigocheatsheet.com/ Rok: 2014, Pozn´amka: posledn´ı pˇr´ıstup 21.12.2014 [3] URL: http://en.wikipedia.org/wiki/Trie Rok: 2014, Pozn´amka: posledn´ı pˇr´ıstup 21.12.2014

13