第8章-聚类

数据挖掘天津大学计算机科学与技术学院喻梅目录CONTENTS28.18.28.38.4聚类概述基于划分的聚类基于层次的聚类基于密度的聚类基于网格的聚类8.5Chapter8.1聚类概述48.1聚类的基本概念–什么是聚类分析？•聚类分析(clusteranalysis)简称聚类(clustering)，是一个把数据对象(或观测)划分成子集的过程。•每个子集是一个簇(cluster)，使得簇中的对象彼此相似，但与其他簇中的对象不相似。•由聚类分析产生的簇的集合称做一个聚类。•聚类分析已经广泛地用于许多应用领域，包括商务智能、图像模式识别、Web搜索、生物学和安全。58.1聚类的基本概念–数据挖掘对聚类的典型要求如下：•处理不同属性类型的能力:越来越多的应用需要对复杂数据类型进行聚类。•可伸缩性：在不同规模的数据集下表现稳定，聚类算法要具有高度可伸缩性。•对于确定输入参数的领域知识的要求：许多聚类算法都要求用户输人参数并且对参数十分敏感。•发现任意形状的簇：一个簇可能是任意形状的。68.1聚类的基本概念–数据挖掘对聚类的典型要求如下：•处理噪声数据的能力：一些聚类算法可能对噪声数据敏感。•增量聚类和对输入次序不敏感：在许多应用中,增量更新可能随时发生。一些聚类算法还可能对输入数据的次序敏感。•聚类高维数据的能力：数据集可能包含高维度数据或大量属性值。•基于约束的聚类：需要找到既满足特定的约束又具有良好聚类特性的数据分组。•可解释性和可用性：用户希望聚类结果是可解释的、可用的。78.1聚类的基本概念–聚类过程遵循的基本步骤：•特征选择：尽可能多地包含任务关心的信息•近邻测度：定量测定两特征如何“相似”或“不相似”•准则定义：以蕴含在数据集中类的类型为基础•算法调用：按近邻测度和聚类准则揭示数据集的聚类结构•结果验证：常用逼近检验验证聚类结果的正确性•结果判定：由专家用其他方法判定结果的正确性88.1聚类的基本概念–基本聚类方法概述：•基于划分的方法(partition-basedmethod):给定一个n个对象的集合,划分方法构建数据的k个分区,其中每个分区表示一个簇,并且k≤n。也就是说,它把数据划分为k个组,使得每个组至少包含一个对象。•基于层次的方法(hierarchical-basedmethod):层次方法创建给定数据对象集的层次分解。层次方法可以分为疑聚的或分裂的方法。层次方法的缺陷在于,一旦一个步骤(合并或分裂)完成,它就不能被撤销。•基于密度的方法(density-basedmethod):基于密度的方法定义邻域的半径范围，邻域内的对象数目超过某限定值则添加到簇中。基于密度的方法可以发现任意形状的簇。•基于网格的方法(grid-basedmethod):基于网格的方法把对象空间量化为有限个单元，形成一个网格结构。所有的聚类操作都在这个网格结构(即量化的空间)上进行。这种方法的主要优点是处理速度很快,其处理时间通常独立于数据对象的个数。Chapter8.2基于划分的聚类基于划分的聚类的形式化定义：给定n个数据对象的数据集D,以及要生成的簇数k,划分算法把数据对象组织成k(k≤n)个分区,其中每个分区代表一个簇。基于划分的聚类主要介绍K-均值算法和K-中心点算法。108.2基于划分的聚类−基本概念假设数据集D包含n个欧氏空间中的对象。划分方法把D中的对象分配到k个簇𝐶1,𝐶2,…,𝐶𝑘中,使得对于1≤i,j≤k,𝐶𝑖∈𝐷且𝐶𝑖∩𝐶𝑗=∅。使得数据集中所有对象的误差的平方和E最小。𝐸=𝑑(𝑜,𝑐𝑖)2𝑜𝜖𝐶𝑖𝑘𝑖=1其中，Ci为第i个簇，o为簇Ci中的对象，ci为簇Ci的质心，是簇Ci中所有对象的平均值，如公式(8-2)所示。𝑐𝑖=1|𝐶𝑖|𝑜𝑜∈𝐶𝑖(8-2)式中，|𝐶𝑖|是簇𝐶𝑖中的对象个数。118.2基于划分的聚类1.k-均值算法−k-均值算法的基本过程：①首先输入k的值，即具有n个对象的数据集𝐷={𝑜1,𝑜2,…,𝑜𝑛}经过聚类将得到k个分类或分组。②从数据集D中随机选择k个对象作为簇质心，每个簇质心代表一个簇，得到的簇质心集合为𝐶𝑒𝑛𝑡𝑟𝑜𝑖𝑑={𝑐1,𝑐2,…,𝑐𝑘}。③对D中每一个对象𝑜𝑖，计算𝑜𝑖与𝑐𝑖(𝑖=1,2,…,𝑘)的距离，得到一组距离值，选择最小距离值对应的簇质心𝐶𝑠，则将对象𝑜𝑖划分到以𝐶𝑠为质心的簇中。④根据每个簇所包含的对象集合，重新计算簇中所有对象的平均值得到一个新的簇质心，返回步骤③，直到簇质心不再变化。128.2基于划分的聚类1.k-均值算法例8-1使用k-均值算法进行聚类数据对象集合D如表8-2所示，作为一个聚类分析的二维样本，要求的簇的数量k=2。138.2基于划分的聚类数据对象𝑜1𝑜2𝑜3𝑜4𝑜5x001.555y20002表8-2数据集数据分布如图8-1所示。o1o3o4o5o2图8-1数据分布图1.k-均值算法解：①任意选择𝑜1(0,2)，𝑜2(0,0)为簇𝐶1和𝐶2初始的簇质心，即𝑐1=𝑜1=(0,2)，𝑐2=𝑜2=(0,0)。②对剩余的每个对象，根据其与各个簇质心的距离，将它赋给最近的簇。𝑜3：𝑑(𝑐1,𝑜3)=0−1.52+2−02=2.5𝑑(𝑐2,𝑜3)=0−1.52+0−02=1.5显然，𝑑(𝑐1,𝑜3)𝑑(𝑐2,𝑜3),故将𝑜3分配给𝐶2。𝑜4：𝑑𝑐1,𝑜4=0−52+2−02=29𝑑(𝑐2,𝑜4)=0−52+0−02=5显然，𝑑(𝑐1,𝑜4)𝑑(𝑐2,𝑜4)，故将𝑜4分配给C2。𝑜5：𝑑𝑐1,𝑜5=0−52+2−22=5𝑑𝑐2,𝑜5=0−52+0−22=29显然，𝑑𝑐1,𝑜5𝑑(𝑐2,𝑜5),故将𝑜5分配给𝐶1。更新，得到两个簇：𝐶1={𝑜1,𝑜5},𝐶2={𝑜2,𝑜3,𝑜4}148.2基于划分的聚类1.k-均值算法计算每个簇的平方误差准则:𝐸1=(0−0)2+(2−2)2+(5−0)2+(2−2)2=25𝐸2=0−02+0−02+1.5−02+0−02+5−02+0−02=27.25𝐸=𝐸1+𝐸2=25+27.25=52.25形成的两个簇如图8-2所示。158.2基于划分的聚类c1c2o1o3o4o5o2xY图8-2初始簇划分1.k-均值算法③计算新簇质心𝑐1=0+52,2+22=(2.5,2)𝑐2=0+1.5+53,0+0+03=(2.17,0)④重复②，对每个对象，根据其与各个簇新质心的距离，将它赋给最近的簇。𝑜1：𝑑(𝑐1,𝑜1)=2.5−02+2−22=2.5𝑑(𝑐2,𝑜1)=2.17−02+0−22=2.95显然，𝑑𝑐1,𝑜1𝑑(𝑐2,𝑜1),故将𝑜1分配给𝐶1。𝑜2：𝑑(𝑐1,𝑜2)=2.5−02+2−02=3.20𝑑(𝑐2,𝑜2)=2.17−02+0−02=2.17显然，𝑑(𝑐1,𝑜2)𝑑(𝑐2,𝑜2),故将𝑜2分配给𝐶2。𝑜3：𝑑(𝑐1,𝑜3)=2.5−1.52+2−02=2.24𝑑(𝑐2,𝑜3)=2.17−1.52+0−02=0.67显然，𝑑(𝑐1,𝑜3)𝑑(𝑐2,𝑜3),故将𝑜3分配给𝐶2。𝑜4：𝑑𝑐1,𝑜4=2.5−52+2−02=3.20𝑑(𝑐2,𝑜4)=2.17−52+0−02=2.83显然，𝑑(𝑐1,𝑜4)𝑑(𝑐2,𝑜4)，故将𝑜4分配给C2。𝑜5：𝑑𝑐1,𝑜5=2.5−52+2−22=2.5𝑑𝑐2,𝑜5=2.17−52+0−22=3.47显然，𝑑𝑐1,𝑜5𝑑(𝑐2,𝑜5),故将𝑜5分配给𝐶1。更新，得到两个新簇：𝐶1={𝑜1,𝑜5},𝐶2={𝑜2,𝑜3,𝑜4}168.2基于划分的聚类1.k-均值算法计算每个簇的平方误差准则:𝐸1=(0−2.5)2+(2−2)2+(5−2.5)2+(2−2)2=12.5𝐸2=0−2.172+0−02+1.5−2.172+0−02+5−2.172+0−02=13.17𝐸=𝐸1+𝐸2=12.5+13.17=25.67形成的两个簇如图8-3所示。178.2基于划分的聚类c1c2o2o1o3o4o5Y图8-3更新簇划分1.k-均值算法K-均值算法的优点：①擅长处理球状分布的数据，当结果聚类是密集的，而且类和类之间的区别比较明显时，k-均值聚类算法的效果比较好。②对于处理大数据集，是相对可伸缩的和高效的，它的复杂度是O(nkt),n是对象的个数，k是簇的数目，t是迭代的次数。③相比其他的聚类算法，k-均值聚类算法比较简单、容易掌握。188.2基于划分的聚类1.k-均值算法K-均值算法的缺点：①初始质心的选择与算法的运行效率密切相关②要求用户事先给定簇数k③对噪声和离群点敏感，少量的这类数据对结果产生很大影响198.2基于划分的聚类1.k-均值算法2.k-中心点（PAM）算法−基本概念k-中心点（k-Medoids）算法不采用簇中对象的平均值作为参照点，而是选用簇中位置最中心的对象，即中心点作为簇的代表对象，以降低k-均值算法对离群点数据敏感性。PAM（PartitioningAroundMedoids）算法是最早提出的k-中心点算法之一。该算法首先为每个簇随意选择一个代表对象，剩余的对象根据其与代表对象的距离分配给最近的一个簇，然后反复地用非代表对象来替代代表对象，以改进聚类的质量。208.2基于划分的聚类为了判定一个非代表对象𝑜𝑗是否是当前一个代表对象𝑚𝑖的好的替代，对于每一个非代表对象𝑝，考虑下面的四种情况：①𝑝当前隶属于代表对象𝑚𝑖所代表的聚类，如果𝑚𝑖被𝑜𝑗所代替，且𝑝离𝑜𝑖最近，𝑖与𝑗不等，那么𝑝被重新分配给𝑜𝑖所在的聚簇；②𝑝当前隶属于代表对象𝑚𝑖所代表的聚类，如果𝑚𝑖被𝑜𝑗所代替，且𝑝离𝑜𝑗最近，那么𝑝被重新分配给𝑜𝑗所在的聚簇；③𝑝当前隶属于代表对象𝑚𝑗所代表的聚类，且𝑖与𝑗不等，如果𝑚𝑖被𝑜𝑗所代替，且𝑝离𝑜𝑖最近，那么对象的隶属不发生变化；④𝑝当前隶属于代表对象𝑚𝑗所代表的聚类，且𝑖与𝑗不等，如果𝑚𝑖被𝑜𝑗所代替，且𝑝离𝑜𝑗最近，那么𝑝被重新分配给𝑜𝑗所在的聚簇。218.2基于划分的聚类2.k-中心点（PAM）算法−k-中心点算法的基本过程：①从n个数据对象任意选择k个对象作为初始聚类中心代表；②计算其余各对象与这些中心对象间的距离，并根据最小距离原则将各对象分配到离它最近的聚类中心所在的簇中；③任意选择一个非中心对象𝑜𝑗，计算其与中心对象𝑚𝑖交换的总代价𝑇𝐶𝑖𝑗；④若𝑇𝐶𝑖𝑗为负值，则交换𝑜𝑗与𝑚𝑖以构成新聚类的k个中心对象。⑤循环②到④直到每个聚类不再发生变化为止。228.2基于划分的聚类2.k-中心点（PAM）算法𝑇𝐶𝑖𝑗表示中心点𝑚𝑖被非中心点𝑜𝑗替换后的总代价，由每一个对象的替换代价组成，计算公式如(8-3)所示。𝑇𝐶𝑖𝑗=𝑆𝑖𝑗𝑘𝑛𝑘=1(8-3)其中，𝑆𝑖𝑗𝑘为中心点𝑚𝑖被非中心点𝑜𝑗替换后对象𝑜𝑘的替换代价。假设对象𝑜𝑘原先属于中心点𝑚𝑠所代表的簇，替换中心点后属于中心点𝑚𝑡所代表的簇，则替换成本𝑆𝑖𝑗𝑘计算公式如(8-4)所示。𝑆𝑖𝑗𝑘=𝑑𝑝,𝑚𝑡−𝑑𝑝,𝑚𝑠(8-4)238.2基于划分的聚类2.k-中心点（PAM）算法例8-2使用PAM算法进行聚类数据对象集合D如表8-2所示，作为一个聚类分析的二维样本，要求的簇的数量k=2。248.2基于划分的聚类数据对象𝑜1𝑜2𝑜3𝑜4𝑜5x001.555y20002表8-2数据集数据分布如图8-1所示。o1