聚类分析(第六章)

聚类分析什么是聚类分析聚类:是一个数据集将数据集划分为若干组（class）或类（cluster）的过程，并使得同一个组内的数据对象具有较高的相似度；而不同组中的数据对象是不相似的。聚类分析将一组（set）物理的或抽象的对象，根据它们之间的相似程度，分为若干组（group）；聚类是一种无监督的分类方法：不能事先定义类典型的应用作为一个调度的工具获得数据分布作为其他算法的一个组成部分聚类的典型应用分类是人类认识世界的方式，也是管理世界的有效手段。在科学研究中非常重要，许多科学的研究都是从分类研究出发的。没有分类就没有效率；没有分类，这个世界就没有秩序。瑞典博物学家林奈（CarlvonLinnaeus,1707-1778）因为对植物的分类成就被后人誉为“分类学之父”，后人评价说“上帝创世，林奈分类”——能与上帝的名字并列的人不多，另一个著名的科学家是牛顿。由此可见分类成果的重要性。最初分类都是定性了，后来随着科学的发展产生了定量分类技术，包括基于统计学的聚类方法和基于模糊数学的聚类技巧。在生物学中，将生物划分为：界，门，纲，目，科，属，种。例如白菜（种）属于油菜属、十字花科、十字花目、双子叶植物纲、被子植物亚门、种子植物门、植物界；老虎（种）则属于猫属、猫科、食肉目、哺乳动物纲、脊椎动物亚门、脊索动物门、动物界。这样，整个世界的生物就可以建立一个等级谱系，根据这个谱系，我们可以比较容易地判断那些生物已经认识了，哪些生物尚未发现，哪些生物已经灭绝了。表1各种生物在分类学上的位置举例位置白菜虎界植物界动物界门种子植物门脊索动物门亚门被子植物亚门脊椎动物亚门纲双子叶植物纲哺乳动物纲目十字花目食肉目科十字花科猫科属油菜属猫属种白菜虎如果发现了新的生物，就可以方便地将其归类。在天文学中，天体可以根据视觉区域分类，也可以根据发光性质与光谱特征进行分类。在地理学中，城市既可以根据地域空间分类，也可以根据城市的职能进行分类。饮料数据（drink.sav）16种饮料的热量、咖啡因、钠及价格四种变量例对10位应聘者做智能检验。3项指标X，Y和Z分别表示数学推理能力，空间想象能力和语言理解能力。其得分如下，选择合适的统计方法对应聘者进行分类。应聘者12345678910X28181121262016142422Y29232223292322232927Z28181622262222242424§1什么是聚类分析我们直观地来看，这个分类是否合理？计算4号和6号得分的离差平方和：(21-20)2+(23-23)2+(22-22)2=1计算1号和2号得分的离差平方和：(28-18)2+(29-23)2+(28-18)2=236计算1号和3号得分的离差平方和为482，由此可见一般，分类可能是合理的，欧氏距离很大的应聘者没有被聚在一起。由此，我们的问题是如何来选择样品间相似的测度指标，如何将有相似性的类连接起来？思考：样本点之间按什么刻画相似程度思考：样本点和小类之间按什么刻画相似程度思考：小类与小类之间按什么来刻画相似程度早期的分类，一般根据事物的属性与特征进行划分，属于定性分类的范畴。随着人们认识的深入和研究对象复杂程度的增加，单纯的定性分类方法就不能满足要求了，于是产生了定量分类技术，即所谓数字分类。根据分类对象的不同，聚类分析又可以分为两类：一是在变量空间中根据变量特征或者指标性质对样本进行分类，这叫做Q型聚类分析；二是在样本空间中根据变量在样本上的观测值对变量进行分类，叫做R型聚类分析。我们着重讲述的是对样本分类，即Q型聚类分析。—对变量分类—型聚类分析—对样本分类—型聚类分析数字分类模糊聚类定量分类定性分类关于分类方法的分类RQ饮料数据（drink.sav）16种饮料的热量、咖啡因、钠及价格四种变量样本数据与小类、小类与小类之间的度量1、最短距离法（NearestNeighbor),ijGx21•x12•x22•x11•13d定义：T为一给定的阈值，如果对任意的，有(为的距离)，则称G为一个类。ijdTijdij和两个类之间的距离是从两个类中抽取的每对样本（一个取自第一个类，另一个取自第二个类）的距离中的最小值。注：在实际问题中有时给出一个阈值T，要求类与类之间的距离小于T，故有些样品可能归不了类。例如：设x1=(0,2),x2=(0,0),x3=(1.5,0),x4=(5,0),X5=(5,2)点间的距离使用欧式距离：pkjkikijxxd12)(解：这些点间的欧式距离是：d(x1,x2)=2,d(x1,x3)=2.5,d(x1,x4)=5.39,d(x1,x5)=5d(x2,x3)=1.5,d(x2,x4)=5,d(x2,x5)=5.29d(x3,x4)=3.5,d(x3,x5)=4.03d(x4,x5)=2首先，按距离最小合并样本x2和x3，生成一个类{x2,x3},其距离值为1.5。第二步，依据更高的合并级别2.0把x4和x5合并成一个新类{x4,x5}.同时，类{x2,x3}和{x1}间的最小距离也是2.0。因此，这两个类可以合并成与x4和x5同一相似级别的类。最后，两个类{x1,x2,x3}和{x4,x5}可以以更高的级别进行合并，其最小距离为3.5。得出的树状图如下图：最长距离法（FurthestNeighbor）•••x11•x21••••12d两个类之间的距离是从两个类中抽取的每对样本（一个取自第一个类，另一个取自第二个类）的距离中的最大值。根据美国等20个国家和地区的信息基础设施的发展状况进行分类。Call—每千人拥有的电话线数；movel—每千人户居民拥有的蜂窝移动电话数；fee—高峰时期每三分钟国际电话的成本；comp—每千人拥有的计算机数；mips—每千人计算机功率（每秒百万指令）；net—每千人互联网络户主数。国家callmovelfeecompmipsnetmeiguo631.6161.90.364032607335.34riben498.4143.23.57176102236.26deguo557.670.602.18199115719.84ruidian684.1281.81.42461666029.39ruishi64493.51.982341362122.68xinjiapo498.4147.52.52841357813.49taiwan469.456.13.6811969111.72hanguo434.5733.369957951.66baxi81.916.33.02198760.52zhili138.68.201.43114111.28moxige92.29.82.613117510.35eluosi174.955.122411010.48bolan1696.53.684017961.45xiongyali262.249.42.666830673.09malaixiya195.588.44.195327341.25taiguo78.627.84.952216620.11yindu13.60.306.2821010.01faguo559.142.91.27201117024.76yingguo521.10122.50.982481446111.91例某公司下属30个企业，公司为了考核下属企业的经济效益，设计了8个指标。为了避免重复，需要对这8个指标进行筛选，建立一个恰当的经济效益指标体系。通过计算30个企业8个指标的相关系数距离，数据是1-r2。得如下表:x1x2x3x4x5x6x7x8x100.6000.430.4600.470.450.1200.570.450.230.2200.380.400.210.290.2200.310.790.650.700.800.6600.450.450.270.230.140.190.770试用将它们聚类。x2x3x4x5x6x7x8确定类的个数在聚类分析过程中类的个数如何来确定才合适呢？这是一个十分困难的问题，人们至今仍未找到令人满意的方法。但是这个问题又是不可回避的。给定阈值——通过观测聚类图，给出一个合适的阈值T。要求类与类之间的距离不要超过T值。例如我们给定T=2.2，当聚类时，类间的距离已经超过了2.2，则聚类结束。什么是好的聚类方法?一个好的聚类方法可以产生高质量的聚类：类的内部具有较高的相似度类间具有较低的相似度聚类结果的质量依赖于相似度评价方法以及它们的应用；聚类结果的质量也取决于它发现隐藏模式的能力。.K-均值聚类K-均值聚类方法是最简单、最常用的使用使用准则的方法。K-均值聚类是属于划分方法中的基于质心技术的一种方法。划分的思路是以k为参数，把n个对象分为k个类，以使类内具有较高的相似度，而类间的相似度较低。相似度的计算根据一个类中对象的平均值(被看作类的重心)来进行。K-均值聚类的处理流程如下。首先，随机选择k个对象，每个对象都初始地代表一个类的平均值或中心。对剩余的对象，根据其与各自类中心的距离，将它赋给最近的类。然后重新计算每个类的平均值。这个过程不断重复，直到准则函数收敛。注意：类均值的初始值是任意分配的，可以随机分配也可以直接使用前K个成员的属性值。K-均值聚类实例假设给定如下要进行聚类的元组：{2,4,10,12,3,20,30,11,25}，并假设k=2.初始时用前两个数值作为类的均值；m=2和m=4.利用欧几里德距离，可得K1={2,3}和K2={4,10,12,20,30,11,25}。数值3与两个均值的距离相等，所以任意地选择K1作为其所属类。在这种情况下，可以进行任意指派。计算均值可得m1=2.5和m2=16。重新对类中的成员进行分配，不断重复上述过程，直至均值不再变化。具体过程如表：m1m2K1K224{2,3}{4,10,12,20,30,11,25}2.516{2,3,4}{10,12,20,30,11,25}318{2,3,4,10}{12,20,30,11,25}4.7519.6{2,3,4,10,11,12}{20,30,25}725{2,3,4,10,11,12}{20,30,25}注意在最后两步中类的成员是一致的，由于均值不再变化，所以均值已经收敛了。因此，该问题的答案为:K1={2,3,4,10,11,12}和K2={20,30,25}K-均值法要求定义的类均值存在，并且要以期望的类的数目k作为输入。要求用户必须事先给出k（要生成的类的数目）可以算是该方法的一个缺点。而且，它对于“噪声”和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。K-Means聚类示例012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910增量聚类在越来越多的应用中，必须对收集来的大量数据进行聚类。“大量”的定义随着技术的改变而不同。在六十年代，“大量”意味着几千个聚类的样本。现在，有些应用涉及到成千上万个高维样本的聚类。增量聚类方法是最流行的，我们将解释它的基本原理，下面是增量聚类方法的所有步骤：1、对样本排序后，把第一个数据项分配到第一个类里。2、考虑下一个数据项，把它分配到目前某个类中或一个新类中。给分配是基于一些准则的，例如新数据项到目前类的重心的距离。在这种情况下，每次添加一个新数据项到一个目前的类中时，需要重新计算重心的值。3、重复步骤2，直到所有的数据样本都被聚类完毕。例如：设x1=(0,2),x2=(0,0),x3=(1.5,0),x4=(5,0),X5=(5,2)假定样本的顺序是：X1,X2,X3,X4,X5,类间相似度的阈值水平是s=3。1、第一个样本X1将变成第一个类C1={x1}.x1的坐标就是重心坐标M1={0，2}。2、开始分析其他样本。a)把第2个样本x2和M1比较，距离d为:d(x2,M1)==2.032202因此，x2属