大规模分布数据的分阶段非线性聚类方法应用研究摘要：提出一种能够有效处理大规模分布的数据聚类问题且简化计算复杂度的分阶段非线性聚类方法，该算法包含两个阶段：首先将数据划分为若干个球形分布的子类，采用K近邻图理论对原始数据计算顶点能量并提取顶点攻能量样本；再采用K近邻算法对该高能量样本做一个划分，从而得到一个考虑高能量样本的粗划分同时估计出聚类的个数，最后，综合两次聚类结果整理得到最终聚类结果。该方法的主要优点是可以用来处理复杂聚类问题，算法较为稳定，并且在保持聚类正确率的同时，降低了大规模分布数据为相似性度量的计算代价。关键词：流数据；数据挖掘；聚类；非线性：TP315文献标识码：A：1009-3044(2013)34-7767-03流数据聚类算法是一种适用于大规模数据聚类的算法，尽管流数据聚类算法已经获得广泛研究，但它仍然是数据挖掘的重要研究课题[1-3]oCluStream是较早的流数据聚类算法[3],它采用微聚类来获取和保存历史流数据的统计信息。两个主要的局限是，ClusStreamH能用于线性可分数据并且不适合于高维流数据处理。为了适应高维流数据的处理，Aggarwal等人提出了一个改进的CluStream算法，称为HPStream[4],其主要思想是通过一个数据投影算法将维数降低，然后再执行ClusStream,但它仍然无法解决非线性可分流数据的问题。Guha等人提出一种基于K均值的流数据处理方法[8],与K均值算法本身的局限类似，该方法也同样不能处理非线性可分流数据。另一种流数据处理模型是基于网格的方法，如DUCStream[5]。通过动态地删除密度小于某个阈值的区域所组成的类，这种方法可以自适应于数据流中的类变化，但是仍然无法解决非线性可分流数据问题。流数据近邻传播方法StrAP[9],虽然可以解决密度变化及自适应估计聚类个数的问题，但是却不能够处理非线性可分流数据。近年来，非线性可分流数据聚类问题才引起了大家的关注[6-8]o为了解决非线性可分流数据聚类，Cao等人将经典的密度聚类算法DBSCAN推广到了流数据处理，提出了DenStream算法[6]。朱蔚恒等人提出的ACluStream聚类算法[7],通过定义有空间位置信息的聚类块，较好地克服了CluStream算法不能支持对任意形状聚类的缺陷。刘青宝提出的基于相对密度的数据流模糊聚类算法结合了相对密度聚类和模糊聚类的优点[8],能形成任意形状、多密度分辨率的层次聚类结果。这些富有启发性的研究工作为非线性可分流数据聚类问题建立了初步的基础，但该问题的研究远没有达到人们的期望。任何新的非线性可分聚类算法的出现，都有可能改善流数据聚类算法的效率。在设计基于进化计算的聚类算法时，最核心的两个问题就是进化个体的编码以及相似性度量。针对聚类问题的个体编码方式有很多，其中使用较多的是借用于K-均值算法的编码方式。即每个个体只对K个聚类中心进行编码，然后对数据样本按照其与聚类中心的相似性进行类别划分。因此，相似性度量对这类算法的性能有重要影响。最简单的相似性度量应该是欧氏距离，但是以欧氏距离作为相似性度量的进化聚类算法虽然在全局最优化性能上比传统的基于梯度下降的K-均值算法有较大提高，但同样存在一个重要的缺点。它们只对空间分布为球形或超球体的数据具有较好的性能，而对空间分布复杂的数据聚类效果很差，这是基于欧氏距离的相似性度量的缺陷导致的必然结果［10］。本文提出一种能够有效处理大规模分布的数据聚类问题且简化计算复杂度的分阶段非线性聚类方法，该算法包含两个阶段：首先将数据划分为若干个球形分布的子类，采用K近邻图理论对原始数据计算顶点能量并提取顶点攻能量样本；再采用K近邻算法对该高能量样本做一个划分，从而得到一个仅仅考虑高能量样本的粗划分同时估计出聚类的个数，最后，综合两次聚类结果整理得到最终聚类结果。2基于核方法的聚类中心点粗划分为研究核竞争学习聚类，本项目拟提出用中心点描述子［W?］表达核空间的聚类中心点。中心点描述子［W?］是一个内积矩阵，其每一行表达一个中心点，元素为中心点与样本点，中心点与中心点的核空间内积，从而给中心点在核空间内一个确定的表达，即：核空间上的竞争学习过程主要就是更新这个中心点描述子［W?］,即对...