（计算机软件与理论专业论文）基于web的数据挖掘技术——web内容挖掘的设计与实现.pdf

摘要 w w w 是个丌放的全球性资源，它是世界上最丰富和最密集的信息来源。随 着w w w 上信息的爆炸性增长，在如此海量的数据中发现有用的信息变得越来越困 难。数据挖掘就是从大量的数据中发现隐含的规律性的内容，解决数据的应用质 量问题。充分利用有用的数据，废弃虚伪无用的数据，是数据挖掘技术撮重要的 应用。因此，采用数据挖掘技术从w w w 上提取隐含的、未知的、非平凡的及有潜 存心用价值的信启、，具有十分重要的现实意义和广泛的应用前景。 本文首先简要论述了w w w 发展的基本现状以及当前存在的一些问题。随后， 简要介绍了数据挖掘技术的基本概念、原理，接着，概要的介绍了本文对于w e b 数据挖掘所用到的技术一j a v a 和x m l 技术，在此基础上研究了数据挖掘技术在 w w wl 的应用，针对w e b 数据内容挖掘进行了详细地论述。文中通过一个具体的 案例详细论述了实现w e b 数据内容挖掘的一种方法以及对该方法的分析。最后， 对全文进行了总结。 关键词：w w w ，w e b 数据挖掘，x m l 第f i 页 a b s tr a c t t h ew o r l dw i d ew e bi sad i s t r i b u t e dg l o b a li n f o r m a t i o nr e s o u r c ec o n t a i n i n ga l a r g ea m o u n to fd a t ar e l e v a n tt oe s s e n t i a l l ya l ld o m a i n so fh u m a na c t i v i t y g i v e nt h e h j g hr a t eo f t h ev o l u m eo fd a t aa v a i l a b l eo nt h ew w i f i n d i n gu s e f u li n f o r m a t i o ni n s u c hal a r g ea m o u n to fd a t ab e c o m e sam o r ed i f f i c u l tp r o c e s se v e r yd a y d a t a m i n i n g i st h et e r mg i v e nt ot h ea u t o m a t e dd i s c o v e r yo fn o n o b v i o u s ，p o t e n t i a l l yu s e f u la n d p r e v i o u s l y u n k n o w ni n f o r m a t i o nf r o m l a r g e d a t as o u r c e s s o o b t a i n i n gv a l u a b l e i n f o r m a t i o nb yd a t am i n i n gt e c h n i q u e si n t e l l i g e n t l ya n da u t o m a t i c a l l y , i m p r o v i n g e f f i c i e n c yo f t h ew w w h a st r e m e n d o u sa p p l i c a t i o nv a l u e s i nt h i sp a p e r , w ef i r s tg e n e r a l l yi n t r o d u c et h ei m p r o v e m e n to fw w wa n ds o m e p r o b l e m su n s o l v e d a n dt h e nw ed e s c r i b et h eb a s i cc o n c e p t sa n dt h e o r i e s o fd a t a m i n i n g t h ef o l l o w i n gi sd i s s e r t a t e dt h ea p p l i c a t i o no f d a t am i n i n gt e c h n i q u e st ot h e w o i l dw i d ew e b ，a n dd i s c u s si nd e t a i lt h ec o n t e n t 、c h a r a c t e r i s t i c 、p r o b l e m su n s o l v e d o t lw e bc o n t e nm i n i n ga n dw e b u s a g em i n i n g a n dt h e n ，w eg e n e r a l l yi n t r o d u c et h e t e c h n i q u e so fu s ef o rd a t am i n i n gi nt h ep a p e r 勺a v aa n dx m l t h r o u g ha c o n c r e t e s a m p l e ，w ed e s c r i b ei nd e t a i lo n e o ft h em e t h o dt h a tr e a l i z ew e bd a t am i n i n g f i n a l l y w em a k eac o n c l u s i o no f t h ep a p e r k e y w o r d s ：烀? 彤w e bd a t am i n i n g ，x m l 第i v 页 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 签名：迸! 旦查日期：z 0 0 1 - 年乙月相 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后 签名：簦噬 第1 1 页 ，鞲 此 签 ： 守 师 期 断 挪 醐 基于w e b 的数据挖掘技术 第一章引言 1 1 ln t e r n e t 的由来与发展 i n z e r n e t 即通常所说的因特网或国际互联网，它是一个全球性的巨大的计 算机网络体系，它把全球数万个计算机网络，数亿台主机连接起来，包含了难 以计数的信息资源，向全世界提供信息服务。它的出现，是世界由工业化走向 信息化的必然和象征。i n t e r n e t 构成了当今信息社会的基础结构。 i n t e r n e t 起源于美国国防部d o d 高级研究计划署a r p a 建立的实验性网络 a r p a n e t ，这是一个比较完善的分布式跨国计算机网络。 a r p a n e t 最早采用了分组交换技术，这种通信技术是把数据分割成一定长度 的信息包来传送，这些信息包可能走不同的通信线路，这样即使是某些线路遭到 破坏，只要还有迂回线路可供使用，便仍可正常进行通信。此外，全网没有统一 的控制中心，网卜各台计算机都遵循着统一的协议自主地工作。 a r p a 于1 9 6 9 年1 月开始研制a r p a n e l ，最初由4 个网络节点爨分布在美国 4 个地区寨地区互联实验，到1 9 7 7 年发展到5 7 个，连接了各类计算机1 0 0 多台。 其问，a r p a 开发了针对于a r p a n e l 的网络协议集，其中最主要的两个协议为t c p 和i p ，它使得各种类型的计算机网络之间能够彼此通信，因此，加入到a r p a n o t 中的计算机网络也越来越多，a r p a n e t 的队伍日益壮大。 1 9 8 0 年a r p a 把t c p i p 加入到u n i x 内核中，因此以后t c p i p 即成为u n i x 系统的标准通信模块，目前i n t e r n e t 网上大部分主机运行的都是u n i x 系统。到 t1 9 8 3 年，a r p a 把t c p i p 正式作为a r p a n e t 的标准协议。 在a r p a n e t 发展过程中，美国其它一些机构开始建立自己的面向全国的计算 机广域网，这些网络大多数采用与a r p a n e t 相同的通信协议。其中美国国家科学 基金会n , e f 的n s f n e t 有着很大影响，它为i n t e r n e t 的产生起了积极的促进作用。 最初n s f n e l 以5 6 k b p s 的速率，连接包括所有大学及国家经费资助的研究机构。 构网方式以校园网为基础形成多个区域性网络，并在此基础上互联形成全国性的 广域嘲。到了1 9 8 8 年，n s f n e t 的主干网升级到1 5 m b p s 线路。 此外，美国宇航局n s s a 与能源部的n s i n e t 、e s n e t 网相继建成。欧洲、f l 本等也积极发展本地网络。于是在此基础上互联形成了i n t e r n e t ，而a r p a n e t 作 为一个军事项目，至1 9 8 9 年即不复存在。如今，n s f n e t 已成为i n t e r n e t 远程 通信设施的主要提供者。 第一1 页 基于w e b 的数据挖掘技术 综上所述，i n t e r n e t 是世界上许多不同网络通过互联而形成的个全球性广 域网络，其中一些网络包括b i t n e t 、u s e n e 、m i i n e t 、e s n e t 、c o m p u s e r v e 、m a i l 等。i n t e r n e t 就是由一个科研网逐步地发展到现在成为面向全球的商业网。 人们通过w w w 来访问i n t e r n e t 。w l v l v 也叫万维网，是一个基于超级文本方 式的信息系统。它是由欧洲核子物理研究所中心研制的。通过它，将位于全世 界i n t e r n e t 上不同地点的相关数据信息有机地编织在一起。w w w 提供这样一种 友好的信息查询接口：用户仅需提出查询要求，而到什么地方查询及如何查询 则由w w w 自动完成。因此，聊w 为你带来的是世界范围的超级文本服务。只要 操纵计算机的鼠标器，就可以通过i n t e r n e t 从全世界任何地方调来你所希望得 到的文本、图像和声音等信息。 w w w 由遍布在 n t e r n e t 网中的被称为w w w 服务器的计算机组成。个服务 器除了提供它自身的独特信息服务外，还“指引”存放在其他服务器上的信息。 那些服务器又指引着更多的服务器，也可能指回原来的服务器。这样，在环球 范围的信息服务器互相指引而形成的信息网便出现了。 w w w 以客户机服务器的模式进行工作。在i n t e r n e t 上的一些计算机上运 行w w w 服务器程序，它们是信息的提供者。在用户的一端运行着w w w 客户机程 序，用来帮助用户完成信息查询。当然，在同一台计算机也允许二者同时运行。 客户机程序主要有两种功能：向用户提供友好的使用界面和将用户的信息查询 请求转换成查询命令传送给网络上相应的w w w 服务器进行处理。当w w w 服务器 接到来自某一客户机的请求后，就进行查询并将得到的数据送回该客户机，而 w w w 客户机程序将这些数据转换成相应的形式显示给用户。 w w w 采用统一资源定位符标识分布在整个i n t e r n e t 上的文档，并使每一个 文档在整个i n t e r n e t 的范围内具有唯的标识符。 w w w 采用超文本传输协议h t t p 实现各种超链接的链接。w w w 客户程序与w w w 服务器程序之间的交互严格遵守这种协议。h t t p 是一个应用层的协议，它使用 t c p 连接进行可靠的传送。 1 2 嗍局限性 w w w 上的信息量每天以几何级数增长，目前信息资源已经成为一个天文数 字。如何利用这些大量的数据对我们提出了挑战，也就是说，怎样把w e b 转换 并且组织，使其成为一个更加有用的信息服务体系。 现在，像g o o g e 这样的搜索引擎利用全文检索的形式构建了这样的经过组 第2 页 基于w e b 的数据挖掘技术 织的信息利用工具。一个用户的查询就是一个关键词或者用关键词和操作符组 合成的字符串，检索的结果就是在查询关键词基础上，和关键词相关的网页的 个列表。这种工具为用户使用w w w 带来了很大的方便。但是今天的搜索引擎 面临着许多困扰，概括的说主要有以下四个方面： f1 ) 火量的不相关的文档被作为查询结果反馈给查询用户； ( 2 ) 每个搜索覆盖到的网页都非常有限； ( 3 ) 提供给用，j 的交互搜索方式非常有限： ( 4 ) 给每一个用户提供单独定制信息的手段非常有限。 这些问题，归根到底是和w w w 的特性有关。同时，人们普遍相信这样一个 事实，9 9 的访问者剥于w e b 页上9 9 的信息都不感兴趣。另外，w e b 的构建是 未经过组织的，以h t m l 形式存在，而这种形式对于分析、提炼其中的内容是非 常困难的。 面对这样的问题，如何更好的组织和利用网络资源使w w w 更好的为人们服 务成为当前的一个重要课题。研究者在这个问题上进行了很多的尝试，在这其 中，新的、不断发展的数据挖掘技术作为一个有力的工具能够实现从w e b 中提 取到更有用的信息。数据挖掘已经作为一项成功的技术被应用到大型数据库的 管理中。在很多领域，例如天气预报、医疗诊断、信用评估、消费分析、市场 欺诈检测等都得到了良好的应用。数据挖掘技术应用在w w w 上有着广阔的前景。 1 3 本文的工作 对于当前在w w w 上查询信息存在的诸多问题，本文提出了在w e b 上结合 j a v a 和xm 1 j 技术，利用数据挖掘技术实现信息有效查询的一种方案。文中详细 论述了该方案的实现过程，并用一个具体的例子来阐述该方案。 本文的结构主要分为以下几个内容： ) r 数捌挖掘技术 l a v a 利x 技术 基于w e b 的数据挖掘 本文提出的解决方案 该方案的实现 第3 页 基于w e b 的数据挖掘技术 2 1 数据挖掘概述 第二章数据挖掘技术 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，千千 力万个数据库被用于商业管理、政府办公、科学研究和工程开发等等，并且这 一趋势仍将持续发展下去。于是，一个新的挑战被提了出来：在这被称之为信 息爆炸的时代，信息过量几乎成为人人需要面对的问题。怎样才能不被信息的 汪洋人海所淹没，从中及时发现有用的知识，变得越发的重要。要想使数据真 f 成为一个公司的资源，只有充分利用它为公司自身的业务决策和战略发展服 务爿行，否则大量的数据可能成为包袱，甚至成为垃圾。因此，数据挖掘和知 识发现d m k d 技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。 2 1 1 数据挖掘的历史背景 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。起初各种 商业数据是存储在计算机的数据库中的，然后发展到可对数据库进行查询和访 问，进而发展到对数据库的即时遍历，数据挖掘使数据库技术进入了一个更高级 的阶段，它不仅能对过去的数据进行查询和遍历，并且能够找出过去数据之间 的潜在联系，从而促进信息的传递。 数据挖捌是一个逐渐演变的过程。电子数据处理的初期，人们就试图通过 某些方法来实现自动决策支持，当时机器学习成为人们关心的焦点。机器学习 的过程就是将一些已知的并己被成功解决的问题作为范例输入计算机，机器通 过学习这些范例总结并生成相应的规则，这些规则具有通用性，使用它们可以解 决某一类的问题。随后，随着神经网络技术的形成和发展，人们的注意力转向 知识工程，知识工程不同于机器学习那样给计算机输入范例，让它生成出规则， 而是甫接给计算机输入已被代码化的规则，而计算机是通过使用这些规则来解 决某些问题。专家系统就是这种方法所得到的成果，但它有投资大、效果不甚 理想等不足。8 0 年代人们又在新的神经网络理论的指导下，重新回到机器学刊 的方法上，并将其成果应用于处理大型商业数据库。随着在8 0 年代末一个新的 术语，它就是数据库中的知识发现，简称k d d ( k n o w l e d g ed i s c o v e r y i n d a t a b a s e ) 它泛指所有从源数据中发掘模式或联系的方法，人们接受了这个术 语，并用k d d 来描述整个数据发掘的过程，包括最开始的制定业务目标到最终 的结果分析，而用数据挖掘( d a t a m i n i n g ) 来描述使用挖掘算法进行数据挖掘 第4 页 基于w e b 的数据挖掘技术 的子过程。但最近人们却逐渐开始使用数据挖掘中有许多工作可以由统计方法 来完成，并认为最好的策略是将统计方法与数据挖掘有机的结合起来。 研究数据挖掘的历史，可以发现数据挖掘的快速增长是和商业数据库的空 前速度增长分不丌的，并且九十年代较为成熟的数据仓库正同样广泛地应用于 各种商业领域。从商业数据到商业信息的进化过程中，每一步前进都足建立在 l 一步的基础上的。下表给出了数据进化的四个阶段，从中可以看到，第四步 进化是革命性的，因为从用户的角度来看，这一阶段的数据库技术已经可以快 速地回答商业上的很多问题了。 进化阶段时间段生产厂家技术支持产品特点 数据收集6 0 年代i b m 、c d c 等磁带提供静态历史 数据 数据访问8 ( ) 年代o r a c l e 、s y b a s e 、关系数据库、在纪录中动态 i b m 、i n f ( ) r m i x 等s q l历史数据信息 数据仓库9 0 年代 p i l o t 、c o m s h a r e 、 联机分析处理提供回溯的动 a r b o r 、c o g n o s 等态的历史数据 数据挖掘2 l 世纪 p il o t 、l o c k h e e d 、 多处理系统、可提供预测性 i b m 、s g i 等海量系统信息 表卜1 特别要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向 特定数据库的简中检索查询调用，而且要对这些数据进行微观、中观乃至宏观 的统计、分析、综合和推理，以指导实际问题的求解，企图发现事件间的相互 关联，甚至利用已有的数据对未来的活动进行预测。例如加拿大b c 省电话公司 要求加拿大s i m o n f r a s e r 大学k d d 研究组，根据其拥有十多年的客户数据，总 结、分析并提出新的电话收费和管理办法，制定既有利于公司又有利于客户的 优惠政策。这样来，就把人们对数据的应用，从低层次的末端查询操作，提 高到为各级经营决策者提供决策支持。这种需求驱动力，比数据库查询更为强 大。同时需要指出的是，这里所说的知识发现，不是要求发现放之四海而皆准 第5 页 基于w e b 的数据挖掘技术 的真理，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器 定理证明。所有发现的知识都是相对的，是有特定前提和约束条件、面向特定 领域的，同时还要能够易于被用户理解，最好能用自然语言表达发现结果。因 此，i ) i a k d 的研究成果是很有实际应用价值的。 2 1 2 数据挖掘的研究现状 k d d 词首次出现在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会 议上。迄今为止，由美国人工智能协会主办的k d d 国际研讨会已经召开了7 次， 规模由原来的专题讨论会发展到国际学术大会，人数由二三十人到七八百人， 论文收录比例从2 x l 到6 x l ，研究重点也逐渐从发现方法转向系统应用，并且 注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。其他内容的 专题会议也把数据挖掘和知识发现列为议题之一，成为当前计算机科学界的一 火热点。 此外，数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也 纷纷开辟了k d d 专题或专刊。i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊 领先在1 9 9 3 年出版了k d d 技术专刊，所发表的5 篇论文代表了当时k d d 研究的 最新成果和动态，较全面地论述了k d d 系统方法论、发现结果的评价、k d d 系 统设计的逻辑方法，集中讨论了鉴于数据库的动态性冗余、高噪声和不确定性、 窄值等问题，k d d 系统与其它传统的机器学习、专家系统、人工神经网络、数 理统计分析系统的联系和区别，以及相应的基本对策。随着d m k d 研究逐步走向 深入，人们越来越清楚地认识到，d m k d 的研究主要有3 个技术支柱，即数据库、 人工智能和数理统计。 目前，i 四# i - 数据挖掘的发展趋势及其研究方面主要有：对知识发现方法的 研究进一步发展，如近年来注重对b a y e s 方法以及b o o s t i n g 方法的研究和提高； 传统的统计回归法在k d d 中的应用；k d d 与数据库的紧密结合。在应用方面包 括：k d d 商业软件：r = 具不断产生和完善，注重建立解决问题的整体系统，而不 是孤立的过程。用户主要集中在大型银行、保险公司、电信公司和销售业。 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所和公司。所涉 及的研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有 关数据挖掘理论方面的研究。 一份最近的g a r t n e r 报告中列举了在今后3 年一5 年内对工业将产生重要影 响的5 项关键技术，其中k d d 和人工智能排名第一。同时，这份报告将并行计 算机体系结构研究和k d d 列入今后5 年内公司应该投资的1 0 个新技术领域。从 第6 负 基于w e b 的数据挖掘技术 这我们不难看出，数据挖掘的研究和应用受到了学术界和实业界越来越多的重 视。相信在不久的将来，数据挖掘技术必将给我们的生活带来巨大的变化。 2 1 3 数据挖掘的概念 从技术上来说，数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声 的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是 潜在有用的信息和知识的过程。还有很多和这一术语相近似的术语，如从数据 库中发现知识、数据分析、数据融合( d a t af u s i o n ) 以及决策支持等。人们把原 始数据看作是形成知识的源泉，就像从矿石中采矿一样。原始数据可以是结构 化的，划关系数据库中的数据，也可以是半结构化的，如文本、图形、图像数 据，甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可 以是非数学的：可以是演绎的，也可以足归纳的。发现了的知识可以被用于信息 管理、查询优化、决策支持、过程控制等，还可以用于数据自身的维护。因此， 数据挖掘是一门很，1 义的交叉学科，它汇聚了不同领域的研究者，尤其是数据 库、人工智能、数理统计、可视化、并行计算等方面的学者和工程技术人员。 从商业角度来说，数据挖掘也是一种新的商业信息处理技术，其主要特点 是对商、世数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理， 从中提取辅助商业决策的关键性数据。 简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身已 经有很多年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另 外，由于当时计算能力的限制，对大数据量进行分析的复杂数据分析方法受到 很大限制。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务 数据，这些数据不再是为了分析的目的而收集的，而是由于纯机会的商业运作 而产生。分析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提 供真正有价值的信息，进而获得利润。但所有企业面临的一个共同问题是：企 业数据量非常大，而其中真正有价值的信息却很少，因此从大量的数据中经过 深层分析，获得有利于商业运作、提高竞争力的信息，就像从矿石中淘金一样， 数据挖掘也因此而得名。 因此，数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进 行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型 化的先进有效的方法。 2 14 数据挖掘的范围 追根溯源，”数据挖掘”这个名字来源于它有点类似于在山脉中挖捌有价值 第7 页 一 茎王! 塑盟塑塑堡塑垫查 的矿减。在商业应用里，它就表现为在大型数据库里面搜索有价值的商业信息。 这需要对巨量的材料进行详细地过滤，并且需要智能且精确地定位潜在价值的 所在。对于给定了大小的数据库，数据挖掘技术可以用它如下的超能力产生巨 大的商业机会： 自动趋势预测 数据挖掘能自动在大型数据库里面找寻潜在的预测信息。传统上需要很多 专家来进行分析的问题，现在可以快速而直接地从数据中间找到答案。一个典 型的利用数据挖掘进行预测的例子就是目标营销。数据挖掘工具可以根据过去 邮件推销中的大量数据找出其中最有可能对将来的邮件推销作出反应的客户。 自动探测以前束发现的模式 数据挖掘工具扫描整个数据库并辨认出那些隐藏着的模式，比如通过分析 零售数据来辨别出表面上看起来没联系的产品，实际上有很多情况下是一起被 售m 的情况。 数据挖掘技术可以让现有的软件和硬件更加自动化，并且可以在升级的或 者新丌发的平台上执行 当数掘挖掘工具运行于高性能的并行处理系统上的时候，它能在数分钟内 分析一个超大型的数据库。这种更快的处理速度意味着用户有更多的机会来分 析数据，让分析的结果更加准确可靠，并且易于理解。此外，数据库可以由此 拓展深度和广度。深度上，允许有更多的列存在。以往，在进行较复杂的数据 分析时，专家们限于时间因素，不得不对参加运算的变量数量加以限制，但是 那些被丢弃而没有参加运算的变量有可能包含着另一些不为人知的有用信息。 现在，高性能的数据挖掘工具让用户对数据库能进行通盘的深度编历，并且任 何可能参选的变量都被考虑进去，再不需要选择变量的子集来进行运算了。广 度上，允许有更多的行存在。更大的样本让产生错误和变化的概率降低，这样 用户就能更加精确地推导出一些虽小但颇为重要的结论。 21 5 数据挖掘与传统分析方法的区别 数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质区别是 数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到 的信息应具有先未知，有效性和实用性三个特征。 先前未知的信息是指该信息是预先未曾预料到的，既数据挖掘是要发现那 些不能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信息 第8 页 基于w e b 的数据挖掘技术 越是出乎意料，就可能越有价值在商业应用中最典型的例子就是一家连锁店通 过数据挖掘发现了小孩尿布和啤酒之间有着惊人的联系。 2 2 数据挖掘的任务、方法、及技术 2 2 1 数据挖掘的挖掘任务 数据挖掘所能发现的知识有如下几种： 广义型知识，反映同类事物共同性质的知识； 特征型知识，反映事物各方面的特征知识； 差异型知识，反映不同事物之间属性差别的知识； 关联型知识，反映事物之间依赖或关联的知识； 预测型知识，根据历史的和当前的数据推测未来数据； 偏离型知识，揭示事物偏离常规的异常现象。 所有这些知识都可以在不同的概念层次上被发现，随着概念树的提升，从 微观到中观再到宏观，以满足不同用户、不同层次决策的需要。 以下将主要从挖掘任务和挖掘方法的角度，着重讨论数据抽取、分类发现、 聚类和关联规则发现四种非常重要的发现任务。 1 、数据抽取 数据抽取目的是对数据进行浓缩，给出它的紧凑描述。传统的也是最简单 的数据抽取方法是计算出数据库的各个字段上的求和值、平均值、方差值等统 计值，或者用直方图、饼状图等图形方式表示。数据挖掘主要关心从数据泛化 的角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从低层次抽象 到高层次上的过程。由于数据库上的数据或对象所包含的信息总是最原始、基 本的信息，人们有h , 3 希望能从较高层次的视图上处理或浏览数据，因此需要对 数据进行不同层次上的泛化以适应各种查询要求。 2 、分类发现 分类在数据挖掘中是一项非常重要的任务，目前在商业上应用最多。分类 的目的是学会一个分类函数或分类模型，该模型能把数据库中的数据项映射到 给定类别中的某一个。分类和回归都可用于预测。预测的目的是从利用历史数 据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行预测。和 第9 页 基于w e b 的数据挖掘技术 回归方法不同的是，分类的输出是离散的类别值，而回归的输出则是连续数值。 分类模型的构造方法有统计方法、机器学习方法、神经网络方法等等。不 同的分类模型有不同的特点。另外要注意的是，分类的效果一般和数据的特点 有关，有的数据噪声大，有的有缺值，有的分布稀疏，有的字段或属性间相关 性强，有的属性是离散的雨有的是连续值或混合式的。目前普遍认为不存在某 种方法能适合于各种特点的数据。 3 、聚类 聚类是把一鲳个体按照相似性归成若干类别，即“物以类聚”。它的目的是 使得属于同一类别的个体之间的距离尽可能的小，而不同类别上的个体间的距 离尽可能的犬。聚类方法包括统计方法、机器学习方法、神经网络方法和面向 数据库的方法。 4 、关联规则发现 关联规则足形式如= _ _ 的一种规则，”在购买面包和黄油的顾客中，有9 0 的 人同时也买了牛奶”( 面包+ 黄油( 牛奶) 。用于关联规则发现的主要对象是事务型 数据库，其中针对的应用则是售货数据，也称货篮数据。一个事务一般e h 女b t 几个部分组成：事务处理时间，一组顾客购买的物品，有时也有顾客标识号( 如 信用i 号) 。 山于条形码技术的发展，零售部门可以利用前端收款机收集存储大量的售 货数据。b i l l ，如果对这些历史事务数据进行分析，则可对顾客的购买行为提 供极有价值的信息。例如，可以帮助如何摆放货架上的商品( 如把顾客经常同时 买的商品放在一起) ，帮助如何规划市场( 怎样相互搭配进货) 。由此可见，从事 务数据中发现关联规则，对于改进零售业等商业活动的决策非常重要。 设i = i l ，i 2 ，【m ) 是一组物品集( 一个商场的物品可能有上万种) ，d 是一组事务集( 称之为事务数据库) 。d 中的每个事务t 是一组物品，显然满足t i 。称事务t 支持物品集x ，如果x t 。关联规则是如下形式的一种蕴含：x y ，其中xi ，y t ，目xr - 、y = i 。 ( 1 ) 称物品集x 具有大小为s 的支持度，如果d 中有s 的事务支持物品集 x ： ( 2 ) 称关联规则xy 在枣务数据库d 中具有大小为s 的支持度，如果物品 集x u y 的支持度为s ； ( 3 ) 称规则xy 在事务数据库d 中具有大小为c 的可信度，如果d 中支持 第- 1 0 页 基于w e b 的数据挖掘技术 物品集x 的事务中有c 的事务同时也支持物品集y 。 如果不考虑关联规则的支持度和可信度，那么在事务数据库中存在无穷多 的关联规则。事实上，人们一般只对满足一定的支持度和可信度的关联规则感 兴趣。在文献中，一般称满足一定要求的( 如较大的支持度和可信度) 的规则为 强规则。因此，为了发现出有意义的关联规则，需要给定两个阈值：最小支持度 和最小可信度。前者即用户规定的关联规则必须满足的最小支持度，它表示了 组物品集在统计意义上的需满足的最低程度：后者即用户规定的关联规则必 须满足的最小可信度，它反应了关联规则的最低可靠度。 在实际情况下，一种更有用的关联规则是泛化关联规则。因为物品概念间 存在一种层次关系，如央克衫、滑雪衫属于外套类，外套、衬衣又属于衣服类。 有了层次关系后，可以帮助发现一些更多的有意义的规则。例如买外套买鞋子 ”( 此处，外套和鞋子是较高层次上的物品或概念，因而该规则是一种泛化的关 联规则) 。由于商店或超市中有成千上万种物品，平均来讲，每种物品( 如滑雪 衫) 的支持度很低，因此有时难以发现有用规则：但如果考虑到较高层次的物品 ( 如外套) ，则其支持度就较高，从而町能发现有用的规则。 另外，关联规则发现的思路还可以用于序列模式发现。用户在购买物品时， 除了具有上述关联规律，还有h , 1 f 自j 上或序列一h 的规律，因为，很多时候顾客会 这次买这些东西，下次买同上次有关的一些东西，接着又买有关的某些东西。 2 2 2 数据挖掘的分析方法 数据挖掘的核心模块技术历经了数十年的发展，其中包括数理统计、人工 智能、机器学习。今天，这些成熟的技术，加上高性能的关系数据库引擎以及 广泛的数据集成，让数据挖掘技术在当前的数据仓库环境中进入了实用的阶段。 数据挖掘利用的技术越多，得出的结果精确性就越高。原因很简单，对于 某一种技术不适用的问题，其它方法即可能奏效，这主要取决于问题的类型以 及数据的类型和规模。数据挖掘方法有多种，其中比较典型的有关联分析、序 列模式分析、分类分析、聚类分析等。 1 、关联分析 利用关联规则进行数据挖掘。在数据挖掘研究领域，对于关联分析的研究 丌展得比较深入，人们提出了多种关联规则的挖掘算法，如a p r i o r i 、s t e m 、 a i s 、d h p 等算法。关联分析的目的是挖掘隐藏在数据间的相互关系，它能发现 数据库中形如”9 0 的顾客在一次购买活动中购买商品a 的同时购买商品b ”之类 的知识。2 、序列模式分析 第1 卜页 基于w e b 的数据挖掘技术 序列模式分析和关联分析相似，其目的也是为了挖掘数据之间的联系，但 序列模式分析的侧重点在于分析数据间的前后序歹口关系。它能发现数据库中形 如”在某一段时间内，顾客购买商品a ，接着购买商品b ，而后购买商品c ，即 序列a b c 出现的频度较高”之类的知识，序列模式分析描述的问题是：在给 定交易序列数据库中，每个序列是按照交易时间排列的一组交易集，挖掘序列 雨数作用在这个交易序列数据库上，返回该数据库中出现的高频序列。在进行 序列模式分析时，同样也需要由用户输入最小置信度c 和最小支持度s 。 3 、分类分析 设有一个数据库和一组具有不同特征的类别( 标记) ，该数据库中的每一个 汜录都赋予个类别的标记，这样的数据库称为示例数据库或训练集。分类分 析就是通过分析示例数据库中的数据，为每个类别做出准确的描述或建立分析 模型或挖掘出分类规则，然后用这个分类规则对其它数据库中的记录进行分类。 举一个简单的例子，信用卡公司的数据库中保存着各持卡人的记录，公司根据 信誉程度，已将持卡人记录分成三类：良好、一般、较差，并且类别标记已赋 给了各个记录。分类分析就是分析该数据库的记录数据，对每个信誉等级做出 准确描述或挖掘分类规则，如”信誉良好的客户是：t h n 些年收入在5 万元以上， 年龄在4 0 5 0 岁之削的人士”，然后根据分类规则对其它相同属性的数据库记 录进行分类。目前已有多种分类分析模型得到应用，其中几种典型模型是线性 回归模型、决策树模型、基本规则模型和神经网络模型。 4 、聚类分析 与分类分析不同，聚类分析输入的是一组未分类记录，并且这些记录应分 成几类事先也不知道。聚类分析就是通过分析数据库中的记录数据，根据一定 的分类规则，合理地划分记录集合，确定每个记录所在类别。它所采用的分类 规则是由聚类分析工具决定的。聚类分析的方法很多，其中包括系统聚类法、 分解法、加入法、动态聚类法、模糊聚类法、运筹方法等。采用不同的聚类方 法，对下相同的记录集合可能有不同的划分结果。 聚类分析和分类分析是个互逆的过程。例如在最初的分析中，分析人员 根据以往的经验将要分析的数据进行标定，划分类别，然后用分类分析方法分 析该数据集合，挖掘出每个类别的分类规则；接着用这些分类规则重新对这个 集合( 抛弃原来的划分结果) 避行划分，以获得更好的分类结果。这样分析人员 州以循环使用这两静分析方法直至得到满意的结果。 基丁w e b 的数据挖掘技术 2 2 3 数据挖掘的分析过程 数据挖掘是一个完整的过程，该过程从大型的数据库中挖掘先前未知的、 有效的、可使用的信息，并使用这些信息做出决策或丰富知识。 数据挖掘环境如下所示： 图1 一l 图1 - 1 描述了数据挖掘环境，数据挖掘工具从数据库中抽取有用的信息 由可视化工具表达给用户。 数据挖掘的基本过程和主要步骤如下： 1 、确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。挖掘 的最后结构是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数据 挖掘则带有盲目性是不会成功的。 2 、数据准备 i ) 数据的选择：搜索所有与业务对象有关的内部和外部数据信息，并从中 选择出适用于数据挖掘应用的数据； 2 ) 数据的预处理：研究数据的质量，为进一步的分析做准备，并确定将要 进行的挖掘操作的类型。 3 ) 数据的转换：将数据转换成一个分析模型。这个分析模型是针对挖掘 算法建立的，建立个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 3 、数据挖掘 对所得到的经过转换的数据进行挖掘。除了完善从选择合适的挖掘算法外， 其余一切工作都能自动地完成。 4 、结果分析 解释并评估结果。其使用的分析方法一般应作数据挖掘操作而定，通常会用 到可视化技术。 第t 3 页 基于w e b 的数据挖掘技术 5 、知识的同化 将分析所得到的知识集成到业务信息系统的组织结构中去。 图22 描述了数据挖掘的基本过程和主要步骤： ? ，一 、 延堪 一告畦捶l 卜f 百蹙蠢、_“t 冀囊l 卜 、竺竺夕、 【茸一鼍j17 、! ! 兰1 i 选择1i 硬娃理i1 转换il 皓妊l1 分i 图2 - 2 数据挖掘过程的步骤 在数据挖掘中被研究的业务对象是整个过程的基础，它驱动了整个数据挖 掘过程，也是检验最后结果和指引分析人员完成数据挖掘的依据和顾问。图2 - 2 各步骤是按一定顺序完成的，当然整个过程中还会存在步骤间的反馈。数据挖 掘的过程并不是自动的，绝大多数的工作需要人工完成。在这些步骤中6 0 的 时间用在数据准备上，这说明了数据挖掘对数据要求的严格性，而后期的挖掘 工作仪在总工作量的1 0 。 224 数据挖掘的常用技术 1 、人工神经i 网络 神经网络方法是模拟人脑神经元结构，以m p 模型和h e b b 学习规则为基础， 主要有3 种神经网络模型： ( 1 ) 前馈式网络。它以感知机、反向传播模型、函数型网络为代表，可用于预 测、模式识别等方面； ( 2 ) 反馈式网络。它以h o p f i e l d 的离散模型和连续模型为代表，分别用于联想 记忆和优化计算： ( 3 ) 自组织网络。它以a r t 模型、k o h o 。n 模型为代表，用于聚类分析等方而。 2 、遗传算法 遗传算法是模拟生物进化过程的算法，由： 个基本算子组成： ( 1 ) 繁殖。即从一个旧种群选出生命力强的个体，产生新的种群的过程； ( 2 ) 交叉。即选择两个不同的个体的部分进行交换，形成新个体的过程； 第1 4 - 页 基于w e b 的数据挖掘披术 ( 3 ) 变异。即对某些个体的某些基因进行变异，形成新个体的过程。 3 、决策树方法 决策树方法是利用信息论中的互信息寻找数据库中具有最大信息量的属性 字段，建立决策树的一个结点，再根据该书性字段的不同取值建立树的分支， 在每个分支集中重复建立树的下层结点和分支的过程。 4 、其他方法 另外还包括l f 每近搜索方法、集合论的粗集方法、规则推理、模糊逻辑、公 式发现等方法。 2 3 数据挖掘局限性 数据挖掘是一个工具，而不是万能的。它不会坐在你的数据库上一直监视 着数据库，然后当它发现有意义的模型时给你发一封电子邮件。它仍然需要了 解你的业务，理解你的数据，弄清分析方法。数据挖掘知识帮助商业人士更深 入、更容易的分析数据，它无法告诉你某个模型对你的企业的实际价值。而且 数据挖掘中得到的模型必须要在现实生活中进行验证。 数据挖掘中得到的预言模型并不会告诉你一个人为什么会做一件事、采取 某个行动，它只会告诉你它会这样做，为什么要人去考虑。比如，数据挖掘可 能会告诉你，如果这个人是男的、年收入在5 万到6 万之间，那么他可能会买 你的商品和服务。你可能会利用这条规则，集中向这类人推销你的商品而从中 获益，但是数据挖掘工具不会告诉你它们为什么会买你的东西，也不能保证所 有符合这条规则的人都会买。 为了保证数据挖掘结果的价值，用户必须了解自己的数据，这一点至关重 要。输入数据库中的异常数据、不相关的字段或相互冲突的字段、数据的编码 方式等都会对数据挖掘输出结果的质量产生影响。虽然一些算法自身会对上面 提到的这些问题做一些考虑，但让算法自己作所有这些决定是不明智的。 数据挖掘不会在缺乏指导的情况卜自动的发现模型。虽然数据挖掘工具使 用户不必再掌握艰深的统计分析技术，但用户仍然需要知道所选用的数据挖掘 工具是如何工作的，它所采用的算法的原理是什么。选用的技术和优化方法会 对模型的准确度和生成速度产生很大影向。 数据挖掘永远不会替代有经验的商业分析师或管理人员所起的作用，它只 是提供一个强大的工具。每个成熟、了解市场的公司都已经具有一些重要的、 第1 5 页 基丁w e b 的数据挖掘技术 能产生高回报的模型，这些模型可能是管理人员花了很长的时间，做了很多的 调查，甚至是经过很多失误之后得来的。数据挖掘工具要做的就是使这些模型 得到的更容易，更方便，而且有根据。 2 4 数据挖掘未来研究方向 当前，d m k i ) 研究方兴未艾，其研究与开发的总体水平相当于数据库技术在 7 0 年代所处的地位，迫切需要类似于关系模式、d b m s 系统和$ q l 查询语言等理 论和方法的指导，彳。能使d m k d 的应用得以普遍推广。预计在本世纪，d m k d 的 研究还会形成更大的高潮，研究焦点可能会集中