在计算机人工智能领域,距离(distance)、相似度(similarity)是经常出现的基本概念,它们在自然语言处理、计算机视觉等子领域有重要的应用,而这些概念又大多源于数学领域的度量(metric)、测度(measure)等概念。
曼哈顿距离
曼哈顿距离又称计程车几何距离或方格线距离,是由十九世纪的赫尔曼·闵可夫斯基所创词汇 ,为欧几里得几何度量空间的几何学之用语,用以标明两个点上在标准坐标系上的绝对轴距之总和。曼哈顿距离的正式意义为L1-距离或城市区块距离,也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上,坐标\((x_1, y_1)\)的点\(P_1\)与坐标\((x_2, y_2)\)的点\(P_2\)的曼哈顿距离为:
$$d=|x_1 -x_2| + |y_1 -y_2| $$
等价于下面的汇总式:
$$d=\sum_{i=1}^n|x_i-y_i|$$
欧几里得距离
欧几里得度量(euclidean metric)也称欧氏距离: 在数学中,欧几里得距离或欧几里得度量是欧几里得空间中两点间“普通”(即直线)距离。在欧几里得空间中,点\(x =(x_1,x_2,...,x_n)\)和 \(y =(y_1,y_2,...,y_n)\)之间的欧氏距离为:
$$d(x,y)=\sqrt{(x_1-y_1)^2 + (x_2-y_2)^2 + ... + (x_i-y_i)^2}$$
等价于下面的汇总式:
$$d=\sqrt{\sum_{i=1}^n(x_i-y_i)^2}$$
切比雪夫距离
数学上,切比雪夫距离(Chebyshev distance)或是\(L_∞\)度量是向量空间中的一种度量,二个点之间的距离定义为其各座标数值差的最大值。以\(p(x_1,y_1)\)和\(q(x_2,y_2)\)二点为例,其切比雪夫距离为
$$D_{Chebyshev}(p,q)=max(|x_2-x_1|,|y_2-y_1|)$$
一般形式为:
$$D_{Chebyshev}(p,q)=\max_{i}(|p_i-q_i|)=\lim_{k \to \infty}(\sum_{i=1}^n|p_i-q_i|^k)^{1/k}$$
闵可夫斯基距离
闵可夫斯基距离或闵氏距离(Minkowski Distance):以俄罗斯数学家闵可夫斯基命名的距离;是欧式距离的推广,闵氏距离不是一种距离,而是一组距离的定义。其定义如下:
$$d=\sqrt[p]{\sum_{i=1}^n|x_i-y_i|^p}$$
从上面公式可以看出:
- 当\(p=1\)时,就是曼哈顿距离
- 当\(p=2\)时,就是欧氏距离
- 当\(p→∞\)时,就是切比雪夫距离
马氏距离
马氏距离(Mahalanobis distance): 由印度统计学家马哈拉诺比斯(P. C. Mahalanobis)提出,表示数据的协方差距离。它是一种有效的计算两个未知样本集的相似度的方法。与欧氏距离不同的是它考虑到各种特性之间的联系(例如:一条关于身高的信息会带来一条关于体重的信息,因为两者是有关联的)并且是尺度无关的(scale-invariant),即独立于测量尺度,如果协方差矩阵为单位矩阵,马氏距离就简化为欧式距离,如果协方差矩阵为对角阵,其也可称为正规化的马氏距离。 计算公式如下:
对于一个均值为\(\mu=(\mu_1,\mu_2,\mu_3,...\mu_p)^T\) ,协方差矩阵为\(Σ\) ,其马氏距离为:
$$D_M(x)=\sqrt{( x-\mu)^TΣ^{-1}( x- \mu)}$$
马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为\(Σ\) 的随机变量 \(\vec x\)与\(\vec y\)的差异程度:
$$d(\vec x,\vec y)=\sqrt{(\vec x-\vec y)^TΣ^{-1}(\vec x-\vec y)}$$
汉明距离
在信息论中,两个等长字符串之间的汉明距离(英语:Hamming distance)是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如:
- 1011101与1001001之间的汉明距离是2
- 2143896与2233796之间的汉明距离是3
- toned 与 roses 之间的汉明距离是3
余弦相似度
余弦相似性通过测量两个向量的夹角的余弦值来度量它们之间的相似性。0度角的余弦值是1,而其他任何角度的余弦值都不大于1;并且其最小值是-1。从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向。两个向量有相同的指向时,余弦相似度的值为1;两个向量夹角为90°时,余弦相似度的值为0;两个向量指向完全相反的方向时,余弦相似度的值为-1。这结果是与向量的长度无关的,仅仅与向量的指向方向相关。余弦相似度通常用于正空间,因此给出的值为0到1之间。给定两个属性向量, \(A\)和\(B\),其余弦相似性\(θ\)由点积和向量长度给出,如下所示:
$$\cos \theta = {A \cdot B\over ||A||\ ||B||} = {\sum_{i=1}^n A_i \times B_i \over \sqrt{\sum_{i=1}^n(A_i)^2} \times \sqrt{\sum_{i=1}^n(B_i)^2}}$$
这里的 \(A_{i}\)和 \(B_{i}\)分别代表向量 \(A\)和 \(B\)的各分量
杰卡德距离
杰卡德距离(Jaccard Distance) :它是杰卡德相似系数的补集,被定义为1减去Jaccard相似系数。而杰卡德相似系数(Jaccard similarity coefficient),也称杰卡德指数(Jaccard Index),是用来衡量两个集合相似度的一种指标。
Jaccard相似指数用来度量两个集合之间的相似性,它被定义为两个集合交集的元素个数除以并集的元素个数。
$$J(A,B)={|A \bigcap B|\over |A \bigcup B|} $$
杰卡德距离如下:
$$d_J(A,B) = 1-J(A,B)={ |A \bigcup B|-|A \bigcap B|\over |A \bigcup B|}$$
性质:
1) 若\(A\)、\(B\)两个集合都为空,则\(J(A,B) = 1\)
2) \(0\leq J(A,B)\leq1\)
皮尔森相关系数
皮尔森相关系数(Pearson correlation coefficient):也称皮尔森积矩相关系数(Pearson product-moment correlation coefficient) ,是一种线性相关系数。皮尔森相关系数是用来反映两个变量线性相关程度的统计量。相关系数用r表示,其中n为样本量,分别为两个变量的观测值和均值。r描述的是两个变量间线性相关强弱的程度。r的绝对值越大表明相关性越强。
计算公式:
$$r={\sum_{i=1}^n(X_i-\overline x)(Y_i-\overline y) \over \sqrt{\sum_{i=1}^n (X_i-\overline x)^2} \sqrt{\sum_{i=1}^n (Y_i-\overline y)^2}}$$
分子是两个集合的交集大小,分母是两个集合大小的几何平均值。是余弦相似性的一种形式
编辑距离
编辑距离(Edit Distance):又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。一般来说,编辑距离越小,两个串的相似度越大。俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。编辑距离越小的两个字符串越相似,当编辑距离为0时,两字符串相等。
计算公式:
$$f(n) = \begin{cases}max(i,j) & \text{if min(i,j)=0}, \\ min{\begin{cases} lev_{a,b}(i-1,j)+1 \\ lev_{a,b}(i,j-1)+1 \\ lev_{a,b}(i-1,j-1)+1_{(a_i \neq b_j)} \end{cases}} & \text{otherwise.}\end{cases}$$
K-L散度
K-L散度(Kullback-Leibler Divergence):即相对熵;是衡量两个分布(P、Q)之间的距离;越小越相似。
计算公式:
$$D(P||Q)=\sum_{i=1}^nP(i)log{P(i) \over Q(i)}$$
本博客文章除特别声明,全部都是原创!
原创文章版权归过往记忆大数据(过往记忆)所有,未经许可不得转载。
本文链接: 【机器学习中常用的距离公式】(https://www.iteblog.com/archives/2317.html)