Clustering von Text-Dokumenten

Abgabe: bis 11.7.2010

Implementieren Sie den k-Means Clustering Algorithmus wie in der Vorlesung besprochen:

• Überführen Sie die Dokumente in eine (normalisierte) TF-Darstellung (kann idealerweise von früheren Aufgaben übernommen werden).
• Verwenden Sie als Ähnlichkeits- bzw. Distanzfunktion die Euklidische Distanz.
• Nehmen Sie als anfängliche Cluster-Mittelpunkte (Seeds) k zufällig ausgewählte Dokumente.
• Terminieren Sie den Algorithmus wenn sich die Partitionen nicht mehr ändern.
  

Testen Sie den Algorithmus an einer Klassifikations-Aufgabe Ihrer Wahl mit zumindest etwa 100 Dokumenten (z.B. aus den Datensätzen früherer Aufgaben).

1. Probieren Sie mehrere, unterschiedliche k aus, von k=1 (sozusagen als triviale Baseline) bis zumindest k=2*Anzahl der Originalklassen. Messen Sie die Qualität des Clusterings anhand des folgenden Maßes:
   Anteil der Dokument-Paare N_t, die sich sowohl im Klassifikationsdatensatz als auch in der berechneten Partitionierung 
   • in der gleichen Klasse/im gleichen Cluster befinden (N_p)
   • in unterschiedlichen Klassen/Clustern befinden (N_n).
   D.h. die Beziehung zwischen zwei Dokumenten "in gleicher Klasse" sollte idealerweise sowohl im Datensatz als auch im Clustering für alle Paare gleich sein.
   Welches k erreicht den höchsten Wert N_t und wie steht diese Clusteranzahl im Verhältnis zur originalen Anzahl der Klassen?
   Wie entwickeln sich N_p und N_n in Abhängigkeit von k, und wie die Anzahl der benötigten Iterationen?
   Tragen Sie diese Entwicklungen idealerweise in einen Graphen ein.
2. Interpretieren Sie die Partitionierung für Ihr k Optimum. Vergleichen Sie z.B. die gefundenen Cluster mit den originalen Klassifikationen oder betrachten Sie für jedes Cluster die wichtigsten Wort-Features (z.B. die Features mit dem höchsten Gewichtsunterschied zu anderen Clustern) und versuchen Sie aufgrund dessen den Clustern Namen oder Etiketten zu vergeben.
   
3. Probieren Sie unterschiedliche Seed-Strategien aus: Nehmen Sie im ersten Fall die Seeds zufällig aus nur einer Klasse und im zweiten Fall die Seeds (so weit wie möglich) gleichverteilt aus allen Klassen. Vergleichen Sie für beide Fälle N_t und die Verteilung der Clustergrößen. Fixieren Sie Ihr k (z.B. das "beste" aus Aufgabe 1).
4. Versuchen Sie Ihren k-Means Algorithmus zu verbessern. Konzentrieren Sie sich dabei auf einen Aspekt von k-Means, z.B. Verbesserung der Cluster-Qualität, die Anzahl der Iterationen bis zur Konvergenz, mögliches Caching der Distanzberechnungen, die Varianz bei unterschiedlichen Seeds, Balanciertheit der Cluster, die automatische Wahl von k, der hohe Einfluss von Outlier, etc. Evaluieren Sie dementsprechend Ihren Vorschlag im Vergleich zur ursprünglichen Variante.