KNN算法中常用的距离计算公式　

关键词： knn算法 距离 knn算法 knn分类算法

KNN，英文全称为K-nearst neighbor，中文名称为K近邻算法，它是由Cover和Hart在1968年提出来的。
KNN算法流程：
输入：训练数据集

T=(x1,y1),(x2,y2),...,(xN,yN)
其中，xi∈X⊆Rn为实例的特征向量，yi∈Y={c1,c2,...,ck}为实例的类别，i=1,2,...,N；实例特征向量x;
输出: 实例x所属的类y
(1) 根据给点的距离度量，在训练集T中找出与x最近邻的k个点，涵盖着k个点的领域，记为Nk(x);
(2) 在Nk(x)中根据分类决策规则(如多数表决)，决定x的类别y:
y=argmaxcj∑xi∈Nk(x)I(yi=cj),i=1,2,...,N;

在上式中，I为指示函数，即当yi=cj时，I为1，否则I为0。
KNN特殊情况是k=1的情形，称为最近邻算法。对于输入的实例点(特征向量)x，最近邻算法将训练数据集中与x最近邻点的类作为x的类。
在KNN算法中，常用的距离有三种，分别为曼哈顿距离、欧式距离和闵可夫斯基距离。
设特征空间X是n维实数向量空间Rn, xi,xj∈X,xi=(x(1)i,x(2)i,...,x(n)i)T, xj=(x(1)j,x(2)j,...,x(n)j)T, xi,xj的Lp距离定义为：

Lp(xi,xj)=(∑nl=1|x(l)i−x(l)j|p)1p
这里 p≥1
当p=1时，称为曼哈顿距离(Manhattan distance), 公式为：
L1(xi,xj)=∑nl=1|x(l)i−x(l)j|
当p=2时，称为欧式距离(Euclidean distance)，即
L2(xi,xj)=(∑nl=1|x(l)i−x(l)j|2)12
当p=∞时，它是各个坐标距离的最大值，计算公式为：
L∞(xi,xj)=maxl|x(l)i−x(l)j|
案例1，已知二维空间的3个点 x1=(1,1)T, x2=(5,1)T, x3=(4,4)T, 试求在p取不同值时，Lp距离下x1的最近邻点。
解析：对于x1与x2,由于x1与x2在第1维上的数字分别为1、5，在第2维上 数字都是1，所以计算x1与x2的距离时只需计算x(1)1和x(1)2即可，Lp(x1,x2)=4.
对于x1与x3, 由于x1与x3在第1维上的数字不相同，在第2维上的数字也不相同，则x1与x3的曼哈顿距离为:
L1(x1,x3)=∑nl=1|x(l)i−x(l)j|=∑2l=1|x(l)i−x(l)j|=3+3=6
则x1与x3的欧式距离为:
L2(xi,xj)=(∑nl=1|x(l)i−x(l)j|2)12=(∑2l=1|x(l)i−x(l)j|2)12=32√=42.4
则x1与x3的L3距离为:
L3(xi,xj)=(∑nl=1|x(l)i−x(l)j|3)13=3.78　　在Matlab，可以直接求两个向量之间的距离。
设xa=(1,1), xa=(4,4)，向量xa,xb组成矩阵D =[1 1; 4 4]
（a）求向量(1,1)、(5,1)的曼哈顿距离

在Matlab，可以直接求两个向量之间的距离。
设xa=(1,1), xa=(4,4)，向量xa,xb组成矩阵D =[1 1; 4 4]
（a）求向量(1,1)、(5,1)的曼哈顿距离

D = [1 1; 4 4];
%%求曼哈顿距离
res = pdist(D, 'cityblock')

如图(1)所示：

图(1) 使用pdist( XXX , ‘cityblock’)求曼哈顿距离
（b）求向量(1,1)、(5,1)的欧式距离
在Minkowski distance公式中，当p=2时，就是欧式距离，而Minikowski的函数为 pdist(XXX, ‘minkowski’,2)，代码如下：

D = [1 1; 4 4]
%%求欧式距离
res = pdist(D, 'minkowski',2)

如图(2)所示：

图(2) 使用pdist(XXX, ‘minkowski’,2)求曼哈顿距离　　（c）求向量(1,1)、(5,1)的L3距离
调用pdist(XXX, ‘minkowski’,3)，代码如下：

D = [1 1; 4 4];
%%求L3类型的距离
res = pdist(D, 'minkowski',3)

如图(3)所示:

图(3)求L3类型的距离