K均值分类器-matlab

基于K均值算法的随机数矩阵动态聚类姓名：曹刚学号：20164228030专业：信息与通信工程【摘要】聚类算法是试图识别数据集合聚类的特殊性质的学习过程。对不同均值的随机数进行基于K均值算法的动态聚类是基于准则函数最优的聚类算法，本文通过描述K均值算法的原理并通过编程仿真，对随机产生的矩阵以每一行作为坐标进行动态聚类。关键词：聚类算法，K均值算法，动态聚类；【Abstract】clusteringalgorithmisthelearningprocessattemptstoidentifytheparticularsetofdataclusteringproperties.MeandifferentrandomnumberbasedondynamicclusteringK-meansalgorithmisbasedonthecriterionfunctionoptimizedclusteringalgorithm,thepaperdescribedtheprincipleofK-meansalgorithmandsimulationbyprogramming,Therandomgenerationofthematrixtoeachlineasthecoordinatesofthedynamicclustering.Keywords:clusteringalgorithm,K-meansalgorithm,dynamicclustering;第一章绪论1.1动态聚类法动态聚类法首先选择若干个样本作为聚类的中心，再按照事先确定的聚类准则进行聚类。在聚类的过程中，根据聚类中心进行反复修改，直到分类合理为止。其基本思想如图1所示。“动态”即指聚类过程中，聚类中心不断被修改的变化状态。动态聚类主要有两种常用算法：K-均值算法和迭代自组织的数据分析算法，本文主要介绍的是K-均值算法。图1动态聚类法的基本思路1.2K均值算法K均值算法（K-meanAlgorithm,也称为C均值算法）是基于准则函数最优的聚类算法，它能够使各类样本到聚类中心的距离平方和取得极小值。已知样本集合X={x1，x2，···，xn}，xj是d维特征向量，j=1,2,···，n；已知类别数K和初始聚类中心Ci；相似性测度可以采用欧氏距离；聚类准则采用误差平方和准则，其准则函数为K1iiicc-Jxx2，Ci是第i类的聚类中心K均值算法就是通过不断调整聚类中心，是的误差平方和准则函数J取得极小值。第二章K均值算法2.1K均值算法的描述（1）初始化：给定类别数K，初始化聚类中心Ci（l），（2）第l次迭代的修正：逐个将样本X={x1，x2，···，xn}按照最小距离原则分配给K个聚类中心的某一个。若，i，p=1，···，K，pi，则）（lCxp，x是聚类中心为Cp（l）的样本集。（3）计算新的聚类中心：）（）（lCxiiixNlC11，i=1,2，···，K其中Ni为第i个聚类所包含的样本个数。用均值向量作为新的聚类中心，可使准则函数CixiCixJ-2，i=1,2，···，K最小。在这一步要分别计算K个聚类的样本的均值向量，所谓的K均值算法就有此特点得名。（4）若)()(ClCi1li，令l=l+1，转（2）；将样本逐个重新分类，重复迭代计算。若）（）（liliC1C，算法收敛，计算完毕。K均值算法的计算复杂度是O（ndKl），其中n是样本数量，d是样本维数，K是类别数，l是迭代次数。K均值算法是以确定类别数和选定的初始聚类中心为前提，使样本到其所在类中心的距离之和最小。分类结构受到类别数和初始聚类中心的影响，得到的聚类结果是局部最优的。但是该方法简单，聚类结构可以令人满意，因而应用比较普遍。当类别数K未知时，在使用K均值算法是假设类别数逐步增加。可采用试探法，令K=2,3,4，···，对应算出准则函数J，做出J与K的关系曲线，J随K的增加而逐步减少。通常情况下，当J下降变慢时，对应的K较为合适。如果当没有明显转折点时，可利用对该问题的先验知识分析选取合理的类别数。初始聚类中心的选择，有以下的几种方法：（1）凭借先验知识，将样本集大致分类，取代表点。（2）将全部样本随机地分为K类，计算每类的中心，作为初始聚类中心。（3）以每个样本为中心，某个正数r为半径，在球内落入的点的个数作为密度，取最大密度点为C1（0），然后再找出与C1（0）的距离大于r的次大密度作为新的聚类中心，依次选定。（4）选择给定样本集的前K个样本作为聚类中心。（5）从K-1类问题的出K-1个聚类中心，再找出一个最远点。)(-lcxlcxijpj）（第三章实验过程及结果1、根据提示输入待聚类矩阵的行列数、聚类数K和聚类中心所在的行数。每一行作为一个模式样本，模式样本之间的距离定义为每一行相应位的差值平方和。现随机生成200行2列的矩阵(可以设定任意阶数的矩阵，此处是为了方便截图)，相当于200个模式样本，每个样本相当于二维空间的一个坐标，在坐标中表示如下图所示，并设定聚类数目K为5,同时选择聚类中心。2、经过7次迭代运算后得到最终的聚类中心以及聚类结果，不同的颜色代表不同的类。第四章实验结论从实验的过程和结果中可以得出以下结论：1、本实验程序中的输入样本是由计算机随机生成的矩阵，实际上这个随机是个伪随机，以至于多次试验结果都是相同的，程序也可以手动输入样本矩阵，只是较为麻烦。2、在K-均值算法中的K需要事先给定，而这个K值的选定通常是比较难以预先准确地估计。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。3、K-均值算法需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果4、从K-均值算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间成本是非常大的。附录：%data=input('请输入样本数据矩阵');m=input('请输入样本矩阵行数:');n=input('请输入样本矩阵列数:');data=round(8*rand(m,n));disp(data);figure(1);plot(data(:,1),data(:,2),'*r');axis([01000100]);%m=size(data,1);%矩阵的第一维度%disp('样本矩阵行数为');%disp(m);%n=size(data,2);%矩阵的第二维度%disp('样本矩阵列数为');%disp(n);counter=0;k=input('请输入聚类数目：');whilekmdisp('您输入的聚类数目过大，请输入正确的K值：');k=input('请输入聚类数目');endifk==1disp('聚类数目不能为1，请输入正确的K值：');k=input('请输入聚类数目');end%产生K个零矩阵，M用来存放聚类中心M=cell(1,m);fori=1:kM{1,i}=zeros(1,n);endMold=cell(1,m);fori=1:kMold{1,i}=zeros(1,n);end%随机选取K个样本作为初始聚类中心%第一次聚类，使用初始聚类中心p=input('请输入初始聚类中心位置');fori=1:kM{1,i}=data(p(i),:);endwhiletruecounter=counter+1;fprintf('###第%d次迭代###',counter);disp('');count=zeros(1,k);%初始化聚类CC=cell(1,k);fori=1:kC{1,i}=zeros(m,n);end%聚类fori=1:mgap=zeros(1,k);ford=1:kforj=1:ngap(d)=gap(d)+(M{1,d}(j)-data(i,j))^2;endend[y,l]=min(sqrt(gap));count(l)=count(l)+1;C{1,l}(count(l),:)=data(i,:);endMold=M;disp('聚类中心为：');fori=1:kdisp(M{1,i});enddisp('聚类结果为：');fori=1:kfprintf('第%d类聚类结果',i);disp('');disp(C{1,i});endfigure(2);fori=1:kifi=1plot(C{1,i}(:,1),C{1,i}(:,2),'*r');axis([01000100]);elseif1i&&i=2plot(C{1,i}(:,1),C{1,i}(:,2),'*g');axis([01000100]);elseif2i&&i=3plot(C{1,i}(:,1),C{1,i}(:,2),'*b');axis([01000100]);elseif3i&&i=4plot(C{1,i}(:,1),C{1,i}(:,2),'*y');axis([01000100]);elseif4i&&i=5plot(C{1,i}(:,1),C{1,i}(:,2),'*m');axis([01000100]);elseif5i&&i=6plot(C{1,i}(:,1),C{1,i}(:,2),'*c');axis([01000100]);elseif6i&&i=7plot(C{1,i}(:,1),C{1,i}(:,2),'*k');axis([01000100]);endholdonendsumvar=0;fori=1:kE=0;disp('单个误差平方和为：');forj=1:count(i)forh=1:nE=E+(M{1,i}(h)-C{1,i}(j,h))^2;endenddisp(E);sumvar=sumvar+E;enddisp('总体误差平方和为：');disp(sumvar);%计算新的聚类中心，更新M，并保存旧的聚类中心fori=1:kM{1,i}=sum(C{1,i})/count(i);end%检查前后两次聚类中心是否变化，若变化则继续迭代，否则算法停止；tally=0;fori=1:kifabs(Mold{1,i}-M{1,i})1e-5*ones(1,n)tally=tally+1;continue;elsebreak;endendiftally==kbreak;endend