On effective classification of strings with wavelets

ABSTRACT

In recent years, the technological advances in mapping genes have made it increasingly easy to store and use a wide variety of biological data. Such data are usually in the form of very long strings for which it is difficult to determine the most relevant features for a classification task. For example, a typical DNA string may be millions of characters long, and there may be thousands of such strings in a database. In many cases, the classification behavior of the data may be hidden in the compositional behavior of certain segments of the string which cannot be easily determined apriori. Another problem which complicates the classification task is that in some cases the classification behavior is reflected in global behavior of the string, whereas in others it is reflected in local patterns. Given the enormous variation in the behavior of the strings over different data sets, it is useful to develop an approach which is sensitive to both the global and local behavior of the strings for the purpose of classification. For this purpose, we will exploit the multi-resolution property of wavelet decomposition in order to create a scheme which can mine classification characteristics at different levels of granularity. The resulting scheme turns out to be very effective in practice on a wide range of problems.

REFERENCES

• 1: Rakesh Agrawal , King-Ip Lin , Harpreet S. Sawhney , Kyuseok Shim, Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.490-501, September 11-15, 1995
• 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: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 4: M. Deshpande, G. Karypis. Evaluation of Techniques for Classifying Biological Sequences. Technical report, TR 01--33, University of Minnesota, 2001.
• 5: R. Duda, P. Hart. Pattern Analysis and scene analysis, Wiley 19773.
• 6: Johannes Gehrke , Venkatesh Ganti , Raghu Ramakrishnan , Wei-Yin Loh, BOAT—optimistic decision tree construction, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.169-180, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 7: Johannes Gehrke , Raghu Ramakrishnan , Venkatesh Ganti, RainForest - A Framework for Fast Decision Tree Construction of Large Datasets, Proceedings of the 24rd International Conference on Very Large Data Bases, p.416-427, August 24-27, 1998
• 8: J, Gehrke, W.-Y. Lob, R. Ramakrishnan. Data Mining with Decision Trees. ACM SIGKDD Conference Tutorial, 1999.
• 9: Valerie Guralnik , George Karypis, A Scalable Algorithm for Clustering Sequential Data, Proceedings of the 2001 IEEE International Conference on Data Mining, p.179-186, November 29-December 02, 2001
• 10: Valery Guralnik , Jaideep Srivastava, Event detection from time series data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.33-42, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312190]
• 11: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 12: J. Han, G. Dong, Y. Yin. Efficient Mining of partial periodic patterns in time series databases. ICDE Conference, 1999.
• 13: H. V. Jagadish , Nick Koudas , S. Muthukrishnan, Mining Deviants in a Time Series Database, Proceedings of the 25th International Conference on Very Large Data Bases, p.102-113, September 07-10, 1999
• 14: H. V. Jagadish , Nick Koudas , Divesh Srivastava, On effective multi-dimensional indexing for strings, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.403-414, May 15-18, 2000, Dallas, Texas, United States
• 15: Mike James, Classification algorithms, Wiley-Interscience, New York, NY, 1985
• 16: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 17: D. A. Keim, M. Heczko. Wavelets and their Applications in Databases. ICDE Conference, 2001.
• 18: E. J. Keogh, M. J. Pazzini. An enhanced representation of time series data which allows fast and accurate classification, clustering and relevance feedback. KDD Conference, 1998.
• 19: E. Keogh, P. Smyth. A probabilistic approach to pattern matching in time-series databases. KDD Conference, 1997.
• 20: Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , Sharad Mehrotra, Locally adaptive dimensionality reduction for indexing large time series databases, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.151-162, May 21-24, 2001, Santa Barbara, California, United States
• 21: B. Liu, W. Hsu, Y. Ma. Integrating Classification and Association Rule Mining. KDD Conference, 1998.
• 22: S. Manganaris. Learning to Classify Sensor Data. TR-CS-95-10, Vanderbilt University, March 1995.
• 23: Tim Oates, Identifying distinctive subsequences in multivariate time series by clustering, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.322-326, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312268]
• 24: C. Perng, H. Wang, S. Zhang, S. Parker. Landmarks: A new model for similarity-based pattern querying in time-series databases, ICDE Conference, 2000.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Deduction (e.g., natural, rule-based)
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representations (procedural and rule-based)

General Terms:
Algorithms, Measurement, Performance