historie stahovaných webových dokumentů

´r ˇska ´ pra ´ ce Bakala

´ klade ˇ Kategorizace uˇ zivatel˚ u na za ´ ch webovy ´ ch historie stahovany dokument˚ u

ˇ´ık Duˇ san Jenc

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

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

Praha 2015

Č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 V Praze dne 5. 2. 2015

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 iv

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 Tunysovi 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ˇca´st´ı Operational Program Research and Development for Innovations, reg. ˇc. CD.1.05 / 3.2.00 / 08.0144.

v

M´e rodinˇe.

vi

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 statistick´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 categorization 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 categories 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 have been found thanks to this algorithm. The topics are formed by distribution of websites and every user is described by distribution of the found topics. The description of topics has been supplemented with categories from DMOZ database and later with the most important words, which are appeared on web pages describing the topic. Anonymized data was provided by unnamed antivirus company. Keywords:

categorization, clustering analysis, topic-model, pLSA vii

Obsah ´ 1 Uvod 1.1 Motivace . . . . . 1.2 Definice probl´emu 1.2.1 Data . . . 1.2.2 Probl´em . 1.3 Struktura pr´ace .

. . . . .

1 1 2 2 2 3

2 Souvisej´ıc´ı pr´ ace 2.1 Anal´ yza clickstreamu . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Anal´ yza matice ˇcetnost´ı . . . . . . . . . . . . . . . . . . . . . . . . .

4 4 5

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

3 Anal´ yza 3.1 Povaha dat . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Rozloˇzen´ı n´avˇstˇevnosti podle URL str´anek . . . . . 3.1.2 Rozloˇzen´ı n´avˇstˇevnosti podle navˇst´ıven´ ych str´anek 3.2 Pˇredzpracov´an´ı dat . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Redukce poˇctu URL . . . . . . . . . . . . . . . . . 3.2.2 Redukce poˇctu uˇzivatel˚ u . . . . . . . . . . . . . . . 3.3 Metodika . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Algoritmus TF-IDF . . . . . . . . . . . . . . . . . . 3.3.2 Algoritmus K-means . . . . . . . . . . . . . . . . . 3.3.3 Algoritmus PCA . . . . . . . . . . . . . . . . . . . 3.3.4 Algoritmus LSA . . . . . . . . . . . . . . . . . . . . 3.3.5 Algoritmus pLSA . . . . . . . . . . . . . . . . . . . 3.4 Nevydaˇren´e experimenty . . . . . . . . . . . . . . . . . . . 3.4.1 Shlukovac´ı algoritmy, PCA, LSA . . . . . . . . . . 3.4.2 S´eriov´e pLSA . . . . . . . . . . . . . . . . . . . . .

viii

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

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

6 6 7 8 10 10 12 14 14 15 16 17 18 20 20 22

4 Fin´ aln´ı zpracov´ an´ı 4.1 Redukce dat . . . . . . . . . . . . . . . . . . . . . 4.2 Paraleln´ı pLSA . . . . . . . . . . . . . . . . . . . 4.2.1 Popis paraleln´ıho algoritmu pLSA . . . . . 4.2.2 Porovn´an´ı rychlosti . . . . . . . . . . . . . 4.3 Popis nalezen´ ych t´emat . . . . . . . . . . . . . . . 4.3.1 Open Directory Project - DMOZ . . . . . 4.3.2 Nejv´ yznamnˇejˇs´ı slova dle webov´eho obsahu 4.4 Fin´aln´ı v´ ysledky . . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

24 24 25 25 31 34 34 37 41

5 Z´ avˇ er

43

A Obsah pˇ riloˇ zen´ eho CD

45

Literatura

46

Pouˇ zit´ e zkratky

50

ix

Seznam tabulek 1.1

Struktura clickstreamu . . . . . . . . . . . . . . . . . . . . . . . . . .

2

3.1 3.2

Velmi u ´zce specializovan´e clustery . . . . . . . . . . . . . . . . . . . . Sloˇzitosti serializovan´eho algoritmu pLSA . . . . . . . . . . . . . . . .

21 23

4.1 4.2 4.3 4.4

Porovn´an´ı sloˇzitost´ı implementac´ı algoritmu pLSA . . . . . . . Porovn´an´ı rychlost´ı a sloˇzitost´ı implementac´ı algoritmu pLSA Kategorie z DMOZ . . . . . . . . . . . . . . . . . . . . . . . . Nejv´ yznamnˇejˇs´ı slova dle obsah˚ u str´anek . . . . . . . . . . . .

33 33 36 39

x

. . . .

. . . .

. . . .

. . . .

Seznam obr´ azk˚ u 3.1 3.2 3.3 3.4 3.5

Poˇcet uˇzivatel˚ u na URL adrese . . . . . . . . . . . . . . . . . . . . . Poˇcet uˇzivatel˚ u na 30 nejvˇetˇs´ıch URL ares´ach . . . . . . . . . . . . . Poˇcet navˇst´ıven´ ych str´anek uˇzivateli . . . . . . . . . . . . . . . . . . . Procento odstranˇen´ ych str´anek v z´avislosti na procentu oˇrezu . . . . Poˇcet navˇst´ıven´ ych str´anek uˇzivateli po odstranˇen´ı nˇeˇza´douc´ıch dom´en

7 8 9 11 13

4.1 4.2 4.3

Rychlost konvergence pLSA . . . . . . . . . . . . . . . . . . . . . . . Zastoupen´ı kategori´ı z DMOZ . . . . . . . . . . . . . . . . . . . . . . Hodnoty entropie napˇr´ıˇc vyhovuj´ıc´ımi t´ematy . . . . . . . . . . . . .

31 37 40

xi

Seznam zdrojov´ ych k´ od˚ u 3.1 4.1 4.2 4.3

Implementace serializovan´eho pLSA . . . . . . Inicializace sd´ılen´e pamˇeti v paraleln´ım pLSA Implementace paraleln´ıho EM algoritmu pLSA Implementace v´ ypoˇctu loglikelihoodu . . . . .

xii

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

22 26 29 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 clickstream1 . 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 2 spoleˇcnost poskytla data pro tuto pr´aci. Sbˇer dat je prov´adˇen pˇri zad´an´ı URL3 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 ˇci dokonce aˇz jednotek TB za jedin´ y den). Takto velk´e mnoˇzstv´ı dat nen´ı trivi´aln´ı zpracovat a je nutn´e pouˇz´ıt sofistikovan´e metody k z´ısk´an´ı hlubˇs´ı informace. Tˇemito metodami se zab´ yv´a tato pr´ace. 1

Z´ aznam navˇst´ıven´ ych adres [14]. ˇ Partner CVUT. 3 Uniform Resource Locator. Unik´atn´ı webov´a adresa. 2

1

1.2 1.2.1

Definice probl´ emu 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 ˇca´st dat, kter´a je citliv´a. Struktura clickstreamu b´ yv´a pˇribliˇznˇe n´asleduj´ıc´ı4 : 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ˇzivatele5 ) 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 po6 7 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.

4

Konkr´etn´ı clickstream m˚ uˇze obsahovat nˇekolik dalˇs´ıch u ´daj˚ 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. 5 Na 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. 6 Byly zvoleny pouze dom´eny 2. ˇr´adu. Pˇr´ıkladem facebook.com, google.com... 7 V buˇ nk´ ach matice jsou poˇcty n´avˇstˇev konkr´etn´ıho uˇzivatele na konkr´etn´ı URL adrese.

2

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 zdokonalen´ı v´ ysledk˚ u.

3

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´ı ˇca´st´ı webu) vedou k u ´spˇ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 → Kategorie 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]. 4

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´ı ˇca´st 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 u ´hl˚ 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 u ´plnˇe stejn´ ym t´ematem se nezab´ yv´a ˇza´dn´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.

5

Kapitola 3 Anal´ yza V t´eto kapitole je pops´ana povaha dat, kter´a jsou n´aslednˇe pomoc´ı nˇekolika algoritm˚ u zanalyzov´ana. Data bylo nutn´e pˇredzpracovat, aby vynikly diskriminuj´ıc´ı informace. 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 u ´vodu 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 CSR1 form´atu a vypad´a n´asledovnˇe:

u1 u2 .. . u224 679

     

w1

w2

...

w586 624

a1,1 a2,1 .. .

a1,2 a2,2 .. .

... ... .. .

a1,586 624 a2,586 624 .. .

a224 679,1

a224 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´ı orientaci ve v´ ysledc´ıch je vyuˇzito grafick´eho zn´azornˇen´ı. 1

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

6

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 matice2 , 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 sestupnˇe. 2

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

7

100.00%

Procento uživatelů

80.00%

60.00%

40.00%

20.00%

0.00% om om om om org om om om om om org om om om om om org om om it.ly om om om om om om om om om om k.c .c .c .c ia. t.c y.c r.c t.c s.c st. n.c .c t.c t.c e.c lla. t.c .c b l.c t.c b.c d.c .c lr.c x.c s.c n.c .c ooutubyeahooazonipedgspoebatwittenposswear igsli ms gaobouteres livmozilmapr ress aypaavasimdzfeeapptluembnetflrivicekedidobe b e p z n a wa ord am wik blo pin gto an cr bu fac yo d se l i w ffin lea g hu o go

URL

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. Nejvhodnˇejˇs´ı metrikou se zde jev´ı mˇeˇren´ı rozsahu navˇst´ıven´ ych str´anek pro jednotliv´e 3 skupiny uˇzivatel˚ u. Matice je nyn´ı seˇctena po ˇra´dc´ı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 4 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 skupiny obyvatel. 3 4

Kaˇzd´ a nenulov´ a hodnota byla nahrazena ˇc´ıslem 1. Uˇzivatel´e byli anonymizov´ ani.

8

35%

30%

procento uživatelů

25%

20%

15%

10%

5%

0%

14 - 52

91 - 129

168 - 206

244 - 283

rozsahy navštívených stránek

321 - 360

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´anek5 . 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.

5ˇ

C´ıslo 398 nen´ı v grafu z d˚ uvodu pˇrehlednosti ostatn´ıch ˇc´ısel zobrazeno. Jedn´a se o maxim´ aln´ı poˇcet r˚ uzn´ ych webov´ ych dom´en, kter´e byly navˇst´ıveny alespoˇ n jedn´ım uˇzivatelem.

9

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´ı adresy6 a m´alo v´ yznamn´e ad7 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´ı adresy. 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 8 9 weby podobn´e indeed.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 charakteru (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 6

Adresy na kter´e chod´ı vˇetˇs´ı poˇcet uˇzivatel˚ u. V´ yznamn´e z hlediska poˇctu n´ avˇstˇevn´ık˚ u. 8 Port´ al s nab´ıdkami pr´ ace. 9 Port´ al s recepty na vaˇren´ı. 7

10

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 u ´vah 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 nediskriminuj´ı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.

100%

procento odříznutých URL

80%

60%

40%

20%

0% 0%

20%

40%

60%

procento ořezu

80%

100%

Obr´azek 3.4: Procento odstranˇen´ ych str´anek v z´avislosti na procentu oˇrezu 11

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. Motivac´ı 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 redukov´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 ˇca´rou. Uˇzivatel´e spadaj´ıc´ı do tˇechto mez´ı byli zachov´ani.

12

35%

30%

procento uživatelů

25%

20%

15%

10%

5%

0%

2 - 38

74 - 110

146 - 182

219 - 255

rozsahy navštívených stránek

291 - 327

Obr´azek 3.5: Poˇcet navˇst´ıven´ ych str´anek uˇzivateli po odstranˇen´ı nˇeˇza´douc´ı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 u ´spora 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.

13

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 s scikit-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. 10 Vˇetˇsina v´ ypoˇct˚ u byla prov´adˇena v MetaCentru hlavnˇe vzhledem k vˇetˇs´ımu objemu dat.

3.3.1

Algoritmus TF-IDF

TF-IDF11 (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´ı 12 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 zastoupena konkr´etn´ı URL dom´ena (sloupec matice). Vysvˇetlen´ı pojm˚ u: ni,j (3.1) tfi,j = P k nk,j kde ni,j je poˇcet v´ yskyt˚ u slova ti (webu) v dokumentu dj (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 dj . idfi = log

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

(3.2)

ˇ e rebublice. Lze si zde na omezenou Jedn´ a se o sdruˇzen´ı superpoˇc´ıtaˇc˚ u rozm´ıstˇen´ ych po cel´e Cesk´ dobu zarezervovat velik´e mnoˇzstv´ı v´ ypoˇcetn´ıch prostˇredk˚ u. 11 Term Frequency - Inverse Document Frequency. 12 Rozs´ ahl´ y soubor text˚ u (dokument˚ u). 10

14

kde |D| je poˇcet dokument˚ u (uˇzivatel˚ u) a |{j : ti ∈ dj }| je poˇcet dokument˚ u obsahuj´ıc´ıch slovo ti [16]. Pot´e se fin´aln´ı hodnota spoˇc´ıt´a n´asledovnˇe: tf idfi,j = tfi,j · idfi

(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´adek tf 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-means13 je clusterovac´ı (shlukovac´ı) algoritmus vytv´aˇrej´ıc´ı k disjunktn´ıch cluster˚ u (shluk˚ u). Iterativnˇe minimalizuje odchylky centroid˚ u (stˇred˚ u) od bod˚ u v dan´em 14 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 clusteru 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˚ u x = {x1 , . . . , xn } ∈ Rm , ˇc´ıslo k ∈ N; k ≤ n a S = {S1 , . . . , Sk } jakoˇzto seznam cluster˚ u. Hled´a se lok´aln´ı optimum n´asledovnˇe: argmin S

k X X

kx − µi k2

(3.4)

i=1 x∈Si

kde m´ısto k · k2 m˚ uˇze b´ yt libovoln´a metrika. 13 14

Shlukovac´ı algoritmus. Existuj´ı efektivnˇejˇs´ı metody pro poˇc´ateˇcn´ı inicializaci, napˇr´ıklad algoritmus K-means++ [1].

15

M´ısto metriky lze i pouˇz´ıt tzv. kosinovou podobnost urˇcuj´ıc´ı sv´ıraj´ıc´ı u ´hel mezi dvˇema vektory (body od poˇc´atku). Pm A·B i=1 Ai × Bi pPm similarity = cos(θ) = = pPm 2× 2 kAkkBk (A ) i i=1 i=1 (Bi )

(3.5)

kde A, B ∈ Rm 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ˇca´teˇcn´ım rozdˇelen´ım a br´at v u ´vahu 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

PCA15 , 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 (principal 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 16 SVD rozklad: A = U SV T (3.6) kde A ∈ Rm,n je p˚ uvodn´ı matice ˇcetnost´ı (vhodnˇejˇs´ı je analyzovat matici transformovanou pomoc´ı TF-IDF), S ∈ Rm,n je diagon´aln´ı matice obsahuj´ıc´ı singul´arn´ı ˇc´ısla seˇrazen´a sestupnˇe, U ∈ Rm,m a V ∈ Rn,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:

15 16

Principal Component Analysis. Singular Value Decomposition.

16

AR = U S R V T

(3.7)

kde SR ⊆ S a AR ∈ Rm,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 AR 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´ı LSA17 . 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ˇza´douc´ı d˚ usledky synonymie. Je zaloˇzena na algebraick´em SVD rozkladu, kde m˚ uˇzeme drasticky sn´ıˇzit dimenzi, a t´ım z´ıskat efektivnˇejˇs´ı v´ ypoˇcty a nalezen´ı v´ yznamn´ ych podobnost´ı mezi dokumenty a slovy. SVD je puˇstˇeno nad matic´ı ˇcetnost´ı (viz ˇca´st 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           − v − 1 a . . . a s1 . . . 0 | | 1,1 1,n            .. .. .. . . ..  ..  ..   . . . · · ' . . .  . u1  ur   . . .     | | 0 . . . sr a . . . a m,1 m,n − vr − (3.9) kde A ∈ Rm,n je matice ˇcetnost´ı a S ∈ Rr,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 ˇra´dky jsou jednotliv´e dokumenty (uˇzivatel´e), tak matice U ∈ Rm,r reprezentuje vztah mezi dokumenty a nˇejak´ ymi“ kategoriemi, kter´e jsou vytvoˇreny podobnostmi mezi slovy a ma” r,n tice V ∈ R reprezentuje vztah opaˇcn´ y, tedy vztah mezi jednotliv´ ymi dom´enami v˚ uˇci nˇejak´ ym“ kategori´ım vytvoˇren´ ych z podobnost´ı uˇzivatel˚ u18 . Slovem nˇejak´ y“ ” ” 17

Latent Semantic Analysis. Vzhledem k poˇzadovan´e niˇzˇs´ı dimenzi dat r ≤ min{m, n} lze velikosti matic U, S, V omezit pomoc´ı r, pˇrestoˇze SVD rozklad to ve sv´e p˚ uvodn´ı formˇe neumoˇzn ˇuje. Je nutn´e pouˇz´ıt tzv. redukovan´ y SVD rozklad, d´ıky kter´emu nen´ı nutn´e poˇc´ıtat pln´e SVD, kter´e bychom n´aslednˇe oˇrezali na pˇr´ısluˇsnou dimenzi. 18

17

je myˇsleno to, ˇze v´ ysledn´e kategorie nelze pˇredem odhadnout. Jsou vytvoˇreny shlukov´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

pLSA19 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 zohledˇ nuje spoleˇcn´e v´ yskyty dat nad asociovan´ ymi tˇr´ıdami promˇenn´e z = {z1 , . . . , zk }, neboli t´ematy [7]. Algoritmus se uˇc´ı pomoc´ı EM20 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 (wj |zk )P (zk |di ) (3.10) P (zk |di , wj ) = PK k0 =1 P (wj |zk0 )P (zk0 |di ) M-krok: PM

i=1 n(di , wj )P (zk |di , wj ) P (wj |zk ) = PM P N i=1 j 0 =1 n(di , wj 0 )P (zk |di , wj 0 ) PN j=1 n(di , wj )P (zk |di , wj ) P (zk |di ) = PN j=1 n(di , wj )

(3.11a) (3.11b)

kde z = {z1 , . . . , zk } jsou latentn´ı t´emata, d = {d1 , . . . , dm } 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: X  M X N K X log L = n(di , wj ) log P (zj |di )P (wj |zk ) (3.12) i=1 j=1 19 20

k=1

Probabilistic Latent Semantic Analysis. Expectation–Maximization.

18

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

P (wj |zk ) = 1

(3.13a)

j=1 K X

P (zk |di ) = 1

(3.13b)

k=1

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´ı jednotliv´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 nalezen´ 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 proceduru folding-in [8], kter´a je inkrementovanou 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.

19

3.4

Nevydaˇ ren´ e experimenty

V t´eto ˇca´sti 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 ˇca´sti 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 ˇra´dky. 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 MiniBatchKmeans [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 algoritm˚ 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 prostoru dat. Probl´em prom´ıtnut´ı dat do nov´eho prostoru reflektuj´ıc´ıho hlavn´ı komponenty 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´ı informaˇ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 rozkladu. Pˇri porovn´an´ı v´ ystup˚ u vych´azej´ıc´ıch z TF-IDF matice a bin´arn´ı matice21 byly 21

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

20

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 u ´zce zamˇeˇren´e clustery. Pˇri odfiltrov´an´ı cluster˚ u s ˇsirˇs´ım z´abˇerem22 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 u ´zce specializov´any. N´ıˇze v tabulce je uk´azka dvou n´ahodnˇe vybran´ ych cluster˚ u, kter´e maj´ı velmi u ´zk´e zamˇeˇren´ı: Tabulka 3.1: Velmi u ´zce specializovan´e clustery Cluster 2 Cluster 1 getdogsex.com cooks.com 3animalsextube.com allrecipes.com yummly.com pornsocket.com bettycrocker.com zootube365.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 u ´zk´e specializaci byly nalezeny i tak nechutn´e clustery podobn´e Clusteru 1, kter´e se zab´ yvaj´ı sexu´aln´ımi str´ankami zamˇeˇren´ ymi na zoofilii. Nutno podotknout, ˇze takto u ´zce 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 u ´zce 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, mezi kter´e patˇr´ı napˇr´ıklad algoritmus pLSA. Dalˇs´ım v´ yznamn´ ym d˚ uvodem je fakt, ˇze clusterovac´ı algoritmy uspoˇra´d´avaj´ı data do disjunktn´ıch skupin, kter´e ale nedostateˇcnˇe popisuj´ı r˚ uznorod´eho uˇzivatele23 . Uˇzivatel m˚ uˇze m´ıt z´ajmy zakategorizovan´e do v´ıce skupin, ale tyto skupiny ve sv´ ych disjunktn´ıch podob´ach popsat uˇzivatele (napˇr´ıklad pomoc´ı URL) nedok´aˇz´ı, a je tedy nutn´e vyuˇz´ıt jin´eho pˇr´ıstupu. 22 ˇ

S´ırˇs´ım z´ abˇerem je zde myˇsleno to, ˇze v dan´em clusteru bylo velmi mnoho adres, kter´e byly velmi m´ alo navˇstˇevov´ any populac´ı dan´eho clusteru. 23 Myˇsleno z hlediska poˇctu r˚ uzn´ ych z´ajm˚ u.

21

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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

import numpy as np ... def plsa ( term_doc_matrix ): p_z_d = np . zeros ([ number_of_documents , number_of_topics ]) p_w_z = np . zeros ([ number_of_topics , number_of_words )]) p_z_d_w = np . zeros ([ number_of_documents , number_of_words , number_of_topics ]) for i in range ( max_iter ): # E - step for d_index in range ( n u mb e r _o f _ do c u me n t s ): for w_index in range ( number_of_words ): prob = p_z_d [ d_index , :] * p_w_z [: , w_index ] normalize ( prob ) p_z_d_w [ d_index ][ w_index ] = prob # M - step for z in range ( number_of_topics ): for w_index in range ( number_of_words ): s = 0 for d_index in range ( n u mb e r _o f _ do c u me n t s ): count = term_doc_matrix [ d_index ][ w_index ] s = s + count * p_z_d_w [ d_index , w_index , z] p_w_z [ z ][ w_index ] = s normalize ( p_w_z [ z ]) for d_index in range ( n u mb e r _o f _ do c u me n t s ): for z in range ( number_of_topics ): s = 0 for w_index in range ( number_of_words ): count = term_doc_matrix [ d_index ][ w_index ] s = s + count * p_z_d_w [ d_index , w_index , z] p_z_d [ d_index ][ z ] = s normalize ( p_z_d [ d_index ])

22

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ˇzitosti24 : Tabulka 3.2: Sloˇzitosti serializovan´eho algoritmu pLSA ˇcasov´a sloˇzitost Ω(I · D · W · (1 + 2Z))

pamˇet’ov´a n´aroˇcnost Ω(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) a Z 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´ı RD,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 ), kde P znaˇc´ı poˇcet proces˚ u a pro doplnˇen´ı 25 posledn´ı D · W je matice ˇcetnost´ı, ale v dense form´atu, protoˇze p˚ uvodn´ı algoritmus nikterak nepracuje s CSR form´atem matice ˇcetnost´ı.

24

V tabulce 3.2 je sice znak Ω pro spodn´ı odhad asymptotick´e sloˇzitosti, ale multiplikativn´ı konstanty jsou zde pomˇernˇe d˚ uleˇzit´e, a tedy nebyly odstranˇeny. Slouˇz´ı pro pozdˇejˇs´ı detailnˇejˇs´ı porovn´ an´ı s paraleln´ı optimalizovanou verz´ı algoritmu pLSA. 25 Form´ at matice, v nˇemˇz jsou uloˇzeny vˇsechny buˇ nky dan´e matice. Oproti CSR form´atu jsou zde uloˇzeny i nulov´e prvky.

23

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 ˇca´sti 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 ˇca´st 3.2. Pˇresto jsou v t´eto sekci zopakov´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 0 = {w ∈ W ; 10 ≤ |w| ≤ 10 %} (4.1) kde W jsou vˇsechny dom´eny, W 0 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.

24

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 0 = {u ∈ U ;

10 ≤ |u| ≤ 150}

(4.2)

kde U jsou vˇsichni uˇzivatel´e, U 0 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 00 = {w ∈ W 0 ;

∃u ∈ U 0 : V (u, w) ≥ 10 %}

(4.3)

kde U 0 jsou uˇzivatel´e z pˇredeˇsl´eho odstavce, W 0 jsou dom´eny z pˇredeˇsl´eho odstavce a W 00 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ˇzivatel u, pro kter´eho je v´ yznamnost (funkce V (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 relevantn´ı pro danou problematiku, tak jeho vyuˇzit´ı bylo v´ıcem´enˇe jist´e. Funkˇcnost algoritmu je pops´ana v ˇca´sti 3.3.5.

4.2.1

Popis paraleln´ıho algoritmu pLSA

Jiˇz bylo naznaˇceno v ˇc´asti 3.4.2, ˇze je vhodnˇejˇs´ı pouˇz´ıt paraleln´ı verzi algoritmu. Bohuˇzel ale paraleln´ı implementace ze zm´ınˇen´e ˇca´sti mˇela jist´e neduhy, a proto bylo nutn´e paraleln´ı algoritmus optimalizovat a zcela jej pˇrepsat. Anal´ yzou jednotliv´ ych krok˚ u bylo moˇzn´e detekovat jistou redundanci vznikaj´ıc´ı pˇri v´ ypoˇctech. Pamˇet’ov´ y probl´em (kop´ırov´an´ı dat s kaˇzd´ ym procesem) je zp˚ usoben t´ım, ˇze syst´emov´e vol´an´ı fork() (kter´e je implicitnˇe vol´ano pˇri paralelizaci) vytvoˇr´ı nov´ y nez´avisl´ y proces, kter´ y m´a sv´e vlastn´ı pamˇet’ov´e u ´loˇziˇstˇe. Aby tento proces mohl pracovat s daty, je 25

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 u ´lohy 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 u ´loˇziˇstˇe, ke kter´emu maj´ı pˇr´ıstup vˇsechny procesy na vˇsech procesorech. Bylo tedy nutn´e vyuˇz´ıt memmap1 . 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 2 3 4 5 6 7 8 9 10 11 12 13 14

import numpy as np global p_z_d , p_w_z , p_w_z_temp_array , p_z_w_di_array p_z_d = np . memmap ( " p_z_d . mm " , shape =( number_of_documents , number_of_topic )) p_w_z = np . memmap ( " p_w_z . mm " , shape =( number_of_topic , number_of_words )) p_w_z_temp_array = np . memmap ( " p_w_z_temp_array . mm " , shape =( number_of_chunks , number_of_topic , number_of_words )) p_z_w_di_array = np . memmap ( " p_z_w_di_array . mm " , shape =( number_of_chunks , number_of_topic , number_of_words ))

kde matice p_z_d ∈ RD,Z je P (z|d) a p_w_z ∈ RZ,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. MaC,Z,W tice p_w_z_temp_array ∈ R 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 ∈ RC,Z,W obstar´av´a pozici P (z|w, d). Promˇenn´a C znaˇc´ı poˇcet ˇca´st´ı (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 u ´kolem 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 ˇca´st dokument˚ 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 ˇca´st´ı se tyto matice P (w|z) uloˇzen´e v p_w_z_temp_array seˇctou a v´ ysledkem je nov´a matice P (w|z) pro dalˇs´ı iteraci algoritmu. 1

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

26

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˚ u C), kter´e se pozdˇeji pˇredaj´ı jednotliv´ 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, di ) 

 x1,1 . . . x1,W  . ..  ...  .. .    xZ,1 . . . xZ,W

= P (z|di )   a1  .  .  =   .  aZ

P (w|z)

+ 10−8

 b1,1 . . . b1,W  . ..  .. .. · . .    bZ,1 . . . bZ,W

+ 10−8

· 

(4.4) kde konstanta 10−8 je renormalizaˇcn´ı“ faktor (matice pln´a tˇechto ” ˇc´ısel), kter´ y odstran´ı nulu vzniklou pˇri souˇcinu P (z|di ) · P (w|z). Vznikl´a nula by se totiˇz propagovala do dalˇs´ıch krok˚ u a pˇri normalizaci by se dˇelilo nulou. ii. Normalizace sloupeˇck˚ u P (z|w, di ) dle L1 normy. iii. M-krok, ˇ c´ ast prvn´ı: P (z|w,di )

Yn(w,di ) 

=

n(w|di )



y1,1 . . . y1,W  . ..  ..  .. . .    = yZ,1 . . . yZ,W

·

P (z|w, di ) 



nDi ,1

 x . . . x 1,W   1,1 .. ..  .  . . . . nDi ,W ·  . . .   xZ,1 . . . xZ,W (4.5)

P (z|w,d )

kde Yn(w,di ) i ∈ RZ,W je doˇcasn´a promˇenn´a a kde n(w|di ) je i-t´ y ˇr´adek (dokument, uˇzivatel) z matice ˇcetnost´ı.

27

iv. M-krok, ˇ c´ ast druh´ a: P (z|di ) =

W X

P (z|w,di )

Yn(w,di )

j=1





  a1 y . . . y 1,1 1,W W X  .   . ..  ..  ..  =  .. . .      j=1 aZ yZ,1 . . . yZ,W

(4.6)

P (z|w,d )

kde matice Yn(w,di ) i je seˇctena po sloupeˇcc´ıch. v. Normalizace vektoru P (z|di ) dle L1 normy. vi. M-krok, ˇ c´ ast tˇ ret´ı: P (w|z)tempc

=

P (w|z)tempc

+

P (z|w,di )

Yn(w,di )



     b1,1 . . . b1,W b1,1 . . . b1,W y1,1 . . . y1,W  .   ..  ..  ..  .. .. ..  ..  =  ...  +  ... . . . . . .        bZ,1 . . . bZ,W bZ,1 . . . bZ,W yZ,1 . . . yZ,W (4.7) kde v matici P (w|z)tempc jsou akumulov´any jednotliv´e d´ılˇc´ı v´ ypoˇcty matice P (w|z) a c je index ˇca´sti v´ ypoˇctu (chunku). (d) Vˇsechny d´ılˇc´ı v´ ysledky z jednotliv´ ych ˇca´st´ı (chunk˚ u) uloˇzen´e v matici P (w|z)tempc , kde c oddˇeluje v´ ypoˇcty z tˇechto ˇca´st´ı (chunk˚ u). Tyto ˇca´sti jsou po dokonˇcen´ı vˇsech proces˚ u seˇcteny, a t´ım vznikne nov´a matice P (w|z): P (w|z)

=

C X

P (w|z)tempc

c=1



   b1,1 . . . b1,W b . . . b 1,1 1,W C X  .  . ..  ..  .. ..  ..   .. = . . . .      c=1 bZ,1 . . . bZ,W bZ,1 . . . bZ,W kde C je poˇcet ˇca´st´ı (chunk˚ u, proces˚ u). 4. Navr´acen´ı matic p_z_d a p_w_z.

28

(4.8) c

Pro doplnˇen´ı je n´ıˇze konkr´etn´ı implementace paraleln´ıho EM algoritmu pLSA: Zdrojov´ y k´od 4.2: Implementace paraleln´ıho EM algoritmu pLSA 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

import numpy as np from sklearn . preprocessing import normalize def do_EM ( p ): start , stop = s t a r t _ s t o p _ i n t e r v a l s [ p ] p_w_z_temp_array [ p ][:] = np . zeros ([ num_z , n_w_d . shape [1]]) p_z_w_di_array [ p ][:] = np . zeros ([ num_z , n_w_d . shape [1]]) for d_index in range ( stop - start ): # E - step : np . multiply ( p_z_d [ start + d_index ][ np . newaxis ]. T , p_w_z , out = p_z_w_di_array [ p ]) np . add ( p_z_w_di_array [ p ] , 1e -8 , out = p_z_w_di_array [ p ]) normalize ( p_z_w_di_array [ p ] , norm = " l1 " , axis =0 , copy = False ) # M - step 1: data = n_w_d . data [ n_w_d . indptr [ start + d_index ]: n_w_d . indptr [ start + d_index + 1]] y = 0. * p_z_w_di_array [ p ] for j , idx in enumerate ( n_w_d . indices [ n_w_d . indptr [ start + d_index ]: n_w_d . indptr [ start + d_index + 1]]): y [: , idx ] = data [ j ] * p_z_w_di_array [ p ][: , idx ] # M - step 2: np . sum (y , axis =1 , out = p_z_d [ start + d_index ]) np . divide ( p_z_d [ start + d_index ] , p_z_d [ start + d_index ]. sum () , out = p_z_d [ start + d_index ]) # M - step 3: np . add ( p_w_z_temp_array [ p ] , y , out = p_w_z_temp_array [ p ])

Na ˇra´dc´ıch 17 aˇz 25 zdrojov´eho k´odu 4.2 je implementov´ano n´asoben´ı CSR matice (vektoru) a matice v dense form´atu. Bohuˇzel ˇz´adn´a z pouˇzit´ ych knihoven tuto operaci nem´a implementovanou, a tak bylo nutn´e tuto operaci implementovat ruˇcnˇe. S vyuˇzit´ım znalosti o CSR matic´ıch, kter´e se skl´adaj´ı ze tˇr´ı pol´ı (data, indices, indptr), lze pˇristupovat pouze k nenulov´ ym prvk˚ um, a t´ım znaˇcnˇe zrychlit v´ ypoˇcet. T´eˇz jsou zde hojnˇe vyuˇz´ıv´any knihovn´ı matematick´e funkce s v´ ystupn´ım parametrem out, kter´e jsou optimalizov´any a v´ ypoˇcet je t´ımto t´eˇz znaˇcnˇe urychlen. Jak jiˇz bylo 29

zm´ınˇeno v popisu algoritmu u E-kroku (viz 3(c)i), tak renormalizaˇcn´ı“ faktor 10−8 ” je do v´ ypoˇctu zahrnut kv˚ uli tomu, aby nemohla vzniknout nula pˇri n´asoben´ı. Tento faktor ovˇsem nijak nezkresluje v´ ysledek, protoˇze konstanta 10−8 je pˇriˇctena v kaˇzd´e iteraci. Abychom mohli mˇeˇrit rychlost konvergence, je vhodn´e poˇc´ıtat na konci kaˇzd´e iterace hodnotu loglikelihoodu (logaritmu vˇerohodnosti). Tu lze poˇc´ıtat opˇet paralelnˇe s podobnou ideou jako u EM algoritmu v´ yˇse zm´ınˇen´eho. Zdrojov´ y k´od 4.3: Implementace v´ ypoˇctu loglikelihoodu 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

import numpy as np def get_loglikehood ( p ): start , stop = s t a r t _ s t o p _ i n t e r v a l s [ p ] L = 0. for d_index in range ( stop - start ): log_p_wd = np . log10 (( p_z_d [ start + d_index ] [ np . newaxis ]. T * p_w_z ) . sum ( axis =0)) data = n_w_d . data [ n_w_d . indptr [ start + d_index ]: n_w_d . indptr [ start + d_index + 1]] for j , idx in enumerate ( n_w_d . indices [ n_w_d . indptr [ start + d_index ]: n_w_d . indptr [ start + d_index + 1]]): L += data [ j ] * log_p_wd [ idx ] return L

kde funkce get_loglikelihood je vol´ana pro kaˇzdou ˇca´st (chunk) a n´aslednˇe jsou v´ ysledky z tˇechto ˇc´ast´ı seˇcteny do jedn´e hodnoty pˇredstavuj´ıc´ı loglikelihood v dan´e iteraci.

30

4.2.2

Porovn´ an´ı rychlosti

Popsan´ y algoritmus 4.2.1 d´ıky sv´e paralelizaci a minimalizaci redundantn´ıho k´odu je mnohem rychlejˇs´ı, neˇz jeho s´eriov´a verze popsan´a v ˇca´sti 3.4.2. Rychlost konvergence popsateln´a grafem loglikelihoodu je oproti s´eriov´e verzi stejn´a. Tento fakt je zp˚ usoben t´ım, ˇze oba algoritmy (s´eriov´ y i paraleln´ı) prov´ad´ı tyt´eˇz akce pˇri v´ ypoˇctu, ale v paraleln´ı verzi jsou tyto akce provedeny rychleji.

−4.0

1e8

hodnota likelihoodu

−4.5

−5.0

−5.5

−6.0

−6.5

−7.0

0

20

40

60

iterace

80

100

120

Obr´azek 4.1: Rychlost konvergence pLSA

Na obr´azku v´ yˇse (viz obr´azek 4.1) je uk´az´an graf loglikelihoodu pro 108 iterac´ı. Budeme-li hledˇet na relativn´ı diferenci (zmˇenu) loglikelihoodu mezi iteracemi (lze tuto diferenci pˇripodobnit k procentu´aln´ı zmˇenˇe), kter´a se asymptoticky bl´ıˇz´ı nule, poˇc´ıtanou n´asledovnˇe: Li − Li−1 (4.9) Li−1 kde Li pˇredstavuje aktu´aln´ı hodnotu loglikelihoodu a Li−1 je hodnota loglikelihoodu z pˇredchoz´ı iterace, tak zjist´ıme, ˇze hodnota relativn´ı diference se pˇribliˇznˇe od 60. iterace pohybuje na menˇs´ıch hodnot´ach neˇz 10−5 . Lze tedy konstatovat, ˇze rychlost konvergence je uˇz natolik pomal´a (menˇs´ı neˇz 0, 00001 % za iteraci), ˇze v´ ypoˇcet dalˇs´ıch iterac´ı uˇz nem´a razantn´ı v´ yznam v pˇresnosti. 31

Kvalitu v´ ypoˇctu a poˇcet iterac´ı lze tak´e odhadnout pomoc´ı v´ ypoˇctu perplexity [7] nebo pomoc´ı zpˇetn´eho dosazen´ı natr´enovan´ ych dokument˚ u (uˇzivatel˚ u) do procedury folding-in. Detailnˇeji se jedn´a o postup takov´ y, ˇze se nejprve natr´enuje P (z|d) a P (w|z) pomoc´ı pLSA algoritmu. Pot´e se vyberou nˇekter´e dokumenty (ˇra´dky matice ˇcetnost´ı) nad kter´ ymi byly tr´enov´any zm´ınˇen´e pravdˇepodobnosti a tyto star´e“ ” dokumenty se vloˇz´ı na vstup metody folding-in, kter´a vr´at´ı P 0 (z|d), coˇz jsou nov´e distribuce t´emat pro uˇzivatele. Porovn´an´ım distribuc´ı P (z|d) z pLSA s novˇe zobrazen´ ymi distribucemi P 0 (z|d) pomoc´ı folding-in pro stejn´e dokumenty lze urˇcit pˇresnost“ tr´enov´an´ı. Jedn´a se o rozd´ıl v distribuc´ıch t´emat pro konkr´etn´ı dokument. ” Opˇet je zde pouˇzit iterativn´ı postup tr´enov´an´ı s mˇeˇren´ım loglikelihoodu. Kˇrivka loglikelihoodu m´a podobnou tendenci jako pˇri tr´enov´an´ı, ale s t´ım rozd´ılem, ˇze poˇc´ateˇcn´ı hodnotou loglikelihoodu je posledn´ı hodnota z tr´enov´an´ı pLSA. Po pˇribliˇznˇe 120 iterac´ıch zmˇena loglikelihoodu je menˇs´ı neˇz 10−10 a rozd´ıl P (z|d) a P 0 (z|d) je v ˇr´adu 10−5 . Pˇri vˇetˇs´ım poˇctu iterac´ı pˇri tr´enov´an´ı lze tento rozd´ıl jeˇstˇe sn´ıˇzit, ale jak je patrn´e z obr´azku 4.1, tendence r˚ ustu nen´ı rychl´a, a tedy pˇresnˇejˇs´ıho v´ ysledku se bude dosahovat jen velmi pomalu. Pro exaktn´ı porovn´an´ı rychlosti je vhodn´e uvaˇzovat nad porovn´an´ım sloˇzitost´ı2 s verz´ı popsanou v ˇca´sti 3.4.2. V tabulce na dalˇs´ı str´ance (viz tabulka 4.1), kde posledn´ı ˇra´dek (paraleln´ı∗ ) je algoritmus popsan´ y v t´eto sekci 4.2.1, I je poˇcet iterac´ı, D je poˇcet dokument˚ u (uˇzivatel˚ u), W je poˇcet slov (dom´en), Z je poˇcet t´emat, P je poˇcet proces˚ u a ε je aditivn´ı konstanta zahrnuj´ıc´ı reˇzii vzniklou se zpracov´an´ım paralelizmu. V tabulce 4.1 je u paraleln´ı∗ implementace zobrazena pamˇet’ov´a n´aroˇcnost pouze pro operaˇcn´ı pamˇet’ RAM, kde sparse(D · W ) znaˇc´ı matici ˇcetnost´ı v CSR form´atu. Tato matice je sice kop´ırov´ana ke kaˇzd´emu procesu, ale vzhledem k jej´ı zanedbatelnˇejˇs´ı velikosti (s porovn´an´ım s dense form´atem) jej´ı pˇresunut´ı na disk nebylo nezbytn´e. Protoˇze algoritmus vyuˇz´ıv´a diskov´eho u ´loˇziˇstˇe pro uloˇzen´ı velk´ ych matic, je vhodn´e 3 ´loˇziˇsti je Θ(Z · (D + W + 2 · C · W )), dodat, ˇze zabran´a pamˇet’ na tomto diskov´em u kde C znaˇc´ı poˇcet ˇc´ast´ı (chunk˚ u) pˇredan´ ych k proces˚ um4 . 2

V tabulce 4.1 je sice znak Ω pro spodn´ı odhad asymptotick´e sloˇzitosti, ale multiplikativn´ı konstanty jsou zde pomˇernˇe d˚ uleˇzit´e, a tedy nebyly odstranˇeny. Slouˇz´ı pro detailnˇejˇs´ı porovn´an´ı star´e“ ” a optimalizovan´e verze algoritmu pLSA. 3 Znak Θ znaˇc´ı pˇresnou asymptotickou n´aroˇcnost a opˇet zde z d˚ uvodu korektn´ıho porovn´an´ı nejsou odstranˇeny multiplikativn´ı konstanty. 4 Vzhledem k tomu, ˇze C se v paraleln´ı∗ implementaci rovn´a P , tak je paralelizmus vyuˇzit na maximum, a je tedy dosaˇzeno maxim´aln´ıho v´ ykonu. Zato v paraleln´ı implementaci [13] bylo vytvoˇreno D proces˚ u, kter´e byly postupnˇe zpracov´av´any P procesory, a tedy vznikl´a reˇzie byla mnohon´asobnˇe vyˇsˇs´ı neˇz u paraleln´ı∗ verze.

32

Tabulka 4.1: Porovn´an´ı sloˇzitost´ı implementac´ı algoritmu pLSA ˇcasov´a sloˇzitost Ω(I · D · W · (1 + 2Z))  I · D · W · (1 + 2Z)  paraleln´ı [13] Ω + 3ε P  I · D ∗ paraleln´ı +ε Ω P

algoritmus s´eriov´ y [13]

pamˇet’ov´a n´aroˇcnost Ω(Z · (D + W + D · W ) + D · W ) Ω(P · (Z · (D + W + D · W ) + D · W )) Ω(P · (Z · W + sparse(D · W )))

N´ıˇze v tabulce 4.2 je uk´azka konkr´etn´ıch ˇcasov´ ych a pamˇet’ov´ ych n´aroˇcnost´ı v z´avislosti na jednotliv´ ych konkr´etn´ıch parametrech, kde A1 je paraleln´ı implemen∗ tace [13] a A2 je implementace z ˇca´sti 4.2.1. Tabulka 4.2: Porovn´an´ı rychlost´ı a sloˇzitost´ı implementac´ı algoritmu pLSA D W Z 1 146 255 30 1 146 255 30 191 676 37 441 200 191 676 37 441 200 191 676 37 441 200 191 676 37 441 200

P I algoritmus 1 1 A1 1 1 A∗2 14 36 A1 14 36 A∗2 14 108 A1 14 108 A∗2

ˇcas [h] RAM [GB] HDD [GB] 47,919 0,230 0 0,109 0,001 0,001 5 525,716 510 368,854 0 46,999 12,193 2,2 16 577,149 510 368,854 0 140,997 12,193 2,2

V posledn´ım ˇr´adku m˚ uˇzeme vidˇet 14 proces˚ u, 108 iterac´ı za ˇcas cca 6 dn˚ u u optimalizovan´e paraleln´ı implementace. Lze jasnˇe vidˇet, ˇze optimalizace byla velmi potˇreba. Tˇechto 6 dn´ı v´ ypoˇctu pˇri 14 v´ ypoˇcetn´ıch j´adrech procesoru Intel Xeon E5-2650v2 2,6 GHz a na velmi rychl´ ych SSD disc´ıch je pˇrijateln´a ˇcasov´a z´atˇeˇz pro z´ısk´an´ı v´ ysledk˚ u. Jak jiˇz bylo zm´ınˇeno v´ yˇse v t´eto ˇca´sti pr´ace, tak 108 iterac´ı je dostateˇcn´ ych 5 ∗ pro vynikaj´ıc´ı pˇresnost . Vyj´adˇreno v procentech, A2 je cca o 99,15 % rychlejˇs´ı, neˇz algoritmus A1 a pamˇet’ovˇe je A∗2 o 99,99 % m´enˇe n´aroˇcn´ y. Algoritmus byl vyzkouˇsen pro 100, 150 a 200 t´emat. Nejlepˇs´ıch v´ ysledk˚ u bylo dosaˇzeno pro 200 t´emat, kde v´ ysledn´e popisy t´emat (viz sekce 4.3) byly nejv´ıce popisn´e a tak´e z˚ ustalo nejv´ıce t´emat vyhovuj´ıc´ıch omezuj´ıc´ım podm´ınk´am popsan´ ych v ˇca´sti 3a sekce 4.3.1, kter´e slouˇz´ı pro odstranˇen´ı m´alo definuj´ıc´ıch t´emat. U 100 t´emat tˇemto podm´ınk´am vyhovˇelo pouze 14 z nich, zato u 200 t´emat to bylo jiˇz pˇres 45. Vˇetˇs´ı poˇcet t´emat je samozˇrejmˇe u ´mˇern´ y vˇetˇs´ımu poˇctu vyhovuj´ıc´ıch t´emat, tedy pro detailnˇejˇs´ı pˇresnost je moˇzn´e poˇc´ıtat s vˇetˇs´ım poˇctem t´emat, ale bylo rozhodnuto, ˇze pro z´ısk´an´ı vypov´ıdaj´ıc´ıch v´ ysledk˚ u je tento poˇcet (200 t´emat) dostateˇcn´ y. 5

Algoritmus byl puˇstˇen 3 kr´ at na 47 hodin kv˚ uli prioritˇe dan´e fronty v MetaCentru. Po 3 tˇechto spuˇstˇen´ıch byl v´ ysledek natolik dostateˇcn´ y, ˇze dalˇs´ıho puˇstˇen´ı nebylo tˇreba. Omezen´ı na 14 jader bylo z d˚ uvodu takov´eho, ˇze v MetaCentru stroje s SSD disky maj´ı m´enˇe procesorov´ ych jader. Rychlost pˇri pouˇzit´ı HDD byla pˇribliˇznˇe o 73 % pomalejˇs´ı, neˇz u pouˇzit´ı SSD disk˚ u.

33

4.3

Popis nalezen´ ych t´ emat

V´ ysledkem pLSA algoritmu jsou pravdˇepodobnosti P (z|d) a P (w|z). Nalezen´e distribuce P (w|z) (pravdˇepodobnosti t´emat pro jednotliv´e dom´eny) by bylo dobr´e nˇejak´ ym zp˚ usobem popsat ˇci dokonce pojmenovat. Bohuˇzel zde ale vych´az´ıme z faktu, ˇze algoritmus nijak nereflektuje jednotn´ y syst´em, kter´ y by bylo snadn´e popsat. Algoritmus vych´az´ı ryze z matice ˇcetnost´ı a hled´a takov´e skupiny dom´en, kter´e jsou pro nˇejakou skupinu uˇzivatel˚ u charakteristick´e. Zde je vhodn´e pouk´azat na fakt, ˇze data, nad kter´ ymi je v´ yzkum prov´adˇen, nemaj´ı dokonal´ y charakter, ale zato jsou vytvoˇrena z re´aln´ ych dat. Konkr´etn´ı uˇzivatel´e opravdu navˇst´ıvili dan´e dom´eny. Ovˇsem pojem uˇzivatel“ je v tomto pohledu ponˇekud ” zav´adˇej´ıc´ı. Jak jiˇz bylo naznaˇceno v sekci 1.2.1 o popisu dat, tak pojem uˇzivatel“, ” kter´ y je zde hojnˇe skloˇ nov´an, nemus´ı reprezentovat konkr´etn´ı osobu v re´aln´em svˇetˇe, ale pouze identifikuje poˇc´ıtaˇc, kter´ y sb´ır´a data. Na tomto poˇc´ıtaˇci m˚ uˇze pracovat v´ıce ˇclen˚ u dom´acnosti, ba dokonce tento poˇc´ıtaˇc m˚ uˇze b´ yt absolutnˇe veˇrejn´ y (napˇr´ıklad v internetov´e kav´arnˇe). To, jak je dan´ y poˇc´ıtaˇc vyuˇz´ıv´an, z dat, kter´a jsme dostali, nelze zjistit. Proto pro zjednoduˇsen´ı probl´emu je jeden ˇra´dek matice ˇcetnost´ı uvaˇzov´an pro jednoho uˇzivatele. T´ım, ˇze m˚ uˇze b´ yt poˇc´ıtaˇc sd´ılen mezi v´ıce osobami doch´az´ı k jist´e desinformaci, neboli zkreslen´ı dat. Kaˇzd´a osoba pouˇz´ıvaj´ıc´ı poˇc´ıtaˇc sb´ıraj´ıc´ı data m˚ uˇze a velmi pravdˇepodobnˇe m´a jin´e z´ajmy, neˇz osoba jin´a vyuˇz´ıvaj´ıc´ı stejn´ y poˇc´ıtaˇc. V matici ˇcetnost´ı jsou ale zaznamen´any z´ajmy vˇsech tˇechto jedinc˚ u dohromady, a tedy v´ ysledn´ y z´ajem“ (okruh webov´ ych dom´en) m˚ uˇze b´ yt mnohem ˇsirˇs´ı, ” neˇz kdyby poˇc´ıtaˇc pouˇz´ıvala pouze jedna osoba. Na tomto z´akladˇe je pomˇernˇe sloˇzit´e urˇcit kategorie z´ajm˚ u jednotliv´ ych uˇzivatel˚ u, protoˇze pr´avˇe z´aznamy z jednotliv´ ych poˇc´ıtaˇc˚ u mohou poch´azet od v´ıcero jedinc˚ u, a tedy profil ˇclovˇeka sestaven nad tˇemito z´aznamy m˚ uˇze b´ yt do jist´e m´ıry nepˇresn´ y.

4.3.1

Open Directory Project - DMOZ

Vhodn´ ym ˇreˇsen´ım k popisu str´anek m˚ uˇze b´ yt ODP; Open Directory Project neboli ODP neboli DMOZ6 je nejvˇetˇs´ı lidmy budovan´y katalog internetov´ych str´anek, kter´y vytv´aˇrej´ı dobrovoln´ı editoˇri z cel´eho svˇeta [4]. Tento katalog obsahuje v´ıce neˇz ˇctyˇri miliony str´anek, kter´e jsou rozdˇeleny do v´ıce neˇz jednoho milionu kategori´ı a podkategori´ı. Na tomto port´ale existuje 137 582 dom´en v pr˚ uniku se zpracov´avan´ ym pln´ ym datasetem, ale pouze 17 073 dom´en v pr˚ uniku s oˇrezan´ ym datasetem dle sekce 4.1. Tento fakt, ˇze existuje popis kategorie pouze pro 45,6 % URL m˚ uˇze b´ yt znaˇcnˇe 6

The Open Directory Project (ODP), nejvˇetˇs´ı lidmy budovan´ y katalog internetov´ ych str´anek.

34

omezuj´ıc´ı pro u ´plnost v´ ysledku. Lepˇs´ı port´al s vˇetˇs´ım poˇctem v´ ysledk˚ u nebyl bohuˇzel nalezen. Kategorie v DMOZ jsou ˇrazeny hierarchicky. Do prvn´ıho stupnˇe spadaj´ı kategorie: Arts, Business, Computers, Games, Health, Home, Kids and Teens, News, Recreation, Reference, Regional, Science, Shopping, Society, Sports a World. Kaˇzd´a z tˇechto kategori´ı je pot´e na druh´em stupni opˇet rozˇrazena do podkategori´ı atd. Hloubka nˇekter´ ych podkategori´ı m˚ uˇze b´ yt i 8. Abychom doc´ılili pojmenov´an´ı t´ematu, je nutn´e zanalyzovat kategorie pro jednotliv´e dom´eny nach´azej´ıc´ı se v dan´em t´ematu. Sjednocen´ım tˇechto kategori´ı, kter´e vznikly vyhled´an´ım dom´eny na DMOZ port´alu, lze urˇcit rozsah z´ajm˚ u dan´eho t´ematu. Pro rychlejˇs´ı zpracov´an´ı byly staˇzeny do offline pouˇzit´ı vˇsechny kategorick´e stromy“ ” pro kaˇzdou dom´enu. Jak jiˇz bylo zm´ınˇeno, tˇechto shod bylo nalezeno pouze 17 073. Protoˇze z DMOZ datab´aze lze z´ıskat jen kategorick´e um´ıstˇen´ı v ruˇcnˇe sestaven´em stromˇe kategori´ı, nelze t´ımto postupem z´ıskat konkr´etn´ı pojmenov´an´ı t´emat, ale lze zjistit nejv´ yznamnˇejˇs´ı kategorie tvoˇr´ıc´ı dan´e t´ema. Princip z´ısk´an´ı kategori´ı pro dan´e t´ema je n´asleduj´ıc´ı: 1. V´ ypoˇcet pLSA, nebo naˇcten´ı matice P (w|z) z pˇredchoz´ıho v´ ypoˇctu pLSA. 2. Naˇcten´ı kategori´ı z DMOZ pouze pro dom´eny odpov´ıdaj´ıc´ı dan´emu datasetu. 3. Sestaven´ı blok˚ u dom´en z t´ematu. Pro kaˇzd´e t´ema, tedy P (w|zi ), kde i je index t´ematu: (a) Ponech´an´ı bloku i, pokud zastoupen´ı prvn´ı dom´eny (seˇrazeno sestupnˇe) je vˇetˇs´ı neˇz 20 %7 . 4. Pro kaˇzd´ y blok dom´en: (a) V´ ypis prvn´ıch 30 dom´en (seˇrazeno sestupnˇe dle pravdˇepodobnosti P (w|zi ), jejich pravdˇepodobnost´ı v t´ematu a v´ ypis kategori´ı z DMOZ pro kaˇzdou dom´enu. (b) V´ ypis sestupnˇe seˇrazen´eho poˇctu v´ yskyt˚ u kategori´ı z prvn´ıch 30 dom´en spolu s n´azvem kategorie. Anal´ yzou tˇechto v´ ypis˚ u bylo zjiˇstˇeno, ˇze pˇri pouˇzit´ı 100 tematick´ ych blok˚ u jsou v´ ysledn´a t´emata ponˇekud obecnˇejˇs´ıho charakteru. Bylo tedy rozhodnuto o pouˇzit´ı ˇ ast v´ algoritmu pro 200 t´emat, odkud jsme dostali pˇresvˇedˇcivˇejˇs´ı v´ ysledky. C´ ysledk˚ u je zobrazena v n´asleduj´ıc´ı tabulce 4.3. V tabulce jsou zobrazena dvˇe n´ahodnˇe vybran´a t´emata. Lze rozeznat, ˇze napˇr´ıklad v prvn´ım t´ematu jsou nejv´ yznamnˇejˇs´ı webov´e 7 Hranice 20 % byla nastavena takto z d˚ uvodu, ˇze z 200 vygenerovan´ ych t´emat ne vˇsechna mˇela dostateˇcnˇe bohat´e zastoupen´ı dom´en. Nˇekter´e kategorie mˇely v´ıce rovnomˇernˇejˇs´ı distribuce, a tedy v´ yraznˇe ˇsirˇs´ı z´ ajmovou oblast.

35

str´anky zamˇeˇreny prim´arnˇe na vzdˇel´av´an´ı a sekund´arnˇe na novinky ve vojenstv´ı. V druh´em t´ematu jsou webov´e str´anky zamˇeˇreny na logistiku ˇci motorismus. Nalezen´ı pˇresn´eho a hlavnˇe jednotn´eho popisu tˇechto t´emat v z´asadˇe nelze, nebo alespoˇ n nelze dokonale. T´emata byla nalezena pomoc´ı algoritmu pLSA, kter´ y nijak nereflektuje z´avislosti slov (dom´en) mezi sebou. Vych´az´ı se pouze z matice ˇcetnost´ı. Tabulka 4.3: Kategorie z DMOZ T´ema 1 T´ema 2 Dom´ena P (w|zi ) Kategorie Dom´ena P (w|zi ) northwood.edu 57,7 % Education paccar.com 37,4 % militarytimes.com 6,7 % News state.tn.us 8,6 % fhu.edu 5,9 % Education wyoming.com 3,7 % calstate.edu 2,3 % army.mil 5,7 % News

Kategorie Trucking Logistics Regional Education

V tabulce lze vidˇet kategorie, kter´e jsou relativnˇe obecn´eho charakteru, ale jsou pomˇernˇe specifick´e. Bylo zde pouˇzito zobrazen´ı druh´e aˇz tˇret´ı podkategorie, protoˇze prvn´ı stupeˇ n kategori´ı byl v dan´em kontextu aˇz pˇr´ıliˇs obecn´ y. Prvn´ı t´ema je z´ajmovˇe pomˇernˇe u ´zk´e. Jedn´a se pravdˇepodobnˇe o studenty Northwoodsk´e univerzity z Michiganu nebo Floridy. Lid´e, kteˇr´ı navˇstˇevuj´ı str´anky t´eto vysok´e ˇskoly t´eˇz navˇstˇevuj´ı ty webov´e str´anky, kter´e se zab´ yvaj´ı novinkami ve vojenstv´ı. Toto t´ema bylo tedy nalezeno pomˇernˇe dobˇre. Ovˇsem druh´e jiˇz tak pˇresvˇedˇciv´e nen´ı. Jsou zde na prvn´ıch pˇr´ıˇck´ach str´anky o motorismu, ale s niˇzˇs´ımi pravdˇepodobnostmi a dalˇs´ı dom´eny maj´ı r˚ uznorodˇejˇs´ı charakter. Tedy toto t´ema nem˚ uˇze m´ıt jednotn´ y popis, ale je nutn´e vyuˇz´ıt k popisu vˇsechny kategorie, z nichˇz je t´ema charakterizov´ano. Bohuˇzel toto je pˇr´ıpad pomˇernˇe ˇcast´ y, protoˇze algoritmus pLSA vych´az´ı pouze z konkr´etn´ıch n´avˇstˇevnost´ı, aniˇz by nˇejak´ ym zp˚ usobem d´aval v´ahu kontextov´ ym informac´ım. V obr´azku 4.2 na dalˇs´ı str´ance lze vidˇet v´ yznamnosti vˇsech kategori´ı8 v dan´em korpusu pro 200 nalezen´ ych t´emat. Nejpoˇcetnˇejˇs´ı kategorie Regional ˇci velmi poˇcetn´a kategorie World (kter´e nejsou v grafu uk´az´any) urˇcuj´ı geografick´e um´ıstˇen´ı a jsou ˇcasto jako doplˇ nuj´ıc´ı kategori´ı u vˇetˇsiny popis˚ u dom´en. Z cca 46 % byla zastoupena severn´ı Amerika, tedy se jedn´a o oˇcek´avateln´ y v´ ysledek, protoˇze jsou data sb´ır´ana na u ´zem´ı USA. V grafu je posledn´ı kategorie nazvan´a Ostatn´ı, kter´a shlukuje ty kategorie, kter´e mˇely m´enˇe neˇz 3% v´ yznamnost. 8

Jsou zobrazeny kategorie pouze z prvn´ı vrstvy kategori´ı, tedy ty nejobecnˇejˇs´ı. To proto, ˇze v druh´e vrstvˇe celkov´ y poˇcet kategori´ı byl 258 a ve tˇret´ı vrstvˇe dokonce 1548 r˚ uzn´ ych podkategori´ı. Z tˇechto d˚ uvod˚ u pro pˇrehlednost zobrazen´ı je uk´az´ano pouze rozdˇelen´ı pro prvn´ı vrstvu kategori´ı.

36

Arts

Society

Computers

10 %

10 %

Business

9% Reference

15 %

9% 7%

Shopping

13 % 7%

6% 5% 5%

Ostatní

4%

Science

Sports Health Kids_and_Teens

Recreation

Obr´azek 4.2: Zastoupen´ı kategori´ı z DMOZ

DMOZ d´av´a v´ yznamn´ y n´ahled na kategorizaci dom´en, bohuˇzel ne vˇsechna zakategorizov´an´ı jsou u ´pln´a a spr´avn´a. Nˇekter´e kategorie, kter´e pˇr´ısluˇs´ı dan´e dom´enˇe neodpov´ıdaj´ı zcela pravdˇe. Z tohoto d˚ uvodu je vhodn´e doplnit tuto informaci o kategori´ıch jeˇstˇe o nˇejakou dalˇs´ı informaci.

4.3.2

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

Dalˇs´ı vhodnou cestou k pojmenov´an´ı t´emat m˚ uˇze b´ yt v´ ypis nejrelevantnˇejˇs´ıch slov vyskytuj´ıc´ıch se na dom´en´ach tvoˇr´ıc´ı dan´e t´ema. Protoˇze v dan´em korpusu jsou pouze dom´eny druh´eho ˇra´du, tak objektivnost cel´eho tohoto pokusu“ nen´ı vˇseˇr´ıkaj´ıc´ı. Kdy” bychom mohli analyzovat slova ze vˇsech konkr´etn´ıch URL adres, kter´e byly navˇst´ıveny uˇzivateli, tak by tato technika byla mnohem v´ yznamnˇejˇs´ı. K tomu, abychom mohli rychle pˇristupovat k jednotliv´ ym obsah˚ um je nutn´e 9 st´ahnout si HTML dokument dan´e URL adresy (dom´eny). Zpravidla se jedn´a pouze o domovskou str´anku, kter´a v nˇekter´ ych pˇr´ıpadech m˚ uˇze, ale tak´e nemus´ı obsahovat slova, kter´a jsou pro danou dom´enu typick´a. I pˇres toto riziko je ale tento experiment vhodn´ y, protoˇze pˇrid´av´a dalˇs´ı informaci slouˇz´ıc´ı k popisu dan´eho t´ematu. Kaˇzd´a 9

HyperText Markup Language.

37

URL str´anka byla staˇzena do intern´ıho u ´loˇziˇstˇe jakoˇzto HTML soubor, kde poˇcet vˇsech staˇzen´ ych dom´en byl 549 769 a zabran´e m´ısto 33,3 GB. D˚ uvodem, proˇc nebylo staˇzeno vˇsech 586 624 dom´en je takov´ y, ˇze dom´ena ve skuteˇcnosti na internetu nebyla dosaˇziteln´a. V takov´em pˇr´ıpadˇe uˇzivatel mohl navˇst´ıvit podstr´anku hostovanou na dan´e dom´enˇe, ale samotn´a domovsk´a str´anka neexistovala. Dalˇs´ımi d˚ uvody mohlo b´ yt to, ˇze dan´a str´anka byla pˇresmˇerov´ana ˇci zruˇsena. Po staˇzen´ı bylo zjiˇstˇeno, ˇze nˇekolik str´anek bylo pr´azdn´ ych ˇci obsahovaly pouze informaci o pˇresmˇerov´an´ı. Tyto str´anky nijak nepˇrisp´ıvaj´ı k nalezen´ı slov charakteristick´ ych pro dan´e t´ema, protoˇze obsah z nich z´ıskan´ y nereflektoval kontext dan´e str´anky. Z celkov´eho poˇctu 6 000 dom´en (200 t´emat × 30 nejv´ yznamnˇejˇs´ıch str´anek pro t´ema) bylo dosaˇziteln´ ych pouze 5 568. V pˇr´ıpadˇe omezen´ı na 20 % u nejv´ yznamnˇejˇs´ı dom´eny z t´ematu (viz 3a z ˇc´asti 4.3.1) z 2 880 zbylo 2 688 dom´en, kter´e na disku zab´ıraj´ı 168 MB. V´ yznamn´a slova lze z´ıskat pomoc´ı TF-IDF algoritmu. Jako dokumenty jsou zde br´any jednotliv´e obsahy z dom´en a slova jsou pomoc´ı TF-IDF vypoˇc´ıt´ana. Vznikne slovn´ık vˇsech slov10 o d´elce S, kter´a se vyskytuj´ı v dan´em t´ematu zi na obsaz´ıch webov´ ych str´anek a tak´e matice reprezentuj´ıc´ı TF-IDF hodnoty pro kaˇzd´e slovo z kaˇzd´eho dokumentu. Protoˇze kaˇzd´a webov´a str´anka m´a jinou v´ yznamnost v dan´em t´ematu, je vhodn´e pˇrev´aˇzit ˇra´dky TF-IDF matice pr´avˇe vektorem v´ yznamnosti konkr´etn´ı dom´eny: Xi

=

×

P (w|zi )

Ti 



x1 . . . xS



=



b1 . . . b30



 t1,1 . . . t1,S  . ..  ... .. ×  .    t30,1 . . . t30,S

(4.10)

kde P (w|zi ) je ˇr´adek z matice P (w|z) znaˇc´ıc´ı pravdˇepodobnosti dom´en w v dan´em t´ematu zi , Ti je TF-IDF matice pˇr´ısluˇsej´ıc´ı t´ematu i a Xi je v´ ysledn´ y vektor d´elky S. T´ımto maticov´ ym pˇrev´aˇzen´ım vznikne vektor obsahuj´ıc´ı vˇsechna v´ yznamn´a slova vyskytuj´ıc´ı se v dan´em t´ematu, kter´a jsou v´aˇzena pravdˇepodobnost´ı dom´eny. Tedy pˇr´ıkladem: pokud na prvn´ı dom´enˇe bylo slovo s1 se stejnou hodnotou TF-IDF jako slovo s2 nach´azej´ıc´ı se na druh´em dokumentu (tedy t1,1 = t2,2 , kde ale s1 6= s2 ), tak po pˇrev´aˇzen´ı x1 = b1 × t1,1 a x2 = b2 × t2,2 bude x1 > x2 , protoˇze b1 > b2 . Tedy po pˇrev´aˇzen´ı a seˇrazen´ı vektoru Xi z´ısk´ame v´ yznamn´a slova pro dan´e t´ema. 10

Je vhodn´e odstranit stop-words“ (slova, kter´a se vyskytuj´ı ˇcasto, ale nenesou v´ yznamnou in” formaci).

38

Pro doplnˇen´ı je vhodn´e poznamenat, ˇze TF-IDF transformace byla provedena na obsaz´ıch dom´en jednoho t´ematu, ale tak´e na obsaz´ıch vˇsech dom´en. Z obsah˚ u vˇsech dom´en vznikl velk´ y slovn´ık slov11 , ze kter´eho byly vyp˚ ujˇceny hodnoty IDF (inverzn´ı hodnota v´ yskytu slova napˇr´ıˇc vˇsemi dokumenty), kter´e byly nahrazeny m´ısto IDF vypoˇc´ıtan´ ych napˇr´ıˇc t´ematem. T´ımto jsme dos´ahli lepˇs´ı v´aˇzenosti TF-IDF hodnoty slova. Pouˇzit´ım glob´aln´ıch“ 12 hodnot IDF byla v´ yznamnost jednotliv´ ych slov vyhod” nocena v r´amci v´ yznamnosti slova pˇres cel´ y dataset a nikoli jen pˇres dan´e t´ema. Ve v´ ysledku tyto dvˇe metody v´ ypoˇctu TF-IDF matice pod´avaly v´ıcem´enˇe stejnˇe z´avˇery, protoˇze nejv´ yznamnˇejˇs´ı roli v pˇrev´aˇzen´ı slov hraj´ı jednotliv´e pravdˇepodobnosti dom´en v t´ematu. N´ıˇze je uk´azka nalezen´ ych v´ yznamn´ ych slov pro t´emata z tabulky 4.3: Tabulka 4.4: Nejv´ yznamnˇejˇs´ı slova dle obsah˚ u str´anek T´ema 1 V´ yznamn´e slovo university business school programs college

T´ema 2 V´ yznamn´e slovo news global careers services transportation

X1 0,357 0,197 0,143 0,132 0,110

X2 0,179 0,104 0,083 0,064 0,024

V prvn´ım sloupeˇcku (T´ema 1) jsou v´ yznamn´a slova jasnˇe ukazuj´ıc´ı ˇskoln´ı prostˇred´ı. To proto, ˇze nejvˇetˇs´ı pravdˇepodobnost v tomto t´ematu mˇela Northwoodsk´a univerzita, a tedy nejv´ yznamnˇejˇs´ı slova poch´azej´ı pr´avˇe ze str´anek t´eto univerzity. V seznamu d´ale pot´e byla slova jako military, kter´a ukazovala na z´ajem t´ematu i v t´eto oblasti. V druh´em t´ematu (T´ema 2) jsou pˇrev´aˇznˇe slova, kter´a odpov´ıdaj´ı slov˚ um na str´ance paccar.com, kter´a se zab´ yv´a prodejem a dalˇs´ımi sluˇzbami ohlednˇe logistick´ ych kamion˚ u. Ze seznamu nejv´ yznamnˇejˇs´ıch slov je pomˇernˇe sloˇzit´e jasnˇe odhadnout zamˇeˇren´ı t´ematu, ale pˇri posouzen´ı vˇetˇs´ıho poˇctu v´ yznamn´ ych slov lze usuzovat, ˇze se jedn´a o t´ema nab´ızej´ıc´ı sluˇzby ohlednˇe kamionov´e dopravy. Za povˇsimnut´ı t´eˇz stoj´ı i v´ yraznˇe menˇs´ı hodnoty X2 u druh´eho t´ematu oproti hodnot´am X1 z t´ematu prvn´ıho. To je pravdˇepodobnˇe zp˚ usobeno ˇsirˇs´ım z´ajmov´ ym okruhem dan´eho t´ematu, nebot’ Northwoodsk´a univerzita tvoˇrila z 57,7 % T´ema 1, ale str´anka paccar.com tvoˇrila T´ema 2 jen z 37,4 %. Z t´eto dedukce lze uvaˇzovat nad jednotn´ ym mˇeˇr´ıtkem ˇs´ıˇre z´ajmu dan´eho t´ematu a to napˇr´ıklad pomoc´ı entropie, kter´a urˇcuje 11

V nijak neomezen´em poˇctu bylo pˇres 16 milion˚ u slov, kter´e ale mˇely dost ˇsumu“, kter´ y bylo ” nutn´e odstranit. 12 Myˇsleno glob´ aln´ı v r´ amci datasetu dom´en.

39

ˇ ım menˇs´ı je entropie t´ematu, t´ım je uˇzˇs´ı z´ajem dan´eho t´ematu, informaˇcn´ı hodnotu. C´ nebot’ zde existuj´ı takov´e dom´eny, kter´e maj´ı vysokou pravdˇepodobnost a jsou tedy pro dan´e t´ema v´ıce charakteristick´e. H(P (w|zi )) = −

30 X

P (wj |zi ) · log2 (P (wj |zi ))

(4.11)

j=1

kde H(P (w|zi )) je entropie dan´eho t´ematu i a kde P (wj |zi ) je pravdˇepodobnost dom´eny v t´ematu. Entropie T´ematu 1 je 1,4172 a T´ematu 2 je 2,2841, coˇz souhlas´ı s t´ım, ˇze T´ema 2 m´a ˇsirˇs´ı z´ajmovou skupinu, neˇz T´ema 1, protoˇze m´a niˇzˇs´ı pravdˇepodobnosti dom´en, kter´e dan´e T´ema 2 tvoˇr´ı.

2.5

entropie

2.0

1.5

1.0

0.5

0

5

10

15

20

25

vyhovující téma

30

35

40

45

Obr´azek 4.3: Hodnoty entropie napˇr´ıˇc vyhovuj´ıc´ımi t´ematy

Pomˇer u ´zce zamˇeˇren´ ych t´emat definuj´ıc´ıch nejv´ yznamnˇejˇs´ı dom´enou je pˇribliˇznˇe podobn´ y poˇctu t´emat ˇs´ıˇreji zamˇeˇren´ ych. Tento fakt lze vyˇc´ıst i z obr´azku 4.3, kde vid´ıme sestupnˇe seˇrazen´e hodnoty entropi´ı pro vˇsechna t´emata, kter´a vyhovuj´ı podm´ınk´am 3a z ˇc´asti 4.3.1. Pˇri zpˇr´ısnˇen´ı tˇechto podm´ınek lze vyselektovat t´emata s mnohem niˇzˇs´ı entropi´ı, a tedy s uˇzˇs´ım zamˇeˇren´ım.

40

4.4

Fin´ aln´ı v´ ysledky

Aplikac´ı krok˚ u zm´ınˇen´ ych v t´eto kapitole 4 jsme z´ıskali seznam t´emat, kter´a se skl´adala z distribuc´ı dom´en. Tato t´emata jsme pot´e popsali pomoc´ı kategori´ı z DMOZ datab´aze a n´aslednˇe pomoc´ı jednotliv´ ych obsah˚ u webov´ ych str´anek jsme z´ıskali v´ yznamn´a slova charakteristick´a pro dan´e t´ema. V´ ysledkem tˇechto krok˚ u je postup, d´ıky kter´emu lze z´ıskat kategorie webov´ ych str´anek. Ideou pr´ace byla p˚ uvodnˇe ale kategorizace uˇzivatel˚ u na z´akladˇe jejich proch´azen´ı internetu. Tato idea bohuˇzel nen´ı z poskytnut´ ych dat provediteln´a u ´plnˇe, 13 vzhledem k tomu, ˇze jsme dostali data jiˇz znaˇcnˇe omezen´a . Z poskytnut´ ych dat nen´ı moˇzn´e dokonale analyzovat z´ajmy populace, lze ale vyuˇz´ıt poznatky k sestaven´ı postupu pln´e anal´ yzy. Hlavn´ım probl´emem je pojmenov´an´ı t´emat. Bez jak´ekoli bliˇzˇs´ı znalosti o konkr´etn´ıch uˇzivatel´ıch neum´ıme za dan´ ych podm´ınek pojmenovat nalezen´a t´emata z´ajmovˇe ˇci dokonce demograficky. M´ısto pojmenov´an´ı t´emat je v t´eto pr´aci zm´ınˇen popis t´emat pomoc´ı kategori´ı webov´ ych str´anek z DMOZ datab´aze, kter´e bohuˇzel nejsou dostateˇcnˇe pˇresn´e. D´ale pomoc´ı slov charakteristick´ ych pro obsahy domovsk´ ych str´anek pˇr´ıstupn´ ych na poskytnut´ ych dom´en´ach. Aby bylo moˇzn´e pojmenov´an´ı nalezen´ ych t´emat z´ajmovˇe ˇci demograficky, je nutn´e pˇrid´an´ı dalˇs´ı popisn´e sloˇzky k uˇzivatel˚ um a z´ uˇzit ˇra´d dom´en. Nyn´ı jsou nalezen´a t´emata charakteristick´a pro nˇejakou“ skupinu populace. Tuto skupinu um´ıme cha” rakterizovat pomoc´ı distribuc´ı dom´en, a ty um´ıme popsat pomoc´ı kategorie dom´eny. Tak´e um´ıme popsat t´ema pomoc´ı slov specifick´ ych pro danou skupinu dom´en. Chyb´ı zde ale informace o popisu uˇzivatele. Abychom mohli popsat nalezen´ a t´ emata napˇ r´ıklad pomoc´ı z´ ajm˚ u, potˇ rebujeme zn´ at z´ ajmy alespoˇ n nˇ ekolika m´ alo uˇ zivatel˚ u, kteˇ r´ı jsou charakteristiˇ ct´ı pro dan´ e t´ ema. Z algoritmu pLSA lze z´ıskat P (z|d), coˇz jsou distribuce nalezen´ ych t´emat pro jednotliv´e uˇzivatele. Popˇr´ıpadˇe pomoc´ı metody folding-in vysvˇetlen´e v ˇca´sti 3.3.5 lze um´ıstit nov´e uˇzivatele do jiˇz natr´enovan´eho prostoru t´emat. Kaˇzd´ y uˇzivatel je pops´an distribuc´ı t´emat. Pokud bychom znali bliˇzˇs´ı z´ajmov´e informace o konkr´etn´ıch uˇzivatel´ıch, mohli bychom tyto z´ajmy dle pravdˇepodobnost´ı t´emat prom´ıtnout do konkr´etn´ıch t´emat, a t´ım zpˇresnit jejich popis. Tot´eˇz plat´ı i pro demografick´e 13 Z p˚ uvodn´ıho clickstreamu byla vytvoˇrena matice ˇcetnost´ı, ˇc´ımˇz se zanonymizovala informace o pr˚ ubˇeˇzn´em pr˚ uchodu uˇzivatele internetem. D´ale byly konkr´etn´ı URL adresy omezeny pouze na dom´eny 2. ˇr´ adu, ˇc´ımˇz t´emˇeˇr zmizela informace o konkr´etn´ıch z´ajmech uˇzivatele na specifick´e URL adrese. Tato informace byla zredukov´ana pouze na dom´enu, kter´a ale nemus´ı b´ yt jako celek dostateˇcnˇe subjektivn´ı vzhledem k z´ ajm˚ um uˇzivatele.

41

informace. Pˇr´ıkladem: vˇedˇeli bychom, ˇze uˇzivatel U1 m´a rozloˇzen´ı pravdˇepodobnost´ı t´emat T´ema 1: 35 %, T´ema 2: 5 %, T´ema 3: 60 % a vˇedˇeli bychom, ˇze uˇzivatel U1 je 35let´ y svobodn´ y muˇz pracuj´ıc´ı jako u ´ˇcetn´ı a bydl´ıc´ı v Praze v Dejvic´ıch a se z´ajmem hraje volejbal a chod´ı plavat, tak bychom vˇsechny tyto informace mohli prom´ıtnout dle pravdˇepodobnost´ı do jednotliv´ ych t´emat. Na z´akladˇe urˇcit´e popsan´e skupiny uˇzivatel˚ u bychom mohli z´ıskat dostateˇcn´ y popis t´emat v podobˇe demografick´ ych ˇci z´ajmov´ ych oblast´ı. Z tˇechto informac´ı by pot´e bylo moˇzn´e takov´e t´ema pojmenovat. Kaˇzd´e t´ema by bylo pops´ano jist´ ymi pravdˇepodobnostmi uˇzivatelov´ ych popisn´ ych informac´ı a prost´ ym pˇrev´aˇzen´ım tˇechto informac´ı by bylo moˇzn´e dokonce pojmenovat dan´e t´ema. Pokud by napˇr´ıklad nˇejak´e t´ema bylo charakteristick´e pro nˇekolik uˇzivatel˚ u, kteˇr´ı jsou sportovci, lze o takov´em t´ematu ˇr´ıci, ˇze je zamˇeˇreno na ˇ ych uˇzivatel˚ u, t´ım lepˇs´ı popisn´ y model bychom mohli sport. C´ım v´ıce by bylo popsan´ z´ıskat. Moment´alnˇe jsme doˇcista bez t´eto informaˇcn´ı hodnoty, a tedy ˇra´dn´e pojmenov´an´ı t´emat na z´akladˇe z´ajm˚ u ˇci obecnˇe popisu uˇzivatele nen´ı uskuteˇcniteln´e za dan´ ych podm´ınek.

42

Kapitola 5 Z´ avˇ er Tato pr´ace se zab´ yv´a popisem metod vhodn´ ych ke kategorizaci webov´ ych str´anek charakteristick´ ych pro urˇcitou skupinu populace na z´akladˇe jejich chov´an´ı. T´ımto chov´an´ım je myˇsleno navˇstˇevov´an´ı dom´en na internetu. Pro tuto pr´aci byla poskytnuta zanonymizovan´a data vych´azej´ıc´ı z re´aln´ ych z´aznam˚ u proch´azen´ı internetu uˇzivateli USA za dobu jednoho mˇes´ıce. Tato data jsou ve form´atu matice ˇcetnost´ı, nad kterou je prov´adˇen cel´ y v´ yzkum. Prvnˇe bylo nutn´e data zanalyzovat a pot´e redukovat m´enˇe d˚ uleˇzit´e ˇca´sti dat, aby vynikly ˇc´asti s vˇetˇs´ı vypov´ıdaj´ıc´ı hodnotou. Touto redukc´ı byla p˚ uvodn´ı matice ˇcetnost´ı o rozmˇerech 224 679 uˇzivatel˚ u × 586 624 URL redukov´ana na 191 676 uˇzivatel˚ u × 37 441 URL pˇri zachov´an´ı a zv´ yraznˇen´ı diskriminuj´ıc´ıch dat. N´aslednˇe byl zvolen tzv. topic-model algoritmus pLSA, kter´ y dok´aˇze naj´ıt P (w|z) popisuj´ıc´ı pravdˇepodobnosti dom´en w pro nalezen´a t´emata z a P (z|d) popisuj´ıc´ı pravdˇepodobnosti t´emat charakterizuj´ıc´ıch konkr´etn´ı uˇzivatele d. Vhodn´a implementace tohoto algoritmu nebyla, a tedy bylo nutn´e algoritmus reimplementovat, aby byl schopn´ y v rozumn´em ˇcase s rozumn´ ymi prostˇredky dodat v´ ysledky pro poskytnut´a data. Po nalezen´ı t´emat popisuj´ıc´ıch uˇzivatele pomoc´ı dom´en bylo vhodn´e tato t´emata nˇejak´ ym zp˚ usobem pojmenovat. Z d˚ uvodu nedostateˇcn´eho popisu uˇzivatel˚ u bylo nutn´e pˇristoupit k popisu t´emat pomoc´ı jin´ ych popisn´ ych metod. Byla pouˇzita nejvˇetˇs´ı ruˇcnˇe tvoˇren´a datab´aze kategori´ı webov´ ych str´anek DMOZ, u kter´e se pozdˇeji zjistilo, ˇze nˇekter´e popisy dom´en pomoc´ı kategori´ı neodpov´ıdaj´ı skuteˇcnosti. Popis t´emat byl proto doplnˇen o seznamy charakteristick´ ych slov z´ıskan´ ych z obsah˚ u webov´ ych str´anek. V´ ysledkem je postup vedouc´ı k nalezen´ı t´emat kategorizuj´ıc´ıch uˇzivatele pomoc´ı t´emat, kter´a jsou kategorizov´ana pomoc´ı dom´en. C´ılem pr´ace bylo pops´an´ı metod vedouc´ıch k nalezen´ı skupin webov´ ych str´anek, kter´e jsou pro urˇcitou skupinu populace charakteristick´e. Tento c´ıl se do jist´e m´ıry 43

podaˇrilo splnit pomoc´ı t´emat charakterizuj´ıc´ıch jednotliv´e uˇzivatele pomoc´ı dom´en, pˇriˇcemˇz v´ ysledn´e pojmenov´an´ı nalezen´ ych t´emat nebylo moˇzn´e z d˚ uvodu nedostateˇcn´eho popisu uˇzivatel˚ u. M´ısto pojmenov´an´ı t´emat byla tato t´emata pops´ana pomoc´ı obecn´ ych kategori´ı z DMOZ datab´aze a pomoc´ı slov charakteristick´ ych pro dom´eny obsaˇzen´e v t´ematech. Pˇri dod´an´ı dodateˇcn´ ych popisn´ ych informac´ı o uˇzivatel´ıch je moˇzn´e na z´akladˇe t´eto pr´ace pojmenovat t´emata shlukuj´ıc´ı jist´e ˇc´asti populace. Charakter popisn´ ych dat urˇc´ı popisn´e schopnosti pˇri pojmenov´an´ı t´emat. Tato pr´ace m˚ uˇze slouˇzit jako v´ ychoz´ı bod pˇri hled´an´ı kategori´ı popisuj´ıc´ıch uˇzivatele internetu, popˇr´ıpadˇe jako studijn´ı materi´al ukazuj´ıc´ı vyuˇzit´ı r˚ uzn´ ych metod kategorizace.

44

Pˇ r´ıloha A Obsah pˇ riloˇ zen´ eho CD latex-src/ Zdrojov´e soubory pro LATEX k t´eto pr´aci. source-code/ Implementace algoritm˚ u v Pythonu. Jencik-thesis-2015.pdf Tato pr´ace v elektronick´e podobˇe.

45

Literatura [1] BAHMANI, Bahman; MOSELEY, Benjamin; VATTANI, Andrea; KUMAR, Ravi a VASSILVITSKII, Sergei. Scalable K-means++. Standford University, CA [online]. Posledn´ı aktualizace 2012 [cit. 2015-04-26]. Dostupn´e z: http: //vldb.org/pvldb/vol5/p622_bahmanbahmani_vldb2012.pdf. [2] CHEN, Ting. Notes on EM and pLSA. Dataera [online]. Posledn´ı aktualizace 1. 4. 2014 [cit. 2015-04-26]. Dostupn´e z: http://dataera.org/2014/04/noteson-em-and-plsa/. [3] DEMPSTER, A. P.; LAIRD, M. a RUBIN, D. B. Maximum Likelihood from Incomplete Data via the EM Algorithm. Journal of the Royal Stastistical Society. Series B, volume 39. MIT [online]. Posledn´ı aktualizace 1977 [cit. 2015-04-26]. Dostupn´e z: http://web.mit.edu/6.435/www/Dempster77.pdf. [4] DMOZ. Open Directory Project. AOL Inc. [online]. Posledn´ı aktualizace 26. 4. 2015 [cit. 2015-05-14]. Dostupn´e z: http://www.dmoz.org. [5] ESTER, Matrin; KRIEGEL, Hans-Peter; SANDER, J¨org a XU, Xiaowei. A Density-Based algorithm for Discovering Clusters. Institute for Computer Science, University of Munich, Germany [online]. Posledn´ı aktualizace 1996 [cit. 2015-05-16]. Dostupn´e z: https://www.aaai.org/Papers/KDD/1996/KDD96037.pdf. [6] FARAHAT, Ayman a CHEN, Francine. Improving Probabilistic Latent Semantic Analysis with Principal Component Analysis. A Digital Archive of Research Papers in Computational Linguistics [online]. [cit. 2015-04-27]. Dostupn´e z: http://www.aclweb.org/anthology/E06-1014. [7] HOFMANN, Thomas. Probabilistic Latent Semantic Analysis. Uncertainity in Artificial Intelligence, University of California, Berkeley & International Computer Science Institute, Berkeley, CA [online]. Posledn´ı aktualizace 1999 [cit. 201504-26]. Dostupn´e z: http://cs.brown.edu/~th/papers/Hofmann-UAI99.pdf. [8] HOFMANN, Thomas. Probabilistic Latent Semantic Indexing. International Computer Science Institute, Berkeley, CA [online]. Posledn´ı aktualizace 1999 [cit. 2015-04-27]. Dostupn´e z: http://cs.brown.edu/~th/papers/HofmannSIGIR99.pdf. 46

[9] HOFMANN, Thomas; PUZICHA, Jan a JORDAN, Michael I. Unsupervised learning from Dyadic Data. Advances in Neural Information Processing Systems, volume 11. MIT Press [online]. Posledn´ı aktualizace 1999 [cit. 2015-04-26]. Dostupn´e z: http://www.cs.berkeley.edu/~jordan/papers/dyadic.pdf. [10] JONES, Eric; OLIPHANT, Travis; PETERSON, Pearu a dalˇs´ı. SciPy: Open source scientific tools for Python. scikit-learn [online]. Posledn´ı aktualizace 2015 [cit. 2015-05-16]. Dostupn´e z: http://www.scipy.org. [11] KANUNGO, Tapas a ostatn´ı. An Efficient k-Means Clustering Algorithm: Analysis and Implementation. Pattern Analysis and Machine Intelligence, IEEE Transaction (2002): 881-892 [online]. Posledn´ı aktualizace 2002 [cit. 2015-02-17]. Dostupn´e z: https://www.cs.umd.edu/~mount/Projects/ KMeans/pami02.pdf. [12] KAUCHAK, David. TF-IDF. Standford University, CA [online]. Posledn´ı aktualizace 2009 [cit. 2015-02-17]. Dostupn´e z: http://www.cs.pomona.edu/ ~dkauchak/classes/f09/cs160-f09/lectures/lecture5-tfidf.pdf. [13] KONG, Alex. pLSA implementace v Pythonu. GitHub, Inc. [online]. Posledn´ı aktualizace 6. 10. 2012 [cit. 2015-05-02]. Dostupn´e z: https://github. com/dx88968/PLSA-1. [14] MOE, Wendy W. a FADER, Peter S. Capturing evolving visit behavior in clickstream data. Journal of interactive marketing, volume 18, number 1 [online]. Posledn´ı aktualizace 2004 [cit. 2015-04-18]. Dostupn´e z: https://marketing. wharton.upenn.edu/files/?whdmsaction=public:main.file&fileID=3817. [15] MONTGOMERY, Alan. Predicting Consumer Behavior using Clickstream Analysis. Carnegie Mellon University [online]. Posledn´ı aktualizace 13. 6. 2003 [cit. 2015-02-17]. Dostupn´e z: http://www.andrew.cmu.edu/user/ alm3/presentations/WebShop%202003.pdf. ¨ [16] MORIK, Katharina a KOPCKE, Hanna. Analysing Insurance Data or The Advantage of TF/IDF Features. University of Dortmund, DE [online]. [cit. 201504-19]. Dostupn´e z: https://km.aifb.kit.edu/ws/LLWA/akkd/2.pdf. [17] PEDREGOSA, F.; VAROQUAUX, G.; GRAMFORT, A.; MICHEL, V.; THIRION, B.; GRISEL, O.; BLONDEL, M.; PRETTENHOFER, P.; WEISS, R.; DUBOURG, V.; VANDERPLAS, J.; PASSOS, A.; COURNAPEAU, D.; BRUCHER, M.; PERROT, M. a DUCHESNAY, E. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research, 12:2825–2830, 2011. [18] scikit-learn. K-means implementace v Pythonu. scikit-learn [online]. Posledn´ı aktualizace 25. 3. 2015 [cit. 2015-05-16]. Dostupn´e z: http://scikit-learn.org/ stable/modules/generated/sklearn.cluster.KMeans.html.

47

[19] scikit-learn. Mini Batch K-means implementace v Pythonu. scikit-learn [online]. Posledn´ı aktualizace 25. 3. 2015 [cit. 2015-05-16]. Dostupn´e z: http://scikit-learn.org/stable/modules/generated/sklearn.cluster. MiniBatchKMeans.html. [20] SCULLEY, D. Web-Scale K-means Clustering. Google, Inc. Pittsburgh. PA USA [online]. Posledn´ı aktualizace 20. 4. 2010 [cit. 2015-05-16]. Dostupn´e z: http: //www.eecs.tufts.edu/~dsculley/papers/fastkmeans.pdf. [21] SEBERA, Martin. Anal´ yza hlavn´ıch komponent a faktorov´a anal´ yza. V´ıcerozmˇern´e statistick´e metody, Masarykova universita [online]. Posledn´ı aktualizace 13. 1. 2012 [cit. 2015-04-20]. Dostupn´e z: http://www.fsps.muni.cz/ ~sebera/vicerozmerna_statistika/pca.html. [22] STEYVERS, Mark a GRIFFITHS, Tom. Probabilistic Topic Models. University of California, Irvine; Brown University [online]. [cit. 201504-26]. Dostupn´e z: http://psiexp.ss.uci.edu/research/papers/ SteyversGriffithsLSABookFormatted.pdf. [23] SUKHWANI, Sumit; GARLA, Satish a CHAKRABORTY, Goutam. Analysis of Clickstream Data Using SAS. Oklahoma State University, Stillwater, UK [online]. Posledn´ı aktualizace 2012 [cit. 2015-02-17]. Dostupn´e z: http: //support.sas.com/resources/papers/proceedings12/100-2012.pdf. [24] TURNEY, Peter D. a PANTEL, Patrick. From Frequency to Meaning: Vector Space Models of Semantics. Journal of Artificial Intelligence Research 37 (2010) 141–188 [online]. Posledn´ı aktualizace 2010 [cit. 2015-02-17]. Dostupn´e z: https: //www.jair.org/media/2934/live-2934-4846-jair.pdf. [25] WANG, Kaijun; ZHANG, Junying; LI, Dan; ZHANG, Xinna a GUO, Tao. Adaptive Affinity Propagation Clusterint. China Jiliang College, Xidian University, China [online]. Posledn´ı aktualizace 2007 [cit. 2015-05-16]. Dostupn´e z: http://arxiv.org/pdf/0805.1096.pdf. ˇ [26] WERNER, Tom´aˇs. Optimalizace. CVUT [online]. Posledn´ı aktualizace 19. 12. 2014 [cit. 2015-04-20]. Dostupn´e z: https://cw.fel.cvut.cz/wiki/ _media/courses/a4b33opt/opt.pdf. [27] WIKIPEDIA. Cosine similarity. Wikipedia [online]. Posledn´ı aktualizace 17. 3. 2015 [cit. 2015-04-26]. Dostupn´e z: http://en.wikipedia.org/wiki/ Cosine_similarity. [28] WIKIPEDIA. K-means clustering. Wikipedia [online]. Posledn´ı aktualizace 7. 4. 2015 [cit. 2015-04-26]. Dostupn´e z: http://en.wikipedia.org/wiki/Kmeans_clustering. [29] WIKIPEDIA. Latent semantic analysis. Wikipedia [online]. Posledn´ı aktualizace 25. 4. 2015 [cit. 2015-04-26]. Dostupn´e z: http://en.wikipedia.org/wiki/ Latent_semantic_analysis. 48

[30] WIKIPEDIA. Natural language processing. Wikipedia [online]. Posledn´ı aktualizace 18. 4. 2015 [cit. 2015-04-26]. Dostupn´e z: http://en.wikipedia.org/wiki/ Natural_language_processing. [31] WIKIPEDIA. Principal component analysis. Wikipedia [online]. Posledn´ı aktualizace 10. 4. 2015 [cit. 2015-04-20]. Dostupn´e z: http://en.wikipedia.org/ wiki/Principal_component_analysis. ˇ ´ Alena. Metody extrakce faktor˚ [32] SKALOUDOV A, u. Faktorov´a anal´yza [online]. Posledn´ı aktualizace 2010 [cit. 2015-04-20]. Dostupn´e z: http://kps.pedf. cuni.cz/skalouda/fa/extrakce_fak.htm.

49

Pouˇ zit´ e zkratky URL Uniform Resource Locator. Unik´atn´ı webov´a adresa. CSR Compressed Storrage Row. Standardn´ı form´at pro ukl´ad´an´ı ˇr´ıdk´ ych matic. Jsou uloˇzeny pouze nenulov´e hodnoty. TF-IDF Term Frequency - Inverse Document Frequency. K-means Shlukovac´ı algoritmus. PCA Principal Component Analysis. SVD Singular Value Decomposition. LSA Latent Semantic Analysis. pLSA Probabilistic Latent Semantic Analysis. EM Expectation–Maximization. DMOZ The Open Directory Project (ODP), nejvˇetˇs´ı lidmy budovan´ y katalog internetov´ ych str´anek. HTML HyperText Markup Language.

50