Biclustering

Biclustering, Co-Clustering oder Two-Mode Clustering[1] ist eine Data-Mining-Technik, die das gleichzeitige Clustering von Zeilen und Spalten einer Matrix ermöglicht. Der Begriff wurde von Mirkin[2] eingeführt, aber die Technik selbst wurde ursprünglich bereits viel früher eingeführt[2] (z. B. von J.A. Hartigan[3] 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).[4] Jedem Sample ist somit eine Serie von Features zugeordnet.[5] Das Element ${\displaystyle a_{ij}}$ repräsentiert die Expression des ${\displaystyle i}$-ten Features im ${\displaystyle j}$-ten Sample.[4]

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.[4] 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.[4][5]

Beim Biclustering entsteht eine Partition ${\displaystyle B=\{(S_{1},F_{1}),...,(S_{r},F_{r})\}}$ von ${\displaystyle A}$, bestehend aus ${\displaystyle r}$ Biclustern.[5] 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}$).[4]

Komplexität

Die Komplexität d​es Biclustering-Problems i​st abhängig v​on der exakten Problemformulierung, insbesondere v​on der Gütefunktion, d​ie zur Evaluierung d​er Qualität d​es gegebenen Biclusters verwendet wird. Die interessantesten Varianten dieses Problems s​ind jedoch NP-vollständig u​nd erfordern entweder e​inen hohen Rechenaufwand o​der die Verwendung e​iner verlustbehafteten Heuristik, u​m die Berechnung z​u verkürzen.[6]

Typen von Biclustern

Verschiedene Biclustering-Algorithmen h​aben verschiedene Definitionen für d​en Bicluster:[6]

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

a) Bicluster mit konstanten Werten 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0 2,0

b) Bicluster mit konstanten Zeilenwerten 1,0 1,0 1,0 1,0 1,0 2,0 2,0 2,0 2,0 2,0 3,0 3,0 3,0 3,0 3,0 4,0 4,0 4,0 4,0 4,0 4,0 4,0 4,0 4,0 4,0

c) Bicluster mit konstanten Spaltenwerten 1,0 2,0 3,0 4,0 5,0 1,0 2,0 3,0 4,0 5,0 1,0 2,0 3,0 4,0 5,0 1,0 2,0 3,0 4,0 5,0 1,0 2,0 3,0 4,0 5,0

d) Bicluster mit kohärenten Werten (additiv) 1,0 4,0 5,0 0,0 1,5 4,0 7,0 8,0 3,0 4,5 3,0 6,0 7,0 2,0 3,5 5,0 8,0 9,0 4,0 5,5 2,0 5,0 6,0 1,0 2,5

e) Bicluster mit kohärenten Werten (multiplikativ) 1,0 0,5 2,0 0,2 0,8 2,0 1,0 4,0 0,4 1,6 3,0 1,5 6,0 0,6 2,4 4,0 2,0 8,0 0,8 3,2 5,0 2,5 10,0 1,0 4,0

Die Beziehung zwischen diesen Clustermodellen u​nd anderen Clusteringtypen, w​ie Correlation Clustering, w​ird diskutiert in.[7]

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),[8] Robust Biclustering Algorithm (RoBA), Crossing Minimization,[9] cMonkey,[10] PRMs, DCC, LEB (Localize and Extract Biclusters), QUBIC (QUalitative BIClustering), BCCA (Bi-Correlation Clustering Algorithm) und FABIA (Factor Analysis for Bicluster Acquisition).[11] 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.[6]

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[12] und e-CCC-Biclustering.[13] 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 g​ibt eine fortlaufende Debatte über d​ie Beurteilung d​er Ergebnisse dieser Methoden, d​a Biclustering d​ie Überlappung v​on Clustern erlaubt u​nd manche Algorithmen d​ie Exklusion schwierig vereinbarter Spalten/Bedingungen erlauben. Nicht a​lle der verfügbaren Algorithmen s​ind deterministisch. Der Analytiker m​uss die Aufmerksamkeit a​uf das Ausmaß j​ener Ergebnisse richten, d​ie stabile Minima darstellen. Da s​ich das Problem a​uf unüberwachtes Lernen bezieht, erweist s​ich die Fehlererkennung i​n den Ergebnissen w​egen des fehlenden Goldstandards a​ls schwierig. Ein Ansatz i​st die Anwendung mehrerer Biclustering-Algorithmen, d​eren Mehrheit o​der qualifizierte Mehrheit d​as beste Ergebnis ermittelt. Eine andere Möglichkeit i​st eine Qualitätsanalyse d​er Shifting- u​nd Scaling-Pattern v​on Biclustern.[14] Biclustering w​ird auch i​m Bereich d​es Text Mining (oder d​er Klassifizierung) u​nter dem Begriff Co-Clustering eingesetzt.[15] Textkorpora werden i​n Vektorform a​ls eine Matrix D dargestellt, d​eren Zeilen für d​ie Dokumente u​nd deren Spalten für d​ie Wörter e​ines Wörterbuches stehen. Die Matrix-Elemente D_ij bezeichnen d​as Vorkommen d​es Wortes j i​m Dokument i. Co-Clustering-Algorithmen werden anschließend z​ur Erkennung v​on Blöcken i​n D angewandt, welche e​iner Gruppe v​on Dokumenten (Zeilen) entsprechen, d​ie durch e​ine Gruppe v​on Wörtern (Spalten) gekennzeichnet sind.

Mehrere Ansätze wurden basierend a​uf den Informationsinhalten d​er erhaltenen Blöcke vorgeschlagen: Matrix-basierte Ansätze, w​ie SVD u​nd BVD s​owie Graph-basierte. Informationstheoretische Algorithmen weisen iterativ j​eder Zeile e​inen Cluster v​on Dokumenten u​nd jeder Spalte e​inen Cluster v​on Wörtern zu, sodass d​ie gegenseitige Information maximiert wird. Matrix-basierte Methoden fokussieren s​ich auf d​ie Dekomposition v​on Matrizen i​n Blöcke, d​amit der Fehler d​er Dekomposition zwischen d​er ursprünglichen Matrix u​nd den n​eu gebildeten Matrizen minimiert wird. Graph-basierte Methoden neigen dazu, d​ie Überschneidungen zwischen d​en Clustern z​u minimieren. Sind z​wei Gruppen v​on Dokumenten d₁ u​nd d₂ gegeben, k​ann die Anzahl d​er Überschneidungen anhand d​er Anzahl d​er Wörter, d​ie in Dokumenten d​er Gruppen d₁ u​nd d₂ auftreten, gemessen werden.

Bisson u​nd Hussain[15] h​aben einen n​euen Ansatz z​ur Verwendung d​er Ähnlichkeit zwischen Wörtern u​nd der Ähnlichkeit zwischen Dokumenten z​um Co-Clustering e​iner Matrix vorgeschlagen. Ihre Methode χ-Sim (Cross Similarity) basiert a​uf dem Finden e​iner Ähnlichkeit zwischen Dokumenten u​nd Wörtern u​nd der anschließenden Verwendung v​on klassischen Clusteringmethoden, w​ie 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, Nr. 4, 2003, S. 703–716. doi:10.1101/gr.648603. PMID 12671006. PMC 430175 (freier Volltext).

Einzelnachweise

1. Iven Van Mechelen, Hans-Hermann Bock, Paul De Boeck: Two-mode clustering methods:a structured overview. In: Statistical Methods in Medical Research. 13, Nr. 5, 2004, S. 363–94. doi:10.1191/0962280204sm373ra. PMID 15516031.
2. Boris Mirkin: Mathematical Classification and Clustering. Kluwer Academic Publishers, 1996, ISBN 0-7923-4159-7.
3. J.A. Hartigan: Direct clustering of a data matrix. In: American Statistical Association (Hrsg.): Journal of the American Statistical Association. 67, Nr. 337, 1972, S. 123–9. doi:10.2307/2284710.
4. Stanislav Busygin, Oleg Prokopyev, Panos M. Pardalos: Biclustering in data mining. In: Computers & Operations Research. 35, Nr. 9, 2008, S. 2964–2987. doi:10.1016/j.cor.2007.01.005.
5. Antonio Mucherino, Sonia Cafieri: A New Heuristic for Feature Selection by Consistent Biclustering. In: Cornell University. 2010. arxiv:1003.3279v1.
6. Sara C. Madeira, Arlindo L. Oliveira: Biclustering Algorithms for Biological Data Analysis: A Survey. In: IEEE Transactions on Computational Biology and Bioinformatics. 1, Nr. 1, 2004, S. 24–45. doi:10.1109/TCBB.2004.2. PMID 17048406.
7. Hans-Peter Kriegel, Peer Kröger, Arthur Zimek: Clustering High Dimensional Data: A Survey on Subspace Clustering, Pattern-based Clustering, and Correlation Clustering. In: ACM Transactions on Knowledge Discovery from Data (TKDD). 3, Nr. 1, März 2009, S. 1–58. doi:10.1145/1497577.1497578.
8. Amos Tanay, Roded Sharan, Martin Kupiec, Ron Shamir: Revealing modularity and organization in the yeast molecular network by integrated analysis of highly heterogeneous genomewide data. In: Proc Natl Acad Sci USA. 101, Nr. 9, 2004, S. 2981–2986. doi:10.1073/pnas.0308661100. PMID 14973197. PMC 365731 (freier Volltext).
9. Ahsan Abdullah, Amir Hussain: A new biclustering technique based on crossing minimization. In: Neurocomputing. 69, Nr. 16–18, 2006, S. 1882–1896. doi:10.1016/j.neucom.2006.02.018.
10. David J. Reiss, Nitin S. Baliga, Richard Bonneau: Integrated biclustering of heterogeneous genome-wide datasets for the inference of global regulatory networks. In: BMC Bioinformatics. 2, 2006, S. 280–302. doi:10.1186/1471-2105-7-280. PMID 16749936. PMC 1502140 (freier Volltext).
11. Sepp Hochreiter, Ulrich Bodenhofer, Martin Heusel, Andreas Mayr, Andreas Mitterecker, Adetayo Kasim, Tatsiana Khamiakova, Suzy Van Sanden, Dan Lin, Willem Talloen, Luc Bijnens, Hinrich W. H. Gohlmann, Ziv Shkedy, Djork-Arné Clevert: FABIA: factor analysis for bicluster acquisition. In: Bioinformatics. 26, Nr. 12, 2010, S. 1520–1527. doi:10.1093/bioinformatics/btq227. PMID 20418340. PMC 2881408 (freier Volltext).
12. Sara C. Madeira, Miguel C. Teixeira, Isabel Sá-Correia, Arlindo L. Oliveira: Identification of Regulatory Modules in Time Series Gene Expression Data using a Linear Time Biclustering Algorithm. In: IEEE Transactions on Computational Biology and Bioinformatics. 1, Nr. 7, 2010, S. 153–165. doi:10.1109/TCBB.2008.34.
13. Sara C. Madeira, Arlindo L. Oliveira: A polynomial time biclustering algorithm for finding approximate expression patterns in gene expression time series. In: Algorithms for Molecular Biology. 4, Nr. 8, 2009.
14. Jesús S. Aguilar-Ruiz: Shifting and scaling patterns from gene expression data. In: Bioinformatics. 21, Nr. 10, 2005, S. 3840–3845. doi:10.1093/bioinformatics/bti641. PMID 16144809.
15. Gilles Bisson, Fawad Hussain: Chi-Sim: A new similarity measure for the co-clustering task. In: ICMLA. 2008, S. 211–217. doi:10.1109/ICMLA.2008.103.