摘要：文中结合遗传算法和粒子群优化算法各自的优势，采用协同进化的思想，同时应用两种算法来遍历两个种群，并引入它们的信息交互机制。最后，实验和应用证明，在可接受的时间复杂度的前提下，协同进化算法不但能继承传统遗传算法的优越性，有效地减少扫描数据库的次数，和产生小规模的候选项目集；而且通过比较协同进化算法，传统的遗传算法和粒子群优化算法的属性，在关联规则挖掘中使用该算法，能避免早熟的现象。采取协同进化算法时可以发现高品质的关联规则，尤其是在高维数据库中。 关键词：关联规则挖掘；协同进化算法；遗传算法；粒子群优化算法；概率调整 中图分类号：TP181 文献标识码：A 文章编号：1009-3044（2014）02-0295-03 关联规则挖掘是发现一个大数据库中的数据项之间的潜在关系， 它可以帮助不同的领域决策者确定合适的策略，是数据挖掘研究中的一个重要分支 。而其中最经典的关联规则挖掘算法当属apriori算法，但随着研究的发展，Apriori算法多次扫描数据库和产生大量候选频繁项集的两大缺陷逐渐显露出来。针对Apriori算法的这些问题，研究人员已经提出了许多改进的算法来弥补其缺点，如FP增长算法，分区算法。与Apriori算法相比，这些算法的性能已经有显著的提高，但在某些场合使用这些算法挖掘大规模高维数据仍然是不现实的。该文是利用协同进化的思想，结合遗传算法和粒子群优化算法的优势，从数据集中挖掘高质量的规则。 1 协同进化的理论思想 协同进化概念首次是由Ehrlich和Raven提出来的，其核心思想是：种群的相互作用是彼此生存的不可或缺的条件。在长期的进化过程中，它们是相互依存的，并提高个体和整体的性能 。通过引入这个概念说明，演化不仅是与自己的种群有关，也影响了与它接触的种群。协同进化的概念有一个很宽的范围，包括多PSO协同进化算法，协同进化遗传算法等。 在本文中我们使用“GA-PSO”的协同进化，使用GA和PSO相互遍历。结合两种算法的优点，巧妙运用协同进化的思想，从大型数据中挖掘高品质的有趣的规则。为了实现这样的想法，我们设计了一个信息交换机制。使两个种群之间的信息得到交换，能够实现共同进化的目的。 2 协同进化算法的搜索策略 2.1 GA搜索策略 GA做了以下改进，以确保该信息可以在两个种群之间传递。 2.1.1 编码规则 关联规则挖掘的搜索空间相当于整个交易的数据库，该方法以一个实数数组编码。在一个数组中，元素序号对应于交易数据库的字段，元素的值代表该字段的属性值。 3 协同进化算法 本文使用了协同进化的思想，在传统遗传算法用于关联规则挖掘时，有助于避免过早收敛。具体步骤如下所述： 1）首先根据数据集随机产生POP1和POP2两个初始种群，分别使用PSO和GA算法的搜索策略挖掘关联规则。两个群体使用相同的编码规则，适应度函数，种群规模和最大迭代数。 2）初始化两个种群的各种参数：惯性因子，最小支持度和最小置信度的阈值，前项集和后项集的约束条件。 3）扫描数据库，使用适应函数计算两个种群中的个体适应度。然后，保留具有资格的个体进入各自的下代，消除不符合规定的个体。比较POP1和POP2中全局最优个体的适应度，适应度较大的个体将取代另一个种群的最佳个体，成为下一代进化的基础。 4）判断是否满足终止条件：如果满足收敛条件或者迭代次数已经达到了最大迭代次数，则算法结束，切换到第6步。否则，继续到下一个步骤5。 5）根据式（4）和式（5）更新POP1中的粒子速度和位置，产生下一代。POP2则是通过遗传操作来进化、产生下一代。然后跳转到第三步计算适应度。 6）输出挖掘到的关联规则。 当POP1中的粒子陷入局部最优时，这些个体将不仅使用当前种群的经验来更新位置，还将借鉴POP2中的最佳个体。利用POP2中的优秀个体，可以引导已经陷入局部最优值个体跳出局部极小的困境。因此，有更大的概率得到全局最优解。 4 实验分析和应用 在Win7中用MATLAB运行协同进化算法。通过跟踪，比较GA，PSO，以及协同进化算法的运行时间和种群的平均适应度。 实验数据库来源于UCI的植物数据集，该数据集有22632个数据元素，和 70的维数。实验环境：英特尔处理器I3系列的M350 频率为2.75GHz 双核和2 GB的RAM的笔记本电脑。实验参数见表1，进化结果如图1。 5 结论 本文提出了一种协同进化算法，使用GA和PSO同时遍历两个种群。引入了一种交换种群之间信息的机制，使得这两个种群可以共同发展。通过实验证明，协同进化算法运行时间比其他两个全局优化算法稍长，却是可以接受的。相比其他两个算法，协同进化算法不仅是挖掘质量高，还具有显著跳出局部最优解的能力。 参考文献： [1] Han J， Kamber M.Data Mining： Concepts and Techniques， 2nd edn.， China Machine Press，2011：146-155. [2] Agrawal R， Imielinski T， Swami A. Mining Association Rules between Sets of Items in Large Databases[C]//Proc.1993 ACM-SIGMOD Int. Conf. Management of Databases，. ACM Press， Washington， 1993： 20-72. [3] Han J， Pei J， Yin Y. Mining frequent patterns without candidate generation. In： Proceedings of the 2000 ACM-SIGMOD International Conference on Management of Data， Dallas， Texas， ACM Press ，2000： 1-12. [4] Savasere A. Omiecinski E， Navathe S. An efficient algorithm for mining association rules in large databases[C]//Dayal U， Gray P M D， Nishio S.Proceedings of the 21th International Conference on Very Large Databases（VLDB 1995）， Zurich， Morgan Kaufmann Publisher ，1995： 432-443. [5] Wiegand R P. An analysis of cooperative co-evolutionary algorithms. George Mason University， Fairfax，2003. [6] Sharma S K， Irwin G W.Fuzzy coding of genetic algorithms. IEEE Trans. Evolutionary Computation， 2003： 344-355. [7] Thierens D.Adaptive mutation rate control schemes in genetic algorithms[C].Proceedings of the 2002 Congress on Evolutionary Computation， CEC 2002， 2002（1）： 980-985. [8] Shi Y， Eberhart R C.Parameter Selection in Particle Swarm Adaptation[C].Porto V W， Waagen D.EP 1998. LNCS， Springer， Heidelberg ，1998（1447）： 591-600.
摘要：文中结合遗传算法和粒子群优化算法各自的优势，采用协同进化的思想，同时应用两种算法来遍历两个种群，并引入它们的信息交互机制。最后，实验和应用证明，在可接受的时间复杂度的前提下，协同进化算法不但能继承传统遗传算法的优越性，有效地减少扫描数据库的次数，和产生小规模的候选项目集；而且通过比较协同进化算法，传统的遗传算法和粒子群优化算法的属性，在关联规则挖掘中使用该算法，能避免早熟的现象。采取协同进化算法时可以发现高品质的关联规则，尤其是在高维数据库中。 关键词：关联规则挖掘；协同进化算法；遗传算法；粒子群优化算法；概率调整 中图分类号：TP181 文献标识码：A 文章编号：1009-3044（2014）02-0295-03 关联规则挖掘是发现一个大数据库中的数据项之间的潜在关系， 它可以帮助不同的领域决策者确定合适的策略，是数据挖掘研究中的一个重要分支 。而其中最经典的关联规则挖掘算法当属apriori算法，但随着研究的发展，Apriori算法多次扫描数据库和产生大量候选频繁项集的两大缺陷逐渐显露出来。针对Apriori算法的这些问题，研究人员已经提出了许多改进的算法来弥补其缺点，如FP增长算法，分区算法。与Apriori算法相比，这些算法的性能已经有显著的提高，但在某些场合使用这些算法挖掘大规模高维数据仍然是不现实的。该文是利用协同进化的思想，结合遗传算法和粒子群优化算法的优势，从数据集中挖掘高质量的规则。 1 协同进化的理论思想 协同进化概念首次是由Ehrlich和Raven提出来的，其核心思想是：种群的相互作用是彼此生存的不可或缺的条件。在长期的进化过程中，它们是相互依存的，并提高个体和整体的性能 。通过引入这个概念说明，演化不仅是与自己的种群有关，也影响了与它接触的种群。协同进化的概念有一个很宽的范围，包括多PSO协同进化算法，协同进化遗传算法等。 在本文中我们使用“GA-PSO”的协同进化，使用GA和PSO相互遍历。结合两种算法的优点，巧妙运用协同进化的思想，从大型数据中挖掘高品质的有趣的规则。为了实现这样的想法，我们设计了一个信息交换机制。使两个种群之间的信息得到交换，能够实现共同进化的目的。 2 协同进化算法的搜索策略 2.1 GA搜索策略 GA做了以下改进，以确保该信息可以在两个种群之间传递。 2.1.1 编码规则 关联规则挖掘的搜索空间相当于整个交易的数据库，该方法以一个实数数组编码。在一个数组中，元素序号对应于交易数据库的字段，元素的值代表该字段的属性值。 3 协同进化算法 本文使用了协同进化的思想，在传统遗传算法用于关联规则挖掘时，有助于避免过早收敛。具体步骤如下所述： 1）首先根据数据集随机产生POP1和POP2两个初始种群，分别使用PSO和GA算法的搜索策略挖掘关联规则。两个群体使用相同的编码规则，适应度函数，种群规模和最大迭代数。 2）初始化两个种群的各种参数：惯性因子，最小支持度和最小置信度的阈值，前项集和后项集的约束条件。 3）扫描数据库，使用适应函数计算两个种群中的个体适应度。然后，保留具有资格的个体进入各自的下代，消除不符合规定的个体。比较POP1和POP2中全局最优个体的适应度，适应度较大的个体将取代另一个种群的最佳个体，成为下一代进化的基础。 4）判断是否满足终止条件：如果满足收敛条件或者迭代次数已经达到了最大迭代次数，则算法结束，切换到第6步。否则，继续到下一个步骤5。 5）根据式（4）和式（5）更新POP1中的粒子速度和位置，产生下一代。POP2则是通过遗传操作来进化、产生下一代。然后跳转到第三步计算适应度。 6）输出挖掘到的关联规则。 当POP1中的粒子陷入局部最优时，这些个体将不仅使用当前种群的经验来更新位置，还将借鉴POP2中的最佳个体。利用POP2中的优秀个体，可以引导已经陷入局部最优值个体跳出局部极小的困境。因此，有更大的概率得到全局最优解。 4 实验分析和应用 在Win7中用MATLAB运行协同进化算法。通过跟踪，比较GA，PSO，以及协同进化算法的运行时间和种群的平均适应度。 实验数据库来源于UCI的植物数据集，该数据集有22632个数据元素，和 70的维数。实验环境：英特尔处理器I3系列的M350 频率为2.75GHz 双核和2 GB的RAM的笔记本电脑。实验参数见表1，进化结果如图1。 5 结论 本文提出了一种协同进化算法，使用GA和PSO同时遍历两个种群。引入了一种交换种群之间信息的机制，使得这两个种群可以共同发展。通过实验证明，协同进化算法运行时间比其他两个全局优化算法稍长，却是可以接受的。相比其他两个算法，协同进化算法不仅是挖掘质量高，还具有显著跳出局部最优解的能力。 参考文献： [1] Han J， Kamber M.Data Mining： Concepts and Techniques， 2nd edn.， China Machine Press，2011：146-155. [2] Agrawal R， Imielinski T， Swami A. Mining Association Rules between Sets of Items in Large Databases[C]//Proc.1993 ACM-SIGMOD Int. Conf. Management of Databases，. ACM Press， Washington， 1993： 20-72. [3] Han J， Pei J， Yin Y. Mining frequent patterns without candidate generation. In： Proceedings of the 2000 ACM-SIGMOD International Conference on Management of Data， Dallas， Texas， ACM Press ，2000： 1-12. [4] Savasere A. Omiecinski E， Navathe S. An efficient algorithm for mining association rules in large databases[C]//Dayal U， Gray P M D， Nishio S.Proceedings of the 21th International Conference on Very Large Databases（VLDB 1995）， Zurich， Morgan Kaufmann Publisher ，1995： 432-443. [5] Wiegand R P. An analysis of cooperative co-evolutionary algorithms. George Mason University， Fairfax，2003. [6] Sharma S K， Irwin G W.Fuzzy coding of genetic algorithms. IEEE Trans. Evolutionary Computation， 2003： 344-355. [7] Thierens D.Adaptive mutation rate control schemes in genetic algorithms[C].Proceedings of the 2002 Congress on Evolutionary Computation， CEC 2002， 2002（1）： 980-985. [8] Shi Y， Eberhart R C.Parameter Selection in Particle Swarm Adaptation[C].Porto V W， Waagen D.EP 1998. LNCS， Springer， Heidelberg ，1998（1447）： 591-600.