精华内容
下载资源
问答
  • 机器学习中,我们经常会对两个样本之间的相似度进行度量,此时会用到各种距离公式来反映某类事物在距离上接近或者远离的... 所有距离公式列表: 闵可夫斯基距离(Minkowski Distance) 欧式距离(Euclidean Dist...
    •    机器学习中,我们经常会对两个样本之间的相似度进行度量,此时会用到各种距离公式来反映某类事物在距离上接近或者远离的程度,K近邻算法,K-means聚类算法也涉及到距离公式的选择问题,今天我们就来总结一下常见的几种距离公式,以及这些公式的Python代码实现。

      所有距离公式列表:

    • 闵可夫斯基距离(Minkowski Distance)
    • 欧式距离(Euclidean Distance)
    • 马氏距离(Mahalanobis Distance)
    • 曼哈顿距离(Manhattan Distance)
    • 切比雪夫距离(Chebyshev Distance)
    • 夹角余弦(Cosine)
    • 汉明距离(Hamming Distance)
    • 杰卡德相似系数(Jaccard Similarity Coefficient)

    一.闵可夫斯基距离(Minkowski Distance)

      严格意义上来看,闵可夫斯基距离不是一种距离,而是一组距离的定义。

    两个n维向量A(x11,x12,...x1n)B(x21,x22,...x2n)间的闵可夫斯基距离为:

     

    其中P是一个变参数

    • 当P=1时,就是曼哈顿距离
    • 当P=2时,就是欧式距离
    •  当P->∞时,就是切比雪夫距离。

    因此我们根据P参数的不同,闵可夫斯基距离可以表示一类距离。

    二.欧式距离(Euclidean Distance)

    欧式距离即L2范数,是欧式空间两点间的距离公式,如图

    • 平面上的两点a(x1,y1)和b(x2,y2)间的欧式距离:

    • 三维空间的两点a(x1,y1,z1)和b(x2,y2,z2)间的欧式距离:

    • 两个n维向量A(x11,x12,...x1n)B(x21,x22,...x2n)间的欧式距离为:

    向量表示形式:

     

    三. 马氏距离(Mahalanobis Distance)

    马氏距离是在欧式距离上发展而来,有M个样本向量X1 -Xm,协方差矩阵为S,均值为向量μ,向量X到μ的马氏距离为:

    向量Xi与向量xj的马氏距离为:

    若协方差矩阵是单位矩阵,则是欧式距离公式;若是对角矩阵,则为标准化欧式距离公式。

    马氏距离的优点是:与量纲无关,排除变量之间的相关性的干扰。

    四.曼哈顿距离(Manhattan Distance)

    曼哈顿距离即L1范数,也称为城市街区距离。

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

    • 两个n维向量A(x11,x12,...x1n)与B(x21,x22,...x2n)间的曼哈顿距离为:

     

     

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

    切比雪夫距离即范数。

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

     

    • 两个n维向量A(x11,x12,...x1n)与B(x21,x22,...x2n)间的切比雪夫距离为:

    等价公式为:

     

    六.夹角余弦(Cosine)

    夹角余弦是用来衡量两个向量方向上的差异,我们可以用来表示样本向量间的差异。

    • 二维空间两个向量A(x1,y1)和B(x2,y2)间的夹角余弦公式:

    • 两个n维样本点A(x11,x12,...x1n)与B(x21,x22,...x2n)间的相似度:

     

    或者:

    夹角余弦的取值范围是【-1,1】。夹角余弦越大,表示两个向量的夹角越小。当两个向量重合时,同向,夹角余弦最大,为1,反向,夹角余弦最小,为-1.

    七.汉明距离(Hamming Distance)

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

    八.杰卡德相似系数(Jaccard Similarity Coefficient)

    杰卡德相似系数定义两个集合A和B的交集元素在A,B集合的并集中所占的比例。是用来衡量两个集合相似度的一种指标。

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

     

     

    参考书籍:机器学习算法原理与编程实现

     

    转载于:https://www.cnblogs.com/lilin22/p/8747782.html

    展开全文
  • 根据语料库,把所有的词都提取出来,编上序号 第二步:独热编码,D维向量 记词典大小为D,那么每个文章就是一个D维向量:每个位置上的数字表示对应编号的词在该文章中出现的次数。 1.1.2 词袋模型的缺点 只....

    1. 文本向量化

    1.1 词袋模型

    词袋模型,顾名思义,就是将文本视为一个 “装满词的袋子” ,袋子里的词语是随便摆放的,没有顺序和语义之分。

    1.1.1 词袋模型的步骤

    • 第一步:构造词典
      根据语料库,把所有的词都提取出来,编上序号
    • 第二步:独热编码,D维向量
      记词典大小为D,那么每个文章就是一个D维向量:每个位置上的数字表示对应编号的词在该文章中出现的次数。

    1.1.2 词袋模型的缺点

    • 只统计词语是否出现或者词频,会被无意义的词汇所影响
      解决:文本预处理(a.去除停用词;b.文字、字母、标点符号统一;c.利用TF-IDF去除不重要的词)
    • 无法识别语义层面的信息
      解决:基于深度学习的文本表示(词向量、句向量等)
    • 无法关注词语之间的顺序关系
      解决:深度学习

    1.2 TF-IDF

    TF-IDF是一种统计方法,用以评估某一字词对于语料库中的一篇文章的重要程度。其算法简单快速,结果也比较符合实际情况。

    1.2.1 TF-IDF的步骤

    • 第一步:统计词频TF
      统计每个词在文本中出现的次数,出现的越频繁,那么就越可能是这个文章的关键词。
     词频TF = 某个词在文章中出现的次数/文章的总词数
     词频TF = 某个词在文章中出现的次数/文章中出现的最多的词出现的次数
    
    • 第二步:计算逆文档频率IDF
      IDF用于衡量每一个词在语料库中的重要性,一个词在语料库中越少见,它的权重就越大;反之,一个词在语料库中越常见,它的权重就越小。
    //首先需要有一个语料库,来模拟语言的使用环境。
    逆文档频率IDF = log(语料库的文章总数/(包含该词的文章数+1))
    
    • 第三步:计算TF-IDF
      TF-IDF用于衡量某个词在文章中的重要性。TF-IDF与该词在文章中的出现次数成正比,与该词在整个语料库中的出现次数成反比。
    TF-IDF = TF * IDF
    

    TF-IDF还可以用于关键词的自动提取:在计算出文章中的每个词的TF-IDF值后,按降序排列,取排在最前面的几个词。

    1.2.2 TF-IDF的缺点

    • 维度太高,不易于计算
      解决:引入了LSI,从语义和文本的潜在主题来分析。

    LSI是概率主题模型的一种,基于统计学和概率论方法实现,类似的模型有LDA等。
    核心思想:每篇文本中有多个概率分布不同的主题,每个主题中都包含所有已知词,但是这些词在不同主题中的概率分布不同。LSI通过奇异值分解的方法,计算文本中的各个主题的概率分布。
    优点:向量从词的维度下降到主题的维度,维度更少,计算更快。

    • 无法体现词的位置信息
      解决:对全文的第一段和每一段的第一句话,给予较大的权重。
    • 无法识别语义层面的信息
      解决:基于深度学习的文本表示(词向量、句向量等)
    • 无法关注词语之间的顺序关系
      解决:深度学习

    1.3 词向量:word2vec

    详见本人博客:词向量(从one-hot到word2vec) - 银山词霸的碎碎念 - CSDN博客
    https://blog.csdn.net/weixin_38493025/article/details/85245044

    2. 距离公式

    2.1 余弦相似度

    在这里插入图片描述
    余弦值越接近1,就表明夹角越接近0度,也就是两个向量越相似,这就叫"余弦相似性"。

    参考教程

    展开全文
  • 双目摄像头可以完成所有单目摄像头能完成的功能,同时能够获得后者永远无法企及的深度信息。 无论何种状态的驾驶系统,无人的还是有人的,对障碍物的信息最重要的是障碍物与自车之间的距离,其次才是识别障碍物的...

      双目摄像头可以完成所有单目摄像头能完成的功能,同时能够获得后者永远无法企及的深度信息。
      无论何种状态的驾驶系统,无人的还是有人的,对障碍物的信息最重要的是障碍物与自车之间的距离,其次才是识别障碍物的类型。
      准确判断障碍物与自车间的距离是保证车辆安全的首要信息,只有获得准确的距离信息,才能准确得出有可能发生碰撞的时间,也就是TTC。单纯识别障碍物毫无意义,识别出前方是个小孩,但无法得出准确距离信息,就无法得出准确的TTC,就无法保证小孩的安全。等识别出来,人可能已经被撞死,届时深度学习图像识别毫无意义。
      当然,激光雷达在距离测量上也很精确,同时FOV也很大,覆盖面更广,但是成本高,功能单一,无法识别颜色(刹车灯)。而双目不仅能精确地测量距离,同时还可以识别刹车灯,车道线,路旁的交通标志等。豪华车也不是不计成本的,所以双目摄像头成了豪华车的首选。
      对单目来说,要想获得距离信息,必须先识别目标。
      要提供目标距离信息,首先要对目标进行框图边界分割,而分割和识别是一体的,不识别无法准确分割。
    图像识别简单分为两大类:一类是基于词包模型的图像识别,一类是基于深度学习的图像识别。
      欧洲NAVER实验室高级科学家Gabriela Csurka等人首次将“自然语言处理”领域的 BoVM(bag-of-words)模型引入到图像分类领域。就是将图像类比为文档,将图像信息用若干单词表示,最终用单词的频率直方图表示图像。
      首先,将一幅图像待检测的特征点或者特征区域用特征描述算子对其进行描述。将提取的特征算子采用机器学习的方法进行训练获得用特征频率表示的视觉单词组成的视觉词典。
      最后,通过对不同类别的视觉直方图进行学习,便可以获得学习模型。在测试环节,提取待测试图像的特征,获得待测试图像的视觉单词直方图,与上述获得的学习模型与待测试图像的频率直方图进行匹配,获得分类识别结果。
    由此可见,将 Bag-of-Word 应用到图像分类模型上通常需要三个步骤:特征检测与描述、视觉词典的构建、分类器。

    视觉词包模型(bag-of-words)相对比其他模型最大的优势在于适用于大部分的应用场合,可以简单直观地把图像表示成直方图呈现出来,这样就可以使图像分类识别问题转化成普通模式识别问题,所需运算资源少。
    但是,视觉词包模型也有一些缺点:
    • 使用特征用视觉单词直方图表示,在这个转化的过程中,丢了特征的位置信息,在一些需要位置信息的研究中,如前方突然掉落的物体,突然出现的行人,这个方法明显是不适合的;
    • 在视觉词包模型建立的在单词与单词之间相互独立的基础上,但是有些情况,单词与单词之间是互相有联系的,如连续的视频,因此,视觉词包模型在这种情况下使用,是造成识别结果较差。
      词包模型实际上相当于只包含了一个卷积层和一个汇聚层,且模型采用无监督方式进行特征表达学习,而卷积神经网络则包含了更多层的简单、复杂细胞,可以进行更为复杂的特征变换,并且其学习过程是有监督过程的,滤波器权重可以根据数据与任务不断进行调整,从而学习到更有意义的特征表达。
      从这个角度来看,卷积神经网络具有更为强大的特征表达能力,因此它在图像识别任务中的出色性能就很容易解释了。
    分割并识别后是估算距离,单目估算距离主要是根据像素大小,这种方法准确度不高。
      由于距离因素,行人3和行人2的像素大小是非常接近的,但行人2和行人3与车辆距离距离差别很大,但是在单目看来,距离是完全一样的。
    双目与单目区别有几点,首先双目是测量距离而非估算。
    双目测距原理


    上图为双目的距离计算公式,准确度比单目要高得多。双目与单目区别的第二点是双目可以在不识别目标的情况获得深度(距离)数据。

     

    双目典型工作流程图

    上图为双目的典型工作流程图。双目最后输出的是一张深度图。

    用颜色深浅来代表距离。双目虽然不需要识别目标,但是双目需要级化分割(Segmentation),常使用的算法有Belief Propagation和Mean Shift。双目最关键的环节在立体匹配。

    双目需要对每一个像素点都做立体匹配,运算量很大,但算法简单,比较适合用FPGA来完成,而FPGA不是特斯拉这种小厂能玩得转的。

    转载于:https://www.cnblogs.com/fuhang/p/7855789.html

    展开全文
  • 返回一个表示节点 i 与其他所有节点距离之和的列表 ans。 输入: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]] 输出: [8,12,6,10,10,10] 解释: 如下为给定的树的示意图: 0 / \ 1 2 /|\ 3 4 5 我们可以计算...

    一、Problem

    给定一个无向、连通的树。树中有 N 个标记为 0…N-1 的节点以及 N-1 条边 。

    第 i 条边连接节点 edges[i][0] 和 edges[i][1] 。

    返回一个表示节点 i 与其他所有节点距离之和的列表 ans。

    输入: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
    输出: [8,12,6,10,10,10]
    解释: 
    如下为给定的树的示意图:
      0
     / \
    1   2
       /|\
      3 4 5
    
    我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) 
    也就是 1 + 1 + 2 + 2 + 2 = 8。 因此,answer[0] = 8,以此类推。
    

    说明: 1 <= N <= 10000

    二、Solution

    方法一:2 × dfs + 公式推导

    最暴力的方法就是枚举所有 x,求递归地出它到其它结点的距离(比如 x->y->z,要求 x 就必须求 y,求 y 就必须求 z),然后将 z、y 的结果返回给 x;对于 y 也是如此,时间复杂度为 O(n2)O(n^2)

    思路

    在这里插入图片描述
    设现在 A—B 这条边被断开后:

    • dist(A)dist(A):表示结点 A 到其子节点 (y1...yn)(y_1...y_n) 的距离总和
      dist(B)dist(B):同理
    • cnt(A)cnt(A):表示结点 A 的子节点数目
      cnt(B)cnt(B):同理
    • ans(A)ans(A):表示结点 A 到其它结点的距离总和
      ans(B)ans(B):同理

    不难发现:
    {ans(A)=dist(A)+dist(B)+cnt(B) ans(B)=dist(B)+dist(A)+cnt(A) \left\{ \begin{aligned} ans(A) = dist(A) + dist(B) + cnt(B)\ ① \\ ans(B) = dist(B) + dist(A) + cnt(A)\ ②\\ \end{aligned} \right.
    附:(加上一个 cnt [B]是因为 A 到 B 的每一个子节点的距离都是在 B 到子节点的距离基础上 +1,总共有 cnt[B] 个子节点)

    一式减二式得
    {ans(A)=ans(B)+cnt(B)cnt(A) =ans(B)+(Ncnt(A))cnt(A) \left\{ \begin{aligned} ans(A) = ans(B) + cnt(B) - cnt(A)\ ③\\ =ans(B)+(N-cnt(A))-cnt(A)\ ④ \end{aligned} \right.

    对于某个父亲节点 fa 与其孩子结点 child 也可推出
    ans(child)=ans(fa)+(Ncnt(child))cnt(child) ans(child)=ans(fa) + (N-cnt(child))-cnt(child)\ ⑤

    算法

    这里需要两步计算:

    • 第一步:根据 ①、② 式与子节点 child 与父节点 fa 算出的数组 ans、cnt
    • 第二步:根据 ⑤ 式子算出最终的 ans
    class Solution {
    public:
    	int n;
    	vector<vector<int>> g;
    	vector<int> ans, cnt;
    	void dfs(int u, int fa) {
    		for (int& v : g[u]) if (v != fa) {
                dfs(v, u);
    			cnt[u] = cnt[u] + cnt[v];
    			ans[u] = ans[u] + ans[v] + cnt[v]; //结点u的距离=所有子节点距离和+子节点数量
    		}
    	}
    	void dfs1(int u, int fa) {
    		for (int& v : g[u]) if (v != fa) {
    			ans[v] = ans[u] + n-cnt[v] - cnt[v];
                dfs1(v, u);
    		}
    	}
        vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& es) {
        	g.resize(N), ans.resize(N), cnt.resize(N, 1);
        	this->n = N;
        	for (auto& e : es) {
        		g[e[0]].push_back(e[1]);
        		g[e[1]].push_back(e[0]);
        	}
        	dfs(0, -1);
        	dfs1(0, -1);
        	return ans;
        }
    };
    

    复杂度分析

    • 时间复杂度:O(n)O(n)
    • 空间复杂度:O(n)O(n)
    展开全文
  • 铰接在最初生成的位置上,它们之间的距离是使用用作健身函数的欧几里得公式来计算的。 使用前述的健身功能,通过轮盘赌轮选择来选择初始人口。 然后计算交叉,如果,交叉的概率。 Pc>(随机生成的概率),使用两点...
  • OGame公式

    2007-12-30 13:31:00
    所有结果取'整数' 飞行时间 a) 前往战场废墟: (10 + (35.000 / Prozent * 开根(5000 / 速度))) / (24 * 60 * 60) b) 在小星系内: (10 + (35.000 / 负载百分数* 开根((1.000.000 + 星球距离 * 5000) / ...
  • 距离与相似度度量

    2018-12-21 11:01:53
    其中p是一个变量,下面的所有距离都是这个公式的特例; p=1就是曼哈顿距离, P=2就是欧式距离,P=无穷时,就是切比雪夫距离. 1.2 欧几里得距离(Euclidean Distance) 最常见的欧式距离就是平面上两点间的距离D=sqrt(x2+y2)...
  • EXCEL函数公式

    热门讨论 2010-03-16 03:26:38
    计算距离退休年龄的公式 求工齡 计算工龄 年龄及工龄计算自动算出工龄日期格式为(yyyy.mm.dd) 【时间和日期应用】 自动显示当前日期公式 如何在单元格中自动填入当前日期 如何判断某日是否星期天 某个日期是星期几 ...
  • 距离与相似性度量

    千次阅读 2017-06-11 21:23:09
    其中p是一个变量,下面的所有距离都是这个公式的特例; p=1就是曼哈顿距离, P=2就是欧式距离,P=无穷时,就是切比雪夫距离.  1.2 欧几里得距离(Euclidean Distance) 最常见的欧式距离就是平面上两点间的距离D=sqrt(x^2+...
  • 类间距离测度方法

    2019-03-27 01:10:00
    就是三角形中线距离公式 两个三角形重心间的距离 平均距离: 两个集合内所有配对的方式连线然后再处理点的配对个数 np*nq 两个集合看成是一个集合 第一个集合把求出Ex ,Ey然后求出方差,第一个集合的...
  • HDU 4311题意二维坐标系上给出n个点,要求在n个点中选定一个点作为中点,使得其它所有点到该点的曼哈顿距离之和最小 曼哈顿距离也叫都市距离,计算公式d = |x1-x2|+|y1-y2| 解决 x轴和y轴独立,分开来做 枚举每...
  • 距离和相似性度量

    2015-12-02 14:57:01
    其中p是一个变量,下面的所有距离都是这个公式的特例; p=1就是曼哈顿距离, P=2就是欧式距离,P=无穷时,就是切比雪夫距离.   2. 欧几里得距离(Euclidean Distance) 最常见的欧式距离就是平面上两点间的距离D=sqrt(x^2...
  • 题意:给出一N个点 每个点距离原点的距离(所有点在一个圆上) 每个点相邻点的角度  思路:其实就是由n-1个三角形组成的一个多边形,求出n-1个三角形的面积和就行。。 公式是高中学的 ½absinA,注意这里的A指的...
  • 范数的公式 范数是衡量某个向量空间(或矩阵...当p=2时,是L2范数, 表示某个向量中所有元素平方和再开根, 也就是欧几里得距离公式。 实际应用与选择 下面以sklearn里逻辑回归算法为例,具体看下两者的不同 ...
  • (注意这里的理解就是“最少”两个字,意思就是在所有能达到同样效果的操作次数中选最小的那个,后边的公式也是如此理解)例子编辑距离计算Levenshtein距离indexbeautyindex0123456b1012345a21...
  • 找到一个超平面,在所有样本点分类正确的前提下,使距离超平面(w,b)最近的几个样本点,与分隔超平面距离最大 原目标函数: 原约束条件: (2)通过等比例缩放w调整几何间隔,得到新的目标函数 (3)求解不等式...
  • HDU_5734_数学推公式

    2016-07-22 18:17:00
     看了题解说是推公式,并且将结果看作是方差,这样W中的负值可直接转化为正值,也即将B所有分量当作1(这里需要想一下),所以只需要看α,当结果为方差时最小,也即α为均值,根据||x||=√∑x...
  • 设计短距离无线系统的人一定都知道Friis公式与路径预测帮助很大:  Pr是天线接收到的信号功率;Pt是发射功率;Gt和Gr分别是发射天线增益和接收天线增益--单位为功率比而非dB,来自各向同性辐射;λ是信号波长,...
  • 计算距离退休年龄的公式 求工齡 计算工龄 年龄及工龄计算自动算出工龄日期格式为(yyyy.mm.dd) 【时间和日期应用】 自动显示当前日期公式 如何在单元格中自动填入当前日期 如何判断某日是否星期天 某个日期是星期几 ...
  • 作者:AirCity 2020.2.2 Aircity007@sina.com 本文所有权归作者Aircity所有 L=10.16×Htop×ln⁡(2s/d) 单位pH Htop:第一层至器件顶层的距离 s:过孔中心间距 d:过孔直径 ...
  • 题目传送门 题意:找一条直线,使得其余的点都在直线的同一侧,而且使得到直线的平均距离最短。 分析:训练指南P274,先求凸包,如果每条边都算一边的...所以只要先求出x的和以及y的和,能在O (1)计算所有距离和。...
  • 排列组合公式 二项式定理 系数性质: ⑴和首末两端等距离的系数相等; ⑵当二项式指数n是奇数时,中间两项最大且相等; ⑶当二项式指数n是偶数时,中间一项最大; ⑷二项式展开式中奇数项和偶数项总和...
  • 每次给个区间[l,r],查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少? 比如储物点i有x个东西,要运到储物点j,代价为x * dist( i , j ) dist就是储物点间的距离。  输入描述: ...
  • python实现:KL距离、jensen-shannon距离

    万次阅读 2016-10-16 16:34:21
    Kullback–Leibler divergence:两个概率分布之间的距离,是从信息熵的角度出发,也叫鉴别信息。 计算公式:    对于所有i,都有Q(i)=0 implies P(i)=0;当p(i)=0时,p(i)*log(p(i))趋向于0 二者并不...
  • 编辑距离(LD)算法

    2015-12-01 15:29:08
    为此,提出一种基于改进编辑距离的字符串相似度求解算法,对字符串相似度度量公式及Levenshtein 矩阵计算方法进行改进。 在计算编辑距离时,以原有矩阵求出两字符串的最长公共子串及所有LD 回溯路径
  • 设计短距离无线系统的人一定都知道Friis公式与路径预测帮助很大:  Pr是天线接收到的信号功率;Pt是发射功率;Gt和Gr分别是发射天线增益和接收天线增益--单位为功率比而非dB,来自各向同性辐射;λ是信号波长,...
  • 支持向量机可以分为三类: 线性可分的情况 ==> 硬间隔最大化 ==> 硬间隔SVM 近似线性可分的情况 ==>...任务:寻找一条与所有支持向量距离最远的决策边界,这条决策边界就是0=wTX+b0 = ...
  • 纹理——灰度共生矩阵公式及代码

    千次阅读 2019-08-27 15:29:07
    灰度共生矩阵(Grey-Level Co-occurence Matrix,GLCM)被定义为从灰度为i的像素点出发,离开某个固定位置(相隔距离为d,方位为)的点上灰度值为的概率,即,所有估计的值可以表示成一个矩阵的形式,以此被称为灰度...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 543
精华内容 217
关键字:

所有距离公式