高维数据中最近的邻居？

Question

我曾问一个问题,几天就回来了如何找到一个给定矢量最近的邻居.我的矢量现在是21维,在我继续前进之前,因为我不是来自机器学习领域,也不是数学领域,我开始问自己一些基本问题:

• 欧几里德距离是否是首先找到最近邻居的一个很好的指标？如果没有,我的选择是什么？
• 此外,如何确定确定k邻居的正确阈值？是否有一些分析可以用来计算出这个值？
• 以前,我被建议使用kd-Trees,但维基百科页面清楚地表明,对于高维度,kd-Tree几乎相当于蛮力搜索.在这种情况下,有效找到百万点数据集中最近邻居的最佳方法是什么？

有人可以澄清一些(或所有)上述问题吗？

Answer 1

我目前正在研究这类问题 - 分类,最近邻搜索 - 用于音乐信息检索.

您可能对近似最近邻(ANN)算法感兴趣.这个想法是你允许算法在邻居附近返回(可能不是最近的邻居); 这样做可以降低复杂性.你提到了kd树 ; 这是一个例子.但正如你所说,kd-tree在高维度上表现不佳.实际上,所有当前的索引技术(基于空间划分)都会降级为线性搜索,以获得足够高的维度[1] [2] [3].

在最近提出的ANN算法中,最流行的可能是Locality-Sensitive Hashing(LSH),它将高维空间中的一组点映射到一组箱中,即哈希表[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] Slaney,Casey,"寻找最近邻居的地方敏感哈希",2008年.

Answer 2

I.距离度量

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

• 数据的基础统计分布;

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

• 获取数据的坐标空间.

如果您事先不了解数据采样的分布,至少有一项(记录完备且详尽的)研究得出结论,欧几里德距离是最佳选择.

YEuclidean度量标准用于大型Web推荐引擎以及当前的学术研究.由欧几里德计算的距离具有直观的意义和计算尺度 - 即,欧几里德距离以相同的方式计算,无论这两个点是二维还是二十二维空间.

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

但除了您的数据属于非笛卡尔坐标系的情况之外,距离度量的选择通常并不重要.(参见CS学生的博客文章,通过检查它们对kNN分类器的影响来比较几个距离指标 - 卡方得到最好的结果,但差异并不大;更全面的研究在学术论文中,比较研究最近邻居的距离函数 --Mahalanobis(基本上欧几里德归一化归因于维协方差)是本研究中最好的.

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

X_new = (X_old - mu) / sigma

II.数据结构

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

尽管为此目的应用VT以及随之而来的性能优势,但这并不是持久保存kNN训练数据的最常用方法(请参阅此Microsoft研究报告).这样做的实际意义在于,如果您使用的是"主流"语言(例如,在TIOBE索引中),那么您应该找到一个执行VT的库.我知道在Python和R中,每种语言都有多种选择(例如,CRAN上的R 的voronoi包)

使用VT for kNN就像这样工作::

根据您的数据,随机选择w点 - 这些是您的Voronoi中心.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.

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

从一组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.I我不是这种技术的粉丝,因为它经常会使最近的邻居超重(并伴随着较远的邻居的重量不足); 这一点的重要性在于给定的预测几乎可以完全依赖于单个邻居,这反过来又增加了算法对噪声的敏感度.

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

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

要使用kNN代码计算预测值,您需要确定要预测其响应变量的数据点的n个最近邻居('test instance'),然后为n个邻居中的每个邻居调用weight_gauss函数一次,在每个邻居之间的距离,测试点.该函数将返回每个邻居的权重,然后在加权平均计算中将其用作该邻居的系数.

Answer 3

你所面对的被称为维度的诅咒.运行像PCA或ICA这样的算法有时很有用,以确保您确实需要所有21个维度并可能找到一个线性变换,这将允许您使用少于21的结果质量大致相同.

更新: 我在Rangayyan的一本叫做生物医学信号处理的书中遇到过它们(我希望我能正确记住它).ICA不是一个简单的技术,但它是由芬兰的研究人员开发的,我认为它的Matlab代码可以公开下载.PCA是一种使用更广泛的技术,我相信您应该能够找到它的R或其他软件实现.通过迭代求解线性方程来执行PCA.我很久以前就已经这么做了,以便记住.=)

我们的想法是,在您的情况下,将信号分解为独立的特征向量(实际上是离散的本征函数)和它们的特征值.每个特征值显示每个特征函数为每个测量提供的贡献量.如果特征值很小,你可以非常接近地表示信号而不使用它相应的本征函数,这就是你如何摆脱一个维度.

Answer 4

最佳答案很好但很旧,所以我想加上2016年的答案.

如上所述,在高维空间中,维度的诅咒潜伏在拐角处,使得传统方法(例如流行的kd树)与蛮力方法一样慢.因此,我们转向对近似最近邻搜索(ANNS)的兴趣,这有利于一些准确性,从而加快了过程.你得到了精确NN的良好近似值,具有良好的可行性.

热门话题可能值得:

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

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

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

Answer 5

逐一回答您的问题:

• 不,欧几里德距离在高维空间中是一个坏指标.基本上在高维度上,最近和最远邻居之间几乎没有差别.
• 高维数据中有很多论文/研究,但大多数东西需要大量的数学软化.
• KD树对于高维数据是不好的......一定要避免它

这是一篇很好的论文,可以帮助您开始正确的方向." 在最近邻有意义吗？" 由Beyer等人提供.

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

Answer 6

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

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

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