KNN算法的补充

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

文本自动分类技术是文字管理的基础。通过快速、准确的文本自动分类，可以节省大量的人力财力；提高工作效率；让用户快速获得所需资源，改善用户体验。本文着重对KNN文本分类算法进行介绍并提出改进方法。

一、相关理论介绍

文本分类技术的研究由来已久，并且取得了很多可喜的成果，形成了一套完整的文本自动分类流程。

（1）文本分类

文本分类是根据训练样本集中的样本来进行训练，找到一定的分类规则和规律,然后根据这些规则和规律对需要进行分类的文本进行判断，自动将其归类。

（2）文本表示

要实现依据内容的自动分类，需要将文本表示成机器能够“理解”的形式。目前最为成熟的就是向量空间模型(VSM: Vector Space Model)。将文本转化为一个个的文本向量，然后通过计算个个向量间的相似度来进行分类判断。

（3）文本分词

使用一定的规则方法，将中文文本内容分割为一个一个具有基本语义的词，以供提取特征项。

（4）去停用词

在文本提取特征项的过程中，需要将那些词频非常高，对于分类又没有任何表征作用而且会影响分类结果的停用词过滤掉，以提高分类准确度。例如：介词、连词等。

（5）特征选择和权重计算

特征选择是按照一定的选择方法从经过分词、去停用词处理的词组中挑选出一些对分类具有表征意义的词，用作构建文本向量空间的特征项。然后将各个文本表示成这个向量空间中的向量，再选择合适的权重算法，计算各个特征项的权重，将文本向量化。

（6）分类算法

分类算法是通过使用一定的规则对向量化的文本进行判断，自动对其进行归类。其过程可以分为两个阶段：训练阶段和分类阶段。

训练阶段是根据给定的已经归好类的训练样本集进行训练，学习分类的规则和规律，建立分类器。分类阶段是使用训练阶段建立的分类器对待分类文本进行判断，实现自动分类。

二、KNN算法分析

KNN算法的提出最早可以追溯到半个世纪以前，由Cover和Hart于1968年提出。KNN算法是一个比较成熟的算法，应用的范围很广。

KNN分类算法可以简单将其分类过程描述为：

（1）进行文本预处理,即文本分词、去停用词、特征选择、权重计算，将训练集中的文本表示成文本向量并进行存储。

（2）计算待分类文本向量与训练集中的所有文本向量的相似度，从训练集中选出相似度排名前K的文本。

（3）依据这个K个文本对待分类文本进行分类。K篇文本中哪个类别的文本多，则待分类文本就属于这个类别。

KNN算法的优点主要集中在两个方面。首先，KNN算法成熟、稳定、易于实现。其次训练过程很快，只需对新加入的文本进行训练就好。

KNN算法的缺点也是很明显的。其中一点就是需要大量的时间开销。KNN算法之所以在分类阶段需要耗费大量的时间是因为KNN算法并没有实际的分类器。在训练阶段，KNN算法只是将样本集的文本进行了处理，而并没有进行实际的训练学习，而是将这种学习放到了分类阶段，在分类阶段需要计算待分类文本与所有训练样本集文本间的相似度，使得分类阶段的计算量相当的大，从而影响了分类时间。

由于现在网络中的数据量越来越大，对于分类时间的要求也越来越高，因此通过改进KNN算法以降低时间开销是非常有意义的。

三、算法改进

可以从以下几个方向入手对KNN算法进行改进，以降低时间开销：

（1）样本集剪裁。为了降低KNN算法的空间以及时间开销，对初始的样本集进行筛减是最简单，也最有效的方法。但在筛减的同时一定要保证不以牺牲分类的准确性为代价，所以就一定要选取那些特征性强，能很好的代表这个分类的文本，从而将其他特征不明显，代表性不强的文本删去，从而减少分类时需要比对的文本数量，缩短分类时间。

（2）获得K篇近邻文本方法的改进。要获得最终的K篇近邻文本，需要待分类文本与训练集中的所有文本进行相似度计算，通过比较计算结果才能得到。如果能够避开与所有文本进行相似度计算而直接找出这K篇文本，那就能大幅提升分类速度。

本文采取第一种方法，来对KNN进行改进。

KNN算法之所以在分类阶段需要耗费大量的时间是因为KNN算法并没有实际的分类器。要使得KNN算法拥有较好的分类性能，需要在训练阶段建立起分类器，将大量的计算放到学习阶段，从而减少分类阶段的时间开销。考虑到类中心向量法拥有非常好的分类速度，因此将类中心向量和KNN算法相结合，以达到分类精度趋近于KNN算法，分类速度趋近于类中心向量法的效果。结合后的算法可简单描述入下：

（1）对样本集中的所有文本进行处理，将计算后得到的文本向量保存下来。

（2）采用类中心向量法，计算个各类的中心向量。

（3）分类时，首先将待分类文本与各个类中心向量进行相似度计算并排序。然后确定一个阀值m，取排名前m个类中的文本作为使用KNN算法的样本集。

（4）在新的样本集上使用KNN算法进行分类计算，将D归类。

四、改进分析

通过对KNN算法和类中心向量法的结合，使得KNN算法在训练阶段也能够建立起简单的分类器，其好处是显而易见的：

当需要对待分类文本进行分类时，通过训练阶段获得的类中心向量，可以快速的获得待分类文本与个类中心向量间的距离，从而确定需要使用KNN算法进行计算的m个类。最后实际参与KNN算法的样本集即为这m个类中的文本，变相减少了样参与相似度计算的样本集，使得计算量大幅下降。如果m取值为分类数的一半，那么就可以直接减少一半的计算量。阀值m的选择对于最终速度的提升有决定性作用。如果m过小会直接影响到分类的精度，过大对于分类速度的提升效果不明显，需要通过实验确定。一般情况下m可取分类数的一半。

最后通过实验验证改进后的KNN算法较之传统的KNN算法，在保证分类准确度的基础上，分类时间大幅缩短超过一半。说明改进取得了不错的成效。