Comparison of Matrix Reordering Algorithms Based on Monotone Systems Grete Lind and Rein Kuusik Tallinn University of Technology, Tallinn, Estonia {grete.lind,rein.kuusik1}@taltech.ee Abstract. 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 mono- tone systems. Presented methods are applicable both to NxN (entity- to-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 ini- tial 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. Keywords: Matrix Reordering, Monotone Systems, Conformity, Stress. 1 Introduction 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 [1]. Seriation is often called matrix reordering, when applied to two-way datasets [2]. Two-way one-mode data table means entity-to-entity (NxN) data table and two-way two-mode is entity-to-attribute (MxN) data table [1]. Matrix reordering has been used in many different fields, from archaeology to operations research. A thorough historical overview is given by Liiv [1]. In this paper, we introduce little known matrix reordering methods that are based on the theory of monotone systems (MS) created by Mullat [3–5]. These methods – scale of conformity, minus technique, plus technique – have been created by Leo Võhandu at Tallinn University of Technology, department of Informatics [6–8]. We propose a novel MS-based method by Rein Kuusik called mixed technique [8]. According to Liiv [1] the main future goal for seriation is to make it ubiqui- tously usable, reordering the matrices should be a common practice for every- body inspecting any data table. Recently Liiv and Võhandu [2] experiment with asymmetric one-mode two-way (NxN) data tables. They propose that “seriation methods can be applied to analyze asymmetric one-mode two-way datasets as if Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Published in Francisco J. Valverde-Albacete, Martin Trnecka (Eds.): Proceedings of the 15th International Conference on Concept Lattices and Their Applications, CLA 2020, pp. 281–286, 2020. 282 Grete Lind and Rein Kuusik they were two-mode two-way datasets while continuing to keep the information about entities actually belonging to one class”. The paper is organized as follows. In the following subsections, we intro- duce 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 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 [9]: 1. in the Moore neighborhood–a square-shaped neighborhood comprising (at most) eight adjacent entries: min(n,i+1) min(m,j+1) sij = Σk=max(1,i−1) Σl=max(1,j−1) (xij − xkl )2 , (1) 2. in the von Neumann neighborhood–a diamond-shape neighborhood compris- ing (at most) four adjacent entries: min(n,i+1) min(m,j+1) sij = Σk=max(1,i−1) (xij − xkj )2 + Σl=max(1,j−1) (xij − xil )2 . (2) A global stress measure for the whole matrix is the sum of the local stresses (in either neighborhood) for all entries of the table: n m ST RESS = Σi=1 Σj=1 sij . (3) In case of binary data, the local stress sij is just the count of the neighbors that have different values. 1.2 Reordering Methods Based on Monotone Systems Here we briefly introduce three methods for reordering data tables: scale of conformity, minus technique and plus technique [6–8]. Because of limited space we cannot present their algorithms and examples. All the methods reorder rows and columns separately. Thus, the same algo- rithm 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 [6] reorders the data by object’s typicality using the conformity measure that is the sum of all attribute-value frequencies (of the row). In case of iterative techniques [7], to wit minus technique, plus technique, rows/columns are removed from table one-by-one, after each removal the weights of the remaining rows/columns are recomputed. Iterative techniques use confor- mity as a weight function. Actually different weight functions (e.g. influence [6]) can be used. Comparison of Matrix Reordering Algorithms Based on Monotone Systems 283 Algorithm: Mixed technique for matrix rows Calculate frequencies F T (t, j) for every attribute’s values t = 1, 2, . . . , Kj in S1. columns j, where j = 1, . . . , M S2. For every row i = 1, 2, . . . , N find the sums (weights) W (i) = Σ F T (t, j), j = 1, . . . , M S3. Find R = min W (i); remember i S4. Eliminate row i from the matrix S5. If there are yet rows in the matrix then goto S6 else goto S12 S6. Nullify the frequency table F T , weights W prev S7. Increase frequencies of the eliminated row i elements by one: F T (t, j) = F T (t, j) + 1 S8. For every row i = 1, 2, . . . , N find the sums (weights) W (i) = Σ F T (t, j), j = 1, . . . , M S9. Find R = max W (i) − W prev(i); remember i S10. Eliminate row i from the matrix S11. If there are yet rows in the matrix then W prev = W ; goto S7 else goto S12 S12. Reorder matrix rows in the order of elimination S13. End 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 Mixed Technique Here we present a novel iterative method for matrix reordering, called mixed technique [8]. It is aimed to create a gradual way of changes, starting from the first object/attribute. The user chooses from which object/attribute to start. If the user cannot decide, then it can be chosen by minimal weight (as in minus technique). Further the closest object/attribute to the just eliminated one (by the number of coincidences) is chosen for removal. The weight is not based on the frequencies of (diminishing) initial table (as in case of plus technique and minus technique), but on the (growing) table of already removed objects/attributes. 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). 284 Grete Lind and Rein Kuusik Table 1. (a) Initial data matrix, (b) order of elimination of objects (6 iterations), (c) order of elimination of attributes (5 iterations), (d) reordered data matrix (a) A1 A2 A3 A4 A5 (b) It1 It2 It3 It4 It5 It6 O1 1 2 2 2 2 O1 0 O2 2 1 2 1 1 O2 0 1 4 O3 2 1 2 1 1 O3 0 1 4 9 O4 1 1 2 1 2 O4 0 3 O5 2 2 1 2 1 O5 0 2 2 4 6 9 O6 2 1 1 1 1 O6 0 0 2 6 10 (c) A1 A2 A3 A4 A5 (d) A1 A2 A4 A5 A3 W(Oi) It1 0 0 0 0 0 O1 1 0 0 0 0 0 It2 2 2 2 0 O4 1 1 1 0 0 3 It3 4 8 4 O2 0 1 1 1 0 4 It4 6 8 O3 0 1 1 1 0 9 It5 10 O6 0 1 1 1 1 10 O5 0 0 0 1 1 9 W(Aj) 0 2 8 8 10 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 infor- mation. By maximizing the similarity between consecutive rows/columns, it re- veals an “evolutionary” way of changing/developing the initial object/attribute. 3 Experiments We compare the results of four introduced algorithms by two stress measures [9] (see section 1.1) using 20 different data sets. 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/ Comparison of Matrix Reordering Algorithms Based on Monotone Systems 285 Table 2. Data sets from UCI ML repository Data Set Size Data Set Size 1 adult-stretch 20*10 11 balance-scale 625*23 2 lenses 24*12 12 tic-tac-toe 958*29 3 shuttle-landing 15*23 13 car 1728*21 4 post-operative 90*25 14 flare2 1066*32 5 hayes-roth 132*18 15 soybean-large 307*133 6 zoo 101*28 16 dermatology 366*130 7 audiology 26*110 17 breast-cancer 699*110 8 servo 167*19 18 chess 3196*75 9 spect-test 187*23 19 nursery 12960*31 10 house-votes-84 435*18 20 mushroom 8124*119 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 ([10], p.61): “the “minus” technique outperformed the “plus” technique on the average with all three measures”, although used data sets and evaluation measures are different. 4 Conclusion 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 chal- lenges 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. References 1. Liiv, I.: Seriation and matrix reordering methods: An historical overview. Statistical analysis and data mining 3(2), 70–91 (2010) 2. Liiv, I., Vohandu, L.: Seriation and Matrix Reordering Methods for Asymmet- ric One-Mode Two-Way Datasets. In: Imaizumi, T., Nakayama, A., Yokoyama, S. (eds.), Advanced Studies in Behaviormetrics and Data Science: Essays in Honor of Akinori Okada, Behaviormetrics: Quantitative Approaches to Human Behavior 5, https://doi.org/10.1007/978-981-15-2700-5_10 (2020) 286 Grete Lind and Rein Kuusik Table 3. Comparison of reordering algorithms by stress in the von Neumann neigh- borhood and in the Moore neighborhood. Stress in the von Stress in the Neumann neighborhood Moore neighborhood conf plus min mixed conf plus min mixed 1 404 248 248 200 824 516 516 468 2 518 386 388 334 1054 834 818 770 3 338 306 286 248 684 644 598 526 4 2602 2370 2322 1720 5116 4952 4848 4162 5 3526 2302 2198 1830 6642 5410 5172 4596 6 2480 2044 1824 1164 5716 5008 4484 2964 7 1268 1128 1120 908 2636 2384 2376 2050 8 3804 2980 2624 2362 7272 6392 6050 5634 9 5462 5026 4658 3234 11408 10752 10078 7338 10 11712 7152 7074 5080 27204 15868 15534 12612 11 15266 14346 13958 11532 34766 32590 32348 29088 12 38300 35544 34262 28388 79808 77764 76332 69814 13 46776 38280 38280 35708 112804 94208 94208 92986 14 19664 18016 18012 14238 51728 47568 47896 40206 15 27782 24982 23728 15434 60224 56060 54472 38058 16 37078 34990 32290 24164 76834 73466 69046 55414 17 25886 25594 24790 18804 56068 55816 55020 44712 18 241918 229222 212218 114190 487386 469402 452762 308070 19 471404 369884 383684 335936 1162272 952904 977356 920826 20 647100 543784 451436 298416 1408528 1282768 1132470 824468 3. Mullat, J.E.: On the Maximum Principle for some Set Functions. Proceedings of the Tallinn Technical University, 313, 37–44 (1971). http://www.datalaundering. com/download/modular.pdf, last accessed 2016/02 4. Mullat, J.E.: Extremal Subsystems of Monotonic Systems. I. Automation and Remote Control, 37(5), 758–766 (1976). www.datalaundering.com/download/ extrem01.pdf, last accessed 2016/02 5. Mullat, J.E.: Extremal Subsystems of Monotonic Systems. II. Automation and Remote Control, 37(8), 1286–1294, (1977). www.datalaundering.com/downlaods/ extrem02.pdf, last accessed 2016/02 6. Vyhandu, L.: Rapid data analysis methods. Transactions of Tallinn Technical Uni- versity, 464, 21–39 (1979). (in Russian) 7. Vyhandu, L: Fast Methods in Exploratory Data Analysis. Transactions of Tallinn Technical University, 705, 3–13 (1989) 8. Võhandu, L., Kuusik, R., Lind, G.: Monotone systems and their applications. Tallinn: Tallinn University of Technology, Department of Software Science (2018). (in Estonian) issuu.com/monotsys/docs/monotoonsed_s_steemid, last accessed 2019/07 9. Hahsler, M., Hornik, K., Buchta, C.: Getting things in order: An introduction to the R package seriation, https://rdrr.io/cran/seriation/, last accessed 2019/06/27 10. Liiv, I.: Pattern Discovery Using Seriation and Matrix Reordering: A Unified View, Extensions and an Application to Inventory Management. Ph.D. Thesis, Tallinn University of Technology (2008)