郭超磊 陳軍華

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

0 引 言

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

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

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

1 相關(guān)理論

1.1 模擬退火算法

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

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

(1)

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

1.2 支持向量機(jī)

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

y=ωTΦ(x)+b

(2)

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

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

(3)

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

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

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

(4)

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

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

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

(5)

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

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

(6)

RBF函數(shù)具有收斂域?qū)挕?shù)少、通用性好等優(yōu)點(diǎn)，是一個(gè)很理想的分類依據(jù)函數(shù)，因此采用RBF函數(shù)建立SVM，公式如下：

(7)

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

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

2 SA-SVM文本分類方法

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

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

表1 C=1時(shí)的分類結(jié)果

表2 σ=1時(shí)的分類結(jié)果

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

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

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

相關(guān)設(shè)置如下：

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

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

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

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

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

(6) 設(shè)置終止條件：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(8)

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

(9)

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

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

采用分類常用的評價(jià)指標(biāo)：準(zhǔn)確率P、召回率R和F1度量，具體表示如下：

(10)

(11)

(12)

4 實(shí)驗(yàn)例證

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

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

表3 不同分類算法在復(fù)旦大學(xué)中文文本 分類庫的分類結(jié)果 %

圖2 不同分類算法在復(fù)旦大學(xué)中文文本分類庫 各類別分類精度

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

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

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

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

5 結(jié) 語

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