基于密度网格的数据流聚类和概念漂移检测算法研究

摘要

数据流聚类算法是一项关键的数据挖掘技术，在数据流聚类研究中，算法框架可以分为两类:single-phase model和two-phase scheme。应用two-phase scheme的基于密度网格的数据流聚类框架，包含了在线处理阶段和离线处理阶段。在线处理阶段中，将据流数据映射到网格中，在离线处理阶段中，对网格数据聚类，此框架降低了数据流聚类的难度。但是在离线处理阶段中，这种聚类框架也存在三点缺陷:(1)基于固定阈值的稀疏网格或稠密网格判定不能适用于不均匀分布的数据流和多密度的数据流;(2)基于密度把相邻的网格连接为一类，而没有考虑数据之间的相似度，数据间相似度考量的缺失会影响数据聚类的准确性;(3)边界点的检测考量不够全面，有的边界点是噪音，而有的边界点可能属于邻近的簇。
　　数据流的概念也会随着时间的推移而改变，这种现象被称为概念漂移。DCDA是一种基于粗糙集理论和滑动窗口技术的概念漂移检测算法，其主要思想是:计算两个滑动窗口之间的距离判断概念漂移。这种算法存在如下缺陷:(1)只适用于分类型数据;(2)没有考虑一个窗口中包含多概念的情况;(3)无法确定合适的滑动窗口尺寸。
　　针对以上问题，本文的主要贡献如下:
　　第一，针对DCDA概念漂移检测存在的缺陷，提出了一种基于密度网格的数据流概念漂移检测框架（简称DCDD）。该框架利用网格技术，进而使得其适用于一般的数据。在解决滑动窗口中多概念问题上，在在线处理阶段中创建一个临时密度网格和一个历史密度网格，根据数据集到达时间给网格赋予一个权值扩展了DCDA检测模型，计算临时密度网格和历史密度网格的距离检测概念漂移。在离线处理阶段中训练提取的概念漂移特征，提出一个预测模型，预测概念数据量，并根据预测量设计了可变尺寸的滑动窗口。实验结果表明，我们检测概念漂移的时间远低于DCDA算法，且检测的概念漂移更准确，更有效。
　　第二，针对基于密度网格的数据流聚类框架的缺陷，提出了一种基于相对密度网格的数据流聚类算法和边界检测算法。其主要思想是:计算相邻网格之间的相似性，并根据相似性作为权重去影响相邻网格之间的连接，而连接相邻网格是根据一个考虑了密度、质心和相邻网格之间的相似性权重的差异模型。最后，我们提出了一个边界检测算法，使用隶属函数给簇周围稀疏网格中的数据点打上簇标签。实验结果表明，我们的算法适用于多密度分布的数据流，且具有更好的聚类质量。

目录

声明

致谢

摘要

1．1．1 研究背景

1．1．2 研究意义

1．2 国内外研究现状

1．2．1 国内外数据流挖掘研究现状

1．2．2 国内外概念漂移研究现状

1．3 本论文主要工作

1．4 本论文结构安排

2 数据流聚类的相关研究

2．1 数据分析基础

2．1．1 数据集种类

2．1．2 数据的相关联系

2．1．3 数据挖掘相关技术

2．2 传统数据聚类算法

2．3 数据流聚类算法综述

2．3．2 Two-phase scheme算法

2．3．3 基于密度网格的数据流聚类算法

2．4 本章小结

3 数据流中概念漂移的相关研究

3．1 概念漂移的介绍和种类

3．2 概念漂移的检测算法分类

3．3 基于增量式决策树模型的数据流概念漂移检测

3．3．1 CVFDT系列数据流概念漂移检测

3．3．2 RDT系列数据流概念漂移检测

3．4 通过数据流属性检测概念漂移

3．5 本章小结

4 基于密度网格改进DCDA概念漂移检测的聚类算法

4．1 问题背景

4．2 相关研究工作

4．2．1 基于密度网格数据流聚类框架的基本定义

4．2．2 DCDA概念漂移检测模型

4．3 基于密度网格的概念漂移检测算法

4．3．1 算法基本框架

4．3．2 DCDD概念漂移检测模型

4．3．3 滑动窗口调整策略

4．3．4 预测模型和Concept-Feature

4．3．5 算法描述与分析

4．4 实验结果

4．4．1 实验设备与数据集

4．4．2 实验结果评价指标

4．4．3 实验结果对比

4．5 本章小结

5 基于相对密度网格的数据流聚类算法和边界检测

5．1 问题描述

5．2 问题解决思想

5．3 相对密度网格聚类算法和边界检测算法

5．3．1 相邻网格的相似权重

5．3．2 相对密度网格聚类

5．3．2 边界检测算法

5．4 实验结果

5．4．1 实验设备与数据集

5．4．2 测试多密度数据集

5．4．3 测试包含边界点的数据集

5．4．4 真实数据集实验结果对比

5．4．5 时间性能对比

5．5 本章小结

6．1 研究工作总结

6．2 今后工作展望

参考文献

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

学位论文数据集