针对大规模时间序列数据的改进聚类算法

摘要

时间相关的数据在日常生活中普遍存在，数据的安全性也越来越受到人们的重视。在针对时间数据的异常检测系统中，聚类是常用的挖掘方法。但是多数时间序列聚类算法侧重于以批处理的方式检测集群，这种方案会消耗大量存储空间，限制了聚类算法在处理大型时间数据时的性能和扩展能力。针对这一问题，本文提出了一种基于平衡迭代规约层次聚类(BIRCH)的改进算法——Ex-BIRCH算法，以准确地挖掘时间序列中的模式信息。
　　论文的研究工作得到了国家自然科学基金项目(No.61172072、61271308)、北京市自然科学基金项目(No.4112045)和高等学校博士学科点专项科研基金(No.20100009110002)的支持。论文的主要工作包括:
　　首先，本文对现有聚类算法进行了较为详细的分析，指出了时间序列聚类所面临的挑战。接着分析了BIRCH聚类算法在处理大规模数据时具有的优势。在此基础上提出了一种适用于时间序列的改进聚类算法，并介绍了具体的改进方案:
　　(1)替换了BIRCH算法中的距离度量。考虑到欧氏距离不能准确衡量时间序列这一事实，Ex-BIRCH算法采用动态时间归整(DTW)作为时间序列的距离度量;
　　(2)更改了BIRCH算法中的集群质心计算方法。本文对DTW下的质心平均算法(DBA算法)做出调整，提出了一种Ad-DBA算法。Ad-DBA算法可以在数据流环境下计算时间序列的均值。Ex-BIRCH算法使用Ad-DBA算法作为集群质心的计算方法;
　　(3)修改了BIRCH算法中的集群特征。距离度量和均值计算方法的改变会导致BIRCH算法中原有的特征向量失效。根据DTW算法以及Ad-DBA算法的计算过程，本文提出一种新的集群特征向量替代了原始向量。
　　论文还对Ex-BIRCH算法、BIRCH算法、k-means算法以及BIRCH和k-means的变体算法的准确性和效率进行了评估。计算结果表明，改进算法的聚类准确率，相比于原始BIRCH算法以及BIRCH的变体算法有显著地提高。达到了与全局聚类算法（k-means算法和k-DBA算法）准确率相当的水平。然而，与k-means和k-DBA算法不同的是，Ex-BIRCH算法可以增量地处理连续到来的数据对象。
　　最后，本文在滑动窗口模型的帮助下，将Ex-BIRCH算法部署到仿真环境中进行实现和分析。结果进一步证明改进算法可以在数据流环境下完成序列模式挖掘工作。

目录

声明

致谢

摘要

1．1 论文背景与意义

1．2 主要研究工作

1．3 论文组织结构

2 时间序列聚类相关理论

2．1 聚类算法介绍

2．1．1 静态聚类算法

2．1．2 时间序列聚类

2．1．3 聚类算法评价标准

2．2 时间序列距离度量及平均技术

2．2．1 时间序列距离度量

2．2．2 时间序列平均技术

2．3 时间序列预处理技术

2．3．1 序列标准化及频域变换

2．3．2 滑动窗口模型

2．4 BIRCH算法与K-MEANS算法

2．4．1 BIRCH算法

2．4．2 k-means算法

2．8 本章小结

3 针对时间序列的改进聚类算法

3．1 改进聚类算法概述

3．2 改进聚类算法的距离度量

3．3 改进聚类算法的集群特征

3．3．1 集群特征(CF)以及CF树

3．3．2 改进的集群特征向量

3．4 改进聚类算法的序列平均技术

3．4．1 DTW下的重心平均算法

3．4．2 Ad-DBA算法

3．5 本章小结

4 聚类算法评估与精度损失量化

4．1 运算设置

4．1．1 数据集

4．1．2 对照算法

4．1．3 参数设置

4．1．4 评价标准

4．2 计算结果

4．3 调整后DBA算法的精度损失

4．4 分析概括

4．5 本章小结

5 仿真环境算法实现

5．1 滑动窗口模型

5．2 仿真设置与结果

5．2．1 环境设置

5．2．2 仿真运算结果

5．3 仿真运算结论

5．4 本章小结

6．1 论文总结

6．2 研究展望

参考文献

附录

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集