Kontextbasierte Web-Navigationsunterstützung mit Markov-Modellen Sebastian Stober 21. Dezember 2005 Verteidigung der Diplomarbeit

Kontextbasierte Web-Kontextbasierte Web-Navigationsunterstützung mit Markov-Navigationsunterstützung mit Markov-

ModellenModellen

Sebastian StoberSebastian Stober

21. Dezember 200521. Dezember 2005

Verteidigung der DiplomarbeitVerteidigung der Diplomarbeit

21.12.2005 sebastian stober - kontextbasierte web-navigationsunterstützung mit markov-modellen 2

GliederungGliederung

►EinführungEinführung MotivationMotivation KontextKontext Markov-ModelleMarkov-Modelle

►UmsetzungUmsetzung►ErgebnisseErgebnisse►ZusammenfassungZusammenfassung►DemonstrationDemonstration


MotivationMotivation

► Suchmaschinen & Verzeichnisse bieten einem Suchmaschinen & Verzeichnisse bieten einem Nutzer einen guten Einstiegspunkt bei der Suche Nutzer einen guten Einstiegspunkt bei der Suche nach Informationennach Informationen

► Beim Browsen im weiteren Verlauf der Suche ist Beim Browsen im weiteren Verlauf der Suche ist der Nutzer aber immer noch auf sich allein der Nutzer aber immer noch auf sich allein gestelltgestellt

► Idee: Durch Vorhersage, welchem Link ein Idee: Durch Vorhersage, welchem Link ein Nutzer wahrscheinlich folgen wird, kann der Nutzer wahrscheinlich folgen wird, kann der Nutzer bei der Navigation im Web unterstützt Nutzer bei der Navigation im Web unterstützt werden.werden.


KontextKontext

Kontext:Kontext:

BrowserBrowser BrowserfensterBrowserfenster Inhalt des DokumentsInhalt des Dokuments Titel des DokumentsTitel des Dokuments AbsatzAbsatz WortfensterWortfenster AnkertexteAnkertexte AnkertextAnkertext

--OptionenOptionen

TF/iDF- TF/iDF-

DokumentvektorDokumentvektor

--RepräsentationRepräsentation


HistoryHistory

KontexttKontextt-1Kontextt-n+1 …

aktueller Kontext

History der letzten n Kontexte

Kandidaten

History der letzten 2 Kontexte


Markov-ModelleMarkov-Modelle

► Beschreiben stochastische Prozesse mit der Beschreiben stochastische Prozesse mit der Markov-Eigenschaft: Markov-Eigenschaft: Die Wahrscheinlichkeitsverteilung des Die Wahrscheinlichkeitsverteilung des

Folgezustands hängt zu jedem Zeitpunkt Folgezustands hängt zu jedem Zeitpunkt tt nur nur von den von den nn letzten Zuständen ab: letzten Zuständen ab:

P(sP(st+1t+1|s|stt, … ,s, … ,st-n+1t-n+1,s,st-nt-n, … ,s, … ,s00)=P(s)=P(st+1t+1|s|stt, … ,s, … ,st-n+1t-n+1))► Problem bei Modellen höherer Ordnung:Problem bei Modellen höherer Ordnung:

exponentielle Speicherkomplexität exponentielle Speicherkomplexität O(kO(k(n+1)(n+1)) ) für die für die Übergangswahrscheinlichkeiten (Übergangswahrscheinlichkeiten (kk – Anzahl der – Anzahl der Zustände, Zustände, nn – Ordnung des Modells) – Ordnung des Modells)

► Sparsity-Problem bei Betrachtung des Sparsity-Problem bei Betrachtung des gesamten World Wide Webgesamten World Wide Web


Schlußfolgerungen Schlußfolgerungen

►Betrachtung der History der letzten n Betrachtung der History der letzten n Kontexte Kontexte Markov Modell n-ter Markov Modell n-ter OrdnungOrdnung

►Reduktion der Modellgröße notwendigReduktion der Modellgröße notwendig►Eineindeutige Abbildung von Eineindeutige Abbildung von

Kontexten auf Zustände des Modells Kontexten auf Zustände des Modells ist nicht praktikabelist nicht praktikabel



►EinführungEinführung►UmsetzungUmsetzung

SystemüberblickSystemüberblick Lernen des ModellsLernen des Modells VorhersageVorhersage

►ErgebnisseErgebnisse►ZusammenfassungZusammenfassung►DemonstrationDemonstration


SystemüberblickSystemüberblick


SystemüberblickSystemüberblick


Recommender-ModulRecommender-Modul


Lernen des Modells: ClusternLernen des Modells: Clustern

C1C3

C2

► Zusammenfassen ähnlicher Kontexte (Clustern)Zusammenfassen ähnlicher Kontexte (Clustern)

Reduktion der Größe des ZustandsraumesReduktion der Größe des Zustandsraumes Sparsity-ProblemSparsity-Problem

K1 K3 K5

K1 K2 K4 K5

C1 C2 C3

C1 C1 C2 C3

K1

K2

K3 K4

K5




Induktion des Modells 1. Induktion des Modells 1. OrdnungOrdnung

SF

AC

B

FolgeFolge ##

A,B,CA,B,C 33

A,B,DA,B,D 22

E,B,CE,B,C 11

E,B,DE,B,D 11

G,B,CG,B,C 22

G,B,DG,B,D 11

A,B,D,HA,B,D,H 11

E,B,D,HE,B,D,H 33

G,B,D,HG,B,D,H 22

33

33

Übergangshäufigkeit

künstlicher Start- und Endzustand

Beispiel aus: José Borges and Mark Levene. Generating Dynamic Higher-Order Markov Models in Web Usage Mining, PKDD, 2005.




SF

AC

B

D

55

33

22

FolgeFolge ##

A,B,CA,B,C 33

A,B,DA,B,D 22

E,B,CE,B,C 11

E,B,DE,B,D 11

G,B,CG,B,C 22

G,B,DG,B,D 11

A,B,D,HA,B,D,H 11

E,B,D,HE,B,D,H 33

G,B,D,HG,B,D,H 22




SF

AC

B

D

55

44

22

FolgeFolge ##

A,B,CA,B,C 33

A,B,DA,B,D 22

E,B,CE,B,C 11

E,B,DE,B,D 11

G,B,CG,B,C 22

G,B,DG,B,D 11

A,B,D,HA,B,D,H 11

E,B,D,HE,B,D,H 33

G,B,D,HG,B,D,H 22

E

11




SF

AC

B

D

55

44

33

FolgeFolge ##

A,B,CA,B,C 33

A,B,DA,B,D 22

E,B,CE,B,C 11

E,B,DE,B,D 11

G,B,CG,B,C 22

G,B,DG,B,D 11

A,B,D,HA,B,D,H 11

E,B,D,HE,B,D,H 33

G,B,D,HG,B,D,H 22

E

22


Modell 1. OrdnungModell 1. Ordnung


SF

AC

B

D

6 (0,38)6 (1)

6 (0,38) 6 (1)

10 (0,62)

4 (0,40)

FolgeFolge ##

A,B,CA,B,C 33

A,B,DA,B,D 22

E,B,CE,B,C 11

E,B,DE,B,D 11

G,B,CG,B,C 22

G,B,DG,B,D 11

A,B,D,HA,B,D,H 11

E,B,D,HE,B,D,H 33

G,B,D,HG,B,D,H 22

H

E

G

5 (1)

5 (1)5 (0,31)

5 (0,31)

6 (0,60)

6 (1)

Übergangswahrscheinlichkeit P(C|B)




SF

AC

B

D

6 (0,38)6 (1)

6 (0,38) 6 (1)

10 (0,62)

4 (0,40)

FolgeFolge ##

A,B,CA,B,C 33

A,B,DA,B,D 22

E,B,CE,B,C 11

E,B,DE,B,D 11

G,B,CG,B,C 22

G,B,DG,B,D 11

A,B,D,HA,B,D,H 11

E,B,D,HE,B,D,H 33

G,B,D,HG,B,D,H 22

H

E

G

5 (1)

5 (1)5 (0,31)

5 (0,31)

6 (0,60)

6 (1)

CC DD

A,BA,B 0.50.5 0.50.5

E,BE,B 0.20.2 0.80.8

G,BG,B 0.40.4 0.60.6

Überprüfung der induzierten Übergangswahrscheinlichkeiten aller Eingangspfade eines Zustands

B muß geklont werden!ähnlich!


Modell 2. OrdnungModell 2. Ordnung


FolgeFolge ##

A,B,CA,B,C 33

A,B,DA,B,D 22

E,B,CE,B,C 11

E,B,DE,B,D 11

G,B,CG,B,C 22

G,B,DG,B,D 11

A,B,D,HA,B,D,H 11

E,B,D,HE,B,D,H 33

G,B,D,HG,B,D,H 22

SF

AC

D

6 (0,38)

6 (1) 5 (0,45)

6 (0,55)

1 (0,2)

4 (0,8)

B’

B

6 (1)

4 (0,40)

H

E

G 5 (1)

5 (1)

5 (0,31)

5 (0,31)

6 (0,60)

6 (1)

Einfügen des Klons B‘ von B und Anpassen der eingehenden und ausgehenden Kanten




RecommendationRecommendation

► Bei jeder Änderung der History:Bei jeder Änderung der History: Abbilden der History auf das ModellAbbilden der History auf das Modell

►Finden ähnlicher PfadeFinden ähnlicher Pfade►Berechnung von PfadgewichtenBerechnung von Pfadgewichten

(Minimum der Zustandsähnlichkeiten)(Minimum der Zustandsähnlichkeiten) Bestimmung der Wahrscheinlichkeitsverteilung Bestimmung der Wahrscheinlichkeitsverteilung

für den Folgezustand bei gegebener Historyfür den Folgezustand bei gegebener History► Für jeden Kandidaten:Für jeden Kandidaten:

Abbilden auf das Modell (Finden ähnlicher Abbilden auf das Modell (Finden ähnlicher Zustände)Zustände)

Vorschlagen, wenn die Wahrscheinlichkeit für Vorschlagen, wenn die Wahrscheinlichkeit für einen der ähnlichen Zustände mindestens einen der ähnlichen Zustände mindestens θθ istist


Recommendation-BeispielRecommendation-Beispiel Finde ähnliche Finde ähnliche

Zustände für Zustände für KKt-1t-1

►A,C,C‘A,C,C‘ Finde Nachfolger von Finde Nachfolger von AA, ,

CC und und C‘C‘, die , die KKtt ähneln ähneln►B,EB,E

Bestimme Bestimme PfadgewichtePfadgewichte►wwA,BA,B = min(0,7 , 0,9) = 0,7 = min(0,7 , 0,9) = 0,7►wwC,BC,B = min(0,9 , 0,9) = 0,9 = min(0,9 , 0,9) = 0,9►wwC‘,EC‘,E = min(0,9 , 0,8) = 0,8 = min(0,9 , 0,8) = 0,8►wwBB = 0,9 = 0,9►wwEE = 0,8 = 0,8

C

F

ADB

C’

6

4

HE

G

5 (0,5)

2 (0,4)

1

5 (0,5)

4 3 (0,6)0,8

0,9

0,9

0,9

0,7

► Abbilden der History Abbilden der History (K(Kt-1t-1,K,Ktt)) auf das Modell auf das Modell (mit Schwellwert (mit Schwellwert λλ=0,7=0,7):):


Recommendation-BeispielRecommendation-Beispiel► Berechnung der Wahrscheinlichkeitsverteilung für den FolgezustandBerechnung der Wahrscheinlichkeitsverteilung für den Folgezustand

Gewichtete Überlagerung der Wahrscheinlichkeitsverteilungen, die durch die verschiedenen Pfade induziert werden:Gewichtete Überlagerung der Wahrscheinlichkeitsverteilungen, die durch die verschiedenen Pfade induziert werden:

► Behandlung eines Kandidaten Behandlung eines Kandidaten YY:: Finde ähnliche Zustände für Finde ähnliche Zustände für YY (mit Schwellwert (mit Schwellwert λλ=0,7=0,7))

►DD

Wenn Wenn P(D|KP(D|Kt-1t-1,K,Ktt) ) ≥≥ θθ wird wird YY vorgeschlagen vorgeschlagen

HFDX

wwwww

EXPwBXPwECXPwBCXPwBAXPw,KKXP

EBECBCBA

EBECBCBAtt-

,,für

,',,

,',,

,',,1



►KonzeptKonzept►UmsetzungUmsetzung►ErgebnisseErgebnisse

DatensammlungDatensammlung ModellgrößeModellgröße VorschlagquoteVorschlagquote

►ZusammenfassungZusammenfassung►DemonstrationDemonstration


DatensammlungDatensammlung

► Nutzung des FrameworksNutzung des Frameworks► 18. Oktober 18. Oktober

bis 6. Dezember 2005bis 6. Dezember 2005► 8 Nutzer8 Nutzer► 632 Webseiten (106 Hosts)632 Webseiten (106 Hosts)► 216 Klicks (24 Hosts)216 Klicks (24 Hosts)► 75% der Klick-Sequenzen haben höchstens die Länge 375% der Klick-Sequenzen haben höchstens die Länge 3► 15% der Klick-Sequenzen haben mindestens die Länge 15% der Klick-Sequenzen haben mindestens die Länge

88► Datensammlung zu klein für eine Evaluierung der Datensammlung zu klein für eine Evaluierung der

VorhersagegüteVorhersagegüte► Modelle mit Ordnung größer als 3 nicht sinnvollModelle mit Ordnung größer als 3 nicht sinnvoll


ModellgrößeModellgröße

0

50

100

150

200

250

1 2 3 4 5 6 7 8 9 10

Ordnung des Modells

Grö

ße

des

Mo

del

ls

μ=1,0 γ=0,0 μ=0,7 γ=0,0 μ=0,5 γ=0,0 μ=0,2 γ=0,0 μ=0,2 γ=0,3


VorschlagquoteVorschlagquote

0,00

0,20

0,40

0,60

0,80

Vo

rsch

lag

qu

ote

0,05

0,10

0,15

0,20

0,25

0,30

0,35

0,40

0,45 1,0

0,90,8

0,70,6

0,50,4

0,30,2

0,1

λ

θ

Modell 3. Ordnung mit μ=0,5 und γ=0,0


ZusammenfassungZusammenfassung

► Verwendung eines Markov Modells höherer Ordnung Verwendung eines Markov Modells höherer Ordnung zur Vorhersage, ob Link ein von einem Benutzer in zur Vorhersage, ob Link ein von einem Benutzer in einem bestimmten Kontext weiterverfolgt wird oder einem bestimmten Kontext weiterverfolgt wird oder nichtnicht Reduktion der Modellgröße durch Clustern von KontextenReduktion der Modellgröße durch Clustern von Kontexten Erweiterung eines existierenden Verfahrens zur Induktion von Erweiterung eines existierenden Verfahrens zur Induktion von

Modellen mit möglichst geringer GrößeModellen mit möglichst geringer Größe Parametrisiertes Verfahren zum Vorschlagen von KandidatenParametrisiertes Verfahren zum Vorschlagen von Kandidaten Evaluierung mangels genügend großer Datensammlung nicht Evaluierung mangels genügend großer Datensammlung nicht

möglichmöglich► Implementierung eines Frameworks zum clientseitigen Implementierung eines Frameworks zum clientseitigen

Loggen von Benutzeraktionen beim Browsen Loggen von Benutzeraktionen beim Browsen (verwendbar für weitere Arbeiten)(verwendbar für weitere Arbeiten)

► Aufbau einer kleinen DatensammlungAufbau einer kleinen Datensammlung


AusblickAusblick

► Aufbau einer größeren DatensammlungAufbau einer größeren Datensammlung zur Evaluierungzur Evaluierung für andere Arbeiten verwendbarfür andere Arbeiten verwendbar

► Benutzerstudie mit FeedbackBenutzerstudie mit Feedback► Erweiterung des Frameworks durch weitere Erweiterung des Frameworks durch weitere

ModuleModule► Recommendation mit globalem Wissen über Recommendation mit globalem Wissen über

die Datendie Daten► Graphentheoretisch Analyse des gelernten Graphentheoretisch Analyse des gelernten

ModellsModells


DemonstrationDemonstration

Vielen Dank für Ihre Vielen Dank für Ihre AufmerksamkeitAufmerksamkeit

Documents

Kontextbasierte Web-Navigationsunterstützung mit Markov-Modellen Sebastian Stober 21. Dezember 2005 Verteidigung der Diplomarbeit