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 |