title: Classification double
text: # 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, la définition de la classification double peut s'exprimer de la manière suivante (pour le type de classification par colonne) :
  
  $\mathrm {E}$
  
  $\mathrm {M} \times \mathrm {N}$
  
  $\mathrm {I} \subseteq \mathrm {M} {\text{ , }}J\subseteq \mathrm {N}$
  
  $\mathrm {E} _{IJ}$
  
  $\mathrm {E}$
  
  $\mathrm {E} _{i_{1},j}=\mathrm {E} _{i_{2},j}=..=\mathrm {E} _{i_{m},j}$
  
  $j\in J{\text{ et }}(i_{1},i_{2},...i_{m})\in \mathrm {M}$
  
  ## Application
  
  Le « biclustering » a été utilisé massivement en biologie - par exemple dans l'analyse de l'expression génétique par Yizong Cheng et George M. Church $^,$ -, mais aussi dans d'autres domaines tels que la compression d'image de synthèse, l'analyse médicale - par exemple pour l'étude des traitements de l'épilepsie par stimulation vagale, la caractérisation d'émetteurs de pourriels (« spam »), l'analyse du mouvement, l'analyse des termes publicitaires sur internet, ...
  
  ## 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 : $+3,-1,+2,-3$ en colonnes, $+3,+1,-5,+1,5$ en lignes; en e) le motif est ${\frac {1}{2}},*4,{\frac {1}{10}},*4$ en colonnes et $*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 :
  
  $f_{1}=\left|\mathrm {I} \right|+\left|J\right|$
  
  $f_{2}=\left|\mathrm {I} \right|*\left|J\right|$
  
  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 »), RoBA (« Robust Biclustering Algorithm »), « Crossing Minimization » , cMonkey, PRMs, DCC, LEB (« Localize and Extract Biclusters »), QUBIC (« QUalitative BIClustering »), BCCA (« Bi-Correlation Clustering Algorithm »), FABIA (« Factor Analysis for Bicluster Acquisition »). Certains de ces algorithmes ont été comparés par Doruk Bozda, Ashwin S. Kumar et Umit V. Catalyurek en termes de type de motifs recherchés. Le package « biclust » propose un ensemble d'outils pour la classification double dans le logiciel R.
  
  