Clustering: Klassifikation ohne vorgegebenes Klassifikationssystem

Das Clustering von Dokumenten basiert auf der Ermittlung von Ähnlichkeit bzw. Differenz von Dokumenten nach vorgegebenen Merkmalen. Eine einfache Form der Bestimmung von Merkmalen ist das Vorkommen gemeinsamer Deskriptoren. In der Praxis berücksichtigen die Systeme viele zusätzliche Eigenschaften wie Wortlänge, Distanz von Wörtern usw. Der Einfachheit halber gehen wir für die weiteren Überlegungen von automatisch (z. B. auf der Grundlage der Termfrequenz (tf)) oder intellektuell ermittelten Deskriptoren aus.

Schauen wir uns dazu zunächst nocheinmal die Tabelle aus LE 9 an. Diesmal allerdings nicht im binären Werten (0 oder 1), sondern mit Werten, die sich aus tf*idf ergeben.

Schlagwort	Dok 1	Dok 2	Dok 3	Dok 4
Student	0,5	1	0	1
Protest	1	0,5	2	1
Sparmaßnahme	1	3	0	1
Sternmarsch	1	0	1,5	1
Senat	2	0	1	2

Zunächst werden alle Dokumente einer begrenzten Ausgangsdatenmenge paarweise miteinander multipliziert. Auf diese Weise erhält man eine Dokument-Dokument-Ähnlichkeitsmatrix. Im Anschluss wird ein Schwellenwert festgelegt; alle Dokumentpaare, die diesen Wert überschreiten werden gruppiert. Die Werte in der Tabelle unten stehen für das jeweilige Ergebnis des Skalarproduktes der Vektoren der verglichenen Dokumente (z.B. für das Skalarprodukt zw. Dok 1 und Dok 2 könnte das so aussehen: 4,0 = 0,5*1 + 1*0,5 + 1*3 + 1*0 +2*0

	Dok 1	Dok 2	Dok 3	Dok 4	Dok x
Dok 1	-	4,0	4,5	7,5	???
Dok 2	4,0	-	1,0	4,5	???
Dok 3	4,5	1,0	-	4,5	???
Dok 4	7,5	4,5	4,5	-	???
Dok x	???	???	???	???	-

Wenn wir nur die vier eingetragenen Dokumente vergleichen, erhalten wir bei einem Schwellenwert von 7,5 ein Cluster, das aus den Dokumenten 1 und 4 besteht. Bei einem Schwellenwert von 4,5 würden alle 4 Dokumente in das Cluster aufgenommen, obwohl Dokument 2 und 3 nur wenige Übereinstimmungen haben. In der Praxis würde man natürlich mit wesentlich mehr Dokumenten arbeiten und hätte nach diesem ersten Arbeitsschritt eine ganze Reihe von Clustern.

Diese Cluster würden folgendermaßen weiterverarbeitet. Für die Dokumente eines Clusters wird ein sogenannter Zentroidvektor ermittelt. Der Zentroidvektor ergibt sich aus dem Mittelwert aller Dokumentvektoren des Clusters. In der Tabelle sehen Sie, wie der Zentroidvektor für das Cluster aus den Dokumenten 1, 3 und 4, die durch die Vektoren "Studenten, Protest, Sparmaßnahmen, Demonstration, Senat", dargestellt werden, aussähe. Dieser Zentroidvektor repräsentiert jetzt die Klasse der drei aufgeführten Dokumente.

	Studenten	Protest	Sparmaßnahmen	Demonstration	Senat
Vektor Dok 1	0,5	1	1	1	2
Vektor Dok 3	0	2	0	1,5	1
Vektor Dok 4	1	1	1	1	2
Zentroidvektor	1,5/3 = 0,5	4/3 = 1,33	2/3 = 0,66	2,5/3 = 0,83	5/3 = 1,66

Wenn jetzt in der Datenbank ein neues Dokument mit den Deskriptoren Studenten, Protest, Sparmaßnahmen, Demonstration, Senat ergänzt wird, wird dieses nicht mit dem Vektor aller 4 Dokumente verglichen, sondern nur mit dem Zentroidvektor.

 

Clustering ist ein mehrstufiger Prozess

1. Zunächst wird eine Ausgangskonfiguration aus einigen wenigen Clustern erstellt, für die jeweils ein Clusterrepräsentant, also ein Zentroidvektor, ermittelt wird.
2. Neu hinzukommende Dokumente werden mit allen Clusterzentroiden verglichen.
3. Das Cluster mit der maximalen Ähnlichkeit wird ermittelt und das Dokument wird in das Cluster integriert. Wenn Überlappungen zwischen den Clustern erlaubt sind, wird das Dokument in alle Cluster integriert, für die der Ähnlichkeitswert einen bestimmten Schwellenwert überschreitet.
4. Nach der Dokumentzuweisung müssen die Clusterzentroiden neu berechnet werden. In einem nächsten Bearbeitungsschritt werden die Schritte 2 bis 4 erneut durchlaufen.
5. Das Verfahren wird nach einer vorher festgelegten Anzahl der Wiederholungen der Schritte 2 bis 4 beendet.

Auf diese Weise erhalten Sie eine Reihe disjunkter oder sich überschneidender Cluster, die allerdings noch keine Benennung haben. Verschiedene Verfahren der Benennung sind denkbar. Im einfachsten Fall werden der oder die am stärksten gewichteten Deskriptoren des Zentroidvektors als Benennung des Clusters ausgegeben.

Quelle: Salton, Gerard; McGill, Michael: Information Retrieval - Grundlegendes für Informationswissenschaftler. - Hamburg u. a.: Mc Graw-Hill Book Company Gmbh, 1987, S. 228-236.

In der Abbildung sehen Sie zwei Beispiele für Cluster zum Thema Studenten Protest Sparmaßnahmen Demonstration aus der Suchmaschine Carrot2. Je nachdem, in welchem Bestand (Web (links) oder Wiki (rechts)) Sie suchen, unterscheiden sich die Cluster und ihre Benennungen.

Abb.: Ausschnitt Clusterergebnisse carrot2. Suche nach Studenten Protest Sparmaßnahmen Demonstration im gesamten Web (links) oder in Wikis (rechts). - Stand: 27.06.13

Stand: 6. Juni 2018

< Seite drucken >
< Zum Seitenanfang >

STEP 1 - Einführung | STEP 2 - Initialaufgabe | STEP 3 - Lektüre | STEP 4 - Übung 1| STEP 5 - Übung 2