K-最近邻是分类器算法中最通俗易懂的一种，计算测试样本到各训练样本的距离，取其中最小的K个，并根据这K个训练样本的标记进行投票得到测试样本的标记。

算法的思路清晰简单，然而对于海量数据计算量过大，每个训练样本都有一个距离必须度量，耗费大量时间。

function test_knn
% 二维平面两类分类问题： k应该取奇数，避免投票时正负两类的得票数相同
clear;
k=10; % 最近邻居的数目
kk=zeros(k,1); % k个最近邻的标记初始值为0；
num_po=100; % 正类样本：横坐标（0，1）；纵坐标（0，1）
x11=rand(num_po,1);
x12=rand(num_po,1);
x1=[x11 x12];
y1=ones(num_po,1); % 正类标记
num_ne=100; % 负类样本：横坐标（1，2）；纵坐标（0，1）
x21=rand(num_ne,1)+1;
x22=rand(num_ne,1);
x2=[x21 x22];
y2=-1*ones(num_ne,1); % 负类标记
x=[x1;x2];
y=[y1;y2];
num_t=20; % 测试样本
test1=rand(num_t,1)+0.5;
test2=rand(num_t,1);
test=[test1 test2];
for num=1:num_t
for i=1:(num_po+num_ne)
dis(i)=(test(num,1)-x(i,1))^2+(test(num,2)-x(i,2))^2;
end
for j=1:k % 赋初值
near(j)=10^5;
end
for i=1:(num_po+num_ne) % 求最近的K个距离并记录其标记
for j=1:k
if dis(i)<near(j)
near(j)=dis(i);
kk(j)=y(i);
for t=j:k
near(t+1)=near(t);
end
break
end
end
end
sum=0;
for h=1:k
sum=kk(h)+sum;
end
y_test(num)=sign(sum); % 测试样本的标记end
for i=1:(num_po+num_ne) % 训练样本图示 if y(i)>0
plot(x(i,1),x(i,2),'r+');
hold on
else
plot(x(i,1),x(i,2),'b.');
hold on
end
end
for i=1:num_t % 测试样样本图示 if y_test(i)>0
plot(test(i,1),test(i,2),'g+');
title('K-最近邻分类器');
hold on
else
plot(test(i,1),test(i,2),'y.');
hold on
end
end。