基于密度网格的数据流聚类算法研究

论文摘要

数据挖掘即为从大量数据中提取或“挖掘”知识。更具体地说,就是通过对数据进行深入分析,得到隐藏在数据背后的本质特性和普遍规律。聚类分析作为数据挖掘中的一种重要方法,在各领域中有着广泛的应用。按照某种相似性度量准则,将物理或抽象对象的集合分成相似的对象类的过程称为聚类。通过聚类可以发现数据全局分布模式与对象属性之间有趣的相关性。近年来,随着计算机与通信技术的发展,在各行业当中产生了大量的数据流。这种数据具有以下特性：数据流速快,数量无限,动态变化,无法预测。由于以上种种特性的限制,在对数据流进行聚类分析时产生了众多的难题。已有许多学者对数据流聚类分析方法进行了大量的研究,但仍存在许多尚待改善的地方。基于密度与网格的聚类方法在各种聚类方法中有着计算速度快,可以发现任意形状的类等特殊优势,适用于数据流的聚类分析。对于基于网格与密度的算法而言,网格的密度阈值是一个至关重要的参数,在很大程度上影响了算法的聚类质量。而缺乏领域知识与数据先验知识的用户很难对此参数进行确定。本文采用平均密度的方法,通过对数据初始分布的网格密度进行统计,确定网格的密度阈值,并在数据流的处理过程当中进行动态的调整,以应对数据流动态变化的特性。聚类边界难以精确是基于网格的聚类方法中另外一个普遍存在的问题,其原因在于在基于网格的方法中通过舍弃数据的原有信息而只对网格进行操作。将数据信息进行适量保存,对类边界的网格进行不均匀划分,可以提高类边界的精确度。大部分基于网格的聚类算法在聚类的形成过程中采用随机的生成顺序,这会产生大量没有意义的小聚类,本文在聚类的生成过程中选取密度最高的网格单元作为起始点进行搜索,这有助于发现簇的原有结构。在上述研究的基础上,本文提出了一种基于D-Stream算法的改进数据流聚类算法。通过对人工数据与真实数据的实验分析与实验结果对比,表明算法能够获得良好的聚类质量。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 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.2.3 聚类算法的典型要求
• 2.2.4 聚类分析算法
• 2.3 数据流聚类分析
• 2.3.1 数据流聚类特点
• 2.3.2 经典数据流聚类算法
• 2.4 本章小结
• 第3章 基于密度网格的数据流聚类算法
• 3.1 算法背景与存在问题
• 3.2 基本概念
• 3.2.1 密度网格单元
• 3.2.2 格簇
• 3.2.3 探查数据流的演化过程
• 3.2.4 空网格单元的探测与移除
• 3.3 对存在问题的改进
• 3.3.1 网格单元密度阈值的设定
• 3.3.2 簇边缘的精度提升
• 3.3.3 聚类顺序的确定
• 3.4 NDD-Stream算法
• 3.4.1 算法基本思想
• 3.4.2 在线部分
• 3.4.3 离线部分
• 3.5 本章小结
• 第4章 实验结果与分析
• 4.1 实验数据与评价方法
• 4.1.1 数据集
• 4.1.2 聚类效果评价
• 4.2 数据流的动态演化
• 4.3 聚类效果测试
• 4.3.1 聚类形状测试
• 4.3.2 聚类质量测试
• 4.3.3 执行效率测试
• 4.4 算法参数设置测试
• 4.5 本章小结
• 结论与展望
• 致谢
• 参考文献
• 攻读硕士学位期间发表的论文