本站分享大数据、数据分析、数据挖掘、数据库、商业智能(BI)、数据分析师、培训课程考试认证等相关信息!【广告合作】在线联系联系我们数据分析QQ交流群:331864445

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

matlab培训 cdadata 57℃ 0评论

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

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

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

T=(x1,y1),(x2,y2),...,(xN,yN)

其中,xiXRn为实例的特征向量,yiY={c1,c2,...,ck}为实例的类别,i=1,2,...,N;实例特征向量x;
输出: 实例x所属的类y
(1) 根据给点的距离度量,在训练集T中找出与x最近邻的k个点,涵盖着k个点的领域,记为Nk(x);
(2) 在Nk(x)中根据分类决策规则(如多数表决),决定x的类别y:
y=argmaxcjxiNk(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,xjX,xi=(x(1)i,x(2)i,...,x(n)i)T, xj=(x(1)j,x(2)j,...,x(n)j)T, xi,xjLp距离定义为:

Lp(xi,xj)=(nl=1|x(l)ix(l)j|p)1p

这里 p1
p=1时,称为曼哈顿距离(Manhattan distance), 公式为:
L1(xi,xj)=nl=1|x(l)ix(l)j|

p=2时,称为欧式距离(Euclidean distance),即
L2(xi,xj)=(nl=1|x(l)ix(l)j|2)12

p=时,它是各个坐标距离的最大值,计算公式为:
L(xi,xj)=maxl|x(l)ix(l)j|

案例1,已知二维空间的3个点 x1=(1,1)T, x2=(5,1)T, x3=(4,4)T, 试求在p取不同值时,Lp距离下x1的最近邻点。
解析:对于x1x2,由于x1x2115在第2维上 数字都是1,所以计算x1x2的距离时只需计算x(1)1x(1)2即可,Lp(x1,x2)=4.
对于x1x3, 由于x1x3在第1维上的数字不相同,在第2维上的数字也不相同,则x1x3的曼哈顿距离为:
L1(x1,x3)=nl=1|x(l)ix(l)j|=2l=1|x(l)ix(l)j|=3+3=6

x1x3的欧式距离为:
L2(xi,xj)=(nl=1|x(l)ix(l)j|2)12=(2l=1|x(l)ix(l)j|2)12=32=42.4

x1x3L3距离为:
L3(xi,xj)=(nl=1|x(l)ix(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)所示:

KNN算法中常用的距离计算公式_knn算法 距离
图(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)所示:

KNN算法中常用的距离计算公式_knn算法 距离
图(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)所示:

KNN算法中常用的距离计算公式_knn算法 距离
图(3)求L3类型的距离

 

转载请注明:数据分析 » KNN算法中常用的距离计算公式_knn算法 距离_knn算法 matlab

喜欢 (2)or分享 (0)

您必须 登录 才能发表评论!