main_near_neighbor_fucntion_criteria.m

模式识别分类方法中的最近邻准则方法。内有详细说明文档。

%***近邻函数值准则 classification algorithm simulation ***%
% Author: Feng Shuo
% Student ID: 1030520508
% Date 2007.04.19 

clc;
clear;

%% sample,point coordinate 
sample= [2 1;
         1 2;
         1 3;
         2 4;
         4 1;
         4 2;
         5 2;
         4 3;
         5 3;
         6 5;
         9 3;
         7 6;
         7 7;
         6 8;
         5 8;
         1 7;
         3 9;
         11 2;
         4.3 4.3];

% sample=[0 0;1 0;1 1;2 2;4 3;4 4;5 3;5 4;6 5;
%         7 4;1 4;2 4;1 4;3 5;1 6;5 1;7 2;5.5 8;
%         5.5 4;1.4 9;3 7.4;5 9;3.5 7;3.7 1.5];

     
N=length(sample);

%% distance matrix D(step 1)%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
D=zeros(N,N); 
for m=1:N
   for n=1:N
      if m~=n
         D(m,n)=ecld_dist(sample(m,:),sample(n,:));
      end
   end
end
Large=ceil(max(D(:)));
for m=1:N
   for n=1:N
      if m==n
         D(m,n)=Large;
      end
   end
end

%% neighbor coefficient matrix M(step 2)%%%%%%%%%%%%%%%%%%
for i=1:N
   M(i,:)=seq_arrange(D(i,:));
end

%% neighbor function value matrix L(step 3)%%%%%%%%%%%%%%%
for i=1:N
   for j=1:N
      if i~=j
         L(i,j)=M(i,j)+M(j,i)-2;
      else
         L(i,j)=2*N;
      end
   end
end

%% original classification(step 4)%%%%%%%%%%%%%%%%%%%%%%%%

class_num=1:N;
for m=1:N
   [temp position]=min(L(m,:));
   class_num(m)=class_num(position);
end
for m=1:N %repeat
   [temp position]=min(L(m,:));
   class_num(m)=class_num(position);
end
%-----------
class_a=zeros(2,N);
for m=1:N
   for n=1:N
      if class_num(n)==m
         class_a(1,m)=class_a(1,m)+1;
         class_a(2,m)=m;
      end
   end
end
class_b=[];
for i=1:N
   if class_a(1,i)==0
      class_b=[class_b i];
   end
end
class_a(:,class_b)=[];
class_info=class_a;
clear class_a
clear class_b
%-----------
% 分类数目c
c=length(class_info);
s=cell(3,c);
% 第一行存该类样本
for k=1:c
   for n=1:N
      if class_num(n)==class_info(2,k)
         s{1,k}=[s{1,k} n];
      end
   end
end   

% 第二行存类内最大近邻函数值

% 各类内最大连接损失
for i=1:c
   % 各类内连接损失
   in_class_loss=min(L(s{1,i},s{1,i})')';
   s{2,i}=max(in_class_loss);
end
% 第三行存类间最小近邻函数值
for i=1:c
   s{3,i}=class_info(1,i);
end
% names
s{1,end+1}='sample';
s{2,end}='largest in-class loss';
s{3,end}='sample number';
%-----------
% 类间近邻函数值矩阵 r_ik
rik=zeros(c,c);
for p=1:c
   for q=1:c
      if q>=p
         rik(p,q)=min(min(L(s{1,p},s{1,q})));
      else
         rik(p,q)=Inf;
      end
   end
end
clear temp
%-----------

%% 比较类间最小近邻函数值与类内最大近邻函数值（step 5)%%%%%%%%%%%%%%%%%%%%%
% 判断需要合并的l类数，flag，供后面循环范围使用
flag=0;
for i=1:c-1
    for j=i+1:c-flag
        if rik(i,j)<s{2,i}||rik(i,j)<s{2,j}
            flag=flag+1;
        end
    end
end

for i=1:c-1
    for j=i+1:c-flag
        
        % 合并判断及执行        
        if rik(i,j)<s{2,i}||rik(i,j)<s{2,j}
            flag=flag+1;
            % 满足合并条件时：
            % 构造s_temp,先把不需要合并的s中数据保存入其中，再把需要合并的也加入
            s_temp=cell(1,1);
            temp=0;
            for k=1:c
                if k~=i&&k~=j
                    temp=temp+1;
                    s_temp{1,temp}=s{1,k};
                end
            end
            s_temp{1,end+1}=[s{1,i},s{1,j}];
            c=c-1;
            % 给出另外两行数据——类内最大连接损失、样本个数
            for k=1:c
                s_temp{2,k}=max([s{2,i},s{2,j}]);
            end
            for k=1:c
                s_temp{3,k}=length(s_temp{1,k});
            end
            s=s_temp;
            
            rik=zeros(c,c);
            for p=1:c
               for q=p:c
                  if q>=p
                     rik(p,q)=min(min(L(s{1,p},s{1,q})));
                  else
                     rik(p,q)=Inf;
                  end
               end
            end
            clear temp
            
        end            
        % 合并完成
    end
end
% names
s{1,end+1}='sample';
s{2,end}='largest in-class loss';
s{3,end}='sample number';   
     

%% 


%% figure, give out the pictures
% ------------------------------------
%maximum figure axis value
mfaxis=max(sample(:)+1);

% ----------------------------------
figure;
plot(sample(:,1),sample(:,2),'r^','MarkerFaceColor','g','LineWidth',2);
title('Original Points');
legend('Original Points')
grid on;
axis([0 mfaxis 0 mfaxis]);
% ----------------------------------
figure;
for i=1:c
       plot(sample(s{1,i},1),sample(s{1,i},2),'-*r' ,'MarkerFaceColor','g','LineWidth',2);
       title('Classified Points  (Connected points are in the same class)')
       grid on;
       hold on;
       axis([0 mfaxis 0 mfaxis]);
end

% ----------------------------------
%%%Author: Feng Shuo%%%%%%%%