Apriori算法
Apriori算法改进及其实现
内容摘要
信息技术的不断推广应用，将企业带入了一个信息爆炸的时代。如何充分利用这些数据信息为企业决策者提供决策支持成为一个十分迫切的又棘手的问题，人们除了利用现有的关系数据库标准查询语句得到一般的直观的信息以外，必须挖掘其内含的、未知的却又实际存在的数据关系。著名的Apriori算法是一种挖掘关联规则的算法。
本文通过对参与候选集的元素计数的方法来减少产生候选集的组合和减少数据库的扫描次数来达到要求。这有利于提高挖掘的速度和减少数据库的I/O 操作时间的开销。
关键字：数据挖掘，关联规则，Apriori算法
Apriori Algorithm And Improved Apriori Algorithm Abstract：An information burst age is coming with the various application of Information technology. How to maximize the information is a very important problem for the decision-maker of the companies. Besides getting the regular information from the Database by SQL-query, people still need to mine the data relation which is unclear but really exists.Association rules is one of the data mining methods, the famous algorithm Apriori is a method, which can be used to solute those problems.
This article analyzes and studies the improved algorithm Apriori based on the algorithm of mining association rules Apriori. The main idea is to decrease the number of candidate items and to decrease the times of Database scanning. The solution is available. It upgrades the speed of data mining and decreases computer's I/O operation. It's proved to be more efficient than the traditional
Key words: Datamining, association rules, Apriori algorithm,
目录
1 数据挖掘.................................................................................................................................. - 1 -
1.1 技术上的定义及含义.................................................................................................. - 1 -
1.2 商业角度的定义.......................................................................................................... - 2 -
1.3 数据挖掘与传统分析方法的区别.............................................................................. - 2 -
1.4数据挖掘不能干什么................................................................................................... - 3 -
2 数据挖掘的几种主要形式:.................................................................................................... -
3 -
2.1:规则挖掘：.................................................................................................................. - 3 -
2.2聚类分析：................................................................................................................... - 4 -
3 关于关联规则的讨论.............................................................................................................. -
4 -
3.1购物篮分析................................................................................................................... - 4 -
3.2 关联规则基本问题描述.............................................................................................. - 4 -
3.3 关联规则挖掘举例...................................................................................................... - 6 -
3.4 关联规则问题的分解.................................................................................................. - 8 -
4 Apriori算法的描述............................................................................................................... - 8 -
4.1 Apriori算法的说明................................................................................................... - 8 -
4.2 Apriori算法的描述................................................................................................... - 9 -
4.3 Apriori算法的举例................................................................................................. - 11 -
5 一种Apriori的改进算法.................................................................................................... - 14 -
5.1算法产生的思路......................................................................................................... - 14 -
5.2算法的图例说明......................................................................................................... - 15 -
5.3本算法的评价:........................................................................................................... - 15 - 附录1 程序运行图示............................................................................................................... - 18 - 附录2 程序代码....................................................................................................................... - 20 -
1 数据挖掘
1.1 技术上的定义及含义
数据挖掘（Data Mining）就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海皆准的知识，仅支持特定的发现问题。
----何为知识?从广义上理解，数据、信息也是知识的表现形式，但是人们更把概念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数据库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理，查询优化，决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的技术热点。
这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。实际上，所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域的，同时还要
能够易于被用户理解。最好能用自然语言表达所发现的结果。
1.2 商业角度的定义
数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性数据。
简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身已经有很多年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另外，由于当时计算能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限制。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这些数据不再是为了分析的目的而收集的，而是由于纯机会的（Opportunistic）商业运作而产生。分析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提供真正有价值的信息，进而获得利润。但所有企业面临的一个共同问题是：企业数据量非常大，而其中真正有价值的信息却很少，因此从大量的数据中经过深层分析，获得有利于商业运作、提高竞争力的信息，就像从矿石中淘金一样，数据挖掘也因此而得名。
因此，数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有效的方法。
1.3 数据挖掘与传统分析方法的区别
数据挖掘与传统的数据分析(如查询、报表、联机应用分析)的本质区别是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识.数据挖掘所得到的信息应具有先未知,有效和可实用三个特征.
先前未知的信息是指该信息是预先未曾预料到的,既数据挖掘是要发现那些不能靠直觉发现的信息或知识,甚至是违背直觉的信息或知识,挖掘出的信息越是出乎意料,就可能越有价值.在商业应用中最典型的例子就是一家连锁店通过数据挖掘发现了小孩尿布和啤酒之间有着惊人的联系.
1.4数据挖掘不能干什么
DM 不能告诉你某个模型对你的企业的实际价值DM是一个工具，他只是帮助商业人士更深入、更容易地分析数据，但是无法告诉你某个模型对你的企业的实际价值，DM中得到的模型必须在现实生活中进行验证，DM不会在缺乏指导的情况下自动的发现模型。数据分析者必须知道你所选用的DM工具是如何工作的，采用的算法的原理是什么。DM永远不会替代有经验的商业分析师或管理人员所起的作用，它只是一个强大的工具。
2 数据挖掘的几种主要形式:
2.1:规则挖掘：
如果一个事务中含有X，则该事务中很可能含有Y。具体形式为{X}→{Y}，即通常可以描述为:当一个事务中顾客购买了一样东西{钢笔}(这里X=“钢笔”)则很可能他同时还购买了{墨水}(这里Y= "墨水")，这就是关联规则。在美国，有一种说法是:“尿不湿”和“啤酒”经常一起被购买。这种说法有其一定的现实意义:1)或许是该年龄段的经常喝啤酒的人刚好家庭开始养育小孩;2)或许是因为啤酒喝多，需要用尿不湿。然而不管怎样，如果没有数据挖掘中的关联规则在这里的应用，你是无论如何想象不出这样有点惊人的“笑话”。本文在后面将就该规则作一详细的阐述与讨论。
2.2聚类分析：
数据库中的记录可被化分为一系列有意义的子集，即聚类。聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括传统的模式识别方法和数学分类学。80年代初，Mchalski提出了概念聚类技术其要点是，在划分对象时不仅考虑对象之间的距离，还要求划分出的类具有某种内涵描述，从而避免了传统技术的某些片面性。
3 关于关联规则的讨论
3.1购物篮分析
关联规则挖掘的一个典型例子是购物篮分析。市场分析员要从大量的数据中发现顾客放入其购物篮中的不同商品之间的关系。如果顾客买牛奶，他也购买面包的可能性有多大？什么商品组或集合顾客多半会在一次购物时同时购买？例如，买牛奶的顾客有80%也同时买面包，或买铁锤的顾客中有70%的人同时也买铁钉，这就是从购物篮数据中提取的关联规则。分析结果可以帮助经理设计不同的商店布局。一种策略是：经常一块购买的商品可以放近一些，以便进一步刺激这些商品一起销售，例如，如果顾客购买计算机又倾向于同时购买财务软件，那么将硬件摆放离软件陈列近一点，可能有助于增加两者的销售。另一种策略是：将硬件和软件放在商店的两端，可能诱发购买这些商品的顾客一路挑选其他商品。
3.2 关联规则基本问题描述
关联规则是描述数据库中数据项之间存在的潜在关系的规则,形式为“A1∧A2∧...∧Am=>B1∧B2∧...∧Bn”,其中Ai(i=1,2,......,m),Bj(j=1,2,......,n)是数据库中的数据项.数据项之间的
关联规则即根据一个事务中某些项的出现,可推导出另一些项在同一事务中也出现.
挖掘关联规则的问题描述如下:
设: I={i1,i2......,im}是所有项目的集合. D是所有事务的集合(即数据库), 每个事务T是一些项目的集合, T包含在I中, 每个事务可以用唯一的标识符TID来标识. 设X为某些项目的集合,如果X包含在T中, 则称事务T包含X, 关联规则则表示为如下形式(X包含在T)=>(Y包含在T)的蕴涵式, 这里X 包含在I中, Y包含在I中, 并且X∧Y=Φ. 其意义在于一个事务中某些项的出现,可推导出另一些项在同一事务中也出现 (为简单化,将(X包含在T)=>(Y包含在T)表示为X=>Y, 这里,‘=>’称为‘关联’操作, X称为关联规则的先决条件, Y称为关联规则的结果).
事务集D中的规则X=>Y是由支持度s(support)和置信度c(confidence)约束,置信度表示规则的强度, 支持度表示在规则中出现的频度。数据项集X的支持度s(X)是D中包含X的事务数量与D的总事务数量之比, 但为下文便于叙述, 数据项集X的支持度是用数据库D中包含X的数量来表示;
规则X=>Y的支持度s定义为: 在D中包含X∪Y的事务所占比例为s%, 表示同时包含X和Y的事务数量与D的总事务量之比; 规则X=>Y的置信度c定义为: 在D中,c%的事务包含X的同时也包含Y, 表示D中包含X的事务中有多大可能性包含Y.
最小支持度阈值minsupport表示数据项集在统计意义上的最低主要性. 最小置信度阈值mincontinence表示规则的最低可靠性. 如果数据项集X满足X.support>=minsupport, 则X是大数据项集. 一般由用户给定最小置信度阈值
和最小支持度阈值.置信度和支持度大于相应阈值的规则称为强关联规则, 反之称为弱关联规则. 发现关联规则的任务就是从数据库中发现那些置信度、支持度大小等于给定值的强壮规则.
基于上述概念，我们可以很容易得到一些基本结论:
(1) K维数据项集X K是频繁项集的必要条件是它所有K-1维子项集也为频繁项集，记为X K-1
(2)如果K维数据项集X K的任意一个K-1维子集X K-1，不是频繁项集，则K 维数据项集X K本身也不是最大数据项集。
(3) X K是K维频繁项集，如果所有K-1维频繁项集集合X K-1中包含XK的K-1维子项集的个数小于K，则X K不可能是K维最大频繁数据项集。
证明:
很明显，数据项集X K-1:的K-1维子项集的个数为K-1。如果高频繁数据项集X K-1，中包含X K的K-1.维子项集的个数小于k，则存在X K的K-1维子项集不是频繁数据项集，由结论(2)知K维数据项集本身也不是高频繁数据项集。
3.3 关联规则挖掘举例
一个超级市场的销售系统记录了顾客购物的情况。表3-1中记录了5个顾客的购物单。
记录号所购物品清单
1 啤酒、尿布，婴儿爽身粉，面包，雨伞
2 尿布，婴儿爽身粉
3 啤酒、尿布，牛奶
4 尿布，啤酒，洗衣粉
5 啤酒，牛奶，可乐饮料
表3-1
超市经理想知道商品之间的关联，要求列出那些同时购买的、且支持度≥40%（即在5行中至少出现两次）的商品名称。 KDD 系统通过特定算法（例如著名的Apriori(验证)算法及或改进算法）多次扫描数据库，依次得出如表2和表3。其中支持度<2/5的项,如单项的{面包}，{雨伞}和 双项中的 {尿布，牛奶}等等已经略去，三项统计为空，其中只有 {啤酒，尿布,牛奶}出现了一次(表3-1中3号记录)，支持度小于40%,略去。
单项统计
支持度 {啤酒}
4/5 {尿布}
4/5 {婴儿爽身粉}
2/5 {牛奶} 2/5 表3-2 表3-3
从单项统计中看出80%的顾客买了啤酒、80%的顾客买了尿布。从双项统计中看出，60%的顾客同时买了啤酒和尿布，40%的顾客买了啤酒和牛奶，40%的顾客买了尿布和爽身粉。还可观察到买了啤酒顾客中又买了尿布的占0.6{啤酒，尿布}/0.8{啤酒}=75% (称为置信度)。于是可得出下列六条规则,其中：s 为支持度，c 为置信度。
R1：啤酒→尿布,S=60%，C=0.6/0.8=75%
R2：尿布→啤酒,S=60%，C=0.6/0.8=75%
R3：牛奶→啤酒, S=40%，C=0.4/0.4=100%
R4：啤酒→牛奶, S=40%，C=0.4/0.8=50%
R5：尿布→爽身粉。S=40%，C=0.4/0.8=50%
R6：婴儿爽身粉→尿布。S=40%，C=0.4/0.4=100%
双项统计 支持度 {啤酒，尿布} 3/5 {啤酒，牛奶} 2/5 {尿布，婴儿爽身粉} 2/5
KDD规则反映了物品之间的表面联系，不一定是现实世界的因果关系。规则是死的，人是活的，运用之妙成乎于人。例如，R6“婴儿爽身粉→尿布”有很高的置信度，是合理可理解的，R3有很高的置信度将提示进一步的调查分析，本例中是因为训练资料太少引起的失真。
3.4 关联规则问题的分解
关联规则挖掘问题可分解为以下两个子问题:
1.找出事务数据库D中所有大于等于用户指定最小支持度的项目集(itemset).
具有最小支持度的项目集称为最大项目集.项目集的支持度指包含该项目集的数目.
2.利用最大项目集生成所需要的关联规则
对每一最大项目集A,找到A的所有非空子集a,如果比率support(A)/support(a)>=minconfidence,就生成关联规则a=>(A-a).support(A)/support(a) 即规则a=>(A-a)的置信度.
事实上,挖掘关联规则的整个执行过程中第一个子问题是核心问题.当找到所有的最大项目集后,相应的关联规则将很容易生成.在本文中将对关联规则的第一个问题进行探讨、研究。
4 Apriori算法的描述
4.1 Apriori算法的说明
在Apriori算法中,寻找最大项目集的基本思想是: 算法需要对数据集进行多步处理.第一步,简单统计所有含一个元素项目集出现的频率,并找出那些不小于最小支持度的项目集, 即一维最大项目集. 从第二步开始循环处理直到再没
有最大项目集生成. 循环过程是: 第k步中, 根据第k-1步生成的(k-1)维最大项目集产生k维侯选项目集, 然后对数据库进行搜索, 得到侯选项目集的项集支持度, 与最小支持度比较, 从而找到k维最大项目集.
为方便后文叙述，现约定如下:
1.数据库事务中的项目都是以字母顺序排列的,每个项目用
2.每个项目集的项目数称为该项目集的size. 当项目集的size=k时, 称该项目集为k-itemset(k维项目集).
下文中遇到的以下符号,分别代表相应的内容
k-itemset k维项目集
Lk 具有最小支持度的最大k-itemset
Ck 侯选的k-itemsets(潜在的最大项目集)
4.2 Apriori算法的描述
Apriori算法的第一步是简单统计所有含一个元素的项集出现的频率,来决定最大的一维项目集.在第k步,分两个阶段,首先用一函数sc_candidate(候选),通过第(k-1)步中生成的最大项目集Lk-1来生成侯选项目集Ck. 然后搜索数据库计算侯选项目集Ck的支持度. 为了更快速地计算Ck中项目的支持度, 文中使用函数count_support计算支持度.
Apriori算法描述如下
(1) C1={candidate1-itemsets};
(2) L1={c∈C1|c.count≥minsupport};
(3) For(k=2,Lk-1≠Φ,k++) //直到不能再生成最大项目集为止
(4) Ck=sc_candidate(Lk-1); //生成含k个元素的侯选项目集
(5) for all transactions t∈D //办理处理
(6) Ct=count_support(Ck,t); //包含在事务t中的侯选项目集
(7) for all candidates c∈Ct
(8) c.count=c.count+1;
(9) next
(10) Lk={c∈Ck|c.count≥minsupport};
(11) next
(12) resultset=resultset∪Lk
其中, D表示数据库; minsupport表示给定的最小支持度; resultset表示所有最大项目集.
Sc_candidate函数
该函数的参数为Lk-1,即: 所有最大k-1维项目集,结果返回含有k个项目的侯选项目集Ck.事实上,Ck是k维最大项目集的超集,通过函数count_support计算项目的支持度,然后生成Lk.
该函数是如何完成这些功能的, 详细说明如下:
首先, 通过对Lk-1自连接操作生成Ck',称join(连接)步,
该步可表述为:
insert into Ck
selectP.item1,P.item2,......P.itemk-1,Q.itemk-1 from Lk-1P,Lk-1Q whereP.item1=Q.item1,......P.itemk-2=Q.itemk-2,P.itemk-1 若用集合表示:Ck'={X∪X'|X,X'∈Lk-1,|X∩X'|=k-2} 然后,是prune(修剪)步,即对任意的c,c∈Ck, 删除Ck中所有那些(k-1)维子集不在Lk-1中的项目集,得到侯选项目集Ck.表述为: for all itemset c∈Ck for all (k-1)维子集s of c if (s不属于Lk-1) then delete c from Ck; 用集合表示:Ck=={X∈Ck'|X的所有k-1维子集在Lk-1中} 在此函数中需要说明以下几点: (1) 最大项目集的子集必为最大项目集. 这是该算法中隐含的最基本的一条性质. 因为最大项目集定义为不小于最小支持度(minsupport)的项目集. 若最大项目集为c, 则即c.count>=minsupport, 若c的子集为c', 则c'.count必然大于等于minsupport. 所以c'也为最大项目集. (2) 在prune步中, 删除Ck'中那些所有k-1维子集不在Lk-1中的项目集, (其中k-1维子集为Ck的所有项目数为k-1的子集). 这里用了(1)中的性质: 最大项目集的子集必为最大项目集. 即若某项目集的(k-1)维子集不是最大项目集(Lk-1中包含所有k-1维最大项目集), 则该项目集不是最大项目集. 所以将删除Ck'中所有不在Lk-1中的k-1维子集. count_support函数 count_support函数为是以t和 Ck 为条件. 来求出t 中所包含的侯选项目集的. 同时计算出所包含的侯选项目集的数目. 4.3 Apriori算法的举例 示例说明Apriori算法运作过程 有一数据库D, 其中有四个事务记录, 分别表示为 TID Items T1I1,I3,I4 T2I2,I3,I5 T3I1,I2,I3,I5 T4I2,I5 在Apriori算法中每一步创建该步的侯选集.统计每个侯选项目集的支持度,并和预定义的最小支持度比较,来确定该步的最大项目集. 首先统计出一维项目集,即:C1.这里预定义最小支持度minsupport=2,侯选项目集中满足最小支持度要求的项目集组合成最大的1-itemsets.为生成最大的2-itemsets,使用了sc_candidate函数中join步,即: L1joinL1,并通过prune 步删除那些C2的那些子集不在L1中的项目集.生成了侯选项目集C2.搜索D中4个事务,统计C2中每个侯选项目集的支持度.然后和最小支持度比较,生成L2.侯选项目集C3是由L2生成.要求自连接的两个最大2-itemsets中,第一个项目相同,在L2中满足该条件的有{I2,I3},{I2,I5}.这两个集合经过join步后, 产生集合{I2，I3，I5}.在prune步中,测试{I2，I3，I5}的子集{I3，I5},{I2，I3},{I2，I5}是否在L2中,由L2可以知道{I3,I5},{I2,I3},{I2,I5}本身就是最大2-itemsets.即{I2,I3,I5}的子集都是最大项目集.那么{I2,I3,I5}为侯选3-itemset.然后搜索数据库中所有事务记录,生成最大的3-tiemsets L3. 此时, 从L3中不能再生成侯选4-itemset .Apriori算法结束. 算法的图例说明 从以上的算法执行过程可以看到Apriori算法的缺点: 第一:在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素;第二:每次计算项集的支持度时，都对数据库D中的全部记录进行了一 遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系 统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求一种能减少这种系统1/O开销的更为快捷的算法。 5 一种Apriori的改进算法 5.1算法产生的思路 在Apriori算法中，寻找最大项目集的基本思路是:第一步简单统计所有含一个元素的项目出现的频率，并找出那些大于或等于最小支持度的项目集，产生一维频繁项目集Lt。从第二步开始循环处理直到未能再产生维数更高的频繁项目集。循环过程是:在第k步中，根据k-1步生成的k-1维频繁项目集来产生k 维候选项目集，由于在产生k-1维频繁项目集时，我们可以实现对该集中出现元素的个数进行计数处理，因此对某元素而言，若它的计数个数不到k-1的话，可以事先删除该元素，从而排除由该元素将引起的大规格所有组合。这是因为对某一个元素要成为K维项目集的一元素的话，该元素在k-1阶频繁项目集中的计数次数必须达到K-1个，否则不可能生成K维项目集(性质3)。然后再按Apriori 算法再检验新的K 维频繁项目集的所有k-1维项目集是否已经包含在已经求出的K-1维频繁项目集。若其中有一个没有包含，则也可删去该组合，这样得到一个真正有用的K维频繁项目集选项目集。得到了这个候选项目集后，可以对数据库D的每一个事务tid进行扫描，若该事务中至少含有候选项目集CK中的一员，则保留该项事务，否则把该事物记录与数据库末端没有作删除标记的事务记录对换，并对移到数据库末端的事务记录作删除标一记，整个数据库扫描完毕后为新的事务数据库D’中。因此随着K 的增大，D’中事务记录量大大地减少，对于下一次事务扫描可以大大节约I/0 开销。由于顾客一般可能一次只购买几件商品，因此这种虚拟删除的方法可以实现大量的交易记录在以后的挖掘中被踢除出来， 在所剩余的不多的记录中再作更高维的数据挖掘是可以大大地节约时间的。5.2算法的图例说明 5.3本算法的评价: 通过上述介绍，我们可以看到本算法的思路基本上与Apriori算法保持一致，即它们的共同之处是首先通过扫描数据库D得到那些支持度不小于用户给定的最小支持度minsup的频繁项集L1。然后同样通过多次循环扫描数据库D，分别得到频繁项集L2,L3, . . . ,Lk。但是又有不同之处。第一，改进的算法在 考虑组合Ck前，对将参与组合的元素进行计数处理，根据计数结果决定排除一些不符合组合条件的元素，这就降低了组合的可能性，即降低循环判断的次数。如果对大型的数据库而言，这种时间开销的降低对数据挖掘效率来说是显而易见的，这是Apriori方法中没有涉及的;第二，改进的算法对数据库进行了扫描后的重新生成(‘删除’一些不能支持频繁集的记录，这里所谓的删除实际上是把不符合再次扫描比较条件的记录通过交换记录内容的方式移到数据库的末端，把末端新记录填入该记录的位置。同时对数据库中的记录数逻辑地减少。)，虽然会在记录重写中浪费时间和I/O的开销，但是随着循环次数的增加，本算法对以后在‘新生成的数据库’中的扫描比较次数很快减少将逐渐体现出来。从数据挖掘工具的评价标准（1.模式种类的数量，2.解决复杂问题的能力，3.操作性能，4.数据获取能力，5挖掘结果的输出，6.噪声数据的处理及挖掘工具的鲁棒性）来看，本算法可以达到较高的标准;从算法效率的角度来看，本算法的挖掘效率也是较高的。因此本文认为，这种方法在实践应用中也是值得使用的。 参考文献 [1]（加）Jiawei Han,Micheline Kamber著.范明等译.数据挖掘：概念与技术.北京：机械工业出版社，2001.8 [2] 陈京民数据仓库与数据挖掘技术 2002.北京电子工业出版社 [3] 颜雪松、蔡之华一种基于Apriori的高效关联规则挖掘算法的研究计算机工程与应用 2002.10 1002-8331一(2002) 10-0209-03 209-211 [4] 李绪成，王保保挖掘关联规则中Apriori算法的一种改进计算机工程2002.7 第28卷 104-105 [5] 毛秉毅一种新的关联规则发现算法及应用研究计算机应用与工程 2002.22 [6] Peter Cabena, Discovering Data Mining From Concept to Implementation，IBM, 1997 Apriori算法改进及其实现 内容摘要 信息技术的不断推广应用，将企业带入了一个信息爆炸的时代。如何充分利用这些数据信息为企业决策者提供决策支持成为一个十分迫切的又棘手的问题，人们除了利用现有的关系数据库标准查询语句得到一般的直观的信息以外，必须挖掘其内含的、未知的却又实际存在的数据关系。著名的Apriori算法是一种挖掘关联规则的算法。 本文通过对参与候选集的元素计数的方法来减少产生候选集的组合和减少数据库的扫描次数来达到要求。这有利于提高挖掘的速度和减少数据库的I/O 操作时间的开销。 关键字：数据挖掘，关联规则，Apriori算法 Apriori Algorithm And Improved Apriori Algorithm Abstract：An information burst age is coming with the various application of Information technology. How to maximize the information is a very important problem for the decision-maker of the companies. Besides getting the regular information from the Database by SQL-query, people still need to mine the data relation which is unclear but really exists.Association rules is one of the data mining methods, the famous algorithm Apriori is a method, which can be used to solute those problems. This article analyzes and studies the improved algorithm Apriori based on the algorithm of mining association rules Apriori. The main idea is to decrease the number of candidate items and to decrease the times of Database scanning. The solution is available. It upgrades the speed of data mining and decreases computer's I/O operation. It's proved to be more efficient than the traditional Key words: Datamining, association rules, Apriori algorithm, 1 Apriori介绍 Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做L1，然后利用L1找频繁2项集的集合L2，L2找L3，如此下去，直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。 其中，Apriori算法具有这样一条性质：任一频繁项集的所有非空子集也必须是频繁的。因为假如P(I)< 最小支持度阈值，当有元素A添加到I中时，结果项集（A∩I）不可能比I 出现次数更多。因此A∩I也不是频繁的。 2连接步和剪枝步 在上述的关联规则挖掘过程的两个步骤中，第一步往往是总体性能的瓶颈。Apriori算法采用连接步和剪枝步两种方式来找出所有的频繁项集。 1）连接步 为找出L k（所有的频繁k项集的集合），通过将L k-1（所有的频繁k-1项集的集合）与自身连接产生候选k项集的集合。候选集合记作C k。设l1和l2是L k-1中的成员。记l i[j]表示l i中的第j项。假设Apriori算法对事务或项集中的项按字典次序排序，即对于（k-1）项集l i，l i[1] Apriori算法实验报告 1背景 关联规则挖掘的研究工作主要包括：Apriori算法的扩展、数量关联规则挖掘、关联规则增量式更新、无须生成候选项目集的关联规则挖掘、最大频繁项目集挖掘、约束性关联规则挖掘以及并行及分布关联规则挖掘算法等，其中快速挖掘与更新频繁项目集是关联规则挖掘研究的重点，也是多种数据挖掘应用中的技术关键，已用于分类规则挖掘和网络入侵检测等方面的研究。研究者还对数据挖掘的理论进行了有益的探索，将概念格和粗糙集应用于关联规则挖掘中，获得了显著的效果。到目前为止，关联规则的挖掘已经取得了令人瞩目的成绩，包括：单机环境下的关联规则挖掘算法；多值属性关联规则挖掘；关联规则更新算法；基于约束条件的关联规则挖掘；关联规则并行及分布挖掘算法等。 2 算法描述 Apriori算法是一种找频繁项目集的基本算法。其基本原理是逐层搜索的迭代：频繁K项L k 集用于搜索频繁(K+1)项集L k+1，如此下去，直到不能找到维度更高的频繁项集为止。这种方法依赖连接和剪枝这两步来实现。 算法的第一次遍历仅仅计算每个项目的具体值的数量，以确定大型l项集。随后的遍历，第k 次遍历，包括两个阶段。首先，使用在第(k-1)次遍历中找到的大项集L k-1和用Aprioir-gen函数产生候选项集C k。接着扫描数据库，计算C k中候选的支持度。用Hash树可以有效地确定C k中包含在一个给定的事务t中的候选。算法如下： (1) L1 = {大项目集1项目集}; (2) for (k = 2; L k-1 != 空; k++) do begin (3) C k = apriori-gen(L k-1); //新的候选集 (4) for 所有事务t ∈D do begin (5) C t = subset ( C k，t); //t中所包含的候选 (6) for 所有候选 c ∈C t do (7) c.count++; (8) end (9) L k = {c ∈C k | c.count ≥ minsupp} (10) end (11) key = ∪L k； Apriori-gen函数： Apriori候选产生函数Apriori-gen的参数L k-1，即所有大型(k-1)项目集的集合。它返回所有大型k项目集的集合的一个超集(Superset)。首先，在Jion(连接)步骤，我们把L k-1和L k-1相连接以获得候选的最终集合的一个超集C k： Apriori ['e?pr?'?:r?] Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。而且算法已经被广泛的应用到商业、网络安全等各个领域。 其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。 经典的关联规则数据挖掘算法Apriori 算法广泛应用于各种领域，通过对数据的关联性进行了分析和挖掘，挖掘出的这些信息在决策制定过程中具有重要的参考价值。 Apriori算法广泛应用于商业中，应用于消费市场价格分析中，它能够很快的求出各种产品之间的价格关系和它们之间的影响。通过数据挖掘，市场商人可以瞄准目标客户，采用个人股票行市、最新信息、特殊的市场推广活动或其他一些特殊的信息手段，从而极大地减少广告预算和增加收入。百货商场、超市和一些老字型大小的零售店也在进行数据挖掘，以便猜测这些年来顾客的消费习惯。 Apriori算法应用于网络安全领域，比如网络入侵检测技术中。早期中大型的电脑系统中都收集审计信息来建立跟踪档，这些审计跟踪的目的多是为了性能测试或计费，因此对攻击检测提供的有用信息比较少。它通过模式的学习和训练可以发现网络用户的异常行为模式。采用作用度的Apriori算法削弱了Apriori算法的挖掘结果规则，是网络入侵检测系统可以快速的发现用户的行为模式，能够快速的锁定攻击者，提高了基于关联规则的入侵检测系统的检测性。 Apriori算法应用于高校管理中。随着高校贫困生人数的不断增加，学校管理部门资助工作难度也越加增大。针对这一现象，提出一种基于数据挖掘算法的解决方法。将关联规则的Apriori算法应用到贫困助学体系中，并且针对经典Apriori挖掘算法存在的不足进行改进，先将事务数据库映射为一个布尔矩阵，用一种逐层递增的思想来动态的分配内存进行存储，再利用向量求"与"运算，寻找频繁项集。实验结果表明，改进后的Apriori算法在运行效率上有了很大的提升，挖掘出的规则也可以有效地辅助学校管理部门有针对性的开展贫困助学工作。 Apriori算法被广泛应用于移动通信领域。移动增值业务逐渐成为移动通信市场上最有活力、最具潜力、最受瞩目的业务。随着产业的复苏，越来越多的增值业务表现出强劲的发展势头，呈现出应用多元化、营销品牌化、管理集中化、合作纵深化的特点。针对这种趋势，在关联规则数据挖掘中广泛应用的Apriori 算法被很多公司应用。依托某电信运营商正在建设的增值业务Web数据仓库平台，对来自移动增值业务方面的调查数据进行了相关的挖掘处理，从而获得了关于用户行为特征和需求的间接反映市场动态的有用信息，这些信息在指导运营商的业务运营和辅助业务提供商的决策制定等方面具有十分重要的参考价值。 /* 这个程序是数据挖掘中的Apriori算法*/ #include Apriori算法例子 Apriori算法例子 算法integerstringeach数据库c 1 Apriori介绍 Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做L1，然后利用L1找频繁2项集的集合L2，L2找L3，如此下去，直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。 其中，Apriori算法具有这样一条性质：任一频繁项集的所有非空子集也必须是频繁的。因为假如P(I)< 最小支持度阈值，当有元素A添加到I中时，结果项集（A∩I）不可能比I 出现次数更多。因此A∩I也不是频繁的。 2 连接步和剪枝步 在上述的关联规则挖掘过程的两个步骤中，第一步往往是总体性能的瓶颈。Apriori算法采用连接步和剪枝步两种方式来找出所有的频繁项集。 1）连接步 为找出Lk（所有的频繁k项集的集合），通过将Lk-1（所有的频繁k-1项集的集合）与自身连接产生候选k项集的集合。候选集合记作Ck。设l1和l2是Lk-1中的成员。记li[j]表示li中的第j项。假设Apriori算法对事务或项集中的项按字典次序排序，即对于（k-1）项集li， li[1]<li[2]<……….<li[k-1]。将Lk-1与自身连接，如果(l1[1]=l2[1])&&( l1[2]=l2[2])&&……..&a mp;& (l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])，那认为l1和l2是可连接。连接l1和l2 产生的结果是 {l1[1],l1[2],……,l1[k-1],l2[k-1]}。 2）剪枝步 CK是LK的超集，也就是说，CK的成员可能是也可能不是频繁的。通过扫描所有的事务（交易），确定CK中每个候选的计数，判断是否小于最小支持度计数，如果不是，则认为该候选是频繁的。为了压缩Ck,可以利用Apriori性质：任一频繁项集的所有非空子集也必须是频繁的，反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。 （Tip：为什么要压缩CK呢？因为实际情况下事务记录往往是保存在外存储上，比如数据库或者其他格式的文件上，在每次计算候选计数时都需要将候选与所有事务进行比对，众所周知，访问外存的效率往往都比较低，因此Apriori加入了 Apriori算法例子 1 Apriori介绍 Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做L1，然后利用L1找频繁2项集的集合L2，L2找L3，如此下去，直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。 其中，Apriori算法具有这样一条性质：任一频繁项集的所有非空子集也必须是频繁的。因为假如P(I)< 最小支持度阈值，当有元素A添加到I中时，结果项集（A∩I）不可能比I出现次数更多。因此A∩I也不是频繁的。 2连接步和剪枝步 在上述的关联规则挖掘过程的两个步骤中，第一步往往是总体性能的瓶颈。Apriori 算法采用连接步和剪枝步两种方式来找出所有的频繁项集。 1）连接步 为找出L k（所有的频繁k项集的集合），通过将L k-1（所有的频繁k-1项集的集合）与自身连接产生候选k项集的集合。候选集合记作C k。设l1和l2是L k-1中的成员。记l i[j]表示l i中的第j项。假设Apriori算法对事务或项集中的项按字典次序排序，即对于（k-1）项集l i，l i[1] matlab 实现apriori 算法源代码 一、实验目的 通过实验，加深数据挖掘中一个重要方法——关联分析的认识，其经典算法为apriori 算法，了解影响apriori 算法性能的因素，掌握基于apriori 算法理论的关联分析的原理和方法。 二、实验内容 对一数据集用apriori 算法做关联分析，用matlab 实现。 三、方法手段 关联规则挖掘的一个典型例子是购物篮分析。市场分析员要从大量的数据中发现顾客放入其购物篮中的不同商品之间的关系。如果顾客买牛奶，他也购买面包的可能性有多大？ 什么商品组或集合顾客多半会在一次购物时同时购买？例如，买牛奶的顾客有80%也同时买面包，或买铁锤的顾客中有70%的人同时也买铁钉，这就是从购物篮数据中提取的关联规则。分析结果可以帮助经理设计不同的商店布局。一种策略是：经常一块购买的商品可以放近一些，以便进一步刺激这些商品一起销售，例如，如果顾客购买计算机又倾向于同时购买财务软件，那么将硬件摆放离软件陈列近一点，可能有助于增加两者的销售。另一种策略是：将硬件和软件放在商店的两端，可能诱发购买这些商品的顾客一路挑选其他商品。 关联规则是描述数据库中数据项之间存在的潜在关系的规则,形式为 1212 ......m n A A A B B B ∧∧∧?∧∧∧,其中(1,2...,)i A i m =,(1,2...,)j A j n =是数据库中的数据项.数据项之间的关联规则即根据一个事务中某些项的出现,可推导出另一些项在同一事务中也出现。 四、Apriori 算法 1.算法描述 Apriori 算法的第一步是简单统计所有含一个元素的项集出现的频率,来决定最大的一维项目集。在第k 步,分两个阶段,首先用一函数sc_candidate(候选),通过第(k-1)步中生成的最大项目集L k-1来生成侯选项目集C k 。然后搜索数据库计算侯选项目集C k 的支持度. 为了更快速地计算C k 中项目的支持度, 文中使用函数count_support 计算支持度。 Apriori 算法描述如下： (1) C 1={candidate1-itemsets}; (2) L 1={c ∈C 1|c.count ≥minsupport}; (3) for(k=2,L k-1≠Φ,k++) //直到不能再生成最大项目集为止 (4) C k =sc_candidate(L k-1); //生成含k 个元素的侯选项目集 (5) for all transactions t ∈D //办理处理 (6) Ct=count_support(C k ,t); //包含在事务t 中的侯选项目集 (7) for all candidates c ∈C t (8) c.count=c.count+1; (9) next (10) L k ={c ∈C k |c.count ≥minsupport}; (11) next (12) resultset=resultset ∪L k 其中, D 表示数据库；minsupport 表示给定的最小支持度；resultset 表示所有最大项目集。 《数据挖掘》设计论文 院（系）理学院 专业信息与计算科学 指导老师刘建伟 班级 101001班 姓名龙云祥、黄健 时间 2013年7月4日 Apriori算法及其实现 内容摘要 经典的关联规则数据挖掘算法Apriori 算法广泛应用于各种领域，通过对数据的关联性进行了分析和挖掘，挖掘出的这些信息在决策制定过程中具有重要的参考价值。信息技术的不断推广应用，如何充分利用这些数据信息为各个行业决策者提供决策支持成为一个十分迫切的又棘手的问题，人们除了利用现有的关系数据库标准查询语句得到一般的直观的信息以外，必须挖掘其内含的、未知的却又实际存在的数据关系。著名的Apriori算法是一种挖掘关联规则的算法。 本文通过对Apriori算法的基本思想，挖掘出内含的数据关系，并实现Apriori算法。 关键字：数据挖掘，关联规则，Apriori算法 目录 1 人员分工.................................................................................................................................. - 1 - 2 数据挖掘定义.......................................................................................................................... - 1 - 3 关联规则介绍.......................................................................................................................... - 3 - 4 Apriori算法背景介绍........................................................................................................... - 3 - 5 Apriori算法的描述............................................................................................................... - 5 - 5.1 Apriori算法的说明................................................................................................... - 5 - 4.2 Apriori算法的描述................................................................................................... - 6 - 4.3 Apriori算法的举例................................................................................................... - 6 - 6 设计要求.................................................................................................................................. - 7 - 7 设计原理.................................................................................................................................. - 7 - 8 程序流程图.............................................................................................................................. - 8 - 9 程序运行环境.......................................................................................................................... - 8 - 10 测试数据................................................................................................................................ - 8 - 11 程序运行结果........................................................................................................................ - 9 - 12 参考资料.............................................................................................................................. - 10 -13设计总结............................................................................................................................... - 11 - 13.1黄健总结................................................................................................................... - 11 - 13.2龙云祥总结............................................................................................................... - 11 -14程序源代码见附录1............................................................................................................ - 11 - 一、Apriori算法简介：Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。Apriori（先验的，推测的）算法应用广泛，可用于消费市场价格分析，猜测顾客的消费习惯；网络安全领域中的入侵检测技术；可用在用于高校管理中，根据挖掘规则可以有效地辅助学校管理部门有针对性的开展贫困助学工作；也可用在移动通信领域中，指导运营商的业务运营和辅助业务提供商的决策制定。 二、挖掘步骤： 1.依据支持度找出所有频繁项集（频度） 2.依据置信度产生关联规则（强度） 三、基本概念 对于A->B ①支持度：P(A ∩B)，既有A又有B的概率 ②置信度： P(B|A)，在A发生的事件中同时发生B的概率p(AB)/P(A)例如购物篮分析：牛奶?面包 例子：[支持度：3%，置信度：40%] 支持度3%：意味着3%顾客同时购买牛奶和面包 置信度40%：意味着购买牛奶的顾客40%也购买面包 ③如果事件A中包含k个元素，那么称这个事件A为k项集事件A满足最小支持度阈值的事件称为频繁k项集。 ④同时满足最小支持度阈值和最小置信度阈值的规则称为强规则 四、实现步骤 Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法Apriori使用一种称作逐层搜索的迭代方法，“K-1项集”用于搜索“K项集”。 首先，找出频繁“1项集”的集合，该集合记作L1。L1用于找频繁“2项集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K项集”。找每个Lk都需要一次数据库扫描。 核心思想是：连接步和剪枝步。连接步是自连接，原则是保证前k-2项相同，并按照字典顺序连接。剪枝步，是使任一频繁项集的所有非空子集也必须是频繁的。反之，如果某 个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。 简单的讲，1、发现频繁项集，过程为（1）扫描（2）计数（3）比较（4）产生频繁项集（5）连接、剪枝，产生候选项集重复步骤（1）~（5）直到不能发现更大的频集 2、产生关联规则，过程为:根据前面提到的置信度的定义，关联规则的产生如下： （1）对于每个频繁项集L，产生L的所有非空子集； （2）对于L的每个非空子集S，如果 P（L）/P（S）≧min_conf 则输出规则“SàL-S” 注：L-S表示在项集L中除去S子集的项集 #ifndef APRIRORI_H #define APRIRORI_H #include Apriori算法实验报告 学号： 姓名： 专业：计算机应用技术 教师： 计算机学院 目录 1 APRIORI实验 (1) 1.1实验背景 (1) 1.1.1 国内外研究概况 (1) 1.1.2 发展趋势 (1) 1.2实验内容与要求 (1) 1.2.1 实验内容 (1) 1.2.2 实验要求 (1) 1.2.3 实验目的 (2) 2 APRIORI算法分析与实验环境 (3) 2.1A PRIORI算法的描述 (3) 2.2A PRIORI算法的步骤 (3) 2.3开发环境 (3) 2.3.1 软件环境 (3) 2.3.2 硬件环境 (4) 2.4本章小结 (4) 3 算法的设计 (5) 3.1A PRIORI算法整体框架 (5) 3.2主要的数据结构与函数 (5) 3.2.1 数据结构 (5) 3.2.2 主要的程序 (6) 3.2.3 连接与剪枝操作 (6) 3.3本章小结 (6) 4 数据库的设计与数据的来源 (7) 4.1正确性验证数据 (7) 4.2实验数据 (7) 4.3本章小结 (8) 5 实验结果与性能分析 (9) 5.1A PRIORI实验界面 (9) 5.2实验的正确性验证 (9) 5.3实验性能分析 (10) 5.3.1固定最小支持度改变数据量 (10) 5.3.2固定数据量改变最小支持度 (11) 5.3.3实验结果分析 (11) 5.4本章小结 (12) 6 总结与体会 (13) 1 Apriori实验 1.1 实验背景 现在, 数据挖掘作为从数据中获取信息的有效方法, 越来越受到人们的重视。关联规则挖掘首先是用来发现购物篮数据事务中各项之间的有趣联系。从那以后, 关联规则就成为数据挖掘的重要研究方向,它是要找出隐藏在数据间的相互关系。目前关联规则挖掘的研究工作主要包括：Apriori算法的扩展、数量关联规则挖掘、关联规则增量式更新、无须生成候选项目集的关联规则挖掘、最大频繁项目集挖掘、约束性关联规则挖掘以及并行及分布关联规则挖掘算法等。关联规则的挖掘问题就是在事务数据库D中找出具有用户给定的满足一定条件的最小支持度Minsup和最小置信度Minconf的关联规则。 1.1.1 国内外研究概况 1993年，Agrawal等人首先提出关联规则概念，关联规则挖掘便迅速受到数据挖掘领域专家的广泛关注.迄今关联规则挖掘技术得到了较为深入的发展。Apriori算法是关联规则挖掘经典算法。针对该算法的缺点，许多学者提出了改进算法，主要有基于哈希优化和基于事务压缩等。 1.1.2 发展趋势 关联规则挖掘作为数据挖掘的重要研究内容之一, 主要研究事务数据库、关系数据库和其他信息存储中的大量数据项之间隐藏的、有趣的规律。关联规则挖掘最初仅限于事务数据库的布尔型关联规则, 近年来广泛应用于关系数据库, 因此, 积极开展在关系数据库中挖掘关联规则的相关研究具有重要的意义。近年来,已经有很多基于Apriori 算法的改进和优化。研究者还对数据挖掘的理论进行了有益的探索，将概念格和粗糙集应用于关联规则挖掘中，获得了显著的效果。到目前为止，关联规则的挖掘已经取得了令人瞩目的成绩，包括：单机环境下的关联规则挖掘算法；多值属性关联规则挖掘；关联规则更新算法；基于约束条件的关联规则挖掘；关联规则并行及分布挖掘算法等。 1.2 实验内容与要求 1.2.1 实验内容 编程实现Apriori算法：要求使用‘a’,‘b’,‘c’,‘d’,‘e’,‘f’,‘g’,‘h’,‘i’,‘j’10个项目随机产生数据记录并存入数据库。从数据库读取记录进行Apriori实验，获得频繁集以及关联规则，实现可视化。并用课堂上PPT的实例测试其正确性。 1.2.2 实验要求 1、程序结构：包括前台工具和数据库； 2、设定项目种类为10个，随机产生事务，生成数据库； 3、正确性验证（可用课堂上的例子）； 4、算法效率的研究：在支持度固定数据量不同的时候测量运行时间；在数据量固定，支持度不同的时候测量运行时间； 5、注意界面的设计，输入最小支持度和最小可信度，能够输出并显示频繁项目集以及关联规则。 Apriori算法详解之【一、相关概念和核心步骤】 Apriori算法核心步骤 感谢红兰整理的PPT，简单易懂，现在将其中精彩之处整理，与大家分享。 一、Apriori算法简介：Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。Apriori（先验的，推测的）算法应用广泛，可用于消费市场价格分析，猜测顾客的消费习惯；网络安全领域中的入侵检测技术；可用在用于高校管理中，根据挖掘规则可以有效地辅助学校管理部门有针对性的开展贫困助学工作；也可用在移动通信领域中，指导运营商的业务运营和辅助业务提供商的决策制定。 二、挖掘步骤： 1.依据支持度找出所有频繁项集（频度） 2.依据置信度产生关联规则（强度） 三、基本概念 对于A->B ①支持度：P(A ∩B)，既有A又有B的概率 ②置信度： P(B|A)，在A发生的事件中同时发生B的概率p(AB)/P(A)例如购物篮分析：牛奶?面包 例子：[支持度：3%，置信度：40%] 支持度3%：意味着3%顾客同时购买牛奶和面包 置信度40%：意味着购买牛奶的顾客40%也购买面包 ③如果事件A中包含k个元素，那么称这个事件A为k项集事件A满足最小支持度阈值的事件称为频繁k项集。 ④同时满足最小支持度阈值和最小置信度阈值的规则称为强规则 四、实现步骤 Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法Apriori使用一种称作逐层搜索的迭代方法，“K-1项集”用于搜索“K项集”。 首先，找出频繁“1项集”的集合，该集合记作L1。L1用于找频繁“2项集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K项集”。找每个Lk都需要一次数据库扫描。 核心思想是：连接步和剪枝步。连接步是自连接，原则是保证前k-2项相同，并按照字典顺序连接。剪枝步，是使任一频繁项集的所有非空子集也必须是频繁的。反之，如果某 个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。 简单的讲，1、发现频繁项集，过程为（1）扫描（2）计数（3）比较（4）产生频繁项集（5）连接、剪枝，产生候选项集重复步骤（1）~（5）直到不能发现更大的频集 2、产生关联规则，过程为:根据前面提到的置信度的定义，关联规则的产生如下： （1）对于每个频繁项集L，产生L的所有非空子集； （2）对于L的每个非空子集S，如果 Apriori算法研究 Apriori算法是一个挖掘关联规则的算法，是Agrawal等设计的一个基本算法。它采用两阶段挖掘的思想，并且基于多次扫描事务数据库来执行。 1.关联规则 1.1.基本概念 关联规则是形如X →Y 的蕴涵式，表示通过X 可以推导“得到”Y ，其中X 和Y 分别称为关联规则的先导(antecedent 或left-hand-side, LHS) 和后继(consequent 或right-hand-side, RHS)。 关联规则A->B 的支持度support=P(AB) ，指的是事件 A 和事件B 同时发生的概率。 置信度confidence=P(B|A)=P(AB)/P(A), 指的是发生事件 A 的基础上发生事件 B 的概率。 同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。 如果事件 A 中包含k 个元素，那么称这个事件 A 为k 项集，并且事件 A 满足最小支持度阈值的事件称为频繁k 项集。 1.2.挖掘过程 第一，找出所有的频繁项集；其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。 第二，由频繁项集产生强规则。其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称为强规则。 通常，频繁项集产生的计算开销远大于产生规则所需的计算开销。 2.Apriori算法思想 Apriori 算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k 项集用于探索(k+1) 项集。首先，通过扫描事务（交易）记录，找出所有的频繁1 项集，该集合记做L1 ，然后利用L1 找频繁 2 项集的集合L2 ，L2 找L3 ，如此下去，直到不能再找到任何频繁k 项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。 其中，Apriori 算法具有这样一条性质：任一频繁项集的所有非空子集也必须是频繁的。因为假如P(I)< 最小支持度阈值，当有元素 A 添加到I 中时，结果项集（ A ∩I ）不可能比I 出现次数更多。因此A ∩I 也不是频繁的。 该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最Apriori算法
Apriori算法及java实现
Apriori算法实验报告
Apriori算法总结
数据挖掘中的Apriori算法(C语言版)
Apriori算法例子
Apriori算法例子
matlab实现apriori算法源代码
Apriori算法及其实现
Apriori算法详解之【一、相关概念和核心步骤】
Apriori算法C语言源代码实现
Apriori算法实验报告材料及程序
Apriori算法详解
Apriori算法研究