利用复杂网络为自由评论鉴定词汇情感倾向性

第 38 卷 第 3 期 自 动 化 学 报 Vol. 38, No. 3 2012 年 3 月 ACTA AUTOMATICA SINICA March, 2012 利用复杂网络为自由评论鉴定词汇情感倾向性 殷春霞 1, 2 彭勤科 1, 2 摘 要 词汇情感倾向性 (Word sentiment orientation, WSO) 的鉴定通常是对文本进行粗粒度意见挖掘的基础. 自由评论 中存在许多语法噪声, 这使得以往基于规范文本提出的WSO 鉴定方法不再适合自由评论. 自由评论中的情感词汇往往是上下 文敏感的, 这使得非当前鉴定的情感词汇难以适用于当前自由评论的粗粒度意见挖掘. 针对上述问题, 提出一种新的利用复杂 网络为自由评论鉴定WSO 的方法. 该方法主要有两个部分: 1) 为了利用自由评论中词汇之间的上下文信息建模一个能够有 效解决上下文敏感问题且具有良好抗噪声能力的情感倾向性关系网络 (Sentiment orientation relationship network, SORN), 提出了两个算法: 金字塔抗噪声信息模型算法和利用抗噪声信息优化调整 SORN 的算法; 2) 为了有效利用 SORN 为自由评 论鉴定WSO, 提出了基于 SORN 的WSO 鉴定算法. 实验表明: 对于在线为自由评论鉴定WSO, 本文方法不仅在精确度方 面远高于 Hatzivassiloglou 提出的方法, 且具有良好的时间效率. 关键词 意见挖掘, 自由评论, 词汇情感倾向性, 复杂网络 DOI 10.3724/SP.J.1004.2012.00389 Identifying Word Sentiment Orientation for Free Comments via Complex Network YIN Chun-Xia1, 2 PENG Qin-Ke1, 2 Abstract Identifying word sentiment orientation (WSO) is usually the foundation of mining coarse-grained emotion information. In free comments, there exist many grammatical errors which disable previous grammatical text-based methods in identifying WSO for free comments, and there exist some context-sensitive words which disable offline opinion words in mining coarse-grained emotion information. In view of the above questions, a new method which identifies WSO for free comments via complex network is proposed. This method consists of two parts. The first part makes use of context information in free comments to build a sentiment orientation relationship network (SORN) for effectively solving the context sensitive and noise problems. For this purpose, two algorithms are brought forward. One is the algorithm for building the pyramid anti-noise information model and the other is the algorithm for optimizing the sentiment orientation relationship network by anti-noise information. The second part identifies WSO for free comments via SORN. For this purpose, the SORN-based WSO algorithm is put forward. Experimental results show that our method far exceeds HM in identifying WSO for free comments and has good timeliness. Key words Opinion mining, free comments, word sentiment orientation (WSO), complex network 互联网上的自由评论 (影视评论、产品评论、新 闻评论等) 是个人观点的表达和内在情感的抒发, 其 情感信息无论对个人、公司还是政府等都有潜在价 值[1]. 与规范文本 (符合语法规范的文本) 不同, 自 由评论具有短小精悍、形式自由及趋于口语化的特 点[2], 这决定了从自由评论中挖掘情感信息的难度. 收稿日期 2011-03-02 录用日期 2011-10-08 Manuscript received March 2, 2011; accepted October 8, 2011 国家高技术研究发展 (863 计划) (2007AA01Z475, 2007AA01Z 464), 国家自然科学基金 (60774086), 教育部博士点基金 (2009020111 0027) 资助 Supported by National High Technology Research and De- velopment Program of China (863 Program) (2007AA01Z475, 2007AA01Z464), National Natural Science Foundation of China (60774086), and the Ph.D. Programs Foundation of Ministry of Education of China (20090201110027) 本文责任编委 刘德荣 Recommended by Associate Editor LIU De-Rong 1. 西安交通大学机械制造与系统国家重点实验室 西安 710049 2. 西安交通大学电子与信息工程学院自动化系 西安 710049 1. State Key Laboratory for Manufacturing Systems Engineer- ing, Xi′an Jiaotong University, Xi′an 710049 2. School of Elec- tronic and Information Engineering, Xi′an Jiaotong University, Xi′an 710049 词汇情感倾向性 (Word sentiment orientation, WSO) 的研究在文本意见挖掘中有着举足轻重的地 位[3], 是分析文本粗粒度情感 (句子级别[4−5]、评论 级别[6−8]、主题级别[9] 等) 的基础. WSO 的鉴定方 法通常被归纳为基于语料的方法[10−12] 和基于知识 库的方法[13−19]. Hatzivassiloglou 等[10] 将对数线性回归模型与 形容词之间的连接信息结合起来生成形容词连接关 系图, 利用聚类算法鉴定该图上形容词的情感倾向 性 (该方法简称为 HM 方法). HM 方法具有良好的 时间效率, 然而它是基于规范文本提出的, 完全依赖 于词汇之间的语言学约束, 缺乏对违反语法规范噪 声现象的处理, 这直接导致 HM 方法不适于为自由 评论鉴定WSO. Turney 等[11] 通过计算目标词汇与 基准词之间的逐点互信息来鉴定WSO, 然而计算逐 点互信息需要繁重的计算量. 杜伟夫等[12] 将WSO 计算问题归结为对基于词汇之间相似度建立的词语 无向图的最小切分, 然而同样存在效率问题. Kamps等[13]利用WordNet 的同义关系建立形 390 自 动 化 学 报 38卷 容词网络, 比较目标形容词与基准词 “good” 和 “bad” 在网络中的最短距离来鉴定目标词的 倾向, 然而无法鉴定不在同义关系网络中的WSO. Esuli 等[14−16] 基于 “WSO 相似则其注释相似” 的 思想构造了 SentiWordNet 情感词汇资源, 然而该 方法依赖于注释的质量以及向量的表示. Kim 等[17] 采用 Esuli 的思想扩充种子集, 根据目标词汇的同义 词出现在扩充集中的概率来计算WSO, 然而只能鉴 定目标词汇的同义词与扩充集有交集的情况. Rao 等[18] 利用半监督标记传递算法来鉴定WSO, 然而 该方法只能鉴定少量词汇的情感倾向. 朱嫣岚等[19] 利用 HowNet 计算词汇与基准词的相似度的方法来 鉴定WSO, 然而该方法对基准词的选择及其数量比 较敏感. 上述基于语料的方法都是基于规范文本提出的, 而且除了HM方法, 其他都存在效率不高的问题.基 于知识库的方法需要知识库的支持, 也就是说, 这类 方法很大程度上依赖领域专家带有一定主观性的背 景知识. 来自互联网终端用户的自由评论不同于规范文 本, 它存在着以下几种特殊现象. 1) 很多词汇的情 感倾向由当前所在的上下文语境决定, 例如:“佟大 为傻乎乎的, 演的不错.”, “这个手机样子傻乎乎的, 难看死了！”. 显然,“傻乎乎”在第一个句子中呈现 positive (积极) 倾向性, 在第二个句子中呈现 nega- tive (消极) 倾向性. 2) 存在反语、讽刺情况, 例如: “这部影片太好了, 看了你就想呕吐.”. 3) 存在着大 量违反语法规范的噪声现象 (比如: 缺省转折关联 词、标点符号用错等), 这些噪声会干扰词汇之间上 下文关系的正确识别. 有 2 种上下文关系: 转折关系 和非转折关系. 同现在一个句子中的一对情感词汇 只可能具有其中一种上下文关系. 基于规范文本的 词汇倾向性鉴定方法恰恰缺乏对上述特殊现象的处 理, 以至于很难再适合为自由评论鉴定情感词汇. 针对上述问题, 本文旨在研究: 1) 有效利用自 由评论中词汇之间的上下文信息构建一个抗噪声 的情感倾向性关系网络 (Anti-noise sentiment ori- entation relationship network, ANSORN). 有效解 决WSO 上下文敏感 (暂不考虑反语、讽刺情况) 问 题和噪声干扰问题是构建 ANSORN 的目标, 为此 提出了两个算法: 建立金字塔抗噪声信息模型的算 法 (Algorithm for building the pyramid anti-noise information model, PANIMA) 和利用抗噪声信息 优化调整情感倾向性关系网络的算法 (Algorithm for optimizing SORN by anti-noise information, ANISA). 构建 ANSORN 主要有 3 个步骤: a) 构建 基本的情感倾向性关系网络 (Basic sentiment ori- entation relationship network, BSORN); b) 利用 PANIMA 算法构建金字塔抗噪声信息模型 (Pyra- mid anti-noise information model, PANIM); c) 利 用 ANISA 算法, BSORN 在 PANIM 的优化调整 下演化成 ANSORN. 2) 为了有效利用 SORN 为自 由评论鉴定WSO, 提出了基于 SORN 的WSO 鉴 定算法 (SORN based word sentiment orientation algorithm, SWSOA). 该算法基于 SORN 网络节点 (词汇) 之间的最少噪声路径来计算节点之间的情感 倾向性关系, 从而能有效利用 ANSORN 中的抗噪 声信息为自由评论鉴定WSO. 在文献 [20−21] 中已经证明了语言网络是一个 存在着小世界性[22] 的复杂网络. 显然, SORN 属于 语言网络的范畴, 因而本文方法被期望有很好的时 间效率. 本文中将出现多种具体的 SORN (比如, BSORN 和 ANSORN 是两个具体的 SORN), SWSOA 算法能否为自由评论有效鉴定 WSO 依 赖于不同的情感倾向性关系网络的特性. 为此本文 按如下方式组织: 首先引入抽象的 SORN 模型, 进 而提出 SWSOA 算法, 接着详细介绍如何构建具有 良好特性的 ANSORN, 最后实验及结果分析. 1 SORN模型 分析大量的自由评论发现: 对于同一个评论对 象 (比如: 一部电影、一个新闻事件等) 所使用的同 一个情感词汇, 该情感词汇所表现的倾向性通常在 该评论对象的所有上下文中是保持一致的. 因此可 以设想: 只要语料足够充分, 通过词汇之间的上下文 关系便能够计算任何两个情感词汇的情感倾向性关 系 (一对词汇的情感倾向性关系表明这对词汇是否 同倾向性). 基于此, 提出用于计算词汇之间情感倾 向性关系的网络模型, 该模型被称为 SORN 模型. 本文构建的 SORN 模型由 3 个要素构成, 分别 是节点、带颜色的边以及边噪声强度, 它们分别对应 着语料中待鉴定情感倾向性的词汇、词汇之间的上 下文关系以及该上下文关系发生错误的可能性. 本 文的目的是通过构建合理的 SORN 来解决自由评 论中WSO 的上下文敏感问题以及噪声干扰问题. 定义 1. 假设有 n 个待鉴定情感词汇, W 为这 些词汇组成的集合, 即 W = {w1, w2, · · · , wn}. 若 wi 和 wj 不仅以转折关系同现在一些句子中, 而且 以非转折关系同现在另外一些句子中, 则称 wi 和 wj 的上下文关系在语料中发生了冲突. “wi 和 wj 的上下文关系在语料中发生了冲突” 意味着同现 wi 和 wj 的某些句子违反了语法规范. 比如: 1) “上集很不错, 下集没预想的那么好.”; 2) “总体还不错, 战争场面拍得很好.”. 抽取的形容词 序列分别为: “不错 but 好”、“不错 好”. “不错” 和 “好” 在第一个句子中是转折关系, 而在第二个句子 3期 殷春霞等: 利用复杂网络为自由评论鉴定词汇情感倾向性 391 中是非转折关系, 显然这种不一致是由于第一个句 子缺省了转折词而导致的. 一对词汇的上下文关系在语料中若发生了冲突, 随机选择一种关系作为这对词汇在 SORN 中的上 下文关系显然不合理. 这是因为错误的上下文关系 被选中后, 如果用来计算一对词汇倾向性关系的路 径必须经过这个错误的上下文关系 (噪声边), 则可 能会错误地鉴定这对词汇的情感倾向性关系. 基于上述分析, 需要设置一定的抗噪声条件来 确定一对词汇在 SORN 中的上下文关系, 以便尽量 减少向 SORN 引入错误的上下文关系. 为了便于后 面的定义及分析, 定义 2 先使用泛化的抗噪声条件 来确定 SORN 中词汇之间的上下文关系. 定义 2. 对 ∀wi, wj ∈W (i 6= j), 记 cij =  1, 抗噪声条件 1 −1, 抗噪声条件 2 ∞, 否则 (1) 称 cij 为 SORN 中 wi 和 wj 的上下文关系. 1, −1 和 ∞ 分别表示非转折关系、转折关系和不存在关 系. 令 cii =∞. 在 SORN 中, 用两种不同颜色的边 来分别表示不同的上下文关系. 一致采用黑色边来 表示非转折关系, 灰色边来表示转折关系. 称 C = (cij)n×n 为 SORN 的上下文关系矩阵. 由于 cij 表示的上下文关系仍有可能是错误的 上下文关系, 因此需要给出该上下文关系是错误的 可能性 (上下文关系噪声强度). 定义 3. 对 ∀wi, wj ∈W , 记 qij = { +∞, cij =∞ ξ, 否则 (2) 其中, 0 < ξ < +∞. 称 qij 为 cij 的噪声强度. ξ 是 噪声强度变量. 称 Q = (qij)n×n 为 SORN 的上下 文关系噪声强度矩阵. 显然, cij = cji 和 qij = qji, 因此 C 和 Q 都是 对称矩阵. W , C 以及 Q 唯一确定了一个 SORN, 形式化地将 SORN 表示成一个三元组, 即: SORN = (W,C,Q). 为了方便计算 SORN 中一条路径上经过的转 折关系边的数量, 定义下面的指示函数: δij = { −1, cij = −1 0, cij = 1 或 cij =∞ (3) 2 SWSOA算法 定义 4. 对 ∀wi ∈W , 记 T (wi) = { 1, 若 wi 为 positive −1, 若 wi 为 negative (4) 称 T (wi) 为 wi 的情感倾向性值. 定义 5. 给定 SORN = (W,C,Q),在 SORN中 一条从 wi 到 wj 的路径上经过的词汇编号序列被记 为 (p1, p2, · · · , ps), 其中 2 ≤ s ≤ n, p1 = i, ps = j. 若集合 {(p1, p2, · · · , ps)} 中一个元素 (h1, h2, · · · , hs) 满足: qh1h2 + qh2h3 + · · ·+ qhs−1hs = min{qp1p2 + qp2p3 + · · ·+ qps−1ps} 则称 (h1, h2, · · · , hs) 为 SORN 中从 wi 到 wj 的 一条最少噪声路径上经过的词汇编号序列, 记为 D(i, j). 称 (D(i, 1), · · · , D(i, i − 1), D(i, i + 1), · · · , D(i, n)) 为 D(i, j) 的序列, 记为 D(i). 例 1. 给定一个简单的 SORN, 如图 1 所示. 图 1 SORN 的例子 Fig. 1 An example of SORN 显然, W = {w1, w2, w3, w4, w5, w6, w7}. C =  ∞ 1 −1 1 ∞ ∞ ∞ 1 ∞ −1 ∞ ∞ ∞ ∞ −1 −1 ∞ −1 ∞ 1 ∞ 1 ∞ −1 ∞ −1 ∞ ∞ ∞ ∞ ∞ −1 ∞ 1 ∞ ∞ ∞ 1 ∞ 1 ∞ 1 ∞ ∞ ∞ ∞ ∞ 1 ∞  Q =  +∞ 0.12 0.12 0.48 +∞ +∞ +∞ 0.12 +∞ 0.24 +∞ +∞ +∞ +∞ 0.12 0.24 +∞ 0.12 +∞ 0.12 +∞ 0.48 +∞ 0.12 +∞ 0.24 +∞ +∞ +∞ +∞ +∞ 0.24 +∞ 0.6 +∞ +∞ +∞ 0.12 +∞ 0.6 +∞ 0.24 +∞ +∞ +∞ +∞ +∞ 0.24 +∞  D(1, 2) = (1, 2), D(1, 3) = (1, 3), D(1, 4) = (1, 3, 4), D(1, 5) = (1, 3, 4, 5), D(1, 6) = (1, 3, 6), D(1, 7) = (1, 3, 6, 7). 从而 D(1) = ((1, 2), (1, 3), (1, 3, 4), (1, 3, 4, 5), (1, 3, 6), (1, 3, 6, 7)). 本文采用邻接表和斐波纳契堆实现的 Dijkstra 算法[23] 来计算 D(i). 显然, 应该选择两个词汇之间噪声最少的路径 来鉴定这对词汇的情感倾向性关系. 当语料足够充 392 自 动 化 学 报 38卷 分, 对 ∀wi, wj ∈ W (i 6= j), 利用 Q 便可获得 D(i, j), 再利用 C 便能计算 wi 和 wj 的情感倾向 性关系. 另外在语料中 positive 词汇总比 negative 词汇多[10]. 基于上述分析, 提出 SWSOA 算法, 该 算法从 SORN 最大连通子图的任何一个节点开始, 便可对该子图中的所有节点进行情感倾向性分类. SWSOA 算法的输入为一个具体的 SORN. 为方便 使用, 将该算法表示成函数 SWSOA(SORN), 其中 SORN 表示 SORN 变量. SWSOA算法. 步骤 1. 利用广度优先遍历算法获得 SORN 的最大连通子图 GS. GS 中包含的词汇节点组成的 集合被记为WGS. 步骤 2. 指定WGS 中的任意一个节点 wi, 且使 得WGS =WGS − {wi}, U = {wi} 和 V = ∅. 步骤 3. 计算 D(i) 来获得 wi 到 WGS 中任意 节点的最少噪声路径. 步骤 4. 对 WGS 中的每一个词汇节点 wj, 执 行: 步骤 4.1. 依据 D(i) 中的 D(i, j), 计算从 wi 到 wj 的最少噪声路径上经过的转折关系边的数量 e. e = ∑s−1 l=1 δhlhl+1chlhl+1 . 步骤 4.2. 计算 wj 与 wi 的倾向性关系: T (wj) = (−1)e × T (wi). 步骤 4.3. 如果 T (wj) = T (wi), 那么 U = U ∪ {wj}, 否则 V = V ∪ {wj}. 步骤 5. WSO 分类完成, 分类结果分别存放 在 U 和 V 中. 如果 |U | > |V |, 那么 U 中存放着 positive 词汇和 V 中存放着 negative 词汇, 反之亦 然. SWSOA 算法能否为自由评论有效鉴定WSO 依赖于对其输入的具体 SORN 的连通性及抗噪声 能力. 接下来详细介绍如何构建具有良好连通性和 抗噪声能力的 ANSORN. 3 构建ANSORN 构建 ANSORN 主要有 3 个步骤: 1) 构建 BSORN; 2) 构建拥有丰富抗噪声信息的 PANIM, 这主要通过提出的两个算法: PANIMA 算法和 ANISA 算法来实现; 3) 再次通过 ANISA 算法, 使得 BSORN 在 PANIM 的优化调整下演化成 AN- SORN. 3.1 BSORN 通过分析自由评论语料中情感词汇之间的上下 文关系发现: 如果一对词汇以上下文关系 r1 同现的 频率比以上下文关系 r2 同现的频率高, 则 r1 更有 可能是这对词汇正确的上下文关系. 另外, 在大语料 中的一对词汇以转折关系同现的频率与以非转折关 系同现的频率相同时, 将转折关系作为这对词汇在 SORN 中的上下文关系会更好 (见第 4.2 节实验结 果). 由此, 引入构建 BSORN 的 cij 具体定义, 即式 (5). 其中, naij 和 nbij 分别表示 wi 和 wj 在语料中 以非转折关系同现的次数和以转折关系同现的次数. cij =  1, naij > nbij −1, naij ≤ nbij 6= 0 ∞, 否则 (5) qij = { +∞, cij =∞ 1, 否则 (6) 由W , 式 (5) 确定的 C 以及式 (6) 确定的Q 联合构 建的 SORN 被称为 BSORN. 式 (6) 表明, BSORN 中各边权重相等, 也就是说 BSORN 相当于一个无 权重无向图, 它没有提供任何 SORN 上下文关系的 噪声强度. 接下来构建的 PANIM 能够给 SORN 上 下文关系赋予合理的噪声强度. 3.2 PANIM 如果一对词汇在语料中只存在一种上下文关系 且其出现频率很高, 则这种关系通常就是这对词汇 正确的上下文关系. 该现象是构建 PANIM 的基础. 由此引出 cij 的另一个具体定义, 即式 (7). cij =  1, naij > α ≥ 0 且 nbij = 0 −1, naij = 0 且 nbij > β ≥ 0 ∞, 否则 (7) 由 W , 式 (7) 确定的 C 以及式 (6) 确定的 Q 联合 构建的 SORN 被简称为 SORN(α, β). 一方面, 第 4.3.1 节实验表明: SORN(α, β) 的 连通性随着 α 和 β 的增大而变小, 然而 SWSOA 算 法利用 SORN(α, β) 所鉴定WSO 的精确度却随着 α 和 β 的增大而增大, 并当 α 和 β 增大到一定程 度时精确度稳定到 1.0. 另一方面, 第 4.2 节实验表 明: SWSOA 算法利用 BSORN 所鉴定WSO 的精 确度相对比较低, 但 BSORN 的连通性较好. 依据 SWSOA 算法, 对其输入的 SORN 连通性越小, 该 算法能够鉴定倾向性的情感词汇就越少. 理想状况是能够高精确度地鉴定自由评论语料 中所有情感词汇的倾向性, 因此高精确度而连通性 很小或低精确度而连通性很大都不可行. 那么能否 利用 SORN(α, β) 和 BSORN 各自的长处来构建一 个具有良好的连通性和抗噪声能力的 SORN 呢? 的 确如此. 抗噪声能力的大小直接决定着精确度的高 低. SWSOA 算法分类词汇倾向性的精确度越高意 味着分类的倾向性结果中错误的倾向性信息就越 少. 所以, 可将 SWSOA(SORN(α, β)) 获得的高精 3期 殷春霞等: 利用复杂网络为自由评论鉴定词汇情感倾向性 393 确度词汇倾向性信息组成抗噪声信息, 使得用这些 抗噪声信息优化调整 BSORN 后获得的 SORN 具 有两个特点: 连通性不小于 BSORN 和具有良好的 抗噪声能力. 实现这个目标需要解决两个关键问 题: 1) 如何产生抗噪声信息? 2) 如何利用抗噪声 信息优化调整一个 SORN? 第一个问题的解决 是: 将 SWSOA 算法作用于一个拥有大 α 和 β 的 SORN(α, β), 然后给获得的有价值倾向性信息赋予 一个体现该倾向性信息发生错误可能性的噪声值. 显然, α 和 β 越小, 赋予的噪声值就应该越大. 接着 将上述倾向性信息和其噪声值作为一个信息层添加 到抗噪声信息中. 更新减小 α 和 β, 用获得的抗噪 声信息优化调整当前的 SORN(α, β). 这个过程迭 代下去, 直到取得足够的抗噪声信息. 通过这种方式 获得的第 i 个信息层会比第 i − 1 个庞大, 以至于 由一个个信息层组成的抗噪声信息呈现出金字塔形 状, 只是这个金字塔是从顶部开始构建的, 因此形象 化地将最终形成的抗噪声信息称为 PANIM. PAN- IMA 算法具体描述了上述构建 PANIM 的思路. 第 二个问题的解决方案是: 按噪声值从小到大依次利 用抗噪声信息中的信息层来调整当前 SORN. 信息 层的噪声值越低意味着该信息层中同倾向性词汇以 越大的概率是同倾向性的, 不同倾向性词汇以越大 的概率是不同倾向性的. 为了能够充分且尽量正确 地利用抗噪声信息, 对其包含的每一个信息层, 在当 前 SORN 中建立一个全连通子图 (充分性), 即该信 息层同倾向性情感词汇节点两两之间建立非转折关 系的边, 该信息层不同倾向性情感词汇节点两两之 间建立转折关系的边; 该子图中仅噪声强度高于该 信息层噪声值的边被重新赋予该信息层噪声值 (正 确性), 这样做的目的是不干扰低噪声值的信息层已 优化调整的结果, 如此才能保证 SWSOA 算法尽可 能选择干净路径来计算词汇之间情感倾向性关系. ANISA 算法具体描述了上述利用抗噪声信息优化 调整 SORN 的思路. 在给出 PANIMA 算法和 ANISA 算法之前, 先 解释一下其中的相关符号以及 α, β 的更新方式. µ 和 ν 分别表示 α 和 β 更新减少量. θα 和 θβ 分别是建立 PANIM 需要的 α 下限和 β 下限. γ 表示噪声值. δ 表示 γ 的更新增量. H 是存放 抗噪声信息的哈希表, 关键字为信息层编号 l, 值为 [γ, (Pl, Nl)], 每一个 (l, [γ, (Pl, Nl)]) 构成 H 中的一 个信息层. Pl 和 Nl 是分别存放 positive 词汇和 negative 词汇的集合. l 初始化为 1. H, Pl 和Nl 各 自初始化为空. α, β 的更新方式 (首次更新使用步骤 1): 步骤 1. 如果 α > 0, 则 α = α − µ 且 β 不变, 否则如果 β > 0, 则 α 不变且 β = β − ν, 否则更新 结束. 若还能进行下一次更新, 则执行步骤 2 获得下 一个更新值. 步骤 2. 如果 β > 0,则 α = α+µ且 β = β−ν, 否则 α = α+ µ 且 β 不变. 执行步骤 3 获得下一个 更新值. 步骤 3. 如果 α > 0, 则 α = α − µ 且 β 不变, 否则如果 β > 0, 则 α 不变且 β = β − ν, 否则更新 结束. 若还能进行下一次更新, 则执行步骤 1 获得下 一个更新值. PANIMA 算法的输入参数有: α, β, µ, ν, θα, θβ, γ 以及 δ. 为方便使用, 将该算法表示成函数 PANIMA (α, β, µ, ν, θα, θβ, γ,δ). PANIMA算法. 步骤 1. 若满足条件 α ≤ θα, β ≤ θβ 且 γ + δ < 1, 则执行步骤 2∼ 6, 否则执行步骤 7. 步骤 2. 利用 ANISA 算法将 SORN(α, β) 在 H 下调整, 即执行 ANISA(SORN(α, β),H). 调整 后获得的 SORN 被记为 SORN(H,α, β). 步骤 3. 利用 SWSOA 算法对 SORN(H,α, β) 最大连通子图中的词汇进行情感倾向性分类, 即执 行 SWSOA(SORN(H,α, β)). 将倾向性分类结果分 别存放于 Pl 和 Nl 中. 步骤 4. 为了避免高噪声 (低精度) 信息层中的 倾向性信息与低噪声 (高精度) 信息层中的倾向性信 息发生冲突, 对 Pl 和 Nl 做如下处理: X = Pl − (Pl−1 ∪ Nl−1), Pl = X ∪ Pl−1, Y = Nl − (Pl−1 ∪ Nl−1), Nl = Y ∪Nl−1. 步骤 5. 若 Pl 6= Pl−1 或 Nl 6= Nl−1, 则在 H 中添加一个新信息层 (l, [γ, (Pl, Nl)]), 并且 γ = γ + δ, l = l + 1. 步骤 6. 更新 α 和 β, 转向步骤 1. 步骤 7. PANIM 构造完成. 目前的 H 便是 PANIM. 该算法第一次迭代时, 步骤 4 涉及的 P0 和 N0 是两个空集合. 为了保证 PANIM 中的每个信息层 的确是有用的信息层, 算法中要求 γ + δ < 1. ANISA 算法的输入参数为 SORN 和H. 为方 便使用, 将该算法表示成函数 ANISA(SORN,H). ANISA算法. 按 l 或 γ 从小到大的顺序依次利用 H 中的信 息层 (l, [γ, (Pl, Nl)]) 来调整 SORN, 调整方式如下: 检查 Pl ∪ Nl 中的每对元素 wi 和 wj, 在满足 qij > γ 条件下执行: 如果 (wi ∈ Pl 且 wj ∈ Pl) 或 (wi ∈ Nl 且 wj ∈ Nl), 则 cij = 1 且 qij = γ; 否则 cij = −1 且 qij = γ. 第 4.3.2 节给出了构建 PANIM 的具体例子. 3.3 ANSORN 执行 ANISA(BSORN, PANIM) 使得 BSORN 在 PANIM 的优化调整下演化成 ANSORN. 显然, 394 自 动 化 学 报 38卷 ANSORN 被 BSORN 和 PANIM 唯一确定. 如此 构建的 ANSORN 必然具有两个特点: 良好的连通 性和良好的抗噪声能力. 4 实验及结果分析 4.1 实验数据以及测量 与产品、新闻事件等评论对象不同, 影视作品 往往能够引发人们的内在强烈情感, 因此影视自由 评论包含的情感信息非常丰富. 本文选择互联网上 的中文影视自由评论作为实验语料. 形容词是好的 主观评价指示器[24], 与其他词性相比, 形容词蕴含 着更为丰富的情感, 因此选择形容词为研究对象. 实验语料是从人人网 (http://movie.renren.com) 上获取的电影《赤壁》的自由评论以及从豆瓣网 (http://www.douban.com) 上获取的电影《唐山大 地震》的自由评论. 实验中的语料规模以句子为单 位进行统计. 为了构建 SORN, 需要提前做一些预处 理工作: 1) 暂不考虑 “反语、讽刺” 情况, 因此将包 含有 “反语、讽刺” 的句子剔除; 2) 使用 ICTCLAS 分词程序对语料进行分词和词性标注; 3) 将第 2) 步的结果以句子为单位进行否定词匹配和转折词识 别, 从而抽取出以句子为单位的形容词序列集合. 形 容词序列集合是构建 SORN 的基础材料. 请中文 系 7 人将抽取出的所有形容词按照所在上下文进行 positive 或 negative 情感倾向性标注, 采取少数人 服从多数人的原则, 最后产生表 1 中的电影《赤壁》 测试集和电影《唐山大地震》测试集. x, y 和 z 分别表示在相应语料规模下的语料中 包含的 positive 形容词数量、negative 形容词数量 及两者之和. 使用式 (8) 计算算法鉴定WSO 的精确度. 精确度 = xr + yr z (8) 其中, xr 和 yr 分别表示在 z 个形容词中被正确鉴 定的 positive 词汇数量和 negative 词汇数量. 4.2 构建 BSORN 首先引入两个具体的 SORN: SORNa 和 SORNb. cij =  1, naij ≥ nbij −1, naij < nbij 6= 0 ∞, 否则 (9) 一对词汇以转折关系同现的频率和以非转折关 系同现的频率相同的情况下, 式 (5) 将转折关系作 为这对词汇的 SORN 上下文关系, 式 (9) 将非转 折关系作为这对词汇的 SORN 上下文关系. 将W、 式 (9) 确定的 C 以及式 (6) 确定的 Q 联合构建的 SORN 记为 SORNa. 将W , 式 (5) 确定的 C 以及 式 (6) 确定的 Q 联合构建的 SORN 记为 SORNb. 图 2 展示了分别将 SORNa 和 SORNb 作为 SWSOA 算法的输入所鉴定WSO 的精确度. 该图 表明, 在大语料 (规模超过 15 000) 中的一对词汇以 转折关系同现的频率与以非转折关系同现的频率相 同时, 与非转折关系相比, 将转折关系作为这对词汇 图 2 SWSOA(SORNa) 和 SWSOA(SORNb) 的精确度 Fig. 2 Accuracies of SWSOA(SORNa) and SWSOA(SORNb) 表 1 测试集 Table 1 Test data 语料规模 1 000 2 000 4 000 6 000 8 000 10 000 12 500 15 000 17 500 20 000 22 500 25 000 27 500 30 000 x 96 145 216 264 309 352 387 421 455 483 501 531 543 557 《赤壁》 y 53 77 121 155 185 207 234 266 285 293 303 313 319 327 z 149 222 337 419 494 559 621 687 740 776 804 844 862 884 x 100 153 228 285 331 374 403 442 470 502 522 558 570 583 《唐山大地震》 y 51 67 114 152 186 210 242 281 296 303 315 326 334 344 z 151 220 342 437 517 584 645 723 766 805 837 884 904 927 3期 殷春霞等: 利用复杂网络为自由评论鉴定词汇情感倾向性 395 在 SORN 中的上下文关系会获得更好的词汇倾向 性分类结果. 由此, SORNb 便是 BSORN. 图 2 表明, 对 于《赤壁》和《唐山大地震》, 在语料规模 30 000 时, BSORN 的连通性分别为 0.828 和 0.831, SWSOA(BSORN) 所鉴定 WSO 的精确度分别为 0.663 和 0.69. 4.3 构建 PANIM 4.3.1 SORN(ααα, βββ)特性 本小节使用语料规模为 30 000 时的自由评论来 展现 SORN(α, β) 的特性. 图 3 表明: SORN(α, β) 的连通性随着 α 和 β 的增大而变小, 然而 SWSOA 算法利用 SORN(α, β) 所鉴定WSO 的精确度却随 着 α 和 β 的增大而增大, 并当 α 和 β 增大到一定程 度时精确度稳定到 1.0. 图 3 SORN(α, β) 的特性 Fig. 3 Characteristics of SORN(α, β) 4.3.2 PANIM的构建过程 本小节使用语料规模为 30 000 时电影《赤壁》 的自由评论来解释 PANIM 的构建过程. 现将 PANIMA 算法的输入参数分别初始化为: α = 6, β = 4, µ = 2, ν = 1, θα = 2, θβ = 3 和 γ = δ = 0.12. 执行 PANIMA (6, 4, 2, 1, 2, 3, 0.12, 0.12) 构建的 PANIM 如表 2 所示. 其中粗体字的词 汇是倾向性被分类错误的词汇. 依据 PANIMA算法, 完成该 PANIM的构建总 共经历了 5 次迭代. 第 1 次迭代: l = 1, γ = 0.12, α = 6, β = 4, H = ∅. 图 4 (a) 是执行 ANISA(SORN(6, 4), ∅) 获得 的 SORN(∅, 6, 4) 的最大连通子图. 建立第 1 个信 息层 (1, [0.12, (P1, N1)]). 此时H 仅由该信息层构 成, 记作 H1. 第 2 次迭代: l = 2, γ = 0.24, α = 4, β = 4, H = H1. 图 4 (b) 是执行 ANISA(SORN(4, 4), H1) 获得的 SORN(H1, 4, 4) 的最大连通子图, 该连通子 图包含着第 1 个信息层中所有情感词汇构成的全连 通子图 C1. C1 各条边的噪声强度均为 0.12, 且 P1 中两两词汇之间以及 N1 中两两词汇之间用黑色线 条连接, P1中任意词汇与N1中任意词汇之间用灰色 表 2 θα = 2 和 θβ = 3 时构建的 PANIM Table 2 PANIM when θα = 2 and θβ = 3 l γ Pl Nl 1 0.12 好看 成功 壮观 不错 棒 恢弘 宏伟 幽默 一般 2 0.24 好看 壮观 成功 不错 棒 恢弘 宏伟 幽默 一般 失望 大气 精彩 强大 好 开心 冷静 老 紧张 烂 好看 壮观 成功 不错 大气 棒 精彩 恢弘 宏伟 幽默 强大 好 开心 冷静 老 紧张 一般 失望 3 0.36 妙 真实 诚实 豪爽 轻松 完美 妩媚 诙谐 烂 差 嗲 鲜明 冗长 强 窝囊 挑剔 拖沓 血腥 无聊 恶心 过时 厉害 难得 闷 可爱 好笑 不行 优秀 冷 不好 妙 幼稚 风趣 过瘾 感人 雷人 (a) SORN(∅, 6, 4) 的最大连通子图 (a) The maximal connected subgraph of SORN(∅, 6, 4) (b) SORN(H1, 4, 4) 的最大连通子图 (b) The maximal connected subgraph of SORN(H1, 4, 4) 396 自 动 化 学 报 38卷 (c) SORN(H2, 2, 3) 的最大连通子图 (c) The maximal connected subgraph of SORN(H2, 2, 3) 图 4 最大连通子图 Fig. 4 The maximal connected subgraph 线条连接. 建立第 2 个信息层 (2, [0.24, (P2, N2)]). 此时 H 由已获得的两个信息层组成, 记作 H2. 第 3 次迭代: l = 3, γ = 0.36, α = 6, β = 3, H = H2. 本次迭代中 P3 = P2 且 N3 = N2, 即本次迭 代没有增加新的有价值信息. 因此不建立新信息层. 第 4 次迭代: α = 4, β = 3, 仍然 l = 3, γ = 0.36, H = H2. 本次迭代也没有增加新的有价值信 息, 因此本次迭代也不建立新信息层. 第 5 次迭代: α = 2, β = 3, 仍然 l = 3, γ = 0.36, H = H2. 执行 ANISA(SORN(2, 3), H2) 使 得 SORN(2, 3) 被 H2 的两个信息层依次调整. 第 1 个信息层对 SORN(2, 3) 调整后获得的 SORN 被 记为 SORN1, SORN1 包含着 C1, 接着第 2 个信 息层对 SORN1 调整, 调整后获得的 SORN 被记 为 SORN2, SORN2 包含着第 2 个信息层中所有情 感词汇构成的全连通子图 C2, C2 完整保留着 C1. C2 中除 C1 包含的边之外的其他边噪声强度均为 0.24. 图 4 (c) 是执行 ANISA(SORN(2, 3), H2) 获 得的 SORN(H2, 2, 3) 的最大连通子图. 可以看到 图 4 (c) 中的全连通子图完整地保留了图 4 (b) 中的 全连通子图 (仅显示顺序有些不同). 建立第 3 个信 息层 (3, [0.36, (P3, N3)]). 此时H 由已获得的三个 信息层组成, 记作 H3. 5 次迭代结束后, H3 便是 θα = 2 和 θβ = 3 时 的 PANIM. 4.3.3 分析 PANIM算法的参数 在语料规模 30 000 的实验语料下, 若将 “α, β 更新方式” 中 α 和 β 分别换成 θα 和 θβ, 并初始化 θα 和 θβ 分别为 6 和 4, 则按更新顺序便获得 θα, θβ 的 11 对候选取值: 6, 4; 4, 4; 6, 3; 4, 3; 2, 3; 4, 2; 2, 2; 0, 2; 2, 1; 0, 1 和 0, 0. 第 i 对候选取 值被记为 θαi, θβi. 现在初始化 PANIMA 算法的输 入参数: α = 6, β = 4, µ = 2, ν = 1, θα = θαi, θβ = θβi 以及 γ = δ = 0.12. 执行 PANIMA(6, 4, 2, 1, θαi, θβi, 0.12, 0.12) 获得的 PANIM 被记 为PANIMi. 然后执行ANISA(BSORN, PANIMi), 并将 BSORN 在 PANIMi 调整下获得的 SORN 记 为 PANIMi BSORN. 图 5 展示了将 θαi, θβi 对应的 PANIMi BSORN 作为 SWSOA 算法输入时所鉴定 WSO 的精确度. 从图 5 看出: 无论是《赤壁》还是《唐山 大地震》, SWSOA(PANIMi BSORN) 精确度先升 后降. 这说明: θα, θβ 的 11 对候选取值中, 太靠 前或太靠后的候选取值对应的 PANIM 都不能给 BSORN 带来最好的抗噪声信息; 显然, 精确度最高 点时的候选取值 (记为 θαop, θβop) 对应的 PANIM (记为 PANIMop) 能给 BSORN 带来最好的抗噪声 信息. 因此, θα 和 θβ 应分别取值为 θαop 和 θβop. (a)《赤壁》 (a) Chibi (b)《唐山大地震》 (b) Tangshan Earthquake 图 5 SWSOA(PANIMi BSORN), SWSOA(BSORN) 和 HM 方法的比较 Fig. 5 Comparision among SWSOA(PANIMi BSORN), SWSOA(BSORN) and HM 这样, 执行 ANISA(BSORN, PANIMop) 后获 得的 SORN 便是 ANSORN. 4.4 与其他方法比较 考虑到实际应用, 在线词汇情感倾向性鉴定 应具备良好的时间效率. 如果在线情感挖掘系统 3期 殷春霞等: 利用复杂网络为自由评论鉴定词汇情感倾向性 397 的反馈速度让用户难以容忍, 即使该系统给出的 评价非常精确, 这个系统也是失败的. 基于规 范文本提出的方法普遍存在效率问题, 因此本文 取计算效率较好的 HM 方法来做比较. 此外, 为了展示 PANIM 确实能优化调整 BSORN, 将 SWSOA(PANIMi BSORN) 和 SWSOA(BSORN) 也做了比较. 在相同的自由评论实验语料 (语料规模为 30 000) 下, 图 5 展示了比较结果. 从图 5 可 以看出, 无论是《赤壁》还是《唐山大地震》 : 1) HM 方法最差, 说明基于规范文本提出的 WSO 鉴定方法不再适合为自由评论鉴定 WSO; 2) 每一个 SWSOA(PANIMi BSORN) 在精确度 方面都高于 SWSOA(BSORN), 这表明 θα, θβ 的 11 对候选取值分别对应的 PANIM 都能给 BSORN 带来有价值的抗噪声信息, 不过带来的 抗噪声信息质量因 θα, θβ 取值不同有差异; 3) 在《赤壁》测试语料下, SWSOA(ANSORN) 的 精确度比 SWSOA(BSORN) 高出 4 个百分点, 比 HM 方法高出 9.5 个百分点; 在《唐山大地 震》测试语料下, SWSOA(ANSORN) 的精确度比 SWSOA(BSORN) 高出 4.9 个百分点, 比 HM 方法 高出 11.8 个百分点. 实验数据表明了本文方法的精 确性. 本文利用 ANSORN 为自由评论鉴定WSO 具 有良好的时间效率. 这能从与 HM 方法的实际运 行时间比较上得到验证: 在相同的运行环境 (双核 CPU: 2.11GHz, 内存: 4G) 和实验语料 (语料规模 为 30 000 的《赤壁》和《唐山大地震》) 下, 本文方 法和 HM 方法分别平均需要 20.31 s 和 24.7 s 来鉴 定语料中的WSO. 5 结论 本文提出的利用复杂网络为自由评论鉴定 WSO 的方法是对自由评论进行粗粒度情感挖掘 的基础性研究. 主要成果总结如下: 1) 提出 PANIMA 算法和 ANISA 算法来构 建揭示词汇之间情感倾向性关系的复杂网络 AN- SORN. A