（计算机软件与理论专业论文）web日志挖掘新方法.pdf

复旦大学顾士学位论文w e b 日志挖掘新方法 摘要 w e b 日志是w e b 网站的访问记录的集合。它是一个不断增长的海量数据集，包 含大量有用信息。w e b 目志挖掘即采用数据挖掘的方法和手段埘w e b 目志进行分析 处理，发现其中的访问模式、用户兴趣和其他相关特征。w e b 日志挖掘的结果能够 帮助管理者改善网站结构，提高服务质量。 w e b 日志挖掘作为数据挖掘的一个新领域，有许多相关的研究和产品。除了对 用户活动、网页访问频率等进行简单的统计外，其主要有两种方法：一种是构造 w e b 日志n 维立方体，运用o l a p 技术对其进行多维分析，挖掘其特征：另一种是 采用事务挖掘中的关联规则挖掘、序列模式挖掘等方法，在w e b 日志中发现关联网 页和频繁路径。 本文的主要目的是对w e b 日志挖掘做进一步的研究，并提出新的挖掘方法。论 文首先探讨如何有效的将原始w e b 日志转化为用户事务：然后介绍事务集合的关联 规则挖掘和序列模式挖掘的原理和算法；接着将一种互关联后继树( i n t e r - r e l a t e d s u f f i xt r e e ，i r s l ) 模型应用于w e b 日志事务挖掘，构造w e b 日志事务集的互关联后 继树结构，从中挖掘频繁路径：最后论文还尝试将w e b 日志和w e b 网站内容、网 站结构结合起来进行挖掘的方法。 本文的创新点在于： 1 采用互关联后继树挖掘模型挖掘w e b 目志，得到比一般的序列模式挖掘算法 更好的效果。 2 提出了将w e b 日志挖掘和w e b 站点内容、w e b 站点结构结合起来的新方法。 关键词：w e b 日志挖掘，w e b 日志事务，序列模式，频繁路径，互关联后继树，i r s t 复旦火学硕j 。学位沦文 w e b 日志挖掘新方法 a b s t r a c t w e bl o gi st h ec o l l e c t i o no fw e b s i t e sa c c e s si n f o r m a t i o n i ti sal a r g ed a t as e tt h a t i n c r e a s i n ge x p e d i t i o u s l y t h ea c t i v i t i e so fa n a l y z i n gw e bl o g sw i t ht h et e c h n i q u e sa n d i n s t r u m e n t so fd a t am i n i n gt of i n dt h ea c c e s sp a t t e r n s ，u s e rh t e r e s t s ，a n do t h e rh i d d e n f e a t u r e s ，a r ed e f i n e da sw e bl o gm i n i n g t h er e s u l to f w e bl o g m i n i n gi sh e l p f u lf o rw e b a d m i n i s t r a t o rt oi m p r o v es i t es t r u c t u r ea n dp r o m o t es e r v i c eq u a l i t y w e b l o gm i n i n gi s an e wf i e l di nd a t am i n i n g t h e r ea r em a n yr e s e a r c hw o r k sa n d p r o d u c t sr e l a t e dt oi t e x c e p ts o m es t a t i s t i c a l w o r k ss u c ha sc o u n t i n gu s e rv i s i t i n gr a t e a n dp a g ec l i c kf r e q u e n c y ，t h e r ea r et w om a i nt e c h n i q u e su s e dt om i n i n gw e bl o go n ei s c o n s t r u c t i n gn - d i m e n s i o no l a p c u b eo f w e b l o g sa n dd i s c o v e r i n gt h en a t u r e st h r o u g h i t t h eo t h e ri s a p p l y i n ga s s o c i a t i o nr u l e sm i n i n ga n ds e q u e n t i a lp a t t e r nm i n i n go nw e bl o g t r a n s a c t i o n st of i n da s s o c i a t e dp a g e sa n d f r e q u e n tp a t h t h eo b j e c t i v eo ft h i st h e s i si st og od e e pi n t ot h ew e b l o gm i n i n ga n dp r o p o s es o m e n e wm i n i n ga p p r o a c h e s f i r s t l yw ed i s c u s sh o wt ot r a n s f o r mt h et a ww e b l o g si n t ou s e r u a n s a c t i o n se f f i c i e n t l y t h e nw ed e s c r i b es o m ec u r r e n ta s s o c i a t i o nr u l e sa n ds e q u e n t i a l p a t t e r n sm i n i n gt h e o r y a n d a l g o r i t h m i nc o m p a r i s o n ，w ep r e s e n t an e we f f e c t i v e p r o t o t y p eo ft r a n s a c t i o nm i n i n g ，i n t e r - r e l a t e ds u f f i xt r e e ( i r s t ) w ec o n s t r u c ti r s to f w e bl o gt r a n s a c f i o n s ，a n dm i n ef r e q u e n tp a t hf r o mt h i st r e e a tl a s t ，w es u g g e s tan e w m i n i n gf r a m e w o r ko fi n t e g r a t i n gw e bl o gm i n i n gt o g e t h e rw i t hw e b s i t ec o n t e n tm i n i n g a n dw e b s i t es t r u c t u r em i n i n g t h ec o n t r i b u t i o n so f t h i st h e s i sa r e ： 1 a p p l i e si n t e r - r e l a t e ds u f f i xt r e et ow e bl o gt r a n s a c t i o nm i n i n g ，a n dp r o v e st h a ti t i sb e t t e rt h a nc o l n l n o ht r a n s a c t i o n m i n i n ga l g o r i t h m si ne f f e c t 2 g i v e sas u g g e s t i o nt o i n t e g r a t ew e bl o gm i n i n gt o g e t h e rw i t hw e b s i t ec o n t e n t m i n i n ga n dw e b s i t es t r u c t u r em i n i n g ， k e yw o r d s ：w e bl o gm i n i n g ，w e bl o gt r a n s a c t i o 乌s e q u e n t i a lp a t t e r n ，f r e q u e n tp a t h ， i n t e r - r e l a t e ds u f f i xt r e e ，i r s t 4 夏旦大学硕士学位跄文w e b 口志挖掘新方法 1 - 1 概述 第一章引言 6 0 年代，由于传统的文件系统不能适应处理大量数据信息，因此出现了数据库 技术。至9 0 年代初，人类积累的数据以高于每月1 5 的速度急剧增加，海量数据 难以消化，反而成了获取信息的阻碍。为了解决如何快速、准确地获得有价值的信 息，如何理解已有的历史数据并用于预测未来的行为，如何从这些海量数据中发现 知识等问题，导致了知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 和数据挖掘 ( d a t am i n i n g ，d m ) 技术的产生f j j 。知识发现和数据挖掘是集统计学、人工智能、模 式识别、并行计算、机器学习、数据库等技术的一个交叉性的研究领域【“】。 上世纪中后期，i n t e m e t 的普及使计算机、网络、通信合而为一。互连网络以其 巨大的社会效益和极富挑战与机遇的内涵，成为信息科学最引人注目的研究领域。 i n t e m e t 上存贮了许多复杂的数据，它涉及新闻、广告、消费信息、金融管理、教育、 政府、电子商务和其它许多信息服务，还包含了丰富和动态的超链接信息。这些大 量的非结构化的信息无法使用现有的数据库管理系统来操纵和管理，所以如何高效 地发现和利用因特网上资源，是一个挑战性的课题。而且，i n t e m e t 用户群体也表现 出多样性的特点，全球互连网大约有数千万个w e b 网站，其访问用户具有不同的背 景、不同的兴趣和目的，他们在访问过程中留下大量的w e b 访问和使用信息。尤其 是大型电子商务网站每天都可能有上百万次的在线交易，生成大量的w e b 目志和登 记表单。如何对这些数据进行分析和挖掘，用以改善网站服务，也是一个需要研究 重要领域。 解决这些问题的一个途径就是采取w e b 挖掘( w e bm i n i n g ) 5 。w e b 挖掘是将 数据挖掘技术应用于w e b 领域的成果，其目的是从w e b 文档和w e b 活动中抽取感 兴趣的，潜在的，有用的模式和隐藏信息。根据挖掘对象的不同，w e b 挖掘可分为 三类：w e b 内容挖掘( w e bc o n t e n tm i n i n g ) 、w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 和w e b 使用模式挖掘( w e bu s a g em i n i n g ) ，其挖掘主要对象分别是w e b 页面文本 内容、w e b 超链接和w e b 日志p w 。 i n - a l i a g i | 撇b 撼蜘i ，”1 、。 fw 铀c 硼l 曲啦幻备唾 n 瞻h w d 嘴r a i n i n z嗡bu 举i _ l “j 鸺 i 撇渖襻撼糍j 锇b 髂输缆搦) e 蜘鞋用| 窀 黔 f i g 1 1w e b 挖掘的分类 复旦大学硕士学位论文w e b 口志挖掘新方法 1 2 数据挖掘和w e b 挖掘 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机 的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信 息和知识的过程。数据挖掘常用的技术包括人工神经网络、遗传算法、决策树、邻 近搜索方法、规则推理、模糊逻辑等。数据挖掘常用的分析方法有：基于关联度的 分析，基于序列模式的分析，分类分析，聚类分析等。 就建模、技术和算法而言，w e b 挖掘和数据挖掘差别并不是特别大，很多思想 和方法都通用。但是w e b 数据也有其自身的特点： ( 1 ) 对有效的数据仓库和数据挖掘而言，w e b 似乎太庞大了。w e b 的数据量目前 以兆兆字节( t e r a b y t e s ) 计算，而且仍然在迅速地增长。许多机构和社团都在把 各自大量的可访问信息置于网上。这使得几乎不可能去构造一个数据仓库来 复制、存储或集成w e b 上的所有数据。 ( 2 ) w e b 页面的复杂性高于任何传统的文本文档。w 曲页面缺乏同一的结构，它 包含了远比任何一组书籍或其它文本文档多得多的风格和内容。 ( 3 ) w e b 是一个动态性极强的信息源。w e b 不仅以极快的速度增长，而且其信息 还在不断地发生着更新。新闻、股票市场、公司广告和w e b 服务中心都在不 断地更新着各自的页面，w e b 日志更是每秒种都会记录下大量的访问信息。 ( 4 ) ) w e b 面对的是一个广泛的用户群体。目前因特网上连接有约5 千万台工作 站，其用户群仍在不断地扩展当中。各个用户可以有不同的背景、兴趣和使 用目的。 ( 5 ) w e b 上9 9 的信息相对9 9 的用户是无用的。用户只关心w e b 上的很小一 部分信息，其余信息对用户来说是不感兴趣的，反而会淹没其所希望得到的 搜索结果。 w e b 挖掘采用其特有的方法，可以部分的解决上述问题带来的困难。w e b 挖掘 作为一个新领域，还在不断的发展之中，不断的发现解决问题的新方法。如前面所 述，为了明确挖掘对象，进行有效的资源和知识发现，把w e b 挖掘划分为三个类别。 下面分别对每个类别的任务和相关工作做简要介绍： ( 1 ) w e b 内容挖掘 w 曲内容挖掘是从w e b 文档内容或其描述中抽取知识的过程，其方法包括其中 包括内容摘要、分类、聚类、关联等。w 曲文档文本内容的挖掘，基于概念索引的 资源发现，以及基于代理的技术都属于这一类。w 曲内容挖掘有两种策略：直接挖 掘文档的内容，或在其它工具搜索的基础上进行改进。采用第一种策略的有针对 w e b 的查询语言w e b o q l “ ，利用启发式规则来寻找个人主页信息的a h o y f ”】，等 6 复旦大学硕_ 上学位跄业w e b 口志挖掘新方法 等。采用第二种策略的方法主要是对搜索引擎的查询结果进行进一步的处理，得到 更为精确和有用的信息。属于该类的有w e b s q l ”】，及对搜索引擎的返回结果进行 聚类的技术等。 ( 2 ) w e b 结构挖掘 w e b 结构挖掘是分析w e b 页面之间的超链接关系，从页面的组织结构和链接关 系中推导知识。由于文档之间的互连，w 、 几 ，能够提供除文档内容之外的有用信息。 利用这些信息，可以对页面进行排序，发现重要的页面。这方面t 作的代表有 p a g e r a n k 【“l 。此外，在多层次w e b 数据仓库( m l d b ) 中也利用了页面的链接结构。 ( 3 ) w e b 使用模式的挖掘 w e b 使用记录挖掘的主要目标则是从w e b 的访问日志和其他信息中抽取感兴趣 的模式。w w w 中的每个服务器都保留了访问日志( w e bl o g ) ，记录了关于用户访问 和交互的信息。分析这些数据可以帮助理解用户的行为，从而改进站点的结构，或 为用户提供个性化的服务。这方面的研究主要有两个方向：一般的访问模式追踪和 个性化的使用记录追踪。一般的访问模式追踪通过分析使用记录来了解用户的访问 模式和倾向，以改进站点的组织结构。而个性化的使用记录追踪则倾向于分析单个 用户的偏好，其目的是根据不同用户的访问模式，为每个用户提供定制的站点。这 方面的主要研究项目和产品有w e b s i f 9 15 1 ，w l j m 1 9 和w e b t r e n d s ”1 等， 1 3 本文的任务 本文的主要研究w e b 挖掘中的w e b 日志挖掘。w e b 日志是w e b 服务器记录的 用户对站点资源的访问，其中每条记录一般包括用户i p 、访问时间、资源的u p & 等字段。大型网站每天可能会产生数百兆的w e b 访问日志。有效地对这些w e b 曰 志进行定量分析揭示其中的关联关系、时序关系、页面类属关系、客户类属关系 和频繁路径等，可以为优化w e b 站点的组织结构，增加个性化服务提供参考。f i g i 2 展示了w e b 日志挖掘的详细流程。 本文首先讨论w e b 日志预处理，研究如何才能将w e b 日志转换成适合数据挖掘 工作的用户事务：然后研究在w e b 事务中进行关联规则和序列模式( 频繁访问路径) 的挖掘，并尝试将一种新的数据模型互关联后继树( i n t e r - r e l a t e ds u f f i xt r e e ) 应用于w e b 曰志挖掘：最后本文综合w e b 挖掘以往的成果和经验，首次提出采用 聚类( c l u s t e r i n g ) 方法将w e b 日志挖掘和w e b 站点内容挖掘，w e b 站点结构挖掘 结合起来的思想。 攥 放 教 现 复日大学硕士学位论文 w e b 日志挖掘新方法 f i g 1 2w e be t 志挖掘的流程 8 糖凡nuv雠灶瑗nv 复旦大学硕上学位论文w e b 日志挖掘新方法 第二章w e b 日志预处理 2 1w e b 日志的格式 w e b 日志一般符合w 3 cw o r k i n gd r a f ( 推荐的c l f ( c o m m o nl o gf i l ef o r m a t ) ” 和e c l f ( e x t e n d e d l o g f i l e f o r m a t ) 1 9 1 标准，其常用的字段和含义如f i g 2 1 所示。然 后f i g 2 2 给出了实际的w e b 日志数据。 字段名称描述 h o s tn a n l c访问者的域名或i p 地址 a u t hu s e t访问者的l d ，如果身份认证，则为空 d a t e本次请求的日期和时间 m e t h o d 请求方法( g e t ，p o s t ，h e a d ，等) u r l访问者请求的文件( 网页或图片等) 的完整地址 s t a t u s服务器发送给浏览器的状态信息 s i z e本次请求传送的文件的大小 r e f e r e r 上次请求的u r l ，本次请求的来源( 引用者) a g e n t 用户的浏览器和操作系统类型 f i g 2 1w e b 日志数据格式 目j 峭tm h目抽 盘越袖日，枷 翻f b 0 ”“删0 e 广l 妯日| l t t i r 妁l 蛙h i d a , y e w d 女“h h # 4 g m * m ) 斡喇鞠：t 够* 一州 谢 m t i j 巍t 鼬_ t a | m 埘黼n 日日m 日# v m 黯8 w w 雌 口 ：l - 叫 e r m m l ，略h b 黼n # f l * 舶d d o 帮n m 帅 静蚪曲自1 ：1 甜如i 1 0 qw m t m ，1 l l 啦h b m 0 * 口i j 目抽q 自溯嗣畦露m 社i f 6 m ”，删 w k t t * tr 女n h h 。n l a | b a h 衄_妊瞄 黼m 静啊铺舯：l 惜制 h h n r l r螂4h h “椭州唰n i d抽嘣鼬轴i 1 _ l e l 9 锎 嘲i f ；l d i i ：t h 删 程r c m 日h r t 卦 ， h b 日一咀u e o 抽“ 埔心蛆牌b 4 蜘 p 孵确口嘲：1 t 1 2 羽1 日e 聊1 酏蹦撼9 瓤n w 嘲n 社自b o l _ t # 删 r m 卅m 1 r i 般h d * 帆4 n o 日n 4 l 姗m m 蛳酬d 扫鞭_ 曲融m ：l t l i 。口i镶 ，1 ，l ” h 0 女h 舟b 螺幽档蛳强删酗鼬 瓤w ”蚪n 脚旧蛔忡i ：塘l 鬟- 删 。蓝r h h 雌t 协 。 t鼬h n 黼a 4 舢粗对 m m 嘲m 赫旰鞠0 * 州 w 8 刚瑚，1 傩b “a 瑚h 陶脚糯i赫口翰黼l 硎* 0 珏 i _ 嗥拍0 妊1 q 晰“i1 l - q镰r i 雌，胡t 钠， 缆镕m m 聱薛曲：l 村堋- ，叫 噶f 渊”h 1 j 。 翱b 皤黼d i a 蚝l 抽d 柏1 础o 釉n 惜椒力 嘲f 翱6 嘲i 蛸 q懂 | n m i ，r h b _ x d 镌蛐抛m 目瑚帅 f i g2 2 来自某大学网站的一段w e b 日志数据 9 复日大学硕十学位论文 w e b 日志挖掘新方法 虽然w e b 服务器忠实的记录了用户对它的每次访问，但不可避免一些“噪音” 的存在。如：一些无需考虑的访问信息( 如图片文件、声音文件的访问记录) 也会 被记录在w e b 日志中；一些访问记录虽然有相同的i p 地址，但是可能是来自于同 一个p r o x y 服务器的不同用户，这在w e b 日志中不易区分；用户本地和p r o x ys e r v e r 的c a c h e 的使得有些网页访问直接从c a c h e 中获得，从而在w e b 日志中没有记录， 造成访问数据的遗漏。而且，也没办法直接在原始w e b 日志上直接施加w e b 挖掘 方法。所以必须先对w e b 日志进行行预处理。 w e b 日志预处理一般分为数据净化( d a t ac l e a n i n g ) ，用户识别( u s e r i d e n t i f i c a t i o n ) ，会话识别( s e s s i o ni d e n t i f i c a t i o n ) ，路径补充( p a t hc o m p l e t e ) ，事务 识别( t r a n s a c t i o ni d e n t i f i c a t i o n ) 5 个部分 2 3 。f i g 2 3 描述了各个阶段的次序关系和 相互间联系。w e b 日志预处理最后生成的事务文件将作为后面的挖掘工作的基本数 据。本章的后面几节将对w e b 日志预处理的每个部分做详细说明。 2 2 数据清理 f i g23 w e b 日志预处理过程 根据h t t p 协议的特征，用户获取w e b 服务器上的每一个文件( 包括图像和声 音等被用h t m lt a g 嵌入到网页中的文件) 都要发送一个请求。用户请求一个网页 时，网页内包含的图片、声音等文件也同时被浏览器作为单独请求提交给服务器了。 1 0 复旦大学硕士学位论文w e b 臼志挖掘新方法 通常情况下这些图像声音文件的访问记录与w e b 日志挖掘的目的是无关的，因此可 以删除这些无关的项来达到数据净化的目的。实现方法可通过查找访问记录中 u r l ，如过发观其请求的文件以g i f , j p g ，j p e g , w & v 等为后缀的文件就可以将该记录 删除。还有，如计数器c g i 脚本，也经常被嵌入到网页中，需要将其删除。 这一步的实现方法比较简单，可以用一个过滤器来遍历整个w e b 日志，发现某 条记录满足给定条件( 如请求的u r l 后缀为g i f , i p g ，w a v ) 就将其删除。而且，过 滤条件可以由管理员根据具体的情况，自己设定。 2 3 用户识别和会话识别 用户会话是一个用户对网站的一次访问过程。具体来说，就是用户打开浏览器， 在地址栏中输入w e b 站点的u r l ，然后连续点击网页上的超链接，访问该网站中 自己感兴趣的页面，直至用户离开网站或关闭浏览器的过程。用户在这个过程中在 w e b 日志中留下的w e b 访问记录序列，形象的称为一个c l i c k s t r e a m 。 w e b 站点为了识别用户，目前已有多种方法在采用：在c o o k i e 中嵌入用户i d ； 采用客户端软件如j a v a s c r i p t 等记录用户并将活动记录发送给服务器；对在网站注册 过的用户用s e s s i o n 进行跟踪。但现实情况是：用户可能因为安全方面的考虑而关 闭c o o k i e ：客户端搜集的办法会因为可能泄露用户隐私而引起用户反感使用不是 很广泛：用户访问站点时往往不愿登录，采用匿名的方式访问。在上述情况下，w e b 访问记录中的用户i d ( a u t hu s e r ) 字段都是空值，只能通过分析i p 地址、a g e n t 等信息，并结合w e b 站点结构，采用一些启发式搜索策略，识别不同的用户和用户 会话。 下面列出影响用户会话的识别的主要因素： ( 1 ) 单个i p 地址多个用户会话 例如，t s p 利用p r o x y 代理为用户提供服务，这样，同一个i p 访问同一个w e b 站点很可能使用同一个p r o x y 代理的不同的用户。 ( 2 ) 多个i p 地址单个用户会话 有些i s p 对来自同一个用户的请求，会随机分配若干个i p 中的一个给用户， 这样，一个用户会话会有不同的i p 。 ( 3 ) 多个i p 地址单个用户 从不同机器上访问w e b 的同一个用户因为不同的进程而拥有不同的i p ，这也 使得追踪同一个用户变得复杂。但这种情况往往是用户出于不同的访问目的才会用 不同的机器来访问的，而且这种情况出现的也比较少。对整体的影响不大。 ( 4 ) 多个服务会话单个用户 这种情况发生在用户打开多个浏览器窗口，同时对同一个站点的不同部分进行 复旦大学颁士学位论文 w e bu 志挖掘新方法 i 方问。这时可能会被认为是来自同。个i p 地址的不同用户的访问。但由于用户可能 是出于不同的目的，所以即使认为是不同用户的访问会话，也是可以接受的。 这些因素，特别是( 1 ) 和( 2 ) ，使得从没有用户i d 的w e b 日志中完全正确的识别 用户会话是不可能的。只有根据其的特点，采用一些启发式策略，尽可能还原用户 会话，为后面的事务识别阶段提供正确的数据。以下是识别用户会话的策略。 如果访问记录中的i p a g e n t 字段有一个不同，认为其属于不同用户 i p a g e n t 相同，但是某条访问记录的r e f e r e r 字段所记录的网页不在当前已 识别的用户会话里，这说明当前用户会话不能通过超链接导航到该条记录所 代表的网页，所以认为该条记录属于不同的用户会话 l c a t l e d g e 曾对w e b 用户访问行为做过统计，认为如果两条连续的访问记录 的时间间隔超过2 5 5 分钟川，这两条记录将有很大的可能是属于不同的用 户会话，一般为方便起见取间隔时间为3 0 分钟。 如果一条访问记录的r e f e r e r 网页出现在多个当前会话序列中，则将其加入 到其出现最近的那个会话中。如：a - b c - d ，a 一 e - f c 是当前正在识 别的两个会话，a ，b ，代表网页。如果当前考虑的访问记录访问网页g ，而 g 的r e f e r e r 网页是c ，则将g 加入到第二个会话中去。 下面是上述根据策略给出的算法。 设s e s s i o n = s l ，s 2 ，s 3 ，s m ) 是当前用户会话的集合，l 是w e b 日志，l 是w 曲日志中的一条访问记录。根据w e b 日志的格式，包括属性l i p , ，u r ll d a t e , 1 r e f e r e r ot 为事务的最大时间间隔。假设l 中的访问记录具有相同的i p a g e n t ( 不 同的i p a g e n t 肯定是不同的事务，可以把w e b 日志先按照口a g e n t 分类) ，并且 按照d a t e 递增排序。给出算法的伪代码为： 复日大学硕士学位论文w e b 目志挖掘新方法 但是这种方法识别用户毕竟不是完全准确的。这是在w e b 日志除了i p a g e n t 之外没有其他用户身份标志时，不得己所采用的方法。 作者曾提出一种采用u r l 重写来识别用户会话的方法。这，手f f t 方法不用客户端软 件支持，使用起来比较灵活方便。其主要思路是： ( 1 ) 当用户会话开始，也就是用户开始访问网站时，w e b 服务器为用户分配一个 唯一的s e s s i o ni d ，并在传送给用户的网页的所有u r l 后都附带上这个s e s s i o n 1 d 。即如下形式： h t t p ：w w w a b c d c o m j a h t m l 7 & s e s s i o n i d = 1 3 1 2 3 4 & ( 2 ) 用户点击任何u r l 访问下一个的网页时，都会把u r l 后的s e s s i o n l l 3 返回 给w e b 服务器，w e b 服务器以此判断请求是来自于哪一个用户会话。 ( 3 ) 在本会话过程中，服务器发送给用户的网页的u r l 中都带有此s e s s i o ni d ， 服务器以此来跟踪用户会话，并在w e b 日志中，把每次访问的相应s e s s i o nd 写入到访问记录中。 “) 这样，用户识别会话识别十分简单，具有相同s e s s i o n1 i ) 的w e b 访问记录 属于同用户的一个会话。 2 4 路径补充 由于本地高速缓存的存在，用户访问的一些页面可以直接从c a c h e 中获得，因 而这些访问信息没有被包括在w e b 日志中，造成w e b 曰志访问信息的不完整。解 决这一问题的一个策略是，如果在一个用户会话的一条访问记录中，r e f e r e r 字段中 的网页于该会话中的上一个网页没有直接的链接关系，可以认为是用户点击 b a c k ” 键回退导致的。查出r e f b r 盯网页在会话中的位置，把从该位置到当前访问记录之间 的网页补充进去。这样，般可以修正由于本地高速缓存的使用而引起的当用户单 击“b a c k ”键时所产生的路径信息不完整的描述。同样也可以借助网络拓扑结构的 信息，将w e b 日志会话文件中一些未描述的信息补充完整。 2 5 事务识别 事务识别的目的是在用户会话识别的基础上，依据数据挖掘任务的需求将用户 会话做分割或合并的处理，以利于特定知识的发现。其任务就是对输入的会话集合 进行分割或合并处理，输出事务序列集合： t = ( f 。，f ：，t ，t ) ( 2 1 ) ，其中f 为被识别的事务序列， f = ，“吼讹l , l i t i m e ) , ( z u r f , l ：砌甸，也u f 0 f 触p ) ) ( 2 2 ) 复旦大学硕士学位论文w e b 日志挖掘新方法 对l = k = m ，。l ( l 为访问记录集) ，i p = l 。i p ，f 。u i d f u i d 事务识别的算法曰前包括引用长度( r e f e r e n c el e n g t h ) ，最大向前路径( m a x f o r w a r d p a t h ) ，时间窗口( t i m e w i n d o w ) 。根据不同的数据挖掘目的，可以采用不同 算法。其中引用长度是指页面的浏览时间。引用长度法以浏览时间为依据，把网页 分为辅助页和内容页，以此来分割用户会话。最大向前路径法以w e b 目志访问序列 中的访问链的最大向前深度来决定事务。时间窗口法则仅仅通过时间差w 来分割事 务，同一个事务中的任意两个页面的最大访问时间差不能超过w 。 由于事务识别的输出结果是实施w e b 挖掘的数据来源，其质量直接影响到w e b 挖掘的准确性和精确性，所以其算法的选择十分重要。下面对三种事务挖掘算法详 细分析。 2 5 1 引用长度 引用长度算法假设网页分为两种类型：辅助页面( a u x i l i a r yp a g e ) 和内容页面 ( c o n t e n t p a g e ) 。内容页面被认为是因为包含了用户感兴趣的信息而被浏览的页面， 通常用户花费在浏览这种页面的时间较长。辅助页面是指为获得感兴趣的页面而访 问的一些中间页面，通常用户浏览这种页面的时间较短。 通常认为，用户每次访问的目的是为了获取特定的内容页面，而为了达到内容 页面，中间要通过一些辅助页面的导航。根据这种方式，可以把用户会话序列中， 从辅助页面开始到某个内容页面结束，定义为一个事务称之为一个辅助一内容事务。 如果只关心内容页的请求，可以定义事务为一次用户会话过程中所访问的内容页， 由于这种事务只包含内容页，我们称它为内容事务。f i g 2 4 是两种事务的一个示例。 十忖卜什叶_ 卜 事务1事务2事务3 ( 辅助内容事务) 页面 。恚苎! 、 a 莴蕃箦； ( 内容事务) f i g 2 4 引用长度法的两种事务 辅助页面和内容页面通过浏览时间长短上来区分。问题是如何计算时间阈值。 通过从w e b 站点g r i p 2 0 】的w e b 日志中统计的页面的引用长度和引用数的关系曲线 4 一 复旦大学硕十学位论文w e b 口志挖掘新方法 ( f 唔25 ) ，可以看到其分布具有指数特征：在曲线的低端( 这部分主要是辅助页面) ， 引用数变化刚，引用长度变化不明显：而到高端的内容页面，引用长度变化非常大。 对其它站点的访问日志统计也证明了这点。 f i g2 5 分布曲线函数 据此构造页面分类和引用长度的分布函数： 1 2 ，- y 2 万p “( 2 - 3 ) 设其中自变量为引用长度，因变量为w e b 访问日志中页面的访问率，? 为指数分布 的观察平均数的倒数，在这里即估计的页面平均访问时间。假设? 为访问记录中辅 助页面的访问率( 估计值) ，将指数分布函数从? 到。积分，得到辅助页面最大引用 长度： t = 掣( 2 。) 这个t 就是区分辅助页面和内容页面的阚值，凡引用长度小于t 的认为是辅助页面， 大于t 的则是内容页面。 为采用引用长度识别事务，可以将式2 - 2 中的事务修改为如下的序列： 复旦大学硕士学位论文 w e b 日志挖掘新方法 f _ ( i p ，u i d ，f 】u r l ，it i m e ，。l e n g t h x ( 1 2u r l ，1 2 t i m e ，f 2 l e n g t h ) , ，( f ，f “，l ，t i m e ，1 。l e n g t h ) ) ( 2 5 ) 其中l e n g t h 即为网页的引用长度，这可以由序列中前一页面的请求时间 f t i m e ) 减去后一页面的请求时间得到。 如果是辅助内容事务，则t 满足条件： 1 k m 一1 ：k l e n g t h t ， t ( 2 6 ) 即前i r 卜1 个页面是辅助页面，最后一个页面是内容页面。 如果是内容事务，则t 满足条件： l k m ，t l e n g t h t ( 2 - 7 ) 即所有的页面都是内容页面。还有一种可能是，有些页面即是辅助页面，也是内容 页面。如果要把这些页面也包含在内容事务中，可以修改引用长度阈值，比如令其 为t 2 。 内容事务适合于用户兴趣模式和兴趣页面的挖掘，而辅助一内容事务适合于访问 频繁路径的挖掘。这说明了，必须根据不同的挖掘目的，选择不同的事务识别方法。 2 5 2 最大向前路径 在经过路径补充后的用户会话中的页面既包含用户请求的页面又包含路径补充 时添加的页面。遍历路径有两个移动方向：一个是前进，即请求页是此前从未访问 的页面；另一个是后退，即请求页是在用户会话中已经访问过的页面。向前进行时 会有新的页面加入遍历路径：而向后回退的过程并没有扩展遍历路径，只是再一次 访问了遍历路径已包含的页面。可以把用户会话中的页面表示成一棵扩展有向树。 构造扩展有向树的过程是： 假设当前页为p ，上一页为t ( 1 ) 把用户会话中的第一个页面作为根结点，令t 为根结点 ( 2 ) p 指向下一页面，若p 不在已生成的树中，从t 引一条实线指向p ，即把p 作为t 的孩子。此时再将t 指向p f 3 ) 若p 已在生成的树中，则从t 引一条虚线指向p ，将t 指向p ( 4 ) 重复( 2 ) 、( 3 ) 直到用户会话中的最后一页，这时得到的树就是该用户会话的 扩展有向树 例如用户会话为( a ，b ，c ，d ，c ，b ，e ，f ，e ，g ) 的扩展有向树如图2 5 所示 复旦大学硕士学位论文 w c b 日志挖掘新方法 向前路径 - 后退路径 f i g 26 扩展有向树 采用最大向前路径识别事务的思想是：从根节点到最大向前页面即时子节点中， 只有叶子节点是用户感兴趣的内容页面，而路径中的其他页面则是导航( 辅助) 页 面。所以，把从根节点到叶子节点的每条路径看作一个辅助内容事务：把所有的 叶子节点看作一个内容事务。这样，上述会话的辅助一内容事务为( a ，b ，c ，d ) ，( a ，b e ，f ) ，( a ，b ，e ，g ) ；而内容事务为( d ，f ，g ) 。 最大访问路径法相对于引用长度法的优点是，它不需要有像引用长度法中的时 间闽值t 那样的估计参数。而且访问路径很好的体现了用户浏览网页的序列模式。 但是它忽略了访问时间这样一个重要的信息，对于一些主要通过浏览时间来衡量用 户兴趣的w e b 日志挖掘方法可能不太适合。 2 5 3 时间窗口 时间窗口法很简单，即通过时间窗口w 来分割会话，使得同一事务中任两个网 页的访问时间差不能大于w ，因为网页访问序列是按时间递增的，所以简单来说就 是事务t 中的 ( e t i m e 一，- t i m e ) ，k 定f 手最后一个页面( 2 - 8 ) 时间窗口仅仅根据时间来划分事务，所以无法正确识别辅助页和内容页。它一 般不用来直接识别事务，而是用来对其他两种方法识别出事务的事务做分割或合并。 如果一个事务的时间距离大于w ，则将其分割成两个事务；如两个事务的总时间距 离小于w ，则将其合并成一个事务。 复旦大学颐j 学位论文 w e b 日志挖掘新方法 2 5 4 事务识别总结 事务识别是w e b 日志预处理中最复杂和最关键的一个部分，事务文件将直接供 数据挖掘阶段使用，所以事务识别的质量的将关系到以后的工作。如同前面所论述 的，事务识别的方法有多种选择，必须根据w e b 数据挖掘工作的要求和目的，选择 适当的事务识别方法，而没有一种能够在任何情况下通用的方法。引用长度法能较 好的识别内容页面，其识别的事务适合于用户兴趣模式挖掘；最大向前路径法体现 了用户访问的序列模式，适合于频繁路径的挖掘。 复旦大学硕土学位隆文w e b 日志挖掘新方法 第三章采用i r s t 模型挖掘w e bb 志 通过对w e b 日志的预处理，得到w e b 日志事务集合t = ( l ，t ：，t ，t 。) 后，就可 以在其上直接运用数据挖掘来发现我们感兴趣的模式和隐含信息了。将数据挖掘中 关联规则挖掘和序列模式挖掘应用于w e b 事务，来发现页面间的关联和用户的频繁 路径，是一种最常用的w e b 挖掘方式。 关于数据挖掘中的关联规则和序列模式挖掘，自1 l a g r a w a l 提出这两个概念之 后，出现大量研究和许多算法。但是w e b 日志事务有其自身的特征，并不是所有的 算法都能适用。本文将分析这些算法的优劣，并将一种新的数学模型互关联后 继树( i n t e r - r e l a t e ds u f f i xt r e e ) 应用于w e b 事务挖掘。 互关联后继树( i r s t ) 是胡运发教授在文献【22 j 中提出的一种发现频繁项集的数 学模型。这种模型能保持事务的序列结构，减少全文存储的膨胀比，具有较高的奄 找速度。i r s t 从其结构和特征上看十分适用于w e b 挖掘中的频繁路径的识别。频 繁路径是在w e b 日志事务中出现频率大于一定值的页面序列，即频繁被用户访问的 页面路径。为了做研究，本文用实现了一种i r s t 的构造和模式搜索系统，并在实 验中运用此系统在实际w e b 日志数据中挖掘频繁路径，以此分析i r s t 效率，速度 等特征。 3 1 关联规则挖掘 关联规则是k d d 研究中的个重要分支。自从r a g r a w a l 等在s i g m o d 9 3 2 4 】 上第一次提出这个问题以来，关联规则一直是众多学者的研究热点。现已发表的研 究论文包括确定性关联规则的挖掘、量化关联规则的挖掘、增量式关联规则的挖掘、 模糊关联规则的挖掘、广义关联规则的挖掘等。关联规则挖掘的目的是在交易数据 库中发现各项目之间的关联关系。a p f i o d 2 4 】是a 掣- a w a l 提出的著名的关联规则发现 算法，该算法首先提出识别频繁大项目集这一核心任务。在此基础上还有更多的优 化算法，如：a p d o r i ti d 【2 ”，p a r k 等人提出的d h p t ”，多层关联规