高维数据中的最近邻居?
language-agnostic
machine-learning
5
0

我几天前问了一个问题,问题是如何找到给定向量的最近邻居。我的向量现在是21维,在我进一步研究之前,因为我既不属于机器学习领域也不属于数学领域,所以我开始问自己一些基本问题:

  • 欧几里得距离是一个很好的度量标准,可以用来首先找到最近的邻居?如果没有,我有什么选择?
  • 另外,如何确定用于确定k个邻居的正确阈值?是否可以进行一些分析以找出该值?
  • 以前,有人建议我使用kd-Trees,但Wikipedia页面上明确指出,对于高维,kd-Tree几乎等同于蛮力搜索。在那种情况下,有效地找到一百万点数据集中的最近邻居的最佳方法是什么?

有人可以澄清以上部分(或全部)问题吗?

参考资料:
Stack Overflow
收藏
评论
共 10 个回答
高赞 时间 活跃

我遇到了同样的问题,可以说以下内容。

  1. 欧几里得距离是一个很好的距离度量标准,但是它在计算上比曼哈顿距离更昂贵,有时结果会稍差一些,因此,我选择后者。

  2. k的值可以凭经验找到。您可以尝试使用其他值,并检查生成的ROC曲线或其他一些精度/召回率指标,以找到可接受的值。

  3. 欧几里得距离和曼哈顿距离都遵守Triangle不等式 ,因此您可以在度量树中使用它们。确实,当数据的维度超过10个时,KD树的性能就会严重下降(我自己也遇到了这个问题)。我发现VP树是更好的选择。

收藏
评论

我认为布尔功能的tf-idf上的余弦会很好地解决大多数问题。那是因为它在Lucene等许多搜索引擎中使用了久经考验的启发式方法。根据我的经验,欧氏距离对任何类似文本的数据都显示不好的结果。可以使用训练数据和蛮力参数选择来选择不同的权重和k个示例。

收藏
评论

您所面临的被称为维数诅咒 。有时运行诸如PCA或ICA之类的算法很有用,以确保您确实需要全部21个维度,并可能找到一个线性变换,该变换可使您使用少于21个维度且结果质量大致相同。

更新:我在Rangayyan的一本名为《生物医学信号处理》的书中遇到了它们(我希望我能正确记住它)。 ICA并非微不足道的技术,但它是由芬兰的研究人员开发的,我认为该工具的Matlab代码可公开下载。 PCA是一种使用更广泛的技术,我相信您应该能够找到它的R或其他软件实现。 PCA通过迭代求解线性方程式来执行。我做这件事太久了,以至于还记得如何。 =)

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

收藏
评论

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

使用的最近邻居的数量根据数据类型,噪声多少等而变化。没有通用规则,您只需尝试范围内的所有值即可找到最适合您的特定数据和问题的方法。人们有一个直观的认识,即数据越多,所需的邻居就越少。在假设条件下,您拥有所有可能的数据,则只需寻找单个最近邻居即可进行分类。

已知k最近邻方法在计算上很昂贵。这是人们转向支持向量机等其他算法的主要原因之一。

收藏
评论

对于高维数据,kd树确实无法很好地工作。由于修剪步骤不再有多大帮助,因为最接近的边缘(一维偏差)几乎总是小于到已知的最近邻居的全尺寸偏差。

但是此外,就我所知,kd树仅适用于Lp范数,并且距离集中效应使基于距离的算法随着维数的增加而降低。

有关更多信息,您可能需要阅读维数的诅咒以及它的各种变体(它不止一个方面!)

我不认为盲目逼近欧几里得最近的邻居有很多用处,例如使用LSH或随机投影。首先可能需要使用更精细的距离功能!

收藏
评论

最佳答案不错,但是很老,所以我想加一个2016年的答案


如上所述,在高维空间中,维数的诅咒潜伏在拐角处,使得传统方法(例如流行的kd树)的速度与蛮力方法一样慢。结果,我们对“ 近似最近邻居搜索”(ANNS)产生了兴趣,该搜索出于某种准确性的考虑而加快了处理速度。您可以很好地近似精确的NN,并具有良好的可扩展性。


可能值得关注的热门话题:

  1. LSH的现代方法,例如Razenshteyn的方法。
  2. RKD森林FLANN中所述的随机kd树(RKD)的森林,或者我最近参与的kd-GeRaF的一部分
  3. LOPQ它代表局部优化的产品量化,如所描述这里 。这与新的Babenko + Lemptitsky的方法非常相似。

您还可以检查我的相关答案:

  1. 两组高维点:在另一组中找到最近的邻居
  2. 比较不同数据结构上的最近邻居查询的运行时
  3. PCL kd-tree实现极其缓慢
收藏
评论

I.距离度量

首先,数据集中的要素(列)数量不是选择用于kNN的距离度量的因素。已有许多针对这一问题的已发表研究,比较的通常依据是:

  • 您数据的基本统计分布;

  • 构成数据的要素之间的关系(它们是独立的-即协方差矩阵是什么样子);和

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

如果您对数据采样的分布没有先验知识,那么至少一项(有据可查且详尽的) 研究得出结论,欧几里德距离是最佳选择。

YEuclidean指标用于大规模Web推荐引擎以及当前的学术研究。欧几里得距离计算的距离具有直观的含义和计算范围,即,无论两点是二维空间还是二十二维空间,欧几里德距离的计算方式都是相同的。

它对我来说只有几次失败,在每种情况下,欧几里德距离都失败了,因为基础(笛卡尔)坐标系是一个糟糕的选择。而且您通常会认识到这一点,因为例如路径长度(距离)不再是累加的,例如,当公制空间是国际象棋棋盘时,曼哈顿距离要比欧几里得更好,同样,当公制空间是地球并且您的距离是反距离时-洲际飞行,适合极坐标系统的距离度量是一个好主意(例如,伦敦到维也纳是2.5小时,维也纳到圣彼得堡是3小时,或多或少在同一方向,而伦敦到圣地圣彼得堡不是5.5小时,而是3小时多一点。)

但是,除了数据属于非笛卡尔坐标系的情况以外,距离度量的选择通常并不重要。 (请参阅来自CS学生的这篇博文 ,通过检查其对kNN分类器的影响来比较多个距离度量标准-卡方得出最佳结果,但差异并不大;更全面的研究是在学术论文《 比较研究最近邻的距离函数-马哈拉诺比斯(本质上是欧几里得,用尺寸协方差归一化)是本研究中最好的。

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

X_new = (X_old - mu) / sigma


二。数据结构

如果您担心kd-tree结构的性能, Voronoi Tessellation是概念上简单的容器,但是它将大大提高性能,并且比kd-Trees更好地扩展。

t

这不是持久保留kNN训练数据的最常见方法,尽管对此已充分记录了VT的应用以及由此带来的性能优势(例如,参见此Microsoft Research报告 )。这样做的实际意义是,假设您使用的是“主流”语言(例如,在TIOBE Index中 ),那么您应该找到一个执行VT的库。我知道在Python和R中,每种语言都有多个选项(例如, CRAN上提供R的voronoi包)

将VT用于kNN的工作方式如下:

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

如何选择沃罗诺伊中心?我使用两个正交准则。随机选择w点后,为您的训练数据计算VT。接下来检查分配给每个Voronoi中心的数据点的数量-这些值应大致相同(在整个数据空间中均采用统一的点密度)。在二维中,这将导致VT具有相同大小的图块,这是第一条规则,这是第二条规则。通过迭代选择w-使用w作为变量参数运行kNN算法,然后测量性能(通过查询VT返回预测所需的时间)。

因此,假设您有一百万个数据点.....如果这些点被保存在普通的2D数据结构或kd树中,则对于每个其响应变量的新数据点,平均要进行几百万次距离计算您希望预测。当然,这些计算是在单个数据集上执行的。使用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个最近邻居(“测试实例”),然后为n个邻居中的每一个调用weight_gauss函数,该函数将返回每个邻居的权重,然后将其用作加权平均计算中该邻居的系数。

收藏
评论

要一一回答您的问题:

  • 不,在高维空间中,欧几里得距离是一个不好的指标。基本上在高维度上,最近的邻居和最远的邻居之间几乎没有差异。
  • 高维数据中有大量论文/研究,但大多数内容都需要大量的数学知识。
  • KD树不利于高维数据...一定要避免

这是一篇不错的论文,可以帮助您正确地开始工作。 “ 什么时候在最近邻有意义 ?”由Beyer等所有。

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

收藏
评论

我目前正在研究此类问题-分类,最近邻居搜索-以获取音乐信息。

您可能对近似最近邻ANN )算法感兴趣。这个想法是让算法允许返回足够近的邻居 (也许不是最近的邻居)。这样可以减少复杂性。您提到了kd-tree ;那是一个例子。但是正如您所说, kd-tree在高维度上效果不佳。实际上, 所有当前的索引技术(基于空间划分)都降级为对足够高的尺寸进行线性搜索[1] [2] [3]。

在最近提出的ANN算法中,也许最流行的是局部敏感哈希LSH ),它将高维空间中的一组点映射到一组bin中,即哈希表[1] [3]。但是与传统的哈希不同,对位置敏感的哈希将附近的点放置在同一容器中。

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

其次,有一个严格的理论可以支持其性能。可以证明,查询时间在数据库大小上是次线性的,即比线性搜索快。快多少取决于我们可以忍受的近似程度。

最后,对于0 < p <= 2LSH与任何Lp范数兼容。因此,要回答第一个问题,您可以将LSH与欧几里德距离度量标准结合使用,或者将其与曼哈顿(L1)距离度量标准结合使用。汉明距离和余弦相似度也有变体。

Malcolm Slaney和Michael Casey在2008年为IEEE Signal Processing Magazine撰写了不错的综述[4]。

LSH似乎已在所有地方得到应用。您可能需要尝试一下。


[1] Datar,Indyk,Immorlica,Mirrokni,“基于p稳定分布的局部敏感散列方案”,2004年。

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

[3] Gionis,Indyk,Motwani,“通过散列在高维中进行相似性搜索”,1999年。

[4] Slaney,Casey,“对位置敏感的哈希,用于寻找最近的邻居”,2008年。

收藏
评论

对于高维数据中的精确knn检索,iDistance可能是最好的方法。您可以将其视为近似Voronoi消息传递。

收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号