第5章聚类分析ppt课件

《第5章聚类分析ppt课件》由会员分享，可在线阅读，更多相关《第5章聚类分析ppt课件（147页珍藏版）》请在装配图网上搜索。

1、第1页第第5章章 聚类分析聚类分析 本章概述 本章的学习目标主要内容第2页什么是聚类什么是聚类l聚类（聚类（Clustering）就是将数据分组成为多个类）就是将数据分组成为多个类（Cluster或译为簇）。或译为簇）。l在同一个类内对象之间具有较高的相似度，不同类在同一个类内对象之间具有较高的相似度，不同类之间的对象差别较大。之间的对象差别较大。簇之间的距离最大化在一个簇内的距离最小化第3页l从机器学习的角度讲，簇相当于隐藏模式。聚类是从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程。搜索簇的无监督学习过程。l与分类不同，无监督学习不依赖预先定义的类或带与分类不同，无监督学

2、习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。标记，而分类学习的实例或数据对象有类别标记。第4页什么是聚类什么是聚类l早在孩提时代，人就通过不断改进下意识中的聚类早在孩提时代，人就通过不断改进下意识中的聚类模式来学会如何区分猫和狗，动物和植物模式来学会如何区分猫和狗，动物和植物l将周围的人分为家人和非家人将周围的人分为家人和非家人第5页聚类分析无处不在聚类分析无处不在l谁经常光顾商店，谁买什么东西，买多少？谁经常光顾商店，谁买什么东西，买多少？按忠诚卡记录的光临次数、光临时间、性别、按

3、忠诚卡记录的光临次数、光临时间、性别、年龄、职业、购物种类、金额等变量分类年龄、职业、购物种类、金额等变量分类这样商店可以这样商店可以.识别顾客购买模式（如喜欢一大早来买酸奶和识别顾客购买模式（如喜欢一大早来买酸奶和鲜肉，习惯周末时一次性大采购）鲜肉，习惯周末时一次性大采购）刻画不同的客户群的特征（用变量来刻画，就刻画不同的客户群的特征（用变量来刻画，就象刻画猫和狗的特征一样）象刻画猫和狗的特征一样）第6页什么情况下需要聚类什么情况下需要聚类l为什么这样分类？为什么这样分类？l因为每一个类别里面的人消费方式都不一样，需要因为每一个类别里面的人消费方式都不一样，需要针对不同的人群，制定不同的关系

4、管理方式，以提针对不同的人群，制定不同的关系管理方式，以提高客户对公司商业活动的响应率。高客户对公司商业活动的响应率。第7页聚类分析无处不在聚类分析无处不在l挖掘有价值的客户，并制定相应的促销策略：挖掘有价值的客户，并制定相应的促销策略：如，对经常购买酸奶的客户如，对经常购买酸奶的客户对累计消费达到对累计消费达到12个月的老客户个月的老客户l针对潜在客户派发广告，比在大街上乱发传单命中针对潜在客户派发广告，比在大街上乱发传单命中率更高，成本更低！率更高，成本更低！第8页聚类分析无处不在聚类分析无处不在l谁是银行信用卡的黄金客户？谁是银行信用卡的黄金客户？利用储蓄额、刷卡消费金额、诚信度等变量对

5、客利用储蓄额、刷卡消费金额、诚信度等变量对客户分类，找出户分类，找出“黄金客户黄金客户”！这样银行可以这样银行可以制定更吸引的服务，留住客户！比如：制定更吸引的服务，留住客户！比如： 一定额度和期限的免息透资服务！一定额度和期限的免息透资服务！ 百盛的贵宾打折卡！百盛的贵宾打折卡！ 在他或她生日的时候送上一个小蛋糕！在他或她生日的时候送上一个小蛋糕！l手机套餐的制定手机套餐的制定第9页聚类的应用领域聚类的应用领域l经济领域：经济领域：帮助分析人员从客户数据库中发现不同的客户群，帮助分析人员从客户数据库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。并且用购买模式来刻画不同的客户群的

6、特征。谁喜欢打国际长途，在什么时间，打到那里？谁喜欢打国际长途，在什么时间，打到那里？对住宅区进行聚类，确定自动提款机对住宅区进行聚类，确定自动提款机ATM的安放的安放位置位置股票市场板块分析，找出最具活力的板块龙头股股票市场板块分析，找出最具活力的板块龙头股企业信用等级分类企业信用等级分类第10页l生物学领域生物学领域推导植物和动物的分类推导植物和动物的分类(门、纲、目、科、属、门、纲、目、科、属、种种)；对基因分类，获得对种群的认识对基因分类，获得对种群的认识l数据挖掘领域数据挖掘领域作为其他数学算法的预处理步骤，获得数据分布作为其他数学算法的预处理步骤，获得数据分布状况，集中对特定的类做

7、进一步的研究状况，集中对特定的类做进一步的研究第11页聚类分析原理介绍聚类分析原理介绍l聚类分析中聚类分析中“类类”的特征：的特征：聚类所说的类不是事先给定的，而是根据数据的聚类所说的类不是事先给定的，而是根据数据的相似性和距离来划分相似性和距离来划分聚类的数目和结构都没有事先假定聚类的数目和结构都没有事先假定第12页有多少个簇？四个簇2个簇6个簇簇簇(类类)的概念可能是模糊的的概念可能是模糊的如何对汉语方言进行分类？如何对汉语方言进行分类？第13页聚类分析原理介绍聚类分析原理介绍l我们看以下的例子：我们看以下的例子：l有有16张牌张牌l如何将他们分为如何将他们分为 一组一组的牌呢？一组一组的

8、牌呢？AKQJ第14页聚类分析原理介绍聚类分析原理介绍l分成四组分成四组l每组里每组里花色相同花色相同l组与组之间花色相异组与组之间花色相异AKQJ花色相同的牌为一副花色相同的牌为一副Individual suits第15页聚类分析原理介绍聚类分析原理介绍l分成四组分成四组l符号相同符号相同的牌为一组的牌为一组AKQJ符号相同的的牌符号相同的的牌Like face cards第16页聚类分析原理介绍聚类分析原理介绍l分成两组分成两组l颜色相同颜色相同的牌为一组的牌为一组AKQJ颜色相同的配对颜色相同的配对Black and red suits第17页聚类分析原理介绍聚类分析原理介绍l分成两组分

9、成两组l大小程度相近大小程度相近的牌分到的牌分到一组一组AKQJ大配对和小配对大配对和小配对Major and minor suits第18页聚类分析原理介绍聚类分析原理介绍l这个例子告诉我们，分这个例子告诉我们，分组的意义在于我们怎么组的意义在于我们怎么定义并度量定义并度量“相似性相似性” (Similar)l因此衍生出一系列度量因此衍生出一系列度量相似性的方法相似性的方法AKQJ大配对和小配对大配对和小配对Major and minor suits第19页聚类分析原理介绍聚类分析原理介绍变量按测量尺度（变量按测量尺度（Measurement Level）分类）分类l区间（区间（Interv

10、al）值变量）值变量连续变量，如长度、重量、速度、温度等连续变量，如长度、重量、速度、温度等l有序（有序（Ordinal）值变量）值变量等级变量，不可加，但可比，如一等、二等、三等级变量，不可加，但可比，如一等、二等、三等奖学金等奖学金l名词性（名词性（Nominal）变量）变量类别变量，不可加也不可比，如性别、职业等类别变量，不可加也不可比，如性别、职业等l下面介绍对各种不同类型的变量如何进行度量下面介绍对各种不同类型的变量如何进行度量第20页度量对象间的相似与差异度量对象间的相似与差异l对象间的对象间的相似度相似度或或相异度相异度通常基于每对对象间的距通常基于每对对象间的距离的计算离的计算

11、l欧几里得距离欧几里得距离lMinkowski距离距离qppjxixjxixjxixjid)|.|(|),(2222211qqppqqjxixjxixjxixjid)|.|(|),(2211第21页度量对象间的相似与差异度量对象间的相似与差异l曼哈顿距离曼哈顿距离(Block距离距离)l欧几里得距离是当欧几里得距离是当q=2时的时的Minkowski距离的特例距离的特例l曼哈顿距离是当曼哈顿距离是当q=1时的时的Minkowski距离的特例距离的特例l当当q= 时得到无穷距离时得到无穷距离(无穷范数无穷范数)，由向量间各分量，由向量间各分量的最大差决定的最大差决定|.|), (2211ppjx

12、ixjxixjxixjid第22页度量对象间的相似与差异度量对象间的相似与差异l距离所应满足的数学性质距离所应满足的数学性质d(i,j) 0d(i,i) = 0d(i,j) = d(j,i)d(i,j) d(i,k) + d(k,j)l除此之外，还可以使用除此之外，还可以使用加权加权的距离的距离第23页二元属性变量二元属性变量l二元变量只有两种状态：二元变量只有两种状态：0或或1例如给定描述患者的变量例如给定描述患者的变量smoker，1表示患者抽表示患者抽烟，烟，0表示不抽烟表示不抽烟l像处理一般数值量一样来处理二元变量会产生误导像处理一般数值量一样来处理二元变量会产生误导的聚类结果的聚类结

13、果第24页二元属性变量的相依表二元属性变量的相依表l如果所有的二元变量具有相同的权重，则可以得到如果所有的二元变量具有相同的权重，则可以得到上表所示的两行两列的相依表上表所示的两行两列的相依表q是对象是对象i和和j值都为值都为1的变量的数目的变量的数目r是在对象是在对象i值为值为1，但对象，但对象j值为值为0的变量数目的变量数目变量的总数是变量的总数是p=q+r+s+tptrsqsumtstsrqrqsum0101Object iObject j第25页对称二元变量和非对称二元变量对称二元变量和非对称二元变量l对二元变量的相异度计算还要考虑变量的对二元变量的相异度计算还要考虑变量的对称性对称性

14、l对称二元变量对称二元变量如果他的两个状态具有同等价值和相等的权重如果他的两个状态具有同等价值和相等的权重输出用输出用0或或1编码没有优先权，如性别编码没有优先权，如性别l对称二元相异度对称二元相异度tsrqsr jid),(第26页对称二元变量和非对称二元变量对称二元变量和非对称二元变量l非对称二元变量非对称二元变量如果状态的输出不是同等重要的如果状态的输出不是同等重要的例如基本检查的阳性和阴性结果。根据惯例，将例如基本检查的阳性和阴性结果。根据惯例，将比较重要的输出结果比较重要的输出结果(通常也是出现机率较小的结通常也是出现机率较小的结果果)编码为编码为1，而将另一种结果编码为，而将另一种

15、结果编码为0(如如HIV阴性阴性)给定两个非对称二元变量，两个都取值给定两个非对称二元变量，两个都取值1的情况认的情况认为比两个都取值为比两个都取值0的情况更有意义的情况更有意义l非对称二元相异度非对称二元相异度srqsr jid),(第27页对称二元变量和非对称二元变量对称二元变量和非对称二元变量l有时采用两个二元变量的有时采用两个二元变量的相似度相似度而不是而不是相异度相异度来测来测量他们之间的距离。量他们之间的距离。l非对称二元相似度非对称二元相似度sim(i,j)如下定义如下定义l系数系数sim(i,j)常称作常称作Jaccard系数系数),(1),(jidsrqq jisimJacc

16、ard第28页例例 二元变量之间的相异度二元变量之间的相异度l假设一个患者记录表包含上述属性，其中假设一个患者记录表包含上述属性，其中name是标是标识符，性别是对称二元属性，其余的属性都是非对识符，性别是对称二元属性，其余的属性都是非对称二元属性称二元属性l对于非对称属性，值对于非对称属性，值Y和和P(positive)置为置为1，值，值N(no或或negative)置为置为0第29页例例 二元变量之间的相异度二元变量之间的相异度l假设对象之间的距离只基于非对称变量来计算。根假设对象之间的距离只基于非对称变量来计算。根据公式，三个患者据公式，三个患者Jack、Mary和和Jim两两之间的两两

17、之间的相相异度异度如下：如下：l度量显示度量显示Jim和和Mary不大可能患相似的疾病，而不大可能患相似的疾病，而Jack和和Mary最可能患相似的疾病最可能患相似的疾病75.021121),(67.011111),(33.010210),( maryjimdjimjackdmaryjackd第30页名词性属性变量名词性属性变量l可取多个相异值，之间没有序关系可取多个相异值，之间没有序关系l如产品颜色可以取：红、黄、绿、蓝等如产品颜色可以取：红、黄、绿、蓝等也可以用也可以用0，1，2，3等代码来表示，但注意这里等代码来表示，但注意这里的数字仅是标识，不能做运算的数字仅是标识，不能做运算l两个对

18、象两个对象i和和j之间的相异度简单的处理方法是计算不之间的相异度简单的处理方法是计算不匹配率：匹配率：其中其中p是全部变量的数目，是全部变量的数目，m是匹配的数目是匹配的数目l也可以构造一个大的二元变量数组，再按二元变量也可以构造一个大的二元变量数组，再按二元变量处理处理pmpjid),(第31页余弦相似度余弦相似度l文档数据文档数据第32页l 在信息检索、文本文档聚类和生物学分类中，需要在信息检索、文本文档聚类和生物学分类中，需要对包含了大量符号实体的复杂对象进行比较和聚类对包含了大量符号实体的复杂对象进行比较和聚类l为了测量复杂对象间的距离，通常期望放弃传统的度为了测量复杂对象间的距离，通

19、常期望放弃传统的度量距离计算，而引入量距离计算，而引入非度量非度量的相似度函数的相似度函数l 如果如果d1 和和 d2 是两个文档向量，则是两个文档向量，则 cos( d1, d2 ) = (d1 d2) / |d1| |d2| , l 其中其中 表示向量的点积表示向量的点积(内积内积)，| d |表示向量的范表示向量的范数数.l问题：余弦相似度的范围？取最大值时是否两个向量问题：余弦相似度的范围？取最大值时是否两个向量相等？相等？余弦相似度余弦相似度第33页余弦相似度计算的例子余弦相似度计算的例子ld1 = 3 2 0 5 0 0 0 2 0 0 ld2 = 1 0 0 0 0 0 0 1

20、0 2 ld1 d2 = 3*1 + 2*0 + 0*0 + 5*0 + 0*0 + 0*0 + 0*0 + 2*1 + 0*0 + 0*2 = 5l|d1| = (3*3+2*2+0*0+5*5+0*0+0*0+0*0+2*2+0*0+0*0)0.5 = (42) 0.5 = 6.481l|d2| = (1*1+0*0+0*0+0*0+0*0+0*0+0*0+1*1+0*0+2*2) 0.5 = (6) 0.5 = 2.245lcos( d1, d2 ) = 5/(6.481*2.245).3150第34页如何选择恰当的度量如何选择恰当的度量l有很多方法用来选择一个具体的相似度或距离函数，有

21、很多方法用来选择一个具体的相似度或距离函数，但是还没有一个通用的标准用来指导这样的选择但是还没有一个通用的标准用来指导这样的选择l这种度量的选择高度依赖于具体的应用。这种度量的选择高度依赖于具体的应用。第35页主要聚类方法的分类主要聚类方法的分类l划分方法划分方法：给定：给定n个对象，划分方法构建数据的个对象，划分方法构建数据的k个个划分，每个划分表示一簇，划分，每个划分表示一簇，k=n，满足如下要求，满足如下要求每组至少包含一个对象每组至少包含一个对象每个对象必须只属于一个组每个对象必须只属于一个组(在软聚类技术中可放在软聚类技术中可放宽宽)l对于给定的划分数目对于给定的划分数目k，通常创建

22、一个初始划分，然，通常创建一个初始划分，然后采用迭代方法尝试通过对象在组间移动来改进划后采用迭代方法尝试通过对象在组间移动来改进划分分第36页主要聚类方法的分类主要聚类方法的分类l好的划分的标准：同一个簇中的对象之间尽可能相好的划分的标准：同一个簇中的对象之间尽可能相似，不同簇的对象尽可能有大的差异似，不同簇的对象尽可能有大的差异l常用方法：常用方法：k均值方法：每个簇都用该簇中对象的均值来表示均值方法：每个簇都用该簇中对象的均值来表示k中心点法：每个簇用接近簇中心的一个对象来表中心点法：每个簇用接近簇中心的一个对象来表示示第37页l层次方法创建给定数据对象的层次分解层次方法创建给定数据对象的

23、层次分解l根据使用的方法，层次的方法可以分类为凝聚的或根据使用的方法，层次的方法可以分类为凝聚的或分裂的方法分裂的方法凝聚法：也称自底向上的方法，开始将每个对象凝聚法：也称自底向上的方法，开始将每个对象形成单独的组，然后逐次合并相近的对象或组，形成单独的组，然后逐次合并相近的对象或组，直到所有的组合并为一个或满足某个终止条件直到所有的组合并为一个或满足某个终止条件分裂法：自顶向下的方法，一开始将所有对象置分裂法：自顶向下的方法，一开始将所有对象置于一个簇中，每次迭代，簇分裂为更小的簇，直于一个簇中，每次迭代，簇分裂为更小的簇，直到每个对象在一个簇中或满足终止条件到每个对象在一个簇中或满足终止条

24、件层次方法层次方法第38页基于模型的方法基于模型的方法l为每簇假定一个模型，并寻找数据对给定模型的最为每簇假定一个模型，并寻找数据对给定模型的最 佳拟合佳拟合l常见算法常见算法EM算法：基于统计模型并进行期望最大化分析算法：基于统计模型并进行期望最大化分析COBWEB：概念学习算法，进行概率分析并把概：概念学习算法，进行概率分析并把概念作为簇模型念作为簇模型SOM(自组织映射自组织映射)：一种基于神经网络的算法，：一种基于神经网络的算法，通过把高维数据映射到通过把高维数据映射到2维或维或3维特征空间进行聚维特征空间进行聚类类第39页划分聚类划分聚类原始点原始点划分聚类划分聚类第40页层次聚类层

25、次聚类p4p1p3p2 p4 p1 p3 p2 p4p1p2p3p4p1 p2p3Traditional Hierarchical ClusteringNon-traditional Hierarchical ClusteringNon-traditional DendrogramTraditional Dendrogram第41页l互斥的与非互斥的互斥的与非互斥的在非互斥聚类中，点可以属于多个簇在非互斥聚类中，点可以属于多个簇.可以表示多重类或边界类可以表示多重类或边界类l模糊聚类与非模糊聚类模糊聚类与非模糊聚类模糊聚类中，一个点到隶属于每个簇的情况可模糊聚类中，一个点到隶属于每个簇的情况可

26、以用一个在以用一个在0到到1之间的隶属度描述之间的隶属度描述其他的聚类类型的差别其他的聚类类型的差别第42页不同的簇类型不同的簇类型l明显分离的簇明显分离的簇l基于中心的簇基于中心的簇l基于近邻的簇基于近邻的簇l基于密度的簇基于密度的簇l概念簇概念簇第43页不同的簇类型不同的簇类型l明显分离的簇明显分离的簇: 每个点到同簇中任意点的距离比到不同簇中所每个点到同簇中任意点的距离比到不同簇中所有点的距离更近有点的距离更近3 个明显分离的簇个明显分离的簇第44页不同的簇类型不同的簇类型l基于中心的簇基于中心的簇 每个点到其簇中心的距离比到任何其他簇中心每个点到其簇中心的距离比到任何其他簇中心的距离更

27、近的距离更近 簇的中心通常是重心，簇中所有点的平均值，簇的中心通常是重心，簇中所有点的平均值，或者是簇的原型，即一个簇中最具代表性的点或者是簇的原型，即一个簇中最具代表性的点4 center-based clusters第45页不同的簇类型不同的簇类型l基于近邻的簇基于近邻的簇(基于图的基于图的连通分支连通分支)每个点到该簇中至少一个点的距离比到不同簇每个点到该簇中至少一个点的距离比到不同簇中任意点的距离更近中任意点的距离更近8 contiguous clusters第46页不同的簇类型不同的簇类型l基于密度的簇基于密度的簇簇是被低密度区域分开的高密度区域簇是被低密度区域分开的高密度区域. 当

28、簇不规则或互相盘绕，并且有噪声和离群点当簇不规则或互相盘绕，并且有噪声和离群点时，通常使用基于密度的簇定义时，通常使用基于密度的簇定义6 density-based clusters第47页划分方法划分方法l对于一个给定的对于一个给定的n个对象或元组的数据库，采用目标个对象或元组的数据库，采用目标函数最小化的策略，通过迭代把数据分成函数最小化的策略，通过迭代把数据分成k个划分块，个划分块，每个划分块为一个簇，这就是划分方法。每个划分块为一个簇，这就是划分方法。 l划分方法满足两个条件：划分方法满足两个条件：（1）每个分组至少包含一个对象；）每个分组至少包含一个对象；（2）每个对象必属于且仅属于

29、某一个分组。）每个对象必属于且仅属于某一个分组。 l常见的划分方法有常见的划分方法有k-均值方法和均值方法和k-中心点方法。其他中心点方法。其他方法大都是这两种方法的变形。方法大都是这两种方法的变形。 第48页k-均值算法均值算法 lk-均值聚类算法的核心思想是通过迭代把数据对象划均值聚类算法的核心思想是通过迭代把数据对象划分到不同的簇中，以求分到不同的簇中，以求目标函数目标函数最小化，从而使生最小化，从而使生成的簇尽可能地紧凑和独立。成的簇尽可能地紧凑和独立。随机选取随机选取k个对象作为初始的个对象作为初始的k个簇的质心；个簇的质心；将其余对象根据其与各个簇质心的距离分配到最将其余对象根据其

30、与各个簇质心的距离分配到最近的簇；再求新形成的簇的质心。近的簇；再求新形成的簇的质心。这个迭代重定位过程不断重复，直到目标函数最这个迭代重定位过程不断重复，直到目标函数最小化为止。小化为止。 第49页k-均值算法均值算法 算法算法输入输入输出输出方法方法1234K均值均值K：簇的数目：簇的数目D：包含：包含n个对象的点集个对象的点集K个簇的集合个簇的集合从从D中任意选择中任意选择K个点作为初始簇中心个点作为初始簇中心Repeat根据簇中对象的均值，将每个对象再指派到最相似的簇根据簇中对象的均值，将每个对象再指派到最相似的簇更新簇均值，即计算每个簇中对象的均值更新簇均值，即计算每个簇中对象的均值

31、第50页-2-1.5-1-0.500.511.5200.511.522.53xyIteration 1-2-1.5-1-0.500.511.5200.511.522.53xyIteration 2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5-2-1.5-1-0.500.511.5200.511.522.53xyIteration 6初始质心的选择非常重要初始质

32、心的选择非常重要第51页-2-1.5-1-0.500.511.5200.511.522.53xyIteration 1-2-1.5-1-0.500.511.5200.511.522.53xyIteration 2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5-2-1.5-1-0.500.511.5200.511.522.53xyIteration 6使用使用K均

33、值算法的迭代过程均值算法的迭代过程第52页K-K-均值算法均值算法 012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2Arbitrarily choose K object as initial cluster centerAssign each objects to most similar centerUpdate the cluster meansUpdate the cluster means

34、reassignreassign第53页欧几里得空间中的数据欧几里得空间中的数据l通常使用误差的平方和通常使用误差的平方和(sum of the squared error, SSE)作为度量聚类质量的目标函数作为度量聚类质量的目标函数lSSE也称散布也称散布(scatter)：计算每个数据点的误差：计算每个数据点的误差即它到最近质心的欧几里得距离，然后计算误差的即它到最近质心的欧几里得距离，然后计算误差的 平方和平方和l给定由两次运行给定由两次运行K均值产生的两个不同的簇集，我们均值产生的两个不同的簇集，我们更喜欢误差的平方和最小的那个，这意味着聚类的更喜欢误差的平方和最小的那个，这意味着聚

35、类的 原型原型(质心质心)是簇中点的更好代表是簇中点的更好代表KiCxiixmdistSSE12),(第54页欧几里得空间中的数据欧几里得空间中的数据l可以证明在欧几里得空间中是簇的可以证明在欧几里得空间中是簇的SSE最小的质心最小的质心 就是均值就是均值lK均值算法的第均值算法的第3步和第步和第4步试图直接最小化步试图直接最小化SSE步骤步骤3通过将点指派到最近的质心形成簇，最小化通过将点指派到最近的质心形成簇，最小化关于给定质心集的关于给定质心集的SSE步骤步骤4重新计算质心，进一步最小化重新计算质心，进一步最小化SSEl问题：问题：K均值的步骤均值的步骤3和和4只能找到关于只能找到关于S

36、SE的的局部最局部最小值小值，因为它们是对选定的质心和簇，而不是对，因为它们是对选定的质心和簇，而不是对 所所有可能的选择来优化有可能的选择来优化SSE第55页-2-1.5-1-0.500.511.5200.511.522.53xyIteration 1-2-1.5-1-0.500.511.5200.511.522.53xyIteration 2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.

37、53xyIteration 5初始质心的选择非常重要初始质心的选择非常重要第56页-2-1.5-1-0.500.511.5200.511.522.53xyIteration 1-2-1.5-1-0.500.511.5200.511.522.53xyIteration 2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5初始质心的选择非常重要初始质心的选择非常重要第5

38、7页随机初始化随机初始化l由于由于K均值算法会陷入局部最小值而得到次优聚类，均值算法会陷入局部最小值而得到次优聚类，一种常用的选取初始质心的方法是多次运行，每次一种常用的选取初始质心的方法是多次运行，每次使用一组不同的随机初始质心，然后选取具有最小使用一组不同的随机初始质心，然后选取具有最小SSE的簇集的簇集l下面我们看一看这种方法的问题下面我们看一看这种方法的问题l下页的图中有下页的图中有5个簇对，每个簇对有上下两个簇。个簇对，每个簇对有上下两个簇。如果每个簇对有两个初始质心，则效果较好如果每个簇对有两个初始质心，则效果较好如果有一个簇对中只有一个初始中心，而另一个如果有一个簇对中只有一个初

39、始中心，而另一个簇对中有三个初始中心，则会出现错误。簇对中有三个初始中心，则会出现错误。第58页05101520-6-4-202468xyIteration 105101520-6-4-202468xyIteration 205101520-6-4-202468xyIteration 305101520-6-4-202468xyIteration 4Starting with two initial centroids in one cluster of each pair of clusters5个簇对，个簇对，10个簇的例子个簇的例子第59页05101520-6-4-202468xyIte

40、ration 105101520-6-4-202468xyIteration 205101520-6-4-202468xyIteration 305101520-6-4-202468xyIteration 4Starting with two initial centroids in one cluster of each pair of clusters5个簇对，个簇对，10个簇的例子个簇的例子第60页Starting with some pairs of clusters having three initial centroids, while other have only one.0

41、5101520-6-4-202468xyIteration 105101520-6-4-202468xyIteration 205101520-6-4-202468xyIteration 305101520-6-4-202468xyIteration 45个簇对，个簇对，10个簇的例子个簇的例子第61页Starting with some pairs of clusters having three initial centroids, while other have only one.05101520-6-4-202468xyIteration 105101520-6-4-202468xy

42、Iteration 205101520-6-4-202468xyIteration 305101520-6-4-202468xyIteration 45个簇对，个簇对，10个簇的例子个簇的例子第62页解决初始质心设置问题的方法解决初始质心设置问题的方法l多次运行多次运行不一定总有效不一定总有效l对数据作采样并使用层次聚类，从中提取对数据作采样并使用层次聚类，从中提取K个簇并使个簇并使用这些簇的质心作为初始质心用这些簇的质心作为初始质心l选取多于选取多于k个的初始质心，然后从其中选择个的初始质心，然后从其中选择k个个最分离的最分离的k个点个点l后处理后处理l二分二分K-均值均值第63页二分二分K

43、均值均值l基本思想：基本思想：l为了得到为了得到K个簇，将所有点的集合分裂成两个簇，从个簇，将所有点的集合分裂成两个簇，从这些簇中选取一个继续分裂，如此下去直到产生这些簇中选取一个继续分裂，如此下去直到产生K个个簇簇l可以使用多种方法选择待分裂的簇可以使用多种方法选择待分裂的簇最大的簇最大的簇具有最大具有最大SSE的簇的簇基于大小和基于大小和SSEl二分二分K均值得到的最终的簇集并不代表使均值得到的最终的簇集并不代表使SSE局部最局部最小的聚类小的聚类第64页二分二分K均值算法均值算法算法算法12345678910二分二分K均值均值初始化簇表，使之包含有所有的点组成的簇初始化簇表，使之包含有所

44、有的点组成的簇Repeat从簇表中取出一个簇从簇表中取出一个簇对选定的簇进行多次二分试验对选定的簇进行多次二分试验for i=1 to 试验次数试验次数 do 使用基本使用基本K均值，二分选定的簇均值，二分选定的簇end for从二分试验中选择具有最小总从二分试验中选择具有最小总SSE的两个簇的两个簇将这两个簇添加到簇表中将这两个簇添加到簇表中until 簇表中包含簇表中包含K个簇个簇第65页二分二分K-均值的例子均值的例子第66页K-均值方法的缺陷均值方法的缺陷lK-均值方法当簇在下述方面有较大不同时会出现问均值方法当簇在下述方面有较大不同时会出现问题题 不同大小不同大小不同密度不同密度非球

45、形的形状非球形的形状第67页Original PointsK-means (3 Clusters)K-均值的缺陷：不同的簇大小均值的缺陷：不同的簇大小WHY？第68页Original PointsK-means (3 Clusters)K-均值的缺陷均值的缺陷不同的密度分布不同的密度分布WHY？第69页Original PointsK-means (2 Clusters)K均值的缺陷：非球形形状均值的缺陷：非球形形状K均值目标函数是最小化等尺度和等密度的球形簇，或明显分均值目标函数是最小化等尺度和等密度的球形簇，或明显分离的簇离的簇第70页Original PointsK-means Clus

46、ters一种方法是使用更多的簇，再反过来使其部分合并一种方法是使用更多的簇，再反过来使其部分合并克服克服K均值方法的缺陷均值方法的缺陷第71页Original PointsK-means Clusters克服克服K均值方法的缺陷均值方法的缺陷第72页Original PointsK-means Clusters克服克服K均值方法的缺陷均值方法的缺陷第73页层次聚类方法层次聚类方法l定义：对给定的数据进行层次的分解：定义：对给定的数据进行层次的分解：l凝聚的（凝聚的（agglomerative）方法（自底向上）方法（自底向上）思想：一开始将每个对象作为单独的一组，然后思想：一开始将每个对象作为单

47、独的一组，然后根据同类相近，异类相异的原则，合并对象，直根据同类相近，异类相异的原则，合并对象，直到所有的组合并成一个，或达到一个终止条件为到所有的组合并成一个，或达到一个终止条件为止。止。l分裂的方法（分裂的方法（divisive）（自顶向下）（自顶向下）思想：一开始将所有的对象置于一类，在迭代的思想：一开始将所有的对象置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每每一步中，一个类不断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终止条件。个对象在单独的一个类中，或达到一个终止条件。 第74页凝聚的和分裂的层次聚类凝聚的和分裂的层次聚类 a, b, c, d, e c

48、, d, e d, e a, b e d c b a 第 4 步 第 3 步 第 2 步 第 1 步 第 0 步 凝聚的（AGENS） 第 0 步 第 1 步 第 2 步 第 3 步 第 4 步 分裂的（DIANA） 第75页层次聚类方法层次聚类方法l产生一个相邻簇的集合，通常用一棵树来表示产生一个相邻簇的集合，通常用一棵树来表示lCan be visualized as a dendrogram树状图记录了分裂或合并的序列树状图记录了分裂或合并的序列13254600.050.10.150.212345612345以树状图和嵌套簇图显示的以树状图和嵌套簇图显示的4个点的层次聚类个点的层次聚类第

49、76页层次聚类法的特点层次聚类法的特点l不用预知不用预知(预设预设)簇的数目簇的数目任何需要簇数的聚类可以通过在树状图的适当层任何需要簇数的聚类可以通过在树状图的适当层次切割而得到次切割而得到l得到更有意义的结构得到更有意义的结构如生物学中的分类如生物学中的分类l传统的层次聚类算法使用相似度矩阵或距离矩阵传统的层次聚类算法使用相似度矩阵或距离矩阵每次合并或分裂一个簇每次合并或分裂一个簇第77页1 计算距离矩阵计算距离矩阵2 令每个点为一个簇令每个点为一个簇3 Repeat4 合并最接近的两个簇合并最接近的两个簇5 更新距离矩阵更新距离矩阵6 until 仅剩下一个簇仅剩下一个簇基本凝聚层次聚类

50、算法基本凝聚层次聚类算法第78页l关键步骤在于计算两个簇之间的邻近度关键步骤在于计算两个簇之间的邻近度 不同的定义簇之间的距离的方法区分了不同的不同的定义簇之间的距离的方法区分了不同的算法算法基本凝聚层次聚类算法基本凝聚层次聚类算法第79页开始开始.l每个点为一个簇，计算各个簇两两之间的距离矩阵每个点为一个簇，计算各个簇两两之间的距离矩阵p1p3p5p4p2p1p2p3p4p5. . .距离矩阵距离矩阵第80页接下来接下来.l经过若干凝聚步骤，得到如下的簇经过若干凝聚步骤，得到如下的簇 C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5距离矩阵距离矩阵第81页接下来接下来.l合并两个

51、最靠近的簇合并两个最靠近的簇 (C2 和和 C5) 并更新距离矩阵并更新距离矩阵C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5距离矩阵距离矩阵第82页合并后合并后l问题变为如何更新距离矩阵问题变为如何更新距离矩阵C1C4C2 U C5C3? ? ? ? ?C2 U C5C1C1C3C4C2 U C5C3C4距离矩阵距离矩阵第83页 p1p3p5p4p2p1p2p3p4p5. . .距离距离lMIN(单链单链)lMAX(全链全链)lGroup Average(组平均组平均)l质心的距离质心的距离l其他的源自目标函数的方法其他的源自目标函数的方法Ward方法使用平方差方法使用平方差距

52、离矩阵距离矩阵如何定义簇之间的邻近度如何定义簇之间的邻近度第84页 p1p3p5p4p2p1p2p3p4p5. . .距离矩阵距离矩阵lMIN(单链单链)lMAX(全链全链)lGroup Average(组平均组平均)l质心的距离质心的距离l其他的源自目标函数的方法其他的源自目标函数的方法Ward方法使用平方差方法使用平方差如何定义簇之间的邻近度如何定义簇之间的邻近度第85页 p1p3p5p4p2p1p2p3p4p5. . .距离矩阵距离矩阵lMIN(单链单链)lMAX(全链全链)lGroup Average(组平均组平均)l质心的距离质心的距离l其他的源自目标函数的方法其他的源自目标函数的方

53、法Ward方法使用平方差方法使用平方差如何定义簇之间的邻近度如何定义簇之间的邻近度第86页 p1p3p5p4p2p1p2p3p4p5. . .距离矩阵距离矩阵lMIN(单链单链)lMAX(全链全链)lGroup Average(组平均组平均)l质心的距离质心的距离l其他的源自目标函数的方法其他的源自目标函数的方法Ward方法使用平方差方法使用平方差如何定义簇之间的邻近度如何定义簇之间的邻近度第87页 p1p3p5p4p2p1p2p3p4p5. . .距离矩阵距离矩阵 lMIN(单链单链)lMAX(全链全链)lGroup Average(组平均组平均)l质心的距离质心的距离l其他的源自目标函数的

54、方法其他的源自目标函数的方法Ward方法使用平方差方法使用平方差如何定义簇之间的邻近度如何定义簇之间的邻近度第88页MIN或单链或单链l两个簇之间的邻近度基于两个簇中最近的两个点的两个簇之间的邻近度基于两个簇中最近的两个点的距离距离由一个点对决定，或者说由图中的一条链决定由一个点对决定，或者说由图中的一条链决定I1I2I3I4I5I1 1.00 0.90 0.10 0.65 0.20I2 0.90 1.00 0.70 0.60 0.50I3 0.10 0.70 1.00 0.40 0.30I4 0.65 0.60 0.40 1.00 0.80I5 0.20 0.50 0.30 0.80 1.0

55、012345第89页Nested ClustersDendrogram1234561234536254100.050.10.150.2层次聚类层次聚类: MIN第90页Original PointsTwo Clusters可以处理非椭圆的形状可以处理非椭圆的形状MIN的优点的优点第91页Original PointsTwo Clusters 对噪声点和离群点很敏感对噪声点和离群点很敏感MIN的不足的不足第92页MAX或全链或全链l两个簇之间的邻近度由两个簇间最不相似的两个簇之间的邻近度由两个簇间最不相似的(最大距最大距离的离的)点对决定点对决定由两个簇中所有的点对决定由两个簇中所有的点对决定I

56、1I2I3I4I5I1 1.00 0.90 0.10 0.65 0.20I2 0.90 1.00 0.70 0.60 0.50I3 0.10 0.70 1.00 0.40 0.30I4 0.65 0.60 0.40 1.00 0.80I5 0.20 0.50 0.30 0.80 1.0012345第93页Nested ClustersDendrogram36412500.050.10.150.20.250.30.350.412345612534MAX或全链或全链第94页Original PointsTwo Clusters对噪声点和离群点不太敏感对噪声点和离群点不太敏感MAX的优点的优点第95

57、页Original PointsTwo Clusters倾向于分裂大的簇倾向于分裂大的簇倾向于球状的簇倾向于球状的簇MAX的不足的不足第96页组平均组平均l两个簇的邻近度定义为不同簇的所有点对的平均逐对邻近度两个簇的邻近度定义为不同簇的所有点对的平均逐对邻近度lNeed to use average connectivity for scalability since total proximity favors large clusters|Cluster|Cluster)p,pproximity()Cluster,Clusterproximity(jiClusterpClusterpjij

58、ijjiiI1I2I3I4I5I1 1.00 0.90 0.10 0.65 0.20I2 0.90 1.00 0.70 0.60 0.50I3 0.10 0.70 1.00 0.40 0.30I4 0.65 0.60 0.40 1.00 0.80I5 0.20 0.50 0.30 0.80 1.0012345第97页Nested ClustersDendrogram36412500.050.10.150.20.2512345612534组平均组平均第98页组平均组平均l是单链和全链之间的一个折中，该法利用了所有样是单链和全链之间的一个折中，该法利用了所有样本的信息，被认为是较好的层次聚类法本的

59、信息，被认为是较好的层次聚类法l优点优点 对噪声和离群点不太敏感对噪声和离群点不太敏感l不足不足 倾向于球状的簇倾向于球状的簇第99页 Ward方法和质心方法方法和质心方法l两个簇的邻近度定义为两个簇合并时导致的平方误两个簇的邻近度定义为两个簇合并时导致的平方误差的增量，该方法使用的目标函数与差的增量，该方法使用的目标函数与K均值相同均值相同可以证明，当取距离的平方作为两个点间的邻近可以证明，当取距离的平方作为两个点间的邻近度时，度时，Ward方法与组平均方法相似方法与组平均方法相似l对噪声和离群点不太敏感对噪声和离群点不太敏感l倾向于球状的簇倾向于球状的簇l可以用来初始化可以用来初始化K均值

60、方法均值方法第100页层次聚类法：比较层次聚类法：比较Group AverageWards Method12345612534MINMAX123456125341234561253412345612345第101页lO(N2) 空间复杂度，因为要存储邻近度矩阵，空间复杂度，因为要存储邻近度矩阵，N为点为点的数目的数目l最坏情况下最坏情况下O(N3) 的时间复杂度的时间复杂度共有共有N步，在每一步中要更新和搜索步，在每一步中要更新和搜索N2规模的邻规模的邻近度矩阵近度矩阵在某些算法中可以接近在某些算法中可以接近O(N2 log(N) ) 的时间复杂的时间复杂度度层次聚类：时间和空间复杂度层次聚类

61、：时间和空间复杂度第102页层次聚类方法的优缺点层次聚类方法的优缺点l层次聚类方法的优点在于可以在不同粒度水平上对层次聚类方法的优点在于可以在不同粒度水平上对数据进行探测，而且容易实现相似度量或距离度量。数据进行探测，而且容易实现相似度量或距离度量。 l单纯的层次聚类算法终止条件含糊，而且执行合并单纯的层次聚类算法终止条件含糊，而且执行合并或分裂簇的操作后不可修正，这很可能导致聚类结或分裂簇的操作后不可修正，这很可能导致聚类结果质量很低。果质量很低。l通常考虑把层次聚类方法与其他方法（如迭代重定通常考虑把层次聚类方法与其他方法（如迭代重定位方法）相结合来解决实际聚类问题。位方法）相结合来解决实

62、际聚类问题。 第103页lDBSCAN是一种基于密度的聚类算法是一种基于密度的聚类算法 密度密度 = 给定半径给定半径(Eps)内点的数目内点的数目 核心点核心点(core point ) 在半径在半径Eps的邻域内拥有的邻域内拥有多于特定数目多于特定数目(MinPts)的邻点的点，在基于密的邻点的点，在基于密度的簇内部的点度的簇内部的点 边界点边界点(border point )在半径在半径Eps的邻域内拥的邻域内拥有多于特定数目有多于特定数目(MinPts)的邻点的点，但是落的邻点的点，但是落在某个核心点的邻域内在某个核心点的邻域内 噪声点噪声点(noise point )既非核心点也非边

63、界点既非核心点也非边界点的任何点的任何点基于密度的聚类：基于密度的聚类：DBSCAN第104页DBSCAN: 核心点，边界点和噪声点核心点，边界点和噪声点第105页DBSCAN 算法算法l算法算法1：将所有点标记为核心点、边界点或噪声点：将所有点标记为核心点、边界点或噪声点2：删除噪声点：删除噪声点3：为距离在：为距离在Eps之内的所有核心点之间赋予一条之内的所有核心点之间赋予一条边边4：每组连通的核心点形成一个簇：每组连通的核心点形成一个簇将每个边界点指派到一个与之关联的核心点的簇将每个边界点指派到一个与之关联的核心点的簇中中第106页原始点原始点点的类型点的类型: 核心核心, 边界边界 和

64、和噪声噪声Eps = 10, MinPts = 4DBSCAN 算法算法第107页原始点原始点得到的簇得到的簇 对噪声不敏感对噪声不敏感 可以处理不同形状和大小的簇可以处理不同形状和大小的簇当当DBSCAN工作良好时工作良好时第108页原始点集原始点集(MinPts=4, Eps=9.75). (MinPts=4, Eps=9.92) 变密度的簇变密度的簇 对高维数据计算量巨大对高维数据计算量巨大当当DBSCAN工作不佳时工作不佳时第109页l基本方法：观察点到它的基本方法：观察点到它的k个最近邻的距离个最近邻的距离(称作称作k-距离距离)。对于属于某个簇的点，如果。对于属于某个簇的点，如果k

65、不大于簇不大于簇的大小的话，则的大小的话，则k-距离将很接近距离将很接近l噪声点由于不在簇中，其噪声点由于不在簇中，其k-距离将相对较大距离将相对较大l对于某个对于某个k，计算所有点的，计算所有点的k-距离，以递增次序将距离，以递增次序将它们排序，然后绘制排序后的值，则预期会看到它们排序，然后绘制排序后的值，则预期会看到k-距离的急剧变化处对应于合适的距离的急剧变化处对应于合适的Eps值值DBSCAN算法算法: 确定确定EPS和和 MinPts第110页DBSCAN算法算法: 确定确定EPS和和 MinPts第111页簇评估簇评估 l对于有监督的分类，我们可以有多种方式评价模型对于有监督的分类

66、，我们可以有多种方式评价模型的优劣的优劣准确度准确度, 精度精度, 召回率召回率l对于聚类分析对于聚类分析, 相应的问题是如何评价聚类结果是否相应的问题是如何评价聚类结果是否是是 “好好”的的l评估簇的目的评估簇的目的避免寻找噪声中的模式避免寻找噪声中的模式比较不同的聚类算法比较不同的聚类算法比较两个聚类的结果比较两个聚类的结果比较两个簇比较两个簇第112页在随机数据中发现的簇在随机数据中发现的簇00.20.40.60.8100.10.20.30.40.50.60.70.80.91xy100个个随机分随机分布的点布的点00.20.40.60.8100.10.20.30.40.50.60.70.80.91xyK-均值均值00.20.40.60.8100.10.20.30.40.50.60.70.80.91xyDBSCAN00.20.40.60.8100.10.20.30.40.50.60.70.80.91xy全链聚类全链聚类第113页1. 确定数据的聚类趋势确定数据的聚类趋势( clustering tendency ), 即即识别数据中是否实际存在非随机结构识别数据中是否实际存在非随机