高超　許翰林

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

關(guān)鍵詞： 混合算法； 支持向量機； 不均衡數(shù)據(jù)集； 插值樣本； 文本分類； 迭代進(jìn)化

中圖分類號： TN911.1?34； TP391.9 文獻(xiàn)標(biāo)識碼： 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 引 言

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

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

1 支持向量機介紹

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

支持向量機轉(zhuǎn)化成數(shù)學(xué)形式為一個帶約束的最小值問題：

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

2 PSO算法

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

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

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

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

式中：[w]為慣性權(quán)重；[c1]是粒子跟蹤自己歷史最優(yōu)值的權(quán)重系數(shù)；[c2]是粒子跟蹤群體最優(yōu)值的權(quán)重系數(shù)；[r1]和[r2]是區(qū)間[0，1]的隨機數(shù)。

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

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

3 SMOTE算法

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

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

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

4 基于支持向量機的文本分類算法優(yōu)化

4.1 PSO?SMOTE文本分類器設(shè)計

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

4.2 PSO?SMOTE算法生成最優(yōu)插值樣本

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

1） 輸入經(jīng)過預(yù)處理的訓(xùn)練文本數(shù)據(jù)集，獲取少數(shù)類樣本數(shù)據(jù)集合。

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

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

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

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

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

7） 用支持向量機分類算法訓(xùn)練每一個候選粒子并計算適應(yīng)度值。

8） 如果在這個粒子當(dāng)前位置計算出更小的適應(yīng)度值，則更新這個粒子的歷史最優(yōu)值[Pb]。

9） 如果設(shè)置的進(jìn)化停止條件還沒滿足，則返回步驟6）繼續(xù)循環(huán)；如果已經(jīng)滿足停止條件，則得到全局歷史最優(yōu)粒子。組成這個粒子的插值樣本即為全局最優(yōu)插值樣本。

4.3 PSO?SMOTE適應(yīng)度函數(shù)的選擇

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

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

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

5 實驗與結(jié)果分析

5.1 實驗數(shù)據(jù)

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

5.2 實驗結(jié)果

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

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

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

6 結(jié) 語

本文針對支持向量機在文本分類中分類不均衡文本數(shù)據(jù)集的局限，提出PSO?SMOTE混合算法優(yōu)化支持向量機的文本分類能力。實驗結(jié)果表明，本文提出的混合算法有效地提升了支持向量機分類不均衡文本數(shù)據(jù)集的能力。下一步的工作方向是對支持向量機的理論進(jìn)行優(yōu)化，將改進(jìn)的支持向量機與PSO?SMOTE算法相結(jié)合進(jìn)一步提升分類能力，并對PSO?SMOTE算法進(jìn)行進(jìn)一步改進(jìn)，嘗試?yán)弥С窒蛄可刹逯禈颖尽?/p>

參考文獻(xiàn)

[1] 周慶平，譚長庚，王宏君，等.基于聚類改進(jìn)的KNN文本分類算法[J].計算機應(yīng)用研究，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] 杜選.基于加權(quán)補集的樸素貝葉斯文本分類算法研究[J].計算機應(yīng)用與軟件，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不平衡數(shù)據(jù)過采樣算法的改進(jìn)與應(yīng)用[D].南寧：廣西大學(xué)，2015.

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

[4] 崔建明，劉建明，廖周宇.基于SVM算法的文本分類技術(shù)研究[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] 謝娜娜，房斌，吳磊.不均衡數(shù)據(jù)集上文本分類方法研究[J].計算機工程與應(yīng)用，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] 王超學(xué)，張濤，馬春森.面向不平衡數(shù)據(jù)集的改進(jìn)型SMOTE算法[J].計算機科學(xué)與探索，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] 薛薇.非平衡數(shù)據(jù)集的改進(jìn)SMOTE再抽樣算法[J].統(tǒng)計研究，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].電子測量與儀器學(xué)報，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] 張鈺莎，蔣盛益，謝柏林，等.基于改進(jìn)的PSO算法的網(wǎng)絡(luò)社區(qū)劃分方法[J].計算機應(yīng)用與軟件，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ìn)隱樸素貝葉斯算法的研究[J].小型微型計算機系統(tǒng)，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.