用于文本分类的改进KNN算法

An Improved KNN Algorithm Applied to Text Categorization

最近邻分类器是假定局部的类条件概率不变,而这个假定在高维特征空间中无效。因此在高维特征空间中使用k最近邻分类器,不对特征权重进行修正就会引起严重的偏差。本文采用灵敏度法,利用前馈神经网络获得初始特征权重并进行二次降维。在初始权重下,根据样本间相似度采用SS树方法将训练样本划分成若干小区域,以此寻找待分类样本的近似k0个最近邻,并根据近似k0个最近邻和Chi-square距离原理计算新权重,搜索出新的k个最近邻。此方法在付出较小时间代价的情况下,在文本分离中可获得较好的分类精度的提高。

Nearest neighbor classification assumes locally constant class conditional probabilities. The assumption becomes invalid in feature space with high dimension. When KNN classier is used in feature space high dimension, severe bias can be introduced if the weights of features are not amended. In this paper, initial weights of text features are acquired based on sensitivity method firstly, and the second dimension reduce is done. Then training samples are divided into many groups based on sample similarity and the initial weights by using SS tree, k0 approximate nearest neighbors of unknown sample are acquired by using SS tree. Weights are computed again based on k0 approximate nearest neighbors and chi-square distance theory. K nearest neighbors are acquired based on new weights. Little time is spent, but the better accuracy of text categorization is acquired.