相似度度量方式及原理

引子

对于一个聚类问题，假设数据集中包含n个无标记样本 $D=\{X_1,X_2,...,X_n\}$ ，其中任意样本 $X_i=(x_{i1},x_{i2},...,x_{id})$ 是一个d维向量。将给定的样本集划分成若干个互不相交的子集，使得子集内样本的相似性尽可能大，不同子集中样本的相似性尽可能小。

用距离作为相似性度量，最常用的是欧式距离：对于一个划分 $C={C_1,C_2,...,C_k}$ ，要使其为最优划分，所有类的样本到各自类中心的距离之和应该最小。对类 $C_i$ ，其类中心为 $M_i=\frac{1}{|C_i|}\displaystyle \sum_{X\in{C_i}}X,(1<=i<=k)$ 该类样本到其类中心的距离之和为 $\displaystyle \sum_{X\in{C_i}}||X-M_i||$ ，所以，所有类的样本到各自的类中心的距离之和为 $\displaystyle \sum^k_{i=1}\displaystyle \sum_{X\in{C_i}}||X-M_i||$ 。于是，最优的划分应该满足： $\begin{cases}min\displaystyle \sum^k_{i=1}\displaystyle \sum_{X_j\in{C_i}}||X_j-M_i||^2 \\s.t. \quad \cup_{i=1}^kC_i=D \\ \quad \qquad C_i\cap{C_j}=\Phi\\\quad \qquad i,j\in\{1,2,...,k\}\\\quad \qquad i\neq{j }\end{cases}$

那么，思考一下，通过距离衡量两个样本之间的相似度的方法的优缺点，还可以通过什么来度量呢？

不仅是聚类问题，在数据分析和数据挖掘的过程中，我们需要知道个体间差异的大小，进而评价个体的相似性和类别，比如数据分析中的相关分析，数据挖掘中的分类和聚类算法，如K最近邻（KNN）和K均值（K-Means）。

为了方便下面的解释和举例，先设定我们要比较X个体和Y个体间的差异，它们都包含了n个维度的特征，即 $X=(x_1,x_2,x3,…,x_n)$ ， $Y=(y_1,y_2,y_3,…,y_n)$ 。衡量两者的差异的方法，主要分为距离度量和相似度度量。

距离度量：

距离度量（Distance）用于衡量个体在空间上存在的差异，距离越远说明个体间差异越大。

欧几里得距离(Euclidean Distance)

欧氏距离是最常见的距离度量，衡量的是多维空间中各个点之间的绝对距离。公式如下： $dist(X,Y)=\sqrt{\displaystyle\sum_{i=1}^n(x_i-y_i)^2}$

因为计算是基于各维度特征的绝对数值，所以欧氏度量需要保证各维度指标在相同的刻度级别，比如对身高（cm）和体重（kg）两个单位不同的指标使用欧式距离可能使结果失效。

明可夫斯基距离(Minkowski Distance)

明氏距离是欧氏距离的推广，是对多个距离度量公式的概括性的表述。公式如下： $dist(X,Y)=(\displaystyle\sum_{i=1}^n|x_i-y_i|^p)^{1/p}$ ,这里的p值是一个变量，当p=2的时候就得到了上面的欧氏距离。

曼哈顿距离(Manhattan Distance)

曼哈顿距离来源于城市区块距离，是将多个维度上的距离进行求和后的结果，即当上面的明氏距离中p=1时得到的距离度量公式，如下： $dist(X,Y)=\displaystyle\sum_{i=1}^n|x_i-y_i|$

切比雪夫距离(Chebyshev Distance)

切比雪夫距离起源于国际象棋中国王的走法，我们知道国际象棋国王每次只能往周围的8格中走一步，那么如果要从棋盘中A格(x1, y1)走到B格(x2, y2)最少需要走几步？扩展到多维空间，其实切比雪夫距离就是当p趋向于无穷大时的明氏距离： $dist(X,Y)=\displaystyle\lim_{p \to\infty}(\displaystyle\sum_{i=1}^n|x_i-y_i|^p)^{1/p}=\max{|x_i-y_i|}$ ，其实上面的曼哈顿距离、欧氏距离和切比雪夫距离都是明可夫斯基距离在特殊条件下的应用。

马哈拉诺比斯距离(Mahalanobis Distance)

既然欧几里得距离无法忽略指标度量的差异，所以在使用欧氏距离之前需要对底层指标进行数据的标准化，而基于各指标维度进行标准化后再使用欧氏距离就衍生出来另外一个距离度量——马哈拉诺比斯距离（Mahalanobis Distance），简称马氏距离。

相似度度量

相似度度量（Similarity），即计算个体间的相似程度，与距离度量相反，相似度度量的值越小，说明个体间相似度越小，差异越大。

向量空间余弦相似度(Cosine Similarity)

余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。相比距离度量，余弦相似度更加注重两个向量在方向上的差异，而非距离或长度上。公式如下： $\sin(X,Y)=\cos\theta=\frac{\vec{x}·\vec{y}}{||x||·||y||}$

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

即相关分析中的相关系数r，分别对X和Y基于自身总体标准化后计算空间向量的余弦夹角。公式如下： $r(X,Y)=\frac{n\sum{xy}-\sum{x}\sum{y}}{\sqrt{n\sum{x^2}-(\sum{x}^2)}·\sqrt{n\sum{y^2}-(\sum{y})^2}}$

Jaccard相似系数(Jaccard Coefficient)

Jaccard系数主要用于计算符号度量或布尔值度量的个体间的相似度，因为个体的特征属性都是由符号度量或者布尔值标识，因此无法衡量差异具体值的大小，只能获得“是否相同”这个结果，所以Jaccard系数只关心个体间共同具有的特征是否一致这个问题。如果比较X与Y的Jaccard相似系数，只比较xn和yn中相同的个数，公式如下： $Jaccard(X,Y)=\frac{X\cap{Y}}{X\cup{Y}}$

调整余弦相似度(Adjusted Cosine Similarity)

虽然余弦相似度对个体间存在的偏见可以进行一定的修正，但是因为只能分辨个体在维之间的差异，没法衡量每个维数值的差异，会导致这样一个情况：比如用户对内容评分，5分制，X和Y两个用户对两个内容的评分分别为(1,2)和(4,5)，使用余弦相似度得出的结果是0.98，两者极为相似，但从评分上看X似乎不喜欢这2个内容，而Y比较喜欢，余弦相似度对数值的不敏感导致了结果的误差，需要修正这种不合理性，就出现了调整余弦相似度，即所有维度上的数值都减去一个均值，比如X和Y的评分均值都是3，那么调整后为(-2,-1)和(1,2)，再用余弦相似度计算，得到-0.8，相似度为负值并且差异不小，但显然更加符合现实。

欧氏距离与余弦相似度

欧氏距离是最常见的距离度量，而余弦相似度则是最常见的相似度度量，很多的距离度量和相似度度量都是基于这两者的变形和衍生，所以下面重点比较下两者在衡量个体差异时实现方式和应用环境上的区别。
　　借助三维坐标系来看下欧氏距离和余弦相似度的区别：相似度度量方式及原理

注明：本篇文章来自网络搜索出来的结果，防止原链接失效以及为了自己学习方便，由本人汇总所得笔记。如有侵权，望告知！尽快删除！以下是参考的连接：相似度度量算法
值得注意的是，在聚类问题中，数据标准化之后的结果也可能产生和预想不同的情况，例如：
在数据处理阶段，一般要对数据进行标准化处理，需要考虑的一个问题是当改变某一个维度的大小，是否会有利于聚类的效果？如下图，图一是随机画的四个点，如果缩小x轴的维度，很显然分为两簇{1，2}和{3，4}；如果缩小y轴的维度，很显然分为两簇{1，3}和{2，4}。
相似度度量方式及原理
聚类之后如何评价分好的簇效果是不是好呢？可能针对实际情况有一定的衡量标准吧。比如下图，很直观的可以看出图一这样聚类挺合理的。如果用欧式距离作为相似度度量，按照距离每一个簇中心点（两个加号的位置）的远近来度量的话，图二的分类效果比较好。
相似度度量方式及原理
然而，一般的聚类问题是无法直观看出来高维空间点的分布，在Matlab中可以用一个函数来度量聚类效果，每一个样本点包含两个度量值a(i)和b(i)。a(i)表示和同组的其他点的平均距离，b(i)表示和不同组的点平均距离。
相似度度量方式及原理