基于TAN的文本分類集成方法

1、基于TAN 的文本分類集成方法    基于TAN 的文本分類集成方法#劉佳，賈彩燕*基金項目：本文受高等學校博士學科點專項科研基金項目（20070004038）資助作者簡介：劉佳，（1985-），男，碩士，主要研究方向：文本挖掘通信聯(lián)系人：賈彩燕，（1976-），女，講師，主要研究方向：數(shù)據(jù)挖掘、生物信息學、復雜網絡分析等. E-mail: EBag-TAN 與單個最優(yōu)TAN 分類器的分類性能相當。進一步說明了集成方法適用于弱分類器，即如果單個分類器的分類能力越強，集成后的效果越差。需要給出有效的方法增加不同的單分類器之間的分類差異，從而提高集

2、成分類器的分類性能。而對于文本分類問題，基于特征集選取的集成方法可以構造出單個分類器多樣性較大的集成分類方法。45 1 集成學習目前，集成學習分為基于數(shù)據(jù)的集成方法和基于特征的集成方法兩種。基于數(shù)據(jù)的集成主要使用隨機取樣的方法獲取訓練數(shù)據(jù)，它是集成學習算法獲取差異性個體經常使用的方法，包括有放回隨機取樣、無放回隨機取樣與混合取樣（包括無放回隨機取樣與有放回隨機取樣）。比較經典的算法包括：Boosting 和Bagging。基于特征集的集成方法通過提取不同50 的特征子集來訓練集成模型中的個體，是提高集成個體差異性的一種較好的方法，適用于學習性能較穩(wěn)定的分類器。1.1 Boosting 算法Bo

3、osting 算法的基本思想是試圖通過產生數(shù)個簡單的、精度比隨機猜測略好的粗糙估計（Boosting 算法中稱為弱規(guī)則T h , h ,.h 1 2 ），再將這些規(guī)則集成構造出一個高精度的估計。55 這種思想起源于Valiant 提出的PAC 學習模型4。在PAC 模型中定義了兩個概念：強學習和弱學習。Keams 和Valiant 提出了弱學習算法與強學習算法間的等價問題5，即是否能把弱學習算法轉化為強學習算法？如果兩者等價，那么只要找到一個比隨機猜測略好的弱學習算法就可以直接將其提升為強學習算法，而不必直接去找很難獲得的強學習算法。Keams和Valiant6證明只要有足夠的數(shù)據(jù)，弱學習算法

4、就能通過集成的方式生成任意高精度的估60 計。1990 年，Schapire7最先構造出一種多項式級的算法，即最初的Boosting 算法。1991年，F(xiàn)reund8提出了一種效率更高的Boosting 算法。由于早期的Boosting 算法在解決實際問題時要求事先知道弱學習算法學習正確率的下限，這實際上很難做到。1995 年，F(xiàn)reund和Schapire9提出了AdaBoost（Adaptive Boosting）算法，這種算法的效率和原來Boosting算法的效率一樣，但不需要任何關于弱學習器性能的先驗知識，可以非常容易地應用到實際65 問題中。因此，該算法已成為目前最流行的Boosti

5、ng 算法。AdaBoost 算法的主要思想是給定一個訓練集( , ), ( , ),.( , ) 1 1 2 2 m m x y x y x y ，1,+1 i y 。初始化時AdaBoost 指定訓練集上的分布為1/m，并按照該分布調用弱學習器對訓練集進行訓練。每次訓練后，根據(jù)訓練結果更新訓練集上的分布，并按照新的樣本分布進行訓練。反復迭代T 輪，最終得到一個估計序列T h , h ,.h 1 2 ，每個估計都具有一定的權70 重，最終的估計H 是采用有權重的投票方式獲得。AdaBoost 算法9的偽代碼如下：輸入：訓練集( , ),., ( , ) 1 1 m m S = x y x y

6、 ，其中x X i ， 1,+1 i y ，X 表示一個實例空間；迭代次數(shù)T 和弱分類器。初始化：權重D (i) 1/ m 1 = ，i = 1, , m。執(zhí)行：For t = 1, , T1) 對有權重分布的訓練集進行學習，得到一個估計t h ： 1,+1 i 75 x ；2) 計算t h 訓練偏差= mit t t i i D i h x y1 ( ) ( )，如果= 0 t或者 1/ 2 t，令T = t-1 并跳出循環(huán)；3) 令0.5 ln(1 ) / t t t = × ；4) 更新權重： t t t i t i t D (i) D (i)exp y h (x )

7、 / Z 1 = + ，其中t Z 是標準化因子。輸出： ( ) ( ( )1 =Ttt t 80 H x sign h x 。上面給出的算法是針對于兩分類問題的，關于如何將Boosting 算法應用到多分類問題，研究者提出了多種不同的方法，包括AdaBoost.M191、AdaBoost.M291和AdaBoost.MH92等算法。其中，AdaBoost.M1 是最直接的應用于多分類問題的方法，其算法步驟如下：輸入：訓練集( , ),., ( , ) 1 1 m m S = x y x y ， y Y 1,2,., k i = ，迭代次數(shù)T 和弱學習85 算法。初始化：權重D (i) 1/

8、m 1 = ，i = 1, , m。執(zhí)行：For t = 1, , T1) 用弱學習算法對有權重分布的訓練集進行學習；2) 得到一個估計t h ： X Y ；3) 計算t h 訓練偏差=: ( )( )i ht xi yit t D i ，如果> 1/ 2 t 90 ，令T = t-1 并跳出循環(huán)；4) 令/(1 ) t t t = ；5) 更新權重： = × +t i it t i ittt h x yh x yZD iD i1 ( )( ) ( )( ) 1，其中t Z 是標準化因子。輸出： =t h x y ty YtH x: ( )( ) argmax log 1。1.

9、2 Bagging 算法95 Bagging11（Bootstrap aggregating）是Breiman 在1996 年提出的與Boosting 相似的技術。Bagging 的基礎是重復取樣，它通過產生樣本的重復Bootstrap 實例作為訓練集，每次運行Bagging 都隨機地從大小為m 的原始訓練集中抽取l 個樣本作為此次訓練的集合。這種訓練集被稱作原始集合的Bootstrap 復制，這種技術也叫Bootstrap 綜合，即Bagging。平均來說，每個Bootstrap 復制包含原始訓練集的63.2%，原始訓練集中的某些樣本可能在新的訓100 練集中出現(xiàn)多次，而另外一些樣本則可能一

10、次也不出現(xiàn)。Bagging 通過重新選取訓練集增加了分量學習器集成的差異度，從而提高了泛化能力。Breiman11同時指出，穩(wěn)定性是Bagging 能否提高預測準確率的關鍵因素。Bagging 對不穩(wěn)定的學習算法能提高預測的準確度，而對穩(wěn)定的學習算法效果不明顯，有時甚至會使預測精度降低，學習算法的不穩(wěn)定性是指如果訓練有較小的變化，學習算法產生的預測函數(shù)將105 發(fā)生較大的變化。Bagging 算法的原理如下，給定一個數(shù)據(jù)集( , ),., ( , ) 1 1 l l L = x y x y ，基礎學習器為h(x, L) 。如果輸入為x，就通過h(x, L) 來預測y。現(xiàn)在，假定有一個數(shù)據(jù)集序列

11、 k L ，每個序列都有l(wèi) 個與L 從同樣分布數(shù)據(jù)集得來的獨立觀察組成，任務是使用 k L 來得到一個更好的學習器，它比單個數(shù)據(jù)集學習器h(x, L) 要強。Bagging 算法的偽代碼如下： 輸入：訓練集( , ),.,( , ) 1 1 m m 110 S = x y x y ，迭代次數(shù)T 和弱學習算法。執(zhí)行：For t = 1, , T1) 從初始的訓練集中采用bootstrap 方法抽取l 個訓練實例組成的子集S ' ；2) 在S ' 上，利用弱學習算法訓練得到弱分類器，得到預測函數(shù)t h ： X Y ；輸出： = =Tiiy YH x h x y1( ) a

12、rg max ( ( ) )115 Bagging 算法與Boosting 算法的主要區(qū)別在于Bagging 訓練集的選擇是隨機的，各輪的訓練集之間是相互獨立的，而Boosting 訓練集的選擇不是獨立的，各輪訓練集的選擇與前面各輪的學習結果有關；Bagging 的各個預測函數(shù)沒有權重，而Boosting 是有權重的；Bagging的各個預測函數(shù)可以并行生成，而Boosting 的各個預測函數(shù)只能順序生成。對于像神經網絡這樣極為耗時的學習方法，Bagging 可以通過并行訓練節(jié)省大量時間開銷。另外，一些研120 究者發(fā)現(xiàn)1213，一般情況下，Bagging 方法總是可以改善學習系統(tǒng)的性能；而B

13、oosting方法在有效時效果比Bagging 還好，但在無效時卻可能使學習系統(tǒng)的性能惡化。值得注意的是，Boosting 和Bagging 的輪數(shù)并非越多越好，實驗表明13，學習系統(tǒng)性能的改善主要發(fā)生在最初的若干輪中。1.3 基于特征集的集成方法125 基于不同特征集選取的集成方法是用來提高集成個體差異性的另一類方法，通過提取不同的特征子集來訓練集成中的個體。為了提高集成個體的差異性，通常采取不同的技術獲取這組特征子集。最直接的方法就是在大小為n 的特征集合中，求出所有的特征子集，然后在其中選取所需要的特征子集集合。但由于特征子集所構成的搜索空間由2n 種可能狀態(tài)構成，顯然，即使在特征數(shù)目不

14、多的情況下，搜索空間也是龐大的。在實際應用中，這種窮盡130 式搜索是不可行的，因此，研究者們致力于用啟發(fā)式搜索算法尋找特征子集集合。Ho14提出了構建決策森林的隨機子空間方法，在這種方法中，隨機選擇特征子集，并分配給學習算法，然后在這個子空間中生成分類器，最后根據(jù)分類器的正確率使用加權投票方法進行集成。Opitz 提出了基于遺傳算法的特征選擇的集成學習算法15；Oliveira 等人運用了多目標的遺傳算法16。135 另外，Tumer 與Oza17提出了ID( Input Decimation) 方法，這種方法目的是減少集成成員產生錯誤的相關性，通過使用不同的特征子集訓練集成中的成員，這種方

15、法與隨機子空間方法是不同的，因為對于每一類，要計算每個特征與類的輸出間的相關性，并且僅在特征最相關的子集上訓練集成成員。Bryll 等人18提出的AB(Attribute Bagging)算法是基于特征選擇的集成學習方法的代表140 性算法。該算法通過對屬性進行隨機擾動，可以得到較強的泛化能力，AB 算法主要有兩步：(1) 尋找最優(yōu)的屬性集規(guī)模。所用方法為隨機投影出不同大小屬性集規(guī)模的訓練數(shù)據(jù)，對每份訓練數(shù)據(jù)用可重復取樣技術生成多個子訓練集，構建分類器，再用集成測試其精度，這樣可以得到不同屬性集規(guī)模的精度曲線，最高精度所對應的屬性集規(guī)模被認為是最優(yōu)的屬性集規(guī)模，為了得到較為平滑的精度曲線，通常

16、需要在數(shù)據(jù)集上循環(huán)計算若干遍，然后求得145 平均值。(2) 提高投票精度。在(1)的基礎上用隨機投影的方法生成大量的具有最優(yōu)屬性規(guī)模的訓練數(shù)據(jù)，針對每份訓練數(shù)據(jù)構建分類器，然后根據(jù)這些分類器在原始訓練數(shù)據(jù)或原始訓練數(shù) 據(jù)的子集上的分類精度進行排序，取精度最高的一部分參加投票?？梢钥闯?，由于AB 算法在第(2)步中需要尋找最優(yōu)的屬性集規(guī)模，而這又需要對所有可150 能規(guī)模的屬性子集進行多遍考察，其時間開銷很大。綜上所述，對于上面的這些基于特征集的集成學習方法可以概括為如下的集成學習框架：1) 選取不同的特征集以構成特征集的集合；2) 使用這組特征集集合生成集成中的個體；155 3)

17、選取一種結論生成方法對個體結論融合。2 TAN 文本分類集成方法根據(jù)上一節(jié)中介紹的Boosting、Bagging 和基于特征集的集成方法的思想，我們分別結合TAN 模型進行了TAN 集成的三次嘗試，得到的三種集成模型分別為：AdaBoost.M1 TAN，簡稱AdaM1-TAN；Extended Bagging TAN，簡稱EBag-TAN；Feature Random Subspace TAN，160 簡稱FRS-TAN。2.1 TAN 集成模型之一：AdaM1-TAN首先，我們將Boosting 與TAN 模型相結合來對TAN 集成。由于本文研究的是文本的多分類問題，為簡便起見，我們利用

18、Boosting 多分類問題的最直接方法AdaBoost.M1作為集成算法；為避免閾值選取的麻煩，基分類器采用ATAN 框架19，得到各閾值下分類165 性能最優(yōu)的TAN 分類器（具體利用CR-ATAN 算法19）；結論生成時采用投票方法。我們給該集成模型命名為AdaBoost.M1 TAN，為方便敘述，簡稱為AdaM1-TAN。AdaM1-TAN 的算法流程敘述如下：輸入：訓練文檔集( , ),( , ),.,( , ) 1 1 2 2 N N D = d y d y d y ， y C 1,2,.,| C | i = ，其中N 表示訓練集文檔的個數(shù)，C 表示文檔所屬的類別集合，|C|表示類

19、別數(shù)目；另設迭代次數(shù)T。1) 利用ATAN 框架中的CR-ATAN 算法從訓練文檔集學習ATAN 結構模型ATAN 170 G ；2) 初始化每個訓練集文檔的權重：D (i) 1/ N 1 = ，i = 1, , N；3) For t = 1, , Ta) 從有權重分布的訓練文檔集中學習ATAN G 結構的參數(shù)；b) 得到一個分類器t h ；c) 利用分類器t h 對訓練集文檔進行分類，并計算偏差=: ( )( )i ht di yit t 175 D i ，如果> 1/ 2 t，令T = t-1 并跳出循環(huán)；d) 令/(1 ) t t t = ；e) 更行訓練集文檔的權重： = 

20、15; +t i it t i ittt h x yh x yZD iD i1 ( )( ) ( )1 ( )，其中t Z 是標準化因子。輸出：終分類器=t h d y ty CtH d: ( )( ) argmax log 1180 。需要說明的是，在對ATAN G 進行參數(shù)學習時，三組概率值的估計中， P(c j ) 仍與(4-6) 相同，對于P(wt | c j ) 和P(wt | c j ,ws ) 的估計則必須采用基于權重分布的估計，如(5-4)和(5-5)所示：| | ( | ) ( )1 ( | ) ( )( | ) | |1| |1| |1V N B c d D iN

21、 B c d D iP w clVsDiis j iDiit j i lt j= =+= (5-4)| | ( | ) ( )1 ( | ) ( )( | , ) | |1| |1| |1V N B B c d D iN B B c d D iP w c wlVsDiit is j iDiit is j i lt j s= =+185 = (5-5)其中，D (i) l 表示的是第l 次迭代中，第i 個文檔i d 的權重（這里用l 表示迭代的次數(shù)而不用算法描述中t，主要是避免與公式中t w 表達的第t 個單詞沖突），其它符號的說明同第四章。2.2 TAN 集成模型之二：EBag-TAN190

22、一般來說，Bagging 是從原始訓練集合中重復Bootstrap 實例作為新的訓練集，分別訓練生成多個分類器，然后再將其集成的方法。它通過重新選取訓練集來增加分量學習器集成的差異度，從而提高了泛化能力。對于文本分類來說，重復抽取訓練子集進行訓練，就意味著要對每一個訓練子集都進行文本預處理，包括分詞、特征選擇和文檔向量生成等操作，雖然Bagging 可以并行處理，但這個過程過于繁瑣，因此我們不考慮直接利用Bagging 方法進行195 集成。換個角度想，Bagging 不斷進行重抽樣的目的無非就是學習得到多個有差異性的分類器，因此，我們只要能得到多個有差異性的分類器就可以了，而不一定要通過重抽

23、樣的方法。本節(jié)我們正是利用這個思想來對TAN 進行集成的，基分類器同AdaM1-TAN，仍然選用CR-ATAN，結論生成時采用投票方法，與基于Bagging 的集成區(qū)分，我們將該模型命名為Extended Bagging TAN，簡稱為EBag-TAN。200 如何得到多個有差異性的分類器是EBag-TAN 所要考慮的最主要問題。在TAN 模型的基于分布的構造算法中，我們需要“通過選擇一個根變量，在每條邊上添加方向，將由此生成的無向樹轉換為有向樹”，當選擇不同的根變量時，在邊上添加方向時可能會產生不同的方向，從而使得形成的有向樹結構不同，最終導致形成的TAN 結構模型不一樣。我們在實驗中發(fā)現(xiàn)，

24、選取不同的根變量形成不同的結構在分類性能上會有或多或少的差異，而且有的205 差異還比較顯著。我們嘗試用選擇不同的根變量帶來的性能差異生成的多個分類器來進行集成，算法流程敘述如下：輸入：訓練文檔集D；預生成的分類器個數(shù)T。1) 利用基于分布的TAN 構造算法執(zhí)行到第三步，即完成最大加權生成樹的構造，最大加權樹用MAX_TREE 表示。210 2) 執(zhí)行：For t = 1, , Ta) 初始化一個新的TAN 結構為樸素貝葉斯的結構，即NBtTAN G = G ；b) 將MAX_TREE 結構完全復制到tTAN G 中，然后在tTAN G 的最大加權樹結構中隨機選擇一個結點作為根變量，在每條邊上

25、添加方向，將無向樹轉換為有向樹； c) 將tTAN G 替代4.6.2 節(jié)中ATAN 算法中的完整的TAN 結構TAN G ，然后利用ATAN 算法學習得到ATAN 結構模型tATAN G ，設t215 GATAN 所對應的分類器為ht ；輸出：終分類器= =Tiiy CH d h d y1( ) argmax ( ( ) ) 。以上通過選擇不同的根變量產生分類器間的差異來達到集成的目的，這種方法應該說只能算是EBag-TAN 的一種，諸如此類的通過一定的方法生成有差異性的分類器來進行的集成，我們都視為EBag-TAN 方法。220 2.3 TAN 集成模型之三 ：FRS-TAN與基

26、于數(shù)據(jù)的集成相比，基于特征集的集成方法的研究和應用都相對較少，通常是通過一定的策略對特征空間進行搜索，得到多個特征子集，然后學習生成多個分類器進行集成。這種方法往往復雜度比較高，特別是對于文本這種高維數(shù)據(jù)來說，顯然不大實用。為降低復雜性，我們采用Ho14提出的隨機子空間方法，在這種方法中，隨機選擇特征子集，并分225 配給學習算法，然后在這個子空間中生成分類器，最后根據(jù)分類器的正確率使用加權投票方法進行集成。用隨機子空間方法對TAN 進行集成時，基分類器的選取同AdaM1-TAN 和EBag-TAN，結論生成時也采用投票方法，我們將該TAN 集成模型命名為Feature RandomSubsp

27、ace TAN，簡稱為FRS-TAN。FRS-TAN 的算法流程如下：230 輸入：訓練文檔集D；預設特征子空間的特征數(shù)目M；預生成的分類器個數(shù)T。執(zhí)行：For t = 1, , T1) 從特征空間中隨機抽取M 個特征；2) 利用文獻19中ATAN 框架中的CR-ATAN 算法從訓練文檔集學習ATAN 模型tATAN G ，設tATAN G 所對應的分類器為t h ；輸出：終分類器= =Tiiy CH d h d y1235 ( ) argmax ( ( ) ) 。需要說明的是，在第一步的隨機抽取特征子空間中，可以采用“放回取樣”和“不放回取樣”兩種，“放回取樣”允許某一個特征在該特征子集中多

28、次出現(xiàn)，而“不放回取樣”則不允許同一特征子集中有重復的特征。我們在實驗中發(fā)現(xiàn)，“放回取樣”得到的集成分類器的性能普遍好于“不放回取樣”方法，因此，本文統(tǒng)一采用“放回取樣”選擇特征子集。240 3 實驗結果及分析本節(jié)我們對上文提出的三種基于TAN 的集成模型：AdaM1-TAN、EBag-TAN 和FRS-TAN 在Reuters-21578-12 和CNLP-19637-12 語料上進行文本分類實驗， 并與CR-ATAN19構造的單個分類器的分類性能進行對比。其中，Reuters-21578-12 是從國際通用的英文文本分類測試集Reuters-215781中的挑選樣例最多的前12 個類別所形

29、成的數(shù)據(jù)集；245 CNLP-19637-12 選取中國科學院計算技術研究所的中文自然語言處理開放平臺2（ChineseNatural Language Processing Open Platform，CNLP Platform）發(fā)布的由復旦大學計算機信息1 2  與技術系國際數(shù)據(jù)庫中心自然語言處理小組所提供的中文語料庫中的前12 個類別所構成的文本集。語料預處理過程中，中文分詞利用中科院計算所提供的ICTCLAS 工具3。特征選擇采用信息增益（Information Gain，IG）方法，不做特別說明，特征數(shù)目取1000 個（當特征250 數(shù)目選擇1000 時，單個分類器在這兩個

30、語料上的整體分類性能最佳）。在實驗中我們發(fā)現(xiàn)，當EBag-TAN 和FRS-TAN 模型中個體分類器的數(shù)量超過25 時，集成分類器的性能基本穩(wěn)定，因此以下的實驗中個體分類器的數(shù)量統(tǒng)一選取25。對于FRS-TAN 模型來說，涉及特征個數(shù)M 的選取問題，在Reuters-21578-12 語料上，我們把M取為600，CNLP-19637-12 語料M 取200，因為當M 分別取對應的這些值時，F(xiàn)RS-TAN 集255 成模型的分類性能最好。實驗結果參見表1 和表2。表1 三種TAN 集成模型在Reuters-21578-12 語料上的分類性能Table 1 Comparison of three

31、ensemble learning methods based on TAN on Reuters-21578-12算法 Macro-avg（Recall）Macro-avg（Precision）Macro-avg（F1-Measure） Micro-avgAdaM1-TAN 0.781629 0.66373 0.689306 0.869078EBag-TAN 0.801581 0.795337 0.794582 0.931094FRS-TAN 0.818879 0.807126 0.810812 0.937123CR-ATAN 0.816383 0.797519 0.804459 0.933

32、678260 表2 三種TAN 集成模型在CNLP-19637-12 語料上的分類性能Table 2 Comparison of three ensemble learning methods based on TAN on CNLP-19637-12算法 Macro-avg（Recall）Macro-avg（Precision）Macro-avg（F1-Measure） Micro-avgAdaM1-TAN 0.797786 0.782053 0.765346 0.881119EBag-TAN 0.827237 0.812656 0.813187 0.897727FRS-TAN 0.8463

33、84 0.83104 0.836224 0.910839CR-ATAN 0.859237 0.789097 0.81951 0.893357從實驗結果，我們可以看到：在Reuters-21578-12 語料上，AdaM1-TAN 的宏平均1 F 相對于CR-ATAN 單分類器下降了11.5%，微平均下降了6.46%；EBag-TAN 的宏平均1 F 下降了0.98%，微平均下降了0.26%；FRS-TAN 的宏平均1 265 F 上升了0.64%，微平均上升了0.35%。在CNLP-19637-12 語料上，AdaM1-TAN 的宏平均1 F 相對于CR-ATAN 單分類器下降了5.42%，微平均下降了1.22%；EBag-TAN 的宏平均1 F 下降了0.63%，而微平均上升了0.44%；FRS-TAN 的宏平均1 F 上升了1.67%，微平均上升了1.74%?？傮w來說，AdaM1-TAN 顯示了較差的性能，EBag-TAN 與CR-ATAN 的性能相當，270 FRS-TAN 相比于CR-ATAN 單分類器性能有所提升。從語料層面上來講，三種