（计算机软件与理论专业论文）基于机器学习的主题web挖掘技术.pdf

山东师范大学硕士学位论文 基于机器学习的主题w e b 挖掘技术 摘要 随着网络信息资源的急剧增长，人们越来越多地关注如何快速有效地从海量 的网络信息中，获取潜在的、有价值的信息，使之有效地在管理和决策中发挥作 用。但当用户面对这个海量、异构、半结构化的信息库时，常常发现要查找到所 、 需的信息要耗费大量的时间和精力，甚至难以找到，造成了“信息过载、知识匮 乏”的现象。主题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 结构挖掘、w e b 使用记录挖掘文中介绍 了主题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 爬虫能够根据用户或信息检索定义的目 标主题，以智能的方式在线爬行w e b ，在有限的时间和空间资源条件下，收集到 尽可能多的主题相关w e b 页面。如何有效地控制主题爬虫爬行策略是影响w e b 挖 掘成功的最重要因素之一本文结合机器学习理论，引入反例样本学习理念，提 出一种新的主题爬虫爬行策略。实验证明该策略能有效的提高查询的收获率。 3 w e b 页面重要性的计算是进行w e b 挖掘的一个重要问题本文在原有h i t s 算 山东师范大学硕士学位论文 法的基础上，加入了内容相关度的计算，提出了一种新的计算页面重要性的算法 一嚣h i t s 算法。 4 本文设计了基于机器学习的主题w e b 挖掘系统，并对各个模块的作用进行了 介绍。该系统能够根据用户的查询请求进行页面收集，对收集到的页面计算其重 要性，最后把主题相关且重要的页面反馈给用户。同时，可根据用户的反馈信息， 进行进一步的系统调整。 关键字：w e b 挖掘；机器学习；主题爬虫；h i t s 分类号：t p 3 9 1 山东师范大学硕士学位论文 t h et e c h n o l o g yo ft o p i c a lw e bm i n i n gb a s e do nm a c h i n el e a r n i n g w i t ht h ew e bi n f o r m a t i o nr e s o u r c e se m e r g ea b r u p t l y ，h o wt og e tt h o s e p o t e n t i a la n dv a l u a b l ei n f o r m a t i o nf r o mn e t w o r kh a sa t t r a c t e dp e o p l e s m o r ea n dm o r ea t t e n t i o n c o n f r o n t e dw i t ht h i sh u g e ， h e t e r o g e n e o u sa n d s e m i s t r u c t u r a li n f o r m a t i o nr e p o s i t o r y ，w e bs u r f e r so f t e nh a v et os p e n d al o to ft i m ea n de f f o r t st of i n di n f o r m a t i o nn e e d e d ，a n de v e nt h a tt h e y m a yf a i l i nm a n yc a s e s ；t o p i c a lw e bm i n i n gi san e wr e s e a r c hd i r e c t i o n i nr e c e n ty e a r s ，w h i c hp r o v i d e san e wr e s e a r c hd i r e c t i o n t h em a i nc o n t r i b u t i o n so ft h et h e s i sc a nb es u m n r i z e da sf o l l o w s ： 1 t h i sa r t i c l es t u d i e sa n da n a l y s e sw e bm i n i n ga n dm a c h i n el e a r n i n g w e b m i n i n gi sd i v i d e di n t ot h r e eb r a n c h e sb yd i f f e r e n to b j e c t s ：w e bc o n t e n t m i n i n g 、w e bs t r u c t u r em i n i n g 、w e bu s a g em i n i n g a c c o r d i n gt ot h e d i s t r i b u t i o n o ft h et o p i cw e bp a g e so nt h ew e b ，t o p i c a lw e bm i n i n gc o l l e c t s w e bp a g e sw h i c ha r er e l a t e dt ot h et o p i ct h e m ea n da n a l y s e s ，h a n d l e st h e m b yi n t e l l e c t u a lw a y s m a c h i n el e a r n i n gi sa ni m p o r t a n tb r a n c ho ft h ef i e l d o fa r t i f i c i a li n t e l l i g e n c e t h i sp a p e rp r e s e n t st h em o d e lo fm a c h i n e l e a r n i n g , c l a s s i f i c a t i o n ，a n dt h ed e v e l o p m e n tp r o c e s s 。m e a n w h i l e ，c h i n e l e a r n i n gi nt h ef i e l do fw e bm i n i n ga p p l i c a t i o ni sd e s c r i b e d 2 w e bc r a w l e ri sak i n do fr e c u r s i v et r a v e r s a lw e ba u t o m a t i o np r o g r a m w h i c hc a nd o w n l o a dw e bp a g e sa n da n a l y s i st h e s ec o n t e n t h o wt oc o n t r o l t h ec r a w l e r sc r a w l i n gs t r a t e g ye f f e c t i v e l yi so n eo ft h em o s ti m p o r t a n t f a c t o r sw h i c hi n f l u e n c ew e bm i n i n g i nt h el i g h to fm a c h i n el e a r n i n g ，a n d u s i n gt h en e g a t i v ee x a m p l es t u d yt h e o r y ，w ea d v a n c ean e wc r a w l e r s c r a w l i n gs t r a t e g y t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h i ss t r a t e g yc a n i n c r e a s et h eh a r v e s tr a t eo fi n q u i r i e s 3 t h ec a l c u l a t i o no fw e bp a g e sa u t h o r i t yr a d i oi sa ni m p o r t a n ti s s u e f o rw e bm i n i n g b a s e do nt h eh i t sa l g o r i t h m , w ea d v a n c ean e wa l g o r i t h m 山东师范大学硕士学位论文 f o rc a l c u l a t i n gt h ei m p o r t a n c e t h ew h i t sa l g o r i t h 4 w eh a v ed e s i g n e da n di m p l e m e n t e dat o p i c a lw e bm i n i n gs y s t e mb a s e do n m a c h i n el e a r n i n g t h i ss y s t e mc a nc o l l e c tp a g e sb a s e do nu s e r sr e q u e s t s ， a n dc a l c u l a t ei m p o r t a n c eo ft h o s ew e bp a g e s 。a n df e e d b a c kt h o s et h e m e p a g e st ot h eu s e rf i n a l l y m e a n w h i l e ，w ec a na d j u s ts y s t e ma c c o r d i n gt o t h eu s e r sf e e d b a c ki n f o r m a t i o n k e y l r o r d s ：w e bm i n i n g ；m a c h i n el e a r n i n g ：t o p i c a lc r a w l e r ；h i t s c i a s s i f i c a f i o n ：t p 3 9 1 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得 ( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我_ 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 靴黻储戳。细 新擗狮彳 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权勉l 可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名： 签字日期：彩叼年争月z 7 日 氯膨 签字日期：弘刁年争月刁日 山东师范大学硕士学位论文 1 1 研究背景 第一章绪论 随着因特网( i n t e r n e t ) 的迅速发展，网络对我们的影响已经越来越大，日渐成为人们获 得信息的必要途径和重要手段而在网上发展最为迅猛的w w w ( w o r l dw i d ew e b ) 技术，以 其直观、方便的使用方式和丰富的表达能力，己经发展成为一个全球化信息发展空间。随 着信息时代的到来和发展，w e b 上的信息如雨后春笋般迅速增长起来。2 0 0 7 年1 月2 3 日， 中国互联网络信息中心( c n n i c ) 在北京发布第十九次中国互联网络发展状况统计报告。 报告显示，截止到2 0 0 6 年1 2 月3 1 日，我国网民人数达到了1 3 7 0 0 万人，与去年同期相比 增长了2 3 4 ，其中宽带上网网民人数己突破一亿目前，我国网民数和宽带上网人数均位 居世界第二” 然而面对这个分散无序的海量信息库，w e b 用户经常发现难以找到能满足他们需要的信 息，造成“信息过载，知识匮乏”的现状一方面网上的信息多种多样、丰富多彩，而另 一方面用户却找不到他们所需要信息这一矛盾的主要原因是人们在如此大的信息库里， 很难用浏览的方式找到自己所需的信息。这一现象促使一种以w e b 搜索引擎为主的，用于 提取网络有效资源的信息检索技术应运而生了。g o o g l e ，i n f o s e e k ，b a i d u ，a l t a v i s t a 、 天网等国内外知名的搜索引擎正是人们为了解决网上信息检索的难题，而在信息检索领域 进行大量研究后的成果 现在，通用搜索引擎嘲已成了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 w w 资源上存在的有趣的、潜在的、有用的模式及隐藏的信息，并 利用这些信息加快用户检索的效率，从而使w w 资源更好的人们服务。同时，随着主题爬 虫技术的提出，主题w e b 挖掘技术越来越受到人们的重视。许多项目的研究结果表明，使 用主题w e b 挖掘方法能够保持更高的主题相关度，提高查询的精度，同时也展示了许多急 需解决的具有挑战性的问题。其中如何有效地控制爬虫爬行策略是影响w e b 挖掘是否成功 的最重要因素之一。 山东师范大学硕士学位论文 1 2w e b 挖掘与相关研究内容 w e b 挖掘1 就是从w e b 页面和w e b 用户访问活动中发现、抽取感兴趣的潜在的有用模式 和隐藏的信息。它是以从w e b 上挖掘有用知识为目标，以数据挖掘、文本挖掘、多媒体挖 掘为基础，并综合运用计算机网络、数据库与数据仓储、人工智能、信息检索、可视化、 自然语言理解等技术，将传统的数据挖掘技术与w e b 结合起来的一门新兴学科。下面介绍 一下w e b 挖掘相关领域的研究，以及它们与w e b 挖掘的联系。 i 2 iw e b 挖掘与数据挖掘 数据挖掘嗍是从数据库的大量数据中揭示出隐含的、先进而未知的、潜在有用信息的频 繁过程。从广义观点来说，数据挖掘就是从存放在数据库、数据仓库或其他信息库中的大 量数据中挖掘有趣知识的过程。许多人把数据挖掘视为数据库中的知识发现或k d d 的同义 词。而另一部分人只是把数据挖掘视为数据库中知识发现过程中的一个基本步骤。 传统的数据挖掘是以数据仓库为基础，对结构化的数据源进行信息的加工、分析和模式 挖掘。数据挖掘的对象是包含大量数据信息的各种类型数据库，如关系数据库，面向对象 数据库等。数据挖掘的过程可由三个主要阶段组成：数据准备、数据挖掘、结果表达和解 释数据挖掘是这三个阶段的反复执行的过程。 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 文档进行预处理的基础之上。 i 2 2w e b 挖掘与信息检索 信息检索是自动获取相关文档的同时尽可能少的获取不相关文档。信息检索最主要的 目标是索引文本，寻找有用的文档。现在信息检索的研究领域包括建模、文本分类、用户 接口、数据可视化和信息过滤等等。有人把信息检索称为w e b 内容挖掘的实例：有人把智能 信息检索称为w e b 挖掘，可见两者之间有密切的联系。但w e b 挖掘和信息检索是两种不同的 技术，其区别主要表现在以下几个方面。 第一，方法论不同。信息检索是目标驱动的，用户需要明确提出查询要求；而w e b 挖掘 2 山东师范大学硕士学位论文 是机会主义的，其结果独立于用户的信息需求，也是用户所无法预知的 第二，着眼点不同信息检索着重于文档中显示存储的字词和链接；而w e b 挖掘试图更 多的理解其内容和结构。 第三，目的不同信息检索的目的在于帮助用户发现资源，即从大量的文档中找到满足 其查询请求的文档子集；而w e b 挖掘是为了揭示文档中隐含的知识 第四，评价方法不同。信息检索使用精度( p r e b i s i o n ) 和查全率( r e c a l l ) 来评价其性能， 要求返回尽可能多的相关文档，同时不相关的文档尽可能的少；而w e b 挖掘采用受益度 ( g a i n ) 、置信度( c e r t a i n t y ) 、简洁性( s i m p l i c i t y ) 等来衡量所发现知识的有效性、可用性 和可理解性。 第五，使用场合不同。有时信息检索系统返回太多的结果以致用户无法一一浏览，有时 用户没有明确的信息需求，有时用户希望发现文档集合中所具有的结构、趋势、含义等， 在这些场合下，就需要使用w e b 挖掘技术。 1 2 3w e b 挖掘与信息提取 信息提取”1 ( i n f o r m a t i o ne x t r a c t i o n ) 的目标是将一个文本集转化为更易于消化和分析 的信息。信息提取主要有两种类型：非结构化文本的信息提取和结构化文本的信息提取 对非结构化的自然语言文本进行信息提取，典型的就是在执行数据挖掘之前用更基本的方 法进行数据预处理传统的信息提取依赖于语言预处理，例如依照句法分析、语义分析和 会话分析。结构化信息提取常常利用半结构化数据之中的信息，例如h t m l 中的标志位、 简单的造句法、定界符和分隔符等。 手动的构建一个信息提取系统是不可能的，例如对象是像w e b 内容这样的动态、多变 的媒体。一些信息提取系统致力于从特殊的w e b 站点提取信息，还有的是应用机器学习或 数据挖掘技术来半自动或全自动的从w e b 文档中提取模式或规则。从这点来看，w e b 挖掘 是信息提取处理过程中的一部分。还有人认为，信息提取可以看作w e b 挖掘过程的预处理 阶段；相反的，由于经过摘要表达和格式压缩的文档是一个以前并不存在的新文档，因而 可以说信息提取是w e b 挖掘的一个实例 1 3 本文研究内容及结构 本文在研究w e b 挖掘理论的基础之上，分析主题爬虫的工作原理及现存问题，深入讨论 如何改进爬虫爬行策略，以及如何应用到w e b 挖掘系统中，以提高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 挖掘的理论及当前的研究现状，结合主题w e b 页面在网络中的分布特征，阐明了 进行主题w e b 挖掘的依据及存在的困难。 第三章，本章主要研究和探讨了机器学习技术，对机器学习的模型、分类，及发展历程 作了介绍。同时，对机器学习在w e b 挖掘领域的应用前景作了描述。强化学习和贝叶斯学 习是机器学习中的两种重要方法，文中对这两种方法作了简要说明。同时，对第四章用到 的q 学习和贝叶斯分类器作了重点介绍。 第四章，w e b 爬虫是进行w e b 网页收集的工具。本章研究和探讨了主题爬虫的结构及与 普通爬虫的异同。同时对主题爬虫的爬行策略进行改进，结合q 学习方法和贝叶斯分类器 技术，引入反例样本学习理念，提出一种新的主题爬虫爬行策略。实验证明，该爬行策略 具有较好的收获率。 第五章，本章在简要描述h i t s 算法的基础上，指出h i t s 算法易出现主题漂移的现象 我们结合h i t s 算法和内容相关度评价方法，提出一种新超链接评价方法w h i t s ，用于计算 w e b 页面的a u t h o r i t y 值和h u b 值。 第六章，描述了基于机器学习的w e b 资源挖掘系统的概念设计，对各个模块的作用进行 了简要介绍。 第七章，本章主要对本文所做工作进行了总结，并提出了进一步的工作展望。 4 山东师范大学硕士学位论文 第二章w e b 挖掘理论简介 万维网作为一个巨大的、分布广泛的全球性信息服务中心，服务内容不仅涉及新闻、消 费信息、金融管理、教育、政府、电子商务等许多其它服务信息，而且还包括丰富的超链 接信息，和访问信息。一人们将数据挖掘技术应用到半结构化的w e b 数据上，使其能够针对 w e b 数据的特点进行知识发现，这为数据挖掘开辟一个新的研究领域，即w e b 挖掘。 2 1w e b 挖掘的定义 w 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 孵相关的资源和行为中 抽取感兴趣的、有用的模式和隐含信息。 。 典型w e b 挖掘隅“1 的处理流程包括如下四个步骤：资源发现、信息选择和预处理、模式 发现、模式分析。 ( 1 ) 资源发现 系统使用网络爬虫在线收集w e b 文档，并从中得到相应数据。值得注意的是信息资源 不仅限于在线w e b 文档，还包括电子邮件、电子文档、新闻组、网站的日志数据，甚至是 通过w e b 形成的交易数据库中的数据。 ( 2 ) 信息选择和预处理 系统从取得的w e b 资源中剔除无用信息，并将信息进行必要的整理例如w e b 文档中 自动去除广告连接、去除多余格式标记、自动识别段落或者字段、将数据组织成规整的逻 辑形式、英文单词的词干提取、高额低频词的过滤等。 ( 3 ) 模式发现 系统自动地进行模式发现，可以在同一个站点内部或多个站点之间进行，以自动发现 w e b 站点的共有模式。 ( 4 ) 模式分析 系统验证并解释上一步骤产生的模式，对其进行可视化表示。可以是机器自动完成，也 可以是与分析人员进行交互完成。 5 山东师范大学硕士学位论文 2 2w e b 挖掘的分类 w e b 挖掘是从w w w 资源上挖掘有趣的、潜在的、有用的模式及隐藏信息的过程，它是将 数据挖掘技术应用于w 孵资源进行挖掘的一个新兴的研究领域。w e b 挖掘的分类方法有很 多，如按w e b 文本的语言分，按挖掘站点的属性( 如企业门户、政府、个人站点) 分等。 目前多数人倾向于根据挖掘对象的不同，把w e b 挖掘大致分为三类：w e b 内容挖掘( w e b c o n t e n tm i n i 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 e m i n i n g ) 下图为w e b 挖掘的分类图： 2 2 1w e b 内容挖掘 图2 - if e b 挖掘分类图 w e b 内容挖掘是指从w e b 上的网页内容及其描述信息中获取潜在的、有价值的知识模式， 以实现w e b 资源的自动检索，提高w e b 数据利用率的过程。w e b 内容挖掘根据不同的标准， 有多种不同的分类方法。 w e b 内容挖掘根据挖掘对象的不同可分对文本文档( t e x t 、h t m l 、x 札等) 的挖掘和多媒 体文档( i m a g e 、a u d i o 、v i d e o 等) 的挖掘。w e b 文本挖掘是一个新的跨学科的研究领域，它 包括机器学习、数据挖掘、统计学、信息获取、自然语言理解等w e b 文本挖掘可以对w e b 上大量文档集合的内容进行关联分析、总结、分类、聚类，以及利用w e b 文档进行趋势预测， 还可以对搜索结果进行进一步的挖掘。w e b 多媒体挖掘是指从w e b 多媒体数据中抽取事先 未知的、隐藏的、完整的和新颖的知识。 w e b 内容挖掘按挖掘方法来划分可分为信息查询观点( i rv i e w ) 和数据库观点( d b v i e w ) 信息查询观点认为，w e b 站点是由一些超文本文档的集合构成，w e b 内容挖掘的主要 目的是检查并发现文档的语义模式，包括文本、链接结构、相关领域知识元数据以及用户的 使用偏爱等。数据库观点则认为，w e b 站点是由一些半结构化的文档组成，从不同种类的数 据中发现和抽取共同的模式来获取相关的语义信息，来满足用户的信息需求是w e b 内容挖掘 的主要目的。 6 山东师范大学硕士学位论文 2 2 2w 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 算法“。圳和h i t s 算法“”。它们的 共同点是使用一定方法计算w e b 页面之间的超链接质量，从而得到页面的权重。 ( 1 ) p a g e r a n k 算法 人们搜索某一主题的w e b 页面时，除了要求内容相关，更加期望检索到的页面有较高 的质量和权威性。p a g e r a n k 是由l p a g e 等提出的，用于发现“权威页面”的方法。它的 基本思想是：一个页面放多次引用，则该页面很可能是重要的；一个页面尽管没有被多次引 用，但被一个重要页面引用，则这个页面也被认为是重要的一个页面中指向其它页面的超 链接越多，在一定程度上说明该网页中的信息内容越具有说服力：指向该页面的超链接越多， 则说明该页面的信息内容有一定的权威性 ( 2 ) h i t s 算法 h i t s 也称为h u b a u t h o r i t y 方法，是由k l e i n b e r g 提出的另一种挖掘“权威页面”的 方法。h u b 页是指带有多个指向权威页面的链接的页面。h u b 页面本身可能并不突出，或者 说可能没有几个链接指向它们，但是h u b 页面却提供了指向一个或多个权威页面的链接。利 用h u b 页面来发现权威页面的算法有h i t s 算法及其改进算法。 w e b 结构挖掘中存在很大的局限性。首先，不是每个超链接都代表准确的链接，有些是 为了其它目的而创建的，如为了导航或付费广告等：第二，存在着w e b 页面之间频繁相互引 用的情况：第三，基于商业或竞争的考虑，很少有w e b 页面指向其竞争领域的权威页面：第 四，权威页面很少具有特别的描述。 2 2 3w e b 使用记录挖掘 虽然唧w 是一个复杂的、异质的、动态的信息源，但从局部来看，在每一个提供信息 资源的w e b 服务器上都有一个结构化较好的记录集，即w e b 访问日志( w e ba c c e s sl o g ) 每当有获取资源的请求到来时，w e b 服务器都将记录和积累这些关于用户访问和交互的信 息。 w e b 使用记录挖掘又称为w e b 日志挖掘( w e bl o gm i n i n g ) ，主要目标是从w e b 的访问 记录中发现感兴趣的模式。通过分析不同w e b 站点的访问日志来帮助人们理解w e b 结构和 用户的行为，从而改进站点的结构，或为用户提供个性化的服务。 目前w e b 使用记录挖掘方面的研究主要有两个方面：一般的访问模式追踪和个性化的 7 山东师范大学硕士学位论文 使用记录追踪。一般的访问模式追踪通过分析使用记录来了解用户的访问模式和倾向，以 改进站点的组织结构而个性化的使用记录追踪则倾向于分析单个用户的偏好，其目的是 根据不同用户的访问模式，为每个用户提供定制的站点。 w e b 使用挖掘的基本流程包括四个阶段：数据预处理、挖掘算法实施、模式分析、可视 化。预处理完成将原始的日志文件过滤、筛选及重组后，将之转变为适合挖掘的数据格式， 通常以用户会话文件的形式保存到数据库中，供后续挖握过程使用。挖掘算法实施是挖掘 的核心，根据挖掘任务的不同，采用不同的挖掘算法，从数据预处理阶段产生的用户会话 中寻找用户的浏览模式。模式分析利用领域专家的知识以及其它一些可用的标准来分析这 些模式，并过滤掉那些没有利用价值以及有偏差的模式。可视化阶段将发现的有价值的用 户测览模式以表格、饼图、曲线图、趋势图、直方图或者其它特殊表现形式显示出来 w e b 内容挖掘和w e b 结构挖掘的对象是网上的原始数据，而w e b 使用记录挖掘的对象 多是用户和网络交互过程中抽取的第二手资料本文主要针对w e b 网络中的原始资料进行 分析。重点在对w e b 内容和结构进行挖掘研究 2 3 国内外研究动态 w e b 挖掘是把w w w 和数据挖掘结合起来的一种新兴技术。它的应用前景非常广阔目前 国际上对此领域的研究主要集中在：搜索引擎的设计、文件自动化分类技术，关键词的自 动提取、半结构化信息的提取等。在国内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 ) 在数据预处理方面，多种w e b 数据的收集、结 构转换等处理技术方面的研究；( 2 ) w e b 挖掘以及模式识别技术在构造自适应站点以及智 能站点服务的个性化和性能优化方面的研究：( 3 ) w e b 知识库的动态维护、更新，各种知识 和模式的融合、提升以及知识的评价综合方法； ( 4 ) 基于w e b 挖掘和信息检索的、高效 的、具有自动导航功能的智能搜索引擎相关技术的研究；( 5 ) 研究和开发基于w e b 的多层 数据体系结构和智能集成系统，提供相应的查询语言，优化和维护机制；( 6 ) 现有的数据挖 掘方法与技术的改进及其向w e b 数据的扩展，挖掘算法的适应性和时效性的研究； 7 ) w e b 文档内的模式发现及其在信息提取、文本分析中的应用研究；( 8 ) w e b 挖掘的相关技术在 8 山东师范大学硕士学位论文 电子商务领域的应用研究等。 2 4 主题w e b 挖掘理论 随着网络的发展，w e b 上的信息越来越丰富，人们倾向于从网络当中获取知识和信息。 而这时，搜索引擎就成了w e b 用户访问w e b 的必备工具之一它的基本原理是：w e b 爬虫采 用特定的爬行策略，周期性的收集尽可能多的w e b 网页，然后提交给自动索引系统；索引系 统根据定义的索引要求建立基于相应检索元的索引库；用户通过系统提供的查询接口访问 搜索引擎；查询系统根据用户提交的查询条件搜索索引库，获得检索结果，并且采用一定 的评价算法计算用户查询条件和检索结果之间的相关性，检索结果根据相关度进行排序后 按相关度优先的顺序返回给用户。 在各种搜索引擎中，最常用的是各个通用搜索引擎，如g o o g l e 、a l t a v i s t a 、y a h o o 等 通用搜索引擎将用户提交的查询词作为查询条件，从而获取与用户需求相关的网页，为用 户提供方便的检索功能但由于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 ) e l s e v i e r 的s c i r u s 系统” s c i r u s 科学搜索引擎是一种专为搜索高度相关的科学信息而设计的搜索引擎，获得 2 0 0 1 搜索引擎观察授予的“最佳专业搜索引擎”奖。s c i r u s 是目前互联网上最全面、 综合性最强的科技文献门户网站之一它只面向包含有科学内容的网站，如大学和作者个 人主页以及e l s e v i e r 自己的数据库 ( 2 ) b e r k e l e y 的f o c u s ep r o j e c t 伽 这个系统由一个印度裔的科学家s c h a r k r a b a r t i 带头从事，他是最早从事这方面研究 的人之一该系统通过两个程序来指导爬行器：一个是分类器c l a s s i f i e r ，用来计算下载文 档与预订主题的相关度。另一个程序是净化器d i s t i l l e r ，用来确定那些指向很多相关资源 的页面。 ( 3 ) n e c 研究院的c i t e s e e r c i t e s e e r 是一个非常有名的针对计算机科学领域论文的检索系统。c i t e s e e r 的核心是 9 山东师范大学硕士学位论文 a c i ( a u t o m a t i c a l l yc i t a t i o ni n d e x ) 1 9 p 它可以自动地对网上的电子文件( p o s t s c r i p t 和 p d f 等格式) 进行索引并分类。 ( 4 ) 美国国家科学数字图书馆的c o l l e c t i o nb u i l d i n gp r o g r a m ( c b p ) 这个项目旨在为科学、数学、工程和技术创建大规模的在线数字图书馆，试图研究在 某一主题上资源自动建设的可能性。c b p 具有自己的特点：第一，因为c b p 是面向教育、面 向教学。主题精确度比覆盖度更为重要：第二，e b p 不存储资源原文，而只是提供u r l 。第 三，c b p 只需要用户最少量的输入，如关键词，系统就可以全自动的将有关该主题的最相关 的有限数量u r l 返回给用户。 2 5 主题页面在w e b 上的分布特征 从表面看来，万维网是一个海量的信息库，其中的w e b 页面分布的杂乱无章，难以发现 整体的分布规律。但对于同一主题的w e b 页面而言，他们的分布却有一定的规律可循经 研究发现，我们将这些分布规律总结为以下四个特性：h u b 特性、主题关联特性、站点主 题特性、t u n n e l 特性。这些特性是进行主题w e b 挖掘的基础，为主题w e b 挖掘的研究提供 了依据。 ( 1 ) h u b 特性 美国康奈尔大学的教授j o nl lk l e i n b e r g 发现w e b 上存在一些这样的w e b 页面，它们 的页面含有许多o u t l i n k 链接( 指出链接) ，并且这些链接趋向于相关同一个主题j o nm k l e i n b e r g 把这种指向相关主题页面的一个中心页面称为h u b 页。同时，他还定义了权威页 面( a u t h o r i t y ) 的概念，即其它许多页面都认为相关于这一主题有价值的好页面。好的h u b 页面一般指向多个a u t h o r i t y 的页面，并且所指向的a u t h o r i t y 页面越权威h u b 页面的 质量也越好；反过来，h u b 页面的质量越好，它所指向的每个页面也越趋向于权威。根据 这个思想，他还提出了h u b a u t h o r i t y 算法，这个算法就是我们剐刚在w e b 结构挖掘中提 到的h i t s 算法。 ( 2 ) 主题关联特性 人们从页面设计者的角度出发。提出了主题关联特性( 即s i b l i n g l i n k a g el o c a l i t y 特 性) 。它是指页面所包含的链接趋向于指向和该页面同主题的页面：对于链接到某主题页面 的页面，它所包含的其它链接指向的页面也趋向于该主题。这实际上源于网页制作的习惯， 即页面设计者一般会把本页面指向于与本页面相关的其它页面 ( 3 ) 站点主题特性 在浏览网页中我们会发现，一个站点通常只在说明一个或几个主题，并且那些说明同一 个主题的页面紧密地在此站点内部链接成团，而各个主题团之间却链接较少研究人员认 为，这主要根源于网站设计者的设计思路。每个网站在设计之初都是有一定的目标，而这 种目标往往就集中在一个或几个主题中。用户在测览网页的时候往往也有一定的目的往， 这个目的性一般体现在浏览者趋向于测览同一主题的页面。因此，网站设计者习惯于将相 l o 山东师范大学硕士学位论文 关内容的网页紧密地链接在一起。 ( 4 ) t u n n e l 特性 w e b 中存在很多相关主题页面团，这些页面团之间要经过较多的无关链接才能够到达 这些无关链接就像一个长长的隧道，连接着两个页面团，我们把这种现象称为“隧道现象” ( t u n n e l ) 。在页面采集过程中，t u n n e l 现象的存在极大地影响着采集页面的质量、查全率、 和查准率。如果我们为了保证采集页面的查全率，则需要降低超链接与主题相关性判定以 及页面与主题相关性判定的阈值，阈值的降低使得采集系统可以得到t u n n e l ，但同时也容 易混进了大量的其它无关页面，从而大大降低了页面的查准率反之，如果我们为了提高 采集页面的查准率，则需要提高阈值以过滤掉大量无关链接，但同时也过滤掉大量的 t u n n e l ，使得采集系统很可能丢失t u n n e l 另一端的主题团，进而影响了查全率。这是一个 两难的问题，解决这一问题关键在于阈值的确定，尽可能地区别t u n n e l 和其它大量无关页 面，以使得能够有效的在查全率和查准率之间取得一个有效的折衷 w e b 中的页面是杂乱的，但也存在一些规律。h u b 特性说明了主题网页容易成团出现的