張洪勝，高海賓

（淮南聯(lián)合大學(xué) 計(jì)算機(jī)科學(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)換為用于機(jī)器學(xué)習(xí)的樣本時(shí)，存在著轉(zhuǎn)換時(shí)間較長的問題.針對這種情況，筆者提出了一種利用有限人工標(biāo)注樣本特征空間的模擬樣本生成算法，并將其用于并行支持向量機(jī)的文本分類中.實(shí)驗(yàn)表明，利用有限樣本構(gòu)造特征空間模擬生成的大規(guī)模訓(xùn)練樣本，可以訓(xùn)練出具有良好分類效果的分類器，并且這種方式能夠大大減少訓(xùn)練樣本的生成時(shí)間.

1 支持向量機(jī)的文本分類

1.1 支持向量機(jī)分類原理

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

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

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

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

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

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

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

1.2 支持向量機(jī)的文本分類過程

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

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

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

（3）將所有的訓(xùn)練樣本分詞，并按生成的特征空間表示為n 維空間的向量形式：（w1，w2，w3，…，wn），其中wi為通過某種方式計(jì)算得到的第i 個(gè)特征詞的權(quán)重.權(quán)重的表示有相對詞頻和絕對詞頻兩種方法［7］.絕對詞頻為詞在文本中出現(xiàn)的次數(shù)表示， 相對詞頻采取如TF-IDF 等公式通過計(jì)算得到，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）通過某種機(jī)器學(xué)習(xí)算法，對向量形式的訓(xùn)練樣本進(jìn)行訓(xùn)練學(xué)習(xí)，得到分類器的分類模板.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)和結(jié)果

3.1 實(shí)驗(yàn)環(huán)境

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

3.2 實(shí)驗(yàn)及結(jié)果分析

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

表1 模擬樣本生成及SVM 分類實(shí)驗(yàn)

（2）實(shí)驗(yàn)二：在具有不同特征維數(shù)的特征空間中，設(shè)置相同的閥值，利用模擬樣本生成算法生成1 000個(gè)正反例樣本，觀察特征空間維數(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）實(shí)驗(yàn)三：特征空間和閥值相同，多次執(zhí)行同一算法，生成相同數(shù)量1 000 個(gè)的訓(xùn)練樣本，觀察算法中的隨機(jī)過程對模擬樣本訓(xùn)練分類效果的穩(wěn)定性會否產(chǎn)生影響.由表3 可知，模擬樣本生成算法中非0特征位置和非0 特征數(shù)量的生成具有一定的隨機(jī)性，但在特征空間、閥值及樣本生成總數(shù)確定的情況下，模擬樣本的訓(xùn)練分類效果具有較好的穩(wěn)定性.

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

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

表4 樣本生成時(shí)間對比實(shí)驗(yàn)

4 結(jié)語

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