信息与电脑杂志入选论文参考

　　流数据聚类算法是一种适用于大规模数据聚类的算法，尽管流数据聚类算法已经获得广泛研究，但它仍然是数据挖掘的重要研究课题[1-3]。CluStream是较早的流数据聚类算法[3]，它采用微聚类来获取和保存历史流数据的统计信息。两个主要的局限是，ClusStream只能用于线性可分数据并且不适合于高维流数据处理。为了适应高维流数据的处理，Aggarwal等人提出了一个改进的CluStream算法，称为HPStream[4]，其主要思想是通过一个数据投影算法将维数降低，然后再执行ClusStream，但它仍然无法解决非线性可分流数据的问题。Guha等人提出一种基于K均值的流数据处理方法[8]，与K均值算法本身的局限类似，该方法也同样不能处理非线性可分流数据。另一种流数据处理模型是基于网格的方法，如DUCStream[5]。

　　摘要：提出一种能够有效处理大规模分布的数据聚类问题且简化计算复杂度的分阶段非线性聚类方法，该算法包含两个阶段：首先将数据划分为若干个球形分布的子类，采用K近邻图理论对原始数据计算顶点能量并提取顶点攻能量样本；再采用K近邻算法对该高能量样本做一个划分，从而得到一个考虑高能量样本的粗划分同时估计出聚类的个数，最后，综合两次聚类结果整理得到最终聚类结果。该方法的主要优点是可以用来处理复杂聚类问题，算法较为稳定，并且在保持聚类正确率的同时，降低了大规模分布数据为相似性度量的计算代价。

　　关键词：流数据,数据挖掘,聚类,非线性

　　通过动态地删除密度小于某个阈值的区域所组成的类，这种方法可以自适应于数据流中的类变化，但是仍然无法解决非线性可分流数据问题。流数据近邻传播方法StrAP[9]，虽然可以解决密度变化及自适应估计聚类个数的问题，但是却不能够处理非线性可分流数据。近年来，非线性可分流数据聚类问题才引起了大家的关注[6-8]。为了解决非线性可分流数据聚类，Cao等人将经典的密度聚类算法DBSCAN推广到了流数据处理，提出了DenStream算法[6]。朱蔚恒等人提出的ACluStream聚类算法[7]，通过定义有空间位置信息的聚类块，较好地克服了CluStream算法不能支持对任意形状聚类的缺陷。刘青宝提出的基于相对密度的数据流模糊聚类算法结合了相对密度聚类和模糊聚类的优点[8]，能形成任意形状、多密度分辨率的层次聚类结果。这些富有启发性的研究工作为非线性可分流数据聚类问题建立了初步的基础，但该问题的研究远没有达到人们的期望。任何新的非线性可分聚类算法的出现，都有可能改善流数据聚类算法的效率。

　　在设计基于进化计算的聚类算法时，最核心的两个问题就是进化个体的编码以及相似性度量。针对聚类问题的个体编码方式有很多，其中使用较多的是借用于K-均值算法的编码方式。即每个个体只对K个聚类中心进行编码，然后对数据样本按照其与聚类中心的相似性进行类别划分。因此，相似性度量对这类算法的性能有重要影响。最简单的相似性度量应该是欧氏距离，但是以欧氏距离作为相似性度量的进化聚类算法虽然在全局最优化性能上比传统的基于梯度下降的K-均值算法有较大提高，但同样存在一个重要的缺点。它们只对空间分布为球形或超球体的数据具有较好的性能，而对空间分布复杂的数据聚类效果很差，这是基于欧氏距离的相似性度量的缺陷导致的必然结果[10]。

　　本文提出一种能够有效处理大规模分布的数据聚类问题且简化计算复杂度的分阶段非线性聚类方法，该算法包含两个阶段：首先将数据划分为若干个球形分布的子类，采用K近邻图理论对原始数据计算顶点能量并提取顶点攻能量样本；再采用K近邻算法对该高能量样本做一个划分，从而得到一个仅仅考虑高能量样本的粗划分同时估计出聚类的个数，最后，综合两次聚类结果整理得到最终聚类结果。

　　2基于核方法的聚类中心点粗划分

　　为研究核竞争学习聚类，本项目拟提出用中心点描述子[W?]表达核空间的聚类中心点。中心点描述子[W?]是一个内积矩阵，其每一行表达一个中心点，元素为中心点与样本点，中心点与中心点的核空间内积，从而给中心点在核空间内一个确定的表达，即：

　　核空间上的竞争学习过程主要就是更新这个中心点描述子[W?]，即对于某个新来的样本[?（xi）]，选择核空间上距离该样本最近中心点作为优胜者中心点，也即中心点描述子[W?]对应的行向量[W?v，：]；接着再使之朝着该样本在核空间内移动一定的距离，是这个行向量[W?v，：]得到对应的更新，如图9所示。这样便可以通过中心点描述子及对应的竞争学习过程提出一个核竞争学习框架。

　　在核竞争学习的框架上，我们将进一步考虑添加各种自动聚类个数估计机制，如对手惩罚机制，实现能够自动估计聚类个数的核竞争学习算法。为添加对手惩罚机制，我们首先初始化一个中心点描述子，使其行向量的个数，即初始聚类个数远远大于实际聚类个数，接着在核空间的竞争学习过程中，对每一个新来的样本，不但使优胜者中心点所对应的行向量朝着该样本移动，并且使第二优胜者，即对手所对应的行向量朝着该样本反向移动。不断迭代，直至收敛为止。迭代结束之时，中心点描述子[W?]的某些行向量在核空间中距离所有的样本都非常远，即为冗余的中心点，这样便可以去除冗余中心点，实现核空间自动聚类个数估计的目的。

　　核竞争测度的引入，使复杂分布数据的结构特点得到较好的体现，对于现实世界中的聚类问题可以达到较好的效果。然而正如前文提到的，要用图论中的最短路径来计算流形距离，其计算复杂度要明显高于欧式距离的计算复杂度。随着数据集规模的增加，这个弊端尤为明显，就更无法应用于大规模聚类问题。对于一个数据集，如果我们只利用其中一部分样本点的信息就可以得出对整个数据集的正确聚类，势必会大大缩减计算量.我们发现，对于一个数据集，无论是超球体分布还是复杂结构，我们总能将其划分为若干类，使得每一类都是符合球形分布的简单子数据集。这一步可以通过选取合适的类数K，对数据集进行K-均值聚类轻易实现，而这些子数据集的聚类中心即可很好地代表整个数据集的分布特点，此时采用具有流形距离作为相似性测度的聚类算法来处理代表点集（即K-均值聚类中心集），即可获得符合数据分布结构的合理聚类结果.这样就可以达到降低计算量的目的。基于上面的思想，我们设计了如下的两阶段聚类算法。3分阶段非线性聚类方法

　　该算法首先采用基于K近邻图理论的能量方法构造出一个粗划分，然后再采用多中心点竞争学习算法对粗划分进一步处理产生精确的划分。该算法主要解决如下科学问题。顶点能量的计算，基于K近邻图理论的顶点能量计算决定了高能量样本的提取及粗划分的产生。研究计算顶点能量的一个关键是K近邻图中近邻个数即参数K的选取。顶点能量确定之后，就可以提取高能量样本及构建对应的K近邻图。多中心点竞争学习，多中心点竞争学习的主要目的是通过采用多个中心点表达一个类，同时通过竞争学习对这些中心点进行更新从而精确化由第一阶段产生的粗划分。这个问题的难点在于如何确定每个类的中心点个数及如何用竞争学习法则更新这些中心点。

　　本文拟考虑提出一个两阶段的算法。在第一阶段，首先采用K近邻图理论对原始数据计算顶点能量，然后提取50%高能量样本，再采用K近邻算法对该高能量样本做一个划分，从而得到一个仅仅考虑高能量样本的粗划分同时估计出聚类的个数，这一阶段的一个关键是顶点能量的计算。该文拟采用类似于密度的全局能量估计，实现对任意密度及形状分布的聚类的有效划分。即对每一个样本点，其顶点能量是由整个数据集合计算得到，而非由某一个近邻关系计算所得。第一阶段得到的粗划分仅仅考虑了高能量样本，为了对低能量样本进行类标赋值，同时得到精确化的聚类结果，在第二阶段拟采用多中心点竞争学习对该粗划分进行精确化处理，对粗划分中的每一个类，首先采用AP聚类算法求得最佳表达该类的多个中心点，所有类的这些多个中心点的集合我们称之为多中心点集合，然后用竞争学习算法更新这些多中心点集合。更新多中心点集合的关键步骤是：对于某个当前样本，选择一个离其最近的某个类的中心点，并使这个中心点朝着该样本移动某个学习步长，而该类的其他中心点及其他类的中心点保持不变。这样不断迭代，直至所有中心点保持不动，收敛为止。这样便使得低能量样本也赋值类标，从而实现对该粗划分的一个精确化处理，最终得到聚类结果。

　　第1阶段旨在根据全体样本点提供的信息，寻找若干符合球形分布的子数据集，并构造出一个较小的代表点集，这些代表点能够较为完整、准确地表现整个数据集的分布形状及结构特点。我们选择采用欧氏距离测度的改进K-均值算法作为第1阶段的选择手段，将得到的聚类中心作为数据集的代表点。对于数据集X={x1，…，xN}，期望聚为K类，我们先通过TPC的第1阶段将其聚为K′类，表示为C={C1，C2，…，CK′}，聚类中心为μ={μ1，μ2，…，μK′}，其中，K′>K。

　　对第1阶段得到的聚类中心μ={μ1，μ2，…，μk′}，我们在TPC的第2阶段使用MEC将其聚为K类。在设计基于进化计算的聚类算法时，最核心的两个问题就是进化个体的编码以及相似性度量。我们从组合优化的角度来考虑聚类问题，将指定类别数K的聚类问题建模为一个从数据集中选择K个典型样本来代表K个类别的优化问题，然后按照样本与K个典型样本的相似性对数据集进行类别划分。因此，每个个体代表一种典型样本序号的组合，显然，对于一个K类的聚类问题，一个个体的长度为K，第1个基因位为代表第1个类别的样本序号，第2个基因位为代表第2个类别的样本序号，依此类推，为了更加具体地说明这种新的个体表示方式。

　　该方法应用视频总结的聚类。如在图像分割应用中，传统线性可分聚类技术需要对图像的像素提取线性可分的特征，同时需要用户提供图像的感兴趣个体的个数；在视频聚类应用中，这类技术需要对视频的每一帧提取易划分的低维特征，同时需要提供视频中场景的个数，在大规模视频聚类实时处理中，这是两个聚类算法应用的瓶颈问题。该文所提出的同时具有自动初始化和非线性可分能力的分阶段聚类方法将有利于同时克服这两个问题，并在图像分析方面展示新的应用效果，在视频的关键帧选取任务中，聚类算法将视频的每一帧看成特征空间里面的一个样本点，假设该特征空间中的代表点集合（如聚类的中心点）可以当成整个视频序列的关键帧，则视频关键帧的选取问题就直接转化为聚类问题中的中心点选取问题。视频聚类类似于场景图片聚类，一段场景的视频段通常包含多个主题，但它通常强调实时性。该文应用上述已经提出的非线性竞争学习的快速聚类算法来研究它在视频聚类上的应用，实验显示该方法提高了视频分析效率。

　　4结束语

　　参考文献：

　　[1]金澈清，钱卫宁，周傲英.流数据分析和管理综述[J].软件学报，2004，15（8）：1172-1181.

　　[2]周晓云，孙志挥，张柏礼.高维数据流聚类及其演化分析研究[J].计算机研究与发展，200643（11）：2005-2011.

　　[3]张晨，金澈清，周傲英.一种不确定数据流聚类算法[J].软件学报，2010，21（9）：2173-2182.

　　[4]AggarwalCC，HanJ，WangJ.Aframeworkforprojectedclusteringofhighdimensionaldatastreams[M].Proceedingsofthe30thInternationalConferenceonVeryLargeDataBases，MorganKaufmann，Toronto，Canada，2004.

　　[5]GaoJ，LiJ，ZhangZ.Anincrementaldatastreamclusteringalgorithmbasedondenseunitsdetection[M].ProceedingsoftheNinthPacific-AsiaConferenceonAdvancesinKnowledgeDiscoveryandDataMining，LectureNotesinComputerScience，Springer，2005.

　　[6]CaoF，EsterM，QianW.Density-basedclusteringoveranevolvingdatastreamwithnoise[M].J.Ghosh，D.Lambert，D.B.Skillicorn，J.Srivastava（Eds.），ProceedingsoftheSixthSIAMInternationalConferenceonDataMining，SIAM，Bethesda，Maryland，USA，2006.