（计算机应用技术专业论文）web日志挖掘相关算法研究及其原型系统设计.pdf

西南交通大学硕士学位论文第1 页 摘要 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 日志挖掘原型系统( w l m s ) 。 本文的工作主要有以下几个方面： 1 、在改进f p g r o w t h 算法的基础上，提出挖掘用户频繁访问模式序列的 f a s m i n i n g 算法，通过构建f a s t r e e ，在其上进行挖掘得到最大频繁访问模式 序列，进一步转换生成模式分析所需的不同深度的频繁访问模式序列，并分析 了相应的增量更新算法，通过实验证明了算法的有效性。 2 、提出一种快速挖掘w e b 页面间关联规则的算法，结合网站既有拓扑结构 和w e b 页面信息，定义相应的页面距离，保证页面关联规则有较高的兴趣度， 以发现网站设计和用户访问兴趣关联的不一致，为网站结构优化提供有效的决 策参考。 3 、提出一个快速有效挖掘w e b 日志文件中聚类模式的c l o p e 1 算法，从 提高用户覆盖面和减少收益值计算量的角度，改进c l o p e 聚类算法，并分析了 算法的时间和空间复杂度，探讨了算法在w e b 日志挖掘中的具体应用，并在具 有典型结构的合成数据上进行了用户聚类的实验。 4 、把现有的一些通用的w e b 挖掘技术及本文提出或改进的算法集成起来， 结合关系数据库的特点，完成了一个w e b 日志挖掘原型系统w l m s 的设计工作， 阐述了系统整体实现的考虑，并按照挖掘的过程简要介绍了系统的处理流程及 各个主要组成模块的接口和功能设计。 关键词：w e b 日志挖掘；关联规则；用户访问模式；用户聚类：w e b 挖掘 西南交通大学硕士学位论文第页 a b s tr a c t w e bm i n i n gi sah o tr e s e a r c hi s s u ew h i c hc o m b i n e sv a r i o u st e c h n o l o g i e sa n d m e t h o d sb e t w e e nd a t am i n i n ga n dw w wi ng e n e r a l w e bm i n i n gi n c l u d e st h r e e r e s e a r c hf i e l d s ：w e bc o n t e n tm i n i n g ，w e bs t m c t u r em i n i n ga n dw e b u s a g em i n i n g w e b u s a g em i n i n ga i m st od i s c o v e rt h eb e h a v i o rr u l e sw h i l eu s e r sb r o w s ew e bs i t e ， t oi m p r o v et h es i t es t r u c t u r ea n dt h el i n k a g es t r u c t u r ea m o n g p a g e s ，t oe n h a n c et h e q u a l i t yo fw e bs e r v i c e s ，a n dt op r o v i d et h ed e c i s i o ns u p p o r to nc l i e n tr e l a t i o n s h i p m a n a g e m e n to ft h ee c o m m e r c e h a v i n gm a d ea n a l y s i sa n dr e s e a r c h e so nw e bu s a g em i n i n gs y s t e m i c a l l yb a s e d o nw e bl o gr e c o r d s rt h i st h e s i s i m p r o v e sa n dp r o p o s e st h r e en e wd a t am i n i n g a l g o r i t h m s ，d e s i g n sap r o t o t y p es y s t e mo fw e bl o gm i n i n gt h r o u g ha p p l y i n gt h e i m p r o v e do rp r o p o s e da l g o r i t h m st ow e bu s a g em i n i n g t h em a i nr e s e a r c hw o r ki nt h i st h e s i si n c l u d e st h ef o l l o w i n g s ： ( 1 ) f a s - m i n i n ga l g o r i t h mf o rm i n i n gu s e r s f r e q u e n ta c c e s s i n gp a t t e r n si sp u t f o r w a r db yi m p r o v i n gf p - g r o w t ha l g o r i t h mw h i c hi su s e dt om i n i n g f r e q u e n ti t e m s e t s f a s m i n i n ga l g o r i t h mf i r s t l yc o n s t r u c t sf a s t r e ea st h eo b j e c tf o rm i n i n gm a x i m a l f r e q u e n ta c c e s s i n gp a t t e r n s ，a n dt h e nt r a n s f e r st h e s ep a t t e r n si n t of r e q u e n ta c c e s s i n g p a t t e r n so fd i f f e r e n td e p t h e so nd e m a n d a l s o ，t h ei n c r e m e n tu p d a t ea l g o r i t h mo f f a s - m i n i n gi sa n a l y z e d ，a n df i n a l l yt h ee f f e c t i v i t yo ff a s - m i n i n gi sp r o v e db yt e s t ( 2 ) a f a s ta l g o r i t h mf o rm i n i n ga s s o c i a t i o nr u l e so fw e bp a g e si sp r o p o s e d ，w h i c h c o n s i d e r sb o t ht h ew e b - s i t eo r g a n i z a t i o na n di n f o r m a t i o no fp a g e si no r d e rt oe n s u r e h i g hi n t e r e s t i n go fa s s o c i a t i o nr o l e sa n dt o d i s c o v e rt h e d i s p a r i t yb e t w e e nt h e o r g a n i z a t i o no fw e b s i t ea n dt h ea s s o c i a t i o no fu s e r s i n t e r e s t ( 3 ) b yi m p r o v i n ge l o p ea l g o r i t h ma n dc o n s i d e r i n gb o t he x p a n d i n gs c o p eo f u s e ra n dr e d u c et h ew o r k l o a do nc a l c u l a t i n gb e n e f i t so fc l u s t e r i n g ，e l o p e 1 a l g o r i t h mi sb r o u 【g h tf o r t h t h e nt h et i m ea n ds p a c ec o m p l e x i t yo ft h ee l o p e - 1 a l g o r i t h ma r ea n a l y z e d f i n a l l y , t h ea p p l i c a t i o no fe l o p e 1a l g o r i t h mo nw e bf o g m i n i n gi sd i s c u s s e d ，a n dat e s tf o re l o p e - 1a l g o r i t h mi sa l s od o n eo nt h ed a t aw i t h t y p i c a ls t r u c t u r e ( 4 ) ap r o t o t y p es y s t e mf o rw e bl o gm i n i n g ( w l m s ) i sd e s i g n e db yi n t e g r a t i n g t h ee x i s t i n gg e n e r a l p u r p o s et e c h n o l o g i e sw i t ht h ei m p r o v e do rp r o p o s e da l g o r i t h m s a b o v e a l s o ，t h em a i nm o d u l e s a n di n t e r f a c e so fw l m sa r ed e s c r i b e di nd e t a i l s k e yw o r d s ：w e bl o gm i n i n g ；a s s o c i a t i o nr u l e ；u s e r s a c c e s s i n g p a t t e r n s ；u s e rd u s t 6 。； w e bm i n i n g 西南交通大学硕士研究生学位论文第1 页 1 1 研究背景与意义 第1 章绪论 1 1 1 研究背景 中国互联网近年来呈现爆炸性的增长，c n n i c ( 中国互联网信息中心) 每半 年的大规模问卷调查显示：互联网用户基本上每六个月翻一番。而更为深刻的 变化在于，在国内网民数量大大增加的同时，互联网的应用范围也在迅速扩展。 早期互联网或多或少带有娱乐成分，而现在则更多地渗透到生活、工作和交流 的各个方面。尤其是作为大众传媒，已经成为报纸、广播和电视等传统媒体强 有力的竞争者，以及不可替代的补充。这标志着中国的互联网开始走向成熟。 w e b 上的数据正以每天新增一百万个页面的速度增长，页面数目已超过1 0 亿。w e b 已经成为人们获取信息的重要手段。w e b 是一个快速变化的信息源，不 单单是网上内容的急剧膨胀，页面内容的改变也是极度频繁，新闻、股票市场、 广告公司和网络服务中心都在一定的时间间隔内修改着他们的网上信息。另外， 网页的链接和存取路径也常常被改变，还要面对各种不同的用户，而且用户的 数量也在不断地增长，其使用兴趣和目的各不相同。 随着w e b 在信息共享、电子商务和提供在线服务方面的广泛应用，许多企 业投入大量资金建立自己的网站用于发布信息，或在别人的网站上为自己的产 品和服务作广告，或在网上开展电子商务活动，他们迫切需要了解这些投资产 生的效益和作用，以便改进企业的策略，获取更多的商业机会，为用户提供更 优质的服务。因此，理解用户的行为对这些企业来说至关重要。 用户在网站上的活动隐含了他们的需求和兴趣，如果对用户的行为加以分 析，就有可能发现一些潜在的规律。了解用户在网站上的访问模式和兴趣爱好 有助于优化网站的组织结构和空间设计，例如：在高度相关的页面或站点之间 提供快速有效的访问途径【l l ，设计外观和布局更加友好的页面，以方便用户获取 信息和服务；改善企业的市场营销策略，例如：对用户进行更为准确的聚类， 推荐其可能感兴趣的信息和服务，识别潜在的电子商务客户，在关心企业产品 西南交通大学硕士研究生学位论文第2 页 和服务的用户经常访问的页面或站点放置广告；分析和提高w e b 服务器的性能 和信息服务质量，例如：提供w e b 页面缓冲、页面预取和页面推荐，改善服务 响应时问；为用户提供个性化的服务，例如：为用户动态调整网站结构、页面 内容和外观，使其更加符合用户的偏好和信息需求，减轻用户搜索和过滤海量 信息的负担。 w e b 服务器日志记录了用户与服务器的交互信息，对于掌握w e b 服务器的运 行情况、分析用户需求、维护系统安全、辅助站点维护入员优化站点具有重要 作用【2 l 。对日志采用统计分析和联机分析处理( o l a f ) 的方法，可以对常用数据 进行汇总，提供关于用户行为的统计报告。但为了在更深的层次上理解用户的 行为和w e b 站点的结构，得到诸如用户的访问模式和兴趣爱好等有用信息，就 要用到数据挖掘的方法，于是产生了w e b 日志挖掘。 1 1 2 研究意义 w e b 日志挖掘的研究成果主要应用在以下几个方面： ( 1 ) 调整网站信息的组织和显示，优化服务性能。应用w e b 日志挖掘学习群 体用户的访问模式，并据此做出调整，使网站对于大多数用户来说更易于访问。 这些调整可以是：通过用户浏览路径进行挖掘来进行页面聚类从而调整网站 的链接结构；合理设置广告页面。 ( 2 ) 发现商业智能，辅助商业决策。在电子商务网站，把w e b 日志和顾客交 易信息相结合进行挖掘，能够发现关联购买集合、顾客的购买趋势，以及潜在 顾客对商品的兴趣，从而对商品信息在页面的显示进行调整以方便顾客浏览和 购买，为顾客推荐相关商品，预测顾客的购买兴趣，还可以把潜在的顾客转变 为实际的购买者。 ( 3 ) 提供在线推荐和页面预取机制。由于w e b 用户的增加和网络固有的延 迟，用户对w e b 服务器的请求常常得不到及时的响应。为了提高服务质量，w e b 浏览器提供缓冲机制，把用户曾经访问的w e b 页面保存在本地机器，以便减少 再次获取该页面的时间，平衡网络负载，提高响应速度。而w e b 预取机制却是 对用户未来的请求进行预测，把用户可能访问的页面预先取回放在本地或代理 服务器，当用户要访问这些缓冲过的页面时，就不必从远程服务器传输了，这 样能大大减少用户等待韵时间。因此，w e b 预取是一种主动的缓冲网。可以将活 动用户距当前最近的短期访问历史与应用w e b 使用挖掘技术发现的模式( 如频 西南交通大学硕士研究生学位论文第3 页 繁遍历路径或频繁访问页组) 进行匹配，确定用户当前所遵循的浏览模式：并 分析当前请求页面中的每一个超链接，从反映用户兴趣的角度计算每一条超链 接的质量，并把质量大于给定阀值的超链接推荐给用户或将其指向的页面预先 取到本地【4 1 ( 4 ) 响应每一个用户的特定需求，为其提供个性化服务。互联网海量信息与 用户狭窄专一需求产生矛盾，一方面造成信息资源的巨大浪费，另一方面。为 用户寻找所需要的信息造成巨大困难，因而需要提供个性化服务四。应用w e b 日志挖掘通过对用户访问历史的分析，发现个体用户的访问模式，从该模式中 学习、记忆用户的兴趣、爱好、习惯和需求，建立个性化用户模型。把从w e b 上获取的源与个性化模型所描述的信息相比较，可以主动地有选择性地向用户 推荐符合其兴趣的个性化信息，如页面、链接、广告、经过裁剪的文本和图片 等。由于滤除了与用户需求无关的信息，因而大大提高了用户获取有用信息的 效率。应用w e b 日志挖掘建立个性化用户模型的优点在于； 不需要用户对自己的兴趣、爱好和需求进行描述。有时用户对自己的需 求很难清楚、明确地表达出来，而用户的行为自然地反映了其兴趣和需 求。借助于w e b 服务器日志中的客观数据自动发现用户的兴趣和需求， 能够减少主观性和减轻用户参与的负担。 个性化用户模型是从用户的访问模式中动态提取的，能够随着用户需求 的改变而不断调整，因而总是反映用户当前最新的兴趣和需求。 模型具有一般性的特点，适用于所有的w e b 用户。 基于个性化用户模型把具有相似访问模式的用户加以聚类，还可以根据 同一聚类用户的兴趣和爱好向个体用户推荐其最有可能需要的信息。 1 2 国内外研究现状 1 ，2 1w e b 日志挖掘的国内研究现状 c h e n 掣明首先将数据挖掘技术应用于w e b 服务器日志文件，以期发现用户 浏览模式。h a n 等1 8 】则根据w e b 日志建立数据立方体，然后对数据立方体进行 数据挖掘和联机分析处理。w e b 日志挖掘最初研究的重点放在对模式发现中挖 掘算法的设计、分析和改进，现阶段对日志文件预处理方法和模式分析的研究 也有所增加。 西南交通大学硕士研究生学位论文第4 页 国内的w 曲日志挖掘，主要侧重于理论研究。宋爱波等【9 l 提出了一种新颖 的m b p 算法，利用关联规则挖掘发现的频繁项目集以加快速度，能找出所有满 足阀值约束的频繁浏览路径。陈才扣等f l 。i 提出了一种新的w 曲访问序列模式， 并提出了识别最大向前访问路径和发现最大访问路径的算法。文献【1 1 】提出了一 种智能w e b 预取技术，用来加快用户浏览w e b 页面时获取页面的速度。杨怡玲 等【1 2 1 提出了一种w e b 日志预处理阶段的f r a m e 页面过滤算法；王实等【u l 提出了 k - p a t h s 路径聚类算法，根据用户访问兴趣对用户集进行划分：文献f 1 4 】提出了 一个用户识别的通用算法；张娥、潘登、宋敏青等【挎1 7 l 在w e b 挖掘研究方面做 了多项工作；李晓1 1 叼成功地将w e b 挖掘应用到了防洪网站中：张戈【1 9 3 也在做电 子商务网站中数据挖掘的研究。 从收集到的文献来看，国内对挖掘算法研究较多的是关联规则挖掘和序列 模式挖掘【删，以及频繁遍历路径挖掘【2 1 ，矧，而对聚类挖掘的关注较少。现有的 聚类主要集中在相似客户群体的聚类和相关w e b 页面的聚类。对于相似客户群 体聚类，国内的大多数研究者还停留在主要依靠统计学方法和简单聚类方法的 阶段，如采用基于模糊等价关系的聚类算法刎。黄松等陋】于2 0 0 1 年提出在聚 类前根据网页的层次性，采用面向属性的推理方法构造归纳化的会话向量，从 而减少会话向量的维数，生成基于归纳化会话的网络用户的聚类。 1 2 2w e b 日志挖掘的国外研究现状 s i m o nf r a s e r 大学的w e bl o gm i n e r t 2 6 】将w e b 日志中的数据组织为数据立方 体，然后在其上进行联机分析处理和数据挖掘。 h u m b o l d t 大学的w u m ( w e bu t i l i z a t i o nm i n e r ) 【2 7 l 能够挖掘w e b 日志中的 序列模式，并提供一个集成了日志准备、模式查询以及可视化的环境，但其模 式查询语言m i n t 在表达序列模式的约束时不够灵活。 m i n n e s o t a 大学的w e b m i n e r 系统【嚣】提出一种通用的w e b 日志挖掘的体系结 构，该系统能自动从w e b 日志中发现关联规则和序列模式等。w e bm i n e r 的思 路是通过对w e b 站点的日志进行处理，将数据组织成传统的数据挖掘方法能够 处理的事务数据形式，然后利用传统的数据挖掘方法( 如传统的关联规则算法) 进行处理。 i b m 公司的w 曲日志挖掘和分析工具s p e e d t r a c e r l 2 9 1 ，通过在用户会话上应 用数据挖掘能够发现频繁遍历路径和频繁访问页组( 其中的页面经常被一起访 西南交通大学硕士研究生学位论文第5 页 问，但不一定位于同一条遍历路径上) 。 ，0 n a s r a o u i ，h f r i g u i ，a j o s h i 和r k r i s h n a p u r a m 3 0 1 提出的c a r d ( c o m p e t i t i v e a g g l o m e r a t i o n f o rr e l a t i o n a ld a t a ) 算法，能够聚类非欧几里德的关系 数据，可用于从w e b 访问日志中自动发现用户的访问模式。该算法的缺点是不 够健壮 a j o s h i 和k j o s h i 3 1 】提出用于用户会话聚类的模糊聚类算法f c m d d ( f u z z y c - m e d o i d s ) 及其健壮性改进算法f c t m d d ( f u z z yc t r i m m e dm e d o i d s ) 。f c m d d 和 f c t m d d 在聚类前都要先确定一个固定的聚类数，因此聚类结果对初始值很敏 感。 1 3 研究内容与框架 1 3 1 研究内容 本文主要以w e b 服务器日志里的数据作为挖掘对象，通过挖掘用户在w e b 环境中的访问模式，发现用户访问兴趣间的关联度和站点拓扑结构的不一致， 并利用挖掘结果对网站结构进行调整；通过对用户浏览会话分析进行用户聚类， 进一步发现用户群体的兴趣、爱好，以有效地为用户提供实时推荐，优化访问 效能，同时为商业决策提供依据；最后，把现有的一些通用的w e b 挖掘技术集 成起来，设计了一个w e b 日志挖掘原型系统w l m s ( w e bl o gm i n i n gs y s t e m ) 。 具体说来，本文的研究工作主要有以下几点： ( 1 ) 挖掘用户频繁访问模式序列 在改进f p g r o w t h 算法的基础上提出挖掘用户频繁访问模式序列的 f a s m i n i n g 算法，通过构建f a s t r e e ，在其上挖掘得到最大频繁访问模式序列， 进一步转换生成模式分析所需的不同深度的频繁访问模式序列，并分析了相应 的增量更新算法，通过实验证明了算法的有效性。 ( 2 ) 挖掘w e b 页面问关联规则 提出一种快速挖掘w e b 页面间关联规则的算法，结合页面的条件访问概率 和范化内容链接比1 3 2 1 的概念，定义相应的页面距离，保证页面关联规则有较高 的兴趣度，为网站结构优化提供有效的决策参考。 ( 3 ) 用户会话聚类 提出一个快速有效挖掘w e b 日志文件中聚类模式的c l d p e 1 算法，从提高 西南交通大学硕士研究生学位论文第6 页 用户覆盖面和减少收益值计算量的角度，改进c l o p e 聚类算法，并分析了算法 的时间和空间复杂度，探讨了算法在w e b 日志挖掘中的具体应用，并在具有典 型结构的合成数据上进行了用户聚类的实验 ( 4 ) w e b 日志挖掘系统设计 把现有的一些通用的w e b 挖掘技术及本文提出或改进的算法集成起来，结 合关系数据库的特点，进行了一个w e b 日志挖掘原型系统w l m s 的设计工作， 阐述了系统整体实现的考虑，并按照挖掘的过程简要介绍了系统的运行流程及 各个主要组成模块的接口和功能设计 1 3 2 内容框架 全文共分六大部分。 第一章绪论：介绍了本文的研究背景及研究意义，分析了国内外对w e b 日 志挖掘的研究现状，引出了本文的研究主题和研究内容。 第二章w e b 挖掘和w e b 日志挖掘研究：概述w e b 挖掘的定义、特点和分 类，重点介绍w e b 日志挖掘的数据抽象和通用模型。 第三章用户访问模式挖掘：这一章主要分为两部分：用户频繁访问模式序 列挖掘和w e b 页面关联规则挖掘。详细介绍了各部分的理论方法及其算法，并 通过测试数据加以说明论证。 第四章一种快速有效的日志聚类算法：基于对c l o p e 算法的改进，提出 一种有效挖掘用户会话聚类模式的c l o p e - 1 算法，详细介绍了算法的改进思想 和具体实现，探讨了算法在w e b 日志挖掘中的具体应用，并在具有典型结构的 合成数据上进行了用户聚类的实验。 第五章w l m s 原型系统设计：介绍了w e b 臼志挖掘系统( w l m s ) 的结构 与框架，并将各模块的功能、接口设计做了详细的介绍。 结论与展望；总结了论文的主要工作和结论，对将来的研究工作进行展望， 提出了进一步的研究方向。 西南交通大学硕士研究生学位论文第7 页 第2 章w e b 挖掘和w e b 日志挖掘研究 2 1w e b 挖掘 2 1 1w e b 挖掘的定义 w e b 挖掘是- - n 交叉性学科，涉及数据挖掘、机器学习、模式识别、人工 智能、统计学、计算机语言学、计算机网络技术、信息学等多个领域。 从广义的角度出发，可以对w e b 挖掘作如下定义【3 3 l ： 定义p 1 ：w e b 挖掘是指从大量非结构化、异构的w e b 信息源集合中发现 有效的、新颖的、潜在可用的及最终可理解的知识，包括概念( c o n c e p t s ) 、模式 ( p a t t e r n s ) 、规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 、约束( c o n s t r a i n t s ) 及可视化 ( v i s u a l i z a t i o n s ) 等形式的非平凡过程。 以上定义借鉴了数据挖掘的传统定义。因此w e b 挖掘在部分方法和技术研 究方面也与数据挖掘相似，具有相通之处。 如果从实用性开发的角度来考虑的话，可以对w e b 挖掘作出如下定义削： 定义2 2 ：w e b 挖掘是针对包括w e b 页面内容、页面之间的结构、用户访 问信息、电子商务信息等在内的各种w e b 数据源，在一定基础上应用数据挖掘 的方法以发现有用的知识帮助人们从w w w 中提取知识，改进站点设计，更好 地开展电子商务等应用。 2 1 2 w e b 挖掘的特点 i n t e m e t 上存贮了大量的、非结构化的信息，无法使用现有的数据库管理系 统来操纵和管理。主要特点如下1 3 5 】： ( 1 ) 大量存在的文档、图形、图像、声音信息及大型的商业数据、天气、水 文数据等表现出多种信息类型，而且用户有充分的自由，可以随意链接到i n t e m e t 的任意站点上。因此，i n t e r a c t 本身体现了巨大的、分层的、多维的、非结构化、 动态性、不完全、混沌的特点； ( 2 ) 用户群体也表现出多样性，全球信息网大约有数亿个工作站，其用户具 西南交通大学硕士研究生学位论文第8 页 有不同的背景、不同的兴趣和目的； ( 3 ) w e b 上的信息只有很小的一部分是相关的或是有用的，甚至可以说9 9 n 的w e b 信息对于9 9 的用户是无用的。虽然这看起来不是很明显，但一个人只 是关心w e b 上的很小一部分信息却是事实，w e b 所包含的其余信息对用户来说 是不感兴趣的，而且会淹没所希望得到的搜索结果。 2 1 3 w e b 挖掘的分类 w e b 挖掘技术是实现w e b 个性化服务的核心技术之一，其一般过程可以分 为三个阶段： ( 1 ) 预处理：需要对收集的数据进行必要的预处理，例如清除“脏”数据； ( 2 ) 模式发现：应用不同的w e b 挖掘算法发现用户访问模式； ( 3 ) 模式分析：从模式发现的模式集合中选择有意义的模式。 w e b 挖掘通常可以分为3 大类，即w e b 内容挖掘、w e b 结构挖掘和w e b 使 用挖掘。其中，w e b 使用挖掘又分为w e b 日志挖掘和单个用户两类，如图2 - 1 所示。 图2 - 1w e b 挖掘的分类 w e b 内容挖掘( w e bc o n t e n tm i n i n g ) 是从w e b 资源中发现信息或知识的过 程。在创建个性化服务系统时，人们通常应用w e b 内容挖掘对网页内容进行分 析，其中网页的自动分类技术在搜索引擎、数字化图书馆等领域得到了广泛的 应用。根据实现方法的不同，w e b 内容挖掘可以分成基于代理的方法和数据库 方法。w e b 内容挖掘由于直接处理数据对象的内容，因此得到的结果一般比较 精确，在个性化系统中得到较广泛的应用。 w e b 使用挖掘通常可以应用到两个领域：当用来分析w e b 服务器的访问日 西南交通大学硕士研究生学位论文第9 页 志时，可以利用挖掘得到的服务模型来设计适应性w e b 站点；当应用到单个用 户时，通过分析用户的访问历史来发现有用的用户访问模式。w e b 使用挖掘由 于处理数据对象通常为用户的访问历史或服务器的访问日志，无法得知数据对 象代表的内容，因此得到的结果一般比较粗糙，但是由于该方法比较成熟而且 实现起来也较w e b 内容挖掘简单，在个性化系统中也得到了较广泛的应用。w e b 使用挖掘的基本方法包括：聚类、关联规则、序列模式、分类、统计分析等。 w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 包括页面内部的结构以及页面之间的 结构。通过挖掘w e b 结构信息，对于导航用户的浏览行为、改进站点设计、评 价页面的重要性等都非常重要。 2 2w e b 日志挖掘研究 2 2 - 1w e b 日志挖掘的定义 w e b 日志挖掘属于w e b 使用挖掘的范畴，是指采用数据挖掘的技术，通过 对w e b 服务器日志中大量的用户访问记录深入分析，发现用户的访问模式和兴 趣爱好等有趣、新颖、潜在有用以及可理解的未知信息和知识，用于分析站点 的使用情况，从而辅助管理和支持决策，为用户提供更好的，更为人性化的服 务。 不同用户对同一网站的兴趣存在差异，但多多少少会有某些相同之处，这 能够从他们在服务器日志中留下的访问记录反映出来。因此，通过对日志的挖 掘，可以发现用户的共同偏好和交叉兴趣。另一方面，同一用户在不同时期可 能有不同的访问模式，但从长期来看，也表现出一定的规律和趋势，能够反映 用户的兴趣。统计数据表明 3 6 1 ：大多数用户在网站上的活动范围是有限的，因 而他们的活动中必然包含了许多重复的动作，也印用户的行为是有规律可循的。 w e b 日志挖掘能够发现这些规律。此外，由于w e b 服务器日志中记录了该服务 器被外部访问的所有过程信息，通过对这些过程信息的分析，可以客观地反映 服务器的内部结构、组成、内容、访问频度等有关服务器的重要信息，这对于 评价和改进网站的服务质量来说是非常宝贵的资源。同时，在任何一个服务器 上都可以很方便地得到它的日志文件，数据的来源很方便，文件结构较为良好， 且数据挖掘技术的日趋成熟使德对这一不断增长的巨大数据文件的处理变褥可 能p 7 】。因此，w e b 日志挖掘是有效可行的。 西南交通大学硕士研究生学位论文第1 0 页 2 2 2 w e b 日志的内容 w e b 服务器日志记录着用户访闯该站点时每个页面的请求信息，w e b 日志 中一般每一条记录包括用户的i i i 地址、用户的m 、用户请求访问的页面、请求 的方法、错误的代码、访闯时闯等属性。 w e b 服务器日志的格式取决于服务器系统的配置，比较常见有通用日志格 式( c o m m o nl o gf o r m a t ) 、扩展日志格式( e x t e n d e dl o gf o r m a t ) 以及a p a c h e 和i i s w 3 c w e b 日志格式。表2 - 1 是一个日志记录的结构表： 表2 - 1 日志记录的结构表示例 属性域描述 日期用户请求页面的时间 时间用户请求页面的详细时间 用户i p 地址客户端主机的口地址或d n s 出口 用户名客户端的用户名 服务器名服务器的名称 服务器i p 地址服务器端的i p 地址 服务器端口服务器端的端口号 方法 用户请求的方法，比如g c t 等 访问页用户请求的页面 u r l 查询用户想进行的查询 协议状态h t f i 的状态标示 发送字节数发送数据的字节数 接收字节数接收数据的字节数 所花时间浏览耗费时问 协议版本h r r p 协议的版本 主机服务的操作系统 用户代理服务的提供者 * c o o k i ec o o k i e 标识号 引用页用户从哪一页跳转过来 西南交通大学硕士研究生学位论文第n 页 其中标有号的是扩展日志中增加的项，而其他的是通用日志和扩展日志都 存在的项。在我们的日志分析过程中，并不是所有条目都必须使用，我们只把 日志记录中用到的日志条目投影出来 2 2 3 w e b 日志挖掘中的数据抽象 万维网协会( w o r l dw e bc o n s o r t i u m ) 对于日志挖掘过程中的数据定义了以 下一些抽象1 3 8 】： 用户( u s e r ) ：通过浏览器访问页面的个体，我们称之为用户。用户可以通 过不同的机器或者使用不同的代理来访问网站。 页面浏览( p a g e v i e 们：用户点击鼠标来浏览网页所得到的有多个文件组成 的结果，一个页面浏览代表了一个具体的用户行为，标志着用户对网页的访问 记录。 点击流( c l i c k - s t r e a m ) ：用户在一次访问中连续的访问的网页的有序序列。 用户会话( u s e rs 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 ) ：用户会话中一段有意义的点击流。 2 2 4w e b 日志挖掘的通用模型 无论w e b 日志挖掘的最终应用目的是什么，挖掘的基本过程是一致的。w e b 日志挖掘的对象既然是日志本身，首先需要对日志进行预处理f 3 9 j 。w e b 日志并 非所有的日志记录都是可利用的，有一些记录是属于“脏数据”，必须进行必 要的日志清洗，并且我们从日志的格式中可以看出，并非日志记录中的每一项 对我们都是有用的，因而必须将我们使用到的那些项从日志中投影出来。根据 具体分析要求，我们可能仅仅为了考虑一些典型用户的使用模式，没有必要将 偶然用户的记录也包括在内，对于这种噪音数据，我们必须在输入到聚类或者 其他的分析步骤前就将其过滤掉。在经过这一系列的步骤之后，我们就可以将 日志从原来的记录形式进一步地抽象成为我们需要的数据，以便分析并加以应 用。w e b 日志挖掘的通用模型如图2 2 所示。 西南交通大学硕士研究生学位论文第1 2 页 图2 - 2 w e b 日志挖掘的通用模型 数据预处理 算法分析 应用分析 、0lr，j、，lrl-、l厂j 西南交通大学硕士研究生学位论文第1 3 页 第3 章用户访问模式及算法研究 3 1 用户访问模式概述 如前文所述，w e b 挖掘技术一般过程可以分为三个阶段：( 1 ) 预处理：需要 对收集的数据进行必要的预处理，例如清除“脏”数据；( 2 ) 模式发现：应用不 同的w e b 挖掘算法发现用户访问模式；( 3 ) 模式分析：从模式发现的模式集合中 选择有意义的模式。 在w e b 日志挖掘的模式发现中，用户的访问模式主要分为：( 1 ) 用户的访问 模式序列；( 2 ) 用户所访问页面之间的关联规则。前者反映的是用户总的迁移序 列，着重于序列的发现：后者反映的是群体用户所访闯的页面之闯的关联度， 着重于独立页面之间的关联。了解用户在w e b 环境中的访问模式不仅有助于改 善站点的设计，如在高度相关的页面之问提供有效的访问，改进页面上的链接 设计，而且能够改进市场决策，如将广告放在合适的页面，改善客户用户的分 类和行为。 w e b 日志挖掘在使用挖掘算法之前要执行一系列数据预处理过程，包括： 数据净化、用户识别、会话识别和事务分割。其中，用户事务模式识别主要有 三种：引用长度法( r e f e r e n c ek n g t h ) m 】，最大向前引用法( m a x i m a lf o r w a r d r e f e r e n c e ) t 4 1 1 和时间窗法( t i m ew i n d o w ) t 4 2 1 。对于以上两种用户访问模式的挖掘， 目的不同，所基于的挖掘对象也不同，则各自采用的用户事务模式识别方法亦 有所不同，后文将分别予以介绍。本章接下来的讨论中假设相应的预处理工作 已经完成，并着重讨论用户访问模式的挖掘。 3 2 用户频繁访问模式序列及算法改进 3 2 1 引言 对于一个网站而言，网站访问量、点击数、独立d 访问数等参数是反映这 个网站用户访问情况的重要指标。通过分析那些访问过的网页的有序数据可以 预测访问者对网站的访问行为。任何时候当一个用户连接到一个站点时，服务 西南交通大学硕士研究生学位论文第1 4 页 器就会在日志文件中记录其所有的操作，这样可以获得用户使用键盘或鼠标访 问站点时的点击流。通常鼠标的每次点击都对应着一个网页的访问，所以可以 定义点击流为访问的网页序列。一个用户会话描述了用户在登录网站后一段时 甸内访问的网页序列，经过适当的数据预处理，可以将用户会话转换成由用户 访问模式序列组成的用户访问事务集，用户频繁访问模式序列挖掘就是要找出 全部支持度( 在事务集中出现的次数) 大于等于指定阀值的访问模式序列，从而发 现用户访问网站时的频繁遍历路径，网站管理员可据此发现网站拓扑设计与用 户频繁遍历路径间的不一致，一方面调整站点结构，比如删除很少被访问的路 径，即删除页面闯的冗余链接，或者改进页面布局，引导用户沿管理员期望的 路径进行访问：另一方面，可将网站广告放置在用户频繁遍历路径上，这一点 对电子商务网站尤为适用。 对于挖掘用户频繁访问模式序列，目前已有许多算法，其中多数属于类 a p f i o r i 算法【4 “卯，其缺点是需要多次扫描数据库，而每次扫描数据库只能使发 现的频繁访问模式序列增加一个单位长度。本节将提出一种算法，f a s m i n i n g ( f r e q u e n ta c c e s ss c q u v n c e m i n i n g ，频繁访问序列挖掘) ，该算法采用最大向前 引用法( m f g ) 将用户会话划分为相应的用户访问事务，以发现和识别用户的访问 模式序列，并通过改进f p g r o w t h 算法 4 6 1 挖掘频繁访问模式序列，只需要遍历事 务数据库两次，且不用产生候选模式序列。 3 2 2f p g r o w t h 算法 f p g r o w t h 算法1 4 6 1 的主要思想是基于分治策略，即在第一次扫描数据库以 后，将产生频繁集的数据压缩到一棵频繁模式树中，又称之为f p t r e e ，用模式 树保留项集的关联信息，然后对模式树产生频繁集，即：将长的频繁集分割成 多个长度为1 的频繁项，一步一步用模式生长的方法产生较长的频繁集，避免 了大量候选项集的产生和测试过程，直接产生频繁模式。当原始数据量很大的 时候，也可结合划分的方法，使得一棵f p t r e e 能放入主存中。由f p g r o w t h 算 法的策略可以看出，此算法分为构造f t - t r c c 和构造频繁模式两个步骤。 设d 是事务集，k i l ，i 2 ，i 。 是d 中全体项组成的集合，其中i k ( k = l ，2 ，m ) 称为项，包含k 个项的项集称为k 项集。一个事务t 是一个项集，它是l 的子 集，每个事务都与一个唯一标识符t i d ( t r a n s a c t i o ni d e n t i f i e r ) 相联系。不同的 事务一起组成事务集d ，f p g r o w t h 算法即在其上进行。下面以图3 - 1 所示的事 西南交通大学硕士研究生学位论文第1 5 页 务数据库d 为例描述f p - g r 他算法的实现过程。 田di t e m s e t s t 1 0 0 a ，b ，c 删 b ，d t 3 0 0 a ，b ，c ，e t 4 0 0 b ，d ，f t 5 0 0c e 图3 - i 事务数据库d 第一步：构造f p - t r e e 。首先扫描事务数据库d 一遍，假设支持度阀值为2 ， 生成频繁1 项集l = 伯：4 ，e ：3 ，c ：2 ，d ：2 ，a ：2 ，并得到它们的支持度计数。然后，创建 f p t r e e 的根节点，用“r o o t ”表示。接下来第二遍扫描数据库d ，每个事务中的 项按照l 中的支持度计数降序处理，并对每个事务创建一个分枝。 例如，图3 1 中第一个事务t 1 0 0 构成f p t r e e 的第一个分枝 ，如图3 2 ( a ) 。接下来处理第二个事务t 2 0 0 。事务t 2 0 0 按照l 中的次序 包含项b 和d ，它构成一个新的分枝，如图3 2 ( b ) ，由于该分枝与t 1 0 0 产生的 分枝共享前缀b ，所以将节点b 的计数加1 ，并创建新节点( d ：1 ) 。通常，在为f p t r e