基于支持向量機的不均衡文本分類方法

高超　許翰林

摘 要： 目前支持向量機（SVM）對均衡文本數據集進行文本分類時表現十分良好，但如果文本數據集是不均衡的，尤其是當不均衡率很大時，容易導致支持向量機分類失敗。提出PSO?SMOTE混合算法，針對不均衡文本數據集問題，運用SMOTE算法生成插值樣本均衡數據集，并通過PSO算法迭代進化得到最佳的插值樣本，對支持向量機的文本分類能力進行優化。實驗結果表明，新算法大幅優化了支持向量機分類不均衡文本數據集的能力。

關鍵詞： 混合算法； 支持向量機； 不均衡數據集； 插值樣本； 文本分類； 迭代進化

中圖分類號： TN911.1?34； TP391.9 文獻標識碼： A 文章編號： 1004?373X（2018）15?0183?04

Unbalanced text classification method based on support vector machine

GAO Chao， XU Hanlin

（School of Electronic & Information Engineering， Nanjing University of Information Science and Technology， Nanjing 210044， China）

Abstract： The support vector machine （SVM） performs well in text categorization of balanced text datasets， but will cause the classification failure when the text dataset is unbalanced， especially for high unbalanced ratio. The PSO?SMOTE hybrid algorithm is proposed to solve the unbalanced text datasets. The SMOTE （synthetic minority oversampling technique） algorithm is used to generate the balanced dataset of interpolation sample， and then the iterative evolution is performed for the interpolation sample by means of PSO algorithm to obtain the optimal interpolation sample， and optimize the text classification performance of SVM. The experimental results show that the new algorithm can greatly optimize the ability of SVM to classify the unbalanced text datasets.

Keywords： hybrid algorithm； support vector machine； unbalanced dataset； interpolation sample； text classification； iterative evolution

0 引 言

通常來說，文本分類的主要任務是將未被標記的文檔自動分類到預定義的類別。常見的文本分類方法有支持向量機（Support Vector Machine，SVM）、K最近鄰算法（KNN）和樸素貝葉斯（Native Bayes）等。學術界的許多學者也針對這些算法做出了改進研究。文獻[1]提出一種基于聚類的改進KNN算法。文獻[2]提出一種加權補集貝葉斯文本分類算法。

與其他的文本分類方法相比，支持向量機因為其強大的理論背景以及在處理分類問題中所表現出的優異的泛化能力，越來越多的學者傾向于使用支持向量機進行文本分類。雖然支持向量機十分擅長對均衡文本數據集進行文本分類，但在面對不均衡文本數據集時的分類表現卻差強人意。本文針對這一問題提出SMOTE?PSO混合算法對支持向量機進行優化。混合算法生成的最優插值樣本均衡了數據集，改善了支持向量機分類不均衡文本集的表現。

1 支持向量機介紹

支持向量機方法建立在統計學習理論的VC維理論和結構風險最小原理基礎上，根據有限的樣本信息在模型的復雜性（即對特定訓練樣本的學習精度，Accuracy）和學習能力（即無錯誤地識別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力（或稱泛化能力）。支持向量機的基本原理為：假設存在訓練樣本[xi，yi，i=1，2，…，m]，可以被某個超平面[ω·x+b=0]無錯地分開，其中，[xi∈Rn，yi∈-1，1]，m為樣本個數， [Rn]為n維實數空間。因此與兩類最近的樣本點距離最大的分類超平面為最優超平面。如圖1所示，H為最優超平面。最優超平面只由離它最近的少量樣本點即支持向量確定。

支持向量機轉化成數學形式為一個帶約束的最小值問題：

[min12ω2s.t. yiω?xi+b≥1， i=1，2，…，n] （1）

2 PSO算法

粒子群優化算法（PSO）是一種基于種群信息共享概念的最優解搜索方法。粒子群算法首先對種群中的粒子進行初始化，隨機分配它們的位置。種群中的每一個個體（粒子）在搜索空間中根據之前的搜索經驗不斷改進自己的搜索位置。

在搜索最優解的過程中，粒子不斷調整它們的位置和速度。將每一個粒子搜索到的歷史最優值設為[Pb（t）]，全部粒子搜索到的最優值被稱作全局歷史最優解，設為[Pg（t）]。

粒子[Pi]的速度更新公式如下：

[Vi（t+1）=wVi（t）+c1?r1（t）Pb（t）-Pi（t）+c2?r2（t）Pg（t）-Pi（t）] （2）

式中：[w]為慣性權重；[c1]是粒子跟蹤自己歷史最優值的權重系數；[c2]是粒子跟蹤群體最優值的權重系數；[r1]和[r2]是區間[0，1]的隨機數。

粒子[Pi]的位置更新公式如下：

[Pi（t+1）=Pi（t）+Vi（t）] （3）

3 SMOTE算法

SMOTE（Synthetic Minority Oversampling Technique）算法的基本思想是在少數類中相距較近的樣本之間插入一個人工合成的樣本均衡數據集。算法的具體步驟如下：對少數類中的每一個樣本[xi]，尋找k個與[xi]距離最近的樣本點。在k個樣本點中隨機抽取n個樣本點[xij（j=][1，2，…，n）]與[xi]進行線性插值操作，生成插值樣本[pj]。

[pj=xi+rand（0，1）×（xi-xij）] （4）

式中[rand（0，1）]表示區間[0，1]中的一個隨機數。插值樣本生成示意圖如圖2所示。

4 基于支持向量機的文本分類算法優化

4.1 PSO?SMOTE文本分類器設計

本文提出的PSO?SMOTE文本分類器與傳統的支持向量機文本分類器相比，對不均衡文本集的分類效果更佳。首先對文本數據集進行預處理，將數據集轉換為支持向量機可以處理的形式。需要利用向量空間模型（Vector Space Model）把文本表示成向量形式。在向量空間模型中，文本[dk=（w1，k，w2，k，…，wi，k，…，wn，k）]。其中，[wi，k]代表文本[dk]中特征項[ti]的權重。文本被表示成向量形式之后往往會因為向量維數過高影響分類效果。本文選擇CHI（卡方統計量）作為文本特征選擇方法進行降維處理。使用本文提出的PSO?SMOTE算法在少數類中生成最優插值樣本均衡文本數據集。最終使用支持向量機可以找出有效的超平面，利用分類模型對文本數據集進行有效地劃分。PSO?SMOTE優化分類器模型如圖3所示。

4.2 PSO?SMOTE算法生成最優插值樣本

通過原始的SMOTE算法簡單的生成隨機插值樣本很有可能產生噪音插值樣本對分類結果造成影響[3]，所以需要對新生成的插值樣本進行一定的篩選。本文提出的PSO?SMOTE混合算法可以簡單有效地得到最優的插值樣本，提高支持向量機文本分類的表現。PSO?SMOTE算法步驟如下：

1） 輸入經過預處理的訓練文本數據集，獲取少數類樣本數據集合。

2） 根據式（6）生成隨機插值樣本，初始化大小為[m×q×r]粒子群。其中，[r]是每個插值樣本的維度，[q]是插值樣本的個數，[m]是種群中粒子的個數。

3） 初始化粒子群的速度[Vi， i=1，2，…，q×r]。

4） 對由插值樣本組成的粒子[Pi，i=1，2，…，m]中的每一個位置[Pi]用支持向量機分類算法進行訓練并用適應度函數計算它的適應度值。

5） 初始化每一個粒子的最優位置為它的初始位置，[Pbi=Pi，i=1，2，…，m]。

6） 得到種群中的全局最優粒子[Pg]。分別根據式（2），式（3）更新每一個粒子的速度、位置。

7） 用支持向量機分類算法訓練每一個候選粒子并計算適應度值。

8） 如果在這個粒子當前位置計算出更小的適應度值，則更新這個粒子的歷史最優值[Pb]。

9） 如果設置的進化停止條件還沒滿足，則返回步驟6）繼續循環；如果已經滿足停止條件，則得到全局歷史最優粒子。組成這個粒子的插值樣本即為全局最優插值樣本。

4.3 PSO?SMOTE適應度函數的選擇

適應度函數提供了找出最優解的方式并且掌控著粒子的進化過程。適應度函數幫助PSO算法評估每一個候選粒子即每一個問題的潛在解的優劣，所以選擇一個合適的適應度函數是非常重要的。本文選取G?mean作為適應度函數。G?mean的計算公式如下：

[G?mean=TpTp+FN·TNTN+Fp] （5）

式中：[Tp]代表正類樣本最終被預測分類為正類的樣本個數；[TN]代表負類樣本最終被預測分類為負類的樣本個數；[Fp]代表負類樣本最終被預測分類為正類的樣本個數；[FN]代表正類樣本最終被預測分類為負類的樣本個數。學術界學者通常會利用G?mean來度量分類器分類不均衡數據集的能力。

5 實驗與結果分析

5.1 實驗數據

本文從搜狗實驗室中選取編輯經過手工整理的新聞語料，并且已經分類為經濟、社會、體育、環境、政治五大類。本實驗的重點是測評PSO?SMOTE混合算法優化支持向量機分類不均衡文本的能力，所以刻意將每類新聞文本與其他非新聞文本數據混合構成不均衡文本數據集。文本數據的文本特征選擇采用卡方統計量算法。如表1所示，為了提升實驗數據的復雜度，每一類不均衡文本集的不均衡率都不相同。

5.2 實驗結果

如圖4所示，實驗選取了一個不均衡文本集并采用本文所提出的PSO?SMOTE算法對在少數類中生成的插值樣本進行迭代優化。初始化種群中的粒子數為30，進化迭代次數設為200，適應度函數選取G?mean。群體中的每一個粒子由隨機生成的插值樣本組成。圖4中的兩條曲線分別為群體的最佳G?mean曲線以及平均G?mean曲線。可以明顯看出，隨著進化迭代次數的增加，種群中的粒子也在不斷優化。證明本文提出的PSO?SMOTE算法可以有效地對經典SMOTE算法在不均衡文本集中生成的隨機插值樣本進行優化。

為了突出本文提出的PSO?SMOTE算法對支持向量機分類不均衡文本數據集的優化，實驗將PSO?SMOTE算法與SMOTE算法以及經典支持向量機算法作為對比。分別對5.1節中整理的不均衡文本數據集進行分類運算，性能評價標準依舊選擇G?mean。實驗過程中選擇支持向量機的核參數為RBF核，采取交叉驗證的方式確定懲罰系數[C]和核寬度[σ]的值。實驗結果如表2所示。

從表2可以看出，PSO?SMOTE算法改進了支持向量機分類不均衡文本數據集的能力。證明此算法存在一定的實用性和推廣價值。

6 結 語

本文針對支持向量機在文本分類中分類不均衡文本數據集的局限，提出PSO?SMOTE混合算法優化支持向量機的文本分類能力。實驗結果表明，本文提出的混合算法有效地提升了支持向量機分類不均衡文本數據集的能力。下一步的工作方向是對支持向量機的理論進行優化，將改進的支持向量機與PSO?SMOTE算法相結合進一步提升分類能力，并對PSO?SMOTE算法進行進一步改進，嘗試利用支持向量生成插值樣本。

參考文獻

[1] 周慶平，譚長庚，王宏君，等.基于聚類改進的KNN文本分類算法[J].計算機應用研究，2016，33（11）：3374?3377.

ZHOU Qingping， TAN Changgeng， WANG Hongjun， et al. Improved KNN text classification algorithm based on clustering [J]. Application research of computers， 2016， 33（11）： 3374?3377.

[2] 杜選.基于加權補集的樸素貝葉斯文本分類算法研究[J].計算機應用與軟件，2014，31（9）：253?255.

DU Xuan. Research on weighted complement?based naive Bayes text classification algorithm [J]. Computer applications and software， 2014， 31（9）： 253?255.

[3] 陳斌.SMOTE不平衡數據過采樣算法的改進與應用[D].南寧：廣西大學，2015.

CHEN Bin. The improvement and application of SMOTE algorithm for unbalanced data sampling [D]. Nanning： Guangxi University， 2015.

[4] 崔建明，劉建明，廖周宇.基于SVM算法的文本分類技術研究[J].計算機仿真，2013，30（2）：299?302.

CUI Jianming， LIU Jianming， LIAO Zhouyu. Research of text categorization based on support vector machine [J]. Computer simulation， 2013， 30（2）： 299?302.

[5] 謝娜娜，房斌，吳磊.不均衡數據集上文本分類方法研究[J].計算機工程與應用，2013，49（20）：118?121.

XIE Nana， FANG Bin， WU Lei. Study of text categorization on imbalanced data [J]. Computer engineering and applications， 2013， 49（20）： 118?121.

[6] 王超學，張濤，馬春森.面向不平衡數據集的改進型SMOTE算法[J].計算機科學與探索，2014，8（6）：727?734.

WANG Chaoxue， ZHANG Tao， MA Chunsen. Improved SMOTE algorithm for imbalanced datasets [J]. Journal of frontiers of computer science & technology， 2014， 8（6）： 727?734.

[7] 薛薇.非平衡數據集的改進SMOTE再抽樣算法[J].統計研究，2012，29（6）：95?98.

XUE Wei. An improved SMOTE algorithm for re?sampling imbalanced data sets [J]. Statistical research， 2012， 29（6）： 95?98.

[8] 王道明，魯昌華，蔣薇薇，等.基于粒子群算法的決策樹SVM多分類方法研究[J].電子測量與儀器學報，2015，29（4）：611?615.

WANG Daoming， LU Changhua， JIANG Weiwei， et al. Study on PSO?based decision?tree SVM multi?class classification method [J]. Journal of electronic measurement and instrumentation， 2015， 29（4）： 611?615.

[9] 張鈺莎，蔣盛益，謝柏林，等.基于改進的PSO算法的網絡社區劃分方法[J].計算機應用與軟件，2013，30（8）：25?27.

ZHANG Juesha， JIANG Shengyi， XIE Bolin， et al. Improved PSO algorithm based network community detection method [J]. Computer applications and software， 2013， 30（8）： 25?27.

[10] 李晶輝，張小剛，陳華，等.一種改進隱樸素貝葉斯算法的研究[J].小型微型計算機系統，2013，34（7）：1654?1658.

LI Jinghui， ZHANG Xiaogang， CHEN Hua， et al. Improved algorithm for learning hidden naive Bayes [J]. Journal of Chinese computer systems， 2013， 34（7）： 1654?1658.