（计算机应用技术专业论文）基于关联规则分类的web用户兴趣预测.pdf

摘要 摘要 w e b 挖掘是数据挖掘的一个重要的研究方向。w e b 挖掘突破传统意义上的数据 格式的限制，随着w e b 的发展，它会变得越来越重要，成为b 用户更好的获得信息 的一个有效的途径。 如何对网上用户分类是w e b 挖掘领域应用最多的任务之一。对网上用户分类 可以使网站针对不同的用户提供不同的服务，这样，用户就能方便快捷的获得自 己所需的信息。如何有效的找出关于w e b 用户的分类模式知识是w e b 挖掘研究的热 点问题，具有重要的理论意义和实用价值。 本文针对数据挖掘技术在w e b 挖掘中的应用进行了研究工作。在第一章绪论 中介绍了本论文的研究背景、研究意义，以及论文的主要工作。第二章对数据挖 掘技术的定义，结构，过程以及一些分析方法进行了综述。第三章分析w e b 挖掘当 前研究现状，指出了w e b 挖掘的困难，着重讨论了霹e b 内容挖掘技术。第四章讨论 了w e b 使用挖掘的过程，模式发现的常用算法，详细分析了日志预处理的各个过 程。 第五章中对关联规则的经典算法a p r i o r i 进行分析，并指出它的一些缺陷，存 在的问题，同时，也讨论f p - g r 0 州h 算法，指出用f p g r 0 讹算法来挖掘频繁项集可以 避免产生大量候选集，并且算法效率有很大的提高。在此基础上，分析了传统分 类关联规则挖掘算法产生的问题，提出一种用于w e b 挖掘的分类关联规则挖掘算 法。 第六章运用不同的方法来对w e b 用户兴趣预测。试验表明用于w e b 挖掘的分 类关联规则挖掘算法是有效的。在全文的分析基础上，提出一种基于w e b 挖掘的网 站个性化推荐系统结构。 第七章是全文的总结和研究工作展望。 论文主要做了以下工作： 通过对经典关联规则挖掘算法a p r i o r i 进行分析，同时，也讨论f p g r o w c l l 算法，指出用f p g r o w 山算法来挖掘频繁项集可以避免产生大量候选集，并 且算法效率有很大的提高。在此分析基础上，分柝了传统分类关联规i j 基于关联规则分类的w e b 用户兴趣预测 挖掘算法产生的问题，提出一种用于w e b 挖掘的分类关联规则挖掘算法。 分别运用i d 3 算法，传统的分类关联规则挖掘算法和用于w e b 挖掘的分类 关联规则挖掘算法来对w e b 用户兴趣预测。试验表明用于w e b 挖掘的分类 关联规则挖掘算法是有效的。 提出一种基于w e b 挖掘的网站个性化推荐系统结构。该结构的特点是综 合了w e b 使用挖掘，w e b 结构挖掘和w e b 内容挖掘，并且它可以通过搜索引 擎在线搜索网页，弥补了网站内容的本身不足。 关键词：数据挖掘，w e b 挖掘，关联规则，分类 a b s t r a c t a b s t r a c t w e bm i n i n gi sa ni m p o r t a n tr e s e a r c hd i r e c t i o ni nd a t am i n i n g i t b r e a k st h r o u g ht h er e s t r i c t i o no ft r a d i t i o n a ld a t ab e h a v i n gf o r m a t ，a n d w i t ht h ei n t e r n e td e v e l o p m e n t ，i tb e c o m e sm o r ea n dm o r ei m p o r t a n t i ti s a ne f f e c t i v ew a yf o rw e bu s e r st og e ti n f o r m a t i o n w e bu s e r sc l a s s i f i c a t i o ni 8o n eo ft h em o s tc o 唧o n l yu s e dt a s k si n w e bm i n i n g i tc a nh e l pw e bs i t ep r o v i d ep e r s o n a li z e ds e r v i c e sf o rw e b u s e r sa n ds ot h eu s e r sc a ng e ti n f o r m a t i o nc o n v e n i e n t l y h o wt of i n da l l t h o s ec l a s s i f i c a t i o np a t t e r n so fw e bu s e r si sar e s e a r c hi s s u ei nw e b m i n i n ga n dh a sg r e a tt h e o r e t i cs i g n i f i c a n c ea n dp r a c t i c a lv a l u e t h ep a p e rm a k e ss o m er e s e a r c h e so ft h ea p p l i c a t i o no fd a t am i n i n gt o w e bd a t a i ti n t r o d u c e st h eb a c k g r o u n d ，t h es i g n i f i c a n c ea n dt h es t r u c t u r e o ft h ep 8 p e ri nt h ef i r s tc h a p t e r i nt h es e c o n dc h a p t e r ， t h ep a p e r i n t r o d u c e st h ec o n c e p t ， t h es t r u c t u r ea n dt h ep r o c e s so fd a t am i n i n g t e c h n j q u e s t h et h i r dc h a p t e rd e s c r i b e sw e bm i n i n g ， i n c l u d i n gt h es t a t e a n d t h ed i f f j c u l t i e si nt h ew e bm i n i n g i nt h i sc h a p t e r ， t h ep a p e r s u m r r l a r i z e sw e bu s a g em i n i n g ， i n c l u d i n gp r o c e s sa n dp a t t e r nf i n d i n g a r i t h m e t i ca n dp u t se m p h a s e so nt h ep r e p r o c e s s i n go fw e bl o g i nt h ef i f t hc h a p t e r w ea n a l y z et h et r a d i t i o n a la s s o c i a t i o nr u l e s a r i t h m e t i ca n dp o i n to u ts o m ed e f i c i e n c i e 8o ft h ea r i t h m e t i c 。 t h e nw e a n a l y z et h ef p g r o w t ha r i t h m e t i c b a s e do nt h ea n a l y s i s ，w ep u tf o r w a r d ac l a s s i f i c a t i o na s s o c i a t i o nr u l ef i n d i n ga r i t h l i l e t i cf o rw e bm i n i n g i nt h es i x t hc h a p t e r ，w ea t t e m p tt oa p p l ys o m ea r i t h m e t i c ，i n c l u d i n g i d 3 ，t r a d i t i o n a lc l a s s i f i c a t i o na s s o c i a t i o nr u l ef i n d i n ga r i t h m e t i ca n d t h ea s s o c i a t i o nr u l ef i n d i n ga r i t h m e t i cf o rw e bm i n i n g t h er e s u l ts h o w s t h a tt h ea s s o c i a t i o nr u l ef i n d i n ga r i t h m e t i cf o rw e b m i n i n gi se f f e c t i v e i nt h es e v e n t hc h a p t e r ， w es u i l l r r 【a r i z et h ew h o l ep a p e ra n dm a k ea - i i l - 一一一苎差壁塑型坌鲞堕! 生旦宝茎塑堡型 p r o s p e c t0 to u rr e s e a r c h e s m a i nw o r k so ft h ep a p e r ： 1 f p g r o w t ha r i t h m e t i cd o s en o tp r o d u c et h ec a n d i d a t ei t e m sa n dt h e e f f i c i e n c yo ft h ea r i t h m e t i ci sb e t t e rt h a na p r i o r ia r i t h m e t i c b a s e do n t h ea n a l y s i s ，t h ep a p e rp u t sf o r w a r dac l a s s i f i c a t i o na s s o c i a t i o nr u l e f i n d i n ga r i t h m e t i cf o rw e bm i n i n g 2 w ea t t e m p tt oa p p l ys o m ea r i t h m e t i c ， i n c l u d i n gi d 3 ， t r a d i t i o n a l c l a s s i f i c a t i o na s s o c i a t i o nr u l ef i n d i n ga r i t h m e t i ca n dt h ec l a s s f i c a t i o n a s s o c i a t i o nr u l ef i n d i n ga r i t h m e t i cf o rw e bm i n i n gt op r e d i c tt h ew e b u s e r s i n t e r e s t s w e c o m p a r e t h er e s u l t sa n dc o n c l u d e t h a tt h e c l a s s i f i c a t i o na s s o c i a t i o nr u l ef i n d i n ga r i t h m e t i cf o rw e bm i n i n gi s e f f e c t i v e 3 w ep u tf o r w a r daf r a m e w o r ko fap e r s o n a l i z e dr e c o 咖e n d e ds y s t e mf o r w e bs i t e sa n dt h ef r a m e w o r ki n t e g r a t e sw e bu s a g em i n i n g ， w e bc o n t e n t 巾i n i n ga n dw e bu s a g em i n i n g k e y w o r d ： d a t am i n i n g ，w e bm i n i n g ， a s s o c i a t i o nr u l e ， c l a s s i f i c a t i o n i v 独创性声明 y7 6 5 8 0 6 本人芦明所呈趸的芋位论文是本人在导师指导h 进行的研冤工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得疹 勃尤净其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位敝储始弘艰期：埘年f 月7 日 学位论文版权使用授权书 本学位论文作者完全了解蔷7 勤古孑有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权麦膨右以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：下雩钦 签字日期：沙。弭，月彳日 学位论文作者毕业去向： i f 导师签名 签字日期 电话： 邮编： 7 月 厂 观啤邳删 力 绪论 1 1 论文的研究背景 第一章绪论 随着数据库技术和数据库管理系统的广泛应用，全球范围内数据库中存储的 数据量急剧增大，有些面向科学研究的数据库中的数据也非常惊人。但是，传统 的数据库应用仅限于简单的查询、统计及报表的打印，数据库中隐藏着的丰富知 识远远没有得到充分的挖掘和应用。以指数级速度增长的数据库与人们从中获取 的知识形成强烈的反差，势必造成信息腐烂，导致大量的数据垃圾，人们迫切需 要利用一种崭新的技术和上具智能地、自动地将数掘转变为知识，这种情况下数 据挖掘术就应运而生。 w o r l dw i d ew e b 自从1 9 9 1 年诞生以来，已经发展为拥有亿万用户和上百万站 点的巨大分布式信息库。随着i n t e r n e t 得广泛应用，如何在浩如烟海的w w w 数据中 找到需要的信息，比传统的关系数据库更加复杂，困难。所以，数据挖掘技术在成 功的应用于传统的数据库领域之后，人们对基于w e b 的数据挖掘也开始进行研究。 在众多的w e b 数据挖掘研究领域中，w e b 使用挖掘由于对于w e b 网站的优化和页面 内容的重新组织起到重要作用，并直接会对w e b 网站产生经济效益，因此对这个 领域的研究也日益增加。w e b 使用挖掘主要的工作是从记录用户浏览页面的历史 日志记录中，发现用户浏览页面地习惯，从而调整w e b 页面的链接结构。 在使用挖掘中，采用了许多数据挖掘中成熟的技术，但由于用户浏览模式的 挖掘和传统数据挖掘不同，在应用这些技术时，要作相应的改动。 1 2 论文的研究意义 i n t e r n e t 给人类带来了革命性的变革，随着i n t e r n e t 的进一步发展，各种网 络的应用业务也如雨后春笋般地发展起来，例如网上商店、网上银行、远程教育、 远程医疗等，特别是方便、快捷、高效的电子商务，在1 9 9 8 到2 0 0 3 年发展速度超 过了3 0 。2 0 0 2 年全球消费者的电子贸易额达到了数千亿美元的规模。i n t e r n e t 基于关联规则分类的w c b 用户若趣预测 将成为未来商战的战场。随着越来越多组织、企业在互联网上开展业务，传统的 市场营销策略、企业战略制定技术也都纷纷转向i n t e r n e t 。w e b 是i n t e r n e t 上存 储和发布信息最普遍的载体，人们从w e b 上获取信息的模式、获取信息的类型也 就反映了其兴趣偏好所在。因此，用户访问w e b 的规律，成了i n t e r n e t 环境下各 企业共同关注的热点。分析用户使用模式有助于企业确定顾客消费的生命周期， 针对不同的产品定制相应的营销策略；可以找出如何优化一个网站组织结构的策 略；可以确定预传哪些页面到客户端，从而提高网站的效率：另外，对那些要通 过w o r l dw i d ew e b 发送广告的企业，分析用户使用模式有助于有针对性地在某些 用户经常访问的地方插播广告条。除了w e b 站点管理者需要跟踪和分析用户的浏 览模式，用户也有必要使用自动搜索工具寻找需要的信息，这些因素推动了服务 器端和客户端的智能系统的产生。目前，数据挖掘技术的研究已经有了很大的发 展，数据挖掘的理论也已逐步成型，但对于w e b 挖掘技术的研究还不够深入。w e b 挖掘的困难在于：传统的数据挖掘是面向关系数据库或数据仓库。处理的数据具 有完整的结构，但是i n t e r n e t 上的数据是无序的、非结构化或半结构化的，并且 存在大量的冗余和噪声。所以，如何将传统的数据挖掘技术应用于w e b 挖掘是一 个很大的挑战，并且也县有很现实的意义。 1 3 论文工作介绍 论文比较系统、完整地分析和论述了数据挖掘技术以及w e b 挖掘技术。着重 研究了w e b 使用模式挖掘过程中各环节的关键技术，从数据准备到模式发现再到 模式分析。根据论文研究的目的，本人主要做了以下几个方面的工作： 1 数据挖掘技术的定义，结构，过程以及一些分析方法。全面的介绍w e b 挖掘 技术当前国内外的研究重点和研究现状。 2 重点讨论了w e b 使用模式挖掘中的挖掘过程，介绍了各种用于w e b 使用挖掘 的模式发现算法，详细地分析了预处理阶段的各项任务。 3 分析了传统的关联规则发现算法a p r i o r i 算法，并指出的一些缺陷，存在 的问题。在分析了a p r i o r i 算法缺陷的基础上，分析了传统分类关联规则产生的 问题在此基础上，提出一种用于w e b 掘的分类关联规则挖掘算法。 的。 4 。将算法应用于w e b 使用挖掘来预测用户的兴趣，试验表明该方法是有效 5 在前面分析的基础上，提出一种基于w e b 挖掘的网站个性化推荐系统结构。 1 4 论文的组织 在论文中，我们重点研究了数据挖掘技术在w e b 使用挖掘中的应用。全文共 分七章，组织如下： 第一章绪论：简要介绍了本论文的课题背景、研究意义，以及论文的主要工作。 第二章数据挖掘技术：数据挖掘技术的定义，结构，过程以及一些分析方法。 第三章w e b 挖掘：分析w e b 挖掘当前研究现状，指出了w e b 挖掘的困难，着重讨论 了w e b 内容挖掘技术。 第四章w e b 使用挖掘及其数据预处理：讨论了w e b 使用挖掘的过程，模式发现的常 用算法，详细分析了日志预处理的各个过程。 第五章基于关联规则分类方法：对关联规则的经典算法a p r i o r i 进行分析，并指出 的一些缺陷，存在的问题，同时，也讨论f p - g r 0 、础算法，指出用f p g r o w 【h 算法来挖 掘频繁项集可以避免产生大量候选集，并且算法效率有很大的提高。在此基础上， 分析了传统分类关联规则算法产生的问题，提出一种用于w e b 挖掘的分类关联规 则挖掘算法。 第六章基于关联分类方法的w e b 用户兴趣预测：我们运用不同的方法来对、b 用户兴趣预测。通过对不同方法的比较，可以看出我们的方法是有效的。在全文 的分析基础上，提出一种基于w e b 挖掘的网站个性化推荐系统结构。 第七章总结和进一步的研究工作。 基于关联规则分类的w e b 用户兴趣预测 第二章数据挖掘基本原理 2 1 数据挖掘的由来 自8 0 年代中期以来，数据库技术的特点是广泛接受关系技术，研究和开发新 的、功能强大的数据库系统。这些系统使用了先进的数据模型，如扩充关系模型、 面向对象模型、对象一关系模型和演绎模型。包括空间的、时间的、多媒体的、 主动的和科学的数据库、知识库、办公信息库在内的面向应用的数据库系统层出 不穷。涉及分布性、多样性和数据共享的问题被广泛研究。异种数据库和基于 i n t e r n e t 的全球信息系统，如w w w 也已经出现，并成为信息产业的主力军。 现在，数据可以存放在不同类型的数据库中。最近出现的一种数据库结构是 数据仓库。这是一种多个异种数据源在单个站点以统一的模式组织的存储，以支 持管理决策。数据仓库技术包括数据清理、数据集成和联机分析处理( o l a p ) 。 0 l a p 是一种分析技术，具有汇总、合并和聚集功能，以及从不同的角度观察信 息的能力。尽管0 l a p 工具支持多分析和决策，但对于深层次的分析，如数据分 类、聚类和数据随时间变化的特征，仍然需要其他分析工具。 数据的丰富带来了对强有力的数据分析工具的需求。快速增长的海量数据 收集、存放在大量数据库中，理解它们远远超出了人的能力。结果，收集在大量 数据库中的数据变成了难以再次访问的数据档案。这样，重要的决定常常不是基 于数据库中信息丰富的数据，而是基于决策者的直觉。因为决策者缺乏从海量数 据中提取有价值知识的工具。此外，考虑当前的专家系统技术，通常，这种系统 依赖用户或领域专家人工地将知识输入知识库，这就常常有偏差和错误，并且耗 时，费用高。利用数据挖掘工具进行数据分析，可以发现重要的数据模式，对商 务决策、知识库建立、科学和医学研究等领域做出贡献。现实存在的数据和信息 之间的鸿沟要求系统地开发数据挖掘工具。 2 2 数据挖掘的定义 2 2 1 数据挖掘的定义 数据挖掘，就是从大型数据库中提取人们感兴趣的知识，这些知识是隐含的， 事未知的潜在的有用的信息，提取的知识表示为概念( c o n c e p t s ) ，规则( r u l e s ) ， 规律( r e g u l a “t i e s ) ，模式( p a t t e r n s ) 等形式“。 这里把数据挖掘的对象定义为数据库，更广义的说法是：数据挖掘意味着在一些 事实或观察数据集合中寻找模式的决策支持过程。数据挖掘的对象不仅是数据库 也可以是文件系统，或其他任何组织在一起的数据集合，例如，本文的挖掘对象 是w w w 信息资源。 从数据挖掘的定义可以看出，作为一个学术领域，数据挖掘和知识发现k d d 具有很大的重合废，大部分学者认为数据挖掘和知识发现是等价的概念，人工智 能领域习惯称k d d ，而数据挖掘领域习惯称数据挖掘。有学者把k 叻看作知识发现 的完整过程，而数据挖掘只是这个过程中的一个部分。这里，我们倾向于前一种观 点，认为数据挖掘从理论和技术上继承了知识发现领域的成果，同时又有着独特 的内涵，数据挖掘更着眼于设计高效的算法以达到从巨量数据中发现知识的目 的。与数据挖掘关系密切的研究领域包括机器学习( m a c h i n el e a r n i n g ) 和统计 ( s t a t i s t i c s ) 。特别是机器学习被认为和数据挖掘的关系最密切。二者的主要 区别在于：数据挖掘的任务是发现可以理解的知识，而机器学习关心的是提高系 统的性能，因此训练神经网络来控制系统是一种机器学习过程，但不是数据挖掘； 数据挖掘的对象是大型数据库，一般来说机器学习处理的数据集要小，因此效率 问题对数据挖掘问题来说是至关熏要的。 2 2 2 数据挖掘的系统结构 基于上述观点，典型的数据挖掘系统具有以下主要成分”1 ： 数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、 电子表格或其他类型的信息库。可以在数据上进行数据清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓 库服务器负责提取相关数据。 苎主羞壁塑墨! ! 坌鲞塑竺! 旦宝茎塑塑型 知识库：这是领域知识，用于指导搜索，或评估结果模式的兴趣度。这 种知识可能包括概念分层，用于将属性值组织成不同的抽象层。用户确 信方面的知识也可以包含在内。可以使用这种知识，来评估模式的兴趣 度。领域知识的其他例子有兴趣度限制或阈值和元数据( 例如，描述来 自多个异种数据源的数据) 。 数据挖掘引擎：这是数据挖掘系统基本的部分，由一组功能模块组成， 用于特征化、关联分类、聚类分析以及演变和偏差分折。 模式评估模块：通常，此成分使用兴趣度度量，并与数据挖掘模块交互， 以便将搜索聚焦在有趣的模式上。它可能使用兴趣度阈值过滤发现的模 式。模式评估模块也可以与挖掘模块集成在一起，这依赖于所用的数据 挖掘方法的实现。对于有效的数据挖掘，建议尽可能深地将模式评估推 进到挖掘过程之中，以便将搜索限制在有兴趣的模式上。 图形用户界面：本模块在用户和数据挖掘系统之间通信，允许用户与系 统交互，指定数据挖掘查询或任务，提供信息、帮助搜索聚焦，根据数 据挖掘的中间结果进行探索式数据挖掘。 系统结构如下所示： 图2 一l 典型数据挖掘系统结构 数据挖掘的基本原理 2 3 数据挖掘的过程 数据挖掘指根据对数据的分析，建立对数据的特性以及数据之间关系描述的 模式的过程。在这个描述中，数据是一系列事实的集合( 例如数据库中的实例) ， 而模式是使用某种语言对数据集合一个子集的描述。过程是指挖掘中的步骤。数 据挖掘一般由三个主要阶段组成：数据准备、数据挖掘，以及结果的解释评估。 知识的发现可以描述为这三个阶段的反复过程“。图2 1 给出了数据挖掘的整个 过程，这个过程是交互和迭代的，其中许多时候需要用户的参与。 2 3 1 数据准备 图2 2 数据挖掘的过程 数据准备又可分为三个子步骤：数据选取( d a t as e l e c t i o n ) 、数据预处理 ( d a t ap r e p r o c e s s i n g ) 和数据变换( d a t at r a n s f o r m a t i o n ) 。数据选取的目的是 确定发现任务的操作对象，即目标数据，它是根据用户的需要从原始数据源中抽 取的一组数据。数据预处理一般包括消除嗓声、推导计算缺省值数据、消除重复 记录、完成数据类型转换等。一般来说，如果数据挖掘的对象是数据仓库，则数 据预处理己经在生成数据仓库时完成了。数据变换的主要目的是消减数据维数， 即从初始特征中找出真正有用的特征以减少数据挖掘时要考虑的特征或变元个 数。 2 3 2 数据挖掘 数据挖掘阶段首先要确定挖掘的任务或目的是什么，如数据总结、分类、聚 类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用什么样 基于关联规则分类的w e b 用户* 趣预测 的挖掘算法。同样的任务可以用不同的算法来实现。选择实现算法有两个因素要 考虑：一是不同的数据有不同的特点，因此需要用与之相关的算法来开采；二是 用户或实际运行系统的要求，有的用户可能希望获取描述型( d e s c r i p t i v e ) 的， 容易理解的知识c 采用规则表示的挖掘方法显然要好于神经网络之类的方法) ， 而有的用户或系统的目的是获取预测准确度尽可能高的预测型( p r e d i c t i v e ) 知 识。 2 3 3 结果解释和评估 数据挖掘阶段发现出来的模式，经过用户或机器的评估，可能存在冗余或无 关的模式，这时需要将其剔除：也有可能模式不满足用户要求，这时就需要整个 发现过程退回到发现阶段之前，如重新选取数据、采用新的数据变换方法、设定 新的数据挖掘参数值，甚至更换挖掘算法。由于数据挖掘系统最终是面向用户的， 因此可能要对发现的模式进行可视化，或者把结果转换为用户易懂的表现形式。 数据挖掘过程应该注意的几点： ( 1 ) 数据挖掘仅仅是整个过程中的一个步骤。数据挖掘质量的好坏有两个影 响要素：一个是采用的数据挖掘技术的有效性，二是用于挖掘的数据的质量和数 量( 数据量的大小) 。如果选择了错误的数据或不适当的属性，或对数据进行了错 误的转换，则有可能取到不正确的挖掘结果。 ( 2 ) 整个挖掘过程是一个不断反馈的过程。假如用户在挖掘途中发现选择的 数据不太好，或使用的挖掘技术产生不了期望的结果，这时就需要重复先前的过 程，甚至从头重新开始。 ( 3 ) 可视化在数据挖掘的各个阶段都扮演着重要的作用。特别是，在数据准 备阶段，用户可能要使用散点图、直方图等可视化统计技术来显示有关数据，以 期对数据有一个初步的理解，从而为更好地选取数据打下基础。在挖掘阶段，用 户有可能要使用与领域问题有关的可视化工具。在表示结果阶段，则可能又要用 到其它的可视化技术。 茎塑丝堡塑苎查垦堡一 2 4 数据挖掘的分析方法 数据挖掘的核心技术经历了数十年的发展，其中包括数理统计、人工智能、 机器学习。现在，这些成熟的技术，加上高性能的关系数据库引擎以及广泛的数 据集成，让数据挖掘技术进入了实用阶段。 数据挖掘方法有多种，其中比较典型的有关联分析、序列模式分析、分类 分析、聚类分析等： 关联分析：即利用关联规则进行数据挖掘。在数据挖掘研究领域，对 于关联分析的研究开展得比较深入，人们提出了多种关联规则的挖掘 算法，如a p r i o r i 、f p g r o w t h 等算法。关联分析的目的是挖掘隐藏在 数据间的相互关系，它能发现数据库中形如”9 0 的顾客在一次购买活 动中购买商品a 的同时购买商品旷之类的知识。 序列模式分析：序列模式分析和关联分析相似，其目的也是为了挖掘 数据之间的联系，但序列模式分析的侧重点在于分析数据问的前后序 列关系。它能发现数据库中形如”在某一段时间内，顾客购买商品a ， 接着购买商品b ，而后购买商品c ，即序列a b c 出现的频度较高 “之类的知识，序列模式分析描述的问题是：在给定交易序列数据库中， 每个序列是按照交易时间排列的一组交易集，挖掘序列函数作用在这 个交易序列数据库上，返回该数据库中出现的高频序列。在进行序列 模式分析时，同样也需要由用户输入最小置信度( m i n i 叫mc o n f i d e n c e ) c 和最小支持度( m i n i m u ms u p p o r t ) s 。 分类分析：设有一个数据库和一组具有不同特征的类别( 标记) ，该数 据库中的每一个记录都赋予一个类别的标记，这样的数据库称为示例 数据库或训练集。分类分析就是通过分析示例数据库中的数据，为每 个类别做出准确的描述或建立分析模型或挖掘出分类规则，然后用这 个分类规则对其它数据库中的记录进行分类。举一个简单的例子，信 用卡公司的数据库中保存着各持卡人的记录，公司根据信誉程度，已 将持卡人记录分成三类：良好、一般、较差，并且类别标记赋给各个 记录。分类分析就是分析该数据库的记录数据，对每个信誉等级做出 准确描述或挖掘分类规则，如”信誉良好的客户是指那些年收入在5 万 基于关联规则分类的w c b 用户兴趣预测 元以上，年龄在4 0 5 0 岁之间的人士”，然后根据分类规则对其它相 同属性的数据库记录进行分类。目前已有多种分类分析模型得到应用， 其中几种典型模型是线性回归、决策树等模型。 聚类分析：与分类分析不同，聚类分析输入的是一组未分类记录，并且 这些记录应分成几类事先也不知道。聚类分析就是通过分析数据库中 的记录数据，根据一定的分类规则，合理地划分记录集合，确定每个 记录所在类别。它所采用的分类规则是由聚类分析工具决定的。聚类 分析的方法很多，其中包括系统聚类法、分解法、加入法、动态聚类 法、模糊聚类法、运筹方法等。采用不同的聚类方法，对于相同的记 录集合可能有不同的划分结果。 w e b 挖掘技术 第三章w e b 挖掘技术 3 1 w e b 挖掘的定义 w e b 挖掘是一项综合技术，涉及w e b 、数据挖掘、计算机语言学、信息学等多 个领域。不同研究者从自身的领域出发，对w e b 挖掘的含义有着不同的理解，项 目开发也各有其侧重点。例如，有些计算机语言学家认为，w e b 文档为自然语言 理解提供了丰富的语料，可以从中自动地学习词语的意义，以进行词义辨析或确 定词语所属的概念4 3 。我们从更为一般的角度出发，对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 e b 挖掘的对 象是大量、异质、分布的w e b 文档。我们认为，在本质上，以w e b 作为中间件对数 据库进行挖掘，以及对w e b 服务器上的日志、用户信息等数据所开展的挖掘工作 仍属于传统的数据挖掘的范畴。其次，w e b 在逻辑上是一个由文档节点和超链接 构成的图，因此w e b 挖掘所得到的模式可能是关于w e b 内容的，也可能是关于w eb 结构的。此外，由于w e b 文档本身是半结构化或无结构的，且缺乏机器可理解的 语义，而数据挖掘的对象局限于数据库中的结构化数据，并利用关系表格等存储 结构来发现知识，因此有些数据挖掘技术并不适用于w e b 挖掘，即使可用也需要 建立在对w e b 文档进行预处理的基础之上。这样，开发新的w e b 挖掘技术，以及对 w e b 文档进行预处理以得到关于文档的特征表示，便成为w e b 挖掘研究的重点。 3 2 面向w e b 数据挖掘特点 w e b 上有海量的数据信息，怎样对这些数据进行应用，成了现今数据库技术 的研究热点，数据挖掘就是从大量的数据中发现隐含的规律性的内容，解决数据 的应用质量问题，充分利用有用的数据，废弃虚伪无用的数据，是数据挖掘技术 基于关联规则分类的w 曲用户兴趣预测 的最重要的应用。相对于w e b 的数据而言，传统的数据库中的数据结构性很强， 即其中的数据为完全结构化的数据，而w e b 上的数据最大的特点就是半结构化， 所谓半结构化是相对于完全结构化的传统数据库的数据而言，显然面向w e b 的数 据挖掘比面向单个数据仓库的数据挖掘要复杂的多。”： ( 1 ) w e b 挖掘的对象是大量、异质、分布的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 挖掘所得 到的模式可能是关于w e b 内容的，也可能是关于w e b 结构的 ( 3 ) w e b 上的数据与传统的数据库中的数据不同，传统的数据库都有一定的 数据模型，可以根据此模型来具体描述特定的数据，而w e b 上的数据非常复杂没 有特定的模型描述，每一站点的数据都各自独立设计，并且数据本身具有自述性 和动态可变性，因而w e b 上的数据具有一定的结构性，但因自述层次的存在，从 而是一种非完全结构化的数据，这也被称之为半结构化数据，半结构化是w e b 上 数据的最大特点。由于w e b 本身是半结构化或无结构的，且缺乏机器可理解的语 义，而传统的数据挖掘的对象局限于数据库中的结构化数据，有些数据挖掘技术 不适用于w e b 挖掘，即使可用也需对w e b 文档进行预处理。这样，就需要开发新的 w e b 挖掘技术。 ( 4 ) 对有效的数据仓库和数据挖掘而言，w e b 似乎太庞大了。w e b 的数据量目 前以兆兆字节计算，而且仍然在迅速地增长。许多机构和社团都在把各自大量的 可访问信息置于网上。这使得几乎不可能去构造一个数据仓库来复制、存储或集 成w e b 上的所有数据。最近，有一些工作在致力于存储或集成w e b 上的所有数据。 、b 挖掘技术 ( 5 ) w e b 页面的复杂性高于任何传统的文本文档。w e b 页面缺乏同一的结构， 它包含了远比任何一组书籍或其它文本文档多得多的风格和内容。w e b 可以看作 一个巨大的数字图书馆，然而，这图书馆中的大量文档并不根据任何有关排列 次序加以组织。它没有分类索引，更没有按标题、作者、扉页、目次等的索引。 ( 6 ) w e b 是一个动态性极强的信息源。w e b 不仅以极快的速度增长，而且其信 息还在不断地发生着更新。新闻、股票市场、公司广告和w e b 服务中心都在不断 地更新着各自的页面。链接信息和访问记录也在频繁地更新之中。 ( 7 ) w e b 面对的是一个广泛的形形色色的用户群体。目前因特网上连接有约5 千万台工作站，其用户群仍在不断地扩展当中。各个用户可以有不同的背景、兴 趣和使用目的。大部分用户并不了解信息网络结构，不清楚搜索的高昂代价，极 容易在“黑暗”的网络中迷失方向，也极容易在“跳跃式”访问中烦乱不已和在 等待信息中失去耐心。 ( 8 ) w e b 上的信息只有很小的一部分是相关的或有用的。据说9 9 的w e b 信息 相对9 9 的用户是无用的。虽然这看起来不是很明显，但一个人只是关心w e b 上的 很少一部分信息确是事实。w e b 所包含的其余信息对用户来说是不感兴趣的，而 且会淹没所希望得到的搜索结果。这些挑战已经推动了如何高效且有效地发现和 利用因特网上资源的研究工作。w e b 挖掘是一个更具挑战性的课题，它实现对w e b 存取模式、w e b 结构、规则和动态的w e b 内容的查找。 3 3 w e b 挖掘的分类 w e b 信息的多样性决定了w e b 挖掘任务的多样性。1 。网络中有各种各样的数据 资源，可以将这些资源分为四类，第一类是内容( c o n t e n t ) ，即网页上的真正 数据；第二类是结构( s t r u c t u r e ) ，即描述内容组织的数据；i n t r a p a g e 结 构信息包括各种h t m l 或) ( m l 标记及其出现的序列等，其中的主要结构信息是 网页之间的超链接属性；第三类是使用( u s a g e ) ，是网页被人浏览的记录，如 i p 地址、访问时间等，这些信息可以从w e b 服务器的日志文件获得。第四类是 用户资料( u s e rp r o f i l e ) ，是某个网站中记录的用户资料。 根据数据资源的分类，w e b 数据挖掘可以分为三类：w e b 内容挖掘( w e b c o n t e n tm i n i n g ) 、w e b 结构挖掘( w e bs t r u c t u r e i i n i n g ) 和w e b 使用挖掘( w e b 基于关联规则分类的w e b 用户兴趣预测 u s a g em i n i n g ) ，如图卜3 所示1 。w e b 内容挖掘和w e b 结构挖掘分别是对前两 种数据类型进行挖掘，而w e b 使用挖掘则不同于前两者，它针对的是用户和网络 交互过程中提取的数据，主要包括：w e b 服务器日志记录、代理服务器的日志记 录、浏览器日志记录、用户简介、注册信息、交易信息等等。 图3 1w e b 挖掘的分类 3 3 1 w e b 使用挖掘 所谓w e b 使用挖掘主要是通过对用户在访问w w w 服务器时留下的访问记录进 行挖掘，从而获得有关用户的访问模式。挖掘的对象主要是在服务器上的日志信 息。w w w 服务器的日志文件中记录了用户的访问记录，通过对这些数据的分析， 获取有关用户的行为模式。在后面的章节中，我们将详细的对w e b 使用挖掘进行 分析。 3 3 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 内容挖掘的重点是页面分类和聚类。 w e b 页面的分类是根据页面的不同特征，将其划归为事先建立起来的不同的类。 w e b 页面的聚类是指在没有给定主题类别的情况下，将w e b 页面集合聚成若干个 、e b 挖掘技术 簇，并且同一簇的页面内容相似性尽可能大，而簇间相似度尽可能小。 w e b 文本挖掘可以对w e b 上大量文档的集合的内容进行总结、分类、聚类、关 联分析，以及利用w e b 文档进行趋势预测。无论文本挖掘的目的是什么，都可 以把文本挖掘的一般处理过程用下图来概括： ”8 b e 冷 收集 h t m l 文档特征库结果 输出 司忌日扣翅 t土土， 图3 2 文本挖掘的处理过程 1 文本的特征表示 w e b 文档具有有限的结构，或者根本就没有结构。这些特殊性使得现有的数 据挖掘技术无法直接应用于其上。我们需要对文本进行预处理，抽取代表其特征 的元数据。这些特征可以用结构化的形式保存，作为文档的中间表示形式。w 3 c 近来制定的蹦l “”，r d f 1 ”等规范提供了对w e b 文档资源进行描述的语言和框架。 矢量空间模型( v s m ) 是近年来应用较多且效果较好的方法之一“。在该模型中， 文档空间被看作是由一组正交词条矢量所形成的矢量空间，每个文档d 表示为其 中的一个范化特征矢量v ( d ) = ( k 。，w ( d ) ：，w ，( d ) ；：k 。，w 。( d ) ) ，其中k 。 为词条项，w 。( d ) 为k ；在d 中的