企业的大型数据库中蕴含的大量有用的信息资源,促进了知识发现和数据挖掘的兴起。聚类是数据挖掘中一个重要的分析方法,其定义如下:给定k维空间的n个数据点,把这n个点分成d个组,即满足最大的组内相似性和最小的组间相似性,使得不同聚类中的数据尽可能地不同,而同一聚类中的数据尽可能地相似。 数据挖掘、统计学、机器学习等很多领域都涉及到聚类分析,它被应用到市场营销聚类分析、空间数据技术、生物学、生物医学上基因分析、国土资源利用等诸多领域。数据挖掘领域中的聚类分析主要是针对大的数据集,相关聚类算法的研究主要集中在算法的可伸缩性、算法对聚类复杂形状和类型的数据的有效性以及处理不同类型属性的能力等方面。 近年来,越来越多的应用产生数据流,它是连续的、有序的、快速变化的、海量的数据。流数据不同于传统的存储在磁盘上的静态的数据,而是一类新的数据对象。典型的流数据包括网络与道路交通监测系统的监测信息数据、电信部门的通话记录数据、由传感器传回的各种监测数据、股票交易所的股票价格信息数据以及环境温度的监测数据等。流数据聚类分析成为聚类研究的一个重要方向。 流数据聚类分析较传统的聚类分析具有更大的挑战性,这是由流数据的特性所决定的。对流数据分析的要求如下:第一,有限的使用内存及存贮空间;第二,对数据的访问最多一次;第三,要能够跟上流的速度。本文分析了流数据对聚类的要求以及流数据聚类方面的最新研究成果。研究发现,目前的流数据聚类算法大多是基于k-中心或k-均值的算法,其缺点是不能对任意形状的数据分布进行聚类。传统的基于密度的聚类算法,如DBSCAN,可以发现任意形状的类,但这些算法的高复杂度及多次扫描数据集的需求不适合对流数据进行聚类。基于空间划分的算法CLIQUE可以发现任意形状的类,且只需一次扫描数据集。但是,该算法中产生的单元的个数与数据集维数成指数增长,算法的高复杂度不适合对流数据进行分析。 本文提出了一种新的索引结构CD-Tree对空间划分生成的非空单元进行索引,使生成的单元数大大减少。基于该结构,提出了一种基于密度的流数据聚类算法CDS,该算法可以实现对任意形状分布的流数据进行聚类。该算法分为滑动窗口上的在线聚类及基于磁盘的离线演化分析两部分。本文还提出了一种新的衡量数据