K-最近邻分类方法（KNN，k-nearest-neighbor classifier)是一种惰性学习法，所谓惰性就是KNN不像一些算法(比如SVM)一样在接收待分类数据前就已经根据训练数据构造好了分类模型，而是会在接受到训练数据后，只是对训练数据进行简单的存储，并不构造分类模型，在接受到待分类数据时，KNN通过计算待分类数据X与所有训练数据之间的距离，选择前K个距离X最近的数据，并将这K个距离最近的数据中出现次数最多的类属性赋给X。如下图所示，判断图中待分类数据绿色圆点的分类情况：

当K取3时，此时离待分类数据绿色圆点最近的5个数据中，包含2个红色三角和1个蓝色四边形，出现次数多的红色三角的类属性将会赋给此待分类数据。
当K取5时，此时离待分类数据绿色圆点最近的5个数据中，仍包含2个红色三角，但是蓝色四边形数目增加到3个，3>2，所以，出现次数多的蓝色四边形的类属性将会赋给此待分类数据。

knnclassify函数
在matlab中，关于KNN分类的函数为knnclassify，Class=knnclassify(Sample,Training，Group，k，distance，rule),其中输入参数分别为
1、Sample：待分类数据，其列数（特征数）要与训练数据相同。
2、Training：训练数据，M*N,M（行）为数据个数，N（列）为特征数。
3、Group：训练数据所对应的类属性。
4、k：分类中，最近邻的个数，默认为1.
5、distance：计算数据间距离的方法，有以下几种选择：
（1）euclidean：欧几里得距离（默认值）
（2）cityblock：曼哈顿（或城市块）距离
（3）cosine:余弦距离
（4）correlation：相关距离
（5）hamming：海明距离
这些距离方式实际上是采用不同的函数来计算两个数据对象之间的距离，例如：
对于两个被p个特征描述的数据对象 i=(Xi1，Xi2，……，Xip)和j=(Xj1，Xj2，……，Xjp)，他们的欧几里得距离为：

他们的曼哈顿（或城市块）距离为：

6、rule：确定类属性的规则，有以下几种选择：
（1） nearest ： 最近的K个的最多数（默认值）
（2） random ： 随机的最多数
（3） consensus： 投票法
测试实验
(1)选取k=1,diatance=’cityblock’,rule=’nearest’

function [ classfication ] = KNN2_1( train,test )
%使用matlab自带的关于花的数据进行二分类实验（150*4），其中，每一行代表一朵花，
%共有150行（朵)，每一朵包含4个属性值（特征），即4列。且每1-50，51-100，
%101-150数据分别为同一类，分别为setosa青风藤类，versicolor云芝类，virginica锦葵类

load fisheriris                       %下载数据包含：meas（150*4花特征数据）
                                  %和species（150*1 花的类属性数据） 

meas=meas(1:100,1:2)                    %选取前两类前两个属性进行分类 
train=[(meas(1:40,:));(meas(51:90,:))]; %选取数据中每类对应的前40个作为训练数据
test=[(meas(41:50,:));(meas(91:100,:))];%选取数据中每类对应的后10个作为测试数据
trainGroup=[ones(1,40),2*ones(1,40)]';       %类属性设置为1，2
testGroup=[ones(1,10),2*ones(1,10)]';

%KNN分类
class=knnclassify(test,train,trainGroup,1,'cityblock','nearest');
%用plot显示出测试数据分类结果
testGroup=[ones(1,10),2*ones(1,10)]'; 
figure;
hold on;
plot(testGroup,'o');
plot(class,'*');
legend('测试集正确分类','KNN分类结果');
disp(class);
%计算分类测试的准确率
%正确的分类情况为testGroup，实验测试获得的分类情况为class

%计算分类精度
count=0;
for i=(1:20)
   if class(i)==testGroup(i)
      count=count+1;
   end
end
fprintf('分类精度为：%f\n' ,count/20);

end

实验结果

当改变knnclassify函数参数为：k=5,distance=’euclidean’,rule=’nearest’时，获得的实验结果如下图：


主要存在的问题
KNN分类法最大的优点是思想简单，容易理解，并且不需要训练分类模型，同时，对于多分类问题，KNN分类较其他方法也更简单，还是一样的根据距离来判断。
虽然KNN不需要训练模型，但其在对数据分类时的计算量却很大，因为每一个待分类的数据与训练数据的距离都要计算，并且当训练数据中各类别数据的个数差距较大时，在类别判定时，由于某类的数据个数太多，在总体训练数据中分布比较密集，对于一个待分类的数据来说，在它的K个最近邻居中，数据个数多的类别更容易占优势，从而影响了分类结果。再有就是K值得选择问题，如果K值太小，得到的最近邻数据太少，对分类精度会有影响，如果K值太大，那么像上面所说的‘各类别数据个数差距较大而影响分类结果’的问题就会被放大。
改进 （1）对于计算量大的问题，我们可以通过减少特征个数，只选择部分区别性能强的特征来作为分类数据的特征值，再有就是由于计算距离时，需要计算待分类数据与所有训练数据的距离，我们还可以减少训练数据的数量，只保留部分与分类相关较大的训练数据。 （2）再有就是在计算距离时，通过对不同的特征设置不同的权重值，对不同距离的邻居设置不同的权重值的方法来改进KNN方法中所有特征对距离的作用相同的缺陷以及不同距离的邻居对类别的判定作用相同的缺陷。 （3）K值得选择，很大程度影响分类的效果，可以采用交叉检验来确定K值。