k-nearest neighbors algorithm

代码在https://github.com/Vast-Stars/Algorithm/tree/master/KNN 上可以看到。欢迎Star

一. 算法介绍

Main Idea：找出 $K$ 个距离未知样本$x$ 最近的已知样本点，以其中多数已知样本的类别作为$x$ 的类别。

需要考虑的问题：

算法优化。由于环境为Matlab，故无需考虑。
距离的定义。根据特征空间性质定义距离，一般有以下几种：
- Euclidean Distance ： $ d_{s,t}^2=(x_s-x_t)·(x_s-x_t)’ $ . 欧氏距离虽然很有用，但也有明显的缺点。一：它将样品的不同特征之间的差别等同看待，这一点有时不能满足实际要求。二：它没有考虑各特征的数量级(量纲)，一般需要先对原始数据进行规范化处理再进行距离计算。
- Standardized Euclidean distance : $ d_{s,t}^2=(x_s-x_t)V ^ {-1} (x_s-x_t)’ $ where V is the n-by-n diagonal matrix whose $j$th diagonal element is ${S(j) }^2 $, where $S$ is the vector of standard deviations. 相比单纯的欧氏距离，标准欧氏距离能够有效的解决上述缺点。注意，这里的$V$在许多Matlab函数中是可以自己设定的，不一定非得取标准差，可以依据各变量的重要程度设置不同的值，如knnsearch函数中的Scale属性。
- Mahalanobis distance : $ d_{s,t}^2=(x_s-x_t)C^{-1}(x_s-x_t)’ $ , C为协方差矩阵. 与欧式距离不同的是它考虑到各种特性之间的联系,并且是尺度无关的.如果协方差矩阵为单位矩阵,那么马氏距离就简化为欧式距离,如果协方差矩阵为对角阵,则其也可称为正规化的欧氏距离。缺点是：1 马氏距离的计算是建立在总体样本的基础上的，因为C是由总样本计算而来，所以马氏距离的计算是不稳定的；2 在计算马氏距离过程中，要求总体样本数大于样本的维数。3 协方差矩阵的逆矩阵可能不存在。
- Manhattan Distance ：$D_{s,t}= \sum_{j=1}^n|x_{s_j}-x_{t_j}|$ . 曼哈顿距离是闵可夫斯基距离的一种特例(当$p=1$ 时)。
- Minkowski Distance : $D_{s,t}= \sqrt[p]{ \sum_{j=1}^n|x_{s_j}-x_{t_j} | ^p } $ . $p=1,2, \infty $ 时，闵可夫斯基距离分别等价于曼哈顿距离、欧氏距离、切比雪夫距离。闵可夫斯基距离由于是欧氏距离的推广，所以其缺点与欧氏距离大致相同。
- Chebychev Distance ： $D_{s,t}= \max \limits_j |x_{s_j}-x_{t_j}|$
- Cosine Distance : $ D_{s,t}=1- \frac{x_s x_t’} { | x_s |_{2} | x_t | _{2} } $ 与Jaccard距离相比，Cosine距离不仅忽略0-0匹配，而且能够处理非二元向量，即考虑到变量值的大小。
- Correlation distance : $d_{s,t}=1- \frac{x_s x_t’} { \sqrt[]{ (x_s- \bar{x_s} )(x_t- \bar{x_t} )’}. \sqrt{ (x_t- \bar{x_t} ).(x_t- \bar{x_t} ) ‘ } } $ . Correlation距离主要用来度量两个向量的线性相关程度。
- Hamming Distance: $ d_{s,t}=( \frac{ \sharp (x_{s_j} \neq x_{t_j} ) } {n} )$ . 两个向量之间的汉明距离的定义为两个向量不同的变量个数所占变量总数的百分比。
- Jaccard Distance: $ d_{s,t}=( \frac{ \sharp [ (x_{s_j} \neq x_{t_j} ) \cap ( (x_{s_j} \neq 0) \cup(x_{t_j} \neq 0) ) ] } { \sharp (x_{s_j} \neq0) \cup(x_{t_j} \neq 0) } )$ . Jaccard距离常用来处理仅包含非对称的二元(0-1)属性的对象。很显然，Jaccard距离不关心0-0匹配，而Hamming距离关心0-0匹配。
- Spearman Distance: $d_{s,t}=1- \frac{ (r_s- \overline{r_s} )(r_t- \overline{r_t} )’} { \sqrt[]{ (r_s- \overline{r_s} ) (r_s- \overline{r_s} )’}. \sqrt{ (r_t- \overline{r_t} ) (r_t- \overline{r_t} )’} }$ .

KNN是一种lazy learning 算法，不需要预先训练，只需把所有训练数据载入内存，即可构成分类器。分类器也不含参数信息。

二. 实现

function Test_Y=KNN(Train_X,Train_Y,Test_X,K)
%% Parameter:
% 	Train_X should be m*n and Train_Y should be m*1;
% 	Test_X  should be p*n ;
%   K should be postive;
%% Return:
%   Test_Y will be p*1;
[Dis,I]=pdist2(Train_X,Test_X,'euclidean','Smallest',K);
Test_Y=mode(Train_Y(I) )';
end