硕士论文-基于马尔科夫模型的用户浏览路径预测研究.pdf

燕山大学 硕士学位论文 基于马尔科夫模型的用户浏览路径预测研究 姓名：乔良 申请学位级别：硕士 专业：计算机应用技术 指导教师：陈子军 20070301 摘要 摘要 w e b 日志挖掘需要对用户的测览模式做出归纳和预测，m a r k o v 模型是 一种简单而有效的预测工具，但现有的预测方法存在着一些不足之处。因 此，改进基于m a r k o v 模型进行用户浏览路径预测的方法，成为w 曲日志挖 掘的一个新课题。本文对国内外关于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 模型 的不足。最后利用实验验证网页类预测方法的有效性。 其次，提出了动态分类预测模型，主要解决多m a r k o v 链模型的学习算 法时间复杂度过高的问题。动态分类预测模型采用了聚类的思想对用户分 类，在每一类用户上进行浏览路径预测，同时能动态更新用户的特征。该 模型下的分类算法在时间复杂度上，明显优于多m a r k o v 链模型。 最后，通过实验对传统模型算法、多m a r k o v 链模型算法和动态分类算 法进行了分析，比较了这三种算法的实验结果，并基于实验结果分析了动 态分类预测模型的空间复杂度，从而验证了动态分类预测模型的有效性。 关键词w e b 日志挖掘；导航；m a r k o v 模型；预测；聚集 燕山大学工学硕士学位论文 a b s t r a c t w e bl o gm i n i n gn e e d st os u m m a r i z ea n dp r e d i c tt h ei l g e i s n a v i g a t i o n p a t t e r n a n dt h em a r k o vm o d e li s as i m p l ea n dp r a c t i c a lt o o lt od ot h a t b u t s o m ee 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 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 s an e wl e s s o ni nt h ea r e ao f w e b l 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 o nm e t h o d s n l 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 tt h eu s e r s n a v i g a t i o np a t t e m t h e nw 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 s b a s e do nm a r k o vm o d e l so nw o r ka r e aa n dc o s to ft i m ea n dp r e s e n t0 1 , 1 1 “ p l a nt o c o r r e c tt h e m 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 n m a r k o vm o d e l f i r s to fa l l ，t h i sp a p e ri n t r o d u c e st h ep r i n c i p l ea n dw o r kp r o c e s so ft h e t r a d i t i o n a lm a r k o vm o d e l b ya n a l y z i n gt h ei n p u ta n do u t p u td a t ao ft r a d i t i o n a l m a r k o vm o d e l ，w ef m dt h a ti tc a l ln o tr e f l e c tu s e r s i n t e r e s te x a c t l ys o m e t i m e s a n dt h e nw i t ht h ew a yo fa g g r e g a t i o no fm u l t i d i m e n s i o n a lh i e r a r c h i c a ld a m , a p r e d i c t i o na p p r o a c hf o rw e b p a g et y p e si sp r e s e n t e di nt h i sp a p e r f i n a l l y ，t h e e f f i c i e n c yo f t h ea p p r o a c hi sv a l i d a t e dt h r o u g ht h ee x p e r i m e n t s e c o n do fa 1 1 t h i sp a p e rs t u d i e sm u l t i - m a r k o vc h a i n sm o d e lw h i c hu s e c l u s t e rt om a k et h eu s e i 苫d i f f e r e n tt y p e s t h e nw ea n a l y z ei t sa l g o r i s m ，a n df r e d t h a tm u l t i m a r k o vc h a i n sm o d e lc a l lg i v eh i g h e rp r e d i c t i o na c c u r a c ya n d r e q u i r e sl o w e rs p a c ec o m p l e x i t yt h a nt r a d i t i o n a lm o d e ld o e s ，b u ti t c o s t st o o m u c ho nt i m ec o m p l e x i t y f o rt h a t , t h i sp a p e rp r e s e n t st h ed y n a m i c - m a r k o v m o d e la n dg i v e so u tt h r e ea l g o r i s m sf o rd y n a m i c m a r k o vm o d e l t h e nw ep r o v e t h a to u ra l g o r i s m sa l em u c hb e t t e ra tt i m ec o m p l e x i t yt h a nt h eo n eo f m u l t i m a r k o vc h a i n sm o d e l f i n a l l y ，w ea n a l y z et h et r a d i t i o n a lm a r k o vm o d e l ，m u l t i - m a r k o vc h a i n s a b s t r a e t m o d e la n dd y n a m i c m a r k o vm o d e lt h r o u g he x p e r i m e n t s a n dw ep r e s e n tt h e s p a c ec o m p l e x i t yo fd y n a m i c m a r k o vm o d e lb a s e do ne x p e r i m e n t s t h er e s u l t s o f o u re x p e r i m e n t sv a l i d a t ee f f i c i e n c yo f t h en e w a p p r o a c h k e y w o r d sw e bm i n i n g ；n a v i g a t i o n ；m a r k o vm o d e l ；p r e d i c t i o n ；a g g r e g a t i o n h i 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于马尔科夫模型的用 户浏览路径预测研究，是本人在导师指导下，在燕山大学攻读硕士学位期 间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外 不包含他人已发表或撰写过的研究成果，对本文的研究工作做出重要贡献 的个人和集体，均己在文中以明确方式注明。本声明的法律结果将完全由 本人承担。 7 作者签字7 哥弛日期：幻年弓月次扫 燕山大学硕士学位论文使用授权书 基于马尔科夫模型的用户浏览路径预测研究系本人在燕山大学攻 读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归 燕山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。 本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并 向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人 授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布 论文的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密 ( 请在以上相应方框内打“”) 作者签名： 舞钆 日期：厶刀1 年；月拥 导师签名：筒，子孕 日期：力卿年三月z 咽 第1 章绪论 1 1 研究背景 第1 章绪论 经过十几年的发展，互联n ( i n t e m e t ) 尸, 经成为信息时代的标志，它极大 地影响了人类的生活方式，并将在新世纪继续对人类社会的进步起着巨大 的推动作用。随着互联网的飞速发展，网络上的网页数目也在急速膨胀。 据估计到1 9 9 9 年，互联网上的网页数已达到了8 亿多个，而且这个数字仍 以每4 到6 个月翻一番的速度增加【l j 。 面对急剧增大的w e b 空间，用户要进行有效的浏览变得非常困难。而 作为主要的w e b 信息检索工具搜索引擎和目录服务，只能提供对特定 主题的检索，却无法为用户的浏览提供有效的帮助。因此，开发各种浏览 导航工具就变得非常必要，并成为了一个研究热点。而建立有效的用户浏 览预测模型，对用户的浏览做出准确的预测，是实现这些导航工具的关键。 1 9 9 9 年，z u k e r m a n 等提出利用m a r k o v 链进行浏览路径预测的方法【2 j ， 它将用户的浏览过程抽象为一个特殊的随机过程齐次离散m a r k o v 链， 用转移概率矩阵描述用户的浏览特征，并基于此对用户的浏览进行预测。 之后，b o r g e s 等采用了多阶转移矩阵，进一步提高了模型的预测准确率【j j 。 在此基础上，s a r u k k a i 建立了一个实验系统，通过在e p a 服务器日志文件 上的实验表明，基于m a r k o v 链模型对用户的浏览进行预测，其准确率可以 达到7 0 左右【4 】。然而，该模型存在以下三个方面的不足有待改进。 ( 1 ) 用户在w e b 空间的浏览过程是一个受浏览目的、文化背景、兴趣爱 好等多种因素影响的复杂过程。由于这些因素的差异，各个用户的浏览过 程也就表现出不同的个性化特点，而该模型采用一个m a r k o v 链描述所有用 户的浏览特征，明显过于简单，其预测结果必然存在较大的误差。 ( 2 ) 该模型的存储空间主要用于保存转移概率矩阵，所以它的存储复杂 度是模型中包含的网页数目挖的平方，即o ( n 2 ) 。由于九值一般都比较大， 燕山大学工学硕士学位论文 因此其存储复杂度很高。而且为了提高预测准确率，经常还需要用到多阶 转移概率矩阵，使存储复杂度成倍提高。 ( 3 ) 该模型的输入与输出都是单个网页组成的路径，单独观察某几个网 页之间的跳转很难在宏观上了解用户的兴趣，因此这种模型并没有确切的 反映用户所感兴趣的网页类别以及这些类别间的联系。 为了解决以上的问题，需要对现有的基于m a r k o v 模型的预测方法进行 研究和改进，从而对用户浏览路径做出更准确的预测，并且使模型具有更 低的存储复杂度。 1 2 研究现状 1 9 9 9 年，m a r k o v 模型由z u ke r ：r a a n 等首次引入到日志挖掘中来【2 】，它将 用户的浏览过程抽象为一个特殊的随机过程齐次离散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 模型，使用引用页；链接空间一时间m a r k o v 模型，它使 用引用页和最后请求页来预测用户的下一个请求。一旦一个页面被请求， 四个模型计算下一页的概率。 b o r g e s 等采用了多阶转移矩阵，进一步提高了模型的预测准确率，并提 出t m a r k o v 模型的经典算法【引。 b e s t a v r o s 和s a r u k k a i 使用m a r k o v 模型预测在一确定性时间中用户可能 链接的网页【4 j 。 z h u 提出了在链接概率分布的基础上给链接分配权值的思想【5 j ，以便更 好的进行预测。 c a d e z 等提出混合m a r k o v 模型【6 】，不同的模型针对不同的聚类给各种用 户作出不同的导航。 b o r g e s 等提出深度优先算法阴，它把日志中存储的网页看做一个个节 点，在深度遍历浏览路径的同时生成一棵搜索树，树的每一枝代表着一个 2 第1 章绪论 预测结果。这样的方法使得算法的平均复杂度与访问网页数目成线性的倍 数关系。传统算法在运行时，对阈值变化非常敏感，阈值小导致产生的规 则( 预测结果) 多，降低了准确率增加了存储空间。闽值大使得产生规则太短， 无法体现出可能存在的长路径，b o r g e s 等通过对阈值加上限制性条件【8 ，9 l ， 成功的解决了这一问题。之后，他们把动态聚类的思想引入m a r k o v 模型i l o j ， 为该领域的研究提供了新的思路。 c o r i n 提出一种新的类m a r k o v 模型1 1 l 】关系m a r k o v 模型( i m m ) ， 通过对网页分类，提高了传统模型的预测准确率。 王实，高文等提出了路径预测中的聚类观点【l “，把聚类分类的思想引 入了m a r k o v 模型。 邢永康，马少平提出多m a r k o v 链模型1 3 】，其基本思想是通过用户浏览 过程中表现出兴趣相同或相近的特点，在预测之前先对用户进行聚类。通 过对用户分类，由于同一类别的用户具有相同或相近的浏览特征，因此更 适合用一个模型来描述它。而不同类别的用户其浏览过程差别较大，用不 同的模型来描述他们的特征则更为合理。这样就克服了传统模型用一个 m a r k o v 链描述所有用户浏览特征而带来的不准确性。 金民锁等利用隐m a r k o v 模型进行路径预测【1 4 】，该模型中，同样引入了 聚类、分类的思想，与多m a r k o v 模型不同的是，它同时考虑到了用户所浏 览的w e b 页面的内容，进一步把握用户的真正兴趣所在。 s a m e rn a s s a 等提出了一种在大规模【1 5 1 、动态变化的数据库中进行数据 聚类的增量方法。 m i n g h u a z h a n g 等研究了从队列间隙请求中挖掘频繁模式的问题i l6 】，给 出了挖掘问题的复杂度，并讨论了传统挖掘算法在计算上为什么是不可行 的。最后提出了解决该问题的可行算法。 r u iz h a n g 等研究了在高速流数据上有效计算多重聚集的问题【1 7 1 。 j u n h o oc h o 等提出了搜索引擎在搜索结果的顶端重复反馈流行页面的 问题【1 8 1 ，这样的搜索结果使得一些非流行的页面被大多数用户忽视了。针 对此，作者提出了一个新的分级函数，对网页进行级别评估，以减轻流行 页面对搜索结果造成的负面影响。 燕山大学工学硕士学位论文 邢东山等在分析目前用户浏览模式挖掘算法存在的问题的基础上，利 用提出的支持偏爱度的概念【1 9 1 ，设计了网站访问矩阵，并基于这个矩阵提 出了用户浏览偏爱路径挖掘算法，先利用w e b 日志建立以引用网页u r l 为行、浏览网页u r l 为列、路径访问频度为元素值的网站访问矩阵。该矩 阵为稀疏矩阵，将该矩阵用三元组法来进行表示。然后，通过对该矩阵进 行支持偏爱度计算得到偏爱子路径。最后进行合并生成浏览偏爱路径。 在关联规则挖掘过程中，现有的取样误差量化方法和快速估计算法存 在着不足。对此，贾彩燕等提出了一种新的取样误差量化三元组模型【2 0 l ， 并在实验观察和理论分析的基础上给出了一种取样误差的快速估计算法 主误差区间估计法。 王实等提出一种新的基于分类方法的实时个性化推荐方法【2 1 1 。在这种 方法中，用户不需要注册信息，推荐不打扰用户，可以为用户提供实时个 性化的服务。 连一峰等在文献 2 2 1 中阐述了针对t e l n e t 会话中用户执行的s h e l l 命令， 利用数据挖掘中的关联分析和序列挖掘技术，对用户行为进行模式挖掘的 方法，分析了传统的相关函数法在应用于序列模式比较时的不足，提出了 基于递归式相关函数的模式比较算法。 孟小峰等在文献 2 3 1 中讨论了目前数据库研究领域中最热门的几个研 究方向的发展现状、面临的问题和未来趋势。包括信息集成、数据流管理、 传感器数据库技术、x m l 数据管理、网格数据管理、d b m s 自适应、移动 数据管理和微小数据库，数据库用户界面等。 由于其内在的计算复杂性，挖掘密集型数据集的频繁模式完全集非常 困难，解决方案之一是挖掘最大频繁模式集。刘君强等在频繁模式完全集 挖掘算法o p p o r t u n e p r o j e c t 基础上，提出了挖掘最大频繁模式的新算法 2 4 1 ， 实现搜索与剪裁效率最优化。 m l e v e n e 从熵的角度入手，对m a r k o v 模型进行了分析【2 5 埘】。熵的概 念以及m a r k o v 链的概率统计分布在个性化分级算法( 例如g o o g l e 中使用的 p a g e r a n k ) 上得到应用。 邓长寿，赵秉岩对b 2 c 网站的用户浏览行为进行了系统的研究【2 7 l 。通 4 第1 章绪论 过建立基于m a r k o v 链的动态模型，对用户浏览行为进行了深入的分析。进 一步综合利用w e b 日志文件信息和w e b 站点的拓扑结构，对用户有关某页面 的兴趣度进行了计算并提出了相关页面的聚类矩阵。 何江宏，陈启明在历史资料没有给出系统处于”个状态次数的情况下， 给m a r k o v 模型一步状态转移概率矩阵估计的最优化方法【2 ”。 王双成，苑森淼等使用依赖分析方法建立基于贝叶斯网络的m a r k o v 毯 预测【2 9 】，提出了首先进行递推条件独立性检验，然后进行因果语义定向， 最后进行冗余边检验的贝叶斯网络结构学习方法。该方法能够更准确地建 立m a r k o v 毯预测。 金松河，钱慎一等提出一种w e b 日志挖掘算法【3 0 】，该算法首先以w e b 站点的u r l 为行、以用户的u s e r l d 为列，建立u i 也u s e r i d 关联矩阵，元素 值为用户的访问次数；然后，对行向量进行相似性度量获得用户会话粗聚 类，最后，利用层次结构对比聚类算法，对用户会话粗聚类进行进一步地 处理得到更高精度的聚类。 郭岩等在文献【3 1 】中，围绕网络日志中是否蕴含用户访问w e b 的规律性 特性以及如何利用这些特性，研究了日志规模与用户数、w e b 文档数以及单 位用户访问的w e b 文档数的关系；利用日志中蕴含的用户稳定兴趣，提出了 一个基于用户行为的相关文档检索模型和搜索引擎系统s i s i 。s i s i 的实际检 索性能与分析检索模型所得结论一致，检索准确率和检索时间主要依赖于 用户数，检索返回的记录数主要依赖于文档数。 孟涛等针对网页变化和增量搜集技术这一主题，对最近几年的研究成 果作总结，并介绍最新的研究进展 3 2 1 。 任永功等提出了一种基于主次属性划分的聚类方法和一种新的数据可 视化方法【3 3 】。该方法有利于用户全面地理解数据，为数据的预测、决策起 到重要作用。 1 3 研究意义 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 左右1 ， 这样有利于开发各种浏览导航工具，为用户提供更好的服务。 第二，虽然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 模型在路径预测中的应用具有重要意义。 1 4 课题研究的内容 根据上面所阐述的研究背景和研究现状，课题的研究内容是增强 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 链描述所有用户的浏 6 第1 章绪论 览特征，明显过于简单，其预测结果必然存在较大的误差。多m a r k o v 链模 型【1 3 j 通过聚类对用户划分类别对传统模型进行改进，提高了预测的准确率。 但是，该模型大大增加了计算的时间复杂度，对此，本文提出一个新的分 类方法，以降低多m a r k o v 链模型在时间上的消耗。 1 5 本文的结构 本文共分四章，具体结构布局如下。 第2 章是基础知识概述。先介绍了m a r k o v 模型的数学形式和w e b e l 志挖 掘的相关概念，然后介绍了与路径预测有关的n - g r a m 模型，并详细叙述了 利用m a r k o v 模型进行日志挖掘和路径预测的过程，最后介绍了多m a r k o v 链 模型的相关知识。 第3 章是网页类预测方法。这是本文提出的一种新方法，改进了现有基 于m a r k o v 模型的预测方法，由于用到了数据聚集的技术，因此先介绍用于 网页分类的h h h s 3 4 l 方法。然后给出了网页类预测方法中网页分类的具体过 程，以及该方法下类m a r k o v 模型的建立过程。最后用实验验证了网页类预 测方法的有效性。 第4 章是动态分类预测模型，这是本文提出的一种改进多m a r k o v 链模 型，以降低其时间复杂度的新模型。本章先分析了多m a r k o v 链模型的时间 复杂度，然后提出了动态分类预测模型的思想和分类过程。给出并分析动 态分类的算法，理论上证明该算法在时间复杂度上的优越性。最后用实验 验证了动态分类预测模型的有效性，并比较了传统模型，多m a r k o v 链模型 以及动态分类预测模型在不同条件下的工作效率。 最后是本文的结论，并对下一步的研究工作进行了展望。 7 燕山大学工学硕士学位论文 2 1引言 第2 章基础知识概述 第l 章主要阐述了本课题的研究背景、研究现状和研究意义。在本章 中，将详细介绍与本课题研究相关的基础知识。 2 2w e b 日志挖掘的概念及相关技术 面对巨大而复杂的网络系统以及浩如烟海的信息资源，研究人员将传 统的数据挖掘技术和相结合，进行w e b 挖掘，从半结构或无结构的页面中， 以及使用者的活动中，抽取感兴趣的模式，分析、研究，并加以利用【3 ”。 挖掘可分为三类，w e b 内容挖掘、w e b 结构挖掘和w e b 日志挖掘【3 6 j 。而w e b 日志挖掘作为w e b 挖掘的一个重要组成部分，有其独特的理论和实践意义。 所谓日志，是指在服务器上有关w e b 访问的各种日志文件【3 7 j ，包括访 问日志、引用日志、代理日志、错误日志等文件。这些文件里包含了大量 的用户访问信息，如用户的碑地址、所访问的u r l 、访问日期和时间、访 问方法( g e t 或p o s t ) 、访问结果( 成功、失败、错误) 、访问的信息大小等。 而w e b 日志挖掘，就是通过对w e b 日志记录的挖掘，发现用户访问页面的模 式，从而进一步分析和研究w e b 日志记录中的规律p 8 】，以期改进w e b 站点 的性能和组织结构，提高用户查找信息的质量和效率，并通过统计和关联 的分析找出特定用户与特定地域、特定时间、特定页面等要素之间的内在 联系，这在电子商务等领域是大有作为的。 目前，w e b h 志挖掘技术主要分为两大类，基于w e b 事务的方法和基于 数据立方体的方法【3 9 】。 基于w e b 事务的日志挖掘技术，最早是c h e n 等人【4 0 】提出的。他将数 据挖掘技术应用于w e b 服务器日志文件，提出最大向前引用算法m f 的概念。 8 第2 章基础知识概述 他将用户会话分割成一系列的事务，然后采用与关联规则相类似的方法挖 掘频繁访问序列，从而取得用户访问模式。 基于w e b 事务的日志挖掘技术的基本流程如下。 ( 1 ) 预处理过程w c b 服务器日志中的内容非常丰富，但是由于本地缓 存、代理服务器、防火墙的存在，使得直接在w e bl o g 数据上进行挖掘变得 十分困难和不准确。因此，在实施数据挖掘之前，首先必须对w e bl o g 文件 进行数据净化、用户识别、会话识别、页面过滤、路径补充等一系列的工 作。数据净化( d a t ac l e a n i n g ) 是指删除w e b 日志中与挖掘算法无关的数据， 同时将有用的w e b 日志记录信息转换为适当的数据格式。用户识别和会话 识别是从日志中的每一条记录中识别出相应的用户，并将日志中的多条记 录分割为不同的w e b 事务。页面过滤是针对w e b 页面的帧( f r a m e ) 结构，对 日志记录进一步过滤，而路径补充则是考虑到用户可能在浏览器中使用 b a c k 方式而使w e b 日志中遗漏了访问信息。 ( 2 ) 序列模式识别w e b 事务分割完成以后，接下来就是实施序列模式 识别的工作。第一步，通过m f 算法( m a x i m a lf o r w a r dr e f e r e n c e s ) 将日志数 据中原始序列，转换为最大向前引用集，其中的每一个访问子序列都代表 一个从用户访问点出发的最大向前引用，其目的是过滤掉为了取消访问而 产生的回退引用的影响，从而使我们能专注于挖掘有意义的用户访问序列。 第二步，从最大向前引用集中找出大引用序列( l a r g er e f e r e n c es e q u e n c e s ) 也就是频繁出现的引用序列。其方法和挖掘关联规则的方法相类似，但不 同的是，在挖掘访问模式时，一个引用序列必须是包含在最大向前引用中 的连续引用，而在挖掘关联规则时，一个大项目集仅仅是一个事务中的项 目的集合。为了找出大引用序列，c h e l a 等人提出了f s ( f u l ls c a n ) 和 s s ( s e l e c t i v es c a n ) 两种算法。f s 算法从本质上说，是利用了一些h a s h 和p r u n e 技术，以解决前面所提到的访问模式与关联规则的差异问题，它要求每次 都必须对事务数据库进行扫描。而s s 算法，则适当地利用了候选的引用序 列，减少扫描事务数据库的次数，从而降低磁盘i o 读写的开销。因此s s 算 法相对f s 算法更先进，效率更高。第三步，从大引用序列中确定最大引用 序y u ( m a x i m a lr e f e r e n c es e q u e n c e s ) ，即频繁访问序列。这一步非常简单和 9 燕山大学工学硕士学位论文 直观，只要找出没有包含在其他任何大引用序列中的大引用序列即可。 ( 3 ) 序列模式分析掌握了用户的访问序列模式，即频繁访问序列，就 可以对所获得的知识进一步加以分析和利用。例如，改善网站的组织结构， 按照大多数访问者的浏览模式对网站加以重组等。此外，个性化的用户交 互和可视化的结果呈现，也是模式分析研究的新内容。 下面介绍基于数据立方体的w e b 日志挖掘技术。 h a n 等人【4 1 1 提出基于数据立方体的w e b 日志挖掘技术，他根据w e b , 暇务 器日志文件，建立数据立方体( d a t ac u b e ) ，然后对数据立方体进行数据挖 掘和联机分析处理( o l a p ) 。和基于事务的w e b 日志挖掘技术相似，基于数 据立方体的w e b 日志挖掘同样要经过下面的预处理、模式识别、模式分析 这三个步骤。 ( 1 ) 预处理过程即对w c b 日志进行清洗、过滤和转换，并抽取感兴趣 的数据。 ( 2 ) 模式识别即建立数据立方体，进行联机分析处理( o l a p ) 。将所访 问的u r l 、访问方法、访问资源的类型和大小、请求和停留的时间、访问 者的域名和i p 、用户、服务器状态等作为的d a t ac u b e 维变量，将对不同页 面和文件的请求次数、来自不同i n t e r n e t 域名的请求次数、事件、会话、带 宽、错误次数、不同浏览器种类、用户所在组织等作为的d a t ac u b e 度量变 量建立数据立方体。然后，运用逐层细化分析( d r i l l d o w n l 、汇总分析 ( d r i l l u p ) 、切片分析( s l i c e ) 和切块分析( d i c e ) 等技术对d a t ac u b e 进行联机分 析处理。逐层细化分析是从一般到特殊的分析过程，如时间上从“年”、 “月”到“日”的逐步细化；汇总分析是从特殊到一般的分析过程，例如 地域上从某个区域到某个国家；切片分析方法是在多维数组的某一维上选 定一维成员，得到一个多维数组的子集。切块分析方法是在多维数组的某 一维上选定某一区间的维成员后得到的结果。 ( 3 ) 模式分析和数据挖掘利用成熟的数据挖掘技术( 如特征、性能、分 类、关联、预测、时间序列分析、趋势分析等) 进行w e b 流量分析、典型的 事件序列和用户行为模式分析、事务分析等。例如，应该在怎样的上下文 环境下使用特定的成分和特征? 典型的事件序列是什么? 不同的用户群在 1 0 第2 章基础知识概述 使用和访问模式方面有什么不同? 在不同的过程里用户在使用和访问模式 方面有什么不同? 在某一特定的环境下最普遍的用户访问模式是怎样的? 用户行为随时间的不同有什么变化? 用户的使用模式将如何随着系统性 能、服务质量的不同而变化? 网络流量的分配与时间的关系如何? 除了以上介绍的两种主要的w e b 日志挖掘技术以外，许多研究人员根 据实际的需要，开发出一些简单、新颖、高效的w e b 日志挖掘方法。例如， 建立u r lu s e r l d 关联矩阵，通过相似性分析和聚类算法，获得相似客户群 体和相关w e b 页面，并进一步发现频繁访问路径。又比如，针对电子商务 中的时间特性，研究基于w e b 的时间序列模式挖掘等。 2 3m a r k o v 模型的相关概念 m a r k o v 模型是一种简单而有效的用户浏览路径预测模型，本节将介绍 有关m a r k o v 模型定义和概念。 2 3 1m a r k o v 链的定义 m a r k o v 过程按其状态和时间参数是连续的或离散的，可分为三类旧。 ( 1 ) 时间、状态都是离散的m a r k o v 过程，称为m a r k o v 链。 ( 2 ) 时间连续、状态离散的m a r k o v 过程，称为连续时间的m a r k o v 链。 ( 3 ) 时间、状态都连续的m a r k o v 过程。 在本文中，由于m a r k o v 链是研究的重点，因此下面给出m a r k o v 链的数 学定义。 假设m a r k o v 过程 蜀，拧d 的参数集绳离散的时间集合，即产 o ，1 ， 2 ， ，其相应可能取值的全体组成的状态空间是离散的状态集卢 f l ，2 ， i 3 ， 。 定义2 1 ：设有随机过程 蜀，行乃，若对于任意的整数n e 砑口任意的i 0 ， i l ，0 1 绦件概率满足式( 2 - 1 ) 。 p k 。= i n + l i x 0 = i 0 ，以= = p 以“= i n + l i x = ) ( 2 - 1 ) 则称瓦，疗d 为m a r k o v 链。 燕山大学工学硕士学位论文 条件概率p 墨+ l 可乒f 的直观含义为系统在时刻刀处于状态i 的条件 下，在时刻n + l 系统处于状态，的概率。它相当于随机游动的质点在时刻即处 于状态i 的条件下，下一步转移到状萄的概率。记此条件概率为p d n ) ，其严 格定义如下。 定义2 2 ：称条件概率p “ ) = p ( 瓦+ 1 可= f ) 为m a r k o v 链( ，n ed 在时刻 h 的一步转移概率，其中f ，y e i , 简称为转移概率。 一般地，转移概率p “以) 不仅与状态f 有关，而且与时刻珂有关。当p f ) 不依赖于时刻h 时，表示m a r k o v 链具有平稳转移概率。 定义2 3 ：若对任意的i ，j e i ，m a r k o v 链 ，n 乃的转移概率p “n ) 与n 无关，则称m a r k o v 链是齐次的，并t 印和) 为西。 由于本文中只讨论齐次m a r k o v 链，所以通常将“齐次”两字省略，以 后统称为m a r k o v 链。 设尸表示转移概萼肇，所组成的矩阵，且状态空间卢 o 时，语言所包含的串可以从任意的状态 开始。因此，n 的值应当根据一个状态作为会话的第一个状态的重要性来确 定。最后，从起始状态出发的产生路径的概率对应着一个初始概率向量万， 其他的路径概率对应着一个m a r k o v 链的转移矩阵【4 5 j 。 2 3 3 n - g r a m 模型 n - g r a m 的概念用来决定在站点导航时，假定的用户存储器，其中 7 ( 垒1 ) 称作历史深度。因此，当一个用户访问一个页面时，假设用户下一个将要 选择的链接，仅仅是由前面个浏览过的页面所决定的。也就是说，用户的 下一步选择只依赖于前面最后个浏览的网页。 n - g r a m 模型的缺点在于，当历史深度增加时，状态的数目也随之增加。 如果一个网站有胛个网页，给定浏览的历史深度为，那么语法的状态数目 为6 ( n ，6 是一个网页向外链接的平均数目。 在利用m a r k o v 模型进行用户浏览路径的预测过程中，的取值将直接影 响预测结果的准确率。 燕山大学工学硕士学位论文 2 4m a r k o v 模型的预测过程 下面介绍传统m a r k o v 模型，以及利用m a r k o v 模型进行用户浏览路径预 j 受0 的过程。 定义2 5 ：m a r k o v 模型可以表示为一个三元组， 4 c 气誓a ，痧，其中， 腥一个离散随机变量，值域为，x 2 ，靠) ，其中每个x 对应一个网页，称 为模型的一个状态。4 为转移概率矩阵，简称转移矩阵，每一巧如f = p - 矧 丘l f ) 表示由状态而转移到状态x 的概率。石为初始状态分布，每一项为 p ，= p ( x t ；o = x ，) ，如式( 2 - 3 ) 所示。 a = ( p 。) = p t lp 1 2 p 2 1p 2 2 p “ 1p h 2 ，r = ( p ，) = ( p 1 ，p 2 ，p 。) p l 。 p 2 月 p n 月 ( 2 3 ) 按照时间顺序，记录一个用户在w e b 空间中浏览过的所有网页，从而得 到随机变量硼q 一个取值序列，称为该用户的浏览序列。通过记录m 个用户 的浏览过程，得到f 1 3 m 个用户浏览序列构成的学习数据集合d = d l ，砬， 如 。利用该学习数据，采用最大似然估计可以估计, p , m a r k o v 模型中的所有 参数，如式( 2 - 4 ) 所示。 。岛 岛= 车l ，只= 牛( 2 - 4 ) 岛s o j = l t = l j = l 式( 2 - 4 ) 中，岛表示在所有用户浏览序列中状态x c ( x b x ) 的出现次数。 用向量z ( 力：( o 0 1 ) 表示用户在时刻f 的状态，如果此时用户处于状态 劫，则该向量的第i 维等于l ，其余各维都为0 。向量坎o = ( p = x 0 ，p = 耽) ， p c 蜀。) ) 中每一维表示不同状态的概率，可以根据式( 2 - 5 ) 对用户在时n t 的 状态做出预测。 坎力= z ( t - 1 ) x a( 2 - 5 ) 1 4 第2 苹基础知识概述 在式( 2 5 ) 的向量坎0 中，概率值最大的一维所对应的状态，可能就是用户在 时n t 所处的状态，为了提高预测准确率，常采用多阶加权组合模型，以充 分利用用户的历史浏览信息进行预测。 v ( o = o s l z ( t - 1 ) x a l + 纰z ( ，一2 ) x 4 0 + o z ( t - u ) x a “ ( 2 6 ) 式( 2 6 ) 中，彳“表示m a r k o v 链的u 阶转移矩阵。劬是权值，并要满足下面的等 式，铆+ 眈+ + 吼= 1 o 实验表明，“的取值越大，模型的预测准确率就越高，但是，计算量也 越大。 2 5 多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 链预测模型进行介绍。 2 5 1多m a r k o v 链预测模型的定义 用户在w e b 空间的浏览过程是一个受浏览目的、文化背景、兴趣爱好 等多种因素影响的复杂过程，由于这些因素的差异，各个用户的浏览过程 也就表现出不同的个性化特点。然而观察大量用户的浏览过程可以发现， 某些用户的浏览过程表现出相同或相近的特点。如他们浏览的网页基本相 同，浏览各个网页的顺序相似等。这一现象引发了对w e b 用户分类的研究。 f u 等研究了基于用户在每个网页上的停留时间对其聚类的问题1 4 9 】。t a l c 等则通过设置用户浏览向量，基于用户访问的页面对其进行聚类【5 0 】。这些 研究都取得了较好的结果，从而证明了对w e b 用户分类的可行性。 通过对用户分类，由于同一类别的用户具有相同或相近的浏览特征， 因此更适合用同一个模型来描述它。而不同类别的用户其浏览过程差别较 大，用不同的模型来描述他们的特征则更为合理。这样就克服了传统m a r k o v 模型中用一个m a r k o v 链描述所有用户的浏览特征而带来的不准确性，从而 能更精确的描述用户的浏览特征，并有希望得到更高的预测准确率。基于 这种思想，对用户的浏览过程做出以下两条假设。 燕山大学工学硕士学位论文 假设2 1 ( 用户分类假设) ：假设根据用户在w e b 空间的浏览特点，可以将 所有用户分为髟类。如果用c 生 c l ，c 2 ，c t ) 表示用户的类别，则任意一个用 户属于类别c 女的概率为p ( c = c k ) ，且有式( 2 7 ) 。 盖 p ( c = 气) = 1 ( 2