Übung 5 - Web Mining

1. Sammeln der Daten (2 Punkte)

1. Laden Sie sich ausgehend eines von Ihnen ausgewählten englischen Wikipedia-Artikels 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). 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 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.
   
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. Clustering (2/2/1.5/2.5 Punkte)

1. Wenden Sie k-Means auf Ihre Datenbasis an. Implementieren Sie hierfür den k-Means Clustering Algorithmus. Sie sollten dabei in der Lage sein, sowohl Parameter k als auch die Anfangsmittelpunkte der Cluster (Seeds) frei bestimmen zu können. Welche Ähnlichkeits- bzw. Distanzfunktion und welche Featurerepräsentation Sie verwenden bleibt dabei Ihnen überlassen (Beschreiben Sie kurz.). Sie sollten diese aber idealerweise von Ihren Daten abhängig machen.
   Wählen Sie für einen ersten Durchlauf ein vernünftiges k (z.B. im Bereich von 5-15 je nach Gesamtanzahl der Artikel und resultierenden Cluster-Größen) mit zufälligen Artikeln als Seeds. Achten Sie darauf, nur die Artikeltexte zu verwenden, also z.B. nicht die Namen der Wikipedia-Kategorien am Ende eines Artikels.
   
2. In­ter­pretieren Sie die Par­ti­tion­ierung für Ihr k (aus Teilaufgabe 1). Ergeben die Cluster Ihrer Meinung Sinn? Kann man anhand der Cluster z.B. Themenkomplexe identifizieren?
   Überlegen und entwickeln Sie nun ein Verfahren, um den Clustern automatisch Namen oder Beschreibungen zu geben. Betrachten Sie für jeden Clus­ter z.B. die wichtig­sten Wort-Fea­tures (z.B. die Fea­tures mit dem höchsten Gewicht­sun­ter­schied zu an­deren Clus­tern). Sie können hierbei z.B. auch die Wikipedia-Kategorien nutzen.
3. Stellen Sie Ihre Partitionierung graphisch dar. Benutzen Sie hierfür z.B. die bereits produzierte Darstellung aus Aufgabe 1. Sie können die verschiedenen Cluster z.B. farblich voneinander unterscheiden.
   Wie sehr korrelieren Partitionierung und Link-Struktur? Können Sie hier einen Zusammenhang ausmachen?
4. Untersuchen Sie die Robustheit des k-Means-Verfahrens. Wiederholen Sie dafür das Clustering mit unterschiedlichen, zufälligen Seeds (mind. 10-20 Duchläufe). Identifizieren Sie die Artikelpaare, die am häufigsten zusammen in einem Cluster landen. Für welche Paare geschieht dies am seltensten? Stellen Sie diese Mengen graphisch dar. 
   Entspricht das Ergebnis Ihren Erwartungen?
   Gab es Auffälligkeiten in ihren Durchläufen, z.B. immer wieder auftretende Cluster oder häufiges Auftreten von Clustern mit nur einem oder sehr wenigen Artikeln? Was sagt dies über die Robustheit des Verfahrens aus?

Hinweise

• 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. Zusätzlich erlaubt das Tool relativ einfach Einfärbung und Beschriftung von Knoten und es sollte für den gleichen Eingabegraphen (aber z.B. unterschiedlicher Beschriftung oder Kolorierung) stets die gleiche Anordnung und Platzierung der Knoten wählen.
  
• 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. Beachten Sie aber trotzdem die Hinweise in Aufgabe 1 zu der Eignung der Datenbasis für die Aufgabe.
  
• Die Wikipedia überprüft den User-Agent beim Herunterladen von Seiten. Bedenken Sie dies, falls Sie ungewöhnliche Daten erhalten.