基于SA-SVM的中文文本分類研究

郭超磊 陳軍華

(上海師范大學信息與機電工程學院 上海 201400)

0 引 言

文本分類，就是利用計算機相關技術將具有相同特征的文本信息根據(jù)文本內(nèi)容自動劃分到預先設定好的文本類別體系中的過程[1]。眾多學者在研究文本分類的過程中，提供了許多優(yōu)秀的分類算法，鐘將等[2]提出一種改進的KNN文本分類算法，介紹KNN文本分類算法，并基于LSA降維和樣本密度對KNN進行改進；Shathi等[3]將貝葉斯算法應用于文本分類中；Bahassine等[4]使用決策樹算法對文本進行分類；Goudjil等[5]采用SVM算法對文本分類進行技術研究。經(jīng)過大量實驗表明，在中文文本分類上，SVM具有較強的泛化能力?；赟VM的文本分類性能與其懲罰因子C和核函數(shù)參數(shù)σ等密切相關，直接影響文本分類精度[6-7]。

選擇SVM的參數(shù)是一個優(yōu)化問題，近年來，國內(nèi)外學者提出了很多優(yōu)化SVM參數(shù)的方法。莊嚴等[8]提出了基于蟻群優(yōu)化算法(ACO)的支持向量機選取參數(shù)算法；陳晉音等[9]提出了基于粒子群算法(PSO)的支持向量機的參數(shù)優(yōu)化；王克奇等[10]采用遺傳算法(GA)優(yōu)化支持向量機參數(shù)。ACO算法的收斂速度較慢易陷入局部最優(yōu)，PSO算法易早熟收斂且局部尋優(yōu)能力較差，GA算法實現(xiàn)比較復雜，需先對問題進行編碼，然后再對最優(yōu)解進行解碼，搜索速度較慢。模擬退火算法(SA)也是一種啟發(fā)式算法[11]，能較強地跳出局部最優(yōu)，提高全局尋優(yōu)能力。

本文提出一種基于模擬退火算法優(yōu)化SVM參數(shù)的方法，并應用于中文文本分類中。利用SA良好的尋優(yōu)性能構建的SVM中文文本分類器，與樸素貝葉斯、KNN算法、決策樹算法、邏輯回歸算法構建的分類器相比，該分類器能達到更好的分類效果，具有更強的魯棒性。

1 相關理論

1.1 模擬退火算法

模擬退火算法[12]來源于材料統(tǒng)計力學的研究成果，它引入固體退火過程的自然機理并適當引入隨機因素，在整個解鄰域范圍內(nèi)隨機性地取值，提高全局尋優(yōu)能力，有效地解決眾多組合優(yōu)化問題。

引入Metropolis準則到優(yōu)化過程，以最大化目標函數(shù)為例，對于某一溫度Ti和優(yōu)化問題的一個解x(k)，可以生成x′。接受x′作為下一個新解x(k+1)的概率為：

(1)

在溫度Ti下，經(jīng)過很多次的轉移之后，降低溫度Ti，得到Ti+1

1.2 支持向量機

對于數(shù)據(jù)集D={(x1,y1),(x2,y2),…,(xn,yn)}，其中xi∈Rn，并表示輸入，yi表示對應輸出，n為輸入樣本的維數(shù)。SVM分類目標是找到一個超平面，這個超平面能將所有樣本分開，并使樣本之間的距離盡可能最大。即有:

y=ωTΦ(x)+b

(2)

式中：Φ(x)為標準正態(tài)分布函數(shù)，ω表示權值向量，b表示偏移向量。

求解最優(yōu)超平面，就是針對所給定的數(shù)據(jù)集樣本，找到權值向量ω和偏移向量b的最優(yōu)值，使得權值代價函數(shù)最小化，且正例和反例之間的間隔最大。對于式(2)而言，難以對超平面參數(shù)ω和b直接求解，因此利用增加非負的松弛因子將式(2)轉變成二次優(yōu)化問題：

(3)

s.t.yi(ωΦ(xi)+b)≥1-ξiξ≥0,i=1,2,…,n

式中：C為懲罰因子，C>0；ξi表示松弛因子。將最少錯分樣本和最大分類間隔折衷考慮，就能得到廣義上的最優(yōu)分類面。

通過引入拉格朗日乘子將式(3)轉化為對偶問題，以便于更好地求解，公式如下：

(4)

式中：αi為拉格朗日乘子。

對式(4)進行求解得到αi值，那么ω為:

ω=∑αiyiΦ(xi)·Φ(x)

(5)

最終，SVM相應的分類決策函數(shù)為:

f(x)=sgn(αiyiΦ(xi)·Φ(x)+b)

(6)

RBF函數(shù)具有收斂域寬、參數(shù)少、通用性好等優(yōu)點，是一個很理想的分類依據(jù)函數(shù)，因此采用RBF函數(shù)建立SVM，公式如下：

(7)

式中：σ為RBF核函數(shù)參數(shù)。

SVM進行分類的基本流程可歸納為：首先將輸入的SVM向量映射到一個特征空間，緊接著在這個特征空間中尋找優(yōu)化的線性分界線，于是就構建出了一個可分離類別的超平面，使不同的類別正確分開。SVM的訓練過程實質上就是尋找全局最優(yōu)解。

2 SA-SVM文本分類方法

2.1 參數(shù)對SVM分類性能的影響

為了驗證懲罰因子C和核函數(shù)參數(shù)σ對SVM分類性能的影響，隨機選擇四類3 306個文本作為訓練集。建立分類SVM模型，并選取適當數(shù)目的文本作為測試集，分析不同C和σ對SVM分類精度的影響，具體結果如表1、表2所示。

表1 C=1時的分類結果

表2 σ=1時的分類結果

從表1和表2的結果可知，在相同的訓練集、測試集下，懲罰因子和核函數(shù)參數(shù)不同，SVM分類準確率不同，這表明C和σ的取值影響基于SVM的文本分類結果，要獲得最優(yōu)的SVM文本分類模型，找到最優(yōu)的C和σ值是關鍵。

2.2 基于SA的SVM參數(shù)選擇設計方案

SA優(yōu)化SVM的懲罰因子C和核函數(shù)參數(shù)σ的主要判定是取得更高的文本分類準確率，在最優(yōu)參數(shù)[C,σ]處能取得最高的分類準確率，故最大化目標函數(shù)為F=Vprecision(C,σ)。

相關設置如下：

(1) 設置溫度T的初始值：SA算法的全局搜索性能受溫度初始值的影響，若初始值高，則全局搜索能力強，但需大量時間進行計算；反之，雖可減少時間，但會影響全局搜索性能。在具體操作時，T的初始值可根據(jù)實驗結果進行靈活調(diào)整。

(2) 設置退火速度(內(nèi)循環(huán)每個溫度的迭代次數(shù))：SA算法的全局搜索性能同時也受退火速度的影響，若在某個溫度下充分搜索，需要時間代價，在具體執(zhí)行時，要根據(jù)實際問題設置合理的退火速度。

(3) 設置溫度管理：權衡計算復雜度，通常的降溫方式為T(k+1)=αT(k)，k為降溫次數(shù)，α一般取較接近1的正常數(shù)。

(4) 設置初始解和解的搜索范圍：SA算法具有優(yōu)良的健壯性，求得的最優(yōu)解不受初始解的影響，可在解空間內(nèi)隨機設置初始解。不同的數(shù)據(jù)集的最優(yōu)參數(shù)[C,σ]范圍不同，實際應用中可根據(jù)實驗結果進行靈活調(diào)整。

(5) 設置記憶存儲器：在搜索過程中，SA算法由于執(zhí)行概率接受環(huán)節(jié)，有可能遺漏當前取得的最優(yōu)解，增加記憶存儲器，存儲搜索過程的中間最優(yōu)解，并及時更新。

(6) 設置終止條件：

① 內(nèi)循環(huán)終止條件：當前狀態(tài)下連續(xù)若干個新解都未被接受或達到迭代次數(shù)。

② 外循環(huán)終止條件：連續(xù)若干次降溫所獲得的最優(yōu)解均不變或T

SA優(yōu)化SVM參數(shù)的過程具體操作描述如下：

(1) 初始化溫度T，設置終止溫度Tmin，設置降溫系數(shù)α。

(2) 產(chǎn)生隨機初始解[C0,σ0](是算法迭代起點)，并以此作為當前最優(yōu)解[Cbest,σbest]=[C0,σ0]，計算目標函數(shù)值F(Cbest,σbest)。

(3) 設置每個T值的迭代次數(shù)L；對l=1,2,…,L做第4至第6步。

(4) 在可行解空間內(nèi)，對當前最優(yōu)解作一次隨機擾動，利用狀態(tài)產(chǎn)生函數(shù)生成一個新解[Cnew,σnew]，并計算其目標函數(shù)值F(Cnew,σnew)以及目標函數(shù)值增量Δf=F(Cnew,σnew)-F(Cbest,σbest)，其中F(C,σ)為優(yōu)化目標。

(5) 采用狀態(tài)接受函數(shù)，判斷是否接受新解：若Δf>0，則接受[Cnew,σnew]作為新的當前解；否則按式(1)中Metropolis準則判決，以概率p接受[Cnew,σnew]為當前最優(yōu)解。若接受，設置當前狀態(tài)為[Cnew,σnew]，存入記憶存儲器；反之，當前狀態(tài)為[Cbest,σbest]。

(6) 判斷是否滿足內(nèi)循環(huán)終止條件，若是，輸出當前解為最優(yōu)解并結束此次迭代，轉入(7)；否則轉入(4)。

(7) 降溫。根據(jù)設置的降溫系數(shù)α進行降溫，取新的溫度T=αT(其中T為上一步迭代的溫度)。

(8) 判斷滿足外循環(huán)終止條件，退火過程終止，轉入(9)；否則轉入(3)；

(9) 輸出當前最優(yōu)解與記憶存儲器的中間最優(yōu)解比較，找到最優(yōu)解[Cfinal,σfinal]，算法結束。

3 基于SA-SVM的中文文本分類

基于SA-SVM的中文文本分類過程如圖1所示。

圖1 基于SA-SVM的中文文本分類過程

采用Python的第三方庫jieba分詞對數(shù)據(jù)集進行分詞處理，然后去除停用詞。

利用TFIDF進行權重計算，TF指的是特征詞在文本中出現(xiàn)的絕對頻率，而IDF指的是特征詞在文本中的文本內(nèi)頻率。常用的TFIDF公式如下：

(8)

利用DF進行特征選擇，文檔頻率計算訓練集中包含特征項t的文本數(shù)目。設|D|為訓練集中的文本總數(shù)，di為其中的一個訓練文本，于是有：

(9)

若t∈di，則p(t,di)=1；若t?di，則p(t,di)=0。

DF值低于某個設定閾值的特征詞屬于低頻詞，它們可能不含或者含有很少的文本分類信息，可以在原始特征空間剔除這樣的特征項，既能降低特征空間的維度，還有可能提高文本分類的準確率。

采用分類常用的評價指標：準確率P、召回率R和F1度量，具體表示如下：

(10)

(11)

(12)

4 實驗例證

為驗證SA-SVM中文文本分類的有效性和可行性，采用SA-SVM對中文文本進行分類實驗。實驗的硬件平臺：操作系統(tǒng)為Windows 10專業(yè)版，處理器為Inter(R) Core(TM) i5-3210M CPU @2.50 GHz，內(nèi)存為10 GB，硬盤為256 GB；軟件平臺：Python 2.7。為保證實驗具有全面性和代表性，使用復旦大學中文文本分類庫和搜狗文本語料庫進行對比實驗。

復旦大學中文文本分類庫共有9 804篇訓練文本，9 833篇測試文本，分為20個類別，每一個文本只屬于一個類別。去除重復和損壞的文本以及文本數(shù)小于100篇的稀有類別，共有9個類別，其中訓練文本9 318篇，測試文本9 331篇。經(jīng)過SA優(yōu)化的SVM參數(shù)[Cfinal,σfinal]=[100,0.05]，將其代入分類模型重新訓練學習，與常用的文本算法比較，實驗結果如表3和圖2所示。

表3 不同分類算法在復旦大學中文文本 分類庫的分類結果 %

圖2 不同分類算法在復旦大學中文文本分類庫 各類別分類精度

搜狗文本語料庫共有9個類別，每個類別1 990篇文本，隨機將每個類別的1 400篇文本分為訓練文本，590篇文本分為測試文本。經(jīng)過SA優(yōu)化的SVM參數(shù)[Cfinal,σfinal]=[10,0.5]，將其代入分類模型重新訓練學習，與常用的文本算法比較，實驗結果如表4和圖3所示。

表4 不同分類算法在搜狗文本語料庫的分類結果 %

圖3 不同分類算法在搜狗文本語料庫的各類別分類準確率

實驗表明，不同數(shù)據(jù)集的最優(yōu)參數(shù)[Cfinal,σfinal]不同，兩組數(shù)據(jù)集通過SA全局尋優(yōu)能力搜索到最優(yōu)的SVM參數(shù)。經(jīng)過SA優(yōu)化參數(shù)的SVM分類模型，相比其他中文文本分類算法，在準確率、召回率和F1度量各個方面有明顯的優(yōu)勢，具有較強的泛化能力，展現(xiàn)了較為顯著的分類性能。

5 結 語

基于SVM的文本分類模型的泛化能力與其參數(shù)選擇緊密相關，為解決優(yōu)化SVM參數(shù)難題，本文提出了一個基于SA優(yōu)化SVM參數(shù)的方法，以最大化文本分類準確率為目標全局搜索SVM的最優(yōu)參數(shù)[Cfinal,σfinal]。在設計算法流程時，合理靈活地設置模擬退火的關鍵參數(shù)，并引入記憶存儲器以防止因執(zhí)行概率接受環(huán)節(jié)遺漏中間最優(yōu)解，使得模擬退火算法更為智能。在設置內(nèi)外循環(huán)終止條件時充分考慮實際情況，在保證最優(yōu)性的基礎上盡可能減少不必要的計算量。實驗結果比較表明，基于SA-SVM中文文本分類模型具有良好的使用價值，展現(xiàn)出了非常顯著的分類性能，為今后的文本分類建模提供了一種可行的思路。由于在綜合考慮分類性能時未能做到充分的特征降維，使得分類過程時間較長，因此下一步的工作將在文本分類的特征降維方法上進行改進，進一步提高模型的計算效率。