精华内容
下载资源
问答
  • 数学中的常见的距离公式

    万次阅读 2017-08-24 11:20:08
    数学中的常见的距离公式 转载自:点击打开链接 最近看到文章中对距离的衡量依据所针对的问题,针对所使用到的各种距离公式从网上搜罗如下 1. 欧氏距离,最常见的两点之间或多点之间的距离表示法,又称...

    数学中的常见的距离公式

    转载自:点击打开链接

    最近看到文章中对距离的衡量依据所针对的问题,针对所使用到的各种距离公式从网上搜罗如下

    • 1. 欧氏距离,最常见的两点之间或多点之间的距离表示法,又称之为欧几里得度量,它定义于欧几里得空间中,如点 x = (x1,...,xn) 和 y = (y1,...,yn) 之间的距离为:

    (1)二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离

    (2)三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离:

    (3)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的欧氏距离:

      也可以用表示成向量运算的形式:

    其上,二维平面上两点欧式距离,代码可以如下编写:

    1. //unixfy:计算欧氏距离  
    2. double euclideanDistance(const vector<double>& v1, const vector<double>& v2)  
    3. {  
    4.      assert(v1.size() == v2.size());  
    5.      double ret = 0.0;  
    6.      for (vector<double>::size_type i = 0; i != v1.size(); ++i)  
    7.      {  
    8.          ret += (v1[i] - v2[i]) * (v1[i] - v2[i]);  
    9.      }  
    10.      return sqrt(ret);  
    11.  }  

    • 2. 曼哈顿距离,我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离,也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上,坐标(x1, y1)的点P1与坐标(x2, y2)的点P2的曼哈顿距离为:,要注意的是,曼哈顿距离依赖座标系统的转度,而非系统在座标轴上的平移或映射。 

         通俗来讲,想象你在曼哈顿要从一个十字路口开车到另外一个十字路口,驾驶距离是两点间的直线距离吗?显然不是,除非你能穿越大楼。而实际驾驶距离就是这个“曼哈顿距离”,此即曼哈顿距离名称的来源, 同时,曼哈顿距离也称为城市街区距离(City Block distance)。

    (1)二维平面两点a(x1,y1)与b(x2,y2)间的曼哈顿距离 

    (2)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的曼哈顿距离 

                              

    • 3. 切比雪夫距离,若二个向量或二个点p 、and q,其座标分别为,则两者之间的切比雪夫距离定义如下:
        这也等于以下Lp度量的极值: ,因此切比雪夫距离也称为L∞度量。

        以数学的观点来看,切比雪夫距离是由一致范数(uniform norm)(或称为上确界范数)所衍生的度量,也是超凸度量(injective metric space)的一种。
        在平面几何中,若二点p及q的直角坐标系坐标为 ,则切比雪夫距离为:

        玩过国际象棋的朋友或许知道,国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步?。你会发现最少步数总是max( | x2-x1 | , | y2-y1 | ) 步 。有一种类似的一种距离度量方法叫切比雪夫距离。

    (1)二维平面两点a(x1,y1)与b(x2,y2)间的切比雪夫距离 

    (2)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的切比雪夫距离   

    这个公式的另一种等价形式是 

    • 4. 闵可夫斯基距离(Minkowski Distance),闵氏距离不是一种距离,而是一组距离的定义。
    (1) 闵氏距离的定义       
    两个n维变量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的闵可夫斯基距离定义为: 

    其中p是一个变参数。
    当p=1时,就是曼哈顿距离
    当p=2时,就是欧氏距离
    当p→∞时,就是切比雪夫距离       
    根据变参数的不同,闵氏距离可以表示一类的距离。 
    • 5. 标准化欧氏距离 (Standardized Euclidean distance ),标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。标准欧氏距离的思路:既然数据各维分量的分布不一样,那先将各个分量都“标准化”到均值、方差相等。至于均值和方差标准化到多少,先复习点统计学知识。

      假设样本集X的数学期望或均值(mean)为m,标准差(standard deviation,方差开根)为s,那么X的“标准化变量”X*表示为:(X-m)/s,而且标准化变量的数学期望为0,方差为1。
      即,样本集的标准化过程(standardization)用公式描述就是:
      标准化后的值 =  ( 标准化前的值  - 分量的均值 ) /分量的标准差  
      经过简单的推导就可以得到两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的标准化欧氏距离的公式:  
      如果将方差的倒数看成是一个权重,这个公式可以看成是一种加权欧氏距离(Weighted Euclidean distance)。 
    • 6. 马氏距离(Mahalanobis Distance)
      (1)马氏距离定义       
      有M个样本向量X1~Xm, 协方差矩阵记为S,均值记为向量μ,则其中样本向量X到u的马氏距离表示为: 
      协方差矩阵中每个元素是各个矢量元素之间的协方差Cov(X,Y),Cov(X,Y) = E{ [X-E(X)] [Y-E(Y)]},其中E为数学期望
      而其中向量Xi与Xj之间的马氏距离定义为:    
      若协方差矩阵是单位矩阵(各个样本向量之间独立同分布),则公式就成了:       
      也就是欧氏距离了。  
      若协方差矩阵是对角矩阵,公式变成了标准化欧氏距离。
      (2)马氏距离的优缺点:量纲无关,排除变量之间的相关性的干扰。 
      微博上的seafood高清版点评道:原来马氏距离是根据协方差矩阵演变,一直被老师误导了,怪不得看Killian在05年NIPS发表的LMNN论文时候老是看到协方差矩阵和半正定,原来是这回事
    • 7、巴氏距离(Bhattacharyya Distance),在统计中,Bhattacharyya距离测量两个离散或连续概率分布的相似性。它与衡量两个统计样品或种群之间的重叠量的Bhattacharyya系数密切相关。Bhattacharyya距离和Bhattacharyya系数以20世纪30年代曾在印度统计研究所工作的一个统计学家A. Bhattacharya命名。同时,Bhattacharyya系数可以被用来确定两个样本被认为相对接近的,它是用来测量中的类分类的可分离性。
    (1)巴氏距离的定义
    对于离散概率分布 p和q在同一域 X,它被定义为:
    其中:
    是Bhattacharyya系数。
    对于连续概率分布,Bhattacharyya系数被定义为:
    这两种情况下,巴氏距离 并没有服从三角不等式.(值得一提的是,Hellinger距离不服从三角不等式 )。 
    对于多变量的高斯分布 

    和是手段和协方差的分布
    需要注意的是,在这种情况下,第一项中的Bhattacharyya距离与马氏距离有关联。 
    (2)Bhattacharyya系数
    Bhattacharyya系数是两个统计样本之间的重叠量的近似测量,可以被用于确定被考虑的两个样本的相对接近。
    计算Bhattacharyya系数涉及集成的基本形式的两个样本的重叠的时间间隔的值的两个样本被分裂成一个选定的分区数,并且在每个分区中的每个样品的成员的数量,在下面的公式中使用
    考虑样品a 和 b ,n是的分区数,并且 被一个 和 b i的日分区中的样本数量的成员。更多介绍请参看: http://en.wikipedia.org/wiki/Bhattacharyya_coefficient
    • 8. 汉明距离(Hamming distance), 两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。例如字符串“1111”与“1001”之间的汉明距离为2。应用:信息编码(为了增强容错性,应使得编码间的最小汉明距离尽可能大)。
    或许,你还没明白我再说什么,不急,看下 上篇blog中第78题的第3小题整理的一道面试题目,便一目了然了。如下图所示:
    1. //动态规划:    
    2.     
    3. //f[i,j]表示s[0...i]与t[0...j]的最小编辑距离。    
    4. f[i,j] = min { f[i-1,j]+1,  f[i,j-1]+1,  f[i-1,j-1]+(s[i]==t[j]?0:1) }    
    5.     
    6. //分别表示:添加1个,删除1个,替换1个(相同就不用替换)。   
        与此同时, 面试官还可以继续问下去:那么,请问,如何设计一个比较两篇文章相似性的算法?( 这个问题的讨论可以看看这里: http://t.cn/zl82CAH,及这里关于simhash算法的介绍: http://www.cnblogs.com/linecong/archive/2010/08/28/simhash.html ),接下来,便引出了下文关于夹角余弦的讨论。
    上篇blog中第78题的第3小题给出了多种方法,读者可以参看之。同时,程序员编程艺术系列第二十八章将详细阐述这个问题)
    • 9. 夹角余弦(Cosine) 几何中夹角余弦可用来衡量两个向量方向的差异,机器学习中借用这一概念来衡量样本向量之间的差异。

    (1)在二维空间中向量A(x1,y1)与向量B(x2,y2)的夹角余弦公式:

    (2) 两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夹角余弦

           

    类似的,对于两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n),可以使用类似于夹角余弦的概念来衡量它们间的相似程度,即:       

    夹角余弦取值范围为[-1,1]。夹角余弦越大表示两个向量的夹角越小,夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值1,当两个向量的方向完全相反夹角余弦取最小值-1。 

    • 10. 杰卡德相似系数(Jaccard similarity coefficient)
    (1) 杰卡德相似系数       
    两个集合A和B的交集元素在A,B的并集中所占的比例,称为两个集合的杰卡德相似系数,用符号J(A,B)表示。 
     
    杰卡德相似系数是衡量两个集合的相似度一种指标。
    (2) 杰卡德距离       
    与杰卡德相似系数相反的概念是杰卡德距离(Jaccard distance)。
    杰卡德距离可用如下公式表示:  
    杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。
    (3) 杰卡德相似系数与杰卡德距离的应用      
    可将杰卡德相似系数用在衡量样本的相似度上。
    举例:样本A与样本B是两个n维向量,而且所有维度的取值都是0或1,例如:A(0111)和B(1011)。我们将样本看成是一个集合,1表示集合包含该元素,0表示集合不包含该元素。
    M 11 :样本A与B都是1的维度的个数
    M0 1:样本A是0,样本B是1的维度的个数
    M10:样本A是1,样本B是0 的维度的个数
    M 00:样本A与B都是0的维度的个数
    依据上文给的杰卡德相似系数及杰卡德距离的相关定义,样本A与B的杰卡德相似系数J可以表示为:
    这里M 11+ M 01+ M 10可理解为A与B的并集的元素个数,而M 11是A与B的交集的元素个数。而样本A与B的杰卡德距离表示为J':

    • 11.皮尔逊系数(Pearson Correlation Coefficient)
        在具体阐述皮尔逊相关系数之前,有必要解释下什么是相关系数 ( Correlation coefficient )与相关距离(Correlation distance)。
        相关系数 ( Correlation coefficient )的定义是:
    ( 其中,E为数学期望或均值,D为方差,D开根号为标准差,E{ [X-E(X)] [Y-E(Y)]}称为随机变量X与Y的协方差,记为Cov(X,Y),即Cov(X,Y) = E{ [X-E(X)] [Y-E(Y)]},而两个变量之间的协方差和标准差的商则称为随机变量X与Y的相关系数,记为 )
       相关系数衡量随机变量X与Y相关程度的一种方法,相关系数的取值范围是[-1,1]。相关系数的绝对值越大,则表明X与Y相关度越高。当X与Y线性相关时,相关系数取值为1(正线性相关)或-1(负线性相关)。
        具体的,如果有两个变量:X、Y,最终计算出的相关系数的含义可以有如下理解:
    1. 当相关系数为0时,X和Y两变量无关系。
    2. 当X的值增大(减小),Y值增大(减小),两个变量为正相关,相关系数在0.00与1.00之间。
    3. 当X的值增大(减小),Y值减小(增大),两个变量为负相关,相关系数在-1.00与0.00之间。
       相关距离的定义是:

    OK,接下来,咱们来重点了解下皮尔逊相关系数。
        在统计学中,皮尔逊积矩相关系数(英语:Pearson product-moment correlation coefficient,又称作 PPMCC或PCCs, 用r表示)用于度量两个变量X和Y之间的相关(线性相关),其值介于-1与1之间。

    通常情况下通过以下取值范围判断变量的相关强度:
    相关系数     0.8-1.0     极强相关
                     0.6-0.8     强相关
                     0.4-0.6     中等程度相关
                     0.2-0.4     弱相关
                     0.0-0.2     极弱相关或无相关

    在自然科学领域中,该系数广泛用于度量两个变量之间的相关程度。它是由卡尔·皮尔逊从弗朗西斯·高尔顿在19世纪80年代提出的一个相似却又稍有不同的想法演变而来的。这个相关系数也称作“皮尔森相关系数r”。
    (1)皮尔逊系数的定义
    两个变量之间的皮尔逊相关系数定义为两个变量之间的协方差和标准差的商:
    以上方程定义了总体相关系数, 一般表示成希腊字母ρ(rho)。基于样本对协方差和方差进行估计,可以得到样本标准差, 一般表示成r:
    一种等价表达式的是表示成标准分的均值。基于(Xi, Yi)的样本点,样本皮尔逊系数是

                   其中  及  ,分别是标准分、样本平均值和样本标准差。

    或许上面的讲解令你头脑混乱不堪,没关系,我换一种方式讲解,如下:

    假设有两个变量X、Y,那么两变量间的皮尔逊相关系数可通过以下公式计算:

    • 公式一:
    注:勿忘了上面说过,“皮尔逊相关系数定义为两个变量之间的协方差和标准差的商”,其中标准差的计算公式为:
    • 公式二:
    • 公式三:
    • 公式四:

    以上列出的四个公式等价,其中E是数学期望,cov表示协方差,N表示变量取值的个数。

    (2)皮尔逊相关系数的适用范围
    当两个变量的标准差都不为零时,相关系数才有定义,皮尔逊相关系数适用于:
    1. 两个变量之间是线性关系,都是连续数据。
    2. 两个变量的总体是正态分布,或接近正态的单峰分布。
    3. 两个变量的观测值是成对的,每对观测值之间相互独立。
    (3)如何理解皮尔逊相关系数

    rubyist皮尔逊相关系数理解有两个角度

    其一, 按照高中数学水平来理解, 它很简单, 可以看做将两组数据首先做Z分数处理之后, 然后两组数据的乘积和除以样本数,Z分数一般代表正态分布中, 数据偏离中心点的距离.等于变量减掉平均数再除以标准差.(就是高考的标准分类似的处理)

    样本标准差则等于变量减掉平均数的平方和,再除以样本数,最后再开方,也就是说,方差开方即为标准差,样本标准差计算公式为:

    所以, 根据这个最朴素的理解,我们可以将公式依次精简为:

    其二, 按照大学的线性数学水平来理解, 它比较复杂一点,可以看做是两组数据的向量夹角的余弦。下面是关于此皮尔逊系数的几何学的解释,先来看一幅图,如下所示:


    回归直线: y=gx(x) [红色] 和 x=gy(y) [蓝色]

    如上图,对于没有中心化的数据, 相关系数与两条可能的回归线y=gx(x) 和 x=gy(y) 夹角的余弦值一致。
    对于没有中心化的数据 (也就是说, 数据移动一个样本平均值以使其均值为0), 相关系数也可以被视作由两个随机变量 向量 夹角 的 余弦值(见下方)。
    举个例子,例如,有5个国家的国民生产总值分别为 10, 20, 30, 50 和 80 亿美元。 假设这5个国家 (顺序相同) 的贫困百分比分别为 11%, 12%, 13%, 15%, and 18% 。 令 x 和 y 分别为包含上述5个数据的向量: x = (1, 2, 3, 5, 8) 和 y = (0.11, 0.12, 0.13, 0.15, 0.18)。
    利用通常的方法计算两个向量之间的夹角  (参见 数量积), 未中心化 的相关系数是:


    我们发现以上的数据特意选定为完全相关: y = 0.10 + 0.01 x。 于是,皮尔逊相关系数应该等于1。将数据中心化 (通过E(x) = 3.8移动 x 和通过 E(y) = 0.138 移动 y ) 得到 x = (−2.8, −1.8, −0.8, 1.2, 4.2) 和 y = (−0.028, −0.018, −0.008, 0.012, 0.042), 从中

    (4)皮尔逊相关的约束条件

    从以上解释, 也可以理解皮尔逊相关的约束条件:

    • 1 两个变量间有线性关系
    • 2 变量是连续变量
    • 3 变量均符合正态分布,且二元分布也符合正态分布
    • 4 两变量独立

    在实践统计中,一般只输出两个系数,一个是相关系数,也就是计算出来的相关系数大小,在-1到1之间;另一个是独立样本检验系数,用来检验样本一致性。

         简单说来,各种“距离”的应用场景简单概括为,空间:欧氏距离,路径:曼哈顿距离,国际象棋国王:切比雪夫距离,以上三种的统一形式:闵可夫斯基距离,加权:标准化欧氏距离,排除量纲和依存:马氏距离,向量差距:夹角余弦,编码差别:汉明距离,集合近似度:杰卡德类似系数与距离,相关:相关系数与相关距离。

    展开全文
  • 数学中几种常用的距离

    千次阅读 2016-03-24 11:01:30
    多种多样的距离在数学建模、计算机学习中有着不小的应用。比如,A*搜索时的评估函数。比如,机器学习中,做分类时常常需要估算不同样本之间的相似性度量(Similarity Measurement),这时通常采用的方法就是计算样本...

    数学中有很多不同种类的距离,常用于几何、高等代数等数学研究。

    多种多样的距离在数学建模、计算机学习中有着不小的应用。

    比如,A*搜索时的评估函数。

    比如,在机器学习中,做分类时常常需要估算不同样本之间的相似性度量(Similarity Measurement),这时通常采用的方法就是计算样本间的距离。采用什么样的方法计算距离是很讲究,甚至关系到分类的正确与否。

    欧氏距离(Euclidean Distance)

    欧氏距离是最易于理解的一种距离计算方法,源自欧几里得几何中两点间的距离公式。

    (1)二维平面上两点 a(x1,y1) b(x2,y2) 间的欧氏距离:

    这里写图片描述

    (2)两个n维向量 a(x11,x12,,x1n) b(x21,x22,,x2n) 间的欧氏距离:

    这里写图片描述

    也可以用表示成向量运算的形式:

    这里写图片描述

    (4)Matlab计算欧氏距离

    Matlab计算距离主要使用pdist函数。若 X 是一个M×N的矩阵,则pdist(X)将 X 矩阵M行的每一行作为一个 N 维向量,然后计算这M个向量两两间的距离。

    例子:计算向量 (0,0)(1,0)(0,2) 两两间的欧式距离

    X = [0 0 ; 1 0 ; 0 2]
    
    D = pdist(X,'euclidean') %大家可以去查一查pdist的参数
    
    结果:
    
    D =
    
        1.0000    2.0000    2.2361

    曼哈顿距离(Manhattan Distance)

    从名字就可以猜出这种距离的计算方法了。想象你在曼哈顿要从一个十字路口开车到另外一个十字路口,驾驶距离是两点间的直线距离吗?显然不是,除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源, 曼哈顿距离也称为城市街区距离(City Block distance)。

    (1)二维平面两点 a(x1,y1) b(x2,y2) 间的曼哈顿距离

    这里写图片描述

    (2)两个n维向量 a(x11,x12,,x1n) b(x21,x22,,x2n) 间的曼哈顿距离

    这里写图片描述

    (3) Matlab计算曼哈顿距离

    例子:计算向量 (0,0)(1,0)(0,2)(2,2) 两两间的曼哈顿距离

    X = [0 0 ; 1 0 ; 0 2 ; 2 2];
    
    D = pdist(X,'cityblock')
    
    结果:
    
    D =
    
         1     2     4     3     3     2
    

    切比雪夫距离 ( Chebyshev Distance )

    国际象棋玩过么?国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步?自己走走试试。你会发现最少步数总是max( | x2-x1 | , | y2-y1 | ) 步 。有一种类似的一种距离度量方法叫切比雪夫距离。

    (1)二维平面两点 a(x1,y1) b(x2,y2) 间的切比雪夫距离

    这里写图片描述

    (2)两个n维向量 a(x11,x12,,x1n) b(x21,x22,,x2n) 间的切比雪夫距离

    这里写图片描述

      这个公式的另一种等价形式是

    这里写图片描述

    看不出两个公式是等价的?提示一下:试试用放缩法和夹逼法则来证明。

    (3)Matlab计算切比雪夫距离

    例子:计算向量 (0,0)(1,0)(0,2) 两两间的切比雪夫距离

    X = [0 0 ; 1 0 ; 0 2]
    
    D = pdist(X, 'chebychev')
    
    结果:
    
    D =
    
         1     2     2

    闵可夫斯基距离(Minkowski Distance)

    闵氏距离不是一种距离,而是一组距离的定义,上文说的几个距离都是属于闵可夫斯基距离的。

    (1) 闵氏距离的定义

    两个n维变量 a(x11,x12,,x1n) b(x21,x22,,x2n) 间的闵可夫斯基距离定义为:

    这里写图片描述

    其中p是一个变参数。

    p=1 时,就是曼哈顿距离

    p=2 时,就是欧氏距离

    p 时,就是切比雪夫距离

    根据变参数的不同,闵氏距离可以表示一类的距离。

    (2)闵氏距离的缺点

    闵氏距离,包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。

    举个例子:
    二维样本(身高,体重),其中身高范围是 [150,190] ,体重范围是 [50,60] ,有三个样本: a(180,50) b(190,50) c(180,60)
    那么a与b之间的闵氏距离(无论是曼哈顿距离、欧氏距离或切比雪夫距离)等于a与c之间的闵氏距离,但是身高的 10cm 真的等价于体重的 10kg 么?因此用闵氏距离来衡量这些样本间的相似度很有问题。

    简单说来,闵氏距离的缺点主要有两个:
    (1)将各个分量的量纲(scale),也就是“单位”当作相同的看待了。
    (2)没有考虑各个分量的分布(期望,方差等)可能是不同的。

    (3)Matlab计算闵氏距离

    例子:计算向量 (0,0)(1,0)(0,2) 两两间的闵氏距离(以变参数为2的欧氏距离为例)

    X = [0 0 ; 1 0 ; 0 2]
    
    D = pdist(X,'minkowski',2)
    
    结果:
    
    D =
    
        1.0000    2.0000    2.2361

    标准化欧氏距离 (Standardized Euclidean distance )

    (1)标准欧氏距离的定义

    标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。

    标准欧氏距离的思路:既然数据各维分量的分布不一样,那先将各个分量都“标准化”到均值、方差相等。

    均值和方差标准化到多少呢?这里先复习点统计学知识吧,假设样本集 X 的均值(mean)为m,标准差(standard deviation)为 s ,那么X的“标准化变量”表示为:

    X=Xms

    标准化变量的数学期望为0,方差为1。因此样本集的标准化过程(standardization)用公式描述就是:

    标准化后的值 = ( 标准化前的值 - 分量的均值 ) /分量的标准差

    经过简单的推导就可以得到两个 n 维向量a(x11,x12,,x1n) b(x21,x22,,x2n) 间的标准化欧氏距离的公式:

    这里写图片描述

    如果将方差的倒数看成是一个权重,这个公式可以看成是一种加权欧氏距离(Weighted Euclidean distance)。

    (2)Matlab计算标准化欧氏距离

    例子:计算向量 (0,0)(1,0)(0,2) 两两间的标准化欧氏距离 (假设两个分量的标准差分别为0.5和1)

    X = [0 0 ; 1 0 ; 0 2]
    
    D = pdist(X, 'seuclidean',[0.5,1])
    
    结果:
    
    D =
    
        2.0000    2.0000    2.8284

    马氏距离(Mahalanobis Distance)

    (1)马氏距离定义

    M 个样本向量X1 Xm,协方差矩阵记为 S ,均值记为向量μ,则其中样本向量 X μ的马氏距离表示为:

    这里写图片描述

    而其中向量Xi与Xj之间的马氏距离定义为:

    这里写图片描述

    若协方差矩阵是单位矩阵(各个样本向量之间独立同分布),则公式就成了:

    这里写图片描述

    也就是欧氏距离了。

    若协方差矩阵是对角矩阵,公式变成了标准化欧氏距离。

    (2)马氏距离的优缺点:量纲无关,排除变量之间的相关性的干扰。

    (3) Matlab计算 (1,2)(1,3)(2,2)(3,1) 两两之间的马氏距离

    X = [1 2; 1 3; 2 2; 3 1]
    
    Y = pdist(X,'mahalanobis')
    
    
    
    结果:
    
    Y =
    
        2.3452    2.0000    2.3452    1.2247    2.4495    1.2247
    

    夹角余弦(Cosine)

    几何中夹角余弦可用来衡量两个向量方向的差异,机器学习中借用这一概念来衡量样本向量之间的差异。

    (1)在二维空间中向量 a(x1,y1) 与向量 b(x2,y2) 的夹角余弦公式:

    这里写图片描述

    (2) 两个n维样本点 a(x11,x12,,x1n) b(x21,x22,,x2n) 的夹角余弦:

    这里写图片描述

    类似的,对于两个n维样本点 a(x11,x12,,x1n) b(x21,x22,,x2n) ,可以使用类似于夹角余弦的概念来衡量它们间的相似程度。

      即:

    这里写图片描述

    夹角余弦取值范围为 [1,1] 。夹角余弦越大表示两个向量的夹角越小,夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值1,当两个向量的方向完全相反夹角余弦取最小值-1。

    (3)Matlab计算夹角余弦

    例子:计算 (1,0)(1,1.732)(1,0) 两两间的夹角余弦

    X = [1 0 ; 1 1.732 ; -1 0]
    
    D = 1- pdist(X, 'cosine')  % Matlab中的pdist(X, 'cosine')得到的是1减夹角余弦的值
    
    结果:
    
    D =
    
        0.5000   -1.0000   -0.5000
    

    汉明距离(Hamming distance)

    (1)汉明距离的定义

    两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。例如字符串“1111”与“1001”之间的汉明距离为2。

    应用:信息编码(为了增强容错性,应使得编码间的最小汉明距离尽可能大)。

    作为北邮的学生,这个算的就是比较多吧。

    (2)Matlab计算汉明距离

    Matlab中2个向量之间的汉明距离的定义为2个向量不同的分量所占的百分比。

    例子:计算向量 (0,0,0)(0,0,1)(0,1,0)(1,0,0)(0,1,1) 两两间的汉明距离

    X = [0 0 0 ; 0 0 1 ; 0 1 0 ; 1 0 0 ; 0 1 1];
    
    D = pdist(X,'hamming')
    
    结果:
    
    D =
    
        0.3333    0.3333    0.3333    0.6667    0.6667    0.6667    0.3333    0.6667    0.3333    1.0000
    

    杰卡德相似系数(Jaccard similarity coefficient)

    (1) 杰卡德相似系数

    两个集合A和B的交集元素在A,B的并集中所占的比例,称为两个集合的杰卡德相似系数,用符号J(A,B)表示。

    这里写图片描述

    杰卡德相似系数是衡量两个集合的相似度一种指标。

    (2) 杰卡德距离

    与杰卡德相似系数相反的概念是杰卡德距离(Jaccard distance)。杰卡德距离可用如下公式表示:

    这里写图片描述

      杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。

    (3) 杰卡德相似系数与杰卡德距离的应用

    可将杰卡德相似系数用在衡量样本的相似度上。

    样本A与样本B是两个n维向量,而且所有维度的取值都是0或1。例如:A(0111)和B(1011)。我们将样本看成是一个集合,1表示集合包含该元素,0表示集合不包含该元素。

    p :样本A与B都是1的维度的个数

    q :样本A是1,样本B是0的维度的个数

    r :样本A是0,样本B是1的维度的个数

    s :样本A与B都是0的维度的个数

    这里p+q+r可理解为A与B的并集的元素个数,而p是A与B的交集的元素个数。

    而样本A与B的杰卡德距离表示为:

    这里写图片描述

    (4)Matlab 计算杰卡德距离

    Matlab的pdist函数定义的杰卡德距离跟我这里的定义有一些差别,Matlab中将其定义为不同的维度的个数占“非全零维度”的比例。

    例子:计算 (1,1,0)(1,1,0)(1,1,0) 两两之间的杰卡德距离

    X = [1 1 0; 1 -1 0; -1 1 0]
    
    D = pdist( X , 'jaccard')
    
    结果
    
    D =
    
    0.5000    0.5000    1.0000

    相关系数 ( Correlation coefficient )与相关距离(Correlation distance)

    (1) 相关系数的定义

    这里写图片描述

    相关系数是衡量随机变量X与Y相关程度的一种方法,相关系数的取值范围是 [1,1] 。相关系数的绝对值越大,则表明X与Y相关度越高。当X与Y线性相关时,相关系数取值为1(正线性相关)或-1(负线性相关)。

    (2)相关距离的定义

    这里写图片描述

    (3)Matlab计算 (1,2,3,4) (3,8,7,6) 之间的相关系数与相关距离

    X = [1 2 3 4 ; 3 8 7 6]
    
    C = corrcoef( X' )   %将返回相关系数矩阵
    
    D = pdist( X , 'correlation')
    
    结果:
    
    C =
    
        1.0000    0.4781
    
        0.4781    1.0000
    
    D =
    
    0.5219
    
          其中0.4781就是相关系数,0.5219是相关距离。
    
    展开全文
  • 数学距离与相似度度量

    千次阅读 2013-12-10 21:43:05
    数学距离 1.1 一些性质  数学距离具有一些性质。如果d(p1, p2)是两个点p1和p2之间的距离,则如下性质成立:  (1)非负性  (a)对于所有的p1和p2,d(p1, p2)≥0,  (b)当且仅当p1=p2时,d(p1, p2)=0。  ...

    机器学习中的相似性度量【补充-向量表示形式】


    一  数学距离

    1.1   一些性质

          数学距离具有一些性质。如果d(p1, p2)是两个点p1和p2之间的距离,则如下性质成立:

          (1)非负性

                  (a)对于所有的p1和p2,d(p1, p2)≥0,

                  (b)当且仅当p1=p2时,d(p1, p2)=0。

           (2)对称性

                  对于所有的p1和p2,d(p1, p2)=d(p2, p1)。

           (3 )当且仅当p1与p2为同一个点时,距离为0。

            (4)三角不等式

                  对于所有的p1、p2和p3,d(p1, p3)≤d(p1, p2)+p(p2, p3)。

         1.2 常见距离

            1.2.1 欧氏距离Euclidean Distance欧几里得度量、欧几里得距离)

             二维空间的欧氏距离公式   d = sqrt( (x1-x2)^2+(y1-y2)^2 ) 

               三维空间的欧氏距离公式  d = sqrt( (x1-x2)^2+(y1-y2)^2+(z1-z2)^2 )
             N维空间的欧氏距离公式  d(A,B) =sqrt [ ∑( ( a[i] - b[i] )^2 ) ] (i = 1,2,…,n)

               N维欧氏空间是一个点集,它的每个点 X 可以表示为 (x[1],x[2],…,x[n]) ,其中 x[i] (i = 1,2,…,n) 是实数,称为 X 的第i个坐标,两个点 A = (a[1],a[2],…,a[n]) 和 B =  (b[1],b[2],…,b[n]) 之间的距离 d(A,B) 定义为上面的公式。

      因为计算是基于各维度特征的绝对数值,所以欧氏度量需要保证各维度指标在相同的刻度级别,比如对身高(cm)和体重(kg)两个单位不同的指标使用欧式距离可能使结果失效。

         1.2.2 明可夫斯基距离(Minkowski Distance)

              明氏距离是欧氏距离的推广,是对多个距离度量公式的概括性的表述。公式如下:



      这里的p值是一个变量,当p=2的时候就得到了上面的欧氏距离。

         1.2.3曼哈顿距离(Manhattan Distance)

      曼哈顿距离来源于城市区块距离,是将多个维度上的距离进行求和后的结果,即当上面的明氏距离中p=1时得到的距离度量公式,如下:



        1.2.4切比雪夫距离(Chebyshev Distance)

      切比雪夫距离起源于国际象棋中国王的走法,我们知道国际象棋国王每次只能往周围的8格中走一步,那么如果要从棋盘中A格(x1, y1)走到B格(x2, y2)最少需要走几步?扩展到多维空间,其实切比雪夫距离就是当p趋向于无穷大时的明氏距离:


      其实上面的曼哈顿距离、欧氏距离和切比雪夫距离都是明可夫斯基距离在特殊条件下的应用。

         

        1.2.5马哈拉诺比斯距离(Mahalanobis Distance)

      既然欧几里得距离无法忽略指标度量的差异,所以在使用欧氏距离之前需要对底层指标进行数据的标准化,而基于各指标维度进行标准化后再使用欧氏距离就衍生出来另外一个距离度量——马哈拉诺比斯距离(Mahalanobis Distance),简称马氏距离。

        1.2.6 Jaccard距离

         两个集合A和B的Jaccard 距离被定义为1-J(A, B),其中J(A, B)为Jaccard相似系数(Jaccard similarity coefficient or Jaccard index)

        

    二相似度度量

          相似度度量(Similarity),即计算个体间的相似程度,通常与距离度量相反,相似度度量的值越小,说明个体间相似度越小,差异越大。

    2.1 向量空间余弦相似度(Cosine Similarity)

      余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。相比距离度量,余弦相似度更加注重两个向量在方向上的差异,而非距离或长度上。公式如下:


    余弦相似度对绝对数值不敏感

    2.2皮尔森相关系数(Pearson Correlation Coefficient)

      即相关分析中的相关系数r,分别对X和Y基于自身总体标准化后计算空间向量的余弦夹角。公式如下:


    2.3 Jaccard相似系数(Jaccard Coefficient)

      Jaccard系数主要用于计算符号度量或布尔值度量的个体间的相似度,因为个体的特征属性都是由符号度量或者布尔值标识,因此无法衡量差异具体值的大小,只能获得“是否相同”这个结果,所以Jaccard系数只关心个体间共同具有的特征是否一致这个问题。如果比较X与Y的Jaccard相似系数,只比较xn和yn中相同的个数,两个集合Jaccard相似系数为两个集合的交集的元素个数除以两个集合并集的元素个数,公式如下:

    2.4  广义Jaccard系数(又叫Tanimoto系数)

        (但还有一种系数也叫Tanimoto系数,这里就不用了)

    可用于文档数据,在二元属性情况下规约为Jaccard系数,用EJ表示:

    至于所谓的二元属性下规约为Jaccard系数举个例子就知道了:

    x = (1, 1, 0, 0, 1), y = (0, 1, 1, 0, 0)

    这里顺便提一下:对于两个n维向量x和y,每个属性都是一个二元属性(只能取0或1),

    M11表示x取1,y也取1的属性个数

    M10表示x取1,y取0的属性个数

    M01表示x取0,y取1的属性个数

    M00表示x取0,y也取0的属性个数

    都取0的情况在计算Jaccard系数时时不考虑的,因为比如对于两个文档向量,其实0占的很多,就是文档向量其实是稀疏的,如果考虑都取0的情况,那两个文档会因为0多而相似,不合理。

    因此:

    所以对于上面给出的两个向量x和y

    J(x, y) = 1/(2+1+1) = 1/4

    EJ(x, y) = 1/(3+2-1) = 1/4

    2.5 调整余弦相似度(Adjusted Cosine Similarity)

      虽然余弦相似度对个体间存在的偏见可以进行一定的修正,但是因为只能分辨个体在维之间的差异,没法衡量每个维数值的差异,会导致这样一个情况:比如用户对内容评分,5分制,X和Y两个用户对两个内容的评分分别为(1,2)和(4,5),使用余弦相似度得出的结果是0.98,两者极为相似,但从评分上看X似乎不喜欢这2个内容,而Y比较喜欢,余弦相似度对数值的不敏感导致了结果的误差,需要修正这种不合理性,就出现了调整余弦相似度,即所有维度上的数值都减去一个均值,比如X和Y的评分均值都是3,那么调整后为(-2,-1)和(1,2),再用余弦相似度计算,得到-0.8,相似度为负值并且差异不小,但显然更加符合现

    三  欧氏距离与 余炫相似度

           3.1侧重点区别

             两者相同的地方,就是在机器学习中都可以用来计算相似度,但是两者的含义有很大差别:

    前者是看成坐标系中两个,来计算两点之间的距离

    后者是看成坐标系中两个向量,来计算两向量之间的夹角

    前者因为是,所以一般指位置上的差别,即距离

    后者因为是向量,所以一般指方向上的差别,即所成夹角



         如果保持A点的位置不变,B点朝原方向远离坐标轴原点,那么这个时候余弦相似度cosθ是保持不变的,因为夹角不变,而A、B两点的距离显然在发生改变,这就是欧氏距离和余弦相似度的不同之处。

    3.2  适用场景

         根据欧氏距离和余弦相似度各自的计算方式和衡量特征,分别适用于不同的数据分析模型:

         

          欧氏距离能够体现个体数值特征的绝对差异,所以更多的用于需要从维度的数值大小中体现差异的分析,如使用用户行为指标分析用户价值的相似度或差异;

          余弦相似度更多的是从方向上区分差异,而对绝对的数值不敏感,更多的用于使用用户对内容评分来区分用户兴趣的相似度和差异同时修正了用户间可能存在的度量标准不统一的问题(因为余弦相似度对绝对数值不敏感)。

    3.3关于归一化:

    因为余弦值的范围是 [-1,+1] ,相似度计算时一般需要把值归一化到 [0,1],一般通过如下方式:

    sim = 0.5 + 0.5 * cosθ
    若在欧氏距离公式中,取值范围会很大,一般通过如下方式归一化:

    sim = 1 / (1 + dist(X,Y))


    3.4 实例理解

      举个栗子吧:

           例如某T恤从100块降到了50块(A(100,50)),某西装从1000块降到了500块(B(1000,500))

    那么T恤和西装都是降价了50%, 两者的价格变动趋势一致, 余弦相似度为最大值,即两者有很高的变化趋势相似度

    但是从商品价格本身的角度来说,两者相差了好几百块的差距,欧氏距离较大,即两者有较低的价格相似度



    参考文献:

    距离和相似度度量

    http://webdataanalysis.net/reference-and-source/distance-and-similarity/

    欧氏距离和余弦相似度

    http://blog.csdn.net/linvo/article/details/9333019


    展开全文
  • 数学中各种距离的定义

    万次阅读 2016-05-30 23:28:12
    做分类时常常需要估算不同样本之间的相似性度量(SimilarityMeasurement),这时通常采用的方法就是计算样本间的“距离”(Distance)。采用什么样的方法计算距离是很讲究,甚至关系到分类的正确与否。  本文的...

    在做分类时常常需要估算不同样本之间的相似性度量(SimilarityMeasurement),这时通常采用的方法就是计算样本间的“距离”(Distance)。采用什么样的方法计算距离是很讲究,甚至关系到分类的正确与否。

      本文的目的就是对常用的相似性度量作一个总结。


    本文目录:

    1.欧氏距离

    2.曼哈顿距离

    3. 切比雪夫距离

    4. 闵可夫斯基距离

    5.标准化欧氏距离

    6.马氏距离

    7.夹角余弦

    8.汉明距离

    9.杰卡德距离& 杰卡德相似系数

    10.相关系数& 相关距离

    11.信息熵

    12.巴氏距离

    13.皮尔逊系数


    1. 欧氏距离(EuclideanDistance)

           欧氏距离是最易于理解的一种距离计算方法,源自欧氏空间中两点间的距离公式。

    (1)二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离:

     

    (2)三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离:

     

    (3)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的欧氏距离:

     

      也可以用表示成向量运算的形式:

     

    (4)Matlab计算欧氏距离

    Matlab计算距离主要使用pdist函数。若X是一个M×N的矩阵,则pdist(X)将X矩阵M行的每一行作为一个N维向量,然后计算这M个向量两两间的距离。

    例子:计算向量(0,0)、(1,0)、(0,2)两两间的欧式距离

    X= [0 0 ; 1 0 ; 0 2]

    D= pdist(X,'euclidean')

    结果:

    D=

        1.0000   2.0000    2.2361

     


    2. 曼哈顿距离(ManhattanDistance)

           从名字就可以猜出这种距离的计算方法了。想象你在曼哈顿要从一个十字路口开车到另外一个十字路口,驾驶距离是两点间的直线距离吗?显然不是,除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源, 曼哈顿距离也称为城市街区距离(CityBlock distance)

    (1)二维平面两点a(x1,y1)与b(x2,y2)间的曼哈顿距离

     

    (2)两个n维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的曼哈顿距离

     

    (3)Matlab计算曼哈顿距离

    例子:计算向量(0,0)、(1,0)、(0,2)两两间的曼哈顿距离

    X= [0 0 ; 1 0 ; 0 2]

    D= pdist(X, 'cityblock')

    结果:

    D=

         1    2     3


    3. 切比雪夫距离 ( Chebyshev Distance )

           国际象棋玩过么?国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步?自己走走试试。你会发现最少步数总是max(| x2-x1 | , | y2-y1 | ) 步。有一种类似的一种距离度量方法叫切比雪夫距离。

    (1)二维平面两点a(x1,y1)与b(x2,y2)间的切比雪夫距离

     

    (2)两个n维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的切比雪夫距离

     

      这个公式的另一种等价形式是

     

           看不出两个公式是等价的?提示一下:试试用放缩法和夹逼法则来证明。

    (3)Matlab计算切比雪夫距离

    例子:计算向量(0,0)、(1,0)、(0,2)两两间的切比雪夫距离

    X= [0 0 ; 1 0 ; 0 2]

    D= pdist(X, 'chebychev')

    结果:

    D=

         1    2     2

     


    4. 闵可夫斯基距离(MinkowskiDistance)

    闵氏距离不是一种距离,而是一组距离的定义。

    (1)闵氏距离的定义

           两个n维变量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的闵可夫斯基距离定义为:

     

    其中p是一个变参数。

    当p=1时,就是曼哈顿距离

    当p=2时,就是欧氏距离

    当p→∞时,就是切比雪夫距离

           根据变参数的不同,闵氏距离可以表示一类的距离。

    (2)闵氏距离的缺点

      闵氏距离,包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。

      举个例子:二维样本(身高,体重),其中身高范围是150~190,体重范围是50~60,有三个样本:a(180,50),b(190,50),c(180,60)。那么a与b之间的闵氏距离(无论是曼哈顿距离、欧氏距离或切比雪夫距离)等于a与c之间的闵氏距离,但是身高的10cm真的等价于体重的10kg么?因此用闵氏距离来衡量这些样本间的相似度很有问题。

           简单说来,闵氏距离的缺点主要有两个:(1)将各个分量的量纲(scale),也就是“单位”当作相同的看待了。(2)没有考虑各个分量的分布(期望,方差等)可能是不同的。

    (3)Matlab计算闵氏距离

    例子:计算向量(0,0)、(1,0)、(0,2)两两间的闵氏距离(以变参数为2的欧氏距离为例)

    X= [0 0 ; 1 0 ; 0 2]

    D= pdist(X,'minkowski',2)

    结果:

    D=

        1.0000   2.0000    2.2361



    5. 标准化欧氏距离(Standardized Euclidean distance )

    (1)标准欧氏距离的定义

      标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。标准欧氏距离的思路:既然数据各维分量的分布不一样,好吧!那我先将各个分量都“标准化”到均值、方差相等吧。均值和方差标准化到多少呢?这里先复习点统计学知识吧,假设样本集X的均值(mean)为m,标准差(standarddeviation)为s,那么X的“标准化变量”表示为:

      而且标准化变量的数学期望为0,方差为1。因此样本集的标准化过程(standardization)用公式描述就是:

      标准化后的值 =  ( 标准化前的值  - 分量的均值 ) /分量的标准差

      经过简单的推导就可以得到两个n维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的标准化欧氏距离的公式:

      如果将方差的倒数看成是一个权重,这个公式可以看成是一种加权欧氏距离(WeightedEuclidean distance)

    (2)Matlab计算标准化欧氏距离

    例子:计算向量(0,0)、(1,0)、(0,2)两两间的标准化欧氏距离 (假设两个分量的标准差分别为0.5和1)

    X= [0 0 ; 1 0 ; 0 2]

    D= pdist(X, 'seuclidean',[0.5,1])

    结果:

    D=

        2.0000   2.0000    2.8284

     


    6. 马氏距离(MahalanobisDistance)

    (1)马氏距离定义

           有M个样本向量X1~Xm,协方差矩阵记为S,均值记为向量μ,则其中样本向量X到u的马氏距离表示为:

     

           而其中向量Xi与Xj之间的马氏距离定义为:

           若协方差矩阵是单位矩阵(各个样本向量之间独立同分布),则公式就成了:

           也就是欧氏距离了。

      若协方差矩阵是对角矩阵,公式变成了标准化欧氏距离。

    (2)马氏距离的优缺点:量纲无关,排除变量之间的相关性的干扰。

    (3)Matlab计算(1 2),( 1 3),( 2 2),( 3 1)两两之间的马氏距离

    X = [1 2; 1 3; 2 2; 3 1]

    Y = pdist(X,'mahalanobis')

     

    结果:

    Y=

        2.3452   2.0000    2.3452    1.2247   2.4495    1.2247

     


    7. 夹角余弦(Cosine)

           有没有搞错,又不是学几何,怎么扯到夹角余弦了?各位看官稍安勿躁。几何中夹角余弦可用来衡量两个向量方向的差异,机器学习中借用这一概念来衡量样本向量之间的差异。

    (1)在二维空间中向量A(x1,y1)与向量B(x2,y2)的夹角余弦公式:

    (2)两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夹角余弦

           类似的,对于两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n),可以使用类似于夹角余弦的概念来衡量它们间的相似程度。

      即:

           夹角余弦取值范围为[-1,1]。夹角余弦越大表示两个向量的夹角越小,夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值1,当两个向量的方向完全相反夹角余弦取最小值-1。

           夹角余弦的具体应用可以参阅参考文献[1]。

    (3)Matlab计算夹角余弦

    例子:计算(1,0)、( 1,1.732)、(-1,0)两两间的夹角余弦

    X= [1 0 ; 1 1.732 ; -1 0]

    D= 1- pdist(X, 'cosine')  % Matlab中的pdist(X,'cosine')得到的是1减夹角余弦的值

    结果:

    D=

        0.5000  -1.0000   -0.5000

     


    8. 汉明距离(Hammingdistance)

    (1)汉明距离的定义

           两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。例如字符串“1111”与“1001”之间的汉明距离为2。

           应用:信息编码(为了增强容错性,应使得编码间的最小汉明距离尽可能大)。

    (2)Matlab计算汉明距离

      Matlab中2个向量之间的汉明距离的定义为2个向量不同的分量所占的百分比。

           例子:计算向量(0,0)、(1,0)、(0,2)两两间的汉明距离

    X = [0 0 ; 1 0 ; 0 2];

    D = PDIST(X, 'hamming')

    结果:

    D=

        0.5000   0.5000    1.0000

     


    9. 杰卡德相似系数(Jaccardsimilarity coefficient)

    (1) 杰卡德相似系数

           两个集合A和B的交集元素在A,B的并集中所占的比例,称为两个集合的杰卡德相似系数,用符号J(A,B)表示。

      杰卡德相似系数是衡量两个集合的相似度一种指标。

    (2) 杰卡德距离

           与杰卡德相似系数相反的概念是杰卡德距离(Jaccarddistance)。杰卡德距离可用如下公式表示:

      杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。

    (3)杰卡德相似系数与杰卡德距离的应用

           可将杰卡德相似系数用在衡量样本的相似度上。

      样本A与样本B是两个n维向量,而且所有维度的取值都是0或1。例如:A(0111)和B(1011)。我们将样本看成是一个集合,1表示集合包含该元素,0表示集合不包含该元素。

    p:样本A与B都是1的维度的个数

    q:样本A是1,样本B是0的维度的个数

    r:样本A是0,样本B是1的维度的个数

    s:样本A与B都是0的维度的个数


    那么样本A与B的杰卡德相似系数可以表示为:

    这里p+q+r可理解为A与B的并集的元素个数,而p是A与B的交集的元素个数。

    而样本A与B的杰卡德距离表示为:

    (4)Matlab计算杰卡德距离

    Matlab的pdist函数定义的杰卡德距离跟我这里的定义有一些差别,Matlab中将其定义为不同的维度的个数占“非全零维度”的比例。

    例子:计算(1,1,0)、(1,-1,0)、(-1,1,0)两两之间的杰卡德距离

    X= [1 1 0; 1 -1 0; -1 1 0]

    D= pdist( X , 'jaccard')

    结果

    D=

    0.5000    0.5000   1.0000

     


    10. 相关系数( Correlation coefficient )与相关距离(Correlation distance)

    (1)相关系数的定义

    相关系数是衡量随机变量X与Y相关程度的一种方法,相关系数的取值范围是[-1,1]。相关系数的绝对值越大,则表明X与Y相关度越高。当X与Y线性相关时,相关系数取值为1(正线性相关)或-1(负线性相关)。

    (2)相关距离的定义

     

    (3)Matlab计算(1, 2 ,3 ,4 )与( 3 ,8 ,7 ,6 )之间的相关系数与相关距离

    X = [1 2 3 4 ; 3 8 7 6]

    C = corrcoef( X' )   %将返回相关系数矩阵

    D = pdist( X , 'correlation')

    结果:

    C=

        1.0000   0.4781

        0.4781   1.0000

    D=

    0.5219

          其中0.4781就是相关系数,0.5219是相关距离。


    11. 信息熵(Information Entropy)

           信息熵并不属于一种相似性度量。那为什么放在这篇文章中啊?这个。。。我也不知道。 (╯▽╰)

    信息熵是衡量分布的混乱程度或分散程度的一种度量。分布越分散(或者说分布越平均),信息熵就越大。分布越有序(或者说分布越集中),信息熵就越小。

           计算给定的样本集X的信息熵的公式:

    参数的含义:

    n:样本集X的分类数

    pi:X中第i类元素出现的概率

           信息熵越大表明样本集S分类越分散,信息熵越小则表明样本集X分类越集中。。当S中n个分类出现的概率一样大时(都是1/n),信息熵取最大值log2(n)。当X只有一个分类时,信息熵取最小值0


    12、巴氏距离(Bhattacharyya Distance),在统计中,Bhattacharyya距离测量两个离散或连续概率分布的相似性。它与衡量两个统计样品或种群之间的重叠量的Bhattacharyya系数密切相关。Bhattacharyya距离和Bhattacharyya系数以20世纪30年代曾在印度统计研究所工作的一个统计学家A. Bhattacharya命名。同时,Bhattacharyya系数可以被用来确定两个样本被认为相对接近的,它是用来测量中的类分类的可分离性。

    (1)巴氏距离的定义
    对于离散概率分布 p和q在同一域 X,它被定义为:
    其中:
    是Bhattacharyya系数。
    对于连续概率分布,Bhattacharyya系数被定义为:
    这两种情况下,巴氏距离 并没有服从三角不等式.(值得一提的是,Hellinger距离不服从三角不等式 )。 
    对于多变量的高斯分布 

    和是手段和协方差的分布
    需要注意的是,在这种情况下,第一项中的Bhattacharyya距离与马氏距离有关联。 
    (2)Bhattacharyya系数
    Bhattacharyya系数是两个统计样本之间的重叠量的近似测量,可以被用于确定被考虑的两个样本的相对接近。
    计算Bhattacharyya系数涉及集成的基本形式的两个样本的重叠的时间间隔的值的两个样本被分裂成一个选定的分区数,并且在每个分区中的每个样品的成员的数量,在下面的公式中使用
    考虑样品a 和 b ,n是的分区数,并且 被一个 和 b i的日分区中的样本数量的成员。更多介绍请参看: http://en.wikipedia.org/wiki/Bhattacharyya_coefficient

    13.皮尔逊系数(Pearson Correlation Coefficient)
        在具体阐述皮尔逊相关系数之前,有必要解释下什么是相关系数 ( Correlation coefficient )与相关距离(Correlation distance)。
        相关系数 ( Correlation coefficient )的定义是:
    ( 其中,E为数学期望或均值,D为方差,D开根号为标准差,E{ [X-E(X)] [Y-E(Y)]}称为随机变量X与Y的协方差,记为Cov(X,Y),即Cov(X,Y) = E{ [X-E(X)] [Y-E(Y)]},而两个变量之间的协方差和标准差的商则称为随机变量X与Y的相关系数,记为)
       相关系数衡量随机变量X与Y相关程度的一种方法,相关系数的取值范围是[-1,1]。相关系数的绝对值越大,则表明X与Y相关度越高。当X与Y线性相关时,相关系数取值为1(正线性相关)或-1(负线性相关)。
        具体的,如果有两个变量:X、Y,最终计算出的相关系数的含义可以有如下理解:
    1. 当相关系数为0时,X和Y两变量无关系。
    2. 当X的值增大(减小),Y值增大(减小),两个变量为正相关,相关系数在0.00与1.00之间。
    3. 当X的值增大(减小),Y值减小(增大),两个变量为负相关,相关系数在-1.00与0.00之间。
       相关距离的定义是:

    OK,接下来,咱们来重点了解下皮尔逊相关系数。
        在统计学中,皮尔逊积矩相关系数(英语:Pearson product-moment correlation coefficient,又称作 PPMCC或PCCs, 用r表示)用于度量两个变量X和Y之间的相关(线性相关),其值介于-1与1之间。

    通常情况下通过以下取值范围判断变量的相关强度:
    相关系数     0.8-1.0     极强相关
                     0.6-0.8     强相关
                     0.4-0.6     中等程度相关
                     0.2-0.4     弱相关
                     0.0-0.2     极弱相关或无相关

    在自然科学领域中,该系数广泛用于度量两个变量之间的相关程度。它是由卡尔·皮尔逊从弗朗西斯·高尔顿在19世纪80年代提出的一个相似却又稍有不同的想法演变而来的。这个相关系数也称作“皮尔森相关系数r”。
    (1)皮尔逊系数的定义
    两个变量之间的皮尔逊相关系数定义为两个变量之间的协方差和标准差的商:
    以上方程定义了总体相关系数, 一般表示成希腊字母ρ(rho)。基于样本对协方差和方差进行估计,可以得到样本标准差, 一般表示成r:
    一种等价表达式的是表示成标准分的均值。基于(Xi, Yi)的样本点,样本皮尔逊系数是

                   其中  及  ,分别是标准分、样本平均值和样本标准差。

    或许上面的讲解令你头脑混乱不堪,没关系,我换一种方式讲解,如下:

    假设有两个变量X、Y,那么两变量间的皮尔逊相关系数可通过以下公式计算:

    • 公式一:
    注:勿忘了上面说过,“皮尔逊相关系数定义为两个变量之间的协方差和标准差的商”,其中标准差的计算公式为:
    • 公式二:
    • 公式三:
    • 公式四:

    以上列出的四个公式等价,其中E是数学期望,cov表示协方差,N表示变量取值的个数。

    (2)皮尔逊相关系数的适用范围
    当两个变量的标准差都不为零时,相关系数才有定义,皮尔逊相关系数适用于:
    1. 两个变量之间是线性关系,都是连续数据。
    2. 两个变量的总体是正态分布,或接近正态的单峰分布。
    3. 两个变量的观测值是成对的,每对观测值之间相互独立。
    (3)如何理解皮尔逊相关系数

    rubyist:皮尔逊相关系数理解有两个角度

    其一, 按照高中数学水平来理解, 它很简单, 可以看做将两组数据首先做Z分数处理之后, 然后两组数据的乘积和除以样本数,Z分数一般代表正态分布中, 数据偏离中心点的距离.等于变量减掉平均数再除以标准差.(就是高考的标准分类似的处理)

    样本标准差则等于变量减掉平均数的平方和,再除以样本数,最后再开方,也就是说,方差开方即为标准差,样本标准差计算公式为:

    所以, 根据这个最朴素的理解,我们可以将公式依次精简为:

    其二, 按照大学的线性数学水平来理解, 它比较复杂一点,可以看做是两组数据的向量夹角的余弦。下面是关于此皮尔逊系数的几何学的解释,先来看一幅图,如下所示:


    回归直线: y=gx(x) [红色] 和 x=gy(y) [蓝色]

    如上图,对于没有中心化的数据, 相关系数与两条可能的回归线y=gx(x) 和 x=gy(y) 夹角的余弦值一致。
    对于没有中心化的数据 (也就是说, 数据移动一个样本平均值以使其均值为0), 相关系数也可以被视作由两个随机变量 向量 夹角 的 余弦值(见下方)。
    举个例子,例如,有5个国家的国民生产总值分别为 10, 20, 30, 50 和 80 亿美元。 假设这5个国家 (顺序相同) 的贫困百分比分别为 11%, 12%, 13%, 15%, and 18% 。 令 x 和 y 分别为包含上述5个数据的向量: x = (1, 2, 3, 5, 8) 和 y = (0.11, 0.12, 0.13, 0.15, 0.18)。
    利用通常的方法计算两个向量之间的夹角  (参见 数量积), 未中心化 的相关系数是:


    我们发现以上的数据特意选定为完全相关: y = 0.10 + 0.01 x。 于是,皮尔逊相关系数应该等于1。将数据中心化 (通过E(x) = 3.8移动 x 和通过 E(y) = 0.138 移动 y ) 得到 x = (−2.8, −1.8, −0.8, 1.2, 4.2) 和 y = (−0.028, −0.018, −0.008, 0.012, 0.042), 从中

    (4)皮尔逊相关的约束条件

    从以上解释, 也可以理解皮尔逊相关的约束条件:

    • 1 两个变量间有线性关系
    • 2 变量是连续变量
    • 3 变量均符合正态分布,且二元分布也符合正态分布
    • 4 两变量独立

    在实践统计中,一般只输出两个系数,一个是相关系数,也就是计算出来的相关系数大小,在-1到1之间;另一个是独立样本检验系数,用来检验样本一致性。

         简单说来,各种“距离”的应用场景简单概括为,空间:欧氏距离,路径:曼哈顿距离,国际象棋国王:切比雪夫距离,以上三种的统一形式:闵可夫斯基距离,加权:标准化欧氏距离,排除量纲和依存:马氏距离,向量差距:夹角余弦,编码差别:汉明距离,集合近似度:杰卡德类似系数与距离,相关:相关系数与相关距离。


    参考资料: 

    [1]吴军. 数学之美 系列 12 -余弦定理和新闻的分类.

    http://www.google.com.hk/ggblog/googlechinablog/2006/07/12_4010.html

    [2]Wikipedia. Jaccard index.

    http://en.wikipedia.org/wiki/Jaccard_index

    [3]Wikipedia. Hamming distance

    http://en.wikipedia.org/wiki/Hamming_distance

    [4] 求马氏距离(Mahalanobisdistance )matlab版

    http://junjun0595.blog.163.com/blog/static/969561420100633351210/

    [5] Pearson product-momentcorrelation coefficient

    http://en.wikipedia.org/wiki/Pearson_product-moment_correlation_coefficient


    展开全文
  • 数学常识--两点之间距离公式

    千次阅读 2019-12-05 14:57:34
    概率统计中最常使用作为统计分布程度的测量。标准差是方差的算术平方根。标准差能反映一个数据集的离散程度。平均数相同的两组数据,标准差未必相同。 ⒈方差 s^2=[(x1-x)^2+(x2-x)^2+......(xn-x)^2...
  • 来源:环球物理摘要:这个题目当今Computer Vision中百花齐放的世界中并没有任何特别的地方。事实,使用各种Graphical Model把各种东西联合一起...
  • 凸优化中的数学(二)之——范数,距离、单位球我们首先给出范数的定义:
  • TOPSIS称为优劣解距离法。是一种常用的综合评价方法,能充分利用原始数据的信息,其结果能精确地反映各评价方案之间地差距。 首先分析层次分析法地一些局限性: (1)评价的决策层不能太多,太多的话n会很大,判断...
  • 数学(1)初一学期数学笔记

    千次阅读 2018-12-03 17:38:19
    正数是数学术语,比0大的数正数(positive number),0本身不算正数。正数与负数表示意义相反的量。 正数前面常有一个符号“+”,通常可以省略不写。 2.负数 负数是数学术语,比0小的数叫做负数,负数与正数表示...
  • 3D数学读书笔记——向量运算及c++的实现

    万次阅读 多人点赞 2014-05-03 09:47:05
    关于向量运算及c++的实现的内容
  • 优劣解距离法(TOPSIS法)(备用) 优劣解距离法(TOPSIS)又称理想解法,是一种有效的多指标评价方法。这种方法通过构造评价问题的正理想解和负理想解,即各指标的最大值和最小值,通过计算每个方案到理想方案的相对...
  • 在数学的海洋中飘荡

    千次阅读 2012-11-01 19:31:45
    科学网论坛看到的MIT牛人写的数学体系介绍,出自dahuasky的博客,其人现在微软(美国)工作 转自http://dahuasky.spaces.live.com/blog/cns!1AB3BC993DB84FD7!305.entry 在数学的海洋中飘荡 过去的一年中...
  • 2017数学建模总结

    千次阅读 2017-09-19 01:47:30
    2017年数学建模 第一天晚上选题,看了看A,看了看B,B题分析性太强,属于应用统计,数据分析类,和队友商量着战略性放弃,然后就开始查资料,搞东西了,突然回忆起以前姜起源的书貌似讲过CT成像这种东西,翻出来看...
  • 曼哈顿距离又称Manhattan distance,还见到过更加形象的,出租车距离的。具体贴一张图,应该就能明白。 图摘自维基百科,红蓝黄皆为曼哈顿距离,绿色为欧式距离。 2.欧式距离 欧式距离又称...
  • 高等数学上学习总结(集合,邻域,函数)

    千次阅读 多人点赞 2019-03-19 12:09:39
    高等数学是大学中很重要的一门学科,由于大一的时候比较爱玩,根本...高等数学上的核心内容就是一元函数微积分。而一元函数微积分就包括极限,微分,积分和微分方程四个内容。其中极限是基础,微分和积分是运算,微...
  • 数学模型中,射线法求取射线与多边形交点个数来判断点是否多边形内,交点为奇数时多边形内,偶数多边形外 判断几种特殊情况,点为多边形顶点,点多边形边上,射线与多边形交点是多边形的顶点(多边形的每...
  • 数学中空间的含义

    千次阅读 2017-04-20 16:07:36
    在数学中有许多空间表示,比如欧几里德空间、赋范空间、希尔伯特空间等。这些空间之间有什么关系呢?首先要从距离的定义说起。 什么距离呢?实际上距离除了我们经常用到的直线距离外,还有向量距离如Σni=1xi⋅yi...
  • 数学在机器学习中的重要性

    千次阅读 2016-08-06 23:00:20
    数学在机器学习中的重要性[by Dahua Lin] Linear Algebra (线性代数) 和 Statistics (统计学) 是最重要和不可缺少的。这代表了Machine Learning中最主流的两大类方法的基础。一种是以研究函数和变换为重点的代数...
  • 现代数学体系概论

    千次阅读 2019-06-29 21:08:31
    摘要:这个题目当今Computer Vision中百花齐放的世界中并没有任何特别的地方。...小编学习数学的目的,是要想爬巨人的肩膀,希望站更高的高度,能把小编研究的东西看得更深广一些。说起来,小编...
  • 数学分支

    万次阅读 2013-05-29 19:49:31
    “算术”这个词,我国古代是全部数学的统称。至于几何、代数等许多数学分支学科的名称,都是后来很晚的时候才有的。 国外系统地整理前人数学知识的书,要算是希腊的欧几里得的《几何原本》最早。《几何原本》全书...
  • 距离算法汇总

    千次阅读 2018-07-12 12:52:31
    转载自:https://blog.csdn.net/mousever/article/details/459676431. 欧氏距离,最常见的两点之间或多点之间的距离表示法,又称之为欧几里得度量,它...之间的距离为:(1)二维平面两点a(x1,y1)与b(x2,y2)间的欧...
  • MIT牛人解说数学体系

    千次阅读 2011-12-25 17:36:12
    我学习数学的目的,是要想爬巨人的肩膀,希望站更高的高度,能把我自己研究的东西看得更深广一些。说起来,我刚来这个学校的时候,并没有预料到我将会有一个深入数学的旅程。我的导师最初希望我去做的题目,是...
  • 离散数学

    千次阅读 2018-06-14 20:15:07
    版权声明:欢迎转载 https://blog.csdn.net/suntengnb/article/details/78452871注意/技巧:析取符号为V,大写字母V x + y = 3不是命题 前件为假时...也就是说,不改变原意的基础,按照最简单的方式翻译 通用...
  • 曼哈顿距离,欧式距离,明式距离,切比雪夫距离区别
  • 本文总结了常用的数学模型方法和它们的主要用途,主要包括数学和统计的建模方法,关于在数学建模中也挺常用的机器学习算法暂时不作补充,以后有时间就补。至于究竟哪个模型更好,需要用数据来验证,还有求解方法也...
  • 歪写数学

    千次阅读 2013-01-23 17:18:42
    我最早是 newsmth 看到本文的,作者的文笔还不错。收藏这里。 刚刚百度了一下,这篇文章最早应该是天涯论坛贴出的,作者是 狗熊不爱的犀牛。 数的起源 故事可以开始于公元前好久的一个印加帝国...
  • 曼哈顿距离又称马氏距离(Manhattan distance),还见到过更加形象的,出租车距离的。具体贴一张图,应该就能明白。 图摘自维基百科,红蓝黄皆为曼哈顿距离,绿色为欧式距离。 2.欧式距离 欧式距离又称...
  • 数学体系简单介绍

    万次阅读 多人点赞 2018-05-27 21:41:24
    我学习数学的目的,是要 想爬巨人的肩膀,希望站更高的高度,能把我自己研究的东西看得更深广一些。说起来,我刚来这个学校的时候,并没有预料到我将会有一个深入数学的旅 程。我的导师...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 34,255
精华内容 13,702
关键字:

在数学上什么叫距离