变阶马尔科夫模型算法实现

Algorithm Implementation of Variable Order Markov Model

如何快速有效对历史数据进行统计建模和规律挖掘具有重要意义.鉴于模型在实际数据挖掘应用的局限及马尔科夫模型的良好统计特性,设计实现了基于后缀数组和后缀自动机的变阶马尔科夫模型.算法在后缀树形结构实现的基础上,引入后缀链,实现各状态子序列的快速跳转,能动态自适应计算不同阶长概率的需求.实验结果表明:相比传统马尔科夫模型,模型能在线性时间和空间复杂度内,构建历史数据的概率统计特征及各状态后缀子序列之间的链接关系,大大降低了存储空间和时间,能实现大规模数据的在线学习和应用.

It is of great significance how to model and mine historical data quickly and effectively. Based on the statistical characteristics of Markov model, this study designs and implements a variable order Markov model based on suffix array and suffix automata, in view of the limitations of the model in practical data mining applications. Based on the realization of suffix tree structure, the suffix chain is introduced to realize the quick jump of each state subsequence, and the requirement of different order length probability can be dynamically and adaptively calculated. The experimental results show that compared with the traditional Markov model, the model constructs the link between suffix sequence characteristics of probability and statistics of historical data and the state in linear time and space complexity, which can greatly reduce the storage space and time, and realize online learning and application of large data.