（管理科学与工程专业论文）基于扩展网页和公平特征选择的网页分类算法研究.pdf

摘要 摘要 随着互联网技术的不断发展，i n t e i 州e t 上的信息只益丰富，已经成为人 们同常工作和生活中获取信息的重要来源。但是，由于i n t e r n e t 所固有的开 放性和异构性，用户很难从纷繁复杂的海量信息中准确定位到自己所需要的信 息。 因此，如何合理和有效地组织和管理网上信息，已经日益成为信息处理领域 一个十分重要的研究课题。传统的处理方式是依靠人工的方法对网页进行分类， 即专业人员在浏览网页后，根据其内容将它划分到一个或多个类别中。然而，网 页信息在不断地快速增长，仍然依靠人工的方式对大量的网页进行分类，将是不 合适，也是难以实现的。为了使用户更容易更准确地定位所需要的信息，众多的 学者开始研究网页自动分类技术。 自动文本分类是在给定的分类体系下，由特定的算法根据文本的内容确定 与之相关联的类别。自动文本分类是人工智能技术和信息获取技术相结合的研究 领域，是进行基于文本内容的自动信息处理的核心技术。本文对中文网页分类算 法进行了研究，具体内容如下： 1 、研究了中文网页分类的背景和难点。分析了中文文本分类的基本原理，对传 统的特征选择和分类算法进行了分析，对比了传统特征提取方法的优缺点。 2 、详细论述了对中文网页进行自动分类的主要问题。即网页的表示和网页的预 处理。论述了网页预处理过程，包括网页的清洗和中文自动分词技术。 3 、本文提出了一种将扩展网页和公平特征选择相结合的网页分类算法。考虑到 超链接的重要性，通过建立扩展网页，增加了关键分类特征的比例和数量，从而 提高了网页分类的准确率。考虑到网页结构的重要性，我们把锚点文本所在的句 子或段落添加到原网页形成扩展网页。公平特征选择算法不仅可以公平的对待每 个类，而且可以识别有效特征，降低特征空j 目的维度。 4 、对本文提出的算法进行实验，并对实验结果评估。实验结果数据表明，本文 提出的算法可以有效的提高网页分类的准确率和f 值，是一种有效的网页分类算 法。 关键词：公平特征选择算法扩展网页特征提取网页分类 论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：一至毕 伊辱钿胡 第l 章绪论 1 1 背景介绍 第1 章绪论 随着互联网技术的飞速发展，网络上的信息资源呈指数级增长，i n t e m e t 己 经成为拥有几十亿个页面的分布式信息空问，人们从信息缺乏的时代过渡到信息 极为丰富的数字化时代。由于互联网在线信息的快速增加，“信息迷向”、“在信 息超载”已经成为一个同益严峻的问题，尽管搜索引擎能在一定程度上帮助人们 获取网上资源，但由于查全率和查准率不高，反馈结果存在大量无关信息，因而 不能很好地满足人们从互联网上获取有价值信息和进行深层次信息挖掘的需求。 因此，人们对网页自动分类技术的需要越来越迫切。网页自动分类是处理海 量网页的有效手段，它能提供网页集的良好组织结构，简化网页的存取和操作， 提高网页处理效率。网页自动分类技术已经成为组织和管理在线文本数据的关键 技术。网页自动分类技术不仅可应用于对未知类别网页的在线分类，也可对大批 量己经分类的网页按新的分类体系进行重新分类，以满足不同的应用需求。实际 上网页索引、网页摘要、网页过滤、w 曲资源的按层次分类组织、个性化信息服 务，以及所有需要进行网页文档自动整理、自动选择和发送的应用都可采用网页 自动分类的技术和方法来实现，因此网页自动分类技术具有很高的研究价值和研 究前景。 网页自动分类也称为在线文档分类( o n l i n ed o c u m e m sc a t e g o r i z a i i o n ) ，通过分 析被分类网页的特征，并与各类别中网页所具有的共同特征进行比较，将被分类 网页化归为特征最接近的一类并赋予相应类别。面对网上的海量信息，传统的做 法是对网上信息进行人工分类，并加以组织和整理，为人们提供一种相对有效的 信息获取手段。但是，这种人工分类的做法存在着许多弊端：一是耗费大量的人 力，物力和财力。二是存在分类结果一致性不高的问题。即使分类人的语言素质 较高，对于不同的人分类，其分类结果仍然不尽相同。甚至同一个人，在不同时 间做分类也可能会有不同的结果。i n t e m e t 上各种信息的迅速增加，仅靠人工的 方式来处理是不切实际的。 传统的人工分类的做法存在许多弊端，不仅是耗费大量人力、物力和精力， 而且存在分类结果一致性不高的问题。因而，构造一个有效的文本分类系统是十 分必要的。文本分类是一个活跃的科研领域，它是数据挖掘中一个重要的研究领 域。采用文本分类技术可以建立起一个自动的文本分类系统，相对于人工分类， 自动分类系统具有以下特点： 第1 章绪论 高效率、高速度。自动分类的效率将是人工分类的百倍甚至千倍，从而节约大 量的人力物力。 较高的准确度消除了人为错误产生的可能。 良好的自适应性。可快速适应文本的更新及类别的变化，适应不同环境及需求。 众多的研究者对文本分类系统，进行了深入的研究，提出了许多统计方法和机器 学习方法。并且在实验中有很好的表现。但是，在这个领域还是有很大的空间值 得我们继续去研究和探索。 1 2 国内外文本自动分类研究动态 文本自动分类技术起源于上个世纪5 0 年代，h p l u h n 在这方面作了开创性 的研究，提出了词频统计的思想，6 0 年代g s a l t o n 等人( 1 9 9 1 ) 提出的向量空间模 型成为后来进行文本表示的主要方法，7 0 年代以后，m e s t e v e n s ，s k e e n a n ， l b 跏y l e 等人也在这个领域进行了卓有成效的研究。早期的自动分类研究因为 受计算机发展水平的限制，更多的是可行性的研究。 2 0 世纪8 0 年代，文本分类的研究进入实验阶段，当时主要采用基于知识的 分类方法。基于知识的分类系统需要知识库作为支撑，而知识提取、更新、维护 及自我学习的相关技术尚为达到实用化程度，因此其应用领域较为狭窄，目前在 实际应用中已经很少单独采用这种方法。 2 0 世纪9 0 年代以来，随着世界范围内数字图书馆研究的兴起，特别是9 0 年代末互联网的迅速普及和发展，出现了大量的需要进行分类的语料，使得文本 自动分类技术得到了迅猛的发展，逐渐由可行性研究转向实用化研究阶段。这个 阶段出现了大量的基于统计和机器学习技术的分类方法，这些方法大多采用向量 空间模型进行文本表示，比较典型的如r o c c h i o 方法( k j e r s t ia a s ，1 9 9 9 ) 、b a y e s 方法( l u d o v i cd e n o y e r ，2 0 0 4 ) 、i c 沦n ( k 最近邻) 方法( y i m i n gy 抽g ，2 0 0 2 ) 、决策 树( j 孙j o n gt s a y 2 0 0 0 ) 、相似性度量( s a l t o n ，1 9 9 1 ) 、神经网络法( m 培u e le r u i z ，2 0 0 0 ) 、支持向量机( s v m ) 等方法( 1 l l o r s t e nj o a c h i m s ，1 9 9 8 ) ，这些方法在英 文一级欧洲语种文本分类上有广泛的研究，而且很多研究表明州和s v m 是 英文文本分类的最好方法( y a n gy e ta 1 ，1 9 9 9 ) 。 相对于国外文本分类的发展水平，国内自动分类研究起步较晚，始于2 0 世纪8 0 年代初期。1 9 8 1 年，侯汉清对计算机在文献分类工作中的应用作了探讨。 早期的系统主要特点是结合主题词表进行分析分类，人工干预的成分很大，如香 港中文大学的w r a i l 锄( 1 9 9 8 ) 等人将k n n 方法和线性分类器结合，取得了较好效 果，在召回率接近9 0 时准确率超过8 0 。c k p w b n g ( 2 0 0 0 ) 等人研究了用混合 第l 章绪论 关键词进行文本分类的方法，召回率、准确率为7 2 ，6 2 。复旦大学和富士通 研究开发中心的黄董蓄、吴立德、石崎洋之等( 2 0 0 0 ) 研究了独立语种的文本分类， 并以词汇和类别的互信息量为评分函数，分别用单分类器和多分类器对中文和日 文文本进行了实验，最好的结果召回率为8 8 8 7 。上海交通大学的刁倩、王永 成等人( 2 0 0 0 ) 结合词权重和分类算法进行分类，在用v s m 方法的封闭式测试实 验中分类正确率达到9 7 。此后，基于统计学的思想，以及分词、语料库等技术 被不断应用到分类中。 随着中文信息处理技术特别是中文自动分词技术的同渐成熟，以此为基础的 中文文本分类技术的研究得到了飞速发展，在短短2 0 多年中完成了从可行性探 索到实用化阶段的转变。随着w e b 信息的迅速增加，面向w r e b 的以网页作为语 料库的自动分类研究已经成为新的研究热点。 1 3 网页自动分类的研究现状 网页的自动分类研究自上世纪8 0 年代互联网兴起以后才逐渐发展。由于文本 自动分类的研究相对较早，而且拥有比较成熟的技术，因此有不少研究工作试图 使用纯文本分类技术实现网页分类。这些研究主要分两种思路，一是用表示纯文 本的方式表示网页，二是组合文本分类器的方法。f u r n k r a n z ( 1 9 9 9 ) 用指向该网 页所有链接周围的文本、链接所在段落的标题以及上级标题文本表示网页，并用 r i p p e r 算法对文本进行分类，准确率比使用网页局部文本提高了2 0 ： c h a k r a b a r t i ( 1 9 9 8 ) 和g h a n i ( 2 0 0 1 ) 尝试用网页的局部文本和跟它链接网页的文 本表示网页，分类结果还没有只使用网页局部文本好；o h ( 2 0 0 0 ) 等人也结合网页 局部文本和链接网页的文本表示网页，但没有引入所有链接网页的文本，而是基 于文本相似性选择了部分跟原网页接近的网页文本，试验结果f l 值比使用所有链 接网页提高了7 。y a n g ( 2 0 0 2 ) 等人通过在h o o v e r s 和w e b k b 数据集上的研究给出了 比较客观的解释：网页是否集中地存在某种规律以及能否利用这些规律，对网页 分类算法的性能影响较大，因此应该根据这些规律设计网页的表示方式和网页分 类算法。c h o o n ( 2 0 0 0 ) 用组合网页分类器的方法进行网页分类，其中一个分类器 用网页中的纯文本、标题和子标题文本表示网页，另一个分类器用指向该网页所 有链接周围的文本表示网页；国内的范焱( 2 0 0 1 ) 等人提出一种用朴素贝叶斯分类 器综合网页纯文本和其它结构信息的分类方法。试验结果证明组合后的分类器性 能都有一定程度的提高。 1 4 课题研究的难点及突出问题 第l 章绪论 网页分类是在文本分类技术上发展起来的，但网页分类问题相对文本分类更 加难处理，要考虑更多因素，这一特点主要是由网页特征决定的。网页分类面临 的突出问题主要有以下几个方面： 1 网页格式多样化：多种格式并存，而且同一格式的网页也存在多个标准，同时 由于网页的写作风格及内容变化都很大，因此如何解析不同格式、不同风格的网 页成为网页预处理的一个难点； 2 分类主题的模糊：互联网的知识系统发展异常迅猛，各种新的知识结构不断涌 现，如果训练语料库得不到及时更新，就会导致网页无法分类； 3 网页去噪：网页中存在大量与页面主题无关的噪音信息，如何提高去噪算法的 性能是有待研究的问题； 4 网页结构信息：网页含有丰富的结构信息，除纯文本以外，还有其它一些内容 对分类有贡献。如h n 和t i t l e 标注网页的标题和段落子标题，m e t a 标记中的n a m e 属性值和c o n t e n t 属性值是对网页主题的描述，网页中的超链接指向的内容有可 能是与该网页主题相关的内容，这些信息都对网页分类有贡献，也可能存在噪声， 综合利用上述特征设计分类算法是网页分类的关键，也是难点所在； 5 。缺乏评价标准：对于网页分类系统，目前没有统一的评价标准，常用的评价指 标有准确率和召回率。网页数量极其巨大，单纯的召回率已经没有实际价值，准 确率的意义也要作相应的变通：数据库规模，索引方法，用户界面，响应时间应 该纳入评价体系，作为评价指标。 中文网页自动分类系统的研究对象为中文网页。中文网页与普通英文文本相 比有以下几方面的不同： 首先中文处理要比英文处理复杂的多，需要采用专门的方法。其次网页是半 结构化的数据，和无结构的纯文本相比，在处理方法上有较多的差异。 此外网页自动分类系统的处理对象往往是大规模、动态的、开放的网页集合，分 类处理的实时性要求很高。 根据中文网页处理的上述特点，结合文本自动分类技术，系统的关键技术主 要包括网页及文本预处理、网页表示、特征选择、自动分类算法、性能评估五个 方面。 1 5 本文工作及内容安排 在已有的网页分类的研究中，多数是基于单个网页的分类系统，由于网页格 式的多样化，因此无法有效地提取到全部有用信息。本文提出利用网页超链接文 本扩展原网页，利用公平特征算法解决网页分类中的非公平性问题。文中使用 4 第l 章绪论 e p f f s s 算法，有效提高了有用词对类别的贡献，降低了网页中噪音词的影响，实 现了网页的无偏分类。此外，本文还比较了几种典型的分类器并做了进一步的理 论研究和实验分析。 本文的结构安排如下： 第一章绪论，综述了本研究课题的背景及应用领域，介绍了本文研究的主要工 作和论文的结构安排。 第二章，主要对文本分类的基础理论及相关技术。 第三章，中文网页表示及其预处理的内容。 第四章，扩展网页和公平特征算法介绍，e p f f s s 的算法。 第五章，实验设置与结果分析，主要介绍实验过程与实验结果。并对结果进行了 全面分析，得出了具有借鉴意义的实验结论。 第六章结论与展望，对全文工作进行了总结，并提出下一步的工作展望。 第2 章文本分类的基础理论及相关技术 第2 章文本分类的基础理论及相关技术 网页分类的核心问题是文本自动分类技术。文本自动分类的研究涵盖若干学 科领域，包括语言学中的自然语言处理，图书情报学中的分类学，数学领域的统 计学等，以及计算机领域的模式识别、人工智能、神经网络等研究方向。本章将 分别介绍文本分类的基本概念、文本自动分类系统的基础理论和相关技术，以及 文本分类的评价体系。 2 1 文本分类的基本概念及特点 2 1 1 文本分类的基本概念 从数据挖掘的角度来说，自动分类是个有指导学习( s u p e r v i s e dl e a r n i n g ) 的过程。在这个学习过程中，它根据一个己被人工处理过的训练文本集合 ( t r a i n i n gs e t ) 去挖掘出文本属性和文本类别之间的关系模型，然后根据学习得 到的这种关系模型对新到来的文本测试集合( t e s ts e t ) 进行自动的类别判断。文 本分类的形式化定义：文本分类就是将一个二元组( z ，f ) d x c 映射到一个布 尔值的任务。该映射用数学公式表示如下：m ：伙c _ 佤日，其中d = “，呸，) ， c = ( q ，巳，c 。) 。这里d 为待分类的文本集合，c 为给定分类体系下所有预先 定义的类别的集合，d 可以是无限集合，而c 必须是有限集合。如果将二元组( 谚，c ，) 映射为值t ( t r u e ) ，则认为文本z 属于类别c ，否则认为文本z 不属于类别c ，。 文本分类的关键就是要找到一个函数：d c 一 丁，用，使得通过该函数 能够将任意一个文本尽可能准确地分类。这罩是根据已掌握的每类若干样本的 信息，总结出分类的规律而建立的判别公式和判别规则。 文本自动分类的方法分为两大类：一是基于规则的分类方法：二是基于统计 的分类方法。文本自动分类的统计模型主要有向量空| 日j 模型、概率模型、线性模 型、非线性模型以及组合模型等。 基于统计学习法的分类系统在整体上可以被分为两类：独立二元 ( i n d e p e n d e n tb i n a r y ) 分类系统和m 元( m a r y ) 分类系统。所谓独立二元分类， 也可以叫做单类别分类，就是给定一篇文档，分类系统对每一个类别都独立地判 断这篇文档是否属于该类：要么属于，要么不属于，而不存在其它的结果，并且 在分类过程中，不同类别之间互不影响。所谓m 元分类，也可以叫做多类别分类， 就是给定一篇文档，系统计算这篇文档与所有预先定义的类的相似度，并按这篇 6 第2 章文本分类的基础理论及相关技术 文档和各个候选类的相似度排序，最后输出候选类列表。 2 1 2 文本分类的特点 文本分类实际上是一个模式分类任务，所以许多模式分类的算法可以应用到 文本分类中。但是，文本分类同时又是模式分类和自然语言处理的一个交叉学科， 是和文本的语义紧密相关的，所以与普通的模式分类任务相比有许多独特之处。 1 高维特征空间 在文本特征提取的时候，存在大量的候选特征。如果使用词语作为文本特征， 即使一个1 0 0 0 篇左右的训练文本集，一般也会产生上万的候选特征。如果使用 n g r a i f l 项作为特征，会产生更多的候选特征。 2 特征语义相关 一种避免特征维数过大的解决方法是，假设大部分特征之间是相互独立的， 使用特征选择方法选取那些彼此无关的特征但是，文本分类中很少特征之间是 彼此无关的。很多特征与上下文之间存在较强的关联性。 3 特征存在多义和同义现象 文本分类中一般使用词、短语和n g r a m 等作为表征语义的文本特征。但是， 这些特征往往无法清晰地表达一种含义。一个特征可能有多种含义，即多义现象。 如：“教授”既可以表示一种职称的含义，也可以代表一种传授知识的含义。同 时，许多相同的含义又可以用不同的特征来描述，即同义现象。如：“计算机 和“电脑”这两个特征都表示相同的含义。 4 特征分布稀疏 根据z i p f 法则，发现一个词出现的频率f 和它的排列位置之间的关系。设它 的排列位置为r ，那么z i p f 法则可以表示成：厂o c ( 1 ，i ) 。 这意味着排列在第5 0 位的词的出现次数大约是排在第1 5 0 位的词的出现次数 的3 倍。文本特征空间的维数是非常高的，而能够作为文本特征的往往是那些在 语料库中出现频度适中的词。对于一篇不是很长的文本来说，特征空间中多数特 征词的出现频率都为o ，导致文本向量中多数特征值都为o ，特征的分布非常稀疏。 2 2 文本表示模型 在大规模文本分类系统中，首要任务就是将非结构化的自然语言文本转化为 结构化的计算机可识别的信息，即对文本进行形式化处理。这一形式化的结果称 为文本表示。 在文本分类领域，文本表示涉及以下两个问题： 7 第2 章文本分类的基础理论及相关技术 一是如何确定表示文本的基本单位。用于表示文本的基本单位通常称为文本 的特征或特征项。文本表示就是要用一定的特征项构成特征向量来代表文本信 息，最终通过这些特征向量来评价未知文本与类的相关程度。在不同内容的文本 中，各特征项出现频率有一定的规律性，不同的特征项就可以区分不同内容的文 本。 文本表示的另一个问题是采用什么方法建立模型。文本表示模型是文本自动 分类的一个重要技术问题。文本表示所采用的模型有很多种，目前通常采用的有 布尔模型、概率模型和向量空间模型。 2 2 1 布尔模型( b o o i e a nm o d e i ) 布尔模型就是采用布尔表达式对文本进行表示。布尔模型在传统的信息检索 中有广泛的应用，它通过与用户给出的检索式进行逻辑比较来检索文本，是一种 基于关键词的匹配。在标准的布尔模型中，文本采用如下的表达形式： z = ( m ，w i 2 ，。w j 。) ， k = l ，2 ，玎其中n 为特征项的个数，为o 或l ， 表示第k 个特征项在文本i 中是否出现。布尔模型易于实现，但在文本分类领域， 它的准确率和召回率较差。 布尔模型在2 0 世纪六、七十年代得到了较大的发展，出现了许多基于布尔 模型的商用检索系统，如d i a i a g ，s t a i r s ，m e d l a r s 等。其主要优点是：速度快、 易于表达一定程度的结构化信息，如同义关系( 电脑0 r 微机o r 计算机) 或词组( 文 本a n d 过滤a n d 系统) 。目前，几乎所有的商用检索系统都采用布尔检索，虽然 布尔检索有着许多优点，但他的缺陷也是很明显的： 1 缺乏对文档相关性排序的概念，限制了过滤功能。 2 难以将用户的信息需求转换为布尔表达式。 3 匹配标准存在某些不合理的地方。 4 检索结果不能按照用户定义的重要性排序输出。 2 2 2 概率模型( p r o b a b iis t i cm o d e i ) 布尔模型是将文档表示为相互独立的项，忽视了词条之间的关联性，概率模 型( 郭辉等，2 0 0 2 ) 基于概率排序原理，概率模型是考虑词与词之问的相关性，把 文档分为相关文档和无关文档。概率模型是一种基于贝叶斯( b a y s e ) 决策理论的 自适应模型，其以成熟的数学理论为基础，通过赋予词的概率值来表示这些词在 相关文档和无关文档之间出现的概率，然后计算文档间相关的概率。 在该模型中，词的权值设为： 第2 章文本分类的基础理论及相大技术 l o g 巫生丛 ( 2 1 ) 。p ( 1 一) 式中p ，p 分别表示某词在相关文档集和无关文档集中出现的概率。 概率模型的优点在于： 1 有严格的数学理论为基础，并采用了反馈原理： 2 文档可以按照他们相关概率递减的顺序来排序。 主要缺点在于： 1 开始时需要把文档分为相关文档和不相关文档的两个集合，实际上这种模型没 有考虑关键词在文档中的频率； 2 使用这种模型增加了存储开销和计算量；其参数估计的难度也较大。 2 2 3 向量空间模型( v e c t o rs p a c em o d e i v s m ) 在当前的大多数信息处理系统中，文本模型，也就是文本的表示主要采用向 量空间模型( v e c t o rs p a c em o d e l ，简称v s m ) 。 2 2 3 1 向量空问模型的基本概念 向量空问模型( v e c t o rs p a c em o d e l ，v s m ) 是由g s a l t o n ( 1 9 7 5 ) 等人在2 0 世纪6 0 年代提出的。它把文档简化为以项的权重为分量的向量表示，把分类过 程简化为空间向量的运算，使得问题的复杂性大大降低。迄今己在实验系统 s m a r t ( r o c c h i oj r ，1 9 7 1 ) ，及多种实用系统如l y c o s ，a l t a v i s t a 中得到了成功 的应用，但这一模型也存在着诸如它的词条正交性假设不符合自然语言的实际等 问题。 向量空间模型的基本思想是：将每个词条作为特征空间坐标系的一维，将文 本看作特征空间的一个向量，用两个向量之间的夹角来衡量两个文本之间的相似 度。在向量空间模型中，每一个文本都被表示为由一组规范化正交词条向量所张 成的向量空间的一个点，即形式化为n 维空间中的向量，因此我们可以将文本抽 象为： 矿( d ，) = ( ( ，h ，) ，( ，心f ) ，( 乙，) ) ， f = l ，2 ，靠( 2 2 ) 其中f ，是特征项i ，w ，是，在文本j ，中的权重。对于一个训练文本集合，我们就 可以得到如图2 一l 所示的一个向量空间w 。 9 第2 章文本分类的基础理论及相关技术 d l ” d 2 ” d r t lw l l 一一一 ”“”“” “。 t i ”。 一一” w i j ”一” n 。 。” “”。 w n l 图2 1 向量空间模型的文本表不 w 通常是一个稀疏矩阵。训练文本和待分类文本在向量空间模型中都可用相 同的方法表示出来。待分类文本的向量越接近训练文本向量，说明其与训练空间 中的文本的相似度越大，越有可能和训练文本属于同一个类别。其计算方法主要 运用t f i d f 公式，目前存在多种t f i d f 公式，一种比较普遍的t f i d f 公式： 职啊卜老黔一仁孙 其中，( ，孑) 为词t 在文本孑中的权重，而矿( ，孑) 为词t 在文本孑中的词频， n 为训练文本的总数，绣为训练文本集中出现t 的文本数，分母为归一化因子。 对两个文本d ，和d ，之间的内容相关度( d e g r e eo fr e l e v a n c e ) 的度量被称为 曲矩( d ，d ，) 。对于文档z ( w f ，w 2 ) 和文档吒( ，2 ) ，我们可以借助向 量之间的某种距离来表示它们之间的相似度，常用向量之间的内积进行计算： s 砌( d ，嘭) = ( 2 4 ) 也可以通过另一种方式表示： j 拥( d ，t ) = ， 七t l ( 2 5 ) i o 第2 章文本分类的基础理论及相大技术 向量空间模型有效地解决了非结构化文本数据的处理问题，大大提高了文本 处理的速度和效率，把对文本的操作转变为对特征向量的操作。 2 3 特征项的选择 在向量空间模型中，特征项的选择对其表达效果有着很重要的影响。一般可 以选择字、词或词组作为特征项，或者更高层次的语言单位都可作为特征项，特 征项也可以是相应词语或者短语的语义概念类，形成概念特征项。 2 3 1 字特征项 字是汉语中最基本的语言单位，以它作为特征项对文本语义的表述能力相对 较差。但是对于中文来讲，分词过程本身就是难点，不好的分词同样会导致系统 性能的下降，并且在汉语中，汉字的数量大大少于词的数量，所以，选择字作为 特征项可以使特征选择的工作量降低。 2 3 2 词特征项 一般认为，词( 词组) 是构成汉语文本的主体，是最能够反映文本语义的基本 单位，通常选择词作为特征项能充分表示汉语的语义，系统的性能优于选择字作 为特征项的系统。但是直接选用文本中的词或词组作为文本特征项也会存在以下 问题： 一是词( 词组) 的数量十分巨大，不算各行各业的专用词，就普通词额数量而 言，一般在1 0 万左右。文本中还存在一些没有实在意义但使用频率很高的虚词和 功能词，这些词经常把一些真正有分类作用的实词淹没掉。 二是汉语中存在大量的同义词，近义词，将它们作为不同的特征显然会使得 两篇类似的但用词风格不同的文本距离相差过大。 2 3 3 概念特征项 概念通常是指代表一类同义词或近义词的条目，它合并了同义词和近义词， 使得特征项的选择尽可能地集中，贴近语义。但是概念本身的判断和处理相对复 杂，汉语中存在同义关系( 如土豆和马铃薯) 、近义关系( 如高兴和愉快) 、从属关 系( 如房顶和房屋) 、关联关系( 警察和罪犯) 等各种关系。如何很好地划分概念特 征项，确定概念类都是关键性问题，而这些处理势必加大了文本处理的复杂度。 潜在语义索引( l a t e n ts e m a n t i ci n d e x ) ( s d e e n e s t e r ，1 9 9 0 ) 是基于潜在语义分 第2 章文本分类的基础理论及相关技术 析( l a t e n ts e m a n tica n a ly sis ) 的术语一一文本表示方法，它在一定程度上实现 了基于语义的检索。 n 元( n g r a m ) 模型。以字作为特征，粒度太大，所包含的语义信息较少：以 词作为特征，需要基于词典进行分词；以概念为特征，受到对中文自然语言理解 水平的限制。而n 元( n g r a m ) 模型，使文本自动分类系统摆脱了对复杂分词处理 程序和庞大词库的依赖，并且，n 元模型比上述提到的标准词代法关注更多的上 下文信息。n g r a m 概念是信息理论创始人s h a n n o n 在研究信源编码时提出来的， 常被用来表示信源输出的连续n 个字符所组成的字符串，s h a n n o n 曾经用它来研究 英文文本中的字符或字符串的统计特性，即信息熵，随后，n g r a m 被广泛应用于 文本压缩、字符识别与纠错等领域，是一种直接面向代码的技术。在文本分类中， n 元模型被( c a v n a r 1 9 9 4 ) ，d a m a s h e k f ( 1 9 9 5 ) 等人研究过。采用n g r a m 作为中文文 本特征项具有以下优点： 无需任何词典支持，无需进行分词处理； 对输入文本所需要的先验知识较少； 关注更多上下文信息。 但是n g r a m 获取技术中的领域无关性和时间无关性的实现是有代价 的：n g r 硼的提取对系统资源的要求较高。因为在进行提取时，会产生巨大的数 据冗余，占用大量的内存空间，实现效率较低，获取n g r a m 将花费较长的时间， 降低了分类系统的性能。故一般采用词作为文本的特征项。 2 4 关键词权的计算 特征项选择出来后，要对每个项赋予权重，应使文本中越重要的项的权重越 大。关键词的权重( s a l t o nge ta 1 ，1 9 9 8 ) 的计算方法有很多：布尔权重，基于 嫡概念的权重，t f 工d f 1 9 型权重。在关键词权重的计算中最为成功的和广为应 用的方法称为“词频与倒文档频度( t e r mf r e q u e n c y i n v e r s ed o c u m e n t f r e q u e n c y ，简写为t f i d f 方法。该方法综合考察了一个关键词在单个文档中的 重要性和在整个数据全集中的重要性，并将二者结合起来成为一个统一的量度。 通常由下式计算 溉：l o g ( 笪+ o 0 1 ) ( 2 们 仇 一 其中，n 表示数据集中文档( 文本) 的总数：俾表示包含关键词的文档的总 数。 第2 章文本分类的基础理论及相关技术 一个关键词在文档z 的权重计算： = 砺。坝( 2 7 ) 以i 件i d f 量度为基础，许多学者对这一量度提出了“正规化” ( n o m a l i z a t i o n ) 的改进方法。针对t f 的改进主要是将词频进行了正规化处理， 将它映射为个在区间 0 ，1 中的量。即： = ( 2 8 ) 由上述公式计算出的权重，往往有少数项的值远远大于其它项。权值过高的 个别项在分类过程中往往会抑制其它项的作用，因此在计算权重时，应对统计出 的词频做适当的均衡处理。经过词频均衡处理的权重计算公式如下： 2 ( 2 9 ) t f i d f 公式只是一种经验公式，并没有坚实的理论基础，它的物理意义并 不明朗。t h o r s t e n ( 1 9 9 7 ) 运用了概率理论对t f 一工d f ，进行了理论上的分析和解 释，并成功地得到了一种新的分类模型。s s h a n k a r ( 2 0 0 0 ) 也对t f i d f 进行了改 进。陆玉昌 2 2 等人从单词加权和向量旋转的角度解释t f i d f 并提出了使用文 本特征选择中的评估函数来代替i n 函数进行权值调整的方法。另外一个经常使 用的正规化方法称为“对数词频”( 1 0 9 a r “h m i ct e r mf r e q u e n c y ) 法，该方法使 用如下公式计算t f 的值： 绣，= l o g ( 加钆) + l ( 2 1 0 ) 对数词频法不使用文本长度或者最大词频这些正规化因子，而是通过对数函 数降低了词频对t f 取值的影响，从而减少了文档中少数的高频词对权重计算的 影响，降低了低频词权重的取值，而且减轻了文档长度的变化对这一取值的变化 影响。 2 5 文本特征选择 构成文本的词的数量非常之大，导致了表示文本的向量空间的维数也相当 多，可以达到几力维。数量过大的特征项一方面导致分类算法的代价过高，另一 第2 章文本分类的基础理论及相关技术 方面导致无法准确地提取文档的类别信息，造成分类效果不佳。因此，需要在不 牺牲分类质量的前提下尽可能地降低特征项空间的维数。 “所谓文本特征，就是用于描述文本内容的原始特征，是内容的外在表现形 式。一个有效的特征集，必须具有彻底性和专门性。其中彻底性是指文本所讨论 的内容被特征词覆盖的程度；专门性是指特征词必须能反映文本的具体内容，而 不是泛泛而谈。为了满足彻底性要求，对文本进行结构和内容分析，以保证对文 本各部分内容的最大限度的覆盖。为了满足专门性，需要消除停用词，选择具有 实际意义的名词及其短语，特别要注意选取面向内容的词汇。 目前对文本特征选择的研究中，所采用的特征提取算法一般是构造一个权重 函数，对特征集中的每一个特征进行独立的评估，这样每文本分类相关技术研究 个特征都获得一个评估分，然后对所有的特征按照其评估分大小进行排序，选取 预定数目的特征作为结果的特征子集。所以，选取多少个最佳特征以及采取什么 评估函数都需要针对一个具体的问题通过实验来决定。 为便于后面的描述，这罩简要给出特征选取的一般过程。给定训练文档集合 d = 碣，破，以 ，设丁= ，i ，f ：，乙) 为对d 中的文档做分词后得到的词汇全集， 用 m 表示集合 1 ，2 ，州。所谓“特征选取”可以看成是确定从t e r m s 到 m 的 一个卜1 映射，即： f - s e l e c t i o n ：丁一 朋】 然后根据计算开销的考虑，取一个f 叻】，认为t 中那些函数值不小于i 的词汇为“选取的特征项”，记做t s 。在完成了特征选取后，分类就是基于t s ， 即以其中的元素为基础，用一个向量来表达每一个文档。分类的过程就是按照某 种算法来比较待分类文档的表示向量和训练集文档的表示向量，取最相近者所处 的类为待分类文档的类。现有的用于文本特征选择的评估函数，主要有文档频率， 信息增益，期望交叉熵、互信息、z 2 统计、文本证据权、几率比等( 陆玉吕等， 2 0 0 2 ) 。这些评估函数可分为两类：基于统计分析的方法和基于机器学习的方法。 2 5 1 文档频率( d f ) d f ( d o c u m e n tf r e q u e n c y ) ，即文档频率( 王美方等，2 0 0 7 ) 。d f 表示在 训练集中包含某个特征项t 的文档数。这种衡量特征项重要程度的方法基于这样 一个假设：d f 较小的特征项对分类结果的影响较小。这种方法优先取d f 较大的 特征项而d f 较小的特征项将被剔除。即特征项按照d f 值排序。不过我们注意到， 这种策略不符合被广泛接受的信息检索理论：高频词没有低频词对文档特征贡献 大。d f 是最简单的特征项选取方法，而且该方法的计算复杂度低，能够胜任大 1 4 第2 章文本分类的基础理论及相关技术 规模的分类任务。 2 5 2 信息增益( ig ) i g ( 陈志雄等，2 0 0 7 ) 通过统计某个特征项在一篇文档中出现或不出现的次 数来预侧文档的类别。i g 的计算公式如下： g ( f ) = p ( e ) l o g e ( q ) + e ( ，) e ( q i f ) l o g e ( e i f ) 怛( f ) e ( e l f ) l o g p ( e l f ) ( 2 1 1 ) ，- l忙l，= i 其中，e ( c ，) 表示一篇文档属于类别e 的概率，p “t ) 表示特征项t 在一篇文档 中出现的概率p ( t ) 表示特征项r 不在一篇文档中出现的概率，e o ) 表示特征项t 在属于类别，的文档内出现的概率，p ( 丁) 则表示特征项r 不在属于类别c j 的 文档内出现的概率，m 表示文档的类别数。从上可以看出信息增益g ( t ) 反映了特 征t 对分类混乱程度的降低，也就是对分类的信息量在实现中通过根据各个特 征的信息赢取值排序，并根据设置的阈值选择出合适规模的特征子集。 2 5 3 互信息( mi ) m i ( m u t u a li n f o r m a t i o n ) ，互信息值，它通过计算特征t 和类别c 间的相关 性来完成提取。计算公式为： 一- 1 0 9 意蒜( 2 2 ) 为了便于计算，简化为： m c ) 汕g 两瓮南( 2 1 3 ) 其中：a 为t 和c 同时出现的次数：b 为t 出现而c 没有出现的次数；c 为c 出现面t 没有比现的次数。n 为所有文档数。如果t 和c 不相关，则i ( t ，c ) 值为 0 。如果有m 个类，于是对于每个t 会有m 个值，取它们的平均，就可得到特征 选取所需的一个线性序。大的i 平均值的特征被选取的可能性大。 2 5 4z 2 统计( c h i ) c h i 方法有和m i 方法基本相似的思想，同样通过计算特征t 和类别c 间的 依赖程度来完成提取。但二者的计算细节不同，c h i 作了更多地考虑，有种看法 认为c h i 是一种“正规化 了的m i 。使用m i 衡量特征项的重要程度时，只考虑 到了正相关对特征项重要程度的影响。如果特征项t 和类别c 反相关，就说明含 有特征项t 的文档不属于c 的概率要大一些，这对于判断一篇文档是否不属于类 第2 章文本分类的基础理论及相关技术 别也是很有指导意义的。为克服这个缺陷，c h i 使用公式( 2 1 4 ) 计算特征项t 和 类别c 的相关性。 托加两蒜筹篙而( 2 1 4 ) 其中：a 为r 和c 同时出现的次数：b 为r 出现而c 没有出现的次数。c 为c 出现而r 没有出现的次数；d 为t 和c 同时没有出现的次数。n 为训练集中的文 档数与m i 类似，如果t 和c 不相关，则z 2 ( f ，f ) 值为o 。同m i 相同，如果有m 个类，每个t 就会有m 个值，取它们的平均，就可得到特征选取所需的一个线性 序。大的z 2 ( ，c ) 值平均值的特征被选取的可能性大。 2 5 5 期望交叉熵( c e ) 期望交叉熵( c e ) 的定义如下： 唧) = 讹| ，) 1 0 9 裂( 2 1 5 ) 其中p ( qf ，) 和p ( c ，) 的意义同信息增益。如果词条和类别强相关，也就是 e ( 仁| f ) 大，且相应的类别出现概率小，则说明词条对分类的影响大，相应的c e 值就大，就很可能被选中作为特征项。期望交叉熵反映了文本类别的概率分布和 在出现了某个特定词的条件下文本类别的概率分布之间的距离，词条t 的期望交 叉熵越大，对文本类别分布的影响也越大。 期望交叉熵与信息增益唯不同之处在于没有考虑单词未发生的情况。实验 表明，用期望交叉熵优于用信息增益。因为虽然某词不出现也可能对判断文本类 别有贡献，但这种贡献往往远小于考虑单词不出现情况所带来的干扰。 2 5 6 文本证据权 文本证据权( t h ew e i g h to fe v i d e n c ef o rt e x t ) 计算公式如下： 哪，= 军刮嵫 ( 2 1 6 ) 文本证据权是一种较新的评估函数，它衡量类的概率和给定特征时类的条件 概率之间的差别。当计算出来的函数值小时，说明词条对分类的影响小，应该被 去除。 2 5 7 几率比 几率比( o d d sr a t i o ) 计算公式如下： 1 6 第2 章文本分类的基础理论及相关技术 渊础删乩g 麓瑞( 2 ，7 )p ，z 曙八l p 川p d 刚) 式中p o s 表示目标类，n e g 表示非目标类。o d d sr a t i o 不像前面的特征选择 方法那样对所有类同等对待，而是只关心目标类值。这使得几率比这种特征选择 方法，特别适用于二元分类器。在二元分类中，我们希望能识别出尽可能多的正 类，而不关心识别出负类，这使几率比比其它信息测度有额外的优势。 2 5 8 特征选取方法的比较 诸多的学者对文本分类中的特征提取方法进行了试验比较和性能总结。单松 巍等( 2 0 0 3 ) 对主要的特征选取算法做了比较详细的介绍、试验比较和评价。根 据文献中的实验数据我们可以得出这样的结论，几种主要特征提取方法中c e 和 c h i 效果最好，在不损失分类准确率的情况下可以达到很高的降低维度作用。如 果保留1 0 左右的特征，d f 方法的效果可以和c e ，c h i 相比。在计算量太大的情 况下，d f 具有算法简单、质量高的优点，可以用d f 方法代替c e ，c h i ，在准确率 和效率之间达到一个很好的平衡，但是同被广泛接受的信息检索理论有些矛盾。 2 6 文本分类算法 研究文本自动分类的关键问题是如何构造分类器，分类器需要通过某种算法 进行学习获得。文本分类的算法大多来自于模式分类，基本上可以分为三大类： 一类是基于统计的方法，如中心向量法、朴素贝叶斯( n a i v eb a y e s ) 、k 近邻 ( k n n ) 、回归模型、支持向量机( s ) 、最大熵模型等方法：另一种是基于连接 的方法，如人工神经网络：还有一种是基于规则的方法，如决策树、关联规则等。 这些方法的主要区别在于规则获取的方式。 2 6 1 向量距离分类法 该方法的分类思路十分简单，根据算术平均值为每类文本集生成一个代表该 类的中心向量，然后在新文本来到时，确定新文本的向量，计算该向量与每类中 心向量问的距离( 相似度) ，最后判定文本属于哪个与文本距离最近的类，具体步 骤如下： 计算每类文本集的中心向量，即所有训练文本向量的简单算术平均。 新文本到来后，分词，将文本表示为特征向量。 计算新文本特征向量和每类中心向量间的相似度，公式为： 1