一種最大分類間隔SVDD的多類文本分類算法*

羅 琦

(中國西南電子技術(shù)研究所，成都 610036)

1 引言

信息技術(shù)尤其是Internet相關(guān)技術(shù)的發(fā)展使得信息資源呈現(xiàn)出海量的特征，其中大部分信息仍是以文本形式存儲。如何從這些海量數(shù)據(jù)中快速、準(zhǔn)確、全面地提取人們需要的信息是信息檢索的重要課題之一。由此基于內(nèi)容的信息檢索和數(shù)據(jù)挖掘逐漸成為熱點(diǎn)的研究領(lǐng)域。文本分類技術(shù)是信息檢索和文本挖掘的重要基礎(chǔ)，其主要任務(wù)是在預(yù)先給定的類別標(biāo)記集合下，根據(jù)文本內(nèi)容判定它的類別［1］。

作為一種確定文檔所屬類別的情報(bào)分析方法，文本分類目前發(fā)展出貝葉斯分類器(Native Bayes)、決策樹(Decision Tree)、k－近鄰(KNN)、神經(jīng)網(wǎng)絡(luò)(Neural Network)和支持向量機(jī)(SVM)等算法［2］。其中應(yīng)用較多、分類效果相對較好的方法是k－近鄰算法和SVM算法，但k－近鄰算法存在類傾斜現(xiàn)象。SVM分類算法是以結(jié)構(gòu)風(fēng)險(xiǎn)最小化為目標(biāo)，具有很好的泛化能力。相關(guān)研究表明，在文本分類方面相比于其他算法，SVM占有效果和穩(wěn)定性上的優(yōu)勢［3］。但是SVM本質(zhì)上是針對兩分類問題的分類器，不能直接用于多分類問題，而文本分類通常是多類分類問題。要使SVM實(shí)現(xiàn)多分類，通常采用構(gòu)造一系列分類器結(jié)合起來實(shí)現(xiàn)多分類的方法，主要有一對多(one－against－all)和一對一(one－againstone)方法［4］。假設(shè)文本訓(xùn)練集分為k個(gè)類別，一對多方法把第j類看作正類，把其余的k－1類看作負(fù)類，構(gòu)造k個(gè)兩分類SVM子分類器。測試時(shí)，對輸入樣本分別計(jì)算每個(gè)SVM子分類器的判別函數(shù)值，取最大值所對應(yīng)的類別作為輸入樣本的類別。但該方法訓(xùn)練時(shí)正負(fù)類數(shù)據(jù)分布不平衡，導(dǎo)致分類精度降低。一對一方法分別選取兩個(gè)不同類別，構(gòu)成一個(gè)SVM子分類器，需要建立k(k－1)/2個(gè)子分類器，計(jì)算量龐大。

Tax等以SVM為基礎(chǔ)提出了支持向量數(shù)據(jù)描述算法(Support Vector Data Description，SVDD)［5］。和SVM不同的是，SVDD不是尋找一個(gè)超平面而是通過計(jì)算包含一組數(shù)據(jù)的最小超球體邊界來對數(shù)據(jù)的分布范圍進(jìn)行描述。通常位于超球體內(nèi)部的數(shù)據(jù)被分類為目標(biāo)對象，位于超球體邊界的數(shù)據(jù)稱為支持向量，超球體外的則是非目標(biāo)數(shù)據(jù)。由于可以對每一類樣本單獨(dú)使用SVDD，得到各個(gè)類別樣本的超球體，并以此作為分類邊界，因此SVDD可以很容易地?cái)U(kuò)展為處理多分類問題。Hao等借鑒SVDD的思想，構(gòu)造了小超球大間隔的球形支持向量機(jī)用于多類別分類［6］。本文在文獻(xiàn)［6］的基礎(chǔ)上，提出基于多分類SVDD的文本分類算法，并引入應(yīng)用核空間k－近鄰平均距離的重疊區(qū)域樣本的類別判定規(guī)則，通過文本多分類實(shí)驗(yàn)，驗(yàn)證了該算法具有較好的分類效果和效率。

2 文本的表示

文本表示就是將文本轉(zhuǎn)化為在機(jī)器上可以描述和計(jì)算的形式的過程，向量空間模型(Vector Space Model，VSM)是常用的文本表示模型［7］。在該模型中，文本空間被視為一組正交特征向量組成的向量空間，一個(gè)文檔表示為空間中的一個(gè)向量，向量的各維對應(yīng)文檔中的一個(gè)特征項(xiàng)。一般選用文檔中的詞、詞組或短語作為特征項(xiàng)。假設(shè)文本的特征總數(shù)是n，則構(gòu)成一個(gè)n維的向量空間，每篇文檔d被表示為一個(gè) n維的向量 V(d)=(t1，w1(d)，…，tnwn(d))，其中ti為詞條項(xiàng)，wi(d)表示詞條ti在文檔d中的權(quán)值，用于表示在文檔中的重要程度。在計(jì)算權(quán)值wi(d)的方法中，最常用的是TF－IDF計(jì)算方法:

其中，tfi(d)為詞條ti在文檔d中出現(xiàn)的頻率，N為所有文檔的數(shù)目，ni為出現(xiàn)了詞條ti的文檔數(shù)目，M表示特征總數(shù)。

VSM中的文本特征向量的維數(shù)成千上萬，使得分類器計(jì)算代價(jià)過大，影響分類效果，因此需要對文本向量進(jìn)行降維處理。特征選擇是一種常用的降維方法。

特征選擇是從原有的比較大的特征集中，去除一些對分類起很小作用或無作用的特征項(xiàng)，而不損傷其分類精度。它能大幅降低向量空間維數(shù)，提高分類的效率。典型的特征選擇方法包括文檔頻率、信息增益、期望交叉熵、互信息和χ2統(tǒng)計(jì)量等［8］。

3 算法描述

3.1 支持向量描述SVDD

假設(shè)訓(xùn)練集中包含n個(gè)目標(biāo)樣本，X={x1，x2，…，xn}，SVDD的目標(biāo)是尋找一個(gè)體積最小的超球體，使得全部或盡可能多的樣本被包圍在該超球體內(nèi)，而非該類樣本沒有或盡可能少地位于該超球體內(nèi)。為了減少奇異點(diǎn)的影響，使用松弛變量ξi把奇異點(diǎn)排除在超球體的外面。所尋找的超球體用半徑R和球心a來描述，需要解決如下的約束優(yōu)化問題:

其中，參數(shù)C對錯(cuò)分樣本進(jìn)行懲罰，控制了超球體體積和分類誤差之間的折衷。

利用Lagrange算子求解上述優(yōu)化問題，得到其對偶形式為

訓(xùn)練結(jié)束后，給定一個(gè)測試樣本z，它與超球體球心的距離表示為

如果D(z，a)≤R，則判斷測試樣本屬于目標(biāo)類別。

通常情況下，即使排除了偏遠(yuǎn)的樣本點(diǎn)，原始空間中的數(shù)據(jù)也不會成球形分布，所以無法取得一個(gè)較好的描述。這時(shí)可以通過一個(gè)非線性映射p(x)將原始空間的數(shù)據(jù)映射到高維特征空間，在高維空間中尋求目標(biāo)樣本的最小超球體。事實(shí)上，p(x)的顯式構(gòu)造可能未知或很復(fù)雜，但求解過程中卻只需利用顯式的核函數(shù)K簡單計(jì)算高維特征空間中的內(nèi)積，使得復(fù)雜的非線性變換在計(jì)算上可行。核函數(shù)K(x，y)表示高維空間中向量內(nèi)積運(yùn)算，即K(x，y)=(p(x)·p(y))。

常用的核函數(shù)有多項(xiàng)式核函數(shù)

和徑向基核函數(shù)

應(yīng)用核函數(shù)后，式(3)中的對偶式可轉(zhuǎn)換為

在核空間中，測試樣本點(diǎn)z與超球體球心之間的距離表示為

3.2 基于多分類SVDD的文本分類算法

SVDD是典型的一類分類器，能夠?yàn)槊款悢?shù)據(jù)分布提供較好的緊湊描述，訓(xùn)練時(shí)只需要一類樣本，有較快的訓(xùn)練速度。在此基礎(chǔ)之上，可以對數(shù)據(jù)空間中的每一類樣本單獨(dú)構(gòu)造超球體，從而很容易應(yīng)用到多類別分類問題。

給定包含n個(gè)樣本訓(xùn)練集(xi，yi)，…，(xn，yn)，該訓(xùn)練集劃分為L個(gè)類別，其中 yi∈{1，2，…，L}。設(shè)nj表示第j類中樣本的個(gè)數(shù)，有n=n1+n2+…nL。為訓(xùn)練數(shù)據(jù)中的每一類數(shù)據(jù)建立一個(gè)包圍該類所有訓(xùn)練樣本的最小超球，每個(gè)超球用半徑Rj和球心aj來定義，需要解決如下的約束優(yōu)化問題［6］:

其中，dj為調(diào)節(jié)分類間隔的因子。該優(yōu)化問題尋求盡可能減小包含每個(gè)目標(biāo)類的超球體，獲得對目標(biāo)數(shù)據(jù)的更緊湊的描述，并且盡可能增大目標(biāo)類和非目標(biāo)類樣本之間的間隔，通過最大化分類間隔來增強(qiáng)泛化能力。

對于給定的文本集合，在訓(xùn)練階段，通過SVDD多分類算法，構(gòu)造包圍訓(xùn)練樣本的分隔面，獲得L個(gè)超球Si(i=1，2，…，L)，其中L為總的類別數(shù)。理想情況下，任意兩個(gè)超球都相互獨(dú)立，每一個(gè)新的樣本點(diǎn)都能被正確分類。但是實(shí)際情況中會出現(xiàn)超球重疊的情況，即一個(gè)測試樣本同時(shí)屬于兩個(gè)或多個(gè)超球。如果測試樣本落入重疊區(qū)域，如何判斷其屬于哪個(gè)類就是一個(gè)非常關(guān)鍵的問題。

本文引入基于核空間k近鄰平均距離的判別準(zhǔn)則。在核空間中，測試樣本z到其k個(gè)最近鄰樣本的平均距離表示為

其中，xi(i=1，2，…，k)表示z的k個(gè)最近鄰。樣本z的k最近鄰平均距離表示z相對于其周圍k個(gè)最近鄰樣本在空間分布上的密集程度。Dk(z)越小，表示z越靠近k鄰域內(nèi)的近鄰;否則，表示越遠(yuǎn)離。

給定一個(gè)測試文本的樣本，判斷其所屬類別的步驟如下:

(1)給定一個(gè)新的測試樣本z，根據(jù)它與第i個(gè)超球Si的球心ai的距離與超球半徑Ri，計(jì)算判定函數(shù)

如果只有一個(gè)fi(z)＞0，則樣本位于單獨(dú)一個(gè)超球類內(nèi)部，屬于該超球?qū)?yīng)的類;

(2)如果有不止一個(gè)fi(z)＞0，表明樣本被多個(gè)超球體包圍，位于超球重疊的區(qū)域。假設(shè)z位于m個(gè)超球重疊的區(qū)域內(nèi)，則逐個(gè)選取其中每個(gè)超球體，在超球內(nèi)部包含的訓(xùn)練樣本中，分別尋找測試樣本的k個(gè)最近鄰，計(jì)算k近鄰平均距離。判定樣本所屬類別的判定函數(shù)為

則樣本屬于第i類;

(3)如果所有的fi(z)＜0，表明樣本位于所有超球體的區(qū)域之外，則依然應(yīng)用式(10)判斷樣本歸屬該值最小的類。

4 實(shí)驗(yàn)與結(jié)果分析

采用文本分類的標(biāo)準(zhǔn)測試數(shù)據(jù)集 Reuters－21578作為實(shí)驗(yàn)數(shù)據(jù)，其中包含了路透社從1987年2～10月收集的新聞，共有21578個(gè)文檔，被分為135個(gè)子類別。本文使用該數(shù)據(jù)集中文檔最多的10個(gè)類別和其中的4500篇文檔進(jìn)行實(shí)驗(yàn)。將文本經(jīng)過預(yù)處理后形成詞空間向量，特征降維采用信息增益的方法，采用TF_IDF公式來計(jì)算向量中每個(gè)詞的權(quán)重。

對分類性能的評估，采用通用的分類性能評價(jià)標(biāo)準(zhǔn)，即準(zhǔn)確率P(Precision)和召回率R(Recall)對分類的效果進(jìn)行比較［9］。假設(shè)對于訓(xùn)練集中第i類樣本而言，ni表示實(shí)際屬于類i的樣本數(shù)，pi表示分類器預(yù)測為類i的樣本數(shù)，ci表示被正確分到類i的樣本數(shù)，則準(zhǔn)確率P定義為P=ci/pi，召回率R定義為R=ci/ni。

將本文提出的算法與SVM一對一多分類算法、SVM一對多多分類算法進(jìn)行了對比實(shí)驗(yàn)。實(shí)驗(yàn)采用徑向基核函數(shù)和5重交叉驗(yàn)證(5－fold cross validation)方法，即將數(shù)據(jù)集隨機(jī)劃分成近似相等的5份，進(jìn)行5次訓(xùn)練和測試，每次取其中一份作為測試集，其他4份作為訓(xùn)練集。表1給出了3種分類算法在Reuters數(shù)據(jù)集上的平均準(zhǔn)確率、平均召回率、訓(xùn)練時(shí)間和測試時(shí)間。

表1 不同算法的性能對比Table 1 The performance evaluation of different algorithms

實(shí)驗(yàn)數(shù)據(jù)表明，對于多類別文本的分類，本文提出的基于多類SVDD的文本分類算法在訓(xùn)練效率和分類精度上比傳統(tǒng)的SVM多類分類算法有較大提高，取得了較好的效果。

基于多類SVDD的算法針對每類樣本構(gòu)造最小包圍球，對每類樣本僅訓(xùn)練一次，因此訓(xùn)練效率高。而且該算法盡可能減小包圍每個(gè)類的超球體，盡量增大類與類之間的間隔，增強(qiáng)了泛化能力，因此有較好的分類效果。

5 結(jié)束語

文本分類通常是多類分類問題，傳統(tǒng)的SVM算法是針對兩分類問題，不能應(yīng)用于多分類的文本分類問題。相關(guān)研究表明，SVM在文本分類方面相比于其他算法占有效果和穩(wěn)定性上的優(yōu)勢，但是SVM本質(zhì)上是針對兩分類問題的分類器，不能直接用于多分類問題。SVDD是典型的一類分類器，能夠?yàn)槊款悢?shù)據(jù)分布提供較好的緊湊描述，訓(xùn)練時(shí)只需要一類樣本，有較快的訓(xùn)練速度。本文提出了一種最大分類間隔SVDD的多類別文本分類算法，它結(jié)合多分類SVDD和超球體重疊區(qū)樣本分類判別規(guī)則實(shí)現(xiàn)文本分類，用支持向量描述訓(xùn)練求得包圍各類樣本的最小超球體，并使得分類間隔最大化，在測試階段，引入基于核空間k－近鄰平均距離的判別準(zhǔn)則，判斷樣本所屬類別。實(shí)驗(yàn)結(jié)果表明，該算法與傳統(tǒng)算法相比，具有更好的泛化能力和時(shí)間性能，是一種高效的文本分類算法。

［1］Sebastiani F.Machine learning in automated text categorization［J］.ACM Computing Surveys，2002，34(1):1－47.

［2］Lewis D D，Yang Y，Rose T，et al.Rcv1:A New Benchmark Collection for Text Categorization Research［J］.Journal of Machine Learning Research，2004(5):361－397.

［3］Joachims T.Text categorization with support vector machines:Learning with many relevant features［M］//Proceedings of the 10th European Conference on Machine Learning.New York:Springer－Verlag，1998:137－142.

［4］鄧乃揚(yáng)，田英杰.支持向量機(jī)－理論、算法與拓展［M］.北京:科學(xué)出版社，2009.DENG Nai－yang，TIAN Ying－jie.Support Vector Machine－Theory、Algorithm and Expandedness［M］.Beijing:Science Press，2009.(in Chinese)

［5］Tax D M，Duin R P W.Support vector data description［J］.Machine Learning，2004，54(1):45－66.

［6］Hao P Y，Chiang J H，Lin Y H.A new maximal margin spherical structured multi－class support vector machine［J］.Applied Intelligence，2009，30(2):98－111.

［7］Salton G，Wang A，Yang C S.A vector space model for automatic indexing［J］.Communication of the ACM，1975，18(11):613－620.

［8］Manevitz L，Yousef M.One class SVMs for document classification［J］.Journal of Machine Learning Research，2002(2):139－154.

［9］Bennett P N，Dumais S T，Horvitz E.The combination of text classifiers using reliability indicators［J］.Information Retrieval，2005，8(1):67－100.