聚类分析—KmeansandKmedoids聚类要点课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《聚类分析—KmeansandKmedoids聚类要点课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 聚类分析 KmeansandKmedoids 要点 课件
- 资源描述:
-
1、数据挖掘数据挖掘Topic3-聚类分析聚类分析K-means&K-medoids 聚类聚类2023-2-8主要内容K-means算法Matlab程序实现在图像分割上的简单应用K-medoids算法k-中心点聚类算法中心点聚类算法-PAMK-medoids改进算法2023-2-8基于划分的聚类方法基于划分的聚类方法n构造构造n个对象数据库个对象数据库D的划分的划分,将其划分成将其划分成k个聚类个聚类n启发式方法启发式方法:k-平均值平均值(k-means)和和 k-中心点中心点(k-medoids)算算法法nk-平均值平均值(MacQueen67):每个簇用该簇中对象的平均值来表示每个簇用该簇中
2、对象的平均值来表示 nk-中心点或中心点或 PAM(Partition around medoids)(Kaufman&Rousseeuw87):每个簇用接近聚类中心的一个对象来表示每个簇用接近聚类中心的一个对象来表示 n这些启发式算法适合发现中小规模数据库中的球状聚类这些启发式算法适合发现中小规模数据库中的球状聚类n对于大规模数据库和处理任意形状的聚类对于大规模数据库和处理任意形状的聚类,这些算法需要进这些算法需要进一步扩展一步扩展2023-2-8K-means聚类算法聚类算法n算法描述算法描述1.为中心向量c1,c2,ck初始化k个种子2.分组:将样本分配给距离其最近的中心向量 由这些样本
3、构造不相交(non-overlapping)的聚类3.确定中心:用各个聚类的中心向量作为新的中心4.重复分组和确定中心的步骤,直至算法收敛2023-2-8K-means聚类算法聚类算法(续)(续)n算法的具体过程算法的具体过程1.从数据集 中任意选取k个赋给初始的聚类中心c1,c2,ck;2.对数据集中的每个样本点xi,计算其与各个聚类中心cj的欧氏距离并获取其类别标号:3.按下式重新计算k个聚类中心;4.重复步骤2和步骤3,直到达到最大迭代次数为止。1Nnnx2()argmin|,1,.,1,.,ijjlabel iiN jkxc:(),1,2,.,ss label sjjjcjkNx202
4、3-2-8Matlab程序实现程序实现function M,j,e=kmeans(X,K,Max_Its)N,D=size(X);I=randperm(N);M=X(I(1:K),:);Mo=M;for n=1:Max_Its for k=1:K Dist(:,k)=sum(X-repmat(M(k,:),N,1).2,2);end i,j=min(Dist,2);for k=1:K if size(find(j=k)0 M(k,:)=mean(X(find(j=k),:);end end2023-2-8Matlab程序实现程序实现(续)(续)Z=zeros(N,K);for m=1:N Z(
5、m,j(m)=1;end e=sum(sum(Z.*Dist)./N);fprintf(%d Error=%fn,n,e);Mo=M;end2023-2-8k-平均聚类算法平均聚类算法(续续)n例例012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2任意选择任意选择 K个对个对象作为初始聚类象作为初始聚类中心中心将每个将每个对象赋对象赋给最类给最类似的中似的中心心更新簇更新簇的平均的平均值值重新赋值重新
6、赋值更新簇更新簇的平均的平均值值重新赋值重新赋值2023-2-8在图像分割上的简单应用在图像分割上的简单应用例例1:1.图片:一只遥望大海的小狗;2.此图为100 x 100像素的JPG图片,每个像素可以表示为三维向量(分别对应JPEG图像中的红色、绿色和蓝色通道);3.将图片分割为合适的背景区域(三个)和前景区域(小狗);4.使用K-means算法对图像进行分割。2023-2-8在图像分割上的简单应用在图像分割上的简单应用(续)(续)分割后的效果注:最大迭代次数为20次,需运行多次才有可能得到较好的效果。2023-2-8在图像分割上的简单应用在图像分割上的简单应用(续)(续)例例2:注:聚类
7、中心个数为5,最大迭代次数为10。2023-2-8k-平均聚类算法平均聚类算法(续续)n优点优点:相对有效性相对有效性:O(tkn),其中其中 n 是对象数目是对象数目,k 是簇数目是簇数目,t 是迭代次数是迭代次数;通常通常,k,t n.n当结果簇是密集的,而簇与簇之间区别明显时,它的效果当结果簇是密集的,而簇与簇之间区别明显时,它的效果较好较好nComment:常常终止于常常终止于局部最优局部最优.n全局最优全局最优 可以使用诸如确定性的退火可以使用诸如确定性的退火(deterministic annealing)和遗传算法和遗传算法(genetic algorithms)等技术得到等技术
8、得到2023-2-8k-平均聚类算法平均聚类算法(续续)n弱点弱点n只有在簇的平均值只有在簇的平均值(mean)被定义的情况下才能使用被定义的情况下才能使用.可能不适用于可能不适用于某些应用某些应用,例如涉及有例如涉及有分类属性分类属性的数据的数据n需要预先指顶簇的数目需要预先指顶簇的数目k,n不能处理噪音数据和孤立点不能处理噪音数据和孤立点(outliers)n不适合用来发现具有非凸形状不适合用来发现具有非凸形状(non-convex shapes)的簇的簇2023-2-8k-中心点聚类方法中心点聚类方法nk-平均值算法对孤立点很敏感平均值算法对孤立点很敏感!n因为具有特别大的值的对象可能显
9、著地影响数据的分布因为具有特别大的值的对象可能显著地影响数据的分布.nk-中心点中心点(k-Medoids):不采用簇中对象的平均值作为参照不采用簇中对象的平均值作为参照点点,而是而是选用簇中位置最中心的对象选用簇中位置最中心的对象,即中心点即中心点(medoid)作作为参照点为参照点.0123456789100123456789100123456789100123456789100123456789100123456789102023-2-8k-中心点聚类方法中心点聚类方法(续续)n找聚类中的代表对象找聚类中的代表对象(中心点中心点)nPAM(Partitioning Around Medo
10、ids,1987)n首先为每个簇随意选择选择一个代表对象首先为每个簇随意选择选择一个代表对象,剩余的对象根据剩余的对象根据其与代表对象的距离分配给最近的一个簇其与代表对象的距离分配给最近的一个簇;然后反复地用然后反复地用非代表对象来替代代表对象,以改进聚类的质量非代表对象来替代代表对象,以改进聚类的质量 nPAM 对于较小的数据集非常有效对于较小的数据集非常有效,但不能很好地扩展到大但不能很好地扩展到大型数据集型数据集nCLARA(Kaufmann&Rousseeuw,1990)抽样抽样nCLARANS(Ng&Han,1994):随机选样随机选样2023-2-8k-中心点聚类方法中心点聚类方法
11、(续续)n基本思想:基本思想:n首先为每个簇随意选择选择一个代表对象首先为每个簇随意选择选择一个代表对象;剩余的对象剩余的对象根据其与代表对象的距离分配给最近的一个簇根据其与代表对象的距离分配给最近的一个簇n然后反复地用非代表对象来替代代表对象然后反复地用非代表对象来替代代表对象,以改进聚类以改进聚类的质量的质量n聚类结果的质量用一个代价函数来估算聚类结果的质量用一个代价函数来估算,该函数评估了该函数评估了对象与其参照对象之间的平均相异度对象与其参照对象之间的平均相异度 21|jkijp CEpo2023-2-8k-中心点聚类方法中心点聚类方法(续续)n为了判定一个非代表对象为了判定一个非代表
12、对象Orandom 是否是当前一个代表对象是否是当前一个代表对象Oj的好的替代的好的替代,对于每一个非代表对象对于每一个非代表对象p,考虑下面的四种情况:考虑下面的四种情况:n第一种情况:第一种情况:p当前隶属于代表对象当前隶属于代表对象 Oj.如果如果Oj被被Orandom所代替所代替,且且p离离Oi最近最近,ij,那么那么p被重新分配给被重新分配给Oi n第二种情况:第二种情况:p当前隶属于代表对象当前隶属于代表对象 Oj.如果如果Oj 被被Orandom代替代替,且且p离离Orandom最最近近,那么那么p被重新分配给被重新分配给Orandom n第三种情况:第三种情况:p当前隶属于当前
展开阅读全文