（计算机应用技术专业论文）基于粗集理论的关联规则挖掘研究.pdf

摘要 粗糙集理论是一种新的处理不确定性知识的数学工具。近年来， 粗糙集理论在知识发现中的应用己取得了很大的进展，基于粗糙集理 论的方法逐渐成为数据挖掘主流方法之一，而在数据挖掘的知识模式 中，关联规则是比较重要的一种。关联规则挖掘就是在数据集中寻找 给定项之间的有趣关系，而传统关联规则挖掘只能挖掘布尔型关联规 则，且效率低。在信息系统中获得模板的基础上，基于粗糙集理论的 关联规则挖掘，将可以挖掘更广泛的关联规则，并有助于提高所获规 则的简洁性。 近年来，粗糙集理论在决策信息系统的属性约简和决策规则的抽 取方面已取得很好的成果。本文借用粗糙集理论中口一约简的概念，提 出了一种新的启发式关联规则挖掘算法，可以获取近似最优强关联规 则。在已获得模板t 和原信息表的基础上创建一张新的决策表，先通 过将组成模板的描述子的知识量作为启发函数知识量大的描述子 优先成为候选口一约简集中的元素，再通过对候选口一约简集中的元素 进行计数，从而选择满足阈值的约简集作为最终的近似最短口一约简， 也即通过运用启发式算法求描述子集的近似最短口一约简来进行关联 规则挖掘，最后通过“相关系数”对提取出的强规则进行筛选，以得 到最终有趣的关联规则。通过示例，验证了本文提出的有关启发式算 法相关理论，此法可以求得基于模板t 的近似最短口一约简，快速挖掘 出尽可能多的关联规则。本文提出的将粗糙集理论运用于关联规则挖 掘的算法，弥补了经典关联规则挖掘方法的不足，有助于提高挖掘效 率，拓宽关联规则挖掘范围。 关键词：粗糙集理论；关联规则；模板：描述子；口约简 a b s t r a c t r o u g hs e tt h e o r yo f f e r s an e wm a t h e m a t i c a lt o o lt os o l v et h e p r o b l e m sw i t hu n c e r t a i n t y i nr e c e n ty e a r s ，t h ea p p l i c a t i o n so fr o u g hs e t t h e o r yi nk n o w l e d g ed i s c o v e r yh a v em a d eg r e a tp r o g r e s s e s t h em e t h o d b a s e do nr o u g hs e tt h e o r yg r a d u a l l yh a sb e c o m eo n eo ft h em a i n m e t h o d si nd a t am i n i n g a s s o c i a t i o nr u l ei sak i n do fv e r yi m p o r t a n t k n o w l e d g ep a t t e r n si nd a t am i n i n g a n ds o m ei n t e r e s t i n gr e l a t i o n sa m o n g i t e m si nt h eg i v e nd a t ac a r lb ef o u n dw i t ha s s o c i a t i o nr u l em i n i n g t e c h n o l o g y t h et r a d i t i o n a la l g o r i t h m sf o ra s s o c i a t i o nr u l em i n i n g c a no n l y m i n ea s s o c i a t i o nr u l e so fb o o l e a nt y p e b yu s i n gt h ec o n c e p to fat e m p l a t e i ni n f o r m a t i o ns y s t e m s ，t h em e t h o do fa s s o c i a t i o nr u l em i n i n gb a s e do n r o u g hs e tt h e o r yc a nm i n ea s s o c i a t i o nr u l e so fo t h e rt y p e sa n di m p r o v e t h ec o m p a c t n e s so fa s s o c i a t i o nr u l e s i nr e c e n ty e a r s ，g r e a tp r o g r e s s e sh a v eb e e nm a d ei nt h ea p p l i c a t i o n so f r o u g hs e tt h e o r yf o ra t t r i b u t er e d u c i n ga n dr u l e se x t r a c t i n gi nd e c i s i o n i n f o r m a t i o ns y s t e m s i nt h i sp a p e r , an e wd e c i s i o nt a b l ei sc o n s t r u c t e d f r o mag i v e nt e m p l a t eta n da no r i g i n a li n f o r m a t i o nt a b l e t h ek n o w l e d g e q u a n t i t y o fd e s c r i p t o r sa sh e u r i s t i ci n f o r m a t i o ni su s e dt o d e s i g n a n a l g o r i t h mf o rf i n d i n gas u b o p t i m a l 口r e d u c t d e s c r i p t o r sw h i c hc o n t a i n m u c hk n o w l e d g ew i l lh a v et h ep r i o r i t yt ob e c o m eac a n d i d a t ei nt h e s u b o p t i m a l1 2 一r e d u c t t h e nt h er e d u c t i o n ss a t i s f y i n gt h eg i v e nt h r e s h o l d c a r lb ec h o s e na st h ef i n a la p p r o x i m a t es h o r t e s t 盘一r e d u c t b yt h eh e u r i s t i c a l g o r i t h mp r o p o s e d i nt h e p a p e r ，a na p p r o x i m a t es h o r t e s t 口- r e d u c to f d e s c r i p t o r s c a nb e o b t a i n e d ，t h e n a s s o c i a t i o nr u l e sc a nb e g o t t e n a c c o r d i n gt o r e l a t i o n a lc o e f f i c i e n t ，s o m ei n t e r e s t i n gs t r o n ga s s o c i a t i o n r u l e sc a nb es e l e c t e df r o mt h er u l e so b t a i n e db yt h ea l g o r i t h m w ea l s o v e r i f yt h eh e u r i s t i ca l g o r i t h mp r o p o s e di nt h i sp a p e rw i t h i na ne x a m p l e t h ep r o p o s e da l g o r i t h mc a nm i n ea s s o c i a t i o nr u l e sf r o md a t a b a s e sn o t o n l yw i t hb o o l e a nt y p e ，a n dr e m e d y t h ed e f e c to fc l a s s i c a la l g o r i t h m s k e y w o r d s ：r o u g hs e tt h e o r y ；a s s o c i a t i o nr u l e ；t e m p l a t e ；d e s c r i p t o r ； 口一r e d u c t 第一章绪论 第一章绪论 1 1 论文的选题背景和意义 数据采集和存储技术的进步导致庞大的数据库日益增多，这已经发生在人类 耕耘的几乎所有领域，从普通的超市业务数据、信用卡使用记录、电话呼叫清单 以及政府的统计数据等领域，到不太普通的天体图像、分子数据库和医疗记录等 领域。能否从这些数据中提取出对数据库拥有者有价值的信息呢? 人们对这个问 题的兴趣在不断增长。而且已经形成了致力于这个任务的- - f 学科数据挖掘。 目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现 数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘 数据背后隐藏知识的手段，导致了“数据爆炸但信息、知识贫乏”的现象。而我 们要想在这些数据和信息的基础上进行迅速准确的决策就必须借助一些新的技术 和自动工具，以便将海量的数据转化成有价值的信息和知识。这些都促使数据挖 掘的出现并推动其发展。 在激烈的市场竞争中，企业只有通过了解和分析某一产品潜在消费群体的特 征，才能在未来的市场竞争中取得主动权。在市场决策中需要很多支持信息，传 统的市场调查数据分析主要是用统计方法对调查数据进行单项统计处理。而如何 揭示事物间客观存在而未被人所知的内在联系具有更重要的实际意义。 关联规则模式作为当前数据挖掘研究的主要模式之一，侧重于描述数据中不 同领域之间的联系，找出满足给定条件的多个域之间的依赖关系。根据这种关联 性可从某一数据对象的信息来推断另一数据对象的信息。从大量商务事务记录中 发现有趣的关联关系，可以帮助许多商务决策的制定。因此在这个领域的研究具 有很大的实际意义。 粗糙集理论作为一个具体的数据挖掘技术，也是一门新兴的学科，它由波兰 学者p a w l a kz 于1 9 8 2 年正式提出。在粗糙集理论的研究上存在两个方向，其中 一个方向是将粗糙集理论作为数学的研究范畴和领域，把粗糙集理论当作种纯 粹的集合理论，侧重于构造粗糙集的数学理论体系。另外一个方向则是将粗糙集 理论作为人工智能和知识发现的一种实用技术，运用到生产生活中的各个方面， 本文着重第二个方向的研究。 由于数据挖掘和粗糙集理论都是新兴的学科，两者在国内的研究都明显落后 基于粗集理论的关联规则挖掘 j j 究 于国外，作为二者结合的方法一基于粗糙集理论的关联规则挖掘方法的研究更加 明显落后于国外，因此，对这一方法进行研究具有重大的意义，这f 是本论文选 题的意义之所在。 目前的关联规则挖掘方法有很多，但仍存在许多不足：如产生大量我们并不 感兴趣的关联规则，算法效率低，一般仅能产生定性的关联规则等。而粗糙集理 论是一种新的数据分析理论，是一种可以处理不确定性知识的数学工具，我们用 粗糙集的理论与关联规则挖掘相结合，可以发挥很大的优势：其一，我们通过粗 糙集的方法对传统关联规则进行改进，不仅可以挖掘定性的关联规则，还可以挖 掘定量的关联规则；其二，运用粗糙集的方法，对属性进行约简，减少了计算量， 提高了挖掘的效率；其三，数据库的数据表与信息表的形式类似，为粗糙集理论 与关联规则挖掘的结合提供了平台，易于操作。由此可见，将裉糙集理论应用于 关联规则的挖掘有很广阔的发展前景。 1 2 国内外研究动态 关联规则挖掘是由a g m w a lr ，等人提出来的。关联规则挖掘的研究是近几年 研究较多的数据挖掘方法，在数据挖掘的各种方法中应用得也最为广泛。运用关 联规则进行数据挖掘可以发现大量数据中的项集之间有趣的关联或相关联系。目 前，关联规则的算法比较多，如经典的a p r i o r i 算法“，它是目前频繁集发现算 法的核心，是一种最有影响的挖掘布尔关联规则频繁集的算法：此外还有改进的 f p 一增长算法”1 ，使用f p 一树，通过模式段的增长，挖掘频繁模式；以及基于 h a s h 的方法等，都大大提高了a p r i o r i 算法的性能，但大都是从经典算法 a p r i o r i 演绎而来。 粗糙集理论是波兰科学院和波兰华沙大学的一些学者长期共同研究的成果， 由波兰学者p a w l a k z 于1 9 8 2 年正式提出。1 9 9 2 年出版了粗糙集理论的应用专辑， 总结了当时的粗糙集理论和应用。p a w l a kz ( 1 9 9 9 ) 出版的专著系统全面的阐述 了粗糙集理论，给出了严密的数学定义和表述。自1 9 9 2 年开始至今每年都召开以 粗糙集为主题的国际会议，国际上成立了粗糙集学术研究会，国内从2 0 0 1 年开始 由中国计算机学会和人工智能与模式识别专业委员会主办，每年召丌一届粗糙集 与软计算学术研讨会。 k o m o r o w s k ij ，p a w l a kz 等人于1 9 9 8 年阐述了经典的粗糙集理论，系统的 介绍了包括特征选择、特征提取、规则获取与评判在内的基于粗糙集的建模方法 第一章绪论 过程，总结了粗糙集理论的几种推广形式，探讨了粗糙集理论与其他几种理论方 法的关系，列举了粗糙集的一些应用，比较了几种进行粗糙集理论和应用研究的 软件系统。p a w l a kz 于2 0 0 2 年对基于粗糙集的数据分析方法的理论研究及应用 状况进行总结，阐述了基于粗糙集理论的智能数据分析技术在很多方面取得的最 新进展，粗糙集为在数据中寻找隐臧的模式提供了有效的算法，能够对数据进行 压缩，并给出了一个评价数据质量的标准，可以直接从数据中获取决策规则。 其他许多专家学著在粗糙集的应用方面也做了广泛深入的研究，已经有很多 基于粗糙集理论的分析系统和工具，其中有代表性的研究系统有：加拿大r e d u c t s y s t e m 有限公司的d a t a l o g i c r ；美国肯萨斯大学的l e a r n i n gf r o me x a m p l e sb a s e d o nr o u g hs e t 澉兰波兹南科技大学的r o u g h d a s 和r o u g h c l a s s ；国内中科院自动 化研究所的r s l 等。 经过近几年的研究和发展，已经在信息系统分析、人工智能及应用、决策支 持系统、知识与数据发现、模式识别与分类、故障检测等方面取得了较为成功的 应用。 基于粗糙集提取规则的方法就是应用粗糙集理论进行规则挖掘的方法。规则 的提取主要依据决策信息表来进行。该方法的一般过程包括： ( 1 ) 对数据进行预处理，建立决策信息表： ( 2 ) 进行属性约简： ( 3 ) 提取规则。 因为粗糙集是一种处理不确定性的数学工具，而且无需提供问题所需处理的 数据集合之外的任何先验信息。其次同基于频繁项集的方法，规则容易获得，而 且规则的简洁性好。虽然该方法具有上述优点，但是，基于粗糙集方法产生的候 选规则多，规则产生过程中对信息表进行约简和提取规则时的计算量大。为了弥 补这些不足，研究人员陆续提出了一系列关于属性约简和规则提取的改进方法。 如：基于可分辨矩阵的约简方法“2 。1 、粗糙集与模糊集的结合、粗糙集与神经 网络的结合、粗糙集与决策树的结合、粗糙集与概率统计的结合等。 本文从数据库中的原始数据出发，通过将数据库中的连续属性离散化，旨在 将粗集理论用以进行关联规则挖掘。一方面，对粗集理论和关联规则挖掘进行学 习研究；另一方面，通过对传统的关联规则挖掘算法的分析比较，运用粗集理沦 基于粗集理论的关鞋规则挖掘研究 对关联规则挖掘的第二步进行了改进，大大提高了挖掘的效率，拓宽了挖掘的数 据范围，降低了挖掘的复杂度。 1 3 论文的主要研究内容 本文以粗糙集理论作为数据的分析工具，以关联规则挖掘作为数据分析的目 的，进行了以下工作： 第一、阐述了传统的关联规则挖掘算法、粗糙集理论与方法。 第二、提出了基于口一约简的关联规则挖掘启发式算法。 第三、探讨了关联规则的评价方法。 1 4 论文的组织结构 本文章节及内容的安排如下： 第一章绪论 简述了论文的选题背景及意义：并分析了当前粗糙集、关联规则挖掘的 国内外的研究动态，阐述了本论文的主要研究内容。 第二章关联规则挖掘和粗糙集理论简介 介绍数据挖掘的发展和目前应用研究的概况，研究关联规则挖掘的相关 方法及传统算法，并分析了传统关联规则挖掘存在的问题，提出了改进的方 向；同时对粗糙集理论进行了介绍，首先给出粗糙集理论的相关基本概念和 定义，其次，重点讨论了信息决策表的属性约简和核，最后，说明了粗糙集 理论的应用及其发展方向。 第三章基于粗集理论的关联规则挖掘 在前面几章基本理论的基础上，研究了连续属性离散化常用方法的应用 要点，并通过其中的层次聚类方法进行离散分类，重点研究了信息系统的关联 规则挖掘方法；提出在已提取到模板t 后，通过启发函数求满足模板t 的最 小置信度的描述子集的近似最短口一约简进行关联规则的挖掘，最后通过“相 关系数”对提取出的强规则进行最后的筛选，以得到最终有趣的关联规则。 总结和展望部分对本文的工作进行总结，并且提出若干继续进行研究的 方向和工作展望。 d 第二章关联规则挖掘和租糙集理论简介 第二章关联规则挖掘与粗糙集理论简介 2 1 关联规则挖掘 2 1 1 关联规则挖掘简介 数据挖掘( d a t a m i n i n g ) 就是对观测到的数据集( 经常是很庞大的) 进行分 析，目的是发现未知的关系和以数据拥有者可以理解并对其有价值的新颖方式来 总结数据“。这些数据可以存放在数据库、数据仓库或其它信息存储中。这是一 个年青的跨学科领域，源于诸如数据库系统、数据仓库、统计学、机器学习、数 据可视化、信息检索和高性能计算。其他有贡献的领域包括神经网络、模式识别、 空间数据分析、图像数据库、信号处理和许多应用领域，包括商务、经济学和生 物信息学等。 数据挖掘也称为术语数据库中的知识发现( 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 ) 1 “。 一般由以下几个步骤组成： 1 ) 数据清理其作用就是清除数据噪声和与挖掘主题明显无关的数据。通常 包括：添补遗漏数据、平滑噪声数据、识别或去除异常值，以及解决不一 致问题。有问题的数据将会误导数据挖掘的搜索过程。 2 ) 数据集成其作用是将来自多数据源中的相关数据组合在一起。由于描述 同一个概念的属性在不同数据库取不同的名字，在进行数据集成时常常会 引起数据的不一致或冗余。因此在完成数据集成之后，有时需要进行数据 清洗以便消除可能存在的数据冗余。 3 ) 数据选择其作用是从数据库中检索与分析任务相关的数据。 4 ) 数据变换其作用是将数据变换或统一成易于进行数据挖掘的数据存储 形式。数据变换包含以下处理内容：平滑、合计、泛化、规格化以及属性 构造。平滑是一种数据清洗方法，合计和泛化也可以作为数据消减的方法。 对于使用基于对象距离的挖掘算法，必须进行数据规格化，将其收缩至特 定的范围内。 5 ) 数据挖掘它是知识挖掘的一个基本步骤，其作用就是利用智能方法提取 数据模式或规律知识。 基于粗集理论的关联规则挖掘研究 6 ) 模式评估 其作用就是根据一定评估标准从挖掘结果筛选出有意义的模 式知识。一个数据挖掘系统在完成一个挖掘算法之后，常常会获得成千上 万的模式或规则。在这些规则中，只会有- 4 , 部分是有实际应用价值的。 需要对数据挖掘步骤所获得的挖掘结果进行有效的评估，以便最终能够获 得有实际应用价值的模式或规则知识。 7 1 知识表示使用可视化和知识表示技术，向用户展示所挖掘出的相关知 识。 知识发现的全过程如图2 - 1 所示1 ： 图2 - 1 知识发现过群 尽管数据挖掘仅仅是整个知识挖掘过程中的一个重要步骤，但在工业、媒体、 数据库研究领域中，“数据挖掘”一词已被广泛使用和普遍接受，不加区分地表示 整个知识挖掘过程。 现有的多种数据分析方法从总体上均可归类到统计学习方法、机器学习方法 以及仿生物学方法这三大类中的某一种，在应用上这些方法各有利弊，需要针对 具体挖掘问题选择合适的技术。对于复杂的数据挖掘系统，还常常采用多种数据 挖掘技术以弥补不同数据挖掘技术所存在的不足。 传统的统计方法有回归分析、聚类分析、主元分析以及相关分析等”。，在传 统的统计学习方法基础上，已经形成多种新型的数据分析方法，如基于范例的推 理方法、贝叶斯网络方法以及新兴的支持向量机技术等。 机器学习方法是目前研究的重点，研究成果较多。从采用的技术上看，可分 为两大类：基于决策树的技术和基于决策规则的方法。基于决策树的技术以信息 第二牵关联拢则挖掘和糟撵集理论简介 论的原理为基础建立决策树，最后获得的知识表示形式是决策树，最著名的方法 就是q u i n l a n 开发的i d 3 方法，另外还有a s s i s t a n tp r o f e s s i o n a l 、i d l 以及p r i s m 等门j 。基于决策规则的方法又可细分为两类，一种是在决策树基础上加入规则求 取步骤获得决策规则的方法，如c n 2 方法、c 4 5 方法吲等；另外一种则是直接 具有规则求取能力的方法，如r o u g h 集、f u z z y 集，后面我们将详细介绍r o u g h 集的相关内容。 仿生物技术典犁的方法是神经网络方法和遗传算法，这两种方法已经形成了独立的研究 体系，在数据挖掘中发挥着巨大作i l f j 。 关联规则是数据挖掘的知识模式中的比较重要的一种。关联规则的概念由 a g r a w a l 、i m i e l i n s k i 、s w a m i 提出，隐含于数掘中的种简单而实用的知识模式。 关联规则模式属于描述型模式，挖掘关联规则的算法属于无监督学习范畴。 关联规则挖掘旨在寻找给定数据集中项之问的有趣关系。所谓项是指形如 ，= 1 ) 或( 爿，= o ) 的模式。设i = ( f 。，i ：，i 。 是项的集合。设任务相关的数据d 是数 据库事务的集合，其中每个事务t 是项的集合，使得t 亡，。每一个事务有一个 标识符，称作t i d 。设a 是一个项集，事务r 包含a 当且仅当a t 。关联规则 是形如a jb 的蕴涵式，其中a c ，b c ，并且a n 日= o 。一般情况下，我们用 两个数量指标支持度s 和置信度c 来度量关联规则：如果d 中事务包含aub 的百分比为8 则称规则a jb 在事务集d 中具有支持度，。即支持度 ( 爿jb ) = 皇鱼等学，它是事件a u 占的频率，是概率p ( a t 3 占) 的近似 值。规则ajb 在事务集d 中具有置信度c ，是指d 中同时包含a 与b 的事务在 包含a 的事务中所占的百分比，即置信度( aj b ) = 拿喜爹器，它是条 件概率p 佃的频率。理论上，通常将关联规则a j b 的支持度s u p p o r t ( a j b ) 和黄信度c o n f i d e n c e ( ajb ) 定义为： s u p p o r t ( ajb ) 2 j p ( 一u b ) c o n f i d e n c e ( ajb ) = 尸佃 支持度是对关联规则重要性和实用性的衡量，置信度是对关联规则的准确度 基于粗集理论的关联规则挖掘研究 和有效性的衡量。支持度说明了这条规则在所有事务中有多大的代表性，显然支 持度越大，关联规则越重要。有些关联规则置信度虽然很高，但支持度却很低， 浇明该关联规则实用性很小，因此就会不重要。 通常，关联规则挖掘通过寻找频繁项集来实现。所谓频繁项集是指支持度大 于支持度闺值p 。的项集。关联规则的获取可以通过以下两个步骤来完成： 1 ) 找出所有频繁项集：这些项集出现的频率至少和预先设定的最小支持度 一样。 2 ) 由频繁项集产生强关联规则：这些规则必须满足最小支持度和最小置信 度。 2 1 2 关联规则的a p r i o f i 算法 关联规则应用面很广，如识别欺诈，购物篮分析等。推销商可以用关联规则 帮助他们分析客户的性质，确定客户的主要来源，从而在不减少收入的前提下节 约不必要的开支；商场根据关联规则可以设计不同的货架布局，还可以规划什么 商品可以降价销售，什么商品可以捆绑销售，以刺激消费，增加盈利；利用关联 分析方法对宏观经济系统中的宏观经济变量进行关联分析，以选择适当的经济变 量，剔除不必要的变量，建立准确、高效的宏观经济模型。关联规则既可以检验 各领域内长期形成的知识模式，也能够发现隐减的新舰律。有效地发现、理解和 运用关联规则，是完成数据挖掘任务的一个重要手段。 关联规则的挖掘研究己成为数据挖掘研究的热点，迄今为止，已出现了很多 算法，最典型的是a p r i o r i 算法。该算法使用候选项集找频繁项集，使用一种逐 层搜索的迭代方法，矗项集用于探索( k + 1 ) 一项集。首先，找出频繁1 一项集的集 合。该集合记作厶。上用于找频繁2 一项集的集合厶，而厶用于找厶，如此下 去，直到不能找到频繁“项集。为了压缩搜索空间，主要依据于a p r i o r i 性质。 a p r i o r i 性质：频繁项集的所有非空子集也都是频繁的。由此性质可知，如 果个集合不能通过测试，则它的所有超集也都不能通过相同的测试。 a p r i o r i 算法主要通过k 与自己连接产生候选舡项集的集合，然后根据任何 非频繁的1 ) 一项集都不可能是频繁 一项集的子集进行剪枝，最终找到频繁缸项 集。 t p r i o r i 算法“： 输入：事务数据库d ；最小支持度阈值r a i ns u p 。 第一二市关联规则挖掘和射i 糙集理论简介 输出：d 中的频繁项集上。 ( 1 ) l j = f i n d _ f r e q u e n t _ 1 一i t e m s e t s ( d ) ； ( 2 ) f o r ( k = 2 ；l k ，西；k + + ) ( 3 ) q = a p r i o r i g e n ( l k _ ，m i n s u p ) ； ( 4 ) f o re a c ht r a n s a c t i o nted s c a ndf o rc o u n t s ( 5 ) c f = s u b s e t ( g ，t ) ；g e tt h es u b s e t so ftt h a tc a n d i d a t e s ( 6 ) f o re a c hc a n d i d a t ec g ( 7 ) c c o u n t + + ； ( 8 ) ( 9 )上广 c c l c c o u n t m i ns u p ( 1 0 ) ) ( 1 1 ) r e t u r n 三2 u 止i p r o c e d u r ea p r i o r ig e n ( 如，：f r e q u e n t ( k - 1 ) - i t e m s e t s ；r a i n s u p ：m i n i m u ms u p p o r tt h r e s h o l d ) ( 1 ) f o re a c hi t e m s e tf l l k 1 ( 2 ) f o re a c hi t e m a e tf 2 l kt ( 3 )i f ( 1 l 1 卜如 1 】) ( 2 】= 如 2 ) 八八( “k 一2 = ，z k 一2 ) a ( h k _ 1 f 2 k - l 】) ( 4 ) t h e n c = 1 1 0 0 l 2 ： j o i ns t e p ；g e n e r a t ec a n d i d a t e s ( 5 ) i f h a s _ i n f r e q u e m s u b s e t ( c ，l k 1 ) t h e n ( 6 ) d e l e t e c ； p r u n es t e p ：r e m o v eu n f r u i t f u lc a d i d a t e ( 7 ) e l s ea d dc t o c k ； ) ( 8 ) r e t u r nc k ； p r o c e d u r eh a s i n f r e q u e n t _ s u b s e t ( c ：c a n d i d a t ek - i t e m s e t ；l k i ：f r e q u e n t ( k 一1 ) - i t e m s e t ) u s ep r i o rk n o w l e d g e ( 1 ) f o re a c h j ( k 1 ) 一s u b s e tso f c ( 2 )i f s 仨l k i t h e n ( 3 ) r e t u mt r u e ； ( 4 ) r e t u r nf a l s e ； 在生成频繁项集后，由频繁项集产生关联规则的方法如下： ( 1 ) 对于每个频繁项集，产生f 的所有非空子集。 基于粗集理论的关联规则挖掘研究 ( 2 ) 对于，的每个非空子集s ，如果 s u p p o r t s u p p o r t c o u n t ( 1 ) c o u n t ( s ) m i n _ c o n f ，贝输出规贝9 “5j ( f _ s ) ”。其中m i n _ c o n f 是最小置信度阈值。 此外，在a p r i o r i 算法基础上还出现了改进的f p - 增长算法“，基于h a s h 的 算法“4 1 等。这些传统的算法虽然为推动关联规则挖掘的研究作出了巨大的贡献， 但依然存在一定的局限性：算法效率不高，有时甚至会导致组合爆炸，且仅能挖 掘布尔关联规则，挖掘出的规则冗余度大，会产生大量用户并不感兴趣的关联规 则等。 2 2 粗糙集理论 2 2 1 粗糙集理论的概念 粗糙集理论是波兰数学家z p a w l a k 在1 9 8 2 年提出的一种分析数据的数学理 论。是一种新的处理模糊和不确定性知识的数学工具。其主要思想就是在保持分 类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。目前，粗糙 集理论已被成功地应用于机器学习、决策分析、过程控制、模式识别与数据挖掘 等领域。 定义2 1 “”设u ，是我们感兴趣的对象组成的有限集合，称为论域。 定义2 2 “”任何子集并u ，称为u 中的一个概念或范畴。 定义2 3 n 2 3 如果置u ，x ，置f x j = 以u x ，= u ，其中 f ，i ，j = 1 , 2 ，n ，称f = x i x 2 ，以) 为论域u 的一个划分。 定义2 4 “”设置是u 上的一族等价关系，芷= r m 彤称为一个知识库，若 p r ，且p 庐，则n p ( p 中所有等价关系的交集) 也是一个等价关系，n p 称为p 上的不可区分( i n d i s c e r n i b i l i t y ) 关系，记为i n d ( p ) 定义2 5 “2 1给定知识库尽= f m 尉，对于每个子集x ( ，和等价关系i n d ( r ) ，x 的r 下近似集定义为蹦= u r u i r i y g x ) ，x 的r 上近似定义为 r x = u f f u r ij ，n x ，集合砌r ( ) = r x 一些称肖的r 边界域， p o s r ( x ) = 些称为x 的r 正域，n e g 。( x ) = u r x 称为z 的负域。这里u r 是 u 删的简记，表示由等价关系i n d ( r ) 所决定的u 的划分，它是i n d ( r ) 的所有等 价类所构成的集合。足石是由那些根据知识r 判断肯定属于x 的u 中元素组成的 集合：r x 是那些根据知识r 判断可能属于z 的u 中元素组成的集合；b n 。( x ) 是 1 0 第二二章关联规则挖掘和莉l 糙集理论简介 那些根据知识r 既不能判断肯定属于爿又不能判断肯定属于硝的( ，中元素组成 的集合；n e g 。( x ) 是那些根据知识r 判断肯定不属于的u 中元素组成的集合。 当能表达某些月基本概念( 范畴) 的并时，称z 是月可定义的，月可定义 集也称作r 精确集：否则称x 为月不可定义的，j r 不可定义集也称为r 非精确集 或r 萃r 糙集( r o u g hs e t ) 例2 1 ：给定一知识库瓦= 以刖和一个等价关系r i n d ( k ) ，其中 u = x o , x l ，x l o ，且有r 的下列等价类：e i = f ， ，e 2 = x 2 ，z 6 ，x 9 ) ， e 3 = x 3 ，x 5 ，e 4 = x 4 ，x 8 ) ，e 5 ： x 7 ，x l o ) 假设有集合鼻j = x 0x l ，x 4 ，) ，x 2 = x 0 屯，x 4z 5 ，z 8 ，x i o ，根据定义有： 蹦i = r x l = e lu e 。，所以为r 可定义集； 星盖2 = e 3u e 4 = x 3 ，x 4 ，x 5 ，x 8 ) ， r x 2 = e u e ，u e 4 u e 5 = ，x ，屯，硝，z 5 ，x 7 ，x 。 ，_ 2 为粗糙可定义集。 2 2 2 粗糙集理论中的知识表示 在粗糙集理论中，一般采用信息表或决策表作为知识表示框架。称四元组 s = 以彳，v 刀是一个信息系统，其中 u ：对象的非空有限集合，称为论域； a ：属性的非空有限集合： v = u ，v ；是属性a 的值域； fu ) c a r 是信息函数，它为每个对象在每个属性下赋一个值，即 v a a ，x u ，f ( x ，口) 圪 通常s = r u , a ，聊也简记作s = r u 圳。 信息系统的数据以关系表的形式表示。关系表的行对应要研究的对象，列对 应对象的属性。当没有重复元组时，信息表是一个关系数据库。若将条件属性集 划分为条件属性集c 和决策属性集d ，则该信息表就被称为决策表。无决策的数 据分析和有决策的数据分析是粗糙集理论在数据分析中的两个主要应用。 2 2 3 属性约简与核 属性约简是粗糙集理论的核心内容之一。所谓属性约简，就是在保持知识库 分类能力不变的条件下，删除其中不相关或不重要的属性。 定义2 6 “”设信息系统s = r u 刎是一个信息系统，b c 为条件属性的非空 子集，如果存在一子集b cb ，有i n d ( b ) = i n d ( b ) ，则称曰为属性依赖集，否则，称 基十粗集理论的关联规则挖掘韧f 究 为独立集。如果b c 为独立集，且i n d ( c ) = i n d ( b ) ，则b 称为c 的约简。c 的所 有约简记为r e d ( c ) 定义2 7 “2 1 对于任意属性d c ，如果i n d ( c ) f n d r c - 扣，则称a 为c 中不 可省略的。c 中所有不可省略属性的集合称为c 的核，记为c o r e ( c ) ，且有 c o r e ( c ) = f q r e d ( c ) 一般情况下，属性的约简不唯一，而核是唯一的。 定义2 8 1 t 2 设信息系统s = 似驯是一个决策表，a = c u d ，b c 为条件属 性的非空子集，d 为决策属性集，d 的1 3 正域记为p o s 。、( d ) 。即 p o s l 。 ) ( d ) = u 旦y ，d 的b 正域是u 中所有根据分类u b 的信息可以准确划分 ，5 到属性集d 的等价类中去的对象集合。 定义2 9 “”设s = 州是一个决策表，a = c u d ，b c ，如果存在一子集 bcb t 7 卣p o s m f 口1 ( f h d ( d ) ) = p o s 删b ) ( f d ( d ) ) ，则b 称为相对于d 的依赖集，否 则，称为b 相对于d 的独立集。 定义2 1 0 “”若b c 是相对于d 的独立集，且 p o s 州c ) ( m d ( d ) ) = p o s m ( 8 ) ( 加d ( d ) ) ，则称b 为c 相对于d 的约简。c 的所有d 约 简记为r e 而幻 定义2 1 1 1c 中所有d 不可省略属性的集合称为c 的d 核，记为c o r e d 倒， 且有c o r e d ( c ) 一nr e d d 幻 属性约简是粗糙集用于数据分析的重要部分。因为信息表中属性的多少直接 影响到数据挖掘算法的复杂性，从而影响到数据挖掘算法的效率，而冗余属性的 删除还可以提高数据挖掘的效率和所获知识( 规则) 的简洁性。 对于小规模的数据库，我们可以使用区分矩阵来表达知识，从而很容易地计 算出约简与核。 令s = r u 州是一个知识表达系统，l 硼一n 。s 的区分矩阵是一个n x n 矩阵， 其任一元素为a ( x ，y ) = a af ( x ，a ) f ( y ，日) ) 。因此口( x ，y ) 是区别对象x 和y 的所有属性的集合。 约简是满足能区别由整个属性集区别的所有对象的极小集，即对 v c t ( x ，y ) 庐，若b a 是满足条件口n a ( x ，y ) ，的极小属性子集，则日是爿 的一个约简。为了计算方便，a s k o w r o n 引入一个区分函数的概念，即 第二章关联规则挖掘和相糙集理论简介 2 ( 。，眉。，口( x ，y ) ，并证明了约简即为区分函数的极小析取范式“。 核是区分矩阵中所有单个元素组成的集合，即 c o r e ( a ) = a a ( x ，y ) = 口) ，其中x ，y u ) 对于带决策属性的决策表，我们可以用类似的方法来计算其相对约简和相对 核。对于大规模的信息系统，通过引入属性的重要性来求属性的核，进而以核为 起点，求出属性的约简。 近年来，粗糙集理论在数据库领域的知识发现中的应用取得了很大的进展， 基于粗糙集理论的方法逐渐成为k d d 主流方法之一。 2 3 本章小结 本章对数据挖掘进行了概述，阐述了数据挖掘的一般过程，并给出关联规则 的概念及其描述形式，研究了经典a p r i o r i 算法，及其在频繁项集的基础上挖掘 关联规则的方法，并讨论了传统关联规则挖掘算法的局限性以及关联规则的应用 及研究动态；同时也简要介绍了粗糙集的相关理论，给出了粗糙集的相关基本概 念，以及粗糙集理论中的知识表示形式：信息表或决策表，讨论了信息决策表的 属性约简与核，并给出了小规模信息系统基于区分矩阵的属性约简和核的计算方 法。 基于租集理论的关联规则挖掘研究 第三章基于粗集理论的关联规则挖掘 随着数据的规模越来越大，数据的类型越来越复杂，从这些复杂的信息中快 速、有效地挖掘出相关知识，就成为我们研究的热点。传统的关联规则挖掘算法 效率不高，且仅能挖掘布尔规则，挖掘出的规则冗余度大，且会产生大量虽然是 强关联规则却不是用户真正感兴趣的规则。针对这些局限性，本文针对无决策信 息系统，将粗糙集的相关理论运用于关联规则的挖掘，从而拓宽关联规则挖掘的 范围，提高关联规则挖掘的效率，增强关联规则挖掘的准确性。本章从数据的预 处理，连续属性的离散化及属性的约简进行了研究，并重点研究了关联规则挖掘 的第二步，以启发式算法对经典的规则抽取方法进行了改进。 3 1 连续属性离散化 由于传统的关联规则挖掘只能处理布尔型数据库，对于数值属性依然束手无 策，因此，本文结合了粗糙集理论来进行挖掘。因为粗糙集理论的数学基础是集 合理论，分析对象是信息表，要求信息表中的各种属性的值必须是离散的，而实际 中的大型数据库中存放的数据大部分都是连续性数据，因此在运用粗糙集理论之 前，必须对连续属性的原始数据进行合理的离散化。 针对属性离散化问题，已经提出许多算法。有s l o w i n s k i 方法心方法) 。，是 s l o w i n s k i 利用领域知识将连续性属性转换为象“低”，“中”，“高”和“很高”等 特定的词汇；有h u 4 1 方法( h 方法) ，通过领域专家事先提供概念树，将适于概念 树提升的属性进行属性的离散化；有l e n a r c i k 方法。，把原系统看成是随机信息 系统，在此基础上定义了划分质量的期望值，通过每次删除增益最大的分点，直 到划分质量不再增加为止。 事实上，粗糙集理论的优势就在于它不需要任何先验知识便可完全从数据或 经验中获得知识。s o m 自组织映射网络方法、g a 进化计算方法、聚类方法、信息 熵方法已经成为连续属性离散化的主流方法。“。由于各种方法都有自己的优缺点， 任何一种方法应用要点的把握，都直接关系到离散化的效果，因此我们必须结合 实际选用适合离散目的的正确的方法，从而研究这些方法的应用要点就显得很重 要。 通过自组织特征映射网络( $ o m ) 对连续属性进行离散化，输出层神经元数量等 于聚类数目。正确选取聚类数目非常关键，聚类数目少，可能会得到不相容的决 第三章基于相集理论的关联舰则挖掘研究 策系统，聚类数目多，会出现过度离散情况导致抽取规则时判断的复杂度大大 增加，通常可以用启发函数来进行优化。详见文献 3 0 。