Übung 5 - Web Mining

1. Sammeln der Daten (2 Punkte)

1. 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. Benutzen Sie dabei die Breitensuche und ignorieren Sie 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, aber auch die Main-Seite). Sie können Ihre Suche auch durch die selektive Hinzunahme von weiteren Startseiten erweitern, falls Ihnen ihre Seitenbasis zu klein erscheint. Auf der anderen Seite kann es Ihnen auch passieren, daß Sie auf Seiten treffen, die zu viele Links enthalten, die wiederum untereinander nicht sehr verbunden sind. Gehen Sie deshalb auch hierbei wenn nötig selektiv vor oder bearbeiten Sie Ihre Datenbasis nachträglich, wenn sie Ihnen nicht als geeignet erscheint. Möglicherweise sind hier, wie bei Übung 2 gesehen, mehrere Anläufe notwendig.
   Erklären Sie kurz Ihr Vorgehen.
2. 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 Kan­ten der Form P1 -> P2 enthalten, wobei die Knoten P1 und P2 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.
   
3. Stellen Sie nun den gerichteten Graphen graphisch dar. Dabei sollten sowohl die Artikelnamen als auch die Verbindungen gut sichtbar sein. Die in Teilaufgabe 1 angegebenen 100 Seiten führen hierbei meist zu zu großen oder zu komplexen Graphen. Verkleinern Sie deshalb entsprechend die Datenbasis oder wählen Sie einen bestimmten Bereich im Graphen aus. Benutzen Sie für die Erzeugung der Abbildung z.B. graphviz (siehe Hinweis).
   

2. Page Rank und HITS (8 Punkte)

1. Schreiben Sie ein Pro­gramm, das sowohl den Page Rank als auch die von HITS ver­wen­de­ten Hub und Au­thor­i­ty 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 aus­suchen, ob Sie die it­er­a­tive Meth­ode aus der Vor­lesung im­ple­men­tieren oder das Prob­lem in ein Eigen­vek­tor-Prob­lem um­for­mulieren und dieses mit Hilfe einer Lin­ear-Al­ge­bra-Tool­box lösen. Für er­stere Meth­ode ver­wen­den sie als Ab­bruch-Kri­teri­um, dass die Summe der Veränderun­gen der Gewichte klein­er als 1/10000 ist oder bere­its mehr als 10000 It­er­a­tio­nen durch­laufen wurden. Verwen­den 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, der Anzahl der Inlinks und der Outlinks. (1,5P)
2. Setzen Sie auf Ihren Daten die Query "machine learning" ab und vergle­ichen Sie den Page Rank, den Hub und den Au­thor­i­ty Score der Knoten miteinander und mit den In- und Outlinks und in­ter­pretieren Sie dies. Vergle­ichen Sie auch die An­zahl der It­er­a­tio­nen bis zur Kon­ver­genz falls Sie das iterative Verfahren verwenden, bzw. die Laufzeit bei der Optimierungslösung. Beachten Sie auch die Hinweise zur Query am Ende. (1P)
3. 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)
4. 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)
5. Gegeben sei folgendes "wahre" Ranking von Artikeln für die Query "web mining" (nach absteigender Relevanz sortiert):
   Web Mining, Web scraping, Social media mining, Data mining, Text mining, Social web, Social network analysis, Web analytics, Semantic similarity, Document classification, Structure mining, Naive Bayes.
   Berechnen Sie jeweils für die drei Ranking-Verfahren Recall, Precision, Average Precision, und Normalized Dicounted Cumulative Gain. Geben Sie dabei den Rechenweg nachvollziehbar (und überprüfbar) an. Welche Maße eignen sich für den Vergleich der drei Ranking-Verfahren, und wieso? (1,5P)
   Hinweis: Sie können diese Maße auch händisch berechnen.

Hinweise

• Falls Sie Schwierigkeiten mit einzelnen Querys haben oder andere Querys für geeigneter halten, können Sie sich selber passende Querys ausdenken. Erstellen Sie sich im Falle von Aufgabe 2.5 selber ein wahres Ranking (fragen Sie z.B. eine Suchmaschine).
  
• 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.