资源预览内容
第1页 / 共28页
第2页 / 共28页
第3页 / 共28页
第4页 / 共28页
第5页 / 共28页
第6页 / 共28页
第7页 / 共28页
第8页 / 共28页
第9页 / 共28页
第10页 / 共28页
亲,该文档总共28页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
聚类(无监督学习)综述,聚类问题的描述(1),聚类问题的描述(2),聚类问题:根据给定的数据集,要求寻找 T上的一个“好”的划分 (划分成m个类; m可以是已知的,也可以是未知的),满足约束条件:,聚类问题的描述(3),模糊聚类问题:根据给定的数据集,要求寻找 T上的一个“好”的模糊划分 (划分成m个模糊集),满足约束条件 :,模糊聚类问题可以看成是前面聚类问题(硬聚类)的一个推广,当uj的值域限制为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) 1068枚举聚类是行不通的!,主要聚类算法(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个样本x1,xN划分到m个类C1,Cm中,最小化评分函数,这里 c1,cm 是C1,Cm的质心, 是划分到类Cj的样本,K-means Clustering实现,随机选择m个样本点作为m个初始质心c1,cm ; 按距离最近原则,将所有样本划分到以质心c1,cm为代表的m个类中; 重新计算m个类的质心c1,cm; 重复(2)和(3)直到质心c1,cm 无改变或目标函数J(c1,cm )不减小。,K-means Clustering特点,优点: 当类密集,且类与类之间区别明显(比如球型聚集)时,聚类效果很好; 强的一致性 算法的复杂度是O(Nmt)(t为迭代次数),对处理大数据集是高效的。 缺点: 结果与初始质心有关; 必须预先给出聚类的类别数m; 对“噪声”和孤立点数据敏感,少量的这些数据对平均值产生较大的影响; 不适合发现非凸面形状的聚类,K-中心点聚类,避开k-均值聚类对“噪声”和少数孤立点的敏感性,将类中各个对象的平均值(质心)更改为类中各个对象的中心点。 但运算代价比k-均值聚类大。,模糊k-均值聚类(ISODATA),谱聚类,谱聚类,可以看成是特征空间中的聚类问题 原空间不具备球型(或椭球型)的聚类问题,可通过映射将其转化为特征空间中的球型(或椭球型)聚类问题,基于密度的方法,Step 1: 寻找数据集中的核心对象(即其-邻域包含较多对象的对象) p1,pm,形成以这些核心对象为代表的类; Step 2:反复寻找从这些核心对象直接密度可达的对象(在核心对象的-邻域中),这期间可能涉及一些密度可达类的合并,该过程直到没有新的点可加入到任何类中时结束。,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号