蔣宗禮,徐學(xué)可

(北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,北京 100124)

一種基于集成學(xué)習(xí)與類指示器的文本分類方法

蔣宗禮,徐學(xué)可

(北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,北京 100124)

提出了一種基于集成學(xué)習(xí)機(jī)制與類指示器的文本分類方法.該方法利用 AdaBoost.MH算法框架,在每一輪次中,自適應(yīng)地計(jì)算類指示度,通過(guò)加權(quán)組合所有成員類指示度,獲得對(duì)理想類指示度的一種逼近.利用最終的類指示度所得到的分類器不僅簡(jiǎn)單、易于更新,而且泛化能力強(qiáng).在標(biāo)準(zhǔn)語(yǔ)料集TanCorp-12上的實(shí)驗(yàn)表明,該方法適用于對(duì)分類效率要求較高的實(shí)時(shí)應(yīng)用,同時(shí)可以利用集成學(xué)習(xí)進(jìn)行某些知識(shí)的精確學(xué)習(xí),并將這些知識(shí)用于弱分類器,從而實(shí)現(xiàn)簡(jiǎn)單高效的分類.

機(jī)器學(xué)習(xí);集成學(xué)習(xí);AdaBoost.MH;文本分類;類指示器

大規(guī)模在線文本分類、文本信息檢索、過(guò)濾等實(shí)時(shí)性要求強(qiáng)的應(yīng)用往往需要泛化能力很強(qiáng),簡(jiǎn)單、快速、高效、易于更新的文本分類方法,目前很少有符合要求的.支持向量機(jī)(supportvectormachine,SVM)雖然具備較高的泛化能力,但訓(xùn)練與分類的過(guò)程過(guò)于復(fù)雜,而基于向量空間模型(vector space model,VSM)[3]相似度的分類器雖然簡(jiǎn)單,但分類性能往往達(dá)不到實(shí)際需求.雖然集成學(xué)習(xí)技術(shù)可以將弱分類器提升為泛化能力很強(qiáng)的強(qiáng)分類器,但大大提高了計(jì)算復(fù)雜性.作者首先將文本特征視為類指示器,相應(yīng)定義了類指示度函數(shù)并提出一種基于類指示器的文本分類方法,然后利用集成學(xué)習(xí)的方法,獲取更精確的類指示度函數(shù),在此基礎(chǔ)上構(gòu)造等價(jià)于集成分類器的分類系統(tǒng),使其既具備集成分類器泛化能力高的特點(diǎn),又保持簡(jiǎn)單、快速易于更新的優(yōu)點(diǎn).

1 集成學(xué)習(xí)相關(guān)介紹

集成分類器可分為使用同類型單分類器的集成分類器和使用不同類型單分類器的集成分類器.使用同類型單分類器的集成分類器根據(jù)成員分類器生成方式的不同,大致分為 2類.一類以 AdaBoost[4]為代表,在這一類算法中,成員分類器順序生成和執(zhí)行,一個(gè)分類器的結(jié)果對(duì)下一個(gè)分類器產(chǎn)生影響.另一類以 Bagging[5]為代表,成員分類器可以并行生成和執(zhí)行,算法用可重復(fù)取樣技術(shù)(bootstrap samp ling)生成與原來(lái)樣本集中的樣本個(gè)數(shù)相同的新樣本集.

Boosting、AdaBoost與 AdaBoost.MH是一類集成學(xué)習(xí)器.Boosting包括了一系列算法,其基本策略是將一個(gè)比隨機(jī)猜測(cè)略好的弱學(xué)習(xí)算法提升為強(qiáng)學(xué)習(xí)算法,不必直接去找通常情況下很難獲得的強(qiáng)學(xué)習(xí)算法.Adaboost[4]是其中最具代表性的一種,AdaBoost將樣本集{(x1,y1),…,(xm,ym)}作為訓(xùn)練數(shù)據(jù),其中 xi是問(wèn)題空間 X中的實(shí)例,yi∈{-1,+1}是 xi的類別標(biāo)簽.AdaBoost在訓(xùn)練實(shí)例空間 X上維護(hù)一個(gè)權(quán)重分布,在初始化時(shí)對(duì)每個(gè)樣本賦相等的權(quán)重 1/m,然后用樣本集對(duì)成員分類器進(jìn)行訓(xùn)練,每次訓(xùn)練后,對(duì)訓(xùn)練失敗的樣本賦以較大的權(quán)重,以便在后面對(duì)比較難的樣本集中學(xué)習(xí),從而得到一個(gè)預(yù)測(cè)函數(shù)序列 h1,…,hT,其中 hj也有一定的權(quán)重.預(yù)測(cè)效果好的預(yù)測(cè)函數(shù)權(quán)重較大,反之較小.最終的預(yù)測(cè)函數(shù) h采用有權(quán)重的投票方式對(duì)新實(shí)例進(jìn)行類屬判別.

AdaBoost.MH[2]將成員分類器定義成 h∶X×Y→R形式,并在 X×Y上維持一個(gè) |X|×|Y|的權(quán)重分布.推廣 AdaBoost使它能處理多類多標(biāo)簽分類問(wèn)題,實(shí)際上是將 X×Y的成員作為推廣的實(shí)例形式,在推廣實(shí)例(xi,yi)上,成員分類器的輸出是對(duì)訓(xùn)練實(shí)例 xi屬于 yi類的支持度的判斷.若輸出值大于 0,表示支持xi屬于 yi類;若輸出值小于 0表示支持 xi不屬于 yi類.輸出值的絕對(duì)值越大則可信度越高.它在推廣實(shí)例集上維護(hù)權(quán)重分布,這樣就將多類多標(biāo)簽化為二類單標(biāo)簽問(wèn)題.AdaBoost.MH在 AdaBoost框架下運(yùn)行,可以看成 AdaBoost的推廣形式,AdaBoost中的一些結(jié)論也適用于 AdaBoost.MH.

Schapire等[2]將基于決策樹(shù)樁 (decision stump)的 AdaBoost.MH集成算法用于文本分類系統(tǒng)BoosTexte.它的成員分類器根據(jù)某個(gè)單詞出現(xiàn)與否給當(dāng)前文本賦予一實(shí)數(shù)值,用于進(jìn)行文本的類別可信度預(yù)測(cè).文獻(xiàn)[6]對(duì)此做了改進(jìn),將詞頻分類器集成應(yīng)用于文本分類.

2 基于類指示器的文本分類方法

進(jìn)行文本分類往往需要抽取一系列特征來(lái)表示文本.這些特征往往跟類別存在一定關(guān)聯(lián),起著類指示器作用.設(shè)文檔集 D,特征集 F,類別標(biāo)簽集 C,定義類指示度函數(shù) I∶F×C→(-1,1)用于度量這種關(guān)聯(lián),I(f,c)＞0時(shí)表示特征 f與類 c正關(guān)聯(lián),即表示特征 f在文檔 d中的出現(xiàn)對(duì) d為 c類起支持作用;反之特征 f與類 c負(fù)關(guān)聯(lián),表示特征 f在文檔 d中的出現(xiàn)對(duì) d為 c類起反對(duì)作用.分類器 h∶D×C→R,h(d,c)為文檔 d包含的所有特征的關(guān)于類 c的指示度的加權(quán)和,表示 d為 c類的可信度,取可信度最高的 c作為d的類標(biāo)簽.定義權(quán)重函數(shù),其值由特征在文檔中的重要程度及特征本身的類區(qū)分度決定 w∶D×F→[0,1],w(d,f)表示文本 d關(guān)于特征 f的權(quán)重.值得說(shuō)明的是本文采用詞作為其特征,實(shí)際上,特征可以是關(guān)鍵短語(yǔ)、n-gram、詞組、領(lǐng)域詞典中的領(lǐng)域關(guān)聯(lián)詞等,他們具備一定類指示作用.

算法 1 基于類指示器的分類方法(category indicator based method,CIM)

假設(shè)?〈f,c〉∈F×C,I(f,c)已經(jīng)事先計(jì)算

初始化:h(d,c)=0

輸入:d∈D

顯然這是一種相當(dāng)簡(jiǎn)單、快速、高效的分類方法,同時(shí)也易于更新,只要提取對(duì)新特征的類指示度,并添加到特征庫(kù)中,便可完成對(duì)分類模型的更新,這在網(wǎng)絡(luò)時(shí)代中新詞不斷出現(xiàn)的情況下尤其重要.但該方法中類指示度的學(xué)習(xí)過(guò)于依賴訓(xùn)練集的規(guī)模與質(zhì)量,可能難以有效處理新例,泛化性能低.本文期望利用集成學(xué)習(xí)的方法,獲取更精確的類指示度,在此基礎(chǔ)上構(gòu)造等價(jià)于集成分類器的分類系統(tǒng),使其既具備集成分類器泛化能力高的特點(diǎn),又能保持簡(jiǎn)單、快速易于更新的優(yōu)點(diǎn).

3 算法框架

本文的工作以 AdaBoost.MH作為集成學(xué)習(xí)的框架,不同于 Schapire,這里的成員分類器采用綜合考慮文本所有特征的基于類指示器的方法,來(lái)獲得更精確的類指示度函數(shù),并以此構(gòu)造最終的分類器,與一般集成分類器相比,它不需要在執(zhí)行過(guò)程中對(duì)各成員分類器的加權(quán)融合.基于 AdaBoost.MH框架,隨著權(quán)重分布的自適應(yīng)更新,每一輪的類指示度函數(shù)的學(xué)習(xí)重點(diǎn)考慮那些權(quán)重較大的文檔,相應(yīng)的分類器更多體現(xiàn)這些樣本的特性,各輪的類指示度函數(shù)及相應(yīng)分類器側(cè)重不同訓(xùn)練空間的特性,具備一定的差異性,將各輪的類指示度函數(shù)加權(quán)融合,得到的分類器具有較高的穩(wěn)定性與泛化能力.

3.1 主要思路

3.2 算法

算法 2 基于集成學(xué)習(xí)的 CIM

for t=1,…,T;T為事先確定的迭代次數(shù)

1)基于權(quán)重分布 Wt(di,cj)(i=1,…,g,j=1,…,m)學(xué)習(xí)類指示度函數(shù),It∶F×C→(-1,1)

2)基于類指示度函數(shù),得到成員分類器 ht∶D×C→R

3)評(píng)估成員分類器 ht

若 cj∈ Ci返回 Ci[cj]=1否則 Ci[cj]=-1

4)更新權(quán)重分布

因此,這 2種分類器是等價(jià)的,而利用 h分類時(shí)需要存儲(chǔ) T個(gè)分類模型,分類時(shí)需用每個(gè)成員分類器進(jìn)行分類并對(duì)其結(jié)果加權(quán)融合,時(shí)間與空間開(kāi)銷大,利用 h′分類時(shí),只需存儲(chǔ)一個(gè)分類模型(特征的類指示度可以事先計(jì)算并存儲(chǔ)),進(jìn)行一次分類過(guò)程,時(shí)間與空間開(kāi)銷大為減少,同時(shí)具備集成分類器泛化性能高的優(yōu)點(diǎn).

3.3 權(quán)重函數(shù)及類指示度函數(shù)

3.3.1 權(quán)重函數(shù)

在向量空間模型(vector space model,VSM)[3]中,用向量表示文檔,它的每一維對(duì)應(yīng)于文檔的一個(gè)特征項(xiàng),特征項(xiàng)的權(quán)重一般與特征項(xiàng)在文檔中的重要程度以及特征項(xiàng)的類區(qū)分能力有關(guān),一般采用 TF-IDF方法計(jì)算,該方法簡(jiǎn)單地認(rèn)為文本頻數(shù)少的特征項(xiàng)重要顯然過(guò)于武斷.如果以特征選擇中的評(píng)估函數(shù)代替 IDF函數(shù),對(duì)特征項(xiàng)進(jìn)行權(quán)值調(diào)整,就有希望得到高質(zhì)量的向量空間法[7],本文采用互信息(mutual information,MI),以文檔 d改進(jìn)的 VSM中表示特征 f的權(quán)重作為 w(f,d)的值

式中,tf(fi,d)定義為 fi在 d中出現(xiàn)頻率;m(fi)為 fi的互信息評(píng)估函數(shù)值;f1,…,fn為 d包含的特征.另外,本文的特征選擇也采用互信息.

3.3.2 類指示度函數(shù)

方法1

該方法受特征選擇中的互信息方法啟發(fā),設(shè)

式中,Pr(f)表示特征 f在訓(xùn)練文本集合中出現(xiàn)的概率;Pr(f|c)表示在 c類的文本中 f出現(xiàn)的條件概率,當(dāng)Pr(f|c)＞Pr(f)時(shí) Pr(f|c)＞0,表示特征 f與類別 c正關(guān)聯(lián),反之表示負(fù)關(guān)聯(lián).采用比值的方式可以比較純粹的學(xué)習(xí)特征的類關(guān)聯(lián)性,而與特征的頻度無(wú)關(guān).

類指示度函數(shù)為

式(4)將 m(f,c)映射到(-1,1),避免 m(f,c)值之間的過(guò)大差異,防止個(gè)別特征對(duì)分類結(jié)果影響過(guò)大,保證分類器的穩(wěn)定性.

在 AdaBoost.MH每一輪次中,都要根據(jù)新的權(quán)重分布,重新計(jì)算 Pf(f|c)與 Pr(f),從而實(shí)現(xiàn)類指示度的自適應(yīng)調(diào)整.

式中,Wt表示第 t輪次的權(quán)重分布;n(d,f)為 f在文檔 d中出現(xiàn)次數(shù).

方法2

文獻(xiàn)[2]中的決策樹(shù)樁分類器按一定標(biāo)準(zhǔn)選擇某個(gè)詞,分類器以該詞的出現(xiàn)與否給當(dāng)前文本賦予實(shí)數(shù)值,實(shí)現(xiàn)文本的判別,受其賦值公式啟發(fā),設(shè)計(jì)了類指示度函數(shù)

設(shè) Df={d|d∈ D,f∈ d},令

式中,Cd表示文檔 d的類標(biāo)簽集;(f)表示子集 Df中標(biāo)記為 c類的文檔權(quán)重之和(f)表示子集 Df中不被標(biāo)記為 c類的文檔權(quán)重之和;Wc為在權(quán)重分布 W基礎(chǔ)上調(diào)整所得,滿足,其中表明 c類文檔的權(quán)重和與其他文檔相同.可以對(duì) c類文檔進(jìn)行如下調(diào)整

3.4 分類的時(shí)間復(fù)雜度

該方法利用特征類指示度構(gòu)造最終的分類器,與集成分類器相比,它不需要在分類過(guò)程中對(duì)各成員分類器的加權(quán)融合.

總的分類過(guò)程步驟為:1)檢索到每個(gè)文檔特征相應(yīng)的類指示度;2)對(duì)每個(gè)類別把所有特征關(guān)于該類的指示度加權(quán)和作為文檔為該類的可信度;3)取可信度的類作為文檔的類標(biāo)簽.利用 Trie樹(shù)等高效的檢索數(shù)據(jù)結(jié)構(gòu),可以在常數(shù)時(shí)間找到某特征的指示度,因此步驟 1)時(shí)間復(fù)雜度為 O(|Fd|)(Fd為文檔 d的特征集),總時(shí)間復(fù)雜度為 O(|Fd|×|C|).考慮類別數(shù)固定,總時(shí)間復(fù)雜度可為 O(|Fd|),表明這是一種線性分類器,適用于在線分類.

3.5 算法的進(jìn)一步改進(jìn)

值得注意的是,Boosting和 Bagging的迭代輪次數(shù)并非越多越好,學(xué)習(xí)系統(tǒng)性能的改善主要發(fā)生在最初的若干輪次中.Schapire和 Singer指出,迭代次數(shù)過(guò)多,AdaBoost.MH有可能發(fā)生過(guò)適應(yīng)[8].實(shí)驗(yàn)過(guò)程中也發(fā)現(xiàn)文本的方法迭代次數(shù)較少時(shí),性能提升明顯,隨著迭代次數(shù)進(jìn)一步增加,性能反而下降.通?？梢詷?gòu)建驗(yàn)證數(shù)據(jù)集,取驗(yàn)證數(shù)據(jù)集性能最優(yōu)的迭代次數(shù)作為最終參數(shù).

這是由于 AdaBoost算法存在類權(quán)重分布扭曲的現(xiàn)象,導(dǎo)致對(duì)個(gè)別類的過(guò)度重視以及對(duì)其他若干類的偏見(jiàn),生成的預(yù)測(cè)規(guī)則在測(cè)試集上的分類錯(cuò)誤急劇增加,發(fā)生退化現(xiàn)象[9].本文的訓(xùn)練過(guò)程中也出現(xiàn)了該現(xiàn)象,作者對(duì) AdaBoost.MH進(jìn)行改進(jìn),在一定程度上緩解了該問(wèn)題,方法是經(jīng)過(guò)若干輪次迭代后調(diào)整權(quán)重分布,然后對(duì)分布進(jìn)行歸一化.調(diào)整公式為

4 實(shí)驗(yàn)和討論

實(shí)驗(yàn)采用 TanCorp-12語(yǔ)料集[10-11].該語(yǔ)料包含 12類,共有 14 150篇文檔.12類分別為財(cái)經(jīng)、地域、電腦 、房產(chǎn) 、教育 、科技 、汽車 、人才 、體育 、衛(wèi)生 、藝術(shù)與娛樂(lè) .

作者利用經(jīng)典集成學(xué)習(xí)技術(shù),目標(biāo)是獲取既有較高分類性能又有較高分類效率的文本分類方法.首先,將本文的方法跟目前主流分類方法做性能比較.作者用精度(precision)考查分類器在各個(gè)類別上的性能,并用微 F1值(Micro-F1)考查綜合性能[12].將本文方法與常見(jiàn)的中心法(centroid)[13],Rocchio法[14],K-最近鄰法 (k-nearest neighbors,KNN)[15],樸素貝葉斯法 (na?ve bayes,NB)[16],支持向量機(jī)法(supportvector machine,SVM)[17],決策樹(shù)法(decision tree,DT)(具體采用 SPRINT決策樹(shù)算法[18])等進(jìn)行比較.其中 KNN方法參數(shù) K的取值為 15,SVM方法采用開(kāi)源工具 LibSVM[19],核函數(shù)采用 linear kernel,其他參數(shù)取默認(rèn)值.將采用方法 1作為類指示度計(jì)算方法的分類方法記為 CIM1,采用方法 2的記為CIM2,把整個(gè)語(yǔ)料隨機(jī)分成 5份,然后取其中的 2份進(jìn)行訓(xùn)練,剩余取1份作測(cè)試.采用 MI方法進(jìn)行特征選擇,具體的評(píng)估函數(shù)為

式中,Pr(f)表示特征 f在訓(xùn)練文本集合中出現(xiàn)的概率;Pf(f|c)表示在 c類的文本中 f出現(xiàn)的條件概率,取詞頻超過(guò) 15的前 5 000個(gè)詞作為候選特征.CIM 1與 CIM 2的迭代次數(shù)為 100.

從結(jié)果看出 CIM1,CIM 2都表現(xiàn)出較高的性能,其中 CIM1的 Micro-F1指標(biāo)僅次于 SVM和 Rocchio,而CIM2甚至接近目前公認(rèn)文本分類性能較好的 SVM,見(jiàn)表 1.此外 CIM2方法性能好于 CIM 1,是本文推薦的方法.

表 1 本文方法與經(jīng)典文本分類方法性能比較Table 1 The com parison of the p roposed methods and traditionalmethods

CIM2方法性能略低于 SVM,但該方法的最大優(yōu)勢(shì)在于分類效率,是一種線性分類器,適用于在線分類.3.4節(jié)給出其算法時(shí)間復(fù)雜度分析,此外還記錄了 CIM 2與 SVM算法測(cè)試時(shí)間(這里時(shí)間開(kāi)銷為分類過(guò)程開(kāi)銷,不包括算法無(wú)關(guān)的文本預(yù)處理時(shí)間,實(shí)驗(yàn)機(jī)器配置為 Pentium-4,2.3GHz CPU及 1 024M內(nèi)存的機(jī)器上,開(kāi)發(fā)環(huán)境為 Java JDK1.6)分別為 78和 116032ms,可以明顯看出 CIM2時(shí)間開(kāi)銷遠(yuǎn)小于 SVM.此外,本文的方法僅是一種框架性方法,其中類指示度函數(shù)的計(jì)算方法是開(kāi)放,選取更合理的類指示度函數(shù)及權(quán)重函數(shù)還可以進(jìn)一步提升分類性能.

基于改進(jìn)的 AdaBoost.MH的 CIM2,記為 CIM2-Adv,與 CIM2方法相比,CIM2-Adv每經(jīng)過(guò) 40輪次迭代后用式(8)調(diào)整權(quán)重分布.圖 1給出了 CIM2-Adv與 CIM2方法取不同迭代次數(shù) T時(shí) Micro-F1指標(biāo)變化情況.

從圖 1可以發(fā)現(xiàn):1)迭代次數(shù)較少時(shí),CIM2-Adv性能不如 CIM2,表明原有的權(quán)重自適應(yīng)更新機(jī)制更加有效,式(8)在一定程度上破壞了原有的Boosting機(jī)制,導(dǎo)致性能不理想;2)隨著迭代次數(shù)增加,CIM2出現(xiàn)性能退化現(xiàn)象,而 CIM2-Adv性能依然保持上升趨勢(shì),最終 CIM 2-Adv的性能超過(guò) CIM2最佳性能,表明本文提出的方法在一定程度上緩解了經(jīng)典方法權(quán)重扭曲問(wèn)題.

圖1 CIM 2-Adv與 CIM 2方法 Micro-F1指標(biāo)依迭代次數(shù) T變化Fig.1 The Micro-F1 values of CIM 2.Adv and CIM 2 with different iteration count T

5 結(jié)束語(yǔ)

集成學(xué)習(xí)的動(dòng)機(jī)就是將弱分類器提升為高泛化性能的強(qiáng)分類器,但大大增加了計(jì)算復(fù)雜性.為了解決該矛盾,本文提出基于集成學(xué)習(xí)機(jī)制與類指示器的文本分類方法.該方法利用 AdaBoost.MH算法框架,在每一輪次中,自適應(yīng)地計(jì)算類指示度.通過(guò)加權(quán)組合所有成員類指示度,獲得對(duì)理想類指示度的一種逼近.基于最終的類指示度,得到的分類器不僅簡(jiǎn)單易于更新,同時(shí)也獲得了集成分類器泛化能力強(qiáng)的優(yōu)點(diǎn).考慮到它的簡(jiǎn)單性,適用于對(duì)分類效率要求較高的實(shí)時(shí)應(yīng)用.針對(duì) AdaBoost權(quán)重分布扭曲現(xiàn)象本文對(duì) AdaBoost.MH進(jìn)行改進(jìn),取得初步效果.結(jié)果也表明,利用集成學(xué)習(xí)進(jìn)行某些知識(shí)的精確學(xué)習(xí),并將這些知識(shí)應(yīng)用于弱分類器,可以獲得簡(jiǎn)單高效的分類模型.本文的方法是僅僅一種框架性方法,類指示度函數(shù)的定義是開(kāi)放,如何定義更加合理的類指示度函數(shù)是進(jìn)一步研究的內(nèi)容.

[1]DIETTERICHL TG.Machine learning research:four current directions[J].AIMagazine,1997,18(4):97-136.

[2]SCHAPIRE R,SINGER Y.BoosTexter:a boosting based system for text categorization[J].Machine Learning,2000,39(203):135-168.

[3]SALTON G,WONG A,YANG C.A vector spacemodel for automatic indexing[J].Commu of ACM,1995,18:613-620.

[4]FREUND Y,SCHAPIRE R E.A decision-theoretic generalization of on-line learning and an app lication to boosting[J].Journalof Computer and System Sciences,1997,55(1):119-139.

[5]BREIMAN L.Bagging p redictors[J].Machine Learning,1996,24(2):123-140.

[6]姜遠(yuǎn),周志華.基于詞頻分類器集成的文本分類方法[J].計(jì)算機(jī)研究與發(fā)展,2006,43(10):1681-1687.JIANG Yuan,ZHOU Zhi-hua.A text classification method based on term frequency classifier ensemb le[J].Journal of Computer Research and Development,2006,43(10):1681-1687.(in Chinese)

[7]FRANCA D,FABRIZIO S.Supervised term weighting for automated text categorization[C]∥Proceedings of the 2003 ACM Symposium on Applied Computing.Melbourne,Florida:ACM Press,2003:784-788.

[8]SCHAPIRE RE,SINGER Y.Improved boosting algorithms using confidence-rated predictions[J].Machine Learning,1999,38:297-336.

[9]GUINLAN J R.Bagging,boosting,and C4.5[C]∥Proceedings of the Thirteenth National Conference on Artificial Intelligence.Portland,Oregon:AAAI Press and the MIT Press,1996:725-730.

[10]譚松波,王月粉.中文文本分類語(yǔ)料庫(kù)-TanCorpV 1.0[DB/OL].http:∥www.searchforum.org.cn/tansongbo/corpus1.php TANSong-bo,WANGYue-fen.A corpus for Chinese text categorization-TanCorpV1.0[DB/OL].http:∥www.searchforum.org.cn/tansongbo/corpus1.php(in Chinese)

[11]TAN Song-bo.A novel refinement approach for text categorization[C]∥ACM CIKM 2005.Bremen,Germany:ACM Press,2005:469-476.

[12]SEBASTIAN F.Machine learning in automated text categorization[J].ACM Computing Surveys,2002,34(1):1-47.

[13]HAN E,KARYPISG.Centroid-based document classification analysis＆ experimental result[C]∥PKDD 2000.Lyon,France:Springer Berlin/Heidelberg,2000:116-123.

[14]JOACHIMS T.A probabilistic analysis of the rocchio algorithm with TFIDF for text categorization[C]∥Proceedings of International Conference on Machine Learning(ICML).Nashville,Tennessee,USA:Morgan Kau fmann Publishers Inc,1997:143-151.

[15]YANG Y,LIU X.A re-examination of text categorizationmethods[C]∥Proceedings of ACM SIGIR Conference on Research and Development in In formation Retrieval(SIGIR'99).Berkley,USA:ACM Press,1999:42-49.

[16]MLADENICD,GROBELNIK M.Word sequences as features in text-learning[. C]∥Proceedings of ERK-98,the Seventh Electrotechnical and Computer Science Con ference.Ljubljana,Slovenia:IEEE Press,1998:145-148.

[17]JOACHIMST.Text categorization with support vector machines:learning with any relevant features[C]∥Proceedings of CML-98,10th European Conference on Machine Learning.Chemnitz,Germany:Springer Berlin/Heidelberg,1998:137-142.

[18]SHAFER JC,AGRAWAL R,MEHTAM.SPRINT:a scalab le parallel classifier for datamining[C]∥Proc of the 1996 Int Conf Very Large Data Bases.Bombay,India:ACM Press,1996:544-555.

[19]CHANG C,LIN C.LIBSVM:a library for support vector machines[CP/OL].2001.http:∥www.csie.ntu.edu.tw/～cjlin/libsvm/.

(責(zé)任編輯 鄭筱梅)

An Ensemble Learning and Category Indicator Based Text Categorizing Method

JIANG Zong-li,XU Xue-ke
(College of Computer Science,Beijing University of Technology,Beijing 100124,China)

As it is well known that the motivation of ensemble learning is to boost a strong classifier with high generalization ability from aweak classifier.However,the achievement of generalization ability isoften at great cost of complexity and intense computation.In this paper an ensemble learning and category indicator based categorizing method is proposed and Adaboost.MH based mechanism is developed to adaptively compute the category indicating function at every step.Then all individual category indicating functions are combined with weightand an approximation to the expected category indicating function is obtained.Based on the combined category indicating function,a classifier,which has low computational cost,flexibility in updating with new features and suitable for real-time applications has been obtained.Furthermore it is proved that the proposed method is equivalence to ensemble classifier and thereby it has high generalization ability.Experiments on the corpus of Tan Corp-12 show that the proposed method can achieve good performance in text categorizing tasks and outperform many text categorizing methods.

machine learning;ensemble learning;Ada Boost.MH;text categorization;category indicator

TP 181

A

0254-0037(2010)04-0546-08

2008-05-08.

蔣宗禮(1956—),男,河南南陽(yáng)人,教授.

文本分類是在給定分類體系下,根據(jù)內(nèi)容對(duì)未知類別文本進(jìn)行歸類.文本分類是處理和組織大規(guī)模文本信息的關(guān)鍵,能使信息資源得以合理有效組織,是信息處理領(lǐng)域最重要的研究方向之一.文本分類技術(shù)也是主題搜索、個(gè)性化信息檢索、搜索引擎目錄導(dǎo)航、信息過(guò)濾等的核心技術(shù),對(duì)于解決有效獲取有效網(wǎng)絡(luò)信息,研究新一代搜索引擎有著重要意義.

集成學(xué)習(xí)為解決同一個(gè)問(wèn)題訓(xùn)練出多個(gè)分類器,在對(duì)新的數(shù)據(jù)進(jìn)行處理時(shí),將各個(gè)分類器的結(jié)論以某種方式進(jìn)行綜合.這種方法能克服各個(gè)分類器對(duì)訓(xùn)練集的過(guò)擬合問(wèn)題,提高泛化能力,從而盡可能好地處理新數(shù)據(jù),因此集成學(xué)習(xí)受到國(guó)際機(jī)器學(xué)習(xí)界的廣泛重視,被機(jī)器學(xué)習(xí)權(quán)威專家 Dietterich認(rèn)為是當(dāng)前機(jī)器學(xué)習(xí)的四大研究方向之首[1],在包括文本分類的多個(gè)領(lǐng)域得到廣泛應(yīng)用[2].