（江南大学 无锡 214122）

1 引言

关联规则指数据库中超过指定最小支持度和最小置信度的项目的集合，作为数据挖掘的重要组成部分它一直是学者的研究热点［1］。随着挖掘问题变得越来越复杂，诸如Apriori算法与FP-growth算法等传统算法出现了缺点，其中最典型的是由大量候选项集和复杂的数据结构所造成的时间和内存的成本，导致挖掘效率较低［2］。因此许多学者开始使用启发式算法，粒子群优化算法（PSO）是应用较为广泛的算法之一［3］。

有许多研究将启发式算法应用于关联规则挖掘。例如，Chen等使用PSO算法从高维数据集中挖掘关联规则［4］，Rom提出的基于遗传算法的关联规则可避免挖掘过程中发现的无用个体［5］，BADA等融合了PSO算法和蚁群算法（ACO），将事务数据转换为二进制数据后，从数据集中挖掘频繁项集［6］，Kuo等使用PSO算法快速有效计算出关联规则的最小支持和置信度［7］。

然而，大多数改进的PSO算法重点考虑粒子全局和局部搜索能力，而忽略了粒子种群和搜索范围带来的影响。因此，本文提出了一种改进的二进制粒子群优化算法（GRBPSO），根据适应度函数对粒子初始种群进行预处理，并以频繁项集的性质为依据对粒子搜索空间进行缩减，减少算法运行时间。

2 基本概念

2.1 频繁项集

频繁项集的有关定义为I={i1,i2,…,im}是m个不同项目的集合，每个ik称为一个项目［8］。数据集D={t1,t2,…,tn}是n个不同事务的集合，每个tk称为一个事务，其中tk⊆I。集合X⊆I称为项集，|X|表示项集中的项目数，长度为1的项集称为1项集。项集X的支持度表示为sup（X），其含义是项集X在数据集D中出现的实际频率，若sup(X)≥最小支持度(min_sup)，则称项集X是频繁项集。……