张琪 纪淑娟 傅强 张纯金

摘 要：针对在电子商务平台上检测编写虚假评论的水军群组的问题，提出了基于带权评论图的水军群组检测算法（WGSA）。首先，利用共评论特征构建带权评论图，权重由一系列群组造假指标计算得到;然后，为边权重设置阈值筛选可疑子图;最后，从图的社区结构出发，利用社区发现算法生成最终的水军群组。在Yelp大型数据集上的实验结果表明，与K均值聚类算法（KMeans）、基于密度的噪声应用空间聚类算法（DBscan）以及层次聚类算法相比WGSA算法的准确度更高，同时对检测到水军群组的特征与差异作了分析，发现水军群组的活跃度不同，危害也不同。其中，高活跃度群组危害最大，应重点关注。

关键词：电子商务;水军群组;带权评论图;社区发现;聚类

中图分类号： TP391.4 模式识别与装置

文献标志码：A

Abstract： Concerning the problem that how to detect spammer groups writing fake reviews on the e-commerce platforms， a Weighted reviewer Graph based Spammer group detection Algorithm （WGSA） was proposed. Firstly， a weighted reviewer graph was built based on the co-reviewing feature with the weight calculated by a series of group spam indicators. Then， a threshold was set for the edge weight to filter the suspicious subgraphs. Finally， considering the community structure of the graph， the community discovery algorithm was used to generate the spammer groups. Compared with K-Means clustering algorithm （KMeans）， Density-Based spatial clustering of applications with noise （DBscan） and hierarchical clustering algorithm on the large dataset Yelp， the accuracy of WGSA is higher. The characteristics and distinction of the detected spammer groups were also analyzed， which show that spammer groups with different activeness have different harm. The high-active group is more harmful and should be concerned more.

Key words： e-commerce; spammer group; weighted reviewer graph; community discovery; clustering

0 引言

在电子商务平台上，在线商品评论在用户的决策中起着重要作用。用户倾向于购买正面评论较多的产品，而不是负面评论较多的产品。为了抬高或降低某产品的信誉，赚取更多利益，很多商家往往会雇佣虚假评论者发布大量赞美自家商品或诋毁竞争对手商品的不实评论，误导消费者，影响电商平台的公平竞争环境。这些虚假评论者称为水军。近年来，随着电子商务的迅猛发展，水军的规模也越发壮大，甚至结成水军群组协同作案。水军群组即指那些有组织地协同发布虚假评论的一群人。相比水军个体，水军群组影响力更大（甚至能控制产品的舆论走势、造成用户逆向选择）、隐秘性更强，因此对检测算法的设计要求更高。

在水军群组检测方面，研究者也提出了一些有针对性的检测方法。文献[1]首次进行了电商平台水军群组的检测工作，指出水军群组的一个重要特征——“共评论”，即水军成员通常共同评论相同的产品。为了检测共评论的水军群组，他们利用频繁项挖掘的方法寻找共评论过多个产品的评论者集作为候选水军群组，然后提出一种排序模型来定位最可疑的水军群组。

继文献[1]之后，文献[2]也使用频繁项挖掘的方法来确定候选水军群组，他们还评价了已有的用于识别评论者造假个体的特征与造假群组的特征的有效性;但是他们工作的目的是设计算法实现共谋者个体和非共谋者个体的检测，而不是水军群组的检测。文献[3]提出了一种水军群组检测算法。该算法分两步实现：第一步，量化某產品为水军目标产品的概率，定位目标产品;第二步，利用层次聚类算法得到水军群组。文献[4]提出基于评论产品构建二部图，然后利用一系列群组造假特征作为识别标准，使用图划分方法得到水军群组。文献[5]依据评论者“共评论”的关系特征构建用户关系网络，然后使用一系列特征构建多特征尺度空间模型进行水军群组的识别。

从已有群组检测研究的发展来看，利用基于图的方法来检测水军群组是一个趋势。群组划分多采用聚类算法、图划分算法。然而，上述方法只进行了水军群组的划分，没有对水军群组进行进一步的分析，探究不同水军群组间的联系和差别，以发现水军群组的整体行为特征。

针对上述工作的不足，本文提出了基于带权评论图的水军群组发现算法（Weighted reviewer Graph based Spammer group detection Algorithm， WGSA）。本文的主要工作总结如下：

1）本文在基于图的水军群组检测方法基础上，构建了带权评论图，然后利用权重筛选子图。该方法能够去掉大部分不重要的节点，大大降低计算的时空复杂度。

2）本文从图的社区结构出发，认为水军群组的造假行为会形成典型的社区结构，所以本文采用社区发现算法生成水军群组，实验证明效果较好。

3）基于Yelp的大型带标签数据集，本文对发现的水军群组作了全面的可疑度分析以证明本文算法的有效性，同时探究了水军群组的差异和整体行为特征。

1 水军群组检测算法

本章描述了本文提出的水军群组检测算法，算法由四个步骤组成，即水军群组造假行为特征选择、带权评论图的构建、可疑子图的筛选以及基于社区发现算法的水军群组的聚类。下面详细介绍每个步骤细节。

1.1 造假行为特征选择

在已有工作中，研究者提出了很多评估个人或群组的造假指标，例如语言指标[1， 3， 6-7]、行为指标[1-4， 8-12]、关系指标[2-6， 8-14]等。与之前提出的指标不同，本文使用行为指标量化两个评论者之间的共谋程度，具体指标如下。

1.1.1 共评论次数

水军群组的成员通常同时针对多个产品发表评论，协同合作完成任务。两两评论者，如果只共同评论过一件或两件产品，有可能只是因为巧合，是正常用户的评论，不能因此判定为水军组织成员;而评论用户作为分散的网络用户，若共同评论的产品数很多，就可视为非正常用户行为。本文利用共评论次数（Co-Reviewing Time， CRT）[1]来捕捉两两评论者的共评论特征。

1.1.2 评分相似度

水军群组通常协同发布虚假评论来抬高或贬低目标产品的评分。因此，水军群组成员往往发布相似评分来控制目标产品的评分趋势。本文定义了评分相似度（Similarity of Rating， SR）[5]来捕捉这种行为。

其中：Rp1是评论者n1对产品p的评分，评分R∈[1，5];本文引入了一个参数β以减少误差，β取值为2.5。SR（n1，n2）∈[1，5]，SR值越趋近于-1，表示两两评论者在同一维度上的评分值偏差越大;越趋近于1，表示两两评论者的观点一致性越强。

1.2 带权评论图的构建

在电子商务网站中，不同的用户可以通过两种方式建立联系：一种是用户之间的直接交互，例如用户发表评论和其他用户回复其评论。另一种隐含的联系是两个用户对同一产品进行评论，即共评论。一个水军群组的成员通常共同评论相同的产品，这是识别水军群组成员间联系的关键。

本文将评论者个体作为节点，将用户的共评论关系作为边的联系，构建带权评论图G=（N， E，W）。N是由全体评论者组成的节点集，边e=（n1，n2）∈E存在当且仅当评论者n1、n2至少共同评论过一个产品。边的权重w∈W，对应着每一条边，代表了两两评论者节点间共谋的可疑度。

边的权重w由1.1节描述的造假行为特征计算得到，计算式如下：

1.3 可疑子图的筛选

本文构建的评论图是基于评论者的共评论特性，边的权重代表了两两评论者间共谋的可疑度。因为原始评论图十分庞大，计算难度较高，本文首先进行可疑子图的筛选，既可以保证算法的准确度，也可以降低算法的时间复杂度。详见算法1。

1） 构建原始带权评论图G= （N， E， W） ，将边的权重初始化为1

2） for 边e=（n1，n2）∈E do

3）计算权重

4）if we< δ then

5） 移除边e

6） end for

7） 输出筛选得到的可疑子图

程序后

在算法1中，在第1）行，首先构建带权评论图G，将边的权重初始化为1;第2）～7）行，计算边的权重，设置边权重的阈值δ，移除边权重we<δ的边，得到筛选后的子图。边筛选阈值δ的确定在实验部分具体说明。

1.4 水军群组的聚类

水军群组的造假行为会在评论图中形成典型的社区结构，基于此，本文利用Louvain社区发现算法[16]来生成水军群组。Louvain算法是典型的社区发现算法，它基于最大化模块度进行社区划分，能够有效地发现网络中社区结构，即本文中的水军群组。

2 实验及结果分析

2.1 数据集

与文献[6，10-11]中的实验研究相同，本文也使用来自美国著名商户点评网站Yelp自2006年起历时7年的旅店评论数据。该数据集包含了评论虚假与否的标签，数据集的评论真率为61.1%。特别的，数据集中没有重复交易的买家和卖家对。每条评论包含以下属性：日期、评论ID、评论者ID、评论内容、评分、认为该评论有用的用户个数、认为该评论很酷的用户个数、认为该评论有趣的用户个数、标签、旅店ID。

在数据被使用之前，本文对数据集进行了如下预处理：

1）删除评论集中匿名的用户及评论数据。因为无法确定匿名是被同一人發表还是被多人发表。

2）删除不活跃的用户和产品。在本文研究中关注的是活跃度较高的用户，以及具有较高关注度的产品，不活跃的用户可疑性小，可以忽略。在数据集中评论用户发表的评论数少于三个，以及产品的评论数少于三个，则首先将其删除。

3）将数据表中未使用的属性去除，以精简数据集。

经过以上三个方面的数据处理之后，数据集的概况如表1所示。

2.2 边筛选阈值δ的确定

δ的大小决定了筛选得到的可疑子图的大小与质量：如果δ取值过大，删除的边过多，可能严重破坏子图的结构，影响后面社区划分的质量;如果取值太小，又无法保证得到的子图中边和节点的可疑度。由于边的权重是通过特征CRT与SR计算得到，本文分别探究了CRT的阈值，记作ωCRT和SR的阈值ωSR。如果一条边的CRT≥ωCRT，SR≥ωSR，则该边是可疑的。在这两个阈值的基础上，本文提出了如下δ计算方法：

2.2.1 ωCRT的计算

用式（2）计算评论图中边的CRT值，频繁2项集挖掘的结果如表2所示。边的CRT值统计数据如图1所示，其中61%的边的CRT值为3、4和5。

接下来的问题就是ωCRT的选取，以筛选可疑的边。如果ωCRT取值过大，会过滤掉大部分边，严重破坏图的结构;如果ωCRT取值过小，过滤效果不明显。为了避免过度破坏图的结构，本文选取了3个通用的指标：模块度（Modularity， Q）[17]、平均聚类系数（Average Clustering Coefficient， ACC）[18]和平均路径长度（Average Path Length， APL）[19]来评价网络社区结构。Q、ACC、APL值越大，则代表相应的图更紧密，社区结构更明显。本文采用插值法，计算了ωCRT取不同值时，筛选得到的子图的Q、ACC、APL值。计算结果如表3所示，当ωCRT=40时，Q、ACC、APL均取得最大值，这说明，此时的网络社区结构达到了最佳，所以，ωCRT取40。

2.2.2 ωSR的计算

用式（3）计算SR的值，对SR值的分布进行统计，如图2所示。从图2中可以看出，大部分边的SR值都大于0.5，这说明大部分边所连接的两两评论者之间的评分相似度极高，观点一致性较强。这里取ωSR为0.5。

2.3 水军群组的聚类

2.4 结果分析

鉴于本文使用的Yelp数据集只有评论虚假与否的标签，首先从虚假评论比例出发，分析了检测到的水军群组的特征与差异。然后选取K均值聚类算法（K-Means clustering algorithm， KMeans）、基于密度的噪声应用空间聚类算法（Density-Based spatial clustering of applications with noise， DBscan）以及层次聚类算法进行对比，验证本文算法的有效性。

2.4.1 基于虚假评论比例的造假度分析

正如许多研究中所提到的，Yelp、Amazon和Dianping等大型电子商务网站的数据集只能得到虚假/真实的评论标签，很难得到评论者个体的标签，更不用说水军群组了。在文献[6]中，至少发布过一条假（被电商网站过滤掉的）评论的评论者将被视为虚假评论者，没有假评论的评论者将被视为正常评论者。在文献[13]中，如果评论者至少有10%的评论被Dianping网站检测到是假的，则将其视为虚假评论者。在文献[14]中，一个评论者发布的评论中如果有超过50%的评论是假的，即被认为是垃圾邮件用户。为了获取水军群组的标签，文献[1-2，4]中只能采用手动标记的方法。而在文献[14]中通过评估聚类质量来评价得到的水军群组的好坏，这样做说服力明显不足。

结合上述文献对标签的处理，本文进行了有趣的分析，对于每个水军群组，本文计算了在这个群组中，虚假评论超过一定百分比的评论者所占的比例，统计情况如表5所示。

表5中的值指的是每个群组中至少发布了10%、20%、…虚假评论的评论者的比例。例如，在第一组中，有190个成员。在这一组中，100%（表5中的第一组）的评审员发布了超过10%的虚假评论，这意味着第一组的所有成员都发布了超过10%的虚假评论。注意到，第6组第8行出现的0，指的是群组6中没有成员的虚假评论比例超过45%，换言之，群组6中的成员发布的虚假评论比例均低于45%。特别地，第一组的成员中有69%的成员至少发布了50%的虚假评论。这种群组可疑度极大。

本文还计算了每个水军群组中成员虚假评论比例的平均值，结果如图5所示。由图5可以看出，不同群组间有极大的差异性，例如群组1、2、3、7和12中成员的平均虚假评论比例均高于40%，群组4、5、8和9为30%～40%，群组6、10、11为10%～30%。从图5中可以看出，不同群组的活跃度是不同的。因此本文将12個群组分为3类：群组1、2、3、7和12为高活跃度群组，群组4、5、8和9为一般活跃群组，群组6、10、11为低活跃度群组。

三类群组中成员的虚假评论比例如图6所示。从图6中可以看出，高活跃度群组，成员数较多，大部分成员的虚假评论比例均超过30%，危害极大;一般活跃群组，成员规模一般，虚假评论比例也较高，但远低于高活跃度群组;相对来说，低活跃度群组成员数较少，虚假评论比例也较低。综上所述，高活跃度群组因为人数多、每个人的造假比例高，对整个市场环境的危害也最大，因此应重点关注。

2.4.2 对比实验

为了验证本文算法的性能，本文选举经典的聚类算法KMeans算法、基于密度的聚类算法DBscan算法作为基准算法进行对比。在现有工作中，文献[3]利用层次聚类算法生成水军群组，所以，本文也与层次聚类算法作了比较。

本文利用KMeans算法、DBscan算法、层次聚类算法以及本文所提出的基于带权评论图的水军群组发现算法（WGSA）对检测出的top12个群组的4个特征进行评估。具体特征为一天最大评论数 （Maximum One day Review， MOR）[20]、极端评分比率 （EXtreme rating Ratio， EXR）[20]、评论时间间隔（Review Time Interval， RTI）[1，20]和评论者比率（Reviewer Ratio， RR）[4]。之所以选择这些特征作为评估指标，主要因为它们具有很好的通用性，在相应文献采用这4个特征对个体或群体作可疑度的评估和比较，表现较好。

1）一天最大评论数 （MOR）。

一个评论者在一天中发布大量评论是十分可疑的。MOR度量的是一个评论者一天发布评论的最大值。文献 [20]的研究结果显示一名水军一天的理论评论数至少为5，而正常评论者一般为2。对每个水军群组的成员计算其MOR值，然后取每个水军群组中成员MOR的平均值，得到如图7所示的结果。从图7可以看出，各算法检测出的水军群组平均一天最大评论数均超过6，有些群组甚至超过20，十分可疑，而本文算法与DBscan算法的表现相对更加突出。

2）极端评分比率 （EXR）。

水军往往发布极高或极低的评分来抬高或降低目标产品的评分。EXR度量的是一个评论者的评分是否极高或极低。由于评分范围为[1，5]，本文采用与文献[20]一样的处理方法，即将1、5作为极端评分，然后计算每个评论者极端评分的比例。计算得到的每个水军群组中成员的平均极端评分比率如图8所示。从图8可以看出，本文算法检测出的水军群组中成员的平均极端评分比率均大于0.6，而其他算法只有0.3左右，本文的算法表现较好。

3）评论时间间隔（RTI）。

水军通常在较短的时间内连续发布虚假评论，所以相邻评论间较短的时间间隔揭示了疑似的水军行为。文献[1， 20]指出，如果一个评论者的相邻评论时间间隔小于28天，则是可疑的。本文亦取小于28天的评论时间间隔为可疑时间间隔。RTI计算的是一个评论者的所有相邻评论时间间隔中可疑时间间隔的比例。每个群组中成员的平均RTI值如图9所示。从图9可以看出，本文算法检测出的水军群组的平均RTI值均在0.9左右，而其他算法的表现差一些，在0.7左右。

4）评论者比率（RR）。

如果目标产品主要由某水军群组的成员所评论，该水军群组就能完全控制该产品的舆论，危害极大。RR度量的是一个产品的评论者中身为某水军群组成员的比例。本文取一个群组中该比例的最大值作为RR的值。每个水军群组的最大RR值如图10所示。从图10可以看出，所有算法中每个水军群组的RR值均为1，这说明这些水军群组完全控制了部分产品的舆论走势，危害极大。

从上述分析可以得到，本文提出的算法WGSA，在MOR、RR指标上表现相对较好，在EXR、RTI指标上比其他算法有较大提升，总体来看，本文算法得到的水军群组可疑度更高，更有效。

3 结语

本文提出了基于带权评论图的水军群组发现算法（WRBA）。该算法首先构建带权评论者网络图，权重由一系列特征计算得到;然后设置阈值筛选可疑子图;最后利用社区发现算法生成水军群组。本文从虚假评论比例出发，发现检测到的水军群组成员的平均虚假评论比例均超过10%，表明了本文所提算法的有效性。而且本文研究发现，水军群组可以分成三类：高活跃度群组、一般活跃群组以及低活跃度群组。其中，高活跃度群组发布的评论多，虚假评论比例高，危害极大，应重点关注。为了验证本文算法的性能，本文选取了多个已有算法在4个群组虚假度特征（MOR、EXT、RTI和RR）上进行比较。实验结果表明，本文算法检测出的水军群组可疑度更高，算法性能表现更好。但本文只考虑了两种特征来构建带权评论者网络图，而且没有考虑时间因素，在今后的工作中，将考虑更多的特征，完善水军群组的检测方法。

参考文献 （References）

[1] MUKHERJEE A， LIU B， GLANCE N. Spotting fake reviewer groups in consumer reviews [C]// Proceedings of the 21st Annual Conference on World Wide Web. New York： ACM， 2012： 191-200.

[2] XU C， ZHANG J， CHANG K， et al. Uncovering collusive spammers in Chinese review website [C]// Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. New York： ACM， 2013： 979-988.

[3] YE J， AKOGLU L. Discovering opinion spammer groups by network footprints [C]// Proceedings of the 2015 Joint European Conference on Machine Learning and Knowledge Discovery in Databases， LNCS 9284. Cham： Springer， 2015： 267-282.

[4] WANG Z， HOU T， SONG D， et al. Detecting review spammer groups via bipartite graph projection [J]. The Computer Journal， 2016， 59（6）： 861-874.

[5] 張慧杰.基于多特征尺度空间模型的网络水军组织发现技术研究[D].杭州：浙江工商大学，2015：2-66.（ZHANG H J. Research technology on found of spammer organizations based on multi-feature scale space model [D]. Hangzhou： Zhejiang Gongshang University ， 2015：  2-66.）

[6] RAYANA S， AKOGLU L. Collective opinion spam detection： bridging review networks and metadata [C]// Proceedings of the 2015 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2015： 985-994.

[7] RAYANA S， AKOGLU L. Collective opinion spam detection using active inference [C]// Proceedings of the 2016 16th SIAM International Conference on Data Mining. Philadelphia， PA： SIAM， 2016： 630-638.

[8] JINDAL N， LIU B. Opinion spam and analysis [C]// Proceedings of the 2008 International Conference on Web Search & Data Mining. New York： ACM， 2008： 219-230.

[9] LIM E， NGUYEN V， JINDAL N， et al. Detecting product review spammers using rating behaviors [C]// Proceedings of the 19th ACM Conference on Information and Knowledge Management. New York： ACM， 2010： 939-948.

[10] OTT M， CHOI Y， CARDIE C， et al. Finding deceptive opinion spam by any stretch of the imagination [C]// Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics： Human Language Technologies. Stroudsburg， PA： Association for Computational Linguistics， 2011： 309-319.

[11] YU P S， LIU B， XIE S， et al. Review graph based online store review spammer detection [C]// Proceedings of the 11th IEEE International Conference on Data Mining. Piscataway， NJ： IEEE， 2011： 1242-1247.

[12] AKOGLU L， CHANDY R， FALOUTSOS C. Opinion fraud detection in online reviews by network effects [C]// Proceedings of the 2013 7th International Conference on Weblogs and Social Media. Menlo Park， CA： AAAI， 2013： 2-11.

[13] LI H， CHEN Z， MUKHERJEE A， et al. Analyzing and detecting opinion spam on a large-scale dataset via temporal and spatial patterns [C]// Proceedings of the 9th International Conference on Web and Social Media. Menlo Park， CA： AAAI， 2015： 634-637.

[14] LI H Y， FEI G， SHAO W X， et al. Bimodal distribution and co-bursting in review spam detection [C]// Proceedings of the 26th International Conference on World Wide Web. Republic and Canton of Geneva， Switzerland： International World Wide Web Conferences Steering Committee， 2017： 1063-1072.

[15] AGRAWAL R， SRIKANT R. Fast algorithms for mining association rules in large databases [C]// Proceedings of the 20th International Conference on Very Large Data Bases. San Francisco， CA： Morgan Kaufmann Publishers Inc.， 1994： 487-499.

[16] BLONDEL V D， GUILLAUME J， LAMBIOTTE R， et al. Fast unfolding of communities in large networks [J]. Journal of Statistical Mechanics Theory & Experiment， 2008（10）： 155-168.

[17] NEWMAN M E J. The structure and function of complex networks [J]. SIAM Review， 2003， 45（2）： 167-256.

[18] WATTS D J， STROGATZ S H. Collective dynamics of ‘small-world networks [J]. Nature， 1998（393）： 440-442.

[19] FRONCZAK A， FRONCZAK P， HOYST J A. Average path length in random networks [J]. Physical Review E， 2004， 70（5）： 056110.

[20] MUKHERJEE A， KUMAR A， LIU B， et al. Spotting opinion spammers using behavioral footprints [C]// Proceedings of the 2013 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2013： 632-640.