刘忠 刘洋 建晓

桂林理工大学信息科学与工程学院 广西 541004

0 引言

文本分类是在预定义的分类体系下，根据文本的特征(内容或属性)，将给定文本与一个或多个类别相关联的过程。常见的分类算法包括：朴素贝叶斯分类法、支持向量机分类法，k-最近邻法，神经网络法，决策树分类法等。

KNN分类法因其思想简单，效果较好得到了广泛的应用。但是KNN是一种惰性学习法，模型仅对训练样本进行简单的存储或稍加处理，一直等到给定一个检验样本时才进行泛化。通过给定的检验样本与和它相似的训练样本进行比较来预测类别。然而，在文本分类中，由于训练样本集很大和文本特征向量的维数很高，计算训练样本的最近邻样本需要花费很多时间。

1 KNN算法的改进

针对KNN算法在文本分类上效率低下的问题，目前已经提出了很多的改进算法。归纳起来有两种途径：①降低文本向量的维度，采用的主要方法有：聚合文本向量中相关联的特征词的方法，基于隐含语义的kNN文本分类方法；②裁剪训练集，使用小样本代替大样本，采用的主要方法有：基于中心向量的分类法，基于质心的文本分类算法，基于簇的K最近邻分类算法，基于粗糙集的快速KNN文本分类算法。

本文提出的基于KD-Tree的KNN文本分类算法就是在保持原有KNN算法训练时间为零的前提下，通过对训练文本向量集建立KD-Tree，测试时，只需要对KD-Tree进行搜索，而不是对整个无序的训练集进行搜索，这样，测试时间为，远小于原始算法的，使得总的分类时间大大减小。……