Towards parameter-free data mining
Eamonn Keogh, Stefano Lonardi, Chotirat Ann Ratanamahatana · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · 2004
Most data mining algorithms require the setting of many input parameters. Two main dangers of working with parameter-laden algorithms are the following. First, incorrect settings may cause an algorithm to fail in finding the true patterns. Second, a perhaps more insidious problem is that the algorithm may report spurious patterns that do not really exist, or greatly overestimate the significance of the reported patterns. This is especially likely when the user fails to understand the role of parameters in the data mining process.Data mining algorithms should have as few parameters as possible, ideally none. A parameter-free algorithm would limit our ability to impose our prejudices, expectations, and presumptions on the problem at hand, and would let the data itself speak to us. In this work, we show that recent results in bioinformatics and computational theory hold great promise for a parameter-free data-mining paradigm. The results are motivated by observations in Kolmogorov complexity theory. However, as a practical matter, they can be implemented using any off-the-shelf compression algorithm with the addition of just a dozen or so lines of code. We will show that this approach is competitive or superior to the state-of-the-art approaches in anomaly/interestingness detection, classification, and clustering with empirical tests on time series/DNA/text/video datasets.
Cited by 567 works. doi:10.1145/1014052.1014077
Authors
References
- Modeling by shortest data description
- Data mining and knowledge discovery: making sense out of data
- Inferring decision trees using the minimum description lenght principle
- An Introduction to Kolmogorov Complexity and Its Applications
- FastMap
- Using the triangle inequality to accelerate k-means
- On Comparing Classifiers: Pitfalls to Avoid and a Recommended Approach
- A symbolic representation of time series, with implications for streaming algorithms
- Information theory and the living system
- Book Review: An introduction to Kolmogorov Complexity and its Applications Second Edition, 1997 by Ming Li and Paul Vitanyi (Springer (Graduate Text Series))