Classification double
La Classification double ou « Biclustering » est une technique d'exploration de données non-supervisée permettant de segmenter simultanément les lignes et les colonnes d'une matrice. Plus formellement[1], la définition de la classification double peut s'exprimer de la maniÚre suivante (pour le type de classification par colonne) :
Application
Le « biclustering » a été utilisé massivement en biologie[2] - par exemple dans l'analyse de l'expression génétique par Yizong Cheng et George M. Church[3] - [4] -, mais aussi dans d'autres domaines tels que la compression d'image de synthÚse[5], l'analyse médicale - par exemple pour l'étude des traitements de l'épilepsie[6] par stimulation vagale, la caractérisation d'émetteurs de pourriels (« spam »)[7], l'analyse du mouvement[8], l'analyse des termes publicitaires sur internet[9], ...
Types
Dans les différents algorithmes qui utilisent la classification double, on trouve différents types de bicluster :
- « Bi-cluster » à valeurs constantes (a),
- « Bi-cluster » à valeurs constantes en lignes (b) ou en colonnes (c),
- « Bi-cluster » à valeurs cohérentes (d, e).
|
|
|
|
|
En d) la notion d'additivité se comprend comme ceci : en colonnes, en lignes; en e) le motif est en colonnes et .
Algorithmes
Le but des algorithmes de classification double est de trouver, s'il existe, le plus grand « bi-cluster » contenu dans une matrice, en maximisant une fonction objectif. On peut prendre comme fonction, avec les notations adoptées ci-dessus :
De nombreux algorithmes ont été développés notamment par la bio-informatique, dont :
« Block clustering », CTWC (« Coupled Two-Way Clustering ») , ITWC (« Interrelated Two-Way Clustering »), Ύ-bicluster, Ύ-pCluster, Ύ-pattern, FLOC, OPC, « Plaid Model », OPSMs (« Order-preserving submatrixes »), Gibbs, SAMBA (« Statistical-Algorithmic Method for Bicluster Analysis »)[11], RoBA (« Robust Biclustering Algorithm »), « Crossing Minimization »[12]
, cMonkey[13], PRMs, DCC, LEB (« Localize and Extract Biclusters »), QUBIC (« QUalitative BIClustering »), BCCA (« Bi-Correlation Clustering Algorithm »), FABIA (« Factor Analysis for Bicluster Acquisition »)[14]. Certains de ces algorithmes ont été comparés par Doruk Bozda, Ashwin S. Kumar et Umit V. Catalyurek[15] en termes de type de motifs recherchés.
Le package « biclust »[16] propose un ensemble d'outils pour la classification double dans le logiciel R.
Articles connexes
Notes et références
- Tran Trang, Nguyen Cam Chi, Hoang Ngoc Minh,Bi-clustering des donnĂ©es de biopuces par les arbres pondĂ©rĂ©s de plus long prĂ©ïŹxe - Chapitre 1 Introduction
- Sara C. Madeira, Arlindo L. Oliveira,Biclustering Biological Data Analysis
- (en) Cheng Y, Church GM, « Biclustering of expression data », Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology,â , p. 93â103
- Yizong Cheng, George M. Church Biclustering of Expression Data
- Xin Sun, Qiming Hou,Zhong Ren, Kun Zhou, Baining Guo,Radiance Transfer Biclustering for Real-time All-frequency Bi-scale Rendering
- Stanislav Busygin,Nikita Boyko, Panos M. Pardalos,Michael Bewernitz, Georges Ghacibeh,Biclustering EEG data from epileptic patients treated with vagus nerve stimulation
- Kevin S. Xu, Mark Kliger, Alfred O. Hero III, Identifying Spammers by Their Resource Usage Patterns
- Keren Erez, Jacob Goldberger, Ronen Sosnik, Moshe Shemesh, Susan Rothstein,Moshe Abeles, Analyzing Movement Trajectories Using a Markov Bi-Clustering Method
- Dmitry I. Ignatov, Concept-based Biclustering for Internet Advertisement
- Stefano Lonardi, Qiaofeng Yang, Wojciech Szpankowski,Finding biclusters by random projections
- (en) Tanay A, Sharan R, Kupiec M and Sahmir R, « Revealing modularity and organization in the yeast molecular network by integrated analysis of highly heterogeneous genomewide data », Proc Natl Acad Sci USA, vol. 101, no 9,â , p. 2981-2986 (PMID 16749936, PMCID 14973197, DOI 10.1073/pnas.0308661100)
- Ahsan Abdullah, Data Mining Using the Crossing Minimization Paradigm
- (en) Reiss DJ, Baliga NS, Bonneau R, « Integrated biclustering of heterogeneous genome-wide datasets for the inference of global regulatory networks », BMC Bioinformatics, vol. 2, no 7,â , p. 280â302 (PMID 16749936, PMCID 1502140, DOI 10.1186/1471-2105-7-280)
- (en) Hochreiter S, Bodenhofer U, Heusel M, Mayr A, Mitterecker A, Kasim A, Khamiakova T, Van Sanden S, Lin D, Talloen W, Bijnens L, Gohlmann HWH, Shkedy Z, Clevert DA, « FABIA: factor analysis for bicluster acquisition », Bioinformatics, vol. 26, no 12,â , p. 1520â1527 (PMID 20418340, PMCID 2881408, DOI 10.1093/bioinformatics/btq227)
- Doruk Bozda, Ashwin S. Kumar et Umit V. Catalyurek, Comparative Analysis of Biclustering Algorithms
- Sebastian Kaiser, Friedrich Leisch, A Toolbox for Bicluster Analysis in R