Post on 15-Jan-2016
description
transcript
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