基于DBSCAN聚类的改进KNN文本分类算法

K最近邻算法(KNN)在分类时,需要计算待分类样本与训练样本集中每个样本之间的相似度.当训练样本过多时,计算代价大,分类效率降低.因此,提出一种基于DBSCAN聚类的改进算法.利用DBSCAN聚类消除训练样本的噪声数据.同时,对于核心样本集中的样本,根据其样本相似度阈值和密度进行样本裁剪,以缩减与待分类样本计算相似度的训练样本个数.实验表明此算法能够在保持基本分类能力不变的情况下,有效地降低分类计算量.

An Improved KNN Text Categorization Algorithm Based on DBSCAN

In order to find k neighbors of classification, KNN algorithm needs to calculate the similarity between the test sample and every training sample in sample space, with the increasing in the number of training samples, the computational overhead becomes higher. Aiming at the problem of the KNN, this paper proposes an improved algorithm based on DBSCAN to reduce the number of training samples. The noisy data in sample space were reduced with DBSCAN algorithm, furthermore, the part of highly similar samples in kernel set of training data were reduced according to the similarity threshold and density. It is shown that the improved method can reduce computational overhead effectively.