文本分类方法研究.doc

毕业论文 题目： 文本分类方法研究 姓名： 贾云璠 院系： 理学院物理系 专业： 物理学 年级： 2013级 学号： 201341021 指导教师： 郑伟 二一七年六月 摘要近些年来，随着信息技术的发展与应用，互联网上的数据错综复杂，面对如此纷繁复杂的数据，需要借助数据挖掘对数据进行处理来实现对数据的分类，以便查询和搜索，实现数据的最大利用价值。文本分类在信息处理方面占有重要的作用，到目前为止，有很多种方法：KNN SVM决策树，以及贝叶斯等算法可以帮助我们快速的对文本进行自动分类，本文主要研究KNN SVM两种方法，在比较这两种分类对中文文本分类的基础之上，分析了K临近算法和支持向量机的优缺点，因SVM和KNN具有互补的可能性，提出了SVM和KNN组合1的算法。实验表明：SVM和KNN有很好的分类效果。 关键词：文本分类，SVM、KNN，线性组合 AbstractIn recent years, with the development of information technology and application, the complexity of the data on the Internet in the face of so complicated data, need with the help of data mining, data processing to implement the data classification, in order to query and search, and realize the maximum utilization of the data value.Chinese text classification plays an important role in Chinese information processing, for example, Chinese information retrieval and search engine, KNN SVM decision tree, and the bayesian algorithm can be applied to Chinese text classification, based on the research analysis compares the two kinds of KNN and SVM classification method, and the experimental comparison of the two algorithms of Chinese text classification effect, on the basis of analyzing the K near the advantages and disadvantages of the algorithm and support vector machine (SVM), found that the SVM and KNN has the possibility of complementary, SVM and KNN algorithm of linear combination is presented.Key words: Text classification, SVM, KNN, linear combination III第二章 文本分类的主要过程 目录 摘要IIAbstractII1 引言11.1文本分类背景和意义11.2文本分类的应用领域和发展趋势12 文本分类主要过程22.1文本分类的定义过程及评价22.2关于文本分词22.3特征项权重（向量空间）32.4特征项选择（常用的降维方法）53 常用的文本分类方法113.1k临近分类器113.2支持向量机分类器124 实验及结果分析164.1实验质量评估指标164.2试验目的174.2实验条件174.3实验结果分析17总结19致谢201 引言1.1文本分类背景和意义随着互联网的飞速发展，网络上的信息的数量也快速地增长。据统计，截止到2014年12月，我国网页数量达到1899亿个，静态网页和动态网页数量都处于不断增长的趋势，依照这样的速度发展下去，我国网络信息的容量会呈现出爆增的状态。信息量的确在不断增长，而人们的信息分析和信息利用能力是有限的，如何在这样的海量数据信息中找到对于自己有价值的信息，就成为人们关注的焦点。从单一客体网页的角度来看，保证做好合理的规划和安排，基于人工判断的模式显然难以完成如此大量的工作，此时就需要依靠更加先进，更加高效的分类方式。信息资源的无限增长给信息处理提出了亟待解决的难题。一方面，数字化信息资源数量高速增长；另一方面，人们获取有价值信息的需求也在不断提高。如何在浩瀚而又复杂的信息中检索出有效的信息，一直是信息处理领域追求的目标。在信息处理领域，关于信息资源的加工和组织方法较多，其中文本的自动分类是比较关键的技术，并且有广泛的应用。文本自动分类是根据文本的语义，将大量的文本自动分门别类。有序的分类能够为人们浏览和查找信息提供许多便捷。因此，不断推进文本自动分类技术的发展迫在眉睫。1.2文本分类的应用领域和发展趋势文本分类能够有效的组织管理杂乱的信息，这一特性在现代很多科技领域很受欢迎,例如Internet、网络图书馆、网络安全、电子邮件等。在Internet中引入文本分类系统，基于关键词，在搜索页输入要查找的内容，电脑系统可以自动判定与之相关的类别并可以快速、准确、全面的搜索出想要的答案，查询速度和精度以及稳定性也是非常的高效，这为我们的生活提供了方便。图书馆的信息资源可谓成千上万，能够快速高效的查询到我们想要的信息，如果单纯的一个个搜索，会花很长的时间。将文本自动分类技术应用到图书馆领域，这样不仅阅读者在寻找自己想要的图书也会很高效，而且减少图书管理员的时间进行整理和查询使查询更加简单方便。大数据规模巨大，随处可见，分布广泛，动态衍变,带来数据复杂性的挑战，因此文本分类技术的发展就显得尤为必要。在网络安全方面，文本分类技术可以对信息进行访问，将不良信息剔除,为用户带来很多方便。在电子邮件方面，文本分类系统可以将邮件进行分门别类。2 文本分类主要过程2.1文本分类的定义过程及评价文本分类的过程，可以将其看做为映射的过程。从无序到有序的历程中，不仅仅可以实现一对一的映射，还可以实现一对多的映射。此时，完全可以以数学映射的概念来诠释文本分类。下图为文本分类的流程图：图2.1文本分类流程示意图2.2关于文本分词文章是由字，词，句，段，篇构成的。词是构成文章的基础，首先需要对文章进行分词，然后将词表示成空间向量，最后进行计算。最后分类结果的好坏由分词的好坏直接决定，分词的标准是越细越好，词语提取越准确越好，nlpir的分词效果较其他分词工具更准确些，更权威。2.3特征项权重（向量空间）2.3.1布尔框架（Booolean weighting） 单一特征词i，为了对于其权重实现界定，就会采取特定的界定手段，在此环节，其界定机制为： 权值定义为：1 特征词i出现在文档k中 公式2-1 Wik =0 特征词i未出现在文档k中 分析：此种方法只是显示了特征词是否存在，出现的次数不能很好的反应分类的效果，因此我们选用下面的方法。 2.3.2TF-IDF计算权值算法TF-IDF（term frequencyinverse document frequency），IF词频：假设实际的词汇为“中国”，这个“中国”词汇在整个文章中会出现多少次，这个次数代表的就是词频。IDF频率代表的是：为收集对应信息，给定了80篇文章，而实际数据库中有120篇文档，此时可以计算出其比重为：0.67。上述两个概念可以诠释如下的问题：单一词汇，在某篇文章中出现的次数越大，此时其IF取值也不会小；但是从宏观数据库角度来看，如果其在数据库中的次数多，此时自身权重反而不会太大，甚至出现下跌的情况。 TF（词频）计算公式 公式2-2 分子代表的是：词汇在文章中的出现次数多少；分母代表的是：全部词汇在文章中出现的次数是多少。依照实际设定原则，如果同样的词出现两次，分母是不会进行叠加处理的。 举例1：在一篇科普类文章中，“鸟儿”在文中出现次数是7,文章中的总词数是1000，则“鸟儿”这个词的词频为：TF=7/1000=0.7% IDF(反文档频率)计算公式 公式2-3 D；数据库中篇章数量多少；Si代表的是，在数据库中出现词汇I的文章数量多少。 TF-IDF最后得到i的权值公式为 公式2-4 举例3：综合例1，例2，那么地球这个词，在语料库中的权值为：TF*IDF=0.007*3=0.021 TF-IDF计算权值的好处分析: 实例：“地球” 、“的”、 “公转”在所指定的一篇文章中出现的次数分别是7,100,5，如果只采用IF计算方法，如果文章有1000词，三个词的频率为：0.007,0.1,0.005，三个词加起来对这篇文章的贡献值为0.112，我们知道在并不能表征这篇文章的特征，而所占比例很小的飞行和鸟儿则可以表征。因此只用IF值存在漏洞，于是我们引入IDF，语料库中含有的总文章数为105其中鸟儿文章数为102，在的文章数为105，含有飞行的文章数为103，那么有如下公式： W（鸟儿）=0.007*lg(105/102)=0.021 W（在）=0.100*lg(105/105)=0 W(飞行)=0.005*lg(105/103)=0.0102.4特征项选择（常用的降维方法）当空间向量形成之后，由于一篇文章的文本分词很多，对应的空间向量长度很长，如果直接运用分类算法，计算时间较长，效果也不是很好。为了保证实际效果，会以减少向量长度的方式来应对。一般情况下，此时采取的手段主要有：基于信息的降维方式，要么以增益的方式，要么以互信息的方式来进行；期望交叉熵的方法；量化理论下的X2统计；定性视角下的文本证据等。 对于个别算法，不适用降维直接对向量进行计算，效果也不错。但对于大多数算法来说，运用降维之后处理比较好。2.4.1信息增益方法 我们现在先来介绍一下信息熵的概念。 公式2-5 称为事件X的的信息熵。 现在选班长进行投票，小明和小红的实力相当，X表示从两人之间随便选取一个的概率为1/2。计算得到信息熵为：H（X）=-0.5*(-1)-0.5*(-1)=0.5*2=1如X表示从四个人中选班长，每个人被选中的机会相等，则此时的概率为1/4。计算得到信息熵为： H（X）=-4*0.25*log2(0.25)=2如果有八个候选班长，计算得到的信息熵为： H（X）=-8*0.125*log2(0.125)=3由此可知，可选的结果越多，H（X）的值越大。信息熵值越低，事件结果发生越稳定。 综合上述多种降维方法，实际运用最为频繁的就是信息增益，其取得的效果也是比较客观的。 信息t的信息增益的公式为： 同样此处我们选择以“中国”词汇来解释上述的公式字母含义，首先我们确定t代表的就是词汇“中国”。那么：P(t)代表的是：选定词汇“中国”在文本中出现的可能性；代表的是：不包含选定词汇“中国”的本本出现可能性；P(Ci)代表的是：在选择的篇章中，可以将其界定为Ci的可能性；P(Ci|t)代表的是：本来牵涉特征词“中国”，并且可以将其归结到Ci的可能性；P（Ci/t-）代表的是：不牵涉特征词“中国”，但是可以将其归纳到Ci的可能性。之所以选择信息增益的手段来处理，是因为其自身具备其他方式难以企及的优势：对于类别没有太多的要求，对于篇章也没有要求，基于总文库和类别进行类别规划，这种设定可以使得计算效果处于良好的状态。所选定的信息增益值越大，该词对文章就更重要，反之信息增益值越小，所选的词就不那么重要，除去那些不重要的词，剩下的词相对来说就减少了，达到了降维的目的，有利于提升分类的速度。2.4.2互信息方法 互信息8可以这样去理解：单一信息群体中，不同的信号因素之间存在关联，以依赖属性最为明显。存在交互的两个信息元素，我们将其称作为互信息。在文本分类的过程中，可以运用互信息去诠释文本的关联属性。 互信息的计算公式如下： 公式2-6 注：P（tCi）为特征词t与类别Ci同时出现，P(t)表示包括选定词t的文本出现的概率，其中P(Ci)表示所选篇章属于Ci的概率。互信息在此机制中效能的发挥，并非是一帆风顺的。如果在实际的条件下，临界特征出现，就会对于其有效性产生负面影响。从量化的角度来看，在特征取值相同的时候，稀有特征往往会凌驾到普通特征之上。此时，如果采用互信息评估，其就具备明显的倾向性，由此得出的信息检索结论参考性也不大，甚至户对于实际决策产生不良影响。因此,互信息在文本分类中应用不是很广泛。2.4.3期望交叉熵方法期望交叉熵的优势在于：没必要去关注特征词是否会出现，自身并没有在此环节的局限性。一般情况下，计算出来的取值越大，其实际的文本类别会呈现出不断增长的趋势。期望交叉熵的算法公式为： 公式2-7 用这种方法，所选定的特征词与类别关系越大，期望交叉熵值越大；所选定的特征词与类别关系越小，期望交叉熵值越小。2.4.4X2统计方法X2统计方法使用十分普遍，在各个领域都可以看到其运用案例。在文本类别划分的过程中，其倡导在探究文本类别与特征词之间关联性的基础上来判定。如果实际的相关度不断提升，此时的表征作用也会不断凸显出来。X2统计方法的计算公式： 公式2-8 上述公式中，不同字母代表的含义是不一样的。详细来讲：A：特征词和Ci同时出现的可能性；B：会出现t，但是并没有出现Ci，将这样的情况进行统计，得出的数据；C：t没有出现，但是Ci出现了的，将这样的情况进行统计得出的结论；D：t不出现，Ci也不出现，将这样的情况进行统计得出的数据。 在下列表格信息中，实际的临界点显示了如下的信息：三高疾病与性别之间的关联不大。患肺癌疾病不患肺癌疾病合计吸烟37 (A)183(B)220不吸烟21 (C)274(D)295合计58457515已知在H成立的条件下P（X2=6.635）=0.01现在X2=11.863远大于6.635，概率不超过0.01。运用上述公式可得X2=11.863,我们有99%的把握认为是否患肺癌疾病与吸烟有关。|ad-bc|越小，代表肺癌患病与吸烟之间的关联不是很大，或者说其关联的程度处于较小的状态；相反如果实际的取值比较大，其代表的是这两者之间的关联是比较大的。2.4.5文本证据权方法 文本证据权方法，是基于比较文本概率和特征词的属性来探究，在某个类别条件概念出现差异的时候，可以依照这样的方案来进行量化，继而获得权重数据。 文本证据权的计算公式如下： 公式2-920 3 常用的文本分类方法前面部分为文本分类做了知识铺垫,也讲述了将文本处理成向量形式的方法。选择分类器作为研究切入点，对于其运行机制进行探究，继而延伸到文本分类手段上，对于常用到的四种算法进行概述。其中本章主要研究K临近算法(KNN)和支持向量机算法(SVM)。3.1k临近分类器3.1.1KNN算法概述KNN(K-临近算法)首先锁定目标点,然后寻找其周围临近点,计算各临近点与目标点之间的距离,比较得出距离最近的临界点,则目标点就从属于临界点所在的类别。通俗的说:目标点归属于距其最近的临界点的类别,即跟着那个最近的点走。3.1.2KNN算法概述KNN算法的运作机制为：目标文本确定收，需要在实际文本集合中去寻找文本相关的，继而将其界定为文本类别。实际上，其需要历经如下几个步骤：Step1：基于特征属性，实现训练文本向量的确定，给予详细的描述，为后期的算法奠定基础；Step2：依照特征词汇属性对于实际文本的向量进行探究，继而形成有效认Step3：在训练文本集合中寻找上述相关的文本，此时需要依靠公式来进行计量： Pi表示第i篇档的特征向量 Pj代表的是：在对于第j篇章中特征向量进行探究之后，实现对应维数M的确定；sim(Pi,Pj)代表的是：在对于第j和第i文档属性进行判定，找到两者之间的相似度，继而实现维度的推动。 Step4：权值的计算公式为： 公式3-1 上述公式中，y(di,cj)是判断di这个文本是否属于类别，属于类别，则其值为1，反之其值为0。Sim关注的是两者之间的相似性，如果这个取值处于比较高的状态，就会对于实际的权值产生极大程度的影响。Step5：依照实际获取到的结果，对于文本属性进行探究，由此完成实际的类别划分工作。 KNN方法的优势在于：存储文本集合的相关信息，完全可以在忽略分类器的背景下，实现分类文本的再次操作。处于特定分类情境中，无论是待分类文本，还是分类文本，都需要进入到相似度考量中去。由此导致实际的计算量处于比较大的状态。但是这样的工作量带来的好处在于：使得文本集合中文本类别分布不均衡的问题得到的调整，此时整个类别呈现出很强的稳定性特点。3.2支持向量机分类器3.2.1SVM算法概述支持向量机的数学描述：wx-b=0 表示一个超平面的公式,其中w表示垂直平面的一个向量,x是超平面上的点,位移不断的改变b的取值会构成很多个平行于本平面的平面,之后我们从这些平面中选取2个平面: 公式3-2 由于这两个平面与原本平面之间的差距是对等的，此时可以运用抽象思维，将其界定为三维空间内对等平面。 上式运用在线性空间的原理类似,当在高维时涉及到的n-1维超平面,问题变得很复杂,此公式发挥了巨大作用。3.2.2SVM构造分类器 （1）线性可分在介绍复杂问题之前,先进行简单问题的铺垫。用一条直线将图中黑白两类点进行分开：图3.1 多条线性划分图示我们知道:一个平面内有无数条直线,显而易见,使两个类别划分的越开,这条直线越好。可以使用下面的方法：图3.2向两边延伸 图3.3只想向量机M距离图示直线画出之后，在两边进行延伸，平行线与实际之间之间的距离在不断变大，直到和空间类别中的某一个点相交，要求是两边都相交，然后求M的取值，当然满足条件使得M的取值越大，证明划分的越开，划分效果越好，M的取值 定义为：M=2/|W|。|W|表示二范数，就是在没有特殊条件下，实际向量的长度范围，计算出来的M的最大值，就是W的最小值，这两者之间就形成了这样的对应关系。 用公式形象的表示为： 公式3-3 此式还有一个约束条件，如下： 公式3-4 公式3-5 （2）线性不可分在文本分类中,上述用一条直线或空间平面直接对其划分的线性可分情况,存在很多弊端,只适用于理想情况。对于真实的情况,不可能向上述那样简单,而是在空间的多个区域有零散的分布，针对这种情况，要引入惩罚函数，如下图所示：图3.4 曲线划分图示 图3.5 惩罚函数引入图第一种方法：可以用一条曲线进行划分；第二种方法：基于惩罚因子理论，实现对于直线的处理，其实际的处理依据为下述公式： 公式3-6上述公式可以对于不归属原本类别的点以及其可能导致后果进行分析，简而言之不可能因此出现太多的差错。 （3）映射函数（核函数）上述两种情况是在很鲜明的划分很多点的情况下进行的划分,还是比较理想。处于实际运作环境中，样本与样本之间的关联需要格外关注，站在数学映射的角度来探究，超平面划分就成为最佳的选择，可以使得其映射到更加高维度格局中。具体可以参见下图：本身的样本是二维的x,y坐标平面，现在引入第三位坐标z,根据映射关系，就可以很容易的用一个平面进行划分了，如下图所示： 图3.6 三维空间映射图示 （4）SVM进行分类 如上面三种方法，均是svm分类器的构造，当确定某一种划分之后，一个新的样本到达时，就可以对这个样本所处的区间，继而选择将样本纳入到对应类别体系中去。运算流程中有诸多的点，此时可以在不用降维的前提下开展运算，这样可以保证两两类别划分变得更加精确。但是遇到多种类别的情况，要么可以以直线的方式来处理，要么可以以立体维度的空间来处理。 （5）SVM分类评价这种评价机制的特点在于：向量机算法优势明显，可以以更加好的方式呈现出来，整个计算过程也比较简单，实际的应用实践案例比较多。基于映射的方式，实现高维空间的过度，可以诱导出最理想的平面，继而将其渗透到分类决策中去，可以发挥出最大的效能，不用涉及各个向量的测度，不用计算遍历每个向量，在一定程度上，可以避免因维数而带来的各种困难。4 实验及结果分析4.1实验质量评估指标评价：召回率（查全率）、准确率（查准率）、F1值（综合准确率） 查全率(Recall ratio)=检查出的相关信息量/检索到以及未检索到的相关信息总量。查准率(Presion ratio)：实际需求信息的规模与查出来的信息规模之比。为了更好的理解查全率和查准率的概念，需要引入多个变量来进行a-程序归类正确的文章篇数b-程序把文章分配到某个类别，而实际文章并不在这个类别c-文本本身在某个类别，但是程序并没有将文章归入d-程序和语料库归类都不在某个类的文章数。 此时再去理解查全率和查准率，就可以获得相对精确的解答。由此得出公式中的分母，就是数据库中拥有的所有信息量。F1值：制定有效的评价机制，在获得系统数据结构之后，进行定向判定。此时，会使用到多个评价参数：综合分类率，综合准确率，召回率。详细来讲，可以运用如下的公式来诠释三者之间的： 公式4-1 接着，依照如下公式来计算F1： 表4.1 F1值计算公式示意图4.2试验目的不同的特征选择方法有一定的差异，这就导致了文本分类过程中应用的效率差异。再者，基于不同的选择方法，实现分类机制的构建，由此得到的结果也是多样化的。因此，从大量的方法组合中找出效率高的搭配就显得尤为重要了，文本分类的关键技术之间的相互影响能够很好地反应到分类的效果上，所以通过分类效果的研究就能够找出优秀的方法组合方式我们取KNN和SVM在各自最优组合的前提之下，挑选出SVM和KNN两者结合的最优方法，对SVM和KNN进行线性组合，看其对文本分类是否有良好的效果。4.3实验条件 window xp 系统下，VC+ 6.0程序实现。采用中科院自主研发的Txtcat系统。它基于KNN和SVM两种算法进行训练和对文本分类。另外与语料库选择方面，是实现与复旦大学之间的合作，保证了该语料库的丰富性。搜狗语料包括健康、教育、经济、军事、劳动与就业、旅游、体育、文学、新资讯等十类。4.4实验结果分析根据以往实验鉴定，基于SVM和KNN算法各自较优组合条件下，不论是在复旦大学语料下，还是在搜狗语料下，在空间维度为1000维，K=35时，F1值达到最大值。根据经验值：在空间维度为1000，K=35这一条件下，对SVM和KNN进行线性组合，即aKNN+（1-a）SVM,其中a取值从0，0.1, 0.2，0.3一直取到1.结果见如下表:SVM和KNN线性组合a00.10.20.30.40.50.60.70.80.91aKNN+(1-a)SVM的F1值86.57%86.57%86.36%84.43%84.53%81.28%78.33%78.22%78.12%78.53%78.53 表4.2 SVM与KNN线性组合随a值的变化 由于表中显示的数据不直观，我们将其转化成折线图，如下图所示： 图4.3 F1值随a值的变化 由图表可知，当全部应用SVM算法时，F1值较高，对于文本分类有良好的效果。当0.8KNN+0.2SVM线性组合时，F1值最低；之后又呈现轻微的升高。因此得出：在KNN和SVM的线性组合中，KNN成分的增加拉低了SVM文本分类的F1值，并不能起到一个很好的效果。 总结论文所做工作如下： 1、通过大量的文献阅读，对文本分类算法有了一定的理解。2、总结了文本分类的基本原理、研究了KNN的SVM两种算法的特点。根据所掌握的理论知