Bipolarisation

Cette méthode procède de façon inverse à la méthode PPI. Au lieu de chercher à regrouper ce qui se ressemble, elle cherche à opposer ce qui est dissemblable. Elle réorganise la matrice D en plaçant les plus grandes dissimilarités de la matrice D dans les cellules les plus éloignées de la diagonale.
C'est une approche gloutonne, procédant par étapes.
À la première étape, on recherche la plus grande des dissimilarité de D. On la place dans l'angle supérieur droit de la matrice D, par permutations adéquates des lignes et des colonnes de D. Les éléments les plus dissemblables sont ainsi placés aux deux extrémités de la sériation. L'un sera à l'extrémité gauche, l'autre à l'extrémité droite.

Les étapes suivantes s'organisent alternativement autour de ces deux points pris pour référence.
À la deuxième étape, on recherche l'élément le plus dissemblable du point placé le plus à droite à la première étape. Par un mouvement des lignes et des colonnes de D, on place cette valeur dans la cellule (1, n-1) de D. Cet élément devient ainsi le deuxième élément le plus à gauche de la sériation.
À la troisième étape on recherche l'élément le plus dissemblable du point placé le plus à gauche de la sériation à la première étape. Il devient l'avant dernier élément le plus à droite de la sériation.
Alternativement on place un élément à gauche de la sériation, par mise en opposition avec le point placé à l'extrême droite, puis un élément à gauche, par mise en opposition avec le point mit à l'extrême droite à la première étape de la sériation.
Cet algorithme est très rapide et donne de très bons résultats quand il existe une organisation bi polaire des éléments à sérier. Il reprend l'un des algorithmes proposés par Hubert(1974, p.145).

Si la sériation est faite sous contrainte arborée, l'idée qui sous-tend cette méthode peut également être mise en œuvre.
On parcourt de façon descendante chacune des arêtes internes de l'arbre que l'on oriente successivement. Pour une arête donnée, on s'arrange pour que les deux extrémités les plus éloignées des deux sous-arbres soient occupées par les éléments les plus éloignés au sens de D,
Là encore l'algorithme est rapide et donne de très bons résultats.

 

Hubert, L. J. (1974) Some applications of graph theory and related non-metric techniques to problems of approximate seriation: The case of symmetric proximity measures. British Journal of Mathematical and Statistical Psychology, 27, 133-153.