模式识别(KNNKMEANSFCM).doc

一、K近邻算法1.算法思想取未知样本的x的k个近邻,看这k个近邻中多数属于哪一类，就把x归于哪一类。具体说就是在N个已知的样本中,找出x的k个近邻。设这N个样本中，来自类的样本有个，来自的样本有个，.，来自类的样本有个，若分别是k个近邻中属于类的样本数，则我们可以定义判别函数为： 决策规则为： 若，则决策2.程序代码%KNN算法程序function error=knn(X,Y,K)%error为分类错误率data=X;M,N=size(X);Y0=Y;m0,n0=size(Y);t=1 2 3;%3类向量ch=randperm(M);%随机排列1Merror=0;for i=1:10 Y1=Y0; b=ch(1+(i-1)*M/10:i*M/10); X1=X(b,:); X(b,:)=; Y1(b,:)=; c=X; m,n=size(X1); %m=15,n=4 m1,n=size(c); %m1=135,n=4 for ii=1:m for j=1:m1 ss(j,:)=sum(X1(ii,:)-c(j,:).2); end z1,z2=sort(ss); %由小到大排序 hh=hist(Y1(z2(1:K),t); w,best=max(hh); yy(i,ii)=t(best); %保存修改的分类结果 end error=error+sum(Y0(b,:)=yy(i,:); X=data;enderror=error/M;%算法主程序：clcclear allload iris.mat %iris.mat中存放X为150*4的iris数据，Y为150*1的分类结果，以下均使用该数据n=0;for i=1:10error=knn(X,Y,1);n=n+error;endcorrect=1-n/103.程序运行结果做十折交叉验证得到：当K=1时，正确分类概率为：0.9587当K=3时，正确分类概率为：0.9613当K=5时，正确分类概率为：0.9640当K=7时，正确分类概率为：0.9653当K=10时，正确分类概率为：0.9667当K=30时，正确分类概率为：0.9480当K=60时，正确分类概率为：0.90274.结果分析从以上的结果我们可以看出当k较小时，随着k的增加，其正确分类的概率也逐渐增加；然而当k增加到一定的值时，即k取较大的值时，随着k的增加，其正确率并没有随之增加，反而大大降低了。因此在实际中选择K的值时应慎重考虑，结合实际结果，选取合适的K值。二、K均值算法1.算法思想K-means算法是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点，通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。在下面的算法中，在计算数据样本之间的距离时，采用的欧式距离。其步骤如下：（1） 为每一个聚类确定一个初始的聚类中心，这样就有K个聚类中心。（2） 将样本集中的样本按照最小距离准则分配到最临近聚类（3） 使用每个聚类中的样本均值作为新的聚类中心（4） 重复步骤2,3直到聚类中心不再变化。（5） 结束，得到K个聚类2.程序代码%K均值算法程序function class,num,center = kmeans(x,k,start)n,d = size(x); class = zeros(1,n);% 设置class 为分类结果显示矩阵num = zeros(1,k); %num保存每一类的个数maxgn= 10000;iter = 1;while iter maxgn %计算每个数据到聚类中心的距离 for i = 1:n dist = sum(repmat(x(i,:),k,1)-start).2,2); m,ind = min(dist); class(i) = ind; % 将当前聚类结果存入class 中 end for i = 1:k %找到每一类的所有数据，计算他们的平均值，作为下次计算的聚类中心 ind = find(class=i); start(i,:) = mean(x(ind,:); num(i) = length(ind); % 统计每一类的数据个数 end iter = iter + 1;endmaxiter = 2;iter = 1;move = 1;while iter 1是一个可以控制的聚类结果的模糊程度的常数。在不同的隶属度定义方法下最小化损失函数，就可以得到不同的模糊聚类方法。模糊C均值算法，它要求一个样本对于各个聚类的隶属度之和为1，即满足：算法的步骤如下：（1） 设定聚类数目c、算法停止阈值和参数b（2） 随机初始化隶属度矩阵U（3） 用当前的聚类中心计算隶属度函数，若隶属度函数小于所给阈值，算法停止。（4） 用当前的隶属度函数更新计算各类的聚类中心，转（3）2.程序代码%模糊C均值程序function Correct,Class,Center,Distance,U,Fvalue,Count=fcm(Data,C)% Correct:正确分类概率% Data:聚类的原始数据% C:聚类数目 % Center : 聚类中心% Distance:聚类中心到各样本点的距离% U:隶属度矩阵 % Class: 聚类结果,共 C 行,每一行对应一类% Fvalue: 目标函数值% Count:算法迭代次数eps=1.0e-10; %算法的迭代停止阈值M=2; %加权指数N,S=size(Data);m=2/(M-1);Count=0;Distance(C,N)=0; U(C,N)=0;Center(C,S)=0;U0 = rand(C,N); % 随机初始化隶属度矩阵U0=U0./(ones(C,1)*sum(U0);% FCM 的迭代算法while 1 Count=Count+1; % 迭代次数 % 计算或更新聚类中心 Um=U0.M; Center=Um*Data./(ones(S,1)*sum(Um); % 更新隶属度矩阵 for i=1:C for j=1:N Distance(i,j)=norm(Center(i,:)-Data(j,:); end end U=1./(Distance.m.*(ones(C,1)*sum(Distance.(-m); %计算新的隶属度值 Fvalue(Count)=sum(sum(Um.*Distance.2); % 聚类损失函数值： 类内加权平方误差和 if norm(U-U0,Inf)N/C*(i-1) & Class.h; % 目标函数绘图figure(1),plot(Fvalue)title(目标函数值变化曲线,fontsize,8)figure(2),plot3(Center(:,1),Center(:,2),Center(:,3),rs),hold onfor i=1:C v=Data(find(Res=i),:); plot3(v(:,1),v(:,2),v(:,3),str(rem(i,12)+1) endgrid on,title(聚类结果图,fontsize,8),hold off%算法主程序：clear all;clc;load iris.mat;fcm(X,3)3.程序运行结果画图结果：4.结果分析 从上面运行结果我们可以得到其识别率大致为89.33%，在迭代了36次后，目标损失函数最终收敛于60.5760。从准确率来看，模糊c均值的识别率还是相对较高的，对于类别一的样本可以准确的分类，而对于二、三类的样本中相交叠的部分样本点存在着部分错分情况。 由于引进了归一化条件，因此，当样本集不理想的情况下，可能会导致效果不好