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