基于CBC—LIKE算法的产品特征词聚类的研究
江伟+路松峰+杨莉萍
摘 要： 用户评论中存在产品特征表达多样性问题，在细粒度观点挖掘任务中需要对产品特征词聚类。首先，结合不同的语义相似度计算的特点，提出基于语义知识和上下文熵模型的语义相似度混合计算方法，计算抽取得到的特征词语义相似度；然后改进了传统CBC算法，提出适用于产品特征词聚类的CBC?LIKE方法实现聚类。最后在三个领域的真实评论语料上进行实验，对提出的语义相似度计算方法和聚类算法的性能进行了分析。实验结果表明，所提方法是有效的，与另外两种基线方法相比性能较优，取得了较好效果。
关键词： 产品特征； 语义相似度； 聚类算法； 观点挖掘
中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2017）14?0081?04
Abstract： Aiming at the problem of the various product feature expressions existing in user reviews， it′s necessary to cluster the product feature words in the task of fine?grained opinion mining. According to the calculation characteristics of different semantic similarities， a semantic similarity mixture calculation method based on semantic knowledge and context entropy model is proposed to calculate the extract the semantic similarity of feature words. The traditional CBC algorithm is improved. A CBC?LIKE method suitable for product feature words clustering is proposed. The experiment is conducted for the real review corpus in three domains. The performances of the proposed semantic similarity calculation method and clustering algorithm are analyzed. The experimental results show that the method is effective， its performance is better than that of other two benchmark methods， which has perfect effect.
Keywords： product feature； semantic similarity； clustering algorithm； opinion mining
产品评论领域中的细粒度意见挖掘旨在深入到产品特征层面，产品特征包含商品本身、商品的部件和属性、以及属性的特征等[1?2]。比如下面评论句子：I browsed the [pictures] in the computer， and found the [photos] were perfect and the [resolution] was high。其中方括号括起来的是相机这一领域产品评论的特征，而下划线的词语是针对该特征用户表达的观点。由于用户发表评论时通常具有很大的自由度和随意性，并且不同用户的表达习惯也并不相同，因此，用户评论文本呈现出高度的随意性和不确定性特点。例如在数码相机领域中，不同用户可能分别采用“picture quality”和“image clarity”表示“照片”特征，而相机产品评论中提到的“picture”，“image”和“photo”这三个特征表示的是同一特征[3?4]。针对产品特征词聚类问题，本文在完成特征抽取任务的基础上，结合不同的语义相似度计算的特点，提出基于语义知识和基于上下文熵模型的语义相似度混合计算方法，计算抽取得到的特征词的语义相似度，然后提出CBC?LIKE聚类方法完成特征词集合的聚类任务。最后对来自于三个领域的真实评论语料上的仿真实验结果表明，本文提出的方法对特征词的聚类效果是有效的，优于另外两种基线方法。
1 产品特征词聚类
1.1 混合特征词语义相似度计算
本文采用基于三种语义相似度计算的混合计算方法用于特征聚类。
（1） 对产品特征的表达往往会共享同样的词[5]。比如，“LCD screen”， “LCD viewfinder”，指的都是同样的产品特征“display”，这时，screen和viewfinder具有相同的含义，所以对共享词相似度的计算公式如下：
（2） 基于WordNet[6]的语义相似度量方法，常用Jiang & Conrath算法[7]，其计算方法如下：
式中：LCS表示和之间的最小公共包含（Least Common Subsumer）；IC表示信息量；是一个常量，表示WordNet的名词分类中概念总数。比如，本文实验中计算的产品特征“image”和“photo”语义相似度为0.744，而“image”和“battery”计算结果为0.221。
（3） 基于词典的方法的局限在于词典容量有限，语义覆盖程度不足[8]。所以本文进一步引入基于上下文熵的方法计算词的相似度，计算方法如下：
式中：，分别表示分布上下文中出现的特征词；，其中，和表示当前词的左上下文向量和右上下文向量[9]，上下文向量中的每个维度用TF?IDF作为向量值。，之间的距离可以通过它们的左右上下文分布的KL?divergence之和计算得到[10]。因为两个特征词分别都有其对应的左边上下文向量和右上下文向量，所以将两个相加计算得到，如下：
式中：和分别表示第维的词出现在特征词和的左（右）上下文向量中的概率权值；表示向量的维度。
最后，本文对基于上述三个语义相似度度量方法相结合，得到最终的相似度计算公式：
式中，和分别为语义相似度计算方法的权重，本文根据多次重复实验结果取值分别为0.7和0.4，实验中也对不同的语义相似度计算方法对聚类结果产生的影响进行了分析。
1.2 基于CBC算法的产品特征聚类
CBC算法[11]由Pantel等人提出，其基本思想是首先根据待聚类数据集中的数据紧凑度形成若干簇，然后采用递归的方法将高质量的候选聚类簇形成真正的中心，删除与其冲突的候选中心，待所有聚类中心确定后，计算残余元素与聚类中心的相似度，确定其归属。与K?means算法只用一个元素表示聚类的思想不同之处在于，该算法通过计算簇中元素的平均距离确定聚类的质心，从而可以避免因局部最优解而导致的较大误差，并且已被证明在根据词的语义相似度聚类中是有效的[11]。本文对传统CBC算法进行改进，提出CBC?LIKE算法用于特征词的聚类任务。与原始CBC算法一样该算法也分为三个步骤，不同的是，原始算法中需要两个阈值进行判断，而CBC?LIKE算法中只需要一个阈值即可，本文根据经验设置其值为0.35。另一方面改进是原始CBC算法的聚类簇数是未知的，所以其总是尽可能构建聚类簇，但在产品特征聚类任务中，事先可以根据产品领域人工设定聚类簇数[5]，比如“Battery Cluster”，“Photography Cluster”等，从而提高聚类效果。算法如下：
CBC?LIKE算法描述：
输入： 产品特征词集合S
聚类簇个数p
（Committee）种子成员个数q
输出： 特征词聚类结果C
步骤1：for each feature in S
计算语义相似度：ss（，），，属于S且将ss（，）按降序存入集合
end for
步骤2：for each feature in S
选择中前q个特征构成的committee：
计算 的平均相似度：
end for
将按照降序存入集合
定义C为存储聚类中心集合的一个列表，初始化为空
for each in
if 相似度s（C，）<且
if 为空 then 返回 C
end if
end for
步骤3：for each residue feature
分别计算与p个committee的语义相似度
把fi并入语义相似度最近的簇
end if
2 实验结果与分析
2.1 实验数据集与评估指标
为测试本文提出方法的有效性，使用从亚马逊电商网站（http：//www.amazon.com/）中收集的3个领域的语料，分别是Digital Camera，Vacuum，Cell Phone。为得到最佳标准，三个标注者对抽取的产品特征进行人工分类，从中选择至少两个以上相同标注者标注的标签作为最终标注结果。表1给出了收集语料和标注结果的基本统计信息。
文中，对于特征聚类效果的评价指标使用熵值（Entropy）和纯度（Purity）[6]，熵值用来衡量结果与标准划分相比的混乱程度，值越小，分类结果的混乱程度越低；纯度用来衡量分类结果与标准划分的一致性程度，值越大，分类结果的纯度越高。给定产品特征词集合FS和簇数，对该集合的最佳分类记作，聚类算法将特征词集合FS划分为k个独立子集，其熵值：
式中，表示结果类中包含标准类中元素的比例。给定一组对于每个特征词分类子集，其纯度：
式中，表示结果类中包含标准类中元素的比例。另外，为评估本文提出的基于CBC?LIKE聚类方法的效果，引入K?means和基于自动标注的半监督EM方法这两种聚类策略作为基线方法进行对比。
2.2 实验结果及分析
为了验证本文提出的CBC?LIKE算法中种子（committee）的个数对聚类效果的影响，实验中设置种子个数从1～6，在三个领域语料上分别进行了5轮实验，计算其对应的纯度和熵值。实验结果如图1所示。随着种子个数的增加，CBC?LIKE算法的性能首先是在增加，然后在某些点的位置上减少。这表明种子个数对产品特征聚类是有帮助的，但是随着种子数量的增加，会随之带来一些噪声信息。为了验证本文提出的基于CBC?LIKE聚类方法的有效性，将其与其他两个基线方法进行了比较，表2给出了不同聚类算法在三种产品领域集上Entropy和Purity值的比较结果。其中，对于特征词之间的相似度计算采用了本文提出的三种相似度计算结合的计算方法。可以看到，与KM和EM方法相比，雖然在某些领域上面CBC?LIKE方法的Entropy值和Purity值这两个指标不占优，但是其在三种产品领域的平均Entropy值上都取得了最小值，同时平均Purity值取得了最大值，准确率上与KM算法比较，具有较为明显优势，这表明，本文提出的CBC?LIKE方法在聚类性能上要优于其他两种聚类方法。
为了进一步分析不同的相似度计算对于CBC?LIKE聚类算法效果的影响。下面分别给出了基于词典的计算方法和基于共同词的相似度计算方法（WordNet+SW），基于上下文熵模型和共同词的计算方法（CE+SW），本文前述的基于三种方法结合的相似度计算方法（FS），实验结果如表3所示。从实验结果中可以看出，采用三种相似度计算相结合的方法在最后的聚类效果上要优于另外两种。从平均Entropy值和Purity的结果上可以看到，FS要优于前两种方法，而CE+SW又优于WN+SW的方法，说明采用上下文熵模型对于特征词的相似度度量方法具有较好效果，能较好地反应特征词在产品评论中的语义关系，这个和本文实验中对于两个调和参数α和β的实验性选取上是相印证的。
3 结 论
针对产品评论观点挖掘产品特征聚类进行了研究，提出在三种不同语义相似度的混合计算方法的基础上，用CBC?LIKE聚类算法完成特征词集合的聚类。最后的仿真实验结果表明，本文提出的三种不同语义相似度混合计算方法以及CBC?LIKE聚类算法能有效完成聚类任务，纯度和熵值这两个指标上的表现优于基线方法。
参考文献
[1] BALAZS J A， VEL?SQUEZ J D. Opinion mining and information fusion： a survey [J]. Information fusion， 2015， 27（C）： 95?110.
[2] HU M Q， LIU B. Mining and summarizing customer reviews [C]// Proceedings of 2004 the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Seattle： ACM， 2004： 168?177.
[3] YU Jianxing， ZHA Zhengjun， WANG Meng， et al. Aspect ranking： identifying important product aspects from online consumer reviews [C]// Proceedings of 2011 Annual Meeting of the Association for Computational Linguistics： Human Language Technologies. Portland： Association for Computational Linguistics， 2011： 1496?1505.
[4] XU H， ZHANG F， WANG W. Implicit feature identification in Chinese reviews using explicit topic mining model [J]. Knowledge?based systems， 2015， 76（5）： 166?175.
[5] ZHANG S， JIA W， XIA Y， et al. Product features extraction and categorization in Chinese reviews [C]// Proceedings of 2010 IEEE the 6th International Conference on Advanced Information Management and Service. [S.l.]： IEEE， 2010： 324?329.
[6] MILLER G A. WordNet： a lexical database for English [J]. Communications of the ACM， 1995， 38（11）： 39?41.
[7] ZHAI Zhongwu， LIU Bing， XU Hua， et al. Clustering product features for opinion mining [C]// Proceedings of the Forth International Conference on Web Search and Web Data Mining. Hong Kong， China： IEEE， 2011： 347?354.
[8] BRYNIELSSON J， JOHANSSON F， JONSSON C， et al. Emotion classification of social media posts for estimating people′s reactions to communicated alert messages during crises [J]. Security informatics， 2014， 3（1）： 1?11.
[9] XU T， PENG Q， CHENG Y. Identifying the semantic orientation of terms using S?HAL for sentiment analysis [J]. Knowledge?based systems， 2012， 35（15）： 279?289.
[10] ZHENG X， LIN Z， WANG X， et al. Incorporating appraisal expression patterns into topic modeling for aspect and sentiment word identification [J]. Knowledge?based systems， 2014， 61（2）： 29?47.
[11] PANTEL P， LIN D. Discovering word senses from text [C]// Proceedings of 2002 ACM SIGKDD Conference on Knowledge Discovery and Data Mining. [S.l.]： ACM， 2002： 613?619.
摘 要： 用户评论中存在产品特征表达多样性问题，在细粒度观点挖掘任务中需要对产品特征词聚类。首先，结合不同的语义相似度计算的特点，提出基于语义知识和上下文熵模型的语义相似度混合计算方法，计算抽取得到的特征词语义相似度；然后改进了传统CBC算法，提出适用于产品特征词聚类的CBC?LIKE方法实现聚类。最后在三个领域的真实评论语料上进行实验，对提出的语义相似度计算方法和聚类算法的性能进行了分析。实验结果表明，所提方法是有效的，与另外两种基线方法相比性能较优，取得了较好效果。
关键词： 产品特征； 语义相似度； 聚类算法； 观点挖掘
中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2017）14?0081?04
Abstract： Aiming at the problem of the various product feature expressions existing in user reviews， it′s necessary to cluster the product feature words in the task of fine?grained opinion mining. According to the calculation characteristics of different semantic similarities， a semantic similarity mixture calculation method based on semantic knowledge and context entropy model is proposed to calculate the extract the semantic similarity of feature words. The traditional CBC algorithm is improved. A CBC?LIKE method suitable for product feature words clustering is proposed. The experiment is conducted for the real review corpus in three domains. The performances of the proposed semantic similarity calculation method and clustering algorithm are analyzed. The experimental results show that the method is effective， its performance is better than that of other two benchmark methods， which has perfect effect.
Keywords： product feature； semantic similarity； clustering algorithm； opinion mining
产品评论领域中的细粒度意见挖掘旨在深入到产品特征层面，产品特征包含商品本身、商品的部件和属性、以及属性的特征等[1?2]。比如下面评论句子：I browsed the [pictures] in the computer， and found the [photos] were perfect and the [resolution] was high。其中方括号括起来的是相机这一领域产品评论的特征，而下划线的词语是针对该特征用户表达的观点。由于用户发表评论时通常具有很大的自由度和随意性，并且不同用户的表达习惯也并不相同，因此，用户评论文本呈现出高度的随意性和不确定性特点。例如在数码相机领域中，不同用户可能分别采用“picture quality”和“image clarity”表示“照片”特征，而相机产品评论中提到的“picture”，“image”和“photo”这三个特征表示的是同一特征[3?4]。针对产品特征词聚类问题，本文在完成特征抽取任务的基础上，结合不同的语义相似度计算的特点，提出基于语义知识和基于上下文熵模型的语义相似度混合计算方法，计算抽取得到的特征词的语义相似度，然后提出CBC?LIKE聚类方法完成特征词集合的聚类任务。最后对来自于三个领域的真实评论语料上的仿真实验结果表明，本文提出的方法对特征词的聚类效果是有效的，优于另外两种基线方法。
1 产品特征词聚类
1.1 混合特征词语义相似度计算
本文采用基于三种语义相似度计算的混合计算方法用于特征聚类。
（1） 对产品特征的表达往往会共享同样的词[5]。比如，“LCD screen”， “LCD viewfinder”，指的都是同样的产品特征“display”，这时，screen和viewfinder具有相同的含义，所以对共享词相似度的计算公式如下：
（2） 基于WordNet[6]的语义相似度量方法，常用Jiang & Conrath算法[7]，其计算方法如下：
式中：LCS表示和之间的最小公共包含（Least Common Subsumer）；IC表示信息量；是一个常量，表示WordNet的名词分类中概念总数。比如，本文实验中计算的产品特征“image”和“photo”语义相似度为0.744，而“image”和“battery”计算结果为0.221。
（3） 基于词典的方法的局限在于词典容量有限，语义覆盖程度不足[8]。所以本文进一步引入基于上下文熵的方法计算词的相似度，计算方法如下：
式中：，分别表示分布上下文中出现的特征词；，其中，和表示当前词的左上下文向量和右上下文向量[9]，上下文向量中的每个维度用TF?IDF作为向量值。，之间的距离可以通过它们的左右上下文分布的KL?divergence之和计算得到[10]。因为两个特征词分别都有其对应的左边上下文向量和右上下文向量，所以将两个相加计算得到，如下：
式中：和分别表示第维的词出现在特征词和的左（右）上下文向量中的概率权值；表示向量的维度。
最后，本文对基于上述三个语义相似度度量方法相结合，得到最终的相似度计算公式：
式中，和分别为语义相似度计算方法的权重，本文根据多次重复实验结果取值分别为0.7和0.4，实验中也对不同的语义相似度计算方法对聚类结果产生的影响进行了分析。
1.2 基于CBC算法的产品特征聚类
CBC算法[11]由Pantel等人提出，其基本思想是首先根据待聚类数据集中的数据紧凑度形成若干簇，然后采用递归的方法将高质量的候选聚类簇形成真正的中心，删除与其冲突的候选中心，待所有聚类中心确定后，计算残余元素与聚类中心的相似度，确定其归属。与K?means算法只用一个元素表示聚类的思想不同之处在于，该算法通过计算簇中元素的平均距离确定聚类的质心，从而可以避免因局部最优解而导致的较大误差，并且已被证明在根据词的语义相似度聚类中是有效的[11]。本文对传统CBC算法进行改进，提出CBC?LIKE算法用于特征词的聚类任务。与原始CBC算法一样该算法也分为三个步骤，不同的是，原始算法中需要两个阈值进行判断，而CBC?LIKE算法中只需要一个阈值即可，本文根据经验设置其值为0.35。另一方面改进是原始CBC算法的聚类簇数是未知的，所以其总是尽可能构建聚类簇，但在产品特征聚类任务中，事先可以根据产品领域人工设定聚类簇数[5]，比如“Battery Cluster”，“Photography Cluster”等，从而提高聚类效果。算法如下：
CBC?LIKE算法描述：
输入： 产品特征词集合S
聚类簇个数p
（Committee）种子成员个数q
输出： 特征词聚类结果C
步骤1：for each feature in S
计算语义相似度：ss（，），，属于S且将ss（，）按降序存入集合
end for
步骤2：for each feature in S
选择中前q个特征构成的committee：
计算 的平均相似度：
end for
将按照降序存入集合
定义C为存储聚类中心集合的一个列表，初始化为空
for each in
if 相似度s（C，）<且
if 为空 then 返回 C
end if
end for
步骤3：for each residue feature
分别计算与p个committee的语义相似度
把fi并入语义相似度最近的簇
end if
2 实验结果与分析
2.1 实验数据集与评估指标
为测试本文提出方法的有效性，使用从亚马逊电商网站（http：//www.amazon.com/）中收集的3个领域的语料，分别是Digital Camera，Vacuum，Cell Phone。为得到最佳标准，三个标注者对抽取的产品特征进行人工分类，从中选择至少两个以上相同标注者标注的标签作为最终标注结果。表1给出了收集语料和标注结果的基本统计信息。
文中，对于特征聚类效果的评价指标使用熵值（Entropy）和纯度（Purity）[6]，熵值用来衡量结果与标准划分相比的混乱程度，值越小，分类结果的混乱程度越低；纯度用来衡量分类结果与标准划分的一致性程度，值越大，分类结果的纯度越高。给定产品特征词集合FS和簇数，对该集合的最佳分类记作，聚类算法将特征词集合FS划分为k个独立子集，其熵值：
式中，表示结果类中包含标准类中元素的比例。给定一组对于每个特征词分类子集，其纯度：
式中，表示结果类中包含标准类中元素的比例。另外，为评估本文提出的基于CBC?LIKE聚类方法的效果，引入K?means和基于自动标注的半监督EM方法这两种聚类策略作为基线方法进行对比。
2.2 实验结果及分析
为了验证本文提出的CBC?LIKE算法中种子（committee）的个数对聚类效果的影响，实验中设置种子个数从1～6，在三个领域语料上分别进行了5轮实验，计算其对应的纯度和熵值。实验结果如图1所示。随着种子个数的增加，CBC?LIKE算法的性能首先是在增加，然后在某些点的位置上减少。这表明种子个数对产品特征聚类是有帮助的，但是随着种子数量的增加，会随之带来一些噪声信息。为了验证本文提出的基于CBC?LIKE聚类方法的有效性，将其与其他两个基线方法进行了比较，表2给出了不同聚类算法在三种产品领域集上Entropy和Purity值的比较结果。其中，对于特征词之间的相似度计算采用了本文提出的三种相似度计算结合的计算方法。可以看到，与KM和EM方法相比，雖然在某些领域上面CBC?LIKE方法的Entropy值和Purity值这两个指标不占优，但是其在三种产品领域的平均Entropy值上都取得了最小值，同时平均Purity值取得了最大值，准确率上与KM算法比较，具有较为明显优势，这表明，本文提出的CBC?LIKE方法在聚类性能上要优于其他两种聚类方法。
为了进一步分析不同的相似度计算对于CBC?LIKE聚类算法效果的影响。下面分别给出了基于词典的计算方法和基于共同词的相似度计算方法（WordNet+SW），基于上下文熵模型和共同词的计算方法（CE+SW），本文前述的基于三种方法结合的相似度计算方法（FS），实验结果如表3所示。从实验结果中可以看出，采用三种相似度计算相结合的方法在最后的聚类效果上要优于另外两种。从平均Entropy值和Purity的结果上可以看到，FS要优于前两种方法，而CE+SW又优于WN+SW的方法，说明采用上下文熵模型对于特征词的相似度度量方法具有较好效果，能较好地反应特征词在产品评论中的语义关系，这个和本文实验中对于两个调和参数α和β的实验性选取上是相印证的。
3 结 论
针对产品评论观点挖掘产品特征聚类进行了研究，提出在三种不同语义相似度的混合计算方法的基础上，用CBC?LIKE聚类算法完成特征词集合的聚类。最后的仿真实验结果表明，本文提出的三种不同语义相似度混合计算方法以及CBC?LIKE聚类算法能有效完成聚类任务，纯度和熵值这两个指标上的表现优于基线方法。
参考文献
[1] BALAZS J A， VEL?SQUEZ J D. Opinion mining and information fusion： a survey [J]. Information fusion， 2015， 27（C）： 95?110.
[2] HU M Q， LIU B. Mining and summarizing customer reviews [C]// Proceedings of 2004 the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Seattle： ACM， 2004： 168?177.
[3] YU Jianxing， ZHA Zhengjun， WANG Meng， et al. Aspect ranking： identifying important product aspects from online consumer reviews [C]// Proceedings of 2011 Annual Meeting of the Association for Computational Linguistics： Human Language Technologies. Portland： Association for Computational Linguistics， 2011： 1496?1505.
[4] XU H， ZHANG F， WANG W. Implicit feature identification in Chinese reviews using explicit topic mining model [J]. Knowledge?based systems， 2015， 76（5）： 166?175.
[5] ZHANG S， JIA W， XIA Y， et al. Product features extraction and categorization in Chinese reviews [C]// Proceedings of 2010 IEEE the 6th International Conference on Advanced Information Management and Service. [S.l.]： IEEE， 2010： 324?329.
[6] MILLER G A. WordNet： a lexical database for English [J]. Communications of the ACM， 1995， 38（11）： 39?41.
[7] ZHAI Zhongwu， LIU Bing， XU Hua， et al. Clustering product features for opinion mining [C]// Proceedings of the Forth International Conference on Web Search and Web Data Mining. Hong Kong， China： IEEE， 2011： 347?354.
[8] BRYNIELSSON J， JOHANSSON F， JONSSON C， et al. Emotion classification of social media posts for estimating people′s reactions to communicated alert messages during crises [J]. Security informatics， 2014， 3（1）： 1?11.
[9] XU T， PENG Q， CHENG Y. Identifying the semantic orientation of terms using S?HAL for sentiment analysis [J]. Knowledge?based systems， 2012， 35（15）： 279?289.
[10] ZHENG X， LIN Z， WANG X， et al. Incorporating appraisal expression patterns into topic modeling for aspect and sentiment word identification [J]. Knowledge?based systems， 2014， 61（2）： 29?47.
[11] PANTEL P， LIN D. Discovering word senses from text [C]// Proceedings of 2002 ACM SIGKDD Conference on Knowledge Discovery and Data Mining. [S.l.]： ACM， 2002： 613?619.
