（概率论与数理统计专业论文）基于隐马尔科夫模型的时间序列聚类.pdf

摘要 时间序列是按时间的先后顺序排列而成的数列，广泛存在于社会生产的各个领域，形成规模 庞大的时间序列数据库，真实地记录了应用系统在各个时刻的重要信息时间序列分析已成为机 器学习、数据挖掘、模式识别、统计学等众多领域的研究热点之一对于时间序列的聚类是时间 序列分析的重要内容，在众多时间序列聚类方法中，近几年发展起来的基于隐马尔科夫( h m m ) 模型的方法尤其有效但这种方法要求序列等长、结构已知，本文对此提出了自己的解决方法 传统的聚类方法，通常先将序列分割成等长的子序列集合，然后对各子序列进行聚类，这种 方法会导致信息丢失和模型过度拟合问题本文采用k 1 i l e a r l s 框架，选用联合似然函数作为准则 函数，首先利用动态时间弯曲( d t w ) 对数据集进行初始分类，然后进行迭代修正每次迭代中， 先用每类内的样本训练h m m 模型，然后对每个样本计算其出现在各模型的概率，按照概率最大 原则将其分配到对应的类内 对于模型结构未知情形，按照混合最小描述长度准则，提出一种基于h m m 模型的嵌套循环 算法，该算法能快速找出模型的隐状态数，是属于数据驱动的一种方法数值试验表明了该方法 的有效性 关键词：隐马尔科夫模型，聚类分析，时间序列，混合最小描述长度 a b s t r a c t t i m es e r i e si sa ni m p o r t a n tc l a s so fs e q u e n c eo fn u m b e r s i tc a l lb ee a s i l yo b t a i n e df r o ma l m o s t e v e r yf i e l d so fs o c i e t y t h e r ea r em a n ye n o r m o u st i m e - s e r i e sd a t a b a s e ，w h i c hr e c o r d e dt h ei m p o r t a n t i n f o r m a t i o na te v e r yt i m e f o rt h ef u l l yu s eo ft h e s et i m es e r i e sd a t aa n dt r y i n gt of i n dt h ek n o w l e d g e f r o mt h el a r g ed a t a b a s e s 。c l u s t e rb e c o m eaf o c u st h e s ed a y s i ne x i s t i n gh m m c l u s t e r i n gm e t h o d s ，t i m e - s e r i e si sa s s u m e de q u a ll e n g t ha n dm o d e ls i z ei sg i v e n s o ，t h i st h e s i sd e v o t e dt or e s o l v i n gt h i st w o p r o b l e m a i m e da ts o m es h o r t a g e si nt h ee x i s t i n gc l u s t e r i n gt i m es e r i e sm e t h o d sb a s e do nh i d d e nm a r k o v m o d e l ，s u c ha sl o n g e rs e q u e n c e sa n de q u a ll e n g t h ，ah i d d e nm a r k o vm o d e l - b a s e dk - m e a n st i m es e r i e s c l u s t e r i n ga l g o r i t h mi sp r o p o s e d ，w h o s eo b j e c t i v ef u n c t i o ni st h ej o i n tl i k e l i h o o df u n c t i o n a tf i r s t ，a n i n i t i a lp a r t i t i o ni so b t a i n e db yu n s u p e r v i s e dc l u s t e r i n go ft h et i m es e r i e su s i n gd y n a m i ct i m ew a r p i n g ( d t 、聊，t h e n 鲴m m sa r eb u i l tf r o mi t , a n dt h e s ei n i t i a lc l u s t e r ss e r v e 越i n p u tt oap r o c e s st h a tt r a i n so n e h m mo ne a c hc l u s t e ra n di t e r a t i v e l ym o v e st i m es e r i e sb e t w e e nc l u s t e r sb a s e do nt h e i rl i k e l i h o o d sg i v e n t h ev a r i o u sh m m s am o d e lb a s e d0 1 1n e s t e dl o o p sh 删a l g o r i t h mi sp r o p o s e df o rt h em o d e ls t r u c t u r eu n k n o w nc i r - c u m s t a n c e s ，w h i c ha c c o r d sw i t ht h em i x t u r em i n i m u md e s e r i p t i o n i tn o to n l yc a l lf i n do u tt h em o d e ls i z e q u i c k l y , a n db ea no b j e c t i v e d a t a d r i v e nm e t h o d t h es i m u l a t i o ne x p e r i m e n ts h o w st h a tt h ea l g o r i t h mi s e f f e c t i v e k e y w o r d s ：h i d d e nm a r k o vm o d e l ，c l u s t e r i n g ，t i m es e r i e s ，m i x t u r em i n i m u md e s c r i p t i o nl e n g t h 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得宁夏大学或其它教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：桫 时f 日- - j ：知，年彳月 易日 关于学位论文使用授权的说明 本人完全了解宁夏大学有关保留、使用学位论文的规定，即：学校有权保留送 交论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复 制手段保存、汇编学位论文。同意宁夏大学可以用不同方式在不同媒体上发表、传 播学位论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 研究生签名： 导师签名： 时间：知，年，月2 ，日 时间：扣o 年6 月够e l ，】3 b = ) 一 强立丛垃 辎纽 宁夏人学硕l ：学位论文 第一章绪论 1 1 研究目的及意义 第一章绪论 从统计意义上讲，时间序列就是将某一指标在不同时间上的不同数值，按照时间的先后顺 序排列而成的数列1 1 1 这儿的“顺序”既可以是时间顺序，也可以是具有不同意义的物理量， 如代表温度、速度或其他单调递增地取值的物理量时间序列分析起源于预测，自从1 9 7 0 年 g e p b o x 和g m j e n k i n s 的( t i m es e r i e sa n a l y s i s f o r e c a s t i n ga n dc o n t r 0 1 ) 一书问世以来，时间 序列分析方法的研究和应用发展迅速，其应用的范围日益扩大，涉及天文、地理、生物、物理、 化学等自然科学领域，图像识别、语音通讯、声纳技术、遥感技术、核j r 程、环境：_ l ：程、医学工 程、海洋工程、冶金工程、机械：【程等工程技术领域，市场经济、金融分析、生产管理、人口统 计等社会经济领域，并取得了一定的成果从时序应用以及其研究情况来看，时序分析的工程应 用大致可分为六个方面【l 】：( 1 ) 系统辨识；( 2 ) 系统分析；( 3 ) 谱分析；( 4 ) 模式识别( 特别是用 于工况监测、故障诊断、医疗诊断等方面的) ：( 5 ) 模态参数估计；( 6 ) 预测与控制传统的时间 序列分析方法是从系统论的观点出发，主要揭示信号本身的结构和规律及其与相应系统之间的关 系，采用的主要方法包括参数建模( 如a r 建模和a r m a 建模) 、统计量分析( 如一阶统计量 和高阶统计量) 、变换分析( 如离散傅立叶变换和小波变换) 等 1 - a 其主要思路是根据系统的输 入和输出及其相互关系，完成对待分析系统的参数建模同时，时间序列作为数据库中的一种数 据形式，它广泛存在于各种大型的商业、医学、工程、和社会科学等数据库中，形成规模庞大 的大型时间序列数据库这些巨量时间序列数据真实地记录了应用系统在各个时刻的所有重要信 息随着数据库知识发现( k d d ，k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 1 4 l 和模式识别等计算机技术的发 展，出现了基于大量甚至海量数据库的数据挖掘技术，其研究目的是从大量时间序列数据中发现 未知的重要模式和知识，并据此做出具有知识驱动的决策在时间序列数据挖掘中，聚类是其中 一个非常重要的领域吼 现实生活中时间序列广泛存在，比如金融证券市场中每天的股票价格：商业零售行业中，某 项商品的周期销售额；气象预报研究中，某一地区的气温与气压读数；以及在生物医学中，某一 症状病人在每个时刻的心跳变化等等比较不同的时间序列在某段时间内运动变化是否相似，从 而对其进行聚类分析在许多应用领域中具有重要的意义，下面就是一些典型应用的例子 在宏观经济分析中，通常可以根据国民收入、就业率、通货膨胀程度等经济指标的时间序列 对国家或地区进行分类，发现典型国家或地区的经济发展特点 在证券市场上，找出在过去两星期里与微软公司的股票价格序列的变化模式相似的公司，从 中可以分析产生这种变化模式的原因 在金融领域，跟踪信用卡顾客的使用情况，对信用卡顾客进行分类，发现信用卡使用情况异 常顾客，能够及时报告，预防信用欺诈 在交通管理中，需要将具有相似交通流变化趋势的时段进行聚类，从而实现对具有不同流量 特性的交通检测点早晚时段进行合理分组，当把每组内的时段形成各个相对独立的特征区域时， 可将它作为进一步进行交通规划及控制优化的依据之，如应用于岔道口的信号配时 宁夏人学硕i ：学位论文第一帝绪论 1 2 聚类分析 聚类分析是一个重要的人类行为，早在孩提时代，一个人就通过不断的改进下意识中的聚类 模式来学会如何区分备类动物或植物聚类是一种重要的机器学习方法，是指对数据集在某种测 量下的非监督的划分方法【3 0 1 与监督学习方法不同，聚类不需要人工干预训练过程，有时这种 干预过程是非常枯燥和费时的( 例如在语音处理中的原始音频数据的切分和标记过程) 同时， 聚类这种计算机自主地对样本集进行归纳、总结的功能是人工智能的一个重要表现聚类的结果 可以体现样本的本质结构，是对事物内在特性的一种理解它在模式识别、数据分析、图象处理 和市场研究等领域都有重要的应用 聚类分析的目的是把整个目标数据分成多个不同的类，使得每个类中的数据尽可能相似，而 不同类中的数据具有明显的差别常见的聚类算法主要包括划分方法和层次方法【37 1 划分法只创建数据集的一个单层的划分如果k 是希望的簇的数目，那么划分法一次找到所 有的k 个簇划分法包括k m e a l l s 方法、k - m e d o i d s 方法以及概率方法等k - m e a n s 算法先找到k 个簇的中心点，然后将每个点分配到离它最近的中心点其基本算法如下：先随机地选取k 个对 象作为簇的中心，将剩余的对象分配给离它最近的中心，然后再计算出新的簇中心重复以上过 程，直到k 个簇的中心点都不再发生变化，这种算法试图找到数据的k 个划分使得一个准则函 数得到优化但该算法缺点在于对数据中的孤立点非常敏感，为此人们提出利用最接近于聚类中 心的数据点作为簇的中心点以增强算法的鲁棒性，即k - m e d o i d s 算法 分层法产生一个树状的分层数据簇可以进一步划分为凝聚法( a g g l o m e r a t i v e ) 和分解法 ( d i v i s i o n ) 凝聚法从单点簇开始，不断地合并两个或多个最合适的簇而分解法先将所有的数据点 看作一个大簇，然后不断地对最合适的簇进行分裂这个过程一直进行到一个停止准则( 通常为 聚类的数量) 满足为止在分层聚类法中，簇的合并和分解要按照一定的相似性( 或相异性) 度量 原则 1 3 时间序列聚类的研究现状 时间序列是按一定顺序排列而成的数据，其基本特征在于观测值之间存在着一定的依存关 系，这导致时间序列分析的研究方法与传统的数理统计不同，现有的序列分析方法从易到难可以 分为以下四层1 3 0 】： 第一种是离散分析法这种方法只考虑序列中的一项，在某些应用中还是能够得到整个序列 的含义例如人体的三维建模中，一类流行的方法就是通过静态图像进行三维重构；手势识别 中，也可以利用静态手势的图像进行这类方法中假设观测物体的特征变化在时间上没有规律， 或者是把这些时间上的变化规律忽略不加考虑 第二种是点集分析法这种方法是只看到了序列中的向量值，而忽略它们的时序信息，把序 列看成是一个没有顺序关系的特征点集合最典型的例子就是离线形式的手写体识别在这个应用 中，系统看到的是写完以后的字符的图像，即一个点集，而不知道这个点集产生的顺序 第三种是均匀采样分析法，在这种方法中，序列的顺序性被考虑了进来但是为了便于分 析，序列的长度都是一样的假设序列长度都是t ，而每一项啦都属于一个n 维实数空间冗竹， 则每个序列都能用个n t 维的向量统一表示这样在建模、识别时就可以直接采用各种距离 2 宁夏人学硕i j 学位论文第一幸绪论 函数来度量序列间的相似度了例如，在手写体汉字识别中，就可以采朋按时间或空间均匀采样 的方法把不同的样本用相同维数的向量表示 最后一类方法，时域模型法，需要对时间轴上的扭曲变化进行建模这种方法中，对序列长 度没有了限制，可以说是目前处理时间序列最完善的方法，其典型代表是动态时间弯曲( d y n a m i c t i m ew a r p i n g ，简称d t w ) 它可以同时得到两个距离，一个是时间上的扭曲程度，另一个是空间 上的轨迹相似度但是它只适合于两个时间序列的时序变化不大的场合，如语音、手写体、曲线 等而且，d t w 在计算距离时没有考虑样本点的分布特征，往往会出现错误的结果例如，在序 列的某一段样本点比较集中，而另一段却很分散，利用d t w 计算距离时，分散的那段距离就占 了整个样本距离中很大的一部分，以至其它部分的差异却被掩盖了f 8 】 近年来对时间序列的聚类研究更多地使用基于模型的聚类分析【5 】，而h m m ( h i d d e nm a r k o v m o d e l ，隐马尔可夫模型) 由于具有以下两个特点而特别吸引研究者 4 1 】：( 1 ) 它是一个有坚实数 学基础的概率模型，而且其相关问题已有解决的有效算法；( 2 ) 模型中的隐状态能合理解释动态 过程中的潜在“因素” 一种基于h m m 的聚类方法是直接通过h m m 衡量两个样本之间的相似度1 1 3 1 1 2 3 j 1 4 2 2 3 1 一 文中比较了三种已有的用h m m 输出概率进一步计算样本间相似度的方法【1 3 】中采用了另外一 种描述方法，直接用样本在其它样本的相似度组成一个特征向量，来表示这个样本，然后把这些 向量进行聚类【4 2 】则针对常用的衡量两h m m 模型相似度的k u l l b a c kl e i b l e r ( k l ) 距离不满足距 离的不等式性质，在基于h m m 的不变累计分布函数上，提出了一种h s d 距离，该距离不但满 足距离定义的性质，而且试验表明其相对于k l 距离，在聚类时间序列方面有更好的准确度以 上这一类方法都需要对每一个样本训练一个h m m 模型，这就要求被处理的序列必须很长，例如 d n a 序列，e e g ( 脑电波) 序列，可以通过一个样本直接训练得到h m m 模型，否则得到的模 型会过度拟合到样本，与其它样本的相似度较小 另一种基于h m m 的聚类方法采用的是k - m e a n 的框架 1 3 4 3 】聚类分为初始化和迭代两个阶 段初始化时把样本序列随机地或按某种原则进行初始划分在迭代阶段对分类结果不断修正每 次迭代先用每类内的样本训练h m m 模型，然后对每个样本，计算它在各个模型内的出现概率， 把它放到概率最大的那个模型对应的类内这种方法的缺点是h m m 模型没有对类内样本相似度 要高的要求，可能出现两类样本在一个h m m 内概率很高的情况 文献【1 2 】采取分层聚类方法，针对序列长度相同但模型隐状态未知的情形，提出了一种 m a t r y o x h k a 算法，该算法利用b i c 准则作为其聚类的准则函数【4 1 】则对其要求序列相等以及稳 健性较差做了改进，将d t w 与m n 嗄相结合，采用了分裂的聚类方式本文第四章受此启发， 试图利用m m d l 准则处理时间序列的聚类以及隐状态数的确定 1 4 本文所做的工作与论文组织结构 本文对时间序列聚类的历史背景和意义做了详尽的了解，在总结过去聚类时间序列算法中要 求时间序列等长以及隐马尔科夫模型中的隐状态数已知上，提出了改进的方法 本文主要完成了以下几个方面的工作： ( 1 ) 通过阅读大量文献，了解了时间序列聚类的发展历程，掌握了隐马尔科夫模型的基本 原理、基本算法以及算法实现中问题 3 宁夏人学坝f j 学位论义第章绪论 ( 2 ) 以往聚类时间序列的算法中，要求将原始序列分割成等长度的子序列集合，这样会导致 信息的流失本文则提出基于k 均值的时间序列算法，它先用动态时间弯曲将数据集进行初始 分类，然后在初始划分基础上利用i - i m m 聚类，该算法对时间序列的长度没任何限制 ( 3 ) 针对过去利用h m m 模型聚类时间序列要求模型结构已知，我们利用混合展小描述k 度 ( m m d l ) 准则来寻找隐状态数，并将其融入到聚类中，提出了一种嵌套循环算法 本文分为5 章第一章为绪论，首先介绍了时间序列的含义以及实际应用价值，然后对聚类 的内容以及时间序列聚类发展以及研究现状做了阐述，最后介绍了本文的主要工作和成果在第 二章，我们对h m m 模型的概念、它的基本问题( 评价，解码，学习) 以及算法实现中的问题做 了详细介绍第三章为基于k - 均值的时间序列聚类，本章我们首先比较了点聚类方法和序列序 列方法的不同，然后介绍了动态时间弯曲距离，并将它与h m m 模型结合，提出了一种针对不 同长度的序列聚类的k 均值算法第四章为本文的重点，主要要解决在模型结构不确定的情况 一f ，如何进行时间序列聚类为此，我们引入了混合最小描述长度( m i x t u r em i m m u md e s c r i p t i o n l e n g t h ，简称m m d l ) ，并将它应用于隐状态数寻找和模型聚类，提出了种基于h m m 的嵌套循 环算法，试验表明，该算法能较好解决该问题第五章为全文总结与展望 4 宁夏人学硕 ：学位论文第- 二章隐马尔科人模型( h m m ) 第二章 隐马尔科夫模型( h m m ) 本章我们首先从一个经典的例子引出隐马尔科夫模型的基本定义，然后给出组成隐马尔科大 模型理论的三大基本问题，并给出相应的算法，包括概率计算的前向、后向算法，解码( 状态确 定) 的v i t e r b i 算法和参数估计的b a u m w e l c h 算法 2 1h m m 模型的概念 由于h m m 是在马尔科夫链的基础上发展而来的，为了更好的理解h m m ，我们首先介绍马 尔科夫链的基本概念 2 1 1 马尔科夫链 若有一随机过程 x ( ) ，t t ) ( 这里t 表示随机过程的长度) ，在时刻t 的状态是五，而在将 来某时刻t + l 的状态x t + 1 仅仅与现在的状态五有关，而与过去时刻的状态咒一1 ，x t 一2 ， 无关，则称 x ( t ) ，t t ) 为马尔科夫过程马尔科夫链是状态和时间都是离散的马尔科夫过程， 即 p ( 五+ 1 = q t + ll 墨= q t ，噩一1 = 吼一1 ，x 1 = q 1 ) = p ( x t + l = q t + li 五= g t ) ，( 2 1 ) 其中，q l ，纯，q m ( 0 1 ，0 2 ，) 是状态的取值，并且称 ( ，t + 1 ) = p ( q t + l = 如ig t = o i ) ，1 i ，j i n ( 2 2 ) 为状态转移概率，这里表示状态可以取值的数目，当p i j ( t ，t + 1 ) 与t 无关时，称这个m a r k o v 链为齐次m a r k o v 链 若将状态转移概率p i a t ，t + 1 ) 记为a i j ，所有状态转移概率a i j ，1 i ，歹n 可以构成一个状 态转移矩阵，即 且有 l a l l a ：l ： l 。 fa n l 。升 g n n 0 a q 1 ， 叼= 1 i , j = l 5 ( 2 3 ) ( 2 4 ) 宁夏人学坝i ：学位论文 第- 二章隐马尔科人模型( h m m ) 显然，a 矩阵表示的是已知前一状态时，后一状态取值的方向，但它不能确定初始分布，即 由a 求不出q x = 巩的概率，这样，完全描述马尔科夫链，除矩阵a 之外，还必须引进初始概率 矢量7 r = ( 7 r l ，砘，7 r ) ，其中 显然有 1 i = p ( q 1 = 巩) ，1 i n 0 f f i 1 7 1 i = 1 i = 1 此时，由7 r 和a 共同描述了一个完整的马尔科夫链 2 1 2h m m 模型的概念 ( 2 6 ) ( 2 7 ) h m是在m a r k o v 链的基础之上发展起来的由于实际问题比m a r k o v 链模型所描述的更为 复杂，观察到的事件并不是与状态一一对应，而是通过一组概率分布相联系，这样的模型就称为 隐m a r k o v 模型它是一个双重随机过程，其中之一是马尔科夫链，这是基本随机过程，它描述 状态的转移另一个随机过程描述状态和观测值之间的统计对应关系为了进一步说明h m m ，现 引入一个著名的说明h m m 概念的例子一球和缸试验 设有个缸，每个缸中装有很多彩色的球，球的颜色由一组概率分布描述，试验是这样进 行的，根据某个初始概率分布，随机地选择个缸中的一个，例如第i 个缸，再根据这个缸中 彩色球的颜色的概率分布，随机地选择一个球，记下球的颜色，记为d 1 ，再把球放同缸中，又根 据描述缸的转移的概率分布，随机选择下一个缸，例如第歹个缸，再根据这个缸中的彩色球颜色 的概率分布，随机地选择一个球，记下球的颜色，记为d 2 ，这样一直进行下去，就得到一个描述 球的颜色的序列o l ，0 2 ，由于这是观测到的事件，因而称之为观测值序列但缸之间的转移以 及每次选取的球的颜色并不是与缸一一对应，而是由该缸中彩球颜色概率分布随机决定的，而每 次选取那个缸则由一组转移概率所决定 这样的模型实际上是一种多状态自动机的马氏链，它认为：任一时刻系统的状态只与前一 时刻的状态相关；模型的输出，也就是所谓的观察值( o b s e r v a t i o n ) ，由当前状态决定的某概率分 布随机产生事实上，人们只能“看到”观察值，而看不到模型内在的状态变化，也不能给出任 一时刻所处的状态，人们将这样的状态称为是“隐含”的，因此，这类模型称为隐马尔可大模 型( h i d d e nm a r k o vm o d e l ) 它可从逻辑上分为两层结构一隐含状态层( h i d d e n l a y e r ) 和观察层 ( o b s e r v a t i o n l a y e r ) ，马氏链存在丁隐含层中，而观察层是隐含层的输出 隐马尔可大模型的隐含层是一个基于有限状态自动机的马氏链，其中的有限状态自动机主要 包括下列主要元素： 1 拓扑结构，拓扑结构描述了有限状态自动机的结构，主要包括左一右型、全连接型和其 它一些类型图2 1 显示了两种4 状态隐马尔可夫模型的拓扑结构，其中可能的状态转移在图中 用箭头标出拓扑结构主要是用来模拟和描述随机信号的发生机制 6 宁夏人学顾i j 学位论文第二帝隐马尔科人模型( h m m ) 图2 1 全连通型 2 状态集，即有限状态自动机里状态的集合如果状态数量是n ，记n 个状态为p 1 ，踟， t 时刻m a r k o v 链所处状态为吼，其中口t ( 0 1 ，o n ) 隐含状态的序列口t 是一种齐次马氏链，该马氏链具有如下要素： 3 初始分布，丌= ( 7 r l ，丌 r ) ，其中孔= p ( q l = o i ) ，1 i n 4 状态转移概率矩阵，a = ( a i j ) n x ，其中a l j = p ( q t + 1 = 岛l q t = o i ) ，1 墨i ，歹n 隐马尔可夫模型的观察层具有如下要素： 5 字母表( 离散观察值) ，如果观察值取值可能有m 个，则字母表可表示为，t 时 刻观测到的观测值为0 t ，则0 t ( k ，) 一些复杂模型可能包括多个字母表 6 状态输出概率，b = ( b j k ) n m ，其中b j k = p ( o t = v k i 口t = o j ) ，l j l 七m 对于连续观察值，最常用的是混合高斯概率分布，可表示为 b ( d t ) = c j k n ( o t ，心知，j 知) ， 1 j ， 七= 1 其中仍是观察值，( 仇，纷知，马詹) 是一个均值为心七、方差为j 知的高斯概率密度函数k 是组 成( d t ) 的混合概率分布的个数，勺知状态j 的第m 个混合高斯的权重，且是 这样，一个h m m 就可记为a = ( n ，m7 r ，a ，b ) 从h m m 模型的定义可以看出，h m m 实际上是分为两个部分，一是m a r k o v 链，利用一组 与概率分布相联系的状态转移的统计对应关系，来描述每个短时平稳段是如何转到下一短时平稳 段，它由7 r ，a 描述，输出为状态序列二是一个随机过程，描述状态与观测值之间的统计模型， 它解决了用短时模型描述平稳段的信号问题，由b 描述，输出为观测值序列，可由下图表示： 7 ，工 l i 七 勺 k 宁夏人学颀i ：学位论义第_ 二章隐马尔科人模型( h m m ) i m 幽v 链c 丌 q l ，q 2 ，归 瞄蜘甘碑，mp 1 ，0 2 ，d t 状态序列 腿形l u 任d j 观察值序列 图2 2h i v i m 组成示意图 经典隐马尔可夫模型将( 7 r ，a ，b ) 视作待定参数，它们需要通过对样本进学习( 训练) 来确 定，而其它参数在训练之前预先定义因此隐马尔可模型也经常被表示为a = ( 7 r ，a ，b ) 训练也 可以看作是一种优化问题，最终得的a + 是满足某种优化标准的最优模型，如著名的b a u m w e l c h 训练算法以最大似然( m a x i m u ml i k e l i h o o d ，m l ) 作为优化标准，即： 2 2h m m 中的基本问题 入+ = a r g m a x p ( oi 入) 在利用h m m 进行研究工作时，由于我们只能得到一组观测值，一个首要的问题就是如何利 用这组观测值去估计h m m 中的参数，其次，在得到h m m 的参数值后，我们如何去计算产生这 组观测值的概率，以及它是由怎样的状态序列产生 2 2 1评价问题 则 给定模型参数a = ( 7 r ，a ，b ) 及观测序列0 = ( 0 1 ，0 2 ，) 的状态序列s = ( q l ，q 2 ，铷) ， p ( o ，s = p ( 0 1 只a ) p ( s i a ) 丌n ， n ( 2 8 ) = 6 ( 劬，o j ) 7 1 1 y ia t 训 ”“7 j = lj = 2 于是 p ( d l 入) = e p ( o ，s l a ) ：蔓毗1 ，d 加( 口1 ，q 2 ) 6 ( 蚴) 似川6 ( 螂n ) q 9 上式是在整个状态空间上计算，导致计算量非常惊人，算法的复杂度为o ( 2 t n n ) 事实上，上 述算法中有许多重复计算，可以采用递归的方式米简化该问题的求解 ( 1 ) 前向算法 定义前向变量 a t ( i ) = p ( o l ，0 2 ，o t ，q t = 巩) ，15t t 8 宁夏人学硕i j 学位论文 第一二章隐- w j ； ；4 人模型 h m m ) 则 于是 o t t + l ( 歹) = p ( o x ，0 2 ，o t + l ，q t + x2 算法描述如下： a 初始化 b 递归 c 终结 那么 如) p ( d 1 ，0 2 ，o t + l ，g t = o i , q t + l = 乃) p ( q t + 1 = 易，o t + li0 1 , 0 2 ，m ，g t = 吼) p ( 。l ，0 2 ， p ( q t + l = 易，o t + li 吼= o i ) a t ( i ) p ( o t + 1iq t + a = o j , q t = 巩) p ( 口t + 1 = 如i 口t = o i ) a t ( i ) p ( o t + xiq t + a = o j ) p ( q t + a = 岛i 口t = a t ( t ) b ( j ，砚+ 1 ) a i j a t ( i ) ， 1 t z l ，1 歹 ( 2 ) 后向算法 定义后向变量 0 p ( o x ，0 2 ，o n ) = p ( q n = t ，d 1 ，d 2 ，) q n ( i ) m ( i ) = 丌i b ( i ，0 1 ) ，1 i ，d t ，吼= o i ) a t + l ( j ) = b ( j ，o t + 1 ) a t ( i ) a i j ，1 t t 一1 ，1 js p ( o ) = 口。( i ) i 反( z ) = 尸( 砚+ 1 ，o r + 2 ，0 nlq t = i ) 尻( i ) = p ( o t + a ，o r + 2 ，d niq t = i ) p ( q t + x2 歹，o t + l ，o t + 2 ，d niq t = i ) p ( o t + a ，d 。jo t + l ，q t = i ，g t + 1 = j ) p ( o t + a ，啦+ l = j ig t = i ) p ( d t + 2 ，0 t lig t + 1 = j ) p ( o t + ll 口t = i ，口t + 1 = j ) p ( q t + x = 歹iq t = i ) 风+ 1 ( 歹) 6 ( j ，o - ：+ 1 ) a i j 9 ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) j， 宁夏人学硕f ：学位论文第二章隐马尔科人模型( h m m ) 故 p ( o l 恕，o n ) = p ( q l = i ，。1 ，0 2 ，) = p ( d l ，0 2 ，o nj 口l = i ) p ( 9 1 = i ) ( 2 1 3 ) i = 卢，( i ) i 算法如下： a ：初始化 风( i ) = 1 ，1 i b ：递归 风( 1 ) = f i t - l - 1 ( 3 ) b j ( o t + 1 ) a i j ，t = t 一1 ，1 ，1 is n j c ：终结p ( o a ，o u ，0 n ) = 夙( i ) i 这两个算法的算法复杂度都是2 t ，而且还是一种格型结构，它们大大减少了计算量，其结 构示意图如图2 3 p 1 如 2 2 - 2 解码问题 t + 1 啦+ 1 0 ) t 展( i ) 图2 3 前向一后向算法示意图 t + 1 尻+ 1 0 ) 给定一个模型入= ( 7 r ，a ，b ) 以及一组观察值序列0 = ( 0 l ，口2 ，) ，由此观察序列最可能 由怎样的状态序列q = ( 口l ，口2 ，) 产生，这里若最可能用最大概率来衡量，则该问题可以通过 v i t e r b i 算法来解决 v i t e r b i 算法的核心是下述递推关系：如果已经确定了对给定部分观察序列( d l ，d 2 ，d ) 的最优状态序列为( q 1 ，口2 ，口t ) ，如何找到当部分观察序列增加l 时的最优状态序列 ( 口1 ，口2 ，q t + 1 ) 为此，定义辅助变量： 6 t ( i ) = m a x p ( q l ，口2 ，g t ，d l ，d 2 ，o t ) 叮l ，口2 ，口t l 】0 1 ， ( m 阶 以 p 宁夏入学顾 ：学位论义第_ 二章隐马尔科人模型( h m m ) 则 6 t ( i ) = m a xp ( 吼，匏，吼，d l ，0 2 ，口t ) 口1 ，i 犯，g t = 。m a x p ( q t + x 。歹，o t + liq l ，9 2 ，q t ，0 1 ，0 2 ，o t ) p ( q l ，q 2 ，q t ，0 1 ，0 2 ，o t ) 口l ，叮2 ，q i =m a x p ( q t + l = j ，吼+ 1i 吼) 尸( 1 ，q 2 ，q t ，o l ，0 2 ，o t ) g l ，9 2 ，口t = m a x a i j b j ( o t + 1 ) m a x p ( 1 ，q 2 ，吼，d l ，d 2 ，o t ) g tq l ，9 2 。，q t 一1 = b ( o t + 1 ) m 。a xa q 6 ( i ) ( 2 1 4 ) 于是最优路径只需在递推的每一步把对应每个魂( i ) 的获胜状态记录一f 来，最后回推相应的状态序 列 算法描述如下： a ：初始化 6 1 ( i ) = 兀b i ( 0 1 ) ，1 i n ，帆( i ) = 0 ，1 i n b ：递归 魂( ) 21 m 气饩a x “ i t l ( i ) a i j b j ( o t + 1 ) ，2 t n ，1 j 妒t 0 ) = a r 9 1 m ，a x v 文一1 ( i ) o 巧】， 2 tsn ，1s j c ：终结p = m 。a x6 ( i ) ，螃= 1 p ( ofa ) ，即天比a 更接近于优化目标因此经过反复迭代就可以得到a 的极大似然解，而且满足 墨l 氟= 1 , e j n la 巧= 1 , e m = 1 砖七= 1 这儿需要指出b a u m - w e l c h 算法得到的解是一个局部最 优值为了得到全局最优值，必须要求a 的参数初始值比较接近真实参数 2 3h m m 算法实现中的问题 2 3 1 初始模型选取 根据b a u m w e l c h 算法由训练数据得到h m m 参数时，一个重要的问题是初始模型的选取 不同的初始模型将产生不同的训练结果因为算法是使p ( o , h ) 局部极大时得到的模型参数，因 此，选取好的初始模型，使最后求出的局部极大与全局最大接近，是很有意义的但是，这个问 题至今还没有完美的答案一般认为，初始状态7 r 和状态转移矩阵a 的参数初始选取对模型的 影响不是很大，可以随机选取或均匀取值，但状态输出矩阵b 的初值对训练出的h m m 影响较 大，对它的选取需要慎重一种比较简单有效的方法是通过v i t e r b i 算法求出训练数据的状态序 列，然后根据状态序列估计状态输出矩阵的参数值其算法描述图2 4 这里，初始模型入可以任 意选取，但因为有p ( o a ) p ( o ) o ，所以a 是a 改进后的模型再将a 作为初始值利用重估公 式得到入这样就避免了初值的选择不当，变经典的入- 为入- 9 又_ 天 1 3 宁夏人学硕f ：学位论义第 二审隐马尔科人模型( h m m ) 图2 4 一种h i v i l v l 参数估计方法示意图 2 3 2 多个观察值序列训练 经典的b a u m - w e l c h 算法针对的单一序列，若针对多个观察值序列，则需要对算法加以修正 设l 个观察值序列为d ( ，z = 1 ，2 ，l ，其中d ( 。) = d ：n ，硝，d 坚) 假定各个观察值序列 独立，此时， l p ( o a ) = i ip ( o 从) 1 = 1 由于重估公式是以不同事件的频率为基础的，因此，对三个训练序列，重估公式修正为 亓t = a ，( i ) 硝。( o p ( o ( 。入) ，1 i ， 1 = 1 lt 厶t - - 1u ( 1 ( i ) 口臼幻( d 1 2 1 ) 卢卿1 ( 歹) 胪( d ( 1 a ) 2 鼍亳甚甄而河而丽颐广1 g 娲 壹1 董1 口p ( i ) 厦。) ( j ) p ( o i t ) a ) 幻詹= 2 4 本章小结 1 = 1t = l 肚o = v k l 墨a p ( j ) 毹。( j ) p ( d ( 1 ) a ) 1 = 1 t = 1 ( 2 1 5 ) ( 2 1 6 ) ， 15 歹n ，1 忌sm ( 2 1 7 ) 本章首先通过介绍m a r k o v 链引出h m m 模型的概念，为了更深入的理解h m m 模型的基本 原理，文中用一个非常经典的球一缸试验对h m m 的原理做了一形象具体的说明，接下来，本 章对h m m 在应用时的三大基本问题以及算法实现中需要解决的问题做了详细的讨论 1 4 宁夏人学硕i ：学位论义 第三章皋十h m m 模型的k 均值时问序列聚类 第三章基于h m m 模型的k 均值时间序列聚类 聚类是一种重要的机器学习方法，是指对数据集在某种测量下的非监督的划分方法与监督 学习方法不同，聚类不需要人工干预训练过程，有时这种干预过程是非常枯燥和费时的( 例如在 语音处理中的原始音频数据的切分和标记过程) 同时，聚类这种计算机自主地对样本集进行归 纳、总结的功能是人工智能的一个重要表现聚类的结果可以体现样本的本质结构，是对事物内 在特性的一种理解 3 0 1 以往在聚类时间序列时，般针对的是长度相同的序列，本章则针对长 度不定的序列提出了一种基于k 一均值的时间序列聚类算法 3 1 点聚类方法 常见的聚类方法，分析的对象是维数固定的向量这个向量可能是n 维空间的点，也可能是 数目确定的点构成的序列对于后者，可以用一个高维向量统一表示多个点这种可以用相同维 数的向量来表示的样本聚类问题称为点聚类问题在这种问题中，可以用样本在空间中的距离来 度量它们之间的相似性其中，距离可以用欧氏距离，或者其它任意的距离度量方法 k - m e a n s 是一种常用的点聚类算法该算法中，聚类的目标是使样本到聚类中心的距离平方 和最小这个准则函数是以计算各类均值m t ，与计算各类样本到其所属类均值点误差平方和为准 则，若各类均值表示成 1 弋， m i 。而乙 一掣q 其中第i 类集合为g ，其样本数目为肌，y 是样本特征向量 此时误差平方和准则可表示为 c 五= - m i l l 2 ， i = 1 掣c 其中c 为数据集的类别数，m i 为第i 类的类均值这个准则函数可以简单的解释为：对任何一个 类别q ，如果从g 中“误差”向量y m t 长度平方和为最小的意义上讲，均值向量m t 是最能 代表a 中所有样本的一个向量因此，以衡量的是用e 个均值向量m 1 ，m 。分别代表n 类样 本z 1 ，z n 而产生的平方和误差以的值取决于类别的数目和样本的分类情况，最优划分被定 义为使得以最小的划分，这样的聚类通常也称为最小方差划分( m i n i m u mv a r i a n c ep a r t i t i o n