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) :

soit ${\displaystyle \mathrm {E} }$ une matrice ${\displaystyle \mathrm {M} \times \mathrm {N} }$, soient ${\displaystyle \mathrm {I} \subseteq \mathrm {M} {\text{ , }}J\subseteq \mathrm {N} }$, alors ${\displaystyle \mathrm {E} _{IJ}}$ est appelé « bicluster » de ${\displaystyle \mathrm {E} }$ lorsque ${\displaystyle \mathrm {E} _{i_{1},j}=\mathrm {E} _{i_{2},j}=..=\mathrm {E} _{i_{m},j}}$ pour tout ${\displaystyle j\in J{\text{ et }}(i_{1},i_{2},...i_{m})\in \mathrm {M} }$

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).

a) « Bi-cluster » à valeurs constantes 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6 7,6

b)« Bi-cluster » à valeurs constantes en lignes 1,2 1,2 1,2 1,2 1,2 2,1 2,1 2,1 2,1 2,1 3,2 3,2 3,2 3,2 3,2 4,1 4,1 4,1 4,1 4,1 4,2 4,2 4,2 4,2 4,2

c)« Bi-cluster » à valeurs constantes en colonnes 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) « Bi-cluster » à valeurs cohérentes (additives) 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)« Bi-cluster » à valeurs cohérentes (multiplicative) 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

En d) la notion d'additivité se comprend comme ceci : ${\displaystyle +3,-1,+2,-3}$ en colonnes, ${\displaystyle +3,+1,-5,+1,5}$ en lignes; en e) le motif est ${\displaystyle {\frac {1}{2}},*4,{\frac {1}{10}},*4}$ en colonnes et ${\displaystyle *2,*1.5,{\frac {4}{3}},{\frac {5}{4}}}$.

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 :

${\displaystyle f_{1}=\left|\mathrm {I} \right|+\left|J\right|}$ ou ${\displaystyle f_{2}=\left|\mathrm {I} \right|*\left|J\right|}$^[10]

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

• Classification
• Classification automatique
• Segmentation (sciences humaines)