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

A Fast KNN Algorithm Applied to Web Text Categorization

KNN算法是一种简单、有效、非参数的web文本分类方法。传统KNN方法的明显缺陷是样本相似度的计算量很大，使其在具有大量高维样本的web文本分类中缺乏实用性。本文提出一种快速查找精确的k个最近邻的FKNN（Fast-k-Nearest-Neighbor）算法。FKNN算法首先选择一个样本作为基准点，并将所有样本按照距基准样本的距离进行排序并建立索引表，然后根据索引表和有序队列查找k个最近邻，减小了查找范围，极大降低了相似度计算量。

The KNN is a simple, valid and non-parameter method applied to WEB text categorization. The traditional KNN has a fatal defect that time of similarity computing is huge. The practicality will he lost when the KNN is applied to WEB text categorization with high dimension and huge samples. In this paper, a method called FKNN （Fast-k -Nearest-Neighbor） is presented which can search the k nearest neighbors quickly. In the method, all samples are sorted based on the similarity between itself and the fiducial sample, k nearest neighbors are searched in the sorted queue and the index is created, then the searching scope is reduced. Subsequently the time of similarity computing is decreased largely.