Abstract
Previous seriation algorithms are confronted with a balance problem. Some approaches provide permutations with perfect wholeness, where matrix rows/columns are associated with increasing or decreasing gradient. However, this smooth permutation may lead to the blurred representation of the data structure, such as clustering structures and detailed structures inside clusters. Some other approaches indicate these structures well by tighter aggregating similar rows/columns, but this aggregation is alway at the cost of losing necessary coherence of the matrix rows/columns. In this paper, we introduce a seriation algorithm that aims at balancing the smoothness of the permutation and the clarity of the matrix structure. The permutation algorithm greedily and recursively replaces high-dissimilar object pairs with low-dissimilar ones, and the optimization algorithm searches the global optimizing solution by applying the simulated annealing algorithm. A comparison study shows both empirical and statistical evidence that Recut can provide more accurate and visually appropriate permutation by considering the balance problem.