为了账号安全,请及时绑定邮箱和手机立即绑定

高维数据中的最近邻居?

高维数据中的最近邻居?

我几天前问了一个问题,该问题是如何找到给定向量的最近邻居。我的向量现在是21维,在继续下一步之前,因为我既不是机器学习也不是数学领域的专家,所以我开始问自己一些基本问题:欧几里得距离是一个很好的度量标准,可以用来首先找到最近的邻居?如果没有,我有什么选择?另外,如何确定用于确定k个邻居的正确阈值?是否可以进行一些分析以找出该值?以前,有人建议我使用kd-Trees,但Wikipedia页面上明确指出,对于高维,kd-Tree几乎等同于蛮力搜索。在那种情况下,有效地找到一百万个点数据集中的最近邻居的最佳方法是什么?有人可以澄清以上部分(或全部)问题吗?
查看完整描述

3 回答

?
Smart猫小萌

TA贡献1911条经验 获得超7个赞

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

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

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

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

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

最后,LSH与的任何Lp规范兼容0 < p <= 2。因此,要回答第一个问题,您可以将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年。


查看完整回答
反对 回复 2019-10-14
  • 3 回答
  • 0 关注
  • 944 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信