（计算机软件与理论专业论文）基于web数据挖掘的面向领域高性能信息检索研究.pdf

基于w e b 数据挖掘的面向领域高性能信息检索研究 摘要 随着i n t e r n e t w e b 技术的快速普及和迅猛发展，w w w 上的信息量不断增加，如何在 这些信息中找到用户真正需要的内容，成为数据组织和w e b 相关领域专家学者关注的焦点。 由于，因特网信息使川技术的发展往往跟不上因特网信息的增长，搜索引擎可以为人们查找 与关键词相关的文档，但返回的结果往往是文档数量太多而命中率不高。传统搜索引擎技术 满足了人们一定的需要，但由丁其通川的性质，仍然不能满足不同背景、不同目的和不同时 期的川户个性化的需求。基于w e b 挖掘的高性能信息检索就是针对这个问题而提出来的。研 究的目标在于充分利川川户的个性化信息，通过刚户兴趣制导或丰富查询模式等灵活手段米 采集w e b 信息，充分利川网络信息，从而提高奇渤的准确度，提高了检索质量，并满足， j 户 的特定查询需求。 本文首先对w e b 挖掘技术利搜索引擎技术进行了分析，同时对其- _ i ：作原理和数据挖掘中 的聚类分析技术进行了较为深入的分折。由于高性能的个性化信息检索的前提是挖掘刚户的 访问特点并对用户进行分类，用户的访问行为是存放在w e b 日志中，w e b 日志数据需要进 行预处理，才能川于州户兴趣的挖掘。冈此论文深入讨论页面过滤和用户访问路径等问题， 使w e b 日志预处理l ：作更加完善。 本文通过深入研究检索系统如何更快速抓取更多高质越网页，如何进行网页文档索引， 如何为州户提供高性能的检索服务后，重点闻绕检索效率和检索效果这两个最基本的 旨标， ， 从索引创建和检索过榭详细分析高效检索系统的相关基本实现技术。在此基础上提出根据 w e b 页面网页所在的位置，挖掘出网页在网站中的层次类别信息，通过这些信息进行动态 聚类，为h j 户提供一种动态的目录聚类夯询服务：并针对单个川户以往搜索记录进行分析， 推测川户的搜索偏好，并对该川户进行夯询建模，然后根据用户查询模型产生该类川户的访 问模式。 最后，本文对作者所做的：i ：作进行了j | ：1 纳，总结，并讨论了将米进一步的研究方向。 关键词：w e b 数据挖掘，信息检索，个性化服务，w e b 日志，预处理，聚类，访问行为 s t u d yo f f i e l d s o r i e n t e d h i g hq u a l i t yi n f o r m a t i o nr e t r i e v a l b a s e do nw e bd a t am i n i n g a b s t r a c t i nt o d a y si n f o r m a t i o nw o r l d ，t h et e c h n o l o g yo fi n t e r n e t w e bi si ni t sf u l ib l o o m ，a n dt h e i n f o r m a t i o nf r o mw w wc o n t i n u et og r o w f i n d i n gt h ec o n t e n tw h i c ht h eu s e r sa r er e a li n t e r e s ti n h a sb e c o m et h ef o c a lp o i n to fo r g a n i z a t i o n sa n ds p e c i a l i s t si nt h er e l a t e df i e l d s t h es e a r c he n g i n e c o u l df i n do u tt h ed o c u m e n t sw h i c hh a v es o m er e l a t i o nt ot h ek e yw o r d s h o w e v e r , t h e r ea r et o o m a n yr e s u l t sa n dt h ep r e c i s i o nr a t i oi sn o tt oh i g h t h et r a d i t i o n a ls e a r c he n g i n et e c h n o l o g yh a s a d a p t e dt op e o p l e sc e r t a i nn e e d s ，b u tb e c a u s ei t sc o m m o n a l i t yi t c a nn o ts a t i s f yt h er e q u i r e m e n t s o fu s e r s p e r s o n a l i t yd e m a n d sw i t hd i f f e r e n tb a c k g r o u n d ，d i f f e r e n tp u r p o s e sa n dd i f f e r e n tt i m e a n dt h ep u r p o s eo fr e s e a r c hi st of u l l yu t i l i z et h eu s e r sp e r s o n a li n f o r m a t i o nt h r o u g ht h ef l e x i b l e m e a n s ，s u c ha si n t e r e s t sh o m i n gm e c h a n i s mo fu s e ro rd i v e r s eo fr e t r i e v a ls c h e m e st oc o l l e c tt h e i n f o r m a t i o nf r o mw e b ，a n d 而a k ef u l lu s eo fn e t w o r ki n f o r m a t i o n ，t h e ni m p r o v i n gt h ea c c u r a c yo f i n q u i t i e sa n di m p r o v et h eq u a l i t yo ft h er e t r i e v a l ，a n dt om e e tt h ed e m a n df o rs p e c i f i cu s e r s f i r s t l yt h i sp a p e ra n a l y s i st h es e a r c he n g i n et e c h n o l o g ya n dw e bd a t am i n i n gt e c h n o l o g y , a n d t h ep r i n c i p l eo fs e a r c he n g i n ea n dt h ec l u s t e r i n ga n a l y s i so fd a t am i n i n g a st h ec h a r a c t e r so f u s e r sa c c e s s i n ga n dt h ec l a s s i f i c a t i o no fu s e r si st h ep r e c o n d i t i o no fh i g hq u a l i t yp e r s o n a l i z e d i n f o r m a t i o nr e t r i e v a l ，a n dt h ea c c e s s i n ga c t i v i t y h a sb e e ns t o r ei nt h ew e bl o g ，a n di n f o r m a t i o n c a nb ee v e n t u a l l yu s e di nt h em i n i n go fu s e r si n t e r e s to n l yw h e nt h ew e bl o gd a t ah a sb e e n p r e p r o c e s s e d t h e r e f o r et h i sp a p e rt h o r o u g h l yd i s c u s st h ep r o b l e m so fw e bp a g ef i l t e r i n ga n du s e r a c c e s sp a t h sa n ds oo n ，t om a k et h ew o r ko fw e bp r e p r o c e s s e dm u c hm o r ep r e f e c t ! s e c o n d l yw ee x p l o r et h em e a n st h a tr e t r i e v a ls y s t e mc a p t u r eh i g hq u a l i t yw e bp a g e s ，a n d h o wt ob u i l dt h ei n d e xo fp a g e s ，h o wt oo f f e rt h eh i g hq u a l i t yr e t r i e v a ls e r v i c e s w ef o c u so nt w o b a s i ci n d e x e s t h ee f f i c i e n c yo fr e t r i e v a la n dt h er e s u l t so fr e t r i e v a l o nt h eb a s i so fs e a r c h i n g ，w e r e p r e s e n t e dat h e o r yt h a tm i n i n gt h ec l a s s if i c a t i o ni n f o r m a t i o no fp a g e si nt h ew e b s i t ea c c o r d i n g t h ep o s i t i o no ft h ew e bp a g e ，a n dd y n a m i cc l u s t e r i n gt h r o u g ht h e s ei n f o r m a t i o nc a np r o v i d et h e u s e rak i n do fd y n a m i cc l u s t e r i n gd i r e c t o r ys e a r c hs e r v i c e ；t od e d u c et h eu s e g ss e a r c hp r e f e r e n c e a n dt h e nb u i l dt h em o d e lo fu s e rs e a r c h i n g ，f i n a l l y g e n e r a lt h eu s e r a c c e s sp a t t e r n sb a s eo ni t f i n a l l yt h op a p e rm a k eac o n c l u s i o na n ds u m m i n gu po f a l lt h er e s e a r c h ，t h e nd i s c u s st h e p o s s i b l ed i r e c t i o no f f u r t h e rr e s e a r c h k e yw o r d s ：w e bd a t am i n i n g ，i n f o r m a t i o nr e t r i e v a l ，p e r s o n a l i z e ds e r v i c e s ，w e bl o g ，d a t a p r e p r o c e s s i n g ，c l u s t e i i n ga n a l y z i n g ，a c c e s s i n ga c t i v i t y i l 附：学位论文原创性声明和关于学位论文使用授权的声明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究曾做出重要贡献的个人和集体，均已在文中以明确 方式标明。本人完全意识到本声明的法律责任由本人承担。 论文作者签名：e l 期：! ! ! 足生垒旦乡 关于学位论文使用授权的声明 本人完全了解贵州i 大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权贵州大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 撇雠雌名：袒蝴一 1 1 引言 第一章概述 近年来，随着i n t e m e t w e b 技术的快速普及和迅猛发展，特别是电子商务的蓬勃发展为 网络应用提供了强大支持。然而，因特网信息使用技术的发展往往跟不上因特网信息的增长， 虽然搜索引擎可以为人们金找与关键词相关的文档，但返回的结果往往是文档数量太多而命 中率小高。如何合理地挖掘和利用w e b 信息，使因特网的臣大作用和满能得以发挥，一直 是一个热门的研究课题。 w e b 挖掘指使用数据挖掘技术在w w w 数据中发现潜在：的、有用的模式或信息。w e b 挖掘研究覆盖了多个研究领域，包括数据库技术、信息获取技术、统计学、人丁智能。i j 的机 器学习平神经网络等1 2 1 1 4 1 1 1 3 1 d s 。根据对w e b 数据的感兴趣程度4 i 同，w e b 挖掘一般可以分 为三类：w e b 内容挖掘、w e b 结构挖掘、w e b 用法挖掘。 1 ) w e b 内容挖掘，h 前般从两个刁i 同的观点来进行研究。第，从资源查找 ( i n f o r m a t i o nr e t r i v a l ) 的观点挖掘_ j 仁结构化义档，其主要任务是从用户的角度发，怎样 提高信息质量和帮助用户过滤信息。其次，从数据库的观点挖掘非结构化文梢，其主要任务 是试图对w e b 卜的数据进行集成、建模，以支持对w e b 数据的复杂查询。 2 ) w e b 结构挖掘，即对w e b 文档的结构进行挖掘。对于给定的w e b 文档集合，应该 能够通过算法发现他们之问连接情况的有厂仃信息，文档之问的超链接反映了义档之间的包 含、弓lj f j 或者从属关系。日前w e b 结构挖掘往定程度上得益于社会例络和引川分析的研 究，运川引川分析方法找到i 叫一网站内部以及不网站之i n j 的链接笑系。在w e b 结构挖掘 领域最著名的算法足h i t s 算法和p a g e r a n k 算法5 1h g 。他们的共同点都足使川- 定方法计 算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 数据仓j 车中榆 a 剐本以帮助定位镜像站点，通过发现针对桀一特定领域超连接的层次属陀上探索信息流动 如何影响w e b 站点的设计。 3 ) w e bj | j 法挖掘，即w e b 使用记录进f ，挖棚，在新必的电了向务领域彳丁其重要意义， 它通过挖掘籼灭的w e b 日忐记求，束发现用广访 uw e b 贞的模式，通过分析日忐记录巾 的规律，可以识别用户的忠实度、爱好、满意度等，从而发现潜在的厂玎户，增强站点的服务 竞争力。目前，经典的数据挖掘算法都可以直接用到w e b 用法挖掘上来，但为了提高挖掘 质量，研究人员在扩展算法上进行了努力，包括复合关联规则算法、改进的序列发现算法等。 1 2 研究背景 由于w e b 信息量增长极伙，一些作为基于w e b 挖掘技术的戍用实体，往往不能也无法 做到把w e b 窄问f ：的所有内容都收录进来，因此出现搜索不完伞的现象。在信息选取的策 略方面，也会出现某些倾向性。此外，由于其服务器存储容量的限制，这些应用实体还规定 每个站点最多索引页而数。这样，对于某个特定的领域或主题，通用挖捌实体无法保西e 在信 息采集方面做到真正的全面l 。 其次就足榆索模式单一，榆索精度低。目前搜索引擎在检索的时候主要还足某于传统的 ”关键词v 配”，常常会洲为关键词存在歧义性影响杏洵的准确性。再加上w e b 信息数景庞 大，而用户在进行w e b 信息检索时输入的查询关键浏通常比较简币，导致企询结果集膨胀， 用户必须在大最的与自己夼淘意图相关和一i 桐关的结果集中寻找自l 需要的东西。 1 3 论文主要工作 鉴于w e b 数据挖掘征生产活动中的重要作用，w e b 挖掘作为一个完整的技术体系，与传 统数据和数据仓库相比，w e b 卜的信息是j e 结构化或半结构化的、动态的、并日是容易造 成混淆的，所以很难直接以w e b 网页上的数捌进行数据挖掘，而必须经过必要的数据处理。 而甚于面向领域的w e b 信息检索技术，其其有i 分广泛的虑用领域、u 。观的应用前景。通 过对木课题的研究，可以充分结合州关领域知识的特点，在优化信息抽墩、十富企洵模式、 提岛检索精度等方面做更多的t 作。由于把川户企洵的地r 爿限定律- 某个特定领域，町以在一 定程度上避免查洵词的歧义性，从而提高查询的准确度。总之，通过对面向领域的赢性能信 息检索研究，不但解决了存特定领域信息糙盖量、信息更新速度等方面的问题，提岛了检索 质量，而上土还可以满足崩广，的特定查询需求。此外开展对此课题的研究，对丁我省实施信息 化带动现代化有积极意义。 论文研究多项w e b 挖掘和 j 然语言处胖( n l p ) 技术，结合面向领域信息检索的特点， 研究层次结构挖掘的动态茹琶类和访问模式挖掘的个忭检索扩展等创新一陀的技术，建立面向领 域的高性能信息榆索模型，为用广准确定位信息资源行提供商质最的榆索结果。在研究的过 程中，主要针对以下问题：其一，根据w e b 贞面网贝所在的化胃，挖抛出网贝在n , 五j i 中的 层次类别信息，通过这些信息进行动念聚类，为用户提供种动态的日爿之聚类企nj i r 务；j e 二，针对单个用户以征搜索i 己录进行分析，推测川户的搜索偏好，并对陔用户进行杏i ： j 建模， 2 然后根据用户查询模型产乍该类用户的访问模式。 论文题口源头于贵州省教育厅自然科学类立项课题基于w e b 数据挖掘的面向领域岛 性能信息检索研究，属于理论研究领域。选题的意义一方面在于拓宽了数据挖掘的应用领 域，可以允分结合相关领域知识的特点，在优化信息抽取、丰富查洵模式、提高检索精度等 方面做更多的工作。由于把片j 户查询的范围限定在某个特定领域，可以在一定程度上避免查 询词的歧义性，从而提高查询的准确度；另一方面，采用“基于访问模式挖掘的个性化检索 扩展”方法。通过对用户以往搜索记录的分析，即通过对w e b 日志的挖掘进行归纳学习， 发现并获得用户的习惯性访问模式，推测用户的搜索偏好，将偏好近似的_ f 1 】户分类。根据已 经建立的用户查询模型产十该类用厂，的访i 丌j 模式，由此设讣反映访问特征的检索扩展方法。 1 4 论文结构 木论文结构安t i t a nf ： 第章为弓l 亩，简述论文中的研究对象，研究7 亍景和研究意义，和所要完成的i ：作等情 况。 第一二章为理论基础i 年h 关技术，概述了w e b 数槲挖掘技术的基本概念、数据挖掘的流 程及原理；概述了搜索引擎技术的皋木概念、w e b 搜索引擎的工作原理；深入探讨了聚类 分析的们i 关技术。为进- 一步利用w e b 数据挖掘技术研究面向领域的信息检索提供理论依据。 筇ji 币为信息检索的数据预处理技术，本章主要l 寸论w e b 日志预处理，包括数据清理、 用户识别、会活识别和路径步允等上作，在u 有上作的基础上，重点讨论贝咖过滤利用广l ：方 问路径等问题，使w e b 口志预处理j i ：作更j u 完善。 第四章为高t _ l ：f i e 的面向领域个性化信息检索，本章亟点山绕检索效率和检索效果这两个 最皋本的指标，从索引创建和检索过程详细分析高效检索系统的相天肚本实现技术。捉根 据w e b 页阿州页所在的位置，挖掘出网页位例站中的层次类别信息，通过这些信息进行动 态聚类，为用户提i ：j 一种动：各的目录聚类垒询服务；并钊对蕾个用户以往搜索址录进行分析， 推测用广的搜索偏好，并对该用厂1 进行杏询建模，然后根掂用户_ 杏洵模型， ，卜该类用户的访 问模式。 笫血章为总结j 腱鬯，对沦文所做的工作进行总结，并对下步的工作进行了腱毕。 3 2 1w e b 数据挖掘 第二章理论基础与相关技术 2 1 1w e b 数据挖掘基本概念 随着i n t e m e t i n t r a n e t 技术的发展，尤其是w e b 的全球普及，使得w e b 上信息量无比丰 富，如何从非格式化数据信息l - 有效地挖掘出有用的信息是对数据挖搁领域的一个新挑战。 w e b 是个巨大的、广泛分布、高度异构、半结构化、超文本超媒体、丰瓦联系并且不断 进化的信息仓库：也是一个巨人的文档累积的集合，包括超链接信息、访问及使用信息。传统 的数据挖掘大多足针对关系数据_ i 牢或数据仓库的，处卵的数据具有完整的结构，但足w e b 包含各种类型的数据，现有的数据库管理系统无法操纵和管理人显的非结构化数据，其用户 群体也表现h 多样性的特点。w e b 数据挖掘起源j ：数据挖掘，h 的在于可以处邶非结构化 的数据，w e b 数据的非结构化这一显著特征使w e b 数据挖掘更加复杂。 w e b 数据挖掘足一项综合技术，足利， j 数舫i 挖掘从w w w 资源上扪取信息( 或知识) 的 过程，是对w e b 资源中蕴涵的、未知的、有潜在应用价值的模式的提取。他反复使用多种 数据挖掘算法，从观测数据中确定模式或合删模型，也是将数据挖掘技术和理论应用于对 w w w 资源进行挖掘的一个新兴的研究领域。 对w e b 数据挖掘可做如下定义：w e b 数据挖捌足指w e b 从文档结构和使用的集合c 中 发现隐含的模式p 。如果将c 看作输入，p 看作输出，那么w e b 挖拥 的过租：就是从输入到 输出的t 个映射1 1 3 j ：a ：c 寸p 。 w e b 数据挖掘从数据挖捌发展i f i j 来，都是在分析人量数据的荩础卜，做出! fi 纳性的推 理，预测客户的行为，帮助食q k 的决策者调整市场策略、减少风险并做出正确决策的过程。 w e b 数据挖掘川以存很多方面发挥作用，如对搜索引擎的结构进行挖掘，确定权威贞面， w e b 文梢分类、w e bl o g 挖掘、年1 能查询、建、，：m e t a w e b 数据仓库等。w e b 挖抛研究覆盖 了多个研究领域，包括数据库技术、信息获取技术、统计学、人j i ：智能中的机器学习和神经 网络等。根据对w e b 数据的感兴趣程度不同，w e b 挖掘般可以分为t 类：w e b 内容挖 艇、 w e b 结构挖掘、w e b 用法挖掘。 2 1 2w e b 数据挖捌的原朋! 及实现 w e b 数据挖掘的苍本原理的处理过程f u l 图2 1 所示引1 6 1l i 9 11 2 3 1 。口标数据集就是根据用 户要求，从w e b 资源f f l 提l d c 的卡u 关数据，w e b 数据挖掘卡要从这些数据通信巾进行数据提 取；项处理是从1 1 标数据集中除上明 l ! 错洪的数据和冗余的数据，进一步精简所选数据的：f 丁 4 效部分，并将数据转换成有效形式，以使数据开采算法( 包括选取合适的模型和参数) 寻求感 兴趣的模型，并用一定的方法表达成某种易十理解的形式：模式分析是对发现的模式进行解 释和评估，必要时需返回前面处理中的某些步骤以反复提取，最后将发现的知识以能理解的 方式提供给用户。 图2 - lw e b 数据挖掘原理 与传统数据和数据仓库相比，w e b 卜的信息足：二结构化或、i ，结构化的、动态的、并h 是容易造成混淆的，所以很雄亢接以w e b 网页上的数 l t ；进 j ：数槲挖掘，而必须经过必要的 数据处i 哩。解决w e b ：的异构数据的集成与查询问题，就必须要自一个模型来清晰地捕述 w e b 上的数据。针对w e b 上的数 l l i 半结构化的特点，解决问题的关键在于寻找一个半结构 化的数据模型。因此，首先耍建立一个j 卜结构化数据模型，以描述w e b 上的数据；其次还需 要一种半结构化模攫抽取技术，即自动地从现有数据中抽取半结构化模型的技术。典制w e b 挖掘的处理流程如卜： ( 1 ) 查找资源：仃务足从h 标w e b 文梢f i 得到数捌，值得注意的是仃时信息资源4 i 仪 限丁往线w e b 文档，还包括电子邮件、电子文档、新n 日组，或者网站的日志数据甚伞是通 过w e b 形成的交易数据_ 年中的数据。 ( 2 ) 信息选择和预处理：任务是从取得的w e b 资源一i t 剔除无用信息和将信息进行必要 的整邢。例如从w e b 文档中自动去除j “牛连接、去除多余格式丰，j ：记、自动以别段落或者字 段并将数据组织成规整的逻辑形式甚虿是关系表。 ( 3 ) 模式发现：自动进行模式发现。可以往同。+ 个站点内部或枉多个站点之l d j 进行。 ( 4 ) 模式分析：验i j e 、解释卜一步骤产生的模式。u 以是机器向动完成，也l 叮以是与 分析人员进行交可米完成。 网络信息挖掘技术实现的总体流程女图2 2 所示。 5 图2 2w e b 数据挖掘实现的流程 2 1 3w e b 数据挖掘的数据特点 从数据库研究的角度出发，w e b 网站上的信息也可以看作个更大、更复杂的数据库。 w e b 上的每个站点就是一个数据源，每个数据源都是异构的，而且每个站点之问的信息和 纽织都不样，这就构成丫。个巨大的异构数据库环境。要利j h 这些数据进行数据挖掘，首 先要研究站点之间片构数据的集成问题，只有将这些站点的数据都集成起来，提供给用户一 个统一的视图，才囱可能从巨大的数据资源t l 一获墩所需的东四；j e 次，还要解决w e b i ：f r j 数据奁淘问题，因为f u i 果不能有效地得到所需的数据，对这些数据进行分析、集成、处理就 无从谈起l1 3 11 6 1 。 w e b 上的数据与f 譬统的数据阼中的数据不i 司，传统的数据库都有一定的数 i ! ：模型，可 以根据模型柬具体描述特定的数据。而w e b i ：的数据非常复杂，没自特定的模犁来描述， 每一站点的数掂都各自独立设计，并- l 数据本身见有自述性和动念l i j 变性。人l 而，w e b 上 的数据具仃一定的结构性，f u 因i ，| 述层次的存存，使j e 成为一种_ j l 完全结构化的数据，这也 被称为半结构化数据，半结构化足w e b 上数据的最人特点h i 。 2 1 4w e b 数据挖掘所采用的技术办法 w e b 数据挖掘中常用的技术舀w e b 使川的特有的路衽分析技术，数抛挖掘领域常川的 关联胤则、序列模式、分类聚类技术等1 1 2 0 1p 3 l 。 ( 1 ) 路径分析技术 用路径分析技术进行w e b 数据- 之b , i i 时，最常用的足i 刘。因为w e b 可以川一个自向图来 表示，g = ( v ，e ) ，其中：v 是贝面的集合，e 是页血之l 口j 的超连接集合，页面定义为图中的 顶点，而页而问的超链接定义为h i i l 的仃向边。顶点v 的入边表示对v 的引用，边表示v 0 i 加了其他的页面，这样肜成恻站结构图，从罔f f l 确定最频綮的访问路衽。 ( 2 ) 关联肌则挖捌技术 关联规n - j e 掘技术主要用于从厂乃户访序列数据用i 的序列项中挖掘出榭关的规则，就足 6 要挖掘出用户在一个访j 占jj i l l 问( s e s s i o n ) ，从服务器上访问的页面文件之问的联系，这些页面 之问可能并不存在直接的参弓l ( r i f e r e n c e ) 关系。最常用的是用a p r i o r 算法，从事务数据库 中挖捌出最大频繁访i 口j 项集，这个项集就是关联规则挖掘出来的用户访问模式。 ( 3 ) 序列模式挖掘技术 序列模式数据挖掘就足要挖掘出交易集之问的有时间序列关系的模式。他与关联挖掘技 术都是从用户访问下的口志中寻找用户普遍访问的规律，关联挖掘技术更注重事务内的关 系，序列模式技术则注重事务问的关系。 ( 4 ) 聚类分类技术 分类规则可以挖掘某些共同的特性，这个特性可以用来对新添到数据库里的数据项进 行分类。在w e b 数据挖掘中，分类技术l l j + 以根据访问这些用户而得到的个人信息或- j 乓1 j 的访 f , d 模式，得m 访问某服务器文件的用户特征。聚类技术则是对符合某+ 访i 丌j 规律特征的用 户进行用户特征挖掘。最后进行模式分析，挖捌出人们1 1 j 理角，f 的知识的模了l = 解释。 2 1 5w e b 数据挖 j i i 的应j f j 与发展趋势 w e b 数据挖掘已，“泛地应厂于金融业、远科通讯业、政府管理、制造业、医疗服务以 及体育事业i i 对他的应用和研究正在成为一个热点。w e b 数据挖抛的应用前景卡要表现在 3 个方面。 ( 1 ) 搜索引擎 用搜索引擎进 ：j ：i 】c ) 9 络信息挖掘的最人特色体现祚他所采用的对网页链接信息的挖掘技 术i ：。通过对网页内容挖抛，可以实现对网页的聚类、分类，实现网络信息的分类浏览与榆 索；运厂日网络内容挖掘技术改进火键侧加权算法，提高网络信息的标，j l 准确度，从l m 改善检 索效果。 ( 2 ) 电了商务 运用网络挖掘技术能够从服务器和浏览器端日：占记录i - r l 动发现隐藏存数据i i i 的模式 信息，了解系统的访i u j 模式以及川户的行为模式，从i 町做出顶测性分析。例如通过评价用户 埘某一信息资源浏览所花的时问，可以削断剧户对资源兴趣如何等l 1 。 ( 3 ) 叫站发计 通过对网站内容的挖扣l ，可以自效地组织网站信息，例如通过对刚户访问日志记录信息 的挖掘，把握厂玎户的必趣，有助于j l ：腱i ) c ) 9 站信息推送服务以及个人信息的定! 6 - 州j 务。u 时 p d a ( p e r s o n a ld i g i t a l a s s i s t a n t ，个人数宁助理) 以及m o b i l ep h o n e ( 移动电话) 鄙已经可以直 接接受网络信息服务。 7 2 2 搜索引擎技术 2 2 1 搜索引擎的概念 搜索引擎，指的是种在w e b 上应用的软什系统，它以一定的策略在w e b 上搜集和发 现信息，在对信息进行处理和组织后，为用户提供w e b 信息查询服务6 1 。从使用者的角度 看，这种软件系统提供一个网页界面，让他通过浏览器提交一个词语或者短语，然后很快返 回一个可能和用户输入内容相关的信息列表。这个列表中的每一条日代表一篇网页，至少有 3 个元素： ( 1 ) 标题：以某种方式得到的网页内容的标题。最简译的方式就是从网贝的 标签巾提取的内容。 ( 2 ) u r l ：该网负对应的“访问地址”。有经验的w e b 用户常常町以通过这个元索对 网页内容的权威性进行削断，例如h t t p ：w w w p e o p l e c o mi ：而的内容通常就比h t t p ：w w w n o t r e s p o n s i b l e n e t ( 某个假想的个人网站) 上的要更权威些( 不排除后者上的内容更有趣些) 。 ( 3 ) 摘要：以某种力式得剑的网页内容的摘要。最简译的一种办式就是将网页内容的 头若十字+ 1 ，截取下米作为摘要。 用户通过浏览这些元素，可以对相应的网页是否真正包含他所需的信息进行削断。比较 肯定的话则i 叮以点击一卜述u r l ，从而得到该网负的全文。当然根据用户所提交的杏询信息 的关键同，系统会返回一个相关的信息列表，列表的每一条目所含内容比1 ：述要中高些，仙 核心还是那三个元索。但是，我们应该注意这样一个问题，即搜索引擎提供信息杏询服务的 时候，它1 f l i 对的只址佥询阋。而仃不同背景的人可能提交相同的企询词，关心的足和这个查 咖训棚火的小同方面的信息，但搜索0 i 擎通常是彳i 知道用户背景的，大l 此搜索，j i 擎既要争取 不漏掉仟何相关的信息，还要争墩将那些“最可能被关心”的信息排在列表的前而。这也就 是对搜索0 i 擎的根小要求1 6 1 【1 。除此以外，考虑到搜索引擎的成用环境是w e b ，洲此对人 篮并发片j 户企询的响应r e 能也足一个不能忽略的力。 2 2 2 搜索引擎的发展历史 甲在w e b 现之前，白：联网i ：就已经存在许多旨存让人们共享的信息资源了。那些资 源当时主要存征于，行种允诈：匿名访j u j 的f t p 站点，内锌以学术技术报告、研究惟软件居多， 它们以计算机文件的形式存在，文。，材料的编码通常足p o s t s c r i p t 或者纯文本。为了便丁人 们征分散的f t p 资源巾找到所需的尔两，1 9 9 0 年加拿大麦吉尔大学( u n i v e r s i t yo f m c g i l l ) 计算机学院的师生开发了一个软件a r c h i e l 6 1 。已通过定期搜集并分析f t p 系统l t 存柞：的文件 名信息，提供杏找分斫j n i 各个f t p 主机中义件的服务。a r c h i e 能在：j 知道艾件名的胁提下， 8 为用户找剑这个文件所在的f t p 服务器的地址。a r c h i e 实际上是一个大型的数据库，再加 上与这个大型数据库相关联的一套检索方法。该数据库中包括大量町通过f t p 下载的义件 资源的有关信息，包括这些资源的文件名、文件长度、存放该文件的计算机名及目录名等。 随着w w w 的发展，以w e b 网页为对象的搜索引擎产生，其是利用h t m l 文档之间的 链接关系，在w e b 上+ 个网页、一个网页的“爬取”( c r a w l ) ，将那些网页“抓”( f e t c h ) 到 本地后进行分析。斟此，如何在w e b 上“爬取”，就是搜索引擎要解决的一个基奉问题。在 这办而，1 9 9 3 年m a t t h e wg r a y 开发了w o r l dw i d ew e bw a n d e r e r ，它是世界上第个利用 h t m l 网负之问的链接火系来监测w e b 发展规模的“机器人”( r o b o t ) 程序，鉴于其在w e b l ：沿超链“爬行”的工作办式，这种程序有u 寸也称为“蜘蛛”( s p i d e r ) ，即在w e bi j 依照网 贝之间的超链关系一个个抓取网贝的程序，通常也称为“搜集”。 现代搜索引擎的思路源予w a n d e r e r ，不少人在m a t t h e wg r e y 工作的基础1 ：对它的蜘蛛 程f 做了改进。l9 9 4 年7 月，m i c h a e lm a u l d i n 将j o h nl e a v i t t 的蜘蛛程序接入到其索引程序 ，| i 创建了大家现存熟知的l y c o s ，成为第一个现代意义的搜索引擎。随着w e b 1 ：信息的爆 炸性增长，搜索引擎的应用价值也越米越高，彳i 断有更新、更强的搜索引擎系统推m f 2 1 1 1 3 1 。 比如，g o o g l e e 采用了独特的p a g e r a n k 技术，使e 成为当前全球最受欢迎的搜索引擎。在 中国，对搜索引擎的研究起源十“中国教育科研网”( c e r n e t ) 一期i ：挥中的予项口，北 五r 大学计算机系的项日组l 任陈葆珏教授的卡持卜丁1 9 9 7 年l o 月在c e r n e t ，i ：推了天网 搜索1 0 版本。在这之后，是百度公刊于2 0 0 0 年推出+ j ，“百度”商业搜索引擎 ( h t t p ：w w w b a i d u c o m ) ，月前一直处丁囡内搜索引擎的领先地位。 搜索引擎出现虽然j 仃l o 年左右的历史，但在w e b 上已经有j ，很重要的地化。据c n n i c 统计，它已经成为继电子邮件之后的第_ 大w e b 应用。虽然它的肚木工作原理已绛相当稳 定，但在其质最、性能和服务方式等方面的提高空问依然很人，研究成果也层出1 i 穷。 2 2 3w e b 搜索引警的_ t _ f l - 原理 搜索t j i 擎是一个嘲络麻用软件系统( 如图2 3 ) ，它能够接受用户通过浏览器提交的查 询词或哲短语，记作q ，例如“贵州大学9 99 “数据挖抛”等等，并可以在一个可以接受的时 l n j 内返回。个和该厂订户查询匹配的网页信息列农，记作l ，这个列农的每条u 仝少包龠三 个元素：标题、网址链接和摘要。这咀所指的“可以接受的州问”足指在w e bi ：的响应时 问，是衡最搜索，j j 擎口j 用忡的。个基本指标；所谓“匹配”，指的是网页中以某种形式包含 有q 的内容，其一 t 最简币、最i 接的形式就足q 在其i l i 血接现。目前，一般人规模岛质量 搜索0 i 擎都采用三段式的i ：作流程：网页搜集、颁处理和杏咖服务。1 6 1 9 q | t q l t 工l 搜锻，j | 锈 m6 f 效獬盼 图2 3 收索引擎示意图 ( 1 ) 网贞搜集 南丁搜索引擎是一个工作在某个数据集合上的软件系统，这个软什系统操作的数据不仪 包括内容不叮预测的用户查询，还要包括在数量上动态变化的海量网页，并且这些网贝不会 十动送到系统来，而是需要由系统去抓取。在抓墩过程巾，酋先要考虑抓取的时机，通常从 网上下载一篇网页人约需要1 秒钭- 左右，队i 此如果在用户查淘的时候即时去网上抓来成干上 万的网页，。个个分析处理，和用，r l l 的查询匹配，不可能满足搜索引擎的响应i 忖问要求。不 仅如此，这样做的系统效益也不高；另外，面对人最的用户查洵，不- i ，能想象每来一个杏治j ， 系统就到网l ：“搜索”一次。因此，搜索引擎服务的基础应该足自一批预先收集好的网页。 对于这批i ) i ) 9 页的维护策略一般采j l j 两种方法：定期搜集和增量搜集。 定期搜集是每次搜集替换卜一次的内容，既“批量搜集”。由丁：每次都是蘑新来一次， 对0 二人规模搜索引擎米说，每次搜集的时问通常会花儿周。而由于这样做丌销较人，通常凹 次搜集的间隔u 寸问也不会微短，虽然这样做的好处地系统实现比较简单，仙j e 卡要缺点址“时 新性”4 i 高，还有重复搜集所带来的额外带宽的消耗。 增爷搜集，开始u j 搜集一批，然后搜集新现的网页，搜集那止电存l ：次搜集后自过改变 的嗍页，同时对手上次搜集后已经不再存白i j ，的网页从席中删除。这样的系统= 2 乏现出米的信 息时新性就会比较高，卜要缺点足系统实现比较复杂，这种复杂还不仅存丁搜集过程，而足 还4 ：十下面要谈到的建索引的过程。 在具体搜集过程t l ，如何抓取一篇篇的网页呢? 最常见的一种是所谓“爬取”：将w e b 上的网页集合看成是。个有向图，搜集过程从给定起始u r l 集合s ( 或者说“种了”) j i ：始， 沿着网页- i - 的链接，按照先深、先宽、或者某种别的策略遍历，不停的从s - i 移除u r l ， 下载，f h 虑的网页，解析出刚页中的超链接u r l ，看是否已经放访i 、u j 过，将未访i u j 过的那些 u r l 加入集合s 。整个过程可以形象地想象为一个蜘蛛( s p i d e r ) 存蜘蛛网( w e b ) 卜爬行 ( c r a w l ) ，将 _ 1 描该网站的所有网页并将有关信息存入数据席中0 6 1 1 1 3 11 3 3 1 。 ( 2 ) 预处理 随便取篇网页的源义件( 例f ( 1 l 通过浏览器的“杏石源义件”功能) ，我们口j 以石剑其 1 0 中的情况纷乱繁杂。除了我们从浏览器中能够正常看到的文字内容外，还有大量的h t m l 标记。另外，由于h t m l 文档产生来源的多样性，许多网贞在内容上比较随意，不仅文宁 不讲究规范、完整，而且还可能包含许多和主要内容无关的信息( 例如广告，导航条，版权 说明等) 。因此，必须对数据进行预处理，作为预处理阶段的一个黛本任务，就是要提取出 网页源文件的内容部分所含的关键词。对于中文来说，就是要根据一个词典，用一个所谓 “切词软件”，从网页文字中切出所含的侧语来。在郧之后，一篇网页主要就由一组词来 近似代表了，p = t l ，t 2 ，t n ) 。 另外，还用考虑网负重要程度的计算，因为搜索引擎返叫给用户的，是一个和用户查询 相关的结果列农，列表巾条目的顺序是很重要的一个问题。由于而对各种各样的用户，加之 查询的自然语言风格，对吲样的q 0 返i u l 相j 叫的列袭肯定是不能使所有提交q 0 的用户都满意 的，因此搜索引擎实际i ：追求的足种统计意义l ：的满意。 ( 3 ) 查询服务 在w e b 搜索的过程- i i ，从一个原始网页集合s 丌始，预处理过程得剑的足对s