基于双链量子遗传优化的分类规则挖掘算法*

张宇献，陈向文，钱小毅

(沈阳工业大学 a. 电气工程学院，b. 信息科学与工程学院，沈阳 110870)

基于规则的分类系统(rule-based classification systems，RBCSs)由若干条包含数值型前件的规则构成，通过对训练样本的学习实现规则挖掘，根据规则与新样本的匹配程度进行分类.与其他分类系统相比，基于规则的分类系统除了可同时处理专家知识、数学模型和经验数据等多源信息，其输出结果还具有极强的可解释性，给决策者或操作者提供了更好的决策依据，因此，系统被广泛应用于纵多领域[1-2].

文献[3]提出一种基于小生境遗传算法的规则提取算法，从规则编码、适应度设计、搜索策略三个方面做了讨论和分析，但算法耗时长，计算量大，同时种群多样性差；文献[4]通过改进基因表达式编程(GEP)提出兼顾规则一致性增益和完备性的适应度函数，但是GEP采用多基因染色体模式解决问题时，染色体中基因数目不好控制；文献[5]提出一种基于粗糙集增量式规则自动学习的方法获取分类规则，避免了繁琐的重训练过程，但此方法不能准确找到规则进行样本分类且更新过程繁琐；文献[6]通过采用自适应信息素更新和更换启发式函数的蚁群算法(ACO)实现分类规则的挖掘，精度有所提升，但是算法收敛速度缓慢，且易陷入局部最优解；文献[7]在ACO算法的基础上提出了一种自适应蚁群算法，通过动态调整决定性选择概率和波动系数值，加快ACO收敛速度，但搜索空间有限且鲁棒性较差；文献[8]将粒子群算法(PSO)用于分类规则挖掘，通过改变粒子群的位置和速度以及适应度评价指标减少分类规则数目和缩短运行时间，但此方法易早熟收敛，且寻优能力差.

上述基于规则的分类算法中普遍存在着全局搜索能力不强、鲁棒性和种群多样性较差的问题.本文提出基于双链量子遗传的分类规则挖掘算法(DCQGA-CRM)，该算法以双链量子遗传算法为框架，采用双链量子和目标函数梯度信息进行分类器构建，将量子比特的两个概率幅作为基因位描述可行解，利用量子旋转门加快规则挖掘收敛速度，通过量子非门对规则前件进行变异.

1 基于规则的分类系统

分类系统由多条分类规则表示，通过分析训练样本数据构建分类系统模型，进而检验分类精确度，实现对未来采集样本数据分类.每个数据样本可看作由条件属性和类标签(目标属性)组成，其表达式为

Vq=(vqj，gl)

(1)

式中：vqj为第q个样本第j个条件属性值，q=1，2，…，N，j=1，2，…，n；gl为第l类标签，l=1，2，…，c.

通常用具有高层次性和象征性的If-Then分类规则来搭建分类器模型，典型的分类规则形式为

Rk：ifA1=xk1and … andAj=xkjthenCk=gkl

(2)

式中：Aj为第j个条件属性；Ck为第k条规则所属类别；gkl为第k条规则第l类标签.

精确度是评价基于规则分类器的重要指标，分类精度越高，表明分类器分类效果越好.本文用正确分类样本数占分类样本总数的比例表示精确度.

分类问题中样本正确分类数目确定过程如下：1)计算样本数据与分类规则前件差；2)选择前件差最小值作为样本适用规则；3)对样本分类，设样本正确分类数目初值为零，比较样本类标签gl和分类规则类标签gkl是否相等.

采用测试样本对分类模型进行检验，精度越高，表明搭建分类器模型越好，进而对新测试样本数据进行分类，赋予类标签.

2 基于DCQGA的分类规则挖掘

量子遗传算法(QGA)是在遗传算法的基础上，将量子理论引入到其中的智能优化算法.本节将双链量子与分类规则挖掘相结合，主要过程包括量子位实数编码、解空间变换、量子旋转门操作和量子非门变异几个部分.

2.1 量子位实数编码

DCQGA-CRM采用双链量子位实数编码方式产生分类规则，每个个体包含上下两条基因链，每条基因链对应优化问题的一个分类规则.在种群规模一定的条件下，通过双链量子位实数编码方式增加种群多样性，加倍搜索空间.

QGA以充当信息存储单元的双态量子比特系统为基础，用量子比特表示染色体，两个量子态的线性叠加态表示一个量子位，其形式为

|φ〉=γ|0〉+β|1〉

(2)

式中，γ、β为量子比特的概率幅，满足归一化条件.考虑归一化约束性，用概率幅编码，则DCQGA-CRM双链编码方式表示为

(3)

式中，costij、sintij为第i个种群、第j个量子位的两个概率幅值.

2.2 解空间变换

双链量子实数编码产生分类规则的概率幅在[-1，1]之间，与原始样本数据存在差异.利用解空间变换将量子位概率幅转换为指定范围内相对应实数集，便于分类规则与样本对比.由于每条染色体含有2m个量子位的概率幅，可利用线性变换将m维单位空间Im=[-1，1]转换到实数解空间.令aj表示第j个量子位下限值，bj表示第j个量子位上限值，则相应解空间变换为

(4)

2.3 量子旋转门转角方向

量子旋转门操作的作用是促使染色体上每个基因位概率幅值收敛到预先设定幅值，从而使其收敛到全局最优解.量子旋转门表达式为

(5)

(6)

量子旋转门更新过程中，旋转角方向和大小是根据预先设定调整策略确定的.量子旋转门只改变相位大小，不改变量子位长度.量子基因位幅值对收敛速度造成直接影响，其值一般设置为0.001π～0.1π.

2.4 量子旋转门转角大小

量子旋转门转角大小更新策略为：目标函数在搜索点处梯度较大，即所处搜索过程较陡时，适当减小步长，避免越过全局最优解；反之，适当增大步长，加速其搜索过程，尽快搜寻到全局最优解.根据搜索点处目标函数梯度变化确定搜索点处步长，即

(7)

2.5 量子变异

依据变异概率选择最优染色体，对染色体量子位施加量子非门操作，通过改变量子位概率幅使两条基因链上量子位同时得到变异，其变异过程为

(8)

基于双链量子遗传优化的分类规则挖掘算法流程图如图1所示.

图1 DCQGA-CRM算法流程图Fig.1 Flow chart of DCQGA-CRM algorithm

3 实验与结果分析

本文选取UCI数据库中9个数据集对算法的分类精度和鲁棒性进行对比分析.首先将所提算法与两种基于规则的分类算法(Michigan算法和Pittsburgh算法)进行对比分析.在此基础上，在训练集中添加类噪声，将所提算法与Michigan算法[9]、Pittsburgh算法[10]、C4.5算法[11]和BP神经网络[12]进行对比，验证所提算法的噪声容忍度.

3.1 数据集与算法评价指标描述

数据集具体描述如表1所示，其中，#Ex.为样本数，#Atts.为属性数，#Class.为类别数.

表1 UCI数据集描述Tab.1 Description of UCI datasets

本文采用样本正确分类数占样本总数的比例来进行描述分类精度；引入相对损失精度RLA来描述鲁棒性优劣，其定义为

(9)

式中：e0%为原始数据集下测试分类精度；ex%为噪声水平下测试分类精度.

为验证所提出的DCQGA-CRM与其他分类算法相比具有显著性能，采用Wilcoxon符号秩检验[9]进行显著性测试.比较检验概率p值与显著水平α的大小，判断两个算法预测阶段平均值与各自所代表的总体差异是否显著，本文选取显著水平α=0.05.本实验采用5折交叉验证方式进行算法性能验证，即将数据集随机分成5等份，选取其中的4份作为训练样本集，其余部分作为测试样本，实验结果选取5次运行结果平均值和标准差.

3.2 分类精度分析

将本文算法与Michigan算法和Pittsburgh算法进行分类精度比较分析，各算法参数设置如表2所示.

表2 不同算法参数设置Tab.2 Parameters settings of different algorithms

表3为DCQGA-CRM与Michigan算法和Pittsburgh算法分类精度对比，分别记录了各算法对9组数据集的训练精度(eTr)与测试精度(eTst)结果，精度值后面的数值为分类精度的标准差.由表3可以看出，在9个数据集的实验结果中，DCQGA-CRM在测试结果的分类正确率明显高于其他两种对比算法.将DCQGA-CRM与Michigan算法、Pittsburgh算法的Wilcoxon符号秩检验进行对比，本文所提出算法得到的检验概率p值均小于0.05，说明本文提出的DCQGA-CRM与Michigan算法、Pittsburgh算法相比，分类性能有显著性提高.

表3 DCQGA-CRM与其他分类算法分类精度对比Tab.3 Comparison in classification accuracy between DCQGA-CRM and other classification algorithms %

表4为本文所提算法与其他算法在分类精度实验中数据集单次运行的时间对比，其中，Pittsburgh算法和本文提出算法中的单个个体均代表一个分类器，因此，单次运行的时间要高于以单条规则为优化对象的Michigan算法，但本文所提算法采用量子旋转门策略提高了单次迭代的运行速度.

表4 各算法运算时间对比Tab.4 Comparison of operation time among different algorithms s

3.3 分类鲁棒性分析

通过向训练数据集中加入类噪声来分析DCQGA-CRM的噪声容忍度.采用不同类噪声水平(noise level，NL)测试其预测精度，并通过相对损失精度RLA分析算法在类噪声作用下的噪声容忍度.

本实验还选择了对类噪声容忍度较强的C4.5算法和BP神经网络进行比较分析.图2为噪声水平分别取NL=10%，20%，30%，40%和50%时不同算法对样本数据集的分类精度.在大多数数据集情况下，DCQGA-CRM类噪声容忍度优于其他算法.

图2 不同噪声水平下DCQGA-CRM与其他算法分类精度对比Fig.2 Comparison of classification accuracy between DCQGA-CRM and other algorithms under different noise levels

本文给出了类噪声分别为10%、30%、50%时的RLA值，如表5所示.表5中，(·)值表示同一噪声水平下各算法的RLA值排名，Av.Rank表示各算法在9个数据集测试中的平均排名.从表5中可以看出，DCQGA-CRM的RLA在大多数情况下小于其他对比分类算法，拥有良好的噪声容忍度.

4 结 论

本文针对智能优化分类规则挖掘算法中分类精度低及噪声容忍度差等问题，提出一种DCQGA-CRM算法，以基于规则的分类系统为框架，采用双链量子实数编码增加搜索空间多样性，通过量子旋转门操作和量子非门进行策略更新，利用目标梯度函数避免陷入局部最优解.实验利用UCI数据库中9个数据集，将所提出的DCQGA-CRM与对比分类方法相比，实验结果表明，DCQGA-CRM具有较高分类精度和噪声容忍度.相对精度损失RLA和Wilcoxon符号秩检验表明，DCQGA-CRM与其他分类方法相比，噪声容忍度有显著性提高.

表5 不同噪声水平下DCQGA-CRM与其他算法的RLA对比Tab.5 Comparison of RLA between DCQGA-CRM and other algorithms under different noise levels