王珂，周瑤，趙媛媛

（西安建筑科技大學，西安710055）

0 引言

作為一個信息大平臺，互聯(lián)網(wǎng)的輿論功能為信息交流提供了一個便捷的渠道。然而網(wǎng)絡上的信息良莠不齊，及時準確發(fā)現(xiàn)網(wǎng)絡中的輿情信息和熱點事件并加以監(jiān)督與引導，對社會的和諧穩(wěn)定發(fā)展具有重要意義，尤其是根據(jù)分析的結(jié)果對輿情進行預測，這對有關(guān)部門很有必要[1-2]。

網(wǎng)絡輿情研究與分析的重要依托技術(shù)是文本分類。文本分類作為輿情監(jiān)管的基礎，其重要性不言而喻。SVM 是文本分類中應用最為廣泛的一個算法。SVM[3]自提出之日起至今雖然只有短短二十多年，但是它在分類問題中表現(xiàn)出來的優(yōu)越性能備受機器學習領(lǐng)域?qū)W者的青睞。影響SVM 的分類效率和模型預測性能的主要因素是核參數(shù)[4]，但傳統(tǒng)的核參數(shù)選擇并沒有一套可遵循的理論方法，往往依靠經(jīng)驗進行窮舉或通過交叉驗證進行大量實驗選取合適的參數(shù)，這些方法不僅需要依靠大量的人力物力，而且最終并不能得到令人滿意的結(jié)果。本文針對SVM 這一問題提出了差分進化算法智能選取核參數(shù)。

差分進化算法是一種智能優(yōu)化算法，用它來智能選取SVM 的核參數(shù)可以避免人為經(jīng)驗產(chǎn)生的偶然與誤差，同時還可以節(jié)省人力物力。差分進化算法相較其他優(yōu)化算法有較多優(yōu)勢，如：參數(shù)少，算法簡單，易于實現(xiàn)。但也因為其容易陷入早熟收斂這一特性而受到很多局限。因此，本文首先要對標準DE 算法進行改進，再令其進行SVM 的參數(shù)尋優(yōu)。本文是對標準差分進化算法進行改進，并用該算法優(yōu)化SVM 的核參數(shù)，最后將其應用到分類問題中，實質(zhì)上是對差分進化算法的改進與應用。

1 差分進化算法的改進

1.1 DE算法基本原理

差分進化算法是一種智能隨機搜索算法[5]。變異、交叉、選擇是差分進化算法的主要操作算子。其基本思想是：首先初始化各參數(shù)，隨機生成初始種群，然后從初始種群中隨機選擇兩個不同的個體，利用其向量差與第三個個體按照一定的規(guī)則生成新的變異個體。然后利用該變異個體與父代的目標個體進行交叉生成試驗個體。判斷試驗個體的適應度與目標個體適應度值的大小，適應度高的保留，差的淘汰，不斷迭代，直至逼近全局最優(yōu)解[6]。然而標準差分尋優(yōu)算法受到種群大小、F 值、CR 以及變異策略等的影響。

1.2 標準DE局限性分析

DE 算法因其實現(xiàn)簡單，算法魯棒性好而備受關(guān)注，但差分進化算法也有自身的局限性，即易陷入局部極優(yōu)而出現(xiàn)早熟收斂[7]，造成這種現(xiàn)象主要是因為隨著迭代次數(shù)的增加，種群多樣性降低，使得個體差異太小從而導致算法不能達到全局最優(yōu)點。差分進化算法的收斂速度主要受其控制參數(shù)和變異策略的影響[8]。

變異因子F 決定著種群的多樣性和收斂速度，F(xiàn)一般取值范圍在[0，2]。當F 較大時全局搜索能力提高，不易陷入早熟收斂，但收斂速度減慢；反之，算法的收斂速度加快，對種群擾動小，易陷入局部極優(yōu)出現(xiàn)早熟收斂。交叉概率CR 通常的取值范圍為[0，1]，當CR較大時，局部搜索能力加強收斂速度加快，易陷入局部極優(yōu)；反之，CR 取值較小時，種群多樣性增加有利于全局搜索。

1.3 改進的DE算法

為了避免標準DE 易陷入早熟收斂這一特點，本文提出了一種自適應組合優(yōu)化差分進化算法（Adaptive Combinatorial Optimization Differential Evolution，ACODE）。在搜索前期注重全局搜索能力，在后期主要進行精確的局部搜索，加快收斂速度。因此需要合理選取F 和CR 的值[9-10]。

為了使算法在搜索前期進行全局搜索，F(xiàn) 取值應較大，CR 較??；后期進行局部搜索則需要F 小CR 大，F(xiàn) 和CR 的值需要進行動態(tài)變化。

為使得搜索前期取較大的F，較小的CR，搜索后期有較小的F 和較大的CR，本文使F 和CR 動態(tài)變化。

本文F 和CR 的動態(tài)變化如式（1-2）所示。

其中Fmax、Fmin 分別為F 的取值上限和下限，CRmin、CRmax 分別為CR 取值的上限和下限，其中最大進化代數(shù)用T 表示，當前進化代數(shù)用t 表示。

DE 中還存在一個重要影響因素，即變異策略。式（3）和（4）是其中兩種常見的變異模式，通常情況下使用單一且固定的變異模式，最常采用的是DE/rand/1。

DE/rand/1：

DE/best/1：

其中，變異個體決定著優(yōu)化的方向，同時影響著全局最優(yōu)解的搜索能力。為了既能保證種群的多樣性又能提高收斂速度，本文采取自適應的變異策略，使搜索前期采用式（3）保證全局搜索，后期采用式（4）保證收斂速度。具體變異策略如式（5）。

在前期有助于保持種群的多樣性，后期提高收斂速度，但是如果后期還沒有找到最優(yōu)解，則容易陷入局部最優(yōu)產(chǎn)生早熟收斂。本文采用新增隨機個體來逃出局部極優(yōu)。如果搜索停滯則增加新的個體。搜索停滯即新生成的個體適應度值等于原種群個體的適應度，使得種群個體難以更新從而導致搜索停滯現(xiàn)象。

每個個體i 在迭代過程中使得目標函數(shù)未改進的次數(shù)記作count，若個體i 的目標函數(shù)在某次迭代中得到改進則count 的值保持不變，否則count+1，若新個體等于原始個體L 次則說明L 次該個體未得到更新，表明此個體性能較差已經(jīng)陷入局部極優(yōu)，則隨機生成一個新個體代替它。如式（6）和（7）所示：

If

則：

1.4 算法步驟

ACODE 算法具體操作步驟如下：

（1）初始化種群規(guī)模，進化代數(shù)t+1，最大迭代次數(shù)T，控制參數(shù)CR 和F 按照式（1）和式（2）設置。

（2）計算個體適應度。

（3）判斷步驟2 得到的適應度和迭代次數(shù)是否達到算法終止條件，如果適應度達到理論最優(yōu)值或者滿足t=T 則輸出結(jié)果，否則轉(zhuǎn)到步驟4

（4）對當代種群，根據(jù)改進的變異策略式（5）進行變異操作，生成中間變異個體vi( g+1)

（5）交叉操作，對t+1 代變異個體vi( g+1) 進行交叉操作產(chǎn)生t+1代實驗個體ui,j( j+1)

（6）選擇操作，對t+1 代實驗個體ui,j( j+1) 進行選擇操作產(chǎn)生t+1代個體xi( g+1)

（7）判斷是否存在停滯現(xiàn)象并解決參見式（6）和式（7）

（8）t=t+1，返回步驟2。

1.5 算法性能評價

本文采用基準函數(shù)測試ACODE 算法的性能。這里標準DE 的CR 和F 的值均設置0.8。而ACODE 算法中的CR 和F 分別按照式子（1）和（2）進行自適應變化，且變異策略也按照式子（5）進行自適應變化。為避免實驗偶然性，保證測試質(zhì)量，算法獨立運行20 次，算法迭代次數(shù)為1000，種群大小為100，維數(shù)為10。結(jié)果如表1 所示，收斂曲線圖分別如圖1-3 所示。

測試函數(shù)如下：

（1）Sphere 函數(shù)：

（2）Rastrigin 函數(shù)：

（3）Rosenbrock 函數(shù)：

表1 基準函數(shù)測試結(jié)果

圖1 Sphere函數(shù)收斂曲線圖

從表1 可以看出，對于Sphere 函數(shù)，兩種算法皆表現(xiàn)出較高的精度，但改進的DE 算法明顯比標準DE 算法得到的值更優(yōu)；對于Rastrigrin 函數(shù)，ACODE 算法收斂精度更高，說明該算法能更好地避免局部極優(yōu)；對于Rosenbrock 函數(shù)，可看出ACODE 算法的平均值略差于DE 算法，而其最優(yōu)值略優(yōu)于DE 算法。從收斂曲線看，對于三種基準函數(shù)而言，ACODE 算法均有優(yōu)越的收斂性能，極好地避免了局部極優(yōu)。

綜上，ACODE 算法可克服標準DE 算法自身的缺陷，并在基準函數(shù)測試中性能較好，尋優(yōu)能力較強。

圖2 Rastrigrin函數(shù)收斂曲線圖

圖3 Rosenbrock函數(shù)收斂曲線圖

2 基于ACODE算法的SVM核參數(shù)優(yōu)化

由于ACODE 算法對SVM 參數(shù)優(yōu)化的效果還不能完全確定，因此本文將ACODE 算法應用到具體的分類過程中。本文以搜狗語料庫為實驗數(shù)據(jù)集，共選取十類，每類數(shù)據(jù)集有220 篇文檔，其中每篇訓練集占200篇，剩下的為測試集。算法流程圖如圖4 所示。

首先初始化ACODE-SVM 算法中的參數(shù)，其中，種群規(guī)模M=20，最大進化代數(shù)gmax=100，其他參數(shù)設定依照前文，SVM 的懲罰參數(shù)C 和核函數(shù)的參數(shù)g 的上下限均設為[0.0001，1000]。使用ACODE 算法對SVM 進行最優(yōu)參數(shù)選擇，利用得到的參數(shù)進行模型的訓練和測試，并與未優(yōu)化的模型的結(jié)果進行對比，表2 是本次的實驗結(jié)果。

圖4 ACODE-SVM流程圖

表2 三種算法的實驗結(jié)果對比

從表2 可以看出，整體而言采用ACODE-SVM 算法訓練所得模型的準確率比未優(yōu)化的值更高，分類結(jié)果更準確。

3 結(jié)語

本文研究分類問題中影響SVM 分類效率的主要因素：核參數(shù)和懲罰因子。由于差分進化算法相比較其他智能算法而言控制參數(shù)較少，具有較強的全局搜索能力，魯棒性好，很適合參數(shù)尋優(yōu)問題，因此本文引入差分進化算法優(yōu)化SVM 的參數(shù)并對其進行改進，實驗表明基于ACODE-SVM 的優(yōu)化算法大大提高了SVM 的分類準確率。