高维数据中最近的邻居？

很大程度上取决于你为什么想知道最近的邻居。如果您真正想要的是找到数据集的模式，那么您可以查看均值转移算法 http://en.wikipedia.org/wiki/Mean-shift。

你所面对的是众所周知的 维数灾难。有时候运行一个像 PCA 或者 国际反恐局这样的算法是很有用的，它可以确保你真的需要所有的21个维度，并且可能找到一个线性映射，允许你使用少于21个维度，并且得到大致相同的结果质量。

更新: 我在一本叫做《生医信号处理》的书中遇到了他们(我希望我没有记错)。ICA 不是一个简单的技术，但它是由芬兰的研究人员开发的，我认为它的 Matlab 代码可以公开下载。 PCA 是一种应用更广泛的技术，我相信您应该能够找到它的 R 或其他软件实现。主元分析采用迭代求解线性方程组的方法。我很久以前就这么做了，已经记不得是怎么做的了。= )

这个想法是你把你的信号分解成独立的特征向量(实际上是离散的特征函数)和它们的特征值，在你的情况下是21。每个特征值表示每个特征函数对每个测量值的贡献量。如果一个特征值很小，你可以非常接近地表示这些信号，而不需要使用相应的特征函数，这就是如何去掉维数的方法。

逐一回答你们的问题:

• 不，在高维空间里，欧几里得度量不是一个好的衡量标准。基本上在高维中，数据点之间有很大的差异。这减少了给定数据点与其最近和最远邻居之间的相对差距。
• 很多论文/研究都是高维数据，但大部分内容都需要大量的数学复杂性。
• KD 树不利于高维数据... ... 请务必避免使用它

这里有一篇不错的论文可以帮助你朝着正确的方向开始。

我的工作与文本数据的尺寸20K 及以上。如果你需要一些文字相关的建议，我也许可以帮助你。

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

使用的最近邻的数量取决于数据的类型，有多少噪声，等等。没有一般的规则，您只需要通过尝试范围内的所有值来找到对您的特定数据和问题最有效的方法。人们有一种直观的理解，那就是数据越多，你需要的邻居就越少。在一个假设的情况下，您拥有所有可能的数据，您只需要寻找一个最近的邻居进行分类。

众所周知，k 最近邻方法的计算开销很大。这是人们求助于支持向量机等其他算法的主要原因之一。

我认为对于大多数问题，布尔特性的 Tf-idf上的余弦都能很好地工作。这是因为它经过时间验证的启发式应用于许多搜索引擎，如 Lucene。根据我的经验，欧几里得度量对于任何类似文本的数据都显示出不好的结果。通过训练数据和蛮力参数的选择，可以选择不同的权重和 k 样本。

距离度量

首先，在选择 kNN 中使用的距离度量时，数据集中的特征(列)的数量不是一个因素。有相当多的已发表的研究正是针对这个问题，通常的比较基础是:

• 潜在的统计数据 你的资料分发

• 特征之间的关系 组成你的数据(它们是 独立的——也就是说，什么是 协方差矩阵) ;

• 坐标空间 数据获得

如果你事先不知道你的数据是从哪个分布取样的，至少有一个(有充分的文档记录和详尽的) 学习认为欧几里得度量是最好的选择。

在大规模网络推荐引擎和当前学术研究中使用的 YEuclidean 度量。欧几里得计算的距离具有直观的意义和计算尺度——也就是说，无论这两个点是在二维空间还是在二十二维空间，欧几里得度量的计算方法都是相同的。

对我来说，这种欧几里得度量只失败过几次，每一次失败都是因为潜在的(笛卡尔)坐标系是一个糟糕的选择。你通常会意识到这一点，因为例如路径长度(距离)不再是累加的——例如，当度量空间是一个棋盘，曼哈顿距离比欧几里得更好，同样，当度量空间是地球，你的距离是跨大陆飞行，适合一个极坐标系的距离度量是一个好主意(例如，伦敦到维也纳是2.5小时，维也纳到圣彼得堡是另一个3小时，或多或少在同一个方向，但伦敦到圣彼得堡不是5.5小时，而是略超过3小时)

但是，除了那些你的数据属于非笛卡尔坐标系的情况之外，距离度量的选择通常并不重要。(参见来自 CS 学生的这个 博客文章，通过检查它们对 kNN 分类器的影响来比较几个距离度量——卡方给出了最好的结果，但差异并不大; 一个更全面的研究是在学术论文中，最近邻距离函数的比较研究—— Mahalanobis (基本上欧几里得标准化来说明维度协方差)是这项研究中最好的。

一个重要的附加条件是: 为了使距离度量计算有意义，必须使用 重新缩放数据——如果不这样做，很少有可能构建一个 kNN 模型来生成准确的预测。例如，如果您正在构建一个 kNN 模型来预测运动员的表现，您的期望变量是身高(cm) ，体重(kg) ，体脂(%)和静息脉搏(每分钟搏动) ，那么一个典型的数据点可能看起来像这样: [180.4,66.1,11.3,71]。很明显，距离的计算将以身高为主，而体脂百分比的贡献几乎可以忽略不计。换句话说，如果数据报告的方式不同，那么体重是以克为单位，而不是以千克为单位，那么86.1的原始值，将是86.100，这将对你的结果有很大的影响，这正是你不想要的。可能最常见的缩放技术是减去平均值，然后除以标准差(平均值和标准差是指为每一列或该数据集中的特征分别计算的数据，X 是指数据行中的一个单独的条目/单元格) :

X_new = (X_old - mu) / sigma

二、数据结构

如果您关心 kd-tree 结构的性能，那么 (咒语)在概念上是一个简单的容器，但是它将比 kd-tree 更好地提高性能和伸缩性。

这并不是持久化 kNN 训练数据的最常见方法，尽管 VT 在这方面的应用以及随之而来的性能优势已经被很好地记录下来了(参见这个 微软研究报告)。这样做的实际意义在于，如果您使用的是“主流”语言(例如，在 TIOBE 索引中) ，那么您应该找到一个库来执行 VT。我知道在 Python 和 R 中，每种语言都有多个选项(例如，在 CRAN上可以使用针对 R 的 我们走包)

对 kNN 使用 VT 的工作原理如下: :

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

如何选择 Voronoi 中心？我使用两个正交准则。随机选择 w 点后，计算训练数据的 VT。接下来检查分配给每个 Voronoi 中心的数据点的数量——这些值应该大致相同(给定数据空间中的统一点密度)。在二维空间中，这将导致具有相同大小瓷砖的 VT。这是第一条，这是第二条。通过迭代选择 w ——将 w 作为变量参数运行 kNN 算法，并测量性能(通过查询 VT 返回预测所需的时间)。

假设你有一百万个数据点。如果这些点保存在一个普通的2D 数据结构中，或者保存在 kd-tree 中，那么对于您希望预测其响应变量的 每个人新数据点，您将平均执行几百万次距离计算。当然，这些计算是在单个数据集上执行的。使用 v/T，最近邻搜索按照两个步骤一个接一个地执行，针对两个不同的数据种群——首先是针对 Voronoi 中心，然后一旦找到最近的中心，在单元格内对应于该中心的点被搜索以找到实际的最近邻居(通过连续的距离计算)结合起来，这两个搜索要比单一的蛮力搜索快得多。这很容易看到: 对于1M 个数据点，假设您选择250个 Voronoi 中心来细分数据空间。每个 Voronoi 细胞平均有4000个数据点。因此，与平均500,000个距离计算(蛮力)相比，您执行的计算要少得多，平均只有125 + 2,000个。< br/> < br/>

计算结果(预测响应变量)

从一组 kNN 训练数据中计算预测值有两个步骤。第一种方法是标识用于此计算的 n 或 最近邻居的数量。第二个是 如何衡量他们的贡献的预测值。

第一个分量，你可以通过求解一个最佳化问题来确定 n 的最佳值(非常类似于最小二乘优化)。这就是理论; 在实践中，大多数人只使用 n = 3。在任何情况下，对 n = 1、 n = 2、 n = 3等的一组测试实例(计算预测值)运行 kNN 算法并将误差作为 n 的函数绘制出来都很简单。如果你只是想要一个合理的 n 开始的值，再一次，只需要使用 n = 3。

第二个组件是如何权衡每个邻居的贡献(假设 n > 1)。

最简单的加权技术就是把每个邻居乘以一个加权系数，这个系数就是1/(dist * K) ，或者把从邻居到测试实例的距离反过来乘以某个经验导出的常数，K。我不喜欢这个技术，因为它经常会加重最近的邻居的权重(同时也会减轻更远的邻居的权重) ; 这个技术的意义在于，一个给定的预测几乎完全依赖于一个邻居，这反过来增加了算法对噪音的敏感性。

一个必须更好的加权函数是 高斯函数，它基本上避免了这个限制，在 python 中，它看起来像这样:

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

为了使用 kNN 代码计算一个预测值，您需要确定数据点的 n 个最近邻，您希望预测其响应变量(“测试实例”) ，然后调用 weight _ gauss 函数，每个 n 个邻居一次，传递每个邻居之间的距离作为测试点。这个函数将返回每个邻居的权重，然后在加权平均数计算中使用这个权重作为该邻居的系数。

你可以试试 z 次序曲线，对于三维空间来说很简单。

我目前正在研究这些问题——分类、最近邻搜索——以寻找音乐信息检索。

您可能对 最近的邻居(ANN)算法感兴趣。其思想是允许算法充分返回 邻居家附近(可能不是最近的邻居) ; 这样做可以降低复杂性。您提到了 KD 树; 这是一个例子。但是正如你所说，KD 树在高维环境下工作得很差。事实上，所有当前的索引技术(基于空间分割)退化为线性搜索，以获得足够高的维度[1][2][3]。

在最近提出的 ANN算法中，最流行的算法可能是 局部性敏感哈希(LSH) ，它将高维空间中的一组点映射到一组箱，即哈希表[1][3]。但与传统散列不同的是，对地理位置敏感散列将 附近指针放入同一个容器中。

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

其次，有一个严谨的理论来支持它的表现。结果表明，在数据库大小方面，查询时间为 次线性，比线性搜索快。多快取决于我们能容忍多少近似值。

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

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

LSH 的应用似乎无处不在，您可以尝试一下。

[1] Datar，Indyk，Immorlica，Mirrokni，“基于 p 稳定分布的局部性敏感哈希方案”，2004。

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

[3] Gionis，Indyk，Motwani，“高维散列最近邻搜索”，1999。

[4]斯兰尼，凯西，《寻找最近邻居的局部性敏感哈希》 ，2008年。

KD 树在21维空间中工作良好，如果你提前退出, 在看了所有分数的5% 之后。 FLANN 做这个(和其他加速) 匹配128-dim SIFT 向量。(不幸的是，FLANN 只做欧几里德度量, 还有快速而坚固的 Scypy.spatial.cKDTree 只做 Lp 度量; 这些数据对于 你的数据可能足够，也可能不足够。) 这里当然存在速度和精度之间的权衡。

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

增加了4月26日，cKDTree 的运行时间与我的旧 Mac 个人电脑的截止时间，给出了一个非常粗略的可行性想法:

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

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

但是，据我所知，kd 树只能很好地适用于 Lp 范数，并且存在距离集中效应，使得基于距离的算法随着维数的增加而降低。

为了获得更多的信息，你可能需要阅读维数灾难，以及它的各种变体(它有不止一面!)

我不相信盲目地近似欧几里得最近邻有很多用处，例如使用 LSH 或随机投影。首先，可能有必要使用一个更精细的调谐距离函数！

在高维数据的精确已知检索中，iRange 可能是最好的。你可以把它看作是一个近似的 Voronoi 模拟。

我也遇到过同样的问题，可以这么说。

1. 欧几里得度量是一个很好的距离度量标准，但它的计算成本比 曼哈顿距离高，有时会产生稍差的结果，因此，我会选择后者。

2. K 的值可以通过经验找到。您可以尝试不同的值，并检查得到的 ROC 曲线或其他精度/召回度量，以便找到一个可接受的值。

3. 欧几里得距离和曼哈顿距离都尊重 三角不等式，因此可以在公制树中使用它们。事实上，当数据超过10个维度时，KD 树的性能会严重下降(我自己也遇到过这个问题)。我发现 副总统树是一个更好的选择。

首先，欧几里得度量是否是找到最近邻居的一个很好的衡量标准？如果没有，我有什么选择？

我建议使用 软子空间聚类软子空间聚类，这是一种非常常见的方法，通过计算特征权重来找到最相关的维度。例如，你可以在使用欧几里得度量时使用这些砝码。请参阅 维数灾难了解常见问题，这篇文章也可以给你一些启示:

一种 k 均值型聚类算法用于混合数字和数据的子空间聚类 分类数据集

最好的答案是好的，但是很老，所以我想加一个 2016年的答案。

如上所述，在一个高维空间中，维数灾难潜伏在角落里，使得传统的方法，如流行的 k-d 树，像蛮力方法一样缓慢。因此，我们将兴趣转向 近似最近邻搜索(ANNS)，它有利于一定的准确性，从而加快了处理速度。你得到了精确神经网络的一个很好的近似值，具有很好的概率。

有价值的热门话题:

1. LSH的现代方法，如 Razenshteyn。
2. RKD 森林 : 随机 k-d 树(RKD)的森林，如 FLANN, 或者在最近的方法，我是 Kd-GeRaF的一部分。
3. LOPQ 表示局部优化的产品量化，如 给你所述，它与新的 Babenko + Lemptitsky 的 接近非常相似。