基于Relief-PGS優(yōu)化算法的數(shù)據(jù)分類

張菡玫

（武昌職業(yè)學(xué)院，湖北 武漢 430000）

0 引言

近年來，不同領(lǐng)域的專家對(duì)如何提高圖像分類精度進(jìn)行研究，普遍認(rèn)為分類精確率的高低取決于圖像特征的選擇。即需要從輸入的p個(gè)特征中選擇出d（d＜p）個(gè)特征，并將這些特征評(píng)選為最優(yōu)特征［1］，以此來進(jìn)行分類。選擇的特征集通常包含冗余特征，當(dāng)冗余特征過多時(shí)，運(yùn)算復(fù)雜度將加大，從而導(dǎo)致圖像分類精度下降。為解決這一問題，需要對(duì)提取到的紋理特征進(jìn)行篩選，并根據(jù)各個(gè)特征和類別的相關(guān)性對(duì)特征進(jìn)行選擇，從而減少特征數(shù)據(jù)的維度，提高運(yùn)算速率。在篩選特征時(shí)，常用過濾式［2］特征選擇法中的Relief 算法［3］，通過預(yù)處理來刪除所選數(shù)據(jù)中的無關(guān)特征，縮小特征數(shù)據(jù)維度，并利用支持向量機(jī)［4］和粒子群-遺傳優(yōu)化算法［5］對(duì)篩選后的特征數(shù)據(jù)進(jìn)行學(xué)習(xí)，從而提高分類的準(zhǔn)確率。

為此，本研究提出Relief-PGS 優(yōu)化算法，該算法能提高分類的準(zhǔn)確率。先使用Relief 算法對(duì)特征集進(jìn)行初步篩選，再將篩選結(jié)果和SVM 參數(shù)一起編碼到粒子群-遺傳算法中，對(duì)特征子集及SVM 參數(shù)進(jìn)行同步優(yōu)化。

1 原理及方法

1.1 Relief算法

Relief 算法根據(jù)所提供數(shù)據(jù)的特征和類別間的關(guān)聯(lián)，從而賦予特征不同權(quán)重。權(quán)重值越大，表示圖像的能力越強(qiáng)；權(quán)重值越小，表示圖像的能力越弱［6］。Relief 算法的具體實(shí)現(xiàn)步驟如下。①對(duì)樣本所有特征權(quán)重進(jìn)行初始化，將其置0。②隨機(jī)挑選樣本xi，從xi的相同類別樣本中查找最近鄰樣本H，從xi的不同類別樣本中查找最近鄰樣本M。計(jì)算xi與H、xi與M分別在特征上的距離dist(xi,H)、dist(xi,M)。若dist( )xi,H＜dist(xi,M)，則xi不能有效區(qū)分同類別樣本和不同類別樣本，從而減小特征的權(quán)重［7］。反之，則增大特征的權(quán)重。③將上一步重復(fù)循環(huán)m次，最終獲得n個(gè)特征權(quán)重。

1.2 支持向量機(jī)

支持向量機(jī)（Support Vector Machine，SVM）是一種基于最優(yōu)化理論來解決機(jī)器學(xué)習(xí)問題的算法，可分為三類，即線性可分、線性不可分、非線性可分［8］。

SVM算法用分離超平面作為分離訓(xùn)練數(shù)據(jù)的線性函數(shù)，可解決線性分類問題［9］。假設(shè)訓(xùn)練樣本集合為{(xi,yi)|i= 1,2,…,m}，其中，xi∈Rn為訓(xùn)練樣本，yi∈{-1,1}為輸入樣本的類別。通過訓(xùn)練獲得一個(gè)最優(yōu)分類面，見式（1）。

式中：x為樣本；ω為權(quán)向量；b為分類閾值。

根據(jù)最優(yōu)化理論來引入拉格朗日函數(shù)，對(duì)SVM求取判別函數(shù)，見式（2）。

式中：xi、xj為樣本；ai*=(a1*,a2*,…,ai*)為最優(yōu)解，多數(shù)樣本ai*為零，ai*不為零的樣本決定最優(yōu)分類面；b*為分類閾值，可由任意ai*求得。

1.3 粒子群-遺傳算法

遺傳算法（Genetic Algorithm，GA）是根據(jù)生物界優(yōu)勝劣汰進(jìn)化準(zhǔn)則衍生出的隨機(jī)優(yōu)化搜索算法［10］。GA 在經(jīng)過有限次迭代后，得到問題的近似最優(yōu)解，包括三個(gè)基本操作，即選擇、交叉和變異。

粒子群算法（Particle Swarm Optimization，PSO）是一種基于群體的隨機(jī)優(yōu)化算法［11］，PSO 的核心思想是在一個(gè)S維的搜索空間中找到m個(gè)粒子組成一個(gè)群體，S維的向量xi=(xi1,xi2,…,xis),i=1,2,…,m，利用xi對(duì)解的最優(yōu)結(jié)果進(jìn)行判斷。

對(duì)參數(shù)優(yōu)化問題，GA 有較好的全局搜索能力和種群多樣性，但要經(jīng)歷選擇、交叉和變異才能得到下代種群，計(jì)算效率較低，收斂速度較慢。PSO 只需將粒子當(dāng)前最優(yōu)位置與飛行歷程中經(jīng)歷的最優(yōu)位置進(jìn)行比較，即可得到最優(yōu)的飛行速度和飛行方向。粒子群-遺傳算法（PSO-GA）是將PSO 和GA 聯(lián)立，利用PSO來代替GA的選擇算子，結(jié)合算法在初期的收斂速度更快，同時(shí)因保留GA 的交叉和變異算子，能提高全局尋優(yōu)的能力［12］。

1.4 Relief-PGS優(yōu)化算法

本研究基于Relief算法、PSO-GA和SVM對(duì)數(shù)據(jù)集特征進(jìn)行選擇和分類，即Relief-PGS 優(yōu)化算法。先利用Relief 算法對(duì)獲取到的數(shù)據(jù)特征集進(jìn)行選擇，然后將選擇出的特征數(shù)據(jù)集和SVM 參數(shù)一起編碼到PSO-GA 的染色體中，通過SVM 來構(gòu)建適應(yīng)度函數(shù)，并對(duì)所選擇的特征數(shù)據(jù)集和SVM 參數(shù)進(jìn)行優(yōu)化，從而實(shí)現(xiàn)用較少的特征數(shù)據(jù)集和較短的優(yōu)化時(shí)間來獲得較高的識(shí)別精度，具體流程如圖1所示。

圖1 Relief-PGS優(yōu)化算法流程

Relief-PGS 優(yōu)化算法的具體步驟如下。①使用Relief 算法對(duì)圖像進(jìn)行一次特征篩選，得到特征矩陣。②采用PSO-GA 對(duì)參數(shù)進(jìn)行初始化操作，種群大小為30，迭代次數(shù)為50，算法的終止條件為達(dá)到迭代次數(shù)或連續(xù)十代的適應(yīng)度值不變。③生成初代種群。由于SVM 的懲罰系數(shù)C和核參數(shù)σ采用的是實(shí)數(shù)編碼，而對(duì)特征的二次篩選是通過0、1 進(jìn)行的，0 表示沒有選擇該特征，1 表示選擇該特征，采用二進(jìn)制編碼。④將個(gè)體的后N位帶入樣本中，并對(duì)特征進(jìn)行二次篩選。⑤將個(gè)體的前兩位帶入SVM 模型中，結(jié)合二次篩選的訓(xùn)練樣本，確定SVM 分類模型。⑥將二次篩選出的測(cè)試樣本放入到確定的SVM中，從而獲取分類結(jié)果。⑦計(jì)算初代種群的適應(yīng)度值。⑧將初代種群的適應(yīng)度值輸入到PSO 算法中，更新個(gè)體的速度和位置。⑨將經(jīng)過PSO算法更新的種群輸入到GA 中，經(jīng)過交叉算子和變異算子，得到新種群。⑩返回步驟④，計(jì)算新種群的適應(yīng)度值。?判斷是否滿足判定條件，若滿足，則輸出SVM 參數(shù)和特征數(shù)；若不滿足，則繼續(xù)對(duì)種群進(jìn)行處理，直至滿足判定條件為止，從而得到最終結(jié)果。

2 試驗(yàn)過程

為了驗(yàn)證Relief-PGS 算法的有效性，應(yīng)將特征子集的個(gè)數(shù)和SVM參數(shù)一起編碼到PSO-GA染色體中，在對(duì)SVM 參數(shù)進(jìn)行優(yōu)化的同時(shí)，對(duì)所有特征子集的個(gè)數(shù)進(jìn)行同步優(yōu)化。試驗(yàn)時(shí)需要統(tǒng)一對(duì)數(shù)據(jù)和參數(shù)進(jìn)行處理。

2.1 數(shù)據(jù)預(yù)處理

為提高SVM 分類的準(zhǔn)確率，對(duì)需要分類的數(shù)據(jù)樣本進(jìn)行歸一化處理，將其分為訓(xùn)練樣本和測(cè)試樣本，進(jìn)行后續(xù)的分類處理。

2.2 參數(shù)選擇方法

對(duì)PSO-GA 算法的核參數(shù)進(jìn)行優(yōu)化，設(shè)置算法的迭代次數(shù)為50、種群規(guī)模為30、個(gè)體長(zhǎng)度為2，通過適應(yīng)度值計(jì)算得到GA 中交叉和變異的概率，PSO中的ω是基于適應(yīng)度值自適應(yīng)計(jì)算出的。

統(tǒng)一設(shè)置適應(yīng)度函數(shù)，見式（3）。

式中：we1 為訓(xùn)練樣本識(shí)別結(jié)果的權(quán)重；we2 為測(cè)試樣本識(shí)別結(jié)果的權(quán)重（其中，we1+we2=1。樣本不平衡可能導(dǎo)致模型的預(yù)測(cè)能力下降。經(jīng)多次試驗(yàn)，通過調(diào)節(jié)樣本權(quán)重，將we1 分別設(shè)為0.10、0.15、0.20、0.30，當(dāng)we1 為0.15 時(shí)，可得到最優(yōu)結(jié)果）；m1為訓(xùn)練樣本的總數(shù)；m2 為測(cè)試樣本的總數(shù)；nsv1 為訓(xùn)練樣本分類正確的結(jié)果；nsv2 為測(cè)試樣本分類正確的結(jié)果。fitness越小，表明綜合分類的精確度越高。

2.3 模型建立

從每組訓(xùn)練樣本中選擇優(yōu)化后的核參數(shù)對(duì)樣本進(jìn)行新一輪訓(xùn)練，從而獲得SVM 分類模型，再通過測(cè)試樣本來測(cè)試模型的分類精度。

Relief-PGS 優(yōu)化算法主要是為了解決兩個(gè)問題，即優(yōu)化后的輸入特征子集選擇、優(yōu)化后的核函數(shù)參數(shù)選擇。使用Relief-PGS 優(yōu)化算法將優(yōu)化后的征子集個(gè)數(shù)和SVM 參數(shù)一起編碼到PSO-GA 染色體中，在對(duì)特征子集進(jìn)行優(yōu)化的同時(shí)，對(duì)SVM 參數(shù)同步進(jìn)行優(yōu)化，最后得到優(yōu)化后的分類結(jié)果。

選取UCI數(shù)據(jù)庫中5種數(shù)據(jù)集進(jìn)行試驗(yàn)，所選取數(shù)據(jù)集的基本信息見表1。

表1 試驗(yàn)數(shù)據(jù)集的基本信息

利用Relief 算法對(duì)獲取到的特征數(shù)據(jù)進(jìn)行初步篩選，選擇與目標(biāo)類別關(guān)聯(lián)較大的特征，使用PSOGA算法、SVM算法分別對(duì)篩選出的特征數(shù)據(jù)和SVM參數(shù)進(jìn)行優(yōu)化，從而獲得優(yōu)化后的特征子集。優(yōu)化的特征子集個(gè)數(shù)見表2。

表2 優(yōu)化特征子集個(gè)數(shù)

利用SVM 分類器對(duì)選取的多個(gè)優(yōu)化特征進(jìn)行分類，并將RBF作為SVM的核函數(shù)進(jìn)行分類。

3 試驗(yàn)結(jié)果分析

使用Relief-PGS 優(yōu)化算法得到分類結(jié)果，并將分類結(jié)果分別與默認(rèn)核參數(shù)的SVM、使用PSO-GA算法優(yōu)化參數(shù)的SVM（PGS）、使用Relief算法優(yōu)化特征的SVM（Relief-SVM）這三種不同算法的優(yōu)化結(jié)果進(jìn)行對(duì)比，并評(píng)價(jià)特征選擇方法的優(yōu)劣，試驗(yàn)結(jié)果見表3。

表3 數(shù)據(jù)集分類結(jié)果對(duì)比

由表3 可知，Relief-PGS 優(yōu)化算法的分類準(zhǔn)確率最高。通過對(duì)這四種算法的分類結(jié)果進(jìn)行對(duì)比可知：①對(duì)于任意特征數(shù)據(jù)，使用PGS 優(yōu)化算法進(jìn)行參數(shù)尋優(yōu)得到的分類準(zhǔn)確率比使用默認(rèn)參數(shù)的SVM 要有所提高，分類準(zhǔn)確率平均提高了12%左右?？勺C明對(duì)傳統(tǒng)的SVM 中的參數(shù)進(jìn)行尋優(yōu)，能找到優(yōu)化后的控制參數(shù)，從而提高SVM 分類的準(zhǔn)確率；②使用Relief-SVM 優(yōu)化算法對(duì)輸入的特征向量進(jìn)行篩選分類，分類準(zhǔn)確率比默認(rèn)參數(shù)的SVM 平均提高了13%左右，從而證明了Relief-SVM 對(duì)輸入的特征數(shù)據(jù)集進(jìn)行篩選和優(yōu)化，得到優(yōu)化后的特征子集，可去除一些特征不明顯的影響因素，能減少不重要因素對(duì)分類結(jié)果造成的影響，從而提高分類的準(zhǔn)確率；③使用Relief-PGS 優(yōu)化算法得到的分類準(zhǔn)確率最高，分類的準(zhǔn)確率基本在85%左右，從而證明了在對(duì)特征子集和SVM 參數(shù)同步進(jìn)行優(yōu)化時(shí)，去除不重要的特征，并對(duì)參數(shù)進(jìn)行優(yōu)化，能得到更好的分類效果。

4 結(jié)語

本研究提出的Relief-PGS 優(yōu)化算法可同時(shí)優(yōu)化特征子集和SVM 參數(shù)，通過優(yōu)化特征子集和SVM 參數(shù)來提高分類的準(zhǔn)確率。與傳統(tǒng)的SVM、PGS 算法和Relief-SVM 算法相比，Relief-PGS 算法對(duì)圖像分類的準(zhǔn)確率分別提高了22.53%、6.05%和11.16%，從而證明了圖像分類識(shí)別的準(zhǔn)確性。研究結(jié)果證明，Relief-PGS 算法能利用最少特征來獲得最高分類精度，能有效提高圖像特征選擇分類的準(zhǔn)確率。