一种基于粗糙集的改进KNN文本分类算法

An Improved KNN Text Categorization Algorithm Based on Rough Set

K最近邻算法(KNN)被认为是向量空间模型下最好的分类算法之一。在准确率和召回率方面比较出众,但随着样本数量的增加其相似度计算开销很大。提出一种改进算法RS-KNN,主要是利用粗糙集的相关理论,计算训练样本集中各样本子类的上近似空间和下近似空间,根据待分类文本出现在不同的近似空间。以缩减与待分类样本计算相似度的训练样本个数。实验表明此算法能够有效地降低分类计算开销。

KNN algorithm is efficient text categorization algorithm in recall and precision, but the computation- al overhead of text similarity is higher when the number of texts is larger. Aiming at the problem of the KNN, an improved algorithm named RS-KNN based on rough set theory is proposed. According to the upper approximation space and lower approximation space of sample subsets, the algorithm can classify the part of texts driectly. Results of the experiment indicate the RS-KNN reduce computational overhead of text classification.