一种新的基于量子遗传算法的ECOC算法

摘  要：纠错输出编码（ECOC）將多分类问题转化为二类问题进行求解。其中，影响ECOC性能的关键因素是最优编码矩阵，为构建有效的最优编码矩阵，文章提出一种新的基于量子遗传算法的ECOC算法。首先，将ECOC矩阵作为量子遗传算法中的个体，使用量子位编码重新生成编码矩阵。随后，利用交叉、变异、量子旋转门等遗传算子，使ECOC算法朝着最优的方向进化。在12个标准UCI数据集上进行的实验表明所提出算法具有良好的分类性能。

关键词：多分类；纠错输出编码；量子遗传算法

中图分类号：TP312  文献标识码：A  文章编号：2096-4706（2023）10-0022-04

Abstract： Error Correcting Output Codes （ECOC） transforms the multi-class classification problems into the two-class problems to solve. The key factor affecting the performance of the ECOC is the optimal coding matrix. In order to construct an efficient and optimal coding matrix， a new ECOC algorithm based on Quantum Inspired Genetic Algorithm is proposed in this paper. Firstly， one ECOC coding matrix is regarded as one individual in Quantum Inspired Genetic Algorithm， and the coding matrix is reconstructed by the q-bit coding. Then， the genetic operators such as crossover， mutation， quantum rotating gate are used to make the ECOC algorithm evolve toward the optimal direction. Experiments conducted on 12 standard UCI data sets show that the proposed algorithm has better classification performance.

Keywords： multi-class classification; ECOC; Quantum Inspired Genetic Algorithm

0  引  言

在模式识别等领域中，多分类问题是指将样本分为N（N＞2）类。相较于二分类任务，多分类问题的分类更困难，成为模式识别等领域中的研究难点和热点[1]。目前解决该问题的普遍方法是分治法。其中应用最为广泛的分治策略是纠错输出编码[2]（ECOC）。ECOC算法已被广泛应用于各种多分类任务场景中，例如交通标志识别，人脸识别[3]，行为识别[4]等。

ECOC算法性能的关键因素是在编码过程中生成判别能力强的编码矩阵。据此，研究人员针对编码过程进行了研究，试图找到最优的编码方案。然而，最优编码矩阵的设计已经被证明是一个NP难问题[5]。因此，一些学者提出使用优化算法解决该问题。其中，遗传算法（GA）作为一个著名的优化算法，被广泛应用于编码矩阵的寻优。Lorena等[6]在研究将SVM扩展到多分类问题中时，首次提出了使用遗传算法来优化编码矩阵，取得了良好的效果。Bautista等[7]使用遗传算法优化最小ECOC矩阵，进而提出最小ECOC算法。不同于直接利用遗传算法对编码矩阵进行优化的方法，Ye等[8]通过设计新的个体结构以获得更好的分类性能。Wang等[9]提出一种新的结合ECOC和遗传编程的算法，并将其用于微阵列数据的分类。

量子遗传算法（QGA）是一种量子启发进化算法[10]。状态叠加的相干性和并行性，量子门的旋转和量子寄存器的自旋等量子原理保持了种群的多样性并扩大了搜索范围，从而使优化比GA更有效。利用量子遗传算法较强的优化效率，本文尝试将其应用于ECOC编码矩阵优化中。据此，提出一种基于量子遗传算法的ECOC算法，简称为QECOC。在该算法中，首先随机生成一组个体编码矩阵。每一个个体代表一个编码矩阵，直接由量子编码观测生成。其次，将分类准确率用作适应度函数，通过ECOC解码过程计算个体的适应度值。随后，个体经历交叉、变异和量子旋转门等操作以产生新的一代。最终使得种群向最佳编码矩阵方向进化。

1  相关工作

1.1  纠错输出编码

纠错输出编码（ECOC）处理多分类问题的有效性使得其得到了科研人员们的广泛关注。ECOC算法包含两个步骤：编码过程和解码过程。其中，编码过程是将多分类问题分解为一系列二分类问题的过程。分解方案由编码矩阵生成，矩阵中的每一行代表一个类，每一列表示一个二元问题，每一个二元问题则需要通过生成一个二类分类器来解决。

在解码阶段，所有基分类器对未知样本S0的分类结果组成了一个结果向量。计算该结果向量与编码矩阵中的每一行的编码字之间的距离，并将S0分配到距离最小的行所代表的类中。常用的距离计算方法为汉明距离，如式（1）所示：

1.2  量子遗传算法

经典的QGA计算过程如下：

1）创建一个随机种群，种群中的每一个个体被编码为量子位个体；2）通过观测操作将所有量子位染色体收缩到确定的量子位状态；3）计算每一个个体的适应度，选择具有最高适应度的个体作为当前种群的最优个体；4）执行进化过程。使用旋转门、交叉、变异等操作来指导其他个体向着最优个体进化。进化过程产生的后代与当前种群一起执行选择操作，以确定下一代种群；5）整个进化过程一直持续到最优个体满足优化要求或迭代次数达到预定义值。

1.2.1  量子位编码

在QGA中，量子位是基本信息单元，它能够表示任何0和1的线性叠加态。QGA的一个量子位由式（2）给出：

其中，复数α和β分别表示状态  和状态  的概率辐，α和β满足归一化条件：

根据式（2），每一个量子位  可以被看作二维平面中的一个点，该平面以  为横坐标，以  为纵坐标。由于α和β为复数，因此一个量子位至少需要两个实数的存储空间。为了减少算法的运行存储空间需求，提出了一种用三角函数表示量子位的方法，如式（4）所示：

使用角度的形式表示量子位的方法不仅减少了存储空间，而且使量子旋转门的操作更加容易。

1.2.2  量子旋转门

在QGA中，旋转门用于指导染色体的进化过程，使得当前种群中的每个个体都向适应度最高的个体靠近。与GA中的二进制状态相比，旋转门的使用使得QGA有可能获得全局最优值，这是由于量子位具有多种叠加状态。

经典的旋转门操作是通过与旋转矩阵的乘积实现的。为降低旋转门操作的计算复杂性，提出了一种基于式（5）的改进的量子旋转门。它通过加减角度操作修改量子位角度θ。量子位的更新规则如下：

其中，θ和θ′分别表示更新前和更新后的量子位角度；θop表示最优个体的量子位角度；δ是一个任意小的角度，称为旋转角；sign （Δθ）是一个符号函数。其他个体的量子位角度在每次进化时朝着最优个体的量子位角度旋转。δ的大小对算法收敛速度有显著影响。δ过大会导致早熟，而δ过小又会导致算法收敛太慢。通常将δ的值设置在0.001π～0.5π之间。

通过旋转门更新之后的量子位角度可能变为0或π/2，此时状态  或  的概率辐接近1。这种量子位收缩不是我们期望的，因为其导致QGA的个体变为确定态，即丧失了种群多样性。为了防止这种情况的发生，提出式（7）所示的改进方法：

其中，ε是一个任意小的角度。

2  量子遗传算法用于ECOC

2.1  量子位编码表示

在遗传算法与ECOC结合的GA-ECOC算法，一个ECOC矩阵被视为遗传算法的个体。而在所提的QECOC中，个体是使用量子位编码表示的，因此首先需要将ECOC编码矩阵转换为使用量子位编码表示的矩阵。

传统的二元ECOC编码矩阵由2种符号组成，编码矩阵中的‘1和‘0代表了生成二类分类器时每一个类的确定的状态。在使用QGA算法时，要使用量子位编码代替确定的二进制编码，从而使每一个类的状态变得不确定。根据第1章对量子位编码的描述，我们选择使用量子角度表示ECOC编码矩阵中的每一个元素。根据多分类问题的类别数N和生成的分类器数量l，生成一个大小为N×l的量子位编码矩阵，矩阵中的每一个元素为[0， π/2]范围内的一个角度。

2.2  量子位观测

观测操作将不确定的量子位编码收缩为确定的二进制值，该二进制值被称为量子位的观测值。图1展示了上述量子位编码矩阵的一次观测结果：

假设一个大小为N×l的量子位编码矩阵，其中的每一个元素用对应的角度表示。对量子位编码矩阵中的每一个元素，使αi， j =cosθi， j。首先计算所有元素的α值，然后生成[0， 1]范围内的随机数x。若αi， j ＞x，则该位置为1；否则置为0。观测操作完成，量子位矩阵将收缩为一个确定的二元编码矩阵。

对观测得到的二进制编码矩阵进行个体性能的评估，并进行后续的进化操作。为了确保编码矩阵的合理性，我们提出了以下对观测操作的改进方法：首先对矩阵中的每一列元素的α值進行排序，使α最大的位置为1，α最小的位置为0，其他位置的元素的观测结果不变。其次对于出现元素值全为0的行，生成一个[1，l]之间的整型随机数pos，将pos位置的编码置为1。

2.3  适应度

在QGA中，需要对每一个个体进行评估以确定该个体的性能。本文使用所有类的平均分类准确率作为个体的适应度。对于数据集中的第i类，该类的样本数量为NCi，正确分类的样本数量为Ti，平均分类准确率由式（8）给出：

2.4  交叉和变异

通常情况下，QGA的进化过程是通过旋转门实现的。然而，量子旋转门引导所有个体向着当前最优个体的方向进化，导致在进行旋转门操作之后，不同个体之间的适应度差异变小，因而种群的多样性倾向于降低，最终导致算法不能收敛到最优解。为了扩展种群的多样性，引入遗传算法中的交叉和变异算子。

交叉算子随机选择种群中的两个个体执行列交叉操作，产生与双亲个体完全不同的新个体。首先随机选择两个个体作为父本，并生成一个整型随机数作为交叉点。每个父本在交叉点的位置分为两个部分，双亲个体在交叉点之后的部分互换，从而产生新的个体。交叉操作的示意图如图2所示。

新生成的个体放入后代种群池中，不参与后续的进化过程。

在本文使用的QGA中，我们也引入了变异算子。变异操作旨在改变量子位的叠加状态。若一个量子位在突变之前趋向于收缩为状态  ，那么在变异之后应该趋向于收缩为状态  。突变操作描述为：

其中， 为变异之前的量子角度； 为变异之后的量子角度。变异之后，量子位向状态  和状态  的收缩概率转变。

本文使用了两种不同的变异算子：1）随机改变量子位编码矩阵中的某一个元素，如图3（a）所示；2）改变量子位编码矩阵中的某一列的值，如图3（b）所示：

3  实验分析

3.1  数据集

本次实验使用12个UCI数据集[11]，详细信息列在表1中。所有的数据集都被分为训练集和测试集，其比例为9：1。其中训练集用于训练基分类器。测试集作为未知数据用于评估算法的性能，在测试集上获取的分类准确率用于算法的性能比较。

3个ECOC算法被选择用以与所提算法进行性能对比，它们分别是：随机编码[2]（Random），GECOC[8]和Impro-GECOC[9]。

3.2  实验设置

在我们的QGA框架中，种群的尺寸为20个，最大迭代次数为100。变异率设置为0.25。在实验中，将分类准确率作为算法性能的评估标准。表2～表4分别列出了在测试集上使用DT，KNN和NB三种分类器得到的不同算法的分类准确率对比结果，其中最优的结果用黑体标出。

由表2～表4分类准确率结果对比可知，QECOC算法在大部分数据集上取得最好的分类准确率，证明了算法的有效性。

4  结  论

本文提出了一种新的基于量子遗传算法的ECOC算法用于处理多分类数据集。该算法将一个ECOC矩阵进行量子位编码后作为量子遗传算算法的个体，使用量子旋转门、交叉、变异等遗传算子进行演化以生成最优的编码矩阵。在多个数据集上的实验结果证明了该算法的有效性。

参考文献：

[1] KRAWCZYK B，GALAR M，WOZNIAK M，et al. Dynamic ensemble selection for multi-class classification with one-class classifiers[J].Pattern Recognition，2018，83：34–51.

[2] ALLWEIN E L，SCHAPIRE R E，SINGER Y. Reducing multiclass to binary：a unifying approach for margin classifiers [J].Machine Learning，2001，1 （2）：113–141.

[3] NAZARI S，MOIN M S，KANAN H R. Securing templates in a face recognition system using Error-Correcting Output Code and chaos theory [J].Computers & Electrical Engineering，2018，72：644–659.

[4] QIN J，LIU L，SHAO L，et al. Zero-shot action recognition with error-correcting output codes [C]//IEEE Conference on Computer Vision and Pattern Recognition.Honololo：IEEE，2017：1042-1051.

[5] CRAMME K，SINGER Y. On the learn ability and design of output codes for multiclass problems [J].Machine Learning，2002，47（2-3）：201-233.

[6] LORENA A C，ANDRE C P，CARVALHO L F. Evolutionary design of multiclass support vector machines [J].Journal of Intelligent & Fuzzy Systems，2007，18：445–454.

[7] BAUTISTA M A，ESCALERA S，BARO X，et al. Minimal design of error-correcting output codes [J].Pattern Recognition Letters，2012，33：693-702.

[8] YE X，LIU K. A novel genetic algorithm based ECOC algorithm [C]// 2018 14th International Conference on Semantics，Knowledge and Grids.Guangzhou：IEEE，2018：241-244.

[9] WANG H，LI K，LIU K. A genetic programming based ECOC algorithm for microarray data classification [C]//24th International Conference，ICONIP 2017.Guangzhou：Springer，2017：683-691.

[10] DAHI Z A E M，MEZIOUD C，DRAA A. A quantum-inspired genetic algorithm for solving the antenna positioning problem [J]. Swarm and Evolutionary Computation，2016，31：24-63.

[11] DUA D，TANISKIDOU E K.UCI machine learning repository [DB/OL].[2022-10-05].http：//archive.ics.uci.edu/ml.

作者簡介：周大鹏（1997—），男，汉族，河南南阳人，硕士研究生在读，研究方向：机器学习。