第10章-聚类方法

第10章聚类方法10.1聚类概述10.2基于划分的聚类算法10.3基于层次的聚类算法10.4基于密度的聚类算法10.5基于网格的聚类算法10.6基于模型的聚类算法10.7离群点分析分类和聚类是两个容易混淆的概念，事实上它们具有显著区别。在分类中，为了建立分类模型而分析的数据对象的类别是已知的，然而，在聚类时处理的所有数据对象的类别都是未知的。因此，分类是有指导的，是通过例子（训练样本集）学习的过程，而聚类是无指导的，是通过观察学习的过程。10.1.1什么是聚类聚类是将数据对象的集合分成相似的对象类的过程。使得同一个簇（或类）中的对象之间具有较高的相似性，而不同簇中的对象具有较高的相异性。定义10.1聚类可形式描述为：D={o1，o2，…，on}表示n个对象的集合，oi表示第i（i=1，2，…，n）个对象，Cx表示第x（x=1，2，…，k）个簇，CxD。用sim(oi，oj)表示对象oi与对象oj之间的相似度。若各簇Cx是刚性聚类结果，则各Cx需满足如下条件：其中，条件①和②表示所有Cx是D的一个划分，条件③表示簇内任何对象的相似度均大于簇间任何对象的相似度。聚类簇1簇2簇3（a）原来的点（b）3个簇10.1.2相似性测度1.距离相似性度量曼哈坦距离mkjkikjioooodist1||),(欧几里得距离mkjkikjijioooooodist12)(),(闵可夫斯基距离qmkqjkikjioooodist1||),(通常相似度与距离成反比，在确定好距离函数后，可设计相似度函数如下：),(11),(jijioodistooSim2.密度相似性度量密度是单位区域内的对象个数。密度相似性度量定义为：density(Ci，Cj)=|di－dj|其中di、dj表示簇Ci、Cj的密度。其值越小，表示密度越相近，Ci、Cj相似性越高。这样情况下，簇是对象的稠密区域，被低密度的区域环绕。3.连通性相似性度量数据集用图表示，图中结点是对象，而边代表对象之间的联系，这种情况下可以使用连通性相似性，将簇定义为图的连通分支，即图中互相连通但不与组外对象连通的对象组。也就是说，在同一连通分支中的对象之间的相似性度量大于不同连通分支之间对象的相似性度量。某种距离函数4.概念相似性度量若聚类方法是基于对象具有的概念，则需要采用概念相似性度量，共同性质（比如最近邻）越多的对象越相似。簇定义为有某种共同性质的对象的集合。狗鸡猫苹果葡萄语义上的相似性10.1.3聚类过程数据准备属性选择属性提取某种聚类算法结果评估训练样本输入分类算法分类模型测试样本输入新样本学习阶段分类阶段10.1.4聚类算法的评价一个好的聚类算法产生高质量的簇，即高的簇内相似度和低的簇间相似度。通常估聚类结果质量的准则有内部质量评价准则和外部质量评价准则。1.内部质量评价准则例如，CH指标的定义如下：)/()1/()(kntraceWktraceBkCH其中：kiiizzdistntraceB12)(kiCoiizodisttraceW12)(niionz11traceB表示簇间距离，traceW表示簇内距离，CH值越大，则聚类效果越好。为整个数据集的均值为簇Ci的均值nCoiiionz1【例10.1】如图10.2（a）所示的数据集有图10.2（b）、（c）、（d）三种聚类结果，这里n=16，距离函数采用欧几里得距离。采用CH指标判断聚类结果的好坏。CH=5.39CH=6.25625CH=3.962.外部质量评价准则常用的外部质量评价指标有聚类熵等。对于簇Ci，其聚类熵定义为：)(log)(21iijsjiijinnnnCE整体聚类熵定义为所有聚类熵的加权平均值：kiiiCEnnE1)(1显然，E越小，聚类效果也越好，反之亦然。E＝0E＝0.58例如(P274)：10.1.5聚类方法的分类按照聚类的尺度，聚类方法可被分为以下三种：基于距离的聚类算法：用各式各样的距离来衡量数据对象之间的相似度。基于密度的聚类算法：相对于基于距离的聚类算法，基于密度的聚类方法主要是依据合适的密度函数等。基于互连性的聚类算法：通常基于图或超图模型。高度连通的对象聚为一类。按照聚类分析方法的主要思路，可以被归纳为如下几种。划分法：基于一定标准构建数据的划分。层次法：对给定数据对象集合进行层次的分解。密度法：基于数据对象的相连密度评价。网格法：将数据空间划分成为有限个单元的网格结构，基于网格结构进行聚类。模型法：给每一个簇假定一个模型，然后去寻找能够很好的满足这个模型的数据集。10.1.6聚类分析在数据挖掘中的应用①聚类分析可以用于数据预处理。②可以作为一个独立的工具来获得数据的分布情况。③聚类分析可以完成孤立点挖掘。10.1.7聚类算法的要求①可伸缩性。②具有处理不同类型属性的能力。③能够发现任意形状的聚类。④需要（由用户）决定的输入参数最少。⑤具有处理噪声数据的能力。⑥对输入记录顺序不敏感。⑦具有处理高维数据的能力。⑧支持基于约束的聚类。⑨聚类结果具有好的可解释性和可用性。划分聚类算法预先指定聚类数目或聚类中心，通过反复迭代运算，逐步优化目标函数的值，当目标函数收敛时，得到最终聚类结果。划分后每个类中的数据点到该类中心的距离最小10.2.1k-均值算法k-均值（k-means）算法的基本过程如下：①首先，即希望将数据集D={o1，o2，…，on}经过聚类得到k个分类或分组。②从数据集D中k个数据点作为，每个簇质心代表一个簇。这样得到的簇质心集合为Centroid={Cp1，Cp2，…，Cpk}。③对D中每一个数据点oi，计算oi与Cpj（j=1，2，…，k）的距离，得到一组距离值，从中找出对应的簇质心Cps，则将数据点oi划分到以Cps为质心的簇中。1.k-均值算法的过程④根据每个簇所包含的对象集合，。若|Cx|是第x个簇Cx中的对象个数，mx是这些对象的质心，即：xCoxxoCm||1⑤如果这样划分后满足目标函数的要求，可以认为聚类已经达到期望的结果，算法终止。否则需要迭代③~⑤步骤。通常目标函数设定为所有簇中各个对象与均值间的误差平方和（SumoftheSquaredError，简称SSE）小于某个阈值ε，即：kxCoxxmoSSE12||这里的簇质心mx是簇Cx的均值，这就是k-均值算法名称的由来。k-均值算法示例【例10.3】如图10.4所示是二维空间中的10个数据点（数据对象集），采用欧几里得距离，进行2-均值聚类。其过程如下：初始的10个点（1）k=2，随机选择两个点作为质心，假设选取的质心在图中用实心圆点表示。（2）第一次迭代，将所有点按到质心的距离进行划分，其结果如图10.5所示。第1次迭代（3）假设这样划分后不满足目标函数的要求，重新计算质心，如图10.6所示，得到两个新的质心。求新的质心第2次迭代（4）第2次迭代，其结果如图10.7所示。（5）假设这样划分后满足目标函数的要求，则算法结束，第2次划分的结果即为所求；否则还需要继续迭代。序号属性1属性2111221312422根据所给的数据通过对其实施k均值算法（设n=8，k=2），其主要执行执行步骤：第1次迭代：假定随机选择的两个对象，如序号1和序号3当作初始点，分别找到离两点最近的对象，并产生两个簇{1，2}和{3，4，5，6，7，8}。对于产生的簇分别计算平均值，得到平均值点：示例：样本数据序号属性1属性2543653744854对于{1，2}，平均值点为（1.5，1）（这里的平均值是简单的相加除2）；对于{3，4，5，6，7，8}，平均值点为（3.5，3）。本题采用欧几里得距离第2次迭代：通过平均值调整对象的所在的簇，重新聚类，即将所有点按离平均值点（1.5，1）、（3.5，1）最近的原则重新分配。得到两个新的簇：{1，2，3，4}和{5，6，7，8}。重新计算簇平均值点，得到新的平均值点为（1.5，1.5）和（4.5，3.5）。第3次迭代：将所有点按离平均值点（1.5，1.5）和（4.5，3.5）最近的原则重新分配，调整对象，簇仍然为{1，2，3，4}和{5，6，7，8}，发现没有出现重新分配，而且准则函数收敛，程序结束。2.k-均值算法输入：数据对象集合D，簇数目k，阈值ε输出：k个簇的集合方法：其过程描述如下：从D中随机选取k个不同的数据对象作为k个簇C1、C2、…、Ck的中心m1、m2、…、mk;while(true){for(D中每个数据对象o){求i，使得;将o分配到簇Ci中;}for(每个簇Ci)计算//计算新的质心，|Ci|为簇Ci中的对象数目计算误差平方和if(SSE≤ε)break;//满足条件，退出循环})}(tan{argjjoocedisMINi||iCoiComikxCoxxmoSSE12||优点复杂度：O(tkn)，其中n是对象的数目，k是簇的数目，t是迭代的次数。通常k、tn。通常以局部最优结束。使用遗传算法技术可以达到全球最优。缺点只有在簇的平均值被定义的情况下才能使用，那当涉及有分类属性的数据时该怎么办?需要事先给出k，即簇的数目不能处理噪声数据和孤立点不适合发现非凸面形状的簇3.k-均值算法的特点5.二分k-均值算法二分k-均值算法是基本k-均值算法的直接扩充，它基于一种简单的想法：为了得到k个簇，将所有点的集合分为两个簇，从这些簇中选取一个继续分裂，如此下去，直到产生k个簇。二分k-均值算法如下：输入：数据对象集合D，簇数目k，二分次数b输出：k个簇的集合方法：其过程描述如下：将D的所有对象构成一个簇C1，将其加入到簇表S中，即S={C1};do{从簇表S中取出一个簇Ci;for(j=1tob)使用基本k-均值算法，二分簇Ci，得到一对子簇Ci1、Ci2;从上述得到的b对子簇中选择具有最小SSE的一对子簇，将其加入S中;}until簇表S中包含k个簇;10.2.2k-中心点算法改进的方法是不采用簇中对象的均值作为质心，而是在每个簇中选出一个实际的对象来代表该簇，这个对象称为簇的中心点，其余的每个对象聚类到与其最相似的中心点所在簇中。划分方法仍然基于最小化所有对象与其对应的中心点之间的距离之和的原则来执行。目标函数（或误差函数）使用绝对误差标准，其定义如下：kxCoxxooE1||其中，E是数据集D中所有对象的绝对误差和。ox是簇Cx的中心点。PAM是最早提出的k-中心点算法之一。PAM算法的过程如下：①任意选择k个对象作为k个中心点。②计算每个非中心点对象到每个中心点的距离。③把每个非中心点对象分配到距离它最近的中心点所代表的簇中。④随机选择一个非中心点对象oi，计算用oi代替某个簇Cx的中之点ox所能带来的好处（用△E表示代替后和代替前误差函数值之差，意思是使误差E增加多少）。⑤若△E0，表示代替后误差会减少，则用oi代替ox，即将oi作为簇Cx的中心点；否则，不代替。⑥重复②～④，直到k个中心点不再发生改变。【例10.4】有9个人的年龄分别是1、2、6、7、8、10、15、17、20，采用PAM算法将年龄分为3组。其过程如下：（1）随机选取3个年龄作为中心点，假设是6、7、8。（2）计算每个年龄和这3个中心点的距离后，将年龄分为3组：{1，2，6}，{7}，{8，10，15，17，20}，对应的E=5+4+0+0+0+2+7+9+12=39。（3）假设随机选取年龄10，用它代替中心点6，即新的3个中心点为10、7、8，这样产生的分组为{1，2，6，7}，{8}，{10，15，17，20}，对应的E'=6+5+1+0+0+0+5+7+10=34。△E=E'-E=34-39=-50，则用10代替中心点6，新的E=34。（4）再随机选取年龄17，用它代替中心点7，即新的3个中心点为10、17、8，这样产生的分组为{1，2，6，7，8}，{10}，{15，17，20}，对应的E'=7+6+2+1+0+0+2+0+3=21。△E=E'