一種新的基于量子遺傳算法的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—），男，漢族，河南南陽人，碩士研究生在讀，研究方向：機器學習。