kap4

Information about kap4

Published on November 20, 2007

Author: Aric85

Source: authorstream.com

Content

Kapitel 4: Linkanalyse für Autoritäts-Ranking:  Kapitel 4: Linkanalyse für Autoritäts-Ranking 4.1 Page-Rank-Verfahren 4.2 Exkurs: Grundlagen aus der Stochastik 4.3 HITS-Verfahren 4.4 Themenspezifisches Page-Rank-Verfahren Verbessertes Ranking durch Autoritäts-Scores:  Verbessertes Ranking durch Autoritäts-Scores Ziel: Höheres Ranking von URLs mit hoher Autorität bzgl. Umfang, Signifikanz, Aktualität und Korrektheit von Information  verbesserte Präzision von Suchresultaten Ansätze (mit Interpretation des Web als gerichtetem Graphen G): Citation- oder Impact-Rank (q)  indegree (q) Page-Rank (nach Lawrence Page) HITS-Algorithmus (nach Jon Kleinberg) Kombination von Relevanz- und Autoritäts-Ranking: gewichtete Summe mit geeigneten Koeffizienten (Google) initiales Relevanz-Ranking und iterative Verbesserung durch Autoritäts-Ranking (HITS) 4.1 Page-Rank r(q):  4.1 Page-Rank r(q) Idee: gegeben: gerichteter Web-Graph G=(V,E) mit |V|=n und Adjazenzmatrix A: Aij = 1 falls (i,j)E, 0 sonst Def.: mit 0 <   0.25 Iterative Berechnung von r(q): Initialisierung mit r(q) := 1/n Verbesserung durch Auswerten der rekursiven Definitionsgleichung konvergiert typischerweise mit ca. 100 Iterationen Satz: Mit A‘ij = 1/outdegree(i) falls (i,j)E, 0 sonst, gilt: d.h. r ist Eigenvektor einer modifizierten Transitionsmatrix 4.2 Exkurs: Markov-Ketten:  4.2 Exkurs: Markov-Ketten Ein stochastischer Prozeß ist eine Familie von Zufallsvariablen {X(t) | t  T}. T heißt Parameterraum, und der Definitionsbereich M der X(t) heißt Zustandsraum. T und M können diskret oder kontinuierlich sein. Ein stochastischer Prozeß heißt Markov-Prozeß, wenn für beliebige t1, ..., tn+1 aus dem Parameterraum und für beliebige x1, ..., xn+1 aus dem Zustandsraum gilt: Ein Markov-Prozeß mit diskretem Zustandsraum heißt Markov-Kette. O.B.d.A. werden die natürlichen Zahlen als Zustandsraum gewählt. Notation für Markov-Ketten mit diskretem Parameterraum: Xn statt X(tn) mit n = 0, 1, 2, ... Exkurs: Eigenschaften von Markov-Ketten mit diskretem Parameterraum (1):  Exkurs: Eigenschaften von Markov-Ketten mit diskretem Parameterraum (1) homogen, wenn die Übergangswahrscheinlichkeiten pij := P[Xn+1 = j | Xn=i] unabhängig von n sind Die Markov-Kette Xn mit diskretem Parameterraum heißt irreduzibel, wenn jeder Zustand von jedem Zustand mit positiver Wahrscheinlichkeit erreichbar ist: für all i, j aperiodisch, wenn alle Zustände i die Periode 1 haben, wobei die Periode von i der ggT aller Werte n ist, für die gilt: Exkurs: Eigenschaften von Markov-Ketten mit diskretem Parameterraum (2):  Exkurs: Eigenschaften von Markov-Ketten mit diskretem Parameterraum (2) Die Markov-Kette Xn mit diskretem Parameterraum heißt positiv rekurrent, wenn für jeden Zustand i die Rückkehr- wahrscheinlichkeit gleich 1 ist und mittlere Rekurrenzzeit endlich: ergodisch, wenn sie homogen, irreduzibel, aperiodisch und positiv rekurrent ist. Resultate über Markov-Ketten mit diskretem Parameterraum (1):  Resultate über Markov-Ketten mit diskretem Parameterraum (1) Für die n-Schritt-Transitionswahrscheinlichkeiten gilt: mit in Matrix-Notation: Für die Zustandswahrscheinlichkeiten nach n Schritten gilt: mit Anfangswahrscheinlichkeiten in Matrix-Notation: (Chapman- Kolmogorov- Gleichung) Resultate über Markov-Ketten mit diskretem Parameterraum (2):  Resultate über Markov-Ketten mit diskretem Parameterraum (2) Jede homogene, irreduzible, aperiodische Markov-Kette mit endlich vielen Zuständen ist positiv rekurrent und ergodisch. Für jede ergodische Markov-Kette existieren stationäre Zustandswahrscheinlichkeiten Diese sind unabhängig von (0) und durch das folgende lineare Gleichungssystem bestimmt: in Matrix-Notation (mit 1n-Vektor ): (Gleichgewichts- gleichungen) Beispiel: Markov-Kette:  Beispiel: Markov-Kette 0: sunny 1: cloudy 2: rainy 0.8 0.2 0.3 0.3 0.4 0.5 0.5 0 = 0.8 0 + 0.5 1 + 0.4 2 1 = 0.2 0 + 0.3 2 2 = 0.5 1 + 0.3 2 0 + 1 + 2 = 1 0 = 330/474  0.696 1 = 84/474  0.177 2 = 10/79  0.126 Page-Ranks im Kontext von Markov-Ketten :  Page-Ranks im Kontext von Markov-Ketten Modellierung des Random Walks eines Web-Surfers durch Verfolgen von Hyperlinks mit gleichverteilten Wahrscheinlichkeiten „Random Jumps“ mit Wahrscheinlichkeit  ergodische Markov-Kette Der Page-Rank einer URL ist die stationäre Besuchswahrscheinlichkeit der URL für diese Markov-Kette. Verallgemeinerungen sind denkbar (z.B. Random Walk mit Back-Button u.ä.) Kritik am Page-Rank-Verfahren: Page-Rank ist query-unabhängig und orthogonal zur Relevanz Beispiel: Page-Rank-Berechnung:  Beispiel: Page-Rank-Berechnung 1 2 3  = 0.2 1 = 0.1 2 + 0.9 3 2 = 0.5 1 + 0.1 3 3 = 0.5 1 + 0.9 2 1 + 2 + 3 = 1  1  0.3776, 2  0.2282, 3  0.3942 T T T T T T 4.3 HITS-Algorithmus: Hyperlink-Induced Topic Search (1):  4.3 HITS-Algorithmus: Hyperlink-Induced Topic Search (1) Idee: Bestimme gute Inhaltsquellen: Authorities (großer indegree) gute Linkquellen: Hubs (großer outdegree) Finde bessere Authorities mit guten Hubs als Vorgängern bessere Hubs mit guten Authorities als Nachfolgern Für Web-Graph G=(V,E) definiere für Knoten p, q V Authority-Score und Hub-Score HITS-Algorithmus (2):  HITS-Algorithmus (2) Iteration mit Adjazenz-Matrix A: x und y sind also Eigenvektoren von ATA bzw. AAT. Authority- und Hub-Scores in Matrix-Notation: Intuitive Interpretation: ist die Cocitation-Matrix: M(auth)ij ist die Anzahl der Knoten, die auf i und j zeigen ist die Bibliographic-Coupling-Matrix: M(hub)ij ist die Anzahl der Knoten, auf die i und j zeigen Implementierung des HITS-Algorithmus:  Implementierung des HITS-Algorithmus Bestimme hinreichend viele (z.B. 50-200) „Wurzelseiten“ per Relevanz-Ranking (z.B. mittels tf*idf-Ranking) Füge alle Nachfolger von Wurzelseiten hinzu Füge für jede Wurzelseite max. d Vorgänger hinzu Bestimme durch Iteration die Authority- und Hub-Scores dieser „Basismenge“ (von 1000-5000 Seiten) mit Initialisierung xq := yp := 1 / |Basismenge| und Normalisierung nach jedem Schritt  konvergiert gegen die Eigenvektoren mit dem betragsgrößten Eigenwert (falls dieser Multiplizität 1 hat) Gib Seiten nach absteigend sortierten Authority-Scores aus (z.B. die 10 größten Komponenten von x) Kritik am HITS-Algorithmus: Relevanz-Ranking innerhalb der Wurzelmenge bleibt unberücksichtigt Verbesserter HITS-Algorithmus:  Verbesserter HITS-Algorithmus Potentielle Schwachstellen des HITS-Algorithmus: irritierende Links (automatisch generierte Links, Spam, etc.) Themendrift (z.B. von „Jaguar car“ zu „car“ generell) Verbesserung: Einführung von Kantengewichten: 0 für Links auf demselben Host, 1/k bei k Links von k URLs desselben Host zu 1 URL (xweight) 1/m bei m Links von 1 URL zu m URLs desselben Host (yweight) Berücksichtigung von thematischen Relevanzgewichten (z.B. tf*idf) Iterative Berechnung von Authority-Score Hub-Score Bestimmung verwandter URLs:  Bestimmung verwandter URLs Cocitation-Algorithmus: Bestimme bis zu B Vorgänger der gegebenen URL u Für jeden Vorgänger p bestimme bis zu BF Nachfolger  u Bestimme unter allen Geschwistern s von u diejenigen mit der größten Anzahl von Vorgängern, die sowohl auf s als auch auf u zeigen (Cocitation-Grad) Companion-Algorithmus: Bestimme geeignete Basismenge um die gegebene URL u herum Wende den HITS-Algorithmus auf diese Basismenge an Companion-Algorithmus zur Bestimmung verwandter URLs:  Companion-Algorithmus zur Bestimmung verwandter URLs Bestimmung der Basismenge: u sowie bis zu B Vorgänger von u und für jeden Vorgänger p bis zu BF Nachfolger  u sowie bis zu F Nachfolger von u und für jeden Nachfolger c bis zu FB Vorgänger  u mit Elimination von Stop-URLs (wie z.B. www.yahoo.com) Duplikateliminierung: Verschmelze Knoten, die jeweils mehr als 10 Nachfolger haben und mehr als 95 % ihrer Nachfolger gemeinsam haben Bestimme Authority-Scores mit dem verbesserten HITS-Algorithmus HITS-Algorithmus zur „Community Detection“:  HITS-Algorithmus zur „Community Detection“ Wurzelmenge kann mehrere Themen bzw. „Communities“ beinhalten, z.B. bei Queries „jaguar“, „Java“ oder „randomized algorithm“ Ansatz: Bestimmung der k betragsgrößten Eigenwerte von ATA und der zugehörigen Eigenvektoren x In jedem dieser k Eigenvektoren x reflektieren die größten Authority-Scores eine eng vernetzte „Community“ Beispiel: HITS-Algorithmus:  Beispiel: HITS-Algorithmus 1 2 3 Wurzel- menge 4 5 6 7 8 Basismenge 4.4 Themenspezifisches Page-Rank-Verfahren:  4.4 Themenspezifisches Page-Rank-Verfahren für verschiedene thematische Klassen (Sport, Musik, Jazz, etc.), wobei jede Klasse ck durch eine Menge Tk einschlägiger Autoritäten charakterisiert ist (z.B. aus Verzeichnissen von yahoo.com, dmoz.org) Kernidee : Ändere den Random Walk durch themenspezifische Random-Jump-Wahrscheinlichkeiten für Seiten aus Tk: mit A'ij = 1/outdegree(i) für (i,j)E, 0 sonst mit (pk)j = 1/|Tk| für jTk, 0 sonst (anstatt pj = 1/n) Verfahren: 1) Berechne für jede Klasse ck thematische Page-Rank-Vektoren rk 2) Klassifiziere Query q (inkl. Kontext) bzgl. Klasse ck  Wahrscheinlichkeit wk := P[ck | q] 3) Der Autoritäts-Score von Seite d ist Experimentelle Evaluation: Qualitätsmaße:  Experimentelle Evaluation: Qualitätsmaße basierend auf Stanford WebBase (120 Mio. Seiten, Jan. 2001) enthält ca. 300 000 von 3 Mio. Seiten aus dmoz.org aus 16 Themen der obersten Stufe von dmoz.org; Link-Graph mit 80 Mio. Knoten und der Größe 4 GB auf 1.5 GHz Dual Athlon mit 2.5 GB Speicher und 500 GB RAID 25 Iterationen für alle 16+1 PR-Vektoren brauchen 20 Stunden Random-Jump-W.  gesetzt auf 0.25 (themenspezifisch?) 35 Test-Queries, z.B.: classical guitar, lyme disease, sushi, etc. Qualitätsmaße: Betrachte Top-k zweier Ranglisten 1 und 2 (k=20) Überlappung OSim (1,2) = | top(k,1)  top(k,2) | / k Kendall's  KSim (1,2) = mit U = top(k,1)  top(k,2) Experimentelle Resultate (1):  Experimentelle Resultate (1) Ranglistenähnlichkeit zwischen den ähnlichsten PR Vektoren: (Games, Sports) 0.18 0.13 (No Bias, Regional) 0.18 0.12 (Kids&Teens, Society) 0.18 0.11 (Health, Home) 0.17 0.12 (Health, Kids&Teens) 0.17 0.11 OSim KSim Präzision für Top-10 (# relevante Dok. / 10) von 5 Benutzern: Standard Themenspezifisch alcoholism 0.12 0.7 bicycling 0.36 0.78 death valley 0.28 0.5 HIV 0.58 0.41 Shakespeare 0.29 0.33 micro average 0.276 0.512 Experimentelle Resultate (2):  Experimentelle Resultate (2) Top-5 für Query-Kontext "blues" (Benutzer wählt Seite aus) (klassifiziert auf arts mit W. 0.52, shopping mit 0.12, news mit 0.08) No Bias Arts Health 1 news.tucows.com www.britannia.com www.baltimorepsych.com 2 www.emusic.com www.bandhunt.com www.ncpamd.com/seasonal 3 www.johnholleman.com www.artistinformation.com www.ncpamd.com/Women's_Mental_Health 4 www.majorleaguebaseball www.billboard.com www.wingofmadness.com 5 www.mp3.com www.soul-patrol.com www.countrynurse.com Top-3 für Query "bicycling" (klassifiziert auf sports mit W. 0.52, regional mit 0.13, health mit 0.07) Standard Recreation Sports 1 www.RailRiders.com www.gorp.com www.multisports.com 2 www.waypoint.org www.GrownupCamps.com www.BikeRacing.com 3 www.gorp.com www.outdoor-pursuits.com www.CycleCanada.com Persönliche Page-Rank-Werte:  Persönliche Page-Rank-Werte Theorem: Seien u1 und u2 persönliche Präferenzvektoren (für Random-Jump-Ziele) und seien r1 und r2 die zugehörigen Page-Rank-Vektoren. Dann gilt für alle 1, 2  0 mit 1 + 2 = 1: 1 r1 + 2 r2 = (1-) A‘ (1 r1 + 2 r2) +  (1 u1 + 2 u2) Korollar: Für einen Präferenzvektor u mit m von 0 verschiedenen Komponenten und Basisvektoren ep mit (ep)i =1 für i=p, 0 für ip gilt: mit Konstanten 1 ... m und für den persönlichen Page-Rank-Vektor r Page-Rank-Gleichung: Ziel: Effiziente Berechnung und Speicherung auf einzelne Benutzerpräferenzen zugeschnittener Page-Rank-Vektoren

Related presentations


Other presentations created by Aric85

bop
13. 04. 2008
0 views

bop

crm
28. 04. 2008
0 views

crm

ACPA NASPA 2007 Culture NEW
29. 10. 2007
0 views

ACPA NASPA 2007 Culture NEW

Pekka Roine
22. 04. 2008
0 views

Pekka Roine

070306shan
17. 04. 2008
0 views

070306shan

weber IntegrationAgents
16. 04. 2008
0 views

weber IntegrationAgents

Eggertsson Presentation
10. 04. 2008
0 views

Eggertsson Presentation

CS2 Hutchison
09. 04. 2008
0 views

CS2 Hutchison

CPB750 LEC
07. 04. 2008
0 views

CPB750 LEC

ADD isahara
30. 03. 2008
0 views

ADD isahara

rddmethodist
27. 09. 2007
0 views

rddmethodist

doc 15 NewYorkFed
27. 09. 2007
0 views

doc 15 NewYorkFed

Seven Wonders
04. 10. 2007
0 views

Seven Wonders

chapter16
07. 10. 2007
0 views

chapter16

Flood Men v Women ppt
10. 10. 2007
0 views

Flood Men v Women ppt

ad
15. 10. 2007
0 views

ad

Fc Expan Under Roosevelt
22. 10. 2007
0 views

Fc Expan Under Roosevelt

DMW MolecularTechniques
15. 10. 2007
0 views

DMW MolecularTechniques

Anti TerrorIHK310805
23. 10. 2007
0 views

Anti TerrorIHK310805

Dura
04. 12. 2007
0 views

Dura

2302aRosaseng
25. 10. 2007
0 views

2302aRosaseng

Chechnya
26. 10. 2007
0 views

Chechnya

Disasters
30. 10. 2007
0 views

Disasters

Avances para Pre RESSCAD2005
22. 10. 2007
0 views

Avances para Pre RESSCAD2005

ekb
14. 11. 2007
0 views

ekb

Lingua
23. 10. 2007
0 views

Lingua

Volkswagen
16. 11. 2007
0 views

Volkswagen

Vermiculture
23. 10. 2007
0 views

Vermiculture

avdiagndesmineraliz
28. 12. 2007
0 views

avdiagndesmineraliz

ch7
01. 01. 2008
0 views

ch7

Principles Ecology
03. 01. 2008
0 views

Principles Ecology

ThermCh03
04. 01. 2008
0 views

ThermCh03

news Fagor 2006
05. 01. 2008
0 views

news Fagor 2006

PRESENTACION PLAN PUEBLA PANAMÁ
22. 10. 2007
0 views

PRESENTACION PLAN PUEBLA PANAMÁ

Ebbing17
15. 10. 2007
0 views

Ebbing17

Prog Lundi
24. 10. 2007
0 views

Prog Lundi

loukachevitch
26. 10. 2007
0 views

loukachevitch

Dendrology
23. 11. 2007
0 views

Dendrology

BalancePasDeDeux
27. 11. 2007
0 views

BalancePasDeDeux

Frye
31. 08. 2007
0 views

Frye

FutureWarfare
28. 02. 2008
0 views

FutureWarfare

mypyramid foodsafety
04. 03. 2008
0 views

mypyramid foodsafety

Chapter 3 tidal wave
11. 03. 2008
0 views

Chapter 3 tidal wave

Dial 325 Social Disorganization
12. 03. 2008
0 views

Dial 325 Social Disorganization

Different mutations
16. 10. 2007
0 views

Different mutations

oks for sugar industry
14. 02. 2008
0 views

oks for sugar industry

copa cogeca thiermann
13. 03. 2008
0 views

copa cogeca thiermann

s Landmasses
26. 03. 2008
0 views

s Landmasses

abou assaleh mitacs04
15. 11. 2007
0 views

abou assaleh mitacs04

Part2 Data Handlin 2 20
20. 06. 2007
0 views

Part2 Data Handlin 2 20

Part1 EGEE intro security
20. 06. 2007
0 views

Part1 EGEE intro security

pakdd 02
20. 06. 2007
0 views

pakdd 02

Morozov
31. 08. 2007
0 views

Morozov

RR08 NIST May
03. 01. 2008
0 views

RR08 NIST May

safer needle devices
20. 06. 2007
0 views

safer needle devices

rocket trajectory
20. 06. 2007
0 views

rocket trajectory

robson reusability guidelines
20. 06. 2007
0 views

robson reusability guidelines

rdfs
20. 06. 2007
0 views

rdfs

rdf lux
20. 06. 2007
0 views

rdf lux

Pwd Hash
20. 06. 2007
0 views

Pwd Hash

power of one
20. 06. 2007
0 views

power of one

plutoplus policy pki 2000
20. 06. 2007
0 views

plutoplus policy pki 2000

pldi04
20. 06. 2007
0 views

pldi04

pki ten years present
20. 06. 2007
0 views

pki ten years present

photonis
20. 06. 2007
0 views

photonis

Oportunidad a la Paz 2036
19. 06. 2007
0 views

Oportunidad a la Paz 2036

Ahorrando vida 1932
19. 06. 2007
0 views

Ahorrando vida 1932

Ahora lo entiendo 1931
19. 06. 2007
0 views

Ahora lo entiendo 1931

sample presentation
19. 06. 2007
0 views

sample presentation

rss
20. 06. 2007
0 views

rss

911554418
26. 03. 2008
0 views

911554418

LexisNexis Academic PASCAL 05
29. 09. 2007
0 views

LexisNexis Academic PASCAL 05

WSS09 Jrroda
26. 11. 2007
0 views

WSS09 Jrroda

IPTV Sep07 Ellzey EMC
29. 10. 2007
0 views

IPTV Sep07 Ellzey EMC

parkes
20. 06. 2007
0 views

parkes

dubna03
31. 08. 2007
0 views

dubna03

Lecture SHS Androids Therapy
19. 10. 2007
0 views

Lecture SHS Androids Therapy

estuaries intro123
23. 10. 2007
0 views

estuaries intro123

Ammosov proposal
31. 08. 2007
0 views

Ammosov proposal

jfklibrary
08. 10. 2007
0 views

jfklibrary

Global History 2005 TV
21. 10. 2007
0 views

Global History 2005 TV

vancouver2004 konstantin klokov
15. 10. 2007
0 views

vancouver2004 konstantin klokov

Osos polares 1912
19. 06. 2007
0 views

Osos polares 1912

1996 pCO2 intercomparison
09. 10. 2007
0 views

1996 pCO2 intercomparison

popl05
20. 06. 2007
0 views

popl05

Sacred Sites in Laojunshan
11. 10. 2007
0 views

Sacred Sites in Laojunshan

518 presentation
02. 11. 2007
0 views

518 presentation

antigo
22. 10. 2007
0 views

antigo

phone2
13. 10. 2007
0 views

phone2

pkcs13 proposal
20. 06. 2007
0 views

pkcs13 proposal

pkcs1
20. 06. 2007
0 views

pkcs1

SPANL 07
24. 10. 2007
0 views

SPANL 07

PresJosephineWiggall Lazarus
20. 03. 2008
0 views

PresJosephineWiggall Lazarus

vidya amrita
15. 10. 2007
0 views

vidya amrita

music entertainment
12. 10. 2007
0 views

music entertainment

Siemens in Russia
31. 08. 2007
0 views

Siemens in Russia

present2
20. 06. 2007
0 views

present2

Musulm anbekov
31. 08. 2007
0 views

Musulm anbekov

Part42
01. 12. 2007
0 views

Part42