（计算机软件与理论专业论文）基于web日志的频繁浏览路径挖掘技术研究.pdf

摘要 频繁浏览路径的挖掘是w e b 使用挖掘中的一个重要研究领域，它对于电子商务网站 的商业决策、改善网站建设等都有现实的指导意义。通过对大量文献的研究，本文提出 了两种基于w e b 日志的频繁路径的挖掘算法。 一、提出了一种新的基于w e b 日志的挖掘用户浏览偏爱路径的方法。首先，综合考 虑影响用户浏览兴趣的w e b 日志中的浏览次数、浏览时间和浏览接收字节数等因素，采 f 用算术法求解兴趣度；其次以浏览兴趣度为基本元素，以“三矩阵 为数据结构实现挖 掘算法，这种“三矩阵的数据结构避免了多次频繁浏览数据库，提高了算法的效率。 以存储矩阵为基础建立会话矩阵和路径矩阵后，再在会话矩阵上采用两个页面向量夹角 余弦作为相似用户的页面距离公式进行页面聚类，求得相似用户的相关页面集。本文采 用的计算页面距离的公式，解决了h u m m i n g 距离的不足之处，全面考虑了w e b 日志中多种 因素对页面距离产生的影响，得到的相关页面集更精确，相似度更高，进而提高了算法 的准确性；最后利用路径选择偏爱度在相似用户的路径矩阵上挖掘出相似用户的浏览偏 爱路径。 二、提出了一种基于w e b 日志的用户连续频繁路径的挖掘算法。采用多元线性回归 的方式实现了兴趣度的线性求解；其次将浏览兴趣度作为一个属性，根据不同需求生成 三种w e b 浏览树，此浏览树不仅解决了连续可回溯路径的描述问题，而且可以全面反映用 户浏览情况，使结果更全面，更实用；以三种浏览树为前提，生成倒序单子树序列，在 经过整合倒序单子树后的r t 树上挖掘出频繁浏览路径。 本文提出的两种算法不仅在页面浏览兴趣度的求解方法上提出了创新性的改进，而 且提升了频繁路径的精准性和合理性。实验证明算法结果更真实，更全面。 关键字：w e b 日志；浏览兴趣度；页面聚类；多元线性回归；频繁浏览路径。 a b s t r a c t t h er e s e a r c ho nf r e q u e n tb r o w s i n gp a t h sm i n i n gb a s e do nw e bl o g s i s a n i m p o r t a n tr e s e a r c hi nw e bu s a g em i n i n g ，a n di th a sa g r e a tg u i d a b l es i g n i f i c a n c e t ot h eb u s i n e s sd e c i s i o n so fe l e c t r o n i cc o m m e r c ew e b s i t e sa n dt h ei m p r o v e m e n t o fw e b s i t ec o n s t r u c t i o n t h i sp a p e rp r o p o s e st w oa l g o r i t h m so ff r e q u e n tp a t h s m i n i n gb a s e do nw e bl o g st h r o u g ht h es t u d yo fal a r g en u m b e ro f 1i t e r a t u r e f i r s to fa l l ，t h i sa r t i c l ep r o p o s e san e wa p p r o a c h o fm i n i n gu s e r s p r e f e r r e db r o w s i n gp a t h sb a s e do nw e bl o g s f i r s t ，c o u n t s o u tt h eb r o w s i n g i n t e r e s tb yc o n s i d e r i n gt h eb r o w s i n gc o u n t ，t i m e ，b y t e sr e c e i v e da n d s u c h f a c t o r si nw e bl o g st h a te f f e c t su s e r s b r o w s i n gi n t e r e s t ：t h e n ，r e a l iz e st h e m i n i n ga l g o r i t h mw i t h t h et h r e e m a t r i xd a t as t r u c t u r eb yt a k i n gb r o w s i n g i n t e r e s ta st h ef u n d a m e n t a le l e m e n t ，t h i st h r e e m a t r i xd a t as t r u c t u r ea v o i d s b r o w s i n gd a t a b a s ef r e q u e n t l ya n ds a v e st h et i m eo fa l g o r i t h m ，e s t a b l i s h e st h e s e s s i o nm a t r i xa n dt r a c em a t r i xo nt h ef o u n d a t i o no fs t o r a g em a t r i x ，t h e nc a r r i e s o np a g ec l u s t e r i n gi nt h es e s s i o nm a t r i xt h r o u g hu s i n ga n g l ec o s i n ei nv e c t o r s p a c eb e t w e e nt w op a g e s ，w h i c h isc a l l e dt h esi m i l a ru s e r sp a g ed is t a n c e f o r 叫l a ，a n dw ec a ng e tt h es i m i l a ru s e r sr e l a t i v ep a g e ss e t ，t h i sp a g e s 7 d i s t a n c ef o r m u l as o l v e s t h e d e f i c i e n c i e so fh u m m i n gd i s t a n c e，t a k e s f u l l c o n s i d e r a t i o no fe f f e c t so np a g e sd i s t a n c et h a t a r ec a u s e db yv a r i o u sf a c t o r s i nw e bl o g s ，t h eo b t a i n e dr e l a t e dp a g e ss e ti sm o r ea c c u r a t ea n ds l m l l a r ，a n d i ti m p r o v e st h ea c c u r a c yo ft h ea l g o r i t h m ，f i n a l l ym i n e st h es i m i l a ru s e r s b r o w s i n gp r e f e r r e dp a t h sb yu s i n gp a t hc h o i c e p r e f e r e n c e i ns i m i l a ru s e r s t r a c em a t r i x s e c o n d t h i sa r t i c l ep r o p o s e sa na l g o r i t h mo fm i n i n gc o n t i n u o u sf r e q u e n t p a t h sb a s e do nw e bl o g s f i r s t ，s o l v e st h eb r o w s i n gi n t e r e s tb yu s i n gt h em o r e c o n v i n c i n gm u l t i - d i m e n s i o n a ll i n e a rr e g r e s s i o n ：s e c o n d ，g e n e r a t e st h r e ek i n d s o fw e bb r o w s i n gt r e e sa c c o r d i n gt ot h ed i f f e r e n td e m a n d sb yt a k i n gt h eb r o w s i n g i n t e r e s ta sap r o p e r t y ，t h i sb r o w s i n gt r e es o l v e st h ed e s c r i p t i o nq u e s t i o no f t h ec o n t i n u o u s ，r e v i e w i n gp a t h s ，m o r e o v e r ，r e f l e c t st h eu s e r s b r o w s i n gs t a t u s ， t h er e s u l ti sm o r ec o m p r e h e n s i v ea n dp r a c t i c a li ，t h i r d ，m i n e st h ef r e q u e n t b r o w s i n gp a t h sb a s e do nt h er tt r e e ，w h i c hi sr e s u l t e df r o mt h er e a r r a n g e m e n t a n dm e r g i n go ft h es u b t r e e t h i sa l g o r i t h mn o to n l ym a k e sa ni n n o v a t i r ei m p r o v e m e n to nc o u n t i n gm e t h o d o fp a g e sb r o w s i n gi n t e r e s t ，b u ta l s op r o m o t e st h ea c c u r a c ya n dr a t i o n a li t y i i o ft h e o b t a i n e df r e q u e n tb r o w s i n gp a t h s r e f l e c t st h eu s e rs i n t e r e s t si nw e b m o r er e a la n dm o r ec o m p r e h e n siv e t h ee x p e r i m e n t sp r o v et h a tt h ea l g o r it h m l o g sf r o mab r o a d e rv i e w ，t h er e s u l ti s k e yw o r d s ：w e bl o g ：b r o w s i n gi n t e r e s t ：p a g ec l u s t e r ：m u l t i v a r i a t i o nl i n e a r r e g r e s s i v e ；f r e q u e n tb r o w s i n gp a t h s i i i 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特 别加以标注和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其 他同志的研究成果对本人的启示和所提供的帮助，均已在论文中做了明确的声明并表示 谢意。 学位论文作者签名 每垒 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名：兰要垄二指导教师签名：学位论文作者签名：2 立2 二指导教师签名： 签名日期： 年月 日 基于w e b 日志的频繁浏览路径挖掘技术研究 第一章绪论 1 1 选题背景 随着w w w ( w o r l dw i d ew e b ) 技术的纵深发展，i n t e r n e t 正在前所未有地影响并改变 着我们地生活。由于i n t e r n e t 上存贮了许多复杂的数据，大量的非结构化的信息无法使 用现有的数据库管理系统来操作。首先，用户群体表现出多样性的特点，全球信息网大 约有数亿个工作站，其用户具有不同的背景、不同的兴趣和目的；其次，i n t e r n e t 本身 非结构化、动态性、不完全性的特点，体现了巨大的、分层的、多维的方式支持用户有 效地发现和利用全球信息网络上的资源，对信息系统的研究者提出了新的挑战。而解决 这方面需求的一个有力工具就是w e b 使用挖掘，即改进和创新原有的数据挖掘的原理和 思想，并加强对w e b 日志信息的挖掘，从而发现有用的知识和信息。w e b 日志挖掘就是在 这样的市场需求下出现的。 w e bl o g s 是w e b 数据挖掘的重要数据来源，它记录了用户访问站点的数据，经过适当 的数据预处理，可以将w e bl o g s 中的数据转换成由用户访问路径组成的w e b 访问事务。 w e b 频繁访问路径挖掘就是要找出浏览页面兴趣度大于等于某一用户指定阈值的访问 路径，从而发现用户访问模式，而发现用户访问模式对于网站的商业决策具有十分重要 的指导意义。 1 2 本课题的研究现状 此课题的研究1 2 1 在国外起步比较早，成熟的系统有：( 1 ) w e bm i n e r 系统。该系 统的主要功能是通过处理w e b 日志，把数据转换成传统的关联规则发现算法能够处理 的事务数据形式，然后利用传统算法自动提取出w e b 日志中的关联规则和序列模式等。 ( 2 ) 分析工具s p e e d t r a c e 。它的目标是基于用户会话，挖掘出经常被访问的频繁浏览 路径和页面组；( 3 ) c a r d 算法。算法主要用于处理用户会话聚类中典型的噪音数据， 并可用于非欧几里得的关系数据的聚类。 相对于国外，国内的w e b 数据挖掘研究发展较晚n 小1 3 3 。原因主要是国内对互联网业 发展认识和意识较晚，2 0 世纪末期，国内互联网用户达到一定规模后，国内在w e b 使用 挖掘才有了全新的尝试和探索，其中比较成熟的有：( 1 ) 周斌等在我国w e b 研究初期基于 e - o e m 模型尝试着进行了关联规则挖掘；( 2 ) 陈宁结合国外应用数据挖掘技术解决 i n t e r n e t 应用问题；( 3 ) j u d y ( 台湾) 等人通过问卷调查，提出了t a m 模型，为评价网 站的质量提供重要依据；( 4 ) w e b - i a m ( 网站智能分析系统) ( 5 ) s w l m s 以及日志挖掘实 验系统等。 w e b 频繁访问路径挖掘具有重要的意义，挖掘出来的访问路径可以用于提供个性化 服务，改善网站的组织结构等。可采用通用的序列模式挖掘算法挖掘连续频繁访问路径， 如经典的a p r i o r i ( p a r t i t i o na l g o r i t h m ) 类算法、g s p ( g e n e r a li z e ds e q u e n t i a l p a t t e r n s ) 算法、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 l e s s ) 基于w e b 日志的频繁浏览路径挖掘技术研究 算法、最大向前路径法、引用长度法、拓扑结构法、类a p r i o r i 算法、f p f m a 算法、j i a n p e i 和j i a w e ih a n 提出了基于访问路径树的w a p 算法、c a p 算法、o b - m i n e 算法等等。本文 会在以后的章节中重点对几个算法进行讨论和比较。 1 3 本文的研究内容 本文主要研究基于w e b 日志的浏览路径的挖掘算法h 引。目前大部分的挖掘算法主要围 绕以下几个问题展开讨论：1 、算法基本处理元素问题。即采用何值作为算法的最基础 分析依据? 有些算法利用浏览次数作为主要研究对象，这样求得的浏览路径不全面；有 些算法虽考虑到了浏览时间、浏览次数及浏览内容的长度等因素，并采用页面浏览兴趣 度作为算法的基本元素，但兴趣度的定义比较模糊，不能准确反映用户对网页感兴趣程 度；2 、存储结构问题。即采用何种存储结构表示w e b 日志数据库文件? 使用该种存储结 构后访问数据库时间效率如何? 3 、挖掘后的路径是否精准，是否能反映用户的兴趣所 在? 围绕上面的问题，本文将主要解决兴趣度的求解及基于浏览路径的存储结构的浏览 路径的挖掘。本文提出了两种基于w e b 日志的频繁浏览路径的挖掘算法。 首先，本文提出了一种改进的用户浏览偏爱路径的挖掘方法。较之以往算法充分考 虑影响用户浏览兴趣的浏览时间，浏览次数，浏览速度等因素，采用一种新的兴趣度公 式求得兴趣度，采用“三矩阵 方式存储浏览路径。在有效性和准确性方面，具有一定 优越性，能准确、充分地表现不同用户群体在浏览路径上的偏爱倾向。 其次，本文提出了一种新的频繁路径的挖掘算法。该算法提出了用线性回归方式求 解兴趣度，根据不同需求可生成三种不同浏览树，不但解决了连续，可重复的路径的描 述问题，也从不同视角反映w e b 日志中的用户兴趣、真实、全面。 最后，针对当今的基于w e b 日志的挖掘浏览路径的算法进行总结，指出一些尚待解 决的问题并提出进一步的工作。 1 4 本文的结构框架 本文由五章组成，主要论述了w e b 使用挖掘中的一个重要分支一基于w e b 日志的频 繁路径的挖掘算法。从w e b 日志挖掘的原理，方法到频繁路径的挖掘算法，本文给出了 详细地说明和阐述。各个章节结构安排如下： 第一章绪论。本章论述了频繁路径挖掘的研究背景、意义；总结了国内外在该领 域的研究进展和研究现状；并给出了本文的研究内容和结构框架。 第二章w e b 日志挖掘的相关理论。本章描述了w e b 数据挖掘的基本定义、分类、 相关定理及性质，为本文的算法提供理论依据。 第三章一种新的基于w e b 日志的挖掘用户浏览偏爱路径的方法。本章提出的算法 是一种改进的偏爱路径的挖掘算法。该算法主要用算术法求解兴趣度，采用矩阵的存储 2 基于w e b 日志的频繁浏览路径挖掘技术研究 结构实现算法。本章介绍了算法的相关定义、算法的思想、具体实现步骤、示例分析， 并讨论了实验结果。 第四章基于w e b 日志的连续频繁浏览路径挖掘算法。本章深入地给出了一种新的 频繁路径的挖掘算法，算法给出了全新的用户浏览兴趣度的定义，并采用树的存储结构 进行分析研究。本章从算法思想、算法步骤，示例分析及实验结果全面地阐述了算法。 第五章总结与展望。本章对整个论文的主要工作和成果进行了总结，并对下一步 的工作和研究进行了展望。 1 5 本章小结 本章描述了本文的选题背景，本课题的研究现状，并简明地阐述了本文的研究内容 及结构框架。本章不仅在文章结构上做了合理的安排，而且在内容上为下文的展开分析 奠定了基础。 3 第二章w e b 挖掘的相关理论 2i 数据挖掘基础知识 随着万维网上可用信息资源的爆炸性增长，使各种信息可以以非常低的成本在网 络上获得，在如此海量的数据中发现有用的信息变得越来越困难，如何在数据集合中发 现有用信息无疑将成为人们研究的热点。本节主要介绍数据挖掘相关知识，描述数据挖 掘的产生，概念及发展趋势。 2 i i 数据挖掘的产生背景 近年来， n t e r n e t 融合了计算机、网络、通信等相关技术，正前所未有地改变着 我们的生活。网络在快捷、方便地带来大量信息的咧时，也带来了很多的问题：信息量 冗杂，信息真假难辨，网络安全性差等等。于是人们倡导要学会“抛弃”，即丢掉一 些繁冗的信息，解决数据过度膨胀而资源相对匮乏的问题，于是引发了数据挖掘领域 的出现1 。 2i 2 数据挖掘概念 目前为止，学术界并没有给数据挖掘下一个统一的定义。但数据挖掘“”1 ( d a t a m i n i n g ) 就是对海量的信息进行选择、处理和建模的过程，目的是发现隐藏在其中的有 可利用价值的模式和知识。数据挖掘如图2 一i 所示。 图2 一l 数据挖掘示意圄 m d * 高坤 从上世纪9 0 年代初到现在，数据挖掘技术融合了计算机的理论与应用以及数学知 识，迅猛地发展起来，应用也已渗入各个领域。 22w e b 挖掘概述 由于每天都有无数的用户访问t n t e r n e t ，因此，网上积累了大量无用和可用的数 据，w e b 无疑已经成为人们获取信息的重要下段。由于w e b 上的信息瞬息万变，再加上 脚 ，一， 。 岛 基于w e b 日志的频繁浏览路径挖掘技术研究 不断增多的用户数量，i n t e r n e t 上的资源急剧增多，连页面关系结构变化也是相当频繁 的。使信息的质量渐渐成为人们关注的焦点。用户在网站上的行为反映了他们不同的喜 好，假使对用户的行为加以充分地分析，就有可能发现一些潜在的规则。深刻研究用户 在网站上的访问模式和偏好对掌握和运用目前日益变化的w e b 技术是不无裨益的，它将 有助于优化网站的结构、方便用户等。于是w e b 挖掘开始出现并初露锋芒。 2 2 1w e b 挖掘的概念 w e b 挖掘指在人为构造的w w w 上挖掘潜在的、有用的模式及隐藏的信息的过程。即 w e b 数据挖掘是指从文档结构和使用的集合中发现隐式的模式1 。 1 9 9 6 年o r e n e t z i o n i n 2 1 第一个给出了“w e b 挖掘”的概念。他认为w e b 挖掘融合了 w e b 知识和数据挖掘，能自动从w e b 资源中提取有用的网络信息。“因特网的数据挖掘 、 “w e b 知识发现”、“网络信息挖掘 “w e b 信息挖掘”都可认为是w e b 挖掘的同义词。 2 2 2w e b 挖掘的分类 w e b 挖掘分为w e b 内容挖掘、w e b 结构挖掘、w e b 使用挖掘。w e b 挖掘的分类如图2 - 2 所示。 w e b 挖掘 w e b 内容挖掘 文本 挖掘 多媒体 挖掘 w e b 结构挖掘 超链接 挖掘 页面结 构挖掘 w e b 使用挖掘 甩户访 问模式 挖掘 分析定 s j j w e b 站点 图2 2w e b 挖掘分类图 1 、w e b 内容挖掘 w e b 内容挖掘n 别是指从文字、多媒体等各种形式的网络内容中发现用户可用的信 息，从而提高w e b 上数据的占有和应用效率。文本分类的算法有很多种，比较常用的有 t fd f 和n a i v eb a y e s ( 朴素贝叶斯) 等方法，k - n n ( k 一最近邻接分类算法) ，f o i l 方法。 2 、w e b 结构挖掘 w e b 内容挖掘研究的是文档的内容，而w e b 结构挖掘n 2 1 3 研究的是w e b 的链接结构。 简言之，w e b 结构挖掘是从人为的链接结构中获取有价值的信息的过程。 w e b 结构挖掘主要有超链接挖掘、页面结构挖掘两种形式。w e b 结构挖掘的算法很多， 其中最经典的算法有p a g e r a n k 、h i t s 算法以及h i t s 改进算法，还有其他改进或类似的算 5 基于w e b 日志的频繁浏览路径挖掘技术研究 法s a l s a 、p s a l s a 、p h i t s 等。这些算法的核心都集中在计算w e b 页面与页面之间的相关 性上；再者，可以为研究网站之间的通信和网站之间的联系提供重要依据，为深层挖掘 奠定基础。 3 、w e b 使用挖掘 w e b 使用挖掘n 2 儿珏3 是应用数据挖掘技术和方法从w e b 使用数据或w e b 日志中发现w e b 使用模式的过程。w e b 使用挖掘的对象主要是用户访问w e b 时留下的访问记录及隐藏在行 为背后的更深层的动因和规律。w e b 使用挖掘是指通过分析w e b 服务器日志( 1 0 9 ) 来获取 可用信息的过程，w e b 使用挖掘有十分重要的现实意义：( 1 ) 在l o g s 中挖掘出的用户的浏 览模式将用于管理、建设网站和调整网站组织模式；( 2 ) 可以服务于企业。浏览规则的 抽取给企业提供有价值的信息，为企业寻找新的商机，发现目标客户等。 图2 - 3 描述了w e b 使用挖掘流程。本文的研究内容即为w e b 使用挖掘的一个重要分支， 属于流程中的第二过程。 图2 - 3 w e b 使用挖掘流程示意图 由图2 - 3 我们可以看出，w e b 使用挖掘的主要研究对象是w e b 日志，下面我们主要讨 论一下w e b 服务器及相应的日志格式。 目前最常用的w e b 服务器有a p a c h e 、n e t s c a p ee n t e r p r i s es e r v e r 、m si i s 等。而 现在互联网上最常用的w e b 服务器就是a p a c h e ，对于a p a c h e 来说，支持多种日志文件格 式，最常见的是c o m m o n 和c o m b i n e d 两种模式，其中c o m b i n e d 方式l t c o m m o n 方式的同志的 信息要多。各种w e b 服务器会产生三种类型日志文件：s e r v e rl o g s ，e r r o rl o g s ，c o o k i e l o g s 。这三种日志文件的格式和内容大致相同。根据w 3 c 的标准，一般w e b 日志都包括诸 如用户的i p 地址、请求时间、方法( g e t p o s t 等) 、被请求网页或文件的u r l 、发送接 收字节数、协议版本等信息。表2 1 给出了以c o m b i n e d 类型的w e b 日志格式n 引。 表2 1w e b 服务器日志格式 域( f i e l d )i 描述( d e s c r i p t i o n ) 日期( d a t e )i 请求页面的时间、日期和时区 6 f 程 过 二 一 第 一 程 | i 过 一 第 - 法算掘挖 理别别充清识识补据户话径数用会路 基于w e b 日志的频繁浏览路径挖掘技术研究 客户端( c l i e n ti p )远程主机的i p 或d n s 入口 用户名( u s e rn a m e )远程登录的用户名 字节( b y t e s )发送和接收的字节 服务器( s e r v e r )服务器名称、i p 地址和端口 请求( r e q u e s t )u r l 查询和枝节 状态( s t a t u s )返回给h t t p 状态标识 服务名( s e r v i c en a m e ) 用户请求的服务名称 耗用时间( t i m et a k e n ) 完成浏览的时间 协议版本( p r o t o c o lv e r s io n ) 传输用的协议版本 用户代理( u s e ra g e n t ) 服务提供者 c o o k i e标识号 参照页( r e f e r e e r )本页的上一页 通过w e b h 艮务器日志格式，我们可以看至l j w e b 访问日志记录了服务器接收请求以及运 行状态的各种原始信息，包括客户端的i p 地址、浏览网页的时间、访问请求的页面、w e b 服务器对于该请求返回的状态信息、返回给客户端的内容的大小( 以字节为单位) 、上 次访问页面、c o o k i e s 等我们迫切需要的信息。如果客户端在连续的网站上浏览，就会 产生很多条包含某些相同信息的日志文件，这样就构成了一个访问在网站上所有活动的 日志信息列。通过这些信息，我们就可以通过一定的算法对日志文件进行挖掘，从而就 会发现用户的访问模式、相似用户群体、频繁路径等有价值的知识。 2 3 本章小结 本章简单介绍了数据挖掘的相关知识，概括了w e b 挖掘的概念、分类等基础知识。 这些知识为本文的挖掘算法提供了充分的理论依据。下文中的频繁路径的挖掘算法是 w e b 使用挖掘的重要分支，主要的研究对象是w e b 日志。从第三章开始，本文将基于表2 1 格式的w e b 日志，重点研究与分析频繁浏览路径的挖掘算法。 7 基于w e b 日志的频繁浏览路径挖掘技术研究 第三章一种新的基于w e b 日志的挖掘用户浏览偏爱路径的算法 3 1 引言 随着w e b 挖掘技术的不断发展，基于w e b 日志的浏览路径的研究也越来越引起学者 与专家的重视。本节将介绍几种浏览偏爱路径的挖掘算法，分析其优缺点，并提出本章 算法的改进之处。 3 1 1 浏览偏爱路径挖掘算法比较与分析 目前基于w e b 日志的分析浏览路径的方法很多，虽然取得了一定的成果，但还有不 少值得研究探讨的问题。 首先，本章将分析与比较以往的算法儿例：文献 1 6 中提出了偏爱度的概念，指出 用户对页面的浏览兴趣完全由用户的访问次数n 力n 胡决定，该算法着重强调了访问次数在 挖掘用户浏览偏爱度算法中的作用，但忽略了访问时间和访问页面速度对用户浏览偏爱 度的影响。文献 1 9 采用矩阵作为存储结构存储w e b 日志记录，解决了存储连接、回溯 的路径问题，但仅用页面访问次数作为算法分析度量值，与文献 1 6 类似，即算法的最 基本元素不能全面反映用户的真实的浏览兴趣；另外文献 1 9 3 中采用h u m m i n g 距离公式 进行页面聚类，判断每两个页面是否相似，由此得到的偏爱路径不具有说服力，不够准 确。文献 2 0 中用树存储结构存储w e b 日志中的网页访问情况，即对每一条浏览路径都 会从树的根结点开始依次向下生成一棵子树，一个结点对应一个浏览页面。该算法可以 反映一般浏览路径，但对有回溯的浏览路径不能准确地描述。比如浏览路径a - - b - - a - - b a ，因此存在片面性等，还有部分文献没有独立的存储结构，在算法分析和计算时需 频繁访问w e b 日志数据库文件，这势必会加重i 0 负担，降低算法效率m 1 。 3 1 2 本章算法改进之处 针对上述问题，本文做出了如下改进h 6 】 4 钥： l 、提出存储矩阵的概念，该矩阵采用单元数组作为存储结构，仅存储算法必需的 日志项，去掉了大量冗余的w e b 日志信息，并用浏览兴趣度作为该存储矩阵的一列元素， 直观、真实地记录了用户对网页的感兴趣情况。存储矩阵的建立首先使得日志数据可视 化，并且整个算法只需访问一次数据库，避免了在建立会话矩阵和路径矩阵时再度频繁 访问数据库，提高了算法效率，节省了算法的时间。存储矩阵是建立会话矩阵和路径矩 阵的数据依据。 2 、本章算法给出的由平均用户兴趣度值作为卜项浏览偏爱页面集的判定条件，比 总浏览次数作为判断条件更精确。平均兴趣度值记录的是总体水平，具有一般性，而总 浏览次数容易产生极端情况。 3 、本章算法改进了以h u m m i n g 距离求页面距离的聚类方法，提出一种新的相似用 户的页面聚类方法，以用户浏览兴趣度为基本处理元素，采用页面向量夹角余弦的页面 8 基于w e b 日志的频繁浏览路径挖掘技术研究 距离公式作为相似用户的页面距离的公式，经实验证明该页面距离公式得到酌相关页面 集更精确，相似度更高。由此得到的浏览偏爱路径更具真实性，更能说明相似用户在网 页浏览上的真正喜好。 3 2 基于w e b 日志的挖掘用户浏览偏爱路径的算法描述 3 2 1 相关定义 1 、页面浏览兴趣度h 印h 7 1 本章中挖掘浏览频繁路径的最基本元素是页面浏览兴趣度。兴趣是指个人对客观事 物的选择性态度，准确地度量用户浏览兴趣是w e b 日志挖掘的基础。所谓页面浏览兴趣 度即个人对网页的感兴趣程度。通过对用户的浏览行为进行分析，就可以推断出该用户 在某一段时间内的浏览兴趣。具体说，用户对正在浏览的网页是否感兴趣，可以通过w e b 日志中的浏览时间，浏览次数，浏览速度反映出来。浏览次数越多，说明用户对页面越 感兴趣；浏览时间越长，说明用户对页面感兴趣，但浏览时间又与浏览速度有关。 文献 2 0 将会话中两个连续访问页面之间的时间差定义为“持续时间作为描述 用户兴趣的属性，但是持续时间与网络的传输速度有直接的关系，不能准确表示用户的 兴趣，并且最后一个页面的持续时间无法得到；文献 2 1 综合考虑浏览频度时间和页面 长度作为描述用户兴趣的属性，但是页面长度信息在w e b 日志文件中没有相应的字段记 录，页面长度无从获取；文献 2 2 选择两个在日志文件中记录的字段信息和统计得到的 信息计算页面兴趣度，两个字段信息分别为所花时间和发送字节数，需要统计的信息是 页面的浏览频度，该方法采用的是实际日志数据，虽然日志数据能体现用户的真实信息， 但所包含的信息有限，屏蔽了用户的背景信息。文献 2 3 选取用户浏览页面的次数和 访问时间作为描述用户兴趣的属性，但是用户访问页面所用的时间是与页面自身的长度 相关的，单纯考虑访问时间不能反映用户的浏览兴趣。 本章h 6 4 7 1 中提出用算术法求解兴趣度的方法，使其基于w e b 日志真正全面反映用户 的浏览兴趣。 约定p ，表示用户在页面j 上的浏览兴趣度；c o u n t u 表示用户从页面i 进入页面j 的浏览次数；t i m e “表示用户从页面i 进入页面j 的浏览时间( 单位：秒) ；3 b s “表示从 页面i 进入页面j 所接收到的字节数( 单位：m b ) 。则用户的浏览兴趣度公式为： 弓1 1 ( c o u n t i j + t i m e l j ) s b s i j 。 由w e b 日志，我们可以看出用户浏览网页时对某一页面感兴趣程度由页面的浏览时 间，浏览次数以及网速等几方面的因素决定。定义中的浏览时间在w e b 日志中指页面的 耗用时间，页面的浏览时间越长说明用户对该页面越感兴趣，而浏览时间又与浏览速度 有关，页面的浏览速度在w e b 日志中则指页面的接收字节数( 见表2 1 ) 。速度越快，接 收字节数越多。因此我们给出上述定义，它能全面地反应出用户对页面的关注程度。 用户浏览兴趣度是本文实现算法中最基本的细胞元素，算法中无论是建立矩阵模型 9 基于w e b 日志的频繁浏览路径挖掘技术研究 还是算法挖掘都以用户浏览兴趣度为基准展开分析和计算。 2 、“三矩阵模型 删h 力 所谓“三矩阵 即本章算法中依次要生成的和赖以生存的三个矩阵。它们分别称为 存储矩阵、会话矩阵和路径矩阵。 1 ) 存储矩阵( 记作m e m ) 。 存储矩阵是一个n * 4 的单元数组。其存储的是经计算与整理过后的可用的w e b 日志 记录。矩阵共四列；分别代表当前页面、用户，兴趣度与当前页面的引用页。存储形式 如下： 旷臣u r l i tu s e r lb u s e r 2e 2 u s e r n 只 p r e u r l l p r e u r l 2 p r e u r l 月 其中：矩阵维数r l 并不是数据库文件中记录总个数，而是整理合并后的记录总个数， u r l 表示当前访问页；u s e r 表示访问用户；p 表示页面浏览兴趣度；p r e u r l 表示引用页。 存储矩阵的建立简化了w e b 日志内容，去掉了冗余的w e b 日志记录，直观、明了地 反映出算法所用的信息。m e m 是整个算法的数据基础。存储矩阵的正确与否直接影响会 话矩阵与路径矩阵的准确性。 2 ) 会话矩阵( 记作s m ) 会话矩阵n 卅是以u r l 为行，u s e r 为列，页面浏览兴趣度p 为其基本元素值的矩阵， 会话矩阵形式如下： 卜i s m 舻l ； ；l l s 。s 。i 3 ) 路径矩阵( 记作t r m ) 路径矩阵n 刚是以p r e u r l 为行，u r l 为列，页面浏览兴趣度p 为基本元素值的矩阵。 路径矩阵的形式如下： t r m 。f t o o t 0 1 t l ot l l t m ot m l 该矩阵有以下特点 ( 1 ) 矩阵的对角元素值为0 ( 网页个体不可作为自身的引用页) 。 ( 2 ) 矩阵2 行值总和等于2 列值总和荟f 故5 荟f 麟 o _ k f r e n u m ； 行号- - - t a g ： t a g 放置频繁页面集对应矩阵位置 s m ( 1 。：) 一m a t r i x ； ) 在m a t r i x 中计算页面距离p d ，并由页面距离，进一步筛选得到相似用户的相关 页面集合。 f o ri = l ：mm 是m a t r i x 的总行数 第i 行向量x - * u s e r s e t l ； u s e r s e t l 是参与计算的第一个页面 取出i 在t a g 中的位置； f o rj = i + l ：m 第j 个行向量y - - u s e r s e t 2 ； u s e r s e t 2 是用于计算第二个页面 取出j 在t a g 中的位置； 求出p d ： i fp d = 2 p a g e t m p a g e ； 1 3 基于# e b 日志的频繁浏览路径挖掘技术研究 在t m p p a g e 中去掉重复项，结果- + s i m p a g e s ； s i m p a g e s 为所求。 2 一项浏览偏爱子路径集生成算法c o n p a t h 20 是发现偏爱路径的关键算法，旨在利用 相似用户页面集对应的路径矩阵，先找出2 一项浏览偏爱子路径。然后通过2 一项浏览偏 爱子路径，合并生成所有的偏爱路径集。只有找到正确的2 一项偏爱子路径，才能生成准 确的多项偏爱路径集。 算法2 ：2 一项浏览偏爱子路径集生成算法m 儿4 7 1 算法名称：c o n p a t h 20 2 - 项浏览偏爱子路径集生成算法 输入：相似用户的相关页面矩阵集f r e m a t r i x s ，相关页面在存储矩阵中的存储位置 t a g s e t s ，路径选择偏爱度阈值p i 输出：2 一项浏览偏爱子路径集合p r e p a t h 2 s e t s 算法描述： p r e p a t h 2 s e t s 置空； 分别统计每个相关页面集的2 一项浏览偏爱子路径集。 f o rk = l ：p r e p a t h 2 s e t s 长度 每组相关页面对应的矩阵- * m a t r i x ； 相关页面在存储矩阵中的存储位置一t a g ； f o ri = l ：mm 是m a t r i x 的行数 f o rj = l ：ni n 是m a t r i x 的列数 判断每个非零元素对应的路径是否是偏爱路径 计算每个非零元素的路径选择偏爱度p c ； 将满足条件的路径 加入到p r e p a t h 2 中。 i fp c = p i 根据t a g 的值，将 对应的浏览路径放入p r e p a t h 2 中。 - * p r e p a t h 2 ； p r e p a t h 2 s e t s 为所求的2 一项浏览偏爱子路径集合。 p r e p a t h 2 一p r e p a t h 2 s e t s ； 1 4 基于w e b 日志的频繁浏览路径挖掘技术研究 3 2 4 示例分析 本节m 4 7 1 以部分w e b 日志为例，给出实验过程和结果。 1 ) 设由一个网站的w e b 日志经过预处理后形成如下的存储矩阵m e m ：( 部分) a u r 【8 3 】 c u 1 【3 2 】 e u 1 【4 】 f u 1 【2 8 】 e u r 1 4 2 】 c u 2 【3 7 1 1 d u 2 【2 5 2 】 2 ) 建立会话矩阵鳓和路径矩阵t r m a 由m e m 建立的会话矩阵s m ： b 由m e m 建立的路径矩阵t r m ： 01 5 4 3 0o 1 8 0o o0 1 4 00 1 4 60 3 3 90 1 0 4 3 5 4 9 0 1 7 5 0 o 1 1 0 7 3 ) 通过c l u s p a g e s 算法统计出相似用户的相关页面集f r e p a g e s 。 计算各页面的平均兴趣度，a ：1 7 1 ，b