（计算机软件与理论专业论文）代理服务器的网页预取研究.pdf

西华大学硕士学位论文 代理服务器的网页预取研究 计算机软件与理论专业 研究生万里春指导教师彭宏 随着网络的快速成长，使用网络的人数也急剧增加。加上多元化网络应用 的发展，造成大量数据需要通过网络来传送。虽然近几年来网络速度有了很大 的提高，但是由于接入i n t e r n e ! 的用户数量急剧增加以及w e b 服务和网络的固 有延迟，使得网络越来越拥挤，导致人们在访问w w w 时总是要忍受较长的 等待时间。如果仅仅靠通过对网络硬件设各的提高来解决网络速度问题己经变 得不符合实际，而w e b 预取作为一种最流行和最有效的减少访问延迟的手段， 已经越来越受到研究者的关注。 通过在代理服务器端提供缓存以及预取功能的方式，可以有效地降低使用 者等待传输的时间，让资源得到更有效的利用。因此如何进一步提高代理服务 器的缓存使用率及预取命中率，便成为一项重要的研究课题。 在本文中，我们研究了代理服务器的网页预取技术，目的是减少用户访问 w e b 时所感知的延迟，为用户提供个性化的预测预取服务。我们的工作主要 包括以下四个方面： 第一，对访问日志中各个数据项进行分析，通过先验知识，找出一些对访 问日志进行预处理的规则。通过这些先验知识的使用，我们将日志中对分析没 有帮助的记录过滤掉，以降低预取算法的计算复杂度。 第二，使用关联规则的方法，产生p o r t a l a w a r e 的二维热门排行榜列表。 p o r t a l a w a r e 的预取清单可以挖掘出用户跨网站的浏览行为，让产生的热门排 行榜更能够反应用户真正的浏览行为。 第三，将网页信息价值的概念应用到预取的方法中。通过对网页信息价值 的计算，将网页大小的因素也考虑进来，让产生的预取清单能够更具有代表性， 整个缓存空间的使用也更有效合理。 第四，利用层次聚类的方法，找出用户浏览行为随时间变化的区间。我们 对时间进行分段处理，对不同的时间段利用不同的预取清单进行预测，不仅可 以保持页面的新鲜度，避免预取到过时的网页，还可增加预取的命中率。 关键词：w e b 预取，先验知识，关联规则，信息价值，层次聚类 i i 西华大学硕士学位论文 s t u d y o i lw e b p a g ep r e f e t c ha tp r o x ys e r v e r c o m p u t e rs o f t w a r e & t h e o r y m d c a n d i d a t ew a nl i c h u n s u p e r v i s o rp e n gh o n g w i t ht h ef a s tg r o w t ho fn e t w o r k ，t h en u m b e r su s i n gt h en e t w o r ki n c r e a s i n g r a p i d l yt o o ，m e a n w h i l e ，t h ed e v e l o p m e n to fm u l t i l e v e ln e t w o r k sa p p l i c a t i o n a d d i t i o n a l l ym a d eag r e a td e a lo fd a t at _ i a n s p o r tt h r o u 出n e t w o r k 。a l t h o u g ht h e s p e e do fn e t w o r kh a sb e e ni m p r o v e dc o n s i d e r a b l yi nr e c e n ty e a r s ，b u tb e c a u s e m o r ea n dm o r eu s e i sj o i ni n t e r n e ta sw e l la st h ew e bs e r v i c ea n dn e t w o r kd e l a y , t h en e t w o r kb e c o m em o r et r a f f i c ，s oa st op e o p l ea l w a y ss u f f e rf i o ml o n gt i m e w a i t i n gw h e nt h e yv i s i tt h ew o r l dw i d ew e b i tw i l lf a l ls h o r to fp r a c t i c ei fw e s o l v et h ep r o b l e mo n l y d e p e n do ni m p r o v i n gt h en e t w o r kh a r d w a r e w e b p r e f e t c h i n gi so n eo ft h em o s tp o p u l a ra n de f f e c t i v es t r a t e g i e s f o rr e d u c i n gt h e p e r c e i v e da c c e s sd e l a y , s oi th a sd r a w ne x t e n s i v er e s e a r c ha u e n t i o nr e c e n t ly t h ew e bc a c h i n ga n dp r e f e t c h i n ga t p r o x ys e r v e rc a nr e d u c et h e u s e r s p e r c e i v e dl a t e n c y , i tm a k ee f f e c t i v eu s e o fn e t w o r kr e s o u r c ea sw e l l i th a sb e c o m e o n eo ft h ei m p o r t a n tt a s kh o ww ec a ng e tb e t t e rc a c h eu t i l i z i n gr a t ea n dh i tr a t ea t p r o x ys e r v e r i nt h i st h e s i s ，w es t u d yt h ew e b p r e f e t c h i n gt e c h n o l o g ya tp r o x ys e r v e r i t s p u r p o s ei s t or e d u c et h ew e bl a t e n c ya n dp r o v i d ew e bp r e f e t c h i n gs e r v i c eo f i n d i v i d u a l i z a t i o nf o ru s e r s o u rw o r ki sm a i n l yi nt h ef o l l o w i n gf o u ra s p e c t s ： f i r s t l y , w ea n a l y z ea l ld a t ai t e m si nt h ea c c e s sl o gi no r d e rt of i n ds o m er u l e s w h e nw ep r e p r o c e s s i n gt h ea c c e s sl o gb yt r a n s c e n d e n t a lk n o w l e d g e t h r o u g ht h i s w a y , w ec a nf i l t e rt h el o gr e c o r dw h i c hh e l p l e s st oa n a l y z e ，a n dt h ec a l c u l a t i n g i i i 西华大学硕士学位论文 c o m p l e x i t yo fp r e f e t c h i n ga l g o r i t h mr e d u c ea c c o r d i n g l y s e c o n d l y , w ep r o d u c et w od i m e n s i o n sp o r t a l - a w a r eh o tr a n kl i s tb yu s i n g a s s o c i a t i o nr u l e s t h ep o r t a l - a w a r ep r e f e t c h i n gl i s tc a nm i n eu s e r s a c c e s sb e h a v i o r i nw e bs i t e ，s ot h a tt h eh o tr a n kl i s tc a l lr e f l e c tu s e l s r e a la c c e s sb e h a v i o rm o r e e s s e n t i a l l y t h i r d l y , t h ep a g ei n f o r m a t i o nv a l u ec o n c e p th a sb e e nu s e di np r e f e t c h i n g m e t h o d s w ec o n s i d e rt h ef a c t o ro fp a g es i z e ，b yc a l c u l a t i n gt h ev a l u eo fp a g e i n f o r m a t i o n ，t h ep r e f e t c h i n gl i s tb e c o m em o r er e p r e s e n t a t i v e ，a n dt h ec a c h i n gs p a c e c a nb eu s e dm o r er e a s o n a b l e f o u r t h l y , t h eh i e r a r c h i c a lc l u s t e r i n gm e t h o dh a sb e e nu s e dt of i n d o u tt h e t i m e b a s e du s e r s a c c e s sb e h a v i o r w et a k ew e bt e m p o r a l i t yi n t oa c c o u n tf o r c o n s t r u c t i n gp r e f e t c h i n gl i s t ，b a s e do i lw h i c hw ep r e d i c tt h eu s e r s b e h a v i o r i n a d d i t i o nt om a i n t a i nt h ew e bp a g ef r e s h ，t h i sm e t h o da v o i dp r c f c t c h i n go u t d a t e d p a g ea n di m p r o v ec a c h eh i tr a t ea sw e l l k e y w o r d s ：w e bp r e f e t c h ，t r a n s c e n d e n t a lk n o w l e d g e ，a s s o c i a t i o n r u l e ， i n f o r m a t i o nv a l u e ，h i e r a r c h i c a lc l u s t e r i n g i v 西华大学硕士论文 1 绪论 1 1 研究背景 由于近年来i n t e m e t 的普及以及电子商务的发展，越来越多的人利用网络来 获得他们所需要的信息。近年来，虽然网络速度得到了很大的提高，但是，由 于i n t e m e t 的用户数量剧增以及w w w ( w o r l dw i d ew e b ) 信息量的爆炸式增长， 使得网络越来越拥挤，用户的服务质量( q o s ) 得不到很好的保证，用户在访问 网页之前往往要忍受较长的等待时间。在目前带宽发展速度跟不上数字内容快 速发展的情况之下，网络交通拥挤的情况将会越来越严重。如何能够有效地提 高网络的服务质量，让网络资源的使用更有效率，以减少网络堵塞的情况，便 成为一项重要议题。 事实上，w e b 延迟问题，并非只受到用户的关心，i n t e m e t 的运营商特别是 i c p ( i n t e r n e tc o n t e n tp r o v i d e r ) 也迫切地要求减少用户的访问延迟，提高服务质 量。有一个被广泛引用的称为“八秒钟规则”的统计 3 5 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 ) 技术。 所谓缓存技术是将经常被浏览或不久前被浏览的网页文档，复制一份在代 理服务器的缓存区中，让网页文档的存取更有效率。它的运行机制如下图1 1 所 示。当用户第一次向远端请求网页时，代理服务器的缓存区并没有所请求的页 面，所以通过代理服务器向远程服务器提出请求，获得页面后才能将文件传给 西华大学硕士论文 用户，并复制一份在缓存区中。当有用户再次请求相同文件时，便可直接从代 理服务器的缓存区来提供而不用连接到远端，从而分担站点服务器的负担。研 究表明，缓存的命中率可达到3 0 5 0 1 9 1 ，它对节省网络带宽、减少用户感知 的延迟时间是显而易见的。 耖兰二一禽 ( 1 ) 实线代表代理服务器缓存中没有用户请求的网页时，网页的读取路径 ( 2 ) 虚线代表代理服务器缓存中有用户请求的网页时网页的读取路径 g r a p h l 1t h ec o n c e p to fc a c h em e c h a n i s m 图1 1 缓存机制概念图 使用缓存技术虽然可以降低延迟并提高访问的速度，但缓存仅保留过去浏 览过的网页，并未进一步分析用户之后的浏览行为，因此当用户访问新的w e b 站点或没有被缓存的内容时，其响应性能依然得不到改善。为了进一步减少网 络的延迟时问，提高网络性能和缓存的命中率，研究者们又提出了w e b 预取技 术。预取技术是针对用户过去的浏览记录做分析，建立网页的预取模型，将用 户未来可能需要的网页内容预先下载到缓存中，当用户请求该网页时，便能直 接由代理服务器的缓存区来提供，可降低用户的等待时间并提高缓存的命中率。 预取的概念可由图1 2 表示： 2 西华大学硕士论文 ! 婴重鲞- - - - - - - - - - - - 一 哪响应 c a c h e ( 1 ) 实线代表代理服务器一般缓存的运行机制 ( 2 ) 虚线代表代理服务器的预取机制 g r a p h l 2t h ec o n c e p to fp r e f e t c hm e c h a n i s m 图1 2 预取机制概念图 1 2w e b 代理与缓存 w e b 预取是建立在w e b 缓存基础之上的，所以要研究t w e b 预取，就必须 对w e b 组件和w e b 缓存有深入透彻的了解。 w e b 消息最初是在用户和原始服务器之间直接传输的，它是传统的客户机 n 务器通信模式，在客户机与服务器之间的路径上没有中间媒体。但随着w e b 的迅速发展，代理服务器( p r o x y ) 作为一种中间媒体，己逐渐成为i n t e m e t 不可 分割的一个基础构件。即一个集团、一个单位或一个局域网内的用户，通过代 理服务器作为访问i n t e m e t 的中转，代理服务器通常放在防火墙内，并且常常 与防火墙放在同一台机器上。这样，当一个用户向服务器发起请求时，该请求 被首先送到代理服务器，代理服务器分析该请求，假如代理服务器配有缓存， 并且代理服务器的缓存中有该请求数据，代理服务器就将缓存中的数据直接发 送给用户，对用户请求的响应也就到此为止；否则，代理服务器将用户的请求 转发给服务器或下一级代理服务器，当收到响应后，代理服务器再将响应的数 3 曲华人学硕士论文 据传送给用户，同时在自己的缓存中保存一份该数据的拷贝。这样，当再有用 户请求相同的数据时，代理服务器就可以直接传送给用户，而不必再向该服务 器发起请求。很明显，当用户距离代理服务器比较近时，不仅用户感知的网络 延迟大大减少，而且也避免了冗余通信，节省了网络带宽。 严格来讲，w e b 代理与w e b 缓存是两种不同的技术，常规的代理只是转发 请求和响应，并不一定要求配备缓存。然而，由于目前的w e b 代理总是配备了 缓存，除了浏览器端的缓存外，w e b 缓存的使用总是与w e b 代理相结合，以至 于许多人都将它们视为同一实体。 w e b 代理或缓存有三种工作方式，即正向代理( f o r w a r dp r o x y ) 、透明代明 ( t r a n s p a r e n tp r o x y ) 和反向代理( r e v e r s ep r o x y ) ，其中，我们平常所说的w e b 服务器缓存实际上就是指反向代理上的缓存，它在本质上也是一种代理服务器 缓存，只是被设定为一种特定的工作方式。 1 3 缓存一致性 w e b 预取是建立在缓存基础之上的，w e b 预取可以提高缓存的命中率，那 么，通过增加缓存的容量，将高速缓存设置得足够大，使它缓存更多的数据， 是否也可以达到这一目的昵? 如果这样，不是可以取消预取工作，或者至少降 低对预取的要求吗? 事实上并非如此简单。 缓存中保存的是原始服务器网页内容的拷贝，但是服务器中的网页内容却 并非静止不变的，它始终处于不断的更新之中。换句话说，从上一次缓存开始， 缓存下来的内容有可能已经被修改了。假定我们有一台配有巨大容量的代理服 务器，有一用户在几天前访问了某个网页，且此后没有其它用户访问更新过该 网页，那么缓存中保存的是该网页几天前的内容，如果我们现在发出对该网页 的请求，代理服务器返回的将是一个不再“新鲜”的内容，显然这并非我们所 期望的。要保持缓存中的内容始终是原始服务器的最新备份，并不是一件容易 的事，因为原始服务器在网页内容发生改变时，并没有什么机制来通知代理服 务器，缓存一致性( c a c h ec o h e r e n c e ) 就是解决这一问题的。 4 西华大学硕士论文 对于计算机各种形式的缓存，缓存一致性都是一个被深入研究的问题。对 于w e b 缓存，在过去几年中，已经有多种缓存一致性算法被提出。例如， h t r p 1 1 协议提供了几种方法来维护缓存的一致性。如果原始服务器为资源设 置了指定的过期时间，则提供缓存服务的代理服务器必须遵守到期时间。唯一 的例外是在客户的请求上加入c a c h e c o n t r o l ：o n l y - i f - c a c h e d 限制，这些限制强 迫代理返回一个未经原始服务器重检验的响应。如果原始服务器没有设定到期 时间，代理可以使用试探到期时间。试探到期经常与一致性检验联系在一起。 在w e b 上最常用的方法是用i f - m o d i f i e d s i n c e 请求标头发送g e t 或h e a d 请 求。i f - m o d i f i e d s i n c e 标头传送资源上次修改的时间戳，该时间戳由原始服务 器提供。原始服务器会将i f - m o d i f i e d s i n c e 标头中指定的时间戳与资源的最后 一次修改时间进行比较，如果资源没有改变，服务器将仅返回3 0 4n o tm o d i f i e d 响应，而无响应主体；如果资源己经更新，服务器会返回一个恰当的状态码( 通 常是2 0 0o 目，并附上完整的响应主体。对于不经常改变的资源，这有助于减 少不必要的数据传输，缩短用户所感知的延迟。 维护w e b 缓存一致性的策略可分为两类：强一致性策略和弱一致性策略。 如果在每次缓存命中发生时，缓存代理服务器都发送一个重校验的请求，那么 这种策略就叫作强一致性：如果缓存利用试探的方法来确定缓存响应是否是新 鲜的，而不是每次缓存命中发生时都询问原始服务器，那么这样的策略就叫作 弱一致性。 弱一致性策略又可分为基于租用的试探和基于时间的试探两种方法。对于 基于租用的方法，由服务器为每个响应设定一个租用期( 一个固定的时间量) ， 代理服务器缓存在其租用期内存储响应而不必重校验，如果在租用期内缓存的 资源发生改变，服务器就会通知缓存。这种方法把系统开销转移到了服务器上， 而且要求缓存和服务器的合作，服务器必须跟踪所有它许诺通知的缓存代理， 实现起来非常困难，所以，这种算法只是在文献中被广泛讨论，但在实际的产 品和系统中并没有得到具体的应用。对于基于时间的方法，代理服务器为缓存 中的每个响应设置一个1 几( t i m e t o 1 i v e 生存期) 时间，当时间间隔过去后，就 认为响应己经失效；而在1 阻内，缓存不对响应进行重校验。基于1 t i l 的方 法使用起来非常灵活，对不同的响应可设置不同的t r l 值，这种方法目前得到 5 西华大学硕士论文 了广泛应用。 1 4 研究目的及方法 尽管w e b 代理和缓存的使用，能够有效地减少用户的访问延迟，并减轻网 络和原始服务器的负载，但是w e b 代理和缓存在管理、通信等方面的复杂性， 以及高速缓存一致性的维护，又限制了其性能的进一步提高。目前，虽然存储 空间的价格越来越低，为提供超大规模的w e b 高速缓存提供了条件，但单纯依 靠增大缓存的体积，除了增加管理成本外，并不能持续地提升缓存的命中率， 这就为w e b 预取技术提供了广阔的生存空间。 w e b 预取，作为提升w e b 缓存命中率的一种手段，己经越来越显示出它的 重要性，也越来越引起研究者和1 1 r 厂商的重视。而代理服务器作为i n t e m e t 基础 构件的中间层，本身就具备了减少用户访问延迟的特性，在代理服务器上实旆 w e b 预取，无疑会取得更佳的效果。但是随着网络上信息的急剧增加，访问日 志( a c c e s sl o g ) 中的记录也呈倍数成长，如何从这么多的浏览记录中找出重要 的信息，便是一项重大的考验，尤其是代理服务器的预取，更需要一个精确的 预取模型才行。而数据挖掘( d a t am i n i n g ) 的概念正好是由庞大的数据中，找出 有价值的信息，因此我们便想将这方面的技术，应用到预取技术中。 本文首先对访问日志中的噪声数据进行处理，我们分析各数据项的特征后， 提出一些先验知识，来帮助分析用户的浏览记录，找出一些可以过滤掉这些噪 声数据的规则，以减少运算的复杂度及错误的预测：接下来我们使用关联规则， 找出用户热门的浏览序列作为预取的参考，让预取模型可以更精确的预测用户 可能的浏览行为；我们还配合网页信息价值使用，以网页信息价值作为计算网 页热门程度的依据，让代理服务器所预取的网页更具价值；最后利用聚类的方 法，分析出一天当中用户不同时间段的浏览习性，以便代理服务器根据时段的 不同来提供不同的预取策略，保持信息的新鲜程度。希望通过这些方法的提出， 产生更精确的预取模型，让代理服务器可以有效地提高服务质量。 6 西华大学硕士论文 1 5 国内外研究现状 现有的网页预取技术按照实施的位置，可分为以下三种：服务器端、代理 服务器端和客户端。其中，基于服务器端的预取方法多数建立在用户访问模式 中时序关系的基础上。也就是说，如果用户的访问模式记录表明，页面a 随着 页面b 被访问也被访问的概率很大，一旦用户访问页面b ，则可预取页面a 。 a z e r f l 】提出基于概率模型的预取方法。根据服务器l o g 数据，服务器计算 出在一定时间间隔内，网页间被连续访问的概率，并建立条件概率矩阵。以此， 服务器预测用户的访问请求。s a r u k k a i 2 j 运用马尔可夫链进行访问路径分析和链 接预测。在此模型中，用户访问的网页集作为状态集。根据用户访问记录，计 算出网页问的转移概率，作为预测依据。 s c h e c h t e r 等人【3 】构造用户访问路径树，采用最长匹配方法，寻找与当前用 户访问路径匹配的历史路径，以此预测用户接下来的访问请求。徐宝文等人【2 9 】 提出一种基于数据挖掘的预取模型。模型利用客户端浏览器缓冲区数据，挖掘 其中蕴含的兴趣关联规则，以此预测用户可能选择的链接。在此模型中，用户 兴趣表现为对词条的兴趣，兴趣关联规则表示从一个词条转向其他词条的可能 性。利用兴趣关联规则，结合用户当前访问的页面的轨迹和用户访问的当前页 面，预测用户可能访问的链接。 x uc h e n g z h o n g 等人陋j 引入神经网络实现基于语义的网页预取。通过抽取 网页超链描述文字信息中的关键词作为神经网络的输入，神经网络输出结果作 为预取依据。用户浏览路径途径的页面作为训练样本反馈给神经网络进行学习。 由于关键词的多义性会影响预取的准确性，模型对预取网页的范围采取分类处 理，不同类别构造不同的预取器。 朱培栋等人【6 】提出提炼用户会话特征，按语义对用户会话进行分类。在回 应用户访问请求时，服务器计算当前用户访问路径与各类别中心的距离，确定 会话所属的类别。根据会话所属类别的共同特征，预测用户可能访问的文档， 一次性地预送到客户端。 x u h u a n q i n g 等人【7 】提出了一种基于隐马尔可夫模型的网页预取方法，该 方法借助隐马尔可夫模型，挖掘蕴涵在用户访问路径中的信息需求概念，以此 西华大学硕士论文 进行预取页面的评价，最终实现基于语义的网页预取。 1 6 论文组织结构 本章本章从w e b 预取的背景入手，分析了w e b 代理与缓存技术的局限性， 提出了我们研究的方法，并大致了解了国内外研究现状。其后续各章节的内容 安排如下： 第二章回顾预取技术的相关研究，包括现行代理服务器的预取方法及数据 挖掘的各种技术。 第三章介绍本篇论文所提出访问日志的预处理，以及利用数据挖掘来强化 用户浏览模式的p o r t a l a w a r e 预取方法。 第四章介绍网页信息价值的概念，并研究利用网页信息价值以及利用聚类 方法分析用户浏览的时间趋势来进行预取的方法。 第五章利用实验设计的方式来验证本文提出的方法是否有效。 最后，是结论及研究贡献。对代理服务器端的网页预取作一个简单的总结， 并提出未来研究的方向。 西华大学硕士论文 2 w e b 预取技术研究 2 1 引言 w e b 预取的基本依据是，在使用者发出的2 次h r r r p 请求之间，常常有一 段空闲时间，称为使用者思考时间。这段空闲时间的长度可以从几秒钟到几分 钟。预取就是利用这段空闲时间提前把使用者不久将要访问的网页下载，并存 放到缓存中，以减少实际访问时的等待时间。其基本思想是将用户不久可能访 问的某些页面，在用户还没有请求时就取到用户的缓存中。当用户请求了预取 页面中的某个页面时，由于该页面己经在本地的缓存中，因此能够直接从本地 读取，从而减少了用户等待时间。预取方法利用了网络的相对空闲时间，是缓 存机制的有效补充手段。如果预取足够准确，则缓存的性能将得到明显改进。 我们知道，w e b 预取是以增加网络流量和w e b 组件的负载为代价的，一方 面，执行预取算法要占用网络原有的资源；另一方面，预取的内容并不能保证 总是正确的，总有一部分用户所不需要的冗余信息；此外，为了保证预取的性 能，可能还需要在网络上传输一些除预取内容之外的其它附加信息。因此，如 果预取算法的性能太差，不仅不能优化网络性能，减少用户感知的网络延迟， 反而会加重网络负担，使用户感知的网络延迟增大。要保证预取的性能，除设 计高效的预取算法外，还必须尽量提高预取的准确性，减少冗余信息和附加信 息的传输。这实际上是一个矛盾的统一体，往往需要设计者在各个问题之间进 行平衡折衷。w e b 预取的应用主要取决于性能上的收获是否大于代价。 2 2 预取方法 w e b 预取的关键在于所使用的预测算法，而预测算法的信息来源主要有两 个：访问历史的统计信息或者是来自于被访问的对象本身( 例如h t m l 页面中 的超链接) 。根据w e b 预取时所采用的预测算法，可将w e b 预取划分为四类： 9 西华大学硕士论文 通过目标链接预取、通过访问模式预取、通过“热点”预取和其它的预取方法。 ( 1 ) 通过目标链接预取：它是按照网页的超链接预取，它对每个被访问的 h t m l 页面，从中提取超链接，然后按照一定的规则( 如选择文本，图片等等) ， 预取这些超链接指向的所有网页或部分网页。它是基于这样的一个假定，即用 户浏览网页时总是按照网页上的超链接进行，当前网页所指向的链接，更可能 是用户下一个要请求的对象。但是，如果当前网页中的超链接数太多时，往往 难以决定应该预取哪些网页更合适。这种方法没有考虑用户个人特定的访问行 为，其有效性依赖于用户的访问习惯和w e b 页面的组织，预取时所得到的冗余 信息也很大，但实现起来比较简单。 ( 2 ) 通过用户的访问模式预取：指的是通过收集用户过去的访问行为，从 中找出用户的访问模式，在此基础上建立预测预取模型，指导下一步的预取工 作。这种方法考虑到了用户特定的访问行为，故可实现较高的预取准确率，取 得更好的整体性能。这里，对用户访问行为的收集是基础，在系统中建立专门 的机制来收集用户的访问行为当然是可行的，但是在代理服务器和服务器端， 当用户的访问数量巨大时，这种直接收集的方法又变得难以操作。幸运的是， w e b 日志对用户的每一个访问都进行了记录，因此通过分析w e b 访问日志来获 取用户的访问模式，以此来建立预取模型就成为这种方法的通用范例。 ( 3 ) 通过“热点”预取：它是按照过去访问的历史信息或通过一定的规则， 推算出哪些网页是“热点”，即最流行或最受欢迎的网页，然后把它们优先预取 到缓存中。例如，按照网页的级别预取和按照网页的热门程度预取就是这样的 方法。 按照网页级别预取，是指为每个网页计算出一个对应的级别，预取时优先 预取级别高的网页。网页级别( p a g er a n k ) ，本来是g o o g l e 创始人l a r r yp a g e 和s e r g e yb r i n 在斯坦福大学开发出的一套用于网页评级的系统，它是所有 g o o g l e 网络搜索工具的基础。网页级别有效地利用了w e b 所拥有的庞大链接 构造的特性，它是基于“从许多优质的网页链接过来的网页，必定还是优质网 页”的回归关系来判定所有网页的重要性。在w e b 预取中，可以采用与g o o g l e 网页评级相同或不同的方法，给已经访问或可能访问的每个网页评定一个级别， 然后按照每个网页的级别来决定是否预取它。例如，在按照当前网页的超链接 西华大学硕士论文 进行预取时，可以仅预取满足指定级别的那些网页。 按照网页的热门程度预取，也是一种通过“热点”预取的方法。它对用户 以前访问过的网页进行统计分析( 可以通过日志，也可在预取模型中直接计算) ， 然后按照用户访问量的大小，给每个网页赋予不同的权值，访问量大的网页给 予较高的权值，访问量低的网页则得到一个较小的权值。在进行预取时，优先 预取权值较大的网页。 ( 4 ) 其它预取方法：除上述预取方法外，还有一些其它的方法，如按照目 录预取的方法和混合式预取方法等。 按照目录预取，是指预取那些与当前请求页在同一目录或相近目录下的文 件或链接，它假定网站的构建者总是把内容相关的网页放在同一个目录下，而 用户在一次浏览任务中又总是浏览相关的内容。这种方法要求对网站的结构组 织非常清楚，显然，它只适用于w e b 服务器端的预取，而不适用于浏览器端或 代理服务器端的预取。 混合式预取是指综合使用上面的各种预取方法。既可以同时使用上面的方 法，也可将其中的几个方法结合起来，或者可以根据不同的要求或不同的时间， 分别使用不同的预取方法。 下面我们将详细介绍两个较具代表性的代理服务器端预取算法：a c c e s s t r e e 算法嘲以及d o m a i n t o p 算法p ”。 2 2 1a c c e s st r e e 算法 a c c e s st r e e 利用多元树来储存数据，将每个用户的浏览记录分别建立成一 颗访问路径树，其根结点( r o o t ) 不储存任何数据，之后将浏览的网页记录依序 加入到访问路径树的子结点上。此算法执行程序分为两大步骤：第一步是利用 路径发现算法来建立访问路径树；第二步是利用产生的访问路径树来预测未来 将被访问的网页，下面说明这两个步骤的执行过程： ( 1 ) 建立访问路径树：a c c e s st r e e 利用路径发现算法来建立访问路径树。 算法设定一个阈值t 每个网页视为长度1 的路径，依序加入到访问路径树当 中，当长度为n 的路径出现次数超过t 时，就会将长度为n + l 路径加入访问路 径树，通过这样的步骤来产生每个用户的访问路径树。我们举个例子来说明会 西华大学硕士论文 比较清楚，假设用户的网页浏览序列为： d ，c ，e ，a ，b ，d ，c ，a ) ，闽值 t = 2 ，则算法首先按浏览序列次序将 d ，c ，e ，a ，b 加入访问路径树第一层， 之后检查到d 时发现d 出现两次，便加入长度2 的路径d c ，之后检查到c ， 发现d c 出现两次，便加入长度3 的路径d c e 跟d c a ，之后检查到a 发现a 出现两次，便加入长度2 的路径a b ，检查完整个浏览序列后，完成访问路径 树的建立( 图2 1 ) 。在访问路径树的子节点代表网页，而路径代表用户访问网页 的顺序。 g r a p h 2 1b u i l da c c e s s1 1 e e 图2 1 建立访问路径树 ( 2 ) 利用访问路径树预测未来网页：在访问路径树建立完成后，便可预测用 户下一步的浏览行为。假设用户的访问路径树如图2 1 ，且用户目前浏览序列为 e d c ，经过对比我们可以发现访问路径树中符合浏览序列的最长路径为d c ， 因此我们可以预测用户下一步的请求是a 或e ，然后进行预取操作，把网页a 及 e 预先读取过来。 a c c e s st r e e 对每个用户建立一棵访问路径树作为预测的依据，优点在于预 测的正确率较高，且算法只选择最长路径作为预测结果，预测出的节点数比较 1 2 西华大学硕士论文 少。但是缺点在于目前情况下无法根据访问日志中的数据明确区分用户，而且 针对每个用户建立访问路径树的话需要相当大的存储空间，代理服务器在进行 预测时计算也相当复杂，会使得代理服务器的整体性能降低。 2 2 2d o m a i n - t o p 算法 鉴于a c c e s st r e e 算法的计算复杂，并且要占用较大的存储空间，3 1 1 提出 r d o m a i n t o p 算法，它利用较为简单的计算方式来减轻服务器的负担，而且进 一步对网页的内容信息做分析，将访问日志中网站的信息作为重点考虑对象。 d o m a i n t o p 算法的思想方法是：用户会根据本身的兴趣，来选择特定领域 的网站进行浏览，例如每天上各大新闻网看新闻，或者上证券网看股票行情等。 而浏览同一个领域的用户，其浏览的网页相似性就比较大，如果我们能够针对 目前最热门的领域及热门领域中的网页进行计算，便可提供预取的依据。 d o m a i n t o p 根据代理服务器的访问日志，计算出最受用户欢迎的网站 ( t o p d o m a i n ) 及网站中最受欢迎的网页( t o p d o c u m e n t s ) ，并利用等级列表 ( r a n k - l i s t ) 的方式记录热门排行榜的信息，作为预取的依据。根据对许多用户 浏览行为的分析发现，一般用户每天浏览的网站约为2 0 个，因此算法设定热门 网站的数目为2 0 ，热门网页的数目为8 ，d o m a i n t o p 算法每天计算出一个二维 的热门排行榜作为预取模型参考的依据( 如下图2 2 ) 。 西华大学硕士论文 g r a p h 2 2l a n kl i s to fd o m a i n - t o pa l g o r i t h m 图2 2d o m a i n - t o p 算法所使用的排行榜示意图 t o pd o m a i n t o p d o c u m e n t s d o m a i n t o p 算法的优点，在于考虑了网页内容中网站的信息，让整个预测 更加精确，而且使用热门排行榜作为预测，对代理服务器不会造成沉重的负担， 使用上也仅需在代理服务器端加入预测模块即可，属于轻量级的设计。 不过我们观察d o m a i n t o p 所计算出来的热门网站中，几乎都是门户( p o r t a l ) 网站，我们认为p o r t a l 的性质虽然具有d o m a i n 内部延伸的特性，但是也包含 许多跨d o m a i n 的浏览行为，因此在分析上采取d o m a i n t o p 的方式不一定能够 有效的进行预测。而且d o m a i n - t o p 没有考虑用户浏览趋势随时间变化的情况， 无法根据时间变化趋势有弹性地提供适当的预取机制。本文针对上述两个缺点 加以该进，尝试提出一个p o r t a l a w a r e 的预取算法以及一个根据时间段来动态 1 4 西华大学硕士论文 提供预取的算法，希望能够提供更好的预测效果。 2 1 3 数据挖掘概述 数据挖掘( d a t a m i n i n g ) 目前相当热门的研究领域，主要探讨如何在大量数 据中，发掘出未知且有用的信息，以提供决策人员参考。数据挖掘的对象不仅 是数据库，也可以是文件系统或其他任何组织在一起的数据集合，因此我们将 数据挖掘应用到数据量也相当大的预取分析上，肯定会有不错的效果。本节将 探讨数据挖掘技术中与本文相关的三种方法：关联规则方法( a s s o c i a t i o nr u l e ) ， 聚类方法( c l u s t e r i n g ) ，w e b 挖掘( w e bm i n i n g ) 。各小节中我们将会介绍各种目 前常见的数据挖掘技术以及这些技术如何应用在代理服务器的预取上，以协助 研究模型的建立。 2 3 1 关联规则方法 关联规则是最常见的数据挖掘技术，因为它的概念最浅显易懂。关联规则 主要是希望从庞大的数据中挖掘出有价值描述数据项之间相互联系的有关知 识，之后应用这些关联规则来获取利润。a g r a w a l 等学者提出关联规则m 1 1 3 7 1 ， 最初是应用在超级市场内顾客会同时购买哪些商品。根据消费者每次购买的商 品项目记录，通过关联规则来分析消费者的购物习惯，之后决策者就可以利用 产生的关联规则了解到商品被一起购买的概率有多少，对于促销的举办，商品 的摆设都有很大帮助，进而增加交易机会及顾客满意度，并获取利润。以下关 联规则的说明是以w e b 挖掘为出发点，不同于传统以超级市场的模式来说明是 为了更明白地表示w e b 挖掘的程序。 令p = 只，最，p m 为网站内所有网页的集合，而每一用户会话s ；为p 的子集合，用户会话集合即为d = u s ；。关联规则表示法为x y ，其中x p 、 y 尸，且x n y = 中。在用户会话集合d 中，x 与y 同时出现的概率为s ， 则x y 的支持度为s ；而在x 出现的条件下，y 也出现的概率为c ，则 z l ，信任度为c 。另外，对于一规则z l ，x 即为规则之前件 西华大学硕士论文 ( a n t e c e d e n t ) ，y 为规则之后件( c o n s e q u e n t ) 。 关联规则算法中，最为著名的就是a g r a w a l 等学者在1 9 9 4 年所提出的a p r i o r i 算法，而许多算法也是在此基础上的改进。此算法是由单一项集开始为搜索起 点，然后利用一个层次顺序搜索的循环方法来完成频繁项集的挖掘工作。算法 推导，主要包含两大步骤： ( 1 ) 根据数据库的交易项目中找出所有的频繁项集。 ( 2 ) 利用步骤( 1 ) 所得的频繁项集，推导出所有的关联规则。 在步骤( 1 ) 中，先获得出现频率较高的频繁1 一项集，也就是超过最小支持 度闽值的项目集合，在统计学上，出现机率较高的项目较具决策参考的价值， 因此过滤掉出现机率较低的项目。在寻找频繁项集的过程中，必须重复的搜索 数据库，并利用连接和删除两个步骤产生新的频繁k 一项集。在步骤( 2 ) 中，利 用最小信任度的闽值来判断关联规则是否有意义，大于最小信任度的关联规则 才会被列入考虑范围。 此算法的优点是概念相当简单，而且可以减少非频繁项集的产生，并节省 c p u 的计算时间；但缺点为需要多次搜索数据库，尤其当数据库相当庞大且要 找的频繁项集长度较长时，会耗费相当多的时间，导致效率降低。许多研究以 此算法为基础，针对不同的应用而进行小幅度的改变，本文也是以此算法为基 础，将关联规则应用在代理服务器的预取上。 关联规则应用在代理服务器的预取上，可用来找出哪些网页记录是经常一 起出现的。通过数据清洗去掉了数据中的噪声，纠正了不一致，在转为一个 t r a n s a c t i o n s 的格式后，便可以计算出经常一起出现的