一种基于压缩矩阵的Apriori改进算法

2022-12-16

数据挖掘是从数据库、数据仓库或其他信息库中发现有趣知识的过程, 而这些有趣的关联能辅助决策者作出正确的决策。目前最经典的关联规则算法是由Agrawal等于1994年提出的apriori算法。但Apriori算法在处理含有大量事务的数据库时, 需要多次扫描数据库, 而且会产生大量的候选项集, 使该算法效率降低。本文提出的基于矩阵的Apriori改进算法可以避免多次扫描数据库且无需产生大量候选项集, 从而大大提高了算法的效率。

1 基本概念

设I={I1, I2, …, Im}是项目的集合, 任务相关的数据D是数据库的集合, 其中每个事务T是项目的集合, 使得T⊆I。每个事务有一个唯一标识符, 称作TID。

定义1:每个项Ij的向量定义为:

其中,

定义2:项集I的矩阵记为:

性质1:若有一事务T其长度小于2, 则可以在矩阵中删除该事务所对应的列项量。

证明:若事务T的长度小于2, 则说明事务T不可能包含频繁K (k>1) -项集, 故可以在矩阵中删除该事务所对应的列向量。

性质2:任何非频繁项集都不可能是频繁项集的子集[1]。

2 基于压缩矩阵的Apriori算法 (简称PM_Apriori算法)

(1) 扫描数据库建立布尔矩阵D, 使D中的每列压缩存储一条或多条事务信息, 且无重复列 (建立一个数组av来存放每列的权值即含相同项目的事务个数) 。

(2) 裁剪矩阵。 (1) 扫描矩阵并计算所有项目的支持度计数, 若项目的支持度小于最小支持度, 则该项目对生成频繁K (K>1) -项集不起作用, 可以在矩阵中删除该项目所对应的行向量。 (2) 分别对矩阵中的每个列求和, 若某列和小于2, 依据性质1则可删除该列向量。

(3) 生成频繁2-项集对D各行按位做与运算, 并对运算结果求两个项目同时在所有事务中出现的次数:

若其值小于最小支持度计数, 则舍去该行向量, 否则保存。此时, 保存下来的行向量所对应的项目集即为频繁2-项集。

(4) 生成频繁K-项集。 (1) 对步骤2.3保存下来的行向量, 按原来顺序重新组合成矩阵, 得到矩阵D1。 (2) 分别对D1中的每个列求和, 若其和小于2, 则删除该列向量。 (3) 对D1保存下来的列向量, 按原来顺序组合成矩阵, 得到矩阵D2。 (4) 对D2各行按位做与运算, 将运算结果中的1取出, 分别与其对应列的权值相乘后相加, 求出该项集的支持度计数, 若其值小于最小支持度计数, 则舍去该行向量, 否则保存。 (5) 对保存的行向量所对应的项集求并集, 去掉重复的行向量, 此时, 保存下来的行向量所对应的项集即为频繁3-项集和频繁4-项集。 (6) 对保存下来的行向量按原来顺序重新组合成矩阵, 得到相应的矩阵D3。 (7) 分别对D3中的每个列求和, 若其和小于2, 则删除该列向量。 (8) 对D3保存下来的列向量, 按原来顺序组合成矩阵, 得到矩阵D4。 (9) 重复以上步骤直到矩阵行数少于或等于一行, 则算法结束。

(5) 对所有保存下来的行向量转化成相应的频繁项集并输出。

3 PM_Apriori算法与Apriori算法性能比较

为了验证改进后的算法性能, 以Apriori算法作为实验对比算法进行性能分析。程序为Delphi 7.0实现, 数据库为SQL Server 2000自带的Foodmart数据库, 图1描述了支持度为10%, 两种算法随记录数增加而在执行时间上的差异。

4 结语

本文提出的PM_Apriori算法可以避免多次扫描数据库且无需产生大量的候选项集, 并用矩阵的方式直接产生频繁项集, 算法效率得到很大提升。数据库中有大量相同的记录, 为每条记录增加权值 (记录重复次数) , 可降低数据库的规模。实验结果也验证了这种改进是有效的。对于未来工作, 应放在候选项集的裁剪, 以更好的提高算法效率。

摘要：介绍基于压缩矩阵的Apriori改进算法的基本概念和原理。该算法可以避免多次扫描数据库且无需产生候选项集, 提高了算法的效率。实验结果证明其可行性和高效性。

关键词：频繁项集,矩阵,权值