基于后缀自动机的轨迹模式挖掘方法*

如何有效的从轨迹数据中挖掘轨迹模式和规律具有重要意义,本文基于交通路网研究移动对象轨迹预测,将序列分析方法和马尔科夫统计模型结合,提出了一种基于后缀自动机的变阶马尔科夫模型挖掘方法。该方法根据移动对象的历史轨迹数据进行学习训练,计算轨迹序列上下文的概率特征,建立序列的后缀自动机模型,结合当前实际轨迹数据,动态自适应预测将来的位置信息。实验结果表明：相比固定阶马尔科夫模型,随着阶数的增加（L>=2）,固定阶马尔科夫模型预测的精度逐步降低,而该方法能动态自适应,精度保持在81.3%左右,取得较好的预测效果;同时,该方法只需线性的时间和空间开销,大大降低了存储空间和时间,能实现大规模数据的在线学习。     

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

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

深层碳酸盐岩储存空间预测方法仿真

深层碳酸盐岩本身具有的较强非均质性与位置深度,均使储存空间预测难度有所上升,为此,引入概率后缀树模型,面向深层碳酸盐岩提出一种储存空间预测方法.基于经典马尔科夫模型,采用概率后缀树描述模型参数、指代模型建模序列,建立条件概率存在差异时的约束条件.通过遍历概率后缀树,获取深层碳酸盐岩储存空间的匹配序列,结合与预测储存空间...     

符号序列多阶Markov分类

针对基于固定阶Markov链模型的方法不能充分利用不同阶次子序列结构特征的问题,提出一种基于多阶Markov模型的符号序列贝叶斯分类新方法。首先,建立了基于多阶次Markov模型的条件概率分布模型;其次,提出一种附后缀表的n-阶子序列后缀树结构和高效的树构造算法,该算法能够在扫描一遍序列集过程中建立多阶条件概率模型;最后,提出符号序列的贝叶斯分类器,其训练算法基于最大似然法学习不同阶次模型的权重,分类算法使用各阶次的加权条件概率进行贝叶斯分类预测。在三个应用领域实际序列集上进行了系列实验,结果表明：新分类器对模型阶数变化不敏感;与使用固定阶模型的支持向量机等现有方法相比,所提方法在基因序列与语音序列上可以取得40%以上的分类精度提升,且可输出符号序列Markov模型最优阶数参考值。     

基于概率后缀树的移动对象轨迹预测

在移动对象轨迹预测中,针对低阶马尔可夫模型预测准确率不高、高阶模型状态空间膨胀的问题,提出一种基于概率后缀树(PST)的动态自适应变长马尔可夫模型预测方法。首先依时间先后将移动对象的轨迹路径序列化;然后根据移动对象的历史轨迹数据进行学习训练,计算序列上下文的概率特征,建立路径序列的概率后缀树模型,结合当前实际轨迹数据,动态自适应预测将来的位置信息。实验结果表明,该模型在二阶时取得最高的预测精度,随着阶数的增加,预测精度保持在82%左右,能取得较好的预测效果;同时空间复杂度呈指数级减少,大大节省了存储空间。该方法充分利用历史轨迹数据和当前轨迹信息预测未来轨迹,能够提供更加灵活、高效的基于位置服务。     

异构信息网络数据上的融合概率图模型

针对异构信息网络中存在多种数据目标类型,以及多种数据连接关系的问题,将多个主题模型和马尔科夫逻辑网相结合,提出了一种融合概率图模型。多个主题模型可以分别描述不同数据目标子空间的主题分布,实现对多种数据目标的预处理。用一阶逻辑子句描述的连接规则构建马尔科夫逻辑网,将每个主题模型中的不同数据目标连接起来。通过使用Gibbs采样,可以对异构网络进行参数学习和推理。在国际通用的异构信息网络DBLP数据集上的实验结果表明,使用融合概率图模型能够更好地表示不同的数据目标和连接关系。实验对比了4种典型的分类方法,多次采样得到的分类结果稳定,对作者、文章和会议取得了较好的分类结果。     

基于CHMM的背景差算法

为了解决背景差算法在前景提取的过程中对光照变化的敏感性和提取的前景中容易产生椒盐噪声的问题,提出了一种基于耦合隐马尔科夫模型的背景差方法.对像素的马尔科夫性进行了分析,并对像素建立耦合隐马尔科夫模型,通过时间统计的方法统计了像素隐含状态的转移概率,通过实验的方法选取了合适的前景标准差和背景标准差,利用Viterbi算法来求解耦合隐马尔科夫模型的最优隐含状态问题,运用该算法对一段交通监控视频进行分析,表明了该算法能够有效的抑制光照变化的影响,并且能够在一定程度上抑制前景噪声的出现.     

基于傅里叶-隐马尔科夫模型的人体行为识别

研究人行为识别的正确性,针对提高对人体行为序列图像进行识别的能力,隐马尔科夫模型(HMM)是一种统计分析模型,具有时序模式分析能力.为了增加图像信息的有效性,提出了一种傅里叶与隐马尔科夫模型相结合的方法人体行为识别方法.通过获得各种人体行为的二值图像序列,对待识别的序列图像提取具有旋转、平移和尺度不变性的傅立叶特征,采用了一种基于中心距的傅里叶描述子,利用改进的隐马尔科夫模型对提取的特征向量进行分类,得到人体行为的识别结果.试验结果表明,系统的识别率与HMM的状态数和观察值数有关,方法是有效且可行的,设计适当的HMM分类器能使系统的识别率达到90%以上,实际应用效果满足要求.     

DNA序列的二阶隐马尔科夫模型分类

隐马尔可夫模型是对DNA序列建模的一种简单且有效的模型, 实际应用中通常采用一阶隐马尔可夫模型. 然而, 由于其一阶无后效性的特点, 一阶隐马尔科夫模型无法表示非相邻碱基间的依赖关系, 从而导致序列中一些有用统计特征的丢失. 本文在分析DNA序列特有的生物学构造的基础上, 提出一种用于DNA序列分类的二阶隐马尔可夫模型, 该模型继承了一阶隐马尔可夫模型的优点, 充分表达了蕴涵在DNA序列中的生物学统计特征, 使得新模型具有明确的生物学意义. 基于新模型, 提出一种DNA序列的贝叶斯分类新方法, 并在实际DNA序列上进行了实验验证. 实验结果表明, 由于二阶隐马尔可夫模型充分反映了DNA序列碱基间的结构信息, 新方法有效地提高了序列的分类精度.     

针对PM2.5单时间序列数据的动态调整预测模型

针对细颗粒物PM2.5的浓度预测,本文提出了基于单时间序列数据的动态调整模型.在动态指数平滑算法中,指数平滑次数与参数基于样本数据并借助二分查找进行调整.在动态马尔科夫模型中,马尔科夫链的残差状态数、隐马尔科夫模型的隐状态数、连续样本数和阈值参数都通过训练数据加以调整.动态调整模型将指数平滑法和马尔科夫模型有效结合起来,指数平滑法得到的预测值由马尔科夫模型进行校正,从而提高预测准确度.基于大量实际PM2.5数据进行测试,验证了算法的有效性.并与其他现有的灰色模型、人工神经网络、自回归滑动平均模型、支持向量机等方法进行了对比,表明所提模型能够得到精度更高的预测结果.本文模型不局限于PM2.5数据,还可应用于其他类型的数据预测.     

基于灰色马尔可夫Verhulst模型的因特网访问人数预测分析

为了科学准确地预测近几年因特网访问人数,提出了应用灰色马尔可夫Verhulst模型进行预测的方法。首先,利用历史数据建立灰色Verhulst模型,通过确定系数可获得因特网访问人数的时间响应序列的表达式,从而可获得未来年份因特网访问人数的发展序列值。然后,结合马尔可夫链过程将序列状态划分为三类,通过确定状态转移矩阵可获得序列处于各状态的概率值及与各状态对应的预测中值,最终求得各序列的修正值。最后,通过2006/12~2012/6期间我国互联网上网人数的历史数据,预测了最近四个统计时段的访问人数。实例表明,该模型预测结果的误差更小、精度更高,还能提供预测结果的波动范围及出现概率,能够为网络建设及管理提供决策依据。     

基于混合马尔科夫树模型的ICS异常检测算法

针对工业控制系统中现有异常检测算法在语义攻击检测方面存在的不足,提出一种基于混合马尔科夫树模型的异常检测算法,充分利用工业控制系统的阶段性和周期性特征,构建系统正常运行时的行为模型|混合马尔科夫树.该模型包含合法的状态事件、合法的状态转移、正常的概率分布以及正常的转移时间间隔等4种信息,基于动态自适应的方法增强状态事件的关联度并引入时间间隔信息以实现对复杂语义攻击的检测,语义建模时设计一种剪枝策略以去除模型中的低频事件、低转移事件以及冗余节点,当被检测行为使得模型的以上4种信息产生的偏差超过阈值时,判定该行为异常.最后,基于OMNeT++网络仿真环境构建一个简化的污水处理系统对本文算法进行功能性验证,并利用真实物理测试床的数据集对算法的检测准确度进行性能验证.验证结果表明,本文算法能有效消除人机交互和常规诊断等操作带来的噪声影响,对复杂语义攻击具有较高的检出率,且能识别传统的非语义攻击.     

Prediction suffix trees for supervised classification of sequences

This paper presents a statistical test and algorithms for patterns extraction and supervised classification of sequential data. First it defines the notion of prediction suffix tree (PST). This type of tree can be used to efficiently describe variable order chain. It performs better than the Markov chain of order L and at a lower storage cost. We propose an improvement of this model, based on a statistical test. This test enables us to control the risk of encountering different patterns in the model of the sequence to classify and in the model of its class. Applications to biological sequences are presented to illustrate this procedure. We compare the results obtained with different models (Markov chain of order L, Variable order model and the statistical test, with or without smoothing). We set out to show how the choice of the parameters of the models influences performance in these applications. Obviously these algorithms can be used in other fields in which the data are naturally ordered.     

基于UML的软件Markov链使用模型的构建

构建软件的使用模型是进行软件可靠性测试及软件可靠性评估的基础.近年来,如何由软件的UML模型构造软件的使用模型成为研究热点.对于大型的软件系统来说,应用现有方法构建的软件Markov链使用模型的状态空间过于庞大,模型描述困难,不利于测试用例的自动生成及软件可靠性评估.针对以上问题,提出了一种由UML模型构建Markov链使用模型的方法.该方法将场景的前置条件和后置条件作为Markov链使用模型的状态,将场景的执行及执行概率作为状态之间的转移及转移概率.与现有方法相比,新方法构建的Markov链使用模型的状态空间小且无需人为干预,而且可以很方便地生成测试输入从而进行可靠性测试.针对UML模型的有效性,提出了经过可靠性评估扩展的UML模型生成Markov链使用模型的验证算法.最后通过一个卫星控制系统的实例对新方法的性能进行了验证.     

基于混合高斯隐马尔可夫模型的带式输送机堆煤时刻预测方法

提出了一种基于混合高斯隐马尔可夫模型的带式输送机堆煤时刻预测方法。该方法根据传感器采集的带式输送机功率时序数据建立带式输送机运行状态的混合高斯隐马尔可夫模型,基于该模型采用基于图的状态序列遍历算法和基于切普曼-柯尔莫哥罗夫方程的概率转移算法对带式输送机堆煤时刻进行预测:基于图的状态序列遍历算法通过寻找当前状态到堆煤状态的通路确定剩余时间;基于切普曼-柯尔莫哥罗夫方程的概率转移算法通过粒子群优化算法及切普曼-柯尔莫哥罗夫方程交叉验证来获取训练样本上失败状态的概率阈值,并计算当前的状态迁移到超过失败状态概率阈值的转移次数来确定剩余时间。基于煤矿生产实际数据集的实验验证了该方法可有效预测带式输送机的堆煤发生时刻。     

面向漏洞生命周期的安全风险度量方法

为了反映信息系统安全漏洞的风险随时间动态变化的规律,构建基于吸收Markov链的漏洞生命周期模型,计算先验历史漏洞信息作为模型输入,构造漏洞生命周期的状态转移概率矩阵,在时间维度上利用矩阵对状态演化过程进行推导.借鉴通用漏洞评分标准分析漏洞威胁影响,给出安全漏洞的时间维度风险量化方法,并对漏洞生命周期各状态发生概率的演化规律进行总结和分析.最后以典型APT攻击场景中“WannaCry”勒索病毒的漏洞利用过程为例,验证了模型及方法的合理性和有效性.     

MPEG VBR视频流—统计特性及其模型

该文分析了已有的MPEG VBR视频流模型及其缺点,并在此基础上对VBR视频流的统计特性进行了研究,实验结果表明,通过对整个视频流进行场景划分（聚类）,聚类间用Markov调制链建模,而每一聚类中独立的场景则可以采用TES模型基于GOP（Group Of Picture)而非帧进行建模,则该方法既能避免状态空间过大,又能避免帧间周期性的自相关,因而能够更好地拟合VBR视频流序列的一阶和二阶统计特性,同时,对独立场景的GOP分布函数可以采用Gamma函数进行拟合,自相关函数则可以采用双指数函数更好地拟合。