相似性度量

引入

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

  • 相似性

  • 相异性, 也就是距离

  • 核函数

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

距离

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

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

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

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

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

Minkovski距离

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

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

d(a,b)=(∑i=1n∣ai−bi∣p)1pd(\mathbf{a}, \mathbf{b}) = (\sum\limits_{i=1}^{n}|a_i - b_i|^p)^{\frac{1}{p}}

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

  • p=1p=1, Manhattan distance或L1-norm distance

  • p=2p=2, Euclidean distance或L2-norm distance

  • p→+∞p\to +\infty, Chebyshev distance(切比雪夫距离)

Manhattan distance

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

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

d(a,b)=∑i=1n∣ai−bi∣d(\mathbf{a}, \mathbf{b}) = \sum\limits_{i=1}^{n}|a_i - b_i|

Euclidean distance

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

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

d(a,b)=∑i=1n∣ai−bi∣2d(\mathbf{a}, \mathbf{b}) = \sqrt{\sum\limits_{i=1}^{n}|a_i - b_i|^2}

Chebyshev distance

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

d(a,b)=lim⁡p→∞(∑i=1n∣ai−bi∣p)1p=max⁡(∣a1−b1∣,∣a2−b2∣⋯ ,∣an−bn∣)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][0, 1]的值来判断并比较相似程度. 常用的相似性度量方法有下面几种.

Cosine similarity, 余弦相似度

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

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

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

皮尔逊相关系数, Pearson Correlation Coefficient

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

ρa,b=cov(a,b)σaσb=n∑ixiyi−∑ixi∑iyin∑ixi2−(∑ixi)2n∑iyi2−(∑iyi)2\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.

参考资料

上一页聚类算法下一页聚类算法选择速查表

最后更新于

这有帮助吗？