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

KNN和SVM算法在中文文本自动分类技术上的比较研究[日期：2009-07-22]来源：作者：[字体：大中小]马建斌‘，李谨，滕桂法’，王芳’，赵洋’摘要:中文文本分类技术在中文信息智能处理方面具有十分重要的作用比如:中文信息检索和搜索引攀等KNN、贝叶斯、SVM等算法都可以应用到中文文本分类技术上，本研究分析和比较了KNN和SVM两种分类算法，并通过实验比较这两种算法对中文文本分类技术的效果。结果表明:SVM算法较优，是一种较好的中文文本分类算法。ThecomParisonstudiesonthealgorithmofKNNandSVMforchinesetextClassificationAbtraet::Chinesetextelassifieation15importantforehineseintelligentinformationmanagement，suehasehineseinformationretrievalandrehengine.AIOtofalgorithmseanbeusedforChinesetextelassifieation，suehasKNN，BayesandSVMete.ThePaperhasanalyzedandcomparedtheKNNandSVMalgorithm.AndtheeffectofthetwoagorithmsonChinesetextelassifieationwasgotbytheexperiments.TheresultsindieatedthattheSVMalgorithmwasbetterthantheKNNalgorithm，whiehprovedthattheSVMalgorithmwasoneexcellentehinesetextelassifieationalgorithm.Keywords:Chinesetextelassifieation;KNN;SVM随着计算机技术、信息技术的发展，尤其是互联网的日益普及，以半结构化或完全非结构化为主的电子信息呈几何级数增长，当前，仅google搜索引攀搜索的网页就达40多亿。如此海量的信息，为网络用户的工作和生活带来了极大的便利，但是如何从海量的信息中快速、准确地找到用户感兴趣的内容成为一个需要迫切解决的问题。基于内容的信息检索和数据挖掘逐渐成为备受关注的领域。其中，文本分类技术是信息检索和文本挖掘的重要基础，其主要任务是在预先给定的类别标记(label)集合下，根据文本内容判定它的类别。文本分类在自然语言处理与理解、信息组织与管理、内容信息过滤等领域都有粉广泛的应用。20世纪90年代以前，占主导地位的文本分类方法一直是基于知识工程的分类方法，即由专业人员手工进行分类。人工分类非常费时，效率过低.20世纪90年代以来，众多的统计方法和机器学习方法应用于自动文本分类，文本分类技术的研究引起了研究人员的极大兴趣。目前英文自动分类已经取得了丰硕的成果，提出了多种成熟的分类方法，如最近邻分类(Knearestneighbor，KNN)、贝叶斯分类川、决策树以及支持向量机(Sup因rtveetormaehine，svM)[，]、向量空间模型(vesto:spaeemedel，vSM)、回归模型和神经网络川等方法，但对于中文文本的自动分类技术研究尚不尽人意。目前国内中文文本分类研究主要集中在朴素贝叶斯、KNN、向量空间模型[’]和支持向量机[’]等技术上。本研究分析和比较KNN和SVM这两种机器学习算法在中文文本自动分类技术上的应用，并通过实验比较这两种分类算法的效果。1中文文本分类技术自动文本分类也就是在已有数据的基础上学会一个分类函数或分类模型，即所谓的分类器(Classifier)。为文档集合中的每个文档确定一个类别。现在主流的文本分类方法是基于机器学习的方法，此方法首先使用训练样本进行特征选择和分类器训练，然后把特征形式化待分类样本输人到分类器进行类别判定，最终得到输人样本的类别。基于机器学习的自动文本分类方法的基本过程包括文本的特征表示、特征提取、特征选择、文本分类等过程。1.1文本特征衰示和特征提取用简单而准确的方法将文档表示成计算机能够处理的形式是进行文本分类的基础，它是对从文本中抽取出的特征项进行量化，以一定的特征项表示目标信息。最经典文本形式化表示方法是20世纪60年代Salton等人提出的向量空间模型(VSM)。向量空间模型的基本思想把文档简化为以项的权重为分量的向量表示:(w，，w:，w3……w，)，其中w‘为第i个特征项的权重，一般选取词作为特征项。向量用词频表示。词频分为绝对词频和相对词频:绝对词频，即词在文本中出现的频率，相对词频为归一化的词频，其计算方法主要运用TF一IDF公式:1.2特征选择由于一个训练文档集中的候选特征项通常很多，可高达几十万个，不同特征项对于文档的重要性和区分度是不同的。去除区分度较小的噪音特征项可以提高分类准确率，去除重要性较低的低频特征项可以加快运行速度。因此，在分类之前，对特征项进行特征选择是必要的，常见的特征选择方法有文档频次、互信息、信息增益、才统计里等。CarnegleMellonUniversity的Yiming对这些方法进行了比较。1.3特征匹配与分类特征匹配是利用特征项评价未知文档与用户目标的相关度，找到最大匹配文档。文本转换为向t形式并经特征提取后，便可以进行分类挖掘，即模式匹配。基于机器学习的文本分类问题分为训练和分类两个阶段，方法是利用机器学习算法进行自动文本分类。当前用于文本分类的主要机器学习算法有:贝叶斯方法、决策树、神经网络、KNN、支持向t机等。2KNN和SVM算法原理2·1KNN算法该算法的基本思路是:在给定新文本后考虑在训练文本集中与该新文本距离最近的K篇文本，根据这K篇文本所属的类别判定新文本所属的类别，具体的算法步骤如下:STEPI:根据特征项集合重新描述训练文本向量;STE刃:在新文本到达后，根据特征词分词新文本，确定新文本的向量表示;STEP3:在训练文本集中选出与新文本最相似的K个文本，计算公式为:i‘表示第i篇档的特征向量j表示第j篇文档的特征向量，M为特征向量的维数，sim(d‘，峨)表示第i和j篇文档的相似度，讯为向量的第k维。STEP4:在新文本的K个邻居中，依次计算每类的权重，计算公式如下:其中，牙为新文本的特征向量，sim(,)为相似度计算公式，而到，c为类别属性函数，如果属于cj类，那么函数值为1，否则为0。sTEPS:比较类的权重，将文本分到权重最大的那个类别中。KNN算法简单，且分类准确率较高，但是，由于KNN算法需要将所有样本首先存储起来，进行分类时就临时进行分词，降维等计算处理，因此，当训练样本或者测试样本数目迅速增加时，就会导致计算量迅速增加，速度较慢。.2.2SVM算法支持向量机(SVM)是由vaPnik等人根据统计学习理论导出的结构风险最小化原则基础上的机器学习算法。其主要思想是针对2类分类问题，在高维空间中寻找一个超平面作为2类的分割，以保证最小的分类错误率。SVM是从线性可分情况下的最优分类面发展而来的，基本思想可见图1。分割线1和分割线2都能正确地将2类样本分开，这样的分割线有无线多条，但分割线1使2类样本的间隙最大，称之为最优分类线(更高维即为最优分类面或最优超平面)。设线性可分训练集(x，，y:)，…，(x，，yt)，x1∈Rn,y1∈{-1,1}l为样数。n维空间中线性判别函数的一般形式为g(x)二w·x+b，分类面的方程为w·x+b二0。将判别函数归一化，等比例调节w和b，使两类所有样本都满足!g(x)})1，这样，分类间隔就等于2/||w类样本的间隔最大变为求日||w||其中满足}g(x)}=1的样本点离分类线(平面)最近，它们决定了最优分类线(平面)，称之为支持向量。可见，求最优分类面的问题转化为优化问题:满足约束条件:本优化问题可以转化为:满足约束条件:通过求解，可得最优分类函数为:其中，N，为支持向量个数对于线性不可分问题，vapnik引入了核空间理论:将低维的输人空间数据通过非线性映射函数映射到高维属性空间。上面介绍的是二值分类器，基于SVM的多值分类器的构造可以通过组合多个二值分类器来实现，具体的构造方法有一对一和一对多两种。3kmN和SVM算法对中文文本分类实验结果3.1方法在一个具有2846篇中文文本语料库上测试KNN和SVM这两种分类算法，并对其效率和结果进行比较分析。语料库的文本都是新华社的新闻稿，所有这些新闻稿都由领域专家事先进行分类，一共有十类，包括:环境、交通、计算机、教育、经济、军事、体育、医药、艺术、政治，其中，每一类中的2/3用作训练集，剩下的1/3用作测试集，抽取1000个词语作为特征项。本文采用文本分类研究普遍接受的评估指标来评价文本分类的性能，即准确率(Precision)、查全率(Reeall)和FI测试值。3.2结果通过上述的实验方法试验KNN和SVMZ种算法的实验结果，假设特征选择采用信息增益方法，其分类结果如表1所示。可以看出，SVM算法比KNN算法的文本分类结果好的多，表明SVM是一种比较好的文本分类算法。为了比较几种特征选择方法的效果，比较了3种特征选择方法，用KNN算法进行了试验，结果如表2所示。从表2可以看出，3种特征选择方法对最终的分类结果相差不大，但是统计量特征选择方法稍微好些。4结论本研究分析和比较了KNN和SVM两种分类算法，并在2846篇中文文本语料库上比较KNN和SVM这两种分类算法对中文文本分类的效果KNN，算法的F，测试值为87.8%，而SVM的F，测试值为95.3%，结果表明svM算法比KNN算法的文本分类结果好，证明SVM是一种较好的中文文本分类算法。另外，比较了信息增益、互信息和统计量3种特征选择方法对中文文本分类的效果，结果表明统计量特征选择方法稍微好些。参考文献:〔l〕MiguelERuiz，padminiSrinivasan.HierarchiealneuralnetworksfortextcategorlzationC〕//proceedinofSIGIR一99:22ndACMIntemationalCbnfereneeonResearehandDevelmentinInformationRetrieval，NewYork:ACMPress，1999:281一282.[2]AlfonsJuan，HermannNey.ReversingandSmoothingtheMultinomialNaiveBaTextClassifier〔C]l/InZndIntemationalWorkshoPonPatternrecogmtionininformationsystems，Germany:sPringer，2002:200一212.[3TJoaehims.Texteategorizationwithsuptvectormaehines:Learningwithmanyrelevantfeatures[C〕l/InProceedinoftheEuropeanCbnfereneeonMaehineLearning，Germany:SPri〔4]庞剑锋，卜东波，白硕.基于向量空间模型的文本自动分类系统的研究与实现【J].计算机应用研究，2001，18(9):23一26.【5〕都云琪，肖诗斌.基于支持向量机的中文文本自动分类研究[J].计算机工程，2002，28(11):137一138.[6]YimingYang，Jan0Pedersen.ACbmparativeStudyonFeatureSelectioninTextCategodzation〔G]//In14thInternationalConfereneeonMaehineLearning(ICML)，SanFraneisco:MorganKaufmannPubishers，1997:21一29.[7〕eCbrtes，vvapnik.sup