（计算机应用技术专业论文）基于语义相似度的web结构挖掘研究及实现.pdf

硕士论文基于语义相似度的w e b 结构挖掘算法研究及实现 摘要 目前，i n t e m e t 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 算法进行验证。 通过实验和分析，新的算法在不影响原算法的优点和效率的情况下能更好地对网页进行 评分，提升了用户满意度。它在网页优先级算法上向人工智能和语义w e b 又迈进了一 步。 关键词：语义相似度，知网，p a g e r a n k ，搜索引擎 a b s t r a c t硕士论文 a b s t r a c t a tp r e s e n t ，t h ei n t e m e t w e bt e c h n o l o g yt e n d st om a t u r a t eg r a d u a l l y a n dw e bh a s a l r e a d yb e c o m eo n eo ft h em o s ti m p o r t a n t i n f o r m a t i o nr e s o u r c e s h o w e v e r , g o i n g 、析t l l p r o v i d i n gp r o f u s em e s s a g e ，i t sc h a r a c t e r i s t i c sw h i c hi n c l u d et h es e m i - s t r u c t u r e dd a t a , t h e n o n s t r u c t u r i z a t i o n , t h ed a t am a g n a n i m o u s ，r e a l - t i m ed y n a m i c ，u s e rp o l y m o r p h i s ma n d s oo n , m a k et h eu s eo fw e br e s o u r c ed i f f i c u l tt oac e r t a i ne x t e n t a sar e s u l t ，w i t ht h ec o m b i n a t i o no f d a t am i n i n gt e c h n o l o g i e sa n dw e bp r o p e r t i e s ，i nt h ev a s ti n f o r m a t i o nr e s o u r c e s ，s e a r c h i n gf o r t h em e s s a g ei nn e e df a s ta n dp r e c i s e l yh a sb e c o m ea nu r g e n ta n dm e a n i n g f u lr e s e a r c h i nt h i sp a p e r , i ti n t r o d u c e st h ec o n t e m p o r a r yc l a s s i c a la l g o r i t h mo fp a g e r a n kw h i c h r e f l e c t st h er e l a t i o n s h i po ft h el i n ks t r u c t u r e so fw e bp a g e s ，a n a l y z i n gi t sb a s i ci d e a t h o r o u g ) f l ya n dp o i n t i n go u ti t sd e f i c i e n c yw h e nw e bp a g eb e i n gv a l u e d t h em a i nf l a wo f p a g e r a n ka l g o r i t h mi sd i s t r i b u t i n gt h ep a g e r a n kv a l u ei na l lo u t - l i n k se q u a l l y i nf a c t , t h e i m p o r t a n c eo fe a c hl i n ka n dc o r r e l a t i o no ft h el i n k sa r ed i f f e r e n t i tc o m p l e t e l yn e g l e c t st h e s e m a n t i ci n f o r m a t i o no fw e bc o n t e n t ，w h i c hl e a d st or e c e i v et h ei n f l u e n c eo ft h ei r r e l e v a n t l i n ke a s i l y , a n dt h e nr e d u c eu s e rs a t i s f a c t i o no ft h es e a r c hr e s u l t s i nr e s p o n s et ot h e s ed e f i c i e n c i e s ，b yi n t r o d u c i n gt h es e m a n t i cs i m i l a r i t yb a s e do n i tm a k e sc o n n e c t i o nb e t w e e nt h eq u a l i t i e so fl i n ka n c h o rt e x ta n dt h ec o n t e n to ft h e p a g ew h i c hi tp o i n t st o w i t hi n t e g r a t i n gt h es i m i l a d t yi n f o r m a t i o nb e t w e e nt h eo u t l i n ka n d t h eg o a lp a g e ，i tw o u l dd i s t r i b u t ef e wp a g e r a n kv a l u et ot h o s ep a g e sw h i c hh a v en ov a l u e ，o r p a g e sb e i n gn o n c o r r e l a t e d a n de n h a n c et h ep a g e r a n kv a l u eo ft h ep a g e sw h i c ha r er e a l r e l e v a n tt ot h es u b j e c t t h u s ，i tw i l lr e f l e c tt h ec o m p e t i t i o nb e t w e e nt h ev a r i o u sl i n k sm o r e a c c u r a t e l y f i n a l l y , t h es i m u l a t o rm o d e l i n gt h es e a r c he n g i n ei sr e a l i z e d t h es i m u l a t i o ns y s t e m h a s n e a r l yc o n t a i n e dt h es e a r c he n g i n ef u n c t i o nc o m p l e t e l y , a n di th a s b e e nt e s t e du n d e rt h er e a l e n v i r o n m e n to ft h ei n t e m e t , i n c l u d i n gt h ev e r i f y i n go ft h ep a g e r a n ka l g o r i t h mw h i c h i n t e g r a t e sw i t ht h es e m a n t i cs i m i l a r i t y t h r o u g he x p e r i m e n t sa n da n a l y s i s ，t h en e wa l g o r i t h m w h i c hd o e sn o ta f f e c tt h em e r i t sa n de f f i c i e n c yo ft h eo r i g i n a la l g o r i t h mc a nv a l u et h ep a g e s c o r eb e t t e r , a n dt h e ni m p r o v ec u s t o m e rs a t i s f a c t i o n i tm a k e sg r e a ts t r i d e sf o r w a r dt ot h e a r t i f i c i a li n t e l l i g e n c ea n ds e m a n t i cw e bi nt h ep a g ep r i o r i t ya l g o r i t h m k e y w o r d s ：s e m a n t i cs i m i l a r i t y , ，p a g e r a n k ，s e a r c he n g i n e 声明尸明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：纽 砂汐7 年臼扫 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：二互数量 研究生签名：厶数生 砂呷年f 月2 归 硕士论文基于语义相似度的w e b 结构挖掘算法研究及实现 1 绪论 伴随着网络通信、信息资源发布及共享等技术的快速普及和迅猛发展，人们需要的 各种信息几乎都可以在网络上获得。如何在这个全球最大的数据集合中发现有用信息成 为数据挖掘研究的热点。近年来i n t e m e t 使计算机、网络、通信融合为一，网上购物、 博客、眼球经济等新概念的出现，以其独特的方式和巨大的效益，成为信息科学领域中 最引人注目的研究课题。然而，w e b 网络在快捷、方便地带来大量信息的同时，也带来 了一系列的、不可忽视的问题，诸如：数据信息海量化以至难以高效吸收并利用；信息 的真伪越来越难以准确判断；私密信息的安全性难以得到强有力的保证；信息的表现形 式不一致等等。如何更快速、更准确地获得真正有价值的网络信息和资源；如何更深层 次的理解已有的历史数据并用于预测未来的方向和行为；如何从这些半结构化或非结构 化的海量数据中发现知识等一系列问题促使了基于w e b 的知识发现和数据挖掘领域的 出现。 1 1 引言 在诸多的信息来源中，w w w 以超文本的形式给用户提供了包含从科研资料、商业 咨询到时事新闻、娱乐信息等多种类别和形式的信息。可以说w e b 是全球最大的电子 信息数据仓库，蕴含着巨大的潜在价值和知识。然而，i n t e m e t 是一个具有开放性、自 治性、时效性、动态性、异构性的全球分布式网络。资源分布不匀，没有统一的结构和 管理方式，这就导致了信息、知识获取的困难，即所谓的耻c hd a t ap o o ri n f o r m a t i o n 的 问题。 如何在w e b 数据的海洋里更加快速而准确的找到自己需要的相关信息成为当前面 临的一大难题。比较经典的链接分析算法p a g e r a n k 、h i t s 等，在搜索引擎上的应用迎 合了广大用户的需求。 传统意义上的搜索查询是指能够帮助用户迅速、准确地找到所需物品。例如，人们 可以通过图书管理员手工制作的书籍编目中寻找所需的图书。但是随着信息量的增大， 这种手工方式，不管是从时效性还是从准确性上来讲，都不能再满足检索的需要。图书 藏量的增大导致工作量的增大，更进一步导致工作人员的增多、管理复杂程度急速增大， 效率严重下降。对于高速发展的互联网更是如此。如何从如此众多的信息中及时、精确 地获取所需要的信息，已是迫在眉睫的问题。为用户能够省时省力、快速准确的寻找自 己真正需要的资源，为信息资源发布者能够让更多的用户共享他们提供的信息和服务， 将海量的网络资源搜集起来，并按某种要求分类排序供用户查询访问，搜索引擎应运而 生。通过搜索引擎人们可以快速定位到所需要的信息，这在一定程度上缓解了人们低效 1 绪论硕士论文 访问网络资源、面对海量的网络信息却无从下手的困境。目前，比较有影响的搜索工具 有g o o g l e 、y a h o o 、百度、a l t a v i s t a 等。 1 2 研究概述 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 搜索的精度和效果。 目前根据这种超链接信息分析的思想，对网络的组织结构和链接关系进行挖掘的主 要算法大体可以分为四类： 1 、基于随机漫游模型的，比如p a g e r a n k 算法等【l j 。它由l a r r yp a g e 和s e r g e yb r i n 于1 9 9 8 年提出。现在已成为g o o g l e 搜索引擎中网页排序的核心算法，并取得了重大的 商业性成功。 2 、基于h u b 和a u t h o r i t y 相互加强模型的，比如h i t s 2 1 及其改进算法a r c 等。h i t s 算法是在1 9 9 8 年由j k l e i n b e r g 提出的经典的主题提取算法( h y p e r l i n k - i n d u c e d t o p i c s e a r c h ) 。h i t s 算法成功的在i b m 的c l e v e r 系统中得到了应用。 3 、基于贝叶斯模型的，比如贝叶斯算法及其简化版本等。 2 硕士论文 基于语义相似度的w e b 结构挖掘算法研究及实现 4 、基于概率模型的，如s a l s a ，p h i t s 算法等。 目前研究最为广泛，并在实践中得到良好应用的算法有p a g e r a n k 、h i t s 等。世界 上还有其它许多的科研团体或者个人在这领域不断进行广泛的研究和新的尝试。文献【3 】 中作者将随机取样的方法与w e b 超链接的分析结合起来挖掘w e b 信息。文献 4 】中作者 则侧重于从w e b 的h u b 值挖掘入手来匹配人们需要的w e b 信息。 基于超链接的排序算法纯粹地基于链接分析来发现权威网页，完全忽略网页的具体 内容，造成“主题漂移 现象：有部分网页，它们之间相互链接密度很高，使权威值偏 大，但是在内容上却偏离主题。i b m a l m a d e n 研究中心的c l e v e r 工程组提出的a r c 算 法( a u t o m a t i cr e s o u r c ec o m p i l a t i o n ) 就是在赋予网页集对应的链接矩阵初值时，结合了链 接锚文本( a n c h o r ) 的信息，使不同链接具有不同的权值，提升了用户满意度。 本论文主要是对p a g e r a n k 算法进行深入分析和研究，然后针对其存在的缺陷，提 出一种修正方法一一引入基于知网的语义相似度的概念。根据形成的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 值。以 此来改善搜索效果，从而提高用户满意度。 1 3 本论文主要工作及组织结构 本文综合分析了基于超链接信息的w e b 数据挖掘和信息检索技术中最具有代表性 的几种算法：p a g e r a n k 算法和h i t s 算法等。其中重点对g o o g l e 搜索引擎所采用的 p a g e r a n k 算法作了详细的分析，并针对该算法中存在的问题引入了自己的解决方案来 优化p a g e r a n n k 算法的迭代过程。系统原型中引入了基于世界知识的知网字典的语 义相似度的概念。在第2 章节和第4 章节对其相关知识作了详细的阐述。 本文的主要工作可归纳为以下几点： 1 、对w e b 数据挖掘做了全面阐述，重点在w e b 结构挖掘。并主要针对目前基于网 页中的超链接结构信息的排序算法进行研究与分析，发现其中所存在的问题。 2 、客观地评价了对p a g e r a n k 的各种改进算法的适用环境和性能。针对p a g e r a n k 值与网页内容完全无关的缺陷，引入了基于知网的语义相似度的概念。 3 、设计了一个融入基于知网语义相似度的p a g e r a n k 算法的信息检索系统原型， 并对改进后的算法进行实验验证与分析。 全文共分为6 章： 第1 章绪论 分析i n t e m e t w e b 及相关搜索技术的发展状况，提出面临的问题；概述研究现状， 1 绪论硕士论文 归纳算法种类及其应用。并给出了本论文的主要工作安排。 第2 章w e b 数据挖掘与语义相似度 共分两部分： 1 、介绍w e b 数据挖掘的种类、难点、重点及w e b 数据挖掘的基本思想和流程。 2 、对语义相似度和知网语义字典的相关知识进行了初步介绍，为下文中在 p a g e r a n k 算法中引入语义相似度作铺垫。 第3 章w e b 结构挖掘算法 从计算机学和数学两个角度，对著名的网页排序方法一- - p a g e r a n k 算法的原理进 行了深入研究和分析并给出了评价。同时也对其它相关算法，如h i t s 算法、s a l s a 算 法等做了相关介绍。 第4 章基于语义相似度的p a g e r a n k 算法改进 首先分析p a g e r a n k 算法存在的缺陷，阐述现有的改进算法；然后针对p a g e r a n k “与 内容无关”的缺陷，提出融入语义相似度概念。并进一步深入讨论计算语义相似度的问 题、网页中锚文本与其指向的网页主题内容相关性问题。 第5 章模拟系统的实现及测试 设计了一个融入基于知网语义相似度的p a g e r a n k 算法的信息检索系统原型， 并给出部分实验结果及分析。 第6 章总结与展望 对全文进行研究总结及展望，并指出今后的研究方向及需要做的工作。 4 硕士论文 基于语义相似度的w e b 结构挖掘算法研究及实现 2w e b 数据挖掘与语义相似度 2 1w e b 数据挖掘概述 w e b 挖掘作为数据挖掘的一个新方向、新主题，已经逐渐成为人们研究的热点。它 实现对w e b 存取模式、w e b 结构和规则，以及动态的w e b 内容的查找。w e b 挖掘可以 在很多方面发挥作用，如在搜索引擎中确定权威页面、w e b 文档分类、w e b l o g 挖掘、 智能查询、建立m e t a w e b 数据仓库等。w e b 数据挖掘是一项多学科领域交叉的综合技 术，涉及到数据挖掘、a g e n t 技术、计算机语言学、信息学、w e b 数据规范等多个领域。 不同研究者从自身的领域出发，对网络信息的含义有着不同的理解，因此科学研究也各 有其侧重点。例如，国外有人认为：w e b 挖掘就是利用数据挖掘技术，自动地从网络文 档以及服务中发现和抽取信息的过程。国内则众说纷纭，有学者将网络环境下的数据挖 掘归入网络信息检索和网络信息内容的开发。也有站在信息服务的角度上提出“w e b 挖 掘 ，指出其有别于传统的信息检索，能够在异构数据组成的信息库中发现有价值的信 息和知识，并提出w e b 挖掘将改革传统的信息服务方式而形成一个全新的适合网络时 代要求的信息服务组合。可以一般地将w e b 挖掘定义为p j ： w e b 数据挖掘是指从大量w e b 文档的集合c 中发现隐含的模式尸。如果将c 看作 输入，将尸看作输出，w e b 挖掘的过程就是从输入到输出的映射过程：c 一 p 。 w e b 数据和一些诸如存放在关系数据库中的数据是有很大区别的。w e b 数据是属于 非结构化和半结构化数据。非结构化文档主要指w e b 上的自由文本，包括论坛贴子、 时事新闻、以及最近流行的博客文档等。在这方面的研究相对比较多一些，大部分研究 都是建立在向量表示法( 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 ci n d e x i n g ) ，它通过分析不同文档中相同主题 的共享词汇，找到他们共同的根，用这个公共的根结点代替所有覆盖的词汇，以此来减 少维空间。例如：“水果 、“肉 、“面包 、“零食 可以用他们的根“食物”来表示，这 样可以减少属性集合的规模。知网( h o w n e t ) 就是根据本体语义之间的关系而编写的 一部语义字典。相对于非结构化的w e b 数据来讲，w e b 上的半结构化文档挖掘是指在 加入了h t m l 、超链接、c s s 格式等附加结构的信息上进行挖掘，其应用包括超链接文 5 2w e b 数据挖掘与语义相似度 硕士论文 本的分类、聚类、发现文档之间的关系、提出半结构化文档中的模式和规则等【6 1 。 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 ) 、w e b 结构挖 掘( w e bs t r u c t u r em i n i n g ) 、w e b 使用挖掘( w 曲u s a g em i i l i n g ) 如表2 1 忉： 表2 1w e b 挖掘的分类 w e b 使用挖掘 w e b 结构挖掘w e b 内容挖掘 处理数据类型用户访问w e bw e b 结构数据瓜方法一般数据库方法一 数据处理的是无般处理的是半 结构数据，结构化数据 半结构化数 据 主要数据数据库日志、客w e b 文档内部自由化文h t 池标记的 户日志等或者文档之间本，h t m l超文本 的超链接信息标记的超文 本 表示方法图关系表，图词集，段落，o e m 关系 概念，瓜的 三种经典模 型 处理方法 统计，机器学机器学习，专有t f i d f ，统数据库技术 习，关联规则 算法如计，机器学 p a g e r a n k ， 习，自然语 h i t s言学习 主要应用 w e b 站点，商业页面权重，分类分类，聚类，模式发现，数 决策聚类，模式发现模式发现据向导，多层 数据库 2 2 1w e b 内容挖掘 w e b 内容挖掘指从w e b 所包含的网页内容、数据信息等中发现有用信息。w e b 上 的信息是多种形式表现的。传统的i n t e m e t 由各种类型的服务和数据源组成。服务包括 万维网服务、文件传输服务、远程登录服务等。表现在客户端的应用层次上，更是多种 多样，例如：政府信息服务、数字图书馆、电子商务数据、网上购物等等。数据源的可 见方式也是各不相同，w e b 内容挖掘的对象包括文本、数字、图片、音频、视频、多媒 体和其他各种类型的数据。由于网络带宽和资源等各方面的条件成熟，多媒体数据在网 络资源中的重要性也日益突出。因此对于w e b 多媒体数据挖掘在逐渐成为新的研究热 点。另外，针对无结构化文本进行的w e b 挖掘被归类到基于文本的知识发现( k d t ) 领域， 也称文本数据挖掘或文本挖掘。它也是w e b 挖掘中比较重要的技术领域。图2 1 为文本 6 硕士论文基于语义相似度的w e b 结构挖掘算法研究及实现 挖掘工作的流程图。 图2 1w e b 文本挖掘工作流程图 w e b 内容挖掘大体可分为两个不同的研究方向： l 、从资源查找的观点来看，w e b 内容挖掘的任务是从用户的角度出发。需要解决 的问题有：怎样提高信息质量，让用户得到更可靠、更真实的数据信息、帮助用户过滤 信息，让用户需要的信息在海量数据中脱颖而出。 2 、从数据库的角度讲，w e b 内容挖掘的任务主要是试图对w e b 上的数据进行集成、 建模，以支持对w e b 数据的复杂查询，提供个性化服务r 7 。 2 2 2w e b 使用挖掘 w e b 使用挖掘顾名思义即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 使用记录的数据直接预处理再进行挖掘。图2 2 为使用 挖掘流程图： 源数据 原始日志文件 预处理 预处理后的 数据文件 模式发现 图2 2w e b 使用挖掘流程图 各种模式 模式分析 有意义的 模式规则 7 2w e b 数据挖掘与语义相似度 硕士论文 根据数据来源、数据类型、数据集合中的用户数量、数据集合中的服务器数量等将 w e b 使用挖掘分为五类【5 】【6 】： 1 、个性挖掘：针对单个用户的使用记录对该用户进行建模，结合该用户基本信息 分析他的使用习惯、个人喜好，目的是在电子商务环境下为该用户提供与众不同的个性 化服务。 2 、系统改进：w e b 服务的性能和其他服务质量是衡量用户满意度的关键指标，w e b 使用挖掘可以通过用户的拥塞记录发现站点的性能瓶颈，以提示站点管理者改进w e b 缓存策略、网络传输策略、流量负载平衡机制和数据的分布策略。此外，可以通过分析 网络的非法入侵数据找到系统弱点，提高站点安全性，这在电子商务环境下尤为重要。 3 、站点修改：站点的结构和内容是吸引用户的关键。w e b 使用挖掘通过挖掘用户 的行为记录和反馈情况为站点设计者提供改进的依据，比如页面链接情况应如何组织、 那些页面应能够直接访问等。 4 、智能商务：用户怎样使用w e b 站点的信息无疑是电子商务销售商很关心的重点。 用户一次访问的周期可分为被吸引、驻留、购买和离开四个步骤，w e b 使用挖掘可以通 过分析用户点击流等w e b 日志信息挖掘用户行为的动机，以帮助销售商合理安排销售 策略。 5 、w e b 特征描述：这类研究与关注一样，通过用户对站点的访问情况统计各个用 户在页面上的交互情况，对用户访问情况进行特征描述。 2 2 3w e b 结构挖掘 从整体的角度来看，w e b 网页的链接结构信息所包含的潜在知识是十分丰富的。这 也是本论文最基本的理论依据之一。w e b 结构挖掘就是指通过分析不同网页之间的超链 接结构以及文档u r l 中的目录路径结构等挖掘w e b 潜在的链接结构模式。通过分析一 个网页链接和被链接数量以及对象来建立w e b 自身的链接结构模式。这种模式可以用 于网页归类，并且由此可以获得有关不同网页间相似度及关联度的信息。w e b 结构挖掘 有助于用户找到相关主题的权威站点。 w e b 结构挖掘的对象是w e b 本身的超链接，即对w e b 文档的结构进行挖掘。我们 把网页之间的关系分为入链接和出链接两种。运用引用分析方法找到同一网站内部以及 不同网站之间的链接关系。这种超链接存在的潜在关系就是我们需要的信息。因为文档 之间的超链接反映了文档之间的包含、引用或者从属关系。对被引用文档的一般都是对 引用文档做了更客观、更概括、更准确的详细阐述和分析【5 1 。 在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 搜索引擎就采用了该类算法对网页进 8 硕士论文基于语义相似度的w e b 结构挖掘算法研究及实现 行排序。 w e b 结构挖掘的应用实例主要有： 1 、帮助结果排序8 】【9 】 因为i n t e m e t 上的网页数量己达4 0 亿之多，不可能对全部的页面进行链接分析。所 以实际的工作过程，一般采用的方法是：先用基于关键词的搜索引擎得到一个集合( 取 前面m 个) 。然后对这m 个页面应用p a g e r a n k 或h i t s 算法，得到最终的排序结果。 对这两个算法的分析和评价，将会在下文中详细介绍。 2 、指导网页采集【9 】【1 0 】【1 1 】 网页采集是搜索引擎中s p i d e r 爬行网页的过程。它一般是根据网页之间的链接信息 来进行深度采集或者广度采集。它不考虑网页内容质量，由于w e b 数据的海量化，这 种采集方式效率已无法满足需要。为了采集“高质量 的网页，就应按照网页质量的高 低依次来进行采集，使得采集少量的网页而获得最好的网页。此时网页链接分析可以为 判断网页的质量提供一种参考依据。 3 、检索结果聚类旧 与基于词或短语的诸多文本聚类算法不同，还可以使用超链接分析的方法来对搜索 出来的结果进行聚类。它是基于c o - c i t a t i o n 和c o u p l i n g 分析来过滤无关文档，将质量高 的文档进行聚类，提供给用户进行浏览和访问。这样将大大提高用户访问效率，使用用 户可以在更短的时间内查找到自己需要的信息资源。 4 、查找 i i 关i n n ( q u e r yb ye x a m p l e s ) t 9 】【1 3 】 在访问网络资源时，经常发现，单一的一个网页，无法满足对某一实例的认识。此 时我们就想迅速找到和此实例相关的其它网页( f i n dr e l a t e dp a g e s ) ，以便对此实例有一 个更全面、更准确的认识。在g o o g l e 和n e t s c a p e 中支持这种功能，并提供服务。传统 的信息检索技术是采用文本相似度，而在w e b 环境中，可以充分挖掘链接结构来实现。 k l e i n b e r g 声称将h i t s 算法稍加修改也可以用来实现实例查找。基于链接分析的算法从 总体上来讲是优于基于文本相似度算法。 5 、消除重复网页9 】【1 4 】 网页路径是u r l ( 统一资源定位符：因特网上标准的资源地址) 的一部分。例如 u r l ：h t t p ：w w w b a i d u c o 垤a o j i a d v a n c e d h t m l 。w w w b a i d u c o r n 就是主机地址， 儋a o j i a d v a n c e d h t m l 就是路径。根据超链接的特性，如果服务器a 1 中的文档路径和结 构与服务器a 2 的相似时，就可以确定a 1 和a 2 是镜像网站。反之亦然。通过分析超链 接信息可以检测出近似的镜像网站，节省了网络服务提供商的索引时间、索引空间、存 储空间等，从而从整体上减少了运行时间并提高了运作效率。 6 、确定w e b 影响因子( w e bi m p a c tf a c t o r ) l 1 4 1 w e b 影响因子是从期刊影响因子( i m p a c tf a c t o r ，i f ) 发展过来的。期刊的影响因子是 9 2w e b 数据挖掘与语义相似度 硕士论文 表征期刊影响大小的一项定量指标。也就是某刊平均每篇论文的被引用数，它实际上是 某刊在某年被全部源刊物引证该刊前两年发表论文的次数，与该刊前两年所发表的全部 源论文数之比。计算公式： 1 f ( k ) = ( 刀一l + ? l k _ 2 ) ( a r 七。+ m 一2 ) 。( 2 1 ) 说明：k 为某年，m 一。和m 一：为该刊在前一两年发表的论文总数量，r l k _ ! 和刀h 该刊 在k 年的被引用数量。也就是说，某刊在2 0 0 9 年的影响因子是其2 0 0 8 和2 0 0 7 两年刊 载的论文在2 0 0 9 年的被引总数除以该刊在2 0 0 8 和2 0 0 7 这两年的载文总数( 可引论文) 。 w e b 影响因子的基本原理是：越多网页通过超链接指向某一站点或区域，就说此站 点或区域越有影响力。但是由于网络资源的随意性、非规范性，比如说：有些超链接是 导航；有些超链接是广告链接；甚至有些链接是具有破坏能力的恶意链接，这些链接也 需要进行相应处理和分析。只有这样才能发现许多蕴涵在w e b 内容之外的对我们有潜 在价值的模式和知识的过程i l 引。 总之，分析这些链接结构可以从中获取有用的知识。由于文档之间的互连，w w w 能够提供除文档内容之外的有用信息。利用这些信息，可以对页面进行排序，发现重要 页面，重新组织内容结构，使内容逻辑结构更加合理。w e b 结构挖掘是以超链接分析为 基础评估w e b 资源，提高搜索质量，客观上避免了人为作弊。它缩短了人们在搜索结 果中挑选自己需要的信息的时间。 2 3w e b 数据挖掘流程 与传统数据相比，w e b 上的信息具有独特的性质，比如：多种格式、动态变化、海 量等，并且h t m l 网页中信息内容和格式控制符是混在一起的。不像x m l 那样层次分 明、内容和格式清楚明了。所以很难直接以w e b 网页上的数据进行数据挖掘，而必须 经过必要的数据处理。然后才能进行数据挖掘。典型w e b 挖掘的处理流程如下1 5 j ： 1 、寻找资源：首先要完成的任务就是从目标w e b 文档中得到科学研究所需要的数 据。这些信息资源不仅限于在线w e b 文档，还包括电子邮件、个人注册信息、浏览记 录或者网站的日志数据甚至是通过w e b 进行电子商务作业而形成的数据记录。 2 、信息选择和预处理：主要是从取得的w e b 资源中去掉不关心的信息，并将信息 进行必要的整理。例如从w e b 文档中自动去除广告链接、去除多余格式标记等，使其 成为我们需要的内容，并将这些内容格式化成规范的结构。 3 、模式发现：自动进行模式发现。它可以在同一个站点内部或在多个站点之间进 行。 4 、模式分析：验证、解释上一步骤产生的模式。它可以是机器自动完成，也可以 是与分析人员进行交互完成。 w - e b 挖掘流程如图2 3 所示： 1 0 硕士论文 基于语义相似度的w e b 结构挖掘算法研究及实现 图2 3w e b 挖掘的处理流程 w e b 挖掘作为一个完整的技术体系，在进行挖掘之前的信息获得i r ( i n f o r m a t i o n r e t r i e v a l ) 和信息抽取i e ( i n f o r m a t i o ne x t r a c t i o n ) 相当重要。i r 的目的在于找到相关w e b 文档，它只是把文档中的数据看成未经排序的词组的集合，而i e 的目的在于从文档中 找到需要的数据项目，它对文档的结构和表达的含义感兴趣，它的一个重要任务就是对数 据进行组织整理并适当建立索引。 对于瓜和i e 的研究已近有很长时间。但是中文信息抽取方面的研究起步较晚，主 要的研究工作集中在对中文命名实体的识别方面，在设计实现完整的中文信息抽取系统 方面还处在探索阶段。随着w e b 技术的发展，基于w e b 技术的r 、i e 得到了更多的重 视。由于w e b 数据量非常大，而且可能实时变化，用原来手工方式进行信息收集已经 很难满足现实的需要，目前的研究方向是用自动化、半自动化的方法在w e b 上进行信 息获得和信息抽取。最近几年在这两方面都有相应的研究成果和具体应用，特别是在大 型搜索引擎中得到了很好的应用i l6 j 。 2 4w e b 数据挖掘的应用前景 虽然在国内数据挖掘技术还处于起步阶段，但是在国外，数据挖掘技术已经广泛地 应用于各行各业中，随着网络的发展，基于w e b 的数据挖掘也正在成为一个热点。网 络信息挖掘的应用涉及到网站设计、电子商务和搜索引擎服务等众多方面。下面主要从 这三个方面介绍其应用【6 j 。 1 、网站设计。通过对网站内容的挖掘，比如对访问日志、网站内超链接结构等数 据，可以更有效地组织网站信息。结合对用户访问日志记录信息的挖掘，把握用户的兴 趣，从而有助于开展网站信息推送服务以及个人信息的定制服务( 个性化访问服务) ； 对站内超链接分析，可以知道用户访问的规则习性以调整网站结构，提高站点访问量。 2 、电子商务。运用w e b 使用挖掘方法和技术能够从服务器和客户端的日志记录中 自动发现隐藏在数据中的模式信息，掌握系统的访问模式以及用户的行为模式，从而做 出具有预测性的分析。例如通过用户在某一网页中逗留时间的长短，可以判断出用户对 所访问资源兴趣度的高低；对日志文件所收集到的域名数据，如国家是以g o v 结尾、教 育是以e d u 结尾等的分类分析；可以应用聚类分析来识别用户的访问动机和访问趋势 等。 2w e b 数据挖掘与语义相似度 硕士论文 3 、搜索引擎。比如g o o g l e ，它的最大特色体现在基于对网页超链接信息的分析技 术之上进行网页排序。另外随着本体技术的发展，结构挖掘技术也在逐渐融入内容挖