相似度度量(Similarity Measurement）

在数据分析中，我们经常要评价样本之间的相似程度。通常我们会选择计算样本特征之间的距离，基础的和改进的度量方法有很多种，可以单独或组合的用于不同的情形之下。

欧式距离(Euclidean Distance)

最简单最常见的欧氏距离（也称欧几里得度量），指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。

计算公式：

适用场景：
在数据完整(无维度数据缺失)的情况下, 维度间的衡量单位是一致的, 否则需要标准化处理。
它适用于基于连续变量的数据，如图像和音频处理等领域。欧氏距离的值越小，则说明两个点越相似。

python实现：

import numpy as np

vec1 = np.array([1, 3, 4])
vec2 = np.array([4, 2, 4])

d = np.linalg.norm(vec1-vec2, ord=2)
# 或者
d = np.sqrt(np.sum(np.square(vec1-vec2)))

曼哈顿距离(Manhattan Distance)

背景：
在曼哈顿街区要从一个十字路口开车到另一个十字路口，驾驶距离显然不是两点间的直线距离。这个实际驾驶距离就是“曼哈顿距离”。曼哈顿距离也称为“城市街区距离”(City Block distance)。

定义：
曼哈顿距离是指在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。

计算公式：
二维平面两点A(x1,y1)与B(x2,y2)间的曼哈顿距离：

n维空间点A(x11,x12,…,x1n)与B(x21,x22,…,x2n)的曼哈顿距离：

适用场景：
在数据完整(无维度数据缺失)的情况下, 需要将空间划分成网格, 然后以网格为单位来进行度量, 允许4个方向。
它适用于在图像处理和物流领域等需要计算两点之间实际行进距离的场景。

python实现：

import numpy as np

vec1 = np.array([1, 3, 4])
vec2 = np.array([4, 2, 4])
 
d = np.linalg.norm(vec1-vec2, ord=1)
# 或者
d = np.sum(np.abs(vec1-vec2))

切比雪夫距离(Chebyshev Distance)

背景：
国际象棋中，国王可以直行、横行、斜行，所以国王走一步可以移动到相邻8个方格中的任意一个。国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？这个距离就叫切比雪夫距离。

定义：
切比雪夫距离是向量空间中的一种度量，二个点之间的距离定义为其各座标数值差的最大值。

计算公式：
二维平面两点A(x1,y1)与B(x2,y2)间的切比雪夫距离：

n维空间点A(x11,x12,…,x1n)与B(x21,x22,…,x2n)的切比雪夫距离：

或者：

适用场景：
需要将空间划分成网格, 然后以网格为单位来进行度量, 允许8个方向。

python实现：

import numpy as np

vec1 = np.array([1, 3, 4])
vec2 = np.array([4, 2, 4])

d = np.linalg.norm(vec1-vec2, ord=np.inf)
# 或者
d = np.abs(vec1-vec2).max()

闵可夫斯基距离(Minkowski Distance)

欧氏空间中的一种测度，被看做是欧氏距离和曼哈顿距离的一种推广。

计算公式：

适用场景：
闵氏距离不是一种距离，而是一组距离的定义，是对多个距离度量公式的概括性的表述。
当 p=1 时，就是曼哈顿距离
当 p=2 时，就是欧氏距离
当 p → ∞ 时，就是切比雪夫距离

python实现：

import numpy as np

vec1 = np.array([1, 3, 4])
vec2 = np.array([4, 2, 4])

"""
ord=1: 一范数
ord=2: 二范数
ord=np.inf: 无穷范数
"""
d = np.linalg.norm(vec1-vec2, ord=arg)

小结：

闵氏距离，包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。
e.g. 二维样本(身高[单位:cm],体重[单位:kg]),现有三个样本：a(180,50)，b(190,50)，c(180,60)。那么a与b的闵氏距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于a与c的闵氏距离。但实际上身高的10cm并不能和体重的10kg划等号。

闵氏距离的缺点：
(1)将各个分量的量纲(scale)，也就是“单位”相同的看待了;
(2)未考虑各个分量的分布（期望，方差等）可能是不同的。

汉明距离(Hamming Distance)

在信息论中，两个等长字符串之间的汉明距离(Hamming distance)是两个字符串对应位置的不同字符的个数。

计算公式：

适用场景：
信息编码(为了增强容错性，应使得编码间的最小汉明距离尽可能大)。常用于数据压缩和信息编码等领域。

python实现：

import numpy as np

vec1 = np.array([1, 1, 0, 1, 0, 1, 0, 0, 1])
vec2 = np.array([0, 1, 1, 0, 0, 0, 1, 1, 1])

d = len(np.nonzero(vec1-vec2)[0])
# 或者
d = np.shape(np.nonzero(vec1-vec2)[0])[0]

余弦相似度(Cosine Similarity)

余弦相似度，又称为余弦相似性，是通过计算两个向量的夹角余弦值来评估他们的相似度。

计算公式：

或者：

适用场景：
衡量两个向量方向的差异。它适用于基于离散变量的数据，如文本分类和推荐系统等领域。余弦相似度的值越大，则说明两个向量越相似。

python实现：

import numpy as np

vec1 = np.array([1, 3, 4])
vec2 = np.array([4, 2, 4])

d = np.dot(vec1,vec2)/(np.linalg.norm(vec1)*(np.linalg.norm(vec2)))

皮尔森相关系数(Pearson Correlation Coefficient)

用于度量两个变量（随机变量X与Y）之间的线性相关程度，相关系数的取值范围是[-1,1]。相关系数的绝对值越大，则表明X与Y相关度越高。当X与Y线性相关时，相关系数取值为1（正线性相关）或-1（负线性相关）。

计算公式：

适用场景：
用于计算两个连续变量之间线性相关程度的度量方式。反映两个变量是正相关还是负相关。

python实现：

import numpy as np

vec1 = np.array([1, 3, 4])
vec2 = np.array([4, 2, 4])

p = np.corrcoef(vec1, vec2)

杰卡德相似系数(Jaccard Similarity Coefficient)及杰卡德距离(Jaccard Distance)

用于比较有限样本集之间的相似性与差异性。

杰卡德相似系数计算公式：

杰卡德距离计算公式：

适用场景：

• 比较文本相似度，用于文本查重与去重；
• 计算对象间距离，用于数据聚类或衡量两个集合的区分度等。
  它适用于基于二元变量的数据，如文本分类和网络分析等领域。Jaccard相似系数的值越大，则说明两个集合越相似。

python实现：

import numpy as np
import scipy.spatial.distance as dist

vec1 = np.array([1, 1, 0, 1, 0, 1, 0, 0, 1])
vec2 = np.array([0, 1, 1, 0, 0, 0, 1, 1, 1])

d = dist.pdist(np.array([vec1, vec2]), "jaccard")

弗雷歇（Frechet）距离

背景：
Fréchet distance(弗雷歇距离)是法国数学家Maurice René Fréchet在1906年提出的一种路径空间相似形描述。

一个人牵着一条狗，共同走到目的地，试求：狗链子的最短值。

计算公式：
曲线A，B为度量空间S内的两条曲线，即A:[0,1] →S；B:[0,1]→S.。α和β是单位区间的两个重采样函数，α：[0:1] → [0,1]。弗雷彻距离为：

通俗的数学定义可以简化为：

适用场景：
对于空间路径的相似性比较适用。

python代码实现：
基于动态规划，求两条轨迹的弗雷彻距离，具体的，将轨迹A和B每步分为三类可能的路径状态，1）A和B都向前移动一步；2）A停留原地，B向前移动一步；3）A向前移动一步，B停留原地；

import numpy as np
from scipy.spatial import distance
from scipy.spatial import minkowski_distance
from scipy.spatial.distance import euclidean
import seaborn as sns
def Frechet_distance(exp_data,num_data):
    """
    cal fs by dynamic programming
    :param exp_data: array_like, (M,N) shape represents (data points, dimensions)
    :param num_data: array_like, (M,N) shape represents (data points, dimensions)
    # e.g. P = [[2,1] , [3,1], [4,2], [5,1]]
    # Q = [[2,0] , [3,0], [4,0]]
    :return:
    """
    P=exp_data
    Q=num_data
    p_length = len(P)
    q_length = len(Q)
    distance_matrix = np.ones((p_length, q_length)) * -1

    # fill the first value with the distance between
    # the first two points in P and Q
    distance_matrix[0, 0] = euclidean(P[0], Q[0])

    # load the first column and first row with distances (memorize)
    for i in range(1, p_length):
        distance_matrix[i, 0] = max(distance_matrix[i - 1, 0], euclidean(P[i], Q[0]))
    for j in range(1, q_length):
        distance_matrix[0, j] = max(distance_matrix[0, j - 1], euclidean(P[0], Q[j]))

    for i in range(1, p_length):
        for j in range(1, q_length):
            distance_matrix[i, j] = max(
                min(distance_matrix[i - 1, j], distance_matrix[i, j - 1], distance_matrix[i - 1, j - 1]),
                euclidean(P[i], Q[j]))
    # distance_matrix[p_length - 1, q_length - 1]
    sns.heatmap(distance_matrix, annot=True)
    return distance_matrix[p_length-1,q_length-1] # 最后一步即为弗雷彻距离

代码链接：
https://jekel.me/similarity_measures/similaritymeasures.html
https://github.com/nelsonwenner/shape-similarity
安装该库，该库结合了Frechet距离和Procrustes分析来检查两个形状/曲线之间的相似性。在实现过程中，首先使用Procrustes分析对曲线进行归一化，然后计算曲线之间的Fréchet距离。 注意事项： 该库的输入必须是节点数相等的。

小结：
基于点方法： EDR，LCSS，DTW等
基于形状的方法： Frechet， Hausdorff（该方法可以解决上述问题）
基于分段的方法：One Way Distance, LIP distance
基于特定任务的方法：TRACLUS， Road Network，grid等