Biclustering

Biclustering, Co-Clustering oder Two-Mode Clustering ist eine Data-Mining-Technik, die das gleichzeitige Clustering von Zeilen und Spalten einer Matrix ermöglicht. Der Begriff wurde von Mirkin eingeführt, aber die Technik selbst wurde ursprünglich bereits viel früher eingeführt (z. B. von J.A. Hartigan unter dem Begriff Direct Clustering).

Definition

Sei ${\displaystyle A=(a_{ij})_{m\times n}}$ eine Datenmenge in Form einer rechteckigen Matrix, die sich aus ${\displaystyle n}$ Spalten und ${\displaystyle m}$ Zeilen zusammensetzt. Jede Spalte steht für ein Sample (Datenprobe) und jede Zeile für ein Feature (Komponente eines Samples). Jedem Sample ist somit eine Serie von Features zugeordnet. Das Element ${\displaystyle a_{ij}}$ repräsentiert die Expression des ${\displaystyle i}$-ten Features im ${\displaystyle j}$-ten Sample.

Weiters seien die Klassen ${\displaystyle S_{1},...,S_{r}}$ eine Klassifikation der Samples und die Klassen ${\displaystyle F_{1},...,F_{r}}$ eine Klassifikation der Features. Eine Submatrix von ${\displaystyle A}$, die als Paar ${\displaystyle (S_{k},F_{k})}$ mit ${\displaystyle k\in \{1,...,r\}}$ dargestellt wird, wird als Bicluster bezeichnet.

Beim Biclustering entsteht eine Partition ${\displaystyle B=\{(S_{1},F_{1}),...,(S_{r},F_{r})\}}$ von ${\displaystyle A}$, bestehend aus ${\displaystyle r}$ Biclustern. Manche Biclustering-Methoden erlauben Bicluster, die Sample- und Feature-Klassen mit unterschiedlichen Indizes beinhalten (das sind Paare ${\displaystyle (S_{k},F_{l})}$ mit ${\displaystyle k,l\in \{1,...,r\}}$ und ${\displaystyle k\neq l}$).

Komplexität

Die Komplexität des Biclustering-Problems ist abhängig von der exakten Problemformulierung, insbesondere von der Gütefunktion, die zur Evaluierung der Qualität des gegebenen Biclusters verwendet wird. Die interessantesten Varianten dieses Problems sind jedoch NP-vollständig und erfordern entweder einen hohen Rechenaufwand oder die Verwendung einer verlustbehafteten Heuristik, um die Berechnung zu verkürzen.

Typen von Biclustern

Verschiedene Biclustering-Algorithmen haben verschiedene Definitionen für den Bicluster:

1. Bicluster mit konstanten Werten (a),
2. Bicluster mit konstanten Zeilenwerten (b) oder Spaltenwerten (c),
3. Bicluster mit kohärenten Werten (d, e).

Die Beziehung zwischen diesen Clustermodellen und anderen Clusteringtypen, wie Correlation Clustering, wird diskutiert in.

Algorithmen

Zahlreiche Biclustering-Algorithmen wurden für die Bioinformatik entwickelt, darunter: Block Clustering, CTWC (Coupled Two-Way Clustering), ITWC (Interrelated Two-Way Clustering), δ-Bicluster, δ-pCluster, δ-Pattern, FLOC, OPC, Plaid Model, OPSMs (Order-preserving Submatrices), Gibbs, SAMBA (Statistical-Algorithmic Method for Bicluster Analysis), Robust Biclustering Algorithm (RoBA), Crossing Minimization, cMonkey, PRMs, DCC, LEB (Localize and Extract Biclusters), QUBIC (QUalitative BIClustering), BCCA (Bi-Correlation Clustering Algorithm) und FABIA (Factor Analysis for Bicluster Acquisition). Auch in anderen Anwendungsgebieten werden Biclustering-Algorithmen vorgeschlagen und eingesetzt. Dort sind sie unter den Bezeichnungen Co-Clustering, Bidimensional Clustering sowie Subspace Clustering zu finden.

Biclustering hat sich zur Erkennung lokaler Muster in Zeitreihendaten als relevant gezeigt. Daher haben sich neueste Ansätze für Zeitreihendaten von Genexpressionen dem Biclustering-Problem gewidmet, mit dem interessante Bicluster auf Bicluster mit aneinander angrenzenden Spalten beschränkt werden können. Diese Einschränkung führt zu einem Problem, das in polynomieller Zeit gelöst werden kann. Zudem ermöglicht es die Entwicklung von effizienten erschöpfenden Enumerationsalgorithmen, wie CCC-Biclustering und e-CCC-Biclustering. Manche der neuesten Algorithmen haben versucht, zusätzliche Unterstützung für das Biclustering von rechteckigen Matrizen mit anderen Datentypen, darunter cMonkey, zu inkludieren.

Es gibt eine fortlaufende Debatte über die Beurteilung der Ergebnisse dieser Methoden, da Biclustering die Überlappung von Clustern erlaubt und manche Algorithmen die Exklusion schwierig vereinbarter Spalten/Bedingungen erlauben. Nicht alle der verfügbaren Algorithmen sind deterministisch. Der Analytiker muss die Aufmerksamkeit auf das Ausmaß jener Ergebnisse richten, die stabile Minima darstellen. Da sich das Problem auf unüberwachtes Lernen bezieht, erweist sich die Fehlererkennung in den Ergebnissen wegen des fehlenden Goldstandards als schwierig. Ein Ansatz ist die Anwendung mehrerer Biclustering-Algorithmen, deren Mehrheit oder qualifizierte Mehrheit das beste Ergebnis ermittelt. Eine andere Möglichkeit ist eine Qualitätsanalyse der Shifting- und Scaling-Pattern von Biclustern. Biclustering wird auch im Bereich des Text Mining (oder der Klassifizierung) unter dem Begriff Co-Clustering eingesetzt.Textkorpora werden in Vektorform als eine Matrix D dargestellt, deren Zeilen für die Dokumente und deren Spalten für die Wörter eines Wörterbuches stehen. Die Matrix-Elemente D_ij bezeichnen das Vorkommen des Wortes j im Dokument i. Co-Clustering-Algorithmen werden anschließend zur Erkennung von Blöcken in D angewandt, welche einer Gruppe von Dokumenten (Zeilen) entsprechen, die durch eine Gruppe von Wörtern (Spalten) gekennzeichnet sind.

Mehrere Ansätze wurden basierend auf den Informationsinhalten der erhaltenen Blöcke vorgeschlagen: Matrix-basierte Ansätze, wie SVD und BVD sowie Graph-basierte. Informationstheoretische Algorithmen weisen iterativ jeder Zeile einen Cluster von Dokumenten und jeder Spalte einen Cluster von Wörtern zu, sodass die gegenseitige Information maximiert wird. Matrix-basierte Methoden fokussieren sich auf die Dekomposition von Matrizen in Blöcke, damit der Fehler der Dekomposition zwischen der ursprünglichen Matrix und den neu gebildeten Matrizen minimiert wird. Graph-basierte Methoden neigen dazu, die Überschneidungen zwischen den Clustern zu minimieren. Sind zwei Gruppen von Dokumenten d₁ und d₂ gegeben, kann die Anzahl der Überschneidungen anhand der Anzahl der Wörter, die in Dokumenten der Gruppen d₁ und d₂ auftreten, gemessen werden.

Bisson und Hussain haben einen neuen Ansatz zur Verwendung der Ähnlichkeit zwischen Wörtern und der Ähnlichkeit zwischen Dokumenten zum Co-Clustering einer Matrix vorgeschlagen. Ihre Methode χ-Sim (Cross Similarity) basiert auf dem Finden einer Ähnlichkeit zwischen Dokumenten und Wörtern und der anschließenden Verwendung von klassischen Clusteringmethoden, wie dem hierarchischen Clustering.

Siehe auch

• Formale Begriffsanalyse
• Galoisverbindung

Literatur

• Amos Tanay, Roded Sharan, Ron Shamir: Biclustering Algorithms: A Survey. In: Srinivas Aluru (Hrsg.): Handbook of Computational Molecular Biology. Chapman, 2004.
• Yuval Kluger, Ronen Basri, Joseph T. Chang, Mark Gerstein: Spectral Biclustering of Microarray Data: Coclustering Genes and Conditions. In: Genome Research. 13. Jahrgang, Nr. 4, 2003, S. 703–716, doi:10.1101/gr.648603, PMID 12671006, PMC 430175 (freier Volltext).