高维数据中最近的邻居？

几天前我问了一个问题，如何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近似。

最后， LSH与0 < 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的原始值就是86,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例子。

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

欧几里德距离是一个很好的距离度量，但是它的计算量比曼哈顿距离要大，有时产生的结果也会稍微差一点，所以我select后者。
k的值可以凭经验find。您可以尝试不同的值，并检查生成的ROC曲线或一些其他精度/召回措施，以find可接受的值。
欧几里德距离和曼哈顿距离都尊重三angular形的不平等，因此你可以在度量树中使用它们。事实上，当数据超过10个维度时（我自己也经历过这个问题），KD树的performance严重退化。我发现副树是一个更好的select。

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

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

热门话题可能值得：

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

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

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

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

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

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

高维数据中最近的邻居？

MATLAB中的最近邻插值algorithm