Apriori算法报告

更新时间：2024-01-27 13:43:01 阅读量：教育文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

一、实验背景

Apriori算法广泛应用于商业中，应用于消费市场价格分析中，它能够很快的求出各种产品之间的价格关系和它们之间的影响。通过数据挖掘，市场商人可以瞄准目标客户，采用个人股票行市、最新信息、特殊的市场推广活动或其他一些特殊的信息手段，从而极大地减少广告预算和增加收入。百货商场、超市和一些老字型大小的零售店也在进行数据挖掘，以便猜测这些年来顾客的消费习惯。

二、实验目的

1.加强对Apriori算法的理解

2.提高分析解决问题 3.实践编程的能力

三、实验环境及工具

1.硬件环境:网络环境中的微型计算机 2.软件环境:Windows操作系统 3.编程语言:Java

4.数据库引擎:SQL Server 2014

四、Apriori算法思想

Apriori算法是一个挖掘关联规则的算法，是Agrawal等设计的一个基本算法，这是一个采用两阶段挖掘的思想，并且是基于多次扫描事务数据库来执行的。

Apriori算法的设计可以分解为两步骤来执行挖掘： a)从事务数据库（D）中挖掘出所有频繁项集。

支持度大于给定最小支持度minSup的项目集称为频繁项目集（Frequent ItemCollection）。首先需要挖掘出频繁1-项集；然后，继续采用递推的方式来挖掘频繁k-项集（k>1），具体做法是：在挖掘出候选频繁k-项集（Ck）之后，根据最小置信度minSup来筛选，得到频繁k-项集。最后合并全部的频繁k-项集（k>0）。

b)基于第1步挖掘到的频繁项集，继续挖掘出全部的频繁关联规则。

置信度大于给定最小置信度minConf的关联规则称为频繁关联规则（Frequent Association Rule）。在这一步，首先需要从频繁项集入手，首先挖掘出全部的关联规则（或者称候选关联规则），然后根据minConf来得到频繁关联规则。

Apriori算法程序流程图如下:

五、实验过程及结果

1.程序伪代码描述输入：

D:实物数据库（六个可选数据库的其中一个）； minSup:最小支持度 minConf：最小可信度

输出：

L:D中的频繁项集 R:D中关联规则

方法：

a)连接数据库表，读取数据

public Apriori_function(int sup,double conf,String sql){//构造函数

/*通过连接数据库后，将数据库中所有记录存放到记录列recordList存放表中，以

后可重复扫描recordList表，不需要再直接重复扫描数据库*/

}

b)获取频繁1项集getFc1()

private Map getFc1(){ 扫描数据库D获得频繁1项目集 }

c) 获取候选集getCc()

private Map getCc(Map midFcMap){ //第一步：连接（join）

For each 项集 l1 属于 Lk-1 For each 项集 l2 属于 Lk-1

If( (l1 [1]=l2 [1])&&( l1 [2]=l2 [2])&& ……&& (l1 [k-2]=l2 [k-2])&&(l1

[k-1]

c = l1 连接 l2 // 连接步：产生候选集 //第二步：剪枝（prune）

If c的 k-1项子集中存在不是k-1项频繁集then delete c; else add c to Ck; }

Return Ck; }

d)递归产生所有频繁项目集getFc()

public Map getFc(){ For(k=2;Lk-1 !=null;k++){ Ck = getCc (Lk-1 );

For each 事务t in D{ // 扫描 D 进行候选计数

Ct =subset(Ck,t); // 得到 t 的子集

For each 候选 c 属于 Ct c.count++; }

Lk ={c 属于 Ck | c.count>=min_sup}//返回候选项集中不小于最小支持度的项集

}

Return L= 所有的频繁集； }

e) 获取频繁项目集的非空子集getSubFc()

private void getSubFc(List sourceSet, List> subFcList) { if (sourceSet.size() == 1){// 仅有一个元素时,递归终止，添加到result中

subFcList.add();

} else if (sourceSet.size() > 1) {//当有n个元素时,递归求出前n-1个子集置于result中 getSubFc(sourceSet.subList(0, sourceSet.size() - 1), subFcList);

subFcList.add();//添加到result中 } }

f)生成关联规则getRr()

public Map getRr(Map FcMap){

getSubFc(source,subFcList);//对每个频繁项目l，产生其所有非空真子集对于每个非空真子集s

If(support_count(l)/support_count(s)>=min_conf)

则输出 s->(l-s)， return relationRules; }

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：最小支持数对挖掘时间的影响支持度 20万 40万 60万 80万 100万 0.1 1093 2188 3890 4422 5406 0.2 844 1657 3016 3375 4203 0.3 532 1065 1828 2031 2578 0.4 406 813 1468 1640 2047 0.5 328 703 1267 1422 1735 对应折线图如图1所示：

固定数据量改变支持度阈值 0.20.30.4 支持度图1：最小支持数对性能影响

60005000耗时/ms400030002000100000.120万40万60万80万100万0.5

b) 固定支持度阈值改变数据量

固定支持度阈值（分别为0.1、0.2、0.3、0.4、0.5），置信度阈值为0.7，程序耗时（/ms）如表2：

表2：数据量对挖掘时间影响

记录条数/万支持度0.1 支持度0.2 支持度0.3 支持度0.4 支持度0.5 20 1093 844 532 406 328 40 2188 1657 1065 813 703 60 3890 3016 1828 1468 1267 80 4422 3375 2031 1640 1422 100 5406 4203 2578 2047 1753 对应的折线图如图2所示：

固定支持度阈值改变数据量 600050004000300020001000020 406080100数据量/万图2：数据量对挖掘时间的影响

支持度0.1支持度0.2支持度0.3支持度0.4支持度0.5从以上实验我们可以看出，程序耗时会随着支持度阈值的增大而减小，并且随着数据量的增大而增大。在关联规则挖掘过程的两个步骤中，依据支持度找出所有频繁项集往往是总体性能的瓶颈。当支持度阈值增大时，频繁集的个数将随之减少，生成新的频繁集所花费时间减少。而对于数据量来说，数据越多，则扫描数据库以及其他操作花费的时间也越多。

六、实验总结

1 Apriori算法的缺点

i.由频繁k-1项集进行自连接生成的候选频繁k项集数量巨大。

ii.在验证候选频繁k项集的时候需要对整个数据库进行扫描，非常耗时。 2网上提到的频集算法的几种优化方法