KNN(K Nearest Neighbor)

原理解读

  KNN(K Nearest Neighbor):又称K近邻，是一种基本分类方法，给定测试实例，基于某种距离度量找出训练集中与其最靠近的k个实例点，然后基于这k个最近邻的信息使用投票法，即选择这k个实例中出现最多的标记类别作为分类结果。

核心思想

距离的度量

  1. 欧式距离(Euclidean Distance)
$$L_2(x_i,x_j)=\sqrt{\displaystyle \sum_{k=1}^n ({x_i}^{(k)}-{x_j}^{(k)})^2}$$

  2. 曼哈顿距离(Manhattan distance)
$$L_1(x_i,x_j)=\displaystyle \sum_{k=1}^n \lvert{x_i}^{(k)}-{x_j}^{(k)} \rvert$$

  3.余弦距离(Cosine Distance)
$$L_{cos}(x_i,x_j)=1-\frac{x_i \cdot x_j}{\lVert x_i \rVert_2 \ \lVert x_j \rVert_2}$$

K值的选择

  K值的选择会对K近邻法的结果产生重大影响，在应用中，k值一般取一个比较小的数值，通常采用交叉验证法来选取最优的k值。
  K=1时K近邻算法退化成最近邻，即数据的类别为距离最近的样本的类别。

算法流程

代码实战

KNN_main.m

clear;clc;close all;
%类别数目，请输入大于1的数
class_num=2;
%k近邻数目
knn=3;
%训练集样本
train_x=[0.7,0.8,0.1,0.4,0.2;...
     0.5,0.6,0.1,0.8,0.2];
train_y=[1,1,2,1,2];
%特征数目
feat_num=size(train_x,1);
%测试集样本
test_x=[rand(1,50);rand(1,50)];
%训练集样本数
train_num=size(train_x,2);
%测试集样本数
test_num=size(test_x,2);
%尺度缩放到0-1
train_x_scale=zeros(size(train_x));
test_x_scale=zeros(size(test_x));
for i=1:feat_num
    train_x_scale(i,:)=(train_x(i,:)-min(train_x(i,:)))/(max(train_x(i,:))-min(train_x(i,:)));
    test_x_scale(i,:)=(test_x(i,:)-min(train_x(i,:)))/(max(train_x(i,:))-min(train_x(i,:)));
end
%如果knn大于样本数，则无法判别
if knn>train_num
    disp('Error');
else
    test_y=KNN_classify(train_x_scale,train_y,test_x_scale,train_num,test_num,knn);
    %如果数据的特征是二维的，可以绘图表示
    if feat_num==2
        KNN_display(train_x,train_y,test_x,test_y,train_num,test_num,class_num);
    else
        disp('The Feature Is Not Two-Dimensional');
    end
end

KNN_classify.m

function test_y=KNN_classify(train_x_scale,train_y,test_x_scale,train_num,test_num,knn)
test_y=zeros(1,test_num);
distance=zeros(test_num,train_num);
for i=1:test_num
    %distance(i,j)代表第i个测试集到第j个训练集的距离
    distance(i,:)=sum((train_x_scale-repmat(test_x_scale(:,i),1,train_num)).^2);
    temp=sort(distance(i,:));
    %找到最近的knn个数据
    tem=tabulate(train_y(distance(i,:)<=temp(knn)));
    %找到最近的数据中最多的类别
    test_y(i)=tem(find(tem(:,2)==max(tem(:,2)),1),1);
end

KNN_display.m

function KNN_display(train_x,train_y,test_x,test_y,train_num,test_num,class_num)
hold on;
color_bar=zeros(class_num,3);
for i=1:class_num
    color_bar(i,:)=[rand(1),rand(1),rand(1)];
end
%画出每一类的训练数据，用*表示
for i=1:train_num
    plot(train_x(1,i),train_x(2,i),'color',color_bar(train_y(i),:),'marker','*');
end
%画出每一类的测试数据，用o表示
for j=1:test_num
    plot(test_x(1,j),test_x(2,j),'color',color_bar(test_y(j),:),'marker','o');
end
hold off;

实验结果

KNN优缺点

• 优点：
  • 无需参数估计，无需训练
  • 算法简单，易于理解和实现
  • 适合于对稀有数据进行分类
  • 特别适合于多分类问题，KNN的表现超过SVM
• 缺点：
  • 无法给出分类规则
  • 对于高维特征，距离的选择和衡量不准确
  • 计算量较大，对每一个测试样本都需要计算与其他样本的距离
  • 样本不平衡时，尤其是一类样本多，其他类样本少时会产生严重的问题