用于文本分类的快速KNN算法

摘要

KNN(k Nearest Neighbor)算法是一种简单、有效、非参数的文本分类方法.传统的KNN方法有着样本相似度计算量大的明显缺陷,使其在具有大量高维样本的文本分类中缺乏实用性.提出了一种快速查找精确的k个最近邻的TKNN(Tree-k-Nearest-Neighbor)算法,该算法建立一棵用于查找的树,加速k个最近邻的查找.首先以整个样本集合中心为基准,按照距离中心的距离将所有样本进行排序,并等分L组,作为根结点的孩子,每个孩子以同样方式处理,直到每组样本数量在[k,2k]间为止.根据这棵树查找k个最近邻,减小了查找范围,极大地降低了相似度计算量.