关联规则挖掘算法的研究

张 丽

（湖南文理学院 经济与管理学院，湖南 常德 415000）

关联规则挖掘算法的研究目前是数据挖掘领域的一个重要方向，其中，Apriori算法就是一个经典的挖掘关联规则算法.1993年，Agrawal等提出关联规则挖掘的相关概念，随后提出经典Apriori算法，它是一个采用两阶段挖掘思想的算法，且多次扫描事务数据库，直到寻找出给定数据集中数据项之间有趣的关联规则.

1 关联规则基本概念

1.1 关联规则

关联规则是形如A圯B的蕴含式，在关联规则中，有两个重要的概念：支持度和置信度.支持度是对关联规则的重要性的衡量，置信度是对关联规则的准确度的衡量，一般情况下，用户根据实际挖掘需要，预先给定最小支持度和最小置信度，通常情况下，如果规则的置信度和支持度大于用户指定的最小置信度和支持度，那么这个规则就是一条有效规则.事实上，有效规则并不一定具有实用性，还要参照关联规则的其他指标.

定义1 设I={I1,I2,…,IM}是数据项的集合,D是全体事务的集合,一个事务T有一个唯一的标识TID.如果项集A哿T,则称事务T支持项集A,也称事务T包含项集A.

定义2 关联规则是形如A圯B的蕴含式，其中A奂I，B奂I，且 A∩B=Φ.

定义3 事务数据库D中有N条交易事务，关联规则A圯B的支持度定义为：

引理1 在数据库中若有一事务T其长度小于K+1，则由K项频繁集生成K+1项频繁集时，事务T是没必要扫描的.

1.2 Apriori算法的基本思想

Apriori算法是发现关联规则的经典算法.该算法分两个步骤发现关联规则：第一步通过迭代，找出事务数据库中的所有频繁项集，即支持度不低于最小支持度的项集；第二步利用频繁项集构造出满足用户最小可信度的规则.

2 Apriori算法的不足之处

Apriori算法最大的优点是算法思路比较简单，它以递归统计为基础，生成频繁项集，易于实现.Apriori算法虽然能够从海量数据中挖掘出关联规则，但是算法在执行速度和效率上有一定的局限性，表现如下：

2.1 Apriori算法会产生大量的候选项集.该算法是由候选集函数Apriori-Gen利用Lk-1项产生候选项集Ck，所产生的Ck由CkLk-1项集组成.显然k越大产生的候选项集的数目就越多.

2.2 I/O负载过大.Apriori算法需要多次扫描事务数据库，需要很大的I/O负载.对每次k循环，候集Ck中的每个元素都必须扫描数据库1次来决定其是否加入Ck.例如，一个频繁大项目集包含12个项，那么就至少扫描事务数据库12遍.

同理心对于做好办公室工作尤其重要，在日常工作中，要有意识地安排一些活动，形成一种氛围去培养办公室工作人员的同理心，这有利于我们做好办公室的工作。但同时，也要正确认识同理心，在合理利用同理心做好工作的同时，也要合理规避同理心带来的负面影响，加强制度的约束力和执行力。确保同理心能在合适的范围得到充分的利用，服务于我们的办公室工作。

3 对Apriori算法的改进

算法改进的思路

1.改变数据的存储结构，用二进制位存储各项目的事务集，矩阵的列代表频繁K-项集，矩阵的行代表事务，其中1表示该项目在某事务中出现，0表示该项目在某事务中没有出现.

2.生成频繁1-项集.首先扫描源数据库，生成矩阵.统计每列中包含1的数目,得到该项目的支持事务数，如果该项的支持事务数大于最小支持事务数，则该项是频繁项集，否则是非频繁项集.从矩阵中将该列删除,并根据引理1，在矩阵中删除第9行，得出频繁1-项集.

3.由频繁1-项集生成频繁2-项集.对频繁1-项集中的项两两连接得出候选2-项集,也就是对矩阵中第i列所代表的项集和第j列所代表的项集进行逻辑与操作.然后计算支持候选2-项集各项集的事务集,在矩阵中删除支持事务数小于最小支持事务数项集对应的列,根据引理1，在矩阵中删除第4、6、10行.得出频繁2-项集.

4.类推，得到频繁K-项集，直到不能产生新的频繁项集为止.

4 改进算法举例

假定最小支持数为3

?

第一步 生成初始矩阵

?

第二步 将支持度小于3的列删除.得到L1=(a,b,c,d)

?

第三步 将支持度小于3的列删除，且根据引理1，删除第9行,得到L2=(ac,bc,bd,cd)

?

第四步 将支持度小于3的列删除，且根据引理1，删除第4,6,10行,得到L3=(bcd)

?

5 结束语

进算法通过改进数据的存储结构，利用“0”和“1”存储各项目的事务集，采用逻辑运算求得某项集的支持事务数，再根据给定的最小支持数生成频繁项集.改进后的算法与Apriori算法相比具有以下优势：（1）整个数据库只要扫描一次.（2）由频繁k-1项集直接生成频繁k项集，不需要再扫描整个数据库.3)在求k频繁项集时，删除了长度小于K的事务.节约了存储空间，算法的效率也大大提高.

〔1〕刘军，谢康林.一种改进的关联规则提取算法[J].型微型计算机系统，2003(7).

〔2〕安颖．基于关联规则的数据挖掘算法研究[D]北京：北京工业大学，2009.

〔3〕杨志刚,何月顺.基于压缩事务矩阵相乘的Apriori改进算法[J].中国新技术新产品,2010,30(6):57-58..

〔4〕黄建明,赵文静,王星星.基于十字链表的 Apriori改进算法[J].计算机工程,2009,35(2):37-38.

〔5〕李云峰,陈建文,程代杰.关联规则挖掘的研究及对Apriori算法的改进[J].计算机工程与科学,2002,24(6):65-68.