Deep Learning Specialization on Coursera

如何实现k近邻算法?

+4 投票

记得硕士期间完成过一项简单的基于k近邻算法解决文本分类的任务,距离度量函数采用的余弦相似度,当时直接利用Lucene对训练集建倒排索引(建模),分类转化成检索问题。对待分类的新文本,将其转化为query进行检索,然后根据Top-k篇最相关的文本所属类别投票表决新文本的类别。显然,这是一种取巧的方法。

今天从李航博士的《统计学习方法》中看到基于kd-tree实现k近邻法,一种通用的解决方案。但是,当特征空间维数较高时,如接近训练实例规模,其效率迅速下降,几乎接近线性扫描。

请问,大家一般如何实现k近邻算法?是否有更好的方案呢?

时间: 2012年 5月 31日 分类:机器学习 作者: fandywang (2,370 基本)
编辑 2012年 5月 31日 作者:fandywang

1个回答

+2 投票
一般的做法是对数据进行划分,在子空间上构建邻居图,该过程可以重复好几次,从而形成层次化的子空间,该过程可以被看作是一个k近邻图构造的方法,用来实现近似的k近邻算法。为了增加k近邻查找的准确性,一般还会辅助增加一个近邻传递(用来解决子空间划分之后的邻居遗漏问题)。用于高维空间数据的高效k近邻问题可以看一下CV领域,针对图像等多媒体数据的处理。有一篇参考,是CVPR 2012的文章 http://research.microsoft.com/en-us/um/people/jingdw/pubs/CVPR12-GraphConstruction.pdf

还有一个思路是,可以看一下近年来数据库方面在reverse k近邻的研究,特别是之前港科大yufeng tao的工作,主要思想也是数据切分,他这里利用R-tree等空间数据库的索引技术来处理。这里reverse k近邻的含义是给定一个任意维度的点,找出所有点集,使得给定点是这些点的k近邻。参看一篇早期VLDB的文章 http://www.vldb.org/conf/2004/RS20P1.PDF
已回复 2012年 6月 1日 作者: haofen (680 基本)
NLPJob

Text Summarization

Keyword Extraction

Text Processing

Word Similarity

Best Coursera Course

Best Coursera Courses

Elastic Patent

本站架设在 DigitalOcean 上, 采用创作共用版权协议, 要求署名、非商业用途和保持一致. 转载本站内容必须也遵循“署名-非商业用途-保持一致”的创作共用协议.