劉 林，劉三女牙，劉 智，鐵 璐

(華中師范大學(xué)國(guó)家數(shù)字化學(xué)習(xí)工程技術(shù)研究中心，武漢430079)

基于隨機(jī)主元分析算法的BBS情感分類研究

劉 林，劉三女牙，劉 智，鐵 璐

(華中師范大學(xué)國(guó)家數(shù)字化學(xué)習(xí)工程技術(shù)研究中心，武漢430079)

針對(duì)論壇(BBS)中文本的情感分類問題，提出一種改進(jìn)的隨機(jī)子空間算法。挖掘特征空間中的分類信息，在生成子空間的過程中，利用權(quán)重函數(shù)對(duì)特征進(jìn)行分類能力評(píng)估，以較大概率選擇分類能力較好的特征維度，保證分類精度；擴(kuò)大選擇的子空間維度，選擇具有分類能力的特征，通過主元分析對(duì)子空間進(jìn)行降維，保證算法效率和子空間多樣性。實(shí)驗(yàn)結(jié)果表明，該算法分類精度達(dá)到91.3%，比基準(zhǔn)算法具有更好的性能穩(wěn)定性。

情感分析；集成學(xué)習(xí)；隨機(jī)子空間方法；主元分析；支持向量機(jī)；基分類器

1 概述

網(wǎng)絡(luò)的迅速發(fā)展，給人們提供了新的交流方式和互動(dòng)空間，極大地影響和改變著人們的生活。論壇(Bulletin Board System, BBS)作為互聯(lián)網(wǎng)上最著名的服務(wù)項(xiàng)目之一，它以其獨(dú)特的信息交流和互動(dòng)方式，擁有龐大的用戶群體。目前，隨著互聯(lián)網(wǎng)的迅擴(kuò)張和蔓延，國(guó)內(nèi)外對(duì)BBS的研究也與日俱增。在國(guó)內(nèi)眾多對(duì)BBS的研究中，大部分集中在對(duì)BBS技術(shù)、應(yīng)用以及影響等方面，較少關(guān)注于BBS情感的研究。國(guó)外對(duì)BBS的直接研究也很少，而且這些研究?jī)H關(guān)注于特定的話題或內(nèi)容，如流產(chǎn)、槍支管制等；間接研究主要集中在對(duì)網(wǎng)絡(luò)社會(huì)、虛擬社區(qū)、網(wǎng)絡(luò)安全方面(如Dark Web project)。如何利用豐富的BBS資源，對(duì)用戶表達(dá)的主觀情感進(jìn)行研究，成為新的研究問題。

與普通的網(wǎng)絡(luò)文本一樣，BBS文本亦具有口語(yǔ)化、碎片化、非結(jié)構(gòu)化等特點(diǎn)；同時(shí)又有話題寬泛、互動(dòng)性強(qiáng)等特點(diǎn)，這與局限于特定領(lǐng)域的(例如新聞?shì)浾?、商品評(píng)價(jià)、影視評(píng)價(jià)等)的文本情感分類有些不同。簡(jiǎn)單地說，文本情感分類通常是指辨識(shí)文本中表現(xiàn)出的立場(chǎng)、觀點(diǎn)、看法、情緒等主觀信息，對(duì)文本的情感傾向做出類別判斷[1-2]。從20世紀(jì)90年代開始，文本情感研究在國(guó)內(nèi)外受到了普遍的關(guān)注，并逐漸成為自然語(yǔ)言處理領(lǐng)域中的一個(gè)研究熱點(diǎn)。其中基于機(jī)器學(xué)習(xí)的研究比較成熟，也很好地應(yīng)用于文本情感分類，具有代表性的算法有支持向量機(jī)(Support Vector Machine, SVM)、K-近鄰法(K-Nearest Neighbor, KNN)、樸素貝葉斯(Naive Bayesian, NB)等。文獻(xiàn)[3-4]分別在英文、中文語(yǔ)言環(huán)境下進(jìn)行比較研究表明，SVM被認(rèn)為是穩(wěn)定性和分類效果較好的算法。但是，這些研究基本都以單分類器方法為主，較少采用集成學(xué)習(xí)的方法。在通常情況下，集成學(xué)習(xí)通過多個(gè)分類器的有效組合，獲得比單分類器更好性能。

綜上原因，本文選擇用集成學(xué)習(xí)的算法對(duì)BBS進(jìn)行情感分類研究，通過辨識(shí)BBS文本中的情感傾向，分析用戶情緒變化。

2 RSM算法

為提高分類效果，希望分類器能盡可能充分利于所有的具有分類能力的特征，但是在文本分類中，維度災(zāi)難是不可忽視的問題，過高的特征維度會(huì)花費(fèi)成倍的時(shí)間和空間代價(jià)。如何在特征維度和效率之間進(jìn)行平衡，隨機(jī)子空間方法(Random Subspace M ethod, RSM)[5-10]是一種較好的方法。它從高維特征空間隨機(jī)選取生成低維的子空間RS來分別構(gòu)建基分類器(Base Classifier, BC)，最后通過一定的組合規(guī)則將各基分類器結(jié)果進(jìn)行集成，能有效地提升分類精度。RSM不僅受維數(shù)災(zāi)難的影響較小，還能充分利用高維度特征帶來的分類能力提高，且能避免小樣本問題的發(fā)生[5]，在多種分類任務(wù)中都顯著提高了學(xué)習(xí)系統(tǒng)的泛化能力，是一種非常有效的集成學(xué)習(xí)方法。

在隨機(jī)子空間中，子空間的維度(m)和基分類器個(gè)數(shù)(n) 是2個(gè)主要的參數(shù)。文獻(xiàn)[9-10]都對(duì)這2個(gè)參數(shù)進(jìn)行了研究，表示適當(dāng)?shù)膍值和較小的n值即可獲得較優(yōu)的效果。Kuncheva還認(rèn)為學(xué)者在RSM對(duì)弱分類器的集成研究較多，而對(duì)強(qiáng)分類器的研究還不普遍；然而，與SVM等強(qiáng)分類器的集成不僅可以很好地提高分類精度，還可以解決較高特征維度的問題。

3 隨機(jī)主元分析算法

在RSM中，子空間生成過程是隨機(jī)選擇的，即所有特征都是相同的概率被選中。考慮最差的情況，如果生成子空間時(shí)選中的大部分是分類能力較差的特征，在此基礎(chǔ)上進(jìn)行訓(xùn)練和集成，可能需要較長(zhǎng)的時(shí)間和較多的基分器才能獲得理想的較果。如果能在選擇的過程中，實(shí)施某種策略，將具有良好分類能力的特征優(yōu)先選擇，較差的特征以較小的概率被選中，效果將會(huì)更好。受文獻(xiàn)[11]啟發(fā)，提出一種將RSM與主元分析相融合的算法，即隨機(jī)主元分析(Random Principal Component Analysis, RPCA)算法。其主要思想是選擇一種權(quán)重算法，對(duì)特征的分類能力進(jìn)行評(píng)估，將結(jié)果作為特征被選中的概率。在子空間生成中，盡可能多地選擇具有分類能力的原始特征，保持足夠的分類能力和多樣性；為減少增加的子空間維度帶來的訓(xùn)練時(shí)間和存儲(chǔ)空間的開銷，選擇主元分析(PCA)對(duì)子空間進(jìn)行降維處理，RPCA算法描述如下：

輸入 數(shù)據(jù)集D，特征集T，特征維度p，子空間維度m，子空間數(shù)目n

輸出 十折交叉分類結(jié)果

Step1根據(jù)十折交叉驗(yàn)證，劃分訓(xùn)練集和測(cè)試集。

Step2用權(quán)重函數(shù)對(duì)特征tk(k=1,2,…,p)分類能力進(jìn)行計(jì)算，記為wk，對(duì)W (wk∈W)進(jìn)行從大到小排序。

Step3循環(huán)生成n個(gè)子空間RS，每個(gè)子空間生成過程如下：

(2)產(chǎn)生一個(gè)[0,1)范圍內(nèi)隨機(jī)數(shù)r；

(4)設(shè)定wk=0；

(5)循環(huán)步驟(1)～步驟(4)，直至m個(gè)特征全部選擇完成。

Step4用PCA算法對(duì)RSi進(jìn)行特征壓縮，選擇貢獻(xiàn)率總和大于99%以上特征形成子空間RSi’。

Step5對(duì)RSi’訓(xùn)練一個(gè)基分類器BCi并進(jìn)行分類。

Step6用多數(shù)投票法對(duì)分類結(jié)果進(jìn)行集成。

Step7循環(huán)完成十折過程，統(tǒng)計(jì)識(shí)別精度。

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集與預(yù)處理

本文實(shí)驗(yàn)數(shù)據(jù)集來自華中師范大學(xué)校園BBS——華大博雅。該論壇擁有獨(dú)特穩(wěn)定的大學(xué)生用戶群體，實(shí)名用戶66 00 0多人，帖子數(shù)450多萬(wàn)條，對(duì)研究大學(xué)生心理健康發(fā)展有重大的意義。經(jīng)過分析整理，選擇正面和負(fù)面情感樣本集各338個(gè)，數(shù)據(jù)集的預(yù)處理包括統(tǒng)一BBS標(biāo)簽字符、特殊HTML代碼替換、繁簡(jiǎn)轉(zhuǎn)換、縮略指代還原等。最終得到的數(shù)據(jù)集信息如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集相關(guān)信息

從表1可以得知，負(fù)面數(shù)據(jù)集在字?jǐn)?shù)和詞匯方面都比正面數(shù)據(jù)集豐富，這與實(shí)際的用戶群體相關(guān)，一方面喜好發(fā)貼交流或情感表達(dá)；另一方面在表達(dá)負(fù)面情感時(shí)，更具有文飾性和爆發(fā)性，較難捉摸。

4.2 實(shí)驗(yàn)流程與設(shè)置

進(jìn)行情感分類之前，首先需要把數(shù)據(jù)集中的文本表示成特征，可以采用反映文本語(yǔ)言學(xué)特征的元素來表示特征，如使用詞、ngram、詞組和概念等[4]。其中，ngram具有預(yù)處理簡(jiǎn)單、語(yǔ)種無(wú)關(guān)、蘊(yùn)含細(xì)粒度特征和部分高層語(yǔ)法信息，被廣泛采用。接著，通過特征選擇，去除不相關(guān)或冗余的特征，實(shí)現(xiàn)特征降維，提高效率和分類精度。特征選擇結(jié)果直接影響分類器的精度和泛化性能，文獻(xiàn)[4]研究表明，信息增益(IG)在中文語(yǔ)境下具有較好的效果。實(shí)驗(yàn)中將聯(lián)合ngram(n分別取1，2，3，4)4種特征表示，通過信息增益選擇各排在前1 5 00位的特征進(jìn)行融合作為初始特征集，然后通過RPCA算法進(jìn)行分類實(shí)驗(yàn)，實(shí)驗(yàn)流程如圖1所示。

圖1 實(shí)驗(yàn)流程

為驗(yàn)證RSM和RPCA算法的有效性，實(shí)驗(yàn)設(shè)計(jì)如下：實(shí)驗(yàn)1考察RSM集成算法與具有代表性單分類器算法(SVM、KNN、NB)進(jìn)行比較；實(shí)驗(yàn)2將RPCA與RSM集成算法進(jìn)行對(duì)比。實(shí)驗(yàn)中采用識(shí)別精度作為比較指標(biāo)，即測(cè)試集中被正確分類的樣本占測(cè)試集樣本總量的比例。集成實(shí)驗(yàn)中基分類器算法選用的是臺(tái)灣大學(xué)林智仁教授的Libsvm[12]，主要參數(shù)是：s=1，d=2，c=1.5。RPCA中對(duì)特征tk分類能力計(jì)算采用文獻(xiàn)[2]的Fisher準(zhǔn)則：

其中，a，b表示為數(shù)據(jù)集中正面、負(fù)面文檔數(shù)；a1，b1表示包含特征tk的正面、負(fù)面文檔數(shù)；dP,i(tk)表示特征tk是否出現(xiàn)在正面第i個(gè)文檔中，出現(xiàn)則值為1，否則為0；同樣，dN,j(tk)表示表示特征tk是否出現(xiàn)在負(fù)面第j個(gè)文檔中。

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

為避免初始特征集中分類能力過低的特征對(duì)單分類器的影響，實(shí)驗(yàn)1中對(duì)初始特征集成行二次選擇，選擇前3 000維進(jìn)行KNN，NB，SVM單分類器實(shí)驗(yàn)；對(duì)于集成實(shí)驗(yàn)，參數(shù)為m=3 000、n=50。實(shí)驗(yàn)分別進(jìn)行5次，取最好精度作為最后結(jié)果，如表2所示。

表2 不同分類算法精度比較 %

從表2中可以看出，在3種單分類器算法中，SVM精度明顯高于其他2種算法；在集成算法中，分類精度都有所提高。其中，對(duì)KNN提高最大，有近4.4%。而SVM最小，僅有略大于0.9%。原因在于，SVM本身是一個(gè)強(qiáng)分類器，在文本情感分類任務(wù)中效果較好，且分類精度在超過89%的情況下，精度提升的空間有限。實(shí)驗(yàn)1同時(shí)也表明RSM是一種有效的集成學(xué)習(xí)算法。實(shí)驗(yàn)2集中對(duì)比RSM 與RPCA的集成效果，其中參數(shù)中m=4 200，將實(shí)驗(yàn)過程中獲得的單個(gè)分類器各自的精度和集成精度如圖2所示。

圖2 R SM與RPCA精度比較

從圖2可以看出，RSM和RPCA算法都能有效地提高分類精度，同時(shí)增加分類的穩(wěn)定性；隨著子空間數(shù)目的增加，集成精度逐漸趨于穩(wěn)定，僅在小范圍內(nèi)波動(dòng)。在RSM中，由于m值的變大引入了較多分類能力較低的特征，使得表現(xiàn)出的分類效果較實(shí)驗(yàn)1的最好效果差一點(diǎn)，而RPCA算法中由于進(jìn)行了子空間選擇和PCA降維，提高算法執(zhí)行速度，同時(shí)單個(gè)分類器的精度相應(yīng)有所提高；在基分類器個(gè)數(shù)大于20的時(shí)候，即獲得比較穩(wěn)定的效果，而RSM方法在基分類器數(shù)接近60時(shí)，才較為穩(wěn)定；但受限于本例中較小樣本數(shù)和投票法集成策略，在某些時(shí)刻，集成精度都有小范圍的突變，進(jìn)一步的工作中考慮改進(jìn)集成策略(如加權(quán)投票法等)來消除或減小突變的影響。

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

針對(duì)BBS中文本的情感分類問題，本文提出一種改進(jìn)的隨機(jī)子空間算法，實(shí)驗(yàn)結(jié)果表明，RPCA算法對(duì)本文BBS數(shù)據(jù)集情感分類有較好的效果，能有效地提高分類精度和穩(wěn)定性。同時(shí)，注意到本文雖然使用的是真實(shí)標(biāo)注語(yǔ)料，但數(shù)據(jù)集規(guī)模較小，實(shí)驗(yàn)的結(jié)果也僅能作為特殊個(gè)體甄別的參考。在特征表示的過程中，還有較多的BBS風(fēng)格特征沒有充分利用(例如BBS標(biāo)簽、表情、字號(hào)字色等)，而此部分信息在情感表達(dá)上比較重要。在對(duì)識(shí)別錯(cuò)誤的語(yǔ)料分析看出，本文方法對(duì)含幽默和反語(yǔ)等表達(dá)手法的語(yǔ)料識(shí)別還存在不足。在下一步的工作中嘗試加入風(fēng)格特征，借鑒語(yǔ)義的方法，以獲得更好的識(shí)別效果。

[1] Pang B, Lee L. Opinion Mining and Sentiment A nalysis[J]. Foundations and Trends in Information Retrieval, 2008, 2(1): 1-135.

[2] 王素格. 基于Web的評(píng)論文本情感分類問題研究[D]. 上海:上海大學(xué), 2008.

[3] Pang B, Lee L, V aithyanathan S. Thumbs up? Sentiment Classification Using Machine Learning Techniques[C]//Proc. of ACL’02. Morristown, USA: [s. n.], 2002: 222-228.

[4] 唐慧豐, 譚松波, 程學(xué)旗. 基于監(jiān)督學(xué)習(xí)的中文情感分類技術(shù)比較研究[J]. 中文信息學(xué)報(bào), 2007, 21(6): 88-94.

[5] Kam H T, Labs B, Hill M. The Random Subspace Method for Constructing Decision Forests[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998, 20(8): 832-843.

[6] Xia Rui, Zong Chengqing, Li Shoushan. Ensemble of Feature Sets and C lassification A lgorithms for Sentiment C lassification[J]. Information Sciences, 2011, 181(6): 1138-1152.

[7] 黎冬媛, 劉 智, 劉三女牙. 采用半隨機(jī)特征采樣算法的中文書寫紋識(shí)別研究[J]. 計(jì)算機(jī)科學(xué), 2013, 40(2): 120-123.

[8] Liu Zhi, Yang Zongkai, Liu Sanya. A Novel Random Subspace Method for Online W riteprint Identification[J]. Journal of Computers, 2012, 12(7): 2997-3004.

[9] Gangeh M J, Kamel M S, Duin P W. Ra ndom Subspa ce Method in T ext Categorization[C]//Proc. of the 20th International Co nference o n P attern Reco gnition. Istanbul, Turkey: [s. n.], 2010: 478-486.

[10] Kuncheva L I, Rodriguez J J, Plumpton C O. Random Subspace Ense mbles for fMRI Classification[J]. IEEE Transactions on Medical Imaging, 2010, 29(2): 531-542.

[11] Yang Jinnmin, Kuo Borchen, Yu Paota. A Dynamic Subspace Method for Hyperspectral Image Classication[J]. IEEE Transactions on Geoscience and Remote Sensing, 2010, 48(7): 2840-2853.

[12] Chang Chih-Chung, Lin Chih-Jen. LI BSVM: A Library for Support Vector Machines[J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2(3): 1-27.

編輯 索書志

Study on BBS Sentiment Classification Based on Random Principal Component Analysis Algorithm

LIU Lin, LIU San-ya, LIU Zhi, TIE Lu

(National Engineering Research Center for E-Learning, Central China Normal University, Wuhan 430079, China)

For Bulletin Board System(BBS) sentiment classification issues, an improved Random Subspace Method(RSM) is proposed. This method tries to make full us e of the discriminative informa tion in the high dimensional feature space. In the process of g enerating subspaces, on the one hand, a weighting function is used to evaluate classification abilities of the features, and better ones are chosen to ensure accuracy of classification with a higher pr obability, on th e other hand, the size of the subspa ce is enlar ged, principal component analysis is used to reduce the dimension of the sub space, and they ensure the efficiency and diversity. Experimental results show that the proposed algorithm obtains the best accuracy of 91.3% , which is higher than the conventional Random Subspace Method(RSM).

sentiment analysis; ensemble learni ng; Random Subspace Method(RSM); principal c omponent analysis; Support Vector Machine(SVM); Base Classifier(BC)

10.3969/j.issn.1000-3428.2014.05.039

國(guó)家“十二五”科技支撐計(jì)劃基金資助項(xiàng)目(2011BAK08B03)；新世紀(jì)優(yōu)秀人才支持計(jì)劃基金資助項(xiàng)目(NCET-11-0654)；“核高基”重大專項(xiàng)(2010ZX01045-001-005)；華中師范大學(xué)中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金資助項(xiàng)目(CCNU09A02006)。

劉 林(1983－)，男，博士研究生，主研方向：情感識(shí)別，數(shù)據(jù)挖掘；劉三女牙，教授、博士；劉 智，博士研究生；鐵 璐，碩士研究生。

2013-03-04

2013-05-24E-mail：liulinhere@163.com

1000-3428(2014)05-0188-04

A

TP18