（计算机应用技术专业论文）利用非广延最大熵模型进行文本分类.pdf

摘要 在线资源的迅速增长、互联网信息量的急剧增加使得人们从信息匮乏的时代 过渡到了信息极为丰富的时代。面对日益膨胀的、异构的信息资源，如何快速、 准确地从海量信息中寻找到所需的相关内容变得十分棘手。因此，研究利用计算 机进行自动文本分类成为自然语言处理和人工智能领域中一项具有重要应用价 值的课题。目前文本分类领域中已经存在多种具有良好分类效果的理论技术，本 文主要介绍如何利用非广延熵模型进行文本分类。非广延熵模型建立在最大熵模 型的基础上，最大熵模型是一项概率分布估计技术，它的基本思想是拟合所有己 知事实，保持未知事件的未知状态，已被广泛应用于语言建模、词性标注、文本 分割等自然语言处理领域。 本文在最大熵模型的基础上提出了两个用于文本分类的扩展模型。第一个模 型利用非广延熵代替香农熵作为最大熵模型中的目标函数，以期简化分类器的表 达形式，称之为非广延熵模型；第二个模型在非广延熵模型的基础上引入实体间 的高阶约束，试图通过增加文本中单词间的共现关系约束提高文本分类的正确 率，称为带有高阶约束的非广延熵模型。成功建模后利用拉格朗日乘子法求解模 型，得到分类器的表达形式并进行参数估计，最终得到文本分类器。 本文选用2 0 作为语料库进行文本分类，并进行了两组分类器性newsgroups 能评价对比实验。第一组对比实验比较基于本文提出的两个扩展模型的文本分类 器，实验结果表明在非广延熵模型中添加高阶约束后文本分类的正确率有一定程 度的提高；第二组对比实验比较两个非广延熵模型和最大熵模型，实验结果表明 本文提出的两个扩展模型均具有更高的分类正确率。以上两组对比实验证实了非 广延熵模型和带有高阶约束的非广延熵模型的有效性。 关键词：非广延熵高阶约束文本分类 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fo n l i n er e s o u r c e s ，t h e r ea r em o r ea n dm o r e i n f o r m a t i o no nt h ew e b s i t e c o n s e q u e n t i a l l y , a u t oc l a s s i f i c a t i o nt e c h n i q u e sa r e r e q u i r e dt od i s c r i m i n a t eu s e f u li n f o r m a t i o na g a i n s tr e d u n d a n tu r g e n t l y f o rt e x t c l a s s i f i c a t i o n , t h e r ea r eav a r i e t yo f m a t u r et e c h n i q u e sw h i c hh a v eb e e nd e m o n s t r a t e d r e a s o n a b l ep e r f o r m a n c e s t h i sp a p e rp r o p o s e st h eu s eo fn o n e x t e n s i v ee n t r o p yf o r t e x tc l a s s i f i c a t i o n n o n e x t e n s i v ee n t r o p yt e c h n i q u ei sb a s e do nt h ep r i n c i p l eo f m a x i m u me n t r o p y m a x i m u me n t r o p yi sap r o b a b i l i t yd i s t r i b u t i o ne s t i m a t i o n t e c h n i q u ew i d e l yu s e df o rn a t u r a ll a n g u a g et a s k s ，s u c ha sl a n g u a g em o d e l i n g ， p a r t - o f - s p e e c ht a g g i n ga n dt e x ts e g m e n t a t i o n t h eu n d e r l y i n gp r i n c i p l eo fm a x i m u m e n t r o p yi s t h a tw i t h o u te x t e r n a lk n o w l e d g e ，o n es h o u l dp r e f e rd i s t r i b u t i o n st h a ta r e u n i f o r m t h i sp a p e rp r o p o s e st w on o n e x t e n s i v em o d e l sf o rt e x tc l a s s i f i c a t i o n t h ef i r s t m o d e le x t e n d ss h a n n o ne n t r o p yi n t on o n e x t e n s i v ee n t r o p yt os i m p l i f yt h ef o r mo f c l a s s i f i e r ；t h eo t h e ro n ei n t r o d u c e sh i g h - l e v e lc o n s t r a i n t si n t on o n - e x t e n s i v em o d e lt o i m p o s ec o n s t r a i n t s o nt h ep a i r so fe n t i t i e s m o d e lw i t h h i g h - l e v e lc o n s t r a i n t s c o n s t r u c t sr e l a t i o n sb e t w e e nw o r dp a i r sw h i c hb u i l d ss e m a n t i cc o n s t r a i n t s ，f o rt h e s a k eo fa d v a n c i n ga c c u r a c yo ft e x tc l a s s i f i c a t i o n t h en o n e x t e n s i v e e n t r o p y f o r m u l a t i o nh a sau n i q u es o l u t i o nw h i c hc a nb ef o u n db yl a g r a n g em u l t i p l i e rm e t h o d 他p a p e rs e l e c t s2 0 _ n e w s g r o u p sa se x p e r i m e n t a lc o r p u sa n dt w os e t so f c o n t r a s t i v ee x p e r i m e n t sa r eb a s e do n t h ec o r p u s i nt h ef i r s ts e to fc o n t r a s t i v e e x p e r i m e n t sw ec o m p a r et h ea c c u r a c yb e t w e e nt h et w op r o p o s e dm o d e l s ，r e s u l t s i n d i c a t et h a tt h em o d e lw i t hh i g h l e v e lc o n s t r a i n t sp e r f o r m sb e t t e rt h a nt h eo n e w i t h o u t i nt h es e c o n ds e to fc o n t r a s t i v ee x p e r i m e n t sw ec o m p a r ea c c u r a c yt o m a x i m u me n t r o p ya n ds h o wt h a tb o mt h em o d e l sp r o p o s e di nt h i sp a p e ra r ea l w a y s s i g n i f i c a n t l yb e t t e r e x p e r i m e n t s d e m o n s t r a t et h a tn o n - e x t e n s i v em o d e la n d n o n - e x t e n s i v em o d e lw i t hh i g h - l e v e lc o n s t r a i n t sa r eb o t hp r o m i s i n gt e c h n i q u e sf o r t e x tc l a s s i f i c a t i o n k e yw o r d s ：n o n e x t e n s i v ee n t r o p y , h i g h - l e v e lc o n s t r a i n t s ，t e x tc l a s s i f i c a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：彳寸霹奢 签字日期： 文d 。夕年6 月f 日 学位论文版权使用授权书 本学位论文作者完全了解鑫盗盘堂有关保留、使用学位论文的规定。 特授权苤盗盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：力寸磷卜 导师签名： 饭恕乏 签字日期：o l o o 尹年6 月 f 日 签字日期：吱d d 罗年6 月1 日 第一章绪论 1 1 项目背景及研究意义 1 1 1 项目背景 第一章绪论 随着i n t e m e t 应用的不断普及深入，在“网络摩尔定律”的支配下，互联网 信息量正以每1 0 0 天翻一番的速度增长，使人们从信息缺乏的时代过渡到了信息 极为丰富的时代。当今社会的信息突出表现为：信息量急剧增加，各种电子文本 形式所提供的信息量正以惊人的速度递增；信息结构更加复杂，互联网上包含的 信息以文本、图像、视频等多媒体格式存在；信息全球化，要求处理与传递信息 的速度加快。面对日益膨胀的、异构的信息资源，如何快速、准确地从浩瀚的信 息资源中寻找到所需的狭小领域内的相关内容就成了一个十分有意义的课题。正 是在这样的背景下，基于机器学习的文本分类正在逐渐成为一个日益重要昀研究 领域【4 3 1 ，特别是随着i n t e m e t 在线信息量的增加，文本分类显得越来越重要。 它对于有效共享网上资源、提高工作效率、更进一步地普及i n t e r n e t 等网络通信 都具有极其现实的意义。文本分类可以在较大程度上解决目前网上信息杂乱的现 象，方便用户准确定位所需的信息和分流信息，因此它已经成为一项具有较大使 用价值的关键技术，是组织和管理各类数据的有力手段。近年来，文本分类逐渐 与搜索引擎、信息推送、信息过滤等信息处理技术相结合，还可用于抽取符号知 识、新闻分发、排序电子邮件以及学习用户兴趣等领域中，有效地提高了信息服 务的质量，是信息检索、机器翻译、自动文摘、信息过滤等技术的基础。 1 1 2 研究意义 因特网是全球规模最大的信息源基地，但因特网中信息种类繁多、良莠不齐， 如果没有简洁有效的算法做基础，高速有效的文件组织结构做铺垫，在浩瀚无边 的信息海洋中迅速准确地获取用户需要的信息是不可能实现的。目前互联网上的 绝大部分海量信息仍以文本形式存在，在这种隋况下，文本聚类、分类算法及相 关的技术越来越受到研究人员的青睐与关注。 文本分类其实也是一种文献检索的手段，与普通的文本检索不同的是文本分 类技术预先设定了一个类别集合，对于待检索的文本，根据一定的判别法则，判 断该文本是否属于这个集合中的某个类。文本分类技术在文本检索、信息过滤、 第一章绪论 数据组织、符号知识抽取、新闻发布、排序电子邮件、学习用户兴趣等方面都具 有相当有意义的实际应用价值【2 1 。下面简单举几个文本分类应用的例子： 1 提高信息检索精度：在信息检索过程中，利用文本分类对检索结果进行过滤， 剔除掉无关的文本信息，提高检索准确率； 2 图书馆文本资料管理：图书馆的整个索引系统都建立在文本分类的基础之 上，方便使用； 3 电子邮件的层次分类：可以为电子邮件分类省去大量的人力物力； 4 语料库学的发展：随着电子出版业的迅速发展，获取大量的电子文本从而建 立大规模语料库已经成为可能，但语料的处理速度却落后于语料的收集速 度。如果对收集来的语料进行自动文本分类，则会大大加快语料的处理速度。 1 2 文本分类国内外现状 1 2 1 国际研究概况 国际上在文本分类技术及相关的信息检索、信息抽取等领域起步较早，进行 了较为深入的研究并开发了一系列可用的分类系统，例如分别针对新闻稿件、网 页和电子邮件的自动文本分类器等。至今在信息处理的很多领域都已经取得了突 破性的进展，并为文本分类效果的不断提升奠定了基础： 1 文本信息表示模型 s a l t o n 等人在6 0 年代末提出的向量空间模型( v e c t o rs p a c em o d e l ，v s m ) t 3 】 在文本分类、自动索引、信息检索等领域得到了广泛的应用，已经成为最简便最 高效的文本表示模型之一，并被很多商业搜索引擎采用；随着自然语言处理研究 的不断深入，概率语言模型( p r o b a b i l i s t i cl a n g u a g em o d e l ，p l m ) 也被逐渐应用到 索引技术、信息检索领域f 4 】。 2 特征选择方法 在使用向量空间模型表示文本信息时，为了降低向量维度和计算时间复杂 度，通常采用特征选择的方法对文本中的词条进行筛选，从而过滤对于充当句法 成分无意义的以及信息区分能力弱的词条。国际上已经提出多种行之有效的基于 信息学和统计学的方法【5 1 ，这些方法主要包括：文本频率( d o c u m e n t f r e q u e n c y ， d f ) 、信息增益( i n f o r m a t i o ng a i n ，i g ) 、互信，息( m u m a li n f o r m a t i o n ，m i ) 、期望交 叉熵( e x p e c t e dc r o s se n t r o p y ) 及词条强度( t e r m ss t r e n g t h ，t s ) 等。 3 文本分类方法 近些年，很多理论技术被应用到该领域，主要包括：朴素贝叶斯( n a f v eb a y e s ， 2 第一章绪论 n b ) 【6 1 、支持 置7 j l ( s u p p o r tv e c t o rm a c h i n e ，s v m ) 7 1 、k - 2 近# g ( kn e a r e s tn e i g h b o r ， k n n ) t 引、神经网络模型( n e u r a ln e t w o r k ，n n ) t 9 1 、决策树模型( d e c i s i o nt r e e ， d t ) 【1 0 】、最大熵模型( m a x i m u me n t r o p y ，m e ) r 1 5 1 以及线性最小平方拟合( l i n e a r l e a s ts q u a r e sf i t ，l l s f ) o l 】等。许多学者对这几种文本分类方法进行了大量的对 比研究，结果表明结合不同的分类器能够提高分类的精度。 4 测试语料库及评测方法 国际上对于英文文本分类语料制定了一些规则完善、标准统一的语料集。 2 0 _ n e w s g r o u p s ( 1 9 9 9 7 篇文章2 0 + 类另t j ) t 4 5 1 、w e b k b ( 4 1 9 9 篇文章7 个类别) f 4 5 】、 r e u t e r s 系列语料库( 2 1 5 7 8 篇文章1 3 5 个类别) ( 4 6 】都曾得到较为广泛的应用， t r e c t 4 7 】也提供了较为标准的语料库。 在系统性能测评方面，l e w i s 给出了一套较完整的分析方浏呓】，不但可以测 试系统的整体性能，而且可以较科学地分析训练文本充足和训练文本不足时的分 类性能差异。 5 半监督( s e m i s u p e r v i s e d ) 的机器学习方法 收集及分类训练文本是极其费时、费力的过程，因此有学者提出了在训练文 本不足的情况下利用未标记文本提高分类系统性能的方法，将文本分类和聚类有 机结合起来。 1 2 2 国内研究概况 国内的研究起步较晚，相对比较落后，但是近些年来很多研究学者都做了大 量的努力，使得文本分类这一技术在国内的发展日益成熟和完善，特别是中文分 词技术的准确率不断提升，使得大规模的中文文本处理成为可能。但目前仍然存 在一些问题： 1 仍缺少统一的中文语料库，各个研究者收集自己的训练文本集，并在此基础 上开展研究，因此系统的性能可比性不刮1 3 】。同时由于人力财力有限，中文 语料库的规模普遍不大； 2 由于汉语言在词义、句法和语法等概念上与英文相比存在较大差异，这就要 求要充分考虑词义消歧【1 4 】和词间予以概念对分类系统的影响； 3 中文分类技术与其他信息技术还未充分结合。国内的文本分类系统主要应用 于图书馆等专业信息处理机构。在信息服务领域，除了与搜索引擎有所结合 外，文本分类技术与其他信息技术还没有很好的结合，没有得到充分的应用。 第章绪论 1 3 本文的研究内容及论文结构 1 3 1 论文研究内容 本文所作的工作主要如下： 1 介绍文本分类、最大熵模型及其原理、特征选择和参数估计算法。 2 模型扩展：将最大熵模型扩展到非广延熵领域并建立非广延熵模型，以 期简化文本分类器的形式；在已扩展的非广延熵模型中添加高阶约束，试图通过 建立文本中词对问的共现关系约束提高分类正确率。 3 模型求解：求解在文本分类领域中建立的两个扩展模型。首先利用训练 文本得到分类器的表达形式，通过参数估计得到分类器表达式中的相关参数，从 而得到文本分类器：其次利用分类器对测试文本进行类别预测，计算分类器的正 确率；最后评估分类器的性能，对比两个模型的分类性能，并和基于最大熵模型 的分类器进行对比实验。 1 3 2 论文结构安排 依据本论文的研究内容，安排论文结构如下： 第一章绪论，介绍文本分类的研究背景和目的及其研究现状。 第二章相关概念综述，简要介绍文本分类的概念和流程，介绍熵的概念、 最大熵原理及应用于文本分类的最大熵模型。 第三章介绍非广延熵模型，将最大熵模型中的香农熵扩展到非广延熵，建 模应用于文本分类的非广延熵模型，通过模型求解得到文本分类器。简要介绍非 广延熵的概念和性质，详述非广延熵模型的建模过程，如文本预处理、特征生成、 约束建立、模型建立、模型求解、参数估计等。 第四章提出带有高阶约束的非广延熵模型，在非广延熵模型的基础上引入 文本中词对间的共现关系约束，以期通过增加约束条件提高文本分类的正确率。 详述高阶约束的意义和表达形式，约束建立、模型建立、模型求解以及参数估计 过程。 第五章评估分类器性能，选定语料库后，通过训练得到文本分类器，并对 测试文本进行类别划分，由此得到分类器的正确率。对比两个扩展模型的实验结 果可以发现，通过增加词对间的共现约束可以提高文本分类的正确率；在两个扩 展模型和最大熵模型间进行对比实验，结果表明本文提出的两个扩展模型具有更 高的分类正确率。 第六章结束语，对文本研究工作的总结和对未来研究方向的计划和展望。 4 第二章相关概念综述 第二章相关概念综述 本章主要介绍利用最大熵模型进行文本分类时所涉及到的几个基本概念。一 是文本分类，简要介绍文本分类的概念和流程；二是熵的概念，主要介绍香农熵 和条件熵；三是给出基于香农熵的最大熵模型、最大条件熵模型以及应用于文本 分类的最大条件熵模型。 2 1 文本分类简述 2 1 1 问题描述 文本自动分类是数值分类学和信息处理技术相结合的研究方向。在最初的分 类学中，人们往往通过专业知识和经验对事物进行定性分析，很少使用数学工具。 但随着信息的不断增长，信息间的关系也日益复杂，导致分类程度越来越细、分 类规模越来越大。这时仅仅依靠定性分析无法满足要求，于是在分类中引入了数 学工具，使用统计、人工智能等各种方法处理信息，从而形成了数值分类学，大 大推动了信息处理技术前进的步伐。 简单的说，文本分类系统的任务是：在给定分类系统下，根据文本的内容或 属性，将大量的文本归属到一个或多个类别中【啦】。从数学角度来看，文本分类 是一个映射过程，它将未分类的文本映射到已有类别。由于一篇文本可以和多个 类别关联，因此该映射可以是一一映射也可以是一对多映射，用数学公式表示如 下： 卜d - - 9 , c 其中d = f d , ，皿，见) ，c = ( g ，c 2 ，c m ) ，d 是待分类文本集合，c 是类 别集合。d 可以是无限集合，但c 必须为有限集合。 文本分类的映射规则厂是文本分类系统的关键，它是系统根据训练样本的内 容或属性信息总结出的分类规律，用来建立判别公式和判别规则。对于待分类文 本，根据从训练文本中得到的文本分类映射规则，确定该文本的类别。 5 第一章相关概念综述 2 1 2 文本分类流程 文本分类的流程如图2 1 所示，由文本预处理、特征选择、分类器训练和测 试评估四个主要模块构成文本分类系统。在分类过程中，选择特征、训练分类器 和评估分类器性能构成一个循环，在每次循环中根据测试结果调整所选择的特征 和分类训练的参数，使得分类器具有更佳的分类性能。 图2 1 文本分类系统流程图 从图2 1 中可以看出，文本分类需要解决以下五个问题： 1 获取训练文本和测试文本 2 文本预处理 3 特征选择方法 4 求解分类器模型 5 系统性能评测 2 1 2 1 文本集合的选取 训练文本集的选择是否合适对文本分类器的性能有较大影响。如果训练文本 和测试文本集的分布存在很大差异，就很难保证良好的分类结果，特别是对于训 练样本很少的情况【1 5 】，因此训练文本集应该能够广泛代表分类系统所要处理的各 个类别中的文本。一般来说，训练文本集应该是公认的经人工分类的语料库，而 且各个类别所包含的训练文本应保持数量上的基本一致，这样训练得到的分类器 不会对某些文本类产生估计偏差。 6 第二章相关概念综述 2 1 2 2 文本预处理 预处理模块是文本分类的基础部分。通过文本预处理，将文本转化为计算机 可以读取和识别的矢量信息。 常用的一种文本表示方法是向量空间模型v s m ( v e c t o rs p a c em o d e l ) t 3 1 ，在该 模型中文本被表示成为由词条构成的向量形式。通常将一个文本集合表示成“词 条一文本”矩阵，矩阵中的每一个元素表示某一词条在一篇文本中的出现情况。 由于并不是所有的词条都会均匀出现在每个文本中，因此矩阵往往是一个稀疏矩 阵。矩阵的行数对应于词典的词条数，而列数则对应于训练集文本。词条数有可 能会非常大，因此特征空间庞大的维度也是文本分类问题的个特点和难点。在 文本分类中，特征词的权值计算方法主要有：t f i d f 法 1 6 a 1 、t f c 法和l t c 权 值法1 1 7 】，本文选用t f i d f 权值法进行文本表示。 t f i d f 权值法是信息检索领域中最经典的一种词条权值计算方法。词条的 权值正比于它在文本中的出现频率t f ( t e r mf r e q u e n c y ) ，反比于它在整个文本集 合中的出现频率i d f ( i n v e r s ed o c u m e n tf r e q u e n c y ) 。i d f 算法的核心思想是，在 大多数文本中都出现的特征项不如只在小部分文本中出现的特征项重要。i d f 算 法能弱化一些在大多数文本中都出现的高频特征项的重要程度，同时增强一些只 在小部分文本中出现的低频特征项的重要度。t f i d f 权值法的计算公式为： 矿帆= 删。g ( 期 其中代表整个文本集中的文本数，刀是包含该词条的文本数，以是该词 条在该文本中的出现频率。 2 123 特征选择方法 语言是一个开放的系统，作为语言的一种，书面化或电子化的文本也是开放 的，其大小、结构以及包含的语言信息也都是开放的。目前的文本分类方法和系 统都采用词和词组作为表征文本语义的属性，文本特征的提取一般通过对文本的 多遍扫描实现，但是得到的特征向量维数往往很高，这样就会增加信息处理的时 间复杂度。所有特征对于文本分类的意义是不同的，些通用的、各个类别都普 遍存在的词汇对分类没有贡献；只有那些在某个特定类中出现比重大而在其他类 中出现比重小的词汇才对文本分类有大的贡献。为了提高分类的精度，应去除那 些类别区分能力不强的特征，筛选出针对每一类的特征项集合。因此在不影响分 类结果的前提下，需要进行特征子集的选取，即特征选择。文本分类系统应尽可 能地精简特征的数量，选择与文本主题密切相关的特征作为分类的依据。其方法 7 第_ 章相关概念综述 一般是构造一个评价函数，对特征集中的特征进行评价，然后从中选取评价较高 的一组特征作为特征子集。 常用的特征选择方法有： 1 ) 基于阈值的统计方法：文本频率方法( d f ) 、信息增益方法( 1 g ) 、互信息方 法( ) 、z 统计方法【1 1 】、期望交叉熵、文本证据权、优势纠1 7 】； 2 1 基于词频覆盖度的特征选择方法： 3 ) 由原始的低级特征( 比如词) 经过某种变换构建正交空间中的新特征选 择法，如主分量分析方法等。 2 1 2 4 分类器模型 分类器的设计和实现是文本分类系统的核心。目前比较成熟的分类技术基本 都属于统计学习理论的范畴。在机器学习领域，分类和回归都可用于预测。预测 的目的是利用历史数据记录自动推导出对给定数据的推广模式描述，从而能对未 来数据进行预测。在文本分类的机器学习过程中，关键的问题是如何让计算机将 未分类文本正确地归入相应的类别。目前存在多种基于向量空间模型的文本分类 算法，主要有以下几种： 1 ) 类中心分类法( r o e c h i o ) 2 ) 朴素贝叶斯( n a i v eb a y e s ) 3 ) k 最邻近方法( k - n e a r e s tn e i g h b o r ) 4 ) 支持向量机( s u p p o r tv e c t o rm a c h i n e ) 5 ) 决策树模型( d e c i s i o nt r e e ) 6 ) 线性最小平方拟合映射( l i n e a rl e a s t s q u a r ef i t ) 7 ) 神经网络模型( n e u r a ln e t w o r k ) 8 ) 最大熵模型( m a x i m u me n t r o p y ) 目前为止，很多学者都偏向于使用n a i v eb a y e s 、k n n 、s v m 这几种相对比 较成熟的方法进行文本分类，也有大量学者对这几种方法进行了对比实验，结果 表明s v m 的分类性能偏好于k n n 和n a i v eb a y e s ，但是对于多分类来说，s v m 的运行时间较长【2 3 1 。利用最大熵模型( m a x i m u me n t r o p ym o d e l ) 进行文本分类的 研究相对较少。本文利用最大熵模型的基本思想，在文本分类过程中改进和扩展 模型，试图提高分类器的性能和效率。 2 1 2 5 确定性能评估指标 比较不同分类模型之间的性能是科研的重要任务之一，由于不同的分类器有 不同的本质特点，对文本分类系统主要有三种评价或比较尺度：( 1 ) 模型有效性； 第二章相关概念综述 ( 2 ) 计算复杂度：( 3 ) 模型描述的简洁度。模型有效性是使用最多的一种比较尺度。 计算复杂度依赖于具体的实现细节和硬件环境，文本的操作对象是海量文本数据 库，因此空间和时间的复杂度问题将是非常重要的因素。模型描述越简洁越受欢 迎。三个方面中，有效性最为重要，因为不管分类器的速度多快、占用空间多少、 算法多简便，如果它不能正确分类，这个分类器就是没有用的，因此对于分类结 果的评价主要指有效性的评价。 评价分类结果有效性主要有三个指标：精确度( p r e c i s i o n ) 、召回率( r e c a l l ) 和 f 测量值( f - m e a s u r e ) ，这几个术语均来源于信息检索领域。 对于一个类别和每一篇文本而言，分类器决定该文本是否属于这一类别，我 们对每个类别的四个关键性指标进行统计： a 正确分配到该类别的文本数量；b 错误分配到该类别的文本数量； c 错误拒绝到该类别的文本数量；d 正确拒绝到该类别的文本数量。 根据这四个指标，定义文本分类器性能的评测标准： r e c a l l ( 召回率) = 兰 a+c p r e c i s i 0 1 1 ( 精确率) ：三 a+d 口例朋缈( 正确率) = i 忑a 再+ i d 砑 啪，( 错误率) = i 琵b i + i c 万 公式( 2 - 3 ) 公式( 2 - 4 ) 公式( 2 - 5 ) f 测量伊m e a s u r e ) 精确率和召回率是两个相互矛盾的衡量指标，一般情况 下，精确率会随着召回率的升高而降低，所以很多情况下需要将它们综合在一起 考虑。最常用的办法就是f 测量，定义如下： 乃= 篇篙罴字 馘7 ， 其中是一个调整参数，用于以不同权重综合精确率和召回率。当= 1 时， 表示精确率和召回率被平等地对待，此时f 测量值又被称为只。 分类方法的综合评价上面提到的精确率、召回率及只方法都是针对单个类 别的分类情况而言的。当需要评价某个分类器性能时，还需要将所有类别的结果 综合起来，通常有两种方法：宏平均( m a c r o a v e r a g i n g ) 和微平均( m i c r o a v e r a g i n g ) 。 前者首先得到每个类别的p r e c i s i o n 和r e c a l l 结果，然后在所有类别上得到一个平 均结果作为宏平均结果指标。后者则不考虑个体类别，而是在整个文本集合上统 计p r e c i s i o n 和r e c a l l 指标作为其输出结果。从定义中可以看出，不管类别的大小， 9 第二章相关概念综述 宏平均对所有类别的结果都平等对待，所以任何个类的变动都可能对宏平均造 成较大的影响。相对而言，微平均则平等对待每篇文本。本文采用正确率作为 评价指数评估分类器的性能。 2 2 熵的概念 2 2 1 信息熵 熵的概念源自热物理学。1 9 4 8 年香农提出的“信息熵”概念解决了信息的 量化度量问题，因此信息熵又称为“香农熵”。信息熵是一个数学上颇为抽象的 概念，在这里不妨把它理解成某种特定信息的出现概率( 离散随机事件的出现概 率) 。一个系统越是有序，信息熵就越低；反之系统越混乱，信息熵就越高。信 息熵也可以说是系统有序化程度的一个度量。 定义1 ：对于一个数据集合中的某属性x ，设它的属性域为 五，x 2 ， ， 对应的概率分布为 p ( x 1 ) ，烈而) ，烈_ ) ，则x 的熵定义为： j l 日( 兰一p ( x ，) l o g p ( x , ) 公式( 2 8 ) 从熵的定义可以看出，熵是关于属性值概率分布的函数，它用一个非负实数 描述属性取值的不确定程度，是一个全局度量。在信息论中，熵通常作为某信源 所蕴含信息量的度量，表达属性彳所包含的信息量。就属性肖而言，熵可以用 来衡量该属性的纯度，一个属性的熵值越小，表明数据在该属性域上的分布越不 均匀。比如属于某个属性值的数据较多，而属于其他属性值的数据较少，那么这 个数据集合越纯，相应的熵值就越小。如果一个属性的所有数据都属于同一个属 性值，则该属性的熵值为0 ，它所包含的信息量也为0 ，即该属性在数据集合中 不存在对数据有用的信息。反之，一个属性的熵值越大，说明数据在该属性域上 的分布越均匀，那么这个属性也就越不纯。例如，属性x 中的数据在属性域上 服从均匀分布，则该属性的熵值最大，所蕴含的信息也就最多。 从公式( 2 8 ) 可知h 是a ，p 2 ，见的, 元函数，其中a + 岛+ + 见= 1 ，从 中可以看出熵具有以下性质： 对称性：h ( p l ，p 2 ，见) = h ( p 2 ，局，以) = = 日( 见，见1 ，a ) 非负性：何( a ，p 2 ，见) 0 加法性：若随机变量彼此独立，则它们的联合熵h ( x ，n = h ( x ) + 日( 即 极值性：日( n ，p 2 ，只，) 日( 1 ”1 刀，1 n ) = n l o g n 1 0 第二章相关概念综述 扩展性：( a ，p 2 ，见) = l 。i 训r a h ( p i ，1 2 ，以，以+ 1 ) ，其中l = f ，6 - - + 0 上凸性：h ( t x + ( 1 一a ) 即 a h ( x ) + ( 1 一五) 日( y ) ，其中0 a 表示x 上的概率分布，x x 。已知 a ) 的数字特征满 足如下的一组约束： ，以巧( x ) = 匆 1 i 力 公式( 2 1 1 ) 其中z ) 为特征函数。 得到约束条件后，将公式( 2 8 ) 作为模型中的目标函数建立起基于香农熵的最 大熵模型： a r g r a i n p 。l o g p x 旺 以霉( 石) = 6 i = 1 ，2 ，刀 以= 1 工石 p 。0 工x 该模型中的目标函数是凹函数，约束条件均为线性约束，因此它是一个典型 的凸规划问题。利用拉格朗日乘子法求解该模型，首先定义拉格朗日函数( 忽略 归一化条件p 。= l ，该条件转化为得到待求变量后的统一归一化处理) ： f ( p ，力) = 见l o g p x 一乃( 见互( x ) 一6 f ) 公式( 2 1 2 ) ，fj 公式( 2 1 2 ) 中左边的p 表示概率分布 只) ，五表示拉格朗日系数集合 丑 。 由求得极值的必要条件： o ：要- 1 + l o g p ，, - 塬x ) 公式( 2 - 1 3 ) 蛾_ 得到 1 2 第二章相关概念综述 见= 三e x p ( ；硼砌 公式( 2 小) 其中z 是归一化因子，z = z e x p ( e 以l ( x ) ) 。 2 3 2 基于香农熵的最大条件熵模型 该小节介绍以机器翻译任务为背景导出的最大条件熵模型。设源文本的词项 集合为s ，目标文本( 即译文) 的词项集合为r ，以x 和y 分别表示s 和r 中的 元素，；( x ，y ) 是源词项集合和目标词项集的联合经验分布，；( 工) 是源词项集的 经验边际分布，互( x ，y ) 表示形式化约束的特征函数，如下定义；( z ) 和p ( z ) ： ；( z ) 量；( x ，y ) z ( x ，y ) j ，y p ( z ) 兰弓( x ) p ( j ，ix ) z ( x ，y ) j y 公式( 2 - 1 5 ) 公式( 2 - 1 6 ) 这里；( z ) 和p ( z ) 可分别理解为经验分布和真实分布上的某个数字特征( 统 计量) 。由条件熵的定义， p ( y i x ) 的条件熵可由公式( 2 1 7 ) 近似： 日( p ) = ；( x ) p ( y i 工) l o g p ( 少lz ) 公式( 2 1 7 ) x 最大条件熵模型在满足特定约束的前提下，求解使得熵值取得最大的概率分 布 p ( y i x ) ，模型如下： a r g r a i n , p ( x ) p ( y x ) l o g p ( yi x ) i p t y l o j j j y j j p ( 巧) = p ( z )i = l ，乏：“，k p ( y i 工) = 1 工s y p 0 i x ) 0石s ，y r 利用拉格朗日乘子法求解最大条件熵模型，得到建立在最大条件熵模型上的 概率分布的解的形式： p ( y = 南唧( 莩槲w ) ) 公式( 2 - 1 8 ) 其中z ( z ) 是归一化因子，z ( x ) = e x p ( 乃巧( x ，y ) ) 。 1 3 第二章相关概念综述 2 3 3 应用于文本分类的最大条件熵模型 对于文本分类来说，待求的是测试文本的类别，类别信息需要利用分类器进 行预测。因此，得到高效率、高性能的文本分类器是文本分类的关键，在分类器 的训练过程中，特征选择和参数估计具有决定性作用。利用最大熵进行文本分类 主要包括以下几个步骤：文本预处理、特征选择、约束生成、模型建立、参数估 计、性能评估 1 9 , 2 3 。下面分别介绍这几个步骤，首先进行符号设定。 2 331 符号设定 d ：训练文本集 d ：文本，d d c ：文本的类别集合 c ：类别，c c 形：文本中的单词集合 w ：单词，w 形 p ：先验概率， p ( c ld ) ：文本d 属于类别c 的概率值 2 3 3 2 特征选择 特征函数是从训练文本中获得的可以有效表达文本统计信息的函数，它可以 是任意的实值函数【4 2 】。在最大熵模型中，一般利用词频信息来表示特征函数【1 9 1 。 利用词频表达的特征函数为： f 0 矿c c 丘，( c , d ) 2 坐塑d t h e 眦p 公式( 2 。1 9 ) i ( d ) 其中n ( d ，们是单词w 在文本d 中的出现次数，n ( d ) 是文本d 的总词数。 在训练文本中，首先过滤停用词，计算非停用词的词频并将其作为特征函数 运用于文本分类中。本文采用归一化的词频信息表达特征函数，可以避免因文本 长度不同而带来的不便。 2 3 3 3 约束生成 设；( c ，d ) 是文本集合和类别集合的联合经验分布，；( d ) 是文本集合的经验 边际分布，利用已经得到的特征函数，如下定义；( z ) 和p ( z ) ： ；何) 暑；( c ，d ) z ( f ，d ) 公式( 2 2 0 ) c d 1 4 第章相关概念综述 p u ) 兰；( d ) p id ) z ( c ，d ) 公式( 2 2 1 ) c d ；( c ，们，( f ，d ) 表示某个特征函数彳在训练文本中对于经验概率分布的期 望值；( d ) p ( f i d ) z ( c ，d ) 是对应的z 对于模型p ( c l d ) 的期望值。 c d 通过在这两者间建立等式约束关系，从而建立起训练文本中已分类训练文本 和待分类测试文本间特征函数期望值的等式约束【”，2 3 1 。由于可以在训练文本中选 择多个特征函数，就可以在训练文本和测试文本间建立起多个等式约束。等式约 束可表达为： ；( c ，d ) ，( c ，d ) = ；( d ) p oi 力z ，d ) 公式( 2 2 2 ) c ，dc d 约束p ( cd ) = 1 和p ( cd ) o 用来保证p ( c id ) 的概率分布特性。 2 3 3 4 模型建立 。 文本分类中需要用到条件熵的概念，综合条件熵以及以上两组约束条件，应 用于文本分类的最大熵模型可表达为： a r g m i n ；( d ) p ( c l d ) l o g p ( c i d ) i p l c l a ) jc d s ep ( c ，d ) ，( c ，d ) = ；( d ) p ( cj ) ，( c ，d ) c ，dc 。d p ( c l d ) = 1 de d p ( c l d ) 0 d d ，c c 2 3 3 5 参数估计 利用拉格朗日乘子法求解该优化模型，将带约束的优化问题转化为无约束优 化问题，得到p ( c id ) 的表达形式： e x p ( z 4 f , ( c ，力) p ( c i d ) = 之万一 公式2 。2 3 其中z ( 力是归一化因子，z ( d ) = e x p ( 4 f , ( c ，d ) ) 。 ci 得到p ( c id ) 的表达形式后，利用g i s ( g e n e r a li t e r a t i v es c a l i n g ) 法 2 1 1 或者 i i s ( i m p r o v e di t e r a t i v es c a l i n g ) 法1 2 0 1 对模型进行参数估计， 至up ( c ic o 中各个特征 函数所对应的a 值后，带a p ( c i d ) 的表达式，得到文本分类器。 第三章非广延最大熵模型 第三章非广延最大熵模型 基于朴素最大熵模型的分类器是指数形式的，为了简化分类器的表达形式， 本文将最大熵模型中的目标函数由香农熵扩展为非广延熵，并由此建立非广延