距离

$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_j$ 的 $L_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$

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

最后编辑于：2018.12.25 10:40:07