（模式识别与智能系统专业论文）用户浏览模式与页面推荐的研究.pdf

硬士论文用户翊览模式与页面推荐的研究 摘要 用户浏览模式与页面推荐是w e b 日志挖掘领域的一个研究热点。随着i n t e m e t 应用的越来越广泛，i n t e m e t 上的数据量也越来越大，人们迫切需要从这些用户测览 网站留下的记录中得出需要的“感兴趣”的信息。页面推荐是指在用户浏览模式的基 础上，将用户频繁浏览的链接尽量的放置首页，或者有针对性的修改从首页至频繁页 面的链接关系。 本文论述了用户浏览模式和页面推荐的内涵，详细介绍了w e b 日志挖掘的算法； 同时介绍了蚁群算法的产生，原理，并以t s p 问题为例详细分析了蚁群算法的流程 以及时间和空间复杂度。 本文在分析蚁群算法框架的基础上，分析了蚁群算法应用于w e b 日志挖掘的可 行性，设计了基本蚁群挖掘算法。同时，通过分析信息素扩散的更新策略在t s p 问 题中的使用特点，进而将信息素扩散的更新策略引入到w e b 日志挖掘中，并设计了 基于信息素扩散的改进蚁群挖掘算法。 在分析蚁群算法和w e b 日志挖掘的基础上，本文设计实现了完整的w 曲日志挖 掘系统，包括日志预处理，挖掘算法和挖掘结果等。在挖掘算法中，设计了两种蚁群 挖掘算法：基于基本蚁群算法和基于改进的蚁群算法。最后设计试验进行了蚁群挖掘 算法中参数的配置，蚂蚁个体数目的确定，以及两种算法的收敛性对比试验。并在此 基础上进行用户的测览模式和页面推荐的分析。 关键词：用户浏览模式，页面推荐，蚁群算法，w e b 日志挖掘 硕士论文 用户谢览模式与夏面推荐韵研究 a b s t r a c t u s e rb r o w s i n gp a t t e r n sa n dp a g er e c o m m e n d a t i o ni so n eo ft h eh o t t e s tr e s e a r c h p o t s 。w t t ht h eu s eo fi n t e r n e t , t h ed a t ai nl u t e r n e ta r em o r ea n dm o r eh u g e p e o p l eh a v e i m m i n e n c yn e e d st of i n do u tt h e “i n t e r e s t e d ”i n f o r m a t i o nf r o mt h eu s e rb r o w s i n gl o g p a g e r e c o m m a d e n f i o n m e a n st h a tp u tt h eh i g h e s tf r e q u e n c yp a g ei nt h ei n d e xp a g eo nt h eb a s e o f u s e rb r o w s i n gp a t t e r n s ，o rm o d i f yt h el i n kb o t w e c ni n d e xp a g ea n df r e q u e n c yp a g e s t h i s p a p e ra n a l y s e s t h e m e a n i n g o f u s e l b r o w s i n gp a t t e r n s a n d p a g e r e c o n m m e n d a t i o n , i n t r o d u c e st h ea l g o r i t h m so fw e bl o gm i n i n g ，a sw e l la st h ea n tc o l o n y a l g o r i t h m s a n da n a l y s et h ef l o w , t i m ea n ds p a c ec o m p l i c a t i o nw i t ht s pp r o b l e ma s _ _ - _ 一 e x a m p l e t h i sp a p e ra l s oa n a l y s e st h ef e a s i b i l i t yt h a tu s i n ga n tc o l o n yt om i l l et h ew e b l o ga n d d e s i g n st h eb a s i ca n tc o l o n ym i n g i n ga l g o r i t h m s t h r o u g ha n a l y s et h ec h a r a c t e r i s t i co f e c t o h o r m o n ed i f f u s e n e s s 。a n di si m p o r t e ai n t ow e bl o gm j n i g a tl a s t , d e s i g nt h e a l g o r i t h m sb a s e do ne c t o h o r m o n ed i f f u s e n e s s a tl a s t , t h i sp a p e rd e s i g n sa n dc a r r i so u tt h ew h o l ew e b l o gm i n i n gs y s t e m ，i n c l u d i n g l o gp r e t r e a t m e n t ，m i n g i n ga l g o r i t h m sa n dm i n g i n gr e s u l t i nt h em i n g i n ga l g o r i t h o m ， d e s i g nt w oa n tc o l o n ym i n i n ga l g o r i t h m s ：b a s i ca n tc o l o n ya l g o r i t h m sa n da n tc o l o n y a l g o r i t h m sb a s e do i le c t o h o r r n o n ed i f f u s e n e s s a n dc o m p a r et h ep a r a m e t e r s ，a n tm l m b e r , a n dc o n v e r g e n c eo f t w oa l g o r i t h m st h r o u g hs e r i e so f e x p e r i m e n t a t i o n s k e yw o r d s ：u s e rb r o w s i n gp a t t e r n ，p a g er e c o m m e n d a t i o n ，a ca l g o r i t h m s u 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 孜d 、磊 耖习年f 月矽日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容 对于保密论文，按保密的有关规定和程序处理。 研究生签名：i 叁! ：垒凋年彳月，7 日研究生签名：! 奎! ：丝凋年彳月，7 日 硬士论文用户浏览模式与页面推荐的研究 l 绪论 1 1 研究背景 用户浏览模式与页面推荐，即从大量的w e b 日志中寻找和发现用户浏览模式的特 点。并在此之上给用户推荐最有价值的网页，以及对网站的链接结构进行有针对性的 改进。因为w e b 日志是用户赦0 览网站的记录，其中隐藏了用户的浏览特性。如何有效 的发现这些浏览模式以及利用这种浏览模式来进行页面的推荐，就导致了w e b 日志挖 掘的产生。 w e b 日志挖掘指使用数据挖掘技术在w e b 日志中发现潜在的模式或信息。焉e b 日 志挖掘研究覆盖了多个研究领域，包括数据库技术，信息获取技术，统计学，人工智 能，机器学习和神经网络等。 随着i n t e r n e t 时代的到来，大量的计算机通过互联网而连接到了一起，计算机 与计算机之间通过各种各样的方式来进行数据的共享和交换，原本独立的，封闭的原 始数据开始产生了爆炸式的增长。在i n t e r n e t 时代，企业的经营成本不断下降，管 理者需要用更低的管理成本来获得具有更高价值的决策支持，人们开始发现原始数据 熬价型2 1 。对于管理者来说，原始数据中存在着很多“令人感兴趣”的信息，但是并 没有一种相对应的技术从这些巨量甚至海量的数据中把它们提取出来。相对早期较小 数据量的数据分析方法已经从根本上无法满足现代数据分析的要求。所以，w e b 日志 挖掘技术应运而生。 w e b 日志挖掘是一个较新的研究领域，具有广阔的发展和应用前景。但是w e b 日 志挖掘技术还有许多问题需要解决，目前的几个研究方向如下： ( 1 ) w e b 日志挖掘中内在机理及新的挖掘体系和结构的研究； ( 2 ) 用户访问模式库的动态维护和更新，模式，知识的评价体系和评价方法； ( 3 ) 挖掘算法在海量数据挖掘时的适应性和时效性研究嘲； ( 4 ) 智能站点服务和性能最优化的研究； ( 5 ) 关联规则和序列模式在构造自组织站点方面的研究i 6 1 ； ( 6 ) 分类在电子商务市场智能提取中的研究【嘲。 蚁群算法 2 1 】作为一个新兴的进化算法，在近些年有了长足的发展，其使用的领域 也越来越广，从最初的解决t s p 问题( t r a v e l l i n gs a l e s m a np r o b l e m 。旅行商问题) 。 到应用于解决网络路由，机器人路径选择，生命优化等领域，表现出了强大的生命力。 硕士论文 用户浏览模式与页面推荐的研究 蚁群算法( a mc o l o n yo p t i n d z a t i o n ，a c o ) ，又称蚂蚁算法，是一种用来在图中 寻找优化路径的基于概率的技术。它由d o r i g om 于1 9 9 2 年在其博士论文中引入，来 源于蚂蚁在寻找食物过程中发现路径的行为的特点。 蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质，该 算法具有多样性，正反馈和启发式搜索的特点。多样性保证了蚂蚁个体在搜索的时候 不置走进死胡同而无限循环，正反馈机制保证了相对优良的信息能够被保存下来，启 发式搜索则保证了蚂蚁个体能够搜索其感知范围内的每条路径，并选择最好的路径， 直至搜索到目标。 t s p 作为一个著名的最优组合的问题，蚁群算法在这个领域的成果很丰富，以蚁 群算法为框架，有学者提出了很多的改进方法，如信息素扩散，最大最小值信息素， 自适应蚁群算法等。 目前，已有学者研究将蚁群算法应用到w e b 日志挖掘中，但目前的研究重点大部 分是从理论上进行分析，设计实现简单的基本蚁群挖掘算法。 1 2 本文的主要工作 本论文中，主要进行了如下的工作： ( 1 ) 分析了w e b 日志挖掘技术中现有的挖掘算法，总结了其研究成果。 ( 2 ) 详细分析了蚁群算法的特点，基本原理和解决具体问题的流程，并对基本 蚁群算法的优缺点进行了分析。 ( 3 ) 在研究蚁群算法特点的基础上，将用户浏览模式挖掘与t s p 问题进行对比， 从理论上将蚁群算法应用于用户浏览模式挖掘的可行性进行了探讨。 ( 4 ) 分析了基本蚁群算法用于用户浏览模式挖掘的不足之处，并分析了基于信 息素扩散的蚁群算法的改进方法和原理，将信息素扩散的理论引入到w e b 日志挖掘 中，证明了基于此方法的蚁群算法用于w e b 日志挖掘的可行性，设计实现了完整的挖 掘系统。 ( 5 ) 设计且实现了基于基本蚁群挖掘算法和改进的蚁群挖掘算法的试验过程， 设计试验进行蚁群算法的参数配置，蚂蚁个体数目，并设计试验从挖掘结果对比分析 了两种挖掘算法的优缺点。 1 3 本文的组织结构 本文是基于蚁群算法的w e b 日志挖掘系统的研究。全文的组织结构如下： 第一章绪论 简要介绍了w e b 日志挖掘的背景，本文的主要研究工作和组织结构 2 硕士论文用户洲览模式与页面推荐的研究 第二章w e b 数据挖掘技术 具体介绍了w e b 数据挖掘技术，其中重点介绍了w e b 日志挖掘的相关技术，包括 日志的预处理过程，挖掘算法，并简要介绍了w e b 日志挖掘的研究现状。 第三章蚁群算法 介绍了蚁群算法的产生，基本原理，算法的基本流程。并分析了蚁群算法的时间 和空间复杂度。重点分析了蚁群算法应用于w e b 日志挖掘的可行性，并基于信息素扩 散基础的蚁群算法进行了理论的分析和探讨。 第四章基于蚁群算法的用户浏览模式与页面推荐 本章主要从理论上分析了蚁群算法应用予w e b 日志挖掘的可行性，设计了以基本 蚁群挖掘算法为框架的挖掘算法。此外，以t s p 问题为借鉴，分析了基于信息索扩散 的蚁群算法，并将其引入到w e b 日志挖掘中，设计了以此为基础的改进的蚁群挖掘算 法。 第五章用户浏览模式与页面推荐系统的设计 设计并实现了基于基本蚁群挖掘算法和改进的蚁群挖掘算法的w e b 日志挖掘系 统，详细介绍了系统的架构，各个模块的基本功能，工作流程，以及算法的详细设计。 最后设计若干试验，并对试验结果进行详细分析。 结论与展望 总结了本文的主要工作，以及未来的发展方向。 硕士论文用户浏览模式与页面推荐的研究 2w e b 日志挖掘技术 w e b 日志挖掘技术是数据挖掘技术在互联网上的一个典型的应用。随着越来越多 的企业在互联网上建立企业网站，通过互联网来进行企业的整个运作，比如企业的管 理，商品的销售和用户的反馈。在这些与客户面对面的交互中，企业发现在客户浏览 商品的记录中隐藏着对产品的兴趣。 w e b 日志挖掘一般由日志提取，日志预处理，日志挖掘等部分组成，其中日志预 处理和日志挖掘是最主要的部分。 2 1w e b 挖掘简介 图2 1 日志挖掘的流程图 在i n t e m e t 时代，在网络上存在着大量的数据信息。如何对这些大量的数据信息 进行有效的分析处理就成为一个研究的热点问题。但是，w e b 数据挖掘又有与其他的 数据挖掘形式不同之处。在w e b 上的数据通常是通过“链接”而连接在一起的，例 如文本，图像，视频和声音对象之间是根据需要而链接在一起的，它们之间并没有严 格的前后关系。而且w e b 上的数据都是半结构化的，以往的数据挖掘中，通常都是对 同一类型数据库的数据进行挖掘，这也是一个不同之处。 2 2w e b 挖掘的分类 w e b 数据挖掘根据挖掘的对象不同可以分为w e b 内容挖掘( w e bc o n t e n t m a n g ) ，w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 以及w 曲使用挖掘( w e bu s a g e m i n i n 驴。其中，w e b 使用挖掘的主要资源是w e b 站点的用户访问日志，所以又被称 4 颈士论文用户浏览模式与页面推荐的研究 为w e b 日志挖掘。 t 曲挖摇 | ll 弛i l | 撇l i e 磷裁蜕兜撼 i 弛钢记嚣啦 上llll上 文 多超 内 个 本 蝶链 部 般 性 挖 体接 结 访 化 挖挖 构河 使 掘挖模 甩 摇括记 握式 录 2 2 1w e b 内容挖掘 图2 2w e b 挖掘的分类 w 曲内容挖掘即从网络的内容，数据，文档中发现有用信息的过程。w 曲信息 资源类型众多，i n t e m e t 出现之后，各种形式的资源逐渐隐藏到超文本形式之后，但 这些资源仍可以通过w e b 进行访问。然而除了大量的人们可以直接从网上抓取，建 立索引，实现检索服务的资源之外，一些网络信息是“隐藏”的数据，如由用户的提 问而动态生成的结果，或是存在d b m s ( 数据库管理系统) 中的数据，或是那些私人数 据，它们无法被索引，从而无法提供对它们有效的检索方式。若从资源形式看，网络 信息内容是由文本，图像，音频，视频数据等形式的数据组成的，因而w e b 内容挖 掘也可以称为多媒体数据挖掘。w e b 内容挖掘主要研究热点是文本挖掘【6 】。文本挖掘 的一般过程包括：数据收集，文本预处理，文本特征提取，挖掘结果。 2 2 2w e b 结构挖掘 w e b 结构挖掘即挖掘w e b 潜在的链接结构模式，即通过分析一个网页链接和被 链接数量以及对象来建立w e b 自身的链接结构模式。w e b 结构挖掘可以用于网页归 类，并且可以由此获得有关不同网页间相似度及关联度的信息。w e b 结构挖掘有助于 用户找到相关主题的权威站点，并且可以指向众多权威站点的相关主题的站点。 i n t e m e t 上页面与页面之间是通过超链接相互联系起来的。某一个页面既可能链 接到其他多个页面，也可能有其他多个页面链接到它本身，所以w 曲上页面之间的 5 硕士论文 用户浏览模式与页面推荐的研究 连接是多对多的关系。从图论的角度出发，整个网络是一个有向图，每个页面是有向 图上的一个节点，链接关系就是连接节点和节点之间的边。通过对页面之间链接关系 的分析和处理，即通过w e b 结构挖掘，可以得出页面和页面之间链接关系的重要性， 同时也可以得到页面和页面之间的层次关系嘲。图2 3 是页面链接结构示意图。 图2 3 页面结构示意图 目前通常使用的w e b 结构挖掘算法主要有p a g e r a n k 算法和m t s 算法。 ( 1 ) p a g e r a n k 算法 p a g e r a n k 算法是由s _ i a n d f o r d 大学的b r i n 和p a g e 提出的，是较为成功的w e b 结 构挖掘算法，被著名的搜索引擎g o o g l e 所采用。 p a g e r a n k 算法的基本原理是：将网络看作成一个有向图，设集合c 是有向图中 节点的集合，有向图中每个节点都有出链接和入链接，设节点i 的出链接集合为o u t ( i ) ， 入链接集合为i n ( i ) ，则可以通过以下两个步骤计算节点i 的p a g e r a n k 值。首先以概 率p 随机选择一个节点，再以概率1 1 随机选择当前节点i 的一个出链接节点 p a g e r a n k ( i ) = ( 1 - p ) n + d 寄 ( 2 1 ) 但是p a g e r a n k 存在一些不足，如p a g e r a n k 算法偏重已经存在的旧网页，因为旧网 页被其它网页链接到的可能性更高，但是事实上新的网页可能会具有更好的信息价 值；p a g e r a n k 算法无法处理动态生成的页面：p a g e r a n k 算法偏重以综合性的网站，因 为这些网站可能比其它类型的网站获得更多入链接和出链接；p a g e r a n k 算法无法区分 网页中的超链接是和网页主题相关还是不相关，即无法判断网页内容上的相似性，这 样就容易导致出现主题漂移问题唧。 由于p a g e r a n k 算法的先天性不足，就有学者对p a g e r a n k 算法做了很多改进。如上 海交通大学的张玲博士提出了一个加速评估的p a g c r a i l l 【改进算法1 1 0 】，该算法使得网 络上有价值的内容以更快盼速度传播。斯坦福大学计算机科学系t a h v rh a v e l i w a i a 提 出了一种主题敏感( t o p i c - s e n s i t i v e ) i 勺p a g e r a n k 算法【l i 】。 6 硕士论文用户浏览模式与页面推荐的研究 ( 2 ) 肼s 算法 h i t s 算法，& p h y p e r t e x ti n d u c e dt o p i cs e a r c h ，是由康奈尔大学( c o m e l lu n i v e r s i t y ) 的j o h nk l e i n b e r g 博士于1 9 9 8 年首先提出的， 在h i t s 算法中，每个页面都有两个属性：a u t h o r i t y ( 由所有指向它的链接决定) 和h u b ( 由它所指向的链接决定) 。根据页面之间的超链接结构，将页面分为h u b 页和 a u t h o r i t y 页，其中，h u b 页是一个指向权威页的超链接集合的w e b 页，而a u t h o r i t y 页 是被许多h u b 页指向的权威的w e b 页。因此，一个h u b 页面应该指向好的a u t h o r i t y 页 面，而个a u t h o r i t y 页面应该由很多h u b 页面所指向。这样，h u b 页面和a u t h o r i t y 页 面就构成了相互联系，相互增强的关系。 将所有页面的a u t h o r i t y 和h u b 值都设为一个非负的值( 例如都设为1 ) 。然后通 过式2 2 和式2 3 进行迭代直到算法收敛。在每次迭代后通过式2 4 和式2 5 对a p 和h p 进行规范化。收敛后，h i t s 算法将输出一组具有较大h u b 值和a u t h o r i t y 值的 页面。 a 1 = h = t ) v q ：q - - p h 1 = a v p ：p - * q 其中，h q 是h u b 权重，a q 是a u t h o r i t y 权重。 hp = ( 2 3 ) ( 2 4 ) ( 2 5 ) 但是，h i t s 算法也有其一定的局限性。如h u b 页面的多主题性，不相关链接的干 扰，同样存在的主题漂移现象。 由于以上的不足，h i t s 算法进行了很多的改进。如h u b 权重算法的改进，将h u b 权重的计算由它所指向的a u t h o r i t y 权重之和改为a u t h o r i t y 权重的平均值：改进算法解 决两台主机之间的互相强化关系；使用x m l 技术来解决不相关页面的问题，由于x m l 的语义性，就可以通过处理该链接来决定页面的相关性【1 2 1 。 2 2 3w e b 使用挖掘 w e b 使用挖掘，就是从w e b 的访问记录中抽取感兴趣的模式。在网络中每个服 7 一， 一 声咖 硕士论文用户浏览模式与页面推荐的研究 务器保留了访问日志，记录关于用户访问和交互的信息。分析这些数据可以帮助，理 解用户的行为，从而改进站点的结构u 3 1 ，所以又可以称为w e b 日志挖掘。 w e b 使用挖掘的常用技术有以下几种。 ( 1 ) 路径分析技术。用该技术进行w e b 使用模式的数据挖掘时，是将页面之 间的关系用图来表示。网站上的页面定义成节点，页面之间的超链接定义成图中的边。 在w e b 使用模式挖掘过程中，通过路径分析技术可以确定网站的频繁访问路径。 ( 2 ) 关联规则挖掘技术。它主要用于从用户访问序列数据库的序列项中挖掘出 相关的规则。在w e b 使用挖掘中，关联规则挖掘就是要挖掘出用户在一个访问期间 ( s e s s i o n ) 从服务器上访问的页面和文件之间的联系，这些页面之间可能并不存在直接 的参照( r e f e r e n c e ) 关系。 ( 3 ) 序列模式挖掘技术。它就是要挖掘出有时间序列的模式。在w e b 使用挖 掘中，用户的访问是以时闻为单位记载的。经过数据过滤和会话识别后，就生成间断 的时间序列，这些序列所反映的用户行为有助于发现用户浏览网页的特性。 ( 4 ) 聚类分类技术。分类规则可以挖掘某些共同的特性。这些特性用来对新添 到数据库中的数据项进行分类。聚类分析把有相似特性的用户和数据项集合到一起。 2 3w e b 日志挖掘的过程 w e b 日志挖掘的一般过程包括获取日志，日志预处理，日志挖掘，挖掘结果等。 下面介绍w e b 日志挖掘的各个组成部分。 现在较为流行的日志格式是由n c s a ( 美国伊利诺斯大学的国家超级计算应用中 心) 的日志文件规范，即公共日志文件格式( c o m m o n l o g f i l e f o r m a t ，简称c l f ) 。 如图2 4 是c l f 日志的节选。 6 9 8 = z z 7 一一e 略，o v ，i “0 9 ：5 6 ：2 2 l 咐t ，啼，岬_ ，1 0 i z 0 0 0 一h 岫m t i - or ，p 口e r r e 1 1 。2 0 0 3 1 2 8 2 0 0 3 4 7 1 一一t ，n 口v ，2 1 ：a 9 ：5 6 ：2 2 - 0 8 0 0 2 ”g e t ，由埘，l , 螂t s z 3 9 ，2 0 - c h l 咄n e i l 一1 ，口口耵t p ，1 o 。2 0 04 5 8 0 ：1 2 9 2 0 0 ，t 7 1 一- 1 0 9 i n 吖z 0 0 1 ：0 9 ：s 5 ：2 2 一i ”g e ti b 扯i 珥钟酬2 3 ，2 0 0 0 - c b l 曲辅“一7 ，p 口f f r r p 1 o 2 0 00 7 0 4 1 2 82 0 0 3 4 1 l 一一【o g l e a 州l z o o l ：0 9 ：5 6 ：2 2 - o 0 0 0 11 能t - b w 岫e e z 3 ，z o o o 一# h i 脚b 随n 一5 j f 口耵- r e 1 d 2 0 07 9 9 3 ：1 2 8 2 0 0 ， 1 一t 0 s n o v z 0 0 1 ：0 9 ：5 6 ：2 z - 0 e 0 0 1 ”g r r ，_ b 砧，i 魁a e “2 ，9 2 0 0 0 - t b u a o 脯1 1 - ：j p o 盯t p ，1 0 。2 0 06 1 0 1 1 2 8 2 0 0 3 4 1 l 一一【o s n o v 2 0 0 l ：0 9 ：5 6 ：2 2 0 8 0 0 】g r t ，由耻，l m a o e s 2 3 ，- 2 0 0 0 t h l 呐n _ “9 1 p g 们t p ，1 0 。2 0 0 _ 2 1 2 8 2 0 0 3 4 1 l 一一【0 s u o v z o o i ；0 9 ：5 6 ：2 2 0 8 0 0 ) “g c t ，q 扯，n - 叼e 4 ，：3 9 2 0 0 0 t m m b n a i l 1 1 3 口b r _ r p 1 o 。2 0 0 ，甜 i 2 8 z 0 0 3 ，7 j 一- 0 9 ，n 州z i ：0 9 ：s 轧2 2 - q 8 0 0 ，1 q z t - b 扯i 嘲c ，z ，t i 一2 0 t h 岫n - “一玛，口f f f l ，i o 。z 口o9 1 1 2 1 2 日2 0 0 3 4 7 1 一一【o g ，n d v ，瑚i ：0 9 ：5 6 2 2 0 8 0 0 】g e t - b 扯，抽l $ ，z ，92 o 一曲i 叫，n 。1 7 - ) p g 耵t p 1 0 e ：0 09 6 鲚 2 1 3 9 9 9 9 ，1 5 6 一f 0 9 ，n 口v ，2 0 95 ：2 2 - 0 8 0 0 】7 g e ti - c h e m “r e p 血上l a ，e x t l l o h c m i 耵t p ，1 1 。2 0 62 e o s n e 2 0 0 ，t 一一“日，州2 i ；b 9 f s 5 ：2 2 * o e o o 】。0 t - b n c * = = g e s 2 3 9 2 0 0 0 。c h l 曲惦i 卜2 0 j p gf f t p ，1 0 。2 5 娜 控e 2 0 0 3 4 7 1 一- 【g g l n w l 2 0 0 1 ：0 9 ：5 6 ：z z - 0 8 0 0 1 6 耵，q 址e ，l 哪e 5 ，2 3 ，2 0 0 0 一c h 岫n i i 一2 3r ，w # n ，1 0 。2 0 0s ，粥 拉b 2 0 0 3 7 1 一一【0 9 ) = o v z o o x ：0 9 - ：5 6 ：z z - o e 0 0 ) ”g 盯，一咄，t m 口e 吖2 3 9 z 0 一t h 曲n t l l - 1 0 ，硝f t p ，1 o ”2 0 05 0 5 t 壕8 2 0 0 ，7 i 一一【n 9 t n w z 0 0 1 ：0 9 ：5 6 ：2 2 一0 0 】1 0 r t - b 扯m 叫e ，2 3 9 - 2 0 0 0 一c h 岫n 1 - 1 5 ，p ge r r w l o - 2 0 09 3 i 2 8 z 3 4 7 1 一一曲，a w 2 0 0 1 ：0 9 ：5 6 ：2 2 - o e o o ”g e t 咄自c l # 口e $ ，2 3 9 2 0 0 呐c h 岫艏l l - z 2 ，j p 口h t t p 1 o 。2 0 03 日皓 1 2 8 2 0 0 ， 1 l 一0 9 n o v 2 0 0 1 ：0 9 ：s 6 ：2 2 - o e o o 。o r t ，缸，嘲廿，2 ，9 2 0 c b i 咄触“一1 2 ，】p a 帅1 0 - z o o 日： 土2 6 2 0 0 t 1 一一曲，n w ，o ：0 9 ：s ：2 2 0 8 0 0 ) 1 0 c ti - h c l i 瞄g e _ ，2 3 0 2 0 一c h 叫，酏“一8 】9 q 耵t ，i ，0 。2 0 05 5 9 9 址e 2 0 0 ，7 1 一一o 咖v ，；1 ：0 9 ：5 ：2 2 - o e o o ) o 玎- b 让娴e e 2 3 9 2 c 0 - c h 皿自n _ u 1 9 ，”目? r ，1 0 z 5 也 6 9 8 2 2 2 7 一- 1 0 9 n 吖2 0 0 1 ：0 9 ：5 6 ：2 2 一o e o o ) g e t _ b d o ，l m g e s 1 0 1 2 0 0 0 - c h 蛐n i 1 - 4 2 ，p 口a t l 口1 1 。2 0 06 6 1 4 j 1 2 3 1 6 1 0 1 一一f 0 9 ，n 口w 2 l ：0 9 ：5 6 ：z z - 0 8 0 印”c r r ，q m j l e 口n b c ，i l b c5 0 5 h c _ la t t p 1 0 ；z o oj 5 - 5 6 9 8 2 ，2 2 ，一一e o f n w a 0 0 1 ：0 9 ：5 e l ：2 2 - 0 c o o ”龇t 也w ，i m g e o ，1 0 1 z 0 0 0 一h 咖n i 1 - 4 5 】，口耵驯1 1 。2 0 0 耵2 痒 2 1 6 6 5 1 盯2 ”- 1 0 9 姗z o o z ：0 9 ：5 6 ：2 2 - 0 8 0 田1 g e t ，一- h m 缸，l 一7 5 s t a c 岫刖冲，i 1 3 0 13 龉 t 6 92 2 9 缸8 1 一一【，n 口v ，2 l ：0 9 ：5 6 ：2 3 - 0 0 0 0 ”g e ttl r r t p 1 1 。2 0 01 1 5 6 3 矸6 9 e 2 2 2 7 一一f o n w ，z 0 0 1 ：0 9 4 5 6 ：2 3 o e o o l 。血t b 坼，i m 口e “1 0 1 2 d o * c h l 岫m “一，口m n , 1 1 - 2 0 0 懈 2 1 6 5 1 钉2 3 ，一一【0 9 ，m v ，2 0 0 i ：0 9 ：5 6 ；= 3 - 0 8 0 卅g z t ，一- ，劬a 吖慨1 5 一t u ，耵t p ，1 1 - z o o1 5 1 3 ：l ，姻9 9 坫一( 0 9 附：1 ；0 9 ：5 6 2 3 - o s 0 0 ”0 e t ，一c h 酬磷d w 抽i - 口e 4 i ，u 5 ，e d 力包，p 啪辑 i 碍z 7 9 5 2 8 1 一一f ，n 吖，2 1 ：曲：5 6 t 2 稍】4 让t ，_ 掣j ，h 瓣一吖t 口i te m n i ”2 0 03 们 1 6 9 2 2 9 6 z e 1 一- o g n o v ；z e l ) l ；0 9 t 5 6 ：2 i o e a o ) ”6 r t i 啦口e o 船一舯i z 帅，1 1 卸oz 们 1 6 9 2 2 9 缸搴i 一一【，v ，2 ，；幛：s 5 ：2 4 - o e o o g r r ，嘶e 5 ，h e i p 卯1 t 目巾1 1 。2 0 02 t 2 2 9 雠 l - 一 瞎n o v 2 0 0 l ：o e ：5 ；2 删锄】o o l t ，自- 舭，由协l c = , l o v 蛳8 r l ，l - l 砷o 枷 图2 4c l f 日志格式 3 硪士论文用户测览横式与页面推荐的研究 w e b 日志的格式比较复杂，其中包含了很多的信息，如访问者的口域名地址， 访问的时间日期，访问者请求的页面等，各个字段具体的含义见表2 1 表2 1c l f 日志的字段 字段名称字段含义 r e m o t eh o s t 网站访问者的坤地址或者d n s 名 r f c 9 3 l 该访客的远端身份。破折号表明未指定 a u t h u s e r 用户d ，破折号表明”未指定 d a t e t i m e 对服务器请求的日期和时间，相对格林威治的时差 r e q u e s t网站访问者的h t t p 请求，例如g e t 或者p o s t p a g e 访问者请求的页面 v e r s i o n h t t p 1 0 为协议及版本 s t a t u s 服务器所返回的状态代码。例如：2 0 0 代表浏览器请求成功 b y t e s 用户所请求文件的大小 2 4w e b 日志挖掘数据预处理 用户在访问页面时，服务器会记录下用户访问的信息。通常这种信息是按照一定 格式存储在服务器上的，即w e b 日志。w e b 日志一般记录了来访者的i p 地址或者域 名，请求页面的时间和日期，对请求页面的方法，所请求的页面等。但w e b 日志中 的数据并不能完全代表用户浏览的信息，其中有许多可能含有噪声数据或垃圾数据， 这些都会对以后的挖掘算法和挖掘结果造成影响，所以就需要在挖掘之前对这些数据 进行处理以得到适合于挖掘的数据格式。w e b 日志挖掘通常包括数据清洗，用户识 别，会话识别和路径补充等过程。 2 4 1 数据清洗 数据清理是指根据挖掘的需求，对原始的日志文件进行处理。清洗的内容包括删 除不相关的数据，对用户请求页面时发生错误的记录进行适当的处理等。当用户请求 一个网页时，除了请求的页面信息会记录在日志中，这个网页上的图片，视频和音频 信息等也同样会记录在日志文件中。这些信息对于挖掘是没有关系的，如果不清除掉 反而会影响挖掘算法的性能，降低挖掘结果的准确性。通过分析，在数据清理中需要 把日志中请求文件后缀为( 3 s s ，p h p ，a s p ，j p g ，j p e g ，g i f 等记录删除。一般而言，经 过这样处理以后。日志文件的大小会减少为原始文件的1 4 至1 1 0 左右 9 硕士论文 用户浏览模式与页面推荐的研究 2 4 2 数据降维 w e b 日志挖掘需要对日志中的数据维进行提取，即去除与挖掘无关的信息，保留 与挖掘关系密切的信息。参考c l f 日志的格式，字段r f c 9 3 1 ，a u t h u s e r ，v e r s i o n ，s t a t u s 和b y t e s 与挖掘无关，需要去除。对于字段r e q u e s t ，虽然它反映了用户对页面的请 求，但是对以后的挖掘过程，以及挖掘结果并没有直接的影响，所以同样需要去除。 这样，c l f 日志格式中与挖掘有直接关系的字段包括：r e m o t e h o s t ，d a t e t u n e ，p a g e 。 因为在挖掘算法中，需要按照r e m o t eh o s t ，d a t e t r i n e ，p a g e 这三个字段进行各种 操作。通过数据降维，可以在清理掉无关数据的基础上再次大大压缩数据量，达到浓 缩数据，提高数据质量，提高挖掘算法的速度和准确度的目的。 2 4 3 用户识别 对用户访问模式的挖掘而言，用户识别问题是十分重要的，为了能够的更好的加 深用户对网站浏览兴趣的理解，需要按照日志中m 地址或者域名地址来对匿名用户 进行用户识别。由于缓存、代理服务器等的存在和影响，使得用户识别交得很复杂 用户识别是从日志的记录中识别出相应的用户，因此采用以下的规则来进行识 别： 规则( 1 ) ：不同的i p 地址代表着不同的用户。 规则( 2 ) ：当i p 地址相同时，不同的浏览器认为代表不同的用户。 规则( 3 ) ：在p 地址相同，用户使用的浏览器也相同的情况下，则根据网站的拓 扑结构图对用户进行识别。如果用户请求的某个页面不能从已访问的任何页面到达， 则判断这是一个新的用户。如果网站的拓扑结构比较复杂，在根据拓扑结构识别页面 与页面之间的关系时，识别效率会降低。 但是，并不是使用了这些规则就能准确地识别出用户。例如，如果具有相同口地 址的用户若在同样类型的机器上使用同种浏览器，并且请求的页面集合相同，那么将 很难识别。一个用户使用两种类型的浏览器，或是没有使用站点的链接结构直接输入 u r l ，如从收藏的网页直接进入，则容易被认为是多个用户。 2 4 4 会话识别 会话识别即指将用户在同一时间段内访问的页面组成一个用户会话序列，通过其 连续请求的页面，就可以获得用户在网站中的访问行为和浏览兴趣。日志文件中不同 用户访问的页面当然属于不同的会话，所以需要在用户识别的基础上来进行。当某个 用户的页面请求在时间上跨度比较大时，就有可能是该用户多次访问同一个网站，就 l o 硕士论文用户浏览模式与页面推荐的研究 可以将用户的访问记录分成多个会话来处理。最简单的方法是时间窗方式，如果两个 不同页面访问的时问差超过某个值则认为用户开始了另一个新的会话，通常可以使用 3 0 分钟作为一个合理的时间阈值。 在g a u s s 分布的假设下可以为每个单一用户p 设定一个合理的切分阈值，当相邻 页面访问时间间隔超出该阈值时切分会话。基于固定时间窗口的方法，由于用户行为 变化较大，并不可靠，这个时间阈值很大程度上取决于网站内容以及用户浏览习惯， 比如一个小说网站每个页面的浏览时间一定远远长于一个图片网站。在时间方面，高 速缓存也会带来错误判断。会话标识的目的就是要尽量创建每一个用户的有意义的页 面聚类。 在会话识别完成后，同样需要将会话长度小于3 的会话去除。因为在w c b 日志挖 掘中，浏览或者会话长度大于3 的才有意义。 需要注意的是，w e b 日志的预处理是为以后的挖掘算法做准备的，在算法的设计 和性能上应当是合理和快速的。 2 5w e b 日志挖掘的算法 w e b 日志挖掘的算法通常可以分为两大类：第一类是基于统计理论的，常用的有 概率分析，聚类和分类分析等；第二类是基于人工智能的，通过训练和学习样品空间 从而得出需要的模式。w e b 日志挖掘的算法目前常见的有：统计分析，关联规则分析， 序列模式分析，聚类分类分析，决策树和神经网络等。 2 5 1 统计分析 统计分析是收集，组织数据并从这些数据集中得出结论的科学。历史上，最早建 立在计算机基础上的数据分析方面是由统计分析人员支持的。从一元到多元的数据分 析，统计理论为数据挖掘提供了大量不同类型的判别分析方法【1 5 1 。通过求出现率，求 平均，求中值。统计最经常访问的网页，每页平均访问的时间，浏览路径的平均长度， 网页视图，浏览时间，导航路径长度等，可以获得用户访问站点的基本信息，所以可 以将统计分析的理论应用到w e b 日志挖掘中来分析用户行为。除此之外，还能提供 有限的低层次的错误分析，比如检测未授权入口点，找出最常见不变的u r l 等。 统计分析的般方法有：回归分析( 多元回归、自回归等) ，判别分析( 贝叶斯 分析，f i s h e r 判别，非参数判别等) 。统计分析的处理过程可以分为三个阶段：搜集 数据，分析数据和进行推理。 作为- - 1 3 最早用来分析w e b 日志的技术，统计理论为以后w e b 日志挖掘算法提 供了理论基础。 颈士论文用户浏览模式与页面推荐的研究 2 5 2 关联规则分析 关联规则分析的概念可以从商品的购物记录来引出。商品的购物记录是用户一次 购买商品的清单，可以看作是一次购买的事务。每个事务中都记载了用户购物的项， 或者叫做项集。关联规则分析就是对这些项集进行分析。并试图找出有价值的项集的 集合。 关联规则分析是指从大量的数据集中发现有用的依赖性或关联性的知识。关