收藏 分销(赏)

聚类(无监督学习)综述.ppt

上传人:仙人****88 文档编号:14774284 上传时间:2026-11-19 格式:PPT 页数:28 大小:288.50KB 下载积分:10 金币
下载 相关
聚类(无监督学习)综述.ppt_第1页
第1页 / 共28页
聚类(无监督学习)综述.ppt_第2页
第2页 / 共28页


点击查看更多>>
资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,聚类(无监督学习)综述,聚类问题的描述(,1,),聚类问题的描述(,2,),聚类问题,:根据给定的数据集,,要求寻找,T,上的一个“好”的划分,(,划分成,m,个类;,m,可以是已知的,也可以是未知的),满足约束条件:,聚类问题的描述(,3,),模糊聚类问题,:根据给定的数据集,,要求寻找,T,上的一个“好”的模糊划分,(,划分成,m,个模糊集),满足约束条件,:,模糊聚类问题可以看成是前面聚类问题(硬聚类)的一个推广,当,u,j,的值域限制为,0,1,时,模糊聚类就是硬聚类,.,聚类问题的要点,样本间的接近度(,Proximity Measures,),聚类评价准则:,“好”的聚类指什么?,聚类算法,聚类有效性检验(统计假设检验),聚类结果解释(结合专家知识),聚类的泛化能力或一致性或抗扰动能力,样本间的接近度度量,差异性度量(,Dissimilarity,Measure,DM,),对称性,自己与自己的相异性最小,例子:距离差异性度量,相似性度量(,Similarity Measure,,,SM,),对称性,自己与自己的相似性最大,例子:高斯径向基函数,常用的接近度度量,点与点之间,点与集合之间,集合与集合之间,点与点之间,DM,点与点之间,SM,点与集合之间,集合与集合之间,聚类评价准则,类内样本间的接近度大,类间样本间的接近度小,主要聚类算法,(1),N,个样本聚为,m,类的可能聚类数,S(N,m,):,S(15,3)=2375101;S(20,4)=45232115901,S(25,8)=690223721118368580;S(100,5),10,68,枚举聚类是行不通的!,主要聚类算法,(2),顺序聚类(,Sequential,Clutering,Algorithms,),分层聚类(,Hierachical,Clutering,Algorithms,),模型聚类(,based on cost function optimization),其他,顺序聚类,最基本的顺序聚类算法,(,1,)第,1,个样本归为第,1,类;,(,2,)计算下一个样本到己有类的最短距离,若其距离小于给定的域值,则将该样本归为其对应的类,否则增加一个新类,并将该样本归为新类。,(,3,)重复(,2,),直到所有样本都被归类。,特点,聚类结果与样本的顺序和给定的域值有关;,聚类速度快,分层聚类,将数据对象按层次进行分解,形成一个分层的嵌套聚类,(,聚类谱系图或聚类树状图,),,可分为,凝聚算法(,Agglomerative Algorithms,),开始将每个对象作为一个类,然后相继地合并上轮中最相近的两个类,直到所有的类合并为一个类或者达到某个终止条件。,分裂算法(,Divisive Algorithms,),开始将所有对象置于一个类中;然后将上轮的每个类按某个准则分裂为两类,在从中选择其中最好的一个分裂,作为该轮的类分裂;直到每个对象都在单独的一个类中或达到某个终止条件。,缺点在于一旦一个合并或分裂完成,就不能撤销,导致分层聚类方法不能更正错误的决定。,分层(凝聚)聚类的一些结论,聚类结果和样本点间距离函数以及类间距离函数的关系:,一般来讲,最短距离法使用于长条状或,S,形的类,最长距离法,重心法,类平均法,离差平方和法适用于椭球型的类。,我们用,Dk,表示第,k,次并类操作时的距离,如果一个系统聚类法能够保证,Di,是单调上升的,那么我们称之为具有单调性。可以证明,最短距离法,最长距离法,类平均法,离差平方和法具有单调性,重心法和中间距离法不具有单调性。从聚类谱系图中可以看出,不具有单调性表现为出现一个凹陷,并且不容易划分类。,分层(凝聚)聚类的一些结论,有人从极端距离矩阵的观点出发,认为相比于其他方法,类平均法既不太浓缩,也不太扩张,比较适中;因而从空间的浓缩和扩张的角度,他们推荐类平均法。,有人证明与初始距离距离矩阵,A,最接近的极端距离矩阵,恰好是使用最短距离法得到的极端距离矩阵,而其他的凝聚型分层聚类法都不具有这个最优性质。从这个角度出发,最短距离法比较受到推崇。,模型聚类,K-means Clustering,K-,中心点聚类,模糊,K-,均值聚类或,ISODATA,K-means Clustering,模型,将,N,个样本,x,1,x,N,划分到,m,个类,C,1,C,m,中,最小化评分函数,这里,c,1,c,m,是,C,1,C,m,的质心,,是划分到类,C,j,的样本,K-means Clustering,实现,随机选择,m,个样本点作为,m,个初始质心,c,1,c,m,;,按距离最近原则,将所有样本划分到以质心,c,1,c,m,为代表的,m,个类中;,重新计算,m,个类的质心,c,1,c,m,;,重复(,2,)和(,3,)直到质心,c,1,c,m,无改变或目标函数,J,(,c,1,c,m,),不减小。,K-means Clustering,特点,优点:,当类密集,且类与类之间区别明显(比如球型聚集)时,聚类效果很好;,强的一致性,算法的复杂度是,O(Nmt)(t,为迭代次数,),,对处理大数据集是高效的。,缺点:,结果与初始质心有关;,必须预先给出聚类的类别数,m,;,对“噪声”和孤立点数据敏感,少量的这些数据对平均值产生较大的影响;,不适合发现非凸面形状的聚类,K-,中心点聚类,避开,k-,均值聚类对“噪声”和少数孤立点的敏感性,将类中各个对象的平均值(质心)更改为类中各个对象的中心点。,但运算代价比,k-,均值聚类大。,模糊,k-,均值聚类(,ISODATA,),谱聚类,谱聚类,可以看成是特征空间中的聚类问题,原空间不具备球型(或椭球型)的聚类问题,可通过映射将其转化为特征空间中的球型(或椭球型)聚类问题,基于密度的方法,Step 1:,寻找数据集中的核心对象,(,即其,-,邻域包含较多对象的对象,)p1,pm,,形成以这些核心对象为代表的类;,Step 2:,反复寻找从这些核心对象直接密度可达的对象(在核心对象的,-,邻域中,),这期间可能涉及一些密度可达类的合并,该过程直到没有新的点可加入到任何类中时结束。,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 包罗万象 > 大杂烩

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服