（计算机应用技术专业论文）web使用挖掘算法研究与实现.pdf

w e b 使用挖掘算法研究及实现 摘要 随着网络技术的高速发展，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 e b 挖掘的理论知识，分析了数据挖掘的研究 焦点； 其次，在讨论w e b 访问同志预处理的基础上，设计出由用户会话求最大 向前指引路径的算法；同时给出了一种新的会话构造方法一基于时间和引用 的启发式方法，该方法不仅利用了用户会话的时间特性，而且考虑了用户的浏 览特性，在一定程度上方便了用户频繁访问模式的挖掘； 提出一种发现用户频繁访问模式的算法( f a p m i n i n g ) ，该算法可以用于 发现不同类型的网站用户的访问模式，并且可以根据专家设定的支持度阈值发 现用户的频繁访问模式。 最后，设计开发了w e b 使用挖掘实验系统，在会话识别模块实现了基于 时间和引用的会话构造方法，并将其与其他流行方法进行了比较；在访问模式 模块实现了本文提出的f a p m i n i n g 算法。 关键词：数据挖掘，w e b 挖掘，w e b 使用挖掘，数据预处理，会话构造、频繁 访问模式，f a p m i n i n g 算法 t h er e s e a r c ha n di m p l e m e n t o fa l g o r i t h mo nw e bu s a g em i n i n g 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 fn e t w o r kt e c h n o l o g y , i n f o r m a t i o no n l i n e i n c r e a s e so na ne x p o n e n t i a lb a s i s w e bb e c o m e st h em o s ti m p o r t a n tc a r r i e rt h a t s t o r e s r e l e a s e sa n do b t a i n si n f o r m a t i o ni n f o r m a t i o n w e bm i n i n gi st h ea p p l i c a t i o n o ft r a d i t i o n a ld a t am i n i n gt e c h n o l o g yi nt h ew e be n v i r o n m e n t ，f i n d i n go u tt h e u s e r sb r o w s i n gp a t t e r na n dr e l e v a n tw e bp a g e s t h ep u r p o s eo fs t u d yo nt h e m i n i n gi st of m do u tt h ea c t i o np a r e mo fb r o w s i n go n l i n e ，i m p r o v et h ew e b s i t e s s t r u c t u r ea n dh y p e r l i n ks t r u c t u r ea n dt h es e r v i c eq u a l i t yo fw e b s i t e s ，p r o v i d e s u p p o r tf o rt h ep o l i c yd e c i s i o n so nt h ec l i e n t s r e l a t i o n s h i pm a n a g e m e n ti n e - c o m m e r c e t h et h e s i sf o c u s e so nt h es e a r c ho fm i n i n ga l g o r i t h mf o rw e b i n c l u d i n gt h ef o l l o w i n gc o n t e n t s ： f i r s t l y ，t h et h e o r e t i c a lk n o w l e d g eo nd a t am i n i n ga n dw e bm i n i n gi s i n t r o d u c e d ，i na d d i t i o nt ot h ea n a l y s i so f r e s e a r c hf o c u s s e c o n d l y , t h ea l g o r i t h mf o rt h em a x i m u mf o r w a r ds e s s i o np a t hi sd e s i g n e do n t h eb a s i so fw e b s i t e sa c c e s sp r e p r o c e s s i n g t h e n , an e ws e s s i o nc o n s t r u c t i o n m e t h o d ，a l le l i c i t a t i o nm e t h o db a s e do nt i m ea n dc i t a t i o n , i si n t r o d a c e d ，w h i c hn o t o n l yt a k e sa d v a n t a g eo f f e a t u r e so nt i m e ，b u tt a k e si n t oa c c o u n tt h eu s e r sb r o w s i n g h a b i t s i t ，t os o m ee x t e n t , b r i n g su s e r sc o n v e n i e n c eo nt h em i n i n gf o rt h ef r e q u e n t a c c e s sp a t t e r n ip u tf o r w a r daf a p - m i n i n gm e t h o d w h i c hc a nb eu s e dt of i n do u tt h eu s e r ，s a c c e s sp a t t e mo nd i f f e r e n tt y p e so f w e b s i t e s ，a n do b t a i nt h ef r e q u e n ta c c e s sp a 仕e m a c c o r d i n gt ot h et h r e s h o l ds e tb ye x p e a s a tl a s t ，a ne x p e r i m e n t a ls y s t e mf o rw e ba p p l i c a t i o nm i n i n gi sd e v e l o p e d , w h i c hi m p l e m e n t st h es e s s i o nc o n s t r u c t i o nm e t h o db a s e do nt i m ea n dc i t a t i o n f a p m i n i n ga l g o r i t h mi si m p l e m e n t e di na c c e s sp a t t e mm o d u l e k e yw o r d s ：d a t am i n i n g ，w e b m i n i n g ，w e ba p p l i c a t i o nm i n i n g ，d a t a p r e p r o c e s s i n g ，s e s s i o nc o n s t r u c t i o n ，f r e q u e n ta c c e s sp a t t e r n , f a p m i n i n gm e t h o d i i 插图清单 图卜l 数据挖掘的基本过程6 图1 2w e b 数据挖掘的工作流程9 图卜3w e b 数据挖掘分类1 0 图2 - l 一个简单w e b 站点的拓扑结构1 7 图3 - i ( a ) f p t r e e ( a ) 2 6 图3 - i ( b ) f p - t r e e ( b ) 2 6 图3 2 用户访问网站的路径2 7 图4 1w e b 使用挖掘实验体统体系结构3 2 图4 2 响应状态分析图3 4 图4 3 页面请求成功i p 统计图3 4 图4 - 4 页面请求成功点击数统计图3 4 图4 - 5 长度为i - 3 的短会话表分析图3 8 图4 - 6i p - 2 1 8 6 9 1 3 2 2 0 8 的用户频繁访问模式树3 9 v 表格清单 表2 1 清洗过的w e b 服务器访问日志的中间文件1 7 表3 - i 事务数据库d 2 5 表3 - 2 用户会话片断3 0 表3 3f p g r o w t h 算法挖掘结果3 l 表4 - i 访问日志整体统计表3 3 表4 2 页面请求成功的校内用户统计表3 5 表4 - 3 访问次数前1 0 位的页面统计表3 6 表4 4 基于会话时间方法的比较结果3 7 表4 - 5 基于页面访问时间的比较结果3 7 表4 - 6 会话时间的会话长度比较分析表3 8 表4 7i p = 2 1 8 6 9 1 3 2 2 0 8 的用户会话表3 9 表4 8i p = 2 1 8 6 9 1 3 2 2 0 8 的用户访问模式表4 0 v 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得盒目巴王些厶堂 或其他教育机构的学位或 证书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名 签字日期：1 ，碑1 1 月f 日 学位论文版权使用授权书 本学位论文作者完全了解盒目巴些盔堂有关保留，使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权金胆：至些厶堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文储签名：壶底， 签字日期：蛔年1 1 月i f 日 学位论文作者毕业后去向 工作单位： 通讯地址： 导师签名 签字日期 电话： 邮编； 6 日 钟r ， 歹片易纠， 他帕批1 ，俨咖 致谢 三年的研究生生活即将划上句号，在这三年的学习和生活中，老师、同学、 亲人、朋友给予我的关心和帮助将永远留在我美好的记忆深处。 首先，我衷心感谢我的导师胡学钢教授，感谢他对我的指导与鼓励。在整 个研究过程中，从研究方向的确立、研究材料的搜集，到算法分析以及论文的 规范写作方法，都得到了胡学钢导师的悉心指导。在三年的学习生活中，胡老 师开阔的学术思维、严谨的治学态度、勤奋务实的工作作风、乐观豁达的性格 和平易近人的态度给我留下了深刻的印象，使我受益终生。我的硕士论文倾注 了胡老师的大量心血，没有他的指导和帮助，我是不可能完成我的硕士学位论 文的。在此，致以深深的敬意! 同时，我深深感谢王浩教授、侯整风教授、周国祥教授等老师，是他们构 建了合肥工业大学优良的、积极向上的学习环境。三年硕士求学期间的收获是 全方位的，不仅学会了专业领域的丰富知识，使自身知识结构得以重构，更重 要的是学到了科学研究的态度与方法。 最后真诚地感谢我的同学、同事们和我的家人，是他们的鼓励、关心、支 持和帮助使本文顺利完成。谢谢你们! 作者：李森 2 0 0 7 年1 1 月 第一章数据挖掘与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 1 引言 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，千万 万个数据库被用于商业管理、政府办公、科学研究和工程开发等等，并且这一 势头仍将持续发展下去。随着数据库技术的迅速发展以及数据库管理系统的广 泛应用，人们积累的数据越来越多。大量信息在给人们带来方便的同时也带来 了一大堆问题：第一是信息过量，难以消化；第二是信息真假难以辨识；第三 是信息安全难以保证；第四是信息形式不一致，难以统一处理。人们开始考虑： “如何才能不被信息淹没，而是从中及时发现有用的知识、提高信息利用率? ” 爆炸式增长的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层 次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据 的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据 现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致 了“数据爆炸但知识贫乏”的现象。人们迫切需要利用一种崭新的技术和工具智 能地、自动地将数据转变为知识，这种情况下数据挖掘和知识发现( k d d ) 技术 就应运而生。 1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能联合会议的专题讨 论会上首次出现数据库中的知识发现k d d ( k n o w l e d g ed i s c o v e r yi n d a t a b a s e s ) ”。这个术语，泛指所有从源数据中挖掘模式或联系的方法，包括最 开始的制定业务目标到最终的结果分析。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年 都举行k d d 专题讨论会，汇集来自各个领域的研究人员和应用开发者，集中 讨论数据统计、海量数据分析算法、知识表示、知识运用等问题。随着参与人 员的不断增多，k d d 国际会议发展成为年会。1 9 9 8 年在美国纽约举行的第四 届知识发现与数据挖掘国际学术会议不仅进行了学术讨论，并且有3 0 多家软 件公司展示了他们的数据挖掘软件产品，不少软件己在北美、欧洲等国得到应 用。 随着i n t e m e t 飞速发展和普及，网上的数据资源空前丰富，以每月2 0 的 速度急剧增加，目前i n t e r n e t 已经发展成为一个巨大、分布广泛、全球性的信 息服务中心，涉及教育、政府、电子商务、新闻、广告、消费信息、金融管理 和许多其它信息服务。i n t e r n e t 的普及和发展为人们带来了巨大的社会效益， 也为信息科学的研究带来了巨大的机遇和挑战。 虽然网络可以迅速便捷地为人们带来大量信息，但在实际应用中，当需要 从网络上获取信息时，有用信息往往会被大量的无用信息所淹没，使用户处于 无所适从的境地。与此同时，还有许多其它问题伴随而来：诸如信息真假难以 辨识；信息安全难以保证；信息形式不一致，难以统一处理等等。因此，如何 快速准确的获取所需信息、如何获得信息之间潜在的知识以及如何提供个性化 的服务，己经成为急需解决的问题。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 的行为规律的分析和研究。 1 2 数据挖掘 用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量 数据背后的知识，这两者的结合促成了数据库中的知识发现的产生。实际上， 数据库中的知识发现是- i 7 交叉性学科，涉及到机器学习、模式识别、统计学、 智能数据库、知识获取、数据可视化、高性能计算、专家系统等多个领域。从 数据库中发现出来的知识可以用在信息管理、过程控制、科学研究、决策支持 等许多方面。 数据挖掘是k d d 最核心的部分，是采用机器学习、统计等方法进行知识 学习的阶段。数据挖掘算法的好坏将直接影响到所发现知识的好坏。目前大多 数的研究都集中在数据挖掘算法和应用上。人们往往不严格区分数据挖掘和数 据库中的知识发现，把两者混淆使用。一般在科研领域中称为k d d ，而在工 程领域则称为数据挖掘( ”7 f 1 9 j 。 1 2 1 数据挖掘的定义 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在 有用的信息和知识的过程f ”。 与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义 2 包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感 兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海 皆准的知识，仅支持特定的发现问题。即所有发现的知识都是相对的，是有特 定前提和约束条件，面向特定领域的，同时还要能够易于被用户理解，最好能 用自然语言表达所发现的结果。 数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的 大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决 策的关键性数据。简而言之，数据挖掘其实是类深层次的数据分析方法j 。 因此，数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进行探 索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的 先进有效的方法。 现在数据挖掘技术在商业应用中已经可以马上投入使用，因为对这种技术 进行支持的海量数据搜集、强大的多处理器计算机、数据挖掘算法三种基础技 术已经发展成熟。f r i e d m a n 1 9 9 7 列举了四个主要的技术理由激发了数据挖掘 的开发、应用和研究的兴趣p 2 j ： ( 1 ) 超大规模数据库的出现，例如商业数据仓库和计算机自动收集的数 据记录； ( 2 ) 先进的计算机技术，例如更快和更大的计算能力和并行体系结构； ( 3 ) 对巨大量数据的快速访问； ( 4 ) 对这些数据应用精深的统计方法计算的能力。 因此可以说，数据挖掘是信息技术发展到定阶段的必然产物，是拥有大 规模数据库、高效的计算能力、经营管理的压力和有效的计算方法后的产物， 是从存放在数据库、或其他信息库大量数据中挖掘有用知识的一个过程。 1 i2 2 数据挖掘的常用技术 人工智能、数据库技术、概率与数理统计是数据挖掘技术的三大支柱。人 工智能中一些已经成熟的方法和技术在数据挖掘中得以利用，例如：人工神经 网络、决策树、遗传算法、近邻搜索算法、规则推理、模糊逻辑等。 ( 1 ) 关联分析 关联分析1 6 j 用于寻找数据库中值的相关性，目的就是为了挖掘出隐藏在数 据间的相互关系。常用的关联分析技术是关联规则和序列模式。关联规则用于 寻找在同一个事件中出现的不同项的相关性。序列模式与关联模式相仿，而把 数据之间的关联性与时间联系起来【l q 。为了发现序列模式，不仅需要知道事 件是否发生，而且需要确定事件发生的时间。 ( 2 ) 分类分析 分类模式是使用一个分类函数( 分类器) ，能够把数据集中的数据项映射 到某个给定的类上。分类模式往往表现为一棵分类树【2 0 】，根据数据的值从树 根开始搜索，沿着数据满足的分支往上走，走到树叶就能确定类别。分类分析 法的输入集是一组记录集合和几种标记。 ( 3 ) 聚类分析 聚类分析法的输入集是一组未标定的记录，也就是说此时输入的记录还没 有被进行任何分类。聚类模式把数据划分到不同的组中，组之间的差别尽可能 大，组内的差别尽可能小【2 l 】。 ( 4 ) 人工神经网络 神经网络近年来越来越受到人们的关注，因为它为解决复杂度很大的问题 提供了一种相对来说比较有效的简单方法。神经网络可以很容易地解决具有上 百个参数的问题。神经网络常用于两类问题：分类和回归。神经网络是建立在 可以自学习的数学模型的基础之上的。它可以对大量复杂的数据进行分析，并 可以完成对人脑或其他计算机来说极为复杂的模式抽取及趋势分析。神经网络 系统由一系列类似于人脑神经元一样的处理单元组成，称之为节点( n o d e ) 。 这些节点通过网络彼此互连，如果有数据输入，它们便可以进行确定数据模式 的工作。 ( 5 ) 决策树 决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。 决策树是通过一系列规则对数据进行分类的过程。采用决策树，可以将数据规 则可视化，其输出结果也容易理解。决策树方法精确度比较高，不像神经网络 那样不易理解，同时系统也不需要长时间的构造过程，因此比较常用。 ( 6 ) 遗传算法 遗传算法是一种基于生物进化理论的优化技术。其基本观点是“适者生 存”，用于数据挖掘中，则常把任务表示为一种搜索问题，利用遗传算法强大 的搜索能力找到最优解。具体地讲，就是模仿生物进化的过程，反复进行选择、 杂交和突变等遗传操作，直至满足最优解。 ( 7 ) 最近邻居方法 将数据集合中每个记录进行分类的方法。它的基本思想是在给定数据 后，考虑在训练数据集中与该新数据距离最近( 最相似) 的所有数据，根据这 些数据所属的类别判定新数据所属的类别。 ( 8 ) 统计分析法 在数据库或其它数据集的各项之间建立两种关系，即能用函数公式表示确 定关系的函数关系和不能用函数公式表示但有相关确定关系的相关关系，对它 们的分析可采用回归分析、相关分析、主成分分析等。 ( 9 ) 可视化技术 4 数据集中包含大量的数据，并且在数据集背后也暗含着各种数据模型，将 如此大量的数据可视化需要复杂的数据可视化工具。数据挖掘和数据可视化可 以很好地协作。就数据可视化系统本身而言，由于数据集中的数据量很大，很 容易使分析人员变得不知所措，数据挖掘工具可以通过可视化技术，并且根据 用户的需要来表示数据，为数据分析人员提供很好的帮助。拓宽了传统的图表 功能，使用户对数据剖析更清楚。 1 2 3 数据挖掘的过程 数据挖掘是一个多步骤的处理过程，这个过程是交互和迭代的，其中许多 过程需要用户参与。图1 1 描述了数据挖掘的基本过程和主要步骤。 ( 1 ) 确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。挖 掘的最后结构是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而 数据挖掘则带有盲目性，是不会成功的。 ( 2 ) 数据准备( d a mp r e p a r a l i o n ) 这个阶段又可以细分为三个步骤：数据选取( d a t as e l e c t i o n ) 、数据预处 理( d a mp r e p r o c c s s i n g ) 和数据变换( d a t at r a n s f o r m a t i o n ) 。 数据选取：是根据用户的挖掘目的，搜索所有与业务对象有关的内部和 外部数据信息，从数据源中提取与挖掘相关的数据。 数据预处理：是对选取出的数据进行加工，主要包括检查数据的完整性 及数据的一致性，对其中噪音数据进行处理，推导计算出丢失的数据，消除重 复的记录，完成数据类型的转换等。如果数据挖掘的对象是数据仓库，则数据 预处理在形成数据仓库时已经完成。 数据变换：将数据转换成个分析模型。这个分析模型是针对挖掘算法 建立的。建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。可以 通过投影或数据库的其它操作来降低数据的维数，从而减少数据挖掘时数据的 数量，提高挖掘算法的效率。 ( 3 ) 数据挖掘 对所得到的经过转换的数据进行挖掘。除了完善选择合适的挖掘算法外， 其余一切工作都能自动地完成。整个挖掘过程应该是交互的、迭代的，即用户 可以控制某些挖掘参数，如支持度、置信度、挖掘的粒度等。数据挖掘算法是 整个数据挖掘系统的核心部分。 ( 4 ) 挖掘结果的表述和评价 这个阶段分为两个步骤：结果表述( p r e s e n t a t i o n ) 和结果评价( a s s e s s ) 。 结果表述：数据挖掘所获得的模式是用户可以理解的，可以利用可视化 工具帮助用户理解挖掘的结果。 结果评价：数据挖掘所获得的模式经过用户和机器的评价，删除冗余或 无关的模式。如果用户对挖掘出的模式不满意，可以重新选择数据、挖掘算法 递归地执行整个挖掘过程，直到用户满意为止。 ( 5 ) 知识的同化 将分析所得到的知识集成到业务信息系统的组织结构中去。 图1 - 1 数据挖掘的基本过程 1 2 4 数据挖掘的研究焦点 当前，数据挖掘研究方兴未艾，其研究与开发的总体水平相当于数据库技 术在7 0 年代所处的地位，迫切需要类似于关系模式、d b m s 系统和s q l 查询 语言等理论和方法的指导，才能使d m k d 的应用得以普遍推广。预计在不久 的将来，d m k d 的研究还会形成更大的高潮，研究焦点可能会集中到以下几 个方面【3 3 l ： ( 1 ) 处理不同类型数据； ( 2 ) 发现语言的形式化描述，即研究专门用于知识发现的数据挖掘语言， 也许会像s q l 语言一样走向形式化和标准化； ( 3 ) 寻求数据挖掘过程中的可视化方法，使知识发现的过程能够被用户 理解，也便于在知识发现的过程中进行人机交互。数据挖掘的结果应准确地描 述数据挖掘的要求，并易于表达。从不同的角度考察发现的知识，并以不同形 式表示，用高层次语言和图形界面表示数据挖掘要求和结果。目前许多知识发 现系统和工具缺乏与用户的交互，难以有效利用领域知识； ( 4 ) 研究在网络环境下的数据挖掘技术( w 曲m i n i n g ) ； 6 ( 5 ) 加强对各种非结构化数据的开采( d a m m i n i n g f o r a u d i o v i d e o ) ， 如对文本数据、图形数据、视频图像数据、声音数据乃至综合多媒体数据的开 采； ( 6 ) 交互式发现； ( 7 ) 知识的维护更新。 就目前来看，将柬的几个热点包括w e b 数据挖掘、生物信息或基因的数 据挖掘、文本的数据挖掘、多媒体数据挖掘、元数据的数据挖掘以及数据挖掘 的安全和隐私等等。 1 3w e b 数据挖掘 i n t e r a c t 已经发展成为一个巨大、分布广泛、全球性的信息服务中心，它 涉及教育、政府、电子商务、新闻、广告、消费信息、金融管理和许多其它信 息服务，i n t e r n e t 的普及和发展为人们带来了巨大的社会效益，也为信息科学 的研究带来了巨大的机遇和挑战。然而，虽然网络可以迅速便捷地为人们带来 大量信息，但在实际应用中，当需要从网络上获取信息时，有用信息往往会被 大量的无用信息所淹没，使用户处于无所适从的境地。与此同时，还有许多其 它问题伴随而来：诸如信息真假难以辨识；信息安全难以保证；信息形式不一 致，难以统一处理等等。因此，如何快速准确的获取所需信息、如何获得信息 之间潜在的知识以及如何提供个性化的服务，己经成为急需解决的问题。但是， w e b 所具有的海量数据、复杂性、极强的动态性、用户的多样性和小相关性 或有用性等特点给w e b 资源发掘造成了相当的难度。 w e b 上的搜索引擎部分地解决了资源发现问题，但由于精确度不高等原 因，其效果远不能使人满意。此外，搜索引擎的目的在于发现w e b 上的资源， 就w e b 上的知识发现而言，即使检索的速度再高，搜索引擎也不能胜任。为 此，我们需要开发一种比信息检索层次更高的新技术。但是，数据挖掘的绝大 部分工作所涉及的是结构化的数据库，很少有处理w e b 上的异质的、非结构 化的信息的工作。w e b 挖掘作为数据挖掘的一个新主题，引起了人们的极大 兴趣，并在各个领域显示出了诱人的应用前景。 1 3 1w e b 数据挖掘概念 w e b 挖掘是从w e b 资源上抽取信息或知识的过程，它是将传统的数据挖 掘的思想和方法应用于w e b ，从w 曲文档和w e b 活动中抽取感兴趣的、潜在 的、有用的模式和隐藏信息口9 1 1 3 ”。 w e b 是个巨大的、广泛分布、高度异构、半结构化、超文本超媒体、 相互联系并且不断进化的信息仓库；也是一个巨大的文档累积的集合，包括超 链接信息、访问及使用信息。传统的数据挖掘大多是针对关系数据库或数据仓 库的，处理的数据具有完整的结构，但是w e b 包含各种类型的数据，现有的 7 数据库管理系统无法操纵和管理大量的非结构化数据，其用户群体也表现出多 样性的特点。w e b 数据挖掘起源于数据挖掘，目的在于可以处理非结构化的 数据，w e b 数据的非结构化这一显著特征使w e b 数据挖掘更加复杂。 w e b 挖掘可在多方面发挥作用，如搜索引擎结构的挖掘，搜索引擎的开 发，改进和提高搜索引擎的质量和效率，确定权威页面，w e b 文档分类，w e b l o g 挖掘、智能查询，建立m e t a - w e b 数据仓库等。w e b 挖掘研究覆盖了多个 研究领域，包括数据库技术、信息获取技术、统计学、人工智能中的机器学习 和神经网络等。特别是电子商务领域，通过w e b 挖掘，不仅可以从大量多种 多样信息的w e b 页面中提取出我们需要的有用的知识，还可以得到关于群体 用户访问行为和方式的普遍知识，用以改进w e b 服务设计。更重要的是，通 过对用户特征的理解和分析，如对用户访问行为、频度、内容等的分析，提取 出用户的特征，从而为用户定制个性化的界面，有助于开展有针对性的电子商 务活动口o l 。 1 3 2w e b 挖掘流程 w e b 数据挖掘就是利用数据挖掘技术从网络文档和服务中发现和提取信 息i i ，与传统数据和数据仓库相比，w e b 上的信息是非结构化或半结构化的、 动态的、并且是容易造成混淆的，所以很难直接以w e b 网页上的数据进行数 据挖掘，而必须经过必要的数据处理。典型w e b 挖掘的处理流程如图1 2 1 ”j ： ( 1 ) 资源发现：任务是从目标w e b 文档中得到数据，值得注意的是有时 信息资源不仅限于在线w 曲文档，还包括电子邮件、电子文档、新闻组，或 者网站的日志数据甚至是通过w e b 形成的交易数据库中的数据。 ( 2 ) 信息选择和预处理：任务是从取得的w e b 资源中剔除无用信息和将 信息进行必要的整理。例如从w e b 文档中自动去除广告连接、去除多余格式 标记、自动识别段落或者字段并将数据组织成规整的逻辑形式甚至是关系表。 ( 3 ) 模式识别阶段：这个阶段主要运用数据挖掘技术和统计方法，从 w e b 使用记录中挖掘知识。实现算法可以是统计分析、路径分析、关联规则、 序列模式以及分类聚类等。 ( 4 ) 模式分析阶段：这个阶段的任务是采用合适的成熟的技术和工具， 进行模式的分析，从而辅助分析人员的理解，使采用各种工具挖掘出的模式得 到很好的利用。目前常用的方法有：采用类似s q l 的形式化查询进行分析； 先将数据导入多维数据立方体中，再利用o l a p 工具进行分析并提供可视化 的结果输出。可视化技术被经常应用到模式分析的结果显示。 8 图1 - 2w e b 数据挖掘的工作流程 需要注意的是：w e b 挖掘作为一个完整的技术体系，在进行挖掘之前的 信息获得i r ( i n f o r m a t i o nr e t r i e v a l ) 和信息抽取i e ( i n f o r m a t i o ne x t r a c t i o n ) 相当重要。信息获得( r ) 的目的在于找到相关w e b 文档，它只是把文档中的 数据看成未经排序的词组的集合，而信息抽取( i e ) 的目的在于从文档中找到 需要的数据项目，它对文档的结构合表达的含义感兴趣，它得一个重要任务就 是对数据进行组织整理并适当建立索引。信息获得( 取) 和信息抽取( i e ) 技 术的研究已近有很长时间，随着w e b 技术的发展，基于w e b 技术的i r 、i e 得到了更多的重视。由于w e b 数据量非常大，而且可能动态变化，用原来手 工方式进行信息收集早已经力不从心，目前的研究方向是用自动化、半自动化 的方法在w e b 上进行i r 和i e 。在w e b 环境下既要处理非结构化文档，又要 处理半结构化的数据，最近几年在这两方面都有相应的研究成果和具体应用， 特别是在大型搜索引擎中得到了很好的应用1 2 j 。 1 3 3w e b 数据挖掘的数据 在w e b 上可以用来作为数据挖掘分析的数据量比较大，而且类型众多，总 结起来有以下几种类型的数据可用于w e b 数据挖掘技术产生各种知识模式： ( 1 ) 服务器数据 客户访问站点时会在w e b 服务器上留下相应的目志数据，这些同志数据通 常以文本文件的形式存储在服务器上。一般包括s e v e = t l o g s 、e i t o 1 0 9 s 、c o o k i e l o g s 等。 ( 2 ) 查询数据 它是电子商务站点在服务器上产生的种典型数据。例如，对于在线客户 也许会搜索一些产品或某些广告信息，这些查询信息就通过c o o k i e 或是登记 信息连接到服务器的访问日志上。目前还没有一个标准的查询数据格式。 ( 3 ) 代理服务器端数据 网站服务器同志只记录用户对某个网站的访问，代理服务器日志记录用户 对所有网站的访问。代理服务器相当于在客户浏览器和w e b 服务器之间提供 了缓存功能的中介服务器，它的缓存功能减少了w e b 服务器的网络流量，加 9 快了网页的运行速度，同时将大量的用户访问信息通过代理日志的形式保存起 来。 ( 4 ) 在线市场数据 这类数据主要是传统关系数据库里存储的有关电子商务站点信息、用户购 买信息、商品信息等数据。 ( 5 ) w e b 页面 主要是指h t l m 和x m l 页面的内容，包括本文、图片、语音、图像等。 ( 6 ) w e b 页面超级链接关系 主要是指页面之间存在的超级链接关系，这也是一种重要的资源。 ( 7 ) 客户登记信息 客户登记信息是指客户通过w e b 网页在屏幕上输入并提交给服务器的相 关信息，这些信息通常是关于用户的人口特征。在w 曲的数据挖掘中，客户 登记信息需要和访问日志集成，以提高数据挖掘的准确度，使之能更进一步的 了解客户。 我们可以按照通行的做法将其归为三类：内容数据，即w e b 页面，如h t m l 文档、动画、图片等；用户访问数据，即描述用户使用网络资源的数据，通常 以日志文件的形式存在，如s e r v e rl o g s ，e r r o rl o g s 和c o o k i el o g s ：结构数据， 如网页的内部链接和网页间的超链接等。 相应地，根据挖掘对象不同w e b 挖掘可以分为三类：w e b 内容挖掘( w e b c o n t e n tm i n i n g ) 、w 曲结构挖掘( 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 em i n i n g ) 【l 】【”。图1 3 给出了w e b 挖掘的分类图。 图1 - 3w e b 挖掘分类 1 0 1 3 4w e b 数据挖掘的分类 ( 1 ) w e b 内容挖掘 w c b 内容挖掘是一种基于网页内容的挖掘，是从大量的网络的内容、数 据、文档中发现信息、抽取知识或模式的过程。 w e b 内容挖掘的对象包括文本、图象、音频、视频、多媒体和其他各种 类型的数据。其中针对无结构化文本进行的w e b 挖掘被归类到基于文本的知 识发现( k d t ) 领域，也称文本数据挖掘或文本挖掘，是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 结构挖掘和内容挖掘有着紧密的联系。二者都是对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 方法 8 1 等。 p a g e - r a n k 的基本思想是：如果一个页面被多次引用，则该页面很可能是 重要的；一个页面未被多次引用但被一个重要页面所引用，该页面也很可能是 重要的。一个页面中指向其它页面的超链接越多，在一定程度上说明该网页中 的信息内容越有说服力，指向该页面的超链接越多( 即被多次引用) ，则说明 该页面中的信息内容有一定的权威性。因此，网页之间的超链接( 引用) 在一 定程度上能表明w e b 文档的重要性。网页的被点击率也是与超链接有关的一 项重要评价指标。但具有一定欺骗性，因为一个网页虽然被点击，可能只是通 往目标网页的超链路径上的一环，用户并非真正想浏览它。 但是由于w e b 链接结构具有一定局限性。如：不是每个超链接都代表寻 找的认可，有些是为了其他目的而创建的( 如为了导航或付费广告等) ；出于 商业或竞争的考虑，很少有w e b 页面指向其竞争领域的权威页面( 如可口可 乐就不会链接到其竞争对手百事可乐的w e b 页面上) ：权威页面很少具有特别 的描述( 如y a h o o ! 主页就不会明确给出“w e b 搜索引擎”之类的自描述信息) 。 为了克服w e b 链接结构存在的局限性，人们提出了另一种重要的w e b 页面 一h u b 页面。它提供了指向权威页面的链接集合。h u b 页面本身可能并不突出， 或者可能没有几个链接指向它们，但是，h u b 页面提供了最为突出( 或重要) 的站点链接，它起到了隐含说明某权威页面的作用。通常，好的h u b 页面指 向许多好的权威页面；好的权威页面则有好的h u b 页面指向它。这样，可以用 h u b 页面和权威页面之间的这种相互作用，来挖掘权威页面和自动发现高质量 的w e b 结构和资源。有关利用h u b 页面来寻找权威页面的h i t s 算法的介绍 见参考文献【4 2 。 ( 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 使用挖掘可以了解用户的网络行为数据所具有的意义，对用户访问 w e b 时在服务器方留下的访问记录进行挖掘。它通过挖掘w e b 日志文件及其 相关数据来发现用户访问w e b 页面的模式，可以识别用户的忠实度、喜好、 满意度，可以发现潜在用户或为用户提供个性化服务，改进站点的结构从而增 强站点的服务竞争力。 w e b 使用记录数据除了服务器的日志记录外还包括代理服务器日志、浏 览器端日志、注册信息、用户会话信息、交易信息、c o o k i e 中的信息、用户 查询、鼠标点击流等一切用户与站点之间可能的交互记录。可见w e b 使用记 录的数掘量是非常巨大的，而且数据类型也相当丰富。根据对数据源的不同处 理方法，w e b 用法挖掘可以分为两类，一类是将w e b 使用记录的数据转换并 传递进传统的关系表里，再使用数据挖掘算法对关系表中的数据进行常规挖 掘；另一类是将w e b 使用记录的数据直接预处理再进行挖掘。w e b 用法挖掘 中的一个有趣的问题是在多个用户使用同一个代理服务器的环境下如何标识 某个