Algorithms for Context Based Sequential Pattern Mining

• Autorzy: Ziembiński R.
• Języki publikacji: EN

Abstrakty

EN

This paper describes practical aspects of a novel approach to the sequential pattern mining named Context Based Sequential Pattern Mining (CBSPM). It introduces a novel ContextMapping algorithm used for the context pattern mining and an illustrative example showing some advantages of the proposed method. The approach presented here takes into consideration some shortcomings of the classic problem of the sequential pattern mining. The significant advantage of the classic sequential patterns mining is simplicity. It introduces simple element construction, built upon set of atomic items. The comparison of sequence's elements utilizes simple inclusion of sets. But many practical problems like web event mining, monitoring, tracking and rules generation often require mining more complex data. The CBSPM takes into account non nominal attributes and similarity of sequence's elements. An approach described here extends traditional problem adding a vector of context attributes of any kind to sequences and sequence’s elements. Context vectors contain details about sequence's and element's origin. The mining process results in context patterns containing additional, valuable context information useful in interpretation of patterns origin.

Słowa kluczowe

EN

knowledge discovery; sequential patterns mining; events mining; pattern; context pattern; context mapping

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 76, nr 4
• Strony: 495--510
• Opis fizyczny: bibliogr. 15 poz., tab.

Twórcy

autor

Ziembiński R.

• Institute of Computing Sciences Poznań Univesity of Technology, ul. Piotrowo 3a, 60-965 Poznań, Poland,

Bibliografia

• [1] Agrawal, R., Faloutsos, C., Swami, A. N.: Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, Springer-Verlag, London, UK, 1993, 69-84.
• [2] Agrawal, R., Srikant, R.: Fast algorithms for mining association rules, Proc. 20th Int. Conf. Very Large Data Bases, {VLDB} (C. Z. Jorge B. Bocca, Matthias Jarke, Ed.), Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 12--15˜ 1994, 487-499.
• [3] Agrawal, R., Srikant, R.: Mining sequential patterns, IEEE Computer Society Press, Taipei, Taiwan, 1995, 3-14.
• [4] Garofalakis, M. N., Rastogi, R., Shim, K.: {SPIRIT}: Sequential Pattern Mining with Regular Expression Constraints, 1999.
• [5] Han, J., Dong, G., Yin, Y.: Efficient Mining of Partial Periodic Patterns in Time Series Database, Fifteenth International Conference on Data Engineering, IEEE Computer Society, Sydney, Australia, 1999, 43-52.
• [6] Han, J., Pei, J., Mortazavi-Asl, B., Chen, Q., Dayal, U., Hsu, M.-C.: FreeSpan: frequent pattern-projected sequential pattern mining, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, ACM Press, New York, NY, USA, 2000, 355-359.
• [7] Han, J., Pei, J., Mortazavi-Asl, B., Chen, Q., Dayal, U., Hsu, M.-C.: PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth, Proceedings of the 17th International Conference on Data Engineering, Heidelberg, Germany, 2001, 215-224.
• [8] Lee, S.-L., Chun, S.-J., Kim, D.-H., Lee, J.-H., Chung, C.-W.: Similarity Search for Multidimensional Data Sequences, Proceedings of the 16th International Conference on Data Engineering, IEEE Computer Society, Washington, DC, USA, 2000, 599-608.
• [9] Morzy, T.: Discovery associations: algorithms and datastructures, OWN Poznan, PAN Press, Poznan, Poland, 2004.
• [10] Pinto, H., Han, J., Pei, J., Wang, K., Chen, Q., Dayal, U.: Multi-dimensional sequential pattern mining, Proceedings of the tenth international conference on Information and knowledge management, ACM Press, New York, NY, USA, 2001, 81-88.
• [11] Srikant, R., Agrawal, R.: Mining Sequential Patterns: Generalizations and Performance Improvements, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, Lecture Notes In Computer Science, vol. 1057 of Lecture Notes In Computer Science, Springer-Verlag, London, UK, 1996, 3-17.
• [12] Stefanowski, J., Ziembinski, R.: Mining Context Based Sequential Patterns, Proceedings of the Third International Atlantic Web Intelligence Conference: Advances in Web Intelligence (P.Szczepaniak, J.Kacprzyk, A.Niewiadomski, Eds.), Lecture Notes in Computer Science, vol. 3528 of Lecture Notes in Computer Science, Springer-Verlag, Lodz, Poland, June 2005, 401-407.
• [13] Yan, X., Han, J.: gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), IEEE Computer Society, Washington, DC, USA, 2002, page 721.
• [14] Zaki, M. J.: SPADE: An Efficient Algorithm for Mining Frequent Sequences, Mach. Learn., 42(1-2), January-February 2001, 31-60.
• [15] Zaki, M. J.: Efficiently mining frequent trees in a forest, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, ACM Press, New York, NY, USA, 2002, 71-80.