（模式识别与智能系统专业论文）快速图像文档分类的研究.pdf

独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均己在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：翌煎 日期： 知吐、午二g - 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：至煎 日期： 塑皇：生_ = 至 导师签名 霉孳 北京邮电大学学位论文 快速图像文档分类的研究 捅要 计算机技术、多媒体技术以及i n t e r n e t 技术的飞速发展产生大量的图像信息。 纸制的图书、报刊杂志在存放上受时间、环境的影响比较严重，人们越来越倾向 于将图书、报刊杂志等资料用图像的形式存储起来，于是数字图书馆出现了。数 字图书馆使人们不出家门即可浏览图书资料，与此同时，如此大量的图像文档使 人们查找起来难度加大了。因此如何有效地、快速地从大规模的图像文档库中查 找出需要的图像文档是目前一个急需解决的重要问题。 目前，文本文档分类研究的比较多。而对于图像文档分类一般是利用o c r 技术先将其识别成文本文档，再利用文本文档的分类方法进行分类。由于分类的 图像文档的数量非常巨大，要处理这样的海量信息速度问题是个关键。现有的图 像文档分类，因为引入了o c r 技术，使得复杂度大大增加，耗时比较多，难以 满足快速分类的需要。 本文主要研究脱离o c r 技术的图像文档分类技术，以提高系统的运行效率。 为了达到这个目的，具体探讨了如何提取汉字图像的特征、如何提取图像文档的 特征、如何建立图像文档模型以及采用何种相似度等方面的问题。本文主要采用 了笔划密度编码的方法提取汉字图像特征，采用n g r a m 模型表示图像文档，在 图像文档分类方法上使用了最邻近分类方法，在相似度计算方面采用了传统的余 弦度量方法。这种方法使图像文档的分类脱离了o c r 技术，因而大大提高了系 统的运行效率。尽管分类精度有所降低，但满足了特定场合下的网络图像文档分 类的要求。 本文的内容主要由以下几个方面组成： l 、介绍了现有文档分类技术：首先介绍了特征提取方法和文本分类方法， 并对各类方法进行了分析和比较；接下来介绍了几种常用的计算文档间距离的方 法；最后介绍了两种文档的表示方法：空间向量模型方法和n g r a m 模型。 2 、开发了建立图像文档数据库的两个软件工具：文档一图像转换工具和汉 字图像处理工具。使用这种工具，首先可以将文本文档中的每个汉字转换为图像 形式，使后续的研究可以直接在单个汉字图像上进行，省去了图像文档中汉字切 分的步骤，从而避免了因为汉字切分错误而带来的误差：其次可以方便的将文本 文档转换为图像文档，为创建图像文档数据库提供了方便：最后可以根据自己的 需要对图像文档进行各种处理，例如可以通过程序加入噪声来模拟真实的情况。 3 、提出了使用笔划密度编码提取汉字图像特征、n - g r a m 模型表示文档、使 用最邻近分类方法进行文档分类及采用余弦公式计算文档间距离的快速图像文 北京邮电大学学位论文 档分类方法。对系统实现、实验数据进行了描述，对实验数据进行了分析。实验 结果表明这种图像文档分类方法是有效的。 4 、最后给出了总结及对后续工作的展望。 关键字 图像文档分类特征提取笔划密度编码图像文档模型n - g r a m 模型相似度计算 北京邮电大学学位论文 h i g hs p e e dd o c u m e n ti m a g ec l a s s i f i c a t l o n a b s t r a c t t h er a p i dd e v e l o p m e n to fc o m p u t e r , m u l t i m e d i aa n d1 n t e m e tt e c h n i q u e sh a s p r o d u c e dv e r yl a r g ea m o u n to fi m a g e t h eb o o k ，n e w s p a p e ra n dm a g a z i n ea r en o t e a s i l ys t o r e df o ral o n gt i m eb e c a u s et h ep a p e rw i l lb er o t t e di fi ti ss t o r e df o ral o n g t i m eo ri nab a de n v i r o n m e n t s ot h eb o o k ，n e w s p a p e ra n dm a g a z i n ea r es t o r e di n c o m p u t e ra n da r ec o n v e n e di n t oi m a g e t h u si tc o m e sal o to fd i g i t a ll i b r a r i e s p e o p l e c a r ls c a ni n f o r m a t i o nw i t h o u tg o i n go u tb yu s eo fd i s t a ll i b r a r y a tt h es a m et i m e ，i ti s d i f f i c u l tt oc l a s s i f yt h e s ed o c u m e n ti m a g e s i ti sap r o b l e mt ob es o l v e dt h a th o wt o c l a s s i f yt h e s ed o c u m e n ti m a g e se f f i c i e n t l ya n df a s t n o w , t h er e s e a r c ho fd o c u m e n tc l a s s i f i c a t i o ni sd o n eal o t t h ed o c u m e n ti m a g e c l a s s i f i c a t i o nu s u a l l yu s e so c rt e c h n o l o g yt oc o n v e r tt h ed o c u m e n ti m a g ei n t o d o c u m e n t w ec l a s s i f yt h ed o c u m e n tj u s ta st h ed o c u m e n tc l a s s i f i c a t i o n b e c a u s eo f t h el a r g ea m o u n to fd o c u m e n ti m a g e ，i ti sav e r yi m p o r t a n tp r o b l e mt op r o c e s ss o m u c hi n f o r m a t i o n b yu s i n go c rt e c h n o l o g y , t h ed o c u m e n ti m a g ec l a s s i f i c a t i o ni s m o r ec o m p l e xa n dn e e d sm o r et i m e i ti sn o tm e tt h ec l a s s i f i c a t i o nr e q u i r eo f f a s t i nt h i sa r t i c l e ，w er e s e a r c hh o wt o c l a s s i f yd o c u m e n ti m a g ew i t h o u to c r t e c h n o l o g y f o rt h i sp u r p o s e ，w ed i s c u s sh o wt oe x t r a c tt h ef e a t u r eo fd o c u m e n t i m a g e ，h o wt oe x p r e s st h ed o c u m e n ti m a g em o d e la n dh o wt o c a l c u l a t et h e c o m p a r a b i l i t y w ei n t r o d u c et h es t r o k ed e n s i t yc o d em e t h o dt oe x t r a c tt h ef e a t u r e ， n - g r a mm o d e lt oe x p r e s st h ed o c u m e n ti m a g em o d e l ，a n du s en e a r e s tn e i g h b o r m e t h o df o rd o c u m e n ti m a g ec l a s s i f i c a t i o na n dt h ec o s i n em e a s u r e m e n tt oc a l c u l a t e t h ec o m p a r a b i l i t y b yu s i n gt h i sm e t h o d ，w ec a nc l a s s i f yd o c u m e n ti m a g ew i t h o u t o c rt e c h n o l o g y s ot h ee f f i c i e n c yo f t h es y s t e mi si m p r o v e do b v i o u s l y a l t h o u g ht h e p r e c i s i o no fc l a s s i f i c a t i o ni sd e p r e s s e d ，i tc a nm e e tt h er e q u i r e m e n to fn e t w o r k d o c u m e n ti m a g ec l a s s i f i c a t i o ni ns o m es p e c i a ls i t u a t i o n t h ec o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r ea sf o l l o w s ： 1 t h ec o n t r i b u t i o n si n t r o d u c et h et e c h n o l o g yo fd o c u m e n tc l a s s i f i c a t i o nb r i e f l y ： f i r s t l y , w ei n t r o d u c ef e a t u r ee x t r a c t i o nf r o md o c u m e n ta n dd o c u m e n tc l a s s i f i c a f t o n 3 北京邮电大学学位论文 m e t h o da n da n a l y z et h e i ra d v a n t a g ea n dd i s a d v a n t a g e ；n e x tw ei n t r o d u c e d o c u m e n td i s t a n c ec a l c u l a t i o nm e t h o d ；a tl a s t , w ei n t r o d u c et w od o c u m e n t e x p r e s s i o nm e t h o d - - v e c t o rs p a c em o ( 1 e la n dn g r a mm e t h o dw h i c hi su s e di n t h i sp a p e r 2 t h e n ，w ed e v e l o p e dt w os o f t w a r et o o l sf o rc o n s t r u c t i n gd o c u m e n ti m a g ed a t a b a s e o n ei sd o c u m e n t - i m a g et r a n s f o r m ；t h eo t h e ri sc h i n e s ei m a g eo p e r a t o r u s i n g t h e s et o o l s ，w ec a l lc o n v e r te v e r yc h i n e s et oi m a g e s ow ec a l lg oo no u rr e s e a r c h o nt h es i n g l ec h i n e s ei m a g e w ec a n tr e s e a r c hh o wt os e p a r a t et h ec h i n e s e d o c u m e n t ，a n da v o i dt h ee r r o ro fs e p a r a t i n gc h i n e s ed o c u m e n t o nt h eo t h e rh a n d ， a l lt h ew o r kw en e e dt od oi sc o n v e r ta l lt h et x td o c u m e n tt oi m a g eb yu s i n gt h i s t 0 0 1 a n dt h et o o lc a np r o c e s sag r o u pd o c u m e n ta to n et i m e 1 1 1 ew o r ki sa l ld o n e b yt h et o o l sa n ds a v eal o to fm a n p o w e ra n dt i m e a tl a s t , w ec a l lp r o c e s s d o c u m e n ti m a g ea sw en e e d ，f o re x a m p l e ，w ec a na d dn o i s et ot h ei m a g et o s i m u l a t et h er e a le n v i r o n m e n t 3 n e x t ，w ep u tf o r w a r ds t r o k ed e n s i t yc o d em e t h o dt oa b s t r a c tt h ec h a r a c t e r i s t i c ， n - g r a mm o d e lt oe x p r e s st h ed o c u m e n ti m a g em o d e l ，a n dn e a r e s tn e i 【g h b o r m e t h o df o rd o c u m e n ti m a g ec l a s s i f i c a t i o na n dt h ec o s i n em e a s u r e m e n tt o c a l c u l a t et h ec o m p a r a b i l i t y a tl a s t ，w ei n t r o d u c et h ei m p l e m e n t a t i o no ft h e s y s t e m 、e x p e r i m e n td a t aa n dt h ea n a l y s i st ot h ed a t a n 砖r e s u l ts h o w st h a tt h i s d o c u m e n tc l a s s i f i c a t i o nm e t h o di se f f e c t i v e 4 a tl a s t , w es u m m a r i z eo u rd i s s e r t a t i o na n dg i v et h ee x p e c t a t i o n k e yw o r d s d o c u m e n t i m a g ec l a s s i f i c a t i o n ，a b s t r a c tc h a r a c t e r i s t i c ，s t r o k ed e n s i t yc o d e ， d o c u m e n ti m a g em o d e l ，n g r a mm o d e l ，c a l c u l a t ec o m p a r a b i l i t y 4 北京邮电太学学位论文 1 1 课题背景及研究意义 第一章概述 现代技术可以运用各种手段大量地采集和生产各种类型的信息。据统计全世 界的信息量正以2 0 万倍于人口的增长速度递增。全球各地己建立了许多大型的 多媒体数据库并向公众提供服务。随着信息高速公路的建设，各种信息的流通和 传输也将越来越方便。但在很多情况下，信息的膨胀给人类带来过多的信息量以 至于要超过人的接受能力了。 随着现代计算机的不断发展，数字文档越来越流行，它比起传统的纸制文档 更方便存储和传输。数字文档使用最多的形式是文本文档，即文档字符是由机器 可读码( 如a s c i i 码) 表示的。成千上万卷的报纸、书籍、杂志仍是纸制的，需 要转换到数字领域。一般来说，通过数字设备这些纸制文档很容易被转换成数字 图像，然后利用光学字符识别( o c r ) 技术可以再将这些数字图像转换成机器可 读的文本文档的形式。 文档分类是指根据文档的内容或属性，将大量的文档归到一个或多个类别的 过程。目前对于文本文档的分类研究的比较多，随着图像文档的日益增多，图像 文档的分类问题也越来越引起人们的重视。图像文档分类应用广泛，例如越来越 普遍的数字图书馆。众所周知，将文档以数字图像的形式存储起来是非常经济的， 但是，如何访问和操作这些图像文档却成了一个新的问题。 对文本文档进行分类，比较简单的方法是利用关键词实现的。本文需要讨论 的是图像文档的分类，如果使用关键词分类的方法进行，就必须使用o c r 技术， 但这样会导致系统的效率降低，运行速度满足不了实际的需求。本文所要研究的 是脱离o c r 技术的快速图像文档的分类方法，对图像文档的内容进行简洁的表 示，以此为基础进行分类。 要访问和操作图像文档，一种方法是将这些图像文档全部转换成机器可读的 文档的形式( 一般是文本文档) ，然后再利用文本文档分类的方法进行处理。但 是要使图像文档完全无误的转换为文本文档在技术上几乎是不可实现的，因为 o c r 识别率的限制，识别后人工校正工作不可避免；而且这种转换的时间、空 间资源开销太大。因此，研究图像文档信息的分类方法是迫切需要解决的问题。 目前研究的一种方法是允许在使用o c r 技术( 由于切分和识别) 过程中有一定 的误差的基础上进行的 2 】；另外一种方法是基于图像的识别方法，即不使用o c r 技术。 北京邮电大学学位论文 + ：基于o c r 的途径+ ：基于图像的途径 国l 一1 使用基于o c r 技术的方法的优点是被转换后的文本文档可能会有其他的用 处，但是校正o c r 的识别结果所需要的代价太高，由图像转换成文本的整个过 程要花费很多时间。在网络环境下进行图像文档分类，需要处理速度快，这种方 法无法满足网络上图像文档的分类。而基于图像识别的方法可以直接以图像的形 式进行分类，这样图像文档分类脱离了o c r 技术，大大提高了系统的运行效率。 尽管分类精度有所降低，但是满足了特定场合下的网络图像文档分类的要求。 1 2 国内外的研究现状 长期以来，文档分类都是自然语言处理的一个重要的应用领域。直到8 0 年 代末，在文档分类方面占主导地位的一直是基于知识工程的分类方法，即由专业 人员手工编写分类规则来指导分类，其中最著名的系统是路透社开发的c o n s t r u e 系统。9 0 年代以来，随着信息存储技术和通信技术的迅猛发展，大量的文字信 息开始以计算机可读的形式存在，并且其数量每天仍在急剧增加。这一方面增加 了对于快速、自动的文档分类的迫切需要，另一方面又为基于机器学习的文档分 类方法准备了充分的资源。在这种情况下，基于机器学习的文档分类通常由训练 和分类两个阶段组成。在训练阶段，从训练文档学习分类知识，建立分类器；在 分类阶段，根据分类器将输入文档分到最可能的类别中。在机器学习领域，分类 属于监督学习。 文档自动分类的关键问题是如何构造一个分类函数或分类模型( 也称为分类 器) ，并利用此分类模型将未知文档映射到给定的类别空间。分类器的构造方法 有多种，主要有统计方法、机器学习方法、神经网络方法等。空间向量模型( v s m ) 与n a i v eb a y e s 模型是近年应用较多且分类效果较好的两种文档分类模型。文档 自动分类是一项重要的信息处理技术，作为组织和管理数据的一种有力手段，在 邮件分类、电子会议、信息过滤等方面得到了较为广泛的应用。其中较为成功的 系统有麻省理工学院为白宫开发的邮件分类系统、卡内基集团为路透社开发的 北京邮电大学学位论文 c o n s t r u e 系统。在国内，文档自动分类技术研究的起步较晚。 对于图像文档，目前传统的做法是先舟o c r 技术将图像文档识别成文本文 档，然后再采用文本文档分类的技术进行分类。由于o c r 的识别精度有限，转 换出来的文本文档中不可避免的存在一定的错误，这就给后续的分析带来了困 难。解决这个问题的方法是在o c r 后应用一个o c r 自动纠错系统。这种技术 会尽量减少文本文档中由于o c r 带来的错误，但是不可能完全消除错误，而且 这样用了o c r 技术之后又用相应的纠错技术非常耗时，使图像文档分类的时间 开销大大增加。而在图像文档分类方面的应用上，希望处理时间近可能的快，如 何解决这个矛盾成为现在面临的主要问题。 在中文图像文档分类中，目前经常使用的一种方法是在图像文档中查找关键 字。基于图像的关键字查找在信息分类领域是有其实用价值的。许多这样的关键 字查找的方法是针对英文单词的，如前几年提出的单词定位技术【3 ，4 ，5 】，目前针对 中文图像文档的研究还比较少。汉语与西方语言相比是有很大的不同的。所以研 究适用于汉语的基于图像的关键字查找技术是很有必要的。还有种分类中文图 像文档的方法是基于内容的分类方法【6 1 。在这种方法中，使用了笔划密度编码的 方法来表示图像文档，并且用n g r a m 模型来描述中文图像文档，然后用关键字 的笔划密度编码串与这个n g r a m 模型中的每个元素进行比较。这种方法需要对 文档中的每个字符图像进行笔划密度编码，然后再进行关键字的查找。 目前做这方面研究的有新加坡国立大学计算机学院。新加坡国家图书馆将全 部的期刊微缩拍摄下来，存储成图像文档的形式。很多人们需要在这些图像文档 中查找自己需要的内容，因此对于图像文档的分类、检索闯题成了他们研究的主 要课题。继文本文档分类之后，国内许多科研机构也开始了对图像文档分类问题 的研究。 我国计算机文档分类起步于8 0 年代初期。在计算机编制主题词表、汉语自 动分词和标引、数据库建造、情报检索和相关软件的研制、联机检索、机器翻译、 图书馆业务管理、全文检索理论等主要领域取得了很大的进步。但由于汉语语言 的独特性，我国的计算机文档分类系统与国外分类系统还有一定的差距。目前文 档分类技术在向两个方向发展：一是传统的文档分类向全文文本、多媒体等新型 信息分类发展，在深度上对提问的内容进行分析和理解，提高精确率，探索自动 抽词、自动索引、自动分类、自动分类、自动翻译等解决方案，提高管理和组织 信息的能力；二是文档资源的网络化和分布化，从广度上面向i n t e m e t 上浩瀚的 文档资源提高召回率。 北京邮电大学学位论文 1 3 论文的主要内容 通过研究生两年的学习研究，在翻阅了国内外相关方面的研究论文的基础 上，在指导教师的指导下，本文提出了一种脱离o c r 技术进行图像文档分类的 方法，这种方法大大提高了系统的运行效率。尽管分类精度有所降低，但满足了 特定场合下的网络图像文档分类的要求。 论文首先简单介绍了文档分类的现有技术：首先介绍了文档的特征提取方法 文档频率、信息增益、交叉熵、c h i 统计和互信息；然后介绍了几种典型的 文本分类方法最邻近分类、朴素贝叶斯、决策树、支持向量机、相关反馈和 神经网络，并且分析比较了这几种方法的优点和缺点；接下来介绍了几种常用的 计算文档间距离的方法内积、d i c e 系数、j a c c a r d 系数和余弦系数；最后介 绍了文档的表示方法，这里介绍了一种使用最广泛的空间向量模型方法，然后还 主要介绍了本文中使用的n g r a m 模型表示文档的方法。 然后介绍了为了进行图像文档分类的测试，创建的图像文档数据库。现有的 图像文档数据库是用扫描仪将文档扫描进电脑的，这样做费时费力，但是这样做 可以建造一个最能反映真实情况的图像文档数据库。本文是在已有的文本文档的 基础上，利用自己开发的文档一图像转换工具，将文本文档转换成图像文档，形 成了自己的图像文档库。建立图像文档数据库而开发的两个软件工具文档一 图像转换工具和汉字图像处理工具。这两个工具对于建立图像文档数据库发挥了 很重要的作用：一是使用这种工具，可以将文本文档中的每个汉字转换为图像形 式，这样接下来的研究就可以直接在单个汉字图像上进行了，省去了图像文档中 汉字切分的部分，从而避免了因为汉字切分错误而带来的误差；二是使用这种工 具创建图像文档数据库，所要做的工作只是将现有的文本文档通过程序转换为图 像形式即可，而且程序具有批处理功能，这样主要的工作都交给程序来完成，节 省了大量的人力和时间；三是可以根据自己的需要对图像文档进行各种处理，例 如模拟真实的情况就可以自己加入噪声等。 接下来介绍了一种无需o c r 技术进行图像文档分类的方法。因为使用o c r 技术每个汉字需要提取大量的特征，所以在判断这个汉字图像的时候需要进行大 量的计算，增大系统的开销，非常耗时。本文采用了一种笔划密度编码的方法， 应用这种方法，提取汉字图像的特征，将汉字图像仅用一个8 位的数据表示，大 大简化了传统的o c r 的特征提取方法，使处理时间大大缩短。但是，这种方法 是以牺牲一定的精度为代价的。汉字的一级字库里面有3 7 5 5 个汉字，而8 位只 有2 5 6 类，也就是说本文将3 7 5 5 个汉字分成了2 5 6 类，这样存在一个汉字压缩 的问题，就是可能一个编码表示多个汉字。为了解决这个问题，本文采用了 n g r a m 模型来表示图像文档。使用n g r a m 模型表示文档，将上述的笔划密度 北京邮电大学学位论文 编码方法带来的汉字压缩的问题对分类的影响降低了。最后本文采用了最邻近的 文档分类方法，使用余弦公式来计算文档模型间的距离。 论文的最后部分介绍了应用这种图像文档分类方法的系统实现。给出了测试 的结果，并对结果进行了分析。最后对这种方法进行了总结以及提出了需要改进 的地方。从实验结果上来看，这种方法在图像文档分类方面还是有一定的效果的。 接下来需要进一步进行研究和改进。 1 0 北京邮电大学学位论文 2 1 概述 第二章文档分类 文档分类中需要研究的主要问题就是文档分类的问题。文档分类的思想是： 已知一组已有标记的类的集合c t ( o ，o ，c 珊 ( 训练集) ，用最高的相似度分配 一个测试样本( 文档) 到个类，在文本分类的一些方法中，要计算文档与文档 类之间的相似度，根据相似度的值来分配文档到一个类。 分类的模式有两种：是两类问题，即给定的待分类文档属于或者不属于某 一类；二是多类问题，即个文本可以属于多个类别。分类体系一般是人工构造 的，例如将现有的文本分为政治、体育、军事等类别。目前，现有的分类体系主 要是中图分类体系： 中图分类；鲁 类马刊主义、毛泽勰惫口类般 】陆术 墨类哲学仰类矿业卫瞪 c 类社会j 伴黻1 e 类石油、天然诎 d 娄政治、法律1 f 类诮虹业 e 类军事类金露学、金屠工艺 f 类经济类机挂、仪杠艺 g 类文化、科学、教育、体育1 了类武器耻 类语言、文字类动力耻 i 类文学1 l 类额子黼 i 粪艺术礓类电琳 x 类历史、地理类无婚扣蝌、电燃 类自然稃学慧论口类自动f e 技术、计算接术 o 类数理科学和化学m 类化学工业 p 类天文学、地球科学巧类轻工业、手工业 q 粪生铀科学西类建觥 r 类酾、卫生盯类水刺工程 s 类农业科学 u 类交通运输 y 类航空、航天 呈类环境科学、劳动保护科学( 安全科学) 图2 一l 文档分类的一般过程为首先收集训练集和测试集，对文档进行预处理：然后 对文档类别进行人工标注；接下来需要对文档进行特征提取：另方面要训练每 一类的标准特征；最后通过相关的计算确定被分类文档所属的别类。文档分类的 北京邮电大学学位论文 系统结构如下图所示 2 2 文档的特征提取 图2 2 文档的表示也是一个特征提取的过程，本文要提取的是文档的特征。文档表 示中词条乃及其权值彤的选取称为文档特征提取。文档特征提取是文档类共性 与规则的归纳过程，是分类系统的核心，文档特征提取算法的优劣直接影响到文 档分类的效果。 在文本分类的问题中遇到的一个主要困难就是高维的特征空间，特征维数很 高是文档分类面临的一个重要的问题。通常一份普通的文本在经过文本表示后， 如果以词为特征，它的特征空间维数将达到几千，甚至几万。大多数学习算法都 无法处理如此大的维数。为了能够在保证分类性能的前提下，自动降低特征空间 维数是一个很重要的工作。 文档集中每个单词对应一维，进行分类计算时，就需要大量的计算时间。如 能在不削弱精确率等性能指标的前提下，较大程度地压缩文档空间的特征维数， 就能提高系统的响应速度。特征选择方法尝试从文档集中除去信息含量较低的单 词，从而提高分类效率和减少计算复杂度。下面简单介绍几种目前常用的文档特 征抽取方法。 2 2 1 文档频率( d o c u m e n tf r e q u e n c y ) 词条的文档频率是指在训练语料中出现该词条的文档数。采用d f 作为特征 抽取基于如下基本假设：d f 值低于某个阈值的词条是低频词，它们不含或含有 北京邮电大学学位论文 较少的类别信息。将这样的词条从原始特征空间中移除，不但能够降低特征空间 的维数，而且还有可能提高分类精度。 文档频率是最简单的特征抽取技术，它能够容易地被用于大规模语料统计。 但是在信息抽取研究中却通常认为d f 值低的词条相对于d f 值高的词条具有较 多的信息量，不应该将它们完全移除。 2 2 2 信息增益( i n f o r m a t i o ng a i n ) 信息增益在机器学习领域被广泛使用。对于词条r 和文档类别c ，信息增益考 察c 中出现和不出现r 的文档频数来衡量r 对于c 的信息增益。本文采用如下的 定义式： 佑p ) = 一p ( q ) 1 0 9 p ( c i ) + 尸( r ) p ( q l t ) l o g p ( c ，lr ) + p ( - ) p ( q i t ) l o g p ( c , i _ ) i = il - lt = l 式( 2 1 ) 其中p p j 表示c i 类文档在语料中出现的概率，pn ) 表示语料中包含词条f 的文档的概率，p ( c f l ，) 表示文档包含词条，时属于c i 类的条件概率，p ( t ) 表示 语料中不包含词条f 的文档的概率，p ( qlr ) 表示文档不包含词条t 时属于。的条 件概率，埘表示类别数。 词条的熵值越大，说明分布越均匀，越有可能出现在较多的类别中；熵值越 小，说明分布的越倾斜，词可能出现在较少的类别中。 2 2 3 交叉熵( c r o s se n t r o p y ) 相对熵也称为k l 距离( k u l l b a c k - l e i b l ed i v e r g e n c e ) ，反映了文本类别的概 率分布和在出现了某个特定词汇条件下的文本类别的概率分布之间的距离，该值 越大，词对文本类别分布的影响也大。 c e ( t ) = p ( qi t ) l o g 幽 p ( c j ) 交叉熵的定义与信息增益近似，不同之处在于交叉熵只考虑一个词f 出现时 的影响。它的定义为： c 删莩讹l o g 错 2 2 4c h i 统计 c h i 统计方法度量词条f 和文档类别c 之间的相关程度，并假设r 和c 之间 北京邮电大学学位论文 符合具有一阶自由度的z 2 分布。词条对于某类的z 2 统计值越高，它与该类之间 的相关性越大，携带的类别信息也较多。令表示训练语料中的文档总数，c 为 某一特定类别，r 表示特定的词条，a 表示属于c 类且包含r 的文档频数，b 表示 不属于c 类但是包含f 的文档频数，c 表示属于c 类但是不包含f 的文档频数，d 是即不属于c 也不包含t 的文档频数。则t 对于c 的c h i 值由下式计算： z 2 p ，。= 百面面n x 面( a d 两- 面c b ) 而z 对于多类问题，分别计算r 对于每个类别的c h i 值， 于整个语料的c h i 值，分别进行检验： 磊。( f ) = i n a x ：l z 2 ( f ，o ) 再用下式计算词条r 对 式( 2 - 5 ) 其中m 为类别数。从原始特征空间中移除低于特定阈值的词条，保留高于 该闽值的词条作为文档表示的特征。另一种方法是将词条对于各个类别的平均 c h i 值作为它对所有类别的c h i 值，但是它的表现不如上式。 2 2 5 互信息( m u t u a li n f o r m a t i o n ) 互信息在统计语言模型中被广泛采用。如果用a 表示包含词条r 且属于类别 c 的文档频数，占为包含t 但是不属于c 的文档频数，c 表示属于c 但是不包含t 的文档频数，表示语料中文档总数，t 和c 的互信息可由下式计算： 埘( f ，c ) l o g 丽丽ax 石n 两 式( 2 - 6 ) 如果r 和c 无关，“，c ) 值自然为零。为了将互信息应用于多个类别，与 c h i 统计的处理类似，由下式计算t 对于c 的互信息： m i r a 。( f ) = m a x , 1 l ( t ，q ) 式( 2 - - 7 ) 其中m 为类别数。将低于特定闽值的词条从原始特征空间移除，降低特征 空间的维数，保留高于阈值的词条。 互信息 打越大t 和c 共现的程度越大。互信息的定义与交叉熵近似，只是 互信息不考虑，出现的概率。 2 3 文档的表示 2 3 1 布尔模型( b o o l e a nm o d e l ) 布尔模型是一种简单的严格匹配模型，是最简单的分类模型，也是其他分类 1 4 北京邮电大学学位论文 模型的基础。标准布尔逻辑模型为二元逻辑，即一系列对应于文件特征的二元变 量。这些变量包括从文件中提取的文本分类词，有时也包括一些更为复杂的特征， 如数据、短语、私人签名和手工加入的描述子句。在布尔模型中有确切的文件特 征表达集合，用户可以根据分类项在文档中的布尔逻辑关系递交查询。匹配函数 由布尔逻辑的基本法则确定，所分类出的文档或者与查询相关或者与查询无关。 查询结果一般不进行相关性排序。布尔模型分类速度快，在许多分类系统中得到 应用。但布尔模型的文档表示能力差，无法区分特征项对文档内容贡献的重要程 度，并且逻辑表达式过于严格，往往会因为一个条件末满足而忽略了其他全部特 征，造成大量的漏检。 2 3 2 空间向量模型( v e c t o rs p a c em o d e l ) 文档表示方法 对文档进行分类之前需要将文档表示为计算机能够处理的形式。向量空间模 型( v s m ) 是使用最多且效果较好的表示方法之一。在该模型中，文档空间被 看作是由一组正交向量长成的向量空间。若该空间的维数为n ，则每个文档d 可 被表示为一个实例特征向量z ( d ) = ( q ，：，国。) ，v 的每一个分量表示对应特征 在该篇文档中的权值。 计算特征权值的最简单的方法是布尔权重：口矿1 ( 乃0 ) 或0 ( t f f 0 ) ；计算特 征权值的另一种方法是t f i d f 。词条在文档d 中的t f i d f 值由下式定义： t f i d f 。= r e , l o g ( n d e , 1 式( 2 8 ) 其中z r 是词条 在文档d 中出现的频数，表示全部训练文档的总数，d f i 表示包含词条t t 的文档频数。 为了降低文档的特征维数，本文假设稀少的词或者对于目录预测没有帮助， 或者不会影响整体性能。本文先计算所有词的d f ，然后删除所有d f 小于某个 阈值的词，从而降低特征空间的维数。这样做的优点是这是最简单的降低特征空 间维数的方法；缺点是稀少的词有时具有更多的信息，因此不宜用d f 大幅度地 删除词条。 相似度比较一般是采用c o s i n e 计算或者内积计算。 2 3 3n g r a m 模型文档表示方法 2 3 3 1n - g r a m 模型简介 n g r a m 模型是最为常用的统计语言模型， 三元文法( t r i g r a m ) 模型应用最为广泛。 n g r a m 模型以马尔可夫模型为理论基础， 其中尤以二元文法( b i g r a m ) 和 对一词串w = w ，w 2 ，w 。， 北京邮电大学学位论文 可以认为词w 。( 1 i 1 1 ) 的出现与上文的前一个词相关，则词串w 出现的概率 可通过如下的方法得出： p ( w ) = p ( w 。w 2 o ) = 兀p ( w jw f i w f 一：一。) r 1 1 其中j p ( w f l w f 。+ j w f h ) 表示在给定历史信息w i 。+ 1 ，w ，1 ，w f _ 1 的条件下，选取词w ，的概率。这就是n g r a m 模型，并且所有信息组成了一条马 尔可夫链。在实际应用中，为简化计算，往往只考虑一个或两个历史信息，形成 二元文法( b i g r a m ) 和三元文法( t r i g r a m ) ，即p ( w f l w “) 和p ( w f l w , _ 2 w 。m 一般来说，拧取2 或3 。在语言模型的构造中，可以字、词、词性或词义等 作为n g r a m 模型的统计单元。 由于n g r a m 模型只观察2 到3 个历史信息，所以它反映的是语言的局部规 律，但如果训练语料足够大，模型构造合理，这个局部规律将比较可靠。利用这 一点，本文可以应用n g r a m 模型对文本进行局部分析。 2 3 3 2 使用n - g r a m 模型表示文档 在进行全文分类的时候，首先要将要分类的内容分割成较短的文字序列，然 后生成在每个文字序列中所包含字符串的对应表( 索引) 。每篇文章都进行同样 的处理。然后以一个这样的字符串的对应表( 索引) 作为基础，与每个文章的索 引进行比较，当这样计算的两篇文章的相似度大于一定的阈值的时候，本文就认 为这两篇文章是同一内容的。 汩前有两种文字切割方法：词素解析与文字索引( n g r a m ) 。词素解析是指 文字序列按照字典意义上的最小单位进行分解处理。与此相对的，n g r a m 则不 考虑文字的意义，只按照一定的长度n 来分割文章。按词素解析法进行文字分 割后，可根据有意义的单词进行分类。对于只有部分文字一致但没有意义的文字 就排除在外，减少了分类的干扰。但会出现词典中没有的单词时就不能进行正确 分割的现象，所以有发生分类遗漏的可能性。相反，如果采用n g r a m 的话，不 会出现分类遗漏的情况，但增加了分类的干扰。 n g r a m 算法用于文本文档中最初是由d a m a s h c k z 3 1 提出的，是为了测算电 子文本文档的相似性的。一个n g r a m 就是一个珂个字符组成的连续序列。一系 列的n g r a m 序列是由一个宽度为n 个字符的窗口在一篇文档上以一个字符为单 位的步长向前滑动而产生的。然后建立一个h a s h 表来表示每个不同的n g r a m 在这个文档中出现的次数。每个文档都会有一个这样的h a s h 表，这个h a s h 表就 是该文档的特征向量。 本文采用的是n - g r a m 的切割方法。这种方法适合本文在汉字图像特征提取 1 6 北京邮电大学学位论文 的时候使用的笔划密度编码方法，使由于笔划密度编码方法带来的汉字压缩问题 造成的误差尽量降低。 2 4 文档的分类 分类器是整个分类方法的核心，一般需要使用训练数据来构造和完善。分类 器解决这些问题的方法主要有：基于规则的方法和归纳学习的方法。基于规则的 方法与专家系统中使用的方法类似，但是需要手工构造规则，并且修改比较困难。 另一种方法是使用归纳学习的方法，利用训练数据自动构造分类器。训练数据集 合可能有大量的特征词，因此文档分类向归纳学习方法提出了许多新的问题。 早期多使用基于知识工程