Übung 5 - Web Mining

1. Sammeln der Daten

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. Ignorieren Sie dabei alle Links auf 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. Seien Sie auch mit der Anzahl der heruntergeladenen Kategorie-Seiten sparsam. Wenn Sie diese Hinweise befolgen, sollten sie bei Breitensuche und einer Tiefe von 1 auf etwa 100 Artikel kommen.
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 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

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.
   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.
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 und in­ter­pretieren Sie diese. Vergle­ichen Sie auch die An­zahl der It­er­a­tio­nen bis zur Kon­ver­genz.
3. Wählen Sie eine geeignete Query und zeichnen Sie den Root-Set und den Base-Set. Geben Sie 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?
4. Gegeben sei folgendes "wahre" Ranking von Artikeln für die Query "web mining":
   Web Mining, Information retrieval, Data mining, Text Mining, Natural language processing, Internet, Naive Bayes classifier, Weka (machine learning), Biomedical text mining, Data stream mining, Rapidminer, Hyperlink.
   Berechnen Sie jeweils für die drei Ranking-Verfahren Recall, Precision, Average Precision, und Normalized Dicounted Cumulative Gain. Welche Maße eignen sich für den Vergleich zwischen den drei Ranking-Verfahren?
   Hinweis: Sie können diese Maße auch händisch berechnen.
5. Berechnen Sie zusätzlich für jedes ermittelte Ranking die normalisierte Kendall tau Distanz zu dem wahren Ranking. Kendall Tau zählt die Knotenpaare, die im vorhergesagten Ranking eine unterschiedliche Ordnung haben als im wahren Ranking. Betrachten Sie dabei nur Artikel, die in beiden Rankings vorkommen. Wie fällt jetzt der Vergleich zwischen den Ranking-Verfahren aus?
6. In unseren Voruntersuchungen genoß der Artikel Data Mining im Allgemeinen einen hohen Page Rank und landete deshalb bei den meisten Querys ganz oben und besonders noch vor der offensichtlich besten Seite, nämlich die, die genauso heißt wie die abgesetzte Query (vgl. "web mining"). Wieso ist das so und wie ließe sich dieses Problem beheben.

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.4 und 2.5 selber ein wahres Ranking.
• Sollten Sie ernste Schwierigkeiten mit der Bearbeitung der ersten Aufgabe haben, greifen Sie auf unsere Version des Datensatzes zu. graph.dot enthält die Kanten und node.dict das Mapping von Artikelnummer zu Artikelname.
• Für die Zeichnung des Graphen bietet sich die Software graphiz an, welches in der Lage ist, selbständig aus der Angabe von Knoten eine ansehnliche Zeichnung zu erstellen.
• Um die Wikipedia zu crawlen und zu parsen bietet sich für Java die Java Wikipedia Library des UKP Labs an.