一种改进的FP树关联规则挖掘算法

人工智能及识别技术

本栏目责任编辑：李桂瑾

１引言

关联规则挖掘是从大量数据中提取项集之间的关联和相互关系，由Ｒ．Ａｇｒａｗａｌ等人在１９９３年首先提出［１］，经过十多年的发展，目前已经形成了一些较为有影响的挖掘算法［２￣４］，以Ａｐｒｉｏｒｉ算法，ＦＰ树算法为代表。其中，Ａｐｒｉｏｒｉ算法通过产生候选频繁项集来挖掘关联规则，人们对其改进做了许多研究工作［５］。２００４年左右，Ｊ．Ｈａｎ等人提出了一种不产生候选项集的挖掘方法，即ＦＰ树算法［３］。本文在深入研究ＦＰ树算法的基础上，提出了一种改进的ＦＰ树算法，它只需要对数据库进行一次扫描即可构造出ＦＰ树，从而缩短了关联规则挖掘时间，提高了效率。

２相关概念描述

２．１关联规则挖掘的相关概念

关联规则挖掘的数据集记为ＴＤＢ（称为事务数据库），Ｔ＝｛ｔ１，ｔ２，…，ｔｋ，…，ｔｎ｝，ｔｋ＝｛ｉ１，…，ｉｊ，Ｌ，ｉｐ｝，ｔｋ（ｋ＝１，２，…，ｎ）称为事务，ｉｊ（ｊ＝１，２，…，ｐ）称为项目。设Ｉ＝｛ｉ１，ｉ２，…，ｉｍ｝是ＴＤＢ中全体项目组成的集合，ｌ的任何子集Ｘ称为ＴＤＢ中的项目集。设ｔｋ和Ｘ分别为ＴＤＢ中的事务和项目集，如果Ｘ!ｔｋ，称事务ｔｋ包含项目集。

数据集ＴＤＢ中包含项目集Ｘ的事务数量称为项目集Ｘ的支持数，记为σｘ。项目集Ｘ的支持度记为ｓｕｐｐｏｒｔ（Ｘ）。ｓｕｐｐｏｒｔ（Ｘ）＝σｘ／｜ＴＤＢ｜，其中｜ＴＤＢ｜是数据集ＴＤＢ的事务数。

若Ｘ、Ｙ为项目集，且Ｘ｜Ｙ＝"，蕴涵式Ｘ＝＞Ｙ称为关联规则。

项目集Ｘ∪Ｙ的支持度称为关联规则Ｘ＝＞Ｙ的支持度，记作：ｓｕｐｐｏｒｔ（Ｘ＝＞Ｙ），ｓｕｐｐｏｒｔ（Ｘ＝＞Ｙ）＝ｓｕｐｐｏｒｔ（Ｘ∪Ｙ）。

关联规则Ｘ＝＞Ｙ的置信度记作：ｃｏｎｆｉｄｅｎｃｅ（Ｘ＝＞Ｙ）。ｃｏｎｆｉｄｅｎｃｅ（Ｘ＝＞Ｙ）＝ｓｕｐｐｏｒｔ（Ｘ∪Ｙ）／ｓｕｐｐｏｒｔ（Ｘ）２．２ＦＰ树挖掘的相关概念

一棵频繁模式树［３］（简称为ＦＰ树）是一棵定义如下的树结构：（１）它由一棵以标记为的节点为根节点和一系列代表频繁项的节点构成的树，以及一个频繁项头表组成。（２）除根节点外，树中的每个节点包含三个域：项名（ｉｔｅｍ＿ｎａｍｅ），计数（ｃｏｕｎｔ），以及节点链（ｎｏｄｅ＿ｌｉｎｋ）。其中，项名是指该节点所代表的项；计数用于记录经

过此节点的事务的数目；节点链指向具有相同项名的下一个节点，当没有下一个节点时，其指针为空。（３）在频繁项头表中的每一个条目由三个域组成，即项名（ｉｔｅｍ＿ｎａｍｅ），支持度计数（ｃｏｕｎｔ）和节点链头（ｈｅａｄｏｆｎｏｄｅ＿ｌｉｎｋ），其中节点链头是一个指向ＦＰ树中具有相同项名的节点链中第一个节点的指针。

根据文献［３］中的ＦＰ树的构造过程，ＦＰ树显然具有下列性质。（１）ＦＰ树中的各非根节点所代表的项在按支持度排序的频繁１－项集中必定位于其后裔节点所代表的项之前。（２）若ＦＰ树中从根节点到某节点的分支上所有节点所代表的项（根节点代表空项）组成的项集为Ａ，ＴＤＢ中包含Ａ的所有事务称为该节点对应的支持事务集，根节点对应的支持事务集为ＴＤＢ中的所有含有频繁项的事务，则除根节点外，ＦＰ树中任一节点所对应的支持事务集为其父节点对应的支持事务集的子集。

３相关的数据结构及挖掘算法

３．１相关数据结构

本文算法中新增的相关数据结构主要包括如下几个。（１）事务支持数表（Ｔｒａｄｅ＿ｕｓｅｄｔａｂｌｅ）

该表的每个条目的结构为｛ｔｒａｄｅ＿ｎｕｍ，ｃｏｕｎｔ｝。其中，ｔｒａｄｅ＿ｎｕｍ为事务号；开始构造ＦＰ树前，ｃｏｕｎｔ为该事务所包含的频繁１－项项目的个数。该表的目的是记录事务项所包含的频繁项数量，算法中用于判断ＦＰ树各个节点及其子树构造是否完成，以便释放多余内存空间。

（２）事务节点（ｔｒａｄｅ＿ｎｏｄｅ）

事务节点的结构为｛ｔｒａｄｅ＿ｎｕｍ，ｎｏｄｅ＿ｌｉｎｋ｝。其中，ｔｒａｄｅ＿ｎｕｍ为事务号；ｎｏｄｅ＿ｌｉｎｋ指向另一个事务节点。该结构用于下面所定义的项支持事务表。

（３）项支持事务表（Ｉｔｅｍ＿ｕｓｅｄｔａｂｌｅ）

该表的每个条目的结构为｛ｉｔｅｍ＿ｎａｍｅ，ｃｏｕｎｔ，ｎｏｄｅ＿ｌｉｎｋ｝。该表主要存放频繁１－项集，以及含有该项的事务计数。其中，ｉｔｅｍ＿ｎａｍｅ为频繁１－项集的项名；ｃｏｕｎｔ为该项的支持数计数；ｎｏｄｅ＿ｌｉｎｋ指向包含该项的事务所组成的事务链的第一个节点，事务链由事务节点（ｔｒａｄｅ＿ｎｏｄｅ）构成，事务链中事务节点的个数即是ｃｏｕｎｔ值。项支持事务表中的条目及其所指向的事务链在构造ＦＰ树时不断被释放，当构造完成时，项支持事务表将全部被释放，以免额外占用内存空间。

３．２算法描述

有了上述的数据结构，其ＦＰ－Ｔｒｅｅ的构造和挖掘过程如下：（１）构造初始项支持交易表和初始交易支持数表。扫描数据库，将每条交易中包含的项统计到项支持交易表中，并构造初始交易支持数表。

（下转第１７３２页）

收稿日期：２００７－０９－０６

基金项目：南京信息工程大学科研基金项目Ｙ５０７。

作者简介：李涛（１９７８－），男，讲师，研究方向：机器学习、数据挖掘。

一种改进的ＦＰ树关联规则挖掘算法

李涛

（南京信息工程大学通信工程系，江苏南京２１００４４）

摘要：关联规则挖掘向来是数据挖掘的一个重要领域，挖掘算法也层出不穷。本文在深入分析了ＦＰ树特性的基础上，改进了ＦＰ树构造过程，通过一次扫描事务数据库生成ＦＰ树。缩短了关联规则挖掘时间，提高了效率，实验验证了其有效性。

关键词：数据挖掘；关联规则；ＦＰ树中图分类号：ＴＰ３１１文献标识码：Ａ文章编号：１００９－３０４４（２００７）１８－３１７０７－０１

ＡｎＩｍｐｒｏｖｅｄＦＰ－ＴｒｅｅＡｌｇｏｒｉｔｈｍｆｏｒＭｉｎｉｎｇＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓ

ＬＩＴａｏ

（ＮａｎｊｉｎｇＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ２１００４４，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：ＴｈｉｓｐａｐｅｒｉｎｔｒｏｄｕｃｅｓａｎｉｍｐｒｏｖｅｄＦＰ－Ｔｒｅｅａｌｇｏｒｉｔｈｍｆｏｒｍｉｎｉｎｇａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ．ＴｈｅｎｅｗａｌｇｏｒｉｔｈｍａｃｃｅｌｅｒａｔｅｓｔｈｅｐｒｏｃｅｓｓｏｆｃｏｎｓｔｒｕｃｔｉｎｇＦＰ－Ｔｒｅｅａｎｄｇｅｎｅｒａｔｅｓｔｈｅｎｏｄｅｓｂｙｓｃａｎｎｉｎｇｔｈｅｄａｔａｂａｓｅｏｎｌｙｏｎｃｅ．Ｔｈｅｐｒｅｓｅｎｔｅｄａｌｇｏｒｉｔｈｍｃａｎｅｆｆｉｃｉｅｎｔｌｙｉｍｐｒｏｖｅｔｈｅｐｅｒｆｏｒ－ｍａｎｃｅｏｆａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓｍｉｎｉｎｇ．

Ｋｅｙｗｏｒｄｓ：ＤａｔａＭｉｎｉｎｇ；ＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓ；ＦＰ－Ｔｒｅｅ

１７０７

计算机教育本栏目责任编辑：王力

握，大大提高了学生的积极性和主动性，也使得他们分析设计系统的能力有很大的提高。这种教学方法比较适合程序设计类课程，对它在其它类课程中的适应性还有待探索。

参考文献：

［１］何克抗．建构主义——

—革新传统教学的理论基础［Ａ］．学校教育现代化建设［Ｍ］．国家教委电教办樟木头培训中心，１９９８，（３）．［２］张建伟，陈琦．从认知主义到建构主义［Ｍ］．北京师范大学学报（社会科学版），１９９６，（４）．

［３］赵建华，李克东．协作学习及协作学习模式［Ｊ］．中国电化教育，２０００，（１０）．

［４］项目教学的研究与实践［Ｊ］．中国职业技术教育，２００３，（４）．

［５］谢志江，案例教学法在工科教学中的应用［Ｊ］，高等工程教育研究，２００３，（５）．

［６］郑金洲，案例教学指南［Ｍ］．上海：华东师范大学出版社，２０００．

（上接第１７０７页）

（２）确定项支持交易表和交易支持数表。对初始项支持交易表按支持数由大到小排序，在给定最小支持数（或支持度）的基础上，去除低于最小支持数的项即可得到频繁１－项集。在此过程中，同时对初始交易支持数表进行调整。每去除一个非频繁项，交易支持数表中相关条目的计数相应的减去１。此过程结束后，项支持交易表仅仅包含频繁１－项集，而且其中各条目指向的交易链记录了支持该项的所有的交易号。交易支持数表中包含了各交易对频繁１－项集的支持程度，即该交易号在项支持交易表中出现的总次数。

（３）根据项支持交易表和交易支持数表构造ＦＰ－Ｔｒｅｅ。根据性质１可知，ＦＰ－Ｔｒｅｅ中每个非根节点的子女节点所代表的项在频繁１－项集中位于该节点所代表的项之后，也就是说，每个非根节点的子女节点代表的项在项支持交易表中位于该节点代表的项之后。此外，根据性质２，子女节点所对应的支持交易集为其父节点对应的支持交易集的子集。

由此，在构建了根节点ｒｏｏｔ后，每次从项支持交易表中选取排在第一位的项建立ｒｏｏｔ的子节点，以其项支持交易表中的指针链作为比较链，将排在其后的每一个项所含的交易链与比较链作比较，如果含有某些相同的交易编号，则建立一个子节点，该节点支持度即是具有相同编号的交易数量；调整交易支持数表和项支持交易表，将交易支持数表中相应的交易数量减去１，支持交易表中对应项的交易节点从指针链中释放；这样继续下去，直至与比较链对应的交易支持数表中的交易计数均为０。依次对项支持交易表中的第一位的项进行此种处理，直至项支持交易表中所有项均处理完成。此时ＦＰ－Ｔｒｅｅ构造完成，相应的项支持交易表亦在构造过程中不断释放而为空，交易支持数表中所有记录亦为０。

（４）在ＦＰ－Ｔｒｅｅ的基础上进行挖掘。此过程与文献［４］相同，此处不再赘述。

４实验

实验平台采用Ｐ３．０ＧＣＰＵ，１ＧＭｅｍｏｒｙ，１２０ＧＨＤ的ＩＢＭ服务器，操作系统是Ｗｉｎｄｏｗｓ２０００Ｓｅｒｖｅｒ，采用ＶｉｓｕａｌＳｔｕｄｉｏ．ＮＥＴ２００３编写程序。对比算法包括：Ａｐｒｉｏｒｉ算法、ＦＰ树算法和本文算法（ＩＦＰ）。实验数据采用ＵＣＩ机器学习数据库中的Ｍｕｓｈｒｏｏｍ数据集（其包括２２属性，８１２４条记录）和Ｃｏｎｎｅｃｔ－４数据集（其包括４３属性，６７，５５７条记录）。实验过程中，变化支持度阈值进行不同的实验，实验结果如图１、图２所示。

由实验结果明显看出，在同等数据集上，采用不同支持度阈值，本文提出的算法（ＩＦＰ）挖掘时间均少于对比算法，说明其关联规则挖掘性能要优于对比算法，证明了本文算法的有效性。

５结论

针对关联规则挖掘，本文提出了一种ＦＰ树的快速构造方法，仅需要一次扫描数据库即可生成ＦＰ树，进而提高了关联规则挖掘速度，实验结果也证明了算法的有效性。

图１Ｍｕｓｈｒｏｏｍ数据集实验结果

图２Ｃｏｎｎｅｃｔ－４数据集实验结果

参考文献：

［１］Ｒ．Ａｇｒａｗａｌ，Ｔ．Ｉｍｉｅｌｉｎｓｋｉ，ａｎｄＡ．Ｓｗａｍｉ．Ｍｉｎｉｎｇａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓｂｅｔｗｅｅｎｓｅｔｓｏｆｉｔｅｍｓｉｎｌａｒｇｅｄａｔａｂａｓｅｓ［Ａ］．ＩｎＰｒｏｃ．１９９３ＡＣＭ－ＳＩＧＭＯＤＩｎｔ．Ｃｏｎｆ．ＭａｎａｇｅｍｅｎｔｏｆＤａｔａ（ＳＩＧＭＯＤ’９３），Ｗａｓｈｉｎｇｔｏｎ，ＤＣ，Ｍａｙ１９９３，２０７－２１６．

［２］Ｒ．ＡｇｒａｗａｌａｎｄＲ．Ｓｒｉｋａｎｔ．Ｆａｓｔａｌｇｏｒｉｔｈｍｓｆｏｒｍｉｎｉｎｇａｓｓｏｃｉａ－ｔｉｏｎｒｕｌｅｓ［Ａ］．ＩｎＰｒｏｃ．１９９４Ｉｎｔ．Ｃｏｎｆ．ＶｅｒｙＬａｒｇｅＤａｔａＢａｓｅｓ（ＶＬＤＢ’９４），Ｓａｎｔｉａｇｏ，Ｃｈｉｌｅ．Ｓｅｐｔ．１９９４，４８７－４９９．

［３］Ｊ．Ｈａｎ，Ｊ．Ｐｅｉ，Ｙ．Ｙｉｎ，ａｎｄＲ．Ｍａｌ．Ｍｉｎｉｎｇｆｒｅｑｕｅｎｔｐａｔｔｅｒｎｓｗｉｔｈｏｕｔｃａｎｄｉｄａｔｅｇｅｎｅｒａｔｉｏｎ：ａｆｒｅｑｕｅｎｔ－ｐａｔｔｅｒｎｔｒｅｅａｐｐｒｏａｃｈ［Ｊ］．Ｄａｔａｍｉｎｉｎｇａｎｄｋｎｏｗｌｅｄｇｅｄｉｓｃｏｖｅｒｙ，２００４，８（１），５３－８７，．

［４］Ｊ．Ｐｅｉ，Ｊ．Ｈａｎ，Ｈ．Ｌｕ，Ｓ．Ｎｉｓｈｉｏ，Ｓ．Ｔａｎｇ，ａｎｄＤ．Ｙａｎｇ．Ｈ－Ｍｉｎｅ：Ｈｙｐｅｒ－ｓｔｒｕｃｔｕｒｅｍｉｎｉｎｇｏｆｆｒｅｑｕｅｎｔｐａｔｔｅｒｎｓｉｎｌａｒｇｅｄａｔａｂａｓｅｓ［Ａ］．Ｐｒｏｃ．２００１Ｉｎｔ．Ｃｏｎｆ．ｏｎＤａｔａＭｉｎｉｎｇ（ＩＣＤＭ’０１），ＳａｎＪｏｓｅ，ＣＡ，Ｎｏｖ．

２００１．

１７３２

电脑知识与技术

颜雪松,-关联规则挖掘综述

收稿日期:2001 12 14;修返日期:2002 04 28 基金项目:湖北省自然科学基金资助项目(2001ABB006) 关联规则挖掘综述 * 颜雪松,蔡之华,蒋良孝,贺 毅 (中国地质大学信息工程学院,湖北武汉430074) 摘 要:介绍了关联规则挖掘的一般概念,并进一步导出它的一般框架;同时对一些典型算法进行了分 析和比较,介绍了关联规则的应用;最后展望了关联规则挖掘的未来研究方向。关键词:关联规则;频繁项目集;深度优先遍历;宽度优先遍历 中图法分类号:TP301 6 文献标识码:A 文章编号:1001 3695(2002)11 0001 04 Survey of Association Rule Mining YAN Xue song,CAI Zhi hua,JIANG Liang xiao,HE Yi (Colle ge o f Information Enginee ring ,China Unive rsit y o f Geosc ienc es,Wuhan Hubei 430074,China) Abstract:In this paper we explain the fundaments of association rule mining and moreover derive a general framework.At the same time compares and analyses some typical algorithms,introduces the application of the association rules.At the end,views some future directions in association rule generation. Key w ords:Association Rule;Frequent Itemsets;DFS;BFS 1 引言 面对海量的存储数据,如何从中发现有价值的信息或知识是一项非常艰巨的任务。数据挖掘就是为了满足这种要求而迅速发展起来的。数据挖掘是指从大型数据库或数据仓库中提取隐含的、先前未知的、对决策有潜在价值的知识和规则。数据挖掘是人工智能和数据库发展相结合的产物,是目前国际上数据库和信息决策系统最前沿的研究方向之一,已引起了学术界和工业界的广泛关注。目前研究的主要目标是发展有关理论、方法和工具,以支持从大量数据中提取有价化的知识和模式。在事务数据库中挖掘关联规则是数据挖掘领域中的一个非常重要的研究课题。它是由R.Agra wal 等人首先提出的。关联规则的一个典型例子就是: 90%的客户在购买面包的同时也会购买牛奶 ,其直观意义为顾客在购买某些商品的时候有多大的倾向会购买另外一些商品。 2 关联规则的基本概念 假设T 是事务的集合,在T 中的每一个事务都是项目集I 的子集。假设C 是I 的一个子集,我们定义C 的支持度如下: (C)=|{t|t !T,C t}|。 (C)表示包含在C 中的事务的数目。例如图1所示的事务集。事务的项目集I 是{Bread,Beer,Coke,Diaper,Milk}。{Diaper,Milk}的支持度是 {Diaper,M ilk}=3,而 {Diaper,Milk, Beer}=2。 TID Item s 1Bread,Coke,Mil k 2Beer,Bre ad 3Beer,Coke,Diape r,Mil k 4Beer,Bre ad,Diape r,Mil k 5 Coke,Dia pe r,Mil k 图1 Transactions from Supermarket 关联规则可描述为:!XY,X I,Y I 。关联规则X !Y 的支持度s 定义为: (X ?Y)/|T|,置信度 定义为 (X ?Y )/ (X)。例如,假设一条规则{Diaper,Milk}!{Beer},表示如果Diaper 和Milk 在一个事务中,就意味着Beer 也包含在这个事务中。这条规则的支持度是: (Di aper ,Milk,Beer)/5=40%。置信度为 (Diaper,Milk,Beer)/ (Diape r,Milk)=66%。如果一条规则的置信度很高的话,就说明这条规则很重要,因为它可以在规则中给项目关联提供精确的预测。同样的,规则的支持度也很重要,它可以暗示在事务中这条规则的出现频率有多高。支持度很低的规则通常是引不起人们的兴趣的。 这就是为什么大多数的算法[2] 忽视那些不能满足用户给定的最小支持度条件的规则的原因。这种用给定最小支持度过滤规则的方法可以减少产生的关联规则的数量,以便于管理。因为算法可能产生的规则的数量和项目集I 的子集的数量是成比例的,可能达到2|I|,因此,这种过滤在实际应用中是必需的。 发现关联规则的任务就是发现所有形如X !Y 的规则,规则的支持度大于或等于给定的最小支持度,规则的置信度大于或等于给定的最小置信度。发现关联规

关于关联规则挖掘综述

关联规则挖掘综述 潮娇娇 摘要：关联规则挖掘是数据挖掘中的一个很重要的研究内容之一，近年来很多国内外研究人员对其进行了大量的研究。为了更进一步的了解关联规则挖掘技术，并掌握其发展方向和目前的研究现状。本文对关联规则挖掘技术进行了相关综述。首先介绍了关联规则的基本概念，其次分析了近年来一些经典关联规则算法的改进，并概述了相关算法在实际中的应用。最后对关联规则挖掘技术未来的发展趋势进行了讨论。 关键字：关联规则；算法；数据挖掘； Abstract: association rule mining is one of the important data mining research contents in this year, many domestic and foreign researchers have done a lot of research on it. In order to understand further the association rule mining technology, and grasp the development status and direction of research at present. This article of association rule mining technology related review. Firstly introduces the basic concepts of association rules, then analyzes the improvement of some classical algorithm of association rules in recent years, and summarizes the application of related algorithms in practice. At the end of the association rule mining technology development trend in the future are discussed. Key words: association rules; algorithms; data mining; 引言 随着计算机技术与数据库技术的飞速地发展，数据资源越来越多。但巨大的数据，依然没有解决我们的信息需求问题，针对这种情况，产生了数据库的数据挖掘。与传统技术相比，数据挖掘技术是一种新型的信息处理技术，能够自动和智能地把位置数据或者大量数据中潜在信息转换成人们需要的信息和知识的技术。它可以从数据库提取有用的知识、规律以及更高层次的信息，对这些进行分析，帮助人们更有效的利用海量数据中存在的价值。目前对数据挖掘的发展趋势及研究方向主要集中在数据挖掘的数据总结、分类、聚类、关联规则等方面。而关联规则挖掘作为数据挖掘的核心内容之一，进来得到了很快的发展。并已经成为当今数据挖掘的热点。为此，对关联挖掘技术的研究具有重要的意义。本文将重点介绍关联规则挖掘技术的相关研究。主要对近年来关联规则挖掘技术的算法改进进行综述以及未来的发展方向。 1、关联规则基本概念 1.1 相关介绍 关联规则作为数据挖掘的核心研究内容之一，它是大量数据中发现信息之间可能存在的某种关联或者相关联系。通过分析这些挖掘出的数据联系，可以在现实中帮助我们预测或决定某些事情将会发生。有效的提高了我们制定出准确的决策。目前，关联规则挖掘技术广泛应用于金融、互联网、医学等多个领域。最早的关联挖掘是未来发现交易数据库中不同商品之间的联系，通过分析这种联系获得有关购买者的一般的购买模式。从而有助于商家合理地安排进货、库存及货架设计，更好的制定发展计划和规避风险。

数据挖掘算法综述

数据挖掘方法综述 [摘要]数据挖掘（DM，DataMining）又被称为数据库知识发现（KDD,Knowledge Discovery in Databases）,它的主要挖掘方法有分类、聚类、关联规则挖掘和序列模式挖掘等。 [关键词]数据挖掘分类聚类关联规则序列模式 1、数据挖掘的基本概念 数据挖掘从技术上说是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们事先不知道的、但又是潜在的有用的信息和知识的过程。这个定义包括好几层含义: 数据源必须是真实的、大量的、含噪声的、发现的是用户感兴趣的知识, 发现的知识要可接受、可理解、可运用, 并不要求发现放之四海皆准的知识, 仅支持特定的发现问题, 数据挖掘技术能从中自动分析数据进行归纳性推理从中发掘出潜在的数据模式或进行预测, 建立新的业务模型帮助决策者调整策略做出正确的决策。数据挖掘是是运用统计学、人工智能、机器学习、数据库技术等方法发现数据的模型和结构、发现有价值的关系或知识的一门交叉学科。数据挖掘的主要方法有分类、聚类和关联规则挖掘等 2、分类 分类（Classification）又称监督学习（Supervised Learning）。监

督学习的定义是：给出一个数据集D，监督学习的目标是产生一个联系属性值集合A和类标（一个类属性值称为一个类标）集合C的分类/预测函数，这个函数可以用于预测新的属性集合（数据实例）的类标。这个函数就被称为分类模型（Classification Model），或者是分类器（Classifier）。分类的主要算法有：决策树算法、规则推理、朴素贝叶斯分类、支持向量机等算法。 决策树算法的核心是Divide-and-Conquer的策略，即采用自顶向下的递归方式构造决策树。在每一步中，决策树评估所有的属性然后选择一个属性把数据分为m个不相交的子集，其中m是被选中的属性的不同值的数目。一棵决策树可以被转化成一个规则集，规则集用来分类。 规则推理算法则直接产生规则集合，规则推理算法的核心是Separate-and-Conquer的策略，它评估所有的属性-值对（条件），然后选择一个。因此，在一步中，Divide-and-Conquer策略产生m条规则，而Separate-and-Conquer策略只产生1条规则，效率比决策树要高得多，但就基本的思想而言，两者是相同的。 朴素贝叶斯分类的基本思想是：分类的任务可以被看作是给定一个测试样例d后估计它的后验概率，即Pr（C=c j︱d），然后我们考察哪个类c j对应概率最大，便将那个类别赋予样例d。构造朴素贝叶斯分类器所需要的概率值可以经过一次扫描数据得到，所以算法相对训练样本的数量是线性的，效率很高，就分类的准确性而言，尽管算法做出了很强的条件独立假设，但经过实际检验证明，分类的效果还是

关联规则挖掘的Apriori算法改进综述

关联规则挖掘的Apriori算法改进综述 1引言 数据挖掘是一种半自动地从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取出隐含在其中潜在有用的信息和知识的过程。数据挖掘从数据中提取人们感兴趣的可用信息和知识，并将提取出来的信息和知识表示成概念、规则、规律和模式。 数据挖掘，又称数据库中的知识发现(Knowledge Discovery in Database, KDD)，指的是从大型数据库的数据仓库中提取人们感兴趣的知识，这些知识是隐含的、事先未知的潜在有用信息，换言之，数据挖掘是一个利用各种分析工具在海量数据中，发现模型和数据间关系的过程，这些模型和关系可以用来作出预测。对于数据挖掘技术的研究已引起了国际人工智能和数据库等领域专家与学者的广泛关注，这其中在事务数据库中挖掘关联规则是数据挖掘领域中的一个非常重要的研究课题。关联规则是美国IBM Almaden research center的Rabesh Agrawal等人于1993年首先提出的，最近几年在数据挖掘研究领域对关联规则挖掘的研究开展得比较积极和深入[1]。关联规则挖掘是发现大量数据中项集之间有趣的关联或相关关系。随着大量数据不停被地收集和存储，许多业界人士对于从数据库中挖掘关联规则越来越感兴趣。 2 Apriori算法 2.1关联规则挖掘问题的形式化描述 对于经常使用的数据，同一文件的不同版本之间的内容往往会有重复，因此数据冗余比较多，如果采用增量式压缩就可以大大节省磁盘空间。但是这样的数据是压缩的，一旦用户需要查询/恢复数据就需要解压过程，因此这会使系统性能降低。设I={i1，i2，…，im}是由m个不同的项目组成的集合，给定一个事务数据库D，其中的每一个事务T是I中一组项目的集合，即T?I，T有一个唯一的标识符TID。若项集X?I 且X?T，则事务T包含项集X。一条相联规则就是形如X?Y的蕴涵式，其中X?I，Y?I，x∩Y=Φ。相联规则X?Y成立的条件是: (l)它具有支持度s，即事务数据库D中至少有s%的事务包含XY ∪； (2)它具有置信度c，即在事务数据库D中包含X的事务至少有c%同时也包含Y。 关联规则的挖掘问题就是在事务数据库 D 中找出具有用户给定的最小支持度minsup 和最小置信度minconf的关联规则。 2.2 Apriori算法简介 1994 年，Rakesh AgrawalRama 和Krishnan Skrikant 首先提出了Apriori算法[2]，它是一种最有影响的挖掘布尔关联规则频繁项集的算法。Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法，其核心是使用候选项集找频繁项集。Apriori算法使用一种称作逐层搜索的迭代方法k-项集用于搜索以(k+l)-项集。首先，找出频繁1-项集的集合，该集合记作L1，L1 用于找频繁2-项集的集合L2，L2 从用于找L3.如此下去，直到不能找到频繁项集。 3 Apriori算法的改进 3.1 DDApriori算法[3] 从Apriori算法可以看出, 对每一Ci均对数据库扫描一次,而这时有些事务已经对频繁项集的生成不产生作用, 减少数据库 D 内不起作用的事务对于算法来说是很有必要的,本

数据挖掘中关联规则挖掘的应用研究

数据挖掘中关联规则挖掘的应用研究 吴海玲，王志坚，许峰 河海大学计算机及信息工程学院，江苏南京（210098） 摘 要：本文首先介绍关联规则的基本原理，并简单概括其挖掘任务，然后说明关联规则的经典挖掘算法Apriori 算法，通过一个实例分析进一步明确关联规则在CRM 中的应用，最后展望了关联规则挖掘的研究方向。 关键词：数据挖掘，关联规则，Apriori 算法，CRM 引言 关联规则是表示数据库中一组对象之间的某种关联关系的规则，关联规则挖掘的主要对象是交易(Transaction)数据库。这种数据库的一个主要应用是零售业，比如超级市场的销售管理。条形码技术的发展使得数据的收集变得更容易、更完整，从而可以存储大量的交易资料。关联规则就是辨别这些交易项目之间是否存在某种关系。例如：关联规则可以表示“购买了商品A 和B 的顾客中有80％的人又购买了商品C 和D”。这种关联规则提供的信息可以用作商品目录设计、商场货架的布置、生产安排、具有针对性的市场营销等。 [1] 1 关联规则的基本原理 设Ｉ＝｛i 1，i 2，……，i m ｝是项的集合，设任务相关的数据D 是数据库事务的集合，其中每个事务T 是项的集合，使得T I 。每一个事务有一个标识符，称作T ID 。设X 是一个项集，事务T 包含X 当且仅当X T 。关联规则是形如X Y 的蕴涵式，其中X I ，Y ?I ，并且X ∩Y ＝?。规则X Y 在事务集D 中成立，具有支持度s ，其中s 是D 中事务包含X ∪Y （即X 和Y 二者）的百分比，它是概率P （X ∪Y ）。规则X Y 在事务集中具有可信度c ，如果D 中包含X 的事务同时也包含Y 的百分比c 。这是条件概率P （X Y ∣）。即是 ??????support(X ?Y)= P （X Y ∪） confidence(X ?Y)= P （X Y ∣） 同时满足最小支持度(minsup)和最小可信度阈值（minconf ）的规则称作强规则[1]。 项的集合称为项集（itemset ）。包含k 个项的项集成为k －项集，例如集合{computer, software }是一个2—项集。项集的出现频率是包含项集的事务数，简称为项集的频率。项集满足最小支持度minsup ，如果项集的出现频率大于或者等于minsup 与D 中事务总数的乘积。如果项集满足最小支持度，则称它为频繁项集(frequent itemset) [2]。 2 关联规则的发现任务 关联规则挖掘的问题就是要找出这样的一些规则，它们的支持度或可信度分别大于指定的最小支持度minsup 和最小可信度minconf 。因此，该问题可以分解成如下两个子问题[3]： 1．产生所有支持度大于或等于指定最小支持度的项集，这些项目集称为频繁项目集（frequent itemsets ），而其他的项目集则成为非频繁项目集（non-frequent itemsets ） 2．由频繁项集产生强关联规则。根据定义，这些规则必须满足最小支持度和最小可信度。 关联规则挖掘的问题的主要特征是数据量巨大，因此算法的效率很关键。目前研究的重点在第一步，即发现频繁项目集，因此第二步相对来说是很容易的。

关联规则算法Apriori的学习与实现

关联规则算法Apriori的学习与实现 (2011-07-18 11:28:52) 首先我们来看，什么是规则？规则形如”如果…那么…(If…Then…)”,前者为条件，后者为结果。关联规则挖掘用于寻找给定数据集中项之间的有趣的关联或相关关系。关联规则揭示了数据项间的未知的依赖关系，根据所挖掘的关联关系，可以从一个数据对象的信息来推断另一个数据对象的信息。例如购物篮分析。牛奶?面包[支持度：3%，置信度：40%] 支持度3%意味3%顾客同时购买牛奶和面包。置信度40%意味购买牛奶的顾客40%也购买面包。规则的支持度和置信度是两个规则兴趣度度量，它们分别反映发现规则的有用性和确定性。关联规则是有趣的，如果它满足最小支持度阈值和最小置信度阈值。这些阈值可以由用户或领域专家设定。 我们先来认识几个相关的定义： 定义1：支持度（support） 支持度s是事务数据库D中包含A U B的事务百分比，它是概率P（A U B），即support （A B）=P（A U B），它描述了A和B这两个物品集的并集在所有的事务中出现的概率。定义2：置信度（confidence） 可信度为事务数据库D中包含A的事务中同时也包含B的百分比，它是概率P（B|A），即confidence（A B）=P（B|A）。 定义3：频繁项目集 支持度不小于用户给定的最小支持度阈值（minsup）的项集称为频繁项目集（简称频集），或者大项目集。所有 的频繁1-项集记为L1。 假设有如下表的购买记录。 顾客项目 1orange juice, coke 2milk, orange juice, window cleaner 3orange juice, detergent 4orange juice, detergent, coke 5window cleaner 将上表整理一下，得到如下的一个2维表 Orange Win Cl Milk Coke Detergent Orange41122 WinCl12100 Milk11100 Coke20021 Detergent10002 上表中横栏和纵栏的数字表示同时购买这两种商品的交易条数。如购买有Orange的交易数为4，而同时购买Orange和Coke的交易数为2。 置信度表示了这条规则有多大程度上值得可信。设条件的项的集合为A,结果的集合为B。置信度计算在A中，同时也含有B的概率。即Confidence(A==>B)=P(B|A)。例如计算"如果

关联规则Apriori算法的改进

关联规则Apriori算法的改进 摘要：文章提出一种改进的apriori算法。该算法通过减少对数据库搜索的次数，从而减少数据挖掘过程中的i/o开销。实践证明，用此算法进行关联挖掘，其效率比传统的方法要高。 关键词：数据挖掘关联规则频繁项集 apriori算法improvement of apriori algorithm for association rules li xiao-hui (college of computer science and technology,changchun university,changchun 130022,china) abstract：this paper presents an improved apriori algorithm. the new algorithm can decrease the i/o operation of the process of mining by means of decreasing the times of database searching. it is shown by the experimental result that the improved algorithm is much more efficient than the traditional algorithm in being applied to mining association rule. neywords：data mining，association rule，frequent itemset，apriori algorithm 1、引言 随着数据库技术和计算机网络的发展,在海量数据里发现有价值 的知识和信息的工作受到了越来越多的重视。数据挖掘的一个重要方向是关联规则的挖掘，而关联规则挖掘中最经典算法是apriori

基于股票时间序列数据的关联规则挖掘研究

基于股票时间序列数据的关联规则挖掘研究 Study on Mining Association Rules from Stock Time Series Data 一．引言 随着计算机信息系统的日益普及，大容量存储技术的发展以及条形码等数据获取技术的广泛应用，人们在日常事务处理和科学研究中积累了大量的各种类型的数据。在这些数据中，有很大一部分是呈现时间序列（time series）类型的数据。所谓时间序列数据就是按时间先后顺序排列各个观测记录的数据集[1]，如金融证券市场中每天的股票价格变化；商业零售行业中，某项商品每天的销售额；气象预报研究中，某一地区的每天气温与气压的读数；以及在生物医学中，某一症状病人在每个时刻的心跳变化等等。然而，我们应该注意到：时间序列数据不仅仅是历史事件的记录，更重要的是蕴藏这些数据其中不显现的、有趣的模式。随着时间推移和时间序列数据的大规模增长，如何对这些海量数据进行分析处理，挖掘其背后蕴藏的价值信息，对于我们揭示事物发展规律变化的内部规律，发现不同事物之间的相互关系，为人们正确认识事物和科学决策提供依据具有重要的实际意义。 时间序列数据分析按照不同的任务有各种不同的方法，一般包括趋势分析、相似性搜索、与时间有关数据的序列模式挖掘、周期模式挖掘等[2]。本综述是针对证券业中股票时间序列分析的，试图通过列举、分析有关证券业中股票时间序列数据分析的原理、方法与技术，着重探讨数据挖掘中基于股票时间序列数据的关联规则挖掘的概念、原理技术、实施过程及存在的障碍和问题，以期能有新的发现和领悟。 二．股票时间序列传统研究方法概述 随着我国市场经济建设的发展，人们的金融意识和投资意识日益增强。股票市场作为市场经济的重要组成部分，正越来越多地受到投资者的关注。目前股票投资已经是众多个人理财中的一种重要方式。不言而喻，如果投资者能正确预测股票价格、选准买卖时机，无疑会给投资者带来丰厚的收益。于是，在股票的预测和分析方面出现了大量的决策分析方法和工具，以期能有效地指导投资者的投资决策。目前，我国股市用得较多的方法概括起来有两类[3]：一类是基本分析和技术分析，另一类是经济统计分析。 1．基本分析和技术分析 在股票市场上，当投资者考虑是否投资于股票或购买什么股票时，一般可以运用基本分析的方法对股市和股票进行分析；而在买卖股票的时机把握上，一般可以运用技术分析的方法[4]。 基本分析指的是通过对影响股票市场供求关系的基本因素（如宏观政治经济形势、金融政策、行业变动、公司运营财务状况等）进行分析，来确定股票的真正价值，判断未来股市走势，是长期投资者不可或缺的有效分析手段。 技术分析是完全根据股市行情变化而加以分析的方法，它通过对历史资料（成交价和成交量）进行分析，来判断大盘和个股价格的未来变化趋势，探讨股市里投资行为的可能转折，从而给投资者买卖股票的信号，适合于投资者作短期投资。目前技术分析常用的工具是各种各样的走势图（K线图、分时图）和技术指标（MA、RSI、OBV等）。 2．经济统计学分析

数据挖掘算法之关联规则

数据挖掘算法之-关联规则挖掘(Association Rule) (2009-09-20 21:59:23) 转载 标签： 分类：DM dm 在数据挖掘的知识模式中，关联规则模式是比较重要的一种。关联规则的概念由Agrawal、Imielinski、Swami 提出，是数据中一种简单但很实用的规则。关联规则模式属于描述型模式，发现关联规则的算法属于无监督学习的方法。 一、关联规则的定义和属性 考察一些涉及许多物品的事务：事务1 中出现了物品甲，事务2 中出现了物品乙，事务3 中则同时出现了物品甲和乙。那么，物品甲和乙在事务中的出现相互之间是否有规律可循呢？在数据库的知识发现中，关联规则就是描述这种在一个事务中物品之间同时出现的规律的知识模式。更确切的说，关联规则通过量化的数字描述物品甲的出现对物品乙的出现有多大的影响。 现实中，这样的例子很多。例如超级市场利用前端收款机收集存储了大量的售货数据，这些数据是一条条的购买事务记录，每条记录存储了事务处理时间，顾客购买的物品、物品的数量及金额等。这些数据中常常隐含形式如下的关联规则：在购买铁锤的顾客当中，有70 ％的人同时购买了铁钉。这些关联规则很有价值，商场管理人员可以根据这些关联规则更好地规划商场，如把铁锤和铁钉这样的商品摆放在一起，能够促进销售。 有些数据不像售货数据那样很容易就能看出一个事务是许多物品的集合，但稍微转换一下思考角度，仍然可以像售货数据一样处理。比如人寿保险，一份保单就是一个事务。保险公司在接受保险前，往往需要记录投保人详尽的信息，有时还要到医院做身体检查。保单上记录有投保人的年龄、性别、健康状况、工作单位、工作地址、工资水平等。这些投保人的个人信息就可以看作事务中的物品。通过分析这些数据，可以得到类似以下这样的关联规则：年龄在40 岁以上，工作在A 区的投保人当中，有45 ％的人曾经向保险公司索赔过。在这条规则中，

关联规则最大频繁项目集的快速发现算法

第42卷　第2期 吉林大学学报(理学版) V ol.42　N o.2 2004年4月 JO U RN A L OF JIL IN U N IV ER SIT Y(SCIEN CE EDIT ION)A pr　2004 关联规则最大频繁项目集的快速发现算法 刘大有1,2,刘亚波1,2,尹治东3 (1.吉林大学计算机科学与技术学院,长春130012; 2.吉林大学符号计算与知识工程教育部重点实验室,长春130012; 3.吉林出入境检验检疫局,长春130062) 摘要:提出一种快速发现最大频繁项目集的算法,该算法对集合枚举树进行改进,结合自底向上与自顶向下的搜索策略,利用非频繁项目集对候选最大频繁项目集进行剪枝和降维,减少了不必要候选最大频繁项目集的数量,显著提高了发现的效率. 关键词:关联规则;集合枚举树;最大频繁项目集 中图分类号:T P311 文献标识码:A 文章编号:1671-5489(2004)02-0212-04 Fast algorithm for discovering maximum frequent itemsets of association rules LIU Da-yo u1,2,LIU Ya-bo1,2,YIN Zhi-dong3 (1.College of Comp uter S cience and T echnology,J ilin U niver sity,Changchun130012,China; 2.K ey L abor atory of Sy mbolic Comp utation and K now ledg e E ngineering of M inistry of Education,J ilin U niver sity, Changchun130012,China; 3.J ilin E ntry-Ex it I nsp ection and Quar antine Bureau,Changchun130062,China) Abstract:The present paper presents an efficient alg orithm that improv es set-enumeratio n tr ee and finds maxim um frequent item sets.By co mbining botto m-up and top-dow n searches in set-enumeration tree and making use of the infrequent itemsets to pr une candidates of the m ax imum frequent itemsets, the algorithm reduces the number of candidates of the max imum frequent itemsets g enerated by it so that the efficiency is incr eased. Keywords:association rule;set-enumeration tree;max imum frequent itemset 发现频繁项目集是关联规则等多种数据挖掘的关键问题.在关联规则挖掘中,如果一个项目集的支持度不小于用户定义的最小支持度(以下简记为minsup),则称为频繁项目集;反之则称为非频繁项目集.如果一个频繁项目集的所有超集都是非频繁项目集,则称为最大频繁项目集.目前,多数频繁项目集发现算法都是Apr io ri算法或者其变种[1].这些算法采用自底向上的方法穷举每个频繁项目集,当最大频繁项目集很长时,这将是一个NP问题.任何频繁项目集都是最大频繁项目集的子集,该问题可以转化为发现所有最大频繁项目集.提高发现最大频繁项目集效率的关键是减少生成不必要的候选项目集及对其支持度的计算. 文献[2]中的M ax-Miner算法采用集合枚举树来描述项目集,突破了传统的自底向上的搜索策 收稿日期:2003-09-28. 作者简介:刘大有(1942～),男,教授,博士生导师,从事人工智能、数据挖掘和计算机应用的研究,E-mail:dyliu@https://www.wendangku.net/doc/df13784504.html,. cn.联系人:刘亚波(1975～),女,博士研究生,从事关联规则挖掘和粗糙集理论的研究,E-mail:liu-yabo@https://www.wendangku.net/doc/df13784504.html,. 基金项目:国家自然科学基金(批准号:60173006)、国家高技术研究发展计划项目(批准号:2003AA118020)、吉林省科技发展计划重大项目(批准号:吉科合字20020303-2)和吉林大学符号计算与知识工程教育部重点实验室资助基金.

关联规则算法改进

1.关联规则概述 1.1关联规则 超市，商场的商品应该如何摆放最合适?啤酒和尿布这两类不同商品能否摆在一起?数据挖掘的经典案例——啤酒尿布告诉我们顾客的购买行为存在一定的关联，使我们不得不重视经典的购物车问题。 关联规则的挖掘就是通过一系列数据分析来挖掘某种特定的商品组合被顾客同时购买的可能。关联规则的分析有R.Agrawal于1993年最早提出，是KDD 研究的重要内容，侧重于确定数据中不同领域之间的联系，找出满足给定支持度和置信度的多个域之间的依赖关系。关联规则的挖掘是数据挖掘的一项重要任务，其目的就是从事物数据库、关系数据库中发现项目集或属性之间的相关性，关联关系，因果关系。 1.2关联规则的概念： 关联规则是描述数据库中数据项之间存在的潜在的关系规则。问题可以描述如下： I ={i1，i2，i3….im}是所有项的集合，相当与商品的种类集合。D 是所有事务的子集，相当于数据库中的记录集合。每个事务T 由I中的若干项组成，是I的子集，用唯一的ID 标识，记为T = { t1，t2，. . . ，tn }，相当于每次交易中的商品列表。假设X，Y 是数据项集，X 中含有的项的数目为k，称为k_数据项集，是I 的子集。关联规则表示为: ( T 中包含X) ( ( T中包含Y)。意义在于一次交易中(数据库中的一条记录)存在X 项目，意味着该交易中也存在Y 项目。通常简写为X ( Y，X 称为关联规则的前项，Y称为该关联规则的后项，称为关联操作。)关联规则主要解决的两个问题：找出所有频繁项集和分析频繁项集找出关联规则。

2.关联规则算法简介 2.1宽度优先算法：Apriori 算法 Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。 2.2深度优先算法：FP-Growth算法 针对Apriori算法的不足，通过减少项集的搜索空间和数据库的扫描次数，Han于2004年提出了一个无需产生候选集，只需扫描两次数据库的算FP-Growth。FP-Growth采取如下策略:首先将要挖掘的数据库压缩到一棵频繁模式树中，并在压缩的过程中保留项集的关联信息;然后，将压缩后的数据库划分成一组条件数据库(一种特殊类型的投影数据库，每个关联一个频繁项)，然后分别挖掘每个条件数据库来产生频繁项集。与逐层进行的宽度优先搜索算法不同，基于深度优先搜索的FP_ Growth算法对整个搜索空间的分枝逐个进行搜索，所以，只有当某个节点上的项集属于频繁项集的时候，才会对其子节点作进一步的搜索。 FP-Growth频繁项集挖掘算法的主要步骤： 第一步，构造FP树: （1）扫描事务数据库DB，找出1-频繁项集，并根据它们的支持度计数按降序排序， 结果一记为L。 （2）创建FP树的根节点，记为“null”，并置为当前树根。 （3）扫描DB中的一个事务T:根据L选出T中的频繁项，并按L中的顺序排列，

关联规则挖掘综述

关联规则挖掘综述 摘要：近年来国内外学者对关联规则进行了大量的研究。为了更好地了解关联规则的挖掘技术，对研究现状有更深入的了解，首先本文对数据挖掘技术进行了介绍，接着介绍了关联数据挖掘的基本原理，最后对经典的挖掘算法进行分类介绍。 关键词：数据挖掘；关联规则；算法；综述 1.引言 数据挖掘是从海量的数据里寻找有价值的信息和数据。数据挖掘中常用的算法[1]有：关联规则分析法（解决事件之间的关联问题）、决策树分类法（对数据和信息进行归纳和分类）、遗传算法（基于生物进化论及分子遗传学理论提出的）、神经网络算法（模拟人的神经元功能）等。 数据挖掘最早使用的方法是关联分析，主要应用于零售业。其中最有名的是售货篮分析，帮助售货商制定销售策略。随着信息时代的到来，数据挖掘在金融[2]、医疗[3]、通信[4]等方面得到了广泛的应用。 2.关联规则基本原理 设项的集合I = { I1 ，I2 ，...，Im }，数据库事务的集合为D，我们用|D|表示事务数据库所有事务的个数，其中用T

表示每个事务，使得T I。我们用TID作为每个事务的唯一标识符。用X表示一个项集，满足X T，那么交易T包含X。根据上述相关描述，给出关联规则的相关定义。 2.1项集支持度 用X表示数据库事务D中的项集，项集X的支持度表示项集X在D中事务数所占的比例，用概率P（X）表示，那么Support（X）=P（X）=COUNT（X）/|D| （1） 2.2关联规则置信度 X Y关联规则的置信度是数据库事务D中包含X Y的事务数与包含X的事务数之比，表示方法如下： confidence（X Y）= support（X Y）/support（X）= P（Y|X）（2） 3.关联规则算法 3.1经典的Apriori挖掘算法 大多数关联规则的算法是将关联规则挖掘任务分为两个子任务完成。一是频繁项集的产生，频繁项集的目的是找到大于等于给定的最小支持度阈值的所有项集，这些项集我们称之为频繁项集。二是规则的产生，即从频繁项集中找到置信度比较高的规则，我们称之为强规则。Apriori挖掘算法是众多挖掘关联规则中比较经典的算法，它采用布尔关联规则，是一种宽度优先算法。 3.2Apriori算法优化

关联规则基本算法

关联规则基本算法及其应用 1．关联规则挖掘 1.1 关联规则提出背景 1993年，Agrawal 等人在首先提出关联规则概念，同时给出了相应的挖掘算法AIS ，但是性能较差。1994年，他们建立了项目集格空间理论，并依据上述两个定理，提出了著名的Apriori 算法，至今Apriori 仍然作为关联规则挖掘的经典算法被广泛讨论，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。关联规则挖掘在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。 关联规则最初提出的动机是针对购物篮分析(Market Basket Analysis)问题提出的。假设分店经理想更多的了解顾客的购物习惯（如下图）。特别是，想知道哪些商品顾客可能会在一次购物时同时购买？为回答该问题，可以对商店的顾客事物零售数量进行购物篮分析。该过程通过发现顾客放入“购物篮”中的不同商品之间的关联，分析顾客的购物习惯。这种关联的发现可以帮助零售商了解哪些商品频繁的被顾客同时购买，从而帮助他们开发更好的营销策略。 1.2 关联规则的基本概念 关联规则定义为：假设12{,,...}m I i i i =是项的集合，给定一个交易数据库 12D ={t ,t ,...,t }m ， 其中每个事务(Transaction)t 是I 的非空子集，即t I ∈，每一个交易都与 一个唯一的标识符TID(Transaction ID)对应。关联规则是形如X Y ?的蕴涵式， 其中X ,Y I ∈且X Y φ?=， X 和Y 分别称为关联规则的先导(antecedent 或left-hand-side, LHS)和后继(consequent 或right-hand-side, RHS)。关联规则X Y ?在D 中的支持度(support)是D 中事务包含X Y ?的百分比，即概率()P X Y ?；置信度(confidence)是包含X 的事务中同时包含Y 的百分比，即条件概率(|)P Y X 。如果满足最小支持度阈值和最小置信度阈值，则称关联规则是有趣的。这些阈值由用户或者专家设定。

关联规则挖掘基本概念和算法--张令杰10121084

研究生课程论文 关联规则挖掘基本概念和算法 课程名称：数据仓库与数据挖掘 学院：交通运输 专业：交通运输规划与管理 年级：硕1003班 姓名：张令杰 学号：10121084 指导教师：徐维祥

摘要 (Ⅰ) 一、引言 (1) 二、关联规则的基本描述 (1) 三、经典频繁项集挖掘的Apriori算法 (3) 四、提高Apriori算法的效率 (6) 五、由频繁项集产生关联规则 (8) 六、总结 (9) 参考文献 (9)

目前，数据挖掘已经成为一个研究热点。关联规则数据挖掘是数据挖掘的一个主要研究内容，关联规则是数据中存在的一类重要的可被发现的知识。其核心问题是如何提高挖掘算法的效率。本文介绍了经典的关联规则挖掘算法Apriori并分析了其优缺点。针对该算法的局限性，结合Apriori性质，本文对Apriori中连接的步骤进行了改进。通过该方法，可以有效地减少连接步产生的大量无用项集并减少判断项集子集是否是频繁项集的次数。 关键词：Apriori算法；关联规则；频繁项集；候选集

一、 引言 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。如果两项或多项属性之间存在关联，那么其中一项的属性就可以依据其他属性值进行预测。它在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。 关联规则挖掘的一个典型例子是购物篮分析[1] 。关联规则研究有助于发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。 最著名的关联规则发现方法是R. Agrawal 提出的Apriori 算法。关联规则挖掘问题可以分为两个子问题：第一步是找出事务数据库中所有大于等于用户指定的最小支持度的数据项集；第二步是利用频繁项集生成所需要的关联规则，根据用户设定的最小置信度进行取舍，最后得到强关联规则。识别或发现所有频繁项目集市关联规则发现算法的核心。 二、关联规则的基本描述 定义1. 项与项集 数据库中不可分割的最小单位信息，称为项目，用符号i 表示。项的集合称为项集。设集合{}k i i i I ,,,21 =是项集，I 中项目的个数为k ，则集合I 称为k -项集。例如，集合{啤 酒，尿布，牛奶}是一个3-项集。 定义2. 事务 设{}k i i i I ,,,21 =是由数据库中所有项目构成的集合，一次处理所含项目的集合用T 表示，{}n t t t T ,,,21 =。每一个i t 包含的的项集都是I 子集。 例如，如果顾客在商场里同一次购买多种商品，这些购物信息在数据库中有一个唯一的标识，用以表示这些商品是同一顾客同一次购买的。我们称该用户的本次购物活动对应一个数据库事务。 定义3. 项集的频数（支持度计数） 包括项集的事务数称为项集的频数（支持度计数）。 定义4. 关联规则 关联规则是形如Y X ?的蕴含式，其中X ，Y 分别是I 的真子集，并且φ=?Y X 。 X 称为规则的前提，Y 称为规则的结果。关联规则反映X 中的项目出现时，Y 中的项目也 跟着出现的规律