Apriori算法报告

一、实验背景Apriori算法广泛应用于商业中，应用于消费市场价格分析中，它能够很快的求出各种产品之间的价格关系和它们之间的影响。通过数据挖掘，市场商人可以瞄准目标客户，采用个人股票行市、最新信息、特殊的市场推广活动或其他一些特殊的信息手段，从而极大地减少广告预算和增加收入。百货商场、超市和一些老字型大小的零售店也在进行数据挖掘，以便猜测这些年来顾客的消费习惯。二、实验目的1.加强对Apriori算法的理解2.提高分析解决问题3.实践编程的能力三、实验环境及工具1.硬件环境:网络环境中的微型计算机2.软件环境:Windows操作系统3.编程语言:Java4.数据库引擎:SQLServer2014四、Apriori算法思想Apriori算法是一个挖掘关联规则的算法，是Agrawal等设计的一个基本算法，这是一个采用两阶段挖掘的思想，并且是基于多次扫描事务数据库来执行的。Apriori算法的设计可以分解为两步骤来执行挖掘：a)从事务数据库（D）中挖掘出所有频繁项集。支持度大于给定最小支持度minSup的项目集称为频繁项目集（FrequentItemCollection）。首先需要挖掘出频繁1-项集；然后，继续采用递推的方式来挖掘频繁k-项集（k1），具体做法是：在挖掘出候选频繁k-项集（Ck）之后，根据最小置信度minSup来筛选，得到频繁k-项集。最后合并全部的频繁k-项集（k0）。b)基于第1步挖掘到的频繁项集，继续挖掘出全部的频繁关联规则。置信度大于给定最小置信度minConf的关联规则称为频繁关联规则（FrequentAssociationRule）。在这一步，首先需要从频繁项集入手，首先挖掘出全部的关联规则（或者称候选关联规则），然后根据minConf来得到频繁关联规则。Apriori算法程序流程图如下:五、实验过程及结果1.程序伪代码描述输入：D:实物数据库（六个可选数据库的其中一个）；minSup:最小支持度minConf：最小可信度输出：L:D中的频繁项集R:D中关联规则方法：a)连接数据库表，读取数据publicApriori_function(intsup,doubleconf,Stringsql){//构造函数/*通过连接数据库后，将数据库中所有记录存放到记录列recordList存放表中，以后可重复扫描recordList表，不需要再直接重复扫描数据库*/}b)获取频繁1项集getFc1()privateMapString,IntegergetFc1(){扫描数据库D获得频繁1项目集}c)获取候选集getCc()privateMapString,IntegergetCc(MapString,IntegermidFcMap){//第一步：连接（join）Foreach项集l1属于Lk-1Foreach项集l2属于Lk-1If((l1[1]=l2[1])&&(l1[2]=l2[2])&&……&&(l1[k-2]=l2[k-2])&&(l1[k-1]l2[k-1]))then{c=l1连接l2//连接步：产生候选集//第二步：剪枝（prune）Ifc的k-1项子集中存在不是k-1项频繁集thendeletec;elseaddctoCk;}ReturnCk;}d)递归产生所有频繁项目集getFc()publicMapString,IntegergetFc(){For(k=2;Lk-1!=null;k++){Ck=getCc(Lk-1);Foreach事务tinD{//扫描D进行候选计数Ct=subset(Ck,t);//得到t的子集Foreach候选c属于Ctc.count++;}Lk={c属于Ck|c.count=min_sup}//返回候选项集中不小于最小支持度的项集}ReturnL=所有的频繁集；}e)获取频繁项目集的非空子集getSubFc()privatevoidgetSubFc(ListStringsourceSet,ListListStringsubFcList){if(sourceSet.size()==1){//仅有一个元素时,递归终止，添加到result中subFcList.add();}elseif(sourceSet.size()1){//当有n个元素时,递归求出前n-1个子集置于result中getSubFc(sourceSet.subList(0,sourceSet.size()-1),subFcList);subFcList.add();//添加到result中}}f)生成关联规则getRr()publicMapString,DoublegetRr(MapString,IntegerFcMap){getSubFc(source,subFcList);//对每个频繁项目l，产生其所有非空真子集对于每个非空真子集sIf(support_count(l)/support_count(s)=min_conf)则输出s-(l-s)，returnrelationRules;}2.GUI用户界面用户可以根据需求设置“最小支持度minSup”以及“最小可信度minConf“可选数据库”中有11个数据库可选，分别为：Data0（9条数据）、Data1（20万条数据）、Data2（40万条数据）、Data3（60万条数据）、Data4（80万条数据）、Data5（100万条数据）3.实验测试用课堂示例对该算法的正确性进行了测试，记录列表数据预览：测试结果如下(最小支持度为0.2，置信度阈值为0.7)：4.性能分析为了对Apriori算法实验进行性能分析，我们分别采用固定数据量改变支持度阈值以及固定支持度阈值改变数据量两种情况进行时间分析,其中最小置信度设为0.7不变。a)固定数据量改变支持度阈值固定数据量（分别为20万、40万、60万、80万、100万），置信度阈值为0.7，改变支持度阈值，程序耗时(/ms)结果如表1：表1：最小支持数对挖掘时间的影响支持度0.10.20.30.40.520万109384453240632840万21881657106581370360万3890301618281468126780万44223375203116401422100万54064203257820471735对应折线图如图1所示：图1：最小支持数对性能影响固定数据量改变支持度阈值01000200030004000500060000.10.20.30.40.5支持度耗时/ms20万40万60万80万100万b)固定支持度阈值改变数据量固定支持度阈值（分别为0.1、0.2、0.3、0.4、0.5），置信度阈值为0.7，程序耗时（/ms）如表2：表2：数据量对挖掘时间影响记录条数/万20406080100支持度0.110932188389044225406支持度0.28441657301633754203支持度0.35321065182820312578支持度0.4406813146816402047支持度0.5328703126714221753对应的折线图如图2所示：图2：数据量对挖掘时间的影响从以上实验我们可以看出，程序耗时会随着支持度阈值的增大而减小，并且随着数据量的增大而增大。在关联规则挖掘过程的两个步骤中，依据支持度找出所有频繁项集往往是总体性能的瓶颈。当支持度阈值增大时，频繁集的个数将随之减少，生成新的频繁集所花费时间减少。而对于数据量来说，数据越多，则扫描数据库以及其他操作花费的时间也越多。六、实验总结1Apriori算法的缺点i.由频繁k-1项集进行自连接生成的候选频繁k项集数量巨大。ii.在验证候选频繁k项集的时候需要对整个数据库进行扫描，非常耗时。2网上提到的频集算法的几种优化方法i.基于划分的方法。ii.基于hash的方法。iii.基于采样的方法。iiii.减少交易的个数。固定支持度阈值改变数据量010002000300040005000600020406080100数据量/万耗时/ms支持度0.1支持度0.2支持度0.3支持度0.4支持度0.5