高维数据中的最近邻？

我目前正在研究此类问题——分类、最近邻搜索——用于音乐信息检索。

您可能对近似最近邻 (ANN) 算法感兴趣。这个想法是您允许算法返回足够近的邻居（可能不是最近的邻居）；这样做可以降低复杂性。你提到了kd-tree；这是一个例子。但正如你所说，kd-tree 在高维上效果不佳。事实上，所有当前的索引技术（基于空间分区）都退化为对足够高维度的线性搜索[1][2][3]。

在最近提出的 ANN 算法中，也许最流行的是局部敏感散列（LSH），它将高维空间中的一组点映射到一组 bin 中，即散列表 [1][3]。但与传统散列不同，位置敏感散列将附近的点放入同一个 bin。

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 年。

---

一、距离度量

首先，数据集中的特征（列）数量不是选择用于 kNN 的距离度量的因素。有不少已发表的研究正是针对这个问题，通常的比较基础是：

您数据的基本统计分布；

构成数据的特征之间的关系（它们是独立的——即协方差矩阵是什么样的）；和

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

如果您事先不知道从中采样数据的分布，那么至少有一个（有据可查且详尽的）study 得出结论，欧几里得距离是最佳选择。

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

它对我来说只失败了几次，每个案例欧几里得距离都失败了，因为底层（笛卡尔）坐标系是一个糟糕的选择。而且您通常会认识到这一点，因为例如路径长度（距离）不再是相加的 - 例如，当度量空间是棋盘时，曼哈顿距离比欧几里得更好，同样当度量空间是地球并且您的距离是反式时- 大陆航班，适合极坐标系的距离度量是个好主意（例如，伦敦到维也纳是 2.5 小时，维也纳到圣彼得堡是另外 3 小时，或多或少在同一方向，但伦敦到圣彼得堡. 圣彼得堡不是 5.5 小时，而是 3 小时多一点。）

但除了您的数据属于非笛卡尔坐标系的情况之外，距离度量的选择通常并不重要。 （参见一个 CS 学生的blog post，通过检查它们对 kNN 分类器的影响来比较几个距离度量——卡方给出最好的结果，但差异不大；更全面的研究在学术论文中，{2 }--Mahalanobis（本质上是欧几里得归一化以考虑维度协方差）是本研究中最好的。

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

X_new = (X_old - mu) / sigma

二、数据结构

https://i.stack.imgur.com/uUKgA.png

这不是持久化 kNN 训练数据的最常见方式，尽管为此目的应用 VT 以及随之而来的性能优势已得到充分证明（参见例如 Microsoft Research report）。这样做的实际意义在于，如果您使用的是“主流”语言（例如，在 TIOBE Index 中），那么您应该找到一个库来执行 VT。我知道在 Python 和 R 中，每种语言都有多个选项（例如，用于 R 的 voronoi 包在 CRAN 上可用）

对 kNN 使用 VT 的工作方式如下：

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

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

所以想象一下你有一百万个数据点......如果这些点被保存在一个普通的二维数据结构中，或者在一个 kd-tree 中，你将为每个响应变量的新数据点执行平均几百万个距离计算你想预测。当然，这些计算是在单个数据集上执行的。对于 V/T，最近邻搜索分两步依次执行，针对两个不同的数据群——首先针对 Voronoi 中心，然后一旦找到最近的中心，单元格内的点对应于搜索该中心以找到实际的最近邻居（通过连续的距离计算）结合起来，这两个查找比单个蛮力查找要快得多。这很容易看出：对于 1M 数据点，假设您选择 250 个 Voronoi 中心来细分您的数据空间。平均而言，每个 Voronoi 单元将有 4,000 个数据点。因此，您无需执行平均 500,000 次距离计算（蛮力），而是执行得更少，平均仅为 125 + 2,000。

三、计算结果（预测的响应变量）

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

W/r/t 第一个组件，您可以通过解决优化问题（非常类似于最小二乘优化）来确定 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 个邻居中的每一个调用一次，通过在每个邻居之间的距离测试点。此函数将返回每个邻居的权重，然后将其用作该邻居在加权平均计算中的系数。

---

您所面临的就是 curse of dimensionality。有时运行诸如 PCA 或 ICA 之类的算法很有用，以确保您确实需要所有 21 个维度，并可能找到一个线性变换，这将允许您使用少于 21 个且结果质量大致相同.

更新：我在 Rangayyan 的《生物医学信号处理》一书中遇到了它们（我希望我没记错）。 ICA 不是一项简单的技术，但它是由芬兰的研究人员开发的，我认为它的 Matlab 代码可以公开下载。 PCA 是一种使用更广泛的技术，我相信您应该能够找到它的 R 或其他软件实现。 PCA 是通过迭代求解线性方程来执行的。我很久以前做过，不记得怎么做的了。 = )

这个想法是您将信号分解为独立的特征向量（实际上是离散的特征函数）及其特征值，在您的情况下为 21。每个特征值显示每个特征函数对您的每个测量值的贡献量。如果特征值很小，您可以非常接近地表示信号，而无需使用其相应的特征函数，这就是您摆脱维度的方式。

---

最佳答案很好但很旧，所以我想添加一个 2016 年的答案。

如前所述，在高维空间中，维度的诅咒潜伏在拐角处，使得传统方法（例如流行的 kd 树）变得像蛮力方法一样缓慢。因此，我们将兴趣转向近似最近邻搜索 (ANNS)，它有利于提高一些准确性，从而加快了这一过程。您可以很好地近似精确的 NN，并且具有很好的概率。

可能值得的热门话题：

LSH 的现代方法，例如 Razenshteyn 的方法。 RKD 森林：随机 kd 树 (RKD) 的森林，如 FLANN 中所述，或者在我参与的更新方法中，kd-GeRaF。 LOPQ 代表局部优化产品量化，如此处所述。它与新的 Babenko+Lemptitsky 的方法非常相似。

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

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

---

一一回答您的问题：

不，欧几里得距离在高维空间中是一个不好的度量。基本上在高维中，数据点之间存在很大差异。这减少了给定数据点与其最近和最远邻居之间距离的相对差异。

很多论文/研究都存在于高维数据中，但大多数东西都需要大量的数学复杂性。

KD树对高维数据不利……一定要避免

这是一篇很好的论文，可以帮助您朝着正确的方向开始。 “When in Nearest Neighbour meaningful？”拜尔等人。

我使用尺寸为 20K 及以上的文本数据。如果您需要一些与文本相关的建议，我也许可以为您提供帮助。

---

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

要使用的最近邻的数量取决于数据的类型、有多少噪音等。没有一般规则，您只需通过尝试范围内的所有值来找到最适合您的特定数据和问题的值.人们有一个直观的认识，即数据越多，需要的邻居就越少。在您拥有所有可能数据的假设情况下，您只需要寻找单个最近邻进行分类。

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

---

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

但此外，据我所知，kd-trees 仅适用于 Lp 范数，并且存在距离集中效应，这使得基于距离的算法随着维度的增加而退化。

有关更多信息，您可能需要阅读维度诅咒及其各种变体（它不止一个方面！）

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

---

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

---

我认为布尔特征的 tf-idf 上的余弦对于大多数问题都适用。这是因为它在许多搜索引擎（如 Lucene）中使用了久经考验的启发式方法。根据我的经验，欧几里得距离对于任何类似文本的数据都显示不好的结果。可以通过训练数据和蛮力参数选择来选择不同的权重和 k 示例。

---

iDistance 可能是高维数据中精确 knn 检索的最佳选择。您可以将其视为近似的 Voronoi 镶嵌。

---

我遇到过同样的问题，可以说以下。

欧几里得距离是一个很好的距离度量，但是它在计算上比曼哈顿距离更昂贵，有时会产生稍差的结果，因此，我会选择后者。 k的值可以根据经验找到。您可以尝试不同的值并检查生成的 ROC 曲线或其他一些精度/召回度量，以便找到可接受的值。欧几里得距离和曼哈顿距离都尊重三角不等式，因此您可以在度量树中使用它们。事实上，当数据超过 10 个维度时，KD-trees 的性能会严重下降（我自己也遇到过这个问题）。我发现 VP-trees 是一个更好的选择。

---

如果您在查看所有点的 5% 后尽早退出，KD 树在 21 个维度上工作得很好。 FLANN 这样做（和其他加速）以匹配 128 维 SIFT 向量。 （不幸的是，FLANN 只做欧几里得度量，而快速而可靠的 scipy.spatial.cKDTree 只做 Lp 度量；这些对于您的数据可能足够，也可能不足够。）当然有速度和准确性的权衡这里。

（如果你能描述你的 Ndata、Nquery、数据分布，那可能有助于人们尝试类似的数据。）

在我的旧 mac ppc 上添加了 4 月 26 日，cKDTree with cutoff 的运行时间，以给出一个非常粗略的可行性概念：

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 order curve。 3维很容易。

---

不久前我有一个类似的问题。对于快速近似最近邻搜索，您可以使用来自 spotify 的 annoy 库：https://github.com/spotify/annoy

这是 Python API 的一些示例代码，在 C++ 中进行了优化。

from annoy import AnnoyIndex
import random

f = 40
t = AnnoyIndex(f, 'angular')  # Length of item vector that will be indexed
for i in range(1000):
    v = [random.gauss(0, 1) for z in range(f)]
    t.add_item(i, v)

t.build(10) # 10 trees
t.save('test.ann')

# ...

u = AnnoyIndex(f, 'angular')
u.load('test.ann') # super fast, will just mmap the file
print(u.get_nns_by_item(0, 1000)) # will find the 1000 nearest neighbors

它们提供不同的距离测量。您要应用哪种距离测量在很大程度上取决于您的个人问题。还要首先考虑对某些维度的重要性进行预缩放（意思是加权）。这些维度或特征重要性权重可能通过熵损失之类的方法计算，或者如果您有监督学习问题 gini impurity gain 或 mean average loss，您可以在其中检查机器学习模型的性能差多少，如果您打乱这些维度值。

通常向量的方向比它的绝对值更重要。例如在文本文档的语义分析中，我们希望文档向量在语义相似时接近，而不是长度相似。因此，我们既可以将这些向量归一化为单位长度，也可以使用角距离（即余弦相似度）作为距离度量。

希望这会有所帮助。

---

欧几里得距离是首先找到最近邻居的好指标吗？如果没有，我有什么选择？

我建议使用软子空间聚类，这是当今非常常见的一种方法，通过计算特征权重来找到最相关的维度。例如，您可以在使用欧几里得距离时使用这些权重。有关常见问题，请参阅维度诅咒，本文也可以以某种方式启发您：

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

---