记得硕士期间完成过一项简单的基于k近邻算法解决文本分类的任务,距离度量函数采用的余弦相似度,当时直接利用Lucene对训练集建倒排索引(建模),分类转化成检索问题。对待分类的新文本,将其转化为query进行检索,然后根据Top-k篇最相关的文本所属类别投票表决新文本的类别。显然,这是一种取巧的方法。
今天从李航博士的《统计学习方法》中看到基于kd-tree实现k近邻法,一种通用的解决方案。但是,当特征空间维数较高时,如接近训练实例规模,其效率迅速下降,几乎接近线性扫描。
请问,大家一般如何实现k近邻算法?是否有更好的方案呢?