两步聚类方法

两步聚类方法张伟徐远（北京科技大学经济管理学院，北京100083）摘要：k-means算法一个很大的缺点是不能消除异常值对聚类结果的影响，而层次聚类方法和基于密度的聚类方法都能够很好的找出异常值。本文提出一种两步聚类方法，先用基于密度的聚类方法找出异常值，再用k-means算法进行聚类，其中k值可以参考第一步聚类结果来确定。文章最后给出了实例分析，对比聚类效果。关键词：k-means；密度聚类；两步聚类；异常值Two-StepClusteringMethodZhangWei,XuYuan(SchoolofEconomics&Management,UniversityofScience&Technology,Beijing,Beijing,100083)Abstract:Intheclusteringprocess,exceptionalpointscan’tbefoundbyusingk-meansalgorithmsbutbyusinghierarchicalclusteringmethodordensity-basedclusteringmethod.So,inthisarticle,weputforwardamethodcalled“Two-stepClusteringMethod”.Firstwecanfindexceptionalpointsbyusingdensity-basedmethod;thenweusek-meansalgorithmstocluster.Intheendofthisarticle,anexampleisgiven.KeyWords:K-means;Density-basedClustering;Two-stepClustering;ExceptionalPoints1.引言聚类算法可以归为分割聚类方法（PartitioningClusteringMethod）、层次聚类方法（HierarchicalClusteringMethod）、基于密度的聚类方法（Density-BasedClusteringMethod）和基于网格的聚类方法（Grid-BasedClusteringMethod）。每一种方法都有自己的优点和缺点，本文尝试将分割聚类方法中的k-means算法与聚结型层次聚类的基本算法或基于密度的聚类方法相结合，提出一种两步聚类方法，发挥聚类方法各自的特长，弥补k-means算法的不足。2.k-means算法2.1分割聚类算法分割聚类方法是一种基于原型的聚类方法，其本质是首先从数据集中随机地选择几个对象作为聚类的原型，然后将其他对象分别分配到由原型所代表的最相似，也就是距离最近的类中。分割聚类方法通过迭代控制策略对原型不断地进行调整，从而使得整个聚类得到优化。根据所采用的原型的不同，分割聚类方法主要包括k-means和k-medoid两大类算法。这里主要介绍k-means算法。2.2k-means算法的步骤k-means算法是以平均值作为类的“中心”的一种分割聚类方法。假设有n个对象，将其分成k个类。其中，分成的聚类的个数k是采用k-means算法必须预先指定的参数。聚类的过程有以下步骤：（1）随机地选择k个对象，每一个对437象作为一个类的“中心”，分别代表将要分成的k个类；（2）根据距离“中心”最近的原则，寻找与个对象最为相似的类，将其他对象分配到各个相应的类中；（3）在完成对象的分配之后，针对每一个类，计算其所有对象的平均值，作为该类的新的“中心”；（4）根据距离“中心”最近的原则，重新进行所有对象到各个相应类的分配；（5）返回步骤（3），直到没有变化为止。2.3k-means算法的特点k-means算法的优点是：（1）可以应用于数据量比较大的情况[1]；（2）简单直观，易于理解和操作，便于并行处理，对数据的处理次序不敏感[2]；但是，k-means算法的缺点也是比较明显的[1,2]：（1）仅能处理数字属性；（2）需要预置“中心”且该操作对结果有明显影响；（3）需要预知类的数目k，这在实际应用中往往很难做到；（4）由于该方法采用一个类中所有对象的平均值作为该类的“中心”，因此聚类的结果会受到异常值的影响，抗干扰性较差；（5）算法扩展性较差；（6）只能得到次优解；（7）在预置操作最坏的情况下可能出现空类（该类中没有样本）；（8）只适用于形状为凸形的聚类，不能处理非凸形的聚类；3.聚结型层次聚类算法3.1层次聚类方法概述层次聚类方法是采用“自顶向下”或“自底向上”的方法在不同的层次上对对象进行分组，形成一种树形的聚类结构。如果采用“自顶向下”的方法，则成为分解型层次聚类法；如果采用“自底向上”的方法，则成为聚结型层次聚类法。层次聚类方法同分割聚类方法的不同之处在于：对于分割聚类方法而言，一般需要一种迭代控制策略，使得整个聚类得到油画；而层次聚类方法并不是试图寻找最佳的聚类结果，而是按照一定的相似性判断标准，合并最相似的部分，或者分割最不相似的两个部分。如果合并最相似的部分，那么从每一个对象作为一个类开始，逐层向上进行聚结，直到形成唯一的一个类；如果分割最不相似的两个部分，那么从所有的对象归属在唯一的一个类中开始，逐层向下分解，直到每一个对象形成一类。3.2聚结型层次聚类算法的基本思想聚结型层次聚类算法采用“自底向上”的方法，首先将每一个对象独立地作为一个类，然后根据各个类之间的相似程度逐层向上聚结，形成越来越大的类，在满足一定的聚结终止条件时终止聚结，。iC和jC是聚结过程中同一层次上的两个类,in和jn分别是iC和jC两个类的对象数目,()ip为iC中的任意一个对象,()jp为jC中的任意一个对象,if为iC中对象的平均值,jf为jC中对象的平均值。3.3聚结型层次聚类算法的特点该算法的优点是能够找出异常值，不足之处是聚类结果受各个类形状、大小的影响，并且时间复杂度较大，为O(n2)，n为对象个数。4.DBSCAN算法及其特点4.1基于密度的聚类方法概述基于密度的聚类方法是以局部数据特征作为聚类的判断标准，类被看作是一个数据区域，在该区域内对象是密集的，对象稀438疏的区域将各个类分隔开来。多数基于密度的聚类算法形成的聚类形状是可以任意的，并且一个类种对象的分布也可以是任意的。4.2DBSCAN算法DBSCAN算法的主要思想为：如果一个对象在其半径为ε的邻域内包含至少MinPts个对象，那么该区域是密集的。为了确定这样的密集区域，该算法涉及有关密度的一系列定义，从而根据这些定义来确定密集区域，也就是确定各个类，并隔离出异常值。这些定义包括：定义1ε-邻域：对于一个给定的对象，其半径为ε的邻域成为该对象的ε-邻域。定义2核心对象：对于一个对象，如果在其ε-邻域内至少包含MinPts个对象，那么该对象成为核心对象。定义3直接密度可达：在给定的对象集D中，对于参数ε和MinPts，如果q是一个核心对象，对象p在q的ε-邻域内，那么称对象p从对象q是直接密度可达的。定义4密度可达：在给定的对象集D中，对于参数ε和MinPts，如果存在着对象p1，p2，…，pn，p1=q，pn=p，对于每一个i∈{1，2，…，n-1}，对象pi+1从对象pi是直接密度可达的，那么称对象p从q是密度可达的。定义5密度相连：在给定的对象集D中，对于参数ε和MinPts，如果对象p和对象q都是从对象o密度可达的，那么称对象p和对象q是密度相连的。定义6类与噪声：在给定的对象集D中，对于参数ε和MinPts，一个类C是满足下面两个条件之一的D的非空子集：（1）对于任意的p,q∈D，如果q∈C，并且p是从q密度可达的，那么p∈C；（2）对于任意的p,q∈C，p和q是密度相连的。不属于任何一个类的对象被认为是噪声。该算法聚类过程通过收集直接密度可达的对象来完成，步骤如下：（1）针对待聚类的对象集中的每一个对象p，检查其ε-邻域内是否至少包含MinPts个对象，也就是确定对象p是否为核心对象。如果p是核心对象，那么就创建一个初始的类C，C中包含对象p及从p直接密度可达的所有对象，也就是包含对象p及其ε-邻域内的所有对象。（2）确定该邻域中的每一个对象q是否为核心对象。如果是核心对象，那么就将其ε-邻域内尚未包含在类C中的所有对象追加到类C中，并继续确定这些新追加的对象是否为核心对象，如果是，则继续进行上述的对象追加过程。这一过程一直持续到没有新的对象可以追加到类C中为止，类C就完全确定下来了。4.3DBSCAN算法的特点（1）形成的聚类形状可以是任意的，并且不受异常值的影响，能够找出异常值。（2）算法的计算复杂度为O(n2)，在采用索引的情况下可以达到O(nlogn)，其中n是对象的总数。该算法的缺点是要求预先确定两个参数ε和MinPts，并且对这两个参数非常敏感，而合理确定这两个参数却又是比较困难的。5.二步聚类方法5.1二步聚类方法的思路前面介绍的三种聚类方法各有优缺点，层次聚类方法和DBSCAN算法能够找出对象集中的异常值这一优点正好能够弥补k-means算法受异常值影响的缺点。于是，本文提出一种二步聚类方法，具体思路如下：（1）采用层次聚类方法或DBSCAN算法对待聚类对象集D进行聚类，得到初始聚类结果，找出异常值；（2）从待聚类的对象集D中将找到的异常值排除出去，得到待聚类对象子集D1；（3）采用k-means算法对D1进行聚类，得到只含对象集D1的聚类结果，再将异常值单独作为一类，获得最终聚类结果。5.2二步聚类方法聚类效果实例分析4395.2.1二步聚类方法聚类效果我们选取某钢厂1号高炉10段横截面上5个温度检测点某一时刻的温度作为一个数据对象。这样，在某段时间内50个时刻的历史数据就构成了待聚类数据对象集D。我们将这50条数据存储于Access数据库中，编写了可对这些数据采用k-means算法和DBSCAN算法进行聚类的程序。(1)采用相关系数进行差异度的计算，取ε=0.9，MinPts=1，采用DBSCAN算法对这50个对象进行聚类，结果共聚6类，其中有3个异常类，见图1至图3，这3个类都分别只有一条数据，这三条数据是异常值。(2)将异常值的两条记录从数据库中排除出去，形成新的待聚类对象集D1。(3)参考第一步聚类的结果，排除异常值，可以取k=4，采用k-means算法对待聚类对象集D1进行聚类，结果见图4至图7，其中采用相关系数进行差异度的计算。聚类结果各类的平均值见表1。从图4到图7可见，各类中对象集中,而类与类之间区别也较大,所以聚类效果不错。再将异常值的3类加进来，共7类，作为最终聚类结果。下面我们再来看看直接采用k-means算法进行聚类的结果。图1DBSCAN算法得到异常值（1）图2DBSCAN算法得到异常值（2）图3DBSCAN算法得到异常值（3）图4第二步聚类结果(1)图5第二步聚类结果(2)图6第二步聚类结果(3)图7第二步聚类结果(4)440表1二步聚类结果各类的平均值点类12345173.87654.76943.35353.25760.933268.04143.74362.56052.36749.944357.31853.26452.52250.88549.210458.43754.34253.19852.84550.8135.2.2直接采用k-means算法的聚类结果我们同样选用刚才的50条数据记录作为待聚类的对象，取k=4，相关系数进行差异度的计算，直接采用k-means算法进行聚类，结果如图8至图11，各类平均值见表2。由图8和图9可见，第1类和第2类中的对象不够集中，没有消除异常值的影响，聚类效果不理想。将图4至图7与图8至图11进行对比，可以看出前面我们采用二步聚类方法获得的聚类结果明显优于直接采用k-means算法得到的聚类结果，很好地排除了异常值对聚类结果的影响。图8k-means结果(1)图9k-means结果(2)图10k-means结果(3)图11k-means结果(4)表2k-means聚类结果各类的平均值点类12345152.25152.6