DuˇsanJenˇc´ık Kategorizaceuˇzivatel˚unaz´akladˇehistoriestahovan´ychwebov´ychdokument˚u

Bakal´aˇrsk´a pr´ace

Kategorizace uˇ zivatel˚ u na z´ akladˇ e historie stahovan´ ych webov´ ych

dokument˚ u

Duˇ san Jenˇ c´ık

Vedouc´ı pr´ace: Ing. Jan ˇSediv´y, CSc.

Cesk´ˇ e vysok´e uˇcen´ı technick´e v Praze Fakulta elektrotechnick´a

České vysoké učení technické v Praze Fakulta elektrotechnická

Katedra kybernetiky

ZADÁNÍ BAKALÁŘSKÉ PRÁCE

Student: Dušan J e n č í k

Studijní program: Otevřená informatika (bakalářský)

Obor: Informatika a počítačové vědy

Název tématu: Kategorizace uživatelů na základě historie stahovaných webových dokumentů

Pokyny pro vypracování:

Cílem této práce je kategorizovat uživatele internetu na základě znalosti historie stahování webových dokumentů. Úkolem kategorizace je zařadit uživatele do různých kategorií (např.

ženy, děti, podle věku apod.). Pro práci bude poskytnuta databáze posloupností stahovaných URI skutečných uživatelů internetu. Postupujte podle následujících kroků:

• Prostudujte metody pro klástrování do kategorií.

• Prostudujte generativní statistické modely pro uspořádání URI do neznámých kategorií.

• Proveďte základní statistickou analýzu poskytnuté databáze.

• Vyberte vhodné algoritmy na základě předchozí analýzy a aplikujte je na databázi

• Nalezněte vhodná kritéria pro posouzení kvality kategorizace vybranými algoritmy a posuďte jejich přesnost a vhodnost.

Seznam odborné literatury:

[1] Kanungo, Tapas, et al. "An efficient k-means clustering algorithm: Analysis and

implementation." Pattern Analysis and Machine Intelligence, IEEE Transactions on 24.7 (2002): 881-892.

[2] Ahmed, Amr, and Alexander Smola. "Www 2011 invited tutorial overview: latent variable models on the internet." Proceedings of the 20th international conference companion on World wide web. ACM, 2011.

[3] Attardi, Giuseppe, Antonio Gulli, and Fabrizio Sebastiani. "Automatic Web page

categorization by link and context analysis." Proceedings of THAI. Vol. 99. No. 99. 1999.

[4] Pedregosa, Fabian, et al. "Scikit-learn: Machine learning in Python." The Journal of Machine Learning Research 12 (2011): 2825-2830.

Vedoucí bakalářské práce: Ing. Jan Šedivý, CSc.

Platnost zadání: do konce letního semestru 2015/2016

L.S.

doc. Dr. Ing. Jan Kybic vedoucí katedry

prof. Ing. Pavel Ripka, CSc.

děkan

Prohl´ aˇ sen´ı autora pr´ ace

Prohlaˇsuji, ˇze jsem pˇredloˇzenou pr´aci vypracoval samostatnˇe a ˇze jsem uvedl veˇsker´e pouˇzit´e informaˇcn´ı zdroje v souladu s Metodick´ym pokynem o dodrˇzov´an´ı etick´ych princip˚u pˇri pˇr´ıpravˇe vysokoˇskolsk´ych z´avˇereˇcn´ych prac´ı.

V Praze dne . . . . . . . .

Podpis autora pr´ace

Podˇ ekov´ an´ı

R´ad bych podˇekoval pˇredevˇs´ım m´emu vedouc´ımu Ing. Janovi ˇSediv´emu, CSc., kter´y mi nab´ıdl toto t´ema bakal´aˇrsk´e pr´ace a po celou dobu jej´ıho vypracov´an´ı byl perfektn´ım vedouc´ım.

D´ale bych sv´e podˇekov´an´ı vˇenoval i Ing. Tom´aˇsovi Gog´arovi, Ing. Tom´aˇsovi Tuny- sovi a Ing. Tom´aˇsovi Baˇrinovi za obˇetavou pomoc pˇri vypracov´av´an´ı t´eto pr´ace.

V´ypoˇcetn´ı prostˇredky byly poskytnuty MetaCentrem v r´amci programu LM2010005 a skupinou CERIT-SC v r´amci programu Center CERIT Scientific Cloud, kter´a je souˇc´ast´ı Operational Program Research and Development for Innovations, reg. ˇc. CD.1.05 / 3.2.00 / 08.0144.

M´e rodinˇe.

Abstrakt

C´ılem t´eto pr´ace je nalezen´ı metod a postup˚u vedouc´ıch ke kategorizaci uˇzivatel˚u dle historie jejich z´aznam˚u z proch´azen´ı internetu. Pr´ace vyuˇz´ıv´a analytick´e a statis- tick´e metody, kter´ymi se snaˇz´ı nal´ezt kategorie webov´ych str´anek charakteristick´ych pro urˇcitou skupinu uˇzivatel˚u. Bylo zjiˇstˇeno, ˇze shlukovac´ı algoritmy nejsou dostateˇcnˇe popisn´e pro nalezen´ı poˇzadovan´ych kategori´ı, a tak bylo vyuˇzito topic-model algoritmu pLSA. D´ıky tomuto algoritmu byla nalezena t´emata tvoˇren´a distribucemi webov´ych str´anek a z´aroveˇn kaˇzd´y uˇzivatel byl pops´an distribuc´ı nalezen´ych t´emat. Popis t´emat byl doplnˇen o kategorie z DMOZ datab´aze a n´aslednˇe o nejv´yznamnˇejˇs´ı slova, kter´a se vyskytuj´ı na str´ank´ach charakterizuj´ıc´ıch dan´e t´ema. Pro tuto pr´aci byla poskytnuta zanonymizovan´a data nejmenovanou antivirovou spoleˇcnost´ı.

Kl´ıˇcov´a slova kategorizace, shlukov´a anal´yza, topic-model, pLSA

Abstract

The aim of this thesis is to find methods and procedures which are leading to ca- tegorization of users with respect to history of their records from internet browsing.

The work uses analytical and statistical methods, by which it tries to find some ca- tegories of websites, which are characteristic for a specific group of users. It has been found that clustering algorithms are not sufficiently descriptive for finding required categories, and thus it has been used topic-model algorithm named pLSA. The topics

Obsah

1 Uvod´ 1

1.1 Motivace . . . 1

1.2 Definice probl´emu . . . 2

1.2.1 Data . . . 2

1.2.2 Probl´em . . . 2

1.3 Struktura pr´ace . . . 3

2 Souvisej´ıc´ı pr´ace 4 2.1 Anal´yza clickstreamu . . . 4

2.2 Anal´yza matice ˇcetnost´ı . . . 5

3 Anal´yza 6 3.1 Povaha dat . . . 6

3.1.1 Rozloˇzen´ı n´avˇstˇevnosti podle URL str´anek . . . 7

3.1.2 Rozloˇzen´ı n´avˇstˇevnosti podle navˇst´ıven´ych str´anek . . . 8

3.2 Pˇredzpracov´an´ı dat . . . 10

3.2.1 Redukce poˇctu URL . . . 10

3.2.2 Redukce poˇctu uˇzivatel˚u . . . 12

3.3 Metodika . . . 14

3.3.1 Algoritmus TF-IDF . . . 14

3.3.2 Algoritmus K-means . . . 15

3.3.3 Algoritmus PCA . . . 16

3.3.4 Algoritmus LSA . . . 17

3.3.5 Algoritmus pLSA . . . 18

3.4 Nevydaˇren´e experimenty . . . 20

3.4.1 Shlukovac´ı algoritmy, PCA, LSA . . . 20

3.4.2 S´eriov´e pLSA . . . 22

4 Fin´aln´ı zpracov´an´ı 24

4.1 Redukce dat . . . 24

4.2 Paraleln´ı pLSA . . . 25

4.2.1 Popis paraleln´ıho algoritmu pLSA . . . 25

4.2.2 Porovn´an´ı rychlosti . . . 31

4.3 Popis nalezen´ych t´emat . . . 34

4.3.1 Open Directory Project - DMOZ . . . 34

4.3.2 Nejv´yznamnˇejˇs´ı slova dle webov´eho obsahu . . . 37

4.4 Fin´aln´ı v´ysledky . . . 41

5 Z´avˇer 43

A Obsah pˇriloˇzen´eho CD 45

Literatura 46

Pouˇzit´e zkratky 50

Seznam tabulek

1.1 Struktura clickstreamu . . . 2

3.1 Velmi ´uzce specializovan´e clustery . . . 21

3.2 Sloˇzitosti serializovan´eho algoritmu pLSA . . . 23

4.1 Porovn´an´ı sloˇzitost´ı implementac´ı algoritmu pLSA . . . 33

4.2 Porovn´an´ı rychlost´ı a sloˇzitost´ı implementac´ı algoritmu pLSA . . . . 33

4.3 Kategorie z DMOZ . . . 36

4.4 Nejv´yznamnˇejˇs´ı slova dle obsah˚u str´anek . . . 39

Seznam obr´ azk˚ u

3.1 Poˇcet uˇzivatel˚u na URL adrese . . . 7 3.2 Poˇcet uˇzivatel˚u na 30 nejvˇetˇs´ıch URL ares´ach . . . 8 3.3 Poˇcet navˇst´ıven´ych str´anek uˇzivateli . . . 9 3.4 Procento odstranˇen´ych str´anek v z´avislosti na procentu oˇrezu . . . . 11 3.5 Poˇcet navˇst´ıven´ych str´anek uˇzivateli po odstranˇen´ı nˇeˇz´adouc´ıch dom´en 13 4.1 Rychlost konvergence pLSA . . . 31 4.2 Zastoupen´ı kategori´ı z DMOZ . . . 37 4.3 Hodnoty entropie napˇr´ıˇc vyhovuj´ıc´ımi t´ematy . . . 40

Seznam zdrojov´ ych k´ od˚ u

3.1 Implementace serializovan´eho pLSA . . . 22

4.1 Inicializace sd´ılen´e pamˇeti v paraleln´ım pLSA . . . 26

4.2 Implementace paraleln´ıho EM algoritmu pLSA . . . 29

4.3 Implementace v´ypoˇctu loglikelihoodu . . . 30

Kapitola 1 Uvod ´

Na internetu je v dneˇsn´ı dobˇe t´emˇeˇr kaˇzd´y. Lid´e vyuˇz´ıvaj´ı internetov´ych sluˇzeb a tyto sluˇzby vyuˇz´ıvaj´ı dat sv´ych uˇzivatel˚u. Internetov´e spoleˇcnosti jsou dnes nuceni analyzovat sv´e uˇzivatele, aby byly schopn´e drˇzet krok s konkurenc´ı. Tato pr´ace ukazuje postupy pˇri anal´yze nasb´ıran´ych dat o uˇzivatel´ıch.

1.1 Motivace

Nˇekter´e softwarov´e spoleˇcnosti sb´ıraj´ı data od sv´ych uˇzivatel˚u. V pˇr´ıpadˇe webov´ych produkt˚u se nejˇcastˇeji pouˇz´ıv´a clickstream¹. N´azorn´ym pˇr´ıkladem m˚uˇze b´yt antivirov´a spoleˇcnost, kter´a pro zefektivnˇen´ı sv´ych antivirov´ych produkt˚u sb´ır´a z´aznamy z proch´azen´ı internetu od nˇekter´ych sv´ych uˇzivatel˚u. Jedna takov´a spoleˇcnost² poskytla data pro tuto pr´aci. Sbˇer dat je prov´adˇen pˇri zad´an´ı URL³ adresy do prohl´ıˇzeˇce uˇzivatelem. Pˇredt´ım neˇz uˇzivatel dostane obsah str´anky, tak antivirus danou webovou str´anku provˇeˇr´ı na v´yskyt ˇskodliv´eho k´odu a v negativn´ım pˇr´ıpadˇe uˇzivateli str´anku povol´ı naˇc´ıst. Pokud na chtˇen´e str´ance bude objeven virus ˇ

ci jin´y neˇz´adouc´ı k´od, tak je uˇzivatel varov´an a pˇr´ıstup na str´anku mu je rozmlouv´an, popˇr´ıpadˇe zam´ıtnut. Tato a j´ı podobn´e spoleˇcnosti takto mohou sb´ırat velk´e mnoˇzstv´ı dat, kter´a z povahy clickstreamu mohou nar˚ustat do enormn´ıch velikost´ı (stovek GB

1.2 Definice probl´ emu

1.2.1 Data

Vzhledem k tomu, ˇze clickstream spad´a do kategorie velmi citliv´ych dat, tak je nutn´e data anonymizovat. Jedn´a se o proces, kde se urˇcit´ym zp˚usobem skryje ˇci odstran´ı ta ˇc´ast dat, kter´a je citliv´a.

Struktura clickstreamu b´yv´a pˇribliˇznˇe n´asleduj´ıc´ı⁴: Tabulka 1.1: Struktura clickstreamu

ID poˇc´ıtaˇce ˇcas UTC HTTP referrer URL IP adresa Nejd˚uleˇzitˇejˇs´ımi parametry clickstreamu jsou ID poˇc´ıtaˇce (prozat´ım br´ano jako ID uˇzivatele⁵) a URL adresa na kterou smˇeˇroval.

V t´eto pr´aci je popisov´ano zpracov´an´ı jiˇz zanonymizovan´ych dat, kter´a jsou po- psateln´a vektorem webov´ych adres⁶ a matic´ı ˇcetnost´ı⁷ obsahuj´ıc´ı na sv´ych sloupc´ıch 586 624 URL a na ˇr´adc´ıch jsou n´ahodnˇe seˇrazen´ı uˇzivatel´e (resp. ID poˇc´ıtaˇce), kter´ych je 224 679. Kaˇzd´y uˇzivatel (resp. ID poˇc´ıtaˇce) je zastoupen pouze jednou. Jedn´a se pˇritom pouze o populaci ˇzij´ıc´ı v USA, kde data byla nasb´ır´ana za obdob´ı jednoho mˇes´ıce.

1.2.2 Probl´ em

Hlavn´ı ideou t´eto pr´ace je kategorizace uˇzivatel˚u na z´akladˇe jejich proch´azen´ı internetu. C´ılem je popsat metody vedouc´ı k nalezen´ı skupin webov´ych str´anek, kter´e jsou pro urˇcitou skupinu populace charakteristick´e. Tedy se jedn´a o nalezen´ı takov´ych skupin str´anek, na kter´e chod´ı

”podobn´ı“ uˇzivatel´e. Tato informace ale nen´ı z kontextu dat pˇr´ımo jasn´a, a proto je potˇrebn´e data analyzovat.

4Konkr´etn´ı clickstream m˚uˇze obsahovat nˇekolik dalˇs´ıch ´udaj˚u jako jsou st´at, mˇesto atp. Tyto a dalˇs´ı parametry nejsou z´ısk´av´any pˇr´ımo od uˇzivatele, ale na z´akladˇe heuristik postaven´ych na ˇ

cist´em clickstreamu.

5Na jednom poˇc´ıtaˇci, kter´y je monitorov´an, m˚uˇze pracovat v´ıce ˇclen˚u dom´acnosti. Z d˚uvodu zjednoduˇsen´ı probl´emu je uvaˇzov´ano o z´aznamech z jednoho poˇc´ıtaˇce tak, ˇze jsou generov´any pouze jedn´ım uˇzivatelem.

6Byly zvoleny pouze dom´eny 2. ˇr´adu. Pˇr´ıklademfacebook.com,google.com...

7V buˇnk´ach matice jsou poˇcty n´avˇstˇev konkr´etn´ıho uˇzivatele na konkr´etn´ı URL adrese.

1.3 Struktura pr´ ace

Prvn´ı kapitola Popis probl´emu a struktury dat.

Druh´a kapitola Pr´ace pojedn´av´a o ˇreˇsen´ı podobn´eho probl´emu jin´ymi.

Tˇret´ı kapitola Zde je pops´ana povaha dat a r˚uzn´e metody (algoritmy) vhodn´e pro ˇreˇsen´ı. Ke konci kapitoly jsou pops´any postupy, kter´e nevedly k uspokojiv´ym v´ysledk˚um.

Ctvrt´ˇ a kapitola Pojedn´an´ı o fin´aln´ım zpracov´an´ı dat. Popsan´e konkr´etn´ı postupy, v´ypoˇcty a z´ıskan´e v´ysledky.

P´ata kapitola Shrnut z´avˇer v´yzkumu, dosaˇzen´e v´ysledky a pops´ana cesta pro zdo- konalen´ı v´ysledk˚u.

Kapitola 2

Souvisej´ıc´ı pr´ ace

Anal´yzou clickstreamu se v dneˇsn´ı dobˇe zab´yv´a mnoho spoleˇcnost´ı. Nˇekter´e pro vylepˇsen´ı sv´eho marketingu, jin´e proto, aby byly l´epe konkurenceschopn´e, ale t´emˇeˇr vˇsechny to dˇelaj´ı za prim´arn´ım c´ılem: zjistit o z´akazn´ıkovi vˇse d˚uleˇzit´e a n´aslednˇe tyto znalosti zmonetizovat. V t´eto kapitole jsou zm´ınˇeny r˚uzn´e pˇr´ıstupy vych´azej´ıc´ı z anal´yzy clickstreamu, kter´e v´ıce ˇci m´enˇe byly pˇr´ınosn´e pro anal´yzu v t´eto pr´aci.

2.1 Anal´ yza clickstreamu

Anal´yza clickstreamu je v dneˇsn´ı dobˇe pomˇernˇe ˇcast´ym jevem, ale prim´arnˇe je tvoˇrena spoleˇcnostmi, kter´e analyzuj´ı sv´e uˇzivatele (napˇr. e-shop) a dle jejich chov´an´ı usmˇerˇnuj´ı sv´e dalˇs´ı kroky v marketingu. Takov´e anal´yzy vznikaj´ı d´ıky zaznamenan´e cestˇe (sled webov´ych adres - clickstream) uˇzivatelem. Tyto cesty jsou tvoˇreny pouze na str´ank´ach vlastnˇen´ych nˇejakou spoleˇcnost´ı (napˇr. e-shop). D´ıky anal´yze sled˚u sv´ych uˇzivatel˚u lze urˇcit napˇr´ıklad pohlav´ı sv´ych z´akazn´ık˚u jak je tomu ps´ano v [15].

Kaˇzd´y uˇzivatel m´a jin´e chov´an´ı, ale lze naj´ıt jist´e charakteristick´e rysy v proch´azen´ı zm´ınˇen´eho e-shopu typick´e pro muˇze a pro ˇzeny.Path analysis, neboli anal´yza sled˚u, d´avaj´ı v´yznamnou informaci napˇr´ıklad o tom, jestli z´akazn´ık provede n´akup ˇci nikoli.

D´ıky statistick´ym metod´am lze vypozorovat, jak´e sledy ud´alost´ı (navˇst´ıven´ı ˇc´ast´ı webu) vedou k ´uspˇeˇsn´emu n´akupu napˇr.: {Domovsk´a str´anka → Kategorie produkt˚u

→ Kategorie produktu → N´akupn´ı koˇs´ık}. Naopak pokud sled vypad´a: {Domovsk´a str´anka → Informace o webu→ Domovsk´a str´anka → Informace o webu → Katego- rie produktu. . .}, tak je velk´a pravdˇepodobnost, ˇze z´akazn´ık s takov´ym clickstreamem n´akup produktu neuskuteˇcn´ı, nebo alespoˇn ne ihned. Zm´ınˇen´a pr´ace se zab´yv´a t´ım, jak predikovat n´akup a kde jsou ta d˚uleˇzit´a m´ısta v clickstreamu, kter´a rozhoduj´ı o tom, jestli z´akazn´ık nakoup´ı ˇci nikoli. Detailnˇejˇs´ı pops´an´ı clickstreamu je v pr´aci [23].

Bohuˇzel naˇse situace je ponˇekud odliˇsn´a, a to t´ım, ˇze data z clickstreamu nejsou pro jeden e-shop, ale pro vˇetˇs´ı ˇc´ast cel´eho internetu. Dalˇs´ı negativum je v tom, ˇze n´am nebyl poskytnut

”surov´y“ clickstream, ale jiˇz data transformov´ana do matice ˇcetnost´ı.

Na tomto z´akladˇe je nutn´e uvaˇzovat nad probl´emem z jin´ych ´uhl˚u.

2.2 Anal´ yza matice ˇ cetnost´ı

Vzhledem k tomu, ˇze m´ame k dispozici matici ˇcetnost´ı, jak jiˇz bylo naznaˇceno v ˇc´asti 1.2.1, tak je nutn´e hledat zpracov´an´ı pr´avˇe t´eto matice a nikoli ˇcist´eho clickstreamu, pˇrestoˇze matice ˇcetnost´ı vych´az´ı pr´avˇe z clickstreamu. Pr´ace [24] se zab´yv´a anal´yzou matice ˇcetnost´ı z pohledu s´emantick´ych vektor˚u. Vektorov´y prostor je zde obhajov´an pro jeho snazˇs´ı a rychlejˇs´ı zpracov´an´ı. Naˇceˇz pr´ace [11] navazuje vysvˇetlen´ım efektivn´ıho shlukovac´ıho algoritmu K-means. Shlukovac´ı algoritmy jsou pro kategorizaci velmi vhodn´e. V pr´aci [12] je zm´ınˇeno zpracov´an´ı TF–IDF algoritmu, vysvˇetleny d˚uleˇzitosti normalizace vektor˚u a benefity kosinov´e podobnosti. Z v´yˇse zm´ınˇen´ych prac´ı a mnoh´ych dalˇs´ıch je v tomto v´yzkumu vych´azeno. Vzhledem k tomu, ˇze ´uplnˇe stejn´ym t´ematem se nezab´yv´a ˇz´adn´a pr´ace, tak je nutn´e s pomoc´ı d´ılˇc´ıch znalost´ı zkonstruovat postup, kter´y je v t´eto pr´aci pops´an.

Kapitola 3 Anal´ yza

V t´eto kapitole je pops´ana povaha dat, kter´a jsou n´aslednˇe pomoc´ı nˇekolika algo- ritm˚u zanalyzov´ana. Data bylo nutn´e pˇredzpracovat, aby vynikly diskriminuj´ıc´ı in- formace. Jsou zde pops´any nˇekter´e z nejv´yznamnˇejˇs´ıch algoritm˚u, kter´e jsou vhodn´e pro zpracov´an´ı dat podobn´eho charakteru.

3.1 Povaha dat

Jak jiˇz bylo zm´ınˇeno v ´uvodu 1.2.1, tak v´yzkum prob´ıh´a nad matic´ı ˇcetnost´ı s rozmˇery 586 624 URL ×224 679 uˇzivatel˚u. Matice je uloˇzena v CSR¹ form´atu a vy- pad´a n´asledovnˇe:













w₁ w₂ . . . w_{586 624} u₁ a_1,1 a_1,2 . . . a_{1,586 624} u₂ a_2,1 a_2,2 . . . a_{2,586 624}

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

u_{224 679} a_{224 679,1} a_{224 679,2} . . . a224 679,586 624













kde w jsou webov´e str´anky (konkr´etnˇe pouze dom´eny 2. ˇr´adu), u jsou uˇzivatel´e a a znaˇc´ı poˇcet navˇst´ıven´ı konkr´etn´ı dom´eny uˇzivatelem.

Aby se zjistilo, jakou maj´ı data povahu, myˇsleno jejich rozdˇelen´ı, rozloˇzen´ı a dalˇs´ı charakteristiky, je vhodn´e prov´est nˇekolik popisn´ych n´ahled˚u na data. Pro lepˇs´ı ori- entaci ve v´ysledc´ıch je vyuˇzito grafick´eho zn´azornˇen´ı.

1Compressed Storrage Row. Standardn´ı form´at pro ukl´ad´an´ı ˇr´ıdk´ych matic. Jsou uloˇzeny pouze nenulov´e hodnoty.

3.1.1 Rozloˇ zen´ı n´ avˇ stˇ evnosti podle URL str´ anek

V prvn´ım kroku je na data nahl´ednuto z pohledu n´avˇstˇevnosti URL str´anek. Tedy kolik jedineˇcn´ych uˇzivatel˚u chod´ı na konkr´etn´ı URL adresu. U kaˇzd´eho uˇzivatele je zapoˇc´ıt´ana nenulov´a n´avˇstˇeva jen jednou. Hodnoty na ose Y jsou vytvoˇreny tak, ˇze se seˇcetly sloupeˇcky matice², kter´e byly pot´e znormalizov´any v˚uˇci celkov´emu poˇctu uˇzivatel˚u.

Obr´azek 3.1: Poˇcet uˇzivatel˚u na URL adrese

Hodnoty v grafu v´yˇse (viz obr´azek 3.1) ukazuj´ı, ˇze existuje velmi m´alo adres, kter´e maj´ı v´yznamnˇejˇs´ı n´avˇstˇevnost. Proto v n´asleduj´ıc´ım grafu (viz obr´azek 3.2) je uk´azka prvn´ıch 30 nejvˇetˇs´ıch adres. Jednotliv´e procentu´aln´ı n´avˇstˇevnosti jsou seˇrazeny se- stupnˇe.

facebook.com youtube.com

yahoo.com amazon.com

wikipedia.org blogspot.com

ebay.com twitter.com huffingtonpost.com

answers.com craigslist.org

msn.comgo.com about.com

pinterest.comlive.com mozilla.org

walmart.com wordpress.combit.ly

paypal.com avast.com

imdb.com buzzfeed.com

apple.com tumblr.com

netflix.com googleadservices.com

linkedin.com adobe.com

URL 0.00%

20.00%

40.00%

60.00%

80.00%

100.00%

Procento uživatelů

Obr´azek 3.2: Poˇcet uˇzivatel˚u na 30 nejvˇetˇs´ıch URL ares´ach

Dominuj´ıc´ı adresou je facebook.com. Z letm´eho pohledu lze rozpoznat dalˇs´ı ˇcasto navˇstˇevovan´e weby, kter´e jsou vˇseobecnˇe zn´am´e. Bohuˇzel tyto

”velk´e“ webov´e str´anky, na kter´e chod´ı t´emˇeˇr vˇsichni uˇzivatel´e jsou pro diskriminaci zcela nepouˇziteln´e. Na tyto str´anky chod´ı v´yznamn´a vˇetˇsina uˇzivatel˚u, a tedy v´yznamnost tˇechto dom´en je t´ımto razantnˇe pon´ıˇzena. Podobnˇe je to i s tˇemi webov´ymi str´ankami, na kter´e chod´ı velmi m´alo uˇzivatel˚u.

3.1.2 Rozloˇ zen´ı n´ avˇ stˇ evnosti podle navˇ st´ıven´ ych str´ anek

V druh´em kroku je vhodn´e diskutovat n´ahled na data z pohledu uˇzivatele. Nej- vhodnˇejˇs´ı metrikou se zde jev´ı mˇeˇren´ı rozsahu navˇst´ıven´ych str´anek pro jednotliv´e skupiny uˇzivatel˚u. Matice je nyn´ı seˇctena po ˇr´adc´ıch³, ˇc´ımˇz vznikl vektor zn´azorˇnuj´ıc´ı poˇcet r˚uzn´ych navˇst´ıven´ych dom´en pro kaˇzd´eho uˇzivatele. Protoˇze je ale uˇzivatel˚u hodnˇe a ˇz´adn´y z nich nenese v´yznamnˇejˇs´ı popisnou informaci⁴, je zde vhodn´e tyto hodnoty z vektoru shrom´aˇzdit pomoc´ı histogramu, kde l´epe vyniknou jednotliv´e sku- piny obyvatel.

3Kaˇzd´a nenulov´a hodnota byla nahrazena ˇc´ıslem 1.

4Uˇzivatel´e byli anonymizov´ani.

14 - 52 91 - 129 168 - 206 244 - 283 321 - 360 rozsahy navštívených stránek

0%

5%

10%

15%

20%

25%

30%

35%

procento uživatelů

Obr´azek 3.3: Poˇcet navˇst´ıven´ych str´anek uˇzivateli

V grafu v´yˇse (viz obr´azek 3.3) jsou jednotliv´e poˇcty navˇst´ıven´ych str´anek uˇzivateli slouˇceny do 10 tˇr´ıd. Prvn´ı a nejpoˇcetnˇejˇs´ı tˇr´ıda reprezentuje tu skupinu uˇzivatel˚u, ve kter´e kaˇzd´y uˇzivatel chod´ı na 14 aˇz 52 unik´atn´ıch webov´ych str´anek (dom´en). Tˇechto uˇzivatel˚u je pˇribliˇznˇe 34,5 %. V posledn´ı tˇr´ıdˇe je 0,32 % uˇzivatel˚u, kteˇr´ı chod´ı na 360 aˇz 398 str´anek⁵. 10 tˇr´ıd bylo vybr´ano pouze jako n´azorn´a uk´azka, protoˇze pˇri vˇetˇs´ım poˇctu tˇr´ıd nen´ı dostateˇcnˇe ˇciteln´a informace o poˇctu navˇst´ıven´ych str´anek. Tendence (trend) grafu t´ımto nen´ı pozmˇenˇena.

3.2 Pˇ redzpracov´ an´ı dat

Vzhledem k tomu, ˇze povaha dat nen´ı ide´aln´ı, je nutn´e data jist´ym zp˚usobem upravit, aby dalˇs´ı v´ysledky mˇely relevantnˇejˇs´ı charakter.

3.2.1 Redukce poˇ ctu URL

Redukc´ı poˇctu, neboli oˇrez´an´ım URL je myˇsleno to, ˇze z cel´eho seznamu dom´en budou odstranˇeny ty adresy, kter´e nevyhov´ı n´asleduj´ıc´ım poˇzadavk˚um. Ve sv´e pod- statˇe budou vymaz´any konkr´etn´ı dom´eny i pˇr´ısluˇsn´e slupce v matici ˇcetnost´ı. ´Ukol oˇrez´an´ı dom´en je z d˚uvodu pˇrehlednosti rozdˇelen na dva po sobˇe jdouc´ı kroky.

Prvotn´ı redukce

Pˇri pohledu na obr´azek 3.1 a seˇrazen´ı hodnot sestupnˇe zjist´ıme, ˇze poˇcet menˇs´ıch hodnot je v´yraznˇe vˇetˇs´ı neˇz poˇcet vˇetˇs´ıch hodnot. Tato skuteˇcnost n´as mus´ı v´est k zamyˇslen´ı, jak´e ˇze webov´e str´anky jsou dostateˇcnˇe popisn´e pro dalˇs´ı anal´yzu.

Jiˇz bylo zm´ınˇeno v odstavci 3.1.1, ˇze dominantn´ı adresy⁶ a m´alo v´yznamn´e ad- resy⁷ jsou pro dalˇs´ı zpracov´an´ı sp´ıˇse nevyhovuj´ıc´ı. Na tomto z´akladˇe je na m´ıstˇe tato neˇz´adouc´ı data spoleˇcnˇe s adresami odstranit. Motivace k tomuto by mˇela b´yt takov´a, ˇ

ze zanedb´an´ım nediskriminuj´ıc´ıch adres z´ısk´ame odfiltrovan´e v´ıce diskriminuj´ıc´ı ad- resy.

Po prozkoum´an´ı v´ypisu dom´en (seˇrazen´ych sestupnˇe dle n´avˇstˇevnosti) jsme dospˇeli k z´avˇeru, ˇze u hranice 10 % n´avˇstˇevnosti (odpov´ıd´a pˇribliˇznˇe 22 000 uˇzivatel˚u navˇstˇevuj´ıc´ıch konkr´etn´ı dom´enu) m˚uˇze b´yt pomysln´a oddˇeluj´ıc´ı linie pro obecn´e a z´ajmovˇe uˇzˇs´ı webov´e str´anky. Mezi dom´eny obecnˇejˇs´ıho charakteru m˚uˇzeme zaˇradit facebook.com, youtube.com ˇci amazon.com. Z´ajmovˇe uˇzˇs´ı dom´enou m˚uˇzeme nazvat weby podobn´eindeed.com⁸ ˇci foodnetwork.com⁹. Tedy webov´e str´anky, kde n´avˇstˇeva takov´eho webu o uˇzivateli uˇz nˇeco vypov´ıd´a.

Na druh´e stranˇe lze mluvit o tˇech webov´ych str´ank´ach, na kter´e chod´ı naopak velmi mal´y poˇcet uˇzivatel˚u. Tyto webov´e str´anky jsou pˇrev´aˇznˇe soukrom´eho cha- rakteru (pˇr. lok´aln´ı firma). V dan´em mˇeˇr´ıtku pˇribliˇznˇe p˚ul milionu r˚uzn´ych dom´en jsou tyto mal´e weby v´ıcem´enˇe nev´yznamn´e. Rozhodli jsme se, ˇze webov´a str´anka

6Adresy na kter´e chod´ı vˇetˇs´ı poˇcet uˇzivatel˚u.

7V´yznamn´e z hlediska poˇctu n´avˇstˇevn´ık˚u.

8Port´al s nab´ıdkami pr´ace.

9Port´al s recepty na vaˇren´ı.

v´yznamnˇejˇs´ıho charakteru (lze se z n´ı dozvˇedˇet nˇejak´a podstatn´a informace) m˚uˇze zaˇc´ınat na 10 r˚uzn´ych n´avˇstˇevn´ıch.

Na z´akladˇe tˇechto ´uvah jsme odstranili (neboli nepouˇzili v dalˇs´ıch v´ypoˇctech) ty webov´e str´anky, kter´e jsou navˇstˇevov´any vˇetˇs´ım neˇz 10% mnoˇzstv´ım populace a tak´e ty dom´eny, na kter´e chod´ı m´enˇe neˇz 10 lid´ı. Z celkov´eho poˇctu 586 624 webov´ych adres z˚ustalo po t´eto redukci pouze 102 453.

Redukce pro z´ısk´an´ı vˇetˇs´ı vypov´ıdaj´ıc´ı hodnoty

V pˇredchoz´ım kroku jsme pomˇernˇe hrubˇs´ım s´ıtem odstranili nˇekolik zjevnˇe nedis- kriminuj´ıc´ıch dom´en. V tomto kroku se ale zamˇeˇr´ıme na ponech´an´ı pouze tˇech dom´en, kter´e z hlediska pohledu na celkovou populaci mohou m´ıt v´yznamnˇejˇs´ı charakter.

Tento charakter lze urˇcit napˇr´ıklad podle toho, jak moc je dan´a dom´ena v´yznamn´a v r´amci poˇctu n´avˇstˇev pro jednoho uˇzivatele. Existuj´ı dom´eny webov´ych str´anek, na kter´e uˇzivatel chod´ı opakovanˇe a tyto webov´e str´anky mohou tvoˇrit jistou v´yznamnost v r´amci obl´ıbenosti webu. Hranici mezi v´yznamn´ymi a m´enˇe v´yznamn´ymi dom´enami pro jednoho uˇzivatele jsme urˇcili na 10 %. Tedy ty adresy, kter´e tvoˇr´ı alespoˇn 10 % ze vˇsech navˇst´ıven´ych web˚u dan´ym uˇzivatelem jsou pro nˇej pravdˇepodobnˇe v´yznamn´e.

Ostatn´ı adresy jsme v dalˇs´ıch v´ypoˇctech zanedbali. Z˚ustaly tedy pouze ty dom´eny, kter´e tvoˇr´ı alespoˇn 10 % ze vˇsech n´avˇstˇev pro alespoˇn jednoho uˇzivatele.

40%

60%

80%

100%

procento odříznutých URL

V grafu na pˇredchoz´ı str´ance (viz obr´azek 3.4) je uk´az´ano, kolik procent webov´ych str´anek bude odstranˇeno (osa Y) v z´avislosti na procentu oˇrezu v´yznamn´ych ˇci nev´yznamn´ych adres pro alespoˇn jednoho uˇzivatele (osa X). V grafu je t´eˇz uk´az´ana i pˇreruˇsovan´a linie zn´azorˇnuj´ıc´ı v´yˇse zm´ınˇen´y oˇrez na 10 %. Je patrn´e, ˇze t´ımto oˇrezem bude odstranˇeno velik´e mnoˇzstv´ı dom´en. Na druhou stranu z˚ustanou pouze ty dom´eny, kter´e jsou v´yraznˇe v´yznamnˇejˇs´ı pro mˇeˇrenou populaci. Po odstranˇen´ı tˇechto m´enˇe v´yznamn´ych adres z˚ustane 37 441 z p˚uvodn´ıch 102 453 adres.

3.2.2 Redukce poˇ ctu uˇ zivatel˚ u

Podobnˇe jako jsme redukovali URL, nyn´ı pˇristoup´ıme k redukci uˇzivatel˚u. Moti- vac´ı je to, ˇze v dan´e populaci existuj´ı uˇzivatel´e, kteˇr´ı chod´ı na velmi velk´e mnoˇzstv´ı r˚uzn´ych dom´en. R˚uznorodost z´ajm˚u tˇechto uˇzivatel˚u je pomˇernˇe velik´a. Tak´e existuj´ı uˇzivatel´e, kteˇr´ı naopak chod´ı na velmi mal´e mnoˇzstv´ı dom´en. Obˇe tyto skupiny by mohly negativnˇe ovlivnit dalˇs´ı zpracov´an´ı.

V r´amci zachov´an´ı z´ajmu o nalezen´ı obecn´ych kategori´ı jsme nuceni pˇristoupit i k redukci uˇzivatel˚u. M´alo r˚uznorod´ı uˇzivatel´e nemaj´ı takovou vypov´ıdaj´ıc´ı hodnotu, nebot’ jejich z´ajmy na internetu jsou tvoˇreny pouze mal´ymi shluky. Naopak uˇzivatel´e s pˇr´ıliˇs ˇsirok´ymi z´ajmy by bylo pozdˇeji obt´ıˇzn´e zakategorizovat. Z tˇechto d˚uvod˚u budou odstranˇeny tyto dvˇe skupiny uˇzivatel˚u.

Vych´az´ıme z prvn´ı ˇc´asti pˇredeˇsl´e sekce (viz 3.2.1). Jednotliv´e dom´eny byly redu- kov´any dle poˇctu n´avˇstˇevn´ık˚u na hranici 10 % ze strany velk´ych dom´en a na hranici 10 uˇzivatel˚u ze strany dom´en s niˇzˇs´ımi poˇcty n´avˇstˇevn´ık˚u. Je vhodn´e zakomponovat redukci uˇzivatel˚u ihned po tomto odstranˇen´ı dom´en. D˚uvod je n´asleduj´ıc´ı. Pˇri redukci dom´en se zmˇen´ı poˇcty unik´atn´ıch navˇst´ıven´ych dom´en uˇzivateli (viz obr´azek 3.3, kter´y zobrazuje rozloˇzen´ı navˇst´ıven´ych str´anek bez jak´ehokoliv odstranˇen´ı). Po aplikov´an´ı oˇrezu poˇctu dom´en se poˇcty navˇst´ıven´ych str´anek zmˇen´ı n´asledovnˇe (viz obr´azek 3.5 na dalˇs´ı str´ance). V grafu se zmˇenily hlavnˇe rozsahy navˇst´ıven´ych str´anek. D˚uleˇzit´e rozsahy jsou u prvn´ı a ˇctvrt´e tˇr´ıdy.

Po prozkoum´an´ı tohoto grafu jsme dospˇeli k z´avˇeru, ˇze relevantnˇejˇs´ı informace dostaneme tehdy, kdyˇz odstran´ıme ty uˇzivatele, kteˇr´ı chod´ı na m´enˇe neˇz 10 a v´ıce neˇz 150 r˚uzn´ych dom´en. Tedy z p˚uvodn´ıho poˇctu 224 679 uˇzivatel˚u jsme dostali 191 676 uˇzivatel˚u, kteˇr´ı nemaj´ı tolik extr´emn´ı chov´an´ı. Spodn´ı (lev´y) a horn´ı (prav´y) pr´ah jsou na obr´azku vykresleny pˇreruˇsovanou ˇc´arou. Uˇzivatel´e spadaj´ıc´ı do tˇechto mez´ı byli zachov´ani.

2 - 38 74 - 110 146 - 182 219 - 255 291 - 327 rozsahy navštívených stránek

0%

5%

10%

15%

20%

25%

30%

35%

procento uživatelů

Obr´azek 3.5: Poˇcet navˇst´ıven´ych str´anek uˇzivateli po odstranˇen´ı nˇeˇz´adouc´ıch dom´en

Po redukci uˇzivatel˚u n´asledovala dalˇs´ı redukce dom´en na 10 % (viz druh´a ˇc´ast pˇredeˇsl´e sekce 3.2.1).

Z p˚uvodn´ıho rozmˇeru matice (224 679 uˇzivatel˚u × 586 624 URL) jsme z´ıskali po celkov´em oˇrez´an´ı matici velikosti 191 676 uˇzivatel˚u × 37 441 URL, coˇz je ´uspora pˇribliˇznˇe 94,6 % bunˇek pˇri zachov´an´ı (ba zlepˇsen´ı) charakteru dat. Pro upˇresnˇen´ı je vhodn´e dodat, ˇze jsme t´ımto uˇsetˇrili pˇribliˇznˇe 57,7 % dat na disku. Vzhledem k tomu, ˇze je matice st´ale velmi ˇr´ıdk´a (pˇribliˇznˇe 99,875 % nulov´ych bunˇek), je pro dalˇs´ı v´ypoˇcty zachov´an form´at CSR.

3.3 Metodika

V t´eto ˇc´asti jsou pops´any nejbˇeˇznˇejˇs´ı algoritmy a postupy pro zpracov´an´ı dat povahy matice ˇcetnost´ı. Vˇsechny zde zm´ınˇen´e algoritmy jsme na datech vyzkouˇseli, ale nˇekter´e nevedly k poˇzadovan´ym v´ysledk˚um.

Vzhledem k nejasn´e cestˇe k c´ıli jsme se rozhodli, ˇze nejvhodnˇejˇs´ım n´astrojem pro zpracov´an´ı bude programovac´ı jazyk Python doplnˇen´y o statistick´e a v´ypoˇcetn´ı knihovny v ˇcele sscikit-learn [17] a SciPy [10]. Tyto knihovny jsou velmi jednoduch´e k pouˇzit´ı, obsahuj´ı optimalizovan´e algoritmy a maj´ı velmi podrobnou dokumentaci.

Spolu s velmi jednoduchou syntax´ı Pythonu je zde vytvoˇreno prostˇred´ı prosp´ıvaj´ıc´ı relativnˇe rychl´emu v´yvoji a testov´an´ı vˇetˇs´ıho poˇctu experiment˚u. Mezi nev´yhody tohoto ˇreˇsen´ı jistˇe patˇr´ı rychlost Pythonu. Jedn´a se o interpretovan´y jazyk, kter´y je vhodn´y hlavnˇe k zaznamen´an´ı myˇslenek a algoritm˚u.

Vˇetˇsina v´ypoˇct˚u byla prov´adˇena v MetaCentru¹⁰ hlavnˇe vzhledem k vˇetˇs´ımu ob- jemu dat.

3.3.1 Algoritmus TF-IDF

TF-IDF¹¹ (zkratka pro anglick´a slova maj´ıc´ı v´yznam ˇcetnosti slova v dokumentu a pˇrevr´acen´e ˇcetnosti slova ve vˇsech dokumentech) je numerick´a statistika zohledˇnuj´ıc´ı d˚uleˇzitost slov v dan´em korpusu¹² [16]. V naˇsem pˇr´ıpadˇe je korpus tvoˇren matic´ı ˇ

cetnost´ı. Dokumentem je zde nazv´an uˇzivatel (ˇr´adek matice) a slovem je zde zastou- pena konkr´etn´ı URL dom´ena (sloupec matice).

Vysvˇetlen´ı pojm˚u:

tf_i,j = n_i,j P

kn_k,j (3.1)

kden_i,j je poˇcet v´yskyt˚u slovat_i (webu) v dokumentud_j (pro uˇzivatele). Kaˇzd´y poˇcet v´yskyt˚u je vydˇelen souˇctem vˇsech v´yskyt˚u slov v cel´em dokumentu d_j.

idf_i = log |D|

|{j :t_i ∈d_j}| (3.2)

10Jedn´a se o sdruˇzen´ı superpoˇc´ıtaˇc˚u rozm´ıstˇen´ych po cel´e ˇCesk´e rebublice. Lze si zde na omezenou dobu zarezervovat velik´e mnoˇzstv´ı v´ypoˇcetn´ıch prostˇredk˚u.

11Term Frequency - Inverse Document Frequency.

12Rozs´ahl´y soubor text˚u (dokument˚u).

kde |D| je poˇcet dokument˚u (uˇzivatel˚u) a |{j : t_i ∈ d_j}| je poˇcet dokument˚u obsa- huj´ıc´ıch slovot_i [16]. Pot´e se fin´aln´ı hodnota spoˇc´ıt´a n´asledovnˇe:

tf idf_i,j =tf_i,j·idf_i (3.3) V´ysledkem je matice stejn´e velikosti jako p˚uvodn´ı matice ˇcetnost´ı. Tato matice reprezentuje v´yznamnost kaˇzd´eho slova v dokumentu napˇr´ıˇc vˇsemi dokumenty. Tedy pro kaˇzd´e slovo v kaˇzd´em dokumentu existuje ˇc´ıseln´a hodnota, kter´a pro vˇetˇs´ı ˇc´ısla znaˇc´ı vˇetˇs´ı d˚uleˇzitost dan´eho slova v dokumentu a pro menˇs´ı ˇc´ısla d˚uleˇzitost menˇs´ı.

Po seˇrazen´ı tohoto vektoru (ˇr´adektf idf matice) z´ısk´ame mapov´an´ım slova, kter´a jsou pro dan´y dokument v´yznamn´a, neboli diskriminuj´ıc´ı.

3.3.2 Algoritmus K-means

K-means¹³ je clusterovac´ı (shlukovac´ı) algoritmus vytv´aˇrej´ıc´ık disjunktn´ıch clus- ter˚u (shluk˚u). Iterativnˇe minimalizuje odchylky centroid˚u (stˇred˚u) od bod˚u v dan´em shluku. Algoritmus n´ahodnˇe¹⁴ um´ıst´ı pˇredem zvolen´e k bod˚u (centroid˚u) do dan´eho prostoru a pˇriˇrad´ı nejbliˇzˇs´ı body z okol´ı k dan´emu centroidu v z´avislosti na zvolen´e metrice. V dalˇs´ıch iterac´ıch um´ıst´ı kaˇzd´y centroid do stˇredu (pr˚umˇeru) dan´eho clus- teru a tento postup opakuje do t´e doby, dokud se mˇen´ı rozloˇzen´ı bod˚u napˇr´ıˇc clustery.

C´ılem je dos´ahnout co nejmenˇs´ıch rozd´ıl˚u centroidu od bod˚u uvnitˇr cluster˚u [28].

Pˇredpoklady

Seznam bod˚ux={x₁, . . . , x_n} ∈R^m, ˇc´ıslo k ∈N;k ≤n

a S={S₁, . . . , S_k}jakoˇzto seznam cluster˚u.

Hled´a se lok´aln´ı optimum n´asledovnˇe:

argmin

S k

XX

kx−µ_ik² (3.4)

M´ısto metriky lze i pouˇz´ıt tzv. kosinovou podobnost urˇcuj´ıc´ı sv´ıraj´ıc´ı ´uhel mezi dvˇema vektory (body od poˇc´atku).

similarity= cos(θ) = A·B kAkkBk =

Pm

i=1A_i ×B_i pPm

i=1(Ai)²×pPm

i=1(Bi)² (3.5) kde A, B ∈R^m jsou dva body v prostoru [27].

Po nalezen´ı lok´aln´ıho optima algoritmus konˇc´ı s t´ım, ˇze je p˚uvodn´ı prostor bod˚u rozdˇelen do k cluster˚u. Vzd´alenost centroidu ke vˇsem bod˚um v dan´em clusteru je nejmenˇs´ı moˇzn´a pro dan´y poˇcet k. Vzhledem k tomu, ˇze je nalezeno pouze lok´aln´ı optimum urˇceno poˇc´ateˇcn´ım rozdˇelen´ım, je vhodn´e algoritmus spustit v´ıcekr´at s jin´ym poˇc´ateˇcn´ım rozdˇelen´ım a br´at v ´uvahu pouze ten v´ysledek, kter´y mˇel nejmenˇs´ı souˇcet vˇsech kvadr´at˚u vzd´alenost´ı. T´ımto opakov´an´ım lze naj´ıt takov´e lok´aln´ı optimum, kter´e je nejlepˇs´ı moˇzn´e pro dan´y poˇcet opakov´an´ı (vhodn´e jsou des´ıtky aˇz stovky).

3.3.3 Algoritmus PCA

PCA¹⁵, neboli anal´yza hlavn´ıch komponent, je statistick´a procedura pouˇz´ıvaj´ıc´ı ortogon´aln´ı transformaci k dekorelaci dat. Pouˇz´ıv´a se ke sn´ıˇzen´ı dimenze dat s co nejmenˇs´ı ztr´atou informace [31].

PCA je matematicky definov´ano jako ortogon´aln´ı line´arn´ı transformace, kter´a transformuje data do nov´eho souˇradnicov´eho syst´emu [31]. Hlavn´ı komponenty (prin- cipal components) d´avaj´ı nekorelovan´e faktory, kter´e jsou uspoˇr´ad´any sestupnˇe dle rozptylu (variance) [32]. Nejvˇetˇs´ı komponenta leˇz´ı na prvn´ı ose nov´eho souˇradnicov´eho syst´emu, druh´a komponenta na druh´e atd. [31]. K z´ısk´an´ı redukovan´ych dat se pouˇz´ıv´a SVD¹⁶ rozklad:

A=U SV^T (3.6)

kde A ∈ R^m,n je p˚uvodn´ı matice ˇcetnost´ı (vhodnˇejˇs´ı je analyzovat matici transfor- movanou pomoc´ı TF-IDF), S ∈R^m,n je diagon´aln´ı matice obsahuj´ıc´ı singul´arn´ı ˇc´ısla seˇrazen´a sestupnˇe,U ∈R^m,m aV ∈R^n,n jsou ortogon´aln´ı matice [26, kapitola 7]. Pro redukci dimenze jsou vhodn´e ta singul´arn´ıˇc´ısla, kter´a jsou vˇetˇs´ı neˇz 1 [21]. Poˇzadovan´a dimenze je z´ısk´ana tak, ˇze se v matici S nech´a pouze tolik singul´arn´ıch ˇc´ısel, kolik je poˇzadovan´a dimenze (ostatn´ı se vynuluj´ı), a zpˇetnˇe se vyn´asob´ı matice n´asledovnˇe:

15Principal Component Analysis.

16Singular Value Decomposition.

A_R=U S_RV^T (3.7) kde SR ⊆ S a AR ∈ R^m,r, kde r je poˇzadovan´a dimenze, protoˇze vzniknou nulov´e sloupeˇcky, kter´e je vhodn´e odstranit.

T´ımto lze z´ıskat matici A_R redukovan´e (poˇzadovan´e) dimenze, kter´a by mˇela m´ıt co nejmenˇs´ı ztr´atu informace oproti p˚uvodn´ı matici A.

3.3.4 Algoritmus LSA

S vyuˇzit´ım znalost´ı o SVD (viz sekce 3.3.3) na ˇradu pˇrich´az´ı LSA¹⁷. Jedn´a se o techniku zpracov´an´ı pˇrirozen´eho jazyka [30], kter´a dok´aˇze analyzovat vztahy mezi dokumenty (uˇzivateli) a slovy (URL) [29]. Tato metoda m´a pomoci potlaˇcit neˇz´adouc´ı d˚usledky synonymie. Je zaloˇzena na algebraick´em SVD rozkladu, kde m˚uˇzeme dras- ticky sn´ıˇzit dimenzi, a t´ım z´ıskat efektivnˇejˇs´ı v´ypoˇcty a nalezen´ı v´yznamn´ych podob- nost´ı mezi dokumenty a slovy. SVD je puˇstˇeno nad matic´ı ˇcetnost´ı (viz ˇc´ast 3.3.1), kter´a m˚uˇze b´yt transformov´ana pomoc´ı TF-IDF.

U ·S·V^T =svd(A)'A (3.8)

neboli













| u₁

|





 . . .







| u_r

|











·









s₁ . . . 0 ... . .. ...

0 . . . s_r









·











− v₁ − ...

− v_r −









 '









a_1,1 . . . a_1,n ... . .. ... a_m,1 . . . a_m,n









(3.9) kdeA ∈R^m,n je matice ˇcetnost´ı a S∈R^r,r je diagon´aln´ı matice obsahuj´ıc´ı singul´arn´ı ˇ

c´ısla, kde r je oznaˇcen´ı pro redukovanou dimenzi. Pokud budeme uvaˇzovat matici ˇ

cetnost´ı ve tvaru takov´em, ˇze na sloupeˇcc´ıch jsou jednotliv´a slova (URL) a ˇr´adky jsou jednotliv´e dokumenty (uˇzivatel´e), tak maticeU ∈R^m,r reprezentuje vztah mezi doku- menty a nˇejak´ymi“ kategoriemi, kter´e jsou vytvoˇreny podobnostmi mezi slovy a ma-

je myˇsleno to, ˇze v´ysledn´e kategorie nelze pˇredem odhadnout. Jsou vytvoˇreny shlu- kov´an´ım podobnost´ı mezi jednotliv´ymi dokumenty ˇci slovy.

Matice U, V (singul´arn´ı vektory) prom´ıtaj´ı p˚uvodn´ı data do nov´ych prostor˚u, ve kter´ych vynikne povaha dat.

3.3.5 Algoritmus pLSA

pLSA¹⁹ je statistick´a technika ideovˇe vych´azej´ıc´ı z LSA, avˇsak stoj´ıc´ı na jin´ych podkladech. Zat´ımco LSA (potaˇzmo SVD) vyuˇz´ıv´a L2 nebo Frobeniovu normu [26, kapitola 7.3], tak pLSA maximalizuje vˇerohodnost (likelihood) [6]. Jedn´a se o pravdˇepodobnostn´ı topic-model syst´em, snaˇz´ıc´ı se nal´ezt skryt´e (latentn´ı)

”to- pics“ (t´emata) shlukuj´ıc´ı dokumenty (uˇzivatele) nebo slova (URL) [7, 22]. Startovn´ım bodem pLSA je statistick´y model zvan´y aspect model [9]. Tento aspect model zo- hledˇnuje spoleˇcn´e v´yskyty dat nad asociovan´ymi tˇr´ıdami promˇenn´ez ={z₁, . . . , z_k}, neboli t´ematy [7]. Algoritmus se uˇc´ı pomoc´ı EM²⁰ algoritmu [3]. Prvn´ı f´aze algoritmu (E - expectation) poˇc´ıt´a posteriorn´ı pravdˇepodobnosti pro latentn´ı promˇenn´e a druh´a f´aze (M - maximization) aktualizuje parametry.

E-krok:

P(z_k|d_i, w_j) = P(w_j|z_k)P(z_k|d_i) PK

k⁰=1P(w_j|z_k⁰)P(z_k⁰|d_i) (3.10) M-krok:

P(w_j|z_k) =

PM

i=1n(d_i, w_j)P(z_k|d_i, w_j) PM

i=1

PN

j⁰=1n(d_i, w_j⁰)P(z_k|d_i, w_j⁰) (3.11a) P(z_k|d_i) =

PN

j=1n(di, wj)P(zk|di, wj) PN

j=1n(d_i, w_j) (3.11b)

kde z = {z₁, . . . , z_k} jsou latentn´ı t´emata, d = {d₁, . . . , d_m} jsou dokumenty (uˇzivatel´e), w = {w1, . . . , wn} jsou slova (URL) a n(d, w) je hodnota z matice ˇ

cetnost´ı [2]. P(w|z) zn´azorˇnuje distribuci slov pˇres jednotliv´a t´emata a P(z|d) zn´azorˇnuje distribuci t´emat pˇres jednotliv´e uˇzivatele.

Kaˇzdou iterac´ı pLSA algoritmus maximalizuje vˇerohodnost (loglikelihood) n´asledovnˇe:

logL=

M

X

i=1 N

X

j=1

n(d_i, w_j) log ^K

X

k=1

P(z_j|d_i)P(w_j|z_k)

(3.12)

19Probabilistic Latent Semantic Analysis.

20Expectation–Maximization.

D˚uleˇzit´ymi omezen´ımi jsou n´asleduj´ıc´ı omezuj´ıc´ı podm´ınky:

N

X

j=1

P(w_j|z_k) = 1 (3.13a)

K

X

k=1

P(zk|di) = 1 (3.13b)

kter´e zajist´ı spr´avnou normalizaci.

V´ysledkem tohoto postupu je z´ısk´an´ı distribuc´ı slov (URL) nad jednotliv´ymi t´ematy. Tyto distribuce (pravdˇepodobnostn´ı rozdˇelen´ı) v´yznamnˇe definuj´ı jednot- liv´a t´emata, jeˇz nen´ı lehk´e jednotnou formou popsat, protoˇze se jedn´a o modely smˇes´ı (mixture model), kter´e ve sv´e podstatˇe v˚ubec nemusej´ı reflektovat jednotn´y popisn´y syst´em. V sekci 4.3 je tato problematika rozebr´ana podrobnˇeji. Dalˇs´ım v´ysledkem pLSA je distribuce t´emat pˇres jednotliv´e uˇzivatele. Tedy pro kaˇzd´eho uˇzivatele (z tr´enovac´ı sady) je zn´amo jeho pravdˇepodobnostn´ı rozdˇelen´ı do nale- zen´ych t´emat. Tato informace je vhodn´a k tomu, abychom zjistili v´ıce informac´ı o st´avaj´ıc´ıch uˇzivatel´ıch. Pro pˇr´ıpad, ˇze budeme potˇrebovat zaˇradit nov´eho uˇzivatele d do natr´enovan´eho modelu, je moˇzn´e vyuˇz´ıt procedurufolding-in [8], kter´a je inkre- mentovanou variantou EM algoritmu, pˇriˇcemˇz v M-kroku se nemˇen´ı jiˇz natr´enovan´a P(w|z). T´ımto dostaneme distribuci t´emat pro nov´e uˇzivatele, neboli jejich um´ıstˇen´ı do prostoru t´emat.

3.4 Nevydaˇ ren´ e experimenty

V t´eto ˇc´asti pr´ace jsou shrnuty nˇekter´e postupy, kter´e nakonec nebyly pouˇzity k fin´aln´ımu zpracov´an´ı, protoˇze jejich v´ysledky nebyly dostateˇcnˇe uspokojiv´e. Pˇresto je vhodn´e tyto experimenty zm´ınit, protoˇze jejich v´ysledky byly velmi n´apomocn´e v hled´an´ı vhodnˇejˇs´ı cesty pˇri anal´yze dat.

3.4.1 Shlukovac´ı algoritmy, PCA, LSA

Prvn´ım n´apadem pˇri hled´an´ı kategori´ı jsou metody shlukov´an´ı (clusterov´an´ı).

Jedn´a se o statistick´e metody slouˇz´ıc´ı ke klasifikaci objekt˚u. Shlukovac´ı metody rozdˇeluj´ı vzorky do skupin, ve kter´ych jsou si tyto vzorky nejpodobnˇejˇs´ı z hlediska zvolen´e metriky. Jedn´ım z v´yznamn´ych shlukovac´ıch algoritm˚u je K-means popsan´y v ˇc´asti 3.3.2.

Aby algoritmus K-means d´aval rozumn´e v´ysledky bylo nutn´e nejprve data transformovat pomoc´ı TF-IDF algoritmu. T´ım data mˇela z´aroveˇn znormalizovan´e ˇr´adky. C´ılem bylo nalezen´ı shluk˚u webov´ych str´anek. Vzhledem k velikosti matice nebylo moˇzn´e spuˇstˇen´ı klasick´e K-means implementace [18] na pln´e velikosti matice.

N´asledovala ˇc´asteˇcn´a redukce t´eto matice a vyuˇzit´ı rychlejˇs´ı implementace Mini- BatchKmeans [19, 20]. Nyn´ı jiˇz bylo moˇzn´e puˇstˇen´ı K-means nad daty, v´ysledky nebyly nijak pˇresvˇedˇciv´e. Hlavn´ım probl´emem bylo urˇcen´ı k (poˇctu shluk˚u) a to, ˇ

ze nˇekter´e vytvoˇren´e shluky byly obrovsk´e v porovn´an´ı s jin´ymi. Tyto probl´emy um´ı ˇreˇsit algoritmy jako jsou Afinn´ı propagace [25] ˇci DBSCAN [5], kter´e dok´aˇz´ı odhadnout k a z´aroveˇn ˇreˇsit hustotu nalezen´ych shluk˚u, ale jsou v´ypoˇcetnˇe mnohem n´aroˇcnˇejˇs´ı.

Pˇri prozkoum´an´ı v´ysledk˚u z´ıskan´ych pomoc´ı v´yˇse zm´ınˇen´ych shlukovac´ıch algo- ritm˚u jsme nar´aˇzeli st´ale na ten sam´y probl´em, a tedy velmi hust´e um´ıstˇen´ı bod˚u (dom´en) okolo poˇc´atku. Proto vhodnˇejˇs´ım ˇreˇsen´ım bylo prom´ıtnut´ı dan´eho prostoru do jin´e dimenze, kde souˇradn´e osy budou korelovat s hlavn´ımi komponentami pro- storu dat. Probl´em prom´ıtnut´ı dat do nov´eho prostoru reflektuj´ıc´ıho hlavn´ı kompo- nenty syst´emu ˇreˇs´ı napˇr´ıklad algoritmus PCA bl´ıˇze popsan´y v sekci 3.3.3. Pomoc´ı tohoto algoritmu bylo moˇzn´e sn´ıˇzit dimenzi prostoru se zachov´an´ım maxim´aln´ı in- formaˇcn´ı hodnoty. Zpˇetnˇe rekonstruovan´a matice niˇzˇs´ı dimenze byla opˇet pomoc´ı shlukovac´ıch algoritm˚u (prim´arnˇe K-means) zpracov´ana, ale mnohem lepˇs´ı v´ysledky jsme dostali pˇri pouˇzit´ı LSA, odkud jsme zpracovali pouze matici V z SVD roz- kladu. Pˇri porovn´an´ı v´ystup˚u vych´azej´ıc´ıch z TF-IDF matice a bin´arn´ı matice²¹byly

21Bin´arn´ı matice je takov´a, kter´a m´a m´ısto nenulov´ych hodnot ˇc´ıslo 1 a jinde 0.

zaznamen´any v´yraznˇe lepˇs´ı v´ysledky pr´avˇe pˇri pouˇzit´ı bin´arn´ı matice, a tedy tato matice byla pouˇzita v n´asleduj´ıc´ıch v´ypoˇctech. Shlukovac´ı algoritmy vr´atily mnoho shluk˚u (cluster˚u), kter´e byly rozprostˇren´e po cel´em prostoru, ale naˇsly tak´e velmi

´

uzce zamˇeˇren´e clustery. Pˇri odfiltrov´an´ı cluster˚u s ˇsirˇs´ım z´abˇerem²² z˚ustaly pouze ty clustery, kter´e splˇnovali n´asleduj´ıc´ı podm´ınky v konjuknci:

• Nejnavˇstˇevovanˇejˇs´ı str´anka z clusteru byla navˇstˇevov´ana alespoˇn 10 % uˇzivateli z dan´eho t´ematu.

• Tuto nejnavˇstˇevovanˇejˇs´ı str´anku navˇst´ıvilo alespoˇn 10 uˇzivatel˚u.

• Celkov´y poˇcet uˇzivatel˚u v clusteru je alespoˇn 15.

V´ystupem byly pouze takov´e shluky webov´ych str´anek, kter´e sv´ym obsahem byly velmi ´uzce specializov´any. N´ıˇze v tabulce je uk´azka dvou n´ahodnˇe vybran´ych cluster˚u, kter´e maj´ı velmi ´uzk´e zamˇeˇren´ı:

Tabulka 3.1: Velmi ´uzce specializovan´e clustery

Cluster 1 Cluster 2

getdogsex.com cooks.com 3animalsextube.com allrecipes.com

pornsocket.com yummly.com zootube365.com bettycrocker.com animalsexfun.com myrecipes.com

petsex.com epicurious.com homeanimaltube.com kraftrecipes.com

Cluster 2 zobrazuje str´anky zab´yvaj´ıc´ı se pouze vaˇren´ım. Tedy bychom mohli j´asat, ˇ

ze pˇresnˇe takov´e specializace hled´ame. Bohuˇzel zbyl´ych cca 70 % cluster˚u se zab´yvaj´ı sexu´aln´ım obsahem a kv˚uli velmi ´uzk´e specializaci byly nalezeny i tak nechutn´e clus- tery podobn´e Clusteru 1, kter´e se zab´yvaj´ı sexu´aln´ımi str´ankami zamˇeˇren´ymi na zoofilii. Nutno podotknout, ˇze takto ´uzce specializovan´e clustery obsahovaly pouze pˇribliˇznˇe 2 % ze vˇsech webov´ych str´anek v dostupn´em korpusu, a pr´avˇe tyto str´anky byly tak moc ´uzce specializov´any, ˇze nemˇely vypov´ıdaj´ıc´ı hodnotu pro cel´y dataset.

Z tˇechto d˚uvod˚u byla pozornost dalˇs´ıho v´yzkumu upˇrena na postupy s jin´ymi pˇr´ıstupy,

3.4.2 S´ eriov´ e pLSA

Bohuˇzel v pouˇzit´ych knihovn´ach (scikit-learn a ScpiPy) nen´ı algoritmus pLSA implementov´an, a tedy bylo nutn´e pouˇz´ıt jinou implementaci. Jako vhodn´e ˇreˇsen´ı byla zvolena implementace k´odu [13], kter´y je v n´asleduj´ıc´ı ˇc´asti pops´an.

Zdrojov´y k´od 3.1: Implementace serializovan´eho pLSA

1 i m p o r t n u m p y as np 2 ...

3 def p l s a ( t e r m _ d o c _ m a t r i x ):

4 p _ z _ d = np . z e r o s ([ n u m b e r _ o f _ d o c u m e n t s ,

5 n u m b e r _ o f _ t o p i c s ])

6 p _ w _ z = np . z e r o s ([ n u m b e r _ o f _ t o p i c s ,

7 n u m b e r _ o f _ w o r d s )])

8 p _ z _ d _ w = np . z e r o s ([ n u m b e r _ o f _ d o c u m e n t s ,

9 n u m b e r _ o f _ w o r d s ,

10 n u m b e r _ o f _ t o p i c s ])

11 for i in r a n g e( m a x _ i t e r ):

12 # E - s t e p

13 for d _ i n d e x in r a n g e( n u m b e r _ o f _ d o c u m e n t s ):

14 for w _ i n d e x in r a n g e( n u m b e r _ o f _ w o r d s ):

15 p r o b = p _ z _ d [ d_index , :] * p _ w _ z [: , w _ i n d e x ]

16 n o r m a l i z e ( p r o b )

17 p _ z _ d _ w [ d _ i n d e x ][ w _ i n d e x ] = p r o b

18 # M - s t e p

19 for z in r a n g e( n u m b e r _ o f _ t o p i c s ):

20 for w _ i n d e x in r a n g e( n u m b e r _ o f _ w o r d s ):

21 s = 0

22 for d _ i n d e x in r a n g e( n u m b e r _ o f _ d o c u m e n t s ):

23 c o u n t = t e r m _ d o c _ m a t r i x [ d _ i n d e x ][ w _ i n d e x ]

24 s = s + c o u n t * p _ z _ d _ w [ d_index ,

25 w_index ,

26 z ]

27 p _ w _ z [ z ][ w _ i n d e x ] = s

28 n o r m a l i z e ( p _ w _ z [ z ])

29 for d _ i n d e x in r a n g e( n u m b e r _ o f _ d o c u m e n t s ):

30 for z in r a n g e( n u m b e r _ o f _ t o p i c s ):

31 s = 0

32 for w _ i n d e x in r a n g e( n u m b e r _ o f _ w o r d s ):

33 c o u n t = t e r m _ d o c _ m a t r i x [ d _ i n d e x ][ w _ i n d e x ]

34 s = s + c o u n t * p _ z _ d _ w [ d_index ,

35 w_index ,

36 z ]

37 p _ z _ d [ d _ i n d e x ][ z ] = s

38 n o r m a l i z e ( p _ z _ d [ d _ i n d e x ])

K´od na pˇredchoz´ı str´ance (viz algoritmus 3.1) je jednoduchou implementac´ı EM a pLSA algoritmu. Vstupem je matice ˇcetnost´ıterm_doc_matrix a v´ystupem jsou matice p_z_d (znaˇc´ıc´ı podm´ınˇen´e pravdˇepodobnosti t´ematu a dokumentu P(z|d)) a matice p_w_z (znaˇc´ıc´ı podm´ınˇen´e pravdˇepodobnosti slova a t´ematu P(w|z)). N´ıˇze jsou uk´az´any sloˇzitosti²⁴:

Tabulka 3.2: Sloˇzitosti serializovan´eho algoritmu pLSA ˇ

casov´a sloˇzitost pamˇet’ov´a n´aroˇcnost

Ω(I·D·W ·(1 + 2Z)) Ω(Z·(D+W +D·W) +D·W)

kde I je poˇcet iterac´ı, D je poˇcet dokument˚u (uˇzivatel˚u), W je poˇcet slov (URL) aZ je poˇzadovan´y poˇcet t´emat. S tˇemito parametry tato implementace nen´ı vhodn´a pro vˇetˇs´ı matice. V pˇr´ıpadˇe pouˇzit´ı t´eto implementace naraz´ıme jak na ˇcasov´y, tak i na pamˇet’ov´y probl´em. Jiˇz pˇri menˇs´ım datasetu v´ypoˇcetn´ı ˇcas ne´umˇernˇe rychle roste a algoritmus si zbyteˇcnˇe udrˇzuje informace v matici p_z_d_w (znaˇc´ıc´ı posteriorn´ı pravdˇepodobnost P(z|d, w)), jej´ıˇz rozmˇery n´aleˇz´ıR^D,W,Z.

Abychom zrychlili v´ypoˇcet, je vhodn´e uvaˇzovat o jeho paralelizaci. V origin´aln´ım k´odu [13] je i paraleln´ı implementace t´ehoˇz algoritmu, ovˇsem kv˚uli nˇekolika

”drob- nostem“ nesm´ırnˇe pamˇet’ovˇe n´aroˇcn´a. Data (vˇsechny matice se kter´ymi se poˇc´ıt´a) jsou kop´ırov´ana ke kaˇzd´emu procesu. Tedy pamˇet’ov´a n´aroˇcnost t´ımto vzroste na Ω(P ·Z·(D+W +D·W) +P ·D·W), kdeP znaˇc´ı poˇcet proces˚u a pro doplnˇen´ı posledn´ıD·W je matice ˇcetnost´ı, ale v dense²⁵ form´atu, protoˇze p˚uvodn´ı algoritmus nikterak nepracuje s CSR form´atem matice ˇcetnost´ı.

Kapitola 4

Fin´ aln´ı zpracov´ an´ı

Tato kapitola pr´ace pojedn´av´a o postupech, kter´e vedly k nejlepˇs´ım v´ysledk˚um, a tedy kroky popsan´e v t´eto ˇc´asti jsou nazv´any fin´aln´ımi v z´ajmu c´ıl˚u t´eto pr´ace.

Kroky jsou provedeny postupnˇe ve stejn´em poˇrad´ı, jako jsou ˇc´ıslov´any sekce v t´eto kapitole.

4.1 Redukce dat

Redukc´ı dat se pomˇernˇe obs´ahle zab´yv´a ˇc´ast 3.2. Pˇresto jsou v t´eto sekci zopa- kov´any postupy vedouc´ı ke sn´ıˇzeni dimenze dat jak u URL, tak u uˇzivatel˚u.

Prvnˇe je provedena redukce poˇctu URL str´anek, tedy odstranˇen´ı pˇr´ıliˇs velk´ych a pˇr´ıliˇs mal´ych dom´en. Velikost´ı dom´eny je zde myˇslena jej´ı popularita, tedy poˇcet unik´atn´ıch n´avˇstˇevn´ık˚u. Po oˇrezu z˚ustanou pouze ty dom´eny, kter´e jsou navˇstˇevov´any maxim´alnˇe 10 % populace a minim´alnˇe 10 unik´atn´ımi n´avˇstˇevn´ıky. Vyj´adˇreno pomoc´ı matematiky:

W⁰ ={w∈W; 10≤ |w| ≤10 %} (4.1)

kdeW jsou vˇsechny dom´eny,W⁰ jsou dom´eny, kter´e z˚ustaly po oˇrezu a|w|znaˇc´ı poˇcet unik´atn´ıch uˇzivatel˚u pro konkr´etn´ıw jakoˇzto URL. Pro pˇripom´ınku 10 % populace je pˇribliˇznˇe 22 000 uˇzivatel˚u.

Dalˇs´ı odstraˇnov´an´ı je provedeno na uˇzivatel´ıch. Jak jiˇz bylo zm´ınˇeno v ˇc´asti 3.2.2, tak je vhodn´e ponechat pouze ty uˇzivatele, kteˇr´ı chod´ı na 10 aˇz 150 r˚uzn´ych dom´en.

U⁰ ={u∈U; 10≤ |u| ≤150} (4.2)

kdeU jsou vˇsichni uˇzivatel´e, U⁰ jsou jen ti uˇzivatel´e, kteˇr´ı z˚ustali po odstranˇen´ı a|u|

je poˇcet navˇst´ıven´ych r˚uzn´ych dom´en pro konkr´etn´ıho uˇzivatele u.

Posledn´ım krokem je ponech´an´ı pouze v´yznamn´ych dom´en, a tedy odstranˇen´ı tˇech

”m´enˇe“ v´yznamn´ych. Hranice mezi nimi byla urˇcena na 10 % (viz druh´a ˇc´ast sekce 3.2.1). Tedy v´yznamnou dom´enou je takov´a str´anka, kter´a tvoˇr´ı alespoˇn 10 % n´avˇstˇevnosti pro alespoˇn jednoho uˇzivatele.

W⁰⁰ ={w∈W⁰; ∃u∈U⁰ :V(u, w)≥10 %} (4.3) kde U⁰ jsou uˇzivatel´e z pˇredeˇsl´eho odstavce, W⁰ jsou dom´eny z pˇredeˇsl´eho odstavce a W⁰⁰ je koneˇcn´y poˇcet v´yznamn´ych dom´en. Ve v´yrazu 4.3 se ˇr´ık´a, ˇze mnoˇzinu koneˇcn´ych webov´ych str´anek tvoˇr´ı takov´e dom´eny u nichˇz existuje alespoˇn jeden uˇzivatelu, pro kter´eho je v´yznamnost (funkceV(u, w) vrac´ı procentu´aln´ı v´yznamnost dan´e dom´eny w pro konkr´etn´ıho uˇzivatele u) vˇetˇs´ı neˇz 10 %.

Po dokonˇcen´ı vˇsech operac´ı redukce dat je v´ysledn´a velikost matice

191 676 uˇzivatel˚u×37 441 URL z p˚uvodn´ı velikosti 224 679 uˇzivatel˚u×586 624 URL.

4.2 Paraleln´ı pLSA

Vzhledem k tomu, ˇze se topic-model algoritmus pLSA osvˇedˇcil jako velmi re- levantn´ı pro danou problematiku, tak jeho vyuˇzit´ı bylo v´ıcem´enˇe jist´e. Funkˇcnost algoritmu je pops´ana v ˇc´asti 3.3.5.

4.2.1 Popis paraleln´ıho algoritmu pLSA

nutn´e jejich zkop´ırov´an´ı k procesu. Proto bylo nutn´e pˇrij´ıt s jin´ym ˇreˇsen´ım. T´ımto ˇreˇsen´ım je ukl´ad´an´ı dat do sd´ılen´e pamˇeti. Vzhledem k tomu, ˇze v MetaCentru puˇstˇen´e ´ulohy pracuj´ı na nˇekolika r˚uzn´ych procesorech, je vyuˇz´ıv´an´ı sd´ılen´e pamˇeti ponˇekud obt´ıˇznˇejˇs´ı. Je nutn´e sd´ılet pamˇet’ pˇres diskov´e ´uloˇziˇstˇe, ke kter´emu maj´ı pˇr´ıstup vˇsechny procesy na vˇsech procesorech. Bylo tedy nutn´e vyuˇz´ıtmemmap¹. D´ıky tomu bylo moˇzn´e pracovat s mnohem vˇetˇs´ı pamˇet´ı, neˇz byla velikost operaˇcn´ı pamˇeti (RAM) pˇri zachov´an´ı relativnˇe rychl´eho pˇr´ıstupu pˇri sekvenˇcn´ıch operac´ıch. N´ıˇze n´asleduje uk´azka zdrojov´eho k´odu ukazuj´ıc´ı inicializaci sd´ılen´e pamˇeti:

Zdrojov´y k´od 4.1: Inicializace sd´ılen´e pamˇeti v paraleln´ım pLSA

1 i m p o r t n u m p y as np

2 g l o b a l p_z_d , p_w_z , p _ w _ z _ t e m p _ a r r a y , p _ z _ w _ d i _ a r r a y 3 p _ z _ d = np . m e m m a p (" p _ z _ d . mm ", s h a p e =( n u m b e r _ o f _ d o c u m e n t s ,

4 n u m b e r _ o f _ t o p i c ))

5 p _ w _ z = np . m e m m a p (" p _ w _ z . mm ", s h a p e =( n u m b e r _ o f _ t o p i c ,

6 n u m b e r _ o f _ w o r d s ))

7 p _ w _ z _ t e m p _ a r r a y = np . m e m m a p (" p _ w _ z _ t e m p _ a r r a y . mm ",

8 s h a p e =( n u m b e r _ o f _ c h u n k s ,

9 n u m b e r _ o f _ t o p i c ,

10 n u m b e r _ o f _ w o r d s ))

11 p _ z _ w _ d i _ a r r a y = np . m e m m a p (" p _ z _ w _ d i _ a r r a y . mm ",

12 s h a p e =( n u m b e r _ o f _ c h u n k s ,

13 n u m b e r _ o f _ t o p i c ,

14 n u m b e r _ o f _ w o r d s ))

kde matice p_z_d ∈ R^D,Z je P(z|d) a p_w_z ∈ R^Z,W je P(w|z), kde W je poˇcet slov (URL), D je poˇcet dokument˚u (uˇzivatel˚u) a Z je poˇcet t´emat. Ma- tice p_w_z_temp_array ∈ R^C,Z,W slouˇz´ı pro doˇcasn´e ukl´ad´an´ı v´ysledk˚u matice P(w|z) z EM algoritmu a p_z_w_di_array ∈ R^C,Z,W obstar´av´a pozici P(z|w, d).

Promˇenn´aCznaˇc´ı poˇcet ˇc´ast´ı (chunk˚u), kter´e jsou paralelnˇe rozdˇeleny mezi jednotliv´e procesory. T´ımto bychom mˇeli m´ıt vyˇreˇsen´y probl´em se sd´ılenou pamˇet´ı.

Dalˇs´ım ´ukolem bylo rozdˇelen´ı v´ypoˇcetn´ıch ˇc´ast´ı v k´odu tak, aby jednotliv´e ˇc´asti (chunky) byly na sobˇe nez´avisl´e, a tedy paralelizace byla v˚ubec moˇzn´a.

Hlavn´ı idea paralelizace pLSA Kaˇzd´y procesor dostane na starost ˇc´ast doku- ment˚u (pˇr. rozsah 1. aˇz 30. dokument), kter´e zpracuje a vr´at´ı v´yslednou matici P(w|z) pro dan´e dokumenty (1. aˇz 30.). Po dokonˇcen´ı v´ypoˇctu vˇsech ˇc´ast´ı se tyto matice P(w|z) uloˇzen´e v p_w_z_temp_array seˇctou a v´ysledkem je nov´a maticeP(w|z) pro dalˇs´ı iteraci algoritmu.

1Mapov´an´ı diskov´e pamˇeti jakoˇzto operaˇcn´ı pamˇeti RAM.

Pro lepˇs´ı pochopen´ı souvislost´ı je n´ıˇze bliˇzˇs´ı popis postupu:

1. Alokace sd´ılen´ych matic. Vytvoˇren´ı matic mapovan´ych na disk.

2. V´ypoˇcet interval˚u mezi dokumenty (chunk˚uC), kter´e se pozdˇeji pˇredaj´ı jednot- liv´ym proces˚um.

3. Pro kaˇzdou iteraci:

(a) Vytvoˇren´ıC proces˚u.

(b) Kaˇzd´emu z proces˚u se pˇred´a jedna ˇc´ast (chunk C).

(c) Pro kaˇzdou ˇc´ast (chunk), kde i n´aleˇz´ı indexu dokumentu z intervalu pˇriˇrazen´eho dan´e ˇc´asti:

i. E-krok:

P(z|w, d_i) = P(z|d_i) · P(w|z) + 10⁻⁸









x1,1 . . . x1,W

... . .. ... x_Z,1 . . . x_Z,W









=







 a1

... a_Z









·









b1,1 . . . b1,W

... . .. ... b_Z,1 . . . b_Z,W









+ 10⁻⁸

(4.4) kde konstanta 10⁻⁸ je

”renormalizaˇcn´ı“ faktor (matice pln´a tˇechto ˇ

c´ısel), kter´y odstran´ı nulu vzniklou pˇri souˇcinu P(z|d_i) · P(w|z).

Vznikl´a nula by se totiˇz propagovala do dalˇs´ıch krok˚u a pˇri normali- zaci by se dˇelilo nulou.

ii. Normalizace sloupeˇck˚uP(z|w, d_i) dle L1 normy.

iii. M-krok, ˇc´ast prvn´ı:

Y_n(w,d^P(z|w,di)

i) = n(w|d_i) · P(z|w, d_i)









y_1,1 . . . y_1,W ... . .. ... y_Z,1 . . . y_Z,W









=

n_Di,1 . . . n_Di,W ·









x_1,1 . . . x_1,W ... . .. ... x_Z,1 . . . x_Z,W









(4.5)