作者：唐焕玲
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
基于半监督与集成学习的文本分类方法试读：
内容简介
文本分类技术广泛应用于新闻媒体、网络期刊文献、数字图书馆、互联网等领域，是人类处理海量文本信息的重要手段。
本书重点探讨了利用信息论中的评估函数量化特征权值的方法；基于权值调整改进Co-training的算法；利用互信息或CHI统计量构造特征独立模型，进行特征子集划分的方法；基于投票熵维护样本权重的BoostVE分类模型；融合半监督学习和集成学习的SemiBoost-CR分类模型。
其中特征选择和权值调整方法、基于特征独立模型划分特征子集的方法适用于文本分类，其他算法不仅适用于文本分类，对机器学习和数据挖掘的其他研究也有较大的参考价值和借鉴作用。
本书适合研究方向为文本挖掘、机器学习的硕士、博士研究生及相关专业技术人员学习和参考。未经许可，不得以任何方式复制或抄袭本书之部分或全部内容。版权所有，侵权必究。图书在版编目（CIP）数据基于半监督与集成学习的文本分类方法/唐焕玲著．—北京：电子工业出版社，2013.8ISBN 978-7-121-21256-7Ⅰ.①基… Ⅱ.①唐… Ⅲ.①文字处理—研究 Ⅳ.①TP391.1中国版本图书馆CIP数据核字（2013）第188126号责任编辑：张 京文字编辑：薄 宇印 刷：三河市鑫金马印装有限公司装 订：三河市鑫金马印装有限公司出版发行：电子工业出版社 北京市海淀区万寿路173信箱 邮编 100036开 本：900×1 280 1/32 印张：5.875 字数：205千字印 次：2013年8月第1次印刷定 价：29.00元
凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系，联系及邮购电话：（010）88254888。
质量投诉请发邮件至zlts@phei.com.cn，盗版侵权举报请发邮件至dbqq@phei.com.cn。
服务热线：（010）88258888。前 言
文本分类（Text/Document Categorization）是指按照预先定义的主题类别，通过一定的学习机制，在对带有类别标签的训练文本进行学习的基础上，给未知文本分配一个或多个类别标签的过程。文本分类技术广泛应用于新闻媒体、网络期刊文献、数字图书馆、互联网等领域，是人类处理海量文本信息的重要手段。数据挖掘技术在信息检索、邮件过滤、Web个性化服务等领域的成功应用均在一定程度上依赖于准确的文本分类技术。因此，文本分类技术的相关研究一直是近年来国际学术界的研究热点。
本书对文本分类的关键技术进行了概述，阐述了基于半监督学习和集成学习的国内外相关研究，重点对基于半监督学习和集成学习的文本分类方法进行了深入探讨。
本书的第1章介绍了研究背景、文本分类及其面临的问题，阐述了基于半监督学习和集成学习的文本分类方法的研究意义和国内外研究现状。第2章对文本分类的关键技术进行了概述，主要包括文本预处理、文本的表示、特征选择、分本分类方法、实验数据集及分类模型的评估方法。第3章分析了特征选择存在的问题，采用信息论中的评估函数量化特征的重要性，调整特征的权值，提出TEF-WA权值调整技术；分析比较了文档频率﹑信息增益（Information Gain，IG）、期望交叉熵（Expected cross Entropy）、互信息（Mutual Information，2MI）、χ统计量（CHI）、文本证据权（Weight of Evidence for Text，WET）和几率比（Odds Ratio）等多种评估函数及实验结果。第4章分析了半监督学习中的代表方法Co-training算法，提出了利用TEF-WA技术对Co-training改进的算法TV-SC和TV-DC，通过评估两个基分类器之间的差异性，可间接评估两个特征视图的独立性，并通过实验证明了所提方法的有效性。第5章针对Co-training方法的独立性假设问题，提出了利用互信息（MI）或CHI统计量评估特征之间的相互独立性的方法，构造了一种特征独立模型（MID-Model）。基于该模型提出了特征子集划分方法——PMID算法，以便把不存在自然划分的一个特征集合划分成两个独立性较强的子集，进而提出了改进的半监督分类算法——SC-PMID算法。并且对由PMID算法划分得到的两个特征子集之间的独立性进行了理论论证。第6章分析了集成学习算法AdaBoost算法不能有效提升Naïve Bayesian分类器的原因，提出了基于投票信息熵和多视图的AdaBoost改进算法——BoostVE算法，采用基于投票信息熵的样本权重维护新策略，能有效提高Naïve Bayesian文本分类器的泛化能力。理论分析证明改进的BoostVE算法的最小训练错误上界优于AdaBoost。第7章基于半监督学习和集成学习，提出了置信度重取样的SemiBoost-CR分类模型，给出了基于最大差距和基于相似近邻两种置信度计算方法。实验表明利用少量标注样本和大量未标注样本，SemiBoost-CR分类模型能够明显提升Naïve Bayesian文本分类器的性能指标。第8章介绍了采用VC++ 6.0实现的中英文文本分类系统SECTCS，阐述了SECTCS系统的原有的功能与新扩展的功能、总体结构、主要的用户界面及操作。
本书的研究工作得到了山东省高校智能信息处理重点实验室（山东工商学院）、国家自然科学基金项目（No.61073133，No.61175053，No.61272369，No.61272244）及山东省优秀中青年科学家科研奖励基金计划项目（S2010DX021）的资助，特此表示感谢。唐焕玲2013年3月第1章 绪论1.1 研究背景及意义1.1.1 数据挖掘和文本挖掘
随着信息技术和网络技术的迅速发展，网络数据规模呈指数增长，Internet已发展成站点遍布全球的巨大信息服务网络，包含了涉及许多领域的丰富的信息资源。面对内容异构的海量信息，传统的数据分析方法只能获得数据的表层信息，无法获得数据属性的内在关系和隐含的信息，难以适应需求的不断发展。数据挖掘和知识发现（Data Mining ＆ Knowledge Discovery in Database，DM＆KDD）是20世纪90年代兴起的一门信息技术领域的前沿技术，它是在数据和数据库急剧增长远远超过人们对数据处理和理解能力的背景下产生的。
数据挖掘（Data Mining，DM）是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中采掘出隐含的、先前未知的、对[1]决策有潜在价值的知识和规则。知识发现（Knowledge Discovery in Databases，KDD）指识别出存在于数据库中有效的、新颖的、具有[2]潜在效用的、最终可理解的模式的非平凡过程。数据挖掘是一个交叉学科领域，受多个学科的影响，包括数据库系统、统计学、机器学习、可视化和信息科学等。此外，依赖于所用的数据挖掘方法及可使用的其他学科的技术，如神经网络、粗糙集理论、知识表示、归纳逻辑程序设计或高性能计算。依赖于所挖掘的数据类型或给定的数据挖掘应用，数据挖掘技术也可能集成空间数据、信息检索、模式识别、图像分析、信号处理、计算机图形学、Web技术、经济、商业、生物[1]信息学或心理学领域的技术。
传统的数据挖掘技术，主要针对的是结构数据，如关系的、事务的、数据仓库的数据。随着数据处理工具、先进数据库技术及网络技术的迅速发展，大量的形式各异的复杂类型的数据（如结构化与半结构化数据、超文本与多媒体数据）不断涌现。因此数据挖掘面临的一个重要课题就是针对复杂数据的挖掘，这包括复杂对象、空间数据、多媒体数据、时间序列数据、文本数据和Web数据。
文本挖掘是数据挖掘领域的一个分支，在国际上，文本挖掘是一个非常活跃的研究领域。从技术上说，它实际是数据挖掘和信息检索两门学科的交叉。文本挖掘与传统数据挖掘的差别在于文本数据与一般数据的巨大差异。传统数据挖掘所处理的数据是结构化的，如关系的、事务的、数据仓库的数据。其特征数通常不超过几百个，而文本数据没有结构，转换为特征矢量后特征数将达到几万甚至几十万。所以，文本挖掘既采用了很多传统数据挖掘的技术，又有自己的特性[5-14]。
近年来随着Internet的大规模普及和企业信息化程度的提高，信息积累越来越多，Internet已经发展为当今世界上最大的信息库。Internet上的信息，绝大多数是以网页形式存放的，而网页的内容又多以文本方式来表示，传统的信息检索技术已不适应日益增长的大量文本数据处理的需要。如何快速、准确地从来自异构数据源的大规模的文本信息资源中提取符合需要的简洁、精炼、可理解的知识，就要用到文本知识挖掘。Internet的发展极大地促进了文本挖掘的发展。
文本挖掘（Text Mining，TM）：以计算语言学、统计数理分析为理论基础，结合机器学习和信息检索技术从文本数据中发现和提取独立于用户信息需求的文本集中的隐含知识。它是一个从文本信息描述[6]到选取提取模式，最终形成用户可理解的信息知识的过程。根据KDD的框架，结合文本挖掘的定义和特点，文本挖掘的过程示意图如图1.1所示。开始处是原始文本信息源，最终结果是用户获得的知识模式，经历了信息预处理→文本挖掘→质量评价三个主要阶段。图1.1 文本挖掘的过程示意图1.1.2 文本分类及其面临的问题
文本分类（Text Categorization，TC）是文本挖掘中最重要的研究领域之一。对文本进行准确、高效的分类是许多数据管理任务的重要组成部分。数据挖掘技术在信息检索、邮件过滤和提供个性化的服务等方面，均在一定程度上依赖于准确的文本分类技术。
1．文本分类的定义
所谓文本分类，是指按照预先定义的主题类别C={c，c，…，12c}，通过一定的学习机制，在对带有类别标签的训练文本D={(x,y),L11…,(x,y)}进行学习的基础上，给未知文本分配一个或多个类别的过NN程。其中C可以是并列的也可以分层次组织起来的。可以用一个目标[1]函数φ:D×C→{T,F}来描述文本分类，称φ:D×C→{T,F}为分类规则或假设或模型，对x∈D,c∈C，(x,c)→T表示x属于类别c；而(x,c)→Fijijijij表示x不属于类别c。ij
这里，文本既可以是传统的纯文本，也可以是经过HTML Parser等网页解析工具去掉网页标记、转换成纯文本的网页（Web文档），网页可以看做是特殊的文本。Web上的信息资源大多以HTML页面或XML页面的形式存在，与一般文本的表示不同，网上大量半结构化的文本及其之间的超链接提供了多于传统文本的有用信息，如标题、段落标题、超链接文字、链接及所用的字号等辅助信息为文本分类提供了更多的有用信息。根据Web网页的具体特性，一般可以从两个方面来选取网页特征项：① 通过提取网页内容中的关键词；② 利用网页中的有关标识符及其结构特征。Web网页经过HTML Parser等网页解析工具，去掉网页标记，可转换成纯文本。
文本分类的过程一般包括文本预处理、特征约简、训练与分类、分类结果的评价和反馈等过程，如图1.2所示。
本书研究的基于半监督学习和集成学习的文本自动分类方法，既适用于纯文本的分类，也可应用于网页的分类。在后续的章节，没有特别说明时，文本泛指纯文本和经过预处理后的Web文档。图1.2 文本分类的一般过程
2．文本分类的发展
文本分类是信息检索与数据挖掘领域的研究热点。1960年Maron在Journal of ASM上发表了有关自动分类的第一篇论文, 标志着文本分[8]类技术的诞生，而H. P. Luhn 在这一领域进行了许多开创性的研究工作。随后许多著名的情报学家如K. Sparch、G. Salton 及R. M. [9-11]Needham 等都在这一领域进行了卓有成效的研究。
文本自动分类在国外大体经历了三个发展阶段：
第一阶段（1960—1964），主要进行文本自动分类的可行性研究；
第二阶段（1965—1974），进行自动分类的实验研究；
第三阶段（1975至今），自动分类进入实用化阶段，新方法和新系统层出不穷。
我国的自动分类工作也经历了这三个阶段，只是起步较晚。1981年侯汉清先生在国内首次对文本自动分类进行探讨，此后国内一些科研院所也相继开展了文本分类研究，在分类理论和应用特别是中文文本分类方面取得了众多成果。2007年侯汉清教授承担的国家社科基金项目“基于知识库的网页自动标引和自动分类研究”结题。
目前国外开展文本自动分类研究比较著名的机构包括卡耐基梅隆大学（CMU）、麻省理工学院（MIT）、加州大学伯克利分校、康奈尔大学、马里兰大学、微软剑桥研究院、微软亚洲研究院、IBM研究中心、卡耐基集团等。国内比较活跃的单位有清华大学、北京大学、复旦大学、上海交通大学、哈尔滨工业大学、东北大学、北京邮电大学、中国科学院（计算所、软件所、计算机语言信息工程研究中心）、南京大学、纳讯科技公司、西风网站等。此外国内外还有大批研究机构和公司也在从事同类研究。
从文本分类使用的方法上说，主要有：① 20世纪80年代基于知识工程和专家系统的文本分类模式；② 20世纪90年代逐渐成熟的基于机器学习的文本分类方法，更注重分类器的模型自动挖掘和生成及动态优化能力，在分类效果和灵活性上都比之前基于知识工程和专家系统的文本分类模式有所突破，成为相关领域研究和应用的经典范例。
文本分类的主要方法包括决策树（Decision Tree）、K近邻算法（K Nearer Neighbors Classifier）、线性分类器（Linear Classifier）、回归模式（Regression Models）、简单Bayesian网络（Bayesian belief Networks）、规则学习算法（Rule Learning Algorithms ）、BP神经网络（BP Neural Networks）、归纳学习技术（Inductive Learning [15-33]Techniques）、支持向量机（Support Vector Machine，SVM）等。20世纪90年代出现了基于集成学习的分类方法，即组合多个分类器以克服单个分类器的不足，有效提高了分类的精度，已成为一个研究[34-38]热点，Boosting和Bagging方法是其中的代表算法。
3．文本分类面临的问题
文本分类技术能够较好地解决大部分具有数据量相对较小、标注比较完整及数据分布相对均匀等特点的应用问题，但是对大规模应用[33]仍受到很多问题的困扰，目前面临着诸多挑战，本书主要讨论以下两点。（1）标注瓶颈问题
传统的有监督分类算法（Supervised Categorization Algorithm）需要提供足够的已标注训练样本（Labeled Data），但是已标注的训练样本集的建立需要专家知识，费时费力，代价高，获取困难，制约了分类模型的建立，致使许多实际问题的研究无法开展，这就是所谓的标注瓶颈问题。然而，互联网上存在大量未标注样本（Unlabeled Data），获取相对比较容易。因此，利用大量的未标注样本结合少量的标注样本的半监督分类（Semi-supervised Categorization）的研究引起了学术界比较广泛的关注。
针对标注瓶颈问题，基于半监督学习（Semi-supervised [39-41][47-56]Learning）的分类方法是比较有效的解决方法。半监督学习在文本分类、图像分类、邮件过滤、机器翻译、主题词识别、词性标注等方面都有广泛的应用。基于半监督学习的分类称为半监督分类（Semi-supervised Categorization或Semi-supervised Classification），其研究重点在于使用大量的未标注（Unlabeled）样本，结合少量的标注（Labeled）样本训练生成分类器，提高分类器的性能指标。
半监督分类的研究虽然已经取得了不少成果，但是也存在许多值得探讨和亟待解决的问题。例如，半监督分类算法的应用存在一定的约束条件；半监督分类的精度还有待提高；半监督分类算法往往要付出大量的迭代代价，计算复杂度比较高等。如何提高半监督分类的精度、降低计算复杂度，是值得研究的问题。基于半监督学习的文本分类方法的研究，在理论和实践上都是比较有意义的研究方向。（2）分类方法本身存在局限性
分类技术在其发展过程中出现了许多经典的分类方法，如决策树方法、Naïve Bayesian学习方法、神经网络（Netware Net）、K近邻法（K Nearest Neighbor）、支持向量机（Support Vector Machine，SVM）等，由于受到分类方法本身的局限性，这些经典方法的性能[3][15-33]指标在原有基础上很难进一步提高。因此，基于集成学习的分类方法，即组合多分类器来提高分类的精度成为学术界比较关注的另一个研究方向。
集成学习（Ensemble Learning）是一种机器学习范式，多个学习器的单独决策被以某种方式组合起来（通过加权或无权重投票）解[34-38]决同一个问题。集成学习技术已经在行星探测、地震波分析、Web信息过滤、生物特征识别、计算机辅助医疗诊断等众多领域得到了广泛的应用。在文本挖掘领域，集成学习技术可用于文本分类、文本过滤等；在网络挖掘方面，集成学习技术在网页分类、信息检索和网络用户行为分析——偏好排序方面都有应用。由于集成学习技术可以有效地提高学习系统的泛化能力，因此成为国际机器学习界的研究热点，并被国际权威T. G. Dietterich 称为当前机器学习四大研究方向之首。
鉴于文本分类面临的这两种挑战，利用少量标注样本（Labeled Data）和大量的未标注样本（Unlabeled Data）的半监督分类（Semi-supervised Categorization）和组合多个分类器来提高分类性能的集成学习（Ensemble Categorization）是近年来模式识别和机器学习领域的研究热点，也是本书研究的主要内容。1.2 国内外相关研究1.2.1 半监督学习
半监督学习是模式识别和机器学习研究领域的热点之一，在文本分类、图像分类、邮件过滤、机器翻译、主题词识别、词性标注等方面得到了广泛的应用。根据半监督分类算法的实现方式，现有的典型方法大致分为五种：基于生成模型（Generative Model）的半监督分[39-43][44-46]类方法、自训练方法（Self-Training）、协同训练方法（Co-[47-56][57-59]Training）、基于图的半监督分类方法、直推式支持向量机方[60-64]法（Transductive SVM，TSVM）等。
1．EM算法
Dempster、Laird和Rubin提出的EM（Expectation-Maximization）
[40]算法是一种对不完整数据进行最大化参数估计的迭代算法。结合标注文本和未标注文本的信息进行半监督学习，未标注文本的类别可以看成缺失的值。Nigam结合EM算法和Naïve Bayesian算法，从标注文[41-42]本和未标注文本中学习，改进了Bayesian分类器的分类效果，是基于生成模型（Generative Model）的半监督分类方法的典型代表。
初始时，只使用标注样本集，建立Naïve Bayesian分类器，然后[41]重复交替执行E步骤和M步骤，达到使似然函数增加的目的。直观地，EM试图在未标注样本的分布上建立最大可能的分类假设，EM算法可以看成未标注样本在初始的标注训练样本“周围”的聚类。
标注文本集和未标注文本集组成混合模型（Mixture Model），当标注文本集的数目远远小于未标注文本集时，EM的参数估计在很大程度上来源于未标注文本集。当未标注文本集上的无监督聚类学习产生的类别与标注文本集的类别不一致时，反而会降低分类的正确性。EM-λ算法是Nigam在基本的EM算法上，引入了一个参数λ(0≤λ≤1)，[39][42]以调整未标注文本在EM算法中的权重。
2．Self-training算法
Self-training首先使用由少量的标注样本训练生成分类器对未标注样本分类，选出置信度高的未标注样本，加上预测的类标记，添加到训练样本集中重新训练，迭代这个过程。Self-training 又称Self-teaching或Bootstraping。为了避免一个分类器强化自己的错误，通常当置信度低于某个阈值时就停止迭代，或者使用Co-training方法。[44]Self-training在主题名词的识别、emotional和non-emotional的对话
[45][46]分类、图像检测等应用领域取得了比较好的效果。
3．Co-training算法[47-49]
Co-training算法最早由Blum和Mitchell提出，假设数据集可以被自然地分成两个独立的特征子集（视图），每个子集都包含足够的信息进行分类学习，在每个视图上建立各自的分类器，两个分类器每次互相标记一部分置信度高的样本给对方，重新训练，迭代直到没有更多适合的未标注样本加入。Blum和Mitchell将Web文本集分成两个视图，视图V由Web网页上的单词组成，另一个视图V由指向其他网12页的超链接的单词组成。任意样本x 可以用一个三元组(x,x,c)表示，12这里，x和x是x在两个视图中的描述，c是它的类别。Co-training算12法要求两个特征视图满足假设：① 一致性（Compatible），② 独立性（Uncorrelated）。前者表示，样本的分布与分类的目标函数是一致的，12也就是说，对大多数样本x：f(x)=f(x)=f(x)，目标函数在每个特征子12集上预测的类别是完全相同的。后者表示对指定类别的任意的样本(x,x,c)，P(x|f(x),x)=P(x|f(x))，也就是说，样本x和x在两个视图中1212112[47-49][56]的描述是独立的。
实际上由于多种原因，这两个假设并不能完全严格地满足，尤其是独立性，甚至在许多实际应用中不存在自然划分且满足这种假设的[50]两个视图。Goldman和Zhou使用两个不同的学习器在同一个特征视图进行共同训练，Zhou和Goldman提出了在单个特征视图上多个分类器的Democratic Co-learning算法，如果大多数分类器给未标注样本xu的分类一致，则把x连同它的标注一起加入训练样本集，所有分类器u[51]在更新的训练样本集上重新训练。类似地，周志华提出了使用三个[54]分类器的Tri-training算法。Muslea提出了多视图（Multi-views）与主动学习（Active Learning）相结合的Co-EM算法、CO-EMT算法[56]，也可以看成是Co-training与EM相结合的算法。
4．直推式支持向量机[57-61]
直推式支持向量机（Transductive SVM，TSVM）使得分类器首先通过对已标注样本的学习，仅对当前的少量未知样本进行误差最小的预测，而且暂不考虑对未来所有实例预期性能的最优性，将这些样本加入到学习过程中来，以改进分类器的效果。由于成功地把未标注样本中所隐含的分布信息引入了支持向量机的学习过程中，TSVM算法比单纯使用有标注样本训练得到的分类器在性能上有了显著提高。
TSVM算法的一个主要缺陷在于：算法执行之前必须人为指定待训练的未标注样本中的正类样本数N，而在一般情况下N值是很难准确地估计的。
5．基于图形的方法
基于图形的半监督分类方法的典型代表是Blum和Chawla提出的[62,63]Mincut方法，该方法定义了一种图形，图中的节点表示样本集中的已标注样本和未标注样本，两点之间的边的权重反映了两个样本点之间的相似度。在两类问题中，Mincut方法的目标是寻找将两类样本[64]点分开的最小割集。[65]
Lawrence提出的高斯随机模型（Gaussian Process Model）是另外一种比较受关注的半监督学习方法，为核函数的学习提供了一种既具有理论基础又可用于实践的概率模型，在模型的选择、学习和分类方面提供了一个完整的理论框架。Chu结合成对的类之间的联系，[66,67]改进了高斯随机模型 。
关于半监督学习的其他算法可参见文献[39]（Seeger, 2001）、文献[68] （Chapelle, 2006）和文献[69]（Zhu Xiaojin，2006）。Xiao Li [70-75]Li和Bing Liu等在半监督学习方面也做了很多工作。1.2.2 集成学习
基于集成学习的分类方法在文献中有许多称谓，如组合分类（Combining Classifiers）、集成分类（Ensembling Learning，Classifier Ensembles）、多分类系统（Multiple Classifiers Systems）等。集成分类器是分类器的集合，这些分类器的单独决策被以某种方式组合起来（通过加权或无权重投票）以给新样本分类，研究发现集成分类器通常比组成它们的单个分类器要精确得多，前提是用错误率小于0.5的单个分类器，而这些单个分类器的错误之间至少应是某种[76-80]程度上无关的。如图1.3所示，集成分类器将T个学习得到的分类*器C, C, …, C组合起来，目的是创建一个改进的分类器C。12T
集成分类器的模型一般分为两类：一是使用不同类型的单分类器[4][80]的集成分类器，称分类委员会（Classifier Committees）；二是使用相同类型的单分类器的集成分类器，典型代表是Breiman的[35][76][34][37-38]Bagging和Freund及Schapire的Boosting。图1.3 集成分类
1．分类委员会
分类委员会（Classifier Committees）所基于的假设是对一个需要专家进行判断的任务，k个专家个人判断的有效组合优于个人的判[4]断。在文本分类中，选择k个不同的分类器Φ,Φ,…,Φ，对同一个12k文本分类，将分类结果进行适当的组合得到最终的分类结果。一个分类委员会的特性就由两方面决定，一是k个分类器的选择，二是集成规则的选择。
有关k个分类器的选择，从机器学习的理论可以知道，为了保证结果的有效性，组成分类委员会的分类器要尽可能地互相独立，[80]Tumer 和Ghosh在他们的文献中有详细介绍。人们研究最多的是有关组合规则的选择，通常有如下几种。
① 多票表决（Majority Voting ，MV）：是最简单组合规则，对于二值分类器，得到超过(k+1)/2个投票的分类结果被选为最终结果（k必须是奇数）。
② 线性加权组合（Weighted Linear Combination，WLC）：对k个分类器的分类结果进行加权求和得到最终的分类结果。权重反映的是分类器Φ的分类有效性。j
③ 动态分类器选择（Dynamic Classifier Selection，DCS）：考察与文本x最相近的校验文本集中的分类器的性能，效果最好的分类器i作为分类委员会选择。
④ 自适应分类器组合（Adaptive Classifier Combination，ACC）：是介于WLC与DCS之间的一种策略。对分类委员会中的所有分类器的分类判断求和，但是分类器的权重与文本x最相近的校验文i[25]本集中的分类的效果有关。
Li和Jain使用朴素贝叶斯分类器、近邻分类器、决策树做单分类器，基于MV、DCS和ACC三种组合规则实验比较之后，认为ACC规[25]则是最好的。由于这种评价是在小样本空间上做出的，还不能说是[4]权威性的结论。另外，分类委员会的分类结果并不总是比单分类器的分类效果好，而且它的计算代价高昂，是单个分类器的总和再加上组合规则的计算代价。这些都是需要改进的地方。
2．Bagging方法
Bagging方法（Bootstrap Aggregation）是由Breiman于1996年提出的，其基本思想是，将产生样本的重复Bootstrap实例作为训练集，每一回运行Bagging都给学习算法提供有替代的、随机从大小为m的原始训练集抽取出m个训练样本的集合。这种训练集被称为原始训练集合的Bootstrap复制，这种技术也叫做Bootstrap综合，即[35]Bagging。
Bagging方法是基于对训练集进行处理的集成方法中最简单、最直观的一种。使用Bagging算法的时候，理论上每个基本分类器的训练集中有63.2%的重复样例。Breiman在文献[35]中同时指出，要使得Bagging有效，基本分类器的学习算法必须是不稳定的，所谓不稳[35]定，是指训练样本发生小的变动会明显影响分类结果，也就是说对训练数据比较敏感。基本分类器的学习算法对训练数据越敏感，Bagging的效果越好，因此Bagging对于决策树和人工神经网络这样的学习算法是相当有效的。另外，由于Bagging算法本身的特点，使得Bagging算法非常适合用来并行训练多个基本分类器，这也是Bagging的优势，适用于大规模问题的研究。
3．Boosting方法
Boosting（增强）方法的思想最早来源于1984年Valiant的PAC-[84]Learning Model。学习算法根据准确度可分为“弱”学习器和“强”学习器。“弱”学习算法准确率不高，仅比随机猜测略好；“强”学习算法是准确率很高的学习算法。Valiant提出了下面的问题：一个性能仅比随机猜稍好的“弱”学习器是否能被“提升”为一个“强”学习算法？1989年Schapire提出了第一个可证明的多项式时间Boosting算[34]法，对这个问题给出了肯定的回答。
Boosting 算法的基本流程如下：
① 原始训练集输入，给每个样本赋予初始权重；
② 将训练集输入已知的弱分类器，弱分类器对每个样本给出假设；
③ 更新训练集中各样本的权重；
④ 对此次的弱分类器给出权重；
⑤ 转到步骤②，直到循环到达一定次数或某度量标准符合要求；
⑥ 将弱分类器按其相应的权重加权组合形成强分类器。
Boosting方法的核心思想如下。（1）样本的权重
Boosting算法也通过操纵训练样本来产生多假设，每个训练样本赋予一个权重。
在没有先验知识的情况下，初始的分布应为等概分布，也就是训练集如果有N个样本，每个样本的分布概率为1/N。
在每次的迭代中，按照一定的标准增加被分类错误的样本的权重，减少分正确样本的权重，使得下一次迭代的弱分类器能够集中力量对这些错误样本进行判断。（2）弱分类器的权重
每个弱分类器也对应一个权重，分类精确度高的弱分类器会有大的投票权重。
Boosting算法主要包括两个系列：Boost-by-majority和AdaBoost。在每一回迭代中Boost-by-majority通过重取样生成不同的训练集，与Bagging类似，只不过重取样的具体方法不同。而AdaBoost在每个样本上调整这种分布。AdaBoost根据弱分类器在训练样本上的错误率来调整训练样本上的概率分布，被误分的样本将获得更大的权重，使得在下一次迭代中弱分类器更加关注这样的样本。最终的分类器通过单个弱分类器的加权投票建立起来。每个弱分类器按照其在训练集上的精度而加权。
4．Bagging与Boosting的比较
Bagging的训练集随机选择，每一次迭代的训练集相互独立；而Boosting的每一次迭代的训练集并不独立，它的选择与前一轮的学习结果有关。在生成弱假设时，Bagging没有权重，可以并行生成；而Boosting有权重，只能顺序生成。因此Bagging比Boosting更易于修改为并行和分布处理的版本，这比较适用于大规模的数据挖掘。[75]
J. R. Quinlan在“Bagging，Boosting，and C4.5”一书中指出，Bagging 和Boosting都可以有效地提高分类的准确性。在大多数数据集中，Boosting的准确性比Bagging高。在有些数据集中，Boosting会引起退化。
Bagging和Boosting的学习过程都是运行多次，每次都在训练样例的子集上学习，最后综合各次迭代生成的基学习器以形成最终决策。虽然Bagging 与Boosting算法因为要经过多次迭代而造成效率不够高，但是在大多数应用中，准确率比运算速度更为重要，因为计算机的性价比提高很快。Bagging 和Boosting都可以有效地提高分类的准确性。
Bagging和Boosting在不稳定的学习算法上工作得尤其好，如决策树、神经网络，规则学习算法都是不稳定的。但是线性回归、K近邻法、Naïve Bayesian算法和线性阈值算法通常是很稳定的，Bagging和Boosting在提升这类算法时，效果就比较差。如何利用Bagging和Boosting提升Naïve Bayesian、K近邻等算法的分类性能，也是比较值得探讨的问题。
半监督学习（Semi-supervised Learning）和集成学习（Ensemble Learning）作为机器学习（Machine Learning）的两大主流，在各自的领域已经取得了不少研究成果，但是也存在一些问题。本书重点对二者的代表方法Co-training算法和AdaBoost算法进行深入的研究，在理解前人研究的基础上，针对存在的问题提出几种改进方案。1.3 本书内容组织
本章介绍了研究背景、文本分类及其面临的问题，阐述了基于半监督学习和集成学习的文本分类方法的研究意义和国内外研究现状。
第2章对文本分类的关键技术进行概述，主要包括文本分类预处理、文本的表示、特征选择、文本分类方法、实验数据集及分类模型的评估方法。
第3章分析了特征选择存在的问题，采用信息论中的评估函数量化特征的重要性，调整特征的权值，提出TEF-WA权值调整技术；分析比较了文档频率、信息增益（Information Gain，IG）、期望交叉熵2（Expected cross Entropy）﹑互信息（Mutual Information，MI）、χ统计量（CHI）、文本证据权（Weight of Evidence for Text，WET）和几率比（Odds Ratio）等多种评估函数及实验结果。
第4章分析了半监督学习中的代表方法Co-training算法，它要求两个特征视图满足一致性和独立性的理论假设，但是直接判断两个视图是否满足独立性有一定的难度。本章提出了通过评估两个基分类器之间的差异性，间接评估二者独立性的方法。在此基础上提出了两种改进算法：TV-SC和TV-DC算法。
第5章针对Co-training方法的独立性假设问题，提出了利用互信息（MI）或CHI统计量评估特征之间的相互独立性的方法，构造了一种特征独立模型（MID-Model）。基于该模型提出了特征子集划分方法——PMID算法，以便把不存在自然划分的一个特征集合划分成两个独立性较强的子集，进而提出了改进的半监督分类算法——SC-PMID算法，并且对由PMID算法划分得到的两个特征子集之间的独立性进行了理论论证。
第6章分析了集成学习算法AdaBoost算法不能有效提升Naïve Bayesian分类器性能的原因，提出了一种基于投票信息熵的样本权重维护新策略，即样本权重的调整不仅考虑是否被当前基分类器分错，还要考虑该样本在前几轮基分类器上的投票分歧，而且在错误率相同的情况下，对基分类器间的差异性贡献大的基分类器将会获得更大的置信度。在此基础上提出了对AdaBoost的改进算法——BoostVE算法，并对BoostVE算法的最小训练错误上界进行了论证分析。理论分析和在20-newsgroups标准数据集上的对比实验结果表明BoostVE算法优于AdaBoost算法，能够有效提高Naïve Bayesian文本分类器的泛化能力。
第7章结合半监督学习对集成学习的Boosting方法进行了研究，提出了一种基于置信度重取样的SemiBoost-CR分类模型；提出了基于相似近邻和基于最大差距的两种置信度计算公式，按照置信度重采样，选取一定比例置信度较高和置信度较低的未标注样本，分别以不同的策略加入到已标注的训练样本集。对比实验表明使用少量的标注样本和大量的未标注样本，SemiBoost-CR分类模型能够有效提升NB的分类效果。
第8章介绍了采用VC++ 6.0实现的中英文文本分类系统SECTCS，该系统前期设计针对的是有监督分类算法，这里对原来的SECTCS系统进行了修改和功能扩展，进一步开发实现了半监督分类方法和集成分类方法中的经典算法，以及前几章所提出的基于半监督学习与集成学习的各种改进算法，并在20-newsgroup数据集和中文新闻数据集上进行了大量的对比实验和分析，验证了所提方法的有效性。本章阐述了SECTCS系统的原有的功能与新扩展的功能、总体结构、主要的用户界面及操作，描述了分类模型的多种评估方法和实验数据集。第2章 文本分类技术概述
文本的自动分类技术（Automatic Text Categorization，ATC）是文本挖掘中最重要的研究领域之一。对文本进行准确、高效的分类是许多数据管理任务的重要组成部分。对文本、电子邮件的内容实时辨识和过滤并据此将其放置到相应的文件夹下，进行类别标识以便后续进行与类别相关的处理。结构化的搜索和浏览、提供个性化的服务等方面，均在一定程度上依赖于准确的文本分类技术。2.1 文本分类预处理
文本分类预处理是文本分类的第一个步骤，也是比较重要的一个步骤。预处理过程对分类效果的影响至关重要，数据准备是否做好将直接影响文本挖掘的效率和准确度及最终模式的有效性。文本的预处理过程可能占据整个系统80%的工作量。
与传统的结构化数据相比，文本分类处理的是大量的、非结构化的文本数据，这些数据一般是长期积累的结果，且没有统一的结构。因此不仅需要对这些文本数据进行数据挖掘中相应的标准化预处理，如数据的选择（选择相关的数据内容）、净化（消除噪声、冗余数据）、推测（推算缺失数据）、数据缩减（减少数据量），而且文本使用自然语言描述，计算机难以直接处理，所以还需要进行文本数据的信息预处理。
Internet 上的大部分网页是HTML文档或XML文档，文本的预处理首先要做的是，利用网页信息抽取模块将网页的内容，去掉与分类无关的标记，转换成统一格式的TXT文本以备后续处理。
信息预处理的主要目的是抽取代表文本特征的元数据（特征项），对元数据进行标记、语言学分析、词性标注、短语边界辨认等。一般“词”能表达完整的语义对象，所以通常选用词作为文本特征的元数据。中文文本的预处理比英文文本的预处理复杂，因为中文的基元是字而不是词，字的信息量比较低，句子中各词语间没有固有的分隔符（如空格），因此对中文文本还需要进行词条切分处理。汉语语义及结构上的复杂性和多样性给中文自动分词带来了极大困难，这也成为中文文本信息处理中的技术难点之一。在中文信息处理领域，对中文自动分词的研究工作已经做了很多，下面重点介绍汉语分词的方法。
目前，汉语分词主要有两大类方法：基于词典与规则的方法和基于统计的方法。基于词典与规则的方法应用词典匹配、汉语词法或其他汉语语言知识进行分词，如最大匹配法（Maximum Matching）、最小分词方法等。这类方法简单、分词效率较高，但对词典的完备性、规则的一致性等要求比较高。基于统计的分词方法则将汉语基于字和词的统计信息，如相邻字间互信息、词频及相应的贡献信息等应用于分词，由于这些信息是通过训练集动态获得的，因而具有较好的鲁棒性能，但是完备性相对比较差。
在这两大类方法的基础上又可将分词的基本方法归纳为如下几种。
① 词典匹配法：如最大匹配法、逆向匹配法、增字或减字匹配法、双向扫描法、二次扫描法、逐词遍历法、部件词典法。
② 设立标志法：如切分标志法、统计标引法、多层次列举法。
③ 词频统计法：如高频优先法、基于期望法、最少分词词频法。
④ 联想词群法：如联想回溯AB法、词链法、多遍扫描联想法、联想树分析法、无词库法。
⑤ 语义语用法：如邻接约束法、扩充转移网络法、综合匹配法、后缀分词法。
⑥ 知识与规则法：如切词规则法、切分与语义校正法、规则描述切词法、生成-测试法、语境相关法、短语结构法、词语结构类比法。
⑦ 人工智能法：如专家系统法、神经网络方法等。
a. 专家系统分词法：将自动分词过程看成知识推理过程，力求从结构与功能上分离分词过程和实现分词所依赖的汉语词法知识、句法知识及部分语义知识。把知识的表示、知识库的逻辑结构与知识库的维护放在系统设计的首位考虑。其知识库按常识性知识与启发性知识分别进行组织。对于常识性分词知识采用“语义网络”表示，对于启发性分词知识采用“产生式规则”表示。知识库是使专家系统具有“智能”的关键部件。
b. 基于神经网络的分词方法：以模拟人脑运行，分布处理和建立数值计算模型工作。它将分词知识所分散的隐式的方法存入神经网络内部，通过自学习和训练修改内部权值，以达到正确的分词结果。这种方法的关键在于知识库（权重链表）的组织和网络推理机制的建立。
实验表明，文本分类对分词的精度要求不是很高，通常采用基于词典的“最大匹配法”。这一方法简单、高效，适合用于模型系统的设计实现。总之，汉语自动分词是中文信息处理的“瓶颈”问题，它的最终解决依赖于汉语的分词结构、句法结构、语义等语言知识的深入、系统的研究；依赖于对语言与思维的本质的揭示；同时，在很大程度上还依赖于神经网络、专家系统、知识工程等人工智能技术的研究进展。2.2 文本的表示
文本的内容是人类所使用的自然语言，表达了丰富的信息，但是要把这些信息编码为一种标准形式是非常困难的。基于自然语言处理和统计数据分析的文本挖掘中的文本特征表示指的是对从文本中抽取出的元数据（特征项）进行量化，以结构化形式描述文档信息。这些特征项作为文档的中间表示形式，在信息挖掘时用以评价未知文档与用户目标的吻合程度，这一步又叫做目标表示。
常用的文本表示模型有：① 布尔逻辑模型：布尔逻辑模型通过定义一个二值变量集合来表示文档；② 向量空间模型（Vector [10]Space Model，VSM）：1969年Gerard Salton和McGill提出；③ 潜在语义索引（Latent Semantic Indexing，LSI）：也用向量表示特征项，但是每一个向量代表一个“概念”，由Deerweater和Dumais等于1990[13][14]年提出；④ 概率模型（Probabilistic Model）：使用概率构架表示特征项，由Belkin和Croft于1992年提出。
本书的文本自动分类系统采用了近年来应用较多且效果较好的VSM方法，下面重点讨论。
向量空间模型的基本思想是使用词袋法（Bag-of-Word）表示文本，这种表示法的一个关键的假设，就是文本中的词条出现的先后次序是无关紧要的。每个特征词对应特征空间的一维，将文本表示成欧[9]氏空间的一个向量，并成功应用到SMART系统中，是文本分类技术使用最多的表示方法。它的核心概念可以描述如下。
① 特征项：组成文档的字、词、句子等。x=(t,t,…,t,…t)，其12kn中t表示第k个特征项，作为一个维度。k
② 项的权重：在一个文本中，每个特征项都被赋予一个权重w，以表示特征项在该文本中的重要程度。
③ 向量空间模型（VSM）：在舍弃了各个特征项之间的顺序信息之后，一个文本就表示成向量，即特征空间的一个点。
如文本x的表示：x=(w,w,…,w,… w)，其中，w=f(t,c)， iii1i2iki|V|ikkjf(t,c)为权值函数，表示特征t决定文档x是否属于类c的重要性。V表kjkij示特征词集合，|V|表示特征词数。
④ 相似度（similarity）：对于所有文档和用户目标都可映射到此文本向量空间，从而将文档信息的匹配问题转化为向量空间中的矢量匹配问题。n维空间中点的距离用向量之间的余弦夹角来度量，即表示了文档间的相似程度。假设用户目标为u，未知文档为x，相似度i计算公式如下：其中，“⋅”表示向量点积，||x||是向量x的长度，sim(x,u)∈[0,1]。如iii果余弦相似度为0，则x与u之间的夹角为0°，除大小（长度）之外，i二者是相同的；如果余弦相似度为0，则x与u之间的夹角为90°，并i且它们不包含任何相同的特征词。因此夹角越小，余弦相似度越大，说明二者的相似度越高。
权重通常是特征项频率的函数，用TF(t)表示特征t出现的频率，kk权重函数有多种。文本向量由0和1组成。[9]
比较著名的权值函数是由Salton在1988年提出的TF-IDF公式[23]，它是根据词条的重要性正比于词条的文档内频数，反比于训练文档中出现该词条的文档频数的原理构造的。N为训练文本总数，N为k训练文本集中出现词条t的文本数。k
归一化后处理后为：。归一化的目的是使不同的文本具有相同的长度。
文本经过分词程序分词后，首先使用停用词表去掉对分类没有贡献的词，还可采取特征词相关性分析、聚类、同义词和近义词归并等策略，最终表示成上面描述的文本向量。2.3 特征选择
特征选择的目的有三个：
① 为了提高程序效率，提高运行速度。
② 数万维的特征对文本分类的意义是不同的，一些通用的、各个类别都普遍存在的特征对分类的贡献小，在某个特定的类中出现的比重大而在其他类中出现的比重小的特征对文本的贡献大。
③ 防止过拟合（Overfiting）。
一个有效的特征集合直观上说必须具备以下两个特点。
① 完全性：确实体现目标文档的内容。
② 区分性：能将目标文档同其他文档区分开来。2.3.1 初始特征选择
在文本的向量空间模型中，向量的维数常常是数十万维，存在着大量的对分类无用的特征，也称无关特征，也就是各个类别中均可以出现的特征，它不代表类别的特点。举例来讲，“的”、“the”、“我们”、“所以”在所有的文档中都有很高的出现频率，对分类不起作用。而稀有词在全部的训练文档中的出现次数都很少，它对文档也不具代表性。这两种词都应该删除，否则会影响分类。另外，根据ZIP法则，频率低的词在所有单词中占的比例是很高的。例如，只出现一次的单词在所有的单词中的比例占大约50%，因此合理地删除大量的低频词，可以降低特征空间的维数。通常，将“的”、“the”、“我们”、“所以”等常用词放在一个停用词表里，然后设置一个最低词频阈值，文本中属于停用词表中的单词和词频低于最低词频阈值的单词全部删除。为了减少冗余度、提高分类效果，还可以采取特征词相关性分析、聚类、同义词和近义词归并等策略，如“计算机”、“电脑”、“computer”应该作为一个词条处理。2.3.2 特征选择算法
用向量空间法表示文档时，即使经过删除停用词表中的停用词及应用ZIP法则删除低频词，仍会有数万特征留下。最后一般只选择一定数量的最佳特征来作为分类依据。所以进一步对特征进行精选就显得异常重要。
1．机器学习中的特征选择算法
在统计学、模式识别、机器学习中都有以不同的搜索策略和评估函数进行特征选择的方法，搜索策略一般有以下几种。（1）前向选择：将初始特征设为空集，用贪婪算法逐步增加特征。（2）后向消除：将初始特征设为包括所有特征的全集，用贪婪算法逐步删除特征。（3）前向逐步选择：将初始特征设为空集，用贪婪算法逐步增加或删除特征。（4）后向逐步消除：将初始特征设为包括所有特征的全集，用贪婪算法逐步增加或删除特征。（5）随机应变：将初始特征设为随机选择的特征集，用给定的重复次数增加或删除特征。[12]
机器学习中的特征选择方法可分为Filter和Wrapper两种模型。在Filter模型中，特征选择算法是学习算法的预处理过程，与学习算法独立，两个著名的算法是Relief和Fovcus算法。在Wrapper模型中特征选择的算法和学习算法是交织在一起的，这种模型的代价相当高昂，即使处理几百个特征也很困难。
2．基于评估函数的特征选择
大多数机器学习的特征选择算法不适用于文本分类，因为文本分类中的特征的维数过于庞大，对于一个n维的向量，其各维的特征组合会有2n种，即使采用一定的优化技术，这在计算复杂度上也是不可承受的。于是常常使用特征独立性的假设来简化特征选择，以达成计算时间和计算质量的折中。因为有了特征独立性的假设，文本挖掘中选择特征子集的方法和机器学习比起来是简单的。
特征子集提取的一般步骤是：通过构造一个特征评估函数，对特征集中的每个特征进行评估，每个特征获得一个评估分数，然后对所有的特征按照评估分大小进行排序，选取预定数目的最佳特征作为特征子集。评估函数一般使用逆文本频率（TF-IDF）、信息增益（Information Gain）、期望交叉熵（Expected Cross Entropy）。已经[12][15-18]有很多研究者在特征选择方面进行了大量工作，其中斯坦福大学的Mechran Sahami和美国卡耐基梅隆大学的Yang Yiming教授的文[12][16]章较具代表性和总结性。本书将在第3章讨论基于评估函数的特征权重调整（Term Evaluate Function-Weight Adjustment，TEF-WA）技术。
3．潜在语义索引
潜在语义索引（Latent Semantic Indexing，LSI）的基本观点是：把高维的向量空间模型（VSM）中表示的文档映射到低维的潜在的语义空间（LSS）中。Deerwester等人利用线性代数的知识，通过矩阵的奇异值分解（Singular Value Decomposition，SVD）来进行[13]信息滤波和潜在语义索引。
奇异矩阵分解（SVD）的相关知识如下。
假设A表示训练文档集的特征向量矩阵，m表示文档中特征的(m×n)个数，n表示文档的个数。A的奇异矩阵可由下面的式子得到：TT
其中，U和V是正交矩阵（UU=VV=1），∑是A的奇(m×K)(K×n)(R×R)异值对角矩阵。R≤min(m,n)，从∑中选取K个最大的在奇异值，(R×R)其余的设为0，构成∑，此时有：(K×K)
其中，U和U是删除了U、V中相应的行和列构成的新矩K(m×K)K(K×n)阵。
A从某种意义上说挖掘出了A的潜在的语义模式，在一定程度上K克服了一词多用和多词同意的问题，同时滤掉了词的用法和多变性产
试读结束[说明：试读内容隐藏了图片]