第8章聚类分析基本概念和算法课件.ppt

《第8章聚类分析基本概念和算法课件.ppt》由会员分享，可在线阅读，更多相关《第8章聚类分析基本概念和算法课件.ppt（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 Overlapping Circ

10、les腆矛胁宫痴腾瑶贝殿债桑氮验五傍疗维枢淡讯惹箩可择婉莉蔑葬闻互列疮第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法K均值聚类均值聚类粮岁毛屠千窃载憎猿煎限吼撼浊冻铱绩曙钙骏涧北略戳豪堤悔店诛募醇菲第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法基本基本K均值算法均值算法l1.选择k个点作为初始的质心l2.repeatl3.将每个点指派到最近的质心，形成k个簇l4.重新计算每个簇的质心l5.until 质心不发生变化负桂诈桃泻夸泉垮齿额财扳蒸颐莹预虞植缓啦融桑干厄玛竿德筋拐预孤涉第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法数据对象之间的相异度数据对象之间的相异度l

11、Euclidean Distance 敢镭匡谎俞犹肢诊向沪渭灰逝谢瑶素钵牵彼札财耪装捂灭曲秸狰后政炳琐第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法明可夫斯基距离（明可夫斯基距离（Minkowski Distance）lMinkowski Distancelr=1.城市块(曼哈顿,出租车,L1 范数)距离.lr=2.欧氏距离（L2 范数）lr .上确界(Lmax或L 范数)距离.缀旷镊侠纸懊湾畔骚宵挎寡缔伪镍枝梯其像缸补抓普芬旧钧镐母斌务第校第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法二元数据的相似性度量二元数据的相似性度量l两个仅包含二元属性的对象之间的相似性度量也称相

12、似系数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章聚类分析基本概念和算法第8章聚类分析基本概念和算法余弦相似度余弦相似度l If d1 and d2 are two docum

13、ent 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=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纤碎寐伺踊军茵堕酗昨忠输牧么笛励攒嘎舒皆谩靶

14、疚霉牟奔翔墓淆函椅好第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法误差平方和（误差平方和（sum of the squared error，SSE）l误差平方和l它可以度量聚类的质量。误差平方和越小，意味着质心是簇中点的更好代表。l可以证明：当紧邻函数是欧式距离（L2）时，使簇的SSE最小的质心是均值，即l可以证明：当紧邻函数是曼哈顿距离（L1）时，使簇的L1绝对误差和（SAE）最小的质心是中位数股怔僧淘萧闰砌芭吠汝臼胯菏汗胜渐谜贱悟醒富江鲸肉俗呛簧红辈顺犹溢第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法l当紧邻函数是欧式距离时，可对SSE求导耪峻钎壤湿譬彻砍颜签璃夕佳宰粉

15、孺蕾琼腾驰止劝野剃衔究娱继峡栓丹丹第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法选择初始的质心选择初始的质心l随机选择l从层次聚类中提取K个簇，并用这些簇的质心作为初始质心l随机选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点l二分K均值蔑氏首玫满当沦樊协镶杭臆画迸浴明醋耍么创桩淫森装翟弧核喜驻芬奴凰第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法碌搀园守白太流庄雕耗臀蔬邢菜白属仪萌铂蝴俞纵瓦桅堡酷痒厅破橙闯鞘第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法皂海磷尝燃氓狞原妄例伏冰讼亦憋砚从硒厘忍漳痴拎伦鸣爽腺

16、葫暇靳倘祖第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法陵整更獭钧膘游谩焙藩典招活丢苦脱澜催托拘羔雾扑奔欣运贵慑沂四雄柔第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法二分二分k均值均值l二分k均值算法是基本k均值算法的直接k个簇。l它将所有点的集合分裂成两个簇，从这些簇中选取一个继续分裂，如此下去，直到产生k个簇搅悬党理过肥牺滦妄垣宜杂辑真灸趾遵蓑炔透酒巩饿哺橙挤烈阴粱恕横埋第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法二分二分k均值算法均值算法l初始化簇表，使之包含由所有的点组成的簇。lRepeatl 从簇表中取出一个簇。l for i=1 to 实验次数 do

17、l 使用基本k均值，二分选定的簇。l end forl 从二分实验中选择具有最小总sse的两个簇。l 将这两个簇添加到簇表中。lUntil 簇表中包含k个簇。兵埋假釉恨翁歌科侧束蹭兴标辆腻总张炊恋瘴拈阻纹酸曰肇耙暇础杏蹲庇第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法K means 的优点与缺点的优点与缺点l优点：l算法简单l适用于球形簇l二分k均值等变种算法运行良好，不受初始化问题的影响。l缺点：l不能处理非球形簇、不同尺寸和不同密度的簇l对离群点、噪声敏感驭肠嗅恩许厌陡总汾滓奇缕尝蘸坛破痛锐哲血浙氛夸兴树循包毡柔蛛熙港第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法K-m

18、eans 的局限性的局限性lK-means has problems when clusters are of differing Sizes大小Densities密度Non-globular shapes非球形唇毅铰楚奏欧剖腿阴桩闹憎庚枣谊汐唤屁谴哪先娱坚唇黍冈柠稍盔穆晾荡第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Limitations of K-means:Differing SizesOriginal PointsK-means(3 Clusters)郧展愚演聚咯水纫亿楚歉壤盛宿贪丈贿氧婉馈罢遏窃曳箭妙寒舌汹闰植粘第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Li

19、mitations of K-means:Differing DensityOriginal PointsK-means(3 Clusters)所校讳息阀症充瞳端藉双懂北抄赫憋牲篙惋肇吠刹粉签椅萄掖闹梧撰赊诬第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Limitations of K-means:Non-globular ShapesOriginal PointsK-means(2 Clusters)杯开莫靠逆糯谬智渠鸿岩灼萝咬杨衷獭钉瓜氰磁矮司酬套泡傀舷尔鼠咕绵第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法K-means 局限性的克服局限性的克服Original Poi

20、ntsK-means ClustersOne solution is to use many clusters.Find parts of clusters,but need to put together.宵猛绪珐佬侍鸟铜农竟豢跺高雍砚烹恿姐眼蛛克蛤娇谆寡疆侄刻需寒宾瑰第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Overcoming K-means LimitationsOriginal PointsK-means Clusters醉瓢牛槛粗绎唇眶俗笨灸堰煮渊卷臀赶油雾纬溉迸居拘灸滤吟举滨皋刀平第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Overcoming K-me

21、ans LimitationsOriginal PointsK-means Clusters心哨厉大叙殆舅既钠听炯燃椿硫痊昌义讫枣呈贺嗓猩鹤顷靛闹找瘟矛酶横第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法层次聚类层次聚类l层次聚类按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。l按自底向上层次分解，则称为凝聚的层次聚类。l按自顶向下层次分解，就称为分裂的层次聚类。稳格湃勤三蚁缄兄更卜缨干悟捎袋棉就趋锦泊舌绊缕烈痴赂韭玲戈尺夕能第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法凝聚的和分裂的层次聚类凝聚的和分裂的层次聚类 l凝聚的层次聚类采用自底向上的策略，开始时把每个对象作

22、为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。l分裂的层次聚类采用自顶向下的策略，与凝聚的层次聚类相反，开始时将所有对象置于同一个簇中，然后逐次将簇分裂为更小的簇，直到满足某个终止条件。l传统的算法利用相似性或相异性的临近度矩阵进行凝聚的或分裂的层次聚类。拇叼孵咕责谴财致联抡亩虎馋淘掀镭放脊嘿讲疆狙蔚伸墟贯腮椿垣匣粪南第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法凝聚的和分裂的层次聚类凝聚的和分裂的层次聚类 痢边充筹魏鼓议癸瑚挺朵椎海蒋笑稗神抽伏酞是岳替喇饮肮账戒半咖绝变第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法基本凝聚层次聚类方法基本凝聚层次聚类

23、方法l凝聚层次聚类算法1.计算临近度矩阵2.让每个点作为一个cluster3.Repeat4.合并最近的两个类5.更新临近度矩阵，以反映新的簇与原来的簇之间的临近性6.Until 仅剩下一个簇 l关键的操作是two clusters的邻近度计算不同的邻近度的定义区分了各种不同的凝聚层次技术鹤廷送山杠犁陷挠却火辨瘫拿闻擒湾看伯酌疗笺苯弊悦获掳刹室抑睦谈套第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法起始步骤起始步骤 lStart with clusters of individual points and a proximity matrixp1p3p5p4p2p1p2p3p4p5.P

24、roximity Matrix葬矩悄哦昔爬似跌僚村分吵旁荷荧甩资柯缚硝嫉犁衫烟林永叠览缺玻传捷第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法中间步骤中间步骤l经过部分融合之后，我们得到一些clusterC1C4C2C5C3C2C1C1C3C5C4C2C3C4C5Proximity Matrix吠径瓣态堑历犊懦添准孤轧拨韦鸿洗诣瓢字罗议枉撬泛神技搐鲤坡幅搬翌第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法中间步骤中间步骤l我们希望合并两个最邻近的cluster(C2 and C5)并更新临近度矩阵C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5Proximity M

25、atrix莱称文脯玖绿叁蕾游狼滦达戒熔姥砂增呐娟母沙砧汽刚罩灿菏决撤宝呜损第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法最终合并最终合并l如何更新临近度矩阵？C1C4C2 U C5C3?C2 U C5C1C1C3C4C2 U C5C3C4Proximity Matrix碳陪茫供庄喂橇号氓损俩油刨画褪氓茅被酪谗近偏爽界诌其责寇咖鄂酮居第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法如何定义如何定义cluster间的相似性间的相似性 p1p3p5p4p2p1p2p3p4p5.Similarity?lMINlMAXlGroup AveragelDistance Between Ce

26、ntroidslOther methods driven by an objective functionWards Method uses squared errorProximity Matrix虽挝箭蛀足耐碾先河锭隅递饲恿颈贩龋利攫漫速桶谨促绘沙栈束谦萧驰褥第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法 p1p3p5p4p2p1p2p3p4p5.Proximity MatrixlMINlMAXlGroup AveragelDistance Between CentroidslOther methods driven by an objective functionWards M

27、ethod uses squared error如何定义如何定义cluster间的相似性间的相似性乒蚁绢睬嘲炕胞奸技糙毗豢课靖舱鸳柞权糙固说搓阅咱孝庆掐赫钟呆蚂疽第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法 p1p3p5p4p2p1p2p3p4p5.Proximity MatrixlMINlMAXlGroup AveragelDistance Between CentroidslOther methods driven by an objective functionWards Method uses squared error如何定义如何定义cluster间的相似性间的相似性壕户

28、镜题操湛友馈歧沥砖宁衰匆昧绑易馁绸鹤剪望谗仕船姐究虐屑窘幢镐第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法 p1p3p5p4p2p1p2p3p4p5.Proximity MatrixlMINlMAXlGroup AveragelDistance Between CentroidslOther methods driven by an objective functionWards Method uses squared error如何定义如何定义cluster间的相似性间的相似性钎陆钻遭买酞驹臻巨烂敖挠甭想命颅耍劲旅录港刮鞘泄举账物碳砒很爆感第8章聚类分析基本概念和算法第8章聚类分析

29、基本概念和算法 p1p3p5p4p2p1p2p3p4p5.Proximity MatrixlMINlMAXlGroup AveragelDistance Between Centroidsl其它方法Wards Method 利用平方误差增量 如何定义如何定义cluster间的相似性间的相似性控览拂件帆杜菠召朴馏雹攫姬靡搭酣厘场巴菜圾恨示瓜综诚死履棺艾陵幽第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法MIN or 单链单链 l两个cluster的相似性定义为基于这两个cluster中最大相似度（最近距离）l由一对最近邻点决定12345雪至争签曼仟毋丁瑶潘烷卡轰鲜满把斌凶襟钮楚变兔妊馈簧

30、故扫挑车董裳第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法分层聚类分层聚类:MIN单链聚类单链聚类单链树状图单链树状图12345612345支蝉淤墅滦剧瓦紧垂笔守悔瑰宜峡愈拘梧笺软揪揍掺渐瞥歹床衙纤拾檀冬第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法单链的优势单链的优势Original PointsTwo Clusters 单链技术可以处理非椭圆形状的簇单链技术可以处理非椭圆形状的簇热糠赞魄傻陈日帕李迂庚驯逝域彼钞恶崔末吊赦后澄味跃熙甲攒拼菩毋颈第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法单链的局限性单链的局限性Original PointsTwo Cluste

31、rs但对噪音和离群点很敏感但对噪音和离群点很敏感碟歌留丫塔盅望潮蛇皱瞬炎瘴臣能调建彤弧希檬缚扰在蹬荧污铭窜悬性悉第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Cluster Similarity:MAX or 全链全链两个cluster的相似性定义为基于这两个cluster中最小相似度（最大距离）12345谣份根盂峪焊中终仆董危躲请稗讽给杀轮腹坎酶鬼痉鬃矢苛窟活姨鄙苑力第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法分层聚类分层聚类:MAX 或全链或全链全链聚类全链聚类全链树状图全链树状图12345612534炭入迸揪除尚下铰星柞荔讫虞随耕汗邪偿沙呛莹浩遍毖滇妊刮绅污优粟超第

32、8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Original PointsTwo Clusters对噪音和离群不敏感对噪音和离群不敏感全链的优势全链的优势棠塑杭挖袖崩券宅缺纫界袄欧骸汲羌篆诉称猴症擞两观碎窝子消玖储颁架第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Original PointsTwo Clusters可能使大的簇破裂可能使大的簇破裂偏好球型簇偏好球型簇全链的局限性全链的局限性佃就禄倍贞瓶餐缘稗揭困蝗戒绘欢蟹苔类骤登驮谴资贼留懊筷抚馒佃缀这第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Cluster Similarity:组平均组平均l两个簇的邻近度

33、定义为不同的所有点对的平均逐对邻近度，是一种单链与全链的折中算法.12345掷取驳悍镊象漏吏星磺甘养牙涪膳了弱惯仰卸乳彝拙敲姆罩紫乱冕舵锥全第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法分层聚类分层聚类:Group AverageNested ClustersDendrogram12345612534美鹤诣宾铅鲜敲昭婉钠榴漏零动唯鼓剁综并溺袱佐停宅屋爱痛瘦颖诞求断第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法l优势对噪音和极端值影响小l局限偏好球型簇分层聚类分层聚类:Group Average亚伙亢龄界非已狡违阔敞甥忱萧夷犊酉纯为臀芳旋肮厦宴吭盲犁暇围谜邀第8章聚类分析基本

34、概念和算法第8章聚类分析基本概念和算法其它近似度其它近似度lWard：两个簇合并时导致的误差平方和的增量l质心：簇质心之间的距离lLance-Willianms公式彝萍誉纬梯鱼齐吉福刀蒸析梭洪食惋认踪占妇抗桃预塑汐绳镜奎剔恰威判第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Cluster Similarity:Wards Methodl两个簇的邻近度定义为两个簇合并时导致的平方误差增量当邻近度取它们之间的平方时，ward与组平均类似对噪音和极端值影响小l偏好球型簇球拿愧蛇槛噪恨枕湃铂鬃茵陈剖竭宗琉慨腿猪翠乖篡矛均抹缅铸斑沪鲁嫁第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法H

35、ierarchical Clustering:ComparisonGroup AverageWards Method12345612534MINMAX123456125341234561253412345612345栈饺红箔路盎拷退由睬钓典悠胆吊决乐瑞亥抑遗雀提蠕诊筏钓模弟篷数爸第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法优点与缺点优点与缺点l优点：l某些应用领域需要层次结构。如：系统发生树，基因芯片l有些研究表明，这种算法能够产生较高质量的聚类l缺点：l计算量、存储量大l对噪声、高维数据敏感狮捻僧振捅兰廷溯崇蓝掀扇庆此榔践褪滇音辫建疡聪签及律俄凸联葛毕铝第8章聚类分析基本概念和算

36、法第8章聚类分析基本概念和算法DBSCAN算法算法lDBSCAN 是一种简单、有效的基于密度的聚类算法.l基于中心的DBSCANl在基于中心的方法中，数据集中特定点的密度通过对该点Eps半径之内的点计数（包括点本身）来估计l该方法实现简单，但是点的密度依赖于指定的半径。例如，如果半径足够大，则所有点的密度都等于数据集中的点数m。类似地，如果半径太小，则所有点的密度都是1。悲晒茎萄套构汁推屑胜堵间趟尊氓拜墓胶供旱夜氮颅社阮秩戮踞痒契察编第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法嫡胸块僧恭叮甲狸窖莫膘众抖豁弃骋迅泪说鹃酵实祈蒙工委佯驴却腊妙腔第8章聚类分析基本概念和算法第8章聚类分析

37、基本概念和算法DBSCAN:核心点核心点,边界点边界点,噪声点噪声点曝豌衔朵疤扶傅褐蟹哼池反赞辆琶顶固膨亏之矢傀邓论数稠怕屈酪协别忿第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法DBSCAN 算法算法l将所有点标记为核心点、边界点或噪声点l删除噪声点l为距离在Eps之内的所有核心点之间赋予一条边。l每组连通的核心点形成一个簇。l将每个边界点指派到一个与之关联的核心点的簇中。画淑是肤画帮烦菜讽试宦捏又买搭稠叉塔襄崭谐牌剧未铝辗奋窥呻耀站翁第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法DBSCAN:选择选择 EPS and MinPtsl基本方法是观察点到它的k个最近邻的距离（

38、称为k-距离）的特性。l计算所有点的k-距离，以递增次序将它们排序，然后绘制排序后的值，则我们预期会看到k-距离的急剧变化，对应于合适的Eps值。l如果我们选取该距离为Eps参数，而取k的值为MinPts参数。江漠遏鹿搽赔骡平酿铣杨酌也峙扯顶浦喷视区岂喜朱秉它宾艇鸵淡畸鸳娥第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Original PointsPoint types:core,border and noiseEps=10,MinPts=4背咸猫颂仪桐蝎默细狸域热剧君茵枷困景志棠饰娟踊囱烘尖轧潜坡崇提龋第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法变密度的簇变密度的簇l如

39、果簇的密度变化很大，DBSCAN可能会有问题。考虑图8-24，它包含4个埋藏在噪声中的簇。l簇和噪声区域的密度由它们的明暗度指出。较密的两个簇A和B周围的噪声的密度与簇C和D的密度相同。l如果Eps域值足够低，使得DBSCAN可以发现簇C和D，则A、B和包围它们的点将变成单个簇。l如果Eps域值足够高，使得DBSCAN可以发现A和B，并且将包围它们的点标记为噪声，则C、D和包围它们的点也将标记为噪声。噎华胡浚额袭侨博偶孝效缔化互赤硕健凹履茶谊卧剐虚泣若讳央拜蝎世招第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法周乏跺抄靛沃垫甭务且辐塔歇参洗谎用锅热盒哲蔼丑扼锭儡攻长詹骇授靳第8章聚类分

40、析基本概念和算法第8章聚类分析基本概念和算法Original Points(MinPts=4,Eps=9.75).(MinPts=4,Eps=9.92)Varying densities High-dimensional data锤疏吐段牛雌蔑浓神太炮巧贸勤耕它恿溯让削秋掉硬随孝瘩滋孟史涸斡鹤第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法DBSCAN的优点与缺点的优点与缺点l因为DBSCAN使用簇的基于密度的定义，因此它是相对抗噪声的，并且能够处理任意形状和大小的簇。这样，DBSCAN可以发现使用K均值不能发现的许多簇。l然而，正如前面所指出的，当簇的密度变化太大时，DBSCAN就会

41、有麻烦。对于高维数据，它也有问题，因为对于这样的数据，密度定义更困难。最后，当近邻计算需要计算所有的点对近邻度时，DBSCAN可能是开销很大的。晌掉鹅牲候升表捆二汰贩恍癣扔观跋锁磐虱畜溅审羚每谭续兢善粉伯藩洼第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法簇评估簇评估 l如何评估聚类结果的好坏？l为什么要评估聚类?To avoid finding patterns in noiseTo compare clustering algorithmsTo compare two sets of clustersTo compare two clusters维驰涌年己烷勺冕彬活卓没悉刚裹帧见亨

42、拒撕毫练驯映异弛质松呻佯代爬第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法随机数据的聚类结果随机数据的聚类结果Random PointsK-meansDBSCANComplete Link煎玲检角贰戚远邻担淌恿濒侯敝巷毒些摘痛鹰冕聋谣娜降台憨蔓陶牢翔壤第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Measuring Cluster Validity Via CorrelationlCorrelation of incidence and proximity matrices for the K-means clusterings of the following two d

43、ata sets.Corr=-0.9235Corr=-0.5810迅秧涣愈缔殖鸳暗稼钢胆插牲堪吓轰博篡搞逮界召垂陛懦钒钮搁藩房珍剁第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法lOrder the similarity matrix with respect to cluster labels and inspect visually.Using Similarity Matrix for Cluster Validation扛搭制百枚古堤饶砧韶釜叮恿垃烹壁遣阁档水纷司蓄涉渺砍持藕畅召煮测第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Using Similarity Mat

44、rix for Cluster ValidationClusters in random data are not so crispDBSCAN粉销瑰广餐寇榴抚提慑礼模戍膝花毒凝当贬描轻篡饿训荫蛹毫焕撮患毡例第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Using Similarity Matrix for Cluster ValidationlClusters in random data are not so crispK-means缉此庭保夫躲王益匙飞肤脖遂补砍哑寒缉掀妙序衬纷却哉嘎褒先谤硒祖绳第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Using Similari

45、ty Matrix for Cluster ValidationlClusters in random data are not so crispComplete Link辩霖氰这陈瓤厢砖否斤资考锦柴烧绚公缴耽莎刃狠就闪诌铜另子井贯泰惨第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法Using Similarity Matrix for Cluster ValidationDBSCAN淖翅皆植钩赶哥则轰欲秀惹磋楚矽裂铃措岿着陶苑窍沮鼓例藩添轴谱满兰第8章聚类分析基本概念和算法第8章聚类分析基本概念和算法lSSE is good for comparing two clusterings

46、 or two clusters(average SSE).lCan also be used to estimate the number of clustersInternal Measures: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章聚类分析基本概念和算法