相似性度量

度量不同样本之间的相似性时，通常需要计算样本间的距离。而采用不同的计算方法将关系到算法的性能和准确性。一些常用的相似性度量方法有：

欧氏距离

欧式距离是最易于理解的距离计算方法。

两个$n$维向量$a(x{11}, x{12}, x{13}, …, x{1n} )$与$b(x{21}, x{22}, x{23}, …, x{2n})$间的欧式距离：

$d_{12}=\sqrt {\sum_{k=1}^n (x_{1k} - x_{2k})^2}$

向量运算的形式：

$d_{12} = \sqrt{(a-b)(a-b)^T}$

例如常见在二维平面上两点$a(x_1, y_1)$与$b(x_2, y_2)$间的欧式距离：

$d_{12}=\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$

曼哈顿距离

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

两个$n$维向量$a(x{11}, x{12}, x{13}, …, x{1n} )$与$b(x{21}, x{22}, x{23}, …, x{2n})$间的曼哈顿距离：

$d_{12} = \sum_{k=1}^n|x_{1k}-x_{2k}|$

切比雪夫距离

在国际象棋中，国王走一步能够移动到相邻的任意一个。那么国王从各自$(x_1, y_1)$走到格子$(x_2, y_2)$最少需要的步数为$max(|x_2-x_1|, |y_2-y_1|)$。有一种类似的距离度量方法叫切比雪夫距离。

两个$n$维向量$a(x{11}, x{12}, x{13}, …, x{1n} )$与$b(x{21}, x{22}, x{23}, …, x{2n})$间的切比雪夫距离：

$d_{12}=max_i(|x_{1i}-x_{2i}|)$

这个公式的另一种等价形式是

$d_{12}=\lim_{k \rightarrow \infty }(\sum_{i=1}^n |x_{1i}-x_{2i}|^k)^\frac {1} {k}$

使用放缩法和夹逼法则证明两个公式等价

闵可夫斯基距离

闵氏距离不是一种距离，而是一组距离的定义。

闵氏距离的定义：
两个$n$维向量$a(x{11}, x{12}, x{13}, …, x{1n} )$与$b(x{21}, x{22}, x{23}, …, x{2n})$间的闵可夫斯基距离定义为：
$d_{12}=\sqrt[p]{\sum_{k=1}^n |x_{1k} - x_{2k}|^p}$
其中$p$是一个变参数：当$p=1$时，就是曼哈顿距离；当$p=2$时，就是欧氏距离；当$p\rightarrow \infty$ 时，就是切比雪夫距离。根据变参数的不同，闵氏距离可以表示一类的距离
闵氏距离的缺点
闵氏距离，包括曼哈顿距离、欧式距离和切比雪夫距离都存在明显的缺点。例如，二维样本(身高,体重)，其中身高范围是$150~190$，体重范围是50 ~ 60，有三个样本：$a(180,50)，b(190,50)，c(180,60)$。那么a与b之间的闵氏距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于a与c之间的闵氏距离，但是身高的10cm真的等价于体重的10kg么？因此用闵氏距离来衡量这些样本间的相似度很有问题。
简单说来，闵氏距离的缺点主要有两个：1. 将各个分量的量纲(scale)，也就是“单位”当作相同的看待了。2. 没有考虑各个分量的分布(期望、方差等)可能是不同的。

标准化欧式距离

标准化欧式距离是针对简单欧式距离的缺点而做的一种改进方案。标准欧式距离的思路：面对数据各维度分量的分布不一样，我们先将各个分量都”标准化”到均值、方差相等。那么均值和方差标准化到多少呢？假设样本集$X$的均值（mean）为$m$，标准差(standard deviation)为$s$，那么$X$的”标准化变量“表示为：

标准化变量的数学期望为0，方差为1。因此样本集的标准化过程(standardization)用公式描述就是：

$X^*=\frac{X-m}{s}$

标准化后的值 = （标准化前的值 - 分量的均值）/ 分量的标准差

经过简单的推导就可以得到两个$n$维向量$a(x{11}, x{12}, x{13}, …, x{1n} )$与$b(x{21}, x{22}, x{23}, …, x{2n})$间的标准化欧式距离的公式：

$d_{12}=\sqrt{\sum_{k=1}^n(\frac{x_{1k}-x_{2k}}{s_k})^2}$

如果将方差的倒数看成是一个权重，这个公式可以看成是一种加权欧式距离(Weighted Euclidean distance)。

马氏距离(Mahalanobis Distance)

有$M$个样本向量$X_1, …, X_m$，协方差矩阵记为$S$，均值记为向量$\mu$的马氏距离表示为：

$D(X)=\sqrt{(X-\mu)^T S^{-1} (X-\mu)}$

而其中向量$X_i$与向量$X_j$之间的马氏距离定义为：

$D(X_i, X_j)=\sqrt{(X_i-X_j)^T S^{-1} (X_i-X_j)}$

若协方差矩阵是单位矩阵(各个样本向量之间独立同分布)，则公式为：

$D(X_i, X_j)=\sqrt{(X_i-X_j)^T (X_i-X_j)}$

即为欧式距离。

若协方差矩阵是对角矩阵，公式变成了标准化欧氏距离。

马氏距离的优缺点：量纲无关，排除变量之间的相关性的干扰

夹角余弦(Cosine)

几何中夹角余弦可用来衡量两个向量方向的差异，机器学习中借用这一概念来衡量样本向量之间的差异。

对于两个$n$维向量$a(x{11}, x{12}, x{13}, …, x{1n} )$与$b(x{21}, x{22}, x{23}, …, x{2n})$，可以使用类似于夹角余弦的概念来衡量它们间的相似程度：

$cos\theta = \frac{a \cdot b}{|a||b|}$

即：

$cos(\theta)=\frac{\sum_{k=1}^n x_{1k} x_{2k}}{\sqrt{\sum_{k=1}^n x_{1k}^2} \sqrt{\sum_{k=1}^n x_{2k}^2}}$

在二维空间中向量$A(x_1, y_1)$ 与向量$B(x_2, y_2)$的夹角余弦公式：

$cos\theta = \frac{x_1 x_2 + y_1 y_2}{\sqrt{x_1^2 + y_1^2} \sqrt{x_2^2 + y_2^2}}$

汉明距离(Hamming distance)

定义：两个等长字符串$s_1$与$s_2$之间的汉明距离定义为将其中一个变为另外一个所需要做的最小替换次数。例如字符串”1111”与”1001”之间的汉明距离为2。

应用：信息编码（为了增强容错性，应使得编码间的最小汉明距离尽可能大）。

杰卡德距离 & 杰卡德相似系数(Jaccard similarity coefficient)

杰卡德相似系数
两个集合A和B的交集元素在A, B的并集中所占的比例，称为两个集合的杰卡德相似系数，用符号$J(A,B)$表示：
$J(A,B)=\frac{|A\cap B|}{|A \cup B|}$
杰卡德相似系数是衡量两个集合的相似度一种指标
杰卡德距离
与杰卡德相似系数相反的概念是杰卡德距离(Jaccard distance)。杰卡德距离可用如下公式表示：
$J_{\sigma}(A, B) = 1-J(A,B) = \frac{|A \cup B|-|A \cap B|}{|A \cup B|}$
杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分的。
杰卡德相似系数与杰卡德距离的应用
可将杰卡德相似系数用在衡量样本的相似度上。
样本A与样本B是两个$n$维向量，而且所有维度的取值都是0或1。例如：$A(0111)$和$B(1011)$。我们将样本看成是一个集合，1表示集合包含该元素，0表示集合不包含该元素。
$p$：样本A与B都是1的维度的个数
$q$：样本A是1，样本B是0的维度的个数
$r$：样本A是0，样本B是1的维度的个数
$s$：样本A与B都是0的维度的个数
那么，样本A与B的杰卡德相似系数可表示为：
这里$p+q+r$可理解为A与B的并集的元素个数，而p是A与B的交集的元素个数。
而样本A与B的杰卡德距离表示为：
$J=\frac{p}{p+q+r}$

信息熵(Information Entropy)

信息熵是衡量分布的混乱程度或分散程度的一种度量。分布越分散(或者说分布越平均)，信息熵就越大。分布越有序（或者说分布越集中），信息熵就越小。

计算给定的样本集$X$的信息熵的公式：

$Entropy(X)=\sum_{i=1}^n p_i log_2\frac{1}{p_i}$

其中，$n$表示样本集$X$的分类数，$p_i$为$X$中第$i$类元素出现的概率。

信息熵越大表明样本集分类越分散，即随机变量的不确定性越大，信息熵越小则表明样本集分类越集中，此时随机变量的不确定性减小。当样本集$S$中$n$个分类出现的概率一样大时（都是$1/n$），信息熵取最大值$log_2n$。当$S$只有一个分类时，信息熵取最小值0。

其实熵拐了两个弯。熵意思是信息的混乱程度，越混乱，熵越大。分布越均匀，则是越混乱。

[1]. https://www.jianshu.com/p/991182ec5968

[2]. https://blog.csdn.net/wguangliang/article/details/49667109