图 2 网站链接结构的基本模型
模拟用户浏览行为的 Markov链是各态历经的 , 因为它 可
以经过一步或多步转 移 , 从 某一个 状态转 移到其 他状态 。 转
移概率矩阵中的元素 Pi, j为用户从页面 i链接到页面 j占页面 i出权的比值 。
Pi, j =P(Xn+1 =j Xn =i, Xn-1 =in-1 , … , X0 =i0) =
第 27卷第 11 2007年 11月
期
计算机应用 ComputerApplications
Vol.27 No.11 Nov.2 007
文章编号 :1001 -9081(2007)11 -2746 用
石 磊 1, 2 , 姚 瑶1, 2, 3 (1.河南省信息网络重点开放实验室 , 郑州 450052; 2.郑州大学 信息工程学院 , 郑州 450052;
本文将网站的链 接结构看 作是分 等级的 , 可把 网页组 织 成不同的概念层 。 一 般主页在 第一概 念层 , 链接到 第二概 念 层的若干网页 。 第一概念层的网页比第 二概念层上的页面更 具有综合性和概括性 , 依此类推 。 通常意义上 , 它将用于一个 分等级的网站上任何两个相邻 的概念层 。 根据上述概念化的 层次结构 , 本文给出两种链接形式 :主干链接和分支链接 。 主 干链接定义网站的概 念层次 结构 , 分支链 接体现 用户在 网页 间的自由访问 。
2 构造 Markov预测模型
用户浏览网 页时 除了 输入 起始 网址 和关 闭最 后 网页 之 外 , 总是沿着超 链接 的指 引从 一个 网页 转移 到另 一个 网页 。 用户在网上的 访问 过程 可以 看作 一个 Markov过程 [ 1] , 包 含 一 系 列的 事件 {Xn}, n=0, 1, 2, … , 其 中 n代 表序 列 中的 步
若保留主干链接和同层网页间的链接 , 即部分分支链接 , 可得到一个层 次化的 网站 链接结 构 。 添加 Start节点 作为 用 户访问的开始节点 , Exit节 点作 为用户 访问 的结 束节点 。 同 时添加一条链接从 Exit指向 Start, 保 证了链 接结构 中的任 意 两个节点之间 都有 通路 。 图 2 显示 了网 站链 接结 构基 本 模 型。
∑ P(Xn+1 =j Xn =i) =wi, j/ wi, k k
(1)
∑ 其中 wi, j是从 i到 j的链接权重 ,
wi, k是页面 i的出权 。矩
k
阵 P的第 i行表示从页面 i出发到其他页面的转移概率 。每一
行的和是 1.0。第 i列表示从其他页面到达页面 i的转移概率 。 转移概率矩阵如图 3。
定义 1 主干链 接 。 指在 一个 分等 级的 网站 上 , 从较 高 概念层的页面链接到它所邻接 的较低概念层的页面 。 所有非 主干链接则称为分支 链接 。
图 1是结构化网站 的链接示 意图 , 其中 包含了 用实线 表 示的主干链接及用虚线表示的 分支链接 。 每一概念层用不同 的虚线连接 , 代表那一层的节点同属于一层 。
1 网站链接结构
网页上的一系列 超链接可 以表示 为 L ={(r, u, w)}, 其 中 r是发出请求的页面 , u是被请求的页面 , w是从 r到 u的链 接数量 , 一条链接可能被访问多次 。删除 链接到当前网站以外 的引用 , 可构造反映网页访问情况的邻接矩阵 。其中行代表发 出请求的页面 , 列代表被请求的页面 。两 个页面间的对应权值 越大就越相关 , 访问的可能性也就越高 。
骤 , Xn从链接结构所有页面的状 态空间 取值 , 包括 了链接 结 构 S中的所有页面 。未来事件 的结果 可以看 作仅依 赖于固 定 数量的以前发生的事件 。根据 WLS构造 Markov预测 模型可定 义为一个三元组 (S, P, π(0)), 其中 S是链接结构中 所有状态 的集合 , P是一阶转 移概率矩阵 。一个 Markov链可看 作一系列 状态分布向量 , (π(0), π(1), … , π(n))。
Keywords:Markovpredictionmodel;matrixcompression;similarity;rowsimilarity;columnsimilarity
0 引言
随着互联网信息 及用户的 飞速增 长 , 如 何有效 减少用 户 访问延时 , 提高 网络 服务 质量 是一 个迫 切需 要解 决的 难题 。 预取技术是克服此难题的有效 方法之一 。 预取的关键是预测 模型的构造 , 目前通常采用的办法是根据网站链 接结构 (Web siteLinkStructure, WLS)的 特 点 和 用 户 的 访 问 行 为 构 造 Markov模型 [ 1] , 模拟用户对网页的浏 览行为 。 网 站上的 网页 视为状态 , 根据网页间的 超链接 得到一 阶转移 概率矩 阵 。 虽 然初始转移概率矩 阵非常 稀疏 , 但存储 复杂度 却很高 。 如 果 直接用它作进一步的预测会花 费不少的时间 , 影响预取效率 。 高阶 Markov模型虽能提高预测准确率 , 却导致存储复杂 度成 倍增 加 。 在 保 证 一 定 的 预 测 准 确 率 和 查 全 率 前 提 下 , 对 Markov预测模 型的转移概率矩阵进 行有效 压缩 , 具有积 极的 意义 。
2.SchoolofInformationEngineering, ZhengzhouUniversity, ZhengzhouHenan450052, China; 3.DepartmentofComputerScience, XinyangNormalUniversity, XinyangHenan464000, China)
关键词 :Markov预测模型 ;矩阵压缩 ;相似度 ;行相似 ;列相似 中图分类号 :TP311.13 文献标识码 :A
Compressionandapplicationoftransitionprobabilitymatrix inMarkovpredictionmodel
SHILei1, 2 YAOYao1, 2, 3 (1.HenanProvincialKeyLaboratoryonInformationNetwork, ZhengzhouHenan450052, China;
3.信阳师范学院 计算机科学系 , 河南 信阳 464000) (xyyaoyao@)
摘 要 :Markov预测模型是 Web预取与个性化推荐技术的基础 。 大量 Web对象的存在使得用户 浏览转移状态激增 , 导致预测模型出现了巨大的空间复杂度问题 。基于网站链接结构 (WLS), 针对 Markov预测模型中的转移概率矩阵 , 提出一种基于行相似与列相似的相似度度量方法 。 首先计算出相 似矩阵 , 然后利用行相似 、列相似获得相似页面并压缩在一起 , 减小了 Markov模型中的状态个数 。 实验 表明 , 该模型具有较好的整体性能和压缩效果 , 在预取效率方面能够保持较高的预测准确率和查全率 。
图 1 网站的链接结构
对于网站上的每 一个页面 , 既可 以由其 他若干 页面链 接
到它 , 也可以从它链接到其他若干页面 。
定义 2 内链 。 由 其他页 面指 向当 前页 面的 链接 , 其 链
接的权值和称为入权 。
图 3 转移概率矩阵
定义 3 外链 。 由 当前页 面指 向其 他页 面的 链接 , 其 链 接的权值和称为出权 。
Abstract:MarkovpredictionmodelisthebaseforWebprefetchingandpersonalizedrecommendationtechnique.The existenceofalargeamountofWebobjectsresultsinalargeincreaseofthenumberofstateswhichrepresenttheusersvisit transferbehavior, whichalsocausestheissueofhugespatialcomplexityinpredictionmodel.BasedontheWebsiteLink Structure(WLS), inviewofthetransitionprobabilitymatrixinMarkovpredictionmodel, ameasurementmethodbasedonrow similarityandcolumnsimilaritywasproposed.Firstly, thesimilarmatrixwascalculated.Thentherowsimilarityandcolumn similaritywereusedtoobtainsimilarpagessimultaneouslywhichcouldbecompressedtogether.Thusthenumberofstates couldbereduced.Theexperimentalresultsshowthatthismodelhavegoodoverallperformanceandcompressioneffect, and keeprelativelyhigherpredictionaccuracyandrecallintermsoftheefficiencyofWebprefetching.
第 11期
石磊等 :马尔可夫预测模型中转移概率矩阵的压缩与应用
2 74 7
压缩方法 。 在兼顾网 站站点结 构和页 面之间 链路的 同时 , 考 虑页面彼此间的重要 程度对 各条超 链接进行 赋权 , 以用 户浏 览的页面为行和列 , 建立 转移概 率矩阵 。 挖掘矩阵 状态的 相 似性并把同时具备行相似和列 相似的状态进行合并 。 与传统 方法相比 , 该方法 不仅 能减 小存 储空 间 , 而 且能 保留 Markov 模型的转移行为 , 反映状态间的内在关系 。
本文提出了一种 针对 Markov预 测模 型转 移概率 矩阵 的