【有书共读】数据挖掘导论 第2章 2.4
2.4 相似性和相异性的度量
这一节的内容比较重要，而且公式比较多，所以单独拎出来。之所以说重要，是因为大多数数据挖掘和机器学习的算法都会涉及到相似性和相异性。本质上来讲，目前的数据挖掘和机器学习，乃至深度学习的本质都是统计学习，所以从根本上来讲，我们得到的模型，是希望跟现实情况有着尽可能接近的概率分布，这就是相似性的本质。既然涉及到了概率分布，那么实操中，我们自然是希望模型的输出和现实数据尽可能接近，这就是我们在模型中所求的相似性，一个抽象，一个具体。
2.4.1 基础
1. 定义
两个对象之间的相似度（similarity）的非正式定义是这两个对象相似程度的数值度量。如果两个对象越相似，那么它们的相似度就越高。一般来说，相似度是非负的，通常在0到1之间取值。
两个对象之间的相异度（dissimilarity）是这两个对象差异程度的度量，和相似度类似。2. 变换
通常，相似度和相异度之间会根据需要进行转换，或者把邻近度变换到一个区间，一般是0到1。
邻近度一般被定义为0到1之间的值。因此，按照我个人的理解，归一化后的相似度和相异度，都可以代表邻近度。相似度和相异度一般分别用以下两个式子转换到[0, 1]的区间：
s' = (s – min_s) / (max_s – min_s), d’ = (d – min_d) / (max_d – min_d)
这相当于是把非归一化的相似度或相异度转化为邻近度。
下一个问题就是相似度和相异度之间的转换，一个比较直接的做法是，s = 1 – d。如果不是归一化的，我们还可以将相似度和相异度定义为相反数，即s = -d。这两者之间的变换的本质是此消彼长，只要是单调减函数，基本都满足要求，因此还有以下定义方式：
s = 1/(1+d), s = e^(-d)
2.4.2 简单属性之间的相似度和相异度
这一部分可以用一张表来很清楚的说明，如下：
2.4.3 数据对象之间的相异度
这是我们在数据挖掘中很常见的问题，相异度的计算其实就是计算数据对象之间的距离，或者是点之间的距离，只不过这个点是高维空间的或者是抽象的。
欧几里得距离是计算高维空间中距离的基本方法，本质上是两个向量的二范数
广义的距离一般用闵可夫斯基（Minkowski distance）来定义：
r是参数。
若r = 1，则距离为L1范数，也叫曼哈顿、出租车距离，一个常见的例子是汉明距离（Hamming distance）。
若r = 2，则为欧几里得距离，也称L2范数。
若r→∞，则为上确界距离，或者叫无穷范数。
距离具有一些通用的性质，如果d(x, y)是两个点x和y之间的距离，则如下性质成立：
(1) 非负性。(a) 对于所有x和y，d(x, y) ≥ 0，(b) 仅当x = y时，d(x, y) = 0。
(2) 对称性。对于所有的x和y，d(x, y) = d(y, x)。
(3) 三角不等式。对于所有x，y和z，d(x, z) ≤ d(x, y) + d(y, z)。
满足以上三个性质的测度称为度量（metric）。
相异度也可以用非度量的形式来表示，比如集合差。对于集合A和集合B，则A – B是不在B中的A中的元素集合，此种距离不具有对称性，但是若将距离定义为d(A, B) = size(A – B) + size(B – A)，其中size是集合中元素的个数，这样定义的距离就满足(1)-(3)。
另一种非度量的相异度的例子是时间，时间距离一般定义为
对于相似度，三角不等式通常是不成立的，但是一般具有对称性和非负性，具体的，如果s(x, y)是数据点x和y之间的相似度，则相似度具有如下经典性质
(1) 仅当x = y时，s(x, y) = 1（0≤s≤1）。
(2) 对于所有x和y，s(x, y) = s(y, x)。
2.4.5 邻近度度量的例子
1. 二元数据的相似性度量
仅包含二元属性的对象之间的相似性度量也称为相似系数（similarity coefficient），并且通常在0到1之间取值。假设x和y是两个对象，都由n个二元属性组成。这样的两个对象（即两个二元向量）的比较可以生成如下四个量（频率）：
f00 = x取0并且y取0的属性个数
f01 = x取0并且y取1的属性个数
f10 = x取1并且y取0的属性个数
f11 = x去1并且y去1的属性个数
简单匹配系数（Simple mMtching Coefficient，SMC）是一种常用的相似性系数，定义如下：
举例，假设
x = (1, 0, 0, 0, 0, 0, 0, 0, 0, 0)
y = (0, 0, 0, 0, 0, 0, 1, 0, 0, 1)
则
2. 余弦相似度
余弦相似度的计算如下
其中，·表示向量点积。从本质上讲，余弦相似度就是两个数据对象的属性向量在高维空间中夹角的余弦值。
3. 广义Jaccard系数
这个系数也叫做Tanimoto系数，用EJ表示，由下式定义
这个公式看起来跟余弦相似度有点像，并且有相应的物理意义。我们先看Jaccard系数的原始定义。给定两个集合A，B，Jaccard系数定义为A与B交集的大小与并集大小的比值，因此根据集合的公式，我们可以得到如下的定义
4. 相关性
从统计的角度，我们可以给两个数据对象x和y定义它们之间的相关性，如下
Bregman散度（Bregman divergence）*
这里只简要讨论，不做详细地说明。Bregman散度本质是衡量损失或者失真的程度，从数学上，有如下正式定义。
定义2.6 Bregman散度 给定一个严格凸函数φ，由该函数生成的Bregman散度D(x, y)通过下面的公式给出
D(x, y) = φ(x) – φ(y) – <▽φ(y), (x-y)>
上式中x和y均为向量，▽表示梯度，<>表示向量的内积。从上式我们可以看出，Bregman散度的本质就是函数在该点(y)的值与正切于该函数的平面（线）之间的差。因此，从我们可以将其作为相异度的度量，因为当两个点很接近的时候，D会趋于0，反之则会有很大的偏离。不同的凸函数φ可以提供不同的相异度函数。
这一部分暂时没有必要过于深究，之后在聚类算法中，我们可能会讨论到Bregman散度。
2.4.6 邻近度计算问题
1. 距离度量的标准化和相关性
无论在数据挖掘还是机器学习中，属性的标准化是非常有必要的，这样可以避免某数值很大的属性（比如年收入相对于年龄）左右结果。
另一个问题是，如果属性之间相关，那么应该如何计算距离。当属性相关、具有不同的值域（不同的方差）、并且数据分布近似于高斯（正态）分布时，可以将欧几里得距离推广，用Mahalanobis距离计算。具体的，两个数据对象x和y之间的Mahalanobis距离定义为：
其中∑-1是数据协方差矩阵的逆。
如果属性相对来说不相关，只是具有不同的值域，则只需要对变量进行标准化就足够了。
2. 组合异种属性的相似度
组合的话，无非就是用某种规则将各个属性的相似度进行加和，这里直接上算法，如下：
3. 使用权值
跟算法2.1类似，只要把（2-15）式里分子的求和加上权值即可，不同的权值代表了不同属性的重要程度，并且权值的和为1，如下
闵可夫斯基距离的定义也可修改为：
2.4.7 选取正确的邻近性度量
这一部分比较有用的有两点，
1. 对于许多稠密的、连续的数据，通常使用距离度量邻近性，比如欧几里得距离。
2. 对于稀疏数据，通常包含非对称的属性，因此一般会使用忽略0-0匹配的相似性度量，这里的哲学是，对于一对复杂对象，他们的相似度依赖于它们共同具有的性质数目，而不是依赖于它们都缺失的性质数目。因此，常常使用余弦相似度和广义Jaccacrd系数度量这类数据。