聚类分析Kmeans聚类.pptx

2019/4/8主要内容K-means算法Matlab程序实现在图像分割上的简单应用算法的优缺点初始中心的选取对算法的影响KernelK-means算法2019/4/8K-means聚类算法算法描述为中心向量c1,c2,…,ck初始化k个种子分组:将样本分配给距离其最近的中心向量由这些样本构造不相交(non-overlapping)的聚类确定中心:用各个聚类的中心向量作为新的中心重复分组和确定中心的步骤,直至算法收敛2019/4/8K-means聚类算法(续)分组:将样本分配给距离它们最近的中心向量,并使目标函数值减小确定中心:亦须有助于减小目标函数值,原因:等式成立的充要条件:2019/4/8K-means聚类算法(续)算法的具体过程从数据集中任意选取k个赋给初始的聚类中心c1,c2,…,ck;对数据集中的每个样本点xi,计算其与各个聚类中心cj的欧式距离并获取其类别标号:按下式重新计算k个聚类中心;重复步骤2和步骤3,直到达到最大迭代次数为止。2019/4/8Matlab程序实现function[M,j,e]=kmeans(X,K,Max_Its)[N,D]=size(X);I=randperm(N);M=X(I(1:K),:);Mo=M;forn=1:Max_Itsfork=1:KDist(:,k)=sum((X-repmat(M(k,:),N,1)).^2,2)';end[i,j]=min(Dist,[],2);fork=1:Kifsize(find(j==k))>0M(k,:)=mean(X(find(j==k),:));endend2019/4/8Matlab程序实现(续)Z=zeros(N,K);form=1:NZ(m,j(m))=1;ende=sum(sum(Z.*Dist)./N);fprintf('%dError=%f\n',n,e);Mo=M;end2019/4/8在图像分割上的简单应用例1:图片:一只遥望大海的小狗;此图为100x100像素的JPG图片,每个像素可以表示为三维向量(分别对应JPEG图像中的红色、绿色和蓝色通道);将图片分割为合适的背景区域(三个)和前景区域(小狗);使用K-means算法对图像进行分割。2019/4/8在图像分割上的简单应用(续)分割后的效果注:最大迭代次数为20次,需运行多次才有可能得到较好的效果。2019/4/8在图像分割上的简单应用(续)例2:注:聚类中心个数为5,最大迭代次数为10。2019/4/8算法的优缺点优点:思想简单易行;时间复杂度接近线性;对大规模数据的挖掘具有高效性和可伸缩性。缺点:最终的结果会随初始中心的变化而变化;算法依赖于用户指定的k值;各聚类间线性不可分时,K-means算法就会失效。