基于聚类核的半监督情感分类算法研究

郑文静，李 雷

(南京邮电大学 理学院，江苏 南京 210023)

基于聚类核的半监督情感分类算法研究

郑文静，李 雷

(南京邮电大学 理学院，江苏 南京 210023)

在互联网快速发展的今天，人类已经进入“大数据”时代，其中文本数据作为人类知识的载体，对于人类的进步与发展意义重大。如何运用大量未标记样本来提升文本情感分类的精度，也变得愈发重要。将半监督学习中的聚类核算法应用到情感分类问题中，给出基于聚类核的半监督情感分类算法。在标记样本和未标记样本上，建立加权无向图，求解聚类核，然后将该核函数用于SVM的情感分类器的训练上，完成情感分类工作。该方法直接将未标记样本所蕴含的信息融合到核中，不需要建立多个分类器，有效利用了未标记样本。实验结果表明，CKSVM算法在分类精度上明显优于基于Self-learning SVM和Co-training SVM的半监督情感分类算法，且在不同数据集上都有较好的适应性。

半监督学习；聚类核；图；情感分类

0 引 言

随着互联网的发展,越来越多的消费者在网上发表评论[1]，这些评论以主观的文本形式表达了消费者对于消费产品或服务的满意度。这不仅可以帮助其他消费者做出更好的判断，还可以帮助制造商跟踪和管理这些意见[2]。在自然语言处理(NLP)中，情感分类作为一种特殊的文本分类问题正受到越来越多的重视[3-6]。情感分类的标准是挖掘文本中蕴含的极性情感态度，如“positive” or “negative”,“thumbs up” or “thumbs down”,“favorable” or “unfavorable”[7]，而不是主题。如今，情感分类技术广泛应用于商业智能系统、推荐系统、公众的意见收集和挖掘系统等等。在上述领域，存在着丰富的未标记文本数据，标记的文本数据很少，且需要通过人工标注获得。这使得使用许多传统的算法训练数据的代价过高，因为这些分类器要求足够的标记数据来保证实现高精度。

为使用未标记样本提高情感分类的精度，提出一种基于聚类核的半监督情感分类算法。基于聚类假设，Chapelle提出聚类核概念[8]，使用核函数，而不是明确的特征向量，重新表示给定的数据，以反映未标记数据透露的结构。首先通过bag-of-word模型将数据集中的评价转化为向量形式，并将这些向量作为图的顶点，将各评价间的相似度作为边上的权重，构建加权无向图。然后引入线性转换函数，将该图上的相似矩阵重新表示，使得在同一集群中两点间的距离更小，建立半监督聚类核，并将其用于SVM分类器的训练上。实验结果表明，该算法分类精度较高，且在分类精度上优于基于Self-learning SVM和基于Co-training SVM的半监督情感分类算法。

1 相关研究

1.1 情感分类

一般来说，情感分类技术可分为基于机器学习(Machine Learning,ML)的情感分类方法、基于词典的方法和混合方法[9]，具体见图1。

图1 情感分类算法

基于机器学习的情感分类算法，主要是经典机器学习算法结合语义特征的应用[10]，大体上可分为基于监督学习的情感分类方法、基于半监督学习的情感分类方法和基于无监督学习的情感分类方法。基于监督学习的情感分类方法依赖于已存在的标记训练样本，包括概率分类器[11-13]、线性分类器[14-18]、决策树分类器[19-20]和基于规则的分类器[10,21]等模型。2002年，Pang等[6]率先使用监督式机器学习方法中的支持向量机(Support Vector Machine,SVM)对电影评论进行情感分类，并且对比了朴素贝叶斯(Naïve Bayes,NB)、最大熵分类法(Maximum Entropy Classification,MEC)和SVM三种监督学习算法在情感分类问题中的性能[6]。由于情感分类问题一般是将文档划分到一定数量的预定义类别中，且标记样本较难获得[9]，因此基于无监督学习的情感分类方法引起了广泛关注。例如，Turney使用PMI-IR(Pointwise Mutual Information and Information Retrieval)方法进行消费者评论的情感分类[22]。

半监督学习使用少量标记样本和大量未标记样本，可以有效提高分类精度，大大减少人工标记的工作量，因此越来越多的研究者将其与情感分类问题相结合，取得了较好效果。Goldberg和Zhu[23]提出了一种基于图的半监督学习算法来处理评分系统的情感分析问题，其中不同数值的评分对应着给定的情感。Sindhwani和Melville[24]将文本先验信息同未标记样本相结合，给出了一种半监督情感分类算法。Zhou等运用主动学习来解决半监督情感分类问题，提出了主动深度网络方法(Active Deep Networks,ADN)[25]，并进一步提出了模糊深度置信网络法(Fuzzy Deep Belief Networks,FDBN)[26]。基于基本假设：具有相似情感倾向的情感词有较高的概率出现在同样情感倾向的消费者评论中,文献[27]提出一种基于特征聚类的半监督式情感分类方法。该方法根据情感特征的共现关系构建共现矩阵，利用spectral聚类方法生成分类用的扩展特征，结合原有训练域内的分类特征来训练新的情感分类器形成两个分类器，共同完成最后的情感分类工作。

1.2 聚类核

聚类假设[28]是半监督学习的核心，是建立目标函数与未标记样本分布之间关系的枢纽[5]，指的是同一聚类中的样本点很可能具有相同的类别标签，即在高密度区域里，如果某两个点可以通过区域内某条路径相连接，那么这两个样本点的标签相同的可能性比较大。而聚类核[8]依赖聚类假设思想，使用核函数重新表示给定的数据，从而将未标记数据中的结构加入到分类器中[29]。其主要思想在于改变距离度量，使同一群集中两点挨得更紧，距离更小[30]。

构造聚类核的整体框在文献[8]中提出。本质上，聚类核来源于核矩阵的能量本征谱，其中两种比较典型的方法是随机游走核[8]及谱聚类核[8]。在一个标准化且对称化的随机游动过程中，随机游走核是它的t步转移矩阵。Szummer[31]指出，在以xi为顶点的图上，随机游动过程的转移矩阵可以是RBF核，由此定义的随机游走，就可以通过一步转移矩阵求解出t步随机游走核。谱聚类核的主要思想依据是谱聚类，即在特征空间中，计算出样本间相似度矩阵的谱分解后，就可以重新表示样本点了。这样一来，位于同一聚类区域中的样本点更加紧凑地分布在新的空间中。文中将聚类核算法应用到情感分类中，在样本集上求解出核函数后，与SVM分类器的训练相结合，提出了基于半监督聚类核的情感分类算法(ClusterKernelbasedSVMforsentimentclassification，CKSVM)。

2 基于聚类核的半监督情感分类算法

为了更好地满足聚类假设，减少分类器的使用，文中提出基于聚类核的半监督情感分类算法。在构建基于文本数据集的加权无向图之后，使用线性分段转换函数将图上的相似矩阵重新表示，利用该半监督聚类核训练的基于SVM情感分类器有着更好的分类效果。

为了构建可以给出样本集中xi类别的分类器，需要得到决策函数f(x)：f:X→Y。

各顶点间边的权重通过以下相似矩阵来度量。相似矩阵W为：

(1)

其中，xi和xj表示两个评价的特征向量；d(xi,xj)取cos(xi,xj)；σ为给定的控制参数。

接下来计算对角矩阵D，Dii=∑jWij，其元素是W的行和，可以得到图拉普拉斯矩阵L=D-W。L的谱分解为：

(2)

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

(3)

从上述描述，可以得到CKSVM的步骤：

Step1:根据bag-of-word模型，将文本数据表示为向量，进行初步的特征提取之后，得到标记样本集T和未标记样本集U的特征矩阵M，M∈im×n。其中，m为训练数据集的文本个数，n为特征项的个数。

Step2:根据式(2)计算相似矩阵W。

Step3:计算对角矩阵Dii=∑jWij。

Step7:使用上述聚类核训练SVM分类器，得到基于半监督聚类核的情感分类器，对数据集上的评价提取出的特征向量进行训练。

3 实 验

为了验证CKSVM算法的有效性，分别在数据集上进行测试。并且与较早实现的基于Self-learningSVM和基于Co-trainingSVM的半监督情感分类算法进行比较，这两种算法的实现过程见文献[32]。算法均在32位Python集成环境Anaconda中进行，调用了多个用于科学计算的Python库，如numpy、sk-learn等。都选用交叉验证法找出的最优参数。

3.1 数据集选取及预处理

(1)文中选取movie-reviews影评数据集和20 Newsgroups数据集。其中，movie-reviews数据集由康奈尔大学(Cornell)提供，包括2 000条电影评价，其中肯定和否定态度的各1 000条。目前影评库被广泛应用于各种粒度的(如词语、句子和篇章级)情感分析研究中。20 Newsgroups数据集包括接近20 000种报纸的数据，每种报纸选出1 000篇文章。文章的主题包括计算机、政治、宗教、运动和科学。

(2)文中对英文文本的预处理，主要依赖Python的NLTK库。NLTK是用来处理和自然语言处理相关事件的工具包，包括分词(tokenize)、词性标注(POS)、文本分类等现成工具。文中将数据集中的文本进行分词，用VSM模型将一个个的文本表示成向量。

3.2 实验结果分析

对movie-reviews影评数据集，在不同训练样本比例情况下，各半监督情感分类算法的分类精度如表1所示。

表1 movie-reviews影评数据集三种半监督情感分类算法的分类精度

三种算法在movie-reviews数据集上的分类准确度如图2所示。

图2 三种半监督情感分类算法在movie-

从图2可以看出，随着标记样本比例的增加，各半监督情感分类算法的分类准确度都有提升，其中CKSVM算法提升最快，且其分类精度几乎一直高于基于Self-learning SVM和基于Co-training SVM的半监督情感分类算法，说明CKSVM算法更好地运用了未标记样本中的信息。

对20 Newsgroups数据集，在不同训练样本比例情况下，各半监督情感分类算法的分类精度如表2所示。

三种算法在20 Newsgroups数据集上的分类准确度如图3所示。

从图3可以看出，随着标记样本比例的增加，各半监督情感分类算法的分类准确度都有提升，其中CKSVM算法提升最快，说明在该数据集上CKSVM算法也同样很好地运用了未标记样本中的信息。另外，由于20 Newsgroups数据集更加复杂，三种算法的分类精度都有下降，但是CKSVM下降最少，说明CKSVM有较好的适应性，在不同数据集上依然可以得到较好的结果。

表2 20 Newsgroups数据集三种半监督情感分类算法的分类精度

图3 三种半监督情感分类算法在20 Newsgroups

4 结束语

文中提出了基于聚类核的半监督情感分类算法。该方法直接将未标记样本所蕴含的信息融合到核中，可以直接用于SVM的情感分类器的训练上，有效利用了未标记样本中蕴含的信息。在两个数据集上的实验表明，该算法在分类精度上明显优于基于self-learning SVM和Co-training的半监督情感分类算法，且CKSVM在两个数据集上表现都最好，有较好的适应性。

[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] 郑文静,李 雷.基于图的组合半监督SVM聚类核算法研究[J].计算机技术与发展,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] 李素科,蒋严冰.基于情感特征聚类的半监督情感分类[J].计算机研究与发展,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

国家自然科学基金资助项目(61070234,61071167,61501251)；南京邮电大学引进人才科研启动基金资助项目(NY214191)

郑文静(1990-)，女，研究方向为机器学习、情感分类；李 雷，博士，教授，研究方向为智能信号处理、非线性分析与计算智能、机器学习。

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