不确定数据流环境下聚类算法的研究与实现

论文摘要

数据挖掘技术因其能从海量的信息中提取有用的知识模式而受到人们普遍的关注,而聚类作为其中一种重要的数据挖掘方法,能够从用户给出的描述数据对象的信息中将数据对象分组,从而发现数据分布与属性之间的关系,因此被广泛用于许多应用领域。近年来,随着数据收集技术的进步,人们对数据的认识也逐步加深,数据的不确定性问题日渐引起人们的关注。传统的聚类技术无法直接应用到不确定数据上,因此需要对不确定数据的聚类技术进行研究。然而在大多数应用场合,数据并不都是存放于数据库中,而是以数据流的形式存在。由于流数据具有时间有序、速度可变、数据量巨大等特点,因此对于不确定数据流的聚类技术有着更高的要求。例如在数据流环境下,数据快速到达,要求聚类算法具有较快的处理速度。但当聚类的对象是不确定数据的时候,算法的时间开销很大。本文从缩短聚类时间的角度考虑,提出两种面向不确定数据流环境的聚类算法。文中首先对不确定数据点用MBR描述其实例的分布特征,并证明了不确定数据点和簇的期望距离可以用不确定数据点MBR的中心点和簇心之间的确定距离来表示,且误差不会超过MBR对角线的一半。基于此,提出了一种不确定数据流环境下的聚类算法,通过期望距离范围的上下界排除一些距离较远的簇,从而达到减少计算代价的目的。其次,为了进一步提高算法的性能,文中根据簇内数据点的分布特征提出了簇的MBR的概念,并根据不确定数据点MBR和簇的MBR的位置关系提出了一种新的划分数据点的策略。MBR的位置关系有三种：包含、相交、相离,通过简单的判断不确定数据点MBR和微簇MBR的位置关系,可以将一些距离当前不确定数据点明显较远的簇排除,从而提高聚类算法效率。最后,本文对提出的两种算法进行了实验验证,实验结果表明两种算法均能有效的减少计算的代价,从而缩短聚类执行的时间。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景及意义
• 1.1.1 聚类技术概述
• 1.1.2 数据流
• 1.1.3 不确定数据产生原因
• 1.2 国内外研究现状
• 1.3 本文主要工作
• 1.4 本文组织结构
• 第2章 相关工作
• 2.1 不确定数据模型
• 2.2 数据流聚类
• 2.2.1 单边扫描算法
• 2.2.2 演化算法
• 2.3 不确定数据聚类
• 2.3.1 基于划分的方法
• 2.3.2 基于密度的方法
• 2.3.3 其它方法
• 2.4 不确定数据流聚类
• 2.5 本章小结
• 第3章 基于剪枝技术的不确定数据流聚类算法
• 3.1 问题描述及相关定义
• 3.1.1 问题描述
• 3.1.2 相关定义
• 3.2 基于期望距离的聚类算法
• 3.2.1 期望距离的等价化
• 3.2.2 三角不等式剪枝策略
• 3.2.3 算法框架
• 3.2.4 时间复杂性分析
• 3.3 基于空间位置关系的聚类算法
• 3.3.1 微簇的聚类特征结构
• 3.3.2 MBR的空间位置关系
• 3.3.3 边界情况的优化
• 3.3.4 算法框架
• 3.4 算法的扩展
• 3.5 本章小结
• 第4章 实验及结果分析
• 4.1 实验环境与实验设计
• 4.1.1 实验环境
• 4.1.2 实验数据集
• 4.1.3 实验方案
• 4.2 性能分析
• 4.2.1 效率和有效性
• 4.2.2 参数影响
• 4.2.3 扩展性
• 4.3 本章小结
• 第5章 总结与展望
• 参考文献
• 致谢