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

哈尔滨工程大学硕士学位论文 摘要 数据挖掘是从存放在数据库、数据仓库或其它信息库中的大量数据中挖 掘有用知识的过程。它是一个新兴的边缘学科，其应用领域非常广泛，并且 具有良好的应用前景。它包含关联规则挖掘、预测、分类、聚类、演化分析 等多种技术手段，其中关联规则挖掘是一种主要的也是用途最广的数据挖掘 方法。 为了知识的关联性，本文首先对k d d ( k n o w l e d g ed i s c o v e r y i n d a t a b a s e s ，数据库中的知识发现) 、数据挖掘( d a t am i n i n g ) 和关联规则 ( a s s o c i a t i o nr u l e s ) 等概念也作了阐述，为深入讨论作了充分的准备。在对 现有关联规则文献的研究基础上，详细的介绍了关联规则的基本概念和基本 性质，并且对关联规则的典型频繁集挖掘算法a p r i o r i 算法、a p r i o r i i i d 算法 及f p - c , r o w t h 算法进行了归纳、分析和研究，为a p r i o r i 改进算法的提出和构 造建立了理论上的必要性前提。 本文的重点是a p r i 嘶改进算法的设计和分析研究。考虑a i ，r i 0 i i 算法中 频繁项目集生成的瓶颈问题，一方面，利用哈希树来存储数据项集，以实现 对候选项目集的快速计数。另一方面，从理论上论证了减小候选集q 的大小 对提高整个算法效率有着明显的贡献。此外还提出了一种新的关联规则挖掘 算法。将老算法和改进算法进行比较后，充分的说明了改进算法的性能优势。 关键词：数据挖掘；关联规则；a p r i o r i 算法；频繁集 哈尔滨工程大学硕士学位论文 a b s t r a c t d a _ bm i n i n gi st h ep r o c e 豁t h a tw h i c hm 硫st h eu s e f i l lh o w l e d g c 舶mt h e 出妞w h i c hs t o r e di n 纰b a s e 。t h e 加w 孤c h o u s e0 f 血。山e fi n f o r m a t i o ns t o 螨i t j s 蛆e m 盯g i n gc d g cd i s e i p l i n c ，i 乜a p p u f i o nd o m a i ni sc x 仃c m c l y 研d e s p 碍a d a n dh a s 恤cg o o da p p 融t i 佃p r o s p e c tnc o n t a i n sm cn s s o c i a f i o nm l cm i n i n g ，m c f o r e e a s t ，t h ce l a s s i f i c a f i o n , g a t h e r sl 【i n 正t h e 钾o l v c da n a l 螂a n dm a n yo t l a 盯 k i n d so ft c e l m i c a lm c - t h o d , t h ea s s o e i a f i m l cm i n i n gi so n e0 ft l a cm o s t i m p o r t a n tk i n da n da l s oi sn s c db r o a d c s t f o r 曲峙k n o w l 酣g c 曲t e d n e s s , t h i sa r t i e l cf i r s tm t r o d u c 燧s 哪cc o n c e p t s a b o u tk d d ( k n o w l e d g ed i s c o v e r yj nd a t a b a s c s ) ，d a t am i n i n ga n dt h e a s s o e i a t i o l lr u l e sa n d o nt om a k et h ef u l l e p a m t i f o rt h ct h o m u g h d i s c u s s i o n nt h i n t r o d u c e sl h eb 舾i c 咖c c p ta n dm t u r e 缸& t a i la b o u tt h c a s s o c i a t i o nn l l 器恤t h e 坞s c a r e ho ft h ee x i t i n ga s s o c i a t i o n 邢l 嚣笛w h i l c 撼 s m m a l j e $ , a n a l 螂a n d r c s c a r c h 嚣t h ea p l i o , i a l g o f i t l a m , t h ea , p f i o r i d a l g o f i t h n la n dt h ef p - c , r o w t ha l g o r i t h m , w h i c hh a s 龉t a b l i s h 。dt h c 岫r e f i e a l l y n e c e s s a r y 雕m i t op r o p o s et h ea p r i o f ii m p r o v e m ta l g o f i t l a m t h ek c yp o i n to ft h i sa r t i c l ei st h ed e s i g i 删肌a n dt h ea n a l y s i sr c s c 觚c h 伽 a p r i o r ii m p m v e m e n ta l g o f i t l u n o n 璐i d c i i n gt h eb o m c n c c bi nt h ea 4 , r i o r i a 1 9 0 r i t h m ，o nt h e ch 柚d ，i ts a v 髂t h ed a t ai t e ms e t 璐i l l gt h eh a s h 柚t o 托a l i z c f a s tc o u n t i n gt ot h ec a n d i d a t ei t e m s e t s o nt h eo t h e rh 柚正i tp r o v c dt h a ty o uc a l l 锄h a n t h e 训坨a l g o f i t h me 蚯c i c n c yb yr 酣u c i n gt h es i z e0 fc a n d i d a t c 捃 t h c o d 删y ha d m t i 叫“p r o p o s e do n ek i n do fn e wi m p r o v c m e n ta s s o c i a t i o n m i em i n i n ga l g o r i t h m t h e m p a r i s o no ft h en e w a l g o f i t h m 诵t ht h eo l d 咖c 哈尔滨工程大学硕士学位论文 s t a t e dt h ep 耐o r m a n c es u p e r i o r i t yi nt h ei m p r o v e m e n t a l g o r i t h m 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 ；a p r i o r ia l g o r i t h m ；f r e q u e n ts e t 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：盔描羞 日期：0 年7 月文，日 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 课题的目的及意义 如今是一个网络化的时代，通信、计算机和网络技术正改变着整个人类 和社会，最明显的是在这些技术的帮助下人们产生和收集数据的能力迅速提 高了。然而，网络化时代同时也出现了一大堆新的问题：诸如信息过量、难以 消化；信息真假难以辨识；信息安全难以保证；信息形式不一致，难以统一 处理等等。如何理解已有的历史数据并用以预测未来的行为，如何从这些海 量数据中发现信息，变被动的数据为主动的知识，如何快速、准确地获得有 价值的信息，指导政府和企业决策，获取更大的经济效益和更好的社会效益， 都迫使人们去寻找新的、更为有效的数据分析手段对各种“数据矿藏”进行 有效的挖掘以发挥其应用潜能。 一门新兴的自动信息提取技术：数据挖掘和知识发现( d a t am i n i n ga n d 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 s ) 正是在这样的需求背景下应运而生了m 。 关联规则挖掘是数据挖掘研究的一个重要分支，关联规则是数据挖掘的众多 知识类型中最为典型的一种关联规则挖掘可以发现存在于数据库中的项目 ( i t e m s ) 或属性( a t t r i b u t e s ) 间的有趣关系，这些关系是预先未知的和被隐 藏的，也就是说不能通过数据库的逻辑操作( 如：表的联接) 或统计的方法 得出。这说明它们不是基于数据自身的固有属性( 例如函数依赖关系) ，而是 基于数据项目的同时出现特征，所发现的关联规则可以辅助人们进行市场运 作，决策支持及商业管理，网站设计等。关联规则是由r a g r a w a l 等人首先 提出的，它的一个典型例子就是：“9 0 的客户在购买面包的同时也会购买牛 奶”，其直观意义为顾客在购买某些商品的时候有多大的倾向会购买另外一些 商品1 2 1 。 哈尔滨工程大学硕士学位论文 数据挖掘是一个非常广泛的研究领域，包含方方面面的不同内容。本文 只是选择了其中几个比较重要的也是作者比较感兴趣的问题进行研究论述， 主要旨在做如下工作 1 在国内外大量相关文献资料的基础上，对数据挖掘和关联规则挖掘的 基本概念、研究现状及所面临的挑战等问题进行了归纳总结 2 研究了几种典型的关联规则挖掘算法，并比较了它们各自的优缺点及 适用范围。 3 对现有的关联规则挖掘算法，提出改进方法，并证明。 1 2 国内外研究现状及进展 数据挖掘语言的设计，高效而有用的数据挖掘方法和系统的开发，交互 和集成的数据挖掘环境的建立，以及应用数据挖掘技术解决大型应用问题， 都是目前的研究和开发热点，下面描述的是一些数据挖掘的应用趋势： 1 应用的探索：早期数据挖掘应用主要集中在帮助企业提升竞争能力， 随着数据挖掘的日益普及，数据挖掘也日益探索其它应用范围，如生物医学、 金融分析和电信等领域。随着电子商务和电子市场逐渐成为零售业的主流因 素，数据挖掘也在不断扩展其在商业领域的应用面。 2 可伸缩的数据挖掘方法：与传统的数据分析方法相比，数据挖掘必须 能够有效地处理大量数据，并尽可能是交互式的；由于数据量是在不断的激 增，因此针对单独的和集成的数据挖掘功能的可伸缩算法显得十分重要。一 个重要的方向是基于约束的挖掘，它致力于在增加用户交互的同时如何改进 挖掘处理的总体效率。 3 数据挖掘与数据库系统、数据仓库和w e b 数据库系统的集成：事务 处理、查询处理、联机分析处理和联机分析挖掘应集成在一个统一框架中， 这将保证数据的可获得性，数据挖掘的可移植性，可伸缩性，高性能，以及 2 哈尔滨工程大学硕士学位论文 形成对多维数据分析和探查的集成信息处理环境。 4 数据挖掘语言的标准化：标准的数据挖掘语言或其它方面的标准化工 作将有助于数据挖掘的系统化开发，改进多个数据挖掘系统和功能问的相互 操作，促进数据挖掘系统在企业和社会中的教育和使用。 5 可视化数据挖掘：可视化数据挖掘是从大量数据中发现知识的有效途 径系统研究和开发可视化挖掘技术将有助于推进数据挖掘成为数据分析的 基本工具 6 复杂数据类型挖掘的新方法：复杂数据类型挖掘是数据挖掘中一项重 要的前沿研究课题，虽然在地理空问挖掘、多媒体挖掘、时序挖掘、序列挖 掘以及文本挖掘方面取得了一些进展，但它们与实际应用的需要仍存在很大 距离。对此需要进一步的研究，尤其是针对上述数据类型的现存数据分析技 术与数据挖掘方法集成起来的研究 7 w e b 挖掘：由于w e b 上存在大量信息，并且w e b 在当今社会扮演越 来越重要的角色，有关w e b 内容挖掘、w e b 日志挖掘和因特网上的数据挖掘 服务，将成为数据挖掘中一个最为重要的子领域。 8 数据挖掘中的隐私保护与信息安全：随着数据挖掘工具和电信与计算 机网络的日益普及，数据挖掘面对的一个重要问题是隐私保护和信息安全 需要进一步开发有关方法，以便在适当的信息访问和挖掘过程中确保隐私保 护与信息安全。 1 3 课题的主要工作及论文组织 1 3 1 本课题的主要工作 本课题的主要研究内容是关联规则挖掘算法。通过对国内外取得的一些 成果进行研究和分析，并在借鉴前人成果的基础上，针对目前关联规则挖掘 3 、 哈尔滨工程大学硕士学位论文 算法研究和运用中遇到的一些问题提出改进的方法。故课题的主要工作是： 1 充分研究与分析常用的关联规则算法及相关的已有的改进措施的各自 优缺点 2 在此基础上，针对于频繁项目发现算法的两个瓶颈问题，提出一些新 的、有效的解决措施，以提高算法效率具体改进措旄可从以下几个方面着 手： ( i ) 在数据库扫描方面，由算法自适应确定扫描次数，以减少数据库扫 描次数。 ( 2 ) 在求候选项目集的支持度时，通过减少数据库记录长度的方法，有 效降低事务记录的子集个数，以提高算法的效率 ( 3 ) 利用哈希表来存储数据项集。 3 结合自己提出的改进措施并综合已有改进措施的优点，给出一种新的 关联规则挖掘算法 4 利用实例验证自己提出的新的关联规则挖掘算法。 1 3 2 论文的组织 本论文共分为五章。第1 章绪论，介绍了本课题的研究目的和意义及本 课题目前国内国际的研究动态。第2 章数据挖掘技术研究，介绍了数据挖掘 的相关理论与技术，包括数据挖掘的定义、数据挖掘的分类与方法、数据挖 掘的体系与步骤、数据挖掘的相关技术以及关联规则挖掘的基本概念等第 3 章关联规则的经典频繁集算法介绍了关联规则的挖掘过程及典型的频繁项 目集发现算法_ _ a 州面算法。第4 章，关联规则算法研究介绍a p f i o r i t i d 算法和另一种不产生候选项的f p - c , r o w t h 算法。第5 章关联规则的若干改进 算法，介绍了两种a p r i o r i 算法的改进算法，并提出了一种新的算法。 4 哈尔滨工程大学硕士学位论文 第2 章数据挖掘技术研究 2 1 数据挖掘的概念 计算机与信息技术经历了半个世纪的发展，给人类社会带来了巨大的变 化与影响，人们能够以更快速、更容易、更廉价的方式获取和存储数据，这 就使得数据及其信息量以指数方式增长。据估计，一个中等规模企业每天要 产生1 0 0 m b 以上来自各生产经营等多方面的数据。由于这些数据十分繁杂， 如何有效的利用这些数据，从这些数据中发现有价值的信息或知识，达到为 决策服务的目的，就成了一项非常艰巨的任务 简单地说，数据挖掘就是从大量的数据中提取或者“挖掘”知识在许 多场合下，数据挖掘又被称为数据库中的知识发现嘲( 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 ，简称k d d ) 但是，更科学的说法是将数据挖掘视为数据库知识 发现的一个基本步骤 从1 9 8 9 年到现在，k d d 的定义随着人们研究的不断深入也在不断完善， 目前比较公认的定义是f a y y a d 等给出的：数据挖掘是从数据集中识别出有效 的、新颖的、潜在有用的以及最终可理解模式的高级处理过程h 。数据挖掘 是一门很广义的交叉学科，它汇聚了不同领域的研究者，尤其是数据库、人 工智能、数理统计、可视化、并行计算等方面的学者和工程技术人员嘲。 在这种情况下，数据库的知识发现过程如图2 1 所示，由以下几个步骤 组成。 ( 1 ) 数据清理：消除噪声或者不一致数据。 ( 2 ) 数据整合：多种数据源可以组合在一起。它和数据清理一起被视为 预处理步骤，结果数据存放在数据仓库中。 ( 3 ) 数据选择：从数据库中检索与分析任务相关的数据。 哈尔滨工程大学硕士学位论文 ( 4 ) 数据变换：将数据变换或统一成适合挖掘的形式，如通过汇总或聚 集操作在有些场合下，数据变换在数据选择过程之前进行，特别是在数据 仓的情况下 ( 5 ) 数据挖掘：使用智能方法提取数据模式。 ( 6 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式。 ( 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。 卜一赣嚣准备十赣霸恕嚣十秤毽嶷示 l 螂 ， i k 旷曩式 膏鼍萄彩 l _ 岷， 毒；| ，_ 图2 1 数据挖掘的过程 2 2 数据挖掘的体系结构 尽管将数据挖掘视为数据库知识发现过程的一个基本步骤更为科学，但 是在产业界、媒体和数据库研究界，将数据挖掘直接当作数据库中的知识发 现更为流行。因此数据挖掘有了一个更加广泛的概念：数据挖掘是从存放在 数据库、数据仓库或其他信息库中的大量数据中挖掘有趣知识的过程。 基于这种观点，一个典型的数据挖掘系统可以由以下几个主要成分组成 6 哈尔滨工程大学硕士学位论文 ( 如图2 2 所示) 。 图2 2 数据挖掘系统的典型结构 要指出的是，数据挖掘技术从一开始就是面向应用的它不仅是面向特 定数据库的简单检索查询调用，而且要对这些数据进行微观、宏观的统计、 分析、综合和推理，以指导实际问题的求解，企图发现事件间的相互关联， 甚至利用已有的数据对未来的活动进行预测这样一来，就把人们对数据的 应用，从低层次的末端查询操作，提高到为各级经营决策者提供决策支持。 这种需求驱动力，比数据库查询更为强大。 2 3 数据挖掘常用技术及应用 2 3 1 数据挖掘常用的技术 常用的技术有： 1 人工神经网络：仿照生理神经网络结构的非线形预测模型，通过学习 7 哈尔滨工程大学硕士学位论文 进行模式识别。 2 决策树：代表着决策集的树形结构。 3 遗传算法：基于进化理论，并采用遗传结合、遗传变异、以及自然选 择等设计方法的优化技术。 4 近邻算法：将数据集合中每一个记录进行分类的方法。 5 规则推导：从统计意义上对数据中的“如果那么”规则进行寻找 和推导。 采用上述技术的某些专门的分析工具已经发展了大约十年的历史，不过 这些工具所面对的数据量通常较小，而现在这些技术已经被直接集成到许多 大型的工业标准的数据仓库和联机分析系统中去了。 2 3 2 数据挖掘的应用 数据挖掘的应用十分广泛，各个领域在k d d 应用上既有相同之处，又 有各自不同的独特地方。以下是数据挖掘技术的一些典型应用领域： 1 科学应用 在科学研究中，需要分析各种大量的实验或观测数据，如观测卫星、遥 感器、d n a 分子技术等，传统的数据分析工具效率较低甚至无能为力，因此 必须有强大的智能型自动数据分析工具才行1 9 1 。 2 市场销售 是数据挖掘技术应用最早也是最重要的领域。主要功能是：市场定位， 消费者分析，预测销售趋势，优化营销策略，分析库存需求，识别顾客的购 买行为模式，协助货架布置，制定促销活动时间，促销商品组合以及了解滞 销和畅销商品状况等商业活动 3 金融 典型的金融分析领域有投资评估和股票交易市场预测，分析方法一般采 8 哈尔滨工程大学硕士学位论文 用模型预测法 4 欺诈甄别 分析银行或保险客户的要求和信誉，识别欺诈行为，如恶性透支等。 5 i n t c m e t 的应用 目前这方面的研究主要有两个方面：研制新的更好的索引系统、利用已 有索引系统或搜索引擎开发高层次的搜索或发现系统。相比之下，后者的研 究更为活跃。 随着数据挖掘技术水平不断地提高以及其相关领域的继续发展，数据挖 掘的应用前景将会越来越广阔。 2 4 关联规则挖掘的研究现状 目前，数据挖掘的主要研究领域为数据总结、分类、聚类、关联规则等 方面关联规则表示数据库中一组对象之间某种关联关系的规则。关联规则 挖掘技术迎合了商品零售决策者的需要，于1 9 9 3 年被a g r a w a l 等人提出，其 最初动机是从事务数据库中发现关于顾客购买行为方面的知识，以指导商品 销售部门进行商品摆放、组合促销和市场规划等工作，挖掘出的知识用关联 规则的形式表达出来。 例如，关联规则可以表示为“购买了项目a 和b 的顾客中有9 0 的人又 买了c 和d ”。从这些规则可找出顾客购买行为模式，可以应用于商品货架 设计、生产安捧、针对性的市场营销等。采用关联模型比较典型的例子是“啤 酒和尿布”的故事。在美国，一些年轻的父亲下班后经常到超市去买婴儿尿 布，超市经过对顾客的购物信息进行挖掘，发现在购买婴儿尿布的年轻父亲 中，有3 0 - 4 0 的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿 布和啤酒放在一起。结果是：销售额明显增加了 由于关联规则挖掘可以发现用传统的人工智能和统计方法无法发现的项 9 哈尔滨工程大学硕士学位论文 与项或属性与属性问的关系规律，因此具有重要的研究价值。同时它也满足 了人们从大规模数据存储中获取知识的迫切需求。许多大学的研究机构和学 者对该领域的发展做出了重要贡献，如加拿大s i m o nf r a s e ru n i v e r s i t y 大学的 j i a w e ih a n ，比利时赫尔辛基大学的m a n n i l a ，t o i v o n n e n 等都是数据挖掘研究 的著名专家，它们的许多工作都是在该领域中具有奠基性的旧近年来，国 内的关联规则挖掘研究也正逐渐掀起高潮，出现了一批相关的科研项目，在 算法和应用方面取得了一些具有扩展性或突破性的研究成果嗍。 2 5 本章小结 本章主要研究了数据挖掘的基本概念。数据挖掘的过程，包括数据清洗、 数据整合、数据选择、数据变换、模式析取、结果评价、知识表示。一个典 型的数据挖掘系统，其组成包括数据库或数据仓库服务器、知识库、数据挖 掘引擎、模式评估模块、图形用户界面。其次还有关联规则的基本概念，所 涉及到的术语的定义，关联规则挖掘主要研究哪些方面的问题，按照不同的 方法对关联规则分类，关联规则可分为布尔型和数值型关联规则，单维和多 维型关联规则，以及单层关联规则和多层关联规则，同时也了解了关联规则 数据挖掘的现状，明确了研究方向。 哈尔滨工程大学硕士学位论文 第3 章关联规则的经典频繁集算法 3 1 关联规则挖掘问题描述 、关联规则挖掘问题是采用形式化描述来说明的，具有通用意义，具体为： 设i = i 1 ，i 2 ，k ) 是m 个不同的项组成的集合。给定一个事务数据库d ，其 中的每一个事务t 是l 中一组项的集合，即砸了，每个t 有唯一的标识符t i d 。 若项集) 0 9 且瑶r ，则称事务t 包含项集x 。关联规则是形如x 号y 的蕴 涵式，其中) g ，y g ，且x f i y = o 。若关联规则) 【号y 成立还应具有以下 两个标志参数：支持度s ，即事务数据库d 中至少有s 的事务同时包含x 和y 中的所有项；置信度c ，即在事务数据库d 中包含x 的事务至少有c 同时也包含y l a t 在x 号y 中，x 被称为规则前件，y 被称为规则后件，其 中的x 和y 均可以由合取表达式构成。 定义3 1 项集x 的支持度s u p p o r t ( x ) 是包含项集x 的事务t 在事务数 据库d 中出现的次数和d 中事务总数的比率，即： s t l p p o l t ( x ) = i t e m ，且x 印 t e m ，i 定义3 2 规则x 号y 的支持度s u p p o r t ( x o y ) 是d 中事务包含x u y ( 即x 和y 二者) 的百分比，它是概率p ( x o y ) ，即： s u p p o r t ( x 号y ) = p ( x u y ) = s u p p o r t ( x u y ) 定义3 3 规则x ： y 的置信度c o n f i d e n c e ( x o y ) 是d 中包含x 的事务 同时也包含y 的百分比，它是条件概率p ( y l x ) ，即： c o n f i d e n c e ( ) p y ) = p ( y ix ) ：s u p p o r t ( x u y ) s u p p o r t ( x ) 定义3 4 大项集是指支持度超过用户定义的最小支持度阈值m i n s u p 的 非空项集的集合，记为k ，代表长度为k 的大项集的集合，即： l f x l x c i ，且s u p p o r t ( x ) ，- m i n s u p 1 1 哈尔滨工程大学硕士学位论文 定义3 5 同时满足最小支持度阈值( m i n s u p ) 和最小置信度阈值 ( m i n c o n f ) 的规则称作强规则。 为方便，常用o 和1 0 0 之间的值而不是用0 到1 之间的值表示支持度 和置信度。最小支持度阈值和最小置信度阈值的大小一般由领域专家设定。 项的集合称为项集包含k 个项的项集称为l 项集。所有的大项集表示 为l ( l = l 1 u i - 2 u u k ) ，其中k 是最长大项集的长度。项集的出现频率 是事务数据库d 中包含项集的事务数，也可称为项集的频率或支持计数。项 集满足最小支持度m i n s u p ，是指项集的出现频率大于等于m i n s u p 与d 中事 务总数的乘积如果项集满足最小支持度，则称它为频繁项集。 根据以上定义，可以有如下性质： 性质3 1 如果) 【，z 是项集，且硷【，则s u p p o r t ( z ) ，s u p p o r t ( x ) 。 性质3 2 设x 是大项集，z 是项集，如果z ( = ) ( ，则z 也是大项集。 性质3 3 设x 是小项集，z 是项集，如果) 延z ，则z 也是小项集。 3 2 关联规则挖掘的步骤 关联规则挖掘的任务就是在事务数据库d 中找出具有用户给定的最小支 持度m i n s u p 和最小置信度m i n c o n f 的强关联规则。强关联规则) - y 对应的 项集x u y 必定是频繁项目集，而频繁项目集x u y 导出的关联规则x 号y 的置信度又可由频繁项目集x 和x u y 的支持率计算i 埘。因此，关联规则挖 掘可分解为两个子问题： ( 1 ) 根据最小支持度阈值找出数据集d 中所有频繁项目集； ( 2 ) 根据频繁项目集和最小置信度阈值产生所有关联规则【坍。 综上所述，关联规则挖掘的基本过程可用图3 1 表示，其中d 为数据集， a l g o r i t h m - 1 为频繁项集的搜索算法，a l g o r i t h m 2 为关联规则的产生算法，r 为挖掘出的关联规则集合。用户通过指定最小支持度阈值( m i n s u p ) 和最小 哈尔滨工程大学硕士学位论文 置信度阈值( m h l c o n f ) 分别与算法a l g o r i t h m 一1 和a l g o r i t h m 一2 交互，并通 过与r 的交互对挖掘结果进行解释和评价。 图3 1 关联规则挖掘的基本步骤 3 3 关联规则挖掘中的频繁集算法 设l - a l ，a z ，a m ) 是项的集合，事务数据库d = - 其 中每个事务t i ( i e 1 n ) ) 是l 中项的集合，使得t 包含在i 中每一个 事务有一个标识符，称作t i d 设模式a 是一个项集，a 的支持度( 或者发 生频率) 就是d 中包含a 的事务的个数。如果a 的支持度不小于预先设定 的最小支持度阙值，则称它为频繁模式( f r e q u e n tp a t t e r n ) 给定一个事务数 据库和一个最小支持度阈值，挖掘所有的频繁模式的问题就称之为频繁模式 挖掘问题，也称为频繁集挖掘问题。 不论关联规则算法有多少，都可以归纳为两类。一类是产生频繁项集候 选项的算法，另一类是不产生候选项的算法。其中对于这两类关联规则算法 最具有代表性的分别是a p f i o r i 和f p - g r o w t h 算法。对它们的深入分析、研究 在进行关联规则挖掘中具有非常重要的作用，它们可谓是关联规则挖掘的基 石 a g r a w a l 等人在1 9 9 3 年设计了一个基本算法，它通过使用递推的方法生 成所有频繁项目集，即著名的a 州耐算法 哈尔滨工程大学硕士学位论文 3 3 1a p r i o r i 算法 1 p r i o r i 算法的基本思想 主要就是利用a p r i 砸性质：“频繁项e l 集的任何子集也一定是频繁的。” 将满足给定支持度的所有1 频繁项的每种组合作为产生频繁项的候选项，再 对它们进行修剪，判断其支持度是否大于给定值，这样递推得到最后的频繁 集嘲。 2 p r i o r i 算法 算法3 1 a p r i o r i 算法 输入：事务数据库d ，最小支持度阈值m i n s u p 。 输出：d 中的频繁项集l 处理流程： ( 1 ) l l = l a r g el - i t e m s e t s 发现1 - 项集 ( 2 ) f o r ( 1 【= 2 ；i t 1 o ；k + + ) ( 3 ) c a r = a p r i o r i - g e n ( i t - 1 ) ；，新的候选集 ( 4 ) f o re a c ht r a n s a c t i o n s t e d ( 5 )g - - s u b s e t ( q ，t ) ；$ 务t 中包含的候选集 ( 6 )f o re a c hc a n d i d a t e sc e g ( 7 ) c c o u n t + + ； ( 8 ) k c q b 咖t 倒m i n s u p ( 9 ) 咖l = u 山 p r o c e d u r e a p r i o r i - g e n ( k 1 ) ( i ) f o r e a c h p e k l ( 2 )f o re a c hq k l ( 3 )i f ( p i t e m l = q i t e m l ) a ”：a ( p i t e m k 2 = q i t e m k 2 )a ( p i l e m k 1 = q i t e m k 1 ) 1 4 哈尔滨工程大学硕士学位论文 ( 4 ) c = p e q ；连接两个项集 ( 5 )征h a s l n 矗e q u e n t - l t e m s e t ( c ，k 1 ) ( 6 ) d e l e t ec ；除去不能产生频繁项集的候选集 (7)dseq=qu c ( 8 ) ( 9 )r e t u r n q p t ( n 剃i t l r e h a s - i n f t e q u e n t - i t e m s e t ( c ，l k _ 1 ) ( 1 )f o r e a c h ( k - 1 ) s u b s e ts o f c ( 2 ) i f s 鳓l t 1r e t u r nt r u e ；e l s er e t u i n 邮e a p i i o a 算法可以产生相对较小的候选项目集，扫描数据库的次数由最大 频繁项目集的项目数决定因此，该算法适合于最大频繁项目集相对较小的 数据集中的关联规则挖掘问题。 3 3 2a p r i o r i 算法的实例分析 给定一个由客户交易( c u s t o m e r t r a n s a c t i o n ) 组成的大型数据库如表3 1 客户交易数据库，每个交易( t r a n s a c t i o n ) 由客户号( c u s t - l d ) 以及在交易 中购买的项( i t e m ) 组成。在此不考虑顾客在一次交易中所购买物品的数量， 若最小支持度计数阈值为2 ，用a p r i o r i 算法实现关联规则挖掘。 首先将原始数据库进行相应的转换。每种物品( 也就是商品) 都是由一 个十进制变量代替，得到一个新的客户交易数据库d ，如表3 2 转换后的交 易数据库d 。然后在交易数据库d 上面进行关联规则的挖掘。 哈尔滨工程大学硕士学位论文 表3 1 客户交易数据库 t d项i d 列表 t l牛奶，可乐，香肠 1 2 面包，辣酱 t 3可乐，牛奶，面包，辣酱 t 4辣酱，牛奶，面包 给商品编以序号：牛奶：1 ；面包：2 ；香肠：3 ；辣酱：4 ；可乐：5 ；得 到下列转换后的交易数据库d 表3 2 转换后的交易数据库d 客户号( o u s t i d )所购商品( i t e m )频繁项 11 ，5 ，31 ，5 22 ，42 ，4 0 0 35 ，1 ，2 ，4l ，2 ，4 ，5 0 0 4 4 ，1 ，21 ，2 ，4 利用a 删砸算法进行关联规则挖掘，m i n _ s u p = 2 ，m i n _ c o n f = 2 。利用 m i n _ s u p 对交易数据库d 进行关联挖掘，其中的最大频繁集产生过程如下： ( 1 ) 第一次扫描数据库d ( 如表3 2 ) ，得到1 候选集c l 来计算它在数 据库中的支持度( 如表3 3 ) ( 2 ) 修剪，将支持度小于给定阈值2 的项剔除掉，得1 频繁集1 4 ( 如 表3 4 ) ( 3 ) 调用a p f i o r i - g e n 函数，进行自连接操作，同时进行修剪，得到q ， 同时第二次扫描数据库d 计算各个2 候选集的支持度( 如表3 3 ) 。 表3 3 卜候选集c ， i t e m s u p p o r t 1 ) 3 2 ) 3 3 1 4 ) 3 5 2 表3 4 卜频繁集l 。 i t e m s u p p o r t 1 3 2 3 4 3 5 ) 2 表3 52 - 候选集g i t 锄 s u p p o r t 1 ，2 2 1 ，4 2 1 ，5 2 2 ，4 3 ， 2 ，5 ) 1 4 ，5 1 1 7 哈尔滨工程大学硕士学位论文 ( 4 ) 再修剪，将支持度小于给定阈值2 的项剔除，得到2 频繁集k ( 如 表3 6 ) 表3 62 - 频繁集k i t e m s u p p o r t 1 ，2 2 1 ，4 2 1 ，5 2 2 ，4 3 ( 5 ) 调用a p r i o d - g e n 函数，进行自连接操作，同时进行修剪，得到c 3 ， 同时第二次扫描数据库d 计算各个3 候选集的支持度( 如表3 7 ) 。 表3 73 - 候选集g i t e m s u p p o r t 1 ，2 ，5 ， 1 1 ，2 ，4 ) 2 ( 6 ) 再次修剪，将支持度小于给定阙值2 的项剔除，得到3 频繁集b ( 如表3 8 ) 。 表3 83 - 频繁集k i t e m s u p p o r t 1 ，2 ，4 ) 2 ( 7 ) 最后一次扫描数据库，没有候选集产生，因此k 为空，结束。 从上面的分析可以看出，。此客户交易数据库d 中的频繁集是 1 ，2 ，4 和 1 ，5 l 。通过这个实例了解了a p d o r i 算法的全过程，以及其基本思想和原 哈尔滨工程大学硕士学位论文 理。由于a p r i o r i 算法可以产生相对较小的候选项目集，扫描数据库的次数由 最大频繁项目集的项目数决定因此，对最大频繁项目集相对较小的数据集 中的关联规则挖掘问题，此算法尤为适合。 3 4 本章小结 本章主要介绍了关联规则的基本定义、性质，及经典的a p r i o r i 频繁集算 法。a p r i o r i 算法是利用a p r i o r i 性质：“频繁项目集的任何子集也一定是频繁 的。”将满足给定支持度的所有1 频繁项的每种组合作为产生频繁项的候选 项，再对它们进行修剪，判断其支持度是否大于给定值，这样递推得到最后 的频繁集。由于a p r i o r i 算法可以产生相对较小的候选项目集，扫描数据库的 次数由最大频繁项目集的项目数决定，适合最大频繁项目集相对较小的数据 集中的关联规则挖掘问题。 哈尔滨工程大学硕士学位论文 第4 章关联规则算法研究 4 1 频繁项目集改进算法a p r i o r i t i d 算法 从上面的介绍可以看到a p d o f i 算法的缺点是：在每一次产生候选项目集 时都要扫描一遍数据库d ，而用于关联规则挖掘的数据库的规模通常是非常 大的，所以这样就无形之中增加了额外的开销，影响了算法的效率。a p r i o r i 啊d 算法在a 埘0 i i 算法的基础上对数据集进行修剪，因而在扫描数据库的效率上 要优于冉晒0 r i ，而且减少了f o 操作时间口q 1 p r i o r i t i d 算法描述 a p i i o n n d 算法的第一步是简单统计所有含一个元素的项集出现的频率， 来决定频繁的一维项目集，同时产生集合c 1 。在第k 步，分两个阶段，首先 用函数a l ”i o r i - g c ，通过第( k - d 步中生成的频繁项目集k 1 ，来生成候选 项目集c t ，同时产生集合c ，然后搜索c t 、计算候选项目集g 的支持度 2 p r i o r i t i d 算法 算法：4 1a 州。棚d 算法 输入：事务数据库d ，最小支持度阈值m i n s u p 。 输出：d 中的频繁项集l 处理流程： ( 1 ) _ l - - d a t a b a s ed ； ( 2 ) 厶一 c c 1 i cl l d im i n s u p ；k = 2 ； ( 3 ) w h i l e ( k l 一垂) d o b c g m ，膻到不能生成频繁项目集为止 ( 4 ) q t - a p r i o r i - g e n ( 上骺1 ) ；生成含k 个元素的候选项目集 啥尔滨工程大学硕士学位论文 ( 5 ) c i 一垂： ( 6 ) f o r a l lt e c t q ，d o b e g i n 删自定包含在事务中的标志为t t i d 的c k 的候选项目集 ( 7 ) c | - c gi ( c - c t ) e t s e t - o f - i t c m s c t s ( c - c k - 1 ) e t s c t - o f - i t e m s e t s ； ( 8 ) 计算集合q 中增加的所有候选者； ( 9 ) i fe - m ) & e n c k + - t 3 7 d ，c l ； ( 1 0 ) e n d ； ( 1 1 ) 厶- c e gl c 肋删| d l 乏m i n s u p ) ( 1 2 ) e n d ； ( 1 3 ) 加l 黼玩五； 其中，d 表示数据库；m i n s u p 表示给定的最小支持度；a 1 l s w t ! r 表示所有 频繁项目集。a p f i o d - g e n 函数与a p f i o d 算法中的一样，是通过连接和删除( 也 叫剪枝) 来产生候选项目集的 在a p r i o r i i i d 算法中，寻找最大项目集的基本思路是：算法需要对数据 集进行多步处理。第一步，简单统计所有含一个元素项目集出现的频率，并 找出那些不小于最小支持度的项目集，即一维频繁项目集。从第二步开始循 环处理直到再没有频繁项目集生成。循环过程是：在第k 步中，根据k - 1 步 生成的( k - 1 ) 维频繁项目集来产生k 维候选项目集，然后对集合乙进行搜 索，得到候选项目集的项集支持度，与最小支持度比较，从而找到k 维频繁 项目集。集合c 是这样定义的：集合中的每一个成员的形式为 1 时，c l 是由算法产生的，集合c i 中的成员和事务t 是一致的，如： t t i d ， c c tl c c f p 。如果一个事务不包含任何候选k 维项目集，c t 将没有这个 事务的目录，所以，c t 的目录数将小于数据库中事务的数日，特别是对于值 很大的k 。此外，对于值很大的k ，每一个目录都比相应的事务小，因为在事 务中几乎不包含候选项。反之，对于值很小的l 【，每一个目录都比相应的事 务大，因为c i 中的一个目录包括了包含在事务中所有候选k 维项目集。 3 p r i o r i t i d 算法的优点 从a p r i o r i t i d 算法寻找频繁项目集的思路中，可以知道该算法的优点是 仅在第一次扫描时用事务数据库d 计算候选频繁项目集的支持度，其它各次 扫描用其上一次扫描生成的候选事务数据库d 算候选频繁项目集的支持度 嘲在最后的几次扫描中，d 的大小要远远小于d ，减少了i o 操作时间， 从而提高了算法的效率 4 2 不产生候选项的f p - g r o w t h 算法 4 2 1f p - g r o 州c h 算法的基本思想 前两类a p d o d 算法和a p r i o r i 面d 算法是产生频繁项集候选项的算法，另 一类是不产生候