0 概述

随着电子商务与Web 2.0的快速发展, 在线评论已成为消费者在购买产品或服务时的重要参考依据^[1]。与此同时, 大量水军通过发布虚假评论影响用户的购买决策, 从而攫取不正当的商业利益^[2]。虽然已有研究试图通过异常的评论特征、行为特征等对水军进行检测^[3-5], 但是, 近年来越来越多的水军通过组成群组的方式, 共同发布针对目标商品的虚假评论。在这种有组织的行动下, 水军个体能够以更加轻微的异常行为隐藏自己的身份, 且由于群组中包含大量水军, 往往能够形成言论优势, 进而完全控制关于目标商品的评价^[6]。水军群组对社会产生了巨大危害, 其检测问题成为广受关注的研究热点。

主流水军群组检测方法一般包含2个阶段^[7]:提取若干候选群组(提取阶段), 从候选群组中识别出水军群组(识别阶段)。现有研究工作主要聚焦于检测方法准确率的提升^[8-9], 较少关注检测效率等性能问题。然而, 随着电子商务平台中用户和商品规模的急剧扩张, 检测方法的效率与扩展性成为限制其广泛应用的瓶颈。水军群组识别阶段主要使用分类、排序等机器学习算法, 已有研究多数致力于解决这些算法的效率问题^[10-11], 且目前很多分布式框架中已集成了成熟的机器学习工具包(如Hadoop中的Mahout、Spark中的MLlib等)。另一方面, 识别算法的运行速度主要受待识别样本量的影响, 如果提取阶段产生的候选群组过多, 且其中包含大量的非水军群组, 将会增加识别阶段的压力, 导致算法整体检测性能降低。

综上, 精准且高效的候选群组提取是提升水军群组检测算法整体性能的关键。为此, 本文提出一种基于余弦模式挖掘的群组提取算法, 以精准提取候选水军群组。在此基础上, 利用Spark框架设计基于分布式余弦模式挖掘的群组提取算法, 以进一步提升群组提取的效率、扩展性以及算法的整体性能。

1 相关工作

进行水军群组检测的第1步是从所有用户中提取群组(提取阶段)。在电子商务水军检测领域, 群组即一组多次针对不同目标商品共同发布评论的用户。文献[7]提出一种基于频繁模式挖掘的群组提取方法, 该方法将共同评论某一商品的用户视为关联规则中的一条事务, 进而将群组提取转化为从多个事务中挖掘多次出现的用户组合, 相当于从事务集中挖掘频繁模式。由于该群组提取方法简单易行, 因此被很多后续的水军群组检测研究所沿用^[8-9], 成为群组提取的主流方法。

利用频繁模式挖掘提取出的群组中既包含水军群组, 也包含由于某些特殊原因偶然形成的群组(如拥有共同的兴趣爱好、同时购买流行商品等)。因此, 此时提取出的群组仅仅是水军群组的候选, 还需进一步构建群组特征, 利用分类、排序等机器学习方法从中识别出真正的水军群组(识别阶段)。目前, 水军群组识别工作主要基于以下3个思路:

1) 构建群组特征与分类器, 将候选群组分类为水军群组和非水军群组, 如文献[8]基于群组评论相似性、群组规模等特征, 利用k近邻分类器对候选群组进行分类。

2) 利用群组特征建立关联关系网络, 然后通过图排序算法对候选群组的受怀疑程度或恶意性进行排序, 再将可疑度或恶意性高于预设阈值的群组判定为水军群组。如文献[7]建立群组-用户、群组-商品以及用户-商品3种关联关系并融合成关系网络, 然后利用类似PageRank的排序算法计算群组恶意性, 从而获得水军群组。

3) 提取群组特征或群组目标商品的特征, 将每种特征转化为分值并按一定的方式进行加权, 根据最终的分值识别水军群组。如文献[9]利用主成分分析对有关群组恶意程度的主要特征值进行加权, 根据最终加权分值判定水军群组。

在群组提取阶段, 如何高效地从大规模用户中提取群组, 且提取出的群组足够精确, 即尽可能多地排除非水军群组, 减轻识别阶段的计算量, 对于提升水军群组检测的整体性能至关重要, 本文将围绕这一问题展开研究。需要说明的是, 由于识别阶段所采用的多种机器学习算法已有较成熟的分布式工具包, 这一阶段的算法性能分析暂不纳入本文的研究范围。

2 基于余弦模式挖掘的群组提取

利用频繁模式挖掘提取群组时需设置支持度参数, 即定义构成群组的用户需同时出现的次数。为避免遗漏水军群组, 通常会设置较低的支持度, 由此带来的负面影响是提取出的群组过多, 可能包含大量的非水军群组, 为后续水军群组的识别带来困难。造成这一现象的原因是频繁模式挖掘仅考虑用户间的共现次数, 忽略了对用户间关系的度量。从内部看, 群组成员间不仅有共同评论的商品, 各成员也有各自独立评论的商品, 即非共同评论商品。对一个群组而言, 成员共同评论的商品与被群组成员评论过的商品总和间的比值衡量了群组成员间的紧密程度, 本文用耦合度表示这一概念。相关研究结果表明, 耦合度较高的群组(下文称为紧耦合群组)属于水军群组的概率更高^[12]。如图 1所示, 水军群组成员以集体行动为主, 共同评论的商品比例较高, 而由于兴趣聚合而成的群组, 成员往往还有各自购买/评论的需求和偏好, 独立评论的商品比例较高。将群组的耦合度纳入群组提取过程中进行考虑, 将更具针对性并能够过滤掉大量偶然形成的群组。本文从紧耦合群组的定义开始, 利用余弦模式对其进行建模, 设计基于余弦模式挖掘的紧耦合群组提取算法。

2.1 紧耦合群组

水军群组由一群多次共同评论特定商品或商品集合的用户所组成。令U={u₁, u₂, …, u_n}表示一组用户的集合, P_l表示用户u_l所评论的商品集合。若U中各用户所评论的商品集合完全相同, 即P₁=P₂=…=P_n, 则称这样的用户集合为完全耦合群组, 并有:

$ \frac{{\left| {\bigcap\limits_{l = 1}^n {{P_l}} } \right|}}{{\left| {{P_1}} \right|}} = \frac{{\left| {\bigcap\limits_{l = 1}^n {{P_l}} } \right|}}{{\left| {{P_2}} \right|}} = \cdots = \frac{{\left| {\bigcap\limits_{l = 1}^n {{P_l}} } \right|}}{{\left| {{P_n}} \right|}} $

(1)

其中, |·|表示集合中元素的数量。定义用户u_l的共同评论率$ R_{l}=\left|\bigcap\limits_{l=1}^{n} P_{l}\right| /\left|P_{l}\right|$, 其表示群组中所有用户共同评论的商品数量与用户u_l所评论的商品数量间的比值。式(1)表明完全耦合群组中用户的共同评论率都为1。根据这一思路, 可以用共同评论率作为水军群组的衡量指标。由于在实际情况中, 完全耦合群组出现的概率极低, 因此需对共同评论率为1这一要求进行必要的松弛。在此之前, 先给出平均共同评论率这一概念的定义。

定义1 (平均共同评论率)给定一个用户集合U(|U|≥2), 其平均共同评论率AR定义为集合中所有用户的共同评论率的几何平均数, 即:

$ AR(U) = \sqrt[{|U|}]{{\prod\limits_{{u_l} \in U} {{R_l}} }} $

(2)

由式(2)可以看出, 平均共同评论率的取值在0~1之间, 其值越高, 说明用户间共同评论的商品所占比例越大, 用户间的耦合度也越高。因此, 紧耦合群组可视为一个平均共同评论率AR≥τ_AR的用户集合, 其中, τ_AR表示预设的阈值。

此外, 为过滤掉部分共同评论的商品数量过少的用户集合, 还需对共同评论商品的最小数量进行限制。为适应不同规模的商品集合, 本文用共同评论商品占商品总量的比例描述这一限制, 即要求用户集合U(|U|≥2)满足如下条件:

$ M S(U)=\frac{\left|P_{1} \cap P_{2} \cap \cdots \cap P_{|U|}\right|}{m} \geqslant \tau_{M S} $

(3)

其中, m表示商品总量, τ_MS为预设的阈值。由此, 可得到紧耦合群组的定义。

定义2 (紧耦合群组)当且仅当给定阈值τ_AR、τ_MS∈[0, 1]满足AR(U)≥τ_AR且MS(U)≥τ_MS时, 用户集合U为紧耦合群组。

特别地, 当τ_AR=1时紧耦合群组将转化为完全耦合群组。所有群组成员的评论商品完全相同, 这表明紧耦合群组是完全耦合群组的一种松弛版本, 两者的区别随着τ_AR值的增大而减小。

2.2 紧耦合群组的余弦模式建模

在对紧耦合群组进行建模前, 先给出余弦模式的定义。余弦模式是频繁模式的变种, 除采用支持度外, 还引入余弦相似度作为模式的兴趣度度量指标^[13]。假设I={i₁, i₂, …, i_k}(k≥2)为事务集D中的一个k项集, I的余弦相似度定义为:

$ Cos (I) = \frac{{Supp(I)}}{{\sqrt[k]{{\prod\limits_{p = 1}^k {Supp} \left( {\left\{ {{i_p}} \right\}} \right)}}}} $

(4)

其中, Supp(·)表示支持度, 其计算公式为:

$ {Supp}(I)=\frac{S C(I)}{|D|} $

(5)

其中, $ S C(I)=|\{T | I \in T, T \in D\}|$表示I的支持度计数, T为事务集D中包含项集I的事务。根据余弦相似度, 可给出余弦模式的定义。

定义3 (余弦模式)分别给定支持度阈值τ_s∈[0, 1]和余弦相似度阈值τ_c∈[0, 1], 如果项集I满足Supp(I)≥τ_s且Cos(I)≥τ_c, 则I为τ_s和τ_c约束下的余弦模式。

在定义3中, 如果将τ_c设置为0, 则余弦模式退化为频繁模式, 此时支持度成为唯一的兴趣度度量指标。如果将评论某一特定商品的用户集合视为一条事务, 那么每个商品将产生一条事务并共同组成事务集D, 此时可得到如下命题。

命题1  给定阈值τ_AR和τ_MS, 提取紧耦合群组等价于从事务集中根据阈值τ_c =τ_AR和τ_s=τ_MS挖掘余弦模式。

证明  给定一个用户集合U, 如果q为U中所有用户共同评论的某一商品, 即q∈P₁∩P₂∩…∩P_|U|, 则可认为U包含在商品q对应的事务t_q∈D中, 因此, 可得到:

$ \begin{aligned} | P_{1} & \cap P_{2} \cap \cdots \cap P_{|U|} |=\\ &\left|\left\{t_{q} | U \subseteq t_{q}, 1 \leqslant q \leqslant m\right\}\right|=S C(U) \end{aligned} $

其中, SC(U)为U在事务集D中的支持度计数。则可得到:

$ M S(U)=\frac{\left|P_{1} \cap P_{2} \cap \cdots \cap P_{|u|}\right|}{m}={Supp}(U) $

(6)

进一步将共同评论率R_l的定义代入式(2), 易得:

$ \begin{array}{l} AR(U) = \sqrt[{|U|}]{{\left| {\bigcap\limits_{l = 1}^{|U|} {{P_l}} } \right|{\raise0.7ex\hbox{${|U|}$} \!\mathord{\left/ {\vphantom {{|U|} {\prod\limits_{{u_l} \in U} {{P_l}} }}}\right.} \!\lower0.7ex\hbox{${\prod\limits_{{u_l} \in U} {{P_l}} }$}}}} = \\ \left| {{P_1} \cap {P_2} \cap \cdots \cap {P_{|U|}}} \right|{/^{|U|}}\sqrt {\prod\limits_{{u_l} \in U} {{P_l}} } = \\ SC(U){/^{|U|}}\sqrt {\prod\limits_{{u_l} \in U} S C\left( {\left\{ {{u_l}} \right\}} \right)} = \\ Supp(U){/^{|U|}}\sqrt {\prod\limits_{l = 1{u_l} \in U}^{U|} {Supp} \left( {\left\{ {{u_l}} \right\}} \right)} = \\ Cos (U) \end{array} $

(7)

由式(6)、式(7)以及定义2、定义3可得, 提取紧耦合群组等价于挖掘余弦模式, 证毕。

2.3 候选水军群组提取

在紧耦合群组建模为余弦模式后, 可采用余弦模式挖掘算法提取紧耦合群组。为易于进行后续的分布式扩展, 本文选用文献[13]提出的余弦模式挖掘算法CIP-Growth进行紧耦合群组提取。该算法是经典频繁模式挖掘算法FP-Growth的扩展, 其基本流程与FP-Growth类似, 如下:

1) 扫描事务集并计算每个项的支持度计数, 对其降序排列生成头部表Head Table。

2) 再次扫描事务集构建FP树, 将其作为基础数据结构。

3) 以递归的方式生成条件FP树, 从中搜索余弦模式。

基于CIP-Growth的群组提取算法伪代码如下, 具体的设计思想与细节可参考文献[13]。

算法1  基于GIP-Growth的紧耦合群组提取算法

输入  条件FP树Tree, 初始化由事务集D构建; Tree的前缀模式S, 初始化为空; 支持度阈值τ_s; 余弦相似度阈值τ_c

输出  余弦模式集合G, 即紧耦合群组集合, 初始化为空

1.CIP-Growth(Tree, S, G, τ_s, τ_c)

2.FOR Tree的头部表中的项i_k; //按降序遍历

3.生成候选余弦模式S′=S∪{i_k};

4.IF Cos(S′)≥τ_c THEN

5.G=G∪S′;

6.按τ_s创建S′的条件FP树Tree_S′;

7.IF Tree_S′≠ $ \emptyset $ THEN

8.CIP-Growth(Tree, S, G, τ_s, τ_c);

9.返回G.//G中包含所有的余弦模式(紧耦合群组)

鉴于余弦模式与紧耦合群组间的等价关系, 挖掘出事务集中的所有余弦模式相当于提取出所有的紧耦合群组。

3 候选群组提取算法的分布式实现

真实的电子商务平台中包含大量的商品与用户, 由此建立的事务集规模巨大。为应对这一挑战, 本文将对基于余弦模式挖掘的提取算法进行分布式扩展, 以提升其性能。在类FP-Growth算法中, 进行分布式设计的核心是利用组投影技术^[14], 通过将头部表划分成若干组, 根据每组包含的项集, 在事务数据集上进行投影, 从而将事务集分割为互不相交的数据子集, 然后对每个数据子集分别构建FP树并进行模式挖掘, 最终汇总得到挖掘结果。本文利用组投影技术对事务集进行分割, 然后基于内存计算框架Spark(http://spark.apache.org/)设计分布式候选群组提取算法。

3.1 组投影技术

组投影技术是文献[14]为设计并行FP-Growth算法而提出的一种事务集转换切割方法, 其形式化定义为:

定义4 (组投影)假设按降序排列的头部表FList中的各项自上而下被分为K个不相交的子集, 即FList = β₁∪β₂∪…∪β_K, 其中, $\beta_{k}=\left\{i_{1}^{k}, i_{2}^{k}, \cdots, i_{r}^{k}\right\} $由FList中r个连续项组成, 则事务集D在第k个组β_k上的组投影数据集为$ {D_k} = \left\{ {{T_p} \cap \left( {\bigcup\limits_{j = 1}^k {{\beta _j}} } \right)|{T_p} \cap {\beta _k} \ne } \right.\emptyset , {T_p} \in D\} $。

为便于理解组投影的含义, 以表 1所示事务集为例, 其按各项支持度降序排列的头部表为{E(7), D(5), C(5), B(4), A(3)}(括号中的数据代表相应项的支持度计数)。假设FList被分割为3个组{D, E}、{B, C}、{A}, 则在这种分割下通过组投影技术生成的数据集如表 2所示。以组{B, C}投影得到的数据为例, 当删除FList中位于项B之后的A后, 提取所有包含B或C的事务, 得到表 2中组{B, C}所对应的包含7个事务的投影数据集, 其中, 括号中的数字表示对应事务在数据集中的数量。

3.2 基于Spark框架的分布式候选水军群组提取

在Spark框架下, 本文设计的基于余弦模式的分布式水军群组提取算法可封装为2个Map-Reduce过程, 如下:

1) 横向切割事务集D并加载到Spark的弹性分布式数据集(Resilient Distributed Datasets, RDD)中, 触发第1次Map-Reduce过程。在Map阶段计算每个RDD上各项的支持度计数, 然后以项为键、对应的支持度计数为值, 在Reduce阶段汇总计算项在整个事务集中的支持度计数, 并排序生成FList, 这一过程类似于经典的Word Count算法, 在此不再赘述。

2) 将FList分割为K个子集, 广播到各个RDD上, 触发第2次Map-Reduce过程。在Map阶段根据FList的分割对RDD中的事务进行组投影, 在Reduce阶段, 以组为键, 汇总投影结果生成K个新的RDD, 每个RDD中保存对应组的投影数据。最后, 在新产生的RDD中执行第2.3节的紧耦合群组提取算法, 汇总得到候选群组。

基于Spark框架的分布式群组提取算法结构如图 2所示。

在得到候选群组后, 可选用已有的水军群组识别方法从中识别水军群组。这些方法大多基于分类、排序等机器学习算法, 如SVM、PageRank等, 其分布式版本已在Spark的机器学习库MLlib中实现, 可与本文分布式水军群组提取算法进行有效结合。

4 实验结果与分析

本节利用真实数据集从性能和准确性2个方面对分布式水军群组检测算法进行验证和分析。

4.1 实验设置

实验具体设置如下:

1) 数据集:实验数据爬取自亚马逊中国网站(https://www.amazon.cn/), 共收集了自2009年9月—2017年12月间834 547个用户针对4 837 386个商品发布的190 435 346条评论数据。从中移除冷门商品和用户, 仅保留发布3次以上评论的用户和被评论10次以上的商品以及对应的评论数据, 建立如表 3所示的实验数据集。

2) 实验环境:本文使用Spark集群运行分布式水军群组检测算法, 集群共包含8台服务器, 使用InfiniBand万兆网络互联, 每台服务器配置为英特尔E5-2650v2 CPU(4核, 主频2.6 GHz), 128 GB内存, 240 GB SSD硬盘以及600 GB SAS硬盘, 操作系统为64位RedHat Linux 7.0, Spark版本为1.6.2, 实验代码采用Java语言编写。

4.2 性能验证

由于水军群组识别阶段的算法未纳入本文研究范围, 因此本次实验主要关注群组提取阶段的性能。本文基于余弦模式挖掘的提取算法能够提取出紧耦合群组, 较频繁模式挖掘方法能够大幅降低候选群组的数量, 有利于提升后续识别的效率。设置余弦阈值τ_c=0.2, 支持度τ_s在0.01%~0.05%间变化, 图 3所示为余弦模式挖掘和频繁模式挖掘所提取出的群组数量对比。从图 3可以看出, 余弦模式挖掘提取出的候选群组数量远少于频繁模式挖掘, 且支持度越小, 两者的差异越大。由于支持度越小, 越不容易遗漏群组, 因此较小支持度下两者的显著性差异更能凸显余弦模式挖掘对于提升检测效率的优势。

从运行时间方面比较分布式版本和单机版本的余弦模式挖掘算法的性能差异。设置余弦阈值τ_c=0.2, 支持度τ_s=0.01%, FList的分割数K从4变化到20, 经测算单机版算法的运行时间为1 430.27 s, 分布式版本算法的运行时间如图 4所示。从图 4可以看出, 随着并行度(即K的数值)的增大, 提取群组所消耗的时间持续减少, 且分布式版本的运行时间远小于单机版本, 当K=20时, 分布式版本算法比单机版本算法所消耗的时间减少90%以上。该实验结果表明, 分布式余弦模式挖掘算法能够有效提升群组提取的效率, 最终提升水军群组检测的整体性能。

4.3 准确性验证

为验证本文群组提取算法的检测准确性, 选用文献[7]提出的GSRank算法从候选群组中识别水军群组。GSRank算法利用群组、用户及商品特征建立群组-用户、群组-商品以及用户-商品3种关联关系并融合成关系网络, 然后利用类似PageRank的算法计算群组恶意度并排序, 选择排序列表中恶意度位于前列的群组, 将其判定为水军群组。

由于实验所使用的数据集中并未给出用户或群组是否为水军的标记, 即缺乏GroundTruth。因此, 本文采用文献[15]提出的间接验证思路对水军群组识别的准确性进行验证。由于GSRank算法会给出群组的恶意度, 在按恶意度排序生成的列表中(假设按降序排列), 如果检测算法是准确的, 那么排在列表前列的群组和排在末尾的群组间必然具有较高的区分度, 即前列群组的恶意度很高, 末尾群组的恶意度很低, 截取首尾部分群组组成新的测试集, 使用分类器对测试集进行分类也将取得较好的分类效果。反之, 如果检测算法准确性较低, 则列表首尾部分群组的区分度较低, 分类器将难以取得好的分类效果。在进行间接验证时, 本文设定余弦阈值τ_c=0.2, 支持度τ_s=0.01%, 提取候选群组并采用GSRank算法进行排序, 然后分别截取列表首尾5%、10%、15%的群组建立测试集, 再使用SVM和C4.5决策树对测试集进行分类, 分类效果采用准确率(P)、召回率(R)和综合评价指标(F)进行描述, 实验结果如表 4所示。由表 4可以看出, 本文余弦模式提取算法与频繁模式提取算法在水军检测中所取得的准确率相差无几, 说明本文算法在提升检测效率的同时, 也能保证准确率。由表 4还可以看出, 在排序列表首尾截取的群组越少, 群组间的区分度越高, 分类器的分类效果越好。

使用余弦模式挖掘算法提取出的群组数量远少于频繁模式挖掘, 因此, 余弦模式是否会造成水军群组遗漏值得关注。本文分别使用余弦模式和频繁模式提取群组, 然后用GSRank排序得到2个列表并按恶意度降序排列。由于水军群组排在列表的前列, 本文分别截取2个列表的前Y个群组, 考查两者间的重合率, 实验结果如图 5所示。由图 5可以看出, 2个列表中排序靠前的群组间重合度很高, 当余弦阈值τ_c=0.2、截取的群组位于列表前2 000时, 2个列表中超过90%的群组是相同的。因此, 相对频繁模式挖掘, 余弦模式挖掘所排除的群组主要是非水军群组, 几乎没有造成水军群组遗漏。

5 案例研究

为进一步阐述本文水军群组检测算法的有效性, 本节展现2个由该算法从实验数据集中检测出的水军群组, 并分析其异常行为。本文实验数据取自2009年9月—2013年12月, 由于亚马逊网站本身也会开展水军检测工作, 案例中展现的水军ID可能已被网站删除, 但这也从侧面说明了本文算法的有效性。2个水军群组信息如下:

1) 水军群组1共包含8名成员, 在2010年5月21日—25日的5天里, 这些用户一共评论了15个商品, 所有商品均给予5星评价。图 6所示为用户评论商品的时间分布情况, 可以看出, 这些用户多次在同一天共同评论同一商品, 这种行为有异于偶然形成的普通群组。普通群组的成员虽然有共同评论的商品, 但评论时间通常是不同的。此外, 通过在亚马逊中国网站上搜索群组成员的ID, 发现很多ID或相关评论已被删除, 这说明亚马逊的检测算法与本文得出了一致的结论, 上述用户组成的群组为水军群组。

2) 水军群组2包含5名成员, 并于2010年9月30日共同评论了3件商品, 其中, 3名成员还分别额外评论了2件商品。图 7所示为该群组的目标商品及评论行为。首先, 该群组所评论的商品集中属于“书中缘”品牌的图书, 但图书类别各不相同, 因此, 其并非由兴趣形成的群组; 其次, 3名成员发布了重复评论, 这是水军发表评论的典型特征; 最后, 所有成员均给出了4星或5星的高评分, 其目的在于提升“书中缘”品牌图书的排名, 即该群组属于品牌营销水军。

6 结束语

本文提出紧耦合群组的概念并用余弦模式进行建模, 基于余弦模式挖掘精准提取候选群组, 在此基础上, 运用组投影和Spark框架设计一种分布式群组提取算法, 以提升算法的运行效率与扩展性。下一步将通过合理划分头部表, 使组投影技术得到更加均衡的数据切割, 以提高分布式算法的运行效率。