数据流聚类方法的研究 ——基于概率密度和应用摘要层次的算法研究

论文摘要

近年来,作为数据挖掘的重要工具之一,聚类分析的应用领域日益广阔,越来越多的领域出现了大量的数据流。数据流具有数据量无限且流速快等特点,使得传统的聚类算法不能直接应用于数据流聚类问题,如何对数据流进行有效的聚类是当前数据挖掘领域的一个难点和热点问题。数据流聚类分析的难点之一就是要求算法只能有限次的扫描数据集,最好是一次扫描。本文针对数据流聚类的难点,给出了一种基于概率密度的数据流聚类算法,该方法不需要存储全部历史数据,只需要存储新到达的数据并对其应用EM算法,利用高斯混合模型增量式的更新概率密度函数。本文还给出了应用摘要层次结构的数据流聚类算法,该算法的在线阶段应用了两种摘要技术,基于小波的技术和基于回归的技术来构造摘要层次结构。基于回归的拟合模型可以得到较精确的摘要层次结构,而基于小波的拟合模型可以快速地建立摘要层次结构并且所需的存储空间比较小。为了验证以上两种算法的性能,进行了一系列的仿真实验和对真实数据的实验。通过实验证明本文所给出的算法,运算速度有了很大的提高,并且随着簇数目和数据维度的增大运行时间呈线性增长,对噪音敏感度较低。另外,通过对真实数据的实验表明,算法的聚类质量也有大幅度的提高。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 研究背景
• 1.1.1 数据挖掘概述
• 1.1.2 数据挖掘的任务
• 1.1.3 数据挖掘的方法
• 1.1.4 聚类分析
• 1.2 流聚类的研究现状
• 1.3 本文的主要工作
• 1.4 论文基本结构
• 第二章 聚类分析
• 2.1 聚类分析概述
• 2.1.1 聚类的定义
• 2.1.2 相似性度量（求相异度方法）
• 2.1.3 对聚类分析算法的典型要求
• 2.2 传统的聚类方法及算法综述
• 2.2.1 划分方法（Partition methods）
• 2.2.2 层次方法（Hierarchical Method）
• 2.2.3 基于密度的方法（Density-based Method）
• 2.2.4 基于网格的方法（Grid-based Method）
• 2.2.5 基于模型的方法（Model-based Method）
• 2.3 本章小节
• 第三章 数据流聚类
• 3.1 数据流模型
• 3.2 数据流挖掘与传统数据挖掘的不同
• 3.3 数据流聚类方法及算法综述
• 3.3.1 STREAM：基于k 中位数的流聚类算法
• 3.3.2 CluStream：聚类演变的数据流
• 3.4 本章小节
• 第四章 基于概率密度的数据流聚类算法
• 4.1 EM 算法和高斯混合模型
• 4.2 基于概率密度的数据流聚类算法
• 4.2.1 在线的pdmicro-cluster 过程
• 4.2.2 离线的pdmacro-cluster 过程
• 4.3 仿真实验
• 4.3.1 算法PDCluStream 的扩展性实验
• 4.3.2 处理有噪声数据集的实验
• 4.4 PDCluStream 算法的应用
• 4.4.1 实验环境和数据集
• 4.4.2 聚类质量比较
• 4.4.3 聚类处理时间
• 4.4.4 GC 率影响
• 4.5 本章小节
• 第五章 应用摘要层次的数据流聚类算法
• 5.1 SHCLU 算法聚类框架
• 5.2 SHCLU 算法的在线保持阶段
• 5.2.1 基于小波的拟合模型
• 5.2.2 基于回归的拟合模型
• 5.3 离线的聚类阶段
• 5.3.1 对全部历史数据的分析
• 5.3.2 时间窗口分析
• 5.4 实验结果分析
• 5.4.1 聚类质量分析
• 5.4.2 对聚类中心准确识别命中率
• 5.4.3 算法随数据维数增大的准确性实验
• 5.5 本章小节
• 第六章 总结与展望
• 致谢
• 参考文献
• 攻读硕士学位期间发表的论文