我在几天前发了一个问题，询问如何找到给定向量的最近邻。我的向量现在有21个维度，然而由于我不是机器学习或数学领域的人，所以在进一步进行之前，我开始思考一些基本问题：
有没有人能够澄清上述某些（或全部）问题？
我目前研究音乐信息检索中的分类和最近邻搜索等问题。
您可能对近似最近邻（Approximate Nearest Neighbor，ANN）算法感兴趣。这种算法的思想是允许算法返回足够接近的相邻点（可能不是最近邻），从而减少复杂度。您提到了kd树，它是其中一种例子。但正如您所说，kd树在高维下效果很差。实际上，所有基于空间划分的现有索引技术都会在足够高的维度下退化为线性搜索[1][2][3]。
在近期提出的ANN算法中，最受欢迎的可能是局部敏感哈希（Locality-Sensitive Hashing，LSH），它将高维空间中的一组点映射到一组桶中，即哈希表[1][3]。但与传统哈希不同，局部敏感哈希将附近的点放入同一个桶中。
LSH有一些巨大的优势。首先，它很简单。只需计算数据库中所有点的哈希值，然后从中创建哈希表。要查询，只需计算查询点的哈希值，然后从哈希表中检索所有位于同一桶中的点。
其次，有严格的理论支持其性能。可以证明查询时间与数据库的大小成亚线性关系，即比线性搜索更快。速度快多少取决于我们可以容忍多少近似值。
最后，LSH可与任何Lp范数兼容，其中0 < p <= 2。因此，回答您的第一个问题，您可以使用Euclidean距离度量来使用LSH，或者使用曼哈顿（L1）距离度量来使用它。还有Hamming距离和余弦相似度的变种。
在2008年IEEE信号处理杂志中，Malcolm Slaney和Michael Casey写了一篇不错的概述[4]。
局部敏感哈希（LSH）似乎已经被应用到各个领域，你可能想试试。
[1] Datar, Indyk, Immorlica, Mirrokni，“基于p稳定分布的局部敏感哈希方案”，2004。
[2] Weber, Schek, Blott，“高维空间相似性搜索方法的定量分析与性能研究”，1998。
[3] Gionis, Indyk, Motwani，“通过哈希在高维度中进行相似性搜索”，1999。
[4] Slaney, Casey，“利用局部敏感哈希查找最近邻居”，2008。
d，其中d[k]是具有键k的一个bin。d[k]包含所有哈希值为k的点的标签。然后，您只需要计算每个点的哈希值。请参见[4]中的公式（1）或[1]中的第3节。 - Steve TjoaI. 距离度量
首先，在选择kNN中使用的距离度量时，数据集中特征（列）的数量并不是一个因素。已经有很多发表的研究专门针对这个问题，比较常见的基础是：
你的数据的潜在统计分布；
构成你的数据的特征之间的关系（它们是否相互独立-即协方差矩阵长什么样）；和
从中获取数据的坐标空间。
如果你没有关于你的数据被采样自哪种分布的先前知识，至少有一项（经过充分文献记录和详细描述的）研究认为欧氏距离是最佳选择。
在巨型网络推荐引擎以及当前学术研究中，欧几里得度量被用作计算距离的方法。欧几里得距离具有直观的意义，并且计算规模可扩展——即无论两点处于二维空间还是22维空间中，欧几里得距离的计算方式都相同。但除了那些数据属于非笛卡尔坐标系的情况外，距离度量的选择通常并不重要。 （请参见这位CS学生的博客文章，通过检查距离度量对kNN分类器的影响来比较几种距离度量-卡方距离给出了最佳结果，但差异并不大; 一份更全面的研究在学术论文中，最近邻距离函数的比较研究-马哈拉诺比斯（基本上是欧几里得距离通过考虑维度协方差而归一化）在这项研究中表现最佳。）
重要提示：为了使距离度量计算有意义，您必须重新缩放数据——很少有可能构建一个kNN模型来生成准确的预测而不进行此操作。例如，如果您正在构建一个kNN模型来预测运动表现，并且您的期望变量是身高（厘米）、体重（千克）、体脂肪（%）和静息心率（每分钟心跳数），那么典型的数据点可能看起来像这样：[180.4，66.1，11.3，71]。显然，距离计算将被身高主导，而体脂肪百分比的贡献几乎可以忽略不计。换句话说，如果数据以不同的方式报告，例如将体重以克为单位而不是千克为单位，则原始值86.1将变成86100，这将对结果产生很大影响，这正是您不想要的。最常见的缩放技术可能是减去平均值并除以标准差（平均值和标准差分别针对数据集中的每一列或特征进行计算；X指数据行中的单个条目/单元格）：
X_new = (X_old - mu) / sigma
II. 数据结构
如果您关心kd树结构的性能，那么Voronoi Tessellation是一个概念上简单的容器，但它将显著提高性能并比kd树更好地扩展。
虽然这不是持久化kNN训练数据的最常见方式，但VT的应用以及随之而来的性能优势已有充分记录（例如，请参阅此Microsoft Research报告）。这个实际意义在于，只要您使用的是“主流”语言（例如在TIOBE指数中），那么您应该能够找到执行VT的库。我知道在Python和R中，每种语言都有多个选项（例如，在CRAN上可用的R软件包voronoi）。
使用VT进行kNN的工作方式如下：
从您的数据中随机选择w个点 - 这些是您的Voronoi中心。 Voronoi单元封装了所有最接近每个中心的相邻点。想象一下，如果为每个Voronoi中心分配不同的颜色，那么分配给给定中心的每个点都会被涂上该颜色。只要您具有足够的密度，这样做将很好地显示每个Voronoi中心的边界（作为分隔两种颜色的边界）。
如何选择Voronoi中心？我使用两条正交线指南。在随机选择w个点之后，计算训练数据的VT。接下来检查分配给每个Voronoi中心的数据点数量--这些值应该大致相同（假设你的数据空间具有均匀的点密度）。在二维空间中，这会导致大小相同的VT瓷砖。这是第一条规则，这是第二条规则。通过迭代来选择w--以w为可变参数运行kNN算法，并测量性能（查询VT返回预测所需的时间）。def weight_gauss(dist, sig=2.0) :
return math.e**(-dist**2/(2*sig**2))
顶尖答案都是不错的，但都比较老，所以我想补充一个2016年的答案。
以下是可能有价值的热门话题：
逐一回答您的问题：
以下是一篇不错的论文，可以帮助您朝着正确的方向开始学习：“When in Nearest Neighbour meaningful” by Beyer et all. (英文原版链接)
我处理的是维度为20K及以上的文本数据。如果您需要一些与文本相关的建议，我也许能够帮到您。
kd树在高维数据中的表现不佳。因为修剪步骤不能提供太多帮助，因为最接近的边 - 一维偏差 - 几乎总是小于已知最近邻居的全维偏差。
此外，据我所知，kd树只适用于Lp范数，并且存在距离集中效应，使得随着维数增加，基于距离的算法会退化。
如果需要更多信息，您可以阅读关于维度诅咒及其各种变体的内容（它有不止一个方面！）
我并不认为仅仅盲目地近似欧几里得最近邻居，例如使用LSH或随机投影，有很大用处。可能需要首先使用一个更精细调整的距离函数！
（如果您能描述Ndata，Nquery，数据分布，这可能有助于人们尝试类似的数据。）
添加于4月26日，在我的旧mac ppc上带有截止时间的cKDTree运行时间，以给出可行性的非常粗略的想法：
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
很多事情取决于你想知道最近邻居的原因。如果你真正想要找到数据集的模式，那么可以研究均值漂移算法http://en.wikipedia.org/wiki/Mean-shift。
我认为，在布尔特征的tf-idf上使用余弦函数对大多数问题都是有效的。这是因为它是一种经过时间验证的启发式算法，用于许多搜索引擎，如Lucene。在我的经验中，欧几里得距离对于任何类似文本的数据都表现不佳。选择不同的权重和k个实例可以通过训练数据和暴力参数选择来完成。