Accelerated k-nearest neighbors algorithm based on principal component analysis for text categorization

摘要

text categorization is a significant technique to manage the surging text data on the Internet. The k-nearest neighbors (kNN)%29&ck%5B%5D=abstract&ck%5B%5D=keyword'>k-nearest neighbors (kNN) algorithm is an effective, but not efficient, classification model for text categorization. In this paper, we propose an effective strategy to accelerate the standard kNN, based on a simple principle: usually, near points in space are also near when they are projected into a direction, which means that distant points in the projection direction are also distant in the original space. Using the proposed strategy, most of the irrelevant points can be removed when searching for the k-nearest neighbors of a query point, which greatly decreases the computation cost. Experimental results show that the proposed strategy greatly improves the time performance of the standard kNN, with little degradation in accuracy. Specifically, it is superior in applications that have large and high-dimensional datasets.