王志昊，王中卿，李寿山，李培峰，施寒潇

（苏州大学 计算机科学与技术学院，江苏 苏州215006）

（浙江工商大学 计算机与信息工程学院，浙江 杭州310018）

1 引言

随着微博、社交网络、电子商务等互联网应用的迅猛发展，人们习惯于在网络中表达观点或抒发情感。与此同时，网络中的用户行为数据成倍增长，这些数据包含着大量情感信息。传统的基于主题的文本分类系统无法满足对这些主观文本分析的需求，情感分类在这种背景下受到越来越多人的重视［1］。情感分类任务是指对文本自身情感倾向性进行分类，例如，判断某一评论是“赞扬”或“批评”［2－3］。近年来，情感分类在自然语言处理研究领域已经成为一个热点研究问题［1］。

情感分类的主流研究方法是机器学习方法，大致可以分为无监督学习、监督学习和半监督学习三种。目前大多数研究都基于监督学习并且已经取得了非常好的效果［4］，但是由于监督学习依赖于大量人工标注的训练样本，使得监督学习的分类系统具有很高的标注代价。相对而言，无监督学习方法不需要人工标注训练样本，是最小化标注量的一种解决方案，但由于其分类效果不佳，通常难以达到实际要求［5－6］。半监督学习是采取综合利用少量已标注样本和大量的未标注样本来提高学习性能的情感分类方法［7－9］，它兼顾了人工标注成本和分类效果，被视为一种折中方案。本文主要围绕半监督情感分类方法进行展开。

情感分类任务同其他文本分类一样，面临着高维度特征空间的问题，同时半监督情感分类任务中的训练分类模型的过程也因高维度而变得漫长。特征选择是解决高维问题的一种有效手段，可以在不降低分类效果的前提下达到降维的目的。特征选择方法在文本分类研究中占有非常重要的地位。同时，已有的研究显示特征选择方法能够有效的降低监督情感分类中的特征维度空间［10］。然而针对半监督情感分类，特征选择方法的研究还未涉及。在半监督情感分类中，由于标注样本规模太小，特征在类别中的分布并不能可靠获得。因此，传统的基于监督情感分类的特征提取方法没法直接应用。如何在半监督情感分类中进行特征选择是一个新的具有挑战的问题。

本文首次探讨半监督情感分类中的特征提取方法，提出一种基于二部图的特征选择方法。该方法首先借助二部图模型来表述文档与单词间的关系。然后，结合小规模标注样本的标签信息和二部图，利用标签传播（LP）算法计算特征的正负类的情感概率。最后，按照特征的情感概率进行排序进而实现特征选择。基于选择出的特征，利用标签传播算法进行半监督情感分类。该方法在英文和中文领域都有明显的降维效果，在部分领域的评论语料中，其分类效果超过了使用全特征的半监督学习方法，最高有4个点的提升。此外，我们还针对随机特征选择的结果进行了比较研究，实验结果显示我们的方法优势明显。

本文结构安排如下：第2节介绍了半监督情感分类及特征选择方法的相关工作；第3节提出基于二部图的半监督特征选择方法；第4节为实验结果及分析；第5节为相关结论。

2 相关工作

2.1 半监督情感分类

近几年来，基于半监督学习的情感分类渐渐受到广大研究者们的重视。文献［8］将两种不同语言（英语和汉语）作为两个不同的视图，采用协同训练方法进行半监督情感分类；Li等则是把评价语句分为个人视图（Personal View）和非个人视图（Impersonal View）并同样采用协同训练方法进行半监督情感分类［9］。Dasgupta和Ng将谱聚类、主动学习、直推学习和集成学习引入到半监督学习中［7］，但仍未获得较高的分类准确率（在初始标注样本为100时，Book和DVD领域的准确率只有60%）。苏艳等对协同训练方法进行改进，提出了基于动态随机特征子空间的协同训练算法，并实验验证了当特征子空间数目为4左右的时候，该半监督分类方法能够取得最佳性能［11］。Li等则基于限制性非负矩阵分解 （Constrained Non－negative Tri－factorization）的方法实现了这种方式的半监督学习情感分类任务［12］。此外，高伟等提出了一种基于一致性标签的集成方法，该方法对两种主流的半监督情感分类方法：基于随机特征子空间的协同训练方法和标签传播方法进行了融合，从而有效降低对未标注样本的误标注率，获得比任一种半监督学习方法更好的分类效果［13］。

2.2 情感分类中的特征选择

情感分类任务作为一种特定的文本分类任务，同其他文本分类一样面临着高维度特征空间的问题。特征选择用于降低高维度特征空间，让文本分类变得更快速，分类更精确［14］。相关研究表明，将特征选择方法CHI应用于大规模在线产品评论，可以在不损失性能的前提下减少特征向量维度［15］。Ng等将WLLR方法用于电影评论的情感分类，取得很好的分类效果［16］。此外，Li等将 DF、MI、IG等特征选择方法用于主题文本分类和情感分类问题中，有效降低了维度［10］。然而，上述特征选择方法都是基于监督学习的，依赖于人工标注的结果。在半监督情感分类中，如何利用少量标注样本寻找出大量未标注样本中的有效特征是值得研究的问题。据我们所知，在半监督情感分类问题上还没有关于特征选择方法的研究。

3 基于二部图的半监督特征选择方法

3.1 总体框架

为了本文的表述清楚，我们首先给出基于二部图的半监督特征选择方法的总体框架图，如图1所示。该方法以二部图模型为基础，首先构建情感文本的二部图表示，建立文档到特征的正负类转移概率矩阵。通过多次迭代并对转移概率差值进行排序，选择出那些区分度最高的特征。这些被选择出的特征构成了半监督学习和情感分类过程中的特征空间。此外，在半监督学习中我们选用标签传播算法（LP）作为学习策略，情感分类方面则选用贝叶斯分类器。下文将详细介绍我们提出的基于二部图的半监督特征选择方法的具体实施步骤。

图1 总体框架图

3.2 基于二部图的情感文本表示

情感分类中，文档通常用词袋（Bag－of－words）模型化并用向量形式描述，其缺点是文档与单词间的关联是不清晰的。本文采用的二部图是图论中的一种特殊模型，其顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集。图2显示了文档—单词的二部图表示，其中文档用d1，d2...，dn表示，文档中包含的单词用w1，w2...，wn表示。文档—单词的二部图仅存在文档到词及词到文档的连接关系，一篇文档可以包含多个单词，一个单词会在多个文档中出现。显然，通过构建这种文档—单词的二部图可以很清晰地表述文档与单词间的关系。

图2 文档与单词的二部图模型

3.3 基于二部图和标签传播的特征选择

上文提到，在半监督情感分类的问题上还没有关于特征选择方法的研究，目前大多数特征选择方法都是围绕监督学习展开的。相关研究表明，特征选择可以在不降低分类效果的前提下达到降维目的，这也是我们提出这种方法的动机所在。

对于每个文档和文档中所含单词，或文档所包含的特征之间具有如下转移概率。如果文档di包含m个特征且特征tk的权重为wik，则文档di到特征tk的转移概率为式（1）：同理，若特征tk在n个文档中出现且文档dj的权重为wkj，那么该特征到文档dj的转移概率为式（2）：

显然，所有文档到特征tk的转移概率之和可由式（3）求得。

所有v个特征到某个文档di的转移概率之和如式（4）所示。

由于半监督情感分类中具有少量已标注样本，包括正类和负类样本，我们由式（3）、式（4）求得文档到特征tk的正类转移概率之和及负类转移概率之和，式（5）中的ppos（di）表示特征到文档di的正类转移概率之和，

式（6）中的pneg（di）则表示特征到文档di的负类转移概率之和。其中ppos（tk）和pneg（tk）的初始值p0T都为0。

对于标注样本，正类和负类转移概率初始值为固定常数（本文中取0），对于没有情感倾向的未标注样本，正类和负类转移概率的初始值设为0，在标签传播的过程中，样本到特征以及特征到样本的正负类转移概率被不断更新。本文所提出的特征选择方法认为，某一特征的正类和负类转移概率之和的差值越大，该特征所包含的情感区分度越高，差值的具体计算公式如式（7）所示。

我们选择那些区分度最高的特征作为半监督学习和情感分类过程中使用的特征，特征的极性由转移概率之和高的一方决定。图3给出了基于二部图的半监督特征选择方法流程。

图3 文档与单词的二部图模型

3.4 基于标签传播的半监督情感分类方法

半监督学习方面，本文使用的是标签传播算法。标签传播算法是Zhu等人于2002年提出的，它是一种基于图的半监督学习方法，其基本思路是用已标记节点的标签信息去预测未标记节点的标签信息［17］。同样的，这里我们也采用文档—词的二部图来表述文档与单词的关系。文档di到文档dj的转移概率是由文档di通过该文档里面的所有词到达文档dj的概率之和，即式（8）。

得到文档间的转移概率之后，通过建立标注矩阵和文档—特征的概率转移矩阵计算出未标注样本的标签［18］。此外，本文中的标签传播算法建立在上一步挑选出来的特征，而并不是所有的特征。值得一提的是，实验过程中我们发现，使用了特征选择后的标签传播算法执行效率更高，特别是当特征数目很少时，这种优势非常明显。

4 实验

4.1 实验设置

实验数据使用了中文和英文两组数据集：其中英文语料采用亚马逊收集的四个不同领域的产品评论，具体为Book、DVD、Electronics和 Kitchen，每个领域包含1 100篇正类和1 100篇负类评论。实验随机选取正类和负类样本各100篇作为初始标注样本，随机选取正类和负类各800篇作为未标注样本，剩余的正负各200篇作为测试样本。中文语料同样涵盖四个领域的产品评论，分别是化妆品、箱包、电脑和电子产品，每个领域包含1 000篇正类和1 000篇负类评论，实验随机选取正类和负类样本各100篇作为初始标注样本，随机选取正负各700篇作为未标注样本，剩余的正负各200篇作为测试样本。实验采用MALLET机器学习工具包中的贝叶斯分类器，分类算法的所有参数都设置为默认值。分类选取词的二元特征（Bigram）作为特征。除了与几种常见分类方法作比较外，实验中我们还加入了随机特征选择方法用于对比研究，考虑到该方法的随机性问题，每次实验我们取5次实验结果的平均值作为最终结果。

实验中使用准确率（Accuracy，Acc.）衡量分类效果，其中，TP和TN代表了被正确分类的正类样本和负类样本，FP和FN代表了被错误分类的正类样本和负类样本。准确率的计算公式如式（9）所示。

我们实现以下常见方法的比较研究。

全监督学习：直接使用标注样本及其所有特征训练分类模型（未使用非标注样本）。

使用所有特征的半监督学习：运用标签传播算法后的所有样本直接训练分类器，不使用特征选择方法。

使用特征选择的半监督学习：使用基于二部图的半监督特征选择方法选择特征并构成特征空间，用于标签传播算法和训练分类过程，方法过程参见3.1。

我们首先实验观察了基于二部图的半监督特征选择方法在英文语料中的表现，之后，在中文领域我们也安排了相应的实验。下面的实验结果中，每张曲线图中横纵坐标表示的含义相同，横坐标为特征数百分比，即选择的特征数目除以总特征数，纵坐标为准确率。

4.2 结果和分析

图4 基于二部图的半监督特征选择方法的分类性能比较（英文领域）

图4显示了基于二部图的半监督特征选择方法在英文语料中表现。可以看到，当选择的特征数量大于总特征数的10%时，我们的方法基本保持稳定的分类效果，很好的达到降维目的。此外，在kitchen和electronics两个领域，我们的方法表现优异，在保持性能的情况下有1%～2%的提升。

图5显示了我们的方法在中文语料下的分类效果。实验结果表明，基于二部图的半监督特征选择方法在中文语料里也有不俗表现。其中化妆品和箱包两个领域在特征数相对较少时也有很好的分类性能，达到了降维的效果。值得一提的是，在电子产品领域我们的方法表现突出，分类效果基本不低于使用全特征的标签传播算法。在特征数百分比为0.03，即136个特征时达到峰值，分类效果有4个点的提高。

图5 基于二部图的半监督特征选择方法的分类性能比较（中文领域）

图7 500个特征下与随机特征选择方法的分类性能比较

图6和图7分别显示了选择200个和500个特 征时，随机特征选择和我们提出的方法在中英文领域下的分类性能比较。实验结果清楚的表明：基于二部图的半监督特征选择方法比随机特征选择方法的分类效果好很多，特别是在特征数目很少的时候这种优势越大。除了上图中200和500这两个固定的特征数目点以外，我们对其他特征数也做了类似的实验。实验结果都显示，我们的方法始终优于随机特征选择方法。

4 结语

本文在半监督情感分类中，提出一种基于二部图和标签传播的特征选择方法。该方法首先借助二部图模型来表述文档与单词间的关系。然后，结合小规模标注样本和标签传播算法进行特征提取。实验结果表明，在多个领域的半监督情感分类任务中，基于二部图和标签传播的特征选择方法明显优于随机特征选择。在保证分类效果不下降（甚至提高）的前提下有效降低了特征空间维度。

面向半监督分类的特征选择的研究才刚刚起步，存在很多问题需要我们进一步探讨。例如，从上面的实验结果可以看到，相比使用全部特征的半监督学习方法，我们的方法在大多数领域的分类效果没有很大的性能提升。下一步工作中，我们将尝试加入分类器融合策略，用以稳定和提高最终的分类性能。此外，我们会继续关注半监督领域的高维度特征空间问题，寻找更适合半监督情感分类任务的特征选择方法。

［1］Pang Bo，Lee L，Vaithyanathan S.Thumbs up？Sentiment classification using machine learning techniques［C］／／Proceedings of EMNLP－02，2002：79－86.

［2］Liu Bing，Hu Minqing，Cheng Junsheng.Opinion Observer：Analyzing and Comparing Opinions on the Web［C］／／Proceedings of WWW－05，2005：342－351.

［3］Wiebe J，Wilson T，Cardie C.Annotating Expressions of Opinions and Emotions in Language.Language Resources and Evaluation，2005，39：165－210.

［4］唐慧丰，谭松波，程学旗.基于监督学习的中文情感分类技术比较研究［J］.中文信息学报，2007，6（2）：88－94.

［5］Zagibalov T，Carroll J.Automatic Seed Word Selec－tion for Unsupervised Sentiment Classification of Chinese Test［C］／／Proceedings of COLING，2008：1073－1080.

［6］Yarowsky D.Unsupervised Word Sense Disambiguation Rivaling Supervised Methods［C］／／Proceedings of ACL－05，2005：189－196.

［7］Dasgupta S，Ng V.Mine the Easy，Classify the Hard：A Semi－Supervised Approach to Automatic Sentiment Classification［C］／／Proceeding of ACL－IJCNLP－09，2009：701－709.

［8］Wan Xiaojun.Co－Training for Cross－Lingual Sentiment Classification［C］／／Proceedings of ACL－IJCNLP－09，2009：235－243.

［9］Li Shoushan，Huang Chu－Ren，Zhou Guodong，et al.Employing Personal／Impersonal Views in Supervised and Semi－supervised Sentiment Classification［C］／／Proceedings of ACL－10，2010：414－423.

［10］Li Shoushan，Xia Rui，Zong Chengqing，et al.A Framework of Feature Selection Methods for Text Categorization ［C］／／Proceedings of IJCNLP－09，2009：692－700.

［11］苏艳，王中卿，居胜峰，等.基于随机特征子空间的半监督情感分类方法研究［J］.中文信息学报，2012，26（4）：85－92.

［12］Li Tao，Zhang Yi，Sindhwani V.A Non－negative Matrix Tri－factorization Approach to Sentiment Classification with Lexical Prior Knowledge［C］／／Proceeding of ACL－IJCNLP－09，2009：244－252.

［13］高伟，王中卿，李寿山.基于随机特征子空间的半监督情感分类方法研究［J］.中文信息学报，2012，27（3）：120－126.

［14］Yang Yiming，Pedersen J.A comparative study on feature selection in text categorization［C］／／Proceedings of ICML－97，1997.

［15］Cui Hang，Mittal V，Datar M.Comparative Experiments on Sentiment Classification for Online Product Reviews［C］／／Proceedings of AAAI－06，2006：611－618.

［16］Ng V，Dasgupta S，Niaz Arifin S.Examining the role of linguistic knowledge sources in the automatic identification and classification of reviews［C］／／Proceedings of the COLING／ACL Main Conference Poster Sessions，2006.

［17］宗成庆.统计自然语言处理［M］.清华大学出版社，2008.5

［18］Zhu Xiaojin，Ghahramani Z.Learning from Labeled and Unlabeled Data with Label Propagation［C］／／Proceedings of CMU CALD Technical Report，2002.