精华内容
下载资源
问答
  • 如何利用最近邻算法,根据图片的灰度值判断一张图片在另一张图片位置? 已知: 1. 一张原图片的灰度值.txt文件 2. 一张部分图片的灰度值.txt文件 3. 部分图片是原图片的一部分 .txt 文件如下: 2.5500000e+...
  • 针对高维特征向量存在的最近邻匹配正确率低的问题, 提出了一种基于SURF和快速近似最近邻搜索的图像匹配算法。首先用Fast-Hessian 检测子进行特征点检测, 并生成SURF特征描述向量; 然后通过快速近似最近邻搜索算法...
  • 通过与随机样本共识(RANSAC),图形变换匹配(GTM)算法以及提出的双向邻域匹配方式比较,采用双向邻域过滤策略的匹配方式能够处理空间顺序匹配时存在的伪同构问题,同时获得更高的召回率和匹配率。
  • 最近邻查找算法kd-tree

    万次阅读 多人点赞 2016-08-12 10:12:01
    海量数据最近邻查找的kd-tree简介  利用Octree,為封閉的3D空間建立一個資料結構來管理空間中的每個元素。如此我們可以在 O(log N) 的時間內對這3D空間進行搜尋。  3D空間可以用Octree,2D空間可以用Quadtree(四...

    http://blog.csdn.net/pipisorry/article/details/52186307

    海量数据最近邻查找的kd-tree简介

            利用Octree,為封閉的3D空間建立一個資料結構來管理空間中的每個元素。如此我們可以在 O(log N) 的時間內對這3D空間進行搜尋。

            3D空間可以用Octree,2D空間可以用Quadtree(四元樹,概念跟Octree一樣)。那麼4D空間呢?5D空間呢? .... 遇到多維度的空間時,要怎麼去建立一個資料結構來有效管理呢?K-d tree 可以解決這個問題,這是由 Bentley [1] 在 1975年所提出的概念並發表在ACM (Association for Computing Machinery)上。
            若有一筆資料 f(x) 佈於 k 維度的空間內,其中 x代表 k 維度的向量,也就是該空間的位置。

    本文的主要目的是讲一下如何创建k-d tree对特征点集合进行数据组织和使用k-d tree来进行最近邻搜索。

            k-d树(k-dimensional),是一种分割k维数据空间的数据结构(对数据点在k维空间中划分的一种数据结构),是一种高维索引树形数据结构。K-D树是二进制空间分割树的特殊的情况。其实,Kd-树是一种平衡二叉树。
        K-d tree 是一個二元樹(binary tree),在此樹中除了樹葉外,每一節點皆代表此k維度空間中的某一點,且能平分某一維度的某個子平面空間。
        K-d tree 也具有平衡的特質(balanced),即任兩樹葉的高度差皆不超過1。

            主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。常用于在大规模的高维数据空间进行最近邻查找(Nearest Neighbor)和近似最近邻查找(Approximate Nearest Neighbor),例如图像检索和识别中的高维图像特征向量的K近邻查找与匹配。

    Kd-Tree与一维二叉查找树之间的区别

            二叉查找树:数据存放在树中的每个结点(根结点、中间结点、叶子结点)中;
    Kd-Tree:数据只存放在叶子结点,而根结点和中间结点存放一些空间划分信息(例如划分维度、划分值);{Note: 后面的示例从示例1起,对应的kdtree都将数据写在了划分结点上,其实只是示意,实际并未如此存储!}

    应用背景

            SIFT算法中做特征点匹配的时候就会利用到k-d树。而特征点匹配实际上就是一个通过距离函数在高维矢量之间进行相似性检索的问题。针对如何快速而准确地找到查询点的近邻,现在提出了很多高维空间索引结构和近似查询的算法,k-d树就是其中一种。
    索引结构中相似性查询有两种基本的方式:一种是范围查询(range searches),另一种是K近邻查询(K-neighbor searches)。范围查询就是给定查询点和查询距离的阈值,从数据集中找出所有与查询点距离小于阈值的数据;K近邻查询是给定查询点及正整数K,从数据集中找到距离查询点最近的K个数据,当K=1时,就是最近邻查询(nearest neighbor searches)。
    特征匹配算子大致可以分为两类。一类是线性扫描法,即将数据集中的点与查询点逐一进行距离比较,也就是穷举,缺点很明显,就是没有利用数据集本身蕴含的任何结构信息,搜索效率较低,第二类是建立数据索引,然后再进行快速匹配。因为实际数据一般都会呈现出簇状的聚类形态,通过设计有效的索引结构可以大大加快检索的速度。索引树属于第二类,其基本思想就是对搜索空间进行层次划分。根据划分的空间是否有混叠可以分为Clipping和Overlapping两种。前者划分空间没有重叠,其代表就是k-d树;后者划分空间相互有交叠,其代表为R树。(这里只介绍k-d树)

    皮皮blog

     

     

    为了更好的引出k-d tree,先讲一讲最近邻搜索。

    最近邻搜索

    最近邻的数学形式的定义

            给定一个多维空间image,把image中的一个向量成为一个样本点或数据点。image中样本点的有限集合称为样本集。给定样本集E,和一个样本点d,d的最近邻就是任何样本点d’∈E满足None-nearer(E,d,d’)。

    None-nearer如下定义:

    image

    上面的公式中距离度量是欧式距离,当然也可以是任何其他Lp-norm。

    image

    其中di是向量d的第i个分量。

    朴素最近邻搜索

            现在再来说最近邻搜索,如何找到一个这样的d’,它离d的距离在E中是最近的。

            很容易想到的一个方法就是线性扫描,也称为穷举搜索,依次计算样本集E中每个样本点到d的距离,然后取最小距离的那个点。这个方法又称为朴素最近邻搜索。当样本集E较大时(在物体识别的问题中,可能有数千个甚至数万个SIFT特征点),显然这种策略是非常耗时的。

    皮皮blog

     

     

    k-d tree的简介及表示

    表示

            因为实际数据一般都会呈现簇状的聚类形态,因此我们想到建立数据索引,然后再进行快速匹配。索引树是一种树结构索引方法,其基本思想是对搜索空间进行层次划分。k-d tree是索引树中的一种典型的方法。

            k-d tree是英文K-dimension tree的缩写,是对数据点在k维空间中划分的一种数据结构。k-d tree实际上是一种二叉树。每个结点的内容如下:

    域名 类型 描述
    dom_elt kd维的向量 kd维空间中的一个样本点
    split 整数 分裂维的序号,也是垂直于分割超面的方向轴序号
    left kd-tree 由位于该结点分割超面左子空间内所有数据点构成的kd-tree
    right kd-tree 由位于该结点分割超面右子空间内所有数据点构成的kd-tree

            样本集E由k-d tree的结点的集合表示,每个结点表示一个样本点,dom_elt就是表示该样本点的向量。该样本点根据结点的分割超平面将样本空间分为两个子空间。左子空间中的样本点集合由左子树left表示,右子空间中的样本点集合由右子树right表示。分割超平面是一个通过点dom_elt并且垂直于split所指示的方向轴的平面。

            举个简单的例子,在二维的情况下,一个样本点可以由二维向量(x,y)表示,其中令x维的序号为0,y维的序号为1。假设一个结点的dom_elt为(7,2) ,split的取值为0,那么分割超面就是x=dom_elt(0)=7,它垂直与x轴且过点(7,2),如下图所示:

    image

    (红线代表分割超平面)

            于是其他数据点的x维(第split=0维)如果小于7,则被分配到左子空间;若大于7,则被分配到右子空间。例如,(5,4)被分配到左子空间,(9,6)被分配到右子空间。如下图所示:

    image

    从上面的表也可以看出k-d tree本质上是一种二叉树,因此k-d tree的构建是一个逐级展开的递归过程。

    并且从这个过程中可知,内部节点都在分割面上,而叶子节点都在某个分割区域中。

    kdtree的构建 过程

    怎样构造一棵Kd-tree?

            对于Kd-tree这样一棵二叉树,我们首先需要确定怎样划分左子树和右子树,即一个K维数据是依据什么被划分到左子树或右子树的。
    在构造1维BST树时,一个1维数据根据其与树的根结点和中间结点进行大小比较的结果来决定是划分到左子树还是右子树,同理,我们也可以按照这样的方式,将一个K维数据与Kd-tree的根结点和中间结点进行比较,只不过不是对K维数据进行整体的比较,而是选择某一个维度Di,然后比较两个K维数在该维度Di上的大小关系,即每次选择一个维度Di来对K维数据进行划分,相当于用一个垂直于该维度Di的超平面将K维数据空间一分为二,平面一边的所有K维数据在Di维度上的值小于平面另一边的所有K维数据对应维度上的值。也就是说,我们每选择一个维度进行如上的划分,就会将K维数据空间划分为两个部分,如果我们继续分别对这两个子K维空间进行如上的划分,又会得到新的子空间,对新的子空间又继续划分,重复以上过程直到每个子空间都不能再划分为止。

    Kd-Tree的构建算法

    (1) 在K维数据集合中选择具有最大方差的维度k,然后在该维度上选择中值m为pivot对该数据集合进行划分,得到两个子集合;同时创建一个树结点node,用于存储<k, m>;
    (2)对两个子集合重复(1)步骤的过程,直至所有子集合都不能再划分为止;如果某个子集合不能再划分时,则将该子集合中的数据保存到叶子结点(leaf node)。

            给定二维数据集合:(2,3), (5,4), (9,6), (4,7), (8,1), (7,2),利用上述算法构建一棵Kd-tree。左图是Kd-tree对应二维数据集合的一个空间划分,右图是构建的一棵Kd-tree。

    1)k-d tree[5]

            把n维特征的观测实例放到n维空间中,k-d tree每次通过某种算法选择一个特征(坐标轴),以它的某一个值作为分界做超平面,把当前所有观测点分为两部分,然后对每一个部分使用同样的方法,直到达到某个条件为止。
    上面的表述中,有几个地方下面将会详细说明:(1)选择特征(坐标轴)的方法  (2)以该特征的哪一个为界 (3)达到什么条件算法结束。

    (1)选择特征的方法

            计算当前观测点集合中每个特征的方差,选择方差最大的一个特征,然后画一个垂直于这个特征的超平面将所有观测点分为两个集合。

    (2)以该特征的哪一个值为界 即垂直选择坐标轴的超平面的具体位置。

            第一种是以各个点的方差的中值(median)为界。这样会使建好的树非常地平衡,会均匀地分开一个集合。这样做的问题是,如果点的分布非常不好地偏斜的,选择中值会造成连续相同方向的分割,形成细长的超矩形(hyperrectangles)。

            替代的方法是计算这些点该坐标轴的平均值,选择距离这个平均值最近的点作为超平面与这个坐标轴的交点。这样这个树不会完美地平衡,但区域会倾向于正方地被划分,连续的分割更有可能在不同方向上发生。

    (3)达到什么条件算法结束

            实际中,不用指导叶子结点只包含两个点时才结束算法。你可以设定一个预先设定的最小值,当这个最小值达到时结束算法。


          图 6  一个k-d tree划分二维空间

            图6中,星号标注的是目标点,我们在k-d tree中找到这个点所处的区域后,依次计算此区域包含的点的距离,找出最近的一个点(黑色点),如果在其他region中还包含更近的点则一定在以这两个点为半径的圆中。假设这个圆如图中所示包含其他区域。先看这个区域兄弟结点对应区域,与圆不重叠;再看其双亲结点的兄弟结点对应区域。从它的子结点对应区域中寻找(图中确实与这个双亲结点的兄弟结点的子结点对应区域重叠了)。在其中找是否有更近的结点。
            k-d tree的优势是可以递增更新。新的观测点可以不断地加入进来。找到新观测点应该在的区域,如果它是空的,就把它添加进去,否则,沿着最长的边分割这个区域来保持接近正方形的性质。这样会破坏树的平衡性,同时让区域不利于找最近邻。我们可以当树的深度到达一定值时重建这棵树。

    [【机器学习】K-means聚类算法初探]

    分裂结点选择程序

            分裂结点的选择通常有多种方法,最常用的是一种方法是:对于所有的样本点,统计它们在每个维上的方差,挑选出方差中的最大值,对应的维就是split域的值。数据方差最大表明沿该维度数据点分散得比较开,这个方向上进行数据分割可以获得最好的分辨率;然后再将所有样本点按其第split维的值进行排序,位于正中间的那个数据点选为分裂结点的dom_elt域。

    每次对子空间的划分时,怎样确定在哪个维度上进行划分?

            最简单的方法就是轮着来,即如果这次选择了在第i维上进行数据划分,那下一次就在第j(j≠i)维上进行划分,例如:j = (i mod k) + 1。想象一下我们切豆腐时,先是竖着切一刀,切成两半后,再横着来一刀,就得到了很小的方块豆腐。可是“轮着来”的方法是否可以很好地解决问题呢?再次想象一下,我们现在要切的是一根木条,按照“轮着来”的方法先是竖着切一刀,木条一分为二,干净利落,接下来就是再横着切一刀,这个时候就有点考验刀法了,如果木条的直径(横截面)较大,还可以下手,如果直径较小,就没法往下切了。因此,如果K维数据的分布像上面的豆腐一样,“轮着来”的切分方法是可以奏效,但是如果K维度上数据的分布像木条一样,“轮着来”就不好用了。因此,还需要想想其他的切法。

            如果一个K维数据集合的分布像木条一样,那就是说明这K维数据在木条较长方向代表的维度上,这些数据的分布散得比较开,数学上来说,就是这些数据在该维度上的方差(invariance)比较大,换句话说,正因为这些数据在该维度上分散的比较开,我们就更容易在这个维度上将它们划分开,因此,这就引出了我们选择维度的另一种方法:最大方差法(max invarince),即每次我们选择维度进行划分时,都选择具有最大方差维度。

    在某个维度上进行划分时,怎样确保在这一维度上的划分得到的两个子集合的数量尽量相等,即左子树和右子树中的结点个数尽量相等?

            假设当前我们按照最大方差法选择了在维度i上进行K维数据集S的划分,此时我们需要在维度i上将K维数据集合S划分为两个子集合A和B,子集合A中的数据在维度i上的值都小于子集合B中。首先考虑最简单的划分法,即选择第一个数作为比较对象(即划分轴,pivot),S中剩余的其他所有K维数据都跟该pivot在维度i上进行比较,如果小于pivot则划A集合,大于则划入B集合。把A集合和B集合分别看做是左子树和右子树,那么我们在构造一个二叉树的时候,当然是希望它是一棵尽量平衡的树,即左右子树中的结点个数相差不大。而A集合和B集合中数据的个数显然跟pivot值有关,因为它们是跟pivot比较后才被划分到相应的集合中去的。好了,现在的问题就是确定pivot了。给定一个数组,怎样才能得到两个子数组,这两个数组包含的元素个数差不多且其中一个子数组中的元素值都小于另一个子数组呢?方法很简单,找到数组中的中值(即中位数,median),然后将数组中所有元素与中值进行比较,就可以得到上述两个子数组。同样,在维度i上进行划分时,pivot就选择该维度i上所有数据的中值,这样得到的两个子集合数据个数就基本相同了。

    kdtree最近邻查找的算法过程

    构建好一棵Kd-Tree后,下面给出利用Kd-Tree进行最近邻查找的算法:

    (1)将查询数据Q从根结点开始,按照Q与各个结点的比较结果向下访问Kd-Tree,直至达到叶子结点。
    其中Q与结点的比较指的是将Q对应于结点中的k维度上的值与m进行比较,若Q(k) < m,则访问左子树,否则访问右子树。达到叶子结点时,计算Q与叶子结点上保存的数据之间的距离,记录下最小距离对应的数据点,记为当前“最近邻点”Pcur和最小距离Dcur。
    (2)进行回溯(Backtracking)操作,该操作是为了找到离Q更近的“最近邻点”。即判断未被访问过的分支里是否还有离Q更近的点,它们之间的距离小于Dcur。
            如果Q与其父结点下的未被访问过的分支之间的距离小于Dcur,则认为该分支中存在离P更近的数据,进入该结点,进行(1)步骤一样的查找过程,如果找到更近的数据点,则更新为当前的“最近邻点”Pcur,并更新Dcur。如果Q与其父结点下的未被访问过的分支之间的距离大于Dcur,则说明该分支内不存在与Q更近的点。
            回溯的判断过程是从下往上进行的,直到回溯到根结点时已经不存在与P更近的分支为止。

    怎样判断未被访问过的树分支Branch里是否还有离Q更近的点?

            从几何空间上来看,就是判断以Q为中心center和以Dcur为半径Radius的超球面(Hypersphere)与树分支Branch代表的超矩形(Hyperrectangle)之间是否相交。
            在实现中,我们可以有两种方式来求Q与树分支Branch之间的距离。第一种是在构造树的过程中,就记录下每个子树中包含的所有数据在该子树对应的维度k上的边界参数[min, max];第二种是在构造树的过程中,记录下每个子树所在的分割维度k和分割值m,(k, m),Q与子树的距离则为|Q(k) - m|。

    kdtree算法实现

    构建kd-tree算法的伪代码

    1 构建k-d树的伪码

    算法:构建k-d树(createKDTree)

    输入:数据点集Data-set和其所在的空间Range

    输出:Kd,类型为k-d tree

    1.If Data-set为空,则返回空的k-d tree

    2.调用节点生成程序:

    (1)确定split域:对于所有描述子数据(特征矢量),统计它们在每个维上的数据方差。以SURF特征为例,描述子为64维,可计算64个方差。挑选出最大值,对应的维就是split域的值。数据方差大表明沿该坐标轴方向上的数据分散得比较开,在这个方向上进行数据分割有较好的分辨率;

    (2)确定Node-data域:数据点集Data-set按其第split域的值排序。位于正中间的那个数据点被选为Node-data。此时新的Data-set' = Data-set\Node-data(除去其中Node-data这一点)。

    3.dataleft = {d属于Data-set' && d[split] ≤ Node-data[split]}

    Left_Range = {Range && dataleft}
    dataright = {d属于Data-set' && d[split] > Node-data[split]}

    Right_Range = {Range && dataright}

    4.left = 由(dataleft,Left_Range)建立的k-d tree,即递归调用createKDTree(dataleft,Left_Range)。
    并设置left的parent域为Kd;

    right = 由(dataright,Right_Range)建立的k-d tree,即调用createKDTree(dataright,Right_Range)。
    并设置right的parent域为Kd。

    2 算法:createKDTree 构建一棵k-d tree
    输入:exm_set 样本集
    输出 : Kd, 类型为kd-tree
    1. 如果exm_set是空的,则返回空的kd-tree
    2.调用分裂结点选择程序(输入是exm_set),返回两个值
    dom_elt:= exm_set中的一个样本点
    split := 分裂维的序号
    3.exm_set_left = {exm∈exm_set – dom_elt && exm[split] <= dom_elt[split]}
    exm_set_right = {exm∈exm_set – dom_elt && exm[split] > dom_elt[split]}
    4.left = createKDTree(exm_set_left)
    right = createKDTree(exm_set_right)

    k-d tree的最近邻搜索算法

            如前所述,在k-d tree树中进行数据的k近邻搜索是特征匹配的重要环节,其目的是检索在k-d tree中与待查询点距离最近的k个数据点。

            最近邻搜索是k近邻的特例,也就是1近邻。将1近邻改扩展到k近邻非常容易。下面介绍最简单的k-d tree最近邻搜索算法。

            基本的思路很简单:首先通过二叉树搜索(比较待查询节点和分裂节点的分裂维的值,小于等于就进入左子树分支,等于就进入右子树分支直到叶子结点),顺着“搜索路径”很快能找到最近邻的近似点,也就是与待查询点处于同一个子空间的叶子结点;然后再回溯搜索路径,并判断搜索路径上的结点的其他子结点空间中是否可能有距离查询点更近的数据点,如果有可能,则需要跳到其他子结点空间中去搜索(将其他子结点加入到搜索路径)。重复这个过程直到搜索路径为空。下面给出k-d tree最近邻搜索的伪代码:

    算法:kdtreeFindNearest /* k-d tree的最近邻搜索 */
    输入:Kd /* k-d tree类型*/
    target /* 待查询数据点 */
    输出 : nearest /* 最近邻数据结点 */
    dist /* 最近邻和查询点的距离 */
    1. 如果Kd是空的,则设dist为无穷大返回
    2. 向下搜索直到叶子结点
    pSearch = &Kd
    while(pSearch != NULL)  {
    pSearch加入到search_path中;
    if(target[pSearch->split] <= pSearch->dom_elt[pSearch->split]) /* 如果小于就进入左子树 */
    {
    pSearch = pSearch->left;
    }
    else  {
    pSearch = pSearch->right;
    }
    }
    取出search_path最后一个赋给nearest
    dist = Distance(nearest, target);
    3. 回溯搜索路径
    while(search_path不为空)  {
    取出search_path最后一个结点赋给pBack
    if(pBack->left为空 && pBack->right为空) /* 如果pBack为叶子结点 */
    {
    if( Distance(nearest, target) > Distance(pBack->dom_elt, target) )  {
    nearest = pBack->dom_elt;
    dist = Distance(pBack->dom_elt, target);
    }
    }
    else {
    s = pBack->split;
    if( abs(pBack->dom_elt[s] - target[s]) < dist) /* 如果以target为中心的圆(球或超球),半径为dist的圆与分割超平面相交, 那么就要跳到另一边的子空间去搜索 */
    {
    if( Distance(nearest, target) > Distance(pBack->dom_elt, target) )  {
    nearest = pBack->dom_elt;
    dist = Distance(pBack->dom_elt, target);
    }
    if(target[s] <= pBack->dom_elt[s]) /* 如果target位于pBack的左子空间,那么就要跳到右子空间去搜索 */
    pSearch = pBack->right;
    else
    pSearch = pBack->left; /* 如果target位于pBack的右子空间,那么就要跳到左子空间去搜索 */
    if(pSearch != NULL)
    pSearch加入到search_path中
    }
    }
    }

    k-d tree的构建过程及搜索实例

    示例1

            假设样本集为:{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}。构建过程如下:

    (1)确定split域,6个数据点在x,y维度上的数据方差分别为39, 28.63。在x轴上方差最大,所以split域值为0(x维的序号为0)

    (2)确定分裂节点,根据x维上的值将数据排序,则6个数据点再排序后位于中间的那个数据点为(7,2),该结点就是分割超平面就是通过(7,2)并垂直于split=0(x)轴的直线x=7

    (3)左子空间和右子空间,分割超面x=7将整个空间氛围两部分,x<=7的部分为左子空间,包含3个数据点{(2,3), (5,4), (4,7)};另一部分为右子空间,包含2个数据点{(9,6), (8,1)}。如下图所示

    (4)分别对左子空间中的数据点和右子空间中的数据点重复上面的步骤构建左子树和右子树直到经过划分的子样本集为空。下面的图从左至右从上至下显示了构建这棵二叉树的所有步骤:

    imageimageimageimage

    示例2

            假设有六个二维数据点 = {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},数据点位于二维空间中。为了能有效的找到最近邻,Kd-树采用分而治之的思想,即将整个空间划分为几个小部分。六个二维数据点生成的Kd-树的图为:

    2D 3D KD-tree

    示例3

            假设我们的k-d tree就是上面通过样本集{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}创建的。将上面的图转化为树形图的样子如下:

    image

            我们来查找点(2.1,3.1),在(7,2)点测试到达(5,4),在(5,4)点测试到达(2,3),然后search_path中的结点为<(7,2), (5,4), (2,3)>,从search_path中取出(2,3)作为当前最佳结点nearest, dist为0.141;

    然后回溯至(5,4),以(2.1,3.1)为圆心,以dist=0.141为半径画一个圆,并不和超平面y=4相交,如下图,所以不必跳到结点(5,4)的右子空间去搜索,因为右子空间中不可能有更近样本点了。

    image

    于是在回溯至(7,2),同理,以(2.1,3.1)为圆心,以dist=0.141为半径画一个圆并不和超平面x=7相交,所以也不用跳到结点(7,2)的右子空间去搜索。

    至此,search_path为空,结束整个搜索,返回nearest(2,3)作为(2.1,3.1)的最近邻点,最近距离为0.141。

     示例4

            再举一个稍微复杂的例子,我们来查找点(2,4.5),在(7,2)处测试到达(5,4),在(5,4)处测试到达(4,7),然后search_path中的结点为<(7,2), (5,4), (4,7)>,从search_path中取出(4,7)作为当前最佳结点nearest, dist为3.202;

    然后回溯至(5,4),以(2,4.5)为圆心,以dist=3.202为半径画一个圆与超平面y=4相交,如下图,所以需要跳到(5,4)的左子空间去搜索。所以要将(2,3)加入到search_path中,现在search_path中的结点为<(7,2), (2, 3)>;另外,(5,4)与(2,4.5)的距离为3.04 < dist = 3.202,所以将(5,4)赋给nearest,并且dist=3.04。

    image

    回溯至(2,3),(2,3)是叶子节点,直接平判断(2,3)是否离(2,4.5)更近,计算得到距离为1.5,所以nearest更新为(2,3),dist更新为(1.5)

    回溯至(7,2),同理,以(2,4.5)为圆心,以dist=1.5为半径画一个圆并不和超平面x=7相交, 所以不用跳到结点(7,2)的右子空间去搜索。

    至此,search_path为空,结束整个搜索,返回nearest(2,3)作为(2,4.5)的最近邻点,最近距离为1.5。

            两次搜索的返回的最近邻点虽然是一样的,但是搜索(2, 4.5)的过程要复杂一些,因为(2, 4.5)更接近超平面。研究表明,当查询点的邻域与分割超平面两侧的空间都产生交集时,回溯的次数大大增加。最坏的情况下搜索N个结点的k维kd-tree所花费的时间为:

    image

    复杂度分析

    对于拥有n个已知点的kD-Tree,其复杂度如下:
    构建:O(log2n)
    插入:O(log n)
    删除:O(log n)
    查询:O(n1-1/k+m)        其中m为每次要搜索的最近点个数

    把最邻近点算法扩展成K-最邻近点算法

    ...

    k-d tree的扩展

    Kd-tree with BBF

            由于大量回溯会导致kd-tree最近邻搜索的性能大大下降,因此研究人员也提出了改进的k-d tree近邻搜索。

            其中一个比较著名的就是 Best-Bin-First,它通过设置优先级队列和运行超时限定来获取近似的最近邻,有效地减少回溯的次数。
            Kd-tree在维度较小时(例如:K≤30),算法的查找效率很高,然而当Kd-tree用于对高维数据(例如:K≥100)进行索引和查找时,就面临着维数灾难(curse of dimension)问题,查找效率会随着维度的增加而迅速下降。通常,实际应用中,我们常常处理的数据都具有高维的特点,例如在图像检索和识别中,每张图像通常用一个几百维的向量来表示,每个特征点的局部特征用一个高维向量来表征(例如:128维的SIFT特征)。因此,为了能够让Kd-tree满足对高维数据的索引,Jeffrey S. Beis和David G. Lowe提出了一种改进算法——Kd-tree with BBF(Best Bin First),该算法能够实现近似K近邻的快速搜索,在保证一定查找精度的前提下使得查找速度较快。
            在介绍BBF算法前,我们先来看一下原始Kd-tree是为什么在低维空间中有效而到了高维空间后查找效率就会下降。在原始kd-tree的最近邻查找算法中(第一节中介绍的算法),为了能够找到查询点Q在数据集合中的最近邻点,有一个重要的操作步骤:回溯,该步骤是在未被访问过的且与Q的超球面相交的子树分支中查找可能存在的最近邻点。随着维度K的增大,与Q的超球面相交的超矩形(子树分支所在的区域)就会增加,这就意味着需要回溯判断的树分支就会更多,从而算法的查找效率便会下降很大。
            一个很自然的思路是:既然kd-tree算法在高维空间中是由于过多的回溯次数导致算法查找效率下降的话,我们就可以限制查找时进行回溯的次数上限,从而避免查找效率下降。这样做有两个问题需要解决:1)最大回溯次数怎么确定?2)怎样保证在最大回溯次数内找到的最近邻比较接近真实最近邻,即查找准确度不能下降太大。

    [Kd Tree算法原理和开源实现代码]*

    [Kd-tree with BBF]

    [k-d tree算法的研究]*

    [KD Tree]

    [转载:Kd-Tree算法原理和开源实现代码]

    [百度百科 kd-tree]

    [从K近邻算法、距离度量谈到KD树、SIFT+BBF算法]*

     

    K值的选择

            除了上述1.2节如何定义邻居的问题之外,还有一个选择多少个邻居,即K值定义为多大的问题。不要小看了这个K值选择问题,因为它对K近邻算法的结果会产生重大影响。如李航博士的一书「统计学习方法」上所说:

            如果选择较小的K值,就相当于用较小的领域中的训练实例进行预测,“学习”近似误差会减小,只有与输入实例较近或相似的训练实例才会对预测结果起作用,与此同时带来的问题是“学习”的估计误差会增大,换句话说,K值的减小就意味着整体模型变得复杂,容易发生过拟合;
            如果选择较大的K值,就相当于用较大领域中的训练实例进行预测,其优点是可以减少学习的估计误差,但缺点是学习的近似误差会增大。这时候,与输入实例较远(不相似的)训练实例也会对预测器作用,使预测发生错误,且K值的增大就意味着整体的模型变得简单。
            K=N,则完全不足取,因为此时无论输入实例是什么,都只是简单的预测它属于在训练实例中最多的累,模型过于简单,忽略了训练实例中大量有用信息。
            在实际应用中,K值一般取一个比较小的数值,例如采用交叉验证法(简单来说,就是一部分样本做训练集,一部分做测试集)来选择最优的K值。

    k-d tree的实现库

    伪代码:

    [KD-tree Implement]

    python:

    [scipy.spatial.KDTree][scipy.spatial]

    [KD-tree的原理以及构建与查询操作的python实现]

    c/c++:

    [kdtree A simple C library for working with KD-Trees]

    [http://code.google.com/p/kdtree/]

    [https://github.com/sdeming/kdtree]

    java:

    [KD-Tree Implementation in Java and C#]

    from: http://blog.csdn.net/pipisorry/article/details/52186307

    ref: [wiki:http://en.wikipedia.org/wiki/K-d_tree]

    [Kd Tree算法原理和开源实现代码]*

    [k-d tree算法原理及实现]**

    [KD tree]**

    Paper
    [1] Multidimensional binary search trees used for associative searching*
    [2] Shape indexing using approximate nearest-neighbour search in high-dimensional spaces
    Tutorial
    [1] [An intoductory tutorial on kd-trees Andrew W.Moore]
    [2] Nearest-Neighbor Methods in Learning and Vision: Theory and Practice

     

    展开全文
  • 主要介绍了详解opencv Python特征检测及K-最近邻匹配,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • icp点云匹配迭代最近邻算法

    千次阅读 2018-10-21 23:04:00
    1.icp算法能够使两个不同坐标系下的点集匹配到一个坐标系中,这个过程就是配准,配准的操作就是找到从坐标系1变换到坐标系2的刚性变换。 2.icp的本质就是配准,但有不同的配准方案,icp算法本质是基于最小二乘的...

    一、含义:
    1.icp算法能够使两个不同坐标系下的点集匹配到一个坐标系中,这个过程就是配准,配准的操作就是找到从坐标系1变换到坐标系2的刚性变换。
    2.icp的本质就是配准,但有不同的配准方案,icp算法本质是基于最小二乘的最优配准方法。该方法重复进行选择对应关系对,计算最优刚体变换,直到满足正确配准的收敛精度要求。
    3.icp算法的目的就是找到待匹配点云数据与参考点云数据之间的旋转参数R和平移参数T,使得两点数据之间满足某种度量准则下的最优匹配。
    4.每次操作的都是目标点集,使目标点集不断靠近参考点集,因此求R和T也是每次考虑目标点集中每个点在参考点集中的最近点;
    二、流程图:
    在这里插入图片描述
    假设给两个三维点集x1和x2,ICP方法的配准方案步骤如下[1]:
    第一步,计算x2中每一个点在x1点集中的最近点;
    第二步,求得使上述对应点对平均距离最小的刚体变换,求得平移参数和旋转参数;
    第三步,对x2使用上一步求得的平移参数和旋转参数,得到新点集;
    第四步,如果新的变换点集和参考点集满足两点集的平均距离小于某一给定阈值,则停止迭代计算,否则新的变换点集作为新的x2继续迭代,直到达到目标函数的要求。
    三、注意事项:
    什么是目标点集,什么是参考点集?
    目标点集就是你每次不断操作的点集,每次不断移动,使其不断靠近参考点集,每次求R和T时是在参考点集中查找和目标点集最近的点,操作的对象目标点集。
    四、程序代码:
    在网上参考了很多版本,都不太适合新手入门,本人写了一个比较简单的代码,希望与大家共同交流学习:

    clc;
    clear all;
    clear all;
    %产生点集1
    x1=1:0.01:2;
    sample=randn(1,length(x1));
    y1=10*x1+2*sample;
    pointcloud1=[x1;y1];
    theta=pi/3;
    R=[cos(theta) -sin(theta);
           sin(theta) cos(theta) ];
    T =[4;5] *ones(1,length(pointcloud1(1,:))) ;
    pointcloud2=R*pointcloud1+T;
    sourch_point=pointcloud1;%参考点云
    desti_point=pointcloud2;%目标点云
    error=1;%初始误差
    nit=0;%计数
    Iter=20;%最大迭代次数
    %目标点云不断向参考点云靠近
    %可认为初始R为eyes(2);
    %和初始平动t=[0;0];
    %没有任何平动或者移动
    while error>0.01
    	index=[];
    	nit=nit+1;
    	if nit>iter
    		break;
    	end
    	for i=1:length(desti_point(1,:))%为每一个目标点云中的点寻找对应点
    		dx=(source_point-repmat(desti_point(:,i),1,length(source_point(1,:))));
    		dist=sqrt(dx(1,:).^2+dx(2,:).^2);
    		[dist,ii]=min(dist);
    		index=[index;;ii];
    		error=error+dist
    	end
    	source_point_part=source_point(:,index);
    	%求质心
    	u_sour_point=(sum(source_point_part,2))/length(source_point_part(1,:));
    	u_dest_point=(sum(desti_point,2))/length(source_point_part(1,:));
    	%去中心化
    	source_point_center=source_point_part-u_sour_point*ones(1,length(source_point_part(1,:)));
    	desti_point_center=desti_point-u_dest_point*ones(1,length(desti_point(1,:)));
    	%求W
    	W=source_point_center*desti_point_center';
    	%SVD分解
    	[U,S,V]=svd(W);
    	%求R和t
    	R=U*V';
    	t=u_sour_point-R*u_dest_point;
    	%变换后的点集
    	desti_point=R*desti_point+t*ones(1,length(desti_point(1,:)));
    	%画图观察变换后的目标点集
    	figure;
    	plot(pointcloud1(1,:),pointcloud1(2,:),'r.');
    	hold on;
    	plot(pointcloud2(1,:),pointcloud2(2,:),'b.');
    	hold on;
    	plot(desti_point(1,:),desti_point(2,:),'y.');
    	error=1/length(desti_point(1,:))*sum(sum(((source_point_part-desti_point).^2),2),1);
    end		
    

    五、程序运行结果:
    结果图:
    在这里插入图片描述
    红色为参考点云,蓝色为目标点云,黄色为最终经过不断旋转和移动的目标点云
    参考文献:
    [1]:https://www.cnblogs.com/sddai/p/6129437.html

    展开全文
  • 最近邻算法

    2018-12-21 14:18:00
     kNN算法全程是k-最近邻算法(k-Nearest Neighbor)  kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数数以一个类型别,则该样本也属于这个类别,并具有该类别上样本的特征。该方法在确定...

    1.什么是最近邻是什么?

      kNN算法全程是k-最近邻算法(k-Nearest Neighbor)

      kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数数以一个类型别,则该样本也属于这个类别,并具有该类别上样本的特征。该方法在确定分类决策上,只依据最近邻的一个或者几个样本的类别来决定待分样本所属的类别。

    下面举例说明:

    即使不知道未知电影属于哪个类型,我们也可以通过某种方式计算,如下图

    现在,我们得到了样本集中与未知电影的距离,按照距离的递增顺序,可以找到k个距离最近的电影,假设k=3,则三个最靠近的电影是he is not realy into Dudes,Beautiful women, California man , kNN 算法按照距离最近的三部电影类型决定未知电影的类型,这三部都是爱情片,所以未知电影的类型也是爱情片。

    2:kNN算法的一般流程

    • step.1---初始化距离为最大值
    • step.2---计算未知样本和每个训练样本的距离dist
    • step.3---得到目前K个最邻近样本中的最大距离maxdist
    • step.4---如果dist小于maxdist, 则将训练样本作为K-最近邻样本
    • step.5---重复步骤2,3,4,直到未知样本和所有训练样本的距离都算完
    • step.6---统计K-最近邻样本中每个类标号出现的次数
    • step.7---出现频率最大的类标号最为未知样本的类标号

    3.距离公式

    在KNN算法中,通过计算对象间距离作为各个对象之间的非相似性指标,避免了对象之间的匹配问题,在这里距离一般使用欧式距离或者曼哈顿距离:

     对应代码如下

    #  kNN算法全称是k-最近邻算法(K-Nearest Neighbor)
    from numpy import *
    import operator
    
    # 创建数据函数
    def createDataSet():
        """ 创建数据集,array 创建数组
        array数组内依次是打斗次数, 接吻次数
        group小组, labels标签"""
        group = array([[3, 104], [2, 100], [1, 81], [101, 10], [99, 5], [98, 2]])
        labels = ["爱情片", "爱情片", "爱情片", "动作片", "动作片", "动作片"]
        return group, labels
    
    # 归类函数
    def classify(inX, dataSet, labels, k):
        """ 获取维度,
         inX 待测目标的数据,
         dataSet 样本数据,
         labels 标签,
         k 设置比较邻近的个数"""
        dataSetSize = dataSet.shape[0]  # 训练数据集数据 行数
        print(dataSetSize)
        print(tile(inX, (dataSetSize, 1)))
    
        diffMat = tile(inX, (dataSetSize, 1)) - dataSet  # 测试数据,样本之间的数据 矩阵偏差
        print(diffMat)
    
        sqDiffMat = diffMat**2  # 平方计算,得出每个距离的值
        print(sqDiffMat)
    
        sqDistance = sqDiffMat.sum(axis=1)  # 输出每行的值
        print(sqDistance)
    
        distances = sqDistance**0.5  # 开方计算
        print(distances)
    
        sortedDistances = distances.argsort()  # 排序 按距离从小到大 输出索引
        print(sortedDistances)
    
        classCount = {}
        for i in range(k):
            voteIlabel = labels[sortedDistances[i]] + 1.0 # 按照排序,获取k个对应的标签
            classCount[voteIlabel] = classCount.get(voteIlabel, 0)  # 在字典中添加距离最近的k个对应标签
        sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    
        return sortedClassCount[0][0]
    
    group, labels = createDataSet()
    res = classify([18, 90], group, labels, 3)
    print(res)

     运行结果:

     

    转载于:https://www.cnblogs.com/daofaziran/p/10155475.html

    展开全文
  • 快速近似最近邻算法by Braden Riggs and George Williams (gwilliams@gsitechnology.com) Braden Riggs和George Williams(gwilliams@gsitechnology.com) Whether you are new to the field of data science or a ...

    快速近似最近邻算法

    by Braden Riggs and George Williams (gwilliams@gsitechnology.com)

    Braden Riggs和George Williams(gwilliams@gsitechnology.com)

    Whether you are new to the field of data science or a seasoned veteran, you have likely come into contact with the term, ‘nearest-neighbor search’, or, ‘similarity search’. In fact, if you have ever used a search engine, recommender, translation tool, or pretty much anything else on the internet then you have probably made use of some form of nearest-neighbor algorithm. These algorithms, the ones that permeate most modern software, solve a very simple yet incredibly common problem. Given a data point, what is the closest match from a large selection of data points, or rather what point is most like the given point? These problems are “nearest-neighbor” search problems and the solution is an Approximate Nearest Neighbor algorithm or ANN algorithm for short.

    无论您是数据科学领域的新手还是经验丰富的资深人士,您都可能接触过“最近邻居搜索”或“相似搜索”一词。 实际上,如果您曾经使用搜索引擎,推荐器,翻译工具或互联网上的几乎所有其他工具,那么您可能已经在使用某种形式的最近邻居算法。 这些算法已渗透到大多数现代软件中,解决了一个非常简单但难以置信的常见问题。 给定一个数据点,从大量数据点中选择最接近的匹配是什么 ,或者最像给定点的是哪个点? 这些问题是“最近邻居”搜索 问题和解决方案是简称为“ 近似最近邻居”算法或ANN算法。

    Approximate nearest-neighbor algorithms or ANN’s are a topic I have blogged about heavily, and with good reason. As we attempt to optimize and solve the nearest-neighbor challenge, ANN’s continue to be at the forefront of elegant and optimal solutions to these problems. Introductory Machine learning classes often include a segment about ANN’s older brother kNN, a conceptually simpler style of nearest-neighbor algorithm that is less efficient but easier to understand. If you aren’t familiar with kNN algorithms, they essentially work by classifying unseen points based on “k” number of nearby points, where the vicinity or distance of the nearby points are calculated by distance formulas such as euclidian distance.

    近似最近邻算法或ANN是我在博客上大量谈论的主题,并且有充分的理由。 在我们尝试优化和解决最邻近的挑战时,ANN始终站在解决这些问题的优雅且最优的解决方案的最前沿。 机器学习入门课程通常包括有关ANN的哥哥kNN的部分,kNN是概念上更简单的近邻算法样式,效率较低但更易于理解。 如果您不熟悉kNN算法,则它们实际上是通过基于“ k”个邻近点数对看不见的点进行分类来工作的,其中邻近点的邻近度或距离是通过诸如欧几里得距离之类的距离公式来计算的。

    ANN’s work similarly but with a few more techniques and strategies that ensure greater efficiency. I go into more depth about these techniques in an earlier blog here. In this blog, I describe an ANN as:

    ANN的工作与此类似,但是有更多的技术和策略可以确保更高的效率。 我在这里先前的博客中对这些技术进行了更深入的介绍。 在此博客中, 我将ANN描述为

    A faster classifier with a slight trade-off in accuracy, utilizing techniques such as locality sensitive hashing to better balance speed and precision.- Braden Riggs, How to Benchmark ANN Algorithms

    一种更快的分类器,在精度上会稍有取舍,利用诸如位置敏感的哈希值之类的技术来更好地平衡速度和精度。- Braden Riggs,如何对ANN算法进行基准测试

    The problem with utilizing the power of ANNs for your own projects is the sheer quantity of different implementations open to the public, each having their own benefits and disadvantages. With so many choices available how can you pick which is right for your project?

    在您自己的项目中使用ANN的功能所带来的问题是,向公众开放的不同实现的数量庞大,每个实现都有其自身的优缺点。 有这么多的选择,您如何选择最适合您的项目?

    Bernhardsson和ANN救援基准: (Bernhardsson and ANN-Benchmarks to the Rescue:)

    Image for post
    For this project, we need a little help from the experts. Photo by Tra Nguyen on Unsplash
    对于这个项目,我们需要专家的帮助。 Tra NguyenUnsplash拍摄的照片

    We have established that there are a range of ANN implementations available for use. However, we need a way of picking out the best of the best, the cream of the crop. This is where Aumüller, Bernhardsson, and Faithfull’s paper ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms and its corresponding GitHub repository comes to our rescue.

    我们已经建立了一系列可供使用的ANN实现。 但是,我们需要一种方法来挑选最好的农作物。 这是Aumüller,Bernhardsson和Faithfull的论文ANN基准:近似最近邻算法的基准工具 并且其相应的GitHub存储库可为我们提供帮助。

    The project, which I have discussed in the past, is a great starting point for choosing the algorithm that is the best fit for your project. The paper uses some clever techniques to evaluate the performance of a number of ANN implementations on a selection of datasets. It has these ANN algorithms solve nearest-neighbor queries to determine the accuracy and efficiency of the algorithm at different parameter combinations. The algorithm uses these queries to locate the 10 nearest data points to the queried point and evaluates how close each point is to the true neighbor, which is a metric called Recall. This is then scaled against how quickly the algorithm was able to accomplish its goal, which it called Queries per Second. This metric provides a great reference for determining which algorithms may be most preferential for you and your project.

    我过去讨论过的项目是选择最适合您项目的算法的一个很好的起点。 本文使用一些巧妙的技术来评估多种ANN实施对所选数据集的性能。 它具有这些ANN算法来解决最近邻居查询,以确定算法在不同参数组合下的准确性和效率。 该算法使用这些查询来定位最接近查询点的10个数据点,并评估每个点与真正邻居的接近程度,这是一个称为“召回率”的度量。 然后,根据算法能够实现其目标的速度(称为“每秒查询”)进行缩放。 该指标为确定哪种算法可能最适合您和您的项目提供了很好的参考。

    Image for post
    Screenshot from an earlier blog where I recreated Bernhardsson’s results benchmarking ANN algorithms on the Gloce-25-angular NLP dataset. Read more here. Image by Author.
    我以前的博客中的屏幕快照,在该博客中我重新创建了Bernhardsson的结果,该结果对Gloce-25角NLP数据集的ANN算法进行了基准测试。 在这里 阅读更多 。 图片由作者提供。

    Part of conducting this experiment requires picking the algorithms we want to test, and the dataset we want to perform the queries on. Based off of the experiments I have conducted on my previous blogs, narrowing down the selection of algorithms wasn’t difficult. In Bernhardsson’s original project he includes 18 algorithms. Given the performance I had seen in my first blog, using the glove-25 angular natural language dataset, there are 9 algorithms worth considering for our benchmark experiment. This is because some algorithms perform so slowly and so poorly that they aren’t even worth considering in this experiment. The algorithms selected are:

    进行此实验的一部分需要选择我们要测试的算法,以及我们要对其执行查询的数据集。 根据我在以前的博客上进行的实验,缩小算法的选择范围并不困难。 在Bernhardsson的原始项目中,他包括18种算法。 鉴于我在第一个博客中看到的性能,使用了Gloves-25角度自然语言数据集,有9种算法值得我们进行基准测试。 这是因为某些算法的执行速度如此之慢且如此差,以至于在本实验中甚至都不值得考虑。 选择的算法是:

    • Annoy: Spotify's “Approximate Nearest Neighbors Oh Yeah” ANN implementation.

      烦恼: Spotify的 “哦,是,最近的邻居” ANN实现。

    • Faiss: The suite of algorithms Facebook uses for large dataset similarity search including Faiss-lsh, Faiss-hnsw, and Faiss-ivf.

      Faiss: Facebook用于大型数据集相似性搜索的算法套件,包括Faiss-lshFaiss-hnswFaiss-ivf

    • Flann: Fast Library for ANN.

      Flann: ANN的快速库。

    • HNSWlib: Hierarchical Navigable Small World graph ANN search library.

      HNSWlib:分层可导航小世界图ANN搜索库。

    • NGT-panng: Yahoo Japan’s Neighborhood Graph and Tree for Indexing High-dimensional Data.

      NGT-panng: Yahoo Japan的邻域图和树,用于索引高维数据。

    • Pynndescent: Python implementation of Nearest Neighbor Descent for k-neighbor-graph construction and ANN search.

      Pynndescent:用于k邻域图构建和ANN搜索的Nearest Neighbor Descent的Python实现。

    • SW-graph(nmslib): Small world graph ANN search as part of the non-metric space library.

      SW-graph(nmslib):小世界图ANN搜索,作为非度量空间库的一部分。

    In addition to the algorithms, it was important to pick a dataset that would help distinguish the optimal ANN implementations from the not so optimal ANN implementations. For this task, we chose 1% — or a 10 million vector slice — of the gargantuan Deep-1-billion dataset, a 96 dimension computer vision training dataset. This dataset is large enough for inefficiencies in the algorithms to be accentuated and provide a relevant challenge for each one. Because of the size of the dataset and the limited specification of our hardware, namely the 64GBs of memory, some algorithms were unable to fully run to an accuracy of 100%. To help account for this, and to ensure that background processes on our machine didn’t interfere with our results, each algorithm and all of the parameter combinations were run twice. By doubling the number of benchmarks conducted, we were able to average between the two runs, helping account for any interruptions on our hardware.

    除算法外,重要的是选择一个有助于区分最佳ANN实现与非最佳ANN实现的数据集。 为此,我们选择了庞大的Deep-billion数据集(96维计算机视觉训练数据集)的1%(即一千万个矢量切片)。 该数据集足够大,可以突出算法的低效率,并为每个算法带来相关挑战。 由于数据集的大小和我们硬件的有限规格(即64GB内存),某些算法无法完全运行到100%的精度。 为了解决这个问题,并确保我们机器上的后台进程不会干扰我们的结果,每种算法和所有参数组合都运行两次。 通过将执行的基准测试数量加倍,我们可以在两次运行之间求平均值,从而帮助解决硬件上的任何中断。

    This experiment took roughly 11 days to complete but yielded some helpful and insightful results.

    该实验大约花费了11天的时间,但得出了一些有益而有见地的结果。

    我们发现了什么? (What did we find?)

    After the exceptionally long runtime, the experiment completed with only three algorithms failing to fully reach an accuracy of 100%. These algorithms were Faiss-lsh, Flann, and NGT-panng. Despite these algorithms not reaching perfect accuracy, their results are useful and indicate where the algorithm may have been heading if we had experimented with more parameter combinations and didn't exceed memory usage on our hardware.

    经过异常长的运行时间后,该实验仅用三种算法就无法完全达到100%的精度。 这些算法是Faiss-lshFlannNGT-panng 。 尽管这些算法没有达到理想的精度,但是它们的结果还是有用的,它们表明如果我们尝试了更多的参数组合并且未超过硬件上的内存使用量,该算法可能会前进。

    Before showing off the results, let’s quickly discuss how we are presenting these results and what terminology you need to understand. On the y-axis, we have Queries per Second or QPS. QPS quantifies the number of nearest-neighbor searches that can be conducted in a second. This is sometimes referred to as the inverse ‘latency’ of the algorithm. More precisely QPS is a bandwidth measure and is inversely proportional to the latency. As the query time goes down, the bandwidth will increase. On the x-axis, we have Recall. In this case, Recall essentially represents the accuracy of the function. Because we are finding the 10 nearest-neighbors of a selected point, the Recall score takes the distances of the 10 nearest-neighbors our algorithms computed and compares them to the distance of the 10 true nearest-neighbors. If the algorithm selects the correct 10 points it will have a distance of zero from the true values and hence a Recall of 1. When using ANN algorithms we are constantly trying to maximize both of these metrics. However, they often improve at each other’s expense. When you speed up your algorithm, thereby improving latency, it becomes less accurate. On the other hand, when you prioritize its accuracy, thereby improving Recall, the algorithm slows down.

    在展示结果之前,让我们快速讨论一下我们如何呈现这些结果以及您需要了解哪些术语。 在y轴上,我们有每秒查询数或QPS。 QPS量化了每秒可以进行的最近邻居搜索的次数。 有时将其称为算法的逆“潜伏期”。 更准确地说,QPS是带宽量度,与延迟成反比。 随着查询时间的减少,带宽将增加。 在x轴上,我们有Recall 。 在这种情况下,调用实质上代表了函数的准确性。 由于我们正在查找选定点的10个最近邻居,因此Recall分数将采用我们的算法计算出的10个最近邻居的距离,并将它们与10个真实最近邻居的距离进行比较。 如果该算法选择了正确的10个点,则它与真实值的距离为零,因此召回率为1。使用ANN算法时,我们一直在不断尝试使这两个指标最大化。 但是,它们通常会以互相牺牲为代价而有所改善。 当您加快算法速度从而改善延迟时,它的准确性就会降低。 另一方面,当您优先考虑其准确性从而提高查全率时,该算法会变慢。

    Pictured below is the plot of Queries Performed per Second, over the Recall of the algorithm:

    下图是算法调用每秒执行查询的图:

    Image for post
    The effectiveness of each algorithm as evaluated by Queries per Second which is scaled logarithmically and Recall (accuracy). The further up and to the right the algorithm’s line is, the better said algorithm performed. Image by Author.
    通过每秒查询数评估的每种算法的有效性,该算法的对数和查全率(准确度)均按比例缩放。 该算法的行越靠右,则该算法执行得越好。 图片由作者提供。

    As evident by the graph above there were some clear winners and some clear losers. Focusing on the winners, we can see a few algorithms that really stand out, namely HNSWlib (yellow) and NGT-panng (red) both of which performed at a high accuracy and a high speed. Even though NGT never finished, the results do indicate it was performing exceptionally well prior to a memory-related failure.

    从上图可以明显看出,有一些明显的赢家和一些明显的输家。 着眼于获胜者,我们可以看到一些真正脱颖而出的算法,即HNSWlib(黄色)和NGT-panng(红色),它们均以高精度和高速执行。 尽管NGT从未完成,但结果确实表明它在与内存相关的故障之前表现出色。

    So given these results, we now know which algorithms to pick for our next project right?

    因此,鉴于这些结果,我们现在知道为下一个项目选择哪种算法对吗?

    Unfortunately, this graph doesn’t depict the full story when it comes to the efficiency and accuracy of these ANN implementations. Whilst HNSWlib and NGT-panng can perform quickly and accurately, that is only after they have been built. “Build time” refers to the length of time that is required for the algorithm to construct its index and begin querying neighbors. Depending on the implementation of the algorithm, build time can be a few minutes or a few hours. Graphed below is the average algorithm build time for our benchmark excluding Faiss-HNSW which took 1491 minutes to build (about 24 hours):

    不幸的是,当涉及到这些ANN实现的效率和准确性时,该图并没有完整描述。 虽然HNSWlib和NGT-panng可以快速而准确地执行,但这只是在它们构建之后。 “构建时间”是指算法构建其索引并开始查询邻居所需的时间长度。 根据算法的实现,构建时间可能是几分钟或几小时。 下图是我们的基准测试的平均算法构建时间, 不包括Faiss-HNSW,该过程花费了1491分钟的构建时间(约24小时)

    Image for post
    Average build time, in minutes, for each algorithm tested excluding Faiss-HNSW which took 24 hours to build. Note how some of the algorithms that ran quickly took longer to build. Image by Author.
    测试的每种算法的平均构建时间(以分钟为单位)(不包括Faiss-HNSW花费的24小时构建时间)。 请注意,快速运行的某些算法是如何花较长时间构建的。 图片由作者提供。

    As we can see the picture changes substantially when we account for the time spend “building” the algorithm’s indexes. This index is essentially a roadmap for the algorithm to follow on its journey to find the nearest-neighbor. It allows the algorithm to take shortcuts, accelerating the time taken to find a solution. Depending on the size of the dataset and how intricate and comprehensive this roadmap is, build-time can be between a matter of seconds and a number of days. Although accuracy is always a top priority, depending on the circumstances it may be advantageous to choose between algorithms that build quickly or algorithms that run quickly:

    正如我们看到的那样,当我们考虑“构建”算法索引所花费的时间时,情况会发生很大的变化。 该索引本质上是该算法在查找最近邻居的过程中要遵循的路线图。 它允许算法采用快捷方式,从而加快了找到解决方案的时间。 根据数据集的大小以及此路线图的复杂程度,构建时间可能在几秒钟到几天之间。 尽管准确性始终是头等大事,但根据具体情况,在快速构建的算法或快速运行的算法之间进行选择可能会比较有利:

    • Scenario #1: You have a dataset that updates regularly but isn’t queried often, such as a school’s student attendance record or a government’s record of birth certificates. In this case, you wouldn’t want an algorithm that builds slowly because each time more data is added to the set, the algorithm must rebuild it’s index to maintain a high accuracy. If your algorithm builds slowly this could waste valuable time and energy. Algorithms such as Faiss-IVF are perfect here because they build fast and are still very accurate.

      方案1:您有一个定期更新但不经常查询的数据集,例如学校的学生出勤记录或政府的出生证明记录。 在这种情况下,您不希望算法构建缓慢,因为每次将更多数据添加到集合中时,该算法必须重建其索引以保持较高的准确性。 如果算法构建缓慢,可能会浪费宝贵的时间和精力。 Faiss-IVF之类的算法在这里非常理想,因为它们构建速度很快并且仍然非常准确。

    • Scenario #2: You have a static dataset that doesn’t change often but is regularly queried, like a list of words in a dictionary. In this case, it is more preferential to use an algorithm that is able to perform more queries per second, at the expense of built time. This is because we aren’t adding new data regularly and hence don’t need to rebuild the index regularly. Algorithms such as HNSWlib or NGT-panng are perfect for this because they are accurate and fast, once the build is completed.

      场景2:您有一个静态数据集,该数据集不会经常更改,而是会定期查询,例如字典中的单词列表。 在这种情况下,更可取的是使用能够每秒执行更多查询的算法,但会浪费构建时间。 这是因为我们不会定期添加新数据,因此不需要定期重建索引。 HNSWlib或NGT-panng之类的算法非常适合此操作,因为一旦构建完成,它们便准确且快速。

    There is a third scenario worth mentioning. In my experiments attempting to benchmark ANN algorithms on larger and larger portions of the deep1b dataset, available memory started to become a major limiting factor. Hence, picking an algorithm with efficient use of memory can be a major advantage. In this case, I would highly recommend the Faiss suite of algorithms which have been engineered to perform under some of the most memory starved conditions.

    还有第三种情况值得一提。 在我的实验中,试图在Deep1b数据集的越来越大的部分上对ANN算法进行基准测试 ,可用内存开始成为主要的限制因素。 因此,选择一种有效利用内存的算法可能是一个主要优势。 在这种情况下,我强烈建议使用Faiss算法套件,这些套件经设计可在某些内存不足的情况下执行。

    Regardless of the scenario, we almost always want high accuracy. In our case accuracy, or recall, is evaluated based on the algorithm’s ability to correctly determine the 10 nearest-neighbors of a given point. Hence the algorithm’s performance could change if we consider its 100 nearest-neighbors or its single nearest-neighbor.

    无论哪种情况,我们几乎总是希望获得高精度。 在我们的情况下,根据算法正确确定给定点的10个最近邻居的能力来评估准确性或召回率。 因此,如果我们考虑它的100个最近邻居或单个最近邻居,算法的性能可能会改变。

    摘要: (The Summary:)

    Image for post
    What will you pick for your next project? Photo by Franck V. on Unsplash
    您将为下一个项目选择什么? Franck V.Unsplash上的照片

    Based on our findings from this benchmark experiment there are clear benefits to using some algorithms as opposed to others. The key to picking an optimal ANN algorithm is understanding what about the algorithm you want to prioritize and what engineering tradeoffs you are comfortable with. I recommend you prioritize what fits your circumstances, be that speed (QPS), accuracy (Recall), or pre-processing (Build time). It is worth noting algorithms that perform with less than 90% Recall aren’t worth discussing. This is because 90% is considered to be the minimum level of performance when conducting nearest-neighbor search. Anything less than 90% is underperforming and likely not useful.

    根据我们从基准测试中获得的发现,使用某些算法相对于其他算法具有明显的好处。 选择最佳ANN算法的关键是了解要确定优先级的算法是什么,以及需要进行哪些工程折衷。 我建议您优先考虑适合您的情况的速度,速度(QPS),准确性(调用)或预处理(构建时间)。 值得注意的是,执行调用率不到90%的算法不值得讨论。 这是因为在执行最近邻居搜索时,90%被认为是最低性能。 少于90%的广告效果不佳,可能没有用。

    With that said my recommendations are as follows:

    话虽如此,我的建议如下:

    • For projects where speed is a priority, our results suggest that algorithms such as HNSWlib and NGT-panng perform accurately with a greater number of queries per second than alternative choices.

      对于优先考虑速度的项目,我们的结果表明,与其他选择相比,诸如HNSWlibNGT-panng之类的算法每秒可以执行的查询数量更高, 从而能够准确执行。

    • For Projects where accuracy is a priority, our results suggest that algorithms such as Faiss-IVF and SW-graph prioritize higher Recall scores, whilst still performing quickly.

      对于以准确性为优先的项目,我们的结果表明,诸如Faiss-IVFSW-graph之类的算法会优先考虑较高的查全率,同时仍能快速执行。

    • For projects where pre-processing is a priority, our results suggest that algorithms such as Faiss-IVF and Annoy exhibit exceptionally fast build times whilst still balancing accuracy and speed.

      对于需要优先处理的项目,我们的结果表明,诸如Faiss-IVFAnnoy之类的算法显示出异常快的构建时间,同时仍然在准确性和速度之间取得了平衡。

    Considering the circumstances of our experiment, there are a variety of different scenarios where some algorithms may perform better than others. In our case, we have tried to perform in the most generic and common of circumstances. We used a large dataset with high, but not excessively high, dimensionality to help indicate how these algorithms may perform on sets with similar specifications. For some of these algorithms, more tweaking and experimentation may lead to marginal improvements in runtime and accuracy. However, given the scope of this project it would be excessive to attempt to accomplish this with each algorithm.

    考虑到我们的实验环境,在许多不同的情况下,某些算法的性能可能会优于其他算法。 在我们的案例中,我们试图在最普通和最常见的情况下执行。 我们使用了一个具有高(但不是过高)维的大型数据集,以帮助指示这些算法如何在具有相似规格的集合上执行。 对于其中一些算法,更多的调整和实验可能会导致运行时和准确性的轻微改善。 但是,鉴于该项目的范围,尝试使用每种算法来完成此任务将是多余的。

    If you are interested in learning more about Bernhardsson’s project I recommend reading some of my other blogs on the topic. If you are interested in looking at the full CSV file of results from this benchmark, it is available on my GitHub here.

    如果您有兴趣了解有关Bernhardsson项目的更多信息,我建议您阅读其他一些有关该主题的博客。 如果您有兴趣查看此基准测试结果的完整CSV文件,请在我的GitHub上此处获取

    未来的工作: (Future Work:)

    Whilst this is a good starting point for picking ANN algorithms there are still a number of alternative conditions to consider. Going forward I would like to explore how batch performance impacts our results and whether different algorithms perform better when batching is included. Additionally, I suspect that some algorithms will perform better when querying for different numbers of nearest-neighbors. In this project, we chose 10 nearest neighbors, however, our results could shift when querying for 100 neighbors or just the top 1 nearest-neighbor.

    虽然这是选择ANN算法的一个很好的起点,但仍然需要考虑许多替代条件。 展望未来,我想探讨批处理性能如何影响我们的结果以及包括批处理时不同的算法是否表现更好。 另外,我怀疑在查询不同数量的最近邻居时某些算法的性能会更好。 在此项目中,我们选择了10个最近的邻居,但是,当查询100个邻居或仅搜索前1个最近的邻居时,结果可能会发生变化。

    附录: (Appendix:)

    1. Computer specifications: 1U GPU Server 1 2 Intel CD8067303535601 Xeon® Gold 5115 2 3 Kingston KSM26RD8/16HAI 16GB 2666MHz DDR4 ECC Reg CL19 DIMM 2Rx8 Hynix A IDT 4 4 Intel SSDSC2KG960G801 S4610 960GB 2.5" SSD.

      计算机规格: 1U GPU服务器1 2 Intel CD8067303535601Xeon®Gold 5115 2 3 Kingston KSM26RD8 / 16HAI 16GB 2666MHz DDR4 ECC Reg CL19 DIMM 2Rx8 Hynix A IDT 4 4 Intel SSDSC2KG960G801 S4610 960GB 2.5“ SSD。

    2. Link to How to Benchmark ANN Algorithms: https://medium.com/gsi-technology/how-to-benchmark-ann-algorithms-a9f1cef6be08

      链接到如何对ANN算法进行基准测试: https : //medium.com/gsi-technology/how-to-benchmark-ann-algorithms-a9f1cef6be08

    3. Link to ANN Benchmarks: A Data Scientist’s Journey to Billion Scale Performance: https://medium.com/gsi-technology/ann-benchmarks-a-data-scientists-journey-to-billion-scale-performance-db191f043a27

      链接到ANN基准:数据科学家的十亿规模绩效之旅: https : //medium.com/gsi-technology/ann-benchmarks-a-data-scientists-journey-to-billion-scale-performance-db191f043a27

    4. Link to CSV file that includes benchmark results: https://github.com/Briggs599/Deep1b-benchmark-results

      链接到包含基准测试结果的CSV文件: https : //github.com/Briggs599/Deep1b-benchmark-results

    资料来源: (Sources:)

    1. Aumüller, Martin, Erik Bernhardsson, and Alexander Faithfull. “ANN-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms.” International Conference on Similarity Search and Applications. Springer, Cham, 2017.

      Aumüller,Martin,Erik Bernhardsson和Alexander Faithfull。 “ ANN基准:用于近似最近邻算法的基准测试工具。” 国际相似性搜索及其应用会议 。 湛,施普林格,2017

    2. Deep billion-scale indexing. (n.d.). Retrieved July 21, 2020, from http://sites.skoltech.ru/compvision/noimi/

      十亿规模的深索引。 (nd)。 于2020年7月21日从http://sites.skoltech.ru/compvision/noimi/检索

    3. Liu, Ting, et al. “An investigation of practical approximate nearest neighbor algorithms.” Advances in neural information processing systems. 2005.

      刘婷,等。 “研究实用的近似最近邻算法。” 神经信息处理系统的研究进展 。 2005。

    翻译自: https://medium.com/gsi-technology/a-data-scientists-guide-to-picking-an-optimal-approximate-nearest-neighbor-algorithm-6f91d3055115

    快速近似最近邻算法

    展开全文
  • 最近邻目标关联算法

    2021-02-19 09:08:40
    就我所知,关联或匹配方法(如:匈牙利算法最近邻目标关联算法、回溯法等)都是以获取两者之间的距离或其他标准(如网上回溯法的例子大部分是给工人分配工作,要求完成时间最少,那么这个标准就是时间,但是时间也...
  • KNN最近邻算法理解

    千次阅读 2019-03-20 21:54:39
    k-最近邻算法是基于实例的学习方法中最基本的,先介绍基于实例学习的相关概念。 基于实例的学习 已知一系列的训练样例,很多学习方法为目标函数建立起明确的一般化描述;但与此不同,基于实例的学习方法只是简单地...
  • 不断向开源社区添砖加瓦的微软近日又有大动作-- 将强大的最近邻搜索算法开源。2019年5月15日,GitHub存储库上的开源社区成员都可以访问微软的空间分区树和图(SPTAG)算法,该算法“允许用户充分利用学习模型在以...
  • 快速最近邻匹配

    千次阅读 2016-03-06 13:51:43
    这是一个完整的利用Suft快速近邻匹配的程序#include #include #include #include #include #include <opencv2
  • k-d树最近邻搜索算法伪代码: ''' 输入:k-d树根节点root,要查询的结点target 输出:k-d树中距离target最近的结点nearest_node ''' search(root, target): ## 1. 进行二叉查找,建立搜索路径,直到找到一个叶结点...
  • KNN(k-nearest neighbor的缩写)最近邻算法原理详解

    万次阅读 多人点赞 2017-08-24 16:55:43
    k-最近邻算法是基于实例的学习方法中最基本的,先介绍基于实例学习的相关概念。 基于实例的学习 已知一系列的训练样例,很多学习方法为目标函数建立起明确的一般化描述;但与此不同,基于实例的学习方法只是简单地...
  • Scikit-learn实战之最近邻算法

    千次阅读 2016-12-22 20:36:19
    1. 最近邻的概念 sklearn.neighbors 提供了基于最近邻的无监督和有监督学习方法的功能。无监督最近邻是许多其他学习方法的基础,尤其是流型学习和谱聚类。有监督的最近邻学习有两种形式:对离散类标的数据进行分类...
  • 最近邻算法(KNN)

    2018-11-27 19:54:00
    最近邻算法: 1.什么是最近邻是什么?  kNN算法全程是k-最近邻算法(k-Nearest Neighbor)  kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数数以一个类型别,则该样本也属于这个类别,...
  • 数据挖掘——近似最近邻算法ANN之LSH简介LSH算法LSH之相似网页查找——Simhash 简介 局部敏感哈希(Locality Sensitive Hashing,LSH)主要是为了处理高维度数据的查询和匹配等操作。 关于这个算法,综合多个前辈的...
  • 【机器学习】《机器学习实战》读书笔记及代码:第2章 - k-近邻算法 1、初识 K最近邻分类算法(K Nearest Neighbor)是著名的模式识别统计学方法,在机器学习分类算法中占有相当大的地位。主要应用领域是对未知事物的...
  • 最近邻算法(KNN)

    千次阅读 2019-03-17 18:00:50
     目前,对于文本分类的研究已经取得了巨大的进展,常用的文本分类算法最近邻算法(KNN),支持向量机,人工神经网络,boosting,随机森林等。而KNN算法既是最简单的机器学习算法之一,也是基于实例的学习方法中最...
  • KNN最近邻分类算法 + cs231n assignment1

    千次阅读 2017-12-04 15:47:02
    K最近邻(k-Nearest Neighbor,KNN)分类算法 1、KNN的基本思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。 2、用处:KNN算法不仅...
  • 数据挖掘十大经典算法之K最近邻算法 k-最近邻算法是基于实例的学习方法中最基本的,先介绍基于实例学习的相关概念。  基于实例的学习  1.已知一系列的训练样例,很多学习方法为目标函数建立起明确的一般化...
  • Surf(Speed Up Robust Feature) ...Surf算法的原理 1.构建Hessian矩阵构造高斯金字塔尺度空间 其实surf构造的金字塔图像与sift有很大不同,就是因为这些不同才加快了其检测的速度。S
  • kkk-nearest neighbors algorithm - kkk 最近邻算法 In pattern recognition, the kkk-nearest neighbors algorithm (kkk-NN) is a non-parametric method used for classification and regression. In both cases, ...
  • k-d tree的最近邻搜索算法

    千次阅读 2013-04-24 11:27:24
    所谓的特征点匹配本质上是一个通过距离函数(例如欧式距离)在高维...K近邻查询就是给定查询点和正整数K,从数据集中找到距离查询点最近的K个数据,当K=1时,它就是最近邻查询。   如上图(b)我们从输入图像中进行
  • SURF——FLANN快速最近邻匹配

    千次阅读 2018-11-06 15:51:35
    //实例化一个FLANN快速最近匹配器 vector<DMatch> matches; //DMatch专门为特征点匹配建立的类型 //int queryIdx; //此匹配对应的查询图像的特征描述子索引,如1,2,3。 //int trainIdx; //此匹配对应的训练...
  • 高维数据的可伸缩最近邻算法FLANN1.简介在计算机视觉和机器学习中,对于一个高维特征,找到训练数据中的最近邻计算代价是昂贵的。对于高维特征,目前来说最有效 高维数据的快速最近邻算法FLANN 1.简介 在...
  • ICP算法——迭代最近邻算法

    千次阅读 2017-07-06 22:11:36
    转载自http://blog.csdn.net/xiaowei_cqu/article/details/8470376 ... ...假定已给两个数据集P、Q, ,给出两个点集的空间变换f使他们能进行空间匹配。这里的问题是,f为一未知函数,
  • 最近邻算法 基本思路:近朱者赤,近墨者黑 定义:以全部训练样本作为代表点,计算未知样本与所有训练样本的距离,并以最近邻者的类别作为决策未知样本类别的唯一依据 缺陷:对噪声数据过于敏感 K-最近邻算法(KNN) ...
  • 本文针对传统SURF (Speeded Up Robust Features)算法精度和速度较低的问题, 提出一种优化的图像匹配算法. 在特征点提取阶段引入局部二维熵来刻画特征点的独特性, 通过计算特征点的局部二维熵并设置合适的阈值来剔除...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,648
精华内容 3,459
关键字:

最近邻匹配算法