基于马尔可夫随机场的评论欺诈在线检测方法

陈 前，王 琢

(沈阳理工大学 信息科学与工程学院，沈阳 110159)

在线评论对候选消费者有着强烈的导向性。高分的评论往往更容易吸引消费者前去购买该商品；反而低分的评论容易诱导消费者放弃购买。商家利用这个规则张贴大量虚假评论来蒙蔽消费者[1]。

虚假评论问题是由Bing Liu研究团队，在2008年首次提出在线垃圾评论检测问题[2]中所引出的，而后Ott等强调标准数据集的重要性[3]，通过Amazon旗下的“Amazon Mechanical Turk”(机械土耳其人)网站招聘来一些人，为指定酒店书写虚假评论从而获得虚假的评论内容，研究人员让受试者完成任务，并支付少量酬金，并从TripAdvisor(猫途鹰在线旅行社区)上选取真实的评论内容，从而获得了对评论的虚假性有标注的标准数据集。该方法利用监督模型对虚假评论进行检测，得到了很高的准确率。

在现实世界中评论是复杂多样的，因此有标注的虚假评论数据集的获取极其困难，这同时也从根本上加大了有监督算法的难度。Akoglu等提出通过网络效应在网络评论中的评论欺诈检测[4]——FraudEagle框架，该方法将用户、产品视为顶点，用户和产品之间生成的评论为边，以此建立二部图；然后以此二部图为基础，利用概率图模型中的马尔可夫随机场建模，并使用经典的近似推断算法之一的 Loopy Belief Propagation(循环置信传播，简称LBP)来求解每个顶点的边缘概率。依照边缘概率值来表示该评论人作弊的可疑度。

以上的框架都是利用离线大规模数据进行离线虚假评论挖掘，因此以往的离线算法都无法迅速捕捉到虚假评论，这样就会造成即使离线框架已经检测到虚假评论(评论人)，而所造成的危害已经产生，其算法的应用价值变低。为应对这个问题在线检测虚假评论框架应运而生。Ye等首先提出基于多元指示信号进行实时虚假评论检测[5]，通过每个单位时间窗的多元指示信号的变化，来得到当前时间窗内产品的可疑度。吕海等使用时间窗口在评论数据流上滑动构造评论人-产品二部图，并利用SCAN技术挖掘虚假评论人群组[6]。Xu C等提出利用矩阵分解算法对评论人、产品形成的评分矩阵进行因子化，最后得到评论人的可疑度[7]。

本文所提出的FRAUDMRF是以在线的方式，当新评论产生时利用近期相关数据，构建轻量型二部图(评论人-产品)，利用马尔科夫随机场模型迅速预测出近期评论(评论人)的可疑度，并在两个有标注的评论数据集YelpNYC、YelpZip上进行实验，以作弊度排序的方式来检验模型的性能。

1 模型的建立

1.1 FRAUDMRF框架介绍

FRAUDMRF是一个在线运行框架，假设评论v=(uid,pid,r,d)、v.uid、v.pid、v.r、v.d分别表示评论v的评论人、产品、评分值、评分日期。即每当一条新的评论vt到来时，更新模型并对近期评论(评论人)进行预测，迅速得出其作弊度。

设常量T用来控制是否为近期评论的阈值。当评论vt到达，寻vt.uid近期评论的其他产品集合Pt={v.pid|vt.d-v.d≤T∩vt.uid=v.uid}，以及近期评论过vt.pid的其他评论人集合Ut={v.uid|vt.d-v.d≤T∩vt.pid=v.pid}。边集合E={e(v.uid,v.pid) |ifv.uid=vt.uidorv.pid=vt.pid,v.uid∈Ut,v.pid∈Pt}。由此得到二部图Gt(V,E)，如图1所示，其中V=Ut∪Pt。

图1 t时刻评论人-产品二部图

得到图Gt，用结对马尔可夫随机场[8]进行建模，将图Gt中的顶点集合中的每个顶点假设为不可观测的随机变量Yi。

每个随机变量Yi可以从其各自的有限个标签域中取得适当的标签值，如评论人的标签域为Lu={真实，虚假}，产品为Lp={好的，坏的}。并将随机变量Yi所分配的标签值设为yi。设Ψ表示一个团势集合，由以下两种类型组成。

(1)每个随机变量Yi都有与之相对应的先验知识，维度与随机变量Yi所对应的标签域相同，以概率的形式表现，如：Y2是评论人顶点，所对应的先验为={0.2,0.8}，表示该评论人从已知条件估计是真实的概率为0.2，是虚假的概率为0.8。

依据以上条件，建立如下联合概率表达式。

(1)

式中：Z为归一化常量；y为所有随机变量所分配的标签值的集合。要求得argmaxp(y)的解y，可知这是一个NP-Hard问题，所以利用近似推断算法“循环置信传播”(LBP)来求解该问题。

1.2 先验知识

利用良好的先验知识提升模型性能。Rayana等[9]针对虚假评论检测问题提出SpEagle框架，该框架利用马尔科夫随机场建模，并融入大量的先验知识取得了很好的效果。尤其是融入先验知识后的模型比默认使用固定先验知识的模型的性能得到了整体的提升。本文将其离线特征改造成可在线计算的特征，在FRAUDMRF中，并设计在线特征融合公式，见公式(2)所示。

(2)

式中：S(g)表示顶点g的评论人为作弊(产品为坏的)先验值，顶点g的先验为{1-S(g),S(g)}；fi(g)表示顶点g的第i个特征的特征值；F表示顶点g的特征总个数；σ∈(0,1]表示该先验的可信度,并将得到的先验保存到集合Prior={(vi.uid,S(g)),(vi.pid,S(g)),…}中。

1.3 作弊先验可视化分析

本文将两个数据集的计算完成在线作弊先验，按照标签将真实评论和虚假评论分别统计其各自的累计分布函数(CumulativeDistributionFunction,CDF)，并以直方图显示两种先验在两个数据集中对真实评论和虚假评论的区分度，图2、图3所示。图2、图3中参数δ=1。

图2 YelpNYC数据集

图3 YelpZip数据集

1.4 兼容性矩阵

1.4.1虚假评论人的勾结相似性

在虚假评论检测问题中，群体爆发性作弊评论所造成的危害是最为严重的。本文通过观察数据，针对群爆发性作弊评论行为，总结出以下几点。

(1)评论人会在短时间内集中针对某个或某几个产品发布大量虚假评论。

(2)评论人在这期间内会对该产品共同评论高分，吹捧商家产品质量；或共同评论低分，贬低商家商品质量。

(3)评论人数在此期间内相对于其他时间较为密集。

根据以上几点信息，本文提出评论之间的勾结相似性来捕获群体爆发性虚假评论行为，其勾结相似性公式见式(3)所示。

(3)

设Δt=vt.d-v.d，服从均值为0，方差为σ1(默认为T)的正态分布；设Δr=|vt.r-v.r|，服从均值为0，方差为σ2(默认为3)的正态分布；φ(g)表示累积分布函数(CDF)的标准正态分布，乘2是为了将其数值范围放大到0～0.5之间。

1.4.2兼容性矩阵的定义

兼容性矩阵是以条件概率分布表的形式来表示，如表1、表2所示。

表1 类型s+边的兼容性矩阵

表2 类型s-边的兼容性矩阵

其中α为固定参数(接近于0的正小数)，主要影响当前评论人vt.uid和该人近期评论的相关产品vi.pid之间的网络效应；β主要影响近期评论产品vt.pid的评论人vj.uid之间的网络效应，β越小表示近期评论成为虚假评论的可能性越小，通常设置一个接近于1的小数。

1.5 模型的推断过程

LBP是一种基于迭代消息传递的方法，当消息传递趋于稳定时停止迭代，利用当前稳定的消息计算出顶点的置信度bi(yi)(类似于边缘概率，表示顶点yi通过算法估计在其标签域上可能为各个标签值的概率)[10]。其消息传递公式如下。

(4)

式中：mi→j(yj)表示由顶点Yi向顶Yj的标签yj传递一次消息；z1表示归一化常量；Ni表示顶点Yi邻居，如果Yi为评论人顶点，则Ni表示评论人i近期评论的所有产品，反之Yi表示产品顶点,则Ni表示近期评论过该产品i的所有评论人；yj表示不包含yj；mk→i(yj)表示除yj外yi的邻居向yi传递的消息。计算置信度bi(yi)的公式如下。

(5)

式中z2为归一化常量。关于评论的可疑度计算，本文利用该评论的评论人顶点Yi和产品顶点Yj的联合概率p(yi,yj)“虚假，坏的”来表示，其计算公式如下(z3为归一化常量)。

(6)

2 算法详细过程

算法的详细过程本文以伪代码的形式展现，如表3所示。

表3 算法详细过程

当一条新的评论到达时，FraudMRF算法的时间复杂度为O(k+k×iters)，其中iters是LBP算法的最大迭代次数。计算新到达的评论的评论人和产品的实时先验的时间复杂度为O(k2),其中k=|E|。

3 实验结果评估

3.1 参数设置和在线特征选取

数据集的介绍及其参数设置如表4、表5所示。

表4 Yelp数据集统计信息

表5 各个数据集设置

表5中δu、δp分别为公式(2)中评论人先验和产品先验的可信度参数。

3.2 实验结果分析

本文在两个数据集(YelpNYC，YelpZip)上设置如上参数运行FRAUDMRF模型。将该评论(评论人)在其延后T天数内得到的最大的可疑度作为该评论(评论人)的最终可疑度。将FRAUDMRF的评论最终可疑度结果以排名的方式与评论人(产品)实时作弊先验和FRAUDEAGLE算法的评论可疑度结果进行比较；用相同的方式将FRAUDMRF的评论人的最终可疑度结果与FRAUDEAGLE算法的评论人可疑度结果进行比较。在样本分布很不平衡的数据集中以排名的方式检验结果，能够更好的反应模型的性能。在Xu C等提出的“用户评论中的在线信誉欺诈活动的检测方法”中，指出YelpZip数据集中符合团体活动欺诈评论人仅474人。所以实验展示按作弊度排序前1000个评论人和评论的表现，并以归一化折损累计增益NDCG (衡量排序搜索算法常用指标)作为评价指标来展示模型的性能，如图4、图5所示。图4中FraudEagle(V1)、FraudMRF(V2)表示FRAUDEAGLE算法和FRAUDMRF算法的评论结果。图5中FraudEagle(R1)、FraudMRF(R2)表示FRAUDEAGLE算法和FRAUDMRF算法的评论人结果。

由图4可以看出，FRAUDMRF的评论结果的NDCG指标在前面的排名遥遥领先实时先验的评论排名与FRAUDEAGLE算法的评论结果排名，在排名的后期评论人实时先验的评论排名与FRAUDMRF的评论排名指标接近，分析可得其原因是因为产品实时先验下降，才导致FRAUDMRF的评论在排名后期降低。

图4 两个数据集评论排名

图5为两个数据集评论人排名。

由图5可以看出，FRAUDMRF的评论人结果的NDCG指标整体上的排名都遥遥领先FRAUDEAGLE算法的评论人排名结果。在两个数据集上将前2000的评论(评论人)排名的平均精度(Average Precision，简称AP)指标以表格的形式展现，如表6所示。

图5 两个数据集评论人排名

表6 前2000评论(评论人)排名AP

4 结论

(1)在网络结构上，本文建立的轻量型二部图，能够在短时间内获得近期评论(评论人)的可疑度，由于是轻量型二部图，因为顶点数量较少，不仅在网络传播上时效性高，且还是一个稳定的快速收敛算法。

(2)在比较结果上，FRAUDMRF在两个数据集上，无论是靠前的排名还是靠后的排名都领先于FRAUDEAGLE，可以证明马尔可夫随机场融入在线实时先验的重要性，以及网络效应在虚假评论领域发挥的优良表现。