Knn算法

邻近算法

KNN算法的决策过程

　　k-Nearest Neighbor algorithm
　　右图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。
　　K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相 似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决 策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方 法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
　　KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。
　　该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量 很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。该方法 的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样 本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误 分。

matlab练习程序（KNN，K最邻近分类法）

K最邻近密度估计技术是一种分类方法，不是聚类方法。

不是最优方法，实践中比较流行。

通俗但不一定易懂的规则是：

1.计算待分类数据和不同类中每一个数据的距离（欧氏或马氏）。

2.选出最小的前K数据个距离，这里用到选择排序法。

3.对比这前K个距离，找出K个数据中包含最多的是那个类的数据，即为待分类数据所在的类。

不通俗但严谨的规则是：

给定一个位置特征向量x和一种距离测量方法，于是有：

1.在N个训练向量外，不考虑类的标签来确定k邻近。在两类的情况下，k选为奇数，一般不是类M的倍数。

2.在K个样本之外，确定属于wi,i=1,2,...M类的向量的个数ki,显然sum(ki)=k。

3.x属于样本最大值ki的那一类wi。

如下图，看那个绿色的值，是算三角类呢还是算矩类形呢，这要看是用几NN了，要是3NN就属于三角，要是5NN就属于矩形。

至于K到底取几，不同情况都要区别对待的。

下面是相关matlab代码：

clear all;
close all;
clc;

%%第一个类数据和标号
mu1=[0 0];  %均值
S1=[0.3 0;0 0.35];  %协方差
data1=mvnrnd(mu1,S1,100);   %产生高斯分布数据
plot(data1(:,1),data1(:,2),'+');
label1=ones(100,1);
hold on;

%%第二个类数据和标号
mu2=[1.25 1.25];
S2=[0.3 0;0 0.35];
data2=mvnrnd(mu2,S2,100);
plot(data2(:,1),data2(:,2),'ro');
label2=label1+1;

data=[data1;data2];
label=[label1;label2];

K=11;   %两个类，K取奇数才能够区分测试数据属于那个类
%测试数据，KNN算法看这个数属于哪个类
for ii=-3:0.1:3
    for jj=-3:0.1:3
        test_data=[ii jj];  %测试数据
        label=[label1;label2];
        %%下面开始KNN算法，显然这里是11NN。
        %求测试数据和类中每个数据的距离，欧式距离（或马氏距离） 
        distance=zeros(200,1);
        for i=1:200
            distance(i)=sqrt((test_data(1)-data(i,1)).^2+(test_data(2)-data(i,2)).^2);
        end

        %选择排序法，只找出最小的前K个数据,对数据和标号都进行排序
        for i=1:K
            ma=distance(i);
            for j=i+1:200
                if distance(j)<ma
                    ma=distance(j);
                    label_ma=label(j);
                    tmp=j;
                end
            end
            distance(tmp)=distance(i);  %排数据
            distance(i)=ma;

            label(tmp)=label(i);        %排标号，主要使用标号
            label(i)=label_ma;
        end

        cls1=0; %统计类1中距离测试数据最近的个数
        for i=1:K
           if label(i)==1
               cls1=cls1+1;
           end
        end
        cls2=K-cls1;    %类2中距离测试数据最近的个数
        
        if cls1>cls2    
           plot(ii,jj);     %属于类1的数据画小黑点
        end
        
    end
end

代码中是两个高斯分布的类，变量取x=-3:3,y=-3:3中的数据，看看这些数据都是属于哪个类。

下面是运行效果图：