（计算机应用技术专业论文）web日志挖掘系统中相关算法的研究.pdf

西南交通大学硕士研究生学位论文第l 页 摘要 随着互联网技术的飞速发展，网络正在成为人们进行信息交流和信息处 理的有效平台，各种数字化的信息每天以极高的速度增长，网络上积累了海 量的数据。面对如此巨大的信息量，如何发现自己所需信息，成了困扰网络 用户的一大难题，即所谓的r i c h d a t a p o o r i n f o r m a t i o n 问题。 为了解决上述问题，w e b 挖掘技术应运丽生，其中，面向w e b 服务器曰 志的w e b 目志挖掘技术尤其得到了众多研究人员的关注。利用w e b 臼志挖 掘技术可以发现用户访问站点的浏览模式。 在模式发现中，首先要解决的问题就是w e b 日志的数据预处理。传统的 w e b 臼志数据预处理过程没有消除f r a m e 页面的影响，导致最终挖掘出来的 模式的兴趣度偏低。为此，本文作者提出了f r a m e 页面过滤算法，并把它应 用到w e b 曰志数据预处理过程中。 数据经过预处理后，就可以根据具体的需求来选择诸如聚类、分类、关 联规刚等数据挖掘技术了。本文要实现的目标是：根据用户的浏览行为，发 现相似的用户群；根据w e b 页面被用户访问的情况，发现相关页面组。本文 选择的是聚类技术。首先，对已有的聚类技术进行了简单介绍。然后，详细 分析了一个典型的基于距离的聚类算法，发现该算法在空间和时闻的复杂性 有者难以克服的局限性，为此，文中提出了一种基于矩阵的快速聚类算法一 标记传播算法，用于实现用户和页面的快速聚类。最后，结合一个具体的 实例，对f r a m e 页面过滤算法秘标记传播算法的有效性进行了验证。 关键词：数据挖掘；w e b 日志挖掘：数据预处理；f r a m e 页面过滤算法；关 联矩阵；标记传播算法 西南交通大学硕士研究生学位论文第l | 页 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e m e tt e c h n o l o g y , t h en e t w o r ki sb e c o m i n g a l le f f e c t i v ep l a t f o r mf o rp e o p l et oe x c h a n g ea n d p m c e s si n f o r m a t i o n , a n dd i g i t a l i n f o r m a t i o ni n c r e a s e sd a i l yw i t hh i 业s p e e d t h e r ei sam a s so fi n f o r m a t i o no n i n t e r a c t ，h o wt ol o o kf o ri n f o r m a t i o nt h a ts o m e o n e w a n t si ni n t e m e ti sb e c o m i n ga d i f f i c u l tp r o b l e m , w h i c hi ss o - c a l l e d r i c hd a t ap o o ri n f o r m a t i o n ” i no r d e rt os o l v et h ep r o b l e mm e n t i o n e da b o v e w e bd a t am i n i n ge m e r g e sa s t h et i m e sr e q u i r e t h e r e i n t o t h ew c bl o gm i n i n gt e c h n o l o g yi sp a i dm o l e a t t e n t i o n sb yn u m e r o u sr e s e a r c h e r sc s p e c i a l l yb yu t i l i z i n gw e bl o gm i n i n g , w e c a n g e t t h e b r o w s i n g m o d eo f t h ec u s t o m e r i nt h e p r o c e s so fg e t t i n g t h eb r o w s i n gm o d eo ft h ec u s t o m e r , w e bl o g p r e p r o c e s s i n gi s t h ec h i e fp r o b l e mt ob es o l v e d b u t ，b e c a u s et h et m d i f i o n a l p r o c e s so f w e b t o gp r e p r o c e s s i n gd o e sn o te l i m i n a t et h ei n f l u e n c eo f f l a m e p a g e ， t h ei n t e r e s t i n go f m o d ei sl o w t h u s ，t h ea u t h o rp u t sf o r w a r da na l g o d t h mo f p a g e f i l t e ri nt h i sp a p e r , a n da p p l i e si tt ot h ep h a s eo f w e bl o gp r e p m c e s s i n g a f t e rd a t ap r e p r o c e s s i n g , w ec a ns e l e c to n eo fd a t am i n i n gt e c h n i q u e s ，s u c h a sc l u s t i n g ，c l a s s i f y i n g , o ra s s o c i a t i o nr u l ee t c ，a c c o r d i n gt oc o n c r e t er e q u i r e m e n t s o u ra i mi st of i n dt h es i m i l a ru s 盯g r o u pa c c o r d i n gt ob r o w s i n gb e h a v i o r s ，a n dt o f i n dr e l a t e dp a g eg r o u pa c c o r d i n gt ot h ew e b p a g e sv i s i t e db y t h eu s e r i nt h i s t h e s i s t h ec l u s t i n gi ss e l e c t e da so u rd a t am i n i n gt e c h n o l o g y f i r s t l y , t h i st h e s i s i n t r o d u c e sb r i e f l y c l u s t e r i n gt e c h n i q u e s w h i c ha l ee x i s t e d a f t e ra n a l y z i n ga t y p i c a lc l u s t e r i n ga l g o r i t h m i nd e t a i l ，t h ea u t h o rf i n d si th a st h e d i s a d v a n t a g e i nt h e c o m p l e x i r y o f s p a c ea n dt i m e t h e r e f o r e ，t h ea u t h o rb r i n g sf o r w a r d af a s tc l n s t i n g a l g o r i t h m b a s e do n m a t r i x ，i e ，m a r k e rp r o p a g a t i o na l g o r i t h m t h en e wa l g o r i t h m i su s e dt oa c c o m p e s ht h er a p i dc l u s t i n go fn s e ra n dp a g e f i n a l l y , s o m ed a t ai s u s e dt ov e r i f yt h ev a l i d i t yo fp a g ef i l t e r i n ga l g o r i t h ma n dm a r k e rp r o p a g a t i o n a l g o r i t h m 西南交通大学硕士研究生学位论文第ll i 页 k e y w o r d s ：d a t am i n i n g ；w e b l o gm i n i n g ；d a t ap r e p r o c e s s i n g ； f r a m e - p a g ef i l t e r a l g o r i t h m ；m a r k e rp r o p a g a 6 0 na l g o r i t h m 西南交通大学硕士研究生学位论文篱1 页 1 1 问题的提出 第1 章绪论 2 0 世纪9 0 年代以来，i n i e r n c t 得到了飞速的发展，使得w w w 成为了全 球最大、最方便的信息集散地，积聚了海量的信息，成为人们工作与学习的 最大支持平台。据估计，w e b 已经发展成为了拥有3 亿页面的分布式信息空 间，而且这个数字仍以每4 至6 个月翻番的速度增加。在这些海量的、异 构的w e b 信息资源中，蕴含着具有巨大潜在价值的知识。然而，i n t c m e t 是 一个具有开放性、动态性和异构性的全球分布式网络，资源分布很分散，且 没有统一的管理和结构，这就导致了信息获取的困难，如何从数以亿计的页 面中发现需要的内容，如何合理有效的组织网站的页面链接结构，如何将用 户、网页进行合理聚类【l i 以提供个性化服务耻4 】，如何对使用有限瓷源的用 户实现信息的预取1 2 。，成了困扰网络用户的一大难题，即所谓的r i c hd a t a p o o ri n f o r m a t i o n 问题，这也是人们迫切希望解决的问题。人们迫切需要能够 从w 曲上快速、有效地发现资源和知识的工具，提高在w e b 上检索信息的 效率。 为了解决上述问题w e b 挖掘p 1 3 塘而生，w e b 挖掘源于数据挖掘和 i n t e r a c t 技术的结合，并涉及到计算语言学、信息学等多个领域。w e b 挖掘主 要是研究w e b 文档和w e b 活动，从中抽取感兴趣的潜在的有用模式和隐藏 的信息。w e b 挖掘可以在多个方面发挥作用，如确定权威页面、w e b 文档分 类、w e b 页面聚类、客户聚类、w e b 页面预取、智能查询等 1 4 - 1 9 】。 1 2 研究现状 数据挖掘从2 0 世纪8 0 年代出现以来，有许多关于它的宣传，尤其是许 多人希望数据挖掘能成为一种从数据中挖掘知识的工具，使它能帮助企业经 理制定决策、促进商业竞争，或者傲其他很多有煮义的事情。 目前，数据挖掘方法一般有三种：自顶t ( t o p - d o w n ) 、自下而上 ( b o t t o m u p ) 和混合法。数据挖掘技术和算法主要包括智能超市搜索、决策树、 西南交通大学硕士研究生学位论文第2 页 神经网络、相关分析、遗传算法、模糊逻辑、粗集( t o u g hs e t ) 、概念学2 - ( c o n c e p t l e a r n i n g ) 、归纳逻辑程序和聚类等等。目前使用较多的是关联规则分析、聚 类分析、分类和预测等【1 】i “，这些技术大多应用在生物医学、商业、金融和电 信等方面。 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 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 e b 挖掘的一个主要方向，它是通过分析w e b 服务 器的日志文件，以发现用户访问站点的浏览模式，为站点管理员提供各种利 于站点改进或可以带来经济效益的信息( 如：聚类分析可以把具有相似特征的 用户或数据项归类来帮助进行市场决策) 。w e b 服务器日志也可以结合其它数 据库( 如：电子商务、银行数据库) 一同进行挖掘，以获得更详细的信息。w e b 岛志挖掘能带来许多方面的好处：分析网站流量模式、发现系统性能瓶颈、 测定广告和促销计划的成功度及测定投资回报率、发现用户的需要和兴趣等。 迄今为比，基于w e b 日志的数据挖掘方法主要有两大类：一类c h e r t 2 0 1 等人提出的基于w e b 事务的方法，即将数据挖掘技术应用于w e b 服务器吕 志，以期发现用户浏览模式。c h e n 提如了最大前向引用序列m f r 2 0 的概念， 西南交通大学硕士研究生学位论文第3 页 并用它将用户会话分割成一系列的事务，然后采用与关联规则相似的方法挖 掘频繁浏览路径。 第二类方法是h 斟刈等人提出的基于数据立方体的方法，即根据w e b 门 志建立数据立方体，然后对数据立方体进行数据挖掘和o l a p 捌。 除了上面提到的基于w e b 日志的数据挖掘研究外，目前各种信息检索： 具的研制也是i n t e m e t w w w 信息检索与数据挖掘研究的重点。在1 9 9 9 年程 开的d a s f a a 9 9 会议上，日本学者提交了w e b 文档交互分类方顽的文章， 提出了利用自组织映射和搜索引擎，通过w e b 与数据库、人工智能的集成进 行w e b 文档分类的方法。而w e b 文本挖掘中的协同式方法同样是比较新颖 的方法。 与国外相比，国内对d 凇d 的研究稍晚，没有形成整体力量。1 9 9 3 年国 家自然科学基金首次支持对该领域的研究项目。目前，国内的许多科研单位 和高等院校竞相开展知识发现的基础理论及其应用研究，这些单位包括清华 大学、中科院计算技术研究所、空军第三研究所、海军装备论证中心等。其 中，北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研 究，北京大学也在开展对数据立方体代数的研究，华中理工大学、复旦大学、 浙江大学、中国科技大学、中科院数学研究所、吉林大学等单位开展了对关 联规则开采算法的优化和改造；南京大学、四川大学和上海交通大学等单位 探讨、研究了非结构化数据的知识发现 6 l 以及w e b 数据挖掘。 当前，该领域的研究多应用于推荐系统，提供个性化网站，动态自适应网 站的建造等。w e b 挖掘是一项综合技术，涉及w e b 、数据挖掘、计算语言学、 信息学等多个领域。不同研究者从自身的领域出发，对w e b 挖掘的含义有着 不同的理解，项目开发也各有其侧重点。 w e b 挖掘是一种技术。和其他技术一样，w e b 挖掘也需要时间和精力来 研究、开发、和逐步成熟，最终被人们接受。目前已经有了很多通用的w e b 挖掘系统，如d b m i n i e r 、w u m 等，但是还不能达到期望的智能系统那样。 在近来的w e b 挖掘研究和开发中，随着m i c m s o t l 、o r a c l e 、m m 等国际大公 司的介入，w e b 挖掘受到越来越多的关注，一些问题得到解决，而另一些尚 处于研究阶段，然而，这些尚处于研究阶段的问题必将刺激人们进行进一步 的研究和探索。 西南交通大学硕士研究生学位论文第4 页 1 3 论文研究的主要内容 首先，介绍了国际上w e b 挖掘技术研究现状，总结了w e b 挖掘的内容、 任务、分类及其与传统的数据挖掘的异同点，并对w e b 日志挖掘中所涉及到 的预处理技术进行了较全为面的阐述，特别是对w 曲日志挖掘系统中所涉及 到的一些预处理技术的性能以及优缺点进行了分析，提出了一种旨在提高数 据质量的算法_ f r 锄e 页面过滤算法。 接着，对已有的聚类技术进行了简单介绍，并详细分析了一个典型的基 于距离的聚类算法，发现该算法在空间和时间的复杂性有着难以克服的局限 性，为此，文中提出了一种基于矩阵的快速聚类算法标记传播算法，用 于实现用户和页面的快速聚粪。 然后，结合一个具体的实例，对f r a m e 页面过滤算法和标记传播算法的 有效性进行了验证。 最后，本文通过对上述实现技术的阐述及对实验结果的分析，提出了一 些关于w e b 挖掘系统研究的见解，并对今后的研究工作进行了展望。 1 4 论文结构安排 本论文的后续章节的内容安排如下： 第二章：主要介绍本论文所涉及到的基础知识，包括数据挖掘和w e b 挖 掘的定义、w e b 挖掘的分类、w e b 日志挖掘相关技术和基于w e b 臼志的数据 挖掘系统。 第三章：主要介绍数据预处理技术尤其是基于w e b 日志的数据数据预 处理技术；还给出了基于w e b 日志的数据预处理过程，并对预处理过程中所 涉及到的技术进行了简单介绍 第四章：首先介绍了框架式结构的页面f 2 ”越，并分析了该稀结构的页面 在w e b 曰志挖掘中可能会引起的一些问题；接着，提出了旨在消除f r a m e 页面不良影嗨的算法f f a m e 页面过滤算法，并给出了算法描述；最后， 还对算法的性能进行了简单地分析。 第五章：首先，对已有的聚类技术进行了简单介绍；接着，详细分析了 一个典型的基于距离的聚类算法，发现该算法在空间和时间的复杂性有着赡 以克服的局限性，为此，文中提出了一种基于矩阵的快速聚类算法标记 西南交通大学硕士研究生学位论文第5 页 传播算法，用于实现用户和页面的快速聚类；最后，对该算法进行了性能分 析。 第六章：通过一个实例介绍了f r a m e 页面过滤算法和标记传播算法的具 体应用。 最后，对本论文所做工作进行了总结，并对未来的工作进行了展望。 西南交通大学硕士研究生学位论文第6 页 第2 章相关知识基础 本章主要介绍了数据挖掘技术的知识基础，特别是基于w e b 日志的数据 挖掘技术的知识基础，并给出了基子w 曲日志数据挖掘系统的体系结构以及 各组成模块的功能和各自的特征。 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累 的数据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对 其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以 高效地实现数据的录入、查询、统计等功能，但无法发现数据间存在的关系 和规则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏 的知识的手段，导致了“数据爆炸但知识贫乏”的现象。 如何理解已有的历史数据并用于预测未来的行为，如何从浩如烟海的数 据中发现隐藏的有用知识，导致了知识发现和数据挖掘研究领域的出现。知 识发现和数据挖掘是集统计学、人工智能、模式识别、并行计算、机器学习、 数据库等技术 1 】 2 6 】的一个交叉性的研究课题、是近年来一个十分活跃的研 究领域。 2 1 数据挖掘和w 曲挖掘 2 1 1 k i ) d 和数据挖掘 k d d 即数据库知识发现，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 的缩写。这 一术语首先出现在1 9 8 9 年在美国底特律召开的第1 1 届国际人工智能联合会 议的专题讨论会上，1 9 9 1 、1 9 9 3 和1 9 9 4 年又接着继续举行k d d 专题讨论会。 t 9 9 5 年在舅口拿大召开了第一属知识发现和数据挖掘国际学术会议。从1 9 9 7 年开始，k d d 已经拥有了专门的杂志k n o w l e d g ed i s c o v e r ya n dd a t a m i n i n g ) ) 。国外在这方面发表了众多的研究成果和论文，并且开发了一大批数 据挖掘软件( h t t p ：w w w k d n u g g e t s c o r n ) ，对数据挖掘的研究已成为计算机领域 的一个热门课题。 许多学者认为数据挖掘和k d d 是等价的概念，人工智能领域习惯称为 k d d ，而数据库领域习惯称呼为数据挖掘；也有学者把k d d 看作是发现知 西南交通大学硕士研究生学位论文第7 页 识的完整过程，而将数据挖掘视为其中的一个基本步骤。图2 1 示意了知识 发现的主要过程。 知识发现的过程主要由以下几个步骤组成： 数据清理( 消除噪声或不一致数据) ； 数据集成( 多种数据源可以组合在一起) ： 数据选择( 从数据库中检索与分析任务相关的数据) ； 数据变换( 数据变换或统一成适合挖掘的形式) ； 数据挖掘( 基本步骤，使用智能方法提取模式) ； 模式评估( 根据某种兴趣度度量，识别表示知识的真正有趣的模式) ： 知识表示( 使用可视化或其它表示技术，向用户提供挖掘的知识) 。 我们可以将前4 个步骤统称为数据预处理过程( d a 乜p r e p m e e s s i o n ) 州。 原始曰志文件用户会话文件规则、模式感兴趣的模式、规则 圈2 - 1知识发现过程 由于在产业界、媒体和数据库领域中，数据挖掘的叫法更为流行，因此， 本文采用数据挖掘表示数据库中的知识发现过程。u f a y y a d 1 4 等对数据挖掘 的定义是：从数据集中识别出有效的、新颖的、潜在有用的、并且最终可理 解的模式的a # 平凡过程。定义中，涉及到几个需要进步解释的概念： 过程：包含多个阶段，涉及到数据准备、模式搜索、知识评价、以 及反复的修改求精。 非平凡的( n o n l r i v i a l ) ：意思是要有一定程度的智能性和自动性。 有效性：是指发现的模式对于新的数据仍保持有一定的可信度。 新颖性：要求发现的模式应该是新的，从前未知的。 潜在有用性( p o t e n t i a n yu s e f u l ) ：是指发现的知识将来有实际效用。 最终可理解1 洼( u l t i m a t e l yu n d e r s t a n d a b l e ) ：指发现的模式能被用户理 解，目前它主要是体现在简洁性上。 有效性、新颖性、潜在有用性和最终可理解性综合在一起可称之为兴趣 性( i n t e r e s t i n g n e s s ) ，具体可参见文献l i 。 西南交通大学硕士研究生学位论文第8 页 2 1 2w e b 挖掘的定义及意义。 2 121w e b 挖掘的定义 w e b 挖掘是从数据挖掘发展而来，因此其定义与我们熟知的数据挖掘定 义相类似。w e b 挖掘是指从大量的w e b 文档的集合c 中发现隐含的模式p 。 如果将c 看作输入，将p 看作输出，那么w e b 挖掘的过程就是从输入到输 出的一个映射掣：c p 。 然而，w e b 挖掘与传统的数据挖掘相比又有许多独特之处。首先，两者 挖掘对象不同：前者的挖掘对象是海量、异构、分布式的w e b 文档和w 曲 服务器日志，而后者的挖掘对象是数据库。其次，两者使用的挖掘技术有所 不同，因为w e b 在逻辑上是一个由文档节点和超链接构成的图，并且w e b 文档本身是半结构化或无结构的，缺乏机器可理解的语义，而传统的数据挖 掘技术针对的是局限于数据库中的结构化数据，并利用关系表格等存储结构 来挖掘知识，因此一些传统的数据挖掘技术并不适合于w e b 挖掘，即使可用 也需要建立在对w e b 文档进行预处理的基础之上。 w w w 目前是一个巨大、分布广泛、全球性的信息服务中心，它涉及新 闻、广告、消费信息、金融管理、教育、政府、电子商务和许多其它信息服 务。w e b 还包含了丰富和动态的超链接信息以及w 曲页璇的访问和使用信 息，这为数据挖掘提供了丰富的资源。然而从下面的分析可以看出，对w e b 进行有效的资源和知识发现具有极大挑战。 对于一些原来有效的数据挖掘技术而言，w e b 似乎太庞大了。而且 w e b 的数据薰目前仍以可怕的速度快速增长。这使得几乎不可能去 构造一个数据库或数据仓库对w 曲上的所有数据进行复制、存储或 集成。 w e b 页面的复杂性商于任何传统的文本文档。因为w e b 页面缺乏统 一的结构，它包含了远比任何一组书籍或其它文本文档多得多的风 格和内容。 w e b 是一个动态性极强的信息源。w e b 不仅以极快地速度增长，且 其信息还在不断地发生着更新，如：新闻、股票市场等；链接信息 和访问记录也在频繁地更新之中。 西南交通大学硕士研究生学位论文第9 页 w e b 面对的是个广泛的形形色色的用户群体。w e b 的用户群仍在 快速地扩张中，并且各个用户具有不同的背景、兴趣和使用目的。 w e b 上的信息对用户而言，只有很小的一部分是相关的或有用的： 据说9 9 的w e b 信息对于9 9 的用户是无用的。 这些挑战推动了如何有效且高效地发现和利用因特网上资源的研究：亡 作。因此w e b 挖掘也就成为数据挖掘领域个新的研究方向。 2 1 2 2w e b 挖掘的意义 信息时代，无法获取信息的人们将会被时代所抛弃。i n t e m e t 时代，问题 已经不是无法获得信息，而是无法把握隐藏在信息背后的更深层次的信息， 如何从海量的文本及多媒体数据或用户访问信息中发现有用的知识更是突破 了人类的极限。w e b 数据挖掘为解决这个问题指出了条道路。数据挖掘在 传统的结构化的事务数据挖掘领域，己经取得了比较成功的应用。然而，w e b 上的信息不同于数据库，数据库有规范的数据结构，而w e b 上的数据包括文 本、图片、v e d i o 等多种信息，它们很多是半结构化的甚至是无结构化的。 因此，在w e b 上进行数据挖掘可能需要用到很多非常规的数据挖掘技术。 现实生活中存在的数据多是半结构化的、异源的数据，w e b 挖掘的研究 也必将极大的推动数据挖掘在其它领域的应用。 w e b 内容挖掘提供了自动的文档分类与聚类功能，基于内容挖掘的智能 搜索代理可以给人们提供更好的信息服务。而w e b 使用模式的挖掘，能够辅 助改进分布式网络的设计性能，如在高度相关的站点间提供快速有效的访问 通道能帮助更好的组织w 曲页面；帮助改善市场营销策略。 特别要指出的是，w e b 挖掘技术从一开始就是面向应用的。它不仅是面 向特定数据源的简单检索查询调用，而且要对这些无结构的、异源的数据进 行微观、中观乃至宏观的清洗、集成、统计、分析、综合和推理，以指导实 际问题的求解，企图发现用户间、页面间的相互关联，甚至利用已有的数据 对用户未来的活动进行预测。因此，w e b 挖掘被信息产业界认为是最有前途 的交叉学科。 西南交通大学硕士研究生学位论文第1 0 页 2 1 3w e b 挖掘分类 w e b 上的数据主要包括： w 曲页面：包含文本和多媒体信息( 包括图像、语音、图片) ，现有的 w e b 挖掘方法大都是针对w 曲页面开展的。 服务器日志数据：浏览w e b 服务器时，产生三种类型的臼志文件s e r v e r l o g s ，c l i e n t l o g s 和p r o x y l o g s ，用于记录用户访问的基本情况。 w e b 页面、超链接关系：描述了文档之间的联系，同时为用户浏览 w e b 站点提供了可用的路径。 在线市场数据：这是传统的关系数据库结构数据，如客户登记信息等， 存储电子商务信息。将它们和访问日志集成，有助于更好地提高w e b 挖掘的 质量。 般地，根据w e b 挖掘的数据对象将w e b 挖掘分为三类f 6 】：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 b u s a g e m i n i n g ) 如图2 2 所示，其中，w e b 内容挖掘和w e b 使用记录挖掘是w e b 挖掘的两个主要方面。 图2 - 2w e b 挖掘的分类 w e b 内容挖掘 w e b 内容挖掘【6 l 是从文档内容或其描述中抽取知识的过程，分为两类： 对文本文档( 包括t e x t ，h t m l 等格式) 和对多媒体文档( 包括i m a g e ，a u d i o ， v i d e o 等媒体类型) 的挖掘。w e b 挖掘可以对w e b 上大量文档集合的内容进 行摘要、分类、聚类、关联分析，以及利用w e b 文档进行趋势预测等。文本 摘要是指从文档中抽取关键信息，用简洁的形式对文档内容进行摘要或解释。 这样，用户不需要测览全文就可以了解文档或文档集合的总体内容。文本摘 要在有些场合有用，例如，搜索引擎在向用户返回查询结果时，通常需要给 西南交通大学硕士研究生学位论文第1 1 页 出文档的摘夏。目前，绝大部分搜索弓；擎采用的方法是简单的截取文档的前 几行。 文本分类是指按照预先定义好的主题类别，为文档集合中的每个文档确 定一个类别。这样，用户不但能够方便地浏览文档，而且可以通过限制搜索 范围来使文档的查找更为容易。目前，y a h o o ! 通过人工来对w e b 上的文档进 行分类，这大大影响了索引的页面数目( y a h o o ! 索引的覆盖范围远远小二f a l t a - v i s t a 等搜索引擎) 。利用文本分类技术可以对大量文档进行快速、有效的 自动分类。目翦，文本分类的算法有很多种，比较常用的有t f i d f 和n a i v e b a y e s 等方法。 文本聚类与分类的不同之处在于，聚类没有预先定义好的主题类别，它 的目标是将文档集分成若干类，要求同一文档内文档内容的相似度尽可能大， 雨不同类间的相似度尽可能地小。h e a r s t 等人的研究己经证明了“聚类假设”， 即与用户查询相关的文档通常会聚类的比较靠近，而远离与用户查询不相关 的文档。我们可以利用文本浆类技术将搜索引擎的检索结果划分为若干个类， 用户只需要考虑那些相关的类，大大缩小了所需要的浏览结果数量。目前有 多种文本聚类算法，大致可以分为两种类型：以g h a c 等算法为代表的层 次凝聚法，以k - m e a n s 等算法为代表的平面得分法。 关联分析是指从文档集合中找出不同词语之间的关系。b 啦提出了一种 从大量文档中发现一对词语出现模式的算法，并用来在w e b 上寻找作者和书 名的出现模式，从而发现了数千本在a m a z o n 网站上找不到的新书籍。w a n g 等人以w e b 上的电影介绍作为测试文档，通过使用o e m 模型从这些半结构 化的页面中抽取词语项，进而得到些关于电影名称、导演、编剧的出现模 式。 分布分析与趋势预测是指通过对w e b 文档的分析，得到特定数据在某个 历史时刻的情况或将来的取值趋势。f e l d m a n 等人使用多种分析模式对路透 社的两万多篇新闻进行了挖掘，得到主题、国家、织织、人、股票交易之间 的相对分布，揭示了一些有趣的趋势。w v t h r i c h 等人通过分析w e b 上出版的 权威性经济文章，对每天的股票市场指数进行预测，取得了良好效果。 对w e b 页面内多媒体信息的挖掘，是先应用多媒体特征抽取工具，形成 特征二维表，然后可以采用传统的数据挖掘方法进行挖掘。 在特征提取阶段，利用多媒体信息提取工具进行特征提取。抽到出 西南交通大学硕士研究生学位论文第1 2 页 i m a g e 、v i d e o 的文件名，u r l ，父u r l ，类型，键值表，颜色向量等。对这 些特征可进行挖掘操作，如分类，根据提供的某种类标，针对特征集，利用 决策树可以进行分类。 w e b 结构挖掘峰1 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 e b 挖掘而言是可以利用的一种重要资 源。 w e b 结构挖掘是从w e b 的链接关系和组织结构中推导知识，目的是发现 页面的结构和w e b 的结构，在此基础上对页面进行分类和聚类从而找至i 权威 页面。常用的方法有p a g e - r a n k 方法和h u b a u t h o r i t y 方法。 q v a g e r a n k 方、法【2 7 人们搜索某一主题的w e b 页面时，除了要求内容相关，更加期望检索到 的页面具有较高的质量和权威性。 权威性可由w e b 页面链接来反映。超链接包含了大量人类潜在的语义， 有助于自动分析出权威性语义。当一个w e b 页面的作者建立指向另一个页面 的链接时，可以看作是作者对另一页面的注解，把对一个页面的来自不同作 者的注解收集起来，就可以用来反映该页面的重要性，并可以很自然地用于 权威w e b 页面的发现。 p a g e r a n k 方法的基本思想是：一个页面被多次引用，则这个页面很可 能是重要的；一个页西尽管没有被多次引用，但被一个重要页面引用，受日这 个页面很可能是重要的。一个页面的重要性被均分并被传递到它所引用的页 面。 ( 萤h u b a u t h o r i t y 方法【2 7 1 考虑到w e b 链接结构的特殊特征，不是每个超链接都具有注解性，有 些是为其它目的创建的，如为了导航或为了付费广告。另外，基于商业或竞 争的考虑，很少有w e b 页面会指向其竞争领域的权威页面。 西南交通大学硕士研究生学位论文第1 3 页 由于w e b 链接结构存在这些局限性，人们提出了h u b 页面。一个h u b 页 面是指一个或多个w e b 页面，它提供了指向权威页面的链接集合。h u b 页面 本身可能并不突出，可能没有几个链接指向它们，但却提供了指向就某个主 题而言最为突出的站点链接。h u b 页面起到了隐含说明某主题权威页面的作 用，可以是主页上的推荐链接列表，例如一门课程主页上的推荐参考文献站 点。 通常好的h u b 是指向许多好的权威的页面，好的权威页面是指由许多 好的h u b 所指向的页面。这种h u b 与a u t h o r i t y 之间的相互作用，可用于权威 页面的挖掘和高质量w e b 结构和资源的发现。这就是h u b a u t h o r i t y 方法的基 本思想。 w e b 使用记录挖掘【6 】 w e b 使用记录挖掘通过挖掘w e b 日志记录来发现用户访问w e b 页面的 模式。通过分析和探究w e b 日志记录中的规律，可以识别电子商务中潜在客 户，增强对最终用户的因特网信息服务的质景和交付，并改进w e b 服务器系 统的性能和结构。目前研究较多的w 曲使用记录挖掘技术和工具可分为两 类：模式发现和模式分析。 w e b 使用记录中的模式发现 用户访问模式的发现采用了来自人工智能、数据挖掘、信息论等领域的 成熟技术，从w e b 使用记录中挖掘知识。僵在新的环境中，有许多新的问题 需要考虑和研究。 在模式发现中，首先要解决的问题就是数据的预处理，它主要包括如下 两个部分：数据清洗( a a t ad e m i n g ) 包括无关记录的剔除、判断是否有重要的 访问没有电录、用户的识别；事务识别( t r a n s a c t i o n i d e n t i f i c a t i o n ) 是指将页面访 问序列划分为代表w e b 事务或用户会话的逻辑单元。 在对事务进行了划分之后，就可以根据具体的需求选择访问模式发现的 技术，如路径分析、关联规则挖掘、时序模式、聚类和分类技术。路径分析 ( p a t ha n a l y s i s ) 可以用来发现w e b 站点中最经常被访问的路径，从而帮助管理 员调整站点的结构。在w e b 使用记录挖掘的环境下，关联规受h 挖掘的目标是 发现用户对站点各页面的访问之间的关系，这对于电予商务是非常有用的。 各种聚类和分类技术的采用对于w e b 使用记录中的模式发现都有其各自的 作用。 西南交通大学硕士研究生学位论文第1 4 页 模式分析 如果没有合适的技术和工具来帮助分析人员进手亍理解，采用各萃申技术挖 掘出来的模式将不能得到很好的利用。所以开发各种分析技术和工具也是非 常必要的。目前这个领域的工作还不是很多，是一个较新的领域。 可视化技术在其它领域中的应用己取得了巨大的成功，因此对于理解 w e b 用户行为模式来讲也是一个自然的选择。p i t k o w 等人己经开发了w e b w i z 系统来将w w w 的访问模式可视化。此外联机分析处n ( o l a p ) 技术也可以 应用到模式分析中。 由于w e bl o g 可以提供很多关于w e b 的信息，通过对日志文件的多维分 析，可以提供各种各样的统计报告，完成日常管理工作，发现潜在的客户和 市场等。计划挖掘( p l a nm i n i n g ) 挖掘通常的存取规律，可以用于调整w e b 链 接、改善性能；相关，序列存取模式分析，可以对服务器的缓存、预取和交换 参数进行调整趋势分析，可以了解w 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 服务器日志也可以结合其它数据库( 如：电子商务、银行数据库) 一 同进行挖掘，以获得更详细的信息。w 曲日志挖掘能带来许多方面的好处： 分析网站流量模式；发现系统性能瓶颈；测定广告和促销计划的成功度及测 定投资鄹报率；发现用户的需要和兴趣等。 2 3 基于w e b 日志的数据挖掘系统 面向w e b 曰志的数据挖掘系统主要由三个模块组成：创建，更新模式库 模块，实时智能推荐模块和管理员指导模块。创建更新模式库模块的任务是 利用w e b 日志挖掘算法从w e b _ 日志发现用户的浏览模式，并对用户行为模 西南交通大学硕士研究生学位论文第1 5 页 式库进行更新和维护。 实时推荐模块则是根据当前用户的浏览行为以及模式库中保存的模式， 实时并且智能地为用户推荐可能感兴趣的内容。 管理员指导模块则是辅助站点维护人员优化网站的结构，修改站点不台 理之处，方便用户的使用，最终提高网站的用户数。基于w e b 日志的数据挖 掘系统的体系结构如图2 _ 3 所示。 图2 - 3基于w e b 日志的数据挖掘系统的体系结构 基于w e b 日志的数据挖掘系统首先利用w e b 站点的访问日志、w e b 文 档、站点结构以及w e b 站点的其它可以利用的数据源，如用户注册数据库和 电子商务数据库等。经过数据预处理阶段将这些数据集成到一起产生用户会 话文件，对用户会话文件应用w e b 日志挖掘算法，如聚类、关联分析和序列 模式，从中获取用户的访问模式，如用户聚类、页面聚类、频繁访问页组、 频繁访问路径等，这些用户访问模式被保存在模式库中。假如在挖掘用户浏 览模式的过程中发现选择的数据或属性有偏差，或者使用的挖掘技术产生不 西南交通大学硕士研究生学位论文第1 6 页 了预期的结果，这时就需要根据反馈结果，不断重复先前的过程，甚至重新 开始。所以建立用户访问模式库是一个循环往复的过程，并且需要要领域号 家参与。基于w e b 日志的数据挖掘系统的模式创建更新模块完成了用户访问 模式库的创建和更新工作。 如何利用模式库中的用户访问模式，为用户提供更好的服务就是实时智 能推荐模块的任务。实对智能推荐模块裉据当前用户的访问情况，从模式库 中搜索与当前用户浏览行为匹配的模式，根据匹配的结果动态地生成为用户 推荐的页面集合，集合中的页面是用户可能感兴趣并且尚未访问过的新页面， 然后将推荐页面集合与用户请求的页面集成在起，同返回给用户。 因为这三个模块的不同特征，其运行方式也不尽相同。创建厦新模式库 模块对于系统来说开销非常大，也是非常耗时的一个任务，并且模式库的必 须在运行实时推荐模块之前创建，旦建立了模式库、并不需要对它进行实 时更新，可以