高性能文本分類算法研究.pdf

1、因特網(wǎng)上的文本信息的爆炸式增長(zhǎng)給文本分類的精度與速度提出了新的標(biāo)準(zhǔn)與挑戰(zhàn)。這就要求文本分類在提高精度的同時(shí)，還要進(jìn)一步提升訓(xùn)練與分類速度。為了面對(duì)時(shí)代的挑戰(zhàn)，作者從特征選擇與學(xué)習(xí)算法兩個(gè)角度展開(kāi)了深入的研究，取得了一系列突破性進(jìn)展。 作者從基于分辨矩陣的粗糙集屬性約簡(jiǎn)中受到啟發(fā)，提出了一系列基于粗集理論的文本特征選擇算法，即DBl、DB2、LDB。實(shí)驗(yàn)結(jié)果表明，DB2與LDB極為穩(wěn)定，達(dá)到了與信息增益相當(dāng)?shù)木?；?dāng)特征數(shù)較少時(shí)，

2、DB2與I,DB的精度要明顯高于信息增益。同時(shí)，在時(shí)間上也具有相當(dāng)?shù)膬?yōu)勢(shì)，DB2與LDB的時(shí)間代價(jià)與文檔頻次、互信息、CHI統(tǒng)計(jì)大體相當(dāng)，但明顯低于信息增益。 “沒(méi)有免費(fèi)的午餐定理”表明：任何一種模式分類算法都不存在“與生俱來(lái)”的優(yōu)越性。換句話說(shuō)，所有分類器都存在一定程度上的“分類器偏差”。原因很簡(jiǎn)單，因?yàn)樗蟹诸惼鞫冀⒃谀撤N假設(shè)(模型)之上。通常，這個(gè)偏差會(huì)導(dǎo)致訓(xùn)練集與測(cè)試集錯(cuò)誤率增大。很自然地，作者就考慮采用訓(xùn)練集錯(cuò)分樣本

3、來(lái)在線修正分類器模型。這便是拉推策略的基本思想。作者將拉推策略應(yīng)用到三個(gè)基本的分類器，即中心法、貝葉斯、最近鄰，于是得到三個(gè)修正的分類器，即RCC、RNB、RKNN。其中RCC的性能最為卓越。實(shí)驗(yàn)結(jié)果表明算法RCC取得了逼近SVM的分類精度，但運(yùn)行時(shí)間需求卻與問(wèn)題規(guī)模成線性關(guān)系，因此實(shí)際運(yùn)行時(shí)間要遠(yuǎn)遠(yuǎn)低于SVM。 但是，拉推策略只是降低了經(jīng)驗(yàn)誤差，還沒(méi)有有效地降低推廣誤差。作者的一個(gè)非常直接的想法就是，不但要求訓(xùn)練樣本與正確類別

4、的相似度大于所有與其它類別的相似度，而且要至少存在一個(gè)間隔，即近似Margin。算法的具體做法就是，不但對(duì)誤分樣本要修正相應(yīng)類代表，而且對(duì)Margin較小的樣本也要修正相應(yīng)類代表。實(shí)驗(yàn)結(jié)果表明該算法既能降低訓(xùn)練集誤差，又能在一定程度上降低推廣誤差。并且，分類質(zhì)量要比拉推策略高出1個(gè)百分點(diǎn)。 考慮到層次化分類的實(shí)用性與有效性。作者將拉推策略推廣到層次化分類。作者給出了兩種將拉推策略推廣到層次模型的方法。其一是選取整棵樹(shù)進(jìn)行拉推修正

5、。其二是選取每個(gè)非葉子節(jié)點(diǎn)進(jìn)行拉推修正。實(shí)驗(yàn)結(jié)果表明，層次拉推策略的分類質(zhì)量與非層次拉推策略基本相當(dāng)，但運(yùn)行時(shí)間上具有明顯的優(yōu)越性。 概念索引采用類中心作為壓縮空間的坐標(biāo)。但是，簡(jiǎn)單地采用類中心來(lái)代表一個(gè)類別，往往受到類中樣本分布情況的影響。因此，為了提高類中心的表達(dá)能力，作者借助于拉推策略來(lái)修正類中心。然后再把修正的類中心作為壓縮空間的坐標(biāo)。實(shí)驗(yàn)結(jié)果表明，修正的概念索引在精度上要明顯優(yōu)于普通的概念索引。同時(shí)，修正的概念索引在與

6、SVM分類器的兼容性方面表現(xiàn)得更為出色。 概念索引使用中心法的類代表(類中心)來(lái)作為“概念”。于是，作者把“概念”進(jìn)行推廣。也就是說(shuō)，不僅僅可以使用類中心來(lái)作為“概念”，還可以使用其它類代表，如Winnow的權(quán)向量、貝葉斯的類概率與詞概率、KNN的類代表、SVM的支持向量等等，來(lái)作為“概念”。作者把采用推廣的“概念”來(lái)進(jìn)行壓縮的方法統(tǒng)稱為“分類器索引”。實(shí)驗(yàn)結(jié)果表明分類器索引表現(xiàn)出了非常穩(wěn)定的性能。 前面所提到的分類器修