顧偉，傅德勝，蔡瑋

改進(jìn)的支持向量機(jī)中文文本分類

顧偉，傅德勝，蔡瑋

支持向量機(jī)是數(shù)據(jù)挖掘的新方法，由于其優(yōu)秀的學(xué)習(xí)能力而得到了廣泛的應(yīng)用，但是，傳統(tǒng)的支持向量機(jī)算法在處理大規(guī)模問題時(shí)存在訓(xùn)練時(shí)間過長(zhǎng)和內(nèi)存空間需求過大的問題，而應(yīng)用多個(gè)支持向量機(jī)構(gòu)成多分類器系統(tǒng)進(jìn)行并行學(xué)習(xí)，是目前解決文本分類中大規(guī)模數(shù)據(jù)處理問題的一種有效方法。在分析傳統(tǒng)并行算法的基礎(chǔ)上，提出了一種改進(jìn)的基于多支持向量機(jī)的并行學(xué)習(xí)算法，實(shí)驗(yàn)結(jié)果表明，采用該算法可使得分類效率得到較大的程度的提高，雖然，分類精度相對(duì)傳統(tǒng)的方法略差，但是，在可接受的范圍之內(nèi)。

多支持向量機(jī)；文本分類；并行算法

0 引言

文本分類又稱文本自動(dòng)分類，是指在給定的類別體系下，由計(jì)算機(jī)自動(dòng)根據(jù)文本內(nèi)容將其劃歸到某一個(gè)或者多個(gè)類別的過程，是搜索引擎、數(shù)字圖書館、信息檢索和過濾、話題追蹤與識(shí)別等領(lǐng)域的技術(shù)基礎(chǔ)，有著廣泛的應(yīng)用前景，也是目前數(shù)據(jù)挖掘領(lǐng)域的一個(gè)研究熱點(diǎn)與核心技術(shù)。目前常用的文本分類方法有最近鄰（K-Nearest Neighbor，KNN）法、人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Networks，ANN）法、樸素貝葉斯分類法（Naive Bayesian classifier, NB）和支持向量機(jī)（Support Vector Machines, SVMs）法等等。其中支持向量機(jī)（SVMs）是由Vapnik等人基于統(tǒng)計(jì)學(xué)習(xí)理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理的提出的一種機(jī)器學(xué)習(xí)方法[1]，由于該方法具有完備的理論基礎(chǔ)、出色的學(xué)習(xí)性能和較強(qiáng)的泛化能力，并且在解決小樣本、非線性和高維空間問題中的具有一定的優(yōu)勢(shì)，使得支持向量機(jī)得到了廣泛的關(guān)注，并被成功地應(yīng)用于文本分類、模式識(shí)別等領(lǐng)域。

1 相關(guān)研究進(jìn)展

為了進(jìn)一步提高支持向量機(jī)的分類性能，眾多專家學(xué)者相繼對(duì)支持向量機(jī)進(jìn)行了大量的研究與應(yīng)用，并提出了各種不同算法來改進(jìn)其學(xué)習(xí)和訓(xùn)練過程以提高支持向量機(jī)的分類性能。根據(jù)前人的研究成果[2-4]，目前支持向量機(jī)算法主要有以下幾種：增量算法、分解算法、并行算法。

1.1 增量算法

增量算法的提出主要用來解決當(dāng)樣本隨時(shí)間持續(xù)而逐漸增加的情況。此類算法在處理新增樣本是，只對(duì)原學(xué)習(xí)結(jié)果中與新樣本有關(guān)的部分進(jìn)行增加、修改或刪除操作，與之無關(guān)的部分則不被觸及。Ralaivola[5]提出的種增量式學(xué)習(xí)方法思想是基于高斯核的局部特性，只更新對(duì)學(xué)習(xí)機(jī)器輸出影響最大的Lag range 系數(shù)，以減少計(jì)算復(fù)雜度。BatchSVM 增量學(xué)習(xí)算法[6]將新增樣本分成互不相交的多個(gè)子集，對(duì)新增樣本分批訓(xùn)練，每次訓(xùn)練中把位于分類間隔以內(nèi)的樣本加入到歷史樣本中，重新訓(xùn)練, 直到所有新增樣本都訓(xùn)練完，楊靜等人則在此基礎(chǔ)上提出了改進(jìn)的BatchSVM學(xué)習(xí)算法[7]。

1.2 分解算法

SVM分解算法最早由Osuna 等人提出，主要思想是基于某種策略將訓(xùn)練集分解成若干子集，在每個(gè)子集上訓(xùn)練支持向量機(jī)，最后采用某種策略將各支持向量機(jī)組合起來[8]。比較典型的算法有SMO算法、chunking算法、SVMlight 算法、libSVM算法等。其中SMO算法是一種特殊的分解算法，該算法將工作集中僅劃分為2個(gè)樣本，由于每次迭代的時(shí)間非常短，因而大大縮短了訓(xùn)練時(shí)間。

1.3 并行算法

SVM 對(duì)于大規(guī)模數(shù)據(jù)集，訓(xùn)練速度異常緩慢，并且需要占用很多的內(nèi)存，應(yīng)用多個(gè)支持向量機(jī)分類器構(gòu)成多分類器系統(tǒng)進(jìn)行并行學(xué)習(xí)，是解決大規(guī)模數(shù)據(jù)處理問題的另一種有效方法。w-model 算法[9]和Cascade SVMs算法[10]是并行支持向量機(jī)兩種典型的算法。

w-model 算法同時(shí)處理w規(guī)模最大為b的樣本集，其設(shè)計(jì)思想類似于程序的并發(fā)執(zhí)行，但不同之處在于在下一時(shí)刻進(jìn)行訓(xùn)練時(shí)要將當(dāng)前時(shí)刻最后一個(gè)并行處理節(jié)點(diǎn)拋棄，并將新的增量樣本集單獨(dú)進(jìn)行訓(xùn)練，所得的結(jié)果替換掉當(dāng)前第一個(gè)并行處理節(jié)點(diǎn)。由于w-model算法利用多個(gè)支持向量機(jī)分類器處理流數(shù)據(jù)，將流數(shù)據(jù)分布到各分類器上與歷史數(shù)據(jù)進(jìn)行重組和學(xué)習(xí)，因而可以避免數(shù)據(jù)流因隨時(shí)間變化而可能產(chǎn)生的學(xué)習(xí)結(jié)果突變。但是算法的并行性并沒有提高流數(shù)據(jù)處理所需要的時(shí)間，此外該算法需要每次都要在 t+1 時(shí)刻舍棄因而可能造成知識(shí)的丟失。

Cascade SVMs算法也采用了多個(gè)支持向量機(jī)分類器對(duì)大規(guī)模的數(shù)據(jù)進(jìn)行并行處理的方法，Cascade SVMs算法保留了所有的分類器，而不舍棄其中的某一個(gè)，并且在對(duì)分類器進(jìn)行更新時(shí)，將這多個(gè)分類器的訓(xùn)練結(jié)果結(jié)合，產(chǎn)生新的分類器，通過這樣的方式來積累學(xué)習(xí)的結(jié)果，并將最后的結(jié)果作為反饋對(duì)初始的分類器進(jìn)行調(diào)整和更新，以避免分布在多個(gè)分類器上的樣本集中樣本分布差異過大對(duì)分類器性能產(chǎn)生的潛在影響。Cascade SVMs 算法利用多個(gè)分類器對(duì)訓(xùn)練樣本集并行處理，降低了整體學(xué)習(xí)過程需要的時(shí)間，同時(shí)利用反饋對(duì)初始的分類器進(jìn)行調(diào)整和更新，避免了初始訓(xùn)練樣本的分布差異過大而對(duì)分類器性能產(chǎn)生的潛在影響。但由于反饋是在各訓(xùn)練樣本集的支持向量集逐層合并后才進(jìn)行，在訓(xùn)練樣本集個(gè)數(shù)較多的情況下，逐層訓(xùn)練分類器合并需要花費(fèi)大量的時(shí)間。

盡管前人在SVM算法方面做了大量的工作，但是支持向量機(jī)同時(shí)還存在一些局限性依然沒有克服，例如其求解時(shí)間和空間復(fù)雜度分別為O（n3）和O（n2），當(dāng)訓(xùn)練集規(guī)模較大時(shí)，支持向量機(jī)的訓(xùn)練時(shí)間會(huì)太長(zhǎng)并且容易導(dǎo)致內(nèi)存空間不足。解決此類問題的方法主要是從如何處理樣本集的訓(xùn)練問題、提高訓(xùn)練算法收斂速度等方面進(jìn)行改進(jìn)，例如工作集方法、并行化方法、避免求解二次規(guī)劃問題方法和幾何方法等等。本文在傳統(tǒng)并行算法的基礎(chǔ)上提出了一種改進(jìn)的基于多支持向量機(jī)的并行學(xué)習(xí)算法，并在中文文本分類中取得了一定的效果。

2 SVM分類原理

SVM 方法是從線性可分情況下的最優(yōu)分類面提出的[11，12]，對(duì)于一個(gè)線性的兩類分類問題，SVM的是找出一個(gè)合適的分類函數(shù)對(duì)未知樣本進(jìn)行預(yù)測(cè)，要求該分類函數(shù)不但能將兩類正確地分開，并且可以使兩類的分類間隔最大以保證最小的分類錯(cuò)誤率，如圖1所示：

圖1 最優(yōu)分類超平面示意圖

圖1中實(shí)心點(diǎn)和空心點(diǎn)代表兩類樣本，H為分類超平面，H1和H2分別為過各類中離H最近的樣本且平行于H的超平面，它們到H的距離相等，H1和H2之間的距離叫做分類間隔，所謂最優(yōu)分類超平面就是以最大間隔將兩類正確分開的超平面。

其中w表示垂直于超平面的向量，b表示偏移量。將判別函數(shù)歸一化，使兩類所有樣本都滿足公式（2）：

最終的分類判別函數(shù)可以表達(dá)為公式（3）：

多項(xiàng)式核函數(shù)公式（4）：

Gauss 徑向基核函數(shù)公式（5）：

Sigmoid核函數(shù)公式（6）：

3 一種基于多支持向量機(jī)的并行學(xué)習(xí)算法

應(yīng)用多個(gè)支持向量機(jī)分類器對(duì)大規(guī)模的訓(xùn)練樣本集進(jìn)行并行處理的最基本出發(fā)點(diǎn)是[13-17]：按照某種規(guī)則劃分成多個(gè)容易處理的小規(guī)模訓(xùn)練樣本子集，并將它們分布在多個(gè)支持向量機(jī)分類器上進(jìn)行訓(xùn)練。本文在w-model 算法和Cascade SVMs算法的基礎(chǔ)上，借鑒二者優(yōu)點(diǎn)，提出了一種新的并行支持向量機(jī)方法。該算法在w-model算法的基礎(chǔ)上，采用了多個(gè)支持向量機(jī)分類器對(duì)數(shù)據(jù)進(jìn)行并行處理，并且在更新時(shí)保留了所有的分類器，但考慮到不同子樣本集中樣本的分布狀態(tài)差異對(duì)分類器性能產(chǎn)生的潛在影響，因此在更新分類器的時(shí)候利用支持向量集的傳遞構(gòu)成循環(huán)式的反饋，以調(diào)整分類器的分類性能，并通過調(diào)整Cascade SVMs算法中的反饋方式來節(jié)省訓(xùn)練分類器時(shí)間，該方法在保證分類器推廣能力的同時(shí)減少了支持向量機(jī)的訓(xùn)練時(shí)間，并減少了支持向量的數(shù)目。具體算法描述如下：

以二值分類為例，假定己有樣本集D和新增樣本集M，并且D被劃分為K個(gè)個(gè)不相交的子集，K為2的偶數(shù)倍，構(gòu)造多層支持向量機(jī)模型，其算法可以描述為以下步驟：

Step1：分別訓(xùn)練這K個(gè)訓(xùn)練子集，得到K個(gè)SVM分類器以及對(duì)應(yīng)的支持向量集SVi，i=1,2Kk。

Step2：分別SVi兩兩合并，進(jìn)行訓(xùn)練后得到相應(yīng)的支持向量集SVj，j=1,2，Kk/2

Step3：重復(fù)步驟2中的操作,直到得到最后需要合并的SVm和SVn。

Step4：分別將SVm和SVn 作為反饋向量加入到前k/2和后k/2個(gè)訓(xùn)練子集中，重新進(jìn)行訓(xùn)練，重復(fù)步驟1至步驟3，得到新的SV’m和SV’n。

Step5：如果SVm-SV’m= ?且SVn-SV’n=?，則將SV’m和SV’n合并，如果其差集為一固定的訓(xùn)練樣本或者SVm-SV’m≤εand SVn-SV’n≤ε，則合并SV’m和SV’n，并加入（SVm-SV’m）和（SVn-SV’n）。

Step6：訓(xùn)練合并后的支持向量集，并得到最終的分類器SVMS。

Step7：將新增樣本集M劃分為若干個(gè)子集進(jìn)行增量學(xué)習(xí)，在分類精度不滿意的情況下將對(duì)應(yīng)的子集加入到集合D中，并轉(zhuǎn)至步驟1，重新訓(xùn)練。

Step8：End

4 算法實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)描述

真實(shí)的數(shù)據(jù)來自復(fù)旦大學(xué)中文文本分類庫(kù)，該文本庫(kù)由復(fù)旦大學(xué)計(jì)算機(jī)信息與技術(shù)系國(guó)際數(shù)據(jù)庫(kù)中心自然語言處理小組構(gòu)建，該文本全部采自互聯(lián)網(wǎng)，包含20個(gè)文本類別，該語料庫(kù)分為訓(xùn)練集和驗(yàn)證集兩部分，去除部分損壞文檔后，得到完整文檔18185篇。本文從該數(shù)據(jù)庫(kù)中提取了經(jīng)濟(jì)、運(yùn)動(dòng)和環(huán)境3個(gè)方面的數(shù)據(jù)，任選其中的兩類構(gòu)成一個(gè)兩類分類問題，于是就可以得到3個(gè)兩類問題，如表1所示：

表1 實(shí)驗(yàn)數(shù)據(jù)分布

所有實(shí)驗(yàn)的硬件平臺(tái)為：操作系統(tǒng)為Microsoft Windows XP Professiona ( SP3)，CPU為P4 4. 0GH z, 內(nèi)存4G MB，硬盤500 GB；軟件平臺(tái)為Matlab7.0。本文的實(shí)驗(yàn)系統(tǒng)是用C++語言編寫而成，其中分詞系統(tǒng)采用的是中科院研制的漢語詞法分析系統(tǒng) ICTCLAS（Institute of Computing Technology, Chinese Lexical Analysis System），經(jīng)過特征提取后，特征空間的維數(shù)為4000；同時(shí)，為了便于和傳統(tǒng)機(jī)器學(xué)習(xí)方法對(duì)比，標(biāo)準(zhǔn)的SVM分類方法使用的是臺(tái)灣大學(xué)林智仁的開源工具包LIBSVM。

4.2 實(shí)驗(yàn)結(jié)果及分析

本文采用準(zhǔn)確率（Precision）、召回率（Recall）、和訓(xùn)練時(shí)間來評(píng)價(jià)w-model 算法[9]、Cascade SVMs算法[10]以及標(biāo)準(zhǔn)SVM和改進(jìn)后的并行SVM分類效果。準(zhǔn)確率是判定屬于某類的文本中，正確的判定所占的比例，召回率是對(duì)于某類文本，最終給出的判定結(jié)果中，正確的判定所占的比例，訓(xùn)練時(shí)間則是用來判定算法的工作效率，如表2～表4所示：

表2 不同算法的分類準(zhǔn)確率對(duì)比（%）

表3 不同算法的分類召回率對(duì)比（%）

表4 不同算法的訓(xùn)練時(shí)間對(duì)比(s)

從表1和表2可以看出，在準(zhǔn)確率（Precision） 和召回率（Recall）方面，改進(jìn)的算法在經(jīng)濟(jì)、環(huán)境和運(yùn)動(dòng)類比w-model 算法[9]、Cascade SVMs算法[10]以及標(biāo)準(zhǔn)SVM都高。表3的結(jié)果表明，在訓(xùn)練耗時(shí)方面，改進(jìn)后的SVM算法則比w-model 算法[9]、Cascade SVMs算法[10]以及標(biāo)準(zhǔn)SVM都低，提高了分類的效率。

通過以上分析可以看出，分類的效率的提高是本算法最主要的一個(gè)優(yōu)點(diǎn)，具有較高的使用價(jià)值。不足的地方是改進(jìn)后的方法分類效果相對(duì)傳統(tǒng)的方法相對(duì)較差，但是均在可接受的范圍之內(nèi)。這是因?yàn)槲谋痉诸惿婕拔谋颈硎?、?quán)重計(jì)算、特征提取、分類算法等多種復(fù)雜技術(shù)，每一個(gè)環(huán)節(jié)都會(huì)對(duì)最終的分類效果產(chǎn)生影響。因此需要對(duì)文本分類各個(gè)環(huán)節(jié)都做一定的研究與改進(jìn)，這樣文本系統(tǒng)的性能才會(huì)有明顯的提高。

5 總結(jié)

本文在分析傳統(tǒng)并行算法的基礎(chǔ)上提出了一種改進(jìn)的基于多支持向量機(jī)的并行學(xué)習(xí)算法，并對(duì)真實(shí)語料進(jìn)行了實(shí)驗(yàn)測(cè)試，實(shí)驗(yàn)結(jié)果表明這種并行的多支持支持向量機(jī)是一種具有較好泛化能力、性能優(yōu)越的技術(shù)，采用該算法可使得分類效率得到較大的程度的提高，雖然分類精度相對(duì)傳統(tǒng)的方法略差，但是在可接受的范圍之內(nèi)。

[1] Vapnik V N. The Nature of Statistical Learning Theory [M].New York: Springer-Verlag,1995:205-208.

[2] 顧亞祥,丁世飛.支持向量機(jī)研究進(jìn)展[J].計(jì)算機(jī)科學(xué),2011,38(2):14-17.

[3] 祁亨年.支持向量機(jī)及其應(yīng)用研究綜述[J].計(jì)算機(jī)工程,2004,30(10):6-9.

[4] 王曉丹,王積勤.支持向量機(jī)訓(xùn)練和實(shí)現(xiàn)算法綜述[J].計(jì)算機(jī)工程與應(yīng)用,2004,13(10):75-78.

[5] Ralaivola L, Flovence d. Incremental Support vector machine Learning: a Local Approach[C] Proceedings of International Conference on Neural Network s. Vienna, Aus t ria,2001: 322-330.

[6] Domeniconi C, Gunop lo s D. Incremental support vector machine construction [A]. ICDM [C]. IEEE Trans, 2001: 589- 592.

[7] 楊靜, 張健沛, 劉大聽.基于多支持向量機(jī)分類器的增量學(xué)習(xí)算研究[J ]. 哈爾濱工程大學(xué)報(bào), 2006, 26 (1) : 103- 106.

[8] Cristian, Shawe t. An introduction to support vector machine [M]. New York: Cambridge University Press, 2000.

[9] Lin K M, Lin C H. A Study of Reduced Support Vector Machines[C]. IEEE Transactions on Neural Network, 2003.

[10] Hans Peter Graf, Eric Cosatto, Leon Bottou, et al. Parallel Support Vector Machines:The Cascade SVM[C]. Proceedings of NIPS, 2004, 196-212.

[11] Cristianim N, Shawe-Taylor J.Introduction to Support Vector Machine[M].Cambridge University Press,2000.

[12] 李國(guó)正,王猛,曾華軍譯.支持向量機(jī)導(dǎo)論[M]. 北京：電子工業(yè)出版社,2004.

[13] Y.Yang, X.Liu.A Re-examination of Text Categorization Methods[C]. ACM (SIGIR'99).New York.ACM.Press. 1999:42-49.

[14] 馬金娜; 田大鋼.基于支持向量機(jī)的中文文本自動(dòng)分類研究.系統(tǒng)工程與電子技術(shù)[J ].2007,03:254-258.

[15] 張苗,張德賢.多類支持向量機(jī)文本分類方法[J].計(jì)算機(jī)技術(shù)與發(fā)展, 2008,03:154-158.

[16] 張振宇.穩(wěn)健的多支持向量機(jī)自適應(yīng)提升算法.大連交通大學(xué)學(xué)報(bào) 2010,04:147-152.

[17] 付曉利,楊永田,張乃慶.一種基于多支持向量機(jī)的增量式并行訓(xùn)練算法[J ]. 航空電子技術(shù),2007,06:214-217.

Improved SVM for Chinese Text Classification

Gu Wei1, Fu Desheng2, Cai Wei3
(1. Jiangsu Engineering Center of Network Monitoring, Nanjing University of Information Science & Technology, Nanjing210044, China; 2. School of Computer & Software, Nanjing University of Information Science & Technology, Nanjing210044, China; 3. School of Computer Engineering, Nanjing Institute of Technology, Nanjing 211167, China)

Support Vector Machines (SVMs) is a new technique for data mining. It has wide applications in various fields and is a research hot pot of the machine learning field. However, SVMs needs longer training time and larger memory when it is applied to handling large-scale problems. It’s an effective way to solve large scale data processing in text classification with multiple classifier systems composed by multiple support vector machine classifiers. Based on the analysis of traditional parallel algorithms, an improved algorithm based on multiple SVMs is proposed. The experimental results indicate that the new algorithm works well in precision and recall rate in the condition that the speeds of classification increases remarkably. Compared with traditional algorithms, the classified accuracy is lower but is within the range for acceptance.

Multiple SVMs; Text Classification; Parallel Algorithms

TP311

A

1007-757X(2014)10-0017-03

2014.06.27）

江蘇高校優(yōu)勢(shì)學(xué)科建設(shè)工程項(xiàng)目（PAPD）

顧 偉（1983-），男，江蘇南京，碩士，南京信息工程大學(xué)，江蘇網(wǎng)絡(luò)監(jiān)控中心，實(shí)驗(yàn)師，研究方向：模式識(shí)別、人工智能、數(shù)據(jù)挖掘，南京，210044傅德勝（1950-），男，江蘇南京，博士，南京信息工程大學(xué)，江蘇網(wǎng)絡(luò)監(jiān)控中心，教授，研究方向：數(shù)據(jù)挖掘，信息安全，南京，210044蔡 瑋（1981-），男，江蘇南京，碩士，南京信息工程大學(xué)，講師，研究方向：數(shù)據(jù)挖掘、軟件工程，南京，211167