KNN(k Nearest Neighbor)算法是一种简单、有效、非参数的文本分类方法.传统的KNN方法有着样本相似度计算量大的明显缺陷,使其在具有大量高维样本的文本分类中缺乏实用性.提出了一种快速查找精确的k个最近邻的TKNN(Tree-k-Nearest-Neighbor)算法,该算法建立一棵用于查找的树,加速k个最近邻的查找.首先以整个样本集合中心为基准,按照距离中心的距离将所有样本进行排序,并等分L组,作为根结点的孩子,每个孩子以同样方式处理,直到每组样本数量在[k,2k]间为止.根据这棵树查找k个最近邻,减小了查找范围,极大地降低了相似度计算量.
[1] 杨建良, 王永成. 基于KNN与自动检索的迭代近邻法在自动分类中的应用 [J]. 情报学报 2004.doi:10.3969/j.issn.1000-0135.2004.02.002
[2] 王晓晔, 王正欧, WANG Xiao-ye, Wang Zheng-ou. K-最近邻分类技术的改进算法 [J]. 电子与信息学报 2005.
[3] 李荣陆, 胡运发. 基于密度的kNN文本分类器训练样本裁剪方法 [J]. 计算机研究与发展 2004.
[4] 王煜, 王正欧, WANG Yu, WANG Zheng-ou. 基于模糊决策树的文本分类规则抽取 [J]. 计算机应用 2005.
[5] Zaher Al Aghbari. Array-index: a plug&search K nearest neighbors method for high-dimensional data [J]. Data & knowledge engineering 2005, 3(3).
