（计算机软件与理论专业论文）半监督自训练分类模型的研究与实现.pdf

大连理工大学硕士学位论文 摘要 半监督学习是近年来提出的一种新的学习方法，根据学习目的的不同大致可以分为 半监督分类和半监督聚类。其主要思想是在已标记训练数据集较少的情况下，如何结合 大量的未标记数据来改善学习性能。 本文探讨的是半监督分类。主要针对半监督分类算法中典型的自训练分类算法进行 了大量的研究与分析。针对自训练分类模型在初始阶段己标记训练集较少的情况，训练 得到的分类器性能不高的事实，进行了适当的改进。即在自训练分类模型中引入了基于 最近邻规则的数据剪辑技术，试图辨别出在训练过程和分类过程中引入的误标记数据从 而起到净化训练集的目的。在训练的迭代过程中使用该技术，辨别和清除噪音，净化训 练集，提高分类准确率。本文的实验数据集采用u c i 机器学习库中随机抽取的数据集。 实验结果表明，引入该数据剪辑技术后的分类模型相对于原模型在分类准确率上有不同 程度的提高，经过对实验数据进行分析总结，平均分类准确率提高了6 7 0 5 。 本文还针对t r i t r a i l l i n g 分类模型分类能力的局限性，进行了适当的改进。使用了 一种基于不同分类器之间相互合作，利用投票选举的方式对未标记数据进行标记的模 型。该模型针对传统的由z h o u 等人提出的t r i t r a i n i n g 分类模型利用相同分类器之间相 互合作，投票选举的方式给出了改进模型。在基于不同分类器相互合作的同时，如同自 训练分类模型的改进，同样引用了基于最近邻规则的数据剪辑技术，该技术旨在减少噪 音数据净化训练集。实验数据集同样来自u c i 机器学习库中随机抽取的数据集。通过实 验表明，改进后的模型相对原模型在分类精度上有不同程度的改进，经过对实验数据进 行分析总结，分类准确率有不同程度的提高。 关键词：半监督分类；数据剪辑；自训练；未标记数据 大连理工大学硕士学位论文 r e s e a u r c ha i l di m p l e m e n t a t i o no f s e i l l i s u p e r v i s e db a s e ds e l f - t r a m i l l g c 1 a s s i f i c a t i o nm o d e l a b s t r a c t s e m i - s u p e r v i s e dl e a n l i n gi san e ws t u d ) ，i n gm e t h o dp m p o s e di i lr c c e n ty e a r s i tc a nb e d i v i d e dn o 协，0c a t e g o r i e ss 锄i s l l p e i s e dc l a s s 讯c a t i o na i l ds 咖i s u p e r v i s e dd u s t e r i n g r e s p e c t i v e l ya c c o r d i n gt 0i t ss t l l d y i n gp u 印o s e n sm a i ni d e ai st h a th o wc 锄w ec o m b i n et 置l e l a b e l e d 仃a i l l i n gs e tw i ms m a l l 肌m b e ra 1 1 dm e u n l a b e l e do n e sw i t l ll a r g en u m b e rt oi m p r o v et h e p 娟m l a l l c eo ft l l ec l a s s i f i c a t i o n w ed i s c u s ss 锄i - s u p e r v i s e dc l a s s i 丘c a t i o nm a i l l l yi nt 1 1 i sp a p e ra n dw em a k eal o to f r e s e a r c h 觚d 觚a l y s i so ns e l f - 仃a i l l i n ga l g o r i m mw h i c hi s ac l a s s i ca l g o r i t l l mi l ls e i i l i - s u p e i s e dd 嬲s i 6 c a t i o n w ea t t 唧tt o 舀v ea i li m p r o v 酣m o d e lb a s e do nm et 1 1 抽m a t w h e i li ni n i t i a lt 1 1 e 仃a i n i n gs e ti ss os m a l la 1 1 dm ec l a s s i f i e fw eg e tc a nn o tb es oa c c u r a c ya s w eh a v ee x p e c t e d w ei n 仃o d u c ead a t ae d i t i n gt e c l l i l i q u em a tb a s e do nn e a r e s tn e i g h b o rm l e s t oi d e n t i t ) ，m ew r o n g1 a b e l e do n e si 1 1m e 仃a i l l i n g 锄dc l a s s i 伽n gp r o c e s si no f d e rt op 嘶矽t l l e 仃a i l l i n gs e t w ee x p l o i tn l i st e “q u ei nt h ei t e f a t i o np r o c e s so ft 1 1 e 的i 1 1 i n gt 0i d t i 矽a 1 1 d r e i i l o v et l l en o i s ed a t a ，p u r i 矽t h e 仃a i n i n gs e t ，i m p r o v et 1 1 ea c c u r a c yo ft h ec l a u s s m c a t i o n t h e e x p e r i m e n td a t as e t si nm i sp 印e ra r es e l e c t e dr 趾d o m l y 丘0 mm eu c im a c h i n el e a m i n g r 印o s i t o r y 柚d l er e s u l ts h o w st h a tt h ec l a s s i f i c a t i o na c c u r a c yo fm ei m p r 0 v e do n ea r e i m p r o v e dd i 触e n t l y a c c o r d i n gt om ea 1 1 a l y s i so ft h er e s u l tw ec a nc o n c l u d e 廿l a tt h ea v e m g e c l a s s i f i c a t i o np e r f o 肌a j l c ei si i n p r o v e db y6 7 0 5 a c c o r d i n gt om ef i a c tt h a tt h et r i t r a i l l i n gm o d e l sg e n e r a l i z a t i o ni sw e a k ，s ow ea l s o 百v e 觚i m p r 0 v e dm o d e l h lt l l i sp 印e r 趾i m p r o v e dm o d e lt h a tm ed i 任h e n tc l a s s i 丘e r sa r ei n c o o p e r a t i o nw i t l le a c ho t h e ra 1 1 dt l l ev o t em l e i su s e da st l l em l et oc l a s s i 母m eu n l a b e l e dd a t a t h ei m p r o v c do n ei sb a s e do nt l l em o d dt 1 1 a tp r o p o s e db yz h o u a n dw ea l s oi n t r o d u c e 1 e d a t ae d i t i n gt e 蛳q u ea sw eh a v ed o n ei ns e l f - 仃a i l l i n ga 1 9 0 r i l i l lt op u r i 匆m e 仃a i l l i n gs e t t h ee x p e r i m e l l td a t as e ta r ea l s of 沁mt h eu c im a c h i n el e a m i n gr 印o s i t o 巧a c c o r d i n gt oo u r e x p 嘶m e i l td a t a ，w ec a l lc o n c l u d et h a tt h en e wm o d e lw ep r o p o s e dh a v eag o o dp e r f b 锄a i l c e i nc l a s s i 矗c a t i o na 1 1 dt 1 1 ea c c u m c yo fm ec l a u s s i f i c a t i o ni si m p r o v e d k e yw o r d s ：s e m j s u p e r v i s e dc i a s s i f i c a t j o n ；d a t ae d j t i n g ；s e ：- t r a n n g ； u n i a b e 【e dd a t a 1 1 1 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 作者签名： 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 辇堕坠区亟l 达j ：褒丝整亚星章垒錾鏖逝： 作者签名：j 近日期：踔年也月孕日 导师签名： 曼聋日期：上当年上二_ 月二l 日 大连理工大学硕士学位论文 1 绪论 1 1 研究背景与意义 随着互联网技术的飞速发展，越来越多的信息可以通过网络的方式共享，然而随着 网络信息的爆炸式增长，却带来了一系列的问题。如何合理地整理这些半结构化或非结 构化的海量信息以便可以更方便的被人们所利用逐渐成为人们所关心的问题之一。因 此，如何对在线文档进行有效的存档管理，缩短获取所需信息的时间，也就成为一项重 要而迫切的研究课题，也是目前被广泛研究的一个方向，而自动分类正是其中的核心问 题。 传统的文本分类是由人工完成的，即人为的分析了一个网页之后，给它一个比较合 适的类别。然而目前互联网上的网站已经超过1 亿数量大关，并且每月还在以3 5 0 万的 速度增长，因此i n t 锄e t 网上各种信息迅速增加，单纯地依靠人工方式处理代价高昂而 且是不现实的。目前用于自动分类的分类算法主要有n a i v eb a y e s 分类算法、支持向量 机算法( s u p p o r t v e c t o r m a c h i n e ) 、最大熵算法、神经网络以及k 近邻算法( k n e a r e s t n e i g h b o r ) 等。至今没有哪个单独的技术体现出超出其他技术的明显优势。上述几种算 法虽然都可用于自动分类，但无论哪一种分类算法要想达到较好的分类精度都必须要依 靠大量足够的已分类文档进行训练，然而当对某一领域文档需要建立一个新的分类器 时，手工分类大规模训练集就成为快速建立高效准确的分类器的瓶颈。 未标记样本相对于已标记样本是一种廉价的并且相对容易获得的资源。如果能将这 些未标记数据集合结合到监督学习( 分类) 中，使得分类算法可以利用较少的标记数据 和大量的未标记数据来达到大量标记数据作为训练集的情况下所能达到的分类性能，将 大大提高分类性能和节约分类时间。这种将大量未标记数据集合与少量己标记数据集合 相结合来提高分类性能的思想称为半监督分类。 半监督分类算法可以快速建立一种相对高效准确的分类器，从而解决了传统分类需 要手工标记大量数据的瓶颈。它是模式识别和机器学习领域的重要研究领域。特别是在 网页检索和文本分类，基于生物特征的身份识别，图像检索等领域有着较为广泛的应用。 因此对于半监督分类的研究有着特别重要的理论和现实意义。 1 2 研究进展 半监督学习研究主要关注当训练数据的部分信息在缺失的情况下，如何去获得具有 良好的性能和比较高的泛化能力的学习机器。在这里，我们所指的信息缺失指的是训练 半监督自训练分类模型的研究与实现 集合的类别标签丢失或未知的情况。目前国际上有关半监督学习的研究可以根据其用途 大致分为两类，即半监督分类和半监督聚类。本文主要针对半监督分类进行探讨。 根据将已标记数据和未标记数据集合相结合来共同训练分类器的思想在统计学中 早已存在。在1 9 6 8 年就有人已经开始使用已标记和未标记数据通过最大似然共同训练 分类器【1 1 。近年来提出的一种e m ( e x p e c t a t i o nm a ) 【i i i l i z a t i o n ) 算法【2 】也是一种较为流行 的算法。 另外，自训练分类算法也是一种半监督的分类算法，该算法的思想是利用基分类器 对少量的已标记数据集进行训练得到的分类器对可信度较高的未标记数据进行标记，得 到的标记数据添加到训练集中，通过迭代的方式增大训练集，提高分类性能。 b l u m ，a ，m i t c h e l l ，t 提出的c o t r a i l l i n g 【3 j 算法被认为是对半监督学习的一项杰出 贡献。该算法假设属性集可以被分成两个充分冗余的视图，即两个满足如下条件的属性 集：首先，这两个属性集中的任意一个都可以描述该问题，即如果训练集合是充足的， 那么在这两个集合中的任何任意一个中都可得到一个分类性能较好的学习器。其次，在 给定标记的时候，每一个属性集与另外一个属性集都是条件独立的，他们之间不属于互 相依赖的关系，具体的说，他们之间没有任何联系。b l 啪，a ，m i t c h e l l ，t 认为，该充 分冗余条件在不少任务中是可以满足的。例如：在一些网页分类问题上，既可以根据网 页本身的信息来进行正确分类，也可以根据链接到该网页的超链接所包含的信息来进行 正确的分类，这样的网页数据就有两个充分冗余视图。然而在实际应用中的大多数实际 情况下，这两个要求是难以满足的。针对这个问题g o l d m 锄和z h o u 又提出一种改进 的c o t r a i n i n ga l g o r i t i l i i l 【4 】。该算法的提出解决了c o t r a i l l i n g 算法必须要满足两个要求 比较强的条件。然而该算法却要求使用两种不同的监督学习方法把实例空间分成一系列 等价类，然后频繁利用耗时的交叉验证技术来决定如何对问标记数据进行标记。改进的 c o t r a i l l i n g 算法对传统的c o t r a i n i n g 算法进行了改进，但其需要频繁使用交叉验证技 术，这种做法是极其耗费时间的，在有些情况下是令人难以忍受的。 此后，z h o u 和“又针对这个问题提出了一种新的半监督分类方法称为 t r i t r a i l l i n g 【5 j 算法。该半监督分类算法使用三个分类器进行训练。t n t r a i n i i l g 算法对属 性集和3 个分类器所用监督学习算法都没有约束，而且不使用交叉验证，因而适用范围 更广，效率更高。具体来讲，如果这三个分类器中存在任意两个分类器对一个未标记样 例的预测相同，则该样例就被认为具有较高的标记置信度，则利用这两个分类器的预测 结果对该样例进行标注，并将标注后的该样例添加到另外一个分类器的有标记训练集合 中【刨。在对一个未标记样例进行预测其类别时，t r i t r a i m n g 算法不再像以往的算法一样 大连理工大学硕士学位论文 挑选出一个分类器对其进行预测，而是使用了集成学习中经常使用的投票法进行预测。 即，如果有任意两个分类器的预测结果相同，则认为该未标记样例的类别为该预测结果。 1 3 本文的工作 本文首先对文本分类中所涉及到的各种技术如分词、特征提取、特征降维等进行了 系统地论述。另外本文在前人研究的基础上，对典型的文本分类算法进行了研究，主要 对传统的典型的分类算法如b a y e s 分类算法，k 近邻分类算法，支持向量机分类算法进 行了分析和实现，并通过实验对比对上述三种分类性能进行了比较，分析了其分类性能 和分类时间的优劣以期选择一种较为合适的分类算法作为本文后面部分实验中半监督 分类模型的基分类器使用。 另外，本文在第四章和第五章主要针对半监督学习进行了研究，并主要对半监督分 类中的一些典型算法如半监督自训练分类模型，半监督t r i t r a i n i n g 分类模型进行了深 入的分析并通过实验的方法予以实现，最后分别对s e l f - t r a i l l i n g 和t r i t r a i l l i n g 模型做 了适当的改进。例如对半监督自训练分类算法中由于初始训练集比较小，得到的训练器 的分类精度有可能不高，因而在训练过程中不可避免的会引入一些噪音，因此本文在分 析噪音的基础上，引入了一种称为基于近邻规则的数据剪辑技术来消除训练过程中引入 的噪音，并对上述思想进行了编程实现和实验分析对比。而对于半监督t r i t r a i l l i n g 分 类算法在引入数据剪辑技术的同时改变了该算法的三个基分类器，通过利用u c i 机器学 习库中的随机抽取的数据集进行实验。通过实验表明改进后的算法模型相对与原来的模 型在分类准确率上有一定的提高。 1 4 本文的章节安排 本文内容的组织结构安排如下。 第一章绪论，主要介绍半监督分类的研究背景意义以及其研究进展，另外本章还涉 及了本文内容的章节安排。 第二章文本分类技术，主要介绍了传统文本分类中的预处理、特征降维等技术。 第三章几种典型的文本分类算法的研究，主要介绍了k 近邻分类、b a y e s 分类以及 支持向量机分类的原理，同时分别对这三种算法利用u c i 机器学习库中的数据集进行测 试，测试其分类性能与时间性能。通过实验分别对这三种主流的分类算法的原理进行了 分析和对比。 第四章改进的半监督自训练分类算法，主要针对传统的自训练分类算法提出了一种 改进的模型，该模型引入了数据剪辑技术。并且利用实验对自训练分类算法和改进的算 法进行了比较，实验表明改进后的算法有较大改进。 半监督自训练分类模型的研究与实现 第五章改进的t r i - t r a i n i n g 分类算法，主要针对乃l o u 和l i 提出的t r a i n i l l g 算法 模型进行研究并给出了一种改进的模型，该模型对分类器进行了修改同时利用了数据剪 辑技术。对该两种分类模型分别进行实验，实验数据表明改进后的模型有较大改进。 大连理工大学硕士学位论文 2 文本分类相关技术 通过前面一章的介绍，我们可以了解到，要理解和掌握半监督分类算法的原理需要 很多的理论知识，而且半监督分类算法的研究也面临着一些困难，比如在众多传统的分 类算法中如何选择出一种分类性能较高的算法，怎么样同时利用已标记数据和未标记数 据学习来提高分类性能。 为了解决这些问题，我们需要从传统的分类算法即有监督学习开始学习。本章的主 要任务就是详细的阐述传统文本分类算法的理论基础。文本分类宏观上分为文本表示过 程、训练过程、分类过程。首先，对文本进行预处理，将文本用模型表示，进行词频统 计，然后进行特征提取并构造训练分类器，最后对测试文档应用分类得到分类结果。 2 1 文本预处理 2 1 1 中文分词 与英文文本不同，中文文档中词与词之间没有空格分隔，因而若要从连续的汉字串 中正确切割中文词语，需要中文分词。而中文分词的结果的好坏将直接影响分类的效果。 目前国内中文分词做的已经比较成熟。其中最为著名的在分词方面做的较为突出的 机构主要有哈尔滨工业大学和中国科学院计算机技术研究所等。而且这两个机构研发的 该分词软件都是开源的。 众所周知，一篇中文文档中出现的虚词以及其他一些在任何文档中都经常出现的高 频词分类不仅仅没有好处，如果不将这些虚词以及高频词去掉反而会对分类有诸多不利 影响，那么这些词会在分类的过程中被认为是对分类有重要影响的词，因而会导致分类 准确率下降。对这些虚词以及一些高频词的剪切称为停用词处理。停用词主要有以下几 类： ( 1 ) 助词中文中的“的地得 等 ( 2 ) 副词中文中的“很非常”等 ( 3 ) 连词中文中的“是”等 ( 4 ) 冠词中文中的“我你她 等 ( 5 ) 指示词中文中的“这那”等 ( 6 ) 介词中文中的“从到在 等 ( 7 ) 疑问词中文中的“什么哪等 上述这些词对分类没有益处反而徒增弊端，因此在文本预处理阶段就应该过滤掉。 半监督自训练分类模型的研究与实现 2 2 文本表示 文本挖掘处理的是一些以自然语言表示的文本，它们都是是无结构或半结构化数 据，都是一些计算机无法理解的文本，缺少计算机可以正确理解的语义表示。因而计算 机无法直接处理这些无结构或半结构化数据。因此，在大规模文本分类系统中，首先就 要将这些大规模的无结构或半结构化数据转化为计算机可以理解的结构化数据，将这些 计算机无法理解的无结构或半结构化数据转化为计算机可以理解的结构化数据的过程 被称为文本表示。 文本是由许许多多字符组成的字符串，文本的类别是从语义层次上来说的，而文本 对语义的表达是通过句子，而句子的含义则又是通过词语来表达的，因此在表示文本类 别的时候我们可以直接选择词语，即将一句话分成多个词语，这样就可以将一篇文档转 化为一些词语。然而众所周知，在一篇文档中有许许多多的词语，然而并不是所有的词 语对这篇文档的贡献都是相同的，即并不是所有词语在被用来表达该篇文档时的贡献都 是相同的，相反不同的词语对文档的类别具有不同的贡献度，利用特征权重算法可以计 算出词汇在文档中的贡献度。文本特征表示是指以一定特征项( 词汇) 来表示文本，在 文本分类时只需对这些特征项进行处理，从而实现对非结构化文本的处理。现有文本分 类技术的前提假设是特征和文本类别概念密切相关。特征表示模型有许多种，主要包括 向量空间模型、布尔模型和概率模型等。 ( 1 )向量空间模型( v e c t o rs p a c em o d e l ) 向量空间模型( v e c t o rs p a c em o d c l ) 是由g e r a r ds a l t o n 和m e g i l l 等【7 】于1 9 6 9 年提 出。该模型最早被成功地应用在信息检索领域。后来随着大量学者研究的深入以及文本 分类技术的成熟，又被成功的应用在文本分类领域。向量空间模型的基本思想是：将每 个特征项作为特征空间坐标系的一维，用特征空间的向量来表示文本，并用两个向量之 间夹角的余弦值来衡量两个对应的文本的相似度。而该模型的一个假设是，一个文本所 属的类别仅与某些特定的单词或词组在该文档中出现的频数有关，而与这些单词或词组 在该文本中出现的位置或顺序无关。也就是说，如果将构成文本的各种语义单位( 如单 词或词组等) 统称为“特征项”，以及特征项在文本出现的次数称为“词频”，那么一 个文本中蕴含的各个特征项的频率信息足以用来对其进行分类。 综上所述，在向量空间模型中，每个文本都被形式化为行维空间中的向量，因此可 以将文本抽象化为式2 1 所示。 y ( d ) = ( w ( ) ，w ( f ：) ，w ( ) ，w ( 乙) ) ( 2 1 ) 大连理工大学硕士学位论文 其中，是特征项，研为文本空间的维数，“) 是函数，其基本功能是计算特征项 t 在文本向量中的权重，函数的自变量是特征在文本中出现的频率和在整个文本集合中 出现的频率，可以认为函数以) 由两部分组成，如式2 2 所示。 w ( ) = 三( f ，) c ( f ) ( 2 2 ) 第一部分为局部权值( f ，j ) ，表示第f 个特征项在第篇文本中的权重，第二部分 为全局权值c ( f ) ，即为第f 个特征项在整个文本集合中的权值。设圻，和蜕分别表示第f 个特征项在第，篇文本中出现的频度和在整个文本集合中出现的频度，z 为文本集合的 总数，以下为常见的局部权值计算公式。 词频法：吮 布尔函数法：f 1 舻o 、u 盯酽0 平方根法：吮 对数词频法：l o g ( 吮+ 1 ) 以下为常见的全局权值计算公式。 n o m a l 法： i d f 法：l 0 9 2 ( ) + l y 引一莩尝 对于一个训练文本集合，就可得到如图2 1 所示的一个向量空间w 。 w 通常是一个稀疏矩阵。训练文本和待分类文本在向量空间模型中都可用相同的方 法表示出来。待分类文本的向量越接近训练文本向量，说明其与训练空间中的文本的相 似度越大，越有可能和训练文本属于同一个类别。在计算时，相似度通常用向量之间的 内积来度量，如式2 3 所示。 s f m ( d l ，d 2 ) = ( w l t w 2 女) ( 2 3 ) 或者向量之间的夹角的余弦值度量，如式2 4 所示。 半监督自训练分类模型的研究与实现 跏( 吐，畋) = 疗 ( w l 七w 2 。) 七= i 、 文 本 特征顼 d ld j a m w h t l t i w 扩 厶 m ” 图2 1向量空间模型下的文本表示 f i g 2 1 t 暇td e s 谢p t i o nu s i i l gv e c t o rs p a c em o d e l ( 2 4 ) ( 2 ) 布尔模型( b 0 0 l e a l lm o d e l ) 布尔模型在传统的信息检索领域中有广泛的应用，它通过与用户给出的检索进行逻 辑比较来检索文本，是一种基于关键词的匹配。布尔模型采用布尔表达式对文本进行表 示，在标准的布尔模型中，文本采用如式2 5 表达形式。 d f = ( w l ，2 ，w k ，w k ) ，后= 1 ，2 ，刀 ( 2 5 ) 其中：，l 为特征项的个数，w 。为o 或1 ，表示第后个特征项在文本f 中是否出现。 布尔模型易于实现，但在文本分类领域，它的准确率和召回率较差。 ( 3 ) 概率模型( p r o b a b i l i s t i cm o d e l ) s t e p h e nr o b e n s o n 和s p a r kj o n e s 等人【s 】提出的概率模型是另外一种文本表示方法， 该种表示方法也得到了广泛认可。它综合考虑了词频、文档频率和文档长度等因素，把 文档和用户兴趣( 查询) 按照一定的概率关系融合。概率模型有多种形式，常见的一种 是贝叶斯概率模型，它用概率架构来表示特征项，将训练实例分解为特征向量和决策类 大连理工大学硕士学位论文 别向量，并且假定特征向量的各分量独立地作用于决策变量。虽然这个假设在一定程度 上限制了贝叶斯概率模型的适用范围，然而在很多领域即使违背这种假定的条件下，该 模型也表现出相当的健壮性和高效性，已经成功应用到信息检索、分类和聚类等领域中。 2 3 特征降维 我们在结束了对中文文档进行分词操作后，可以将分词后所得到的所有词语作为表 示该文档的一个特征项。然而，由于一个文档所包含的数据量有可能非常大，并且存在 一些虚词、介词等对分类结果不但没有贡献，相反对分类结果只有较坏影响的词语，因 此在使用特征向量来表示一篇文本的时候，向量的维数有可能会非常高。而较高的向量 维数对分类的复杂度肯定会产生较坏影响。如何利用较少的向量维数去得到较好分类精 度，成为一个研究方向。在目前阶段，通常在分类之前通常会进行一些预处理操作，比 如去掉停用词、虚词、介词等等对分类无关的词语，但仅仅通过这种方法仍然无法显著 地降低特征向量的维数。高维特征向量会大大降低机器学习的效率，而学习的效果并不 比低维特征子集的效果更好。另一方面，一些特征项在某些类中发生频繁，有更好的分 类效率，而另一些特征项只会给分类带来噪音。因此文本分类系统应该尽可能地选择与 文本类别密切相关的特征进行分类，这就需要有效地进行特征维数约简，在不显著牺牲 分类准确度的前提下，去除文档中信息量小、相关度低的项以降低特征向量的维数，从 而提高分类效率并降低计算的复杂度。维数约简大致包括两种方法，特征抽取和特征选 择【9 1 。 ( 1 ) 特征抽取也叫特征重参数化。由于在自然语言中存在大量的多义词、同义词 现象，特征集无法生成一个最优的特征空间对文本内容进行描述。特征抽取是将原始特 征空间进行变换，重新生成一个维数更小、各维之间更独立的特征空间，可以看作从测 量空间到特征空间的一种映射或变换。其主要的方法有特征聚类、主成分分析和潜在语 义标引等。 ( 2 ) 特征选择是从特征集丁= 毡，乞，) 中选择一个真子集丁= 毛，乞，) ( j 尸( xjc ，) 尸( c ，) 1 小，f 。换言之，x 被指派到其 尸( z l g ) p ( q ) 最大的类g 。 “贝叶斯分类的效率如何? 理论上来讲，与其他所有分类算法相比，贝叶斯分类 具有最小的出错率。然而，实践中却并非如此。主要是由于对其应用的假定( 如类条件 独立性) 的不准确性，以及缺乏可用的概率数据造成的。然而种种实验研究表明，与判 定树和神经网络分类算法相比，在某些领域，该分类算法可以与之媲美。 贝叶斯分类还可以用来为不直接使用贝叶斯定理的其他分类算法提供理论判定。例 如，在某种假定下，可以证明正如朴素贝叶斯分类一样，许多神经网络和曲线拟合算法 输出最大的后验假定。 如下例使用朴素贝叶斯分类预测类标号。 训练数据如下表3 1 所示，数据样本用属性天气0 u t l o o k ，温度t 锄p e r a t l 玳，湿度 h u m i d i t ) ，和风强度w i n d y 描述。类标号属性是否打球p 1 a y t e l l i l i s 具有两个值( 即y e s ， n o ) 。设q 对应于类p 1 a y t e n i l i s = “y e s ，而c 2 对应于类p l a y t e l l i l i s = “n o ”。我们希 望分类的未知样本为 x = ，判断该未知 样本的类别为是否打球。 我们需要最大化p ( xg ) 尸( g ) ，卢1 ，2 。每个类的先验概率p ( q ) 可以根据训练样 本计算。 尸( 册) ，乃刀玎西= ”y 嚣”) = 9 1 4 = o 6 4 3 尸( 砌死甩玎捃= ”刀o ”) = 5 1 4 = o 3 5 7 为计算尸( xg ) ，i - 1 ，2 ，我们计算下面的条件概率： 尸( d ”f 肠d 后= ”- 鼬以砂”lp 伽死力刀捃= ”y 船”) = 2 9 = o 2 2 2 尸( d “f 肠d 后= ”- 珂缈”l 脚死咒咒妇= 刀d ”) = 3 5 = o 6 0 0 尸( 死唧绷伽旭= ”胁，i 尸伽死胛，z 括= 心”) = 2 9 = 0 2 2 2 尸( 死挣驴p ，n 伽，| p = ”上面f i 脚砌押括= ，l d ”) = 2 5 = 0 4 0 0 p ( 协m f 讲纱= 鳓”ip 衄，死咒以妇= ”声”) = 3 9 = 0 3 3 3 尸( 协聊触纱= ”蚴 i 尸啦) ，死，l 咒括= ”以o ”) = 4 5 = o 8 0 0 大连理工大学硕士学位论文 尸( 砌咖= ”慨”ip 伽死刀以西= ”弦”) = 3 9 = 0 3 3 3 尸( 砌咖= ”跚略”i 肋y 砌刀括= ”刀d ”) = 3 5 = 0 6 0 0 使用以上概率，我们可以得到 尸( x l 脚7 0 ，z 刀括= ”归”) = o 2 2 2 o 2 2 2 o 3 3 3 o 3 3 3 = o 0 0 5 p ( x l 脚7 匆玎咒括= ”，l d ”) = o 6 0 0 o 4 0 0 0 6 0 0 o 6 0 0 = o 1 1 5 尸( xi 尸红) ，死万玎西= ”y 嚣”) p ( p 幻y 死以咒括= ”心”) = 0 0 0 5 o 6 4 3 = o 0 0 3 尸( xi 尸幻y 死以，z 西= ”，l d ”) p ( p 红) ，死以力妇= ”刀d ”) = 0 1 1 5 o 3 5 7 = 0 0 4 l 因此，对于样本x ，朴素贝叶斯分类预测砌y 死，l 以括= ”加”。即在 ( d ”如d 尼= 舰咒砂，死叩咖m 陀= 胁f ，协聊砌纱= 劢酚，臃孢d = 跚增 的情况下不去打 球。 表3 1 训练数据 t a b 3 1 t r a i n i n gd a t as e t d a y o u t l o o k t e l l l p e r a t l l r eh u m i d i 田 w i n d p 1 a y t e m l i s d 1 s u 衄y h o t h i 曲 w e a kn o d 2 s u 皿y h o t h i g hs 仃o n g n o d 3o v e r c 嬲th o t h i 时lw e a ky e s d 4r a i nm i l d h i 曲 w e a i 【y e s d 5r a i nc o o ln o 肌a lw e a ky e s d 6i h i nc o o ln o m a l s 仃o n 2 n o d 7o v e 疋鹊tc o o ln o m a l s 仃o n gy e s d 8 s u 衄y m i l d h i 曲 w e a k n o d 9s u 皿vc o o ln o m a lw e 出y e s d 1 0r a i nm i l dn o 姗a lw 朗ky e s d1 1 s u i l n y m i l dn o 册a l s 缸o n 2 y e s d 1 2o v e 疋a s tm i l d h i 2 l l s n o n 2 y e s dl3o v e r c a s th o t n o 珊a lw e a ky e s d 1 4r a i l lm i l d h i g hs 仃o n g n o 3 3 支持向量机方法 v l a d i m i rn v a p i l i k 等人【1 6 】从2 0 世纪6 0 年代开始就致力于研究有限样本的机器学 习问题，经过几十年的研究，到9 0 年代中期终于形成了一个较为完整的理论体系，即 统计学习理论( s t a t i s t i c a ll e 锄i n gm e o 巧) 。近几年来，在统计学习理论的基础上又发展 出一种新的学习机器，即支持向量机( s u p p o r tv e c t o rm a c l l i n e ，s ) ，它不仅具有扎实 的理论基础，而且在许多领域比大多数算法更准确，尤其在处理高维数据时。另外它在 解决小样本、非线性等问题中表现出许多特有的优势。因而，一些研究人员认为支持向 一1 9 半监督自训练分类模型的研究与实现 量机可能是解决文本分类问题的最准确的算法。它也被广泛应用于网页分类和生物信息 领域。 支持向量机建立在计算学习理论的结构风险最小化的原则之上，也就是使真实错误 概率的上界最小，主要用来解决二值分类的模式识别问题。支持向量机的一个最重要的 优点是使用简单的线性分类器划分样本空间，可以处理线性不可分的情况。线性可分是 指存在一个超平面，把训练集按照类别一分为二。对于线性可分的情况，支持向量机找 到一个最优的决策面，它能最好的分隔两类样本。而对于线性不可分的情况，则使用一 个核函数把样本映射到一个高维空间中，然后在高维空间中寻找一个超平面做为两种类 别的分割，并且保证最小的分类错误率。 对于文本分类中的二分类问题，采用支持向量机进行分类可以定义为以下问题：给 定训练文本集： & j j ) ，( 而批) ，帕) ，x 尺“，y + l ，一1 ) 其中，玉为文本喀( 1 f 盯) 的特征向量所属的类别，m = 1 表示文本盈属于第一 个类型，弘= 1 表示文本谚属于第二个类型； 文本分类就是要找到一个满足公式3 9 所示的最优超平面将这两类文本分开。 厂：只 ( w ，薯) 一6 】 = 1 ，江1 ，刀 ( 3 9 ) 对于线性可分的情况，在分类二维空间上的最优超平面如图3 2 所示。 图3 2 二维空间最优超平面 f i g 3 2o p t i i i l a lh y p e r - p l a n e 似。一d i i l l 胁s i o n a ls p a c e 大连理工大学硕士学位论文 3 4 选取高性能算法 本实验在数据挖掘领域中应用比较广泛的工具w e k a 下进行。w e k a 是由新西兰怀 卡托大学在1 9 9 3 年利用j a w l 语言开发的一种开源的数据挖掘工具，可以运行在所有 操作系统中。w e k a 工作平台包含能处理所有标准数据挖掘问题的方法：回归、分类、 聚类、关联规则挖掘以及属性选择。下载网址为：h 仕p ：r 、 n ) l ，c s w a i k a t 0 a c i l z m l w e k a 。 本文所采用的数据集来自数据挖掘领域中机器学习库中的u c i 数据集中的数据。下 载网址为：h t t p ：， ) l n ) l 僻i c s u c i e d l l 哪! e 硼1 m lr 印o s i t o w h n l l l 。本实验采用其中几个比 较大的数据集进行测试。 本实验的数据集从u c i 数据集中随机抽取7 个实验集进行测试，测试集的信息如表 3 2 所示。 表3 2 实验数据集信息 t a b 3 2i n f oo f d a t as e t s d a t as e tn oo fi n s t a n c 鹪n oo fa t n j b u t e sc l a s sc l a s sd i s t r i b u t i o n m u s h r o o m s i c k v o t e g l a s s v e h i c l e d i a b e t e s a u d i o l o g y 8 1 2 4 3 7 7 2 4 3 5 2 1 4 9 4 6 7 6 8 2 2 6 2 2 3 0 1 7 1 0 1 8 9 7 0 5 1 8 4 8 2 9 3 8 6 2 4 5 2 5 4 8 3 2 7 3 5 5 7 9 6 1 4 2 1 3 6 42 5 1 2 5 7 2 5 8 2 3 4 26 5 1 3 4