各种距离的相似度量(距离)计算分类细节和应用(强烈推荐收藏!!!)!(备份)
Distance Classification
Distance
欧氏距离(Euclidean Distance)
闵可夫斯基距离(Minkowski distance)
曼哈顿距离(Manhattan distance)
切比雪夫距离 ( Chebyshev distance )
标准化欧氏距离(Standardized Euclidean distance )
马氏距离(Mahalanobis Distance)
汉明距离(Hamming distance)
余弦相似度(Cosine Similarity)
杰卡德相似系数(Jaccardsimilarity coefficient)
Reference
Distance
由于最近在做故障诊断相关研究,不断学习各种算法,发现在很多算法里面都用到了Distance来定义各种变量之间的关系,确定之间的相关类指标。且在运用算法做分类时需要估不同样本之间的相似性度量(Similarity Measurement,SM),这时通常采用的方法就是计算样本间的“距离”(Distance)。在下面一 一道来!
这可太有意思了,不经让我去寻找,究竟有多少种Distance可以运用在不同的算法里面呢?在不同算法里的计算方式是否有所不同?在计算效率上哪种Distance更优?哪种Distance在算法中运行速度更快,效果更好呢?什么Distance能够使得你的分类或聚类效果更加优秀呢?…
针对太多了疑问和不解,那么现在开始做做Distance的相关解读吧!
首先,了解一下距离计算(聚类分析)
对于函数Dist( ; ),倘若它是一个“距离度量”(distance measure),则需要满足一些基本性质:
欧氏距离(Euclidean Distance)
相信欧氏距离(EuclideanDistance)是很多人都知道且用到的一个距离计算方法,且简单高效。
在我们做聚类分析中常用的基于欧几里得距离的相似矩阵作为一种可行的方法。
欧几里得
简而言之,就是欧式空间中,两点之间的距离公式。
在数学中,欧几里得距离或欧几里得度量是欧几里得空间中两点间“普通”(即直线)距离。使用这个距离,欧氏空间成为度量空间。相关联的范数称为欧几里得范数。较早的文献称之为毕达哥拉斯度量。
欧几里得度量(euclidean metric)(也称欧氏距离)是一个通常采用的距离定义,指在m维空间中两个点之间的真实距离,或者向量的自然长度(即该点到原点的距离)。在二维和三维空间中的欧氏距离就是两点之间的实际距离。
—来源于网络
原理公式
下面简述下计算公式:
二维空间的公式
其中,
简单的说,就是求其二维平面上两点之间的模长。—>本人心得
三维空间的公式
和二维空间一样,只不过多加了一个坐标系的值
再简单的说,同理就是求其三维平面上两点之间的模长。—>本人心得
n维空间的公式
将每个维度的求其模长。 及其不标准描述,别说我说的
拓展内容:
所谓欧氏距离变换,是指对于一张二值图像(在此我们假定白色为前景色,黑色为背景色),将前景中的像素的值转化为该点到达最近的背景点的距离。
欧氏距离变换在数字图像处理中的应用范围很广泛,尤其对于图像的骨架提取,是一个很好的参照。
应用层面
欧氏距离看作信号的相似程度。 距离越近就越相似,就越容易相互干扰,误码率就越高。
最近看了一篇 Paper,大佬级别的,引用率很高。讲的是关于欧几里得距离(欧氏距离)作为主成分分析(PCA)的相似性度量。理论性很强,本人菜鸡一个,目前读的有些老火,上传了网盘,论文可在这里下载【提取码:fvj2】。
《Euclidean Distance as a Similarity Metric for Principal Component Analysis》–KIMBERLY L. ELMORE
cite:[1] Elmore K L , Richman M B . Euclidean Distance as a Similarity Metric for Principal Component Analysis[J]. Monthly Weather Review, 2010, 129(3):540-549.
闵可夫斯基距离(Minkowski distance)
闵氏距离不是一种距离,而是一组距离的定义。是欧氏空间中的一种测度,被看做是欧氏距离的一种推广,欧氏距离是闵可夫斯基距离的一种特殊情况。
闵氏空间指狭义相对论中由一个时间维和三个空间维组成的时空,为俄裔德国数学家闵可夫斯基(H.Minkowski,1864-1909)最先表述。他的平坦空间(即假设没有重力,曲率为零的空间)的概念以及表示为特殊距离量的几何学是与狭义相对论的要求相一致的。闵可夫斯基空间不同于牛顿力学的平坦空间。
闵可夫斯基
一个小故事:
阿尔伯特·爱因斯坦在瑞士苏黎世联邦科技大学(Eidgen?ssische Technische Hochschule, ETH; Swiss Federal Institute of Technology)时期的数学老师赫尔曼·闵可夫斯基在爱因斯坦提出狭义相对论之后,于1907年将爱因斯坦与亨德里克·洛仑兹的理论结果重新表述成(3+1)维的时空,其中光速在各个惯性参考系皆为定值,这样的时空即以其为名,称为闵可夫斯基时空,或称闵可夫斯基空间。
原理公式
官方原理:
闵氏距离有时也指时空间隔,关于时空间隔的内容可跳转看词条解释。
设n维空间中有两点坐标x, y,v为常数,闵式距离定义为
(1)闵氏距离与特征参数的量纲有关,有不同量纲的特征参数的闵氏距离常常是无意义的。
(2)闵氏距离没有考虑特征参数间的相关性,而马哈拉诺比斯距离解决了这个问题。
当v = 1
可得到绝对值距离,也叫曼哈顿距离(Manhattan distance)、出租汽车距离或街区距离(city block distance)。在二维空间中可以看出,这种距离是计算两点之间的直角边距离,相当于城市中出租汽车沿城市街道拐直角前进而不能走两点连接间的最短距离。绝对值距离的特点是各特征参数以等权参与进来,所以也称等混合距离。
当v → ∞
得到切比雪夫距离,下面再做介绍。
应用层面
我们常常将属性划分为“连续属性”(continuous attribute)和“离散属性”(categorical attribute),前者在定义域上有无穷多个可能的取值,后者在定义域上式有限个取值。然而,在讨论距离计算的时候,属性上是否定义“序”关系更为重要。例如,定义域在{1,2,3}的离散属性和连续属性的性质更为接近一些,能直接在属性值上计算距离:“1”和“2”比较接近、与“3”比较远,这样的属性称为“有序属性”(ordinal attribute);而定义为{火车、飞机、船}这样的离散属性则不能直接在属性值上计算距离,称为“无序属性”(non-ordinal attribute)。在这里,闵可夫斯基距离可用于有序距离,
连续属性亦成为“数值属性”(numerical attribute)
离散属性亦成为“列名属性”(nominal attribute)
简单总结:闵可夫斯基距离在面对离散数据集的时候则不适用,而对于有序数列数据集可用。
—来自菜鸡解释,不对可忽略。
曼哈顿距离(Manhattan distance)
由上可知,在闵可夫斯基距离中,当v = 1时,可得到绝对值距离,也叫曼哈顿距离(Manhattan distance)、出租汽车距离或街区距离(city block distance)。
同样也是由上面那位图片上的大佬创建的,这里就不放Photo了
出租车几何或曼哈顿距离(Manhattan Distance)是由十九世纪的赫尔曼·闵可夫斯基所创词汇 ,是种使用在几何度量空间的几何学用语,用以标明两个点在标准坐标系上的绝对轴距总和。
原理公式
官方解释很好理解(附上了)
曼哈顿距离
上图中红线代表曼哈顿距离,绿色代表欧氏距离,也就是直线距离,而蓝色和黄色代表等价的曼哈顿距离。曼哈顿距离——两点在南北方向上的距离加上在东西方向上的距离,即
对于一个具有正南正北、正东正西方向规则布局的城镇街道,从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离,因此,曼哈顿距离又称为出租车距离。曼哈顿距离不是距离不变量,当坐标轴变动时,点间的距离就会不同。曼哈顿距离示意图在早期的计算机图形学中,屏幕是由像素构成,是整数,点的坐标也一般是整数,原因是浮点运算很昂贵,很慢而且有误差,如果直接使用AB的欧氏距离(欧几里德距离:在二维和三维空间中的欧氏距离的就是两点之间的距离),则必须要进行浮点运算,如果使用AC和CB,则只要计算加减法即可,这就大大提高了运算速度,而且不管累计运算多少次,都不会有误差。
菜鸡理解:曼哈顿距离在处理大规模运算的时候,将一些需要用到浮点运算的地方(欧氏距离运算)换成加减运算,在处理器较强的现在,(不懂算法提速的我),或许还会提高运算速度(虽然没有试过,大胆假设一波,再去补补Paper)。在二维三维平面上本来走直线的,现在通过走曲折的“直线”减小计算难度,但增加了计算过程,最终的结果是使得运算速度提速了!!!很神奇
煮个栗子吧
现在请出灵魂画师
此时的曼哈顿距离
应用层面
关于曼哈顿距离的应用,搜罗了大部分Paper,发现都是在计算机领域的应用较多,比如提高改进GPU运算性能、算法层面的性能提升、CV等等…太多了
这里有几篇引用率且水平较高的Paper可读一读。
本菜在不断摸索当中
[1] Chang D J , Desoky A H , Ming O , et al. Compute Pairwise Manhattan Distance and Pearson Correlation Coefficient of Data Points with GPU[C]// 10th ACIS International Conference on Software Engineering, Artificial Intelligences, Networking and Parallel/Distributed Computing, SNPD 2009, in conjunction with 3rd International Workshop on e-Activity, IWEA 2009, 1st International Workshop on Enterprise Architecture Challenges and Responses, WEACR 2009, Catholic University of Daegu, Daegu, Korea, 27-29 May 2009. IEEE, 2009.
[2] Mattausch H J , Omori N , Fukae S , et al. Fully-parallel pattern-matching engine with dynamic adaptability to Hamming or Manhattan distance[C]// VLSI Circuits Digest of Technical Papers, 2002. Symposium on. IEEE, 2002.
[3] Oike Y , Ikeda M , Asada K . A high-speed and low-voltage associative co-processor with exact Hamming/Manhattan-distance estimation using word-parallel and hierarchical search architecture[J]. IEEE Journal of Solid-State Circuits, 2004, 39(8):1383-1387.
深入了解后再细挖(待更新)。
切比雪夫距离 ( Chebyshev distance )
在数学中,切比雪夫距离(Chebyshev distance)或是L ∞
度量,是向量空间中的一种度量,二个点之间的距离定义是其各坐标数值差绝对值的最大值。以数学的观点来看,切比雪夫距离是由一致范数(uniform norm)(或称为上确界范数)所衍生的度量,也是超凸度量(injective metric space)的一种。(—来自网络)
最形象的一个比如应该当属“国际象棋”,相信有大部分人像本弱鸡一样不会下国际象棋,下面直接讲原理。
原理公式
国际象棋棋盘上二个位置间的切比雪夫距离是指王要从一个位子移至另一个位子需要走的步数。由于王可以往斜前或斜后方向移动一格,因此可以较
上一篇: 探索图神经网络的网络架构和训练方法
下一篇: 希尔伯特空间(希尔伯特空间)