| KNN算法中常用的距离计算公式 | 您所在的位置：网站首页 › cos后面如果是数字怎么算 › 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)的曼哈顿距离 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
类型的距离
|
【本文地址】
公司简介
联系我们