聚类分析―K-means聚类 详细介绍

模式识别聚类分析K-means聚类河北大学工商学院Industrial&ComerricialCollege,HebeiUniversity主要内容K-means算法Matlab程序实现在图像分割上的简单应用算法的优缺点初始中心的选取对算法的影响KernelK-means算法2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversityK-means聚类算法算法描述1.为中心向量c1,c2,…,ck初始化k个种子2.分组:将样本分配给距离其最近的中心向量由这些样本构造不相交（non-overlapping）的聚类3.确定中心:用各个聚类的中心向量作为新的中心4.重复分组和确定中心的步骤，直至算法收敛2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversityK-means聚类算法（续）分组:将样本分配给距离它们最近的中心向量，并使目标函数值减小确定中心:亦须有助于减小目标函数值，原因：等式成立的充要条件：21},...,2,1{||||minjniikjpxmiimii12221||||||||||||wyyywymiim11yyw2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversityK-means聚类算法（续）算法的具体过程1.从数据集中任意选取k个赋给初始的聚类中心c1,c2,…,ck；2.对数据集中的每个样本点xi，计算其与各个聚类中心cj的欧式距离并获取其类别标号：3.按下式重新计算k个聚类中心；4.重复步骤2和步骤3，直到达到最大迭代次数为止。1{}Nnnx2()argmin||||,1,...,,1,...,ijjlabeliiNjkxc:(),1,2,...,sslabelsjjjcjkNx2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversityMatlab程序实现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),:));endend2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversityMatlab程序实现（续）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;end2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversity在图像分割上的简单应用例1：1.图片：一只遥望大海的小狗；2.此图为100x100像素的JPG图片，每个像素可以表示为三维向量（分别对应JPEG图像中的红色、绿色和蓝色通道）；3.将图片分割为合适的背景区域（三个）和前景区域（小狗）；4.使用K-means算法对图像进行分割。2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversity在图像分割上的简单应用（续）分割后的效果注：最大迭代次数为20次，需运行多次才有可能得到较好的效果。2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversity在图像分割上的简单应用（续）例2：注：聚类中心个数为5，最大迭代次数为10。2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversity算法的优缺点优点：思想简单易行；时间复杂度接近线性；对大规模数据的挖掘具有高效性和可伸缩性。缺点：最终的结果会随初始中心的变化而变化；算法依赖于用户指定的k值；各聚类间线性不可分时，K-means算法就会失效。2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversity初始中心的选取对算法的影响棋盘格数据集(Checkerboarddataset)仅使用其中486个正类数据，并将数据变换到[-1,1]之间，分布情况如下图所示：-1-0.500.51-1-0.500.512020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversity初始中心的选取对算法的影响（续）初始聚类中心均在左下角，即均为[-1,1]-1-0.500.51-1-0.500.51PointsInitialCentersClusterCenters迭代次数：10002020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversity初始中心的选取对算法的影响（续）初始聚类中心均在中心附近-1-0.500.51-1-0.500.51PointsInitialCentersClusterCenters2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversity初始中心的选取对算法的影响（续）初始聚类中心在平面内随机选取-1-0.500.51-1-0.500.51PointsInitialCentersClusterCenters2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversityKernelK-means算法K-means算法的聚类结果修改欧氏距离度量，即引入基于核函数的距离度量，使聚类可以产生任意形状？2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversityKernelK-means算法（续）数学符号10iivivMvxx如果样本属于第个聚类如果样本不属于第个聚类XF：1()Mvvjjjmx非线性映射：，将样本从输入空间映射到高维的特征空间。聚类中心：注意：①聚类中心的维数与特征空间维数相同，所以可以将其表示为输入样本在特征空间中像的加权和。②对聚类中心的更新只需对系数矩阵进行更新。()vjkN2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversityKernelK-means算法（续）基于核函数的距离度量：其中为核函数，在KernelK-means算法中通常使用Gaussian核函数：221111||()||||()()||(,)2(,)(,)MvvjjjMMMvjjvivjijjijKKKxmxxxxxxxx(,)Kxy22||||(,)exp{}2Kxyxy2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversityKernelK-means算法（续）分组：将xt+1赋给最近的中心mα：22111,1||()||||()||0ttvtvMxmxm如果对所有的，其他11111,11111(,)2(,)(,)2(,)0MMMijijjtjijjMMMtvivjijvjtjijjKKMKKxxxxxxxx如果其他2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversityKernelK-means算法（续）聚类中心的更新公式：11[()]ttttmmxm1,11ttiiMM111()(1)()(1)MMttjjjjjjtxx1tj1(1)11ttjjjtjt对于对于其中则有：的更新公式为：2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversityKernelK-means算法（续）棋盘格数据上的聚类效果KernelK-means算法的聚类结果2020/1/30河北大学工商学院Industrial&ComerricialCollege,HebeiUniversity作业编程实现X-means算法（K-means+BIC）~dpelleg/download/xmeans.pdf体会基于模型选择的自动聚类个数选取方法。编程实现K-means+clusterValidity~roset/papers/cal99.pdf体会基于聚类有效性的自动聚类个数选取方法2020/1/30