jaccard相似度_聚类（一）：相似性度量

在前两篇学习理论和降维的中，我们这么理解无监督学习：在没有数据标签的情况下，我们总是通过学习数据集合上的某些性质或结构来完成我们预定的任务，而这些性质或结构总是通过显式或隐式地学习数据集合的分布来得到，显式地学习数据分布，比如密度估计就是，通过统计理论进行参数估计，有了数据的分布，我们就可以从分布本身出发理论性地推导出数据的很多有用性质；隐式学习则是直接学习数据具有的一些性质，在这里我们仍然称之为分布的一部分信息，只是不再是狭义的分布函数，而是作为描述信息的整体概念，具体来看主要有两类：数据特征变量关联和聚类，前者是利用各种相关性分析方法来找到变量之间的关系并加以应用，降维就在此列，后者则是找到数据的天然分割，即我们这里要讨论的聚类。

什么是聚类

聚类的概念应该说是比较简单的，顾名思义，就是把数据点分成不同的子集合，使得同一个子集合内的数据具有高相似性，子集合之间的数据具有低相似性。说到这里，会发现这个描述很像我们上一篇中提到的“高类间距，低类内距”的Fisher LDA，不同之处在于Fisher LDA是既定类标签的投影，而我们现在要看的聚类则是要去打上“类标签”，也就是聚类问题的输入是数据点集合，大部分方法通常还需要期望的子集合个数，输出则是被聚类的子集合，或者说是每个数据点的“类标签”，从后者的角度讲，又和监督学习的分类有些相似，区别在于有监督学习的分类是通过在已有类标签的训练数据上学习到的判别函数来进行打标签，而无监督学习的聚类则是通过我们之前所说的隐式地学习数据分布，通过数据本身的分布性质来给我们所学习的数据打标签。

对聚类有了整体概念之后，我们接下来详细看怎么定义类、怎么度量相似性、常见聚类方法以及怎么确定类个数的问题，以求对聚类有全面的认识。

怎么定义类

如果给定一个班的同学，让大家随便去聚类，那么得到的结果可能五花八门，有人按照性别分为了两类，有人按照身高区间分为了五类，还有人可能按照喜爱吃的东西分成了十类，可见单纯数据的聚类是一件非常主观的事情。它其实和我们的目的非常相关，带着不同的目的去分析数据可能会有不同的聚类结果，而不同的目的是怎么影响聚类的呢，答案则是相似性，我们针对具体的目的定义相似性，使得我们在聚类过程中只关注跟目的相关的数据属性，指导我们的聚类过程。

相似性度量

其实相似这种东西也是很主观的，它属于我们日常交流中的用语，在实际处理过程中我们将事物表示成数据，将演算步骤抽象成算法时，具体怎么用量化了的数值表示相似性呢，主要有下面两大类方法： 用距离来代替相似性。距离大则相似性高，反之则相似性低，不同类型的相似性也可以有不同类型的距离来度量。所以接下来我们来看一下常见的不同类型的距离，在这之前，我们先来看一下一个度量方式可以用作距离需要满足那些条件，毕竟我们不能说“任意两点之间的距离都为1”这种度量方式也是一种有效距离，因为这种“不好”的度量使得我们很难在距离的实际算法应用中使用它，对于这种不满足我们常识和认识的定义，我们以此学习到的结果很有可能也将不符合我们的常识和期望。 非距离的，这一类就比较零散，针对不同的分析对象构造不同的函数，用有意义的函数值来量化地表示相似性。

距离

在介绍常见的距离度量方式之前，我们先来看一下一个满足预期的距离度量函数

应该满足怎样的条件：

• 对称，即
  ，否则你就可以说“小明很像小李，但小李一点也不像小明”
• 正定，即
  且
  当且仅当
  ，否则你就可以说“小明很像小李，甚至比小李自己都像，或者就存在不相似的东西但是我们却无法区分，这就不是一个可以表示相似的距离度量
• 三角不等式，即
  ，否则你就可以说“小明很像小李，小明也很像小张，但小李和小张一点也不像”

从这个距离的必要条件出发，我们来看一下都有哪些常见距离度量方式

闵可夫斯基距离

我们首先要来看的是闵可夫斯基距离(Minkowski distance)，它是度量数值点之间距离的一类方法的概述，可以对应欧式几何中的范数，对于$d$维数据和$r$，闵可夫斯基距离或Lr范数定义为：

当

取大于1的具体值时，其所表示的距离才满足我们上面说的四个性质，特别的，当

取下面的值时有我们熟悉的概念：

• 其中当
  时，则是我们通常见到的
  欧氏距离(Euclidean distance)或L2范数，即
• 当
  时，则是我们通常见到的
  曼哈顿距离(Manhattan distance)或L1范数，即
  ，特别的，当所有维度的有效取值为二进制时，曼哈顿距离退化为
  汉明距离(Hanming distance)
• 当
  时，则是
  切比雪夫距离(Chebyshev distance)或L
  范数，即

通过闵可夫斯基距离的定义以及几个特殊的例子，我们可以看到它仍然是符合我们欧式空间中的想象，这里有一个有趣的理解，就是不同的

在取与原点距离相同（比如1）的所有点构成的形状是怎样的，我们最熟悉的就是欧氏距离，它跟圆的定义一致，也就是欧氏距离度量下与原点距离相同的点构成了一个圆形，其余的呢，我们展开来看有：

这里先给我们留下一个印象，我们在之后的篇章中结合形状来分析不同距离的性质对于解的影响，比如稀疏。

闵可夫斯基距离比较直观，但是它没有考虑数据的分布，会带来一定的局限性，比如某一个维度上值都很大，变化也大，那么对整体结果带来的影响就相对较大，为了综合考虑各个维度，我们通常在计算闵可夫斯基之前对数据进行标准化，即各个维度减去各自均值，除以各自标准差。这里，其实我们就是在结合数据样本的分布来修正距离的表示了，标准化通过方差和均值来避免不同维度采用不同的量纲以及值大小的影响，但是却无法避免维度之间相关性的影响，衡量不同维度之间的关联就需要引入协方差，这也就是所谓的马氏距离。

马氏距离

我们刚才提到了，我们期望引入当前样本集的性质来修正距离的度量，具体来说是： 通过引入各自维度的均值来避免不同维度值有大有小的影响 通过引入各自维度的方差来避免不同维度采用不同量纲的影响 * 通过引入不同维度之间的协方差来避免维度之间相关性的影响

这里我们来想一下为什么不同维度之间的相关性会对距离的度量带来影响呢，这是因为比如其中两个维度之间有相关性，不管是正相关还是负相关，我们只要知道了其中一个维度的信息，那么就隐含地知道了部分另一个维度的信息，放在距离上也是，如果我们已经计算了其中一个维度的距离了，那么整体距离结果其实就隐含地包含了另一个维度了，如果我们还是以同样的方法再引入一遍另一个维度的距离，那么是不是就冗余了呢，不同大小的相关性对整体距离结果带来了不同程度上对某些维度过分的关注，这样不好的结果就是我们要修正的，也就是维度之间相关性带来的影响。

马氏距离就是这样一个集三者之大成的度量方式，具体来说，对于一个均值为

，协方差为

的多变量向量

，其马氏距离为：

我们可以从上式中看出，如果多变量之间的协方差矩阵为单位矩阵，也就是各维度之间不相关，各维度自己也以

为方差，那么马氏距离也就简化为了欧式距离

编辑距离

考虑从哈密顿距离简化来的汉明距离时，可以把二进制的数据向量表示看做序列，汉明距离就表示两个序列的相似度，而如果这两个序列不仅取值范围不再局限在二进制，而且序列长度也有可能不同时，我们可以用编辑距离(Edit distance)来表示，它是指两个序列之间，由其中一个转成另外一个所需要的最少的编辑操作次数。

非距离的相似性度量

对于非距离类的相似性度量方式，我们可以统称为相似度，它直接刻画两者的相似性程度，常见的相似度有：

余弦相似度(Cosine Similarity)

余弦相似度用向量空间中的两个向量夹角的余弦值来衡量两个个体之间的差异，具体地定义为：

我们在这里来对比理解一下余弦相似度和欧式距离，余弦相似度是一种角距离，加上余弦值只是因为角度的余弦值相对角度本身的计算比较简便，所以说余弦相似度和欧式距离虽然都在向量空间中进行计算，但前者计算的只是角度，它对向量的长度不敏感，向量的“大小”变了，余弦相似度不会变，而欧式距离而会随之变化，余弦相似度消除了向量长度的影响，归一化后，分母为

，则二者具有单调的关系。这是数值上的表现，那么它在物理意义上又代表什么呢，向量各个维度上的数值即我们描述对象的属性特征，欧氏距离表现的是对象特征值上的绝对差异，而余弦相似度衡量的则是方向上的相对差异，更多关注的是不同维度定义的对象的整体状态。我们再从另外一个角度考虑余弦相似度和欧式距离的区别，那就是在高维稀疏数据情形下（高维往往会导致数据的稀疏）二者的表现，我们从定义中可以想象出，当稀疏度足够高的时候，欧氏距离和哈密顿距离的差别会很小，极端情况下，当所有样本只有一个维度上取值为

的时候，那么任意两点的欧氏距离很大可能都是

，欧氏距离有意义需要多数特征上满足

，所以高维稀疏的情境下，欧氏距离通常用处不大，相反，这个时候只要两者至少有一个同时不为0的特征时，余弦相似度就可以很好地工作，从这个角度讲，欧氏距离注重特征的绝对值，而余弦相似度更关注这个特征是否出现过。

皮尔逊相关系数(Pearson Correltation Coefficient)

Pearson相关系数定义为：

从定义中我们可以看出，Pearson相关系数就是引入了样本数据集的特征对余弦相似度进行了修正，也就是中心化后的余弦相似度，这样使得Pearson相关系数不仅有了余弦相似度的尺度不变形，同时具有平移不变性。

Jaccard相似系数

Jaccard相似系数衡量的则是两个集合的相似性，它定义为两个集合的交集元素在并集中所占的比例：

与Jaccard相似系数相反，Jaccard距离则用不同元素所占的比例来衡量两个集合的区分度，即：

KL散度

到目前为止，我们谈到的都是两个数值点之间的相似性，有的距离可能会引入样本集合上的某些性质，但衡量的仍是个体之间的相似性，KL散度则不同，它衡量的是两个概率分布之间的距离，针对观测到的样本集合，也可以说它是衡量的两个样本集合之间的距离。

介绍KL散度之前，不得不谈到的就是熵，熵属于信息论中的概念，它描述的是一个系统内部的整体状态，具体地说是系统内部各要素的分散程度，针对满足某种分布的样本数据集合来讲，样本越分散，信息熵就越大，样本越集中，信息熵越小。信息论的基本想法是一个不太可能发生的事件发生了，要比一个非常可能发生的事件发生，提供的信息更多。如果想通过这种基本想法来量化信息，那么应该有： 非常可能发生的事件信息量非常少，极端地，一定会发生的事件应该没有信息量。 较不可能发生的事件具有更高的信息量。 * 独立事件应具有增量的信息，也就是如果

，那么则有

。

为了满足上述的三个形式，我们定义一个事件

的自信息为：

自信息只处理单个输出，熵则是对整个概率分布中的不确定性总量进行量化，有：

有了对概率分布的度量，那么我们就能够以熵为基础衡量两个分布之间的差异，KL散度又称相对熵定义为：

值得注意的是，从定义中我们可以看出KL散度是不对称的，假设

为真实分布，

为我们学习到的分布并且希望用分布

来近似

，那么最小化

和最小化

会带来不同的效果，具体则要看我们的问题需要。

这里我们先介绍了聚类算法的前置认识，包括如何认识类以及如何理解相似性，下一篇中我们则来探究聚类的具体算法。