（计算机系统结构专业论文）基于分段半马尔可夫模型的在线序列模式检测方法研究.pdf

基于分段半马尔可夫模型的在线序列模式检测方法研究 浙江大学硕士学位论文 摘要 在线检测序列模式是时间序列的一种重要分析方法，它在实时的时间序列中 检测出与给定的示例模式相似的模式，并报告它们出现的位置。该方法是现实应 用领域中对时间序列进行实时监管和控制的一项关键技术，它对故障诊断及修 正、异常情况分析、证券市场投资中技术分析、人类动作分析、生命特征监控等 领域来说具有非常重要的意义。这些巨大的应用前景使得该技术越来越成为当前 时间序列数据挖掘领域中的一个研究热点。目前，大量在线检测序列模式方法已 被提出，主要分为以下两大类：1 ) 基于滑动窗口进行子序列匹配的，例如欧式 距离、d t w 距离等等；2 ) 基于概率模型的，例如分段半马尔可夫模型。前者思 想简单，容易实现，但时间复杂度高；后者建模较为复杂，但其效率高，在许多 方面要比前一种方法优越。然而现有的分段半马尔可夫模型只能解决具有近似相 同长度的模式检测问题，不允许模式在时间上存在缩放。在线检测在时间上( x 轴) 存在任意缩放的相似模式仍是一个具有挑战性的问题。 本文提出一种修正的分段半马尔可夫模型，它对现有的分段半马尔可夫模型 做了以下两方面的修正：1 ) 用每一段的偏移量分布来代替该段的观察值分布；2 ) 为每一段引进该段两个端点间振幅( y 坐标) 差值分布。同时给出了对示例模式 建模、参数估计的方法，在此基础上把该模型应用到在线检测相似序列模式中来。 我们在两套合成数据和两套实际数据中做了大量的实验来验证算法的性能。实验 结果表明，该模型不仅能够快速检测出在时间上存在任意缩放的相似模式，而且 具有较好的抗噪能力。 关键词：时间序列，在线检测，分段半马尔可夫模型，隐马尔可夫模型 基于分段半马尔可夫模型的在线序列模式检测方法研究塾大学理圭堂堕型婆 1 1 研究背景 第一章绪论 随着信息技术曰新月异的发展，人们在日常事务处理和科学研究中积累的大 量各种类型的数据得以保存下来。在过去几十年里，特别是在m t e m e t 兴起后， 全球的信息量就成爆炸性增长，这远远超出了人们的理解能力，使用传统的分析 方法已经不能发现这些数据中所隐藏的信息。因此，如何充分有效地管理和利用 这些海量数据、发现这些数据背后隐含的规律和知识，就成为人们目前非常关注 的问题。 在这些保存的数据中，很大一部分是根据时间顺序对历史事件的记录，我们 称之为时态数据( t e 釉p o r a l d a t a ) 。根据记录数据类型的不同，时态数据主要包括 三种类型：时间序列，事务序列和事件序列。时间序列( r n m es e r i e s ) 可定义为“a j l o r d e r e ds e to f r e a lv a l u e s ”“3 ，它是一类重要的复杂数据对象。社会、科学、经济、 医学、技术等领域中广泛存在着大量的时间序列数据有待进一步的分析和处理。 比如人类身体某部位在每个时刻的坐标数据；气象卫星上不断向地面传回的各种 时间序列图像和数据；金融证券市场中每天的股票价格数据；人类在每个时刻的 心跳数据；半导体生产过程中产生的监测数据等等。时间序列知识发现对人类社 会发展具有重大意义。 传统的时间序列分析是作为概率统计学科的一个课题来研究，着重研究具有 随机性的动态数据，研究方法着重于全局模型的构造，常用的方法有自回归滑动 平均模型( a u t o - r e g r e s s i v ea n dm o v i n ga v e m g em o d e l ，a r m a ) 等。3 。传统时间序 列分析是一种验证型的分析工具，先提出假设然后进行验证，目的是为了对系统 整体行为的把握和预测，它不适合用于发现型的任务。然而在实际问题中，往往 需要对时间序列局部特征进行分析，比如发现频繁出现的变化模式；比较不同序 列在某段时间内，其运动变化是否相似；检测时间序列是否在某一时刻产生特定 模式等等。因此，自上个世纪9 0 年代以来，时间序列数据挖掘引起了越来越多 学者的关注和重视。时间序列数据挖掘是针对时间序列的模式发现过程，旨在研 究隐含在时间序列之中的更深层次的知识，包括时间序列的相似性查询、时间序 基于分段半马尔可夫模型的在线序列模式检测方法研究 浙江大学硕士学位论文 的序列模式x 。，可以计算p ( x + i m ，) 的值来比较两个模式间的相似度。 分段半马尔可夫模型以精度高、计算量适中等优点已经在某些领域取得了良 好效果。”“，但由于其不支持时间轴上缩放，如图1 1 所示的两种相似模式都会 被误认为是不相似的。 2 ) 其它基于结构或模型的相似度度量 k e o 曲和s m y t h 提出了一种概率距离模型“，在时间序列的模式表示基础上， 结合先验知识，定义了模板的变形概率，从而得到两条时间序列之间的概率距离。 概率距离模型支持时间序列的不连续性、振幅伸缩、时间轴伸缩和弯曲。但是不 支持未知或未定义的变形，需要准确和详细韵先验知识。 n a n o p o u l o s 、a 1 c o c k 和m a n 0 1 0 p o u l o s 等人提取时间序列模式的均值、方差、 斜率、峰值等等特征，然后用多层感知器神经网络来计算模式问的相似度“。 1 2 4 在线序列模式检测 在线检测序列模式是时间序列的一个重要分析方法，它在实时的时间序列 ( 其长度是随着时间的推移而不断增加) 中检测出与给定的示例模式相似的模 式，并报告它们出现的位置。在线检测序列模式是现实应用领域中对时间序列进 行实时监管和控制的一项关键技术，它对故障诊断及修正、异常情况分析、证券 市场投资中技术分析、人类动作分析、生命特征监控等领域来说具有非常重要的 意义。 对于在线检测序列模式来说，最主要的问题是相似度量和检测效率等难点， 其中效率应该是要优先解决的问题。由于被检测的时间序列是动态不断增加的， 因此不能向检索时间序列数据库那样构造固定的索引来提高检测的效率。在目前 研究工作中，主要有两种在线检测序列模式的方法，分别是用滑动窗口( s l i d i n g w i n d o w ) 技术进行子序列匹配( s u b s e q u e n c em a t c l l i n g ) ，和基于概率模型的在 线检测。前者思想简单，容易实现，但时间复杂度高，它一般采用基于形状相似 度度量方法，需要用户预先设定相似序列模式间的距离阀值s ；后者建模 x 基于分段半马尔可夫模型的在线序列模式检测方法研究 浙江大学硕士学位论文 1 2 4 1 基于滑动窗口的在线序列模式检测 此类方法具体实现过程与选择的相似度度量方法有关。当该方法选择与欧式 距离等度量方法时，它可以描述如下：算法从被检测的实时序列的第一点开始， 取一个特定的窗口，然后再用欧式距离匹配窗口中的子序列与示例模式，接着滑 动窗口的起点到下一个点，继续匹配子序列，直到被检测的实时序列输入结束。 欧式距离鲁棒性差，并且不能检测时间缩放的相似的模式。当选择d 1 w 距离时， 当窗口的起点固定在某时间点上，窗口的终点是在一定范围内可变化的，就是要 反复计算多次d t w 距离后，窗口的起点才能移动下一点。d t w 距离鲁棒性高， 并支持时间轴的任意缩放，但其计算复杂度高，不适宜用于在线的序列模式检测。 在国内研究中，曾提出一种规范化的欧式距离度量方式，利用快速傅立叶变 换对动态序列与各个模式间的距离采用批处理方式进行相似性距离“。该方法能 加快检测速度，但不支持时间缩放的模式检测。 国外研究中，k e 0 曲等人用均匀缩放技术结合欧式距离来进行子序列匹配， 该方法只能检测如1 1 ( a ) 所示的均匀缩放的相似模式“；a 曜y r o s 等人提出的用 “c d c 血e r i o n ”技术“8 匹配模式的算法也有同样的局限性；f u 等人提出的用缩放 与规整( s c a l e da n dw a i p 酣m a t c h i i i g ，s w m ) “”来匹配模式能检测任意缩放的 相似模式，同时他们提出的下界( l o w e r b o u n d i n g ) 距离也能降低算法复杂度， 是一种较好的算法。 1 2 4 。2 基于模型的在线序列模式检测 基于分段半马尔可夫模型的在线序列模式检测是一种典型的基于模型的检 测方法，它己被应用到半导体生产过程中的终点检测。“2 ”等领域，并取得了很好 的效果，在许多方面都要比前几类方法好。 该方法首先要对示例序列模式q 用分段线性化表示，然后根据分段数建立 一个有个状态的分段半马尔可夫模型m 。，接着提取模式的特征值用于设定模 型的参数。在实时获得的被检测序列中，每获得一个点都用模型m 。计算该点属 于各个状态的概率，概率最大的状态被认为是该点的状态，如果状态是最后一个 状态时表示已经检测到了相似的模式。由于在检测过程中，每个点都只需要计算 9 基于分段半马尔可夫模型的在线序列模式检测方法研究 浙江大学硕士学位论文 一次，时间复杂度相对较低。但现有的分段半马尔可夫模型并不支持模式在时间 上的伸缩，无法检测出如1 1 所示的相似模式。 1 3 本文工作 1 4 1 研究目标 从前面的分析可知，在线检测序列模式领域中，目前对于检测在时间上( x 轴) 存在任意缩放的相似模式仍没有得到很好解决，这一问题现状是我们进一步 研究在线检测序列模式的动机。 首先我们定义一些本文常用的符号如表1 1 所示，接着我们的研究目标可以 描述如下：假设有一个实时获得的时间序列d ，一个由先验知识获得的示例序列 模式q ，其中l d l i q l 。我们再给出最大缩放度2 ，z 1 ，表示与q 相似的模式 在时间上允许伸长到q 的z 倍或缩短到q 的1 z 倍。我们目标是快速在_ d 中检测 出所有与q 相似( 在z 范围内) 的模式，并报告各个相似模式出现的位置。 表1 1 本文定义的一些符号 符号定义 d q x x 实时获得的时间序列 由先验知识获得的示例序列模式 时间序列x 的长度 时间序列x 的第i 个元素 x k 卅以序列x 第i 个元素为起点，第j 个元素为终点的子序列 !搓式量太缠丝廑：! 之! 1 4 2 研究内容 针对上述研究目标，在本文中我们提出一个修正的分段半马尔可夫模型，它 对现有的分段半马尔可夫做了以下两方面的修正： 1 用每一段的偏移量分布来代替该段的观察值分布。 2 为每一段引进该段两个端点间振幅( y 坐标) 差值分布。 同时给出了对示例模式建模、参数估计的方法，并引入了g e 的文章中提到 1 0 基于分段半马尔可夫模型的在线序列模式检测方法研究 浙江大学硕士学位论文 的附加状态前项状态( p r e - p a 呦ls t a t e ) m 1 ，明确给出了该值的确定方法。在 此基础上把该模型应用到在线检测相似序列模式中来。实验表明，该模型不仅能 够快速检测出在时间上存在任意缩放的相似模式，而且保证了模型的鲁棒性，比 传统方法有所改进。 1 4 3 本文结构 本文内容围绕着研究目标而展开，一共分为五章，具体内容安排如下： 第一章：绪论 介绍本文的研究背景与相关研究工作，并简要介绍本文的研究目标与内容。 第二章：基于滑动窗口的在线模式检测 介绍几种基于滑动窗口的在线序列模式检测算法，他们都能支持在时间轴上 存在缩放的相似模式检测。 第三章：修正的分段半马尔可夫模型 介绍隐马尔可夫、分段半马尔可夫的相关理论知识，并在这基础上给出修正 的分段半马尔可夫模型。 第四章：基于分段半马尔可夫的在线序列模式检测 在修正的分段半马尔可夫模型基础上给出了对示例模式建模、参数估计的方 法，以及在线检测相似模式的算法，及实验结果。 第五章：结论与展望 对全文的工作做总结，并展望未来工作的方向。 基于分段半马尔可夫模型的在线序列模式检测方法研究 浙江大学硕士学位论文 由于欧式距离是一个单调的凹函数，在实际应用中一般将2 1 式中的开平方 去掉，用欧式距离的平方来代替欧式距离，实践表明除了降低运算量外还有其它 方面的优点。“，在本文中欧式距离都是指欧式距离的平方。而为了消除序列幅度 对匹配结果的影响，在计算距离前要先将序列规范成均值为0 。1 。 欧式距离要求序列间要有相同的长度才有意义，因此不能匹配在时间上有伸 缩的序列模式。k e 0 班、p a l p a n a s 和z o r d a n 等人引进均匀缩放( u n i f o h ns c a l i n g ， u c ) 技术使得不同长度的序列模式也可以匹配“。假设有一个长度为n 的示例 模式q = q 。，g ：，q m ，和一个长度为m 的候选模式c = c l ，c 2 ，q ，其中m 与n 不必 相等。计算q 与c 的欧式距离前，先用u c 将c 缩放成长度为m 的序列c ： c j = q 删。 ，1 j m ( 2 2 ) 然后计算q 与c 的欧式距离，并用之来匹配q 与c 。图2 2 是计算两个长度不同 的时间序列间欧式距离示意图。 入一里八一! 厂、厂了 嘲佻栅k 耐 剐j l l 麟 o2 0柏6 01 0 01 2 01 4 01 6 01 2 0 0 图2 2 计算长度不同序列间歇式距离从上到下tc 的长度比q 长l 将c 均匀缩放成与q 相闻的长度的c 1 ，然后计算它们问的歇式更离 k e o g h 等人也给出了基于u c 的欧式距离下界( l d w e rb o u n d i n g ，l b ) 距离 函数，简称l 艮碰锯 “”，它能降低在线检测序列模式算法的复杂度。在给定候 选子序列c 与最大伸缩度f ；，为了计算候选子序列c 与q 的下界距离，首先要 对c 创建一个由两个序列组成的限定封套( b o u n d i n g e n v e l o p e ) ： u ，= m a x ( q ( h i + 1 ，q j ) ( 2 _ 3 ) 厶= 1 1 1 i n ( q ( h ) f i + l ，q i ) ( 2 4 ) 基于分段半马尔可夫模型的在线序列模式检测方法研究浙江大学硕主堂竺笙苎 则蚰一o g h ( q ，c ) 定义如下：加一魄 ( q ，c ) = f_1( 吼一u ；) 2 扩氆 u ；( 吼一厶) 2 矿吼4 continue 1 f 0 rd 中每一时刻的点 6 forw i i l d o w = i i l i n w i n d o w ，曲n w i n d o w + 1 ，m a 【w i n d o w7 将子序列dkf+w锄如w均匀缩短到长度为iqi的新序列c8 计算q 与c 的平方欧式距离d ( q ，c )9 i f d(q，c)占lo 报告检测到相似序列模式；b r e a k ：1 1 e n d i f1 2 e n df o r 1 3 e n df o r 输出t所有相似序列模式出现的位置 基于分段半马尔可夫模型的在线序列模式检测方法研究浙江大学硕士学焦羔堕 2 2 基于缩放与规整( s c a l e da n dw h r p e dm a t c h i n g ，s w m ) 距离方法 s w m 距离是结合了均匀缩放与删距离的一种相似度度量方式，它首次 由f u 、k e o g h 和l a u 等人在2 0 0 5 年提出“。在介绍s w m 前，我们首先介绍一 些相关知识： 2 2 1 相关知识 1 1 u r w 假设有两个时间序列a = q ，c 2 ，c 。与q = 吼，吼，q m ，它们的d t w 距离定义如下”3 ： d t ( g ，g ) = o(26) d t 仰7 ( d ，o ) = d t t 矿( o ，q ) = ( 2 7 )d t i 矿( d ，q ) = 日。( f i 8 ( a ) ，f i s t ( q ) ) + m i n d r i 矿( g ，r e s t ( q ) )d r i 矿( r _ e 就( d ) ，q ) (28)d t 矸( r - e 时( d ) ，r _ e 就( q ) ) 其中。表示空序列，n 毹哆) = q ，r e s t p ) = q ，g ，q ，b 表示两个 点的距离，这里我们用平方欧式距离表示它，即是： q 。( q ，q ，) = ( e q 7 ) 2 ( 2 9 ) d t w 距离是比欧式距离鲁棒性更强的距离，它不要求序列模式间点与点之间 进行一一对应匹配，允许它们在时间轴上有伸缩，长度不同。在序列匹配时，序 列模式可以进行自我复制，使得两条序列模式间相似的波形进行对齐匹配，图 2 4 是计算d t w 距离示意图。但d t 也会因为局部过度缩放，进而引起错误 的匹配，如图2 5 所示。同样，为了消除序列幅度对匹配结果的影响，在计算距 离前要先将序列规范成均值为0 。”。 d t w 距离可以通过动态规划( d y n 锄i cp r o g r 锄i n g ) 计算，它的计算时间复杂 度是d ( 1 c l + l q l ) 。而将它作为相似度度量方式时，在线检测的时间复杂度为 d ( 1 d h q f ( z 2 1 i 2 ) ) ，计算量太大，不适宜用于在线检测。 基于分段半马尔可夫模型的在线序列模式检测方法研究 浙江大学硕士学位论文 圈2 4 计算哪甩离，两序列闻匹配示意圈 圈2 5 ( a ) 两个不相似的序列模式( b ) 由于局部过于缩放，它们的啊鼯离为0 。 2 ) c o n s t n i n e d 姗( c d 硼) 与下界距离 为了降低d t w 的运算量，在计算d t w 距离时，可以设定约束规整路径的宽度 ，使得两序列间的对应的下标f 和j 需满足j 一，f j + r 。，“1 。假设有两个时 间序列g = c l ，岛，与q = g 。，吼，它们的约束动态规整距离 ( c o n s t r a i n e dd t w ，c d t w ) 定义如下： 酬，_ ：j q 嬲三。 眨埘 c d n 矿( o ，g ) = 0( 2 1 1 ) c d r 缈( c ，0 ) = c d r ( 0 ，q ) = o o( 2 1 2 ) fc d 硼7 ( c ，r e s ( q ) ，r ) c d z w ( c ，q ，r ) = 珧( 胁f ( c ) ，鼢f ( q ) ) + 1 i l i n c d 刑( r e j f ( c ) ，q ，r )( 2 1 3 ) i c d 刑( r e s f ( c ) ，r e s f ( q ) ，r ) 其中。表示空序列，成肼( c ) = c l ，r e 盯( c ) = c 2 ，c 3 ，g ，见。表示两 个点的距离，这里我们用平方欧式距离表示它，如式子( 2 9 ) 。 在约束规整路径宽度r 下，k e o 曲给出了c d t w 的下界距离函数l 巩( q ，c ) “。同样，首先要对c 创建一个由两个长度为m 的序列组成的限定封套： 硼( = m a x ( c 二( “一，) ，。( 。) ( 2 1 4 ) l w = m i i l ( c o ( 1 。) ，c 衄。( m ) ( 2 1 5 ) 基于分段半马尔可夫模型的在线序列模式检测方法研究塑垩盔堂堡主兰垡丝塞 则l 巩( q ，c ) 可以定义如下 屿( q ，c ) = ( 吼一矿啊) 2f ，吼 u w ( 缶一l 彤) 2 矿口。 u c f ( 吼一l e ) 2 扩氆 0 时，计算p ( f ，f ) 的递归函数如下： p ( f ，f ) _ m p lp ( f ，卜1 ) ，p ( 咒i 暑= f ) l j l 。 j 其中上述函数取得最大值时所对应的，可以通过矩阵舰e y 记录，以作为回 退指针时使用： 眦y ( f ，d _ a r g ? 3 x ；( i ，f 一1 ) a _ p ( 咒li = f ) 从定义可知，观察值序列y = y 。) ，。蜥所对应的概率最大的状态序列有最大 似然值m a x p ( t r ) ，而在时刻r 时模型对应的所在的状态为： s r _ a 略m a ) 【p ( f ，丁) f 至此可以从p r e y ( r ，丁) 开始，在p r e y 中找出以前观察值的最佳状态： s = p r e y ( s “，f + 1 ) ， f = z 一1 ，r 一2 ，l 这样，最佳的状态序列便可以求得。 3 1 4 向前一向后算法 h m m 的另一个基本推理过程是，在给定一个确定h m m 模型与观察值序列 y = m m 蜥下，求出模型在时刻f 时属于状态f 的概率p ( s = f i y ) ，此问题可以通 过向前一向后算法嘲解决。向前向后算法也是基于动态规划思想，通过简单的 迭代求得向前概率口( f ，f ) 与向后概率卢( f ，f ) 。首先我们先定义口( i ，f ) 与( f ，f ) ： 基于分段半马尔可夫模型的在线序列模式检测方法研究 浙江大学硕士学位论文 e m ( e x p e c t a t i o n _ m o d i 矗c a d o n ) 算法的一种。假设一个l 丑订m 的状态数为m ， b a u m w e l c h 算法按照最大似然准则，通过迭代不断调整模型参数，使之最适应 训练数据。 b a u m w j l c h 算法的迭代过程从初始的参数集口o 开始，在第f 次迭代中，把 模型的参数护从口。1 调整成口”，具体过程可以描述如下： 对于状态间转移概率如，向前一向后算法用旧的参数集口“”算出 p ( i = f ，墨。= ，l y ) 的值，则对于每对状态f 来说，从状态辞 出到状态，的伪 次数n 。为： n f = p ( 墨= t s + 。= j i y ) 则状态间转移概率a 可以通过以下式子重新估计： 茑2 最 z ， 同样，对于观测值分布概率p ( ) 。l 卫= f ) ，向前一向后算法用旧的参数集口o _ 1 算出p ( i = f l y ) 的值，则可以对每个观察值m 建立以下带权值的集合： l ；j v ( y r ，p ( = f l y ) ) ) 其中y 。的权值就是p ( i = 引y ) 。根据这个带权值的集合我们可以重新估计观察值 分布p ( s ，= 引y ) 。 可以证明，通过重估计后的模型参数占0 1 要比原来的模型参数目o 。好，也就 是可以使p ( y ) 更大。在实际的模型参数估计过程中，就是不断的重复估计过程， 直到p ( y ) 收敛，不再明显增大，此时即可得到最后的模型。 3 2 分段半马尔可夫模型( s e 舳e n t a ls e m i m a r k o vm o d e l ) 分段半马尔可夫模型是 v i x 基于分段半马尔可夫模型的在线序列模式检测方法研究 浙江大学硕士学位论文 了改进。假设一个分段半马尔可夫模型有m 个状态，它的初始状态概率矢量为 状态转移概率矩阵为a 。与m 删相似，我们假设在f = o 时刻，模型的状态总 是处于一个称作“s t a r t ”的特殊启动状态，而羁则表示从状态“s t a r t ”转 到状态f 的概率。这样，我们就可以把初始状态概率矢量冗合并进状态转移概率 矩阵a 里，从而省掉芤。 3 2 1 状态持续分布( 半马尔可夫模型) 在h m m 中，一个状态只是产生一个观察值只；而在分段半马尔可夫中，一 个状态可以产生一段观察值ky f 2 。假设一个状态序列s 有尺段，记靠为第r 段 终点的时间索引，其中l r r 。则s 的分段情况如下： 我们假设印= o ，而在第r 段的观察值可以定义为y ( q 。曰， 堡堑y 。一， 其中这些观察值是属于同一个状态，即有：，。“= = 。 我们记第r 段所有的观察值的状态为f ，则模型在状态f 的持续分布时间d ，就 是第r 段的观察值个数，所以有吐= 玑一日。在洲中，哦隐式从几何分布， 如图3 2 所示；在分段半马尔可夫中，可以显式指定吐的分布p ( 4i 易) ，其中岛 是分布的参数集。分布p ( 4i 既) 的具体形式由实际应用来决定，例如可以是如 下的泊松分布( 如图3 4 所示) ： z 已一1 p ( 4l 气) 口音，幽4 4 懈吐 ( 3 3 ) 其中参数集眈= 丑，l n j n4 ，m a ) 【吐 。 基于分段半马尔可夫模型的在线序列模式检测方法研究 浙江大学硕士学位论文 圈3 4 分段半马尔可夫模壅允许显示定义状态持续分布函数，倒如泊梧分布 在分段半马尔可夫模型中，段对应的状态间的转移是一个马尔可夫过程，按 照状态转移概率矩阵为a 进行，例如凡s 。可以描述如下： p ( = j l = f ) = a 但相对同一段内的点来说，它们的状态间转移通常不是一个马尔可夫过程( 只有 当状态持续分布p ( 4l 兄) 恰好是几何分布时，该过程才是一个马尔可夫过程) ， 这也是模型被称作半马尔可夫( s 锄i m a r k o v ) 模型的原因。 3 2 2 分段观察值分布( 分段马尔可夫模型) 在 i 垤中，模型在时刻f 的观察值只的分布只是取决于当时的状态i ，与 时间r 无关；而在分段半马尔可夫模型中，在同一段里的观察值处于同一状态， 它们的值也是相互联系的，它们的分布由只与f 共同决定。 假设在同一段里的观察值序列y ( h ，f 2 处于状态f ，则) ，( ，如 的分布可以描 述成p ( y ( ，f ：】l 嚷) ，其中已是分布的参数集，p ( y ( ，f 2 i 巳) 的具体形式由实 际问题决定。例如在时间序列模式检测领域，我们一般用线性回归方程 工( f ) = 龟r + c f 来生成模式的第f 段，加上高斯分布的噪声后，则有只= 岛抖c f + ， 其中服从均值为0 ，方差为盯2 的高斯分布，这种情况下分段观察值分布可以描 述如下( 如图3 5 所示) ： p ( y ( ，) = 名兰e x p ( 一( m 一( 印+ ( 2 辞) ( 3 4 ) b a z 砸 其中参数集口，= 岛，q ，一 。 基于分段半马尔可夫模型的在线序列模式检测方法研究 塑垩查兰堡主兰堡垒奎 护= a r g ，a ) 【雾冀耋l ! 孚j 薹2 ! f ；霸f 薹i； 嚣薹h 裂察；瓣蠢蒙强狂弱霹愆u ；饔鲥略丛螽攀巅e 型箭“缝萄j 嚣灏霆笤塾嚣黧嚣琵铬鏊隧j 薛融猫矧矧裂翮婪醯鬯节魂岔手釜黼戥谬整漕浮 蛤帮强i 期蹦塑赫酗妻照嚣! 蒸伛垂蚕例磅一薹囊，分成锈辚滗坚薹渺透i i 言一潲 舜剐甜辨甄为 复杂的波形，长度为1 8 1 ，比前面的示 例模式要长很多。示例模式一共分成6 段，如图4 1 2 所示。同样，我们也合成 四个长度为3 3 6 2 的时间序列用作模拟实时获得的时间序列，其中每个时间序列 都含有5 个与示例模式相似的模式，它们最大伸缩度f 也是2 。这四个时间序列 的区别是信噪比( s n r ) 不同，分别是没有噪声、1 8 3 7 0 8 、1 5 6 2 4 7 和1 2 9 9 4 7 。 图4 1 3 所示是四个合成的时间序列，它们按信噪比从高到底排列，其中虚线部 分是与示例模式相似的模式出现情况。实验结果如表4 8 所示。 圈4 1 0 第二套合成数据实验中的示倒序列模式示意圈( 模式分成6 段如虚线所示) 表4 8 第二套合成弦据实验嬉果 s n r 误检率 漏检率 时间( 秒) s、mss m msw mss m msw mss m m 没有噪声 16 7 1 6 9 14 1 2 1 6 1 10 2 5 0 5o o o o o o 基于分段半马尔可夫模型的在线序列模式检测方法研究 浙江大学硕士学位j垒塞 。(气)=p(siy，目。“)logp(d，=吼一日“l气；扣) =p(f，=目。，f：=甄，t=fiy，学。“)logp(4=di气)4t 鞲堕嘞，。l o g p ( 4 = d l 吃) 其中吩。塑p ( = g 。，如= 吼，= f i y ，p “) 是模型处于状态i 并持续了时 b ! 舀 间长度为d 的伪个数，可以通过向前一向后算法算出，如式子( 3 6 ) 所示。 则免的大似然估计如下： 莓= a r g m a x 臻。1 0 9 p 似= d l 气) ( 3 ，l o ) d ( 3 ) 分段观察值分布的参数巩： z ，( f ) = p ( s y 曰“) l o g p ( _ ) ( 绋+ 毋】i 乞) y sr = l = p ( = ，f = 靠，屯= 弧俨) 1 0 9 p ( y ( 】i 巳) f yh ，屯 则吼的大似然估计如下： 爵= a r g m a ) 【吩州怕】l o g p ( y ( | 巳) ( 3 1 1 ) ，( h t bj 其中n ( j 2 】堕p ( = q 。f ：= 吼，i ：= f l y ，目“) 是观测值序列) ( ，f 2 处于状 态f 的伪个数，可以通过向前一向后算法算出，如式子( 3 6 ) 所示。 3 3 修正分段半马尔可夫模型 3 3 1 模型介绍 分段半马尔可夫模型首先在语音处理等领域中得到广泛应用。“，随后g e 等人将其引入到了在线序列模式检测中来。“1 ，它以误检率低、计算量适中等特 点收到了良好的效果。但该模型是用分段观察值分布来反映该段的形状的，这对 于那些时间轴上有缩放的相似模式来说是不合适的。如图3 6 所示是两个相似模 式，但它们在对应的段的观察值分布相差很大，用分段半马尔可夫模型是检测不 基于分段半马尔可夫模型的在线序列模式检测方法研究 浙江大学硕士学位论文 出这类相似模式的。因此，围绕着研究目标，我们对现有的分段半马尔可夫模型 做了以下两方面的修正： 1 用每一段的偏移量分布来代替该段的观察值分布。 假设在同一段里的观察值序列y ( f 1 ，屯 处于状态f ，而用线性回归函数得到 的相应序列为；( ，如 。我们用y ( ，乞 与；( ，f 2 的均方根误差( r o o tm e a i l s q u a r e de 玎o r s ) 来定义该段的偏移量冠，即足可由下面公式计算： r ( 地+ ，乳，吼蜕) 丝 后爵磊 ( 3 1 2 ) 偏移量分布保证了该段的予序列能与它线性回归直线拟合得较好，同时允 许相似模式对应段的观察值相差很大，因此能检测出在时间上存在缩放的相似 模式，如图3 7 所示。同时计算偏移量分布的运算量要比计算观察值分布的运算 量小，而且偏移量分布比观察值分布要稳定，因此提高了模型的鲁棒性。 偏移量冠的分布可以描述成p ( 咒1 ) ，其中是分布的参数集，我们用下 面分布来表示p ( ri ) ： 地“徽：，盖毪 聊 参数集= ，t 丁轰) ，图3 ，8 是上述分布的一个示意图。 圈3 6 在时间上存在缩放两个相似模式，它们对应的第二段观察值相差很大 茎主坌壁兰兰苎里查蔓型塑垄垡生型堡茎堡型查垄堑壅兰壁型堕竺生皇型! ! ! 羔 图3 7 圈中两条曲线是圈3 6 中两个相似模式中的第二段。它们擐幅差值相等，即有 y = y + ，且都能与自己线性回归直线拟合得较好 参考偏移量 圈3 8 偏移量分布示意圈 2 为每一段引进该段两个端点间振幅( y 坐标) 差值分布 去掉观察值分布后，该段的形状变得没法保证，因此我们引进了每一段两个 端点间振幅差值分布，它结合偏移量分布能保证该段的形状。 假设在同一段里的观察值序列y ( ，屯】处于状态f ，则该段两个端点间振幅差 值为虬一虬，如图3 7 所示。y ：的分布可以描述成p ( 一+ 。j ) ，其中 是分布的参数集。p ( 一虬+ 。l 吼) 的具体形式应该由具体问题来决定，一般 情况下我们可以用以下的正态分布来表示： p ( 一巩+ 、i 气) ( 如，仃：) ( 3 1 4 ) 参数集吒= 心，吒) 。 至此，我们可以定义修正后的分段半马尔可夫的参数集口如下： 占丝 a ， 气 ， ， ) 其中a 是状态转移概率矩阵；眈是状态持续分布参数；是偏移量分布参 数：良是振幅差值分布参数。 基于分段半马尔可夫模型的在线序列模式检测方法研究浙江大学硕士学位论文 3 3 3 向前一向后算法 修正半马尔可夫模型的向前一向后算法是从分段半马尔可夫模型的向前一 向后算法扩展而来，不同的是( f ，f ，f ) 定义不同。我们用到的变量定义如下： 口( ，f ) 塑p ( f = g r ，r = 绋，量= f ，) ，【l f 】) ( f ，f ) 塑p ( ) ，( f ，列i f = b ，薯= f ) 善( f ，f ) c z 矿p ( f = 靠，= f ，y 1 ，胡) 妒( f ，f 。，r ) 鱼堕p ( 4 = 卜一f ) p ( 只一y f r 一= 鼋。，f = g ，i = f ) 其中1 f m ，1 f f r 。沁毋，暑= f 表示是一个段的终点，而且该段处 于状态f ，r 是该段的偏移量。 则向前一向后算法计算以上变量的过程可以描述如下： 1 初始化： 户。，卜 l ，羹磊胛” ( f ，f = r ) - 1 ，v f 2 递推过程： 妒( f ，f ，f ) = p ( 4 = f f i 气) j p ( y f z + 。i ) p ( ri 氏) 似“。，f ) = i 善( 加。) 如i 艇，f ，f ) 她f ) = 口( 记f ) ( t 力。莩l a 莩 ( 如磁如) j 3 结束 p ( y ) = 她r ) = 胞o ) 与分段半马尔可夫模型类似，根据向前一向后算法我们可以推导出了几个重 要等式，它们被用于估计模型参数的e m 算法中，它们是： 墨王坌垦兰兰堑里查堡型竺垄垡壁! ! 堕查笙型查望塑兰| 一兰塑2 苎兰生望! 垡丝苎 p ( ) ， 1 ，明) = 妊t )( 3 1 7 ) = ( f = “s 姒r 丁”，归o ) p ( f ；f ：吼，= m l ，t 】) = 岱“，f ) 肫f ) ，p ( y 【1 ，t 】) ( 3 1 8 ) p ( t ：f iy 【1 ，r 】) = 口( f ，f ：) ( f ，f ：) p ( y 【l ，丁】) ( 3 1 9 ) 。罐 p ( f ：f ：= i ，i = 洲1 ，t 】) = 如) 岛始f ， ) 触f ) ，p ( y 咿】) ( 3 2 0 ) 3 3 4 修正分段半马尔可夫模型的e m 参数估计算法 修正分段半马尔可夫模型的e m 参数估计方法与分段半马尔可夫的有同样 的思维，利用观察值序列集合 y 】来估计参数集合口，具体描述如下： e 一步骤：对于每一观察值序列y ，算出它对应所有可能的状态序列s 的 后验概率p ( s l y ，p “) 。 m 一步骤：选择新的参数集疗一，使得似然函数的值最大： 口“= 缸g i n a x p ( s i y ，口“) l o g p ( s ，y 占) 利用向前一向后算法的输出可以完成以上两个步骤。同样，为了表述方便清 晰，我们首先对m 一步骤中的似然函数按照不同的参数子集分解成四部分： p ( s i y ，俨) l o g p ( s ，y i 口) ， 5 = p ( s 旧舻) 1 。g p ( ，h ) ye 一1 + p ( s i y ，口“) l 。g p ( 盔2 巩啊一- i 气；扛) y s。一1 + p ( s l y ，俨) l o g p ( 冀l 气) vs ，一j + p ( s l y ，) l o g p ( y 。一+ - l ) d e ，。( a ) + e 。( 仍，1 ) + 。( 氓 ) + ，“氏 ) 则我们可以对不同的参数子集进行单独估计。 加 基于分段半马尔可夫模型的在线序列模式检测方法研究 浙江大学硕士学位论文 ( 1 ) 状态转移概翠矩阵a ： 。( a ) = p ( s i y ，p “) 1 0 9 p ( ，is ) = p ( = 如= 绋，气= f ，屯= m ，矿“) l o g 堕l o g 岛 j j 其中嘞丝p ( = q 。，f 2 = 田，_ = f ，= j l y ，目“) ，是从状态辟 出到状态 ，的伪次数，可以通过向前一向后算法算出，如式子( 3 2 0 ) 所示。 则a ，的最大似然估计如下： 否2 彘 ( 2 ) 状态持续分布的参数免： ( 3 2 1 ) f d ( 气 ) = p ( s l y ，酽“) l o g p ( 4 = 甄一g 。i ；江) = p ( = 乞= 屯蚓y ，目“) 1 0 9 p ( 4 = d l 气) “，：x 岛 鱼芝吩。l o g p ( 4 = d i 岛) 其中n 埘丝p ( = q 。，f 2 = q r ，屯= f i y ，口“) 是模型处于状态f 并持续了时 7 t ! 知 间长度为d 的伪个数，可以通过向前一向后算法算出，如式子( 3 1 8 ) 所示。 则吃的大似然估计如下： 爵= a r g 。蚴啊，加g 啪= d i ) ( 3 2 2 ) ( 3 ) 偏移量分布的参数气： z ，( f ) = p ( s l y ，口“) 1 0 9 p ( 墨i 银) = p n = q 。，岛= b ，屯= f iy 口“) l o g p ( 墨i 气) 则的大似然估计如下： 瓦= 蝣。m a ) 【吩鹏剐1 0 9 p ( 日j & ) ( 3 2 3 ) y ( ，f 2 】 4 1 基于分段半马尔可夫模型的在线序列模式检测方法研究浙江大学硕士学位论文 其中啊州桃】塑p ( = q 。，如= 甄，屯= f i y ，) 是观测值序列) ，( ，f 2 】处于状 态f 的伪个数，可以通过向前一向后算法算出，如式子( 3 1 8 ) 所示。 ( 4 ) 振幅差值分布参数氏： r l ，( 气 ) = p ( s l y ，护。“) i o g p ( y 。一y + ，i 氏) = p “= q 。，f 2 = 吼，屯= f l y ，) p ( 一) ，。+ 。i 氏) y h ，屯 则氏的大似然估计如下： 爵= a r g m a 】【吩眺州p ( 一) ，。l 如) ( 3 2 4 ) y 【f 1 ，乜j 其中吩州怕j 塑p ( = g ，。，f ：= 甄，s 。= f i y ，8 “) 是观测值序列) ，( f 1 ，f 2 处于状 态f 的伪个数，可以通过向前一向后算法算出，如式子( 3 1 8 ) 所示。 基于分段半马尔可夫模型的在线序列模式检测方法研究 浙江大学硕士学位论文 第四章基于修正分段半马尔可夫模型的在线序列模 式检测 分段半马尔可夫模型以其有效的推理和学习算法，和灵活的建模能力，首先 在语音领域得到广泛应用阻“。接着g e ，s m y 吐i 等人将它引进到时间序列分析领 域，在中文分词”3 、子序列匹配”3 、在线序列模式检测。0 2 ”等等方面收到良好效 果。在本章中，基于g e 等人的工作基础上，我们把修正分段半马尔可夫模型应 用到在线序列模式检测中，实验证明，它能快速在线检测出在时间上( x 轴) 存 在任意缩放( 在给定最大伸缩度f 内) 的相似模式。 4 1 示例模式建模 4 1 1 示例模式线性化 现实生活中的时间序列数据一般都以波形呈现的( 如图4 1 所示) ，为了建 立修正分段半马尔可夫模型，我们必须先将示例模式线性化表示。假设一个示例 序列模式为y = 咒蜥，我们的目的是将它分成k 段： y 1 ，+ 1 ，) ，4 。+ 1 _ ”蜥 其中用连接点( 氆。y 。) 与( 吼，y 。) 的线段来近似表示原来序列的第f 段) ，( 鼋f - 。，强 。 我们使用线性回归函数( 也可以使用其他回归函数，如多项式、指数函数等 等) 来对示例序列模式进行分段。目前分段线性化的方法主要包括以下三种”： ( a ) 将序列y 分为足段，使各段的偏移量之和最小。 ( b ) 对序列y 进行分段后，每段的最大偏移量不超过用户定义的阈值。 ( c ) 对序列y 进行分段后，各段的最大偏移量之和不超过用户定义的阈值。 由于在现实生活中，序列模式对应的每段都有特定的意义，应该由人们指定 分段数，加上方法( b ) 和( c ) 的阈值难以确定，因此我们选用方法( a ) 对序列模式进 行分段线性化。在描述分段算法之前，我们先定义各段的偏移量之和如下： 4 3 基于分段半马尔可夫模型的在线序列模式检测方法研究 浙江大学硕士学位论文 表4 1 将时间序列线性化算法 输入t 序列模式：咒蜥 分段数： 置 初始化：，( 足，1 ) - o ，其中= 1 ，2 ，置 1 f o rf = 2 ，3 ，r 2 ，( 七，) - o 口其中七= 1 ，2 ，茁 3 f 0 rf = 1 ，2 ，卜- 1 4 计算子序列x 咒在线性回归函数里对应的序列嚣嚣 5 p ”= ( 咒一) 2 r s “s f 6 f o r 女= 1 ，2 ，置 7 e r r o r = ，( 一1 ，f ) + p r r 8 ，( ，