王中卿, 李壽山，朱巧明，李培峰，周?chē)?guó)棟

(蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006)

1 引言

目前，人們?cè)絹?lái)越習(xí)慣于在網(wǎng)絡(luò)上表達(dá)自己的觀點(diǎn)和情感，從而使得網(wǎng)絡(luò)上漸漸出現(xiàn)了大量帶有情感的文本。由于傳統(tǒng)的基于主題的文本分類方法已經(jīng)無(wú)法很好分析這些情感文本，人們開(kāi)始關(guān)注針對(duì)情感文本分類(簡(jiǎn)稱：情感分類)的方法研究[1-2]。雖然情感分類的研究已經(jīng)開(kāi)展多年，但是目前大部分情感分類的研究假設(shè)正類樣本和負(fù)類樣本是平衡的[1-4]。該假設(shè)和實(shí)際情況并不相符，在實(shí)際收集的產(chǎn)品評(píng)論語(yǔ)料中，我們發(fā)現(xiàn)正類樣本和負(fù)類樣本的數(shù)目差距很大。樣本分布的不平衡往往會(huì)使傳統(tǒng)的機(jī)器學(xué)習(xí)分類方法在分類過(guò)程中嚴(yán)重偏向多樣本類別，從而使分類的性能急劇下降。因此，不平衡數(shù)據(jù)的情感分類問(wèn)題是一個(gè)迫切需要解決的實(shí)際問(wèn)題。

不平衡分類本身在機(jī)器學(xué)習(xí)領(lǐng)域是一個(gè)很有挑戰(zhàn)性的研究問(wèn)題[5-6]。為了表述清楚，在下文中我們將樣本集合中樣本數(shù)較多的一類稱為多類(Majority Class)，樣本數(shù)較少的一類稱為少類(Minority Class)。目前已經(jīng)存在一些用來(lái)解決不平衡分類問(wèn)題的方法，例如，重采樣技術(shù)(Re-sampling)[7]，單類別分類(One-class classification)[8]和代價(jià)敏感學(xué)習(xí)(Cost Sensitive Learning)[9]。但是由于還沒(méi)有針對(duì)情感分類特別是中文情感分類的不平衡問(wèn)題的研究，很多基本問(wèn)題仍待研究，例如，哪種方法更適合中文情感分類任務(wù)。

本文將以欠采樣技術(shù)(Under-sampling)為基礎(chǔ)，通過(guò)集成學(xué)習(xí)(Ensemble learning)解決情感分類中的不平衡問(wèn)題。欠采樣技術(shù)是指從初始的多類標(biāo)注樣本中隨機(jī)取出和少類標(biāo)注樣本一樣規(guī)模的樣本，與少類樣本一同構(gòu)建分類器。欠采樣方法存在一個(gè)明顯缺點(diǎn)：由于欠采樣只是從多類中選擇部分樣本，使得大量未選中的多類樣本在后面的分類過(guò)程中未能發(fā)揮作用，從而丟失了很多可能對(duì)分類有幫助的樣本。因此，為了充分利用所有標(biāo)注數(shù)據(jù)，可以首先在多類樣本中進(jìn)行多次欠采樣，構(gòu)建多個(gè)欠采樣基分類器，最終融合這些基分類器進(jìn)行集成學(xué)習(xí)[10]。我們稱該方法為基于欠采樣融合的集成方法。

影響集成學(xué)習(xí)性能的一個(gè)重要因素是參與集成的分類器之間的差異性。一般來(lái)說(shuō)，分類器之間的差別越大，集成學(xué)習(xí)的性能提高會(huì)越明顯[11]。然而，在欠采樣融合的集成方法中，所有基分類器中參與訓(xùn)練的少類樣本是完全一樣的。為了進(jìn)一步增加基分類之間的差異性，我們提出基于欠采樣和多分類算法的集成方法。具體來(lái)講，每個(gè)欠采樣基分類器是由隨機(jī)分配的分類算法訓(xùn)練得到。由于不同分類算法的分類機(jī)理是不同的，這樣參與的基分類器之間的差異性進(jìn)一步擴(kuò)大，有利于進(jìn)一步提高分類性能。實(shí)驗(yàn)結(jié)果表明，基于欠采樣和多分類算法的集成方法能夠進(jìn)一步的提高分類的效果。

本文結(jié)構(gòu)安排如下：第二節(jié)詳細(xì)介紹情感分類以及不平衡分類的相關(guān)工作；第三節(jié)提出基于集成學(xué)習(xí)的不平衡分類方法；第四節(jié)給出實(shí)驗(yàn)結(jié)果及分析；第五節(jié)給出相關(guān)結(jié)論。

2 相關(guān)工作

2.1 情感分類

早期情感分類研究主要集中在無(wú)監(jiān)督學(xué)習(xí)方法上面。無(wú)監(jiān)督學(xué)習(xí)一般是通過(guò)兩個(gè)詞之間的關(guān)系以及一些資源比如WordNet/HowNet或者未標(biāo)注數(shù)據(jù)來(lái)判斷文本的情感傾向[12]。由于無(wú)監(jiān)督學(xué)習(xí)方法的分類效果比較差，并不能很好滿足實(shí)際應(yīng)用的需求。

基于監(jiān)督學(xué)習(xí)的情感分類方法是當(dāng)前的主流方法，與無(wú)監(jiān)督學(xué)習(xí)方法相比，基于詞袋模型(Bag-of-words Model)的全監(jiān)督情感分類方法總是能夠獲得更好的分類效果[1]。后續(xù)的大量研究在基本的詞袋模型上面給出了多種方式的改進(jìn)，進(jìn)一步提高了分類的性能。例如，采用上下文特征[13]，使用文檔子成分(Document Subcomponent)信息[14]，考慮極性轉(zhuǎn)移[15]等。然而，已有的方法基本都是基于樣本分布平衡的假設(shè)，不平衡數(shù)據(jù)的情感分類方法研究還很缺乏。

2.2 不平衡分類

目前，主流的不平衡分類方法主要分為三類：重采樣技術(shù)、單類別分類和代價(jià)敏感學(xué)習(xí)。

其中，重采樣技術(shù)應(yīng)用最為廣泛。重采樣技術(shù)主要分為兩類：欠采樣(Under-sampling)和過(guò)采樣(Over-sampling)。具體來(lái)講，過(guò)采樣技術(shù)通過(guò)重復(fù)少類樣本使得少類樣本數(shù)和多類樣本數(shù)平衡；欠采樣技術(shù)通過(guò)減少多類樣本使得兩類樣本數(shù)平衡。除了簡(jiǎn)單的隨機(jī)重采樣，其他多重采樣方法通過(guò)啟發(fā)式的策略來(lái)擴(kuò)展/選擇樣本。例如，Yen和Lee 提出基于聚類方法的欠采樣方法，該方法通過(guò)聚類的方式在采樣的過(guò)程中選擇更具代表性的樣本[16]。

代價(jià)敏感學(xué)習(xí)方法的主要思想是在構(gòu)建分類器過(guò)程中修改訓(xùn)練過(guò)程中的分錯(cuò)代價(jià)函數(shù)，讓少類分錯(cuò)的代價(jià)遠(yuǎn)遠(yuǎn)大于多類分錯(cuò)的代價(jià)[9]。單類別分類是指在構(gòu)建分類器過(guò)程中，只使用一個(gè)類別里面的標(biāo)注樣本，在應(yīng)用到不平衡分類中，僅僅多類樣本作為單類別分類的訓(xùn)練樣本[8]。該方法適合樣本非常不平衡情況的分類問(wèn)題。

3 基于集成學(xué)習(xí)的不平衡分類方法

3.1 情感分類中的不平衡分布情況

假設(shè)N個(gè)樣本的訓(xùn)練數(shù)據(jù)中包含有N+個(gè)正類樣本和N-個(gè)負(fù)類樣本。目前大多數(shù)研究總是假設(shè)正類樣本數(shù)和負(fù)類樣本數(shù)是平衡的，即N+=N-，但實(shí)際情況并非如此。通常來(lái)說(shuō)，更一般的情況是訓(xùn)練數(shù)據(jù)中一類樣本要遠(yuǎn)遠(yuǎn)多于另一類樣本，即N+?N-或者N+?N-。

為了更好地理解情感分類中的不平衡現(xiàn)象，我們從卓越網(wǎng)*http://www.amazon.cn/上收集來(lái)自四個(gè)領(lǐng)域的中文評(píng)論語(yǔ)料并統(tǒng)計(jì)它們?cè)趦蓚€(gè)類別里面的分布情況。這四個(gè)領(lǐng)域分別是箱包、化妝品、相機(jī)和軟件。

表1 各領(lǐng)域正類樣本和負(fù)類樣本分布情況

表1給出了四個(gè)領(lǐng)域的類別分布情況。從表中可以看出，各個(gè)領(lǐng)域不平衡比(N+/N-)介于2和4。顯而易見(jiàn)，在每個(gè)領(lǐng)域中，負(fù)類樣本數(shù)目都要明顯少于正類樣本數(shù)目。

3.2 基于欠采樣融合的集成方法

集成學(xué)習(xí)是組合多個(gè)基分類器的一種學(xué)習(xí)機(jī)制。為了產(chǎn)生多個(gè)不同的基分類器，一種常用的方式是通過(guò)訓(xùn)練不同的數(shù)據(jù)集合產(chǎn)生不同的基分類器，稱之為基于樣本融合的集成學(xué)習(xí)。針對(duì)不平衡分類問(wèn)題，可以在多類樣本中進(jìn)行多次欠采樣并將每一次采樣的樣本同少類樣本訓(xùn)練獲得一個(gè)基分類器。

獲得基分類器后，組合分類器方法需要特別的融合方法去融合這些結(jié)果。融合方法可以分為兩種，固定的融合方法(Fixed Rules)和可訓(xùn)練的融合方法 (Trained Rules)。本文選擇基于固定融合方法的貝葉斯規(guī)則融合基分類器的結(jié)果。貝葉斯規(guī)則可以描述為式(1)[17]：

assigny→cj

(1)

總體來(lái)說(shuō)，基于欠采樣的集成學(xué)習(xí)的實(shí)現(xiàn)步驟如下：(1)通過(guò)在多類樣本中進(jìn)行多次欠采樣的方式和少類樣本組成多個(gè)訓(xùn)練樣本集合；(2)對(duì)于每個(gè)訓(xùn)練樣本集合訓(xùn)練一個(gè)基分類器；(3)通過(guò)貝葉斯規(guī)則融合各個(gè)基分類器的結(jié)果。

3.3 基于欠采樣和多分類算法的集成方法

在構(gòu)建集成學(xué)習(xí)系統(tǒng)中除了可以通過(guò)訓(xùn)練不同的樣本集合產(chǎn)生不同的分類器之外，還可以通過(guò)不同的分類方法產(chǎn)生不同的分類器。由于很多分類方法是基于不同的原理的，如k-近鄰(k-NN)方法是基于記憶的方法，支持向量機(jī)方法(SVM)是基于結(jié)構(gòu)風(fēng)險(xiǎn)最小理論的方法等。因此，不同的分類方法實(shí)現(xiàn)的分類器實(shí)現(xiàn)分類的效果往往是不一樣的[2]。所以通過(guò)為不同的訓(xùn)練樣本集合隨機(jī)分配不同的分類算法，可以減少由于存在相同的少類樣本造成的樣本冗余現(xiàn)象，從而進(jìn)一步提高集成學(xué)習(xí)的效果。因此，我們提出一種基于欠采樣和多分類算法的集成方法。具體實(shí)現(xiàn)步驟如下：(1)通過(guò)在多類樣本中進(jìn)行n次欠采樣的方式和少類樣本組成多個(gè)訓(xùn)練樣本集合(n的值為多類樣本和少類樣本的比率，即不平衡比)；(2)對(duì)于每個(gè)訓(xùn)練樣本集合隨機(jī)分配一個(gè)分類算法組成基分類器；(3)通過(guò)貝葉斯規(guī)則融合各個(gè)基分類器的結(jié)果。

基于欠采樣和多分類算法的集成學(xué)習(xí)系統(tǒng)需要使用多種分類算法用來(lái)構(gòu)建基分類器，本文采用三種不同的分類方法，分別為樸素貝葉斯、最大熵和支持向量機(jī)。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

我們?cè)谧吭骄W(wǎng)上收集了來(lái)自四個(gè)領(lǐng)域的中文評(píng)論語(yǔ)料。這四個(gè)領(lǐng)域分別是箱包、化妝品、相機(jī)和軟件。3.1節(jié)已經(jīng)分析了每個(gè)領(lǐng)域的不平衡情況，具體分布可參考表1。實(shí)驗(yàn)過(guò)程中，我們選擇 80%的樣本作為訓(xùn)練樣本，剩余的20%樣本作為測(cè)試樣本。分類算法包括最大熵、SVM和樸素貝葉斯。其中，SVM是使用標(biāo)準(zhǔn)工具light-SVM*http://svmlight.joachims.org/，樸素貝葉斯和最大熵是使用MALLET機(jī)器學(xué)習(xí)工具包*http://mallet.cs.umass.edu/。在使用過(guò)程中，這些工具的所有參數(shù)都設(shè)置為它們的默認(rèn)值。

在進(jìn)行分類之前首先采用中國(guó)科學(xué)院計(jì)算技術(shù)研究所的分詞軟件ICTCLAS*http://ictclas.org/對(duì)中文文本進(jìn)行分詞操作。給定分好詞的文本后，我們選取詞的Unigram作為特征，用以獲得文本向量的表示。

在平衡數(shù)據(jù)的情感分類中，通常使用準(zhǔn)確率(Accuracy，acc.)作為分類效果的衡量標(biāo)準(zhǔn)。 而在不平衡分類中，由于分類結(jié)果很容易偏向多類，所以使用準(zhǔn)確率作為分類效果的衡量標(biāo)準(zhǔn)對(duì)于少類變得非常不公平。因此，一般使用幾何平均數(shù)(G-mean)作為衡量分類效果的標(biāo)準(zhǔn)。幾何平均數(shù)的計(jì)算方法為式(2)：

(2)

其中：TPrate和TNrate分別代表了正類樣本的召回率和負(fù)類樣本的召回率[6]。

4.2 不同分類算法的比較

表2和表3分別是各個(gè)分類算法基于欠采樣以及基于欠采樣集成學(xué)習(xí)的分類的分類結(jié)果(G-mean值)。從結(jié)果中可以看出：(1)最大熵，SVM和樸素貝葉斯在分類結(jié)果上的差別不明顯，這一點(diǎn)同文獻(xiàn)[1]中的結(jié)果一致；(2)雖然不同的分類算法在實(shí)現(xiàn)上有很大的不同，但是基于欠采樣集成學(xué)習(xí)的分類效果都比基于欠采樣的分類有很大的提升，充分顯示了基于欠采樣集成學(xué)習(xí)的分類在不平衡中文情感分類中的優(yōu)勢(shì)。

表2 基于欠采樣的分類的分類結(jié)果

表3 基于欠采樣集成學(xué)習(xí)的分類結(jié)果

4.3 不平衡分類方法比較

為了進(jìn)行充分的比較，我們實(shí)現(xiàn)了多種主流的不平衡分類方法。

1)完全訓(xùn)練(FullTraining，F(xiàn)ullT)，直接將所有訓(xùn)練樣本進(jìn)行訓(xùn)練。

2)隨機(jī)過(guò)采樣(RandomOver-sampling，OverS)，在少類樣本中使用過(guò)采樣技術(shù)隨機(jī)選擇樣本。

3)隨機(jī)欠采樣(RandomUnder-sampling，UnderS)，在多類樣本中使用采樣技術(shù)隨機(jī)選擇樣本。

4)基于聚類的欠采樣(Clustering-basedUnder-sampling，ClusterU)，我們根據(jù)文獻(xiàn)[16]的方法實(shí)現(xiàn)了基于聚類的欠采樣。

5)基于最鄰近的欠采樣(Neighbor-basedUnder-sampling，Neighbor)，在多類樣本中進(jìn)行隨機(jī)欠采樣，只是在欠采樣時(shí)，每次選擇一個(gè)樣本需要在樣本集合中去除和它最鄰近的k個(gè)樣本(k-NN)[18]。在我們的實(shí)驗(yàn)中，該方法通過(guò)在多類樣本中去除“多余的”，“邊界的”樣本從而提高欠采樣的效果。

6)單類別分類(One-classClassification，OneClass)，我們根據(jù)文獻(xiàn)[8]的描述，利用libSVM*http://www.csie.ntu.edu.tw/～cjlin/libsvm/實(shí)現(xiàn)單類別分類。

7)代價(jià)敏感分類(Cost-sensitiveClassification，CostSensitive)，我們根據(jù)文獻(xiàn)[9]的描述，利用libSVM實(shí)現(xiàn)代價(jià)敏感分類。在這里代價(jià)的權(quán)重根據(jù)每個(gè)領(lǐng)域中訓(xùn)練樣本集合中多類樣本和少類樣本的比例進(jìn)行調(diào)整。

8)基于欠采樣和多分類算法的集成學(xué)習(xí)(OurApproach)，在基于欠采樣的集成學(xué)習(xí)的基礎(chǔ)上為每組訓(xùn)練樣本隨機(jī)分類不同的分類器，也就是本文提出的方法。

從上一節(jié)結(jié)果可以看出，三個(gè)分類算法的分類性能差異不大，我們關(guān)于不平衡學(xué)習(xí)方法的比較研究中僅以最大熵分類算法作為基準(zhǔn)系統(tǒng)實(shí)現(xiàn)前四種不平衡分類方法。表4是各種不平衡分類方法在基于不平衡數(shù)據(jù)的中文情感分類中的分類效果。從表中可以看出，單類別分類方法表現(xiàn)最差，可能的原因是單類別分類適合不平衡程度非常大的不平衡分類問(wèn)題(例如，正負(fù)或者負(fù)正樣本比例超過(guò)1 000)，而中文情感分類的正負(fù)比例僅僅介于2到4之間。完全訓(xùn)練(FullT)方法表現(xiàn)也不理想，主要原因就是分類算法嚴(yán)重趨向多類，使得少類的召回率非常低。從幾種采樣方法的比較中可以發(fā)現(xiàn)，欠采樣方法優(yōu)于過(guò)采樣方法，但是幾種欠采樣的方法的性能基本類似。代價(jià)敏感分類方法(CostSensitive)相對(duì)于其他方法有明顯優(yōu)勢(shì)，能夠比隨機(jī)欠采樣方法有明顯提升。我們的基于欠采樣和多分類算法的集成方法明顯優(yōu)于其他各種不平衡分類方法，平均比代價(jià)敏感分類方法提高超過(guò)兩個(gè)百分點(diǎn)。

表4 不同不平衡分類的結(jié)果

5 結(jié)語(yǔ)

本文研究中文情感文本分類任務(wù)中的不平衡數(shù)據(jù)分類問(wèn)題，提出一種基于欠采樣和多分類算法的集成學(xué)習(xí)方法。實(shí)驗(yàn)結(jié)果表明，該方法能夠很好地解決中文情感分類任務(wù)中的不平衡分類問(wèn)題。比較研究發(fā)現(xiàn)，我們的方法明顯優(yōu)于傳統(tǒng)的采樣方法、單類別分類和代價(jià)敏感分類方法。

情感文本分類任務(wù)中的不平衡數(shù)據(jù)分類問(wèn)題才剛剛起步，有許多問(wèn)題還有待進(jìn)一步深入研究。例如，不平衡情感分類問(wèn)題中的特征選擇是明顯區(qū)別于傳統(tǒng)特征提取方法[19]，如果更有效地進(jìn)行不平衡數(shù)據(jù)分類問(wèn)題中的特征提取是一個(gè)值得探討的問(wèn)題。另外，情感分類領(lǐng)域適應(yīng)(Domain Adaptation)[3]中的不平衡數(shù)據(jù)分類問(wèn)題也是一個(gè)急需解決的問(wèn)題。在實(shí)際應(yīng)用中，存在目標(biāo)領(lǐng)域里面的樣本分布不平衡的情況。這些問(wèn)題將作為我們下一步的研究方向。

[1] Pang B. ,Lee L., Vaithyanathan S. Thumbs up?: Sentiment Classification using Machine Learning Techniques[C]//Proceedings of EMNLP. 2002.

[2] 李壽山, 黃居仁. 基于 Stacking組合分類方法的中文情感分類研究[J]. 中文信息學(xué)報(bào), 2010, 24(5)：56-61.

[3] Blitzer J., Dredze M., Pereira F. Biographies. Bollywood, Boom-boxes and Blenders: Domain Adaptation for Sentiment Classification[C]//Proceedings of ACL. 2007.

[4] Li S., Huang C., Zhou G., et al. Employing Personal/Impersonal Views in Supervised and Semi-supervised Sentiment Classification[C]//Proceedings of ACL. 2010.

[5] Barandela R., Sánchez J.S., García V., et al. Strategies for Learning in Class Imbalance Problems[J]. Pattern Recognition, 2003, 36：849-851.

[6] Kubat M., Matwin S. Addressing the Curse of Imbalanced Training Sets: One-Sided Selection[C]//Proceedings of ICML.1997.

[7] Chawla N., Bowyer K., Hall L., et al. SMOTE: Synthetic Minority Over-Sampling Technique[J]. Journal of Artificial Intelligence Research, 2002,16：321-357.

[8] Juszczak P., Duin R. Uncertainty Sampling Methods for One-Class Classifiers[C]//Proceedings of ICML, Workshop on Learning with Imbalanced Data Sets II. 2003.

[9] Zhou Z., Liu X. Training Cost-Sensitive Neural Networks with Methods Addressing the Class Imbalance Problem[C]//IEEE Transaction on Knowledge and Data Engineering, 2006, 18：63-77.

[10] Liu X., Wu J.,, Zhou Z. Exploratory under-sampling for class-imbalance learning[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2009, 39(2): 539-550.

[11] Kittler J., Hatef M., Duin R., et al. On Combining Classifiers[J]. IEEE Trans. PAMI, 1998,20: 226-239.

[12] Turney P. Thumbs up or Thumbs down? Semantic Orientation Applied to Unsupervised Classification of reviews[C]//Proceedings of ACL. 2002.

[13] Riloff E., Patwardhan S., Wiebe J. Feature Subsumption for Opinion Analysis[C]//Proceedings of EMNLP. 2006.

[14] McDonald R., Hannan K., Neylon T., et al. Structured Models for Fine-to-coarse Sentiment Analysis[C]//Proceedings of ACL. 2007.

[15] Li S., Lee S., Chen Y., et al. Sentiment Classification and Polarity Shifting[C]//Proceedings of COLING. 2010.

[16] Yen S., Lee Y. Cluster-Based Under-Sampling Approaches for Imbalanced Data Distributions[J]. Expert Systems with Applications,2009,36：5718-5727.

[17] Kittler J., Hatef M., Duin R. P.W., et al. On combining classifiers[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1998,20: 226-239.

[18] Laurikkala J. Improving Identification of Difficult Small Classes by Balancing Class Distribution[C]// Proceeding of 8th Conference on artificial intelligence in medicine in Europe, 2001.

[19] Li S., Xia R., Zong C. et al. A Framework of Feature Selection Methods for Text Categorization[C]//Proceedings ACL-IJCNLP. 2009.

[20] Somasundaran S., G. Namata, J. Wiebe. Supervised and Unsupervised Methods in Employing Discourse Relations for Improving Opinion Polarity Classification[C]//Proceedings of EMNLP.2009.

[21] Nakagawa T.,Inui K., Kurohashi S. Dependency Tree-based Sentiment Classification using CRFs with Hidden[C]//Proceedings of NAACL. 2010.

[22] 翟云,楊炳儒,曲武.不平衡類數(shù)據(jù)挖掘研究綜述[J].計(jì)算機(jī)科學(xué), 2010, 37: 27-32.

[23] Vilalta R., Drissi Y. A perspective view and survey of meta-learning[J]. Artificial Intelligence Review, 2002, 18(2): 77-95.