Mining long sequential patterns in a noisy environment

ABSTRACT

Pattern discovery in long sequences is of great importance in many applications including computational biology study, consumer behavior analysis, system performance analysis, etc. In a noisy environment, an observed sequence may not accurately reflect the underlying behavior. For example, in a protein sequence, the amino acid N is likely to mutate to D with little impact to the biological function of the protein. It would be desirable if the occurrence of D in the observation can be related to a possible mutation from N in an appropriate manner. Unfortunately, the support measure (i.e., the number of occurrences) of a pattern does not serve this purpose. In this paper, we introduce the concept of compatibility matrix as the means to provide a probabilistic connection from the observation to the underlying true value. A new metric match is also proposed to capture the "real support" of a pattern which would be expected if a noise-free environment is assumed. In addition, in the context we address, a pattern could be very long. The standard pruning technique developed for the market basket problem may not work efficiently. As a result, a novel algorithm that combines statistical sampling and a new technique (namely border collapsing) is devised to discover long patterns in a minimal number of scans of the sequence database with sufficiently high confidence. Empirical results demonstrate the robustness of the match model (with respect to the noise) and the efficiency of the probabilistic algorithm.

REFERENCES

• 1: 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
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 3: R. Baeza-Yates and G. Navarro. Faster approximate string matching. Algorithmica, 23(2), 127-158, 1999.
• 4: Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
• 5: G. Benson and M. Waterman. A method for fast database search for all k-nucleotide repeats. Nucleic Acid Research, 22, 4828-4836, 1994.
• 6: Alvis Brazma , Inge Jonassen , Jaak Vilo , Esko Ukkonen, Pattern Discovery in Biosequences, Proceedings of the 4th International Colloquium on Grammatical Inference, p.257-270, July 12-14, 1998
• 7: Douglas Burdick , Manuel Calimlim , Johannes Gehrke, MAFIA: A Maximal Frequent Itemset Algorithm for Transactional Databases, Proceedings of the 17th International Conference on Data Engineering, p.443-452, April 02-06, 2001
• 8: Pedro Domingos , Geoff Hulten, Mining high-speed data streams, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.71-80, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347107]
• 9: R. Durbin, S. Eddy, A. Krough, and G. Mitchison. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, 1998.
• 10: Minos N. Garofalakis , Rajeev Rastogi , Kyuseok Shim, SPIRIT: Sequential Pattern Mining with Regular Expression Constraints, Proceedings of the 25th International Conference on Very Large Data Bases, p.223-234, September 07-10, 1999
• 11: National Center for Biotechnology Information. Available at "http:/www.ncbi.nlm.nih.gov".
• 12: Dimitrios Gunopulos , Heikki Mannila , Sanjeev Saluja, Discovering All Most Specific Sentences by Randomized Algorithms, Proceedings of the 6th International Conference on Database Theory, p.215-229, January 08-10, 1997
• 13: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 14: Jiawei Han , Jian Pei , Behzad Mortazavi-Asl , Qiming Chen , Umeshwar Dayal , Mei-Chun Hsu, FreeSpan: frequent pattern-projected sequential pattern mining, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.355-359, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347167]
• 15: W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58, 13-30, 1963.
• 16: Dao-I Lin , Zvi M. Kedem, Pincer Search: A New Algorithm for Discovering the Maximum Frequent Set, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.105-119, March 23-27, 1998
• 17: Heikki Mannila , Hannu Toivonen, Levelwise Search and Borders of Theories in KnowledgeDiscovery, Data Mining and Knowledge Discovery, v.1 n.3, p.241-258, 1997 [doi>10.1023/A:1009796218281]
• 18: Heikki Mannila , Hannu Toivonen , A. Inkeri Verkamo, Discovery of Frequent Episodes in Event Sequences, Data Mining and Knowledge Discovery, v.1 n.3, p.259-289, 1997 [doi>10.1023/A:1009748302351]
• 19: Ramakrishnan Srikant , Rakesh Agrawal, Mining Generalized Association Rules, Proceedings of the 21th International Conference on Very Large Data Bases, p.407-419, September 11-15, 1995
• 20: Ramakrishnan Srikant , Rakesh Agrawal, Mining Sequential Patterns: Generalizations and Performance Improvements, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.3-17, March 25-29, 1996
• 21: Hannu Toivonen, Sampling Large Databases for Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.134-145, September 03-06, 1996
• 22: Jeffrey Scott Vitter, An efficient algorithm for sequential random sampling, ACM Transactions on Mathematical Software (TOMS), v.13 n.1, p.58-67, March 1987 [doi>10.1145/23002.23003]
• 23: Jason Tsong-Li Wang , Gung-Wei Chirn , Thomas G. Marr , Bruce Shapiro , Dennis Shasha , Kaizhong Zhang, Combinatorial pattern discovery for scientific data: some preliminary results, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.115-125, May 24-27, 1994, Minneapolis, Minnesota, United States
• 24: Wei Wang , Jiong Yang , Philip S. Yu, Meta-patterns: Revealing Hidden Periodic Patterns, Proceedings of the 2001 IEEE International Conference on Data Mining, p.550-557, November 29-December 02, 2001
• 25: Wei Wang , Jiong Yang , Philip S. Yu, Mining patterns in long sequential data with noise, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.28-33, Dec. 2000 [doi>10.1145/380995.381008]
• 26: Jiong Yang , Wei Wang , Philip S. Yu, Mining asynchronous periodic patterns in time series data, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.275-279, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347150]
• 27: Jiong Yang , Wei Wang , Philip S. Yu, Infominer: mining surprising periodic patterns, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.395-400, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502571]
• 28: J. Yang, W. Wang, and P. Yu. Mining long sequential patterns in a noisy environment. IBM Research Report, 2001.
• 29: M. J. Zaki , S. Parthasarathy , Wei Li , M. Ogihara, Evaluation of sampling for data mining of association rules, Proceedings of the 7th International Workshop on Research Issues in Data Engineering (RIDE '97) High Performance Database Management for Large-Scale Applications, p.42, April 07-08, 1997
• 30: M. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. New algorithms for fast discovery of association rules. Proc. 3rd KDD, 283-286, 1997.
• 31: Mohammed J. Zaki, SPADE: an efficient algorithm for mining frequent sequences, Machine Learning, v.42 n.1/2, p.31-60, Jan. 2001 [doi>10.1023/A:1007652502315]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
        G.1.10 Applications

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

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

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms, Documentation, Theory