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