摘? 要：糾錯(cuò)輸出編碼（ECOC）將多分類(lèi)問(wèn)題轉(zhuǎn)化為二類(lèi)問(wèn)題進(jìn)行求解。其中，影響ECOC性能的關(guān)鍵因素是最優(yōu)編碼矩陣，為構(gòu)建有效的最優(yōu)編碼矩陣，文章提出一種新的基于量子遺傳算法的ECOC算法。首先，將ECOC矩陣作為量子遺傳算法中的個(gè)體，使用量子位編碼重新生成編碼矩陣。隨后，利用交叉、變異、量子旋轉(zhuǎn)門(mén)等遺傳算子，使ECOC算法朝著最優(yōu)的方向進(jìn)化。在12個(gè)標(biāo)準(zhǔn)UCI數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)表明所提出算法具有良好的分類(lèi)性能。

關(guān)鍵詞：多分類(lèi)；糾錯(cuò)輸出編碼；量子遺傳算法

中圖分類(lèi)號(hào)：TP312? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：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? 引? 言

在模式識(shí)別等領(lǐng)域中，多分類(lèi)問(wèn)題是指將樣本分為N（N＞2）類(lèi)。相較于二分類(lèi)任務(wù)，多分類(lèi)問(wèn)題的分類(lèi)更困難，成為模式識(shí)別等領(lǐng)域中的研究難點(diǎn)和熱點(diǎn)[1]。目前解決該問(wèn)題的普遍方法是分治法。其中應(yīng)用最為廣泛的分治策略是糾錯(cuò)輸出編碼[2]（ECOC）。ECOC算法已被廣泛應(yīng)用于各種多分類(lèi)任務(wù)場(chǎng)景中，例如交通標(biāo)志識(shí)別，人臉識(shí)別[3]，行為識(shí)別[4]等。

ECOC算法性能的關(guān)鍵因素是在編碼過(guò)程中生成判別能力強(qiáng)的編碼矩陣。據(jù)此，研究人員針對(duì)編碼過(guò)程進(jìn)行了研究，試圖找到最優(yōu)的編碼方案。然而，最優(yōu)編碼矩陣的設(shè)計(jì)已經(jīng)被證明是一個(gè)NP難問(wèn)題[5]。因此，一些學(xué)者提出使用優(yōu)化算法解決該問(wèn)題。其中，遺傳算法（GA）作為一個(gè)著名的優(yōu)化算法，被廣泛應(yīng)用于編碼矩陣的尋優(yōu)。Lorena等[6]在研究將SVM擴(kuò)展到多分類(lèi)問(wèn)題中時(shí)，首次提出了使用遺傳算法來(lái)優(yōu)化編碼矩陣，取得了良好的效果。Bautista等[7]使用遺傳算法優(yōu)化最小ECOC矩陣，進(jìn)而提出最小ECOC算法。不同于直接利用遺傳算法對(duì)編碼矩陣進(jìn)行優(yōu)化的方法，Ye等[8]通過(guò)設(shè)計(jì)新的個(gè)體結(jié)構(gòu)以獲得更好的分類(lèi)性能。Wang等[9]提出一種新的結(jié)合ECOC和遺傳編程的算法，并將其用于微陣列數(shù)據(jù)的分類(lèi)。

量子遺傳算法（QGA）是一種量子啟發(fā)進(jìn)化算法[10]。狀態(tài)疊加的相干性和并行性，量子門(mén)的旋轉(zhuǎn)和量子寄存器的自旋等量子原理保持了種群的多樣性并擴(kuò)大了搜索范圍，從而使優(yōu)化比GA更有效。利用量子遺傳算法較強(qiáng)的優(yōu)化效率，本文嘗試將其應(yīng)用于ECOC編碼矩陣優(yōu)化中。據(jù)此，提出一種基于量子遺傳算法的ECOC算法，簡(jiǎn)稱(chēng)為QECOC。在該算法中，首先隨機(jī)生成一組個(gè)體編碼矩陣。每一個(gè)個(gè)體代表一個(gè)編碼矩陣，直接由量子編碼觀測(cè)生成。其次，將分類(lèi)準(zhǔn)確率用作適應(yīng)度函數(shù)，通過(guò)ECOC解碼過(guò)程計(jì)算個(gè)體的適應(yīng)度值。隨后，個(gè)體經(jīng)歷交叉、變異和量子旋轉(zhuǎn)門(mén)等操作以產(chǎn)生新的一代。最終使得種群向最佳編碼矩陣方向進(jìn)化。

1? 相關(guān)工作

1.1? 糾錯(cuò)輸出編碼

糾錯(cuò)輸出編碼（ECOC）處理多分類(lèi)問(wèn)題的有效性使得其得到了科研人員們的廣泛關(guān)注。ECOC算法包含兩個(gè)步驟：編碼過(guò)程和解碼過(guò)程。其中，編碼過(guò)程是將多分類(lèi)問(wèn)題分解為一系列二分類(lèi)問(wèn)題的過(guò)程。分解方案由編碼矩陣生成，矩陣中的每一行代表一個(gè)類(lèi)，每一列表示一個(gè)二元問(wèn)題，每一個(gè)二元問(wèn)題則需要通過(guò)生成一個(gè)二類(lèi)分類(lèi)器來(lái)解決。

在解碼階段，所有基分類(lèi)器對(duì)未知樣本S0的分類(lèi)結(jié)果組成了一個(gè)結(jié)果向量。計(jì)算該結(jié)果向量與編碼矩陣中的每一行的編碼字之間的距離，并將S0分配到距離最小的行所代表的類(lèi)中。常用的距離計(jì)算方法為漢明距離，如式（1）所示：

1.2? 量子遺傳算法

經(jīng)典的QGA計(jì)算過(guò)程如下：

1）創(chuàng)建一個(gè)隨機(jī)種群，種群中的每一個(gè)個(gè)體被編碼為量子位個(gè)體；2）通過(guò)觀測(cè)操作將所有量子位染色體收縮到確定的量子位狀態(tài)；3）計(jì)算每一個(gè)個(gè)體的適應(yīng)度，選擇具有最高適應(yīng)度的個(gè)體作為當(dāng)前種群的最優(yōu)個(gè)體；4）執(zhí)行進(jìn)化過(guò)程。使用旋轉(zhuǎn)門(mén)、交叉、變異等操作來(lái)指導(dǎo)其他個(gè)體向著最優(yōu)個(gè)體進(jìn)化。進(jìn)化過(guò)程產(chǎn)生的后代與當(dāng)前種群一起執(zhí)行選擇操作，以確定下一代種群；5）整個(gè)進(jìn)化過(guò)程一直持續(xù)到最優(yōu)個(gè)體滿足優(yōu)化要求或迭代次數(shù)達(dá)到預(yù)定義值。

1.2.1? 量子位編碼

在QGA中，量子位是基本信息單元，它能夠表示任何0和1的線性疊加態(tài)。QGA的一個(gè)量子位由式（2）給出：

其中，復(fù)數(shù)α和β分別表示狀態(tài)? 和狀態(tài)? 的概率輻，α和β滿足歸一化條件：

根據(jù)式（2），每一個(gè)量子位? 可以被看作二維平面中的一個(gè)點(diǎn)，該平面以? 為橫坐標(biāo)，以? 為縱坐標(biāo)。由于α和β為復(fù)數(shù)，因此一個(gè)量子位至少需要兩個(gè)實(shí)數(shù)的存儲(chǔ)空間。為了減少算法的運(yùn)行存儲(chǔ)空間需求，提出了一種用三角函數(shù)表示量子位的方法，如式（4）所示：

使用角度的形式表示量子位的方法不僅減少了存儲(chǔ)空間，而且使量子旋轉(zhuǎn)門(mén)的操作更加容易。

1.2.2? 量子旋轉(zhuǎn)門(mén)

在QGA中，旋轉(zhuǎn)門(mén)用于指導(dǎo)染色體的進(jìn)化過(guò)程，使得當(dāng)前種群中的每個(gè)個(gè)體都向適應(yīng)度最高的個(gè)體靠近。與GA中的二進(jìn)制狀態(tài)相比，旋轉(zhuǎn)門(mén)的使用使得QGA有可能獲得全局最優(yōu)值，這是由于量子位具有多種疊加狀態(tài)。

經(jīng)典的旋轉(zhuǎn)門(mén)操作是通過(guò)與旋轉(zhuǎn)矩陣的乘積實(shí)現(xiàn)的。為降低旋轉(zhuǎn)門(mén)操作的計(jì)算復(fù)雜性，提出了一種基于式（5）的改進(jìn)的量子旋轉(zhuǎn)門(mén)。它通過(guò)加減角度操作修改量子位角度θ。量子位的更新規(guī)則如下：

其中，θ和θ′分別表示更新前和更新后的量子位角度；θop表示最優(yōu)個(gè)體的量子位角度；δ是一個(gè)任意小的角度，稱(chēng)為旋轉(zhuǎn)角；sign （Δθ）是一個(gè)符號(hào)函數(shù)。其他個(gè)體的量子位角度在每次進(jìn)化時(shí)朝著最優(yōu)個(gè)體的量子位角度旋轉(zhuǎn)。δ的大小對(duì)算法收斂速度有顯著影響。δ過(guò)大會(huì)導(dǎo)致早熟，而δ過(guò)小又會(huì)導(dǎo)致算法收斂太慢。通常將δ的值設(shè)置在0.001π～0.5π之間。

通過(guò)旋轉(zhuǎn)門(mén)更新之后的量子位角度可能變?yōu)?或π/2，此時(shí)狀態(tài)? 或? 的概率輻接近1。這種量子位收縮不是我們期望的，因?yàn)槠鋵?dǎo)致QGA的個(gè)體變?yōu)榇_定態(tài)，即喪失了種群多樣性。為了防止這種情況的發(fā)生，提出式（7）所示的改進(jìn)方法：

其中，ε是一個(gè)任意小的角度。

2? 量子遺傳算法用于ECOC

2.1? 量子位編碼表示

在遺傳算法與ECOC結(jié)合的GA-ECOC算法，一個(gè)ECOC矩陣被視為遺傳算法的個(gè)體。而在所提的QECOC中，個(gè)體是使用量子位編碼表示的，因此首先需要將ECOC編碼矩陣轉(zhuǎn)換為使用量子位編碼表示的矩陣。

傳統(tǒng)的二元ECOC編碼矩陣由2種符號(hào)組成，編碼矩陣中的‘1和‘0代表了生成二類(lèi)分類(lèi)器時(shí)每一個(gè)類(lèi)的確定的狀態(tài)。在使用QGA算法時(shí)，要使用量子位編碼代替確定的二進(jìn)制編碼，從而使每一個(gè)類(lèi)的狀態(tài)變得不確定。根據(jù)第1章對(duì)量子位編碼的描述，我們選擇使用量子角度表示ECOC編碼矩陣中的每一個(gè)元素。根據(jù)多分類(lèi)問(wèn)題的類(lèi)別數(shù)N和生成的分類(lèi)器數(shù)量l，生成一個(gè)大小為N×l的量子位編碼矩陣，矩陣中的每一個(gè)元素為[0， π/2]范圍內(nèi)的一個(gè)角度。

2.2? 量子位觀測(cè)

觀測(cè)操作將不確定的量子位編碼收縮為確定的二進(jìn)制值，該二進(jìn)制值被稱(chēng)為量子位的觀測(cè)值。圖1展示了上述量子位編碼矩陣的一次觀測(cè)結(jié)果：

假設(shè)一個(gè)大小為N×l的量子位編碼矩陣，其中的每一個(gè)元素用對(duì)應(yīng)的角度表示。對(duì)量子位編碼矩陣中的每一個(gè)元素，使αi， j =cosθi， j。首先計(jì)算所有元素的α值，然后生成[0， 1]范圍內(nèi)的隨機(jī)數(shù)x。若αi， j ＞x，則該位置為1；否則置為0。觀測(cè)操作完成，量子位矩陣將收縮為一個(gè)確定的二元編碼矩陣。

對(duì)觀測(cè)得到的二進(jìn)制編碼矩陣進(jìn)行個(gè)體性能的評(píng)估，并進(jìn)行后續(xù)的進(jìn)化操作。為了確保編碼矩陣的合理性，我們提出了以下對(duì)觀測(cè)操作的改進(jìn)方法：首先對(duì)矩陣中的每一列元素的α值進(jìn)行排序，使α最大的位置為1，α最小的位置為0，其他位置的元素的觀測(cè)結(jié)果不變。其次對(duì)于出現(xiàn)元素值全為0的行，生成一個(gè)[1，l]之間的整型隨機(jī)數(shù)pos，將pos位置的編碼置為1。

2.3? 適應(yīng)度

在QGA中，需要對(duì)每一個(gè)個(gè)體進(jìn)行評(píng)估以確定該個(gè)體的性能。本文使用所有類(lèi)的平均分類(lèi)準(zhǔn)確率作為個(gè)體的適應(yīng)度。對(duì)于數(shù)據(jù)集中的第i類(lèi)，該類(lèi)的樣本數(shù)量為NCi，正確分類(lèi)的樣本數(shù)量為T(mén)i，平均分類(lèi)準(zhǔn)確率由式（8）給出：

2.4? 交叉和變異

通常情況下，QGA的進(jìn)化過(guò)程是通過(guò)旋轉(zhuǎn)門(mén)實(shí)現(xiàn)的。然而，量子旋轉(zhuǎn)門(mén)引導(dǎo)所有個(gè)體向著當(dāng)前最優(yōu)個(gè)體的方向進(jìn)化，導(dǎo)致在進(jìn)行旋轉(zhuǎn)門(mén)操作之后，不同個(gè)體之間的適應(yīng)度差異變小，因而種群的多樣性傾向于降低，最終導(dǎo)致算法不能收斂到最優(yōu)解。為了擴(kuò)展種群的多樣性，引入遺傳算法中的交叉和變異算子。

交叉算子隨機(jī)選擇種群中的兩個(gè)個(gè)體執(zhí)行列交叉操作，產(chǎn)生與雙親個(gè)體完全不同的新個(gè)體。首先隨機(jī)選擇兩個(gè)個(gè)體作為父本，并生成一個(gè)整型隨機(jī)數(shù)作為交叉點(diǎn)。每個(gè)父本在交叉點(diǎn)的位置分為兩個(gè)部分，雙親個(gè)體在交叉點(diǎn)之后的部分互換，從而產(chǎn)生新的個(gè)體。交叉操作的示意圖如圖2所示。

新生成的個(gè)體放入后代種群池中，不參與后續(xù)的進(jìn)化過(guò)程。

在本文使用的QGA中，我們也引入了變異算子。變異操作旨在改變量子位的疊加狀態(tài)。若一個(gè)量子位在突變之前趨向于收縮為狀態(tài)? ，那么在變異之后應(yīng)該趨向于收縮為狀態(tài)? 。突變操作描述為：

其中， 為變異之前的量子角度； 為變異之后的量子角度。變異之后，量子位向狀態(tài)? 和狀態(tài)? 的收縮概率轉(zhuǎn)變。

本文使用了兩種不同的變異算子：1）隨機(jī)改變量子位編碼矩陣中的某一個(gè)元素，如圖3（a）所示；2）改變量子位編碼矩陣中的某一列的值，如圖3（b）所示：

3? 實(shí)驗(yàn)分析

3.1? 數(shù)據(jù)集

本次實(shí)驗(yàn)使用12個(gè)UCI數(shù)據(jù)集[11]，詳細(xì)信息列在表1中。所有的數(shù)據(jù)集都被分為訓(xùn)練集和測(cè)試集，其比例為9：1。其中訓(xùn)練集用于訓(xùn)練基分類(lèi)器。測(cè)試集作為未知數(shù)據(jù)用于評(píng)估算法的性能，在測(cè)試集上獲取的分類(lèi)準(zhǔn)確率用于算法的性能比較。

3個(gè)ECOC算法被選擇用以與所提算法進(jìn)行性能對(duì)比，它們分別是：隨機(jī)編碼[2]（Random），GECOC[8]和Impro-GECOC[9]。

3.2? 實(shí)驗(yàn)設(shè)置

在我們的QGA框架中，種群的尺寸為20個(gè)，最大迭代次數(shù)為100。變異率設(shè)置為0.25。在實(shí)驗(yàn)中，將分類(lèi)準(zhǔn)確率作為算法性能的評(píng)估標(biāo)準(zhǔn)。表2～表4分別列出了在測(cè)試集上使用DT，KNN和NB三種分類(lèi)器得到的不同算法的分類(lèi)準(zhǔn)確率對(duì)比結(jié)果，其中最優(yōu)的結(jié)果用黑體標(biāo)出。

由表2～表4分類(lèi)準(zhǔn)確率結(jié)果對(duì)比可知，QECOC算法在大部分?jǐn)?shù)據(jù)集上取得最好的分類(lèi)準(zhǔn)確率，證明了算法的有效性。

4? 結(jié)? 論

本文提出了一種新的基于量子遺傳算法的ECOC算法用于處理多分類(lèi)數(shù)據(jù)集。該算法將一個(gè)ECOC矩陣進(jìn)行量子位編碼后作為量子遺傳算算法的個(gè)體，使用量子旋轉(zhuǎn)門(mén)、交叉、變異等遺傳算子進(jìn)行演化以生成最優(yōu)的編碼矩陣。在多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果證明了該算法的有效性。

參考文獻(xiàn)：

[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.

作者簡(jiǎn)介：周大鵬（1997—），男，漢族，河南南陽(yáng)人，碩士研究生在讀，研究方向：機(jī)器學(xué)習(xí)。