基于Relief-PGS優化算法的數據分類

張菡玫

（武昌職業學院，湖北 武漢 430000）

0 引言

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

為此，本研究提出Relief-PGS 優化算法，該算法能提高分類的準確率。先使用Relief 算法對特征集進行初步篩選，再將篩選結果和SVM 參數一起編碼到粒子群-遺傳算法中，對特征子集及SVM 參數進行同步優化。

1 原理及方法

1.1 Relief算法

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

1.2 支持向量機

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

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

式中：x為樣本；ω為權向量；b為分類閾值。

根據最優化理論來引入拉格朗日函數，對SVM求取判別函數，見式（2）。

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

1.3 粒子群-遺傳算法

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

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

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

1.4 Relief-PGS優化算法

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

圖1 Relief-PGS優化算法流程

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

2 試驗過程

為了驗證Relief-PGS 算法的有效性，應將特征子集的個數和SVM參數一起編碼到PSO-GA染色體中，在對SVM 參數進行優化的同時，對所有特征子集的個數進行同步優化。試驗時需要統一對數據和參數進行處理。

2.1 數據預處理

為提高SVM 分類的準確率，對需要分類的數據樣本進行歸一化處理，將其分為訓練樣本和測試樣本，進行后續的分類處理。

2.2 參數選擇方法

對PSO-GA 算法的核參數進行優化，設置算法的迭代次數為50、種群規模為30、個體長度為2，通過適應度值計算得到GA 中交叉和變異的概率，PSO中的ω是基于適應度值自適應計算出的。

統一設置適應度函數，見式（3）。

式中：we1 為訓練樣本識別結果的權重；we2 為測試樣本識別結果的權重（其中，we1+we2=1。樣本不平衡可能導致模型的預測能力下降。經多次試驗，通過調節樣本權重，將we1 分別設為0.10、0.15、0.20、0.30，當we1 為0.15 時，可得到最優結果）；m1為訓練樣本的總數；m2 為測試樣本的總數；nsv1 為訓練樣本分類正確的結果；nsv2 為測試樣本分類正確的結果。fitness越小，表明綜合分類的精確度越高。

2.3 模型建立

從每組訓練樣本中選擇優化后的核參數對樣本進行新一輪訓練，從而獲得SVM 分類模型，再通過測試樣本來測試模型的分類精度。

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

選取UCI數據庫中5種數據集進行試驗，所選取數據集的基本信息見表1。

表1 試驗數據集的基本信息

利用Relief 算法對獲取到的特征數據進行初步篩選，選擇與目標類別關聯較大的特征，使用PSOGA算法、SVM算法分別對篩選出的特征數據和SVM參數進行優化，從而獲得優化后的特征子集。優化的特征子集個數見表2。

表2 優化特征子集個數

利用SVM 分類器對選取的多個優化特征進行分類，并將RBF作為SVM的核函數進行分類。

3 試驗結果分析

使用Relief-PGS 優化算法得到分類結果，并將分類結果分別與默認核參數的SVM、使用PSO-GA算法優化參數的SVM（PGS）、使用Relief算法優化特征的SVM（Relief-SVM）這三種不同算法的優化結果進行對比，并評價特征選擇方法的優劣，試驗結果見表3。

表3 數據集分類結果對比

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

4 結語

本研究提出的Relief-PGS 優化算法可同時優化特征子集和SVM 參數，通過優化特征子集和SVM 參數來提高分類的準確率。與傳統的SVM、PGS 算法和Relief-SVM 算法相比，Relief-PGS 算法對圖像分類的準確率分別提高了22.53%、6.05%和11.16%，從而證明了圖像分類識別的準確性。研究結果證明，Relief-PGS 算法能利用最少特征來獲得最高分類精度，能有效提高圖像特征選擇分類的準確率。