基于衰减窗口与剪枝维度树的实时数据流聚类研究

作     者：曾伟 

作者单位：武汉科技大学 

学位级别：硕士

导师姓名：张晓龙

授予年度：2009年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：数据流挖掘 聚类分析 衰减窗口 密度维度树 剪枝策略 

摘      要：实时数据流挖掘是目前数据挖掘与数据库领域的新兴研究热点,针对实时数据流的聚类分析技术也是该研究中最具有挑战性的难题之一。本文首先介绍了基于实时数据流的数据挖掘和知识发现的研究背景以及该领域现有的主要研究分支:聚类、分类、频繁模式挖掘、关联规则分析等。然后综述了实时数据流聚类技术的最新研究进展,在介绍实时数据流聚类相关理论和常用技术的基础上,对现有各种代表性实时数据流聚类算法的优势和不足进行了系统地分析,从处理速度、聚类形状、演化分析、高维性能及噪声健壮性五个方面对这些聚类算法的性能进行了深入地比较研究,探讨了基于聚类的实时数据流演化分析方法及其局限性。 针对现有实时数据流聚类算法存在的处理速度慢、系统消耗大以及不能识别任意形状聚类等问题,本文设计并实现了一种基于衰减窗口与密度维度树的实时数据流聚类算法PDStream,该算法首先对数据空间进行网格划分,将数据流依次映射到网格空间中,采用一种改进的维度树结构在线维护和更新数据流的概要数据结构,同时设计了一种周期性剪枝策略,周期性地剪去维度树中的稀疏网格,以降低系统消耗,最后采用深度优先搜索算法在线处理聚类请求,通过不同时刻的聚类结果比对来实现数据流的演化分析。 基于人工数据集和真实数据集的实验表明,本研究所提出的聚类算法PDStream可以有效地发现实时数据流在任意时刻具有任意形状的聚类,并且聚类效果较好、内存消耗少、处理速度快,具有较好的计算精度。