距离

L_p距离

设特征空间X是n维实数空间R^n,x_i,x_j\in X,x_i=(x_i^{(1)},x_i^{(2)},...x_i^{(n)})^T,x_j=(x_j^{(1)},x_j^{(2)},...x_j^{(n)})^T,x_i,x_jL_p距离定义为:
L_p(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^p)^{\frac 1p} 这里p\geq1.
当p=2时,称为欧式距离(Euclidean distance)
L_2(x_i,x_j) = (\sum_{l=1}^{n}|x_i^l-x_j^l|^2)^{\frac 12}
当p=1时,称为曼哈顿距离(Manhattan distance)
L_1(x_i,x_j)=\sum_{l=1}^{n}|x_i^l-x_j^l|
p=\infty时,它是各个坐标距离的最大值即:
L_\infty (x_i,x_j)=max|x_i^l - x_i^l|

Lp距离间的关系

欧氏距离(euclidean distance)

对于平面上的二点P1(x1,y1),P2(x2,y2)
欧氏距离定义为:
d(P_1,P_2) =((x_1-x_2)^2+(y_1-y_2)^2)^{\frac 12}

曼哈顿距离(街区距离)

d(p_1,p_2) = |x_1-x_2|+|y_1-y_2|

闵可夫斯基距离

对于二个n维的变量A(x1,x2,…,xn)和B(y1,y2,…yn),闵氏距离为:
d(A,B) = (\sum_{k=1}^n(|x_k-y_k|^p))^{\frac{1}{p}}

海明距离

在信息论中,二个字符串之间的海明距离是二个字符串对应位置的不同字符数。
如:A=(1011101),B=(1001001)
海明距离=2

杰卡德(Jaccard)相似度

J(A,B) = \frac{|A∩B|} {|A∪B|}
其中A,B为集合
如网页相似度比较

网页 网页内容
A 努力建设国家级自然保护区
B 保护自然保护区义不容辞

①分词处理:
A = {‘努力’,‘建设’,‘国家级’,‘自然保护区’}
B = {‘保护’,‘自然保护区’,‘义不容辞’}
②计算相似度:
A∩B = {‘自然保护区’}
A∪B = {‘努力’,‘建设’,‘国家级’,‘自然保护区’,‘保护’,‘义不容辞’}
J(A,B) = 1/6 = 0.17

余弦相似度

对于向量a(x1,y1)和b(x2,y2)的余弦值为:
cos(Θ)=(a\bullet b) /(||a||×||b||) \\=\frac{(x_1,y_1)(x_2,y_2) }{[(x_1^2+y_1^2)^{\frac12}× (x_2^2+y_2^2)^{\frac12}]} \\=\frac{(x_1x_2+y_1y_2) }{[(x_1^2+y_1^2)^{\frac 12}× (x_2^2+y_2^2)^{\frac 12}]}
对于n维时,
x=(x1,x2,…,xn),y=(y1,y2,…,yn)
cos(Θ)=\frac{(x\bullet y) }{(||x||×||y||)}\\ =\frac{∑(x_i\bullet y_i)}{ (\sum x_i^2)^{\frac 12}×(∑y_i^2)^{\frac 12}}
例:网页文本相似度计算

文本编号 内容
A 数据价值是一种数据艺术
B 算法价值是一种算法艺术

① 分词处理:
A={‘数据’,‘价值’,‘是’,‘一种’,‘数据’,‘艺术’}
B={‘算法’,‘价值’,‘是’,‘一种’,‘算法’,‘艺术’}
② 计算并集A∪B
={‘数据’,‘价值’,‘是’,‘一种’,‘算法’,‘艺术’}
③ 词频计算:
A={数据(2),价值(1),是(1),一种(1),算法(0),艺术(1)}
B={数据(0),价值(1),是(1),一种(1),算法(2),艺术(1)}
④ 建立特征向量:
A=(2,1,1,1,0,1)
B=(0,1,1,1,2,1)
⑤ 相似度计算:
cos(Θ) = \frac{(2*0+1*1+1*1+1*1+0*2+1*1)} {[(22+12+12+12+02+12)^{\frac 12} ×(02+12+12+12+22+12)^{\frac 12}]} \\= 4/8 \\= 0.5

余弦相似度更侧重于方向问题。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。