2.1.2 数据相似性度量
一般而言,定义一个距离函数d（x,y）,需要满足下面几个准则:
①d（x,x）=0表示到自己的距离为0。
②d（x,y）≥0表示距离非负。
③d（x,y）=d(y,x)表示对称性:如果A到B距离是a,那么B到A的距离也应该是a。
④d（x,k）+d（k,y）≥d(x,y)表示三角形法则(两边之和大于第三边)。
数据相似性度量常用的度量方法如下所示:
(1)闵可夫斯基距离
闵可夫斯基距离是欧氏空间中的一种测度,被看作欧氏距离和曼哈顿距离的一种推广。其计算公式如下:
其中,p是一个可变参数。当p=1时,就是曼哈顿距离;当p=2时,就是欧氏距离;当p→∞时,就是切比雪夫距离。
闵可夫斯基距离比较直观,但是它与数据的分布无关,具有一定的局限性。闵氏距离的缺点主要有两个:
①将各个分量的量纲(scale)进行相同的看待;
②没有考虑各个分量的分布。
(2)欧氏距离
在数学中,欧几里得距离或欧几里得度量是欧几里得空间中两点间“普通”(即直线)距离。使用这个距离,欧氏空间成为度量空间。相关联的范数称为欧几里得范数。较早的文献称之为毕达哥拉斯度量。
欧氏距离在二维空间下的计算公式:
欧氏距离在n维空间下的计算公式:
欧氏距离在二维空间及n维空间下的计算公式如上所示。欧氏距离变换在数字图像处理中的应用范围很广泛,尤其对于图像的骨架提取,是一个很好的参照。
(3)曼哈顿距离
曼哈顿距离(Manhattan distance)或出租车几何是由19世纪的赫尔曼·闵可夫斯基所创词汇,是一种在几何度量空间使用的几何学用语,用以标明两个点在标准坐标系上的绝对轴距总和。
如图2.1所示,图中代表曼哈顿距离,代表欧氏距离,也就是直线距离,而
和代表等价的曼哈顿距离。曼哈顿距离——两点在南北方向上的距离加上在东西方向上的距离。对于一个具有正南正北、正东正西方向规则布局的城镇街道,从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离,因此,曼哈顿距离又称为出租车距离。曼哈顿距离不是距离不变量,当坐标轴变动时,点间的距离就会不同。在早期的计算机图形学中,屏幕是由像素构成的,是整数,点的坐标一般也是整数,原因是浮点运算很慢而且有误差。如果直接使用AB的欧氏距离(欧几里得距离:在二维和三维空间中的欧氏距离就是两点之间的距离),则必须要进行浮点运算,如果使用AC和CB,则只要计算加减法即可,这就大大提高了运算速度,而且不管累计运算多少次,都不会有误差。
图2.1 曼哈顿距离示意图
不同距离介绍
(4)切比雪夫距离
在数学中,切比雪夫距离(或是L∞度量)是向量空间中的一种度量,两个点之间的距离定义是其各坐标数值差绝对值的最大值。以数学的观点来看,切比雪夫距离是由一致范数(uniform norm)(或称为上确界范数)所衍生的度量,也是超凸度量(injective metric space)的一种。
在二维空间下,和一点的曼哈顿距离L 1为定值r的点会形成一个正方形,而且正方形的边和坐标轴会有π/4(45°)的夹角,因此平面的切比雪夫距离可以视为平面曼哈顿距离旋转再放大后的结果。
(5)海明距离(https://www.daowen.com)
在信息编码中,两个合法代码对应位上编码不同的位数称为码距,又称海明距离。举例如下:10101和00110从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。一个有效编码集中,任意两个码字的海明距离的最小值称为该编码集的海明距离。
海明距离的几何意义如下:
n位的码字可以用n维空间的超立方体的一个顶点来表示。两个码字之间的海明距离就是超立方体两个顶点之间的一条边,而且是这两个顶点之间的最短距离。
海明距离用于编码的检错和纠错。为了检测d个错误,需要一个海明距离为d+1的编码方案。因为在这样的编码方案中,d个1位错误不可能将一个有效码字改编成另一个有效码字。当接收方看到一个无效码字的时候,它就知道已经发生了传输错误。类似地,为了纠正d个错误,需要一个距离为2d+1的编码方案,因为在这样的编码方案中,合法码字之间的距离足够远,因而即使发生了d位变化,则还是原来的码字离它最近,从而可以确定原来的码字,达到纠错的目的。
(6)夹角余弦
夹角余弦通过计算两个向量的夹角余弦值来评估相似度。余弦相似度将向量根据坐标值,绘制到向量空间中,如最常见的二维空间。
余弦相似性通过测量两个向量的夹角的余弦值来度量它们之间的相似性。0度角的余弦值是1,而其他任何角度的余弦值都不大于1;并且其最小值是-1。从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向。两个向量有相同的指向时,余弦相似度的值为1;两个向量夹角为90°时,余弦相似度的值为0;两个向量指向完全相反的方向时,余弦相似度的值为-1。此结果与向量的长度无关,仅与向量的指向方向相关。余弦相似度通常用于正空间,因此给出的值为0到1之间。
夹角余弦的上下界对任何维度的向量空间都适用,而且余弦相似性最常用于高维正空间。例如,在信息检索中,每个词项被赋予不同的维度,而一个维度由一个向量表示,其各个维度上的值对应于该词项在文档中出现的频率。余弦相似度因此可以给出两篇文档在其主题方面的相似度。
另外,它通常用于文本挖掘中的文件比较。此外,在数据挖掘领域中,会用它来度量集群内部的凝聚力。
两个向量间的余弦值可以通过使用欧几里得点积公式求出,如下式所示:
给定属性向量A和B,其余弦相似性θ由点积和向量长度给出,余弦距离计算公式如下所示:
给出的相似性范围从-1到1:-1表示两个向量指向的方向正好截然相反,1表示它们的指向是完全相同的,0表示它们之间是独立的,而在这之间的值则表示中间的相似性或相异性。
对于文本匹配,属性向量A和B通常是文档中的词频向量。余弦相似性,可以被看作是在比较过程中把文件长度正规化的方法。在信息检索的情况下,由于一个词的频率(TF-IDF权)不能为负数,所以这两个文档的余弦相似性范围从0到1。并且,两个词的频率向量之间的角度不能大于90°。
(7)信息熵
信息是物质、能量、信息及其属性的标示,也是事物现象及其属性标识的集合。熵的概念源自热物理学。假定有两种气体a、b,当两种气体完全混合时,可以达到热物理学中的稳定状态,此时熵最高。如果要实现反向过程,即将a、b完全分离,在封闭的系统中是没有可能的。只有外部干预(信息),也即系统外部加入某种有序化的东西(能量),使得a、b分离。这时,系统进入另一种稳定状态,此时,信息熵最低。热物理学证明,在一个封闭的系统中,熵总是增大,直至最大。若要使系统的熵减少(使系统更加有序化),则必须有外部能量的干预。
1948年,香农提出了“信息熵”的概念,解决了对信息的量化度量问题。信息熵这个词是C.E.香农从热力学中借用过来的。热力学中的热熵是表示分子状态混乱程度的物理量。香农用信息熵的概念来描述信源的不确定度。
信息熵的计算是非常复杂的。而具有多重前置条件的信息,更是几乎不能计算的。所以在现实世界中信息的价值大多是不能被计算出来的。但因为信息熵和热力学熵的紧密相关性,所以信息熵是可以在衰减的过程中被测定出来的。因此信息的价值是通过信息的传递体现出来的。在没有引入附加价值(负熵)的情况下,传播得越广、流传时间越长的信息越有价值。
通常,一个信源发送出什么符号是不确定的,衡量它可以根据其出现的概率来度量。概率大,出现机会多,不确定性小;反之不确定性就大。
不确定性函数f是概率P的减函数;两个独立符号所产生的不确定性应等于各自不确定性之和,即f（ P 1,P 2）=f（P 1）+f(P 2),这称为可加性。同时满足这两个条件的函数f是对数函数,如下所示:
在信源中,考虑的不是某一单个符号发生的不确定性,而是要考虑这个信源所有可能发生情况的平均不确定性。若信源符号有n种取值:U 1,U i,…,U n,对应概率为:P 1,Pi,…,Pn,且各种符号的出现彼此独立。这时,信源的平均不确定性应当为单个符号不确定性的统计平均值(E),可称为信息熵,如下所示:
式中,对数一般取2为底,单位为比特。但是,也可以取其他对数底,采用其他相应的单位,它们间可用换底公式换算。
最简单的单符号信源仅取0和1两个元素,即二元信源,其概率为P和Q=1-P。
离散信源的信息熵具有:
①非负性:即收到一个信源符号所获得的信息量应为正值,H(U)≥0。②对称性:即对称于P=0.5。
③确定性:H（1,0）=0,即P=0或P=1已是确定状态,所得信息量为零。
④极值性:因H(U)是P的上凸函数,且一阶导数在P=0.5时等于0,所以当P=0.5时,H(U)最大。
对连续信源,香农给出了形式上类似于离散信源的连续熵,虽然连续熵H c(U)仍具有可加性,但不具有信息的非负性,已不同于离散信源。H c(U)不代表连续信源的信息量。连续信源取值无限,信息量是无限大,而H c(U)是一个有限的相对值,又称相对熵。但是,在取两熵的差值为互信息时,它仍具有非负性。这与力学中势能的定义相仿。
