基于改进特征提取及聚类的网络评论挖掘研究

李昌兵+庞崇鹏 凌永亮+王强

〔摘要〕[目的/意义]针对信息过载条件下中文网络产品评论中特征提取性能低以及特征聚类中初始中心点的选取问题。[方法/过程]本研究提出采用基于权重的改进Apriori算法产生候选产品特征集合，再根据独立支持度、频繁项名词非特征规则及基于网络搜索引擎的PMI算法对候选产品特征集合进行过滤。并以基于HowNet的语义相似度和特征观点共现作为衡量产品特征之间关联程度的特征，提出一种改进 K-means 聚类算法对产品特征进行聚类。[结果/结论]实验结果表明，在特征提取阶段，查准率为69%，查全率为9264%，综合值达到7907%。在特征聚类阶段，本文提出的改进K-means算法相对传统算法具有更优的挖掘性能。

〔关键词〕Apriori算法；特征提取；PMI算法；K-means算法；语义相似度

DOI：10.3969/j.issn.1008-0821.2018.02.011

〔中图分类号〕TP393〔文献标识码〕A〔文章编号〕1008-0821（2018）02-0068-07

Research on Network Review Mining Based on Improved

Feature Extraction and Clustering

Li ChangbingPang Chongpeng*Ling YongliangWang Qiang

（School of Economics and Management，Chongqing University of Posts and Telecommunications，

Chongqing 400065，China）

〔Abstract〕[Purpose/Significance]Aiming at the problem that the feature extraction performance is low and the initial center point in the feature clustering is under the condition of information overload condition.[Method/Process]In this study，a new Apriori algorithm based on weight was proposed to generate candidate product feature sets，and then the candidate product feature sets were filtered according to independent support，frequent item term non-feature rules and PMI algorithm based on web search engine.Based on HowNets semantic similarity and feature view co - occurrence as a feature to measure the degree of correlation between product features，an improved K - means clustering algorithm was proposed to cluster the product characteristics.[Result/Conclusion]The experimental results showed that the precision is 69%，the recall rate was 9264%，and the comprehensive value was 7907%.In the stage of feature clustering，the improved K-means algorithm proposed in this paper had better mining performance than traditional algorithm.

〔Key words〕Apriori algorithm；feature extraction；PMI algorithm；K-means algorithm；semantic similarity

隨着互联网的迅速发展，评论挖掘作为一种从数据中探索有用信息为目标的技术逐渐被研究者所关注。在许多电商领域，用户在做出购买决策之前都会浏览产品的评论信息以此决定是否购买该产品。然而，在信息过载条件下，通常的分类目录和搜索引擎需要用户能准确描述自己的需求，而当用户无法准确描述自己的需求时，前述方法就无能为力了。这时就需要借助以数据挖掘技术为基础的推荐系统，从海量的网络产品评论信息中获取自己需要的信息、产品或服务。

产品特征提取是在海量的网络产品评论信息中提取出用户真正关心的产品特征。在这些产品特征里，往往会发现同一种特征在评论句子中可以有不同的短语或词来描述，如评价手机的“功能”和“机能”实际上表示的是同一个产品特征。因此，对提取出的产品特征信息进行相应聚类也是非常有意义的。现如今，许多国内外研究者在这些方面都取得了不错的成果。在特征提取方面，Zhuang L等[1]采用人工或半自动的方式对电影中文评论领域进行产品特征提取研究。Kobayash N等[2]提出利用产品、产品特征和观点词之间的共现模式的半自动化方法提取产品特征和观点词。娄德成等[3]利用半自动方式进行人工定义，从而抽取出产品评论信息。Hu M等[4]抽取出现频率大的名词及名词短语作为候选产品特征，通过压缩剪枝和冗余剪枝策略对提取的频繁商品特征进行筛选，再使用关联规则挖掘识别频繁产品特征。此方法使得各性能指标有了较大提升。Popescu A M等[5]将产品特征看作是产品的一部分，使用候选产品特征和领域特征之间的共现来提取商品特征，并使用点互信息PMI（Pointwise Mutual Information）表示关联程度，最终按关联程度大小选择商品特征。该方法提高了产品特征提取的准确率，但召回率有所下降。在特征聚类方面，Guo H等人提出了一种两层监督算法mLSA，根据多层次潜在语义关联技术实现对产品特征的聚类[6]。Zhai和Liu在EM算法的基础上提出了一种约束的半监督的SC-EM学习方法归纳特征，主要采用两条约束信息，选择文本上下文信息作为特征，并对其中一条约束信息进行人工标注，进行分类器分类，通过实验验证此方法具有明显的可行性[7]。杨源等提出一种权重标准化方法，然后结合Zhai提出的SC-EM方法，来计算被提取的产品特征之间的相似度，大大提高了聚类效果[8]。张姝等人第一次把经典K-means算法应用于对产品特征进行聚类[9]。Guo H等人提出了一种PLSA方法，利用产品特征词和观点词往往同时出现的信息，对产品特征进行聚类，并取得比较好的聚类效果[6]。对于传统的K-means算法来说，对初始类中心点的选择并不理想，导致聚类效果不佳。

所以，针对上述存在的问题。传统关联规则Apriori算法运行效率低，以及其是根据特征项出现频次来设置最低支持度，会导致频次相对较低且更有价值的特征项未被提取出来。基于此，本文首次将基于权重的改进Apriori算法[10]引入到产品特征预抽取阶段进行频繁项挖掘，然后采用基于网络搜索引擎的PMI算法[11]进行过滤提取最优产品特征集合。传统的K-means算法在选择初始类中心点的时候是随机选择的，而初始类中心点的选择对聚类效果起着重要性作用，本文引入图论中最小生成树Prim算法[12]选择初始类中心点，对聚类算法进行改进。实验结果表明，挖掘性能指标均有显著提高。

1中文网络产品评论挖掘的框架流程

如图1所示，具体步骤如下：

1）应用Python工具的Jieba分词包对原始评论语料进行分词和词性标注。

2）根据Jieba分词工具所使用的词语标记符号，其中与名词相关的子集标记符号有{/n，/nr，/ns，/nt，/nz，/nl，/ng}，再根据这些标记符号所代表的含义和语法特点，本文选取{/n}作为抽取规则。使用计算机程序对每一条评论中进行抽取。

3）采用基于权重的改进Apriori算法产生候选集合。

4）建立常见中文频繁项名词却非产品特征的集合，并从中文语义及语法角度过滤候选特征集合，利用基于网络搜索引擎的PMI算法进一步过滤形成产品特征集合。常见的频繁项名词却非产品特征主要划定为以下几种情况：

①常见商品的品牌。例如“诺基亚”、“三星”、“西门子”等名词。

②一些常见的口语化名词。例如“机子”、“情况”、“方面”、“卖点”、“优缺点”等。

③与产品无关的称呼类名词，例如“朋友”、“同事”、“男子”等。

④计算机程序识别出来的少量错误名词，例如“高端”、“聊天”、“海量”等。

⑤常见的集合类名词，例如“群组”、“大家”等。

⑥单字词，例如“功”、“卡”等。

5）利用改进语义相似度算法提取特征信息。

6）利用改进传统K-means算法进行特征聚类形成特征聚类集合。

2具体改进算法

本文从两个方面对中文网络产品评论挖掘方法进行改进。首先首次将基于矩阵与权重的改进Apriori算法运用到特征预选择阶段，再利用基于网络与搜索引擎的PMI算法进行最终过滤；然后，针对传统K-means聚类算法随机选择初始类中心点的不足，提出用图论中的Prim算法来确定选择初始类中心点，从而实现较好的聚类效果。

21基于权重的改进Apriori算法

用评论语料和特征集合I0构建0～1矩阵M如下：

M=a11a12…a1n

a21a22…a2n

am1am2…amn

式中，aij=1，aij∈Ti

0，aijTi，Ti表示第i条评论，i=1，2，3，…，m，j=1，2，3，…，n，I={I1，I2，I3，…，In}表示N个特征

图1中文网络产品评论挖掘的框架流程

集合。Ij在事务数据库中出现的概率为p（Ij），计算见式（1），IJ的权重记为w（Ij），与p（Ij）有关，w（Ij）的计算公式见（2）。

p（Ij）=l/m（1）

w（Ij）=1/p（Ij）（2）

式中，l表示Ij在事务集中出现的次数，即上述矩阵中第j列中1的个数，m是评论语料的总条数。

事务Tk指数据集中的第k条评论，它的权重指该评论中所包含的特征项的平均权重，记为wt（Tk），即对aij=1的所有w（Ij）求平均值，其中j=1，2，3，…，n，计算见式（3）。

wt（Tk）=∑Ij∈Tkj=1w（Ij）/Tk（3）

式中，Tk表示评论Tk中包含的特征项的个数。

项的权重支持度记为w sup port，权重支持度表示包含特征项的事务权重占所有事务权重的比例，计算见式（4）。

w sup port（S）=∑STkk=1wt（Tk）/∑mk=1wt（Tk）（4）

式中，S表示事务数据库中的任意特征项。

基于权重的改进Apriori算法具体步骤如下：

1）扫描事务数据库，构建0～1事务矩阵，并根据事务矩阵计算出每个特征項和事务的权重，即w（Ij），wt（Tk）。

2）根据事务矩阵得到候选1-项集C1，计算C1中每个特征项的权重支持度w sup port（S），找出满足最小支持度k的频繁-项集Lk。

基于权重的改进Apriori算法流程图如图2所示：

22基于语义相似度聚类算法

本文首先用向量空间模型把产品特征f用向量表示，如feature（f1，f2，…，fn，o1，o2，…，om），其中fi表示产品特征词，oj表示产品特征对应的观点词，通过f和fi的字符串相似度及语义相似度来衡量fi的权重，同样的用f和oj的PMI值来衡量oi的权重。

本文以HowNet的语义相似度和特征观点共现作为衡量产品特征之间关联程度的特征。具体公式如下：

sim（Si，Sj）=x*simA（Si，Sj）+（1-x）*simB（Si，Sj）（5）

其中，x为对应的参数阈值，simA（Si，Sj）为特征之间基于HowNet词典中词语语义之间的相似度。假设有两个特征词S1、S2，若S1中含有m个概念：S11，S12，…，S1m，同样的S2中含有n个概念：S21，S22，…，S2n，对于S1和S2中对应的m和n个概念进行相应的组合，计算概念间的相似度，其中得到的相似度最大值作为两个词语S1和S2的相似度，相应的公式如（6）所示：

simA（S1，S2）=maxe=1…m，f=1…nsim（S1e，S2f）（6）

simB（Si，Sj）为基于特征和观点信息共现的特征相似度。将特征f表示为{O1，O2，…，On}，其中Oi为特征f的观点信息词，wi（S）对应为Oi的权重值，也就是观点词与特征词在词汇集中同时出现的频次，任意两个特征f1和f2语义相似度定义如（7）所示：

simB（S1，S2）=∑nOi∈S1，Oj∈S2wi（S1）wj（S2）sim（Oi，Oj）∑Oi∈S1wi（S1）∑Oj∈S2wj（S2）（7）

其中式（7）中，sim（Oi，Oj）表示两个特征词对应的观点词基于HowNet得出的相似度。

K-means聚类算法中最开始的一步是对初始类中心点进行选择，其选择的结果对下一步的聚类效果有着重要作用，而传统的聚类算法是随机选择初始类中心点，本文研究聚类算法就是对初始类中心点进行改进，并且采用产品特征之间的距离作为考核度量值，考虑将距离相近的两个特征放在同一个簇中，簇内特征尽量紧凑，最终得到的结果是各个独立的簇。

本文算法的基本思想是首先构建一个无向赋权图G=（V，E）；其次对初始类中心点进行选择，过程如下：首先利用图论中Prim算法生成最小生成树，最小生成树中每个节点对应的是产品特征词，根据权重值大小选择权重最小的K-1条边依次删除，最后得到K个连通子图；接着对K个连通子图中所有对象计算均值，并依据这些均值作为K个初始类中心点的选择然后进行相关聚类。改进的K-means聚类算法如图3所示：

图3改进后的K-means算法流程图

K-means聚类算法中还需要事先给出聚类类别K，但是一般情况下，聚类前都是不知道类别K的，本文算法中利用连通子图个数K来作为聚类类别K。本文研究的聚类算法中，每一个产品特征对应一个簇，通过计算该特征与其他簇中的产品特征的相似度都要超过设定的阈值来进行设定算法。

3算法性能评估

31评估指标

311特征抽取评估指标

本文采用查准率P、查全率R和综合值F-score作为特征抽取性能评估指标，具体计算方法如下：

P=AA+B（8）

R=AA+C（9）

F-score=2RPR+P（10）

A、B、C含义见表1所示：

312特征聚类评估指标

本文研究聚类算法为了验证算法的有效性，采用Rand Statistics来评价[13]。Rand Statistics评价的具体指标如下：若特征集合L得到一个聚类结果为R={R1，R2，…，Rk}，而且对应的特征集合的划分为C={C1，C2，…，Cs}，通过比较R与C之间的相似程度来衡量聚类算法的有效性，对于任意一对特征（li，lj）计算以下特征：

SS：li，lj在C和R中都属于同一个类。

SD：li，lj在C中属于同一个类，在R中不属于同一个类。

DS：li，lj在C中不属于同一个类，在R中属于同一个类。

DD：li，lj在C和R中都不属于同一个类。

用a、b、c、d来表示SS、SD、DS、DD的数目。假设a、b、c、d 4个指标之和为n，其中n为特征集中所有特征的个数，对应n=N（N-1）/2，那么R与C之间的相似程度可用如下公式来衡量：Rand Statistics=（a+b）/n，Rand Statistics的取值范围在0～1之间，越往1靠近，表示二者之间的相似度越高，聚类有效性也就越好。

由于研究算法中阈值的选取好坏直接影响到聚类效果，因此选择恰当的阈值，对于提高聚类效果意义重大，本文研究把评论语料作为训练集，通过不断调整Rand Statistics，观察聚类效果，当Rand Statistics值达到最大值时，聚类效果最好，也把此时的值作为阈值。

32实验数据

本文利用数据堂提供的手机评论语料（http：//www.datatang.com/data/43824）。选取其中800条作为实验数据，对语料进行手工标注得到手机产品特征204个，如表2所示：

通过前面对中文网络产品评论进行产品特征提取、优化过滤后得到产品评论的特征集合。针对此集合，采用人工标注的方法对产品评论对象进行人工标注，得到产品特征集。

33實验结果与分析

331特征提取结果分析

在用基于权重的改进Apriori算法进行频繁项挖掘，在考虑噪声的情况下，为使抽取出来的特征更加全面，本文多次对特征维度进行改变，得到的特征维度变化以及抽取出来的正确特征数（查全率）变化见表3：

根据表3可知，将特征维度选取为1900最佳。再根据中文产品特征规则进一步过滤特征集合，最后利用PMI算法进行最终过滤，提取出最优部分特征结果如表4所示：

对PMI设置不同的阈值，性能变化如图4所示：

通过以上实验结果可知，结合基于权重的改进Apriori算法与PMI算法进行特征提取时，当PMI值为-5时，挖掘结果综合性能最优，查准率达到69%，查全率达到9264%，综合值达到7907%。

332特征聚类结果分析

1）评估结果

首先对中文网络产品进行产品特征提取并进行过滤优化后，利用公式（7）的点互信息公式计算特征之间的相似度，然后进行聚类算法，在算法中选择Rand Statistics值最大时作为最后选择阈值，选择阈值如表6所示，从表中可以看出当阈值的值为045时，对应的Rand Statistics最高，为8675%，而此时对应的聚类效果也最好。针对于不同的阈值，对Rand Statistics变化情况如图5所示。

3）对比分析

对于手机评论的产品特征挖掘，通过实验分析，本文所提出的方法与K-means方法在性能指标上的比较结果如图6所示。

4结语

用户评论中蕴含了大量有价值的信息，识别出用户关注的产品特征并将产品信息按照特征进行组织至关重要。

本文专注于解决用户评论中产品特征的提取及聚类问题，首次采用基于矩阵与权重的改进Apriori算法进行频繁项挖掘，然后利用基于网络搜索引擎的PMI算法进行过滤形成最优特征集合。最后采用改进的聚类算法对所提取的产品特征进行聚类。通过使用本文的挖掘方法进行实验，取得了较好的效果。可以满足不同用户的信息需求，帮助潜在的消费者做出购买决策，也可以为生产商的产品改进提供有价值的反馈信息，为其提供决策支持。今后也将结合更多机器学习算法对评论文本中的情感倾向性进行相关研究。

参考文献

[1]Zhuang L，Jing F，Zhu X Y.Movie Review Mining and Summarization[C].In：Proceedings of the 15th ACM International Conference on Information and Knowledge Management （CIKM06），Arlington，Virginia，USA.New York：ACM，2006：43-50.

[2]Kobayashi N，Inui K，Matsumoto Y.Collecting Evaluative Expressions for Opinion Extraction[C].In：Proceedings of the 1st International Joint Conference on Natural Language Processing（IJCNLP04）.Berlin，Heidelberg：Springer-Verlag，2004：596-605.

[3]娄德成，姚天防.汉语句子语义极性分析和观点抽取方法的研究[J].计算机应用，2006，26（11）：2622-2625.

[4]Hu M，Liu B.Mining Opinion Features in Customer Reviews[C].In AAAI，2004：755-760.

[5]Popescu A M，Etzioni O.Extracting Product Features and Opinions From Reviews[C].In Proceedings of HLT-EMNLP 2005，ACL，2005：339-346.

[6]Guo H，Zhu H，Guo Z，et al.Product Feature Categorization with Multilevel Latent Sentiment Association.In：Proceedings of CIKM，2009：1087-1096.

[7]Zhai Zhongwu，Liu Bing，Xu Hua，et al.Groupting Features Using Semi-Supervised Learning with Soft-Constrains.Proceeding of the 23rd International Conference on Computational Linguistics （COLING-2010），2010：1272-1280.

[8]杨源，马云龙，林鸿飞.评论挖掘中产品属性归类问题研究[J].中文信息學报，2012，26（3）：104-108.

[9]扈中凯，郑小林，吴亚峰，等.基于用户评论挖掘的产品推荐算法[J].浙江大学学报：工学版，2013，47（8）：1475-1485.

[10]边根庆，王月.一种基于矩阵和权重改进的Apriori算法[J].微电子学与计算机，2017，（1）：136-140.

[11]王永，张勤，杨晓洁.中文网络评论中产品特征提取方法研究[J].现代图书情报技术，2013，（12）：70-73.

[12]江波，张黎.基于Prim算法的最小生成树优化研究[J].计算机工程与设计，2009，30（13）：3244-3247.

[13]Halkidi M，Batistakis Y，Vazirgiannis M.On Clustering Validation Techniques[J]. Journal of Intelligent Information Systems，2001，17（2-3）：107-145.

（实习编辑：陈媛）