Towards parameter-free data mining

ABSTRACT

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.

REFERENCES

• 1: Allison, L., Stern, L., Edgoose, T., Dix, T.I. Sequence Complexity for Biological Sequence Analysis. Computers & Chemistry 24(1): 43--55 (2000)
• 2: Benedetto, D., Caglioti, E., & Loreto, V. Language trees and zipping. Physical Review Letters 88, 048702, (2002).
• 3: Xin Chen , Sam Kwong , Ming Li, A compression algorithm for DNA sequences and its applications in genome comparison, Proceedings of the fourth annual international conference on Computational molecular biology, p.107, April 2000, Tokyo, Japan [doi>10.1145/332306.332352]
• 4: Dasgupta, D. & Forrest,S. Novelty Detection in Time Series Data using Ideas from Immunology." In Proc. of the International Conference on Intelligent Systems (1999).
• 5: Pedro Domingos, A Process-Oriented Heuristic for Model Selection, Proceedings of the Fifteenth International Conference on Machine Learning, p.127-135, July 24-27, 1998
• 6: Elkan, C. Using the triangle inequality to accelerate k-Means. In Proc. of ICML 2003. pp 147--153
• 7: Charles Elkan, Magical thinking in data mining: lessons from CoIL challenge 2000, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.426-431, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502576]
• 8: Ergun, F., Muthukrishnan, S., & Sahinalp, S.C. Comparing Sequences with Segment Rearrangements. FSTTCS 2003:
• 9: Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.163-174, May 22-25, 1995, San Jose, California, United States
• 10: Martin Farach , Michiel Noordewier , Serap Savari , Larry Shepp , Abraham Wyner , Jacob Ziv, On the entropy of DNA: algorithms and measurements based on memory and rapid convergence, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.48-57, January 22-24, 1995, San Francisco, California, United States
• 11: Flexer, A. Statistical evaluation of neural networks experiments: Minimum requirements and current practice. In Proc. of the 13th European Meeting on Cybernetics and Systems Research, vol. 2, pp 1005-1008, Austria, 1996
• 12: Gatlin, L. Information Theory and the Living Systems. Columbia University Press, 1972.
• 13: Martin Gavrilov , Dragomir Anguelov , Piotr Indyk , Rajeev Motwani, Mining the stock market (extended abstract): which measure is best?, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.487-496, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347189]
• 14: Xianping Ge , Padhraic Smyth, Deformable Markov model templates for time-series pattern matching, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.81-90, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347109]
• 15: Goldberger, A.L., Amaral, L., Glass, L, Hausdorff, J.M., Ivanov, P.Ch., Mark, R.G., Mietus, J.E., Moody, G.B., Peng, C.K., Stanley, H.E.. PhysioBank, PhysioToolkit, and PhysioNet: Circulation 101(23):e215-e220
• 16: Goodman, J. Comment on "Language Trees and Zipping", unpublished manuscript, 2002 (available at {http://research.microsoft.com/~joshuago/}.
• 17: Konstantinos Kalpakis , Dhiral Gada , Vasundhara Puttagunta, Distance Measures for Effective Clustering of ARIMA Time-Series, Proceedings of the 2001 IEEE International Conference on Data Mining, p.273-280, November 29-December 02, 2001
• 18: Keogh, E. http://www.cs.ucr.edu/~eamonn/SIGKDD2004.
• 19: Keogh, E. & Folias, T. The UCR Time Series Data Mining Archive. Riverside CA. 2002. {http://www.cs.ucr.edu/~eamonn/TSDMA/index.html}.
• 20: Eamonn Keogh , Shruti Kasetty, On the need for time series data mining benchmarks: a survey and empirical demonstration, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775062]
• 21: Eamonn Keogh , Jessica Lin , Wagner Truppel, Clustering of Time Series Subsequences is Meaningless: Implications for Previous and Future Research, Proceedings of the Third IEEE International Conference on Data Mining, p.115, November 19-22, 2003
• 22: Li, M., Badger, J.H., Chen, X., Kwong, S, Kearney, P., & Zhang, H. An information-based sequence distance and its application to whole mitochondrial genome phylogeny. Bioinformatics 17: 149--154, 2001.
• 23: Ming Li , Xin Chen , Xin Li , Bin Ma , Paul Vitányi, The similarity metric, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 24: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 25: Jessica Lin , Eamonn Keogh , Stefano Lonardi , Bill Chiu, A symbolic representation of time series, with implications for streaming algorithms, Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13-13, 2003, San Diego, California [doi>10.1145/882082.882086]
• 26: D. Lowenstern , H. Hirsh , M. Noordiwier , P. Yianilos, DNA Sequence Classification Using Compression-Based Induction, Certer for Discrete Mathematics & Theoretical Computer Science, 1995
• 27: Loewenstern, D., & Yianilos, P.N. Significantly lower entropy estimates for natural DNA sequences, Journal of Computational Biology, 6(1), 1999.
• 28: Junshui Ma , Simon Perkins, Online novelty detection on temporal sequences, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956828]
• 29: J. R. Quinlan , R. L. Rivest, Inferring decision trees using the minimum description length principle, Information and Computation, v.80 n.3, p.227-248, Mar. 1989 [doi>10.1016/0890-5401(89)90010-2]
• 30: Ratanamahatana, C.A. & Keogh, E. Making Time-series Classification More Accurate Using Learned Constraints. In proceedings of SIAM International Conference on Data Mining (SDM '04), Lake Buena Vista, Florida, April 22-24, 2004.
• 31: Rissanen, J. Modeling by shortest data description. Automatica, vol. 14 (1978), pp. 465--471.
• 32: Steven L. Salzberg, On Comparing Classifiers: Pitfalls toAvoid and a Recommended Approach, Data Mining and Knowledge Discovery, v.1 n.3, p.317-328, 1997 [doi>10.1023/A:1009752403260]
• 33: Cyrus Shahabi , Xiaoming Tian , Wugang Zhao, TSA-Tree: A Wavelet-Based Approach to Improve the Efficiency of Multi-Level Surprise and Trend Queries on Time-Series Data, Proceedings of the 12th International Conference on Scientific and Statistical Database Management (SSDBM'00), p.55, July 26-28, 2000 [doi>10.1109/SSDM.2000.869778]
• 34: Michail Vlachos , Marios Hadjieleftheriou , Dimitrios Gunopulos , Eamonn Keogh, Indexing multi-dimensional time-series with support for multiple distance measures, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956777]
• 35: Changzhou Wang , Xiaoyang Sean Wang, Supporting Content-Based Searches on Time Series via Approximation, Proceedings of the 12th International Conference on Scientific and Statistical Database Management (SSDBM'00), p.69, July 26-28, 2000 [doi>10.1109/SSDM.2000.869779]
• 36: Yairi, T., Kato, Y., & Hori, K. Fault Detection by Mining Association Rules from House-keeping Data, Proc. of Int'l Sym. on AI, Robotics and Automation in Space, 2001.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
anomaly detection, clustering, parameter-free data mining