Distance-function design and fusion for sequence data

ABSTRACT

Sequence-data mining plays a key role in many scientific studies and real-world applications such as bioinformatics, data stream, and sensor networks, where sequence data are processed and their semantics interpreted. In this paper we address two relevant issues: sequence-data representation, and representation-to-semantics mapping. For representation, since the best one is dependent upon the application being used and even the type of query, we propose representing sequence data in multiple views. For each representation, we propose methods to construct a <i>valid kernel</i> as the distance function to measure <i>similarity</i> between sequences. For mapping, we then find the best combination of the individual distance functions, which measure similarity of different views, to depict the target semantics. We propose a <i>super-kernel function-fusion</i> scheme to achieve the optimal mapping. Through theoretical analysis and empirical studies on UCI and real world datasets, we show our approach of multi-view representation and fusion to be mathematically valid and very effective for practical purposes.

REFERENCES

• 1: http://www.bioinfo.rpi.edu/zukerm/bio-5495/rnafold-html/node2.html.
• 2: Henrik André-Jönsson , Dushan Z. Badal, Using Signature Files for Querying Time-Series Data, Proceedings of the First European Symposium on Principles of Data Mining and Knowledge Discovery, p.211-220, June 24-27, 1997
• 3: Byoung-Kee Yi , H. V. Jagadish , Christos Faloutsos, Efficient Retrieval of Similar Time Sequences Under Time Warping, Proceedings of the Fourteenth International Conference on Data Engineering, p.201-208, February 23-27, 1998
• 4: Yoshua Bengio, Gradient-Based Optimization of Hyperparameters, Neural Computation, v.12 n.8, p.1889-1900, August 2000 [doi>10.1162/089976600300015187]
• 5: Tolga Bozkaya , Nasser Yazdani , Meral Özsoyoğlu, Matching and indexing sequences of different lengths, Proceedings of the sixth international conference on Information and knowledge management, p.128-135, November 10-14, 1997, Las Vegas, Nevada, United States [doi>10.1145/266714.266880]
• 6: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 7: S. Chandrasekaran , B. S. Manjunath , Y. F. Wang , J. Winkeler , H. Zhang, An eigenspace update algorithm for image analysis, Graphical Models and Image Processing, v.59 n.5, p.321-332, Nov. 1997 [doi>10.1006/gmip.1997.0425]
• 8: Olivier Chapelle , Vladimir Vapnik , Olivier Bousquet , Sayan Mukherjee, Choosing Multiple Parameters for Support Vector Machines, Machine Learning, v.46 n.1-3, p.131-159, 2002 [doi>10.1023/A:1012450327387]
• 9: G. Chartrand. Introductory graph theory. New York: Dover, 1985.
• 10: L. Chen, M. Tamer, and V. Oria. Symbolic representation and retrieval of moving object trajectories. University of Waterloo School of Computer Science Waterloo, Canada, Technical Report CS-2003-30., 2003.
• 11: C. S. Daw, C. E. A. Finney, and E. R. Tracy. A review of symbolic analysis of experimental data. Review of Scientific Instruments, 74(2), 2003.
• 12: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 13: Pierre Geurts, Pattern Extraction for Time Series Classification, Proceedings of the 5th European Conference on Principles of Data Mining and Knowledge Discovery, p.115-127, September 03-05, 2001
• 14: L. Hammel and J. Patel. Searching on the secondary structure of protein sequences. Proceedings of the 28th VLDB Conference, 2002.
• 15: T. Hishiki, N. Collier, C. Nobata, T. Ohta, N. Ogata, T. Sekimizu, R. Steiner, H. Park, and J. Tsujii. Developing nlp tools for genome informatics: An information extraction perspective. In Genome Informatics. Universal Academy Press, Inc., Tokyo, Japan, 1998., 1998.
• 16: Yun-Wu Huang , Philip S. Yu, Adaptive query processing for time-series data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.282-286, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.318357]
• 17: Y. Huhtala, J. Karkkainen, and H. Toivonen. Mining for similarities in aligned time series using wavelets. Data Mining and Knowlege Discovery: Theory, Tools, and Technology, SPIE Proceeding Series, 1999.
• 18: Ela Hunt , Malcolm P. Atkinson , Robert W. Irving, A Database Index to Large Biological Sequences, Proceedings of the 27th International Conference on Very Large Data Bases, p.139-148, September 11-14, 2001
• 19: Piotr Indyk , Nick Koudas , S. Muthukrishnan, Identifying Representative Trends in Massive Time Series Data Sets Using Sketches, Proceedings of the 26th International Conference on Very Large Data Bases, p.363-372, September 10-14, 2000
• 20: H. JA and M. BJ. The meaning and use of the area under a receiver operating characteristic (roc) curve. Radiology, 143(1), 1982.
• 21: 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
• 22: 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]
• 23: Risi Imre Kondor , John D. Lafferty, Diffusion Kernels on Graphs and Other Discrete Input Spaces, Proceedings of the Nineteenth International Conference on Machine Learning, p.315-322, July 08-12, 2002
• 24: Flip Korn , H. V. Jagadish , Christos Faloutsos, Efficiently supporting ad hoc queries in large datasets of time sequences, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.289-300, May 11-15, 1997, Tucson, Arizona, United States
• 25: G. R. G. Lanckriet, M. H. Deng, N. Cristianini, M. I. Jordan, and W. S. Noble. Kernel-based data fusion and its application to protein function prediction in yeast. Proceedings of the Pacific Symposium on Biocomputing, 2004.
• 26: 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]
• 27: V. Moulton, M. Zuker, M. Steel, R. Pointon, and D. Penny. Metrics on rna secondary structures. Journal of Computational Biology, 2000.
• 28: S. B. Needleman and C. D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of molecular biology, 1970.
• 29: Sanghyun Park , Sang-Wook Kim , Wesley W. Chu, Segment-based approach for subsequence searches in sequence databases, Proceedings of the 2001 ACM symposium on Applied computing, p.248-252, March 2001, Las Vegas, Nevada, United States [doi>10.1145/372202.372334]
• 30: V. Roth, J. Laub, J. Buhmann, and K.-R. Muller. Going metric: Denoising pairwise data. In Neural Information Processing Systems (NIPS), 2002.
• 31: V. Roth and V. Steinhage. Nonlinear discriminant analysis using kernel functions. NIPS, 1999.
• 32: B. Scholkopf and A. Smola. Learning with kernels. MIT Press, 2001.
• 33: T. F. Smith and M. S. Waterman. Identification of common molecular subsequences. Journal of molecular biology, 1981.
• 34: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 35: C. Watkins. Dynamic alignment kernels. Technical Report CSD-TR-98-11, 1999.
• 36: Gang Wu , Yi Wu , Long Jiao , Yuan-Fang Wang , Edward Y. Chang, Multi-camera spatio-temporal fusion and biased sequence-data learning for security surveillance, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA [doi>10.1145/957013.957126]
• 37: Y. Wu, C.-Y. Lin, E. Y. Chang, and J. R. Smith. Multimodal kernel fusion for news video concept detection. IEEE International Conference on Image Processing (ICIP), 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

General Terms:
Algorithms

Keywords:
multiple-view representation, representation-to-semantics mapping, sequence-data mining, sequence-data representation, super-kernel fusion