Frequent Closed Partial Orders Mining in Sequences

Abstract:

Mining partial orders from sequence data is an important data mining task with broad applications. As partial orders mining is a NP-hard problem, many efficient pruning algorithm have been proposed. In this paper, we improve a classical algorithm of discovering frequent closed partial orders from string. For general sequences, we consider items appearing together having equal chance to calculate the detecting matrix used for pruning. Experimental evaluations from a real data set show that our algorithm can effectively mine FCPO from sequences.

• Periodical: Advanced Materials Research (Volumes 846-847)
• Pages: 1304-1307
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.846-847.1304
• Online since: November 2013
• Authors: Ye Wang*, Yan Jia, Lu Min Zhang
• Keywords: Depth-First Search, Partial Order, Sequence Data

References

[1] R. Agrawal and R. Srikant. Mining Sequential Patterns". In Proc. of the 11th Int, l Conference on Data Engineering, Taipei, Taiwan, Mar. (1995).

[2] R. Srikant and R. Agrawal, Mining Sequential Patterns: Generalizations and Performance Improvements", Proc. Fifth Int'l Conf. Extending Database Technology (EDBT , 96), Mar. (1996).

DOI: 10.1007/bfb0014140

[3] J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, and M. -C. Hsu, PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth", Proc. 2001 Int'l Conf. Data Eng. (ICDE , 01), pp.215-224, Apr. (2001).

DOI: 10.1109/icde.2001.914830

[4] M.J. Zaki, SPADE: An Efficient Algorithm for Mining Frequent Sequences, Machine Learning, vol. 42, nos. 1-2, pp.31-60, (2001).

[5] J. Ayres, J. Flannick, J. Gehrke, and T. Yiu, Sequential Pattern Mining Using a Bitmap Representation", Proc. 2002 ACM SIGKDD Int'l Conf. Knowledge Discovery and Data Mining (KDD , 02), pp.429-435, Jul. (2002).

DOI: 10.1145/775047.775109

[6] H. Mannila, H. Toivonen, and A. I. Verkamo, Discovery of Frequent Episodes in Event Sequences, Data Mining and Knowledge Discovery, vol. 1, pp.259-289, (1997).

DOI: 10.1023/a:1009748302351

[7] H. Mannila and C. Meek, Global Partial Orders from Sequential Data", Proc. 2000 ACM SIGKDD Int'l Conf. Knowledge Discovery in Databases (KDD , 00), pp.150-160, Aug. (2000).

DOI: 10.1145/347090.347122

[8] G. Casas-Garriga, Summarizing Sequential Data with Closed Partial Orders", Proc. 2005 SIAM Int, l Conf. Data Mining, Apr. (2005).

DOI: 10.1137/1.9781611972757.34

[9] J. Pei, H. Wang, J. Liu, K. Wang, J. Wang, P. S. Yu, Discovering Frequent Closed Partial Orders from Strings, Proc. IEEE Transactions on Knowledge and Data Engineering, vol. 18, no. 11, pp.1467-1481, Nov. (2006).

DOI: 10.1109/tkde.2006.172

[10] L. Zhang, Y. Jia, B. Zhou, Microblogging sentiment analysis using emotional vector[C]/Cloud and Green Computing (CGC), 2012 Second International Conference on. IEEE, 2012: 430-433.

DOI: 10.1109/cgc.2012.29