第一章 绪 论
1.1研究背景
当今的时代，是一个信息技术飞速发展的时代。随着信息技术的飞速发展，科学知识也在短时间内发生了急剧的、爆炸性的增长。
据1998年的资料显示[1]，70年代以来，全世界每年出版图书50万种，每一分钟就有一种新书出版。80年代每年全世界发表的科学论文大约500万篇，平均每天发表包含新知识的论文为1.3万-1.4万篇；登记的发明创造专利每年超过30万件，平均每天有800-900件专利问世。近二十年来，每年形成的文献资料的页数，美国约1,750亿页。另据联合国教科文组织所隶属的“世界科学技术情报系统”曾做的统计显示，科学知识每年的增长率，60年代以来已从9.5％增长到10.6％，到80年代每年增长率达12.5％。据说，一位化学家每周阅读40小时，光是浏览世界上一年内发表的有关化学方面的论文和著作就要读48年。而2005年的资料显示[2]，进入20世纪后全世界图书品种平均20年增加一倍，册数增加两倍。期刊出版物，平均10年增加一倍。科技文献年均增长率估计为13％，其中某些学科的文献量每10年左右翻一番，尖端科技文献的增长则更快，约2-3年翻一番。
同时，伴随着Internet 的迅猛发展，网站和网页数也在迅速增长，大约每年翻一番。据估计，目前全世界网页数已高达2000亿，而Google 宣称其已索引250亿网页。在我国，中国互联网络信息中心从2001年起每年都对中文网页总数作统计调查，统计结果显示，中文网页总数已由2001年4月30日的159,460,056个发展到2005年12月31日的24亿个，增长之快可见一斑[3,4]。
从这些统计数字可以看出，我们被淹没在一个多么浩大的信息海洋里！然而信息的极大丰富并没有提高人们对知识的吸收能力，面对如此浩瀚的信息，人们越来越感觉无法快速找到需要的知识。这就是所谓的“信息是丰富的，知识是贫乏的”。
如何在这样一个巨大的信息海洋中更加有效的发现和使用信息以及如何利用这个信息宝库为人们提供更高质量和智能化的信息服务，一直是当前信息科学和技术领域面临的一大挑战。尽管用户对图像、音频和视频等信息资源的需求也
在急剧增加，但文本仍然是最主要的非结构化和半结构化的信息资源。针对目前的出版物和网络信息大部分都以文本形式存在的状况，自动文本分类技术作为处理和组织大量文本数据的关键技术，受到了广泛的关注。
1.2文本分类的定义
1.2.1文本分类的定义
文本分类是指依据文本语义内容将未知类别的文本归类到已知类别体系中的过程。文本分类有多个英文名称，如Text Categorization[5]、Text Classification[6]、Document Categorization[7]、Document Classification[8]以及Topic Spotting[9]等，现在比较常用的为Text Categorization (TC)。文本分类的形式化定义如下，假设有一个文本集合D = {d 1,…,d |D |}和一个预先定义的类别集合C = {c 1,…,c |C |}，二者之间的真实关系可由以下函数表示[5]：
Φ:D ⨯C →{T , F }
⎧⎪T , if d i ∈c j ⎫⎪ (1-1) (d i , c j ) Φ(d i , c j ) =⎨⎬F , if d ∉c ⎪⎪i j ⎩⎭
于是，自动文本分类问题可以转化为找到函数Φ的近似表示Φ：
Φ:D ⨯C →{T , F }
⎧ ⎪T , if d i ∈c j ⎫⎪ (1-2) (d i , c j ) Φ(d i , c j ) =⎨⎬F , if d ∉c ⎪i j ⎪⎩⎭
使得Φ尽量逼近未知的真实函数Φ。此处的函数Φ称为文本分类器，力求真实反映文档和类别的关系，以便尽可能对未知类别的文本进行正确分类。
文本分类根据分类算法的不同，可以分为两类分类算法和多类分类算法。所谓两类分类算法是指算法本质上只能进行两类分类，即只能判别文档属于两类中的某一类，如支持向量机算法；而多类分类算法是指算法可以同时对多个类别进行操作，即同时判别文档属于多类中的某一类或某几类，如KNN 算法。两类分类算法应用于多类分类问题时，通常需要将一个多类分类问题转化为若干个两类分类问题来解决。具体转化方法将在本文第二章详细论述。
另外，文本分类根据文档所属类别是否单一还可以分为单标号分类(Single-label Text Categorization)问题和多标号分类(Multilabel Text Categorization)
问题。所谓单标号分类指文档的类别体系没有重合，一篇文档属于且只属于一个类别，而多标号分类是指文档的类别体系有重合，一篇文档可以属于多个不同的类别。
1.2.2自动文本分类过程
现代自动文本分类技术涉及到人工智能、机器学习、模式识别和统计理论等多个学科，自动文本分类的过程实际上也是机器学习和模式识别的过程。图1-1为基本的分类过程。
图1-1自动文本分类模型
如其他机器学习问题一样，文本分类也包括训练和测试两个模块。训练模块由预处理、文本表示、特征选择(Feature Selection) 、分类器(Classifier)和性能评价五个部分组成：
1. 预处理
负责对训练集中的文本进行去除停用词、词干化(Stemming)、分词、统计等操作，并对文本进行去噪处理。此处对中英文分别采取不同的处理，英文使用空格进行分词[1,10]，而中文则需要根据语义进行分词[11-15]或采用N-gram 法进行分词[16,17]。
2. 文本表示
把文本表示成分类算法可以识别的形式。最常用的统计模型是由Salton 等人提出的向量空间模型[18]，在此模型中，文档d j 被表示成向量的形式，
w j =，T 表示训练集中出现过的特征集合。
3. 特征降维
在文本表示阶段使用的特征集合的数目通常非常巨大，并常含有大量对分类没有贡献甚至具有相反作用的噪声特征。使用如此巨大的特征量会大大影响分类速度，因而需要通过特征降维减少特征数目，以提高训练和分类的速度与精度。特征选择后需要根据新的特征子集对文本重新进行表示。
4. 分类器
使用各种机器学习和模式识别算法对训练集进行学习，确定算法的各参数值，生成分类器。
5. 性能评价
评价分类器对训练集的分类结果，如果性能达不到要求，返回特征选择阶段重新选择特征。
分类模块由预处理、文本表示和分类器三个部分组成：
1. 预处理
功能作用和训练模块中的预处理相同。
2. 文本表示
与训练模块的第一个文本表示有所不同，此处的文本表示使用的特征空间为经过特征选择后的特征空间。
3. 分类器
使用训练完成的分类器对文本分类，输出最终分类结果。
至此，完成了整个文本分类过程。除了预处理部分与语种密切相关外，其余部分均独立于语种。
文本分类是一个应用性很强的技术，分类器的实现需要建立在一个高质量的训练集基础上，不同的应用领域有截然不同的训练集。为了评测文本分类技术的优劣，人们建立了一些标准语料库，常用的英文语料库有Reuters [19]、20_newsgroups[20]、OHSUMED [21]等。目前还没有标准的中文语料库，较多使用的有复旦大学语料库[22]、北京大学天网语料库[23]等。为了避免产生过分适合的现象，语料库通常包含两个互不相交的训练集和测试集。所谓过分适合指的是用训练集来测试分类器，产生较好的分类性能，但是用别的文本进行分类时发生分
类性能急剧下降的情况。
1.3文本分类的发展历史
文本分类最早可以追溯到20世纪60年代[5,24,25]，在这之前主要是采用手工分类的方法。进入60年代后，Maron 发表了具有里程碑作用的论文“Automatic indexing: An experimental inquiry”，采用贝叶斯公式进行文本分类，大大推进了文本分类工作。在该文中，Maron 还假设特征间是相互独立的，这就是后来被广泛采用的“贝叶斯假设”。
在随后的二十多年，主要是采用知识工程(Knowledge Engineering, KE) 的方法进行文本分类[26]，它通过在专家知识基础上手工建立一系列分类规则来构建分类器。知识工程方法需要大量领域的专家和工程师参与，势必耗费很多人力物力，当电子文档急剧增长时将无法满足需求。这种方法最典型的应用实例为由Carnegie Group开发的CONSTRUE 系统[27]，该系统用来对路透社的新闻稿件自动分类。
直到进入20世纪90年代，随着Internet 的迅猛发展，为了能够更好地处理大量的电子文档，并且伴随着人工智能、机器学习、模式识别、统计理论等学科的发展，基于知识工程的文本分类方法渐渐退出了历史舞台，文本分类技术进入了更深入的自动分类时代。由于基于机器学习的自动文本分类系统几乎可以达到与人类专家相当的正确度，但是却不需要任何知识工程师或领域专家的干预，节约了大量的人力，并且分类效率远远高于人类专家，因此机器学习方法在文本分类领域得到了深入的研究和广泛的应用，例如贝叶斯、最近邻、神经网络、支持向量机等。
1.4文本分类的应用领域
自动文本分类是对文本信息基于内容管理的基础，文本分类技术产生的初衷就是为信息管理服务，伴随着信息技术和内容的多元化发展，文本分类也得到了越来越广泛的应用，甚至涉及到通过语音识别和文本分类合成的方式对语音进行分类[46]以及通过分析文本标签对多媒体文本分类[47]等。下面简要介绍文本分类的几种应用，这些应用之间的划分没有非常明确的界限，有时某个应用可能是另
一个应用的特例。
1.4.1文本组织与管理
以科学论文为例，本文1.1节曾经提到，80年代仅科学论文一项每天就产生
1.3万-1.4万篇，科学文献平均年增长率为13％，有些学科每10年翻一番，某些尖端学科2-3年翻一番。从这些统计数据可以得出，到目前为止，科技论文每天约产生4万-5万篇，如果进行人工分类，那么如此庞大的数据量必将使得各领域的科学家付出巨大的劳动。另外，科技论文对实时性的要求也很高，研究人员需要了解到本学科最新的研究现状，这就要求论文库能够及时动态更新。所有这些情况都使得人工组织文本越来越成为不可能，此时就需要使用自动文本分类技术。文本分类使得有序地按类别存储海量文件并及时作出更新成为可能。
另外，Internet 已经成为人们生活中必不可少的一部分，人们已经习惯了坐在电脑前了解自己感兴趣的知识。各大门户网站如新浪、雅虎、搜狐等都建有各自的层次化分类体系，对网页根据其内容进行分类，读者只需按类别层层找下去就可以浏览到各种信息。目前各网站的分类都需要人工干预，如果采用自动文本分类技术，无疑将大大改善分类效率。
文本分类在数字化图书馆[48]、专利分类[49]、新闻文章自动归档和会议文章自动分组等方面都有成功应用。
1.4.2信息检索
毫无疑问，信息检索(Information Retrieval) 工具可以根据查询词返回相关信息，有效帮助了人们查找相关知识，如Goole 、Baidu 、Yahoo 、Excite 等搜索引擎。但是，所有的搜索引擎都存在着相同的一个问题，返回结果并没有如用户期望的那样排列，并且包含了大量用户不感兴趣的网页，用户必须通过阅读这些网页滤除无用信息，这就降低了查询效率。在信息检索领域引入文本分类技术，由用户选择查询类别，或者由搜索引擎给出分类存放的搜索结果，都可以提高查询效率，方便用户使用。
另外，针对信息资源库中各个不同类别，还可以建立各类别的专用搜索引擎，直接供仅对某个专题感兴趣的人使用。
1.4.3冗余文档过滤
信息检索不仅包含了大部分用户不感兴趣的类别，还包含了大量相同或相似的网页，在搜索结果较少时更是如此。这些相同或相似的网页称为冗余文档，相同网页是指除了链接地址不同，内容完全相同的网页；相似文档是指内容只有少许不同的网页。虽然各大搜索引擎都号称对相同和相似网页进行了过滤，但在搜索结果中包含大量相同或相似网页的情况还是经常出现。利用文本分类技术对网页计算相似度，超过指定阈值的网页即可认为是冗余文档，在数据库中只保存一份。
Narayanan Shivakumar等对24,000,000个网页进行统计分析，发现有18％的网页有一个重复网页，5％的网页有10到100个重复网页，经过冗余检测后，可以把存储空间压缩22％[50]。
为了提高检测效率，计算网页相似度之前，可以先对抓取到的网页进行预分类，然后再根据网页类别仅仅在该类别进行检测，这样不仅可以大大减少检测时间和计算复杂度。
1.4.4信息过滤
信息过滤(Information Filtering) 是指根据用户对信息的需求，对产生或到来的信息流进行动态地分类，保留对用户有用的信息，屏蔽无用信息。信息过滤与信息检索如同一面硬币的两面[51]：信息检索关心的是如何从信息源中找到符合用户需求的信息，可以形容为“人找信息”，用户为主动方，称之为“拉”(pull)；信息过滤关心的是过滤系统如何把信息发送给感兴趣的用户，可以形容为“信息找人”，信息发布方为主动方，称之为“推”(push)。
信息过滤的一个典型应用如新闻推送服务，信息发布方为某个新闻社，用户为某种报纸[5,52]。在这个例子中，过滤系统应该屏蔽掉所有用户不感兴趣的文档，例如对于体育报纸，应该屏蔽所有与运动无关的文档。因此信息过滤可以看作是一个单标号分类问题，把所有到来的文本分为两个互不相交的类别：相关文档和无关文档。另外，过滤系统还可以进一步对相关文本按照各个主题进行分类，方便用户阅读。在上一个例子中，与运动有关的文本还可以进一步按照运动类别分类。同样，垃圾邮件过滤系统也可以丢弃垃圾邮件[53]，并对非垃圾邮件根据用
户兴趣进行分类。
过滤系统既可以安装在信息的发送端，此时系统基于信息内容仅发送给对该信息感兴趣的用户；也可以安装在信息的接收端，此时系统负责阻断用户不感兴趣的信息。对于前一种情况，系统需要为每个用户建立一个档案[54]，而在后一种情况下，系统只需建立一个用户档案。
文档过滤(Document Filtering) 可以追溯到上世纪60年代有选择的信息分发技术(selective dissemination of information)，当今数字信息的爆炸更加促进了这类技术的发展，如基于内容的垃圾邮件过滤、新闻组订阅等[5]。
1.4.5词义辨析
词义辨析(Word Sense Disambiguation) 是指根据多义词所处上下文环境判断该词此时含义的活动[5]。例如，英文英文单词“bank ”至少有两个不同含义，在“the Bank of England”中为“银行”，在“the bank of river Thames”中为“河岸”，在“I borrowed some money from the bank”中“bank ”的含义就需要借助词义辨析来确定。把单词所处上下文看作文本，把单词的各种不同含义看作不同类别，那么词义辨析问题就可以转化为一个文本分类问题。显然，词义辨析属于单标号分类任务。
词义辨析只是解决自然语言歧义性时常见难题中的一个例子，也是计算语言学中最重要的一个难题。还有很多机器翻译中的其他问题，比如基于上下文的拼写校对(Context-sensitive spelling correction)[57]、介词短语连接(Prepositional Phrase Attachment) [58]、词性标注(Part-of-speech Tagging)[59,60]等，也都可以通过借助文本文类技术来解决。
第二章 文本分类的性能评估
2.1引言
由于自动文本分类技术在文本处理领域具有关键性作用和广泛的应用前景，因此得到了众多学者的高度重视。随着人工智能、机器学习、模式识别和统计理论等领域技术的快速发展，涌现出了越来越多的文本分类方法。但是，这些分类方法的性能如何，以及如何客观评估和比较这些分类方法，就成为了选择分类方法时无法忽视的问题。
分类器的评估是一个非常复杂的问题，目前还没有一个可以从理论上对单个分类器进行评估或对不同分类器进行比较的方法。由于难以从理论上对分类器进行客观公正的评估，文本分类领域沿用了信息检索领域的评估办法，从仿真的实验结果来评估分类器的性能。已有很多学者使用实验的方法对分类器进行了比较，并且研究者在说明某种分类算法的性能时也是用数据来表示。
分类器的性能评估有两个重要的作用，客观比较不同分类器仅仅是其中的一个方面，另一个重要作用是在训练过程中指导分类器的生成。如图1.1中所示那样，分类器评估是训练过程中必不可少的一个模块，分类器的构建需要根据评估结果调整各参数，以使分类器性能达到最优。
如同任何一个其他领域的科学实验，文本分类的实验结果也受很多客观因素的影响，比如：实验数据集的选定、文本的表示模型、特征选择的方法、分类算法的确定、各参数的选定、评估指标的确定以及实验数据的分析与处理等。显然，不同分类器只有在诸多客观因素均一致的情形下才具有可比性。许多学者基于Reuters 、20_Newgroups、OHSUMED 等标准数据集对一些分类算法进行了比较，结果就具有较高的可信度[29,81]。另外，由于分类器对数据集的严重依赖性，依靠仿真实验得出的任何一种评估结果都只能作为一定的参考，在不同数据集上同一种分类方法可能会表现出截然不同的性能。
由此可见，文本分类的性能评估是文本分类领域的一个重要课题，针对不同的目的，评估侧重点也应有所不同。
2.2文本分类器的性能评估指标
从实验方面来看，文本分类器的性能主要表现在两个方面：效率和效果。所谓效率指的是分类器训练和分类的时间；所谓效果指的是分类器做出正确决定的能力。具体到评估指标上，效率的评估指标是时间，即分类器训练的时间及单篇文本分类的时间；而效果的评估指标并不唯一，有多种类型，下面将重点进行讨论。在目前的文本分类应用中，主要关心的是分类效果的度量，所以本文也将主要讨论分类效果的评估，本文其余部分若未特别指出，文本分类性能评估均指分类效果的评估。
文本分类有多个性能评估指标，常用的有查全率(Recall, r ) 、查准率(Precision, p ) 、正确率(Accuracy, acc ) 、错误率(Error, err ) 以及查全率与查准率的综合评价值F β、11-点平均(Eleven-point average, 11-Ave ) 和平衡点(Breakeven point, BEP ) 等。下面针对单标号分类器给出这些指标的定义及计算方法。
假设一个单标号文本分类器Φ、测试文本集合D ={d 1,..., d M }和预先定义的
类别集合C ={c 1,..., c N }，D 中每篇文档只属于一个类别，C 中各类别两两之间互
不相交。分别由专家和分类器Φ来对全部测试文本判断类别，那么可建立如下的
邻接表：
表2-1 多类分类器列联表
在表2-1中，a ij 的含义如下：
⎧a ii ，i =j a ij =⎨ (2-1) a ，i ≠j ⎩ij
其中，a ii 表示原本属于类别c i 并被分类器正确判断为c i 的文档数目，a ij 表
示原本属于类别c j 但被分类器错误判断为c i 的文档数目。
根据表2-1，各指标定义及计算方法如下： 1. 查全率(Recall, r ) 与查准率(Precision, p )
查全率定义为正确判别为该类的测试样本占该类总测试样本的比例，查准率定义为正确判别为该类的测试样本占判别为该类的测试样本的比例，那么类别c i 的查全率r i 和查准率p i 的计算公式如下[5]：
r i =
a ii
∑a
k =1N
N
ki
(2-2)
p i =
a ii
ik
(2-3)
∑a
k =1
查全率与查准率来源于信息检索领域，是最为传统、也是使用最多的两个指标。查全率和查准率从不同方面反映了分类系统的性能，查全率反映了分类的完备程度，即应该正确分类的文本中有多少被正确分类；查准率反映了分类的准确程度，即分类结果中有多少是正确的。二者通常被一起使用，作为一对指标从不同侧面共同描述分类器性能。 2. F β
把查全率和查准率分开考虑没有任何意义，例如，100篇文档中有10篇属于类别c 1，假设训练了一个类别c 1的“接受分类器”，即所有文本均判为c 1，那么对于c 1来讲，查全率达到100％，但查准率只有10％。于是，Rijsbergen 提出了把二者综合考虑的指标F β，类别c i 的F βi 定义如下[108]：
(β2+1) p i r i
F βi = (2-4)
β2p i +r i
其中，反映了p i 和r i 的相对重要程度。当β=0β∈[0, +∞) ，β是可调节参数，时，F β为查准率p i ；当β=+∞时，F β为查全率r i 。β越小，越强调p i 的作用；
β越大，越强调r i 的作用。最为常用的是F 1i 值，此时β=1，认为p i 与r i 具有同等重要程度，计算公式如下：
F 1i =
2p i r i
(2-5) p i +r i
3.11-点平均(11-point average, 11-Ave )
11-点平均也是一个常用的分类器综合评价指标[31,61]，来源于信息检索领域。11-点平均定义为调整分类器参数，使得查全率分别为0％, 10％, …, 90％, 100％时相应的查准率的算术平均值。 4. 平衡点(Breakeven point, BEP )
Break-even 点是另外一个综合评价指标[39,62]，指的是分类器查全率与查准率相等时的值，这是分类器的一种特殊情况，此时p i =r i =F βi 。有时通过实验可能得不到r i 和p i 相等的值，这时就取r i 和p i 最接近的值的平均值作为BEP i ，称为插值BEP i 。
5. 宏平均(Macro-average)与微平均(Micro-average)
前面所述几个指标都是针对单个类别的局部性能进行评估的，对于一个多类分类器来讲，关心的是整体性能。宏平均和微平均是计算全局性能的两种方法。
宏平均是指先计算各类别的性能指标，然后再求算术平均值，宏平均查全率(macroR ) 、宏平均查准率(macroP ) 及宏平均F 1(macroF 1) 的定义如下：
macroR =
∑r
i =1
N
i
N
(2-6)
macroP =
∑p
i =1
N
i
N
(2-7)
macroF 1=
∑F
i =1
N
1i
N
(2-8)
微平均是指计算各个样本的分类性能，然后求算术平均值。微平均查全率
(microR ) 、微平均查准率(microP ) 及微平均F 1(microF 1) 的定义如下：
microR =
∑a
i =1
N
ii
M
(2-9)
microP =
∑∑a
i =1j =1
i =1
N N
∑a
N
ii
(2-10)
ij
microF 1=
2⨯microP ⨯microR
(2-11)
microP +microR
从微平均各指标的定义可以看出，如果在分类器中未引入拒识策略，则有
∑∑a
i =1j =1
N N
ij
=M ，此时microR =microP =microF 1。
宏平均和微平均两种方式的结果可能相差很大，尤其是对于不均衡的测试集更是如此。宏平均是按类别求平均，微平均是按样本求平均，故宏平均的结果受小类别影响较大，微平均的结果受大类别影响较大。 6. 正确率(Accuracy, acc ) 与错误率(Error, err )
正确率与错误率也是两个衡量分类器整体性能的指标。正确率定义为分类器正确分类的样本占所有测试样本的比例，错误率定义为分类器错误分类的样本占所有测试样本的比例，计算公式如下：
acc =
N
∑a
i =1
N
ii
M
N
ij
(2-12)
∑∑a
err =
i =1j =1
j ≠i
M
=1-acc (2-13)
正确率与错误率来源于机器学习领域，由公式(2-9)可以看出，正确率与微平均查全率的值完全相等，只是物理意义不同罢了。
第三章 文本表示
3.1引言
文本是一个由众多字符构成的字符串，人类在阅读文章后，可以根据自身的理解能力产生对文章的模糊认识，并对其进行分类。但计算机并不能理解文章的内容，从根本上说，它只认识0和1，所以必须把文本转换为计算机或者说分类算法可以识别的形式。
文本表示方法的选择取决于文本中的语义单元以及把这些单元结合在一起的自然语言处理规则。对文本中语义单元的研究属于词汇语义学的范畴，对各单元组合规则的研究属于组合语义学的范畴。文本表示首先根据词汇语义学及组合语义学的相关知识对文本d j 进行分割，把文本转化为由若干个语义单元组成的空间形式(t 1, t 2,..., t k ,...) ，这就是在文本分类及信息检索领域广泛应用的向量空间模型(Vector Space Model，VSM) ，这些语义单元t k 称为特征(term或feature) 。确定文本所用特征后，再计算各特征在文本中的权重(weight)，文本d j 被表示为特征向量的形式w j (w 1j , w 2j ,..., w kj ,..., w |T |j ) ，其中权重值w kj 表示特征t k 在文本d j 中的重要程度，T 表示特征空间的特征集。
向量空间模型是由Salton 提出的[18]，最早成功应用于信息检索领域，后来在文本分类领域也得到了成功应用。Salton 的向量空间模型基于这样一个假设：文本所属类别仅与特定单词或词组在该文本中出现的频数有关，而与这些单词或词组在该文本中出现的位置或顺序无关。
针对如何尽可能准确地表示文本，众多学者进行了广泛研究，主要集中在特征空间的选取和特征权重的计算方面。虽然使用向量空间模型表示文本将丢失大量文本信息，但这种文本的形式化处理使得大量机器学习算法在文本分类领域得到成功应用，大大促进了自动文本分类的发展。
随着文本分类技术的不断进步，向量空间模型也处于不断发展变化中。我们称Salton 最初提出的向量空间模型为狭义向量空间模型，在这基础上发展起来的所有以向量形式表示文本的模型称为广义向量空间模型。事实上，目前使用的文本表示法基本上都是以向量形式表示的，各方法之间的差异主要表现在特征粒度
及权重计算方法的不同。本文其余部分若不特别指出，向量空间模型均指广义向量空间模型。
3.2向量空间模型
向量空间模型中，特征是文本表示的最小单位。划分文本的特征可以是词（包括字）、词组、n-gram 和概念等，根据特征粒度的不同，一篇文本可以有多种表示方式。下面介绍各种文本特征及特征权重计算方法。
3.2.1特征
3.2.1.1词
词是自然语言理解的最小语义单位。不同的语种获取词的方式也大不相同。对英文等拼音文字而言，各个词之间用空格进行分隔，计算机处理时可以用空格作为切分标志，来提取文本的特征。但是对于中文等亚洲文字来说，表达方式以字为最小单位，在自然理解当中又是以词作为有意义的最小单位，词与词之间没有自然分割标志，这样就需要通过分词来取得文本的词特征。
无论何种语种，都会有一些对分类没有任何贡献的代词、介词和连词等，这些词称为停用词(stop words)。中英文对停用词的处理也不同。英文通常根据分类任务构建停用词表，然后在取词特征时根据该表去除停用词，表3-1是本文实验中采用的停用词表，包含319个停用词。而中文通常通过分词时建立的词典去除停用词，即词典初始建立时就不包含停用词。
表3-1 停用词表
表3-1 （续）
另外，英文中存在各种时态、语态及名词的单复数，故英文还可对文本中各
单词进行取词根(stemming)处理，就是依据一定的语法规则剥离各个单词的后缀，得到表明单词基本含义的词根。例如，answer, answered, answers的词根都为answer, 则统一用answer 来表示。目前常用的是Porter 的取词根算法[115]。但也有研究说取词根会降低分类性能[116]，但取词根还是得到了很广泛的应用，因为该方法可以有效降低特征维数。
虽然以词作为特征的词表示法丢失了大量的文本信息，但依然能够在文本分类中取得很好的效果，因而得到了广泛使用。 3.2.1.2词组
以词组作为特征的表示法称为词组表示法，该方法与词表示法非常相似，唯一不同的是特征粒度变大了。显然，用词组作为特征可以更多地包含文本信息，但分类结果却不尽人意[10,117]。
主要原因在于词组表示法虽然提高了特征的语义质量，但却降低了特征的统计质量。和词特征相比，词组特征具有较多的特征、较多的同义或近义特征、较低的一致性以及较低的文档频率[10]。统计质量的降低只能使得特征向量更加稀疏，从而对分类性能产生影响。 3.2.1.3字符串
与词表示法和词组表示法需要依赖于语种不同，字符串(n-gram)表示法[118]是完全独立于语种的一种表示法。n-gram 表示法把文本看作一个大字符串，由若干个以n 个字符组成的字符串作为特征单位。在字符串表示法中，不再考虑文本的语义单位，文本只是一个由各种字符组成的字符串，由计算机根据字符长度n 对文本进行分割。例如，“text categorization”被14-gram 分解为包含特征“text categoriz ”、“ext categoriza”、“xt categorizat”、“t categorizati”、“categorizatio ”和“categorization ”；“华南理工大学”被2-gram 分解为包含特征“华南”、“南理”、“理工”、“工大”和“大学”。
n-gram 表示法可以避免分词的工作，因此尤其适合中文等亚洲语言。但是n-gram 的缺点也非常明显，存在数据噪声大、特征复杂、计算量大和易于过学习等问题。
3.2.1.4概念
在自然语言中，一义多词的现象非常普遍，比如“计算机”“电脑”“微机”表示的都是一个概念。概念具有很高的抽象性，一个概念可以对应一个词，也可以对应若干个词。从自然语言理解的角度看，采用概念作为特征是最高级的表示。
采用概念作为特征有很多好处。首先，一个概念可能对应若干个不同的词，这样将大大降低特征空间的维数，提高分类速度；其次，同义词的聚类使得该概念的权重集中，避免了权重分散带来的对该特征的削弱，从而提高分类的精度。
用概念表示文本需要有一个专门的语义词典，这就需要语言专家和各领域专家的参与，无疑将耗费大量的人力和物力。所以，用概念表示文本的想法虽然非常好，但进展并不十分理想[119]。
3.2.2特征向量
特征空间中不同特征项对文档的重要程度和对分类的贡献是不同的，因此文本分类系统在对文本进行形式化处理的时候，需要对文本的每个特征项赋权，以形成特定文本的特征向量，权重越大的特征认为对文本越重要。由于各研究者对特征重要性认识的不同，涌现出了许多特征权重计算方法，下面介绍几种常用方法，这些方法都基于Zobel 和Moffat 提出的假设[64,120]：
（1）IDF(Inverted Document Frequency)假设：稀有特征的重要程度不低于常见特征；
（2）TF(Term Frequency)假设：一篇文档中出现多次的特征的重要程度不低于只出现一次的特征；
（3）规范化(Normalization)假设：同样的特征匹配数，长文档的重要程度不高于短文档。
从把文本转换为若干个特征的集合到生成文本的特征向量，通常需要经过三个步骤：生成索引向量；对索引向量赋权；规范化。 3.2.2.1文本索引
设训练集有N 篇文档，特征空间为T ={t 1, t 2,..., t |T |}，对文本d j 进行索引后得到索引向量f j =(f 1j , f 2j ,..., f |T |j ) ，其中，f kj 表示特征t k 在文本d j 中的索引值。索
引值的计算通常有以下几种方式。
布尔索引是最简单的一种索引方式，f kj 值的取0或1，取值方式如下：
⎧1, 若t k 在文本d j 中出现f kj =⎨ (3-1)
0, 若t 未在文本d 中出现k j ⎩
词频索引采用特征t k 在文本d j 中出现的次数TF kj 作为索引值：
f kj =TF kj (3-2)
对数索引也利用了特征t k 在文本d j 中出现的次数TF kj ，计算公式如下：
f kj =log(TF kj +1) (3-3)
可以看出，无论采用何种方式计算的索引向量均为非负向量。虽然索引向量真实反映了文本中各特征项出现的情况，但由于各特征对分类的贡献不同，需要在索引向量中进一步加入类别信息，以便准确分类。 3.2.2.2特征赋权
特征赋权的方式有很多种，可以分为“均权”与“非均权”两类。顾名思义，所谓“均权”，就是研究者认为特征在整个训练集中的统计信息对分类不会产生实质性的影响，所以给索引向量中的每个特征赋以相同的权重，也就是使用原索引向量，既不突出也不抑制任何特征。而“非均权”认为特征分为主要特征和次要特征，经过赋权处理可以放大主要特征的作用，缩小次要特征的作用。
目前的研究普遍认为不同特征在分类中的贡献是不同的，一般采用“非均权”对特征加权。其中最有代表性的是“IDF(Inverted Document Frequency)权”。IDF 权认为训练集中包含特征t k 的文档数目越多，则该特征对分类的贡献越小，这样的特征需要受到抑制；相反，训练集中包含特征t k 的文档数目越少，则该特征对分类的贡献越大，这样的特征需要被放大。设特征加权向量为g =(g 1, g 2,..., g |T |) ，训练集中出现过特征t k 的文档数为DF k ，那么特征t k 的加权值g k 由下式计算：
g k =N
) (3-4) DF k
至此，文档d j 由加权索引向量h j =(h 1j , h 2j ,..., h |T |j ) 表示，h j 等于索引向量f j
与特征加权向量g 的内积，由公式(3-5)计算。
h j =f j ∙g =(f 1j ⋅g 1, f 2j ⋅g 2,..., f |T |j ⋅g |T |) (3-5)
3.2.2.3规范化
为了消除文档长度不同对加权索引向量h 的影响，需要对h 进行规范化处理，使得各特征权重落在区间[0,1]内，最终生成文本d j 的特征向量
w j =(w 1j , w 2j ,... w , |T |j ) 。特征t k 的权重w kj 的计算公式如下：
w kj =
h kj
∑h
i =1
|T |
(3-6)
2ij
3.2.2.4相似度计算
文本表示为向量后，文本之间的距离或相似度可以通过空间中这两个向量的几何关系来度量。设有两个特征向量x =(x 1, x 2,..., x |T |) 和y =(y 1, y 2,..., y |T |) 。
如果特征向量是布尔向量，那么相似度函数通常采用汉明距离，定义如下：
D (x, y ) =|T |-∑(x i ⊕y i ) (3-7)
i =1|T |
如果特征向量非布尔向量，则相似度函数通常采用夹角余弦函数，定义如下：
sim (x , y ) =
∑x ⋅y
i i =1
|T |
i
∑x
i =1
|T |
2
i
⋅
∑y
i =1
|T |
(3-8)
2i
3.3经典特征权重
在文本分类领域，通常使用Salton 等人提出的TFIDF(Term Frequency and Inverted Document Frequency)公式计算特征项权重，特征t k 在文档d j 中的TFIDF 计算公式如(3-9)所示[5]：
tfidf (t k , d j ) =TF kj ⋅log(
N
) (3-9) DF k
其中，TF kj 表示特征t k 在文档d j 中出现的次数，DF k 表示在整个训练集中包含特征t k 的文档数，N 表示整个训练集中包含的文档数。该公式的直观解释为：特征t k 在文档中出现的次数越高，在整个训练集中包含该特征项的文档数目越少，则该特征权重越大；反之，特征t k 在文档中出现的次数越少，在整个训练集
中包含该特征项的文档数目越多，则该特征权重越小。
对tfidf (t k , d j ) 的规范化处理如下式所示：
w kj =tfidf (t k , d j )
∑2(tfidf (t , d )) i j i =1T (3-10)
其中，|T |表示特征向量的维数。
第四章 文本分类算法
4.1引言
文本分类算法作为自动文本分类技术的核心，一直处于重点研究与不断发展当中。多年来的研究积累了很多经典的分类算法，如Naive Bayes[32,33]、k 近邻[30]、决策树[34]等，也涌现出了不少新算法和改进的分类算法[35-45]。这些研究基本都致力于改进训练和分类的速度和精度。
目前文本分类的算法有很多种，包括k 近邻法、朴素贝叶斯算法、决策树算法、决策规则算法、回归模型、在线算法、Rocchio 算法、神经网络算法、支持向量机算法、最小二乘拟合与分类器组方法等。文本分类算法基本来源于机器学习与信息论领域，总体来说分类算法大致可分为两大类：基于统计的方法和基于规则的方法。朴素贝叶斯算法是经典的基于统计的算法，决策树则是基于规则的方法中的典型。
为分类系统选择分类算法时需要考虑以下几个方面的问题：第一，分类算法本质上是两类算法还是多类算法，例如支持向量机是两类分类算法，而k 近邻则可以用于多类分类，如果使用两类算法进行多类分类，则需要首先把多类分类任务分解为若干个两类分类任务后，再进行训练；第二，分类算法使用的是局部特征还是全局特征，所谓局部特征是指训练与分类时每个类别分别采用不同的特征空间，全局特征是指训练与分类时所有类别采用相同的特征空间，大部分分类算法使用全局特征与局部特征均可，但有些算法如朴素贝叶斯只能采用全局特征；第三，训练与分类的时间复杂度，一个好的分类系统应该对文本能够快速准确地分类，训练时间较长通常可以忍受，但如果分类时间过长则往往让人难以接受，例如k 近邻法在大规模文本分类问题中就存在时间灾难的问题。
虽然已经出现了一些性能不错的文本分类算法，但由于各个算法在不同应用中的表现差异较大，因此仍然有很多学者致力于更为高效的算法的研究。
4.2文本分类算法
目前的文本分类领域已经有了一些比较成熟的文本分类算法，下面我们介绍几个常用算法。
4.2.1朴素贝叶斯算法
朴素贝叶斯(Naive Bayes, NB) 算法是机器学习领域中常用的一种基于概率的分类算法，非常简单有效。NB 算法基于这样一个朴素的基本假设（称作贝叶斯假设）：假设文本中各个特征的出现是相互独立的 [125]。该算法的关键是计算文本d j 属于类别c i 的后验概率，根据贝叶斯公式(4-1)，把后验概率的计算转化为先验概率的计算，然后取后验概率最大的一个或几个类别作为文本最终类别。显然，NB 法是个多类算法，并可直接应用于多标号分类问题中。
P (d j |c i ) ⋅P (c i ) P (c i |d j ) = (4-1) P (d j )
其中，P (c i |d j ) 表示文本d j 属于类别c i 的后验概率，P (d j ) 表示文本d j 在训练集
中的概率，P (d j |c i ) 表示类别c i 中d j 的先验概率，P (c i ) 表示训练集中类别c i 的先
验概率。由于如果d j 确定，那么对所有类别P (d j ) 为常数，因此有
arg m ax P (c i |d j ) =arg m ax P (d j |c i ) ⋅P (c i ) (4-2) c i c i
接下来的问题就是如何估计P (d j |c i ) 和P (c i ) 。目前存在两种计算模型，多
变量贝努利模型(Multi-variate Bernoulli Model) 与多项式模型(Multinomial Model) 。假定训练集的特征空间为T ={t 1, t 2,..., t |T |}， t k 表示第k 个特征，|T |表示特征空间的维数，下面对这两种模型分别进行介绍。
1. 多变量贝努利模型
多变量贝努利模型中，特征向量采用二进制权重，在文档中出现过的特征权重为1，未在文档中出现过的特征权重为0。该模型是贝叶斯网络中的传统方法，已被广泛应用于文本分类中[10,102,126]。在整个计算过程中，未考虑特征在文档中
出现的次序。由于贝叶斯假设认为文档中各特征间是相互独立的，所以P (d j |c i )
可由下式计算：
|T | P (d j |c i ) =∏P (t k |c i ) (4-3)
k =1
其中，P (t k |ci ) 表示类别c i 中特征t k 出现的概率。
计算P (t k |ci ) 时，把文档看作是一组独立的贝努利实验，每个特征对应一个贝努利实验，用DF ki 表示类别c i 中包含特征项t k 的文档数，|c i |表示类别c i 中包含的所有文档数，那么P (t k |ci ) 的计算公式如下：
P (t k |c i ) =1+DF ki (4-4) |c i |
类别c i 的先验概率P (c i ) 采用最大似然估计法计算，公式如下：
P (c i ) =|c i | |D | (4-5)
其中，|D |代表训练集D 中的所有文档数。
2. 多项式模型
与多变量贝努利模型采用二进制权重不同，多项式模型考虑了文档中特征出现的频率，在该模型中，文本的特征向量权重由特征t k 在文本d j 中的出现次数TF kj 表示。和多变量贝努利模型一样，多项式模型也忽略了特征在文档中出现的
次序。在该模型中，P (d j |c i ) 和P (t k |ci ) 的计算公式如下：
TF |T | P (t k |c i ) kj
P (d j |c i ) =P (|d j |)⋅|d j |!∏ (4-6) TF kj k =1
1+∑TF kj
P (t k |c i ) =j =1|c i |
|T |+∑∑TF sj
s =1j =1|T ||c i | (4-7)
在式(4-7)中，分子表示类别c i 中特征t k 出现的次数，分母表示类别c j 中所有特征出现的总次数，为避免出现零概率，对分子和分母进行了平滑处理。
Andrew McCallum等人对多变量贝努利模型和多项式模型进行了比较，认为多项式模型在文本分类中的性能要优于多变量贝努利模型[128]，其主要原因是多项式模型考虑了文档中特征出现的频率，因此包含了更多文档信息的缘故。
另外，所有的模型都是基于贝叶斯假设的，该假设虽然大大简化了贝叶斯分类器的计算，但是也导致了其分类质量不是很理想的状况。
4.2.2 k近邻法
k 近邻法(k-Nearest Neighbor, kNN) [30,31]又称为基于实例(Example-based, Instance-bases) 的算法，其基本思想相当直观：把未知文本d 与训练集中的每篇文本进行比较，找出最邻近的k 篇文本，用这k 篇文本的类别来判断未知文本的类别。类别判断方法如下：对找到的k 篇文本，为每个类别打分，然后排序，只
有分值超过指定阈值的类别才判定为文本d 的类别。每个类别的分值score (d , c i )
的计算公式如下： score (d , c i ) = sim (d , d j ) y (d j , c i ) -b i (4-8) ∑d j ∈kNN
其中，d 为待分类文本d 的特征向量；d j 为最近邻的k 篇文本之一d j 的特征向
量；sim (d , d j ) 为d 与d j 的相似度，相似度的计算见本文3.3.4的介绍，通常使用
余弦相似度；y (d j , c i ) 为文本d j 在类别c i 中的权重，通常d j 属于c i 时取1，d j 不
属于c i 时取0；b i 为事先设定的阈值，可以在确认集(validation set)上通过训练得
到。所有使得score (d , c i ) >0的类别均判定为文本d 的类别，因而kNN 算法可以
用于多类多标号文本分类问题。
kNN 算法的一个关键问题是k 值的选择，k 值过大会包含较多错误类别的文本，k 值过小又会使得边缘文本难以被正确判断。另外，kNN 算法无须训练，但需要在分类时把待分类文本与训练集中所有文本进行比较，因此对于小规模文本分类问题，使用kNN 不失为一个有效的办法，但对于大规模文本分类问题，kNN 需要耗费大量的分类时间。该算法的分类效率非常低，但是在分类精度上，是效果最好的分类器之一，并且，性能也比较稳定[29]。
4.2.3 Rocchio法
Rocchio 法来源于信息检索系统，后来最早由Hull 在1994年应用于分类[74]，从那以后，Rocchio 方法就在文本分类中广泛应用起来。Rocchio 方法可能是文本分类领域唯一一个植根于信息检索领域而不是机器学习领域的分类器，该方法
在训练阶段为每个类别c i 建立一个代表向量c i =(w 1i , w 2i ,..., w |T |i ) ，其中|T |表示训
练集中的特征总数。在对文本d 分类时计算d 与c i 的相似度，取相似度最大的一
个或几个类别作为文本d 的类别。
类别c i 的代表向量c i 的第k 维值w ki 由公式(4-9)计算：
w ki =β∑d j ∈c i w kj
|c i |-γ∑d j ∉c i w kj
N -|c i | (4-9)
其中，β为训练样本中正例的控制参数，γ为训练样本中反例的控制参数，|c i |表示训练样本中正例的数目，N 表示训练样本的文档总数，正例指属于类别c i 的文本，反例指不属于类别c i 的文本。β和γ是两个控制参数，可以通过提高β降低γ来削弱反例的影响。
进行分类时，待分类文档d =(w 1, w 2,..., w |T |) 与类别c i 的距离度量公式为：
sim (d , c i ) =∑w w k
k =1
|T |2
k
k =1|T |ki ∑w ∑w k =1|T | (4-10) 2ki
当β＝1，γ＝0时，类别代表向量c i 成为正例的质心。
Rocchio 方法容易实现，分类速度快，尤其适合于大规模文本处理。但是，对于一个包含几个互不相交的簇的类别，例如，“运动”类包含“篮球”和“爬山”两个不相干的簇，该类别的质心则可能会落在所有簇的外面，如果使用Rocchio 法分类将导致大部分正例被误分的情况发生。
第一章 绪 论
1.1研究背景
当今的时代，是一个信息技术飞速发展的时代。随着信息技术的飞速发展，科学知识也在短时间内发生了急剧的、爆炸性的增长。
据1998年的资料显示[1]，70年代以来，全世界每年出版图书50万种，每一分钟就有一种新书出版。80年代每年全世界发表的科学论文大约500万篇，平均每天发表包含新知识的论文为1.3万-1.4万篇；登记的发明创造专利每年超过30万件，平均每天有800-900件专利问世。近二十年来，每年形成的文献资料的页数，美国约1,750亿页。另据联合国教科文组织所隶属的“世界科学技术情报系统”曾做的统计显示，科学知识每年的增长率，60年代以来已从9.5％增长到10.6％，到80年代每年增长率达12.5％。据说，一位化学家每周阅读40小时，光是浏览世界上一年内发表的有关化学方面的论文和著作就要读48年。而2005年的资料显示[2]，进入20世纪后全世界图书品种平均20年增加一倍，册数增加两倍。期刊出版物，平均10年增加一倍。科技文献年均增长率估计为13％，其中某些学科的文献量每10年左右翻一番，尖端科技文献的增长则更快，约2-3年翻一番。
同时，伴随着Internet 的迅猛发展，网站和网页数也在迅速增长，大约每年翻一番。据估计，目前全世界网页数已高达2000亿，而Google 宣称其已索引250亿网页。在我国，中国互联网络信息中心从2001年起每年都对中文网页总数作统计调查，统计结果显示，中文网页总数已由2001年4月30日的159,460,056个发展到2005年12月31日的24亿个，增长之快可见一斑[3,4]。
从这些统计数字可以看出，我们被淹没在一个多么浩大的信息海洋里！然而信息的极大丰富并没有提高人们对知识的吸收能力，面对如此浩瀚的信息，人们越来越感觉无法快速找到需要的知识。这就是所谓的“信息是丰富的，知识是贫乏的”。
如何在这样一个巨大的信息海洋中更加有效的发现和使用信息以及如何利用这个信息宝库为人们提供更高质量和智能化的信息服务，一直是当前信息科学和技术领域面临的一大挑战。尽管用户对图像、音频和视频等信息资源的需求也
在急剧增加，但文本仍然是最主要的非结构化和半结构化的信息资源。针对目前的出版物和网络信息大部分都以文本形式存在的状况，自动文本分类技术作为处理和组织大量文本数据的关键技术，受到了广泛的关注。
1.2文本分类的定义
1.2.1文本分类的定义
文本分类是指依据文本语义内容将未知类别的文本归类到已知类别体系中的过程。文本分类有多个英文名称，如Text Categorization[5]、Text Classification[6]、Document Categorization[7]、Document Classification[8]以及Topic Spotting[9]等，现在比较常用的为Text Categorization (TC)。文本分类的形式化定义如下，假设有一个文本集合D = {d 1,…,d |D |}和一个预先定义的类别集合C = {c 1,…,c |C |}，二者之间的真实关系可由以下函数表示[5]：
Φ:D ⨯C →{T , F }
⎧⎪T , if d i ∈c j ⎫⎪ (1-1) (d i , c j ) Φ(d i , c j ) =⎨⎬F , if d ∉c ⎪⎪i j ⎩⎭
于是，自动文本分类问题可以转化为找到函数Φ的近似表示Φ：
Φ:D ⨯C →{T , F }
⎧ ⎪T , if d i ∈c j ⎫⎪ (1-2) (d i , c j ) Φ(d i , c j ) =⎨⎬F , if d ∉c ⎪i j ⎪⎩⎭
使得Φ尽量逼近未知的真实函数Φ。此处的函数Φ称为文本分类器，力求真实反映文档和类别的关系，以便尽可能对未知类别的文本进行正确分类。
文本分类根据分类算法的不同，可以分为两类分类算法和多类分类算法。所谓两类分类算法是指算法本质上只能进行两类分类，即只能判别文档属于两类中的某一类，如支持向量机算法；而多类分类算法是指算法可以同时对多个类别进行操作，即同时判别文档属于多类中的某一类或某几类，如KNN 算法。两类分类算法应用于多类分类问题时，通常需要将一个多类分类问题转化为若干个两类分类问题来解决。具体转化方法将在本文第二章详细论述。
另外，文本分类根据文档所属类别是否单一还可以分为单标号分类(Single-label Text Categorization)问题和多标号分类(Multilabel Text Categorization)
问题。所谓单标号分类指文档的类别体系没有重合，一篇文档属于且只属于一个类别，而多标号分类是指文档的类别体系有重合，一篇文档可以属于多个不同的类别。
1.2.2自动文本分类过程
现代自动文本分类技术涉及到人工智能、机器学习、模式识别和统计理论等多个学科，自动文本分类的过程实际上也是机器学习和模式识别的过程。图1-1为基本的分类过程。
图1-1自动文本分类模型
如其他机器学习问题一样，文本分类也包括训练和测试两个模块。训练模块由预处理、文本表示、特征选择(Feature Selection) 、分类器(Classifier)和性能评价五个部分组成：
1. 预处理
负责对训练集中的文本进行去除停用词、词干化(Stemming)、分词、统计等操作，并对文本进行去噪处理。此处对中英文分别采取不同的处理，英文使用空格进行分词[1,10]，而中文则需要根据语义进行分词[11-15]或采用N-gram 法进行分词[16,17]。
2. 文本表示
把文本表示成分类算法可以识别的形式。最常用的统计模型是由Salton 等人提出的向量空间模型[18]，在此模型中，文档d j 被表示成向量的形式，
w j =，T 表示训练集中出现过的特征集合。
3. 特征降维
在文本表示阶段使用的特征集合的数目通常非常巨大，并常含有大量对分类没有贡献甚至具有相反作用的噪声特征。使用如此巨大的特征量会大大影响分类速度，因而需要通过特征降维减少特征数目，以提高训练和分类的速度与精度。特征选择后需要根据新的特征子集对文本重新进行表示。
4. 分类器
使用各种机器学习和模式识别算法对训练集进行学习，确定算法的各参数值，生成分类器。
5. 性能评价
评价分类器对训练集的分类结果，如果性能达不到要求，返回特征选择阶段重新选择特征。
分类模块由预处理、文本表示和分类器三个部分组成：
1. 预处理
功能作用和训练模块中的预处理相同。
2. 文本表示
与训练模块的第一个文本表示有所不同，此处的文本表示使用的特征空间为经过特征选择后的特征空间。
3. 分类器
使用训练完成的分类器对文本分类，输出最终分类结果。
至此，完成了整个文本分类过程。除了预处理部分与语种密切相关外，其余部分均独立于语种。
文本分类是一个应用性很强的技术，分类器的实现需要建立在一个高质量的训练集基础上，不同的应用领域有截然不同的训练集。为了评测文本分类技术的优劣，人们建立了一些标准语料库，常用的英文语料库有Reuters [19]、20_newsgroups[20]、OHSUMED [21]等。目前还没有标准的中文语料库，较多使用的有复旦大学语料库[22]、北京大学天网语料库[23]等。为了避免产生过分适合的现象，语料库通常包含两个互不相交的训练集和测试集。所谓过分适合指的是用训练集来测试分类器，产生较好的分类性能，但是用别的文本进行分类时发生分
类性能急剧下降的情况。
1.3文本分类的发展历史
文本分类最早可以追溯到20世纪60年代[5,24,25]，在这之前主要是采用手工分类的方法。进入60年代后，Maron 发表了具有里程碑作用的论文“Automatic indexing: An experimental inquiry”，采用贝叶斯公式进行文本分类，大大推进了文本分类工作。在该文中，Maron 还假设特征间是相互独立的，这就是后来被广泛采用的“贝叶斯假设”。
在随后的二十多年，主要是采用知识工程(Knowledge Engineering, KE) 的方法进行文本分类[26]，它通过在专家知识基础上手工建立一系列分类规则来构建分类器。知识工程方法需要大量领域的专家和工程师参与，势必耗费很多人力物力，当电子文档急剧增长时将无法满足需求。这种方法最典型的应用实例为由Carnegie Group开发的CONSTRUE 系统[27]，该系统用来对路透社的新闻稿件自动分类。
直到进入20世纪90年代，随着Internet 的迅猛发展，为了能够更好地处理大量的电子文档，并且伴随着人工智能、机器学习、模式识别、统计理论等学科的发展，基于知识工程的文本分类方法渐渐退出了历史舞台，文本分类技术进入了更深入的自动分类时代。由于基于机器学习的自动文本分类系统几乎可以达到与人类专家相当的正确度，但是却不需要任何知识工程师或领域专家的干预，节约了大量的人力，并且分类效率远远高于人类专家，因此机器学习方法在文本分类领域得到了深入的研究和广泛的应用，例如贝叶斯、最近邻、神经网络、支持向量机等。
1.4文本分类的应用领域
自动文本分类是对文本信息基于内容管理的基础，文本分类技术产生的初衷就是为信息管理服务，伴随着信息技术和内容的多元化发展，文本分类也得到了越来越广泛的应用，甚至涉及到通过语音识别和文本分类合成的方式对语音进行分类[46]以及通过分析文本标签对多媒体文本分类[47]等。下面简要介绍文本分类的几种应用，这些应用之间的划分没有非常明确的界限，有时某个应用可能是另
一个应用的特例。
1.4.1文本组织与管理
以科学论文为例，本文1.1节曾经提到，80年代仅科学论文一项每天就产生
1.3万-1.4万篇，科学文献平均年增长率为13％，有些学科每10年翻一番，某些尖端学科2-3年翻一番。从这些统计数据可以得出，到目前为止，科技论文每天约产生4万-5万篇，如果进行人工分类，那么如此庞大的数据量必将使得各领域的科学家付出巨大的劳动。另外，科技论文对实时性的要求也很高，研究人员需要了解到本学科最新的研究现状，这就要求论文库能够及时动态更新。所有这些情况都使得人工组织文本越来越成为不可能，此时就需要使用自动文本分类技术。文本分类使得有序地按类别存储海量文件并及时作出更新成为可能。
另外，Internet 已经成为人们生活中必不可少的一部分，人们已经习惯了坐在电脑前了解自己感兴趣的知识。各大门户网站如新浪、雅虎、搜狐等都建有各自的层次化分类体系，对网页根据其内容进行分类，读者只需按类别层层找下去就可以浏览到各种信息。目前各网站的分类都需要人工干预，如果采用自动文本分类技术，无疑将大大改善分类效率。
文本分类在数字化图书馆[48]、专利分类[49]、新闻文章自动归档和会议文章自动分组等方面都有成功应用。
1.4.2信息检索
毫无疑问，信息检索(Information Retrieval) 工具可以根据查询词返回相关信息，有效帮助了人们查找相关知识，如Goole 、Baidu 、Yahoo 、Excite 等搜索引擎。但是，所有的搜索引擎都存在着相同的一个问题，返回结果并没有如用户期望的那样排列，并且包含了大量用户不感兴趣的网页，用户必须通过阅读这些网页滤除无用信息，这就降低了查询效率。在信息检索领域引入文本分类技术，由用户选择查询类别，或者由搜索引擎给出分类存放的搜索结果，都可以提高查询效率，方便用户使用。
另外，针对信息资源库中各个不同类别，还可以建立各类别的专用搜索引擎，直接供仅对某个专题感兴趣的人使用。
1.4.3冗余文档过滤
信息检索不仅包含了大部分用户不感兴趣的类别，还包含了大量相同或相似的网页，在搜索结果较少时更是如此。这些相同或相似的网页称为冗余文档，相同网页是指除了链接地址不同，内容完全相同的网页；相似文档是指内容只有少许不同的网页。虽然各大搜索引擎都号称对相同和相似网页进行了过滤，但在搜索结果中包含大量相同或相似网页的情况还是经常出现。利用文本分类技术对网页计算相似度，超过指定阈值的网页即可认为是冗余文档，在数据库中只保存一份。
Narayanan Shivakumar等对24,000,000个网页进行统计分析，发现有18％的网页有一个重复网页，5％的网页有10到100个重复网页，经过冗余检测后，可以把存储空间压缩22％[50]。
为了提高检测效率，计算网页相似度之前，可以先对抓取到的网页进行预分类，然后再根据网页类别仅仅在该类别进行检测，这样不仅可以大大减少检测时间和计算复杂度。
1.4.4信息过滤
信息过滤(Information Filtering) 是指根据用户对信息的需求，对产生或到来的信息流进行动态地分类，保留对用户有用的信息，屏蔽无用信息。信息过滤与信息检索如同一面硬币的两面[51]：信息检索关心的是如何从信息源中找到符合用户需求的信息，可以形容为“人找信息”，用户为主动方，称之为“拉”(pull)；信息过滤关心的是过滤系统如何把信息发送给感兴趣的用户，可以形容为“信息找人”，信息发布方为主动方，称之为“推”(push)。
信息过滤的一个典型应用如新闻推送服务，信息发布方为某个新闻社，用户为某种报纸[5,52]。在这个例子中，过滤系统应该屏蔽掉所有用户不感兴趣的文档，例如对于体育报纸，应该屏蔽所有与运动无关的文档。因此信息过滤可以看作是一个单标号分类问题，把所有到来的文本分为两个互不相交的类别：相关文档和无关文档。另外，过滤系统还可以进一步对相关文本按照各个主题进行分类，方便用户阅读。在上一个例子中，与运动有关的文本还可以进一步按照运动类别分类。同样，垃圾邮件过滤系统也可以丢弃垃圾邮件[53]，并对非垃圾邮件根据用
户兴趣进行分类。
过滤系统既可以安装在信息的发送端，此时系统基于信息内容仅发送给对该信息感兴趣的用户；也可以安装在信息的接收端，此时系统负责阻断用户不感兴趣的信息。对于前一种情况，系统需要为每个用户建立一个档案[54]，而在后一种情况下，系统只需建立一个用户档案。
文档过滤(Document Filtering) 可以追溯到上世纪60年代有选择的信息分发技术(selective dissemination of information)，当今数字信息的爆炸更加促进了这类技术的发展，如基于内容的垃圾邮件过滤、新闻组订阅等[5]。
1.4.5词义辨析
词义辨析(Word Sense Disambiguation) 是指根据多义词所处上下文环境判断该词此时含义的活动[5]。例如，英文英文单词“bank ”至少有两个不同含义，在“the Bank of England”中为“银行”，在“the bank of river Thames”中为“河岸”，在“I borrowed some money from the bank”中“bank ”的含义就需要借助词义辨析来确定。把单词所处上下文看作文本，把单词的各种不同含义看作不同类别，那么词义辨析问题就可以转化为一个文本分类问题。显然，词义辨析属于单标号分类任务。
词义辨析只是解决自然语言歧义性时常见难题中的一个例子，也是计算语言学中最重要的一个难题。还有很多机器翻译中的其他问题，比如基于上下文的拼写校对(Context-sensitive spelling correction)[57]、介词短语连接(Prepositional Phrase Attachment) [58]、词性标注(Part-of-speech Tagging)[59,60]等，也都可以通过借助文本文类技术来解决。
第二章 文本分类的性能评估
2.1引言
由于自动文本分类技术在文本处理领域具有关键性作用和广泛的应用前景，因此得到了众多学者的高度重视。随着人工智能、机器学习、模式识别和统计理论等领域技术的快速发展，涌现出了越来越多的文本分类方法。但是，这些分类方法的性能如何，以及如何客观评估和比较这些分类方法，就成为了选择分类方法时无法忽视的问题。
分类器的评估是一个非常复杂的问题，目前还没有一个可以从理论上对单个分类器进行评估或对不同分类器进行比较的方法。由于难以从理论上对分类器进行客观公正的评估，文本分类领域沿用了信息检索领域的评估办法，从仿真的实验结果来评估分类器的性能。已有很多学者使用实验的方法对分类器进行了比较，并且研究者在说明某种分类算法的性能时也是用数据来表示。
分类器的性能评估有两个重要的作用，客观比较不同分类器仅仅是其中的一个方面，另一个重要作用是在训练过程中指导分类器的生成。如图1.1中所示那样，分类器评估是训练过程中必不可少的一个模块，分类器的构建需要根据评估结果调整各参数，以使分类器性能达到最优。
如同任何一个其他领域的科学实验，文本分类的实验结果也受很多客观因素的影响，比如：实验数据集的选定、文本的表示模型、特征选择的方法、分类算法的确定、各参数的选定、评估指标的确定以及实验数据的分析与处理等。显然，不同分类器只有在诸多客观因素均一致的情形下才具有可比性。许多学者基于Reuters 、20_Newgroups、OHSUMED 等标准数据集对一些分类算法进行了比较，结果就具有较高的可信度[29,81]。另外，由于分类器对数据集的严重依赖性，依靠仿真实验得出的任何一种评估结果都只能作为一定的参考，在不同数据集上同一种分类方法可能会表现出截然不同的性能。
由此可见，文本分类的性能评估是文本分类领域的一个重要课题，针对不同的目的，评估侧重点也应有所不同。
2.2文本分类器的性能评估指标
从实验方面来看，文本分类器的性能主要表现在两个方面：效率和效果。所谓效率指的是分类器训练和分类的时间；所谓效果指的是分类器做出正确决定的能力。具体到评估指标上，效率的评估指标是时间，即分类器训练的时间及单篇文本分类的时间；而效果的评估指标并不唯一，有多种类型，下面将重点进行讨论。在目前的文本分类应用中，主要关心的是分类效果的度量，所以本文也将主要讨论分类效果的评估，本文其余部分若未特别指出，文本分类性能评估均指分类效果的评估。
文本分类有多个性能评估指标，常用的有查全率(Recall, r ) 、查准率(Precision, p ) 、正确率(Accuracy, acc ) 、错误率(Error, err ) 以及查全率与查准率的综合评价值F β、11-点平均(Eleven-point average, 11-Ave ) 和平衡点(Breakeven point, BEP ) 等。下面针对单标号分类器给出这些指标的定义及计算方法。
假设一个单标号文本分类器Φ、测试文本集合D ={d 1,..., d M }和预先定义的
类别集合C ={c 1,..., c N }，D 中每篇文档只属于一个类别，C 中各类别两两之间互
不相交。分别由专家和分类器Φ来对全部测试文本判断类别，那么可建立如下的
邻接表：
表2-1 多类分类器列联表
在表2-1中，a ij 的含义如下：
⎧a ii ，i =j a ij =⎨ (2-1) a ，i ≠j ⎩ij
其中，a ii 表示原本属于类别c i 并被分类器正确判断为c i 的文档数目，a ij 表
示原本属于类别c j 但被分类器错误判断为c i 的文档数目。
根据表2-1，各指标定义及计算方法如下： 1. 查全率(Recall, r ) 与查准率(Precision, p )
查全率定义为正确判别为该类的测试样本占该类总测试样本的比例，查准率定义为正确判别为该类的测试样本占判别为该类的测试样本的比例，那么类别c i 的查全率r i 和查准率p i 的计算公式如下[5]：
r i =
a ii
∑a
k =1N
N
ki
(2-2)
p i =
a ii
ik
(2-3)
∑a
k =1
查全率与查准率来源于信息检索领域，是最为传统、也是使用最多的两个指标。查全率和查准率从不同方面反映了分类系统的性能，查全率反映了分类的完备程度，即应该正确分类的文本中有多少被正确分类；查准率反映了分类的准确程度，即分类结果中有多少是正确的。二者通常被一起使用，作为一对指标从不同侧面共同描述分类器性能。 2. F β
把查全率和查准率分开考虑没有任何意义，例如，100篇文档中有10篇属于类别c 1，假设训练了一个类别c 1的“接受分类器”，即所有文本均判为c 1，那么对于c 1来讲，查全率达到100％，但查准率只有10％。于是，Rijsbergen 提出了把二者综合考虑的指标F β，类别c i 的F βi 定义如下[108]：
(β2+1) p i r i
F βi = (2-4)
β2p i +r i
其中，反映了p i 和r i 的相对重要程度。当β=0β∈[0, +∞) ，β是可调节参数，时，F β为查准率p i ；当β=+∞时，F β为查全率r i 。β越小，越强调p i 的作用；
β越大，越强调r i 的作用。最为常用的是F 1i 值，此时β=1，认为p i 与r i 具有同等重要程度，计算公式如下：
F 1i =
2p i r i
(2-5) p i +r i
3.11-点平均(11-point average, 11-Ave )
11-点平均也是一个常用的分类器综合评价指标[31,61]，来源于信息检索领域。11-点平均定义为调整分类器参数，使得查全率分别为0％, 10％, …, 90％, 100％时相应的查准率的算术平均值。 4. 平衡点(Breakeven point, BEP )
Break-even 点是另外一个综合评价指标[39,62]，指的是分类器查全率与查准率相等时的值，这是分类器的一种特殊情况，此时p i =r i =F βi 。有时通过实验可能得不到r i 和p i 相等的值，这时就取r i 和p i 最接近的值的平均值作为BEP i ，称为插值BEP i 。
5. 宏平均(Macro-average)与微平均(Micro-average)
前面所述几个指标都是针对单个类别的局部性能进行评估的，对于一个多类分类器来讲，关心的是整体性能。宏平均和微平均是计算全局性能的两种方法。
宏平均是指先计算各类别的性能指标，然后再求算术平均值，宏平均查全率(macroR ) 、宏平均查准率(macroP ) 及宏平均F 1(macroF 1) 的定义如下：
macroR =
∑r
i =1
N
i
N
(2-6)
macroP =
∑p
i =1
N
i
N
(2-7)
macroF 1=
∑F
i =1
N
1i
N
(2-8)
微平均是指计算各个样本的分类性能，然后求算术平均值。微平均查全率
(microR ) 、微平均查准率(microP ) 及微平均F 1(microF 1) 的定义如下：
microR =
∑a
i =1
N
ii
M
(2-9)
microP =
∑∑a
i =1j =1
i =1
N N
∑a
N
ii
(2-10)
ij
microF 1=
2⨯microP ⨯microR
(2-11)
microP +microR
从微平均各指标的定义可以看出，如果在分类器中未引入拒识策略，则有
∑∑a
i =1j =1
N N
ij
=M ，此时microR =microP =microF 1。
宏平均和微平均两种方式的结果可能相差很大，尤其是对于不均衡的测试集更是如此。宏平均是按类别求平均，微平均是按样本求平均，故宏平均的结果受小类别影响较大，微平均的结果受大类别影响较大。 6. 正确率(Accuracy, acc ) 与错误率(Error, err )
正确率与错误率也是两个衡量分类器整体性能的指标。正确率定义为分类器正确分类的样本占所有测试样本的比例，错误率定义为分类器错误分类的样本占所有测试样本的比例，计算公式如下：
acc =
N
∑a
i =1
N
ii
M
N
ij
(2-12)
∑∑a
err =
i =1j =1
j ≠i
M
=1-acc (2-13)
正确率与错误率来源于机器学习领域，由公式(2-9)可以看出，正确率与微平均查全率的值完全相等，只是物理意义不同罢了。
第三章 文本表示
3.1引言
文本是一个由众多字符构成的字符串，人类在阅读文章后，可以根据自身的理解能力产生对文章的模糊认识，并对其进行分类。但计算机并不能理解文章的内容，从根本上说，它只认识0和1，所以必须把文本转换为计算机或者说分类算法可以识别的形式。
文本表示方法的选择取决于文本中的语义单元以及把这些单元结合在一起的自然语言处理规则。对文本中语义单元的研究属于词汇语义学的范畴，对各单元组合规则的研究属于组合语义学的范畴。文本表示首先根据词汇语义学及组合语义学的相关知识对文本d j 进行分割，把文本转化为由若干个语义单元组成的空间形式(t 1, t 2,..., t k ,...) ，这就是在文本分类及信息检索领域广泛应用的向量空间模型(Vector Space Model，VSM) ，这些语义单元t k 称为特征(term或feature) 。确定文本所用特征后，再计算各特征在文本中的权重(weight)，文本d j 被表示为特征向量的形式w j (w 1j , w 2j ,..., w kj ,..., w |T |j ) ，其中权重值w kj 表示特征t k 在文本d j 中的重要程度，T 表示特征空间的特征集。
向量空间模型是由Salton 提出的[18]，最早成功应用于信息检索领域，后来在文本分类领域也得到了成功应用。Salton 的向量空间模型基于这样一个假设：文本所属类别仅与特定单词或词组在该文本中出现的频数有关，而与这些单词或词组在该文本中出现的位置或顺序无关。
针对如何尽可能准确地表示文本，众多学者进行了广泛研究，主要集中在特征空间的选取和特征权重的计算方面。虽然使用向量空间模型表示文本将丢失大量文本信息，但这种文本的形式化处理使得大量机器学习算法在文本分类领域得到成功应用，大大促进了自动文本分类的发展。
随着文本分类技术的不断进步，向量空间模型也处于不断发展变化中。我们称Salton 最初提出的向量空间模型为狭义向量空间模型，在这基础上发展起来的所有以向量形式表示文本的模型称为广义向量空间模型。事实上，目前使用的文本表示法基本上都是以向量形式表示的，各方法之间的差异主要表现在特征粒度
及权重计算方法的不同。本文其余部分若不特别指出，向量空间模型均指广义向量空间模型。
3.2向量空间模型
向量空间模型中，特征是文本表示的最小单位。划分文本的特征可以是词（包括字）、词组、n-gram 和概念等，根据特征粒度的不同，一篇文本可以有多种表示方式。下面介绍各种文本特征及特征权重计算方法。
3.2.1特征
3.2.1.1词
词是自然语言理解的最小语义单位。不同的语种获取词的方式也大不相同。对英文等拼音文字而言，各个词之间用空格进行分隔，计算机处理时可以用空格作为切分标志，来提取文本的特征。但是对于中文等亚洲文字来说，表达方式以字为最小单位，在自然理解当中又是以词作为有意义的最小单位，词与词之间没有自然分割标志，这样就需要通过分词来取得文本的词特征。
无论何种语种，都会有一些对分类没有任何贡献的代词、介词和连词等，这些词称为停用词(stop words)。中英文对停用词的处理也不同。英文通常根据分类任务构建停用词表，然后在取词特征时根据该表去除停用词，表3-1是本文实验中采用的停用词表，包含319个停用词。而中文通常通过分词时建立的词典去除停用词，即词典初始建立时就不包含停用词。
表3-1 停用词表
表3-1 （续）
另外，英文中存在各种时态、语态及名词的单复数，故英文还可对文本中各
单词进行取词根(stemming)处理，就是依据一定的语法规则剥离各个单词的后缀，得到表明单词基本含义的词根。例如，answer, answered, answers的词根都为answer, 则统一用answer 来表示。目前常用的是Porter 的取词根算法[115]。但也有研究说取词根会降低分类性能[116]，但取词根还是得到了很广泛的应用，因为该方法可以有效降低特征维数。
虽然以词作为特征的词表示法丢失了大量的文本信息，但依然能够在文本分类中取得很好的效果，因而得到了广泛使用。 3.2.1.2词组
以词组作为特征的表示法称为词组表示法，该方法与词表示法非常相似，唯一不同的是特征粒度变大了。显然，用词组作为特征可以更多地包含文本信息，但分类结果却不尽人意[10,117]。
主要原因在于词组表示法虽然提高了特征的语义质量，但却降低了特征的统计质量。和词特征相比，词组特征具有较多的特征、较多的同义或近义特征、较低的一致性以及较低的文档频率[10]。统计质量的降低只能使得特征向量更加稀疏，从而对分类性能产生影响。 3.2.1.3字符串
与词表示法和词组表示法需要依赖于语种不同，字符串(n-gram)表示法[118]是完全独立于语种的一种表示法。n-gram 表示法把文本看作一个大字符串，由若干个以n 个字符组成的字符串作为特征单位。在字符串表示法中，不再考虑文本的语义单位，文本只是一个由各种字符组成的字符串，由计算机根据字符长度n 对文本进行分割。例如，“text categorization”被14-gram 分解为包含特征“text categoriz ”、“ext categoriza”、“xt categorizat”、“t categorizati”、“categorizatio ”和“categorization ”；“华南理工大学”被2-gram 分解为包含特征“华南”、“南理”、“理工”、“工大”和“大学”。
n-gram 表示法可以避免分词的工作，因此尤其适合中文等亚洲语言。但是n-gram 的缺点也非常明显，存在数据噪声大、特征复杂、计算量大和易于过学习等问题。
3.2.1.4概念
在自然语言中，一义多词的现象非常普遍，比如“计算机”“电脑”“微机”表示的都是一个概念。概念具有很高的抽象性，一个概念可以对应一个词，也可以对应若干个词。从自然语言理解的角度看，采用概念作为特征是最高级的表示。
采用概念作为特征有很多好处。首先，一个概念可能对应若干个不同的词，这样将大大降低特征空间的维数，提高分类速度；其次，同义词的聚类使得该概念的权重集中，避免了权重分散带来的对该特征的削弱，从而提高分类的精度。
用概念表示文本需要有一个专门的语义词典，这就需要语言专家和各领域专家的参与，无疑将耗费大量的人力和物力。所以，用概念表示文本的想法虽然非常好，但进展并不十分理想[119]。
3.2.2特征向量
特征空间中不同特征项对文档的重要程度和对分类的贡献是不同的，因此文本分类系统在对文本进行形式化处理的时候，需要对文本的每个特征项赋权，以形成特定文本的特征向量，权重越大的特征认为对文本越重要。由于各研究者对特征重要性认识的不同，涌现出了许多特征权重计算方法，下面介绍几种常用方法，这些方法都基于Zobel 和Moffat 提出的假设[64,120]：
（1）IDF(Inverted Document Frequency)假设：稀有特征的重要程度不低于常见特征；
（2）TF(Term Frequency)假设：一篇文档中出现多次的特征的重要程度不低于只出现一次的特征；
（3）规范化(Normalization)假设：同样的特征匹配数，长文档的重要程度不高于短文档。
从把文本转换为若干个特征的集合到生成文本的特征向量，通常需要经过三个步骤：生成索引向量；对索引向量赋权；规范化。 3.2.2.1文本索引
设训练集有N 篇文档，特征空间为T ={t 1, t 2,..., t |T |}，对文本d j 进行索引后得到索引向量f j =(f 1j , f 2j ,..., f |T |j ) ，其中，f kj 表示特征t k 在文本d j 中的索引值。索
引值的计算通常有以下几种方式。
布尔索引是最简单的一种索引方式，f kj 值的取0或1，取值方式如下：
⎧1, 若t k 在文本d j 中出现f kj =⎨ (3-1)
0, 若t 未在文本d 中出现k j ⎩
词频索引采用特征t k 在文本d j 中出现的次数TF kj 作为索引值：
f kj =TF kj (3-2)
对数索引也利用了特征t k 在文本d j 中出现的次数TF kj ，计算公式如下：
f kj =log(TF kj +1) (3-3)
可以看出，无论采用何种方式计算的索引向量均为非负向量。虽然索引向量真实反映了文本中各特征项出现的情况，但由于各特征对分类的贡献不同，需要在索引向量中进一步加入类别信息，以便准确分类。 3.2.2.2特征赋权
特征赋权的方式有很多种，可以分为“均权”与“非均权”两类。顾名思义，所谓“均权”，就是研究者认为特征在整个训练集中的统计信息对分类不会产生实质性的影响，所以给索引向量中的每个特征赋以相同的权重，也就是使用原索引向量，既不突出也不抑制任何特征。而“非均权”认为特征分为主要特征和次要特征，经过赋权处理可以放大主要特征的作用，缩小次要特征的作用。
目前的研究普遍认为不同特征在分类中的贡献是不同的，一般采用“非均权”对特征加权。其中最有代表性的是“IDF(Inverted Document Frequency)权”。IDF 权认为训练集中包含特征t k 的文档数目越多，则该特征对分类的贡献越小，这样的特征需要受到抑制；相反，训练集中包含特征t k 的文档数目越少，则该特征对分类的贡献越大，这样的特征需要被放大。设特征加权向量为g =(g 1, g 2,..., g |T |) ，训练集中出现过特征t k 的文档数为DF k ，那么特征t k 的加权值g k 由下式计算：
g k =N
) (3-4) DF k
至此，文档d j 由加权索引向量h j =(h 1j , h 2j ,..., h |T |j ) 表示，h j 等于索引向量f j
与特征加权向量g 的内积，由公式(3-5)计算。
h j =f j ∙g =(f 1j ⋅g 1, f 2j ⋅g 2,..., f |T |j ⋅g |T |) (3-5)
3.2.2.3规范化
为了消除文档长度不同对加权索引向量h 的影响，需要对h 进行规范化处理，使得各特征权重落在区间[0,1]内，最终生成文本d j 的特征向量
w j =(w 1j , w 2j ,... w , |T |j ) 。特征t k 的权重w kj 的计算公式如下：
w kj =
h kj
∑h
i =1
|T |
(3-6)
2ij
3.2.2.4相似度计算
文本表示为向量后，文本之间的距离或相似度可以通过空间中这两个向量的几何关系来度量。设有两个特征向量x =(x 1, x 2,..., x |T |) 和y =(y 1, y 2,..., y |T |) 。
如果特征向量是布尔向量，那么相似度函数通常采用汉明距离，定义如下：
D (x, y ) =|T |-∑(x i ⊕y i ) (3-7)
i =1|T |
如果特征向量非布尔向量，则相似度函数通常采用夹角余弦函数，定义如下：
sim (x , y ) =
∑x ⋅y
i i =1
|T |
i
∑x
i =1
|T |
2
i
⋅
∑y
i =1
|T |
(3-8)
2i
3.3经典特征权重
在文本分类领域，通常使用Salton 等人提出的TFIDF(Term Frequency and Inverted Document Frequency)公式计算特征项权重，特征t k 在文档d j 中的TFIDF 计算公式如(3-9)所示[5]：
tfidf (t k , d j ) =TF kj ⋅log(
N
) (3-9) DF k
其中，TF kj 表示特征t k 在文档d j 中出现的次数，DF k 表示在整个训练集中包含特征t k 的文档数，N 表示整个训练集中包含的文档数。该公式的直观解释为：特征t k 在文档中出现的次数越高，在整个训练集中包含该特征项的文档数目越少，则该特征权重越大；反之，特征t k 在文档中出现的次数越少，在整个训练集
中包含该特征项的文档数目越多，则该特征权重越小。
对tfidf (t k , d j ) 的规范化处理如下式所示：
w kj =tfidf (t k , d j )
∑2(tfidf (t , d )) i j i =1T (3-10)
其中，|T |表示特征向量的维数。
第四章 文本分类算法
4.1引言
文本分类算法作为自动文本分类技术的核心，一直处于重点研究与不断发展当中。多年来的研究积累了很多经典的分类算法，如Naive Bayes[32,33]、k 近邻[30]、决策树[34]等，也涌现出了不少新算法和改进的分类算法[35-45]。这些研究基本都致力于改进训练和分类的速度和精度。
目前文本分类的算法有很多种，包括k 近邻法、朴素贝叶斯算法、决策树算法、决策规则算法、回归模型、在线算法、Rocchio 算法、神经网络算法、支持向量机算法、最小二乘拟合与分类器组方法等。文本分类算法基本来源于机器学习与信息论领域，总体来说分类算法大致可分为两大类：基于统计的方法和基于规则的方法。朴素贝叶斯算法是经典的基于统计的算法，决策树则是基于规则的方法中的典型。
为分类系统选择分类算法时需要考虑以下几个方面的问题：第一，分类算法本质上是两类算法还是多类算法，例如支持向量机是两类分类算法，而k 近邻则可以用于多类分类，如果使用两类算法进行多类分类，则需要首先把多类分类任务分解为若干个两类分类任务后，再进行训练；第二，分类算法使用的是局部特征还是全局特征，所谓局部特征是指训练与分类时每个类别分别采用不同的特征空间，全局特征是指训练与分类时所有类别采用相同的特征空间，大部分分类算法使用全局特征与局部特征均可，但有些算法如朴素贝叶斯只能采用全局特征；第三，训练与分类的时间复杂度，一个好的分类系统应该对文本能够快速准确地分类，训练时间较长通常可以忍受，但如果分类时间过长则往往让人难以接受，例如k 近邻法在大规模文本分类问题中就存在时间灾难的问题。
虽然已经出现了一些性能不错的文本分类算法，但由于各个算法在不同应用中的表现差异较大，因此仍然有很多学者致力于更为高效的算法的研究。
4.2文本分类算法
目前的文本分类领域已经有了一些比较成熟的文本分类算法，下面我们介绍几个常用算法。
4.2.1朴素贝叶斯算法
朴素贝叶斯(Naive Bayes, NB) 算法是机器学习领域中常用的一种基于概率的分类算法，非常简单有效。NB 算法基于这样一个朴素的基本假设（称作贝叶斯假设）：假设文本中各个特征的出现是相互独立的 [125]。该算法的关键是计算文本d j 属于类别c i 的后验概率，根据贝叶斯公式(4-1)，把后验概率的计算转化为先验概率的计算，然后取后验概率最大的一个或几个类别作为文本最终类别。显然，NB 法是个多类算法，并可直接应用于多标号分类问题中。
P (d j |c i ) ⋅P (c i ) P (c i |d j ) = (4-1) P (d j )
其中，P (c i |d j ) 表示文本d j 属于类别c i 的后验概率，P (d j ) 表示文本d j 在训练集
中的概率，P (d j |c i ) 表示类别c i 中d j 的先验概率，P (c i ) 表示训练集中类别c i 的先
验概率。由于如果d j 确定，那么对所有类别P (d j ) 为常数，因此有
arg m ax P (c i |d j ) =arg m ax P (d j |c i ) ⋅P (c i ) (4-2) c i c i
接下来的问题就是如何估计P (d j |c i ) 和P (c i ) 。目前存在两种计算模型，多
变量贝努利模型(Multi-variate Bernoulli Model) 与多项式模型(Multinomial Model) 。假定训练集的特征空间为T ={t 1, t 2,..., t |T |}， t k 表示第k 个特征，|T |表示特征空间的维数，下面对这两种模型分别进行介绍。
1. 多变量贝努利模型
多变量贝努利模型中，特征向量采用二进制权重，在文档中出现过的特征权重为1，未在文档中出现过的特征权重为0。该模型是贝叶斯网络中的传统方法，已被广泛应用于文本分类中[10,102,126]。在整个计算过程中，未考虑特征在文档中
出现的次序。由于贝叶斯假设认为文档中各特征间是相互独立的，所以P (d j |c i )
可由下式计算：
|T | P (d j |c i ) =∏P (t k |c i ) (4-3)
k =1
其中，P (t k |ci ) 表示类别c i 中特征t k 出现的概率。
计算P (t k |ci ) 时，把文档看作是一组独立的贝努利实验，每个特征对应一个贝努利实验，用DF ki 表示类别c i 中包含特征项t k 的文档数，|c i |表示类别c i 中包含的所有文档数，那么P (t k |ci ) 的计算公式如下：
P (t k |c i ) =1+DF ki (4-4) |c i |
类别c i 的先验概率P (c i ) 采用最大似然估计法计算，公式如下：
P (c i ) =|c i | |D | (4-5)
其中，|D |代表训练集D 中的所有文档数。
2. 多项式模型
与多变量贝努利模型采用二进制权重不同，多项式模型考虑了文档中特征出现的频率，在该模型中，文本的特征向量权重由特征t k 在文本d j 中的出现次数TF kj 表示。和多变量贝努利模型一样，多项式模型也忽略了特征在文档中出现的
次序。在该模型中，P (d j |c i ) 和P (t k |ci ) 的计算公式如下：
TF |T | P (t k |c i ) kj
P (d j |c i ) =P (|d j |)⋅|d j |!∏ (4-6) TF kj k =1
1+∑TF kj
P (t k |c i ) =j =1|c i |
|T |+∑∑TF sj
s =1j =1|T ||c i | (4-7)
在式(4-7)中，分子表示类别c i 中特征t k 出现的次数，分母表示类别c j 中所有特征出现的总次数，为避免出现零概率，对分子和分母进行了平滑处理。
Andrew McCallum等人对多变量贝努利模型和多项式模型进行了比较，认为多项式模型在文本分类中的性能要优于多变量贝努利模型[128]，其主要原因是多项式模型考虑了文档中特征出现的频率，因此包含了更多文档信息的缘故。
另外，所有的模型都是基于贝叶斯假设的，该假设虽然大大简化了贝叶斯分类器的计算，但是也导致了其分类质量不是很理想的状况。
4.2.2 k近邻法
k 近邻法(k-Nearest Neighbor, kNN) [30,31]又称为基于实例(Example-based, Instance-bases) 的算法，其基本思想相当直观：把未知文本d 与训练集中的每篇文本进行比较，找出最邻近的k 篇文本，用这k 篇文本的类别来判断未知文本的类别。类别判断方法如下：对找到的k 篇文本，为每个类别打分，然后排序，只
有分值超过指定阈值的类别才判定为文本d 的类别。每个类别的分值score (d , c i )
的计算公式如下： score (d , c i ) = sim (d , d j ) y (d j , c i ) -b i (4-8) ∑d j ∈kNN
其中，d 为待分类文本d 的特征向量；d j 为最近邻的k 篇文本之一d j 的特征向
量；sim (d , d j ) 为d 与d j 的相似度，相似度的计算见本文3.3.4的介绍，通常使用
余弦相似度；y (d j , c i ) 为文本d j 在类别c i 中的权重，通常d j 属于c i 时取1，d j 不
属于c i 时取0；b i 为事先设定的阈值，可以在确认集(validation set)上通过训练得
到。所有使得score (d , c i ) >0的类别均判定为文本d 的类别，因而kNN 算法可以
用于多类多标号文本分类问题。
kNN 算法的一个关键问题是k 值的选择，k 值过大会包含较多错误类别的文本，k 值过小又会使得边缘文本难以被正确判断。另外，kNN 算法无须训练，但需要在分类时把待分类文本与训练集中所有文本进行比较，因此对于小规模文本分类问题，使用kNN 不失为一个有效的办法，但对于大规模文本分类问题，kNN 需要耗费大量的分类时间。该算法的分类效率非常低，但是在分类精度上，是效果最好的分类器之一，并且，性能也比较稳定[29]。
4.2.3 Rocchio法
Rocchio 法来源于信息检索系统，后来最早由Hull 在1994年应用于分类[74]，从那以后，Rocchio 方法就在文本分类中广泛应用起来。Rocchio 方法可能是文本分类领域唯一一个植根于信息检索领域而不是机器学习领域的分类器，该方法
在训练阶段为每个类别c i 建立一个代表向量c i =(w 1i , w 2i ,..., w |T |i ) ，其中|T |表示训
练集中的特征总数。在对文本d 分类时计算d 与c i 的相似度，取相似度最大的一
个或几个类别作为文本d 的类别。
类别c i 的代表向量c i 的第k 维值w ki 由公式(4-9)计算：
w ki =β∑d j ∈c i w kj
|c i |-γ∑d j ∉c i w kj
N -|c i | (4-9)
其中，β为训练样本中正例的控制参数，γ为训练样本中反例的控制参数，|c i |表示训练样本中正例的数目，N 表示训练样本的文档总数，正例指属于类别c i 的文本，反例指不属于类别c i 的文本。β和γ是两个控制参数，可以通过提高β降低γ来削弱反例的影响。
进行分类时，待分类文档d =(w 1, w 2,..., w |T |) 与类别c i 的距离度量公式为：
sim (d , c i ) =∑w w k
k =1
|T |2
k
k =1|T |ki ∑w ∑w k =1|T | (4-10) 2ki
当β＝1，γ＝0时，类别代表向量c i 成为正例的质心。
Rocchio 方法容易实现，分类速度快，尤其适合于大规模文本处理。但是，对于一个包含几个互不相交的簇的类别，例如，“运动”类包含“篮球”和“爬山”两个不相干的簇，该类别的质心则可能会落在所有簇的外面，如果使用Rocchio 法分类将导致大部分正例被误分的情况发生。