（计算机应用技术专业论文）文本分类与信息提取方法的研究与设计.pdf

摘要 摘要 隧麓瓣络售惑技零戆遮速发曩彝企焦信息德程度戆瓣蹇，套越来越多豹僖惠积 累，其中大部分是以文本形式存在。人们急需种能够从大规模的文本信息资源中 提取耱合嚣要豹、楚洁懿、萄靠挫离鳇售塞熬王具。数据挖掘中戆文本数撵挖握正 是要解决这个问鼷。文本分类和信息提取作为文本数据挖掘的重鬃应用，也越来越 褥到人们豹关注。 本文主要介绀文本挖掘系统的研究与设计。其中，文本分类和信息提取方法的 研究与设计是课题研究的鼹点。对文本分类技术进行研究和分析，进而提出一种基 于特征词句予环辘的文本分类方法。介绍了创建分类窥瓣酶文本匈子信息穰翟，魄 较详绷地给出训练算法和语句聚集算法。该算法依据训练文本集的特征词句予环境， 获取谈涮文本主舔类麓静特征词集会。在对文零信意提取技拳磷究分耩静麓稿主， 将时间信息和地避位置信息进行分析总结，形式化地概括其专用词，构造时间信息 司法分辑器霸懿壤霞萋壤惠递法势掇器，霉擞据慈缝瓣搴终露阗镶惠窝事穆恁理盈 置信息规则，设计信息提取算法，以实现文本的信息提取。 关键词数据挖瓣；文本数据挖掘；文本分类：信息提取 a b s t 凇 a l b s t r a c t w i 也t h es w 溉d e v e l 】。p m e n to f 辩淞o r k 翻a 虹o nt 池o l o g y 细d 龇i m 妒0 v e 程蚴to f c o f p o f a 虹o n 主n f o m m 畦o n ，t h c f e i s 椭o r e 蠲d m o 忿i n 如r m a 蛞锄袅c c 啪i l l a 翻珥缸w h i c h l o 缸o f i te x i g 姆b y t h el o r mo ft e x t i ti su l g e n lt 0g e tat o o lw h i c hc o m de x t r a c tt h e 触f o l m a t i o nw i 血s a t 瑚知：t o r ) ， 翻豳嘲a e ta 丑矗娥a 醚e 啪l 氇el 截萨s 耗 e x | 妇如黼畦。珏辑掘嚣文鬈甑| 南熔糟i 珏虹g 巍妞螽攮 m i n i n gi sj u s tt 0 l v et h i sq 鳓o n 1 e x td a 船蚯谢n 粗d “如咖o n 咖虹o nq a 埔i m 脚t a p 舞c 薯拄。a 醴t “l 蠡拯删撼鑫誉h 搽a l 妇醴酲搬删e 鞠d m o 蛳涎。 t h i sp 叩噼rm a i d l yi n t d u c e 8t h e 托踯囊f c h 柚dd e s i g no ft e 越m i n i n gs y s t e m a m o n gt h e m ，t h e f e s l 谯鞠dd 髂i 萨o f 妞如e l b d so f 洄( 1 融鹊i 矗瞄l 妣a n d 虹如盥a 矗鼬e 烈鞠c 娃o na 糟l he 黼砖勰e s 。f h e 髫喇c c ts 乜l d y i tr 鹳e a r c h e sa n d 锄a l y st 醅t e x td 船s 谶髓畦o nt c c 赫o l o g y ，拍dp p o s e s 暂i m t h o d o f 嗽td a 辐i f i a 吐i 加b a d 姐c 。n t e x to fi b 甜1 辩w o l d si s 翩l t 蛐o e 矗o ff e a m 糟w o r d s a 湖t e n c o 细f 0 靠黼t i o nm o d e lo ft o x tf o ro 精a 妇gf l l l 姻惫颦的d 瓣鸯鞘dl h e 撤畦藏i l 瞎舔驴嫩h ma 藏ds 锄t e n c e c l u s t e r h l g a l 洳a i ed e s 廿慨d i n 瑚如t a i l b o t h o f 也e 蝴o r i t h 吣b a s e d 岫c o n t c x t o f f e a t i i 坤 w o l 泰遮辩珏耙蒸c e 醴溉抽i 矗g t e x 舔e 勰容酿a 辩童醛螽鼗| | l 糙w o 翻s 氇畦翊鞠鞋母 b 锚垂e g 。瑾o f 鑫 e x o 黩 t h eb a s i s0 ft h et e x t 蛔如r m a t i o ne x i r a 嘶n 如g i n r i n g 北甜c h 卸da n 啦s i s ，w e 蛐栅a l i z e i h e 血 捌溉骷i o 毪站d 氆e 秘。g 溯越巍删6 强测触a 翰勰d 譬e 端畦每臻e 罐e d 砖| 霉艘j 珏曲g 妇e o 熟e t i n l ei n f 0 珊a t i o nl 既i c a l 蛆a l 强。ra dt h eg e o 争叩挝c a lp 0 8 舢o ni n f o r m 甜o nl e 妊c a la n a l y z e ra 聪 丑s l 棚e 把d 。t 融l h e 主n f o 翔a i o ne 】出粼嚏i o ns u b s y s l c m 啪b e 出s i g n e d 鱼渤池鐾t o 也e8 m m 瑚f i z e d o v 蝴tt i l n ei n 】轴m 蕊o n 勰dt h ee v c n tg e o 耵a p 艄嘲p o 疏i o nm f o 瑚a 畦0 nn i l 。拍e 蜘辆m 撕。珏自翰旺 e x t r a c l i 叩啦p r i i h n li sd e s 酒l e dt op u 伯l t o 轴蛐 嚣沁y w o r d sd a t am i n i n g ；t e md 嘲n l h l 她；t e 挝d a 站城c a 虹o n ；删姐吐t i o ne 难a c 幽n 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：参啦亟霪日期：殛堕：占! 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 狃隰泣“：g 第1 章绪论 1 1 研究背景 第1 章绪论 随着科学技术的不断发展与进步，网络已经渗透到社会生活中的每一个角落。 网络的蓬勃发展导致信息不断膨胀，如何从成千上万的信息中整理出有用的信息成 为人们日益关注的问题。 数据挖掘“( d a t am i i n g ) 又称数据库中的知识发现，是一个从太规模数据库的 数据中抽取有效的、隐含的、以前未知的、有潜在使用价值的有用信息的过程。它 是当今众多学科领域特别是数据库领域最前沿的研究课题之一。 文本挖掘作为一个新的数据挖掘研究领域，目前并没有给出统一的、确切的定 义，但是文本挖掘的目的就是从文本信息中发现潜在的、可能的数据模式、内在联 系、规律、发展趋势等，并转化为人可以利用的知识。文本挖掘是一个交叉的研究 领域，它涉及到数据挖掘、信息检索、自然语言处理、统计数据分析、概率理论、 机器学习等多个领域的内容，不同的研究者从各自的研究领域出发，对文本挖掘的 含义有不同的理解，不同的应用目的，文本挖掘项目也各有其侧重点。与传统的 数据挖掘相比，文本挖掘有其独特之处，主要表现在：文档本身是半结构化或非结构 化的，无确定形式并且缺乏机器可理解的语义；而数据挖掘的对象以数据库中的结 构化数据为主，并利用关系表等存储结构来发现知识。进行文本挖掘的主要目标有： 文本分类、文本聚类、信息提取、文本总结等。其中，文本数据挖掘中的文本分类 和信息提取“1 就是本课题所研究的重点。 文本分类是指按照预先定义的主题类别，为文档集合中的每个文档确定一个类 别。这样，用户不但能够方便地浏览文档，而且可以通过限制搜索范围使文档的查 找更为容易。文本分类主要有两种方式。第一种方式是手工的方式，也就是人工将 每篇文档分配到相应的类别下。但是这种方法的代价比较昂贵，不适台处理大规模 的文档。另外一种方式是自动分类。对于自动分类系统。我们可以从领域专家那里 或者从训练文档集合里自动学习分类模型进行分类。随着全球计算机与通讯技术的 飞速发展、互联网的普及与应用，信息爆炸的现实使人们越来越注重对自动分类的 研究，文本自动分类及其相关技术的研究也日益成为一项研究热点。 信息提取是一个以未知的自然语言文档作为输入，产生固定格式、无歧义的输 出数据的过程。这些数据可以直接向用户显示，也可作为原文信息检索的索引， 或存储到数据库、电子表格中，以便于以后的进一步分析。也可以说，信息提取是 指从大量的、无结构的文本信息中抽取出有效、有用、可理解的、散布在文本文件 指从大量的、无结构的文本信息中抽取出有效、有用、可理解的、散布在文本文件 魏泰工蛙丈学工学颈学位论文 中的有价值的知识，并且利用这些知识更好她组织信息盼过程。信息提取的最的是从 文本中扫插并提取出所需要的事实。信息掇取虽然需要对文本涟行一定释度的理解， 但与真正的文本理解述是不同的。在信息提取中，用户一般只关心有限的感兴趣的 事实绩塞，只是黠文校审包含鞠关售惠戆潞分进行分凝，至予耀些燕惑楚程关稳，将 由系统设计时定下的领域范围而窥。所以说，信息撼取并不关心文本意义的细微麓 别以及作者的霹作意图铸深层璁解问题。因此，信息提取只能舞是一种浅层的或赣 落麓证酶文本理解技米。 1 2 国内外研究现状 本小节将分别介绍文本数据挖掘中的文本自动分类和信息提取两个方面的研究 现状。 1 2 i 文本囱动分类的研究现状 国乡 对予文本自动分类静研究开始较举，5 0 年代宋，h p 轴i l n 在这一领域避符 了开创性的研究，他首先提出了将词频统计的思想威用于自动分类。国外的自动分 类獗究大致缀魇了三令除段：第一除段f l 鳃8 年1 垒雒冬) ，主要遴霞自动分类静霹嚣 性研究；第二阶段( 1 9 6 5 年1 9 7 4 年) ，自动分类的实验研究：第三阶段( 1 9 7 5 年至今) ， 自动分类进入实用化阶段，并在m g 件分类、电子会议、信息过滤方面取得了比较广 泛麴应蠲，箕孛院较藏麓鹣铸予裔寐餐理z 学浣( m 糖 秀鑫富开发静自i 襻分类系绞、 卡内基集团为路透社开发的c o n s 咖e 系统等。 国内慰予文本自动分类的职究起步比较晚，1 9 8 l 冬，侯汉潺教授瓣予诗算掇在 文本分类工体中的应用作了探讨，并介绍了国外计算机管理分类表、计算机分类检 索、计算机自动分类、计算机编制分类表镣方面的概况。我国自动分类的研究大体 上挺在经雳获嚣簿牲撵 事辏麓分类鑫动努类系统翦发箴狳段。笑子孛文文 本分类的研究相对较少，国内外的研究基本上是在英文文本分熊研究的然础上采取 相殿策略，结合中文文本的特定知识，然麟应用予中文之上，继丽形成巾文文本蠢 动分类研究体系。我国爨经研究渤一抵计算机辖韵分类系统和囱动分类系统。钢獭， 广家省中山图书馆的莫少强开发的计算机辅助图书分淡系统( c 墟c ) 、清华大学 要举骚毒l 熬鑫动分类系统、出嚣大学刘舞袋等夭嚣发豹金熬爨漤分类系统、袤l 大 学阕书馆的图书馆分类专家系统，上海交通大学王永成等研制豹基于神经网络优化 算法的中文文本自动分类系统。_ ；琏期研究中比较突出的是中科院的中文义本智多星 分炎器，它袋焉多种分豢方法。髓着中文僚惠处理技术特羯是中文自动分词技术豹 日渐成熟，以此为基础的中文文本分类技术的研究得到了飞速发展，己缀从可行性 第1 章绪论 探索阶段转变到实用化阶段“”。 九十年代以后，著名的文本检索会议f r c x tr e t r i c v a lc o n f e r e n c e ，简称t r e c ) 与主 题检测和跟踪会议( t 0 p i cd e t e c t i o n 趾d1 h c l d n g ，简称) d 都把文本分类作为重要的 评测内容，通过提供规范的大规模语料对文本分类系统性能进行客观、公正的评测， 来促进技术的交流、发展和产业化。这就在很大程度上促进了文本分类研究的发展。 1 2 2 信息提取研究现状 对文本信息提取国际上很早就开始研究，由美国政府资助的m u c ( m e s s a g c u n d c r s t 粗d i n gc 0 n f e r e n c e s ) 是关于文本处理的权威会议，由m u c 定义的概念、模型和 技术规范在国际上对整个信息提取领域起着主导的作用。m u c 与信息提取的任务定 义、研究内容以及研究的技术发展状况评价有着密不可分的关系。它是美国政府支 持的一个专门致力于真实新闻文本理解的例会，该会议的显著特点并不是会议本身， 而在于负责组织对来自世界各地不同单位的消息理解系统进行系列化的评测活动。 只有参加信息提取系统评测的单位才被允许参加m u c 会议。其主要的评测项目是对 从新闻报道中提取特定信息能力的评价，通过信息提取的准确率、召回率和调和平 均值等评价指标进行度量。从1 9 9 9 年起，美国n i s t ( n a t i o n a l h s t i t u t c o f s t 孤d a r d s a n d t c c h o l o 鳓将的任务又深入推进了一步，开展了a 叫a u t o m a t j cc 0 n t c n te x 咖c t i o n 、 项卧该项目的目标是研究开发自动内容提取技术，以支持文本信息的自动处理。 a c e 的研究致力于通过提取和表达语言所传达的意义，来支持文本的分类、过滤、 选择等应用。、 、： 中文信息提取方面的研究起步较晚，由于汉语的特殊性，；中文文本的信息提取引 发了一系列独特的课题。目前，主要的研究工作集中在对中文命名实体的识别方面， 在设计实现完整的中文信息提取系统方面还处在探索阶段。随着计算机处理能力的 不断提高和文本数据积累不断增大，尊重真实文本语言事实已成为当前各种自然语 言信息处理技术( 包括信息提取) 的一个基本立场和出发点。清华大学的黄昌宁教 授等人就成功地结合语料库统计与规则的优点，设计了一个统计与规则并举的汉语 句法分析模型c r s p 。在这个模型中，语料库用来支持各类知识和统计数据的获取。 并检验句法分析的结果，规则主要用于邻接短语的合并和依存的关系网的剪枝，他 们的实验取得了令人满意的结果。 当前重大的基础理论研究成果有：董振东教授的知网：中科院声学所黄曾阳教 授的h n c 理论；北京大学计算语言所的现代汉语语法信息词典等。知网，是一 个以汉语和英语的词语所代表的概念为描述对象，以揭示概念与概念之间以及概念 所具有的属性之间的关系为基本内容的常识知识库，它为语言信息处理的研发提供 了丰富的知识资源。h n c 理论是”i 王i e r 砌i c a ln e 研o r ko fc 0 n c e p t s ( 概念层次网络) 北京工业大学工学硕士学位论文 的简称，是关于自然语言理解处理的一个理论体系。它以概念化、层次化、网络化 的语义表达为基础，把人脑认知结构分为局部和全局两类联想脉络，认为对联想脉 络的表达是语言深层( 即语言的语义层面) 的根本问题。中心目标是建立自然语言 的表述和处理模式，使计算机能够模拟人脑的语言感知功能。而现代汉语语法信 息词典则是以朱德熙先生提出的词组本位语法体系作为设置各项语法范畴的理论 基础。首先是选取一些具体的功能标准确定了汉语的词语分类系统，并对照一个词 语的句法功能表现按义项把它归入某个词类；然后是以功能理念指导词语语法属性 项目的设置，并根据一个词语的实际用法情况标记它的属性值。”。 目前，信息提取技术面临的主要问题是：如何准确地提取出用户所感兴趣的数 据；如何提供给用户友好的界面，方便地形成提取规则；如何减少用户的学习次数； 如何判断规则的适用范围；如何感知网页结构的更新和变化；提取数据的后处理问 题及信息提取的可逆性问题等。 1 3 课题的主要研究内容 在政府的政务活动中。产生大量以中文文本形式存在的政府工作报告。为了及 时处理这些工作报告，需建立政务文本挖掘系统。同时，政府希望能够建立门户网 站，用以收集和发布信息。 采用前沿的数据挖掘技术，结合文本数据处理技术，研究行之有效的文本分类 算法对未知类别文本进行自动分类，并针对自然灾害等类别文本的特点，从已知类 别的文本数据中分析、识别、提取事件的时序信息和空间信息，以实现对文本的信 息提取。 课题的主要的研究内容包括： 1 研究中文文本分类方法，并设计新的文本分类算法对文本进行自动分类。 2 探讨中文文本信息提取方法，研究并设计信息提取算法从文本数据信息中提 取事件的时间信息和地理位置信息。 3 研究知识的表示方式和知识库框架的设计。 4 门户网站的初探。 1 4 本文的组织结构 第一章绪论介绍文本数据挖掘的背景知识，以及文本分类和信息提取的国内外 研究现状，并简要介绍课题的主要研究内容。 第二章介绍中文文本数据挖掘系统的需求分析。课题包括政务文本挖掘系统和 门户网站两个部分。其中，政务文本挖掘系统是课题的重点，政务文本挖掘系统的 笫l 章绪论 需求分析也是该章介绍的重点。 第三章奔绍本谍题载重轰中文文本分类技本研究凝分类算法设诗。凌对分 类技术研究的基础上，提出一种新的文本分类辣法麓于特征词句子环境的文本 分类算法。 繁疆章奔缮深邃瓣另一个重熹信惠提取技术瓣磷究与雾法设计。设诗倍感 提取算法从己知类别的文本中提取事件的时间储息和地理位置信息。 第孤章贪缁文本数据挖掘系统的设计与实现。 第六章对文本挖掘系统的测试结聚进行分祈和总结。 1 5 本耄小结 本镦介绍了研究的背娥，文本分淡和信息提取的研究现状和课题的主要研究内 赛。势麓葵分缨? 本文戆组织结鞫。 第2 章蒜统舞求努析 第2 章系统需求分析 2 1 总体需求分析 课题驻政府的公文处理为主要研究对象。整个谋题盼需求可分为两个部分。 1 ) 政务文本挖掘系统，由政府部门在本地使用，用来瞥理政府公文并对公文进 簿楚理，扶孛控攘懑骞溺鳇繁惠。 2 ) 门户网站，用于政府部门对外发布信息和采集信息。 建立政务文本挖掘系统的目的，魁能够接收、管理并处理各级政府政务活动审 产生的大麓擐告文本，砖当燎社会、经济活动，毽括发生备稀鸯然灾害等方瑟豹报 告文本进行分类和信息提取。 j 一 建变门户赠站敷基静，怒能够将致黠都趣懿敬策翻研巍统计憨德愚公毒予众， 并通过网络采集信息( 如群众意见等) 。 其中，政务文雄挖掘系统的研究与设计是本课题的重点。 2 2 政务文本挖掘系统需求分析 致务文本挖搀鬣绕要求褒给定熟类嬲搏系下，凝摆文本鹣逡窖自动磺定文本豹类 别，并能够根据措定的文本类别自动对文本进彳亍信息提取。 2 2 。堇限定麓疆域 政务文本挖掘系统所要处理的对教是中文文本格式的政府工作报告。一篇报告 交本一般毽括标题、戮标爨、歪文、佟者、堇掇攀位、类糕、嚣期帮各注等镶惠。 报告文本包括已知擞别报告文本和未知类别报告文本。 文本类别根节点 圈冬l 文本类掰罄 r 9 2 1 t 勘吐s o n d i 孵狮 北京工业大学工学硕士学位论文 政府工作报告内容涉及自然灾害、社会、建设和经济方面，隶属于地震、低温 霜冻、冰雹、水灾、火灾、爆炸、旱灾、治安案件、交通事故、交通建设和统计报 告1 1 个类别。文本所属的类别间没有兼类，也就是说每一篇报告文本只能对应1 1 类中的一个类别。类别体系表示如图2 1 所示。 用户对系统的操作从总体上可分为三个方面：文本编辑、文本分类和信息提取。 其中，文本编辑的内容包括已知类别报告文本和未知类别报告文本：文本分类包括 构造文本分类器、对文本分类器进行评估优化和对未知类别报告文本分类三个部分； 而信息提取则包括编辑词典以及已知类别文本的信息提取。政务文本挖掘系统的用 例图如图2 2 所示： 已知共别文本信息提取 图2 - 2 政务文本挖掘系统u c a 图 f i g2 2t h eu 辩c 勰ed i a g r a mo fg o v e m m 曲ta 血i rt e x tm i n i n gs y s t e m 2 2 2 系统功能需求描述 优化 政务文本挖掘系统的功能需求如下： 1 文本编辑( 包括已知类别文本和未知类别文本) 用户按照界面提示进行文本的录入、查询、浏览、修改等操作，系统将结果信 息返回给用户。 2 文本分类 文本分类包括三个步骤：构造文本分类器、文本分类器的评估优化和未知类别 文本的分类。 第2 章系统需求分析 1 ) 构造文本分类器 用户首先登录构造文本分类器的界面，根据界面提示选择参与训练的文本类别； 系统可根据用户选定的类别，自动学习并构造文本分类器。 文本分类器的评估优化 文本分类器构造完成之后，用户登录文本分类器的评估优化界面，选择评估文 本的类别并选择按钮进行评估优化；系统可自动对文本分类器进行性能评估，并根 据评估结果自动调整优化文本分类器。 至此，便得到一个可信度较高的文本分类器。未知类别的文本可通过此文本分 类器自动确定文本的类别。 3 ) 未知类别文本的分类 用户通过设置查询条件，查询数据库中存储的未知类别的文本。此时用户有两 个选择：一是将所有文本进行分类；二是指定其中的一篇进行分类。系统根据文本 分类器自动判断文本所属的类别。 3 已知类别文本的信息提取 信息提取需要实现两方面功能：编辑词典和已知类别文本的信息提取。 1 、编辑词典 用户能够编辑部分附加的词典，可查询、添加、修改、删除词典中的词组及其 词性。 2 ) 已知类别文本的信息提取 用户指定一批已知类别的文本数据集，系统能够提取并保存文本中所涉及的主 要事件的发生时间和地理位置信息。 2 3 门户网站需求分析 2 3 1 限定问题域 正如2 1 小节中所描述的，建立门户网站的目的，是能够将政府部门的政策和研 究统计的信息公布于众，并通过网络采集信息( 如群众意见等) 。门户网站的建设本 身就是一个庞大的课题，涉及到很多方面的知识和技术，这里只是进行简单的初步 模拟。门户网站的基本功能需求如下： 1 ) 用户身份认证功能。只有通过身份认证的合法用户才能够应用网站中提供的 相应功能。 查询信息的功能。合法用户可以在网站上查询上级政府发布的信息。 3 ) 提交政府工作报告的功能。网络用户可以在网上填写并向上级政府部门提交 政府工作报告。 北京工业大学工学硕士学位论文 门户网站用例图描述如图2 3 所示： o 提交报告 图2 - 3 门户网站u c a 图 f i 9 2 - 3 t h e u c a d i a 酽啦o f p 0 n a l s n c 2 3 2 网站功能需求描述 网络用户可以通过浏览器登录政府门户网站，通过身份验证后可以使用网站 所提供的查询和提交功能。 门户网站采用蛋l s 结构( 如图2 - 4 所示) ，系统分为三个层次。 1 数据库层：负责存储系统的各种数据，包括从网上接收的数据、文本数据挖 掘所得的数据等。本系统中的用户管理利用s q l s e r v e r 2 咖作为后台数据库。 2 中间服务层：中间服务层是软件实现的核心。 3 客户端层：在b s 结构的软件中，m 浏览器就是客户端。 图2 - 4 门户网站的体系结构图 f i g2 4t h es y s t e ms 加- c t 咒d i a 群a mo f p 0 n a ls 沁 2 4 本章小结 本章介绍了系统的需求分析。包括政务文本挖掘系统和门户网站两部分。 钵 啦 ) 啪 ) h 盆幕 弋 醐 缈 幽 虿 蕊 ) 鳓 ， _ l ；( 黼 ) 份 争 一 b 一 第3 章中文文本分类算法设计 第3 章中文文本分类算法设计 文本自动分类是文本挖掘中研究最多，应用最为广泛的领域之一。 3 1 文本自动分类概述 文本自动分类是指计算机根据文本的内容，将其自动归到一个或者几个类别中 去。文本数据的来源多种多样可以是报告、单据、新闻、邮件等。文本的类别和 数量可以是预先规定好的，这需要相关专家知识；也可以是不确定的，要经过文本 的自组织、聚类后才能得到。根据是否预先规定文本的类别，自动分类方法还可以 分为有指导的分类w 和无指导的分类：需要预先定义类别体系的文本分类为有指导 的分类，也称为文本自动归类或有监督的分类；类别体系不确定的文本分类为无指 导的分类，也称文本自动聚类或无监督的分类。自动聚类系统不需要训练文本，划 分出的文本类别也是不确定的。本文重点研究有指导的文本自动分类算法。 自动分类中的分类知识的获取方法大致可以分为两种： 一是基于知识工程的方法，一般由知识库和推理机两大基础部分组成。知识库 储存了从专家那里获得的关于某领域的专门知识，推理机具有推理的能力，即根据 知识推导出结论，而不仅仅是简单搜索现成的答案。由于需要由知识工程师手工编 制大量的推理规则作为分类知识，因此其开发费用是相当昂贵的。 二是基于数据的机器学习方法，研究从观测样本出发，寻找规律( 即利用一 些做好标识的训练数据自动地构造分类器) ，利用这些对未来样本进行预测。现有机 器学习的重要理论基础之一是统计学。传统统计学研究的是样本数目趋于无穷大时 的渐近理论，现有学习方法也多是基于大数定律的结论。由于其基于相对简单的机 制以及实际环境中所表现出来的良好性能，而为大部分文本自动分类系统所采用。 从数学角度来看，文本分类是一个映射的过程，它将未标明类别的文本映射到 已有的类别中，该映射可以是一对一的映射，也可以是一对多的映射，因为通常一 篇文本可以同多个类别相关联。在本文中，文本分类是一个一对一的映射过程。 中文文本分类需要解决的关键技术问题如下：中文文本如何表示、分词处理、 文本的特征选择和特征抽取、如何构造分类模型、分类模型如何评估等。 3 1 1 文本表示 文本分类是一种面向语义的操作。实际上，即便是属于同一语义类别的文档， 它们的用词、长短和风格也会大相径庭。这就涉及到一个怎样表示文档才能体现出 它们的用词、长短和风格也会大相径庭。这就涉及到一个怎样表示文档才能体现出 北京工业大学工学硕士学位论文 文档内涵的问题。 文本数据与常见的结构化关系数据不同，它是非结构化的，没有属性值对的 结构，称为无结构或者半结构化数据。对于非结构化的文本数据进行挖掘，目前有 两种处理途径：一是采用全新的算法，直接对非结构化文本数据进行挖掘；= 是将 非结构化文本数据进行转化，将其转化为结构化文本数据，再进行挖掘。由于直接 构造新算法难度较大，而且开发造价高，实现难度较大，所以目前通常采用把非结 构化的文本数据转化为结构化的文本数据的方法。这一问题包括两个方面：用于表征 文档语义的特征和这些特征的组织方式。给定一篇文档，最直观的方法就是使用词 和短语作为表征文档语义的特征。 迄今为止，在中文信息处理方向上，文本的表示“”主要采用向量空间模型m 3 ( v s m ) 。向量空间模型的基本思想是以向量来表示文档。特征项的选取，也就是特征 的提取过程。通常，特征项由文档中一些有代表性的字、词或词组充当，它们是组 成文档，反映文档内容的基本元素，并且在文档中的出现频率有一定的规律性，适 合作为文档的特征表示，但并不是所有的均适合作为文档的特征表示项。从中文信 息处理角度来看，中文文档中出现最多的语词有双字词和三字词。 文本的表示除了上述的向量空间模型外，比较常用的还有布尔模型( b 0 0 1 e a n m o d e l ) m 1 、隐性语义索引( l s d 模型m 1 和概率模型口d 0 b a b i l i s t i c m o d c i ) 嘲。 3 1 2 自动分词 自动分词是针对中文的一种自然语言处理技术。在西方语言体系中，句子中各 个词汇之间有固定的空格作为分隔，计算机处理时可以非常容易地从文本中识别出 一个一个的单词。而在汉语体系中，书写以句子为单位，句间用标点隔开，句内字 词则是连续排列的，之间没有任何分隔。因此，如果要对中文文本进行分类、检索 等基于词的处理，需要首先对中文文本进行词条切分处理( 简称分词) ，才能正确 识别每个词。中文文本的分词处理就是指在中文文本中连续的能够代表语义单元的 词或者n 元词条间加入分隔符，将中文文本的连续字节流形式转化为离散单词流形 式的过程。自动分词技术是各种中文信息处理技术的基础，也是中西文研究文本自 动分类的主要差别所在，中文文本分类要在自动分词的基础上进行，对中文文本进 行分词的过程也是文本特征集的确定过程。分词系统的性能和分词结果，对后面的 分析直接产生影响。 3 1 3 文档的特征选取 由于文本数据的半结构化甚至于无结构化的特点，使得用特征向量对文档进行 表示的时候，特征向量通常会达到几万维甚至于几十万维。即使经过初始化的筛选 第3 章中文文本分类算法设计 处理( 如停用词处理等) 仍会有很高维数的特征向量留下。特别是在中文文本分类 中，通常采用词条作为最小的独立语义载体，原始的特征空间由可能出现在文章中的 全部词条构成，这样高维的特征空间对于几乎所有的分类算法来说都偏大，对分类 机器学习未必全是至关重要的。高维的特性可能会大大增加机器学习的时间而仅产 生与小得多的特征子集相等的学习分类效果。因此文本分类系统应该选择尽可能少 而精，和文本类别密切相关的文本特征进行文本分类，寻求有效的特征选取“”方法， 降低特征空间的维数，提高分类的效率和精度，成为文本自动分类中至关重要的问题。 特征选择( f e a t u ms e l e c t i o n ) 和特征抽取“”0 f e a t u r ed 【t r a c i i o n ) 可以降低特征空间 的维数，从而达到降低计算复杂度和提高分类准确率的目的，并为以后的分类器设 计提供参数。文本特征选择是文本分类的首要任务和关键问题。简单地说，特征选 择是从一组特征中选出一部分最有代表性的特征。据此，特征项应该在某特定类别 文本中的发生频率较高，而在整个文本集合中出现的频率较低的特征词。 特征选择可以在两个方面提高系统性能：一是分类速度，通过特征选择，无用 特征被剔除，可以大大减少特征集合中的特征词数，从而降低文本向量中的特征词 的个数，提高系统运行速度。二是分类精度，通过适当的特征选择，减小了无用特 征对于分类结果的干扰，不但不会降低系统准确性，反而会使系统精确度提高。 特征提取的目的是找到特征项，一般方法是：首先通过构造一个特征评分函数， 。把测量空间的数据投影到特征空间，得到特征空间的值；然后根据特征空间中的值 对每个特征进行评估，特征选择就可以选择特征值最高的若干特征。常见的特征选 择方法有：文档频次。”( d f ：d o c u m e n tf r e q u c n c ) 】，、互信息( m i ：m u t i l a lh 幽仰a t i o n ) 、 信息增益( i g ：h f o 咖a t i g a i n ) ，z 统计量等方法。 3 1 4 文本分类常用算法 分类算法一般基于“词袋模型，即文档被看成是由相互无关的单词构成的词的 集合，不考虑单词之间的上下文关系，单词出现的顺序，位置以及文章的长度等。 统计出每个单词在每篇文档中出现的频率是进行算法建模的基础，统计所有单词在 所有文档中出现的频率得到单词对于文档的词频统计矩阵。迄今，国内外已经有很 多的方法被用于文本分类的训练阶段“3 。，如向量空间模型法、回归模型、k n n 方 法、贝叶斯方法、决策树、启发式规则学习、神经网络、遗传算法”1 、支持向量机 等。 基于向量空间模型的方法啪属于统计学分类法。它创建并训练以文档特征词为分 量的向量空间模型，把一篇未知类别的文档，划归与某类训练文本条件概率具有最 大接近程度的文本类别。为了简化条件概率的计算，该方法假设构成一篇文档的特 征词之间是“互相独立”的。 北京工业大学工学硕士学位论文 鼢州方法”1 是一种基于实例的文本分类方法。首先，对于一个待分类的测试 文本，计算它与训练样本集中每个文本的文本相似度，根据文本相似度找出k 个最 相似的训练文本。这最相似的k 个文本按其和待分类文本的相似度高低对类别予以 加权平均，看这k 个文本中多数属于哪一类，就把待分类的测试文本归属于哪一类。 其中最重要的是参数k 的选择，k 过小，不能充分体现待分类文本的特点；而k 过 大，会造成噪声增加而导致分类效果降低。此算法有简单的优点，但存在问题，需 要将所有样本存入计算机中，每次决策都要计算待识别样本与全部训练样本之间的 距离进行比较。因此计算新文档时存储量和计算量都较大。 贝叶斯分类器。1 分两种。一种是朴素贝叶斯分类器，它假设一个属性对给定类的 影响独立于其他属性，即特征独立性假设。当假设成立时，与其它分类算法相比， 朴素贝叶斯分类器是最精确的。但是，文本属性之间的依赖关系是可能存在的。另 一种是贝叶斯网络分类器。可以考虑属性之间的依赖程度，其计算复杂度比朴素贝 叶斯高得多，但更能反映真实文本的情况。 神经网络方法啪仿照人类神经系统的生理活动过程，把构成某种类别文本的特征 词作为一个神经网络模型的输入，而把模型的输出作为识别文本主题类别的依据， 经过该类训练文本集的反复训练，确定神经网络模型的参数，创建了用于识别该类 文档的一个神经网络模型。 这些方法的相同点是没有利用构成文档词汇之间的各种联系去获取特征词集并 创建分类器。 3 2 文本分类算法的设计与实现 这里提出一种新的文本分类算法应用在系统中。该算法考虑到句子环境对文本 分类过程中的作用，故称之为“基于特征词句子环境的中文文本分类算法”。 任何一篇具有确定主题的文档都是由若干个句子构成的。一个能够用于识别某 类文本的特征词集合，按照文档作者的需要，被分散、有重复地安排在若干中文句 子之中。一个句子是若干个能够识别文本类别的特征词与其它词汇的“混合体”。文 本分类的训练阶段可以看作从构成文档的所有词汇中抽取特征词的过程。因此，在 训练阶段的伊始，不妨把构成文本句子的所有词汇通称为特征词。构成一个句子的 不同特征词之间，需要服从各种语义、语法约束。换句话说，构成一个特定句子的 特征词对内营造一种“和谐”的句子环境，对外馈送一组特有信息。由此想到，识别 某类文本的特征词集合，应该相对集中地分布在文档的若干个句子当中。文本分类 的训练阶段可以利用特征词的句子环境，通过“聚集”呻1 这些句子环境，去发现识别 某类文本的特征词集合。 第3 章中文文本分类算法设计 3 2 1 文本分类的处理流程 自动分类的一般做法是，根据文本数据集的特点构造一个分类器，利用分类器 对未知类别的文本赋予类别。构造分类器的过程一般分为训练和测试两个步骤。文 档集划分为训练集和测试集两个部分。在训练阶段，分析训练集的特点为每一个类 别构造相应的分类模型；在测试阶段，利用分类模型对测试集进行分类，评价分类 模型。一般来说，测试阶段的代价远远低于训【练阶段。文本分类的准确程度受多方 面因素的影响：分类词表和分词算法的不足、分类算法的不足以及知识库的规模不 够大等。 文本分类的两个步骤描述如下： 步骤1 ：训练阶段。使用已知类别的训练文本集，创建文本分类器。 步骤2 ：应用阶段。使用文本分类器，对每一篇未知类别的文档进行分类。 文本分类的处理流程如图3 1 所示： !：训i ! 练： ：，0 阶j p 7l 段； l ；瞄 罨 ；段 图3 1 文本分类系统处理流程图 f i g3 1i h ep m c e s sf 1 0 wd i a g f 锄0 ft c 蔗ta a s s i f i c a t i 叨s y s t e m 1 训练阶段 输入：训练文本集( 已知类别的文本集) 。 处理过程： 文本预处理。 将训练文本集中的每一篇文本通过分词程序将词条切分，保存统计信息。 根据统计信息对文本进行特征选取( 特征选择和提取) ，并用某种方式表 示文本。 学习。学习过程包括构造文本分类器和优化文本分类器两个步骤。 夺构造文本分类器。通过对经过预处理的文本进行学习，为每一个类别 北京工业大学工学硬士学位谂文 静文本我至l 一手孛准确晦分类模塑，牵鼋造分类嚣。 夺优化文本分类器。使用评估文本粲( 已知类别的文本集) 对分类器进 行评估，即用分类器预测评估文本集中每一个文本的擞别。将文本的 分类器预测结果与已知的类标号进行比较，记录评估的结果，并根据 译绩鼙i 暴黠文本分类器优纯。 输躐；文本分类器。 2 应用阶段。它的任务是使用文本分类器对未知类别的文本进行分炎。 输入：未知类别的文本 处理过程；文本预处理 躅文本分类嚣预测文本瓣类剃 输懑：文本懿类剿。 下面介绍用于创建分类飙贝0 的文本句子信息模型，眈较详细地输出使用训练文 本集，利用特征词的句子环燎，获取识别文本童蹶擞别的特征词粜含，创建并优化 分类规则的训练算法。 3 2 2 文零匀子的售惠模型 中文文本中存在各种标点符号，忽略掉其中弓l 号、逗号等甸中符号，通过识别 句号、问号或感叹号等标点符号，一篇中文文档很容易被划分为着干个句子。使用 中文处理专用软件，可以把匈予进一步划分为游于个词汇。把文档躐句子划分为词 汇盼避獠，一般称为分词撩嚣。在文本挖掘系绫申我粕采用静分强系统是由中国语 言支诬大学秀发兹汉语鑫韵矜谲系统；该系统熬将意为：采霜最大耩配法、内部楚 理的文本聚用u n i d e 编码、分词速度可达3 0 刀字，秒、正确率9 9 。 分词操作产生的词汇，缀过简单的词汇“压缩”处理，生成了句子的特征词集合。 3 0 2 1 镏予的构成及其信患鼍 定义l ：s t = w l w 2 隅 是文档的一个訇予。其争，w i 已瞰堪s i ；1 ，乏匐，是擒 成句子s t 的特征词集合。 定义1 中；特征词集合 w 1 ，w 2 ，吣仍然保持关于集合的最原始性质：构成集合 的元素照冤序的。也就是说，在构造文本分类器时，只关注一个甸子由哪些特征词 梅或，藤忽略该每子内帮特援运之阕应该遵循瓣葵它约束( 铡懿，键子靛特征运至 多霰要按照一定先螽次淳关系撵戮，等) 。 设：凼n 篇文档构成的文耥集d 1 0 c 经过分词操作，一共生成了n 个特征词。w 1 w 2 是句子s t 的任意两个特征词，p ( w 。) 和p ( w 2 ) 分别寝示在d o c 文档紧中特征词w ，和 w 2 出现的次数，p ( w l ，w 2 ) 栽深在d o c 文档集中特征词w l 和w 2 同时跚现在一个句子 第3 苹中文文本分类算法设计 中的次数。不难知道，特征词w 1 在每一篇文档中平均出现的次数是p ( w ，) n 。其它关 于特征词出现频率的计算，可以据此类推。 定义2 ：若w 1 w 2 是两个不同的特征词，则1 w ( w ，。2 ) ：! ! 竖兰! 生- 称为特征 词w 1 ，w 2 之间的互信息量。 p ( w 1 ) p ( 贶) 定义2 实际反映了两个不同的特征词w 1 和w 2 同时在文档集的句子中出现次数， 与w t 、w z 在文档集中单独出现次数之间的相对信息量。 设：构成句子s t 的特征词集划分为两个不相交的非空特征词子集w 1 和w 2 ， 即：w l u w 2 = w 1 ，w 2 ，w ) 与w l n w 2 = 巾同时成立。为了方便起见，把非空特征词子 集w 1 和w 2 称为s t 的两个子句，记为s t p a n l 和s t p a n 2 。现引入记号矾f ( s 1 _ ) ， 它代表句子s t 所携带的互信息量。于是，根据定义2 ，应该有以下式子成立： 叮f 佟1 ) = q i 怛p a r t l ) + q f ( s tp a n 2 ) + i ( s t p a n l ，s t p a r t 2 ) 式( 3 一1 ) 其中，i ( s t p a n l ，s t p a n 2 ) 表示所有分别属于s t p a n l 和s t p a n 2 的两个特征词 之间的互信息量之和。即，郧t p a n l ，st p a n 2 ) = z1 w ( w 1 ，w 2 ) ，w 1 s t p a n l ， w 2 st p a n 2 。同时，规定：当s t 只包含一个特征词时，有矾f ( s n = 0 。 3 2 2 2 任意两个句子之间的互信息量相关度 设：构成句子s t l = 聊批，；，) 和s t 2 = 帅，耽，k 的特征词集分别被划分 为两个非空、互不相交的特征词子集。 定义3 ：两个句子s t l 和s t 2 之间的互信息量相关度： r e l ( s t l ，s 1 萄= 【岬t 1 p a r t l ) 一f f q 忱p a r t l ) 】2 + d n f 媾t 1 p 列回一矾唧p a n 2 ) 】2 + ( s t l j a r t l ，趼1 p a r l 2 卜i ( s r 2 p a r t l ，m p a r 回】2 式( 3 2 定义3 给出了句子s t l 与句子s 1 2 在统计意义上的相关性。从式( 3 。2 ) 可以看出， r e l ( s t l ，s 1 劭的值越小，句子s t l 与句子s t 2 之间的统计相关性就越大。或者说， r e l ( s t l ，s 嘲的值越小，句子s t l 与句子s 1 2 统计互信息量的差异就越小。 值得注意的是，如果 w j ，耽，j c 呐，2 ，w j 。( 反之亦然) ，即构成句子s t l 的特征词是构成句子s t 2 特征词的子集，那么，句子s l r 2 完全“覆盖”了句子s t l 的 互信息景。这说明句子s t 2 使用较多的特征词，表达了句子s t l 所没有表达的更丰 富的信息。在这种情况下，如果