改進的支持向量機中文文本分類

顧偉，傅德勝，蔡瑋

改進的支持向量機中文文本分類

顧偉，傅德勝，蔡瑋

支持向量機是數據挖掘的新方法，由于其優秀的學習能力而得到了廣泛的應用，但是，傳統的支持向量機算法在處理大規模問題時存在訓練時間過長和內存空間需求過大的問題，而應用多個支持向量機構成多分類器系統進行并行學習，是目前解決文本分類中大規模數據處理問題的一種有效方法。在分析傳統并行算法的基礎上，提出了一種改進的基于多支持向量機的并行學習算法，實驗結果表明，采用該算法可使得分類效率得到較大的程度的提高，雖然，分類精度相對傳統的方法略差，但是，在可接受的范圍之內。

多支持向量機；文本分類；并行算法

0 引言

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

1 相關研究進展

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

1.1 增量算法

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

1.2 分解算法

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

1.3 并行算法

SVM 對于大規模數據集，訓練速度異常緩慢，并且需要占用很多的內存，應用多個支持向量機分類器構成多分類器系統進行并行學習，是解決大規模數據處理問題的另一種有效方法。w-model 算法[9]和Cascade SVMs算法[10]是并行支持向量機兩種典型的算法。

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

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

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

2 SVM分類原理

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

圖1 最優分類超平面示意圖

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

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

最終的分類判別函數可以表達為公式（3）：

多項式核函數公式（4）：

Gauss 徑向基核函數公式（5）：

Sigmoid核函數公式（6）：

3 一種基于多支持向量機的并行學習算法

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

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

Step1：分別訓練這K個訓練子集，得到K個SVM分類器以及對應的支持向量集SVi，i=1,2Kk。

Step2：分別SVi兩兩合并，進行訓練后得到相應的支持向量集SVj，j=1,2，Kk/2

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

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

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

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

Step7：將新增樣本集M劃分為若干個子集進行增量學習，在分類精度不滿意的情況下將對應的子集加入到集合D中，并轉至步驟1，重新訓練。

Step8：End

4 算法實驗與分析

4.1 實驗描述

真實的數據來自復旦大學中文文本分類庫，該文本庫由復旦大學計算機信息與技術系國際數據庫中心自然語言處理小組構建，該文本全部采自互聯網，包含20個文本類別，該語料庫分為訓練集和驗證集兩部分，去除部分損壞文檔后，得到完整文檔18185篇。本文從該數據庫中提取了經濟、運動和環境3個方面的數據，任選其中的兩類構成一個兩類分類問題，于是就可以得到3個兩類問題，如表1所示：

表1 實驗數據分布

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

4.2 實驗結果及分析

本文采用準確率（Precision）、召回率（Recall）、和訓練時間來評價w-model 算法[9]、Cascade SVMs算法[10]以及標準SVM和改進后的并行SVM分類效果。準確率是判定屬于某類的文本中，正確的判定所占的比例，召回率是對于某類文本，最終給出的判定結果中，正確的判定所占的比例，訓練時間則是用來判定算法的工作效率，如表2～表4所示：

表2 不同算法的分類準確率對比（%）

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

表4 不同算法的訓練時間對比(s)

從表1和表2可以看出，在準確率（Precision） 和召回率（Recall）方面，改進的算法在經濟、環境和運動類比w-model 算法[9]、Cascade SVMs算法[10]以及標準SVM都高。表3的結果表明，在訓練耗時方面，改進后的SVM算法則比w-model 算法[9]、Cascade SVMs算法[10]以及標準SVM都低，提高了分類的效率。

通過以上分析可以看出，分類的效率的提高是本算法最主要的一個優點，具有較高的使用價值。不足的地方是改進后的方法分類效果相對傳統的方法相對較差，但是均在可接受的范圍之內。這是因為文本分類涉及文本表示、權重計算、特征提取、分類算法等多種復雜技術，每一個環節都會對最終的分類效果產生影響。因此需要對文本分類各個環節都做一定的研究與改進，這樣文本系統的性能才會有明顯的提高。

5 總結

本文在分析傳統并行算法的基礎上提出了一種改進的基于多支持向量機的并行學習算法，并對真實語料進行了實驗測試，實驗結果表明這種并行的多支持支持向量機是一種具有較好泛化能力、性能優越的技術，采用該算法可使得分類效率得到較大的程度的提高，雖然分類精度相對傳統的方法略差，但是在可接受的范圍之內。

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

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

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

[4] 王曉丹,王積勤.支持向量機訓練和實現算法綜述[J].計算機工程與應用,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 ]. 哈爾濱工程大學報, 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] 李國正,王猛,曾華軍譯.支持向量機導論[M]. 北京：電子工業出版社,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 ].2007,03:254-258.

[15] 張苗,張德賢.多類支持向量機文本分類方法[J].計算機技術與發展, 2008,03:154-158.

[16] 張振宇.穩健的多支持向量機自適應提升算法.大連交通大學學報 2010,04:147-152.

[17] 付曉利,楊永田,張乃慶.一種基于多支持向量機的增量式并行訓練算法[J ]. 航空電子技術,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）

江蘇高校優勢學科建設工程項目（PAPD）

顧 偉（1983-），男，江蘇南京，碩士，南京信息工程大學，江蘇網絡監控中心，實驗師，研究方向：模式識別、人工智能、數據挖掘，南京，210044傅德勝（1950-），男，江蘇南京，博士，南京信息工程大學，江蘇網絡監控中心，教授，研究方向：數據挖掘，信息安全，南京，210044蔡 瑋（1981-），男，江蘇南京，碩士，南京信息工程大學，講師，研究方向：數據挖掘、軟件工程，南京，211167