（计算机应用技术专业论文）基于关联规则的web日志挖掘研究与应用.pdf

硕士论文 基于关联规则的w e b 日志挖掘研究与应用 摘要 本文从理论、算法和应用三个层次研究了关联规则算法在w e b 日志挖掘中的应用。 首先系统、全面地分析和论述了数据挖掘技术以及w e b 挖掘技术，着重研究了w e b 日志挖掘过程中各环节的关键技术，特别是w 曲日志挖掘的数据预处理过程。 其次，对关联规则挖掘的定义、性质、挖掘过程、挖掘算法以及研究现状进行了综 述，对关联规则经典算法中的a p r i o r i 算法进行了深入研究与分析，针对其需要反复扫 描事务数据库，造成大量i 0 开销，影响关联规则挖掘效率这一不足之处，提出了新的 改进算法i m pa p算法，主要思想为：基于在实际关联规则挖掘中，项的数目远小 r i o r i 于事务数目这一事实，提出将事务数据库转换成项数据库，项数据库以项为索引，其记 录是涉及该项的事务的集合，之后挖掘就直接在项数据库上进行。针对a p r i o r i 算法和 i m p算法，开发出两个测试程序，对同样的数据集在相同支持度和置信度条件apriori 下，两种算法各自挖掘的时间进行比较，从而验证了算法改进的可行性。 最后，在对w e b 日志挖掘理论和算法研究的基础上，设计和实现了w e b 访问日志 挖掘系统，并将该挖掘系统应用于学院网络中心的“招生信息网 上，对w e b 服务器 的日志记录进行了挖掘实验，找出用户的频繁访问路径，得到较为理想的结果。 关键词：w e b 日志挖掘，关联规则，a p r i o r i 算法，频繁访问路径 a b s w a e t 硕士论文 a b s t r a c t t h i st h e s i sa i m st od i s c u s st h et h e o r y , a l g o r i t h m sa n da p p l i c a t i o n so fw e bl o gm i n i n gb a s e d o na s s o c i a t i o nr u l e f i r s t l y , t h i sp a p e ra n a l y z e sd a t am i n i n ga n dw e bm i n i n gr o u n d l ya n dp u t se m p h a s e so nt h e k e yt e c h n i q u ei np r e p r o c e s s i n go fw e bl o gm i n i n g ，e s p e c i a l l yi n t r o d u c e st h ed a t ap r e t r e a t m e n t p r o c e s so fw e bl o gm i n i n g s e c o n d l y , w ed oas u m m a r yt od e f i n i t i o n 、p r o p e r t y 、m i n i n gp r o c e s s 、m i n i n ga l g o r i t h m sa n d p r e s e n tr e s e a r c ho fa s s o c i a t i o nr u l e sm i n i n g ，a n dt h e na n a l y z e st h ec l a s s i c a lc h a r a c t e ro f a p r i o r ia l g o r i t h m ，f i n d i n go u tt h ed i s a d v a n t a g eo ft h ea l g o r i t h m ：t h i sa l g o r i t h ms h o u l ds c a n t h ew h o l et r a n s a c t i o nd a t a b a s em a n yt i m e s ，w h i c hh a v em u c hi oo v e r h e a da n dc a l l ta c h i e v e s i g n i f i c a n ti m p r o v e m e n to fe f f i c i e n c y a n di n t r o d u c e so n ei m p r o v e da l g o r i t h m si m p _ a p r i o r i b a s e do ni t ，t h em a i ni d e ai s ：i nt h ef a c to fa s s o c i a t o nr u l e sm i n i n g ，t h en u m b e ro fi t e m si sf a r l e s st h a nt h en u m b e ro ft r a n s a c t i o n s ，c h a n g et h et r a n s a c t i o nd a t a b a s ei n t oi t e md a t a b a s e ，i n w h i c ht h ei t e mi sr e g a r d e da si n d e xk e y ，i t sr e c o r di st h ec o l l e c t i o no ft r a n s a c t i o n st h a t i n c l u d e st h ei t e m ，t h e nt h em i n i n gp e r f o r m sd i r e c t l yi nt h ei t e md a t a b a s e f i n a l l yd e v e l o p e d d o t e s tp r o c e d u r e sb a s e do na p r i o r ia l g o r i t h ma n di m p _ a p r i o r ia l g o r i t h m ，t h r o u g ht h es a m e d a t as e t si nt h es a l t l es u p p o r ta n dc o n f i d e n c el e v e lu n d e rt h ec o n d i t i o n so ft h et w oa l g o r i t h m s o ft h e i rt i m ed i g g i n gi no r d e rt ov e r i f yt h ef e a s i b i l i t yo fi m p r o v i n gt h ea l g o r i t h m f i n a l l y , b a s e do nt h ew e bl o gm i n i n gt h e o r ya n da l g o r i t h m , d e s i g nas y s t e mo fw e bl o g m i n i n g ，a n dp u t i ti nu s eo fa n a l y z i n gt h ew e bl o go f ”e n r o l l m e n ti n f o r m a t i o n n e t w o r k , w h i c hi si nt h en e t w o r kc e n t e r ，f i n do u tt h eh e r s f r e q u e n ta c c e s sp a t t e r n s ，r e t r i e v e t h ed a t aa sf o rt h ee v i d e n c eo f 血en e x tw o r k s k e y w 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 s ，a p r i o r ia l g o r i t h m ，f r e q u e n ta c c e s sp a t t e r n s 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 多1 蝴佣 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 多一夕锈月堋 硕士论文基于关联规则的w e b 日志挖掘研究与应用 1 绪论 1 1 研究背景及意义 伴随着信息技术的发展，i n t e m e t 已经和我们的生活密不可分。w e b 为人们提供了 越来越多的信息，而人们面对太多的信息却无法选择和消化，不知道如何更有效地发现 自己所需的信息资源。从海量的信息中找出大家都看得懂、有价值的知识和信息是目前 面临最紧要的问题之一。w e b 挖掘技术就是解决这个问题的途径之一，即利用数据挖掘 的原则和思想，针对w e b 信息的特性，对传统的挖掘方法进行扩展和改进，将其应用 到w e b 信息上进行挖掘，从而得出有用的知识。 在w e b 数据挖掘领域中，w e b 日志挖掘技术对于w e b 网站的结构优化和w 曲页面 内容重组都起到了重要作用，通过对w e b 日志挖掘可以找出浏览者的偏好路径，得到 用户的访问模式，从而改进站点结构，使得网站的维护人员可以对站点进行有针对性的 改进，以吸引更多的客户、开展个性化服务和构建智能w e b 站点等，因此对w e b 站点 日志进行挖掘有着及其现实的意义。 1 2 国内外研究现状 目前，国内外基于w e b 日志挖掘的研究工作大致可以分为3 类【l 】： ( 1 ) 以w e b 站点设计的改进为目标：通过挖掘用户聚类和用户的频繁访问路径，重 新构建站点页面之间的链接关系，使得网站更适应用户的访问习惯，同时为用户提供个 性化的信息服务。 ( 2 ) 以理解用户意图为目标：z a i a n e 2 】等人使用的数据立方体方法，以及c h e n m i n g - s y a n 3 等人提出的路径遍历模式( p a mt r a v e r s a lp a t t e r n ) 的发现算法，便是此类的典 型代表。 ( 3 ) 以w e b 站点性能分析为目标：主要从统计学的角度出发，对日志数据项进行统 计，得到用户频繁访问页、单位时间访问数、访问数量随时间分布图等。绝大多数商用 及开源的w e b 日志分析工具均属此类。 1 2 1 国外研究现状 近几年，国外学者、科研院所和商业机构非常关注w e b 日志挖掘的理论研究及其 应用开发。 c h e r tm i n g - s y a n 等人首先将数据挖掘技术应用于w e b 服务器日志挖掘，用于发现 用户的访问模式。提出最大向前引用( m a x i m a lf o r w a r dr e f e r e n c e 。m f r ) 系列的概念，即 将用户会话分割成一系列的事务，然后采用与关联规则类似的方法挖掘频繁访问路径。 1 1 绪论硕士论文 s h a h a b ic 【4 】等人提出的w 曲日志挖掘系统依赖于客户端的数据收集，客户端的代 理为服务器返回用户所请求的页面及时间等相关数据。 s p i l i o p o u l o um 和f a u l s t i c hlc 【5 】提出了一套类似s q l 的挖掘语言m i n t ，允许用 户人为指定感兴趣的频繁路径的特征，然后根据用户的需求挖掘满足条件的结果。z a i a n e 0r 等人将w 曲服务器日志保存为数据立方体( d a t ac u b e ) ，然后在其上执行在线数据 分析处理( o l a p ) 的各种操作，如提升、钻取等，用于发现用户的访问模式。 b u c h n e rag 和m u l v e n n amd 【6 j 等人提出将数据挖掘技术应用于电子商务的环境 下，以发现市场智能。挖掘的对象不仅包括日志、w e b 页面，也包括市场数据，并且 给出了在电子商务环境下挖掘的一个总框架。 m i n n e s o t a 大学的w e bm i n e r 系统提出一种w e b 使用挖掘的体系结构，其挖掘思路 是通过对w e b 站点的日志进行处理，将数据组织成传统的数据挖掘方法能够处理的事 务数据形式，然后利用传统的数据挖掘方法进行处理，从而使得该系统能够自动从w e b 日志中发现关联规则和序列模式等。 m m 公司的w e b 使用挖掘和分析工具s p e e d t r a c e r ，通过在用户会话上应用数据挖 掘，从而能够发现频繁访问页面组( 其中的页面经常被一起访问，但未必位于同一条遍 历路径上) 和频繁遍历路径。 n e t p e r c e o t i o n 公司的n e t p e r c c o t i o n s ，采用了一个叫做实时建议的技术：让它的产 品对象( 主要是网站) 能够根据用户以往的浏览行为，在其他用户访问时找出与他相类似 的浏览行为，根据这些用户的浏览行为来预测该用户以后的浏览行为，从而为用户提供 个性化的浏览建议。这种技术利用了网站用户浏览行为相似性的一面，因此其预言有较 高的准确性。 1 2 2 国内研究现状 目前，国内的许多科研单位和高等院校也竞相开展w e b 日志挖掘的基础理论及其 应用研究。其中中科院计算机技术研究所、北京大学等对w e b 内容挖掘进行了较为深 入的研究；西安交大、复旦大学等高校对w e b 访问信息挖掘进行了大量研究；南京大 学和上海交大等单位探讨、研究了用户访问站点的路径访问模式等。 陈新中、李岩、杨炳儒等人【7 】概述了w e b 挖掘的概念、分类及其主要应用领域，详 细介绍了w e b 日志挖掘的主要方法、用户访问模式挖掘算法及国内外最新研究进展情 况，并提出了w e b 用户访问信息挖掘研究的发展方向和趋势。 沈均毅等人【8 】提出了w 曲页面和客户群体的模糊聚类算法。在该算法中，首先根据 用户对站点的浏览情况分别建立w e b 页面和客户的模糊聚类，在此基础上根据m a x m i n 模糊性度量法则构造相应的模糊相似矩阵：以u r l 为列，u s e r i d 为行，访问次数为矩 阵元素值，建立u r i ，u s e r i d 关联矩阵，对矩阵的行向量和列向量分别处理得到相似页 2 硕士论文基于关联规则的w e b 日志挖掘研究与应用 面群和相似用户群，在此基础上直接进行聚类。 陆丽娜等人【9 】提出了基于神经网络的w e b 用户行为聚类分析方法。首先对w e b 站 点访问日志进行分析和会话分析，从会话中找出频繁数据集，进行归一化处理后，生成 模式向量，采用s o f m 模型进行聚类，最后生成用户聚类。 杨武剑、王泽兵、冯雁、武新玲 1 川利用w e b 数据挖掘技术对用户未来的访问进行 预测和推荐，通过对网站个性化服务相关技术的研究，改进了对w e b 服务器用户访问 日志信息进行聚类分析的关联数据竞争聚类算法，并在此基础上构建了相应的实验模 型。 总之，w e b 日志挖掘是一项综合技术，基于w e b 日志挖掘的各种数据挖掘算法也 广泛发展，当前，该领域的研究在国内外越来越受到广大研究者的关注。 1 3 论文的工作及组织结构 1 3 1 论文的主要工作 本文以w e b 服务器上的日志为研究对象，w e b 日志是w e b 服务器记录的用户对站 点资源的访问，其中每条记录一般包括用户、访问时间、资源的u r l 等字段。有效 地对w e b 日志进行定量分析，揭示其中的关联关系、时序关系、页面类属关系、客户 类属关系和频繁路径等，可以为优化w e b 站点的组织结构，增加个性化服务提供参考。 本文的主要内容包括：论述了w e b 挖掘的概念、分类、流程和挖掘的主要方法； 对w e b 日志挖掘进行了研究，阐述了国内外日志挖掘的研究现状，重点研究了w e b 日 志挖掘技术及其过程，特别是数据预处理阶段；对关联规则经典的a p r i o r i 算法进行了 研究，针对算法的性能瓶颈对算法提出了改进，并通过实验对算法性能进行对比验证； 在v c + + 编程环境下，结合理论研究基础和改进的i m p算法，开发了一个w曲apriori 日志挖掘的测试程序，并且通过对学院网络中心的招生网站日志文件的挖掘找出用户的 频繁访问路径，从而对站点结构的改进提出了可行性方案。 1 3 2 论文的组织结构 基于研究的目的与内容，本论文组织结构如下： 第l 章简述了本文研究的背景及意义，国内外w e b 日志挖掘研究现状，以及本文 的主要工作和文章的组织结构。 第2 章对w e b 挖掘进行了论述，包括w e b 挖掘的概念，w e b 挖掘分类，w e b 挖掘 流程和w e b 挖掘的主要方法。 第3 章详细介绍了w e b 日志挖掘技术，包括日志挖掘步骤，日志数据的采集，日 志格式简介，重点研究了数据预处理。 第4 章详细介绍了关联规则及其算法。重点对a p r i o f i 算法进行了分析，并且对其 3 1 绪论硕士论文 性能瓶颈进行了改进，提出了i m p _ a p r i o f i 算法，并通过实验对算法性能进行了对比验 证。 第5 章基于改进的i m p _ a p r i o r i 算法，使用v c + + 开发了一个w e b 日志挖掘的测试 程序，并且通过对网络中心的“招生信息网 网站日志文件的挖掘找出用户的频繁访问 路径，从而对站点结构的改进提出了可行性方案。 第6 章对本文的工作和研究做了总结，并对本文的不足和未来的研究方向做了说明。 4 硕士论文基于关联规则的w e b 日志挖掘研究与应用 2 数据挖掘和w e b 挖掘概述 2 1 什么是数据挖掘 数据挖掘就是从大量数据中提取出规则、规律或模式，又称为数据采掘、数据开采、 模式发现等 1 1 - 1 3 】。数据挖掘有广义和狭义之分。广义的数据挖掘与数据库知识发现 ( k n o w l e d g ed i s c o v e r f o r d a t a b a s e ，k d d ) 含义相同。狭义的数据挖掘是k d d 中的一个步 骤。 大规模数据集合是数据挖掘的研究对象，被人们形象的描述为“知识的源泉 ，它 可以是以结构化数据为主的关系数据库和数据仓库中的数据，也可以是其他复杂类型的 数据，如对象数据、时序数据、文本数据、空间数据、多媒体数据以及w e b 数据等等。 数据挖掘技术是始于面向应用的，它是对特定的数据进行微观或宏观的统计、分析、综 合和推理，以指导实际问题的求解，目的是发现事件间的相互关系，甚至利用已有的数 据对未来的活动进行预测。这样，它就把人们对数据的应用，从低层次的末端查询操作 提升到为各级决策者提供决策支持。需要强调的是，这儿所说的知识有特定的前提和约 束条件，是相对的，面向特定领域、有实际应用价值，并且易于被用户理解。 2 2 数据挖掘的方法和过程 数据挖掘是多种学科理论和技术成果交叉、融合的产物，主要包括数据库技术、统 计学、机器学习、模式识别、神经网络、信息检索、数据可视化等。因此，数据挖掘的 方法可以是数学的，也可以是非数学的；可以演绎，也可以归纳。常用的数据挖掘方法 有：概念描述、关联规则、分类聚类、神经网络、时序序列分析、遗传算法、粗集方法 等。需要说明的是，不同的数据类型、不同的挖掘方法，甚至同一种方法给了不同的初 始参数，结果都会有很大差异。 数据挖掘过程一般需要经历数据准备、数据开采、结果评价与知识表达三个主要步 骤，见图2 2 1 【1 4 】所示，这些环节在具体挖掘实施中可能需要重复进行，整体上呈现为 一种螺旋式上升过程。 5 2 数据挖掘和w e b 挖掘概述硕士论文 数据库 卜数据准备p _ 数据开采_ 评估表示 图2 2 1 数据挖掘过程图 ( 1 ) 数据准备 数据准备是数据挖掘中的一个重要步骤，数据准备是否做好将直接影响到数据挖掘 的效率、准确度以及最终模式的有效性。这一阶段又可划分成三步：数据集成、数据选 择、数据预处理。 数据集成：首先通过填写空缺值、识别孤立点等方法消除噪声和纠正数据中的不 一致，然后将多个与挖掘任务相关的数据结合起来存放在一个一致的数据存储中。 数据选择：从经过处理的数据中确定和分析任务相关的数据 数据预处理：将数据转换成适合数据挖掘的形式，并进行一些必要的数据约简。 ( 2 ) 数据开采 本阶段是数据挖掘过程中最关键的一步，也是技术难点，指采用若干技术或方法去 提取数据模式，主要包括：决定如何产生假设；选择合适的工具模块；发掘知识的操作； 证实发现的知识。 ( 3 ) 结果评价和表示 挖掘达到的模式需要进行修剪和评估，去除冗余的、用户不感兴趣的模式，并将最 终的挖掘结果转换成用户容易理解的形式，如果用户不满意，需要重复以上的数据挖掘 过程。 6 硕士论文基于关联规则的w e b 日志挖掘研究与应用 2 3w e b 数据挖掘 w e b 数据挖掘起源于数据挖掘，w e b 挖掘旨在应用数据挖掘技术从与w w w 相关 的资源和用户浏览行为中提取隐含的、未知的、对决策有潜在价值的知识和模式的过程 【1 5 1 。w e b 挖掘其实就是对文档的内容、可利用资源的使用以及资源之间的关系进行分析， 以实现对w e b 存储模式、w e b 结构和规则的分析，以及动态w e b 内容的查找等。 w e b 挖掘是一项综合技术，涉及w e b 、数据挖掘、计算机语言学、信息学等多个领 域。不同研究者从自身的领域出发，对网络信息的含义有着不同的理解，项目开发也各 有其侧重点。 一般的数据挖掘对象大多是针对关系数据库或数据仓库的，所处理的数据具有完整 的结构。而w e b 挖掘对象与一般的数据挖掘对象不同，其具有如下特点【1 6 】： ( 1 ) 异构的数据环境：从数据库的角度出发，w e b 网站上的信息可以看作一个数据 库。w e b 每个站点都是一个数据源，每个数据源都是异构的，这就构成一个巨大异构数 据环境。 ( 2 ) 动态性极强的信息源：w e b 的数据量以t e r a 字节计算，其页面数目前己经达到 数千亿，而且每天还在不断更新当中。这使得几乎不可能去构造一个数据仓库来复制、 存储或者集成其上的所有数据。 ( 3 ) 信息具有丰富的内涵：既有涉及经济、文化、教育、新闻、娱乐、电子商务等丰 富的信息服务，又蕴涵着访问页面特性、访问路径特性、访问时间特性这些潜在的访问 信息。 w e b 是一个巨大的、广泛分布的、异构的、半结构的、超文本超媒体的、相互联 系并且不断变化的信息仓库，其中包括链接信息、访问使用信息等。这大量的非结构化 数据是无法使用现有数据库管理系统来处理和管理的，这就对w e b 进行有效的信息抽 取和知识发现带来了极大的挑战，也使得w e b 数据挖掘更加复杂。 w e b 数据挖掘作为一个完整的技术体系，在进行挖掘之前的信息获得( 瓜) 和信息抽 取( i e ) 相当重要【l 7 1 。信息获得的目的在于找到相关w 曲文档，它只是把文档中的数据看 成未经排序的词组的集合，而信息抽取的目的在于从文档中找到需要的数据项目，并且 对文档的结构和表达的含义感兴趣，它的一个重要任务就是对数据进行组织整理并适当 建立索引。 信息获得和信息抽取技术的研究已经有很长时间，随着w e b 技术的发展，基于w e b 技术的承、i e 得到了更多的重视。由于w e b 数据量非常大，而且可能动态变化，用原 来手工方式进行信息收集早已力不从心，目前的研究方向是用自动化、半自动化的方法 在w e b 上进行瓜和i e 。 7 2 数据挖掘和w e b 挖掘概述 硕士论文 2 4w e b 挖掘分类 w 曲文档和服务包含的数据，常总称为“w e b 数据”，按文献【i8 】的分类方法，w e b 数据主要分为三类： ( 1 ) 内容数据( c o n t e n td a t a ) ：它是提供信息的主体，包括文本、声音、图像和元数据。 内容数据主要以各种文档形式存在，譬如h t m l 文件和其他各种非文本的媒体文件。 内容数据的其他约定成俗的概念还有“w e b 文档 或者“w e b 页面 。 ( 2 ) 结构数据( s t r u c t u r ed a t a ) ：它是对内容数据组织而派生的数据。内容数据大部分 用h t m l 描述，超链接被广泛用于组织w e b 文档和w e b 文档内部的数据实体。由此 w e b 上就存在着各种超链接形成的结构。此结构又分为站点结构和站间结构两部分。 ( 3 ) 使用数据( u s a g ed a t a ) ：它是用户使用w e b 而衍生的数据。w 曲是一个不受时空 限制的交互式媒介，可在多个层面上记录和收集因用户访问而产生的数据。典型的方法 是在w e b 服务器端收集w e b 日志，它包含了大量h t t p 协议层面的数据。 w e b 上信息的多样性决定了挖掘任务的多样性。按照研究的w e b 数据对象的不同， 一般将w e b 挖掘分为3 类 1 9 】：w e b 内容挖掘、w e b 结构挖掘和w e b 使用挖掘，如图2 4 1 所示： w 曲挖掘 w e b 内容挖掘l - j文本、超文本、多媒体文档 w e b 结构挖掘l j链接结构、内容结构等 w e b 使用挖掘l _ j 服务器日志、代理服务器等 图2 4 1w e b 挖掘分类图 在实际应用中，w e b 挖掘的三种任务不是孤立的，而是相辅相成的。尤其是w e b 内容挖掘和结构挖掘之间关系更为紧密，因为w e b 文档中也包含有链接。有的时候， w e b 内容挖掘和使用挖掘相结合能够更好的完成某个应用任务。总之，w e b 挖掘的这三 个研究方向在实际应用过程中并不是孤立的，而是相互交叉、相互渗透和相互联系的。 目前国际上对w e b 日志挖掘的研究比较多。 2 4 1w 曲内容挖掘 w e b 内容挖掘是一种基于网页内容的w e b 挖掘，是从大量的w e b 数据中发现信息、 抽取有用知识的过程。这些数据对象既有文本和超文本数据，也有图形、图像、语言等 多媒体数据；既有来之数据库的结构化数据，也有用h t m l 标记的半结构化数据和无 r 硕士论文 基于关联规则的w e b 日志挖掘研究与应用 结构的自由文本。 就其方法而言，w 曲内容挖掘可以分为两大类：信息查询( 取) 方法和数据库方法。 就其处理的内容而言，w e b 内容挖掘分为文本和多媒体挖掘两大类： ( 1 ) 对于文本文档( 包括t x t 、p d f 、h t m l 等) 的挖掘称为文本挖掘，w e b 文本挖掘 的对象既可以是结构化的，也可以是非结构化的、半结构化的。w e b 文本挖掘的结果既 可以是对某个文本内容的概括，也可以是对整个文本集合的分类结果或聚类结果，还可 以利用w e b 文档进行趋势预测 2 0 】等。 ( 2 ) 对于影音动画( 音乐、视频、影视、在线游戏等) 的挖掘称为多媒体挖掘，常用的 方法有关联规则法何特征提取法。 w e b 内容挖掘有两种策略：直接挖掘文档的内容，或在其它工具搜索的基础上进行 改进。 2 4 2w 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 结构挖掘主要应用于w w w 上的信息检索领域，可以指导搜索引擎的网页采 集，可以帮助搜索结果排序，也可以进行检索结果聚类、查找相关网页、消除重复网页、 确定地理区域和识别社区等。 2 4 3w 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 日志挖掘。 9 2 数据挖掘和w e b 挖掘概述硕士论文 w e b 日志挖掘是对用户访问w e b 时在服务器上留下的访问日志进行挖掘，挖掘的 目的是在海量的w e b 日志数据中自动、快速地发现用户的访问模式，如频繁访问路径、 频繁访问页组、用户聚类等，以发现系统性能瓶颈，优化站点结构、提高站点效率和用 户查找信息的质量和效率等。表2 4 1 从五个方面对三种挖掘形式做了比较【2 1 】： 表2 4 iw e b 挖掘三种形式对比 w e b 内容挖掘 w e b 结构挖掘w e b 使用挖掘 半结构化、数据库形式的 数据形式非结构化、半结构化交互形式 网站，链接结构 服务器日志记录，浏览器 数据来源文本文档、超文本文档超文本文档，链接 日志记录 b a go f w o r d s 、n - g r a m s 、词、短语、 边界表示图( o e m ) 、关系 表示 关系型表、图形 概念或实体、关系型数据型数据、图形 t f i d f 和变体、机器学习、统计学 p r o p r i e t a r y 算法、i l p 、( 修 p r o p r i e t a r y 算法、机器学 使用方法习、统计学、( 修改后) 的 ( 包括自然语言处理)改后) 的关联规则 关联规则 归类、聚类、发掘抽取规则、发掘 发掘高频的子结构、发掘 主要应用网站体系结构、归类、聚 站点建设、改进与管理、 文本模式、建立模式 营销、建立用户模式 类 2 5w e b 挖掘主要流程 基于上述w e b 数据的特点，典型的w e b 数据挖掘主要包括以下几个步裂2 2 ，2 ”，挖 掘流程见图2 5 1 所示： ( 1 ) 查找资源：任务是从目标w e b 文档中得到数据，包括电子邮件、电子文档、新 闻组，或者网站的日志数据甚至是通过w e b 形成的交易数据库中的数据。 ( 2 ) 信息选择和预处理：从取得的w e b 资源中剔除无用信息，再将信息进行必要整 理。 ( 3 ) 模式发现：自动进行模式发现。可以在同一个站点内部或在多个站点之间进行。 ( 4 ) 模式分析：验证、解释上一步骤产生的模式。可以是机器自动完成，也可以是分 析人员进行交互来完成。 1 0 硕士论文基于关联规则的w e b 日志挖掘研究与应用 数据选择、 2 6w e b 挖掘主要技术 图2 5 1w e b 挖掘流程图 数据挖掘领域常用的关联规则、分类聚类和序列模式等均可用于w e b 挖掘中，此 外，路径分析技术也可用于w 曲挖掘。 2 6 1 关联规则 关联规则挖掘是数据挖掘中最活跃的研究方法之一，同时也是数据挖掘研究的主要 模式之一。关联规则可用于发现用户会话中经常被用户一起访问的页面集合，通常使用 a p r i o r i 算法或其改进算法。关联规则挖掘是从一组给定的数据项以及事务集中，分析出 数据项集在事务集中出现的频度关系，这些关系是事先未知的且隐藏的，也就是说不能 通过数据库的逻辑操作或统计的方法得出。著名的“啤酒和尿布”就是一个关联规则的 例子。所发现的关联规则可以辅助人们进行市场运行( m a r k e t i n g ) 、决策支持( d e c i s i o n s u p p o r t ) 、商业管理( b u s 证e s sm a n a 鲈n 锄t ) 和网站设计( w 曲s i t ed e s i g n ) 等1 2 4 ；5 】。 2 6 2 分类聚类 分类就是对数据库中的每一类数据挖掘出关于该类数据的描述或模型，而这些数据 库中的类是事先利用训练数据建立起来的。作为数据挖掘的一个重要主题，数据分类在 1 1 叮羹示手挖攉备-1 知 2 数据挖掘和w e b 挖掘概述硕士论文 统计学、机器学习、人工智能等领域中得到了较早的研究，只是近年来，人们把它与数 据库技术结合起来解决实际问题。在数据挖掘中，分类算法的研究成果较多，常用的数 据分类算法有：c a r t 、c 4 5 、i d 3 等。在w e b 挖掘中，分类技术可以根据用户注册信 息或共同的访问模式进行分类，得出访问某一服务器文件的用户特征，这一功能可以通 过决策树技术、贝叶斯分类法及k 相邻分类法等实现。 聚类是将物理的或抽象的对象分为几个群体，在每个群体内部，对象之间具有较高 的相似性，而在不同群体之间，相似性则比较低。一般地，一个群体就是一个类，但与 数据分类不同的是，聚类结果基于当前所处理的数据，我们事先并不知道类结构及每个 对象所属的类别。进行聚类挖掘的目的，就是从用户的访问日志中得到具有相似用户访 问兴趣的分类。 聚类算法包括以下步骤【2 6 】：聚类效果评估，对特定的数据选取合适的相似度计算方 法，聚类或分组算法，数据抽象，特征选择和抽取。 按照簇间距离计算方式的不同，分为单连接法，全连接法，最小方差法，其中单连 接法和全连接法使用较多。其他方法包括概率可能性方法( p c a ) ，图论方法，k 均值聚 类算法，模拟退火聚类算法等。 2 6 3 序列模式 序列模式指在时序数据集中发现时间上具有先后顺序的数据项。在i n t e m e t 上，用 户的访问行为在时间上表现出明显的先后关系，非常适合用序列模式来描述规律。 例如，用来购买事务的相似的时间序列，因为用户一次访问会在w e b 服务器日志 记录中记录一段时间，所以序列模式分析技术可以确定在某一个时间段内所有客户访问 特定页面( 或一序列页面) 的共同特征，然后电子零售商能把这些结果与传统事务数据库 的信息相结合，预测用户访问模式与特定站点的遍历模式相关联的未来销售。有目的的 广告活动应针对站点内、基于典型可视化序列的特殊用户和特殊区域，通过这种有目的 的广告活动公司能更有效地改进站点结构和相关特性。这种分析还能决定用于特殊产品 组和不同客户群体的最佳的“后市场 销售，同时也能决定在合同策略中的不同阶段的 最佳时机。 2 6 4 路径分析 用路径分析进行w e b 数据挖掘时，最常用的是刚2 7 捌。该方法把w 曲用一个有向 图来表示，g = f v , e ) ，其中：v 是页面的集合，e 是页面之间的超链接集合，页面定义为 图中的顶点，而页面间的超链接定义为图中的有向边。顶点v 的入边表示对v 的引用， 出边表示v 引用了其他的页面，这样形成网站结构图，从图中确定最频繁的访问路径。 1 2 硕士论文基于关联规则的w e b 日志挖掘研究与应用 2 7w e b 挖掘应用前景 w e b 数据挖掘已广泛地应用于金融业、远程通讯业、制造业、企业管理、医疗服务 以及体育事业中，对它的应用和研究正成为一个热点。w e b 挖掘的应用前景主要表现在 以下三个方面： ( 1 ) 电子商务 运用w e b 挖掘技术能够从服务器和浏览器日志记录中自动发现隐藏在数据中的模 式信息，了解系统的访问模式以及用户的行为模式，从而做出预测性分析。 ( 2 ) 网站设计 通过对网站内容的挖掘，可以有效地组织网站信息，例如通过对用户访问日志记录 信息地挖掘，把握用户的兴趣，有助于开展网站信息推送服务以及个人信息的定制服务。 ( 3 ) 搜索引擎 用搜索引擎进行w e b 挖掘的最大特点体现在它所采用的对网页链接信息的挖掘技 术上。通过对网页内容挖掘，可以实现对网页的聚类、分类，实现网络信息的分类浏览 与检索。运用网络内容挖掘技术改进关键词加权算法，提高网络信息的标引准确度，从 而改善检索效果。 上面仅仅列举了w e b 挖掘在这三个方面的应用。这项技术的应用正变得越来越广 泛，用户对高品质、个性化信息的需求也将进一步推动学术界与实业界的研究开发工作。 1 3 3w e b 日志挖掘 硕士论文 3w e b 日志挖掘 3 1w e b 日志挖掘的提出 w e b 日志挖掘是通过分析w e b 服务器中的日志文件，从而发现用户访问站点的浏 览规律，分析不同w c b 站点的访问日志可以帮助人们理解用户的行为和w e b 的结构， 给网站管理员提供各种有利于w e b 站点改进或能够带来经济效益的信息。 目前，w e b 日志挖掘可以分为两类：访问模式的追踪和个性化的使用记录的追踪。 一般的访问模式追踪通过分析使用记录来了解用户的模式和倾向，以改进站点的组织结 构：而个性化的使用记录追踪则倾向于分析个别用户的偏好，其目的是根据用户的访问 模式，为其提供定制服务。从研究的角度看，目前基于w e b 日志的数据挖掘研究大致 分为3 类：以分析系统性能为目标；以改进系统设计为目标：以理解用户意图为目标。 由于目标的不同，所采用的技术也自然有所不同。以分析系统性能为目标的w e b 数据挖掘的研究多采用统计学的方法，以改进系统设计为目标的数据挖掘多采用关联规 则挖掘的方法，以理解用户意图为目标的数据挖掘研究多采用聚类挖掘和分类挖掘的方 法。 3 2w 曲日志挖掘的应用 w e b 日志挖掘的应用大多与具体领域有关，主要有以下几个方面【2 7 - 3 0 】： ( 1 ) 提供个性化网站：针对单个用户的使用记录对该用户进行建模，结合该用户基本 信息分析他的使用习惯、个人喜好，目的是在电子商务环境下为该用户提供与众不同的 个性化服务。 ( 2 ) 改善系统，提高性能：通过w e b 日志挖掘，可以提供网站服务效率全方位的信 息，从而有助于平衡服务器负荷，减少拥塞的方法，缩短用户等待时间，提高系统服务 质量。此外，可以通过分析网络的非法入侵数据找到系统弱点，提高站点安全性。 ( 3 ) 站点修改：站点的结构和内容是吸引用户的关键。w e b 日志挖掘通过挖掘用户的 行为记录和反馈情况为站点设计者提供改进依据，比如页面连接情况应如何组织、哪些 页面应能够直接访问等。 ( 4 ) 智能商务：用户怎样使用w e b 站点的信息无疑是电子商务销售商关心的重点， 用户一次访问的周期可分为被吸引、驻留、购买和离开四个步骤，w e b 日志挖掘可以通 过分析用户点击流等w e b 日志信息，挖掘用户行为的动机，以帮助销售商合理安排销 售策略。 ( 5 ) w e b 特征描述：通过分析用户对站点的访问情况，统计各个用户在页面上的交互 1 4 硕士论文 基于关联规则的w e b 日志挖掘研究与应用 情况，对用户访问情况进行特征描述。c a t l e d g e 、p i r k o w 等人对这方面做了相关研究， 通过对用户使用数据的挖掘分析，得出用户的浏览模式。 3 3w e b 日志的记录方式 w w w 的结构是c s 模式，并且具有平台无关性。图3 3 1 清晰表明了在w w w 上 用户的请求及服务器的响应是如何进行的3 1 1 。 客户帆 + _ 使用代理服务器时的信息流 c p 客户，代理服务器间通讯 p - w 代理服务器w e b 服务器间通讯 - 不使用代理服务器时的信息流 c w 客户w e b 服务器间通讯 图3 3 1w w w 数据通讯体系结构图 w e b 服务器记录日志文件的方式：当用户通过浏览器向服务器发出页面请求时， w e b 服务器将该页面对应的h t m l 或a s p 、p h p 等页面文件传送给用户，并将这次请 求记录在服务器日志中。浏览器在解释文件内容时，如果还需要向服务器请求新的资源， 浏览器根据当前文件中提供的u r l 地址发出新的请求，服务器接到请求后重复上述响 应和日志记录的过程。用户对w e b 服务器的一次页面请求( 即一次点击) ，如果所请求 的页面包含多个文件，就会在服务器的日志文件中产生多条记录。 3 4w 曲日志分布 w e b 日志挖掘的数据对象主要分布于服务器、客户端和代理服务器中。 在w e b 服务器上，服务器日志记录了多个用户对单个站点的用户访问行为。一些 1 5 3w e b 日志挖掘硕士论文 更为复杂的日志记录了多个用户对单个站点的交易行为，或提交的查询行为。服务器方 具有w e b 站点的完整的结构信息，电子商务交易信息等。 在客户端计算机上，客户端的代理记录了单个用户对单个站点或单个用户对多个站 点的用户访问行为。客户端的c a c h e 记录了用户访问内容。客户端的b o o k m a r k 也记录 了单个用户对单个站点的访问偏好。 在代理服务器上，记录了多个用户对多个站点的访问行为，同时代理服务器内部的 c a c h e 内，也记录了多个用户对站点的访问内容。因此，用户访问模式的挖掘有三种类 型：w e b 服务器端、客户端和代理服务器，根据挖掘的目的和应用方向，挖掘的用户访 问模式的侧重点也不尽相同。 3 5w 曲日志挖掘数据源 w e b 日志挖掘的数据来源主要包括：w e b 日志( 包括服务器日志、引用日志和代理 日志) 、w e b 站点的拓扑结构和站点文件、用户的注册信息、用户调查信息、c o