Filtrace web stránek s Filtrace web stránek s využitím profilu uživatelevyužitím profilu uživatele

Petr DoskočilPetr.Doskocil@email.cz

ObsahObsah

ÚvodCílePaketový filtrGenerování uživatelova profiluPersonální vyhledávačZávěr

2Filtrace web stránek s využitím profilu uživatele

ÚvodÚvod

Neustálé zvětšování objemu dat na webuUživatel náročnějšíVyšší nároky na internetové vyhledávačeVyhledávače vracejí miliony relevantních

odkazůPředkládané výsledky jsou řazeny podle

globálních kritériíPotřeba personalizovaného vyhledáváníPodle společnosti Imation jsou ročně

vyprodukovány dva exabajty digitálních dat (532 km DVDček)

3Filtrace web stránek s využitím profilu uživatele

CíleCíle

Vytvoření systému pro určování profilu uživatele

Návrh a vývoj personálního vyhledávačeTestování

4Filtrace web stránek s využitím profilu uživatele

Paketový filtrPaketový filtr

Prostředek pro získání dat charakterizujících uživatele

Získává textový obsah navštívených webových stránek

Síťové pakety jsou odchytávány nad všemi síťovými rozhraními počítače

Nezávislost na použitém prohlížečiZískaná data jsou odesílána prostřednictvím

protokolu HTTP na serverUživatel má kontrolu nad poskytovanými daty

5Filtrace web stránek s využitím profilu uživatele

Prostředek realizaceProstředek realizace

Programovací jazyk JavaKnihovna Jpcap (a Java library for

capturing and sending network packets)

Filtrace web stránek s využitím profilu uživatele 6

Generování uživatelova profiluGenerování uživatelova profilu

Vstupní data◦ Textový obsah uživatelem navštívených webových

stránek (uloženy v databázi)◦ Hloubka Suffix Tree = Maximální délka fráze◦ Jazyk◦ Práh vytváření shluků

Postup vytváření profilu◦ Úprava stránky (odstranění tagů, získání textu, …)◦ Rozpoznání jazyka◦ Lemmatizace slov◦ Odstranění stop-slov◦ Vložení slov stránky do Suffix Tree◦ Získání množiny nejlépe ohodnocených frází◦ Generování shluků frází (zájmové okruhy uživatele)

Filtrace web stránek s využitím profilu uživatele 7

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 8

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Budeme vytvářet Suffix Tree fráze délky 3 => hloubka stromu bude 3

Jsou dány dokumenty

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 9

bratr 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 10

bratr 1

často 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 11

bratr 1

často 1

mýt 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 12

často 1

bratr 1

často 1

mýt 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 13

často 1

bratr 1

často 1

mýt 1

mýt 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 14

často 1

bratr 1

často 1

mýt 1

mýt 1

auto 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 15

často 1

bratr 1

mýt1

často 1

mýt 1

mýt 1

auto 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 16

často 1

bratr 1

mýt1

auto 1

často 1

mýt 1

mýt 1

auto 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 17

často 1

bratr 1

mýt1

auto 1

auto 1

často 1

mýt 1

mýt 1

auto 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 18

často 1

bratr 1

mýt1

auto 1

sestra 1

auto 1

často 1

mýt 1

mýt 1

auto 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 19

často 1

bratr 1

mýt1

auto 1

sestra 1

často 1

auto 1

často 1

mýt 1

mýt 1

auto 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 20

často 1

bratr 1

mýt1

auto 1

sestra 1

často 1

auto 1

často 1

mýt 1

mýt 1

auto 1

řídit 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 21

často 2

bratr 1

mýt1

auto 1

sestra 1

často 1

auto 1

často 1

mýt 1

mýt 1

auto 1

řídit 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 22

často 2

bratr 1

mýt1

auto 1

sestra 1

často 1

auto 1

často 1

řídit 1

mýt 1

mýt 1

auto 1

řídit 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 23

často 2

bratr 1

mýt1

auto 1

sestra 1

často 1

auto 1

často 1

řídit 1

mýt 1

mýt 1

auto 1

auto 1

řídit 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 24

často 2

bratr 1

mýt1

auto 1

sestra 1

řídit 1

často 1

auto 1

často 1

řídit 1

mýt 1

mýt 1

auto 1

auto 1

řídit 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 25

často 2

bratr 1

mýt1

auto 1

sestra 1

řídit 1

auto 1

často 1

auto 1

často 1

řídit 1

mýt 1

mýt 1

auto 1

auto 1

řídit 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 26

často 2

bratr 1

mýt1

auto 2

sestra 1

řídit 1

auto 1

často 1

auto 1

často 1

řídit 1

mýt 1

mýt 1

auto 1

auto 1

řídit 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 27

často 2

bratr 1

mýt1

auto 2

sestra 2

řídit 1

auto 1

často 1

auto 1

často 1

řídit 1

mýt 1

mýt 1

auto 1

auto 1

řídit 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 28

často 2

bratr 1

mýt1

auto 2

sestra 2

řídit 1

auto 1

bratr 1

často 1

auto 1

často 1

řídit 1

mýt 1

mýt 1

auto 1

auto 1

řídit 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 29

často 2

bratr 1

mýt1

auto 2

sestra 2

řídit 1

auto 1

bratr 1

často 1

auto 1

často 1

řídit 1

mýt 1

mýt 1

auto 1

auto 1

často 1

řídit 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 30

často 2

bratr 2

mýt1

auto 2

sestra 2

řídit 1

auto 1

bratr 1

často 1

auto 1

často 1

řídit 1

mýt 1

mýt 1

auto 1

auto 1

často 1

řídit 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 31

často 2

bratr 2

mýt1

auto 2

sestra 2

řídit 1

auto 1

bratr 1

často 1

auto 1

často 2

řídit 1

mýt 1

mýt 1

auto 1

auto 1

často 1

řídit 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 32

často 2

bratr 2

mýt1

auto 2

sestra 2

řídit 1

auto 1

bratr 1

často 1

auto 1

často 2

řídit 1

mýt 1

mýt 2

auto 1

auto 1

často 1

řídit 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 33

často 3

bratr 2

mýt1

auto 2

sestra 2

řídit 1

auto 1

bratr 1

často 1

auto 1

často 2

řídit 1

mýt 1

mýt 2

auto 1

auto 1

často 1

řídit 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 34

často 3

bratr 2

mýt1

auto 2

sestra 2

řídit 1

auto 1

bratr 1

často 1

auto 1

často 2

řídit 1

mýt 2

mýt 2

auto 1

auto 1

často 1

řídit 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Suffix Tree frázeSuffix Tree fráze

Filtrace web stránek s využitím profilu uživatele 35

často 3

bratr 2

mýt2

auto 2

sestra 2

řídit 1

auto 1

bratr 1

často 1

auto 1

často 2

řídit 1

mýt 2

mýt 2

auto 1

auto 1

často 1

řídit 1

1) „bratr často myje auto“2) „sestra často řídí auto“3) „sestra bratra často myje“

Výpočet ohodnocení frázeVýpočet ohodnocení fráze

Z výsledné Suffix Tree struktury následně získáme jednotlivé fráze, jejichž maximální délka je rovna hloubce stromu a na základě vzorce

určíme jejich ohodnocení. Jednotlivé symboly mají následující význam:

F_ohod◦ Ohodnocení dané fráze

F_čet◦ Četnost konkrétní fráze v kolekci dokumentů

N_k,max ◦ Počet výskytů nejčastější fráze délky k v kolekci dokumentů

Filtrace web stránek s využitím profilu uživatele 36

%100max,

k

četohod N

FF

Vytváření shluků frází I.Vytváření shluků frází I.

Z ohodnocených frází, které charakterizují danou kolekci dokumentů, je možné vytvořit shluky frází

Shluky frází představují jednotlivé zájmové oblasti uživatele

Počet shluků, který bude vytvořen není předem známý

Filtrace web stránek s využitím profilu uživatele 37

Vytváření shluků frází II.Vytváření shluků frází II.

Vytváření shluků je založeno na podobnosti frází

Princip je založen na předpokladu, že fráze vyskytující se často v jednom dokumentu jsou podobné

Filtrace web stránek s využitím profilu uživatele 38

Podobnost shlukůPodobnost shluků

Mějme dvě fráze f_a, f_b. Tyto fráze jsou podobné jestliže platí:

D_a Počet dokumentů obsahujících frázi f_a

D_b◦Počet dokumentů obsahujících frázi f_b

k◦Prahová konstanta ovlivňující snadnost vytváření

shluků

Filtrace web stránek s využitím profilu uživatele 39

Vytváření shluků frází III.Vytváření shluků frází III.

Hledáním podobnosti mezi jednotlivými frázemi získáme několik shluků

Podobné shluky sjednotímeVýsledkem je množina shluků frází

reprezentující zájmové oblasti uživateleZískaný zájmový profil je možné použít k

ovlivnění uživatelova dotazu

Filtrace web stránek s využitím profilu uživatele 40

Personální vyhledávač I.Personální vyhledávač I.

Vybraným shlukem (shluky) je možné ovlivnit vyhledávání

Uživatel volí shluk nebo shluky, kterými chce dotaz ovlivnit

Ovlivnění dotazu je prováděno postupným rozšířením dotazu o jednotlivé fráze shluku

Dále zadává hloubku vyhledávání – tj. kolik stránek má personální vyhledávač načítat pro každý rozšířený dotaz

Dalšími parametry jsou např. jazyk hledání, hledání stránek s podobným obsahem, …

Jednotlivé shluky je možné upravovat, nebo vytvářen vlastní

Filtrace web stránek s využitím profilu uživatele 41

Personální vyhledávač II.Personální vyhledávač II.

Obsah jednotlivých načtených stránek je porovnáván s profilem uživatele

Jednotlivým stránkám je přiřazováno skóre hodnotící míru schody s profilem uživatele

Ohodnocené stránky jsou sestupně řazeny podle dosaženého skóre

Uživatel má tak na prvním místě stránku, která nejlépe zapadá do jeho profilu

Filtrace web stránek s využitím profilu uživatele 42

ZávěrZávěr

Generátor profilu by bylo vhodné rozšířit o reklamní filtr

Doba odezvy vyhledávače roste přímo úměrně s počtem načítaných stránek, ale zároveň roste i kvalita předkládaných výsledků

Prakticky se ukazuje, že dotaz ovlivněný vhodně zvoleným shlukem, který zapadá do příslušné zájmové oblasti uživatele, poskytuje výsledky přesněji zapadající do jeho zájmového profilu

Filtrace web stránek s využitím profilu uživatele 43

Konec prezentaceKonec prezentace

Otázky?

Filtrace web stránek s využitím profilu uživatele 44