Biclustering

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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

[Bearbeiten | Quelltext bearbeiten]

Sei eine Datenmenge in Form einer rechteckigen Matrix, die sich aus Spalten und 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 repräsentiert die Expression des -ten Features im -ten Sample.[4]

Weiters seien die Klassen eine Klassifikation der Samples und die Klassen eine Klassifikation der Features.[4] Eine Submatrix von , die als Paar mit dargestellt wird, wird als Bicluster bezeichnet.[4][5]

Beim Biclustering entsteht eine Partition von , bestehend aus Biclustern.[5] Manche Biclustering-Methoden erlauben Bicluster, die Sample- und Feature-Klassen mit unterschiedlichen Indizes beinhalten (das sind Paare mit und ).[4]

Komplexität

[Bearbeiten | Quelltext bearbeiten]

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.[6]

Typen von Biclustern

[Bearbeiten | Quelltext bearbeiten]

Verschiedene Biclustering-Algorithmen haben verschiedene Definitionen für den 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 und anderen Clusteringtypen, wie Correlation Clustering, wird diskutiert in.[7]

Algorithmen

[Bearbeiten | Quelltext bearbeiten]

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 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.[14] Biclustering wird auch im Bereich des Text Mining (oder der Klassifizierung) unter dem Begriff Co-Clustering eingesetzt.[15] 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 Dij 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 d1 und d2 gegeben, kann die Anzahl der Überschneidungen anhand der Anzahl der Wörter, die in Dokumenten der Gruppen d1 und d2 auftreten, gemessen werden.

Bisson und Hussain[15] 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

[Bearbeiten | Quelltext bearbeiten]

Literatur

[Bearbeiten | Quelltext bearbeiten]
  • 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).

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. ↑ Iven Van Mechelen, Hans-Hermann Bock, Paul De Boeck: Two-mode clustering methods:a structured overview. In: Statistical Methods in Medical Research. 13. Jahrgang, Nr. 5, 2004, S. 363–94, doi:10.1191/0962280204sm373ra, PMID 15516031.
  2. ↑ a b 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: Journal of the American Statistical Association. 67. Jahrgang, Nr. 337. American Statistical Association, 1972, S. 123–9, doi:10.2307/2284710.
  4. ↑ a b c d e Stanislav Busygin, Oleg Prokopyev, Panos M. Pardalos: Biclustering in data mining. In: Computers & Operations Research. 35. Jahrgang, Nr. 9, 2008, S. 2964–2987, doi:10.1016/j.cor.2007.01.005.
  5. ↑ a b c Antonio Mucherino, Sonia Cafieri: A New Heuristic for Feature Selection by Consistent Biclustering. In: Cornell University. 2010, arxiv:1003.3279v1.
  6. ↑ a b c Sara C. Madeira, Arlindo L. Oliveira: Biclustering Algorithms for Biological Data Analysis: A Survey. In: IEEE Transactions on Computational Biology and Bioinformatics. 1. Jahrgang, 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. Jahrgang, 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. Jahrgang, 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. Jahrgang, Nr. 16–18, 2006, S. 1882–1896, doi:10.1016/j.neucom.2006.02.018 (elsevier.com).
  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. Jahrgang, 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. Jahrgang, 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. Jahrgang, 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. Jahrgang, Nr. 8, 2009.
  14. ↑ Jesús S. Aguilar-Ruiz: Shifting and scaling patterns from gene expression data. In: Bioinformatics. 21. Jahrgang, Nr. 10, 2005, S. 3840–3845, doi:10.1093/bioinformatics/bti641, PMID 16144809.
  15. ↑ a b 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.
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Biclustering&oldid=211882933“