（计算机应用技术专业论文）web挖掘中搜索引擎的研究.pdf

摘要 摘要 随着互联网的快速发展与广泛应用，网络上的信息量几乎每天以百万级的速度增 长，互联网已成为当今人们获取所需资源和信息交流的主要场所。i n t e m e t 是一个开放 的网络，网络中的信息具有分布、动态、异质、复杂、开放性及海量数据的特点，没有 统一的管理和结构，使得人们很难很快搜索出真正需要的信息，如何快速、准确地从浩 瀚的信息资源中找到有用的信息是网络用户面临的一个大问题，因此希望有新的工具来 定位信息资源。 网络信息搜索技术结合了现代信息检索技术和w w w 的相关技术，旨在研究开发 出一个智能化的搜索软件，能在网络上自动地进行信息发现和索引，建立结构化索引库， 向用户提供查询服务，这种技术的呈现给用户的表现就是搜索引擎。 随着互联网的迅猛发展，搜索引擎的发展越来越需要借助各种技术来进一步推动。 作为数据挖掘中新的研究内容的w e b 挖掘，由于自身在信息处理中的层次较高，与搜 索引擎的关系非常密切，对搜索引擎技术有很大推动、辅助作用。所以搜索引擎通过应 用w e b 挖掘技术，可以增强信息处理能力，使得信息检索发展到一个新的水平。搜索 引擎中一个很重要的关键点就是把搜索到的页面中最重要的信息展现给用户。这就涉及 到网页的排序问题。 本文在首先学习了w e b 挖掘和搜索引擎的基础知识，分析了两者之间的区别，指 出w e b 挖掘对搜索引擎发展的辅助作用，并引出本文研究对象p a g e r a n k 算法。 在p a g e r a n k 排序算法进行深入研究的基础上，提出对p a g e r a n k 算法的改进p r p ( p a g e r a n kb a s e do np a g el e v e l ) 算法，并在p r p 算法的基础上进行分析完善，提出了 b p p ( b a s e do np a g e r a n k sp a g e r a n k ) 算法，并通过模拟试验证明p r p 算法和b p p 算 法比p a g e r a n k 算法具有一定的优越性。 关键词：w e b 挖掘；搜索引擎；p a g e r a n k ；p r p ；b p p a b s t r a c t a st h ei n t e r a c t sr a p i dd e v e l o p m e n ta n dw i d ea p p l i c a t i o n ，t h ea m o u n to fi n f o r m a t i o no n t h en e ti n c r e a s e s b ym i l l i o n se v e r yd a y i n t e m e th a sb e c o m et h ep e o p l e s m a i nw a y t og e t r e s o u r c e sa n dt h ep r i m a r yv e n u ef o rt h ee x c h a n g eo fi n f c i r r n a t i o n i n t e m e ti sa no p e nn e t w o r k t h ei n f o r m a t i o no nt h en e th a st h ec h a r a c t e r i s t i c so fd i s t r i b u t i o n ，d y n a m i c ，h e t e r o g e n e o u s ， c o m p l e x ，o p e n ，a n dl a r g ea m o u n t so fd a t a t h ei n f o r m a t i o nh a s n ou n i f i e dm a n a g e m e n ta n d s t r u c t u r e ，m a k i n gi td i f f i c u l t t oq u i c k l ys e a r c ho u tt h er e a ln e e d s h o wt of i n d u s e f u l i n f o r m a t i o nf r o mt h ev a s ti n f o r m a t i o nr e s o u r c e sq u i c k l ya n da c c u r a t e l y t of i n d u s e f u l i n f o r m a t i o ni sab i gp r o b l e mp e o p l eh a v et of a c e ，s op e o p l eh o p et oh a v en e wt o o l st ol o c a t e i n f o r m a t i o nr e s o u r c e s n et e c h n o l o g ys e a r c h i n gi n f o r m a t i o no nt h ei n t e r a c tc o m b i n e st h et e c h n o l o g y o f m o d e mi n f o r m a t i o nr e t r i e v a la n dt h ew w wt e c h n o l o g y i ta i m sd e v e l o p i n ga ni n t e l l i g e n t s e a r c he n g i n e ，w h i c hf i n d si n f o r m a t i o no nt h ei n t e r n e ta u t o m a t i c a l l y ，i n d e x e sas t r u c t u r e d a t a b a s ea n ds e r v e st h ei n t e r n e tu s e r s a n da l lo ft h e s et op e o p l ei ss e a r c he n g i n e w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e t ，s e a r c he n g i n e sf u r t h e rd e v e l o p m e n ts h o u l db e a c c e l e r a t e db vt h ea s s i s t a n c eo fv a r i o u sn e w l ya n de f f i c i e n tt e c h n i q u e w e bm i n i n g , a st h e n e w e s ts e a r c ho fd a t am i n i n g , b e c a u s eo fi t sh i g hl e v e li n f o r m a t i o np r o c e s s i n ga n di ti sv e r y c l o s et ot h es e a r c he n g i n et e c h n o l o g y ，i tc a na c c e l e r a t et h es e a r c he n g i n e sd e v e l o p m e n t s o t h eu s i n go fw e bm i n i n gt e c h n i q u e si nt h es e a r c he n g i n ec a ne n h a n c ei n f o r m a t i o np r o c e s s i n g c a p a b i l i t i e s m a k i n gi n f o r m a t i o nr e t r i e v a lt oa n e wl e v e l av e r yi m p o r t a n tk e yp o i n tf o rs e a r c he n g i n ei sh o wt od i s p l a yp a g e sw h i c hh a s i n f o r m a t i o nn e e d e dt ou s e rt ot h eu s e r i ti n v o l v e st h ea l g o r i t h mo ft h ep a g e s r a n k i n g i nt h i sp a p e r , w el e a r nt h eb a s i c so fw e bm i n i n ga n ds e a r c he n g i n e ，a n dt h e na n a l y s i so f t h ed i f f e r e n c eb e t w e e nt h et w o ，n o t i n gt h a tw e bm i n i n g ss u p p o r t i n gr o l ef o rs e a r c he n g i n e s d e v e l o p m e n t a n dt h ep a g e r a n ka l g o r i t h mi sl e a d e d b yr e s e a r c h i n gp a g e r a n ka l g o r i t h m ，n ep r p ，b a s e do np a g e r a n ka l g o r i t h m ，i sp u t f o r w a r d a n dt h e n ，t h r o u g ha n a l y z i n ga n dp e r f e c t i n gt h ep r p ，t h eb p pa l g o r i t h mi sb r i n g f o r w a r d a n db p pa l g o r i t h mh a sc e r t a i na d v a n t a g e si sp r o v e dt h r o u g ht h es i m u l a t i o nt e s t k e yw o r d s ：w e bm i n i n g ；s e a r c he n g i n e ；p a g e r a n k ；p r p ；b p p 大连交通大学学位论文版权使用授权书 本学位论文作者完全了解丕董塞通太堂有关保护知识产权及保 留、使用学位论文的规定，即：研究生在校攻读学位期间论文工作的 知识产权单位属太整交通太堂，本人保证毕业离校后，发表或使用 论文工作成果时署名单位仍然为太整塞通太堂。学校有权保留并向 国家有关部门或机构送交论文的复印件及其电子文档，允许论文被查 阅和借阅。 本人授权太董塞通太堂可以将学位论文的全部或部分内容编入 中国科学技术信息研究所中国学位论文全文数据库等相关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后应遵守此规定) 锄挠砀城 日期：矽罗年1 月f 日 学位论文作者毕业后去向：参加工作 工作单位：北京市江河瑞通技术发展有限公司电话：1 5 9 4 2 8 2 2 0 7 5 通讯地址：北京市海淀区上河村b 2 ，8 - 9 层邮编：1 0 0 0 5 3 电子信箱：l i n g c s y 19 8 3 y a h o o t o m c n 大连交通大学学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果j 尽我所知，除了文中特别加以标注和致谢及参考 文献的地方外，论文中不包含他人或集体已经发表或撰写过的研究成 果，也不包含为获得太整塞通太堂或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 本人完全意识到本声明的法律效力，申请学位论文与资料若有不 实之处，由本人承担一切相关责任。 学位论文储始酣驾 魄妒7 年p 月f 日 第一一章绪论 第一章绪论 介绍该论文的研究背景及w e b 挖掘在国内外的研究现状，通过分析国内外的w e b 挖掘研究水平，指出现有技术的不足，并在此基础上说明本文研究的意义和主要工作， 最后给如本文的组织结构。 1 1 研究背景和意义 随着i n t e r a c t 的快速发展与广泛应用，网络上的信息量几乎每天以百万级的速度增 长，互联网已成为当今世界人们获取所需资源和信息交流的主要场所。然而，由于网络 中的信息具有分布、动态、异质、复杂、开放性及海量数据的特点，使得人们很难很快 搜索出真正需要的信息，从而面临着“信息爆炸而知识匾乏”的问题。面对这种情况， 产生了大量搜索引擎，例如g o o g l c 、l y c o s 、y a h o o 、百度、中搜、有道等搜索引擎。 然而即使使用搜索引擎大大减少了无用信息的干扰，这些搜索引擎搜索的结果仍然存在 不完整或不相关的问题，很难完全满足用户的需求。分析这个“不完整或不相关 问题， 主要归纳为下述缺点1 1 j ： 1 低质量页面。有的页面只有寥寥数语，包含的信息量很少；有的页面提供的信息 价值非常一般。 2 不同主题的页面。一词多义是自然语言的常见现象；在不同领域，同一个词也常 有常规之外的特定含义。在查询时，用户往往感兴趣的是查询词的某一特定含义代表的 信息内容，但是搜索引擎却将所有的页面一起提交给用户，降低了用户的查询效率。 3 重复页面。由于版权、镜像、常用文档的广泛传播等原因，w e b 上有许多合法 的重复页面。此外，一些有价值的页面被别的站点拷贝或转载。研究表明，w e b 上约 6 0 的页面是重复页面1 2 l 。 4 欺骗问题( s p a m m i n g ) 。由于大多数搜索引擎的相关度评价是采用了一定的规则来 对搜索到的网页进行排名，而经验规则其大多数又是和基于关键词的检索算法相关联 的。一些人就是利用搜索引擎的相关度评价策略，在自己的页面中用不正当的手段，提 高检索中的排名，这类现象称为“s p a m m i n g ”。 互联网是一个巨大的、分布广泛的、全球性的信息服务中心，涉及新闻、广告、消 费者信息、金融管理、教育、政府、电子商务等几乎所有信息。与此同时，w e b 由于自 身固有特点，包含了丰富和动态的超链接信息，以及w e b 页面的访问和使用信息。通 过对w e b 中网页自身的内容提取和对网页之间的链接信息、结构进行分析，可以获取 人近交通人学i ：学硕 ：学f 一论文 大量的有用信息，从而提出了w e b 挖掘的概念。然而，现有w e b 的各种特点也导致 w e b 挖掘具有很大难度p j ： 1 w e b 信息量太大。w e b 的数据是以g 字节计算，并且增长速度特别快。w e b 包 涵了社会中几乎全部方面的信息，而数据挖掘中所必须用到的数据仓库存在存储量的问 题，不可能构造一个数据仓库来复制、存储或集成w e b 上的所有数据。 2 w e b 页面的复杂性。传统数据挖掘需要数据具有统一的结构。然后w e b 网页没 有固定结构，包含了远比任何一组书籍或其他文本文档多的风格和内容。 3 w e b 信息的动态性。w e b 不仅以极快的速度增长，而且其页面信息还在不断地更 新，链接信息和访问记录也在频繁地更新。这就造成了数据存储中大量数据更新的难度。 4 w e b 用户的复杂性。由于各个用户不同的背景、兴趣和使用目的，各个用户需要 信息的内容层次，获取信息的方法都不同，很难满足各类用户的要求。 5 w e b 信息的有效性。互联网上存在真正对用户有用的信息极少，大量的无用信息 会造成对有效信息的干扰，增大搜索有效信息的难度。 这些挑战已经推动了如何快速且有效地发现和利用因特网资源的研究工作。w e b 挖 掘是一个更具挑战性的课题，它能实现对w e b 的存取模式、结构、规则和动态的w e b 内容的查找。本文的研究工作源于上述背景，目的是对w e b 结构挖掘技术进行深入的 学习研究，探讨w e b 结构挖掘中的关键算法p a g e r a n k ，并对p a g e r a n k 算法做出改进来 提高w e b 挖掘的效率及改善挖掘的精确度。 1 2 研究的现状和主要内容 自m i n gs y a nc h e n 、h m a l m i l a 等人于1 9 9 6 年在t h e1 6 t hi n t e r n a t i o n a lc o n f e r e n c eo n d i s t r i b u t e dc o m p u t i n gs y s t e m s 大会上把数据挖掘概念应用到w e b 服务器上的想法首次 提出来以来，w e b 挖掘作为数据挖掘的一个新主题，形成一个新兴的研究领域。 互联网的快速发展，使得对w c b 访问获取需求信息变得越来越迫切，许多国家把 这项研究作为重点资助科研项目。w e b 挖掘也得到了极大的发展。近几年国外的研究取 得了巨大发展，比较有代表性的研究成果有： 在w e b 日志内容挖掘方面s i m o nf r a s e r 大学的w e bl o gm i n e r 将w e b 日志中的数据 组织为数据立方体，然后在其上进行联机分析处理和数据挖掘，用于发现用户的访问模 式，并提出了g r a p h m i n e r t 4 1 。b o r g e sj 等提出了超链接概率原理1 5 j ，修改了传统意义上 对序列的界定，可以把用户的访问在网站结构图中记录下来，根据访问条件概率判断用 户频繁访问路径。z m a n eo r 等通过对w e b 站点的日志进行处理，将数据组织成传统的 2 第一一章绪论 数据挖掘方法能够处理的事务数据形式，然后利用传统的数据挖掘方法( 如关联规则发 现算法) 进行处理，所得出的挖掘结果是传统的数据挖掘结果1 6 l 。 在w e b 结构挖掘方面，w e i s s 通过聚类的方法来考虑w e b 上的超链接结构信息1 7 j ， s p e r t u s 则是讨论了如何将从链接结构获得的信息应用于各种实际应用中【8 j 。l a w r e n c e p a g e ，s e r g e yb r i n 利用网页之间的链接关系创造出p a g e r a n k 算法【9 1 ，并据此创立g o o g l e 公司，成为目前全球第一搜索引擎。 与国外相比，国内对数据挖掘的研究起步较晚。目前，国内从事数据挖掘的人员主 要在大学，也有部分在研究所和公司。国内许多科研单位和高等院校开展数据挖掘的基 础理论及其应用研究，这些单位包括清华大学、中科院计算机技术研究所、空军第三研 究所、海军装备论证中心等。其中，北京系统工程研究所对模糊方法在知识发现中的应 用进行了较深的研究；北京大学也在开展对数据立方体代数的研究；华中理工大学、复旦 大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等单位开展了对关联规 则算法的优化和改造；南京大学、上海交通大学等单位讨论、研究了非结构化数据的知识 发现以及w e b 挖掘。所涉及的研究领域很多，一般集中于学习算法的研究、数据挖掘 的实际应用以及有关数据挖掘理论方面的研究。目前进行的大多数研究项目是由政府资 助进行的，如国家自然科学基金、8 6 3 计划、“九五 计划等。 目前，国内对w e b 挖掘具有代表性的研究成果有： 浙江大学董金祥教授等研究w e b 用户浏览活动的本质，根据w e b 用户在网站中各 页面的停留时间和访问次数等特征，结合用户的参与，识别、建立、调整该用户的喜好， 提出兴趣强度及度量方法【1 0 1 ，使用户能以个性化方式来访问。 西安交通大学陆丽娜教授等，采用基于事务的方法，研究w e b 访问信息挖掘预处 理及用户访问序列模式挖掘方法，提出了一种基于扩展有向树模型进行用户浏览模式识 别的w e b 访问信息挖掘方法i l 。 清华大学马少平教授等，提出一种利用w e b 服务器同志文件，运用n 元( n g r a m ) 预测模型对用户未来可能进行的w e b 访问请求进行预测i l 引。 中国科学院数学研究所周龙镶教授等，分析了w e b 用户浏览活动规律，提出了有 关w e b 浏览路径的一些基本概念，设计了基本用户访问模式的浏览路径优化算法【1 3 j 。 上海交通大学尤晋元教授等引入w e b 页面的内容链接比、页组组内链接度，修改 了频繁访问页组支持度的计算公式，提出了基于页面内容和站点结构的页面聚类挖掘改 进算法【1 4 1 。 3 人连交通人学h ! ：硕十学位论文 1 3 本文的研究意义和主要工作 目前的搜索引擎普遍存在精度低和搜全牢低的问题。精度低主要表现在当用户输入 关键词检索信息时，返回的查询结果动辄成百上千条，更有甚者会达到几十万乃至上百 万条，而其中大多数是一些与检索内容无关的信息，也包括一些无效链接，使查询者无 所适从；搜全率低是由于w e b 上大量的信息未被索引或未被正确索引，因此导致搜索 引擎返回的查询结果并不全面，大部分有用的消息不能被搜索到。而w e b 结构挖掘是 从w w w 链接结构关系网络中推导知识。它主要是针对w e b 页面之间的超链接结构、 内部结构和u r l 中的目录路径结构进行挖掘，从中抽取知识。这样以来可以提高搜索 引擎的效率。在w e b 结构挖掘的传统算法中，p a g e r a n k 已经成功应用在g o o # e 搜索引 擎当中，而h i t s 也成功应用在i b m 的c l e v e r 系统中，都取得了很好的效果。但同时由 于p a g e r a n k 算法和h i t s 算法只考虑w e b 网页之间的链接关系，而没有考虑网页本身 的文本内容，对其中些权威页面随着时间的推移，会不断赋给更高的等级值，对新出 现的比较重要的网页只赋予很低的等级值，导致搜索的结果出现与主题偏离的现象。 鉴于上述原因，我们在深入学习研究p a g e r a n k 算法的基础上，首先做出了对 p a g e r a n k 算法的改进算法一p a g e r a n k b a s e do np a g el e v e l ( p r p 算法) ，并在p r p 算法 的基础上，提出了b a s e do np a g e r a n k sp a g e r a n k ( b p p 算法) ，并给出相关实验证明。 本文主要完成了以下几个方面的工作： 1 分析现有w e b 挖掘的分类及其研究热点，以及w e b 挖掘在搜索引擎中的应用。 2 分析学习w e b 结构挖掘经典算法，即p a g e r a n k 。 3 基于对p a g e r a n k 算法强化学习，提出一种w e b 结构挖掘的改进算法p r p ， 该算法引入了用户对网页进行评价，得到网页等级( p a g e ，并把网页等级加入到1evel) p a g e r a n k 算法中进行改进，从而得到p r p ，并通过模拟数据证明其改进算法的正确性。 4 结合w e b 结构挖掘中p a g e r a n k 算法，针对已经提出的p r p 算法，分析p r p 算 法的潜在缺陷，提出一种基于p a g e r a n k 算法的改进算法b p p 算法，并利用模拟数 据实验分析b p p 算法的有穷性、正确性和可行性，最后实验证明b p p 算法的优越性。 1 4 论文的组织结构 本文共包括六章，各章的主要内容如下： 第一章绪论，介绍论文的研究背景。互联网的迅猛发展推动了w e b 挖掘的产生及 发展，互联网中网页包涵的信息越来越多，信息增长速度越来越快，传统搜索引擎在检 索结果上自身的局限性致使了现有搜索引擎搜索结果存在精度低和搜全率低的问题，指 4 第一幸绪论 明了研究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 挖掘和搜索引擎，说明了w e b 挖掘的三个方 面分别在搜索引擎中的应用。 第三章p a g e r a n k 算法。简单讲解了p a g e r a n k 算法的产生背景和起源，描述了 p a g e r a n k 算法的基本思想和计算过程，并通过一个网页链接结构图来进行了p a g e r a n k 算法计算过程的详细说明。最后分析了影响p a g e r a n k 的各个因素。 第四章特定条件下p a g e r a n k 算法的改进p r p 算法，通过分析现有算法的缺点， 在特定条件下提出p a g e r a n k 进行了一定的改造方法，并通过模拟实验给予初步证明。 第五章b p p 算法。结合w e b 结构挖掘中p a g e r a n k 算法，针对已经提出的p r p 算 法，分析p r p 算法的潜在缺陷，提出一种基于p a g e r a n k 算法的改进算法一b p p ，并 利用模拟数据实验分析b p p 算法的有穷性、正确性和可行性，最后针对第四章的模拟数 据，采用b p p 算法计算出每个网页的b p p 值，并与p r p 算法的实验结果进行比较，证 明出b p p 算法的优越性。 第六章对整个论文工作进行了总结和展望，总结了整个论文的背景和作者在整个论 文中的工作，并在针对论文中的算法提出一定的意见，并指出在现有研究的基础上， 可以得到提升和改进的意见，期望在以后工作学习中进行的进一步的研究。 5 人连变通人羊i ：硕卜忙论文 第二章w e b 挖掘和搜索引擎 2 1w e b 挖掘的起源和定义 2 1 1w e b 挖掘的起源 数据挖掘是从大量数据中提取或“挖掘”出隐含的、事先未知的、潜在的有用信息。 例如：股票分析系统就是从日积月累的大量的股票行情变化的历史记录中发现其规律， 以预测未来股票的整体发展趋势；大型超市的管理人员希望能从过去几年的销售记录 中，从不同时间段时间、地点等各个方面分析顾客的消费习惯和行为，以便及时变换营 销策略等等。 原则上讲，数据挖掘可以在任何类型的信息存储上进行。这包括关系数据库、数据 仓库、事务数据库、先进的数据库系统、展平的文件和w w w 。先进的数据库系统包括 面向对象和对象关系数据库；面向特殊应用的数据库，如空间数据库、时间序列数 据库、文本数据库和多媒体数据库。挖掘的挑战和技术可能因存储系统而异。 w w w 以超文本的形式给用户提供了包含从技术资料，商业信息到新闻报道，娱乐 信息等多种类别和形式的信息，可以说w w w 是当今世界上最大的电子信息仓库，蕴 含着巨大潜在价值的知识。然而，i n t e r n e t 是一个具有开放性、动态性、异构性的全球 分布式网络，资源分布分散，没有统一的管理和机构，这就导致了获取信息、知识的困 难，即所谓的富资源穷信息( r i c hd a t ap o o ri n f o r m a t i o n ) 的问题。这样，运用现有数据挖 掘技术对分布的、异质的w e b 信息资源进行挖掘，就成为了数据挖掘技术的挑战和未 来的发展方向，由此产生了基于w e b 的挖掘。 2 1 2w e b 挖掘的定义 w e b 挖掘涉及数据库技术、计算机语言学、计算机网络技术、信息检索等多个领域 的知识。不同研究者从自身的领域出发，对w e b 挖掘的含义有着不同的理解，项目开 发也各有其侧重点。 国外有人认为w e b 挖掘就是利用数据挖掘技术，自动地从网络文档以及服务中发 现和抽取信息的过程【1 5 】。国内的说法也各持己见。有学者将网络环境下的数据挖掘归入 网络信息检索与网络信息内容的开发。也有学者站在信息、服务的角度上提出“w e b 挖 掘”，指出其有别于传统的信息检索，能够在异构数据组成的信息库中，从概念及相关 因素的延伸比较上找出用户需要的深层次的信息。w e b 挖掘定义为：针对包括w e b 页 面内容、页面之间的结构、用户访问信息、电子商务信息等在内的各种w e b 数据，应 6 第：审w e b 挖掘和搜索引擎 用数据挖掘方法以发现有用的知识来帮助人们从w w w 中提取知识，改进站点设计， 更好地开展电子商务1 1 6 j 。 从更一般的角度出发，p i t k o wj 等对w e b 挖掘作的如下定义，w e b 挖掘就是从w e b 文档和w e b 活动中抽取感兴趣的潜在的有用的模式和隐藏的信息1 1 。7 1 。 因此通常有两种对w e b 挖掘的定义： 1 从一般的角度出发，对w e b 挖掘作如下的定义： 定义1 ：w e b 挖掘是指从大量w e b 文档的集合c 中发现隐含的模式p 。如果将c 看 作输入，将p 看作输出的话，那么w e b 挖掘的过程就是从输入到输出的一个映射宇： c 畸po 2 如果从实用性项目开发的角度来考虑的话，可以对w e b 挖掘做出如下的定义： 定义2 ：w e b 挖掘是针对包括w e b 页面内容、页面之间的结构、用户访问信息、电 子商务信息等在内的各种w e b 数据源，在一定基础上应用数据挖掘的方法以发现有用 的知识来帮助人们从w w w 中提取知识，改进站点设计，更好地开展电子商务。 w e b 挖掘比传统的数据挖掘要复杂的多，它是针对w e b 页面内容、站点拓扑结构、 用户访问信息、用户注册信息及电子商务交易信息等在内的各种数据进行挖掘。w e b 挖 掘可以帮助人们从万维网中发现知识，改进站点设计，提供个性化服务。w e b 挖掘有自 身的特点： 1 w e b 挖掘的对象是大量、异质、分布的w e b 文档。我们认为，以w e b 作为中间 件对数据库进行挖掘，以及对w e b 服务器上的日志、用户信息等数据所开展的挖掘工 作，仍属于传统的数据挖掘的范畴。 2 w e b 在逻辑上是一个由文档节点和超链接构成的图，因此w e b 挖掘所得到的模 式可能是关于w e b 内容的，也可能是关于w e b 结构的。 3 由于w e b 文档本身是半结构化或无结构的，且缺乏机器可理解的语义，而数据 挖掘的对象局限于数据库中的结构化数据，并利用关系表格等存储结构来发现知识。因 此有些数据挖掘技术并不适用于w e b 挖掘，即使可用也需要建立在对w e b 文档进行预 处理的基础之上。这样，开发新的w e b 挖掘技术，以及对w e b 文档进行预处理以得到 关于文档的特征表示，便成为w e b 挖掘研究的重点。 2 2w e b 挖掘的分类及相应研究方法 目前在该研究领域中，由于w e b 上信息的多样性决定了w e b 挖掘任务的多样性， 根据挖掘对象的不同可分为三个方面的挖掘研究：w e b 内容挖掘( w e bc o n t e n tm i n i n g ) 、 7 人连交通人z r ：学硕 ，何沦文 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 所示： 表2 1w e b 挖掘的分类与区别 t a b l e2 1s o r ta n dd i f f e r e n t i a t i o no fw e bm i n i n g w e b 内容挖掘w e b 结构挖掘w e b 使用记录挖掘 处理l r 方法 数据库方法w e b 结构挖掘 数据无结构化数据、半半结构化数据 类型 结构化数据 主要自由化文本、i - l ：1 m lh t m 嘛记的超w e b 文档内及文件s e r v e rl o g 、c l i e n t 数据标记的超文本文本 间的超链接 l o g 表示词集、段落、概念、o e m 关系图关系图、表 方法 i r 的三种经典模型 处理t f i d f 、统计、机器数据库技术机器学习、专有算法统计、机器学习、 方法 学习、自然语言学 如h i t s 和p a g e r a n k 关联规则 习算法 主要 分类、聚类、模式模式发现、数据库 页面权重、分类、模用户p r o f i l e 、自适 应用发现向导、多层数据库式发现 应w e b 站点、商业 决策 2 2 1w 曲内容挖掘 w e b 内容挖掘是指对站点的页面内容( 包括文本、超文本、图像、视频、元数据等 多媒体信息) 中自动发现和获取知识【1 8 1 ，特点是所要挖取的数据是无结构或半结构化的。 w e b 内容挖掘可用于协助用户搜集信息或根据用户的目标过滤无用的信息。用户在网上 能看到的主要是文本和图像信息，随着i n t e r n e t 的进一步延伸，w e b 数据越来越庞大， 种类越来越繁多。除了数字图书馆及政府部门提供的相关数据信息，也有各商用公司自 己组建的数据仓库，其中既有文本数据信息，也有图像、声频、音频等多媒体数据信息， 既有来自于数据库的结构化数据，也有用h t m l 标记的半结构化数据及无结构的自由 文本数据信息。 从w e b 内容挖掘的页面内容方面出发，w e b 内容挖掘可分为两类：1 w e b 文本挖 掘，w e b 文本挖掘可以对w e b 上大量文档的内容进行总结、分类、聚类、关联分析， 以及利用w e b 文档进行趋势预测。2 w e b 多媒体挖掘，w e b 多媒体挖掘与w e b 文本 挖掘的不同点就在于需要提取的特征不同。w e b 多媒体挖掘需要提取的特征一般包括图 8 第：章w e b 挖掘羊l j 搜索引擎 像或视频的文件名、u r l 、类型、键值表、颜色向量等。然后可以对这些特征进行挖掘 操作当然也可以对多媒体文件进行分类、聚类等操作。 从w e b 内容挖掘的潜在内容出发，w e b 内容挖掘可分为两类：1 一类是面向资源 查找( i r ) 的w e b 内容挖掘，目的是从用户的角度出发，改善信息检索质量或者信息 过滤的性能；2 一类是面向数据建模的w e b 内容挖掘，通过挖掘数据模式，实现数据 集成和像关系数据库那样对w e b 数据执行一些复杂的查询。常见的方法是将文档内容 抽取到某个数据模型中。 w e b 内容挖掘的方法主要有基于智能的智能检索代理( a g e n t ) 的方法和基于在线 分析挖掘的数据库方法。 1 基于智能的智能检索代理 基于智能a g e n t 的w e b 挖掘涉及到智能a g e n t 技术。一般来说，基于a g e n t 的w e b 挖掘有三大类：智能搜索a g e n t ；信息滤波和分类a g e n t ；个性化w e b 服务a g e n t 。目前已 经出现的几种智能a g e n t ，利用领域的特征信息和个性化模式，组织、解释己经发现的 信息。例如，h a r v e s t 、f a o f i n d e r 、信息m a n i f o l d 和p a r a s i t e 系统利用对于特定文档的 预定义的和领域的特征信息，或者利用信息源的编码信息，检索并解释文档。信息滤波 和分类a g e n t 利用各种信息检索技术和超文本标记的特点，实现信息检索、过滤和分类。 例如，h y p u r s u t i 利用体现超链接结构和文档内容的语义信息，对超文本进行层次聚类， 并且结构化信息空间，y s m a a r e k 将层次聚类技术和用户交互信息结合起来，对w e b 文档集合进行概念重组。个性化w e b 服务智能a g e n t 通过获取或学习用户的爱好或兴 趣，发现匹配用户兴趣的w e b 信息源，甚至可以发现其它具有相似兴趣的用户。目前 已经知道的例子有w e bw a t c h e r ，p a i n t 等。 2 基于在线分析挖掘的数据库方法 对于w e b 挖掘来说，数据库方法主要用于集成和组织异质、半结构化的w e b 数据， 使之成为结构化的多层数据集，如关系数据库。然后，利用标准数据库查询机制和数据 挖掘技术访问和分析这些数据。 多层数据库组织w e b 信息的基本信息思想是，在多层数据库的最底层包含存储在 不同w e b 容器中的原始的半结构化w e b 信息，如超文本文档；在多层数据库的高层保 存的是元数据( m e t a d a t a ) 或泛化的数据，这些从低层提取的数据被结构化为关系型或面 向对象的数据库，例如，h a r t 等利用多层泛化和变换技术构成多层数据库，k h o l a s 等则 提出了包含领域知识的元信息数据库概念，并且建立了相应检索元信息数据库的索引模 式。 9 人造交通人学l ：学硕十学位论文 近来发展了许多w e b 数据库检索系统，利用标准数据库查询语占，如s q l ，查询 有关w e b 文档的结构化信息，甚至采用自然语言组合查询类型实现w w w 的搜索查询。 例如，根搠超文本的组织结构、内容，利用信息检索技术，再结合结构化查询实现w e b 查询。利用基于逻辑查询语言实现w e b 信息源提取与重构；利用标识图数掘模型实现 w w w 上的异质、半结构化信息的搜索。 w e b 内容挖掘常用的领域有分类、聚类、关联分析、w e b 主题发现与跟踪、预测分 析、提取规则发现、w e b 内容变化规律检测、用户模型、频繁子结构发现、站点数据模 式挖掘、数据集成等。当前基于w e b 内容挖掘的研究主要集中在如下图2 1 所示的四 个方面【1 6 1 ： 图2 1w e b 内容挖掘的研究 f i g 2 1t h er e s e a r c ho fw e b c o n t e n tm i n i n g 2 2 2w e b 结构挖掘 w e b 结构挖掘就是指通过分析不同网页之间的超链接结构，网页内部的可以用 h t m l 、x m l 表示成的树形结构，以及文档u r l 中的目录路径结构等，发现许多蕴涵 在w e b 内容之外的对我们有潜在价值的模式和知识的过程。这种思想源于引文分析， 即通过分析一个网页链接和被链接数量以及对象来建立w e b 自身的链接结构模式。该 模式可用于网页分类，并由此获得有关不同网页问相似度及关联度的信息，并有助于用 户找到指向相关主题的权威站点。 1 0 第一：幸w e b 挖掘f i i 搜索引擎 由于w e b 网页具有比纯文本更为丰富的结构，不仅具有文本信息，而且具有表示 网页之间关系的链接。所以在w e b 结构挖掘中主要目标是利用w e b 文档之间的超链接 结构进行分析，揭示出蕴含于文档结构中的个性化信息，其处理的数据类型为w e b 的 结构化数据，其主要的研究起源于社会网络和引述分析【1 9 珈j 。w e b 页面包含了从一个页 面指向另一个页面的超链接，而超链接信息包含了人类潜在的注释。大量的w e b 超链 接信息提供了关于w e b 页面内容相关性、质量和结构方面的信息，反映了文档之间的 包含、引用或者从属关系。引用文档对被引用文档的说明往往更客观、更概括、更准确。 它有助于自动推断出页面的权威性。所谓权威页面是在一个主题内被高度引用或参考的 网页。与其相关的另一个概念是枢纽页面，即那些指向许多权威页的页面。权威页面和 枢纽页面展示了强烈的依赖关系；一个好的枢纽页指向了许多好的权威页；一个好的权 威页被许多好的枢纽页所指。在信息检索中可以将高权威分和枢纽分的网页视为高质量 的网页，优先提供给用户。这样就可以通过分析超链接拓扑结构发现w w w 上超链接 社区。对于检索结果或指定的网页集合，可以构建一个有向图；每个结点表示一个网页， 超链表示结点间的有向边。网页权威分和枢纽分的计算算法见文献【2 1 。2 2 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 结构挖掘对于结构化数据的挖掘包括超链接挖掘、内容结构挖掘和u r l 挖掘 p j 。目前这方面工作比较有代表性的方法是g o o g l e 公司的p a g e r a n k 2 4 j 。 从页面的重要性来说：一个页面被其他的页面所引用的次数越多，一般来说它的重 要性越高。如果一个页面本身没有被多次引用，但是它却被一个重要页面所引用，那么 这个页面也会具有较高的重要性，这种思想是p a g e r a n k 方法的主要思想。利用p a g e r a n k 方法，搜索引擎可以先对检索提问进行检索，然后再对检索结果进行页面等级分析，从 人j 生交通人学l ：学硕十学何论文 而根据页面的重要性进行输出。g o o g l e 可以获得高精度的检索结果也得益于应用这一关 键技术。它为数十亿w e b 页面构造了引用图，通过该图可以快速计算出每一个页