基于PSO的支持向量機改進算法研究

邱寧佳，賀金彪，趙建平，李巖芳

（長春理工大學 計算機科學技術學院，長春 130022）

支持向量機算法是通過尋求結構最小化來實現(xiàn)風險最小化的機器學習算法，以期待在有限條件的情況下得到最優(yōu)結構。非線性和維數(shù)災難問題以及局部極小問題等問題都可以通過支持向量機在一定程度上得到解決。此外，支持向量機分類的精度與其本身的參數(shù)和多分類模型的選擇有很大的關系。為了解決以上問題，相關學者提出了不同的方法進行嘗試，以提高支持向量機的分類精確度。

崔建明等針對文本分類器的性能容易受到核函數(shù)和參數(shù)的影響問題，將優(yōu)化的粒子群算法引入SVM分類算法中，利用粒子群優(yōu)化算法尋找最佳參數(shù)并用SVM算法進行分類，實驗表明優(yōu)化后的SVM分類器的準確性更高［1］；單黎黎等引入動量因子來緩解粒子群算法極易陷入局部極小值的問題，然后采用改進的粒子群算法實現(xiàn)對由徑向基函數(shù)和多項式函數(shù)組合而成的混合核函數(shù)的參數(shù)尋優(yōu)，實驗表明基于粒子群改進的混合函數(shù)支持向量機分類器具有較好的分類精度［2］；Sun等針對數(shù)據(jù)挖掘中的大尺度和多維度導致的時間浪費和精度降低問題，提出了一種基于多準則排序和C-SVM的特征選擇方法m CRC，通過互信息和類距離計算特征和標簽之間的依賴關系，刪除無關的和完全冗余的屬性［3］；Zhang等為了解決SVM處理大規(guī)模多類樣本時的低學習效率問題，提出了一種基于多聚類的多分類SVM快速學習方法，保證了較高的分類精確率并減少樣本數(shù)量，有效提高學習效率［4］；梁鈺針對SVM分類算法處理數(shù)據(jù)時未考慮語義的相似性度量問題，利用LDA主題模型進行建模和特征選擇確定主題數(shù)和隱主題，在此特征空間下使用SVM分類器進行分類［5］；王道明等利用自變異的PSO聚類算法在每一個決策點自動尋找最優(yōu)或最近分類決策，將數(shù)據(jù)集劃分為兩類，直至葉子節(jié)點位置，最終根據(jù)最優(yōu)決策樹構建SVM多分類結構，實驗表明改進的多分類結構在分類精度和時間上得到明顯改善［6］；朱慶生等重新定義遺傳算法中的適應度函數(shù)，提出了一種基于累積適用度遺傳算法的支持向量機多分類算法，改善基于遺傳算法的支持向量機多分類決策樹算法中存在的全局優(yōu)化缺陷問題，使其分類精確度有所提高［7］；衣治安采用二叉樹結構與多個支持向量機子分類器組合進行Web文本信息分類，提出了一種新的支持向量機的多類分類方法提高了分類精度，體現(xiàn)了將遺傳算法與二叉樹支持向量機結合的優(yōu)越性［8］；王鵬等人提出了一種基于邊分類的SVM模型對分類函數(shù)的參數(shù)進行估計進而對真實網(wǎng)絡進行社區(qū)分類，實驗得到了較高的整體準確度［9］；黃剛等針對SVM算法和樸素貝葉斯算法的缺點，對樸素貝葉斯算法進行分析和改進，提出了SVM-WNB分類算法并驗證改進的算法在準確性方面有明顯提升［10］。王振武等考慮傳統(tǒng)粒子群算法后期震蕩嚴重的缺陷，引入混沌序列來初始化粒子群的位置，并在簡化的粒子群數(shù)學模型上對其改進用于優(yōu)化支持向量機的模型參數(shù)，實驗結果表明具有較高的分類準確率［11］。

上述支持向量機模型均在不同程度上提升了分類的精確度，但這些算法都只是針對核函數(shù)或多分類單方面做了改進，并沒有同時考慮兩種情況，然而本文涉及的是多分類問題，要同時考慮以上兩種情況。因此提出一種改進的PSO-SVM算法來提升多分類性能。

1 文本預處理

在文本分類中，特征選擇方法能從高維的特征空間中選取對分類有效的特征，降低特征的冗余度，提高分類準確度。Li等針對多標簽學習算法性能很大程度取決于輸入特征，提出了一種基于互信息的多標簽學習的粒度特征加權KNN算法以避免標簽組合爆炸問題，有效地提高了其分類性能［12］；陶永才提出了一種基于MapReduce的互信息文本特征選擇機制，利用其能夠處理大規(guī)模數(shù)據(jù)的優(yōu)勢，縮短文本訓練和分類的過程從而提高文本分類的精度［13］；余璇利用互信息能夠表達變量間相關性的特點，使用特征權重改進主題分類算法特征貢獻度進而提高分類的準確率［14］；董露露提出了一種改進的互信息特征選擇方法，引入平均詞頻和絕對值最大因子，提高了文本分類性能［15］；Luo為了解決微博情感分析忽略情感符號和網(wǎng)絡詞的問題，提出了一種擴展語義定向的逐點互信息算法來構造動態(tài)情感語料庫，提高了對語料庫進行分類的效率［16］；Wu提出了一種基于互信息的術語加權樸素貝葉斯文本分類方法，根據(jù)文本互信息的理論部分消除了其屬性獨立性等于其屬性重要性的假設對分類的影響［17］；Nguyen等采用改進粒子群優(yōu)化算法PSOMIE的波濾器特征選擇算法代替?zhèn)鹘y(tǒng)的互信息算法，利用一種新的適應度函數(shù)提高了分類性能同時解決了過度擬合問題［18］；基于上述互信息理論，本文提出一種改進的特征評價函數(shù)，提高文本分類的準確性。

1.1 互信息算法的改進

互信息算法是文本分類常用的特征選擇方法之一，但其在理論以及現(xiàn)實應用中分類精度比較低。傳統(tǒng)的互信息算法按照特征詞和類別一起出現(xiàn)的概率來衡量特征詞與類別的相關性，特征詞t和類別ci的互信息公式如（1）所示：

式中，p(t,)表示在訓練集中類別為且包含特征詞t的文本的概率；p(t)表示在訓練集中包含特征t的文本的概率，p()表示訓練集中屬于類別的文本的概率。

由于計算各個概率時使用的頻數(shù)都是包含特征詞的文本數(shù)量，并沒有考慮到特征詞在各個文本中出現(xiàn)的詞頻因素。當類別C中包含特征詞ti和tj的文本數(shù)目一致，并且兩個特征詞在其他類別中都甚少出現(xiàn)，那么由MI公式計算出的兩個特征詞與類別之間的互信息值基本接近。

然而事實上，當文本中包含的特征詞ti的頻數(shù)遠大于tj時（如特征詞ti在文本出現(xiàn)的平均頻數(shù)為10，而特征詞tj在文本中出現(xiàn)的頻數(shù)為1，那么顯然，特征詞ti更具有代表性，分類能力也越好），利用MI公式計算的互信息值仍相近。因此可以得出特征在某類別各個文本中出現(xiàn)的頻數(shù)是體現(xiàn)特征詞分類能力的重要因素，根據(jù)上述因素引入權重因子、類間和類內(nèi)離散因子三個定義，具體的描述如下。

定義1.設特征集T={t1,t2,…,}tm，訓練集類別集C={c1,c2,…,}cn，記fij為特征詞tj在類別ci出現(xiàn)的總頻數(shù)，F(xiàn)j為特征詞tj在訓練集中出現(xiàn)的總頻數(shù)。特征tj在類別ci中的權重因子，定義如式（2）所示：

一個特征詞的權重因子就是該特征詞在某一類別中出現(xiàn)的頻率。特征的權重因子越大，分類性能就越強。在互信息公式中引入權重因子，削弱互信息中對低詞頻的倚重，增強高詞頻屬性的影響力，提高分類準確性。

定義2.設特征集T={t1,t2,…,}tm，訓練集類別集C={c1,c2,…,}cn，記fij為特征tj在屬于類別ci的文本中出現(xiàn)的總頻數(shù)，為特征詞tj在所有類別文本中出現(xiàn)的平均頻數(shù)。特征tj的類間離散因子定義如式（3）所示：

一個特征詞的類間離散因子能夠量化該特征詞在各個類間的差異分布狀況。類間分布差異越大，特征詞就越具有類別代表性，其分類性能也就越強。將類間離散因子引入互信息公式，就能剔除在各個類中出現(xiàn)頻率相當?shù)?，沒有分類能力的冗余屬性，進而降低計算復雜度，提高分類精確度。

定義3.設特征集T={t1,t2,…,}tm，訓練集類別集C={c1,c2,…,}cn，記Di為類別ci中文檔總數(shù)，fik(tj)為特征詞tj在屬于類別ci的文本dik中出現(xiàn)的次數(shù)，為特征詞tj在類別ci中的文本中出現(xiàn)的平均頻數(shù)。特征tj的類內(nèi)離散因子定義如式（4）所示：

一個特征詞的類內(nèi)離散因子能夠量化該特征在某一個類中的差異分布狀況。

類內(nèi)差異分布越小，特征詞就越有類別代表性，分類性能也就越好。將類內(nèi)離散因子引入互信息方法中，就能夠篩選出在某一類別各個文檔中均勻出現(xiàn)的特征詞，提高分類性能。

1.2 改進的CDMI特征評價函數(shù)

本文著重考慮互信息方法中對低頻詞的影響，可能導致冗余屬性成為特征詞，而有用的條件屬性會漏選的不足之處，引入上文所定義的權重因子、類間離散因子和類內(nèi)離散因子，提出一種改進的CDMI特征選擇算法，其公式如（5）所示：

其中，t為特征詞，訓練集類別集C={c1,c2,…,}cn，α表示為特征t的類間離散因子，βi表示為特征t在ci類內(nèi)的類內(nèi)離散因子，ωi表示為特征t的權重因子，p(t)表示為訓練集中包含特征t的文檔數(shù)和總文檔數(shù)的比值，是訓練文本集中含有特征t的ci類文檔數(shù)與ci類文檔數(shù)的比值。使用CDMI算法進行屬性約簡，獲得彼此相對相互獨立的核心屬性，為支持向量機優(yōu)化模型分類做準備。

2 支持向量機優(yōu)化算法

核函數(shù)的選取是支持向量機理論的核心問題，而核函數(shù)的選取卻常常決定了特征空間的結構。徑向基核函數(shù)只有一個需要調(diào)整的參數(shù)σ，因此只需要適當?shù)恼{(diào)整參數(shù)便可應用于任意分布的樣本。多項式核函數(shù)推廣能力強且隨著階數(shù)的減小而增強。

綜合考慮，徑向基核函數(shù)學習能力強、泛化能力弱的特點和多項式核函數(shù)學習能力弱、泛化能力強的特點，考慮了采用徑向基核Krbf和多項式核Kpoly相結合構造混合核函數(shù)Kmix，如公式（6）所示：

其中，λ∈],1。

本文采用類似于哈夫曼樹的結構構造二叉樹多分類器。對于給的n個權值ω={ω1,ω2,…,ωi,…,ωn}構成n棵二叉樹初始集合T，其中每個二叉樹都只有一個權值為ωi根節(jié)點，其左右子樹均為空，并按權值大小對集合T中的二叉樹按升序排列；在二叉樹集合T中選取權值最小的兩棵樹作為新構造的二叉樹的左右子樹，新的二叉樹根節(jié)點的權值為左右子樹根節(jié)點的權值之和；從二叉樹集合T中刪除選中的兩棵樹，并將新的二叉樹同樣以升序加入集合T中；直至集合T上只有一棵二叉樹。

哈夫曼樹中的每個非葉子節(jié)點相當于決策樹中的每一個SVM分類器，而葉結點就相當于決策樹中的類別。依據(jù)哈夫曼樹構造原理，將用戶類別樣本集兩兩分類，取兩類之間距離最小的兩個用戶類別作為底層的葉節(jié)點，同時將上述兩個類別合成一個新的用戶類別重新與其他類別進行兩兩分類，直至只剩下一個用戶類別為止。

距離函數(shù)是用于計算類別之間的距離值，距離值越小就越說明兩個類別越相近，也越難分離，具體的距離函數(shù)計算公式如（7）所示：

其中，fi,fj分別代表類別i,j中距離最近樣本的分類函數(shù)，分別代表類別中所有樣本分類函數(shù)的平均值。

2.1 PSO優(yōu)化算法

在支持向量機分類器中引入權值的概念，創(chuàng)造了加權向量機模型，由于權值的選取直接影響分類的效果，為了提高分類的準確性引入PSO優(yōu)化算法對初始權值進行全局尋優(yōu)，獲取最優(yōu)權值。

在PSO優(yōu)化算法中依照速度與位置公式來調(diào)整微粒的速度與位置，求得全局最優(yōu)解。由于在PSO優(yōu)化算法中設定了合適的初始權值，其大小只需微調(diào)，因此在迭代尋優(yōu)中速度不宜過大，以免得不到精確解。為避免這種情況發(fā)生，在速度更新中，對速度設定了最低速度和最高速度，保證其收斂性，改善局部最優(yōu)的狀況。其速度公式和位置公式分別如（8）、（9）所示：

式中，ω表示慣性因子，φ1和φ2為學習因子，vis表示第s次更新時微粒i的速度，xis表示第s次更新時微粒i的位置，rand()為隨機函數(shù)。

式中，vis+1為第s+1次更新時微粒i的速度，xis為第s次更新時微粒i的位置。根據(jù)PSO優(yōu)化算法的思想，具體的算法描述如算法1所示：

算法1 PSO優(yōu)化算法輸入：微粒群體的規(guī)模N，迭代次數(shù)max，最高速度vmax，最低速度vmin輸出：最優(yōu)解初始化位置集合x=( )v1,v2,···,vi,···,vN 和 速 度 集 合v=( )v1,v2,···,vi,···,vN for each xi∈x初始位置xi作為局部最優(yōu)解pbesti微粒自適應度計算fitness(xi)end for gbest=min{ }pbesti while max＞0 for i=1 to N更新vi,xi if fitness(xi)＜fitness(pbesti)當前位置xi設為局部最優(yōu)解if fitness(pbesti)＜fitness(gbest)gbest=pbesti end for max=max-1 end while輸出最優(yōu)解gbest

針對支持向量機加權模型中權值的選取問題，本文以特征詞的詞頻比率為初始權值并以此權值作為PSO優(yōu)化算法中的初始位置，迭代尋找全局最優(yōu)解。

2.2 PSO-SVM算法

SVM的分類能力受參數(shù)影響力較大，好的參數(shù)能夠使SVM發(fā)揮較好的分類作用，反之則對分類性有較大影響。故而，尋找合適的參數(shù)對SVM的分類性能起著決定性的作用。由上文分析可知支持向量機的懲罰參數(shù)C、徑向基核函數(shù)σ以及混合函數(shù)中權重λ對SVM的分類性能有影響，因此本文使用粒子群優(yōu)化算法對于混合核函數(shù)的SVM參數(shù)組合(C,σ,λ)進行優(yōu)化，之后結合哈夫曼最優(yōu)二叉樹原理構造支持向量機多分類器，完整的算法結構如圖1所示。

圖1 PSO-SVM算法結構

在特征選擇過程中，針對原有互信息計算中忽略詞頻因素的不足之處，引入權重因子，放大高詞頻的影響；引入類內(nèi)離散因子和類間離散因子篩選出具有類別代表性的特征詞，其具體的算法描述如算法2所示：

算法2特征提取算法輸入：數(shù)據(jù)集，類別集C={ }c1,c2,…,ci,…,cn輸出：特征集t'文本預處理得到初始特征集t={ }t1,t2,…,tj,…，t'=?for eachtj∈t計算 ωij，αj，βij end for for each tj∈t計算CDMI()tj ifCDMI()tj＞ε t'=t'?tj end for輸出特征集t'

在使用PSO優(yōu)化算法進行求解最優(yōu)參數(shù)組合之前，首先設定了參數(shù)的最大以及最小取值，并結合以往實驗經(jīng)驗設定了初始參數(shù)值。然后，就是要設定優(yōu)化時所需要的適應度函數(shù)。由于是多分類，所以在參數(shù)求取時，將正常用戶作為正類，其他用戶都作為負類，進行二分類求解。記準確值為γ，測量值為γi，那么具體的公式可描述如（10）、（11）所示：

那么目標函數(shù)f(x)可表示如公式（12）所示：

適應度函數(shù)確定之后可以利用PSO優(yōu)化算法對參數(shù)組合進行尋優(yōu)求解，其優(yōu)化過程大致流程為首先是初始化粒子群速度和位置并設定核函數(shù)參數(shù)組合(C,σ,λ)的初始參數(shù)值以及計算粒子群的初始適應度，然后通過粒子速度和位置更新求粒子最優(yōu)解pbest和種群最優(yōu)解gbest，最后得到的gbest就是需要的最優(yōu)參數(shù)組合。

在求解出最優(yōu)參數(shù)之后還需要確定多分類模型，具體的算法描述如算法3所示：

算法3 PSO-SVM算法輸入：訓練樣本類別集C={ }c1,c2,…,ci,…,cn，n棵二叉樹集合T={ }t1,t2…,ti,…,tn，類間距離 dij；輸出：多分類器模型哈夫曼樹T for each tn∈T計算dij，end for while n＞1 for each tn∈T計算PSO(tn)best=dij for eachci∈C if PSO(tn)＜best m=i?j，m∈T deli j，end for end for輸出哈夫曼樹T

3 實驗及結果分析

本文針對支持向量機模型的改進主要分為兩個部分。第一部分是對特征選擇方法中的互信息方法進行改進，去除冗余特征詞，降低維度，減少算法計算的復雜度，同時也改善了算法的分類精度，為了驗證改進前后算法的性能，以分類效果作為標準，設計實驗對其進行驗證。第二部分是采用PSO優(yōu)化算法對混合核函數(shù)中的參數(shù)進行優(yōu)化，并以混合核函數(shù)結合哈夫曼最優(yōu)二叉樹優(yōu)化分類器的性能。為了驗證參數(shù)優(yōu)化前后算法的能力，設計實驗將PSO-SVM算法與傳統(tǒng)SVM算法以及其它改進算法的性能進行對比。

實驗采用Reuters-21578中的10個類別新聞組作為數(shù)據(jù)文本集，對算法進行了實驗測評，使用五折交叉驗證法，將樣本集隨機的分割成大小相等但互不相交的5份，對樣本訓練和驗證分別進行5次，計算得出每次分類的召回率與精確率，為了使分類的結果更具科學性，防止實驗的隨機性和偶然性，采取5次實驗結果的平均值作為最終的衡量標準。

3.1 互信息參數(shù)和粒子群參數(shù)的選取

本文稱引入權重因子的MI算法為WMI算法，引入類間離散因子和類內(nèi)離散因子的MI算法為CMI算法，然后將改進的CDMI算法與WMI算法、CMI算法以及MI算法進行實驗對比，確定要篩選的特征詞個數(shù)。下面做的對比主要是在不限定總的單詞個數(shù)的情況下，四種算法能達到的分類結果的最高精確率，以及在相同的單詞個數(shù)下四種算法的精確率和特征詞個數(shù)。

四種算法最高精確率對比結果如表1所示。

表1 算法最高精確率對比

相同單詞總數(shù)情況下，四種算法的精確率和特征詞數(shù)對比如圖2、3所示。

圖2 精確率對比

可以看出，在數(shù)據(jù)集單詞由10000下降到5000時，MI特征選擇算法的分類結果呈現(xiàn)急速下降的趨勢，而MI和CMI算法皆有小幅度的波動，而改進后的CDMI算法一直趨于穩(wěn)定在0.9之上并且CDMI算法的精確率一直優(yōu)于其他算法，這就體現(xiàn)了改進后的CDMI算法的分類性能比較穩(wěn)定且在數(shù)據(jù)記單詞總量變化的狀態(tài)下不會發(fā)生較大的波動。結合圖2和圖3看出，當數(shù)據(jù)集單詞數(shù)目相同情況下改進的CDMI算法所選取的特征詞數(shù)量明顯少于其它算法，而分類精度卻明顯優(yōu)于其它算法，這就說明改進后的CDMI算法可以降低屬性冗余，篩選出具有高分類能力的計算復雜度。因此可以得出，改進的CDMI算法無論在分類精確度還是分類性能上面都明顯優(yōu)于其它算法。

圖3 特征詞數(shù)對比

對于CDMI算法而言，在數(shù)據(jù)集的總單詞數(shù)為7000的時候，分類結果的精確率是最高的，為了更加直觀的說明這一因素，分別對5次實驗得到的精確率平均值進行了描述，如圖4所示。

圖4 CDMI算法準確率對比

對于CDMI算法，在數(shù)據(jù)集的總單詞數(shù)變化的過程中，特征詞的數(shù)量變化如表2所示。

由表2可知，在數(shù)據(jù)集的單詞總數(shù)為7000的時候，特征詞的個數(shù)為140，因此將特征詞的個數(shù)設置為140。將PSO-SVM算法中粒子的規(guī)模設為n=140，粒子群其它參數(shù)的選取分別為φ1=2.05，φ2=2.05，ω=0.729，rand()為（0，1）區(qū)間上均勻分布的隨機數(shù)，最大迭代次數(shù)為500。

3.2 PSO-SVM算法驗證

通過結合以往實驗經(jīng)驗，基于混合核函數(shù)的PSO-SVM算法中，設置PSO參數(shù)φ1=2.05，φ2=2.05，設計實驗驗證，在不同迭代次數(shù)下，參數(shù)組合的取值以及取得的分類精確率。粒子群算法參數(shù)尋優(yōu)中，分類精確度的變化如圖5所示。

圖5 PSO-SVM算法

由圖可以看出，在參數(shù)組合尋優(yōu)過程中，在粒子更新到150次時，分類的精確度已經(jīng)達到最大值，故設定最高迭代為200次。在迭代最優(yōu)的情況下參數(shù)組合分別取值：C=1.54,σ=0.41,λ=0.14。

為了驗證本文所提出的PSO-SVM算法的效果，設計實驗分別測試PSO-SVM和傳統(tǒng)的SVM以及文獻中提及的SVM-WNB和IPSO-SVM這四種不同的算法，為避免實驗的隨機性和偶然性，選取互不相交的5個測試集進行5次實驗，取5次結果的平均值為最終結果，得到3種分類模型的召回率、精確率以及F-Measure的值，進而分析分類器的分類性能，其結果對比如表3所示。

表3 實驗結果對比

由表3可以看出，PSO-SVM算法的召回率和精確率均高于其他三個算法。其中SVM-WNB算法使用不同的加權方法來評估特征詞的重要程度，同時采用WNB算法彌補最優(yōu)超平面附近分錯的情況，以提高分類性能；IPSO-SVM算法利用混沌搜索的便利性初始化粒子群算法使其均勻分布于整個解空間，從而加快粒子群算法的收斂速度，從而提高分類準確率；PSO-SVM算法首先使用改進的PSO優(yōu)化算法對核函數(shù)參數(shù)組合迭代求取最優(yōu)核參數(shù)組合，然后利用哈夫曼最優(yōu)二叉樹原理構建多分類支持向量機模型，因此精確率更高，大大降低了文本類別誤判的概率。

4 結束語

本文針對測試文本集中有過多的屬性冗余以及支持向量機算法受參數(shù)影響力而引起的分類性能降低問題，提出了一種改進的PSO-SVM算法。首先利用改進的CDMI方法進行屬性約簡；然后以特征詞的詞頻比率作為初始權值，使用絕對誤差方法確定目標函數(shù)，結合粒子群優(yōu)化算法求解最優(yōu)的混合核函數(shù)參數(shù)組合；最后使用改進的決策樹多分類模型構造支持向量機多分類器。采用召回率、F-Measure和精確率作為PSO-SVM算法的評價標準，通過與其它算法在Reuters語料集上的實驗對比，可得本文改進的算法具有更高的分類精度以及更低的計算復雜度。