精华内容
下载资源
问答
  • 基于顺序NPsim矩阵的高维数据最近邻搜索算法
  • 提出一种基于角相似性的k-最近邻搜索算法(BA-KNNS)。该算法先提出基于角相似性的数据索引结构(BA-Index),参照一条中心线和一条参照线,将数据以系列壳—超圆锥体方式进行组织并分别线性存储;然后确定查询对象的...
  • 近似最近邻搜索算法

    2021-04-22 15:20:40
    是通过贪心算法遍历图,找出当前数据集中的最近邻点(局部最小值),以此作为插入并构建生成层状网络图,通过在下一层中不断寻找最近邻点插入构建,从而完成对特征向量集的维度分层、数据压缩、索引生成。...

    定义:

    采用分而治之思想,将原始数据通过映射方法划分到不同的向量空间,针对大规模的搜索任务,通过映射函数在向量相似的空间进行遍历查询。

    常用的几种算法:

    基于图的索引量化法:HNSW
    基于树:Annoy
    基于哈希:SLH

    HNSW(Hierarchical Navigable Small World)

    是通过贪心算法遍历图,找出当前数据集中的最近邻点(局部最小值),以此作为插入并构建生成层状网络图,通过在下一层中不断寻找最近邻点插入构建,从而完成对特征向量集的维度分层、数据压缩、索引生成。检索时,采用自上而下的搜索方式,即从最顶层开始粗略搜索,然后逐步向下层搜索,直到最底层精确搜索。
    在这里插入图片描述
    根据Benchmark上的ANN算法的测试,HNSW算法在查询速度和精度上优于其他算法,但是占用内存大。
    在这里插入图片描述

    HNSW代码

    import hnswlib
    import time
    import os
    import psutil
    def get_ann(length,dimen):
        start_time = time.time()
        pid = os.getpid()
        pp = psutil.Process(pid)
        info_start = pp.memory_full_info().uss/1024/1024
        #向量维度
        dim = dimen
        num_elements = length
        data = X
        data_labels = np.arange(num_elements)
        # 声明索引
        p = hnswlib.Index(space = 'l2', dim = dim) # hnswlib支持的距离有L2距离,向量内积以及cosine相似度
        # 初始化index
        p.init_index(max_elements = num_elements, ef_construction = 100, M = 16)
        # ef: 动态检索链表的大小。ef必须设置的比检索最近邻的个数K大。ef取值范围为k到集合大小之间的任意值。
        p.set_ef(50) 
        p.set_num_threads(4)#cpu多线程并行计算时所占用的线程数
        
        #构建items
        p.add_items(X, data_labels)
        index_path = 'data.bin'
        p.save_index(index_path)
        global labels, distances
        labels, distances = p.knn_query(data, k = 10)
        
        info_end=pp.memory_full_info().uss/1024/1024
        print('用时:%.2f s' % (time.time()-start_time))
        print('运行占内存'+str(info_end-info_start)+'MB')
    get_ann(X.shape[0],X.shape[1])  

    Annoy

    基本思路:
    给定一个查询向量,在一个庞大的向量集合中,找到与查询向量最相似的k个目标向量。工作原理:采用随机投影树,对所有的数据进行划分,将每次搜索与计算的点的数目减小到一个可接受的范围,然后建立多个随机投影树构成随机投影森林,将森林的综合结果作为最终结果。
    如何构建随机森林:
    随机选取一个向量,该向量经过原点,垂直于该向量的直线将平面内的点划分为两个部分,这两个部分的点分别划分给左子树和右子树。用数学语言是说,计算各个点与垂直向量的点积,若点积大于零的点划分到左子树,点积小于零的点划分到右子树。
    优点:
    索引小、内存占用小

    Annoy代码

    from annoy import AnnoyIndex
    import time
    import os
    import psutil
    # from guppy3 import hpy
    def get_nn(length,dimen):
        start_time = time.time()#开始时间
        pid = os.getpid()
        p = psutil.Process(pid)
    #     根据pid找到进程,进而找到占用的内存值
        info_start = p.memory_full_info().uss/1024/1024
        
        f = dimen#X的维度
        t = AnnoyIndex(f,'angular')#返回可读写的新索引,用于存储f维度向量
        for i in range(length):
            v = X[i]
            t.add_item(i,v)#构建 n_trees 的森林。查询时,树越多,精度越高。在调用build后,无法再添加任何向量。
        t.build(10)
        t.save('ann.ann')#将索引保存
        u = AnnoyIndex(f,'angular')
        u.load('ann.ann')
        global nn_list
        nn_list = []
        for i in range(length):
            nn_list.append(u.get_nns_by_item(i,10))#返回第i 个item的n个最近邻的item
            
     
        info_end=p.memory_full_info().uss/1024/1024
        print('用时:%s秒' % (time.time()-start_time))
        print('运行占内存'+str(info_end-info_start)+'MB')
        
        return nn_list
        
    get_nn(len(X),X.shape[1])
    展开全文
  • 最近邻搜索算法flann repo https://github.com/mariusmuja/flann http://www.qhull.org/
    展开全文
  • k-d树最近邻搜索算法伪代码: ''' 输入:k-d树根节点root,要查询的结点target 输出:k-d树中距离target最近的结点nearest_node ''' search(root, target): ## 1. 进行二叉查找,建立搜索路径,直到找到一个叶结点...

    k-d树最近邻搜索算法伪代码:

    '''
    k-d树中搜索最近邻点
    输入:k-d树根节点root,要查询的结点target
    输出:k-d树中距离target最近的结点nearest_node
    '''
    def kdsearch_nearest(root, target):
        ## 1. 进行二叉查找,建立搜索路径,直到找到一个叶结点
        #二分查找target结点应该落在哪个区域
        if root == NULL:
            return
        cur_node = root
        while cur_node != NULL:
            search_stack.push(cur_node)#把cur_node压入堆栈
            ##更新cur_node
            s = cur_node->split_dim #当前结点划分区域的维度
            if target->val[s] < cur_node->val[s]: 
                cur_node = cur_node->left
            else:
                cur_node = cur_node->right
        ## 2. 把叶结点设为在root为根的树中的初始最近邻点i_nearest_node
        i_nearest_node = search_stack.pop() #弹出搜索堆栈放进的最后一个结点,即一个叶结点
        if nearest_dis > dis(i_nearest_node,taget): #比较,更新全局最近邻点nearest_node
            nesrest_node = i_nearest_node
            nearest_dis > dis(i_nearest_node,taget)
        ## 3. 回溯更新全局最近邻点nearest_node
        while search_stack != NULL:
            cur_node = search_stack.pop()
            s = cur_node->split_dim
            if target[s] <= cur_node[s]: # 如果taget位于它的父结点的左区域,那么另外一个区域为右区域,
                search(cur_node->right,target) # 进入右区域递归搜寻最近邻点
            else: # 如果taget位于它的父结点的右区域,那么另外一个区域为左区域,
                search(cur_node->left,target) # 进入左区域递归搜寻最近邻点
            if dis(cur_node->right,taget) < nearest_dis: # 计算cur_node到target的距离,比较,更新最近邻点
                nearest_node = cur_node
                nearest_dis = dis(cur_node,target)
        return # 回退到根节点时,即search_stack弹出最底下的root结点,
               # 在root为根的树中结束搜索最近邻点,返回
    
    ## 使用k-d树搜索函数
        nearest_dis = 无穷大
        nearest_node = Node(0)
        kdsearch_nearest(root, target)

     

    展开全文
  • 下面介绍最简单的k-d tree最近邻搜索算法。 基本的思路很简单:首先通过二叉树搜索(比较待查询节点和分裂节点的分裂维的值,小于等于就进入左子树分支,大于就进入右子树分支直到叶子结点)...

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

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

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

    算法:kdtreeFindNearest  
     
    输入:Kd  
     
    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为空)  
      { 
        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)   
        {  
          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])   
            pSearch = pBack->right;  
          else  
            pSearch = pBack->left;   
    
          if(pSearch != NULL)  
            pSearch加入到search_path中  
        } 
      }  
    } 

    现在举一些例子来说明上面的最近邻搜索算法,假设我们的k-d tree就是上面通过样本集{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}创建的。将上面的图转化为树形图的样子如下:

    我们来查找点(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)的右子空间去搜索,因为右子空间中不可能有更近样本点了。

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

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

     

     

    再举一个稍微复杂的例子,我们来查找点(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。

    回溯至(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所花费的时间为:

     

     

    关于k-d tree还有很多扩展。由于大量回溯会导致kd-tree最近邻搜索的性能大大下降,因此研究人员也提出了改进的k-d tree近邻搜索,其中一个比较著名的就是 Best-Bin-First,它通过设置优先级队列和运行超时限定来获取近似的最近邻,有效地减少回溯的次数。

     

    参考资料

    1.An intoductory tutorial on kd-trees Andrew W.Moore

    2.《图像局部不变特性特征与描述》王永明 王贵锦 编著 国防工业出版社

    3.kdtree A simple C library for working with KD-Trees

    转载于:https://www.cnblogs.com/bwin/p/5247416.html

    展开全文
  • 不断向开源社区添砖加瓦的微软近日又有大动作-- 将强大的最近邻搜索算法开源。2019年5月15日,GitHub存储库上的开源社区成员都可以访问微软的空间分区树和图(SPTAG)算法,该算法“允许用户充分利用学习模型在以...
  • 极度快速的近似最近邻搜索算法(EFANNA)是NSG的作者之前的一篇论文,这篇论文主要介绍用更快的方法建立KNN图并且建立一个高性能的KNN图索引。这种方法建KNN图时采用类似于Wei等人提出的方案(地址),首先初始化一个KNN...
  • 寻找查询点的最近邻是信息处理相关领域的主要任务之一。在数据规模较大时需要采用快速检索算法,常用的快速检索算法主要是基于树的算法,但是当数据点维数较高时,这些算法的效率会变低。位置敏感哈希是当前解决高维...
  • 是一个实现亚线性最近邻搜索算法的 Java 库。 它包含近似和精确搜索算法。 第一种,Locality-sensitive Hashing ( LSH ) 是一种针对多个搜索空间的随机近似搜索算法。 第二种,多索引散列是一种精确的最近邻搜索算法...
  • k-d tree的最近邻搜索算法

    千次阅读 2013-04-24 11:27:24
    所谓的特征点匹配本质上是一个通过距离函数(例如欧式距离)在高维...K近邻查询就是给定查询点和正整数K,从数据集中找到距离查询点最近的K个数据,当K=1时,它就是最近邻查询。   如上图(b)我们从输入图像中进行
  • Surf(Speed Up Robust Feature) ...Surf算法的原理 1.构建Hessian矩阵构造高斯金字塔尺度空间 其实surf构造的金字塔图像与sift有很大不同,就是因为这些不同才加快了其检测的速度。S
  • 然后通过快速近似最近邻搜索算法得到初匹配点对, 再对得出的单向匹配结果进行双向匹配; 最后采用鲁棒性较好的PROSAC算法进一步剔除误匹配点对。实验证明了该算法不仅提高了SURF算法匹配的正确率, 还保证了算法的...
  • 高维空间最近邻逼近搜索算法评测

    千次阅读 2018-07-31 18:18:28
    高维空间最近邻逼近搜索算法评测   最近邻方法是机器学习中一个非常流行的方法,它的原理很容易理解:邻近的数据点是相似的数据点,更可能属于同一分类。然而,在高维空间中快速地应用最近邻方法,却是非常有挑战...
  • 版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/pipisorry/article/details/53156836 ... balltree k-dtree也有问题[最近邻查找...
  • 上一次介绍图像搜索的基本原理,现在记录下使用的数据包的问题。 查询图片先进行特征提取,使用一个向量来表示,之后使用该向量与数据库中所有的商品向量进行计算相似度指标,比如cos距离,欧式距离,汉明距离。 ...
  • 其基本思想是将样本集按近邻关系分解成组给出每组质心的位 置以质心作为代表点和未知样本计算距离选出距离最近的一 个或若干个组再在组的范围内应用一般的knn算法由于并不是 将未知样本与所有样本计算距
  • 旅行推销员 该项目将在Java中实现穷举搜索算法和改进的最近邻算法,以解决直线网格上的旅行推销员问题。 输入示例 示例输出文件1:改进的最近邻居算法 示例输出文件2:穷举优化算法
  • K最近邻算法

    2020-02-16 17:53:21
    1. 关于这个系列 这一系列笔记是我对下面这本书的阅读笔记: 虽然里面的内容看起来很简单,但是...之后,我们将了解K最近邻算法,之后简单介绍一些其他的算法,为进一步的学习做做铺垫。我们的这一系列文章几乎完全...
  • 1.5KD树的最近邻搜索算法 1.5.1举例:查询点(2.1,3.1) 1.5.2 举例:查询点(2,4.5) 2 kd树近邻搜索算法的改进:BBF算法 3 球树、M树、VP树、MVP树 3.1球树 3.2VP树与MVP树简介 特征点匹配和数据库查、...
  • 算法一 knn 中的 最近邻搜索

    千次阅读 2014-11-17 14:35:52
    本文的主要目的是讲一下如何创建k-d tree对目标物体的特征点集合进行数据组织和使用k-d tree最近邻搜索来加速特征点匹配。上面已经讲了特征点匹配的问题其实上是一个最近邻(K近邻)搜索的问题。所以为了更好的引出k...

空空如也

空空如也

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

最近邻搜索算法