PROXIMUS: a framework for analyzing very high dimensional discrete-attributed datasets

ABSTRACT

This paper presents an efficient framework for error-bounded compression of high-dimensional discrete attributed datasets. Such datasets, which frequently arise in a wide variety of applications, pose some of the most significant challenges in data analysis. Subsampling and compression are two key technologies for analyzing these datasets. PROXIMUS provides a technique for reducing large datasets into a much smaller set of representative patterns, on which traditional (expensive) analysis algorithms can be applied with minimal loss of accuracy. We show desirable properties of PROXIMUS in terms of runtime, scalability to large datasets, and performance in terms of capability to represent data in a compact form. We also demonstrate applications of PROXIMUS in association rule mining. In doing so, we establish PROXIMUS as a tool for preprocessing data before applying computationally expensive algorithms or as a tool for directly extracting correlated patterns. Our experimental results show that use of the compressed data for association rule mining provides excellent precision and recall values (near 100%) across a range of support thresholds while reducing the time required for association rule mining drastically.

REFERENCES

• 1: IBM Quest synthetic data generation code. http://www.almaden.ibm.com/cs/quest/syndata.html.
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 3: Michael W. Berry , Susan T. Dumais , Gavin W. O'Brien, Using linear algebra for intelligent information retrieval, SIAM Review, v.37 n.4, p.573-595, Dec. 1995 [doi>10.1137/1037127]
• 4: Daniel Boley, Principal Direction Divisive Partitioning, Data Mining and Knowledge Discovery, v.2 n.4, p.325-344, December 1998 [doi>10.1023/A:1009740529316]
• 5: C. Borgelt. Finding association rules/hyperedges with the apriori algorithm. http://fuzzy.cs.Uni-Magdeburg.de/ borgelt/apriori/apriori.html, 1996.
• 6: Moody T. Chu , Robert E. Funderlic, The Centroid Decomposition: Relationships between Discrete Variational Decompositions and SVDs, SIAM Journal on Matrix Analysis and Applications, v.23 n.4, p.1025-1044, 2001 [doi>10.1137/S0895479800382555]
• 7: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society. Series B (Methodological), 39 (1):1--38, 1977.
• 8: David Gibson , Jon M. Kleinberg , Prabhakar Raghavan, Clustering Categorical Data: An Approach Based on Dynamical Systems, Proceedings of the 24rd International Conference on Very Large Data Bases, p.311-322, August 24-27, 1998
• 9: R. M. Gray. Vector quantization. IEEE ASSP, 1(2):4--29, 1984.
• 10: Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, ROCK: a robust clustering algorithm for categorical attributes, Information Systems, v.25 n.5, p.345-366, July 2000 [doi>10.1016/S0306-4379(00)00022-3]
• 11: G. Gupta and J. Ghosh. Value balanced agglomerative connectivity clustering. In SPIE Proc., April 2001.
• 12: E. Han, G. Karypis, V. Kumar, and B. Mobasher. Hypergraph-based clustering in high-dimensional datasets: A summary of results. Bulletin of the Technical Committee on Data Engineering, 21(1), 1998.
• 13: Z. Huang. A fast clustering algorithm to cluster very large categorical data sets in data mining. In Research Issues on Data Mining and Knowledge Discovery, 1997.
• 14: G. H. John and P. Langley. Static versus dynamic sampling for data mining. In E. Simoudis, J. Han, and U. M. Fayyad, editors, Proc. 2nd Int. Conf. Knowledge Discovery and Data Mining, KDD, pages 367--370. AAAI Press, 2--4 1996.
• 15: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 16: Tamara G. Kolda , Dianne P. O'Leary, A semidiscrete matrix decomposition for latent semantic indexing information retrieval, ACM Transactions on Information Systems (TOIS), v.16 n.4, p.322-346, Oct. 1998 [doi>10.1145/291128.291131]
• 17: T. G. Kolda and D. P. O'Leary. Computation and uses of the semidiscrete matrix decomposition. ACM Transactions on Information Processing, 1999.
• 18: Mehmet Koyutürk , Ananth Grama , Naren Ramakrishnan, Algebraic Techniques for Analysis of Large Discrete-Valued Datasets, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.311-324, August 19-23, 2002
• 19: G. H. Lincoff. Mushroom Records Drawn From The Audubon Society Field Guide to North American Mushrooms. Alfred A. Knopf, New York, 1981.
• 20: J. MacQueen. Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symposium, volume 1, pages 281--297, 1967.
• 21: S. McConnell and D. B. Skillicorn. Outlier detection using semi-discrete decomposition. Technical Report 2001--452, Dept. of Computing and Information Science, Queen's University, 2001.
• 22: D. P. O'Leary and S. Peleg. Digital image compression by outer product expansion. IEEE Trans. on Communications, 31:441--444, 1983.
• 23: M. Özdal and C. Aykanat. Clustering based on data patterns using hypergraph models. to be published in Data Mining and Knowledge Discovery, 2003.
• 24: Foster Provost , Venkateswarlu Kolluri, A Survey of Methods for Scaling Up Inductive Algorithms, Data Mining and Knowledge Discovery, v.3 n.2, p.131-169, June 1999 [doi>10.1023/A:1009876119989]
• 25: Hannu Toivonen, Sampling Large Databases for Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.134-145, September 03-06, 1996
• 26: Mohammed J Zaki , Srinivasan Parthasarathy , Wei Li , Mitsunori Ogihara, Evaluation of Sampling for Data Mining of Association Rules, University of Rochester, Rochester, NY, 1996
• 27: S. Zyto, A. Grama, and W. Szpankowski. Semi-discrete matrix transforms (SDD) for image and video compression. In D. Marinescu and C. Lee, editors, Process Coordination and Ubiquitous Computing, pages 249--259. Kluwer, 2002.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

Keywords:
compressing discrete-valued vectors, non-orthogonal matrix decompositions, semi-discrete decomposition