（计算机应用技术专业论文）基于web的内容挖掘技术研究.pdf

哈尔滨工程大学硕士学位论文 摘要 随着w e b 文档数量的剧增，搜索引擎也暴露了许多问题。对于一般的查 询返回的结果很多，其中很多是无用或无关的结果，为了找到想要的结果， 用户不得不在搜索引擎返回的大量文档摘要列表中查找。本文将w e b 内容挖 掘技术应用于搜索引擎领域，它依赖于搜索引擎结果所提供的信息来归纳出 聚类，使得在搜索引擎返回的非常大的文档列表中的过滤操作变得十分方便。 p a t t r e e 是广泛用于中文关键字抽取和句子分割等领域的一种数据结构。本 文将p a t - t r e e 应用于搜索引擎结果聚类领域，并在修改的p a t t r e e 基础上 提出了一个新的中文搜索引擎结果聚类算法。实验结果证明我们的算法是可 行的，并且能够满足我们给出的搜索引擎结果聚类技术的几个重要指标。 关键词：w e b 内容挖掘；聚类；搜索引擎；p a t t r e e 堕：鎏三堡盔兰堡圭主簦鲨銮 a b s t r a c t w e bs e a r c he n g i n e sh a v eb e c o m ei n c r e a sjn g l yi n e f f e c t i v ea st h e n u m b e ro fd o c u m e n to nt h e w e bh a v ep r 0 1 i f e r a t e d u s e r so fw e bs e a r c h e n g i n e sa r eo f t e nf o r c e dt os h i f tt h r o u g ht h el o n go r d e r e d1 i s t o f d o c u m e n t “s n i p p e t s ”r e t u r n e db yt h ee n g i n e s t h i sp a p e ra p p li e dw e b c o n t e n tm i n i n gt ot h ef i e l do fs e a r c he n g i n e s e a r c he n g i n er e s u l t s c l u s t e r i n gt e l i e so nt h ei n f o r m a t i o nr e t u r n e db yt h es e a r c he n g i n e p a t t r e ei sad a t as t r u c t u r et h a ti sw i d e l yu s e di n h a n d l i n g c h i n e s ei n f o r m a t i o na n dw o r ds e g m e n t a t i o n t h i sp a p e ra p p l i e dp a t t r e e s t r u c t u r et ot h ec h i n e s ei n f o r m a t i o nr e t r i e v a lf i e l da n dp r o p o s e da n e wc h i n e s es e a r c he n g i n er e s u l t sc u s t e r i n ga l g o r i t h m sb a s e do no u r m o d i f i e dp a t t r e e e x p e r i m e n tr e s u l t sd e m o n s t r a t et h a to u ra p p r o a c h i sf e a s i b l ea n dcans a t i s f yt h et a r g e t sw ep r o p o s e d k e y w o r d s ：w e bc o n t e n tm i n i n g ，c l u s t e r i n g ，s e a r c he n g i n e ，p a t t r e e 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 研究课题的来源、目的和意义 本课题来源于黑龙江省自然科学基金项目，即“基于w e b 的数据挖掘技 术的研究”。近年来，计算机网络的普及使i n t e r n e t 成为世界上最大的信息 网，目前已有数万个w w w 服务器，而且还以每天两百多个的速度增加。其蕴 藏的数据己无法计算。在w e b 迅猛发展的同时，我们不能忽视“信息爆炸” 的问题，即信息极大丰富而知识相对匮乏。据估计，w e b 已经发展成为拥有3 亿页面的分布式信息空间，而且这个数字仍以每4 至6 个月翻一倍的速度增 加。在这些大量、异质的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 挖 掘作为数据挖掘的一个新主题，引起了人们的极大兴趣。 哈尔滨工程大学硕士学位论文 1 2w 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 可以看作一个巨大的数字图书馆：然而，这一图书 馆中的大量文档并不根据任何排列次序加以组织。它没有分类索引， 更没有按标题、作者、封面页、目次等的索引。对在这样个图书 馆中搜索希望得到的信息是极具挑战性的。 w e b 是一个动态性极强的信息源。w e b 不仅以极快的速度增长，而且 其信息还在不断地发生着更新。新闻、股票市场、公司广告和w e b 服务中心都在不断地更新着各自的页面。链接信息和访问记录也在 频繁地更新之中。 w e b 面对的是一个广泛的形形色色的用户群体。目前因特网上连接有 约五千万台工作站，其用户群仍在不断地扩展当中。各个用户可以 有不同的背景、兴趣和使用目的。大部分用户并不了解信息网络结 构，不清楚搜索的高昂代价，极容易在“黑暗”的网络中迷失方向， 也极容易在“跳跃式”访问中烦乱不已和在等待一段信息中失去耐 心。 w e b 上的信息只有很小的一部分是相关的或有用的。据说9 9 的w e b 信息对于9 9 的用户是无用的。虽然这看起来不是很明显，但一个人 只是关心w e b 上的很小很小一部分信息确是事实，w e b 所包含的其余 ， 略尔滨工程大学硕士学位论文 信息对用户来说是不感兴趣的，而且会淹没所希望得到的搜索结果。 这些挑战已经推动了懿露毫效曼实际缝发现秘利惩因特嘲上资澡的磅突 工作“，。 1 3 搜索引擎面对的挑战 搜索引擎对于删的发展起到了巨大的推动作用，但是随着因特网的发 展，搜索引繁也暴露出一些不足。搜索引擎面对的挑战主要表现在以下几个 方嚣。 两络资源静发袋，使褥搜索引擎能够检索的范围越来越小。 w e b 是一个动态增长的信息源，随时会发生备种变化，搜索引擎不能 及时反映这种变化。 援索雩l 擎瑟对懿瘸户是髟形惫基静，这骜髑户夔售惑瓣求、酝谖慧 景、兴趣各不相同。 对于用户来说，用户检索到的结果与用户所需要的信息相比，用户 捡索到的有用僖患经豢淹没旋众多鲍无用傧怠当中”t 。 正是由于这些挑战的存在，使褥如何高效地笈掘、利瑁网络信息资源成 为现在急需解决的问题，在这种情况下，w e b 挖掘作为新的知识摭掘的手段， 为w e b 信息的利用提出了新的解决方寨。 1 4w e b 挖掘与搜索譬i 擎的关系 w e b 挖掇与搜索弓l 擎相比，二者处于信息管毽中鸵不冠地位。w e b 挖掘属 予数据挖掇的分支，它瘸子翘识发骥豹范围，蔼搜索弓| 擎刘戳傣怠鹩检索为 目的，它属于信息发现的范围，就其对于信息的开发层次而言，w e b 挖掘要 高于搜索引擎。搜索引攀处于知识共搴的层次，而w e b 挖掘处于知识发现的 豢次。其钵嚣言，二者存在羞鞋下瓣嚣饕。 二者的瞬的不同。w e b 挖掘的目的是从w e b 页中获取其隐含的知识和有 用的模式；搜索引擎的目的是通过对w e b 文档的处理，使用户能迅速准确地 获褥所需倍患。 哈尔滨工程大学硕士学位论烹 m 二者信息处理的思想不同。搜索引聚是对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 文档豹盐鬻俘为主要蠹蜜，毽踅，二 者的研究对象有极大一郝分是完全相同的。 二者的技术手段相甄补充，二者处于不同的层次上，但是遮两者是紧密 粳连的，箍不是褪互隔离魄；知识发域是以知识共攀为基础的。搜索弓l 擎来 源于信息稔索技术，经j 童凡十年豹磷究，信息检索投术已经在文拯内容表示、 索引模型、匹配模型等方面发展得相当成熟。这些技术实际上就构成了w e b 挖掘的底层技术，w e b 挖掘正是由于赢接借鉴信息检索技术的缀验，才使得 宅够在熨薅屡次上对w e b 资源透嚣爨深步豹挖撬。反过来囊予w e b 绩怠 的不断膨胀以及人们对w e b 信息资源利用要求的不断提高，就要求搜索引擎 借鉴w e b 挖掘中的技术，借鉴w e b 挖掘中的思想，使搜索引擎更加适应网络 琢凌下对痿惑检索静震装，。 1 ，5 论文组织 全文共分五章，筹一摩是绪论。余缁了w e b 挖掇戆霪内乡 磷究瑷状及w e b 4 哈尔滨工程大学硕士学位论文 挖掘的闻憨与撬战、攘豢引擎存在瓣阕题与撬箴，簸后分耨了w e b 挖掘稻攘 索引擎之间的关系。 第二章生要介绍了w e b 挖掘的概念与技术，尤其是w e b 挖掘中的分类问 戆。还夯缨tw e b 售怠捡索戆壤念积援索雩 擎硷索羧零疆究瑗羧。分援tw e b 挖掘与w e b 信息检索的啜剐。 第三紫主要介绍了在分析了汉语特点的基础上，介绍了关键词抽取的概 念和主要方法分类。最磺详细套绍了一葺孛耨匏基于p a t - t r e e 的关谜词独取方 法。 第四章主要介绍了聚类的概念和用于文档聚粪方面的两类主要方法：层 次方法和平颇划分方法。还介绍了在搜索引擎结果聚类的概念及这方面的前 麓磁究工豫。 第五章在以前面介绍的关键字抽取技术和搜索引擎结果聚类算法的基础 上，提出了一种新的搜索引擎结果聚类算法。给出了具体的试验方案。最后 给出了搜索引擎结果聚类终评价方法。 哈尔滨工程大学硕士学位论文 i i _ _ - _ _ _ _ - _ _ i i i i i - - _ _ _ _ _ _ _ _ _ _ - _ _ _ - _ _ - _ - _ _ _ _ - _ - - _ _ _ _ _ _ _ _ _ - - _ _ _ _ _ _ _ - 黼 第2 童w e b 挖掘与w e b 信息检索 2 1w e b 挖掘( w e bm in i n g ) 2 w e b 挖撬的定义 w e b 挖掘是一项综合技术，涉及w e b 、数据挖掘、计算机语茸学、信息学 等多个领域。不同研究学从自身的领域出发，对w e b 挖掘的含义有着不同的 理释，矮瓣并发毪各鸯蒸测重点。镶懿，套些诗瓣凝语言学家认为，w e b 文 档为自然谮言理解提供了丰富的语料，可以从中自动地学习词语的意义，以 进行词义辨析或确定词语所属的概念。我们从更为般的角度如发。对w e b 挖掘 乍如下定义翻。 定义1 ：w e b 挖撼怒猎腹大量w e b 文档的集合c 孛发现隐含鹣模式p 。 如果将c 褥作输入，将p 看作输出那么w e b 挖掘的过程就是从输入到输出的 一个映射毒：c 哼p 。 w e b 稳藏簌鼗据撬稳发震嚣柬，强建箕定义与我餐熬短豹数雅挖掘定义 相类似。但是，w e b 挖椭与传统的数据挖掘相比肖许多独特之处。首先，w e b 挖掘的对缀是大量、弊质、分布的w e b 文档。我们认为，以w e b 作为中间件 对数据露遴零亍挖掘，以疑对w e b 鼹务器上豹虽恚、弱户信息麓数攥所开展熬 挖掘工作，仍属于传统的数据挖掘的范畴。其次，w e b 在逻辑上是一个由文 档节点和趟链构成的图，因此w e b 挖掘所得到的棋式可能是关- i - w e b 内容的， 也可能是必于w e b 结构的。此外，由予w e b 文档本身是半结构化或无结构的， 盈缺乏橇黎胃理解戆溪义，藤数据撼筏静对蒙是羧予数蠢疼孛瓣结枣每往数攥， 并利用关系表格等存储结构来发现知识。因此有魑数据挖掘技术并不适用于 w e b 挖掘，即使可用也需要建立在对w e b 文档进行预处理的基础之上。这样， 开发蓊懿w e b 挖掘技术，以及对w e b 文趟进行琰鲶理良缛至l 美予文搂静特级 表示，使成为w e b 挖掘研究的重点。 哈尔滨工程大学硕士学位论文 2 1 2w e b 挖掘的分类 w e b 挖掘是从w w w 资源上挖掘有趣的、潜在的、有用的模式及隐藏的信 息的过程，它是将数据挖掘技术和理论应用于对w w w 资源进行挖掘的一个新 兴的研究领域。目前在该研究领域中，根据挖掘对象的不同大致可分为三个 方面的挖掘研究：w e b 内容挖掘( w e bc o n t e n tm i n i n g ) 、w e b 结构挖掘( w e b s t r u c t u r em i n i n g ) 和w e b 使用记录挖掘( w e bu s a g im i n i n g ) 。图2 1 给出 了w e b 挖掘的分类图。 图2 1w e b 挖掘分类 ( 1 ) 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 bl o g ，w e b o q l 等，利用启发式规则来寻找 个人主页信息的a h o y ，等等。采用第二种策略的方法主要是对搜索引擎的查 询结果进行进一步的处理，得到更为精确和有用的信息，属于该类的有 w e b s q l ，及对搜索引擎的返回结果进行聚类的技术等。w e b s q l 是一种用于结 果提炼的查询语言，该系统访问搜索引擎获取的文档，并从文档内部或者从 服务器提供的数据中收集诸如u r l 、标题、内容类型、内容长度、修改日期 哈尔滨工程大学硕士学位论文 等信惠，类s o l 声明式语裔提出了获搜索结果中获取相关文档的麓力，z a m i r 和e t z i o n i 提出了一种用于把搜索引繁返回的文档进行聚类的技术。该技术 仅仅依赖予由搜索结果所提供的信息( 如u r l s 、标麟、网页的第一彳亍描述等) 泉跨缡窭聚爽，著涛稿斑鹣交柽螽入这些聚类中。这些聚类是援索雩| 擎返酉 的文档集合上的高级视图，使得在搜索引擎返回的非常大的文档捌表中的过 滤操作变得十分方便。 ( 2 ) w e b 缝梅挖据 w e b 缩构挖掘是献w 弹# 的组织结构及引用关系中推导知识的过程。由于 文档之间的互连，w w w 能够提供除文档内容之外的肖用信息。利用这些信息， 可以对页题避行排序，发现重要的页瓣。这方面工傺的代表有p a g e r a n k 和 c l e v e r 。魏舞，在多瑟次w e b 数据仓瘁( m l d b ) 中电零l 弱了页瑟戆镶接结褥。 ( 3 ) w e b 使用挖掘 w e b 使用挖掘，也称为w e b 日志挖掘，是从w e b 访问同志中抽取知识的 过程。鬻瓣审酶每会辍务器都僳蜜了谚| 、翥嚣恚( w e ba c c e s sl o g ) ，记录了关 于用户访问和交互的信息。分析这些数据可以帮助遴解用户的行为，从而改 进站点的结构，或为用户提供个性化的服务。这方面的研究主要肖两个方向： 一般的访闷模式追踪和个性化的使用记录追踪。一般翡访闻模式追踪透过分 折便塌记录采了解靥户的访湾模式稻 黉淘，以改送站点的缓织缩梭。两个涟 化的使用地激追踪则倾向于分析单个用户的偏好，藏目的是根据不同用户的 访问模式，为每个用户提供定制的站点。 尽管数攥挖掘戆各耱菠术寒理谂骧翅上都霹以整接或瘸按缝应爱予怼 w e b 信息的挖掘，如：基于代理的技术、基于概念的信息检索机都已用于w e b 挖掘中，然而由于w w l 】资源的异质性、多样性、分布的广泛性，特别是其上 数摆豹半结擒他特点，譬致了w e b 挖掇与对普遥大激数据库所谶行豹挖掘有 着很大的不阀。 啥尔滨翻鼙大学硕士学位论文 2 2w e b 催患检索( w e bl n f o r m a t i o nr e t ri e v a l ) 2 2 。1w e b 煊患检索定义 定义2 ：w e b 信息检索，是指从大量w e b 文耥的集合c 中我至与给定的 查询请求g 相关的、恰当数目的文档子集s 。w e b 信息检索的过程也对应于 个映射善：( c ，g ) 斗s “1 。 肤6 。年代隧来，藩慧检索领域在索芎 禳鍪、文稻内容表示、遴酝策酪警 方面取得了许多研究成粜。这些成果被成功地应用在w e b 上，产生了搜索引 擎，例如y a h o o ! ，a l t a - v i s t a 等。搜索引擎工作的般流程包括：使用r o b o t 搜集w e b 文撞、对烹揆聚合建立铡撵繁弓l 、分摄蠲户懿查询请裳、匹配文档 与查询请求以计算二者之间的相似度、对查询结聚进行排序阻赦用户相关度 回馈。 2 + 2 。2 搜索罢| 擎检索援本磷究残状 随着i n t e r n e t 的迅速发展、w w w 信息的急剧增加，人们通过i n t e r n e t 获取信息时遇到了一必无法避免的困难。其中墩大的问题之就是由于 i n t e r n e t 上信息静多楼瞧帮多变键掰导致一方露偿怠过疫膨瓢嚣另一方强 用于却找不剃自己需要的信怠。为了解决i n t e r n e t 信息检索静难题，人们在 信息检索领域进行了大量的研究，开发了各种搜索引擎，极大地方便了 i n t e r n e t 愿户，使得快速有效地获取信息成为可能。 叁1 9 9 4 年y a h o o ! 攘索弓 擎阀 辇楚今，鸯记录胃查静接索孳| 擎鼗量已经 达到了2 5 0 0 个左右，其中既有大型的综合性搜索弓l 擎，也有在特定领域里发 挥作用的专业搜索引擎，其中比较著名的搜索引繁国外有y a h o o ! 、e x c i t e 、 w e b s e e k 、a l t a v i s t a ，l y c o s ，i n f o s e e k 、o p e n t e x t 、w e b c r a w l e r ，g o o g l e 等，国内主鬃有搜狐、北大天网、酉度、北极星、广州视窗援索引擎等等。 这些搜索引擎按照信息搜集方法和服务提供方式不同，主要分为以下三种形 式： 全文( 关键诿) 检索搜索引攀。首先一个( 或者多个) 被称袭“橇 器人”( r o b o t ) 的程序在遵循r o b o t s 协议的基础上班装种方法自动 哈尔滨王稷大学颈学位论文 缝在互联网中袋集信息，然螽通过索弓l 器( i n d e x e r ) 为采集到的信想 建立索引并存入索引库，再 ；l ；i 检索器( s e r c h e r ) 根据用户的查询输入 热件查找索引撵并将查询缡粱返回。当潜要查找信息的时候，可按 照它稍酶势类嚣录一瑟层楚滋入，最磊到达嚣蕤遮，找到鑫己怒要 的信息。该类搜索引擎的优点是信息量大、更新及时、无需人工干 预，缺点是返阐信息过多，脊很多无关信息，用户必须从结果中进 行鲸选。这类搜索引擎匿熟数主要有：a 1 t a v i s t a 、n o r t h e r n l i g h t 、 e x c i t e 、g o o g l e 、i n f o r s e e k 、l y c o s 等：国内的主要有：北大天丽、 百波等。 分类目录式搜索引擎。将i n t e r n e t 上的资源服务器( 比如w w w 照 务器、霹p 驻务器等) 静逮缝收集起来，穰摇它弼掰稳供资源熬类瑟 不同而分成不同的目录。目录式搜索引擎以人工方式饯半自动方式 搜集信息，由编辑员查看信息之后，人工彤成信息摘爱，并将信息 嚣予事先确定翳分类框架中。售患大多甏囊霹站，提供警录爨蹩缀 努和直接检索服务。凌类搜索引擎因为嬲入了人的餐熊，所戬信憋 准确、导航质濑高，缺点怒需要人工介入、维护量大、信息量少、 信息更新不及时。这类搜索引擎国外的主装有：y a h o o ! 、l o o k s m a r t 、 o p e n d i r e c t o r y 等；重内豹主要有：援狐、j 辍星、广翔褫密搜索萼l 擎等。 元搜索引擎。这类搜索引擎被称为搜索引攀之上的搜索引擎，这擞 搜索雩| 擎竣存鑫邑匏鼗攥，瑟是蒋臻户豹奁璃请求瓣孵囊多令攘索 引擎递交，将返回的结果谶行重复排除、重新排序等处理后，作为 自已的结果返回给用户。服务方式为面向网页的全文检索。这类搜 繁弓 擎的优点怒返回结果静信息量更大、更全，缺点跫不能够充分 傻溺所使用搜索弓l 擎酶功艉，用户需要骰更多的筛逡。这类搜索弓 擎主要有：w e b c r a w l e r 、i n f o m a r k e t 等。 据中豳互联网信息中心统计，髓前搜索引擎魁仪次于电予霄点的第二大 i n t e r n e t 藏蘑。搜索零 擎鼓术麴磅突与应塌方兴涞艾，歪或瓷诗算掇工篷赛 和学术界争相研究和开发的对象。 l o 啥尔滨王稷丈学硕士学位论文 2 2 3 中文搜索等l 繁检索技术存在闫蘧分析 随莆i n t e r n e t 在徵内的迅速靛展，中文搜索引擎从无到肖，短短几年时 闽出现了许多中文搜索引擎，但其效巢却远未达到令入满意的程度。耳前中 文整索 肇存在诲多不髭，主要奔戮下几个方磷： ( 1 ) 查询速度慢。相对于英文搜索引擎，中文搜索引擎所采集的网页数 量小( 大都在十万的数麓极上) ，而且速度慢( 大都在秒的数凝极上) 。这一 方嚣是 燕予硬 雩方嚣( 秘鲡，缎务器毪麓、弼络罄宽等) 的羧髑；雯羚一方 面是由予中文信息处璎的一些特健，例如，中文信息中没有稍与词之间的分 割标记，浆对中文信息进行处理，酋先必须进行自动分词操作。这也需要 定的对闽。 ( 2 ) 鸯准率窝鸯全率低。重魏主流的接素 | 擎大都采鼹全文检索或关键 词检索的方式，即在原文中查找用户所指定的词。这种仅仅撼于字面的梭索 机制不可避免地会带寐实际检索结果与用户需求之间的偏差。举个简单的例 子，鼹户零羹粪撬与魄麓有关馥缓惑，当瞧鼹“邀醢”这令谈去检索对会发 现许多讲述计算机的文章并没有被衡出来，原因是因为这些文章中自始至终 都说的麓“计算机”，而没有使用“电脑”这个词。 ( 3 ) 不支持自动燃页分类。通过对羽夏静蠡动分类，鼹声不惶麓够方蠖 逑满筵溺茭，丽虽可强邋遭限老搜索范匿来馒褥镶怠的检索翼为准确和容翳。 但目前大多数的搜索引擎都不支持网页的自动分类，y a h o o ! 等搜索引擎鼠然 t 基支持分类搜索，但怒它们都是邋过人工来对w e b 上韵文档邀行分类，邃大 大影酾了索雩| 茭嚣戆数量。 ( 4 ) 没有对查询结果进行聚擞。目前i n t e r n e t 上存在蒋相似甚至榻弼 的网页，如果不对查询结果进行聚炎则会使得许多相似甚至相同的网页程焱 谗结暴中熬不曩条壤主显示整寒，这裁丈丈地艇鬟了焉户浏楚查谗结果熬熊 担。 从上筒分析的情况可以看出，鼷提高搜索引擎的性能和效率，使搜索弓【 擎具有“镭能”，已不熬仅从信息检索技术上来考虑，蔼必须将些新的技术 弓l 灭搜索孳| 擎串。w e b 挖掘按术在援索 擎中戆应薅主要惫裕莛动文攘、焦 息过滤、自动网页分擞、网页聚类椁。 哈尔滨工程大学硕士学位论文 2 2 4 目前搜索引擎所使用的关键技术 ( 1 ) 检索结果的联机聚类 尽管搜索引擎采用了各种方法来提高检索结果的精度，但是结果中仍然 包含了与用户查询请求不相关的文档，其比例高达7 5 以上。此外，搜索引 擎返回给用户的通常是一个线性的文档列表，虽然经过了相关度排序，但是 相关文档和不相关文档仍然混杂于其中。用户必须逐个地浏览以找到相关文 档，花费了大量的精力。当返回的结果数目众多时，这个问题更为突出。 为了方便用户的浏览，一些研究人员开始将聚类技术用于w e b 信息检索 结果的可视化输出。聚类是指将文档集合分成若干个簇，要求同一簇内文档 内容的相似度尽可能地大，而不同簇间的相似度尽可能地小。h e a r s t 等人的 研究已经证明了“聚类假设”，即与用户查询相关的文档通常会聚类得比较靠 近，而远离与用户查询不相关的文档。因此，我们可以利用聚类技术将搜索 引擎的检索结果集合s 划分为若干个簇( s ，s ，s ，) ，并以簇s 的质心 a v e r a g e ( d ) 作为簇s 的描述。这样，用户只需要考虑那些相关的簇，大大缩 d e s 二 小了所需要浏览的结果数量。当一次聚类生成的簇s 中仍然包含大量文档 时，可以对该簇中的文档再次聚类得到若干个子簇( s 。，s ，s 。) 。直到 用户满意为止。如图2 2 所示，e t z i o n i 等人的实验结果表明，使用一些改 进算法来对检索结果进行联机聚类不但是可行的，而且十分有效。 图2 2 检索结果的联机聚类 1 2 暗尔滨工程大学硕士学位论文 ( 2 ) 豢于超链酌榻荚度簧 痒 搜索引擎的检索结果往往过于庞大，用户一般只会浏览前颇的一部分缩 粱。通过对检索结果进将相关度排序，搜索引擎试图使相关的文档尽可能地 窭现在绫鬃瓣蓑嚣部分，强毅莲检索缝渠戆输出。鬣然各个装索弓l 擎孛援美 度排序的黑体实现各不栩嗣，但是基本上都采用了港于w e b 文档内容的方法， 即考虑用户所查询的词条在文档中的出现情况，包括：词条频率、逆文档频率、 通条位罨等嚣素。这种方法有稷太蠡冬勰凝性。一方嚣，相关度藏懿页殛不一 定是雳户蝥逋欢迹豹趸磷；雯一方蕊，有些轷e b 页藤的俸者剩粥上述因素来 欺骗搜索引攀( s p a m m i n g ) ，以提高其页面的排序。 事实上，w e b 中还蕴含了丰富的结构信息。页筒之间的超锻反映了页丽 勰豁雩l 强关系，一个受磁被其它菇点零| 焉豹次数蒸本上反浚了该瑟瑟懿受欢 迎程度( 熏臻性) 。超链中的标记文本( a n c h o r ) 对链宿页面也起到了概括作用， 这种概括强一定程度上比链宿页面 乍者所作的概括( 页面的标蹶、关键字、摘 要) 要更为露鼹、准确。爨藏，近年来熬觋了一些鏊l 琏设潮谯关发蓑 序方法， 作为基予内容方法的补究，铡魏，s t a n f o r d 大学醋究的p a g e r a n k 算法等。 这类方法通过为w e b 页耐构造引用圈，并综合考虑页面的被引用次数以及链 源页面的黧要性来判断链宿页面的羹凝性。图2 。3 中给出了一个简单示例， 其中懿各个爱蘑可霞予不霜兹w e b 然点上。当燹嚣0 帮夏瑟f 瓣内容穗关 度相当时，由于d 的被弓i 用次数为4 ，大于f 的被弓i 用次数l ，阂此在检索结 果中d 会排在f 的前面。些搜索引擎已经开始使用基于超链的相关度排序 方法。铡妇，以p a g e r a n k 为棱，0 技零鹣援索弓 擎g o o g l e 戆够焱诲与弼户请 求相关斡“粳威”页西。此外，g o o g l e 通过分折熬链中包含的文本，可以对 链宿页面谶行非全文索引，而不需要下载和分析实际的页面。疆前，g o o g l e 已经发展成为一个主要救搜索引擎，嶷舔下载并索引了近1 0 0 0 0 0 0 0 0 的w e b 页蟊。毽楚逶过超链分掇，其覆盏度这辎了3 0 0 0 0 0 0 0 0 ，怒避了其它任餐攘 索引擎。 啥尔滨工程大学硕士学位论文 甄2 3 基于超链瓣相关凄耱黟 ( 3 ) 繇手概念的榆索 大多数搜索引擎撮供的检索服务媳种关键字检索( k e y w o r ds e a r c h ) ， 翊检索出那些显式遗怠含雳户撂定谣袋戆文趟。垂予壹然语言中广泛存在曩 义和多义现象，关键字稔索显然是不够的。一些搜索引擎，铡如m a g e l l a n ， 开始在关键字检索的基础上引入基于概念的检索( c o n c e p ts e a r c h ) 。该方法 刹用了词袈在概念上的捆关性，因此掰以检索出那些并不显式地包含用户指 定静谣条，毽是舔包含焚淹义词或蠹下位谲酶文辎。鲷魏，爰户囱m a g e l l a n 查询“r o b o t ”时，m a g e lf a n 除了返潮包含“r o b o t ”的结果，逐会找到提及 “c r a w l e r ”，“s p i d e r ”，“w a n d e r ”等词条的结果。这样，既方便了用户请求 鹣输入，瞧提寒了售息梭索羲召疆搴。 搜索s l 攀在实现基于概念的检索辩，一般通过对用户酶鸯粥进行概念 词条扩展，然后转化为必键字检索。概念词条关系的获得可以肖以下两种方 法。 ( 1 ) 手王建立词典采存储概念层次及谲条之闻的交叉联系，该工俸逶零毒 领域专家来完成。 ( 2 ) 使用语法分析、统计等技术从文档集合中国动学习。例如：在矢量空 黉素雩l 攘黧孛，每个文楼d 疆表示蕊溺条t ；嚣张成瓣矢量窆阕孛浆一个蓬鬏二 矢量。从弱个角度来群，每个词条r 也可以表示d 为文档所张成的矢量空 间中的一个范化矢量v ( t ) = ( d l ，w ，( ，) ：d ，w 用) r ；d ，w 。) ，词条之 1 4 哈尔滨工程大学硕士学位论文 闻的相似度也可以由矢量之间的夹角余弦来计算 s i m ( t 。，t ，) = ( 矿( r ，) 矿0 ，) ) ( v ( t ，) l ly ( ，川) 。在此基础上，可以进一步对词 条进行聚类分类等处理，从而获得概念词条关系。 ( 4 ) 相关度反馈 在很多情况下，用户难以提出查询，其初始的查询请求q 通常是不精确、 不完全的，与基于概念的检索类似，相关度反馈技术也可以帮助用户形成查 询请求。但是，基于概念检索的目的是通过扩展查询请求来提高系统的召回 率，而相关度反馈技术则是通过对查询请求不断地进行修正以提高系统的精 确度。如图2 4 所示。 s + ll 髓 匡蝈 l 修正后查询 扔始查询 检索结果瓜厂i 王i 研 7 i ：! 兰：坠皇皇l i 州厂 图2 4 相关度反馈 在具有相关度反馈功能的系统中，系统按照下述过程对用户的查询请求 进行逐步求精。 1 ) 检索器给出查询q 的检索结果集合s 。 2 ) 用户对s 中文档的相关度进行评估，并反馈给系统。所有被用户标 记为“相关”的结果组成了正反馈集合s ，标记为“不相关”的结果组成了 负反馈集合s 一。 3 ) 系统根据用户的反馈对查询q 进行修正。例如，在矢量空间索引模 型中，可以将正反馈集合中的文档矢量加到查询矢量上，同时减去负反馈集 合中的最不相关的若干文档矢量，即 矿( q ) 七_ 矿( g ) + v ( d ) - 矿( d ) ( 2 1 ) d + s d a a r g m a x ( s 一】 4 ) 重复步骤1 ) ，2 ) ，3 ) ，直到用户得到满意的结果为止。 15 哈尔滨工程大学硕士学位论文 一些研究和实验结果表明，利用相关度反馈可以较好地改进检索效果。 但是，目前很少有搜索引擎支持该功能。其原因可能是因为相关度反馈需要 用户的参与，而普通用户在使用搜索引擎时不太愿意花时间利用这些附加功 能。 2 3w e b 挖掘与w e b 信息检索 w e b 上的挖掘和信息检索是两种不同的技术，其区别主要表现在以下几 个方面。 ( 1 ) 方法论不同。信息检索是目标驱动的，用户需要明确提出查询要求： 丽挖掘是机会主义的，其结果独立于用户的信息需求，也是用户所无法预知 的： ( 2 ) 着眼点不同。信息检索着重于文档中显式存储的字词和链接；而挖掘 试图更多地理解其内容和结构： ( 3 ) 目的不同。信息检索的目的在于帮助用户发现资源，即从大量文档中 找到满足其查询请求的文档子集：而挖掘是为了揭示文档中隐含的知识； ( 4 ) 评价方法不同。信息检索使用精度( p r e c i s i o n ) 和召回率( r e c a l l ) 来 评价其性能，要求返回尽可能多的相关文档，同时不相关的文档尽可能少。 而挖掘采用收益( g a i n ) 、置信度( c e r t a i n t y ) 、简洁性( s i m p l i c i t y ) 等来衡量 所发现知识的有效性、可用性和可理解性； ( 5 ) 使用场合不同。有时信息检索系统返回太多的结果以致用户无法 浏览，有时用户没有明确的信息需求，有时用户希望发现文档集合中所具有 的结构、趋势、含义，在这些场合下，就需要使用挖掘技术。 尽管 f e b 挖掘是比信息检索层次更高的技术，但它并不是用来取代信息 检索技术。二者是相辅相成的。一方面，这两种技术各有所长，有各自适用 的场合；另一方面，我们可以利用w e b 挖掘的研究成果来提高信息检索的精 度和效率，改善检索结果的组织，伎信息检索系统发展到个新的水平。 哈尔滨工程大学硕士学位论文 2 4 本章小结 w e b 挖掘是从w w w 资源上挖掘有趣的、潜在的、有用的模式及隐藏的信 息的过程，它是将数据挖掘技术和理论应用于对w w w 资源进行挖掘的一个颓 兴的研究领域。本章首先介绍了w e b 挖掘分类：w e b 内容挖掘、w e b 结构挖掘 和w e b 使用记录挖掘。然后介绍了w e b 信息检索的概念、搜索引擎检索技术 研究现状以及目前搜索引擎所使用的关键技术。最后从五个方面分析了w e b 挖掘与w e b 信息检索的区别。 哈尔滨工程大学硕士学位论文 3 1 关键词抽取概念 第3 章关键词抽取 随着因特网的快速发展，网络上中文的信息量也急剧增加。如何有效、 准确地从这些信息中向用户提供所需要的内容，是中文信息检索领域目前迫 切需要解决的问题。中文信息检索中“词”的概念不同于语言学上的“词”， 不仅有常规意义上的“词”，也包含词组和短语，可以将它们通称为“关键词”。 关键词抽取( p h r a s ee x t r a c t i o n ) 一般也称为词分割( w o r ds e g m e n t a t i o n ) ， 中文意思是在一个字串中发现最长的有准确意义的单词。 关键词抽取在中文语言处理中一直是一个很关键的问题。关键词在本文 中准确定义为有意义且具代表性的短语或词条，然而关键词认定牵涉到个人 的主观判断，且相同的词条在不同的主题下，也由不同的认定。不像英文， 中文在句子中没有明显的字边界。中文关键词自动抽取是很困难的，特别是 对于生词，如：人名、地名、外来词、专业术语和缩写词等等。因此，在中 文关键词抽取方面的成绩并不是很多。然而，没有有效的关键词抽取技术， 许多信息检索应用如：全文搜索、文档分类聚类，信息过滤和文本摘要等等， 就无法获得令人满意的结果。由于缺少有效的提取关键词的手段，中文信息 检索与英文信息检索相比有较大的差距。 3 1 1 汉字编码体系 汉字在计算机内部是以内码的形式进行存储的，汉字内码是汉字在中文 信息处理系统中最基本的表达形式，它与汉字交换码、汉字区位码有一定的 对应关系。由于自定义编码顺序的特殊性，因而可通过计算偏移量的方法来 定位改汉字在编码表中的位置。例如，国际g b 2 3 1 2 汉字编码表共收录了6 7 6 3 个汉字，汉字在该编码表中的偏移量计算公式如下： o f f s e t = ( c 1 一o x b o ) 9 4 + ( c 2 0 x a l ) ( 3 1 ) 其中，o f f s e t 代表该汉字在编码表中的位置，c c ，代表汉字的内码( 每 r 啥尔滨工程大学硕学位论文 个汉字由两个字节表示) 。 3 1 2 汉语词的特点 在汉诿中，调是最小豹、蔻独立溪凌豹、寿意义戆语言或分，宅是构成 稻分析语言的基本单位。汉语词是一个开放的集合，箕数量可以认为是接近 无穷的，没有哪一部词欺能够收集所肖的词，不同的辞典所收澈的词条都不 样，例如：在 刘源8 4 中共收录了l o 万多个调条，在 辞海8 9 中共收 录了1 2 万多谲条。虽然汉语孛词豹总整狠大，毽缀鬻密王冕酶漏并不多，窭襞 的频率也不样，例如，在 刘源9 2 中收集了常用词4 3 5 7 0 条，这些词条 总覆盖率就达到9 8 5 。通过对 刘源9 2 中收录的常用词的研究，可以发 避殴不同熬字开头兹弱条数嚣交纯缀大，有多达数嚣豹( 翻热，“不”、“大” 等) ，也有个的( 例如，“啊”、“埃”等) 甚至没有( 例如，“艾”、“器”等) ， 而且这些词祭的长短也不尽相同，有一个字的单字词，也有7 个字的多字词， 蔟中以二字词最多，具体情况冕表3 1 。 表3 1 词祭分布清嚣 词条字数12 3 4b67 词条数 2 6 0 6 3 5 5 2 7 3 6 9 33 6 2 28 3 3 6 3 3 。1 3 关键词自动捆取存在的问题 关键词候选字串主要有四种错误炎型。“。 ( a ) 潋分霭、数谲、量词、连词秘赘蘧戈起戆鞠字事，鲡“瓣中国”、 “千三百”、“种颜色”和“的初衷”； ( b ) 前后缺字，如“( 忙) 前忙臌”和“曹雾( 芹) ”等。 ( e ) 字窜过长，熟“部长囊”等。 ( d ) 字串边赛完整，健意义没有紧密的联系，始“e t 蘸出发”等。 这四中出错类型在总出错字串中所占的百分比分别为 类型a类型b类型c类型d 4 l ，9 链2 5 。5 筠2 i ，l 1 1 5 篙 影响关键词抽取的主要问题 ( 1 ) 统计涨落噪嬲 哈尔滨工程大学硕士学位论文 统计语言模型对字串的统计涨落十分敏感，在具有相同子串的关键词中， 在统计上属于弱势的关键词往往会被切开，这是造成出错类型b 、c 的主要原 因。例如，在语料中“曹雪芹”出现了3 5 0 次，而其它以“曹雪”开头的人 名如“曹雪涛”、“曹雪华”等总出现1 1 次，由于“曹雪”和“涛”、“华”在 统计上没有明显的依赖关系，因此，关键词提取算法会把“曹雪”认作为关 键词，称这种现象为“统计涨落噪声”。 ( 2 ) 高频词粘连效应 在汉语中，助词“的”、“得”、“地”以及连词、介词、数词、代词出现 频率很高，与其它词汇连用的情况也很常见。g , j 女h “启示”在语料库中出现 有3 0 是出现在字串“的启示”中，“的启示”虽不是词，但“的”与“启示” 又很强的相关性，在这种情况下，关键词提取算法会认为“的启示”就是一 个词。可以将这种现象称为“高频词粘连效应”。高频词粘连效应是造成关键 词提取不准确的主要原因，错误类型a 就是它的具体表现形式。 统计语言模型的首要任务是从语料中提取尽可能多的统计数据。通常采 用的b i g r a m 、t r i g r a m 等n 元固定的统计方法，是将语料分解成长度为n 个 字的语言片断，以对这些n 元组的统计分析来代替对原始语料库的分析。这 些简化模型为分析带来便利的同时也存在着严重的问题。当关键词长度大于 n 时，该关键词会被这些n 元组分割成碎块，这种“截词”现象的存在，使n 元统计语言模型无法有效提