当前位置:文档之家› 对Apriori算法的改进及其实现研究

对Apriori算法的改进及其实现研究

对Apriori算法的改进及其实现研究
对Apriori算法的改进及其实现研究

总第254期计算机与数字丁程V01.38N o.12 2010年第12期C om p ut er&D i gi t al Engi nee r i ng24

对A pr i or i算法的改进及其实现研究‘

郑继刚

(保山学院数学系保山678000)

摘要传统的关联规则挖掘A pr i or i算法时间开销大,针对A pr i or i算法的不足之处,基于关系代数理论,利用关系矩阵及相关运算给出了搜索频繁项集的基于关系代数理论的关联规则挖掘(()R A R)算法。利用关系矩阵只需扫描数据库一次。以降低算法运行时间,挖掘频繁项集,最后通过仿真实验比较这两个算法的执行时间,讨论了数据样本量和最小支持度对算法性能的影响。通过大量的仿真实验证明改进的O R A R算法是高效的,减少了挖掘数据集中频繁项集的运行时间。

关键词数据挖掘;时间;改进;关系矩阵;关联规则

中图分类号T P311.13

R es ea r ch on I m pr ovi ng and Si m ul a t i ng of t he A pr i or i A l gor i t hm

Z h eng Ji gan g

(D epart m en t of M at hm at i c,B aos h an C ol l e ge,B aoshan678000)

A bst r ac t T he t i m e cos t O f t r adi ti onal ass oci a t i on r ul e m i ni ng al gori t hm A p r i or i i s e x pe n s i v e.A ne w al gori t hm O R A R t o m i n e ass oci a t i on r ul es ba se d o n t he r el at i onal al ge br a t heor y w a s pr opos e d i n t h i s pap er.T he O R A R onl y s ca n da t abas e o n c e by usi ng t he r el ati onal m at r i x:Th r oug h t he ext e nsi ve si m ul a t i on expe ri m e nt s s how t he O R A R al gori t hm i s e ffi c i ent.K ey

W or ds dat a m i ni ng,t i m e,i m pr ovem e nt,rel a t i onal m a t r i x,a sso ci at i on r ul e

C I m N um i埘T P311-13

1引言

A pr i or i算法是数据挖掘中发现关联规则的经典算法,1993年由A gr aw al、I m i el i ns ki和S w am i 提出了关联规则挖掘的相关概念,1994年A gr aw al 和Sr i ka nt提出A pr i or i算法[1],用于寻找给定数据集中数据项之间有趣的关联规则或相关关系。

表1购物篮事务

T I D商品集合

1{面包,牛奶}

2{面包,尿布,啤酒,鸡蛋)

3{牛奶,尿布,啤酒,可乐,食盐}

4{面包,尿布,啤酒}

5{面包,牛奶,尿布,食盐}

表1是一个超市购物篮事务例手2|,表中每一行对应一个事务,包含一个唯一标识符TI D和顾客购买的商品集合。

采用A pr i or i算法,得出如下规则:

{尿布)一{啤酒)

[-s uppor t=20A,conf i denc e=40%]

该规则的支持度s uppor t=2%表明有2%的顾客同时购买尿布和啤酒,可信度conf i dence= 40%意味着购买尿布的顾客中有40%的也购买啤酒。通过发现的关联规则帮助决策者进行商品目录的设计、发现新的交叉营销机会或制定其它有关的商业决策。

2基本概念

2.1关联规则

关联规则是“如果……那么……”的形式,要得到有用的规则,就还需要两条与规则相关的重要信息:支持度一规则出现的概率是多少,可信度一规

收稿日期:2010年6月17日,修回日期:2010年7月19日

基金项目:保山学院科学研究项目(编号:108009K)资助。

作者简介:郑继刚,男,硕士研究生,讲师,研究向:挖掘。

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,

Apriori算法及java实现

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算法实验报告

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算法总结

Apriori ['e?pr?'?:r?] Apriori算法是一种挖掘关联规则的频繁项集算法,其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。而且算法已经被广泛的应用到商业、网络安全等各个领域。 其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里,所有支持度大于最小支持度的项集称为频繁项集,简称频集。 经典的关联规则数据挖掘算法Apriori 算法广泛应用于各种领域,通过对数据的关联性进行了分析和挖掘,挖掘出的这些信息在决策制定过程中具有重要的参考价值。 Apriori算法广泛应用于商业中,应用于消费市场价格分析中,它能够很快的求出各种产品之间的价格关系和它们之间的影响。通过数据挖掘,市场商人可以瞄准目标客户,采用个人股票行市、最新信息、特殊的市场推广活动或其他一些特殊的信息手段,从而极大地减少广告预算和增加收入。百货商场、超市和一些老字型大小的零售店也在进行数据挖掘,以便猜测这些年来顾客的消费习惯。 Apriori算法应用于网络安全领域,比如网络入侵检测技术中。早期中大型的电脑系统中都收集审计信息来建立跟踪档,这些审计跟踪的目的多是为了性能测试或计费,因此对攻击检测提供的有用信息比较少。它通过模式的学习和训练可以发现网络用户的异常行为模式。采用作用度的Apriori算法削弱了Apriori算法的挖掘结果规则,是网络入侵检测系统可以快速的发现用户的行为模式,能够快速的锁定攻击者,提高了基于关联规则的入侵检测系统的检测性。 Apriori算法应用于高校管理中。随着高校贫困生人数的不断增加,学校管理部门资助工作难度也越加增大。针对这一现象,提出一种基于数据挖掘算法的解决方法。将关联规则的Apriori算法应用到贫困助学体系中,并且针对经典Apriori挖掘算法存在的不足进行改进,先将事务数据库映射为一个布尔矩阵,用一种逐层递增的思想来动态的分配内存进行存储,再利用向量求"与"运算,寻找频繁项集。实验结果表明,改进后的Apriori算法在运行效率上有了很大的提升,挖掘出的规则也可以有效地辅助学校管理部门有针对性的开展贫困助学工作。 Apriori算法被广泛应用于移动通信领域。移动增值业务逐渐成为移动通信市场上最有活力、最具潜力、最受瞩目的业务。随着产业的复苏,越来越多的增值业务表现出强劲的发展势头,呈现出应用多元化、营销品牌化、管理集中化、合作纵深化的特点。针对这种趋势,在关联规则数据挖掘中广泛应用的Apriori 算法被很多公司应用。依托某电信运营商正在建设的增值业务Web数据仓库平台,对来自移动增值业务方面的调查数据进行了相关的挖掘处理,从而获得了关于用户行为特征和需求的间接反映市场动态的有用信息,这些信息在指导运营商的业务运营和辅助业务提供商的决策制定等方面具有十分重要的参考价值。

数据挖掘中的Apriori算法(C语言版)

/* 这个程序是数据挖掘中的Apriori算法*/ #include #include #define D 9 /*D数事务的个数*/ #define MinSupCount 2 /*最小事务支持度数*/ void main() { /*这里的a,b,c,d,e 分别代表着书上数据挖掘那章的I1,I2,I3,I4,I5 */ char a[10][10]={ {'a','b','e'}, {'b','d'}, {'b','c'}, {'a','b','d'}, {'a','c'}, {'b','c'}, {'a','c'}, {'a','b','c','e'}, {'a','b','c'} }; char b[20],d[100],t,b2[100][10],b21[100][10]; int i,j,k,x=0,flag=1,c[20]={0},x1=0,i1=0,j1,counter=0,c1[100]={0},flag1=1,j2,u=0,c2[100]={0},n[20 ],v=1; int count[100],temp; for(i=0;i

Apriori算法例子

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算法例子

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算法源代码

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 表示所有最大项目集。

Apriori算法及其实现

《数据挖掘》设计论文 院(系)理学院 专业信息与计算科学 指导老师刘建伟 班级 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算法是一种挖掘关联规则的频繁项集算法,其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。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子集的项集

Apriori算法C语言源代码实现

#ifndef APRIRORI_H #define APRIRORI_H #include using namespace std; #define MAXIMAL #include #include #include #include #include #include #include "tract.h" #include "istree.h" #include "Application.h" /*---------------------------------------------------------------------- Preprocessor Definitions ----------------------------------------------------------------------*/ #define PRGNAME "fim/apriori" #define DESCRIPTION "frequent item sets miner for FIMI 2003" #define VERSION "version 1.7 (2003.12.02) " \ "(c) 2003 Christian Borgelt" /* --- error codes --- */ #define E_OPTION (-5) /* unknown option */ #define E_OPTARG (-6) /* missing option argument */

Apriori算法实验报告材料及程序

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算法详解之【一、相关概念和核心步骤】 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算法研究 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 也不是频繁的。 该算法的基本思想是:首先找出所有的频集,这些项集出现的频繁性至少和预定义的最

相关主题
相关文档 最新文档