一种事件序列的加权变阶马尔可夫模型

doi:10.3969/j.issn.1000-3428.2014.04.034

摘要/Abstract

摘要： 变阶马尔可夫模型是对事件序列建模的一种简单且有效的模型，但经典变阶马尔可夫模型只考虑转移概率，未关注子序列本身出现的频率。为此，提出一种加权的变阶马尔可夫模型，在经典变阶马尔可夫模型基础上根据子序列的频率构建一棵加权概率后缀树。给出一种剪枝策略，在构建后缀树时根据结点相似程度剪除树枝，以提高模型的泛化能力，并在线性时间内完成加权概率后缀树的构建。通过将加权的模型应用于事件序列分类进行实验验证，结果表明，该模型可以对不同领域的实际序列数据进行有效分类。

关键词: 变阶马尔可夫模型, 概率后缀树, 事件序列, 分类, 加权, 剪枝

Abstract: Variable-order Markov Model(VLMM) is a simple but effective model for event sequences modeling. However, the classic VLMM only considers the transition probability, without taking into account the frequency of the substring. A Weighted VLMM(WVLMM) is proposed in this paper, constructing a Weighted Probabilistic Suffix Tree(WPST) via the frequency of the substring based on the classic VLMM. It also proposes a strategy for branches pruning based on the degree of the similarity of the nodes while constructing the tree, in order to improve the generalization ability of the model, and to construct the tree in a linear time complexity. To validate the effectiveness of the model, the proposed model is applied to the classification of event sequences. Experimental results demonstrate that the new model can make an effective classification on real-world sequence datasets in different applications.

Key words: Variable-order Markov Model(VLMM), probabilistic suffix tree, event sequence, classification, weighted, pruning

中图分类号:

TP312

吴宏和，陈黎飞，郭躬德. 一种事件序列的加权变阶马尔可夫模型[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2014.04.034.

WU Hong-he, CHEN Li-fei, GUO Gong-de. A Weighted Variable Order Markov Model for Event Sequences[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2014.04.034.

https://www.ecice06.com/CN/Y2014/V40/I4/175

参考文献

参考文献 [1] Han Jiawei, Kamber M. 数据挖掘: 概念与技术[M]. 范明, 孟小峰, 译. 北京: 机械工业出版社, 2012. [2] 王清毅, 刘洁, 蔡庆生. 事件序列中的知识发现研究[J]. 小型微型计算机系统, 1999, 20(1): 16-19. [3] 刘培华, 王立宏. 一种改进的事件序列相似性计算公式[J]. 计算机工程与应用, 2009, 45(7): 68-69. [4] Lin Jie, Adjeroh D, Jiang Binghua. Probabilistic Suffix Array: Efficient Modeling and Prediction of Protein Families[J]. Bioinformatics, 2012, 28(10): 1314-1323. [5] Eddy S R. Hidden Markov Models[J]. Current Opinion in Structural Biology, 1996, 6(3): 361-365. [6] Ron D, Singer Y, Tishby N. The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length[J]. Machine Learning, 1996, 25(2): 117-149. [7] Schulz M H, Weese D, Rausch T, et al. Fast and Adaptive Variable Order Markov Chain Construction[C]//Proc. of the 8th International Workshop on Algorithms in Bioinformatics. Karlsruhe, Germany: [s. n.], 2008: 306-317. [8] Rissanen J. A Universal Data Compression System[J]. IEEE Transactions on Information Theory, 1983, 29(5): 656-664. [9] Apostolico A, Bejerano G. Optimal Amnesic Probabilistic Automata or How to Learn and Classify Proteins in Linear Time and Space[J]. Journal of Computational Biology, 2000, 7(3/4): 381-393. [10] Karampatziakis N, Kozen D. Learning Prediction Suffix Trees with Winnow[C]//Proc. of the 26th Annual International Conference on Machine Learning. [S. l.]: ACM Press, 2009: 489-496. [11] Leonardi F G. A Generalization of the PST Algorithm: Modeling the Sparse Nature of Protein Sequences[J]. Bioinformatics, 2006, 22(11): 1302-1307. [12] Bejerano G, Yona G. Variations on Probabilistic Suffix Trees: Statistical Modeling and Prediction of Protein Families[J]. Bioinformatics, 2001, 17(1): 23-43. [13] Ephraim Y, Dembo A, Rabiner L R. A Minimum Dis- crimination Information Approach for Hidden Markov Modeling[J]. IEEE Transactions on Information Theory, 1989, 35(5): 1001-1013. [14] Steinwart I, Christmann A. Support Vector Machines[M]. New York, USA: Springer-Verlag, 2008. [15] Hassoun M H. Fundamentals of Artificial Neural Networks[M]. Cambridge, USA: MIT Press, 1995. [16] Bühlmann P, Wyner A J. Variable Length Markov Chains[J]. The Annals of Statistics, 1999, 27(2): 480-513. [17] Dekel O, Shalev S S, Singer Y. The Power of Selective Memory: Self-bounded Learning of Prediction Suffix Trees[C]//Proc. of Conference on Neural Information Processing Systems. [S. l.]: Springer, 2004: 345-352. [18] Ukkonen E. On-line Construction of Suffix Trees[J]. Algorithmica, 1995, 14(3): 249-260. [19] Maa? M G. Computing Suffix Links for Suffix Trees and Arrays[J]. Information Processing Letters, 2007, 101(6): 250- 254. [20] van Rijsbergen C J. Information Retrieval[M]. [S. l.]: Butter- worths, 1979. [21] 陈黎飞, 郭躬德. 最近邻分类的多代表点学习算法[J]. 模式识别与人工智能, 2011, 24(6): 882-888. [22] Cover T, Hart P. Nearest Neighbor Pattern Classification[J]. IEEE Transactions on Information Theory, 1967, 13(1): 21-27. [23] Punta M, Coggill P C, Eberhardt R Y, et al. The Pfam Protein Families Database[J]. Nucleic Acids Research, 2012, 40(1): 290-301. [24] Loiselle S, Rouat J, Pressnitzer D, et al. Exploration of Rank Order Coding with Spiking Neural Networks for Speech Recognition[C]//Proc. of International Joint Conference on Neural Networks. [S. l.]: IEEE Press, 2005: 2076-2080. [25] Xiong Tengke, Wang Shengrui, Jiang Qingshan, et al. A New Markov Model for Clustering Categorical Sequences[C]//Proc. of the 11th International Conference on Data Mining. [S. l.]: IEEE Press, 2011: 854-863. [26] Kadouche R, Pigot H, Abdulrazak B, et al. User’s Behavior Classification Model for Smart Houses Occupant Prediction[J]. Activity Recognition in Pervasive Intelligent Environments, 2011, 4(7): 149-164. [27] Wei Dan, Jiang Qingshan, Wei Yanjie, et al. A Novel Hierarchical Clustering Algorithm for Gene Sequences[J]. BMC Bioinformatics, 2012, 13(1): 174-186. 编辑顾逸斐

选择文件类型/文献管理软件名称

选择包含的内容