Bipolarization (What is seriation ?)

This method proceeds in an opposed manner relative to the NI method.
Whereas the NI method searches to group together similar items, the Bipolarization method searches to oppose dissimilar items.
It reorganizes the D matrix by placing the highest dissimilarities from D in the remotest cells from the diagonal.
This is a greedy approach, it proceeds step by step.

In the first step, the highest dissimilarity in D is placed in the upper right angle of the matrix, by adequately permuting rows and columns in D.
The most dissimilar items are consequently placed at the two extremities of the seriation: one on the far left, the other on the far right.
The following steps are organized alternately around these two extremities.

In the second step, the most different item from the item previously set on the far right is searched.
Then it is placed, by permutation of rows and columns in D, in the cell (1, n-1) in D.
This item then becomes the second element in the far left part of the seriation.

In the third step, the most different item relative to the item set on the far right in the first step is placed next to the last item on the far right part of the seriation.
Alternately an item is placed on the left part of the seriation, by opposition to the far right item, then an item is placed on the right, by opposition to the far left item.
This algorithm is very fast and yields good results when there is a bipolar organization in the items to seriate.
It summarizes an algorithm proposed by Hubert (1974, p.145).

If the seriation is performed under tree constraint, the seriation can still be built by opposing dissimilar items.
This is achieved by successively browsing each internal node of the constraint tree to position each sub-tree.
Each node is rotated so that the most distant elements in D are positioned on the two most distant extremities of the two sub-trees.
Here again, the algorithm is fast and yields good results.

References :

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.

PermutMatrix 
TOP