论文摘要
随着计算机应用的普及，信息系统产生的数据量日益增大，如何有效的利用巨量的原始数据分析现状和预测未来，已经成为人类面临的一大挑战。近年来，越来越多的应用促使了数据流的产生，它是连续的、有序的、快速变化的、海量的数据，如网络连接数据、传感器数据和Web点击流数据，分析和挖掘这种类型的数据已经成为一个热点。聚类是挖掘数据流的一种重要工具。聚类就是把没有类别标记的样本按照某种准则划分为若干类，使类内样本的相似性尽可能大，而类间样本的相似性尽可能小，是一种无监督的学习方法。流聚类分析较传统的聚类分析具有更大的挑战性，这是由数据流的特性决定的。数据流分析的基本要求有：有限的使用内存及存储空间；对数据的访问最多一次；能够有较短的响应时间。除了内存限制和单遍扫描限制，数据流环境对聚类还有如下要求：不预先设定聚类个数，能处理具有任意形状的聚簇并且能够处理孤立点。目前已经提出了许多数据流聚类算法，但是都尚未解决以上数据流环境下的要求。传统的基于密度的聚类算法，如DBSCAN，可以发现具有任意形状的聚类，但这些算法的高复杂度以及多次扫描数据集的需求不适合对流数据进行聚类。在数据流滑动窗口模型下，本文提出了基于密度单元覆盖的数据流聚类算法DucStream。该算法能发现具有任意形状的数据流聚类，解决了由于数据流滑动窗口模型下不能精确记录每个数据，历史数据对聚类结果的影响问题。DucStream使用核心密度单元和候选密度单元刻画数据分布形式，作为在线数据摘要信息；根据每个单元中的最近数据到达时间修剪单元，保证了在线数据摘要信息是对当前窗口中数据流数据的覆盖；最后根据查询要求得到结果。在实际和人工数据集上的实验表明，DucStream算法具有良好的性能。