（管理科学与工程专业论文）面向信息检索的智能分类方法研究.pdf

山东师范大学硕士学位论文 面向信息检索的智能分类方法研究 摘要 随着互联网技术的不断发展，i n t e r n e t 上的信息日益丰富，已经成为人们日 常工作和生活中获取信息的重要来源。但是，由于i n t e r n e t 所固有的开放性和异 构性，用户很难从纷繁复杂的海量信息中准确定位到自己所需要的信息。因此， 如何合理有效地组织和管理i n t e r n e t 上的信息，已经日益成为信息处理领域一个 十分重要的研究课题。面对w e b 上的海量信息，传统的做法是对网上信息进行人 工分类，并加以组织和整理，为人们提供一种相对有效的信息获取手段。但是， 这种人工分类的做法存在许多弊端：一是耗费大量的人力、物力和财力。二是存 在分类结果一致性不高的问题。即使分类人的语言素质较高，对于不同的人分类， 其分类结果仍然不尽相同。甚至同一个人，在不同时间做分类也可能会有不同的 结果。因此，人们对网页智能分类技术的需要越来越迫切。 本文在研究传统信息检索技术实现的同时，结合现有的网页分类技术，对网 页智能分类进行了较为系统的研究。在此基础上对面向信息检索的智能分类中的 网页预处理、中文分词、特征提取、网页分类提出了一定的思考和见解。 本文的主要创新点： ( 1 ) 针对网页结构的特点，分析了网页中对分类过程有贡献的信息成分，改进 了从中文网页内自动清除“噪音”并提取正文的行之有效的方法。 ( 2 ) 研究了现有网页源代码的特点，把网页表示成树型层次结构，每个叶子节 点赋予不同的权重：在传统的特征词权重计算公式的基础上，考虑了特征词的长 度和特征词出现的位置两个因素，提出了基于网页标签树型层次结构的特征词权 重计算公式。 ( 3 ) 介绍了传统的特征提取算法，并在z 2 统计量的基础上，对z 2 统计量公式 做了两点改进。 ( 4 ) 研究了现有的网页分类方法。k n n 分类算法为了找到与测试文本距离最近 ( 最相似) 的k 篇文本，需要穷尽搜索整个训练集，在训练样本数较多或者表示样 本的特征向量维数较高时，计算复杂性就很高。针对这问题，本文在粒子群算 法的基础上，提出了一种智能快速寻找新文本的x 个近邻的p s o k n n 算法。 ( 5 ) 对i g 、m i 、c h i 、c h i 木四种统计量的实验结果做出了评价。通过实验证明 本文所采用的特征词提取方式，在一定程度上，能够得到较高的分类准确率，存 山东师范大学硕士学位论文 在一定的合理性。 关键词：信息检索中文分词特征提取智能分类k n n 分类算法 分类号：t p 3 9 山东师范大学硕士学位论文 in t eilig e n tcia s sific a tio nm e t h o dr e s e a r c ho n jn f o r m a tio nr e t rie v ai a b s t r a c t w i t ht h ec o n t i n u a ld e v e l o p m e n to fi n t e r n e tt e c h n o l o g y ，t h ei n f o r m a t i o n o fi n t e r n e tism o r ea n dm o r er i c h ，w h i c hh a sb e c o m ea ni m p o r t a n tr e s o u r c e o fh u m a na c q u i r i n gi n f o r m a t i o ni nd a i l y1 i f ea n dw o r k w h i l ef o r t h e i n t r i n s i co p e n n e s sa n di s o m e r i s mo fi n t e r n e t ，i t i sv e r yd i f f i c u l tf o ru s e r t oe x a c t l yp o s i t i o nt h e i rr e q u i r e di n f o r m a t i o na m o n gn u m e r o u sa n d c o m p l i c a t e di n f o r m a t i o n ，t h e r e f o r e ， h o wt or e a s o n a b l ya n da f f e c t i v e l y o r g a n i z ea n dm a n a g e i n t e r n e ti n f o r m a t i o nh a sb e c o m eav e r yi m p o r t a n t r e s e a r c hs u b j e c td a yb yd a yi ni n f o r m a ti o np r o c e s s i n gr e a l m f o rt h e n u m e r o u si n f o r m a t i o no fi n t e r n e t ，t h et r a d i t i o n a lo p e r a t i o ni st op r a c t i c e m a n u a lc l a s s i f i c a t i o n ，o r g a n i z ea n dp r o c e s s i n ga n do f f e rp e o p l er e l a t i v e l y e f f e c t i v ei n f o r m a t i o na c q u i s i t i o nm e t h o d b u t ， t h em a n u a lc l a s s i f i c a t i o n h a sm u c hd is a d v a n t a g e ：o n eist h ec o n s u m p ti o no fn u m e r o u sm a n p o w e r ， m a t e r i a lr e s o u r c e sa n df i n a n c i a lr e s o u r c e s t w oi st h e1 0 wc o n s i s t e n c yo f c l a s s i f i c a t i o nr e s u l t e v e nc l a s s i f y i n gp e o p l eh a sh i g h1 a n g u a g eq u a li t y ， d i f f e r e n tp e o p l ec l a s s i f y ，t h ec l a s s i f i c a t i o nr e s u l t w i l lb ed i f f e r e n t ： e v e ns a l t l ep e o p l ew h oc l a s s i f ya td i f f e r e n tt i m e ， d i f f e r e n tr e s u l tw i l l a p p e a r s ot h er e q u i s i t i o nu p o ni n t e l l i g e n tc l a s s i f i c a t i o no nw e bi s b e c o m i n gm o r ea n dm o r ee x i g e n t w h i l er e s e a r c h i n gt h er e a l i z a t i o no ft r a d i t i o n a li n f o r m a t i o nr e t r i e v a l t e c h n i q u e ，t h ed o c u m e n tc o m b i n e sa c t u a lw e bc l a s s i f i c a t i o nt e c h n i q u e ，m a k e m o r es y s t e m a t i cr e s e a r c h i n go nw e bi n t e l l i g e n tc l a s s i f i c a t i o n u n d e rt h e b a s i s ， t h ed o c u m e n tb r i n gf o r w a r d ss o m et h o u g h ta n do p i n i o no nw e b p r e t r e a t m e n t ，c h i n e s ep a r t i c i p l e ，f e a t u r es e l e c t i o na n d w e bc l a s s i f i c a t i o n i ni n f o r m a t i o nr e t r i e v a li n t e l l i g e n tc l a s s i f i c a t i o n m a i ni n n o v a t i o ni nt h ed o c u m e n t ： 1 f o c u s i n go nw e bs t r u c t u r ec h a r a c t e r ， t h ed o c u m e n ta n a l y z e st h e 山东师范大学硕士学位论文 i n f o r m a t i o nf a c t o r st h a th a sc o n t r i b u t i o no nc l a s s if i c a ti o na n di m d r o v e s t h ee f f e c t i v em e t h o dt h a ta u t o m a t i c a l l ye l i m i n a t e“n o i s e f r o mc h i n e s e w e ba n de x t r a c tt e x t 2 t h ed o c u m e n tm a k e sr e s e a r c ho nt h ec h a r a c t e ro fa c t u a lw e bs o u r c e c o d e ，e x p r e s sw e ba st r e e h i b e r a r c h y ， a n de n d o wd if f e r e n tw e i g h to ne v e r y l e a f sn o d e ：o nt h eb a s i so ft r a d i t i o n a lc h a r a c t e rw o r d w e i g h t c a l c u l a t i o nf o r m u l a ，t h ed o c u m e n tt h i n ko v e rt h el e n g t ha n da p p e a r i n g p o s i t i o no fc h a r a c t e rw o r dt ob r i n gf o r w a r dc h a r a c t e rw o r dw e i g h t c a l c u l a t i o nf o r m u l ao nt h eb a s i so fw e bl a b e lt r e eh i b e r a r c h v 3 i ti n t r o d u c e st r a d i t i o n a lc h a r a c t e re x t r a c t i o na r i t h m e t i c a n dm a k e s t w oi m p r o v e m e n t so n z 2s t a t i s t i c a lm a g n i t u d ef o r m u l ao nt h eb a s i so f z 2s t a t i s t i c a lm a g n i t u d e 4 i tr e s e a r c h e sa c t u a lw e bc l a s s i f i c a t i o nm e t h o d s k n nc l a s s i f i c a t i o n a r i t h m e t i c ，i no r d e rt of i n dkt e x tw i t hs h o r t e s td i s t a n c e ( m o s ts i m i l a r ) t ot e s t e dt e x t ，r e q u i r e st os e a r c ht h et o t a lt r a i n i n gc o l l e c t i o n w h e nt h e r e i sh i g h e rt r a i n i n gs a m p l en u m b e ro rh i g h e rc h a r a c t e r i s t i cv e c t o rd i m e n s i o n ， t h ec a l c u l a t i o nc o m p l e x i t yi sv e r yh i g h f o c u so nt h ep r o b l e m ，t h ed o c u m e n t b r i n gf o r w a r d足n e i g h b o r i n gp s o k n na l g o r i t h mo ni n t e l l i g e n ta n df a s t s e a r c h i n gn e wt e x to nt h eb a s i so fa l g o r i t h mo fp a r t i c l es w a r m 5 i tm a k e sa p p r a i s a lo nt h et e s t i n gr e s u l to f4s t a t i s t i c a lm a g n i t u d e o fi g 、m i 、c h i 、c h i 水，t h r o u g he x p e r i m e n t ，i tp r o v e st h a tt h ec h a r a c t e r i s t i c w o r de x t r a c t i o nm e t h o d a d o p t e d i nt h ed o c u m e n tc a n a c q u i r eh i g h e r c l a s s i f i c a t i o na c c u r a c yr a l ea n dh a sc e r t a i nr al j o n a l t yo nc e r t a i nd e g r e e k e yw o r d s ： i n f o r m a t i o nr e t r i e v a lc h i n e s ep a r t i c i p l e f e a t u r es e l e c t i o n i n t e l l i g e n tc l a s s i f i c a t i o n k n nc l a s s 【f i c a t i o na r i t h m e t i c c 1 a s s i f i c a t i o n ：t p 3 9 i v 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名： 曙多澹 导师签 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：游声暇 导师签字 签字日期：2 0 0 8 年芗月彩日签字日期：2 0 0 8 年多月2 细 山东师范大学硕士学位论文 1 1 研究背景 第一章引言弟一早j 苗 近年来随着工n t e r n e t 技术的不断发展，w e b 也得到了迅猛的发展，海量的数 据在给用户提供了大量信息的同时，也增加了用户检索信息的难度。搜索引擎作 为传统的信息检索工具，由于搜索的内容比较繁杂，导致用户查询的结果存在大 量的无关信息，降低了查询的精度和效率。因此出现了基于分类的智能信息，并 且成为w e b 应用发展的新课题。 随着计算机软硬件水平的不断提高，i n t e r n e t 己经发展成为拥有数亿用户和 上亿个站点、数十亿个网页的巨大的分布式信息存储空间，而且目前仍以每4 至6 个月翻一番的速度迅猛增加。( 据统计，目前工n t e r n e t 上的w e b 页面已经达到了 1 0 0 多亿。) i n t e r n e t 为我们的工作和生活带来了巨大的便利，它使我们突破了工 作和地域上的限制，方便地共享资源，但在如此庞大的信息库里查找资料，用户 往往显得力不从心。 面对w e b 上的海量信息，传统的做法是对网上信息进行人工分类，并加以组 织和整理，为人们提供一种相对有效的信息获取手段。但是，这种人工分类的做 法存在着许多弊端：一是耗费大量的人力、物力和财力。二是存在分类结果一致 性不高的问题。即使分类人的语言素质较高，对于不同的人分类，其分类结果仍 然不尽相同。甚至同一个人，在不同时间做分类也可能会有不同的结果。因此， 人们对网页自动分类技术的需要越来越迫切。网页自动分类是处理海量网页的有 效手段，它能提供网页集的良好组织结构，简化网页的存取和操作，提高网页处 理效率，网页自动分类及其相关技术的研究也正日益成为研究热点。网页自动分 类技术是当今信息检索和情报检索的一个重要研究课题，在数字存储技术日益普 及的今天，应用的范围十分广泛，例如：数字图书馆、电子邮件分类、新闻分类、 文本检索等等。本文从机器学习的观点出发，系统地研究了面向信息检索的智能 分类中所涉及到的网页预处理、中文分词、特征提取、网页分类等问题，并在此 基础上，提出了一定的思考和见解。 1 2 网页智能分类研究现状 网页自动分类的研究自上世纪8 0 年代互联网兴起以后才逐渐发展。由于文本 山东师范大学硕士学位论文 m e t a 标记中的n a m e 属性值和c o n t e n t 属性值是对网页主题的描述，网页中的超链 接指向的内容有可能是与该网页主题相关的内容，这些信息都对网页分类有贡献， 也可能存在噪声，综合利用上述特征设计分类算法是网页分类的关键，也是难点 所在； ( 5 ) 缺乏评价标准：对于网页分类系统，目前还没有统一的评价标准，常用的 评价指标有准确率和召回率。网页的数量极其巨大，单纯的召回率已经没有实际 价值，准确率的意义也要作相应的变通；数据库规模，索引方法，用户界面，响 应时间等也应该纳入评价体系，作为评价指标。 此外，文本分类中存在的些问题，如特征选择、分类器效率等问题同样会 给网页分类带来影响。 1 4 本文的工作及内容安排 网页自动分类也称为在线文档分类( o n l i n ed o c u m e m sc a t e g o r i z a t i o n ) ，通过分析 被分类网页的特征，并与各类别中网页所具有的共同特征进行比较，将被分类网 页划归为特征最接近的一类并赋予相应的类别。传统上，网页分类是由人来完成 的，即人在分析了网页的内容后，给它一个比较合适的类别。很明显，这需要大 量的人力资源。随着网页信息的快速增长，特别是w 曲上各种信息的迅速增加以 及网页结构的多样化，仅靠人工的方式来处理是不切实际的。同时，由于分类可 以在较大程度上解决目前网上信息杂乱的现象，并方便用户准确地定位所需信息， 因此，网页自动分类己成为一项具有较大实用价值的方法，是组织和管理数据的 有力手段。 就目前的研究来看，网页自动分类的准确率还不高，但网页自动分类的研究 对基于内容的信息检索、w r e b 挖掘以及各种基于w 曲的应用有着深远的意义。本 文在研究传统信息检索技术实现的同时，结合现有的网页分类技术，对网页智能 分类进行了较为系统的研究。在此基础上对面向信息检索的智能分类中的网页预 处理、中文分词、特征提取、网页分类提出了一定的思考和见解。 本文的结构安排如下： 第一章：引言，介绍网页分类的研究现状、存在的问题以及论文研究的目的 和意义。 第二章；信息检索与智能分类，介绍信息检索的定义、信息检索系统的分类 以及文本文类的基本概念、智能分类在信息检索中的应用。 第三章：网页预处理及中文分词，首先针对网页结构的特点，分析了网页中 山东师范大学硕士学位论文 对分类过程有贡献的信息成分。提出了从中文网页内自动清除“噪音”并提取正 文的行之有效的算法。介绍了传统的中文分词算法及本文使用的基于分词词典( 常 用词词典) 的字符串匹配算法。 第四章：文本表示模型及特征提取算法，该章内容首先介绍了常见的文本表 示模型及文本特征表示方法，并对其优缺点进行了分析，其次研究了现有网页的 特点，把网页按h t m l 标签表示成树型层次结构，每个叶子节点赋予不同的权重； 在传统的特征词权重计算公式的基础上，考虑了特征词的长度和特征词出现的位 置两个因素，提出了基于网页标签树型层次结构的特征词权重计算公式。再次介 绍了传统的特征提取算法，给出了一种改进的z 2 统计量公式。 第五章：智能分类技术的研究，研究了现有的网页分类方法，在粒子群算法 的基础上，提出了一种智能快速寻找新文本的足个近邻的p s o k n n 算法，并对i g 、 m i 、c h i 、c h i * 四种统计量的实验结果做出了评价。 第六章；结论与展望。总结了目前研究中的缺陷与不足，明确了下一步研究 的方向。 4 山东师范大学硕士学位论文 查全率是指信息检索系统检索到的相关文档占被检索文档集中所有相关文档 的比重，可以用下面的公式计算：r 。f r 尺口f f 。其中r 是搜索到的相关文档数， 疋，是被检索文档集中所有的相关文档数量。一个系统的查全率越高，则说明它发 现相关文档的能力越强。 查准率是指信息检索系统检索到的所有文档中相关文档所占的比率，可以用 如下公式计算：尺肌删们= 剐d 。其中r 是搜索到的相关文档数，d 是检索到的文 档数。一个系统的查准率越高，则其检索到的信息噪声越低。 用户输入关键词是希望得到内容与关键词特征相匹配的网页，但是搜索引擎 把含有关键词但内容不相符的网页也返回了。分类目录揭示了网页之间的内容相 关性，通过分类可以很轻松地排除掉内容没有相关性的搜索结果，关键词检索和 网页分类检索相结合，可以大大提高信息检索效率。 2 。3 文本分类的基本概念 网页分类中，比较核心的仍然是文本自动分类技术。文本自动分类的研究涵 盖若干学科领域，包括语言学中的自然语言处理，图书情报学中的分类学，数学 领域的统计学，以及计算机领域的模式识别、人工智能、神经网络等研究方向。 简单地说，文本分类口2 3 的任务是：在给定的分类体系下，根据文本的内容自动 地确定文本关联的类别。从数学角度来看，文本分类是一个映射的过程，它将未 标明类别的文本映射到已有的类别中，该映射可以是一对一映射，也可以是一对 多映射，因为通常一篇文本可以同多个类别相关联。用数学公式表示如下： 厂：彳一b其中，彳为待分类的文本集合，b 为分类体系中的类别集合 文本分类的映射规则是系统根据已经掌握的每类若干样本的数据信息，总结 出分类的规律性而建立的判别公式和判别规则。然后在遇到新文本时，根据总结 出的判别规则，确定文本相关的类别。 从数据挖掘的角度来说，自动分类是一个有监督( s u p e r v i s e dl e a r n i n 彰的学 习过程。在这个学习过程中，它根据一个已经被人工处理过的训练文本集合 ( t r a i n i n gs e t ) 去挖掘出文本属性和文本类别之间的关系模型，然后根据学习得 到的这种关系模型对新到来的文本测试集合进行自动的类别判断。这一过程可以 用形式化语言描述如下n 3 1 ： 假设有一组文本概念类c 利一组训练文本d ，则客观上存在一个目标概念r ， 使得r ：d c 。这里，丁把一个文本实例映射为某一个类。对于d 中的文本d 而 山东师范大学硕士学位论文 言，r ( d 1 是己知的：通过有监督地对训练集的学习，可以找到一个近似于丁的模 板日，并满足h ：dj c ，针对一个新文本z ，则日( z ) 表示对巧的分类结果。因此， 一个分类系统的建立或者说分类学习目的就是寻找一个和丁最相似的模板h ，即 给定一个评估函数厂，学习的目标应该使丁和满足： m i n m i f 曼印( z ) 一日( z ) ) ( 2 3 1 ) l ( 丁( z ) 一日( z ) ) l ( 2 3 1 一1 因此，文本的自动分类，简言之，就是先学习找到一个分类模板，然后根据 该模板对新的文本进行分类。 2 。4 智能分类在信息检索中的应用 对新到的网页文本自动指出其所属的类别的智能分类本身可视为自然语言处 理的一种应用。目前w e b 页数量海量，类型各异，并且不断的动态变化和增长。 为了有效的查找用户所需要的信息，需要将传统的信息检索向w e b 信息检索( 搜索 引擎) 方向发展。搜索引擎之所以面临比一般信息检索更大的困难，在于新的信息 检索需求呈现以下新的特征：( 1 ) 待检索文本的数量是海量的；( 2 ) 待检索的文本是 异构的；( 3 ) 待检索文本的数量是动态变化的；( 4 ) 待检索的文本可能有重复；( 5 ) 待检索的文本可能是跨语言的；( 6 ) 包含有指向其他w e b 文本( 资源) 的链接；( 7 ) 在网络环境下，面对的是大量用户不同 x 山东师范大学硕士学位论文 正需要的信息，并且便于用户进一步在检索结果中进行相关检索。另一方面，用 户的兴趣可能不在于提交一个对系统的查询，而是愿意花一些时间来浏览w e b 文 本空间中自身感兴趣的内容，或者是当其对所希望了解的领域知之甚少时，希望系 统能有一个提醒。因为搜索引擎假设用户知道自己要检索什么，所以用户可以比 较轻松的给出查询的关键字。然而在现实的信息利用中，还存在着这样一种情况， 即用户不知道查询的具体关键字，只知道大概的领域；如果有网页文本的预先分 类，则可以使用户顺着这样的目录层次找下去，逐步引导用户到所需要的信息领 域。这样的分类体系是用户浏览网页很好的起点。一个很好的例子是y a h o o 的层 次目录。与之相类似还有o p e nd i r e c t o r yp r o j e c t ，它用在a 1t av i s t a ，n e t s c a p e ， h o t b o t ，l y c o s 等系统中。但是他们都还是人工进行分类，而不是机器自动进行分 类。因此，文本智能分类( 这里指机器的自动分类) 大大降低了人力，提高了效率。 不需要再聘用专门的“通才型 专家一篇篇阅读进行人工分拣，而且毕竟这种方 法在海量的动态变化的w e b 文本信息面前是相当吃力的“引。 9 山东师范大学硕士学位论文 3 1 网页预处理 第三章网页预处理及中文分词 网页是一种半结构化的文本文件，通常都包含大量的“噪音”，譬如：大量的 t a g 标签和超级链接以及各类广告设计人员的注释以及版权声明等和内容无关的 信息，这些“噪音影响了网页分类的质量，因此，需要对网页信息进行预处理， 去掉网页中多余的t a g 标签，尽可能地提取网页中对分类有用的文字部分。 为了有效地剔除网页中的噪音信息，得到有用内容，首先要了解网页的基本 结构和特点。目前普遍使用h t m l 语言作为创建w e b 页面的语言。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 文件是标准的a s c ii 文件，与普通文本不同的是，它加入了很多h t m l 标签，这些标签对应于h t m l 语 言中的不同元素( e l e m e n t ) ，用于组织文件的内容和指导文件的输出格式。绝大多 数元素是“容器 ，即它有起始标记和结尾标记。在起始链接标签和结尾链接标签 中间的部分是元素体。 3 1 1 网页的基本结构 l o 下图是一个网页页面的典型结构以及其对应的树型层次结构： 图3 1 1 一个网页页面的典型结构以及其对应的树型层次结构 山东师范大学硕士学位论文 数字4 、3 、2 、1 - 8 、1 5 表示处于t i t l e 、 等这些特殊标签内的特征词的权重。 h t m l 标签经常是嵌套关系，比如h t m l 标签的元素体部分又包含h e a d 和b o d y 标签而h e a d 标签的元素体部分又包含t i t l e 标签。实际上，一个规范的网页页面 的代码往往对应于一颗树型层次结构，如图3 1 1 ，h t m l 标签为树根，各个不含 任何标签的文本块成为该树型结构的各个叶节点。 3 1 2 网页特点分析 对网页实现自动分类，首先要对其中的有用信息进行提取。在了解网页基本 结构的基础上，通过对网页特点进行进一步的分析，发现有用信息存在于以下结 构中n 司： ( 1 ) 标题 标题是存在于 和 标记中的内容。标题中的内容与网页主题的 关系非常密切，通常是对一个网页内容的高度概括，我们在信息提取时，首先提 取了网页标题，并在后续的分词，特征提取过程中，给这部分的词赋予一定的权 重。 ( 2 ) 关键词 在网页的头部 与 之间可以使用m e t a 标签说明页面的关键词， 如： ，这些关键词对文章类别的决定程 度高于页面的其他有效词语，通常由人工提取，因此可信度相当高。 ( 3 ) 网页正文 网页正文被定义在标记 和 之间，其间包括广告、相关链接、正 文和版权信息等内容，是最能表现网页说明内容的文字。除了少数专业网站外， 绝大部分主要用自然语言书写。由于不同的人有不同的网页编写风格，导致了网 页格式的千差万别。但是，我们通过对大量的网页观察，发现一篇有主题网页中 的正文通常是用成段的文字来描述，中间通常不会加入大量的超链( 也就是处于标 签 和 之间的文字部分) 。而非正文信息通常是伴随着超链出现的( 也就是处 在 和 之间的文字部分) 。因此在网页预处理过程中，我们去除了所有处于 标签 和 之间的文字以及网页的说明文字。 ( 4 ) 相关链接 相关链接用来指向与页面主题相关的页面。规范的网站一般都会在网页中提 供相关链接给浏览者，但页面中也包含了许多与主题不相关的链接，如广告等。 山东师范大学硕士学位论文 如何判断一个链接是否是相关链接成为比较困难的工作。在本文的研究中，我们 忽略了相关链接对文本分类的作用。 ( 5 ) h t m l 语言中的标签 通过仔细观察我们可以发现整个网页中对分类有用的正文内容信息均分布在 h t m l 标签之外，而且，在h t m l 标准中定义的标签主要是用来特殊显示其包含的内 容( 比如：字体变大、粗体、斜体、以超链形式显示，等等) 或处理脚本等其他功能， 那么这部分信息对于中文网页的自动分类来说意义并不是很大。 针对以上网页特点的分析，本文提出了从中文网页内自动清除“噪音”并提 取正文的行之有效的算法。 s t e p l ：提取需要做加权处理的内容 每个网页都可表示成如图3 1 1 所示的典型网页结构或者是其对应的树型层 次结构，提取网页标题、关键词、 和 之间、 和 之间、 和 ( n = 1 ，2 ，3 ) 之间的元素体内容，并在后续的分词，特征提取过 程中，给这部分的词赋予一定的权重。 s t e p 2 ：去除注释及超链接信息 经研究发现9 5 以上的网页都会有相关的注释( 包括：作者、日期、公司信息 等) ，这部分是我们首先要去除的噪音。为此，首先找到注释的结束符，即“一 ” 标记，对于这类标记的处理只需找到结束符并将整个注释部分去掉即可。网页的 超链接处于标签 和 之间，在遍历过程中，找到标签 和 并把标签 和 及之间的内容整个去掉。 s t e p 3 ：去除h t m l 语言中的标签 顺序扫描网页源代码的每个字符，通常“ 。 s t e p 4 ：罩复步骤2 、3 直到网页末尾，那么这时通过扫描后存储的那部分就是该 网页的正文内容。 通过以上方法可以消除h t m l 代码中的不规范标记，为后面的进一步处理带来 方便。 3 。2 中文分词技术 3 2 1 中文分词概述 1 2 在对中文网页进行了预处理之后，也就实现了网页格式向文本格式的转换。 山东师范大学硕士学位论文 中文自动分词是对中文文本进行自动分类的第一步。汉语最基本的独立单位是汉 字，但是能够独立活动的具有一定语义的最小单位是词。词是由单个或多个汉字 构成，一般用得最多的是二字词，其次是单字词，另外还有一些多字词( 如成语、 专有名词等) 。中文词的如下特点，给中文分词带来了许多困难和挑战。 ( 1 ) 数量多。汉语中常用的词有几万条，现代汉语词典中收录的词就达6 万多个。随着社会的发展，许多新词还在不断地出现。 ( 2 ) 用法灵活，变化多样，容易产生歧义。同样的两个连续汉字，在有些语义 环境下是一个词，而在别的语义环境下可能是两个词，或者不是词，在不同的语 义环境下，词的词性也会发生变化。人可以通过自己的知识根据上下文环境判断， 而计算机在识别的时候就会难以区分。 ( 3 ) 汉字同音词多，语法尚末形成规范化，而且人们习惯于非规范化的语法。 ( 4 ) 书写习惯问题。英文词与词之间在书写上用空格隔开，计算机处理时可以 非常容易的从文档中识别出一个一个的词；中文词与词之间在书写上没有空格隔 开，而是在句子间用标点符号隔开。在一句话内，字和字之间是连续的，它们之 间没有任何明确的分隔符号。 因此必须进行词的切分处理，将汉字串切分为正确的词串，即中文分词，以 正确的识别出每一个词。 3 2 2 中文分词技术 中文分词属于自然语言处理范畴，是中文文档分类的前提，分词的效果能够 直接影响后续的分类效果。目前的汉语分词主要有三类算法：基于字符串匹配的 分词方法、基于理解的分词方法和基于统计的分词方法乜钉乜5 m 町瞳7 m 2 8 j 。 ( 1 ) 基于字符串匹配的分词方法 这种方法又叫做机械分词方法，也叫做基于词典的分词方法，主要思想是： 事先建立一个词典，对待切分的字符串，按照己经确定的策略，与词典中的词汇 进行匹配，若在词典中找到某个字符串，则匹配成功，即识别出一个词，否则继 续下一步的匹配，直到所有汉字串都被成功地切分出来。按照扫描方向的不同， 串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况， 可以分为最大( 最长) 匹配和最小( 最短) 匹配；按照是否与词性标注过程相结合， 又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分 词方法如下： 1 ) 正向最大匹配法( 由左到右的方向) ： 山东9 币范大学硕士学位论文 法是未来中文自动分词方法的发展方向。 ( 3 ) 基于统计的分词方法 从中文的形式上看，词是由稳定的字组合而成的，因此在上下文中，相邻的 汉字同时出现的次数越多，就越有可能是一个词。因此字与字相邻共现的频率能 够较好地反映是否为词的概率。当字符串的紧密程度高于某一个阙值时，便可认 为此字符串是一个词。这种方法只需对语料库中的字符串组合频率进行统计，不 需要事先建立词典，因而又叫做无词典分词方法。 基于统计的分词方法的优点是：提供了消歧的方式，处理自然语言具有很好 的一致性和健壮性。该方法的缺点是：低频词很难被切分出来，同时经常抽出一 些共现频度高、但并不是词的常用字组。 3 2 3 中文分词的难点 有了成熟的分词算法，是否就能容易的解决中文分词的问题呢? 事实远非如 此。中文是一种十分复杂的语言，让计算机理解中文语言更是困难。在中文分词 过程中，有两大难题一直没有完全突破托3 2 们。 ( 1 ) 歧义识别 歧义是指同样的一句话，可能有两种或者更多的切分方法。例如：白天鹅， 因为“白天 和“天鹅 都是词，那么这个短语就可以分成“白天鹅”和“白 天鹅，这种称为交叉歧义。像这种交叉歧义十分常见，其实就是因为交叉歧义引 起的错误。“化妆和服装 可以分成“化妆和服装”或者“化妆和服装”。由 于没有人的知识去理解，计算机很难知道到底哪个方案正确。交叉歧义相对组合 歧义来说还算是比较容易处理，组合歧义就必需根据整个句子来判断了。例如， 在句子“教室的门把手坏了 巾，“把手 是个词，但在句子“请把手拿开中， “把手就不是一个词；在句子“他是一名中将 中，“中将”是个词，但在句子 “产量三年中将增长两倍”中，“中将 就不再是词。这些词计算机又如何去识别? 如果交叉歧义和组合歧义计算机都能解决的话，在歧义中还有一个难题，是 真歧义。真歧义意思是给出一句话，由人去判断也不知道哪个应该是词，哪个应 该不是词。例如：“乒乓球拍卖完了”，可以切分成“乒乓球拍卖完了”、也可切 分成“乒乓球拍卖完了 ，如果没有上下文其他的句子，恐怕谁也不知道“拍卖 在这里算不算一个词。 ( 2 ) 未登录词识别 未登录词，也就是那些在字典中都没有收录过，但又确实能称为词的那些词。 山东师范大学硕士学位论文 最典型的是人名，人可以很容易理解句子“王军虎去广州了 中，“王军虎 是个 词，因为是一个人的名字，但要是让计算机去识别就困难了。如果把“王军虎” 做为一个词收录到字典中去，全世界有那么多名字，而且每时每刻都有新增的入 名，收录这些人名本身就是一项巨大的工程。即使这项工作可以完成，还是会存 在问题，例如：在句子“王军虎头虎脑的”中，“王军虎”还能不能算词? 未登录词中除了人名以外，还有机构名、地名、产品名、商标名、简称、省 略语等都是很难处理的问题，而且这些又f 好是人们经常使用的词，因此对于搜 索引擎来说，分词系统中的未登录词识别十分重要。目前未登录词识别准确率已 经成为评价一个分词系统好坏的重要标志之一。 3 2 4 停用词库 在文本预处理过程中，我们自定义了一个停用词库存放停用词，停用词就是 一些在文章中起着辅助作用的词，这些词在表达文章内容上没有很大的作用，比 如一些虚词、助词、连词、感叹词等。停用词库中的词我们可以按字母顺序存储， 这样只需要匹配与自己首字母相同的词，降低了时间复杂度。 部分“停用词库 如图所示： a i啊阿哎哎呀哎哟唉俺俺们按按照 b ：吧吧哒把罢了被本本着比比方比如鄙人彼彼此 边别别的别说并并且不比不成不单不但不独不管 不光不过不仅不拘不论不怕不然不如不特不惟不问不只 c ：朝朝着趁趁着乘冲除除此之外除非除了此此间此外从从而 d ，打待但但是当当着到得的的话等等等地第叮咚对对于 多多少 e 。而而况而且而是而外而言而已尔后 f i 反过来反过来说反之非但非徒否则 g ；嘎嘎登该赶个各各个各位各种各自给根据跟故敌此固然 图3 2 1 部分停用词库 3 2 5 本文采用的中文分词算法及流程图 本文采用的中文分词算法是基于分词词典( 常用词词典) 的字符串匹配算法， 其分词过程如下： 1 6 山东师范大学硕士学位论文 第四章文本表示模型及特征提取算法 4 1 文本表示模型及其优缺点分析 文本本身词汇庞大杂乱，并不适合对其直接进行文本分类，我们利用自然语 言处理技术对文本进行处理，将所有的文本用一个统一的标准模型来表示。目前 常用的文本模型主要有布尔模型、概率模型、向量空间模型。 4 1 1 布尔模型 布尔模型乜朝是基于特征项的严格匹配模型。首先建立一个仅能取值为t u r e 或 者f a l s e 的二值特征变量的集合，文本用这些特征变量来表示，这些特征变量对 应于文本的特征项。如果文本中出现相应的特征项，则特征变量取值为“t u r e ”， 否则取值为“f a l s e ”。查询由特征项和逻辑运算符“a n d ”、“0 r ”和“n o t ”组成。 文本与查询的匹配规则遵循布尔运算的法则。 布尔模型的主要优点是：运算简单速度快，易于表达一定程度的结构化信息， 如同义关系( 电脑0 r 微机o r 计算机) 或词组( 文本a n d 过滤a n d 系统) 。其缺点 是：其检索策略基于二值判定，文本要么与查询相关，要么不相关，没有级别的 变化，不能实现部分语意的匹配；简单的逻辑运算符“a n d ”、“0 r 和“n o t 难 以准确的表达用户的查询请求。 4 1 2 概率模型 概率模型是基于概率排序原则，对于给定用户查询q ，对所有文本计算概率， 并从大到小进行排序，概率公式为p ( 尺id ，q ) 。其中，r 表示文本d 与用户查询q 相关，尺表示文本d 与用户查询q 不相关，有尸( 尺ld ，q ) + 尸( 尺ld ，q ) = l ，也就 是用二值形式判断相关性。 把文本用特征向量表示：x = ( ，而，h ) 。其中，为特征项的个数，葺为o 或1 ，分别表示特征项f 在文本中出现或不出现。 概率模型主要优点在于：从理论上讲，文本可以根据它们的相关的概率按递 减顺序排列。主要缺点足：( 1 ) 需要最初把文本分成相关的和不相关的集合；( 2 ) 山东师范大学硕士学位论文 不考虑特征词在文本中出现的频率，即所有的权值都是二值的；( 3 ) 假设特征词之 间互相独立。 对于大规模动态增加的网页集合，很难用一个概率模型来精确地描述其概率 分布