一种改进的ＫＮＮ　Ｗｅｂ文本分类方法.doc

一种改进的文本分类方法?丶?词：Web文本分类； K最近邻； 快速分类 Improved KNN Web text classification method WU Chun-ying, WANG Shi-tong (School of Information Engineering, Jiangnan University, Wuxi Jiangsu 214122, China) Abstract:KNN method not only has large computational demands, because it must compute the similarity between unlabeled text and all training texts; but also may decrease the precision of classification because of the commonness of classes. This paper presented an improved KNN method, which solved two problems mentioned above. It firstly got the most k0 classes fast by Rocchio method, and then used KNN arithmetic in some representative training texts of theclasses, at last assigned class by an improved similar arithmetic in KNN. The result of research indicates that the impact of the new method is better. Key words：Web text classification; KNN(K-nearest neighbor); fast classification ? 随着网络信息技术的高速发展和高速通信基础设施的建设，Internet上的Web页面数量呈指数增长。如何有效地组织和处理这些海量信息，如何更好地搜索、过滤和管理这些网络资源，Web文本分类成了关键技术。目前关于这方面的研究已经取了很大的进步，并取得了一系列的分类方法，其中比较著名的文本分类方法有Rocchio、支持向量机（SVM）、K最近邻（KNN）、神经网络和贝叶斯（Bayes）算法等1。在这些方法中，KNN是一种简单、有效、非参数的方法，目前应用比较广泛。 为了使KNN方法更实用，不少学者对KNN方法进行了进一步研究，王煜等人2提出了一种快速KNN算法，通过建立索引表来快速找到k个最近邻，但没有提高分类精度；李杨等人3提出了排类和归类算法在不影响原有精度下提高分类速度；李荣陆等人4针对不均匀训练样本，提出了基于密度的裁剪方法，取得了较好的分类效果。本文提出一种改进KNN文本分类方法，目的是为了减少样本间相似度的计算量，克服KNN分类搜索空间巨大的问题，同时又能一定程度地改善分类效果。 1传统的KNN文本分类方法 11文本表示方法 向量空间模型（vector space model,VSM）5是由Salton于1968 年提出的，是近年来文本表示应用较多且效果较好的方法之一。该模型涉及到以下三个基本概念： a)文档(document)。泛指一般的文本或文本中的片断,一般指一篇文章。 b)项(term)。文本中的内容特征常用切分后的词来表示,称为文本的项,即文本可用项集(term list)，表示为D(t1,t2，,tn)。其中：tk是项。 c)项的权重(term weight)。对于含有N项的文本,不同的项tk,其区分文本的能力不同,故tk常被赋予不同的权重wk(d),表示它们在文本中的重要程度。常用的有布尔函数、平方根函数、对数函数、TF-IDF 函数6等。其中TF-IDF 在文本检索和机器学习中被频繁使用。目前存在多种TF-IDF公式,比较普遍的TF-IDF公式如下： W(t,d)=tf(t,d)×log(N/nt+0.01)/dtf(t,d)×log (N/nt+0.01)2(1) 其中：w(t,d)为词t在文本d中的权重；tf(t,d)为词t在文本d中出现的词频（绝对词频即使用词在文本d中出现的频次；相对词频即为归一化的词频)；N为训练文本的总数；nt为训练文本集中出现词t的文本数,分母为归一化因子。这样，Web文本d可表示为向量空间模型为 V(d)=(t1,w1(d);t2，w2(d)；tn,wn(d)(2) 12KNN分类算法 KNN算法是一种简单、有效、非参数的文本分类方法；其本质是一种预测性的监督分类算法，不需要额外的数据来描述规则，它的规则本身就是数据样本；它并不要求数据的一致性，即可以存在噪声；KNN根据待分类样本的k个最近邻样本来预测未知样本的类别。因此，KNN算法必须明确两个基本因素：最近邻样本的数目k和测量相似性的距离函数。距离函数是一个非负函数，用来刻画不同样本的相似程度。常用的有欧氏距离、曼哈顿距离、余弦夹角等。本文采用余弦夹角公式7，如下： sim(di,dj)=(di?dj)/(di×dj)=(nk=0wik×wjk)/(nk=0wik2×nk=0wjk2)(3) 其中：sim(di,dj)表示文本di和文本dj的相似度；wik表示文本di中第k个特征的权重。 在分类时，首先将待分类文本D转换与训练样本一致的向量空间模型；然后计算D与每个样本的相似度，计算见式（3）；再取相似度最大的K个样本，根据K个样本计算属于每个类别的权重，计算见式（4）2 ；最后文本D属于权重最大的那个类别。 p(D,Cj)=ki=0sim (di,D)Pd(di,Cj) (4) 其中:sim(di,D)表示文本D的K个最近文本di与文本D间的相似度。 Pd(di,Cj)=1di属于类别Cj样本0di不属于类别Cj样本 （5） 2改进的KNN分类算法 在传统的KNN分类中，要求计算待测文本与所有训练样本间的相似度，时间上难以满足实际分类需求。因此本文提出了一种改进的KNN分类算法。它的主要思想是：先通过Rocchio分类快速得到k0个最有可能的候选类别；然后在k0个类中心区域采用KNN算法；最后结合Rocchio分类结果，由一种改进的相似度计算方法决定最终的文本所属类别。 21Rocchio方法的使用 Rocchio算法8是用于文档分类的经典向量空间模型，它的基本思想是使用训练集为每个类构造一个原型向量。构造方法如下：给定一个类，训练集中所有属于这个类的文档对应向量的分量用正数表示，所有不属于这个类的文档对应向量的分量用负数表示，把所有的向量加起来，得到的和向量就是这个类的原型向量；定义两个向量的相似度公式，逐一计算训练集中所有文档和原型向量的相似度，从中挑选某个相似度作为边界。给定一篇未知文档，如果这篇文档与原型向量的相似度比边界大，则这篇文档属于这个类；否则这篇文档就不属于该类。该方法的突出优点是容易实现，计算（训练和分类）特别简单，但在实际分类系统中很少采用这种方法解决具体的分类问题。 本文采用Rocchio方法作为第一阶段处理，先将每个类别的所有训练文档表示成向量空间模型，然后对该类所有向量进行相加求和再取平均，得到该类的中心向量；同时计算并保存两个变量：a)训练文本与该类中心的最小相似度，公式同式（3），该最小相似度作为衡量一个未知文本是否属于该类的阈值，记为c；b)求出该类所有训练文本与该类中心的平均相似度，记为C，作为后面KNN分类选取代表样本的参考依据。 在分类时，先利用Rocchio分类器计算待分类文本X与每个类别中心向量之间的相似度SCj=sim(X，Cj)，公式同式（3）；如果sim(X,Cj)Cj，则把Cj作为下阶段处理的候选类别，否则放弃Cj，即后续不再对该类别进行处理。这样待分类文本X就只能属于k0(k0m，m为所有类别数）个候选类别中一种。这样处理的目的就是快速排除那些明显不是文本X的所属类别的训练样本。Rocchio分类过程如图1所示。其中：X为待测样本；C1、C2、C3为类别1、2、3的中心向量。从图1中可以直观地看出文本X不属于第三类，因为它到C3的距离要大于类3中所有训练样本到C3的距离，所以直接排除第三类别。这样文本X要么属于第一类，要么属于第二类，接下来就在k0个类别中选择，由下个阶段专门处理。 22改进的KNN算法 经过Rocchio的第一阶段处理，已经排除了m-k0个类别；接下来就用一种改进的KNN算法来完成k0个类别中的最后文本所属类别。改进点主要针对两点：a)在k0个类中，其训练文本依然很大，要选取其中部分有代表性的样本；b)在传统的KNN分类中，文本大多数在类别的边界处被误分，因此改进方法要尽量避免这种情况。 定义1类中心区域。当一个样本di与该类中心Cj的距离dis(di,Cj)=sim(di,Cj)，如果dis(di,Cj)(=×C)（其中：C为该类的所有训练样本到该类中心的平均距离，(0,1），则称di为类别中心区域的一个样本，所有的di称为该类的中心区域。其二维平面如图2所示。 在图2中，k0=2，三个圆圈表示三个类中心区域，两个椭圆为类别间的边界区域。从图中可以看出，如果采用传统KNN算法，则待分文本X的k个最近邻样本必然在第一个椭圆区域，而该区域的所属类别是最模糊的，也是文本最容易被误分的；采用改进的KNN方法则避免了该情况，让文本X与最能代表类别的中心区域样本进行比较，从而得出的k个最近邻样本也必然是类中心区域中的样本，这样提高了分类精度。 定义2类间影响因子。在KNN分类中，一个待测文本X，类别Cj，SCj=sim(X,Cj)，则称SCj是类别间影响因子，它表示该文本X属于该类Cj的隶属度。 这样，改进后的KNN方法具体步骤如下： a)根据第1.1节将所有训练文本表示为向量空间模型，并将待分类文本X转换为与训练文档一致的向量空间模型。 b)采用基于Rocchio的多值分类器进行分类，计算文本X与所有类别之间的相似度，并根据第2.1节处理，快速得到文本X的k0个候选类别；其余的类别将不再考虑。 c)选取训练集中的代表样本，即k0个类别的中心区域中的样本；计算未知类别文本X与代表样本间的相似度sim(X,di)；然后对相似度值进行排序，取前k个作为文本X的k最近邻样本； d)确定文本X的最后类别；引入类间影响因子SCj，对式（5）进行了改进： Pd(di,Cj)=SCjdi属于类别Cj样本0di不属于类别Cj样本 (6) 最后根据k个样本di，由式（4）（6）计算文本X与每类的权重，把X归于权重最大的类别。 3实验结果与分析 31实验概况 常用的特征提取方法有文档频率（document frequency，DF）、互信息（mutual information，MI）、信息增益（information gain，IG）和CHI统计9。文献中实验表明IG和CHI较好。本次实验采用CHI统计，该方法度量词条t 和文档类别c之间的相关程度,并假设t 和c 之间符合具有一阶自由度的2 分布；词条对于某类的2 统计值越高，它与该类之间的相关性越大,携带的类别信息也较多。令N 表示训练语料中的文档总数,c为某一特定类别, t表示特定的词条，A表示属于c类且包含t 的文档频数, B表示不属于c类但是包含t的文档频数, C表示属于c类但是不包含t 的文档频数, D是既不属于c也不包含t 的文档频数。则t 对于c的CHI 值计算公式如下： 2(t,c)=N×(AD-BC)2/(A+C)×(B+D)× (A+B)×(C+D)(7) 文本分类领域比较常用的评价标准有9： 召回率： r=categories found and correct/total categories correct 准确率：p=categories found and correct/total categories found F1值：F(r,p)=2rp/(r+p) 其中:r表示召回率；p表示准确率；本文采用F1值评价标准。 32实验结果与分析 本次实验数据分为两组，实验针对两组不同数据集分别采用传统KNN和改进后的KNN算法进行测试。第一组来自李荣陆收集的10个类别10，它们是大类，即各类间共性较少，而且分布比较均匀。具体情况见表1。实验结果见表2。 第二组数据来自谭松波收集并发布的文本分类语料11，12个大类中教育下的7个小类，它们都是教育的分支，类别间具有很多共性，而且文本数量分布不均匀。具体情况见表3。实验结果见表4。 从表2和4可以看出：a)不论是大类还是小类，分布是均匀还是不均匀，改进后的KNN方法分类效果都要比传统的KNN效果好（其F1值平均要高出1.3个百分点）。这是因为在改进方法中通过Rocchio方法排除了m-k0个类别，同时利用类别中心区域减少了边界样本点的干扰，进而提高了分类精度；b)在实验一的大类中，使用KNN方法进行分类效果比较好，不论是传统的还是改进后的F1都达到了90%以上，改进后只提高了1.3个百分点；在实验二的小类中，两种方法的F1都不到80%，这是因为小类间存在很多共性，即它们的训练样本间存在严重的特征交叉现象，而且样本分布不均匀，给KNN分类带来了困难，即使这样改进后的方法F1提高了6.1个百分点，这说明类别间越是复杂，分布越是不均匀，改进后的方法越有效。由于现实世界中类别往往是种类繁多、关系复杂、分布差别大，这也进一步说明了改进的方法具有现实意义。