What is the Dimension of Your Binary Data?
Authors:
- 1 December 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE International Conference on Data Mining (ICDM)
- No. 15504786,p. 603-612
Abstract
Many 0/1 datasets have a very large number of variables; however, they are sparse and the dependency structure of the variables is simpler than the number of variables would suggest. Defining the effective dimensionality of such a dataset is a nontrivial problem. We consider the problem of defining a robust measure of dimension for 0/1 datasets, and show that the basic idea of fractal dimension can be adapted for binary data. However, as such the fractal dimension is difficult to interpret. Hence we introduce the concept of normalized fractal dimension. For a dataset D, its normalized fractal dimension counts the number of independent columns needed to achieve the unnormalized fractal dimension of D. The normalized fractal dimension measures the degree of dependency structure of the data. We study the properties of the normalized fractal dimension and discuss its computation. We give empirical results on the normalized fractal dimension, comparing it against PCA.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- The Discrete Basis Problem2006
- LOCI: fast outlier detection using the local correlation integral2004
- Tiling Databases2004
- Profiling of High-Frequency Accident Locations by Use of Association RulesTransportation Research Record: Journal of the Transportation Research Board, 2003
- Deflating the dimensionality curse using multiple fractal dimensions2002
- KDD-Cup 2000 organizers' reportACM SIGKDD Explorations Newsletter, 2000
- An Introduction to Kolmogorov Complexity and Its Applications1997
- On Limited Nondeterminism and the Complexity of the V-C DimensionJournal of Computer and System Sciences, 1996
- NewsWeeder: Learning to Filter Netnews1995
- Multidimensional Scaling by Optimizing Goodness of Fit to a Nonmetric HypothesisPsychometrika, 1964