（计算机软件与理论专业论文）基于j2ee架构的数据挖掘平台中关联规则算法的实现.pdf

中文摘要 数据挖掘是近年来发展起来的新技术，通过数据挖掘，人们可以将知识发 现的研究成果应用于实际数据处理中，为科学决策提供支持。目前数据挖掘逐 渐发展成为一个多学科领域，涉及到多方面的技术，特别是和计算智能方法的 结合越来越紧密。 本文首先介绍了数据挖掘的基本概念、内容、功能、常用技术及未来的发 展方向。接着介绍了关联分析的基本概念、分类及经典的a p r i o r i i 】算法思想。关 联规则算法是数据挖掘中的核心技术之一，在整个数据挖掘过程中有着非常重 要的作用。 接着，本文从工程角度出发，设计并实现了一个基于分布式结构的数据挖 掘系统。本文从系统的体系结构、功能设计、模块划分、实现技术等方面进行 了详细的分析和讨论。该系统在j 2 e e 框架下，支持e j b 技术标准，为数据分析 员提供了一个基于“s 模式的数据挖掘平台。实验小组采用了组件化的思想，设 计了这个数据挖掘系统平台，提供给数据挖掘技术的研究者一个研究用的实验 平台，只要遵循我们的数据模型接口和挖掘模型接口，新的数据挖掘算法可以 很容易地集成到系统中来。同时，我们的平台又是一个具有实际应用价值、可 以与数据挖掘应用紧密结合的、便于升级和移植的挖掘系统框架。将数据挖掘 系统实现技术与最新的e j b 标准结合起来，采用组件技术设计，使得系统具有 良好的开放性和可扩展性。系统基于j 2 e e 技术设计，可以大大减少系统开发的 工作量同时具有良好的健壮性。 然后，提出了一种基于约束项的关联关系的挖掘新算法a p r i o r i t i d ，此算法 主要是改进原来的算法没有基础项集的选择这一缺点，对整个挖掘的基础项集 进行有针对性的筛选。本文从这个算法的产生原由、流程、实现过程、实现的 意义以及需要改进的地方等多个方面进行描述。对于这个算法我用e j b 进行封 装，并发布到j b o s s 服务器上，实现了整个算法分布式调度。这个算法还有很多 的不足，我从理论和实际的应用方面对其进行改进。 最后，本文总结了课题的主要研究工作。 关键词：数据挖掘，关联规则，a p r i o r i ，j 2 e e a b s t r a c t d a t am i n i n gi san e wt e c h n i q u e ，w h i c hh a v eb e c o m ei n c r e a s i n g l yp o p u l a ri n r e c e n ty e a r s p e o p l ec a na p p l yt h er e s e a r c hr e s u l to f k n o w l e d g ed i s c o v e r y t ot h ed a t a p r o c e s st h a tc a ns u p p o r tt h es c i e n c e d e c i s i o n 。n o wd a t am i n i n gh a sb e c o m ea s u b j e c t ， w h i c hi n v o l v e dl o t so fs c i e n c ed o m a i na n dt e c h n o l o g ye s p e c i a l l yi nc o m b i n i n gw i t h c o m p u t a t i o n a l n t e l l i g e n c e ( c d f i r s t l y , t h i sp a p e ri n t r o d u c e st h eb a s i cc o n c e p t s ，t a s k s ，f u n c t i o n s ，a p p l i c a t i o n s a n dd e v e l o p m e n tw a yo fd a t am i n i n g s e c o n d l y ，t h i sp a p e ri n t r o d u c e st h eb a s i c c o n c e p t ，c l a s s i f i c a t i o na n dc l a s s i c a la l g o r i t h mi d e a ss u c ha sa p r i o r io fa s s o c i a t i o n a n a l y s i s a s s o c i a t i o nr u l e s m e t h o di so n eo f t h ec o r et e c h n i q u e si nd a t a m i n i n g i t w a s v e r yi m p o r t a n ti nd a t am i n i n gp r o c e s s t h e n ，ad a t am i n i n gs y s t e mi sp r e s e n t e da n di m p l e m e n t e di nd i s t r i b u t i n gs t y l e a c c o r d i n gw i t he n g i n e e r i n g t h ea u t h o rp u td u ee m p h a s i so n t h ea r c h i t e c t u r ed e s i g n ， f u n c t i o nd e s i g n ，c o m p o n e n td e s i g na n di m p l e m e n t m i o nt e c h n o l o g i e so ft h es y s t e m t h ed a t am i n i n gs y s t e ms u p p o r t st h e e n t e r p r i s ej a v a b e e n ss p e c i f i c a t i o n sa n dt h e j 2 e ea r c h i t e c t u r e ，a l l o w i n gt h ed a t aa n a l y s t st ow o r kt h r o u g hac l i e n t s e r v e r s t y l e f r o ma l m o s ta n y w h e r e i nt h i sa r t i c l e ，t h ed a t am i n i n gg r o u pp r e s e n t st h ed e s i g no fa d a t am i n i n gp l a t f o r mu s i n gc o m p o n e n t - b a s e da p p r o a c h t h i sp l a t f o r mp r o v i d e sa n e x p e r i m e n t a lp l a t f o r mf o rd a t am i n i n gr e s e a r c h e r s c o m p l y i n gw i t ho a r d a t ao b j e c t i n t e r f a c ea n dm i n i n gm o d e li n t e r f a c e ，n e wm i n i n ga l g o r i t h m sc a nb ee a s i l yi n t e g r a t e d t oo u rs y s t e m o u rp l a t f o r ma l s oi sav a l u a b l es y s t e ms k e l e t o nf o rd a t a m i n i n g a p p l i c a t i o n e n t e r p r i s e j a v a b e a n s s p e c i f i c a t i o n ,u s i n gc o m p o n e n t o r i e n t e d t e c h n o l o g y m a k e st h es y s t e ma no p e na n d e a s y - t o u p g r a d es o l u t i o n a n dt h e n ，a l li m p r o v e da l g o r i t h mo fa p r i o r i t i di s p r o p o s e d ，i tc a nc o n q u e r d i s a d v a n t a g et h a tc u s t o m a r ya l g o r i t h mi sn o tc o n s i d e r e dt h eb a s ei t e m s e t sa n dd o e s n o tc o n s i d e r st h es t e po f s e l e c t i n g t h eb a s es e t t h i sp a p e r m a i n l y d i s c u s s e st h eo r i g i n a n dp r o c e s so ft h ea l g o r i t h m ，a l s oi t sr e a l i z a t i o n m e t h o d ，m e a n i n ga n dw a y so f i m p r o v e m e n t t h r o u g h t h e e n c a p s u l a t i o nu s i n ge j b ，m yw o r kf o c u s e so nt h e i i r c p l a n t a t i o no f t h ea l g o r i t h mo n t oj b o s ss e r v e r , t h i sr e a l i z e st h ed i s t r i b u t i v es c h e d u l e o f i t a d d i t i o n a l l y , i nl i g h to f t h ed e f e c t so ft h eo r i g i n a la l g o r i t h m ，ia l s os u c c e s s f u l l y i m p r o v e i tf r o mt h ea s p e c t s o f t h e o r ya n dp r a c t i c a la p p l i c a t i o n k e y w o r d s ：d a t am 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 i ，j 2 e e m - 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：垫煞日期：肼年 月加日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：抽券 五 、 导师签名项盗 日期一年| 堋7 日 基于j 2 e e 架构的数据挖掘平台中关联规则算法的实现 1 1 课题背景 第一章引言 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的 数据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进 行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地 实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则， 无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手 段，导致了“数据爆炸但知识贫乏”的现象。因此，数据挖掘可以说是数据库 技术与信息技术发展到当前高度后的一介必然趋势。当人们不再为数掘如何存 储、查询与管理而大伤脑筋时，如何分析、理解与利用这些数据，就成为了数 据使用者的必然要求。 数据挖掘技术主要分成“关联规则”、“时间序列”、“聚集”、“分类”、“估 值”等这几类。其中关联规则是一类很主要的知识，是数据挖掘研究的主要内 容之一，它能表示数据之间的相互关系，对统计和决策工作有重大意义。关联 规则挖掘算法一般都是基于交易数据库的，也有一些研究成果推广到一般数据 库。关联规则的主要应用包括商场的顾客购物分析，网络故障分析等。 数据挖掘系统的开发，大致经过了四个阶段： 第一代数据挖掘软件一般是针对某个特定应用，编写一个或几个算法进行 挖掘，就构成一个挖掘系统。数据的表示、提取、整理、过滤以及挖掘结果的 表示统统集成在起。数据一般采用向量模型来表示。该类系统通常缺乏数据 管理手段，挖掘的数据一次调入内存。其主要的缺点是当数据量比较大时，特 别是变化比较频繁时，就需要数据库或者数据仓库技术进行管理，第一代挖掘 系统显然不能满足要求。第一代数据挖掘软件的代表产品是新加坡国立大学开 发的c b a 系统。它实现的是基于关联规则的分类算法，能从关系数据或者交易 数据中挖掘关联规则，使用关联规则进行分类和预测。 第二代数据挖掘软件的特点是与数据库管理系统的集成，能够支持数据库 和数据仓库，和它们之间具有高性能的接口，可扩展性大大提高。由于使用了 数据库系统管理数据，所以该类系统能够挖掘大型数据集以及更加复杂的数据 基于j 2 e e 架构的数据挖掘平台中关联规则算法的实现 集。第二代系统的另一个显著的进步是用户与系统之间可以通过数据挖掘语言 进行交互，定义数据挖掘任务和返回数据挖掘结果。其主要缺点在于，由于没 有统一的模型描述标准，不同厂商的产品无法兼容。这一代的数据挖掘产品比 较多，象s f u 的d b m i n e r 和s a s 的s a se n t e r p r i s em i n e r 等。 第三代数据挖掘软件的特点是预言模型标记语言的广泛支持，数据挖掘系 统能够与预言模型系统无缝集成，使得数据挖掘软件产生的模型变化能够及时 地反映到预言模型系统中。由数据挖掘软件产生地预言模型能够自动地被操作 型系统接收，从而与操作型系统中的预言模型相联合提供决策支持的功能。这 个时期的另一个特点是网络数据挖掘和异质数据挖掘。s p s s 公司的s p s s c l e m e n t i n e 属于第三代数据挖掘系统，它能够以p m m l 格式提供与预言模型系 统的接口。信息技术的发展使得移动计算愈发重要。将数据挖掘与移动计算成 为当前的一个重要的研究领域。第四代数据挖掘软件是指能够挖掘各种嵌入系 统、移动系统和普遍存在( u b i q u i t o u s ) 计算设备产生的各种类型的数据。 第四代数据挖掘原型或者商业系统尚未见报。p k d d 2 0 0 1 上k a r g u p t a 发表 了一篇移动环境下挖掘决策树的论文，k a r g u p t a 是u n i v e r s i t yo fm a r y l a n d b a l t i m o r e c o u n t r y 正在研制的c a r e e r 数据挖掘项目的负责人。该项目研究期限 是2 0 0 1 年4 月到2 0 0 6 年4 月，目的是开发挖掘分布式和异质数据的( u b i q u i t o u s 设备) 的第四代数据挖掘系统。 1 2 课题任务 9 0 年代以来，基于组件和中间件的三层结构逐渐取代两层结构成为i n t e m e t 环境下电子商务系统开发的主流技术。s u n 提出的j 2 e e 框架就是三层结构的代 表技术之一。 我们教研室d a t a m i n g 小组开发的数据挖掘系统就是基于j 2 e e 架构的分布式 系统。本身这个系统我们想做成b s 结构的软件系统。但由于人员和技术力量 的有限，我们在新西兰w a i k a t o 大学开发的w e k a 系统的基础进行开发。我们目 前使用的界面基本上是w e k a 系统原来的界面，但w e k a 系统是单机版的系统， 我们把它改建成了分布式的并实现了分布式的调用。我们前期的工程是完成了 系统的改建，我们后期的工作是实现整个系统的界面的个性化。 在完成整个系统开发的时候，我还主要提出了一个基于约束项的关联规则 基于j 2 e e 架构的数据挖掘平台中关联规则算法的实现 新的算法而且把整个算法封装成e j b ，实现了已有算法的无缝集成。 在关联规则中最典型是a p f i o f i 算法，它是一种找频繁项集的基本算法。本 文介绍的基于约束项的关联规则新算法是基于a p f i o f i 算法的一种新的算法。 1 3 内容组织 本文共分四章，具体内容如下： 第一章：引言。本章是整个论文的开始部分。我主要是介绍了论文所讲述 的数据挖掘的应用背景以及本文为了实现整个数据挖掘系统所用到的一些关键 的技术并对论文的整体结构做了一个简单的介绍。 第二章：数据挖掘概述。本章先介绍了数据挖掘的产生，然后介绍了数据 挖掘研究的内容和本质、数据挖掘功能、常用方法和流程，最后介绍了数据挖 掘未来的研究方向和本文的研究内容。 第三章：关联规则的研究。本章首先介绍关联规则的基本概念，然后讨论 了经典的a p n o d 算法的算法思想，最后详细介绍了a p r i o r i t i d 算法。 第四章：c i l a b 基于j 2 e e 架构的数据挖掘系统。本章主要介绍了电子科技 大学计算智能实验室基于j 2 e e 架构的开放式数据挖掘系统的设计意义、目的、 系统结构及模块的划分和模块的流程及具体实现方法。 第五章：基于约束项的关联规则新算法。本章提出的新算法是为了解决数 据库中挖掘数据量过多和忽略了不是频繁项但很有价值的关联规则的问题，采 用了选择基础项集的方法。在本章中，该算法的产生原由、设计思想、详细过 程做了详细的介绍说明。 第六章：结论。本章是整个论文的结尾。对整个论文做了一个总结，并对 还没完成的工作做了一个计划，是整个论文的后续工作。 基于j 2 e e 架构的数据挖掘平台中关联规则算法的实现 第= 章数据挖掘概述 有人说，数据挖掘将成为继网络之后的下一个技术热点，这种说法并不为 过。近年来，数据挖掘已经引起了信息产业界的极大关注，这是快速增长的数 据量和日益贫乏的信息量之间矛盾运动的必然结果。在对基于关联规则的数据 挖掘算法进行深入研究之前，我们有必要对数据挖掘的由来、概念、挖掘的对 象、产生的模式、常用的技术等内容有一个较为全面的了解，以期更加透彻地 领悟数据挖掘这一极具发展潜力的新兴领域。 2 1 数据挖掘的产生 数据挖掘是按照一定的规则对数据库和数据仓库中已有的数据进行信息开 采、挖掘和分析，从中识别和抽取隐含的模式和有趣知识，并利用它们为决策 者提供决策依据。由于数据挖掘的价值在于扫描数据仓库或建立非常复杂的查 询，数据和文本挖掘工具必须提供很高的吞吐量，并拥有并行处理功能，而且 可以支持多种采集技术。数据挖掘工具应该拥有良好的扩展功能，并且能够支 持将来可能遇到的各种数据( 或文档) 和计算环境。 数据挖掘的任务是从数据中发现模式。模式有很多种，按功能可分为两大类： 预测型( p r e d i c t i v e ) 模式和描述型( d e s c r i p t i v e ) 模式。预测型模式是可以根据 数据项的值精确确定某种结果的模式。挖掘预测型模式所使用的数据也都是可 以明确知道结果的。描述型模式是对数据中存在的规则做一种描述，或者根据 数据的相似性把数据分组。描述型模式不能直接用于预测。在实际应用中，根 据模式的实际作用，细分为分类模式、回归模式、时间序列模式、聚类模式、 关联模式和序列模式6 种。其中包含的具体算法有货篮分析( m a r k e t a n a l y s i s ) 、 聚类检测( c l u s t e r i n gd e t e c t i o n ) 、神经网络( n e u r a ln e t w o r k s ) 、决策树方法 ( d e c i s i o n t r e e s ) 、遗传算法( g e n e t i c a n a l y s i s ) 、连接分析( n 1 1 l c a n a l y s i s ) 、基 于范例的推理( c a s eb a s e dr e a s o n i n g ) 和粗集( r o u g hs e t ) 以及各种统计模型。 数据库技术在经过了8 0 年代的辉煌之后，人们逐渐认识到，查询是数据库 的奴隶，发现才是数据库的主人。“数据只为职员服务，不为决策者服务r 这 基于j 2 e e 架构的数据挖掘平台中关联规则算法的实现 是很多单位的领导在热心数据库建设后所发出的感叹。因此，在需求的驱动下， 很多数据库学者从对演绎数据库的研究转向对归纳数据库的研究。专家系统曾 经是人工智能研究工作者的骄傲，但由于其在知识获取、知识表示、缺乏常识 等方面的瓶颈，使得专家系统目前还停留在构造诸如发动机故障论断一类的水 平上。这自然促使人工智能学者开始正视现实生活中大量的、不完全的、有噪 声的、模糊的、随机的大数据样本，走上了数据挖掘的道路。数理统计是应用 数学中最重要、最活跃的学科之一，它在计算机发明之前就诞生了，迄今己有 几百年的发展历史，然而，数理统计和数据库技术结合得并不算快。在人们有 了从数据查询到知识发现、从数据演绎到数据归纳的要求之后，概率论和数理 统计才获得了新的生命力，所以才会在d m k d ( 数据挖掘和知识发现) 这个结 合点上，立即呈现出“忽如一夜春风来，千树万树梨花开”的繁荣景象。 从进化的角度来看，数据挖掘技术的产生过程实际上反映了数据库技术的 演化过程，图2 1 中的表清楚地说明了这一点。 图2 - 1 数据挖掘技术的产生过程 基于j 2 e e 架构的数据挖掘平台中关联规则算法的实现 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果，同时，也 是信息技术自然演化的结果。从机器学习到知识工程，从知识工程到专家系统， 8 0 年代人们又在新的神经网络理论的指导下重新回到机器学习，随后又进入到 数据库中的知识发现，接着又相辅相成地产生数据挖掘，在此期间，数据仓库 技术的出现和逐步成熟为数据挖掘技术的繁荣注入了强劲的动力，最近人们又 认识到把统计分析方法和数据挖掘有机地结合将是最好的策略。因此，数据挖 掘是一门交叉学科，其发展是一个螺旋上升的过程。 2 2 数据挖掘研究的内容 从广义上讲，数据挖掘( d a t am i n i n g d m ) 是指从大量的、不完全的、有噪 声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又 是潜在有用的信息和知识的过程。这个定义包括以下四个层次的含义： 数据源必须是真实的、大量的、含噪声的； 发现的是用户感兴趣的知识； 发现的知识要可接受、可理解、可运用，最好能用自然语言表达发现结果； 并不是要求发现放之四海皆准的知识，也不是要去发现崭新的自然科学定理 和纯数学公式，更不是什么机器定理证明，所有发现的知识都是相对的，是有 特定前提和约束条件、面向特定领域的。 从商业角度出发，数据挖掘可以描述为：按企业既定业务目标，对大量的 企业数据进行探索和分析，揭示隐藏的、未知的或验证己知的规律性，并进一 步将其模型化的先进有效的方法。 随着d m k d 研究逐步走向深入，数据挖掘和知识发现的研究已经形成了三 根强大的技术支柱：数据库、人工智能和数理统计。因此，k d d 大会程序委员 会曾经由这三个学科的权威人物同时来任主席。目前d m k d 的主要研究内容包 括基础理论、发现算法、数据仓库、可视化技术、定性定量互换模型、知识表 示方法、发现知识的维护和再利用、半结构化和非结构化数据中的知识发现以 及网上数据挖掘等。数据挖掘所发现的知识最常见的有以下四类3 】： 2 2 1 广义知识 广义知识指类别特征的概括性描述知识。根据数据的微观特性发现其表征 基于j 2 e e 架构的数据挖掘平台中关联规则算法的实现 的、带有普遍性的、较高层次概念的、中观和宏观的知识，反映同类事物共同 性质，是对数据的概括、精炼和抽象。 广义知识的发现方法和实现技术有很多，如数据立方体、面向属性的归约 等。数据立方体还有其他一些别名，如“多维数据库”、“实现视图”、“o l a p ” 等。该方法的基本思想是实现某些常用的代价较高的聚集函数的计算，诸如计 数、求和、平均、最大值等，并将这些实现视图储存在多维数据库中。既然很 多聚集函数需经常重复计算，那么在多维数据立方体中存放预先计算好的结果 将能保证快速响应，并可灵活地提供不同角度和不同抽象层次上的数据视图。 另一种广义知识发现方法是加拿大s i m o n f r a s e r 大学提出的面向属性的归约方 法。这种方法以类s q l 语言表示数据挖掘查询，收集数据库中的相关数据集， 然后在相关数据集上应用一系列数据推广技术进行数据推广，包括属性删除、 概念树提升、属性阈值控制、计数及其他聚集函数传播等。 2 2 2 关联知识 它反映一个事件和其他事件之间依赖或关联的知识。如果两项或多项属性 之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测。最为 著名的关联规则发现方法是r a 9 1 a w a l 提出的a p r i o r i 算法。关联规则的发现可 分为两步。第一步是迭代识别所有的频繁项目集，要求频繁项目集的支持率不 低于用户设定的最低值；第二步是从频繁项目集中构造可信度不低于用户设定 的最低值的规则。识别或发现所有频繁项目集是关联规则发现算法的核心，也 是计算量最大的部分。 2 2 3 分类知识 它反映同类事物共同性质的特征型知识和不同事物之间的差异型特征知 识。最为典型的分类方法是基于决策树的分类方法。它是从实例集中构造决策 树，是一种有指导的学习方法。该方法先根据训练子集( 又称为窗口) 形成决 策树。如果该树不能对所有对象给出正确的分类，那么选择一些例外加入到窗 口中，重复该过程一直到形成正确的决策集。最终结果是一棵树，其叶结点是 类名，中间结点是带有分枝的属性，该分枝对应该属性的某一可能值。最为典 型的决策树学习系统是i d 3 ，它采用自顶向下不回溯策略，能保证找到一个简单 基于j 2 e e 架构的数据挖掘平台中关联规则算法的实现 的树。算法c 4 5 和c 5 0 都是i d 3 的扩展，它们将分类领域从类别属性扩展到数 值型属性。 数据分类还有统计、粗糙集( r o u g h s e t ) 等方法。线性回归和线性辨别分析 是典型的统计模型。为降低决策树生成代价，人们还提出了一种区间分类器。 最近也有人研究使用神经网络方法在数据库中进行分类和规则提取。 2 2 4 预测型知识 它根据时间序列型数据，由历史的和当前的数据去推测未来的数据，也可 以认为是以时间为关键属性的关联知识。 目前，时间序列预测方法有经典的统计方法、神经网络和机器学习等。1 9 6 8 年b o x 和j e n k i n s 提出了一套比较完善的时间序列建模理论和分析方法，这些经 典的数学方法通过建立随机模型，如自回归模型、自回归滑动平均模型、求和 自回归滑动平均模型和季节调整模型等，进行时间序列的预测。由于大量的时 间序列是非平稳的，其特征参数和数据分布随着时间的推移而发生变化。因此， 仅仅通过对某段历史数据的训练，建立单一的神经网络预测模型，还无法完成 准确的预测任务。为此，人们提出了基于统计学和基于精确性的再训练方法， 当发现现存预测模型不再适用于当前数据时，对模型重新训练，获得新的权重 参数，建立新的模型。也有许多系统借助并行算法的计算优势进行时间序列预 测。 2 2 5 偏差型知识 此外，还可以发现其他类型的知识，如偏差型知识( d e v i 撕o n ) ，它是对差异 和极端特例的描述，揭示事物偏离常规的异常现象，如标准类外的特例，数据 聚类外的离群值等。所有这些知识都可以在不同的概念层次上被发现，并随着 概念层次的提升，从微观到中观、到宏观，以满足不同用户不同层次决策的需 要。 2 3 数据挖掘的功能 数据挖掘通过预测未来趋势及行为，做出前瞻的、基于知识的决策。数据 基于j 2 e e 架构的数据挖掘平台中关联规则算法的实现 挖掘的目标是从数据库中发现隐含的、有意义的知识，主要有以下五类功能 2 3 1 自动预测趋势和行为 数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工分 析的问题如今可以迅速直接由数据本身得出结论。一个典型的例子是市场预测 问题，数据挖掘使用过去有关促销的数据来寻找未来投资中回报最大的用户， 其它可预测的问题包括预报破产以及认定对指定事件最可能做出反应的群体。 2 3 2 关联分析 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变 量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、 因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据 库中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有 可信度。 2 3 3 聚类 数据库中的记录可被划分为一系列有意义的子集，即聚类。聚类增强了人 们对客观现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括 传统的模式识别方法和数学分类学。8 0 年代初m i c h a l s k i 提出了概念聚类技术 及其要点是，在划分对象时不仅考虑对象之间的距离，还要求划分出的类具有 某种内涵描述，从而避免了传统技术的某些片面性。 2 3 4 概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。 概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者 描述不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有 对象的共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。 2 3 5 偏差检测 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。 基于j 2 e e 架构的数据挖掘平台中关联规则算法的实现 偏差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结 果与模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是，寻找 观测结果与参照值之间有意义的差别。 2 。4 数据挖掘常用方法 很多技术都可以用于数据挖掘。机器学习、模式识别、人工智能等领域的 技术、方法经过改进，大都可以应用于数据挖掘。常用的方法有决策树、粗糙 集、神经网络、遗传算法、概念树等。 i 、策树方法 利用信息论中的信息增益寻找数据库中具有最大信息量的字段，建立决策 树的个结点，再根据字段的不同取值建立树的分支：在每个分支子集中重复 建树的下层结点和分支的过程，即可建立决策树。国际上最有影响和最早的决 策树的q u i u l a n 研制的i d 3 方法，数据库越大这种方法运行的效果越好。在i d 3 方法的基础上，又产生了许多决策树方法。 2 、神经网络方法 它模拟人脑神经元结构，以m p 模型和h e b b 规则为基础，建立了三大类多 种神经网络模型： 1 ) 前魁式网络它以感知机、反向传播模型、函数网络为代表，可用于预测、 模式识别等方面。 2 ) 反馈式网络它以h o p f i e l d 的离散模型和连续模型为代表，分别用于联想 和优化计算。 3 ) 自组织网络它以a r t 模型、k o h o l o n 模型为代表，用于聚类。 神经网络的知识体现在网络连接的权值上，是一个分布式矩阵结构；神经 网络的学习体现在神经网络权值的逐步计算上( 包括反复迭代或累加计算) 。运用 神经网络的方法产生许多分类器。 3 、覆盖正例排斥反例方法 它是利用覆盖所有的正例、排斥所有的反例的思想来寻找规则。比较典型 的有m i c h a l s k i 的a q l l 方法。a q l t 的主要思想是，在正例集中任选一个种子， 基于j 2 e e 架构的数据挖掘平台中关联规则算法的实现 到反例集中逐个比较，对字段取值构成的选择子相容则舍去，相斥则保留。按 此思想循环所有的正例种子将得到正例集的规则( 选择子的合取式) 。 4 、粗糙集( r o u g hs e t s ) 方法 在数据库中，将每个元组看成一个对象，列元素看成属性( 分为条件属性和 决策属性) 等价关系r 定义为不同对象在某个( 或几个) 属性上取值相同，这些满 足等价关系的对象组成的集合称为该等价关系r 的等价类。条件属性上的等价 类e 与决策属性上的等价类y 之间有三种情况：1 下近似：y 包含e ；2 上近 似：y 和e 的交非空；3 无关：y 和e 的交为空。对下近似建立确定性规则，对 以上近似建立不确定性规则( 含可信度) ，对无关的情况则不存在规则。 5 、概念树方法 对数据库记录的属性字段按归类方式进行抽象，建立起来的层次结构称为 概念树。如：“城市”概念树的最下层是具体市名或县名( 如：南京、合肥等) ， 它的直接上层是省名( 如：江苏、安徽等) ，省名的直接上层是国家行政区f 如： 华东、华北等) ，再上层是国名( 如：中国、美国等) 。利用概念树提升的方法可 以大大地浓缩数据库中的记录。对多个属性字段的概念树进行提升，将得到高 度概括的知识基表，然后再将知识基表转换为规则。 6 、遗传算法 这是模拟生物进化过程的算法，有三个算子组成： 1 ) 繁殖( 选择) 是从一个旧种群( 父代) 选出生命力强的个体，产生新种 群( 后代) 的过程。 2 ) 交叉( 重组) 选择两个不同个体( 染色体) 的部分( 基因) 进行交换， 形成新个体。 3 ) 变异( 突变) 对某些个体的某些基因进行变异( 1 变0 ，0 变1 ) 。 这种遗传算法可起到产生优良后代的作用。这些后代需满足适应值，经过 若干代的遗传，将得到满足要求的后代( 问题的解) 。遗传算法己在优化计算和 分类机器学习方法方面发挥了显著的作用。 7 、公式发现 在工程和科学数据库( 由试验数据组成) 中，对若干数据项( 变量) 进行一定 基于j 2 e e 架构的数据挖掘平台中关联规则算法的实现 的数学运算，求得相应数学公式。比较典型的b a c o n 发现系统完成了对物理 学中大量定律的重新发现。其基本思想是，对数据项进行初等数学运算( 加、 减、乘、除等) ，形成组合数据项，若它的值为常数项，就得到了组合数据项等 于常数的公式。 8 、统计分析方法 在数据库字段项之间存在两种关系：函数关系( 能用函数公式表示的确定性 关系) ；相关关系( 不能用函数公式表示，但仍是相关确定关系) 。对它们的分析 采用如下方法：回归分析、相关分析、主成分分析，从中可以发现有用的关联 规则。 9 、模糊论方法 利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和 模糊聚类分析。模糊性是客观存在的。系统的复杂性越高，精确化能力就越低， 即模糊性越强。这是z a d e h 总结出的互克性原理。 1 0 、可视化技术 可视化数据分析技术拓宽了传统的图表功能，使用户对数据的剖析更清晰。 例如，把数据库中的多维数据变成多种图形，这对揭示数据的内涵、内在本质 及规律起了很大的作用。 2 5 数据挖掘的流程 2 ，5 1 数据挖掘的环境 数据挖掘是指一个完整的过程，该过程从大型数据库中挖掘先前未知的， 有效的，可实用的信息，并使用这些信息做出决策或丰富知识。 数据挖掘环境可示意如下图； 图2 - 1 数据挖掘环境框图 基于j 2 e e 架构的数据挖掘平台中关联规则算法的实现 2 5 2 数据挖掘过程图 图2 - 2 数据挖掘工程的步骤图 2 5 3 数据挖掘过程工作量 在数据挖掘中被研究的业务对象是整个过程的基础，它驱动了整个数据挖 掘过程，也是检验最后结果和指引分析人员完成数据挖掘的依据和顾问。图1 2 各步骤是按一定顺序完成的，当然整个过程中还会存在步骤间的反馈。数据挖 掘的过程并不是自动的，绝大多数的工作需要人工完成。图2 - 3 给出了各步骤在 整个过程中的工作量之比。可以看到，6 0 的时间用在数据准备上，这说明了数 据挖掘对数据的严格要求，而后挖掘工作仅占总工作量的1 0 。 基于j 2 e e 架构的数据挖掘平台中关联规则算法的实现 图2 - 3 数据挖掘过程工作量比例图 2 5 4 数据挖掘未来的研究方向 当前，d m k d 研究方兴未艾，其研究与开发的总体水平相当于数据库技术 在7 0 年代所处的地位，迫切需要类似于关系模式、d b m s 系统和s q l 查询语言 等理论和方法的指导，才能使d i v l r g d 的应用得以普遍推广。预计在本世纪， d m k d 的研究还会形成更大的高潮，研究焦点可能会集中到以下几个方面： 发现语言的形式化描述，即研究专门用于知识发现的数据挖掘语言，也 许会像s q l 语言一样走向形式化和标准化； 寻求数据挖掘过程中的可视化方法，使知识发现的过程能够被用户理 解，也便于在知识发现的过程中进行人机交互； 研究在网络环境下的数据挖掘技术( w e b m i n i n g ) ，特别是在因特网上建 立d m k d 服务器，并且与数据库服务器配合，实现w e b m i n i n g ； 加强对各种非结构化数据的开采( d a t a m i n i n g f o r a u d i o & v i d e o ) ，如对文 本数据、图形数据、视频图像数据、声音数据乃至综合多媒体数据的开采；处 理的数据将会涉及到更多的数据类型，这些数据类型或者比较复杂，或者是结 构比较独特。为了处理这些复杂的数据，就需要一些新的和更好的分析和建立 模型的方法，同时还会涉及到为处理这些复杂或独特数据所做的费时和复杂数 据准备的一些工具和软件。 但是，不管怎样，需求牵引与市场推动是永恒的，d m k d 将首先满足信息 时代用户的急需，大量的基于d m k d 的决策支持软件产品将会问世。只有从数 基于j 2 e e 架构的数据挖掘平台中关联规则算法的实现 据中有效地提取信息，从信息中及时地发现知识，才能为人类的思维决策和战 略发展服务。也只有到那时，数据才能够真正成为与物质、能源相媲美的资源， 信息时代才会真正到来。 2 6 数据挖掘工具 2 6 1 常见的数据挖掘工具 在数据挖掘技术日益发展的同时，许多数据挖掘的商业软件工具也逐渐问 世。数据挖掘工具主要有两类：特定领域的数据挖掘工具和通用的数据挖掘工 具。特定领域的数据挖掘工具针对某个特定领域的问题提供解决方案。在设计 算法的时候，充分考虑到数据、需求的特殊性，并作了优化。对任何领域，都 可以开发特定的数据挖掘工具。例如，i b m 公司的a d v a n c e d s c o u t 系统针对n b a 的数据，帮助教练优化战术组合：加州理工学院喷气推进实验室与天文科学家 合作开发的s k i c a t 系统，帮助天文学家发现遥远的类星体；芬兰赫尔辛基大学 计算机科学系开发的t a s a ，帮助预测网络通信中的警报。 特定领域的数据挖掘工具针对性比较强，只能用于一种应用：也正因为针 对性强，往往采用特殊的算法，可以处理特殊的数据，实现特殊的目的，发现 的知识可靠度也比较高。 通用的数据挖掘工具不区分具体数据的含义，采用通用的挖掘算法，处理 常见的数据类型，一般提供六种模式。例如，i b h 公司a l m a d e n 研究中心开发的 q u e s t 系统，s g x 公司开发的m i n e s e t 系统，加拿大s i m o n f r a s e r 大学开发的 d b m i n e r 系统。通用的数据挖掘工具可以做多种模式的挖掘，挖掘什么、用什么 来挖掘都由用户根据自己的应用来选择。 下面简单介绍几种数据挖掘工具： 1 q u e s t q u e s t 是i b m 公司a l m a d e n 研究中心开发的一个多任务数据挖掘系统，目的 是为新一代决策支持系统的应用开发提供高效的数据开采基本构件。系统具有 如下特点： 1 ) 提供了专门在大型数据库上进行各种开采的功能：关联规则发现、序列 模式发现、时间序列聚类、决策树分类、递增式主动开采等。 基于3 2 e e 架构的数据挖掘平台中关联规则算法的实现 2 ) 各种开采算法具有近似线性( o ( n ) ) 计算复杂度，可适用于任意大小的 数据库。 3 ) 算法具有找全性，即能将所有满足指定类型的模式全部寻找出来。 4 ) 为各种发现功能设计了相应的并行算法。 2 m i n e s e t m i n e s e t 是由s g i 公司和美国s t a n d f o r d 大学联合开发的多任务数据挖掘系 统。m i n e s e t 集成多种数据挖掘算法和可视化工具，帮助用户直观地、实时地发 掘、理解大量数据背后的知识。m i n e s e t 2 6 有如下特点： 1 ) m i n e s e t 以先进的可视化显示方法闻名于世。m i n e s e t 2 6 中使用了6 种 可视化工具来表现数据和知识。对同一个挖掘结果可以用不同的可视化工具以各 种形式表示，用户也可以按照个人的喜好调整最终效果，以便更好地理解。 m i n e s e t 2 6 中的可视化工具有s p l a t v i s u a l i z e 、s c a t t e r v i s u a l i z e 、 m a p v i s u a l i z e 、t r e e v i s u m i z e 、r e c o r d v i e w e r 、s t a r i s t i c s v i s u a l i z e 、 c