文本分类概述

第一章绪论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文本分类的定义文本分类是指依据文本语义内容将未知类别的文本归类到已知类别体系中的过程。文本分类有多个英文名称，如TextCategorization[5]、TextClassification[6]、DocumentCategorization[7]、DocumentClassification[8]以及TopicSpotting[9]等，现在比较常用的为TextCategorization(TC)。文本分类的形式化定义如下，假设有一个文本集合D={d1,…,d|D|}和一个预先定义的类别集合C={c1,…,c|C|}，二者之间的真实关系可由以下函数表示[5]：jijijijicdifFcdifTcdcdFTCD,,),(),(},{:(1-1)于是，自动文本分类问题可以转化为找到函数的近似表示：jijijijicdifFcdifTcdcdFTCD,,),(),(},{:(1-2)使得尽量逼近未知的真实函数。此处的函数称为文本分类器，力求真实反映文档和类别的关系，以便尽可能对未知类别的文本进行正确分类。文本分类根据分类算法的不同，可以分为两类分类算法和多类分类算法。所谓两类分类算法是指算法本质上只能进行两类分类，即只能判别文档属于两类中的某一类，如支持向量机算法；而多类分类算法是指算法可以同时对多个类别进行操作，即同时判别文档属于多类中的某一类或某几类，如KNN算法。两类分类算法应用于多类分类问题时，通常需要将一个多类分类问题转化为若干个两类分类问题来解决。具体转化方法将在本文第二章详细论述。另外，文本分类根据文档所属类别是否单一还可以分为单标号分类(Single-labelTextCategorization)问题和多标号分类(MultilabelTextCategorization)问题。所谓单标号分类指文档的类别体系没有重合，一篇文档属于且只属于一个类别，而多标号分类是指文档的类别体系有重合，一篇文档可以属于多个不同的类别。1.2.2自动文本分类过程现代自动文本分类技术涉及到人工智能、机器学习、模式识别和统计理论等多个学科，自动文本分类的过程实际上也是机器学习和模式识别的过程。图1-1为基本的分类过程。文本表示特征降维性能评价文本表示分类器训练文本测试文本未知类别文本分类结果训练模块分类模块预处理预处理图1-1自动文本分类模型如其他机器学习问题一样，文本分类也包括训练和测试两个模块。训练模块由预处理、文本表示、特征选择(FeatureSelection)、分类器(Classifier)和性能评价五个部分组成：1.预处理负责对训练集中的文本进行去除停用词、词干化(Stemming)、分词、统计等操作，并对文本进行去噪处理。此处对中英文分别采取不同的处理，英文使用空格进行分词[1,10]，而中文则需要根据语义进行分词[11-15]或采用N-gram法进行分词[16,17]。2.文本表示把文本表示成分类算法可以识别的形式。最常用的统计模型是由Salton等人提出的向量空间模型[18]，在此模型中，文档dj被表示成向量的形式，jTjjww||1,,w，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发表了具有里程碑作用的论文“Automaticindexing:Anexperimentalinquiry”，采用贝叶斯公式进行文本分类，大大推进了文本分类工作。在该文中，Maron还假设特征间是相互独立的，这就是后来被广泛采用的“贝叶斯假设”。在随后的二十多年，主要是采用知识工程(KnowledgeEngineering,KE)的方法进行文本分类[26]，它通过在专家知识基础上手工建立一系列分类规则来构建分类器。知识工程方法需要大量领域的专家和工程师参与，势必耗费很多人力物力，当电子文档急剧增长时将无法满足需求。这种方法最典型的应用实例为由CarnegieGroup开发的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信息检索毫无疑问，信息检索(InformationRetrieval)工具可以根据查询词返回相关信息，有效帮助了人们查找相关知识，如Goole、Baidu、Yahoo、Excite等搜索引擎。但是，所有的搜索引擎都存在着相同的一个问题，返回结果并没有如用户期望的那样排列，并且包含了大量用户不感兴趣的网页，用户必须通过阅读这些网页滤除无用信息，这就降低了查询效率。在信息检索领域引入文本分类技术，由用户选择查询类别，或者由搜索引擎给出分类存放的搜索结果，都可以提高查询效率，方便用户使用。另外，针对信息资源库中各个不同类别，还可以建立各类别的专用搜索引擎，直接供仅对某个专题感兴趣的人使用。1.4.3冗余文档过滤信息检索不仅包含了大部分用户不感兴趣的类别，还包含了大量相同或相似的网页，在搜索结果较少时更是如此。这些相同或相似的网页称为冗余文档，相同网页是指除了链接地址不同，内容完全相同的网页；相似文档是指内容只有少许不同的网页。虽然各大搜索引擎都号称对相同和相似网页进行了过滤，但在搜索结果中包含大量相同或相似网页的情况还是经常出现。利用文本分类技术对网页计算相似度，超过指定阈值的网页即可认为是冗余文档，在数据库中只保存一份。NarayananShivakumar等对24,000,000个网页进行统计分析，发现有18％的网页有一个重复网页，5％的网页有10到100个重复网页，经过冗余检测后，可以把存储空间压缩22％[