鄭文靜，李 雷

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210023)

基于聚類核的半監(jiān)督情感分類算法研究

鄭文靜，李 雷

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210023)

在互聯(lián)網(wǎng)快速發(fā)展的今天，人類已經(jīng)進(jìn)入“大數(shù)據(jù)”時代，其中文本數(shù)據(jù)作為人類知識的載體，對于人類的進(jìn)步與發(fā)展意義重大。如何運(yùn)用大量未標(biāo)記樣本來提升文本情感分類的精度，也變得愈發(fā)重要。將半監(jiān)督學(xué)習(xí)中的聚類核算法應(yīng)用到情感分類問題中，給出基于聚類核的半監(jiān)督情感分類算法。在標(biāo)記樣本和未標(biāo)記樣本上，建立加權(quán)無向圖，求解聚類核，然后將該核函數(shù)用于SVM的情感分類器的訓(xùn)練上，完成情感分類工作。該方法直接將未標(biāo)記樣本所蘊(yùn)含的信息融合到核中，不需要建立多個分類器，有效利用了未標(biāo)記樣本。實驗結(jié)果表明，CKSVM算法在分類精度上明顯優(yōu)于基于Self-learning SVM和Co-training SVM的半監(jiān)督情感分類算法，且在不同數(shù)據(jù)集上都有較好的適應(yīng)性。

半監(jiān)督學(xué)習(xí)；聚類核；圖；情感分類

0 引 言

隨著互聯(lián)網(wǎng)的發(fā)展,越來越多的消費(fèi)者在網(wǎng)上發(fā)表評論[1]，這些評論以主觀的文本形式表達(dá)了消費(fèi)者對于消費(fèi)產(chǎn)品或服務(wù)的滿意度。這不僅可以幫助其他消費(fèi)者做出更好的判斷，還可以幫助制造商跟蹤和管理這些意見[2]。在自然語言處理(NLP)中，情感分類作為一種特殊的文本分類問題正受到越來越多的重視[3-6]。情感分類的標(biāo)準(zhǔn)是挖掘文本中蘊(yùn)含的極性情感態(tài)度，如“positive” or “negative”,“thumbs up” or “thumbs down”,“favorable” or “unfavorable”[7]，而不是主題。如今，情感分類技術(shù)廣泛應(yīng)用于商業(yè)智能系統(tǒng)、推薦系統(tǒng)、公眾的意見收集和挖掘系統(tǒng)等等。在上述領(lǐng)域，存在著豐富的未標(biāo)記文本數(shù)據(jù)，標(biāo)記的文本數(shù)據(jù)很少，且需要通過人工標(biāo)注獲得。這使得使用許多傳統(tǒng)的算法訓(xùn)練數(shù)據(jù)的代價過高，因為這些分類器要求足夠的標(biāo)記數(shù)據(jù)來保證實現(xiàn)高精度。

為使用未標(biāo)記樣本提高情感分類的精度，提出一種基于聚類核的半監(jiān)督情感分類算法?；诰垲惣僭O(shè)，Chapelle提出聚類核概念[8]，使用核函數(shù)，而不是明確的特征向量，重新表示給定的數(shù)據(jù)，以反映未標(biāo)記數(shù)據(jù)透露的結(jié)構(gòu)。首先通過bag-of-word模型將數(shù)據(jù)集中的評價轉(zhuǎn)化為向量形式，并將這些向量作為圖的頂點，將各評價間的相似度作為邊上的權(quán)重，構(gòu)建加權(quán)無向圖。然后引入線性轉(zhuǎn)換函數(shù)，將該圖上的相似矩陣重新表示，使得在同一集群中兩點間的距離更小，建立半監(jiān)督聚類核，并將其用于SVM分類器的訓(xùn)練上。實驗結(jié)果表明，該算法分類精度較高，且在分類精度上優(yōu)于基于Self-learning SVM和基于Co-training SVM的半監(jiān)督情感分類算法。

1 相關(guān)研究

1.1 情感分類

一般來說，情感分類技術(shù)可分為基于機(jī)器學(xué)習(xí)(Machine Learning,ML)的情感分類方法、基于詞典的方法和混合方法[9]，具體見圖1。

圖1 情感分類算法

基于機(jī)器學(xué)習(xí)的情感分類算法，主要是經(jīng)典機(jī)器學(xué)習(xí)算法結(jié)合語義特征的應(yīng)用[10]，大體上可分為基于監(jiān)督學(xué)習(xí)的情感分類方法、基于半監(jiān)督學(xué)習(xí)的情感分類方法和基于無監(jiān)督學(xué)習(xí)的情感分類方法?；诒O(jiān)督學(xué)習(xí)的情感分類方法依賴于已存在的標(biāo)記訓(xùn)練樣本，包括概率分類器[11-13]、線性分類器[14-18]、決策樹分類器[19-20]和基于規(guī)則的分類器[10,21]等模型。2002年，Pang等[6]率先使用監(jiān)督式機(jī)器學(xué)習(xí)方法中的支持向量機(jī)(Support Vector Machine,SVM)對電影評論進(jìn)行情感分類，并且對比了樸素貝葉斯(Na?ve Bayes,NB)、最大熵分類法(Maximum Entropy Classification,MEC)和SVM三種監(jiān)督學(xué)習(xí)算法在情感分類問題中的性能[6]。由于情感分類問題一般是將文檔劃分到一定數(shù)量的預(yù)定義類別中，且標(biāo)記樣本較難獲得[9]，因此基于無監(jiān)督學(xué)習(xí)的情感分類方法引起了廣泛關(guān)注。例如，Turney使用PMI-IR(Pointwise Mutual Information and Information Retrieval)方法進(jìn)行消費(fèi)者評論的情感分類[22]。

半監(jiān)督學(xué)習(xí)使用少量標(biāo)記樣本和大量未標(biāo)記樣本，可以有效提高分類精度，大大減少人工標(biāo)記的工作量，因此越來越多的研究者將其與情感分類問題相結(jié)合，取得了較好效果。Goldberg和Zhu[23]提出了一種基于圖的半監(jiān)督學(xué)習(xí)算法來處理評分系統(tǒng)的情感分析問題，其中不同數(shù)值的評分對應(yīng)著給定的情感。Sindhwani和Melville[24]將文本先驗信息同未標(biāo)記樣本相結(jié)合，給出了一種半監(jiān)督情感分類算法。Zhou等運(yùn)用主動學(xué)習(xí)來解決半監(jiān)督情感分類問題，提出了主動深度網(wǎng)絡(luò)方法(Active Deep Networks,ADN)[25]，并進(jìn)一步提出了模糊深度置信網(wǎng)絡(luò)法(Fuzzy Deep Belief Networks,FDBN)[26]?；诨炯僭O(shè)：具有相似情感傾向的情感詞有較高的概率出現(xiàn)在同樣情感傾向的消費(fèi)者評論中,文獻(xiàn)[27]提出一種基于特征聚類的半監(jiān)督式情感分類方法。該方法根據(jù)情感特征的共現(xiàn)關(guān)系構(gòu)建共現(xiàn)矩陣，利用spectral聚類方法生成分類用的擴(kuò)展特征，結(jié)合原有訓(xùn)練域內(nèi)的分類特征來訓(xùn)練新的情感分類器形成兩個分類器，共同完成最后的情感分類工作。

1.2 聚類核

聚類假設(shè)[28]是半監(jiān)督學(xué)習(xí)的核心，是建立目標(biāo)函數(shù)與未標(biāo)記樣本分布之間關(guān)系的樞紐[5]，指的是同一聚類中的樣本點很可能具有相同的類別標(biāo)簽，即在高密度區(qū)域里，如果某兩個點可以通過區(qū)域內(nèi)某條路徑相連接，那么這兩個樣本點的標(biāo)簽相同的可能性比較大。而聚類核[8]依賴聚類假設(shè)思想，使用核函數(shù)重新表示給定的數(shù)據(jù)，從而將未標(biāo)記數(shù)據(jù)中的結(jié)構(gòu)加入到分類器中[29]。其主要思想在于改變距離度量，使同一群集中兩點挨得更緊，距離更小[30]。

構(gòu)造聚類核的整體框在文獻(xiàn)[8]中提出。本質(zhì)上，聚類核來源于核矩陣的能量本征譜，其中兩種比較典型的方法是隨機(jī)游走核[8]及譜聚類核[8]。在一個標(biāo)準(zhǔn)化且對稱化的隨機(jī)游動過程中，隨機(jī)游走核是它的t步轉(zhuǎn)移矩陣。Szummer[31]指出，在以xi為頂點的圖上，隨機(jī)游動過程的轉(zhuǎn)移矩陣可以是RBF核，由此定義的隨機(jī)游走，就可以通過一步轉(zhuǎn)移矩陣求解出t步隨機(jī)游走核。譜聚類核的主要思想依據(jù)是譜聚類，即在特征空間中，計算出樣本間相似度矩陣的譜分解后，就可以重新表示樣本點了。這樣一來，位于同一聚類區(qū)域中的樣本點更加緊湊地分布在新的空間中。文中將聚類核算法應(yīng)用到情感分類中，在樣本集上求解出核函數(shù)后，與SVM分類器的訓(xùn)練相結(jié)合，提出了基于半監(jiān)督聚類核的情感分類算法(ClusterKernelbasedSVMforsentimentclassification，CKSVM)。

2 基于聚類核的半監(jiān)督情感分類算法

為了更好地滿足聚類假設(shè)，減少分類器的使用，文中提出基于聚類核的半監(jiān)督情感分類算法。在構(gòu)建基于文本數(shù)據(jù)集的加權(quán)無向圖之后，使用線性分段轉(zhuǎn)換函數(shù)將圖上的相似矩陣重新表示，利用該半監(jiān)督聚類核訓(xùn)練的基于SVM情感分類器有著更好的分類效果。

為了構(gòu)建可以給出樣本集中xi類別的分類器，需要得到?jīng)Q策函數(shù)f(x)：f:X→Y。

各頂點間邊的權(quán)重通過以下相似矩陣來度量。相似矩陣W為：

(1)

其中，xi和xj表示兩個評價的特征向量；d(xi,xj)取cos(xi,xj)；σ為給定的控制參數(shù)。

接下來計算對角矩陣D，Dii=∑jWij，其元素是W的行和，可以得到圖拉普拉斯矩陣L=D-W。L的譜分解為：

(2)

其中，φi為L的特征向量；λi≥0為L的特征值。

(3)

從上述描述，可以得到CKSVM的步驟：

Step1:根據(jù)bag-of-word模型，將文本數(shù)據(jù)表示為向量，進(jìn)行初步的特征提取之后，得到標(biāo)記樣本集T和未標(biāo)記樣本集U的特征矩陣M，M∈im×n。其中，m為訓(xùn)練數(shù)據(jù)集的文本個數(shù)，n為特征項的個數(shù)。

Step2:根據(jù)式(2)計算相似矩陣W。

Step3:計算對角矩陣Dii=∑jWij。

Step7:使用上述聚類核訓(xùn)練SVM分類器，得到基于半監(jiān)督聚類核的情感分類器，對數(shù)據(jù)集上的評價提取出的特征向量進(jìn)行訓(xùn)練。

3 實 驗

為了驗證CKSVM算法的有效性，分別在數(shù)據(jù)集上進(jìn)行測試。并且與較早實現(xiàn)的基于Self-learningSVM和基于Co-trainingSVM的半監(jiān)督情感分類算法進(jìn)行比較，這兩種算法的實現(xiàn)過程見文獻(xiàn)[32]。算法均在32位Python集成環(huán)境Anaconda中進(jìn)行，調(diào)用了多個用于科學(xué)計算的Python庫，如numpy、sk-learn等。都選用交叉驗證法找出的最優(yōu)參數(shù)。

3.1 數(shù)據(jù)集選取及預(yù)處理

(1)文中選取movie-reviews影評數(shù)據(jù)集和20 Newsgroups數(shù)據(jù)集。其中，movie-reviews數(shù)據(jù)集由康奈爾大學(xué)(Cornell)提供，包括2 000條電影評價，其中肯定和否定態(tài)度的各1 000條。目前影評庫被廣泛應(yīng)用于各種粒度的(如詞語、句子和篇章級)情感分析研究中。20 Newsgroups數(shù)據(jù)集包括接近20 000種報紙的數(shù)據(jù)，每種報紙選出1 000篇文章。文章的主題包括計算機(jī)、政治、宗教、運(yùn)動和科學(xué)。

(2)文中對英文文本的預(yù)處理，主要依賴Python的NLTK庫。NLTK是用來處理和自然語言處理相關(guān)事件的工具包，包括分詞(tokenize)、詞性標(biāo)注(POS)、文本分類等現(xiàn)成工具。文中將數(shù)據(jù)集中的文本進(jìn)行分詞，用VSM模型將一個個的文本表示成向量。

3.2 實驗結(jié)果分析

對movie-reviews影評數(shù)據(jù)集，在不同訓(xùn)練樣本比例情況下，各半監(jiān)督情感分類算法的分類精度如表1所示。

表1 movie-reviews影評數(shù)據(jù)集三種半監(jiān)督情感分類算法的分類精度

三種算法在movie-reviews數(shù)據(jù)集上的分類準(zhǔn)確度如圖2所示。

圖2 三種半監(jiān)督情感分類算法在movie-

從圖2可以看出，隨著標(biāo)記樣本比例的增加，各半監(jiān)督情感分類算法的分類準(zhǔn)確度都有提升，其中CKSVM算法提升最快，且其分類精度幾乎一直高于基于Self-learning SVM和基于Co-training SVM的半監(jiān)督情感分類算法，說明CKSVM算法更好地運(yùn)用了未標(biāo)記樣本中的信息。

對20 Newsgroups數(shù)據(jù)集，在不同訓(xùn)練樣本比例情況下，各半監(jiān)督情感分類算法的分類精度如表2所示。

三種算法在20 Newsgroups數(shù)據(jù)集上的分類準(zhǔn)確度如圖3所示。

從圖3可以看出，隨著標(biāo)記樣本比例的增加，各半監(jiān)督情感分類算法的分類準(zhǔn)確度都有提升，其中CKSVM算法提升最快，說明在該數(shù)據(jù)集上CKSVM算法也同樣很好地運(yùn)用了未標(biāo)記樣本中的信息。另外，由于20 Newsgroups數(shù)據(jù)集更加復(fù)雜，三種算法的分類精度都有下降，但是CKSVM下降最少，說明CKSVM有較好的適應(yīng)性，在不同數(shù)據(jù)集上依然可以得到較好的結(jié)果。

表2 20 Newsgroups數(shù)據(jù)集三種半監(jiān)督情感分類算法的分類精度

圖3 三種半監(jiān)督情感分類算法在20 Newsgroups

4 結(jié)束語

文中提出了基于聚類核的半監(jiān)督情感分類算法。該方法直接將未標(biāo)記樣本所蘊(yùn)含的信息融合到核中，可以直接用于SVM的情感分類器的訓(xùn)練上，有效利用了未標(biāo)記樣本中蘊(yùn)含的信息。在兩個數(shù)據(jù)集上的實驗表明，該算法在分類精度上明顯優(yōu)于基于self-learning SVM和Co-training的半監(jiān)督情感分類算法，且CKSVM在兩個數(shù)據(jù)集上表現(xiàn)都最好，有較好的適應(yīng)性。

[1] Pan S J,Ni X,Sun J T,et al.Cross-domain sentiment classification via spectral feature alignment[C]//International conference on world wide web.[s.l.]:[s.n.],2010:751-760.

[2] Wei W,Gulla J A.Sentiment learning on product reviews via sentiment ontology tree[C]//Proceedings of meeting of the association for computational linguistics.Uppsala,Sweden:[s.n.],2010:404-413.

[3] Li S,Huang C R,Zhou G,et al.Employing personal/impersonal views in supervised and semi-supervised sentiment classification[C]//Proceedings of meeting of the association for computational linguistics.Uppsala,Sweden:[s.n.],2010:414-423.

[4] Dasgupta S,Ng V.Mine the easy,classify the hard:a semi-supervised approach to automatic sentiment classification[C]//International joint conference on ACL.Singapore:[s.n.],2009:701-709.

[5] Brosius J.Biographies,bollywood,boomboxes and blenders:domain adaptation for sentiment classification[J].Association for Computational Linguistics,2012,31(2):187-205.

[6] Pang B,Lee L,Vaithyanathan S.Thumbs up? sentiment classification using machine learning techniques[C]//Proceedings of EMNLP.[s.l.]:[s.n.],2002:79-86.

[7] Lee S Y M. Sentiment classification and polarity shifting[C]//International conference on computational linguistics.[s.l.]:Association for Computational Linguistics,2010:635-643.

[8] Chapelle O,Weston J,Scholkopf B.Cluster kernels for semi-supervised learning[C]//Proceedings of the 16th annual conference on neural information processing systems.Massachusetts:MIT Press,2003:321-328.

[9] Maynard D,Funk A.Automatic detection of political opinions in tweets[C]//International conference on the semantic web.[s.l.]:Springer-Verlag,2011:88-99.

[10] Medhat W,Hassan A,Korashy H.Sentiment analysis algorithms and applications:a survey[J].Ain Shams Engineering Journal,2014,5(4):1093-1113.

[11] Kang H,Yoo S J,Han D.Senti-lexicon and improved Na?ve Bayes algorithms for sentiment analysis of restaurant reviews[J].Expert Systems with Applications,2012,39(5):6000-6010.

[12] Ortigosa-Hernndez J,Rodríguez J D,Alzate L,et al.Approaching sentiment analysis by using semi-supervised learning of multi-dimensional classifiers[J].Neurocomputing,2012,92(3):98-115.

[13] Berger A L,Pietra V J D,Pietra S A D.A maximum entropy approach to natural language processing[J].Computational Linguistics,2002,22(1):39-71.

[14] Chen C C,Tseng Y D.Quality evaluation of product reviews using an information quality framework[J].Decision Support Systems,2011,50(4):755-768.

[15] Li Y M,Li T Y.Deriving market intelligence from microblogs[J].Decision Support Systems,2013,55(1):206-217.

[16] Moraes R,Valiati J F,Neto W P G.Document-level sentiment classification:an empirical comparison between SVM and ANN[J].Expert Systems with Applications,2013,40(2):621-633.

[17] Cortes C,Vapnik V.Support-vector networks[J].Machine Learning,1995,20(3):273-297.

[18] Ruiz M E,Srinivasan P.Hierarchical text categorization using neural networks[J].Information Retrieval Journal,2002,5(1):87-118.

[19] Quinlan J R.Induction of decision trees[J].Machine Learning,1986,1(1):81-106.

[20] Li Y H,Jain A K.Classification of text documents[J].The Computer Journal,1998,41(8):537-546.

[21] Hu K,Lu Y,Zhou L,et al.Integrating classification and association rule mining:a concept lattice framework[M]//New directions in rough sets,data mining,and granular-soft computing.Berlin:Springer,2003:443-447.

[22] Turney P.Thumbs up or thumbs down?:semantic orientationapplied to unsupervised classification of reviews[C]//Proc of the 40th annual meeting on association for computational linguistics.Stroudsburg,USA:Association for Computational Linguistics,2002:417-424.

[23] Goldberg A B,Zhu X.Seeing stars when there aren't many stars[C]//TextGraphs:the first workshop on graph based methods for natural language processing.[s.l.]:[s.n.],2006:45-52.

[24] Sindhwani V,Melville P.Document-word co-regularization for semi-supervised sentiment analysis[C]//Eighth IEEE international conference on data mining.[s.l.]:IEEE Computer Society,2008:1025-1030.

[25] Zhou S,Chen Q,Wang X.Active deep networks for semi-supervised sentiment classification[C]//International conference on computational linguistics.[s.l.]:Association for Computational Linguistics,2010:1515-1523.

[26] Zhou S,Chen Q,Wang X.Fuzzy deep belief networks for semi-supervised sentiment classification[J].Neurocomputing,2014,131(9):312-322.

[27] Li S,Hao J.Spectral clustering-based semi-supervised sentiment classification[C]//Proc of the 8th advanced data mining and applications.Berlin:Springer,2012:271-283.

[28] Zhou Z H.Co-training paradigm in semi-supervised learning[C]//Proceeding of the Chinese workshop on machine learning and applications.Nanjing,China:[s.n.],2007．

[29] 鄭文靜,李 雷.基于圖的組合半監(jiān)督SVM聚類核算法研究[J].計算機(jī)技術(shù)與發(fā)展,2014,24(5):109-112.

[30] Weston J,Leslie C,Ie E,et al.Semi-supervised protein classification using cluster kernels[J].Bioinformatics,2005,21(15):3241-3247.

[31] Szummer M.Partially labeled classification with Markov random walks[J].Advances in Neural Information Processing Systems,2002(14):945-952.

[32] 李素科,蔣嚴(yán)冰.基于情感特征聚類的半監(jiān)督情感分類[J].計算機(jī)研究與發(fā)展,2013,50(12):2570-2577.

Research on Semi-supervised Sentiment Classification Based on Cluster Kernel

ZHENG Wen-jing，LI Lei

(School of Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

In the rapid development of the Internet today,mankind has entered the era of big data.Text data as the carrier of human knowledge,is of great significance for human progress and development.So the usage of a large number of unlabeled samples to improve the accuracy of sentiment classification,has become more and more important.The kernel clustering method in semi supervised learning is applied to the emotion classification problem,and a semi supervised sentiment classification algorithm based on kernel clustering is proposed.A weighted undirected graph is built according to the labeled samples and unlabeled samples,solving the clustering kernel,and then the kernel function is used for the training of classifier SVM.This method directly uses the information contained by unlabeled samples into the kernel,no need to set up multiple classifiers,effective useage of the unlabeled samples.Experimental results show that the CKSVM is better than that based on Self-learning SVM and Co-training SVM in classification accuracy,with better adaptability on different data sets.

semi-supervised learning;clustering kernel;graph;sentiment classification

2016-02-27

2016-06-15

時間：2016-11-22

國家自然科學(xué)基金資助項目(61070234,61071167,61501251)；南京郵電大學(xué)引進(jìn)人才科研啟動基金資助項目(NY214191)

鄭文靜(1990-)，女，研究方向為機(jī)器學(xué)習(xí)、情感分類；李 雷，博士，教授，研究方向為智能信號處理、非線性分析與計算智能、機(jī)器學(xué)習(xí)。

http://www.cnki.net/kcms/detail/61.1450.TP.20161122.1228.040.html

TP301.6

A

1673-629X(2016)12-0087-05

10.3969/j.issn.1673-629X.2016.12.019