基于密度的不确定数据流聚类算法的研究与实现

论文摘要

近年来,随着网络和作用于网络设备的迅速发展及应用,使大量不确定数据流进入人们的商业应用和学术研究中。例如无线传感器网络WSN(Wireless Sensor Networks)、射频识别RFID(Radio Frequency Identification)等技术的快速发展使大量不确定流数据应运而生。针对不确定数据流环境的聚类分析有着十分重要的应用前景,已经成为当前的研究热点。然而已有的面向静态数据或确定数据流的聚类分析算法已不能满足当前需求。因此开展不确定数据流聚类算法的研究势在必行。在不确定数据流中,数据的不确定性给聚类算法在利用数据信息问题上提出了极大的挑战,首先,简单的计算期望距离将无法得到高质量的聚类结果；其次,现有的数据流聚类算法大多使用标界窗口或类似标界窗口,往往只简单删除最久未更新的簇,因此无法高效处理演化数据流以及分析近期数据的聚类细节；最后,基于划分的流数据聚类算法大多只能形成球形簇,无法针对不同数据分布情况形成任意形状的簇。基于此,本文对不确定数据流环境下基于密度的聚类算法展开研究。首先,本文提出不确定度的概念以衡量不确定数据的分布信息,并通过改进面向确定数据的聚类算法DENCLUE,使其可以处理附带不确定度的不确定数据,以尽量降低数据的不确定性对聚类结果产生的影响。其次,提出在滑动窗口下的基于密度的不确定数据流聚类算法USDENCLUE,并通过聚类特征指数直方图技术实现其快速的删减功能,使其在分析特定时间窗口的聚类细节的同时可以高效的处理噪音数据、演化数据流以及生成任意形状的簇以提高聚类质量。最后,采用真实数据集以及人工合成数据集并与著名的Clustream聚类算法进行比较,实验结果表明USDENCLUE聚类算法在处理不确定数据流时具有良好的聚类效果,并且可以有效的处理噪音数据及演化数据流。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景与意义
• 1.2 国内外研究现状
• 1.3 数据流聚类技术面临的挑战
• 1.4 本文主要贡献
• 第2章 相关研究工作概述
• 2.1 确定数据聚类概述
• 2.1.1 静态数据聚类算法
• 2.1.2 数据流聚类算法
• 2.2 不确定数据聚类概述
• 2.2.1 不确定数据产生原因
• 2.2.2 不确定数据模型
• 2.2.3 不确定数据聚类算法
• 2.2.4 不确定数据流聚类算法
• 2.3 本章小结
• 第3章 基于密度的不确定数据流聚类算法
• 3.1 不确定数据的相关问题
• 3.1.1 数据模型
• 3.1.2 数据的不确定性对聚类结果的影响
• 3.1.3 数据不确定度的定义
• 3.2 不确定数据聚类算法UDENCLUE
• 3.2.1 相关概念及定义
• 3.2.2 不确定影响函数
• 3.2.3 算法描述
• 3.2.4 本地不确定元组密度
• 3.3 基于密度的不确定数据流聚类算法USDENCLUE
• 3.3.1 数据流滑动窗口概念及相关问题
• 3.3.2 微簇结构的相关定义
• 3.3.3 算法描述
• 3.4 本章小结
• 第4章 实验及结果分析
• 4.1 实验环境
• 4.2 数据集
• 4.3 实验分析
• 4.3.1 算法有效性
• 4.3.2 数据不确定度
• 4.3.3 噪音数据
• 4.3.4 处理演化数据流
• 4.4 本章小结
• 第5章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 致谢