Compression, Clustering and Pattern Discovery in Very High Dimensional Discrete-Attribute Datasets

This paper presents an efficient framework for error-bounded compression of high-dimensional discreteattribute datasets. Such datasets, which frequently arise in a wide variety of applications, pose some of the most significant challenges in data analysis. Sub-sampling and compression are two key technologies for analyzing these datasets. The proposed framework, 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 and discovery and interpretation of interesting patterns. We also demonstrate sample applications of PROXIMUS in association rule mining and semantic classification of term-document matrices. Our experimental results on real datasets show that use of the compressed data for association rule mining provides excellent precision and recall values (above 90%) across a range of problem parameters while reducing the time required for analysis drastically. We also show excellent interpretability of the patterns discovered by PROXIMUS in the context of clustering and classification of terms and documents. In doing so, we establish PROXIMUS as a tool for both preprocessing data before applying computationally expensive algorithms and directly extracting correlated patterns