Ü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 Siee 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 sichtbar sein. Falls Ihnen der Graph für die Darstellung zu groß oder zu komplex erscheint, verkleinern Sie 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/2/2 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. 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). Vergleichen Sie z.B. die gefundenen Cluster mit den Artikelnamen, oder betrachten Sie für jedes Clus­ter die wichtig­sten Wort-Fea­tures (z.B. die Fea­tures mit dem höchsten Gewicht­sun­ter­schied zu an­deren Clus­tern). Statt den Wort-Features könnten Sie hierfür auch die Liste der Wikipedia-Kategorien verwenden.
   Ver­suchen Sie, auf­grund Ihrer Beschreibung der Cluster diesen Namen oder Etiket­ten zu vergeben. Lässt sich dies automatisieren?
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. Pro­bieren Sie un­ter­schiedliche Seed-Strate­gien aus: Wiederholen Sie das Clustering mit unterschiedlichen, zufälligen Seeds. Nehmen Sie im Gegensatz dazu sehr ähnliche Dokumente als Seed, die z.B. in vorherigen Durchläufen dem gleichen Cluster zugeordnet wurden. Vergleichen Sie die unterschiedlichen Partitionierungen, z.B. graphisch. Wie robust ist k-Means bzw. das resultierende Clustering gegenüber unterschiedlicher Initialisierung? Wie robust ist die Partitionierung von einzelnen Dokumentenpaaren, die inhaltlich sehr ähnlich sind?
   

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.