（计算机应用技术专业论文）基于weblog的网页预测模型研究.pdf

太原理工大学硕士研究生学位论文 基于w e b - l o g 的网页预测模型研究 摘要 随着互联网信息及用户的飞速增长，如何有效减少用户访问延时，提 高网络服务质量是一个迫切需要解决的难题，缓存与预取技术是克服此难 题的有效方法。但由于随着w w w 上动态内容和个性化服务的比重日益增 加，缓存技术对网络性能的改善已不再显著，而预取技术是缓存技术的一 种有效补充手段，是突破缓存性能上限的最有效的方法，正越来越成为w e b 加速技术领域研究的热点。 在网页预测方面m a r k o v 模型是一种简单而有效的工具，但现有的预测 方法都有预测准确率和预测覆盖率存在矛盾，并且存储复杂度较高的缺点。 因此，改进基于m a r k o v 模型进行用户浏览路径预测的方法成为w e b 日志 挖掘的一个新课题。本文对国内外关于m a r k o v 模型浏览路径预测的研究现 状进行了综合分析，指出了现有的预测方法存在的问题，并提出了改进方 案，对如何改进基于m a r k o v 模型的预测方法这一问题进行了研究。 论文首先介绍了i i l t e m e t 和w w w 起源、发展及现状，提出了互联网 所面临的问题及解决方案。然后阐述了w e b 数据挖掘的基本概念、分类以 及数据预处理的一般方法和过程。介绍了常用的挖掘算法一关联规则算法， 并针对其存在的不足提出了改进的算法。 其次本文提出了新的用户浏览兴趣偏爱度，用传统的用户对网页兴趣 偏爱度的方法，无法反应用户的真正浏览兴趣和网页的重要程度。新的偏 爱度度量方法，不仅考虑了页面的浏览频度，而且引进了页面的访问时间 和页面本身的大小，弥补了传统方法的不足，最后利用实验证明了该度量 方法的有效性。 太原理工大学硕士研究生学位论文 接着，作者提出了二步m a r k o v 预测模型，主要解决了高阶m a r k o v 模 型空间复杂度过高以及覆盖率逐步下降的问题，在此基础上又提出了混合 m a r k o v 模型，给出了对应的理论支持和相应的参数求解方法，并在时间复 杂度和空间复杂度上进行了分析和对比，结果表明混合m a r k o v 模型在这两 个方面都优于二阶m a r k o v 模型。 最后，论文对提出的预取模型在真实w e b 日志中进行了实验，并对实 验结果进行了分析。 关键词：w e b 曰志挖掘，m a r k o v 模型，预测，浏览兴趣，关联规则 太原理工大学硕士研究生学位论文 r e s e a r c ho fw e bp r e d i c a t i o n m o d e lb a s eo nw e b l o g a bs t r a c t w i t ht h er e m a r k a b l ea n de x p o n e n t i a lg r o w t hr a t eo fw e bi n f o r m a t i o na n d u s e r s ，h o wt or e d u c et h eu s e rp e r c e i v e da c c e s sl a t e n c ya n di m p r o v et h eq u a l i t y o fs e r v i c eo ft h en e t w o r ki sc o m i n gac r u c i a lp r o b l e m ，a n dw e bp r e f e t c h i n ga n d w e bc a c h i n ga r et h ep r i m a r ys o l u t i o n s w e bc a c h i n gt e c h n i q u eh a sb e e nw i d e l y u s e di nd i f f e r e n tp l a c e so fi n t e m e t b u ta sd y n a m i cd o c u m e n t sa n dp e r s o n a l s e r v i c e si n c r e a s ea l lo v e rt h ew o r l d ，t h ep e r f o r m a n c eo fc a c h i n gd e t e r i o r a t e s s i g n i f i c a n t l y a sar e s u l t ，w e bp e r f e c t i n g ，w h i c hi sa n e f f i c i e n tw a yo fm a k i n gu p f o rw e bc a c h i n g ，a n dt h em o s te f f e c t i v em e t h o dt ob r e a kt h eu p p e rb o u n do f c a c h i n gp e r f o r m a n c e i sc o m i n gah o t s p o ti nw e bs p e e d u p r e s e a r c ha r e a t h em a r k o vm o d e li sas i m p l ea n dp r a c t i c a lt o o lt op r e f e t c hw e b b u ts o m e e x i s t i n gp r e d i c t i o n m e t h o d sb a s e do nm a r k o vm o d e ls t i l lh a v es o m e s h o r t c o m i n g s oi tb e c o m e san e w l e s s o ni nt h ea r e ao fw e bl o gm i n i n gt h a th o w t oi m p r o v ep r e d i c t i o nm e t h o d s t h i sp a p e ra n a l y s e st h ec u r r e n td o m e s t i ca n d i n t e r n a t i o n a lr e s e a r c hr e s u l t so fh o wt ou s em a r k o vm o d e lt op r e d i c tw e b t h e n w ef i n ds o m ep r o b l e m so fe x i s t i n gp r e d i c t i o nm e t h o d sb a s e do nm a r k o vm o d e l s a n dw es t u d yt h ei m p r o v i n go fp r e d i c t i o nm e t h o d sb a s e do nm a r k o vm o d e l f i r s to fa l l ，t h i st h e s i si n t r o d u c e st h ed e v e l o p m e n ta n dt h es t a t eo ft h e i n t e m e ta n dw 州 g i v e st h ep r o b l e m si n t e m e tf a c e da n dc o r r e s p o n d i n g s o l u t i o n s ；a n dd e s c r i b e st h ec o n c e p t ，c l a s s i f i c a t i o no fw e b d a t am i n i n g ；a n dw e b l o gm i n i n gd a t ap r e p r o c e s s i n gp r o c e s s i no r d e rt oo v e r c o m et h ed r a w b a c k so f a p r i o r ia l g o r i t h m f o rm i n i n gf r e q u e n ti t e m s e t s ，t i m va l g o r i t h mw a sp r o p o s e d s e c o n do fa l l ，t h ei n t e r e s ti st h es e l e c t i v i t ya t t i t u d eo fo b j e c t i v em a t t e ro fa m 太原理工大学硕士研究生学位论文 p e r s o n ，a n dm e a s u r i n gu s e r sb r o w s ei n t e r e s te x a c t l yi st h eb a s eo fw e bb a s eo f w e bs c h e m a m i n i n g t h i sp a p e ra n a l y s e st h ep r e s e n tt h es h o r t a g eo ft h es t y l eo f m e a s u r ea n de x p r e s s e st h eb r o w s i n gi n t e r e s to fu s e r f o ri n s t a n c e ，t h et o os i m p l e m e a s u r ef a s h i o no f t e n l e a d st od i f f i c u l t yo fd i s t r i b u t i o nw h i c hi st h eu s e r i n t e r e s t e di no rn o t ，n o tc o n s i d e r i n gt h ep a g ei n f o r m a t i o na m o u n t si n f l u e n c eo n t h eu s e r s b r o w s et i m ea n ds oo n a sar e s u l t ，p o i n to u tam e t h o db a s e do nu s e r s b r o w s eb e h a v i o rt om e a s u r et h eu s e r s b r o w s ei n t e r e s t t h e n ，ah y b r i dm a r k o vp r e d i c t o rm o d e lw a sp u tf o r w a r db a s e do nt h e s t e p 一2m a r k o vm o d e l ，w h i c hc a ns o l u t e st h ep r o b l e mo fh i g hm e m o r yd e m a n d a n dt h el o wa p p l i c a b i l i t y b e s i d e st h a t ，t h i sp a p e rg i v e st h es u s t a i n i n gt h e o r ya n d t h ew a yt og e tt h ep a r a m e t e r s f i n a l l y , e x p e r i m e n t sh a v eb e e nm a d eb a s e do nt h ep r e d i c t i o nm o d e la n d e x p e r i m e n t a lr e s u l t sa r ea n a l y z e d k e yw o r d s ：w e bm i n i n g ，m a r k o vm o d e l ，p r e d i c a t i o n ，a s s o c i a t i o nr u l e s ， b r o w s ei n t e r e s t i v 声明尸州 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名： 门。 埋笏仅日期：3 盈星：。( 。z 兰 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为：目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签名：正_ | 日期：2 型鱼：。! 兰 导师签名：! ! 二逊立日期：2 巫! ! 兰 太原理工大学硕士研究生学位论文 第一章绪论 1 1 研究背景和意义 1 1 1 研究背景 随着互联网技术的飞速发展和i n t e m e t 信息量的急剧增长，网络已成为人们获取信 息的重要来源。近年来，虽然网络速度得到了很大的提高，但是由于i n t e r n e t 的用户数 量剧增以及w w w ( w o r l dw i d ew e b ) 信息量的爆炸式增长，使得网络越来越拥挤，用户 的服务质量( q o sq u a l i t yo fs e r v i c e ) 得不到很好的保证，用户在访问网页之前往往要忍 受较长的等待时间，以至于有人形象地将w w w 戏称为w o r l dw i d ew a i t 。因此，如何 缩减w e b 访问延迟、改善w w w 服务质量已经成为改善i n t e m e t 应用环境的主要目标。 事实上，w e b 延迟问题并非只受到用户的关心，i n t e m e t 的运营商特别是i c p ( i n t e m e t c o n t e n tp r o v i d e r ) 也迫切地要求减少用户的访问延迟，提高服务质量。有一个被广泛引用 的称为“八秒钟规则”的统计1 1 表明：在电子通信中，如果一个w e b 站点的装载时间超 过8 秒，用户就更可能感到失败而离开这个站点。因此，i c p 出于经济利益的目的以及 商业竞争的需要，也迫切地要求提高w w w 服务的响应速度。为了缓解网络带宽的需 求与其增长之间的矛盾、减少w e b 延迟，从9 0 年代初期开始，i n t e m e t 的运营商和研究 者们就一直在探索各种有效的方法。实践证明，单纯依靠增加硬件和带宽，如提高网络 主干线带宽、采用宽带接入方式等，不仅代价高昂，而且也无法从根本上解决问题。目 前，用于减少w e b 访问延迟的主要技术有两种：即w e b 缓存( c a c h i n g ) 和预取( p r e f e t c h i n g ) 技术。 缓存技术己在网络节点的不同位置( 缓存可以分布在客户端、代理服务器端、服务器 端) 得到广泛应用。但随着w w w 上动态内容和个性化服务的比重日益增加，缓存带来 的性能改善已不再显著2 1 。研究表明3 1w e b 缓存的命中率在2 4 到4 5 之间，一般不超 会过5 0 。而预取技术是缓存技术的进一步扩展，则可以在多个方面实现w e b 系统的 优化： 首先，预取机制可以使命中率进一步提高，达到6 0 。8 0 ； 其次，预取机制可以减少网络访问延迟，提高服务质量q o s ； 太原理工大学硕士研究生学位论文 第三，预取机制与缓存技术相比，预取是有针对性的，消耗的存储空间相对较少； 第四，预取机制可以满足用户个性化需要，反映用户个人的兴趣； 第五，预取机制可以平滑网络流量，使得有限的网络资源得到较为合理的利用。因 此，w e b 预取技术的研究对缩减w e b 访问延迟和提高服务质量q o s 有着重要意义。 1 1 2 课题的意义 尽管w e b 代理和高速缓存的使用，能够有效地减少用户的访问延迟，并减轻网络 和原始服务器的负载，但是，w e b 代理和高速缓存在管理、通信等方面的复杂性，以及 高速缓存一致性的维护，又限制了其性能的进一步提高。目前，虽然存储空间的价格越 来越低，为提供超大规模的w e b 高速缓存提供了条件，但单纯依靠增大高速缓存的体 积，除了增加管理成本外，并不能持续地提升高速缓存的命中率，这就为w e b 预取技 术提供了广阔的生存空间。w e b 预取作为提升w e b 高速缓存命中率的一种手段，己经 越来越显示出它的重要性，也越来越引起研究者和n 厂商的重视。 m a r k o v 模型在路径预测中的应用技术对于日志信息挖掘来说有着深远的影响和巨 大的作用。下面从两方面来说明这一课题的研究意义。 第一，面对急速膨胀的网络空间，m a r k o v 模型为人们提供了一种在海量数据中搜 索有用信息的途径。首先，利用m a r k o v 模型能在日志中发掘出用户已经完成的频繁的 浏览路径，这对于网站建设、网站个性化服务以及电子商务来说是非常重要的，因为这 些路径是实现网站建设和网站个性化服务的主要依据。同时，利用m a r k o v 模型还能够 对用户未来的浏览路径做出较高质量的预测，比如一些改进的m a r k o v 模型预测准确率 达到了8 5 左右【3 】，这样有利于开发各种浏览导航工具，为用户提供更好的服务。 第二，虽然m a r k o v 模型由来己久，但是将它应用于w e b 日志挖掘和路径预测的时 间并不长( 始于1 9 9 9 年) ，因此这项技术还有许多地方有待完善和改进，例如，空间复杂 度很高，预测准确率还有待提高，模型中的矩阵建立过于简单，未能准确反映不同用户 的浏览兴趣等等。 针对上述问题，本文提出了混合m a r k o v 模型的预测方法，对于m a r k o v 模型在网 页预测中的应用具有重要意义。 我们的目标是通过识别用户的访问行为，发现浏览兴趣，进而向每个用户提供面向 个性化的预取服务，最终实现减少访问延迟、提高服务质量的目的。 2 太原理工大学硕士研究生学位论文 1 2w e b 预取研究现状 现有的网页预取技术按照实施的位置，可分为以下三种：客户端、代理服务器端和 服务器端。 客户端预取由客户端根据客户的历史访问信息及当前请求进行预取并将预取内容缓 存在客户端缓存中，客户端预取在分析客户历史访问信息时相对准确，但无法与其他客 户共享预取内容，因而可能会造成较大的网络流量：代理服务器端预取由代理服务器分 析客户的历史访问信息，对客户的当前请求进行预取并将预取内容缓存在代理服务器缓 存或发送到客户端缓存中，代理服务器预取可以发挥群体客户访问同一网站时的请求内 容局部性的特点，实现预取内容的多客户共享，其不足在于代理服务器面对的是多客户， 多网站的访问信息，预取的复杂度相对较高；服务器端预取由服务器对客户的访问信息 进行分析，对客户的当前请求进行预取并将预取内容放入缓存或发送给代理服务器以及 客户。服务器端预取比代理服务器端预取更能发挥群体客户访问内容的局部性，取得的 更的效果，且服务器端保存的客户访问内容只是本网站的内容，可以更好地分析客户网 站内容的喜好部分、喜好程度，从而更好地进行内容预取。服务器端预取的难点在于： 由于缓存系统的存在，服务器端保留的客户访问信息并不能真实地反映客户的访问内 容；由于代理的存在，对客户的辨别造成一定的难度。本文主要研究服务器端预取技术。 按照具体的预取模型划分，可分为页面关联预取模型、文档聚类预取模型、文本匹 配预取模型及其它预取模型。这些模型大部分都是从不同的侧面对客户的访问记录进行 分析，建立预取模型，依据该模型对日志文件进行知识转换和提取，再依据这些先验知 识以及客户当前请求对客户接下来的请求进行预测。对于这部分内容我们将在第三章中 详细叙述。对于这方面的问题，许多学者都进行了卓有成效的研究。 a z e r l 4 1 提出了基于概率模型的预取方法。根据服务器日志( l o g ) 数据，服务器计算出 在一定时间间隔内，网页间被连续访问的概率，并建立条件概率矩阵。以此，服务器预 测用户的访问请求。s a r u k k a i m 运用马尔可夫链进行访问路径分析和链接预测，在此模 型中，将用户访问的网页集作为状态集，根据用户访问记录，计算出网页间的转移概率， 作为预测依据。s c h e c h t e r 等人【6 1 构造用户访问路径树，采用最长匹配方法，寻找与当前 用户访问路径匹配的历史路径，以此预测用户接下来的访问请求。 x uc h e n g z h o n g 等人f 7 1 引入神经网络实现基于语义的网页预取。通过抽取网页超 太原理工大学硕士研究生学位论文 链描述文字信息中的关键词作为神经网络的输入，神经网络输出结果作为预取依据。用 户浏览的页面作为训练样本反馈给神经网络进行学习。由于关键词的多义性会影响预取 的准确性，该模型对预取网页的范围采取分类处理，不同类别构造不同的预取器。 徐宝文等人【s 1 提出了一种基于数据挖掘的预取模型。模型利用客户端浏览器缓冲区 数据，挖掘其中蕴含的兴趣关联规则，以此预测用户可能选择的链接。在此模型中，用 户兴趣表现为对词条的兴趣，兴趣关联规则表示从一个词条转向其他词条的可能性。利 用兴趣关联规则，结合用户当前访问的页面的轨迹和用户访问的当前页面，预测用户可 能访问的链接。 朱培栋等人【9 】提出提炼用户会话特征，按语义对用户会话进行分类。在回应用户访 问请求时，服务器计算当前用户访问路径与各类别中心的距离，确定会话所属的类别。 根据会话所属类别的共同特征，预测用户可能访问的文档，一次性地预送到客户端。 上海交通大学许欢庆等人【1 0 1 提出了一种基于隐马尔可夫模型的网页预取方法，该方 法借助隐马尔可夫链模型，挖掘蕴涵在用户访问路径中的信息需求概念，以此进行预取 页面的评价，最终实现基于语义的网页预取。他们还发表了多篇相关的文章 i h 3 1 ，在网 页预测方面进行了卓有成效的研究。 1 3 论文的主要内容和组织结构 根据整篇文章的内容安排，本文共分六个部分，其具体内容和组织结构如下： 第一章为绪论部分，主要论述本课题研究的背景和意义；以及w e b 预期的研究现 状，是整篇文章的综述和开始。 第二章讲述w e b 数据挖掘，在该部分主要讨论了w e b 挖掘的一些基本概念和w e b 挖掘的一般分类方法，随后对数据预处理进行研究，数据预处理是数据挖掘的前提和基 础，数据处理的好坏直接影响到数据挖掘的结果和精确度。我们认真讨论了数据挖掘用 到的数据的来源和数据预处理的一般方法，最后通过实例说明了数据处理的过程。 第三章研究了预取模型技术，对常用的页面关联预取、会话聚类预取、文本匹配预 取模型进行了讨论和分析比较。关联规则和m a r k o v 模型是w e b 预取模型中的两个关键 技术。本章对关联规则a p r i o r i 进行了详细的描述，提出了改进的a 研谢算法，随后又 讨论了m a r k o v 模型的过程和方法，以及该模型存在的优缺点。 第四章为本文的重点内容之一，首先分析了用户浏览兴趣，引入了新的用户浏览兴 4 太原理工大学硕士研究生学位论文 趣度量方法，其次给出了基于w e b 1 0 9 的改进的m a r k o v 模型，给出了改进模型的理论 依据及其对应的整体框架，然后从理论和实验两个方面验证了该算法的有效性。其后对 预取用到的替换算法也进行了简单的说明。 第五章模型开发及性能分析，该部分综合前四部分的内容，用j a v a 编写完整的系统 进行仿真，详细讨论了系统的设计过程，说明了对应的数据库。通过准确率和覆盖率同 其他模型进行了比较，绘制了实验结果，最后指出了该模型可能的改进方向。 第六章工作总结和展望，这一部分总结整篇文章的内容，指出了作者所做的贡献， 对以后可能的发展方向进行了合理的预测。 太原理工大学硕士研究生学位论文 第二章w e b 数据挖掘技术 2 1 w e b 数据挖掘综述 w e b 目前是一个巨大的、分布广泛的、全球性的信息服务中心，它涉及新闻、广告、 消费信息、金融管理、教育、政府、电子商务和许多其它信息服务。w e b 还包括了大量 丰富和动态的超链接信息及w e b 页面的访问和使用信息，为数据挖掘提供了丰富的资 源。w e b 挖掘是数据挖掘的一个重要内容，它不仅仅是数据挖掘算法在w e b 数据上的 应用，与传统的数据库数据相比，w e b 数据具有特殊性，其特点就是数据没有严格的结 构模式、含有不同格式的数据f 文本、声音、图形等) ，并且存在大量的冗余和噪声。同 时，w e b 是一个动态性极强的信息源，所以面向w e b 的数据挖掘研究极具挑战性。 2 1 1w e b 挖掘的基本概念 目前，w e b 数据挖掘的研究范围十分广泛，这主要归因于不同的研究团体和人员有 着不同的研究兴趣以及w e b 上的信息资源的爆炸性增长。当研究人员在探讨w e b 数据 挖掘的确切定义和比较相互之间的研究成果时，这种现象会给人们带来一些困惑。为了 方便说明w e b 挖掘的概念，先对数据挖掘作一简单说明。 数据挖掘是近年来随着数据库技术和人工智能技术的发展而出现的一种全新的信 息技术，是指从数据中提取模式的过程。同时，数据挖掘又是一种决策支持过程，它主 要基于人工智能、机器学习、统计学等技术，高度自动化地分析企业原有数据，做出归 纳性推理，从中挖掘出潜在的模式，预测用户的行为帮助企业决策者调整市场策略，减 少风险，做出正确决策。 数据挖掘可简单地理解为从数据中挖掘有用的信息，这样理解数据挖掘既能反映数 据挖掘的目的，也能说明数据挖掘所处的阶段。依据数据挖掘的定义我们列出几个比较 公认的w e b 数据挖掘定义。 ( 1 ) w e b 挖掘的定义 w e b 挖掘是- f j 交叉性学科，涉及数据挖掘、机器学习、模式识别、人工智能、统 计学、计算机语言学、计算机网络技术、信息学等多个领域。对w e b 挖掘的定义可以 从多个角度。 6 太原理工大学硕士研究生学位论文 从广义的角度出发，可以对w e b 挖掘作如下的定义： 定义2 1 ：w e b 挖掘是指从大量非结构化、异构的w e b 信息源集合中发现有效的、 新颖的、潜在可用的及最终可理解的知识包括概念( ( c o n c e p t s ) 、模式( p a t t e r n s ) 、规则 ( r u l e s ) 、规律( r e g u l a r i t i e s ) 、约束( c o n s t r a i n t s ) 及可视化( v i s u a l i z a t i o n s ) 等形式) 的非平凡 过程。 如果从实用性开发的角度来考虑的话，可以对w e b 挖掘作出如下的定义： 定义2 2 ：w e b 挖掘是针对包括w e b 页面内容、页面之间的结构、用户访问信息、 电子商务信息等在内的各种w e b 数据源，在一定基础上应用数据挖掘的方法以发现有 用的知识帮助人们从w w w 中提取知识，改进站点设计，更好地开展电子商务等应用。 对于本文研究的基于w e b 1 0 9 网页预测模型来说，和定义2 2 比较吻合。 2 ) w e b 挖掘的特征 l n t e m e t 上存贮了大量的、非结构化的信息，无法使用现有的数据库管理系统来操 纵和管理。主要特点如下： 1 ) 大量存在的文档、图形、图像、声音信息及大型的商业数据、天气、水文数据 等表现出多种信息类型，而且用户有充分的自由，可以随意链接到i n t e m e t 的任意站点 上。因此，i n t e r n e t 本身体现了巨大的、分层的、多维的、非结构化、动态性、不完全 性、混沌的特点； 2 ) 用户群体也表现出多样性，全球信息网大约有数亿个工作站，其用户具有不同 的背景、不同的兴趣和目的； 3 ) w e b 上的信息只有很小的一部分是相关的或是有用的，甚至可以说9 9 的w e b 信息对于9 9 的用户是无用的。虽然这看起来不是很明显，但一个人只是关心w e b 上 的很小一部分信息确是事实，w e b 所包含的其余信息对用户来说是不感兴趣的，而且 会淹没所希望得到的搜索结果。 2 1 2w e b 挖掘的分类 w e b 数据挖掘分为w e b 结构挖掘( w e bs 仃u c 眦m i n i n g ) 、w e b 内容挖掘( w e bc o n t e n t m i n i n g ) 、w e b 使用记录挖掘( w e bu s a g em i n i n g ) ，如图2 1 所示。w 曲挖掘的两个主要 分支是w e b 内容挖掘和w e b 使用记录挖掘，这两个分支所解决的是两个不同的课题。 w 曲内容挖掘主要是处理自动筛选和分类信息、智能搜索a g e n t 、个性化w e b a g e n t s 等 太原理工大学硕士研究生学位论文 问题。w e b 使用记录挖掘处理关于网站结构方面的问题，关心的是如何从存储的w e b 访问日志中发现浏览者行为的有趣信息。下面将分别讨论这三种w e b 挖掘。 图2 - 1w e b 数据挖掘的分类 f i g u r e2 - 1t h ec l a s s i f i c a t i o no fw e bd a t am i n i n g ( 1 ) w e b 结构挖掘 w e b 结构挖掘是从人为的链接结构中获取有用知识的过程。大量的w e b 链接信息 提供了丰富的关于w e b 内容相关性、质量和结构方面的信息，为w e b 挖掘提供了一个 可以利用的重要资源。 w e b 链接结构具有特殊的特征： j 1 ) 不是每一个超链接都代表对我们寻找的认可。有些链接是为其他目的而创建的， 例如，为了导航或为了广告业务。 2 ) 基于商业或竞争的考虑，很少有w e b 页面会指向其竞争领域的权威页面。例如， 摩托若拉不会链接到其竞争对手诺基亚的w e b 页面上。 3 ) 权威页面很少明确给出特别的描述。 因此，人们提出了另外一种重要的w e b 页面，即h u b 。进而提出了利用h u b 页去找 权威页的算法h i t s ( h y p e r l i n k i n d u c e dt o p i cs e a r c h ) 。 ( 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 如的查询语言w e bl o g ， w e bo q l 等，利用启发式规则来寻找个人主页信息的a h o y 等等。采用第二种策略的方 法主要是对搜索引擎的查询结果进行进一步的处理，得到更为精确和有用的信息，属于 该类的有w e bs q l ，及对搜索引擎的返回结果进行聚类的技术等。 ( 3 ) w e b 使用记录挖掘 w e b 使用记录挖掘是指通过挖掘存储在w e b 上的访问目志，来发现有趣的信息( 用 户访问w e b 页面的模式及潜在客户信息的发现) 的过程。包括三个过程：数据预处理、 模式发现及模式分析。 对于w e b 使用记录挖掘的过程如下图： 图2 - 2w e b 使用记录挖掘流程 f i g u r e2 - 2t h ef l o wc h a ro fw e bu s a g em i n i n g w e b 服务器通常保存了对w e b 页面的访问日志w e bl o g 。它包括了请求的u r l ，发 请求的i p 地址和时间戳。而基于w e b 的电子商务服务器厂保存了大量的w e b 访问日志。 如何分析和挖掘这些数据，充分了解客户的喜好和访问模式，从而设计出满足于不同用 户群体需要的个性化网站，进而增加竞争力，是每个网站都应该密切关注的问题。 在开发w e b 使用记录挖掘的技术中，要考虑的问题如下： 1 ) 虽然w e bl o g 分析可以设想出许多潜在的应用，但重要的是此类应用的成功要依 赖于从这个巨大原始的日志数据中能够发现什么样的可靠有效的知识，以及能发现多 少。而在开始挖掘之前，仍需要经过清洗、浓缩和转换。 2 ) 基于u r l 、时间、i p 地址和w e b 页面内容信息，可以在w 曲l o g 数据库上构造 多维视图，进行多维分析，有助于发现潜在客户、用户和市场等。 9 太原理工大学硕士研究生学位论文 3 ) 可以在w e bl o g 上进行数据挖掘，找出关联模式、序列模式和w e b 访问趋势等。 通过分析和探究w e b 日志记录中的规律，可以合理建造网站及合理设计服务器； 帮助更好地组织设计w e b 主页，并改进w e b 服务器系统的性能；识别电子商务的潜在 用户，增强对最终用户的因特网信息服务的质量；帮助改进市场营销决策，如把广告放 在适当的w e b 页上或更好地理解客户的兴趣；分析用户的浏览模式，对用户的行为进 行预测提高服务质量。 2 1 3w e b 挖掘的难点 w e b 是一个巨大、分布广泛、全球性的信息服务中心，涉及经济、文化、教育、 新闻、广告、消费、娱乐、金融、保险、销售、电子商务等信息服务，内容极其丰富。 对w e b 进行有效的信息抽取和知识发现具有极大的挑战性，会面临很多具体问题，主 要有一下几点【2 0 】。 ( 1 ) 目前，对感兴趣的信息仅限于利用各种搜索引擎进行查找。尽管业界开发了很 多的搜索引擎，但其检索性能和服务质量并不令人满意。主要表现在：检索方式单一， 检索时间长、检索结果质量差、难以精确表达用户需求、无法适应用户群体的多样性； 检索召回率和精度低。 ( 2 ) w e b 页面以某种格式h t m l 呈现的半结构化数据( s e m i s t r u c t u r e dd a t a ) ，其数据 结构不规则或不完整，复杂程度远远高于普通的文本文档，其数据结构隐含、模式信息 量大、模式变化快。大量的文档无任何排列次序、无分类索引。 ( 3 ) w e b 是一个异质、分布、动态的信息源。w e b 及其数据的更新、增长速度极快， 也无固定的模式。w e b 上的信息几乎都是隐藏的、潜在的、未知的，从w e b 上发现这 些未知的信息和有用的模式，仅用传统的基于关键字的检索方式很难实现，现在的搜索 引擎尚不具备这些功能。 ( 4 ) 目前w e b 上的数据以t b 数量级计算，且在迅速地增长，能否或如何构建一个 庞大的数据仓库把w e b 所有分布和异质的数据集成在一起。但这几乎是不可能的。最 近，有些研究工作在致力于存储和集成w e b 上的所有数据。 ( 5 ) 不同的用户访问w e b 的兴趣、爱好和使用目的干差万别，面对一个非常广泛的 形形色色的用户群体，能否使用户根据自己的爱好兴趣定制网页，甚至w e bs e r v e r 能否 根据发现的用户p r o f i l e 自动为用户定制网页，从而提供个性化的信息检索和查询服务。 l o 太原理工大学硕士研究生学位论文 ( 6 ) 网络上信息储备量极大且信息内容十分丰富，但信息的利用率很低。w e b 上的 信息对用户个人而言，被使用到的只是极小的一部分，其余信息对用户来说是不感兴趣 的。 这些问题推动了如何有效且高效地发现和充分利用i n t e m e t 上资源的研究工作。万 维网的分布、动态、海量、异质、变化、开放性的特点，网页内容的半结构化特征决定 了w e b 挖掘比传统的k d d 和以关键字搜索为主的信息检索问题更为复杂和困难，很多 问题甚至是n p h a r d 问题。解决w e b 挖掘问题需要有新的数据模型、体系结构和算法等， 在理论上、方法上要有新的突破，要求有更高级的w e b 信息处理技术。 2 2 数据来源 2 2 1 网络日志的获取 数据挖掘中一个很重要的步骤就是要为挖掘算法找到合适的数据。在w e b 使用数 据挖掘中，数据最直接的来源是w e b 服务器上的w e b 曰志文件。w e b 日志文件非常明 确地记录了访问者的浏览行为，因此在w e b 使用数据挖掘中有很重要的地位。 w e b 用户访问日志分别记录在三个地方：客户端、代理服务器端和w e b 服务器端。 三个日志数据集记载了用户使用网络资源的不同模式。 ( 1 ) 代理端数据 一个w 曲代理作为客户( 浏览器) 与w e b 服务器之间的交通要道，代理端的缓存有 助于减少网页( 在客户端) 的装载时间和服务器的工作负载。代理端可以跟踪来自多个客 户访问多个服务器的请求。代理端的缓存对服务器端日志记录内容的影响取决于网站内 容的性质。若是动态生成的网页，则不受代理端缓存的影响，但若是静态网页，就可能 会受到较大的影响。 ( 2 ) 客户端数据 客户端数据可以利用远程a g e n t ( j a v aa p p l e t s 或j a v a s c r i p t s 编写而成) ，来帮助收 集客户端( 单用户，多网站) 访问情况( 记录数据) 。在客户端直接收集用户访问网站的浏览 行为，相比在服务器端间接记录用户的访问行为要准确得多。但是，利用远程a g e n t 在 客户端进行( 用户) 浏览数据的收集工作需要得到用户首肯，否则收集工作很难进行。 ( 3 ) 服务器数据 w e b 服务器日志是w e b 使用挖掘中一个重要的数据源，它清楚记录了网站用户的 太原理工大学硕士研究生学位论文 访问浏览行为。但服务器数据也有其不足：由于缓存和网络传输时间( 延迟) 的原因，服 务器日志中的信息并不十分可靠：由于h t t p 协议是一种无状态协议，因此想要跟踪单 个用户( 整个) 浏览行为往往是比较困难的。这时可以利用服务器为单个用户的( 访问) 浏 览产生相应的c o o k i e s ，从而可以帮助跟踪用户的网站访问踪迹。 服务器还可以提供内容服务器( c o n t e n ts e r v e r ) 日志，它可以提供有关用户所浏览信 息内容的有关情况。此外，服务器端也可以提供有关网站的信息，如其内容数据、结构 信息、本地数据库、网页元数据( 如文件大小和最后修改时间等) 。 本文主要利用数据挖掘相关技术对服务器端的预取技术进行研究，在目前条件下， 从客户端及代理服务器端进行数据收集还比较困难，因此在本课题中数据挖掘的数据源 主要是服务器端客户访问的日志文件。 2 2 1w e b 日志的格式 不同的系统及机器对网络日志的记载有很大的不同，最常用的w e b 服务器有 a p a c h e 和m s s 。前者有两种常用的格式c o m m o n 和c o m b i n e d 。后者m i c r o s o f ti i s 格 式、n c s a 公用格式及w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ，万维网协会) 组织规定的两种 格式存储。一种是普通日志文件格式( c o m m o nl o gf o r m a t ，c l f ) ，另一种是扩展日志文 件格式( e x t e n d e dl o gf o r m a t ，e l f ) 。一般服务器上存放的日志文件是通用日志格式，通 用日志文件格式如下所示： 2 16 3 5 11 6 9 1 一【1 9 a u g 2 0 0 0 ：1 4 ：4 7 ：3 7 一0 4 0 0 】f i g e tl t a n h t m lh t f p 1 1 ”2 0 06 8 8 日志的每一条记录代表了客户的一次请求，共有七项信息组成：第一项为客户端 地址( 客户口或代理服务器i p ) ；第二项为浏览者标识，是浏览者的唯一标识符，绝大 多数情况下为空白符“一”；第三项为浏览者身份验证信息，除非网站要求客户进行身 份验证，否则空白，对于大多数网站来说，日志中该项是空白的；第四项为请求时间； 第五项是请求类型，包括“方法资源协议”；第六项是状态代码，表明请求是否成功， 或发生了什么错误。一般而言，以“2 ”开头的状态代码表示成功，以“3 ”开头的状态 代码表示由于各种不同的原因客户请求被重定向到了其它位置，以“4 ”开头的状态代 码表示客户端存在某种错误，以“5 ”头的状态代码表示服务器遇到了某个错误；第七 项表示发送给客户端的总字节数。 对于具体的服务器，日志的格式会有些形式上的不同，本文用到的日志格式如下： 1 2 太原理工大学硕士研究生学位论文 ii ： iu ： i t ： ir ： i s ： 不同的区域用”i ”分割，第二个字段是匿名口地址，这里为了保护用户的隐私用唯 一的编号来代替唯一的地址，我们以a n o n 开头用以表明，u r l 地址在”g e t ”后面，如 图2 3 所示。 聊h y p e r r e a l o r gja n o n 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4 8 9 4 6 g e t m u s i c m a c h i n e s m a n u f a c t u r e r s k o r g p o y - 8 0 0 e x 一8 0 0 耵t p 1 1j t e x t h t m l l