《数据挖掘原理与应用 第2版 》课件 第7章 聚类分析

第7章聚类分析基本概念聚类分析聚类是将物理或抽象对象的集合划分成为由类似的对象组成的多个属类的过程。比较相近比较相似比较相像如何衡量簇间最大化簇内最小化聚类分析聚类是将物理或抽象对象的集合划分成为由类似的对象组成的多个属类的过程。聚类分析按照一定的算法规则，将判定为较为相近和相似的对象，或具有相互依赖和关联关系的数据聚集为自相似的组群，构成不同的簇。物以类聚人以群分聚类分析将数据划分成有意义或有用的组群，在各种应用中，一个簇中的数据对象可以被作为一个整体来对待应用商务

-从客户信息库中发现不同的客户群，以购买模式来刻画不同的客户群的特征，进行有针对性的精准营销聚类分析将数据划分成有意义或有用的组群，在各种应用中，一个簇中的数据对象可以被作为一个整体来对待应用生物学-通过对基因进行类别划分，推导动植物的分类，获得对种群中固有结构的认识聚类分析将数据划分成有意义或有用的组群，在各种应用中，一个簇中的数据对象可以被作为一个整体来对待应用地理-从地球观测数据库中的数据确定地理上相似的地区房地产

-根据房屋的类型、价值和地理位置对商品房进行分组，区别处理聚类分析将数据划分成有意义或有用的组群，在各种应用中，一个簇中的数据对象可以被作为一个整体来对待应用信息-对Web上的文档进行处理分类，以便于进行分类检索和发现信息与分类相区别分类训练数据

产生规则（提取模型）

标注Supervised有监督的聚类数据

发现相似

簇Unsupervised无监督的聚类的复杂性簇类型明显分离的(Well-Separated)每个点到同簇中任一点的距离比到不同簇中所有点的距离更近。3个分离簇聚类的复杂性簇类型基于原型的每个对象到定义该簇的原型的距离比到其他簇的原型的距离更近。对于具有连续属性的数据，簇的原型通常是质心，即簇中所有点的平均值。当质心没有意义时，原型通常是中心点，即簇中最有代表性的点。基于中心的（Center-Based）的簇：每个点到其簇中心的距离比到任何其他簇中心的距离更近。4个基于中心的簇聚类的复杂性簇类型基于图的簇可以定义为连通分支（connectedcomponent）互相连通但不与组外对象连通的对象组。基于近邻的（Contiguity-Based）其中两个对象是相连的，仅当它们的距离在指定的范围内。这意味着，每个对象到该簇某个对象的距离比到不同簇中任意点的距离更近。8个“连通”簇图论的图！如果数据用图表示，其中节点是对象，而边代表对象之间的联系。聚类的复杂性簇类型基于密度的(Density-Based)簇是对象的稠密区域，被低密度的区域环绕。6个基于密度的簇聚类的复杂性簇类型基于密度的(Density-Based)簇是对象的稠密区域，被低密度的区域环绕。基于密度的簇聚类的复杂性簇类型概念簇(ConceptualClusters)可以把簇定义为有某种共同性质的对象的集合。例如：基于中心的聚类。还有一些簇的共同性质需要更复杂的算法才能识别出来。2个交叠簇聚类的复杂性分为几个簇?分为4个簇分为2个簇分为6个簇聚类算法分类聚类算法K均值，k-medoids及其扩展算法层次聚类算法基于密度的聚类基于网络的聚类其他聚类算法划分聚类算法CLARA，CLARANSCURE算法，ROCK算法BIRCH算法等DBSCAN算法GDBSCAN，DBCLASD算法OPTICS算法FDC算法BANG算法WaveCluster算法STING算法聚类算法分类按分类方法划分聚类聚类算法分类按分类方法划分聚类层次聚类聚类算法分类按分类方法划分聚类层次聚类基于密度的聚类聚类算法分类按划分方法分类互斥聚类聚类算法分类按划分方法分类互斥聚类非互斥聚类聚类算法分类按划分方法分类互斥聚类非互斥聚类模糊聚类聚类算法分类按划分范围分类完全聚类(completeClustering)部分聚类(partialClustering)“距离”度量聚类的实质是“近朱者赤近墨者黑”定义距离函数，基于属性值进行计算非负性对于任意x，y，两者之间的距离d(x，y)≥0，当x

=y时，等号成立。对称性对于任意x，y，两者之间的距离d(x，y)=d(y，x)，即距离是标量而不是向量。三角不等式对于任意x，y，z，有d(x，y)

≤d(x，z)+d(z，y)。即对象x到对象y的距离小于等于途经其他任何对象z的距离之和。？怎样才算近？也称为相似性“距离”度量欧几里得距离EuclideanDistance对于n维数据

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其欧几里得距离为在二维空间中的欧几里得距离就是平面中两点之间的实际距离。在三维空间中的欧几里得距离就是立体（三维）空间中两点之间的实际距离。“距离”度量曼哈顿距离对于n维数据

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其曼哈顿距离为(6,6)(2,2)欧几里得距离=5.66曼哈顿距离=(6-2)+(6-2)=844xy“距离”度量明可夫斯基距离MinkowskiDistance对于n维数据

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其明可夫斯基距离为相似系数余弦相似度对于n维数据

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，即对于x，y两个向量，有：cos(x,y)=(x·y)/‖x‖·‖y‖

余弦相似度【例如】分析以下两个句子的相似性：

句子A：我喜欢看电视，不喜欢看电影。句子B：我不喜欢看电视，也不喜欢看电影。1)可以将两个句子进行分词：句子A：我/喜欢/看电视/不/喜欢/看/电影句子B：我/不/喜欢/看/电视/也/不/喜欢/看/电影2)对所出现的各个词汇（我

喜欢

看

电视

电影

不

也），计算其词频：句子A：我1，喜欢2，看2，电视1，电影1，不1，也0句子B：我1，喜欢2，看2，电视1，电影1，不2，也1余弦相似度【例如】分析以下两个句子的相似性：

句子A：我喜欢看电视，不喜欢看电影。句子B：我不喜欢看电视，也不喜欢看电影。3)将词频转换为向量：句子A：x=(1221110)句子B：y=(1221121)4)计算其余弦相似度，有：余弦相似度由此，我们就得到了“找出相似文章”的一种算法：使用TF-IDF算法，找出两篇文章的关键词；每篇文章各取出若干个关键词（比如20个），合并成一个集合，计算每篇文章对于这个集合中的词的词频（为了避免文章长度的差异，可以使用相对词频）；生成两篇文章各自的词频向量；计算两个向量的余弦相似度，值越大就表示越相似。相似系数余弦相似度相关系数反映变量之间相关关系密切程度的统计指标相关系数按积差的方法计算，以两变量与各自平均值的离差为基础，通过两个离差相乘来反映两变量之间相关程度。x与y之间的协方差x,y的均方差相似系数余弦相似度相关系数Jaccard相似系数(JaccardSimilarityCoefficient)用于比较有限样本集之间的相似性与差异性A、B的相似性：Jaccard距离：余弦相似度TF-IDF算法TF-IDF通过统计方法，对字词对于语料库中的一份文件或文件集的重要程度进行评估。字词的重要性随其在文件中出现的次数正比增加，随其在语料库中出现的频率成反比下降，即如果某字在一篇文章中出现的频率TF高，而在其他文章中很少出现，则认为该字词具有很好的类别区分能力，适合用于分类。这里TF为词频(TermFrequency)，表示词条在文档d中出现的频率；IDF为逆向文件频率(InverseDocumentFrequency)，表示包含词条的文档的数量，值越大，表明词条具有很好的类别区分能力。TF-IDF加权的各种形式常被搜索引擎应用，作为文件与用户查询之间相关程度的度量或评级。除了TF-IDF以外，因特网上的搜索引擎还会使用基于链接分析的评级方法，以确定文件在搜寻结果中出现的顺序。误差平方和(SSE)在对两组数据的误差情况进行估计的时候，如原始数据和拟合数据之间的误差，或者是理论数据和观测数据之间的误差，会用其误差值取平方后求和来衡量误差的大小。计算公式为：

误差平方和(SSE）误差平方和（sumofthesquarederror）它可以度量聚类的质量。误差平方和越小，意味着质心是簇中点的更好代表。误差平方和(SSE）可以证明：当紧邻函数是欧式距离(L2)时，使簇的SSE最小的质心是均值，即【证明】当紧邻函数是欧式距离时，

可对SSE求导误差平方和(SSE）可以证明：当紧邻函数是曼哈顿距离(L1)时，使簇的L1绝对误差和(SAE)最小的质心是中位数第7章聚类分析K均值(K-Means)聚类方法算法原理属于划分聚类分割方法基本思想：给定一个具有n个数据元素的数据集，通过分割的方法对其进行划分，构造k个分组(k<n)，每一个分组即为一个聚类。满足下列条件：①每一个分组至少包含一个数据元素；②每一个数据元素属于且仅属于一个分组。也称为簇40算法原理基本思想：给定一个具有n个数据元素的数据集，通过分割的方法对其进行划分，构造k个分组(k<n)，每一个分组即为一个聚类。41算法认为，聚类后得到的簇，应由较为相似的对象组成，因此算法将得到紧凑且独立的簇作为算法的过程和目标。算法原理42k=3

，?

任意划分3个簇紧凑更靠近簇质心计算质心指派对象计算质心指派对象反复迭代随机指派质心K-means选择初始质心将数据点指派到初始质心（SSE=305）第1次迭代：重新计算质心，并将数据点指派到质心（SSE=268）第2次迭代：重新计算质心并指派到质心(SSE=264)第3次，重新计算质心并指派.最终结果(SSE=262)第4次，质心不再变化，得到最终结果(SSE=262)迭代终止条件：质心不再变化；或2)SSE不再变优。SSE–目标函数聚类就是使目标函数最优的过程。43[例]基本过程例中，二维数据距离：欧几里得距离计算质心点坐标：指定到同一个簇的数据点(x、y

)坐标平均值44算法过程对于给定的k，指定初始质心，完成初始聚类，并通过反复迭代的方法对聚类结果进行调整，使得每次调整后的聚类结果均比前一次好。“好”，是指簇的内聚性大，簇间的耦合性小。通常会用设置一个指标来进行衡量。将数据元素指派给相距“距离”最小的簇，簇的代表为质心。45基本算法过程46选择适当的初始质心是基本K-Means算法的关键步骤。选择不同的质心，聚类的结果也有所不同。

如何选择初始质心？【算法】K-means聚类算法1：选择k个点作为初始的质心2：repeat3：将每个点指派到最近的质心，形成k个簇4：重新计算每个簇的质心5：until质心不发生变化基本算法过程1.随机选择质心【算法】K-means聚类算法1：选择k个点作为初始的质心2：repeat3：将每个点指派到最近的质心，形成k个簇4：重新计算每个簇的质心5：until质心不发生变化47基本算法过程48基本算法过程SSE较大49基本算法过程1.随机选择质心随机地指定k个点作为初始质心点，但是簇的质量常常不高。【算法】K-means聚类算法1：选择k个点作为初始的质心2：repeat3：将每个点指派到最近的质心，形成k个簇4：重新计算每个簇的质心5：until质心不发生变化50基本算法过程对于非监督的聚类，初始质心点的个数k也是决定聚类结果的关键因素簇的数量越多，SSE会达到更小51(a)选择初始质心(SSE=3555)……(b)第2次迭代(SSE=2154)(c)最终结果(SSE=1828)k

=4基本算法过程1.随机选择质心随机地指定k个点作为初始质心点，但是簇的质量常常不高。2.最小误差平方和SSE法多次运行，每次使用一组不同的随机初始质心，然后选取具有最小SSE（误差的平方和）的簇集。【算法】K-means聚类算法1：选择k个点作为初始的质心2：repeat3：将每个点指派到最近的质心，形成k个簇4：重新计算每个簇的质心5：until质心不发生变化52基本算法过程1.随机选择质心2.最小误差平方和SSE法3.层次聚类法使用层次聚类技术对样本进行聚类，从聚类结果中提取k个簇，并以这些簇的质心为初始质心。方法通常很有效，但仅限于样本相对较小（层次聚类开销较大）而且k相对于样本大小较小的情况。【算法】K-means聚类算法1：选择k个点作为初始的质心2：repeat3：将每个点指派到最近的质心，形成k个簇4：重新计算每个簇的质心5：until质心不发生变化53基本算法过程1.随机选择质心2.最小误差平方和SSE法3.层次聚类法4.离散质心法①随机地选择或选取所有点的质心作为第一个初始质心。②

每个后继初始质心，选择离已经选取过的初始质心最远的点。确保选择的初始质心不仅是随机的，且是散开的。可能选中离群点，且求离当前初始质心集最远的点开销也非常大。【算法】K-means聚类算法1：选择k个点作为初始的质心2：repeat3：将每个点指派到最近的质心，形成k个簇4：重新计算每个簇的质心5：until质心不发生变化54基本算法过程55准则：迭代次数达到一定次数质心的变化距离<ε【算法】K-means聚类算法1：选择k个点作为初始的质心2：repeat3：将每个点指派到最近的质心，形成k个簇4：重新计算每个簇的质心5：until质心不发生变化基本算法过程变化：二分k均值算法是基本k均值算法的直接扩充。步骤：将所有点的集合分裂成两个簇从现有簇中选取一个继续分裂重复步骤②此下去，

直到产生k

个簇56初始化簇表，包含由所有的点组成的簇repeat

从簇表中取出一个簇

for

i=1to

n(实验次数)

do

使用基本k均值，二分选定的簇

end

for

选择n个结果中总SSE最小的二分簇将这两个簇添加到簇表中until

簇表中包含k个簇。算法特点对

k值较为敏感k=2k=4k=3k=4不同的距离初始值对同样的数据样本可能得到不同的结果事先判断簇的划分个数非常困难并往往带有很大的随意性57算法特点对离群点、噪声敏感有离群点k=2离群点导致：SSE高，质心代表性变差如何识别、如何处理58算法特点对离群点、噪声敏感无离散点的聚类迭代过程有离散点的聚类迭代过程59算法特点不能处理非球形簇原始数据k=2k=4k=360算法特点不能处理不同尺寸的簇k=2k=461算法特点不能处理不同尺寸的簇k=3k=462算法特点不能处理不同密度的簇原始数据K=263算法特点计算开销大需要迭代进行数据点之间的邻近度计算，以调整质心并指派到簇。当数据量较大时，算法的时间开销非常大算法简单，易于理解二分k均值等变种算法运行良好，不受初始化问题的影响64一些问题空簇所有的点在指派时都没有分配到某簇，就会得到空簇解决：选择一个替补质心找一个距当前任何质心最远的点从最大SSE簇中选一个替补质心，继续分裂簇，降低SSE65一些问题后处理降低簇SSE进一步分裂簇（选SSE最大的簇）引进一个新的质心（选离所有簇质心最远的点）拆散一个簇（删除其质心，重新指派其中的点）合并两个簇增量地更新质心在点到簇的每次指派后，增量地更新质心，而不是在所有的点都指派到簇中之后才更新质心66应用要点在考虑这些因素的情况下，K-Means聚类算法往往会非常复杂且运算开销巨大需要领域、行业、业务方面的知识67小结K-Means算法较为简单清晰高维数据的应用上，需要做相应的调整在相似度度量确定的情况下，k是唯一的算法参数，也非常关键68第7章分类预测3.

K中心点算法背景K-means算法对噪声数据点较为敏感，在前面的例子中的结果说明了这一点。包含离散点数据的质心有较大偏差，造成簇质心点的偏移，在下一轮迭代重新划分样本点的时候，会纳入一定量不属于该簇的样本点，得到不准确的聚类结果。70算法K-medoids算法在计算新质心点时，并非如K-means算法中简单地采用均值计算法，而是在每次迭代后，均从聚类的样本点中选取质心点，而选取的标准就是当该样本点成为新的质心点后能提高该簇的聚类质量，使得簇更加紧凑。该算法使用绝对误差和来定义一个类簇的紧凑程度71数据分为k个簇，Ci为第i个簇，ci为簇Ci的质心选择质心如果某样本点成为质心点后，绝对误差和小于原质心点的绝对误差和，则认为该样本点可取代原质心点，在迭代重新计算类簇质心点时，选择绝对误差和最小的那个样本点成为新的质心点。72迭代处理与K-means算法一样，K-medoids也采用欧几里得距离来衡量样本点到质心点的距离。终止条件是，当所有的簇的质心点都不再发生变化时，即认为聚类结束。73优劣该算法改善了K-means算法对噪声点敏感的问题，但由于新质心点计算规则改变，算法的时间复杂度也有所上升。74K-medoids聚类算法可以一定程度上消除噪声点的影响第7章聚类分析层次聚类层次聚类层次聚类(HierarchicalClustering)，即按照一定的规则，对给定的数据集进行分层次的聚集或分解，直到满足某种事先设定的条件。按聚类的次序：凝聚的层次聚类分裂的层次聚类凝聚的层次聚类a,b,c,d,ec,d,ed,ea,bedcba第4步第3步第2步第1步第0步凝聚的（AGENS）凝聚的层次聚类采用自底向上的策略，开始时把每个对象作为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。分裂的层次聚类a,b,c,d,ec,d,ed,ea,bedcba第0步第1步第2步第3步第4步分裂的（DIANA）分裂的层次聚类采用自顶向下的策略，与凝聚的层次聚类相反，开始时将所有对象置于同一个簇中，然后逐次将簇分裂为更小的簇，直到满足某个终止条件。层次聚类按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。13254600.050.10.150.2基本凝聚层次聚类方法凝聚层次聚类算法计算邻近度矩阵让每个点作为一个ClusterRepeat

合并最近的两个类

更新邻近度矩阵，以反映新的簇与原来的簇之间的邻近性Until仅剩下一个簇

传统的算法利用相似性或相异性的邻近度矩阵进行凝聚的或分裂的层次聚类关键的操作是2个簇的邻近度计算不同的邻近度的定义区分了各种不同的凝聚层次技术[例1]1.将每单个数据聚为一个簇；p7p12p3p9p5p1p8p10p11p2p6p4p7p12p3p9p5p1p8p10p11p2p6p4

xyp11310p21411p3165p41822p51817p6194p72122p8307p9314p103420p113515p123622[例]2.将最邻近的两个簇聚为一个簇；1.将每单个数据聚为一个簇；

xyp11310p21411p3165p41822p51817p6194p72122p8307p9314p103420p113515p123622p1p2p3p6p4p7p5p8p9p10p12p11C1,2C3,6C4,7C8,9C10,12p10p3p7p5p4p9p8p6p11p12p1p2p1p2p3p6p4p7p5p8p9p10p12p11C1,2C3,6C4,7C8,9C10,12C1,2,3,6C4,7,5C10,12,11p10p3p7p5p4p9p8p6p11p12p1p2p1p2p3p6p4p7p5p8p9p10p12p11C1,2C3,6C4,7C8,9C10,12C1,2,3,6C4,7,5C10,12,11C1,2,3,6,4,7,5C8,9,10,12,11C1,2,3,6,4,7,5,8,9,10,12,11p10p3p7p5p4p9p8p6p11p12p1p2[例2]2.将最邻近的两个簇聚为一个簇；1.将每单个数据聚为一个簇；ptxyp11822p22122p31817p43622p53420p63515p71411p81310p9165p10194p11307p12314改进的算法充分利用邻近度矩阵进行聚类？示例2.将最邻近的两个簇聚为一个簇；1.将每单个数据聚为一个簇；ptxyp11822p22122p31817p43622p53420p63515p71411p81310p9165p10194p11307p123143.迭代进行，直至聚类为一个簇。示例ptxyp11822p22122p31817p43622p53420p63515p71411p81310p9165p10194p11307p12314示例ptxyp11822p22122p31817p43622p53420p63515p71411p81310p9165p10194p11307p12314示例ptxyp11822p22122p31817p43622p53420p63515p71411p81310p9165p10194p11307p12314Cluster间的相似性相似性？p3p6p4p1p2p5MIN（单链）MAX（全链）GroupAverage组平均DistanceBetweenCentroids质心距ObjectiveFunction目标函数类Cluster间的相似性MINp3p6p4p1p2p5MIN（单链）两个Cluster的相似性定义为基于

这两个Cluster中最大相似度（最近距离）由一对最近邻点决定p1p2p5p4p3p6p1

p215.6

p518.4

p42613.320.6

p3169.818.410.8

p620.61725.613

p2p5p3p6p4p1dist({3,6},{2,5})=min(dist(3,2),dist(3,5),dist(6,2),dist(6,5))

=min(9.8,18.4,17,25.6)

=9.8Cluster间的相似性MIN（单链）p2p5p3p6p4p1p1p2p3p5p6p4p1p4p2p5p3p6p1

p426

p215.613.3

p518.420.6

p31610.8

p620.613

p1p4p2p5p3p6p1

p426

p215.6

p518.4

p316

p620.6

Cluster间的相似性MIN（单链）单链技术可以处理非椭圆形状的簇Cluster间的相似性MIN（单链）单链技术可以处理非椭圆形状的簇但对噪音和离群点很敏感Cluster间的相似性MAXp3p6p4p1p2p5MAX（全链）两个Cluster的相似性定义为基于

这两个Cluster中最小相似度（最远距离）由一对最远离点决定p1p2p5p4p3p6p1

p215.6

p518.4

p42613.320.6

p3169.818.410.8

p620.61725.613

p2p5p3p6p4p1dist({3,6},{2,5})=max(dist(3,2),dist(3,5),dist(6,2),dist(6,5))

=min(9.8,18.4,17,25.6)=25.6Cluster间的相似性MAX（全链）p2p5p3p6p4p1p1p2p3p5p6p4p1p2p5p4p3p6p1

p215.6

p518.4

p42613.320.6

p3169.818.4

p620.61725.6

p1p2p5p4p3p6p1

p2

p5

p42613.320.6

p3169.818.4

p620.61725.6

Cluster间的相似性MAX（全链）对噪音和离群不敏感Cluster间的相似性MAX（全链）对噪音和离群不敏感可能使大的簇破裂，偏好球型簇Cluster间的相似性GroupAverage组平均两个簇的邻近度定义为不同的所有点

对的平均逐对邻近度是一种单链与全链的折中算法p2p5p3p6p4p1p1p2p3p5p6p4组平均Cluster间的相似性GroupAverage组平均两个簇的邻近度定义为不同簇的所有点

对的平均逐对邻近度是一种单链与全链的折中算法p2p5p3p6p4p1p1p2p3p5p6p4p1p2p5p4p3p6p1

p217

p5

p42616.9

p318.317.711.9

p6

组平均Cluster间的相似性GroupAverage组平均p2p5p3p6p4p1p1p2p5p4p3p6p1

p217

p5

p420.917.5

p3

p6

p1p2p5p4p3p6p1

p2

p5

p418.6

p3

p6

p1p2p3p5p6p4Cluster间的相似性GroupAverage组平均对噪音和极端值影响小偏好球型簇Cluster间的相似性DistanceBetweenCentroids质心距两个簇的邻近度定义为不同簇的质心

的邻近度p2p5p3p6p4p1p1p2p3p5p6p4质心距p1p2,5p4p3,6p1

p2,516.5

p42616.8

p3,618.117.711.4

Cluster间的相似性DistanceBetweenCentroids质心距两个簇的邻近度定义为不同簇的质心

的邻近度p2p5p3p6p4p1p1p2,5p4,3,6p1

p2,516.51

p4,3,620.3616.54

p1p2p3p5p6p4p1,2,5p4,3,6p1,2,5

p4,3,616.12Cluster间的相似性ObjectiveFunction目标函数类Ward算法两个簇的邻近度定义为两个簇合并时导致的平方误差的增量p2p5p3p6p4p1p1p2p3p5p6p4C1C2SSEp1p27.8p1p38.0p1p413.0p1p59.2p1p610.3p2p34.9p2p46.7p2p54.3p2p68.5p3p45.4p3p59.2p3p63.6p4p66.5p4p510.3p5p612.8C1C2SSEp1p27.8p1p3,69.1p1p413.0p1p59.2p2p3,66.7p2p46.7p2P54.3p4p3,65.7p4p510.3p5p3,611.0C1C2SSEp1p2,58.3p1p3,69.1p1p413.0p2,5p3,68.8p3,6p2,58.8p4p3,65.7p4p2,58.4C1C2SSEp1p2,58.3p1p4,3,610.2p2,5p4,3,68.3C1C2SSEp1,2,5p4,3,68.1Cluster间的相似性ObjectiveFunction目标函数类Ward算法两个簇的邻近度定义为两个簇合并时导致的平方误差增量当邻近度取它们之间的平方时，ward与组平均类似噪音和极端值影响小偏好球型簇Cluster间的相似性MIN单链MAX全链组平均Wardp1p2p3p5p6p4p1p2p3p5p6p4p1p2p3p5p6p4质心距p1p2p3p5p6p4p1p2p3p5p6p4Cluster间的相似性Lance-Willianms公式CiCjCkCm#G.N.LanceandW.T.Williams.AGeneralTheoryofClassificatorySortingStrategies:1.HierarchicalSystems.TheComputerJournal,9(4):373–380,February1967.算法特点优点：某些应用领域需要层次结构。如：系统发生树，基因芯片有些研究表明，这种算法能够产生较高质量的聚类系统发生树算法特点优点：某些应用领域需要层次结构。如：系统发生树，基因芯片有些研究表明，这种算法能够产生较高质量的聚类系统发生树算法特点优点：某些应用领域需要层次结构。如：系统发生树，基因芯片有些研究表明，这种算法能够产生较高质量的聚类基因芯片算法特点优点：某些应用领域需要层次结构。如：系统发生树，基因芯片有些研究表明，这种算法能够产生较高质量的聚类缺点：计算量、存储量大对噪声、高维数据敏感小结层次聚类的关键点在于簇的相似度衡量方法计算效率第7章聚类分析DBSCANDBSCAN算法将具有足够密度的区域划分为簇，并在具有噪声点的空间数据中发现任意形状的簇，它将簇定义为以一定密度相连的点的最大集合简单有效Density-BasedSpatialClusteringofApplicationwithNoise基于密度的空间聚类方法具有噪声点的数据DBSCAN算法足够密度单位区域内数据点个数不小于给定阈值相连这些“密度足够”的区域是

连通的基本概念邻域与某被考察点的距离小于给定的阈值Eps的空间范围。Eps是用户指定的参数AEps距离基本概念邻域核心点minPts=6Eps=0.5EpsA给定邻域内的点的个数超过给定的阈值minPts为核心点。minPts是用户指定的参数核心点core基本概念邻域核心点边界点minPts=6，Eps=0.5

EpsA落在某一核心点的邻域内（也可能落在多个核心点的邻域内），但因其邻域内的点数未达到阈值minPts而不能成为核心点的点。核心点core边界点border基本概念邻域核心点边界点噪声点噪声点：既非核心点也非边界点的点。噪声点noiseminPts=6，Eps=0.5

EpsA核心点core边界点borderDBSCAN算法是一种“基于中心的DBSCAN”在基于中心的方法中，数据集中特定点的密度通过对该点Eps半径之内的点计数（包括点本身）来估计该方法实现简单，但是点的密度依赖于指定的半径。如果半径足够大，则所有点的密度都等于数据集中的点数m。如果半径太小，则所有点的密度都是1。【算法】DBSCAN算法1:给定邻域阈值Eps和核心点的个数阈值minPts；2:标记核心点；3:标记边界点；4:标记噪声点；5:删除噪声点；6:为距离在Eps之内的所有核心点之间赋予一条边进行相连；7:每组连通的核心点形成一个簇；8:将每个边界点指派到一个与之关联的核心点的簇中。DBSCAN算法将距离在Eps范围内的，邻域点个数满足minPts的点标记为核心点对于任一非核心点，若Eps范围内有核心点，则标记为边界点其余点标记为噪声点DBSCAN算法【算法】DBSCAN算法1:给定邻域阈值Eps和核心点的个数阈值minPts；2:标记核心点；3:标记边界点；4:标记噪声点；5:删除噪声点；6:为距离在Eps之内的所有核心点之间赋予一条边进行相连；7:每组连通的核心点形成一个簇；8:将每个边界点指派到一个与之关联的核心点的簇中。任意两个足够靠近（互相之间的距离在Eps之内）的核心点将放在同一个簇中任何与核心点足够靠近的边界点也放到该核心点的簇中。（如果一个边界点靠近不同簇的核心点，要解决平局问题）噪声点被丢弃形成簇如果两个核心点的距离在Eps之内，则可以将其用一条边进行相连，这样的两个核心点被称为是密度相连的形成簇如果两个核心点，通过密度相连的核心点可以相互连接，则称这两个核心点是密度连通的选择Eps和MinPts基本方法是观察点到它的k个最近邻的距离(称为k-距离)的特性。计算所有点的k-距离，以递增次序将它们排序，然后绘制排序后的值，则预期会看到k-距离的急剧变化，对应于合适的Eps值。如果选取该距离为Eps参数，而取k的值为MinPts参数。DBSCAN算法：选择Eps和MinPts【例】dist=9Eps=?MinPts=?DBSCAN算法：选择Eps和MinPts【例】DBSCAN算法：选择Eps和MinPts【例】DBSCAN算法：选择Eps和MinPts【例】核心点,边界点,噪声点Eps=10,MinPts=4【例】Excel计算聚类【例】Excel计算聚类【例】Excel计算聚类Eps=2.4，minPts=5【例】Excel计算聚类Eps=2.75，minPts=5DBSCAN算法特点对噪声数据不敏感能够处理任意形状的簇能够处理任意大小的簇可以发现使用Kmeans算法不能发现的簇DBSCAN算法特点变密度的簇(MinPts=4,Eps=9.75)

(MinPts=4,Eps=9.92)DBSCAN算法特点变密度的簇如果簇的密度变化很大，DBSCAN可能会有问题。ClusterBClusterA簇和噪声区域的密度由它们的明暗度表示，簇A密度较高，簇A周围密度较低，且与簇B的密度相同，簇B周围密度最低。如果Eps域值足够低，可以发现簇B，则A及其周围点将变成单个簇。如果Eps域值足够高，可以发现A，A及其周围的点则标记为噪声，B及其周围的点也将标记为噪声。DBSCAN算法特点变密度的簇对于高维数据，较难定义数据的密度，算法应用也会有问题开销较大DBSCAN算法需要访问数据集中所有的样本，有些样本还可能需要多次访问（如确定边界点时），因此算法的时间复杂度主要取决于空间查询（即获取某个样本点的Eps邻域）时的运算次数。DBSCAN算法复杂度

小结DBSCAN是基于空间密度的聚类算法核心参数为Eps和MinPts对噪声、形状、大小不敏感第7章聚类分析聚类算法评估评估聚类算法评估聚类结果评估聚类算法评估可伸缩性处理不同字段类型的能力处理任意形状的数据集领域知识运用最小化(决定输入参数时)处理高维数据的能力处理噪声点数据的能力对数据顺序的不敏感性可解释性和可用性算法是否适用于大数据量，算法的效率是否满足大数据量高复杂性的要求是否能够应付不同的数据类型，能否处理符号属性是否能发现不同类型的聚类是否能应付脏数据或异常数据聚类结果评估簇评估、簇确认ClusterValidity内容比较两个簇的特性比较不同的算法、参数的得到的两组簇通过比较两组簇来比较聚类算法避免得到的簇是来自噪声数据的簇评估：簇评估非监督监督的相对的凝聚性分离性已知分类，对聚类结果进行检验和评估准确率、精度、召回率、F度量不同聚类方法的比较SSEvs.熵内聚度与分离度簇相似度通常以簇中两两数据元素的相似度之和来衡量，称之为内聚度。对于一个簇，希望其中元素具有最大的相似度。衡量分离程度的指标分离度，定义为分