KNN算法的补充

时间:2021-07-07 08:25:21

文本自动分类技术是文字管理的基础。通过快速、准确的文本自动分类,可以节省大量的人力财力;提高工作效率;让用户快速获得所需资源,改善用户体验。本文着重对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算法,在保证分类准确度的基础上,分类时间大幅缩短超过一半。说明改进取得了不错的成效。