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