基于差分進(jìn)化的中文情感分類集成算法研究

楊夢(mèng)月， 衛(wèi) 偉， 陸慧娟， 盧海峰

(中國(guó)計(jì)量大學(xué) 信息工程學(xué)院，浙江 杭州 310018)

1 引 言

隨著互聯(lián)網(wǎng)的快速發(fā)展，越來越多的人通過網(wǎng)絡(luò)表達(dá)自己的觀點(diǎn)和看法，導(dǎo)致網(wǎng)上的評(píng)論數(shù)據(jù)與日俱增，所以，從文本中獲取情感信息有著巨大的現(xiàn)實(shí)意義和研究?jī)r(jià)值。

從文本中提取情感傾向，就是文本情感分類[1～3]的主要內(nèi)容。情感分類與傳統(tǒng)的基于主題文本分類的區(qū)別在于情感分類關(guān)注的對(duì)象是一些主觀因素，從文本中獲取它是否支持某種觀點(diǎn)的信息[4]。

目前，對(duì)情感分析的研究主要采用2種方法：一種是結(jié)合情感詞典的方法，其主要依賴于情感詞典的質(zhì)量；另一種是結(jié)合機(jī)器學(xué)習(xí)的方法，其關(guān)鍵依賴于特征詞的提取[5，6]。前者主要是依據(jù)情感詞典從主觀文本中提取帶有情感極性的詞，根據(jù)某種規(guī)則，獲取文本的情感極性；后者首先要對(duì)文本進(jìn)行特征表示，然后通過機(jī)器學(xué)習(xí)算法訓(xùn)練分類模型來完成分類任務(wù)。應(yīng)用更為廣泛的是基于機(jī)器學(xué)習(xí)的方法。

文獻(xiàn)[7]提出了一種基于情緒詞的非監(jiān)督情感

分類方法，在中文評(píng)論語料上進(jìn)行了實(shí)驗(yàn)，獲得了較好的分類性能。文獻(xiàn)[8]分別使用了不同詞性、不同特征選擇方法和不同分類方法在中文情感語料上進(jìn)行了實(shí)驗(yàn)。文獻(xiàn)[9]使用了樸素貝葉斯和支持向量機(jī)2種機(jī)器學(xué)習(xí)方法在電影評(píng)論語料上進(jìn)行了實(shí)驗(yàn)；但是實(shí)驗(yàn)結(jié)果表明，這2種分類器在語料集上的分類準(zhǔn)確率并不高，樸素貝葉斯的分類準(zhǔn)確率是65.57%，支持向量機(jī)的分類準(zhǔn)確率是45.71%。

單一的機(jī)器學(xué)習(xí)算法在文本情感分類上存在準(zhǔn)確率不高，樣本數(shù)據(jù)不多時(shí)對(duì)新樣本分類效果不好的問題；而集成學(xué)習(xí)[10]通過將多個(gè)學(xué)習(xí)器進(jìn)行結(jié)合，可獲得比單一學(xué)習(xí)器顯著優(yōu)越的泛化性能。文獻(xiàn)[11]使用了3種常用的集成學(xué)習(xí)方法Bagging、Boosting和Random Subspace在標(biāo)準(zhǔn)的文本情感分類數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明3種集成學(xué)習(xí)方法對(duì)基礎(chǔ)分類器的分類精度都有所提高。文獻(xiàn)[12]提出了一種基于半監(jiān)督集成學(xué)習(xí)的情感分類方法，實(shí)驗(yàn)結(jié)果表明，這種方法的分類效果明顯優(yōu)于單獨(dú)的半監(jiān)督情感分類方法。

集成方法較單個(gè)的分類方法有較好的分類效果；但是在集成多個(gè)分類器時(shí)，個(gè)體分類器的權(quán)重難以確定。為了解決這個(gè)問題，文章提出一種基于差分進(jìn)化優(yōu)化分類器權(quán)重的集成分類方法。

2 中文情感分類相關(guān)技術(shù)

2.1 文本表示

文本是一種特殊的數(shù)據(jù)格式，分類算法不能直接處理原始文本，必須把文本表示成可處理的數(shù)學(xué)向量形式。向量空間模型(vector space model,VSM)是最常見的文本表示模型。

在向量空間模型中，每個(gè)文本被表示成

D=(w1,w2,…,wn)

(1)

D是一個(gè)n維向量，wi是特征項(xiàng)權(quán)重,表示該特征項(xiàng)在文本中的重要程度,i=0,1,…,n。每個(gè)文本就是一個(gè)n維的向量。特征項(xiàng)權(quán)重wi可以用詞頻(term frequency,TF)，TF-IDF(term frequency inverse document frequency)，布爾函數(shù)等方法計(jì)算得出。由于實(shí)驗(yàn)所用數(shù)據(jù)集是評(píng)論類的短文本，使用詞頻作為特征項(xiàng)權(quán)重意義不大，而且文獻(xiàn)[13]通過實(shí)驗(yàn)表明在情感分類中使用布爾函數(shù)計(jì)算特征項(xiàng)權(quán)重是可行的,因此，本文實(shí)驗(yàn)采用布爾函數(shù)計(jì)算特征項(xiàng)權(quán)重。

情感分類與其它文本分類的差別在于：情感的正面表達(dá)和負(fù)面表達(dá)主要以形容詞、副詞和少數(shù)動(dòng)詞和名詞的表達(dá)為主[8]。因此，本文僅使用名詞、副詞、形容詞和動(dòng)詞共4種詞性的詞作為特征項(xiàng)。

2.2 特征選擇

文本向量化后的數(shù)據(jù)特征維度很大，一般不直接使用，就需要進(jìn)行特征選擇?？ǚ浇y(tǒng)計(jì)(CHI)在文本特征選擇上有較好的效果，故本文實(shí)驗(yàn)采用卡方統(tǒng)計(jì)進(jìn)行特征選擇。

卡方值表示詞項(xiàng)與類別之間的相關(guān)性，卡方值越大表示相關(guān)程度越高。

表1 CHI中各參數(shù)的意義Tab.1 The meaning of parameters in CHI

表1給出了CHI中各參數(shù)的意義，t表示一個(gè)特征項(xiàng)，c表示文本類別，A、B、C、D表示文檔數(shù)目。N為文檔總數(shù)，則N=A+B+C+D。

特征項(xiàng)t與類別c的卡方值為

(2)

2.3 分類方法

2.3.1 邏輯回歸(logistic regression,LR)

邏輯回歸是一種經(jīng)典的分類算法，一般用于二分類。給定一個(gè)輸入變量x，它可以計(jì)算出該變量屬于某一類別的概率，邏輯回歸模型為

(3)

式中：x是輸入變量；w，b是參數(shù)；y是一個(gè)介于0到1之間的數(shù)。

對(duì)于給定的訓(xùn)練數(shù)據(jù)集T={(x1,y1),(x2,y2),…,(xn,yn)}，求解參數(shù)w，b，得到邏輯回歸模型。然后對(duì)于給定的輸入變量x，計(jì)算出對(duì)應(yīng)的y值，根據(jù)設(shè)定的閾值，判定x歸屬的類別。

2.3.2 線性判別分析(linear discriminant analysis, LDA)

線性判別分析是一個(gè)簡(jiǎn)單、有效、魯棒性強(qiáng)的線性分類方法。該方法的思想是設(shè)法將樣本數(shù)據(jù)投影到一條直線上，使同類別的投影點(diǎn)盡可能接近，不同類別的投影點(diǎn)盡可能疏遠(yuǎn)[14]。對(duì)于二分類來說，就是將帶有類別標(biāo)簽的高維樣本投影到一個(gè)向量W(一維空間)上，使得在該向量上樣本的投影值達(dá)到類內(nèi)距離最小、類間距離最大，根據(jù)這一準(zhǔn)則，求解參數(shù)W，最后將樣本點(diǎn)投影到新的一維向量空間進(jìn)行分類。

2.3.3 樸素貝葉斯(naive Bayes,NB)

樸素貝葉斯是一個(gè)概率模型，在文本分類上有較好的分類效果。該方法假設(shè)特征之間相互獨(dú)立，即詞與詞之間相互獨(dú)立，文檔d的特征是X，則文檔d屬于類別ck的概率是

(4)

對(duì)給定的文檔特征X，求該文檔屬于每個(gè)類別的概率P(c|X)，若最大的概率值是P(ck|X)，則該文檔屬于ck類。

2.3.4 支持向量機(jī)(support vector machines,SVM)

支持向量機(jī)[15～17]是一種二分類模型，它的基本思想是求解能夠正確劃分訓(xùn)練數(shù)據(jù)集并且使幾何間隔最大的分離超平面，其學(xué)習(xí)策略就是間隔最大化，最終可轉(zhuǎn)化為一個(gè)凸二次規(guī)劃問題的求解。對(duì)于非線性分類問題，將樣本從原始空間映射到一個(gè)更高維的特征空間，使得樣本在這個(gè)特征空間內(nèi)線性可分。文獻(xiàn)[7]通過實(shí)驗(yàn)證明了支持向量機(jī)在情感分類上有較好的分類效果。

2.3.5 感知機(jī)(perceptron learning algorithm,PLA)

感知機(jī)是一個(gè)二分類的線性分類模型，學(xué)習(xí)目標(biāo)是尋找一個(gè)能將樣本正例和負(fù)例完全正確分開的超平面。感知機(jī)模型可表示為

f(x)=sign(wTX+b)

(5)

式中：w，b是參數(shù)。

感知機(jī)使用隨機(jī)梯度下降法，根據(jù)誤分類點(diǎn)更新參數(shù)w和b，使損失函數(shù)最小化。

2.4 結(jié)合策略

集成學(xué)習(xí)中常用的結(jié)合策略有簡(jiǎn)單平均法、加權(quán)平均法、絕對(duì)多數(shù)投票法、相對(duì)多數(shù)投票法和加權(quán)投票法等。在本文的對(duì)比實(shí)驗(yàn)中，將提出方法的實(shí)驗(yàn)結(jié)果與采用簡(jiǎn)單平均法(averaging,AVE)的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比。

3 差分進(jìn)化算法

3.1 差分進(jìn)化算法

差分進(jìn)化(differential evolution,DE)算法是用于求解優(yōu)化問題的一種啟發(fā)式搜索算法[18～20]，具有較好的全局優(yōu)化能力，通過在群體上不斷進(jìn)行變異、交叉操作，產(chǎn)生中間個(gè)體，利用貪婪思想根據(jù)適應(yīng)度值選擇表現(xiàn)較好的個(gè)體作為下一代種群個(gè)體，經(jīng)過數(shù)次迭代找到問題的最優(yōu)解。

(1) 初始化種群個(gè)體

隨機(jī)產(chǎn)生m個(gè)個(gè)體，每個(gè)個(gè)體都是一個(gè)n維向量，n就是進(jìn)行優(yōu)化的參數(shù)個(gè)數(shù)，第i個(gè)個(gè)體的第j維初始化為

(6)

(2) 變異操作

對(duì)種群中的每個(gè)個(gè)體，變異操作就是根據(jù)隨機(jī)選擇的種群個(gè)體生成變異向量，變異向量有多種生成方式，這里選擇的方式為

(7)

(3) 交叉操作

交叉操作是為了增加種群的多樣性，將變異向量與種群個(gè)體交叉組成一個(gè)新的試驗(yàn)個(gè)體。交叉方式為

(8)

(4) 選擇操作

采用貪婪策略，交叉操作產(chǎn)生的試驗(yàn)個(gè)體和原來的種群個(gè)體進(jìn)行競(jìng)爭(zhēng)，根據(jù)適應(yīng)度值，將表現(xiàn)較優(yōu)的個(gè)體保留下來，作為下一代的種群個(gè)體。選擇方式為

(9)

3.2 基于差分進(jìn)化優(yōu)化分類器權(quán)重的集成分類 算法

本文提出基于差分進(jìn)化優(yōu)化分類器權(quán)重的集成分類算法，并應(yīng)用于中文情感分類。該方法通過差分進(jìn)化算法優(yōu)化集成方法中個(gè)體分類器的權(quán)重，以分類準(zhǔn)確率為適應(yīng)度值，尋找最優(yōu)的個(gè)體分類器權(quán)重組合，通過加權(quán)集成得到最終的分類模型。算法描述如下：

輸入：種群個(gè)體數(shù)目m；最大迭代次數(shù)G；變異因子F；交叉概率CR。

輸出：最優(yōu)權(quán)重組合w=(w1,w2,w3,w4,w5)；最優(yōu)適應(yīng)度值best_fit。

Step2：判斷當(dāng)前迭代次數(shù)g是否滿足g

Step4：g=g+1，返回Step2。

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

4.1 數(shù)據(jù)集

實(shí)驗(yàn)使用3個(gè)語料集：酒店評(píng)論(Hotel)、書籍評(píng)論(Book)和電腦評(píng)論(Notebook)。3個(gè)語料集均來自譚松波搜集整理的中文情感挖掘語料。3個(gè)語料集各有正向、負(fù)向評(píng)論文本2 000例。

文本預(yù)處理：使用中科院NLPIR2014漢語分詞系統(tǒng)對(duì)評(píng)論文本進(jìn)行分詞和詞性標(biāo)注，保留名詞、動(dòng)詞、形容詞和副詞共4種詞性的詞作為特征項(xiàng)；利用向量空間模型進(jìn)行文本表示，將每個(gè)文檔表示為一維向量形式；使用卡方統(tǒng)計(jì)方法進(jìn)行特征選擇，保留較為重要的特征項(xiàng)，過濾掉不重要的特征項(xiàng)。

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

4.2.1 個(gè)體分類器的實(shí)驗(yàn)結(jié)果分析

從數(shù)據(jù)集中各抽取正向、負(fù)向評(píng)論的80%作為訓(xùn)練集，20%作為測(cè)試集；用LR，LDA，NB，SVM，PLA在訓(xùn)練集上分別進(jìn)行訓(xùn)練；實(shí)驗(yàn)使用文本分類中較為常用的分類準(zhǔn)確率作為模型評(píng)價(jià)標(biāo)準(zhǔn)。

在情感分類任務(wù)中，對(duì)分類有影響的是具有情感極性的特征詞，而這類特征詞占總特征詞的比例較低，所以大部分特征詞是無用的，如果保留全部特征反而會(huì)干擾分類效果。

圖1～圖3分別給出了在3個(gè)數(shù)據(jù)集上，選擇不同的特征維度時(shí)，LR，LDA，NB，SVM，PLA的分類準(zhǔn)確率變化情況?？梢钥闯?，LR，NB，SVM，PLA在不同特征維度上的分類準(zhǔn)確率折線較為平穩(wěn)，在一定范圍內(nèi)波動(dòng)，而LDA的分類準(zhǔn)確率隨特征維度的增大呈下降趨勢(shì)。因?yàn)樘岢龅哪Ｐ褪且粋€(gè)集成模型，每種個(gè)體分類器的準(zhǔn)確率會(huì)影響到整體模型的準(zhǔn)確率，所以每種個(gè)體分類器的準(zhǔn)確率不能過低，否則會(huì)降低整個(gè)模型的分類效果。在Hotel數(shù)據(jù)集上，特征維度為800時(shí)，LDA的準(zhǔn)確率已經(jīng)低于80%，并且持續(xù)下降，所以數(shù)據(jù)集的特征維度不能過大。同時(shí)特征維度又不能太小，否則會(huì)影響分類效果。綜合以上因素，在后續(xù)實(shí)驗(yàn)中，選擇數(shù)據(jù)集的特征維度為800。

圖1 Hotel數(shù)據(jù)集上準(zhǔn)確率對(duì)比Fig.1 Accuracy comparison on Hotel datase

圖2 Book數(shù)據(jù)集上準(zhǔn)確率對(duì)比Fig.2 Accuracy comparison on Book dataset

圖3 Notebook數(shù)據(jù)集上準(zhǔn)確率對(duì)比Fig.3 Accuracy comparison on Notebook dataset

表2給出了5種分類器在3個(gè)數(shù)據(jù)集上進(jìn)行10次訓(xùn)練的平均分類準(zhǔn)確率?？梢钥闯?，在3個(gè)語料集上，LR和SVM表現(xiàn)最好。LR和SVM在Hotel語料集上的分類準(zhǔn)確率可以達(dá)到84%左右，在Book和Notebook語料集上可以達(dá)到90%左右。5種分類器在Book語料集和Notebook語料集上的分類效果都明顯優(yōu)于在Hotel語料集上的分類效果，這種分類效果的差異可能是由于語料文本本身的差異性所致。

表2 5種分類器在3種數(shù)據(jù)集上的分類準(zhǔn)確率Tab.2 Accuracy of five classifiers on three data sets (%)

4.2.2 差分進(jìn)化算法優(yōu)化個(gè)體分類器權(quán)重的實(shí)驗(yàn) 結(jié)果分析

使用差分進(jìn)化算法，根據(jù)2.2節(jié)中的算法描述，對(duì)5種個(gè)體分類器的權(quán)重進(jìn)行優(yōu)化。實(shí)驗(yàn)之前，設(shè)置種群數(shù)目m=50，最大迭代次數(shù)G=200，縮放因子F=0.5，交叉概率CR=0.5，在3個(gè)數(shù)據(jù)集上分別進(jìn)行實(shí)驗(yàn)。

圖4～圖6給出了在3個(gè)數(shù)據(jù)集上，分類模型的準(zhǔn)確率隨差分進(jìn)化算法迭代次數(shù)的變化情況?？梢钥闯觯S著迭代次數(shù)的增加，模型的分類準(zhǔn)確率也在逐漸上升，達(dá)到一定的迭代次數(shù)后，分類準(zhǔn)確率趨于穩(wěn)定，說明算法達(dá)到收斂狀態(tài)。差分進(jìn)化算法具有收斂速度快的優(yōu)點(diǎn)，經(jīng)過多次試驗(yàn)，算法的迭代次數(shù)在50代以內(nèi)已經(jīng)收斂。所以，在后續(xù)的對(duì)比實(shí)驗(yàn)中，將差分進(jìn)化算法的最大迭代次數(shù)設(shè)定為50次。

圖4 Hotel數(shù)據(jù)集上準(zhǔn)確率隨迭代次數(shù)變化Fig.4 The accuracy of the Hotel dataset varing with the number of iterations

圖5 Book數(shù)據(jù)集上準(zhǔn)確率隨迭代次數(shù)變化Fig.5 The accuracy of the Book dataset varing with the number of iterations

圖6 Notebook數(shù)據(jù)集上準(zhǔn)確率隨迭代次數(shù)變化Fig.6 The accuracy of the Notebook dataset varing with the number of iterations

使用基于差分進(jìn)化優(yōu)化分類器權(quán)重的集成分類方法(DE)在3個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，經(jīng)過多次運(yùn)行，調(diào)試參數(shù)，當(dāng)種群數(shù)目m=40，縮放因子F=0.9，交叉概率CR=0.5時(shí)，分類效果最好。將實(shí)驗(yàn)結(jié)果與單個(gè)分類方法和簡(jiǎn)單平均方法(AVE)的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，對(duì)比情況如表3所示。

表3 各個(gè)分類方法的準(zhǔn)確率對(duì)比Tab.3 Accuracy comparison of each classification method (%)

從表3的實(shí)驗(yàn)結(jié)果可以看出，使用差分進(jìn)化算法優(yōu)化個(gè)體分類器權(quán)重后的分類模型(DE)在3個(gè)語料集上的分類效果都有所提高，與簡(jiǎn)單平均法方法(AVE)相比，分類準(zhǔn)確率提高了2%左右。

5 結(jié)束語

差分進(jìn)化算法是在遺傳算法(genetic algorithm,GA)的思想上提出來的，與遺傳算法相比，差分進(jìn)化算法具有參數(shù)少、容易實(shí)現(xiàn)、收斂速度快的優(yōu)點(diǎn)。因此，文章提出一種基于差分進(jìn)化優(yōu)化個(gè)體分類器權(quán)重的集成分類方法。選擇5種個(gè)體分類器，用差分進(jìn)化算法優(yōu)化分類器權(quán)重，然后通過加權(quán)集成得到最終的分類模型，并在3個(gè)領(lǐng)域的評(píng)論文本上進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，這種方法的分類效果較加權(quán)投票方法有明顯提高。

對(duì)情感分類的研究目前集中在對(duì)商品評(píng)論文本分類上，即判斷文本表達(dá)的是支持還是否定的態(tài)度。在后續(xù)工作中，將進(jìn)一步研究多類別情感分析,例如，判斷一個(gè)文本表達(dá)的情感是喜歡、高興、傷心、憤怒等，從而更準(zhǔn)確地提取文本中隱含的主觀情感。