具有容错特性的两层数据流聚类方法

摘要

提出一种具有容错能力的进化数据流聚类算法FTGDStream（Fault-TolerantGrid-Density Clustering over Data Stream）,通过在聚类过程中引入适当的松弛条件,从而在含有噪声的真实世界数据中获取更加泛化的有用知识.首先利用基于相似性度量和小波技术的HLSFTS（Hierarchical Lifting Scheme Fault-Tolerant Synopses）层次概要数据结构实现在线微聚类过程,然后采用基于网格密度的聚类算法实现离线宏聚类过程.在线算法所构造的小波概要数据结构对原始数据的高压缩率降低了离线网格密度聚类算法的计算负载,提高了二层数据流聚类算法的效率.在UCI数据集上的仿真实验结果表明,FTGDStream算法可以聚类任意空间形状的数据并且适用于高维数据流环境,是一种具有容错能力的高效数据流聚类算法.%A new envolving data stream clustering algorithm with fault-tolerance characteristic was proposed named FTGDStream（fault-tolerant grid-density clustering over data stream）.It introduces appropriate relaxation of conditions for discover generalised knowledge in real world data polluted by noise.First,FTGDStream uses similarity measure technology and lifting wavelet to construct synopsis HLSFTS（hierarchical lifting scheme fault-tolerant synopses） to realize online micro-cluster phase.Second,FTGDStream uses grid-density clustering technology to realize offline macro-cluster phase.High compression ratio of HLSFTS in micro-cluster reduces the computation load of grid-density clustering algorithm in macro-cluster and improves the efficiency of two-layer algorithm.Simulation in UCI data set proves that FTGDStream is able to clustering any shape in data space and suitable for dealing with high-dimensional data streams.FTGDStream is an efficient clustering algorithm with fault-tolerance.