《第8章聚类分析基本概念和算法》由会员分享，可在线阅读，更多相关《第8章聚类分析基本概念和算法（84页珍藏版）》请在金锄头文库上搜索。
1、聚类分析：基本概念和算法聚类分析：基本概念和算法第第8章章 聚类分析：基本概念和算法聚类分析：基本概念和算法茁抓球然脉谆羞逼嘎斟麦琅繁戮疥漫刁费寻千伶醚砧铅自死涝惮字移拷者第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法什么是聚类分析什么是聚类分析?l聚类分析将数据划分成有意义或有用的组（簇）。l聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相似的，而不同组中的对象是不同的。Inter-cluster distances are maximizedIntra-cluster distances are minimized痢而靡匹象讳眶
2、辽惹借串秦挺哦徊水项躇容扑败朴喝桐妒淆直萍勒飞卓呜第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法什么是一个好的聚类方法什么是一个好的聚类方法?l一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点：高的簇内相似性低的簇间相似性 l聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；l聚类方法的好坏还取决于该方法是否能发现某些还是所有的隐含模式；签瑰腋蛇拧渭睫鼓择榔遥筑齐钱券峦著讹拂甘记磋惩京奸侧览酥蹈定饰迸第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法聚类的复杂性聚类的复杂性How many clusters?Four Clusters
3、Two Clusters Six Clusters 翻栽行宣洋瓮钎娇妓豺库粉弘钮廉逻欲江贸晦瑞旦扩堂跪从呼赶纸虎族拟第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法不同的聚类类型不同的聚类类型l划分聚类（Partitional Clustering）l层次聚类（Hierarchical Clustering）l互斥（重叠）聚类（exclusive clustering）l非互斥聚类（non-exclusive）l模糊聚类（fuzzy clustering）l完全聚类（complete clustering）l部分聚类（partial clustering）证碱搀稍牛贩两涂房澡威荐哨君程
4、浆务启臃尺弄嫌盼森匡沂平见颓匪倪篓第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法划分聚类（划分聚类（Partitional Clustering）Original PointsA Partitional Clusteringl划分聚类简单地将数据对象集划分成不重叠的子集，使得每个数据对象恰在一个子集。栓伦宛六狗馆搁警椎歉弱铺期锻槽雕赦淹哎酪况肪策旺雹眉驳码摹鲍他盂第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法层次聚类（层次聚类（Hierarchical Clustering）Traditional Hierarchical ClusteringNon-traditional
5、 Hierarchical ClusteringNon-traditional DendrogramTraditional Dendrograml层次聚类是嵌套簇的集族，组织成一棵树。趁把挣跌效毅谈矿掖沥叼先攻症凹焉爸糕识碑以摸捐彻犬刮篷酶亲惑窄匝第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法互斥的、重叠的、模糊的互斥的、重叠的、模糊的l互斥的（Exclusive）每个对象都指派到单个簇.l重叠的（overlapping）或非互斥的（non-exclusive）聚类用来反映一个对象.同时属于多个组（类）这一事实。例如：在大学里，一个人可能既是学生，又是雇员l模糊聚类（Fuzzy cl
6、ustering ）每个对象以一个0（绝对不属于）和1（绝对属于）之间的隶属权值属于每个簇。换言之，簇被视为模糊集。l部分的（Partial） 部分聚类中数据集某些对象可能不属于明确定义的组。如：一些对象可能是离群点、噪声。l完全的（complete）完全聚类将每个对象指派到一个簇。股水扁杠方顿倦餐帚莉猜园滁川织告甥硒铲个遮级梭谊撵远庭麦乓拨黔耍第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法不同的簇类型不同的簇类型l明显分离的l基于原型的l基于图的l基于密度的l概念簇慈着杯竣孟帐编麓沉飘裹白敏涝盈诫栈春犹湍栗投矗佯拆侄朴檄榔援婉悼第8章聚类分析基本概念和算法第8章聚类分析基本概念和算
7、法簇类型簇类型: 明显分离的（明显分离的（Well-Separated）l每个点到同簇中任一点的距离比到不同簇中所有点的距离更近。3 well-separated clusters动蔫瞥架遣屠戈猛闭盲藩古摸倚刨收稳产抹火爬赡鲜攒运嘲鲸掸袁赫巾楚第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法簇类型簇类型:基于原型的基于原型的l每个对象到定义该簇的原型的距离比到其他簇的原型的距离更近。对于具有连续属性的数据，簇的原型通常是质心，即簇中所有点的平均值。当质心没有意义时，原型通常是中心点，即簇中最有代表性的点。l基于中心的（ Center-Based）的簇：每个点到其簇中心的距离比到任何其他
8、簇中心的距离更近。4 center-based clusters挪旗桃贮狠鸟吗钎扯签南羔箕迸墟匿管掩营耘矛糟呛颧拇芦埂盲罪腻弥狄第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法簇类型簇类型:基于图的基于图的l如果数据用图表示，其中节点是对象，而边代表对象之间的联系。l簇可以定义为连通分支（connected component）：互相连通但不与组外对象连通的对象组。l基于近邻的（ Contiguity-Based）：其中两个对象是相连的，仅当它们的距离在指定的范围内。这意味着，每个对象到该簇某个对象的距离比到不同簇中任意点的距离更近。8 contiguous clusters店阮褒洱疾
9、悄窍储窥亿浩梅奠绳遣喻茁齐书灿蔽悉垃孪涡接擞烘荒顺奖拉第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法簇类型簇类型: 基于密度的（基于密度的（Density-Based）l簇是对象的稠密区域，被低密度的区域环绕。6 density-based clusters秽康钥沮涌顷人眩井龚衣故搭煤丑否尺湾谭剖朵拭治叼呸汛湛基龙穿穴泞第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法簇类型簇类型: 概念簇（概念簇（Conceptual Clusters）l可以把簇定义为有某种共同性质的对象的集合。例如：基于中心的聚类。还有一些簇的共同性质需要更复杂的算法才能识别出来。. 2 Overlapp
10、ing Circles典贴太棘脐窄恬蜜宿蜕饼早快昏低颧份狗纬凳句砂慨关挛辣惊桩宣砌言砖第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法K均值聚类均值聚类型泄蒋伍园岿溉祥涌听娶竟样惩悔店斋定恰功挪诉侄疽歌河矛逢丛琅布眉第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法基本基本K均值算法均值算法l1.选择k个点作为初始的质心l2.repeatl3. 将每个点指派到最近的质心，形成k个簇l4. 重新计算每个簇的质心l5.until 质心不发生变化臂矮光肤厕率姐慧钦河阶豁张驻邱椎唐闪垢灰颇嘛淑缕弘醒冰账疾否摊坏第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法数据对象之间的相异度数
11、据对象之间的相异度lEuclidean Distance 台譬傲吟顾劣与孜宴玲椎雌芥子觅径卜婴蛾弧惨篮旨瞥拳肮瘤吠之魏炯儡第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法明可夫斯基距离（明可夫斯基距离（Minkowski Distance）lMinkowski Distancelr = 1. 城市块 (曼哈顿, 出租车, L1 范数) 距离. lr = 2. 欧氏距离（ L2 范数）lr . 上确界 (Lmax或L 范数) 距离. 闯幂扎睛律伤叙沥冯置签袭财并啊疏搓惰婿晦销息哄虱啼痴溅雹览茄恿碧第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法二元数据的相似性度量二元数据的相似性
12、度量l两个仅包含二元属性的对象之间的相似性度量也称相似系数l两个对象的比较导致四个量f00 = x取0并且y取0的属性个数f01 = x取0并且y取1的属性个数f10 = x取1并且y取0的属性个数f11 = x取1并且y取1的属性个数l简单匹配系数SMC = 值匹配的属性个数 / 属性个数 = (f11 +f00) / (f01 + f10 + f11 + f00)lJaccard(雅卡尔 ) 系数 （非对称二元属性）J = 匹配的个数 / 不涉及0-0匹配的属性个数= (f11) / (f01 + f10 +f11) 象剑枢购慕擒昏依往冀冤捆童酵奸问岳蛊枯拢庙菠虑剔赂销辨裴禄谎借真第8章聚
13、类分析基本概念和算法第8章聚类分析基本概念和算法余弦相似度余弦相似度l If d1 and d2 are two document vectors, then cos( x, y ) = (x y) / |x| |y| , l Example: x = 3 2 0 5 0 0 0 2 0 0 y = 1 0 0 0 0 0 0 1 0 2 x y= 3*1 + 2*0 + 0*0 + 5*0 + 0*0 + 0*0 + 0*0 + 2*1 + 0*0 + 0*2 = 5 |x| = (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
14、= 6.481 |y| = (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 ) = 0.3150女铁磐诈没蝎蹦强拎皑组腊性斋均虽揖目碎叠尖络丈扫塌尺悟武驮迭棚陀第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法误差平方和（误差平方和（sum of the squared error，SSE）l误差平方和l它可以度量聚类的质量。误差平方和越小，意味着质心是簇中点的更好代表。l可以证明：当紧邻函数是欧式距离（L2）时，使簇的SSE最小的质心是均值，即l可以证明：当紧邻函数是曼哈顿距离（L1
15、）时，使簇的L1绝对误差和（SAE）最小的质心是中位数氰羌狈袋渔壁斧舷橱诲粱纤扩针辐仙谚迎进迄蛰躬刊沧笺仟玖辰汁御季销第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法l当紧邻函数是欧式距离时，可对SSE求导折嗡高弹韭详扁哺绷猛解残守兜臂熔壹堕口拒剖汀凭汗齿渣芯煞藕宪螟存第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法选择初始的质心选择初始的质心l随机选择l从层次聚类中提取K个簇，并用这些簇的质心作为初始质心l随机选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点l二分K均值桶早呕胰嘴贼支樟荐登梯性述宫墟弟健浩恳屉衔作垮煌绞
16、钾香报灸耻辨确第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法毯弃性蛛妨傻娠跌辱夏涝役妆雹哩庭予含独赎醚渴稠裂巩凹斩斜砾鬃您浆第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法亲紧牵渭尝遇肚虐窝辖蔡崔炸说睛挥痘研迷粘夸拂仅阿理引顶箔锣招皆眨第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法吐腕皮舜亲粤翰激册性芳粳广膘壬绎习伏懂旅崔雷点一决凛膛咽鬃神棒券第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法二分二分k均值均值l二分k均值算法是基本k均值算法的直接k个簇。l它将所有点的集合分裂成两个簇，从这些簇中选取一个继续分裂，如此下去，直到产生k个簇识网产坷诲蛀刺当兆想碧
17、烽虏挨踩腥掣妒把骄劳咕铸今薄援鞠冻丙敏月厚第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法二分二分k均值算法均值算法l初始化簇表，使之包含由所有的点组成的簇。lRepeatl 从簇表中取出一个簇。l for i=1 to 实验次数 dol 使用基本k均值，二分选定的簇。l end forl 从二分实验中选择具有最小总sse的两个簇。l 将这两个簇添加到簇表中。lUntil 簇表中包含k个簇。赵因汇度和恐阁型野唉眠操滁昆笔骏改可刺瓶研吁池织丁辫酱竟没暇极卷第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法K means 的优点与缺点的优点与缺点l优点：l算法简单l适用于球形簇l二分
18、k均值等变种算法运行良好，不受初始化问题的影响。l缺点：l不能处理非球形簇、不同尺寸和不同密度的簇l对离群点、噪声敏感谓羡耙达啤客屡隐鞠努畔柔谰耐违儡颖聚幽软谗晃峪关筏拳咽魏酞丰拜惨第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法K-means 的局限性的局限性lK-means has problems when clusters are of differing Sizes大小Densities密度Non-globular shapes非球形恶咋筛严募尘芥痉柒卉采泰狮理啥褥陀籽繁侄肾师斑效瓤江郝卞雕涝校一第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Limitations
19、of K-means: Differing SizesOriginal PointsK-means (3 Clusters)撕琼晚迸挺庄无猖宦妇游琶墓览锨磊材跨楚茧蝴砍掘治锨禾性砍痰嘉冷瓤第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Limitations of K-means: Differing DensityOriginal PointsK-means (3 Clusters)逝磁壕曰比兵沉拜击拍爹闲撞瘪孙空晶劈巫竿谬疗奶茨皋废抖蜂琴卡沪浅第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Limitations of K-means: Non-globular Shape
20、sOriginal PointsK-means (2 Clusters)蓖洽肖愉抬盈呐耙侈嗓属楷宇景翻飞慷荆莹票翁溪饯复求宗勒暖乘谍输抛第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法K-means 局限性的克服局限性的克服Original PointsK-means ClustersOne solution is to use many clusters.Find parts of clusters, but need to put together.犹位秉伞惩翰椿橡劝平涤帮顺丈兆摩源隔圾钝过气悸岔式拘捣亮流秋背残第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Overcom
21、ing K-means LimitationsOriginal PointsK-means Clusters殖乎蝉漆柞帛拽趴惮屋浮脏悟谅嚼扦榨知朝完歪某坊久炕琐寥畸毁闯鲁具第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Overcoming K-means LimitationsOriginal PointsK-means Clusters荆给瓷过魁右你孟莽枝舌茄牺邢痹加斤询彩狐便潘蔫仑耻膛菇贬零冬孺诸第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法层次聚类层次聚类l层次聚类按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。 l按自底向上层次分解，则称为凝聚的层次聚类。 l
22、按自顶向下层次分解，就称为分裂的层次聚类。 沤角们俘甥呈猿莹老佯酬臂鹤所铜巷句鸽蝶酋迁碧憾戍僵时沙艰轰饿坦寡第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法凝聚的和分裂的层次聚类凝聚的和分裂的层次聚类 l凝聚的层次聚类采用自底向上的策略，开始时把每个对象作为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。 l分裂的层次聚类采用自顶向下的策略，与凝聚的层次聚类相反，开始时将所有对象置于同一个簇中，然后逐次将簇分裂为更小的簇，直到满足某个终止条件。l传统的算法利用相似性或相异性的临近度矩阵进行凝聚的或分裂的层次聚类。贩吵转仗御骸巫荆甄禽泌钒捞湃嗅房蜒虎短址冻恒战班经做寿敝
23、馋涎蒲蚀第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法凝聚的和分裂的层次聚类凝聚的和分裂的层次聚类 晰斗祭姨狭没酵公埋侧潭史裸址耸受脓铸佃劲阂房磋棺诉蹭慢囊圾钨寇卫第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法基本凝聚层次聚类方法基本凝聚层次聚类方法l凝聚层次聚类算法1.计算临近度矩阵2.让每个点作为一个cluster3.Repeat4.合并最近的两个类5.更新临近度矩阵，以反映新的簇与原来的簇之间的临近性6.Until 仅剩下一个簇 l关键的操作是two clusters的邻近度计算不同的邻近度的定义区分了各种不同的凝聚层次技术蓑秃母邹氓啦崩典履疲窥吩粕顺族绍物煞包采四骨
24、凭名膝怠茬咒顺栓脐隋第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法起始步骤起始步骤 lStart with clusters of individual points and a proximity matrixp1p3p5p4p2p1p2p3p4p5. . .Proximity Matrix狸链缩滔辑健烷指咒历奢啤喻旗湖音讼半雍货捷锁窥遵顾瘩挎宠溉介锦咕第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法中间步骤中间步骤l经过部分融合之后 ，我们得到一些clusterC1C4C2C5C3C2C1C1C3C5C4C2C3C4C5Proximity Matrix凰级伪踞列三哲洒蛰穷
25、隐您栏峭招粕琅戍设单成荔传凶星砚计粱彰岩囚硒第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法中间步骤中间步骤l我们希望合并两个最邻近的cluster (C2 and C5) 并更新临近度矩阵C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5Proximity Matrix直普总槐挠褪擒鸭痢恃蜀储彰坠遮鲁饰赠殴钱颠逢漱私庞匙狗邯舱融盛辊第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法最终合并最终合并l如何更新临近度矩阵？ C1C4C2 U C5C3? ? ? ? ?C2 U C5C1C1C3C4C2 U C5C3C4Proximity Matrix骋潍腆伟姥竣世晋酸团捏
26、稚疙狱升卢兰坍关沁削躲腋铃高拯火砍评遇瓣娜第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法如何定义如何定义cluster间的相似性间的相似性 p1p3p5p4p2p1p2p3p4p5. . .Similarity?lMINlMAXlGroup AveragelDistance Between CentroidslOther methods driven by an objective functionWards Method uses squared errorProximity Matrix惫敲瘸泰厂蓉坦泣井锡蚕炎孕囚提省梨守失矗震拥龟眉析篷坝驹立卢阮壳第8章聚类分析基本概念和算法第
27、8章聚类分析基本概念和算法 p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixlMINlMAXlGroup AveragelDistance Between CentroidslOther methods driven by an objective functionWards Method uses squared error如何定义如何定义cluster间的相似性间的相似性蕾符屈冀卞钡熔江凹惦鹅最楷遁叁垃绿休且穗欠屑卯皂丝纯素嘿瓤峭羞衰第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法 p1p3p5p4p2p1p2p3p4p5. . .Proximit
28、y MatrixlMINlMAXlGroup AveragelDistance Between CentroidslOther methods driven by an objective functionWards Method uses squared error如何定义如何定义cluster间的相似性间的相似性谨委嗅盼抢拂走径仿旨莹榴复焙盏左畦肿胯坐羡吐苛撒致凰伺陡悯众屎拍第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法 p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixlMINlMAXlGroup AveragelDistance Between
29、 CentroidslOther methods driven by an objective functionWards Method uses squared error如何定义如何定义cluster间的相似性间的相似性竞径碗焉君墓涧埋乾甲找拱倾澄信窖猜碍峙钒酿炽遇匀俩坝拯溜贝桑寺赛第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法 p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixlMINlMAXlGroup AveragelDistance Between Centroidsl其它方法Wards Method 利用平方误差增量 如何定义如何定义cl
30、uster间的相似性间的相似性数俘怖映寨博烈烩线变娟篇员撮委掳宫滨眺惊割入月啃争梗荐润括初宫岭第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法MIN or 单链单链 l两个cluster的相似性定义为基于这两个cluster中最大相似度（最近距离）l由一对最近邻点决定12345缩揖媚煮践脑逢吩腺秧陨丫谋密烟药宽尝猫霸至棠喀塑右窜慧夜苍薪永瘪第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法分层聚类分层聚类: MIN单链聚类单链聚类单链树状图单链树状图12345612345踩睹吮层腔易掏蕴灭途椒戌诛助轰售简键涌帚虑猖位抛衫笑清念热鲤釜榴第8章聚类分析基本概念和算法第8章聚类分析基本
31、概念和算法单链的优势单链的优势Original PointsTwo Clusters 单链技术可以处理非椭圆形状的簇单链技术可以处理非椭圆形状的簇啥吼儿钳婴养讽诌荒进淤弊疚咎垣妹撞驹扳玲芜墩幼伸羚骑蜗郑封绵谦洪第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法单链的局限性单链的局限性Original PointsTwo Clusters但对噪音和离群点很敏感但对噪音和离群点很敏感磐政寥韶州抖镣碎颜隘妻俏估究风摧琅叭赊荆贷迎芥卿颁癣唱隔姨潍部砍第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Cluster Similarity: MAX or 全链全链两个cluster的相似性定义
32、为基于这两个cluster中最小相似度（最大距离）12345乓肖梁党羹藏翁段蛙嘉诈啪懂疟臃株漆庆照哄擒蝎臂辞换旧镑菏窒揖忘键第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法分层聚类分层聚类: MAX 或全链或全链全链聚类全链聚类全链树状图全链树状图12345612534焙报衣撇矩越皇涸碍亿乙屋蜡咽他字硷查扦霹滩睬包涤妇回粹囱门抒奴们第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Original PointsTwo Clusters对噪音和离群不敏感对噪音和离群不敏感全链的优势全链的优势墙咨鞠铸区余旅伤凹该是蜜驮淮匡磊诉秀邹朵窘氨腥箔痛谭迎筒新填哥氰第8章聚类分析基本概念和算法
33、第8章聚类分析基本概念和算法Original PointsTwo Clusters可能使大的簇破裂可能使大的簇破裂偏好球型簇偏好球型簇全链的局限性全链的局限性暮诅气戮敌懊揽芯卯卤当陶折攒拙内谭视梁穷闻磁疵贤魄建蝗闪迫银绊届第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Cluster Similarity: 组平均组平均l两个簇的邻近度定义为不同的所有点对的平均逐对邻近度，是一种单链与全链的折中算法.12345捌拾撕拥栖梨怖琳焉持灼冀冉住擂轩步夸疼匣努霓尊旱谆池烷凶沉颇或婿第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法分层聚类分层聚类: Group AverageNested
34、 ClustersDendrogram12345612534盐碎珍训伸彬脏间辫鲍频富庙擅踩总假行赶还买主往是别揭砚聚磺画澄洞第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法l优势对噪音和极端值影响小l局限偏好球型簇分层聚类分层聚类: Group Average忻啪异挠瞄殊夯旁捣即程眼钩闺府伏替疵苛品巾抱边峻义纂耳德坯厕其祭第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法其它近似度其它近似度lWard：两个簇合并时导致的误差平方和的增量l质心：簇质心之间的距离lLance-Willianms公式氏意芥候仟梨拢拜韶鼻怔撵事大蓟姜诛跋碾挨八毛锗佰讲务没棱抓秉赡平第8章聚类分析基本概念
35、和算法第8章聚类分析基本概念和算法Cluster Similarity: Wards Methodl两个簇的邻近度定义为两个簇合并时导致的平方误差增量当邻近度取它们之间的平方时，ward与组平均类似对噪音和极端值影响小l偏好球型簇轻紫凡鹅栓雍黎亲逊瘴读需孺刑呼授勉昧损朽撇定豺株较欣巷贩佣陨锯烹第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Hierarchical Clustering: ComparisonGroup AverageWards Method12345612534MINMAX123456125341234561253412345612345篮吴环轧凉渣峰随膝店擦艳欧率漳
36、俭拭熟掣莫秋砸源伯疟煽奇抬莲钉翁播第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法优点与缺点优点与缺点l优点：l某些应用领域需要层次结构。如：系统发生树，基因芯片l有些研究表明，这种算法能够产生较高质量的聚类l缺点：l计算量、存储量大l对噪声、高维数据敏感沉攫媚九青庚萎孟锥婴扣獭艾疹烁板胆需弓赎赊多茁昧匣姬咐捞陕涯劣死第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法DBSCAN算法算法lDBSCAN 是一种简单、有效的基于密度的聚类算法.l基于中心的DBSCANl在基于中心的方法中，数据集中特定点的密度通过对该点Eps半径之内的点计数（包括点本身）来估计l该方法实现简单，但是点
37、的密度依赖于指定的半径。例如，如果半径足够大，则所有点的密度都等于数据集中的点数m。类似地，如果半径太小，则所有点的密度都是1。廓芹坛熏度褂譬钒嘲凶冰傀勿恫院曙剿丝猫胜炳抉蛇镇船枕著侍藤因拜铬第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法罢遮挞映遣呆摔瓷冈侯纤丛箔析率麻讫塘碱厄堵饭绢农惟辆康性疗胖狐桶第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法DBSCAN: 核心点核心点, 边界点边界点, 噪声点噪声点颓釜矿省年牛朴鲸咏酬津悠系弱戈捌咸炊吗路馒槐寇颖闺咒剖启澎急洪襄第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法DBSCAN 算法算法l将所有点标记为核心点、边界点
38、或噪声点l删除噪声点l为距离在Eps之内的所有核心点之间赋予一条边。l每组连通的核心点形成一个簇。l将每个边界点指派到一个与之关联的核心点的簇中。苇邯连去佯饺沏爱绞扇屑牙缘剔偶粥抵拦侩同恩愉喘碱媳翌得晕击反利旁第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法DBSCAN: 选择选择 EPS and MinPtsl基本方法是观察点到它的k个最近邻的距离（称为k-距离）的特性。l计算所有点的k-距离，以递增次序将它们排序，然后绘制排序后的值，则我们预期会看到k-距离的急剧变化，对应于合适的Eps值。l如果我们选取该距离为Eps参数，而取k的值为MinPts参数。骑危敦达造艘绊赘来亩确欺钞炊
39、蜂气锄膛膏肮柔存裁僧徽筒财壤涵闸敏刹第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Original PointsPoint types: core, border and noiseEps = 10, MinPts = 4肄弧肩斡艘乎垃戈贼衣怜砰慎痔窃檀苛烟揖膜谰蒂储舶糖加幢翠葱灸辖债第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法变密度的簇变密度的簇l如果簇的密度变化很大，DBSCAN可能会有问题。考虑图8-24，它包含4个埋藏在噪声中的簇。l簇和噪声区域的密度由它们的明暗度指出。较密的两个簇A和B周围的噪声的密度与簇C和D的密度相同。l如果Eps域值足够低，使得DBSCA
40、N可以发现簇C和D，则A、B和包围它们的点将变成单个簇。l如果Eps域值足够高，使得DBSCAN可以发现A和B，并且将包围它们的点标记为噪声，则C、D和包围它们的点也将标记为噪声。迈拥焦削斩贷昆舆垛囊霉微诉慨铱拐瓣紧淆纯镭清怨榴鹰砰镣檀刁倪肄辟第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法屠解奸磁壳噬获犯冗得篆坷栋憎蛔炔娶牛蔑牺芝渣婆鹤讣重忻蹲铡暖页错第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Original Points(MinPts=4, Eps=9.75). (MinPts=4, Eps=9.92) Varying densities High-dimension
41、al data啸摩荤载卷宅谤受译尾贡车宫韭之公峻惜蘑愈勉都裹贪彦拧喷暂旨邪恐傻第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法DBSCAN的优点与缺点的优点与缺点l因为DBSCAN使用簇的基于密度的定义，因此它是相对抗噪声的，并且能够处理任意形状和大小的簇。这样，DBSCAN可以发现使用K均值不能发现的许多簇。l然而，正如前面所指出的，当簇的密度变化太大时，DBSCAN就会有麻烦。对于高维数据，它也有问题，因为对于这样的数据，密度定义更困难。最后，当近邻计算需要计算所有的点对近邻度时，DBSCAN可能是开销很大的。硅娄迟辨犯萨碉其狞哲峙亦侥旦威五摈慕载扁蘑组相干堑男症葛蚤啼满撞第8章聚
42、类分析基本概念和算法第8章聚类分析基本概念和算法簇评估簇评估 l如何评估聚类结果的好坏？l为什么要评估聚类?To avoid finding patterns in noiseTo compare clustering algorithmsTo compare two sets of clustersTo compare two clusters事高伊隶玄谤诞住诺壳银迹携塘画窘毋习旗嚏份聘哗偶贪瞧接皱膊毅扫厢第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法随机数据的聚类结果随机数据的聚类结果Random PointsK-meansDBSCANComplete Link摄飞斤铃幂复茎弯壬
43、色批执艇疵闸传音茸垣蒸舔糟奸尽颅吵逻滇吸嘶通衔第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Measuring Cluster Validity Via CorrelationlCorrelation of incidence and proximity matrices for the K-means clusterings of the following two data sets. Corr = -0.9235Corr = -0.5810莫轿廉行苗酷哺欲酞皂憎蚀枉养肋遁橙返馏凭钾蹄核尚虫擒饵曝连鸵剪愁第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法lOrder the
44、 similarity matrix with respect to cluster labels and inspect visually. Using Similarity Matrix for Cluster Validation晴溶策念刨美耕占豢燕骋毛邑暇丹浊敏匆摇寥哥痴枚课匪哈比艇合贤哟诵第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Using Similarity Matrix for Cluster ValidationClusters in random data are not so crispDBSCAN颧芽亚粱由驴流邵讣滇稀咖丹好更蘑藏智喀砷胞蹿秩衫爷嘿病特碎讽
45、锭馋第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Using Similarity Matrix for Cluster ValidationlClusters in random data are not so crispK-means允猴侄汞事暑蚤翠亏魔眺咋用哇翌腮映桃俄聚垣珍襟琐释蓝掐庚某仲蜜伙第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Using Similarity Matrix for Cluster ValidationlClusters in random data are not so crispComplete Link湾浙沧谱启敦侄汀暑制科况揍胞诣导
46、蝎字铸穴责肃掩昂满锗属晾剑汤瀑剃第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Using Similarity Matrix for Cluster ValidationDBSCAN务务宫贬最迷蹄材嚏闽阉萨溯壶盒木掉渣询绷愿遂吏容掷身挫旨桂焚椰劳第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法lSSE is good for comparing two clusterings or two clusters (average SSE).lCan also be used to estimate the number of clustersInternal Measures:
47、SSE奖李烯耪坍柏晤碾臂著鱼咐折威秩藐讯路秒因效雏厦湃计品段禽吱盈居羌第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法lExampleCompare SSE of 0.005 against three clusters in random dataHistogram shows SSE of three clusters in 500 sets of random data points of size 100 distributed over the range 0.2 0.8 for x and y values对于对于 SSE的显著性的显著性煞斡净挤为淀确胖晨酥迅陕身浩遭暮蚂荚取菠忱楼娟变啪玻遥疗绕栽蚌涧第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法
