相似性度量

引入

相似性度量(similarity measurement)是衡量点与点之间邻近属性的方法, 从具体的方法来说, 主要分为以下几类:

• 相似性

• 相异性, 也就是距离

• 核函数

首先从比较熟悉的距离方法开始.

距离

距离的值越小, 两个点之间越相似. 距离的定义满足三个属性:

• $d(\mathbf{a}, \mathbf{b})\ge0$, 且当$d(\mathbf{a}, \mathbf{b})=0$时, $\mathbf{a} = \mathbf{b}$

• $d(\mathbf{a}, \mathbf{b}) = d(\mathbf{b}, \mathbf{a})$, 对称性

• $d(\mathbf{a}, \mathbf{c})\le d(\mathbf{a}, \mathbf{b}) + d(\mathbf{b}, \mathbf{c})$, 三角不等式

满足以上三个条件的函数可以称为距离函数. 下面是一些在欧氏空间中的距离度量方法.

Minkovski距离

Minkovski距离也被称为p-norm distance.

对于两个点$\mathbf{a}=(a_1, a_2, \cdots, a_n)$以及点$\mathbf{b}=(b_1, b_2, \cdots, b_n)$, 两个点之间的Minkovski距离如下式表示:

$d(\mathbf{a}, \mathbf{b}) = (\sum\limits_{i=1}^{n}|a_i - b_i|^p)^{\frac{1}{p}}$

其中的参数$p$满足$p\ge1$, 且是实数域. $p$取以下三个值的时候, 为特殊的常用距离:

• $p=1$, Manhattan distance或L1-norm distance
• $p=2$, Euclidean distance或L2-norm distance
• $p\to +\infty$, Chebyshev distance(切比雪夫距离)

Manhattan distance

Manhattan distance(曼哈顿距离)也被称为L1-norm距离.

对于两个点$\mathbf{a}=(a_1, a_2, \cdots, a_n)$以及点$\mathbf{b}=(b_1, b_2, \cdots, b_n)$, 两个点之间的Manhattan距离如下式表示:

$d(\mathbf{a}, \mathbf{b}) = \sum\limits_{i=1}^{n}|a_i - b_i|$

Euclidean distance

Euclidean distance(欧式距离)也被称为L2-norm距离.

对于两个点$\mathbf{a}=(a_1, a_2, \cdots, a_n)$以及点$\mathbf{b}=(b_1, b_2, \cdots, b_n)$, 两个点之间的Euclidean距离如下式表示:

$d(\mathbf{a}, \mathbf{b}) = \sqrt{\sum\limits_{i=1}^{n}|a_i - b_i|^2}$

Chebyshev distance

对于两个点$\mathbf{a}=(a_1, a_2, \cdots, a_n)$以及点$\mathbf{b}=(b_1, b_2, \cdots, b_n)$, 两个点之间的Chebyshev距离如下式表示:

$d(\mathbf{a}, \mathbf{b}) = \lim\limits_{p\to\infty}(\sum\limits_{i=1}^{n}|a_i - b_i|^p)^{\frac{1}{p}}=\max(|a_1-b_1|,|a_2-b_2|\cdots,|a_n-b_n|)$

sklearn.metrics.pairwise

上述的距离度量函数, 在sklearn中都有现有的函数, 例如L2距离sklearn.metrics.pairwise.euclidean_distances.

对于距离, sklearn还有一个统一接口的简便函数: sklearn.metrics.pairwise_distances. 接受的参数如下:

• X: array, [n_samples_a, n_features] otherwise

• Y: array [n_samples_b, n_features], optional

• metric: string, or callable

  • 度量距离的方法

  • 可选的有

    • cityblock, cosine, euclidean, l1, l2, manhattan. 这些方法是sklearn中本身自带的方法

    • braycurtis, canberra, chebyshev, correlation, dice, hamming, jaccard, kulsinski, mahalanobis, minkowski, rogerstanimoto, russellrao, seuclidean, sokalmichener, sokalsneath, sqeuclidean, yule. 这些方法是来自于scipy.spatial.distance

• n_jobs: int or None, optional (default=None)

相似性

使用相似性度量两个点之间的相似程度, 肯定是值越大越相似. 一般来说, 相似性的度量函数会使用一个$[0, 1]$的值来判断并比较相似程度. 常用的相似性度量方法有下面几种.

Cosine similarity, 余弦相似度

对于两个点$\mathbf{a}=(a_1, a_2, \cdots, a_n)$以及点$\mathbf{b}=(b_1, b_2, \cdots, b_n)$, 两个点之间的余弦相似度如下表示:

$K(\mathbf{a},\mathbf{b})=\frac{\mathbf{a}\cdot \mathbf{b}}{||\mathbf{a}||\cdot ||\mathbf{b}||}$

其中$||\cdot||$表示L2-norm. 这样得到的结果是在

皮尔逊相关系数, Pearson Correlation Coefficient

相关系数, 或皮尔逊相关系数也称为线性相关系数. 常用来计算两个变量之间的线性相关程度. 对于两个点, 如果把每一个点都看成一个变量, 点向量中的每个值作为一个样本, 那么就可以计算出这两个点的线性相关系数. 皮尔逊相关系数的公式如下:

$$\begin{aligned} \rho_{\mathbf{a},\mathbf{b}} &= \frac{\text{cov}(\mathbf{a},\mathbf{b})}{\sigma_{\mathbf{a}}\sigma_{\mathbf{b}}} \\ &= \frac{n\sum\limits_{i}x_iy_i-\sum\limits_{i}x_i\sum\limits_{i}y_i}{\sqrt{n\sum\limits_{i}x_i^2-(\sum\limits_{i}x_i)^2}\sqrt{n\sum\limits_{i}y_i^2-(\sum\limits_{i}y_i)^2}} \end{aligned}$$

这种方法的优点在于不受线性转换的影响, 缺点为在维度很高的时候计算量大, 效率低.

核函数

核函数的原理就是把点从低维空间投影到高维空间中, 然后在高维空间中进行计算的到值, 通过这个值反应两个点之间的距离, 因此也是越小, 两个点之间越相似.

使用常见的核函数计算距离在sklearn.metrics.pairwise中都有对应的函数, 使用的方法参考sklearn的官方教程Pairwise metrics, Affinities and Kernels.

参考资料

• Pairwise metrics, Affinities and Kernels
• Pairwise metrics
• 常用的相似性度量
• 用于数据挖掘的聚类算法有哪些，各有何优势