相似性与差异性的度量.docx

相似性与差异性的度量（Measures of Similarity and Dissimilarity）很多数据挖掘技术都用到了相似性与差异性，如聚类（clustering） ，最近邻分类（nearest neighbor classification） ，异常侦测（anomaly detection）等很多情况下，初始数据集并不需要立刻进行相似性或者差异性度量这些方法可以看作是将数据转换到相似性（差异性）空间中再分析首先，我们讨论一些基础的内容：对相似性和差异性在高层次的定义，并探讨一下它们的关系为了方便，相近性（proximity ）既用来代替相似性也代替差异性由于两个对象之间相近性是指这两个对象的相关属性在功能上（或者函数上，原文是 a function of the proximity）相近性，我们首先描述一下如何度量对象之间的一个属性的相近性，然后考虑对象之间多属性的相近性测量这里的测量包括关联关系（correlation）和欧几里得距离（Euclidean distance） ，它们对密集型数据如时间序列（ time series）或者二维点（two dimensional points）等很有用，而 Jaccard 和余弦相似性（cosine similarity）度量则对稀疏性数据，如文档等很有用。

基础部分（Basic）定义（Definitions）非正式的，两个对象之间的相似性是指两个对象之间在数值上有多大的相似程度（the similarity between two objects is a numerical measure of the degree to which the two objects are alike） 因此，相似性越高，对象之间越相像相似性通常是非负的，介于 0（没有相似性）到 1（完全相似）之间差异性则指两个对象在数值上的差异程度差异性越低，两个对象越相像通常，用距离（distance）代替差异性，距离通常表示类别之间的差异性差异性有时在区间[0,1]之间，有时也在 0 到 之间∞转换（Transformations）转换通常是把相似性转变成差异性，或者反过来也一样，也可能是把相近性度量转变成一个特定的区间中，如[0,1]举个例子，我们有个范围在 1 到 10 的相似性，但是某个特定的算法或者软件包要求使用差异性，或者相似性只能在区间[0,1]之间这些问题后面要使用到，且相对独立于其他细节通常情况下，相近性度量，尤其是相似性度量，定义或者转换的区间都在[0,1]之间。

这样转换通常都比较直接如两个对象之间的相似性在 1（没有相似性）到 10（完全相似）之间，我们可以通过转换公式 将该区间转换成 0 到 1 之间，其中 s 和 s’分别表示原来的相似性的𝑠'=(𝑠‒1)/9值和新的相似性的值一般的，相似性转换成[0,1]区间可以使用下面的公式：𝑠'=(𝑠‒𝑚𝑖𝑛⁡_𝑠)/(𝑚𝑎𝑥⁡_𝑠‒𝑚𝑖𝑛⁡_𝑠)其中， 和 分别表示相似性值的最大值和最小值𝑚𝑎𝑥_𝑠𝑚𝑖𝑛⁡_𝑠同样的，差异性转换成[0,1]区间可以使用下面的公式：𝑑'=(𝑑‒𝑚𝑖𝑛⁡_𝑑)/(𝑚𝑎𝑥⁡_𝑑‒𝑚𝑖𝑛⁡_𝑑)但是这样的变换也会带来很多的新问题有很多种方法可以将相近性区间映射到[0.1]之间如果原来的相近性值在[0, ,]之间，则需要一个非线性的变换方法，值之间的关系 ∞也在转换中也会变得不同如用转换公式 d’=d/(1+d)来变换差异性范围在 0 到 之间的∞值差异性：0, 0.5, 2, 10, 100，和 1000 将变成 0， 0.33， 0.67， 0.9， 0.99， 和 0.999原来差异性较大的值转变成接近 1 的结果，当然，这是否满足期望与应用本身有关。

另外一个新问题是相近性测量结果的意义有了变化如相关关系的区间[-1,1]通过取绝对值的方式映射到[0,1]会丢掉符号的信息，这在某些应用中非常重要将相似性转变成差异性或者反过来也是相对直接的转换当然，这里也会遇到改变数值意义或者线性尺度变为非线性尺度等问题[0,1]区间的相似性转变成差异性可以通过d=1-s 得到或者直接在数值上加上负号等方法加负号的转变方法并不局限于[0,1]之间，如果有类似的区间限制可以采用如下转换等：, , 𝑠=1𝑑+1𝑠=𝑒‒𝑑𝑠=1‒ 𝑑‒𝑚𝑖𝑛⁡_𝑑𝑚𝑎𝑥⁡_𝑑‒𝑚𝑖𝑛⁡_𝑑一般的，任何的单调减函数都可以用来将差异性转变成相似性，或者反过来也一样转变的时候其它因素也要考虑，包括保留意义（preserving meaning） ，尺度变换（distortion of scale） ，数据工具分析的需要（ requirements of data analysis tools）等等简单属性的相似性和差异性（Similarity and Dissimilarity between Simple Attributes）具有多个属性的对象之间的相近性通常是由单个属性相近性联合产生的。

因此，我们首先讨论对象单个属性的相近性考虑一下，如果一个对象由一个属性描述，那么两个对象是是相似的，这句话是什么意思呢？由于分类的属性只传达对象之间的差异，我们所能说的只能是它们拥有同样的值或者不是因此，这种情况下，如果属性值是匹配的我们定义它们的相似度为 1，否则为 0而差异性的定义则刚好相反如果对象的属性是顺序的，则稍微复杂一点，因为要考虑到顺序问题举个例子来说，度量某个产品的质量，如糖勺，质量范围有{poor, fair, OK, good, wonderful}正常情况下，我们认为质量是 wonderful 的产品 P1 与质量是 good 的产品 P2 之间的相似性要高于前者与质量是 OK 的产品 P3 之间的相似性为了使这样的观察量化，通常将顺序的属性映射成连续的整数，一般从 0 或者 1 开始，如上面的可以转换成{poor=0, fair=1, OK=2, good=3, wonderful=4}那么，d(P1,P2)=3-2=1 或者，如果我们希望差异性区间落在 0 到 1 之间可以使用 d(P1,P2)=(3-2)/4=0.25相对的相似性可以定义成 s=1-d但是这里的内容（即等区间的假设）可能会让读者有点困惑（uneasy） 。

值 fair 和good 之间的差别与 OK 和 wonderful 之间的差别是否一样？也许不一样，但是实际中，我们可操作是受到限制的，在缺乏更多信息的情况下，这是标准的处理顺序属性的方法Attribute Type Dissimilarity SimilarityNominal0 if x=yd= 1 if x≠y1 if x=ys=0 if x≠yOrdinald=|x-y|/(n-1)(values mapped to integers 0 to n-1,where n is the number of values) s=1-dInterval or Ratio d=|x-y|s=-d, s= , s=11+𝑑, s=1-𝑒‒𝑑𝑑‒𝑚𝑖𝑛⁡_𝑑𝑚𝑎𝑥_𝑑‒𝑚𝑖𝑛⁡_𝑑数据对象之间的差异性（Dissimilarities between Data Objects）在这部分内容中，我们将讨论各种差异性的度量我们从距离（distance）开始讨论，这是某些属性的差异性，并提供一般差异性的例子距离（Distance ）我们首先会就所有的距离的共同属性给出关于距离的正式的描述。

在一维、二维、三维甚至更高维空间中的欧几里得距离（Euclidean distance） ，d ，主要是下列相似性的公式：𝑑(𝑥,𝑦)= 𝑛∑𝑘=1(𝑥𝑘‒𝑦𝑘)2其中 n 是维数， 和 分别是 x 与 y 的第 k 个属性𝑥𝑘𝑦𝑘欧几里得距离是来自闵可夫斯基（Minkowski）距离公式（就是通常所说的闵氏距离）：𝑑(𝑥,𝑦)=( 𝑛∑𝑘=1|𝑥𝑘‒𝑦𝑘|𝑟)1/𝑟其中 r 是参数，下面描述三种最常见的闵氏距离的例子：r=1，城市街区距离（也叫曼哈顿距离，City block distance, Manhattan distance） ，典型的例子是汉明距离（Hamming distance） 是指仅有二进制属性的两个对象之间不同字节的数量，即二进制向量r=2，欧几里得距离r= ，上确界距离（supremum distance） 这是对象之间任意属性的最大的距离∞更正式的距离定义如下：𝑑(𝑥,𝑦)=lim𝑟→∞( 𝑛∑𝑘=1|𝑥𝑘‒𝑦𝑘|𝑟)1/𝑟这里的参数 r 不能与维数 n 混淆这里所说的几种距离在一维、二维、三维等更高维空间中都存在。

距离，比如欧几里得距离满足一些性质1、正向性（a） ，对所有的 x 与 y 均成立；𝑑(𝑥,𝑥)≥0（b） ，当且仅当 x=y 时成立；𝑑(𝑥,𝑦)=02、对称性，对所有的 x 与 y 均成立𝑑(𝑥,𝑦)=𝑑(𝑦,𝑥)3、三角不等式，对所有的 x、y 与 z 均成立𝑑(𝑥,𝑧)≤𝑑(𝑥,𝑦)+𝑑(𝑦,𝑧)满足以上三种特征的测量方式（Measures ）即为矩阵有些人只使用词的距离（term distance）度量差异性以满足这三个特性，但这通常都不行（violated ） 这里描述的三个特性都非常有用，在数学上也是同样的，如果三角不等式成立的话，这个特性可以用来提高那些依靠该特性的距离处理的技术（包括聚类等）的效率然而，很多差异性并不满足这些矩阵的特征下面给出两个例子例 2.14（非矩阵的差异性：集合差异） 这个概念是基于两个集合的差异性，类似集合理论中的定义考虑两个集合 A 和 B，A-B 是 A 中包含但 B 中不包含的元素例如，如果 A={1,2,3,4}和 B={2,3,4}，那么 A-B={1}，B-A=∅，即空集我们可以定义 d(A,B)=size(A-B)，其中 size 是指一个函数，可以返回集合中元素的数量。

这个度量距离是一个整数，大于或者等于 0但是它不满足对称性和三角不等式但是这些特征可以通过修改差异性得到：d(A,B)=size(A-B)+ size(B-A)例 2.15 （非矩阵的差异性：时间） 这个例子给出一个更常见的距离度量的例子，但不是矩阵，它仍然很有用定义每天的时间距离如下：𝑑(𝑡1,𝑡2)={𝑡2‒𝑡1 𝑡1≤𝑡224+(𝑡2‒𝑡1) 𝑡1≥𝑡2说明一下，d(1PM,2PM)=1 hour，然而，d(2PM,1PM)=23 hours这个定义通常可以用来回答“如果有件事在每天的 1 点发生，现在是 2 点，我还要等多长才能再次等到它发生 ”数据对象之间的相似性（Similarities between Data Object）对于相似性，三角不等式的性质通常都不满足，但是对称性和正向性通常满足为了说清楚，如果，s(x,y)是点 x 与 y 的相似性，相似性的性质如下：1、s(x,y)=1 当且仅当 x=y （0 ）≤𝑠≤12、s(x,y)= s(y,x)对于所有的 x 与 y 来说对于相似性度量的三角不等式性质没有一般的模拟方法。

但是相似性测量通常很容易转换成矩阵距离余弦与 Jaccard 相似性度量就是两个例子同样的，对于特定的相似性度量，它可能来自于数学上的两个对象之间的相似性，在三角不等式上有相似的情况相近性测量的例子（Examples of Proximity Mea。