

3 相似度和距离

“爱就是在不同的事物中找到相似性的能力。”—西奥多·阿多诺

3.1简介

许多应用数据挖掘的场合需要决定数据中的对象、模式、属性和时间是相似的还是不相似的。换句话说，就是需要一种定量地判定数据对象之间相似度的方法。事实上所有的数据挖掘问题，例如聚类、离群点检测和分类，都需要用到相似度的计算。关于定量的相似度或者距离问题的正式表述如下所示：

给定两个对象$O_1$和$O_2$ ，确定两个对象之间的相似度$Sim(O_1,O_2)$（或者距离$Dist(O_1,O_2)$）的值。

对于相似度函数，较大的函数值意味着较大的相似度，而对于距离函数，较小的函数值意味着较大的相似度。在某些领域，例如空间数据，使用距离函数是一件更自然的事情，而在其它领域，例如文本数据，人们更习惯于使用相似度函数。尽管如此，在不同领域中设计这些函数所应用的原则是不变的。因此，本章会根据所处理数据的类型使用术语“距离函数”或者“相似度函数”。相似度和距离函数常以闭型表示（如欧几里得距离），但在某些领域，例如时序数据，它们是由算法定义的，不能以闭型表示。

距离函数是设计有效的数据挖掘算法的基础，因为选择一个不好的距离函数会损害结果的质量。有时候，数据分析师选择欧式距离，把他当作一个“黑盒子”，而不考虑这个选择带来的影响。没有经验的分析师经常会花大力气去设计数据挖掘问题的算法，而把数据函数子程序当作事后处理。这是一个错误。本章会阐明，有时一个不好的距离函数在某些应用领域会带来毁灭性的误导。好的距离函数设计对于类型的可移植性也至关重要。正如第二章2.4.4.3节所述，谱嵌入方法可以用来将任何数据类型所构造的相似度图转化为多维数据。

距离函数是对数据分布、维度和数据类型高度敏感的。相比于时序数据这样类型的数据，像多维数据这样类型的数据就更易于设计和计算距离函数。在某些情况下，可以使用用户的意图（或者一对数据对象的训练反馈）来监督距离函数的设计。尽管本章主要关注于无监督的方法，我们也会简要地涉及一些使用有监督方法的原则。

本章组织结构如下：3.2节研究多维数据的距离函数。这包括定量的、分类的和混合的数据。3.3节讨论了文本、二进制和集合数据的相似度测量方法。3.4节讨论了时序数据。3.5节解决了图数据的距离函数设计。对监督相似性的讨论将在第3.6节中进行。第3.7节作了总结。

3.2 多维数据

尽管多维数据是最简单的数据形式，不同属性类型的距离函数设计之间还是有显著差异的，例如分类或定量数据。因此，本节会分别研究这些类型。

3.2.1 定量数据

对于定量数据，最常见的距离函数就是$L_p-$范数。两个数据点$\overline{X}=(x_1 \dots x_d)$和$\overline{Y}=(y_1 \dots y_d)$之间的$L_p-$范数定义如下：

$$Dist(\overline{X},\overline{Y})=(\displaystyle\sum_{i=1}^d|x_i-y_i|^P)^{1/p}\tag{3.1}$$

$L_p-$范数的两个特例是*欧式*距离$(p=2)$和*曼哈顿*距离$(p=1)$。这些特例从空间应用的直觉中产生，具有清晰的物理意义。欧式距离是两个点之间的直线距离。曼哈顿距离是在“街区”中的开车距离，街区中的街道构成矩形的网格，例如纽约城的曼哈顿岛。

欧式距离的一个优势是具有旋转不变性。因为两个点之间的直线距离不会随着坐标系朝向的改变而改变。这个性质意味着可以执行一些变换而不影响$^1$距离，例如$PCA$(主成分分析)、$SVD$(奇异值分解)、或者时序的小波变换(见第二章)。另一个令人感兴趣的特例是令$p=\infty$。这样计算距离的结果是选择两个物体相距最远的那个维度，并返回这个维度上距离的绝对值。其他维度上的特征被忽略了。

$L_p-$范数是数据挖掘分析师最常用的距离函数之一。该范数流行的一个原因是其自然直观的表现形式和$L_1-$、$L_2-$范数在空间应用中的可解释性。但是直观的可解释性不意味这他们是最相关的距离函数，特别是对于高维的情况。事实上，这些距离函数在数据是高维的情况下并不能正确的反应数据点之间的距离，这是因为数据的稀疏性、数据分布特点、噪声和特征相关性等因素带来的不同影响。这一章将会讨论在距离函数设计中需要考虑的更宽泛的原则。

$^1$维度下降会影响距离。但是变换本身不会影响距离。

3.2.1.1 特定领域中相关性的影响

在某些情况下，一个分析师有可能知道对于一个特定的应用，哪些特征相对于其他特征而言是更重要的。例如，对于一个信用评级应用，在设计距离函数时，像薪水这样的属性就会比性别这样的属性具有更高的相关性，尽管他们都对距离函数的设计有些影响。在这种情况下，如果关于不同特征的相对重要性的领域专业知识是已知的，分析师可能会给不同的属性赋予不同的权值。这经常是一个基于经验和技能的启发式过程。在这里，一个广义的$L_p-$范数是最合适的，他的定义形式与$L_p-$范数相似，但是系数$a_i$是和第$i$个特征相关的。这个系数就是$L_p-$范数中相应特征分量的权重：

$$Dist(\overline{X},\overline{Y})=(\displaystyle\sum_{i=1}^da_i\cdot|x_i-y_i|^p)^{1/p}\tag{3.2}$$

这个距离又被称作广义的闵可夫斯基距离。在很多情况下，我们并不知道这些领域知识。因此，$L_p-$范数成了默认的选择。不幸的是，在不知道最相关的特征时，$L_p-$范数容易遭受维度增加带来的不良影响，正如下面所讨论的。

3.2.1.2 高维数据的影响

随着数据维度的增加，许多基于距离的数据挖掘应用程序失去了其有效性。例如，一个基于距离的聚类算法可能将不相关的数据点归为一类，因为距离函数在数据维度增加时不能很好的反映数据点之间内在的语义距离。结果，基于距离的聚类、分类和外点检测模型经常定性地失效了。这种现象被称作“维度的诅咒”，这个概念最早由理查德贝尔曼提出。

为了更好地理解维度诅咒对距离的影响，我们研究一个维度$d$下的完全位于非负象限的单位立方体，它有一个顶点位于坐标原点$\overline{O}$。从坐标原点到到立方体中任意一点$\overline{X}$的曼哈顿距离是多少呢？在这里，因为一个端点位于坐标原点，并且所有的坐标值非负，曼哈顿距离就是$\overline{X}$所有维度上的坐标值求和的结果。每一个坐标值都是在$[0,1]$区间上均匀分布的。因此，如果用$Y_i$表示$[0,1]$区间上服从均匀分布的随机变量，那么曼哈顿距离就可以表示为如下形式：

$$Dist(\overline{O},\overline{X})=\displaystyle\sum_{i=1}^d(Y_i-0)\tag{3.3}$$

结果是一个均值为$\mu=d/2$，标准差为$\sigma=\sqrt{d/12}$的随机变量。当$d$比较大时，由大数定理可知，立方体中绝大多数数据点将会位于区间$[D_{min},D_{max}]=[\mu-3\sigma,\mu+3\sigma]$之内。因此，立方体中大多数点的距离会落在一段长为$D_{max}-D_{min}=6\sigma=\sqrt{3d}$的距离区间内。注意，曼哈顿距离的期望是随着维度$d$按线性比率增长的。因此，距离的变化值和绝对值之间的比率，记为$Contrast(d)$，如下所示：

$$Constrast(d)={\frac{ D_{max}- D_{min}}{\mu}}=\sqrt{12/d}.\displaystyle\tag{3.4}$$

这个比率可以解释为不同数据点之间的距离对比$(contrast)$，它反映从原点出发的最大距离和最小距离之间差异的程度。因为“对比”按照$\sqrt d$的速率降低，这意味着不同数据点的距离实际上几乎不受维度增加的影响。低对比度显然不是我们想要的，因为这意味着数据挖掘算法会将以近似相同的方式在所有对数据点之间的距离进行评分，并且不会在不同的语义关系级别的对象对之间进行区分。当维度增加时，对比的方差的变化情况如图3.1a所示。实际上，所有不同$p$参数的$L_p-$范数都有这种现象，只不过严重程度不同。这里严重程度的差异将会在后面的章节中研究。很清楚的是，当维度增加时，直接使用$L_p-$范数可能不是有效的。

3.2.1.3 局部不相关特征的影响

一个更加根本的探究高维度效果的方法是考察不相关特征的影响。这是因为在一个典型的高维数据集中，许多特征可能是不相关的。举个例子，考虑一个医学记录数据集，它包含各种医学情况的病人和个人病史中的不同方面的广泛的定量的测量值。对于一个包含糖尿病患者的集合，特定的某些属性对于距离的计算更加重要，例如血糖水平。另一方面，对于包含癫痫病患者的集合，另一组特征会更加重要。许多属性值的自然方差的加性效果可能会非常显著。对于像欧式距离这样的距离度量，噪声分量可能会贡献很多不必要的数值，因为欧式距离是采用求平方和的方式计算距离的。这里需要理解的关键点是，和距离计算相关的几个特定特征可能有时会对于被比较的特定对象对非常敏感。在预处理过程中全局地筛选特征子集不能解决这个问题，因为特征是否相关是由被考虑的对象对*局部地*决定的。全局来说，所有特征可能都是相关的。

当许多特征不相关时，不相关特征的加性噪声效果有时可能会表现为距离值的集中。在任意情况下，这样的不相关的特征总是会在距离计算中引入误差。因为高维数据集经常包含各种 特征，许多是不相关的，像$L_2-$范数这样使用平方和的方式计算距离，其加性效果会非常具有破坏性。

3.2.1.4 不同$L_p-$范数的影响

不同的$L_p-$范数的表现效果是不一样的，无论是在不相关特征的影响方面，还是在距离对比方面。考虑$p=\infty$的极限情况。这个范数等价于只使用两个对象最不相似的那个维度。经常发生的是，这个维度对应不相关的属性，其自然方差对基于相似度的算法有不利的影响。事实上，对于一个1000维的应用，如果两个对象在999个属性上有相似的值，那么这两个对象应该被定义为非常相似。但是，单独的一个不相关的属性，如果两个对象在这个属性上相差很多，那么在无穷范数$L_\infty$的度量下，这两个对象的距离会被拉的很远。换句话说，局部的相似的属性被无穷范数$L_\infty$忽视了。显然，这不是我们想要的效果。

总体上，对于较大的$p$值，$L_p-$范数都是这样：不相关的属性被强调了。事实上，对于某些数据分布，当$p$值较大时，距离对比的效果也减弱了。在不同维度的数据上，对于不同的$p$值，距离对比如图3.1b所示。这个图的构造方式和图3.1a是一样的。尽管所有的$L_p-$范数都随着维度的增加而减小，但是较大$p$值的曲线要减小地更快一些。从图3.2中我们可以更好地理解这个趋势，图3.2的$x$轴代表$p$值。在图3.2a中，不同维度数据的对比随着$p$值变化。图3.2b是由图3.2a衍生而来，不同之处在于这个图的结果是用更高阶范数除以曼哈顿性能得到的分数。很明显的是，随着$p$的增加，当数据维度较大时衰减的速率更快。对于二维的数据，几乎不存在衰减。这就是为什么在低维应用中$p$值的选取不是很重要。

这段论述引出了分数度量的概念，也就是$p\in(0,1)$。这个分数度量可以为高维度的数据提供更有效的结果。根据经验，维度越高，$p$值越小。但是，对于$p$值的选取并没有一个准确的准则，这是因为维度不是选取合适的$p$值所要考虑的唯一因素。$p$值的准确选取需要结合具体的应用，使用基准测试的方法。3.8节书目注释中包含了使用分数度量的讨论。

3.2.1.5 基于匹配的相似度计算

由于希望为距离计算选择局部相关特征，因此会出现一个问题，即如何以数据挖掘应用的有意义和实用的方式实现这一点。 在许多情况下，简单的基于匹配多个属性值的累积证据的方法已经被证明是有效的。这种方法也相对容易高效实施。

似乎适用于高维数据的一个更广泛的原则是，在计算多个维度上的累积匹配时，需要忽略沿着各个属性的噪声变化的影响。 当然，这种方法对低维度数据提出了挑战，因为匹配的累积影响在低维数据上不能以一种统计上可靠的方式计算。 因此，需要一种能够自动适应数据维度的方法。

随着维度的增加，记录可能包含相关和不相关的特征。由于不相关特征的噪声变化，一对语义相似的对象可能包含不相似的特征值（在沿着该维度的一个标准偏差的水平）。相反，一对对象不可能偶然地在许多属性中具有相似的值，除非这些属性是相关的。有趣的是，欧几里德度量（通常是$L_p-$范数）通过使用属性值差异的平方和来达到完全相反的效果。结果，来自不相关属性的“噪声”分量主宰了计算并掩盖了大量相关属性的相似效应。$L_\infty-$范数提供了使用具有最大距离值的维度的这种效果的极端示例。在像文本这样的高维领域，相似度函数（如3.3节中讨论的余弦度量）倾向于强调匹配对许多属性值的累积效应，而不是沿着单个属性的较大距离。这个一般原则也可以用于定量数据。

一种不重视精确水平的差异的方法是以维度敏感的方式使用 邻近阈值。 为了执行邻近阈值处理，数据被离散化为等距桶。 每个维度被分成$k_d$个 等深度桶，每个桶包含总记录的$1/k_d$。 桶的数量$k_d$取决于数据维度$d$。

令$\overline{X} =(x_1\dots x_d)$和$\overline{Y} =(y_1\dots y_d)$为两个$d$维记录。 然后，对于维度$i$，如果$x_i$和$y_i$都属于同一个桶，则这两个记录被认为在维度$i$上接近。$\overline{X}$和$\overline{Y}$映射到同一个桶的维度的子集称为邻近集合，它由$S(\overline{X},\overline{Y},k_d)$表示。 此外，对于每个维度$i\in S(\overline{X},\overline{Y},k_d)$，令$m_i$和$n_i$为维度$i$中桶的上下界，其中两个记录彼此靠近。 然后，相似度$PSelect(\overline{X},\overline{Y},k_d)$被定义如下：

$$\displaystyle PSelect(\overline{X},\overline{Y},k_d)=\left [ \sum_{i \in S(\overline{X},\overline{Y},k_d)}\left(1-\frac{|x_i-y_i|}{m_i-n_i}\right)^p \right ]^{1/p}\tag{3.5}$$

上述表达式的值将在$0$和$|S(\overline{X},\overline{Y},k_d)|$之间变化，因为总和中的每个单独表达式都在$0$和$1$之间。这是一个相似度$(similarity)$函数，因为较大的值意味着更大的相似性。

上述相似度函数仅为映射到相同桶的维度保证非零相似性分量。 等深度分区的使用可确保两个记录共享特定维度的桶的概率为$1 / k_d$。因此，平均而言，前述总和可能具有$d / k_d$非零分量。对于更多类似的记录，这些分量的数量会更大，并且每个分量也可能对相似度值贡献更多。这种方法忽略了遥远维度上的不相似程度，因为它常常受噪声支配。理论上[7]看，对于某些数据分布，选择$k_d \propto d$可以在高维空间中获得恒定的对比度水平。 $k_d$越大导致每个维度的界限更严格。这些结果表明，在高维空间中，最好针对每个维度设定更高的质量范围，以便在相似度计算中使用保留维度的较小百分比（而不是数量）。这个距离函数的一个有趣的方面是它对数据维度的敏感性。关于$d$的$k_d$的选择确保了对于低维应用，它通过使用大部分维度而与$L_p-$范数有一些相似之处;而对于高维应用，它通过在匹配属性上使用相似性来表现类似于类似于文本域的相似性函数。距离函数也被证明对原型最近邻分类应用更有效。

3.2.1.6 数据分布的影响

$L_p-$范数仅取决于其参数中的两个数据点，并且对于其余数据点的全局统计量不变。距离是否依赖于数据集中其余点的基础数据分布？答案是肯定的。为了说明这一点，考虑图3.3中以原点$O$为中心的分布。另外，图中标出了两个数据点$A=(1,2)$和$B =(1,-2)$。显然，对于任何$L_p-$范数，$A$和$B$与原点$O$等距。然而，出现了一个问题，在相似度计算中$A$和$B$是否应该真正地被视为与$O$的等距？这是因为从$O$到$A$的直线在*方差变化较大*的方向上，统计上看，数据点在这个方向可能上更远。另一方面，从$O$到$B$的路径的很多分段是稀疏的，相应的方向是低方差$(low-variance)$方向。从统计的角度来看，B离O沿着这个方向的距离要小得多。因此，从$O$到$A$的距离应该$(ought)$小于从$O$到$B$。

马哈拉诺比斯距离 是基于这个一般原则。 令$\Sigma$是其数据集的$d\times d$协方差矩阵。 在这种情况下，协方差矩阵的$(i,j)$项等于维度$i$和$j$之间的协方差。 然后，两个$d$维数据点$\overline{X}$和$\overline{Y}$马哈拉诺比斯距离 $Maha(\overline{X},\overline{Y})$如下：

$$Maha(\overline{X},\overline{Y})= \sqrt{(\overline{X}-\overline{Y})\Sigma^{-1}(\overline{X}-\overline{Y})^T}.$$

理解马哈拉诺比斯距离的另一种方式是主成分分析$(PCA)$。马哈拉诺比斯距离与欧几里得距离相似，除了它基于属性相关性对数据进行归一化。 例如，如果要将坐标轴旋转到数据的主方向（如图3.3所示），那么数据将不具有（二阶）相互作用关系。在将每个变换的坐标值除以该数据的标准偏差之后，$Mahalanobis$距离相当于这样的经过变换（坐标轴旋转）的数据集中的欧几里德距离。 结果，图3.3中数据点$B$到原点$O$的距离将大于数据点$A$到原点$O$的距离。

3.2.1.7 非线性分布：ISOMAP

我们现在研究数据包含任意形状的非线性分布的情况。例如，考虑图3.4所示的全局分布。在三个数据点$A$，$B$和$C$中，哪一对彼此最接近？乍看之下，看起来数据点$A$和$B$在欧几里得距离的基础上是最接近的。然而，全局数据分布告诉我们并非如此。理解距离的一种方式是从一个数据点到另一个数据点的最短路径长度，例如从数据点跳转到他们的基于欧几里德度量的$k$个最近邻居中的一个的点的点对点跳转。直观的基本原理是，只有短暂的点到点跳转才能准确测量该点生成过程中的微小变化。因此，点到点跳跃的总和反映了比点之间的直线距离更准确地从一点到另一（远）点的总变化（距离）。这种距离被称为测地距离。在图3.4的情况下，通过短点对点跳转从$A$到$B$走的唯一方法是沿着数据分布的整个椭圆形行进，同时沿途经过$C$点。因此，在此基础上，$A$和$B$实际上是*最远*的一对数据点（在$A$，$B$和$C$之间）！隐含的假设是，非线性分布是符合*局部*欧几里得的，但*总体来说*是非欧几里得的。

这种距离可以通过使用从非线性降维和嵌入方法（称为$ISOMAP$）导出的方法来计算。该方法由两个步骤组成：

1. 计算每个点的$k-$最近邻点。用表示数据点的节点构造加权图$G$，表示这些$k-$最近邻点的距离的边权重（成本）。

2. 对于任何一对点$\overline{X}$和$\overline{Y}$，报告$Dist(\overline{X},\overline{Y})$作为$G$中相应节点之间的最短路径。

这两个步骤已经能够计算距离而无需执行降维。然而，将数据嵌入多维空间的额外步骤使许多对点之间的重复距离计算快得多，同时失去了一些准确性。这种嵌入还允许使用基于预定义距离度量的数字多维数据上自适应的算法。

这通过使用全对最短路径问题来构造G中任意一对节点之间的全部距离来实现。随后，应用*多维缩放*$(MDS)$（参见第2章第2.4.4.2节）将数据嵌入到较低维空间中。该方法的总体效果是“矫直”图3.4的非线性形状，并将其嵌入到数据沿着扁平条带对齐的空间中。事实上，一维表示可以近似表示这个转换后的数据。此外，在这个新的空间中，只要在最后阶段使用度量$MDS$，距离函数（如欧几里得度量）就可以很好地工作。图3.5a举例说明了一个三维实例，其中数据沿螺旋排列。在这个图中，数据点$A$和$C$之间的距离看起来比B和$C$或者$B$和$A$更短。但是，在图3.5b的$ISOMAP$嵌入中，数据点$B$、$A$和数据点$B$、$C$的 距离更短。此示例显示数据分布对距离计算的巨大影响。

通常，高维数据沿着非线性低维形状排列，这也称为*流形*。这些流形可以被“扁平化”成为一种新的表示形式，可以有效地使用公制距离。因此，这是一种便于使用标准度量标准的数据转换方法。主要的计算挑战是降维。但是，在支付一次预处理成本之后，可以有效地执行重复的距离计算。

非线性嵌入也可以通过$PCA​$的扩展来实现。 $PCA​$可以扩展到使用称为内核技巧的方法来发现非线性嵌入。参考第10章第10.6.4.1节，那里简要介绍了核$PCA​$。

3.2.1.8 局部数据分布的影响

迄今为止的讨论涉及全局分布对距离计算的影响。但是，数据的分布随着区域而变化很大。这种变化可能有两种类型。例如，数据的绝对密度可能随着数据局部性而显着变化，或者聚类的形状可能随局部性而变化。第一种类型的变化如图3.6a所示，它有两个包含相同数据点数的簇，但其中一个比另一个更密集。即使$(A,B)$之间的绝对距离与$(C,D)$之间的绝对距离相同，但从局部数据分布来看，$C$和$D$之间的距离应该被认为更大。换句话说，$C$和$D$相对于他们的局部分布看起来更为分散。许多基于距离的方法经常会遇到这个问题，例如异常值检测。已经表明，调整距离中的局部变化的方法通常比不调整局部变化的方法好得多。被称为局部异常因子$(LOF)$的最常见的异常值检测方法之一就是基于这一原理。

图3.6b举例说明了第二个例子，它说明了不同局部方位的影响。这里，$(A,B)$之间的欧几里得距离与$(C,D)$之间的欧几里得距离相同。然而，每个区域的局部集群呈现出非常不同的方向。与$(A,B)$相关的数据点集群的高方差轴沿着从$A$到$B$的路径排列，对于$(C,D)$来说这不是正确的。因此，$C$和$D$之间的固有距离比$A$和$B$之间的固有距离大得多。例如，如果使用相关聚类协方差统计来计算局部马氏距离，则$C$和$D$之间的距离将评估为比$A$和$B$之间的值大。

**共享最近邻相似性：**用共享最近邻居相似性可以至少部分缓解第一个问题。在这种方法中，每个数据点的$k$近邻在预处理阶段计算。共享最近邻的相似度等于两个数据点之间的共同邻居数量。这个度量是局部敏感的，因为它取决于公共*邻居*的数量，而不取决于距离的绝对值。在密集区域中，$k-$最近邻居距离将很小，因此数据点需要靠得更近以具有更大数量的共享最近邻居。可以使用共享最近邻居方法来定义底层数据点上的*相似度*图，其中具有至少一个共享邻居的数据点对具有它们之间的边缘。基于相似图的方法几乎总是局部敏感的，因为它们局限于$k-$最近邻分布。

**通用方法：**在通用局部距离计算方法中，思想是将空间划分为一组局部区域。然后使用该区域的局部统计数据在每个区域调整距离。因此，通用方法如下：

1. 将数据分区为一组局部区域。

2. 对于任何一组对象，确定该对的最相关区域，并使用该区域的局部统计来计算成对距离。例如，局部的马哈拉诺比斯距离可以用在每个区域。

使用各种聚类方法将数据划分为局部区域。在对中的每个对象属于不同区域的情况下，可以使用全局分布，或者可以使用两个局部区域来计算平均值。另一个问题是算法的第一步（分区过程）本身需要一个用于聚类的距离的概念。这使解决方案成为循环，并要求提供迭代解决方案。尽管对这些方法的详细讨论超出了本书的范围，但本章最后的参考书目提供了许多指导。

3.2.1.9 计算考虑

距离函数设计中的主要考虑因素是计算复杂性。这是因为距离函数计算通常嵌入在应用程序中重复使用的子例程中。如果子程序不能有效地实现，则适用性变得更加受限。例如，像$ISOMAP$这样的方法计算起来很复杂，而且对于非常大的数据集很难实现，因为这些方法至少按照数据大小的平方进行缩放。但是，它们确实具有一次性转换可以创建数据挖掘算法表示的高效使用的优点。距离函数重复执行，而预处理只执行一次。因此，只要加速后期计算，使用预处理密集型方法肯定是有利的。对于许多应用而言，即使对于一次性分析，$ISOMAP$等复杂的方法也可能过于复杂。对于这种情况，可能需要使用本章讨论的早期方法之一。在本节讨论的方法中，仔细选择$L_p-$范数和基于匹配的技术是大规模应用程序最快的方法。

3.2.2 分类数据

距离函数自然地计算为数值数据中维数的差异函数，它是*有序的*。但是，分类数据的离散值之间不存在排序。如何计算距离？一种可能性是使用在第2章第2.2.2.2节中讨论的二值化方法将分类数据转换为数值数据。由于二进制向量很可能是稀疏的（很多零值），因此可以从其他稀疏域（例如文本）调整相似性函数。对于分类数据的情况，使用相似性函数而不是距离函数更常见，因为离散值可以更自然地匹配。

考虑两条记录$\overline{X} =(x_1 \dots x_d)$和$\overline{Y} =(y_1 \dots y_d)$。记录$X$和$Y$之间最简单的可能相似性是各个属性值的相似性总和。换句话说，如果$S(x_i,y_i)$是属性值$x_i$和$y_i$之间的相似度，则总体相似度定义如下：

$$Sim(\overline{X},\overline{Y})=\sum_{i=1}^d S(x_i,y_i).$$

因此，$S(x_i,y_i)$的选择定义了总体相似度函数。

最简单的选择是当$x_i = y_i$时将$S(x_i,y_i)$设置为1，否则设置0。这也被称为重叠$(overlap)$度量。这一措施的主要缺点是它没有考虑不同属性之间的相对频率。例如，考虑一个分类属性，其中99％的记录属性值为“正常”，其余记录为“癌症”或“糖尿病”。显然，如果两个记录对这个变量有一个“正常”的值，那么这并没有提供关于相似性的统计意义上的重要信息，因为大多数的对都可能只是碰巧显示了这个模式。但是，如果这两个记录具有与此相匹配的“癌症”或“糖尿病”值，那么它提供了相似性的重要统计证据。这个论点与之前关于全局数据分布重要性的论点类似。异常的异同在统计上比那些常见的更重要。

在分类数据的情况下，数据集的*总体统计特性*应该用于计算相似性。这类似于使用马哈拉诺比斯距离如何使用全局统计数据更准确地计算相似性。这个想法是，对一个分类属性的异常值的匹配应该比经常出现的值的权重更大。这也构成许多常用规范化技术的基本原理，这些技术在文本等领域中使用。下一节讨论的一个例子是在信息检索领域*逆文档频率* $(IDF)$的使用。这里将介绍类别数据的类似度量。

*逆出现频率*是简单匹配度量的泛化。该度量通过匹配值的频率的反函数来加权两个记录的匹配属性之间的相似度。因此，当$x_i = y_i$时，相似度$S(x_i,y_i)$等于逆加权频率，否则为0。令$p_k(x)$为第k个属性在数据集中取$x$值的记录分数。换句话说，当$x_i = y_i$时，$S(x_i,y_i)$的值为$1 / p_k(x_i)^2$，否则为0。

$$\displaystyle S(x_i,y_i)= \begin{cases} 1/p_k(x_i)^2 &\text{if}\ x_i=y_i \\[2ex] 0 &\text{otherwise} \end{cases} \tag{3.6}$$

一个相关的措施是古道尔的措施。如逆出现频率的情况那样，当值不频繁时，将较高的相似度值分配给匹配。在这个度量[104]的简单变体中，当$x_i = y_i$时，第$k$个属性的相似度定义为$1-p_k(x_i)^2$，否则为0。

$$\displaystyle S(x_i,y_i)= \begin{cases} 1-p_k(x_i)^2 &\text{if}\ x_i=y_i \\[2ex] 0 &\text{otherwise} \end{cases} \tag{3.7}$$

书目注释包含指向分类数据的各种相似性度量的指针。

3.2.3 混合定量和分类数据

通过添加数字和定量组件的权重，将混合数据的方法推广到相当简单。主要挑战是决定如何分配定量和分类组件的权重。例如，考虑两条记录$\overline{X} =(\overline{X_n},\overline{X_c})$和$\overline{Y} =(\overline{Y_n},\overline{Y_c})$，其中$\overline{X_n}$，$\overline{Y_n}$是数值属性的子集，$\overline{X_c}$，$\overline{Y_c}$是分类属性的子集。然后，$\overline{X}$和$\overline{Y}$之间的总体相似性定义如下：

$$Sim(\overline{X},\overline{Y})=\lambda\cdot NumSim(\overline{X_n},\overline{Y_n}) + (1-\lambda)\cdot CatSim(\overline{X_c},\overline{Y_c}).\tag{3.8}$$

参数$\lambda$调节分类属性和数字属性的相对重要性。 $\lambda$的选择是困难的。在缺乏关于属性相对重要性的领域知识的情况下，自然选择是使用等于数据中数值属性部分的$\lambda$值。此外，数值数据中的接近度通常使用距离函数而不是相似度函数来计算。但是，距离值也可以转换为相似度值。对于$dist$的距离值，常用的方法是使用产生相似度值为$1/(1 + dist)$的核映射[104]。

需要进一步的归一化以有意义地比较可能处于完全不同尺度的数值和分类属性上的相似性值分量。实现这一目标的一种方法是使用记录样本对来确定两个域中相似值的标准差。相似度值（数值或分类）的每个分量除以其标准偏差。因此，如果$\sigma_c$和$\sigma_n$是分类和数值分量中相似值的标准偏差，那么公式 3.8需要修改如下：

$$Sim(\overline{X},\overline{Y})=\lambda\cdot NumSim(\overline{X_n},\overline{Y_n})/\sigma_n + (1-\lambda)\cdot CatSim(\overline{X_c},\overline{Y_c})/\sigma_c.\tag{3.9}$$

通过执行这种规范化，$\lambda$的值变得更有意义，作为两个组件之间的真实*相对权重*。默认情况下，除非有关属性的相对重要性的特定领域知识可用，否则可以将此权重设置为与每个组件中的属性数量成比例。

3.3 文本相似性度量

严格地说，只有当文字被视为一袋文字时，它才可以被认为是定量的多维数据。每个单词的频率可以被视为一个量化的属性，基础词汇可以被视为整套属性。然而，文本的结构是稀疏的$(sparse)$，其中大多数属性取值为0。而且，所有的词频都是非负的。这种特殊的文本结构对相似性计算和其他挖掘算法具有重要意义。诸如$L_p-$范数之类的措施不能很好地适应集合中不同文档的长度。例如，两个长文件之间的$L_2-$距离几乎总是大于两个短文件之间的距离，即使这两个长文件有许多共同的单词，并且短文件是完全不相交的。如何规范这种没有规律的现象？这样做的一种方法是使用余弦测量。余弦度量计算两个文档之间的角度，这对文档的绝对长度不敏感。令$\overline{X} =(x_1 \dots x_d)$和$\overline{Y} =(y_1 \dots y_d)$是大小为$d$的词典中的两个文档。然后，$\overline{X}$和$\overline{Y}$之间的余弦测度$cos(\overline{X},\overline{Y})$可以定义如下：

$$cos(\overline{X},\overline{Y})={{\textstyle\sum_{i=1}^d x_i \cdot y_i}\over{\sqrt{\textstyle \sum_{i=1}^d x_i^2}\cdot \sqrt{\sum_{i=1}^d y_i^2}}} \tag{3.10}$$

上述措施仅使用属性之间的原始频率。 但是，与其他数据类型一样，可以使用全局统计量度来改进相似性计算。 例如，如果两个文档匹配一个不常见的单词，则它比两个文档匹配一个常见单词的情况更具有相似性。逆文档频率$id_i$，它是第$i$个词出现的文档$n_i$的数量的递减函数，通常用于归一化： $$ id_i=log(n/n_i).\tag{3.11} $$

这里，集合中的文档数量用$n$表示。 另一个常见的调整是确保单个词的过度存在不会影响相似性度量。 在相似性计算之前，可以对频率应用一个如平方根或对数的衰减函数$f(\cdot)$。

$$f(x_i)=\sqrt{x_i}\\ f(x_i)=log(x_i)$$

在许多情况下，不使用衰减函数，这相当于将$f(x_i)$设置为$x_i$。 因此，可以如下定义第$i$个词的归一化频率$h(x_i)$:

$$h(x_i)=f(x_i)\cdot id_i.\tag{3.12}$$

然后，余弦测量定义如公式 3.10，除了使用单词的标准化频率：

$$cos(\overline{X},\overline{Y})=\frac {\sum_{i=1}^d h(x_i) \cdot h(y_i)}{{\sqrt{\textstyle \sum_{i=1}^d h(x_i)^2}\cdot \sqrt{\sum_{i=1}^d h(y_i)^2}}} \tag{3.13}$$

$ Jaccard$系数 $J(\overline{X},\overline{Y})$是另一种不常用于文本的方法：

$$J(\overline{X},\overline{Y})={{\textstyle\sum_{i=1}^d h(x_i) \cdot h(y_i)}\over{\textstyle \sum_{i=1}^d h(x_i)^2 + \sum_{i=1}^d h(y_i)^2 - \sum_{i=1}^d h(x_i)\cdot h(y_i)}}.\tag{3.14}$$

Jaccard系数很少用于文本领域，但通常用于稀疏二进制数据集。

3.3.1 二进制和集合数据

二进制多维数据是基于集合的数据的表示，其中值为1表示集合中存在元素。 二进制数据通常出现在市场领域中，其中交易包含与交易中是否存在物品相对应的信息。 它可以被认为是文本数据的一个特殊情况，其中词频是0或1。如果$S_X$和$S_Y$是具有二进制表示$\overline{X}$和$\overline{Y}$的两个集合，那么可以证明应用方程 3.14到两组的原始二进制表示相当于：

$$J(\overline{X},\overline{Y})={{\textstyle\sum_{i=1}^d x_i \cdot y_i}\over{\textstyle \sum_{i=1}^d x_i^2 + \sum_{i=1}^d y_i^2 - \sum_{i=1}^d x_i\cdot y_i}}={{|S_X\cap S_Y|}\over{|S_X \cup S_Y|}}.\tag{3.15}$$

这是一个特别直观的方法，因为它仔细考虑了两组中常见元素和不相交元素的数量。

3.4 时间相似性度量

时间数据包含表示时间的单个上下文属性以及测量在特定时间段内变化的属性的一个或多个行为属性。可以根据应用属性将时间数据表示为连续的时间序列，或者表示为离散序列。后一种表述可能被视为前者的不连续版本。应该指出，离散序列数据并不总是具有时序性的，因为上下文属性可能表示位置，在生物序列数据中比较常见。离散序列有时也被称为*字符串*。许多用于时间序列和离散序列的相似性度量都可以在任意域中重用，尽管一些度量更适合于其中一个域。因此，本节将讨论这两种数据类型，并将根据其最常见的用途，在连续序列或离散序列的小节中讨论每个相似性度量。对于某些度量，这两种数据类型的用法是通用的。

3.4.1 时间序列相似性度量

时间序列相似性度量的设计具有很高的应用特定性。例如，两个相等长度的时间序列之间最简单可能的相似性度量就是欧几里德度量。尽管这样的度量标准在许多情况下都可以很好地工作，但它并没有考虑到许多应用中常见的失真因素。其中一些因素如下：

1. *行为属性缩放和平移：*在许多应用中，不同的时间序列可能不会以相同的比例绘制。例如，表示各种股票价格的时间序列可能表现出类似的变化趋势，但在平均值和标准偏差的绝对值方面可能会有很大不同。例如，几个不同的假设股票代号的股价如图3.7所示。所有三个系列都显示相似的模式，但具有不同的缩放比例和一些随机变化。显然，它们显示出相似的模式，但如果使用该系列的绝对值，则不能进行有意义的比较。
2. *时间（上下文）属性平移：*在一些应用中，例如金融市场的实时分析，不同的时间序列可能代表相同的时间段。在其他应用中，例如从医学测量中获得的时间序列的分析，读取时间的绝对时间戳并不重要。在这种情况下，时间属性值需要在至少一个时间序列中移位以允许更有效的匹配。
3. 时间（上下文）属性缩放：*在这种情况下，可能需要沿着时间轴拉伸或压缩该系列以允许更有效的匹配。这被称为*时间扭曲。另外一个复杂的情况是，该系列的不同时间片段可能需要以不同的方式进行变形以允许更好的匹配。在图3.7中，显示了最简单的扭曲情况，即股票A的整组值已被拉伸。通常，在同一系列中的不同窗口可能被拉伸或压缩的情况下，时间扭曲可能更复杂不同。这被称为*动态*时间规整$(DTW)$。
4. *匹配中的不连续性：*长时间序列可能有一些不太匹配的有噪声的片段。例如，图3.7中的其中一个系列由于数据收集限制而导致丢失读数的窗口。这在传感器数据中很常见。距离函数可能需要对这种噪声是鲁棒的。

其中一些问题可以通过预处理期间的属性规范化来解决。

3.4.1.1行为属性标准化的影响

与上下文属性相比，平移和缩放问题通常更易于解决行为属性，因为它们可以在预处理期间通过规范化来解决：

1. *行为属性平移：*行为属性在预处理期间居中。

2. *行为属性缩放：*行为属性的标准偏差缩放为1个单位。

请务必记住，这些规范化问题可能与每个应用程序无关。一些应用程序可能只需要平移，只需要缩放，或两者都不需要，或者其他应用程序可能都需要。事实上，在某些情况下，标准化的错误选择可能会对结果的可解释性产生不利影响。因此，分析人员需要根据应用的具体需求明智地选择标准化方法。

3.4.1.2 $ L_p-$范数

可以为两个系列$\overline{X} =(x_1 \dots x_n) <span><span class="MathJax_Preview">和</span><script type="math/tex">和$\overline{Y} =(y_1 \dots y_n)\overline{Y} =(y_1 \dots y_n)定义$L_p-$范数。此度量将时间序列视为一个多维数据点，其中每个时间戳都是一个维度。

$$Dist(\overline{X},\overline{Y})=\left (\displaystyle\sum_{i=1}^n|x_i-y_i|^P\right)^{1/p}\tag{3.16}$$

$L_p-$范数也可以应用于时间序列的小波变换。在$p = 2$的特殊情况下，如果在表示中保留了大部分较大的小波系数，则可以用小波表示获得精确的距离计算。事实上，可以看出，如果没有去除小波系数，则两个表示之间的距离是相同的。这是因为小波变换可以看作是坐标轴的旋转，其中每个维度代表一个时间戳。欧几里德度量对于坐标轴旋转是不变的。 $L_p-$范数的主要问题是它们是为时间序列长度相等而设计的，并不能解决时间（上下文）属性的扭曲问题。

3.4.1.3 动态时间规整距离

$DTW$沿时间轴以不同的（或*动态的*）方式将序列拉伸到不同的部分以使更有效的匹配。图3.8a中举例说明了扭曲，其中两个系列在A，B和C区段中具有非常相似的形状，但是每个系列中的特定区段需要适当拉伸以实现更好的匹配。$DTW$测量已经从语音识别领域进行了改进，其中时间扭曲被认为是匹配不同说话速度所必需的。 $DTW$可用于时间序列或序列数据，因为它仅解决上下文属性缩放的问题，并且与行为属性的性质无关。以下描述是通用的，可用于时间序列或序列数据。

$L_p-$度量只能在两个等长的时间序列之间定义。然而，$DTW$就其本质而言允许测量两个*不同*长度系列之间的距离。在$L_p-$距离中，两个时间序列的时间戳之间存在一对一的映射关系。但是，在$DTW$中，允许考虑多对一映射时间扭曲。这种多对一的映射可以考虑重复两个时间序列中的任何一个的仔细选择的片段中的一些元素。这可以用来人为地创建两个相同长度的系列，它们之间具有一对一的映射关系。可以使用任何距离度量诸如$L_p-$范数在所产生的扭曲序列上测量距离。例如，在图3.8b中，重复这两个系列的几个片段中的某些元素，以创建两个系列之间的一对一映射。请注意，这两个系列现在看起来比图3.8a中的两个系列更相似。当然，这种重复可以以许多不同的方式完成，目标是以*最佳*方式执行它以最小化$DTW$距离。使用动态编程来确定最佳的扭曲选择。

为了理解$DTW$如何推广到一对一距离度量（如$L_p-$范数），考虑在两个等长的时间序列$\overline{X} =(x_1 \dots x_n)$和$\overline{Y}=(y_1 \dots y_n)$的前$i$个元素上计算的$L_1$（曼哈顿）度量$M(\overline{X_i},\overline{Y_i})。$$M(\overline{X_i},\overline{Y_i})$的值可以*递归地*写成如下形式：

$$M(\overline{X_i},\overline{Y_i})=|x_i-y_i|+M(\overline{X_{i-1}},\overline{Y_{i-1}}).\tag{3.17}$$

请注意，由于一对一匹配，两个系列的索引在右侧*同时*减少1。在$DTW$中，两个索引不需要减少1个单位，因为允许多对一映射。相反，取决于两个时间序列（或序列）之间的*最佳匹配*，任何一个或两个索引可以减少1。没有减少1的索引对应于重复的元素。指数减少的选择是递归地自然定义的，作为对各种选项的优化。

令$DTW(i,j)$分别为两个时间序列$\overline{X} =(x_1 \dots x_m) <span><span class="MathJax_Preview">和</span><script type="math/tex">和$\overline{Y} =(y_1 \dots y_n)\overline{Y} =(y_1 \dots y_n)的第$i$个和第$j$个元素之间的最佳距离。请注意，两个时间序列的长度为$m$和$n$，可能不一样。然后，递归地定义$DTW(i,j)$的值如下：

$$DTW(i,j)=distance(x_i,y_j)+min \begin{cases} DTW(i,j-1) &repeat \ x_i \\ DTW(i-1,j) &repeat \ y_i \\ DTW(i-1,j-1) &repeat \ neither \end{cases} \tag{3.18}$$

$distance(x_i,y_j)$的值可以以各种方式来定义，这取决于应用领域。例如，对于连续时间序列，它可以被定义为$| x_i - y_i |^ p$，或者由（行为属性）缩放和平移的距离来定义。对于离散序列，可以使用分类度量来定义。 $DTW$方法主要集中于扭曲*上下文*属性，与行为属性或距离函数的性质无关。由于这个事实，通过简单地使用递归中的多个属性的距离，时间扭曲可以很容易地扩展到多个行为属性。

公式3.18产生一种自然迭代方法。该方法首先将$DTW(0,0)$初始化为0，将$DTW(0,j)$初始化为$\infty$，其中$j \in \{1 \dots n\}$，将$DTW(i,0)$初始化为$\infty$，其中$i \in \{1 \dots m\}$。该算法通过增加$i$和$j$的索引值，重复执行方程式3.18计算$DTW(i,j)$。这可以通过一个简单的嵌套循环来实现，其中索引$i$和$j$分别从1增加到$m$和1到$n$：

$$\text{对于$i = 1$到$m$}\\ \quad\text{对于$j = 1$到$n$}\\ \qquad\text{使用公式3.18计算$DTW(i,j)$}​$$

上述代码片段是一种非递归和迭代的方法。直接使用公式3.18也可以实现递归计算机程序。因此，该方法需要为每个$i \in [1,m]$和每个$j \in [1,n]$计算$DTW(i,j)$的所有值。这是一个$m\times n$的网格值，因此该方法可能需要$O(m\cdot n)$次迭代，其中$m$和$n$是该序列的长度。

如图3.9所示，最优扭曲可以理解为通过$m\times n$网格值中的不同$i$和$j$值的*最佳路径*。图中显示了三种可能的路径，用$A$，$B$和$C$表示。这些路径只移动到右边（增加$i$和重复$y_j$），向上（增加$j$和重复$x_i$），或两个方向都移动（不重复）。

$DTW$计算通常会添加许多实际的约束条件。一个常用的约束是在匹配元素之间施加最小值$w$的位置对齐的*窗口约束*。窗口约束要求仅在$| i - j |≤w$时计算$DTW(i,j)$。否则，默认情况下，该值可能被设置为$\infty$。例如，图3.9中的路径$B$和$C$不再需要计算。这节省了动态编程递归中许多值的计算。相应地，上面嵌套循环的内部变量$j$中的计算可以通过约束索引j来保存，因此它不会比外部循环变量$i$多出$w$单位。因此，内环索引$j$从$max \{0，i-w\}$变化到$min \{n，i + w\}$。

如果假定不同的行为属性具有相同的时间扭曲，则$DTW$距离可以容易地扩展到多个行为属性。在这种情况下，递归不变，唯一的区别是距离$(\overline{x_i},\overline{y_j})$是使用基于矢量的距离度量来计算的。我们用$\overline{x_i}$和$\overline{y_j}$上的一个条来表示这些是多个行为属性的向量。这个多变量的扩展在第16章的第16.3.4.1节中讨论，用于测量二维轨迹之间的距离。

3.4.1.4 基于窗口的方法

图3.7中的示例说明了丢失的读数可能导致匹配出现空隙的情况。基于窗口的方案试图将两个系列分解成窗口，然后将相似性度量“拼接”在一起。这里的直觉是，如果两个系列具有许多连续的匹配段，则应该认为它们是相似的。对于长时间序列，全局匹配变得越来越不可能。唯一合理的选择是使用窗口来测量分段的相似度。

考虑两个时间序列$\overline{X}$和$\overline{Y}$，$\overline{X_1} \dots \overline{X_r}$和$\overline{Y_1} \dots \overline{Y_r}$是从相应序列中提取的时间有序和非重叠窗口。请注意，基本序列中的一些窗口可能不包含在这些段中（被丢弃的噪音段）。那么，$\overline{X}$和$\overline{Y}$之间的总体相似度可以计算如下：

$$Sim(\overline{X},\overline{Y})=\sum_{i=1}^r Match(\overline{X_i},\overline{Y_i}).\tag{3.19}$$

本节讨论的各种措施可用于实例化$Match(\overline{X_i},\overline{Y_i})$的值。确定$Match(\overline{X_i},\overline{Y_i})$的正确值是很棘手的，因为长窗口的连续匹配比许多相同长度的短段更难。$Match(\overline{X_i},\overline{Y_i})$的正确选择可能取决于实际的应用程序。另一个问题是，将序列最优分解成窗口可能是一项艰巨的任务。这些方法在这里没有详细讨论，但感兴趣的读者可以参考书目注释以获得相关方法的指示。

3.4.2 离散序列相似性度量

离散序列相似性度量是基于时间序列相似性度量的一般原则。就时间序列数据而言，离散序列数据可能存在或可能没有位置之间的一对一映射。当一对一映射确实存在时，正如范数可以适应连续时间序列一样，许多多维分类距离度量可以适应该域。然而，离散序列数据的应用领域通常是一对一映射不存在的。除了$DTW$方法之外，还有许多其他动态编程方法。

3.4.2.1 编辑距离

编辑距离将两个字符串之间的距离定义为通过使用称为“编辑”的一系列变换操作将一个序列变换成另一个序列所需的*最少*量“努力”（或*成本*）。编辑距离也被称为作为$Levenshtein$距离。编辑操作包括使用符号插入，删除和具有特定成本的替换。在许多模型中，假定替换的成本高于插入或删除的成本，尽管插入和删除通常被假定为具有相同的成本。考虑在字母表$\{a,b\}$上绘制的序列$ababababab$和$bababababa$。第一个字符串可以通过多种方式转换为第二个字符串。例如，如果第一个字符串中的每个字母都被另一个字母替换，生成第二个字符。这样做的代价是需要替换10次。但是，实现相同目标的更具成本效益的方法是删除字符串的最左侧元素，并将符号“$a$”插入最右侧的元素中。这一系列操作的成本只有一个插入和一个删除。编辑距离被定义为用一系列插入，删除和替换将一个字符串转换为另一个字符串的最优成本。最优成本的计算需要动态编程递归。

对于两个序列$\overline{X} = (x_1\dots x_m)$和$\overline{Y} = (y_1 \dots y_n)$，通过编辑在序列$\overline{X}$的基础上变换为$\overline{Y}$。请注意，由于编辑的方向性，此距离函数是不对称的。例如，如果插入和删除成本不相同，则$Edit(\overline{X},\overline{Y})$可能与$Edit(\overline{Y},\overline{X})$不同。然而，在实践中，插入和删除成本假定是相同的。

令$I_{ij}$为二进制指标，当$\overline{X}$的第$i$个符号和$\overline{Y}$的第$j$个符号相同时，该指标为0。否则，该指标的值为1。然后，考虑$\overline{X}$的前$i$个符号和$\overline{Y}$的前$j$个符号。假设这些段分别由$\overline{X_i}$和$\overline{Y_j}$表示。令$Edit(i,j)$表示这些段之间的最佳匹配成本。目标是确定在$\overline{X_i}$的最后一个元素上执行什么操作，以便它匹配$\overline{Y_j}$中的元素或将其删除。出现三种可能性：

1. 删除$\overline{X_i}$的最后一个元素，其成本为$[Edit(i-1,j)+ Deletion \ Cost]$。截断段$\overline{X_{i-1}}$的最后一个元素可能匹配或不匹配$\overline{Y_j}$的最后一个元素。

2. 在$\overline{X_i}$的末尾插入一个元素以匹配$Y_j$的最后一个元素，其成本为$[Edit(i,j-1)+ Insertion \ Cost]$。编辑项$Edit(i,j - 1)$的索引反映了两个序列的匹配元素现在可以被删除的事实。

3. 如果$\overline{X_i}$的最后一个元素*不同*，$\overline{X_i}$的最后一个元素被翻转为$\overline{Y_j}$，并且这个操作的成本是$[Edit(i-1,j-1)+ I_{ij}\cdot (Replacement \ Cost)]$。在最后一个要素相同的情况下，额外的重置成本不会发生，但是匹配仍然取得进展。这是因为两个系列的匹配元素$(x_i,y_j)$不需要进一步考虑，剩余匹配成本是$Edit(i-1,j-1)$。

显然，最好选择这些成本中的最小值来进行最佳匹配。因此，最佳匹配由以下递归定义：

$$Edit(i,j)=min \begin{cases} Edit(i-1,j)+Deletion \ Cost \\ Edit(i,j-1)+ Insertion \ Cost \\ Edit(i-1,j-1)+I_{ij}\cdot(Replacement \ Cost) \end{cases}. \tag{3.20}$$

此外，递归的下限也需要设置。 $Edit(i,0)$的值等于$i$的任何值的$i$删除成本，而$Edit(0,j)$的值等于任何$j$值的$j$插入成本。这很好地设置了动态编程方法。可以将相应的计算机程序编写为非递归嵌套循环（如$DTW$）或直接使用上述情况的递归计算机程序。

上述讨论假定一般插入，删除和替换成本。然而，在实践中，插入和删除成本通常被假定为相同。在这种情况下，编辑功能是对称的，因为两个字符串中的哪一个编辑到另一个并不重要。对于从一个字符串到另一个字符串的任何编辑序列，将会存在相同成本的从另一个字符串到第一个字符串的相反编辑序列。

通过将*插入*，*删除*和*替换*的基本操作更改为针对时间序列设计的转换规则，可以将编辑距离扩展为数字数据。这种转换规则可以包括对窗口段中时间序列的形状进行基本改变。这更复杂，因为它需要设计允许的时间序列形状转换的基本集合及其成本。这种方法在时间序列距离计算中没有得到广泛的普及。

3.4.2.2 最长的公共子序列

序列的*子序列*是从序列中按照与原始序列相同的顺序绘制的一组符号。子序列不同于*子字符串*，因为子序列的值不必是连续的，而子字符串中的值需要是连续的。考虑序列$agbfcgdhei$和$afbgchdiei$。在这种情况下，$ei$是两个序列的子串，也是子序列。但是，$abcde$和$fgi$是两个字符串的子序列，但不是子字符串。显然，长度较长的子序列表示字符串之间的匹配程度更高。与编辑距离不同，最长的公共子序列（$LCSS$）是一个相似性函数，因为较高的值表示较大的相似性。可能子序列的数量与字符串的长度呈指数关系。然而，可以用动态规划方法在多项式时间内计算$LCSS$。

对于两个序列$\overline{X} = (x_1\dots x_m)$和$\overline{Y} = (y_1 \dots y_n)$，考虑$\overline{X}$的前$i$个符号和$\overline{Y}$的前$j$个符号。假设这些段分别由$\overline{X_i}$和$\overline{Y_j}$表示。设$LCSS(i,j)$表示这些段之间的最佳$LCSS$值。这里的目标是匹配$\overline{X_i}$和$\overline{Y_j}$的最后一个元素，或者删除两个序列之一中的最后一个元素。出现两种可能性：

1. $\overline{X_i}$的最后一个元素匹配$\overline{Y_j}$，在这种情况下不会伤害到在最后一个元素上实例化匹配，然后删除这两个序列的最后一个元素。因为这是$LCSS(i-1,j-1)+1$可以递归地表达$LCSS(i,j)$。

2. 最后一个元素不匹配。在这种情况下，两个字符串中的至少一个字符串的最后一个元素需要在假设不能出现在匹配中的情况下被删除。在这种情况下，$LCSS(i,j)$的值是$LCSS(i,j - 1)$或$LCSS(i - 1,j)$，具体取决于选择删除哪个字符串。

因此，最佳匹配可以通过枚举这些情况来表示：

$$LCSS(i,j)=max \begin{cases} LCSS(i-1,j-1)+1 &\text{only if $x_i=y_j$} \\ LCSS(i-1,j) &\text{otherwise(no match on $x_i$)} \\ LCSS(i,j-1) &\text{otherwise(no match on $y_j$)} \end{cases}.\tag{3.21}$$

此外，需要设置边界条件。对于$i$和$j$的任何值，$LCSS(i,0)$和$LCSS(0,j)$的值总是等于0。与$DTW$和编辑距离计算一样，可以设置嵌套循环来计算最终值。递归计算机程序也可以使用上述递归关系来实现。虽然$LCSS$方法是针对离散序列定义的，但它也可以在将时间序列值离散为一系列分类值之后应用于连续时间序列。或者，可以离散化两个连续时间戳之间的时间序列*移动*。离散化的具体选择取决于实际应用程序的目标。

3.5 图的相似性度量

图的相似性可以用不同的方式来衡量，取决于相似度是在两个图之间测量，还是在单个图中的两个节点之间测量。为了简单起见，本节以无向网络为假设，这些方法可以容易地推广到有向网络。

3.5.1 单个图中两个节点之间的相似性

令$G =(N,A)$为节点集$N$和边集$A$的无向网络。在一些领域中，成本与节点相关联，而在其他领域中，权重与节点相关联。例如，在书目网络等领域，边缘自然是加权的，而在道路网络中，边缘自然会产生成本。通常，*距离*函数与成本一起工作，而*相似*函数与权重一起工作。因此，可以假定指定了边$(i,j)$的代价$c_{ij}$或权重$w_{ij}$。通常可以使用简单的启发式内核函数将成本转换为权重（反之亦然），这些函数是以特定于应用程序的方式选择的。一个例子是热度核$K(x)= e^{-x^2 / t^2}$。

期望测量任何一对节点$i$和$j$之间的相似性。单个图中两个节点之间的相似性原理基于真实网络中的*同质*概念。同质的原则是，当网络中的节点通过边缘相互连接时，节点在网络中通常更加相似。这在很多领域都很常见，例如网络和社交网络。因此，通过*短路径*和*多条路径*连接的节点应该被认为更相似。后者的标准与节点之间的连通性概念密切相关。第一个标准在网络中使用最短路径算法相对容易实现。

3.5.1.1基于结构距离的测量

这里的目标是测量从任何源节点到网络中任何其他节点的距离。设$SP(s,j)$为从源节点$s$到任意节点$j$的最短路径距离。$ SP(s,j)$的值在$j = s$时被初始化为0，否则被初始化为$\infty$。然后，$s$到网络中所有其他节点的距离计算可以按照一定的顺序对网络中的每个节点恰好执行一次的步骤进行汇总：

• 到目前为止未检查的所有节点中，选择$SP(s,i)$值最小的节点$i$，并更新其每个邻居$j$的距离标签，如下所示：

$$\displaystyle SP(s,j)=min\{SP(s,j),SP(s,j)+c_{ij}\}.\tag{3.22}$$

这是众所周知的$Dijkstra$算法的本质。这种方法在网络边缘数量上是线性的，因为它只检查一次每个节点及其入度。该方法提供了单次通过单个节点到所有其他节点的距离。 $SP(s,j)$的最终值提供了节点$s$和节点$j$之间的结构距离的数值。基于结构距离的测量不会显著增加一对节点之间路径的多样性，因为它们只关注原始结构距离。

3.5.1.2 随机行走相似度

当节点对之间有不同数量的路径时，前面部分的结构测量不能很好地工作。例如，在图3.10中，节点$A$和$B$之间的最短路径长度是4，而在$A$和$C$之间的最短路径长度是3.然而，节点$B$应该被认为更类似于$A$，因为两个节点之间的连接通过*多种*路径更紧密。随机行走相似性的想法基于这个原理。

在基于随机行走的相似性中，方法如下：设想一个随机游走，从源节点$s$开始，然后以与$w_{ij}$成比例的加权概率进入相邻节点。此外，在任何给定的节点处，允许以被称为*重新启动概率*的概率“跳回”到源节点$s$。这将导致严重偏向源节点的概率分布。与s更类似的节点访问的概率较高。这种方法将很好地适应图3.10所示的情况，因为将更频繁地访问$B$。

这里的直觉如下：如果你在一个道路网络迷路了，随机开车，随机转向，你更可能达到哪个位置？你更*有可能*到达附近的地点，并且可以通过多种方式到达。因此，随机行程度量提供的结果不同于最短路径度量的结果，因为它在相似性计算期间还考虑了路径中的多重性。

这种相似性计算与$PageRank$的概念密切相关，$PageRank$用于通过搜索引擎对网页进行排名。测量节点之间相似性的相应修改也称为个性化$PageRank$，相对应的变体称为$SimRank$。本章不会讨论$PageRank$和$SimRank$计算的细节，因为它需要更多关于排名概念的背景知识。请参阅第18章第18.4节，其中提供了更完整的讨论。

3.5.2 两个图之间的相似性

在许多应用中，有多个图可用，有时需要确定多个图之间的距离。相似性计算的一个复杂因素是许多节点可能具有相同的标签，这使得它们难以区分。这种情况通常出现在化学化合物分析等领域。化合物可以表示为节点是元素，键是边的图形。因为一个元素可能在一个分子中重复，节点上的标签并不是独特的。在这种情况下确定图上的相似性度量是非常具有挑战性的，因为即使是确定这两个图是否相同的特殊情况也很困难。后一个问题被称为*图同构*问题，就是著名的$NP-hard$ [221]问题。已经提出了许多措施，例如图编辑距离和基于子结构的相似性，以解决这个非常困难的情况。每种方法的核心思想如下：

1. *最大公共子图距离：*当两个图共同包含一个大的子图时，它们通常被认为更相似。第17章第17.2节介绍了最大公共子图问题和相关距离函数。

2. *基于子结构的相似性：*虽然很难匹配两个大图，但匹配较小的子结构要容易得多。核心思想是计算两个图之间经常出现的子结构，并将其报告为相似性度量。这可以被认为是字符串中基于子序列相似性的图形模拟。第17章第17.3节详细讨论了基于子结构的相似性度量。

3. *图编辑距离：*这个距离度量类似于字符串编辑距离，并被定义为将一个图形转换为另一个图形所需的编辑数量。由于图匹配是一个难题，因此这个度量对于大图很难实现。图编辑距离将在第17章第17.2.3.2节中详细讨论。

4. *图形内核：*定义了许多内核函数来度量图形之间的相似度，如最短路径内核和随机游走内核。第17章第17.3.3节对此主题进行了详细讨论。

这些方法非常复杂，需要图表领域的很多背景知识。因此，这些措施的讨论推迟到本书的第17章。

3.6 监督相似函数

前面的部分讨论了不需要对用户意图有任何理解的相似性度量。在实践中，特征的相关性或距离函数的选择在很大程度上取决于实际的领域。例如，对于图像数据集，颜色特征或纹理特征的权重应该更大一些吗？在不考虑用户意图的情况下，这些方面不能用距离函数来建模。无监督措施，如$L_p-$范数，均等对待所有特征，对最终用户的相似性语义概念没有内在的理解。将这些信息并入相似函数的唯一方法是使用关于对象的相似性和不相似性的明确反馈。例如，反馈可以表示为以下几组对象：

$$\begin{align} &S=\{(O_i,O_j):O_i\text{ is similar to }O_j\}\\ &D=\{(O_i,O_j):O_i\text{ is dissimilar to }O_j\}. \end{align}$$

如何利用这些信息来改善相似性的计算？已经设计了许多专门的方法用于监督相似度计算。一种常见的方法是假设需要学习参数的相似性函数的特定闭型。一个例子是3.2.1.1节中的加权$L_p-$范数，其中由$\Theta$表示的参数对应于特征权重$(a_1 \dots a_d)$。因此，第一步是创建一个距离函数$f(O_i,O_j,\Theta)$，其中$\Theta$是一组未知权重。假定函数的较大的值表示更大的不相似性。因此，这是一个距离函数，而不是一个相似函数。然后，需要确定参数$\Theta$，以便尽可能接近地满足以下条件：

$$f(O_i,O_j,\Theta)=\begin{cases} 0 &\text{if }(O_i,O_j)\in S\\ 1 &\text{if }(O_i,O_j) \in \mathcal{D} \end{cases}.\tag{3.23}$$

这可以表示为$\Theta$上的最小二乘优化问题，其具有以下误差$E$：

$$\displaystyle E=\sum_{(O_i,O_j)\in S}(f(O_i,O_j,\Theta)-0)^2+\sum_{(O_i,O_j)\in \mathcal{D}}(f(O_i,O_j,\Theta)-1)^2.\tag{3.24}$$

通过使用任何现成的优化求解器，该目标函数可以针对$\Theta$进行优化。如果需要，可以在适当的地方添加额外的约束条件$\Theta \geq 0$。例如，当$\Theta$表示$Minkowski$度量中的特征权重$(a_1 \dots a_d)$时，假定系数的非负性是必然的。使用许多非线性优化方法可以很容易地解决这种约束优化问题。使用诸如$f(O_i,O_j,\Theta)$之类的闭型确保函数$f(O_i,O_j,\Theta)$可以在计算参数$\Theta$的一次性成本之后被有效计算。

在可能的情况下，应该使用用户反馈来提高距离函数的质量。学习距离函数的问题可以更一般地建模为分类的问题。分类问题将在第10章和第11章中详细研究。第10章以实例为基础的学习章节中还详细讨论了使用$Fisher$方法的监督距离函数设计。

3.7 总结

距离函数设计的问题在数据挖掘应用中至关重要。这是因为许多数据挖掘算法使用距离函数作为关键子程序，并且函数的设计直接影响结果的质量。距离函数对数据的类型，数据的维度以及数据分布的全局和局部特性高度敏感。

$L_p-$范数是用于多维数据的最常见的距离函数。这种距离函数似乎不适用于增加维度。随着维度的增加，$p$值越高，工作效率就越差。在某些情况下，已经表明，当在$(0,1)$范围内选择p时，分数度量特别有效。随着维度的增加，许多基于接近度的措施也被证明可以有效地发挥作用。

数据分布也对距离函数设计产生影响。使用全球分布的最简单可能的距离函数是马哈拉诺比斯度量。这个度量是欧氏度量的泛化，并且根据它们的方差来延伸沿着主要分量的距离值。一种更复杂的方法称为$ISOMAP$，它使用非线性嵌入来解释非线性数据分布的影响。当数据分布不均匀时，局部归一化往往可以提供更有效的措施。

其他数据类型（如分类数据，文本，时间和图形数据）也会带来更多挑战。时间序列和离散序列相似性度量的确定密切相关，因为后者可以被认为是前者的分类版本。主要问题是两个相似的时间序列可能表现出其行为属性和上下文属性的不同缩放比例。这需要通过对行为属性使用不同的规范化函数以及对上下文属性使用扭曲函数来解决。对于离散序列数据的情况，通常使用许多距离和相似性函数，例如编辑距离和$LCSS$。

因为距离函数通常旨在模拟用户的相似性概念，所以应尽可能使用反馈来改进距离函数设计。该反馈可以在参数化模型的范围内使用，以了解与用户提供的反馈一致的最佳参数。

3.8 书目注释

数据挖掘研究人员和从业人员近年来对相似性计算的问题进行了广泛的研究。高维数据的问题在[17,88,266]中进行了探讨。在[88]的工作中，分析了距离集中效应对高维计算的影响。 [266]中的工作显示了对局部敏感的拾取距离函数的相对优势。该工作还显示了曼哈顿度量在欧几里德度量上的优势。分数度量在[17]中提出，并且通常比曼哈顿和欧几里得度量提供更准确的结果。本章讨论的$ISOMAP$方法在[490]中提出。许多局部方法也可用于距离函数计算。一个有效的局部方法的例子是[543]中提出的基于实例的方法。

类别数据的相似性在[104]中得到了广泛的探讨。在这项工作中，分析了一些相似性度量，并对它们如何应用于异常值检测问题进行了测试。 $Goodall$措施在[232]中介绍。 [122]中的工作使用信息理论度量来计算相似度。本章讨论的大多数措施都不区分属性的不匹配。然而，[74,363,473]中提出的许多方法可以区分属性值的不匹配。前提是统计上预计不频繁的属性值会比频繁的属性值更加不同。因此，在这些方法中，当$x_i$和$y_i$不同时，$S(x_i,y_i)$并不总是被设置为0（或者相同的值）。局部相似性度量在[182]中给出。文本相似性度量已经在信息检索文献[441]中得到了广泛的研究。

时间序列相似性度量的领域是一个丰富的领域，并且在这种背景下设计了大量的算法。有关该主题的优秀教程可以在[241]中找到。在[130]中讨论了使用小波进行时间序列的相似性计算。尽管$DTW$已经广泛用于语音识别，但它在数据挖掘应用中的使用最早是由[87]提出的。随后，它在数据挖掘中被广泛用于基于相似性的应用[526]。数据挖掘应用中的主要挑战是其计算密集性。在时间序列数据挖掘文献中已经提出了许多方法[307]来加速$DTW$。在[308]中提出了一种计算$DTW$下界的快速方法，并说明了如何将它用于精确索引。在[53]中提出了一种基于窗口的方法来计算序列中噪声，缩放和平移的相似性。在[499，500]中提出了多元时间序列和序列中的相似搜索方法。编辑距离已广泛用于生物数据计算序列之间的相似性[244]。 [283，432]研究了时间序列相似性转换规则的使用。这种规则可以用来为连续时间序列创建编辑类似距离的度量。字符串编辑距离的方法在[438]中提出。在[141]中已经表明，$L_p-$范数如何与编辑距离相结合。 $LCSS$问题的算法可以在[77,92,270,280]中找到。这些算法的调查可以在[92]中找到。 [32]中讨论了多种其他的时间序列和序列相似性度量。

许多方法可用于图中的相似性搜索。在[62]中可以找到各种用于发现节点间距离的有效最短路径算法。页面排序算法在Web挖掘书[357]中讨论。 [221]中讨论了图的同构问题的$NP-hardness$以及与编辑距离有关的其他紧密相关的问题。 [119,120]已经研究了最大公共子图问题和图像距离问题之间的关系。在[520,521]中已经解决了子结构相似性搜索的问题以及子结构用于相似性搜索的问题。在[522]中提出了一种突变距离的概念来衡量两个图之间的距离。 [42]中提出了一种使用图的频繁子结构进行聚类中的相似性计算的方法。图的匹配技术的调查可以在[26]中找到。

用户监督已经在距离功能学习的范围内得到了广泛的研究。在[15]中提出了参数化$L_p-$范数权重的最早方法之一。距离函数学习的问题已经与分类的问题形式化地联系起来，并且最近已经进行了很详细的研究。 [33]中提供了涵盖距离函数学习中重要主题的调查。

3.9 练习

1. 对于$p=1,2,\infty$，计算$(1,2)$和$(3,4)$之间的$L_p-$范数。

2. 证明两个数据点之间的马哈拉诺比斯距离等于经过变换的数据集上的欧几里德距离，其中变换将数据投影到主成分上，并除以每个成分的标准差。

3. 从$UCI$机器学习库[213]下载*电离层数据集*，并计算所有数据点对之间的$L_p-$距离，$p = 1,2,\infty$。计算数据集上不同范数的的对比度度量。在对第一个$r$尺寸进行采样后重复练习，其中$r$从1到数据的完整维度变化。

4. 计算两组$\{A,B,C\}$和$\{A,C,D,E\}$之间基于匹配的相似度，余弦相似度和Jaccard系数。

5. 设$\overline{X}$和$\overline{Y}$是两个数据点。证明向量$\overline{X}$和$\overline{Y}$之间的余弦角度由下式给出：

$$cosine(\overline{X},\overline{Y})={{\|\overline{X}\|^2+\|\overline{Y}\|^2-\|\overline{X}-\overline{Y}\|^2}\over {2\|\overline{X}\|\|\overline{Y}\|}}.\tag{3.25}$$

1. 下载$UCI$机器学习资源库*的$KDD \ Cup$*网络入侵数据集[213]。创建一个仅包含分类属性的数据集。使用$(a)$匹配度量，以及$(b)$逆出现频率度量，来计算每个数据点的最近邻居。计算类标签上匹配的案例数量。

2. 仅使用数据集的量化属性重复练习6，并使用Lp范数，其中$p = 1,2,\infty$。

3. 使用数据集中的所有属性重复练习6。使用混合属性函数，以及练习6和7的分类距离函数和量化距离函数的不同组合。

4. 编写一个计算机程序来计算编辑距离。

5. 编写一个计算机程序来计算$LCSS$距离。

6. 编写一个计算机程序来计算$DTW$距离。

7. 假设$Edit(\overline{X},\overline{Y})$表示将字符串$\overline{Y}$转换为$\overline{Y}$的开销。证明$Edit(\overline{X},\overline{Y})$和$Edit(\overline{Y},\overline{X})$是相同的，只要插入和删除成本相同即可。

8. 计算$(a)\ ababcabc$和$babcbc$与$(b)\ cbacbacba$和$acbacbacb$之间的编辑距离和$LCSS$相似性。对于编辑距离，假设插入，删除或替换的成本相等。

9. 证明$Edit(i,j)$，$LCSS(i,j)$和$DTW(i,j)$在$i$和$j$中都是单调函数。

10. 使用以下两句之间的原始频率计算余弦测量值： （a）“狡猾的狐狸跳过懒狗。” （b）“狗扑向入侵者。”

11. 假设插入和删除成本为1，编辑距离的替换成本为2单位。证明两个字符串之间的最佳编辑距离只能通过插入和删除操作来计算。在上述成本假设下，表明最佳编辑距离可以表示为最佳LCSS距离和两个字符串的长度的函数。