（计算机应用技术专业论文）网络个性化推荐模型研究.pdf

郑州人学硕十学倩论文 摘要 随着i n t e r n e t 的快速发展和w e b 信息的日益增长，个性化推荐服务越来越受到用 户青睐。作为个性化推荐的核心技术，预测模型得到了广泛关注，并成为一个具有挑 战性的研究课题。对预测模型进行深入研究，对减小用户的感知延时、处理亟待解决 的信息过载问题，具有重要的理论意义和实用价值。本文提出了一种新的混合阶 m a r k o v 预测模型，对该模型进行了实验，并对实验结果进行了分析。 首先介绍了i n t e m e t 发展概况和w w w 工作机制，分析了个性化服务的必要性。 讨论了个性化推荐技术基础，包括序列模式相关知识和预取技术的基本概念、预取系 统的分类以及现有预测算法。接着阐述了个性化推荐技术的基本概念与国内外研究现 状。 然后，总结了现有的替换算法以及个性化推荐性能评价指标，详细地讨论了w e b 缓存系统中命中率与字节命中率之间的关系，并在此基础上提出了一种新的w e b 缓 存性能评价指标，讨论了该指标在w e b 缓存替换算法及w e b 预取性能评价中的应用， 从而为度量缓存系统的性能提供参考依据。 最后，在分析讨论了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 c b 缓存；w e b 预取；序列模式 第1 i 页 郑州大学硕十学佛论文 a b s t r a c t w i t ht h ee x p l o s i v eg r o w t ho fi n f o r m a t i o na v a i l a b l eo nt h ei n t e m e t ，t h e r ei sac l e a r d e m a n df o rp e r s o n a l i z e dr e c o m m e n d a t i o ns e r v i c e a st h ec o r et e c h n o l o g yo fp e r s o n a l i z e d r e c o m m e n d a t i o n ，p r e f e t c h i n gm o d e lh a s a t t r a c t e dm u c ha t t e n t i o na n db e c o m eac h a l l e n g i n g r e s e a r c ht o p i c i t so fg r e a ti m p o r t a n c ea n ds i 鲫i f i c a n c et os t u d yp r e d i c i t o nm o d e l sf o r e n h a n c i n gt h ew e bi n t e l l i g e n c ea n ds o l v i n gt h ep r o b l e m so fi n f o r m a t i o no v e r l o a d a n d r e d u c i n gu s e r - p e r c e i v e dl a t e n c y an e wh y b r i d o r d e rm a r k o vp r e f e t c h i n gm o d e li sp r o p o s e d ， a n de x p e r i m e n t sh a v eb e e nm a d eb a s e do nt h ep r e d i c t i o nm o d e la n de x p e r i m e n t a lr e s u l t sa r e a n a l y z e d f i r s t ，t h ed e v e l o p m e n to ft h ei n t e r a c ta n dw w w m e c h a n i s ma r ei n t r o d u c e d ，a n dt h e n e c e s s i t yo fp e r s o n a l i z e d s e r v i c ei sa n a l y z e d ；t h e nt h ef o u n d a t i o no fp e r s o n a l i z e d r e c o m m e n d a t i o ni sd i s c u s s e d ，i n c l u d i n gt h er e l a t i v ek n o w l e d g ea b o u ts e q u e n t i a lp a t t e r na n d t h ec o n c e p t ，c l a s s i f i c a t i o no f w e bp r e f e t c h i n g , f o l l o w i n gt h ee x i s t i n gp r e d i c t i o na l g o r i t h m s ； t h e c o n c e p ta n dt h er e s e a r c hp r e s e n ts i t u a t i o no fp e r s o n a l i z e dr e c o m m e n d a t i o n a r e d e s e r i b c d t h e ne x i s t i n gc a c h er e p l a c e m e n ta l g o r i t h m sa n dp e r s o n a l i z e dr e c o m m e n d a t i o n p e r f o r m a n c em e t r i c sa r es u m m a r i z e da n dt h er e l a t i o n s h i pb e t w e e n t h eh i tr a t i oa n db y t eh i t r a t i oo f w e bc a c h i n gi sd i s c u s s e d ；a n do nt h i sb a s i san e w - w e bc a c h i n gp e r f o r m a n c em e t r i c i sp r o p o s e d t h em e t r i cc a nb eu s e da sap e r f o r m a n c em e a s u r e m e n to fw e bc a c h i n g r e p l a c e m e n tp o l i c i e sa n dc a l la l s ob em a d eu s eo fi nt h ew e bp r e f e t c h i n ga r e as oa st o p r o v i d ea b a s i sf o ra ne f f i c i e n tw e bc a c h i n gm a n a g e m e n t f i n a l l y , a f t e rt h ea n a l y s e so fm a r k o vm o d e l ，t r a d i t i o n a lm a r k o vm o d e l s a n d h y b r i d - o r d e rm a r k o vm o d e l s , af l e wh y b r i d o r d e rm a r k o vm o d e li sp r o p o s e d t h em o d e l m o r e st h es e q u e n c e sw h i c hs h a r et h es a n l ep r e f i xs oa st or e d u c et h es t a t e - s p a c ec o m p l e x i t y e x p e r i m e n t ss h o wt h a tt h eh y b r i d - o r d e rm a r k o vp r e f e t c h i n gm o d e lb a s e do nw 曲a c c e s s b e h a v i o rc a ni m p r o v et h ep r e c i s i o na n dr e c a l lt oac e r t a i ne x t e n t k e y w o r d s ：m a r k o vm o d e l ；p e r s o n a l i z e dr e c o m m e n d a t i o n ；w e bc a c h i n g ； w e bp r e f e t c h i n g ；s e q u e n t i a lp a t t e r n 第1 j l 页 郑州大学硕十学位论文 图目录 图1 1 历次调查中国上网计算机总数。l 图1 2w w w 系统结构示意图3 图2 1w e b 预取系统结构1 2 图2 2 推荐的一般框架1 7 图2 3 个性化推荐系统的原型结构：1 8 图2 4 个性化服务体系结构2 0 图3 1 人工开志文件片段3 l 图3 2u c b 服务器的r 志文件片段3 2 图3 3f b r 与m e a ns i z eo f h i t s 的关系图3 2 图3 4f b r 与c a c h es i z e 的关系图3 3 图3 5 命中率与字节命中率的散点图3 4 图4 1 构造会话序列a , b ，a , c ；a ，b ，c ；b ，a , b ，a ，c 的模式树4 1 图4 2 会话序列a , b ，a c ；a , b ，c ；b , a ，b ，a , c 的带头表的模式树4 l 图4 3 会话序列a , b ，a ，c ；a , b ，c ；b ，a , b ，a , c 的p p m 树4 2 图4 4 模式树与p p m 树结构图4 2 图4 59 8 世界杯日志文件片段4 5 图4 6 准确率比较4 7 图4 7 查全率比较4 7 图4 8 预测时间比较4 9 图4 9p r s 比较4 9 第v i i 页 郑州人学硕+ 学位论文 表目录 表1 1 世界互联网用户增长及分布情况表2 表2 1 推荐的类型1 8 表3 1f b r 值与缓存大小对照表( b e r k e l e y 日志) 3 2 表3 2f b r 值与缓存大小对照表( 人工日志) 3 3 表3 3 四种典型算法h r 与b h r 对照表( b e r k e l e y 日志) - 3 3 表3 4 四种典型算法h r 与b h r 对照表( 人工日志) 3 3 表4 1 图例中英文缩写对照表4 6 表4 2 准确率比较( 9 8 世界杯日志) 4 6 表4 3 准确率比较( b e r k e l e y 日志) 4 6 表4 4 查全率比较( 9 8 世界杯同志) 4 6 表4 5 查全率比较( b e r k e l e y 日志) 表4 6 预测时问比较( 9 8 世界杯日志) 4 8 表4 7 预测时间比较( b e r k e l e y 日志) 4 8 表4 8p r s 值比较( 9 8 世界杯同志) 4 8 表4 9p r s 值比较( b e r k e l e y 日志) 4 9 第v i i i 页 郑州人学硕十学位论文 第一章绪论 i n t e r a c t 已经成为人们获取信息的重要途径。然而，网络的快速发展和网络资源的 空前膨胀，使得i n t e m e t 就像一本杂乱无章的百科全书，如何使用和翻阅它是人类面临 的一个巨大挑战。搜索引擎是解决这一问题的有效途径，满足了人们一定的需要，但 由于其通用的性质，仍然不能满足不同背景、不同目的和不同时期的查询请求。个性 化推荐技术是解决这一问题的另一有效途径，弥补了搜索引擎的不足，为用户提供一 对一的服务。本章分析了i n t e r n e t 发展现状和搜索引擎的不足，并在此基础上给出了本 论文的主要内容以及全文的内容组织结构。 1 1i n t e r n e t 概况 1 1 1 因特网发展现状 随着计算机技术和通信技术的发展以及用户对计算机白j 联网需求的不断增长，促 使i n t e r n e t 迅速发展，以中国为例，c n n l c ( c h i n ai n t e m e tn e t w o r ki n f o r m a t i o nc e n t e r ， 中国互联网络信息中心) 最新发布的第十九次中国互联网络发展状况统计报告数 据显示【l l 截止到2 0 0 6 年1 2 月3 1 日，中国的上网计算机总数已达5 9 4 0 万台，与去 年同期相比，增加了9 9 0 万台，增长率为2 0 0 ( 如图1 1 所示) 。根据最新统计数 据【2 】，截至2 0 0 7 年3 月1 9 日，世界总网民数量为1 1 1 4 2 7 4 4 2 6 ；网民平均普及率为1 6 9 ( 如表1 1 所示) 。可见世界各地上网计算机总数以及网民数都呈现出比较快的增长态 势。i n t e r n e t 发展如此迅猛，几乎没有人能预测它今后的发展规模。 2 0 0 n 1 22 0 0 1 1 22 0 0 2 1 22 0 0 3 1 22 0 0 4 j 22 0 0 5 1 22 0 0 6 1 2 数据来源：中国互联网络信息中心( c n n i c ) 图1 1 历次调查中国上网计算机总数 第】页 蕊姗舢姗姗姗。 郑州人学硕十学位论文 表1 1 世界互联网_ l j 户增k 及分布情况表 总人口占世界总人嘲民占人口占世界网民 2 0 0 0 年歪 地区最新嘲民数 2 0 0 7 年喇民 ( 2 0 0 7 年估计值)u 的比倒数量比率数量比率 增长率 竹洲 9 3 3 ，4 4 8 ，2 9 2 1 42 3 3 ，3 3 4 ，8 0 0 3 ，6 3 0 0 6 3 8 4 。 亚洲 3 ，7 1 2 ，5 2 7 6 2 4 5 6 5 3 9 8 , 7 0 9 , 0 6 5 lo 7 3 5 8 2 4 8 8 欧洲 8 0 9 ，6 2 4 ，6 8 6 1 23 3 1 4 。7 9 2 2 2 5 3 89 2 8 3 1 9 9 5 中东 t 9 3 a 5 2 l z 9 1 9 , 4 2 4 , 7 0 0 i n o 。1 7 。4 9 1 4 “ 北美 3 3 4 ，5 3 8 ，0 1 8 5 1 2 3 3 ，l8 8 ，0 8 6 6 9 7 2 0 9 0 , 41 1 5 7 拉荧及加 勒比地区 5 5 6 , 6 0 6 ，6 2 7 8 5 9 6 , 3 8 6 , 0 0 9 1 7 - 3 8 7 4 3 3 4 人洋洲 3 4 ，4 6 8 ，4 4 3 0 5 0 * 0 1 8 ，4 3 9 ，5 4 1 5 35 1 7 1 4 2 0 总诗6 , 5 7 4 , 6 6 6 , 4 1 7 l o 饥0 0 。, 4 l 。1 1 4 , 2 7 4 , 4 2 6 1 6 9 。1 0 0 0 0 2 0 氆7 + 从用户角度来看，i n t e r n e t 是一个全球计算机网络，它连通了大量独立的计算机。 无论机器是在自己的办公室，还是在远隔重洋的某地，用户都能够共享其中的资源。 从技术上看，i n t e m e t 是一个大型的计算机互联网络，它连接了众多规模较小的网络， 这些网络分别又由再小一些的网络互联而成，如此类推，形成一种树型的结构。 1 1 2w w w 工作机制 w w w 是一个分布在整个i n t e m e t 上的一个大型分布式多媒体信息系统，它采用 客户机服务器结构的工作模式，由w e b 服务器( w e bs e r v e r ) 、w e b 代理服务器( p r o x y s e r v e r ) 和客户机组成，图1 2 为w w w 系统结构示意图。在w w w 系统中，w e b 服务 器负责存储信息，是信息的提供者；w e b 代理服务器常用在设有防火墙的网络机器上， 负责将客户机发出的请求转发给远端的w e b 服务器，接收来自w e b 服务器的应答信 息并将该信息转发给相应的客户机；客户机是信息的使用者。 w e b 上的信息是以w 曲文档或页面的形式出现，文档中既包括文本、图片、声 音和影像等多媒体形式，也包括到其它w 曲页面的超文本链接。w 曲页面内容采用 超文本标记语言( h y p e r t e x tm a r k u pl a n g u a g e ，简称h t m l ) 来创建和识别，由于文 档的后缀为“h t m l ”，因而也称这些为h t m l 文档。w e b 服务器就是用来存放这些编 写好的w 曲文档，而浏览器就是用来接收和阅读这些文档的工具。 所有的w e b 文档或所有的w e b 页面都用一个唯一的地址标识，称为统一资源定 位器( u n i f o r mr e s o u r c el o c a t o r 简称u r l ) 。用户只需在浏览器中指明u r l ，相应的 文挡就会从w 西服务器上传输到本地机器并显示出来，用户随后可点击文档中的超 文本链接跳转到其它w 曲页面。每点击一个链接，浏览器就发出一个h t t p 请求。 第2 页 郊州人学硕十学位论文 w e b 服务器和客户机之日j 通过h t t p ( h y p e r t e x tt r a n s f e rp r o t o c a l ) 协议进行通信。 h r r p 协议定义了一系列的方法( g e t 、p o s t 、h e a d ) ，这些方法实现了客户机与服 务器之问的连接，发送请求、接收文件以及关闭连接等，其中最常用的是方法g e t 。 在w w w 系统中，当客户机想访问w e b 服务器上某个资源u r l ( u n i f o r mr e s o u r c e l o c a t o r 一统资源定位器) 时。便发出一个g e t 请求，向服务器请求该资源；代理 服务器收到客户机发的请求后，按照h t t p 协议格式对该请求报文进行解释和重组， 并代表源客户机向w e b 服务器请求资源( g e t ) 或提交数据( p o s t ) ，然后将w e b 服务 器的响应转发给源客户机。 c l i e n t 图1 2 w w w 系统结构示意图 1 1 3 搜索引擎面临的问题 w e bs e l v e a 互联网技术的飞速发展使信息的共享和发布跨越了时空的限制，网络成为人们获 取信息的重要来源。人们逐渐淹没在形形色色、各式各样的信息海洋中。那么，怎么 从互联网提供的信息海洋中快速、准确地找到自己需要的信息成为人们的难点，也成 为研究的熟点。在中国互联网络信息中，c , , ( c n n i c ) 于2 0 0 7 年1 月发布的第十九期中 国互联网络发展状况统计报告川中有如下的数据：过半的用户( 5 1 5 ) 经常使用的网络 服务是搜索引擎，在用户最常使用的网络服务中，搜索引擎排在第三，仅次于电子邮 件服务与浏览新闻。可见，大部分用户上网的目的还是希望能够从网上获得自己需要 的信息，但因特网上的信息是极其无序的，而且信息量越大，就越难被利用。因此， 用户通常利用搜索引擎来快速查找自己需要的信息，而避免劳丽无功。但由于搜索引 擎的通用性，不能满足不同背景、不同目的和不同时期的查询请求。搜索引擎的不足 使得网络用户的信息需求与现有的信息查询技术之问的矛盾日益尖锐。这些不足主要 表现在以下几个方面： 难以准确获得所需要的信息：由于w e b 数据是无结构的、动态的，并且w 曲页 第3 页 郑州人学硕十学伉论文 面的复杂程度远远超过了文本文档，给人们准确查找和定位所需要信息带来了极 大的困难。目前的搜索引擎普遍存在精度低和召回率低等问题。精度低主要表现 在当用户输入关键词检索信息时，返回的查询结果动辄成百上千条，而其中大多 数是一些与检索内容无关的信息，也包括一些死链接；召回率低是由于w e b 上大 量信息未被正确索引，因此导致搜索引擎返回的查询结果并不全面。 难以获得信息之间潜在的知识：多样的、海量的w e b 数据中蕴含着许多有用的、 潜在的、但不容易被发现的知识和模式。这些搜索引擎是办不到的，人们迫切需 要发现这些知识和模式的方法和工具。 个性化的信息服务：一方面，对于不同层次、不同爱好和使用目的的浏览用户需 要个性化的信息服务；另一方面，这个问题涉及到w e b 站点的管理、组织和经营。 w e b 站点的经营和管理者为了提高网站的声誉和效益，需要了解其客户需要什么 和想做什么。其中包括根据大多数客户的共同兴趣，开展有针对性的信息服务以 及对特定的用户开展个性化的信息服务和电子商务活动。这些搜索引擎同样是办 不到的。 1 2 课题的研究背景 由于w e b 信息的日益增长，人们不得不花费大量的时间去搜索、浏览自己需要 的信息。传统的i n t e m e t 服务为用户使用i n t e r n e t 资源提供了一些可行的途径。然而， 相对于巨大、无序的i n t e m e t 信息空间，每个用户真正感兴趣的信息非常有限，仅仅 是i n t e r n e t 信息空间的沧海一粟。在传统i n t e r n e t 服务模式下，为了找到真j 下感兴趣的 信息，用户要耗费大量的时间和精力。由于搜索引擎存在以上缺点，越来越不能满足 人们的需求，用户迫切需要一种能够根据用户的特点自动组织和调整信息的服务模 式，人们提出了需要个性化信息服务的要求。个性化服务作为一种崭新的智能信息服 务方式，能够按照用户的信息需求和兴趣，将用户需要的信息通过在线推荐、预取和 电子邮件等各种方式主动推送给用户，填补了网站和用户之问的信息鸿沟，因此迅速 成为信息服务领域的热点之一。 个性化信息服务是能够满足用户的个体信息需求的一种服务，即通过对用户个 性、使用习惯的分析而主动地向用户提供其可能需要的信息服务，它可以按照特定用 户群体和个人的需求定制内容和表现，也可以预测用户的需求，主动提供服务，其主 要的特点是“主动式服务”，是一个开放式的系统。目前常见的个性化信息服务主要 包括信息推送、智能代理、呼叫中心服务和实时个性化推荐等。 1 信息推送服务 信息推送服务是基于推送技术( p u s ht e c h n o l o g y ) 而发展起来的一种新型信息发布 技术，也就是网络公司通过一定的技术标准或协议，从网上的信息源获取信息，再通 第4 页 郑州人学硕十学位论文 过固定的频道向用户发布信息的技术。信息推送服务的基本过程是：首先由用户向系 统输入自己的信息需求，包括用户的个人档案信息、用户感兴趣的信息主题等；然后 系统自动或人工地在网上进行针对性的搜索；最后由系统定期地将有关信息推送至用 户主机上。常见的信息推送技术主要采用两种方法：一种是由智能软件完成的全自动 化的信息推送；另一种是借助于电子邮箱，并依赖于人工参与的信息推送。这里突出 的是信息的主动服务，即由从前的“人找信息”变成现在的“信息找人”。比起用户 自助式的网上搜索，信息推送服务的最大特点是只需用户一次输入信息需求，就能够 定期地不断接收到最新的相关信息。 2 智能代理 美国麻省理工学院( m i t ) 媒体实验室软件代理研究所小组认为，“智能代理是一种 能够完成委托任务的计算机系统”，例如航班预定、在线书店图书预定等。这不同于 普通软件，智能代理可以快速便利地在因特网上寻找用户所需的信息。人们认为，智 能代理以及其自动搜索处理是一种未来的搜索引擎。在未来，单个用户可以依赖智能 代理技术进行搜索，数据库添加新记录时能自动通知用户，这样就会由一个静态的系 统变成一个有效的由用户驱动的动态信息资源。未来的因特网是一种由智能代理交互 驱动的网络。 3 实时个性化推荐 实时个性化推荐被用来帮助用户在大量的信息中寻找感兴趣的内容，它体现的 “个性化”服务目前越来越为商务网站、电子图书馆等众多领域所接受，并且成为了 它们的一个重要功能。对服务提供方而言，他们需要好的自动辅助设计工具，根据用 户的访问兴趣知识动态地调整页面拓扑结构，改进现有的信息服务，开展有针对性的 电子商务，以更好地满足访问者的需求；对访问者而言，他们则希望看到个性化的页 面，希望得到更好的满足各自需求的服务，希望从具有类似访问兴趣的其他一些用户 的访问行为中得到有价值的启发知识。实时信息推荐服务通过收集和分析用户信息来 学习用户的兴趣和行为，从而实现主动推荐的目的。 4 呼叫中心服务 呼叫中心是一种新近发展起来的专门提供一对一服务的个性化系统，它是集电 话、传真机、计算机等通信设备和办公设备于一体的交互式增值业务系统。用户可以 通过电话接入、传真接入、m o d e m 拨号接入和访问因特网网- 站等多种方式进入系统， 在系统自动语音导航或人工座席的帮助下访问其数据库，获取各种咨询服务信息或完 成相应的事务处理。目前，呼叫中一f i , 将更多地引入客户关系管理( c r m ) ，比如通过建 立客户数据库，对信息进行统计分析、处理、采掘和提炼，使呼叫中心业务代表可以 得到每个客户的详细信息，如过去交往记录和客户爱好等，由此可为用户提供一对一 服务，并能大大节省通话时间。大家熟知的8 8 4 8 客户中心就使用了最先进的c t i 呼 第5 页 郑州人学硕十学何论文 叫中心系统，不仅极大提高了服务的质量，缩短了服务的响应时间，而且充分发挥了 与客户之间互动的优势。 本文的工作是对基于用户网络访问行为的个性化推荐预测模型进行研究，为用户 推荐用户需要的信息，提供个性化的服务。通过对代理服务器保存的用户行为同志进 行挖掘，根据用户以前在网上留下的痕迹建立预测模型，来预测用户下一步最可能访 问哪个网页。 1 3 研究内容 随着w w w 的迅速发展和网络用户的急剧增加，准确预测w e b 用户的访问行为 对减小用户的感知延时、处理亟待解决的信息过载问题等具有重要的作用。如何准确 地预测用户的网络访问行为是个性化服务研究的一个重要方面。影响预测性能的因素 很多，比如缓存大小、所用推荐方法等。准确评价个性化推荐模型的性能对模型的设 计极其重要。 本文的主要工作及创新点： 1 详细地讨论了w e b 缓存系统中命中率与字节命中率之间的关系，提出了一种 新的w e b 缓存性能评价指标：命中比( 阳r ) ，讨论了该指标在w e b 缓存替 换算法及w e b 预取性能评价中的应用，从而为度量缓存系统的性能提供参考 依据； 2 提出了一种基于网络访问行为的混合阶m a r k o v 预测模型( h m p m ) ，使用模式 树压缩存储访问序列，将前缀相同的序列共享存储，降低了状态空间复杂度； 3 使用两种推荐方法，即精度投票方法和选取最高推荐值的阶方法来改进预测 结果。实验结果表明，h m p m 模型在一定程度上提高了预测准确率和查全率。 1 4 论文组织 本文的内容组织如下： 第一章为绪论部分，主要介绍i n t e m e t 发展现状、w w w 工作机制、搜索引擎面 临的问题、课题的研究背景以及论文的主要内容。 第二章介绍个性化推荐技术基础，包括序列模式挖掘基础知识：序列模式的概念、 特点以及序列模式挖掘比较经典的算法和w e b 预取技术基础知识：时间局部性概念、 w e b 预取技术基本概念、分类和现有的预取算法，接着介绍了个性化推荐技术的概念 与国内外研究现状。 第三章讨论了w e b 缓存概述、替换算法、w e b 缓存与传统缓存的区别、个性化 推荐性能评价指标，详细地讨论了w e b 缓存系统中命中率与字节命中率之间的关系， 第6 页 郑州人学硕十学位论文 并在此基础上提出了一种新的w e b 缓存性能评价指标：命中比( f b r ) ，讨论了该指 标在w e b 缓存替换算法及w e b 预取性能评价中的应用，从而为度量缓存系统的性能 提供参考依据。 第四章首先介绍了m a r k o v 模型，接着讨论了传统m a r k o v 模型以及混合阶m a r k o v 模型，并在此基础上提出了一种新的混合阶m a r k o v 模型( h m p m ) ，将前缀相同的序 列共享存储，降低了状态空问复杂度。实验表明，该模型在一定程度上提高了预测准 确率，查全率也有所提升。 第五章是结论与展望。总结本论文工作，并提出需要进一步研究的问题和方向。 第7 页 郑州人学硕十学位论文 第二章个性化推荐技术基础 目前很多个性化推荐系统处理的对象都是序列，本文研究的基于网络访问行为的 个性化推荐模型，处理的对象是用户会话序列，对用户的访问行为进行分析，利用序 列模式挖掘出w e b 同志中用户的访问模式，既可以用于服务器端优化w e b 网站的结 构，也可以用于代理服务器或客户端预测用户访问页面，采取预取技术减少w 曲访 问的延迟。本章主要介绍相关的理论基础知识：序列模式的基本概念、w e b 预取技术 以及个性化推荐技术相关概念。 2 1 序列模式 2 1 1 序列模式简介 序列模式的相关定义如下： 定义2 1 设非空集合，= “i 2 i 是问题域内所有项的集合。项集就是项的 集合，即，的一个子集。一个序列就是一系列有序的项集，记为s = ( 毛，j ：j 。) ， 其中5 ，是一个项集，即对l j m ，。，i 。5 ，也称序列的一个元素，记作( 而，x 2 ，- x m ) ， 其中以是一个项，即对于1 k m ，x k i 。如果元素中只有一个项，例如元素( 工) ， 则可以简写成x 。任何项在一个序列的每个元素中最多可以出现一次，但可以出现在 一个序列的不同元素之中。 定义2 2 一个序列中项的个数定义为这个序列的长度，长度为，的序列叫做，一序 列。序列中项目的个数称为这个序列的大小。 定义2 3 两个序列口= ( a l a 2 以) ，= ( b i b 2 屯) ，如果存在正整数 1 s j 2 s m ，使得q 量b j l ，口2 b j 2 ，a 。6 m ，则称口是的一个子序列， 是口一个的超序列，记作口。若s 包含在一个数据序列中，称该数据序列支持j 。 定义2 4 一个序列s 的支持度s u p p ( s ) 记为所有包含j 的数据序列的总数与d b 中 的数据序列总数之比。最小支持度m i n s u p p 是一个阈值，一般由用户指定，满足 s u p p ( s ) m i n s u p p 称之为频繁序列或序列模式。长度为k 的模式称为k 一模式。 序列模式挖掘( s e q u e n t i a lp a t t e r nm i n i n g ) 是指挖掘相对时间或其他模式出现频率 高的模式。待挖掘的数据集称为序列数据库( s e q u e n c ed a t a b a s e ) 或事务数据库，序列数 据库中每条记录是一个事件序列，是一组按事务时间或其它次序顺序排列的事务。序 列模式挖掘问题是数据挖掘中最重要的研究课题之一，利用序列模式挖掘可以得到序 列数据库中的频繁序列，实现知识的提取。 序列模式挖掘的研究主要针对符号模式( s y m b o l i cp a t t e r n ) ，而数字曲线模式通常 第8 页 郑州大学硕+ 学位论文 属于统计时序分析中的趋势分析和预测范畴。现实世界中大量数据和应用与时间相 关，例如：顾客的消费模式，在三个月内，顾客首先购买计算机，然后购买软件和光 驱；地震、龙卷风等自然灾害的发生，也有其固有的模式和征兆；对于不同的疾病， 有相应的诊断与治疗模式；股票市场随时问波动的模式；用户对网站的访问模式；d n a 序列所具有的模式。网站为了吸引更多的用户，不仅需要分析用户在访问过程中最喜 欢看哪些内容，还需要分析用户在浏览某些内容之后，接下来会访问哪些网页；分析 用户每次访问的网页间的联系，这就导致了序列模式挖掘的产生。因此，序列模式挖 掘具有广泛的应用前景和应用价值。 序列模式挖掘是数据挖掘中最重要的任务之一，a g r a w a l 3 1 等最先提出在事务数据 库中发现序列模式的问题，此后，许多研究人员对此进行了大量的研究工作，提出了 许多有效的方法和算法”埘。目前，对序列模式的研究主要集中在访问事务数据库中 的序列模式的发现上，对w e b 环境下的序列模式发现研究相对较少。而利用序列模 式挖掘出w c b 同志中用户的访问模式，既可以用于服务器端优化w e b 网站的结构， 也可以用于代理服务器或客户端预测用户访问页面，采取预取技术减少w c b 访问的 延迟。 a g r a w a l 和s r i k a n t l 3 1 首先提出序列模式定义是针对多用户事务的数据挖掘方式， 他所提出的事务集( i t e m s e t s ) 只是简单地按照时问排序，并没有引入序列的持续时间 ( d u r a t i o n ) 、事件重叠窗1 2 1 ( e v e n t f o l d i n g w i n d o w ) 、间隔( i n t e r v a l ) 等参数概念，因此时间 上的内涵不够充分。文献【6 】提出了w 曲访问路径模式挖掘，其中的最大前向路径挖 掘( m a x i m u mf o r w a r dr e f e r e n c e ) 步骤，目前已经成为w e b 同志序列模式挖掘中的关键 一步。目前的绝大多数序列模式挖掘算法都采用种宽度优先的搜索模式，如 a p r i o r i a l l 、g s p 等等。 2 1 2 序列模式挖掘的特点 序列模式挖掘与关联规则挖掘及时间序列数据挖掘有许多相似之处，因此通过将 序列模式挖掘与关联规则挖掘及时间序列挖掘之间的比较来说明序列模式挖掘的特 点。 序列模式挖掘与关联规则挖掘 序列模式挖掘的许多概念和算法都是由关联规则挖掘延伸发展而来的，它们之间 有许多相似之处。序列模式与关联模式相仿，而把数据之间的关联性与时间联系起来。 为了发现序列模式，不仅需要知道事件是否发生，而且需要确定事件发生的时间。关 联规则挖掘所需要解决的问题是发现哪些商品是顾客喜欢一起购买的，顾客在一次交 易中购买某些商品后还会购买哪些商品，是发现交易的内部规律的过程，从而使得售 货商能够更好地安排他的货架上的商品。而序列模式数据挖掘所要解决的问题是顾客 第9 页 郑州大学硕十学位论文 在完成一次交易后，在满足时问约束的条件下，顾客接着可能购买什么商品，是发现 交易之问的规律的过程，使得售货商能够根据当前的售货情况来预测以后的售货情 况，从而能够更好地安排库存。 序列模式挖掘与时间序列模式挖掘 序列模式挖掘与时间序列模式挖掘在概念上很容易被混淆，但是如果从挖掘的数 据对象和挖掘的目标来看，很容易区分它们。时间序列模式最早是统计学上的一个概 念，后来被数据挖掘所采用，并增加了新的内容。时间序列模式挖掘的数据是对研究 对象的一个或一组变量进行观察测量，在一系列时刻所得到的观测值，这些观测值与 时间是紧密相关的，可以用函数坟t ) 来描述这些测量值。时间序列模式挖掘的主要目 标有趋势预测、相似性搜索、周期分折等。序列模式挖掘的数据是研究对象所发生的 某一类事件的顺序集合，目标是研究这些事件的先后关系，找出事件所发生的先后规 律。序列模式挖掘中的时问约束是为了更好地约束事件之问的先后关系，而不是规定 事件在时间上的变换。 2 1 3 序列模式挖掘算法 序列模式挖掘的方法有很多，比较经典的算法有三种：g s p ( g e n e r a l i z e ds e q u e n t i a l p a t t e r n s ) 算法、p r e f i x s p a n ( p r e f i x p r o j e c t e ds e q u e i l t i a lp a t t e r nm i n i n g ) 算法和 s p a d e ( s e q u e n t i a lp a t t e r nd i s c o v e r yu s i n ge q u i v a l e n c ec l a s s e s ) 算法。 g s p 算法是序列模式概念的提出者r a g r a w a l 和r s r i k a n t 在a p r i o r i a l l 算法的基 础上提出的，是基于通过候选项集找频繁项集的理论，需要多次扫描数据库。 p r e f i x s p a n 算法是建立在投影数据库的概念基础之上的，采用分治的思想，不断 产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式。 s 队d e 算法将序列数据库由水平格式变成垂直格式，并在新的格式上进行序列 模式挖掘。它利用等价类别( e q u i v a l e n c ec l a s s ) 的观点，将原始的问题分解成若干个较 小的子问题，以便能更有效地使用网格式搜索策略和简单的链接操作，独立地在主存 储器中运行。所有的序列模式只需在三次扫描序列数据库后即可得到。 2 2w e b 预取技术 2 2 1 空间局部性 在存储系统中，“相邻”的概念可以用存储地址来明确地定义，但在w e b 系统中 却没有这么明确。通常的定义是：如果访问对象a 之后访问对象b 的可能性很大， 就认为a 和b 是相邻的。也就是说，可以用l 阶m a r k o v 模型来描述一个w e b 系统， 而对象之间的“距离”和转移概率成反比。 第1 0 页 郑州人学硕十学位论文 空问局部性的含义是：与过去经常被访问的对象“相邻”的对象在将来可能被访 问。可以用以下方法验证一个访问日志中是否存在空间局部性：先统计该日志中k 请 求序列的个数( 重复的序列只统计一次) ，然后将日志中所有请求的前后顺序随机打乱， 再统计打乱的同志( 它保留了文档受欢迎程度的特性，但破坏了请求之间的相关性和 可能存在的空自j 局部性) 中k 请求序列的个数( 重复的序列仍然只统计一次) ，如果原来 的日志中存在空间局部性，那么后者必然大于前者。文献【7 】对波士顿大学计算机科学 系w 曲服务器一个星期的访问日志进行了统计，验证了该结论。 由于w e b 访问具有空间局部性，所以相同的访问序列可能反复出现，如果能记 忆这些序列，就可以对用户的请求作某种程度的预测。空问局部性越明显，相同访问 序列反复出现的可能性越高，预测的准确性也越高。 2 2 2 预取概述 随着i n t e r n c t 的迅速发展，互联网用户的急剧增加，导致用户延迟的因素有网络 带宽、网络固有的传输延迟、数据丢失以及客户端和服务器的负载情况。解决网络拥 塞问题就显得重要了。为了缓解这种情况，人们提出了w e b 缓存( w e bc a c h i n g ) 和网 页预取技术( w e bp r e f e r c h i n g ) ，用于降低用户的访问延迟，提高w e b 服务器的服务质 量。缓存技术是基于w w w 访问的时间局部性，应用在客户端的浏览器和本地代理 服务器中，将己经访问过的w 曲文档保存起来，从而避免再次访问己经访问过的文 件时，又向远程服务器发请求。当w e b 资源频繁地发生变化时( 如动态产生的w e b 文 件) ，缓存技术解决延迟问题的效果不再明显。w e b 预取技术是基于用户访问的空间 局部性，是一种延迟容忍( l a t e n c y t o l e r a n t ) 技术。延迟容忍的基本思想是当高延迟 事件在进行时，允许处理器执行别的任务，延迟时间被并行的计算时阃所隐藏。预取 对于那些常见的数据访问模式非常有效，通过分析用户访问历史记录，利用数据挖掘 技术挖掘出用户的访问模式，主动预测用户可能浏览的页面，将预测结果结合到缓存 替换策略当中，从而减少用户的访问延时。网页预取又称为主动缓存技术。 2 2 3 预取分类 预取总是和缓存一同工作的，所以和缓存一样预取的实施位置可以在客户端、代 理服务器端和w 曲服务器端，如图2 1 所示，图中c s 代表客户机与服务器之间的通信， c p 表示客户机与代理服务器之问的通信，p s n 表示代理服务器与w 曲服务器之