相似性和相异性的度量

1、相似性和相异性的度量相似性和相异性是重要的概念，因为它们被许多数据挖掘技术所使用，如聚类、最近邻分类和异常检测等。在许多情况下，一旦计算出相似性或相异性，就不再需要原始数据了。这种方法可以看作将数据变换到相似性（相异性）空间，然后进行分析。首先，我们讨论基本要素-相-似性和相异性的高层定义，并讨论它们之间的联系。为方便起见，我们使用术语邻近度（）表示相似性或相异性。由于两个对象之间的邻近度是两个对象对应属性之间的邻近度的函数，因此我们首先介绍如何度量仅包含一个简单属性的对象之间的邻近度，然后考虑具有多个属性的对象的邻近度度量。这包括相关和欧几里得距离度量，以及和余弦相似性度量。前二者适用于时间

2、序列这样的稠密数据或二维点，后二者适用于像文档这样的稀疏数据。接下来，我们考虑与邻近度度量相关的若干重要问题。本节最后简略讨论如何选择正确的邻近度度量。1）基础1.定义两个对象之间的相似度（）的非正式定义是这两个对象相似程度的数值度量。因而，两个对象越相似，它们的相似度就越高。通常，相似度是非负的，并常常在（不相似）和（完全相似）之间取值。两个对象之间的相异度（）是这两个对象差异程度的数值度量。对象越类似，它们的相异度就越低。通常，术语距离（）用作相异度的同义词，正如我们将介绍的，距离常常用来表示特定类型的相异度。有时，相异度在区间中取值，但是相异度在和之间取值也很常见。2.变换通常使用变换把

3、相似度转换成相异度或相反，或者把邻近度变换到一个特定区间，如0,。例1如，我们可能有相似度，其值域从1到1，0但是我们打算使用的特定算法或软件包只能处理相异度，或只能处理0,区1间的相似度。之所以在这里讨论这些问题，是因为在稍后讨论邻近度时，我们将使用这种变换。此外，这些问题相对独立于特定的邻近度度量。通常，邻近度度量（特别是相似度）被定义为或变换到区间0,中1的值。这样做的动机是使用一种适当的尺度，由邻近度的值表明两个对象之间的相似（或相异）程度。这种变换通常是比较直截了当的。例如，如果对象之间的相似度在1（一点也不相似）和1（0完全相似）之间变化，则我们可以使用如下变换将它变换到区间：，其

4、中和分别是相似度的原值和新值。一般来说，相似度到区间的变换由如下表达式给出：，其中和分别是相似度的最大值和最小值。类似地，具有有限值域的相异度也能用映射到区间。然而，将邻近度映射到区间可能非常复杂。例如，如果邻近度度量原来在区间01上0取0值0，则需要使用非线性变换，并且在新的尺度上，值之间不再具有相同的联系。对于从变化到的相异度度量，考虑变换（相异度、2、和分别被变换到、0.、607.、90.9和90.9。9在9原来相异性尺度上较大的值被压缩到1附近，但是否希望如此则取决于应用。另一个问题是邻近度度量的含义可能会被改变。例如，相关性（稍后讨论）是一种相似性度量，在区间上取值，通过取绝对值将这

5、些值映射到区间丢失了符号信息，而对于某些应用，符号信息可能是重要的。将相似度变换成相异度或相反也是比较直截了当的，尽管我们可能再次面临保持度量的含义问题和将线性尺度改变成非线性尺度的问题。如果相似度（相异度）落在区间，则相异度（相似度）可以定义为（或，）相异度0,1,1分0别,被变1换0到0，它们分别被变换到）。另一种简单的方法是定义相似度为负的相异度（或相反）。例如，相异度0，1，10和10可0以分别变换成相似度0,-1,和，）相异度0,1,1分0别,被变1换0到0，它们分别被变换到。对于变换5,0；、对0于9；对于1dmin_d，它们分别被变换到。在这里的讨论中，我们关注将相异度变换到相似

6、度。一般来说，任何单调减函数都可以用来将相异度转换到相似度（或相反）。当然，在将相似度变换到相异度（或相反），或者在将邻近度的值变换到新的尺度时，也必须考虑一些其他因素。我们提到过一些问题，涉及保持意义、扰乱标度和数据分析工具的需要，但是肯定还有其他问题。2）简单属性之间的相似度和相异度通常，具有若干属性的对象之间的邻近度用单个属性的邻近度的组合来定义，因此我们首先讨论具有单个属性的对象之间的邻近度。考虑由一个标称属性描述的对象，对于两个这样的对象，相似意味什么呢？由于标称属性只携带了对象的相异性信息，因此我们只能说两个对象有相同的值，或者没有。因而在这种情况下，如果属性值匹配，则相似度定义为

7、1，否则为0；相异度用相反的方法定义：如果属性值匹配，相异度为0，否则为1。对于具有单个序数属性的对象，情况更为复杂，因为必须考虑序信息。考虑一个在标度上测量产品（例如，糖块）质量的属性。一个评定为的产品与一个评定为的产品应当比它与一个评定为的产品更接近。为了量化这种观察，序数属性的值常常映射到从或开始的相继整数，例如，。于是，与之间的相异度1或者，如果我们希望相异度在和之间取值，；序数属性的相似度可以定义为。序数属性相似度（相异度）的这种定义可能使读者感到有点担心，因为这里我们定义了相等的区间，而事实并非如此。如果根据实际情况，我们应该计算出区间或比率属性。值与的差真和与的差相同吗？可能不相

8、同，但是在实践中，我们的选择是有限的，并且在缺乏更多信息的情况下，这是定义序数属性之间邻近度的标准方法。对于区间或比率属性，两个对象之间的相异性的自然度量是它们的值之差的绝对值。例如，我们可能将现在的体重与一年前的体重相比较，说我重了磅。在这类情况下，相异度通常在和之间，而不是在和之间取值。如前所述，区间或比率属性的相似度通常转换成相异度。表总结了这些讨论。在该表中，和是两个对象，它们具有一个指明类型的属性，和分别是和之间的相异度和相似度（分别用和表示）。其他方法也是可能的，但是表中的这些是最常用的。象之间的相异度；（2数）据对象之间的相似度。这样分节可以更自然地展示使用各种邻近度度量的基本动

9、机。然而，我们要强调的是使用上述技术，相似度可以变换成相异度，反之亦然。数据对象之间的相异度本节，我们讨论各种不同类型的相异度。我们从讨论距离（距离是具有特定性质的相异度）开始，然后给出一些更一般的相异度类型的例子。距离我们首先给出一些例子，然后使用距离的常见性质更正式地介绍距离。一维、二维、三维或高维空间中两个点和之间的欧几里得距离（a由如下熟悉的公式定义:是维数，而和分别是和的第个属性值（分量）。我们用a由如下熟悉的公式定义:是维数，而和分别是和的第个属性值（分量）。我们用公式（2-、给出的欧几里得距离可以用公式（公式（2-、给出的欧几里得距离可以用公式（2-2的闵可夫斯基距离（）来推广：

10、其中是参数。下面是闵可夫斯基距离的三个最常见的例子。=城市街区（也称曼哈顿、出租车、范数）距离。一个常见的例子是汉明距离（），它是两个具有二元属性的对象（即两个二元向量）之间不同的二进制位个数。=欧几里得距离（范数）。上确界（或范数）距离。这是对象属性之间的最大距离。更正式地，距离由公式（）定义：注意不要将参数与维数（属性数）混淆。欧几里得距离、曼哈顿距离注意不要将参数与维数（属性数）混淆。欧几里得距离、曼哈顿距离和上确界距离是对的所有值（）和上确界距离是对的所有值（）3定,义.的.，.并且指定了将每个维（属性）上的差的组合成总距离的不同方法。表（属性）上的差的组合成总距离的不同方法。表2-1

11、和0表2-1分1别给出表2-数8据的阵。注意，所有的距离矩阵都是对称的，即第距离和距离的邻近度矩个表目与第个表目相同,鼻0仅当时鼻0仅当时W。）。有些人只对满足这三个性质的相异性度量使用术语距离，但在实践中常常违反这一约定。这里介绍的三个性质是有用的，数学上也是令人满意的。此外，如果三角不等式成立，则该性质可以用来提高依赖于距离的技术（包括聚类）的效率。尽管如此，许多相异度都不满足一个或多个度量性质。下面我们给出两个这种测度的例子。距例1距非距度量的相异度：集合差。距基于集合论中定义的两个集合差的概念举例。设有两个集合和，是不在中的中元素的集合。例如，如果，而，则，而空集。我们可以将两个集合和

12、之间的距离定义为，其中是一个函数，它返回集合元素的个数。该距离测度是大于或等于零的整数值，但不满足非负性的第二部分，也不满足对称性，同时还不满足三角不等式。然而，如果将相异度修改为，则这些性质都可以成立。例非度量的相异度：时间。这里给出一个更常见的例子，其中相异性测度并非度量，但依然是有用的。定义时间之间的距离测度如下：例如，小时，而小时。这种定义是有意义的，例如，在回答如下问题时就体现了这种定义的意义：如果一个事件在每天下午1点发生，现在是下午2点，那么我们还需要等待多长时间才能等到该事件再度发生？4）数据对象之间的相似度对于相似度，三角不等式（或类似的性质）通常不成立，但是对称性和非负性通

13、常成立。更明确地说，如果是数据点和之间的相似度，则相似度具有如下典型性质。仅当时。（WW）对于所有和，。（对称性）对于相似度，没有与三角不等式对应的一般性质。然而，有时可以将相似度简单地变换成一种度量距离。稍后讨论的余弦相似性度量和相似性度量就是两个例子。此外，对于特定的相似性度量，还可能在两个对象相似性上导出本质上与三角不等式类似的数学约束。例非对称相似性度量。考虑一个实验，实验中要求人们对屏幕上快速闪过的一小组字符进行分类。该实验的混淆矩阵（）记录每个字符被分类为自己的次数和被分类为另一个字符的次数。例如，假定0出现了次，它被分类为次，而被分类为次。类似地，出现次并且分类为次，但是分类为只

14、有次。如果取这些计数作为两个字符之间相似性的度量，则得到一种相似性度量，但这种相似性度量不是对称的。在这种情况下，通过选取，相似性度量可以转换成对称的，其中是新的相似性度量。邻近性度量的例子本节给出一些相似性和相异性度量的具体例子。1.二元数据的相似性度量两个仅包含二元属性的对象之间的相似性度量也称为相似系数（）,并且通常在和之间取值，值为表明两个对象完全相似，而值为0表明对象一点也不相似。有许多理由表明在特定情形下，一种系数为何比另一种好。设和是两个对象，都由个二元属性组成。这样的两个对象（即两个元向量）的比较可生成如下四个量（频率）：取并且取0的属性个数取并且取0的属性个数01取=并且取1

15、的属性个数10取=并且取0的属性个数11取=并且取1的属性个数简单匹配系数（）一种常用的相似性系数是简单匹配系数，定义如下：该度量对出现和不出现都进行计数。因此，可以在一个仅包含是非题的测验中用来发现回答问题相似的学生。系数（）假定和是两个数据对象，代表一个事务矩阵的两行（两个事务）。如果每个非对称的二元属性对应于商店的一种商品，则1表示该商品被购买，而0表示该商品未被购买。由于未被顾客购买的商品数远大于被其购买的商品数，因而像这样的相似性度量将会判定所有的事务都是类似的。这样，常常使用系数来处理仅包含非对称的二元属性的对象。系数通常用符号表示，由如下等式定义：例和相似性系数。为了解释这两种相

16、似性度量之间的差别，我们对如下二元向量计算和：例和相似性系数。为了解释这两种相似性度量之间的差别，我们对如下二元向量计算和：取并且取的属性个数如图所示，余弦相似度实际上是和之间夹角（余弦）的度量。这如图所示，余弦相似度实际上是和之间夹角（余弦）的度量。这取并且取的属性个数取并且取的属性个数通常，文档用向量表示，向量的每个属性代表一个特定的词（术语）在文档中出现的频率。当然，实际情况要复杂得多，因为需要忽略常用词，并使用各种技术处理同一个词的不同形式、不同的文档长度以及不同的词频。尽管文档具有数以百千计或数以万计的属性（词），但是每个文档向量都是稀疏的，因为它具有相对较少的非零属性值。（文档规范

17、化并不对零词目创建非零词目，即文档规范化保持稀疏性。）这样，与事务数据一样，相似性不能依赖共享0的个数，因为任意两个文档多半都不会包含许多相同的词，从而如果统计0-匹0配，则大多数文档都与其他大部分文档非常类似。因此，文档的相似性度量不仅应当像度量一样需要忽略匹配，而且还必须能够处理非二元向量。下面定义的余弦相似度（）就是文档相似性最常用的度量之一。如果和是两个文档向量，则其中，表示向量点积，即：II葢II是向量灭的长度，|x|=J工;=疋=。例5两个文档向量的余弦相似度。该例计算下面两个数据对象的余弦相似如图所示，余弦相似度实际上是和之间夹角（余弦）的度量。这如图所示，余弦相似度实际上是和之

18、间夹角（余弦）的度量。这样，如果余弦相似度为1则和之间夹角为，并且除大小（长度）之外，和是相同的；如果余弦相似度为样，如果余弦相似度为1则和之间夹角为，并且除大小（长度）之外，和是相同的；如果余弦相似度为0则和之间夹角为，并且它们不包含任何相同的词（术语）。图余弦度量的几何解释公式（）可以写成公式（）的形式：其中，而和被它们的长度除，将它们其中，而和被它们的长度除，将它们规范化成具有长度1。这意味在计算相似度时，余弦相似度不考虑两个数据对象的量值。（当量值是重要的时，欧几里得距离可能是一种更好的选择。）对于长度为1的向量，余弦度量可以通过简单地取点积计算。从而，在需要计算大量对象之间的余弦相似

19、度时，将对象规范化，使之具有单位长度可以减少计算时间。广义系数（系数）广义系数可以用于文档数据，并在二元属性情况下归约为系数。广义系数又称系数。（然而，还有一种系数也称系数。）该系数用表示，由下式定义：相关性两个具有二元变量或连续变量的数据对象之间的相关性是对象属性之间线性联系的度量。（更一般属性之间的相关性计算可以类似地定义。）更准确地，两个数据对象和之间的皮尔森相关（）系数由下式定义：具有完全正（负）线性关系，即，其中和是常数。下面两个和的值集分别给出相关度为和的情况。为简单起见，第一组中取和的均值为0例7非线性关系。如果相关度为0，则两个数据对象的属性之间不存在线性关系。然而，仍然可能存

20、在非线性关系。在下面的例子中，数据对象的属性之间存在非线性关系，但是它们的相关度为0例相关性可视化。通过绘制对应属性值对可以很容易地判定两个数据对象和之间的相关性。图给出了一些这种图，和具有个属性，这些属性的值随机地产生（服从正态分布），使得和的相关度从到1图中每个小圆圈代表个属性中的一个，其坐标是的一个属性的值，而其坐标是的相同属性的值。关度可以通过求点积来计算。注意，这与其他情况下使用的标准化不同，在其他情况下，我们使用变换和1i散度。本节，我们简略介绍散度（ge它是一族具有共同性质的邻近函数。这样，可以构造使用发散函数的一般数据挖掘算法，如聚类算法，具体的例子是均值聚类算法。注意，本节需

21、要向量计算方面的知识。散度是损失或失真函数。为了理解损失函数，考虑如下情况：设和是两个点，其中是原来的点，而是它的某个失真或近似，例如，可能是由于添加了一些随机噪声到上而产生的。损失函数的目的是度量用近似导致的失真或损失。当然，和越类似，失真或损失就越小，因而散度可以用作相异性函数。有如下正式定义。定义：散度给定一个严格凸函数（连同一些通常满足的适度限制），由该函数生成的散度（损失函数）通过下面的公式给出：例我们使用平方欧几里得距离给出散度的一个具体例子。为了简化数学计算，我们仅限于一维。设和是实数，而0是实数值函数，炉=。在此情况下，梯度归结为导数，而点积归结为乘积。例如，公式（2-1）2变

22、成公式（2-1）3。该例的图形在图中给出，其中=在和上给出了散度。6）邻近度计算问题本节讨论与邻近性度量有关的一些重要问题：（1当）属性具有不同的尺度（a或相关时如何处理；当对象包含不同类型的属性（例如，定量属性和定性属性）时如何计算对象之间的邻近度；（3当）属性具有不同的权重（即并非所有的属性都对对象的邻近度具有相等的贡献）时，如何处理邻近度计算。1.距离度量的标准化和相关性距离度量的一个重要问题是当属性具有不同的值域时如何处理。（这种情况通常称作变量具有不同的尺度。）前面，使用欧几里得距离，基于年龄和收入两个属性来度量人之间的距离。除非这两个属性是标准化的，否则两个人之间的距离将被收入所左

23、右。一个相关的问题是，除值域不同外，当某些属性之间还相关时，如何计算距离。当属性相关、具有不同的值域（不同的方差）、并且数据分布近似于高斯（正态）分布时，欧几里得距离的拓广，距离是有用的。具体地说，两个对象（向量）和之间的距离定义为：其中卫二是数据协方差矩阵的逆。注意，协方差矩阵卫是这样的矩阵，它的第个元素是第个和第个属性的协方差，由公式（1定义。例在图中有个点，其属性和属性的相关度为.在椭圆长轴两端的两个大点之间的欧几里得距离为，但距离仅为。实践中，计算距离的费用昂贵，但是对于其属性相关的对象来说是值得的。如果属性相对来说不相关，只是具有不同的值域，则只需要对变量组合异种属性的相似度前面的相

24、似度定义所基于的方法都假定所有属性具有相同类型。当属性具有不同类型时，就需要更一般的方法。直截了当的方法是使用表2-分7别计算出每个属性之间的相似度，然后使用一种导致0和1之间相似度的方法组合这些相似度。总相似度一般定义为所有属性相似度的平均值。不幸的是，如果某些属性是非对称属性，这种方法效果不好。例如，如果所有的属性都是非对称的二元属性，则相似性度量先归结为简单匹配系数-一-种对于二元非对称属性并不合适的度量。处理该问题的最简单方法是：如果两个对象在非对称属性上的值都是0，则在计算对象相似度时忽略它们。类似的方法也能很好地处理遗漏值。概括地说，算法可以有效地计算具有不同类型属性的两个对象和在前面的大部分讨论中，所有的属性在计算邻近度时都会被同等对待。但是，当某些属性对邻近度的定义比其他属性更重要时，我们并不希望这种同等对待的方式。为了处理这种情况，可以通过对每个属性的贡献加权来修改邻近度公式。如果权耳心的和为1则公式（）变成闵可夫斯基距离的定义也可以修改为：）选取正确的邻近性度量下面是一些一般观察，可能会对你有所帮助。首先，邻近性度量的类型应当与数据类型相适应。对于许多稠密的、连续的数据，通常使用距离度量，如欧几里得距离等。连续属性之间的邻近度通常用属性值的差