几天前我问了一个关于如何找到给定向量的最近邻居的问题。我的向量现在是 21 维，在我继续之前，因为我不是来自机器学习或数学领域，我开始问自己一些基本问题：
有人可以澄清上述部分（或全部）问题吗？
我目前正在研究此类问题——分类、最近邻搜索——用于音乐信息检索。
您可能对近似最近邻( ANN ) 算法感兴趣。这个想法是您允许算法返回足够近的邻居（可能不是最近的邻居）；这样做可以降低复杂性。你提到了kd-tree；这是一个例子。但正如你所说，kd-tree在高维上效果不佳。事实上，所有当前的索引技术（基于空间分区）都退化为对足够高维度的线性搜索[1][2][3]。
在最近提出的ANN算法中，也许最流行的是局部敏感散列( LSH )，它将高维空间中的一组点映射到一组 bin 中，即散列表 [1][3]。但与传统散列不同，位置敏感散列将附近的点放入同一个 bin。
LSH有一些巨大的优势。首先，它很简单。您只需计算数据库中所有点的哈希值，然后从中创建一个哈希表。要查询，只需计算查询点的哈希，然后从哈希表中检索同一 bin 中的所有点。
其次，有一个严格的理论支持它的表现。可以看出，查询时间在数据库大小上是次线性的，即比线性搜索快。快多少取决于我们可以容忍多少近似值。
最后，LSH与 的任何 Lp 范数兼容0 < p <= 2。因此，要回答您的第一个问题，您可以将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 的距离度量的因素。有不少已发表的研究正是针对这个问题，通常的比较基础是：
您数据的基本统计分布；
构成数据的特征之间的关系（它们是独立的——即协方差矩阵是什么样的）；和
从中获取数据的坐标空间。
如果您事先不了解数据的抽样分布，至少有一项（有据可查且彻底的）研究得出结论，欧几里得距离是最佳选择。
用于大型 Web 推荐引擎以及当前学术研究的 YEuclidean 度量。欧几里得计算的距离具有直观的意义和计算尺度——即欧几里得距离的计算方式相同，无论两点是在二维空间还是在二十二维空间。
它对我来说只失败了几次，每个案例欧几里得距离都失败了，因为底层（笛卡尔）坐标系是一个糟糕的选择。而且您通常会认识到这一点，因为例如路径长度（距离）不再是相加的 - 例如，当度量空间是棋盘时，曼哈顿距离比欧几里得更好，同样当度量空间是地球并且您的距离是反式时- 大陆航班，适合极坐标系的距离度量是个好主意（例如，伦敦到维也纳是 2.5 小时，维也纳到圣彼得堡是另外 3 小时，或多或少在同一方向，但伦敦到圣彼得堡. 圣彼得堡不是 5.5 小时，而是 3 小时多一点。）
但除了您的数据属于非笛卡尔坐标系的情况之外，距离度量的选择通常并不重要。（参见一个 CS 学生的这篇博文，通过检查它们对 kNN 分类器的影响来比较几个距离度量——卡方给出了最好的结果，但差异并不大；更全面的研究在学术论文中，Comparative Study of最近邻的距离函数——Mahalanobis（本质上是欧几里得归一化以考虑维度协方差）在这项研究中是最好的。
一个重要的附带条件：要使距离度量计算有意义，您必须重新缩放你的数据——如果不这样做，很少有可能建立一个 kNN 模型来生成准确的预测。例如，如果您正在构建一个 kNN 模型来预测运动表现，并且您的期望变量是身高 (cm)、体重 (kg)、体脂 (%) 和静息脉搏（每分钟心跳数），那么典型的数据点可能看起来像这样：[ 180.4, 66.1, 11.3, 71 ]。显然，距离计算将以身高为主，而体脂百分比的贡献几乎可以忽略不计。换句话说，如果数据报告不同，体重以克而不是公斤为单位，那么 86.1 的原始值将是 86,100，这将对您的结果产生很大影响，这正是您所做的不想。
X_new = (X_old - mu) / sigma
二、数据结构
如果您担心 kd-tree 结构的性能，Voronoi Tessellation是一个概念上简单的容器，但它会大大提高性能并比 kd-Trees 更好地扩展。
这不是保留 kNN 训练数据的最常用方法，尽管为此目的应用 VT 以及随之而来的性能优势已得到充分证明（例如，请参阅此Microsoft Research 报告）。这样做的实际意义在于，如果您使用的是“主流”语言（例如，在TIOBE 索引中），那么您应该找到一个库来执行 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 个邻居中的每一个调用一次，通过在每个邻居之间的距离测试点。此函数将返回每个邻居的权重，然后将其用作加权平均计算中该邻居的系数。
你所面临的就是所谓的维度诅咒。有时运行诸如 PCA 或ICA之类的算法很有用，以确保您确实需要所有 21 个维度，并可能找到一个线性变换，这将允许您使用少于 21 个维度并获得大致相同的结果质量。
更新：
我在 Rangayyan 的《生物医学信号处理》一书中遇到了它们（我希望我没记错）。ICA 不是一项简单的技术，但它是由芬兰的研究人员开发的，我认为它的 Matlab 代码可以公开下载。PCA 是一种使用更广泛的技术，我相信您应该能够找到它的 R 或其他软件实现。PCA 是通过迭代求解线性方程来执行的。我很久以前做过，不记得怎么做的了。= )
这个想法是您将信号分解为独立的特征向量（实际上是离散的特征函数）及其特征值，在您的情况下为 21。每个特征值显示每个特征函数对您的每个测量值的贡献量。如果特征值很小，您可以非常接近地表示信号，而无需使用其相应的特征函数，这就是您摆脱维度的方式。
热门答案很好但很旧，所以我想加一个2016 年的答案。
如前所述，在高维空间中，维度的诅咒潜伏在拐角处，使得传统方法（例如流行的 kd 树）变得像蛮力方法一样缓慢。因此，我们将兴趣转向近似最近邻搜索 (ANNS)，它有利于提高一些准确性，从而加快了这一过程。您可以很好地近似精确的 NN，并且具有很好的概率。
可能值得的热门话题：
您也可以查看我的相关答案：
一一回答您的问题：
这是一篇很好的论文，可以帮助您朝着正确的方向开始。“什么时候在最近邻有意义？” 拜尔等人。
我使用尺寸为 20K 及以上的文本数据。如果您需要一些与文本相关的建议，我也许可以为您提供帮助。
余弦相似度是比较高维向量的常用方法。请注意，由于它是相似性而不是距离，因此您希望最大化它而不是最小化它。您还可以使用特定领域的方式来比较数据，例如，如果您的数据是 DNA 序列，您可以使用考虑突变概率等的序列相似性。
要使用的最近邻居的数量取决于数据的类型、噪声的大小等。没有一般规则，您只需通过尝试范围内的所有值来找到最适合您的特定数据和问题的值. 人们有一个直观的认识，即数据越多，需要的邻居就越少。在您拥有所有可能数据的假设情况下，您只需要寻找单个最近邻进行分类。
众所周知，k 最近邻方法的计算量很大。这是人们转向支持向量机等其他算法的主要原因之一。
kd-trees indeed won't work very well on high-dimensional data. Because the pruning step no longer helps a lot, as the closest edge - a 1 dimensional deviation - will almost always be smaller than the full-dimensional deviation to the known nearest neighbors.
But furthermore, kd-trees only work well with Lp norms for all I know, and there is the distance concentration effect that makes distance based algorithms degrade with increasing dimensionality.
For further information, you may want to read up on the curse of dimensionality, and the various variants of it (there is more than one side to it!)
I'm not convinced there is a lot use to just blindly approximating Euclidean nearest neighbors e.g. using LSH or random projections. It may be necessary to use a much more fine tuned distance function in the first place!
我认为布尔特征的tf-idf上的余弦对于大多数问题都适用。这是因为它在许多搜索引擎（如 Lucene）中使用了久经考验的启发式方法。根据我的经验，欧几里得距离对于任何类似文本的数据都显示不好的结果。可以通过训练数据和蛮力参数选择来选择不同的权重和 k 示例。
很大程度上取决于您为什么想知道最近的邻居。如果您真正想要的是找到数据集的模式，您可以查看均值偏移算法http://en.wikipedia.org/wiki/Mean-shift 。
如果您在查看所有点的 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
iDistance 可能是高维数据中精确 knn 检索的最佳选择。您可以将其视为近似的 Voronoi 镶嵌。
你可以试试 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 类型聚类算法