（计算机应用技术专业论文）基于粗糙集对apriori算法的改进.pdf

上海师范大学硕十学位论文 摘要 摘要 关联规则挖掘是数据挖掘的方法之一。关联规则挖掘通过分析训练数据集， 从其中找到潜在的、有价值的知识。关联规则挖掘在商业领域中有着广泛的应用， 著名的“尿布与啤酒 的例子就是关联规则挖掘的杰作。 本文首先介绍了数据挖掘的相关概念和算法。在关联规则挖掘中，a 研o r i 算 法占据重要地位。a p r i o r i 算法对事务数据库中的所有项集进行分析筛选，依照特 定的最小支持度，从中找到有强关联的频繁项集，并计算所有强关联记录的置信 度，但大量候选集的产生以及多次扫描数据库的操作制约了a 曲o r i 算法的执行效 率。接着，本文介绍了有关粗糙集理论方法的概念。粗糙集理论能有效地处理复 杂系统中的数据与信息，是处理模糊和不精确问题的理想工具。 由此，本文将粗糙集理论方法引入到对a 研o r i 算法的改进工作中，提出一套 新的改进算法a 皿o r i r s 算法。a p r i o m 己s 算法利用项集分类预处理的方法对 事务数据库中所有的项集进行预处理，从而减少了大量候选集产生的可能性。在 筛选项集的过程中，利用粗糙集理论中的知识约简方法对项集进行化简，避免了 重复扫描数据库的操作。 在随后的试验中，通过挖掘训练数据集，将改进后的算法与a p r i o r i 算法的试 验结果进行比较，获得了理想的试验结果。 关键词：数据挖掘，关联规则，粗糙集理论方法，a 州o r i r s 算法 a b s t r a c t 上海师范大学硕十学位论文 a b s t r a c t a s s o c i a t i o nm l ei so n eo ft h em e t h o d so fd a t am i n i n g b ya n a l y z i n gt r a i n i n gd a t a s e t ，w ec a nf i n dp o t e n t i a la n dv a l u a b l ek n o w l e d g ea c c o r d i n gt oa s s o c i a t i o nr u l e i nt h e a 托ao fb u s i n e s s ，a s s o c i a t i o nr u l em i n i n gi sw i d e l yu s e d a sw ea l lk n o w n ，t h e a s s o c i a t i o no f “n 印k i na n db e e r ”i sf o u n db yu s i n ga s s o c i a t i o nr u l em i n i n g a tt h eb e g i n n i n g ，t h i sp a p e ri n t r o d u c e st h ec o n c e p t i o no fd a t am i n i n ga n dd a t am i n i n g a l o r 旷i t h m i na s s o c i a t i o nr u l em i n i n a p r i o r ia l g o r i t h mo c c u p i e sv e 巧i m p o i r t a n ts t a t u s a p r i o r ia l g o r i t h mf i l t e r s a n da n a l y z e si t e m si nt h ed a t a b a s e ，a n df i n d s s t r o n g a s s o c i a t i o no ft 1 1 ef k q u e n ti t e m sa c c o r d i n gt om i n i m u ms u p p o r t ，m e nc a l c u l a t e st h e c o n f i d e n tv a l u eo ft h ei t e m s h o w e v e r ，a p r i o r ia l g o r i t h mw i l lp r o d u c eam o u n to f c a n d i d a t ei t e m sa i l ds c a nt h ed a t a b a s es om a n yt i m e s ，w h i c hw i ur e d u c em ee m c i e n c y o fm ea l g o r i t h m a n dt h e nt 1 1 e p a p e ri n t r o d u c e st h ec o n c e p t i o no fr o u g h s e tm e t l l o d s r o u 曲- s e ti sak i n do ft h e o r yt oa n a l y z ea n dd e d u c ed a t a r o u 曲一s e tc a i le m c i e n t l y d e a lw i t ht h ed a t aa n di n f 0 肌a t i o ni nc o m p l e xs y s t e m a n di ti sak i n do ft o o l st od e a l w i t h 如z 巧觚di m p r e c i s ep r o b l e m s s o ，w ep r o p o s ean e wm e t h o d ，a p r i o r i r sa l o g r i t h mt oi m p r o v et h ee f f e c to f a p r i o r ia l g o r i t h mb yu s i n gm em e t h o do fr o u g h s e t a p r i o r i r sa l o g r i t h mp r e - d e a l s t h ed a t ai nt h ed a t a b a s eb yu s i n gi t e m sd i v i s i o n t h u s ，、v ec a nr e d u c et h ep o s s i b i l i t yo f t h ec a n d i d a t ei t e m sp r o d u c e d i nt h ep r o c e s so fi t e m s6 l t r a t i o n ，、v eu s et h em e t h o do f k n o w l e d g er e d u c t i o nw h i c hi so n eo ft h em e t h o d si nr o u g h - s e tt or e d u c et h ei t e m s t h i sc a na v o i dt h eo p e r a i t i o nt os c a nt 1 1 ed a t a b a s er e p e a t e d l y a n dt h e n ，、eh a v ed o n es o m ee x p e r i m e n ta b o u t t h i s b ym i n i n gt r a i n i n gd a t a ，w e c o m p a r et h er e s u l t so f b o t ht h ea l g o r i t h mi m p r o v e da n da p r i o r i ，a n dg e ta ni d e a lr e s u l t k e y w o r d s ： d a t a m i n i n g ， a s s o c i a t i o nr - u l e s ， r o u g h s e tm e t h o d s ，a p r i o r i r s a l g o r i t h m i i 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究 成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表 示了谢意。 作者签名疰舒日期：砷、厂、夕孑 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此 规定。 作者签名在稻导师签名：日期：刀夕f 2 p 易坳i 红 上海师范大学硕士学位论文第一章绪论 第一章绪论 1 1 论文研究背景 如果时光倒退3 0 年，人们获取信息的途径相对贫乏，传播信息的媒体也比较 单一，所以，当时想在已有的消息中找到有价值的信息并不是一件很难办到的事 情，人们只要有选择性地“吸收”一些与自己所感兴趣的领域相关的信息，就能 在其中找到自己想要的知识。 然而，随着时光流逝，人们慢慢发现知识的缺失严重影响了自己的工作效率， 单一的消息来源以及信息传播方式常常会将人们引入歧途，造成时间和资源的浪 费。消息的匮乏不仅禁锢了人们的思维，更催生了人们强烈的求“知欲。 现如今，高度发达的网络已使计算机成为人们获取信息的主要来源，通过浏 览网页，我们可以轻而易举地搜寻到任何需要的信息。可是，信息量剧增带来了 大量信息，有价值的与没有价值的信息都掺杂于其中，获取有价值的信息又成为 了人们的当务之急，人们急需一种强大的工具来分析数据，从数据中找到有价值 的信息，由此，数据挖掘技术就应运而生。 知识的提炼是数据挖掘技术最主要的任务，通过对海量信息地对比分析，数 据挖掘能提供给人们很多令人激动的信息，这些让人难以置信的信息往往非常有 价值【l 】，所以，目f j 数据挖掘技术已被很多研究人员视为一个十分重要的研究方 向。涉及多个领域的研究，通过分析数据库中的大量数据，数据挖掘技术能从其 中发现潜在的、有意义的知识【2 】。数据挖掘技术中，关联分析是用来表示局部模 式的最流行方法之一【3 】o 关联规则为数据挖掘中的模式提供了种简单描述形式【4 】。通过分析大量信 息的关联程度，关联规则挖掘能发现诸如“尿布与啤酒”这样的经典例子【5 】。近 几年来，关联规则挖掘已成为数据挖掘领域的研究热点【6 】。 在关联规则挖掘的众多方法中，a p r i o r i 算法应用最广泛，占据十分重要的地 位 7 1 。a p r i o r i 算法通过反复扫描数据库，分析记录中的所有项集，依照一定的最 小支持度( m i n，从众多项集中筛选出符合要求的频繁项集，并计算其置_support) 信度。a p r i o r i 算法通过接连n 阶候选集来生成n + l 阶候选集，所以，a p r i o r i 算法 能挖掘出绝大多数的频繁项集，最大程度地减少了频繁项集地遗漏情况；在摒弃 非频繁项集的过程中，a p r i o r i 算法将严格按照最小支持度的限定，逐步排除非频 繁项集，对于小于低于最小支持度的项集，a p r i o r i 算法一概删除，可以看出，只 要最小支持度设定合适，a p r i o r i 算法具有很强的频繁项集挖掘能力。 a p r i o r i 算法的优点十分明显，但其缺陷也很突出。由于要反复多次扫描事务 数据库，算法执行的效率会大打折扣。对于数据挖掘技术来说，大多被应用于大 型的数据库或数据仓库中，a p r i o r i 算法将花很多时间用于对数据记录的来回检索 第一章绪论上海师范大学硕十学位论文 上，对于一些具有较高时间要求的时效性策略系统，这样的缺陷是不可容忍的。 另外，a p r i o r i 算法在生成候选集的时候，采用的是项集自连接的方式，这就使得 候选集的产生将十分庞大，检索候选集的时问也将随之骤然增长。 综上所述，我们发现以下两大因素制约了a p r i o r i 算法的执行效率【8 】： 1 多次反复地检索事务数据库； 2 检索大量候选集。 针对a p r i o r i 算法的两大缺陷，我们需要一种用于解决不确定问题的工具来对 该算法进行优化，粗糙集理论方法无疑是很好的选择。 z p a w l a k 于1 9 8 2 年提出了粗糙集( r o u g hs e t ) 理论【9 】，该理论具有很强的定 性分析能力，能够利用知识的不完整、不确定性进行推理。粗糙集理论方法中的 知识约简是发现知识的工具之一，利用粗糙集理论方法中的知识约简概念可以对 多属性决策分析方法进行优化【l o 】。大型数据库中存在大量冗余属性，在分析数据 的过程中，这些不重要的、冗余的数据就成了限制算法执行效率的重要因素【l l 】。 属性约简能有效地能减少重复的、冗余的数据出现的频率，很大程度上提高了算 法运行的效率。因此，粗糙集理论与方法可作为a p r i o r i 算法改进的理论依据。 虽然粗糙集理论方法已被广泛应用于数据挖掘技术中，但大多体现在信息进 行分类的分类挖掘规则中，将粗糙集理论方法应用于对关联规则的改进还不多见。 鉴于粗糙集方法能有效地提高知识发现的效率，本文将粗糙集应用于a p r i o r i 算法 的改进中，通过相应试验结果，验证了改进算法的良好效果。 1 2 研究现状 从r a g r a w a l 于1 9 9 3 年提出关联规则挖掘的问题以来，人们愈来愈多地将目 光投向这方面领域【翻。随着关联规则挖掘技术得到越来越多专家的认同，很多研 究人员对关联规则的算法也进行了大量的研究。大致可以分为： 1 h a s h b a s e di t e m s e tc o u n t i n g ( 散列项集计数) 【1 2 】 散列项集计数的方法将项集表现为诸女l ：l 的形式，k e y 对应的是项 集的名字，v a l u e 对应的是项集出现的次数，当执行数据挖掘操作时，只需要扫描 散列表，而不是扫描整个事务数据库，这样就可以很大程度减少扫描的工作量， 提高算法执行效率。 2 t r a n s a c t i o nr e d u c t i o n ( 事务压缩) 【1 3 】 将事务数据库中的记录进行压缩也是一种比较有效的提高算法运行效率的方 法。事务压缩的主要思想是：不包含k 阶频繁项集的事务不可能包含k + l 阶频繁 项集，换而言之，如果事务不包含k 阶频繁项集，则在生成k + l 阶候选集时，就 不考虑该事务。如此，数据挖掘过程中所生成的候选集数量将大为减少，有利于 削减运行算法的时间开销。 3 p a r t i t i o n i n g ( 划分) 2 上海师范大学硕士学位论文第一章绪论 划分方法主要是针对项集预处理而言，在执行数据挖掘操作之前对数据记录 中意义或种类近似的项集进行划分，分区对其进行挖掘操作，将一个原本复杂的 大规模检索工作化简为几个相对小型的扫描操作，能使挖掘过程更简单，这也符 合“分而治之”的算法化简原理。 4 s a m p l i n g ( 采样) 1 1 5 采样技术是一种以时间换精度的方法，在数据库中抽取一些样本作为分析过 程的基础数据，得出这些局部数据的关联模型之后，检测该模型的实际描述效果， 这种“抽样+ 检测的模式虽然在时间上开销很大，但使用这种方法能有效地提 高模型导出的准确性，确保数据挖掘结果的有效应用。 在众多的关联算法中，a p r i o r i 算法无疑占据重要地位【l6 】，有很多关联规则的 算法就是建立在对a p r i o r i 算法的改进上，针对a p r i o r i 算法本身存在的缺陷。虽 然研究人员已对关联规则算法进行了大量桌有成就的改进，但其中很少采用粗糙 集理论方法对算法进行改进，而粗糙集理论方法能够针对不确定的问题进行有效 的分析，得出较为准确的结果，适用于关联分析过程，所以，本文将粗糙集理论 方法引入到对a p r i o r i 算法的改进中，力求能在较大程度上弥补a p r i o r i 算法的固 有缺陷。 1 3 论文的主要工作 本文主要论述一种改进a p r i o r i 算法的新型算法，该算法采用粗糙集理论方法 中的相关知识处理关联规则的相关问题。在介绍总结了关联规则中的常用算法之 后，本文针对a p r i o r i 算法的缺陷，提出一套基于粗糙集理论的改进算法，并将该 理论应用于实践，进行了相应试验的论证。具体论述工作如下： 1 较为详尽地介绍了数据挖掘技术地产生和发展原因，并介绍了一些关联规 则常用的算法； 2 结合关联规则挖掘技术，本文介绍了a p r i o r i 算法的基本步骤、特点以及 相关领域的研究成果； 3 介绍粗糙集理论方法的相关概念，以此来论述粗糙集理论方法对于改进 a p r i o r i 算法的理论可行性； 4 在对a p r i o r i 算法的研究基础上，本文提出了一种基于粗糙集理论方法的 改进方法项集约简方法。通过引用粗糙集理论方法中的知识约简方 法，项集约简方法简化了筛选频繁项集的操作过程； 5 在单纯的项集约简方法的基础上，本文提出了一套新的算法一一 a p r i o r i r s 算法，该算法针对原来项集约简方法的缺陷进行了一定程度的 优化，提高了算法执行的效率； 6 本文运用c 群编程语言实现了改进的算法，并将该算法的运行效率和准确 性与原来的a p r i o r i 算法进行比较，论证了改进算法的相对优越性。 3 第一章绪论上海师范大学硕士学位论文 1 4 论文的创新点 本文的创新点如下： 1 结合粗糙集理论方法中知识约简的相关理论，提出一种对a p r i o r i 算法的 改进算法a 研o r i r s 算法。 2 优化了项集预处理步骤，使算法生成的候选集大幅度减少，并减少了算法 运行的时间开销。 3 引入粗糙集理论方法，改进算法的相应步骤，简化原算法的候选集生成过 程，提高算法的运行效率。 1 5 论文的安排 4 本文分为六章，大致内容如下： 第一章讨论了研究对象的背景、研究意义以及目前国内外对于该领域的研究 现状； 第二章介绍了数据挖掘技术的相关理论概念、实现方式和导出模式，并介绍 了a p r i o r i 算法的基本步骤和具体实现，同时还介绍了一些其它的关联 规则算法； 第三章详细介绍了粗糙集理论方法的相关知识，论述了将知识约简理论用于 模糊处理的优势，阐述了粗糙集理论方法用于改进关联规则算法的可 执行性； 第四章结合a p r i o r i 算法与粗糙集理论，提出一套新的改进算法，详细描述该 算法的步骤，论述改进算法的理论优势； 第五章将改进算法与原来的a p r i o f i 算法进行实验比较，并对两种算法给出性 能评估； 第六章总结全文的工作，阐述将来的研究方向。 最后列举参考文献以及致谢。 上海师范大学硕+ 学位论文 第章数据挖掘技术简介 第二章数据挖掘技术简介 2 1 数据挖掘技术产生的原因 当人们置身于海量数据中时，难免产生一种迷茫的感觉，因为在如此大量的 数据中，“无用”的信息量远远大于“有用”的知识，找寻自己所需要的数据犹如 大海捞针，这就使得人工手动查找变得不可执行。在这种“数据爆炸，知识贫乏” 的大背景下，海量数据依然在不停增长，数据库依旧在不断扩容，如果这些情况 不加以改善，那么人们检索数据的效率将大大降低，人们想要做出任何时效性需 求极强的决策都将成为奢望，数据亦将失去活力，只能被用于处理日常事务，而 无法对事务进行分析总结。因此，作为一种能在海量数据中发现潜在的、有价值 的信息和知识的工具，数据挖掘技术的诞生十分让人期待。从诞生至今，数据挖 掘技术一直是人们研究的热点，目前采用数据挖掘技术作为决策的辅助工具的例 子比比皆是，为人们所熟知的“尿布与啤酒”的例子便是数据挖掘技术的“杰作”。 现如今，数据挖掘以其特有的优越性，越来越多地被应用于各行各业中，也同时 促进了人这一新兴技术的研究与进一步发展。 2 2 数据挖掘技术的定义和特点 从字面上理解，数据挖掘技术就是从海量数据中找出有用的知识【 】。大多数 研究报告认为：数据挖掘技术是指从大量数据中探索出隐含的、先前未知的、潜 在有用的信息的过程1 2 】f 4 1 1 5 1 1 1 7 1 。发现的知识可被用于决策系统的导向，辅助决策系 统做出正确的决策。由此可见，数据挖掘技术的主要特性包括： 1 先知性； 2 有效性； 3 实用性。 2 3 数据挖掘的各类模式 发现模式是数据挖掘的重要任务之一。模式被用于描述数据之间的关联，建 立数据分类的重要标准，判断数据变化的基本预测等。通常情况下，预测性模型 和描述性模型是数据挖掘中按照功能划分的两类模式，预测性模型一般被用于对 数据的推断以及预测，在现有数据的基础上，对数据的发展趋势进行判断，预见 未来数据的动态；描述性模式表现了事务数据库中的数据的一系列特征，包括： 数据结构，数据依赖，数据之问的关联等。而在实际应用中，模式常常被分为以 下几种【1 8 1 ： 1 关联模式 关联模式是通过统计数据库中各元素出现的频率，对各元素的关联程度进行 分析而得出的结论。可以说，关联模式描述了数据之间的出现规律，表现了数据 5 第_ 章数据挖掘技术简介上海师范大学硕士学位论文 之问的潜在联系，是从事务数据库中挖掘出隐含的规律、有价值的知识的重要模 型。 2 分类模式 分类模式是指对数据集中的数据进行分类，将数据逐一映射到某一指定的类 上，以此来预测该类的标记，从而对特殊的问题制定一套分类的规则。分类模式 有很多模型，其中判定树是比较常见的形式，另外还有数学公式、神经网络等形 式。 3 聚类模式 聚类模式是指对一组数据的内在规则进行识别，将具有同种内在规则的数据 划分到同组中，组与组之间的区别尽可能大，而组内数据的差别尽可能小。聚类 模式与分类模式的区别是：在进行数据分析之前，聚类模式没有确定的组，只有 在分析过程完成后，才能得出各组的定义。 4 时序模式 时序模式是指将原来数据集中的数据按照时间进行排列，并在此基础上检索 数据，将数据的改变与时间的推移关联起来，以时间的变化来预测未来数据的趋 势。 5 回归模式 回归模式在现有的数据上推测未来的数据，与时序模式相类似，都是以过去 的数据趋势来预测将来的数据变化，它们的不同之处在于，时序模式更强调时间 的特性，而回归模式所描述的数据规律并没有很强的时效性，它所参照的数据也 并非以时间顺序而排列。 6 序列模式 序列模式与关联模式相似，不同的是序列模式指的是一段时间中项集之间的 联系，并把项集之间的关联与时间的推移对应起来，换句话说，序列模式在一定 程度上，就是某个时间段中的关联模式。 数据挖掘技术中的各种模式为人们提供了多种挖掘途径，针对不同的问题， 人们可以使用不同的模式来挖掘数据库中的信息。当然，在许多实际应用中，通 常会同时采用多种模式对数据进行分析f l9 】，因为各类模式都有各自的特点，解决 问题的方式方法也不经相同。例如，分类模式、回归模式与时序模式都是在结果 已知的情况下建立的，被定义为是受监督的知识；而关联模式、聚类模式以及序 列模式在建立之前，都无法预知结果，也没有先验知识可供参考，所以，这些模 式的建立并不受其它因素监督。 2 4 关联模式的常用研究方法 数据挖掘技术中包含许多方法，其中关联分析是一种主要的分析方法。关联 分析目的在于通过分析、比对事务数据库中的记录，检索出记录中的所有项集， 6 上海师范大学硕士学位论文第_ 章数据挖掘技术简介 并按照一定的规则，筛选出关联度较高的频繁项集，并计算这些频繁项集的置信 度，最终建立一套针对特定问题的项集关联度模型。推导出“尿布与啤酒”这样 令人惊奇的例子使研究者对关联模式愈发感兴趣，目前，研究人员已经提出了多 种关联分析的算法，包括：a p f i o f i 算法、f p 树频集算法、基于划分的算法等。 关联分析过程一般可以分为以下几个步骤【2 0 】： 1 数据预处理 在对数据进行分析之前，应该对所挖掘的数据集进行处理。数据预处理工作 可以分为两个方面：一是去除数据库中记录的“冗余数据”，当然这里的“冗余数 据”指的并不事务数据库中实际存在的冗余数据，而是对数据挖掘过程来说没有 意义的“冗余数据”；二是合并意义接近的数据，将多个数据合理地合并在一起不 仅能是挖掘结果更简洁明了，还能有效地减少候选集产生的数量。数据预处理的 目的是尽可能地精简数据的初始项集，为推出准确的关联模型打下坚实的基础。 2 项集处理 对项集的处理是关联分析过程中最为重要的一个阶段。在此阶段中，不同的 算法采用不同的手段对项集进行处理。如：a p r i o f i 算法中，定义一个最小支持度， 将所有项集的频繁程度与最小支持度相比较，保留频繁度大于最小支持度的项集， 舍弃频繁度小于最小支持度的项集，生成下一级候选集，如此循环，直至产生最 终的频繁项集；而f p 树频集算法则采取“分而治之”的策略，将项集压缩为频 繁树，设置分叉条件库，随后对频繁树作进一步分析，最后得出最终的频繁项集。 3 计算置信度 由于关联规则挖掘技术被用于处理不精确的、模糊的问题，所以关联规则挖 掘导出的数据模型并非绝对可靠，很多情况下，这样的模型只是作为决策系统的 一个参考值而不是决定因素，所以，模型中的结论需要计算其合理性，这种合理 性被称为置信度。置信度使得模型更完备，结论跟严密，置信度的计算也是关联 规则挖掘工作的重要组成。 2 4 1a p r i o r i 算法 a p f i o f i 算法是关联规则中的经典算法。在众多关联规则算法中，a p r i o f i 算法 无疑占据重要地位。a p f i o f i 算法是a g r a w a l 等设计的一个基本算法【2 l 】，算法采用 两阶段挖掘的思想，并基于多次扫描事务数据库来执行。 2 4 1 1 a p r i o r i 算法相关组成 一般情况下，一个相对完整的算法都会由一定的数据形式，数据结构，导出 模式和公式等组成。a p r i o f i 算法流程中，构成算法主体的相关组成部分大致可分 为如下几个元素： 1 项集 1 第二章数据挖掘技术简介上海师范大学硕士学位论文 项集是项的集合，由k 个项组成的项集被称为k 阶项集。项集是a p r i o r i 算法 做关联规则挖掘的对象，即算法的挖掘操作都基于项集的基础上完成，由此可见， 项集是算法执行的最小单位，是关联规则挖掘的最小表达因子。 2 最小支持度和置信度 最小支持度是决定项集是否属于频繁的项集的重要标准。最小支持度反应了 关联规则的应用范围，最小支持度限制得越严格，则最终的关联规则的适用场合 也越宽泛。从某种意义上说，最小支持度反应了模式的潜在有用性，而一个模式 潜在的有用性是定义其兴趣度的一个重要因素，所以最小支持度也是评估用户兴 趣度的重要标准。有的时候，最小支持度也被称为，阀值”，意在表达最小支持度 可以被看作一个临界值，用于区分项集的频繁度。可以说，最小支持度是项集筛 选的严格参照，是最终的关联模型的规划依据。 置信度是另一个重要兴趣度指标。置信度反应了关联规则的准确性，或者说， 是对规则表达结论的客观评估。与最小支持度不同，置信度是在导出最终的关联 模型之后才计算得出的，因为只有最终确定的强关联规则才具有实际意义。通常 情况下，a p r i o r i 算法最终得出的规则都会伴随与之相对应的置信度，这使得算法 推出的最终模型更加严密，也为决策者做出相应决策提供了参考。置信度为1 0 0 或l ，意味着数据分析时，该规则总是对的，这种规则称为准确的。 最小支持度和置信度是两个用户兴趣度度量【2 2 】，它们分别反映了发现关联规 则的有用性和确定性。如果关联规则支持度太小，那么该规则的使用面就很窄； 如果关联规则的置信度过小，该规则就没有很大的意义。 3 频繁项集和候选集 从字面上理解，项集在事务数据库中频繁出现，就被称为频繁项集。项集的 出现频率是决定该项集是否为频繁项集的重要参照。项集的频率是项集在所有记 录中出现的次数与记录总数之比，当该频率达到最小支持度( 阀值) 时，项集就 可被定义为频繁项集。频繁项集的产生并非一蹴而就的，是一个反复迭代的过程。 有时，k 阶频繁项集自连接生成的k + l 阶项集并不是频繁项集( 项集频率小于阀 值) 。 候选集是由频繁项集自连接产生，是有待检验的项集。在算法执行的过程中， 前一阶频繁项集生成后一阶频繁项集的候选集，随后依据最小支持度，去除不符 合条件的候选集，筛选出频繁项集。 其实，在a p r i o r i 算法的迭代过程中，候选集与频繁项集一直在不断地相互转 换，直到导出最终关联模型。候选集与频繁项集的判断依据在于最小支持度，大 于最小支持度的候选集就是频繁的，反之，则不是。 由上述定义可知，候选集和频繁项集都是从项集中衍变而来，是两种特殊的 项集。可以说，项集是候选集和频繁项集产生的基础，候选集和频繁项集则是项 集的子集。 8 上海师范大学硕士学位论文第二章数据挖掘技术简介 综上所述，a p f i o f i 算法的基本构成元素可分为普通项集，候选集，频繁项集， 最小支持度和置信度。其中，普通项集，候选集和频繁项集的定义划分并不明显， 换而言之，普通项集，候选集和频繁项集在整个算法执行的过程中，可能会互相 转换。最小支持度和置信度体现了算法的实用性和确定性，最小支持度规范了算 法筛选频繁项集的机制，置信度则充实了算法的导出规则，一个作用于算法过程 中，另一个则用于描述结果，它们使算法更加健全，也使得算法导出的关联模型 更加具有理论说服力。 a p f i o f i 算法过程中，各构成元素的协作如图2 1 所示。 篱 圈一 图2 ia p r i o r i 算法构成兀素协作图 f i g2 1t h ec o o p e r a t i o nd i a g r a mo f a p d o r ia l g o r i t h me l e m e n t s 2 4 1 2 a p r i o r i 算法的基本思想 a p f i o n 算法把数据挖掘过程分为两个步骤： 1 通过迭代，扫描事务数据库中的所有项集，按照一定的最小支持度，筛选 出所有频繁项集，即淘汰阈值低于最小支持度的项集，保留阀值相对较大 的频繁项集； 2 计算这些频繁项集的置信度。 具体的实现方法是：首先，算法选出所有l 阶项集，并将这些l 阶项集与最 小支持度作比较，筛选出1 阶频繁项集，记为l l ；然后用l l 来生成候选集c 2 ， 将c 2 中的项集与最小支持度进行比较，筛选出2 阶频繁项集l 2 ；如此不断地循 环下去，直到无法发现更多的k 阶频繁项集为止。在此过程中，每当挖掘一层频 繁项集l k ，就需要扫描一遍整个数据库。 由上述算法流程可知，a p f i o d 算法的整个过程由“连接 和“剪枝”两个部 分组成。 1 连接 “连接”步骤是将项集进行自连接，生成下一阶候选集。当然，在此过程中 将产生大量的候选集，其数量将以指数倍的等级增长。在不断的迭代连接过程中， 候选集一直是频繁项集的后备项集，“连接”操作的目的就是生成可能成为频繁的 候选集，为发现最终的频繁项集打下基础。所以，“连接”步骤是a p f i o f i 算法的 9 第二章数据挖掘技术简介上海师范大学硕士学位论文 开始与起步，是最后导出模型的开端。 “连接 步骤的具体实现方法是：通过项集l k - l 与自己连接，产生一个k 阶 候选集的集合，该候选集的集合记作c k ，例如： i i 和1 2 是l k - l 中的项集，执行“连接操作之后，假定1 3 为1 1 和1 2 连接而成 的项集，则1 3 包含了1 1 和l2 中的所有元素。作为l l 和1 2 的超集，1 3 也是c k 中的项 集之一，成为k 阶候选集。 如此循环执行“连接”操作，当所有l k 1 中的项集完成自连接，并生成与之 相对应的所有k 阶候选集c k 时，k 阶项集的“连接”操作完成。“连接”步骤的 主要目的是提供候选集，为“剪枝”步骤做准备。 2 剪枝 “剪枝 步骤的实际意义是去除不符合条件的候选集，生成k 阶频繁项集。 在此过程中，“剪枝”的依据是最小支持度，所谓符合条件的候选集是指那些频繁 度大于最小支持度的候选集，“剪枝”步骤的意义在于精简候选集，推导出更有意 义、更符合实际情况的频繁项集。对项集的“连接”操作，会使候选集大量产生， 所以，“剪枝”对算法结论的准确性和真实性有重大的意义。 “剪枝 步骤的具体实现方法是：在得出k 阶候选集c k 的基础上，对c k 中 的项集进行筛选，对于包含大量候选集的c k 来说，它的成员不一定都是频繁项集， 但所有的频繁k 项集都包含在c k 中，所以对c k 进行“剪枝”操作，能逐渐推导 出真正有用的关联规则。“剪枝”的过程是一个循环迭代的过程，一次“剪枝 过 程就是对候选集进行一次有效地化简，这样，最终推导出的关联规则就更具有实 用价值。 在k 阶“剪枝”的过程中，算法首先将会扫描数据库，确定k 阶候选集的集 合c k 中每个候选项集的计数，并计算各个候选集的频繁度，从而确定k 阶频繁项 集l k 。如果c k 很大，所涉及的计算量就很大。 最小支持度( 阀值) 是“剪枝”操作的一个重要指标，而候选集的频繁程度 也是判断该候选集是否频繁的关键因素，候选集频繁度的计算公式如下： s u p p 训似) ：! 丝丝螋、。 s u p p o r t _ c o u n t ( i t e m ) 作为a p f i o f i 算法中的两大关键步骤，“连接”与“剪枝”操作的关系十分紧 密。“连接”操作是为了给“剪枝”操作提供大量的候选集，而“剪枝”又是为了 给“连接”操作提供有待深入挖掘的频繁项集。两者密不可分，缺一不可。 在最后一次“剪枝 操作执行完成之后，为得出更加完整的关联模型，算法 将计算每条关联规则的置信度，具体公式如下： c 。f i d e n c e ( ajb ) = 尸( 爿ib ) = 兰号笔暑羹i 群 1 0 上海师范大学硕十学位论文第二章数据挖掘技术简介 2 4 1 3a p r i o r i 算法举例 现有事务数据库如表2 1 所示， 算法执 骤： 第 扫描数 的每条 t a b l e2 1t h ei n s t a n c eo ft r a n s a c t i o nd a t a b a s e 表2 1 事务数据库实例表 事务i d购买商品 0 0 1 a ，b ，d ，g ，1 0 0 2 a ，b ，c ，d ，e ，h ，j 0 0 3 a ，b ，c ，e ，f 0 0 4 a ，b ，d ，k ， 行 步 一步： 据库中 记录， 将商品看作项，对每个项的出现次数进行统计。 第二步：依照最小支持度，确定1 阶频繁项集l l 。 第三步：将l l 与l l 进行连接，得出2 阶候选集c 2 ，扫描记录，计算每条候 选项的频繁度。按照最小支持度的限制，求出2 阶频繁项集l 2 第四步：继续重复上述步骤，知道多的频繁项集l k 为空，则k 一1 阶频繁项集 l k 1 即为最终的频繁项集。 算法的执行过程如图2 3 所示， 项集频繁度 a1 0 0 b1 0 0 c5 0 d7 5 e 5 0 f2 5 g2 5 h2 5 i2 5 j2 5 k2 5 按最小支项集 持度6 0 生成 a b 项集频繁度 筛选频繁 a1 0 0 候选集 a ，d 项集l lb1 0 0 b d 计算频繁度 项集频繁度 a b1 0 0 a d7 5 b d7 5 得出 最终 频繁 项集 i 项集 频繁度 a , b ，d 7 5 图2 3a p r i o r i 算法执行过程实例 f i g2 3t h ep r o c e s so fe x e c u t i o no f a p r i o r ia l g o r i t h mi n s t a n c e 最终得出一个频繁项集 a ，b ，d ) ，计算该强规则的置信度，如表2 2 所示： t a b l e2 2t h ec a l c u l a t i o no fc o n f i d e n c e 第二章数据挖掘技术简介上海师范大学硕士学位论文 表2 2 置信度的计算 规则置信度 a 八b d 7 5 a 八d b 1o o b 八d ，a1 0 0 a b 八d7 5 b a 八d 7 5 d a 八b1 0 0 2 4 2s e t m 算法 h o u s t s m a 等人提出的s e t m 算法【2 3 】对a p r i o r i 算法中生成的候选集进行了精 简，针对a p r i o r i 算法中生成大量候选集的缺陷，根据a p r i o r i 性质，在对k 阶候选 集进行筛选之前，s e t m 算法首先判断候选集中的元素是否出现在k 1 阶候选集中， 在这个过程中，很多k 阶候选集将被删除。由此，在候选集生成的阶段，s e t m 算 法会比a p r i o r i 算法的执行效率更高。但是，候选集中的元素出现的概率并不是确 定的，如果i j 一阶与后一阶的候选集元素相当，s e t m 算法的改进效率也很难体现。 2 4 3d h p 算法 p a r k 等人提出的d h p 算法1 2 4 弓i 入h a s h 技术来生成频繁2 项集。在产生侯选 项集时，采用哈希技术去除不满足条件的项集，在产生候选2 项目时，算法的执 行效率很高，很好地解决了处理过程的性能瓶颈。但采用h a s h 技术，d h p 算法对 存储空间的花费也较大。 2 4 4f p g r o w t h 算法 h a n 等人提出的不生成候选集直接生成频繁模式f p g r o w t h 算法【2 5 】将生成的频 繁项集压缩成一棵频繁数，以设定的条件对项集进行划分，最后得到关联模型。 f p g r o w t h 算法的最大优点莫过于在算法的执行过程中，只需扫描一次数据库，从 而大大降低了因扫描数据库而花费的时间。当然，f p g r o w t h 算法中频繁树的建立 相对比较复杂，另外，对于大型数据库，算法构成的频繁树也很庞大，不易实现。 2 5 本章小结 本章简要地介绍了数据挖掘技术的相关背景，并结合数据挖掘的相关定义和 概念，突出了关联规则挖掘的现实意义。随后本章对关联规则挖掘中的经典算法 a p r i o r i 算法进行了详尽地描述，并举例分析了a p r i o r i 算法的步骤以及特点。 最后本章介绍了一些其它常用的关联规则算法，将它们与a p r i o r i 算法进行简单地 比较。 1 2 上海师范大学硕士学位论文第三章粗糙集理论方法研究 第三章粗糙集理论方法研究 3 1 粗糙集理论方法的产生和发展 人类文明的进程是一个知识探索的过程，从无知到文明，人们一直在不断摸 索自然界的规律，在此过程中，由于对于某些新事物的不了解，人们时常会处理 一些不确定的因素。现如今，数据量的增长已经远远超出了人们对信息的需求量， 但模糊问题依旧存在，这是因为信息量陡增带来了许多无用的、无意义的信息， 而真正有价值的信息也掺杂于其中，使得发现有用的信息变得十分困难，也使模 糊问题变得更不确定。由于存在各种不确定性和不精确性，关于策略的信息也经 常是模糊的，这直接影响到了决策者的判断，从而制约策略的正常制定和实施。 所以，在信息量骤增的今天，人们急需一种能有效处理模糊的、不确定的问题的 工具。 1 9 8 2 年，z p a w l a k 提出了粗糙集理论方法【2 6 】。在处理决策分析问题的时候， 经常涉及模糊的、不精确的决策信息，这可能使最终决策的制定造成偏差【2 7 】。利 用粗糙集理论方法，能在模糊问题的处理上，推导出更有效、更精确、更有说服 力的数据模型。随着粗糙集理论方法同趋成熟，该理论不仅提供了分析指导方法， 而且利用决策规则形式模型可以为决策者提供决策支持【2 8 】。 3 2 粗糙集理论方法相关概念 1 知识与分类 知识被认为是使用等价关系集尺对离散表示的空间u 进行划分，而知识就是 r 对u 划分的结果【2 9 】。传统意义上，知识是指经过人的思维整理过的信息、数据、 形象、意象、价值标准以及社会的其它符号产物- 。可以说，知识是人类在改造客 观世界的实践中所获得的认识和经验的综合，是人们对自然科学规律的总结，是 指导人们实践工作的理论依据。 在粗糙集理论方法看来，知识是将现实的或抽象的对象进行分类的能力f 3 0 】。 因此，任何客观事物都能有相关的知识来描述，也就是说知识对于客观事物具有 表达能力。根据相应的知识，可以对事物进行分类1 3 1j 。 2 不可分辨关系和基本集 自然界中，属性相差不大的事物通常会被归于同一类，而它们之间的关系就 是不可分辨关系。也就是说，具有相同属性的同一类事物之间是不可分辨关系。 作为事物分类的准则，不可分辨关系将同属性的事物视为同类，实际上完成了对 客观事物的归类工作。不可分辨关系在粗糙集理论方法中的地位十分重要，它揭 示出知识的颗粒状结构，是定义其它概念的基础【3 2 】。 定义3 1 给定一个论域u 和u 上的一簇等价关系s ，若p g ，且p cg ，则 1 3 第三章粗糙集理论方法研究上海师范大学颂十学位论文 np ( p 中所有等价关系的交集) 仍然是论域u 上的一个等价关系，称为p 上的不 可分辨关系，记为i n d ( p ) ，也简记为p 。而且， v x u ，防】i n d ( 尸) = m 尸= n 【x 尺 基本集的定义是由论域中相互间不可分辨的对象组成的集合，是组成论域知 识的构成元素1 3 3 1 。基本集是不可分辨关系划分下的基本元素的集合，被不可分辨 关系划分为同一类事物的集合被视为基本集。由此可见，不可分辨关系可被认为 是一种等效关系，它将事物分割成一系列的基本集。 3 边界 粗糙集理论方法将一些无法确认的元素都归属于边界域。边界集中了一些不 能被不可分辨关系所识别