Websemantik

sagt aus, Dokumente im selben Cluster ähnlich in Bezug auf die Relevanz der Information verhalten und daher den Informationsabfruf (Suchanfrage) verbessern

Clustern von Dokumten aus dem Corpus vorab

wenn eine Abfrage in ein Dokument d matcht retourniere auch die anderen Dokumente deselben Clusters

Geschwindigkeit des VektorspaceModell wird erhöht

Bessere Suchergebnisse in Such-Applikationen (siehe Grafik)

Bessere Navigation in Suchergebnissen

Schnelligkeit: (schnelle Antwortzeit)

Flexibilität: (Web-Inhalt ändert sich ständig)

user-orientiert: Hauptziel ist es für Benutzer richtige Info zu finden

Was als Input zu verwenden:?

• gesamtes Dokument
• Strukturinfos (links)
• Benutzung von stoppwortlisten, stemming

Wie Ähnlichkeit definierten:?

• Inhalt (Vector-Space-Modell)
• Link-Analysis
• Usage-Statistics

Wie werden ähnlich dokumente gruppiert, gruppen gelabelt?

Darstellung des clustering: Dokumentendarstellung? Vector Space? Normalization?

Notation für Ähnlichkeit/Distanz nötig:

Ideal wäre semantische Ähnlichkeit

in Praxis:

• Dokumente als Vektoren, Distanzmetriken

Distanzmetriken

• Euklidsche Distanz
• L1 norm
• Cosinus similarität
• Dice Coefficient

siehe Grafik

siehe Grafik

siehe Grafik

Anzahl ist meist a priori festzulegen

Vermeiden von trivalen (zu vielen/zu wenigen Cluster)

Finden von Clusteranzahl ist Teil des Problems!

Bestrafung bei zu vielen Clustern:

• Definiere einen doc-Benefit als cosinus Ähnlichkeite zu dessen Zentroid.
• Definiere TotalBenefit als Summe aller doc-Benefits
• für jeden Cluster gibte es einen cost cs ein cluster mit k hat: TotalCost = K *cs
• Definiere V = |TotalBenefit+TotalCost|
• finde das clustering, mit höchsten Wert für V über alle Möglichkeiten von K
  • totaler Benefit sinkt mit steigendem K, kann aber stoppen wenn er nich zuviel sinkt (siehe Grafik)

Partitionsmethode: Konstruiere eine Partition von m Dokumenten in ein Set von K Clusters, die Menge der Dokumente (m) und die Anzahl der Cluster (K) ist vorgegeben.

Aufgabe: finde eine Partition mit K Clusters, welche das Partitionskriterium erfüllen.

Flach: beduetet mit Zufallspartitionierung beginnen, iterativ verfeinern

• Single-pass (inkrementell)
• Modellbasiertes Clustering
• K-means (kann fuzzy c-mein sein)

Dokumente werden als reelwertige Vektoren angenommen

Cluster basieren auf Zentroiden (zentrum oder Durchschnitt) der Punkte innerhalb eines Clusters c

Neuordnung der Instanzen zu Clustern basiert auf der Distanz zum aktuellen Zentroiden

Objective-Function: Minimiere die Totale Summe  der quadrierten Distanzen  jedes Punkts  zu seinem korrespondierenden Cluster Zentroiden

Das globale Optimum zu finden ist NP-Hard.

K-Means konvergiert garantiert zu einem lokalem Optimum.

Algorithmus:

• Selektiere K zufällige Dokument (s₁,s₂,...S_k) als Seeds
• Solange Clustering konvergiert, oder stoppkriterium eintritt führe aus:
  • for each doc d_i
    • Assign di to cluster c_j sodaß die distanz(xi,s_j) minimal ist
    • update alle seeds zum zentroiden jedes Clusters
  • for each cluster c_j berechne
    • s_j=mu(c_j)

Üblicherweise wird jede Instanz hart einem Cluster zugeordnet --> erlaubt Zugehörigkeit zu mehrerern Clustern--> Soft clustering ermöglicht das.

Fuzzy C-Means ist eine Methode des clusterin, welche es erlaubt das eine daten zu mehr als einen cluster gehören.

Jede Instanz ist mit einer Wahrscheinlichkeitsverteilung über eine Menge von erforschten Kategorien zuordenbar (siehe Grafik)

die Warhscheinlichkeit aller Kategorien muss 1 ergeben

K-Means ist spezialfall des EM.

EM=Wahrscheinlichkeits-methode für Softclustering.

Algorithmus:

1. zufälle Zuweisung v. wahrscheinlichkeitskategorie Labels

2. Benutze Standard Naive bayes Trainung jum das Wahrscheinlichkeitsmodell  mit Parameter theta von den gelabelten daten zu lernen

3. bis zur Konvergenz/Stoppkriterum:

Expectation (E-Step) Benutze das naive Bayes Model um P(ci|E) für jede Kategorie und Beispiel zu berechnen, relable jedes Beispiel unter verwendung der Wahrscheinlichkeitswerte als soft-kategorie Labels (basierend auf den vorherig ermittelten Wahrscheinlichkeitswerten)

Maximization (M-Step): Benutze standard naoive Bayes training um die parameter theta zu ermitteln unter Verwendung der neuen wahrscheinlichkeits-kategorielabel.

benutze EM in einem semi-supervised Mode durch Lernen von EM sowohl auf labeld als auch auf unlabeld Daten.

Trainiere initiales Wahrscheinlichkeitsmodell auf user-labeled Untermenge von daten anstatt auf willkürlich ausgewählten Daten.

Label der user-labeld werden eingefroren" -> nie relabeled

Labels von unsupervised Daten werden ständig von EM Wahrscheinlichkeit relabled.

Hierarchisch

Agglomertativ Hierarchisches clustern (HAC)

Jedes Dokument formt initial einen Cluster, dann wird wiederholt das näheste Datenpaar verbunden , bis nur ein Cluster übrigbleibt.

Historie des Zusammenführens formt einen Binärbaum oder Hierarchie.

Algorithmus:

1. starte mit allen Instanzen als eigener Cluster

2. Bis es nur noch einen Cluster gibt:

Zwischen allen Clustern ermittle jene zwei Cluster c_i und c_j, die sich am ähnlichsten sind

Ersetze c_i und c_j durch einen vereinten Cluster von c_i und c_j

Laufzeitkomplexität:

alle Ähnlichkeiten von m Instanzen in erster Iteration berechnen O(m²)

in jeder folgenden m² Merging Operation muss die Distanz zwischen den aktuell erzeugten Cluster und allen anderen clustern berechnet werden daher konstant gehalten werden. Laufzeit daher insgesamt entweder O(m³) oder O(m^{2 l}og m) - wenn es clever gemacht wird.

Single-Link: benutze minimale Ähnlichkeit der Paare

Complete-Link: Benutze maximale Ähnlichkeit der Paare

Zentroid: Clusters dessen Zentroid am meisten cosinusähnlich sind

Average-Link: durchschnittliche Ähnlichkeit aller Paare der gemergten Cluster

verbindet HAC u. K-Means (siehe Grafik)

Suffix Tree Clustering:

Linear, inkrementell, überlappend

Algorithmus:

1. Cleaning

Stemming, Satzgrenzenerkennung, Satzzeicheneliminierung

2. Suffix Baum Konstruktion

produziert Basis Cluster (interne Knoten), die mit sore welcher auf größe und Phasenscore (welcher anhand dessen Länge und Wortqualität bestimmt wird)  versehen

3. mergen von Basis Cluster

stark überlappenende Zusammenmergen

Self-Organizing-Map (SOM)

Latetn Semantisches Indizieren (LSI):

auch Singular value Dekomposition (SVD), reduziert die Dimensionalität des Vektorraums (siehe Grafik)

Hart: jedes Dokument gehört zu genau einem Cluster

üblicher in Praxis, einfacher

Weich: ein dok kann zu mehr als einem Cluster gehören

macht sinn bei Applikationen die durchsuchbare Hierarchien haben.

Interne Kriterien:

• intra-Klassen Ähnlichkeit hoch
• inter-Klassen-Ähnlichkeit niedrig
• vom verwendeten Ähnlichkeitsmaß 

Externe kriterien:

• Reinheit (Purity) = Rate der dominaten Klassen innerhalb eines Clusters
• Entropie der Klassen eines Clusters (siehe Grafik)
• Rand-Index für Paarentscheidungen

Beispiele siehe Grafiken

HAC u. K-Means können direkt auf Texte angewendet werden

normalisierte tf/idf gewichtete Vektoren und kosinusähnlichkeiten werden verwendet

Clusteranwendungen in IR:

während des Abrufs werden andere als die initalen dokumente dem Cluster hinzugefügt um den wiederaufruf zu verbessern

clusterung der Ergebenisse des Abrufs, um dem Benutzer ein besser organisiertes Ergebnis zu liefern

automatische erzeugung hierarischer Taxonomien von dokumen zum durchforsten (yahoo..)