（计算机应用技术专业论文）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 上隐藏的用户感兴趣的信息，为用户提供个性化服务、信息导航，并对网 站结构的改进与优化提供依据。w e b 使用挖掘分为数据采集、数据预处理、模式发现 与模式分析四个阶段，其中数据预处理和模式发现是本文研究的重点。 首先，数据预处理是w e b 使用挖掘的一个难点。它分为数据清洗、会话识别、 路径补充、事务识别四个阶段。本文在会话识别阶段，提出了基于d f a 方式的会话 识别。在路径补充阶段，提出了一种基于多窗口方式的路径补充。并在此基础上，构 造了可用于动态框架网站会话识别的s r d f a 。在事务识别阶段，本文改进了事务识 别方法中的最大向前路径法，在事务识别阶段记录可能需要添加的超链接。 其次，模式发现也是一个重要的阶段。在这个阶段中，本文给出了一种改进的 a p r i o r i 算法( r s a p r i o r i 算法) 。它通过自上而下的方式从最大频繁项集开始挖掘，直 到挖掘出用户需要的频繁项集后终止。 此外，本文设计了两个验证性实验，证明了整个处理框架的可行性。最后，本文 将整个处理方法运用于一个真实的m v c 模式下的s t r u t s 框架网站，在实践中证明了 此方法的有效性和实用性。 本文对w e b 使用挖掘部分算法的改进具有一定的现实意义。首先，它对会话识 别和事务分割方法的研究以及部分数据挖掘算法的改进具有一定的参考价值，在一定 程度上推动了w e b 使用挖掘算法的研究；其次，它也促进了w e b 访问行为分析、网 站结构分析和网站结构优化等方面的研究。 关键字：w - e b 使用挖掘、会话识别、路径补充、关联规则、a p r i o r i 算法 作者：黄金晶 导师：杨季文 a b s t r a c tr e s e a r c ha n di m p r o v e m e n to nw e bu s a g em i n i n g r e s e a r c ha n di m p r o v e me n to nw e b u s a g em i n i n g a b s t r a c t r e s e a r c h e r sa p p l yd a t am i n i n gt e c h n o l o g i e st or e s e a r c h so nw e bt e c h n o l o g i e ss i n c e d a t am i n i n gt e c h n o l o g i e sa r er a p i d l yd e v e l o p e d i tr e s u l t si nan e wr e s e a r c ha r e ac a l l e d w e bm i n i n g w e bu s a g em i n i n g ，w h i c hr e t r i e v e sh i d d e na n di n t e r e s t i n gi m f o r m a t i o nb y a n l a y s i n gw e bs e r v e rl o g ，i so n eo ft h ei m p o r t a n tb r a n c h e so fw e bm i n i n g i tp r o v i d e s i n d i v i d u a t i o na n dn a v i g a t i o no fw e bs y s t e m st ou s e r s m o r e o v e r ；i ti st h ef o u n d a t i o no f r e c o n s t r u c t i n gw e bs i t e s w e bu s a g em i n i n gi sd i v i d e di n t of o u rp h a s e s ，d a t ac o l l e c t i o n ， d a t ap r e p r o c e s s i n g ，e s t a b l i s hi n t e r e s t i n gm o d e la n dp a r e ma n a l y s i s ，a n dt w oo ft h e m ，d a t a p r e p r o c e s s i n ga n de s t a b l i s hi n t e r e s t i n gm o d e l ，a r ew h a tt h i sp a p e rf o c u s e so n f i r s t l y , i nw e bu s a g em i n i g ，o n ed i f f i c u l t yi sd a t ap r e p r o c e s s i n g ，w h i c hi sd i v i d e di n t o d a t ac l e a n i n g ，s e s s i o nr e c o n s t r u c t i o n , p a t hs u p p l e m e n ta n dt r a n s a c t i o nr e c o n s t r u c t i o n i n t h es t e po fs e s s i o nr e c o n s t r u c t i o n ，t h i sp a p e r p r o p o s e ss e s s i o nr e c o n s t r u c t i o nb a s e do nd f a ， a n di nt h ep a t hs u p p l e m e n t s t e p ，p r o p o s e s ap a t h s u p p l e m e n tm e t h o db a s e do n m u l t i w i n d o w b e s i d e s ，t h ep a p e rp r o p o s e ss r d f a ，w h i c hr e c o n s t r u c t ss e s s i o n sa i m i n ga t d y n a m i cf r a m e w o r kw e bs i t e s i nt h et r a n s a c t i o nr e c o n s t r u c t i o ns t e p ，t h i sp a p e ri m p r o v e s t h em a x i m a lp a t hf o r w a r dm e t h o d ，w h i c hr e c o r d st h eh y p e r l i n kt h a tn e e db ea p p e n d e d s e c o n d l y , e s t a b l i s hi n t e r e s t i n gm o d e li sa ni m p o r t a n tp h a s e i nt h i sp a p e r , w ep r e s e n t a ni m p r o v e da p r i o da l g o r i t h mf o rt h i sp h a s e ，c a l l e dr s a p r i o r i i to b t a i n sa l lf r e q u e n t i t e m s e t so n eb yo n et h r o u g has e r i e so fi t e r a t i o n sb e g i n n i n gf r o mt h el a r g e s tf r e q u e n t i t e m s e t s u s e r sn e e dt os e tt h ep a r a m e t e rkb e f o r eu s i n gt h i sa l g o r i t h ma n dt h ea l g o r i t h m d o e sn o tf i n i s hu n t i lt h ef r e q u e n tk - i t e m s e t sa r ef o u n d b e s i d e s ，t h i sp a p e rd e s i g n st w oe x p e r i m e n t st op r o v et h ef e a s i b i l i t yo ft h ee n t i r e f r a m e w o r k f i n a l l y , a p p l i e st h ew h o l ea l g o r i t h mt oar e a ls t r u t sf r a m e w o r kw e bs i t eb a s e d o nm v c ，p r o v e st h ee f f i c i e n c ya n dp r a c t i c a b i l i t yo ft h ea l g o r i t h mi nt h ep r a c t i c e t h ei m p r o v e da l g o r i t h mo fw e bu s a g em i n i n gi nt h i sp a p e rh a sc e r t a i np r a c t i c a l s i g n i f i c a n c e f i r s to fa l l ，i tp r o v i d e ss o m er e f e r e n c ef o rs e s s i o nr e c o n s t r u c t i o na n d t r a n s a c t i o nr e c o n s t r u c t i o na sw e l la ss o m ed a t am i n i n ga l g o r i t h m s ，w h i c hp r o m o t e sf u r t h e r r e s e a r c ho fw e bu s a g em i n i n gt oac e r t a i ne x t e n t ；s e c o n d l y , i ta l s op r o m o t e st h er e s e a r c h f o rw e ba c c e s sa n a l y s i s ，s t r u c t u r a la n a l y s i sa n dw e bs i t eo p t i m i z a t i o n , e t c k e y w o r d s ：w e bu s a g em i n i n g ，s e s s i o nr e c o g n i t i o n ，p a t hs u p p l e m e n t ，a s s o c i a t i o nr u l e s ， a p r i o r ia l g o r i t h m w r i t t e nb yh u a n gj i n j i n g s u p e r v i s e db yy a n gj i w e n 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：坐：垒丛 日期：塑! z ：曼：苎 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：茎垒曼 e l 导师签名日 期：兰堂：互 期：竺! ! ! ：墨：芝 w e b 使用挖掘方法的研究与改进第l 章绪论 1 1 课题背景 第1 章绪论 随着网络和通讯技术的发展，w w w ( w o r l dw i d ew e b ) 已经成为一个遍布全球、 拥有亿万用户的分布式信息空间。同时，w e b 上的数据正以每天新增一百万个页面的 速度在增长，页面数目己经超过了1 0 亿【l 】。这个巨大的信息空间包含着丰富的信息， 这些信息涉及各个领域，包括商业、科研、教育等等，为人们提供了不出家门就能了 解世界、获取所需知识的一个平台。 面对如此海量的信息，用户仅仅靠一些关键字匹配的搜索引擎有的时候没有办法 准确定位出真正需要的信息。尽管w e b 上容纳了海量的信息，但是这些信息中有很 多是不完全的、有噪声的、模糊的，因而如何从这些信息中筛选定位出用户所需的信 息就成为w e b 营运商和w e b 用户日益关注的焦点。当前有许多基于索引的w e b 搜索 引擎，可以对w e b 进行搜索，对w e b 页面作索引，建立和存储大量的基于关键字的 索引，用于定位包含某关键字的w e b 页面【2 】。利用搜索引擎，用户通过提供有效的关 键字，一定程度上能够快速的找到自己感兴趣的知识，定位自己所需要的文档。然而， 用户在提供一个关键字后，可能由搜索引擎返回成百上千个链接，其中许多和用户实 际需要的信息相关性很小，同时，用户的需求也在不断增加，越来越多的用户希望获 取信息背后隐藏的、有用的知识，甚至希望网站能够为他们提供个性化服务。因此， 随着i n t e m e t 技术的迅猛发展，关键字匹配的搜索引擎已经不能完全满足用户获取信 息的需求。 随着数据挖掘技术，4 j 的不断发展，人们开始尝试将该技术运用于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 e b 挖掘与传统数据挖掘相比有其自身的特点，而正是由于这些特点，使之成为 研究的一大热点。随着w e b 挖掘技术的不断深入，它将成为在w e b 上获取信息的一 第1 章绪论w e b 使用挖掘方法的研究与改进 个重要手段。数据挖掘就是从大量数据中发现有趣的模式和用户感兴趣的知识，这些 知识恰恰是事先未知的、潜在有用的、易被理解的信息。相应的w e b 挖掘就是针对 w e b 上海量、复杂、离散的数据，挖掘出隐藏在w e b 数据里的有用信息与有用模式。 相比于传统数据挖掘技术，w r e b 数据挖掘自身的特点表现在以下几个方面：首先，传 统数据挖掘技术针对的数据一般是关系型数据库，数据有很强的结构性，而w e b 数 据是无结构或者半结构化的；其次，w e b 数据源众多，每个站点都可以视为一个数据 源，这些数据源之间存在异构性，因为每个站点的组织和结构都不一定相同，因而构 成了w e b 挖掘巨大的异构数据源环境；再者，w e b 数据具有动态性，数据不停地发 生着更新和替换，因而数据间存在着冗余和不一致的现象。 目前，对w e b 挖掘的研究主要集中在三个方面，w e b 内容挖掘、w e b 结构挖掘 以及w ，e b 使用挖掘1 5 】。很多公司和科研机构也在不断的为开发具体的挖掘产品而努 力。比如i b m 公司开发的i n t e l l i g e n tm i n e rf o rt e x t ，就是一个用于文本挖掘的工具， w e b a l i z e r 、a n a l o g 6 , 7 j 等就是用于日志分析的工具。随着网络应用的不断深入，w e b 站点设计的重要性日渐提高，一个设计合理的网站，用户能很方便的找到自己所需要 的网页，同时，能显著的减少网站维护人员的工作量。因而，如何合理的进行站点设 计、导航设计成为网站设计者关注的重要问题，也是w e b 使用挖掘研究的重要内容 之一。 1 2 课题研究内容 w e b 使用挖掘主要是通过对w e b 日志数据进行分析，揭示隐藏在数据后面的各 种关系。利用w e b 使用挖掘技术一方面为用户推荐页面、提供个性化服务，另一方 面为网站优化提供一定的依据。 本课题主要是围绕着w e b 使用挖掘的相关技术展开，研究的是w e b 使用挖掘几 个阶段中的一些相关算法以及这些算法在网站优化中的应用。课题在介绍w e b 挖掘 总体相关知识的基础上，重点介绍了w e b 使用挖掘的相关技术与研究方法。根据w e b 使用挖掘的四个阶段：数据采集、数据预处理、模式分析与模式发现，分步研究每个 阶段具体采用的方法，分析方法的不足，并给出相应的改进算法。具体研究内容如下。 ( 1 ) 首先，重点研究了数据预处理阶段的有关算法，并有针对性的作了改进，给 2 w e b 使用挖掘方法的研究与改进第l 章绪论 出了基于d f a ( 确定的有限自动机) 的会话识别和多窗1 3 方式的路径补充方法，构造了 s r d f a ，并对最大向前路径法做了部分修改。数据预处理是w e b 使用挖掘的难点， 因为预处理结果的好坏对后续模式发现有重要的影响，所以数据预处理是本课题研究 的重点内容之一。数据预处理阶段又分为数据清洗、用户识别、会话识别、路径补充、 事务识别几个步骤。本文针对会话识别和路径补充给出基于自动机的会话识别方法和 基于多窗口方式的路径补充算法，对于一段用户日志，通过d f a 各状态问的转换， 完成会话识别，使得最终结果更加接近于用户真实的访问路径。此外，在事务识别阶 段，文章对传统最大向前路径法进行了部分改进，在切割事务的同时提取出可能需要 添加的超链接，为网站结构的优化提供了一定的参考。 ( 2 ) 其次，主要研究了模式发现阶段中应用于关联规则挖掘的相关算法，并给出 一种改进的关联规则挖掘算法r s a p r i o r i 算法。在分析了a p r i o r i 与f p 增长两个关联 规则挖掘经典算法的基础上，针对a p r i o r i 算法的不足，给出了一种r s a p r i o r i 算法， 并用相关的数学方法证明了r s a p r i o r i 算法的正确性。r s a p r i o r i 算法是一种反序的 a p r i o r i 改进算法，该算法根据用户给定的参数，从最大频繁项集开始逐步向下挖掘 频繁项集，直到用户所需的频繁项集终止，给用户提供了一定的交互性。 ( 3 ) 再次，研究了模式分析阶段获取有效关联规则的方法。在挖掘出频繁项集的 基础上，进行关联规则计算，并根据最小置信度阈值从众多规则中挑选出强关联规则。 这项工作为网站结构的优化提供了一定的依据。 ( 4 ) 最后，本文将全部改进算法合成一个整体的流程，并设计了验证性实验，该 实验模拟用户实际的访问路径，证明了整个处理框架的可行性。在此基础上，将整体 算法运用于一个m v c 模式下的s t r u t s 框架网站，在实践中检验算法。 1 3 课题研究意义 随着i n t e m e t 技术的飞速发展，各种w e b 站点不断的涌现出来，现在仍然有相当 多的网站设计人员在设计实现网站时常常只是凭自己的经验对信息进行分类，并没有 真正的依据用户实际的访问行为，这可能导致网站出现结构不合理、信息冗余、信息 堆砌等缺陷。然而一个不合理的网站不论对用户还是对网站维护者本身都是不利的： 一方面，用户查找自己所需要的信息费时费力，可能在他还没有找到所需信息前就已 第1 章绪论w e b 使用挖掘方法的研究与改进 经丧失了继续访问该网站的兴趣，很显然在当今这样一个商业竞争如此激烈的时代， 这样的网站是完全没有竞争力的；另一方面，对于网站维护人员而言，构建一个合理 的网站，在给出相同信息量的条件下，减少用户的点击次数，很显然能降低网站的负 担。 本课题主要研究了w e b 使用挖掘的相关技术，并改进了其中的部分算法。尽管 这些算法并不一定是最优算法，还有待于进一步的研究与完善，但是本课题所做的工 作还是具有一定的现实意义，体现在如下方面： ( 1 ) 本文给出的基于d f a 方式的会话识别方法以及对最大向前路径法的修改，对 会话识别和事务分割方法的研究具有参考的价值，促进了w e b 使用挖掘技术的发展。 s r d f a 构造的会话，相对于传统基于时间和基于启发方式构造的会话，更加接近于 真实的用户访问行为，避免了总时间阈值对一段完整用户会话造成的切割，并且它弥 补了以往会话构造针对静态的非框架网站这一缺陷。 ( 2 ) 本文在会话识别阶段和模式发现阶段给出的相关改进算法，对部分数据挖掘 算法的改进具有参考价值。比如将传统路径补充扩展到多窗口方式下的路径补充，符 合现在多窗口浏览器访问网站的特点。此外，设计的r s a p r i o r i 算法从最大频繁项集 开始向下挖掘，直至用户需要的频繁项集后终止，为用户提供交互性，提高a p r i o r i 算法的性能。这些改进算法在一定程度上推动了数据挖掘算法的研究。 ( 3 ) 本课题将w e b 使用挖掘的理论运用于实际，在网站优化方面进行了有益的尝 试，并取得了较为满意的结果，促进了w e b 访问行为分析、网站结构分析和网站结 构优化等方面的研究。 综上所述，课题研究的内容对于w e b 使用挖掘在网站的优化方面的应用，具有 一定的现实意义和参考价值。 1 4 文章组织结构 全文的组织如下： 第一章简要介绍了课题提出的背景、课题的研究内容、课题的研究意义。 第二章介绍了w e b 挖掘的分类，重点说明了其中w e b 使用挖掘的应用，还介绍 了它在国内外的研究现状。 4 w e b 使用挖掘方法的研究与改进第1 章绪论 第三章针对w e b 使用挖掘的数据采集、数据预处理、模式发现与模式分析这四 个主要阶段，介绍了其中的相关技术与方法。 第四章介绍了数据预处理的过程，重点介绍了会话识别、路径补充与事务识别中 常用的方法。在此基础上分析了方法的不足，给出基于d f a 的会话识别以及多窗口 方式的路径补充方法，构造了s r d f a 。此外，改进了事务识别中的最大向前路径法。 第五章介绍了两种经典的关联规则挖掘算法a p b o r i 与f p 增长算法，在此基础 上介绍了本文给出的一种改进的a p r i o r i 算法r s a p r i o r i ，并对挖掘出来的频繁项集进 行模式分析。 第六章介绍了针对整体流程的验证性实验，详细说明了实验方案、实验结果，并 将算法运用于一个实际，在实践中检验算法。 第七章对所做的工作进行总结，并对未来工作进行展望。 第2 章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 使用挖掘的应用与它在国内外的研究现状。 2 1w e b 挖掘的分类 2 1 1w e b 挖掘简介 w e b 挖掘是采用数据挖掘技术从w e b 文档和服务中自动的发现与抽取感兴趣的、 潜在有用的模式和隐含的、事先未知的、潜在的信息，涉及w e b 技术、数据挖掘、 计算机语言学、信息学等多个领域，是一项综合技术【l l 。w e b 数据挖掘的应用非常广 泛，不但涉及页面信息的提取、站点的设计与优化，而且在电子商务方面也有很好的 应用前景，如为顾客提供个性化服务、推荐页面、提供页面导航等等。由于w e b 数 据的非结构化和半结构化以及动态性的特点，因而很难对w e b 页面上的数据直接进 行挖掘，一般需要对数据进行必要的预处理。 根据研究的对象和目的不同，将w e b 挖掘分为三类：w e b 内容挖掘( w e bc o n t e n t m i n i n g ) p 】、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 ) 。 图2 1 为w e b 挖掘的分类图。其中w e b 内容挖掘主要是对页面内容进行挖掘，从文 本、图像和视频等多媒体信息中发现有用的信息。w e b 结构挖掘是研究w e b 页面内 部和外部的超链接结构，即发现文档建立的超链接结构。w e b 使用挖掘主要侧重于分 析用户的访问日志发现浏览者访问该站点的行为模式，找出其中的频繁访问模式。 6 w e b 使用挖掘方法的研究与改进第2 章w e b 使用挖掘概述 w e b 挖掘 w e b p q 容挖掘lw e b 结构挖掘lw e b 使用挖掘 嚣煞l 旧体挖掘m 部结构挖掘fp 鬻链接 i w 曲搿瞌 2 1 2w e b 内容挖掘 图2 1w e b 挖掘分类图 w e b 内容挖掘是一种基于网页内容的w e b 挖掘，是从大量的w e b 数据中发现信 息、抽取有用知识的过程。w e b 内容挖掘的对象较为广泛，包括w e b 文档信。窟, ( t e x t 、 h t m l 等格式的文档) 和多媒体信息( i m a g e 、v i d e o 、a u d i o ) ，因而可以将w e b 内容挖 掘分为文本数据挖掘和多媒体数据挖掘。 1 w e b 文本数据挖掘 w e b 文本挖掘是以计算语言学、统计数理分析为理论基础，结合机器学习和信息 检索技术，从大量的文本数据中发现和提取隐含的、事先未知的知识，最终形成用户 可理解的、有价值的信息和知识的过程f 1o 】。w e b 文本挖掘根据对象不同，又可以分 为对单文本的挖掘和对文本集的挖掘，其中对单文本的挖掘主要采用文本总结和信息 提取的方法，对文本集主要采用文本分类、文本聚类、关联规则分析等方法。 文本总结又称文本摘要，是对文本信息进行浓缩，即抽取文本中的关键信息，对 整篇文章进行概括性描述，用户只需要看少量文字就能了解整篇文章的大致思想。 文本分类f lo j 就是按照事先定义好的分类模型，为每一个文档确定归属的类别，是 一种典型的有指导机器学习问题。文本分类包括训练阶段和分类阶段。在训练阶段， 首先确定类别的集合s - s l ，s 2 s k ) ，然后给出训练文档集合t - t 1 ，t 2 t i ， 对于每个训练文档t i ( i 【1 j 】) 将其归为个特定的类别，而后抽取每个训练文档的特 征，得到特征向量v ( t j ) ，以此确定s 中每个类别的特征向量v ( s i ) 。在分类阶段，对 于测试文档集合d = d i ，d 2 d k ，计算每个待分类文档d i ( ie 【lj 】) 与每个v ( s i ) 7 第2 章w e b 使用挖掘概述 w e b 使用挖掘方法的研究与改进 之间的相似度，将相似度最大的一个类别作为d i 的类别。训练方法和分类算法是分 类系统的核心部分，目前存在多种基于向量空间模型的训练算法和分类算法，例如， 支持向量机算法、神经网络方法、最大平均嫡方法、最近k 邻居方法和贝叶斯方法 鐾笔0 0 r 弋r o 文本聚类是一种典型的无指导机器学习问题，就是根据文档的特征向量，将相似 度最大的文档聚成一类。文本聚类的目标是将文档集分成几个不同的类，每一类中的 文档相似程度最高，不同类之间文档的相似度最低。根据文本聚类的结果不同，可以 将文本聚类方法分为层次聚类法和平面聚类法【l o 】。 2 多媒体数据挖掘 多媒体数据挖掘是指从多媒体文本数据中抽取事先未知的、隐藏的、完整的、新 颖的知识，为决策领域提供服务的过程。多媒体数据挖掘可以分为多媒体文本内容挖 掘和多媒体文本结构挖掘，主要采用的方法是特征提取法和关联规则法。 2 1 3w e b 结构挖掘 w e b 结构挖掘i l l j 就是对w e b 文档的结构进行挖掘，它的对象是w e b 本身的超链 接。w e b 结构挖掘主要是从w e b 的结构以及引用和被引用的关系中得到同一网站内 部以及不同网站之间的链接关系。 w e b 结构挖掘的一个重要研究内容是查找权威网页。w e b 不仅由页面组成，而且 还包含了从一个页面指向另一个页面的超链接，当一个作者建立指向另一个页面的指 针时，这可以看作是作者对另一个页面的认可【2 】。用户通过g o o g l e 、百度等搜索引擎 查找某一主题的相关信息时，在搜索引擎中输入该主题的关键词，而后搜索引擎返回 大量跟该主题有一定相关性的记录，用户总希望排在前面的记录就是论述该主题的权 威网页。查找权威页面是w e b 结构挖掘的重要应用之一，受到众多专家的关注。 w e b 结构挖掘的一个重要概念就是有向图。w e b 本身可以用一个有向图来表示， 网站中每个网页就是图中的一个节点，每个指向其他页面的超链接( 包括网站内部的 超链接和网站之间的超链接) 就是图中的一条有向边。图2 2 就是一个有向图，表示 a ，b 两个网站之间的链接关系，其中a l ，a 2 ，a 3 和b l ，b 2 分别是a ，b 两个网站的内部链 接，而有向边a b 代表a 网站主页上有指向b 网站主页的超链接。 8 w e b 使用挖掘方法的研究与改进 第2 章w e b 使用挖掘概述 图2 - 2 网站有向图 w 曲结构挖掘主要采用的算法是p a g e r a i l l 【算法【1 2 ，1 3 】和h i t s 【1 4 ，1 5 1 算法。p a g e r a n k 算法是由斯坦福大 f l 勺s e r g e yb r i n 和l a w r e n c ep a g e 提出的【15 1 ，是搜索引擎g o o g l e l 拘l 核 心算法，该算法通过提取网页的链接信息，计算得出网页的p a g e r a n k 值，其中网页的 p a g e r a n k 值代表网页的重要程度。p a g e r a n k 算法的主要思想是把网页的链接分成导入 链接和导出链接，比如a 网页上有指向b 网页的超链接，那么该链接是a 网页的一条导 出链接，是b 网页的一条导入链接。p a g e r a n k 的值由导入链接的数量和这些链接的级 别决定。导入链接的数量越多，表示一个网页被其他网页引用的次数越多，那么该网 页是一个重要网页的可能性越大。此外，如果一个网页被一个很重要的网页引用，那 么该网页的p a g e r a n k 值也会提高。 h i t s ( h y p e r t e x ti n d u c e dt o p i cs e a r c h ) 算法是k l e i n b e r g 于19 9 9 年提出的【1 6 1 。在这个 算法中，引入了新的概念h u b 。h u b 是指一个或多个w e b 页面，它提供了指向权威页面 的链接集合1 5 1 。一个好的h u b 会指向很多好的权威页面，而一个好的权威页面则是有 很多好的h u b 所指向。h i t s 算法的基本思想如下【2 】：首先，在搜索引擎中输入关键词， 得到基于该关键词的n 个页面，构成根集( r o o ts e t ) 。再将根集中页面所指向的页和指 向根集的页加入根集，形成基本集( b a s es e t ) ，可以为基本集设置上限，即扩展的尺度。 其次，为基本集中的每一个页面设置一个非负i 拘h u b 权重h p 和一个非负的权威权重a p ， 且h 和a 初始化为同一个常数。然后，h u b 和权威权重按如下公式计算： a p = h q ( 2 - 1 ) 口满足9 一p 铲 ( 2 - 2 ) q 满) t ：p - - q 9 第2 章w e b 使用挖掘概述 w e b 使用挖掘方法的研究与改进 式( 2 1 ) 反映了若一个页面由很多好的h u b 所指，则其权威权重会相应增加【2 1 。式( 2 2 ) 反映了若一个页面指向许多好的权威页，贝l j h u b 权重会相应增加【2 1 。 2 1 4w e b 日志挖掘 w e b 日志挖掘又称w e b 使用挖掘，是w e b 挖掘的一个重要研究领域，主要是利用 数据挖掘技术从w 曲服务器日志中获得关于网站有价值的用户访问模式。w e b 内容挖 掘和w ，e b 结构挖掘的数据直接来源于w e b 页面，而w e b 使用挖掘的数据并不直接来源 于页面本身的内容，主要是w 曲服务器用户访问日志、代理服务器日志、浏览器日志 等用户访问w e b 页面后产生的使用信息。 w e b 使用挖掘通过分析w r e b 日志，挖掘出潜在的用户访问网站的规律，能够用于 改进网站的设计，合理配置网站的资源，还能发现电子商务的潜在客户，为客户提供 优质的因特网信息服务。w r e b 日志挖掘一般分为数据采集、数据预处理、模式发现与 模式分析四个阶段，它的过程如下：首先采集用户访问网站留下的日志信息，然后将 这些信息构成用户会话，并将会话切割成适合挖掘的事务，而后通过挖掘算法从中挖 掘出用户感兴趣的模式。图2 3 就是w e b 使用挖掘的总体流程图。 图2 - 3w e b 使用挖掘总体流程 由于w e b 数据自身半结构化、动态性等特点，使得无法对w e b 数据直接进行挖掘， 因而数据预处理是整个w e b 使用挖掘的基础，这个阶段所完成工作质量的好坏对后续 1 0 w e b 使用挖掘方法的研究与改进第2 章w e b 使用挖掘概述 模式发现、模式分析都有至关重要的作用。模式发现阶段的任务是从预处理完毕的数 据集中挖掘出潜在的模式与规则，是w e b 使用挖掘中的重点。模式分析阶段是从挖掘 出的模式与规则中提取用户感兴趣的模式与规则，形成更易被用户所理解的知识。本 文主要研究w e b 使用挖掘的相关技术与方法，在第四章会详细介绍数据预处理的过程 与方法，第五章会详细介绍模式发现与模式分析的具体细节。 2 2w e b 使用挖掘的应用 随着i n t e m e t 的发展以及数据挖掘技术的不断成熟，w e b 使用挖掘的技术也不断提 高，使用的范围也不断扩大。w e b 使用挖掘的结果有着重要的商业运用价值，具体体 现在如下方面： ( 1 ) 为用户提供个性化服务【1 7 1 8 1 。w r e b 使用挖掘的一个重要应用领域就是为用户提 供个性化服务。随着科技的不断进步，人们对“个性化 的呼声越来越强烈，追求个 性早已成为一种时尚，当然与之相适应的就是人们越来越希望网站能随着自己浏览的 兴趣尽可能的自动调整网站的结构，使得网站上呈现的内容跟自己的兴趣尽可能的相 符，真正的实现以用户为中心。正是由于这些需求，促使了w e b 使用挖掘的发展。 w e b 使用挖掘通过分析用户访问网站留下的日志文件，对用户的访问行为进行聚类， 从而发现用户的个性化搜索模式，为每个用户制定不同的w e b 站点，提供符合其兴趣 爱好的w e b 页面，这样用户在访问网站时仿佛网站就是为自己量身定制的一样。 ( 2 ) 为用户进行信息导航。为用户提供信息导航是网站设计者关注的一个重要方 面，也是w 曲使用挖掘的重要研究内容之一。当今，网站的内容越来越丰富，结构也 越来越复杂，在如此众多的信息前用户常常会觉得晕头转向，不知道自己所需要的信 息在哪个页面上，往往花费很多时间去寻找，甚至在浩瀚的信息量中迷失了方向。因 而，为用户提供信息导航显得较为重要。w e b 使用挖掘通过采用相应的聚类算法对整 个用户群体聚类，将具有相似浏览模式的用户聚为一类，每类用户具有相似的兴趣爱 好和共同的访问习惯，为每类用户定制特定的信息，在w e b 页面上用图形标注出链接， 通过该链接引导用户找到自己感兴趣的页面。 ( 3 ) 为用户推荐信皂 1 9 , 2 0 , 2 1 1 。w e b 使用挖掘能够为用户推荐信息，从而吸引了很多 w e b 营运商的投资研究。w e b 使用挖掘通过对用户频繁访问模式的关联规则挖掘，计 第2 章w e b 使用挖掘概述w e b 使用挖掘方法的研究与改进 算页面之间的相关性，得出不同用户访问网站的模式。当某用户访问网站时，根据该 用户当前的浏览路径，与挖掘的模式进行比较和匹配，根据匹配程度来排序，并将排 序结果附加在当前用户请求的页面之后，从而自动为该用户预测下一个最有可能访问 的页面，即页面推荐服务。 ( 4 ) 网站结构的改进与优化【2 2 2 3 。w 曲站点结构的合理性将直接关系到用户使用网 站的方便性和网站维护人员的工作量。一个布局合理的网站，用户在较短的时间内就 能方便的找到自己感兴趣的网页；另一个方面，在给出相同信息量的条件下，用户点 击次数较少，能显著的减少网站的负担。w e b 使用挖掘可以通过挖掘页面间的相关性， 向网站设计者提供各种关于网站架构的信息，设计者根据这些反馈的信息可以将一组 频繁访问的页面或者关联性较高的页面直接通过超链接相连，优化了网站的结构。比 如一个出售电子产品的网站，通过w e b 使用挖掘的相关方法分析后得到如下结论：浏 览c o m p a n y p r o d u e t s c o m p u t e r h t m l 的用f a 7 0 都要浏览c o m p a n y p r o d u c t s p r i n t e r h t m l ，并且6 5 的人都会在线下订单。那么显然，应该在销售电脑c o m p a n y p r o d u c t s c o m p u t e r h t m l 页面上提供进入打印机销售c o m p a n y p r o d u c t s p r i n t e r h t m l 页面 的直接超链接。 ( 5 ) 商业智能。随着电子商务的发展，商家希望通过w e b 使用挖掘对用户群体、用 户满意度等用户行为进行分析，从而为用户提供更优质的网上服务。如果能将“购物 篮规则”也用于电子商务，得到网上交易商品之间的相关性，将相关性较高的商品放 在同一个页面上销售，或者两个相关的商品所在的页面间有直接的超链接，将会大大 提高商家的业绩。 2 3w e b 使用挖掘研究现状 随着i n t e m e t 的发展，各大公司、政府部门都有自己的网站，提供w r e b 服务，将数 据挖掘运用于w e b 领域也成为众多科研机构、公司的研究方向之一。w e b 使用挖掘是 w e b 挖掘的一个分支，也是一个热点研究领域，不过目前对该领域内的相关技术和产 品的研究还不成熟，还有很大的发展空间【2 4 】。 m s c h e r t ，h m a n n i l a 等人在9 0 年代末期提出了将数据挖掘运用与w e b 日志领域， 从用户的日志中挖掘出用户的访问行为，经过1 0 年左右的发展，如今在w e b 使用挖掘 1 2 w e b 使用挖掘方法的研究与改进第2 章w e b 使用挖掘概述 上，已经取得初步成果。目前在w e b 使用挖掘中，主要的研究热点集中在几个方面： 日志数据预处理、模式分析算法的研究( 比如关联规则算法、聚类算法) 、网页推荐模 型、网站个性化服务与自适应网站的构建、结果可视化研究等。 m s c h c n 提出最大向前引用路径( m a x i m a lf o r w a r dr e f e r e n c e ) 2 5 1 ，将用户会话分 割到事务层面，在事务的基础上进行用户访问模式的挖掘。s p c e d t r a c e r 2 6 , 就是w a t s o n 实验室采用c h e n 的思想构建的日志挖掘系统，该系统首先重建用户访问路径识别用户 会话，在此基础上进行数据挖掘。 p e r k o w i t z 等人提出自适应网站( a d a p t i v ew 曲s i t e ) t 2 3 】的概念，指出用户理想的网 站是一个自适应的，从网站的主页开始，不同用户在浏览网站时，整个网站的内容像 是专门根据他的兴趣而定制的一样。目前，对网站个性化服务的探索仍然是w e b 使用 挖掘的一个热点研究方向，国外已经出现不少的原型系统。比女1 p a g e g a t h e r 、p e r s o n a l w e b w a t c h e r 、w e b p e r s o n a l i z e r 、w e b s i f t l 2 7 】等。 h a n 等人提出将日志保存为数据立方体( d a t ec u b e ) t 2 l ，然后可以采用o l a p 的相关 方法比如上卷、下钻、切片等处理日志数据，获取用户的访问模式，并构建了 w e b l o g m i n e r 系统，实现对日志数据的分析。该系统首先根据w e b 日志构建数据库， 其次构造数据立方体，然后基于数据立方体进行o l a p 操作，最后进行知识发现。 w u m 6 ，2 8 】是一个被较多人熟知的系统，主要是用于分析用户的浏览行为，并提 出一种类似于s q l 的数据挖掘语言m i n t ，根据用户要求挖掘满足要求的结果，它主 要包括两个模块：聚合服务和m i n t 处理器。聚合服务主要是将采集来的用户日志组 成事务，再将事务转换为序列，而m i n