结合变异机制和量子PSO的关联规则挖掘算法

(1.广东科贸职业学院 信息与自动化学院，广东 广州 510640；2.广东技术师范大学 数学与系统科学学院，广东 广州 510665；3.华南理工大学 数学学院，广东 广州 510641)

关联规则挖掘是一种用来查找数据库中的频繁项或属性集之间相关性和因果关联的数据挖掘方法[1]。从数据库中执行关联规则挖掘是一个NP完全问题，其取决于数据库、机器学习和优化算法的研究。

目前已有的多种关联规则挖掘算法可以分为两类：一是精确算法[2]，这类算法一定程度上可以获得最优解，但需要多次扫描数据库，产生大量候选项集，对候选项集进行模式匹配时需花费大量时间[3]，如Apriori和FP-Growth算法。二是智能进化算法[4]，这类算法也能够给出很好的解，且执行时间会明显缩短，例如遗传算法、模拟退火算法等。

大型数据库中的关联规则挖掘是一个复杂的过程，使用精确算法非常昂贵，而智能进化算法在这个领域提供了很大的帮助。其中量子进化算法(quantum-inspired evolutionary algorithm，QEA)[5]使用量子比特作为信息的最小单元[6]进行概率表示。量子比特个体为量子比特组成的串，称为多量子比特。量子比特个体的优点是可以在搜索空间中以概率表示状态的线性叠加。因此，量子比特表示法比遗传算法中的染色体表示法具有更好的群体多样性特征[7]。QEA中的量子门为一种变体运算符，用来使个体转向更好的解，并最终收敛到单一最优解[8]。量子粒子群优化(quantum-behaved particle swarm optimization，QPSO)[9]是QEA和粒子群优化(PSO)的混合算法，采用一种新的称为量子角度的量子比特表达机制。并利用PSO中的位置更新机制来更新QEA中的量子比特，使其寻优能力优于传统QEA。

基于上述分析，提出一种基于改进QPSO的关联规则挖掘方法，并在UCI和课程成绩数据集上进行了实验验证，结果表明，提出的方法在执行时间和挖掘规则质量上都具有一定的优势。提出方法的主要创新点在于：将数据实例以量子比特形式表示，构建一个基于QEA的关联规则挖掘基础框架；使用QPSO代替QEA实现关联规则挖掘，并融入变异机制和动态惯性权重形成IQPSO，以加快其收敛速度和跳出局部最优的能力。

1 关联规则挖掘问题描述

1.1 问题定义

关联规则挖掘中，令I={i1,i2,…,im}为一组布尔型属性，称为项目；S={s1，s2，…,sn}为多组数据实例记录，其中每个数据实例si∈S由I中的不同属性构成。数据实例si中若存在某个布尔属性，则意味着其值为1，如果不存在，则其值为0。例如，令I={A,B,C}为一组布尔型属性，S={〈A,B〉,〈C〉,〈C〉}为多组数据实例，那么多组S可以重写为：

S={〈A=1，B=1，C=1〉,〈A=0，B=0，C=1〉,〈A=0，B=0，C=1〉}。

(1)

一个关联规则可表示为：如果C成立，则为P。其中C为条件，P为预测，C、P⊂1并且C∩P=Ø。

本研究连接关联规则，其中C是一个或多个条件的连接，P是一个或多个预测的连接。文中所涉及的符号有：|C|—规则C包含的数据实例数量；|P|—规则P包含的数据实例数量；|C&P|—规则C和P同时包含的数据实例数量；N—要挖掘的数据实例总数。

1.2 规则适应度函数

关联规则的性能通常由置信度和支持度表示，为了更好地量化规则质量，采用文献[10]提出的适应度函数F来评估候选规则的质量。定义规则支持度为满足规则中C的数据实例的百分比，置信度b为满足规则(IFC, THENP)的数据实例的百分比。该适应度函数是基于信息论推导的，综合考虑了置信度和支持度。定义一个J-度量Jm，计算表达式为：

(2)

适应度函数

(3)

式中:npu为潜在有用属性的数量。如果至少存在一个数据实例在C部分和预测属性中具有指定的A值，则认为该属性A是潜在有用的；nr为规则中C包含的属性总数；w1、w2为用户自定义权重，这里分别设置为0.6和0.4；F的取值在0～1之间，值越大说明规则的质量越好。

2 基于QEA的关联规则挖掘

量子进化算法(QEA)与经典进化算法(EA)类似，只是采用了量子个体来代替传统个体进行迭代。量子个体中使用基于量子比特的编码方式[11-12]，即用一对复数定义一个量子比特位。这种表示方法可以表征任意的线性叠加状态。另外，在种群更新中，根据量子的叠加特性和变迁理论，通过量子门变换来产生新的个体。在数据集中应用QEA进行规则挖掘时，必须将数据实例通过量子来表示。基于QEA算法的关联规则挖掘过程如算法1描述。

算法1：QEA关联规则挖掘算法

输入：实例数据集，最小置信度，支持度阈值，种群数量，最大迭代次数

输出：一组最佳关联规则

begin

t←0；

初始化包含多个量子比特个体Q(t)的种群；

把Q(t)投影到二进制解P(t)中；

计算P(t)的适应度函数；

If存在关联规则

Then从每个P(t)上生成关联规则；

endif

存储P(t)中的最佳解；

while(结束条件)do

t←t+1；

把Q(t-1)投影到二进制解P(t)中；

计算P(t)的适应度函数；

If存在关联规则

Then从每个P(t)上生成关联规则；

使用量子门更新Q(t)；

endif

存储P(t)中的最佳解；

enddo

end

QEA算法主要包含4个部分：

(4)

3)计算P(t)的适应度函数：通过适应度函数F对每个二进制解P(t)进行评估。

4)使用量子门更新Q(t)：通过量子旋转门来更新个体角增量。

量子门U(Δθ)是一个可变运算符，可以根据具体问题进行选择。本研究使用的量子门定义为：

(5)

式中:ξ(Δθi)=s(αi,βi)×Δθi；s(αi,βi)和Δθi分别表示旋转方向和角度。

3 基于改进QPSO的关联规则挖掘

3.1 QPSO算法

由于传统QEA中通过量子旋转门来更新量子角增量，操作复杂且更新角度固定，使其容易陷入局部最优[13]。为此，Sun等[14]引入了PSO算法中的位置更新公式替代QEA中的量子旋转门来更新角增量，形成QPSO算法。

|sin(θ)|2+|cos(θ)|2=1。

(6)

量子旋转门变为：

(7)

QPSO使用PSO的群智能概念，将群体中的所有多量子比特视为智能种群，即量子群。首先，QPSO找到局部最佳量子角，并从局部最佳量子角中找到全局最佳量子角。然后根据这些值，用量子角更新公式更新量子角。

基于QEA的QPSO步骤如下：

2)通过|cos(θ)2|观察Q(t)的状态，把Q(t)投影到二进制解P(t)。对于多量子比特中的每一比特xj，其由量子角θ与0和1之间的随机变量得到：如果rand(0,1)>|cos(θ)|2，则生成1；否则生成0，即：

(8)

3)使用以下PSO位置更新公式替换传统“量子门更新Q(t)”步骤：

(9)

3.2 改进QPSO算法(IQPSO)

为了提高QPSO算法的收敛性和跳出局部最优的能力，分别引入动态惯性权重和变异操作对其进行改进。

3.2.1 动态惯性权重

从式(9)可以看出，惯性权重w决定了对当前量子角度的继承程度，传统PSO中将其设置为恒定值。然而，恒定的w不能适应动态的收敛过程。在算法搜索的前期，较大的w有利于跳出局部最优；在搜索后期，较小的w有利于局部寻优[15]。为此，引入了动态惯性权重，使w随着迭代数量的增加而递减，表示为：

(10)

式中：wmax和wmin为w的上限值和下限值，通常设定为0.9和0.4；Tmax为算法的最大迭代轮数，ite为当前迭代轮数。

3.2.2 变异操作

QPSO算法虽然引入了PSO中的角度更新机制和动态惯性权重，但其在迭代后期的角度变化幅度越来越小，仍有可能陷入局部最优。为此，本研究融入了一个变异机制来改进QPSO算法：当判断其迭代解停止不前时，启动变异过程。

首先，建立一种机制来判断QPSO寻优过程是否处于停止不前状态。本研究以全局最佳值Fgbest与平均个体最佳值Fpbest的比例关系kg-p作为判断依据，其中设定取N=20次连续迭代中的个体最佳值来取平均。表达式如下：

(11)

如果连续N次迭代后，量子的个体最佳角度几乎没有改变，即kg-p趋于1，那么判断此时的寻优过程处于停止不前状态。

然后，建立一种变异机制。选择一些量子进行变异操作，根据粒子与全局最优角度的距离作为变异概率，将远离最优角度的量子进行大概率变异，以提高种群跳出局部最优的能力。其中，距离用适应度值来表示。假设量子种群数量为M，那么各量子的变异概率

(12)

最后，通过随机函数rand(0,1)为每个量子产生一个随机值，若该值小于该量子的变异概率pi，则通过量子非门实现量子中1/2个量子位的变异，量子非门变异操作表示如下：

(13)

3.3 关联规则挖掘过程

基于上述IQPSO算法，最终得到关联规则挖掘过程如算法2所示。

算法2：IQPSO关联规则挖掘算法

输入：实例数据集，最小置信度，支持度阈值，种群数量M，最大迭代次数Tmax，学习因子，权重w的上限和下限值，变异概率pi

输出：一组最佳关联规则

begin

t←0；

初始化包含多个量子比特个体Q(t)的种群，并使用量子角编码量子比特；

把Q(t)投影到二进制解P(t)中；

计算P(t)的适应度函数；

If存在关联规则

Then从每个P(t)上生成关联规则；

endif

存储P(t)中的最佳解；

while(结束条件)do

t←t+1；

把Q(t-1)投影到二进制解P(t)中；

计算P(t)的适应度函数；

If存在关联规则

Then从每个P(t)上生成关联规则；

endif

使用包含动态w的式(12)更新Q(t)中量子角；

存储P(t)中的最佳解；

IfN次迭代后寻优过程处于停止不前状态

Then计算量子变异概率，通过量子非门进行变异操作；

endif

enddo

end

4 实验及分析

4.1 实验设置

将提出的IQPSO关联规则挖掘算法与文献[16]提出的Apriori规则挖掘算法进行比较。为了体现IQPSO的改进效果，将其与传统QPSO[9]的关联规则算法进行比较。所有实验均在配备Intel Core i7处理器(3.4 GHz主频、8 G内存)和Windows 10的PC电脑上进行。使用MATLAB编程。其中，IQPSO算法的种群数量为30，最大迭代次数设置为200次，变异概率pi=0.01。Apriori和QPSO的参数设置分别参考文献[16]和文献[9]。

为了验证本文算法的有效性，选择了一个由加州大学建立的国际标准机器学习数据库(UCI)中的幼儿园数据集作为实验数据集。幼儿园数据库最初是为幼儿园入学申请排名而设计的分层数据模型,包含12 960个实例和9个属性，以及各自的分类。另外，为了将本算法应用到实际的高校教学管理系统中，更好服务于课程设置和教学改革，收集了学校几届计算机应用技术专业的200名大学生的10门课程成绩，构建了一个课程成绩数据集，按成绩分为优、良、中、及格和不及格5类。从学生各门课程的成绩中挖掘关联规则，为学校合理安排课程和教师了解学生情况提供帮助。两个数据集的属性如表1所示。

表1 数据库属性

4.2 算法收敛速度分析

为了验证IQPSO算法在收敛速度方面的优势，采用标准的最优化问题测试函数-Sphere函数，该函数是一个理论最小值为0的非线性对称的单峰函数，用于测试寻优速度，表达式为：

(14)

设置各种算法的种群数量为30，最大迭代次数为250，Sphere 函数的维度为20。三种算法对Sphere 函数进行极小值搜索的收敛曲线如图1所示。可以看到，三种算法都能收敛，但IQPSO算法的收敛速度最快，大约在80次迭代后就收敛到0，而PSO和QPSO算法分别需要约180次和120次迭代。这是因为，IQPSO中融入了变异机制和动态权重机制，这些操作的计算量很低，不会增加算法单次运行的时间。然而，这些改进可有效避免算法嵌入局部最优，减少无效搜索的次数，提高算法的收敛速度。

图1 20维Sphere函数的收敛曲线

4.3 规则挖掘的执行时间比较

为了验证提出的算法在关联规则挖掘应用上的实际性能，在幼儿园数据库上进行了相关实验。在实例数目和置信度阈值一定时，对不同支持度阈值下的算法在运行时间方面进行比较。其中，选择4 000个实例进行实验，最小置信度为0.7，支持度阈值为0.5～0.75。当各种算法挖掘的规则达到最小支持度阈值时停止，并统计执行时间。实验结果如图2所示。

从图2可以看到，随着支持度阈值的增加，算法所运行的时间逐渐减少。这是因为当支持度阈值比较小时，能够满足条件的关联规则较多，算法的运行时间较长。其中，QPSO算法的性能优于Apriori算法，这是因为QPSO算法是一种高效的智能优化算法，能够快速收敛到最优解。而IQPSO算法执行时间最短，且对于传统QPSO算法有明显提高。这是因为，IQPSO中融入了变异机制和动态权重机制，提高算法的收敛速度，缩短了挖掘关联规则的执行时间。

接着，在固定最小置信度和最小支持度下，在不同数量的实例数据集上进行实验，比较各种算法的执行时间。其中，置信度设置为0.7，最小支持度设置为0.65，数据集实例数量为4 000到8 000，结果如图3所示。可以看出，随着实例数目的增加，算法的运行时间均逐渐增加。在各种情况下，IQPSO的运行时间都是最短的，且随着实例数量的增加，改善效果更加明显。

图2 不同支持度阈值下各种算法的执行时间

图3 不同实例数量下各种算法的执行时间

另外，对于课程成绩数据集，由于实例数量较少，各种算法的运行时间都比较短(3 s以内)且差距很小，不像在幼儿园数据库上能看出明显差异。

4.4 规则挖掘质量比较

从包含4 000个实例的幼儿园数据库中进行规则挖掘来比较所挖掘的规则质量。这里指定一个目标属性，即“推荐”，将IQPSO算法与文献[16]的Apriori算法和文献[17]基于遗传算法(GA)的挖掘算法进行对比。

对于目标“推荐=不推荐”，利用三种算法发现的最佳规则如表2所示。对比发现，相比其他两种算法，提出的IQPSO算法发现的规则更加有价值。例如：

IF “幼儿园=适合”、“孩子=2”、“住房=不方便”、“金融=不方便”、“社会=没有问题”并且“身体=不健康”；

THEN “推荐=不推荐”。

该规则的支持度|C&P|为446，置信度b为0.97，适应度为0.436。

对于目标“推荐=特别优先”，利用三种算法发现的最佳规则如表3所示。Apriori规则的置信度b为0.94，适应度为0.411。GA规则的置信度和适应度要比Apriori规则高，因为GA是一种群体智能算法，收敛效果较好。类似表2，除了GA、Apriori发现的规则外，IQPSO算法还发现了其他更有趣的规则，如表3，其支持度|C&P|为348，置信度b为1.00，适应度=0.438。

上述两个规则挖掘实验结果表明了IQPSO关联规则挖掘算法所挖掘的规则具有更高的价值。这是因为GA算法的全局搜索能力较弱，容易陷入局部最优。IQPSO算法通过融入变异机制和动态惯性权重，对QPSO进行了更深层次的改进，提高了算法性能，所以能够挖掘到最优的规则。

表2 幼儿园数据库目标“推荐=不推荐”的规则挖掘结果

表3 幼儿园数据库目标“推荐=特别优先”的规则挖掘结果

然后，在学生成绩数据集中进行同样的实验，三种算法挖掘出来的前两个规则分别如表4所示。这里举例分析本方法挖掘出的第一条关联规则：

IF “EE>=良好”并且“CUE>=及格”；THEN “CMU>=中等”。

这条规则的意思是，一个学生的电装实习(EE)成绩优良且计算机硬件原理(CUE)及格，通常计算机维护与升级(CMU)的成绩也会中等以上。这就说明电装实习与计算机维护与升级之间存在很大的相关性，电装实习优秀的学生通常动手能力较好，加上一定的硬件原理基础，就会使其在计算机维护与升级中获得好成绩。所以在今后教学中可以加强对学生电路组装等方面动手能力提升的关注。

表4可见，在三种算法中，IQPSO算法获得规则的适应度最高，说明了本文方法的有效性。

表4 学生成绩数据集中规则挖掘结果举例

在关联规则挖掘应用中，算法会挖掘出很多条规则，通常只需要选取一些高质量的规则来分析和指导实践。为了更加全面地评测各种算法的性能，通过上文描述的适应度函数来表征规则质量。在2个数据集上分别选择出前10条高质量规则，然后计算平均适应度值，结果如表5所示。从表5可以看出，IQPSO算法不仅能够挖掘出最优关联规则，在前10条规则的平均性能方面也具有一定的优越性。

表5 前10条规则的平均适应度

5 结束语

为了提高QPSO算法的性能，融入了变异机制和动态惯性权重形成IQPSO。在UCI和课程成绩数据集上，将提出的IQPSO与QPSO、Apriori规则挖掘算法进行比较，证明IQPSO算法具有快速收敛的能力，且所挖掘的规则比Apriori算法更为合理。

未来会将提出的算法应用于更大规模的数据集中，通过对算法进行优化进一步提高执行效率。此外，通过结合其他的机器学习算法，进一步提高挖掘到的规则的价值。