高维数据中最近的邻居?

几天前我问了一个问题 ,如何find给定vector的最近邻居。 我的向量现在是21个维度,在我进一步研究之前,因为我不是来自机器学习和math领域,我开始问自己一些基本的问题:

  • 欧几里德距离是寻找最近邻居的好方法吗? 如果不是,我有什么select?
  • 另外,如何确定确定k邻居的正确阈值? 是否有一些分析可以做出这个数字呢?
  • 以前,我被build议使用kd-Trees,但维基百科页面清楚地表明,对于高维数据,kd-Tree几乎等同于蛮力search。 在这种情况下,在百万点数据集中有效地find最近邻的最佳方法是什么?

有人可以澄清一些(或全部)上述问题吗?

我目前正在研究这样的问题 – 分类,最近邻search – 用于音乐信息检索。

您可能对近似最近邻ANN )algorithm感兴趣。 这个想法是,你允许algorithm充分返回邻居 (也许不是最近的邻居)。 这样做可以降低复杂性。 你提到了kd-tree ; 这是一个例子。 但正如你所说, kd-tree在高维方面效果不佳。 事实上,目前所有的索引技术(基于空间划分)都会退化为线性search足够高的维数[1] [2] [3]。

在最近提出的人工neural networkalgorithm中,也许最stream行的是局部敏感散列LSH ),它将高维空间中的一组点映射到一组箱,即散列表[1] [3]。 但是与传统的哈希不同, 局部敏感的哈希将附近的点放在同一个文件夹中。

LSH有一些巨大的优势。 首先,这很简单。 您只需计算数据库中所有点的哈希值,然后根据它们生成哈希表。 要查询,只需计算查询点的哈希值,然后从哈希表中检索同一个bin中的所有点。

其次,有一个严格的理论支持它的performance。 可以看出,查询时间在数据库大小上是次线性的,即比线性search更快。 多快取决于我们可以容忍多less近似。

最后, LSH0 < p <= 2任何Lp范数兼容。 因此,要回答你的第一个问题,你可以使用LSH与欧几里得距离度量,或者你可以使用曼哈顿(L1)距离度量。 海明距离和余弦相似也有变种。

Malcolm Slaney和Michael Casey在2008年IEEE信号处理杂志上撰写了一篇不错的综述[4]。

LSH已被应用到表面上到处都是。 你可能想尝试一下。


[1] Datar,Indyk,Immorlica,Mirrokni,“基于p稳定分布的局部敏感散列scheme”,2004年。

[2] Weber,Schek,Blott,“高维空间中相似性search方法的定量分析和性能研究”,1998。

[3] Gionis,Indyk,Motwani,“通过散列进行高维相似性search”,1999年。

[4] Slaney,Casey,“寻找最近的邻居的局部敏感哈希”,2008年。

I.距离公制

首先,数据集中的特征(列)的数量不是select用于kNN的距离度量的因素。 目前已有相当多的研究针对这个问题,通常的比较基础是:

  • 数据的基本统计分布;

  • 构成数据的特征之间的关系(它们是独立的 – 即协方差matrix是什么样的); 和

  • 从中获取数据的坐标空间。

如果您对从中抽取数据的分布没有先验知识,至less有一项(有据可查的和彻底的) 研究得出结论,欧几里德距离是最好的select。

YEuclidean度量标准用于大型Web推荐引擎以及当前的学术研究。 欧几里得计算的距离具有直观的意义,计算尺度 – 即欧几里得距离的计算方式是相同的,无论这两点是二维的还是二维的二维空间。

它只是失败了几次,其中的每一种情况都是因为底层(笛卡尔)坐标系是一个糟糕的select而导致欧几里得距离失败。 你通常会认识到这一点,因为例如path长度(距离)不再是可加的 – 例如,当度量空间是棋盘时,曼哈顿距离比欧几里德要好,同样,当度量空间是地球,距离是反式大陆航class,适合极坐标系统的距离度量是一个好主意(例如,伦敦到维也纳是2.5小时,维也纳到圣彼得堡是另外3小时,或多或less在同一个方向,但伦敦到圣彼得堡不是5.5个小时,而是3个多小时。)

但除了数据属于非笛卡尔坐标系的情况之外,距离度量的select通常不重要。 (请参阅CS学生的这篇博客 ,通过检查他们对kNN分类器的影响来比较几个距离度量 – 卡方给出了最好的结果,但差异并不大;更全面的研究是在学术论文中比较研究最近邻居的距离函数 -在本研究中,马哈拉诺比斯(本质上归结为维数协方差的欧几里得)是最好的。

一个重要的限制条件是:为了使距离度量计算有意义,您必须对数据进行重新规模化 – 很less有可能build立一个kNN模型来生成准确的预测。 例如,如果你正在build立一个kNN模型来预测运动performance,而你的期望variables是身高(cm),体重(kg),体脂(%)和静息脉冲(每分钟跳动),那么一个典型的数据点可能看起来像这样:[180.4,66.1,11.3,71]。 很明显,距离计算将由高度来控制,而身体脂肪的贡献几乎可以忽略不计。 换句话说,如果数据报道不一样,那么体重是以克为单位而不是以千克为单位的,那么86.1的原始值就是8​​6,100,这对你的结果会有很大的影响,这正是你所要的不想要。 可能最常用的缩放技术是减去平均值并除以标准偏差(mean和sd分别为每列或该数据集中的特征计算; X是指数据行内的单个条目/单元格):

 X_new = (X_old - mu) / sigma 

II。 数据结构

如果您关心kd-tree结构的性能,那么Voronoi Tessellation是一个概念上简单的容器,但是这会大大提高性能,并且比kd-Trees更好地扩展。

DAT

这并不是坚持kNN训练数据的最常见的方式,尽pipeVT为此目的的应用以及随之而来的性能优势已经被充分logging(参见例如本研究报告 )。 这样做的实际意义在于,假如你使用的是“主stream”语言(例如,在TIOBE索引中 ),那么你应该找一个库来执行VT。 我知道在Python和R中,每种语言都有多种select(例如,在CRAN上可用的R的voronoi包)

使用VT作为kNN的工作方式如下::

从你的数据中,随机selectw点 – 这些是你的Voronoi中心。 Voronoi单元封装所有邻近每个中心的邻近点。 想象一下,如果你为每个Voronoi中心分配一个不同的颜色,那么分配给给定中心的每个点都被绘制成这个颜色。 只要你有足够的密度,这样做将很好地显示每个Voronoi中心的边界(作为分离两种颜色的边界。

如何selectVoronoi中心? 我使用两个正交准则。 随机selectw点后,计算您的训练数据的VT。 接下来检查分配给每个Voronoi中心的数据点的数量 – 这些值应该大致相同(数据空间中统一的点密度)。 在两个维度,这将导致VT与相同大小的瓦片。这是第一个规则,这是第二个。 通过迭代selectw – 以w作为variables参数运行您的kNNalgorithm,并测量性能(通过查询VT返回预测所需的时间)。

所以想象你有一百万个数据点…..如果这些点是在一个普通的二维数据结构中,或者在一个kd-tree中,那么对于每个响应variables的新数据点,平均执行几百万次距离计算你想预测。 当然,这些计算是在一个数据集上执行的。 使用V / T,最近邻居search按照两个步骤一个接一个地进行,针对两个不同的数据群体 – 首先是针对Voronoi中心,然后一旦find最近的中心,细胞内的点对应于search该中心以查找实际最近的邻居(通过连续的距离计算)结合起来,这两个查找比单一的蛮力查找快得多。 这很容易看出:对于1M数据点,假设您select了250个Voronoi中心来计算您的数据空间。 平均而言,每个Voronoi单元将有4000个数据点。 所以不是平均执行500,000次距离计算(蛮力),而是平均只有125 + 2,000次。

III。 计算结果(预测的响应variables)

从一组kNN训练数据计算预测值有两个步骤。 首先是识别n,或者用于这个计算的最近的邻居的数量 。 其次是如何加权对预测值的贡献

W / r / t是第一个分量,你可以通过求解最优化问题(非常类似于最小二乘优化)来确定n的最佳值。 这就是理论; 在实践中,大多数人只使用n = 3。 无论如何,对于n = 1,n = 2,n = 3等,运行你的kNNalgorithm在一组testing实例(计算预测值)上很简单,并将误差绘制为n的函数。 如果你只是想为n开始一个合理的值,再次使用n = 3。

第二部分是如何加权每个邻居的贡献(假设n> 1)。

最简单的加权技术就是将每个邻居乘以一个加权系数,即1 /(dist * K),或者是从该邻居到testing实例的距离的倒数,通常乘以一些经验导出的常数K。我不是这种技术的粉丝,因为它往往超重最近的邻居(并伴随着较重的邻居权重较低)。 其意义在于,给定的预测几乎完全依赖于单个邻居,这又增加了algorithm对噪声的敏感度。

一个更好的权重函数,这大大避免了这个限制是高斯函数 ,它在Python中,看起来像这样:

 def weight_gauss(dist, sig=2.0) : return math.e**(-dist**2/(2*sig**2)) 

要使用您的kNN代码来计算预测值,您需要确定您希望预测其响应variables('test instance')的数据点的n个最近邻居,然后调用weight_gauss函数,为每个n邻居调用一次在每个邻居之间的距离testing点。这个函数将返回每个邻居的权重,然后用作加权平均计算中的邻居的系数。

你面对的是被称为维度诅咒 。 运行一个像PCA或ICA这样的algorithm有时候是有用的,以确保你真的需要全部21个维度,并且可能find一个线性变换,这个变换可以让你使用less于21的结果质量。

更新:我在Rangayyan的一本名为“生物医学信号处理”(Biomedical Signal Processing)的书中遇到了这个问题(我希望我记得正确)。 ICA并不是一项简单的技术,但它是由芬兰的研究人员开发的,我认为它的Matlab代码是公开可供下载的。 PCA是一个更广泛使用的技术,我相信你应该能够find它的R或其他软件的实现。 通过迭代求解线性方程来执行PCA。 我已经做了很久以前,记住如何。 =)

这个想法是,你把你的信号分解成独立的特征向量(离散特征函数,真的)和它们的特征值,在你的情况下。 每个特征值显示每个特征函数为每个测量提供的贡献量。 如果特征值很小,那么可以非常精确地表示信号,而不必使用其相应的特征函数,这就是如何去除维度的方法。

要一一解答你的问题:

  • 不,欧氏距离在高维空间是一个不好的度量。 基本上在高维度上,最近的邻居和最远的邻居之间几乎没有什么区别。
  • 大量的论文/研究都在高维数据中,但是大多数的东西需要大量的math软化。
  • KD树对于高维数据是不利的…一定要避免它

这是一个很好的文章,让你开始正确的方向。 “ 当最近邻居有意义吗?” 由拜尔等所有。

我使用20K以上的文本数据。 如果你想要一些文字相关的build议,我可能会帮助你。

余弦相似度是比较高维向量的常用方法。 请注意,由于它不是一个距离的相似性,你想要最大化而不是最小化它。 您也可以使用领域特定的方式来比较数据,例如,如果您的数据是DNA序列,您可以使用考虑到突变概率的序列相似性等。

最近使用的邻居数取决于数据的types,有多less噪声等等。没有一般的规则,你只需要通过尝试一个范围内的所有值来find最适合你的具体数据和问题的东西。 人们有一个直观的了解,那里的数据越多,需要的邻居就越less。 在假设情况下,你有所有可能的数据,你只需要寻找最近的单个邻居分类。

已知k最近邻方法在计算上是昂贵的。 这是人们转向支持向量机等其他algorithm的主要原因之一。

很多取决于你为什么想知道最近的邻居。 如果你真正想要的是find你的数据集的模式,你可以看看平均转换algorithmhttp://en.wikipedia.org/wiki/Mean-shift 。

kd-trees在高维数据上确实不能很好地工作。 由于修剪步骤不再有帮助,因为最近的边缘 – 一维偏差 – 几乎总是小于已知最近邻居的全维偏差。

而且,对于我所知道的所有kd树都只能很好地适用于Lp规范,而且距离集中效应使得基于距离的algorithm随着维数的增加而退化。

欲了解更多信息,您可能需要阅读维度的诅咒,以及它的各种变体(有不止一个方面!)

我不相信只是盲目逼近欧几里得最近的邻居,例如使用LSH或随机投影,有很多用处。 首先,可能需要使用更精细的调整距离function!

iDistance可能是高维数据中精确检索的最佳select。 您可以将其视为近似Voronoi tessalation。

KD树在21个维度上工作良好,如果你早点退出,看完所有积分的5%。 FLANN做这个(和其他加速)匹配128昏暗的SIFT向量。 (不幸的是,FLANN只做欧几里德度量,而快速且稳定的scipy.spatial.cKDTree只做Lp度量;这些可能或者可能不足以满足您的数据。)这里当然有一个速度精度折衷。

(如果你可以描述你的Ndata,Nquery,数据分布,这可能有助于人们尝试类似的数据。)

4月26日,cKDTree的运行时间与我的旧mac ppc截断,给了一个非常粗略的可行性的想法:

 kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=1000 eps=0 leafsize=10 clustype=uniformp 14 sec to build KDtree of 1000000 points kdtree: 1000 queries looked at av 0.1 % of the 1000000 points, 0.31 % of 188315 boxes; better 0.0042 0.014 0.1 % 3.5 sec to query 1000 points distances to 2 nearest: av 0.131 max 0.253 kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=5000 eps=0 leafsize=10 clustype=uniformp 14 sec to build KDtree of 1000000 points kdtree: 1000 queries looked at av 0.48 % of the 1000000 points, 1.1 % of 188315 boxes; better 0.0071 0.026 0.5 % 15 sec to query 1000 points distances to 2 nearest: av 0.131 max 0.245 

你可以尝试一下az顺序曲线。 三维很容易。

我认为在布尔特性的tf-idf余弦适用于大多数问题。 这是因为在Lucene等许多search引擎中使用了经过时间validation的启发式。 根据我的经验,欧几里德距离对于任何类似文本的数据都是不好的结果。 训练数据和蛮力参数select可以select不同的权重和k例子。

我遇到了同样的问题,可以说以下几点。

  1. 欧几里德距离是一个很好的距离度量,但是它的计算量比曼哈顿距离要大 ,有时产生的结果也会稍微差一点,所以我select后者。

  2. k的值可以凭经验find。 您可以尝试不同的值,并检查生成的ROC曲线或一些其他精度/召回措施,以find可接受的值。

  3. 欧几里德距离和曼哈顿距离都尊重三angular形的不平等 ,因此你可以在度量树中使用它们。 事实上,当数据超过10个维度时(我自己也经历过这个问题),KD树的performance严重退化。 我发现副树是一个更好的select。

最好的答案是好的,但老,所以我想加起来2016年的答案


正如所说,在高维空间中,维度的诅咒潜伏在angular落,使传统的方法,如stream行的kd树,像暴力方法一样慢。 结果,我们把对于近似最近邻search(ANNS)的兴趣转向了一些准确性,从而加速了这个过程。 你可以很好地近似确切的NN,具有很好的适用性。


热门话题可能值得:

  1. 现代的LSH方法,如Razenshteyn的方法。
  2. RKD森林 :随机化kd树(RKD)的森林,如FLANN中所描述的,或者是我最近使用的方法kd-GeRaF 。
  3. LOPQ代表本地优化产品量化,如此处所述。 这与新的Babenko + Lemptitsky的方法非常相似。

您也可以查看我的相关答案:

  1. 两组高维点:在另一组中find最近的邻居
  2. 最近邻查询在不同数据结构上的运行时间比较
  3. PCL kd-tree的实现非常缓慢

欧几里德距离是寻找最近邻居的好方法吗? 如果不是,我有什么select?

我会build议软子空间聚类 ,这是目前很常见的方法,其中计算特征权重以find最相关的维度。 例如,使用欧几里德距离时可以使用这些权重。 见常见问题的维度的诅咒,这篇文章可以启发你:

混合数字和分类数据集的子空间聚类的k-meanstypes聚类algorithm