（计算机应用技术专业论文）基于遗传算法的关联规则数据挖掘的应用研究.pdf

中文摘要 近几十年来，数据库技术和海量存储器等硬件的快速发展使得人们收集数据 的能力得到进一步的提高。面对信息时代海量数据的出现，如何有效地利用巨量 的原始数据分析现状以预测未来，已经成为人类面临的一大挑战。由此，数据挖 掘技术应运而生并得以迅猛发展。目前，数据挖掘已经成为一个研究热点。数据 挖掘所得到的知识能够为决策支持提供依据。 关联规则是数据挖掘的重要模式之一，有着极其重要的应用价值。本文根据 关联规则挖掘的要求与特点，结合遗传算法的思想，提出了一个基于遗传算法的 关联规则挖掘方法，并通过实例分析，说明是一种具有实用价值的方法。文中主 要在以下几方面做了深入的研究： 深入地分析与研究了数据挖掘技术及关联规则。对关联规则的衡量标准 作了系统的研究，针对基于支持度和置信度框架模型的局限性，引入了 基于差异的兴趣度，用来修剪无趣的规则，从而筛选出用户真正感兴趣 的规则模式。 全面分析了数据挖掘中的一个重要算法遗传算法。在此基础上，提 出一种基于遗传算法的关联规则挖掘算法，从编码方法、适应度函数的 构造、交叉算子和变异算子的设计等方面进行了详细的讨论和分析。 结合一所院校的教师测评系统，给出了用遗传算法进行关联规则挖掘的 实例，实现了数据挖掘在教育领域的应用。 关键词：数据挖掘关联规则兴趣度遗传算法 a b s t r a c t i nt h el a s td e c a d e s , t h ed a m b a s et e c h n o l o g i e sa n dm a g n a n i m i t ym e m o r y t e c h n o l o g i e sh a v ed e v e l o p e dm u c h a ti n f o r m a t i o na g e , o r i e n t e dt oag r e a td e a lo f d a t a , h o wt ou t i l i z et h eh u g eo r i g i n a ld a t at oa n a l y s i st h ec u r r e n ts i t u a t i o na n dp r e d i c t t h ef u t u r ee f f e c t i v e l y ，h a v ea l r e a d yb e c o m eag r e a tc h a l l e n g et h a tt h em a n k i n dh a s f a c e d t h e r e f o r et h ed a t am i n i n gt e c h n o l o g yi sa r i s e da tt h eh i s t o r i cm o m e n ta n dc a n b ed e v e l o p e dr a p i d l y r e c e n t l y ，d a t am i n i n gh a sb e e no n eo fh o tr e s e a r c ha r e a t h e k n o w l e d g ed i s c o v e r e db yd a t am i n i n gt e c h n o l o g i e sc a l l b eu s e dt oo f f e rd e c i s i o n s u p p o r t a s s o c i a t i o nr u l ei so n eo ft h ei m p o r t a n tm o d e l so fd a t am i n i n g ，a n dh a st h em o s t s i g n i f i c a n ta p p l i c a t i o nv a l u e a c c o r d i n gt ot h er e q u i r e m e n ta n dt h e c h a r a c t e ro f a s s o c i a t i o nr u l em i n i n g ，c o m b i n et h ei d e ao fg e n e t i ca l g o r i t h m ，am i n i n gm e t h o do f a s s o c i a t i o nr u l e si sp r o p o s e db a s e do ng e n e t i ca l g o r i t h m a c c o r d i n gt ot h ea n a l y s i so f e x a m p l e ，i ti sap r a c t i c a la l g o r i t h m t h ef o l l o w i n gt h e m e sa r ea d d r e s s e di nt h i sp a p e r ： d e e p l ya n a l y z i n ga n ds t u d y i n gd a t am i n i n gt e c h n o l o g ya n da s s o c i a t i o nr u l e i nt h i sp a p e r ，w eh a v eas y s t e m a t i cr e s e a r c hi n t ot h em e a s u r es t a n d a r df o r a s s o c i a t i o nr u l e s s t u d i e dt h el i m i t a t i o ni nm o d e lb a s e do ns u p p o r ta n d c o n f i d e n c em e a s u r e ，t h ed e v i a t i o n - b a s e di n t e r e s ti sg i v e ni nt h i sd i s s e r t a t i o n ， w h i c hi su s e dt op r u n et h en o i n t e r e s tr u l e si no r d e rt od i s c o v e rt h el e a l i n t e r e s tr u l e sm o d e a n a l y z i n ga ni m p o r t a n tm e t h o d _ - g e n e t i ca l g o r i t h m si nd a t am i n i n g o nt h i s b a s i s ，t h i sp a p e rb r i n g sf o r w a r dam i n i n gm e t h o do fa s s o c i a t i o nr u l e sb a s e d o ng e n e t i ca l g o r i t h m ，d i s c u s s e sa n da n a l y s e st h eg e n e t i ca l g o r i t h m si nd e t a i l f r o mc o d i n gm e t h o d ，f i m e s sf u n c t i o n ，c r o s s o v e ro p e r a t o r s ，s e l e c t i o n o p e r a t o r s ，m u t a t i o no p e r a t o r sa n do t h e ra s p e c t s a s s o c i a t e dw i t ht h et e a c h e re v a l u a t i o ns y s t e m t h i s p a p e rg i v e s t h e a l g o r i t h m sa n dp r o g r a mo fm i n i n g a s s o c i a t i o nr u l eb a s e do ng e n e t i c a l g o r i t h m sa n da p p l i c a t i o ni nt h ef i l e d so f e d u c a t i o n k e yw 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 ，i n t e r e s tm e a s u r e ，g e n e t i c a l g o r i t h m s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨洼盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：碑尊暑 签字日期： 由4 年7 月 日 学位论文版权使用授权书 本学位论文作者完全了解墨盗盘堂 有关保留、使用学位论文的规定。 特授权苤鲞盘茎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 导师签名： 旋，召 签字日期：，髟年7 月 日 帚万錾哥 月 菝叶， 缸 侔 糍 扪 作 ： 文 期 沦 日 位 字 学 签 天津大学硕士学位论文 第一章绪论 1 1 选题背景与意义 第一章绪论 1 1 1 数据挖掘技术的产生及研究现状 近年来随着数据库技术和计算机网络的广泛应用，加上使用先进的自动数 据生成和采集工具，人们所拥有的数据量急剧增大。激增的数据背后隐藏着许多 重要的信息，如何从大量的数据中提取并找到有用的信息以指导决策，是迫切需 要解决的问题。在这种情况下，数据挖掘i l l 新型的数据分析技术于1 9 9 5 年 诞生了。 数据挖掘( d a t am i n i n g ) 是从一个新的角度将数据库技术、机器学习、统 计学等领域结合起来，从更深层次发掘存在于数据内部的、有效的、新颖的、具 有潜在效应的乃至最终可理解的模式【2 】。数据挖掘能预测未来趋势和行为，使商 务活动具有前瞻性，有助于企业做出基于知识驱动的决策。数据挖掘所提供的自 动预期分析，已经远远超出了由典型的决策支持系统工具对过去实践所做的回顾 性分析范围。数据挖掘可以解决传统上需花费很多时间解决的商务问题，它能搜 索整个数据库并查找隐藏的模式，找出那些专家可能错过的预测信尉“。 回顾数据挖掘的发展，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 y i nd a t a b a s e ) 技术；1 9 9 1 、1 9 9 3 、1 9 9 4 年又相继举行了k d d 的专题讨论会；1 9 9 5 年，在美国计算机年会( a c m ) 上，提出了数据挖掘( d a t a m i n i n g ) 的概念。 十年来，数据挖掘的研究工作取得了很大的进展，各种数据挖掘软件的应 用也极大地推动了人们掌握和处理信息的能力，并为人们带来了很好的经济效 益。数据挖掘应用的普遍性及由此带来的高效益，也使其成为一个具有广阔应用 前景的热门研究方向，并吸引了各个领域的专家和研究机构来从事该领域的研 究，许多公司也纷纷推出了自己的数据挖掘系统。 我国的数据挖掘研究开始于9 0 年代中期，到9 q 年代后期，初步形成了知 识发现和数据挖掘的基本框架。1 9 9 3 年国家自然科学基金首次支持对该领域的 研究项目。在9 0 年代中期一批研究成果( 学术论文) 陆续发表在计算机学报、 计算机研究与发展、软件学报、人工智能与模式识别等刊物上，研 究的重点也正在从发现方法转向系统应用，并且注重多种发现策略的技术集成和 天津大学硕士学位论文第一章绪论 多学科之间的相互渗透。研究的内容不仅有学术研究，而且实际应用研究也在不 断加强。比如，中国数据挖掘与商业智能研讨会到今年四月份为止，已经举办了 两届。 目前，国内许多的科研单位和高等院校相继开展了知识发现的基础理论及 其应用研究，如清华大学、中科院计算机技术研究所、空军第三研究所、海军装 备论证中心、中国人民大学等。其中，北京系统工程研究所对模糊方法在知识发 现中的应用进行了较深入的研究：北京大学也在开展对数据立方体代数的研究； 华中理工大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林 大学等单位开展了对关联规则挖掘算法的优化和改造；南京大学、四川联合大学 和上海交通大学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖 掘。但与国外相比，国内的d m k d 的研究稍晚，还没有形成整体力量。 1 1 2 数据挖掘中的关联规则 关联规则的提取是数据挖掘技术研究的一个重要课题。由于符合人类认知 世界的思维模式，关联规则的提取广泛应用于商业、保险等行业。在实际的大型 数据库( 如超级市场的交易事务数据库) 中发现了如“购买物品a 和b 的客户中 8 5 同时也购买c 和d ”这样的规则，对于分类设计、商店布局、市场分析等方 面都大有帮助。 目前关联规则的挖掘研究大都以这种商用事务数据库为主要对象，其属性域 局限于布尔类型，因而也称为布尔相关问题。而普通关系数据库中属性类型较为 丰富，它可以包含数量属性( 如年龄、工资等) 和类别属性( 如性别、教育程度 等) ，布尔类型可以看成是类别属性的一个特例。如何发现普通数据库中各属性 之间的关联，也称为数量相关问题，具有更为普遍的意义，目前该方面的研究工 作开始增多。本文的关联规则挖掘就是关于数值关联规则的挖掘。 1 1 3 遗传算法与数据挖掘 遗传算法是数据挖掘的主要算法之一。遗传算法作为一种有效的全面并行 优化搜索工具，早被众多应用领域所接受，在数据挖掘方面的应用也得到了极高 的重视。遗传算法应用于决策树、分类器、模糊规则获取等方面的文献不断涌现， 是数据挖掘领域的一个重要研究课题1 4 j 。 遗传算法以其解决问题的混沌、随机和非线性为典型特征，它为其它科学 技术无法解决或难以解决的复杂问题提供了新的计算模型。对于数据嘈杂无序的 特征，遗传算法是有效解决此类问题的方法之_ 1 5 1 。 许多知识发现的问题可以看成是搜索问题，数据库可以看作是搜索空间，发 天津大学硕士学位论文第一章绪论 现算法可以看作是搜索策略，而遗传算法是模拟自然进化的全局搜索算法。应用 遗传算法在数据库中进行搜索，对随机产生的一组规则进行进化，直到数据库能 够被该组规则覆盖，从而挖掘出隐含在数据库中的规则。遗传算法避免了搜索过 程中的局部最优解，用在规则发现方面有希望发现真正有用的规则。 1 1 4 数据挖掘技术在教育领域的应用 数据挖掘技术已经在许多领域取得了很好的应用。目前，数据挖掘技术在教 育方面的应用还处于起步阶段。早期使用s a s 编程对教育信息进行简单的统计分 析，即教育测量学。2 0 0 4 年1 0 月在美国拉斯维加斯召开的d a t am i n i n gt e c h n o l o g y c o n f e r e n c e 会议首次将d a t am i n i n gi ne d u c a t i o n 纳入议题。 在教育领域，随着数据量的不断增长，如何利用海量数据可靠、灵活地指导 教学活动、保证教学质量，成为各高校面临的一大挑战。把数据挖掘技术应用到 教学系统中，可以解决以前教学系统中存在的问题，如总是凭借自己的经验或者 学习别人的经验来进行教学管理，因而产生管理滞后等问题。数据挖掘工具能够 较客观地实时反映教学系统中存在的问题，为决策提供重要依据。这一研究也对 实际的教学管理提出了很好的建议，给多年来的计算机教学管理工作增添了新的 内容。 1 2 研究目标及主要内容 本文的研究工作主要源于上述背景。将遗传算法应用于数据挖掘中关联规 则的提取。并结合教师测评系统，将数据挖掘技术引入教育领域，实现了基于遗 传算法的关联规则数据挖掘的应用实现。 本文的主要研究内容有： 数据挖掘技术的分析研究 在数据挖掘相关概念基础上，对数据挖掘的目的与功能、分析方法、挖掘 过程与工具、挖掘方法与技术做了详细的归纳和总结。同时，对数据挖掘的发展 和应用状况也进行了客观的分析。 关联规则的分析研究 全面研究了关联规则的相关知识，对其核心算法一a p r i o r i 算法进行了分析； 在对关联规则的价值衡量标准进行研究的基础上，重点探讨了本文应用实例中使 用到的有关兴趣度的内容。 遗传算法的分析研究 介绍了遗传算法的基本概念和基本思想，分析了遗传算法中染色体编码方 天津大学硕士学位论文第一章绪论 案、适应度函数构造及遗传算子的设计和改进方法，同时对遗传算法的应用流程 和算法也做了分析研究。 基于遗传算法的关联规则挖掘的应用研究 通过对数据挖掘、关联规则和遗传算法的分析研究，提出一种基于遗传算法 的关联规则数据挖掘模型，并将其应用于教育领域中的教师测评系统，给出了该 应用的实现技术和算法。通过实验证明了算法的有效性和可行性，实验效果良好。 1 3 本文结构 本文共分六章，内容概要如下： 第一章是绪论，介绍了课题研究的背景与课题研究的内容及目标。 第二章是数据挖掘技术的综述，分别从数据挖掘的定义、分类，数据挖掘的 分析方法和挖掘方法以及数据挖掘的过程与工具等几方面进行了重点介绍。 第三章深入研究和探讨关联规则的基本理论，重点研究了关联规则的衡量标 准，探讨了兴趣度的相关知识，为后面基于遗传算法关联规则数据挖掘的应用做 了准备。 第四章介绍了遗传算法的原理与方法，重点研究了染色体编码、适应度函数 构造及遗传算子的设计，并对遗传算法的应用流程及算法作了介绍。 第五章将遗传算法应用于数据挖掘中关联规则的挖掘中，并与一所高职学院 的教师测评系统相结合，通过实验验证了该算法的有效性和可行性。 第六章是小结与展望，首先对课题工作做了总结，然后对本课题的下一步研 究提出了一些初步想法。 天津大学硕士学位论文第二章数据挖掘技术概述 第二章数据挖掘技术概述 数据库技术的迅速发展及数据库管理系统的广泛应用，使得人们积累的数 据越来越多。激增的数据背后隐藏着许多重要信息，人们希望能够对其进行更高 层次的分析，发现数据中存在的关系和规则，根据现有的数据预测未来的发展趋 势。数据挖掘( d a t a m i n i n g ) 技术的出现，为解决上述问题提供了较好的方案【6 7 1 。 2 1 数据挖掘的定义 数据挖掘，英文是d a t am i n i n g ，中文译作数据挖掘或数据采掘。一种比较 公认的定义是：数据挖掘是指从大量的、不完全的、有噪声的、模糊的、随机的 实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信 息和知识的过程m j 。 理解数据挖掘的定义需要从技术和应用两个层面进行。从技术层面上看， 数据挖掘是利用多种分析工具从海量数据中发现模型和数据间关系的过程，其基 于机器学习、统计学、神经网络、数据库系统和信息科学等技术。从应用层面上 看，数据挖掘是一个决策过程，基于多种技术，分析企业商务数据，为企业做出 正确的市场预测等提供支持。 作为一个学术领域，数据挖掘和数据库知识发现k d d ( k n o w l e d g ed i s c o v e r y i nd a t a b a s e s ) 具有很大的重合度，大部分学者认为数据挖掘和知识发现是等价的 概念，也有学者认为数据挖掘是知识发现的一个特定步骤。我们倾向于前一种观 点，数据挖掘的一般过程如图2 1 所示。 知识 模式 图2 - 1 数据挖掘的一般过程 天津大学硕士学位论文第二章数据挖掘技术概述 数据挖掘技术可以帮助用户获得决策所需的多种知识。在许多情况下，用 户并不知道数据存在哪些有价值的信息。因此，对于一个数据挖掘系统而言，它 应该能够同时搜索发现多种模式的知识，以满足用户的期望和实际需要。此外， 数据挖掘系统还应该能够挖掘多种层次( 抽象水平) 的模式知识，并且允许用户 来指导挖掘有价值的模式知识。 2 2 数据挖掘的分析方法【9 1 数据挖掘的目的是发现有意义的知识以便为决策支持等具体业务提供帮 助。数据挖掘的分析方法一般包括以下几种： ( 1 ) 关联分析 关联分析的目的是发现数据集中所隐含的若干项目之间的相互关系【10 ，l l 】。 比如，超市记录了每次交易的商品清单，通过对顾客购物行为进行关联分析，从 而可以获取各个商品在销售上的关联程度。关联分析往往以关联规则的形式表 达，并以支持度、置信度等参数来描述关联规则。 ( 2 ) 数据分类 数据分类是发现数据集中各个对象的一般特征，并按照不同的分类模型将 这些对象划分成不同的类”川4 】。对数据进行分类时，假定数据集中的每个对象事 先已知属于某一个类，而分类则是生成这些类的描述。因此，分类分析需要事先 对每个对象加上标记以区分出所属的类。数据分类方法指的是或者导出区分所有 类的规则集合，或者仅仅获得某一个类区别于其它类的区分规则集合，这两者的 侧重点是不同的。 ( 3 ) 聚类分析 聚类是一个过程，它将数据集中的对象进行分组，生成相似对象的类p s , i 6 1 。 聚类分析是无导师的学习过程。聚类分析目的是将大量数据的对象集合分成若干 个有意义的类，使得每个类的内部对象具有较高的相似程度，而不同类的对象之 间具有较小的相似程度。 ( 4 ) 序列模式分析 序列模式分析侧重于分析数据之间的前后因果关系i 7 ，。比如对于超市， 序列模式分析可用于发现顾客购物模式的次序，如先购买商品x ，再购买商品y 。 对于股票市场，序列模式分析可用于发现股票价格变化的先后关系，如股票a 上 涨一定幅度后，股票b 也将上涨一定幅度。可见，序列模式分析与关联分析不同， 关联分析仅考虑数据间的联系，而并不关心先后顺序。 在实际的决策支持等具体业务过程中，则往往需要综合应用上面的各种数据 天津大学硕士学位论文第二章数据挖掘技术概述 挖掘的分析方法，以便获得更好的效果。 2 3 数据挖掘的方法与技术 数据挖掘的方法包括统计分析方法和人工智能方法。实际中，数据挖掘往 往需要综合利用这些方法，并且需要可视化技术等加以辅助。 数据挖掘经常用到的方法和技术包括以下几种： ( 1 ) 关联规则挖掘技术 关联规则挖掘的目的是发现数据之间的关联特性。a p d o r i 和d h p 是关联规 则的经典算法。在许多应用中，往往希望发现数据之上较高层次的关联性，因此 也出现了泛化的和多层次的关联规则挖掘方法。关联规则挖掘技术是比较成熟的 数据挖掘技术，主要应用于数据挖掘中的关联分析。 ( 2 ) 人工神经网络 人工神经网络方法模拟人脑的神经元结构，以m p 模型和h e b b 学习规则为 基础。神经网络主要有三种模型：前馈式网络、反馈式网络、自组织网络。人工 神经网络是典型的机器学习方法，广泛应用于预测、模式识别、优化计算等领域， 也可用于数据挖掘中的聚类分析。 ( 3 ) 决策树方法 决策树方法在机器学习领域曾经得到广泛而深入的研究。最早的决策树算 法是q u i n l a n 提出的i d 3 算法。决策树方法以数据集中各字段的信息增益为依据， 以信息增益最大的字段作为决策树的根结点，并依次对各个子树进行类似的操 作，直到确定决策树的所有结点。在i d 3 算法提出以后，又出现了许多改进的算 法，如i d 4 ，i d 5 ，c 4 5 等。决策树可用于数据挖掘中的数据分类。 ( 4 ) 基于模式的相似搜索技术 基于模式的相似搜索技术主要用于从时态数据库或空间时态数据库中搜索 相似的模式。这类技术需要事先定义相似的测度，一般可用欧拉距离和相关性来 衡量模式的相似程度。 ( 5 ) 遗传算法 遗传算法是模拟生物进化过程的算法。它先将搜索结构编码为染色体，然 后分别通过选择、交叉、变异三个基本遗传算子对其进行循环操作，使所要解决 的问题从随机初始解一步步地逼近最优解，以达到进化的目的。遗传算法主要用 在优化计算、机器学习等领域。 此外，数据挖掘技术还包括粗糙集方法、模糊逻辑、邻近搜索方法、贝叶斯 网络和规则推理等等。 天津大学硕士学位论文第二章数据挖掘技术概述 2 4 数据挖掘的过程与工具 2 4 1 数据挖掘过程 数据挖掘的过程大体可以分为三步：数据准备( d a t ap r e p a r a t i o n ) 、数据挖 掘( d a mm i n i n g ) 和结果的解释与评估( i n t e r p r e t a t i o na n de v a l u m i o n ) 。 ( 1 ) 数据准备 数据准备又可分为三个子步骤：数据选取( d a t as e l e c t i o n ) 、数据预处理 ( d a t ap r e p r o c e s s i n g ) 和数据变换( d a t at r a n s f o r m a t i o n ) 。 数据选取的目的是搜索所有与业务对象有关的数据信息，并从中选择出适 合于数据挖掘应用的数据。 数据预处理一般包括消除噪声、推导计算缺值数据、消除重复记录、完成 数据类型的转换等。当数据挖掘的对象是数据仓库时，一般来讲，数据预处理 已经在生成数据仓库时完成了。 数据变换的主要目的是降维，即从初始特征中找出真正有用的特征以减少 数据挖掘时要考虑的特征或变量数。 ( 2 ) 数据挖掘阶段 数据挖掘阶段首要任务是确定挖掘的任务或目的。清晰地定义出业务问题， 认清数据挖掘的目的是数据挖掘的重要一步。然后，决定使用什么样的挖掘算法。 选择实现算法有两个考虑因素：一是不同的数据有不同的特点，因此需要用与之 相关的算法来挖掘；二是用户或实际运行系统的要求，有的用户可能希望获取描 述型的、容易理解的知识，而有的用户或系统的目的是获取预测准确度尽可能高 的预测型知识。 ( 3 ) 结果解释和评价 数据挖掘阶段挖掘出来的模式，经过用户或机器的评价，可能存在冗余或无 关的模式，这时需要将其剔除；也可能模式不能满足用户要求，这时整个挖掘过 程需要重新选取数据、采用新的数据变换方法、设定新的挖掘参数，甚至采用其 它的挖掘算法。因此，数据挖掘是一个反复迭代的过程。 2 4 2 数据挖掘工具 目前，国外有许多研究机构、公司和学术组织从事数据挖掘系统的原型与 产品的研制和开发。这些系统和工具除了采用了传统的统计方法外，还采用基于 人工智能的技术，包括决策树、规则归纳、神经元网络、可视化、模糊建模等。 这些工具在挖掘功能和方法上差别很大，不仅体现在关键技术上，还体现在运行 天津大学硕士学位论文第二章数据挖掘技术概述 平台上。目前数据挖掘工具主要分为两类：特定领域的数据挖掘工具和通用的数 据挖掘工具。 ( 1 ) 特定领域的数据挖掘工具 特定领域的数据挖掘工具是针对某些特定领域的问题提供解决方案。在设 计算法时，充分考虑到数据需求的特殊性，作了优化。目前，特定领域的数据挖 掘工具主要有以下几种： k d i ：零售业； o p t i o n s & c h o i c e s ：保险业； h n c ：欺诈行为探察； u n i c a m o d e l1 ：市场； ( 2 ) 通用的数据挖掘工具 通用数据挖掘工具不区分具体的数据含义，采用通用的挖掘算法，面向非 特定应用。通用的数据挖掘工具可以做多种模式的挖掘，挖掘什么、用什么挖掘 由用户自己来选择。主要工具有以下几种： s a se n t e r p r i s em i n e r ： i b mi n t e l i g e n tm i n e r ； u n i c ap r w ： s p s sc l e m e n t i n e ： s g im i n e s e t ： o r a c l ed a r w i n ； a n g o s sk n o w l e d g es e e k e r ； 现在许多行业，诸如通信、信用卡公司、股票交易所、保险公司、商业企业 等都用数据挖掘工具来协助其进行业务活动。我国在这方面的应用还处于起步阶 段，因此有着巨大的潜力。 2 5 数据挖掘的发展及应用状况 一份最近的g a m t e r 报告列举了在今后几年将产生重要影响的五项关键技 术，其中数据挖掘和人工智能排名第一。同时，这份报告将并行计算体系结构研 究和数据挖掘列入了今后五年公司应该投资的十个新技术领域之首。 对于数据挖掘技术的研究，在国外已经有了好几年的历史。目前在国外， 数据挖掘技术及其相关的决策支持系统的发展很快，已经给商业界、公共服务行 业带来了令人吃惊的利润。很多的学校和科研机构也正在注入大量的资金进行数 据挖掘的进一步开发应用和更深入的研究。 天津大学硕士学位论文 第二章数据挖掘技术概述 虽然数据挖掘技术的研究还不很成熟，其应用也有较大的局限性，但是， 也正是由于这些局限性的存在，才促使数据挖掘研究可以进一步发展。 目前，数据挖掘研究和应用主要面l 临以下问题： ( 1 ) 挖掘的对象：更大型的数据库、更高的维、更多属性之间的复杂关系。 数据挖掘处理的数据量是十分巨大的。成千上万的数据表、上百万条的记录、数 据库容量达到了g b 元组。更多的属性意味着更多的搜索空间，因而将会导致信 息爆炸，而属性问的关系会变得更加复杂。这些因素都会使搜索知识的代价极高。 ( 2 ) 输入数据的多种形式：目前数据挖掘工具可以处理的数据形式有限。 一般可以处理关系型的结构数据，但对文本、图形、数学公式、图像或w w w 资源等半结构、无结构的数据形式进行挖掘操作仍存在着局限性。 ( 3 ) 用户参与和领域知识：有效的决策过程往往需要多次的交互与多次的 反复。目前的数据挖掘系统或工具很少能真正做到让用户参与到挖掘过程中来， 而且将相关领域的知识应用于数据挖掘系统也没有得到很好的解决。 ( 4 ) 证实( v a l i d a t i o n ) 技术的局限：数据挖掘使用特定的分析方法或逻辑 形式发现知识，比如归纳或演绎。但系统没有能力去交互验证( c r o s s v a l i d a t i o n ) 发现的知识，使得发现的知识没有普适性而不能成为有用的知识。 ( 5 ) 知识的表达和解释机制：用户要求发现的知识不仅局限于数字或符号， 更需要容易理解的方式，如图形、自然语言和可视化等。只有当数据挖掘系统能 提供更好的解释机制，用户才能更有效地评价这些知识，区分出哪些是真正有用 的知识。 ( 6 ) 知识的维护和更新：知识需要动态维护和及时更新，目前主要采用增 量更新的方法来维护已有的知识，比如d w c h c u n g 等提出了维护关联规则的增 量算法。 ( 7 ) 支持的局限性及与其他系统的集成：目前的数据挖掘系统尚不能支持 多个平台，有些基于p c ，有些面向大型机，还有一些面向客户机服务器环境。 此外，数据挖掘系统面临和其他决策支持系统的有机集成，特别是与一些用户已 经熟悉的系统结合在一起，这对系统充分发挥作用是非常重要的。 天津大学硕士学位论文第三章关联规则研究 第三章关联规则研究 在数据挖掘的知识模式中，关联规则模式是比较重要、也是最活跃的一个 分支。关联规则挖掘能发现大量数据中项集之间有趣的关联。随着大量数据的收 集和存储，许多业界人士对于数据库中挖掘关联规则越来越感兴趣。近年来，关 联规则的挖掘已成为数据挖掘领域中的一个非常重要的研究课题。 3 1 关联规则的引入 关联规则挖掘的一个典型例子是购物篮分析。条形码技术的发展使零售机 构能够收集和存储大量的销售记录，这些销售记录称为篮子数据( b a s k e td a t a ) ， 记录顾客在一次购物中购买的商品信息的篮子数据称为事务( t r a n s a c t i o n ) 。现 代化的超级市场中，售货员可以用条形码扫描器方便而准确地记录下所有的事 务。现在，许多组织已经开始收集并存储大量的篮子数据，并标明这些数据是他 们进行营销活动和商业决策的重要基础和依据。但是，现有的数据库管理系统并 没有提供足够的工具来从这些数据中发现有价值的信息和知识。 在这样的背景下，关联规则挖掘问题在1 9 9 3 年被a g m 、v a 炉j 等人提了出来。 其最初的研究目标是从事务数据库中发现有关顾客购买行为方面的知识，并用关 联规则的形式来表达所发现的知识。比如，如果我们分析出购买面包的顾客8 0 也购买了牛奶，就可以将牛奶和面包尽可能近的放在一起，以便进一步刺激顾客 同时购买这些商品。 3 2 关联规则的定义及问题描述 下面给出关联规则的一些必要的概念。 定义3 1 项与项集 数据库中不可分割的最小信息单位，称为项，一般用i 表示。项的集合称为 项集。设集合1 = i 1 ，i 2 ，i k 是项集，l 中项目的数量为k ，则集合i 称为k 一项集。 定义3 2 事务 关联规则挖掘的数据集记为t ( t 为事务数据库) ，t _ t l t 2 , t k ，t 。) ，其中 t k ： i l i 2 ，i k ，i 。l ( k = l ，2 ，n ) 为一条事务。 天津大学硕士学位论文第三章关联规则研究 表3 - 1 给出了以上关联规则概念的具体实例。 表3 - 1 关联规则相关概念 概念举例 项集i = i ，。i2 ，i )所有m 种商品 事务t 是i 的子集顾客一次购买的商品 事务数据库o = t )一定时期的所有事务记录 项集a 是i 的子集一个可能的商品组合 定义3 3 关联规则 关联规则是形如x = y 的蕴含式，其中x y ) = s u p p ( xuy 声p u 支持度反映了x 和y 中所含的项在事务集中同时出现的概率。例如“同时购 买乒乓球拍和乒乓球的顾客有4 8 ”。 定义3 5 关联规则的置信度( c o n f i d e n c e ) 关联规则的置信度是交易集中包含x 和y 的交易数与包含x 的交易数之比， 记为c o n f f x = ，即 c o n f f x 2 y ) = s u p p ( x u y ) s u p p ( x ) = p ( y i x ) 置信度反映了在包含x 的事务中，出现y 的条件概率。例如“在所有购买乒 乓球拍的顾客中有6 0 的顾客又购买了乒乓球”。 关联规则的支持度和置信度分别反映了所发现规则的有用性和确定性。一 般地，用户可以定义两个阈值，分别为最小支持度阈值和最小置信度阈值。当挖 掘出的关联规则的支持度和置信度都满足这两个阈值时，我们就认为这个规则是 有效的，否则，就是无效的。这两个阂值一般可由领域专家或用户设定。 定义3 6 频繁项集 如果项集u = u l ，u 2 一，u k 出现的频率大于或等于最小支持计数，即满足最 小支持度阈值，则称它为频繁项集( f r e q u e n tl t e m s e t ) ，频繁k 一项集的集合通常 记为l k 。 定义3 7 强规则 同时满足最小支持度阈值( m i n s u p p ) 和晟小置信度闽值( m i n c o n o 的规则称作 天津大学硕士学位论文第三章关联规则研究 强规则。强规则可由频繁项集产生。 3 3 关联规则的分类 关联规则有许多种，根据不同的标准，关联规则有多种分类例： ( 1 ) 基于规则中所处理的变量类型 根据规则中所处理的变量类型来分类，关联规则分为布尔型和数值型两种。 布尔型规则处理的值都是离散的、种类化的，它显示了变量之间的关系。 例如： s e x ( x ，”女”) = p r o f e s s i o n ( x ，”文秘”) 其中，x 为代表某人的变量。 数值型关联规则可以和多维或多层关联规则结合起来，对数值型字段进行 处理，也可对其进行动态分割，或者直接对原始数据进行处理。例如： s e x ( x ，”女”) = a v g ( x ) = 2 3 0 0 规则涉及的收入是数值类型，所以这是一个数值型的关联规则。 ( 2 ) 基于规则所涉及的抽象层分类 根据规则所涉及的抽象层来分类，关联规则可分为单层关联规则和多层关 联规则。 在单层关联规则中，不考虑现实生活中的数据实际上具有多个不同的层次， 不涉及不同抽象层的项或属性。例如： b u y x ，”i b m 电脑”) _ b u y kx ，”惠普打印机”) 其中，x 是代表某人的变量，“i b m 电脑”和“惠普打印机”属于同一概念层次 上的数据。这是个细节数据上的单层关联规则。 在多层关联规则中，充分考虑现实生活中数据的多层性，规则涉及数据不 同抽象层的项与属性。例如： b u y “x ，”电脑”) = b u y s ( x ，”打印机”) b u y s ( x ，”i b m 电脑”) = b u y s ( x ，”s o n y 打印机”) b u y s ( x ，”打印机”) = b u y s ( x ，“s o n y 打印机”) 其中，“电脑”和“打印机”属于同一抽象层；“i b m 电脑”和“s o n y 打 印机”属于同一抽象层；“电脑”是比“i b m 电脑”更高的抽象层；“打印机” 是比“s o n y 打印机”更高的抽象层。第三条规则揭示了一个细节层“s o n y 打印 机”和较高层“打印机”之间的多层关联规则，这种关联规则又称作交叉层关联 规1 ( c r o s s - l e v e la s s o c i a t i o nr u l e ) 。多层关联规则挖掘被h a r t 和h u 【2 i 】，s k i k a n t 和 a g r a w a l 等研究。 天津大学硕士学位论文第三章关联规则研究 ( 3 ) 基于规则涉及的数据维分类 根据规则所涉及的数据维来分类，关联规则可分为单维规则和多维规则。 单维关联规则也叫维内规则，是指关联规则中的项或属性只涉及数据的一 个维，这种关联规则通常通过事务数据库进行挖掘。 多维关联规则是指关联规则中的项或属性涉及两个或多个数据维。换句话 说，单维关联规则是处理单个属性中的一些关系，多维关联规则是处理各个属性 之间的某些关系。例如： b u y s ( x , ”电脑”) = b u y s ( x , 吁r 印机”) 这是一个单维关联规则。 s e x ( x ，”男”) a p r o f e s s i o n ( x ，”i t ”) = b u y s 。( ，”电脑”) s e x ( x ，”男”) 八b u y s ( x ，”电脑”) = b u y s ( x ，”打印机”) 其中，s e x 、p r o f e s s i o n 和b u y s 分别是性别维、职业维和购买维。其中第一条 规则是维间关联规则，第二条规则是一个混合维关联规则。 ( 4 ) 基于规则中涉及到的数据的确定性 根据关联规贝f j 所涉及到的数据的确定性来分类，又可分为确定关联规则和 模糊关联规则。 由于客观世界的复杂多样，许多事物是难以用精确和确定的概念来表示， 所以就出现了模糊的关联规则【2 2 1 。在模糊关联规则中，数据项用模糊概念的语义 项表示，表达更自然，更能反映商业语义。例如： p r o 岛s s i o n ( x ，”文秘”) = s e x ( x ，”女”) 这条规则只涉及到确定的数据项，是一条确定的关联规则。 p r o f e s s i o n ( x ，”模特”) = s t a t u r e ( x ，”高”1 这条规则涉及到“高”这个模糊语义项，因此是一条模糊关联规则。 给出了关联规则的分类之后，在关联规则分析时，就可以考虑某个具体方 法适用于哪一类规则的挖掘，而某类规则又可以用哪些不同的方法进行处理。 3 4 关联规则挖掘算法 a g r a w a l 等人于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集问的关联规 则问题，并设计了一个基本算法，我们称为a p r j o r i 算法吲。这是一个基于两阶段 频集思想的方法，将关联规则挖掘算法的设计分解为两个子问题： ( 1 ) 找出所有频繁项集 通过用户给定的m i n s u p p ，寻找所有频繁项集，即满足s u p p o n 不小于m i n s u p p 的项集。事实上，这些项集可能具有包含关系，一般地，我们只关心那些不被其 天律大学硕士学位论文第三章关联规则研究 它频繁项集所包含的所谓频繁大项集( f r e q u e n tl a r g ei t e m s e t ) 的集合。这些频 繁大项集是形成关联规则的基础。 ( 2 ) 由频繁项集产生强关联规则 通过用户给定的m i n c o n f , 在每个最大频繁项集中寻找c o n f i d e n c e 不小于 m i n c o n f 的关联规则。 这里，第一步相对于第二步更为复杂，是整个关联规则挖掘的瓶颈，也是 近年来关联规则挖掘算法研究的重点。 3 4 1 核心算法概述 a p r i o r i 算法是一种最具影响的挖掘布尔关联规则频繁项集的算法。它使用 一种称作逐层搜索的迭代方法，l ( - 项集用于探索他 1 ) _ 项集。首先，找出频繁1 项集的集合，记作l i ，l l 用于寻找频繁2 - 项集的集合l 2 ，而l 2 用于找l 3 ， 如此下去，直到不能找到频繁k 项集。找每个l k 需要做一次数据库扫描，为提高 频繁项集逐层产生的效率，一种称为a p r i o r i 性质的重要性质用于压缩搜索空间。 定义3 8a p r i o r i 性质 频繁项集的所有非空子集都必须是频繁的。 运用a 州硎性质，根据l k - 1 找l k ，可由连接和剪枝两个过程组成。 ( 1 ) 连接步；为找k ，通过l k i 与自己连接产生候选k 一项集的集合，该候 选项集的集合记作c k 。执行连接l k 一1 $ l k _ l ，其中