杜嘉伟 余粟

摘 要：提出一种基于矩阵二进制编码的改进遗传算法MGA（Matrix Genetic Algorithm ），应用于挖掘关联规则中的频繁项集。通过对初始种群的编码以及降维保证了合理的初始适应度，并对遗传算法中交叉算子和变异算子生成新个体与筛选的过程进行优化，使算法有优良的全局和局部搜索能力。实验结果显示，MGA算法的整体挖掘效率与质量良好。

关键词： 遗传算法;关联规则;频繁项集

文章编号： 2095-2163（2021）01-0143-05 中图分类号：TP301.6 文献标志码：A

【Abstract】This paper proposes an improved genetic algorithm MGA （Matrix Genetic Algorithm） based on matrix binary coding， which is applied to mining frequent itemsets in association rules. By encoding the initial population and reducing the dimensionality， a reasonable initial fitness is ensured， and then the process of generating new individuals and screening by the crossover operator and mutation operator in the genetic algorithm is optimized， so that the algorithm has excellent global and local search capabilities. Experimental results show that the overall mining efficiency and quality of the MGA algorithm are good.

【Key words】Genetic Algorithm; association rules; frequent itemsets

0 引 言

频繁项集是那些出现在二进制或者定量数据集中的项目集，其出现频率超过指定的最小支持度，这是关联规则挖掘的基础和重要的部分[1]。由于多数挖掘定量频繁项目集的方法都是先将数据集转换成二进制的表现方法[2]，本文拟重点关注二进制频繁项目集的挖掘。

为了挖掘到最大频繁项目集，通常会选择使用精确算法。其中使用率较高的Apriori算法[3]和FPGrowth算法[4]能够找到目标事务数据集中最大频繁项集，但是随着挖掘问题变得越来越复杂，也带来了一些缺点，如大量的时间和存储的成本。因此，更多的研究者开始运用遗传算法等启发式算法，虽然无法如精确算法一样得到问题的全局最优解，但却能在基于时间和空间的条件约束下求得问题的近似解，这也将具有更大的现实意义。

将传统遗传算法运用到长频繁项集的挖掘过程，但是并未将算法应用到大体量的数据集[5]。侯燕等人[6]研究优化了遗传算法对频繁项集的全局搜索能力，来挖掘关联规则并分析其性能，有着良好的挖掘效率，但对于频繁项集的提取率有限。……