České vysoké učení technické v Praze Fakulta elektrotechnická Katedra počítačů. Bakalářská práce. Adaptivní algoritmy. Jiří Hlinka

České vysoké učení technické v Praze Fakulta elektrotechnická Katedra počítačů

Bakalářská práce

Adaptivní algoritmy Jiří Hlinka

Vedoucí práce: Ing. Martin Balík

Studijní program: Softwarové technologie a management, strukturovaný bakalářský Obor: Web a multimedia 15. květen, 2010

ii

Poděkování: Velmi rád bych poděkoval vedoucímu bakalářské práce Ing. Martinu Balíkovi za cenné rady a pravidelnou motivaci k tvorbě bakalářské práce. Poděkování si také zaslouží celá moje rodina za poskytnuté zázemí. iii

iv

Prohlášení: Prohlašuji, že jsem práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu §60 Zákona č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon).

V Praze dne 15.5. 2010

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

v

vi

Abstrakt Bakalářská práce se zabývá metodami tvorby adaptivního webu. Nejprve popisuje tři vybrané adaptivní algoritmy Decision Trees, Bayesian networks a zvláště K-means, který bude dále implementován pro účely aplikace. Adaptaci umožňuje vybudování uživatelských modelů v relační databázi a to na základě jejich identifikace buď pomocí přihlašování či sessionalizace jejich aktivit. Cílem práce je navrhnout webovou aplikaci v jazyku Java, která umožní sledovat změny chování uživatelů a na kterém se ověří teoretická část bakalářské práce.

Abstract The bachelor thesis deals with methods for adaptive web creation. First it describes three chosen algorithms - Decision Trees, Bayesian network and especially K-means, which was implemented for the application needs. Adaptation is based on a user model stored in a relational database, where the model is identified by logging the user in or by a sessionalization process. The aim of the work was to design and implement in the Java language an application that allows observing user‘s behavior changes to verify the theoretical part of this bachelor thesis.

vii

Obsah Úvod.............................................................................................................................................................1 1.

Data mining.........................................................................................................................................2 1.1.

Decision trees...............................................................................................................................2

1.1.1.

Trénování stromu podle ID3 ...............................................................................................4

1.1.2.

Entropie...............................................................................................................................4

1.1.3.

Information gain..................................................................................................................5

1.1.4.

ID3 algoritmus na učení Decision tree................................................................................6

Algoritmus na učení stromu je podobný algoritmu na jeho používání s tím rozdílem, že se mohou vytvářet větve a uzly pro hodnoty, které nelze zatím vhodně třídit......................................................6 1.1.5.

Problémy s daty při ID3 ......................................................................................................7

1.1.6.

UC4.5 ..................................................................................................................................8

1.2.

K-means .......................................................................................................................................9

1.2.1.

Loyd's algorithm ...............................................................................................................10

1.2.2.

K-means++........................................................................................................................10

1.3.

Bayesovské sítě..........................................................................................................................11

1.3.1. 1.3.1.1.

Bayesův vzorec.........................................................................................................12

1.3.1.2.

Aplikace Bayesova vzorce .......................................................................................13

1.3.2. 2.

Úplná pravděpodobnost ....................................................................................................12

Bayesovské sítě .................................................................................................................14

Adaptivní web ...................................................................................................................................15 2.1.

Zdroje informací pro adaptivní web ..........................................................................................16

2.1.1. 2.1.1.1. 2.1.2.

2.2.

Webové logy .....................................................................................................................16 Postup při sessionalizaci...........................................................................................18 Obsah webové stránky ......................................................................................................19

2.1.2.1.

Textový obsah ..........................................................................................................20

2.1.2.2.

Hypertextové odkazy................................................................................................20

Uchování informací ...................................................................................................................21

2.2.1.

Modely datových úložišť ..................................................................................................22

2.2.1.1.

Cube model...............................................................................................................22

2.2.1.2.

Star model.................................................................................................................22

2.2.1.3.

Pattern Repository ....................................................................................................23

2.3.

Adaptivní algoritmy...................................................................................................................23

2.4.

Postup personifikace webu ........................................................................................................24

2.4.1.

Databáze WIR ...................................................................................................................24

2.4.2.

Tvorba modelu uživatele...................................................................................................26

2.4.3.

Zpracování obsahu stránky ...............................................................................................26

viii

3.

2.4.4.

Analýza uživatelské navigace ...........................................................................................27

2.4.5.

Analýza podobnosti webových stránek......................................................................27

2.4.6.

Změny na webu..............................................................................................................28

Aplikace.............................................................................................................................................29 3.1.

Struktura aplikace ......................................................................................................................29

3.1.1. 3.1.1.1.

TextVector................................................................................................................30

3.1.1.2.

RatingVector ............................................................................................................31

3.1.1.3.

NavigationVector .....................................................................................................31

3.1.1.4.

Centroid....................................................................................................................32

3.1.1.5.

ClusteringAlgorithm.................................................................................................32

3.1.1.6.

TextVectorBuilder....................................................................................................33

3.1.2.

3.2. 4.

5.

WordVectorCreation.........................................................................................................30

WebAdaptation .................................................................................................................33

3.1.2.1.

Views........................................................................................................................34

3.1.2.2.

Registrace .................................................................................................................34

3.1.2.3.

Přihlašování - původní..............................................................................................34

3.1.2.4.

Přihlašování – nová verze.........................................................................................35

3.1.2.5.

Odhlašování..............................................................................................................36

3.1.2.6.

Hodnocení fotek .......................................................................................................36

3.1.2.7.

Navigace...................................................................................................................38

3.1.2.8.

Adaptace...................................................................................................................38

3.1.2.9.

Adaptace hodnocení .................................................................................................39

3.1.2.10.

Adaptace navigace....................................................................................................40

Databáze ....................................................................................................................................41

Testování ...........................................................................................................................................43 4.1.

Adaptace galerie podle popisu...................................................................................................43

4.2.

Adaptace galerie podle podobnosti uživatelů ............................................................................45

4.3.

Adaptace navigace podle obsahu...............................................................................................47

4.4.

Adaptace navigace podle podobnosti uživatelů.........................................................................48

4.5.

Testování reálných uživatelů .....................................................................................................50

Závěr..................................................................................................................................................51

Použité zdroje ............................................................................................................................................52 Obsah CD...................................................................................................................................................53

ix

Seznam obrázků Obrázek 1:Schéma Decision tree podle [2] .....................................................................................3 Obrázek 2: Průběh entropie pro binární klasifikaci [10] .................................................................5 Obrázek 3: a) vektory na začátku b) náhodné vybrání centroidů c-d) postupná klasifikace vektorů a updatování centroidů .........................................10 Obrázek 4: Web Site a jeho hyperlinková struktura [8] ...............................................................21 Obrázek 5: WIR - Cube model [8] ................................................................................................22 Obrázek 6: WIR - Star model [8] ..................................................................................................23 Obrázek 7: Model webu pomocí modelu Star WIR ......................................................................25 Obrázek 8: Model uživatele pomocí Star WIR .............................................................................25 Obrázek 9: Diagram případů užití (Use Case diagram) aplikace ..................................................29 Obrázek 10: Model nasazení (deployment diagram) aplikace ......................................................30 Obrázek 11: Test distribuce všech fotek mezi klustery v závislosti na počtu uživatelů ...............44 Obrázek 12: Test distribuce fotek z jedné kategorie mezi klustery...............................................45 Obrázek 13: Závislost optimálního počtu klusterů hodnocení na počtu uživatelů........................46 Obrázek 14: Závislost optimálního počtu klusterů obsahu článků na počtu uživatelů .................48 Obrázek 15: Závislost optimálního počtu klusterů navigace na počtu uživatelů .........................49

x

Seznam tabulek Tabulka 1: Pravděpodobnostní rozdělení, zdroj [9] ......................................................................14 Tabulka 2: Příklad webového logu ze droje [2] ............................................................................17 Tabulka 3: Navigační clustery , zdroj [2] ......................................................................................28 Tabulka 4: Struktura aplikace WebAdaptation .............................................................................33 Tabulka 5: Pět uměle vytvořených modelových uživatelů............................................................43

xi

Úvod Adaptivní algoritmy jsou algoritmy, které mění své chování na základě získaných dat a účelu, nežli byly konstruovány [1] . Pomocí těchto algoritmů se vytváří aplikace, které tak automaticky zlepšují své uspořádání a prezentaci učením se z uživatelova vzoru chování. K tomu se používá kombinace omezené umělé inteligence, modelu uživatele a algoritmů k dolování dat [2].

Účelem nacházení zákonitostí a vzorů v lidském chování je přesnější předpověď dalšího kroku uživatele. Zjištěním jeho záměru můžeme usnadnit nacházení toho, co hledá či doporučit něco podobného, co by ho zaujalo. Proces adaptace může urychlovat a zefektivňovat uživateli práci či na druhou stranu nabízet více zábavy. Je to adaptace obsahu, co zapříčinilo vzestup oblíbenosti webů jako jsou youtube.com či metaface.com.

Přestože mnohdy efektivní jsou i jednoduchá doporučení a adaptace založená na statistických metodách, zde budou popsány o něco složitější algoritmy založené na metodách dolování dat. Avšak výsledná aplikace nebude zacházet natolik daleko, aby měnila svojí strukturu ani provázanost webových stránek. Bude se držet pouze doporučení odkazů a obsahu.

1

1. Data mining Aby mohly adaptivní algoritmy pracovat, je nutné, aby nějakým způsobem získávaly data (data mining) , které mohou porovnávat a třídit a na základě toho rozhodovat o svém dalším uspořádání. Nejjednodušší technikou získávání dat jsou Association rules, která se dají formálně vyjádřit jako výraz if <X> then . Znamená to například, že se vypozoruje závislost typu: zákazník, co si koupil výrobek X, si také koupil výrobek Y. Pro větší množství takových zákazníků již začíná být jev zajímavý a vede to například k přesunutí výrobku Y blíže k výrobku X. Jinou technikou je Classification, kde je účelem zařadit množinu objektů do předem známých tříd. Celý proces je rozdělen do učící se fáze s testovacími daty a do klasifikace. Poslední významnou technikou je Clustering , který spočívá v seskupování sobě podobných objektů do skupin, jejichž počet je dopředu znám. Základem je zde určení reprezentativního objektu skupiny (centroidu) a jeho postupného přizpůsobování podle prvků ve skupině.

Mezi data mining patří i statistické metody aplikované na webové logy. nenáročné

a

výsledky

jsou

snadno

interpretovatelné.

Mohou

Jejich použití je

obsahovat

například

nejnavštěvovanější stránky, nejdéle čtené stránky či takové stránky, které nikdo nenavštívil.

Nejběžnějšími klasifikačními algoritmy jsou Artificial Neural Networks (ANN), Self-Organizing Feature Maps (SOFMs), K-means, Decision trees, Bayesian networks, K-Nearest Neighbor (KNN) a Support Vector Machines (SVMs). Přiblížím zde pouze tři z nich - Decision trees, Kmeans a Bayesian networks.

1.1. Decision trees Jsou to klasifikátory ve formě stromu [5], tedy acyklické orientované grafy. Mají dva typy uzlů: listy, což jsou konečné klasifikace a rozhodovací uzly, ze kterých vedou větve rozhodnutí dle podmínky v uzlu. Decision trees jsou přehledné a snadno interpretovatelné, protože reprezentují přímo pravidla, která jsou srozumitelná i pro člověka. Pro samotné učení stromu je ale často použit jiný algoritmus. Do stromu se na začátku posílají libovolné objekty a podle jejich atributů se jim na konci přiřadí klasifikace, tedy jakási závislá proměnná. Každý uzel stromu představuje 2

rozhodnutí na základě jediného atributu a vede z něj tolik hran, kolik atribut může nabývat hodnot (zde se někdy musí uplatnit diskretizace). Kořen musí co nejefektivněji odlišit zkoumané objekty. To, podle čeho to udělat, se zjistí entropií atributů objektů – míra jejich informační hodnoty. Často se stromy zapisují ve formě tabulky, kde všechny sloupce kromě posledního představují atributy zkoumaných objektů a poslední sloupec (či kterýkoliv je takto označen) je výsledná klasifikace objektu. K tomu je vyžadováno, aby všechny objekty měly unifikované atributy a jejich rozměry. Konečné klasifikace musí nabývat diskrétních hodnot a v naprosté většině je tato podmínka vyžadována i pro jednotlivé atributy. Naštěstí většina spojitých atributů se dá snadno převést na diskrétní.

Rozhodovací stromy jsou implementovány například v algoritmu ID3 a jeho vylepšení C4.5. Strom, jenž třídí objekty, které mají m atributů, může mít maximální výšku m.

Obrázek 1:Schéma Decision tree podle [2]

Učení je schopnost systému měnit se (adaptovat) tak, že vzniklé změny umožňují systému vykonávat stejnou nebo podobnou úlohu při příští příležitosti účinněji nebo efektivněji. K učení u Decision trees je nutné mít stovky testovacích dat. Hypotéza je formální charakterizace konceptu, který má být splněn. Musí platit pro všechny pozitivní případy a žádný negativní příklad. Může se zapisovat pomocí výrokové logiky.

3

1.1.1. Trénování stromu podle ID3 Metoda shora dolů (atributy jsou již unifikovány): 1. Pro uzel S se nalezne atribut A z množiny s největší entropií z množiny atributů, které ještě nebyly v tomto podstromu použity. 2. Množina všech objektů O se rozloží na podmnožiny Oi , kterých je tolik, jako je různých hodnot H i atributu A . Poté se do těchto množin přiřadí všechny objekty z O a to tak, že objekt patří do množiny Oi právě když jeho atribut A nabývá příslušné hodnoty H i . Celá tato množina je prohlášena za nový uzel stromu Si . 3. Pokud všechny objekty v nějakém uzlu Si mají tutéž klasifikaci, je uzel prohlášen za list a dále už se nevětví. Pokud nemají stejnou klasifikaci, uzel Si je prohlášen za S a vykonají se pro něj znova příkazy 1-3. Ukončení algoritmu též nastane, když již nejsou další atributy.

1.1.2. Entropie Entropie vyjadřuje [5]

„čistotu“ libovolné kolekce hodnot, pokud můžou nabývat předem

známých hodnot. Někdy se používá jiné vysvětlení entropie, především z informatiky – je to minimální počet bitů potřebný k zakódování informace při optimálním kódování. Obecný vzorec pro entropii je:

H (S ) = ∑ − pi ⋅ log 2 pi ,

(1)

kde pi je pravděpodobnost že nastane hodnota i .Entropie H uvnitř množiny Si se určí jednoduše ze vzorce (1) pro dvě možné hodnoty (kladnou a zápornou klasifikaci) H (S i ) = pi+ ⋅ log 2 pi+ − pi− ⋅ log 2 pi− ,

(2)

kde pi+ je pravděpodobnost, že libovolný objekt v Si má kladnou klasifikaci, lze jej tedy možno vyjádřit jako

S i+ Si

.

Co se stane, když všechny vzorky budou nabývat stejné hodnoty ? Pokud se vyskytne pi+ = 0 či pi− = 0 ,tak dosazením do (2): H (S i ) = 0 ⋅ log 2 0 − 1 ⋅ log 2 1 = 0 − 0 = 0 Naopak pokud budou mít obě možnosti shodné zastoupení: H (S i ) = −1 / 2 ⋅ log 2 1 / 2 − 1 / 2 ⋅ log 2 1 / 2 = 1 / 2 − (− 1 / 2 ) = 1

4

Následný obrázek ilustruje entropii pro příklady, které mohou nabývat 2 hodnot (Binary Classification):

Obrázek 2: Průběh entropie pro binární klasifikaci [10]

1.1.3. Information gain Když víme, jak spočítat entropii nějakého systému, můžeme snadno rozhodnout, která volba atributu je nejvhodnější z hlediska entropie a to tak, že pro každé možné vybrání atributu A sečteme entropii celého systému S : n

H ( S , A) = ∑ P ( S i ) ⋅ H ( S i ) ,

(3)

1

kde atribut A rozděluje množinu S podle svých hodnot na S1 , S 2 ,...., S n množin. P( S i ) je poměr

Si S

. Takto se zjistí entropie S pro všechna A a vybere se ta s nejmenší hodnotou.

5

1.1.4. ID3 algoritmus na učení Decision tree Algoritmus na učení stromu je podobný algoritmu na jeho používání s tím rozdílem, že se mohou vytvářet větve a uzly pro hodnoty, které nelze zatím vhodně třídit. S

trénovací množina objektů

R

množina diskrétních atributů

C

klasifikace

begin Let A be the attribute with largest Gain(A,S) among attributes in R; Let {aj| j=1,2,..., m} be the values of attribute A; Let {Sj| j=1,2,..., m} be the subsets of S consisting respectively of records with value aj for A; Return a tree with root labeled A and arcs labeled a1, a2,..., am going respectively to the trees (ID3(R-{A}, C, S1), ID3(R-{A}, C, S2), ...,ID3(R-{A}, C, Sm); Recursively apply ID3 to subsets {Sj| j=1,2,..., m} until they are empty end Funkce Gain() určuje kvantitativní míru hodnoty informace a v algoritmu je implementována takto:

Gain(S , A) = Entropy (S ) −

∑ v∈Values ( A)

Sv S

Entropy (S v )

Vzorec využívá vztahu (3) a vyjadřuje úbytek entropie systému po jeho rozdělní na podsystémy.

6

1.1.5. Problémy s daty při ID3 Někdy mohou data být příliš zarušená nebo jich je málo, aby vytvořila reprezentativní vzorky. Potom mohou vzniknout stromy, které neodpovídají svým trénovacím vzorkům. Jsou metody jak tomu zabránit: •

zastavit rozrůstání stromu dříve, než se dostane do fáze, kde jsou data dobře roztříděny.

•

Nechat strom libovolně rozrůst a potom ho okleštit.

Druhá možnost našla v praxi více uplatnění, jelikož je obtížné najít bod, ve kterém by se rozrůstání mělo zastavit a to i přesto, že první metoda se jeví přímočařejší. V obou případech je ale nutné nějakým způsobem zjistit optimální velikost stromu. To je možné provést třemi způsoby, ale jen dva stojí za zmínění: •

Použije se jiná množina trénovacích vzorků, aby se zjistila užitečnost ořezání uzlů ze stromu.

•

Použijí se všechny uzly, které se vytvořily, avšak poté se projde celý strom a použitím statistické metody se zjistí, jestli ořezání či expandování uzlu vylepší stromovou strukturu.

První metoda se používá více a je popisována jako Training and validation set approach. Spočívá v rozdělení množiny vzorků na trénovací a ověřovací. Pomocí trénovací množiny se sestaví celý strom, čímž se zformuje hypotéza a ověřovací množina ověří její přesnost a umožní určit přínos ořezání uzlů.

Dalším problémem se můžou stát atributy, které nejsou diskrétní. Konečné klasifikace musí určitě být diskrétní, avšak pro samotné atributy objektů které diskrétní nejsou se může v uzlu vytvořit diskrétní hodnota. Například: je-li testovaným spojitým atributem velikost (s), tak v uzlu se porovná velikost k nějaké referenční hodnotě (s > t) a úspěšnost (true) či neúspěšnost (false) porovnání je novým diskrétním atributem. Samotné vybrání prahové hodnoty t se může stát otázkou – nejlepší hodnotou se může stát ta, při které dochází k největšímu informačnímu zisku. K tomuto stačí seřadit atributy objektů a vybrat z nich zástupce rozdílných klasifikací, vypočítat jejich informační zisky a vybrat ten nejoptimálnější.

Jiným problémem jsou chybějící hodnoty atributů u objektů. Lze to řešit tím, že chybějící atribut je dopočítán. A to buď jako průměrná hodnota téhož atributu u všech ostatních 7

trénovacích objektů či pouze u těch objektů, které mají stejnou klasifikaci (u trénovacích dat je známá výsledná klasifikace) jako objekt s chybějícím atributem.

Jako druhá možnost se nabízí dosazení pravděpodobnosti každé z možností a to na základě četností předchozích vzorků, které prošly tímto uzlem. Tedy pokud je poměr například 4:6, tak se část 0.4 instance pošle jednou větví a část 0.6 větví druhou. Takto rozdělená instance poslouží k vypočítání zisku informace a kde je zisk největší, tam se instance nakonec přiřadí. Tento postup rozdělení instance je možné aplikovat i vícekrát po sobě, když chybí více atributů. Výhody Decision trees: •

Jsou srozumitelné, jelikož jsou přímo čitelná pravidla rozhodnutí

•

Jednoduchost výpočtů po natrénování stromu

•

Umí se vypořádat jak s kontinuálními tak diskrétními proměnnými

Nevýhody Decision trees: •

Nehodí se na odhady hodnot kontinuálních proměnných

•

Při velkém počtu klasifikací a málo příkladech jsou náchylné k chybám

•

Náročné výpočty při vytváření stromu (jeho růstu)

Možné aplikace Decision trees: •

[6] Na práci s objekty, které lze reprezentovat pomocí dvojic – název atributu + hodnota atributu. Lepší je když atributy nabývají malého množství různých hodnot a jsou diskrétní.

•

K reprezentaci disjunktních množin.

•

Na třídění dat, která mohou obsahovat errory či chybějící atributy. V Adaptivních algoritmech se hodí k odhadování dat, která neznáme, či k nacházení podobných objektů.

1.1.6. UC4.5 Je to softwarové rozšíření algoritmu ID3 o některé funkce jako je ochrana před přeplnění daty, zvládání spojitých proměnných, výběr vhodných atributů, úprava výpočetní rychlosti apod. Lze jej stáhnout na adrese (nalézá se zde i manuál): http://www2.cs.uregina.ca/~dbd/cs831/notes/ml/dtrees/c4.5/c4.5r8.tar.gz (Unix)

8

1.2. K-means K–means je algoritmus, který hledá množinu vektorů V , do níž lze zařadit data X tak, aby euklidovská vzdálenost všech dat byla co nejmenší. Formální definice [8] : Algoritmus k-means hledá pro množinu dat

X = {x1 ,..., x n }

vektory V = {v1 ,..., vk }

k ≤ n takové, že je

minimalizována střední kvadratická odchylka množiny X od vektoru v1 ,..., v k .

Základním faktorem pro použitelnost algoritmu k-means je možnost reprezentace zkoumaných dat pomocí n-dimenzionálních vektorů. Pro algoritmus je nutné nejprve určit číslo k udávající kolik je ve výsledků klasifikací. Nejprve se inicializují cílové vektory (klasifikace, někdy uváděné jako centroidy či centra) na náhodné hodnoty či hodnoty zvolené heuristickým odhadem. Samotná klasifikace vektorů z množiny X probíhá tak, že každému vektoru xa je přiřazena klasifikace vj s nejmenší euklidovskou vzdáleností. Lze vyjádřit jako:

v j = min( vi − xa

)

pro všechna i ≤ k , kde funkce min() pro 2 vektory u a v je vyjádřena takto

∑u

i

− vi .

i

Po přiřazení vektoru z množiny vzorků do klasifikace obsahující n přiřazených vzorků je samotný vektor reprezentující klasifikaci u j pozměněn podle: uj =

1 ∑ xi , n i

kde xi jsou vektory patřící do klasifikace u j . Je to tedy průměr vzorků. Někdy je vhodné zastavit „update“ centroidů dříve a to tehdy, když už se zařazením nových vzorků centroid příliš nemění. Složitost k-means je:

(

)

Ο n dk +1 ⋅ log n ,

kde d je počet dimenzí zkoumaných datových vektorů, k je počet výsledných klasifikací a n je počet vzorků.

9

1.2.1. Loyd's algorithm Je to nejjednodušší podoba k-means algoritmu, používaná především v informatice.

Obrázek 3: a) vektory na začátku b) náhodné vybrání centroidů c-d) postupná klasifikace vektorů a updatování centroidů

Rychlost konvergence závisí i na volbě počátečních centroidů. Vzhledem k rychlosti algoritmu je někdy vhodné zkusit ho spustit vícekrát s různou volbou počátečních vektorů.

1.2.2. K-means++ Algoritmus určený ke zvolení počátečních vektorů tak, aby byla zaručena složitost Ο(log k ) následného k-means algoritmu. Byl vytvořen roku 2007 Davidem Arthurem a Sergeiem Vassilvitskiem (v díle The advantages of careful seeding) . Dá se dokázat, že špatným zvolením počátečních vektorů algoritmus pracuje s polynomiální složitostí Ο(x n ) . 10

Jak algoritmus pracuje: •

Vyber zcela náhodně první centroid z hodnot objektů

•

Pro každý objekt x spočítej vzdálenost D (x ) od nejbližšího clusteru, který byl vybrán

•

Vlož úplně nový vektor na náhodnou pozici a udělej z něho centroid tak, aby platilo x k +1 ≥ D 2 (x k )

•

Opakuj krok 2-3 dokud se nevybere všech k centroidů.

•

Pokračuje se standardním k-means algoritmem

Přestože vypočítání počátečních clusterů zabere značný výpočetní čas, celkový čas k vykonání obou algoritmů se ve skutečnosti zmenší. Softwarovou implementaci k-means++ lze stáhnout zde: http://www.stanford.edu/~darthur/kmpp.zip

1.3. Bayesovské sítě Pro popsání algoritmu využívajícího Bayesovy sítě je vhodné si nejdříve shrnout matematické základy Bayesova vzorce. Podmíněná pravděpodobnost: Pravděpodobnost náhodného jevu je omezena podmínkou, která

má charakter náhodného jevu a musí nastat před zkoumaným jevem. Podmíněný jev: Jsou-li A, B jevy náhodné a P (B ) ≥ 0 a pokud A může nastat pouze tehdy,

pokud nastane B , tak A je podmíněný jev a zapisuje se A | B (popřípadě A / B ). B je hypotéza. Pravděpodobnost dvou nezávislých jevů zároveň:

P ( A ∩ B ) = P ( A).P (B ) .

(1)

Pravděpodobnost podmíněného jevu (je to pravděpodobnost jevu A když už nastal jev B):

P ( A | B ) = P ( A ∩ B ) / P (B ) .

(2)

Pokud jsou dva jevy na sobě nezávislé, pak P ( A | B ) = P ( A) . Po dosazení do (2) platí vzorec (1).

Častěji se vzorec (2) používá právě tehdy, když je zadané P ( A | B ) a dopočítává se pravděpodobnost průniku:

P ( A ∩ B ) = P ( A | B ) ⋅ P (B ) . Díky tomu je možno zjistit, jsou-li jevy závislé, když známe P ( A) , P (B ) a P ( A ∩ B ) a to tak , že jsou-li nezávislé, pak splňují rovnici (1).

11

1.3.1. Úplná pravděpodobnost Je to systém jevů S = {Bi | 1 ≤ i ≤ n} , pro který platí: •

Pro všechna i , j kde i ≠ j , je Bi ∩ B j = θ (prázdná množina)

•

Sjednocení všech podmnožin Bi vrátí zpátky celé S beze zbytku:

U (B

i

= S)

(3)

(4)

i

Máme náhodný jev A , který může být součástí i několika jevů Bi (ale A nemusí být konkrétně žádný z jevů Bi ). Z (3) plyne : ( A ∩ Bi ) ∩ (A ∩ B j ) = θ pro jakákoliv i , j ( Bi a B j samy o sobě nemají nic v průniku a když se navíc zmenší na to, co mají společného s A , tak se jejich průnik dále zmenší). Z (4) plyne, že A je určitě celé poskládáno, když se vytvoří jako sjednocení průniků :

U(A ∩ B ) . i

(5)

i

Ve vzorci (5) zapíšeme sjednocení ve formě sumy a A nahradíme jeho pravděpodobností

P ( A) : P ( A) = ∑ P ( A ∩ Bi ) , i

pro průnik v sumě platí (2) a tedy P ( A) = ∑ P ( A | Bi ) ⋅ P (Bi ) .

(6)

i

1.3.1.1. Bayesův vzorec Je vytvořen pro podmíněnou pravděpodobnost, kde náhodným jevem je hypotéza Bk a podmínkou původní jev A : P ( B k | A) =

P (B k ∩ A ) P ( A)

(7)

V čitateli se prohodí činitelé v průniku P (Bk ∩ A) = P ( A ∩ Bk ) a poté platí podle (2): P ( B k ∩ A) = P ( A | B k ) ⋅ P ( B k ) .

Jmenovatel se jednoduše nahradí podle (6) a výsledný Bayesův vzorec má tvar: P (Bk | A) =

P ( A | Bk ) ⋅ P (Bi ) . ∑ P( A | Bi ) ⋅ P(Bi ) i

12

(8)

1.3.1.2. Aplikace Bayesova vzorce Nejčastější použitím Bayesova vzorce je vytvoření algoritmů pro programy na straně serveru, které filtrují spamy, například SpamAssassin nebo SpamBayes. Nejjednodušší filtrace elektronické pošty by vypadala takto: P (S | W ) =

P (W | S ) ⋅ P (S ) P (W | S ) ⋅ P (S ) + P(W | H ) ⋅ P (H )

P (S | W )

pravděpodobnost, že zpráva se slovem W je spam

P (W | S )

pravděpodobnost, že slovo W se objevuje ve spamech

P (S )

pravděpodobnost, že zpráva je spam

P (H )

pravděpodobnost, že zpráva je ham (zpráva, která není spam)

P (W | H )

pravděpodobnost, že slovo W se objevuje v hamech

Pokud se neuplatní předpoklady S a H (hypotéza se pak označuje not biased), tak se vzorec zjednodušuje na: P (S | W ) =

P (W | S ) , P (W | S ) + P (W | H )

(9)

P (W | S ) a P (W | H ) se musí vypočítat během učící se fáze pomocí dostatečně reprezentativních zpráv. Výpočet (9) se provede pro všechna či většinu slov ve zprávě, čímž se získají pravděpodobnosti jednotlivých slov p1 , p 2 ,..., p n . Pravděpodobnost, že email je spam je pak : P=

p1 ⋅ p 2 ⋅ ... ⋅ p n p1 ⋅ p 2 ⋅ ... ⋅ p n + (1 − p1 ) ⋅ (1 − p 2 ) ⋅ ... ⋅ (1 − p n1 )

Se slovy, které se vyskytují pouze výjimečně, se nakládá odlišně – buď se s nimi nepočítá vůbec nebo se přidávají koeficienty k hodnotám pravděpodobností (=Beta distribution): P ' (S | W ) =

(s ⋅ P (S ) + n ⋅ P (S | W )) s+n

s

je síla (strength) – užitečná informace o zkoumané zprávě

n

je počet výskytů zkoumaného slova během učící se fáze.

Často se ignorují slova, která jsou přesně na pomezí mezi hamem a spamem s hodnotou kolem 0.5, jelikož moc užitečných informací nepřinášejí. Také se ignorují častá neutrální slova jako

členy před slovy, tvary slovesa být, dělat apod.

13

1.3.2. Bayesovské sítě Jde o pravděpodobnostní grafický model představující množinu proměnných a jejich podmíněných pravděpodobností reprezentovaných acyklickým orientovaným grafem

[7].

Mějme například dané pravděpodobnosti v tabulce:

věk revmatická choroba < 30 ano ne 31 - 41 0.03 0.43 41 - 55 0.02 0.12 > 55 0.11 0.10 Tabulka 1: Pravděpodobnostní rozdělení, zdroj [9]

Veličin ovlivňujících výsledek však bývá řádově více a pokud by se měly všechny dát do jediné tabulky a ke všem kombinacím zjistit pravděpodobnosti, bylo by jich 2 n , kde n je počet veličin.

Bayesovská sít umožňuje efektivnější správu veličin. Je to orientovaný acyklický graf, kde uzly jsou částečné znalosti a hrany vedou od uzlu ke znalosti, která je jím podmíněná. Částečná znalost je dána pravděpodobnostním rozdělením (viz tabulka) závislém na jediné veličině, kterou je v tomto případě věk V . Jedna veličina tedy tvoří v Bayesovské síti jeden uzel. Další veličinou by mohla být například nadváha N , která by byla dána podobným pravděpodobnostním rozdělením jako V s tím, že hodnoty by reprezentovaly podmíněnou pravděpodobnost veličiny N na veličině V . Bayesovská síť by již obsahovala dva uzly a jednu hranu vedoucí od uzlu V

do uzlu N .

Obrázek 4: Bayesovská síť o dvou uzlech

Výsledná pravděpodobnost P je potom dána:

P (V , N ) = P (V ) ⋅ P (N | V ) Na stejném principu funguje i přidávání a větvení více uzlů.

14

2. Adaptivní web Účelem adaptivních webových systémů je přizpůsobit se individuálním uživatelům a změnit tak formu podávání informací či aplikační rozhraní. Jedním z přednostních účelů adaptivních webů v komerční sféře je z návštěvníka udělat zákazníka, zvýšit tržby a upevnit důvěru zákazníků. Z nekomerčních účelů je to hlavně usnadnit návštěvníkovi nalezení hledané informace. Projevem adaptace je personalizace webu, seznamy odkazů na stránky s podobným obsahem či jinak uspořádaná navigace stránek. Avšak přehnaná adaptace webu má i své nevýhody. Hrozí že přílišné změny v navigaci budou uživatele mást a nakonec nenajde nic. Také mohou odradit zásahy do soukromí při schraňování informací o chování uživatele.

Na základě sběru informací o uživateli se vytváří model uživatele a od něho se teprve odvíjí adaptivní změny webu. Kromě informací získaných z uživatelova chování je možno se na některé parametry přímo zeptat prostřednictvím formuláře. Uživateli je tak poskládán nový dokument z širšího záběru možností ( Datového Zdroje Dokumentů ) . Uchování modelu uživatele umožňuje sledovat jeho pozdější změny chování a zachycuje různé druhy person (persona je model uživatele zachycující nejpodstatnější jeho rysy). Pro některé méně komplexní adaptace není nutné, aby model uživatele schraňoval všechny možné informace, ale stačí například udržovat navigační sekvenci stránek či pouze textový obsah stránek v podobě vektoru četnosti slov. Pokud není uživatel na webu nijak identifikován a je anonymní, pak model uživatele nelze vytvořit (případně za cenu složitého procesu sessionalizace) a ztrácí se tak některé možnosti adaptace. Přesto lze stále analyzovat například navigační sekvenci či klasifikovat typ prohlížených stránek.

Model uživatele uložený v databázi a model aktuálně používaný konkrétní aplikací se mohou lišit. Pro většinu operací nejsou nutné všechny informace. Například pro nabízení fotek podobných těm, co uživatel hodnotil, nevyžadují znalost sekvence navštívených stránek. Aktuálně používaný model by měl být kompromisem mezi příliš častými operacemi nad databází a velikostí modelu, který uloženém v aplikaci.

15

Obrázek 5: Model uživatele a jeho adaptace podle zdroje [2]

Adaptivní systém může pracovat i pro uživatele, jenž jsou anonymní tím, že podle vzorku chování zařadí do nějaké klasifikace, podle které předvídá další uživatelův postup. Avšak mnohem lepších výsledků se dosahuje, je-li uživatel autorizován, tedy má-li nějaký svůj profil či účet. V tomto případě adaptivní algoritmus má k dispozici více než jedno uživatelovo chování a vytvoří tak přesnější model uživatele, popřípadě bude vytvářet předpovědi a přizpůsobování pouze na základě jeho vlastních vzorů chování.

2.1. Zdroje informací pro adaptivní web Základní potřebou pro Adaptivní algoritmy na webu je získání dat. Získávají se z několika zdrojů a celý proces se skládá z extrahování, transformování a uložení dat (Extraction Transformation Loading - ETL). Nejčastějšími zdroji jsou webové logy, textový obsah stránek a hyperlinková struktura webu.

2.1.1. Webové logy Jsou to textové soubory generované webovým serverem, ve kterých jsou zapsány informace o uživatelské aktivitě na webu. Do logu se zapisuje nový řádek (registr) při jakémkoliv požadavku uživatele na objekt, kde objektem se rozumí HTML stránky, obrázky, video, dokumenty v jakémkoliv formátu apod. Informace získané z webových logů se také označují jako clickstreamové [3]. 16

Samotná data jsou zapisována ve struktuře dané konsorciem W3C a to buď ve starším formátu Common Log Format (CLF) definující sedm základních položek a nebo novějším Extended Common Log Format (ECLF), kde je položek devět [2] :

remotehost – internetová adresa klienta, který se připojil k webové aplikaci. Bývá zapsána v podobě IP adresy či doménového jména.

rfc931 – obsahuje identifikátor TCP spojení authuser - obsahuje identifikaci uživatele v případě, že se připojil bezpečnostním protokolem HTTPS.

date – datum a čas vzniku požadavku pro webovou aplikaci, jeden z nejdůležitějších záznamů. Díky němu je možno sestavit chronologický záznam uživatelovy navigace stránkami.

request – zaznamenává se použitá metoda požadavku (GET, POST) a za ní následuje URL adresa požadovaného objektu.

status – pouze status stránky, která byla klientovi vrácena. Důležité jsou pouze chybové statusy (404 Page not found)

bytes – počet bytů vrácených serverem referrer – odkaz na stránku, ze které byl požadavek vyslán. Významná položka k určování úspěšnosti reklamních kampaní apod.

user_agent – informace o klientské aplikaci, která se připojila k webu a případně i operační systém uživatele.

Tabulka 2: Příklad webového logu ze droje [2]

17

Webové logy nejčastěji slouží k rekonstrukci posloupnosti uživatelovy navigace. Tento proces se také nazývá sessionalizace. Proces je ztěžován nepravými informacemi podstrčenými proxy servery a firewally. Sessionalizace řeší především problém identity uživatele, kdy musí odlišit stránky, které navštívil ten samý uživatel, aniž by měla k dispozici např. cookies od uživatele, jako je tomu ve většině případů. Jiným problémem je odstranění záznamů z logů od robotů prohledávajících web, které jsou používány vyhledávajícími enginy firem jako je Google.

Webové logy se generují serverovou aplikací. Záleží tedy na použité technologii, kterou může být ASP, PHP, Java, JavaScript apod. Administrátor serveru si proto sám může celkem jednoduše vytvořit aplikaci na tvorbu webových logů či může využít komerčních nástrojů jako je například Web Log Suite.

Pro ucelenost tématu je vhodné ještě zmínit pojem Webhousing. Je to proces ukládání clickstreamových dat získaných z provozu WWW stránek do datového skladu. Webhouse obsahuje především informace o chování uživatele, tedy již transformované logy a případně nalezené vzory chování a pravidla adaptace webu.

2.1.1.1. Postup při sessionalizaci Sessionalizaci je možné provést pomocí programovacích jazyků, které umějí pracovat s proudy, jelikož obsahy webových logů jsou tabulkové textové soubory. Je možné dokonce ukládat generovaná data do databází a poté s nimi pracovat pomocí jazyků jako je SQL.

Proaktivní strategie – používá k identifikaci uživatele cookies, které jsou mu poslané při první návštěvě webu. Nevýhodou je omezování uživatelova soukromí ukládáním více informací, než je třeba. Nevýhodou také je, že uživatel může cookies vypnout.

Reaktivní strategie – používá pouze webové logy a proces sessionalizace, není tak efektivní jako strategie proaktivní, ale nezasahuje do soukromí uživatele. Reaktivní strategie jsou více používané a mohou být implementovány dvěma způsoby: •

Navigation Oriented Heuristics – sleduje, jestli sekvence registrů obsahuje stránky, které jsou přístupné ze stránek předchozích. Není-li tomu tak, je započato nové připojení uživatele.

18

•

Time Oriented Heuristics - Předpokládá se, že každé připojení na server má maximální dobu trvání – většinou kolem 30 minut a po jejím překročení se další navigace považuje za nové připojení.

Postup sessionalizace: 1. V každé sessionalizaci se osekají registry o objekty které nejsou webové stránky, tedy například obrázky, zvuky, videa. K tomuto účelu se dají použít programovací jazyky podporující regulární výrazy (Perl, PHP, Unixové skripty). 2. Poté se odstraní stránky, které jako svůj status signalizovaly error, a stránky navštívené vyhledávacími roboty, kteří se poznají například podle položky prohlížeč nebo podle krátkého času stráveného na stránce. Většinou se ale tyto prohledávací roboti identifikují názvem a dají se dohledat ve veřejném i neveřejném seznamu těchto robotů. 3. Seskupí se registry podle IP adresy a uživatelova prohlížeče. 4. Nyní se použije časové omezení a seskupí se ty registry, které jsou v časovém intervalu 30 minut. 5. Předpokládá se, že stejné IP adresy mohou pocházet od více uživatelů skrytých za síťovým prvkem provádějícím NAT (Net Address Translation) a proto je nastaveno maximální množství stránek, které byly navštívené během jednoho připojení. Pseudo algoritmus sessionalizace by vypadal takto: 1 var List<String> wrongTypes = defineWrongTypes(); 2 var result:= SELECT * FROM WebLog 3 var List result2_1 = new List(); 4 foreach(item in result)begin 5 if(wrongTypes.contains(item)) continue; 6 else result2_1.add(item) 7 end 8 var List<String> robots = getKnownWebCrawlers(); 9 var result2 := SELECT * FROM result2_1 WHERE Status BETWEEN 10 100 AND 304 AND NOT IN List GROUP By IP 11 var List sessions = new List () 12 foreach(group in result2)begin 13 if(maxTime(group)-minTime(group)<30*60) 14 if(Count(group)<30) Session.addSession(group) 15 end

2.1.2. Obsah webové stránky Pro získání informací o webové stránce se hodí pouze její textový obsah a hypertextové odkazy na další stránky. Každému objektu na webu se přiřadí identifikátor. Díky identifikátoru se dají sledovat objekty i přes jejich aktualizace či změny názvu. Objektům se často přiřazuje i popis, 19

který je většinou vytvářen samotnými uživateli či správci systému nebo v případě XML může být popis již obsažen mezi některými ze značek.

2.1.2.1. Textový obsah Celý web je reprezentován pomocí modelu ve vektorovém prostoru (Vector Space Model), což znamená, že každý dokument je převeden na vektor, jehož prvky jsou váhy slov, které se vyskytují v dokumentu. Zde je základní postup, jak takový model vytvořit: Nejdříve se všechna slova na stránce převedou do kanonického tvaru – například slovo writing na write či did na do a were na be. HTML tagy se sice do výskytu slov nezaznamenají, mají ale vliv na váhu slov jimi uzavřených. Dimenze vektoru je dána buď celkovým počtem různých slov, nebo většinou jen těch nejdůležitějších a prvky vektoru jsou váhy příslušných slov. Základem váhy slova je četnost jeho výskytu. Dalším faktorem pro utvoření váhy slova je jeho výskyt mezi některými z HTML či XML tagů. Všeobecná neutrální slova jako be nebo do se neberou v úvahu. Váha slova se obecně počítá jako log(

Q ), ni

kde ni je počet výskytů i -tého slova a nazývá se Inverse Document Frequency (IDF). Variací na IDF je Term Frequency/inverse Document Frequency (TFIDF) a spočívá ve vynásobení IDF příslušným koeficientem v matici: F : mij = f ij ⋅ log(

Q ). ni

f ij je počet výskytů slova i v dokumentu j . Z textového obsahu webu se vytvoří matice typu RxQ : M = (mij ) , kde i = 1...R a j = 1...Q , (mij ) je váha slova i v dokumentu j , R počet různých slov dokumentu a Q počet dokumentů na webu.

2.1.2.2. Hypertextové odkazy Odkaz mezi dvěma stránkami obecně znamená, že mají něco společného. Dokumenty, které mezi sebou obsahují více odkazů než jiné, tvoří komunitu. V komunitě se dají rozlišit 2 druhy stránek: Obsahové (Authorities) – tvoří obsah webu, zdroj informací. Tyto stránky jsou vyhledávány

uživatelem a rozhodují o oblíbenosti webu.

20

Rozcestníky (Hub) – je to kolekce hypertextových odkazů na jiné stránky ať už v rámce stejného webu či webů podobných.

Obrázek 4: Web Site a jeho hyperlinková struktura [8]

Pro Adaptivní algoritmy je důležité rozeznávat tyto druhy stránek a pracovat s těmi obsahovými. Algoritmus projde stránku a hledá tagy href, které odkazují na stránky na stejném webu. Linky stejně jako všechny objekty mají své identifikátory , díky nimž lze do pole snadno zapsat hyperlinkovou strukturu HTML stránky. To se provádí tak, že pro jeden dokument je vytvořeno právě jedno pole, jehož prvním prvkem se stává identifikátor daného dokumentu. Dalšími prvky v libovolném pořadí jsou identifikátory stránek, na které dokument odkazuje. Tedy například {5,3,6,7,10} znamená, že dokument s id 5 odkazuje na stránky 3,6,7,10. Stránka, která nikam neodkazuje obsahuje v poli pouze svoje id.

2.2. Uchování informací Získané informace ať už z textového obsahu webu či webového logu je po okleštění o irelevantní informace nutno uložit pro jejich další použití především k dolování dat. Taková úložiště se nazývají Web Information Repository (WIR) a měly by splňovat: 1. schopnost poskytovat informace jak pro end-user aplikace tak pro techniky dolování dat. 2. výběr zdroje dat – výběr té správné části úložiště 3. logický model úložiště. Nejčastější jsou 2 modely – Cube a Star model.

21

4. představit uživateli předběžný model dat. Model umožňuje uživateli data procházet i když neví, co přesně chce a jak se na to dotázat. 5. volba DBMS (Data Base Manager System ) 6. použitím DBMS namapovat logický model úložiště do fyzické databáze. 7. ukládání dat a vyhodnocení modelu. 8. ladění výkonu, jelikož odezva databáze je nejcennějším aspektem úložiště.

2.2.1. Modely datových úložišť 2.2.1.1. Cube model Používá architekturu MDBMS (Multidimensional DataBase Management System ). Je vytvořen pomocí n-rozměrných polí, kde n je počet atributů v databázi. Mějme například tři atributy A, B, C a tedy v poli p na pozici p[A] jsou hodnoty atributu B a stejně tak na pozici p[A][B ] jsou hodnoty atributu C . Pokud tedy přijde dotaz na A = a , B = b , C = c , je vrácen prvek

p[A][B ][C ] .

Obrázek 5: WIR - Cube model [8]

2.2.1.2. Star model Je založen na častější architektuře RMBMS (Relational database management system). Star model je dnes nejpoužívanějším hlavně proto, že RDBMS je nejrozšířenější druh databází. Je tvořena strukturou tabulek, které jsou provázané pomocí atributu ID jednotlivých položek. Často 22

je struktura vytvářená tak, že existuje hlavní tabulka s identifikátory položek a ostatní tabulky představující atributy jsou propojeny pouze s hlavní tabulkou.

Obrázek 6: WIR - Star model [8]

Logy se nahrávají do struktury několika tabulek, jak je zobrazeno na obrázku. Sekvence navigace se dá uložit v podobě tabulky Point_to, která obsahuje dvojice zdroj odkazu a odkazovanou stránku. Vector Space Model je odkazován ve WebObject v atributu Free_text_content.

2.2.1.3. Pattern Repository Kromě úložiště WIR obsahující veškeré informace jak o webu tak uživateli je nutné uložit vzory chování, které byly získány pomocí nástrojů na dolování dat. Ty se ukládají do Pattern Repository. Dalším možným úložištěm může být Rule Repository schraňující pravidla chování algoritmů jako je Decision tree získaný analýzou vzorů chování. Ve všech úložištích platí, že nové informace nepřepisují ty staré a dají se tak vyhledat změny, které odpovídají nárůstu či poklesu statistik na webu.

2.3. Adaptivní algoritmy Změny způsobené adaptivními algoritmy mohou být jednoduché měnící pouze

přivítání

uživatele nějakou zprávou až po složité změny v navigaci a doporučení podobných produktů či stránek. Možné utřídění druhů personifikací by vypadalo takto [183]: 23

Memorization – spočívá v uchování informací o uživateli, například o jeho posledních navštívených stránkách či hledaném produktu a při příští návštěvě mu tyto stránky nabídne . Guidance – pomáhá uživateli nalézt, co hledá. Sestavuje odkazy na stránky s podobným obsahem či reorganizuje struktury stávajícího webu. Sem patří i nabízení podobných produktů. Task performace support – za již přihlášeného uživatele může vyplňovat dotazník či posílat automatické e-maily.

2.4. Postup personifikace webu Následující kapitola bude popisovat postup personifikace webu, kde se uživatel, pro nějž se změny provádí, přihlašuje pod svým uživatelským jménem. Lze tedy vytvářet model uživatele a ukládat ho do databáze. Také přihlašováním odpadá potřeba sessionalizace a s tím spojené vytváření logů. Nyní bude možno informace přímo ukládat do WIR.

2.4.1. Databáze WIR Základem je vytvoření dvou úložišť WIR – jednu, která bude sloužit jako model webu a druhou do které se budou ukládat uživatelské modely (aktuální i před změnou). Dobrou volbou je například databáze MySQL , jež je zdarma i pro komerční použití a pomocí které se vytvoří tabulkový Star model úložiště popsaný v kapitole 3.2.1.2 .

Model webu: Web – centrální tabulka obsahující hlavně cizí klíče do ostatních tabulek. Může obsahovat všeobecné informace popisující web. Page – stránky, které web obsahuje, každá stránka má svůj identifikátor, URL a stručný popis svého obsahu případně kategorie. Každá stránka obsahuje svoji vektorovou reprezentaci a mezi každými dvěma stránkami je vypočítána vzdálenost. PageDistance – tabulka přiřazující hodnotu vzdálenosti mezi dvěma stránkami Behaviours – obsahuje dosud nalezené uživatelské vzory chování, které se poté porovnávají s jednotlivými vzory od uživatelů.

24

Obrázek 7: Model webu pomocí modelu Star WIR

Model uživatele: UserFacts – centrální tabulka, s kterou se ostatní tabulky spojují pomocí svých primárních klíčů. Kromě cizích klíčů obsahuje informace o uživateli jako jméno, heslo a podobné údaje. Navigation – nejdůležitější tabulka držící sekvenci stránek navštívených uživatelem a datum, kdy bylo sezení uskutečněno. PageVisit –obsahuje pouze identifikátor stránky (je to klíč do tabulky Page, která je již zobrazena u modelu webu) a čas na ní strávený Pattern – obsahuje cizí klíč do tabulky Behaviours (definována v modelu webu)

Obrázek 8: Model uživatele pomocí Star WIR

25

2.4.2. Tvorba modelu uživatele Uživatel prochází mezi stránkami webu a po každé změně se zapíše do WIRu do příslušné navigace vztahující se k aktuálnímu připojení nová návštěva stránky s klíčem stránky v tabulce Page a s časem, který na ní uživatel strávil. Na konci uživatelova sezení se navigace analyzuje (viz 4.1.5) a vyhodnotí vzor chování, který se porovná s již existujícími vzory v tabulce Behaviours. Zde je možné jít dvěma směry – mít předem připravené vzory chování a uživatelské chování do nich postupně zařazovat či je možné vytvářet nové vzory v případě dostatečně odlišného chování.

2.4.3. Zpracování obsahu stránky Celý proces je již popsán v kapitole 3.1.2.1 . Spočtou se všechna slova z textového obsahu webu. Vyberou se jen taková slova, která dávají nějaký užitek, která nenesou význam a nejsou HTML značky. Slova se sestaví do vektorů reprezentující celé dokumenty.

Pomocí programovacího

jazyka se vytvoří parser, který projede celý dokument a vyhledá slova , která potom porovnává se slovy, jež se nebudou uvažovat. V případě , že se tak nestane bude v asociativním poli (mapa) na indexu tvořeném tím slovem zvýšena váha. Pokud slovo neexistuje, vytvoří se nový index s váhou 1. Na konec se upraví váhy slov vzhledem k celkovému počtu slov ve všech dokumentech. 1 foreach(Document document in documents)begin 2 var List<Word> [] HTMLtags = defineHTMLtags() 3 var List<Word> [] excludedWords = defindeExcludedWords() 4 var WordVector vector = initWordVector() 5 do w = document.readWord() 6 while(w != endOfDocument) begin 7 if(w == endOfDocument) break 8 if(HTMLtags.contain(w)) continue 9 if(excludedWords.contain(w)) continue 10 if(vector.contains(w)) begin 11 if(document.betweenHTMLtags(w) 12 vector.addWeight(w,HTMLtag)) 13 else vector.addWeight(w,null) 14 end 15 else 16 vector.addNewWord(w) 17 end 18 end 19 end 20 recountWeights(documents) 26

2.4.4. Analýza uživatelské navigace Nejprve je nutné shromáždit několik uživatelských navigací, ve kterých se poté naleznou vzory chování algoritmem k-means. Určí se dimenze vektoru navigace podle průměrného počtu l stránek navštívených během jednoho sezení. Další nutností pro algoritmus k-means je předem

známý počet výsledných klusterů k . Tím je počet uživatelských vzorů chování uložených v tabulce Behaviours. Algoritmus potřebuje znát pořadí navštívených stránek. To se implicitně udržuje v pořadí zapsání stránek do sekvence navigace.

Samotný algoritmus k-means je detailněji popsán v kapitole 2.2 a pseudokód by nepřidal příliš mnoho nových informací. Výsledkem algoritmu je k navigačních sekvencí délky(tříd) l . Jelikož každá stránka má ve WIRu stručný popis svého obsahu, mohou experti určit záměr uživatele v konkrétní sekvenci. Každému novému uživateli, kterému navigace ‚spadne‘ do konkrétní třídy, je možné nabídnout link na další stránku či v případě dostatečně odlišného chování (větší vzdálenost ode všech clusterů něž určená mez) je možné přidat nový vzor chování.

2.4.5. Analýza podobnosti webových stránek Stránky, které uživatel navštívil a zvláště ty, na kterých strávil nejvíce času, se dají považovat za důležitější než ostatní. Podle statistik se takovéto stránky dají nalézt a jejich vektory vytvořené podle kapitoly 4.1.4 použít v algoritmu k-means k nalezení podobných stran či spíše stran obsahujících podobná slova. Vybrané podobné stránky je ještě vhodné nechat posoudit experty jak moc relevantní jsou. Většinou ale již podle nadpisu je jasné, jde-li či nejde o podobný objekt.

Uživateli je možné nabídnout linky na tyto nalezené stránky, ale i další užitek plyne z vektorů nejčtenějších dokumentů. Jsou jím nejdůležitější slova (Keywords). Relativní důležitost slova v klusteru je definována jako jeho geometrický střed [2] : kw[i ] = n

∏m

ip

,

p

kde p jsou stránky patřící do zkoumaného klusteru, i je konkrétní slovo a n je počet stran p . Určení klíčových slov je důležité pro vytváření obsahu stránek a řadí se mezi Offline

27

doporučení, které posuzují webový experti. Klíčovými slovy se také zviditelňuje web pro vyhledávací stroje jako je Google, Yahoo apod.

2.4.6. Změny na webu Nejprve popíši změny, které lze vytvářet podle navigace. Každé uživatelovo připojení (session) je zaznamenáno v tabulce Navigace a podle 4.1.5 lze zjistit nejpodobnější navigaci k těm, které již existují v tabulce Behaviours. Stránky z navigačního vzoru lze poté uživateli doporučit. Jedinou otázkou zde je, jaká dimenze navigačního vektoru se má použít. Maximální velikost je samozřejmě dána samotnou velikostí vektoru navigace, ale často je lepší zvolit velikost jinou, například jako průměr velikostí navigačních vektorů v tabulce Behaviours v případě jejich menších velikostí.

Další možností adaptace webu je změna hyperlinkové struktury webu. Změna je především koncipována jako offline, jelikož by měla být provedena webovými experty. Předpokládejme, že takto by vypadaly uživatelovy navigace uložené v tabulce Navigation:

Cluster

Visited Pages

Time spent in seconds

1

1,3,8,9,147,190

40,67,175,116,43,184

2

100,101,126,128

20,69,40,63

3

70,86,150,190,101

5,80,121,108,30

Tabulka 3: Navigační clustery , zdroj [2]

Jsou zde nejdůležitější stránky, na kterých uživatel strávil nejvíce času. V prvním clusteru to jsou 8, 9, 190 a poté jsou stránky, na kterých zůstal podstatně kratší dobu 1,3,147. Změnami ve struktuře by bylo přidání linku mezi stránkami 8,9,190. Podobně lze přidávat linky i mezi jednotlivými clustery – v případě, že se stránka s relativně větším časem vyskytuje ve více klusterech, je vhodné přidat mezi nimi link – například stránka 190 se vyskytuje v clusteru 1 a 3.

Dále se dají vytvářet změny podle podobnosti obsahu. Poté, co každá stránka či dokument je reprezentován pomocí vektoru váhy slov, lze najít na webu nejpodobnější stránky stejnou metodou jako předtím sobě podobné navigace. Uživateli je možno doporučit stránky podobné jakékoliv stránce, kterou navštívil, ale spíše je vhodnější zvolit stránky podobné nejnavštěvovanější stránce či stránce, kde strávil uživatel nejvíce času.

28

3. Aplikace Výsledný program je webová aplikace. Jako jazyk jsem zvolil Javu a aplikační framework open source Spring verze 2.5 [12], jenž je přehledný (konfigurační soubory ve formátu xml) a těší se široké základně uživatelů.

Aplikace by měla nabízet uživateli obsah vhodným způsobem podle jeho chování. Kromě funkcí jako je registrace, přihlašování a odhlašování by tak měla nabízet adaptaci hodnocení fotek a navigace. Výsledkem adaptace hodnocení fotek je nabízení jiných vhodných fotografií, které by se mohly uživateli líbit a podobně adaptace navigace způsobuje nabízení relativních odkazů v sekci články.

Obrázek 9: Diagram případů užití (Use Case diagram) aplikace

3.1. Struktura aplikace Samotný webový projekt je nazván WebAdaptation. Algoritmy a potřebné třídy pro samotnou adaptaci jsou však vytvořeny v jiném newebovém projektu WordVectorCreation (název nepříliš odpovídá skutečné funkci, ale je to tak proto, že původně to měla být jeho funkce). Ten je následně zkompilován a jako knihovna typu jar. vložen do projektu WebAdaptation. WordVectorCreation využívá knihovny wvtool.jar (lze stáhnout na http://wvtool.cs.unidortmund.de/) , která obsahuje nástroje pro vytvoření Word Vector Space modelu z textového 29

souboru či přímo z vloženého textového řetězce. Knihovna je distribuována jako open source. Bohužel tento nástroj neobsahuje vytváření váhy na základě tagů, ve kterých se slova nacházejí.

Obrázek 10: Model nasazení (deployment diagram) aplikace

3.1.1. WordVectorCreation Knihovna obsahuje abstraktní třídu Vector. Ten reprezentuje jeden vstup do klusterovacího algoritmu. Vstupní data v mé adaptivní aplikaci potřebují vytvořit vektor pro reprezentaci Vector Space Modelu (TextVector), sekvence navigace (NavigationVector) a množiny hodnocení od jednoho uživatele (RatingVector). Samotné hodnoty jsou uloženy v poli float[]. Samozřejmě si každá zděděná třída může tuto skutečnost předefinovat, ale pro potřeby této aplikace to stačí. Další nutností pro všechny vektory byl odkaz na výsledný centroid, do jehož klusteru spadaly (před tříděním nastavený na null). Všechny vektory musí implementovat metodu pro výpočet jejich vzájemné vzdálenosti VectorDistance(Vector v).

3.1.1.1. TextVector Vector reprezentuje textový dokument či jakýkoliv text, kde se vyskytují běžná slova. Knihovna wvtool.jar při vytváření Vector Space Modelu z daných textových vstupů nejdříve musí vytvořit společný seznam slov, který si poté uloží do souboru. Sekvence vybraných slov 30

slouží jako pole values typu float[] a hodnotami jsou počty výskytů. Tedy například je li values[3] = 1 znamená to, že pro slovo, které je v listu slov na místě 3, byl zaznamenán 1 výskyt v určitém dokumentu. Vzdálenost se mezi dvěma vektory počítá podle publikace Adaptive Web Sites [2] pomocí skalárního součinu jako úhel mezi dvěma vektory cos α =

u ⋅v . Při testování se mi poměrně u ⋅v

dobře jevila i alternativní metoda založená na jednoduchých euklidovských vzdálenostech n

daných vztahem

∑ (u

i

− vi ) . Ještě je vhodné dodat, že u první metody se potřebovalo na konci

i

upravit: výsledek = 1-výsledek, aby bylo zachováno pravidlo vzdálenosti – čím větší číslo tím větší vzdálenost.

3.1.1.2. RatingVector Reprezentuje množinu hodnocení jednoho uživatele. Každý uživatel má pouze jeden svůj hodnotící vektor. Hodnoty tohoto vektoru jsou uloženy tak, že pole values typu float [] má velikost jako maximální index uložené fotky a všude tam, kde uživatel hodnotil, je na příslušném indexu fotky hodnota jeho hodnocení, všude jinde je potom 0.

Vzdálenost mezi dvěma vektory se zde jednoduše počítá jako euklidovská vzdálenost dvou hodnot hodnocení. I zde by bylo možné zkusit určování vzdáleností skalárním součinem.

3.1.1.3. NavigationVector Tento vektor obsahuje sekvenci identifikátorů stránek, které uživatel postupně navštívil při jednom připojení. U tohoto vektoru nebylo možné použít euklidovskou vzdálenost či skalární součin, jelikož jde o prostor diskrétních hodnot, které mezi sebou nemají porovnávací vztah. Zde je metodou, jak určit vzájemnou vzdálenost dvou vektorů Sequence Alignment Method (SAM) [11]. Tou se určí ‚jak obtížné‘ je převést hodnoty jednoho vektoru na druhý, přičemž každá operace je nějak předem bodově ohodnocena. Například mějme sekvence: {2,5,4,7} a {2,4,5,9,10} a ohodnocení operací: výměna dvou prvků za 1 bod, vymazání prvku za 1 bod a vložení nového prvku také za bod. Algoritmus postupně bere prvky sekvence první a hledá, jestli neexistuje stejný prvek v sekvenci druhé. Pokud ano a je dokonce na stejné pozici, tak žádný trestný bod se nepřičte a pokračuje se na další prvek. Pokud prvek v druhé sekvenci existuje, ale na jiné pozici, je přehozen s prvkem na správné pozici, tedy zde se 4 v druhé sekvenci prohodí za 5: {2,5,4,7}. Třetí prvek je již na správném místě a poslední prvek první sekvence 7 již nemá 31

svého partnera v druhé sekvenci a tam proto je číslo 9 vymazáno za jeden bod a vloženo nové 9 také za 1 bod. V druhé sekvenci je navíc číslo 10, které musí být vymazáno za další 1 bod. Konečná vzdálenost je suma těchto bodů 4.

NavigationVector má jednodušší alternativní metodu pro výpočet vzdálenosti. Pouze se postupně berou prvky delší sekvence a jestli k nim někde existuje stejný prvek v kratší sekvenci tak se k vzdálenosti nepřičte žádný trestný bod a onen prvek z kratší sekvence je z ní vypuštěn, aby nebyl použit vícekrát.

3.1.1.4. Centroid Je pouze interface, nutí svou dědící třídu k implementaci metody na update sama sebe. V praxi potom ještě všechny centroidy musí dědit ze třídy Vector, aby se s nimi tak mohlo zacházet – především kvůli metodě vectorDistance. Každý druh Vektoru má svůj centroid (TextCentroid, RatingCentroid a NavigationCentroid).

Metoda update způsobuje, že centroid se stává jakýmsi průměrem jemu přiřazených vektorů. Zde nastává problém. Zatímco u textového a hodnotícího vektoru se z hodnot skutečně může vytvářet aritmetický průměr, u NavigationVectoru nezbývá než na určitou pozici v sekvenci dát číslo, které tam má největší zastoupení.

3.1.1.5. ClusteringAlgorithm Interface mající rozhraní nutné ke spuštění klusterování. Kromě nastavení seznamu Vektorů musí mít ještě možnost inicializovat některé své parametry. To se provádí metodou setClustersCount(int number). Bohužel tento název jsem zvolil s ohledem na konkrétní implementovaný algoritmus k-means a neuvědomil si, že v jiných zděděných třídách by se mohly nastavovat jiné parametry. Nejdůležitější metodou, která musí být implementována, je startClustering(), v níž se provádí celé klustrování.

Pro účely této aplikace jsem vytvořil třídu KMeans, která provádí stejnojmenný algoritmus. Samotný algoritmus je popsaný v kapitole 2.2, avšak zde jsem ho upravil. S přihlédnutím k celkovému malému množství vektorů vstupujících do klustrování nemá smyls po každém updatu centroidu kontrolovat, jestli byla jeho změna větší než nastavená mez. Vhodnější je nechat přiřadit rovnou všechny vektory, vyhneme se tak citlivému nastavování hranice, kdy už se dá považovat algoritmus za ukončený. Pro účely této aplikace to stačí, jelikož v mých 32

možnostech je vytvořit maximálně desítky vektorů. K dodržení původního znění algoritmu stačí uložit hodnotu, kterou vrací metoda update, a následně ji porovnat s mezní hodnotou.

3.1.1.6. TextVectorBuilder Tato třída využívá funkcí knihovny wvtool.jar k sestavení vector space modelu využitého při adaptaci jednak u textového obsahu článků a jednak u textového popisu fotografií. Obsahuje veřejné metody na načtení textu ze souboru či parametru typu String. Třída si po načtení vstupu na disk uloží word list se všemi slovy, která se ve vstupu vyskytovala. Výsledek bylo původně možné pouze uložit do souboru. Doplnil jsem tedy funkci vracení vytvořeného modelu jako návratovou hodnotu (třída WVTModule.WordVectorViewer). Jiné úpravy potřeba nebyly.

3.1.2. WebAdaptation Jak již bylo řečeno, aplikace je vytvářena pomocí SpringFramework a je rozdělena do 4 balíčků: Balíček

Popis

Obsah

controller

Řídí veškeré procesy, využívají služeb managerů a nahrávají data do modelů pro view (stránky jsp)

ArticleController, GalleryController, LoginController, LogoutController, RegistraceController

service

pracující s business objekty. Pro jejich získání a ukládání využívají služeb příslušných objektů z balíčku jdbc

AdaptationLoader, ArticleManager, LoginValidator, ModelAdapter, PhotoManager, RegistrateValidator, UserManager, SimpleArticleManager, SimpleModelAdapter, SimplePhotoManager, SimpleUserManager

domain

business objekty

Article, Navigation, Photo, Rating, User

jdbc

mapují business objekty do relační databáze

JdbArticleDao, JdbcPhotoDao, JdbcUserDao, ArticleDao, PhotoDao, UserDao

Tabulka 4: Struktura aplikace WebAdaptation

SpringFramework si vynucuje dodržení struktury Model View Controller (MVC): Model – tvořen balíčky service, domain a jdbc View – sem patří všechny .jsp stránky obsažené v projektu Controller – vše z balíčku controller 33

3.1.2.1.

Views

View je termín, kterým se označuje výstup aplikace. Může to být například konzole či klientské okno. Zde je forma výstupu webová stránka. Struktura stránky je vždy stejná, existuje jakoby šablona s hlavním obsahem aktuální stránky a do ní se vloží soubory head.jsp a tail.jsp. Důvod, proč nejsou stránky strukturované pomocí vhodných technologií, je vysvětlen v kapitole 4.1.2.4.

3.1.2.2.

Registrace

Registrace probíhá podle zažitého standartu. Uživatel klikne na odkaz register a controller Dispatcher, kde je mimo jiné nastavené, kterému kontroleru se předá řízení, předá požadavek na Login odvozený od SimpleFormController. Ten nabídne jako formView stránku s formulářem register.jsp, kde uživatel vyplní svoje jméno, heslo, věk a pohlaví. Nebylo nutné zjišťovat více údajů, stačilo by vlastně pouze jméno a heslo. Údaj o pohlaví nabízí jen omezené možnosti, které jsou poslané v podobě modelAndView do formView a tam zobrazeny v rolovacím seznamu. Za zbytečné jsem považoval i zdvojené pole pro zadání hesla, kdyby se uživatel překlikl, jelikož v této aplikaci nejsou informace důvěrné.

Údaje jsou při odeslání zvalidovány beanou RegistateValidator, která implementuje rozhraní Validator obsažené ve Springu. Nakonec dojde k ověření, jestli nick zadaný uživatelem již existuje v databázi a jestli ne, je vytvořen nový uživatel. Zde možná trochu nezvykle není uživatel automaticky přihlášen po svém vytvoření. Umožňuje to ale jednomu uživateli zaregistrovat několik nových uživatelů, aniž by se odhlásil.

Pomocí vzoru Depency Injection poskytuje Spring controleru odkaz na třídu UserManager, která manipuluje s beanou User a pro práci s databází využívá objekt UserDao, který mapuje beanu User do relační databáze. UserManager i UserDao jsou pouze rozhraní vynucující si určité metody. Je tedy snadné je vyměnit za jiné objekty a aplikace je tak snadno modifikovatelná.

3.1.2.3.

Přihlašování - původní

Zde bude popsáno, jak bylo původně navrženo přihlašování. Když již není dále používáno, jeho zdrojové soubory jsou stále součástí projektu. Přihlašování umožňuje identifikovat uživatele bez používání sessionalizace. Funguje podobě jako registrace. O řízení průběhu se stará controller Login odvozený od třídy SimpleFormController. Při procesu přihlašování uživatel vyplní jméno 34

a heslo, která si nastavil a odešle požadavek. Login controller nejdříve spustí LoginValidator a nakonec se pokusí pomocí objektu UserManager najít uživatele v databázi. Pokud se shoduje jméno a heslo, uživateli se do session uloží celý objekt User z databáze. Samotné session jsou přístupné z objektu HttpServletRequest request, který je jako parameter v handleru požadavku zpracování formuláře. Uložení celého modelu uživatele v session má jisté výhody. Vždy se dá rychle dostat k některým jeho parametrům jako je jeho největší hodnocení apod., aniž by se musela znovu předávat hierarchie požadavků do databáze. Samozřejmě ale model uživatele uložený v session neobsahuje všechny informace jako například jeho jednotlivá hodnocení či předchozí navigaci.

Důležitou skutečností při přihlašování je, že UserManager ukládá uživateli do proměnné session unikátní vygenerované číslo. Vzniká jako časová známka dělená modulem 10 8 . Jedinou možností, jak by dva uživatelé dostali stejné číslo je, že se přihlásí ve stejnou sekundu či přesně za tři a čtvrt roku, což je vzhledem k povaze aplikace velmi nepravděpodobné. Účelem tohoto unikátní čísla je, jak název napovídá, zjistit, které záznamy navigace patří k jednomu sezení, jelikož se jim tato informace ukládá do záznamu v databázi.

3.1.2.4. Přihlašování – nová verze Tak, jak bylo původně přihlašování zamýšleno, neodpovídalo dnešnímu trendu přihlašování. Dnes se nejvíce používá přihlašovací dialog umístěný v blízkosti ovládacích prvků, který je součástí všech stránek. Je to sice jen designová změna, ale použití frameworku Spring situaci komplikuje. Dialog sestávající ze dvou vstupních textových polí a jednoho odesílacího tlačítka je ve výsledku tvořen jako prvek HTML form. Spring má zabudovanou podporu pro formuláře, která funguje tak, jak je popsána v původní verzi přihlašování. Nejpodstatnější část celého procesu byla, že existoval kontroler typu SimpleFormController, který dostal vstup z formuláře, data zpracoval a výsledek odeslal. Avšak má-li být přihlašování součástí všech stránek, jak zajistit spouštění tohoto kontroleru ?

Nejlepším řešením by bylo složit výslednou stránku z více jiných zdrojů. Například technologie Java Server Pages umožňuje použít značku <jsp:include />, která vkládá obsah jiného souboru. Problém ale je, že se nespustí požadovaný controller. Přestože řídící kontroler ve frameworku Spring má nadefinován mapování url adresy na kontrolery a ty až poté vrací příslušný view, použití značky <jsp:include /> tento efekt nemá.

35

Dále se nabízelo řešení integrováním dalšího frameworku Apache Tiles [13]. Účelem tohoto frameworku je umožnit skládání výsledné stránky z více zdrojů, které jsou nejdříve vráceny svými kontrolery. Přestože framework je cíleně vytvořen pro framework Struts, je možné ho použít i pro Spring. Jeho integrování je snadné, stačí vytvořit šablony pro stránky pomocí speciálních značek a poté jen konfigurační soubor, ve kterém si přiřadíte šablonám soubory, které se do nich mohou vložit. Jediný problém, který nastal je nekompatibilita knihoven s verzí Springu 2.5. I přes to, že na internetových fórech se objevily pokusy o řešení, nepovedlo se mi Apache Tiles zprovoznit.

Možnou záchranou se mohl stát jiný framework – Sitemesh [14], který byl často k Tiles přirovnáván. Po jeho zprovoznění a několika tutoriálech jsem ale zjistil, že úkolem tohoto frameworku je jen „dekorovat“ stránky. To znamená, že Sitemesh je jen filter, který dostane stránku vrácenou kontrolerem, odstraní z ní některé značky jako head a body a čáti obsahu vlepí do uživatelem připravené šablony. Dá se tak rychle změnit obecný vzhled stránek, ale opět se vždy spouští jen jeden kontroler pro stránku. Problém se tím neřeší.

Vzhledem k malému počtu stránek, které aplikace obsahuje, jsem se rozhodl udělat přihlašovací dialog jako součást souboru head.jsp bez podpory frameworku. Znamená to, že nikde není kontroler, jehož jediným úkolem by bylo zachytit data z formuláře. Kód pro obsluhu přihlašovacího dialogu jsem umístil (nakopíroval) do ostatních kontrolerů (galleryController a artikleController). Ztratil jsem tak podporu validace ze strany Frameworku, ale jako dočasné řešení to funguje.

3.1.2.5.

Odhlašování

Odhlašování je velmi jednoduchá procedura. Má svůj kontroler a pokud je uživatel přihlášen, okamžitě vymaže jemu příslušnou session, čímž bude považován za nepřihlášeného. Pokud se také v databázi najde chybějící záznam ukončení navigace pro nějaký článek, bude ukončena s aktuálním časem. Více bude uvedeno v kapitole o navigaci.

3.1.2.6. Hodnocení fotek Galerie je zobrazována v gallery.jsp a jejím kontrolerem je GalleryController, který tentokrát neimplementuje

SimpleFormController,

ale

jen

Controller.

Důvodem

proč

nepoužít

SimpleFormController je, že se shoduje formView a successView a není třeba použít validující beanu, jelikož uživatel pouze klikne na tlačítko (html input typu button) podle volby ohodnocení. 36

Tedy ani není použit žádný objekt pro formulář jako commandClass. Všechny hodnoty jsou čistě poslané metodou POST a zpracované v metodě kontroleru handleRequest.

Prvním úkolem kontroleru je zjištění, jestli je uživatel přihlášen. To zjistí jednoduše – má-li uživatel v session uložený svůj model. V případě že uživatel není přihlášen, nebude moci hodnotit fotografie, jelikož nebude mít k dispozici tlačítka na přiřazení počtu bodů.

Pokud je tedy uživatel přihlášen a existují poslané parametry rating_value a rating_id, znamená to, že uživatel hodnotil fotografii. GalleryController využije služeb svého servisu PhotoManager a ten prostřednictvím svého objektu PhotoDao nechá uložit záznam o ohodnocení do tabulky všech hodnocení. Ovšem pokud uživatel hodnotí jednu fotografii vícekrát, je nejdříve nalezen záznam pro konkrétního uživatele a fotografii a ten je přepsán. Pro fotografii se naleznou v databázi všechna její hodnocení od všech uživatelů a je jí vypočítán průměr hodnocení. Dále jsou uživateli přes servis UserManager vypočítány a uloženy dvě hodnoty: maximální a průměrné hodnocení. Jsou užitečné pro adaptování a jejich zjišťování na místě by bylo příliš drahé.

Dále se volá metoda pro adaptaci hodnocení. Její fungování bude popsáno v kapitole Adaptace 4.1.2.6. Jen zde prozradím, že při adaptování se znovu nahrají všechna hodnocení všech uživatelů z tabulky, provede se na nich klusterovací algoritmus a všechna doporučení jsou uložena do databáze do příslušných tabulek. Poté jsou hodnocení znovu načtena z databáze pomocí metod objektu AdaptaionLoader a controller je přidá do modelAndView pro .jsp stránku. Důvodem pro nadbytečné ukládání a načítání z databáze je kromě přehlednosti snadná modularita programu, kdy se dají vyměňovat celé komponenty. Posledním krokem je vytvoření Mapy indexů a k nim přiřazených hodnot ohodnocení aktuálním uživatelem. Ta je využita pro barevné odlišení tlačítka hodnocení, aby uživatel věděl, jak hodnotil poslední fotografii.

Při hodnocení fotografie dochází vždy k novému nahrání stránky gallery.jsp, přičemž prohlížeč je nastaven na začátek stránky, tedy nikoliv tam, kde byla posledně hodnocená fotografie. Je to neduh frameworku. Jisté řešení spočívá v pamatování si poslední hodnocené fotografie a při jejím vykreslování v gallery.jsp k ní přidat html kotvu. Poté již stačí vytvořit javascriptovou funkci, která na kotvu přesměruje ihned po načtení stránky.

37

3.1.2.7.

Navigace

Obecný pojem navigace v tomto případě je trochu zavádějící, jelikož se neuplatní sledování všech navštívených stránek uživatelem na webu ale pouze vyžádané stránky v sekci articles. Principiálně se to ale neliší, pouze by byla část kódu zkopírována i na další stránky.

Za proces navigace je zodpovědný ArticleController implementující třídu Controller ze Springu. Stejně jako GalleryController se nejdříve zjišťuje, jestli je uživatel přihlášen. Absence přihlášení nelimituje uživatele při procházení články, jen se nenahrává jeho sekvence navštívených stránek a nic se mu tedy nedoporučuje.

Je-li nastaven atribut id, znamená to, že uživatel si vyžádal článek s tímto identifikátorem. Dále je-li uživatel přihlášen, UserManager nechá uložit

do tabulky navigací nový záznam

s identifikátorem uživatele, číslem stránky, číslem uživatelova session získaném při přihlášení a časovou známkou, která zaznamenává dobu započetí čtení nového článku. Zároveň pokud existuje článek ve stejné session, který nebyl uzavřen (tedy předchozí článek), je uzavřen nyní se současnou časovou známkou. Dá se tak zjistit, jak dlouho si uživatel článek četl, ačkoliv jsem tuto informaci k adaptaci nevyužil. Nabízí se otázka, co se stane, když uživatel si prohlíží článek a poté klikne na jinou stránku než articles.jsp ? Ačkoliv se nic nestane, když doba čtení článku není ukončená, přidal jsem kód na uzavření doby čtení i do ostatních stránek.

Nyní nic nebrání spuštění metody na adaptaci navigace v objektu ModelAdaptation. Vytvořené adaptace se načtou z objektu AdaptationLoader a vloží se do ModelAndView výsledné stránky articles.jsp, kde budou zobrazeny. Nakonec se pomocí servisu ArticleManager načtou z databáze všechny články (pouze jejich nadpisy, aby se zbytečně nezabírala paměť) a obsah konkrétně vybraného článku.

3.1.2.8.

Adaptace

Samotná adaptace jak hodnocení tak navigace je vytvářena v objektu SimpleModelAdaptation, který implementuje rozhraní ModelAdaptation. Ta mu nutí naimplementovat dvě funkce makeNavigationAdaptation a makeRatingAdaptation, tedy to opravdové minimum. Tato třída plně využívá služeb knihovny wordvectorcreation.jar a má k dispozici UserManager, ArticleManager i PhotoManager.

38

3.1.2.9. Adaptace hodnocení První co se stane, než se provede samotná adaptace je, že se vymaže výsledek adaptace předchozí. Je tomu tak, aby se nemuselo odlišovat v databázi, který záznam patří ke které adaptaci. Nebylo to nejspíš těžké rozlišit pomocí uživateli již přidělené unikátní session, ale historie adaptace hodnocení se udržovat nepotřebuje. Zde tedy dochází k jistému zjednodušení oproti plánování aplikace v kapitole 3.4.2.

Adaptace hodnocení se vlastně skládá ze tří způsobů, jak doporučit fotografie. Prvním adaptací je doporučení fotografií, které se vyskytují ve společném clusteru hodnotících vektorů, kde každý uživatel je zastoupen pouze jedním vektorem. K tomuto účelu se nejdříve musí vybudovat uživatelské vektory hodnocení. K tomu se do seznamu nahrají všechna hodnocení od všech uživatelů. Zde je důležitá skutečnost, že seznam hodnocení je utříděn podle identifikátoru uživatele ke kterému patří. Velmi to usnadňuje sestavování vektorů. Myšlenka je taková, že postupně se prochází seznam hodnocení a každému novému uživateli, na kterého se narazí, se vytvoří pole, jehož indexy jsou identifikátory fotografií a hodnoty na indexech jsou jejich hodnocení. Jak je to s velikostí onoho pole? To se musí zjistit dopředu. Jeden způsob je, že se dopředu prohlédne celé pole a zjistí se největší budoucí index. Jinou možností je pamatovat si největší index v databázi. Na to by se ale musela vytvořit nová tabulka (například Web) a to prozatím není nutné. Dále během vytváření vektorů je vhodné uložit si do proměnné vektor aktuálního uživatele, tedy toho který nás bude nakonec zajímat. Po zhotovení vektorů se tyto přidají do vytvořeného objektu algoritmu k-means a poté se spustí klustrovací algoritmus. Ještě před spuštěním je však nutné nastavit vhodný počet výsledných klusterů. Tento úkol je poněkud záludný a bude experimentálně řešen při testování aplikace.

Algoritmus postupně vytvoří klustery a každému vektoru přiřadí odkaz na jeho centroid. Protože máme proměnou s vektorem aktuálního uživatele, můžeme snadno dohledat další vektory, které jsou ve společném klusteru. Tyto vektory hodnocení obsahují ale všechna hodnocení od svého uživatele a my chceme doporučit jen ta, která by se mu líbila. Zde jsem zvolil výběr jen těch fotografií, které mají hodnocení větší či rovno průměrnému hodnocení aktuálního uživatele.

Další adaptací je doporučení nejlepších fotek od nejpodobnějších uživatelů. Ty jsme našli už při předchozí adaptaci. Jsou to vlastníci vektorů, kteří sdílejí stejný kluster s aktuálním uživatelem. Zde se uplatní pamatování si hodnoty nejvyššího ohodnocení v modelu uživatele. Jednoduše se 39

nyní projdou vektory hodnocení nejpodobnějších uživatelů a vyberou se z nich jen ty fotografie, které byly ohodnoceny jejich nejvyšším počtem bodů.

Posledním druhem adaptace hodnocení je nalezení fotografií nejpodobnějších poslední z hodnocených založeném na podobnosti textového popisu fotografie. To sebou přináší vytvoření nových textových vektorů. Jejich vytvoření je snadné, stačí načíst do seznamu všechny fotografie a jejich vektory jsou již uloženy v databázi ve formě textu. Jeho formát je: „index slova : počet výskytů ; index slova : počet výskytů ;…“ Stačí tedy rozdělit tento řetězec podle středníků a následně podle dvojteček. Je nutné ještě každému vektoru přiřadit jeho vlastníka. Opět se hotové vektory nastaví do klusterovacího algoritmu, zapamatuje se chtěný vektor a algoritmus se spustí. Tentokrát se z výsledného klusteru mohou vzít všechny hodnoty nebo je možné je omezit pouze na kategorii shodnou s posledně hodnocenou fotografií. Dá se všimnout, že ačkoliv vzdálenosti mezi textovými vektory zůstávají pokaždé stejné, počítají se stále znovu a znovu. Jistým a snad i výrazným urychlením by bylo uložení si vzájemných vzdáleností do databáze. Tabulka by to byla rozměrově přibližně 80x80, což je technicky možné, ale stejně se musí počítat vzdálenosti vektorů k centroidu, který je po každém updatu jiný. Bylo by jen málo případů opravdového zrychlení.

Aby bylo možné rozlišit jakého druhu je nová adaptace, má v databázi uložen několikaznakový popis způsobu vytvoření ( desc, othersBest, content…). To je využito objektem AdaptationLoader při nahrávání jednotlivých adaptací do ModelAndView.

3.1.2.10. Adaptace navigace Stejně jako v případě adaptace hodnocení i zde se předchozí záznamy v databázi vymažou a vytvoří se nové. Zde se vytvoří pouze dva druhy adaptace. První adaptací je doporučení článků z navigačních vektorů, které jsou ve stejném klusteru jako kterýkoliv navigační vektor aktuálního uživatele. Sestavit navigační vektor je trochu obtížnější, než tomu bylo v případě hodnotícího vektoru, ale princip zůstává. Zde platí, že každý uživatel může mít více navigačních vektorů. Každý takový vektor odpovídá sekvenci stránek navštívených během jednoho sezení v daném pořadí. Nejprve jak se sestaví vektory. Do seznamu se uloží všechny záznamy z tabulky Navigation, přičemž i zde je nutné je nahrát setříděné podle uživatele. Postupně se prochází seznam a kdykoliv se narazí na nového uživatele, je mu vytvořena kolekce Map obsahující klíče 40

typu long hodnoty k nim typu List . Klíče jsou hodnoty session, které uživatel dostává při přihlášení. Tedy co záznam v Map, to celé jedno sezení. Sekvence identifikátorů stránek, kterou uživatel v jednom sezení prošel se zapíše do List. Všechny vektory od jednoho uživatele jsou vytvořeny ve chvíli, kdy byly takto zpracovány všechny jeho navigační záznamy. To nastane právě tehdy, když se při procházení záznamů narazí na nového uživatele. Jelikož jako výsledek budeme chtít všechny vektory, které jsou ve společném klusteru s kterýmkoli vektorem aktuálního uživatele, musíme si všechny jeho vektory uložit pro pozdější použití. Po zpracování navigačních záznamů se všechny vektory přiřadí do klustrovacího algoritmu (zde stále k-means), nastaví se počet výsledných klusterů a algoritmus se spustí. Nyní se projde seznam uložených vektorů aktuálního uživatele, přes odkazy se získají jejich centroidy a od těchto centroidů jim přiřazené vektory. Odstraní se duplikace a výsledek se uloží do databáze do tabulky adaptací.

Druhou adaptací je doporučení článku založeném na podobnosti vzhledem ke svému obsahu. Postup je naprosto identický s postupem uvedeným při nacházení podobných fotografií podle textového obsahu jejich popisu, jelikož jejich uložené textové vektory byly vytvářeny stejnou metodou (objektem TextVectorBuilder ve wordvectorcreation.jar).

3.2. Databáze Aplikace si udržuje model uživatele i informace o svém obsahu v relační open source databázi Apache Derby verze 10.3.1.4. Výhodou této databáze je její malá velikost na pevném disku (kolem 2mb) ,jednoduchost instalace (součást prostředí NetBeans 6.1) a také možnost zakomponování ovladače org.apache.derby.jdbc.ClientDriver do jakéhokoliv Java projektu. Naopak nevýhodou může být neimplementace všech funkcí, které nabízí jiné databáze, např. MySQL. Je to například absence možnosti resetovat auto_increment u identifikátorů či špatná podpora vytváření dočasných tabulek.

Tabulky v databázi byly navržené podobně, jak bylo popsáno již v kapitole 3.8, avšak některé záležitosti byly změněny či vypuštěny. user_model – jsou zde základní údaje o uživateli, především jeho nick a heslo. Pro snadnou čitelnost při testování vytváření uživatelů a práce s nimi jsem zvolil uložení hesla v čitelné podobě tak jak, bylo zadáno. Není použito žádné bezpečností hashování či ‚solení‘. 41

photo – uchovává informace o všech fotografiích umístěných na webu. Uchovává se mnoho údajů od jména po rozlišení, přičemž nejdůležitější je lokace. Ta určuje odkud se nahraje náhled fotky a link na umístění nezmenšeného originálu. Významným atributem je také popis fotografie, na jehož základě probíhá doporučování podobných fotografií. Tedy spíše než na samotný text k tomu slouží textový vektor, který je z něj vytvořen a uložen v atributu vektor. Zde dochází ke změně oproti původně navrhovanému způsobu uložení tohoto vektoru. Ten měl být uložen v tabulce vektor, kde by řádky byly identifikátory dokumentů a sloupce indexy slov seřazené podle uloženého seznamu slov. Hodnotami by pak byly četnosti těchto slov v konkrétním dokumentu. Přehlednější cestou však je nechat uložit textový vektor jako řetězec specifického formátu, který je popsán v rámci kapitoly 4.1.2.7.

article – ukládají se zde články zobrazované na stránce articles.jsp. Každý článek má zde titulek, který slouží jako text linku na článek, krátký popis a poté obsah. Obsah je stejně jako popis u fotografií uložen i ve formě textového vektoru.

rating – zde se nacházejí záznamy o hodnocení fotek uživateli. Co jedno hodnocení, to jeden záznam. Jsou tedy opatřeny identifikátorem hodnotícího uživatele, cílové fotografie, počtem udělených bodů a časovou známkou. Snadno se tak dají dohledat všechna hodnocení jednoho uživatele.

navigation – stejně jako se ukládali jednotlivé záznamy do tabulky rating, zde se ukládají jednotlivé požadavky na články. I struktura je velmi podobná tabulce rating, jen se tu navíc drží číslo sezení, které uživatel dostal při přihlášení. Díky tomu lze zpětně poskládat celou jeho sekvenci navigace. Stačí vybrat ty údaje, které mají stejného uživatele a session, a setřídit je podle start_time.

rating_pattern a navigation_patter – tyto dvě tabulky shodné struktury udržují pouze vypočítané adaptace pro uživatele. Tedy záznamy obsahují identifikátor uživatele, dále identifikátor doporučeného obsahu a typ, který říká, o jaký druh adaptace jde. Na přiloženém CD jsou uložené soubory pro vytvoření a naplnění databáze exportované programem RazorSQL (http://www.razorsql.com). 42

4. Testování Přestože klustrovací algoritmus k-means spolehlivě funguje, nemusí to ještě znamenat, že aplikace plní svůj účel. Otázka správnosti nabízení relativního obsahu má však subjektivní charakter. Jestliže uživatel kladně ohodnotí fotografii a algoritmus najde jinou jí podobnou na základě textového popisu, ještě to neznamená, že se i tato fotografie bude uživateli líbit. Vhodné pro testování by bylo sehnat již hotová data o svých zákaznících od internetové společnosti. Potom by ale tento web musel nabízet přesně stejné služby i se stejným materiálem, což je prakticky neproveditelné. Bude tedy požádáno několik skutečných uživatelů, aby aplikaci otestovali. Na začátku se v databázi nachází 80 fotek, 22 článků, žádní uživatelé ani hodnocení či zachycené navigace.

4.1. Adaptace galerie podle popisu První testování doporučení fotografií bylo navrhnuto tak, že bylo uměle vytvořeno pět uživatelů, kteří kladně hodnotili pouze jednu z kategorií. Toto testování mělo ověřit zda doporučení fotek na základě textového popisu spadá alespoň do stejné kategorie. Tato adaptace má tu výhodu, že zde nedochází ke změně výsledků v závislosti na počtu vytvořených uživatelů a jejich aktivitě, tedy vždy dopadne stejně. Testování probíhalo s použitím funkce založené na skalárním součinu dvou vektorů, jejíž princip je popsán v kapitole 4.1.1.1. Nejdříve bylo uměle vytvořeno pět modelových uživatelů: Nick Jirka Josef Ana Jakub Jana

Password Jirka Josef Ana Jakub Jana

Age 23 25 19 30 35

Sex male male female male female

Hodnotil kladně zvířata automobily záběry z vesmíru přírodní scenérie lidská sídla

Tabulka 5: Pět uměle vytvořených modelových uživatelů

Cílem testování je kromě určení správnosti doporučení také nastavení vhodného počtu konečných klusterů, které se zadávají do klusterovacího algoritmu. Výsledek je silně závislý na této hodnotě.

43

Obrázek 11: Test distribuce všech fotek mezi klustery v závislosti na počtu uživatelů

Na grafu uvedeném výše jsou výsledky klusterování při použití počtu klusterů od 2 do 30. Případ, kdy je jeden kluster nebo naopak je jich příliš, nepřichází v úvahu. Na ose x je zvolený počet klusterů. Na ose y je počet elementů (zde fotografií), které jsou v jednom klusteru, přičemž jeden červený křížek označuje kluster. Můžeme zde například vidět, že byl-li zvolen počet klusterů 6 (na ose x pozice 6), tak vzniklo dohromady 6 klusterů (tolik je dohromady značek) a ty postupně obsahují počet elementů (fotografií) 5, 7, 10, 11, 19 a 33.

Optimální počet klusterů by měl splňovat rovnoměrnou distribuci počtu fotek mezi více klusterů. Proto je špatné, když většina fotek je v jediném klusteru, jelikož se poté doporučí příliš mnoho fotek a tedy i takové, které nejsou příliš obsahově relativní. Naopak také není vhodné mít v každém klusteru jen několik málo fotek, ale je to rozhodně lepší varianta. Díky těmto pravidlům by se výběr měl omezit na klustery od 10 do 20. Zde si jsou výsledky opravdu velmi podobné, a proto jsem zvolil jako vhodný počet klusterů 16. Při otestování vychází uspokojivé výsledky. Naprostá většina fotek spadá do stejné kategorie jako ta, která byla ohodnocena, pouze občas se zatoulá fotka z kategorie jiné. 44

Jak by to vypadalo, když by se do klustrovacího algoritmu vkládali pouze fotografie ze stejné kategorie:

Obrázek 12: Test distribuce fotek z jedné kategorie mezi klustery v závislosti na počtu uživatelů

Každá kategorie obsahuje kolem 16-20 fotografií. Zde se nejlepší distribuce dosáhne počtem klusterů 6. Počet doporučených fotek je vždy kolem 2-4, což má výhodu v tom, že nemusíme ořezávat počet fotek při konečném nahrávání do galerie. Na druhou stranu i fotografie z jiné kategorie by možná bylo vhodné nabídnout. Celkově jsem se přiklonil k variantě nabízet fotografie ze všech kategorií.

4.2. Adaptace galerie podle podobnosti uživatelů Zde přijdou na řadu uměle vytvořené modely uživatelů. Nejprve se zjistí optimální počet klustrů opět tím, že se vyzkouší všechny možnosti a vybere se ta nejvhodnější.

45

Obrázek 13: Závislost optimálního počtu klusterů hodnocení na počtu uživatelů

Tento graf se pojetím liší od předchozích. Na ose x sice stále zůstává přibývající počet uživatelů, ale značka v ose y znázorňuje optimální počet klusterů pro jednoho uživatele. Tedy pro jednu hodnotu x je ve skutečnosti tolik hodnot, kolik bylo uživatelů (tedy x), které zde většinou spadnou do stejné hodnoty. Se stoupajícím počtem uživatelů se nejvhodnější počet klusterů pro většinu uživatelů ustálil na hodnotě 6. Proto nemá smysl vytvářet vzorec s rostoucím průběhem, stačí konstantní funkce počtu klusterů.

Dále se vytvoří nový uživatel a testuje se,zda při hodnocení kladně určité kategorie mu jsou nabídnuty fotky od jednoho z pěti modelových uživatelů, který hodnotil tutéž kategorii. Jak již bylo uvedeno, zde se každému uživateli vytvoří právě jeden vektor hodnocení, určí se klustery a uživateli se doporučí ty fotografie z vektorů v těchto klusterech, které mají hodnocení větší či roven průměru hodnocení aktuálního uživatele. Zde vzniká závislost – čím menší počet bodů uživatel dává, tím více fotek je mu doporučováno, protože jich více projde sítem průměrného hodnocení. Po prvním hodnocení poměrně vysokou hodnotou 5 body se uživatelův vektor ocitl v klusteru s dalšími dvěma vektory obsahujícími dohromady 65 fotografií. Přesto ale žádná 46

z fotografií nedosáhla vysokého průměru 5 bodů a nebyla proto doporučena žádná fotografie v této kategorii adaptace. Po několika hodnoceních, kdy celkový průměr je stažen na 3.66, je nabídnuto již 16 fotografií ze 74 ve třech klustrech. Přestože uživatel, se kterým by podobnost měla být největší, má ve výsledném klusteru svůj vektor, tak nabídka je poněkud rozmanitější, jsou zde všechny možné fotografie. Je to dáno tím, že kluster obsahující 3 vektory hodnocení nabízí naprostou většinu fotografií na webu. Mnoho z nich má výborný průměr, což jim zaručuje, že budou doporučeny. Tedy hlavní příčinou je výsledný kluster a to pravděpodobně proto, že modeloví uživatelé hodnotili téměř všechny fotografie, tudíž bylo snadné dostat se s nimi do společného klusteru. Optimalizace této adaptace spočívá spíše ve vhodnějším a realističtějším modelu testování či možná v samotném principu této kategorie.

Posledním druhem adaptace galerie je doporučení nejlépe hodnocených fotek uživateli ze společného klusteru. Zde již není co optimalizovat, protože jsme to již udělali. Podobní uživatelé byli nalezeni již v předchozím druhu adaptace a tak nezbývá než najít jejich nejlépe hodnocené fotografie a doporučit je. Množství doporučení tedy záleží čistě na tom, jak byli předchozí uživatelé štědří a druhy fotografií jsou rozmanité již z principu.

4.3. Adaptace navigace podle obsahu Adaptace článků podle svého textového obsahu funguje na stejném principu jako s popisem fotografií. Články ale nejsou řazeny do kategorií a bohužel žádné dva články nejsou psané přesně na stejné téma. Tím by se jinak dobře ověřila funkčnost nabízení podobného obsahu. Já sám nejsem odborník v pořizování fotografií a mám v tomto oboru jen omezené možnosti. Ve výsledku lze jen těžko vysledovat, jak moc mají nabízené články podobný obsah.

Při dalším testování jsem narazil na doporučení, která vyhovovala na první pohled už podle názvu (animal photography -> doll photography apod.), ale asi v polovině případů mi byly doporučeny články, u kterých by to takto říci nešlo. Poměrně veliký počet výsledných adaptací bude omezen maximálním počtem při nahrávání do view.

47

I zde setrvává úkol najít vhodný počet klusterů, se kterým opět pomůže graf:

Obrázek 14: Závislost optimálního počtu klusterů obsahu článků na počtu uživatelů

Zde je vidět, že od počtu klusterů 14 a více je ve většině klusterů pouze jeden článek a proto jsou nevhodné. Do počtu 4 se v některých klusterech vyskytuje příliš mnoho článků. Nejvhodnějším číslem by mohlo být 6.

4.4. Adaptace navigace podle podobnosti uživatelů Stejně jako adaptace hodnocení podle podobnosti uživatelů i zde je snaha o nelezení toho správného počtu klusterů v závislosti na počtu uživatelů. I tady je na ose x vzrůstající počet uživatelů a v každém sloupci jsou umístěny klustery od jednotlivých uživatelů, které jsou pro ně nejvhodnější z hlediska distribuce. Křivka má zde velmi podobný průběh a ustaluje se dokonce dříve již u sedmého uživatele. S přibývajícím počtem proto nemá cenu zvyšovat počet klusterů optimální nastavení je 7.

Poslední částí je test nově vytvořeným uživatelem bez jediného záznamu navigace. Po prvním vyžádání článku není v této kategorii adaptace žádná nabídka. Při druhém výběru článku se 48

zobrazilo 12 článků v kategorii adaptace podle podobnosti uživatelů. Při dalším prohlížení článků se celkový počet nabídek drží kolem 13, což je mnoho vzhledem k celkovému počtu článků (23). Je to dáno tím, že k doporučení článků stačí, aby v klusteru byl přítomen jediný navigační vektor aktuálního uživatele. Je možné omezit doporučení například na pouze první takový kluster. Je to ale z praktického hlediska stejně dobrá volba, jako oříznout výsledný počet fotek podle pevně nastaveného množství.

Stejně jako šlo filtrovat fotografie podle jejich hodnocení, i zde se nabízí možnost nechat doporučit pouze ty články, u kterých jejich čtenář strávil nějaké pevně dané množství času. Nastává zde opět problém v metodě testování, jelikož modeloví a poté skuteční uživatelé články víceméně v rychlosti proklikali, tedy nikdo je skutečně nečetl a tak byla hranice času nastavena velmi nízko na 5 sekund (hodnota 5000 ve formátu časové známky). Ve výsledku projde tímto filtrem zhruba každá třetí stránka. V ostrém provozu by samozřejmě limit byl větší v řádu minut.

Obrázek 15: Závislost optimálního počtu klusterů navigace na počtu uživatelů

49

4.5. Testování reálných uživatelů Po umělém vytvoření pěti modelových uživatelů byla aplikace odzkoušena na dalších 8 reálných uživatelích. Jejich aktivita přispěla k tvorbě testů, které měly za úkol optimalizovat klusterovací algoritmus, což bylo popsáno v předchozích kapitolách. Ověření uživatelů jestli adaptace skutečně nabízí vhodný obsah ještě před optimalizací, by nemělo smysl. Většina uživatelů byla proto dotázána až po zhotovení všech testů, aby se přihlásili pod svým profilem a prohlídli si nabízený obsah. Bohužel jejich skoro až náhodné odpovědi nelze graficky či tabulkově reprezentovat a už vůbec ne použít jakoukoliv statistickou metodu. Za subjektivními dojmy samozřejmě stojí i samotný obsah webu, který byl náhodně vybrán z těchto webů: http://nationalzoo.si.edu http://www.exoticcarsite.com http://www.edenpics.com http://www.space.com http://www.gigapxl.org http://photography.about.com http://photos-of-the-year.com

(fotografie) (fotografie) (fotografie) (fotografie) (fotografie) (články o fotografování) (články o fotografování)

Tímto jim děkuji a prohlašuji, že jejich materiál bude použit pouze pro účely prezentace této práce.

50

5. Závěr Při tvorbě bakalářské práce jsem získal mnoho zkušeností jak s programováním v dosud nepoznaném frameworku Spring, tak i analytických znalostí. Právě zde mě překvapilo, jak moc se nakonec může lišit návrh aplikace oproti jejímu skutečnému vývoji. Mnoho záležitostí se zdálo najednou nesmyslných a byl jsem nucen některé záležitosti vypouštět či zjednodušovat.

Během vytváření aplikace jsem si ověřil, že i jakákoliv malá adaptace jiného než statistického charakteru je vykoupena poměrně značnými systémovými prostředky. V algoritmech se vyskytuje mnoho cyklů a výpočty tak mohou webový server při několika současných připojeních zahltit. A to i přes to, že aplikace svou povahou je spíše jednoduchá. Značnou dobu jsem se věnoval naučení a zkoušení samotného frameworku Spring před vlastním započetím práce na bakalářském projektu. Základními dovednostmi byla obsluha formulářů a komunikace s databází. Většina vstupů pomocí formulářů se později ukázala jako nedostačující a byl jsem nucen využívat data posílaná přes HttpServletRequest. Důležité bylo navrhnutí struktury relační databáze pro ukládání modelů uživatele a jejich adaptací. Přesné vytváření modelů bylo umožněno použitím přihlašovacího systému místo náročnějšího procesu sessionalizace. Dalším hlavním úkolem byla vlastní implementace klusterovacího algoritmu uloženého v externí knihovně wordvectortool.jar se všemi příslušnými třídami. Algoritmus K-means patřil k těm jednodušším, přestože žádný z algoritmů nebyl příliš obtížný a většina je dobře popsána v mnoha publikacích. Poslední částí bylo vytvoření uživatelského rozhraní ve formě webové stránky. Těší mne, že tvorbou aplikace jsem si vyzkoušel v praxi většinu stěžejních technologií vyučovaných v mém oboru – HTML, CSS, Javascript , JSP, SQL, UML a samozřejmě Java.

Napadlo mě ještě několik strukturálních změn v knihovně wordvectorcreation, které bych v blízké budoucnosti rád implementoval. Jde především o vytvoření nové třídy Cluster. Té bych svěřil odkazy na její centroid a přiřazené vektory (do teď byly odkazy součástí centroidu). Také se mi nepovedlo nalézt žádnou knihovnu, která by vytvářela výpočet váhy slov na základě zvolených (HTML) tagů, v nichž jsou slova uzavřena. Implementace by zřejmě nebyla těžká, ale nemohl jsem si dovolit strávit v této části více času. Dále by ještě chtělo přidat modulární filtrování výsledků místo přímých omezovacích podmínek. Věřím ale, že i tak je aplikace snadno rozšiřitelná a najde případné využití jako součást dalších prací.

51

Použité zdroje [1]

Adaptive algorithm – Wikipedia [online] http://en.wikipedia.org/wiki/Adaptive_algorithm

[2]

Juan D. Velásquez a Vasile Palade Adaptive web sites

[3]

Ivo Renhberger: Obsahují webové logy bohatství? [online] http://www.lupa.cz/clanky/obsahuji-webove-logy-bohatstvi/

[4]

Rozhodovací stromy [online] http://cyber.felk.cvut.cz/gerstner/teaching/kui/sbirka/3_StrojU.doc

[5]

Decision Trees [online] http://dms.irb.hr/tutorial/tut_dtrees.php

[6]

Decision Tree Problem [online] http://www2.cs.uregina.ca/~dbd/cs831/notes/ml/dtrees/dt_prob1.html

[7]

Bayesian network [online] http://en.wikipedia.org/wiki/Bayesian_network

[8]

K-means algorithm [online] http://en.wikipedia.org/wiki/K-means_clustering

[9]

Radim Jirousek: úvod do teorie bayesovských sítí [online] http://webocrat.fei.tuke.sk/znalosti2005/prez/jirousek.pdf

[10]

Entropy – Wikipedia [online] http://en.wikipedia.org/wiki/Entropy

[11]

Sérgio Anibal de Carvalho Junior Sequence Alignment Algorithms

[12]

Spring http://www.springsource.org

[13]

Apache Tiles http://tiles.apache.org

[14]

Sitemesh http://www.opensymphony.com/sitemesh

52

Obsah CD |-- registating_aktivity.png |-- login_aktivity.png |-- rating_aktivity.png |-- navigating_aktivity.png |-- registration_component.png |-- login_component.png |-- rating_navigation_component.png |-- registration_sequence.png |-- login_logout_sequence.png |-- navigating_sequence.png |-- rating_sequence.png |-- requirements.png |-- database.png |-- bakalarka.pdf |-- databáze_export.zip |-- zdrojove_kody.zip |-- instalacni_instrukce.txt 0 adresářů, 16 souborů

53