基于MOABC算法的分類器研究和設(shè)計(jì)

張謙 孟月霞 劉聰

摘 要：在智能算法優(yōu)化分類器參數(shù)時(shí)，經(jīng)常采用加權(quán)方式將分類率和特征數(shù)目作為單目標(biāo)優(yōu)化。為提高分類性能和解決權(quán)值設(shè)定問題，本文提出一種基于MOABC算法的分類器設(shè)計(jì)，將分類率和特征數(shù)目作為兩個(gè)優(yōu)化目標(biāo)，并通過相關(guān)數(shù)據(jù)進(jìn)行驗(yàn)證。結(jié)果表明，通過多目標(biāo)優(yōu)化可以得出多組最優(yōu)解，供決策者選擇，并且分類效果明顯優(yōu)于作為單目標(biāo)處理時(shí)所得的結(jié)果。

關(guān)鍵詞：MOABC算法;分類率;特征數(shù)目

中圖分類號(hào)：TP18;TP311.13文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1003-5168（2020）01-0020-03

Abstract： When the intelligent algorithm optimizes the classifier parameters， the classification rate and the number of features are often used as single target optimization. To improve the classification performance and solve the weight setting problem， this paper proposed a MOABC algorithm. The classifier design took the classification rate and the number of features as two optimization targets， and verified by relevant data. The results show that multiple optimal solutions can be obtained by multi-objective optimization， which can be selected by decision makers， and the classification effect is obviously better than that obtained by single objective processing.

Keywords： MOABC algorithm;classification rate;characteristic number

1 研究背景

隨著社會(huì)的不斷發(fā)展，通信技術(shù)、信息技術(shù)和計(jì)算機(jī)技術(shù)不斷強(qiáng)大，出現(xiàn)了大量數(shù)據(jù)。那么，如何從這些眾多的數(shù)據(jù)中提取出有價(jià)值的數(shù)據(jù)成為研究者的研究?jī)?nèi)容，數(shù)據(jù)挖掘[1]由此產(chǎn)生。數(shù)據(jù)挖掘的基本理念是：決策者通過從大量數(shù)據(jù)中提取出的有用信息作為處理問題的判斷依據(jù)。

數(shù)據(jù)分類是數(shù)據(jù)挖掘中的一個(gè)重要分支，分類算法直接影響分類結(jié)果。要想得到較好的分類結(jié)果，需要構(gòu)建良好的分類模型。隨著智能算法的不斷發(fā)展，基于智能算法的分類器研究越來越多。在數(shù)據(jù)分類中，為了提高分類效果，主要對(duì)分類器參數(shù)進(jìn)行優(yōu)化;而對(duì)于高維數(shù)據(jù)，為了降低分類難度，通常需要數(shù)據(jù)中主要特征數(shù)。

在以往的研究中，研究者經(jīng)常會(huì)將優(yōu)化特征子集和分類器參數(shù)分開進(jìn)行，也有少量研究是同步優(yōu)化特征子集和分類器參數(shù)的，并取得了一定的效果[2]。在同步優(yōu)化參數(shù)和特征子集時(shí)，智能算法適應(yīng)度函數(shù)選用分類率和特征個(gè)數(shù)作為最優(yōu)解的選擇依據(jù)，那么要如何確定兩個(gè)參數(shù)的權(quán)重呢？大部分學(xué)者是通過實(shí)驗(yàn)法主觀設(shè)定，但這種方式會(huì)影響結(jié)果。為解決參數(shù)權(quán)重的設(shè)定問題并提高分類精度，本文將采用多目標(biāo)人工蜂群算法對(duì)分類器進(jìn)行設(shè)計(jì)，將分類率和選擇的特征數(shù)目作為兩個(gè)目標(biāo)進(jìn)行處理。

2 多目標(biāo)優(yōu)化問題

在實(shí)際應(yīng)用中，要想得到一個(gè)優(yōu)化問題的最終解，其實(shí)包含多個(gè)目標(biāo)，而這些目標(biāo)函數(shù)需要同時(shí)進(jìn)行優(yōu)化處理，并且選取的目標(biāo)之間通常是相互矛盾的，這就是多目標(biāo)優(yōu)化問題[3]。

當(dāng)這兩個(gè)條件滿足時(shí)，對(duì)應(yīng)的[x]是可行解，全部可行解的集合稱為可行解集（可行域）。

多目標(biāo)問題的解決方式[3]有兩種：一種是通過設(shè)定權(quán)值將多目標(biāo)問題轉(zhuǎn)換成單目標(biāo)問題，在分類算法中，通常將智能算法優(yōu)化后參數(shù)的分類率和特征個(gè)數(shù)用加權(quán)方式合為單目標(biāo)問題，但是，當(dāng)權(quán)值發(fā)生變化時(shí)，就需要重新運(yùn)算，并且權(quán)值大多是無法預(yù)判的;另一種方法是采用一組互不支配的解集，然后根據(jù)實(shí)際情況最終做出決策。本文主要采用多目標(biāo)人工蜂群算法（Multi-objective Artificial Bee Colony，MOABC）將分類率和特征個(gè)數(shù)作為兩個(gè)目標(biāo)處理，最終應(yīng)用到具體數(shù)據(jù)分類中得到一組最優(yōu)解。

3 MOABC算法

在MOABC算法中，主要明確以下兩點(diǎn)。①對(duì)解的評(píng)價(jià)：由于多目標(biāo)優(yōu)化得到的是一組解集，因此根據(jù)Pareto支配關(guān)系[4]保留最優(yōu)解;②最優(yōu)解的保存和更新方式：將求得的最優(yōu)解保存起來，每次循環(huán)都對(duì)已存在的解進(jìn)行更新，從而去除不好的解，保留優(yōu)解。同時(shí)，保存解集的內(nèi)存要限制大小，從而減少計(jì)算量，并通過擁擠距離控制解的數(shù)量。

MOABC算法的步驟如下。

第一步，初始化。明確待優(yōu)化的參數(shù)，并設(shè)置參數(shù)的上下限，根據(jù)公式（2）完成種群初始化，并依據(jù)Pareto支配原則，找到初始優(yōu)解保存到解集空間中。

第四步，尋找新解。當(dāng)搜尋次數(shù)達(dá)到[Limit]次并且結(jié)果無變化時(shí)，就選擇拋棄，并根據(jù)公式（2）生成新的蜜源。

第五步，外部解集更新。當(dāng)新解被舊解支配時(shí)，則不會(huì)加入外部解集;當(dāng)新解支配舊解時(shí)，新解則會(huì)替換掉舊解;新解與舊解互不支配時(shí)，新解直接歸入解集。外部檔案的大小有限制，因此，需要通過擁擠距離對(duì)外部檔案中的解進(jìn)行排序，進(jìn)而保存最優(yōu)解，并確保外部檔案的大小。

在求第[i]個(gè)個(gè)體的擁擠距離時(shí)，應(yīng)將每個(gè)目標(biāo)函數(shù)值從小到大排列，并將兩端設(shè)為無窮大，而中間個(gè)體的距離按照公式（5）計(jì)算，最后，各個(gè)目標(biāo)函數(shù)的擁擠距離之和即為總體擁擠距離。

4 MOABC分類算法的實(shí)現(xiàn)

本文采用SVM（支持向量機(jī)）分類算法。為了提高分類性能，優(yōu)化的參數(shù)主要是懲罰因子[C]、核函數(shù)參數(shù)[γ]和特征數(shù)目。其中，特征數(shù)目按照實(shí)際操作時(shí)數(shù)據(jù)庫的數(shù)目來定。由于本文是將特征選擇和分類率作為兩個(gè)目標(biāo)來處理，因此，適應(yīng)度函數(shù)包含兩個(gè)，分別是[fitness1=svm_accuracy]和[fitness2=feature number]。具體運(yùn)用MOABC算法優(yōu)化分類率和特征數(shù)目的流程如圖1所示。首先將輸入的數(shù)據(jù)進(jìn)行[0，1]歸一化處理，方便之后的數(shù)據(jù)分類操作;然后將數(shù)據(jù)分為測(cè)試集和訓(xùn)練集，為了保證分類模型的準(zhǔn)確性，通常測(cè)試集的數(shù)目居多，并且要包含每一類數(shù)據(jù)，接著運(yùn)用訓(xùn)練集通過MOABC算法對(duì)模型進(jìn)行尋優(yōu)，通過迭代找到較優(yōu)的參數(shù)和特征數(shù)的集合，然后用于測(cè)試集進(jìn)行測(cè)試。MOABC算法具體尋優(yōu)操作如圖2所示。

5 仿真結(jié)果與結(jié)論

在MATLAB界面下編寫M文件，并結(jié)合LIBSVM工具箱將UCI數(shù)據(jù)庫的數(shù)據(jù)進(jìn)行分類測(cè)試。在測(cè)試時(shí)，將數(shù)據(jù)分為訓(xùn)練集和測(cè)試集，訓(xùn)練集用于優(yōu)化特征子集和參數(shù)，而測(cè)試集用于驗(yàn)證。本文選用兩組數(shù)據(jù)進(jìn)行驗(yàn)證。圖3是多目標(biāo)優(yōu)化算法得出的一組解集，表1是兩組數(shù)據(jù)對(duì)應(yīng)的分類結(jié)果集，表2是將分類率和特征數(shù)目作為單目標(biāo)處理時(shí)所得到的結(jié)果。

由分類結(jié)果可以看出，由多目標(biāo)人工蜂群算法構(gòu)成的分類器，不僅可以避免在單目標(biāo)處理時(shí)設(shè)置權(quán)值的問題，同時(shí)能得到較優(yōu)的分類效果，并且從表1可以看出，多目標(biāo)分類器設(shè)計(jì)可得到多組最優(yōu)解，決策者可根據(jù)實(shí)際需要選擇相應(yīng)的結(jié)果。通過與表2對(duì)比可以看出，使用多目標(biāo)優(yōu)化算法使訓(xùn)練集和測(cè)試集的結(jié)果相差不大，特征數(shù)目也比單目標(biāo)處理時(shí)得到的少。

參考文獻(xiàn)：

[1]Jiawei Han，Micheline Kamber，JianPei，et al.數(shù)據(jù)挖掘：概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2012.

[2]Zhang Y，Gong D，Hu Y，et al. Feature selection algorithm based on bare bones particle swarm optimization[J]. Neurocomputing，2015（148）：150-157.

[3]張長(zhǎng)勝.多目標(biāo)人工蜂群算法及遺傳算法的研究與應(yīng)用[M].沈陽：東北大學(xué)出版社，2013.

[4]胡恒，高鷹.多目標(biāo)人工蜂群算法研究[J].福建電腦，2013（10）：66-69.