（计算机系统结构专业论文）一种网站个性化系统的设计.pdf

摘要 摘要 新信息、新产品、新服务大都在不断被推上w e b ，同时，用户的种类、数量和 关注点也在增加。一方面，用户己经疲于以“人海扮针”的方式搜寻信息，另一 方面w e b 网上的服务商也在不断设法获取用户的兴趣爱好，以填补用户和网站之 间的信息鸿沟。个性化技术就是基于这种需要产生的。传统个性化技术( 如c f 技 术、基于内容过滤技术) 中存在着一些限制，如处理大数据量的能力差、依赖于用 户的登记信息，不能获取w e b 对象之间丰富的语义联系等。为解决传统技术中出 现的这些问题，将w e b 使用日志的挖掘应用到个性化技术中。 本文提出了一个基于序列模式挖掘的个性化技术，它使用概念格( c o n c e p t l a t t i c e ) 作为存储频繁序列的数据结构。序列模式挖掘就是发现序列数据库中的频繁 子序列作为用户感兴趣的模式。概念格适用于挖掘包括序列模式在内的各种知识。 依据序列模式发现的特点，频繁概念格可以改善模式发现的时空性能。 关键词：序列模式概念格日志挖掘个性化 a b s t r a c t a b s t r a c t e v e r yd a y , n e wi n f o r m a t i o n ，p r o d u c t sa n ds e r v i c e sa r eb e i n go f f e r e db yp r o v i d e r s o n t h ew o r l dw i d ew e b a tt h es a m et i m e ，t h en u m b e ro fc o n s u m e r sa n dt h ed i v e r s i t yo f t h e i ri n t e r e s t si n c r e a s e a sar e s u l t ，p r o v i d e r sa r e s e e k i n gw a y s t oi n f e rt h e c u s t o m e r s i n t e r e s t sa n dt oa d a p tt h e i rw e bs i t e st om a k et h ec o g e n to fi n t e r e s tm o r e e a s i l ya c c e s s i b l e p r o p o s a lh a v es u g g e s t e dw e bu s a g em i n i n ga sa ne n a b l i n gm e c h a n i s m t oo v e r c o m et h e p r o b l e ma s s o c i a t e d w i t hm o r et r a d i t i o n a lw e bp e r s o n a l i z a t i o n t e c h n i q u es u c ha sc o l l a b o r a t i v eo rc o n t e n t b a s e df i l t e r i n g t h e s ep r o b l e m si n c l u d el a c k o fs c a l a b i l i t y ，r e l i a n c eo ns u b j e c t i v eu s e rr a t i n g s ，a n dt h ei n a b i l i t yt oc a p t u r ear i c h e rs e t o fs e m a n t i cr e l a t i o n s h i p sa m o n go b j e c t s ， i nt h i s p a p e r w e p r e s e n t a n s e q u e n t i a l - - p a t t e r n - - b a s e d r e c o m m e n d a t i o n s y s t e m ，w h i c he x t r a c tu s a g ep a t t e m sf r o mw e bl o gf i l ea n d r i s et h ec o n c e p tl a t t i c ea si t s d a t as t r u c t u r es t o r i n gf r e q u e n ts e q u e n c e s s e q u e n t i a lp a t t e r nm i n i n g ，w h i c hd i s c o v e r s f r e q u e n ts u b s e q u e n c e sa si n t e r e s t i n gp a t t e r n s i nas e q u e n c ed a t a b a s e t h ec o n c e p t l a t t i c ei ss u i t a b l et od i s c o v e rv a r i o u s k n o w l e d g ei n c l u d i n gs e q u e n t i a lp a t t e r n s c o n s i d e r i n gt h ec h a r a c t e r so ft h es e q u e n t i a lp a t t e r n sm i n i n g ，f e q u e n tc o n c e p tl a t t i c e c a l li m p r o v et h em i n i n ge f f i c i e n c y k e y w o r d ：s e q u e n t i a lp a t t e r nc o n c e p tl a t t i c e l o gm i n i n gp e r s o n a l i z a t i o n 创新性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及所取得的 研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文 中不包含其他人已发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我一起工作的同志所做的任何 贡献均己在论文中做了明确的说明并表示了谢意。 本人签名：高弦 日期：丝! ：! 立 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：学校 有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或 部分内容，可以允许采用影印、缩印、或其它复制手段保存论文。 ( 保密后的论文在解密后遵守此规定) 本人签名： 导师签名： 蔷丞圃盟 丛 日期： e t 期：型：! ：j 第一章绪论 第一章绪论 1 1 研究的背景 随着信息高速公路的发展和普及，人们已经被包围在信息的汪洋大海之中。 i n t e r n 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 m e t 从被动接受浏览者的请求转化为主动感知浏览者的信息需求，实现 i n t e m e t 系统对浏览者的主动信息服务。新一代的信息服务将是个性化主动信息 服务。如何从海量的数据和信息中高效地获取有用知识，如何从迅速爆炸的信息 中及时地获取最新信息，如何提高信息检索与推送的智能水平，以及如何满足各 种用户不同的个性化需求等，都是新的信息服务系统面l 临的挑战性课题。个性 化主动信息服务将是未来信息服务的主流模式，它实现的是“信息找人，按需服 务”。其实现途径就是通过对用户信息需要、兴趣爱好和访问历史的收集和分析， 建立用户模型，并将用户模型应用于网上信息的过滤和排序，从而指导用户的浏 览过程和信息检索，或向用户主动推送信息。用户概貌( p r o f i l e ) 即是为用户建 立的个性化模型。可以理解为用户的信息需要、用户的兴趣领域或主题，用户的 访问方式、思维方式等等，或者是它们的结合。也可以是一些用户需要的特殊信 息的相关背景，比如说，被请求的知识的类型或者用户的背景知识。个性化信息 服务系统可能是一个具有智能的w e b 工具，也可能是个性化的网站、个性化信息 代理。用户的个性化模型也广泛应用于电子商务的个性化服务中。具有智能的w e b 工具被用来帮助用户检索、定位和管理w e b 文档。智能水平高的w e b 工具，能 学习产生用户概貌，并能使用用户概貌进行推理，对用户和信息源的行为进行学 习。站点的个性化就是针对特定的用户建立相应的w e b 内容和应用。这就要收集 和存储站点访问者的信息，并分析这些信息。在此基础上，向每一个访问者在恰 当的时间传送恰当的信息，即个性化地发布新闻、推荐文档、提供建议、发送w e b 一种网站个性化系统的设计 信息、播送广告、推销产品等。总之，i n t e r n e t 上的个性化信息服务系统必须具 有三个能力，即用户概貌能很好地反映用户的兴趣嗜好；为适应用户嗜好的变化， 用户概貌能做适应性的改变：自动开发新的信息领域，主动向用户提供推荐服务。 网络技术近年取得了突飞猛进的发展，越来越深远地影响着人们的日常生活 和工作。因特网作为一种新的大众传媒，由于其快速，方便而受到人们的普遍欢 迎。电子商务，信息共享，教育科研，电子邮件等等服务使因特网成为浩瀚的信 息海洋。万维网是到目前为止世界上最丰富和最密集的信息来源。对于这个世界 上最丰富和最密集的信息来源，如何开发和利用这些丰富的资源就成了人们普遍 关注的问题。于是，数据挖掘技术和网络应用研究的结合w 曲数据挖掘技术 ( w e bm i n i n g ) 构成了当今比较活跃的一个研究领域。w e b 数据挖掘技术是近年 一个很热的研究课题，它是数据挖掘技术在网络信息处理中的应用。w e b 挖掘技 术主要包含了w e b 的内容挖掘、结构挖掘和使用挖掘。他们分别挖掘w e b 站点 文件内容、结构以及站点使用信息。目前国际上对w e b 使用挖掘的研究比较多，w e b 使用挖掘通过挖掘w e b 浏览记录来发现有意义的信息。例如有多少人访问了该页 面，他们从哪里来，那些页面最受欢迎等。它可广泛地应用于个性化服务、系统 改进、站点修改、商业智能和浏览推荐等方面。综合而言，w e b 使用挖掘具有以 下几个方面的益处：为用户提供个性化的服务。根据用户的访问历史，动态地向用 户推荐商品。在电子商务网站上进行个性化营销，具有很大的商业价值。提高系 统效率。随着w w w 的通信量的增加，影响网站用户满意度的主要原因除了w e b 站点的内容外，其服务效率也很重要。通过w e b 使用挖掘，可以提供网站服务效 率全方位的信息。从而有助于找到平衡服务器负荷，优化传输，减少拥塞的方法， 缩短用户等待时间，提高系统效率和服务质量。提高网站结构设计。w e b 结构的 复杂度在飞速的发展着。因此，w e b 站点和w e b 服务器的设计和维护难度也在增 加着，通过w e b 使用挖掘提供的用户使用信息，可以帮助网站设计者确定如何修 改网站结构。 1 2 国内、国外研究现状 国内外关于个性化信息服务的研究很多，而且个性化的研究是和人工智能及 其主体、多主体系统( m a s ) 的研究及数据开采的研究相结合的，有不少成功的 系统。s m a r t p u s h 系统根据用户的个性信息向用户递送电子数据，这些数据是由 芬兰一家大报纸提供的。w e b w a c h e r 是一个非常著名的导航器。它使用一个称为 信息查找助理的主体，引导用户在网上的浏览过程。该系统通过对用户选择“链 路”或站点进行跟踪学习，学习产生哪一超链是可能到达目标信息的知识，通过 采用这些知识来帮助用户定位希望的信息，改善导航质量。a l e x a ( w w w a l e x a c o i n ， 第一章绪论 w w w a l e x a c o m s u p p o r t t e c h n o l o g y h t m l ) 系统收集用户的使用方式，作为对站点的 质量评估的原始资料，以此为基础，来决定相关的链接，提供推荐服务。l e t i z a 系统用于在用户浏览时向用户建议用户可能感兴趣的链接，这些链接与用户当前 访问的页面内容有关。p r o f u s i o n p e r s o n a l a s s i s t a i n t 是一个信息过滤工具，它使用 用户明确的相关度反馈决定用户感兴趣的领域，以此为据，将元搜索引擎 p r o f u s i o n 返回的结果进行过滤，决定哪些结果提交给用户，哪些抛弃。德国的 a l e x a n d e rp r e t s c h n e r 和美国的s u s a ng a u c h 一起研究基于o n t o l o g y ( 作为概念层 次) 的个性化搜索。用户的个性化模型( 用户概貌) 建立为单个用户在w e b 上浏 览历史的函数，是一个由大约4 3 0 0 个节点( 使用向量空间模型) 组成的加权概 念层次，用户概貌根据用户在某一页面上停留的时间和页面的长度进行修正。该 系统目标是通过搜索结果与用户概貌的匹配来重排序和过滤搜索结果，从而提高 搜索系统的性能。“概貌( p r o f i l e ) ”工程( o e n k a m p ，s c h o m a k e r ，v a nb o m m e l ，& v a nd e rw e i d e1 9 9 6 ) 是计算科学协会( c s i ) 和( n o m e g e n ) 认知和信息协会( n i c i ) 的一个合作研究项目，其目标是通过使用对文档和用户概貌的更丰富的描述而不 是关键词来提高检索文档的质量，开发一个对w w w 能动的多主体过滤器。用户 概貌用于支持提供一个额外的过滤器和对查询的语义扩展。i n t e m e t 的信息推送 技术，也被称为“网播( n e t c a s t ) ”，它利用信息推送软件，向i n t e m e t 的广大用 户，主动地发布、推送各种新闻、财经、体育等信息。“网播”实现主动性的途 径包括电子邮件、预留宿主网页、推送( p u s h ) 到指定频道、个人信息代理、与 寻呼机通信等等。 m i c r o s o r 和n e t s e a p e 的w e b 浏览器都支持信息推送模式， 如微软的频道将最喜爱的w e b 站点内容直接传送到计算机，用户可以脱机阅读 信息以减少下载文件和访问繁忙w e b 服务器的时间，频道可确保用户跟踪最新 的w e b 内容，预订频道之后，内容将显示在桌面上，内容提供商定期更新此内 容。p o i n t c a s ti n c 等公司还开发了一些网上信息推送软件，如p o i n t c a s tn e t w o r k 等。我国的网络软件“资讯天使( w e b a g e n t ) ”也具有信息推送功能。但这些信 息推送技术都没有建立用户模型，因而不能很好地满足用户的信息需要。 数据挖掘技术促成了数据库中的知识发现f k d d ：k n o w l e d g ed i s c o v e r yi n d a t a b a s e s ) ，1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会议提出主办的 k d d 国际研讨会已经召开了7 次，规模由原来的专题讨论会发展到国际学术大 会，人数由二三十人到七八百人，论文收录比例从2 ：1 到6 ：1 ，研究重点也逐渐从 发现方法转向系统应用，并且注重多种发现策略和技术的集成，以及多种学科之间 的相互渗透。其他内容的专题会议也把数据挖掘和知识发现列为议题之一，成为当 前计算机科学界的一大热点。目前，w e b 挖掘的有关问题在相关领域有过很多研 究讨论。由于w e b 上存在大量信息，并且w e b 在当今社会扮演越来越重要的角色 有关w e b 内容挖掘、w e b 日志挖掘和因特网上的数据挖掘服务，将成为数据挖掘 一种网站个性化系统的设计 中一个最为重要和繁荣的子领域。w e b 数据挖掘利用数据挖掘技术从网络文档和 服务中发现和提取信息。w e b 上各种形式的文档和用户访问信息就构成了w e b 数据挖掘的对象。如前所述，根据挖掘对象的不同w e b 数据挖掘分为内容挖掘， 结构挖掘和访问信息挖掘3 大类，而目前国内外基于w e b 日志的用户访问模式挖 掘又可以分为3 类：1 分析站点性能，主要从统计学角度对频繁模式等进行发掘， 很多商用工具及有些免费工具属于此类；2 理解用户意图，c h e n 等提出的路径 游历模式( p a t ht r a v e r s a lp a t t e r n ) 发现算法等就是此类代表； 3 改进站点设计，通 过频繁路径、用户聚类，重构站点之间连接关系，适应用户访问习惯，提供个性 化信息服务。c o o k i er 等人开发的w e b m i n e r 就属于这方面的应用。现在世 界上有许多著名的w e b 数据挖掘方向的公司：n e t p e r c e o t i o n 公司，他们的主要 产品是n e t p e r c e r p t i o n s ，它采用了“实时建议”的技术：让产品对象( 主要是网站) 能够根据用户以往的浏览行为( 包括这次的c l i c k t h r o u g h s 和以前的购买记录) ， 在其他用户( 称做c o m m u n i t y ) 中找出与他有相类似浏览行为的，根据这些用户 的浏览行为来预测该用户以后的浏览行为，从而为用户提供个性化的浏览建议， 其预言有很高的准确性。并且它是实时运行的，随着浏览量的增加，它会变得越 来越“聪明”。a c c r u e 公司主要有两大产品：a c c r u ei n s i g h t 和a c c r u eh i tl i s t 前者主要是帮助顾客解决电子商务方面的问题，后者主要是用于网站流量分析 的。a c c r u ei n s i g h t5 是一个综合性的w e b 分析工具，它能够对网站的运行状况 有个深入，细致和准确的分析，利用了多种w e b 数据收集方法，包括a d v a n c e d n e t w o r kc o l l e c t o r s e r v e rc o l l e c t o r s 和w e bs e r v e rl o gf i l e s 。a d v a n c e dn e t w o r k c o l l e c t o r 以其能收集到最大量的数据而著称，它能够收集到w e bs e r v e r 日志里 所得不到的信息，a c c r u ei n s i g h t5 运用了一种口q 做“s e r v e rc o l l e c t o r ”的分析方 法，它支持镜象服务器和负载平衡，路由器和一些其他网络结构设备，能够将一 些加密的地址转化为可分析的形式。a c c r u eh i tl i s t 是表分析工具，适合于中型 网站，目前的版本是a c c r u eh i tl i s t4 5 1 。它主要运用在市场分析，搜索引擎， 广告等方面w e b t r e n d s 公司的重要产品是c o m m e r c e t r e n d s3 0 ，c o m m e r c e t r e n d s 提供“b r o w s e r - b a s e d ”方法，使得不同的部门( 从市场部门到分析家) 能在任 何时间得到他所想得到的个性化报表。它利用了数据仓库技术，根据其提供的数 据产生访问者的行为模式。在w e b 用户访问信息挖掘的理论研究方面国内外学 者也进行了大量研究工作。 b o r g e sj , l e v e n em 等人应用超文本概率文法 ( h y p e r t e x tp r o b a b i l i s t i eg r a m m a r ) 发现用户迁移模式，并用g r a m m a r 的熵值评估挖 掘到的模式。s h a h a h i 等人提出的日志挖掘系统依赖于客户端的数据收集，客户 端的代理为服务器返回用户请求的页面及时间等数据。中国科学院数学研究所周 龙镶教授等人，提出了有关w w w 浏览路径的一些基本概念，设计了基于用户访 问模式的浏览路径优化算法；清华大学马少平教授等人，提出n 元预测模型对 第一章绪论 用户未来可能进行的w e b 访问请求进行预测。 1 - 3 问题的提出 现实生活中有许多按时问进行排序的事件序列，例如一位顾客对某超市的购 买活动序列：网络用户对w e b 站点的访问序列等等。网站为了吸引更多的用户， 不仅需要分析用户在访问过程中最喜欢看哪些内容，还需要分析用户在浏览某些 内容之后，接下来会访问哪些网页：分析用户每次访问的网页间的联系，这就导致 了序列模式挖掘的产生。序列模式的挖掘是指挖掘相对时间或其他模式出现频率 高的模式。序列模式本质上可视为时态数据库( t e m p o r a ld a t a b a s e ) 上的关联规则，其 目标是发现事件间( i n t e r e v e n t ) 的模式( 序列) ，而关联规则是发现事件内的模式( 称 为项集) 。序列( s e q u e n c e ) 是项集的有序表，项集就是项的非空子集。一个项可以出 现在多个项集中，但一个项只能在一个项集中出现一次，也就是一个项集中不能 包括多个相同的项，一个项集中项的顺序可以是任意的。序列模式挖掘是一个非 常重要的数据挖掘问题，有着广泛的应用，包括顾客购买模式或w e b 访问模式分析， 序列或时间相关过程如科学实验、自然灾害、疾病治疗等的分析，d n a 序列分析 等等。 从数学的角度理解形式概念分析，对于任意两个集合之间的某种二元关系 ( b i n a r yr e l a t i o n s h i p ) r ，形式概念分析提供了一个与r 一一对应的、无冗余的 格( l a t t i c e ) 对r 进行可视化，从而提供了一种一般的分析二元关系的数学方 法。形式概念分析理论是基于g a r r e tb i r k h o f f 的格理论建立起来的，其基本思想 是：对于任意给定的两个集合，考查任意一个在这两个集合之间的二元关系，通 过给出一个在两个集合的幂集之间的一个g a l o i s 连接，可以得到一个新的集合， 进一步可以得到一个半序集，b i r k h o f f 证明了这个半序集是一个完备格；另一方 面，根据这个的完备格，仍可以得到原来的二元关系。因此，由形式概念分析得 一到的结果结构化的描述了原有的二元关系。其次，从哲学的角度理解形式概念分 析。形式概念分析反映了概念( c o n c e p t ) 的哲学理解，其核心数据结构概念 格( c o n c e p tl a t t i c e ) 准确而简洁的描述了外延( e x t e n t ) 和内涵( i n t e n t ) 之 间的联系，表明了概念之间的泛化和特化的关系。哲学中，概念被理解为由外延 和内涵两个部分组成的思想单元。任何一个概念都是在某一个特定的背景环境下 建立起来的，这个环境中的某些个体组成的集合构成了概念的外延，同时在这个 环境下考察的所有特性的某个子集构成了这个概念的内涵：内涵是在外延中的所 有个体在这个环境中所具有的共性，同时外延是内涵中的所有特性在这个环境中 的所有的共例。同个环境中可能会产生有多个不同的概念。这些概念都是从一 个最大的、“包罗万象”的概念通过加入对某些特性的考虑得到的。显然，在这 一种网站个性化系统的设计 个背景环境中，概念的内涵越丰富，这个概念的外延就越小，因此概念不断特化 的最终结果一定是所有的概念归结到一个“具有所有的属性”的、最小的概念中 来，这个最小的概念可能在这个环境下没有任何实例。总之，形式概念分析提供 了对二元关系的结构化描述，是一种一般的分析二元关系的数学方法，其核心数 据结构概念格是一种重要的知识表示方法。概念格生成算法分成批量算 法和渐进式生成算法两大类，渐进式算法相对更有利于概念格的维护。形式概念 分析提供了处理关系型数据的有效方法，从而很自然的被应用到数据挖掘之中。 使用渐进式构造方法可以实现概念格的增量更新，使用这样的概念格来作为存储 频繁序列的数据结构，可以实现序列模式的快速增量式更新，比其他序列模式增 量挖掘算法更快速，更节省内存，因为只需对原始概念格做很小的局部改动。 由于w e b 的用户访问模式是一种序列模式，因此将序列模式挖掘方法应用于 w e b 日志文件具有重要意义。使用序列模式实现个性化推荐的效果较好。除非两 个用户的兴趣和访问模式完全一致，否则这两个用户看到的网站网页不会相同。 现有的序列模式挖掘算法包括非增量算法和可增量算法。非增量算法每更新一次 日志，都要从头开始计算，而每次更新只是增长一小部分，这样就造成了时间和 系统资源的巨大浪费。由于网站日志是不断更新的，特别是大网站，每天都产生 大量的曰志，所以，用非增量算法实现w e b 日志挖掘不合适。现有的增量挖掘算 法有m f s ，i s m ，i s e 和i u s ，其中i u s 算法最为先进。但是这些算法进行一次挖掘 要多次扫描所有w e b 日志数据，导致速度较慢，效率不高。而概念格的渐进式增 量算法只需进行一次挖掘只需扫描一次原始数据，效率较高。概念格本身具有支 持抽象的特点，有利于将挖掘结果可视化，相对于非图形表示的数据，结合了人 类可以快速识别模式的能力，给网站的优化提供一个直观的指导。 1 4 本文完成的主要工作 本文提出了一种网站个性化系统，该系统采用数据挖掘技术进行w e b 日志的 挖掘。在该数据挖掘技术中，采用的机器学习方法为序列模式挖掘，采用被称为 数学分析的有力工具的概念格做为存储频繁序列的数据结构，采用非增量式序列 模式挖掘方法进行频繁序列挖掘，采用快速渐进式增量概念格构造方法进行概念 格构造，这样便于序列模式的增量式更新，也便于进行在线的个性化推荐。 本文第二章是有关序列模式挖掘的内容，包括序列模式挖掘的基本知识( 基 本概念和基本算法介绍) 、经典算法介绍( g s p 、s p a d e 、f r e e s p a n 和p r e f i x s p a n ) 和w e b 日志序列模式挖掘。 本文第三章是有关概念格的内容，包括基本概念、构造算法( 按构造方法分 第一章绪论 类、按算法生成结果分类、基于闭包的算法介绍和现有算法性能分析) 和概念格 在数据挖掘中的应用。 本文第四章是有关w e b 日志挖掘的内容，包括w e b 使用挖掘概述( 挖掘过程 和使用挖掘系统) 和日志挖掘与个性化( 曰志挖掘知识、w e b 个性化介绍和基于 w e b 日志的个性化) 。 本文第五章是有关w e b 日志序列模式挖掘算法设计的内容，包括算法总体设 计、频繁序列挖掘和频繁概念格的构建。 本文第六章是有关网站个性化系统设计的内容，包括系统总体设计和推荐引 擎设计。 种网站个性化系统的设计 第二章序列模式挖掘 2 1 序列模式基本知识 序列模式挖掘首先由a g r a w a l 和s r i k a n t 提出。他们基于顾客购买序列的研究， 即：给定一组序列( 每个序列由一列元素组成，每个元素由一组项组成) ，用户指定 的最小支持度阈值m i n s u p p o r t ，序列数据挖掘就是找出所有的频繁子序列，也就 是说，子序列在序列集中的发生频率不小于r a i n s u p p o r t 。 2 1 1 序列模式基本概念 项集：设i = ix , b ，i 。) 是项的集合，项集就是项的非空子集。一个项可以出 现的多个项集中，但一个项只能在一个项集中出现一次，也就是一个项集中不能 包括多个相同的项，一个项集中项的顺序可以是任意的，不失一般性，我们假定 项集中的项按字典顺序排列。 序列：一个序列是项集的有序列表序列记为： s i 8 2 s p ，其中s j 是项集。s j 也称为序列中的元素，记为( x - x 2 x 。) ，其中x k 是项。为简单起见，如果一个元 素只有一个项，那么括号通常省略，即元素( x ) 记为x 。 序列的长度：序列中项的实例数称为序列的长度。长度为1 的序列称为1 一序 列。 子序列、超序列：给定两个序列d = 和，1 3 = ，如果存在整 数1 j l j 2 m i n _ s u p p o r t ，那么序列q 称为序列模式。长度为k 的模式称为 k 一模式。 挖掘序列模式的问题分解为以下几个步骤： 排序：这一步骤隐含地将原始的数据库转换为事务数据库。 挖掘频繁项集：在这一步骤找出所有的频繁项集l ，同时找出所有的频繁 第二章序列模式挖掘 1 序列集合f l l l 。 变换序列：如果一个事务不包含任何频繁项集则在变换过程中将它从序列 中删除。 挖掘频繁序列：使用频繁项集集合挖掘出频繁序列。 找出最大序列：在频繁序列集中找出最大序列即序列模式。在有些算法中 这一步合并到挖掘频繁序列中以减少对非最大序列进行计数所消耗的时间 2 1 2 序列模式的基本算法 挖掘序列模式的算法的总体结构是对数据库数据进行多次扫描。在每一次扫描 过程都从一个频繁序列集合种子开始，我们使用这个种子集合来生成新的候选序 列，在扫描的过程中还要同时计算这些候选序列的支持度。在本次扫描结束前， 我们确定哪些候选序列是频繁的，这些频繁的候选序列称为下次扫描的种子。在 第一趟扫描时，在挖掘频繁项集阶段得到的所有频繁1 一序列作为种子集合。在数 据挖掘领域，序列模式的研究开始于1 9 9 5 年，到目前为止，已经有很多序列模式 挖掘的算法了。序列模式挖掘算法的困难在于尝试哪些序列( 即查找候选序列的问 题) ，以及如何有效地找出哪些候选序列是频繁的( 即候选序列的支持度计算问题) 。 序列模式的发现算法基本上可以分为两大类。 第一类是基于a p r i o r i 特性的、逐层( 1 e v e l w i s e ) 的发现方法，包括a p r i o r i a l l 算法和g s p 算法等。p s p 算法是g s p 算法的改进。g s p 算法将候选序列组织在哈 希树( h a s h t r e e ) 中，而p s p 算法将候选序列组织在前缀树( p r e f i x t r e e )，因而提高 了效率。经典算法基于的数据组织为水平( h o r i z o n t a l ) 方式，而s p a d e 算法基于垂 直( v e r t i c a l ) 数据方式，并且使用了一种格搜索技术和简单时序连接操作来发现所有 的序列模式。这类方法最先由r a g r a w a l 等人提出。关于频繁序列有以下的重要 特性( a p r i o r i 特性) ：在交易数据库中，如果某一长度为k 的序列不是频繁的，那么 它的任何长度为k + l 的超序列也不可能是频繁的。此类算法根据这个特性在基于 已生成的频繁序列搜寻更长的频繁序列的过程中对待检查的序列集进行有效的修 剪。除此之外，此类方法中的大多数采取了一种逐层的、候选序列生成和测试方 法( c a n d i d a t e g e n e r a t i o n a n d - t e s ta p p r o a c h ) 。在算法执行中，需要多趟扫描原序列数 据库。算法的第一趟扫描将发现频繁1 序列。而第k 趟以频繁k 一1 序列的集合作为 种子集来生成候选k 一序列，然后扫描原数据库得到每个候选序列的支持度，满 足最小支持度的候选序列即为频繁序列，并将它作为下一趟扫描的种子集。算法 如此迭代地执行，直至没有频繁序列被发现或没有候选序列生成，算法终止。 另一类方法由h a n 等人提出，称为基于序列模式增长( s e q u e n t i a lp a t t e r n s g r o w t h ) 方法，包括f r e e s p a n ，p r e f i x s p a n 算法等。这类方法采取了一种分而治之 种网站个性化系统的设计 ( d i v i d e a n d c o n q u e r ) 的思想，挖掘过程中无需生成候选序列。其主要特征有： 算法不生成大量的候选序列，而是以某种压缩的形式保留了原数据库的基本 的数据分组。随后的分析可以聚焦于计算相关数据集而非候选序列的频率。 算法的每一次迭代不是扫描完整的原数据库来匹配相应的全部候选序列，而 是通过数据库投影来对将要检查的数据集和序列模式进行划分。这样分而治之的 方法将减小搜索空间，提高算法性能。 2 2 1g s p 算法 2 2 序列模式经典算法介绍 候选项集产生、狈0 试方法是基于a p r i o r i 序列模式挖掘算法的扩展。与频繁模式 类似，序列模式也具有反单调性，即：序列模式的非空子序列也是序列模式。有两 种有效的序列模式挖掘算法具有这种性质：基于水平数据格式的序列模式挖掘算 法g s p ：基于垂直数据格式的序列模式挖掘算法s p a d e 从序列模式挖掘的观点来看，序列数据库可以表示成两种数据格式：水平数据 格式和垂直数据格式。前者使用数据集的自然表示方法把序列表示 为：s e q u e n c ei d as e q u e n c eo f o b j e c t s 是项的序列。后者用垂直格式把序列表示为： ，它可以通过转换水平格式的序列数据库得到。 g s p ( g e n e r a l i z e ds e q u e n t i a lp a t t e r n s ) 是一种基于水平格式的序列数据挖掘算 法，由s r i k a n t 和a g r a w a l 提出g s p 算法第一次扫描数据库找出所有的频繁项组成 单项频繁序列。随后的每次扫描从序列模式的种子集开始，种子集也就是在前次 扫描中发现的序列模式的集合。这个种子集用于产生被称为候选项集的新的序列 模式，每一个候选序列都比种子序列模式多项，当然，序列模式中的每一个元 素可以包含一个或多个项。序列模式中的项的个数称为序列的长度，因此，每一 次扫描数据库所产生的候选序列的长度相同。同时，每一次数据库扫描也计算候 选序列的支持度。所有候选序列中支持度不小于最小支持度闽值的序列就组成了 新的序列模式的集合，这个集合又成了下一次数据库扫描的种子集。当有下列两 个条件产生时，该算法终止：( 1 ) 在数据库扫描中没有新的序列产生；( 2 ) 没有候选序列 产生。 2 1 2 2s p a d e 算法 基于a p r i o r i 的序列模式挖掘算法也可以把序列数据库映射到一个垂直数据 第二章序列模式挖掘 格式上，这种数据格式以项为中心，把与该项相关的序列标识符和序列事件( 元素) 的时间戳作为列表中的一项，这种数据结构称为i d l i s t ，即其结构为 。这 种算法称为s p a d e ( s e q u e n d 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 tc l a s s e s ) 算法。 s p a d e 算法重复两个基本的步骤，即：候选序列的产生和支持度计数。候选序列的 产生主要是通过序列模式的连接操作来实现。在此，我们区分两种不同的序列模 式，设n = bs ，其中b 是( k 一1 ) 序列模式，s 是一个项，如果s 单独构成序列a 的 一个元素，则我们将n 记为a = b s ，若s 与其它项一起构成q 的个元素，则 我们仍记n 为a = bs 因为需要构建长序列的信息己转换到相关的项的垂直数据 格式中，所以s p a d e 算法可能会减少访问序列数据库的开销，然而，s p a d e 的算 法过程类似于g s p ，也是使用了宽度优先的搜索和a p r i o r i 的剪枝，为了构建较长 的子序列，它也会产生大量的候选序列集，因此g s p 算法遇到的很多问题在s p a d e 算法中同样也会出现。 2 2 3f r e e s p a n 算法 f r e e s p a n ( f r e q u e n tp a t t e r n p r o j e c t e ds e q u e n t i a lp a r e mm i n i n g ) 算法是基于数据 库中频繁模式的模式增长方法。对于个序列a = ，项集s l u u s l 称为a 的投影项集。f r e e s p a n 算法是基于如下性质：如果一个项集x 是不频繁的，那么任 何投影项集是x 超集的序列都不可能是序列模式。f r e e s p a n 算法基于投影项集的 概念，通过递归划分搜索空间、投影序列子数据库来挖掘序列模式。f r e e s p a n 算 法的主要思想如下： 设x = x l ，x 。 是序列数据库s 中的频繁项集( 假定，x l ，一，砾按字典顺序 排列) ，那么s 中的全部序列模式可以被分为n 个不相交的子集：( 1 ) 只包含项x l 的 序列模式的集合；( 2 ) 包含x l 及x 。，但不包含 x 3 ，x n 的序列模式的集合；依此类 推，序列模式的第i 个子集就是包含x i 及以前项的序列模式的集合，但不包含 x i + l ，x n 。 数据库投影可以按如下方法进行：假定序列数据库s 的频繁项集x 已知，为了 求得x i 的投影数据库，只需将序列数据库s 中频繁项集x 中x 以前的项包含在 x 的投影数据库中即可。这将有效地去除序列数据库s 中不相关的项，并且投影 数据库的大小很小。通过递归运行该算法，就可以挖掘投影数据库，进而得出序 列数据库的全部序列模式。 f r e e s p a n 算法的优点在于它通过将原序列数据库投影后，每次查询比g s p 小 得多的投影数据库。f r e e s p a n 算法的主要开销是它必须要产生一些投影数据库， 而且有时候所产生的投影数据库和原数据库相比所占空间差别不大，因此f r e e s p a n 算法仍然要耗费大量的计算机资源。 种网站个性化系统的设计 2 2 4 p r e f i x s p a n 算法 对于p r e f i x s p a n 算法，我们引入前缀和后缀的概念。一个序列b = 称作序列o = ( m n ) 的前缀，当且仅当满足下列三个条件时：( 1 ) e i e 。( i m 1 ) ；( 2 ) e 。e 。；( 3 ) ( e m f - e 。) 中所有的频繁项在字典顺序上都位于e 。冲所有频繁 项之后。序列y = 称作序列相对于序列口的后缀，记作y = o b ， 其中e mt = ( e 。一e m t ) 。 p r e f i x s p a n 算法的主要思想为：设x = f ， ， ) 是序列数据库s 的所有1 序列模式，那么序列数据库s 的所有序列模式可以分成r 1 个不相交的子 集，其中第i 个子集是所有前缀为 的序列模式的集合。设a 是一个p 一序列模式， ( bi ，1 52 ，b 。) 是所有前缀为q 的( p + 1 ) 一序列模式，那么除了序列模式a 本身，所 有前缀为a 的序列模式可以被分成m 个不相交的子集，第j ( 1 j m ) 个子集就是 前缀b ，的所有序列模式的集合。按照这些思想，序列模式的数据挖掘问题可以被 递归地分成一些小问题，这也是数据挖掘中的分而治之的思想。设a 是序列数据 库s 的序列模式，a 的投影数据库记为s l a , 是s 中前缀为n 的序列的后缀的集合( 注 意：此处投影数据库的概念与f r e e s p a n 算法中不同1 。 与g s p , f r e e s p a n 等算法相比，p r e f i x s p a n 算法有如下优点：( 1 ) p r e f i x s p a n 算法 不产生候选项集。与a 硼嘶类算法不同，p r e f i x s p a n 算法只是从较短的序列模式 增长到较长的序列模式，它既不产生也不测试投影数据库中不存在的任何候选序 列。与产生并测试大量候选序列的g s p 算法相比，p r e f i x s p a n 算法只需搜索较小 的数据空间。