第5章聚类分析ppt课件.ppt
《第5章聚类分析ppt课件.ppt》由会员分享,可在线阅读,更多相关《第5章聚类分析ppt课件.ppt(147页珍藏版)》请在三一文库上搜索。
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 s
5、uits,第15页,聚类分析原理介绍,分成四组 符号相同的牌为一组,符号相同的的牌 Like face cards,第16页,聚类分析原理介绍,分成两组 颜色相同的牌为一组,颜色相同的配对 Black and red suits,第17页,聚类分析原理介绍,分成两组 大小程度相近的牌分到一组,大配对和小配对 Major and minor suits,第18页,聚类分析原理介绍,这个例子告诉我们,分组的意义在于我们怎么定义并度量“相似性” (Similar) 因此衍生出一系列度量相似性的方法,大配对和小配对 Major and minor suits,第19页,聚类分析原理介绍,变量按测量尺度
6、(Measurement Level)分类 区间(Interval)值变量 连续变量,如长度、重量、速度、温度等 有序(Ordinal)值变量 等级变量,不可加,但可比,如一等、二等、三等奖学金 名词性(Nominal)变量 类别变量,不可加也不可比,如性别、职业等 下面介绍对各种不同类型的变量如何进行度量,第20页,度量对象间的相似与差异,对象间的相似度或相异度通常基于每对对象间的距离的计算 欧几里得距离 Minkowski距离,第21页,度量对象间的相似与差异,曼哈顿距离(Block距离) 欧几里得距离是当q=2时的Minkowski距离的特例 曼哈顿距离是当q=1时的Minkowski距
7、离的特例 当q=时得到无穷距离(无穷范数),由向量间各分量的最大差决定,第22页,度量对象间的相似与差异,距离所应满足的数学性质 d(i,j) 0 d(i,i) = 0 d(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是
8、在对象i值为1,但对象j值为0的变量数目 变量的总数是p=q+r+s+t,第25页,对称二元变量和非对称二元变量,对二元变量的相异度计算还要考虑变量的对称性 对称二元变量 如果他的两个状态具有同等价值和相等的权重 输出用0或1编码没有优先权,如性别 对称二元相异度,第26页,对称二元变量和非对称二元变量,非对称二元变量 如果状态的输出不是同等重要的 例如基本检查的阳性和阴性结果。根据惯例,将比较重要的输出结果(通常也是出现机率较小的结果)编码为1,而将另一种结果编码为0(如HIV阴性) 给定两个非对称二元变量,两个都取值1的情况认为比两个都取值0的情况更有意义 非对称二元相异度,第27页,对称
9、二元变量和非对称二元变量,有时采用两个二元变量的相似度而不是相异度来测量他们之间的距离。 非对称二元相似度sim(i,j)如下定义 系数sim(i,j)常称作Jaccard系数,第28页,例 二元变量之间的相异度,假设一个患者记录表包含上述属性,其中name是标识符,性别是对称二元属性,其余的属性都是非对称二元属性 对于非对称属性,值Y和P(positive)置为1,值N(no或negative)置为0,第29页,例 二元变量之间的相异度,假设对象之间的距离只基于非对称变量来计算。根据公式,三个患者Jack、Mary和Jim两两之间的相异度如下: 度量显示Jim和Mary不大可能患相似的疾病,
10、而Jack和Mary最可能患相似的疾病,第30页,名词性属性变量,可取多个相异值,之间没有序关系 如产品颜色可以取:红、黄、绿、蓝等 也可以用0,1,2,3等代码来表示,但注意这里的数字仅是标识,不能做运算 两个对象i和j之间的相异度简单的处理方法是计算不匹配率: 其中p是全部变量的数目,m是匹配的数目 也可以构造一个大的二元变量数组,再按二元变量处理,第31页,余弦相似度,文档数据,第32页,在信息检索、文本文档聚类和生物学分类中,需要对包含了大量符号实体的复杂对象进行比较和聚类 为了测量复杂对象间的距离,通常期望放弃传统的度量距离计算,而引入非度量的相似度函数 如果d1 和 d2 是两个文
11、档向量,则 cos( d1, d2 ) = (d1 d2) / |d1| |d2| , 其中 表示向量的点积(内积),| d |表示向量的范数. 问题:余弦相似度的范围?取最大值时是否两个向量相等?,余弦相似度,第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)
12、 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.245 cos( d1, d2 ) = 5/(6.481*2.245).3150,第34页,如何选择恰当的度量,有很多方法用来选择一个具体的相似度或距离函数,但是还没有一个通用的标准用来指导这样的选择 这种度量的选择高度依赖于具体的应用。,第35页,主要聚类方法的分类,划分方法:给定n个对象,划分方法构建数据的k个划分,每个划分表示一簇,k=n,满足如下要求 每组至少包含一个对象 每个对象必须只属于一个组(在软聚类技术中可放宽) 对于给
13、定的划分数目k,通常创建一个初始划分,然后采用迭代方法尝试通过对象在组间移动来改进划分,第36页,主要聚类方法的分类,好的划分的标准:同一个簇中的对象之间尽可能相似,不同簇的对象尽可能有大的差异 常用方法: k均值方法:每个簇都用该簇中对象的均值来表示 k中心点法:每个簇用接近簇中心的一个对象来表示,第37页,层次方法创建给定数据对象的层次分解 根据使用的方法,层次的方法可以分类为凝聚的或分裂的方法 凝聚法:也称自底向上的方法,开始将每个对象形成单独的组,然后逐次合并相近的对象或组,直到所有的组合并为一个或满足某个终止条件 分裂法:自顶向下的方法,一开始将所有对象置于一个簇中,每次迭代,簇分裂
14、为更小的簇,直到每个对象在一个簇中或满足终止条件,层次方法,第38页,基于模型的方法,为每簇假定一个模型,并寻找数据对给定模型的最 佳拟合 常见算法 EM算法:基于统计模型并进行期望最大化分析 COBWEB:概念学习算法,进行概率分析并把概念作为簇模型 SOM(自组织映射):一种基于神经网络的算法,通过把高维数据映射到2维或3维特征空间进行聚类,第39页,划分聚类,原始点,划分聚类,第40页,层次聚类,Traditional Hierarchical Clustering,Non-traditional Hierarchical Clustering,Non-traditional Dendr
15、ogram,Traditional Dendrogram,第41页,互斥的与非互斥的 在非互斥聚类中,点可以属于多个簇. 可以表示多重类或边界类 模糊聚类与非模糊聚类 模糊聚类中,一个点到隶属于每个簇的情况可以用一个在0到1之间的隶属度描述,其他的聚类类型的差别,第42页,不同的簇类型,明显分离的簇 基于中心的簇 基于近邻的簇 基于密度的簇 概念簇,第43页,不同的簇类型,明显分离的簇: 每个点到同簇中任意点的距离比到不同簇中所有点的距离更近,3 个明显分离的簇,第44页,不同的簇类型,基于中心的簇 每个点到其簇中心的距离比到任何其他簇中心的距离更近 簇的中心通常是重心,簇中所有点的平均值,或
16、者是簇的原型,即一个簇中最具代表性的点,4 center-based clusters,第45页,不同的簇类型,基于近邻的簇(基于图的连通分支) 每个点到该簇中至少一个点的距离比到不同簇中任意点的距离更近,8 contiguous clusters,第46页,不同的簇类型,基于密度的簇 簇是被低密度区域分开的高密度区域. 当簇不规则或互相盘绕,并且有噪声和离群点时,通常使用基于密度的簇定义,6 density-based clusters,第47页,划分方法,对于一个给定的n个对象或元组的数据库,采用目标函数最小化的策略,通过迭代把数据分成k个划分块,每个划分块为一个簇,这就是划分方法。 划分
17、方法满足两个条件: (1)每个分组至少包含一个对象; (2)每个对象必属于且仅属于某一个分组。 常见的划分方法有k-均值方法和k-中心点方法。其他方法大都是这两种方法的变形。,第48页,k-均值算法,k-均值聚类算法的核心思想是通过迭代把数据对象划分到不同的簇中,以求目标函数最小化,从而使生成的簇尽可能地紧凑和独立。 随机选取k个对象作为初始的k个簇的质心; 将其余对象根据其与各个簇质心的距离分配到最近的簇;再求新形成的簇的质心。 这个迭代重定位过程不断重复,直到目标函数最小化为止。,第49页,k-均值算法,第50页,初始质心的选择非常重要,第51页,使用K均值算法的迭代过程,第52页,K-均
18、值算法,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,K=2 Arbitrarily choose K object as initial cluster center,Assign each objects to most similar center,Update the cluster means,Update the cluster means,reassign,reassign,第53页,欧几里得空间中的数据,通常使用误差的平方和(sum of the squared error, SSE)作为度量聚类质量的目标函数 SSE也称散布(sc
19、atter):计算每个数据点的误差即它到最近质心的欧几里得距离,然后计算误差的 平方和 给定由两次运行K均值产生的两个不同的簇集,我们更喜欢误差的平方和最小的那个,这意味着聚类的 原型(质心)是簇中点的更好代表,第54页,欧几里得空间中的数据,可以证明在欧几里得空间中是簇的SSE最小的质心 就是均值 K均值算法的第3步和第4步试图直接最小化SSE 步骤3通过将点指派到最近的质心形成簇,最小化关于给定质心集的SSE 步骤4重新计算质心,进一步最小化SSE 问题:K均值的步骤3和4只能找到关于SSE的局部最小值,因为它们是对选定的质心和簇,而不是对 所有可能的选择来优化SSE,第55页,初始质心的
20、选择非常重要,第56页,初始质心的选择非常重要,第57页,随机初始化,由于K均值算法会陷入局部最小值而得到次优聚类,一种常用的选取初始质心的方法是多次运行,每次使用一组不同的随机初始质心,然后选取具有最小SSE的簇集 下面我们看一看这种方法的问题 下页的图中有5个簇对,每个簇对有上下两个簇。 如果每个簇对有两个初始质心,则效果较好 如果有一个簇对中只有一个初始中心,而另一个簇对中有三个初始中心,则会出现错误。,第58页,Starting with two initial centroids in one cluster of each pair of clusters,5个簇对,10个簇的例子
21、,第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个簇对,10个簇的例子,第61页,Starting with some pairs of clusters having three initial centroids, while other have
22、only one.,5个簇对,10个簇的例子,第62页,解决初始质心设置问题的方法,多次运行 不一定总有效 对数据作采样并使用层次聚类,从中提取K个簇并使用这些簇的质心作为初始质心 选取多于k个的初始质心,然后从其中选择k个 最分离的k个点 后处理 二分K-均值,第63页,二分K均值,基本思想: 为了得到K个簇,将所有点的集合分裂成两个簇,从这些簇中选取一个继续分裂,如此下去直到产生K个簇 可以使用多种方法选择待分裂的簇 最大的簇 具有最大SSE的簇 基于大小和SSE 二分K均值得到的最终的簇集并不代表使SSE局部最小的聚类,第64页,二分K均值算法,第65页,二分K-均值的例子,第66页,K
23、-均值方法的缺陷,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均值的缺陷:非球形形状,K均值目标函数是最小化等尺度和等密度的球形簇,或明显分离的簇,第70页,Original Points K-means Clusters,一
24、种方法是使用更多的簇,再反过来使其部分合并,克服K均值方法的缺陷,第71页,Original Points K-means Clusters,克服K均值方法的缺陷,第72页,Original Points K-means Clusters,克服K均值方法的缺陷,第73页,层次聚类方法,定义:对给定的数据进行层次的分解: 凝聚的(agglomerative)方法(自底向上) 思想:一开始将每个对象作为单独的一组,然后根据同类相近,异类相异的原则,合并对象,直到所有的组合并成一个,或达到一个终止条件为止。 分裂的方法(divisive)(自顶向下) 思想:一开始将所有的对象置于一类,在迭代的每一步
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 聚类分析 ppt 课件
链接地址:https://www.31doc.com/p-2606882.html