1a co clustering

Co-clustering: 

Co-clustering Björn Hirsch Seminar Data Mining Prof. Dr. Thomas Hofmann 10.05.2005

Übersicht: 

Übersicht Einführung allgemein einfache Beispiele Co-clustering die Idee konkrete Funktionen Algorithmus Beispiel Ergebnisse

Worum geht es eigentlich?: 

Worum geht es eigentlich? Erfassen von Daten Verarbeiten der Daten Ordnen und Auswerten der Daten Internetverhalten (Surf-Verhalten) Einkaufswagen (Empfehlungssysteme) Wort-Dokument-Matrix (Textanalyse) Das sind alles zweidimensionale Häufigkeitstabellen mit von einander abhängigen Daten.

Daten (Beispiel): 

Daten (Beispiel) Jedes Dokument wird als Vektor seiner Worte dargestellt absolute Häufigkeit (Anzahl der Worte im Dokument) relative Häufigkeit (relative Häufigkeit des Wortes im Dokument) normalisierte Matrix (Summe aller Einträge = 1)

Was ist Clustering: 

Was ist Clustering Gruppierung ähnlicher Objekte (Strukturierung) Kategorisierung (Zusammenfassung von Themen, wie im alten Yahoo) ein großes Bündel in mehrere kleine Bündel unterteilen Jaguar (Automarke) und Jaguar (Tier)

von Oben / von Unten: 

von Oben / von Unten Top-down (links) Bottom-up (rechts)

Co-clustering (Idee): 

Co-clustering (Idee) die meisten Cluster-Algorithmen fokussieren sich auf eindimensionales clustern es ist erstrebenswert simultan beide Dimensionen zu clustern (co-clustern) es existiert eine offensichtliche Dualität/Abhängigkeit der Daten Dokumente können nach ihrer Worthäufigkeit geclustert werden Worte können nach ihrem auftreten in Dokumenten geclustert werden

Co-clustering (natürlicher Ansatz): 

Co-clustering (natürlicher Ansatz) die normalisierte Wort-Dokment-Matrix wird als gemeinsame Wahrscheinlichkeitsverteilung zwischen zwei unabhängigen Variablen gesehen das optimale Co-clustering führt zu einem minimalen Verlust an gemeinsamen Informationen (mutual information)

Co-clustering: 

Co-clustering Co-clustering vermischt (im Sinne der Abhängigkeit) Zeilen- und Spaltenclustering in allen Abschnitten Zeilenclustering basiert auf den Clusterprototypen der Spalten Spaltenclustering basiert auf den Clusterprototypen der Zeilen die neuen Cluster berücksichtigen dabei jeweils die (alle) vorherigen (egal welcher Dimension) Seltenheit (Leerheit) wird gut verarbeitet

Allgemeines: 

Allgemeines X hat m Elemente und wird in k Cluster aufgeteilt Y hat n Elemente und wird in l Cluster aufgeteilt D(*||*) ist die Kullback-Leibler-Abweichung, die die relative Entropie des Informationsgehaltes angibt und somit zu minimieren ist.

Verlust an gemeinsamer Information: 

Verlust an gemeinsamer Information gemeinsame Information stellt eine "Gewichtung" der Information dar relative Entropie gibt den gemeinsamen Informationsverlust zwischen zwei Punkten wieder

q(X,Y): 

q(X,Y)

grober Ablauf der Algorithmus: 

grober Ablauf der Algorithmus Initialisierung Bestimmen der ersten Cluster-Zuteilungen (1) Zeilen den Zeilen-Cluster-Prototypen zuordnen (2) & Neuberechnung der benötigten Tabellen (3) If Differenz<10^-3 Spalten den Spalten-Cluster-Prototypen zuordnen (4) & Neuberechnung der benötigten Tabellen (5)

(1) Initialisierung: 

(1) Initialisierung t=0 Bestimmen der ersten Zuordnungen zu den Zeilen- und Spalten-Clustern (Heuristik oder Zufall) Berechnen von:

(2) Zuordnung der Zeilen: 

(2) Zuordnung der Zeilen für jede Zeile von p(x,y) bilden wir die Kullback-Leibler-Abweichungen zu allen Zeilen-Cluster-Prototypen dem Zeilen-Cluster-Prototyp mit dem geringsten Abweichung wird die Zeile neu zugerordnet

(3) Neuberechnung: 

(3) Neuberechnung Wahrscheinlichkeit von Zeilen-Cluster und Spalten-Cluster Wahrscheinlichkeit von einer Zeile unter der Bedingung, dass das Zeilen-Cluster eintritt Wahrscheinlichkeit von einer Spalte unter der Bedingung, dass das Spalten-Cluster eintritt Wahrscheinlichkeit von einer Zeile unter der Bedingung, dass das Spalten-Cluster eintritt

(4) Zuordnung der Spalten: 

(4) Zuordnung der Spalten für jede Spalte von p(x,y) bilden wir die Kullback-Leibler-Abweichungen zu allen Spalten-Cluster-Prototypen dem Spalten-Cluster-Prototyp mit dem geringsten Abweichung wird die Spalte neu zugerordnet

(5) Neuberechnung: 

(5) Neuberechnung Wahrscheinlichkeit von Zeilen-Cluster und Spalten-Cluster Wahrscheinlichkeit von einer Zeile unter der Bedingung, dass das Zeilen-Cluster eintritt Wahrscheinlichkeit von einer Spalte unter der Bedingung, dass das Spalten-Cluster eintritt Wahrscheinlichkeit von einer Saplte unter der Bedingung, dass das Zeilen-Cluster eintritt

loss in mutual information: 

loss in mutual information Der Verlust an gemeinsamer Information kann durch die gewichtete Summe der relativen Entropie zwischen Spalten und Spalten-Clustern oder Zeilen und Zeilen-Clustern ausgedrückt werden. (Kullback-Leibler-Abstand)

Senken des Verlustes an gemeinsamer Information: 

Senken des Verlustes an gemeinsamer Information monotone Abnahme der Kullback-Leibler-Abstände eigentlicher Beweis ist mit Zwischenschritten länger als eine Seite

Ergebnisse: 

Ergebnisse Co-clustering liefert bessere Ergebnisse als eindimensionales clustern

Ergebnisse: 

Ergebnisse schattierte Bereiche sind nicht Null Einträge Seltenheitsbeziehung wird deutlich in der Struktur des Co-clusterings

Ergebnisse: 

Ergebnisse Genauigkeit bei variierter Anzahl der Wort-Cluster Die meisten besten Werte liegen im Bereich von 50 bis 100

Ergebnisse: 

Ergebnisse Verlust an gemeinsamer Information mit variierten Wort-Clustern Die meisten besten Werte auch hier im Bereich von 50 bis 100

Testdaten: 

Testdaten 20 Newsgroups 20 Kategorien mit um die 1000 Dokumente 6 grobe Oberkategorien Classic3 MEDLINE, CISI und CRANFIELD 11 Dokumente 4 Digital-Rights-Management Texte (englisch) 7 Georg Büchner Texte (deutsch)

Weiterführendes: 

Weiterführendes Genetik Einkaufswagen (Prognose) Supermarkt Dokumentklassifikation

Quellen: 

Quellen "Information-Theoretic Co-Clustering" von Inderjit S. Dhillon, Subramanyam Mallela und Dharmendra S. Modha