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

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

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

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

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

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

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

1 概述

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

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

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

2 RSM算法

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

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

3 隨機主元分析算法

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果與分析

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

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

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

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

4.2 實驗流程與設(shè)置

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

圖1 實驗流程

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

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

4.3 實驗結(jié)果與分析

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

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

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

圖2 R SM與RPCA精度比較

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

5 結(jié)束語

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

[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的評論文本情感分類問題研究[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é)報, 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]. 計算機科學(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

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

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

2013-03-04

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

1000-3428(2014)05-0188-04

A

TP18