3.4.5.2: Berechnung von Dokumentclustern und ihrer Zentroide

Die Dokumente werden in Cluster zusammengefasst. Das geschieht mit der single pass Methode:

1. Setze die Menge der Cluster C=Ø
2. Für ein neues Dokument d berechne die Ähnlichkeiten zu den Zentroiden aller Cluster cC und füge d zu allen Clustern hinzu, bei denen die Ähnlichkeit zum Zentroid größer als eine vorgegebene Schranke ist. Berechne für diese Cluster den Zentroid nach der Formel

   

   neu.
3. Falls d zu keinem Cluster hinzugefügt wurde, eröffne einen neuen Cluster mit dem einzigen Element d . Setze dessen Zentroid auf d . Gehe nach Schritt 2.

Dieses Verfahren liefert Cluster, in denen ähnliche Dokumente zusammengefasst sind und die sich überlappen können. Es wird vor allem verwendet, um den Zugriff auf Dokumente zu beschleunigen. Dazu wird eine Anfrage zunächst mit den Zentroiden der Cluster verglichen. Ein Vergleich mit Dokumentvektoren findet dann nur noch in dem Cluster statt, dessen Zentroid dem Anfragevektor am ähnlichsten ist.

Dieses Verfahren kann auch mehrstufig angewendet werden, indem die Cluster einer Ebene wieder zu Clustern einer höheren Ebene zusammengefasst werden.

Damit dieses Verfahren effektiv ist, sollten die Cluster alle eine ähnliche mittlere Größe haben. Um das zu erreichen kann man

• zu große Cluster durch ein neues single pass Verfahren innerhalb des Cluster aufspalten
• zu kleine Cluster mit dem ähnlichsten Cluster vereinigen
• bei zu großem Overlap zwischen zwei Clustern, diese entweder zusammenfassen oder Elemente aus dem Overlap aus einem der Cluster entfernen

Die Verwendung von Dokumentclustern als Zugriffsverfahren scheint zur Zeit nicht weiterverfolgt zu werden.