天气预测频繁2项集_Apriori算法中频繁项集求法的改进

龙源期刊网

http://www.qikan.com.cn

Apriori

算法中频繁项集求法的改进

作者：吴湘华

张祖平

来源：《科技创新与应用》

2013

年第

15

期

摘

要：分析传统

Apriori

效率较低的原因，采用

0-1

矩阵改进数据库事务集的描述，提高

Apriori

中统计匹配的时间效率；分析各频繁项集的计数，改进传统

Apriori

算法完全从低维频

繁项集产生高维频繁项集的方式，通过先求出

1

项频繁集和最大频繁项集，减少中间的频繁项

集剪枝数量，从而达到提高算法效率的目的。

关键词：

0-1

矩阵；统计匹配；剪枝

1

关联规则

[1]

挖掘及

Apriori

算法概述

一提到关联规则挖掘就会令人联想到

“

尿布与啤酒

”

的故事，这是借助数据挖掘技术对大量

原始交易数据进行分析揭示的一条规律。

Apriori[2]

算法是由美国学者

R. Agrawal

等在

1993

年

提出的一种从大规模商业数据中挖掘关联规则的有效方法。现在已经被广泛用于商业决策、社

会科学、科学数据处理等各种各样的数据挖掘领域之中。使用基于支持度的剪枝技术，系统地

控制候选项集指数增长。其核心是使用候选项集找频繁项集。算法具体的执行步骤如下：

(

1

)根据用户的要求确定最小支持度和最小置信度；(

2

)找出所有的频繁项集：先由数

据库读入所有的数据项，得出候选

1

项集

C1

，然后根据最小支持度要求确定频繁

1

项集

L1

；

使用

L1

与

L1

自连接产生候选

2

项集

C2

，继续对数据库扫描，得出候选

2

项集

C2

的支持度，

确定频繁

2

项集

L2

；继续执行上述的步骤，不断进行连接与剪枝，重复对数据库的扫描，并

和最小支持度进行比较，产生更高层次的频繁项集，直到不再产生新的候选频繁项集为止；

(

3

)

根据频繁项集产生强关联规则。

2 Apriori

算法的缺点及改进方法

Apriori

算法能够有效地进行数据关联规则挖掘，但该算法存在效率不高的问题。该算法

使用迭代方法，通过低维频繁项集产生高维频繁项集，该算法存在两个比较明显的缺点：一个

是可能产生大量的候选集，时间开销和空间开销都很大；另一个是需要多次扫描数据库，需要

很大的

I/O

开销。

2.1

采用

0-1

矩阵描述数据库事务集

设

I={i1

，

i2

，

…

，

in}

是项的集合，

D

是数据库事务集，其中每个事务

T

是项的集合，使

得

T

？哿

I

。按如下规则用

0-1

矩阵描述数据库事务集：如果

I

中某一项

ik

在事务

T

中存在，

用

“1”

表示，否则就用

“0”

表示。数据库事务集

D

就转化为

m*n

矩阵的

0-1

矩阵，其中

m

为数

据库事务集

D

的大小，即包含多少个事务，

n

为集合

I

的计数。