资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,/62,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,*,第,3,章,聚类分析,3.1,概述,3.2,相似性度量,3.3 k-means,算法及其改进,3.4,一趟聚类算法,3.5,层次聚类算法,3.6,神经网络方法,3.7,聚类算法评价,3.8,综合例子,第3章 聚类分析 3.1 概述,开篇案例,百思买的客户分群,百思买(,BestBuy,)作为美国最大的家电及,IT,零售连锁商，其客户细分战略(,Customer Centricity,)是其经营及商店定位的重要组成部分。百思买将其中心客户分为,5,种类型，巴利(,Barry,)，巴茨(,Buzz,)，雷(,Ray,)，店门(,StoreFront,)，吉儿(,Jill,)。巴利是对技术很精通的顾客，吉儿是忙于接送小孩参加各种市区文体活动的住在郊区的妈妈，巴茨是热衷于新玩意儿的潮族，雷是对价格敏感的工薪族，店门则拥有一家小企业。除,5,种核心客户之外，还有单身年轻女士凯莉(,Carrie,)和空巢一族海伦及查理(,Helen,，,Charlie,)等，也是百思买感兴趣的客户类型。,百思买结合销售数据(含会员卡)以及人口分布数据，来确认每个商店是否需要侧重于某个客户群。在其,300,个店中，就有,40,个专门定位于巴利型客户，并进行了重新布局，在这类店中可以看到单独的家庭影院店中店，资深销售，以及便携设备专家；吉儿型店的特色导购员可以帮主妇选择合适的数码产品；而巴茨店则有大量的电子游戏商品。同一个店可以侧重于多个客户类型，比如吉儿型和巴利型就经常被作为同一个店的定位。每个店的定位确定之后，相应的布局，存货，人员等，即可相应进行调整优化。,(资料来源：, (1),类间相似度最小化,(,距离最大化,),类内相似度最大化,(,距离最小化,),简单地描述，,聚类,(Clustering),是将数据集划分为若干相似对象组成的多个组,(group),或簇,(cluster),的过程，使得同一组中对象间的相似度最大化，不同组中对象间的相似度最小化。或者说一个簇,(cluster),就是由彼此相似的一组对象所构成的集合，不同簇中的对象通常不相似或相似度很低。,3.1 概述 (1)类间相似度最小化(距离最大化)类内相似度,3.1,概述 (2),从机器学习的角度看，聚类是一种,无监督的机器学习,方法，即事先对数据集的分布没有任何的了解，它是将物理或抽象对象的集合组成为由类似的对象组成的多个类的过程。聚类方法的目的是寻找数据中：潜在的自然分组结构和感兴趣的关系。,聚类分析中“簇”的特征：,聚类所说的簇不是事先给定的，而是根据数据的相似性和距离来划分；,聚的数目和结构都没有事先假定。,3.1 概述 (2)从机器学习的角度看，聚类是一种无监督的机,3.1,概述 (,3,),聚类分析的应用,聚类分析正在蓬勃发展，广泛应用于一些探索性领域,如统计学与模式分析，金融分析，市场营销，决策支持，信息检索，,WEB,挖掘，网络安全，图象处理，地质勘探、城市规划，土地使用、空间数据分析，生物学，天文学，心理学，考古学等。,3.1 概述 (3)聚类分析的应用,3.1,概述 (,4,),典型聚类方法简介,划分方法,：基于质心,(K-means),、中心的划分方法,层次的方法,(hierarchical methods),：,BIRCH,、,ROCK,、,CURE,基于密度的方法,：,DBSCAN,、,OPTICS,基于图的方法,：,Chameleon,、,SNN,基于网格的方法,(grid-based methods),：,STING,、,WaveCluster,、,CLIQUE,基于模型的方法,(model-based methods),：,EM,、,COBWEB,、神经网络,其他聚类方法,：谱聚类算法,(spectral clustering),、蚁群聚类算法等,3.1 概述 (4)典型聚类方法简介,3.2,相似性度量,3.2.1,数据及数据类型,3.2.2,属性之间的相似性度量,3.2.3,对象之间的相似性度量,3.2 相似性度量3.2.1 数据及数据类型,7,3.2.1,数据及数据类型 (1),相关概念,(1),数据,狭义：,数字,广义：,数据对象及其属性的集合，其表现形式可以是数字、符号、文字、图像抑或是计算机代码等等。,(2),属性,也称为特征、维或字段，是指一个对象的某方面性质或特性。一个对象通过若干属性来刻画。,73.2.1 数据及数据类型 (1)相关概念,3.2.1,数据及数据类型 (2),不同的属性类型,属性类型,描述,例子,操作,分类的,(,定性的,),标称,其属性值只提供足够的信息以区分对象。这种属性值没有实际意义,颜色、性别、产品编号,众数、熵、,列联相关。,序数,其属性值提供足够的信息以区分对象的序。,成绩等级,(,优、良、中、及格、不及格,),、年级,(,一年级、二年级、三年级、四年级,),中值、百分位、秩相关、符号检验。,数值的,(,定量的,),区间,其属性值之间的差是有意义的。,日历日期、摄氏温度,均值、标准差、皮尔逊相关,比率,其属性值之间的差和比率都是有意义的。,长度、时间和速度,几何平均、调和平均、百分比变差,3.2.1 数据及数据类型 (2)不同的属性类型属性类型描述,9,属性,包含电信客户信息的样本数据集,客户编号,客户类别,行业大类,通话级别,通话总费用,N22011002518,大客户,采矿业和一般制造业,市话,16352,C14004839358,商业客户,批发和零售业,市话国内长途,(,含国内,IP),27891,N22004895555,商业客户,批发和零售业,市话国际长途,(,含国际,IP),63124,3221026196,大客户,科学教育和文化卫生,市话国际长途,(,含国际,IP),53057,D14004737444,大客户,房地产和建筑业,市话国际长途,(,含国际,IP),80827,对象,3.2.1,数据及数据类型 (3),例子：包含电信客户信息的样本数据集,9属性包含电信客户信息的样本数据集客户编号客户类别行业大类通,10,3.2.1,数据及数据类型 (4),数据集可以看作具有相同属性的数据对象的集合。在数据挖掘领域，关于数据集有三个方面的问题需要考虑：维度、稀疏性和分辨率。,(1),维度,(Dimensionality),指数据集中的对象具有的属性个数总和。,维归约,(2),稀疏性,(Sparsity),指在某些数据集中，有意义的数据非常少，对象在大部分属性上的取值为,0,；非零项不到,1%,。,文本数据集,(3),分辨率,(Resolution),不同分辨率下数据的性质不同,103.2.1 数据及数据类型 (4)数据集可以看作具有相同,11,3.2.2,属性之间的相似性度量,简单属性间的相似度和相异度,两个属性相似程度的数值度量，两个属性越相似，它们的相似度就越高。相异度与相似度相反。,不同类型的属性使用的相似性度量是不同的。,113.2.2 属性之间的相似性度量 简单属性间的相似度和相,12,3.2.3,对象之间的相似性度量 (1),对象之间的相似性度量，即多个属性整体的相似性度量方法,。对象之间的相似度计算涉及描述对象的属性类型，需要将不同属性上的相似度整合成一个总的相似度来表示。,相似性度量方法,包括：距离度量和相似系数。,假定使用,m,个属性来描述数据记录，将每条记录看成,m,维空间中的一个点，距离越小、相似系数越大的记录之间的相似程度越大。这里分三种情况来描述：,(1),所有属性是,数值型,的；,(2),所有属性都是,二值属性,的；,(3),同时包含有分类属性和数值属性的,混合属性,。,123.2.3 对象之间的相似性度量 (1)对象之间的相似性,(1),数值属性相似性度量,1,)距离度量,(,a,) 闵可夫斯基,(Minkowski ),距离,x=1,城市块(曼哈顿)距离,x=2,欧几里得距离,x=,切比雪夫,(Chebyshev),距离,3.2.3,对象之间的相似性度量 (2),(1) 数值属性相似性度量3.2.3 对象之间的相似性度量,14,Minkowski,距离计算例子,Distance Matrix,3.2.3,对象之间的相似性度量 (3),14Minkowski 距离计算例子Distance Mat,15,3.2.3,对象之间的相似性度量 (4),Canberra,距离是由,Lance,和,Williams,最早提出的，定义如下：,Canberra,距离或,Lance,距离可以看成一种相对曼哈顿距离，它克服了,Minkowski,距离受量纲影响的缺点,Canberra,距离对缺省值是稳健的，当两个坐标都接近,0,时，,Canberra,距离对微小的变化很敏感。,153.2.3 对象之间的相似性度量 (4)Canberra,2),相似系数,(,a,) 余弦相似度,余弦相似度忽略各向量的绝对长度，着重从形状方面考虑它们之间的关系。取值范围在区间,-1,，,1,内。当两个向量方向相近时，夹角余弦值较大，反之则较小。特别地，当两个向量平行时，夹角余弦值为,1,，而正交时余弦值为,0,。,(b),相关系数,相关系数是向量标准化后的夹角余弦，取值范围在区间,-1,，,1,内。它表示两个向量的线性相关程度。,3.2.3,对象之间的相似性度量 (,5,),2) 相似系数3.2.3 对象之间的相似性度量 (5),(c),广义,Jaccard,系数,广义,Jaccard,系数又称为,Tanimoto,系数，用,EJ,表示，取值范围在区间,0,，,1,内。广泛用于信息检索和生物学分类中，在二元属性情况下简化为,Jaccard,系数。,3.2.3,对象之间的相似性度量 (,6,),(c)广义Jaccard系数3.2.3 对象之间的相似性度量,(,2,)二值属性的相似性度量,一个二值属性变量(,binary variable,)只有,0,或,1,两种状态，表示属性的存在与否。一种差异计算方法就是根据二值数据计算。,假设二值属性对象,p,和,q,的取值情况如表,3-3,所示，其中,n11,表示对象,p,和,q,中均取,1,的二值属性个数，,n10,表示对象,p,取,1,而对象,q,取,0,的二值属性个数，,n01,表示对象,p,取,0,而对象,q,取,1,的二值属性个数，,n00,表示对象,p,和,q,均取,0,的二值属性个数。,3.2.3,对象之间的相似性度量 (,7,),表,3-3,二值属性对象,p,和,q,的取值情况,对象,p,对象,q,1,0,合计,1,n,11,n,10,n,11,+n,10,0,n,01,n,00,N,01,+n,00,合计,n,11,+n,01,n,10,+n,00,(2)二值属性的相似性度量3.2.3 对象之间的相似性度量,二值属性相似性存在对称的和不对称两种情况,。如果二值属性的两个状态值所表示的内容同等重要，则是对称的，否则为不对称。如，给定变量,smoker,，它描述一个病人是否吸烟的情况，用,0,或,1,进行编码来表示一个病人吸烟状态是同等重要的，因此,smoker,是对称变量。,基于,对称二值变量,所计算的相似度称为,不变相似性,(即变量编码的改变不会影响计算结果)。对于不变相似性，常用简单匹配相关系数来描述对象,p,和,q,之间的差异程度，其定义为：,对于不对称的二值变量，如果取值,1,比,0,重要，那么这样的二值变量就只有一种状态。,例如，属性,disease,的检测结果是阳性或阴性，这两个结果的重要性是不一样的，通常将少见而重要的情况用,1,表示 (如,HIV,阳性)，将不重要情况用,0,表示。这种情况下对象,p,和,q,之间的差异程度评价通常采用,Jaccard,系数，其定义为：,3.2.3,对象之间的相似性度量 (,8,),二值属性相似性存在对称的和不对称两种情况。如果二值属性的两个,(,3),混合属性相似性度量,在实际应用中，数据对象往往包含多种类型的属性，因此使用混合类型的属性描述。这需要将不同类型的属性差异度组合成一个整体，把所有属性间的差异转换到区间,0,，,1,中。,假设数据集包含,m,个不同类型的属性，对象,p,和,q,之间的差异度推广,Minkowski,距离，定义为,:,3.2.3,对象之间的相似性度量 (,9,),(3)混合属性相似性度量3.2.3 对象之间的相似性度量 (,对象,p,和,q,在属性,f,上的相异度,根据其属性类型不同进行相应计算：,(,a,)若属性,f,为二元属性或标称属性，则：如果,，那么,，否则,。,(,b,)若属性,f,为序数型属性，计算对象,p,和对象,q,在属性,f,上的秩(或等级),和,，,。,(,c,)若属性,f,为区间标度属性，则,，,、,分别表示属性,f,的最大值和最小值。,(,d,)若属性,f,为比率数值属性，则通过变换转换为区间标度属性来处理。,这样，当描述对象的属性是不同类型时，对象之间的相异度也能够计算，且取值在,0,，,1,区间。,3.2.3,对象之间的相似性度量 (,10,),对象p和q在属性f上的相异度 根据其属性类型不同进行相应计算,(,4),由距离度量转换而来的相似性度量,可以通过一个单调递减函数，将距离转换成相似性度量，相似性度量的取值一般在区间,0,，,1,之间，值越大，说明两个对象越相似。常用的方式有：, 采用负指数函数将距离转换为相似性度量,s,，即：,采用距离的倒数作为相似性度量，即：,分母上加,1,是为了避免分母为,0,时出现错误。,若距离在,0,1,之间，可采用与,1,的差作为相似系数，即：,3.2.3,对象之间的相似性度量 (,11,),(4)由距离度量转换而来的相似性度量3.2.3 对象之间的相,3.3 k-means,算法及其改进,3.3.1 k-means,算法,3.3.2 k-means,算法的改进,3.3 k-means算法及其改进3.3.1 k-means,3.3,.1,K-means,算法(1),K-means,算法是,1967,年由,MacQueen,提出的，迄今为止，很多聚类任务都选择该经典算法。其核心思想是找出,K,个簇中心,，使得每一个数据点,到其最近的簇中心,的平方距离和被最小化。,k-means,聚类算法的形式化描述如下：,(1),从数据集,D,中任意选择,k,个对象作为初始簇中心；,(2) repeat,(3) for,数据集,D,中每个对象,P do,(4),计算对象,P,到,k,个簇中心的距离,(5),将对象,P,指派到与其最近,(,距离最短,),的簇；,(6) end for,(7),计算每个簇中对象的均值，做为新的簇的中心；,(8) until k,个簇的簇中心不再发生变化,k-means,算法中用如,来表示一个簇。,3.3.1 K-means 算法(1) K-means 算,k-means,描述容易、实现简单、快速，但存在如下不足：,(,1,)簇个数,k,需要预先指定，但实际上难以确定；,(,2,)算法对初始值的选取依赖性极大以及算法常陷入局部最优解；,(,3,)由于簇的质心(即均值)作为簇中心进行新一轮聚类计算，孤立点和噪声点会导致簇质心偏离真正的数据密集区，所以,k-means,对噪声点和孤立点很敏感；,(,4,)不能用于发现非凸形状的簇，或具有各种不同大小或密度的簇。例如图,3-1,所示的两个簇，用,k-means,划分方法不能正确识别，原因在于它们所采用的簇的表示及簇间相似性度量不能反映这些自然簇的特征；,(,5,)只能用于处理数值属性的数据集，不能处理包含分类属性的数据集。,3.3,.1,K-means,算法(,2,),图,3-1,基于质心的划分方法不能识别的数据示例,k-means描述容易、实现简单、快速，但存在如下不足：3.,例,3-1,对表,3-4,中二维数据，使用,k-means,算法将其划分为,2,个簇，假设初始簇中心选为,P7(4,，,5),，,P10(5,，,5),。,3.3,.1,K-means,算法(,3,),P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,x,3,3,7,4,3,8,4,4,7,5,y,4,6,3,7,8,5,5,1,4,5,表,3-4,k-means,聚类过程示例数据集,解：图,3-2,显示了对于给定的数据集,k-means,聚类算法的执行过程。,图,3-2 k-means,算法聚类过程示例,例3-1 对表3-4中二维数据，使用k-means算法将其,(,1,)根据题目，假设划分的两个簇分别为,C,1,和,C,2,，初始中心分别为(,4,，,5,)和(,5,，,5,)，下面计算,10,个样本到这,2,个簇中心的距离，并将,10,个样本指派到与其最近的簇：,(,2,)第一轮迭代结果如下：,属于簇,C,1,的样本有：,P7,，,P1,，,P2,，,P4,，,P5,，,P8,属于簇,C,2,的样本有：,P10,，,P3,，,P6,，,P9,重新计算新的簇中心，,得到：,C,1,的中心为(,3.5,，,5.167,)，,C,2,的中心为(,6.75,，,4.25,),(,3,)继续计算,10,个样本到两个新的簇中心的距离，重新分配到新的簇中，第二轮迭代结果如下：,属于簇,C1,的样本有：, P1,，,P2,，,P4,，,P5,，,P7,，,P10,属于簇,C2,的样本有：, P3,，,P6,，,P8,，,P9,重新计算新的簇中心，得到：,C1,的中心为(,3.67,，,5.83,)，,C2,的中心为(,6.5,，,3.25,),(,4,)继续计算,10,个样本到两个新的簇中心的距离，重新分配到新的簇中，发现簇中心不再发生变化，算法终止。,3.3,.1,K-means,算法(,4,),(1)根据题目，假设划分的两个簇分别为C1和C2，初始中心分,3.3,.2,K-means,算法的改进(1),k-means,算法中距离的计算基于数值型数据,，没有说明对于分类型数据如何处理。此外，它对于噪声和离群点数据敏感。介绍,k-means,聚类算法的一些改进策略，它们在初始簇时对象的选择、相似度的计算方法或簇中心的计算方法等不同。,下面介绍三种,k-means,算法的改进方法：,(,1,)将分类型数据转化为数值型数据，再利用,k-means,算法进行聚类分析。,(,2,)适用于纯分类属性数据集的,k-modes,算法和适用于混合属性数据集的,k-prototypes,算法。,k-modes,算法采用,mode,(取值频率最大的属性值，即众数)来表示分类属性，在聚类过程中使用简单匹配来度量分类属性的不相似性(,dissimilarity,)。将,k-modes,算法和,k-means,结合到一起形成了,k-prototypes,算法，用来处理具有混合属性的数据集。,(,3,)适用于混合属性数据集的,K-Summary,算法，它使用簇的摘要信息表示簇的质心。,3.3.2 K-means 算法的改进(1) k-mean,数据往往具有混合属性的特点，这里介绍一种简单的聚类表示方法，并对,闵可夫斯基(,Minkowski,)距离进行推广以使聚类算法可以有效处理包含分类属性的数据,。,假设数据集,D,有,m,个属性，其中有,个分类属性和,个数值属性，,，设分类属性位于数值属性之前，用,表示第,i,个属性取值的集合。,定义3,-1,给定簇,C,，,，,a,在,C,中关于,D,i,的频度定义为,C,在,D,i,上的投影中包含,a,的次数：,定义3,-2,给定簇,C,，,C,的摘要信息,CSI,(Cluster Summary Information),定义为：,，其中,为,C,的大小,由分类属性中不同取值的频度信息和数值型属性的质心两部分构成，即：,3.3,.2,K-means,算法的改进(2),数据往往具有混合属性的特点，这里介绍一种简单的聚类表示方法，,定义3,-3,给定,D,的簇,C,、 和,对象 与 ，,x0,。,(1),对象,p,，,q,在属性,i,上的差异程度,(,或距离,),定义为：,对于分类属性或二值属性，,;,对于连续数值属性或顺序属性， ；,(2),两个对象,p,，,q,间的差异程度,(,或距离,),定义为：,;,3.3,.2,K-means,算法的改进(3),定义3-3 给定D的簇C、 和 ,对象,(3),对象,p,与簇,C,间的距离 定义为,p,与簇,C,的摘要之间的距离：,这里 为,p,与,C,在属性 上的距离，对于分类属性 其值定义为,p,与,C,中每个对象在属性 上的距离的算术平均值，即,；,对于数值属性 其值定义为,3.3,.2,K-means,算法的改进(4),(3)对象p与簇C间的距离 定义为p与,(4),簇,C,1,与,C,2,间的距离 定义为两个簇的摘要间的距离：,这里 为 与 在属性 上的距离，对于分类属性 其值定义为 中每个对象与 中每个对象的差异的平均值：,对于数值属性 其值定义为,在定义,3-3,的,(2),中，当,x=1,时，相当于曼哈顿,(Manhattan),距离，当,x=2,时，相当于欧式,(Euclidean),距离。,3.3,.2,K-means,算法的改进(5),(4) 簇C1与C2间的距离,3.3,.2,K-means,算法的改进(6),例,3-2,假设描述学生的信息包含属性：性别，籍贯，年龄。有两条记录,p,，,q,及两个簇,C1,，,C2,的信息如下，分别求出记录和簇彼此之间的距离：,p=,男，广州，,18,，,q=,女，深圳，,20,C1=,男：,25,，女：,5,；广州：,20,，深圳：,6,，韶关：,4,；,19,C2=,男：,3,，女：,12,；汕头：,12,，深圳：,1,，湛江：,2,；,24,按定义,4-3,，取,x=1,得到的各距离如下：,d(p,，,q)=1+1+(20-18)=4,d(p,，,C1)=(1-25/30)+(1-20/30)+(19-18)=1.5,d(p,，,C2)=(1-3/15)+(1-0/15)+(24-18)=7.8,d(q,C1)=(1-5/30)+(1-6/30)+(20-19)=79/30,d(q,C2)=(1-12/15)+(1-1/15)+(24-20)=77/15,d(C1,C2)=1-(25*3+5*12)/(30*15)+1-6*1/(30*15)+(24-19)=1003/1506.69,3.3.2 K-means 算法的改进(6) 例3-2 假,3.3,.2,K-means,算法的改进(7),用定义,3-3,取代相关聚类算法中的距离定义，就可使原来仅适用于数值或分类属性的聚类算法不受数据类型的限制而可用于任何数据类型。,k-summary,算法,就是采用定义,3-3,推广了,k-means,算法，可以处理混合属性数据集。由三个主要步骤完成,:,(,1,)初始化,:,选择,k,个对象，创建,k,个簇的,CSI,；,(,2,)划分对象到最接近的簇,;,(,3,)重新计算每个簇的,CSI;,(,4,)重复(,2,)和(,3,)直到选用的度量函数收敛，如误差和变化很小或相邻两次迭代没有对象从一个簇移动到另一个簇。,3.3.2 K-means 算法的改进(7) 用定义3-3,例,3-3,对于表,3-5,所示的数据集，请使用,k-summary,算法将其划分为,2,个簇，并选择记录,3,和,5,分别为每个簇的初始对象。,$_,年收入为年收入列规范化后的结果。,表,3-5,某银行拖欠贷款数据,3.3,.2,K-means,算法的改进(8),序号,是否有房,婚姻状况,年收入,$_,年收入,拖欠贷款,1,yes,single,125K,0.406,no,2,no,married,100K,0.25,no,3,no,single,70K,0.063,no,4,yes,married,120K,0.375,no,5,no,divorced,95K,0.219,yes,6,no,married,60K,0,no,7,yes,divorced,220K,1,no,8,no,single,85K,0.156,yes,9,no,married,75K,0.094,no,10,no,single,90K,0.188,yes,例3-3 对于表3-5所示的数据集，请使用k-summary,3.3,一趟聚类算法,现有聚类算法的普遍存在以下不足：,对于大规模数据集，聚类时效性和准确性难以满足要求；,难以直接处理混合属性的数据；,聚类结果依赖于参数，而参数的选择主要靠经验或试探，没有简单、通用的方法。,3.3 一趟聚类算法 现有聚类算法的普遍存在以下不足：,一趟聚类算法采用摘要信息,CSI,表示一个簇,，及定义,3-3,来度量距离，其将数据集分割为半径几乎相同的超球体(簇)。具体过程如下：,(,1,)初始时，簇集合为空，读入一个新的对象；,(,2,)以这个对象构造一个新的簇；,(,3,)若已到数据库末尾，则转(,5,)，否则读入新对象，利用给定的距离定义，计算它与每个已有簇间的距离，并选择最小的距离；若最小距离超过给定的半径阈值,r,，转(,2,)；,(,4,)否则将该对象并入具有最小距离的簇中并更新该簇的各分类属性值的统计频度及数值属性的均值，转(,3,)；,(,5,)结束。,3.,4.1,算法描述,一趟聚类算法采用摘要信息CSI表示一个簇，及定义3-3来度量,3.,4.2,聚类阈值的选择策略,采用抽样技术来计算阈值范围，具体描述如下：,(1),在数据集,D,中随机选择对对象；,(2),计算每对对象间的距离；,(3),计算,(2),中距离的平均值,EX,和标准差,DX,；,(4),取,r,在,EX+0.25DX,到,EX-2DX,之间,例,3-4,一趟聚类算法聚类过程示例。,对于表,3-5,的数据集，采用一趟聚类算法聚类。,EX=43,，,DX=45,，取,r=EX,，若规范化年收入属性，则,EX=1.32,DX=0.89,取,r=EX,。表中,$_,年收入为年收入规范化的结果。,3.4.2 聚类阈值的选择策略 采用抽样技术来计算阈值范围，,3.5,层次聚类算法,3.5.1,概述,3.5.2 BIRCH,算法,3.5.3,两步聚类算法,3.5 层次聚类算法3.5.1 概述,3.,5.1 概述 (1),层次聚类法,是一种已得到广泛使用的经典方法，它是通过将数据组织为若干组并形成一个相应的树来进行聚类。层次聚类方法可分为自顶向下和自下而上两种层次聚类。,自下而上聚合层次聚类方法,(,或凝聚层次聚类,),。这种自下而上策略就是最初将每个对象,(,自身,),作为一个簇，然后将这些簇进行聚合以构造越来越大的簇，直到所有对象均聚合为一个簇，或满足一定终止条件为止。绝大多数层次聚类方法属于这一类，只是簇间相似度的定义有所不同。,自顶向下分解层次聚类方法,(,或分裂层次聚类,),。这种策略的作法与自下而上策略的作法相反。它首先将所有对象看成一个簇的内容，将其不断分解以使其变成越来越小但个数越来越多的小簇，直到所有对象均独自构成一个簇，或满足一定终止条件为止。,3.5.1 概述 (1)层次聚类法是一种已得到广泛使用的经典,图,3-3,两种不同层次聚类算法,3.,5.1 概述,(2),图,3-3,描述了一种,凝聚层次聚类算法,AGENS,(,AGglomerative NESting,)和一种,分裂层次聚类算法,DIANA,(,DIvisive ANAlysis,)对一个包含五个对象的数据集合,a,，,b,，,c,，,d,，,e,的处理过程。,其中从左往右的过程属于凝聚层次聚类方法：,图3-3 两种不同层次聚类算法3.5.1 概述 (2)图3-,3.5.2 BIRCH,算法 (1),BIRCH,算法,是一种,基于距离的层次聚类算法,，其,核心是聚类特征,CF,(,Cluster Feature,)和,聚类特征树,(,CF-Tree,)，它们用于概括簇描述。这些结构使得,BIRCH,方法对增量和动态聚类非常有效。下面详细讨论聚类特征和聚类特征树。,(,1,),CF,结构,聚类特征(,CF,)是一个包含聚类信息的三元组，其定义如下：,给定一个簇中的,N,个,d,维的数据点：,，这个簇的聚类特征,CF,向量是一个三元组,，其中,N,是簇中数据点的个数，,是,N,个数据点的线性和(即,)，而,SS,是,N,个数据点的平方和(即,)。其中线性和反映了聚类的质心，平方和反映了簇的直径大小，它们的作用是计算平均值和方差。,聚类特征具有可加性。,3.5.2 BIRCH算法 (1)BIRCH算法是一种基于距,例,3-5,假定在簇 中有三个点,(2,，,5),，,(3,，,2),和,(4,，,3),。 的聚类特征是：,CF,1,= = ,假定 是与 不相交的簇，,CF,2,= ,。,和 合并形成一个新的簇 ，其聚类特征便是 ，即：,CF,3,= = ,3.5.2 BIRCH,算法 (2),例3-5 假定在簇 中有三个点(2，5)，(3，2)和,(,2,),CF-,树,一个,CF-,树是一个高度平衡的树，它具有三个参数：非叶节点,CF,条目最大个数,B,、叶节点中,CF,条目的最大个数,L,和距离阈值,T,。,这些参数影响结果树的大小，其目标是通过参数调整，将,CF,树保存在内存中。每个非叶节点最多容纳,B,个形为,的,CF,条目，,是一个指向它的第,个子节点的指针，,是由这个,指向的子节点所代表的子聚类的,。一个叶节点最多容纳,个,条目，每个叶节点还有一个指向前面节点的指针,和指向后面叶节点的指针,，这样所有叶节点形成一个链表可以方便扫描。当,B=6,，,L=5,时的一棵,CF,树的图形如图,3-4,。,3.5.2 BIRCH,算法 (3),(2)CF-树3.5.2 BIRCH算法 (3),3.5.2 BIRCH,算法 (4),CF-,树构造过程实际是一个数据点的插入过程，步骤如下：,(,a,)从根节点开始递归往下，计算当前条目与要插入数据点之间的距离，寻找距离最小的那个路径，直到找到与该数据点最接近的叶节点中的条目。,(,b,)比较计算出的距离是否小于阈值,T,，如果小于阈值,T,则当前条目吸收该数据点；如果距离大于等于阈值,T,，则转,(c),。,(,c,)判断当前条目所在叶节点的条目个数是否小于,L,，如果是则直接将数据点插入为该数据点的新条目，否则需要分裂该叶节点。分裂的原则是寻找该叶节点中距离最远的两个条目并以这两个条目作为分裂后新的两个叶节点的起始条目，其它剩下的条目根据距离最小原则分配到这两个新的叶节点中，删除原叶节点并更新整个,CF,树。,当数据点无法插入时，这个时候需要提升阈值,T,并重建树来吸收更多的叶节点条目，直到把所有数据点全部插入完毕。,3.5.2 BIRCH算法 (4)CF-树构造过程实际是一个,3.5.2 BIRCH,算法 (5),(,3,),BIRCH,算法描述,BIRCH,算法主要分为四个阶段：,第一个阶段对整个数据集进行扫描，根据给定的初始距离阈值,T,建立一棵初始聚类特征树；,第二阶段通过提升阈值,T,重建,CF,树，得到一棵压缩的,CF,树。,第三、四阶段利用全局聚类算法对已有的,CF,树进行聚类得到更好的聚类结果。,3.5.2 BIRCH算法 (5)(3)BIRCH算法描述,3.5.2 BIRCH,算法 (,6,),其中具体建树阶段算法步骤如下：,(,a,)给定一个初始的距离阈值,T,并初始化一棵,CF-,树,t1,。,(,b,)扫描数据点并插入到,CF-,树,t1,中。,(,c,)判断内存是否溢出，如果没有溢出转(,d,)，如果溢出转(,e,)。,(,d,)此时已经扫描完所有数据点，将存储在磁盘中的潜在离群点重新吸收到,CF-,树,t1,中，结束建树。,(,e,)提升阈值,T,的值并根据新的阈值通过,CF-,树,t1,中各节点条目重建,CF-,树,t2,：在重建过程中，如果,t1,的叶节点条目是潜在的离群点并且磁盘仍有空间，则将该离群点写入磁盘，否则使用该条目重建树,t2,。整个树,t2,建好后，重新将,t2,赋给,t1,。,(,f,)判断此时存储潜在离群点的磁盘是否已满，如果没有满则转(,b,)继续扫描下一个数据点。如果此时磁盘满了，则将存储在磁盘中的潜在离群点重新吸收到,CF-,树,t1,中，并转转(,b,)继续扫描下一个数据点。,3.5.2 BIRCH算法 (6)其中具体建树阶段算法步骤如,3.5.3,两步聚类算法,(1),两步聚类(,Two Step Clustering,)算法是,BIRCH,算法的一种改进。其基本步骤如下：,第一步，预聚类,，即先将样本粗略划分成,L,个簇。该步骤读入一个样本数据后，根据“亲疏程度”或“相似性”决定该样本应派生出一个新簇，还是应合并到已有的某个子簇中。这个过程反复进行，最终形成,L,个簇。,第二步，聚类,。即在预聚类的基础上，再根据“亲疏程度”决定哪些子簇可以合并，最终形成,M,个簇。,3.5.3 两步聚类算法 (1)两步聚类(Two Step,3.5.3,两步聚类算法,(3),3.5.3.1,两步聚类算法的特点,两步聚类的特点包括：既可以处理数值型变量，也可以处理分类型变量；能够根据一定准则确定簇数目；通过两步实现数据聚类。,3.5.3.2,两步聚类的“亲疏程度”度量,两步聚类采用距离度量样本或簇间的“亲疏程度”，并依据距离确定簇的划分。两步聚类同时考虑数值型和分类型变量的计算，如果变量均为数值型，则采用欧氏距离，否则，采用对数似然距离。,3.5.3.3,簇数目的确定,簇数目的确定在第二步聚类中完成。采用两个阶段的策略，第一阶段仅给出一个粗略估计，第二阶段给出一个恰当的最终簇数目，且两个阶段的判定标准不同。,3.5.3 两步聚类算法 (3)3.5.3.1 两步聚类算,3.6 SOM,算法 (,1,),3.6.1 SOM,算法中网络的拓扑结构,3.6.2 SOM,算法的聚类原理,3.6 SOM算法 (1)3.6.1 SOM算法中网络的拓扑,3.6 SOM,算法 (2),SOM,采用,WTA(Winner Takes All),竞争学习算法，其聚类过程通过若干单元对当前单元的竞争来完成，与当前单元权值向量最接近的单元成为赢家或获胜单元，获胜神经元不但加强自身，且加强周围邻近神经元，同时抑制距离较远的神经元。,SOM,可以在不知道输入数据任何信息结构的情况下，学习到输入数据的统计特征。,3.6 SOM算法 (2) SOM采用WTA(Winner,SOM,中的网络采用两层、前馈式和全链接的拓扑结构,，其网络结构如图,3-5,所示。,该网络的拓扑结构有以下特点：,3.,6.1 SOM算法中网络的拓扑结构,输入单元,X,i,连接权值,W,ij,输出层,权重向量,W,j,输入层,(,1,)网络包含两层，即一个输入层和一个输出层或竞争层。,(,2,)输入层的神经元个数由输入数据的属性个数决定，一个属性对应一个输入神经元，而输出层则是由输出层神经元按照一定的方式排列在二维平面上，输出节点个数就是簇个数，输出层的神经元个数的选取直接影响,SOM,网络的性能。,(,3,)网络是全连接的，即输入层中的每个输入节点都与输出节点完全相连，这些连接有不同的强度或权值。,(,4,)输出节点呈二维结构分布，且节点之间具有侧向连接。所以对某个输出节点来说，在一定邻域范围内会有一定数量的连接节点，这些连接有不同的权值，它控制和影响着输出层神经元之间的交互作用。,SOM中的网络采用两层、前馈式和全链接的拓扑结构，其网络结构,3.6.2 SOM,算法的聚类原理,(1),SOM,算法中的拓扑结构很好地模拟了人脑神经网络的特点和工作机理。输入层模拟不同的刺激信号，输出层中的每个节点模拟为神经细胞。,SOM,学习算法由最优匹配神经元(竞争)的选择和网络中权值的自组织(确定权值更新邻域和方式)过程两部分组成，这两部分相辅相成，它们共同作用完成自组织特征映射的学习过程。选择最优匹配神经元实质是选择输入模式对应的中心神经元，每执行一次学习，,SOM,网络中就会对外部输入模式执行一次自组织适应过程；其结果是强化现行模式的映射形态，弱化以往模式的映射形态。,3.6.2 SOM算法的聚类原理 (1)SOM算法中的拓扑结,在,SOM,模型中，每一个权值的有序序列,(p,为网络中神经元总数,),都可以看作是神经网络的一种内部表示，它是,有序输入序列 的相对应映象。,(1),获胜神经元,对于输入向量,x,，使用 表示最优匹配输入向量,x,的神经元，则可以通过下列条件决定 ：,这个条件概括了神经元竞争的本质，满足这个条件的神经元称为最佳匹配或获胜神经元。,(2),拓扑邻域,获胜神经元决定兴奋神经元的拓扑邻域空间位置，一个获胜神经元倾向于激活它紧接的邻域内神经元而不是隔得远的神经元，这导致对获胜神经元的拓扑邻域的侧向距离可以光滑地缩减。,3.6.2 SOM,算法的聚类原理,(2),在SOM模型中，每一个权值的有序序列,(3),权值更新与学习率参数,对于获胜神经元,i,的拓扑邻域里的神经元，按以下方式更新权值：,这里 为学习率参数，它随时间的增加单调下降，一种选择就是：,这里 是另一个时间常数。学习率参数 也可以选择线性下降函,数。,3.6.2 SOM,算法的聚类原理,(3),(3) 权值更新与学习率参数3.6.2 SOM算法的聚类原理,3.7,聚类算法评价,(1),好的聚类方法产生高质量的簇，即簇内的对象具有高的相似度和不同簇之间具有低的相似度。由于存在大量不同类型的聚类算法，而每种聚类算法可能都定义了自己的簇类型，每种情况都可能需要一种不同的评估度量。,传统的用于评估簇的度量有两类：监督的度量和非监督的度量。,3.7.1,监督度量,监督度量，也称外部质量评价准则,，是基于一个已经存在的人工分类数据集(已知每个对象的类别)进行评价的，这样可以将聚类输出结果直接与之进行比较。外部质量评价准则与聚类算法无关，理想的聚类结果是具有相同类别的数据被聚集到相同的簇中，具有不同类别的数据聚集在不同的簇中。,3.7 聚类算法评价 (1)好的聚类方法产生高质量的簇，即簇,3.7,聚类算法评价,(2),1,)聚类熵,聚类熵越小，聚类效果越好。,类似于信息熵，考虑簇中不同类别数据的分布。对于簇,Ci,，聚类熵,定义为：,整体聚类熵,定义为所有聚类熵的加权平均值：,(,2,)聚类精度,基本出发点是使用簇中数目最多的类别作为该簇的类别标记。对于簇,Ci,，聚类精度,定义为：,整体聚类精度,定义为所有聚类精度的加权平均值：,3.7 聚类算法评价 (2)1)聚类熵,3.7,聚类算法评价,(1),3.7.2,非监督度量,非监督度量，也称内部质量评估准则,，该类方法不使用对象的类别信息。非监督簇评估度量与聚类算法类型有关，如凝聚度和分离度仅用于划分的簇集合，而共性分离相关系数用于层次聚类。这里介绍共性分离相关系数。,共性分离相关系数(,CoPhenetic Correlation Coefficient,，简称,CPCC,)用于层次聚类的评估。两个对象之间的共性分离距离(,cophenetic distance,)是凝聚层次聚类算法首次将对象放在同一个簇时的邻近度。例如，在凝聚层次聚类过程的某个时刻，两个合并的簇之间的最小距离为,0.1,，则一个簇中的所有点关于另一个簇的各点的共性分离距离都是,0.1,。在共性分离距离矩阵中，项是每对对象之间的共性分离距离。共性分离相关系数是该矩阵与原来的相异度矩阵的项的相关度，是层次聚类对数据拟合程度的标准度量。该度量常用于评估层次聚类算法之间的质量对比。,3.7 聚类算法评价 (1)3.7.2 非监督度量,3.8,综合例子,本例的目的是通过对超市客户个人信息的聚类分析，发现客户群的特征，以实现对目标客户的准确理解和客户定位，便于后期针对不同特点的客户采用不同的营销策略。,数据来源于美国一家大型连锁会员制超市,Food Mart,，该超市拥有巨大的客户数量，而且记录了客户的个人信息。使用客户信息表,customer,进行分析，,customer,共有,10281,条记录，这些个人信息包括客户编号、账户编号、姓名、地址、城市、邮政编号、电话、生日、婚姻状态、年收入、性别、孩子数量、教育水平等,28,个属性。,表,3-7,客户细分属性选择,序 号,属 性,属 性 描 述,数 据 类 型,1,Marital_status,婚姻状态,二元变量,2,Yearly_income,年收入,标称变量,3,Gender,性别,二元变量,4,Total_children,孩子数量,区间标度变量,5,Num_child_at_home,在家的孩子数量,区间标度变量,6,Education,教育水平,标称变量,7,Member_card,会员卡类型,标称变量,8,Occupation,职业,标称变量,9,Houseowner,是否有房子,二元变量,10,Num_cars_owned,拥有的汽车数量,区间标度变量,3.8 综合例子本例的目的是通过对超市客户个人信息的聚类分析,3.9,本章小结,聚类分析,是最基本的数据分析工具，可用于发现复杂数据的结构，对数据进行探索性分析。一旦聚类分析找到了不同的簇，就能用分类等其他工具来发现不同簇之间的规律和模式。在市场或客户细分、高价值客户的发现等方面具有广泛用途。,聚类算法依赖于属性或对象之间的相似性度量，因而本章首先介绍数据的相似性度量。在此基础上，对聚类分析的经典方法，包括划分方法,(K-MEANS,、一趟聚类算法,),、层次方法,(BIRCH,、两步聚类,),、神经网络聚类方法的原理进行了介绍，并通过实例对这些经典算法的使用进行说明。,3.9 本章小结聚类分析是最基本的数据分析工具，可用于发现复,作业：,P61,：,3.1,3.4,3.5,3.6,作业：P61：3.1,3.4,3.5,3.6,此课件下载可自行编辑修改，此课件供参考！,部分内容来源于网络，如有侵权请与我联系删除！感谢你的观看！,此课件下载可自行编辑修改，此课件供参考！,
展开阅读全文