第6章聚类分析ppt课件.ppt

《第6章聚类分析ppt课件.ppt》由会员分享，可在线阅读，更多相关《第6章聚类分析ppt课件.ppt（168页珍藏版）》请在三一办公上搜索。

1、第1页,第5章 聚类分析,本章概述 本章的学习目标主要内容,第2页,什么是聚类,聚类（Clustering）就是将数据分组成为多个类（Cluster或译为簇）。在同一个类内对象之间具有较高的相似度，不同类之间的对象差别较大。,第3页,从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程。与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。,第4页,什么是聚类,早在孩提时代，人就通过不断改进下意识中的聚类模式来学会如何区分猫和狗，动物和植物将周围的人分为家人和非家人,第5页,聚类分析无处不在,谁经常光顾

2、商店，谁买什么东西，买多少？按忠诚卡记录的光临次数、光临时间、性别、年龄、职业、购物种类、金额等变量分类这样商店可以.识别顾客购买模式（如喜欢一大早来买酸奶和鲜肉，习惯周末时一次性大采购）刻画不同的客户群的特征（用变量来刻画，就象刻画猫和狗的特征一样）,第6页,什么情况下需要聚类,为什么这样分类？因为每一个类别里面的人消费方式都不一样，需要针对不同的人群，制定不同的关系管理方式，以提高客户对公司商业活动的响应率。,第7页,聚类分析无处不在,挖掘有价值的客户，并制定相应的促销策略：如，对经常购买酸奶的客户对累计消费达到12个月的老客户针对潜在客户派发广告，比在大街上乱发传单命中率更高，成本更低！

3、,第8页,聚类分析无处不在,谁是银行信用卡的黄金客户？利用储蓄额、刷卡消费金额、诚信度等变量对客户分类，找出“黄金客户”！这样银行可以制定更吸引的服务，留住客户！比如：一定额度和期限的免息透资服务！百盛的贵宾打折卡！在他或她生日的时候送上一个小蛋糕！手机套餐的制定,第9页,聚类的应用领域,经济领域：帮助分析人员从客户数据库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。谁喜欢打国际长途，在什么时间，打到那里？对住宅区进行聚类，确定自动提款机ATM的安放位置股票市场板块分析，找出最具活力的板块龙头股企业信用等级分类,第10页,生物学领域推导植物和动物的分类(门、纲、目、科、属、种)；

4、对基因分类，获得对种群的认识数据挖掘领域作为其他数学算法的预处理步骤，获得数据分布状况，集中对特定的类做进一步的研究,第11页,聚类分析原理介绍,聚类分析中“类”的特征：聚类所说的类不是事先给定的，而是根据数据的相似性和距离来划分聚类的数目和结构都没有事先假定,第12页,簇(类)的概念可能是模糊的,如何对汉语方言进行分类？,第13页,聚类分析原理介绍,我们看以下的例子：有16张牌如何将他们分为 一组一组的牌呢？,第14页,聚类分析原理介绍,分成四组每组里花色相同组与组之间花色相异,花色相同的牌为一副Individual suits,第15页,聚类分析原理介绍,分成四组符号相同的牌为一组,符号相

5、同的的牌Like face cards,第16页,聚类分析原理介绍,分成两组颜色相同的牌为一组,颜色相同的配对Black and red suits,第17页,聚类分析原理介绍,分成两组大小程度相近的牌分到一组,大配对和小配对Major and minor suits,第18页,聚类分析原理介绍,这个例子告诉我们，分组的意义在于我们怎么定义并度量“相似性”(Similar)因此衍生出一系列度量相似性的方法,大配对和小配对Major and minor suits,第19页,聚类分析原理介绍,变量按测量尺度（Measurement Level）分类区间（Interval）值变量连续变量，如长度、

6、重量、速度、温度等有序（Ordinal）值变量等级变量，不可加，但可比，如一等、二等、三等奖学金名词性（Nominal）变量类别变量，不可加也不可比，如性别、职业等下面介绍对各种不同类型的变量如何进行度量,第20页,度量对象间的相似与差异,对象间的相似度或相异度通常基于每对对象间的距离的计算欧几里得距离Minkowski距离,第21页,度量对象间的相似与差异,曼哈顿距离(Block距离)欧几里得距离是当q=2时的Minkowski距离的特例曼哈顿距离是当q=1时的Minkowski距离的特例当q=时得到无穷距离(无穷范数)，由向量间各分量的最大差决定,第22页,度量对象间的相似与差异,距离所应

7、满足的数学性质d(i,j)0d(i,i)=0d(i,j)=d(j,i)d(i,j)d(i,k)+d(k,j)除此之外，还可以使用加权的距离,第23页,二元属性变量,二元变量只有两种状态：0或1例如给定描述患者的变量smoker，1表示患者抽烟，0表示不抽烟像处理一般数值量一样来处理二元变量会产生误导的聚类结果,第24页,二元属性变量的相依表,如果所有的二元变量具有相同的权重，则可以得到上表所示的两行两列的相依表q是对象i和j值都为1的变量的数目r是在对象i值为1，但对象j值为0的变量数目变量的总数是p=q+r+s+t,第25页,对称二元变量和非对称二元变量,对二元变量的相异度计算还要考虑变量的

8、对称性对称二元变量如果他的两个状态具有同等价值和相等的权重输出用0或1编码没有优先权，如性别对称二元相异度,第26页,对称二元变量和非对称二元变量,非对称二元变量如果状态的输出不是同等重要的例如基本检查的阳性和阴性结果。根据惯例，将比较重要的输出结果(通常也是出现机率较小的结果)编码为1，而将另一种结果编码为0(如HIV阴性)给定两个非对称二元变量，两个都取值1的情况认为比两个都取值0的情况更有意义非对称二元相异度,第27页,对称二元变量和非对称二元变量,有时采用两个二元变量的相似度而不是相异度来测量他们之间的距离。非对称二元相似度sim(i,j)如下定义系数sim(i,j)常称作Jaccar

9、d系数,第28页,例 二元变量之间的相异度,假设一个患者记录表包含上述属性，其中name是标识符，性别是对称二元属性，其余的属性都是非对称二元属性对于非对称属性，值Y和P(positive)置为1，值N(no或negative)置为0,第29页,例 二元变量之间的相异度,假设对象之间的距离只基于非对称变量来计算。根据公式，三个患者Jack、Mary和Jim两两之间的相异度如下：度量显示Jim和Mary不大可能患相似的疾病，而Jack和Mary最可能患相似的疾病,第30页,名词性属性变量,可取多个相异值，之间没有序关系如产品颜色可以取：红、黄、绿、蓝等也可以用0，1，2，3等代码来表示，但注意这

10、里的数字仅是标识，不能做运算两个对象i和j之间的相异度简单的处理方法是计算不匹配率：其中p是全部变量的数目，m是匹配的数目也可以构造一个大的二元变量数组，再按二元变量处理,第31页,余弦相似度,文档数据,第32页,在信息检索、文本文档聚类和生物学分类中，需要对包含了大量符号实体的复杂对象进行比较和聚类为了测量复杂对象间的距离，通常期望放弃传统的度量距离计算，而引入非度量的相似度函数 如果d1 和 d2 是两个文档向量，则 cos(d1,d2)=(d1 d2)/|d1|d2|,其中 表示向量的点积(内积)，|d|表示向量的范数.问题：余弦相似度的范围？取最大值时是否两个向量相等？,余弦相似度,第

11、33页,余弦相似度计算的例子,d1=3 2 0 5 0 0 0 2 0 0 d2=1 0 0 0 0 0 0 1 0 2 d1 d2=3*1+2*0+0*0+5*0+0*0+0*0+0*0+2*1+0*0+0*2=5|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.481|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.245cos(d1,d2)=5/(6.481*2.245).3150,第34页,如何选择恰当的度量,有很多方法用来选择一个具体的相似度或距离

12、函数，但是还没有一个通用的标准用来指导这样的选择这种度量的选择高度依赖于具体的应用。,第35页,主要聚类方法的分类,划分方法：给定n个对象，划分方法构建数据的k个划分，每个划分表示一簇，k=n，满足如下要求每组至少包含一个对象每个对象必须只属于一个组(在软聚类技术中可放宽)对于给定的划分数目k，通常创建一个初始划分，然后采用迭代方法尝试通过对象在组间移动来改进划分,第36页,主要聚类方法的分类,好的划分的标准：同一个簇中的对象之间尽可能相似，不同簇的对象尽可能有大的差异常用方法：k均值方法：每个簇都用该簇中对象的均值来表示k中心点法：每个簇用接近簇中心的一个对象来表示,第37页,层次方法创建给

13、定数据对象的层次分解根据使用的方法，层次的方法可以分类为凝聚的或分裂的方法凝聚法：也称自底向上的方法，开始将每个对象形成单独的组，然后逐次合并相近的对象或组，直到所有的组合并为一个或满足某个终止条件分裂法：自顶向下的方法，一开始将所有对象置于一个簇中，每次迭代，簇分裂为更小的簇，直到每个对象在一个簇中或满足终止条件,层次方法,第38页,基于模型的方法,为每簇假定一个模型，并寻找数据对给定模型的最 佳拟合常见算法EM算法：基于统计模型并进行期望最大化分析COBWEB：概念学习算法，进行概率分析并把概念作为簇模型SOM(自组织映射)：一种基于神经网络的算法，通过把高维数据映射到2维或3维特征空间进

14、行聚类,第39页,划分聚类,原始点,划分聚类,第40页,层次聚类,Traditional Hierarchical Clustering,Non-traditional Hierarchical Clustering,Non-traditional Dendrogram,Traditional Dendrogram,第41页,互斥的与非互斥的在非互斥聚类中，点可以属于多个簇.可以表示多重类或边界类模糊聚类与非模糊聚类模糊聚类中，一个点到隶属于每个簇的情况可以用一个在0到1之间的隶属度描述,其他的聚类类型的差别,第42页,不同的簇类型,明显分离的簇基于中心的簇基于近邻的簇基于密度的簇概念簇,第4

15、3页,不同的簇类型,明显分离的簇:每个点到同簇中任意点的距离比到不同簇中所有点的距离更近,3 个明显分离的簇,第44页,不同的簇类型,基于中心的簇 每个点到其簇中心的距离比到任何其他簇中心的距离更近 簇的中心通常是重心，簇中所有点的平均值，或者是簇的原型，即一个簇中最具代表性的点,4 center-based clusters,第45页,不同的簇类型,基于近邻的簇(基于图的连通分支)每个点到该簇中至少一个点的距离比到不同簇中任意点的距离更近,8 contiguous clusters,第46页,不同的簇类型,基于密度的簇簇是被低密度区域分开的高密度区域.当簇不规则或互相盘绕，并且有噪声和离群点

16、时，通常使用基于密度的簇定义,6 density-based clusters,第47页,划分方法,对于一个给定的n个对象或元组的数据库，采用目标函数最小化的策略，通过迭代把数据分成k个划分块，每个划分块为一个簇，这就是划分方法。划分方法满足两个条件：（1）每个分组至少包含一个对象；（2）每个对象必属于且仅属于某一个分组。常见的划分方法有k-均值方法和k-中心点方法。其他方法大都是这两种方法的变形。,第48页,k-均值算法,k-均值聚类算法的核心思想是通过迭代把数据对象划分到不同的簇中，以求目标函数最小化，从而使生成的簇尽可能地紧凑和独立。随机选取k个对象作为初始的k个簇的质心；将其余对象根据

17、其与各个簇质心的距离分配到最近的簇；再求新形成的簇的质心。这个迭代重定位过程不断重复，直到目标函数最小化为止。,第49页,k-均值算法,第50页,初始质心的选择非常重要,第51页,使用K均值算法的迭代过程,第52页,K-均值算法,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,K=2Arbitrarily choose K object as initial cluster center,Assign each objects to most similar center,Update the cluster means,Update the clu

18、ster means,reassign,reassign,第53页,欧几里得空间中的数据,通常使用误差的平方和(sum of the squared error,SSE)作为度量聚类质量的目标函数SSE也称散布(scatter)：计算每个数据点的误差即它到最近质心的欧几里得距离，然后计算误差的 平方和给定由两次运行K均值产生的两个不同的簇集，我们更喜欢误差的平方和最小的那个，这意味着聚类的 原型(质心)是簇中点的更好代表,第54页,欧几里得空间中的数据,可以证明在欧几里得空间中是簇的SSE最小的质心 就是均值K均值算法的第3步和第4步试图直接最小化SSE步骤3通过将点指派到最近的质心形成簇，最

19、小化关于给定质心集的SSE步骤4重新计算质心，进一步最小化SSE问题：K均值的步骤3和4只能找到关于SSE的局部最小值，因为它们是对选定的质心和簇，而不是对 所有可能的选择来优化SSE,第55页,初始质心的选择非常重要,第56页,初始质心的选择非常重要,第57页,随机初始化,由于K均值算法会陷入局部最小值而得到次优聚类，一种常用的选取初始质心的方法是多次运行，每次使用一组不同的随机初始质心，然后选取具有最小SSE的簇集下面我们看一看这种方法的问题下页的图中有5个簇对，每个簇对有上下两个簇。如果每个簇对有两个初始质心，则效果较好如果有一个簇对中只有一个初始中心，而另一个簇对中有三个初始中心，则会

20、出现错误。,第58页,Starting with two initial centroids in one cluster of each pair of clusters,5个簇对，10个簇的例子,第59页,Starting with two initial centroids in one cluster of each pair of clusters,5个簇对，10个簇的例子,第60页,Starting with some pairs of clusters having three initial centroids,while other have only one.,5个簇对，1

21、0个簇的例子,第61页,Starting with some pairs of clusters having three initial centroids,while other have only one.,5个簇对，10个簇的例子,第62页,解决初始质心设置问题的方法,多次运行不一定总有效对数据作采样并使用层次聚类，从中提取K个簇并使用这些簇的质心作为初始质心选取多于k个的初始质心，然后从其中选择k个最分离的k个点后处理二分K-均值,第63页,二分K均值,基本思想：为了得到K个簇，将所有点的集合分裂成两个簇，从这些簇中选取一个继续分裂，如此下去直到产生K个簇可以使用多种方法选择待分裂的

22、簇最大的簇具有最大SSE的簇基于大小和SSE二分K均值得到的最终的簇集并不代表使SSE局部最小的聚类,第64页,二分K均值算法,第65页,二分K-均值的例子,第66页,K-均值方法的缺陷,K-均值方法当簇在下述方面有较大不同时会出现问题 不同大小不同密度非球形的形状,第67页,Original Points,K-means(3 Clusters),K-均值的缺陷：不同的簇大小,WHY？,第68页,Original Points,K-means(3 Clusters),K-均值的缺陷不同的密度分布,WHY？,第69页,Original Points,K-means(2 Clusters),K均值

23、的缺陷：非球形形状,K均值目标函数是最小化等尺度和等密度的球形簇，或明显分离的簇,第70页,Original PointsK-means Clusters,一种方法是使用更多的簇，再反过来使其部分合并,克服K均值方法的缺陷,第71页,Original PointsK-means Clusters,克服K均值方法的缺陷,第72页,Original PointsK-means Clusters,克服K均值方法的缺陷,第73页,层次聚类方法,定义：对给定的数据进行层次的分解：凝聚的（agglomerative）方法（自底向上）思想：一开始将每个对象作为单独的一组，然后根据同类相近，异类相异的原则，合

24、并对象，直到所有的组合并成一个，或达到一个终止条件为止。分裂的方法（divisive）（自顶向下）思想：一开始将所有的对象置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终止条件。,第74页,凝聚的和分裂的层次聚类,第75页,层次聚类方法,产生一个相邻簇的集合，通常用一棵树来表示Can be visualized as a dendrogram树状图记录了分裂或合并的序列,以树状图和嵌套簇图显示的4个点的层次聚类,第76页,层次聚类法的特点,不用预知(预设)簇的数目任何需要簇数的聚类可以通过在树状图的适当层次切割而得到得到更有意义的结构如生物学中的

25、分类传统的层次聚类算法使用相似度矩阵或距离矩阵每次合并或分裂一个簇,第77页,1 计算距离矩阵2 令每个点为一个簇3 Repeat4 合并最接近的两个簇5 更新距离矩阵6 until 仅剩下一个簇,基本凝聚层次聚类算法,第78页,关键步骤在于计算两个簇之间的邻近度不同的定义簇之间的距离的方法区分了不同的算法,基本凝聚层次聚类算法,第79页,开始.,每个点为一个簇，计算各个簇两两之间的距离矩阵,距离矩阵,第80页,接下来.,经过若干凝聚步骤，得到如下的簇,C1,C4,C2,C5,C3,距离矩阵,第81页,接下来.,合并两个最靠近的簇(C2 和 C5)并更新距离矩阵,C1,C4,C2,C5,C3,

26、距离矩阵,第82页,合并后,问题变为如何更新距离矩阵,C1,C4,C2 U C5,C3,?,?,?,?,C2 U C5,C1,C1,C3,C4,C2 U C5,C3,C4,距离矩阵,第83页,距离,MIN(单链)MAX(全链)Group Average(组平均)质心的距离其他的源自目标函数的方法Ward方法使用平方差,距离矩阵,如何定义簇之间的邻近度,第84页,距离矩阵,MIN(单链)MAX(全链)Group Average(组平均)质心的距离其他的源自目标函数的方法Ward方法使用平方差,如何定义簇之间的邻近度,第85页,距离矩阵,MIN(单链)MAX(全链)Group Average(组平

27、均)质心的距离其他的源自目标函数的方法Ward方法使用平方差,如何定义簇之间的邻近度,第86页,距离矩阵,MIN(单链)MAX(全链)Group Average(组平均)质心的距离其他的源自目标函数的方法Ward方法使用平方差,如何定义簇之间的邻近度,第87页,距离矩阵,MIN(单链)MAX(全链)Group Average(组平均)质心的距离其他的源自目标函数的方法Ward方法使用平方差,如何定义簇之间的邻近度,第88页,MIN或单链,两个簇之间的邻近度基于两个簇中最近的两个点的距离由一个点对决定，或者说由图中的一条链决定,第89页,Nested Clusters,Dendrogram,层次

28、聚类:MIN,第90页,Original Points,Two Clusters,可以处理非椭圆的形状,MIN的优点,第91页,Original Points,Two Clusters,对噪声点和离群点很敏感,MIN的不足,第92页,MAX或全链,两个簇之间的邻近度由两个簇间最不相似的(最大距离的)点对决定由两个簇中所有的点对决定,第93页,Nested Clusters,Dendrogram,MAX或全链,第94页,Original Points,Two Clusters,对噪声点和离群点不太敏感,MAX的优点,第95页,Original Points,Two Clusters,倾向于分裂大

29、的簇倾向于球状的簇,MAX的不足,第96页,组平均,两个簇的邻近度定义为不同簇的所有点对的平均逐对邻近度Need to use average connectivity for scalability since total proximity favors large clusters,第97页,Nested Clusters,Dendrogram,组平均,第98页,组平均,是单链和全链之间的一个折中，该法利用了所有样本的信息，被认为是较好的层次聚类法优点对噪声和离群点不太敏感不足倾向于球状的簇,第99页,Ward方法和质心方法,两个簇的邻近度定义为两个簇合并时导致的平方误差的增量，该方法使

30、用的目标函数与K均值相同可以证明，当取距离的平方作为两个点间的邻近度时，Ward方法与组平均方法相似对噪声和离群点不太敏感倾向于球状的簇可以用来初始化K均值方法,第100页,层次聚类法：比较,Group Average,Wards Method,MIN,MAX,第101页,O(N2)空间复杂度，因为要存储邻近度矩阵，N为点的数目最坏情况下O(N3)的时间复杂度共有N步，在每一步中要更新和搜索N2规模的邻近度矩阵在某些算法中可以接近O(N2 log(N)的时间复杂度,层次聚类：时间和空间复杂度,第102页,层次聚类方法的优缺点,层次聚类方法的优点在于可以在不同粒度水平上对数据进行探测，而且容易实

31、现相似度量或距离度量。单纯的层次聚类算法终止条件含糊，而且执行合并或分裂簇的操作后不可修正，这很可能导致聚类结果质量很低。通常考虑把层次聚类方法与其他方法（如迭代重定位方法）相结合来解决实际聚类问题。,第103页,DBSCAN是一种基于密度的聚类算法密度=给定半径(Eps)内点的数目核心点(core point)在半径Eps的邻域内拥有多于特定数目(MinPts)的邻点的点，在基于密度的簇内部的点边界点(border point)在半径Eps的邻域内拥有多于特定数目(MinPts)的邻点的点，但是落在某个核心点的邻域内噪声点(noise point)既非核心点也非边界点的任何点,基于密度的聚类

32、：DBSCAN,第104页,DBSCAN:核心点，边界点和噪声点,第105页,DBSCAN 算法,算法1：将所有点标记为核心点、边界点或噪声点2：删除噪声点3：为距离在Eps之内的所有核心点之间赋予一条边4：每组连通的核心点形成一个簇将每个边界点指派到一个与之关联的核心点的簇中,第106页,原始点,点的类型:核心,边界 和噪声,Eps=10,MinPts=4,DBSCAN 算法,第107页,原始点,得到的簇,对噪声不敏感 可以处理不同形状和大小的簇,当DBSCAN工作良好时,第108页,原始点集,(MinPts=4,Eps=9.75).,(MinPts=4,Eps=9.92),变密度的簇 对高

33、维数据计算量巨大,当DBSCAN工作不佳时,第109页,基本方法：观察点到它的k个最近邻的距离(称作k-距离)。对于属于某个簇的点，如果k不大于簇的大小的话，则k-距离将很接近噪声点由于不在簇中，其k-距离将相对较大对于某个k，计算所有点的k-距离，以递增次序将它们排序，然后绘制排序后的值，则预期会看到k-距离的急剧变化处对应于合适的Eps值,DBSCAN算法:确定EPS和 MinPts,第110页,DBSCAN算法:确定EPS和 MinPts,第111页,簇评估,对于有监督的分类，我们可以有多种方式评价模型的优劣准确度,精度,召回率对于聚类分析,相应的问题是如何评价聚类结果是否是“好”的评估

34、簇的目的避免寻找噪声中的模式比较不同的聚类算法比较两个聚类的结果比较两个簇,第112页,在随机数据中发现的簇,100个随机分布的点,K-均值,DBSCAN,全链聚类,第113页,确定数据的聚类趋势(clustering tendency),即识别数据中是否实际存在非随机结构.比较聚类分析的结果与通过外部知识得到的类标(确定正确的簇个数).评估聚类分析的结果在不引用附加信息的情况下是否能较好拟合数据.比较两个不同的聚类结果的优劣.确定“正确”的类的个数对于 2,3,4,还可以进一步分为是要比较整个分类结果还是其中的某个簇,簇评估,第114页,用于评估簇各方面的评估度量或指标分成如下三类监督的(外

35、部指标):度量聚类算法发现的聚类结构与某种外部结构的匹配程度。例如熵，度量簇标号与外部提供的标号的匹配程度 非监督的(内部指标):聚类结构的优良性度量，不考虑外部因素。如SSE(平方误差和)。簇的有效性的非监督度量常常可以进一步分成两类：簇的凝聚性（紧凑性）：度量簇中对象如何密切相关簇的分离性（孤立性）：度量确定一个簇如何不同于其它簇,度量簇的正确性,第115页,用于评估簇各方面的评估度量或指标分成如下三类相对指标:比较不同的聚类或簇。是用于比较的监督或非监督评估度量，例如SSE或熵,度量簇的正确性,第116页,通过相关性度量簇的有效性,给定数据集的相似度矩阵和数据集聚类分析得到的类标号，则可

36、以通过考察相似度矩阵和基于类标号的相似度矩阵的理想版本之间的相关性，来评估聚类的优良性一个理想的簇：它的点与簇内所有点的相似度为1，而与其它簇中的所有点的相似度为0如果我们将相似度矩阵的行和列排列，使得属于相同簇的对象在一起，则理想的相似度矩阵具有块对角结构：在相似度矩阵中代表簇内相似度的相的块内部相似度非0，而其它地方为0,第117页,通过相关性度量簇的有效性,理想的相似度矩阵如下构造：创建一个矩阵，每个数据点一行一列，矩阵的一个项为1，如果它所关联的一对点属于同一个簇，否则为0理想和实际相似度矩阵之间高度相关表明属于同一个簇的点相互之间很接近。由于实际和理想相似度矩阵都是对称的，所以只需要

37、对矩阵对角线下方或上方的n(n-1)/2个项计算相关度,第118页,对如下的两个数据集使用K-均值算法得到的簇计算相似度矩阵,Corr=0.9235,Corr=0.5810,实际的和理想的相似度矩阵,第119页,按照簇标号调整相似度矩阵的行列次序，然后画出它们。如果有明显分离的簇，则相似度矩阵应当粗略的是块对角的,通过相似度矩阵可视化的评价聚类,第120页,随机数据的簇的相似度矩阵,DBSCAN,随机数据的簇的相似度矩阵,第121页,随机数据的簇的相似度矩阵,K-means,随机数据的簇的相似度矩阵,第122页,Complete Link,随机数据的簇的相似度矩阵,第123页,在随机数据上，D

38、BSCAN、K均值和全链发现的簇的重新排序的相似度矩阵中也存在弱对角模式,第124页,DBSCAN,通过相似度矩阵可视化的评价聚类,第125页,有更复杂图像的簇很难被分离内部指标:不使用外部信息而独立簇结构的优良性SSESSE可以较好地比较两个聚类结果或具体的两个簇,内部测度:SSE,第126页,可以用来估计簇的个数。左图的数据集有10个自然簇。当簇个数等于10时，SSE有一个明显的拐点,内部测度:SSE,第127页,内部测度:SSE,更复杂数据集的SSE曲线,SSE of clusters found using K-means,第128页,聚类趋势,确定数据集中是否包含簇的一种显而易见的方

39、法是使着对它聚类。给定数据，几乎所有的聚类算法都会发现簇。为了处理这一问题，我们可以评估结果簇，至少有些簇具有好的质量，才能说数据集包含簇问题在于数据集中可能存在不同于我们是有的聚类算法所能发现的簇类型尝试使用多种方法，并评估结果簇的质量。如果簇都很差，则可能表示数据中确实没有簇。,第129页,Hopkins统计量,使用统计检验来检验空间随机性产生p个随机地分别在数据空间上的点，并且也抽取p个实际数据点。对于这两个点集，找出每个点到原数据集的最近邻距离。设ui是人工产生的点的最近邻距离，而wi是样本点到原数据集的最近邻距离。Hopkins统计量H由下式定义,第130页,Hopkins统计量,如

40、果随机产生的点与样本点具有大致相同的最近距离，则H将在0.5左右。H接近0或1表明数据是高度聚类的和数据在数据空间是有规律分布的。对于p=20和100的不同实验，左图的H平均值为0.95，标准差为0.0006，右图的H平均值为0.59，标准差为0.03,第131页,聚类：选择聚类的个数,如何选择k-均值算法中的k？可能的策略对不同的可能个数进行试验，选择能使所有点离开它们聚类中心的距离平方的总和达到最小的k值从一个给定的最小个数开始，一直试验到一个较小的固定的最大值，用交叉验证法找出最好的个数根据距离平方和标准来决定最佳聚类训练数据的方法，将总是选择和数据点一样多的聚类。为了抑制选择很多聚类的

41、方案，必须采用诸如最短描述长度准则，或采用交叉验证,第132页,如何理解聚类,坦哥，你好啊，关于数据挖掘作业，我试着先聚类再决策树分析，很多时候都会导致聚类得到的结果跟决策树有冲突，例如：聚类后得到影响某个属性的几个属性，但是在决策树分析中决定我感兴趣的那个属性的决策树却不存在这几个属性子结点，这样反而是聚类影响了决策树的准确性了。我想问几个问题：1.我发现项目里的两个问题用决策树是可以完全解决，为什么还要先聚类再用决策树分析呢？,第133页,如何理解聚类,2.聚类分析跟决策树之间有何联系？对于具体问题，应该如何将它们联系起来分析。困惑中。3.聚类分析在于分类，但是我感觉聚类分析要应用到实际问

42、题中很困难，请指教。我跟很多同学请教过这些问题，发现他们也有类似疑惑，请坦哥不吝赐教啊。,第134页,如何理解聚类,数据挖掘的任务是寻找有意义的数据模式，但这种模式不是立刻就能得到有时候根本找不到(明显的)模式有时候的问题不是缺乏模式，而是模式太多这些数据可能包含很多复杂的结构以至于最佳数据挖掘技术也不能找出有意义的模式当挖掘这些数据集以寻找特定问题的答案时，相互对立的解释往往使彼此相互抵消。,第135页,如何理解聚类,象接受无线电信号一样，太多相互竞争的信号叠加到一起就变为噪音。聚类提供了一种获悉复杂数据结构的方法，即将竞争的信号的杂音分解成各自的成分。当人们试图弄清复杂问题的意义时，往往趋

43、向于将问题分解为更小的片断，每一个片断可以更简单地解释。在许多情况下，非常杂乱的数据集实际上可能由许多表现较好的簇组成，聚类分析的目的就是如何发现它们。,第136页,如何理解聚类,聚类分析是一种描述性的任务，用来发现数据集的分布特征。也可以作为对他发现的簇运行的数据挖掘算法的预处理步骤。,第137页,案例研究：聚类城镇,波士顿环球报是服务于波士顿以及东马萨诸塞州和新罕布什尔南部周围区域的两家大日报之一，是波士顿的主流报纸。2003年的日发行量超过457 000份，在周日发行量超过705 000份。波士顿环球报面临如下问题：波士度核心市场读者群在缩减，郊区报业市场面临来自地方报纸的有力竞争，一些

44、读者已流失。,第138页,案例研究：聚类城镇,为了与郊区报纸更好地竞争，环球报加入了为不同地区定制的报纸版面，为按照地域划分的12个地区加入了特别编辑内容。每周有两天，读者都可以读到为本区精心整理的一些地方报道页。环球报使用的编辑区域利用的是环球报已有的数据、常识性内容以及地图，但没有正式的统计分析。,第139页,案例研究：聚类城镇,编辑区域组成方面有一些限制条件地域必须是地理上连续的，以便运输地域必须适度紧凑，且包含足够人口已证明特殊化编辑的内容是恰当的编辑区域必须接近于过去做广告的地理区域。下面采用数据挖掘技术来把相似的城镇聚集在一起形成编辑区。,第140页,1 创造城镇特征,在做聚类分析

45、之前，首要的问题是找到描述城镇的特征，需要包括可以用于表征城镇特点，以及可用于比较该城镇及其邻近城镇的每个特征的一个列城镇特征标识可以有几个来源，大部分数据可以从1990年和2001年城镇级的美国人口普查数据(census data)得到，包括年龄、种族、宗教信仰、职业、收入、住宅价值、平均通勤时间以及其他令人感兴趣的变量。,第141页,1 创造城镇特征,此外还有外围数据提供商提供的关于订户家庭层次的数据，还有每个城镇的发行量数据，以订阅者层次的信息，如优惠计划、投诉电话和订户类型(日常、周日或者两者都是)等数据的处理：本例中通过四个基本步骤来创建城镇特征聚集归一化计算趋势创建衍生变量,第14

46、2页,1 创造城镇特征,聚集：将较细层次的数据汇总到城镇层次，例如聚集订户的数据以得出每个城镇中订户的总数和中值订户家庭收入归一化：将计数值(例如收入、住宅价值和孩子数目)转变成百分比。这实际上是把人口差别很大的不同城镇的数据归一化，为了可以有效地进行对比。例如2001年有4年大学学历的27573个人住在Borrkline，这只占到教育水平高的城镇的47.5%。在波士顿，具有类似学位的人非常多，但只占到当地总人口的19.4%.,第143页,1 创造城镇特征,计算趋势：人口普查数据中每个变量都有相隔11年的两个值可以使用。历史数据的一个令人感兴趣的地方是可以观察到其中的趋势。如人口的变化：包括学

47、龄人口的变化、不同族裔人口的变化，或拥有自有住房人口比例的变化。创建衍生变量：从已存在的变量中衍生另外一些变量。例如从邮政编码数据数据中产生各个城镇到中心城市（波士顿）的距离,第144页,创建簇,利用人口统计学和地理学数据描述该城镇的特征标识使用这些特征得到的聚类结果不能直接用于创建报纸的编辑区，因为还有地理方面的约束条件，即编辑区域必须由相邻的城镇构成。有相似人口统计学数据的城镇未必在地理上相邻，这个问题可以通过使用加权的方式来增加形成簇过程中地理变量的重要性。但在本案例中最终放弃了地域簇的设计，因为目标是寻找至少部分基于人口统计学的相似性，更侧重于人口统计学方面。,第145页,Massac

48、husetts东部及New Hampshire南部各城镇人口统计学聚类情况,第146页,确定簇的正确数量,处于商业方面的原因，可能需要12个编辑区域，但不能保证找到这么多好的簇。这直接提出如何为数据集确定合适数目的簇的问题。这里使用类似二分K均值的算法。首先以较低的K值确定簇数目，使用普通的K均值算法构建K聚类，利用适应度度量(如SSE)确定最差的簇，然后把这个簇分裂为2个簇，反复重复这个过程，一直到簇数达到上界。每次迭代后，记录该簇的总体适应度。,第147页,对于实际商业问题，簇的最重要的适应度度量是难以量化的度量簇对某个应用的有效性。,按照算法的建议，聚类算法的下一次迭代将把簇2进行分裂。

49、形成的簇有明确的差异，但对于环球报感兴趣的变量而言，所形成的新簇都没有不同的表现，如家庭递送穿透度或订户资历等。,第148页,城镇的最终的四个分组,簇2包含了50个城镇中的31300个家庭，其中137000个家庭订阅日报或周末版环球报。它是“最佳簇”,“Best”based on delivery penetration,“2nd Best”based on delivery penetration,Cluster 2,Cluster 1B,Cluster 1AB,第149页,簇2与其他簇和人口总体区分开的变量是住宅价值和教育程度。这个簇有最高的住宅价值比例、最高的有4年大学学历的人数比例、最

50、高受教育的品均年数和最低的蓝领工作人员比例,第150页,从家庭递送穿透度来看，次好的簇是簇1AA。住宅价值和家庭收入与总人口的均值非常接近。簇1B的特征：主要以有最低家庭收入 历时最久且临近波士顿的订户,“Best”based on delivery penetration,“2nd Best”based on delivery penetration,Cluster 2,Cluster 1B,Cluster 1AB,第151页,簇1AB是唯一主要以地域为特征形成的簇，都是远离波士顿的城镇，其家庭递送穿透度很低。其住宅价值最低，但家庭收入为平均数。簇1AB中的人选择在离城市较远的 地方居住，因