（计算机应用技术专业论文）web信息分类与自动摘要的研究.pdf

中文摘要 随着i n t e r n e t 的不断发展，网上的信息极度膨胀，网络用户越来越难以从 信息海洋中快速有效的查找到所需要的信息。为了解决这一难题，要求人们在 i n t e r n e t 这样一个动态变化的环境下对信息进行收集、分析、分类、评价以提 供有效的信息服务。 本文以网页文本信息为研究对象，针对网页信息内容多样、结构复杂的特点， 从理论和应用两个角度对网页文本信息的分类方法和自动摘要做了深入研究。运 用正向最大和逆向最大分词算法对网页提取的文本信息进行分词，使用k - m e a n s 聚类算法，b a y e r s 分类算法对信息进行分类，设计并实现了适合于新闻网页信息 的自动分类器。详细分析了主题词的结构成分，并对所有超文本标记进行分析， 将 等九个重要的标记在进行主题词评价的时候被分配更大的权重，设计 了主题词权重系数公式，结合句子位置信息计算句子得分、根据句子得分利用 l u 州和l s a 算法进行摘要提取，最终设计并实现了一套w e b 自动文本摘要原型系 统。 经实验表明，改进了主题词评价标准后，利用l u 唧、l s a 算法所生成的摘要 与人工摘要相比可以达到7 0 9 6 以上的精确率和召回率；k - m e a n s 算法的精确率可以 达到7 2 5 ，b a y e r s 算法的精确率和召回率都可以达到9 0 以上。 关键词：信息挖掘；自动分类；自动摘要；主题词； a b s t r a c t w i t i lt h er a p i dd e v e l o p m e n to fi n t e r n e t , t h ei n f l a t i o no fw e br e s o u r c e sm a k e s w e bu s e ra c c e s sa s s f u li n f o r m a t i o nm o r ea n dm o r ed i f f i c u l t l y i no r d e rt or e s o l v et h i s p r o b l e m ，w en e e dt oc o l l e c t , a n a l y z e ，c l a s s i f ya n dv a l u ei n f o r m a t i o ni nad y n a m i c c i r c u m s t a n c et op r o v i d eh e l p f u li n f o r m a t i o ns e r v i c e s i nv i e wo ft h ed i v e r s i t ya n ds t r u c t u r ec o m p l e x i t yo fw e bi n f o r m a t i o n ， t h i sp a p e rm a i n l yr e s e a r c ho nc l a s s i f i c a t i o na n da u t o m a t i cs u m m a r y g e n e r a t i o nf o r w e bd o c u m e n t sf r o ma n g i eo ft h e o r ya n da p p l i c a t i o n w i t h 删a n dr m ma l g o r i t h mt os e g m e n tt h et e x te x t r a c tf r o mw e bd o c u m e n t s a n d k - m e a n sc l u s t e r i n ga l g o r i t h mc o o p e r a t i n gw i t hb a y e r sc l a s s i f i c a t i o n a l g o r i t h mt oc l a s s i f yt h ei n f o r m a t i o ne x t r a c tf r o mw e bd o c u m e n t ，a n a u t o m a t i cc l a s s i f i e rf o rw e bd o c u m e n t so fn e w si si m p l e m e n t e d i nt h i s p a p e r ，t h es t r u c t u r ea n di n g r e d i e n to fk e yw o r d ，a n da l lh y p e r t e x tt a g s a r ea l s oa n a l y s e d n i n ei m p o r t a n tt a g sa r ea s s i g n e dw i t hh i g h e rp r i o r i t y ， a n dk e yw o r d sp r i o r i t yc o e f f i c i e n tf o r m u l ai sd e s i g n e d t h e nas c o r eo f s e n t e n c ea c c o r d i n gt ot h ep o s i t i o no ft h es e n t e n c ei sc a l c u l a t e d w i t h t h es c o r eo fs e n t e n c e sa n dl u h n ，l s aa l g o r i t h m s ，w ee x t r a c tt h es u m m a r y f r o md o c u m e n t s ，a n df i n a l l yi m p l e m e n t sa na u t o m a t i cw e bd o c u m e n t ss u m m a r y e x t r a c t i o ns y s t e m a c c o r d i n gt oe x p e r i m e n t ，a f t e ri m p r o v e m e n to fk e yw o r d se v a l u a t i o n ， t h es u m m a r yg e n e r a t i o nu s i n gl u h na n dl s aa l g o r i t h m sc a nr e a c h7 0 o f a c c u r a c ya n dr e c a l lr a t e ，7 2 5 u s i n gk - m e a n sa l g o r i t h m 。a n d9 0 9 6u s i n g b a y e r sa l g o r i t h m k e y w o r d s ：d a t a m i n i n g ；a u t o m a t i cc l a s s i f i c a t i o n ；a u t o m a t i cs u m m a r i z a t i o n ； t h e m a t i cw o r d s ； 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得丞洼太堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：彳苏 签字日期：别年7 月日 学位论文版权使用授权书 本学位论文作者完全了解丞洼太堂有关保留、使用学位论文的规定。 特授权云洼去堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：莎以 签字日期：凇形年7 月多日 导师签名： 签字日期： 易日 第章绪论 第一章绪论 1 1 课题研究的背景和意义 随着i n t e r n e t 的迅速发展，我们真正迎来了信息爆炸时代。越来越多的学 术集体将自己研究领域的成果放在了i n t e r n e t 上，同时各行各业的学术页面更 是数不胜数。这样导致w e b 信息的信息量极为宠大，这些海量的信息中蕴含着巨 大潜在有价值的知识。 w w 包含了从技术资料、商业信息到新闻报道、娱乐信息等多种类别的信息， w w 以其丰富多彩的内容吸引了大量的用户。w w w 是开放性的全球分布式网络，资 源分布在全球不同的地方，并且网上资源没有统一的管理和结构，导致了信息查 找的困难，如何从信息海洋中查找到自己所要的信息成为困扰网络用户的一大难 题。面对网络上信息的数量和种类的高速增长，而其中经过加工的知识却相对匮 乏，人们在运用网络获取信息时遇到了一些无法避免的困难。一方面信息过度膨 胀，而另一方面用户却找不到所需要的信息。如何在i n t e r n e t 这样一个动态变化 的环境下对各种信息进行收集、分析、分类、评价并提供有效的信息服务成为目 前的一个研究热点。 文本分类技术是网络信息挖掘中内容挖掘的重要手段之一，通过文本的分类 技术可以将网络中纷繁复杂的信息分门别类的组织在一起，从更深的层次来寻找 文档之间的联系，不只停留在字面的匹配上。文本分类技术应用于信息检索中有 利于提高检索的正确率和准确率。 文本分类方法也可以应用到检索结果的组织上。h e a r s t 等人的研究，已经证 明了聚类假设。即与用户查询相关的文档通常会聚类得比较靠近，而远离与用户 查询不相关的文档。因此，可以利用文本分类技术将搜索引擎的检索结果划分为 若干个簇，每一个簇都可以有一个明显的主题，用户只需要考虑那些相关的簇。 大大缩小了需要浏览的结果数量。此外，在网络信息处理中应用文本分类技术还 可以起到加速处理的过程和提供个性化信息处理的作用。 另外，随着电子出版系统和国际互联网络的蓬勃发展。当大量机读形式的文 献潮水般涌来的时候，从而促使了人们想到了自动文摘。 自动摘要就是利用计算机自动地从原始文献中提取文摘m ，。摘要是准确全面 地反映某一文献中心内容的简洁连贯的短文。摘要的目的在于产生一个言简意垓的 第一章绪论 文件描述，它应比文件标题更具叙述性，但又短的可让人一目了然。所以自动摘要技 术的研究是很有意义的： 提高文摘杂志的时效。文摘杂志是一种二次出版物，人工编制文摘成本 高、效率低，从原始文献的出版到文摘的出版往往有相当长的时差。自 动编制文摘不仅可以缩短加工文献和编辑时间，较及时地给用户提供文 献线索，而且成本大大降低。 促进电子出版物的发展：国际互联网蓬勃发展，大量的文献以机读形式 出现，网上信息极大丰富。要想在信息的海洋中找到所需信息，不仅需 要先进的信息检索技术，还应该拥有一个能自动压缩信息甚至自动提炼 信息的智能系统。 实现快速阅读的要求：人们要了解某一领域的知识，往往要翻阅许多文 献。一个好的自动摘要系统可以为读者提供文献的概要与精华，这对读 者快速选择文献与快速阅读了解文献内容是很重要的。 综上，如何对w e b 信息进行分类及形成自动摘要的研究成为了一个亟待解决 的问题。 1 2 论文的主要研究内容 网络上所面临的上述问题，如何快速准确的找到所需要的信息，提高效率是 我们目前面临的一个难题。本文通过系统研究文本分类技术、中文分词技术、自 动摘要技术、分类算法、文本摘要算法、分词算法的基础上，对这些算法一一的 加以实现，并对这些算法的性能做了分析和评价。本文的主要工作可以概括为以 下几个方面： 对w e b 分类技术做了综合的概述，包括网页文件的特点以及如何解析出文 本字段，文本的向量空间表示以及文本的降维技术，并对两个重要的分类 算法k - m e a n s 和b a y e s 做了深入研究。在j b u i l d e r 的环境下利用j a v a 语言实现这两种算法。并通过对网上的根据人工标准分类的新闻进行聚类 或分类测试。在测试中我们用了1 0 组文档来测试。例如其中的一组：由 四类经过人工分类的文档，根据类别按照不同的目录保存于源文档目录 中，利用k - m e a n s 算法( 随机选取种子) ，将种子数量设定为4 ，得出的 一个聚类结果，精确率达到7 2 5 。同样的b a y e r s 的分类方法，利用预 设的分类器类似的数据测试可以得到精确率达到9 3 2 。 第一章绪论 阐述了中文分词的相关问题及基于字符串的分词算法，并给出了a s m 分词 算法模型；基于统计的分词算法，并给出了n 元模型。在j b u i l d e r 的环 境下利用j a v a 语言实现了正向最大匹配法和逆向最大匹配法，并与 i c t c l a s 进行了比较，能很好的保证词语完整性。 阐述了自动摘要的关键技术，针对网页文档结构的特点，详细研究了对分 析主题词的重要性有贡献的结构成分。然后，根据主题词利用l u h n 和l s a 算法进行摘要提取研究。在j b u i l d e r 的环境下利用j a v a 语言实现自动摘 要l u h n 算法、l s a 算法，并将生成的结果与手工摘要的结果相比较有精确 率和召回率都在7 5 以上。 1 3 论文的结构 本文的结构是如下安排的： 第一章阐述了w e b 信息分类与自动摘要技术的背景、意义。并说明了本文的 主要研究内容。 第二章介绍当前的信息分类技术和文本摘要相关技术及研究现状，包括w e b 信息分类和中、外自动摘要技术的发展现状。 第三章阐述了w e b 信息分类的关键技术与算法，包括w e b 文档的解析，文本 表示、降维技术等，算法实例主要是两个重要的分类算法k - m e a n s 和b y a s e 。 第四章阐述了自动摘要的关键技术，包括分词技术和分词算法及摘要算法。 第五章在j b u i l d e r 的环境下利用j a v a 实现分词算法( 正向最大匹配、逆向 最大匹配) 、分类算法( k - m e a n s 、b a y e s ) 和摘要算法( l s a ，l u h n ) 。并对这些 算法做出了评价和分析。 第六章对本文的研究工作进行总结，提出存在问题，并对未来该领域研究 前景做出展望。 第二章文献综述 第二章文献综述 2 1w e b 信息分类的研究现状 自动分类研究开始于上世纪5 0 年代，h p l u h n 在这一领域进行了开创性的研 究，他提出了用于自动分类的词频统计思想。1 9 6 0 年m a r o n 发表有关自动分类的 第一篇论文；1 9 6 2 年博科( h b o r k o ) 等人提出利用因子分析法进行文献的自动分 类。其后k s p a r c kg s a l t o n 以及r m n e e d h a mm e l e s kk s j o n e s 等众多学者 在这一领域进行了卓有成效的研究工作。概括起来他们主要从文本的词频统计分 析、句法分析、语义分析等三个层次上进行研究。其中，以基于词频统计分析的 自动分类试验较为成功。 上世纪8 0 年代末日本庆应义塾大学文学系的图书情报专业和日本i b m 东京基 础研究所合作开发了一个自动分类专家系统，该专家系统基于日本十进分类法啪 实现了图书资料的自动分类。自上世纪9 0 年代以来随着世界范围内出现了一轮又 一轮的数字图书馆研究热，国外计算机界和图书情报界陆续展开了对因特网信息 资料、自动分类的研究。相关研究项目包括： 北欧w a i s 万维网自动分类项目“1 。该项目由瑞典伦德大学图书馆和丹麦 国立技术图书馆合作进行探讨，利用机读版国际十进分类法实现因特网 资源自动标引的可能性。 诺伊斯等人的概念分析试验，主要是利用分面分类法。1 和概念分析等手 段来组织因特网资源。 日本的国际十进分类法数字自动组合系统u d c - a u t c s ，主要是利用著名的 国际十进分类法u d c 进行自动分类试验。 用于分类体系自动交叉参照”1 的基于知识的系统k b s - c r o s s ，该项目就建 筑学领域在u d c 和l c c ( 美国国会图书馆分类法) 之间进行交叉参照目标是 解决因特网资源使用中的多语种问题。 对于w e b 信息而言，由于w e b 数据缺乏结构化信息导致w e b 信息发现比 较困难，传统的搜索引擎如：l y c o s ，a 1 t av i s t a ，w e b c r a w l e r 为用户在 w e b 中寻找需要的信息提供方便，但是这些搜索引擎普遍不提供结构信 息、分类信息。因此，在近期的研究中发现有关研究上更多的信息检索 第二章文献综述 的智能工具，针对w e b 内容有以下几种：智能搜索a g e n t ：w e b 数据挖掘 系统利用特定的领域特性来组织和解释所发现的信息并进行相关的搜 索。 信息分类( i n f o r m a t i o nc l a s s i f i c a t i o n c a t e g o r i z a t i o n ) ：使用各种 搜索技术和w e b 文档的自动特性自动检索，过滤和分类w e b 信息。 个人w e b 代理( p e r s o n a l i z e dw e ba g e n t s ) ：这一方式能够了解用户的 喜好并根据用户和同类型用户的喜好发现w e b 信息资源。 基于数据库方式：集中从w e b 中的半结构化数据抽取结构化数据集。 2 2 自动摘要的研究现状 2 2 - 1 外文自动文摘的研究现状 自动文摘技术的研究与自动分类技术一样，始于2 0 世纪5 0 年代末，i b m 公司的 l u h n 首次设计了一个自动文摘系统。1 9 5 8 年，他发表了第一篇有关文摘的自动 生成方法的文章，拉开了自动编制文摘的序幕。此后出现一些著名的重要的研究 成果，比较著名的工作有：i b m 公司a c s l - - m a t i c 项目的研究；e d m u n d s o n 等人的 工作及t r w 公司的研究，7 0 年代由俄亥俄( o h i o ) 州立大学r u s h 等人开发的a d a m 自动文摘系统，8 0 年代未到9 0 年代初g e 公司p s j a c o b s 和lf r a u 等人开发的 s c i s o r 系统和a n e s 系统，以及欧洲的d a g st u h ls e m i n a r 研究小组的工作 ( j o n e s ，1 9 9 5 ) 。 进入9 0 年代以来，随着i n t e r n e t 的开通，自动文摘的价值充分显露出来。引起 了世人的极大关注，越来越多的学者纷纷开始从认知心理学、情报科学、计算语 言学等各个方面展开研究，提出了实现自动文摘的新的思路和方法，自动文摘的 研究进入了前所未有的繁荣期，研究的系统更趋于大规模和实用化。涌现出了很 多研究小组，著名的如m i t r e 公司的i n d e r j e e tm a n i 和e r i cb l o e d o m ，卡奈基梅 隆大学的j a d eg o l d s t e i n 和j a i m ec a r b o n e l l 等人。1 9 9 3 年1 2 月在德国w a d e r n 召 开了历史上第一次以自动文摘为主题的国际研讨会。1 9 9 5 年，国际期刊 i n f o r m a t i o np r o c e s s i n g & m a n a g e m e n t 出版了一期题为s u m m a r i z i n gt e x t 的专刊， 编者在序言中指出，这一期专刊的出版标志着自动文摘时代己经到来。 迄今为止的自动文摘系统主要经历了以下两个阶段：基于统计的机械文摘和 基于意义的理解文摘”1 。l u h n 0 1 在1 9 6 5 年提出了一种基于文章表面级特征的经典 的摘要算法l u h n 算法。这种算法的核心思想是为文章中的每一个句子赋予一个意 第二章文献综述 义值那些具有最大意义值的句子将会被抽取出来作为摘要，其中句子的意义值 是通过句中意义词的个数计算得到的。l u h n 认为意义词应该是文章中的“中”频 词集。高频词区域中的词多是一些过于普通的词，没有什么区分能力，这些无用 词可以通过停用词表的构造得以消除。另外，潜在语义分析也已经被成功的应用 到信息检索和其他一些领域当中。它的成功源于它能够将词以及与之相关的概念 表示为高维的语义空间中的点。在文本摘要领域，6 0 n 9 0 1 已经成功的将l s a 应用 到文本摘要中。本文的第四章将继续讨论l u h n 和l s a 算法。 2 2 2 中文自动文摘的研究现状 我国从8 0 年代未开始介绍国外自动文摘方面的研究情况“，同时开始研究 自动文摘实验系统，一方面，汉语和西文主要区别是汉语词间没有空格，因而存在 着自动分词问题。汉语自动分词是一项经过多年研究仍未圆满解决的难题。因为 汉语中真正负载信息的是词而不是字，所以如果分词技术能够满足大规模真实文 本处理的需要，那么以词为基础的自动文摘必然优于以字为基础的自动文摘1 。 实际上，大多数中文文摘系统都要对文本进行分词处理，只是由于采用的分词方 法不同，使得分词精度有所不同。此外，汉语的词汇极为丰富，同一个概念可以用 很多不同的词汇表达，这给词频统计带来了一定的困难。上海交通大学王永成教 授从8 0 年代末就开始研究自动摘录技术，1 9 9 7 年研制了o a 中文文献自动摘要系 统。该系统集成了位置法、指示短语法、关键词法和标题法等多种方法。是一个 实用的系统“1 。 另外在语言的深层结构方面，汉语存在一些有别于西文的特点。比如。汉语缺 乏词形的变化，增加了句法分析的难度：汉语有一些特殊的句式，如兼语、连动等。 采用理解的方法研究中文文摘，必须充分考虑汉语的特点。8 0 年代末，沈阳东北 大学姚天顺教授和香港城市理工大学联合开展了“中文全文自动摘要系统”的研 究，该系统采用脚本知识表示，通过与用户交互获取文摘“6 ”。 哈尔滨工业大学王开铸教授于1 9 9 2 年研制了基于自然语言理解的军事领域 的自动文摘实验系统m a t a s “”，1 9 9 4 年研制了自动摘录类的h i t 2 8 6 3i 型自动文摘 系统”和h i t 2 8 6 3i i 型自动文摘系统。 近两年来，从事这项研究的单位不断增加。北京邮电大学信息工程系钟义信 教授等人采用基于多a g e n t 技术的文摘方法，类似于p a i c e 的选择与生成文摘法， 目前主要针对计算机病毒方面及新闻报道方面的相关文章，开发出了g l a n c e 自动 文摘系统及n e w s 自动文摘系统等”“。山西大学郭炳炎教授等人也在开展自动文 摘的研究，他们采用了基于统计的方法分析文本结构。复旦大学吴立德教授”1 研 第二章文献综述 制的自动文摘系统，分析了篇章段落之间的联系，建立了语义网，具有一定的篇章 理解能力，能给出任意长度的摘要。北京邮电大学信息工程系钟义信教授采用的 文摘方法类似于p a i c e 的选择与生成文摘法，目前主要针对计算机病毒方面的文 章。据悉微软亚洲研究院和i 酬中国研究中心也在加紧研究中文自动文摘产品。 第三章w e b 信息分类的关键技术与算法设计 第三章w e b 信息分类的关键技术与算法设计 文本分类是指在给定分类体系下，根据文本内容自动确定文本类别的过程 ，将大量的文本归到一个或多个类别中。从数学角度来看，文本分类是一个映 射的过程，将未标明类别的文本映射到已有的类别中来，数学表示如下：f ：a - b 其中a 为待分类的文本集合，b 为分类体系下的类别集合。 2 0 世纪9 0 年代以前，占主导地位的文本分类方法一直是基于知识工程的分 类方法，即由专业人员手工进行分类。人工分类非常费时，效率过低。9 0 年代以 来，众多的统计方法和机器学习方法应用于自动文本分类。文本分类技术的研究 引起了研究人员的极大兴趣。目前英文自动分类已经取得了丰硕的成果，提出了 多种成熟的分类方法，如最近邻分类、贝叶斯分类、决策树方法以及基于支持向 量机( s ) 、向量空间模型( v s m ) 、回归模型和神经网络等方法，但对于中文文本 的自动分类技术研究尚不尽人意。目前国内中文文本分类研究主要集中在朴素贝 叶斯“”、向量空间模型嗍乜7 1 和支持向量机1 等技术上。 为了有效的处理和组织海量的w e b 信息，需要实现网页的自动分类，自动分 类是快速、有效组织网络上海量信息的一个重要技术。 3 1 文本信息分类的关键技术 3 1 1 网页特点与解析 i m 也简介 h t m l 文件是什么? h t m l 表示超文本标记语言( h y p e rt e x tm a r k u pl a n g u a g e ) 。 h t m l 文件是一个包含标记的文本文件。 这些标记控制浏览器怎样显示这个页面。 h t m l 文件必须有h t m 或者h t m 扩展名。 h t m l 文件可以用一个简单的文本编辑器创建。 b t m l 实际上是普通的文档，没有图形，动画，声音等，但包含了指向这些 类型文件的”指针”或链接。使得w e b 页面包含这些非文本因素。h t m l 本身是由 标识h t m l 文档元素和特性标志( t a g ) 和属性( a t t r i b u t e ) 构成的代码系统。 第三章w e b 信息分类的关键技术与算法设计 它们一起用于标识各个文档部件，告诉浏览器如何显示文档。标志通过指定某块 信息为段落或标题等来标识文档部件。属性是标志的选项，在标志中修饰或进一 步指定信息，比如颜色，高度，宽度等。 所有的h t m l 都应该至少包括有五个结构标志。如图3 一l 所示： ( h t 誓l h e d ( h e b o d y e ( c ji x ) ，l _ ，朋，f ( 3 一1 0 ) 这样，最大化p ( g i x ) 。其中p ( c f i x ) 最大的类c 称为最大后验假定。 根据贝叶斯定理可以得到： p ( c ，= 警 ( 3 1 1 ) 3 、 由上式可知，由于p ( x ) 对于所有的类别均为常数，只需要p ( c jl p ( c f ) 取得最大值即可。如果类的先验概率未知，则通常假设各个类别是等概 率的，即尸( c 1 ) = p ( c 2 ) = = p ( q ) 。这样就只需求e ( x l q ) 的最大值， 类的先验概率可以用p ( c j ) = 鲁计算，其中，墨是类c 中的样本数，s 是 样本的总数。 4 、 如果数据的属性很多，计算e ( xe ) 的开销可能会非常大。为降低计算 e ( xic j ) 的开销，假定各属性值相互条件独立，在属性之间不存在依赖 关系。即p ( x i q ) = f i p ( 耳i q ) 。 b l 5 、 对于一个未知样本数据x ，对每个类别c ，计算j p ( ql 椰以c i ) 。样本x 属于类别c ，当且仅当e ( x ic f ) p ( c f ) p ( x i c ，) p ( c ，) ，l ，m ，j i 也就是，x 被指派到其p ( ei x ) p ( c ，) 最大的类c 。 朴素贝叶斯算法的本质1 是用词和类别的联合概率估计给定文档属于各个 类别的概率。它假设，一个词在给定类别的条件概率独立于该类的其它词的条件 概率。这样，就以降低分类精度的代