Übung 5 - Web Mining
Linkbasiertes Seitenranking auf der Wikipedia
1. Sammeln der Daten (2 Punkte)
- Laden Sie sich ausgehend von der Seite http://en.wikipedia.org/wiki/Category:Data_mining
eine Datenbasis an Artikeln und Links zwischen den Artikeln herunter.
Ignorieren Sie dabei alle Spezial-Seiten der Wikipedia, konzentrieren
sie sich im Prinzip nur auf Links innerhalb des Artikeltextes, und
bewegen Sie sich auch nur auf der englischen Wikipedia. Die Anzahl der
heruntergeladenen Artikel sollte dabei nicht viel mehr als 100 betragen.
Filtern Sie nochmals alle Spezialseiten (Im Grunde alle Artikel mit ":"
im Namen, dies schließt Category:Data_Mining mit ein). Wenn Sie diese
Hinweise befolgen, sollten sie bei Breitensuche und einer Tiefe von 1
auf unter 100 Artikel kommen. Sie können Ihre Suche auch durch die
selektive Hinzunahme von weiteren Startseiten erweitern, falls Ihnen
ihre Seitenbasis zu klein erscheint.
Erklären Sie kurz Ihr Vorgehen. - Erstellen Sie basierend auf den heruntergeladenen Daten eine Datei, die einen gerichteten Graphen beschreibt, welches die Linkstruktur innerhalb der Daten beschreibt. Diese Datei kann den Graphen z.B. als Liste von Kanten der Form P1 -> P2 enthalten, wobei die Knoten P1 und P2 Urls bzw. Artikelnamen und die Kante einen Link von der Seite P1 auf die Seite P2 repräsentieren. Beschränken Sie die Knoten (P1 und P2) auch nur auf die heruntergeladenen Artikel, alle anderen Kanten ignorieren Sie.
2. Page Rank und HITS (8 Punkte)
- Schreiben Sie ein Programm, das sowohl den Page Rank als auch die
von HITS verwendeten Hub und Authority Scores berechnet. Eingabe
ist der gerichtete Graph aus Aufgabe 1, die Artikeltexte, und eine Query
in Form einer Konjunktion von Keywords. Sie können sich aussuchen, ob
Sie die iterative Methode aus der Vorlesung implementieren oder
das Problem in ein Eigenvektor-Problem umformulieren und dieses
mit Hilfe einer Linear-Algebra-Toolbox lösen. Für erstere Methode
verwenden sie als Abbruch-Kriterium, dass die Summe der
Veränderungen der Gewichte kleiner als 1/10000 ist oder bereits mehr
als 10000 Iterationen durchlaufen wurden. Verwenden Sie beim Page
Rank d=0.85 als Damping-Faktor. Beim HITS-Algorithmus enthält das
Root-Set alle Artikel, die im Text alle Schlüsselwörter der Query
enthalten. Das Base-Set wird wie in den Vorlesungsfolien konstruiert. Denken Sie auch daran, Links auf sich selbst bei der Berechnung zu ignorieren.
Ausgabe des Programms ist ausgehend vom Graphen, den Artikeltexten und der Query jeweils für jeden Score ein Ranking auf den Knoten im Root-Set zusammen mit dem errechneten Score, den Inlinks und den Outlinks. (1P) - Setzen Sie auf Ihren Daten die Query "machine learning" ab und vergleichen Sie den Page Rank, den Hub und den Authority Score der Knoten miteinander und mit den In- und Outlinks und interpretieren Sie dies. Vergleichen Sie auch die Anzahl der Iterationen bis zur Konvergenz. (2P)
- Wählen Sie eine geeignete Query und zeichnen Sie den Root-Set und den Base-Set. Geben Sie direkt im Graphen die drei erzielten Scores an. Die Query sollte eine übersichtliche Zeichnung erlauben. Decken sich die Scores und der Graph mit der Theorie hinter Page Rank und HITS ab? (2P)
- Setzen Sie für jedes der Wikipedia-Dokumente eine Query ab mit dem Titel als Query, also z.B. "machine learning" für das Dokument "Machine Learning". Berechnen Sie jeweils für Page Rank und beide HITS-Verfahren, an welcher Position das Dokument zu der Query im Ranking erschienen ist und bilden Sie den Durchschnitt über alle Querys. Wie interpretieren Sie die Ergebnisse, decken sie sich mit Ihren Erwartungen, insbesondere bezüglich der verschiedenen Ranking-Verfahren, und wie könnte man die Ergebnisse verbessern. (2P)
- Gegeben sei folgendes "wahre" Ranking von Artikeln für die Query "web mining":
Web Mining, Information retrieval, Data mining, Text Mining, Natural language processing, Document Classification, Naive Bayes classifier, Structure mining, Data stream mining, Data Mining and Knowledge Discovery, Hyperlink.
Dieses Ranking könnten Sie nun mit den Rankings von Page Rank und HITS vergleichen und somit bestimmen, welches Verfahren in diesem Fall am besten funktioniert. Welche der folgenden bekannten Maße eignet sich oder eignet sich nicht für diesen Vergleich und warum: Recall, Precision, Average Precision, und Normalized Discounted Cumulative Gain? (1P)
Hinweise
- Falls Sie Schwierigkeiten mit einzelnen Querys haben oder andere Querys für geeigneter halten, können Sie sich selber passende Querys ausdenken.
- Für die Zeichnung des Graphen bietet sich die Software graphviz an, welche in der Lage ist, selbständig aus der Angabe von Knoten eine ansehnliche Zeichnung zu erstellen.
- Sollten Sie ernste Schwierigkeiten mit der Bearbeitung der
ersten Aufgabe haben, überspringen Sie sie und greifen Sie ersatzweise
auf unsere Version des Datensatzes zu (in dem Fall kann es aber leider keine Punkte für die Aufgabe geben).
graph-filtered.dot
enthält die Knotennamen und Kanten im dot-Format der graphviz sofware. - Die Wikipedia überprüft den User-Agent beim Herunterladen von Seiten. Bedenken Sie dies, falls Sie ungewöhnliche Daten erhalten.