The aim of this paper is to shed light on matrix reordering methods: namely scale of conformity, minus technique, plus technique and mixed technique. All of them are based on the theory of monotone systems. Presented methods are applicable both to NxN (entityto-entity) and NxM (entity-to-attribute) data tables. All the methods can use larger set of discrete values (not only binary ones). Rows and columns are reordered separately. The result does not depend on the initial order of rows and columns. We compare the results of these methods through stress measure (both in the von Neumann neighborhood and in the Moore neighborhood) using binarized representations of well-known data sets.
Seriation is an exploratory data analysis technique to reorder objects into a
sequence along a one-dimensional continuum so that it best reveals regularity and
patterning among the whole series [
Matrix reordering has been used in many different fields, from archaeology
to operations research. A thorough historical overview is given by Liiv [
In this paper, we introduce little known matrix reordering methods that are
based on the theory of monotone systems (MS) created by Mullat [
According to Liiv [
The paper is organized as follows. In the following subsections, we introduce stress measures and describe MS-based reordering methods. Section 2 is dedicated to the mixed technique. Experiments are presented in section 3 and conclusion in section 4. 1.1
Stress is a dissimilarity measure, it compares the values in a matrix with their
neighbors. For an n × m matrix X, the local stress measure for element xij is
defined for two types of neighborhood [
A global stress measure for the whole matrix is the sum of the local stresses (in either neighborhood) for all entries of the table:
ST RESS = Σin=1Σjm=1sij .
In case of binary data, the local stress sij is just the count of the neighbors that have different values. 2. in the von Neumann neighborhood–a diamond-shape neighborhood comprising (at most) four adjacent entries: 1.2
Here we briefly introduce three methods for reordering data tables: scale of
conformity, minus technique and plus technique [
All the methods reorder rows and columns separately. Thus, the same algorithm can be applied for both rows and columns, using transposed table for one of them. Their result does not depend on the initial order of rows/columns.
The scale of conformity [
In case of iterative techniques [
Algorithm: Mixed technique for matrix rows
These reordering methods allow to process non-binary data and zeros are treated the same way as other values. Using a different weight function, we can treat zeros differently.
The data table will be reordered in order to better visualize the data. In case of conformity scale and plus technique, the most homogeneous group forms in the upper-left corner and the most atypical in the lower-right corner. In case of minus technique–on the contrary.
While these techniques help finding homogeneous groups, we miss a method offering possibly smooth changes. In the next section we will propose such a method. 2
Here we present a novel iterative method for matrix reordering, called mixed
technique [
Assume that we have an N × M data matrix X. Every element Xij , i = 1, . . . , N , j = 1, . . . , M , has a discrete value from an interval [1, K].
Algorithm (see above) starts like the minus technique (S1..S5) and after the first iteration, it continues similarly to the plus technique (S6..S13).
In order to demonstrate the mixed technique we use data given in Table 1 (a). The conformity i.e. weight of O1 is 2+2+4+2+2=12 (count(A1 = 1) + count(A2 = 2) + count(A3 = 2) + count(A4 = 2) + count(A5 = 2)). O1 has the smallest weight among objects, therefore it is selected first. After that starts the iterative part of the algorithm.
Table 1 (b) shows the weights of objects (rows) during 6 iterations and the order of elimination of rows, while Table 1 (c) shows the same for columns (during 5 iterations). Reordered data table is presented in Table 1 (d). Weights of rows W (Oi) and weights of columns W (Aj) present the weights at the moment of elimination of a row/column.
Compared to the previous techniques, mixed technique gives different information. By maximizing the similarity between consecutive rows/columns, it reveals an “evolutionary” way of changing/developing the initial object/attribute. 3
We compare the results of four introduced algorithms by two stress measures [
We use binarized representations of 20 data sets from UCI Machine Learning Repository1, the list of data sets, ordered by size, is given in Table 2.
Table 3 shows global stress values in both neighborhoods for all the considered data sets for all 4 reordering algorithms based on monotone systems: conformity scale (conf), plus technique (plus), minus technique (min) and mixed technique (mixed). 1 http://archive.ics.uci.edu/ml/
The smaller the stress value, the better is the reordering. In each row, the
smallest values for both neighborhoods are shown in bold. In all cases the mixed
technique achieves the best result and conformity scale has the worst result. In
most cases, minus technique gives better result than plus technique (16 data
sets out of 20 by both measures). This complies with observation by Liiv ([
In this paper, we have introduced three matrix reordering methods based on monotone systems and proposed a new one, called mixed technique. We have evaluated all four methods using stress measures. We have found that the novel mixed technique performs better than the other three algorithms. Future challenges include handling big data and dealing with incremental update. Acknowledgements. The authors would like to thank prof. Sadok Ben Yahia for helpful comments and suggestions.