基于多示例學習框架的文本分類算法

徐建國，肖海峰，趙 華

(山東科技大學 計算機科學與工程學院，山東 青島 266590)

0 引 言

SVM(support vector machine)算法在處理文本分類問題時有著較好的應用。張華鑫等[1]通過對比實驗發(fā)現(xiàn)在處理短文本時，SVM使用多項式核函數(shù)的分類準確度普遍高于采用KNN(K-nearest neighbor)算法的分類準確率。董放等[2]利用SVM模型提出了一種基于時間序列的新興技術預測方法，通過對文本摘要的分類，預測了技術驅動力新興技術發(fā)展趨勢。上述SVM算法在處理短文本內(nèi)容時有著較好的表現(xiàn)，但是在處理較大規(guī)模文本分類問題時，分類的準確率存在不足。傳統(tǒng)的機器學習算法在處理具有特殊結構的本文時，已經(jīng)不能滿足對準確率的要求。針對以上問題，本文從一個新的解決文本分類問題的角度，綜合考慮文本的特征結構，充分利用多示例學習框架的優(yōu)點，結合支持向量機中的多類分類算法，對具有特殊結構的文本分類問題展開研究，最后通過實驗驗證本文提出算法的有效性。

1 相關研究

多示例學習(multi instance learning，MIL)源于20世紀90年代Dietterich等在研究藥物分子活性(drug activity prediction)檢測問題時提出的一種新的學習方法[3]。多示例學習方法作為機器學習中從監(jiān)督式學習演變出的一種新方法，自提出以來，一直是學者研究的熱點之一[4-6]。在多示例學習框架中，訓練集中的每個正包被定義為一個有標記的對象，負包由沒有標記的示例組成，訓練器對包中的示例進行學習，從而對示例進行預測。將所有正包的示例視為正示例，如果一個正包中的所有示例都被判斷為負，那么則將該包中具有最大函數(shù)決策值的示例標記為正；支持向量機再對這些被標記為正的示例和所有負包中的示例不斷進行訓練和標記，直到訓練集中所有示例的類別標簽不再發(fā)生變化[7]，多示例學習的目標是預測新的包，這些包是事先沒有標記的標簽。

多示例學習方法的應用場景和應用領域非常豐富，突出表現(xiàn)是在目標識別與圖像檢索領域[8]。由于多示例學習能夠基于圖像的局部內(nèi)容，對字塊進行學習，而不是整個圖片，對圖像進行分部處理，將圖像不同的部分作為示例，因此多示例學習能夠有效處理圖片的二義性。文獻[9]利用在線多示例目標跟蹤算法，根據(jù)數(shù)據(jù)的特性在深度圖中提取多尺度特征，利用多示例學習策略將多尺度特征融合；文獻[10]將圖像看作是多示例包，將包中的示例訓練成特征空間，利用訓練的包構造字典，提出基于稀疏表示的分類方法，有效地利用多示例學習框架解決了圖像分類問題。

多示例學習的優(yōu)點是可以通過多示例的方法充分得到目標對象的多特征，而不是對象的單一特征[11]。因此能夠更加精確地描述目標對象的屬性，提高分類的準確性，比如圖像識別、文本分類。現(xiàn)實情況下，我們遇到的許多文本都是有特定結構的，例如科技通報文章、微博數(shù)據(jù)、網(wǎng)頁評論、網(wǎng)絡輿情數(shù)據(jù)等。因此，在文本識別中可以運用多示例學習的框架，將整篇文本作為一個由多個示例組成的包，將文本內(nèi)容分割映射為多個示例，每個文本對應一個分類主題。

基于以上研究基礎，本文將使用多示例學習框架，結合支持向量機算法對采集的新聞文本數(shù)據(jù)集進行分類研究。將每個文本作為一個示例包，每個文本中的標題和正文作為包的兩個示例。將這兩個具有標記的樣本稱為正包，同時將包映射到高維特征空間中，然后構建基于一類分類的多類分類支持向量機算法，利用高斯核函數(shù)訓練分類器，最終實現(xiàn)對實驗數(shù)據(jù)集文本內(nèi)容的自動分類。

2 基于多示例學習框架的文本分類算法

2.1 定義多示例學習

給定集合X表示示例空間，其中的一個數(shù)據(jù)集為 {(x1,y1),…,(xi,yi),…(xn,yn)}，xi={xi1,…,xij,…xi,ni}∈X，n是訓練集中包的個數(shù)，xij∈Rn,j=1,…,li;i=1,…,l， 輸出yi是對xi的類別標記，xi∈{-1,1}，yi∈{-1,1},i=1,…l， 目的是根據(jù)這個規(guī)則建立分類器，從而實現(xiàn)對為標記包的分類。其中xij∈X， 是一個示例， {xij1,…xijl,…xijk} 中xijk是示例xij中的第k個特征值，ni表示的是包Xi中示例的個數(shù)，k表示的是示例中特征值的個數(shù)。如果存在f∈(1,…,ni)， 使得定義的示例xij是一個正示例，那么包Xi就是一個正包，即yi=+1， 否則，yi=-1[12]。通過上述定義可知，多示例分類問題就是通過已經(jīng)標記過的正包和負包，然后構建分類器來預測一個新的包是正包還是負包[4]。圖1表示空間R2中多示例的分類情況，其中的每一個圈表示一個包，“”和“”表示包中的示例；用“”表示的示例視作正包，用“”表示的示例視作負包。需要解決的問題是，預測平面上的集合是正包還是負包。

圖1 多示例學習兩類分類

以圖像分類為例，我們希望可以根據(jù)圖像看見的內(nèi)容了解圖像所屬的目標類。例如，目標類可能是“海灘”，其中的圖像包含“沙子”和“水”。在多示例學習中，此圖像被描述為包X={X1,…,XN} 每個Xi是從圖像中相應的第i個區(qū)域提取的特征向量(稱為示例),N是分割圖像的總區(qū)域(實例)。如果包中包含“沙子”區(qū)域示例和“水”區(qū)域示例，則將包標記為正(“海灘”)，否則為負圖像。

2.2 支持向量機文本分類方法

本文運用支持向量機算法構建分類器對文本進行分類。SVM本質上是基于統(tǒng)計學習理論的機器學習方法，被廣泛應用于函數(shù)估計(回歸)、模式識別(分類)等數(shù)據(jù)挖掘問題，并在很多領域，如數(shù)字識別、人臉圖像識別、時間序列預測等方面得到成功應用。支持向量機算法的基本思想是：通過非線性變化將進入空間中的樣本特征映射到一個高維的特征空間，并在新空間中尋找到最優(yōu)超平面，使得樣本之間的間隔達到最大[13]。面對非線性分類問題時，支持向量機首先是在低維度空間中計算，然后通過選擇合適的核函數(shù)k(xi,yi) 將輸入的數(shù)據(jù)映射到高維空間中，最終原空間中的非線性分類就變成了高維特征空間中的線性可分問題[14]，圖2表示非線性分類時，通過核函數(shù)方法將數(shù)據(jù)映射到高維空間之中。

圖2 核函數(shù)方法將非線性可分數(shù)據(jù)映射到高維空間

2.3 構造多類分類算法

構造多類分類的方法算法的復雜度很高，所以需要找到一種簡單實用的多類分類算法。本文以一類分類算法為基礎建立一種多類分類算法。首先在高維特征空間上對每一類樣本求出它們的超球體中心，然后計算出后續(xù)樣本和超球體中心之間的距離，再根據(jù)它們之間的最小距離來判斷該點所屬的類，算法的具體步驟如下：定義樣本為 {(x1,y1),…,(xl,yl)}?Rn×Y，Y={1,2,…,M}, 其中，n為測試樣本向量的維數(shù)，M為類別數(shù)目。將樣本分為M類，每個類分開寫成： {(x1(s),y1(s)),…,(xl(s),yl(s)),s=1,…,M} 其中， {(xi(s),yi(s)),i=1,…,ls} 代表第s類訓練樣本，l1+…+lM=l。 為了得到包含每類樣本的最小超球體距離，構造下面的二次規(guī)劃

(1)

約束為

si≥0,s=1,…,M,i=1,…,ls

該優(yōu)化問題轉換成對偶形式為

(2)

約束為

同時引入核函數(shù)方法，本文通過核函數(shù)k(xi,xj) 來代替高維特征空間中的內(nèi)積運算。采用高斯核函數(shù)kG， 給定兩個包含多示例的包xi,xj， 則在多示例情況下高斯核函數(shù)可以表示為

(3)

其中，γ是高斯核函數(shù)的參數(shù)，本文采取麥克勞林展開式來確定γ的取值[6]。將多示例包所處的原空間映射到高維特征空間，并對這個多示例包在高維特征空間中做優(yōu)化處理，最終得到核方法下的優(yōu)化方程為

(4)

約束為

最終優(yōu)化為

(5)

式(5)是多類分類問題最終的優(yōu)化方程，需要優(yōu)化的參數(shù)個數(shù)是樣本的總數(shù)l，可以通過調整參數(shù)c的值來抑制噪聲的影響。該優(yōu)化方程的算法計算復雜度受樣本數(shù)量影響較大，而數(shù)據(jù)集的類別數(shù)量對算法計算復雜度影響較小。因此，可以利用基于一類分類的多類分類算法解決多分類問題。

2.4 示例間距離計算方法

對于多示例學習問題的研究，國內(nèi)外學者做出了深入研究，提出了很多優(yōu)秀的算法，例如：多示例核方法、多示例K近鄰算法、多示例圖方法[15]等。

其中，多示例K近鄰算法利用最大或者最小Hausdorff距離搜索鄰近的包來度量示例之間的距離，是一種利用近鄰規(guī)則的多示例學習算法，在應用中取得了比較優(yōu)異的表現(xiàn)。

dmax H(A,B)=max{d(A,B),d(B,A)}

(6)

(7)

式(6)中的d(A,B),d(B,A) 表示距離，分別表示為

(8)

(9)

通過分析，發(fā)現(xiàn)最大Hausdorff距離容易受到噪聲的干擾，受到異常示例的影響非常大，下面通過一個實際例子加以說明。首先設置每個示例D=1， 即示例為標量。假設包A={-2,-3,-4,-5}， 包B={2,3,4,40} 都是由4個示例構成，其中包B中的示例40為一個噪聲數(shù)據(jù)，定義為異常示例。由式(8)、式(9)可知，d(A,B)=max{4,5,6,7}，d(B,A)=max{4,5,6,42}， 根據(jù)式(6)可知dmax H(A,B)=max{7,42} 很突出，B包中的噪聲示例40會對最大Hausdorff距離的產(chǎn)生影響。再根據(jù)式(7)，可知dmin H(A,B)=4， 包A,B之間的最小Hausdorff距離沒有受到噪聲示例的干擾。因此最小Hausdorff距離(minimum Hausdorff distance)對于異常示例并不敏感，可以使用最小Hausdorff距離作為度量多示例包之間的距離。

對于本文處理的文本示例來說，所有的屬性值都是非數(shù)值的，所以不能直接使用最小Hausdorff距離來計算。為了使MIL-SVM算法能夠適用多示例學習框架，就必須給出兩個包之間距離的度量方法，多示例學習中兩個示例之間的距離我們可以通過計算兩個包之間特征向量的距離。一個文本中出現(xiàn)頻率較高的詞能夠從某一方面代表這個文本的主題，但是對于一些“的”、“啊”、“呵”等停用詞可以不作為文本的特征詞考慮。所以，我們選取文本中的高頻詞作為文本的特征詞語來對文本進行表示。

本文使用文本中出現(xiàn)的一系列高頻詞匯組成一個q維特征向量用w=[w1,…,wq]T來表示文本代表的主要內(nèi)容，其中wi(i=1,2,…,q) 是對應的文本中詞匯出現(xiàn)次數(shù)第i高的高頻詞。在本文中，一個包含有n個文本的數(shù)據(jù)集就可以表示為一個含有n個示例的包Bag={[w11,w12,…,w1q],[w21,w22,…,w2q],…,[wn1,wn2,…,wnq]}， 通過這種方式就能夠將文本中的文本特征通過提取高頻詞的方式表示出來。每一個包通過一個q維特征向量來表示，第i維的屬性值是文本中對應的第i高詞頻的詞匯。如果兩個文本之間的內(nèi)容越相近，那么文本中出現(xiàn)相同高頻詞的概率也就越大，因此兩個特征向量之間包含的相同詞匯越多，那么它們之間的距離也就越小，根據(jù)這個啟發(fā)式原則，可以定義以下距離計算方法。

假設兩個示例a=[x1,x2,…,xq]T，b=[y1,y2,…,yq]T是q維的文本特征向量，那么a和b之間的距離為

(10)

其中，δ(x,y)=1當且僅當x=y。

這樣，就可以通過式(10)代替式(7)中計算兩個示例之間的距離，從而可以得到適合多示例學習中示例之間距離計算的方法。MIL-SVM算法使用時，訓練數(shù)據(jù)來自具有標記的“正示例”和“負示例”，將所有正包的示例看作是“正示例”，加上負包中的“負示例”即可訓練出一個SVM分類器。利用SVM分類器重新標記訓練集中的所有包，并對示例進行標記，只有當一個正包中的所有示例都被判定為負，才能夠將這個包中擁有最小距離的示例標記為正。利用被標記為正的示例和負包中的示例不斷標記和訓練，當全部數(shù)據(jù)集中包的示例標簽穩(wěn)定下來，不再發(fā)生改變時，SVM便被重新訓練完畢。

3 實驗分析

3.1 實驗數(shù)據(jù)集

為了檢驗MIL-SVM算法在文本分類領域的有效性，本文采用來自Python程序爬取的語料庫進行實驗分析。數(shù)據(jù)來源于新浪、微博、知乎等知名中文網(wǎng)站的新聞以及評論數(shù)據(jù)，經(jīng)過數(shù)據(jù)預處理，刪去不滿足要求的文本之后，最終數(shù)據(jù)集包括8個分類，每個分類6000條數(shù)據(jù)，訓練集30 000條，測試集18 000條。類別如下：時政、體育、房產(chǎn)、財經(jīng)、旅游、教育、科技、健康，并對數(shù)據(jù)集標記為(U1-U8)。隨機對8個分類中的數(shù)據(jù)進行標記，每個數(shù)據(jù)集中的正示例與反示例分布情況見表1。

文本分詞采用jieba中文分詞工具，通過多進程分詞，對訓練集、測試集進行分詞，特征值提取階段通過詞頻統(tǒng)計工具，將文本中的高頻詞統(tǒng)計出來后構建特征向量。將實驗數(shù)據(jù)集分為訓練集和測試集，通過上述分類算法對訓練集構建模型，然后對測試集進行分類預測。

表1 數(shù)據(jù)集中正例和反例分布情況

3.2 實驗過程及評價指標

本文使用兩種常用的監(jiān)督式學習經(jīng)典文本分類算法與多示例學習MIL-SVM算法進行對比實驗，支持向量機(SVM)算法和KNN算法。SVM算法是一個經(jīng)久不衰的算法，具有高準確率特性，在線性不可分的情況下，只要給定一個合適的核函數(shù)，就可以發(fā)揮出很好的效果；KNN算法思想簡單，既可以用來做分類也可以用來做回歸分析，可用于非線性分類，KNN是一種在線技術，新數(shù)據(jù)可以直接加入數(shù)據(jù)集而不必進行重新訓練。由于這兩種非多示例學習算法不需要運用多示例學習方法，所以將標題和正文視作一個整體。其中SVM算法采用LIBSVM實現(xiàn)，本實驗中核函數(shù)采取高斯核函數(shù)，參數(shù)c=5； KNN算法由Matlab內(nèi)置集成的fitcknn函數(shù)實現(xiàn)。

本文使用能對數(shù)據(jù)集進行充分利用的K-折交叉驗證法驗證數(shù)據(jù)集上算法對文本分類的準確性。該方法的步驟為：①將數(shù)據(jù)分為隨機的k個包；②不重復地從k個包中選一個包當作測試集，剩余的k-1個包作訓練集；③重復步驟②，直到k個包均被選擇1次。這樣經(jīng)過N次循環(huán)驗證，對每次的評價指標數(shù)據(jù)進行平均，得到分類算法的準確性。本文采取常用的10-折交叉驗證法，選取準確率(Precision，P)、召回率(Recall，R)和綜合評價指標(F1-Measure，F(xiàn)1)值作為文本分類的評測指標。其中準確率表示模型對于正樣本的區(qū)分程度，召回率表示模型對負樣本的區(qū)分程度，F(xiàn)值是兩者的平均值。準確率、召回率、F值的計算公式如式(11)-式(13)所示

(11)

(12)

(13)

其中，實驗測試集中包含X個正示例和Y個負示例，正示例中包含能夠被分類器正確分類的Xa個樣本和被分類器錯誤分類的Yb個樣本，負示例中包含被分類器正確分類的正示例的Xa個樣板和錯誤識別的負示例樣本Yb。

3.3 實驗結果與分析

實驗中，由于特征向量中高頻詞的個數(shù)對示例的表征能力有直接的影響，所以，實驗需要在不同的高頻詞個數(shù)下比較3種算法的分類效果。在高頻詞個數(shù)相同的情況下，得到了KNN，SVM，MIL-SVM這3種算法在對應數(shù)據(jù)集上的準確率P、召回率R和綜合評價指標F1值，然后計算出3種評價指標在對應數(shù)據(jù)集上的平均值。如圖3-圖5所示，分別對應高頻詞為5,10,15時的評價指標實驗結果。

圖3 3種分類算法在5維特征向量下的分類比較結果

圖4 3種分類算法在10維特征向量下的分類比較結果

圖5 3種分類算法在15維特征向量下的分類比較結果

從圖3-圖5可以看出，在實驗中選擇的特征向量數(shù)量相同的情況下，多示例學習MIL-SVM算法在數(shù)據(jù)集上的平均準確率明顯好于其它兩種傳統(tǒng)的非多示例學習算法。并且MIL-SVM算法在所有數(shù)據(jù)集上的分類效果都比較平均，沒有出現(xiàn)特別大的評價標準值異常波動的情況，例如SVM算法在5維特征向量下對于數(shù)據(jù)集U1的分類就出現(xiàn)異常波動。如圖6所示，多示例學習MIL-SVM算法的準確率比較平均，沒有出現(xiàn)異常波動的情況，且準確率優(yōu)于其它兩種對比算法的分類準確率。

圖6 KNN，SVM和MIL-SVM不同特征向量個數(shù)下的準確率對比

從召回率角度看，多示例學習MIL-SVM算法在3種不同的特征向量情況下，分類效果比KNN和SVM算法好。從圖3-圖5的數(shù)據(jù)中可以計算出MIL-SVM算法的平均召回率為82.8%，而KNN和SVM算法的平均召回率分別是68.4%和66.9%。從綜合評價指標F1值來看，多示例學習MIL-SVM算法在3種不同的特征向量情況下表現(xiàn)的分類數(shù)據(jù)更加穩(wěn)定。因此，多示例學習MIL-SVM算法相比于實驗中的其它兩種算法有更加優(yōu)越的分類效果。

綜合3項評價指標來分析，采用多示例學習框架的MIL-SVM算法分類的效果明顯優(yōu)于非多示例學習框架KNN和SVM算法。這說明，在使用多示例學習框架的SVM分類算法，對于具有特殊結構文本分類問題能夠提升其分類的準確率。

通過實驗驗證分析，我們可以發(fā)現(xiàn)本文提出的基于多示例學習框架的支持向量機分類算法相對于傳統(tǒng)的機器學習分類算法有比較大的優(yōu)勢。不同于只考慮了一種示例特征結構的傳統(tǒng)機器學習方法，本文提出的方法將實驗數(shù)據(jù)集的特征結構進行充分細致的考慮，作為分類的特征項的示例源于多角度的選擇，因此原始數(shù)據(jù)集的利用率和分類器的分類精度得以顯著提高。同時，本文提出的多示例學習框架算法適用性很好，只要數(shù)據(jù)集有特定的文本結構，并且合理定義包中的示例，就能很好解決很多文本分類問題。但是，我們提出的多示例學習MIL-SVM分類算法在時間復雜度的表現(xiàn)上比實驗中的其它兩種算法差，存在劣勢，需要進一步優(yōu)化模型。

4 結束語

本文提出的基于多示例學習框架的支持向量機文本分類方法，借鑒機器學習領域的多示例學習方法和支持向量機算法。針對數(shù)據(jù)集具有的特殊結構，將每個文本當作一個示例包，文本中的標題和正文視作為示例包的兩個示例，將示例包映射到高維特征空間中，利用高斯核函數(shù)訓練分類器，有效地提高了分類的準確性。實驗結果表明，該算法相較于傳統(tǒng)的KNN算法和SVM算法在分類的準確率上有明顯的提高。在今后的研究中，將繼續(xù)優(yōu)化模型算法的時間復雜度，使其適應海量數(shù)據(jù)的文本分類需求。