（计算机软件与理论专业论文）面向行业搜索引擎的web文本挖掘技术研究.pdf

基于信息抽取的中国人名搜索引擎 摘要 随着网络信息技术的发展、i n t e r n e t 应用的逐渐普及，w w w 已经成为一个巨 大的信息存储、发布空间。但由于其数据的无结构化、无索引、异构性的特点， 使得人们很难充分利用其丰富的信息。怎样在浩如烟海的信息中找出自己真正 感兴趣的话题，就必须进行w e b 文本挖掘，w e b 文本挖掘成了数据挖掘的一个很 有前途的研究方向。本文以甘肃省自然科学基金“面向行业主题层次聚类搜索 引擎的实现”的研发为背景，实现了面向人名的聚类搜索引擎，重点研究了聚 类搜索引擎的w e b 文本分类聚类技术。在研究过程中，本文在充分学习研究前人 工作的基础上，结合i r ( i n t e r n e tr e t r i v a l ) 和信息抽取及数据挖掘的相关知 识，提出了补偿式信息抽取的主题文本分类算法，实现了面向人名的聚类搜索 引擎的w e b 文本挖掘的过程。与v i v i s i m o 相比，由于这是一种针对面向行业领域 的应用，其分类聚类的效果非常好，实践证明这是一种行之有效的方法。 关键字：搜索引擎数据挖掘w e b 文本挖掘信息抽取文本分类 自然语义理解 基于信息抽取的中国人名搜索引擎 a b s t r a c t a l o n gw i t ht h ed e v e l o p m e n to ft e c h n o l o g yi nn e t w o r ki n f o r m a t i o na n dt h eg r a d u a l p o p u l a r i z a t i o no fi n t e r a c ta p p l i c a t i o n w w wh a sa l r e a d yb e c o m eah u g ei n f o r m a t i o ns t o r a g ea n d i n f o r m a t i o np u b l i s hs p a c e h o w e v e r b e c a u s et h ed a mh a v et h ec h a r a c t e r i s t i c so fn o n - s t r u c t u r e ， n o n i n d e x , w eh a r d l yt , k s ei t sa b u n d a n ti n f o r m a t i o nf u l l y i no r d e rt od i s c o v e ra l li n t e r e s t i n gt o p i c i nt h ev o l u m i n o u si n f o r m a t i o n ，w eh a v et od os o m er e s e a r c hw o r ki nw e bt e x tm i n i n g ，w h i c hh a s b e c o m eap r o m i s i n gr e s e a r c hd i r e c t i o ni nd a t am i n i n g ，b a s e do n “g a n s up r o v i n c en a t u r a l s c i e n c e sf u n d f a c ep r o f e s s i o na p p l i c a t i o ns e a r c he n g i n e ”，w eh a v ed e v e l o p e dac h i n e s e n a m e - o r i e n t e ds e a r c he n g i n ea n ds t u d i e dt h et e c h n o l o g yo fc l a s s i f y i n ga n dc l u s t e r i n go ft h e w e bt e x ts e a r c he n g i n e i nt h i sr e s e a r c hp r o c e s s ，w ed e e p l ys t u d i e dp r e d e c e s s o r s w o r kw h i c hi s t h ef o u n d a t i o no fo u rl a t l e rw o r k ，u t i l i z i n gm i m e dk n o w l e d g eo fi r ( i n f o r m a t i o nr e t r i e v a l ) ，t h e i n f o r m a t i o ne x t r a c t sa n dt h ed a t am i n i n g ，w ep r o p o s e dc o m p e n s a t e di n f o r m a t i o ne x t r a c t i o n t e x tc l a s s i f i c a t i o n ( c i e t c ) ，a n dc o m p l e t e dt h ep r o c e s so fs e a r c he n g i n eo fw e bt e x tm i n i n g f a c e dt h ep e r s o n a ln a m e s c o m p a r e sw i t hv i v i s i m o ，b e c a u s et h i si sa f ta p p l i c a t i o nf a c e dt h e p r o f e s s i o nd o m a i n , t h ec l a s s i f i e da n dc l u s t e r i n gr e s u l ti se x t r e m e l yg o o d t h i si sa ne f f e c t i v e m e t h o dw i t hp r a c t i c a b i l i t yw h i c hh a sb c c np r o v e db yt h ep r a c t i c e k e y w o r d s ：s e a r c he n g i n e ；i n f o r m a t i o ne x t r a c t i o n ；t e x tc l a s s i f i c a t i o n ；i n f o r m a t i o n e x t r a c t i o n ；n a t u r a ll a n g u a g em e a n i n g ；d a t am i n i n g 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导舞的指导下独立进行 研究所取得的成果。学位论文中凡引用他人已经发表或未发表的成 果、数据、观点等，均已明确注明出处。除文中已经注明引用的内容 外，不包含任何其饱个人或集体巴经发表或撰写过的辩研成果。对本 文的研究成果做出重要贡献的个人和集体，均已在文中以明确方式标 明。 本声裴的法律责任由本入承担。 论文作者签名： 日期： 五妒z 占、1 - 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属兰州大学。本 人完全了解兰州大学有关保存、使用学位论文的规定，同意学校保存或向国家有关部门 或机构送交论文的纸质版和电子版。允许论文被查阅和借阅：本人授权兰州大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相关的学术论文或成 果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 超三6 ，厶，j 面向行业搜索引擎的砸b 文本挖掘技术研究 第一章绪论 1 1 本文研究的背景( 现状) 和意义 1 1 1 研究背景 随着互联网的高速发展，网上的信息越来越多，用户要在信息海洋里查找 信息，就像大海捞针一样。搜索引擎技术的出现恰好解决了遮一难题( 它可以 为用户提供信息检索服务) 。人们希望通过网上信息检索迅速快捷地找到自己 所需要的信息，而这时传统的搜索引擎的弊端就逐渐显露出来。比如说，你在 百度上输入一个人名，常常会找到成百上千个网页，其中- - d , 部分和你的检索 需求有关，而其他大部分检索结果和你的检索需求无关，由于每个网页都很长， 你必须逐一阅读这些网页才能找到真正的答案，这就是我们经常所说的r i c h d a t a ，p o o ri n f o r m a t i o n 。因此传统的搜索引擎已不能满足人们的需求。 因而新的信息检索方式和搜索引擎呼之欲出，将基于面向行业搜索引擎的 w e b 文本挖掘技术应用至第四代搜索引擎雹中去就可以使用户更快捷地找到所 需信息。 1 1 2 国内外研究现状分析 目前国外一些有实力的大公司和科研机构正在探索新的技术，在这方面最 成功的搜索系统是美国垤订s i m 。冒公司的搜索引擎，网址为：h t t p ：。 v i v i s i m o c o r n 。它对搜索到的网页进行分类聚类，方便用户查找，但是在 中文方面做的效果不理想。 国内来说还没有类似的搜索引擎系统出现。 对于信息抽取，中国主要有中科院、北京大学、哈工大在进行这方面的研 究。 1 1 3 研究意义 面向行业搜索引擎的眦文本挖掘技术研究 互联网是一个多种语言、多种文化交汇碰撞的地方，每个国家都在积极探 索解决本国语言信息处理的问题，随着中国的网络用户的不断增加和国力的日 益增强，汉语很有可能成为互联网上的第二大语言，因此继英文后中文搜索引 擎也将具有无限的应用前景。 互联网上的信息又是开放的，这等于说任何一个用户都拥有海量的信息， 因此目前信息时代竞争的关键已不是占有信息的多少，而是谁能够以最快的速 度准确而详尽的获得自己真正想要得到的信息。正所谓把握时间就是把握成 功，谁如果能以最快的速度把握新的信息，谁就能成功的把握先机，或是在商 战中领先对手。 综上所述，探索新型的，更高效、更人性化的搜索引擎已具有十分重要的 意义。而基于信息抽取的搜索引擎的发展势必为广大网络用户带来更高效快捷 的信息服务，也将会带来互联网上的又一大革命。 1 2 本论文的主要工作 本论文就是针对以上的背景，对现有的搜索引擎进行尝试性的改革。项目 的目标是通过w e b 信息提取等技术开发针对某一主题的搜索引擎，目前我们针 对中国人名这一主题，并且我们的搜索引擎是一个元搜索引擎，建立在百度搜 索引擎搜索结果的基础上。我们以目录树的形式将最终搜索结果展现给用户， 提供更准确快速的检索服务，方便用户找到他想找的人。其中基于w e b 信息提 取的文本挖掘是一个底层模块，主要用在之后的网页的分类上，它的任务是从 网页中提取人的相关属性后结合文本分聚类技术将文档分类。 1 3 本论文的主要内容 1 3 1 w e b 数据挖掘概述 首先我们将在第二章中我们将对有关w e b 文本挖掘的技术进行阐述。 1 3 2 中文w e b 文本挖掘关键技术介绍 在第三章中，将详细介绍中文w e b 文本挖掘的相关技术，并介绍系统中用 到的一些相关技术。 2 面向行业搜索引擎的髓文本挖掘技术研究 1 3 3 面向人名搜索引擎的文本聚类研究 在第四章中给出所研究系统的整体框架，接着给出系统运行的总体流程。 并举例分析整个系统的工作过程，详细介绍了系统实现的工作步骤，并对每个 步骤地具体实现细节作了全面的分析。 面向行业搜索引擎的肛b 文本挖掘技术研究 2 1 w e b 数据挖掘概述 第二章w e b 数据挖掘 随着以数据库、数据仓库等数据仓储技术为基础的信息系统在各行各业的 应用，使海量数据不断产生。随之而来的问题是如此多的数据让人难咀消化， 无法从表面上看出他们所蕴涵的有用信息，更不用说有效地指导进一步的工 作。如何从大量的数据中找到真正有用的信息成为人们关注的焦点，数据挖掘 技术也正是伴随着这种需求从研究走向应用。 近年来，随着i n t e r n e t w e b 技术的快速普及和迅猛发展使各种信息可以 以非常低的成本在网络上获得，由于i n t e r n e t w w w 在全球互连互通，可以从中 取得的数据量难以计算而且i n t e r n e t w w w 的发展趋势继续看好，特别是电子 商务的蓬勃发展为网络应用提供了强大支持，如何在删这个全球最大的数据 集合中发现有用信息无疑将成为数据挖掘研究的热点。 w e b 挖掘指使用数据挖掘技术在w 州数据中发现潜在的、有用的模式或信 息。w e b 挖掘研究覆盖了多个研究领域，包括数据库技术、信息获取技术、统 计学、人工智能中的机器学习和神经网络等。 2 2 w e b 挖掘方法及流程 与传统数据和数据仓库相比，w e b 上的信息是非结构化或半结构化的、动 态的、并且是容易造成混淆的，所以很难直接以w e b 网页上的数据进行数据挖 掘，而必须经过必要的数据处理。典型w e b 挖掘的处理流程如噶： 2 2 1 查找资源 任务是从目标w e b 文档中得到数据，值得注意的是有时信息资源不仅限于 在线w e b 文档，还包括电子邮件、电子文档、新闻组，或者网站的日志数据甚 至是通过w e b 形成的交易数据库中的数据。 2 2 2 信息选择和预处理 4 面向行业搜索引肇的啊文本挖掘技术研巍 任务是从取得的w e b 资源中剔除无用信息和将信息进行必要的整理。例如 从w e b 文档中自动去除广告连接、去除多余格式标记、自动识别段落或者字段 并将数据组织成规整的逻辑形式甚至是关系表。 2 。2 3 模式发现 自动进行模式发现。可以在同一个站点内部或在多个站点之间进行。 2 2 4 模式分析 验证、解释上一步骤产生的模式。可以是机器自动完成，也可以是与分析 人员进行交互来完成。 w e b 挖掘作为一个完整的技术体系，在进行挖掘之前的信息获得i r ( i n f 。r l i l 8 t i 。nr e t r i e v a l ) 襞和信息抽取i e ( i n f 。r f f b t i 。ne x t r a c t i 。n ) 襞相当 重要。信息获得( i r ) 的目的在于找到相关w e b 文档，它只是把文档中的数据 看成未经摊序的词缱的集合，两信息抽取( i e ) 的目的在于从文档中找到需蒙的 数据项目，它对文档的结构台表达的含义感兴趣，它得一个重要任务就是对数 搬进行组织整理势适当建立索引。 信息获得( i r ) 和信息抽取( i e ) 技术的研究己近有很长时问，随着w e b 技 术的发展，基于w e b 技术的i r 、i e 褥到了更多的重视。由于w e b 数据量非常大， 而且可能动态变化，用原来手工方式进行信息收集早已经力不从心，目前的研 究方向是用自动化、毕喜动化的方法在w e b 上避彳亍i r 和i e 。在w 曲环境下既要处 鞣非结构化文档，又要处理半结构化的数据，最近几年在这两方面都有相应的 磷究戒果和具体应用，特别是在大型搜索引擎中得嚣了很好豹应用。 2 。3 。w e b 擦掘分类及各皇的研究现及发展 根据对w e b 数据的感兴趣程度不同，w e b 挖掘一般可以分为三类：w e b p q 容 挖掘( w e bc o n t e n tm i n j n g ) 、w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 、w e b 用法挖掘( w e bu s a g em i n i n g ) ，见图2 1 。 面向行业搜索引摹的祀b 文本挖掘技术研究 图2 1w e b 挖掘的分类 2 3 1 w e b 内容挖掘 指从w e b 容、数据、文档中发现有用信息，它是数据挖掘技术在网络信 息处理上的应用，主要方法有i r ( i n f o r m a t i o nr e t r i e v a l ) 和数据库方法。 它又可分为w e b 文本挖掘和w e b 多媒体挖掘两种数据挖掘方式。其中针对无结构 化文本进行的w e b 挖掘被归类到基于文本的知识发现( k d t ) 领域，也称文本数 据挖掘或文本挖掘，是w e b 挖掘中比较重要的技术领域，也引起了许多研究者 的关注。最近，w e b 多媒体数据挖掘方面的研究成为另一个热点。 2 3 2 w e b 文本挖掘 w e b 内容挖掘多为这种方式的挖掘，它和平常的平面文本挖掘的功能及方 法比较类似。w e b 文档多为h t m l 、x m l 等自然语言，因此可利用w e b 文档中的标 记，利用这些信息可以提高w e b 文本挖掘的性能。在对w e b 文档进行分类分析中， 可以基于一组预先分好的文档为每一类文档赋予一个类标签。由于超链接里包 括了有关页面内容的高质量信息，因此可以利用这些信息对文档进行分类，并 且这种分类比基于关键字的分类更加准确。 2 3 3 w e b 多媒体挖掘 随着网络带宽的扩大，多媒体信息在网上迅速增加，这对w e b 容挖掘提 出了新的要求。w e b 多媒体挖掘的挖掘主要是指基于音频的挖掘、基于图片的 静态图像的挖掘和基于视频的动态图像的挖掘。 6 面向行业搜索引擎的w e b 文车挖掘技术研究 w e b l 匈容挖掘一般从两个不同的观点来进行研究。从资源查找( i r ) 的观 点来看，w e b f q 容挖掘的任务是从用户的角度出发，怎样提高信息质量和帮助 用户过滤信息。而从d b 的角度讲w e b 内容挖掘的任务主要是试图对w e b 上的数据 进行集成、建模，以支持对w e b 数据的复杂查询。 2 3 4 从资源查找( i n f o r m a t i o nr e t r i e v a l ) 的观点挖掘非结构化文档 非结构化文档主要指w e b 上的自由文本，包括小说、新闻等。在这方面的 研究相对比较多一些，大部分研究都是建立在词汇袋( b a go fw o r d s ) 或称向 量表示法( v e c t o rr e p r e s e n t a t i o n ) 的基础上，这种方法将单个的词汇看成 文档集合中的属性，只从统计的角度将词汇孤立地看待而忽略该词汇出现的位 置和上下文环境。属性可以是布尔型，根据词汇是否在文档中出现而定，也可 以有频度，即该词汇在文档中的出现频率。这种方法可以扩展为选择终结符、 标点符号、不常用词汇的属性作为考察集合。词汇袋方法的一个弊端是自由文 本中的数据丰富，词汇量非常大，处理起来很困难，为解决这个问题人们做了 相应的研究，采取丁不同技术，如信息增益，交叉熵、差异比等，其目的都是 为了减少属性。另外，一个比较有意义的方法是潜在语义索引( l a t e n ts e m a n t i c i n d e x i n g ) _ ，它通过分析不同文档中相同主题的共- g - i 司a z ，找到他们共同的 根，用这个公共的根代替所有词汇，以此来减少维空间。例如：“i n f o r m i n g ”、 “i n f o r m a t i o n ”、“i n f o r m e r ”、“i n f o r m e d ”可以用他们的根“i n f o r m ” 来表示，这样可以减少属性集合的规模。 其他的属性表示法还有词汇在文档中的出现位置、层次关系、使用短语、 使用术语、命名实体等，目前还没有研究表明一种表示法明显优于另一种。 与非结构化数据相比，w e b 上的半结构化文档挖掘指在加入了h t m l 、超连 接等附加结构的信息上进行挖掘，其应用包括超连接文本的分类、聚类、发现 文档之间的关系、提出半结构化文档中的模式和规则等。 2 3 5 从数据库( d a t a b a s e ) 的观点挖掘非结构化文档： 数据库技术应用于w e b 挖掘主要是为了解决w e b 信息的管理和查询问题。这 些问题可以分为三类：w e b 信息的建模和查询；信息抽取与集成；w e b 站点建构 面向行业搜襄引苹的w e b 文车挖掘技术研究 和重构。 从数据库的观点进行w e b p q 容挖掘主要是试图建立w e b 站点的数据模型并 加以集成，以支持复杂查询，而不止是简单的基于关键词的搜索。这要通过找 到w e b 文档的模式、建立w e b 数据仓库或w e b 知识库或虚拟数据库来实现。相关 研究主要是基于半结构化数据进行的。 数据库观点主要利用o e m ( o b j e c te x c h a n g em o d e l ) 模型将半结构化数据表 示成标识图。0 e u 中的每个对象都有对象标识( o i d ) 和值，值可以是原子类型， 如整型、字符串型、g i f 、h i m l 等，也可以是一个复合类型，以对象引用集合 的形式表示。由于w e b 数据量非常庞大，从应用的角度考虑，很多研究只处理 半结构化数据的一个常用自集。一些有意义的应用是建立多层数据库( m l d b ) ， 每一层是它下面层次的概化，这样就可以进行一些特殊的查询和信息处理。对 于在半结构化数据上的查询语言研究也得到了人们的重视并做了专题研究。 由于在数据库观点下数据的表示方法比较特殊，其中包含了关系层次和图 形化的数据，所以大部分建立在扁平数据集合之上的数据挖掘方法不能直接使 用，目前已经有人针对多层数据库挖掘算法进行研究。 2 3 6 w e b 结构挖掘 w e b 结构挖掘的对象是w e b 本身的超连接，即对w e b 文档的结构进行挖掘。 对于给定的w e b 文档集合，应该能够通过算法发现他们之间连接情况的有用信 息，文档之间的超连接反映了文档之间的包含、引用或者从属关系，引用文档 对被引用文档的说明往往更客观、更概括、更准确。 w e b 结构挖掘在一定程度上得益于社会网络和引用分析的研究。把网页之 间的关系分为i n c o m i n g 连接和o u t g o i n g 连接，运用引用分析方法找到同一网站 内部以及不同网站之间的连接关系。在w e b 结构挖掘领域最著名的算法是h i t s 墨 躺 p a g e r a n k 缸法。他们的共同点是使用一定方法计算w e b 页面之间超连接 的质量，从而得到页面的权重。著名的c l e v e r 和g o o g l e 搜索引擎就采用了该类 算法。 此外，w e b 结构挖掘另一个尝试是在w e b 数据仓库环境下的挖掘，包括通过 面向行业搜索引擎的眦文本挖掘技术研究 检查同一台服务器上的本地连接衡量w e b 结构挖掘w e b 站点的完全性，在不同的 w e b 数据仓库中检查副本以帮助定位镜像站点，通过发现针对某一特定领域超 连接的层次属性去探索信息流动如何影响w e b 站点的设计。 2 3 7 w e b 用法挖掘( w e bu s a g em i n i n g ) b p w e b 使用记录挖掘，在新兴的电子商务领域有重要意义，它通过挖掘相 关的w e b 日志记录，来发现用户访问w e b 页面的模式，通过分析日志记录中的规 律，可以识别用户的忠实度、喜好、满意度，可以发现潜在用户，增强站点的 服务竞争力。w e b 使用记录数据除了服务器的日志记录外还包括代理服务器日 志、浏览器端日志、注册信息、用户会话信息、交易信息、c o o k i e 中的信息、 用户查询、鼠标点击流等一切用户与站点之间可能的交互记录。可见w e b 使用 记录的数据量是非常巨大的，而且数据类型也相当丰富。根据对数据源的不同 处理方法，w e b 用法挖掘可以分为两类，一类是将w e b 使用记录的数据转换并 传递进传统的关系表里，再使用数据挖掘算法对关系表中的数据进行常规挖 掘；另一类是将w e b 使用记录的数据直接预处理再进行挖掘。w e b 用法挖掘中 的一个有趣的问题是在多个用户使用同一个代理服务器的环境下如何标识某 个用户，如何识别属于该用户的会话和使用记录，这个问题看起来不大，但却 在很大程度上影响着挖掘质量，所以有人专门在这方面进行了研究。通常来讲， 经典的数据挖掘算法都可以直接用到w e b 用法挖掘上来，但为了提高挖掘质 量，研究人员在扩展算法上进行了努力，包括复合关联规则算法、改进的序列 发现算法等。 根据数据来源、数据类型、数据集合中的用户数量、数据集合中的服务器 数量等将w e b 用法挖掘分为五类： 个性挖掘：针对单个用户的使用记录对该用户进行建模，结合该用户基 本信息分析他的使用习惯、个人喜好，目的是在电子商务环境下为该用户提供 与众不同的个性化服务。 系统改进：w e b 服务( 数据库、网络等) 的性能和其他服务质量是衡量 用户满意度的关键指标，w e b 用法挖掘可以通过用户的拥塞记录发现站点的性 能瓶颈，以提示站点管理者改进w e b 缓存策略、网络传输策略、流量负载平衡 9 面向行业搜索引擎的w e b 文本挖掘技术研究 机制和数据的分布策略。此外，可以通过分析网络的非法入侵数据找到系统弱 点，提高站点安全性，这在电子商务环境下尤为重要。 站点修改：站点的结构和内容是吸引用户的关键。w e b 用法挖掘通过挖 掘用户的行为记录和反馈情况为站点设计者提供改进的依，比如页面连接情况 应如何组织、那些页面应能够直接访问等。 智能商务：用户怎样使用w e b 站点的信息无疑是电子商务销售商关心的 重点，用户一次访问的周期可分为被吸引、驻留、购买和离开四个步骤，w e b 用法挖掘可以通过分析用户点击流等w e b 日志信息挖掘用户行为的动机，以帮 助销售商合理安排销售策略。 0 w e b 特征描述：这类研究跟关注这样通过用户对站点的访问情况统计各 个用户在页面上的交互情况，对用户访问情况进行特征描述。 w e b 使用挖掘技术通常可以应用到两个领域：当用来分析w e b j 艮务器的访 问日志时，可以利用挖掘得到的服务模型来设计适应性w e b 站点 6 ，7 ；当应用 到单个用户时，通过分析用户的访问历史来发现有用的用户访问模式 1 。w e b 使用挖掘由于处理数据对象通常为用户的访问历史或服务器的访问日志，无法 得知数据对象代表的内容，因此得到的结果一般比较粗糙， 尽管w e b 挖掘的形式和研究方向层出不穷，但我认为随着电子商务的兴起 和迅猛发展，未来w e b 挖掘的一个重要应用方向将是电子商务系统。而与本文 相关的研究，由于是基于，将重点详细介绍面向行业的搜索引擎w e b 文本 处理方法。 l o 面向行业搜索引孳的w e b 文本挖掘技术研究 第三章中文w e b 文本挖掘关键技术 3 i w e b 文本获取 w e b 文本抓取器，是w e b 文本获取的主要方式，人们经常形象地将它比喻 i 臂 为网络蜘蛛监。如果把互联网比喻成一个蜘蛛网，那么网络蜘蛛就是在网上爬来 爬去找寻w e b 文本的蜘蛛。我们所用的元搜索引擎的网络蜘蛛是通过百度搜索 引擎所搜集的结果，从结果集合中找到相关姓氏的链接地址，然后通过这些链接 地址得到相关网页的内容，直到把搜索结果集合中所有的网页都抓取完为止，这 样就完成了一个姓氏的网页抓取。 3 2 w e b 文本消噪 浏览w c b 上的网页，我们会发现它们通常包含两部分内容，一部分内容体 现的是网页的主题信息，比如一张新闻网页中的新闻部分，我们称之为“主题” 内窖；另一部分则是与主题内容无关的导航条、广告信息、版权信息以及调查问 卷等内容，我们称之为“噪音”内容。噪音内容通常分布在主题内容周围，有时 也夹杂在主题内容中间，但它们并无内容相关性。 同时，我们观察到噪音内容通常是以链接导航文字( a n c h o rt e ) ( 【) 的形式出 现，因此，噪音内容会导致相互链接的网页常常也无内容相关性。这样，网页中 的噪音内容不仅给w e b 上基于网页内容的应用系统带来困难，也给基于网页超 链指向的应用系统带来困难。 在视觉上，一张网页的页面可以划分为若干个区域，我们把一个区域称为一 个内容块。这些内容块中有的包含着主题内容，而有的则包含着噪音内窑。通 常，一个内容块中的内容是紧密相关的，这就意味着我们可以以内容块为单位对 网页中的内容进行取舍。基于这样的分析，网页净化过程就是保留网页中包含主 题内容的内容块而去掉包含噪音内容的内容块。因此，网页净化过程可以分为两 个步骤：网页内容结构的表示和网页内容块的取舍。 _ 网页内容结构表示翟 面向行业搜索引擎的w e b 文本挖捆技术研究 h t m l 是一个标识语言( m a r k u pl a n g u a g e ) ，其中定义了一套标签来刻画网 页显示时的页面布局。因此，对于h t m l 网页最常用的结构表示方法是构造网 页的标签树。现有的标签树构造工具很多，d o m ( d o c u m e n to b j e c tm o d e l ) 即 文档对象模型是一个常用标签树构造工具，它可以将网页中的标签按照嵌套关系 整理成一棵树状结构。如图4 2 所示： 墨i 商i 一一 瞳畸- 荫榷_ - 曲一h 一 口母 b 一 l ) 1 口4 h ” 蕾 d静 d ，d n4 寸 o 一1 材 _ 酣，c _ 1 2 啕啦 盎_咖 a m t a 2 斟叫m 2 n 舟拈c i 矗咖 p 舻q 由 凸t t l - _ t ，凸“蒜= ；= 翟鬻勰h 。挂咖 。p 蝴焉 0 1 w 图3 1 ：网页标签树状结构图 针对本搜索所引擎搜集到的网页净化的特殊需求，我们首先对h t m l 规范 中的标签按照功能进行分类，进而提出更加适合网页净化的标签树的构造方法。 依据标签的作用可以将h t m l 的标签可以分为两类： 规划网页布局的标签：如上所述，在视觉上，网页是由若干内容块组成的， 而内容块是由特定的标签规划出的( 称之为容器标签) ，常用的容器标签有 、h 、q d 、口 、 等。 描述显示特点的标签：除了描述布局结构的标签外，h t m l 标准中还定义了 一套标签来描述其包含的内容本身，比如： 标签说明它所包含的内容要用粗 体显示， 标签说明它包含的是一个图片，等等。 由于网页净化是以内容块为单位进行保留和删除，因此，依据容器标签构造 标签树中的结点是较为合理的。而其它类型的标签信息可以作为它所在的内容块 的属性而存在。标签树如图4 3 ： 面向行业搜索引擎的髓b 文本挖掘技术研究 h 啪咐 图4 3 ：标签树 标签树构造完成后，网页净化过程就变为对标签树中结点的剪裁。除了上述 基本的标签信息外，我们还可以归纳计算出以下描述性信息。首先，依据内容块 中词项数与图片数和超链数的比值可以为每个内容块设定一个类型，分为主题 型、多链接型( h u b ) 、图片型三种。如果内容块中词项数与图片数的比值小于 某个阐值，该内容块就是图片型，如果内容块中作为链接导航文字出现的词项数 与该块中总词项数的比值小于某个闽值，该内容块就是多链接型，否则为主题类 型。这样，标签树中每个结点都有类型和属性集两组描述性信息，以及起链集和 重要标签集等数据信息。 根据以上分析。网页净化过程是在网页内部以内容块为单位进行重要性和相 关性评价，而不是网页间的比较。因此我们使用如下的特征项权值计算公式盈， 其中b w e i i g h t 表示内容块的权值，它的值由一个内容块中的重要标签来决定的。 w5 其中，b n ：网页中内容块的总数；网页中不同关键词的总数：b w e i 曲t j ：网页 中内容块j 的权重；b 1 丘j ：关键词i 出现在内容块j 中的词频 另外，我们采用的相似性计算公式为较为常用的是计算对应向量的c o s i n e 距 离凹】。给定向量，j = ( 葺，与，矗) ，z = ( 毛，屯，矗。) 面向行业擅索引擎的肛b 文本挖掘技术研究 ，r y r 、一 ：1 耳耳 啦爿卜赢惫：，玉2 ：。# 2 w 算法描述： l ：使用公式( 1 ) 计算网页正文对应的特征项向量q 2 ：f o r 网页中的每个叶子内容块c b id o 3 ：i f c b i 不是主题类型t h e n 4 ：使用公式( 1 ) 计算c b i 对应的特征项向量q i 5 ： 使用公式( 2 ) 计算q 与叫的相似度s i m i l a r i t y i 6 ：i fs i m i l a d t y i bt h e n d 为相似度闽值 7 ：保留c b i 8 ：e l s e 不保留c b i 3 3 文本的表示 文本是一种无结构文档，文本表示就是要将这些无结构文档结构化，以一 定的特征项( 如词语) 来代表文档信息文档。表示所采用的模型有很多种，近年 来应用较多且效果较好的是向量空间模型v s m ( v e c t 。rs p a c ef l e d e l ) 囊。 , 芭v s m 中，每一篇文档都被映射成多维向量空间中的一个点，对于所有的 文档类和未知文档，都可用此空间中的向量亿，彤；五，；，阡- ) 来表示( 其中 i 为特征词条，彤为王对应的权值，用以刻画该词在描述此文档内容时的重要 程度) ，从而将文档信息的表示和匹配问题转化为向量空间中向量的表示和匹 配问题来处理。 对于特征词条权重的计算，我们常用的是一种称为t 脚i d f 蕊的方法。在该 _ 方法中，特征词条的权重一般考虑两个因素：1 ) 词语频率t f ( t e r mf r e q u e n c y ) ： 词语在文档中出现的次数：2 ) 词语倒排文档频率i d f ( i n v e r s ed o c u m e n t 1 4 面向行业搜索引擎的珊文本挖掘技术研究 f r e q u e n c y ) ：该词语在文档集合中分布情况的一种量化，常用的计算方法是 l o g ( n n 。+ o 0 0 1 ) ，其中n 为文档集合中的文档数目，为出现该词语的文档 数目。 根据以上两个因素，可以得出公式； 阡k = c ，jx - 。s ：( 芸十。 c ， 其中，以为词语五在文档d i 中出现的次数，为词语瓦在文档b 中的 权值，k = 1 ，2 ，i n ( m 为特征词的个数) 。 为了计算方便，通常要对向量进行归一化，最后有： = 丛! ! ! 1 2 业! 生! ：! ! ! ! 氍忑磊 对于这个公式，我们不难发现，珊二随着以的增加而增大，随着的增加 而减小，这也正好反映了这样一个事实：当一个词语在文档集中出现的范围越 广，说明它区分文档属性的能力越低；另一方面，它在某一特定的文档中出现 的频度越高，说明它在区分该文档内容属性方面的能力越强。 除了t f * i d f 方法之外，还有一种布尔表示法用于计算词的权重，它用一个 布尔值作为文档向量的分量来表示特定的词汇在文档中是否出现，或者用词在 特定文档中的出现概率作为文档向量的分量。 向量空间模型属于一种文档的词集( b a g - o f - w o r d s ) 表示法，即所有的词从 文档中抽取出来，而放弃考虑词间的次序以及文本的结构，所以它的缺点是没 有考虑特征间的关系，导致分类精度不够高。最近，有人提出了用概念推理网 霍来表示文档，它不仅可以表示概念对类别的影响，而且可以通过概念推理网 自动地获取关键概念及其它概念与概念间的关系，这是一种文本聚类的新思 路。 3 3 1 基于汉语的文本特征提取 面向行业搜索引摹的1 b b 文车挖掘技木研究 前一节，我们提到了文本表示，其中v s m 模型的重要环节就是得到特征词 条t i ，所谓的文本特征提取就是特征词条的抽取过程。 一个英语句子的词与词之间是用空格分开的，它的特征提取就非常容易实 现。但是，汉语句子是线性排列的，使得特征提取成为一个难点。 3 3 2 切词 迄令为止，人们已经提出了许多种基于字典的计算机自动分词算法，这些 算法大致可分为两类：机械匹配方法、理解式切分方法。下面，我们就来看看 这两类分词算法瓣。 1 ) 机械匹配方法 机械匹配方法主要是基于字符串匹配的原理进行的，即它以“足够”大的 词表为依据，采用一定的处理策略将汉语文本中的字串与词表中的词逐一匹 配，若成功，便认定该字串为词。 2 ) 理解式切分方法 针对机械匹配法的不足，人们提出了理解式切分方法。这样的分词系统由 三部分组成：词库、知识库、推理机。 词库中存放词条：知识库中存放己形式化的各种语法规则语法知识，以及 语言学专家在分词过程中进行推理判断的经验知识：推理机制利用词库和知识 库提供的大量数据与知识，模拟语言学专家的逻辑思维过程，实现自动分词。 这实际上就是一个自动分词专家系统。 从理论上讲，它较匹配算法无疑是一个进步，同时也似乎更易为人们所接 受。但其有效性和可行性尚待进一步验证。因为现代汉语毕竟缺乏标志，缺乏 通用的分词规则。语言界中现有的词法( 构词法，构形法) 、句法及组合规则 仍然是十分笼统与复杂的，要想使其有效的、系统的转换成可为机器采用的形 式还有待进一步的研究，因此这种方法在现阶段是难以付诸于实践的。 综上所述，我们可以发现不论采用那一种分词方法，建立分词词库( 或称 机器词典) 都是汉语自动分词系统的基础，并且词库的优劣直接影响分词的正 1 6 面向行业搜索引擎的亿b 文本挖掘技术研究 确率和分词速度。 3 3 3 特征的选取 特征选取是文本特征提取在中文自动分词完成之后，选取出可以表征该文 档内容特征的特征词汇，而去除掉那些与表达内容特征无关的多余词汇。 不同的词条在文档中的作用是不同的，常用词( 例如“的”、“和”等虚 词) 在所有文档中都有很高的出现频率，而稀有词则在全部训练文档中出现的 次数都很少，这两类词的词频统计特性很难确定，不适合作为特征项，应予以 滤除。还有一些词在所有文档中出现的频率都基本相同，区分性差，不能作为 特征项也应滤除。同简单的词汇相比，词组和短语的表达能力强，更能表现文 档内容，因此应尽量多的采用词组和短语作为特征项，提高特征项的表示能力。 3 4 文本特征缩减( 特征子集选取) 使用前面提到的方法来表示待学习的文档时，表示文档的特征向量会达到 数十万维的大小。有人曾利用一些相关的文档集特征提取算法对y a h o o 上4 9 6 0 0 个文档提取作为特征的词串，最后得至r j 3 2 0 0 0 0 个特征词串。如此高维的特征可 能会大大增加机器的学习时间而仅产生与小很多的特征子集相关的学习分类 结果。所以，文本特征缩减( 特征子集的选取) 便显得异常重要。 目前，文档特征子集选取算法一般是构造一个评价函数，对特征集的每个 特征进行独立的评估，这样每个特征都获得一个评估分，然后对所有的特征按 照其评估分大小进行排序，选取预定数目的最佳特征作为结果的特征子集。所 以，选取多少个最佳特征以及采用什么评价函数都需要针对一个具体的问题通 过实验来决定。 下面，本文将介绍几种在当前信息检索、文本分类、文本挖掘等领域中经 常被采用的特征评估函数： 1 ) 词频( w o r df r e q u e n c y ) 昂研馏p ) = 丁f 缈) ( 4 ) 2 ) 文档频数( d o c u m e n tf r e q u e n c y ) 1 7 面向行业搜素引擎的朋b 文本挖掘技术研究 d f r e g ( f ) = d f ( w ) ( 5 ) 它们是最简单的评估函数，其中f 为对应于词条w 的特征，t f ( w ) 为词 条w 在文档集中出现的次数，d f ( w ) 为词条w 在文档集中发生的文档数。我们 在实际运用中一般并不直接使用它们，而常把它们作为评判其他评估函数的基 准。 3 ) 信息增益( i n f o r m a t i o ng a i n ) 卅劭f n 仰= p ( 形) p ( c ，) 1 0 9 p j ( c i 石厂w ) + p ( - ) 尸( c ，而l 。g 号鲁( 6 ) 其中p ( 矿) 为单字出现的概率，意味着单字并不出现，p ( c ) 为第 f 类值的出现概率，p ( c f 阿) 为当单字矿出现时属于第f 类的条件概率。 这里要指出的是，在实际实验中，对上述公式有小小的变形。在 l o g ( p ( c t 吵) p 心) ) 中，如果w 的出现倾向于表明文本属于类e ，那么l o g 的值 为正：如果w 的出现倾向于表明文本不属于类c j ，那么l o g 值为负；如果w 的出 现与类q 是否出现无关，1 0 9 值为0 。但是如果对1 0 9 值简单求和，就会出现这 样的问题：词条彤与各类无关，其信息增益接近于0 ，另一个词条的出现非 常倾向于类c 1 出现，c 2 不出现，这个词条本来非常重要，但对各l o g 值求和后 正l o g 值和负l o g 值抵消，结果也接近于o ，这样就无法与啊区分开了。解决这 一问题有两种办法：一是对各l o g 值取绝对值后再相加；二是不考虑负相关， 略去l o g 值小于0 的情况。在实验中，第二种办法的效果好于第一种，这可能是 因为在一般情况下，一个词条的出现只能说明某个类可能出现，而很难说明某 个类不会出现。在以后的讨论中，就不再考虑负相关。 信息增益的不足之处在于，它考虑了词条末发生的情况，即在上面公式中 的p 矿废，p e l 旷) l 。g ( 尸( c f i 旷) p ) ) 部分。虽然某个单词不出现也可能对判断 面向行业搜索引擎的w e b 文本挖掘技术研究 文本类别有贡献，但实验证明，这种贡献往往远小于不考虑单词不出现情况所 带来的干扰。特别是在类分布和特征值分布是高度不平衡的情况下，绝大多数 类都是负类，绝大多数特征值都是“不出现”的，即尸( 矿) ( 尸矿) ，此时信息 增益大的特征主要是信息增益公式中后一部分( 代表词条不出现情况) 大，而 非前一部分( 代表词条出现情况) 大，信息增益的效果就会大大降低了。有人在 实验中通过模拟这种情况发现，原始t f + i d f 法的分类精度为7 3 ，用信息增 益进行特征选择后精度提高至1 j 8 2 ，但在处理上述“高度不平衡”数据集时， 精度