Fragments of order

ABSTRACT

High-dimensional collections of 0--1 data occur in many applications. The attributes in such data sets are typically considered to be unordered. However, in many cases there is a natural total or partial order ≺ underlying the variables of the data set. Examples of variables for which such orders exist include terms in documents, courses in enrollment data, and paleontological sites in fossil data collections. The observations in such applications are flat, unordered sets; however, the data sets respect the underlying ordering of the variables. By this we mean that if A ≺ B ≺ C are three variables respecting the underlying ordering ≺, and both of variables A and C appear in an observation, then, up to noise levels, variable B also appears in this observation. Similarly, if A₁ ≺ A₂ ≺ … ≺ A_l-1 ≺ A_i is a longer sequence of variables, we do not expect to see many observations for which there are indices i < j < k such that A_i and A_k occur in the observation but A_j does not.In this paper we study the problem of discovering fragments of orders of variables implicit in collections of unordered observations. We define measures that capture how well a given order agrees with the observed data. We describe a simple and efficient algorithm for finding all the fragments that satisfy certain conditions. We also discuss the sometimes necessary postprocessing for selecting only the best fragments of order. Also, we relate our method with a sequencing approach that uses a spectral algorithm, and with the consecutive ones problem. We present experimental results on some real data sets (author lists of database papers, exam results data, and paleontological data).

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 3: Jonathan E. Atkins , Erik G. Boman , Bruce Hendrickson, A Spectral Algorithm for Seriation and the Consecutive Ones Problem, SIAM Journal on Computing, v.28 n.1, p.297-310, Feb. 1999 [doi>10.1137/S0097539795285771]
• 4: Kellogg S. Booth , George S. Lueker, Linear algorithms to recognize interval graphs and test for the consecutive ones property, Proceedings of seventh annual ACM symposium on Theory of computing, p.255-265, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803776]
• 5: K. S. Booth and G. S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using P-Q tree algorithms. J. of Comp. and Syst. Sci., 13:335--379, 1976.
• 6: T. F. Chan and D. C. Resasco. A framework for the analysis and construction of domain decomposition preconditioners. Technical Report CAM-87-09, UCLA, 1987.
• 7: F. R. K. Chung. Spectral Graph Theory. CBMS Regional Conference Series in Mathematics, 1997.
• 8: R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge, 1998.
• 9: M. Fortelius. Private communication. 2003.
• 10: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 11: Wen-Lian Hsu, A simple test for the consecutive ones property, Journal of Algorithms, v.43 n.1, p.1-16, April 2002 [doi>10.1006/jagm.2001.1205]
• 12: J. Jernvall and M. Fortelius. Common mammals drive the evolutionary increase of hypsodonty in the neogene. Nature, 417:538--540, 2002.
• 13: Y. Koren and D. Harel. Multi-scale algorithm for the linear arrangement problem. Technical Report MCS02-04, Faculty of Mathematics and Computer Science, The Weizmann Institute of Science, 2002.
• 14: Heikki Mannila , Christopher Meek, Global partial orders from sequential data, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.161-168, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347122]
• 15: Heikki Mannila , Hannu Toivonen , A. Inkeri Verkamo, Discovery of Frequent Episodes in Event Sequences, Data Mining and Knowledge Discovery, v.1 n.3, p.259-289, 1997 [doi>10.1023/A:1009748302351]
• 16: A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In In Advances in Neural Information Processing Systems, 2001.
• 17: Alexandrin Popescul , Lyle H. Ungar , Gary William Flake , Steve Lawrence , C. Lee Giles, Clustering and Identifying Temporal Trends in Document Databases, Proceedings of the IEEE Advances in Digital Libraries 2000, p.173, May 22-24, 2000
• 18: A. Pothen, H. Simon, and L. Wang. Spectral nested dissection. Technical Report CS-92-01, Pennsylvania State University, Department of Computer Science, 1992.
• 19: Raghu Ramakrishnan , Johannes Gehrke, Database Management Systems, McGraw-Hill Higher Education, 2000
• 20: H. D. Simon. Partitioning of unstructured mesh problems for parallel processing. Computing Systems in Engineering, 2, 1991.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Keywords:
consecutive ones property, discovering hidden orderings, novel data mining algorithms, spectral analysis of data