下载掌阅APP，畅读海量书库
立即打开
许多数据挖掘任务需要计算数据对象之间的相似性或相异性，如聚类、最近邻分类、异常检测等。为了本节内容表述方便，假设两个数据对象 X = (x 1 … x d )和 Y = (y 1 … y d )，我们用sim( X , Y )表示它们的相似度，用Dist( X , Y )表示它们之间的相异度或距离。
相似度指两个对象相似程度的数值度量，对象越相似，数值越大，有sim( X , Y )=sim( Y , X )，且0≤sim( X , Y )≤1。相异度指两个对象差异程度的数值度量，距离可以作为相异度的同义词，两个数据所在的空间距离越大，表示数据越相异，有Dist( X , Y )=Dist( Y , X )且Dist( X , Y )≥0。相似性和相异性计算方法是一致的，通常是用两个对象之间的一个或多个属性距离来表示，它们要可以相互转换。除取值范围外，它们之间名称上的区分更多是源自习惯上的称谓。例如，两篇文章我们常称它们相似度是多少，而空间数据对象会称它们之间的距离是多少。我们使用术语“邻近度”来表示对象间的相似性或相异性。
数据对象之间的邻近度计算与数据对象属性类型密切相关。掌握简单属性之间的邻近度是计算复杂对象之间的邻近度的基础。本节分别以标称和数值类型属性介绍邻近性度量方法。
记录数据具有最简单的结构，是数据挖掘中最常见的数据对象。数值属性和标称属性的相似度计算方式明显不同，我们先介绍具有多维数值属性对象的邻近性度量方法。
序数属性值是有序序列，如size属性值{mini,small,medium,large}。邻近度的计算可以将这些属性值用数值代替，如{mini=0,small=1,medium=2,large=3}，那么计算两个对象的相异度，可以通过对应属性值的差值的绝对值表示。
数据集中的数据对象可以看作某空间下的点。在一般意义下，空间可看作点的全集，即数据集中的点可看作从空间中抽样而成。在欧几里得空间下，这样定义点有益于聚类。在欧几里得空间下的点就是实数向量，向量的长度就是空间的维度数，而向量的分量通常称为点的坐标。
在一个空间下进行聚类、或某些分类任务时，需要在该空间中找到一个距离测度，即给出该空间下任意两点之间的距离。距离测度是一个函数 d ( x , y )，以空间中的两个点作为参数，函数值是一个实数值，该函数必须满足下列准则。
①Dist( X , Y )≥0（距离非负）。
②当且仅当 x = y 时，Dist( X , Y )=0（只要点到自身的距离为0，其他的距离就都大于0）。
③Dist( X , Y )=Dist( Y , X )（距离具有对称性）。
④Dist( X , Y )≤Dist( X , Z )+Dist( Z , Y )（三角不等式）。
只有满足上述性质的距离测度才可以称为度量。在度量方法中，数据对象的属性以连续或离散数值的方式描述，数据对象可以看作度量空间（距离空间）中的点，数据对象之间的距离可以看作相似性的度量。
假设每个对象有 m 个属性，可以把一个对象视为 m 维空间的一个点， n 个对象就是 m 维空间中的 n 个点。从直观上看，属于同一类的对象在空间中应该互相靠近，而不同类的对象之间的距离要大得多，因此可用距离来衡量对象之间的相似程度。距离越小，对象间的相似性就越大。常用的距离形式有曼哈顿距离、欧几里得距离、切比雪夫距离、闵可夫斯基距离、杰卡德距离等。
1.曼哈顿距离
之所以称为“曼哈顿距离”（Manhattan Distance），是因为这里在两个点之间行进时必须要沿着网格线前进，就如同沿着城市（如曼哈顿）的街道行进一样。对于一个具有正南正北、正东正西方向规则布局的城市街道，从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离，是将多个维度上的距离进行求和的结果。其距离公式如下：
2.欧几里得距离
欧几里得距离（Euclidean Distance），也称为欧氏距离，是人们最为熟知的距离测度，也就是我们常说的“距离”。在 m 维欧几里得空间中，每个点是一个 m 维实数向量，该空间中的传统距离测度为 L 2 范式距离，定义如下：
也就是说，首先计算每一维上的距离，然后求它们的平方和，最后求算术平方根。
另一个有趣的距离测度是
L
∞
范式距离，也就是当
r
趋向无穷大时，
L
r
范式距离的极限值。当
r
增大时，只有那个具有最大距离的维度才真正起作用，因此，通常
L
∞
范式距离定义为在所有维度下
中的最大值。
3.切比雪夫距离
以数学的观点来看，切比雪夫距离（Chebyshev Distance）是由一致范数（Uniform Norm）（或称为上确界范数）所衍生的度量，也是超凸度量（Injective Metric Space）的一种。它产生两个数据对象的最大属性值差。
4.闵可夫斯基距离
闵可夫斯基距离（Minkowski Distance）又称为闵氏距离，是欧几里得距离、曼哈顿距离和切比雪夫距离的推广。闵可夫斯基距离对应 L p 范数，其中 p 是一个变参数，根据参数的不同，闵可夫斯基距离可以表示一类的距离。当 p =1时，就是曼哈顿距离；当 p =2时，就是欧几里得距离；当 p →∞时，就是切比雪夫距离。
【例2-17】考虑二维欧几里得空间（通常所说的平面）上的两个点（2，5）和（5，9）。它们的
L
2
范式距离为
=5，
L
1
范式距离为
=3+4=7，而
L
∞
范式距离为
=max（3，4）=4。
附注1：当 L 2 范式距离较小时，表示 x 与 y 在一个类型区域，反之，则不在一个类型区域。这里有一个门限的选择问题，若选择过大，则全部样本被视作唯一类型；若选择过小，则可能造成每个样本都单独构成一个类型。必须正确选择门限值以保证正确分类。
附注2：模式特征坐标单位的选取也会强烈地影响聚类结果。例如，在2维欧几里得空间中，其中一维是长度，另一维是压力。当长度单位由厘米变为米时，在 L 2 中长度特征的比重会下降，同样，若把比重单位由毫米汞柱高度变成厘米汞柱高度，在 L 2 中压力特征的影响也会减小。
附注3：使用欧几里得距离度量时，还需要注意样本测量值的选取，应该能有效反映类别属性特征（各类属性的代表应均衡）。例如，取5个样本，其中有4个反映对分类有意义的特征A，只有1个对分类有意义的特征B，欧几里得距离的计算结果则主要体现特征A。
5.杰卡德距离
杰卡德距离（Jaccard Distance）用于衡量两个集合的差异性，它是杰卡德相似度的补集，被定义为1减去杰卡德相似度。杰卡德相似度用于度量两个集合之间的相似性，它被定义为两个集合交集的元素个数除以并集的元素个数，即集合 A 和 B 的相似度sim( A , B )为：
多维二元数据，其某位数据为1表示元素集合中的某个元素出现，为0表示不出现。例如，超市的一张交易清单中用1或0来表示是否包含某件商品，一篇文章中用0或1来表示词语是否出现。多维二元数据情况下，集合 A 和 B 的相似度可以进一步写成：
集合 A 和 B 的杰卡德距离 d J ( A , B )为：
数值数据是有大小顺序的，距离公式非常适合计算不同维度的数值数据的邻近度。但是，离散的标称属性数据间并不存在大小顺序关系，不能直接用距离来计算相似度或相异度。
标称属性取值是代表事物状态的若干值，只包含了相异性信息。标称类型可以通过编码方案转换成二元数据类型，然后使用数值计算方法来计算邻近度。如果一个标称类型数据有 M 个不同的状态值，那么将该标称数据转换成 M 个二元属性值，每个标称状态值对应一个二元属性，这些二元属性中有一个值为1，剩余的值全为0。这样标称属性相似度计算就可以通过编码方式转化为多个二元属性的相似度计算。
简单二元属性的状态值为布尔值，可以用数字0和1分别来表示。例如，在某图书管理系统中描述图书对象的借出情况，可以用0表示在馆，用1表示借出。
考虑数据对象只有一个属性情况下：如果两个标称属性值匹配，则相似度为1，否则为0；相异度的值刚好相反，如果两个标称属性匹配，则相异度为0，否则为1。
一般地，二元属性相似度可以通过对属性匹配值求和来计算，即首先分别求解对应单个属性间的相似度，然后对所有相似度数值进行直接累加：
式中， d 代表对象的属性总数。更为直接地理解，相似度可用“取值相同的同位属性数/属性总位数”标识对于包含多个二元属性的数据对象相似度计算。
设有 X ={1,0,0,1,0,0,1,0,1,1}， Y ={0,0,0,1,0,1,1,1,1,1}，两个对象共有7个属性取值相同，3个取值不同，那么相似度可以标识为3/10=0.3。
这种方法非常简单，缺点是没有考虑不同属性的概率差异。上面所说的二元属性的两个状态具有同等价值和相同的权重，称为对称二元属性。对于非对称二元属性，我们只关心两者都取1的情况，而认为两者都取0的属性并不意味着两者更相似。
例如，在根据病情对患者聚类时，如果两个人都患有肺癌，我们认为这两个人增强了相似度，但如果两个人都没患肺癌，并不觉得这两个人增强了相似度，即同为0值的负匹配对相似度计算不起作用，而同为患肺癌结果包含了明显的统计信息。
这种情况下，即非对称二元相似度计算，可以改用“取值同为1的属性数/（单个元素的属性位数-同取0的位数）”来标识相似度。
前面所述的计算方法均为有关相同数据类型之间的相似度或相异度计算。现实世界中，多维数据对象属性的类型、分布、值域及权重都可能存在不同。这些问题需要采取适当措施进行处理。
1.距离度量的标准化和相关性
当数据对象属性具有不同的值域时，即属性变量的大小变化范围不同、量纲不同、测量单位不同。如果不对属性值进行标准化处理，那么在使用欧几里得距离计算相似度时，将会受到属性值大的属性影响。例如，第一个变量的数量级是1000，而第二个变量的数量级是10，如 v 1 =(2000，20)， v 2 =(5000，60)，那么如果在只有2维的点中，欧几里得距离为：
由上面可以很容易看出，当两个变量的数量级都变为10时，第一个变量存在一个权重——10，因而如果不使用相同尺度的时候，不同尺度的变量就会在计算的过程中自动地生成相应的权重。因而，如果两个变量在现实中的权重是相同的话，就必须要先进行规范化，化成相同的尺度，以消除由尺度造成的误差。
除值域不同会影响欧几里得距离度量结果外，属性之间可能存在相关性、数据分布不是正态分布等也会影响欧几里得距离度量结果。解决这些问题的方法是使用欧几里得距离的扩展马氏距离：
式中， ∑ -1 是数据协方差矩阵的逆。马氏距离有很多优点，马氏距离不受量纲的影响，两点之间的马氏距离与原始数据的测量单位无关；由标准化数据和中心化数据（原始数据与均值之差）计算出的两点之间的马氏距离相同。马氏距离还可以排除变量之间的相关性的干扰。
2.组合异种属性的相似度
前面所述的多维数据对象邻近度计算都是基于数据对象中所有属性具有相同的数据类型的，但是，现实中从数据库取出的数据类型可能是标称、数值、二元、序数等数据类型的组合。这种组合属性对象相似度最简单的计算方法是分别计算每个属性之间的相似度，然后取它们的均值。但是，对于取值是非对称属性的，采用上述方法会失效。例如，两个对象的二元非对称属性都取0值，并不能表示它们的相似性，可以在计算相似度时忽略，当二元非对称属性值为1时才加入相似度计算。
异种对象 X 、 Y 的相似度计算方法的步骤如下。
第1步：将第 k 个属性标准化到区间[0,1]，计算相似度 S k (X , Y )。
第2步：创建一个指示变量 δ k 用来标示两个对象在第 k 个属性上是否同时取值为0，如果同时为0，则 δ k =0，否则 δ k =1。
第3步：使用式（2.21）计算对象 X 、 Y 的相似度。
3.使用权值
前面所述的所有相似度计算，都是将对象的所有属性同等对待，没有区分不同属性的重要程度。当现实问题中属性的重要程度存在较大差异时，可以借助于领域专业知识，给它们赋予不同的权值，以期望获得更好的性能。相似度计算公式增加权值项后形式如下：
文档是由大量词语构成的，如果把特定词语出现的频率看作一个单独属性，那么文档可以由数千个词频属性构成的向量表示。词频向量通常很长，并且是稀疏的，因为它包括了大量的零值属性。统计两个文档中共同没有的词，即公共零值属性对计算它们之间的相似度并没有多大帮助。对于文档这种特殊结构数据，使用基于距离计算邻近度的方法，会受到大量零值的影响，评估效果并不好。文档相似度需要关注两个文档同时出现的词语，以及这些词语出现的次数，忽略零匹配的数值数据度量。
余弦相似度，又称为余弦相似性，适合用来计算文档之间的相似度。其原理是把两个文档以词频向量表示，通过计算两个向量的夹角余弦值来评估它们之间的相似度。
如果余弦值越接近于1，夹角越小，表示向量之间的匹配越大；如果余弦值为0，表示它们正交，没有匹配。
【例2-18】假设有两个文档，新闻 a 和新闻 b ，将它们的内容经过分词、词频统计处理后得到如下两个向量：
文档 a ：（1，1，2，1，1，1，0，0，0）
文档 b ：（1，1，1，0，1，3，1，6，1）
使用余弦相似度来计算两个文档的相似度的过程如下。
新闻
a
和新闻
b
对应的向量分别是
X
(
x
1
,
x
2
,…,
x
100
)和
Y
(
y
1
,
y
2
,…,
y
100
)，则新闻
a
和新闻
b
夹角
θ
的余弦为
。
（1）计算向量 a 、 b 的点积。
a · b =1×1+1×1+2×1+1×0+1×1+1×3+0×1+0×6+0×1=8
（2）计算向量
a
、
b
的欧几里得范数，即
、
：
（3）计算相似度。
当两条新闻向量夹角等于0°时，这两条新闻完全重复（用这个办法可以删除爬虫收集的网页中的重复网页）；当夹角接近于0°时，两条新闻相似（可以用作文本分类）；夹角越大，两条新闻越不相关。
到现在为止，实现了基于属性的原始出现频率计算文本间的相似度。考虑一种情况，当两个文本之间如果有一个不常见的词语成功匹配，这应该要比它们匹配一个非常常见的词更能说明相似性。例如，我们设计一个垃圾邮件过滤系统，“免费”“特惠”“推广”这样的词语要比“你”“但是”“那里”等更能表征问题。所以，我们需要一个重要性调整系数，衡量一个词是不是常见词。用统计学语言表达，就是在词频的基础上，要对每个词语分配一个“重要性”权重。
词频-逆文档频率（Term Frequency-Inverse Document Frequency，TF-IDF）是一种用于资讯检索与资讯探勘的常用加权技术。基于统计学方法来评估词语对文档的重要性。字词的重要性随着它在文档中出现的次数呈正比增加，但同时会随着它在语料库中出现的频率呈反比下降。
其中，词频（Term Frequency，TF）指的是某一个给定的词语在该文档中出现的次数。由于同一个词语在长文档中可能会比短文档有更高的词频，为了防止它偏向较长的文档，通常会采用词频除以文档总词数来归一化。
逆向文档频率（Inverse Document Frequency，IDF）的主要思想：出现频率较低的词才能够表达文档的主题。如果包含词语 w 的文档越少，IDF值越大，则说明词条具有很好的类别区分能力。为了避免分母为0值，分母做加1处理。
最终TF-IDF的计算公式为：
TF-IDF算法用来对文本进行特征提取，选出可以表征文章特性的关键词。假设文章 X 用由 d 个关键词的词频组成的向量 h （ x ）表示，两篇文章 X 、 Y 的相似度可表示为：
需要说明的是，因为余弦值的范围是[-1,1]，相似度计算时一般通过sim( X , Y )=0.5+0.5×cos( X , Y )把最终值归一化到[0,1]。
离散序列数据不同于多维数据，序列中的各个元素存在前后位置关系，如一个字符串、IP地址、基因序列等。当两个离散序列数据对象长度相等，即序列中的元素可以一一对应时，相似度计算可以采用欧几里得距离、闵可夫斯基距离等计算。但是当序列长度不同时，需要新的计算方法。本节将介绍编辑距离和最长公共子序列两个常用的动态规划算法。
1.编辑距离
编辑距离（Edit Distance）是指将序列 X = (x 1 … x m )变换为序列 Y = (y 1 … y m )所用的最少编辑操作次数Edit( X ， Y )。编辑操作类型包括字符的替换、插入和删除，这3种类型可以根据实际应用问题指定相同或不同的操作代价。一般来说，编辑距离越小，两个字符串的相似度越大。
例如，两个字符序列：abeedc和cbedac。我们可以用多种编辑方法将第一个序列转换成第二个序列。最简单的方法是将第一个序列先后经过将a替换成c，删除一个e，在c前面插入a，这3次编辑操作完成将前者转换成后者。
假设序列 X 的前 i 个元素子序列为 X i ，序列 Y 的前 j 个元素子序列为 Y j ，Edit( X , Y )表示它们之间的编辑距离，根据两个子序列末尾元素的不同，选择不同的编辑操作。编辑距离计算递推公式如下：
当 Y j 为空时，编辑代价为将 X i 中的所有元素删除：
当 X i 为空时，编辑代价为 j 次插入操作：
编辑距离具有下面几个性质。
（1）两个字符串的最小编辑距离是两个字符串的长度差。
（2）两个字符串的最大编辑距离是两个字符串中较长字符串的长度。
（3）只有两个相等的字符串的编辑距离才会为0。
(4)编辑距离满足三角不等式,即 d(x , z )≤ d(x , y)+d(y , z )。
【例2-19】有两个序列 S 1 和 S 2 ，分别为 XGYXYXYX 和 XYXYXYTX 。编辑距离计算矩阵如图2-14所示，最终计算结果为2，箭头标出了回溯路径。
图2-14 编辑距离计算矩阵
2.最长公共子序列
最长公共子序列（Longest Common Subsequence，LCS）的定义是：一个序列 S ，如果是两个或多个已知序列的子序列，且是最长的，则 S 称为已知序列的最长公共子序列。子序列要求左右两元素在母序列中为相邻元素，且前后顺序一致。
最长公共子串（要求连续）和最长公共子序列是不同的。例如，序列adbfucijdlmen和abf2ec3xdue，其中bf既是它们的公共子串，同时是它们的公共子序列，但是abf和cde是它们的公共子序列但不是公共子串。很明显，两个序列的公共子序列越长，则表明这两个序列之间的相似度越高。
设序列 X = {x 1 x 2 … x m }和 Y = {y 1 y 2 … y m }的最长公共子序列为 Z = {z 1 z 2 … z m }，则有如下特性。
（1）若 x m =y n ，则 z k =x m =y n ，且 z k -1 是 x m -1 和 y n -1 的最长公共子序列。
（2）若 x m ≠y n 且 z k ≠x m ，则 Z 是 x m -1 和 Y 的最长公共子序列。
（3）若 x m ≠y n 且 z k ≠y n ，则 Z 是 X 和 y n -1 的最长公共子序列。
由此可见，两个序列的最长公共子序列包含这两个序列前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质，可以使用动态规划算法求解。由最优子结构性质可建立如下递推关系：
当两个序列 X 、 Y 中任意一个为空集时，它们的最长公共子序列为零，即LCSS( i ,0)=0和LCSS)0, j) =0，这两个式子可以作为求解算法的边界条件。
相异度或相似度计算是数据挖掘应用中的重要问题。这是因为很多数据挖掘算法将距离计算方法作为关键子程序调用。距离度量方法深受数据类型、数据维度及数据分布的影响，并且距离度量方法直接影响到数据挖掘的最终成效。