（计算机软件与理论专业论文）基于web使用挖掘的知识发现研究.pdf

基于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 使用挖掘过程，在数据 预处理阶段的事务识别步骤，介绍了一种经典的事务识别算法一 一最大前向引用( m f ) 算法。 第四章中提出了三个发现用户频繁访问模式的改进算法。首先分 析了w e b 使用挖掘中的类a p r i o r i 算法；然后在此基础上i 提出了 r da p r i o r i 改进算法；接着对数据挖掘中挖掘频繁项集的c l o s e 算法进行改进，提出了w e b 使用挖掘中的c l o s e 算法；最后结合 r da p r i o r i 算法和c l o s e 算法，又提出一个r dc l o s e 算法。通过 理论分析和实验验证，它们都能根据不同的支持度阈值有效地发 现用户的频繁访问模式。 设计开发了w e b 使用挖掘原型系统( w e bu s a g em i n i n gp r o t o t y p e s y s t e m ) 。此系统主要包含四个功能模块：数据清洗模块、会话构 造模块、m f 事务识别模块和访问模式挖掘模块，这些模块完成了 原始日志数据的预处理工作，并且实现了第四章中阐述的四个挖 掘算法：类a p r i o r i 算法，r da p r i o r i 算法，c l o s e 算法和r dc l o s e 算法。最后用真实数据对这些算法的性能进行了验证和分析。 关键词：数据挖掘、w e b 挖掘、w e b 使用挖掘、频繁访问模式 t h er e s e a r c ho f k n o w l e d g ed i s c o v e r y b a s e do nw e b u s a g em i n i n g a b s t r a c t w e b m i n i n g i st h eh o tr e s e a r c hi s s u ew h i c hc o m b i n e sv a r i o u s t e c h n o l o g i e sa n dm e t h o d sh e t w e e nd a t am i n i n ga n dw w w i ng e n e r a l w e b m i n i n gi n c l u d e st h r e er e s e a r c hd o m a i n ：w e bc o n t e n tm i n i n g 、w e b s t r u c t u r e m i n i n ga n dw e bu s a g em i n i n g i nt h e s ea r e a s ，w e bu s a g em i n i n ga i m sa tt h e r u l ed i s c o v e r yo fs i t e s v i s i t o r sb r o w s i n gb e h a v i o r ，t h ei m p r o v e m e n to fs i t e s s t r u c t u r ea n dt h e l i n k a g e s t r u c t u r e a m o n gp a g e s ，t h e e n h a n c e m e n to nt h e q u a l i t y o fw e bs e r v i c e sa n dt h ed e c i s i o ns u p p o r to nc l i e n t r e l a t i o n s h i p m a n a g e m e n to ft h ee - c o m m e r c e o nt h e b a s i so ft h ei n t r o d u c t i o no ft h e d e v e l o p m e n ts u r v e yo f w e b u s a g em i n i n g ，t h et h e s i sd i s c u s s e st h ep r o c e d u r e o fw e bu s a g em i n i n ga n ds o m et e c h n o l o g i e sr e l e v a n tt oe a c hp h r a s ei nw e b u s a g em i n i n g t h em a i nw o r ka n dn o v e li d e a so ft h et h e s i s a r es h o w e da s f o l l o w i n g ： t h ed e t a i l e dd e s c r i p t i o no ft h ed e f i n i t i o n ，c l a s s i f i c a t i o n ，c h a r a c t e r i s t i ca n d c h a l l e n g eo f w e b m i n i n g ； t h ed e t a i l e dd e s c r i p t i o no ft h ed e f i n i t i o n ，d a t as o u r c e ，a p p l i c a t i o n ，t h e m a i nr e s e a r c h8 $ e a sa n dr e l a t e dt e c h n o l o g i e so fw e bu s a g em i n i n g t h e d e t a i l e dd e s c r i p t i o no fp r o c e d u r eo fw e bu s a g em i n i n gt h a ti sb a s e do n w e bt r a n s a c t i o n t h e p r e s e n t a t i o n o fac l a s s i c a lm e t h o dc a l l e dm f a l g o r i t h mi d e n t i f i e st r a n s a c t i o n so n t h ep h r a s eo fd a t ap r e p a r a t i o n ； i nc h a p t e rf o u r t h et h e s i sp u t sf o r w a r dt h r e ei m p r o v e da l g o r i t h m sb y a n a l y z i n ga p r i o r ia l g o r i t h m o nw e b u s a g em i n i n g ，w h i c hi s f o rt h eu s eo f d i s c o v e r i n gu s e r s f r e q u e n t a c c e s s p a t t e r n s f i r s t ，p u t t i n g f o r w a r da i m p r o v e da l g o r i t h mc a l l e dr d _ a p r i o r i ，b a s e do nt h ea p r i o r ia l g o r i t h m ； t h e n ，p u t t i n gf o r w a r d ac l o s ea l g o r i t h mw h i c h i m p r o v e st h ec l o s em e t h o d t o m i n i n gf r e q u e n t i t e m s e t so nd a t a m i n i n g ；f i n a l l y , p u t t i n g f o r w a r d r d c l o s ea l g o r i t h mw h i c hi s b a s e do nr c _ a p r i o r ia l g o r i t h ma n dc l o s e a l g o r i t h m b yt h e o r e t i ca n a l y s i sa n de x p e r i m e n t a lt e s t s ，t h e s ea l g o r i t h m s c a nb eu s e dt od i s c o v e ra c c e s sp a t t e r n so fa l lt y p e so fu s e r sa n df r e q u e n t a c c e s s p a t t e r n sa c c o r d i n g t ot h e s u p p o r t t h r e s h o l dv a l u ed e c i d e d b y e x p e r t s ； t h e d e s i g na n dd e v e l o p m e n to fw e bu s a g em i n i n gp r o t o t y p es y s t e mt h i s p r o t o t y p es y s t e m c o n s i s t so ff o u rf u n c t i o nm o d u l e s ：d a t a c l e a n i n g m o d u l e 、s e s s i o nc o n s t r u c t i o nm o d u l e 、t r a n s a c t i o n i d e n t i f y i n gm o d u l e ， a n da c c e s sp a t t e r n s m i n i n g m o d u l e t h e s em o d u l e sf u l f i l l t h e p r e p r o c e s s i n go f t h eo r i g i n a ll o gd a t aa n df o u ra l g o r i t h m sw h i c hi n c l u d e a p r i o r ia l g o r i t h m ，r d a p r i o r ia l g o r i t h m ，c l o s ea l g o r i t h ma n dr d c l o s e a l g o r i t h m f i n a l l yt h ep e r f o r m a n c eo ft h e s ea l g o r i t h m si sa n a l y z e da n d v a l i d a t e db yr e a ld a t a k e y w o r d s ：d a t a m i n i n g 、w e bm i n i n g 、w e bu s a g em i n i n g 、f r e q u e n ta c c e s s p a t t e r n s 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥工业大 学硕士学位论文质量要求。 答 7 渺愀 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标志和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 盒艘王 些去坐或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签字强拟 签字日期：秆r 月；。日 学位论文版权使用授权书 本学位论文作者完全了解 金世王些太堂有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅或借阅。本人授权 金壁工些态堂 可以将学位论文的全部 或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：诱、幺坟 签字日期：面年r 月j o 同 学位论文作者毕业后去向 工作单位： 通讯地址： 诹倒 导师签名砩叼以 签字日期：加r 年r 月。日 电话 邮编 致谢 三年的硕士生涯即将结束，回首这三年，无论在学习、生活，还是在思想 意识、为人处事的态度上，我都受益匪浅。 首先，衷心感谢我的导师欧阳一鸣老师三年期间对我的精心培养。他在课 题的选择、研究和论文撰写期间给予我悉心的指导，引领我步入w e b 挖掘的殿 堂。而且，他耐心地指导我解决前进中的难题，使我独立科研的能力得到了锻 炼和提高，能够顺利完成本篇论文。这些对于我以后继续攻读博士学位打下了 坚实的基础。 同时，我要深深地感谢胡学钢教授以及人工智能和数据挖掘实验室的所有 成员。在实验室举办的研讨会中，老师和同学们的交流，不仅使我认识到自己 正在研究的工作中的不足，也使我在开展课题方面受到了颇多的启发。在这里， 我要感谢师兄汪曦东、周强和张焱师姐在研究工作中给予我的极大帮助。 此外，我还要感谢合肥工业大学和计算机与信息学院的各位老师和院系领 导对我的帮助和支持。 十分感谢在我考博期间欧阳老师和胡学钢老师对我的支持和鼓励，我能顺 利读博与他们的帮助是分不开的。 作者：陈敏 2 0 0 5 年5 月 1 1 背景 1 1 1 数据挖掘的起源 第一章绪论 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的 数据越来越多，激增的数据背后隐藏着许多重要的信息，人们对数据库的应用 已经不满足于简单的查询和检索，人们希望能够对其进行更高层次的分析，以 便更好的利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、 统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测 未来的发展趋势，缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但 知识贫乏”1 的现象。 数据挖掘是一个逐渐演变的过程，电子数据处理的初期，人们就试图通过 某些方法来实现自动决策支持，当时机器学习成为人们关心的焦点。机器学习 的过程就是将一些己知的并己被成功解决的问题作为范例输入计算机，机器通 过学习这些范例总结并生成相应的规则，这些规则具有通用性，使用它们可以 解决某一类问题。 8 0 年代人们又在新的神经网络理论的指导下，重新回到机器学习的方法 上，并将其成果应用于处理大型商业数据库。用数据库管理系统来存储数据， 用机器学习的方法来分析数据，挖掘大量数据背后的知识，这两者的结合促成 了数据库中的知识发现“1 ( k d d ：k n o w l e d g e d i s c o v e r y i n d a t a b a s e s ) 的产生。 k d d 泛指所有从源数据中发掘模式或联系的方法，人们通常用它来描述整个数 据发掘的过程，包括最开始的制定业务目标到最终的结果分析。而用数据挖掘 ( d m ：d a t am i n i n g ) 来描述使用挖掘算法进行数据挖掘的子过程。但最近人 们却逐渐发现在数据挖掘中有许多工作可以由统计方法来完成，并认为最好的 策略是将统计方法与数据挖掘有机地结合起来。 1 1 2w o b 挖掘产生的背景 伴随着网络和通信技术的飞速发展，作为全球最大的信息服务平台的 i n t e r n e t 正在以前所未有的速度渗入到人类生产和生活的各个方谣。w w w 作为 信息发布和交流的全球性媒体，它的内容涵盖了包括科研、教育、商业、金融、 军事等各个领域。正是由于w e b 上包含巨大的信息量，使得越来越多的用户感 觉到在w w w 上寻找自己想要的信息犹如“大海捞针”一样困难，因此给用户 提供某种工具来帮助定位、分析和评价所需的信息变得越来越有必要。 另一方面，各种基于w e b 的网络应用也如雨后春笋般地发展起来，诸如网 上商店，网上银行，远程教育，远程医疗和电子政务等。尤其是以电子商务为 代表的网上交易模式的成功启用，为了更好地、更有针对性地进行一些宣传和 促销活动，商业机构对用户访问模式的追踪和分析变得愈发熏要。因此将数据 挖掘和w w w 这两个领域结合起来，就形成了当前的一个热门研究课题一一 w e b 挖掘。 1 2 研究意义 由于w w w 在传播与交换信息方面的快捷与便利，互联网以惊人的速度作为 商务处理和信息发布的平台持续发展。大部分w e b 站点在建立时由设计人员根 据自身经验与观点进行分类组合，而没有考虑到用户的浏览行为，没有从使用 者的角度对站点进行优化和改进。不合理的站点设计在为用户带来不便的同时， 也会使自己在激烈的竞争中败落。同时，随着w e b 技术的发展，各类电子商务 网站风起云涌，追踪用户浏览行为到每一次鼠标点击的能力使得供应商与终端 用户之间的关系比以前更密切。 因此在当今这个信息社会，w e b 站点管理人员如何能够更加了解客户，提 供更加个性化的内容来满足不同客户的需求以吸引客户，就成为一项十分重要 而紧迫的研究课题。w e b 站点服务器每天产生大量的日志，其中蕴含了关于用 户在网上的行为的丰富数据，分析这些数据能够发现有意义的隐藏访问模式规 则，这对于分析和改善站点的使用情况及资源配置具有重要的意义。随之产生 的v e b 使用挖掘的目的就在于此，它是通过研究w 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 使用挖掘的体系结构、数据准备、事务识别以及频繁访 问路径的挖掘过程。各章内容的安排如下： 第一章绪论：简要介绍了本论文的课题背景、目的和意义，以及论文的 2 主要工作。 第二章从数据挖掘到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 算法，然后提出了三个改进的挖掘算法一 一r d _ a p r i o r i 算法，c l o s e 算法和r d c l o s e 算法，并对它们的性 能进行了理论分析。 第五章w e b 使用挖掘原型系统和算法比较：用实际数据对本文中提出的挖 掘算法进行验证，并对各算法的性能进行了比较。还设计了一个 w e b 使用挖掘原型系统。 第六章结束语：对本论文的总结，并提出了今后的进一步工作。 第二章从数据挖掘到w e b 挖掘 2 1 数据挖掘概述 2 1 1 数据挖掘和知识发现 k d d 这一术语首先出现于1 9 8 9 年在美国底特律召开的第1 1 届国际人工智能 联合会议的专题讨论会上，之后有很多人给出了k d d 的定义。目前大家公认的 k d d 的严格定义是在1 9 9 6 年知识发现国际会议上由f a y y a d 、p i a t e s t s k y 、s h a p i r o 和s m y t h 提出： 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 si st h en o n t r i v i a lp r o c e s so fi d e n t i f y i n g v a l i d ，n o v e l ，p o t e n t i a l l yu s e f u l ，a n du l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si nd a t a k d d 是从数据集中提取出有效的、新颖的、有潜在作用的、可信的，并能 最终可被理解的模式的非平凡过程“1 。 上面的定义中，有几个概念需要作进一步解释： 数据集是一组事实f ( 如关系数据库中的记录) ； 模式是用语言l 来表示的一个表达式e ，它可用来描述数据集f 的某个子集 f e ，e 作为一个模式要求它比数据子集f e 的枚举要简单( 所用的描述信息量要 少】： 过程通常指多阶段的一个过程，涉及数据准备、模式搜索、知识评价，以 及反复的修改求精。该过程要求是非平凡的，意思是簧有一定程度的智能 性、自动性( 仅仅给出所有数据的总和不能算作是一个发现过程1 ； 有效性是指发现的模式对于新的数据仍保持有一定的可信度； 新颖性要求发现的模式应该是新的； 潜在的可用性是指发现的知识将来有实际效用，如用于决策支持系统里可 提高经济效益； 最终可理解性要求发现的模式能被用户理解。目前它主要是体现在简洁性 上。有效性、新颖性、潜在有用性和最终可理解性综合在一起可称之为兴 趣性( i n t e r e s t i n g n e s s ) 。 从知识发现的定义看出，知识发现和数据挖掘有一定的重合度。k d d 的整 个过程包括在数据库中用数据挖掘算法提取模型，以及围绕数据挖掘进行的预 处理和结果表达式等一系列的计算步骤。尽管数据挖掘是整个过程的中心，但 它通常只占整个过程的1 5 2 5 的工作量。数据挖掘着眼于设计高效的算法， 以达到在巨量数据库中发现知识的目的。它充分利用了机器学习、人工智能、 4 模糊逻辑、人工神经网络、分形几何等理论和方法。 k k d 过程是一个以知识使用者为中心、人机交互的探索过程，它由以下步 骤组成”1 ( 如图2 1 所示) ： 1 数据清理( 消除噪声或不一致数据) 2 数据集成( 多种数据源可以组合在一起) 3 数据选择( 从数据库中检索与分析任务有关的数据) 4 数据变换( 数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作1 5 数据挖掘( 基本步骤，使用智能方法提取数据模式) 6 模式评估( 根据某种兴趣度度量，识别表示知识的真正有趣的模式) 7 知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 削2 1知识发现的过程 k d d 是从数据库中发现有用知识的全过程，是应用特定数据挖掘算法和 评价解释模式的一个循环反复的过程，并要对发现的知识不断求精深化，使其 易于理解；而数据挖掘是知识发现过程中的一个关键步骤，即利用算法从数据 库中抽取模式，不包括数据的预处理、领域知识结合以及结果的评价，具有可 接受的计算效率。 2 1 2 数据挖掘模式 数据挖掘的功能用于指定数据挖掘任务中要找的模式类型。在某些情况 下，用户不知道他们的数据中什么类型的模式是有趣的，因此可能想并行地搜 索多种不同的模式。这样，重要的是，数据挖掘系统要能够挖掘多种类型的模 式，以适应不同的用户需求或不同的应用。此外，数据挖掘系统应当能够发现 各种粒度( 即不同的抽象层) 的模式。由于有些模式并非对数据库中的所有数 据都成立，通常每个被发现的模式带上一个确定性或“可信度”度量。 数据挖掘功能以及它们可以发现的模式类型介绍如下： 类概念描述 数据可以与类或概念相关联。用汇总的、简洁的、精确的方式描述每个类 和概念可能是有用的。这种类或概念的描述称为类概念描述( c l a s s c o n c e p t d e s c r i p t i o n ) 。这种描述可以通过下述方法得到：1 ) 数据特征化；2 ) 数据区分： 3 ) 数据特征化和比较。 数据特征化( d a t ac h a r a c t e r i z a t i o n ) 是目标类数据的一般特征或特性的汇 总。通常，用户指定类的数据通过数据库查询收集。有许多有效的方法，将数 据特征化和汇总。例如，基于数据立方体的o l a p 上卷操作可以用来执行用户 控制的、沿着指定维的数据汇总。数据特征的输出可以用多种形式提供。包括 饼图、条图、曲线、多维数据立方体和包括交叉表在内的多维表。 数据区分( d a t ad i s c r i m i n a t i o n ) 是将目标类对象的一般特性与一个或多个对 比类对象的一般特性比较。目标类和对比类由用户指定，而对应的数据通过数 据库查询检索。 关联分析 关联分析( a s s o c i a t i o na n a l y s i s ) 发现关联规则，这些规则展示属性一值频繁 的在给定数据集中一起出现的条件。关联分析广泛用于购物篮或事务数据分析。 购物篮是顾客在一次事务中所购买的项的集合，所谓的事务是一个明确定义的 商业行为。事务数据库研究的一个最普通的例予就是寻找项的集合，或叫做项 集( 在一些事务中一起出现的项) 。商家可以使用这些信息来改善商店中的这些 物品的堆放，或邮购目录页的布局。包含该项集的事务百分数叫做该项集的支 持度。对于有研究价值的项集，它的支持度必须比用户指定的最小值要大，这 样的项集叫频繁项集。 我们希望从一个销售事务的数据库中挖掘出项之间的重要关联，比如说根 据事务中某些项的出现频率，可以推测出事务中其它项的出现频率。设 i = i 1 ，i 2 ，i 。) 为项的集合。设d b 为事务集合，其中每一个事务t 都是项的集 合，且有t g i 。设x 为一个项集。当且仅当x t 时我们说事务t 包含x 。关 联规则是形如x j y 的蕴涵式，其中x c i ，y c i ，且x n y = 中。如果d b 中包 含x 的事务中有c 也包含y ，规则x y 在事务集d b 中具有置信度c 。如果 d b 中有s 的事务包含x u y ，那么规则x 等y 在事务集d b 中具有支持度s 。 6 置信度可以表示规则的确定性，支持度表示模式的潜在有用性。通常人们都愿 意研究一些具有高支持度的关联规则。具有高置信度和高支持度的规则被称为 强关联规则。挖掘关联规则的基本任务就是挖掘出大型数据库中的强关联规则。 挖掘关联规则的问题可以分为两个阶段：l 、发现大项集，也就是事务支 持度s 大于预先给定的最小支持度阙值的项的集合。2 、使用大项集来产生数据 库中最信度c 大于预先给定的最小置信度阚值的关联规则。 分类和预测 分类( c l a s s i f i c a t i o n ) 是这样的过程，它找出描述并区分数据类或概念的模型 ( 或函数) ，以便能够使用模型预测类标记未知的对象类。导出模型是基于对训 练数据集( 即其类标记已知的数据对象) 的分析。导出模式可以用多种形式表 示，如分类( i f t h e n ) 规则、判定树、数学公式或神经网络。判定树是一个 类似于流程图的树结构，每个节点代表一个属性值上的测试，每个分支代表测 试的一个输出，树叶代表类或类分布。判定树容易转换成分类规则。当用于分 类时，神经网络是一组类似于神经元的处理单元，单元之间加权连接。 分类可以用来测试数据对象的类标记，当被预测的值是数值数据时，通常 称之为预测( p r e d i c t i o n ) 。尽管预测可以涉及数据值预测和类标记预测，通常预 测限于值预测，并因此不同于分类。预测也包含基于可用数据的分布趋势识别。 聚类分析 聚类( c l u s t e r i n g ) 分析是依据样本间关联的量度标准将其自动分成几个群 组，且使同一群组内的样本相似，而属于不同群组的样本相异的一组方法。一 个聚类分析系统的输入是一组样本和一个度量两个样本间相似度( 或相异度) 的标准。聚类分析的输出是数据集的几个组( 类) ，这些组构成一个区分或一个 分区结构。聚类分析的一个附加结果是对每个类的综合描述，这种结果对于更 迸一步深入分析数据集的特性是尤其重要的。 聚类的样本是用度量指标的一个向量表示，或更正式的说法是，用多维空 间的一个点表示。同类中的样本比属于不同类的样本彼此具有更高的相似性。 聚类方法尤其适合用来探讨样本问的相互关联关系从而对一个样本结构做一个 初步的评价。人们能够对维、二维或三维的样本进行聚类分析，但是大多数 现实问题涉及到更高维的聚类。对于人们来说凭赢觉解释高维空间包含的数据 是非常困难的。 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。 这些数据对象是孤立点( o u t l i e r ) 。大部分数据挖掘方法将孤立点视为噪声或异常 而抛弃。然而，在一些应用中( 如欺骗检测) ，罕见的事件可能比正常出现的那 些更有趣。孤立点数据分析称作孤立点挖掘( o u t l i e rm i n i n g ) 。 孤立点可以使用统计试验检测。它假定一个数据分布或概率模型，并使用 距离量度，到其他聚类的距离很大的对象被视为孤立点。基于偏差的方法通过 考察一群对象主要特征上的差别识别孤立点，而不是使用统计或距离度量。 例如，孤立点可以发现信用卡欺诈。通过检测一个给定帐号与正常的付费 相比，以付款数额特别大来发现信用卡欺骗性使用。孤立点值还可以通过购物 地点和类型，或购物频率来检测。 演变分析 数据演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的对象的规律或 趋势，并对其建模。尽管这可能包括时间相关数据的特征化、区分、关联、分 类或聚类，这类分析的不同特点包括时间序列数据分析、序列或周期模式匹配 和基于类似性的数据分析。 2 2w o b 挖掘的定义 应用领域的需求是推动技术发展的源动力。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 的数据挖掘比面向单个数据仓库的数据挖掘要复杂得多。 w e b 挖掘的定义是从数据挖掘的概念扩展而来。简单地说，w e b 挖掘是指 从w e b 服务器上的数据文件中提取人们感兴趣的知识的过程。这里所谓的“兴 趣”与我们前面讲数据挖掘时提到的含义相同。w e b 挖掘其实就是对文档的内 容、可利用资源的使用以及资源之间的关系进行分析，以实现对w e b 存取模式、 w e b 结构和规则的分析，以及动态w e b 内容的查找。 w e b 挖掘能给我们带来什么呢? 让我们先看一个例子，如果在y a h o o ! 上 查找“d a t a m i n i n g ”，在显示的结果中会出现有关采矿公司的链接。所以在网上 寻找过资料的人大多会抱怨接索引擎的查询结果。然而w 曲挖掘技术发展成熟 后，此种情况就会消失。w e b 挖掘可以将w e b 上的文档进行分类、寻找文档主 题、汇总搜索结果，使用户在i n t e r n e t 上查找信息更加全面准确。对w e b 站点 分析的结果可用于重新组织w e b 站点结构，以便更好地为用户提供服务。冗长 的遍历路径或是包含重要的信息但访问率很低的页面，都说明站点设计不合理。 借助用户对浏览站点情况的分析，可以对分布式或并行w e b 服务器页面布局和 高速缓存机制进行改进；也可以为用户提供最受欢迎的站点列表，帮助用户导 航。用于数据库知识发现的特征化( c h a r a c t e r i z a t i o n ) 、分类( c l a s s i f i c a t i o n ) 、 预测( p r e d i c t i o n ) 、聚类( c l u s t e r i n g ) 、关联( a s s o c i a t i o n ) 分析和序列模式 ( s e q u e n t i a lp a t t e r n ) 分析等技术都可以用于w e b 上的知识发现。 2 3w e b 挖掘的分类 按照研究的w e b 数据对象，w e b 挖掘可以分为三类：w e b 内容挖掘( w 曲 c o n t e n t m i n i n g ) 、w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 采lw e b 使m 挖掘( w e b u s a g em i n i n g ) ”，“”1 ，如图2 - 2 所示的w e b 挖掘的分类。 图2 2w e b 挖掘分类 在实际应用中，w e b 挖掘的三种任务不是孤立的，而是相辅相成的。尤 其是w e b 内容挖掘和结构挖掘之间关系更为紧密，因为w e b 文档中也包含有 链接。有的时候，w e b 内容挖掘和使用挖掘相结合能够更好的完成某个应用任 务。例如：在【2 2 】中，j o a c h i m s 等人将w e b 内容和使用纪录相结合建立了一个 软件浏览智能体。这个智能体能够帮助用户更好的浏览网站。总之，w e b 挖掘 的这三个研究方向在实际应用过程中并不是孤立的，而是相互交叉、相互渗透 和相互联系的。 2 3 1 w e b 内容挖掘 w e b 内容挖掘是从w e b 文档内容或其描述中抽取知识的过程”3 。w e b 文档 包含了各种不同种类的数据类型，例如：文本、图片、声音、视频、元数据( 是 指关于数据的数据，用以描述数据的属性) 和超链接等。对于这些不同类型数据 的挖掘通常称之为多媒体数据挖掘3 。从这个方面来说，w e b 内容挖掘是一种 多媒体数据挖掘。另外，w e b 内容数据是由非结构化数据( 例如：自由文本) 、 9 半结构化数据( 例如：h t m l 文档) 和结构化数据( 例如：由h t m l 页面生成数据 表) 构成。将数据挖掘的技术应用于非结构化数据的研究又称之为文本挖掘n “。 由此，我们可以看出w e b 内容挖掘的研究范围非常广泛。 w e b 内容挖掘的研究方法可以分为两类：基于智能体的方法( a g e n t b a s e d a p p r o a c h ) 和数据库方法( d a t a b a s ea p p r o a c h ) ”3 。基于智能体的方法是运用软 件系统( 或智能体) 执行w e b 内容挖掘的任务，例如：当前绝大多数搜索引擎都 是用这种方法。通常，基于智能体的w e b 挖掘系统分为三类：智能化的搜索智 能体( i n t e l l i g e n t s e a r c h a g e n t s ) “3 、信息过滤分类( i n f o r m a t i o n f i l t e r i n g c a t e g o r i z a t i o n ) “”3 和个性化w e b 智能体( p e r s o n l i z e dw e b a g e n t s ) “8 - 1 “。 适用于w e b 内容挖掘的数据库方法是运用适当的技术把半结构化的w e b 数 据组织成更加结构化的数据集合，并且使用标准的数据库查询机制和数据挖掘 技术来分析这些数据集。典型的数据库方法有多层次数据库( m u l t i p l el a y e r e d d a t a b a s e s ，m l d b ) ”“”1 和w e b 查询系统( w e bq u e r ys y s t e m s ) “”。 2 3 2w e b 结构挖掘 w e b 结构挖掘是从w w w 的组织结构和链接关系中推导知识的过程。它试 图发现w e b 链按结构中潜在的模型，而这种模型是建立在超链拓扑基础上的。 同时，挖掘出的模型能够被用于w e b 页面分类，并且有助于生成一些有用的信 息( 例如w e b 站点之间的相似性和关系信息) 。值得一提的是，w e b 结构挖掘能 够用于发现某个主题的权威网站和关于此主题的所有网站的概貌。这方面工作 的代表有p a g e r a n k ”“、h i t s 0 5 1 和c l e v e r ”。 p a g e r a n k 技术不仅提高了搜索引擎的有效性而且改善了它们的效率。 p a g e r a n k 被用于衡量某个页面的重要性，并且根据传统搜索引擎搜索返回的页 面的重要性来进行排序。这种方法有效性的一个最好例证就是g o o g l e 的成功。 一个页面的p a g e r a n k 值是根据此页面的导入链接( b a c k l i n k ) 数目计算得来的。 导入链接是指指向此页面的链接，而不是由此页面发出的链接。p a g e r a n k 方法 并不是简单的计算导入链接的数目，而是根据来自不同重要性页面的导入链接 赋予不同的权值( w e i g h t i n g ) ，即来自越重要页面的导入链接的权值越大。 p a g e r a n k 的基本思想是：一个页面被多次引用，则这个页面很可能是重要的； 一个页面尽管没有被多次引用，但是被一个重要页面引用，则这个页面也可能 是重要的；一个页面的重要性被均分并被传递到它所引用的页面。例如：给定 某个页面p ，b 。表示页面p 的导入链接集合，f p 表示页面p 发出的链接集合， 则页面p 的p a g e r a n k 可定义为： 1 0 p r ( p ) ：c p r ( q ) 而脚 这里n q = f q f 。常数c ( o c 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 从大到小依次排列输出。c l e v e r 方法本质上和 p a g e r a n k 是一致的。 2 3 3w e b 使用挖掘 w e b 使用挖掘是从w e b 使用数据或w e b 日志中抽取“感兴趣”的模式的 过程”1 。w w w 中的每个服务器都保留了访问日志( w 曲a c c e s sl o g ) ，记录了 关于用户访问和交互的信息，分析这些数据有重要的意义。目前，国内外对这 方面的研究不仅仅局限于对w e b 日志的挖掘，从更广泛的意义上说是从多方 面对用户使用w e b 的行为规律的分析和研究。 w e b 使用挖掘主要有两个研究发展方向：一般化的访问模式追踪( g e n e r a l a c c e s sp a t t e r nt r a c k i n g ) 。“”“1 和个性化的使用记录追踪( c u s t o m i z e du s a g e t r a c k i n g ) 。 一般化的访问模式追踪是从w e b 日志中挖掘用户的访问模式和预测用户 的访问趋势。这些挖掘出来的模式和规则对w e b 站点的改进包括“： 使用户所关心的页面更加容易访问； 使用户所关心的超链接更加醒目； 链接相关的页面： 聚合相似的页面； 增加缓冲预取机制、改善服务器响应时间； 合理设置广告； 个性化的使用记录追踪是挖掘某一类或某几类用户( 甚至某个用户) 访问 网站的行为规律，这使得网站能够动态地为用户提供个性化的服务以极大地满 足用户的需求。所谓的个性化服务是指w e b 站点为适应某一类或某一个特定 用户的需要而实时地调整数据的组织和显示。一种实现个性化服务的方法是允 许用户手工定制w e b 站点显示选项，系统将记住每个用户的定制，并在该用 户再次进入该网站时进行相应的调整。例如微软的m s n 站点 ( h t t p ：w w w i n s l l c o r n ) 允许用户只看到用户自己选择的新闻栏目。 目前，主要有两种w e b 使用挖掘方法：基于w e b 事务的方法和基于数据立 方体的方法。下面分别介绍这两种方法： 基于w e b 事务的w e b 使用挖掘方法 基于w e b 事务的w e b 使用挖掘方法，最早是由c h e n 等人”提出的。这种 方法在预处理时将日志数据分割成一系列的事务，然后采用与关联规则相类似 的方法挖掘频繁访问模式。本文对于这种挖掘方法将会在第三章的第三节做详 细地介绍。 基于数据立方体的w e b 使用挖掘方法 h a n “等人提出的基于数据立方体的w e b 使用挖掘方法如图2 3 所示，他 根据