基于MOOC人工智能之模式识别的课程完成的第五次作业

MATLAB实现KNN算法（MNIST数据集）

MOOC地址：人工智能之模式识别

k-近邻分类器又称为 KNN 算法（K Nearest Neighbors Algorithm），它是指需要从训练集中找出待识别样本的 k 个最近邻，然后依据这 k 个最近邻分别所属的类别来决定应当把待识别样本划分到哪个类别中。



k-近邻分类器原理简单，无需对样本集进行回归分析或者概率分布统计，实现起来十分方便。

距离度量、k 值的选择及分类决策规则是 k 近邻算法的三个基本要素。

根据选择的距离度量（如曼哈顿距离或欧氏距离，Minkowski 明可夫斯基），可计算测试样本与训练集中的每个实例点的距离，根据 k 值选择 k 个最近邻点，最后根据分类决策规则将测试实例分类。

KNN.m 程序代码主要实现了数据集读入，KNN 分类器训练，测试及结果输出几个部分。数据集仍使用之前的MNIST数据集。
%knn.m
clc 
clear variables
  
load ('../test_images.mat');
load ('../test_labels.mat');
load ('../train_images.mat');
load ('../train_labels.mat');
% 选取数据容量
train_num = 2000;
test_num = 200;
data_train = mat2vector(train_images(:,:,1:train_num),train_num);% 转换为行向量
data_test = mat2vector(test_images(:,:,1:test_num),test_num);
% 参数说明：knn要求在一个范围内选取近邻样本，这个容量需要手动给出
% 其他参数如距离计算模式，距离权重均为默认，如欧式距离，等权值等。
% 具体结果可以在运行后查看knn_model来详细观察
knn_model = fitcknn(data_train,train_labels1(1:train_num),'NumNeighbors',10);
result = predict(knn_model,data_test);
acc = 0.;
for i = 1:test_num
    if result(i)==test_labels1(i)
        acc = acc+1;
    end
end
fprintf('精确度为：%5.2f%%\n',(acc/test_num)*100);

k 值的选择会对 k 近邻法的结果产生重大影响。在应用中，k 值一般取一个比较小的数值，通常采用交叉验证法来选取最优的 k 值。我们可以看一下 K 值的选择如何影响识别精度。

KNN算法在MATLAB中的实现
By:Yang Liu





运行结果：





图中结果表示测试数据（0.5，2.3）最终分到了第二类。

一、简介
K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

1 定义

如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别，即由你的“邻居”来推断出你的类别.

2 距离公式

两个样本的距离可以通过如下公式计算，又叫欧式距离


3 KNN算法的步骤

（1）计算已知类别数据集中每个点与当前点的距离；

（2）选取与当前点距离最小的K个点；

（3）统计前K个点中每个类别的样本出现的频率；

（4）返回前K个点出现频率最高的类别作为当前点的预测分类。
4 KNN原理







5 KNN的优缺点



6 KNN性能问题

NN的性能问题也是KNN的缺点之一。使用KNN，可以很容易的构造模型，但在对待分类样本进行分类时，为了获得K近邻，必须采用暴力搜索的方式，扫描全部训练样本并计算其与待分类样本之间的距离，系统开销很大。
二、源代码
clc
clear all;
close all;

%% 载入各情感的特征向量矩阵
load A_fear.mat;
load F_happiness.mat;
load N_neutral.mat;
load T_sadness.mat;
load W_anger.mat;
NumberOfTrain=size(fearVec,2)/2; %一半测试用，一半训练用
trainVector=[fearVec(:,1:NumberOfTrain),hapVec(:,1:NumberOfTrain),neutralVec(:,1:NumberOfTrain),sadnessVec(:,1:NumberOfTrain),angerVec(:,1:NumberOfTrain)]; % 构建训练样本集
testVector=[fearVec(:,(NumberOfTrain+1):size(fearVec,2)),hapVec(:,(NumberOfTrain+1):size(hapVec,2)),neutralVec(:,(NumberOfTrain+1):size(neutralVec,2)),sadnessVec(:,(NumberOfTrain+1):size(sadnessVec,2)),angerVec(:,(NumberOfTrain+1):size(angerVec,2))]; % 构建测试样本集
k=9; %k 最近邻
distanceMatrix=zeros(size(trainVector,2),size(testVector,2)); % 每一列表示某个测试语音与所有训练集样本的距离
%% 计算每个测试样本和训练样本集各样本的距离
for i=1:size(testVector,2)
    for j=1:size(trainVector,2)
        distanceMatrix(j,i)=norm(testVector(:,i)-trainVector(:,j)); %计算欧氏距离
    end
end
%% 统计分类结果 （根据相应的特征向量在数组trainVector或testVector中所处的位置来辨别类型）
totalTestNumber=size(fearVec,2)-NumberOfTrain;
emtionCounter=zeros(1,5);
n1=NumberOfTrain;
n2=n1+NumberOfTrain;
n3=n2+NumberOfTrain;
n4=n3+NumberOfTrain;
n5=n4+NumberOfTrain;
p1=size(fearVec,2)-NumberOfTrain;
p2=p1+size(hapVec,2)-NumberOfTrain;
p3=p2+size(neutralVec,2)-NumberOfTrain;
p4=p3+size(sadnessVec,2)-NumberOfTrain;
p5=p4+size(angerVec,2)-NumberOfTrain;
if(n5~=size(trainVector,2)||p5~=size(testVector,2))
    disp('data error')
    return;
end

for i=1:size(distanceMatrix,2)
    flag=zeros(1,5);
    [sortVec,index]=sort(distanceMatrix(:,i));
    % 统计K个近邻中各类别的数量
    for j=1:k
        if(n1>=index(j)&&index(j)>=1)
            flag(1)=flag(1)+1;
        elseif(n2>=index(j)&&index(j)>n1)
            flag(2)=flag(2)+1;
        elseif(n3>=index(j)&&index(j)>n2)
            flag(3)=flag(3)+1;
        elseif(n4>=index(j)&&index(j)>n3)
            flag(4)=flag(4)+1;
        else
            flag(5)=flag(5)+1;
        end
    end
    [~,index1]=sort(flag);
    % 如果K个近邻中数量最多的类别与该样本实际的类别一致，则认为算法识别正确，相应counter加一。
    if((p1>=i&&i>=1)&&index1(5)==1)
        emtionCounter(index1(5))=emtionCounter(index1(5))+1;
       
    elseif((p2>=i&&i>p1)&&index1(5)==2)
        emtionCounter(index1(5))=emtionCounter(index1(5))+1;
        
    elseif((p3>=i&&i>p2)&&index1(5)==3)
        emtionCounter(index1(5))=emtionCounter(index1(5))+1;
        
    elseif((p4>=i&&i>p3)&&index1(5)==4)
        emtionCounter(index1(5))=emtionCounter(index1(5))+1;
       
    elseif((p5>=i&&i>p4)&&index1(5)==5)
        emtionCounter(index1(5))=emtionCounter(index1(5))+1;
       
    end

end
function feature=featvector(filename)
[y,fs]=wavread(filename); 
L=length(y);
ys=y;
for i=1:(length(y)-1)
    if (abs(y(i))<1e-3)  %  剔除较小值，计算短时能量时使用  %
        ys(i)=ys(i+1);
        L=L-1;
    end
end 
y1=ys(1:L);
s=enframe(y,hamming(256),128); %  分帧加窗  %
s1=enframe(y1,hamming(256),128); 
[nframe,framesize]=size(s);  
[nframe1,framesize1]=size(s1);
E=zeros(1,nframe1);  
Z=zeros(1,nframe);
F=zeros(1,nframe);
for i=1:nframe
    Z(i)=sum(abs(sign(s(i,framesize:2)-s(i,framesize-1:1))))/2;  %  过零率  %
end
for i=1:nframe1
    E(i)=sum(s1(i,:).*s1(i,:)); %  短时能量  %
end
s1=x2-x1;s2=x3-x4;
E_Reg_coff=s1/s2;
x=0;
for i=1:nframe1
    t=E(i)-(mean(E)-s1/s2*x4/nframe1)-s1/s2*i;
    x=x+t^2/nframe1;
end
E_Sqr_Err=x;
feature(1:7,1)=[max(E);min(E);mean(E);var(E);E_shimmer;E_Reg_coff;E_Sqr_Err];%  短时能量相关特征  %

%  能量比  %
feature(8,1)=Eratio;

end

三、运行结果

四、备注
完整代码或者代写添加QQ 1564658423

一、KNN算法原理

1.算法概述

k近邻(k-Nearest Neighbor，简称kNN)学习是一种常用的监督学习方法，其工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个"邻居"的信息来进行预测。通常，在分类任务中可使用"投票法"即选择这k个样本中出现最多的类别标记作为预测结果；在回归任务中时使用"平均法"，即将这k个样本的实值输出标记的平均值作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。

kNN算法的指导思想是“近朱者赤，近墨者黑”，由你的邻居来推断出你的类别。

以二分类为例，k近邻分类示意图如图1所示。




 

虚线显示出等距线；测试样本在k=1或k=5时被判别为正例，k=3时被判别为负例。

2.算法的计算步骤

1)算距离：给定测试对象，计算它与训练集中每个对象的距离；

2)找邻居：圈定距离最近的k个训练对象，作为测试对象的近邻;

3)做分类：根据这k个近邻归属的主要类别，来对测试对象分类。

3.算法的优缺点

优点：简单，易于理解，易于实现，无需估计参数，无需训练；适合对稀有事件进行分类；特别适合于多分类问题(multi-modal,对象具有多个类别标签)。

缺点：懒惰算法，对测试样本分类时的计算量大，内存开销大，评分慢；可解释性较差，无法给出决策树那样的规则。

4.算法存在的常见问题

1)K值设定的大小

k太小，分类结果易受噪声点影响；k太大，近邻中又可能包含太多的其它类别的点。

k值通常是采用交叉检验来确定（以k=1为基准）

经验规则：k一般低于训练样本数的平方根。

2)类别判定

投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以采用加权投票法(对距离加权，距离越近的样本权重越大)。

3)选择合适的距离衡量

高维度对距离衡量的影响：当变量数越多，欧式距离的区分能力就越差；

变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化。

常用的距离度量公式如图2所示。




 

4)训练样本是否要一视同仁

在训练集中，有些样本可能是更值得依赖的，可以给不同的样本施加不同的权重，加强依赖样本的权重，降低不可信赖样本的影响。

5)性能问题

KNN是一种懒惰算法，平时不好好学习，考试（对测试样本分类）时才临阵磨枪（临时去找k个近邻）；

懒惰的后果：构造模型很简单，但在对测试样本分类时系统开销大，因为要扫描全部训练样本并计算距离；

已经有一些方法提高计算的效率，例如压缩训练样本量等。

6)能否大幅减少训练样本量，同时又保持分类精度？

浓缩技术(condensing)

编辑技术(editing)

二、KNN算法的MATLAB代码实现

对4组不同的信号分别采集20组，总共80组，然后经过特征提取(特征数量为8个)，得到80x8的矩阵。

划分数据集：将64组数据作为训练数据，16组数据作为测试数据，4类信号在训练集和测试集的数量比例相同，将训练集和测试集整体归一化，再分别作为KNN的输入。

源程序是利用KNN算法对训练集和测试集整体归一化后的测试数据进行分类，得到分类准确率。

名称：基于MATLAB的KNN算法实现多分类(类别判定采用投票法)。

源代码的博客地址：https://download.csdn.net/download/weixin_45317919/12850227

 

参考文献

[1]周志华.机器学习[M].北京:清华大学出版社,2017:225.

[2]KNN算法理解.

https://blog.csdn.net/jmydream/article/details/8644004

[3]齐兴敏.基于PCA的人脸识别技术的研究[D].武汉:武汉理工大学,2007.