A Heuristic Algorithm for Global Partial Order Mining
WANG JinLong1,2, XU CongFu1
1.College of Computer Science and Technology, Zhejiang University, Hangzhou 3100272. School of Computer Engineering, Qingdao Technological University, Qingdao 266033
Abstract Sequential pattern mining is an important data mining research topic. In this paper the global partial order algorithm is firstly analyzed. Then, a heuristic algorithm is proposed for improving the process of global partial order construction. By using the local sequence pattern information, the problem of constructing the partial order model with high mathematical complexity can be avoided, and accurate results can be obtained. Finally, the efficiency and accuracy of the proposed method are validated by the experimental results on synthetic and real dataset.
[1] Agrawal R, Srikant R. Fast Algorithms for Mining Association Rules in Large Databases // Proc of the International Conference on Very Large Data Bases. Santiago de Chile, Chile, 1994: 487499 [2] Han Jiawei, Pei Jian, Yin Yiwen. Mining Frequent Patterns without Candidate Generation // Proc of the ACM SIGMOD International Conference on Management of Data. Dallas, USA, 2000: 112 [3] Agrawal R, Srikant R. Mining Sequential Patterns // Proc of the 11th International Conference on Data Engineering. Taipei, China, 1995: 314 [4] Srikant R, Agrawal R. Mining Sequential Patterns: Generalizations and Performance Improvements // Proc of the 5th International Conference on Extending Database Technology. Avignon, France, 1996: 317 [5] Peral J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. San Mateo, USA: Morgan Kaufmann, 1988 [6] Pei Jian, Wang Haixun, Liu Jian, et al. Discovering Frequent Closed Partial Orders from Strings. IEEE Trans on Knowledge and Data Engineering, 2006, 18(11): 14671481 [7] CasasGarriga C. Summarizing Sequential Data with Closed Partial Orders // Proc of the SIAM International Conference on Data Mining. Newport Beach, USA, 2005: 380391 [8] Mannila H, Meek C. Global Partial Orders from Sequential Data // Proc of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Boston, USA, 2000: 161168 [9] Goldenberg A, Moore A. Tractable Learning of Large Bayes Net Structures from Sparse Data [EB/OL]. [20040420]. www.autonlab.org/autonweb/14644/version/61part/s/data/goldenbergtractable.pdf?branch=main&language=en [10] Goldenberg A Q, Moore A W. Bayes Net Graphs to Understand CoAuthorship Networks? // Proc of the 3rd International Workshop on Link Discovery. Chicago, USA, 2005: 18 [11] Dempster A P, Laird N M, Rubin D B. Maximum Likelihood from Incomplete Data via the EM Algorithm. Journal of the Royal Statistical Society, 1977, B(39):138 [12] Ahuja A K, Magnanti T L, Orlin J H. Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, USA: PrenticeHall, 1993
2008, Vol. 21 
