苟和平， 景永霞， 冯百明， 李 勇

(1.琼台师范高等专科学校信息技术系，海南海口 571100;2.西北师范大学计算机科学与工程学院，甘肃兰州 730070)

0 引言

KNN文本分类算法是一种惰性，非参数的文本分类算法，比较简单，易于实现.但由于该算法是在分类阶段计算待分类文本与所有训练样本之间的相似度，导致分类计算量大.因此在处理容量大、纬度高的样本集时，分类效率低.目前，针对此问题主要有两方面的改进方法:1)算法层方法.主要是通过改进K最近邻的搜索算法，快速获取最有可能的近邻样本，减少计算开销，提高分类效率[1].例如，基于向量投影算法通过比较待分类样本和训练样本的一维投影距离，获得最有可能的临近样本点[2];基于粗糙集算法利用上下近似来刻画各类训练样本的分布，在分类过程中根据待分类文本向量在样本空间中的分布位置，可以直接判定一些文本的归属，以缩小K最近邻搜索范围[3];2)数据层方法.主要是通过裁剪一部分对分类影响比较小的训练样本，找出代表性的样本，以实现样本集的缩减，进而达到减少计算开销的目的.例如对各个训练样本类进行聚类，形成若干个簇，然后再删除与簇中心相似度小于一定阈值的边缘区域样本，以减少训练样本数量[4];采取构建样本聚类中心文档代替原始样本建立分类模型，从而提高分类速度[5].

通过聚类技术将样本聚集成若干个簇[4，5]，都需要构建簇中心实现样本裁剪.但簇中心……