基于有向图的缓存内容选取算法研究

基于有向图的缓存内容选取算法研究

web路径挖掘主要影响用户体验的背景随着互联网硬件技术的发展，网站的数据内容和数据结构的范围变得越来越大。大量的数据和访问带来了网站快速响应的巨大挑战。在海量数据中选取合适的内容同时读取并缓存,是提高网站响应速度和用户对此满意度的重要方法。而在这些数据如何选取合适的数据作为缓存内容成为关键的问题之一。其中web路径挖掘为缓存内容的选取问题给出了自己的方法,就是根据用户访问站点的结构关联度,选取用户会连续访问的相关的频繁路径数据进行缓存,减少硬盘读写次数,降低站点服务器压力,提高用户请求的响应速度。本文主要阐述的带权路径模式挖掘(WeightedPathPatternmining),是在AprioriAll算法中增加频度为权值,缓存内容的选取上不仅仅在原来AprioriAll算法中选取用户访问内容的页面结构关联度,而且增加选取内容的整体访问频度,从而提高缓存内容为用户访问页面的命中度,更好地发挥了缓存机制的作用。1网站内容记录1.1运行速度和扩基于链路的方法是当浏览器访问一个Web页时,服务器端会在响应请求页面的同时在后台取出用户可能会连续访问的Web页存入服务器的高速缓冲区,以后当用户点击下一条链接时,若所访问页面已经存在于服务器的高速缓冲区,则只需从缓冲区取出web页进行响应,提高了服务器的响应速度和并发响应能力。1.2基于频域的方法,充分利用有限资源,提高用户访问对于缓存内容的选取,目前有两种常见的解决方法:一种是系统自动记录页面中每个链接被访问的次数并按频率排序,频率越高说明被访问的可能性越大,当需要时选择频率高的页面缓存。另一种是基于历史的方法,记录用户经常访问的站点,并通过数据挖掘的方法获得用户访问频繁的路径,并只缓存这些频繁路径中的页面,从而最大程度上充分利用有限资源,提高站点的响应速度。以上两种方法中,前一种方法考虑了站点的访问频率,后一种方法考虑了用户访问站点的关联性和序列性。但两种方法没有结合考虑用户访问站点的频率性和关联性。本文介绍的加权路径模式挖掘则可以克服这个缺点。2路径模型开挖2.1缓冲页面页面之间的关系在因特网上用户一次浏览中依次访问的站点形成浏览路径,本文结合例子来说明,如图1所示:原始浏览路径为{(A,B,CD,E,D,F,D,G,A,H,I,J,K,J,L,J,I,M,I,N,I,H,O)}。路径站点的权定义为站点在浏览路径中出现的次数。可以得到结果如表1。第一种最容易想到的利用缓存页面站点的选择是按照用户浏览路径的访问频率或者次数。如表1,可以看出如果按照页面的访问次数为标准,选择缓存页面则当选择的缓存页面的数量为4时,显然为I,J,D,A或者为I,J,D,H。如当缓存页面选择数量为4时分别为I,J,D,A,页面之间没有相互的顺序关联关系。用户的访问A后,再访问B或者H时却没有缓存,没有有效地达到缓存的目的。2.2面后频繁序列提取第二种缓存选取算法思想是:选取的缓存中的页面在用户浏览路径中有着前后序列关系,一些页面为用户访问页面后的后续路径中的页面,有更高的机率被用户后续访问,从而提高缓存的效果,更好地提高网站的响应速度和减轻服务器的负担。可以利用数据挖掘的关联规则,发现用户浏览路径的频繁序列集,并缓存相关站点。从浏览路径中发现潜在的用户浏览路径的频繁序列称为路径模式挖掘(pathpatternmining)。2.3确定频繁路径(1)生成深度路径。由浏览过程中的每个站点构成的序列称为原始路径,其中每一个没有重复站点的最长访问路径,称为深度路径(deeppath)。既包括到达一个新页面的向前引用,也包括由于访问失败或未找到所需信息造成的向后引用。只有向前引用是有用的信息,因此从原始路径中删除向后引用,得到一组浏览子序列,其中每个子序列是从用户的访问起点开始的深度路径。如图1表示的原始浏览路径,可以得到深度路径为{(ABCDE),(ABCDF),(ABCDG},(AHIJK),(AHIJL),(AHIM),(AHIN),(A-HO)}。(2)从得到的深度路径中获取频繁路径(frequentpath),即在全部浏览过程出现次数超过给定阈值的序列。频繁路径的搜索从一维开始,利用迭代找到所有满足阈值的频繁路径。(3)确定频繁深度路径,即不包含在其他任何频繁深度路径中的频繁路径。一个频繁深度路径对应于Web中一条频繁出现的最深浏览路径。3频域生成算法3.1有向图深度遍历在一次浏览路径过程中,可以看到浏览的结点形成了一个特殊的有向图。特点为:可以从一个起点沿方向深度优先可以遍历所有的结点。因此生成频繁路径的过程中,可以通过一次有向图的深度优先遍历的过程找到所有的频繁路径。有向图深度遍历过程生成频繁路径算法如下:在深度优先遍历过程中,若栈顶有未被访问的邻接顶点,则邻接顶点入栈,并重复。直到遇到邻接顶点非首次访问,则记录当前栈内顶点,形成一条深度路径。此时退栈并重复,直到下一结点为首次访问,则访问下一结点,并入栈此结点。以上过程重复,直至栈为空或栈内结点未有未被访问的有向边,即遍历了所有结点,得到所有的深度路径。3.2计算模式1阶大序列寻找频繁路径与关联规则中的大项集有相似之处,它们都是满足在事务库中出现的足够次数(规定的阈值),但是频繁路径必须是连续且有顺序的,而大项集仅仅是项的组合,根据这个特点,本文运用序列模式挖掘中的大序列计算机方法AprioriAll的一个改进算法,从第一步生成的深度路径集中找到满足阈值的所有频繁路径。AprioriAll算法的过程与关联规则中的大项集搜索过程类似,也是由1阶大序列构造2阶候选序列,扫描数据库计算候选序列的支持数,得到2阶大序列,这样依次循环,直至找到所有的大序列为止。AprioriAll算法的详细过程描述如下:这里用到这样一个性质:如果A是大序列,那么A的所有子序列也必定是大序列;反之,如果一个序列的某个子序列不是大序列,那么这个序列也一定不是大序列。AprioriAll算法适用于处理这样的序列:序列中的项集有顺序,但不一定是连续出现的。但是,在本文中要处理的序列不仅仅有顺序,而且必须是连续出现的。假设Lk-1表示k-1阶大序列,Ck表示k阶候选序列。首先对Lk-1进行自连接,对于两个k-1阶大序列S、T:如果S的后k-2个项集和T的前k-2个项集相同,那么就由S和T的第k-1个项集连接,得到一个k阶候选序列,这就保证了连续性和有序性,同时生成的候选序列数也减少了,提高了算法的效率。然后,对候选序列进行消减,如果k阶候选序列A的某个Lk-1阶子序列不在Lk-1中,那么A就不可能是大序列,需要将它从候选序列集Ck中删除。消减也是一个重要的步骤,可以减少扫描数据库的次数。比如:2阶大序列为L2={(AE),(EF)},由上面的连接条件可得到C3={AEF)}。因为(AF)不在L2中,所以(AEF)不是3阶候选序列,应当删除。4加权频繁路径在这里对上文运用生成深度路径算法得到深度路径集,然后以其为对象,用改进的AprioriAll算法计算频繁路径,设阈值为2。第一次扫描深度路径集,得到1阶频繁路径。然后产生2阶候选频繁路径,第二次扫描深度路径集计算候选频繁路径的支持数,得到2阶频繁路径。接着构造3阶候选频繁路径,如此循环,直到5阶候选频繁路径为空,循环结束。计算频繁路径的执行过程和结果如图2所示。最后从得到的频繁路径中过滤掉子频繁路径,生成最终的频繁深度路径。本例最后得到的频繁深度路径为{(ABCD)(AHIJ)},详细过程不再赘述。从图2可知,如果选择四个结点作为缓存,当然会选择支持数为3的频繁路径。加权频繁路径的加权支持数定义为支持数与相应阶所有路径结点权和的积。由前文结点权定义及所求的权可以得出频繁路径(ABCD)的权的和为:2+1+1+3=7。此频繁路径的加权支持数为:3*7=21。同理可得加权频繁路径(AHIJ)的加权支持数为:2*(2+5+4+2)=22。尽管(ABCD)支持数大于(AHIJ)的支持数,但其加权支持数小于(AHIJ)的加权支持数。从表2可以看出各种算法的优点与不足,加权频繁路径算法结合依据简单访问频率和关联规则的优点,对缓存内容的选取算法做到更好的均衡。使得缓存内容命中率与有效性在整体效果有了更佳表现,即有了更好的加权支持数。加权支持数反应了结点关联的频繁程度,并且考虑频繁路径中结点的访问频率更加全面地反应了用户访问路径结点的相互和频率均衡。5带权路径挖掘算法的改进随着电子商务的高速发展,以及交友网站等用户关联性强的一些基于web2.0的大型网站的兴起和迅猛发展,未来web挖掘的一个重要应用方向将是类似大型网站系统的以用户特征为基础的各种知识的挖掘,而与用户最为密切的将会是用户路径模式挖掘。在本文提出的带权路径挖掘算法的应用过程中,其权值可以根据需要和实际参数赋为不同的意义和变量,如门户网站中的文章的正文、评论以及文字与多媒体等不同类型的信息因文件大小或客户不同响应要求而对他们分别赋有相应权值,给予客户更好的体验。本文针对挖掘对象的特性,对AprioriAll算法中生成候选序列的函数做了一定的改进,并对路径赋