《第6章聚类分析ppt课件》由会员分享，可在线阅读，更多相关《第6章聚类分析ppt课件（168页珍藏版）》请在金锄头文库上搜索。
1、第第5章章 聚类分析聚类分析 本章概述 本章的学习目标主要内容遁俞证忧反尤崇燕陨耽酝且帮浅呜甥陵爵颇候页铀搜腥强衷草棱猜十菱少第6章聚类分析ppt课件第6章聚类分析ppt课件1什么是聚类什么是聚类l聚类（聚类（Clustering）就是将数据分组成为多个类）就是将数据分组成为多个类（Cluster或译为簇）。或译为簇）。l在同一个类内对象之间具有较高的相似度，不同类之在同一个类内对象之间具有较高的相似度，不同类之间的对象差别较大。间的对象差别较大。簇之间的距离最大化在一个簇内的距离最小化趋谆岿匆逗点钱研北仁权躁苦汛太辣苹诣男避甘娟免傣寞春膊淄暗遭傣笑第6章聚类分析ppt课件第6章聚类分析ppt
2、课件2l从机器学习的角度讲，簇相当于隐藏模式。聚类是搜从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程。索簇的无监督学习过程。l与分类不同，无监督学习不依赖预先定义的类或带类与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。而分类学习的实例或数据对象有类别标记。腰毒哗紫叠共态秽器陶爱疵幻谓橇募删找烹汕蹲胆朱萧辗党父扁谊蚌解贞第6章聚类分析ppt课件第6章聚类分析ppt课件3什么是聚类什么是聚类l早在孩提时代，人就通过不断改进下意识中的聚类模早在孩提
3、时代，人就通过不断改进下意识中的聚类模式来学会如何区分猫和狗，动物和植物式来学会如何区分猫和狗，动物和植物l将周围的人分为家人和非家人将周围的人分为家人和非家人蛮破疯店患咳埃老邱韭缚衬悍疏襄蔡拭取古贪戳憎役甜狙纪甲飘冶爹茨籽第6章聚类分析ppt课件第6章聚类分析ppt课件4聚类分析无处不在聚类分析无处不在l谁经常光顾商店，谁买什么东西，买多少？谁经常光顾商店，谁买什么东西，买多少？按忠诚卡记录的光临次数、光临时间、性别、按忠诚卡记录的光临次数、光临时间、性别、年龄、职业、购物种类、金额等变量分类年龄、职业、购物种类、金额等变量分类这样商店可以这样商店可以.识别顾客购买模式（如喜欢一大早来买酸奶
4、和识别顾客购买模式（如喜欢一大早来买酸奶和鲜肉，习惯周末时一次性大采购）鲜肉，习惯周末时一次性大采购）刻画不同的客户群的特征（用变量来刻画，就刻画不同的客户群的特征（用变量来刻画，就象刻画猫和狗的特征一样）象刻画猫和狗的特征一样）给诬狼翰洞后腊妮彭亢蕾掸刑郸鸿蹭灸眺咬龙涵棘坚外饰兰揍帝镶漾撼掌第6章聚类分析ppt课件第6章聚类分析ppt课件5什么情况下需要聚类什么情况下需要聚类l为什么这样分类？为什么这样分类？l因为每一个类别里面的人消费方式都不一样，需要针因为每一个类别里面的人消费方式都不一样，需要针对不同的人群，制定不同的关系管理方式，以提高客对不同的人群，制定不同的关系管理方式，以提高客
5、户对公司商业活动的响应率。户对公司商业活动的响应率。狄模沦贤渴昂海维趟狸捐哇供弹刮帅给蛛朵功所杂舔借浙轨袭蹦硝厦萝辊第6章聚类分析ppt课件第6章聚类分析ppt课件6聚类分析无处不在聚类分析无处不在l挖掘有价值的客户，并制定相应的促销策略：挖掘有价值的客户，并制定相应的促销策略：如，对经常购买酸奶的客户如，对经常购买酸奶的客户对累计消费达到对累计消费达到12个月的老客户个月的老客户l针对潜在客户派发广告，比在大街上乱发传单命中率针对潜在客户派发广告，比在大街上乱发传单命中率更高，成本更低！更高，成本更低！矽擦阐帧嘎城掖阅兔赣贵沪迂肮则铅獭祥稀听投巧曹咆灼瑟菱黍盛绿帚陈第6章聚类分析ppt课件第
6、6章聚类分析ppt课件7聚类分析无处不在聚类分析无处不在l谁是银行信用卡的黄金客户？谁是银行信用卡的黄金客户？利用储蓄额、刷卡消费金额、诚信度等变量对客利用储蓄额、刷卡消费金额、诚信度等变量对客户分类，找出户分类，找出“黄金客户黄金客户”！这样银行可以这样银行可以制定更吸引的服务，留住客户！比如：制定更吸引的服务，留住客户！比如：一定额度和期限的免息透资服务！一定额度和期限的免息透资服务！百盛的贵宾打折卡！百盛的贵宾打折卡！在他或她生日的时候送上一个小蛋糕！在他或她生日的时候送上一个小蛋糕！l手机套餐的制定手机套餐的制定危甜拉擎实息火赘睬盒刮伞决搓鸥堡抖圣葬恶阳恋暂祁俺涝林祷库眯膘非第6章聚类
7、分析ppt课件第6章聚类分析ppt课件8聚类的应用领域聚类的应用领域l经济领域：经济领域：帮助分析人员从客户数据库中发现不同的客户群，帮助分析人员从客户数据库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。并且用购买模式来刻画不同的客户群的特征。谁喜欢打国际长途，在什么时间，打到那里？谁喜欢打国际长途，在什么时间，打到那里？对住宅区进行聚类，确定自动提款机对住宅区进行聚类，确定自动提款机ATM的安放的安放位置位置股票市场板块分析，找出最具活力的板块龙头股股票市场板块分析，找出最具活力的板块龙头股企业信用等级分类企业信用等级分类风咬氟侥骨世比淬郊瘟盐蓉撑傻愤绚耍隘闲扫尧迹噪裹顷舵瘪沏
8、逗诅滑纷第6章聚类分析ppt课件第6章聚类分析ppt课件9l生物学领域生物学领域推导植物和动物的分类推导植物和动物的分类(门、纲、目、科、属、种门、纲、目、科、属、种)；对基因分类，获得对种群的认识对基因分类，获得对种群的认识l数据挖掘领域数据挖掘领域作为其他数学算法的预处理步骤，获得数据分布作为其他数学算法的预处理步骤，获得数据分布状况，集中对特定的类做进一步的研究状况，集中对特定的类做进一步的研究欺桑窥燥舌妙吨私多汕锚嘴戮紫鸟湘彦禄荡禽依趁炬咆青邵藐惩呻屁制茧第6章聚类分析ppt课件第6章聚类分析ppt课件10聚类分析原理介绍聚类分析原理介绍l聚类分析中聚类分析中“类类”的特征：的特征：聚
9、类所说的类不是事先给定的，而是根据数据的聚类所说的类不是事先给定的，而是根据数据的相似性和距离来划分相似性和距离来划分聚类的数目和结构都没有事先假定聚类的数目和结构都没有事先假定枣兹雌儿除虐败娩锨震腐亥数事尚颂敖论酮贸尼判滚隆拣辉猛歧铭犀挽蛔第6章聚类分析ppt课件第6章聚类分析ppt课件11有多少个簇？四个簇2个簇6个簇簇簇(类类)的概念可能是模糊的的概念可能是模糊的如何对汉语方言进行分类？如何对汉语方言进行分类？鲍使跺刑飘蝇隐体瘩沏宦囚糖饵糠精畅弃鞭仆岿减傣乙忌屿蘸酷拈盆秋部第6章聚类分析ppt课件第6章聚类分析ppt课件12聚类分析原理介绍聚类分析原理介绍l我们看以下的例子：我们看以下的
10、例子：l有有16张牌张牌l如何将他们分为如何将他们分为 一组一组的牌呢？一组一组的牌呢？AKQJ绩垛恶粥斟接孺墟霓膘腑籽弯惦悸落葵赴伍烟于如担电钉醛蜗颈迟炙瘫咀第6章聚类分析ppt课件第6章聚类分析ppt课件13聚类分析原理介绍聚类分析原理介绍l分成四组分成四组l每组里每组里花色相同花色相同l组与组之间花色相异组与组之间花色相异AKQJ花色相同的牌为一副花色相同的牌为一副Individual suits黑缔跑足兄载姆楞桥珊湍挣牵帛信豌氦糜油秆柴捍崎蜀父依农氧史惭祁丈第6章聚类分析ppt课件第6章聚类分析ppt课件14聚类分析原理介绍聚类分析原理介绍l分成四组分成四组l符号相同符号相同的牌为一组
11、的牌为一组AKQJ符号相同的的牌符号相同的的牌Like face cards械轿悟蝎翻隔寸巾敬终娜钒纷虞棱址灶柯敛蠢黎镀寅霄愿德夷云辈槐装宋第6章聚类分析ppt课件第6章聚类分析ppt课件15聚类分析原理介绍聚类分析原理介绍l分成两组分成两组l颜色相同颜色相同的牌为一组的牌为一组AKQJ颜色相同的配对颜色相同的配对Black and red suits伏只军坎篡佃洪桓消童刨驹札几曾礁策铬孜迄饮垢拱岛樱浚劣罩惹灸虱槐第6章聚类分析ppt课件第6章聚类分析ppt课件16聚类分析原理介绍聚类分析原理介绍l分成两组分成两组l大小程度相近大小程度相近的牌分到的牌分到一组一组AKQJ大配对和小配对大配对和
12、小配对Major and minor suits呼素婆夯离蛔粳肩靴倔瓶醒娃恢当诲帅卓略绦惟绒孤肝驰袍锨腮潮阴粹刀第6章聚类分析ppt课件第6章聚类分析ppt课件17聚类分析原理介绍聚类分析原理介绍l这个例子告诉我们，分这个例子告诉我们，分组的意义在于我们怎么组的意义在于我们怎么定义并度量定义并度量“相似性相似性” (Similar)l因此衍生出一系列度量因此衍生出一系列度量相似性的方法相似性的方法AKQJ大配对和小配对大配对和小配对Major and minor suits闹踊迭唤金刺摊荒领乱赊蘸陇杭隧困峙掂馒粳蕉圾化锅游陆观邱邵血听妊第6章聚类分析ppt课件第6章聚类分析ppt课件18聚类分
13、析原理介绍聚类分析原理介绍变量按测量尺度（变量按测量尺度（Measurement Level）分类）分类l区间（区间（Interval）值变量）值变量连续变量，如长度、重量、速度、温度等连续变量，如长度、重量、速度、温度等l有序（有序（Ordinal）值变量）值变量等级变量，不可加，但可比，如一等、二等、三等级变量，不可加，但可比，如一等、二等、三等奖学金等奖学金l名词性（名词性（Nominal）变量）变量类别变量，不可加也不可比，如性别、职业等类别变量，不可加也不可比，如性别、职业等l下面介绍对各种不同类型的变量如何进行度量下面介绍对各种不同类型的变量如何进行度量详伴凌颂哗嚼贬雾栖墅菊额腆凉
14、错釉誉蠢莹痴腿鸟咋曙揍跟帆侄瘸苍缴轿第6章聚类分析ppt课件第6章聚类分析ppt课件19度量对象间的相似与差异度量对象间的相似与差异l对象间的对象间的相似度相似度或或相异度相异度通常基于每对对象间的距离通常基于每对对象间的距离的计算的计算l欧几里得距离欧几里得距离lMinkowski距离距离兵岿夸磁战绚揍勇技砌鲁翼栋妊抡恳荧过谅兹逛醒匣爆香绑赐革仓味迟张第6章聚类分析ppt课件第6章聚类分析ppt课件20度量对象间的相似与差异度量对象间的相似与差异l曼哈顿距离曼哈顿距离(Block距离距离)l欧几里得距离是当欧几里得距离是当q=2时的时的Minkowski距离的特例距离的特例l曼哈顿距离是当曼
15、哈顿距离是当q=1时的时的Minkowski距离的特例距离的特例l当当q= 时得到无得到无穷距离距离(无无穷范数范数)，由向量，由向量间各分量各分量的最大差决定的最大差决定越遏明怔极疏柯滨迪替乓狼云镇晴杰锨韧喘审夕啤惺菱尿迟映涯渔砖爪驹第6章聚类分析ppt课件第6章聚类分析ppt课件21度量对象间的相似与差异度量对象间的相似与差异l距离所应满足的数学性质距离所应满足的数学性质d(i,j) 0d(i,i) = 0d(i,j) = d(j,i)d(i,j) d(i,k) + d(k,j)l除此之外，还可以使用除此之外，还可以使用加权加权的距离的距离危作椭巍茵治制忍侄戒淑呜品桥涤渝刷宏峦助川亭孤料狄
16、甸梯印号老酌铱第6章聚类分析ppt课件第6章聚类分析ppt课件22二元属性变量二元属性变量l二元变量只有两种状态：二元变量只有两种状态：0或或1例如给定描述患者的变量例如给定描述患者的变量smoker，1表示患者抽表示患者抽烟，烟，0表示不抽烟表示不抽烟l像处理一般数值量一样来处理二元变量会产生误导的像处理一般数值量一样来处理二元变量会产生误导的聚类结果聚类结果酗枚诊寇过褥磷犊灶遥缄阻囤输褐这老诽秆又泛瞎皂荒堵崇匈迹砚部多苦第6章聚类分析ppt课件第6章聚类分析ppt课件23二元属性变量的相依表二元属性变量的相依表l如果所有的二元变量具有相同的权重，则可以得到上如果所有的二元变量具有相同的权重
17、，则可以得到上表所示的两行两列的相依表表所示的两行两列的相依表q是对象是对象i和和j值都为值都为1的变量的数目的变量的数目r是在对象是在对象i值为值为1，但对象，但对象j值为值为0的变量数目的变量数目变量的总数是变量的总数是p=q+r+s+tObject iObject j侄哮碉滋耗茸颁酱些痕垃哎捣抹蔡奏盖尝葡浇呸昧敖籽贝唆捣震规婿谨领第6章聚类分析ppt课件第6章聚类分析ppt课件24对称二元变量和非对称二元变量对称二元变量和非对称二元变量l对二元变量的相异度计算还要考虑变量的对二元变量的相异度计算还要考虑变量的对称性对称性l对称二元变量对称二元变量如果他的两个状态具有同等价值和相等的权重如
18、果他的两个状态具有同等价值和相等的权重输出用输出用0或或1编码没有优先权，如性别编码没有优先权，如性别l对称二元相异度对称二元相异度栗沮衫煽晰崇绒鳖果别惟驱梅项耸舟糕宅峙糟泼当侗钢听拭迂本济登蓬删第6章聚类分析ppt课件第6章聚类分析ppt课件25对称二元变量和非对称二元变量对称二元变量和非对称二元变量l非对称二元变量非对称二元变量如果状态的输出不是同等重要的如果状态的输出不是同等重要的例如基本检查的阳性和阴性结果。根据惯例，将例如基本检查的阳性和阴性结果。根据惯例，将比较重要的输出结果比较重要的输出结果(通常也是出现机率较小的结通常也是出现机率较小的结果果)编码为编码为1，而将另一种结果编码
19、为，而将另一种结果编码为0(如如HIV阴性阴性)给定两个非对称二元变量，两个都取值给定两个非对称二元变量，两个都取值1的情况认的情况认为比两个都取值为比两个都取值0的情况更有意义的情况更有意义l非对称二元相异度非对称二元相异度资坯迢荫部呵秩呀暗粹腺蛙售凶合剁皖封山异挫颊价觉蓬揽跳拍挑憨椿侵第6章聚类分析ppt课件第6章聚类分析ppt课件26对称二元变量和非对称二元变量对称二元变量和非对称二元变量l有时采用两个二元变量的有时采用两个二元变量的相似度相似度而不是而不是相异度相异度来测量来测量他们之间的距离。他们之间的距离。l非对称二元相似度非对称二元相似度sim(i,j)如下定义如下定义l系数系数
20、sim(i,j)常称作常称作Jaccard系数系数兑谁弓抒窘屈徊饯乎笔筹彪豁骤辫孙哥侩盏嗜夺智街秤贫汛汞每敏胰鄂授第6章聚类分析ppt课件第6章聚类分析ppt课件27例例 二元变量之间的相异度二元变量之间的相异度l假设一个患者记录表包含上述属性，其中假设一个患者记录表包含上述属性，其中name是标是标识符，性别是对称二元属性，其余的属性都是非对称识符，性别是对称二元属性，其余的属性都是非对称二元属性二元属性l对于非对称属性，值对于非对称属性，值Y和和P(positive)置为置为1，值，值N(no或或negative)置为置为0如卧嫌偿观黄役龄蜕讽瘴铅酣讥靖汉奥胸杏危店棕舀硫廉虽舔谁躲恒攻它第
21、6章聚类分析ppt课件第6章聚类分析ppt课件28例例 二元变量之间的相异度二元变量之间的相异度l假设对象之间的距离只基于非对称变量来计算。根据假设对象之间的距离只基于非对称变量来计算。根据公式，三个患者公式，三个患者Jack、Mary和和Jim两两之间的两两之间的相异相异度度如下：如下：l度量显示度量显示Jim和和Mary不大可能患相似的疾病，而不大可能患相似的疾病，而Jack和和Mary最可能患相似的疾病最可能患相似的疾病劲垦叙圆税水柠烦墒榷朴漂枢廓氦熄逮厚锁辟瓜庇酚纱抹畴了李炼询理蛰第6章聚类分析ppt课件第6章聚类分析ppt课件29名词性属性变量名词性属性变量l可取多个相异值，之间没有
22、序关系可取多个相异值，之间没有序关系l如产品颜色可以取：红、黄、绿、蓝等如产品颜色可以取：红、黄、绿、蓝等也可以用也可以用0，1，2，3等代码来表示，但注意这里等代码来表示，但注意这里的数字仅是标识，不能做运算的数字仅是标识，不能做运算l两个对象两个对象i和和j之间的相异度简单的处理方法是计算不之间的相异度简单的处理方法是计算不匹配率：匹配率：其中其中p是全部变量的数目，是全部变量的数目，m是匹配的数目是匹配的数目l也可以构造一个大的二元变量数组，再按二元变量处也可以构造一个大的二元变量数组，再按二元变量处理理举毙丝免俊爪膜之钡遣筑奢鞘捞臭非破蹲矛牟桥朗侣记恒创圭四制愿裕刃第6章聚类分析ppt
23、课件第6章聚类分析ppt课件30余弦相似度余弦相似度l文档数据文档数据胸毛遗慎唐戎浅范怠改宵奉剃瑟腹涸熙闰掖膨膊念但翔羔钓蟹恬肋咯卧淌第6章聚类分析ppt课件第6章聚类分析ppt课件31l 在在信信息息检索索、文文本本文文档档聚聚类和和生生物物学学分分类中中，需需要要对包含了大量符号包含了大量符号实体的复体的复杂对象象进行比行比较和聚和聚类l为了了测量量复复杂对象象间的的距距离离，通通常常期期望望放放弃弃传统的的度度量距离量距离计算，而引入算，而引入非度量非度量的相似度函数的相似度函数l 如果如果d1 和和 d2 是两个文档向量，是两个文档向量，则 cos( d1, d2 ) = (d1 d2
24、) / |d1| |d2| , l 其其中中 表表示示向向量量的的点点积(内内积)，| d |表表示示向向量量的的范范数数.l问题：余余弦弦相相似似度度的的范范围？取取最最大大值时是是否否两两个个向向量量相等？相等？余弦相似度余弦相似度单锈强决铝钾侣速绑友得鸵烽虏兴葱娄泰绩敷嫉廖袁骏诅臭蚀艰蓟捻冶尝第6章聚类分析ppt课件第6章聚类分析ppt课件32余弦相似度计算的例子余弦相似度计算的例子ld1 = 3 2 0 5 0 0 0 2 0 0 ld2 = 1 0 0 0 0 0 0 1 0 2 ld1 d2 = 3*1 + 2*0 + 0*0 + 5*0 + 0*0 + 0*0 + 0*0 + 2
25、*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轨辞守击刷拂崭去壳涪径夜往危泼爱慈含包榔冒奋捌穴送了拽省振抒泻纠第6章聚类分析ppt课件第6章聚类分析ppt课件33如何选择恰当的度量如何选择恰当的度量l有很多方法用来选择一个具体的相似度或距离函数，有很多
26、方法用来选择一个具体的相似度或距离函数，但是还没有一个通用的标准用来指导这样的选择但是还没有一个通用的标准用来指导这样的选择l这种度量的选择高度依赖于具体的应用。这种度量的选择高度依赖于具体的应用。抓涎姿踩办拇钡豪粹僵罩钉胃懂会嵌旭甥染吵愧帘扑皱壤痊蘸郎予顽荐淳第6章聚类分析ppt课件第6章聚类分析ppt课件34主要聚类方法的分类主要聚类方法的分类l划分方法划分方法：给定：给定n个对象，划分方法构建数据的个对象，划分方法构建数据的k个个划分，每个划分表示一簇，划分，每个划分表示一簇，k=n，满足如下要求，满足如下要求每组至少包含一个对象每组至少包含一个对象每个对象必须只属于一个组每个对象必须只
27、属于一个组(在软聚类技术中可放在软聚类技术中可放宽宽)l对于给定的划分数目对于给定的划分数目k，通常创建一个初始划分，然，通常创建一个初始划分，然后采用迭代方法尝试通过对象在组间移动来改进划分后采用迭代方法尝试通过对象在组间移动来改进划分摇乾出有湘吠侧童腾侈朴膛申放角屎屋悄雷馋诚漠私精扳睦笨咐即眉臀访第6章聚类分析ppt课件第6章聚类分析ppt课件35主要聚类方法的分类主要聚类方法的分类l好的划分的标准：同一个簇中的对象之间尽可能相似，好的划分的标准：同一个簇中的对象之间尽可能相似，不同簇的对象尽可能有大的差异不同簇的对象尽可能有大的差异l常用方法：常用方法：k均值方法：每个簇都用该簇中对象的
28、均值来表示均值方法：每个簇都用该簇中对象的均值来表示k中心点法：每个簇用接近簇中心的一个对象来表中心点法：每个簇用接近簇中心的一个对象来表示示馋糖陈苇票痞罢丝困拒永股粮渤宠汾籍酬曲斑张向委肩寞肄从缅嘶纂徽彪第6章聚类分析ppt课件第6章聚类分析ppt课件36l层次方法创建给定数据对象的层次分解层次方法创建给定数据对象的层次分解l根据使用的方法，层次的方法可以分类为凝聚的或分根据使用的方法，层次的方法可以分类为凝聚的或分裂的方法裂的方法凝聚法：也称自底向上的方法，开始将每个对象凝聚法：也称自底向上的方法，开始将每个对象形成单独的组，然后逐次合并相近的对象或组，形成单独的组，然后逐次合并相近的对象
29、或组，直到所有的组合并为一个或满足某个终止条件直到所有的组合并为一个或满足某个终止条件分裂法：自顶向下的方法，一开始将所有对象置分裂法：自顶向下的方法，一开始将所有对象置于一个簇中，每次迭代，簇分裂为更小的簇，直于一个簇中，每次迭代，簇分裂为更小的簇，直到每个对象在一个簇中或满足终止条件到每个对象在一个簇中或满足终止条件层次方法层次方法柞腕闽屯便诵泼屎湛所右藐事辰妆灸烬翼郎嘿狼惹腰犊肉狱要蕴蔓腑惺民第6章聚类分析ppt课件第6章聚类分析ppt课件37基于模型的方法基于模型的方法l为每簇假定一个模型，并寻找数据对给定模型的最为每簇假定一个模型，并寻找数据对给定模型的最 佳拟合佳拟合l常见算法常见
30、算法EM算法：基于统计模型并进行期望最大化分析算法：基于统计模型并进行期望最大化分析COBWEB：概念学习算法，进行概率分析并把概：概念学习算法，进行概率分析并把概念作为簇模型念作为簇模型SOM(自组织映射自组织映射)：一种基于神经网络的算法，：一种基于神经网络的算法，通过把高维数据映射到通过把高维数据映射到2维或维或3维特征空间进行聚维特征空间进行聚类类骄吨民已博奈渊这逢嘶计母城教腑宵澡骋匈谚衙躁巧排把栅未霹婿猫呐圾第6章聚类分析ppt课件第6章聚类分析ppt课件38划分聚类划分聚类原始点原始点划分聚类划分聚类加漂着易主柳缅兽饮零风搞府眺存禾除盲遗口擅筹羡哩癸冈肿驮捡振塌麓第6章聚类分析pp
31、t课件第6章聚类分析ppt课件39层次聚类层次聚类Traditional Hierarchical ClusteringNon-traditional Hierarchical ClusteringNon-traditional DendrogramTraditional Dendrogram墅倚很衔祁岔逝载溯嘶赔男棍獭劣遭泽俄矽汹卞赚镍御章顶罕庶铝嚎躁堡第6章聚类分析ppt课件第6章聚类分析ppt课件40l互斥的与非互斥的互斥的与非互斥的在非互斥聚类中，点可以属于多个簇在非互斥聚类中，点可以属于多个簇.可以表示多重类或边界类可以表示多重类或边界类l模糊聚类与非模糊聚类模糊聚类与非模糊聚类模糊
32、聚类中，一个点到隶属于每个簇的情况可模糊聚类中，一个点到隶属于每个簇的情况可以用一个在以用一个在0到到1之间的隶属度描述之间的隶属度描述其他的聚类类型的差别其他的聚类类型的差别悦噪釜宴效鬼棠准标博掘厘覆救氏斯塌巩暴田湃钩镇酣钧画帖剩毡扦颓部第6章聚类分析ppt课件第6章聚类分析ppt课件41不同的簇类型不同的簇类型l明显分离的簇明显分离的簇l基于中心的簇基于中心的簇l基于近邻的簇基于近邻的簇l基于密度的簇基于密度的簇l概念簇概念簇奎佃讹基驳弃啥侠栈层钢配怀葛泥传仅悬拖砸肆蚕夸夸抗此久错燎名缮僚第6章聚类分析ppt课件第6章聚类分析ppt课件42不同的簇类型不同的簇类型l明显分离的簇明显分离的簇
33、: 每个点到同簇中任意点的距离比到不同簇中所每个点到同簇中任意点的距离比到不同簇中所有点的距离更近有点的距离更近3 个明显分离的簇个明显分离的簇词蠕理仁疽膀盲贾衔路戚锡小趴苞庸余窥脆甲枢筹礁计出懂殖淹塑云换寥第6章聚类分析ppt课件第6章聚类分析ppt课件43不同的簇类型不同的簇类型l基于中心的簇基于中心的簇 每个点到其簇中心的距离比到任何其他簇中心每个点到其簇中心的距离比到任何其他簇中心的距离更近的距离更近 簇的中心通常是重心，簇中所有点的平均值，簇的中心通常是重心，簇中所有点的平均值，或者是簇的原型，即一个簇中最具代表性的点或者是簇的原型，即一个簇中最具代表性的点4 center-base
34、d clusters设诸拭卢敷酋器烧谁釜乡烩氧何析济惯缸晃湾楼知萨蚤琢坍部审潞卒待竞第6章聚类分析ppt课件第6章聚类分析ppt课件44不同的簇类型不同的簇类型l基于近邻的簇基于近邻的簇(基于图的基于图的连通分支连通分支)每个点到该簇中至少一个点的距离比到不同簇每个点到该簇中至少一个点的距离比到不同簇中任意点的距离更近中任意点的距离更近8 contiguous clusters频甚苔淮肯涉铣出滋门矾槛笨础凝韧蒜排弧缠诚握唆椿阀乌命橙藻遗趾糖第6章聚类分析ppt课件第6章聚类分析ppt课件45不同的簇类型不同的簇类型l基于密度的簇基于密度的簇簇是被低密度区域分开的高密度区域簇是被低密度区域分开的
35、高密度区域. 当簇不规则或互相盘绕，并且有噪声和离群点当簇不规则或互相盘绕，并且有噪声和离群点时，通常使用基于密度的簇定义时，通常使用基于密度的簇定义6 density-based clusters冶博殊升琳尖犁汞诡猩涪走全迷掂猪狭诵孝认陵辐誓鞍勉董禄否访抡辅谚第6章聚类分析ppt课件第6章聚类分析ppt课件46划分方法划分方法l对于一个给定的对于一个给定的n个对象或元组的数据库，采用目标个对象或元组的数据库，采用目标函数最小化的策略，通过迭代把数据分成函数最小化的策略，通过迭代把数据分成k个划分块，个划分块，每个划分块为一个簇，这就是划分方法。每个划分块为一个簇，这就是划分方法。 l划分方法
36、满足两个条件：划分方法满足两个条件：（1）每个分组至少包含一个对象；）每个分组至少包含一个对象；（2）每个对象必属于且仅属于某一个分组。）每个对象必属于且仅属于某一个分组。 l常见的划分方法有常见的划分方法有k-均值方法和均值方法和k-中心点方法。其他中心点方法。其他方法大都是这两种方法的变形。方法大都是这两种方法的变形。 楼目百韵亮啡劲准锌砍僵牙泻憋锤烂乳酶肾约泣殷涟泌裳黄侨堵副溺屁砍第6章聚类分析ppt课件第6章聚类分析ppt课件47k-均值算法均值算法 lk-均值聚类算法的核心思想是通过迭代把数据对象划均值聚类算法的核心思想是通过迭代把数据对象划分到不同的簇中，以求分到不同的簇中，以求目
37、标函数目标函数最小化，从而使生成最小化，从而使生成的簇尽可能地紧凑和独立。的簇尽可能地紧凑和独立。随机选取随机选取k个对象作为初始的个对象作为初始的k个簇的质心；个簇的质心；将其余对象根据其与各个簇质心的距离分配到最将其余对象根据其与各个簇质心的距离分配到最近的簇；再求新形成的簇的质心。近的簇；再求新形成的簇的质心。这个迭代重定位过程不断重复，直到目标函数最这个迭代重定位过程不断重复，直到目标函数最小化为止。小化为止。 枕腺佩术廓饶果榆仙坟帧铣痊碧堪拖沁哲觉橱哑滋想锤霍肢屿锅辟着说姆第6章聚类分析ppt课件第6章聚类分析ppt课件48k-均值算法均值算法 算法算法K均值均值输入输入K：簇的数目
38、：簇的数目D：包含：包含n个对象的点集个对象的点集输出输出K个簇的集合个簇的集合方法方法1从从D中任意选择中任意选择K个点作为初始簇中心个点作为初始簇中心2Repeat3根据簇中对象的均值，将每个对象再指派到最相似的簇根据簇中对象的均值，将每个对象再指派到最相似的簇4更新簇均值，即计算每个簇中对象的均值更新簇均值，即计算每个簇中对象的均值5Until 不再发生变化不再发生变化粳献肮呼净驮凹快办缎杠乳愧氰脏管予掂籽梗权乌册枣覆荔薄变模二市总第6章聚类分析ppt课件第6章聚类分析ppt课件49初始质心的选择非常重要初始质心的选择非常重要俏驭叉酱妇兹靴狈尘采娘拘讹妓纽幻涨讲蔓磋窥援肩隘蕉迈捌鸿灯缘馏
39、石第6章聚类分析ppt课件第6章聚类分析ppt课件50使用使用K均值算法的迭代过程均值算法的迭代过程壁纳甜苇附舱源钙携淳悄居蹲钵掺夹婚粹关廖驴算锯痒沸阑温妻狐涵镶尘第6章聚类分析ppt课件第6章聚类分析ppt课件51K-K-均值算法均值算法 012345678910012345678910012345678910012345678910K=2Arbitrarily choose K object as initial cluster centerAssign each objects to most similar centerUpdate the cluster meansUpdate th
40、e cluster meansreassignreassign逢陇鞘酝弄根本逸肛号鳃捐斌提坝附菠拾熔赫绣括英方缴界尔曳棱走潭漫第6章聚类分析ppt课件第6章聚类分析ppt课件52欧几里得空间中的数据欧几里得空间中的数据l通常使用误差的平方和通常使用误差的平方和(sum of the squared error, SSE)作为度量聚类质量的目标函数作为度量聚类质量的目标函数lSSE也称散布也称散布(scatter)：计算每个数据点的误差：计算每个数据点的误差即它到最近质心的欧几里得距离，然后计算误差的即它到最近质心的欧几里得距离，然后计算误差的 平方和平方和l给定由两次运行给定由两次运行K均值产
41、生的两个不同的簇集，我们均值产生的两个不同的簇集，我们更喜欢误差的平方和最小的那个，这意味着聚类的更喜欢误差的平方和最小的那个，这意味着聚类的 原型原型(质心质心)是簇中点的更好代表是簇中点的更好代表滓划承兜誊压溯诽彤以盲网柑粱冀碎鼓碗楞嗅讲片慕众响哭延样辛哲搀忧第6章聚类分析ppt课件第6章聚类分析ppt课件53欧几里得空间中的数据欧几里得空间中的数据l可以证明在欧几里得空间中是簇的可以证明在欧几里得空间中是簇的SSE最小的质心最小的质心 就是均值就是均值lK均值算法的第均值算法的第3步和第步和第4步试图直接最小化步试图直接最小化SSE步骤步骤3通过将点指派到最近的质心形成簇，最小化通过将点
42、指派到最近的质心形成簇，最小化关于给定质心集的关于给定质心集的SSE步骤步骤4重新计算质心，进一步最小化重新计算质心，进一步最小化SSEl问题：问题：K均值的步骤均值的步骤3和和4只能找到关于只能找到关于SSE的的局部最局部最小值小值，因为它们是对选定的质心和簇，而不是对，因为它们是对选定的质心和簇，而不是对 所所有可能的选择来优化有可能的选择来优化SSE炸熬耘保疾讣论刘蔑醚豫浙烹拽尾韧话飞晦似蚊捷接鲁豫刀颗敏稻维奎寒第6章聚类分析ppt课件第6章聚类分析ppt课件54初始质心的选择非常重要初始质心的选择非常重要蓖篱荣匪洋鞋亚艰鲍秦塞赶臀诉箍竟鞍砰诈苟驼冷搬易胚衡沥熄瑚爆匝秆第6章聚类分析pp
43、t课件第6章聚类分析ppt课件55初始质心的选择非常重要初始质心的选择非常重要闹催矣漾颐谣判氓全底策旋咎摹鲍级觉杆浅獭呀效锋喷痢撵寇琉同磺邦澡第6章聚类分析ppt课件第6章聚类分析ppt课件56随机初始化随机初始化l由于由于K均值算法会陷入局部最小值而得到次优聚类，均值算法会陷入局部最小值而得到次优聚类，一种常用的选取初始质心的方法是多次运行，每次使一种常用的选取初始质心的方法是多次运行，每次使用一组不同的随机初始质心，然后选取具有最小用一组不同的随机初始质心，然后选取具有最小SSE的簇集的簇集l下面我们看一看这种方法的问题下面我们看一看这种方法的问题l下页的图中有下页的图中有5个簇对，每个簇
44、对有上下两个簇。个簇对，每个簇对有上下两个簇。如果每个簇对有两个初始质心，则效果较好如果每个簇对有两个初始质心，则效果较好如果有一个簇对中只有一个初始中心，而另一个如果有一个簇对中只有一个初始中心，而另一个簇对中有三个初始中心，则会出现错误。簇对中有三个初始中心，则会出现错误。棋敖窿瑞氮斡探尽茧朵迸出始积又诅闯迟虐西良郴生凤砧匈杏嘲瑟森誊种第6章聚类分析ppt课件第6章聚类分析ppt课件57Starting with two initial centroids in one cluster of each pair of clusters5个簇对，个簇对，10个簇的例子个簇的例子槽溯迹氯垃烷宴
45、宪臻皮刃唁侣颂约注喀罢濒燎浓抗余啊竭酶候嫡宵幅浸墨第6章聚类分析ppt课件第6章聚类分析ppt课件58Starting with two initial centroids in one cluster of each pair of clusters5个簇对，个簇对，10个簇的例子个簇的例子靛娟头扦集靡粗殃锯捣绣斡运围绦吃苹疮嫉憨彩摘聚恋灯擒一既纂壹乱巾第6章聚类分析ppt课件第6章聚类分析ppt课件59Starting with some pairs of clusters having three initial centroids, while other have only one.
46、5个簇对，个簇对，10个簇的例子个簇的例子锄诸箩铆沥睹限都霸越允嘶邹短近仍船比售嗡账奉殆煽首击趣榆亨验蘑咸第6章聚类分析ppt课件第6章聚类分析ppt课件60Starting with some pairs of clusters having three initial centroids, while other have only one.5个簇对，个簇对，10个簇的例子个簇的例子磊哼社膳贤咎柜钉拆祥算炸古谍牺睁叔佬它跳挣喘噬咳捻踢涪香时练容褥第6章聚类分析ppt课件第6章聚类分析ppt课件61解决初始质心设置问题的方法解决初始质心设置问题的方法l多次运行多次运行不一定总有效不一定总有效
47、l对数据作采样并使用层次聚类，从中提取对数据作采样并使用层次聚类，从中提取K个簇并使个簇并使用这些簇的质心作为初始质心用这些簇的质心作为初始质心l选取多于选取多于k个的初始质心，然后从其中选择个的初始质心，然后从其中选择k个个最分离的最分离的k个点个点l后处理后处理l二分二分K-均值均值盘涎吝京凋须琼离颁名缓宿肘研盘冀豢瘸沈嘴论穆服雕诬刽掇墓萎歧佯凄第6章聚类分析ppt课件第6章聚类分析ppt课件62二分二分K均值均值l基本思想：基本思想：l为了得到为了得到K个簇，将所有点的集合分裂成两个簇，从个簇，将所有点的集合分裂成两个簇，从这些簇中选取一个继续分裂，如此下去直到产生这些簇中选取一个继续分
48、裂，如此下去直到产生K个个簇簇l可以使用多种方法选择待分裂的簇可以使用多种方法选择待分裂的簇最大的簇最大的簇具有最大具有最大SSE的簇的簇基于大小和基于大小和SSEl二分二分K均值得到的最终的簇集并不代表使均值得到的最终的簇集并不代表使SSE局部最局部最小的聚类小的聚类雏裂搁炉狈荤混恒此爆纹子橱稚能胳揭愤胚劝晦浦毫茵养案秋镶醉澜肖汕第6章聚类分析ppt课件第6章聚类分析ppt课件63二分二分K均值算法均值算法算法算法二分二分K均值均值1初始化簇表，使之包含有所有的点组成的簇初始化簇表，使之包含有所有的点组成的簇2Repeat3从簇表中取出一个簇从簇表中取出一个簇4对选定的簇进行多次二分试验对选
49、定的簇进行多次二分试验5for i=1 to 试验次数试验次数 do6 使用基本使用基本K均值，二分选定的簇均值，二分选定的簇7end for8从二分试验中选择具有最小总从二分试验中选择具有最小总SSE的两个簇的两个簇9将这两个簇添加到簇表中将这两个簇添加到簇表中10until 簇表中包含簇表中包含K个簇个簇叛墓付董洼倪卫蔓讫王股弟辛廖级摆拆羞抿捎漏狄恶氖速佛崔莲框买相蜒第6章聚类分析ppt课件第6章聚类分析ppt课件64二分二分K-均值的例子均值的例子弱泅碾骡酱廉慧鸣妖镶北娜楞慧篱碗痕怨嘿挣迪聂菇需垦表赢滤坎撵灭恢第6章聚类分析ppt课件第6章聚类分析ppt课件65K-均值方法的缺陷均值方法
50、的缺陷lK-均值方法当簇在下述方面有较大不同时会出现问题均值方法当簇在下述方面有较大不同时会出现问题 不同大小不同大小不同密度不同密度非球形的形状非球形的形状密舆痰朔掺普授藩右辊枉袁端舀超阑根镭喇卑嘘威趋详啄渣饶言涕墓沮儿第6章聚类分析ppt课件第6章聚类分析ppt课件66Original PointsK-means (3 Clusters)K-均值的缺陷：不同的簇大小均值的缺陷：不同的簇大小WHY？没藉坟绥莽产拂欧狮翅干暑打逸申械身慕痞瞧摊迷简眷富呛磐挺妊瓤胎点第6章聚类分析ppt课件第6章聚类分析ppt课件67Original PointsK-means (3 Clusters)K-均值的
51、缺陷均值的缺陷不同的密度分布不同的密度分布WHY？厚矫婪授冕枝脂姆莽懒酚睡乘甩梁蔬标凰拧魁三橡泥次茁艳汝匿钒畸期返第6章聚类分析ppt课件第6章聚类分析ppt课件68Original PointsK-means (2 Clusters)K均值的缺陷：非球形形状均值的缺陷：非球形形状K均值目标函数是最小化等尺度和等密度的球形簇，或明显分均值目标函数是最小化等尺度和等密度的球形簇，或明显分离的簇离的簇敖北学宋耸统勿是酱拨立备赫耗倘馈姓殉渗慎死妆笨掷捏攘努晓宏曰芯胃第6章聚类分析ppt课件第6章聚类分析ppt课件69Original PointsK-means Clusters一种方法是使用更多的簇
52、，再反过来使其部分合并一种方法是使用更多的簇，再反过来使其部分合并克服克服K均值方法的缺陷均值方法的缺陷板看疤吻骗惊彬给蛆茵楔骡巷振奥疵棋毒砧讥创锨袜制泣蓑瞒六衡帘啮看第6章聚类分析ppt课件第6章聚类分析ppt课件70Original PointsK-means Clusters克服克服K均值方法的缺陷均值方法的缺陷啊啪缩纂软唾互知釉互使赞坏备籍懦凶厘递肃嘴管佛实屠稽攘喷丑蓖溢耐第6章聚类分析ppt课件第6章聚类分析ppt课件71Original PointsK-means Clusters克服克服K均值方法的缺陷均值方法的缺陷辉箱傻址眼差盎率祁宁艺翘陛珊鹊卸疥杰缠埔骏逮汇晚镭预挂儒掷恕轻绍
53、第6章聚类分析ppt课件第6章聚类分析ppt课件72层次聚类方法层次聚类方法l定义：对给定的数据进行层次的分解：定义：对给定的数据进行层次的分解：l凝聚的（凝聚的（agglomerative）方法（自底向上）方法（自底向上）思想：一开始将每个对象作为单独的一组，然后思想：一开始将每个对象作为单独的一组，然后根据同类相近，异类相异的原则，合并对象，直根据同类相近，异类相异的原则，合并对象，直到所有的组合并成一个，或达到一个终止条件为到所有的组合并成一个，或达到一个终止条件为止。止。l分裂的方法（分裂的方法（divisive）（自顶向下）（自顶向下）思想：一开始将所有的对象置于一类，在迭代的思想：
54、一开始将所有的对象置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每每一步中，一个类不断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终止条件。个对象在单独的一个类中，或达到一个终止条件。 讣啦羌碗犬树待镁皇披程挥链仇评有蝇止遍稻庆碾俏减皇麦堪圭膀湍铬购第6章聚类分析ppt课件第6章聚类分析ppt课件73凝聚的和分裂的层次聚类凝聚的和分裂的层次聚类 胶溯惩腾治捉滴捉栗田织穴馈锄涨夸泼谴亭损劲恭婚币匿岔纷虏邻供跨擞第6章聚类分析ppt课件第6章聚类分析ppt课件74层次聚类方法层次聚类方法l产生一个相邻簇的集合，通常用一棵树来表示产生一个相邻簇的集合，通常用一棵树来表示lCa
55、n be visualized as a dendrogram树状图记录了分裂或合并的序列树状图记录了分裂或合并的序列以树状图和嵌套簇图显示的以树状图和嵌套簇图显示的4个点的层次聚类个点的层次聚类喊炳暗貉坏净招拯颖骗印靛拥罕遍粹欠派戮应而前喧邢臻盲姜扛苯挫蜘靡第6章聚类分析ppt课件第6章聚类分析ppt课件75层次聚类法的特点层次聚类法的特点l不用预知不用预知(预设预设)簇的数目簇的数目任何需要簇数的聚类可以通过在树状图的适当层任何需要簇数的聚类可以通过在树状图的适当层次切割而得到次切割而得到l得到更有意义的结构得到更有意义的结构如生物学中的分类如生物学中的分类l传统的层次聚类算法使用相似度矩
56、阵或距离矩阵传统的层次聚类算法使用相似度矩阵或距离矩阵每次合并或分裂一个簇每次合并或分裂一个簇催蹄盅淖幌助傈怔篱构户就鸦慨辅川力箔躬娜乎惋凳学警坎讯攻欢意疵镜第6章聚类分析ppt课件第6章聚类分析ppt课件761 计算距离矩阵计算距离矩阵2 令每个点为一个簇令每个点为一个簇3 Repeat4 合并最接近的两个簇合并最接近的两个簇5 更新距离矩阵更新距离矩阵6 until 仅剩下一个簇仅剩下一个簇基本凝聚层次聚类算法基本凝聚层次聚类算法矿拿噪叹癸芭家狡驴桅索勾选癣诡霍乓梁仗蹲哩铡桂涕犹轨蔷磐山碰肘城第6章聚类分析ppt课件第6章聚类分析ppt课件77l关键步骤在于计算两个簇之间的邻近度关键步骤在
57、于计算两个簇之间的邻近度不同的定义簇之间的距离的方法区分了不同的不同的定义簇之间的距离的方法区分了不同的算法算法基本凝聚层次聚类算法基本凝聚层次聚类算法辞阻悄钥编师祷瓢瑞琴鉴刻为剩再脚鞠藩漫荧三霄蒙碎姬沙苹潮把蓖挑郎第6章聚类分析ppt课件第6章聚类分析ppt课件78开始开始.l每个点为一个簇，计算各个簇两两之间的距离矩阵每个点为一个簇，计算各个簇两两之间的距离矩阵p1p3p5p4p2p1p2p3p4p5. . .距离矩阵距离矩阵努异厂漫恫荣锥坐户撮窍坏作绍崭社耙芦昨隧追善所门荚若凭靴衍蝎溜缠第6章聚类分析ppt课件第6章聚类分析ppt课件79接下来接下来.l经过若干凝聚步骤，得到如下的簇经过
58、若干凝聚步骤，得到如下的簇 C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5距离矩阵距离矩阵岂鞘悟琢窘侠音磨酶寄涉封倘宦醋刊封扬渐人品墓畔幅撮杀尼豁术土禽弘第6章聚类分析ppt课件第6章聚类分析ppt课件80接下来接下来.l合并两个最靠近的簇合并两个最靠近的簇 (C2 和和 C5) 并更新距离矩阵并更新距离矩阵C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5距离矩阵距离矩阵咱蛋贬倘沈信棍洞沽沽沾尚溃妒己姻奏仅健尤泊呸姻晴鸵掣亏雁踪微墓疵第6章聚类分析ppt课件第6章聚类分析ppt课件81合并后合并后l问题变为如何更新距离矩阵问题变为如何更新距离矩阵C1C4C2 U C5
59、C3? ? ? ? ?C2 U C5C1C1C3C4C2 U C5C3C4距离矩阵距离矩阵蚌姥歉曳令绘庶尚燎剃囤魔臆糟呼造潮生魔段黍凶瑟薄追偏评菲坷声蒋滓第6章聚类分析ppt课件第6章聚类分析ppt课件82 p1p3p5p4p2p1p2p3p4p5. . .距离距离lMIN(单链单链)lMAX(全链全链)lGroup Average(组平均组平均)l质心的距离质心的距离l其他的源自目标函数的方法其他的源自目标函数的方法Ward方法使用平方差方法使用平方差距离矩阵距离矩阵如何定义簇之间的邻近度如何定义簇之间的邻近度酝晌结澳沟唇续篱泅烃茧圭锥瓢炼笛痈时抡私翰恿刽翘泽旧笼弓隔猫碉帧第6章聚类分析pp
60、t课件第6章聚类分析ppt课件83 p1p3p5p4p2p1p2p3p4p5. . .距离矩阵距离矩阵lMIN(单链单链)lMAX(全链全链)lGroup Average(组平均组平均)l质心的距离质心的距离l其他的源自目标函数的方法其他的源自目标函数的方法Ward方法使用平方差方法使用平方差如何定义簇之间的邻近度如何定义簇之间的邻近度操猎焊迹蛊铜怎弄扫乖忆掺耙罩藏肚跪卉楼愤评伐躬缚酒力瞧盗庞喷兼周第6章聚类分析ppt课件第6章聚类分析ppt课件84 p1p3p5p4p2p1p2p3p4p5. . .距离矩阵距离矩阵lMIN(单链单链)lMAX(全链全链)lGroup Average(组平均组
61、平均)l质心的距离质心的距离l其他的源自目标函数的方法其他的源自目标函数的方法Ward方法使用平方差方法使用平方差如何定义簇之间的邻近度如何定义簇之间的邻近度箍豫若少幼籽蘑慎价高东蓄往傣乃撅局绪繁掏物盯镭行于玲偶芦抹坚襄呈第6章聚类分析ppt课件第6章聚类分析ppt课件85 p1p3p5p4p2p1p2p3p4p5. . .距离矩阵距离矩阵lMIN(单链单链)lMAX(全链全链)lGroup Average(组平均组平均)l质心的距离质心的距离l其他的源自目标函数的方法其他的源自目标函数的方法Ward方法使用平方差方法使用平方差如何定义簇之间的邻近度如何定义簇之间的邻近度腐耳镐铜藻钥朱喇簇磅斑
62、户斥垃遥耍弯虾莉急咏戊慨躲拾瞥坛琳要倚稼呼第6章聚类分析ppt课件第6章聚类分析ppt课件86 p1p3p5p4p2p1p2p3p4p5. . .距离矩阵距离矩阵 lMIN(单链单链)lMAX(全链全链)lGroup Average(组平均组平均)l质心的距离质心的距离l其他的源自目标函数的方法其他的源自目标函数的方法Ward方法使用平方差方法使用平方差如何定义簇之间的邻近度如何定义簇之间的邻近度濒欠碍谈伙颁晕所陪裸孪荚环揽阻一斌蜗器艘两泽蜂拭厉仲吨猎扦珠唐合第6章聚类分析ppt课件第6章聚类分析ppt课件87MIN或单链或单链l两个簇之间的邻近度基于两个簇中最近的两个点的距两个簇之间的邻近度
63、基于两个簇中最近的两个点的距离离由一个点对决定，或者说由图中的一条链决定由一个点对决定，或者说由图中的一条链决定12345皱耍坛扣镑函巧局钎渊压堤恋砸主肖睬蕴避傻爬嵌蓟之逝粪帽殊嵌窍厚施第6章聚类分析ppt课件第6章聚类分析ppt课件88Nested ClustersDendrogram12345612345层次聚类层次聚类: MIN炊床孽批库判术栋洪易铜朋未异帛蔗讼川烽砷曳浑僧扁踩剐拽君硕谰卞愿第6章聚类分析ppt课件第6章聚类分析ppt课件89Original PointsTwo Clusters可以处理非椭圆的形状可以处理非椭圆的形状MIN的优点的优点务斜熄淄旦臀诣冠钒蛙允粟惮岿娇同剑遍
64、捡轧铃决紧跌阻凋赘季返鞭衰额第6章聚类分析ppt课件第6章聚类分析ppt课件90Original PointsTwo Clusters 对噪声点和离群点很敏感对噪声点和离群点很敏感MIN的不足的不足沮殿烫焕虹赋抽悍资钟夫胆啼仟泄寄朴佩途敢碾确铂蛊侦实驰上搂础页毗第6章聚类分析ppt课件第6章聚类分析ppt课件91MAX或全链或全链l两个簇之间的邻近度由两个簇间最不相似的两个簇之间的邻近度由两个簇间最不相似的(最大距最大距离的离的)点对决定点对决定由两个簇中所有的点对决定由两个簇中所有的点对决定12345令捎褂尼喝捌辊白贸丁签机豫亨烦士痕隙免度箭诌嵌褐庇胚币缆裴杀侯莽第6章聚类分析ppt课件第6
65、章聚类分析ppt课件92Nested ClustersDendrogram12345612534MAX或全链或全链毋弟措酬版藤帝距镶奢漱荤甘遂猖低敏怎篡鹿络山徐个禁孔佛黎滥肋郴蹋第6章聚类分析ppt课件第6章聚类分析ppt课件93Original PointsTwo Clusters对噪声点和离群点不太敏感对噪声点和离群点不太敏感MAX的优点的优点嵌锤趟票姑扶烬涨戈陋戎惠卯洛胳侗臂特它敷砍筋氏朗立辆雄愧仗沃嘴灼第6章聚类分析ppt课件第6章聚类分析ppt课件94Original PointsTwo Clusters倾向于分裂大的簇倾向于分裂大的簇倾向于球状的簇倾向于球状的簇MAX的不足的不足涪
66、渝豪谭琴糖杆座亭徊攫救羔傻港釉给溶柔东怀檀轧衔麻样齐猜侍淖讼秉第6章聚类分析ppt课件第6章聚类分析ppt课件95组平均组平均l两个簇的邻近度定义为不同簇的所有点对的平均逐对邻近度两个簇的邻近度定义为不同簇的所有点对的平均逐对邻近度lNeed to use average connectivity for scalability since total proximity favors large clusters12345贪芳衙骏野盈蛋拇影紊销稚夜桩蹲岭舵逆行瑟筷城遇肝站艘挖风疯磷慷踊第6章聚类分析ppt课件第6章聚类分析ppt课件96Nested ClustersDendrogram123
67、45612534组平均组平均酮酌书琅霓薄抑批毕葛吁苍歧钮钵贪与孰燥驯约癌遣榆肝捧堡匡彩氧孤际第6章聚类分析ppt课件第6章聚类分析ppt课件97组平均组平均l是单链和全链之间的一个折中，该法利用了所有样是单链和全链之间的一个折中，该法利用了所有样本的信息，被认为是较好的层次聚类法本的信息，被认为是较好的层次聚类法l优点优点对噪声和离群点不太敏感对噪声和离群点不太敏感l不足不足倾向于球状的簇倾向于球状的簇镇川隅背剩召愈置姻沿彭雕里屯左照种躲踌吞亮埂畴摘峦笨逆袁凸帅爸稿第6章聚类分析ppt课件第6章聚类分析ppt课件98 Ward方法和质心方法方法和质心方法l两个簇的邻近度定义为两个簇合并时导致的
68、平方误差两个簇的邻近度定义为两个簇合并时导致的平方误差的增量，该方法使用的目标函数与的增量，该方法使用的目标函数与K均值相同均值相同可以证明，当取距离的平方作为两个点间的邻近可以证明，当取距离的平方作为两个点间的邻近度时，度时，Ward方法与组平均方法相似方法与组平均方法相似l对噪声和离群点不太敏感对噪声和离群点不太敏感l倾向于球状的簇倾向于球状的簇l可以用来初始化可以用来初始化K均值方法均值方法撑瓤瞎花访恫骗钨虞紫咱狈丧组催买笛糟钝即氟弹清刨抹访漆刑九绥惶盅第6章聚类分析ppt课件第6章聚类分析ppt课件99层次聚类法：比较层次聚类法：比较Group AverageWards Method1
69、2345612534MINMAX123456125341234561253412345612345曰宝弗凉疥晋皿述门讥猫凰怂娟赵珍踪菇宋克肾标津姿丸乎恩帮字鹃溯茧第6章聚类分析ppt课件第6章聚类分析ppt课件100lO(N2) 空间复杂度，因为要存储邻近度矩阵，空间复杂度，因为要存储邻近度矩阵，N为点为点的数目的数目l最坏情况下最坏情况下O(N3) 的时间复杂度的时间复杂度共有共有N步，在每一步中要更新和搜索步，在每一步中要更新和搜索N2规模的邻规模的邻近度矩阵近度矩阵在某些算法中可以接近在某些算法中可以接近O(N2 log(N) ) 的时间复杂的时间复杂度度层次聚类：时间和空间复杂度层次聚
70、类：时间和空间复杂度役逐陕埂膀雷毖搭买膊激屁绕缉第牺欠斟援涯欧蛹氖贤靡碱黔妙搀狗碑悠第6章聚类分析ppt课件第6章聚类分析ppt课件101层次聚类方法的优缺点层次聚类方法的优缺点l层次聚类方法的优点在于可以在不同粒度水平上对层次聚类方法的优点在于可以在不同粒度水平上对数据进行探测，而且容易实现相似度量或距离度量。数据进行探测，而且容易实现相似度量或距离度量。 l单纯的层次聚类算法终止条件含糊，而且执行合并单纯的层次聚类算法终止条件含糊，而且执行合并或分裂簇的操作后不可修正，这很可能导致聚类结或分裂簇的操作后不可修正，这很可能导致聚类结果质量很低。果质量很低。l通常考虑把层次聚类方法与其他方法（
71、如迭代重定通常考虑把层次聚类方法与其他方法（如迭代重定位方法）相结合来解决实际聚类问题。位方法）相结合来解决实际聚类问题。 喻摇抒辟姐求呕樱巳咀竿但度析日阎喝伏挡邵垮捞俊坍悬凹殷先翔曳汁族第6章聚类分析ppt课件第6章聚类分析ppt课件102lDBSCAN是一种基于密度的聚类算法是一种基于密度的聚类算法密度密度 = 给定半径给定半径(Eps)内点的数目内点的数目核心点核心点(core point ) 在半径在半径Eps的邻域内拥有的邻域内拥有多于特定数目多于特定数目(MinPts)的邻点的点，在基于密的邻点的点，在基于密度的簇内部的点度的簇内部的点边界点边界点(border point )在半
72、径在半径Eps的邻域内拥的邻域内拥有多于特定数目有多于特定数目(MinPts)的邻点的点，但是落的邻点的点，但是落在某个核心点的邻域内在某个核心点的邻域内噪声点噪声点(noise point )既非核心点也非边界点既非核心点也非边界点的任何点的任何点基于密度的聚类：基于密度的聚类：DBSCAN九脉或开翠戳堪榜赋荒顾暑肝况痛期珠啮套瞪敬蛇赶耗俄瓤沁滨洼天锰决第6章聚类分析ppt课件第6章聚类分析ppt课件103DBSCAN: 核心点，边界点和噪声点核心点，边界点和噪声点迪寇色递豺埃小蠕涪网欠奔哇法伊嘱焰你耻挺它轰省冲剥翘躺荐陋樱榨武第6章聚类分析ppt课件第6章聚类分析ppt课件104DBSCA
73、N 算法算法l算法算法1：将所有点标记为核心点、边界点或噪声点：将所有点标记为核心点、边界点或噪声点2：删除噪声点：删除噪声点3：为距离在：为距离在Eps之内的所有核心点之间赋予一条之内的所有核心点之间赋予一条边边4：每组连通的核心点形成一个簇：每组连通的核心点形成一个簇将每个边界点指派到一个与之关联的核心点的簇将每个边界点指派到一个与之关联的核心点的簇中中元法明蓉会管捉涉攀搀挝啡邻湖豌摧吩姓小躬魁筏丰窄炉孟遵丈澡鼠售炎第6章聚类分析ppt课件第6章聚类分析ppt课件105原始点原始点点的类型点的类型: 核心核心, 边界边界 和和噪声噪声Eps = 10, MinPts = 4DBSCAN 算
74、法算法瀑寥魔杂耕藐籍圭双咆杠始让搔久凌蒂伦剐绕郭弧腊撮碰吩彻均债携榴凤第6章聚类分析ppt课件第6章聚类分析ppt课件106原始点原始点得到的簇得到的簇 对噪声不敏感对噪声不敏感 可以处理不同形状和大小的簇可以处理不同形状和大小的簇当当DBSCAN工作良好时工作良好时佩赦宿帽沫净睫由贵潘遏鼠褂色颂帜嗡绵娜瞅溃丙渊腔号哉藉瘦茶庐芭氓第6章聚类分析ppt课件第6章聚类分析ppt课件107原始点集原始点集(MinPts=4, Eps=9.75). (MinPts=4, Eps=9.92) 变密度的簇变密度的簇 对高维数据计算量巨大对高维数据计算量巨大当当DBSCAN工作不佳时工作不佳时饵捏反灶线碑雁
75、直彰壹魄保项辱柱尧拧哮其触猫芜艘辛匣篙懦苗瘴沉钳绎第6章聚类分析ppt课件第6章聚类分析ppt课件108l基本方法：观察点到它的基本方法：观察点到它的k个最近邻的距离个最近邻的距离(称作称作k-距离距离)。对于属于某个簇的点，如果。对于属于某个簇的点，如果k不大于簇不大于簇的大小的话，则的大小的话，则k-距离将很接近距离将很接近l噪声点由于不在簇中，其噪声点由于不在簇中，其k-距离将相对较大距离将相对较大l对于某个对于某个k，计算所有点的，计算所有点的k-距离，以递增次序将距离，以递增次序将它们排序，然后绘制排序后的值，则预期会看到它们排序，然后绘制排序后的值，则预期会看到k-距离的急剧变化处
76、对应于合适的距离的急剧变化处对应于合适的Eps值值DBSCAN算法算法: 确定确定EPS和和 MinPts校蕊豫鹊红形赡焦昂轴偷吕磨拽如驴给疫渣羚漱挎俊凑讹娇繁簇坪简庇茄第6章聚类分析ppt课件第6章聚类分析ppt课件109DBSCAN算法算法: 确定确定EPS和和 MinPts苟采婚旱止恒苗拙九卑琉狙把旁迭陕锻岸博赦狠兆懈守囤怠描寂以黎镐昌第6章聚类分析ppt课件第6章聚类分析ppt课件110簇评估簇评估 l对于有监督的分类，我们可以有多种方式评价模型的对于有监督的分类，我们可以有多种方式评价模型的优劣优劣准确度准确度, 精度精度, 召回率召回率l对于聚类分析对于聚类分析, 相应的问题是如何
77、评价聚类结果是否相应的问题是如何评价聚类结果是否是是 “好好”的的l评估簇的目的评估簇的目的避免寻找噪声中的模式避免寻找噪声中的模式比较不同的聚类算法比较不同的聚类算法比较两个聚类的结果比较两个聚类的结果比较两个簇比较两个簇较衡泥渐讯版焰盅帐躁镰单鸦摧首汰莉矿腿蓖没铭睹晤柬召褥车降叶沏扛第6章聚类分析ppt课件第6章聚类分析ppt课件111在随机数据中发现的簇在随机数据中发现的簇100个个随机分随机分布的点布的点K-均值均值DBSCAN全链聚类全链聚类膨禁建窝渴籍刹犹偶金瑟呢媳庞蓬躁痈良标路比副涅钳角嘶菊壬炬繁哦肿第6章聚类分析ppt课件第6章聚类分析ppt课件1121.确定数据的聚类趋势确定
78、数据的聚类趋势( clustering tendency ), 即识别数据中是否实际存在非随机结构即识别数据中是否实际存在非随机结构. 2.比较聚类分析的结果与通过外部知识得到的类标比较聚类分析的结果与通过外部知识得到的类标(确定正确的簇个数确定正确的簇个数).3.评估聚类分析的结果在不引用附加信息的情况下评估聚类分析的结果在不引用附加信息的情况下是否能较好拟合数据是否能较好拟合数据.4.比较两个不同的聚类结果的优劣比较两个不同的聚类结果的优劣.5.确定确定“正确正确”的类的个数的类的个数l对于对于 2, 3, 4, 还可以进一步分为是要比较整个分类还可以进一步分为是要比较整个分类结果还是其中
79、的某个簇结果还是其中的某个簇簇评估簇评估叛耗巫犁些系恿仇悄翻窜揽伞占冉隧鳞绳蚀胯柞禄闻拧世前别脉带丸森笛第6章聚类分析ppt课件第6章聚类分析ppt课件113l用于评估簇各方面的评估度量或指标分成如下三类用于评估簇各方面的评估度量或指标分成如下三类监督的监督的(外部指标外部指标): 度量聚类算法发现的聚类结度量聚类算法发现的聚类结构与某种外部结构的匹配程度。例如熵，度量簇构与某种外部结构的匹配程度。例如熵，度量簇标号与外部提供的标号的匹配程度标号与外部提供的标号的匹配程度 非监督的非监督的(内部指标内部指标): 聚类结构的优良性度量，聚类结构的优良性度量，不考虑外部因素。如不考虑外部因素。如S
80、SE(平方误差和平方误差和)。簇的有。簇的有效性的非监督度量常常可以进一步分成两类：效性的非监督度量常常可以进一步分成两类：簇的凝聚性（紧凑性）：度量簇中对象如何密切相关簇的凝聚性（紧凑性）：度量簇中对象如何密切相关簇的分离性（孤立性）：度量确定一个簇如何不同于簇的分离性（孤立性）：度量确定一个簇如何不同于其它簇其它簇 度量簇的正确性度量簇的正确性例魏泰赌浊当冬乒馒晒桃馅跺渔萝打喧娱雀徽洞焚袒妄就汇皿象赴待干粤第6章聚类分析ppt课件第6章聚类分析ppt课件114l用于评估簇各方面的评估度量或指标分成如下三类用于评估簇各方面的评估度量或指标分成如下三类相对指标相对指标: 比较不同的聚类或簇。是
81、用于比较的比较不同的聚类或簇。是用于比较的监督或非监督评估度量，例如监督或非监督评估度量，例如SSE或熵或熵度量簇的正确性度量簇的正确性写州弯寐驴戌呈琼拣吧扒赔篙躁锰忽侗胚芒金您介至太医然堤饲斯莲秀育第6章聚类分析ppt课件第6章聚类分析ppt课件115通过相关性度量簇的有效性通过相关性度量簇的有效性l给定数据集的相似度矩阵和数据集聚类分析得到的类给定数据集的相似度矩阵和数据集聚类分析得到的类标号，则可以通过考察相似度矩阵和基于类标号的相标号，则可以通过考察相似度矩阵和基于类标号的相似度矩阵的理想版本之间的相关性，来评估聚类的优似度矩阵的理想版本之间的相关性，来评估聚类的优良性良性l一个理想的
82、簇：它的点与簇内所有点的相似度为一个理想的簇：它的点与簇内所有点的相似度为1，而与其它簇中的所有点的相似度为而与其它簇中的所有点的相似度为0l如果我们将相似度矩阵的行和列排列，使得属于相同如果我们将相似度矩阵的行和列排列，使得属于相同簇的对象在一起，则理想的相似度矩阵具有块对角结簇的对象在一起，则理想的相似度矩阵具有块对角结构：在相似度矩阵中代表簇内相似度的相的块内部相构：在相似度矩阵中代表簇内相似度的相的块内部相似度非似度非0，而其它地方为，而其它地方为0传足扁传驱冈戈雕夕烃保懊港语壳最窍沂手翌篓漓淖夷现尊厘供蹿湃泻筒第6章聚类分析ppt课件第6章聚类分析ppt课件116通过相关性度量簇的有
83、效性通过相关性度量簇的有效性l理想的相似度矩阵如下构造：创建一个矩阵，每个数理想的相似度矩阵如下构造：创建一个矩阵，每个数据点一行一列，矩阵的一个项为据点一行一列，矩阵的一个项为1，如果它所关联的，如果它所关联的一对点属于同一个簇，否则为一对点属于同一个簇，否则为0l理想和实际相似度矩阵之间高度相关表明属于同一个理想和实际相似度矩阵之间高度相关表明属于同一个簇的点相互之间很接近。簇的点相互之间很接近。l由于实际和理想相似度矩阵都是对称的，所以只需要由于实际和理想相似度矩阵都是对称的，所以只需要对矩阵对角线下方或上方的对矩阵对角线下方或上方的n(n-1)/2个项计算相关度个项计算相关度袄咒葬范敷
84、您却臆窝岔扩埋归渐彼俺径邪券漏鹃桃讣迈王始个析耀炉蒋锋第6章聚类分析ppt课件第6章聚类分析ppt课件117l对如下的两个数据集使用对如下的两个数据集使用K-均值算法得到的簇计算相均值算法得到的簇计算相似度矩阵似度矩阵 Corr = 0.9235Corr = 0.5810实际的和理想的相似度矩阵实际的和理想的相似度矩阵己看轨实骚逞奖贼尊傀饺诀丁剖稻芥伙簧杂驼学踩匣牛捍翱谗磅运卜勾簿第6章聚类分析ppt课件第6章聚类分析ppt课件118l按照簇标号调整相似度矩阵的行列次序，然后画出按照簇标号调整相似度矩阵的行列次序，然后画出它们。如果有明显分离的簇，则相似度矩阵应当粗它们。如果有明显分离的簇，则
85、相似度矩阵应当粗略的是块对角的略的是块对角的 通过相似度矩阵可视化的评价聚类通过相似度矩阵可视化的评价聚类搪剐油兹俄逗晋刁掠幅迹嗣涯氖孟价卒松菠店冈斗五弃急香碍扳蓑恃衷诌第6章聚类分析ppt课件第6章聚类分析ppt课件119l随机数据的簇的相似度矩阵随机数据的簇的相似度矩阵DBSCAN随机数据的簇的相似度矩阵随机数据的簇的相似度矩阵迷回恒猩狼惕沂泉兄稻腾闰巍纬沮燕窍偷曼腾玖稼婪讯褐伺擂蒸涨迅舟搽第6章聚类分析ppt课件第6章聚类分析ppt课件120l随机数据的簇的相似度矩阵随机数据的簇的相似度矩阵K-means随机数据的簇的相似度矩阵随机数据的簇的相似度矩阵扦睹膛神已帜件裂兑针允葫岂亥邓叔盒蹦
86、菜尿责孽讨弃志成嘶赢戏叙促倘第6章聚类分析ppt课件第6章聚类分析ppt课件121Complete Link随机数据的簇的相似度矩阵随机数据的簇的相似度矩阵业挫支落拽咬月过痪稠镜炳婶阮舌涂氮蔽麻尊衣邻理溉帮旗孽陛东阀萝晨第6章聚类分析ppt课件第6章聚类分析ppt课件122l在随机数据上，在随机数据上，DBSCAN、K均值和全链发现的簇的均值和全链发现的簇的重新排序的相似度矩阵中也存在弱对角模式重新排序的相似度矩阵中也存在弱对角模式弱脾顽夯卫造与惕饮恳演移盾啃黍迷汽嘱宿仪津汞乙忙堰愿接洱卑要块若第6章聚类分析ppt课件第6章聚类分析ppt课件123DBSCAN通过相似度矩阵可视化的评价聚类通过
87、相似度矩阵可视化的评价聚类皆疹肩难疾帧鲜琼什央殆卸财剂区炼滑获移锤鸡美栅义怕炕谢概弯西帘耘第6章聚类分析ppt课件第6章聚类分析ppt课件124l有更复杂图像的簇很难被分离有更复杂图像的簇很难被分离l内部指标内部指标: 不使用外部信息而独立簇结构的优良性不使用外部信息而独立簇结构的优良性SSElSSE可以较好地比较两个聚类结果或具体的两个簇可以较好地比较两个聚类结果或具体的两个簇内部测度内部测度: SSE武瓦跺蘸匙氓峦虎抛蟹暖窿贼串刹挟氮堑汲庆垃付邪栈凌狂踞屹绘喂入甚第6章聚类分析ppt课件第6章聚类分析ppt课件125l可以用来估计簇的个数。左图的数据集有可以用来估计簇的个数。左图的数据集有
88、10个自然个自然簇。当簇个数等于簇。当簇个数等于10时，时，SSE有一个明显的拐点有一个明显的拐点内部测度内部测度: SSE铱桥棱百颤凛岿竖凰辑箱兹卖枷私偷躯鼠栓盲缨狗卢镊卵阴薛之疆昭恳澡第6章聚类分析ppt课件第6章聚类分析ppt课件126内部测度内部测度: SSEl更复杂数据集的更复杂数据集的SSE曲线曲线SSE of clusters found using K-means卫月应汤阿腥沾锋诊舔销纤裹照辆汾陆绿关颗饱伊疑狮脾缄酬稠铺戴诞俞第6章聚类分析ppt课件第6章聚类分析ppt课件127聚类趋势聚类趋势l确定数据集中是否包含簇的一种显而易见的方法是使确定数据集中是否包含簇的一种显而易见
89、的方法是使着对它聚类。着对它聚类。l给定数据，几乎所有的聚类算法都会发现簇。给定数据，几乎所有的聚类算法都会发现簇。l为了处理这一问题，我们可以评估结果簇，至少有些为了处理这一问题，我们可以评估结果簇，至少有些簇具有好的质量，才能说数据集包含簇簇具有好的质量，才能说数据集包含簇l问题在于数据集中可能存在不同于我们是有的聚类算问题在于数据集中可能存在不同于我们是有的聚类算法所能发现的簇类型法所能发现的簇类型尝试使用多种方法，并评估结果簇的质量。如果尝试使用多种方法，并评估结果簇的质量。如果簇都很差，则可能表示数据中确实没有簇。簇都很差，则可能表示数据中确实没有簇。衣郭鸯泊袋符库跑悼省值福旋乙翔敝
90、郝恍辉福肉德讲抢啥枝迟哲党雕找懒第6章聚类分析ppt课件第6章聚类分析ppt课件128Hopkins统计量统计量l使用统计检验来检验空间随机性使用统计检验来检验空间随机性l产生产生p个随机地分别在数据空间上的点，并且也抽取个随机地分别在数据空间上的点，并且也抽取p个实际数据点。个实际数据点。l对于这两个点集，找出每个点到原数据集的最近邻距对于这两个点集，找出每个点到原数据集的最近邻距离。设离。设ui是人工产生的点的最近邻距离，而是人工产生的点的最近邻距离，而wi是样本是样本点到原数据集的最近邻距离。点到原数据集的最近邻距离。lHopkins统计量统计量H由下式定义由下式定义折蹋溃截摧篮柴僳坑哉
91、宵罗吝京缆厂浑厘谜召用炙高苹男缕神汽顶擎史舵第6章聚类分析ppt课件第6章聚类分析ppt课件129Hopkins统计量统计量l如果随机产生的点与样本点具有大致相同的最近距离，如果随机产生的点与样本点具有大致相同的最近距离，则则H将在将在0.5左右。左右。H接近接近0或或1表明数据是高度聚类的表明数据是高度聚类的和数据在数据空间是有规律分布的。和数据在数据空间是有规律分布的。l对于对于p=20和和100的不同实验，左图的的不同实验，左图的H平均值为平均值为0.95，标准差为，标准差为0.0006，右图的，右图的H平均值为平均值为0.59，标准差，标准差为为0.03瓶坠龙碉染噬阿麻畅泅俞燎顾粕植辙
92、返芋始阎据暇番窄穷芍使因幼炳库仪第6章聚类分析ppt课件第6章聚类分析ppt课件130聚类：选择聚类的个数聚类：选择聚类的个数l如何选择如何选择k-均值算法中的均值算法中的k？可能的策略？可能的策略对不同的可能个数进行试验，选择能使所有点离对不同的可能个数进行试验，选择能使所有点离开它们聚类中心的距离平方的总和达到最小的开它们聚类中心的距离平方的总和达到最小的k值值从一个给定的最小个数开始，一直试验到一个较从一个给定的最小个数开始，一直试验到一个较小的固定的最大值，用交叉验证法找出最好的个小的固定的最大值，用交叉验证法找出最好的个数数根据距离平方和标准来决定最佳聚类训练数据的根据距离平方和标准
93、来决定最佳聚类训练数据的方法，将总是选择和数据点一样多的聚类。为了方法，将总是选择和数据点一样多的聚类。为了抑制选择很多聚类的方案，必须采用诸如最短描抑制选择很多聚类的方案，必须采用诸如最短描述长度准则，或采用交叉验证述长度准则，或采用交叉验证谗趋曾浇陌豫宠婉噪员引吾矛状嵌膘怖踏挽给纸锡栖槛淖贰香胆饿离知袒第6章聚类分析ppt课件第6章聚类分析ppt课件131如何理解聚类如何理解聚类l 坦哥，你好啊，关于数据挖掘作业，我试着先坦哥，你好啊，关于数据挖掘作业，我试着先聚类再决策树分析，很多时候都会导致聚类得到的结聚类再决策树分析，很多时候都会导致聚类得到的结果跟决策树有冲突，例如：聚类
94、后得到影响某个属性果跟决策树有冲突，例如：聚类后得到影响某个属性的几个属性，但是在决策树分析中决定我感兴趣的的几个属性，但是在决策树分析中决定我感兴趣的l那个属性的决策树却不存在这几个属性子结点，这样那个属性的决策树却不存在这几个属性子结点，这样反而是聚类影响了决策树的准确性了。我想问几个问反而是聚类影响了决策树的准确性了。我想问几个问题：题：l1.我发现项目里的两个问题用决策树是可以完全解决，我发现项目里的两个问题用决策树是可以完全解决，为什么还要先聚类再用决策树分析呢？为什么还要先聚类再用决策树分析呢？芝缓肺降讨椒诣旷的灸旺斡富瞅险公堂虽弱鞍闭邢梗有帛施谷寓绘蝉劳廉第6章聚类分析ppt课件
95、第6章聚类分析ppt课件132如何理解聚类如何理解聚类l2.聚类分析跟决策树之间有何联系？对于具体问题，聚类分析跟决策树之间有何联系？对于具体问题，应该如何将它们联系起来分析。困惑中。应该如何将它们联系起来分析。困惑中。l3.聚类分析在于分类，但是我感觉聚类分析要应用到聚类分析在于分类，但是我感觉聚类分析要应用到实际问题中很困难，请指教。实际问题中很困难，请指教。l我跟很多同学请教过这些问题，发现他们也有类似疑我跟很多同学请教过这些问题，发现他们也有类似疑惑，请坦哥不吝赐教啊。惑，请坦哥不吝赐教啊。蕉盼尺环境奖倒徊孔羡援壹赁硫熏沃崔盯们狼胰庭虫遥馏念隧钩痉比股糠第6章聚类分析ppt课件第6章聚
96、类分析ppt课件133如何理解聚类如何理解聚类l数据挖掘的任务是寻找有意义的数据模式，但这种模数据挖掘的任务是寻找有意义的数据模式，但这种模式不是立刻就能得到式不是立刻就能得到有时候根本找不到有时候根本找不到(明显的明显的)模式模式有时候的问题不是缺乏模式，而是模式太多有时候的问题不是缺乏模式，而是模式太多l这些数据可能包含很多复杂的结构以至于最佳数据挖这些数据可能包含很多复杂的结构以至于最佳数据挖掘技术也不能找出有意义的模式掘技术也不能找出有意义的模式l当挖掘这些数据集以寻找特定问题的答案时，相互对当挖掘这些数据集以寻找特定问题的答案时，相互对立的解释往往使彼此相互抵消。立的解释往往使彼此相
97、互抵消。凌蚕椿它杜挝理搞掀咙腮咏利矢尽渡跋瓤四园酚始辫显崩娠浊上溢钞壬券第6章聚类分析ppt课件第6章聚类分析ppt课件134如何理解聚类如何理解聚类l象接受无线电信号一样，太多相互竞争的信号叠加到象接受无线电信号一样，太多相互竞争的信号叠加到一起就变为噪音。一起就变为噪音。l聚类提供了一种获悉复杂数据结构的方法，即将竞争聚类提供了一种获悉复杂数据结构的方法，即将竞争的信号的杂音分解成各自的成分。的信号的杂音分解成各自的成分。l当人们试图弄清复杂问题的意义时，往往趋向于将问当人们试图弄清复杂问题的意义时，往往趋向于将问题分解为更小的片断，每一个片断可以更简单地解释。题分解为更小的片断，每一个片
98、断可以更简单地解释。l在许多情况下，非常杂乱的数据集实际上可能由许多在许多情况下，非常杂乱的数据集实际上可能由许多表现较好的簇组成，聚类分析的目的就是如何发现它表现较好的簇组成，聚类分析的目的就是如何发现它们。们。噶脉阁扒煤惜嘿狠帆袱靠霖耀馒魂盆昭斥俭桨嫉惧手购檬盅钢萧则暴扩粹第6章聚类分析ppt课件第6章聚类分析ppt课件135如何理解聚类如何理解聚类l聚类分析是一种描述性的任务，用来发现数据集的分聚类分析是一种描述性的任务，用来发现数据集的分布特征。也可以作为对他发现的簇运行的数据挖掘算布特征。也可以作为对他发现的簇运行的数据挖掘算法的预处理步骤。法的预处理步骤。廷佃恼浇违桶肘占硬榴校怕筒
99、仙迅偷侈踪镣硒尺捅掩缘甄阜珊鱼玛袄霄卵第6章聚类分析ppt课件第6章聚类分析ppt课件136案例研究：聚类城镇案例研究：聚类城镇l波士顿环球报是服务于波士顿以及东马萨诸塞州波士顿环球报是服务于波士顿以及东马萨诸塞州和新罕布什尔南部周围区域的两家大日报之一，是波和新罕布什尔南部周围区域的两家大日报之一，是波士顿的主流报纸。士顿的主流报纸。l2003年的日发行量超过年的日发行量超过457 000份，在周日发行量超份，在周日发行量超过过705 000份。份。l波士顿环球报面临如下问题：波士度核心市场读波士顿环球报面临如下问题：波士度核心市场读者群在缩减，郊区报业市场面临来自地方报纸的有力者群在缩减，
100、郊区报业市场面临来自地方报纸的有力竞争，一些读者已流失。竞争，一些读者已流失。俊轨醋挫骸鸥迎斧纳旬怕佐兢砖猴愤闻粘迎埃甜嫁藤昼诀铭忆尧凹哩洽湃第6章聚类分析ppt课件第6章聚类分析ppt课件137案例研究：聚类城镇案例研究：聚类城镇l为了与郊区报纸更好地竞争，环球报加入了为不同地为了与郊区报纸更好地竞争，环球报加入了为不同地区定制的报纸版面，为按照地域划分的区定制的报纸版面，为按照地域划分的12个地区加个地区加入了特别编辑内容。每周有两天，读者都可以读到为入了特别编辑内容。每周有两天，读者都可以读到为本区精心整理的一些地方报道页。本区精心整理的一些地方报道页。l环球报使用的编辑区域利用的是环球
101、报已有的数据、环球报使用的编辑区域利用的是环球报已有的数据、常识性内容以及地图，但没有正式的统计分析。常识性内容以及地图，但没有正式的统计分析。洋眯发该理菱绷硅卜屠蕉笑镊汾锁菱霍酗赐屏态纽槐诌侧傲淮迟踩赘掩饰第6章聚类分析ppt课件第6章聚类分析ppt课件138案例研究：聚类城镇案例研究：聚类城镇l编辑区域组成方面有一些限制条件编辑区域组成方面有一些限制条件地域必须是地理上连续的，以便运输地域必须是地理上连续的，以便运输地域必须适度紧凑，且包含足够人口已证明特殊地域必须适度紧凑，且包含足够人口已证明特殊化编辑的内容是恰当的化编辑的内容是恰当的编辑区域必须接近于过去做广告的地理区域。编辑区域必须
102、接近于过去做广告的地理区域。l下面采用数据挖掘技术来把相似的城镇聚集在一起形下面采用数据挖掘技术来把相似的城镇聚集在一起形成编辑区。成编辑区。惧蜡呐韶伺啥绥瘟盅泞元扩卸吴眉末隶嗽雾多比术岂钥奢季厕坪季郊腮磁第6章聚类分析ppt课件第6章聚类分析ppt课件1391 创造城镇特征创造城镇特征l在做聚类分析之前，首要的问题是找到描述城镇的特在做聚类分析之前，首要的问题是找到描述城镇的特征，需要包括可以用于表征城镇特点，以及可用于比征，需要包括可以用于表征城镇特点，以及可用于比较该城镇及其邻近城镇的每个特征的一个列较该城镇及其邻近城镇的每个特征的一个列l城镇特征标识可以有几个来源，大部分数据可以从城镇
103、特征标识可以有几个来源，大部分数据可以从1990年和年和2001年城镇级的年城镇级的美国人口普查数据美国人口普查数据(census data)得到，包括年龄、种族、宗教信仰、职业、收得到，包括年龄、种族、宗教信仰、职业、收入、住宅价值、平均通勤时间以及其他令人感兴趣的入、住宅价值、平均通勤时间以及其他令人感兴趣的变量。变量。以陷驳骗倔滋裂柠妓诧撞标们顾埋博己阿哺喝脖詹帅央夏职踊类宁掇撰市第6章聚类分析ppt课件第6章聚类分析ppt课件1401 创造城镇特征创造城镇特征l此外还有外围数据提供商提供的关于订户家庭层次的此外还有外围数据提供商提供的关于订户家庭层次的数据，还有每个城镇的发行量数据，以
104、订阅者层次的数据，还有每个城镇的发行量数据，以订阅者层次的信息，如优惠计划、投诉电话和订户类型信息，如优惠计划、投诉电话和订户类型(日常、周日常、周日或者两者都是日或者两者都是)等等l数据的处理：本例中通过四个基本步骤来创建城镇特数据的处理：本例中通过四个基本步骤来创建城镇特征征聚集聚集归一化归一化计算趋势计算趋势创建衍生变量创建衍生变量初球瞪腕抄莹识圭绳冻听撮雌歇溺繁庄毡牧驶夏焦恩邻谓徐结丢雾午溶玖第6章聚类分析ppt课件第6章聚类分析ppt课件1411 创造城镇特征创造城镇特征l聚集：将较细层次的数据汇总到城镇层次，例如聚集聚集：将较细层次的数据汇总到城镇层次，例如聚集订户的数据以得出每个
105、城镇中订户的总数和中值订户订户的数据以得出每个城镇中订户的总数和中值订户家庭收入家庭收入l归一化：将计数值归一化：将计数值(例如收入、住宅价值和孩子数目例如收入、住宅价值和孩子数目)转变成百分比。这实际上是把人口差别很大的不同城转变成百分比。这实际上是把人口差别很大的不同城镇的数据归一化，为了可以有效地进行对比。例如镇的数据归一化，为了可以有效地进行对比。例如2001年有年有4年大学学历的年大学学历的27573个人住在个人住在Borrkline，这只占到教育水平高的城镇的这只占到教育水平高的城镇的47.5%。在波士顿，具。在波士顿，具有类似学位的人非常多，但只占到当地总人口的有类似学位的人非常
106、多，但只占到当地总人口的19.4%.恤钒孟缨奋坞猴慈巧施郁福伊猫迟龙纳倦舆冀悯止内泪渔舱轮萨睡划阻渍第6章聚类分析ppt课件第6章聚类分析ppt课件1421 创造城镇特征创造城镇特征l计算趋势：人口普查数据中每个变量都有相隔计算趋势：人口普查数据中每个变量都有相隔11年的年的两个值可以使用。历史数据的一个令人感兴趣的地方两个值可以使用。历史数据的一个令人感兴趣的地方是可以观察到其中的趋势。如人口的变化：包括学龄是可以观察到其中的趋势。如人口的变化：包括学龄人口的变化、不同族裔人口的变化，或拥有自有住房人口的变化、不同族裔人口的变化，或拥有自有住房人口比例的变化。人口比例的变化。l创建衍生变量：
107、从已存在的变量中衍生另外一些变量。创建衍生变量：从已存在的变量中衍生另外一些变量。例如从邮政编码数据数据中产生各个城镇到中心城市例如从邮政编码数据数据中产生各个城镇到中心城市（波士顿）的距离（波士顿）的距离讽活戮坯德叁赠母枕仿朋铭惺村警坚阅层截钢府阔舟版丧覆熔簿伎埃胳讫第6章聚类分析ppt课件第6章聚类分析ppt课件143创建簇创建簇l利用人口统计学和地理学数据描述该城镇的特征标识利用人口统计学和地理学数据描述该城镇的特征标识l使用这些特征得到的聚类结果不能直接用于创建报纸使用这些特征得到的聚类结果不能直接用于创建报纸的编辑区，因为还有地理方面的约束条件，即编辑区的编辑区，因为还有地理方面的约
108、束条件，即编辑区域必须由相邻的城镇构成。域必须由相邻的城镇构成。l有相似人口统计学数据的城镇未必在地理上相邻，这有相似人口统计学数据的城镇未必在地理上相邻，这个问题可以通过使用加权的方式来增加形成簇过程中个问题可以通过使用加权的方式来增加形成簇过程中地理变量的重要性。地理变量的重要性。l但在本案例中最终放弃了地域簇的设计，因为目标是但在本案例中最终放弃了地域簇的设计，因为目标是寻找至少部分基于人口统计学的相似性，更侧重于人寻找至少部分基于人口统计学的相似性，更侧重于人口统计学方面。口统计学方面。宾骋禹粤擒蹬履壮烂晨斋辰肩俊浅厩鞘播畔翌大屈锣淫届瑞潭兵验腑丽团第6章聚类分析ppt课件第6章聚类分
109、析ppt课件144lMassachusetts东部及东部及New Hampshire南部各南部各城镇人口统计学聚类情况城镇人口统计学聚类情况隐站廓违懈术泛角涛袖萌职砾颂甘朔痹疲豹斤谐丁减崎驳露缠际遍蕴澜涯第6章聚类分析ppt课件第6章聚类分析ppt课件145确定簇的正确数量确定簇的正确数量l处于商业方面的原因，可能需要处于商业方面的原因，可能需要12个编辑区域，但个编辑区域，但不能保证找到这么多不能保证找到这么多好的簇。好的簇。这直接提出如何为数据这直接提出如何为数据集确定合适数目的簇的问题。集确定合适数目的簇的问题。l这里使用类似二分这里使用类似二分K均值的算法。首先以较低的均值的算法。首先
110、以较低的K值值确定簇数目，使用普通的确定簇数目，使用普通的K均值算法构建均值算法构建K聚类，利聚类，利用适应度度量用适应度度量(如如SSE)确定最差的簇，然后把这个簇确定最差的簇，然后把这个簇分裂为分裂为2个簇，反复重复这个过程，一直到簇数达到个簇，反复重复这个过程，一直到簇数达到上界。上界。l每次迭代后，记录该簇的总体适应度。每次迭代后，记录该簇的总体适应度。绘息鉴树暮抚莫演邮孰茄堂凯歌诲来创体语汕滇缴褒厘罩过胡需比刹条申第6章聚类分析ppt课件第6章聚类分析ppt课件146l对于实际商业问题，簇的最重要的适应度度量是难以对于实际商业问题，簇的最重要的适应度度量是难以量化的度量量化的度量簇对
111、某个应用的有效性。簇对某个应用的有效性。Cluster 2Cluster 1BCluster 1AB按照算法的建议，聚类算法的下一按照算法的建议，聚类算法的下一次迭代将把簇次迭代将把簇2进行分裂。形成的簇进行分裂。形成的簇有明确的差异，但对于环球报感兴有明确的差异，但对于环球报感兴趣的变量而言，所形成的新簇都没趣的变量而言，所形成的新簇都没有不同的表现，如家庭递送穿透度有不同的表现，如家庭递送穿透度或订户资历等。或订户资历等。迫胀狞律演丢咖捶征倦熙茄久杉葡铃玛刨充气者斯司吮莎善乌倪星串桨恿第6章聚类分析ppt课件第6章聚类分析ppt课件147城镇的最终的四个分组城镇的最终的四个分组l簇簇2包含
112、了包含了50个城镇中的个城镇中的31300个家庭，其中个家庭，其中137000个家庭订阅日报或周末版环球报。个家庭订阅日报或周末版环球报。 它是它是“最佳簇最佳簇”“Best” based on delivery penetration“2nd Best” based on delivery penetrationCluster 2Cluster 1BCluster 1AB魄臆叹沮洱约蝴倚决傀滞东宫赘夫老娟留冰茬羊博阿法云逞燥括圭孔极兰第6章聚类分析ppt课件第6章聚类分析ppt课件148l簇簇2与其他簇和人口总体区分开的变量是住宅价值和与其他簇和人口总体区分开的变量是住宅价值和教育程度。这个
113、簇有最高的住宅价值比例、最高的有教育程度。这个簇有最高的住宅价值比例、最高的有4年大学学历的人数比例、最高受教育的品均年数和年大学学历的人数比例、最高受教育的品均年数和最低的蓝领工作人员比例最低的蓝领工作人员比例干哨判兜救要咐靴颂善眩纂候线热情侠备帅僧浊崩稳廖匹麦耐某蚂距臀腮第6章聚类分析ppt课件第6章聚类分析ppt课件149l从家庭递送穿透度来看，次好的簇是簇从家庭递送穿透度来看，次好的簇是簇1AA。住宅价。住宅价值和家庭收入与总人口的均值非常接近。值和家庭收入与总人口的均值非常接近。l簇簇1B的特征：主要以有最低家庭收入的特征：主要以有最低家庭收入 历时最久且临近波士顿的订户历时最久且临
114、近波士顿的订户“Best” based on delivery penetration“2nd Best” based on delivery penetrationCluster 2Cluster 1BCluster 1AB雪剪回抠研狼宗筹良凑珍咕佯象铁佬蝎倪丛伏黍雹博胳萄股骏转选笔闲芋第6章聚类分析ppt课件第6章聚类分析ppt课件150l簇簇1AB是唯一主要以地域为特征形成的簇，都是远离是唯一主要以地域为特征形成的簇，都是远离波士顿的城镇，其家庭递送穿透度很低。波士顿的城镇，其家庭递送穿透度很低。其住宅价值最低，但家庭收入为平均数。其住宅价值最低，但家庭收入为平均数。l簇簇1AB中的人选
115、择在离城市较远的中的人选择在离城市较远的 地方居住，因为他们希望有自己的地方居住，因为他们希望有自己的 住宅住宅(郊区边缘房间较便宜郊区边缘房间较便宜)咒承户辜襟览沈却执酱帜呀钻泪趋水剥妓绪尖惭滤吼脉冈掀话孔与奶收饲第6章聚类分析ppt课件第6章聚类分析ppt课件151利用簇调整区域边界利用簇调整区域边界l聚类项目的目标是确定已存聚类项目的目标是确定已存在的编辑区域是否最优。每在的编辑区域是否最优。每个编辑区域都是处于上述四个编辑区域都是处于上述四个簇之一的城镇集合构成个簇之一的城镇集合构成l下一个步骤是通过手工方法下一个步骤是通过手工方法将某些城镇交换到邻近的区将某些城镇交换到邻近的区域，以
116、增加每个区域的纯度。域，以增加每个区域的纯度。城镇城镇编辑区域编辑区域所属簇所属簇BrooklineCity2BostonCity1BCambridgeCity1BSomervilleCity1BNeedhamWest 12NewtonWest 12WellesleyWest 12WalthamWest 11BWestonWest 12WatertownWest 11B负睫漂郡虞妒阅悲肯氓岛绎儒皮礼蔽笑湖撵渐舵妮苞讼温嘲侈圾牢憋橇嗓第6章聚类分析ppt课件第6章聚类分析ppt课件152l除除Brookline外，所以处于外，所以处于city区域的城镇都属于簇区域的城镇都属于簇1B中中将将Bro
117、okline交换到邻近交换到邻近的的West1区域区域将将Waltham和和Watertown交换到邻近的交换到邻近的City区域区域l新的新的West1区域是整个簇区域是整个簇2l新的新的City区域是整个簇区域是整个簇1B城镇城镇编辑区域编辑区域所属簇所属簇BrooklineCity2BostonCity1BCambridgeCity1BSomervilleCity1BNeedhamWest 12NewtonWest 12WellesleyWest 12WalthamWest 11BWestonWest 12WatertownWest 11B有了相似城镇组成的编辑区域，就可以容易的集中对本
118、地内容有了相似城镇组成的编辑区域，就可以容易的集中对本地内容提供有针对性的评论，增加发行量和广告销售。提供有针对性的评论，增加发行量和广告销售。冗娠单芍渡悠蔚艳波互悟腊峡牵涡骂次绷硷俱萄稗误冻誓闲沧虹禾察纶休第6章聚类分析ppt课件第6章聚类分析ppt课件153Microsoft 聚类分析算法聚类分析算法lMicrosoft 聚类分析算法提供两种创建分类并为分类聚类分析算法提供两种创建分类并为分类分配数据点的方法。分配数据点的方法。第一种方法是第一种方法是 K-means 算法，属于硬聚类方法。算法，属于硬聚类方法。这意味着一个数据点只能属于一个分类这意味着一个数据点只能属于一个分类第二种方法
119、是第二种方法是“期望值最大化期望值最大化”(EM) 方法，这是方法，这是“软聚类分析软聚类分析”方法。这意味着一个数据点总是方法。这意味着一个数据点总是属于多个分类，并会为每个数据点和分类的组合属于多个分类，并会为每个数据点和分类的组合计算一个概率。计算一个概率。l可以通过设置可以通过设置 CLUSTERING_METHOD 参数来选择参数来选择要使用的算法。聚类分析的默认方法是可缩放的要使用的算法。聚类分析的默认方法是可缩放的 EM。澈丸躁桥蛤满蚤宪终恋咀毗云维县论解注被涉颠冉囱哼汹搭妓沸顽倚巴芹第6章聚类分析ppt课件第6章聚类分析ppt课件154EM 聚类分析聚类分析l在在 EM 聚类分
120、析中，此算法反复优化初始分类模型以聚类分析中，此算法反复优化初始分类模型以适合数据，并确定数据点存在于某个分类中的概率。适合数据，并确定数据点存在于某个分类中的概率。当概率模型适合于数据时，此算法终止这一过程。用当概率模型适合于数据时，此算法终止这一过程。用于确定是否适合的函数是数据适合模型的对数可能性。于确定是否适合的函数是数据适合模型的对数可能性。lEM 聚类分析方法的结果是概率性的。这意味着每个聚类分析方法的结果是概率性的。这意味着每个数据点都属于所有分类，但数据点向分类的每次分配数据点都属于所有分类，但数据点向分类的每次分配都有一个不同的概率。都有一个不同的概率。鲤却详揉蔗斥椎优氮疾萝
121、剪奈换连娃昌怨驭婴笆盂疚南姨决肚甸配私每轨第6章聚类分析ppt课件第6章聚类分析ppt课件155lMicrosoft 实现提供两个选项：可缩放实现提供两个选项：可缩放 EM 和不可缩和不可缩放放 EM。l默认情况下，在可缩放默认情况下，在可缩放 EM 中，前中，前 50,000 个记录用个记录用于为初始扫描设种子。如果成功，则模型将仅仅使用于为初始扫描设种子。如果成功，则模型将仅仅使用这些数据。如果使用这些数据。如果使用 50,000 个记录时模型不适合，个记录时模型不适合，则会继续读取则会继续读取 50,000 个记录。个记录。l在不可缩放在不可缩放 EM 中，总是读取整个数据集，而不考虑中
122、，总是读取整个数据集，而不考虑数据集的大小。数据集的大小。此方法可能会创建更准确的分类，但内存需求非此方法可能会创建更准确的分类，但内存需求非常高。常高。稚叁杰猫腹罚袜膜蛛咙雾眠循坛矩培珐戍乙兜谆琐脯彬皋姐踊帛怔洞约誊第6章聚类分析ppt课件第6章聚类分析ppt课件156l因为可缩放因为可缩放 EM 作用于本地缓冲区，所以循环访问数作用于本地缓冲区，所以循环访问数据要快得多，并且此算法对据要快得多，并且此算法对 CPU 内存缓存的利用率内存缓存的利用率比不可缩放比不可缩放 EM 要高得多。要高得多。l此外，可缩放此外，可缩放 EM 比不可缩放比不可缩放 EM 快三倍，即使所快三倍，即使所有数据
123、都可容纳于主内存中也是如此。有数据都可容纳于主内存中也是如此。l在大多数情况下，性能改进不会导致完成的模型的质在大多数情况下，性能改进不会导致完成的模型的质量下降。量下降。托演白渡纱咨醋龄仇走癸削毖昨窥会千蜂慌役闽册毁甭纳川弧眶枉刃歉侧第6章聚类分析ppt课件第6章聚类分析ppt课件157k-means 聚类分析聚类分析lk-means 通过尽量缩小一个分类中的项之间的差异，通过尽量缩小一个分类中的项之间的差异，同时尽量拉大分类之间的距离，来分配分类成员身份。同时尽量拉大分类之间的距离，来分配分类成员身份。lk-means 中的中的 means 指的是分类的指的是分类的“中点中点”，它，它是任
124、意选定的一个数据点，之后反复优化，直到真正是任意选定的一个数据点，之后反复优化，直到真正代表该分类中的所有数据点的平均值。代表该分类中的所有数据点的平均值。lk 指的是用于为聚类分析过程设种子的任意数目的指的是用于为聚类分析过程设种子的任意数目的点。点。k-means 算法计算一个分类中的数据记录之间算法计算一个分类中的数据记录之间的欧几里得距离的平方，以及表示分类平均值的矢量，的欧几里得距离的平方，以及表示分类平均值的矢量，并在和达到最小值时在最后一组并在和达到最小值时在最后一组 k 分类上收敛。分类上收敛。禁妹歼绦瘦稚邓陷堵弛建犁屁彩瑞镑檬秋歧价卵怀肚铺腻张准几棋蟹裙宇第6章聚类分析ppt
125、课件第6章聚类分析ppt课件158k-means 聚类分析聚类分析lk-means 算法仅仅将每个数据点分配给一个分类，算法仅仅将每个数据点分配给一个分类，并且不允许成员身份存在不确定性。分类中的成员身并且不允许成员身份存在不确定性。分类中的成员身份表示为与中点的距离。份表示为与中点的距离。l通常，通常，k-means 算法用于创建连续属性的分类，在算法用于创建连续属性的分类，在这种情况下，计算与平均值的距离非常简单。但是，这种情况下，计算与平均值的距离非常简单。但是，Microsoft 实现通过使用概率针对分类离散属性对实现通过使用概率针对分类离散属性对 k-means 方法进行改编。方法进
126、行改编。l注意：注意：Microsoft 聚类分析算法不公开用于计算聚类分析算法不公开用于计算 k-means 的距离函数，并且在完成的模型中不能测量的距离函数，并且在完成的模型中不能测量距离。但是，可以使用预测函数返回与距离对应的值，距离。但是，可以使用预测函数返回与距离对应的值，在这种情况下，距离计算为某个数据点属于此分类的在这种情况下，距离计算为某个数据点属于此分类的概率。请参阅概率。请参阅 ClusterProbability。龋这寅睬碧淀写钱抛阵攒毡道猴炸俺伤片埋日视揭缎侣掂蹋健札宠且朔蔓第6章聚类分析ppt课件第6章聚类分析ppt课件159自定义自定义 Microsoft 聚类分析
127、算法聚类分析算法 lMicrosoft 聚类分析算法支持几个参数，这些参数会聚类分析算法支持几个参数，这些参数会影响所生成的挖掘模型的行为、性能和准确性。影响所生成的挖掘模型的行为、性能和准确性。l设置算法参数设置算法参数这些参数影响生成的挖掘模型的性能和准确性。这些参数影响生成的挖掘模型的性能和准确性。lCLUSTERING_METHOD：指定算法要使用的聚类：指定算法要使用的聚类分析方法，默认值为分析方法，默认值为 1（可缩放（可缩放 EM）。）。 ID 方法 1可缩放 EM2不可缩放 EM3可缩放 k-means4不可缩放 k-means。跃谣梨零琢咐惟墒密砾训孔思琢狭狈遗宵妄珠着厨膝弟
128、槐苞血砚约精艇暂第6章聚类分析ppt课件第6章聚类分析ppt课件160lCLUSTER_COUNT 指定将由算法生成的大致分类数。如果无法基于指定将由算法生成的大致分类数。如果无法基于相应的数据生成该大致数目的分类，则算法将生相应的数据生成该大致数目的分类，则算法将生成尽可能多的分类。如果将成尽可能多的分类。如果将 CLUSTER_COUNT 设置为设置为 0，则算法将使用试探性方法最准确地确定，则算法将使用试探性方法最准确地确定要生成的分类数。要生成的分类数。默认值为默认值为 10。六妨赏肃琢姑磺佰喻坦君役咆扁户尤材车吉剔祝丙险提旺设糯翘持啸笼丽第6章聚类分析ppt课件第6章聚类分析ppt课
129、件161lCLUSTER_SEED 指定在为建模初始阶段随机生成分类时所要使用指定在为建模初始阶段随机生成分类时所要使用的种子数字。的种子数字。通过更改此数字，可以更改生成初始分通过更改此数字，可以更改生成初始分的的方法，然后使用不同的种子比较已生成的模型。方法，然后使用不同的种子比较已生成的模型。如果种子已更改，但所发现的分类并没有太大的如果种子已更改，但所发现的分类并没有太大的更改，则模型可被视为相对稳定。更改，则模型可被视为相对稳定。默认值为默认值为 0。渺荐届缄甫毫挣腰永挚莲羽羡电贿涪拳谬弘均沈仆辗谋宛东报媚运淬收糜第6章聚类分析ppt课件第6章聚类分析ppt课件162lMINIMUM
130、_SUPPORT 指定生成某个分类至少需要的事例数。如果分类指定生成某个分类至少需要的事例数。如果分类中的事例数小于此数目，则此分类将被视为空，中的事例数小于此数目，则此分类将被视为空，并将被丢弃。并将被丢弃。如果将这个数目设置得过高，则可能遗漏有效分如果将这个数目设置得过高，则可能遗漏有效分类。类。l注意：如果使用注意：如果使用 EM，即默认聚类分析方法，则一些，即默认聚类分析方法，则一些分类可能具有低于指定值的支持值。这是因为会计算分类可能具有低于指定值的支持值。这是因为会计算每个事例在所有可能分类中的成员身份，对于某些分每个事例在所有可能分类中的成员身份，对于某些分类，可能仅存在最小支持
131、。类，可能仅存在最小支持。压晚榴泰帧酥迫栽贷笆莫籽湿搽宿花浚舌你误揣耽况严胖肉钮辩翰犊哮谰第6章聚类分析ppt课件第6章聚类分析ppt课件163lMODELLING_CARDINALITY 指定在聚类分析过程中构建的示例模型数。指定在聚类分析过程中构建的示例模型数。减少候选模型数会提高性能，但存在遗漏一些好减少候选模型数会提高性能，但存在遗漏一些好的候选模型的风险。的候选模型的风险。默认值为默认值为 10。唾芬隙逼府忌贮舵鹤公沧爬最览湃吵暑浑探司糯闷唾辖比泊思寒柴坯锈译第6章聚类分析ppt课件第6章聚类分析ppt课件164lSTOPPING_TOLERANCE 指定一个值，它可确定何时达到收敛
132、而且算法完指定一个值，它可确定何时达到收敛而且算法完成建模。当分类概率中的整体变化小于成建模。当分类概率中的整体变化小于 STOPPING_TOLERANCE 参数与模型大小之比参数与模型大小之比时，即达到收敛。时，即达到收敛。默认值为默认值为 10。铂萎嗣包峪起抄扰唱棘倔拿飘恬侮灭锯劫艳冗卡界腿缠涵唁垮啦绕窃砂藩第6章聚类分析ppt课件第6章聚类分析ppt课件165lSAMPLE_SIZE 如果如果 CLUSTERING_METHOD 参数设置为其中参数设置为其中一个可缩放聚类分析方法，请指定算法在每个传一个可缩放聚类分析方法，请指定算法在每个传递中使用的事例数。如果将递中使用的事例数。如果
133、将 SAMPLE_SIZE 参数参数设置为设置为 0，则会导致在单个传递中对整个数据集进，则会导致在单个传递中对整个数据集进行聚类分析操作。在单个传递中加载整个数据集行聚类分析操作。在单个传递中加载整个数据集会导致内存和性能问题。会导致内存和性能问题。默认值为默认值为 50000。铃闷晓粕密图砰僧酬擒臻论化兹波岸臃肌赞倒瞧硅撰娠紊埋普哆后崔矮厩第6章聚类分析ppt课件第6章聚类分析ppt课件166lMAXIMUM_INPUT_ATTRIBUTES 指定算法在调用功能选择之前可以处理的最大输指定算法在调用功能选择之前可以处理的最大输入属性数。将该值设置为入属性数。将该值设置为 0 表示不限制属性
134、的最表示不限制属性的最大数目。大数目。增大属性的数目会大大降低性能。增大属性的数目会大大降低性能。默认值为默认值为 255。妊澜螺干柿苍赔砂陌塑劝示齿庭盼和鳖段肆粳福付馁醋国碉龄鲜要割员影第6章聚类分析ppt课件第6章聚类分析ppt课件167lMAXIMUM_STATES 指定算法支持的最大属性状态数。如果属性的状指定算法支持的最大属性状态数。如果属性的状态数超过此最大值，则算法将使用最常见状态，态数超过此最大值，则算法将使用最常见状态，而忽略其余状态。而忽略其余状态。增大状态的数目会大大降低性能。增大状态的数目会大大降低性能。默认值为默认值为 100。匙你暖炉姓霖稚型寞胸饺本便韶从袱丹跌辞暴摸彬徊蒙肩艰窘艳挪曙尿惫第6章聚类分析ppt课件第6章聚类分析ppt课件168
