基于隐马尔可夫模型的时间序列聚类的研究

论文摘要

隐马尔可夫模型（Hidden Markov Model,HMM）是一种概率模型,它假定观测序列是由包含若干隐状态的马尔可夫过程产生的。HMM在语音、手写体、运动轨迹识别和生物信息学等领域有着广泛的应用。基于该模型的时间序列数据聚类算法有两个显著的优点:1)适用于不等序列长度甚至缺失某一时刻观测值的时间序列。2)能够利用时间序列隐含的属性（马尔可夫性）来提高聚类精度。近年来,基于HMM的聚类算法的研究大部分是基于实际应用,而对其准确性和健壮性的研究较有限。本文提出一种基于概率模型的聚类算法——通过计算时间序列在不同HMM参数下的后验概率分布的Kullback-LeiblerDivergence（KLD）来构建相似度矩阵,并将该矩阵用作谱聚类算法的输入。与大部分现有的基于HMM的聚类算法不同,本文采用KLD来度量时间序列对之间的相似度。KLD作用于整个模型参数空间,更充分地利用了概率模型中的信息。在人工和实际数据集上的实验结果表明,该算法在同等条件下相比基于其他距离度量（如互匹配值）的算法具有更高的聚类精度。另一方面,谱聚类算法通过特征向量分解能有效去除时间序列数据中噪声的影响,该算法相比传统聚类算法（如K-Means）,在加入内源性噪声和外源性噪声的人工数据上表现出更好的健壮性。本文的主要贡献包括:（1）研究了距离度量函数以及特征向量分解对聚类精度的影响。以往基于HMM的算法大部分采用互匹配值、BP距离等来度量时间序列间的距离,这些度量函数虽然具有一定的合理性,但是它们只利用了特定时间序列对之间的概率信息,而没有考虑全局概率空间。这种度量的局部性会导致最终聚类准确度的降低。另外,当附加在时间序列数据上的噪声等级上升时,传统的聚类算法,如K-Means、层次聚类等的准确性将明显下降。本文通过引入KLD和谱聚类有效解决了上述两个问题。（2）研究了隐状态数对聚类精度的影响。在HMM的应用中,隐状态数通常是预先设定的。虽然对于某些马尔可夫过程,隐状态有明确的意义（如语音识别中通常认为隐状态表示音节）,但是对于更多的时间序列数据,很难赋予隐状态物理意义。本文对不同隐状态数目下的聚类精度做了研究,发现聚类精度随隐状态数不单调地变化,当模型过度拟合时,聚类精度反而会下降。并且,模型的训练时间将随隐状态数的增加而平方级增加。（3）研究了学习聚类数目的方法。通常聚类的类别数是预先设定的。但是在实际应用中,数据集的类别数往往无法预知,这就需要一种衡量聚类质量的标准来选出最优聚类数。本文采用α值来衡量聚类质量,这种度量不仅能使类内相似度最大,而且可以防止极少数样本点划分为一类的现象。实验结果表明,这种度量方法能找到正确的聚类数。

论文目录

• 摘要
• ABSTRACT
• 表格索引
• 插图索引
• 主要符号对照表
• 第一章 绪论
• 1.1 研究背景与意义
• 1.2 时间序列数据聚类
• 1.2.1 基于原始数据的聚类
• 1.2.2 基于特征的聚类
• 1.2.3 基于模型的聚类
• 1.3 其他背景知识
• 1.3.1 随机过程
• 1.3.2 马尔可夫过程
• 1.4 本文概述
• 1.4.1 本文的研究目标与方法
• 1.4.2 本文的主要成果
• 1.4.3 本文结构
• 第二章 HMM 模型
• 2.1 HMM 的发展背景
• 2.2 HMM 的基本原理
• 2.3 HMM 的类型
• 2.4 HMM 的基本问题及其算法
• 2.4.1 评估问题和Forward-Backwark 算法
• 2.4.2 解码问题和Viterbi 算法
• 2.4.3 学习问题和Baum-Welch 算法
• 2.5 本章小结
• 第三章 谱聚类算法
• 3.1 背景
• 3.2 拉普拉斯图
• 3.2.1 图模型表示
• 3.2.2 谱图理论
• 3.3 算法描述
• 3.4 本章小结
• 第四章 基于HMM 的时间序列聚类算法
• 4.1 相似性度量
• 4.2 聚类结果评估
• 4.3 算法框架描述
• 4.4 实验结果分析
• 4.4.1 人工数据
• 4.4.2 实际数据
• 4.5 本章小结
• 第五章 总结与展望
• 5.1 结论
• 5.2 研究展望
• 附录 A HMM 数值计算问题
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文目录
• 附件