（计算机软件与理论专业论文）web访问模式的序列化分析技术研究.pdf

w e b 访问模式的序列化分析技术研究 摘要 随着w w w 的普及，以w e b 访问日志的形式存储在w e b 服务器上的大 量数据对于理解用户的网路访问行为模式无疑是一个重要的资源。w e b 同 志挖掘就是将数据挖掘的有关技术应用于w e b 日志，从中发现用户一定的 访问模式。w e b 日志的挖掘结果已经被用于改善网站设计，商务和市场决 策支持，用户个性化配置以及w e b 腿釜器系统性能改善上。 本论文首先给出了w e b 日志挖掘问题的形式化描述，然后分析了几个 相关的序列模式挖掘算法。在此基础上，作者提出了一个新的高效序列模式 挖掘算法：增量前缀分解算法。实验数据表明增量前缀分解算法在效率上、 可扩展性和对存储介质的需求上均比前人的几种算法有一定的改善。最后在 总结全篇论文的基础上，提出了未来值得研究的几个方向。 w e b 访问模式的序列化分析技术研究 第4 页共5 6 页 a b s t r a c t a st h ep o p u l a r i t yo fw w w e x p l o d e s ，am a s s i v ea m o u n to f d a t ai sg a t h e r e db y w e bs e r v e r si nt h ef o r mo fw e b a c c e s sl o g s t h i si sar i c hs o u r c eo fi n f o r m a t i o n f o ru n d e r s t a n d i n gw e b u s e rs u r f i n gb e h a v i o r w e bu s a g e m i n i n g a l s ok n o w n a s w e b l o gm i n i n g ，i sa na p p l i c a t i o no fd a t a m i n i n ga l g o r i t h m st ow e b a c c e s sl o g s t of i n dt r e n d sa n dr e g u l a r i t i e si nw e bu s e r s t r a v e r s a lp a t t e m s t h er e s u l t so f w e b u s a g em i n i n gh a v eb e e nu s e di ni m p r o v i n gw e b s i t ed e s i g n ，b u s i n e s sa n d m a r k e t i n g d e c i s i o ns u p p o r t ，u s e rp r o f i l i n g ，a n dw c bs e r v e rs y s t e m p e r f o r m a n c e i nt h i st h e s i sw ef i r s td e s c r i b ef o r m a l l yt h ep r o b l e mo fm i n i n gw e bt r a v e r s a l p a t t e r n ，t h e nw ea n a l y z es e v e r a lr e l a t e ds e q u e n t i a lp a t t e mm i n i n ga l g o r i t h m s i n a d d i t i o n ，an e ws c a l a b l es e q u e n t i a lp a t t e r nm i n i n ga l g o r i t h mw i t he f f i c i e n c yi s d e v e l o p e d t od i s c o v e r c o m m o n l yt r a v e r s e dp a t h s i n l a r g e d a t as e t s o u r e x p e r i m e n t a la n dp e r f o r m a n c es t u d i e sh a v ed e m o n s t r a t e dt h ee f f e c t i v e n e s sa n d e f f i c i e n c yo f t h ea l g o r i t h mi nc o m p a r i s o nt o p r e v i o u s l yd e v e l o p e ds e q u e n t i a l p a t t e r nm i n i n ga l g o r i t h m s i nc o n c l u s i o n ，s o m ef u r t h e rr e s e a r c ha v e n u e si nw e b u s a g em i n i n g a r ei d e n t i f i e da sw e l l 4 w e b 访问模式的序列化分析技术研究 第5 页共5 6 页 第一章前言 1 1 背景 w e b 是一个非常成功的信息系统。这个系统为信息在全球范围发布和 传播提供了机会，它允许任何人在任何地点任何时间传播和获取信息。w e b 的非结构化信息传播和获取方式引发了信息爆炸。大量的非结构化的信息分 散在整个i n t e r n e t 中。大量信息在给人们带来方便的同时也带来了许多 问题：信息过量，难以消化；信息真假难以辨识；信息安全难以保证；信息 形式不一致，难以统一处理。在信息的海洋中，即使是最先进的搜索引擎也 只能从1 3 可以索引的w e b 站点中获取信息。人们开始提出一个新的口号： “要学会抛弃信息”。人们开始考虑：“如何才能不被信息淹没，而是从中 及时发现有用的知识、提高信息利用率? ”事实上，作为一个非专业的信息 管理人员，要从茫茫的信息海洋中获取本专业最新、最权威知识和较为全面 的信息，并从中得到有用的知识几乎变得不可能。要知道，各高等院校或研 究所里的专家教授们由于研究课题计划的紧迫，他们急需本专业领域的最新 最权威的知识和信息，他们没有时间在成千上万的站点中的数不清的页面中 查找所需的信息。现在几乎每家公司都拥有自己的网站，希望能够对公司起 到一定的促进作用。随着电子商务b 2 b ，b 2 c 的应用，越来越多的企业团 体使甩w o r l d w i d e w e b 作为贸易，销售的方式。著名的有国外的亚马逊网 上书店，国内的8 8 4 8 等网站。它们希望在最大程度上把握消费者的消费模 式，发掘潜在的客户，以提升本公司的销售业绩。所以在信息的提供者与信 息的消费者之间应有一个中间环节，通过这个环节，信息消费者能够快捷方 便地得到想要的信息，或者从中提炼出新的有用信息，正是这种迫切需要为 信息提取，数据挖掘等信息处理技术提供了广阔的应用空间。 w w w 是众多情报类型中的一种，并且具有极大的特殊性。它的信息 是分布在全球范围内，并且随时可变。这些分布在各地的信息允许任何人在 任何地点任何时间传播和获取信息。为此，w w w 用户应该使用某种工具来 有效地组织和获取w w w 中的信息。传统的搜索引擎根本不评估站点的内 容，而只是机械地识别w e b 设计者提供的关键字，获得一组按相似程度排 序的链接。这些链接大部分是与用户所需的信息无关的。更为重要的是搜索 引擎不能向用户提供新知识。即使是最优秀的搜索引擎也需要用户亲自访问 w e b 访问模式的序列化分析技术研究 第6 页共5 6 页 到不同的站点并对信息加以验证。互联网所带来的信息急速膨胀使得每个用 户所需的有用信息往往之占其中极少的一部分。w e b 用户大部分时间浪费 在那些对导向链接的频繁穿梭之间。例如，一个零售业用户如何能直接从 v c d c 3 v 中获知最近三个月顾客都偏爱哪些商品? 而w e b 挖掘技术是克服这 些缺点的最理想的工具。 1 2 数据挖掘和w e b 挖掘 数据挖掘( d a t am i n i n g ) 是信息技术( i t ) 领域中最热门话题之一。 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数 据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知 识的过程。何为知识? 从广义上理解，数据、信息也是知识的表现形式，但 是人们更把概念、规则、模式、规律和约束等看作知识。人们把数据看作是 形成知识的源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的， 如关系数据库中的数据：也可以是半结构化的，如文本、图形和图像数据； 甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以 是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被用于信息 管理，查询优化，决策支持和过程控制等，还可以用于数据自身的维护。因 此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询， 提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同 领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、 并行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领 域，形成新的技术热点。当数据挖掘技术应用于网络环境下的w e b 中就成 为w e b 挖掘( w e b m i n i n g ) ，w e b 挖掘可以广义地定义为从w w w 中发 现和分析有用的信息。这个定义有两方面的意义：一方面它描述了自动地从 数以百万计的w e b 站点和在线数据库中搜索和获取信息和资料；另一方面， 它旨在发现和分析用户访问一个或多个站点和在线服务的模型。 w e b 挖掘的数据是自动从w e b 服务器站点的内容中以及每日的访问同 志中收集到的。w e b 挖掘可分为三类：w e b 内容挖掘、w e b 结构挖掘和 w e b 使用挖掘。三者主要是挖掘的对象不同。内容挖掘的对象是非结构化 数据( 如自由文本) 、半结构化数据( 如h t m l ) 和一些更为结构化的数据 ( 如h t m l 中的标签数据) 。结构挖掘的主要对象是w e b 文档的超链接， w e b 访问模式的序列化分析技术研究 第7 页共5 6 页 即w e b 的拓扑结构。使用挖掘的主要对象是w e bs e r v e r 的访问日志、p r o x y s e r 、，e r 的日志、浏览器日志、用户配置文件、用户会话和交易、c o o k i e s 、鼠 标点击流等。w e b 结挖掘构在权威页面挖掘方面的技术已经应用于一些搜 索引擎之中，如g o o g l e 。而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 w w 中检索相关信息。该技术可以自动地检索信息，并把信 息按照课题领域进行分类，使它们更容易访问。图书馆员可以通过为不同的 课题领域建立一组特征，并以这些特征为基础进行检索和分类，从而保证得 到的信息是可靠的和具有权威性的。由于w e b 挖掘技术能够自动地，不须 人工干预地从w w w 中发现和组织信息，从而使图书馆员只需花少量的时 间来维护数据库即可完成任务。用户由于不需要花大量的时间来浏览成百上 千的文档，就可在相当短的时间里得到想要的信息而感到非常满意。更重要 的是，他们可以在任何时间访问到世界任何地方的信息。事实上，这就是图 书馆员把他们的咨询服务从桌面转移到i n t e i e t 的具体工作表现。 再比如说，对于一个电子商务公司，它可能希望获知在该公司网站上进 行大量购物的客户群体，或者是在对所有既定的公司网站访问用户的点击流 分析盼基础上预测哪些客户群体会对什么样的广告感兴趣，一般会在哪个位 置作广告的点击。这些数据对公司的市场和经营策略的制定夺可能会有很大 w e b 访问模式的序列化分析技术研究 第8 页共5 6 页 的帮助。 目前，大部分的服务器分析工具包都缺乏对用户访问行为进行商业分析 的能力，而只是针对服务器的活动状态进行分析。如一些网路交通监测工具： a c c r u e d a n d r o m e d i a ，h i t l i s t ，n e t i n t e l l e c t ，n e t t r a c k e r 和w e b t r e n d s 等等。 它们提供了关于域名、来访i p 地址、浏览器类别、c o o k i e s 和其他一些s e r v e r 活动状态的分析报表。这些报表没有对用户的行为进行分析，因此需要一些 能够反映用户行为状况的分析工具。而w e b 使用挖掘却能发挥数据挖掘的 优势，为用户提供新的有用信息，因此w e b 使用挖掘成为了技术研究和开 发的热点。 w e b 使用挖掘涉及的数据是多样的。这一点在前面已有论述。本篇论 文主要将重点放在对w e b 日志信息的挖掘上。然而，w e b 日志文件是面向 事务的，不能直接用于挖掘，需要经过过滤、归类与转换等预处理工作。在 第二章将详细分析一下w e b 臼志的各种数据源以及需要对它们进行的预处 理工作。 w e b 使用挖掘中的序列化分析技术，即通过监测并分析用户的访问路 径理解用户对w e b 站点的访问模式，是其一个主要的方面。将用户的在线 行为按相似程度分类，可以为公司提供决策支持，还可以根据这些信息用动 态的网页和个人定制的个性化网页技术向用户更直接有效地提供其所需的 信息。然而，不幸的是很难在用户日志上作面向用户的数据挖掘，因为原始 用户访问日志是不完整的并且模糊的。用户日志之所以不完整是由于点击缓 存、代理服务器和h t t p 协议的无状态性造成的。而模糊性是由于用户日志 是面向事务的，并且它记录的仅仅是对w e b 服务器资源的访问数据，但实 际需要的是提取那些对w e b 用户特征分析有用的信息。因此在对w e b 访问 序列模式作挖掘之前，需要对原始日志作预处理。论文在第二章对这一问题 也有较详细的论述。 序列化分析技术也是数据挖掘中的一个主要方向之一，最初是被零售商 应用于分析大众的菜篮子行为，事实上它也适用于分析w e b 用户的在线行 为，论文将在第三章中详细介绍与之相关的序列模式挖掘算法。 w e b 访问模式的序列化分析技术研究第9 页共5 6 页 1 3 论文构架 本篇论文分为5 个章节。第二章将对各种w e b 日志数据源进行分析， 并简单的介绍其相关的预处理技术。第三章作者在分析现有的序列模式挖掘 算法的基础上提出一种快速有效的新算法。第四章给出了实验结果分析并对 前人几个算法与新算法进行了对比讨论。第五章总结了本篇论文的工作，对 未来w e b 使用挖掘的研究方向提出了自己的意见。 w e b 访瓣模式韵垮列纯势辑技术研究 第1 0 甄共5 6 页 第二章数据源分析与预处理技术 本章将分析现有的数掭源及其预处理技术。2 ，l 麓介绍可用于序列挖掘 的数据源种类，2 2 节介绍w e bi 曩志挖掘的数据源常用的些术语，2 3 节 介缨对数羰赝采用鹃颈处攥过稷。 2 1 胃孺数据源 如图2 1 历示，邋誊搠蠢w e b 目惑挖掘熬数据集蠢三类：服务器( s e r v e r ) 疆恚，代臻( p r o x y ) 稳恚茅籍客户端( c l i e n t ) 西志。每种| j 恚数据的格式， 涉及范围鞠实现方法上都鸯掰不溺。 臻2 1 ：w e b 日惑挖撼的数据集 客户端 了志对w w w 用户的访问行为有潜最详细和准确的记泶。它可 以用j a v aa p p | e t s ，j a v a s c r i p t s ，c o o k i e s 等方法实现。如果一个客户与 i n t e r n e t 的连接是逸过互联网服务提供嶷( i s p ) 藏在防火壤聪逶过代理连上 i n t e m e t ，那么毽熬活动祷援就拔记录在代理服务器上。 弋璎服务器或蒴火 壤的主要佟雳是防止恶意豹连接遴天帮资源缓存邵逶过重箱最近谤闯的文 件以减少网络流量。它们的日志文件可能包含多个客户对多个s e r v e r 的访 阉。在| 葺志文件中，簿个客户的日恚记录是按代理收到服务请求的顺序阆隔 排列的。记录l 三l 志的过程较之客户端的日志记录慝自动化些，不需要太多的 予预。臼志的揍式也取决予疆恚较转。枣子在客户竭缓存的存在使褥客户熬 巢些请求不被发送到弋理服务器处，代理疆恚的准礁性受到定豹影响。服 务器强态是大多数w e b 蹬志挖掘算法掰采稻的数据源。大多数的w e b 服务 器都会提供一个选颈设定弱悫楚蔽c o m m o nl o g f o r m a t ( c l f ) ，e x t e n d e d c o m m o n l o gf o r m a t ( e c l f ) 或用户自定义的格式存储【l o u 9 5 】。表2 1 0 w e b 访蝴模式的序列化分析技术研究 第1 1 甄共5 6 页 描述了c l f 格式和e c l f 格式。 术语插述 r e m o t eh o s t远端客户机名或i p 地址 r f c 9 3 l客户的远端登荣名 a u t h u s e r服务器认证的客户端名 d a t e客户请求豹霹阗与蟊期 0 f f s e t本地时间与格林威治时间的偏移 m e t h o d请求方法( g e t ，p o s t ，h e a d ) 。 u r i从客户端发出的对页面请求的完整地址 p r o t o c o l客户端搜爆懿h t t p 汝议 s t a t u s发送给客户的h t t p 服务器状态 b v t e s传竣斡字节数 r e f e r r e r产生请求的u r i a g e n t , 客户端的操l 乍系绫和浏览器软l 孛 表2l ：c l f 、e c l f 格式w e b 日意的域描述 每一个c l f 臼志入口具有如下格式： h o s t l dr f c 3 9 1a u t h u s e r d a t eo f f s e t m e t h o du r l p r o t o c o l s t a t g sb y t e s e c l f 日志：i 丕包括r e f e r r e r 和a g e n t 这龌令域。以下是e c l f 疆式一条记录 的例子。注意r f c 3 9 1 和a u t h e r 这两个域为空( 用表示) 。 1 4 2 。1 0 7 3 0 1 8 0 一f 2 5 m a r l 2 0 0 2 ：2 1 ：0 1 ：4 5 8 0 0 “g e tm y 。h t m l h t t p 1 1 ”2 0 04 219 i n d e x h t m lm o z i l l a ( i e 5 0w i n 9 8 ) 这条例子反映的是一个在远端i p 地址为1 4 2 1 0 7 3 0 8 0 的主机上的用户在 2 0 0 2 年3 月2 0 日晚上2 i ：0 1 ：4 5 这一时亥镬鼹i e 5 0 戆测菱爨对菜w e b 鼹务 器上的m y h t m l 文件发出了h t t p 的g e t 请求，这一请求是从w e b 服务器 上懿索弓l 页i n d e x h t m l 发爨翡。 然丽使熙暇务器日恚褥在羞菜些缺点。 由于客户端和代理服务器的点毒缓存，不是所有客户的点赢都被记 录在服务器的日恚文件中。 当鬟户l d 不可掰并显客户弱狳藏在代理服务器螽灏对，许多不同 客户端的点击都将记录成同一个主机名( 代理服务器的名字) 。结 果对页视的访问就变得非常频繁。 鉴! 鲨鲤堡苎墼坐型丝坌堑堇查堡壅 笙! ! 墨苎墅壅 - g e e 减少点击缓存的方法是使得用户不同的访问发出请求的u r l 能够 难一。这可以透过溯态弼页生成技术翻在每个超链接的w e b 页翁名字螽加 一个唯一标识的用户会话i d 实现。若要比较全面的了解目前e t 悫标准的缺 点及其可能的解决办法，感兴趣的读者可参考1 p 9 7 。 2 2w e b 嚣恚挖掘蠡每鬻怒来港 必了镬论文在概念鲶使用上傈持一致性魏渍喙蛙，馋黄部分采用了由 w 3 cw c a ( w o r l dw i d ew e bc o m m i t t e ew e b u s a g e c h a r a c t e r i a t i o na c t i v i t y ) 矮蠢越关予w e b 瘦爝方瑟翡本添。它孵残予袭2 2 中 术语撼述 s e r v e r ( 服务器)一个提供资源的应用程序 p r o x y 弋理黢务令霞予窖户壤窝爨务器之瓣羁酵充当两者建筑豹中淄程 器)序 c l i e n t ( 客户端)一个专门绫服务器获敬资源的应臻耩痔 u s e r ( 用户)使用客户端软l 牛与服务器交甄的人 u s e fs e s s i o n ( 用 用户对一个或多个服务器的资源请求点击的集合 户会话) ) s e r v e rs e s s i o n ( 服 单个服务器记录的用户点击请求的集合( 也叫访问) 务器会话) e p i s o d e ( 事件)在一次用户会话中相关联的用户点海的子集 w e b p a g e ( 网页)单个u r i 所确定的资源的集合 ip a g ev i e 更撬)反馈绘客户螓程穿戆瓣夏。 i 【c l i c ks t r e a m ( 点 用户请求的一系列页视。 i i 遣流) 最2 2 ：w e b 程志挖掘翡帮孺术语 这里对几个概念作一下说明。页襁瞧一缎鼹来魄应客户蠛u r i 谤裳躲 涤源构成，例如个或多个h t m l 文件，图片等。一个页视通常是用户在一 个超锻接上豹一次甄标点蠢产生豹。越来越多靛霹夏采雳了动态产生豹技术 如c g i ，j s p 等，在这种情况下，必须将不同的参数所产生的请求划分到不 同的癸筏串去。点番流是一个潋辩阔为序的页橇豹巅寝，丽掰户在整个w e b w e b 访问模式的序列化分析技术研究第1 3 页共5 6 页 上的点击流就是一次用户会话。服务器会话则定义为个用户对一个特定的 服务器的点击子集，也称为一次访问。事件则是在一个用户会话中在语义上 相关的点击的集合。 2 3 数据预处理 知识发现的一个核心步骤就是数据的预处理。这步的主要目标是为数 据挖掘提供合适的可挖掘的对象，尽量避免数据的模糊性和不完整性。这一 步是与数据源紧密相关的。不同的数据源所采用的技术往往有很大的不同。 因此，本节将讨论用于预处理c l f e c l f 格式的w e b 服务器日志的相关技 术。表2 3 给出了个e c l f 格式的w e b 日志。 通常，在w e b 日志预处理的工作中有三个主要的任务：用户确认，会 话确认和事件确认。 2 3 1 用户确认 在最理想的情况下，可以根据日志中r f c 9 3 l 和a u t h u s e r 这两个域的值来 确定一个用户。但是，在大多数情况下，r f c 9 3 1 和a u t h u s e r 这两个域是空的。 在这种情况下，主机名和浏览器是唯一可以用来确定个用户的信息。不过 它需要假设每个用户都有唯一的i p 地址，并且只使用一种浏览器。然而实 际情况却未必如此。【s c d + 0 0 指出，存在如下几种情况使得假定的条件 不满足。 如图2 1 所示，可能存在同时有几个用户通过一个代理服务器访问一个 w e b 服务器的情况。 某些1 s p 或隐私工具会为每个用户的请求随机分配一个i p 地址。 某些用户会经常更换机器。 一个用户可能在同一台机器上使用几个不同的浏览器访问w e b 服务器。 在表2 3 所示的例子中，若使用主机名和浏览器组合的方法，那么i p 地址1 4 2 5 9 2 4 3 1 4 6 上有两个用户( 一个是使用w i n n t 的，一个是使用 w i n 9 5 的) 。i p 地址1 4 2 5 9 2 4 3 _ 3 上则有一个用户( 第1 4 1 5 行) 。 型! ! 堕鲤堡盛竺生型! 兰熊堑楚查型塞 笺! ! 墨整堑至 h o a tn a m er f c 9 3 1 u t hd a t e 磷e t h o d u 较l , p r o t o c a is t a t 垴b y t e sr e f e f的e a t j d s e r m o z i l l a 30 1 4 25 92 4 3 1 4 60 8 f e b ，2 0 0 l ：1 9 ：5 1 ：0 4“g e ti h t m i 2 0 01 1 5 2_ i t t p ：w w w c ss f u c a i n d e xh t m l f 1 5 5 0 ： - e o o l h 丁r 州1 1 时i n n t l v l o z i t f a , 3 + 0 t 4 25 92 4 3 1 4 6 ：0 8 , f e b 2 0 0 1 ：1 9 ：5 1 ：0 4* g e t a g i f h h 耕 2 0 0 猢0瞰t p ：f 呐v wc ss f u c a i n d e xh t m i e 50 ： 1 s o o l 4 v i n n t ) m o z i l l a 30 1 4 2 5 9 2 4 31 4 6p s r f e b r 2 0 0 l ：1 9 ：5 1 ：0 4g e t 8h t m i 2 0 01 3 0 0h n o ：“w w w s f u c a l lh t m t f i e 5 0 ， - - s o o 卜r t t p 门1 ”w i n n t ) 1 4 2 ，s 92 4 31 4 8e 0 8 蘑e b t 2 0 0 l ：1 9 ：5 1 ：0 6g 丁 h t m l瑚 1 1 5 2h t t p ：l w w wc ss f u c a i n d e xh h ”1鹾o z f f l e 30 4 ( w i n 9 5 i ) 1 8 0 0 h t t p 1 1 。 m o z i l l a 30 4 1 4 2 s 92 4 31 4 60 8 ，f e b ，2 0 0 1 ：1 9 ：5 1 ：0 74 g e t ag i f h l _ r p ，11 3 0 4h n d ：“w w m c ss f uc a i n d e xh t m l ( w i n 9 5 ，玲 - 8 0 0 i 1 4 2 5 92 4 31 4 5 0 8 f e b l 2 0 0 l ：1 9 ：5 1 ：0 7。g e t dh t m 瑚 8 1 4h t t p ：w w wc ss f uc a t ih f m j m o z i l l a 3 0 4 ( w i n 9 5 i ) - 8 0 0 l h h p t 。 ：, o z i f l 猷30 4 1 4 25 92 4 3 1 4 6 【0 8 f e b 2 0 0 11 9 ：5 1 ：0 4“g e t ch t m i 2 0 01 2 1 0h t t p ：n v w wc a s f uc a d h t m l ( w i n 9 5 1 ) - 8 0 0 】 h t t p 1 1 。 o z i t f a 30 1 4 25 9 2 4 3t 4 5 1 0 8 ，f e t y z 0 0 1 ：1 9 ：5 2 ：2 4h g e t e h t m f删 i e 5 o 0 饿 h t t 科 ”, , v i n n t ) m o z i l l a l 3 ，0 1 4 25 92 4 3 1 4 6 l 0 8 f e b 2 0 0 l ：1 9 ：5 2 ：2 5”g e ti h t m i 2 0 0 5 2h t t p ：l w w wc s s f u c a i n d e xh t m i er e 5 0 1 8 0 0 h t t p 1 1 w i n n t m o z i l l a 30 1 4 25 9 2 4 3 t 4 6 1 0 8 f e b 2 0 0 1 ：1 9 ：5 2 ：3 4“g e t a g i f h t t p ，11 3 0 4 l f f p ：w w wc ss f uc a i n d e xh t 几1 【i e 50 ； - 8 0 0 l w i n n t ) 4 m t o z i l i a 30 4 1 4 25 9 2 4 31 4 60 8 f e b 2 0 0 t ：1 9 ：5 2 ：3 4g e t hh t m z o o2 7 6 2嘣p ：w v , wc s s f uc a ih t m l ( w i n 9 5 ， ) - 8 0 0 】 h t t p 门1 m o z i ( a 30 4 1 4 25 92 4 3 + 1 4 6。0 8 i f a b 2 0 0 1 ：1 9 ：5 2 ：4 5”g e t 8h i m i2 0 01 3 0 0h t t p ：1 w w wc $ s f uc a ah l m l ( w i n 9 5 。i ) - 8 0 0 l 嘲1 p ，1 8 m o z i t i a 30 4 1 4 25 9 2 4 31 4 6 0 8 1 f e b 2 0 0 1 ：1 9 ：5 3 ：0 1。g e t2 c g i ? 始1 5 2 ( w 哟5 1 ) - 8 0 0 l h t t p 1 1 。 m o z i l l a 30 1 4 25 92 4 3 3 0 8 f e b 2 0 0 1 ：1 9 ：5 3 ：0 e。g e t gh t m i 2 0 01 6 8 0h t t p ： w w vc 窖s f uc a bh i m j f i e 50 ： r ! s o o l l 订p 1 1 1 w i n 啊) 瞄o z i f f a 30 1 4 25 9 2 4 33 离煳州9 5 3 伯 4 g e tf h t m lz 0 02 鞋3 7h t t p ：l w 蝴c ss f uc a bh t m i ：i e 5o h h p 1 1 。 w m 盯l 表2 3 ：e c l f 格式的w e b 目志文件样本 4 w e b 访问模式的序列化分析技术研究 第1 5 页共5 6 页 2 3 2 会话确认 一旦用户能够被确认下来，每个用户的点击流就需要分解为不同的服务 器会话或者说访问。它是通过每次访问的最后一个页视来确定的。在没有明 显的注销动作结束用户会话时，可以使用页视的访问时间来确定用户是否在 继续对服务器的访问。c a t l e d g e 和p i t k o w 在【c p 9 5 】研究了用户在w w w 上对页视访问时间的分布，指出若用户在3 0 分钟内对服务器没有进一步的 访问，则可视作注销。注意由于用户可能不仅仅对一个站点感兴趣，在不同 的时刻可能会反复访问某个站点，这就给会话确认增加了难度。 2 3 3 事件确认 在用户的会话被确认下来之后，就可以将其再分解为一系列语义上有意 义的子集称之为事件。最大向前引用方法【w y b 9 8 】就是用来确定事件的 技术之一。在最大向前引用方法中，事件就是一个最大向前引用，它的结束 是发生在页视向后引用时。例如，对于一个用户会话a b c d c ，会话的最 大向前引用是a b c ，c d 。在一个电子商务网站中，一个事件可以根据网页 类型，站点结构和一个特定的用户动作诸如点击广告图标或加一个商品入菜 篮子来确定一个事件。这种类型的网站通常需要找到能反映出一个特定行为 的网页序列。c o o l e ye ta 1 【c m s 9 7 】用引用长度模数和事件窗口模数来作 为事件定义的手段。前者根据网页的内容或导航类型，为每种页面设定一个 最大访问时间。当一个页面的访问时间超过了最大访问时间，那么一个新的 事件就开始了。后者则为每种事件定义一个最大时间窗口。它是基于这样的 假设一个有意义的事件应该有一个合理的平均时间跨度。 w e b 访阿模式的序列化分析技术研究 第1 6 页麸5 6 页 第三章用户w e b 访闷模式的序列纯分析 在对w 。b 墨悫文传佟了掰嚣颓处理之后，裁母戬垂廖列模式挖掘算法找密 e 一频度序列模式。本章先对足令藩人斡疹列模式挖掇算法 筝一个大致的介 缨，在此基础上作者垮绘出一个薮熬扩展性积效率均较好豹序剃模式挖掘算 法；增量翦缀分鹪算法。 3 弓| 富 对w e b 访问序列模式的挖掘就是在给定的w e b 访问同志数攒库中，找 到一个用户访问序列模式集，该集合中的每一个序列模式均满足频度条件， 即是频繁的。序列中的元索以访问时间为序。例如，考虑一个服务器级的 w e b 访问两志数据库，用指定的资源属性表示用户的w e b 页视，日志的每 一条记录表示了每一次w e b 用户在一段时间内以时间为序的访问序列。用 序歹| j 模式挖箍舞法可戳得瓢那魑经常被用户访问的资源集合，并且包括用户 对这些资源的访问次序。以下是一个示饲： “在对当当网站同一次访问中对帝国反击战这郝v c d 煦页辜璺的访 问有7 l 发生在对摄战前传v c d 的页视的访问之前” 事实上，在一个大型的w e b 露志数据库中要挖掘港辨有频度满足大予 频度闺值条件的g - - f r e q u e n t 访闷序列是缎塞挑战投躬。正魏【z 9 8 ，a 0 1 】 中提至q 的其搜索空阅的数量级为( 2 。) ，。其中a 是尽患数摆库中黪w e b 资 源属性集的大小，p 是日志数撂库中最大- - f r e q u e n t 访目序列豹长度。 些拥有大量用户群的网站如y a h o o e o m 和s i n a c o m 等攘鸯数以秀万计的爨 户和上万的资源数熙，访间序列的长度增长很快，搜褥挖撼算法的搜索空溜 呈指数增长。并且，在个大型的数据库中，出于- - f r e q u e n t 访阗序列联 占的比例通常不高，存在着如何减少的问题。鲤煎大多数鲍序列模式挖 掘算法是循环的，在每一步循环中，会产生更长的候选序列，为了计算候选 序列的支持度又必须重新扫描整个数据库。这些算法采用的数搬结构也是一 些基于长指针的动态数据结构，如h a s h 树，链表等。在【p z i 。9 8 】中已经 指出这魑递归的数据结构是高度有序的，其数据的局部性在这些算法中势没 有得到优化。 | 6 w e b 访商模式的序列化分析技术研究 在本章中，馋卷撼出的瓤的算法，针对上述算法的局限，该算法主要有 嚣点改进： 翡一个静态h t m l 文l 牛或个动态生成的文馋。最终，一个w 幽访阉序列模式被定义为一缀 以时间为膨魄耀户访阏的集合。 定义3 2 1 ：设 r = p l ，2 ， 是一个w e b 服务器上所有可用资源的i d 集合。t 是w e b 服 务器上个可用资源的i d 。 p = p l , p ：，p 。 为w e b 服务器所有霹能鲍页视集合，其中 p ；= 筑 ，2 ，- ，气 l i m ，l s j s , 1 - s 辑飞6 殳 三一拿。，2 ，f 。j 为w e b 访闯目志文件中所有记录( w e b 访问事务) 的集合 7 w e b 访问模式的序列化分析技术研究 第18 页共5 6 页 不失一般性，定义1 l 为一个三元组，= ( u s e r i d ，l i m e ，r e s o u r c e i d ) ，i i s q ， ，r e s o u r c e i d r 。 在理想情况下，能够从w e b 服务器的日志文件中获取每个用户的页视。然 而由于点击缓存和代理的存在不是每个用户的点击均记录于l 中，因此需 要对页视作近似。 定义3 2 2 设 e = e 。，p 2 ，e 。 为从w e b 日志提取的页视集合，其中每一个p e 被定义 为三元组：p = ( u s e r i d ，t i m e ，h i t s = ( f n ，2 ，。) ) ，其中 1 i m ，1 j “，f l& f 口u s e r i d = e i u s e r i d& l o t i m e ，( ，+ i ) t i m e & ，( + i ) t i m e 一，d i m e m i n a t & p ，l i m e = m a x l 。( ，口l i m e ) v = ( 1 1 s e r i d ，f f m p ，( 巳，e 2 ，e q ) ) 为用户对w e b 服务器的一次j 韭丑，其中 1 f g ，e ，u s e r i d = v u s e r i d & p ，l i m e se ，+ 1 t i m e & e 川, t i m e e ，t i m e m a x a t & v j i m e = m a x 。；。( e ，i t m e ) 。一个具有k 个页视的访问被称为长度为k 的访问 l v i = k 或垦二边回。 注意页视是w e b 日志访问序列中基本的挖掘元素而不是对资源的点 击。图3 1 给出了一个例子。 定义3 2 3 用户w e b 访问序列是一个以o c f q 为序的访问的集合。被定义为 一三元组s = ( u s e r i d ，t i m e ，( v l ，v 2 ，v ) ) ，其中 l i n ，v ，u s e r i d = s u s e r i d & v ，t i m e v 川l i m e & s t i m e = m a x 旧。( v ，t i m e ) 。 一个具有k 个页视尼= p 1 2 善i v ，| 的序列被称为k 二庄芝虬w e b 边阎庄互堑 握庄定义为w a s = 矗。，s ：，j 。， ，s w a s 是一个用户w e b 访问序列。与 【s a 9 6 】中定义的序列模式挖掘中的序列概念相比，用户w e b 访问序列是 由一组以时间为序的访问为元素的。在单个序列元素中的页视可以重复。例 如：( 1 ，1 ，2 ) 和( 1 ，2 ) 是两个不同的元素。 w e b 访阐模式的序列化分析技术研究 第1 9 页梵5 6 页 豳3 ，lw e b 访嘲序列数据痒 w e b 访问模式的序列化分析技术研究 第2 0 页共5 6 员 定义3 2 4 对于用户访问v = - i ，e ；，。；j 和用户访问v = 0 i 局，一一) o s t ) 当并晨仅当：存在一个熬数痔硝l 毛 l k 满怒 = 气，= 气，嘭2 e , j ，则称v 是z 的王座至l ，v 是! ：魍趁崖剔。表示为 矿当飘仅当，5v 虽v v 时，v 是! 煎塞王巍到，记为v c v 。 类铥翡，辩予访滴痔襄s = v ：，v ；，v ：藉谤溺穿翔 j = ( v i ，v 2 ，v 。) 如甩) ，当且仅当：存在一个整数序列l i f i 2 i 。月 满足q 飞，呸飞，”咳，则称s 屋煎壬壅到，s 是j 煎超庄殛，记为 s gs 。当照仅当s s 艇s s 时，s 是的塞王鏖到，记为s cs 。巍且 仅当：l i m ，v ：= v 。，并且v 二= “，e i ，p ：i v = 0 1 ，p 2 ，吼) c ，t l l g l ，# 卜g ， 成立时，穆s 是趁夔筑。 例如，考虑一个w e b 用户，他访问了如下页视l ，2 ，3 ，4 ，5 。其访闻序列 为s = 0 x 2 3 x 4 5 ) ) 。从中可以肴出对页视2 ，3 的请求发生同一次访问中， 并且缀为s 总共包食5 个页视，矮以s 是一个5 一黟列。窿列模式 l x 2 努是 s 的予序列，n n n j u 0 ) 匹( 1 ) ，访问( 2 ) ( 2 ，3 ) 。然而序列模式 却不 是s 豹子净嬲；孝裂模式 l 荚2 是s 靛翦缀，焉 i x 3 龆不是s 鹃蔫缀。 分析的瞬标是挖掘出赝有这些频繁的w e b 访目廖列模式。过予频繁憋定 量描述，定义支持度的械念。 定义3 2 。5 ：在w e b 谚阉窿裂数据簿粉s = 蕊，s ：， 中，一个访陵事