高效的产品分割树实现紧凑聚类和快速最近邻搜索

1产品拆分树ArtemBabenkoYandex，国立研究型大学高等经济artem. phystech.edu维克托·伦皮茨基斯科尔科沃科学技术学院lempitsky@skoltech.ru摘要在这项工作中，我们介绍了一种新的空间划分树的有效最近邻搜索。我们的ap-proach首先确定一组有用的数据分裂direc- tions，然后学习一个码本，可以用来编码这样的方向。我们使用乘积量化的思想，以使有效的码本大，评估的查询和编码的分裂方向之间的标量积非常快，和编码本身compact。因此，所提出的数据结构（产品分割树）实现了数据点的紧凑聚类，同时保持遍历非常有效。在高维数据的最近邻搜索实验中，乘积分裂树达到了最先进的性能，表现出比其他空间划分树更好的速度-精度权衡。1. 介绍空间划分树是高维空间中用于近似最近邻搜索的常用数据结构。目前，分区树为中等规模的设置提供了最先进的性能，当数据库点可以保存在主内存中，但对它们的线性扫描很慢。分区树通过分层地将搜索空间划分为对应于树叶的大量区域来进行，而每个这样的区域包含一个或几个数据库点。在搜索阶段，查询沿着树向下传播，以深度优先顺序访问有限数量的叶子，并且仅评估从这些叶子到点的在实践中，这种方法比穷举线性扫描快得多，同时在给定有限时间预算的情况下提供高精度。现有技术的划分树通常在每个内部节点中使用由超平面Xw，x=b这里，w是超平面法线，我们称之为分裂方向，b是阈值。当搜索给定的在每个内部节点上查询q表达式的符号w，q确定应该首先访问的子树。划分树的实际性能主要取决于两个因素。第一个因素是定义空间分区的分割方向的通常，树构建算法寻求使用具有高数据投影方差的方向w。 分区X具有高方差方向的区域更多紧凑，因此深度优先搜索将设法以少量步骤从查询的叶移动到其最近的相邻叶的概率更高。第二个因素是传播效率，其取决于在每个内部节点中对（1现有的最先进的方法提出了这两个因素之间的不同可能，最著名的划分树是KD-树[7]，其使用轴对齐的超平面，即。 ||W||0= 1。通常，使用与具有最高数据方差的轴正交的超平面。KD树的传播是非常有效的，因为计算（1）只需要一个COM，在每个内部节点中执行重复操作然而，KD-树内的分裂方向的质量较差，因为在树构造期间在每个节点中仅考虑d个可能的方向w由于依赖于原始数据坐标基础，这些方向可能是次优的，因为在某些节点中沿着所有方向的数据方差可能很小。相比之下，另一种称为PCA树[20]的方法通过沿着从指向特定节点的点的子集学习的主要主方向进行分裂来产生更好的空间划分。三重投影树（TP树）[21]考虑了一组受限的分裂方向，其范围比KD树内的范围更大，比PCA树内的范围更小。总的来说，PCA树和TP树产生的分离超平面比KD树更适合特定的数据集，这导致更紧凑的分区区域。另一方面，评价62146215表1. 最先进的分区树的主要设计特征的比较d表示搜索数据库的维度d′是TP树分割方向内活动坐标的最大数量。K是PS树内的子方向码本的大小，M是码本的数量总的来说，PS树提供了高质量的分割方向和运行时/内存效率。PS树唯一的额外开销是查询预处理，但在大多数实际情况下，通过选择足够小的K，可以使该开销可以忽略不计，这仍然可以提供足够多样的分裂集。在这些树中，（1）的代价更高，传播更慢。此外，PCA树和TP树需要更多的额外内存来保存拆分。在这项工作中，我们介绍了产品分割树（PS树），一种新的空间分区树，使用码本学习，以便在同一方法中组合高质量和高效传播的分裂方向PS树的主要思想是初步学习一个大的分裂方向集，这些方向有希望在树的所有级别上提供这些方向在离线阶段学习，然后在这些方向上的数据集点投影的值被用来以通常的KD树方式构建树。然后，在查询阶段，评估查询在所有学习方向上的投影，然后基于这些值执行典型的KD树传播PS树通过学习乘积量化（PQ）形式的分裂方向实现了效率和良好的数据适应性[10]。基于反向索引的基于PQ的方法已经为非常大的“十亿级”数据集中的最近邻搜索提供了最先进的技术在这项工作中，我们扩展PQ的成功到一个较小的因此，我们展示了如何将PQ的想法纳入分区树，并提供新的国家的最先进的，优于现有的方法。PS-树的性能进行了评估的四个数据集的图像描述符典型的计算机视觉任务（SIFT向量，“深”描述符，GIST描述符，MNIST图像）。我们表明，对于一个给定的时间预算PS-树提供更高的召回相比，现有的表现最好的分区树。此外，我们还表明，对于一个给定的额外的内存预算PS-树也优于现有的方法。这鼓励在具有有限资源的场景中使用PS树，例如在移动应用中。2. 相关工作在这一节中，我们描述了几种方法和思想，从以前的作品是必不可少的描述PS-树。我们还介绍了以下部分的符号。近似最近邻搜索。最近邻搜索任务是许多机器学习系统的重要组成部分，涉及大规模聚类，分类，核回归等。给定数据集X ={x1，. . . ，x N}n= Rd和查询q，目标是找到最接近该查询的点arg mini||x i− q||二、精疲力竭-主动线性扫描需要O（dN）操作，这可能太昂贵了。在这种情况下，近似最近邻（ANN）搜索方法是有用的。 在本文中，我们将-因为时间约束的ANN搜索，这意味着搜索方法在一定的时间预算已经过去之后终止。通常，这些方法通过查全率度量进行比较，查全率度量是在给定时间内成功找到最近邻居的查询的比率。分区树。分区树是ANN搜索的一种常用方法。它们递归地将搜索数据库X分割成多至几个接近点的子集（或者甚至单个子集）。在每棵树的叶子上。在搜索阶段，查询q以深度优先的方式沿着树向下传播，并且仅评估从少量访问的叶子到点的距离。在本文中，我们专注于使用二元超平面分割的树。在这种情况下，每个内部节点具有参数w∈Rd和b∈R，并且对应于将空间分裂为两个半空间{x| w，2。PS-树也可以推广到两个以上的子方向码本。然而，这导致若干缺点。首先，找到最佳分裂方向需要搜索KM个组合，这在M>2的情况下变得更加困难6220M图1.从数据点到其所属分区质心的平均距离所评估的分区是由PS-树、TP-树、PCA-树和小深度的KD-树产生的分区。与KD树相比，PS树和TP树/PCA树产生更紧凑的划分区域，这转化为更有效的叶访问顺序，因此转化为更有效的NN搜索。图2. 在SIFT 1M数据集上具有不同码本大小K值的PS树的比较（召回率与时间），M= 2。在K= 127之后，性能饱和。即使对于小的K，PS树也提供了合理的性能，表明分裂方向自适应的重要性。因为成对协方差的个数变成了C2此外，传播成本是O（M）操作，每个节点必须保持M个索引而不是只有两个。在实践中，具有M=2的PS树已经提供了足够数量的分裂方向，并且优于现有的方法。类似于倒置的多指数（主要是出于相同的原因），M=2似乎是4. 实验在这一节中，我们提供了比较PS树与其他现有的划分树和一些非树ANN搜索方法的实验结果。实验在四个数据集上进行：1. SIFT 1 M数据集[10]，包含128-三维SIFT描述符以及预先计算的10，000个查询的地面实况。2. DEEP1M数据集[5]，包含100万个256维深度描述符以及1000个查询的预先计算的地面实况。深度描述符被形成为在Imagenet数据集上预训练的CNN的全连接层的归一化和PCA压缩输出[1]。目前，这种深度描述符是最近邻搜索算法的重要测试用例。3. GIST 1M[10]包含一百万个960维GIST描述符[17]以及为1000个查询预先计算的地面实况。4. MNIST[22]，包含70，000个784维向量，对应于28×28的手写数字图像。我们使用1000个向量的随机子集作为查询，其余的69000个向量作为基本集合。在我们的大多数实验中，不同的方法是基于查全率衡量标准，这是一个率的查询，真正的最近邻被成功地发现。我们仅针对第一最近邻来测量召回率，因为找到几个最近邻的能力也很重要，但在实践中，它与找到最接近的一个的能力高度相关为了提高效率，在细分码本学习期间，我们使用了[13]中PCA树构造的近似版本对于KD树，我们使用来自FLANN库的著名实现[15]。TP树的实现不能在线或按需提供，我们在FLANN框架内用C++仔细地重新实现了它，并进行了与PS树相同的因此，所有比较的方法都是从同一个基类继承的不同类实现的，区别仅在于它们的分裂和传播函数。所有其他实现细节保持不变，以确保公平的比较。我们打算将我们的代码作为附加的FLANN类与出版物一起发布。所有时间都是在英特尔®至强®CPU E5-2650 v2@2.60 GHz机器上以单线程模式获得的，作为十次运行的平均结果。分裂质量。在第一个实验中，我们证明了PS树产生的分裂方向，其质量与TP树或PCA树的方向相当，并且比KD树分裂方向好得多。为此，我们为SIFT 1M数据集构建了深度在范围[1，5]内的每种类型的单个树。对于每个深度值，我们测量从数据点到它们所属的叶子的质心图1显示PS树和TP树/PCA树的分裂方向具有相同的质量，并且比KD树方向好得多6221SIFT 1M深1MGIST1M MNIST图3.四个数据集上的单个PS-树、单个TP-树和单个KD-树的比较。对于可能的时间预算值的整个范围，PS树提供最高的召回率。对于SIFT 1M，还提供了反向多索引的性能。对于在“百万级”有用的典型搜索时间选择K。然后，我们研究了一个问题的最佳K为给定的数据集。图2展示了不同K值下PS树的性能。当K值大于127时，性能达到饱和。请注意，即使K=7（以及49个可用的分裂方向）非常小，PS树也提供了相当合理的性能，证明了分裂方向适应特定数据集的重要性。在实验中，我们选择K接近数据集维度，即SIFT1M的K=127，DEEP 1M的K=255，MNIST的K =511，GIST 1M的K=1023搜索一棵树。现在我们比较一个单一的PS-树，一个单一的TP-树和一个单一的KD-树的搜索性能。我们比较了M=1和M=2的PS树变体，以证明PQ使用的好处。PCA树不包括在比较中，因为其性能较差[21]。对于所有的基准数据集，我们测量召回实现不同的时间芽-获取。结果示于图3中。对于SIFT 1M，我们还增加了反向多索引的性能，这是十亿级ANN搜索的最先进方法。各方法参数准确在保留数据集上进行调整。图3显示了一个PS树在两个数据集上都优于现有的方法。倒排多索引的性能低于所有分区树，这表明它在这种规模下效率低下（可能是由于数据的分裂非常不平衡树木合奏的表演。然后我们比较PS-树系综与TP-树系综，弗兰选择集合的大小，以便所需的额外内存量与索引数据库的大小大致相同。对于一个N点的数据集，每个划分树包含N-1个内部节点，假设每个叶子只包含一个点。每个叶节点只保留一个整数索引（四个字节）。每个内部节点保留两个指向子节点的指针（提供8个字节），浮点值阈值（4个字节）和一些关于分裂方向的信息，这取决于树的种类。KD树只需要一个字节用于坐标轴，而PS树需要两个字节用于两个索引m，n。TP-树节点需要dN字节，其是多个活动坐标。在我们的实验中，SIFT 1M的平均值为11，DEEP 1M为12，MNIST和GIST 1M为14。总的来说，TP的内部节点6222SIFT 1M深1MGIST1M MNIST图4.在附加内存受限的情况下，比较了不同的划分树集成。在这个实验中，我们将额外内存的大小限制为与搜索数据库的大小相同。因此，对于128维SIFT 1M，比较了8棵KD树、8棵PS树和4棵TP树。对于256维的深度描述符，比较了16个KD-树、16个PS-树和8个TP-树。在这种情况下，内存有效的PS-树与M= 2优于现有的分区树合奏相当。在相同的内存约束下，PS树的性能也优于最先进的LSH方法[3树需要的内存是PS树的两倍。因此，对于SIFT 1M，我们比较了8棵PS树和4棵TP树的集合，而对于DEEP1M，我们比较了16棵PS树和8棵TP树的集合对于MNIST和GIST 1M，我们比较了32个PS树和32个TP树的集成，因为PS树集成的性能饱和，并且添加超过32棵树没有性能优势。为了进行比较，我们还提供了具有相同内存约束的SIFT 1M上最先进的LSH方法[3] [3]据报道，对于LSH 0。9精度水平达到3. 1毫秒（在更快的CPU上），检查了大约13000个候选人。PS树集成达到0. 9召回水平在1. 5毫秒，平均对应于4000名候选人。结果如图4所示。它表明，对于有限的额外内存的制度，PS-树的合奏优于其他多分区树在所有四个数据集。请注意，对于所有数据集，M=2的PS树提供了比M=1更高的查全率。这个ver-体现了使用乘积量化码本的益处5. 总结在本文中，我们介绍了产品分裂（PS）树，一种新的数据结构的近似最近邻搜索。PS-树结合了空间划分的紧凑性和分裂函数的计算效率，高级思想是找到适合于特定数据集的有希望的分裂方向的大集合使用学习的码本，然后我们构建可以有效地遍历的分区树因此，我们的方法建立在产品量化的想法，并将其扩展到“百万级”的而以前的产品，UCT量化成功地结合了倒排索引，我们显示了它与分区树相结合的优点。6223引用[1] A Berg和J Deng和L Fei-Fei。大规模视觉识别挑战赛 （ILSVRC）计算机视觉理论和应用，里斯本，葡萄牙，2009年2月5-8日-第1卷，2009年。3[15]M. Muja和D. G.洛高维数据的可伸缩最近邻算法 IEEETrans. 模式分析http://www.image-net.org/challenges/LSVRC/2010/，Mach.内特尔，36，2014。三、六2010. 6[2] M. Aly，M.E. Munich和P.佩洛娜 大规模图像集合中的索引：缩放特性和基准。在IEEE计算机视觉应用研讨会（WACV 2011），2011年1月5日至7日，美国夏威夷科纳，第418-425页3[3] A. 安多尼山口因迪克，T.拉霍芬岛P. Razenshteyn，以及L.施密特角距离的实用和最佳LSH。2015年，在NIPS中。三、八[4] A. Babenko和V. Lempitsky反向多索引。在CVPR，2012年。 二、三[5] A. Babenko和V.S. Lempitsky 用于大规模相似性搜索和分 类的 树 量 化在 IEEE Conference on Computer Visionand Pattern Recognition，CVPR 2015，Boston，MA，USA，2015年6月7-12日，第42406[6] M. Bawa，T.Condie和P.甘尼桑LSH森林：用于相似性搜索的自调优索引。在第14届万维网国际会议（WWW2005）的会议记录中，Chiba，Japan，May 10-14，2005，pages 651-660，2005.3[7] J. L.本特利用于关联搜索的多维二叉搜索树。Commun.ACM，18，1975. 第1、3条[8] S. Dasgupta和Y.弗罗因德随机投影树与低维流形。在Proceedings of the 40th Annual ACM Symposium onTheory of Computing ， Victoria ， British Columbia ，Canada，May 17-20，2008，pages 5373[9] M. Datar，N. Immorlica，P. Indyk和V. S.米罗克尼基于p-稳定分布的局部敏感散列算法。在Proceedings of the20th ACM Symposium on Computational Geometry ，Brooklyn，New York，USA，June 8-11，2004，pages253-262，2004中。3[10] H. 我也是M. Douze和C. 施密特最近邻搜索的乘积量化IEEE传输模式分析马赫内特尔，33，2011。二、三、六[11] Y. Kalantidis和Y.阿弗里斯近似最近邻搜索的局部优化乘积量化。计算机视觉与模式识别国际会议论文集（CVPR 2014）。IEEE，2014。二、三[12] Q.吕，W.约瑟夫森，Z. Wang，M. Charikar和K.李多探头LSH：高效索引，用于高维相似性搜索。在维也纳大学第33届超大型数据库奥地利，2007年9月23-27日，第950-961页，2007年。3[13] M. McCartin-Lim，A. McGregor和R.王.近似主方向树。在第29届国际机器学习会议（ICML 2012）的会议记录中2012年6月26日至7月1日，英国苏格兰爱丁堡。三、六[14] M. Muja和D. G.洛自动算法配置的快速近似最近邻。在VISAPP 2009 -第四届国际会议[16] D. Nist e'r和H. Ste we e'nius. 用vo-cabulary树进行可扩展的识别2006年IEEE计算机协会计算机视觉和模式识别会议（CVPR 2006），2006年6月17日至22日，美国纽约州纽约市。3[17] A. Oliva 和 A. 托 拉 尔巴 建 模 场 景的 形 状InternationalJournal of Computer Vision，42（3）：145-175，2001。6[18] C. Silpa-Anan和R.哈特利用于快速图像描述符匹配的优化kd树。2008年IEEE计算机协会计算机视觉和模式识别会议（CVPR 2008），2008年6月24日至26日，美国阿拉斯加州安克雷奇。3[19] K.辛哈LSH与随机划分树：哪一个是最近邻搜索？第13届机器学习和应用国际会议，ICMLA 2014，底特律，密歇根州，美国，2014年12月3日至6日，第41-46页3[20] R. F.斯普劳尔k维树中最近邻搜索的改进。1991年，第6期。第1、3条[21] J. Wang，N.Wang，Y.Jia，J.Li，G.Zeng，H.Zha和X.华用于近似最近邻搜索的三值投影树。IEEE传输模式分析马赫内特尔，36，2014。一、三、七[22] 杨·勒昆，科琳娜·科尔特斯，克里斯托弗·J.C.伯吉斯MNIST手写数字数据库。http://yann.lecun.com/exdb/mnist/网站。 6