Dobývání znalostí z webu web mining

Dobývání znalostí z databází

T15: web mining

Dobývání znalostí z webu – web mining „Web Mining is is the application of data mining techniques to discover patterns from the Web“ (Wikipedia) Tři oblasti: Web content mining (web jako kolekce dokumentů) – analogie s text mining Web structure mining (web jako graf) Web usage mining (web jako „dálnice“ na které probíhá provoz)

P. Berka, 2011

1/13


T15: web mining

Obsah webu (web content mining) Cílem získat znalosti na základě webovských stránek chápaných jako dokumenty (tedy jako text mining): vyhledávání a metavyhledávání (tj. hledání stránek relevantních k dotazu uživatele), kategorizace dokumentů (shlukování stránek podle obsahu) nebo filtrování (tj. rozpoznání stránek relevantních k uživatelově profilu), dobývání znalostí “skrytých” ve stránkách (extrakce informací nebo zodpovídání dotazů).

1. vyhledávání

P. Berka, 2011

2/13


T15: web mining

2. metavyhledávání simultánní přístup k více (klasickým) vyhledávacím strojům: přístup k vyhledávacím systémům neznámým pro uživatele jednotný interface následné zpracování nalezených odkazů

All-in-one: seznam vyhledávačů

P. Berka, 2011

3/13


T15: web mining

MetaCrawler: použití více (všech známých) vyhledávačů

SavvySearch: použití více (některých) vyhledávačů

P. Berka, 2011

4/13


T15: web mining

HuskySearch: shlukování nalezených dokumentů

AskJeeves: báze přímých odpovědí

P. Berka, 2011

5/13


T15: web mining

3. extrakce informací named entity recognition

comparison shopping - podpora nakupování na Internetu (hledání cenově nejvýhodnější nabídky v on-line katalozích)

Netbot Jango

P. Berka, 2011

6/13


T15: web mining

Struktura webu (web structure mining) web jako graf, kde uzly jsou dokumenty (stránky) a hrany jsou vazby (odkazy) mezi stránkami. HITS (Kleinberg, 1998) hubs (rozcestníky) a authorities (autority)

a(p) :=

h(q) q

h(p) :=

p a(q)

p

q

rekurzivní algoritmus počítající obě hodnoty (pouze) pro stránky získané jako výsledek konkrétního vyhledávání (systém Clever).

Nalezením rozcestníků a autorit můžeme redukovat část webu pokrývající dané téma do podoby bipartitního grafu.

P. Berka, 2011

7/13


T15: web mining

PageRank (Brin, Page, 1998) webové stránky „bodovány“, hodnocení každé stránky je dáno hodnocením stránek, které na tuto stránku odkazují PR( A)

(1 d ) d

PR(Ti ) C (Ti )

...

PR(Tn ) C (Tn )

kde: A je stránka, pro kterou se počítá PageRank Ti jsou stránky odkazující na stránku A C(Ti) je počet odkazů na stránce Ti d je tlumící faktor

rekurzivní algoritmus počítající hodnotu pro všechny webové stránky (Google)

Webové komunity P. Berka, 2011

8/13


T15: web mining

Využívání webu (web usage mining) Web jako prostor, ve kterém uživatelé prohlížejí jednotlivé stránky 1. analýza web server logů (časová data, sekvence navštívených stránek) remotehost

rfc931

Auth [date] user

"request"

status

bytes

bacuslab.pr.mcs.net - - [01/Jan/1997:12:57:45 -0600] "GET /~bacuslab/ HTTP/1.0" 304 0 bacuslab.pr.mcs.net - - [01/Jan/1997:12:57:49 -0600] "GET /~bacuslab/BulletA.gif HTTP/1.0" 304 0 bacuslab.pr.mcs.net - - [01/Jan/1997:12:57:50 -0600] "GET /~bacuslab/Email4.gif HTTP/1.0" 304 0 151.99.190.27 - - [01/Jan/1997:13:06:51 -0600] "GET /~bacuslab HTTP/1.0" 301 -4 151.99.190.27 - - [01/Jan/1997:13:06:52 -0600] "GET /~bacuslab/ HTTP/1.0" 200 1779 151.99.190.27 - - [01/Jan/1997:13:06:54 -0600] "GET /~bacuslab/BLI_Logo.jpg HTTP/1.0" 200 8210 151.99.190.27 - - [01/Jan/1997:13:06:54 -0600] "GET /~bacuslab/BulletA.gif HTTP/1.0" 200 1151 151.99.190.27 - - [01/Jan/1997:13:06:54 -0600] "GET /~bacuslab/Email4.gif HTTP/1.0" 200 3218

Předzpracování – nalezení clickstreamů, sekvencí stánek navštívených jedním uživatelem během jedné seance např. Discovery Challenge ECML/PKDD 2005 unix time ;IP address

; session ID

; page request; referee

1074589200;193.179.144.2 ;1993441e8a0a4d7a;/dp/?id=124 1074589201;194.213.35.234;3995b2c0599f1782;/dp/?id=182 1074589202;194.138.39.56 ;2fd3213f2edaf82b;/ 1074589233;193.179.144.2 ;1993441e8a0a4d7a;/dp/?id=148 1074589245;193.179.144.2 ;1993441e8a0a4d7a;/sb/ 1074589248;194.138.39.56 ;2fd3213f2edaf82b;/contacts/ 1074589290;193.179.144.2 ;1993441e8a0a4d7a;/sb/

;www.google.cz; ; ;www.seznam.cz; ;/dp/?id=124; ;/dp/?id=148; ; /; ;/sb/;

clickstream pro typ stránky: dp,dp,dp,sb,sb clickstream pro produkt: 124,182,148

segmentace nabízených produktů P. Berka, 2011

9/13


T15: web mining

asociace mezi navštívenými stránkami

lidé používající fulltextové vyhledávání se méně dívají na detaily zboží

P. Berka, 2011

10/13


T15: web mining

predikce následující stránky - lze na základě pozorované sekvence A1A2…An-1 určit následující stránku An?

markovský model

n

P( A1 A2 ...An )

pravidla dp, sb -> sb (0.93)

P( Ai | Ai

k 1

...Ai 1 )

i 1

podobnost mezi sekvencemi

segmentace návštěvníků

P. Berka, 2011

11/13


T15: web mining

2. analýza nákupního košíku internetových obchodů

3. recommender systems – systémy, které doporučují (co koupit, jaké stránky navštívit apod.) na základě chování podobné skupiny návštěvníků – collaborative filtering

amazon

P. Berka, 2011

12/13


T15: web mining

MovieLens

last.fm

P. Berka, 2011

13/13

Dobývání znalostí z webu web mining

Recommend Documents