KNN和SVM算法在中文文本自动分类技术上的比较研究

1、KNN和SVM算法在中文文本自动分类技 术上的比较研究日期：2009-07-22来源：作者:字体：大中小马建斌，李谨，滕桂法，王芳，赵洋，摘要:中文文本分类技术在中文信息智能处理方面具有十分重要的作用比如：中文信息检索和搜索引攀等KNN、贝叶斯、SVM等算法都可以应用到中文文本分类 技术上，本研究分析和比较了 KNN和SVM两种分类算法，并通过实验比较这两 种算法对中文文本分类技术的效果。结果表明:SVM算法较优，是一种较好的中 文文本分类算法。ThecomParisonstudiesonthealgorithmofKNNandSVMforchinesetextClassificationAb

2、traet:Chi nesetextelassifieatio n15importa ntforehi nesei ntellige nti nformatio nmana gement， suehasehineseinformationretrievalandrehengine.AIOtofalgorithmseanbeusedforChinese textelassifieation, suehasKNN Bayesa ndSVMete.ThePaperhasa nalyzeda ndcomparedtheKNNa ndSVMalgorithm.A nd theeffectofthetwo

3、agorithms on Chi nesetextelassifieatio nwasgotbytheexperime nts.Th eresultsindieatedthattheSVMalgorithmwasbetterthantheKNNalgorithm， whiehprovedthattheSVMalgorithmwas on eexcelle nteh in esetextelassifieati on algorithm.Keywords:Chi nesetextelassifieatio n;KNN;SVM随着计算机技术、信息技术的发展，尤其是互联网的日益普及，以半结构化 或完

4、全非结构化为主的电子信息呈几何级数增长，当前，仅google搜索引攀搜索的网页就达40多亿。如此海量的信息，为网络用户的工作和生活带来了极大 的便利，但是如何从海量的信息中快速、准确地找到用户感兴趣的内容成为一个 需要迫切解决的问题。基于内容的信息检索和数据挖掘逐渐成为备受关注的领 域。其中，文本分类技术是信息检索和文本挖掘的重要基础，其主要任务是在预 先给定的类别标记(label)集合下，根据文本内容判定它的类别。文本分类在自然 语言处理与理解、信息组织与管理、内容信息过滤等领域都有粉广泛的应用。20世纪90年代以前，占主导地位的文本分类方法一直是基于知识工程的分类方 法，即由专业人员手工进

5、行分类。人工分类非常费时，效率过低.20世纪90年代 以来，众多的统计方法和机器学习方法应用于自动文本分类，文本分类技术的研究引起了研究人员的极大兴趣。目前英文自动分类已经取得了丰硕的成果， 提出 了多种成熟的分类方法，如最近邻分类(Knearestneighbor, KNN)、贝叶斯分类川、 决策树以及支持向量机(Sup因rtveetormaehine，svM)，、向量空间模型 (vesto:spaeemedel, vSM)、回归模型和神经网络川等方法，但对 于中文文本的自动分类技术研究尚不尽人意。目前国内中文文本分类研究主要集中在朴素贝叶斯、KNN、向量空间模型和支持向量机等技术上。本研究

6、分 析和比较KNN和SVM这两种机器学习算法在中文文本自动分类技术上的应用， 并通过实验比较这两种分类算法的效果。1中文文本分类技术自动文本分类也就是在已有数据的基础上学会一个分类函数或分类模型，即所谓的分类器(Classifier。为文档集合中的每个文档确定一个类别。现在主流的文本 分类方法是基于机器学习的方法，此方法首先使用训练样本进行特征选择和分类 器训练，然后把特征形式化待分类样本输人到分类器进行类别判定，最终得到输人样本的类别。基于机器学习的自动文本分类方法的基本过程包括文本的特征表 示、特征提取、特征选择、文本分类等过程。1.1文本特征衰示和特征提取用简单而准确的方法将文档表示成计

7、算机能够处理的形式是进行文本分类的基 础，它是对从文本中抽取出的特征项进行量化，以一定的特征项表示目标信息。 最经典文本形式化表示方法是 20世纪60年代Salton等人提出的向量空间模型 (VSM)。向量空间模型的基本思想把文档简化为以项的权重为分量的向量表 示:(w，w:，w3w，)，其中w 为第i个特征项的权重，一般选取词作为特征项。向量用词频表示。词频分为绝对词频和相对词频：绝对词频，即词在文本中出现的频率，相对词频为归一化的词频，其计算方法主要运用TF一 IDF公式：W初叫 +0.01)/(/ vrf x log(N/n( + 0 01)2(1)茸中，用仃,2为词r在文本1中的权晝，

8、而tf(Gd)为词在文本/中的词频，N为训练文本的 总数离为训练文本集中出现r的文本效，分母为 归一化因子。1.2特征选择由于一个训练文档集中的候选特征项通常很多， 可高达几十万个，不同特征 项对于文档的重要性和区分度是不同的。 去除区分度较小的噪音特征项可以提高 分类准确率， 去除重要性较低的低频特征项可以加快运行速度。 因此，在分类之 前，对特征项进行特征选择是必要的， 常见的特征选择方法有文档频次、 互信息、 信息增益、 才统计里等。 CarnegleMellonUniversity 的 Yiming 对这些方法进行了比 较。1.3 特征匹配与分类 特征匹配是利用特征项评价未知文档与用户

9、目标的相关度，找到最大匹配文档。 文本转换为向 t 形式并经特征提取后，便可以进行分类挖掘，即模式匹配。基于 机器学习的文本分类问题分为训练和分类两个阶段， 方法是利用机器学习算法进 行自动文本分类。当前用于文本分类的主要机器学习算法有 :贝叶斯方法、决策 树、神经网络、KNN支持向t机等。2KNN 和 SVM 算法原理2 1KNN算法该算法的基本思路是：在给定新文本后考虑在训练文本集中与该新文本距离 最近的K篇文本，根据这K篇文本所属的类别判定新文本所属的类别， 具体的算 法步骤如下：STEP根据特征项集合重新描述训练文本向量；STE刃:在新文本到达后，根据特征词分词新文本，确定新文本的向量

10、表示；STEP3在训练文本集中选出与新文本最相似的 K个文本，计算公式为：J(紳)(轲表示第i篇档的特征向量j表示第j篇文档的特征向量，M为特征向量的维数，sim(d ，峨)表示第i 和j篇文档的相似度，讯为向量的第k维。STEP4在新文本的K个邻居中，依次计算每类的权重，计算公式如下：/(xTCj) = L)y(dt ,C)(3)i KNNA其中，牙为新文本的特征向量，sim(,)为相似度计算公式，而到，c为类别属性 函数，如果属于Cj类，那么函数值为1,否则为0。sTEPS:比较类的权重，将文本分到权重最大的那个类别中。 KNN算法简单，且分类准确率较高，但是，由于KNN算法需要将所有样本

11、首先存储起来，进行分类时就临时进行分词，降维等计 算处理，因此，当训练样本或者测试样本数目迅速增加时，就会导致计算量迅速增加，速度较慢。.2.2SVM 算法支持向量机(SVM)是由vaPnik等人根据统计学习理论导出的结构风险最小 化原则基础上的机器学习算法。其主要思想是针对2类分类问题，在高维空间中 寻找一个超平面作为2类的分割，以保证最小的分类错误率。SVM是从线性可分情况下的最优分类面发展而来的，基本思想可见图1。分割线1和分割线2都能正确地将2类样本分开，这样的分割线有无线多条，但分 割线1使2类样本的间隙最大，称之为最优分类线(更高维即为最优分类面或最 优超平面)。*5= - I;(

12、审时+41oo/oaai矗性二类划分的优n甲arFig. I The two class Hikbt separate optimi hyperplane设线性可分训练集(x , y:)，(x , yt) , xi Ryi -1,1 l为样数。 n维空间中线性判别函数的一般形式为 g(x)二w x+b,分类面的方程为 w x+b 二0。将判别函数归一化，等比例调节w和b,使两类所有样本都满足!g(x)1 ， 这样，分类间隔就等于2/|w类样本的间隔最大变为求日|w|其中满足g(x)=1的样本点离分类线(平面)最近，它们决定了最优分类线 (平面)，称之为支持向量。可见，求最优分类面的问题转化为优

13、化问题：Min(w) = yl wl1=j(W*W)(4)满足约束条件：y (w*xJ + 6) - 10,i = 1 Z(5)本优化问题可以转化为：f I imaxM( a)=听节丫(6)! 心 1满足约束条件：玄吓=0阿沁(7)*1丄 亠 亠 亠 N 4. 亠-亠 4通过求解，可得最优分类函数为：/(x) = sgn( w x + 6) = sgn( 召比匕 + d )其中，N,为支持向量个数对于线性不可分问题，vapnik引入了核空间理论：将低维的输人空间数据通过 非线性映射函数映射到高维属性空间。上面介绍的是二值分类器，基于SVM勺多值分类器的构造可以通过组合多个二值分类器来实现，具体

14、的构造方法有一对一 和一对多两种。3 kmN和SVM算法对中文文本分类实验结果3.1方法在一个具有2846篇中文文本语料库上测试KNN和SVM这两种分类算法，并 对其效率和结果进行比较分析。语料库的文本都是新华社的新闻稿， 所有这些新 闻稿都由领域专家事先进行分类，一共有十类，包括 ：环境、交通、计算机、教 育、经济、军事、体育、医药、艺术、政治，其中，每一类中的 2/3用作训练集， 剩下的1/3用作测试集，抽取1000个词语作为特征项。本文采用文本分类研究普遍接受的评估指标来评价文本分类的性能，即准确率(Precision)、查全率(Reeall)和FI测试值。3.2结果通过上述的实验方法试

15、验 KNN和SVMZ中算法的实验结果，假设特征选择采 用信息增益方法，其分类结果如表1所示。* 1 KNN W SVM *法对中文文本分类第果比较 Table 1 The comparison of KNN and SVM atsoHthm TorChinese teil delineation%算法Algorithm査全率R)准确率(P)FrecisicnF,KNN85 39).47,SSVM94 一79695,3可以看出，SVM算法比KNN算法的文本分类结果好的多，表明 SVM是一种比 较好的文本分类算法。为了比较几种特征选择方法的效果，比较了3种特征选择 方法，用KNN算法进行了试验，结

16、果如表2所示。三种特征选择方養対中文文本分类培果比较 Table 2 The coFiparbon 毎f three feature selettion mdhods fur Chinfitte text dassiFicallon特征选择方法 I he metheds of feature select ion祈全*(R) Recau准瑞率fP)Precision尺信息增播85.390.487.8互信息85.290.287,6筑计量S7,691.389,4从表2可以看出，3种特征选择方法对最终的分类结果相差不大，但是统计 量特征选择方法稍微好些。4 结论本研究分析和比较了 KNN和SVM两种

17、分类算法，并在2846篇中文文本语料库 上比较KNN和SVM这两种分类算法对中文文本分类的效果KNN,算法的F,测试值为87.8%,而SVM的F，测试值为95.3%,结果表明svM算法比KNN算法的 文本分类结果好，证明 SVM 是一种较好的中文文本分类算法。另外，比较了信 息增益、互信息和统计量 3 种特征选择方法对中文文本分类的效果, 结果表明统 计量特征选择方法稍微好些。参考文献 :lMiguelERuiz, padminiSrinivasan.Hierarchiealneural networksfortextcategorlzation C /proceedin of SIGIR 一

18、 99:22ndACMIntemationalCbnfereneeon ResearehandDevel mentinInformationRetrieval , NewYork:ACMPress, 1999:281一 282. 2AlfonsJuan, HermannNey.ReversingandSmoothing theMultinomialNaiveBa TextClassifier Cl/InZnd IntemationalWorkshoPonPatternrecogmtionin informationsystems, Germany:sPringer, 2002:200 一212.3 TJoaehims.Texteategorizationwithsup tvector maehines:LearningwithmanyrelevantfeaturesCl/InProceedin oftheEuropeanCbnfereneeonMaehineLearning, Germany:SPri 4庞剑锋,卜东波,白硕 .基于向量空间模型的文本自 动分类系统的研究与实现【J计算机应用研究， 2001, 18(9):23 一 26.【 5都云琪,肖诗斌 .基于支持向量机的中文文本自动分类 研