（计算机应用技术专业论文）基于rough+set的关联规则研究.pdf

西南交通大学硕士研究生学位论文第l 页 摘要 关联规则挖掘是数据挖掘领域中一个重要的研究方向，它反映了一个事 物与其他事物之间的相互依存性和关联性。i 龋公司a l m a d e n 研究中心的 r a g r a w a l 首次提出关联规则的模型，并给出求解算法，其中a p r i o r i 算法 最为经典，后人大多数是在此算法的基础上进行了改进。虽然在算法的时间 效率方面有了明显的提高，但仍存在很大的提高空间，另外还存在着一个严 重的问题：在关联规则的挖掘过程中，由于它所使用的支持度没有考虑属性 之间的重要性的差别，从而导致了挖掘出大量无效的，无用的，用户不感兴 趣的冗余的规则。本文以此为立据，一方面，利用粗糙集( r o u g hs e t ) 的有关 理论，提出新的关联规则挖掘算法，提高了算法的时间效率；另一方面，把 事务数据中各个属性权值考虑在内，重新定义新的加权支持度，提高了挖掘 结果有效性 主要工作包括： 】、运甲粗糙集( r o u g hs e t 的有关理论，推导出“多属性不可分辨娄”的 性质，然后利用此性质，提出了一种新的关联规则挖掘算法，该算法仅需扫 描一次数据库，改善了现有的挖掘算法由于多次扫描数据库而导致的时间效 率低下问题，并通过大量试验验证其算法的高效性。 2 、通过典型的例子透彻分析出传统支持度隐含着两种弊端：1 ) 没有考虑 属性的权重对规则产生的影响；2 ) 没有考虑规则中包含属性的数目对规则产 生的影响。为了消除这两种弊端，重新定义了加权支持度，通过理论分析说 明其合理性，最后通过试验验证该公式的有效性。 关键词：数据挖掘；关联规则；加权支持度；聚类分析 西南交通大学硕士研究生学位论文第| l 页 a b s t r a c t a s s o c i a t i o nr o l en i l n i n gi so n eo ft h ek e yf i e l d si nt h e r e s e a r c ho fd a t a r a i n i n g i tr e f l e c t sd e p e n d e n c ea n dr e l a t i o n s h i pb e t w e e no n ec e r t a i n i t c ma n d o t h e r s r a g m w a lw i t ha l m a d e nr e a s e r c hc e n t e ro fi b mc o m p a n yf i r s t l y i n t r o d u c e da s s o c i a t i o n r u l em o d e la n dg a v et h er e s o l v e da l g o r i t h m b a s e do nt h e f a m o u sa p r i o r ia l g o r i t h m , m o s to fl a t e ra l g o r i t h m sh a v ef o c u s e do ni m p r o v i n g t h et i m e e f f i c i e n c y h o w e v e r , t h e yf a i l e dt oa v o i dal a r g en u m b e ro fi n v a l i d ， u s e l e s sa n du n i n t e r e s t i n gr u l e sf o rt h ei t e m sa r ea s s u m e dt oh a v ee q u a l i m p o r t a n c e c o n s i d e r i n gt h e d i f f e r e n tc o n t r i b u t i o nt o t h em i n i n gr e s u l tf r o m a t t r i b u t e s ，f o ro n et h i n g ，ai m p r o v e da l g o r i t h mf o ra s s o c i a t i o nr u l eb a s e do nr o u 曲 s e ti sd e v e l o p e dt os o l v et h i sp r o b l e mm e n t i o n e da b o v e f o ra n o t h e r , an e wi m p r o v e d w e i g h t e ds u p p o ad e f i n i t i o ni sp u tf o r w a r dt oi n c r e a s et h ee f f e c i e c yo ft h er e s u l t s t l l em a i nj o b so f t h et h e s i sa r ea sf o l l o w e d ： f i r s t l y , u s i n gr e l e v a n tt h e o r y o fr o u g hs e t s 。t h et h e o r yo f “m u l t i a t t r i b u t e i n d e s c e m i b i l i t y ”i st e s t i f i e d b a s e do nt h i st h e o r y , an e wa l g o r i t h mo fa s s o c i a t i o n m l em i n i n g ，w h i c hd o s en o ts c a nt h ed a t a b a s ef r e q u e n t l ya st r a d i t i o n a lo n e sd o b u to n c e ，i sp u tf o r w a r dt oi m p r o v et h et i m e e f f i c i e n c y al a r g en u m b e ro f e x p e r i m e n t sa r ec a r r i e do u tt ov a l i d a t ei t sp e r f o r m a n c e s e c o n d l y , t h ef a c tt h a tt r a d i t i o n a ls u p p o r ti m p l i c i t st w os h o r t c o m i n g si s a n a l y z e dt h r o u g ht y p i c a le x a m p l e s 。o nt h eo n eh a n d ，i tf a i l s t oc o n s i d e rt h e i m p a c to ft h ew e i g h t i n go fi t e m so nr u l e s ；o nt h eo t h e rh a n d ，t h ei m p a c to f t h e a m o u n to fi t e m s0 nr o l e si sn o tc o n s i d e r e d ，e i t h e r t oa d d r e s st h i sp r o b l e m ，an e w s u p p o r td e f i n i t i o ni sp r o p o s e da n dt h ew e i g h t e da s s o c i a t i o nm l ea l g o r i t h m1 i s g i v e nb ya n a l y s e sa n de x p e r i m e n t s 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 ；w e i g h t e ds u p p o r t ；c l u s t e ra n a l y s i s 西南交通大学硕士研究生学位论文第l 页 1 1 论文研究意义 第1 章绪论 近年来，随着信息产业的快速发展，人们积累的数据越来越多。急剧增 长的数据背后隐藏着许多重要的信息，如何对其进行更高层次的分析，以便 更好地利用这些数据变得越来越重要。传统的数据管理方法可以高效地实现 数据的录入、查询、统计等功能，但无法发现数据中潜在的、有用的关系和 规则。为了挖掘数据背后隐藏的知识，解决“数据爆炸但知识贫乏”的现状， 人们努力寻求各种新方法和新技术。数据挖掘在这种背景下应运而生。目前， 它已经成为计算机科学研究中一个活跃的前沿领域，并在市场分析、金融投 资、医疗卫生、环境保护、产品制造和科学研究等许多领域获得广泛的成功 应用，取得了十分可观的社会效益和经济效益。同时，数据挖掘的研究和应 用对人工智能这门前沿学科的发展注入新的活力，有利地促进了计算机科学 的发展。e 融合了数据库技术、人工智能、机器学习、神经网络、统计学、 模式识别、知识库系统、知识获取、信息检索、高性能计算和数据可视化等 最新技术的研究成果。经过近二十年的研究，数据挖掘已具有了清晰的概念 和方法，并正向更深入的方向发展。 关联规则挖掘的目的是发现大量数据中项集之间的关联或相互关系，是 数据挖掘领域中一个十分重要的研究课题。它是由a g r a w a l 等人于1 9 9 3 年 首次提出。一个关联规则经典的例子是：“2 0 的客户同时购买了苹果、香 蕉和肉制品，在购买苹果和香蕉的客户当中有8 0 的客户购买了肉制品。” 它的直观含义是“客户在购买商品时有多大的倾向会购买其他的商品。”这 有助于指导商场货架组织、布局和配套穿行线路设计等。 关联规则是数据挖掘中应用最广泛的一种技术，可以说在各个领域都有 其用武之地。目前开展得比较活跃的应用领域有保险业( 预测顾客保险的模 式，分析决定医疗保险额的主要因素) 、市场营销( 预测顾客的购买行为，划 分顾客群体) 、银行业( 辨别信用卡申办中的欺诈行为，客户信誉分析) 、工业 部门( 预测机器保障) 、网络领域( 根据日志找出顾客的访问模式，进行站点设 计、网页更新) 和交通部门( 航空公司根据历史中资料寻找乘客的旅行模式， 西南交通大学硕士研究生学位论文第2 页 改进航线的设置) 。 i b m 公司a l m a d e n 研究中心的r a g r a w a l 首次提出关联规则的模型【6 j 并 给出求解算法a i s ，随后出现了s e t m 和a p r i o r i 等许多算法。其中，a p r i o r i 算法最为经典，其思想是在事务数据库中找出具有用户指定的最小支持度 ( m i n s u p ) 和最小信任度( m i n c o n f ) 的关联规则。后人大多数是在此基础上针对 算法的时闻效率进行了改进，但是针对算法的时间效率方面仍存在很大的提 高空间，另一方面，在特定的领域只需要特定模式的规则，经典算法模型挖掘 出大量无效的，无用的，用户不感兴趣的冗余规则，其原因在于经典算法的支 持度存在着严重的缺陷。 比如，某家商场某些商品由于价格昂贵导致其销售量很小，但这些商品 利润极高。商家更关心如何从交易事务数据库中挖掘出能够带来极大利润的 销售规则。就对卖扇子和空调两种商品来说，如果使用经典支持度进行挖掘 的话，由于经典支持度仅根据购买次数来进行规则的挖掘，因为扇子的购买 次数远远大于空调，那么有关扇子的规则得到了一大堆，而与空调有关的规 则可能没有，但卖一台空调比卖几千把扇子带来的利润多的多，所以挖掘出 这样的结果可能并没有多大的实际意义。 a p r i o r i 算法所使用的经典支持度之所以具有这样的盲目性和误导性， 本人认为经典支持度没有考虑到以下因素：在事务数据库中，不同的属性可 能有不同的重要性，对挖掘出的规则贡献各不相同，对它们一视同仁平等对 待。不理会用户对什么感兴趣，用户需要什么样的规则，只是单纯地把所有 满足条件的规则统统展现在用户蘑前。 本文立意以这两个问题为突破口，一是运用r o u g hs e t 有关理论，提出 新的关联规则挖掘算法，提高关联算法的时间效率；二是把事务数据中各个 属性权值考虑在内，提出新的加权支持度，提高挖掘结果有效性。 1 2 论文主要工作介绍 本文对关联规则算法时问执行效率和所挖掘结果的有效性方面进行了研 究，运用租糙集的有关理论，针对这两方面存在的闯题提出了改进算法。主 要工作如下： l 、对粗糙集和模糊集技术进行了分析研究。 2 、利用租糙集相关理论，改进布尔关型联规则挖掘算法，提高挖掘的时 间效率。 西南交通大学硕士研究生学位论文第3 页 3 、对现有的关联规则算法所挖掘结果的有效性方面做了一定的研究，并 对传统的关联规则挖掘算法中的支持度进行了深入的分析，指出其在实际应 用中存在的问题。 4 、针对实际问题分析出传统支持度存在的两种弊端。为了消除这两种弊 端，重新定义了新的关联规则的支持度，把属性的权重考虑在内，并通过理 论分析和一系列试验说明其合理性。 1 3 论文的结构和安排 本文的组织结构如下： 第一章、绪论 介绍了论文研究意义，说明了论文的主要工作和结构安排。 第二章、基于r o u g hs e t 关联规则改进算法 简单介绍论文所用到相关知识和理论，主要包括模糊集，粗糙集和关联 规则等性质，原理和概念；对a p r i o r i 算法和a p r i o r i t i d 算法做了简单描 述，指出了这两种算法在时间效率方面存在的问题：结合粗糙集的相关理论， 提出了基于r o u g hs e t 关联规则改进算法。 第三章、加权支持度的研究 在关联规则挖掘过程中，由于经典的支持度默认数据库中各属性对规则 的贡献相同，为此挖掘出的规则往往带有很大误导性，本文针对这些实际问 题归纳出经典支持度存在的两种弊端。并分析了现有加权支持度存在的不足， 重新定义新的加权支持度，提高了挖掘结果有效性。 第四章、算法试验与性能分析 首先介绍了论文试验所使用的数据测试集( 标准u c i 数据集) ；然后，描 述了在关联规则挖掘过程中所涉及数据预处理内容；对基于r o u g hs e t 关联 规则改进算法进行试验分析，验证了此算法的执行时间效率的高效性。对改 进的加权支持度进行相应的试验，验证新的加权支持度在所挖掘规则的有效 性方面产生的积极影晌。 第五章、结束语 对整篇论文的工作进行了总结和展望。 西南交通大学硕士研究生学位论文第4 页 第2 章基于r o u g hs e t 关联规则改进算法 本章首先介绍了粗糙集( r o u g hs e t ) 和关联规则的基本原理：然后描述了 两种经典的关联规则挖掘算法，并分析关联规则挖掘算法执行对闻效率低下 根本原因。最后，运用粗糙集的有关知识推导出求“多属性不可分辨类”的 重要性质并给予证明，根据此性质提出关联规则新的挖掘算法，避免了因多 次扫描事务数据库而造成的挖掘效率低下瓶颈问题。 2 1 相关原理简述 2 1 1 粗糙集 粗糙集( r o u g hs e t ) 作为一种处理不精确、不确定与不完全数据的新的数 学理论。最钌是由波兰数学家p a w j d k 于1 9 8 2 年提出。相对于概率统计， 证据理论、模糊集等处理含糊性和不确定性问题的数学工具而言，粗糙集理 论既与它们有一定的联系，又有这些理论不具备的优越性。统计学需要概率 分布，证据理论需要基本概率赋值，模糊集理论需要隶属函数，而粗糙集理 论的主要优势之一就在于它不需要关于数据的任何预备的或额外的信息。近 年来，由于它在机器学习与知识发现、数据挖掘、决策支持与分析等方面广 泛应用，研究逐渐趋热。 1 近似空间与不可分辨关系 定义l 【6 】：设u 为所讨论对象的非空有限集合，称为论域；r 为建立在u 上的一个等价关系，称二元有序组a s = ( u ，r ) 为近似空间( a p p r o x i m a t e s p a c e ) 。 近似空阔构成论域u 的一个划分；若r 是u 上的一个等份关系，以 x 】r 表示x 的r 等价类，u r 表示r 的所有等价类构成的集合。即商集：r 的所 有等价类构成u 的一个划分，划分块与等价类相对应。 定义2 1 6 ：令r 为等价关系族，设p r ，且p o ，则p 中所有等价关 系的交集称为p 上的不可分辨关系，记作i n d ( p ) ，即有 西南交通大学硕士研究生学位论文第5 页 i x - n d ( ，j = n 【x 】n r e p ( 2 - 1 ) 显然i n d ( p ) 也是等价关系。 例2 1 设论域u = x l ，x 2 ，x 3 ，& ，x s ，r = r 1 ，r 2 ，r 3 l ，i 是恒等关系，r l ，r 2 ，r 3 定义如下：一， r l - ，( x 2 ，x i ， ， ui r 2 2 i x l ，) ( 2 ， ，q ( 4 ，x s ui r 3 = ， x 2 ，x t x , ， ， ， ， ， ui 若p = r i ，r 2 r ，则由定义可知： 。 i n d ( p ) = r ln r 2 2 ， t t i i n d ( p ) = r l m r 2 n r 3 = ， u i 等价关系中所含的儡序较多，上述表示方式过于繁琐。另一种相对来说 更为简便的表示方式是利用等价关系对应的商集来间接描述不可分辨关系。 若有r l ，r 2 ，r 3 按上述方式给出，则有： u l q = x 1 ，x 2 ) ， x 3 ，磁 ， x d u r 2 = , * ：x 1 x 2 ，f x 3 ：， x 4 。x s ： u r 3 = x l ，x 2 ，x 3 ， x 4 ，x 5 j ； 不可分辨关系i n d ( p ) 的等价类的集合为( 按 x 】i n d ( r i f1 【x 】n 计算) ie p 肼i n d ( p ) = u r l r z 净“x l ，x 2 ， x 3 ， x 4 ；， x 5 u i n d ( p ) = u r i ，r 3 = “x l x 2 ) ， x 3 ， x 4 ， x 5 不可分辨关系是标准粗糙集( p a w l a k 粗糙集) 理论中最基本的概念若 e i n d ( p ) ，则称对象x 与y 是p 不可分辨的，即x , y 存在于不可分辨关系 i n d ( p ) 的同一个等价类中。依据等价关系簇p 形成的分类知识，x 与y 无法 区分。u t n d ( p ) 中的等价类称为p 基本集( 或原子集) 。基本集是粗糙集理论 中构成知识的基本模块。若集合x 可以表示成某些基本集的并时，则称x 是 p 可定义集，否则称为p 不可定义集。 粗糙集理论将分类方法看成知识，分类方法的簇集是知识库。等价关系 对应论域u 的一个划分，即关于论域中对象的一个分类。因此，通过一个等 价关系可以形成与之对应的论域知识( 即等价类的集合一商集) 。从而得到不 可分辨关系对应论域u 上的知识。 定义3 t 6 】：称论域u 的子集为u 上的概念( c o n c e p t ) ，约定中也是一个概 西南交通大学硕士研究生学位论文第6 页 念，概念簇集称为u 上的知识；u 上知识r 分类) 的簇集构成关于u 的知识 库，也就水说，知识库是分类方法的集合。 定义4 【6 】：设u 为论域，r 为等价关系簇。p r 且p o ，则不可分辨 关系i n d ( p ) 的所有等价类的集合，即商集u i n d ( p ) 称为u 的p 基本知识， 相应等价类称为知识p 的基本概念。特别地，若等价关系q r ，则称u q 为u 的q 初等知识，相应等价类称为q 初等概念。由于选取r 的不同子集 p 可以得到u 上的不同知识，故称k 彳u ，r ) 为知识库。 为了简单起见，用u p 代替u i n d ( r ) 。p 基本概念与p 基本集相对应。 给定知识库k ；田，r ) ，知识库的知识粒度由不可分辨关系i n d ( r ) 的等价 类反映。不难证明，对所有p 三r 有i n d ( p ) ：i n d ( r ) ，也就是说任绘一个r 基本概念( r 等价类) ，都可以找至q 个p 基本概念( p 等价类) ，包含绘定的r 基本概念。 定义5 【6 】设集合五c u ，r 是个等价关系，定义： 麟= & ix 芒u 且【x 】。x ) 积= x l x u 且【x 】rn x 。)lhj ( 2 2 ) ( 2 3 ) 分别称r x 及砑为x 的r 下近似集和上近似集，称集合 b n a ( x ) = p 。x 一型为x 的边界域；p o s ( x ) = 丛为x 的r 正域 n e g 。( x ) = u 一面为x 的r 负域。 上近似，下近似和边界域的关系如图2 - 1 所示： i| y 、一 、 厂i - ( i l _ l ， 、r 卜一， ，f 图2 一l 粗糙近似示意图 西南交通大学硕士研究生学位论文第7 页 定义6 嘲当b n 。( x ) = 中时，即蔽= 醛时，称x 是r 精确集( 或可定义 集) 。当b n r ( x ) o 时，e p t o ：麟时称x 是r 粗糙集( 或不可定义集) 。 由等价关系r 定义的集合x 的近似精度为： ar 0 ) ( 2 - 7 ) b n 。x = & l j u 至t 0 = m i n s u p ，则称项目集x 是频繁的( f x e q u e n t ) 。一个项目集的最小 支持度是该项目集被认为是有意义的，支持它的交易数占数据库d 所有交易 总和的最小比例，通常是根据经验来确定的。不具有最小支持度的项目集被 认为是没有意义的。项目集中所包含的项目个数称为它的长度或基数。长度 为k 的项目集称为k ( k ：l x l ) 维项目集，记做k i t e m s e t 。 项目集的性质： 频繁项目集具有以下三个性质，性质1 和性质3 是所有关联规则算法的 基础。 性质l ：子集支持【1 4 1 设a 和b 是两个不同的项目集，如果a 是b 的子集，则s u p ( a ) = s u p ( b ) 。 因为是d 中所有支持b 的交易也一定支持a 。 性质2 ：非频繁项目集的超集也一定是非频繁的【4 1 如果a 在d 中不满足最小支持度条件，即s u p ( a ) m i n s u p ，则a 的每 个超集b 也不是频繁的。由性质1 可得s u p ( b ) = s u p ( b ) = m i n s u p ，因此a 也 是频繁的。特别的如果a 是频繁的，则它的k 个基数为( k - 1 ) 子集都是频繁的， 反之则不成立。 。 。 2 、关联规则的定义： 设i = i i ，1 2 i 。 是一个以m 个不同项目为元素组成的集合，t 是针对i 的交易的集合，每笔交易包含若干个属于i 的项目。关联规则表示为x j y ， 其中x ，y 是l 的子集，并且x n y = o ，x 称做规则的前提或前项，y 为结果 或后项。 每个规则也有两个度量标准：支持度( s u p p o r t ) 及信任度( c o n f i d e n c e ) 。 规则支持度定义为： s u p p o r t ( x ：y ) = s u p p o r t ( x u ( 2 - 1 4 ) 规则信任度定义为： c o n f i d e n c e ( xy ) = s u p p o r t ( xuy ) s u p p o r t ( x ) ( 2 15 ) 关联规则的形式如下： r ：x 号y ，其中x 及y 是两个不相交的集合；x ，y 是i 的子集并且x n y = o 。 关联规则可以理解为一个命题，即如果一个交易支持项目集x ，则它具有也 西南交通大学硕士研究生学位论文第1 i 页 一定的可能性支持项目集y ，这个可能性称之为规则的信任度，记做c o n f ( 鼬 或c ( r ) 。 关联规则的支持度反映了该规则的频度，而它的信任度则表明了整个规 则的正确度。一个关联规则必须具备足够大的支持度及信任度。对于给定的 最小可信度m i n c o n f 及最小支持度m i n s u p ，如果c o n f ( r ) = m i n c o n f ， s u p ( r ) = m i n s u p ，则称关联规则r 关于数据库成立。规则的前项及后项必须 是频繁的是一个关联规则成立的必要条件。 一个关联规则必须同时满足最小支持度和最小可信度条件，二者缺一不 可。如果一个关联规则的可信度为1 0 0 ，但是它描述的并不是数据据中的 一个普通模式，由于它不满足最小支持度的约束，该规则也应该被删除。假 设一个规则具有足够大的支持度，但是可信度却很低，例如购买肥皂的顾客 中2 的人也购买了水果，这一事实虽然被数据库中的大部分数据支持，但 是由于它不能表示出项耳间的较强的相关性，因此也不能作为一个关联规则 存在。 规则前项及后项不相交条件并不是必须的：如果去掉这一约束条件不产 生错误的规则，只是会产生冗余或没有意义的规则。因此规则x 寺x u y 黾一个正确规删。由于x 寺xu y 与x 号x u y 是等价的，因此规则xj x u y 就没有意义。规则的前项x 可以是空集，每个交易都支持空项目集，因此整 个数据库也支持空项目集。前项为空集的规则的可信度等于后项目集的相对 频度。同样道理规则的后项y 必须是非空的项目集，并且前项和后项项目集 不能相交。对交易t 来说，规则r ：x 辛xuy 的可信度c o n f ( r ) 是一个条件概 率，如果y = o ，则c o n f ( r ) = s u p ( x u y ) s u p ( x ) = l 。这表明规则x 辛x 与x 寺o 是等价的。 3 、关联规则挖掘步骤 关联规则挖掘的问题就是找出这样的一些规则，它们的支持度或信任度 分别大于指定的最小支持度值m i n s u p 和最小可信任度m i n c o n f o 因此，该问 题可以分解成如下两个子问题： l 、产生所有支持度大于或者等于指定最小支持度的项集，这些项目囊 称为频繁项目集( f r e q u e n t i t e m s e t s ) ，而且其它的项目集则称非频繁项目集。 2 、对于每个频繁项目集，产生可信度大于或等于最小信任度的规则， 如下：对于一个频繁项目集l 及任意s ，且s 是l 的子集，如果s u p ( l ) s u p ( s ) = m i n c o n f , 那么规则s 净( l s ) 就是一个正确规则。 关联规则挖掘的问题的主要特征是数据量巨大，因此算法的效率很关 西南交通大学硕士研究生学位论文第1 2 页 键。目前研究的重点在第一步，即发现频繁项目集，因为第二步相对来说是 很容易的。 2 2 经典关联规则挖掘算法 2 ，2 1a p r i o r i 算法 最为著名的关联规则挖掘方法是r a g r a w a l 提出的a p r i o r i 算法。关联 规则的挖掘分为两个步骤：第一是迭代识剐所有的频繁项目集，要求频繁项 目集的支持度不低于用户设定的最小值：第二步是从频繁项目集中构造可信 度不低于用户设定的最小值的规则。识别或发现所有频繁项目集是关联规则 发现算法的核心。也是计算量最大的部分。 1 、a p r i o r i g e n 算法： 输入：大小为i 1 的频繁集l i 1 。 输出：大小为i 的候选集c i 。 c ；= n u l l f o re a c h i l 。1d o f o re a c hj z i l i 1 d o i fi 一2o ft h ee l e m e n t si nia n dja r ee q u a lt h e n c f c k u i u j a p r i o r i g e n 算法的作用是在关联规则的挖掘过程中的第一步中，根据i 1 项频繁集l i 1 ，求出大小为i 的候选集c i 。 2 、a p r i o r i 算法： 输入：项目集合i ，事物数据库o ，支持度s 输出：频繁集l k = 0 ；l = n u l l ；c l = i r e p e a t k = k + i ：l l = n u l l 每个项目集的初始计算设为o f o re a c h i i l l - id o c - o ； 统计每个项目c i 出现的次数 西南交通大学硕士研究生学位论文第1 3 页 f o re a c h c t dd o f o re a c hi 。c kd o i f l i t jt h e n c i = c i + l 判断是否满足最小支持度，生成频繁集l k f o re a c hi i c kd o i fc i ( s x i d i ) t h e n l k = l k u i i ； l k = l k u i i ； 生成侯选频繁集ck + i c k + l = a p r i o r i g e n ( l k ) u n t i lc k + i = n u l l 此算法的基本步骤课大致归纳如小形式： 连接一 剪枝一 生成侯选频繁集c k 一 扫描次数一 比较一 生成频繁集l k 。 3 、a r g e n 算法： 输入：d事务数据库 ls 真, 目集 l频繁项目集 s 支持度 a 信任度 输出： r满足s 和a 的关联规则集合 a r g e n 算法： r = o f o r e a c hi l d o f o re a c hx ls u c ht h a tx md o i fs u p p o r t ( l ) s u p p o r t ( x ) = at h e n r = ru x ：( l - x ) ， 此算法为在最大频繁集中提取关联规则的算法。 4 、a p r i o r i 算法性能瓶颈问题 a p r i o r i 算法作为经典的频繁项目集生成算法，在数据挖掘中具有里程 碑的作用。但随着深入研究，它的缺点也随之暴露出来，存在两个致命的性 能瓶颈。 西南交通大学硕士研究生学位论文第1 4 页 l 、多次扫描事务数据库，需要很大的l o 负载。 对每次k 循环，候选集c k 中每个元素都必须通过扫描数据库一次来判 断其是否要加入生成的频繁集。假如一个频繁项目集包含1 0 个项，那么就至 少扫描事务库1 0 遍。 2 、可能生成庞大的候选集 由于k 产生k 一候选集c k 是呈指数增长的，例如1 0 4 个1 频繁项目集就 可能产生接近1 0 7 个元素的2 候选集。如此大的候选集对时间和主存空间来 讲都是一种挑战。 2 3 2a p r i o r i t i d 算法 a p f i o d t i d 算法是基本的a p n o d 算法的一种扩展。该算法还有另外一 个特点，即仅在第一次对事务数据库d 扫描时计算候选项目集的支持度，其 他各次扫描用其上一次扫描生成的候选事务数据库c k 来计算候选频繁项目 集的支持度。c k 中的每一个成员具有 的形式，其中每一个x k 是 一个事务中潜在的k 项目集，对应一个标志符t i d 。当k = - i 时，c l 对应数据 库d ，只不过是d 中的每个项目i 替换成。当k l 时，c k 由算法的第1 0 ) 步产生。对应与事务t 的c k 中成员具有 1 1 、e n d 1 2 ) l k = e c d c c o u n t = s 1 3 ) e n d 1 4 ) a n s w o r = u k k a p r i o r i t i d 算法虽然在挖掘的时间效率上有了很大的突破，但关联规则 挖掘算法的时间效率仍存在很大的提高余地。 2 3 基于r o u g hs e t 关联规则改进算法 2 3 1 多属性不可分辨类的性质 1 、不可分辨类概念 一个信息系统s 是由一个二元组s ：( u ，r ) 组成，其中，u 是一组对象的 非空集合，称为论域；r 为有限个属性的非空有限集合，对于每一个属性x r 都有一个映射：xu 一 x f u ) ，且x e u ) 称为属性x 的值域。当a 进一步划分为两 个不相交的集合：条件属性集c 和决策属性集d ，并且满足a = c ud 且c n d = 由。 在信息系统中有属性a r ，记 a 】。为信息系统中对象x 在属性a 下属 性值为a 的不可分辨类，即 a 】。= x ：a ( x ) = a ( 2 - 1 6 ) 2 、多属性不可分辨类推导过程 给定信息系统s ：( u ，r ) ，假设r = a ，b ，c ，d ) ，c = a ，b 且d = c ，d j ，也就是 说s 由a , b ，c ，d 四个属性组成，而c 由a , b 这两个属性组成，d 由c , d 这两个 属性组成。根据前面我们所介绍的粗糙集的相关理论，可以知道对于cn d = m 的时候，都有 c 】。n ( d 】。= c u d 】。成立。 假设c = a ，b ，c 和d = b ，c ，d ) ，也就c 和d 相交非空时，上面结论 c 】。n d 】。= 【c u d 】。是否同样成立? 如果成立的话，我们就可以利用这个性 质，在关联规则挖掘过程中的第一步，仅需扫描一边事务数据库，首先计算 出频繁1 项集，其余k 频繁集可以通过此性质计算得到，从而大大提高的算 法的时间执行效率，同时为提高a p r i o r i 算法的执行效率开辟了一条新选径。 设信息系统s = ( u ，r ) ，u 为所考虑对象的非空有限集合( 论域) ；r 为所 西南交通大学硕士研究生学位论文第1 6 页 有属性组成的非空有限集合；设有r 的两个子集x 与y ，其中x 与y 相交 非空，即x r ，y r ，o xnyer 。我们给出多属性不可 分辨类的性质： 多属性不可分辨类的性质 设信息系统s = ( u ，r ) ，x r ，y r ，西一xny r ， 则 【x hn 【y l ，= 【xuyl|(217) 在这里，符号n 和u 分别是集合意义上的交运算和并运算。 一证明： 因为对于任意( c ，dcr ) 且( c nd - m ) 都有 e l a o 【d j 。= 【c ud 1 。 所以【x 】。= 【( x x n y ) u ( x n y ) 】- 2 【( x x n y ) 】。n 【x n y t 同理：【1 f 】。2 【( y x o y ) l n 【x n y 】a 所以【x h n 【y 】。= 【( x x n y ) 】。n 群n y 】。n 【( y x n y ) 】。n 【x n y 】a = 【( x - x n y ) 】。n 【x n y 】。n 【( y x n y ) k = i x l 。n ! ( y x n y ) k 2 x u y k 因此命题得证。 由此类推可得： 【q 。n 【b 】。n f q 。2 f a u b u c 玉 【a 1 a n 【b 】。几【c 】。n 【d 】。= 【a u b u c u d 】a 。 【x 1 】an 【x 2 l an 【x 3 l a n 【x 。】。2 x 1ux 2ux 3 ux n a 此性质为求多属性的不可分辨类的主要依据。 2 3 2 基于r o u g hs e t 的关联规则挖掘算法描述 l 、事务数据库的转换 根据粗糙集中的信息系统定义，可以把事务数据库转换为信息系统。信 息系统可以用数据表格来表示，将事务数据库d 的行当成信息系统中对象 j 】：将事务数据库中的项集当成信息系统的属性集x l l l , 每个属性值血取 西南交通大学硕士研究生学位论文第1 7 页 值如下：当t 【i 】行出现属性x i j 时，m i j 取值为a ，否则为0 。 粗糙关联规则支持度，信任度的定义： 。 唧( x y ) - 睦量i t 旦i 咄 c o n f ( x y ) 一 归ln 【y l i 丽可一 其中 x a 和 v a 表示属性x ，y 属性值为a 的不可分辨类， 基数。 ( 2 t 8 ) ( 2 t g ) 牛l 为集合的 经过以上转化后，在关联规则的挖掘过程中寻找频繁集裁变为：在信息 系统中找出属性组合o x 1 ，判断o x ；1 = a 的不可辨的类的个数是否大 l i 1 j - l j - l j 1 于最小支持度，如果大于最小支持度则为频繁集，利用多属性不可分辨类的 性质来进行计算出最大频繁集，这样只需扫描一边数据库避免了因多次扫 描数据库而带来的时间效率低下的问题。 2 、基于r o u g hs e t 关联规则改进算法的思想： 第一步：输入事务数据库，输入最小