基于模擬樣本訓(xùn)練的支持向量機

張洪勝，高海賓

（淮南聯(lián)合大學(xué) 計算機科學(xué)與技術(shù)系， 安徽 淮南232038）

隨著網(wǎng)絡(luò)技術(shù)應(yīng)用的高速發(fā)展，互聯(lián)網(wǎng)每天都產(chǎn)生著海量的網(wǎng)頁、郵件等結(jié)構(gòu)化和半結(jié)構(gòu)化的文本信息，基于內(nèi)容學(xué)習(xí)的文本分類技術(shù)是整理和獲取文本信息的重要方式之一.在基于內(nèi)容學(xué)習(xí)的文本分類過程中，特征選擇是文本分類的關(guān)鍵步驟，人工標(biāo)注的訓(xùn)練樣本是影響特征選擇質(zhì)量的重要因素［1］.海量文本信息的分類，要求人工標(biāo)注的訓(xùn)練樣本必須具有一定的數(shù)量規(guī)模和廣泛代表性，才能保證通過訓(xùn)練學(xué)習(xí)得到的分類模板具有較高的準(zhǔn)確率和穩(wěn)定性.傳統(tǒng)的人工標(biāo)注樣本需要具備專業(yè)知識的人員才能完成，而標(biāo)注大量的樣本開銷昂貴［2］，大規(guī)模、高質(zhì)量的人工標(biāo)注樣本較難獲得［3］，并且在將人工標(biāo)注的普通樣本轉(zhuǎn)換為用于機器學(xué)習(xí)的樣本時，存在著轉(zhuǎn)換時間較長的問題.針對這種情況，筆者提出了一種利用有限人工標(biāo)注樣本特征空間的模擬樣本生成算法，并將其用于并行支持向量機的文本分類中.實驗表明，利用有限樣本構(gòu)造特征空間模擬生成的大規(guī)模訓(xùn)練樣本，可以訓(xùn)練出具有良好分類效果的分類器，并且這種方式能夠大大減少訓(xùn)練樣本的生成時間.

1 支持向量機的文本分類

1.1 支持向量機分類原理

支持向量機（Support Vector Machine，簡稱SVM）是基于統(tǒng)計學(xué)習(xí)理論和結(jié)構(gòu)風(fēng)險最小化原則的一種分類方法，由于其很少過度擬合，適合解決訓(xùn)練樣本少、特征維數(shù)高的文本分類問題［4］.

對于線性可分問題，假定訓(xùn)練數(shù)據(jù)（xl，yl），…，（xi，yi），xi∈Rn，yi∈{+1，-1}能夠被超平面（w·x）-b=0 完成正確地分開，那么與兩類樣本點邊緣最大的超平面具有最佳的分類能力.最優(yōu)超平面將由離它最近的少數(shù)樣本點決定，這些少數(shù)樣本點稱為支持向量.求最優(yōu)超平面問題可以轉(zhuǎn)化為一個凸二次規(guī)劃的求解問題，即：

構(gòu)造Lagrange 函數(shù)：

其中αi是Lagrange 乘子，根據(jù)Kuhn-Tucker 條件，αi滿足消去w 和b，通過運算得到原最優(yōu)化問題的Wolfe 對偶問題：

解出αi后，利用w=確定最優(yōu)超平面，由此得到分類判別函數(shù)：

對于非線性可分?jǐn)?shù)據(jù)，根據(jù)mercer 條件可以通過某種非線性變換K（xi，xj）=?（xi）·?（xj）映射到一高維空間，使它們在高維空間線性可分.此時的對偶問題為：

對應(yīng)的分類判別函數(shù)為：

1.2 支持向量機的文本分類過程

以兩類文本分類問題為例，基于內(nèi)容學(xué)習(xí)的文本分類系統(tǒng)的訓(xùn)練和分類過程為：

（1）準(zhǔn)備一定數(shù)量人工標(biāo)注的正例訓(xùn)練樣本和反例訓(xùn)練樣本.

（2）對正例訓(xùn)練樣本采用某種分詞算法進行分詞，通過特征抽取從中選取一定數(shù)量的詞來表示類文本特征.可用于特征選擇的評估函數(shù)有文本頻數(shù)、信息增益、互信息、X2估計、文本證據(jù)權(quán)和優(yōu)勢率等［5］.抽取得到的所有特征在一起構(gòu)成一個可以表示該類文本的n 維向量空間［6］，n 為抽取得到的該類文本特征的個數(shù).

（3）將所有的訓(xùn)練樣本分詞，并按生成的特征空間表示為n 維空間的向量形式：（w1，w2，w3，…，wn），其中wi為通過某種方式計算得到的第i 個特征詞的權(quán)重.權(quán)重的表示有相對詞頻和絕對詞頻兩種方法［7］.絕對詞頻為詞在文本中出現(xiàn)的次數(shù)表示， 相對詞頻采取如TF-IDF 等公式通過計算得到，TF-IDF 公式有多種，較為普遍的一種TF-IDF 公式，見公式（7）：

其中，W（t，d）為詞t 在文本d 中的權(quán)重，而tf(t，d)為詞t 在文本d 中的詞頻，N 為訓(xùn)練文本的總數(shù)，nt為訓(xùn)練文本集中出現(xiàn)t 的文本數(shù)，分母為歸一化因子.

（4）通過某種機器學(xué)習(xí)算法，對向量形式的訓(xùn)練樣本進行訓(xùn)練學(xué)習(xí)，得到分類器的分類模板.

（5）將待分類的文本分詞，并根據(jù)特征空間同樣表示成向量形式，然后用分類器及分類模板對其進行判斷，得到分類類別.

2 訓(xùn)練樣本的模擬生成

2.1 特征空間下訓(xùn)練樣本的特點

正反例訓(xùn)練樣本按照特征空間轉(zhuǎn)換成向量形式的訓(xùn)練樣本后，從直觀上看，正例樣本的所有非0 特征的權(quán)重值之和通常情況下應(yīng)大于反例向量，而且權(quán)重值非0 的特征在正反例向量中出現(xiàn)的位置具有一定的隨機性.

2.2 訓(xùn)練樣本模擬生成算法

根據(jù)正反例樣本的特點，我們利用向量特征空間和TF-IDF 特征權(quán)重計算方法，設(shè)計了一種訓(xùn)練樣本模擬生成算法，算法步驟如下：

第1 步：準(zhǔn)備一定數(shù)量的正例樣本，對每個樣本進行中英文分詞并統(tǒng)計詞頻，并根據(jù)詞頻大小，按照一定比例如提取作為特征空間的特征，并做去重處理；

第2 步：按照TF-IDF 計算所有特征詞的權(quán)重，為了得到特征詞在正例所在類的權(quán)重，在計算時對公式（1）中tf(t，d)的定義做了修改，將其原來為詞t 在文本d 中的詞頻，改為t 在所有正例樣本中出現(xiàn)的詞頻；

第3 步：隨機生成樣本中非0 特征的個數(shù)m（1～10）；

第4 步：通過循環(huán)，隨機生成m 個特征在特征空間的位置i，由此得到由m 個特征組成的、且特征出現(xiàn)位置隨機的模擬樣本；

第5 步：根據(jù)需要生成樣本的個數(shù)，重復(fù)第3～4 步；

第6 步：對于生成的每個向量形式的模擬樣本，計算各維的權(quán)重之和weightsum，若滿足條件（weightsum＜閥值），則將該模擬樣本作為反例樣本，否則作為正例樣本，由此得到用于訓(xùn)練學(xué)習(xí)的所有正反例樣本，條件中的閥值可以通過分類效果比較實驗進行確定.

2.3 模擬樣本訓(xùn)練的支持向量機

利用模擬樣本進行訓(xùn)練分類的支持向量機文本分類模型見圖1.利用模擬樣本訓(xùn)練和分類的支持向量機，其訓(xùn)練分類過程與文中1.2 節(jié)所述過程基本相同，但其訓(xùn)練樣本不再是從人工標(biāo)注的訓(xùn)練文本轉(zhuǎn)換得到，而要利用2.2 節(jié)的模擬樣本生成算法，根據(jù)需要隨機生成獲得.

圖1 模擬樣本訓(xùn)練的支持向量機文本分類模型

3 實驗和結(jié)果

3.1 實驗環(huán)境

實驗以400 份人工標(biāo)注訓(xùn)練樣本為正例樣本，通過特征抽取和TF-IDF 權(quán)重計算生成特征空間，抽取特征338 個.實驗中人工標(biāo)注樣本使用的是NLP 文本分類語料庫（復(fù)旦大學(xué)）中的訓(xùn)練與測試集.支持向量機采用Platt 提出的序列最小優(yōu)化（Sequential Minimal Optimization，SMO）算法［7］.

3.2 實驗及結(jié)果分析

（1）實驗一：模擬樣本生成及SVM 分類訓(xùn)練實驗.按照筆者提出的模擬樣本生成算法，以（樣本非0特征權(quán)重之和＜閥值）作為反例生成條件，不滿足條件的模擬樣本作為正例樣本，隨機模擬生成共1 000個正反例訓(xùn)練樣本， 測試樣本全部為人工標(biāo)注樣本， 觀察不同閥值情況下， 通過模擬樣本訓(xùn)練得到的SVM 分類器的分類效果.由表1 可知，實驗一的結(jié)果表明，隨著非0 特征權(quán)重之和這個閥值的增大，生成的反例樣本數(shù)量增加、正例樣本數(shù)量數(shù)據(jù)減少，通過模擬樣本訓(xùn)練得到的SVM 分類器的正確率也在隨之發(fā)生變化，樣本非0 特征權(quán)重之和設(shè)為＜1.0 的閥值時，生成的模擬樣本訓(xùn)練效果較好，隨著閥值的增大，反例樣本生成過多，訓(xùn)練得到的分類器的分類效果下降.

表1 模擬樣本生成及SVM 分類實驗

（2）實驗二：在具有不同特征維數(shù)的特征空間中，設(shè)置相同的閥值，利用模擬樣本生成算法生成1 000個正反例樣本，觀察特征空間維數(shù)的變化對模擬樣本生成的影響.由表2 可知，在模擬樣本生成算法中的閥值相同的情況下，特征空間維數(shù)減少，反例樣本生成數(shù)量呈減少趨勢，特征空間維數(shù)增加，反例樣本生成數(shù)量也相應(yīng)增加.反例樣本增加或減少到一定程度，都會導(dǎo)致分類器的分類效果下降，因此，針對不同的特征空間，需要選擇合適的閥值，使模擬生成的正反例樣本數(shù)量處于適當(dāng)?shù)谋壤褂?xùn)練得到的分類器具有較好的分類效果.

表2 特征空間維數(shù)對模擬樣本生成訓(xùn)練的影響（權(quán)重和＜2.0）

（3）實驗三：特征空間和閥值相同，多次執(zhí)行同一算法，生成相同數(shù)量1 000 個的訓(xùn)練樣本，觀察算法中的隨機過程對模擬樣本訓(xùn)練分類效果的穩(wěn)定性會否產(chǎn)生影響.由表3 可知，模擬樣本生成算法中非0特征位置和非0 特征數(shù)量的生成具有一定的隨機性，但在特征空間、閥值及樣本生成總數(shù)確定的情況下，模擬樣本的訓(xùn)練分類效果具有較好的穩(wěn)定性.

表3 算法中的隨機過程對訓(xùn)練分類穩(wěn)定性的影響（權(quán)重和＜1.0）

（4）實驗四：生成相同數(shù)量向量形式的訓(xùn)練樣本，模擬樣本生成和正常樣本生成的時間和分類效果比較.由表4 可知，生成相同數(shù)量訓(xùn)練樣本，模擬樣本生成算法所需的時間遠(yuǎn)遠(yuǎn)低于正常方式生成訓(xùn)練樣本的時間，生成樣本數(shù)量規(guī)模大幅增加時，模擬算法生成樣本時間增長不明顯，并可能由于隨機生成樣本中非0 特征數(shù)量的減少而呈現(xiàn)訓(xùn)練時間反而減少的狀況，而正常方式生成樣本在樣本規(guī)模增加時，樣本生成時間則同向增長且增長顯著.

表4 樣本生成時間對比實驗

4 結(jié)語

針對基于內(nèi)容學(xué)習(xí)的文本分類方法在面對大規(guī)模文本分類問題時，人工標(biāo)注的訓(xùn)練樣本存在樣本數(shù)量有限、獲取困難等問題，根據(jù)特征空間下向量形式訓(xùn)練樣本的特點.筆者提出了一種基于特征空間和TF-IDF 權(quán)重計算的模擬樣本生成算法，并將其用于支持向量機的文本分類中.實驗表明，相對于傳統(tǒng)的訓(xùn)練樣本轉(zhuǎn)換方法，基于特征空間和TF-IDF 權(quán)重計算的模擬樣本生成算法可以在較短時間內(nèi)快速生成大規(guī)模的模擬訓(xùn)練樣本，并且在支持向量機文本分類中表現(xiàn)出良好的性能，可以作為機器學(xué)習(xí)在人工標(biāo)注樣本數(shù)量不足情況下一個很好的補充.