（模式识别与智能系统专业论文）关联规则挖掘算法及其流程工业应用研究.pdf

摘要 近年来，数据挖掘技术的研究引起了国际人工智能和数据库等领域专家与学 者的广泛关注。在事务数据库中挖掘关联规则是数据挖掘领域中一个非常重要的 研究课题，目前其实际应用主要集中在零售业，比如超级市场的销售管理等，在 流程工业领域中的实际应用尚不多见。除零售业之外，流程工业中也存在着大量 的关联规则，比如：某种产品产量的提高引起另一种产品产量的提高，等。如何 将关联规则挖掘技术应用到这类问题中，挖掘出流程工业中有用的关联规则，从 而为流程工业中的生产决策提供良好的依据，为本文的主要研究内容。 本文以关联规则挖掘理论为基础，以实际工程应用为最终目标，在广泛查阅 相关文献、了解相关研究进展的基础上，深入进行了关联规则挖掘算法的研究与 改进，并系统地提出了关联规则挖掘算法在流程工业中进行实际应用的方略。全 文由以下五章组成： 第一章为绪论，阐述了数据挖掘研究内容，特别对数据挖掘技术的发展和现 状进行了完整的综述。 第二章介绍了关联规则挖掘技术的基础，阐述了关联规则挖掘发展状况及其 基本概念。 第三章提出了一种基于自适应支持度的布尔式关联规则挖掘算法，包括布尔 式挖掘原理及挖掘算法的自适应支持度框架。 第四章探讨了基于自适应支持度的布尔式关联规则挖掘算法在流程工业中 的应用问题，并以菜农药厂三唑磷合成过程为实例，阐述了关联规则挖掘算法在 流程工业中进行实际应用的整套方案。 第五章针对复杂工业大系统的特点，提出了种基于关联规则的故障诊断方 法。对尿素生产过程的仿真实验结果表明，该方法能够有效施挖掘隐藏在大量数 据背后的故障模式知识，有效的突破了故障诊断专家系统在知识获取方面的瓶 颈，增强了故障诊断系统的推理诊断能力。 第六章总结全文并讨论了进一步需要研究的问题。 关键词：数据挖掘关联规则流程工业布尔式自适应三唑磷故障诊断专家 系统 浙江大学硕士学位论文 a b s t r a c t r e c e n t l y , t h et e c h n i q u eo f d a t am i n i n g ( d m ) i sw i d e l yc a r e d b yt h e i n t e r n a t i o n a le x p e r t si nt h ef i e l d so f a r t i f i c i a li n t e l l i g e n c e ( a i ) a n dd a t a b a s e t h e m i n i n go fa s s o c i a t i o nr u l e si nt h ed a t a b a s e so ft r a n s a c t i o n si so n e o f t h em o s ti m p o r t a n ts u b j e c t si nt h ef i e l do fd m a tt h ep r e s e n tt i m e t h em i n i n g o fa s s o c i a t i o nr u l e si nt h ed a t a b a s e so ft r a n s a c t i o n si s m o s t l ya p p l i e dt ot h e m e r c h a n d i s ef i e l d f o re x a m p l e ，t h ec o n t r o lo ft h es a l e si ns u p e rm a r k e t s ，e t c t h ep r e s e n ta p p l i c a t i o n so fa s s o c i a t i o nr u l e sm i n i n gi ni n d u s t r i a lp r o c e s sa r e n o t p r o f o u n d a st h em e r c h a n d i s ef i e l d t h e r ea r ea l s oal o to fa s s o c i a t i o nr u l e s i ni n d u s t r i a l p r o c e s s f o re x a m p l e ，t h eo u t c o m eo fo n ek i n d o fp r o d u c ti s a s s o c i a t e dw i t ht h eo u t c o m eo ft h eo t h e rk i n do fp r o d u c t t h em a i nt o p i co ft h i st h e s i si sh o wt oa p p l yt h et e c h n i q u eo fa s s o c i a t i o n r u l e sm i n i n gt ot h ei n d u s t r i a lp r o c e s sa n dm a k et h 色a s s o c i a t i o nr u l e su s eo ft h e d e c i s i o nm a k i n gi nt h ei n d u s t r i a lp r o c e s s t h i st h e s i si sb a s e do nt h et h e o r yo f a s s o c i a t i o nr u l e s m i n i n ga n do b j e c t e d t ot h e p r a c t i c a la p p l i c a t i o n o ft h e i n d u s t r i a lp r o c e s s i nt h i st h e s i s ，t h ea l g o r i t h mo fa s s o c i a t i o nr u l e sm i n i n gi s i m p r o v e d a n dt h e p r o g r a m o ft h e a p p l i c a t i o n o ft h e m i n i n ga l g o r i t h m i s p r e s e n t e d t h em a i nw o r kc o u l db es t a t e da sf o l l o w s ： i nc h a p t e r1 ，t h em a i nc o n t e n t so fd m t h ec l a s s i f i c a t i o no fv a r i o u sd m m e t h o d sa n dp r o s p e c t sa r es u m m a r i z e d ，e s p e c i a l l yt h eh i s t o r ya n ds t a t u s a b o u td mm e t h o d s i nc h a p t e r 2 t h eb a s i so fa s s o c i a t i o nr u l em i n i n gt e c h n i q u ei si n t r o d u c e d ， i n c l u d i n gt h eh i s t o r ya n ds t a t u sa b o u ta s s o c i a t i o nr u l e sm i n i n gm e t h o d s i nc h a p t e r3 t h ee f f e c t i v ea d a p t i v e s u p p o r tb o o l e a na l g o r i t h mf o rm i n i n g a s s o c i a t i o nr u l e si s p r e s e n t e d ，i n c l u d i n gt h ea d a p t i v e - s u p p o r tf r a m eo ft h e a l g o r i t h ma n d i t sb o o l e a nf u n d a m e n t a l s i n c h a p t e r4 ，t h ep r o g r a mo ft h ea s s o c i a t i o n r u l e sm i n i n ga l g o r i t h m s a p p l i c a t i o nt ot h ep r o c e s so ft r i a z o p h o si sp r e s e n t e d 1 1 a bs t r a c t i n c h a p t e r5 ，am e t h o do ff a i l u r ed i a g n o s i sb a s e do na na l g o r i t h mo f m i n i n ga s s o c i a t i o nr u l e sw i t hm u l t i p l em i n i m u ms u p p o f f si s p r e s e n t e d t h i s m e t h o di s a p p l i e dt ot h ef a i l u r ed i a g n o s i so fp r o c e s s t h es i m u l a t i o nr e s u l t s s h o wt h a tt h ep r o p o s e dm e t h o di se f f e c t i v ef o rt h e f a i l u r ed i a g n o s i s c h a p t e r6c o n c l u d e sw i t has u m m a r ya n dd i s c u s s i o n so ff u t u r ea n d p r o s p e c t i v er e s e a r c ho no p e np r o b l e m s ， 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 n r u l e s p r o c e s si n d u s t r y , b o o l e a n ， s e l f - a d a p t i o n ，t r i a z o p h o s ，f a u l td i a g n o s i s ，e x p e r is y s t e m i l l 浙江大学硕士学位论文 致谢 在硕士论文完成之际，衷心感谢导师荣冈教授多年来对我的关心 和指导。两年半的时光里，荣老师渊博的学识、严谨的学风和睿智幽 默的学者风范使我获益匪浅，是我一直以来以及今后学习和工作上的 榜样。 感谢王树青教授、王宁教授、冯毅萍副教授、张泉灵副教授，他 们给予本人很多的鼓励和帮助，在此向他们表示衷心的感谢。 感谢张溥明、赵向海、宋洁蔚、王达、朱炜、王晓初、章鹏、高 峰、裘绍翔、赵小强、张惠良、李荣雨、张奇然、吴剑强、裴瑞凌、 吕品晶、顾海杰等人对我的帮助和支持。与他们在学习上的交流以及 一个实验室的共同生活，给我留下了很多美好的回忆。 感谢我的父母和家人，他们总是给予我最需要的理解和支持。 特别感谢我的知心爱人章瑛萍对我长期的支持与关心。 张建明 2 0 0 4 年3 月于求是园 i v 第一章数据挖掘研究概论 摘要 本章首先描述了数据挖掘的概念，以及数据挖掘的主要内容；然后介绍了一些数据挖掘 的方法；随后，综述了关联规则挖掘技术的研究发展状况，并介绍了数据挖掘领域的发展方 向和热点问题，最后概述了全文的主要内容。 关键词：数据挖掘关联规则 1 1 引言 半个世纪以来，人们利用信息技术生产和搜集数据的能力在不断提高。当前 有无数个数据库被用于商业管理、政府办公、科学研究和工程开发等，这一势头 仍将持续发展下去。特别是近年来，i n t e r n e t 的迅猛发展，网络经济、注意力 经济等新概念的出现，以其巨大的社会效益和极富挑战与机遇的内涵，成为信息 科学最引人注目的研究课题。于是，一个新的挑战被提了出来：在这被称之为信 息爆炸的时代，信息过量几乎成为人人需要面对的问题。如何才能不被信息的汪 洋大海所淹没，从中及时发现有用的知识，提高信息利用率呢? 要想使数据真正 成为一个公司的资源，只有充分利用它为公司自身的业务决策和战略发展服务才 行，否则大量的数据可能成为包袱，甚至成为垃圾。因此，丽对“信息爆炸、但 知识匮乏”的挑战，数据挖掘技术应运而生，并得以蓬勃发展，越来越显示出其 强大的生命力。 从数据库中发现知识( 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 ，简称k d d f a y y a d u m 1 9 9 6 ) 是八十年代末开始的。k d d 一词是在8 9 年8 月于美国底特律市召开 的第一届k d d 国际学术会议上正式形成的。刚开始每两年召开一次国际k d d 学术 会议，9 3 年后每一年召开一次国际k d d 学术会议。这几次国际k d d 学术会议上 讨论的问题有：定性知识和定量知识的发现、数据汇总、知识发现方法、数据依 赖关系的发现和分析、发现过程中知识的应用、集成的交互式的知识发现系统、 知识发现的应用等。 1 9 9 5 年在加拿大召开了第一届知识发现和数据挖掘国际学术会议。由于把 数据库中的“数据”形象地比喻成矿床，“数据挖掘”一词快速流传开来。1 9 9 5 年以来，国外在数据挖掘方面论文已经非常多，已形成了热门研究方向。到目前 浙江大学硕士学位论文 为止，由美国人工智能协会主办的k d d 国际研讨会已经召开了1 0 次，规模由原 来的专题讨论会发展到国际学术大会，研究重点也逐渐从发现方法转向系统应 用，注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。 1 2 数据挖掘定义及特点 数据挖掘( d a t am i n i n g ) ，又称数据库中的知识发现( k d d ) ，一种较为认可的 定义是：数据挖掘就是从大型数据库的数据中提取人们感兴趣的知识 f a y y a d u 1 9 9 7 。这些知识是隐含的事先未知的，潜在的有用信息，提取的知识表示为 概念、规则、模式、规律等形式。这些有用的信息，为经营决策、市场策划、经 营预测、工业控制提供依据。通过数据挖掘，有价值的知识、规则或高层次的信 息就能从数据库的相关数据集合中抽取出来，并从不同角度显示，从而使大型数 据库作为一个丰富可靠的资源为知识归纳服务。与传统信息处理方法相比，数据 挖掘技术有其自身的特点： 1 ) 处理对象为大规模数据库，数据规模十分巨大； 2 ) 信息查询一般是由决策制定者( 用户) 提出的即时随机查询，往往没有精确 的查询要求，需要靠数据挖掘技术寻找其可能感兴趣的东西； 3 ) 在一些应用中，某些行动并没有实际发生或很少发生，因而它们对输出所 造成的影响没有在数据库中体现出来，需要利用数据挖掘技术从数据库中提取有 用的规则，为这种情况提出预测； 4 ) 在一些应用中，由于数据变化迅速可能很快过时，要求数据挖掘技术以快 速对数据变化做出反应以提供决策支持。数据挖掘既要发现潜在的规则，还要管 理和维护规则。而规则是动态的，当前的规则只能反应当前状态的数据库特征， 随着新数据的不断加入，规则需要随之更新； 5 ) 数据挖掘中规则的发现主要基于大样本的统计规律，发现的规则不必适用 于所有的数据。当达到某一阈值时便可认为有此规律。 1 3 数据挖掘方法及分类 数据挖掘技术有根据发现知识的种类分类、根据挖掘的数据库种类分类、根 据采用的技术分类等几种分类方法。根据采用的技术分类，最常用的数据挖掘技 第一章数据挖掘研究概论 术有以下几种： 1 ) 规则归纳 即通过统计方法归纳、提取有价值的i f t h e n 规则，例如关联 规则挖掘。 2 ) 人工神经网络这种方法主要是模拟人脑神经元结构，也是一种通过训练 来学习的非线性预测模型。它可以完成分类、聚类、特征规则等多种数据挖掘任 务，同时它又以m p 模型和h e b b 学习规则为基础，来建立前馈式网络、反馈式网 络、自组织网络3 类神经网络模型。这种方法用于非线性数据和含噪声的数据时 具有更大的优越性。 3 ) 决策树方法即用树形结构表示决策集合，这些决策集合是通过对数据集 的分类来产生规则。决策树方法是首先利用信息熵来寻找数据库中具有最大信息 量的字段，从而建立决策树的一个结点，再根据字段的不同取值来建立树的分支； 然后在每个分支子集中，重复建立树的下层结点和分枝，即可建立决策树。国际 上最有影响的决策树方法是i d 3 方法。其典型的应用是分类规则挖掘。 4 ) 遗传算法这是一种模拟生物进化过程的算法，最早由h o l l a n d 于2 0 世 纪7 0 年代提出 f i s h ke ，b a r n e s ，jh ，e ta l ，1 9 9 5 。它是基于群体的、具有随机和定 向搜索特征的迭代过程，这些过程有基因组合、交叉、变异和自然选择4 种典型 算子。遗传算法作用于一个由问题的多个潜在解( 个体) 组成的群体上，并且群体 中的每个个体都由一个编码表示，同时每个个体均需依据问题的目标函数而被赋 予一个适应值。另外，为了应用遗传算法，还需要把数据挖掘任务表达为一种搜 索的问题，以便发挥遗传算法的优势搜索能力。 遗传算法具有计算简单，优化效果好的特点，它在处理组和优化问题方面有 一定的优势，可用于聚类分析等。 5 ) 模糊技术即利用模糊集合理论对实际问题进行模糊评判、模糊决策、模 糊模式识别和模糊聚类分析。模糊性是客观存在的。系统的复杂性越高，精确化 能力就越低，即模糊性就越强。这是z a d e h 总结出的互克性原理。 6 ) 粗( r o u g h ) 集方法它是1 9 8 2 年由波兰逻辑学家p a w l a k 提出的一种全新 的智能决策分析工具，近年来在机器学习和k d d 等领域获得了广泛的重视和应 用，这种粗集方法是- - 3 * 研究信息系统中不确定、不精确问题的有效手段，它能 有效地分析不精确、不一致、不完整等各种不完备的信息，还可以对数据进行分 浙江大学硕1 。学位论文 析和推理从中发现隐含的知识和潜在的规律。 上述数据挖掘技术虽各有各的特点和适用范围，但它们发现知识的种类不尽 相同，其中规则归纳法一般适用于关联规则、特征规则、序列模式和离群数据的 挖掘；决策树方法、遗传算法和粗集方法一般适用于分类模式的构造；而神经网 络方法则可以用于实现分类、聚类、特征规则等多种数据挖掘；模糊技术通常被 用来挖掘模糊关联、模糊分类和模糊聚类规则。 1 4 数据挖掘技术发展趋势 数据挖掘系统已被广泛地应用于市场营销、医药业、农业、电信业、互联网、 语言识别、知识管理系统等方面。在数据挖掘研究和开发已取得令人瞩目的进展 的同时，一些尚待解决和完善的课题也摆在了研究者的面前。 1 4 1 数据挖掘技术与专家系统的结合 知识获取是建造知识库的核心问题，也是建造专家系统的“瓶颈”问题。能 否有效地获取知识是专家系统成败的关键。它是决定一个专家系统性能是否优越 的主要因素。 基于数据挖掘的专家系统，可以在根本上解决专家系统的“知识瓶颈”问题。 问题的焦点在于如何对专家的深层知识，特别是把存在于形象思维过程中的具有 潜意识的知识提取出来，这样机器才能自动获取专家知识。 在数据挖掘中尽可能地引入人对该应用领域的先验知识是非常必要的。数据 挖掘是一个人机交互、不断重复的过程。专家的领域知识或背景知识的应用对挖 掘过程具有补充和促进作用，经常用来引导发现过程以避免无意义的结果。另外， 一般数据挖掘方法仅仅在数据库内容上产生规则，规则难以理解，领域知识或背 景知识的应用可以产生易理解的规则。利用专家的领域知识的意义不仅在于约 简、表达和评估规则，更重要的是通过评估获得处理结果和应用需求之间的偏差， 并以此作为反馈，去修正以前的各个步骤。 今后的工作会沿着研究和应用两个方向继续深入：一方面，不断积累的数据 呼唤更快、更好的挖掘算法；另一方面，在进一步扩大数据挖掘的应用领域的同 时，如何更好地引入关于该应用领域的先验知识，也是值得关注的问题。 第一章数据挖掘研究概论 1 4 2 时态关联规则挖掘 由于获得的数据是随着时间变化的，因此挖掘得到的关联规则与时间有着密 切的联系。时间对事件发生的关联影响很大，在不同的时间段中，有着不同的可 信度，并且存在着较大差异。例如商品的销售数据，在不同的季节某些特殊商品 的销售情况变化很大，被同时购买的商品也会发生较大变化。 时态数据关联规则挖掘较非时间的关联规则有许多优点：数据分段挖掘，提 高了数据挖掘的效率；按时间挖掘的关联规则，提高了规则在时间方面的可信程 度；得到不同时间段的关联规则，刻画了规则的变化规律；时间的引进，更加符 合关联规则的客观性等。然而，时态关联规则仍然存在着许多值得研究的问题。 例如：如何划分时间段、如何刻画时间对关联规则的影响、如何给出有效的算法 等。 1 4 3w e b 数据挖掘 数据挖掘和w e b 应用研究是信息时代两大活跃的研究领域，两者的结合构成 了另外一个活跃的研究领域w e b 数据控制研究。w e b 数据挖掘有两方面的内 容：一个是w e b 内容的挖掘，主要是从庞大的网络数据资源里发掘信息；另一个 是w e b 使用模式数据挖掘，主要是挖掘网站访问日志，从中发掘出用户访问模式a 分析用户访问w e b 的规律可以找出优化网站组织结构的策略，也可以确定预传哪 些页面到客户端，从而提高网站的效率。 在w e b 内容的挖掘方面，b n ( 贝叶斯网络) 因其处理不确定问题的能力和良好 的因果推理机制，已成为设计w e b 数据挖掘工具的重要技术。它在在线业务的智 能处理( 识别、归类、查询、搜索) 及预测、决策过程的智能分析( 关联分析、因 果推断) 、科学研究中的知识管理等方面有广泛的应用。 b n 模型生成算法通常包括b n 结构学习及相关b n 参数学习两方面内容。但 目前常用的两类b n 生成算法中，基于记分的算法由于模型搜索空间太大而效率 低下，有时还可能得出错误的结果；基于约束的算法虽然可以改进效率，但只能 用于完整数据集。有人提出改进的思路是二者各取所长。用基于约束的算法来学 习b n 结构，而用基于记分的算法来学习给定b n 参数。二者的结合能更有效地生 浙江大学硕一l 学位论文 成b n 模型。 1 4 4 挖掘结果的可理解性 工具系统的总体发展趋势是使数据挖掘技术进一步为用户所接受和使用，也 可以理解为用用户的语言来表达知识。 数据挖掘过程中的问题定义和知识评估两个步骤，对具体应用背景的依赖更 强一些。它们可以分别看作是整个处理流程的输入和输出模块：数据预处理将无 法直接进行数据挖掘的信息转化为符合某种固定格式的、可以挖掘的数据：知识 评估则将挖掘得到的抽象的、以机器可以理解的形式表达的规则，转化为具体的、 以人可以理解的形式表达的知识。每当把数据挖掘应用到一个新的领域，改动最 大的就是这两个模块，它们也因此成为工程应用领域关注的焦点。 由于人们急切需要将存在于数据库或其他信息库中的海量数据转化为有用 的知识，因而数据挖掘技术被认为是一个新兴的、非常重要的、具有广阔应用前 景和富有挑战性的研究领域，并引起了众多学科( 如数据库、人工智能、统计学、 数据仓库、在线分析处理、专家系统、数据可视化、高性能计算机等) 研究者的 广泛注意。而作为一个新兴学科，它也是由上述众多学科相互交叉、融合而形成 的。随着数据挖掘技术的进一步发展，必然会带给用户更大的利益。 1 5 数据挖掘软件介绍及其评价 现在许多研究机构和企业开发出了一系列数据挖掘软件或者宣称其产品支 持数据挖掘，希望抢占数据挖掘软件的主导地位。i b m 公司发布了基于标准的数 据挖掘技术一i b md b 2 智能挖掘器积分服务，可用于开发出个性化的解决方案。 两大统计软件公司s a s 和s p s s 也推出了各自的数据挖掘工具e n t e r p r i s em i n e r 和c l e m e n t i n e 。而数据挖掘软件的应用也显示出了它们在具体的数据挖掘中的 有效性，例如n b a 教练就运用a d v a n c e ds c o u t 来挖掘信息，安排阵型，提高了 获胜的机率。数据挖掘软件的层出不穷也推动了数据挖掘技术的不断发展，但大 量的数据、复杂的分析、形式多样的挖掘工具也使得人们对这类软件的了解越来 越困难。 第一章数据挖掘研究概论 1 5 i 数据挖掘软件的特征 一般认为，数据挖掘就是从海量的数据中挖掘出信息，以供决策。其主要的 功能有：1 、分类；2 、聚类；3 、关联规则和序列模式发现；4 、预测；5 、偏差 的检测。数据挖掘综合运用了统计学、数据库和机器学习的方法，目前应用最广 泛的算法和模型有：1 、传统的统计学方法；2 、可视化技术；3 、决策树；4 、人 工神经网络；5 、遗传算法：6 、关联规则挖掘算法等。 从数据挖掘的定义、功能和方法等，我们可以大致了解数据挖掘软件所应具 备的特性。因此评价数据挖掘软件需要从以下几个方面考虑： 1 ) 软件开发的目的或者解决问题的领域 数据挖掘软件一般分为通用和专业数据挖掘软件，这主要由软件要解决的问 题而定，而这也是评价软件首先要考虑的因素之一。 2 ) 软件实现的功能和方法 不同的软件其具体的实现算法可能是不同的，这个也就决定了软件运行的速 度、对数据处理的有效性和正确性。同时该软件实现功能的多少也是要重点考虑 的因素。 3 ) 对数据的操作能力 数据挖掘面对的是海量的数据，这些数据可能以不同的格式，如多媒体数据， 多维数据等，还可能是不完全的，如何快速地操作这些数据也就显得非常关键。 这些数据可能以不同的形式存储在不同的介质上，一个强大的数据挖掘软件应该 支持o d b c 等连接，可以对d b 2 、i n f o r m i x 、m i c r o s o f ts q l 和o r a c l e 等数据进 行操作。 4 ) 软件使用的容易程度 软件的目的就在于应用，其操作的难易程度决定了是否可以为人接受，易于 推广。现在的一种趋势是可以提供以w e b 为基础的操作界面和允许x m l 的数据输 入输出。 5 ) 软件的运行平台等因素 软件的通用性很大程度决定于其适用的平台。理想的数据挖掘软件应该适应 客户机服务器的结构。 6 ) 软件的销售价格和服务也是必须考虑的因素 浙江大学硕士学位论文 1 5 2 数据挖掘软件功能分类 当前的数据挖掘软件已经有很多，本文尽量选择常见的软件，并根据其实现 的技术进行分类，这样可以使我们对这些软件有一个大致的了解，如表1 5 1 所 示。 表1 5 1 现有数据挖掘软件分类 实现技术软件名称 统计方法s a s e m ，c l e m e n t i n e ，d a t a e n g i n e ，p a r t e k ，m a t l a b 可视化技术s a s e m ，c l e m e n t i n e ，v i s u m i c a t i o nd a t ae x p l o r e r ， i r i s ，p a r t e k ，p v w a v e ，w i n v i z ，m i n e s e t ， a v s e x p r e s s ，n e t m a p ，c r o s s g r a p h s 决策树s a s e m ，d a w i n ，c a r t ，k n o w l e d g e s e e k e r ， k n o w l e d g e s t u d l o ，b u s i n e s sm i n e r ，s c e n a r i o ， i n t e l l i g e n tm i n e r ，d e c i s i o ns e r i e s ，m i n s e t ，a l i c e d i s o f t ，s e l e a r n ，m in s e t ，n c r 神经网络s a s e m ，c l e m e n t i n e ，4 t h o u g h t ，i n t e l l i g e n tm i n e r ， d e c i s i o ns e r i e s ，n e u r a l s i m ，d a r w i n ，d a t a e n g i n e ， d a t a s e o p e ，d b p r o p h e t ，p a r t e k ，k n o w l e 拈e s t u d i o ， s c e n a r i o ，h n c ，n c r 遗传算法p a r t e k ，a e g i sd e v e l o p m e n ts y s t e m ，o m e g a 关联规则s a s e m ，m i n e s e t ，c 1 e m e n t i n e ，s c e n a r i o ，d e c i s i o n s e r i e s ，i n t e l l i g e n tm i n e r ，n c r k 一最邻近算法s a s e m ，d a r w i n ，k n o w l e d g e s t u d i o ，i n t e l l i g e n tm i n e r 从表1 1 可以看出。目前的数据挖掘软件主要实现了统计、可视化技术、神 经网络、决策树等方法，还有其他方法有待开发。从实现的技术来看，还是s a s 、 s p s s 占主导地位，这也从另外个侧面说明了统计学是数据挖掘中的主流技术。 第一帝数据挖掘研究概论 1 5 3 常用数据挖掘软件简介 当前推出的数据挖掘软件有很多，其实现的功能方法都不同。鉴于以上软件 的评价标准，现选择介绍如下： 1 ) s a s e n t e r p r i s em i n e r s a s ( s t a t i s t i c a la n a l y s i ss y s t e m ) 是由美国北卡罗纳大学研究所开发出来 的软件包，为目前最好的统计软件之一。s a s 研究所提出数据挖掘模型 s e m m a ( s a m p l e ，e x p l o r e ，m o d i f y ，m o d e l ，a s s e s s ) ，结合s a s e m 进行数据挖掘。 由于s a s 提供了强大的统计技术，使得s a s e m 成为最好的数据挖掘软件之一。 s a s e m 可以对o r a c l e 、i n f o r m i x 、s y b a s e 和d b 2 的数据集进行操作，实现神经 网络、决策树、统计、预测、时间序列和关联等，可以运行在多种操作平台上。 2 ) s p s s c i e m e n t i n e 同s a s 一样，s p s s 是目前广泛使用的统计软件，功能强大，其一大优势是 大多数的操作可以由图形界面完成。c l e m e n t i n e 具有丰富的数据操作能力，实 现神经网络、决策树、预测、统计和关联等，可以运行在w i n d o w s 、u n i x 平台上。 3 )o r a c l e d a r w i n 以数据库技术著称的o r a c l e 公司从t h i n k i n gm a c h i n e 公司获得了d a r w i n 产品来增强其数据挖掘功能。d a r w i n 从二进制文件和通过o d b c 导入数据，实现 神经网络、k 一邻近、决策树和预测等，可以运行在w i n d o w s 和u n i x 上。 4 ) i b m i n t e l l i g e n tm i n e ri b m 公司无疑是世界上最强大的公司之一，其 数据挖掘软件i n t e l l i g e n tm i n e r 也是主流的产品之一。i n t e l l i g e n tm i n e r 提 供了基于d b 2 的数据操作能力，实现神经网络、决策树、聚类、关联和序列模式 及时间序列等，可以运行在w i n d o w s 和i b m0 s 1 2 上。 5 ) h n c d a t a b a s em i n i n gw o r k s t a t i o n h n c 是最成功的数据挖掘公司之一。它的d a t a b a s em i n i n gw o r k s t a t i o n ( d m w ) 是一个在信用卡欺诈分析方面被广泛接受的神经元网络工具。d m w 是基于 w i n d o w s 的应用软件和一个自定义处理模板组成。 6 ) a n g o s s ss o f t w a r ec o r p o r a t i o n k n o w l e d g e s e e k e r a n g o s s ss o f t w a r e 的k n o w l e d g e s e e k e r 是一个决策树数据挖掘工具，技术 比较成熟，提供了图形的操作界面，易于操作。 9 浙江大学硕j 学位论文 1 6 本文主要内容 全文由以下五章组成： 第一章为绪论，阐述了数据挖掘研究内容，特别对数据挖掘技术的发展和现 状进行了完整的综述。 第二章介绍了关联规则挖掘技术的基础，阐述了关联规则挖掘发展状况及其 基本概念。 第三章提出了一种基于自适应支持度的布尔式关联规则挖掘算法，算法无需 由外部指定最小支持度，在挖掘过程中算法将根据用户需要的规则数范围自动调 节最小支持度以产生特定数目的规则，算法针对用户需要的规则数来产生规则， 在一定程度上减少了挖掘时间，避免了人为指定最小支持度的盲目性。此外，算 法核心采用高效的布尔式挖掘方法，采用逻辑o r 、a n d 和x o r 操作来产生关 联规则，避免了在挖掘过程中产生候选项集，并且只需要对数据库进行一次扫描， 使算法具有一定的高效性。 第四章探讨了基于自适应支持度的布尔式关联规则挖掘算法在流程工业中 的应用问题，并以某农药厂三唑磷合成过程为实例，阐述了关联规则挖掘算法在 流程工业中进行实际应用的方案。三组仿真过程分别选择了不同的初始工艺操作 参数和配方，并且选择了历史数据表中苯唑醇收率的平均值作为在初始工艺操作 参数和配方的条件下拟定的苯唑醇收率。从三组仿真挖掘结果可以看出，在三唑 磷生产过程历史数据基础上利用关联规则挖掘方法能够有效地挖掘出提高苯唑 醇收率的优化建议。对于三唑磷生产过程中其他参数的优化建议，均可以利用类 似的方法来获得，此方法具有较强的通用性。 第五章针对复杂工业大系统的特点，提出了一种基于关联规则的故障诊断方 法。对尿素生产过程的仿真实验结果表明，该方法能够有效地挖掘隐藏在大量数 据背后的故障模式知识，有效的突破了故障诊断专家系统在知识获取方面的瓶 颈。增强了故障诊断系统的推理诊断能力。 第六章总结全文并讨论了进一步需要研究的问题。 第二章关联规则挖掘基础 摘要 本章介绍了关联规则挖掘的基本概念、关联规则挖掘技术发展状况、a p r i o r i 及其几种 改进算法原理。 关键词：关联规则置信度支持度 2 1 引言 在数据挖掘领域，采用关联规则在大型数据库中进行数据挖掘是一个重要的 研究内容。关联规则是美国i b ma l m a d e nr e s e a r c hc e n t e r 的r a b e s ha g r a w a l 等人于1 9 9 3 年首先提出的k d d 研究中的一个重要课题 r a g r a w a l 1 9 9 3 。关联规 则挖掘的一般对象是事务数据库，这种数据库的主要应用在零售业，比如超级市 场的销售管理。关联规则挖掘就是发现事务数据库中不同商品( 项) ( i t e m ，指事 务中的内容，比如，面包、牛奶等都是项目) 之间是否存在某种关联关系。通过 这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。发 现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用户进行 分类。 譬如在商场中，许多决策只停留在管理人员的经验判断层次上，缺乏深层次 的分析，也往往跟不上客观环境的变化，所以就需要对客观实时数据进行分析， 找到它们的内在联系，从而获得有关指导商家进货，方便顾客购物等一些有价值 的知识。关联规则的一个典型例子是购物篮分析。该过程通过发现顾客放入其购 物篮中不同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被 顾客同时购买，这种关联的发现可以帮助超市经营者制定营销策略。例如，在同 一次去商场超级市场，如果顾客购买牛奶，同时也购买面包的可能性有多大? 使 用关联规则通过对过去销售数据的分析，可以帮助超市经营者有选择地经销和安 排货架，这种信息可以引导销售。如将牛奶和面包尽可能放近一些，这样就方便 了顾客的购买，同时也可以进一步刺激一次去超市同时购买这些商品。另一个比 较典型的案例是“尿布与啤酒”的故事。在美国，一些年轻的父亲下班后经常到 超市去买婴儿尿布，超市经过对顾客的购物信息进行挖掘，发现一条非常有用的 规则：在购买婴儿尿布的年轻父亲们中，有3 0 - - 4 0 的人同时要买一些啤酒。 l l 浙江大学硕士学位论文 超市随后调整了货架的摆放，把尿布和啤酒放在一起。结果提高了商场的效益。 因此，找出这样的数据信息对于确定市场策略是很有价值的。寻找这种信息的过 程即是挖掘关联规则的过程。关联规则还可以应用到附加邮递、目录设计、追加 销售、仓储规划以及基于购买模式对顾客进行划分等方面。 2 2 关联规则挖掘基本概念 2 2 1 基本描述 关联规则的挖掘问题可形式化描述如下 r h g r a w a l ，e ta 1 1 9 9 3 ： 设i = i 、，iz ，i 。 是由i n 个不同的项目组成的集合。给定一个事务数据库d ， 其中的每一个事务t 是i 中一组项目的集合，即r ，t 有一个唯一的标识符 t i d 。若项集x ，且x r ，则事务包含项集x 。 一条关联规则就是形如x j y 的蕴涵式，其中z ，y ，x n 】，= o 。 关联规则xjy 成立的条件是：它具有支持度s 。即事务数据库d 中至少有s 的事务包含xuj ，它具有置信度c 。即在事务数据库d 中包x 的事务至少有 c 同时也包含y 。 关联规则的挖掘问题就是在事务数据库d 中找出具有用户给定的最小支持 度m i n s u p 和最小置信度m i n c o n f 的关联规则。 挖掘关联规则问题可以分解为以下两个子问题： 1 、找出存在于事务数据库中的所有大项集。项集x 的支持度s u p p o r t ( x ) 不 小于用户给定的最小支持度m i n s u p ，则称x 为大项集( 1 a r g ei t e m s e t ) 。 2 、利用大项集生成关联规则。对于每个大项集a ，若b c a ，b 巾，且 s u p p o r t ( a ) s u p p o r t ( b ) m i n c o n f ，则有关联规则b j ( a - b ) 。 第2 个子问题比较简单，目前大多数研究集中在第一个子问题上。 2 2 2 关联规则挖掘的一般步骤 r a g r a w a l 等人首先提出了关联规则的挖掘问题并给出解决此问题最原始的 算法h i s 之后，该问题得到了国际人工智能和数据库等领域学者的密切关注，提 第二章关联规则挖掘基础 出了多种的算法。所有的挖掘算法不论它是采用什么数据结构，其复杂程度、效 率如何，它们都可以分为如下几个步骤： 1 ) 预处理与采掘任务有关的数据。根据具体问题的要求对数据库进行相应 的操作，从而构成规格化的数据库d 。 2 ) 针对d ，求出所有满足最小支持度的项集，即大项集。由于一般情况下 我们所面临的数据库都比较大，所以此步是算法的核心。 3 ) 生成满足最小置信度的规则，形成规则集r 。 4 ) 解释并输出r 。 2 3 关联规则挖掘主要研究方向 r a g r a w a l 等人提出了关联规则的挖掘问题之后，该问题的研究得到了长足 的发展。到目前为止，其主要的研究方向有： 1 ) 多循环方式的采掘算法 此类算法包括a g r a w a l 等人提出的a i s r a g r a w a l ，e ta 1 1 9 9 3 、a p r i o r i 、 a p r i o r i t i d 和a p r i o r i h y b r i d r a g r a w a l r s f i k a n t 1 9 9 4 ，p a r k 等人提出的 d h p j s p a r k ，e ta 1 1 9 9 7 ，s a v a s e r e 等人的p a r t i t i o n a s a v a s e r e ，e o m i e c i n s k i a n d s n a v a t h e 1 9 9 5 以及t o i v o n e n 提出的抽样算法s a m p l i n g h a n n u t o i v o n e n 1 9 9 6 等等。其中最有效和有影响的算法为：a p r o r i ，d h p 和p a r t i t i o n 。 2 ) 增量式更新算法 关联规则的增量式更新问题主要有两个： a 、在给定的最小支持度和最小置信度下，当一个新的事物数据集d b 添加到 旧的事物数据库d b 中时，如何生成u d b 中的关联规则； b 、给定事物数据库d b ，在最小支持度和最小置信度发生变化时，如