第八章聚类分析ppt课件.ppt

《第八章聚类分析ppt课件.ppt》由会员分享，可在线阅读，更多相关《第八章聚类分析ppt课件.ppt（142页珍藏版）》请在三一办公上搜索。

1、数据挖掘,主讲：王名扬信息与计算机工程学院,2,引 言要挖掘知识的类型,概念描述：特征化和比较； 关联规则； 分类/预测； 聚类分析；其他的数据挖掘任务。,俗语说：“物以类聚，人以群分”。如，要想把中国的县分成若干类，就有很多种划分方法：可考虑降水、土地、日照、湿度等各方面；可考虑收入、教育水准、医疗条件、基础设施等指标；既可以用某一项来分类，也可以同时考虑多项指标来分类。 再如：同学间的交往（家庭情况、性格、学习成绩、业余爱好等）,引 言,聚类与分类的区别,聚类：是对组的数目或者组的结构不用做任何假设的一种发现项目（或者变量）的自然分组方法（定义）； 必须先建立一个定量的尺度，借以量度对象之

2、间的联系；无（教师）监督的学习方法；观察式学习。分类：依赖于事先确定的数据类别，以及标有数据类别的学习训练样本集合。组的数目已知，目标是将一个新的对象分派给这些组之一；有（教师）监督的学习方法；示例式学习。,第 7 章,聚类分析,第 7 章,7.1 什么是聚类分析？7.2 距离和相似系数7.3 类的定义和类间距离7.4 基于划分的聚类方法7.5 基于层次的聚类方法7.6 基于密度的聚类方法,7,学习目的,掌握各种距离的计算方法。 掌握聚类的常用方法。,7.1 什么是聚类分析,聚类(Clustering)：根据“物以类聚”的道理，对样品和指标进行分类的一种多元统计分析方法；聚类分析中“类”的特征

3、： 聚类所说的类不是事先给定的，而是根据数据的相似性和距离来划分；聚类的数目和结构都没有事先假定。,9,聚类准则对聚类结果的影响,距离测度对聚类结果的影响,数据的粗聚类是两类,细聚类为4类,聚类分析无处不在,挖掘有价值的客户，并制定相应的促销策略：如，对经常购买酸奶的客户； 对累计消费达到12个月的老客户。 针对潜在客户派发广告，比在大街上乱发传单命中率更高，成本更低。,聚类分析无处不在,谁是银行卡的黄金客户？： 利用储蓄额、刷卡消费金额、诚信度等变量对客户分类，找出“黄金客户”！； 这样银行可以： 制定更吸引客户的服务，留住客户，如： 一定额度和期限的免息透资服务； 百盛的贵宾打折卡； 在生

4、日的时候送蛋糕等。,聚类分析无处不在,经济领域： 帮助市场分析人员从客户数据库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征； 谁喜欢打国际长途，在什么时间，打到哪里？ 对住宅区进行聚类，确定自动提款机ATM的安放位置； 股票市场板块分析，找出最具活力的板块龙头股； 企业信用等级分类； 。,聚类分析无处不在,生物学领域： 推导植物和动物的分类； 对基因分类，获得对种群的认识； 。数据挖掘领域： 作为其他数学算法的预处理步骤，获得数据分布状况，集中对特定的类做进一步研究。,聚类分析,聚类分析的目的是寻找数据中：潜在的自然分组结构 (structure of natural group

5、ing)。 感兴趣的关系 relationship,聚类分析,什么是自然分组结构？看一下的例子：现有16张扑克牌，问如何将它们进行分组？,聚类分析,按照花色是否相同：分成四组；组与组之间花色相异。,聚类分析,按照符号是否相同：分成四组；符号相同的牌为一组。,聚类分析,按照颜色是否相同：分成两组；颜色相同的牌为一组。,聚类分析,该例子告诉我们：分组的意义在于我们怎样定义并度量“相似性”？因此衍生出一系列度量相似性的方法。,聚类分析的原则：同一个组内的数据对象具有较高的相似度； 而不同组中的数据对象是不相似的。,7.2 距离和相似系数,相似性（Similar）的度量（统计学角度）：1） Q型聚类：

6、对样本进行聚类（行聚类）常用的距离有：只适用于度量数值型变量（间隔尺度变量）明可夫斯基距离（包括欧氏距离、切比雪夫距离、曼哈顿距离）；马氏距离；其他距离。2）R型聚类：对变量进行聚类（列聚类）；用变量之间的相似系数来度量距离。,7.2 距离和相似系数,一、Q型聚类（对样本聚类）,距离：测度样本之间的亲疏程度；将每一个样本看作p 维空间的一个点，并用某种度量测量点与点之间的距离，距离较近的归为一类，距离较远的点应属于不同的类。,距离的意义,样本资料矩阵,样本资料矩阵,设：,定义距离的准则,定义第i个和第j个样本间的距离要求满足如下四个条件（距离可以自己定义，只要满足距离的条件）：,(1)即距离是

7、一个非负的数值 (2)自身的距离为0 (3)即距离函数具有对称性 (4)即距离函数满足三角不等式,距离矩阵,样品间距离矩阵：,变量的类型,变量按测量尺度的不同可以分为以下三类：*间隔(Interval)尺度变量（数值型变量） 用连续的数量来度量，如长度、重量、速度、温度等有序(ordinal)尺度变量（序数型变量） 有次序关系，不可加，但可比，如一等、二等、三等奖学金名义(Norminal)尺度变量（名义型变量）类别变量，不可加也不可比，如性别中的男与女，职业的分类。,1、间隔尺度变量（数值型变量）,明氏距离,（1）明可夫斯基距离,设原始数据为,第七章：,明氏距离,当k2时，即为欧氏距离：,当

8、k时，即为切比雪夫距离：,特别地，当k1时，即为曼哈顿（绝对值）距离：,欧氏距离,切比雪夫距离,明可夫斯基距离的缺点：,当各变量的测量值相差悬殊时，常发生“大数吃小数”的现象，为消除这种现象带来的影响，通常先将每个变量进行标准化。,35,示例：,另外，明氏距离的数值与指标的量纲有关。如，二维样本（身高、体重），有三个样本：a(180,50); b(190,50); c(180,60) 则a与b之间的明氏距离（欧氏距离、切比雪夫距离）等于a与c之间的距离但问题是，身高的10cm真的等价于体重的10kg吗？因此，明氏距离无法消除量纲的影响，在衡量这类样本的相似度时容易出现问题。,36,示例：,另外

9、，即使是同一个变量，选用的度量单位的不同，也将直接影响聚类分析的结果：如：将高度的度量单位由“米”变为“英尺”，或将重量的单位由“千克”变为“英镑”，可能会产生非常不同的聚类结构。一般，度量单位越小，变量可能的值域越大，对聚类结果的影响也越大。因此，为避免对度量单位选择的依赖，数据应当标准化。,37,度量值的标准化,一种方法是将初始测量值转换为无单位变量。给定一个属性变量f，可用如下公式对其进行标准化：（1）计算标准差,标准差描述的是变量的各个取值到均值的距离之平均，反映的是数值分布的离散度。标准差越大，数值越分散；反之，标准差越小，数值越集中。,（2）计算标准化测量（z-score）：,，而

10、,经过标准化变换处理后，每个变量的平均值为0，方差为1，且也不再具有量纲，这便于不同变量之间的比较。接下来就可以用前面所描述的任意一组距离度量方法进行计算相异度。,度量值的标准化,39,特例：比例数值变量,比例数值变量（比例标度型变量）：一个比例数值变量指在非线性的标度上取正的度量值的变量，如指数比例：,40,在计算比例数值变量所描述对象间的距离时，有两种处理方法：1）将比例数值变量看作区间标度变量，采用相同的方法处理，但不佳，因为比例尺度是非线性的；2）采用对数变换 ，对比例数值变量进行处理，然后将yif当做区间标度变量来处理。,特例：比例数值变量,2、有序(ordinal)尺度变量,42,

11、有序尺度变量,有序尺度变量（顺序变量）：一个离散的顺序变量类似于符号变量，但不同的是顺序变量的M个状态是以有意义的顺序进行排列的。如专业等级是一个顺序变量，是按照助教、讲师、副教授和教授的顺序排列的。一个连续的顺序变量，值的相对位置要比它的实际数值有意义的多，如某个比赛的相对排名（金牌、银牌和铜牌）可能比实际得分更重要。,43,有序尺度变量,有序尺度变量的处理与间隔尺度变量非常类似，假设f是用于描述n个对象的一组顺序变量之一，关于f的距离计算如下：,接下来就可以用间隔尺度变量中所描述的任意一组距离度量方法进行计算相异度。,3、名义尺度变量 （符号变量）,45,名义尺度变量,名义尺度变量（符号变

12、量）：二元变量：只有两个状态：0或者1。其中0代表变量所表示的状态不存在；1则代表相应的状态存在。如：电路的开和关，天气的有雨和无雨，人口性别的男和女，医疗诊断中的“十”和“一”，市场交易中的买和卖等都是此类变量名义变量：是二元变量的推广，可具有多于两个的状态值如颜色变量（红、橙、黄、绿、蓝等）。,46,1）二元变量的相异度计算,差异矩阵法： 如果假设所有的二元变量有相同的权重，则可以得到一个两行两列（2*2）的条件表。,47,二元变量的相异度计算,其中： q表示在对象i和对象j中均取1的二值变量个数； r表示在对象i取1但对象j中取0的二值变量个数； s表示在对象i中取0而在对象j中取1的二

13、值变量个数； t则表示在对象i和对象j中均取0的二值变量个数。 二值变量的总数为p，则：p=q+r+s+t。,48,恒定的相似度,如果一个二值变量取0或1所表示的内容同等价值，且有相同的权重，则该二元变量是对称的。如，属性“性别”，有两个值“女性”和“男性”，两个取值都没有优先权 。基于对称二元变量的相似度，称为恒定的相似度。对恒定相似度而言，评价对象i和j间相异度的最著名的方式是简单匹配系数：,q表示在对象i和对象j中均取1的二值变量个数； r表示在对象i取1但对象j中取0的二值变量个数； s表示在对象i中取0而在对象j中取1的二值变量个数； t则表示在对象i和对象j中均取0的二值变量个数。

14、,49,如果一个二值变量的两个取值的重要性不同等重要，则该二元变量就是不对称的。如一个疾病disease的测试结果positive或negative，显然这两个测试结果的重要性是不一样的： 通常将比较重要的输出结果，编码为1；而将另一结果编码为0. 基于这样的二元变量的相似度被称为非恒定的相似度.,非恒定的相似度,50,对非恒定相似度，最常见的描述对象i和对象j间差异度的参数是Jaccard相关系数：,在计算过程中，负匹配的数目t被认为是不重要的，因此被忽略。,其中，q表示在对象i和对象j中均取1的二值变量个数； r表示在对象i取1但对象j中取0的二值变量个数； s表示在对象i中取0而在对象j

15、中取1的二值变量个数； t则表示在对象i和对象j中均取0的二值变量个数。,非恒定的相似度,51,例：样本Xi和样本Xj都是具有8个二元类型的变量：Xi=0,0,1,1,0,1,0,1Xj=0,1,1,0,0,1,0,0 则，q=2; r=2; s=1; t=3简单匹配系数：d(i, j)=(r+s)/(q+r+s+t)=3/8Jaccard系数：d(i, j)=(r+s)/(q+r+s)=3/5,示例,52,2）名义尺度变量,名义尺度变量（符号变量）：名义尺度变量是二元变量的推广，可具有多于两个的状态值，如颜色变量（红、橙、黄、绿、蓝等）。设一个符号变量所取的状态个数为M，其中的状态可以用字母

16、、符号，或一个整数集合来表示，如1,2,M。此处的整数仅是为方便数据处理而采用的，并不代表任何的特定的顺序。,53,名义尺度变量,54,名义尺度变量,示例：某高校举办一个培训班，从学员的资料中得到这样六个变量：性别（x1）；外语语种（x2）；专业（x3）；职业（x4）；居住处（x5）；学历（x6）。现有两名学员：Y1=（男，英语，统计，非教师，校外，本科）；Y2=（女，英语，金融，教师，校外，本科以下）若记相同状态数为m1，不相同的为m2，则两个学员之间的相异度（距离）：D12=m2/(m1+m2)=4/6=2/3,4. 混合数据类型？,56,混合数据类型,混合数据类型：在实际数据库中，数据对

17、象往往是用复合数据类型来描述的，而且常常包括以上六种数据类型：间隔尺度（数值）变量、比例数值变量、对称二元变量、不对称二元变量、符号变量和顺序变量。如何计算相异度？ 一种方法是将变量按类型分组，对每种类型的变量单独聚类分析，但实际中，往往不可行。 一种更可取的方法是将所有的变量一起处理，只进行一次聚类分析。,57,混合数据类型,一种技术是将不同类型的变量组合在单个相异度矩阵中，把所有有意义的变量转换到共同的值域区间0,1上。假设数据集包含p个不同类型的变量，对象i和j间的相异度d(i,j)定义为：,58,混合数据类型,变量f对i和j直接相异度的计算方式与其具体类型有关：,二、R型聚类（对变量聚

18、类）,相似系数：测度变量之间的亲疏程度；有两种常见的相似系数：夹角余弦；相关系数。,R型聚类,（1）夹角余弦（Cosine）,矢量之间的相似性可用它们的夹角余弦来度量：,另一种形式：,相似矩阵,变量间相似矩阵,（2）相关系数,数据中心化后的矢量夹角余弦：,相似矩阵,研究聚类算法，必须首先给出类的定义和类间距离的计算方法。 类的定义； 类间距离。,7.3 类的定义和类间距离,1、类的定义,类的划分具有人为规定性，这反映在类的定义的选取及参数的选择上。分类结果的优劣最后只能根据实际来评价。定义1 设集合S中任意元素xi与xj间的距离dij有dij h其中h为给定的阈值，称S对于阈值h组成一类。,类

19、的定义,68,思考：,这种定义，适合于哪种分布？答案：团簇状,定义2：设集合S中任意元素xi与xj间的距离dij满足： 则S对于阈值h组成一类。其中k为S中元素的个数。（类内平均距离）,类的定义,思考：,这种定义，适合于哪种分布？答案：仍然是团簇状,定义3：设集合S，对于其中任意一个元素xiS ，都存在xjS，使得二者之间的距离dij h成立，则称S对于阈值h组成一类。,类的定义,思考：,这种定义，适合于哪种分布？答案：长条状,2、类间距离,（一）最近距离(single linkage method)两个聚类k和l之间的最近距离定义为：式中， dij表示 xi k与xj l间的距离。如果l由p

20、和q两类合并而成，则有递推公式：,类间距离,73,最近距离（最小距离）,2022/11/13,74cxt,最短距离：以当前某个样本与已经形成的小类中的各样本距离中的最小值作为当前样本与该小类之间的距离。,例1：为了研究辽宁省5省区某年城镇居民生活消费的分布规律，根据调查资料做类型划分,示 例 1,2022/11/13,75cxt,G1=辽宁，G2=浙江，G3=河南，G4=甘肃，G5=青海采用欧氏距离： d12 =(7.9-7.68)2+(39.77-50.37)2+(8.49-11.35)2+(12.94- 13.3)2+(19.27-19.25)2+(11.05-14.59)2+(2.04-

21、2.75)2+(13.29-14.87)20.5=11.67 d13=13.80 d14=13.12 d15=12.80 d23=24.63 d24=24.06 d25=23.54 d34=2.2 d35=3.51 d45=2.21 1 2 3 4 5D1= 1 0 2 11.67 0 3 13.80 24.63 0 4 13.12 24.06 2.20 0 5 12.80 23.54 3.51 2.21 0,河南与甘肃的距离最近，先将二者（3和4）合为一类G6=G3，G4,2022/11/13,76cxt,d61=d(3,4)1=mind13,d14=13.12 d62=d(3,4)2=mi

22、nd23,d24=24.06d65=d(3,4)5=mind35,d45=2.21 6 1 2 5 6 0D2= 1 13.12 0 2 24.06 11.67 0 5 2.21 12.80 23.54 0d71=d(3,4,5)1=mind13,d14,d15=12.80d72=d(3,4,5)2=mind23,d24,d25=23.54 7 1 2D3= 7 0 1 12.80 0 2 23.54 11.67 0,河南、甘肃与青海并为一新类G7=G6，G5=G3，G4，G5,G8=G1,G2,2022/11/13,77cxt,d78=mind71,d72=12.80 7 8D4= 7 0

23、8 12.8 0河南3甘肃4青海5辽宁1浙江2,（二）最远距离 (complete linkage method)两个聚类k和l之间的最远距离定义为：式中， dij表示 xi k与xj l间的距离。如果l由p和q两类合并而成，则有递推公式：,类间距离,79,最远距离（最大距离）,2022/11/13,80cxt,最远距离：以当前某个样本与已经形成的小类中的各样本距离中的最大值作为当前样本与该小类之间的距离。,例2：对例1的数据以最长距离法聚类。,示 例,2022/11/13,81cxt,d13=13.80 d14=13.12 d15=12.80 d23=24.63 d24=24.06 d25=

24、23.54 d34=2.2 d35=3.51 d45=2.21 1 2 3 4 5D1= 1 0 2 11.67 0 3 13.80 24.63 0 4 13.12 24.06 2.20 0 5 12.80 23.54 3.51 2.21 0d61=d(3,4)1=maxd13,d14=13.80 d62=d(3,4)2=maxd23,d24=24.63 d65=d(3,4)5=maxd35,d45=3.51 6 1 2 5 6 0D2= 1 13.80 0 2 24.63 11.67 0 5 3.51 12.80 23.54 0,河南与甘肃的距离最近，先将二者（3和4）合为一类G6=G2，G

25、4,河南、甘肃与青海并为一新类G7=G6，G5=G3，G4，G5,2022/11/13,82cxt,d71=d(3,4,5)1=maxd13,d14,d15=13.80d72=d(3,4,5)2=maxd23,d24,d25=24.63 7 1 2D3= 7 0 1 13.80 0 2 24.63 11.67 0d78=maxd71,d72=24.63 7 8D4= 7 0 8 24.63 0,G8=G1,G2,（二）平均距离 (average linkage method)两个聚类k和l之间的平均距离定义为：式中， nK和nL分别为类k和l的样品个数，dij为k中的样品i与l中的样品j之间的

26、距离。为所有样本对间的平均距离.,类间距离,84,平均距离法：,类间距离,（四）中间距离 (median method)类与类之间的距离既不取两类最近样品间的距离，也不取两类最远样品间的距离，而是取介于两者中间的距离，称为中间距离法(median method),考虑由Gl、Gp和Gq为边长组成的三角形，取Gl 到GpGq边的中线作为中间距离,类间距离,重心：通常用类中样本的均值代替,87,重心距离法：,7.4 基于划分的聚类方法,大体上，主要的聚类算法可以划分为如下几类：（1）划分方法；（2）层次方法；（3）基于密度的方法；（4）基于网格的方法；（5）基于模型的方法。,89,划分方法,给定一

27、个n个对象或元组的数据库，划分方法构建数据的k个划分，每个划分表示一个聚簇（类），且 。同时满足如下条件：（1）每个聚类内至少包含一个对象；（2）每个对象必须属于且只属于一个聚类。注意：在模糊划分计算中第二个要求可以放宽。一个好的划分的一般准则：在同一个类内的对象间尽可能接近或相似(high intra-class similarity)；不同类中的对象间尽可能远离或不同(low inter-class similarity) 。,90,划分方法,为达到全局最优，基于划分的聚类会要求穷举所有可能的划分，但实际中，绝大多数应用采用了以下两个比较流行的启发式方法：（1）k-均值（k-means）聚

28、类算法：每个聚类用该聚类中对象的平均值来表示；（2）k-中心点（k-mediods） 算法：每个聚类用接近聚类中心的一个对象来表示。,1. k-均值（k-means）聚类算法？,92,K-均值聚类算法,K-均值（k-means）算法是一种得到最广泛应用的聚类算法，它将各个聚类子集内的所有数据样本的均值作为该聚类的代表点；算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。,93,K-均值聚类算法,算法不适合处理离散型属性，但对于连续型属性具有较好的聚类效果。以k为参数，把n个对象分为k个簇，以使簇内对象具有较高的相似度

29、，而簇间的相似度较低。 相似度的计算根据一个簇中对象的平均值（被看作簇的重心）来进行。,94,K-均值聚类算法,95,K-均值聚类算法,算法的基本思想： 首先，随机的选择k个对象，每个对象初始的代表了一个簇的平均值；对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇；然后重新计算每个簇的平均值。 这个过程不断重复，直到准则函数收敛。,96,K-均值聚类算法,通常选择误差平方和最小作为收敛准则函数：,这个准则试图使得生成的结果尽可能地紧凑和独立：当结果簇是密集的，且簇与簇之间区别明显时，算法的效果较好。,97,K-均值聚类算法,该算法有三个要点：1）该算法不适合处理离散型属性 由于该算

30、法不适合处理离散型属性，因此在计算数据样本间的距离时，可根据实际需要选择欧式距离、曼哈顿距离或者明氏距离中的一种作为算法的相似性度量；最常用的是欧式距离。2）选择评价聚类性能的准则函数 算法使用误差平方和准则函数来评价聚类性能。准则公式为：3）相似度的计算根据簇中对象的平均值来进行,98,K-平均聚类算法,算法的特点：只适用于聚类均值有意义的场合，在某些应用中，如：数据集中包含符号属性时，直接应用k-means算法就有问题；用户必须事先指定k的个数；对噪声和孤立点数据敏感，少量的该类数据能够对聚类均值起到很大的影响。,99,示例1,100,示例1,101,示例1,102,示例1,103,示例2

31、,104,示例2,105,示例2,106,示例2,在这个简单的例子里，第一次迭代同时也是最后一次迭代，因为如果继续分析新中心和样本间的距离，得到的簇是一样的，不会将样本重新进行分配，算法停止。,2. k-中心点（k-mediods）聚类算法？,108,K-中心点聚类算法,K-均值聚类算法： 属于划分聚类算法；每个簇用该簇中对象的均值表示；可以是一个虚点；使用误差平方和作为评价准则。K-中心点（k-medians）算法：属于划分聚类算法；每个簇用接近簇中心（均值）的一个对象来表示；是实际存在的点 使用绝对误差作为评价准则。,109,K-中心点聚类算法,基本策略： 首先为每个簇随意选择一个代表对象

32、，称为中心点，剩余的对象根据其与中心点间的距离分配给最近的一个簇。 然后重复地用非中心点对象来替代中心对象，如果它改善了结果聚类的整体距离，则进行替代。 聚类结果的质量用一个代价函数来估算，该函数度量对象与其参照对象之间的平均相异度。,110,K-中心点聚类算法,为判定一个非代表对象 是否是当前代表对象Oj的一个好的替代 ，对于每一个非中心点对象p，考虑如下四种情况：,重新分配给Oi代价函数：Cpjo=d(i,p)-d(j,p),111,K-中心点聚类算法,为判定一个非代表对象 是否是当前代表对象Oj的一个好的替代 ，对于每一个非中心点对象p，考虑如下四种情况：,重新分配给Orandom代价函

33、数：Cpjo=d(o,p)-d(j,p),112,K-中心点聚类算法,为判定一个非代表对象 是否是当前代表对象Oj的一个好的替代 ，对于每一个非中心点对象p，考虑如下四种情况：,不发生变化代价函数：Cpjo=0,113,K-中心点聚类算法,为判定一个非代表对象 是否是当前代表对象Oj的一个好的替代 ，对于每一个非中心点对象p，考虑如下四种情况：,重新分配给Orandom代价函数：Cpjo=d(o,p)-d(p,i),114,K-中心点聚类算法,每当重新分配发生时，替换的总代价是所有非中心对象产生的代价之和：如果总代价是负的，则Oj可被Orandom代替；否则，则认为当前的中心点Oj是可接受的，

34、在本次迭代中没有变化。,115,K-中心点聚类算法,116,两种划分方法的关系,关系：k-中心点方法比k-均值方法更健壮，因为其不易受到极端数据的影响；但k-中心点方法比k-均值方法的执行代价高；两种方法都需要用户提前指定聚类结果的数目k。,9.5 基于层次的聚类方法,大体上，主要的聚类算法可以划分为如下几类：（1）划分方法；（2）层次方法；（3）基于密度的方法；（4）基于网格的方法；（5）基于模型的方法。,118,层次方法,层次方法： 该方法对给定的数据对象集合进行层次分解，根据层次分解的方式，层次的方法被分为凝聚的和分裂的：凝聚层次方法：也称自底向上方法，一开始将每个对象作为单独的一组，然

35、后相继地合并相近的对象或组，直到所有的组合并为一个，或达到某个终止条件，代表：AGNES算法； 分裂层次方法：也称自顶向下方法，一开始所有对象置于一个簇中，在迭代的每一步，一个簇被分裂为更小的簇，直到最终每个对象单独为一个簇，或达到某个终止条件，代表：DIANA算法。,119,120,距离计算方法,AGNES算法,AGNES 算法：最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并，直到达到初始指定的簇数目。,算法9-1 AGNES（自底向上凝聚算法）输入：包含n个对象的数据库，终止条件簇的数目k。输出：k个簇，达到终止条件规定簇数目。(1) 将每个对象当成一个初始簇；(2) RE

36、PEAT(3) 根据两个簇中最近的数据点找到最近的两个簇；(4) 合并两个簇，生成新的簇的集合；(5) UNTIL 达到定义的簇的数目；,122,示 例,AGNES算法,特点：AGNES 算法比较简单，但经常会遇到合并点选择的困难。假如一旦一组对象被合并，下一步的处理将在新生成的簇上进行，已作处理不能撤销，聚类直接也不能交换对象。如果在某一步没有很好的选择合并的决定，则可能会导致低质量的聚类结果。算法的运算复杂度较大，为O(n2)：假定在开始的时候有n个簇，对于第i次迭代，必须在n-i+1个簇中找到最靠近的两个聚类，因此，算法对于n很大的情况是不适用的。,DIANA算法,DIANA 算法：与A

37、GNES算法相反，初始所有节点都在一个大簇中，根据某些准则被一步步地分解，直到达到初始设定的簇数目。聚类过程中，DIANA算法将用到如下两种测度方法：簇的直径：一个簇中的任意两个数据点的距离中的最大值；平均相异度（平均距离）：,DIANA算法,算法9-2 DIANA（自顶向下分裂算法）输入：包含n个对象的数据库，终止条件簇的数目k。输出：k个簇，达到终止条件规定簇数目。（1）将所有对象整个当成一个初始簇；（2） FOR （i=1; ik; i+) DO BEGIN（3） 在所有簇中挑出具有最大直径的簇C；（4） 找出C中与其它点平均相异度最大的一个点p并把p放入splinter group，剩

38、余的放在old party中；（5）. REPEAT（6） 在old party里找出到最近的splinter group中的点的距离不大于到old party中最近点的距离的点，并将该点加入splinter group。（7） UNTIL 没有新的old party的点被分配给splinter group；（8） splinter group和old party为被选中的簇分裂成的两个簇，与其它簇一起组成新的簇集合。（9） END.,126,示例,9.5 基于层次的聚类方法,大体上，主要的聚类算法可以划分为如下几类：（1）划分方法；（2）层次方法；（3）基于密度的方法；（4）基于网格的方法；

39、（5）基于模型的方法。,128,基于密度的聚类方法,密度方法：绝大多数聚类方法基于对象之间的距离进行聚类，这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到了困难。基于密度的方法：只要一个区域中点的密度（对象或数据点的数目）超过某个阈值，就将其加到与之相近的聚类中去。这种方法可以过滤噪声孤立点数据，发现任意形状的簇。代表算法有：DBSCAN、OPTICS、DENCLUE算法等。,129,基于密度的方法：DBSCAN,基于密度的聚类算法。该算法将具有足够高密度的区域划分为簇，并可以在带有噪声的空间数据中发现任意形状的聚类。 在该方法中，簇被定义为密度相连的点的最大集合。 先介绍该方法中涉及到

40、的一些基本的定义。,130,基于密度的方法：DBSCAN,定义 1： 对象的-临域：给定对象在半径内的区域。定义2： 核心对象：如果一个对象的-临域至少包含最小数目MinPts个对象，则称该对象为核心对象。例如，在下图中，设定=1cm，MinPts=5，则q是一个核心对象。,边界点：边界点不是核心点，但落在某个核心点的邻域内；,131,基于密度的方法：DBSCAN,定义 3： 直接密度可达：给定一个对象集合D，如果p是在q的-邻域内，而q是一个核心对象，我们说对象p从对象q出发是直接密度可达的。例如，在下图中，设定=1cm，MinPts=5， q是一个核心对象，对象p从对象q出发是直接密度可达

41、的。,132,基于密度的方法：DBSCAN,定义 4： 密度可达的：如果存在一个对象链p1，p2，pn，p1=q，pn=p，对piD，（1=i=n），pi+1是从pi关于和MitPts直接密度可达的，则对象p是从对象q关于和MinPts密度可达的。,133,基于密度的方法：DBSCAN,定义 5： 密度相连的：如果对象集合D中存在一个对象o，使得对象p和q是从o关于和MinPts密度可达的，那么对象p和q是关于和MinPts密度相连的。例如，在下图中，=1cm，MinPts=5，o是一个核心对象，p1是从o关于和MitPts直接密度可达，p是从p1关于和MitPts直接密度可达，则对象p从对象

42、o关于和MinPts密度可达的；同理，q也是从o关于和MinPts密度可达的，则，称对象p和q是关于和MinPts密度相连的。,134,基于密度的方法：DBSCAN,定义 6： 噪声：一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含在任何簇中的对象被认为是“噪声” 。,135,DBSCAN算法描述,DBSCAN通过检查数据集中每个对象的-邻域来寻找聚类。如果一个点p的-邻域包含多于MinPts个对象，则创建一个p作为核心对象的新簇。然后，DBSCAN反复地寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。,136,DBSCAN算法描述,137,示例,138,示例,距离,139,示例,距离,140,示例,141,示例,Problem： 当MinPts=4时，结果又当如何？,142,基于划分的聚类方法。基于层次的聚类方法？基于密度的聚类方法？,复习与思考问题,