基于模擬樣本訓練的支持向量機

張洪勝，高海賓

（淮南聯合大學 計算機科學與技術系， 安徽 淮南232038）

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

1 支持向量機的文本分類

1.1 支持向量機分類原理

支持向量機（Support Vector Machine，簡稱SVM）是基于統計學習理論和結構風險最小化原則的一種分類方法，由于其很少過度擬合，適合解決訓練樣本少、特征維數高的文本分類問題［4］.

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

構造Lagrange 函數：

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

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

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

對應的分類判別函數為：

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

以兩類文本分類問題為例，基于內容學習的文本分類系統的訓練和分類過程為：

（1）準備一定數量人工標注的正例訓練樣本和反例訓練樣本.

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

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

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

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

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

2 訓練樣本的模擬生成

2.1 特征空間下訓練樣本的特點

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

2.2 訓練樣本模擬生成算法

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

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

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

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

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

第5 步：根據需要生成樣本的個數，重復第3～4 步；

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

2.3 模擬樣本訓練的支持向量機

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

圖1 模擬樣本訓練的支持向量機文本分類模型

3 實驗和結果

3.1 實驗環境

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

3.2 實驗及結果分析

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

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

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

表2 特征空間維數對模擬樣本生成訓練的影響（權重和＜2.0）

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

表3 算法中的隨機過程對訓練分類穩定性的影響（權重和＜1.0）

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

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

4 結語

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