一种多markov链预测模型的web缓存替换算法.docxVIP

一种多markov链预测模型的web缓存替换算法 1 多模型优化算法 由于用户数量的急剧增加和当前网络速度的双重限制，人们在接收网络信息时往往害怕长期等待。web缓存技术允许用户访问的对象减少网络连接量，改善响应时间，这是一个简单有效的解决方案。 缓存的性能很大程度上依赖于缓存替换算法, 虽然经典算法使Web缓存的性能得到了一定程度的提高, 但由于缺乏预测机制缓存的性能作用有限.文献中通过研究社交网站 (SNS) 中用户的访问行为模型, 提出了具有预测机制、面向SNS用户的缓存替换算法, 但是算法只面向SNS用户无法适应通用的网络环境中.文献中利用PPM预测模型根据上下文关系和序列匹配得到预测对象集, 该模型在预测精度与空间复杂度间难以达到平衡.文献中将预处理后会话得到的序列构建访问模式树, 并根据最小支持度进一步建立频繁访问模式树, 该方法没有考虑各个用户浏览过程中的差异性.目前还没有一种可以适应任意网络环境表现出较好性能的替换算法.替换算法的优劣衡量通过多个性能标准综合评估, 好的算法需要在多个性能标准间取得平衡. 文献中使用Markov链模型描述Web中用户的浏览特征, 进而对用户的访问进行预测, 该类方法取得了较高的预测准确率.针对已有算法的缺陷, 本文充分考虑Web中各个用户浏览过程的差异性, 将具有相同或相近浏览特征的用户用同一个模型描述, 建立多Markov链模型, 利用该模型对用户的访问对象进行预测, 使替换算法保留将要访问的对象.在GDSF算法的基础上引入平均间隔时间, 避免缓存保留大量不再具有存储价值的对象, 并将新算法命名为PGDSF-AI (Prediction Greedy Dual Size Frequency-Average Interval) 算法.通过轨迹实验表明, PGDSF-AI算法的多个性能指标取得了较好的效果. 2 存储的状态序列 缓存替换问题可以描述如下:假设O是有限Web访问对象数据集, 对任意请求对象d∈O, 有相应的对象大小为sd和取回代价cd.假定缓存总容量为C, 当前请求序列R = (R1, R2, …, Rn) 导致缓存的一个状态序列 (S1,S2, …, Sn) , 已使用的缓存容量为Cused, 对任意的Sk(k=1, 2, …, n) 有 式中, Ek是移除缓存的对象的集合, 且, 缓存的所有状态的迁移均满足式 (1) . 缓存替换算法就是在所有满足上式的状态序列中, 找出一个状态序列使目标函数的数值最小.通常情况下使用一个目标函数衡量缓存中对象的价值, 选择价值最小的对象从缓存中替换出去. 3 多因素链预测模型 3.1 u3000sqp的生成 多Markov链模型根据Web中各个用户浏览过程表现的差异性和相似性, 将Web上所有的用户分为多个类别, 用四元组表示为:< X, K, P (C) , MC >.其中, X = {x1, x2, …, xn}是一个离散随机变量, 每个xi为一个网页, 称为模型的一个状态;K表示用户类别的数目;C = {c1, c2, …, ck}表示用户的类别, 其分布函数P (C) 表示不同类别用户的概率分布;MC = {mc1, mc2, …, mck}为类Markov链的集合, mck是描述类别为ck的用户浏览特征的Markov链, 称为类Markov链, 其概率转移矩阵Ak和初始状态分布Bk分别表示为 式中, pku3000ij表示从状态Xi到状态Xj的转移概率, 即属于ck类别的用户访问页面xi后接下来访问页面xj的概率;pki表示状态Xi的初始状态概率. 3.2 概率转移矩阵ak 将用户的访问历史页面以时间顺序排列, 获得该用户的浏览序列.设有学习数据D = {d1, d2, …, dm}是m个用户的浏览序列, 第k类用户有mk个浏览序列.利用最大似然估计计算用户的类别C的概率分布P (C=ck) =mk/m.将初始状态看成特殊的聚类结果, 将每个用户的浏览序列看成一个类, 为每一类别用户建立类Markov链, 并使用式 (4) 和 (5) 计算概率转移矩阵Ak中的每一项pkij和初始状态分布Bk中的每一维pki的值, 从而得到m个类Markov链. 式中, Skij表示在第k类所有用户浏览序列中, 状态对 (xi, xj) 出现的次数;αkij是超级参数, 取值为β/n2, β为问题域空间的大小. 同理, 计算任意两个类Markov链mck和mcl合并后的类Markov链mc (k+l) 为 式 (6) 和 (7) 中的所有参数与式 (4) 和 (5) 的参数相同. 任意两个概率转移矩阵Ak和Al的相似度定义为矩阵中行的交叉熵的平均值: 式中, pkij、plu3000ij分别表示概率转移矩阵Ak和Al中从状态Xi到状态