1a co clustering

30 %
70 %
Information about 1a co clustering
Entertainment

Published on November 19, 2007

Author: FunSchool

Source: authorstream.com

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

Add a comment

Related presentations

Related pages

Co-clustering - int.tu-darmstadt.de

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

Technische Universität Darmstadt

Themenliste Data Clustering. 1a. Co-clustering. I. S. Dhillon, S. Mallela, D. S. Modha Information-Theoretic Co-clustering Proceedings of The Ninth ACM ...
Read more

clusterMaker: a multi-algorithm clustering plugin for ...

Conclusions. The Cytoscape plugin clusterMaker provides a number of clustering algorithms and visualizations that can be used independently or in ...
Read more

Co-clustering of Lagged Data - researchgate.net

Co-clustering of Lagged Data Eran Shaham Department of Computer Science Bar-Ilan University Ramat-Gan, 52900 Israel erans@macs.biu.ac.il David Sarne
Read more

Scalable co-Clustering using a Crossing Minimization ...

Acta Polytechnica Hungarica Vol. 13, No. 2, 2016 – 209 – Scalable co-Clustering using a Crossing Minimization ‒ Application to Production Flow Analysis
Read more

Björn Hirsch in der Personensuche von Das Telefonbuch

Finden Sie private und berufliche Informationen zu Björn Hirsch: Interessen, Berufe, Biografien und Lebensläufe in der Personensuche von Das Telefonbuch
Read more

Info-Clustering: A Mathematical Theory for Data Clustering

Info-Clustering: A Mathematical Theory for Data Clustering ... clustering (4.1a), ... the Co-Director of the Institute of Network Coding at the
Read more

AutoSOME: a clustering method for identifying gene ...

AutoSOME: a clustering method for identifying gene expression modules without prior knowledge of cluster number
Read more

BMC Neuroscience BioMed - pdfs.semanticscholar.org

Surface clustering of metabotropic glutamate receptor 1 induced ... fluorescence in control and Homer 1a co-expressing cells was not absolutely uniform.
Read more

Project Suggestions and References - University of Texas ...

Project Suggestions and References 1a. ... Co-clustering simultaneously clusters the rows and columns of a matrix such that the row clusters are ...
Read more