刘昕，安见才让

藏文WEB文档分类算法

刘昕，安见才让

针对藏文WEB文档分类中KNN算法计算复杂度高的缺点，不同于以往从减少训练样本集大小和采用快速算法角度来降低KNN算法的计算复杂度，从并行的角度出发，提出了一种基于Java Bean模式的并行算法，其关键部分的时间计算复杂度从O(n2)降为O(log(n))，该算法与经典的串行算法相比，能显著地提高分类速度。

文档分类；K近邻；并行策略；藏文WEB文档

0 引言

随着Intemet的迅速发展，文本分类已经成为大规模数据处理的热点之一。它是从一组已知的训练集样本中创建分类模型，并且使用这个文本分类模型识别待分类样本。目前比较常用的分类方法有：朴素贝叶斯（NativeBes，NB）、支持向量机（Support veetor Maehine，SVM）、K近邻（K Nearest Neighbour，KNN）等等，其中KNN算法以其实现的简单性及较高的分类准确性在中文文本自动分类等领域得到了广泛的应用。KNN算法的基本思想是在训练样本中找到测试样本的K个最近邻，然后根据这K个最近邻的类别来决定测试样本的类别。但是，该方法对属性较多的训练样本进行分类时，由于计算量大而使其效率大大降低，效果不很理想。为了在更广泛的应用领域使用KNN算法，如何提高该算法在处理属性较多的训练样本时的效率，受到了数据挖掘工作者极大的关注。为了从训练样本中找到K个近邻，不得不计算与所有样本间的距离，而藏文WEB文档又具有高维的特点，庞大的计算量影响了KNN法的实时性应用。为了提高KNN法的运行效率，有很多文献资料提出减少计算负担的算法[1-4]。……