KNN：K-Nearest Neighbor algorithm
问题
已知：存在一个数据集：数据集个数为n，且存在标签，即这些数据都已经分好类。现在又进来一个数据，要求对这个新数据贴上标签，即确定分类。
KNN基本思想：物以类聚，人以群分
首先提取新数据的特征并与原数据集中的每一个数据特征进行比较；然后从数据集中提取K个最邻近（最相似）的数据特征标签，统计这K个最邻近数据中出现次数最多的分类，将其作为新的数据类别。
在KNN学习中，首先计算待分类数据特征与训练数据特征之间的距离并排序，取出距离最近的K个训练数据特征；然后根据这K个相近训练数据特征所属类别来判定新样本类别：如果它们都属于一类，那么新的样本也属于这个类；否则，对每个候选类别进行评分，按照某种规则确定新的样本的类别。笔者借用下面这个图来做更形象的解释：
1.png
- 看离圆形最近（K=1）的那个类型是什么，由图可知，离圆形最近的是三角形，故将新数据判定为属于三角形这个类别。
- 看离圆形最近的3个数据（K=3）的类型是什么，由图可知离圆形最近的三个中间有两个是矩形，一个是三角形，故将新数据判定为属于矩形这个类别。
- 看离圆形最近的9个数据（K=9）的类型是什么，由图可知离圆形最近的9个数据中间，有五个是三角形，四个是矩形，故新数据判定为属于三角形这个类别。
上面所说的三种情况也可以说成是1-近邻方法、3-近邻方法、9-近邻方法。当然，K还可以取更大的值，当样本足够多，且样本类别的分布足够好的话，那么K值越大，划分的类别就越正确。而KNN中的K表示的就是划分数据时，所取相似样本的个数。
我们都知道，当K=1时，其抗干扰能力就较差，因为假如样本中出现了某种偶然的类别，那么新的数据很有可能被分错。为了增加分类的可靠性，可以考察待测数据的K个最近邻样本 ，统计这K个近邻样本中属于哪一类别的样本最多，就将样本X判属于该类。
当然，如果在样本有限的情况下，KNN算法的误判概率和距离的具体测度方法就有了直接关系。即用何种方式判定哪些数据与新数据近邻。不同的样本选择不同的距离测量函数，这能够提高分类的正确率。通常情况下，KNN可以采用Euclidean（欧几里得）、Manhattan（曼哈顿）、Mahalanobis（马氏距离）等距离用于计算。
下面给出KNN学习的伪代码：
Algorithm KNN(A[n],k,x)
Input:
A[n]为N个训练样本的特征，K为近邻数，x为新的样本；
Initialize:
取A[1]~A[k]作为x的初始近邻；
计算测试样本与x间的欧式距离d(x,A[i]),i=1,2...,k;
按d(x,A[i])升序排序；
计算最远样本与x间距离D，即max{d(x,A[i])}；
for(i=k+1;i<=n;i++)
计算A[i]与x之间的距离d(x,A[i])；
if （d(x,A[i])）<D then 用A[i]代替最远样本；
按照d(x,A[i])升序排序；
计算最远样本与x间的距离D，即max{d(x,A[i])}；
End for
计算前K个样本A[i],i=1,2...,k所属类别的概率；
具有最大概率的类别即为样本x的类；
Output:x所属的类别。
KNN的不足
1、加入某些类别的样本容量很大，而其他类样本容量很小，即已知的样本数量不均衡，有可能当输入一个和小容量类相同的的新样本时，该样本的K个近邻中，大容量类的样本占多数，从而导致误分类。
针对此种情况可以采用加权的方法，即和该样本距离小的近邻所对应的权值越大，将权值纳入分类的参考依据。
2、分类时需要先计算待分类样本和全体已知样本的距离，才能求得所需的K近邻点，计算量较大，尤其是样本数量较多时。
针对这种情况可以事先对已知样本点进行剪辑，去除对分类作用不大的样本，这一处理步骤仅适用于样本容量较大的情况，如果在原始样本数量较少时采用这种处理，反而会增加误分类的概率。
改进的KNN算法
KNN学习容易受噪声影响，尤其是样本中的孤立点对分类或回归处理有很大的影响。因此通常也对已知样本进行滤波和筛选，去除对分类有干扰的样本。
K值得选取也会影响分类结果，因此需根据每类样本的数目和分散程度选取合理的K值，并且对不同的应用也要考虑K值得选择。
基于组合分类器的KNN改进算法
常用的组合分类器方法有投票法、非投票法、动态法和静态法等，比如简单的投票法中所有的基分类器对分类采取相同的权值；权值投票法中每个基分类器具有相关的动态权重，该权重可以随时间变化。
首先随机选择属性子集，构建多个K近邻分类器；然后对未分类元组进行分类；最后把分类器的分类结果按照投票法进行组合，将得票最多的分类器作为最终组合近邻分类器的输出。
基于核映射的KNN改进算法
将原空间Rn中的样本x映射到一个高维的核空间F中，突出不同类别样本之间的特征差异出，使得样本在核空间中变得线性可分或者近似线性可分，其流程如下所示：
2.png
实践代码
一个简单的KNN分类的MATLAB实践代码：
main.m文件
function main
trainData = [
0.6213 0.5226 0.9797 0.9568 0.8801 0.8757 0.1730 0.2714 0.2523
0.7373 0.8939 0.6614 0.0118 0.1991 0.0648 0.2987 0.2844 0.4692
];
trainClass = [
1 1 1 2 2 2 3 3 3
];
testData = [
0.9883 0.5828 0.4235 0.5155 0.3340
0.4329 0.2259 0.5798 0.7604 0.5298
];
% main
testClass = cvKnn(testData, trainData, trainClass);
% plot prototype vectors
classLabel = unique(trainClass);
nClass = length(classLabel);
plotLabel = {'r*', 'g*', 'b*'};
figure;
for i=1:nClass
A = trainData(:, trainClass == classLabel(i));
plot(A(1,:), A(2,:), plotLabel{i});
hold on;
end
% plot classifiee vectors
plotLabel = {'ro', 'go', 'bo'};
for i=1:nClass
A = testData(:, testClass == classLabel(i));
plot(A(1,:), A(2,:), plotLabel{i});
hold on;
end
legend('1: prototype','2: prototype', '3: prototype', '1: classifiee', '2: classifiee', '3: classifiee', 'Location', 'NorthWest');
title('K nearest neighbor');
hold off;
KNN.m文件：
function [Class, Rank] = cvKnn(X, Proto, ProtoClass, K, distFunc)
if ~exist('K', 'var') || isempty(K)
K = 1;%默认为K = 1
end
if ~exist('distFunc', 'var') || isempty(distFunc)
distFunc = @cvEucdist;
end
if size(X, 1) ~= size(Proto, 1)
error('Dimensions of classifiee vectors and prototype vectors do not match.');
end
[D, N] = size(X);
% Calculate euclidean distances between classifiees and prototypes
d = distFunc(X, Proto);
if K == 1, % sort distances only if K>1
[mini, IndexProto] = min(d, [], 2); % 2 == row%每列的最小元素
Class = ProtoClass(IndexProto);
if nargout == 2, % instance indices in similarity descending order
[sorted, ind] = sort(d'); % PxN
RankIndex = ProtoClass(ind); %,e.g., [2 1 2 3 1 5 4 1 2]'
% conv into, e.g., [2 1 3 5 4]'
for n = 1:N
[ClassLabel, ind] = unique(RankIndex(:,n),'first');
[sorted, ind] = sort(ind);
Rank(:,n) = ClassLabel(ind);
end
end
else
[sorted, IndexProto] = sort(d'); % PxN
clear d；
% K closest
IndexProto = IndexProto(1:K,:);
KnnClass = ProtoClass(IndexProto);
% Find all class labels
ClassLabel = unique(ProtoClass);
nClass = length(ClassLabel);
for i = 1:nClass
ClassCounter(i,:) = sum(KnnClass == ClassLabel(i));
end
[maxi, winnerLabelIndex] = max(ClassCounter, [], 1); % 1 == col
% Future Work: Handle ties somehow
Class = ClassLabel(winnerLabelIndex);
end
Eucdist.m文件
function d = cvEucdist(X, Y)
if ~exist('Y', 'var') || isempty(Y)
%% Y = zeros(size(X, 1), 1);
U = ones(size(X, 1), 1);
d = abs(X'.^2*U).'; return;
end
V = ~isnan(X); X(~V) = 0; % V = ones(D, N);
%clear V;
U = ~isnan(Y); Y(~U) = 0; % U = ones(D, P);
%clear U;
%d = abs(X'.^2*U - 2*X'*Y + V'*Y.^2);
d1 = X'.^2*U;
d3 = V'*Y.^2;
d2 = X'*Y;
d = abs(d1-2*d2+d3);
KNN分类结果
一些问题：
-
距离或相似度的衡量
什么是合适的距离衡量？距离越近应该意味着这两个点属于一个分类的可能性越大。
觉的距离衡量包括欧式距离、夹角余弦等。
对于文本分类来说，使用余弦(cosine)来计算相似度就比欧式(Euclidean)距离更合适。 -
类别的判定
投票决定：少数服从多数，近邻中哪个类别的点最多就分为该类。
加权投票法：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大（权重为距离平方的倒数） -
优点
简单，易于理解，易于实现，无需估计参数，无需训练
适合对稀有事件进行分类（例如当流失率很低时，比如低于0.5%，构造流失预测模型）
特别适合于多分类问题(multi-modal,对象具有多个类别标签)，例如根据基因特征来判断其功能分类，kNN比SVM的表现要好 -
缺点
懒惰算法，对测试样本分类时的计算量大，内存开销大，评分慢
可解释性较差，无法给出决策树那样的规则。 -
常见问题
1、k值设定为多大？
k太小，分类结果易受噪声点影响；k太大，近邻中又可能包含太多的其它类别的点。（对距离加权，可以降低k值设定的影响）
k值通常是采用交叉检验来确定（以k=1为基准）
经验规则：k一般低于训练样本数的平方根2、类别如何判定最合适？
投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更恰当一些。3、如何选择合适的距离衡量？
高维度对距离衡量的影响：众所周知当变量数越多，欧式距离的区分能力就越差。
变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化。4、训练样本是否要一视同仁？
在训练集中，有些样本可能是更值得依赖的。
可以给不同的样本施加不同的权重，加强依赖样本的权重，降低不可信赖样本的影响。5、性能问题？
kNN是一种懒惰算法，平时不好好学习，考试（对测试样本分类）时才临阵磨枪（临时去找k个近邻）。
懒惰的后果：构造模型很简单，但在对测试样本分类地的系统开销大，因为要扫描全部训练样本并计算距离。
已经有一些方法提高计算的效率，例如压缩训练样本量等。6、能否大幅减少训练样本量，同时又保持分类精度？
浓缩技术(condensing)
编辑技术(editing)
网友评论