孙 勇 1,2 谭文安 1 金 婷 1 周亮广 2
1 (南京航空航天大学计算机科学与技术学院 南京 211106) 2 (安徽省地理信息集成应用协同创新中心(滁州学院) 安徽滁州 239000) (ysun.nuaa@yahoo.com)
随着云计算、服务计算以及社会计算等新技术不断应用于企业信息领域，越来越多的业务过程跨越了企业组织边界，构成了不同组织间松散耦合的云计算应用系统.云计算的广泛应用将传统的封闭、静态、可控的企业计算环境迁移到以开放、动态、不确定为特征的面向大规模服务计算的分布式系统.支持云计算应用系统的可信服务评估模型正面临着协同作弊和虚假评价等各种恶意攻击 [1-2] ，严重影响了企业之间的协同工作效率 [3] .而且，传统的服务评估模型只适用于小规模企业信息系统，难以满足大数据环境下云计算应用系统的服务可信度评估和实时计算的要求.
在互联网应用中，协同服务系统日志的反馈数据可能存在着大量的虚假内容，严重干扰了云计算应用系统从海量的反馈数据中发现高可信的服务.在此背景下，尽管面向服务的云计算应用系统凭借集成第三方服务，降低了业务运作的成本，但也隐藏着巨大的风险.现有的跨组织云平台缺乏行之有效的可信评价机制应对恶意欺诈行为 [4-8] ，而是假设反馈用户的评分值是真实可靠的，不存在虚假行为.但是，在现实世界中，攻击用户为了个体组织利益，对某些服务故意给出虚假错误的评价，影响了服务协同系统的预测评分质量.虚假用户可以通过欺诈行为获取利益，仅靠服务用户的自律难以确保云端服务的质量，应设计出更有效的可信服务评估机制，以消除欺骗行为所产生的负面影响，为跨组织业务推荐可信的服务，从而提高云计算应用系统的运行稳定性和可靠性 [9-10] .
服务用户虚假反馈评价和基于信誉的服务用户信任分析模型主要研究了个体服务用户恶意攻击.针对个体服务用户的虚假反馈评价，基于偏离率和声望值的用户信任评估方法通过迭代计算，分析反馈用户的评分真实性，从而估算出用户的信誉值 [11] .偏离率被用于评价服务用户的可信性，而声望值则用来计算服务用户的重要性.服务用户的偏离率越大，其可信度越低；用户的声望值越大，则表明用户的重要度越高 [12] .基于偏离率和声望值的信任评估方法遏制了个体欺诈提供者的一般恶意行为，但在应对协同作弊及策略攻击等恶意行为时，缺乏有效的评估机制.
基于聚类的可信度分析算法通过预处理基本用户信息进行离线聚类，能够有效地识别出协同作弊问题的服务用户群体 [13-14] .然而，大规模服务计算系统的大数据特性直接影响着协同作弊团体识别与检测的计算速度与质量.传统基于聚类的可信度分析算法存在居多限制：聚类过程采用了基于完全批量的训练学习方法，其算法的时间效率较低；当协同计算应用系统日志中服务用户反馈数据在线更新时，需要重新训练全部样本数据，难以适应大规模服务计算环境下服务反馈评分数据量大且变化快的特点.不同于基于完全批量学习的聚类方法，基于随机梯度下降法的在线聚类模型每次从全部服务反馈训练样本中随机抽取单个样本，并且仅对一个服务反馈样本数据进行学习，然后通过调整聚类模型权值参数以减少预测误差，该方法适用于实时在线服务检测分析 [15-18] .基于随机梯度下降法的在线聚类模型采用了随机抽样方法，减小了学习基数的规模量，极大程度地提高了协同作弊群体检测的时间效率，但是同时也降低了预测精度.
综上所述，支持跨组织云计算应用的协同作弊用户在线检测分析是一个复杂的综合问题，不仅需要考虑大规模服务计算的时效性问题，而且还需要考虑共谋欺骗检测与协同作弊用户团体识别等问题.针对时效性和协作恶意攻击问题，本文提出了一种基于在线聚类的协同作弊团体识别模型及其高效算法，主要贡献有3个方面：
1) 综合考虑大规模服务计算的大数据性特征，提出一种新颖的基于改进更新规则的在线聚类算法，采用小批量学习训练方法，通过基于自适应权重修正的聚类分组方差计算，并进行递减增量优化更新规则的动量性参数，以提高在线 K Means算法的聚类质量.
2) 建立了一套协同作弊检测机制，用以识别出协作虚假攻击行为.针对恶意团体协同作弊及策略攻击等恶意行为，充分考虑团体的同谋行为特征和协同攻击现象，利用聚类的性质以及团体的异常性，提出了基于同谋特征的决策图检测方法，快速自动识别出协同作弊行为.
3) 仿真验证分析了基于在线聚类的协同作弊用户识别算法，实验结果表明所提出的在线共谋团体识别算法具有良好时间性能，并有效地解决大规模服务计算中服务协作反馈欺骗的问题.
大数据环境下，面向服务的集成应用平台中不断涌现出大批量的新用户及其评价数据，服务用户的反馈评价具有主观性高、规范低、更新快以及数量极大等特征，传统的基于聚类的服务可信度评估算法在进行聚类分析时会造成大量的时间开销，难以满足大规模服务可信度评估分析的实时性需求.因此，本文提出了基于改进更新规则的在线 K Means聚类分析技术，针对基于随机梯度法的在线聚类算法精度问题，采取一种改进的基于小批量学习的在线 K Means聚类算法；并且，通过自动修正权重的聚类分组方差优化方法，提高了在线 K Means算法的聚类质量，同时保证了聚类算法的时间效率.
K Means聚类根据服务特征的相似性，将原始数据集划分为 K 个分组(cluster). K Means聚类的输入包括类别数目 K 和训练样本数据，输出则为 K 个类别的分组集合 [19] .假设用户服务评分训练样本为 R ={ r t | t =1,2,…, N }，随机初始化 K 个聚类中心的参考向量为 m i , i =1,2,…, K ，根据参考向量 m i ，将所有的训练样本分配到 K 个用户聚类分组 G i , i =1,2,…, K 中，聚类方法按可计算为
(1)
在每次迭代时，基于大批量学习的 K Means聚类方法求出同类所有用户的服务评价平均值作为临时中心点，更新分组中心的方法计算为
(2)
其中， n i 为聚类分组 G i 的用户数量.
基于随机梯度下降的在线学习方法，通过逐个实例计算并更新聚类的分组中心，当 r t ∈ G i ，标记变量 
表示聚类分组的误差距离，聚类迭代优化过程中不断减小误差距离，则对于单个用户实例的聚类误差定义为
(3)
其中
(4)
式(3)采用随机梯度下降法，得到 r t 的更新变量计算为
(5)
由式(5)可得到 r t 的更新规则为
m i ← m i + η ·( r t - m i ).
(6)
尽管基于随机梯度下降的在线聚类算法(SGD K Means)适用于大规模服务可信度评估分析应用，但是SGD K Means的聚类质量并不佳.因此，本文采用了基于小批量学习的在线聚类算法(Mini K Means)，通过小批量样本学习，逐步考虑小批量样本实例，每一步进行少许更新.基于小批量学习的在线聚类算法是批量梯度学习法和随机梯度下降法的一种折衷方案，介于两者之间.
综上分析，基于小批量学习的在线聚类算法每次选取适量的训练样本进行迭代优化，直到收敛，其算法描述如下：
算法1 . 基于小批量学习的在线聚类算法(Mini K Means).
输入：服务用户-服务评分信息 D =( U , I , R )、聚类数目 K ；
输出：聚类结果.
① 随机选取 K 个用户作为聚类中心；
② 将训练样本 Batches 划分为多个小样本 batch ；
③ REPEAT
④ FOR batch IN Batches DO
⑤ FOR r t ∈ batch DO 
*用户评分信息 r t 属于小批量样本中*
⑥ 根据更新规则式(4)计算用户与所有聚类分组中心加权距离最小： 
*将用户评分数据 r t 加入类别 G i 更新分组中心*
⑦ 采用小批量学习的更新规则： m i ← m i + η ·( r t - m i )；
⑧ END FOR
⑨ END FOR
⑩ UNTIL m i 收敛. *聚类中心点不变*
根据算法1可知，在每次迭代时，只选择 batch 个训练样本，其中 batch 远小于所有训练样本数据，因此，基于小批量学习的在线聚类算法能满足大规模服务可信度评估分析的在线实时性需求.
在线 K Means聚类算法是将所有聚类分组中数据对象之间的距离之和作为最小化目标，忽视了每个聚类分组的距离之和不平衡现象，聚类获得的结果可能存在一种现象：一些分组内的距离之和较大，而另外一些分组的距离之和较小，采用所有分组距离累加的方法掩盖了某些聚类分组效果不佳的问题，导致在线 K Means聚类算法陷入局部最优 [20] .针对局部聚类分组的距离误差优化不平衡问题，基于小批量学习的在线聚类算法引入了自适应加权距离的计算方法，最小化所有聚类分组的最大距离误差，解决各聚类分组的距离误差不平衡问题，实现在线聚类的最优化，其定义为
(7)
其中， E max ( m i | r t )是所有聚类分组的最大距离误差，直接最小化 E max ( m i | r t )是一个非常复杂的最优化求解问题.为了适用于在线聚类的优化模式，采用自适应加权距离方法，将 E max ( m i | r t )最小化目标松弛为
(8)
其中， 
为第 i 个聚类分组的权值； α 是权值调节参数， α ∈[0,1].则聚类算法的优化目标为Minimize： E max ( m i | r t )，即：
(9)
采用拉格朗日乘数法求解式(9)，计算可得：
(10)
其中， 
聚类分组的距离误差决定了权重 w i 的大小，聚类分组的距离误差越大，权值也越大.
通过采用自适应权值修正的更新规则，修改在线聚类参数 
计算可得：
(11)
根据更新规则式(11)，将训练样本在线地划分到加权距离最小的聚类分组中，相比于标准的样本分派距离，改进的更新规则融入了自适应权值修正方法.我们分析加权距离可知，若分组误差距离大，其权值也大，导致一部分距离该分组较远的样本被划分到其他分组；相反，具有权值较小且误差距离也小特征的分组吸收到部分样本.在聚类过程中，通过加权惩罚较高误差的分组，有效地平衡了局部聚类分组的距离误差.
综合考虑2个不同分组的权值比率，通过详细分析加权距离可知：
(12)
(13)
由式(12)(13)可知，在线聚类分组的权值与聚类分组的距离误差成正比关系；其中聚类调节参数 α 取值区间为0≤ α <1.当调节参数 α 的值增加时，比率指数 
和 
也随之而增加，不同分组距离误差的差异被增强.因此，通过参数 α 可调节对分组误差的赏罚力度，合理地设置权值能提升聚类效果.但是，设置过大的调节值会导致样本被错误地划分到其他分组，过小的调节值则没有效果，例如当 α =0，则所有权值为 w i =1，在线聚类的更新规则变成了传统的形式，可见调节参数 α 设置适中为宜.而且，聚类模型通过不断地更新调节参数控制权重，从而提升在线聚类的质量，权重更新计算为
w ( t ) = β · w ( t -1) +(1- β ) · w ( t ) ，
(14)
其中， β 控制了上次权重对当前权值的影响，保证了聚类过程的稳定性.
同时，为了确保在线聚类正常收敛，针对聚类更新规则的动量项参数 η 难以确定的问题，本文采取一种新的 η 值计算优化模型，通过逐渐减少动量项参数 η 以更新聚类中心.
由聚类更新公式可知：
(15)
由式(15)推导可得：
(16)
可得:
(17)
比较式(17)和式(6)，可选取 η =1 n i .
综上分析，基于改进更新规则的在线聚类算法(My K Means)通过修改聚类更新规则的参数，进一步优化了基于小批量学习的在线聚类算法，My K Means可描述如下：
算法2 . 基于改进更新规则的在线聚类算法(My K Means).
输入：服务用户-服务评分信息 D =( U , I , R )和聚类数目 k ;
输出：聚类结果.
① 随机选取 K 个用户作为聚类中心；
② 将训练样本 Batches 划分为多个小样本 batch ；
③ REPEAT
④ FOR batch in Batches DO
⑤ FOR r t ∈ batch DO *用户评分信息 r t 属于小批量样本中*
⑥ 根据改进更新规则式(13)计算用户与所有聚类分组中心加权距离最小： 
⑦ 将用户评分数据 r t 加入类别 G i 更新分组中心，采用在线学习的更新规则： m i ← m i + η ·( r t - m i ) ，其中， 
⑧ END FOR
⑨ END FOR
⑩ UNTIL m i 收敛. *聚类中心点不变*
基于改进更新规则的在线聚类算法综合考虑了在线 K Means聚类算法容易陷入局部最优解的问题，采用了基于自动修正权重的聚类分组方差优化方法，改进了在线聚类模型参数 
的确定方法；并且，通过修改更新规则的参数 η 值，从而提高在线聚类算法的准确性和时效性.
基于在线聚类的服务可信度分析方法将高相似性的服务用户划分到同一个聚类分组，其中可信的反馈评分用户占着绝大多数.虚假服务用户与可信服务用户评价行为存在明显的不同，2类用户的评分会出现较大的偏差，通常虚假用户表现出评价行为高度一致性.因此，当通过在线学习方法计算得出的聚类分组相似度较大时，极有可能是同谋团体.
协同作弊行为通常具有3个特征 [21] ：1)协同作弊团队表现出明显的整体性，在评价行为上保持高度的一致性；2)协同作弊团队与正常用户相比表现出异常性；3)协同作弊团队的攻击时间几乎相近，因为集中攻击能提高作弊的效果 [22] .通过深入分析协同作弊的攻击行为特征，本文将协同作弊的特征刻画方法进行了改进，提出一种新的基于协同作弊特征决策图的检测方法，用以识别出协同作弊团队.
协同作弊团体又称为同谋团体，同谋用户往往评分较大或较小，有强的关联性，采用聚类方法能识别协同作弊行为.同谋攻击者之间具有非常高的一致性特征，其相似度大于0.9，在评价行为上表现出高度的一致性 [23-24] .因此，相似度极高的聚类分组很有可能是协同作弊团体.
定义1 . 协同作弊团体的整体性.针对协同作弊团队行为高度一致性问题，假设通过基于在线 K Means聚类的计算得到聚类分组为{ G i | i =1,2,…, K }，聚类 G i 中 n i 个用户反馈数据，采用团体评分一致性(group ratings consistency, GRC )评估聚类分组 G i 的行为整体性， GRC ( G i )计算方法可定义为
(18)
GRC ( G i )表示聚类分组 G i 整体性的程度，值越小则说明 G i 整体性越高.实际上，协同作弊团体不仅具有高度整体性的特征，而且，相对正常用户，其数量较少.本文不采用平均值描述同谋团体的整体性特征，而是通过对所有值求和来刻画聚类分组的整体性特征，为了与协同作弊团体的异常性评价数值范围一致性，采用了协同作弊团体整体性计算值的倒数作为协同作弊的评价指标，其定义为
(19)
当聚类分组的 GRC ( G i )值较高时，则表明该聚类分组协同作弊的可能性大.
定义2 . 协同作弊团体的异常性.假设通过在线聚类计算得到了 K 个聚类分组{ G i | i =1,2,…, K }，当协同作弊团队与正常聚类分组相比，通常表现出异常性.通过计算用户聚类分组之间的差异性，能够检测出同谋团体.因此，定义了一种团体评分偏差度(group ratings deviation, GRD )的指标函数，以识别出协同作弊团体的异常性， GRD 定义为
(20)
其中，| R |表示所有的反馈用户数量;| G j |代表聚类分组 G j 的服务用户数量； D (·)表示偏差函数；聚类分组整体的偏离度 GRD ( G i )大小反映了聚类分组 G i 评价与真实值的偏差程度.因此，聚类分组的 GRD ( G i )值越大，则表示该聚类分组越有可能是协同作弊团体.
定义3 . 协同作弊团体的攻击时间相似性.协同作弊团体的攻击时间几乎相近，因此，将时间作为描述协同作弊团体的辅助评价指标 [25-26] .通过计算协同作弊团体中评价时间最大值和最小时间之间的时间窗，衡量协作团体的共谋攻击可能性.时间评价指标采用团体评分的时间相似度(group rating time similarity, GTS )表示，时间窗口函数定义为 TW ( r j )，表示聚类分组 G i 中用户 j 的评分时间窗口:
(21)
其中， T ( r j )表示用户 j 的评分时间， j =1,2,…, K ； τ 是时间比较参数，表示可能作弊的评分时间窗.
本文采用聚类分组中反馈用户的最大评价时间窗 TW ( r j )作为协同作弊的评价指标，其定义如下：
GTS ( G i )=max{ TW ( r j )}，
(22)
其中， j =1,2,…, K .
针对协同作弊团队的攻击行为特征，根据同谋欺骗恶意行为的特征定义，从聚类分组的整体性 GRC ( G j )、行为异常性 GRD ( G i )以及评分时间相似性 GTS ( G i )三个方面进行协同作弊行为的检测分析.
Rodriguez和Laio [27] 最近在《Science》提出了一种密度中心聚类算法，将密度值和斥群值表示在一个2维度的决策图上，受此算法的启发，本文提出了一种基于2维特征决策图的协同作弊团体识别方法，对于每个在线聚类分组，可为其计算出( GRC ( G i ), GRD ( G i ))，将二元组( GRC ( G i ), GRD ( G i ))分别以行为整体性为横轴、行为异常性为纵轴，从而形成了协同作弊特征决策图，该图能够帮助决策者快速发现离群作弊团体.在此基础上，将攻击时间作为辅助评价指标，进一步对聚类分组进行评分时间相似性 GTS ( G i )计算，以更好地识别出同谋团队.
支持跨组织业务应用的协同作弊团体发现算法框架，根据大规模服务系统日志中服务用户反馈评分信息，综合考虑大规模服务计算的大数据特性问题.首先采用了一种改进的基于小批量学习的在线聚类方法，并通过自动修正权重的聚类分组方差计算进行递减增量优化，将所有高相似性的服务用户聚到同一分组，通过计算目标服务用户与分组中心的相似性确定其所属的类别分组；然后，分析团体的同谋行为特征和协同攻击现象，利用聚类的性质和同谋团体异常性的特征，检测出协同作弊团体，其算法集成框架如图1所示:
Fig.1 Integration framework of collaborative collusion evaluation
图1 协同作弊团体发现算法集成框架
综上所述，基于在线聚类的协同作弊团体发现算法的具体步骤如算法3所示：
算法3 . 基于在线聚类的协同作弊团体发现.
输入：服务用户-服务评分信息 D =( U , I , R )；
输出：协同作弊团体.
① RData ← PreProcess ( U , I , R )； *数据预处理*
② Groups ← My K Means ( RData )； *调用基于改进更新规则的在线 K Means算法对所有服务用户聚类分组*
③ FOR G i IN Groups DO *计算分析每个聚类分组*
④ 利用在线聚类求解结果，计算所有服务用户分组的整体性：
⑤ 计算所有服务用户分组的行为异常性： 
⑥ 计算所有服务用户分组的攻击时间相似性： GTS ( G i )←max{ TW ( r j )},其中， j =1,2,…, K ；
⑦ END FOR
⑧ DecDiagram ( GRC ( G i ), GRD ( G i ))；
*采用协同作弊特征决策图的可视化方法，筛选出共谋欺骗分组*
⑨ 利用攻击时间相似性验证共谋欺骗分组.
基于在线聚类的协同作弊用户识别方法的程序执行时间主要是在聚类过程产生的，假定采用基于完全批量的聚类方法，时间复杂度为 O ( n × K × d × i )；当采用基于随机梯度下降法的在线聚类方法 [28] 时，时间复杂度为 O (1× K × d × i )；当采用基于小批量在线学习的聚类方法时，时间复杂度为 O ( m × K × d × i )，其中， n 和 m 是聚类训练样本数量， K 为聚类的分组数， d 为特征属性维度， i 表示迭代次数.由于 n ≫ m >1，总体而言，基于在线聚类的协同作弊检测算法极大地减少了聚类的计算时间，同时，基于协同作弊特征决策图的识别方法保证了对共谋检测的正确性.
本文实验环境基于Intel I5-7300 HQ笔记本，CPU主频为2.50 GHz，内存为8.00 GB，所有算法都运用Python编程语言，采用了PyCharm编译工具，运行在Windows 10操作系统上.为了验证所提出算法的可行性和有效性，本节将在不同规模的人工合成数据集、UCI真实数据集以及服务计算等真实数据集上进行了一系列的仿真实验.
本节仿真实例将在不同规模人工合成数据集上，分别从在线服务用户聚类分析与基于改进在线聚类的协同作弊用户识别2个方面运用可视化方法对本文方法进行分析和说明.
3.1.1 基于在线学习的服务用户聚类分析
首先，仿真实验对在线聚类算法进行了收敛性分析，在线聚类分析实验过程中，采用了Scikit-learn的数据分析函数，以[1,1],[1,3],[3,3],[3,1]为中心生成了10 000个人工合成数据，对比分析了基于随机梯度下降的在线聚类算法(SGD K Means)、基于小批量学习的在线聚类算法(Mini K Means)以及基于改进更新规则的在线聚类算法(My K Means)的收敛速度.在聚类过程中，批量规模取值为500，3种算法在给定的人工合成数据集上运行20次，并计算出算法收敛时间的平均值，实验结果如图2和图3所示:
Fig.2 Convergence rate analysis of online clustering (Samples=5 000)
图2 在线聚类收敛速度分析(Samples=5 000)
Fig.3 Convergence rate analysis of online clustering (Samples=10 000)
图3 在线聚类收敛速度分析(Samples=10 000)
图2的训练样本数据的数量为5 000，而图3的样本数目为10 000.通过观察可知，SGD K Means算法、Mini K Means算法以及My K Means算法都能以较快的速度收敛，适用于大规模服务计算.但是，My K Means和Mini K Means的聚类质量明显好于SGD K Means算法；并且，本文所提出的在线聚类算法My K Means的收敛效果更优于Mini K Means算法.
针对 K Means聚类的分组数目的确定问题，基于改进更新规则的在线聚类算法(My K Means)采用了基于拐点的聚类数目确定方法，首先随机选取训练样本数据中的 K 个点作为起始点，当 K 值确定后，随机进行聚类计算 n 次，取得最小开销函数值的 K 作为最终聚类结果，避免随机引起的局部最优解；并通过绘制出 K -开销函数散点图，选取有明显拐点的开销函数值，设为 K 值，如图4所示.
在线聚类效果分析实验主要采用了Scikit-learn的数据分析函数，同样以[1,1],[1,3],[3,3],[3,1]为中心，生成了10 000个人工合成数据，分别应用 K Means+ +聚类算法、改进前的基于小批量学习的在线聚类算法(Mini K Means)以及提出的基于改进更新规则的在线聚类算法(My K Means)进行了仿真模拟，实验效果如图5所示.其中ObjCost值表示误差平方和值， K Means+ +的误差平方和最小，其ObjCost值为1.162 036;Mini K Means的误差平方和值最大，其ObjCost值为1.180 610；而My K Means的ObjCost值为1.165 977，几乎和 K Means+ +接近，好于Mini K Means算法，取得了良好的聚类效果.
Fig. 4 K value confirmation of online clustering for MyKMeans
图4 MyKMeans在线聚类K值选取分析
Fig. 5 Effective analysis of user clustering based on online learning
图5 基于在线学习的用户聚类效果分析
Fig. 6 Silhouette coefficient analysis of online clustering
图6 基于轮廓系数的在线聚类效果分析
在线聚类效果分析实验进一步采用轮廓系数，评估分析了 K Means+ +和My K Means算法的聚类效果，实验结果如图6所示.其中， K Means+ +算法效果稍好于My K Means算法，My K Means算法与 K Means+ +算法的轮廓系数值几乎相同.
在验证所提出的基于改进更新规则的在线聚类算法(My K Means)的时效性时，为使得实验结果对比反差更大，效果更明显直观，算法时间效率实验生成3种规模间隔更大的人工数据[2 000,5 000,10 000]，并将 K Means+ +，Mini K Means，以及My K Means算法运行在该人工数据集上，3种算法的时间性能分析实验结果如图7所示.其中，My K Means算法的时间效率与改进前的Mini K Means算法接近，都明显好于 K Means+ +算法，特别是随着样本数量的不断增多，My K Means算法比 K Means+ +算法效率表现得更好.
由实验分析可知，所提出的My K Means算法不仅表现出良好的算法时效性，而且具有较好的算法精度.
Fig. 7 Time efficiency analysis of clustering algorithm
图7 聚类算法的时间效率分析
3.1.2 协同作弊特征决策图可视化分析
Fig. 8 Binary decision diagrams of collaborative collusion features
图8 协同作弊特征2维决策图分析
协同作弊用户分组检测实验采用人工合成数据方法，针对协同作弊团队的攻击问题，根据协同作弊恶意行为的特征定义，从聚类分组的整体性、行为异常性以及评分时间相似性3个方面进行协同作弊检测分析.对于每一聚类分组，计算出聚类分组行为的 GRC ( G i )和异常性值 GRD ( G i )二元组，分别以行为整体性的取值为横轴、行为异常性值为纵轴，从而形成了协同作弊特征决策图，为用户可信度评估分析提供了决策支持，如图8所示.
通过观察图8可知，聚类分组3和分组6由于同时具有较大的 GRC ( G i )和 GRD ( G i )值，于是从其他聚类分组中脱颖而出，从而帮助管理者直观地快速检测出协同作弊团体.因此可见，协同作弊特征决策图方法能够有效地呈现出共谋团体.在此基础上，可将攻击时间作为辅助评价指标，进一步对聚类分组3和6进行评分时间相似性 GTS ( G i )计算，以更好地识别出协同作弊团队.
本节实验采用了真实数据集，分别从聚类精度和时间效率2个方面测试了本文提出算法My K Means的有效性和可行性.其中，仿真实验从UCI机器学习数据库 [29] 中选择了Iris，Digits，20newsgroup以及在WS-DREAM数据集 [30] 中选取了wsdata1和wsdata2等真实数据集，相关数据集的信息如表1所示：
Table 1 Real Data Analysis
表1 真实实验数据分析
3.2.1 在线聚类算法的精度分析
在聚类精度实验过程中，将采用聚类性能度量函数分析聚类结果的精确度，度量函数指标包括6个聚类有效性评测指标：1)类内聚合度 Inertia ；2)调整兰德指标(adjusted rand index, ARI )；3)调整互信息(adjusted mutual information, AMI )；4)同质性指标(homogeneity, Homo )；5)完整性指标(completeness, Compl )；6)调和平均指标(V-measure, V - meas ).其中，类内聚合度 Inertia 是类内聚合度的一种度量方式，当 Inertia 值越小时，聚类效果越好；调整兰德指数 ARI 是一个外部评测指标，根据数据真实分类标签，测试数据的聚类结果与实际分类之间的相似度；当聚类精度越高时，即聚类结果越近似于实际分类， ARI 值也越高；调整互信息 AMI 是利用基于互信息的方法来衡量聚类效果，当聚类结果越近似于实际分类， AMI 值也越高；同质性指标 Homo 是分析每个聚类是否只包含单个类别的成员；完整性指标 Compl 则是分析给定类的所有成员是否都分配给了同一聚类分组；而调和平均指标 V - meas 表示 Homo 和 Compl 两者的调和平均， V - meas , Homo , Compl 的值在0～1之间，值越大则表明聚类效果越佳.
首先，我们采用了UCI分类数据集Iris进行精度仿真实验，Iris数据集包含了150个数据样本，分为了3类，每类有50个数据，每个样本数据包含4个属性特征.数据集Iris的聚类精度实验结果如表2所示：
Table 2 Clustering Accuracy Analysis of Iris Data
表2 Iris实验数据的聚类精度分析
其次，我们采用了UCI手写数字图像训练集Digits进行精度仿真实验，Digits共有1767个手写数字的图像矩阵，每个手写数字图像都储存成为8×8的矩阵，每个像素表示一个特征.因此，Digits原始数据是64个特征.数据集Digits的聚类精度仿真实验结果如表3所示：
Table 3 Clustering Accuracy Analysis of Digits Data
表3 Digits实验数据的聚类精度分析
最后，我们采用了UCI机器学习库的20新闻语料数据集(20newsgroup)进行精度仿真实验，本次实验抽取了20newsgroup数据集中4个不同话题的新闻组信息，包含了2 034个新闻语料样本数据，每个样本的特征维度是4 331.在聚类处理过程中，首先采集数据并提取特征，将有噪文本转化为向量表征；然后进行聚类模型训练实验.数据集20newsgroup的聚类精度实验结果如表4所示：
Table 4 Clustering Accuracy Analysis of 20newsgroup Data
表4 20newsgroup实验数据的聚类精度分析
通过观察表2～4，可以得出以下结论：本文提出的改进聚类算法My K Means，在3个真实数据集上的聚类效果均优于SGD K Means和Mini K Means算法，表现出了良好的算法性能.
3.2.2 在线聚类算法的时间性能分析
本次实验将从不同规模的样本数量和不同数量的属性特征2方面，在真实新闻语料数据集20newsgroup上验证分析了本文相关的聚类算法的时间效率.图9是基于不同数据规模的聚类时间性能实验结果，验证了本文相关聚类算法的时间相对于不同规模样本数量的变化情况，随着规模增加，聚类处理时间不断增加.图10是基于不同维度属性特征的聚类时间性能实验结果，主要分析了在不同属性特征数量的变化情况下本文相关聚类算法的时间性能.由图10可知，随着维度增加，聚类处理时间不断增加.
Fig. 9 Time efficiency analysis of clustering algorithms
图9 不同数据规模的聚类算法时间效率分析
Fig. 10 Time efficiency analysis of clustering algorithms
图10 不同属性特征规模的聚类算法时间效率分析
通过观察聚类实验结果图9和图10，可得出以下结论：在数据集20newsgroup的不同数据规模和属性特征数的变化情况下，My K Means的聚类时间性能远优于 K Means和 K Means+ +聚类算法，与Mini K Means算法的时间性能接近.由此分析，本文所提出的在线聚类算法在真实数据集表现出良好的算法时效性，而且具有较好的算法精度，进一步验证说明了本文提出算法的可行性和有效性.
3.2.3 协同作弊用户分组识别算法的分析实验
协同作弊团体识别实验采用了真实的WS-DREAM数据集wsdata1和wsdata2，其中wsdata1和wsdata2是用于服务用户评价和服务推荐的数据集，根据共谋作弊恶意行为的特征，我们分别对WS-DREAM的2个数据集进行了攻击.然后，运用在线聚类算法My K Means对WS-DREAM数据集进行聚类分组，并在此基础上，采用本文的在线协同作弊团体识别方法，计算出每个聚类分组的行为二元组：整体性值 GRC ( G i )和异常性值 GRD ( G i ).其中，表5是wsdata1数据集的所有聚类分组的特征行为二元组值.
Table 5 Analysis of wsdata1 Collusion Features
表5 wsdata1协同作弊检测分析
在此基础上，我们采用共谋特征决策图方法，分析了每个聚类分组的行为，如图11和图12所示：
Fig. 11 Analysis of wsdata1 collusion features
图11 wsdata1协同作弊检测分析
Fig. 12 Analysis of wsdata2 collusion features
图12 wsdata2协同作弊检测分析
在图11中，具有共谋特征的聚类分组1、分组2以及分组3都有较大的 GRC ( G i )和 GRD ( G i )值，并且远离正常聚类分组，于是被识别出来；同样，在图12中，聚类分组1和分组3也是同时具有较大的 GRC ( G i )和 GRD ( G i )值，在基于作弊特征二元决策图的可视化方法帮助下，我们有效地区分出了正常聚类分组和共谋团体.而且，通过综合分析实验结果表5和图11～12可知，相对于表格分析方法，基于特征决策图的检测方法更容易识别出具有协同作弊特征的聚类分组.在真实数据集wsdata1和wsdata2上，基于特征决策图的协同作弊团队发现方法表现出了良好的识别效果，验证分析了本文所提出的协同作弊团队识别方法.
针对大规模服务计算的大数据特性，提出了基于改进更新规则的在线聚类算法，采取改进的基于小批量学习的在线 K Means聚类算法，并通过自动修正权重的聚类分组方差优化方法，提高了在线 K Means聚类算法的解质量，同时保证了聚类算法的时间效率；进一步，基于在线聚类分组的基础上，充分考虑协同作弊及策略攻击等恶意行为的特征，定义了同谋攻击的一致性、异常性以及时间相似等检测指标函数，设计了一个基于协同作弊特征决策图的共谋团体识别方法，采用可视化的方式分析了聚类分组的情况.通过在线聚类和协同作弊检测方法，实现了共谋团体的快速识别，本文主要工作包括：1)提出了基于改进更新规则的在线聚类算法；2)提出了在线协同作弊团体发现算法，为面向服务的云计算应用系统集成可信服务提供了技术支持；3)仿真实验分析了基于在线聚类的协同作弊团体识别方法的可行性.实验结果表明，提出的算法通过融合在线聚类与共谋欺骗检测技术，有效地解决了大规模服务计算中协同反馈欺骗问题.
基于在线学习的协同作弊团体识别方法能够快速检测出共谋欺骗用户，为可信分析提供决策支持，因此，在可信计算与服务推荐系统领域有着重要的应用前景.当前，基于在线学习的协同作弊团体识别方法面临各种挑战，特别是如何有效地使用分布式数据和并行计算技术，基于并行在线学习的协同作弊团体识别问题有待人们进一步深入探索和解决.
参考文献
[1]Jiang Meng, Cui Peng, Faloutsos C. Suspicious behavior detection: Current trends and future directions[J]. IEEE Intelligent Systems, 2016, 31(1): 31-39
[2]Wang Haiyan, Yang Wenbin, Wang Suichang, et al. A service recommendation method based on trustworthy community[J]. Chinese Journal of Computers, 2014, 37(2): 301-311 (in Chinese)(王海艳, 杨文彬, 王随昌, 等. 基于可信联盟的服务推荐方法[J]. 计算机学报, 2014, 37(2): 301-311)
[3]Sun Yong, Tan Wenan. Cross-organizational workflow task allocation algorithms for socially aware collaborative computing[J]. Journal of Computer Research and Development, 2017, 54(9): 1865-1879 (in Chinese)(孙勇, 谭文安. 支持社会协同计算的跨组织工作流任务分派算法[J]. 计算机研究与发展, 2017, 54(9): 1865-1879)
[4]Bouguettaya A, Singh M, Huhns M, et al. A service computing manifesto: The next 10 years[J]. Communications of the ACM, 2016, 60(4): 64-72
[5]Meng Xiaofeng, Li Yong, Zhu Jianhua. Social computing in the era of big data: Opportunities and challenges[J]. Journal of Computer Research and Development, 2013, 50(12): 2483-2491 (in Chinese)(孟小峰, 李勇, 祝建华. 社会计算: 大数据时代的机遇与挑战[J]. 计算机研究与发展, 2013, 50(12): 2483-2491)
[6]Wu Zhiang, Zhuang Yi, Wang Youquan, et al. Shilling attack detection based on feature selection for recommender systems[J]. Acta Electronica Sinica, 2012, 40(8): 1687-1693 (in Chinese)(伍之昂, 庄毅, 王有权, 等. 基于特征选择的推荐系统托攻击检测算法[J]. 电子学报, 2012, 40(8): 1687-1693)
[7]Burke R, Mobasher B, Williams C, et al. Classification features for attack detection in collaborative recommendation systems[C] 
Proc of the 12th Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2006: 542-547
[8]Wu Zhiang, Wang Youquan, Cao Jie. A survey on shilling attack models and detection techniques for recommender systems[J]. China Science Bull, 2014, 59(7): 551-560 (in Chinese)(伍之昂, 王有权, 曹杰. 推荐系统托攻击模型与检测技术[J]. 科学通报, 2014, 59(7): 551-560)
[9]Tan Wenan, Sun Yong, Li Lingxia, et al. A trust service-oriented scheduling model for workflow applications in cloud computing[J]. IEEE Systems Journal, 2014, 8(3): 868-878
[10]Sun Yong, Tan Wenan, Li Lingxia, et al. A new method to identify collaborative partners in social service provider networks[J]. Information Systems Frontiers, 2016, 18(3): 565-578
[11]Li Baichuan, Li Ronghua, King I, et al. A topic-biased user reputation model in rating systems[J]. Knowledge and Information Systems, 2015, 44(3): 581-607
[12]Li Ronghua, Yu Xu, Huang Xin, et al. Robust reputation-based ranking on bipartite rating the networks[C] Proc of the 12th SIAM Int Conf on Data Mining. Philadelphia, PA: SIAM, 2012: 612-623
[13]Chandola V, Banerjee A, Kumar V. Anomaly detection: A survey[J]. ACM Computer Survey, 2009, 41(3): 1-15
[14]Vasilomanolakis E, Karuppayah S, Mühlhäuser M, et al. Taxonomy and survey of collaborative intrusion detection[J]. ACM Computing Surveys, 2015, 47(4): 55:1-55:33
[15]Yang Haiqin, Lu Rongcong, Jin Guoqing. Big data oriented online learning algorithms[J]. Communications of CCF, 2014, 10(11): 36-40 (in Chinese)(杨海钦, 吕荣聪, 金国庆. 面向大数据的在线学习算法[J]. 中国计算机学会通讯, 2014, 10(11): 36-40)
[16]Yang Haiqin, Lyu M R, King I. Efficient online learning for multitask feature selection[J]. ACM Trans on Knowledge Discovery from Data, 2013, 7(2): 1-27
[17]Orabona F, Crammer K, Cesa-Bianchi N. A generalized online mirror descent with applications to classification and regression[J]. Machine Learning, 2015, 99(3): 411-435
[18]Shalev-Shwartz S. Online learning and online convex optimization[J]. Foundations & Trends in Machine Learning, 2012, 4(2): 107-194
[19]Poole D L, Mackworth A K. Artificial Intelligence: Foundations of Computational Agents[M]. Cambridge, UK: Cambridge University Press, 2010
[20]Tzortzis G, Likas A, Tzortzis G. The MinMax k -Means clustering algorithm[J]. Pattern Recognition, 2014, 47(7): 2505-2516
[21]Miao Guangsheng, Feng Dengguo, Su Purui. A collusion detector based on fuzzy logic in P2P trust model[J]. Journal of Computer Research and Development, 2011, 48(12): 2187-2200 (in Chinese)(苗光胜, 冯登国, 苏璞睿. P2P信任模型中基于模糊逻辑的共谋团体识别方法[J]. 计算机研究与发展, 2011, 48(12): 2187-2200)
[22]Miao Guangsheng, Feng Dengguo, Su Purui. Colluding clique detector based on activity similarity in P2P trust model[J]. Journal on Communications, 2009, 30(8): 9-20 (in Chinese)(苗光胜, 冯登国, 苏璞睿. P2P信任模型中基于行为相似度的共谋团体识别模型[J]. 通信学报, 2009, 30(8): 9-20)
[23]Mehta B, Nejdl W. Unsupervised strategies for shilling detection and robust collaborative filtering[J]. User Modeling and User-Adapted Interaction, 2009, 19(1 2): 65-97
[24]Gunes I, Kaleli C, Bilge A, et al. Shilling attacks against recommender systems: A comprehensive survey[J]. Artificial Intelligence Review, 2014, 42(4): 767-799
[25]Mukherjee A, Liu Bing, Wang Junhui, et al. Detecting group review spam[C] Proc of the 20th Int Conf on World Wide Web. New York: ACM, 2011: 93-94
[26]Mukherjee A, Liu Bing, Glance N. Spotting fake reviewer groups in consumer reviews[C] Proc of the 20th Int Conf on World Wide Web. New York: ACM, 2012: 191-200
[27]Rodriguez A, Laio A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496
[28]Kanungo T, Mount D M, Netanyahu N S, et al. An efficient k -means clustering algorithm: Analysis and implementation[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2002, 24(7): 881-892
[29]University of California, School of Information and Computer Science. UCI Machine Learning Repository[EB OL]. (2007-06-25) [2013-04-04]. http: archive.ics.uci.edu ml
[30]The Chinese University of Hong Kong. WS-DREAM: Towards Open Datasets and Source Code for Web Service Research[EB OL]. (2015-08-29) [2017-08-18]. https: wsdream.github.io
Sun Yong , born in 1977. PhD. Member of CCF. His main research interests include cooperative computing, service computing, social workflow scheduling, intelligent infor-mation systems, and software engineering.
Tan Wenan , born in 1965. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include software engineering, process engineering and development environment, enterprise dynamic modeling, trusted service comput-ation, and enterprise intelligent information systems.
Jin Ting , born in 1994. MSc candidate. Her main research interests include coo-perative computing and service computing.
Zhou Liangguang , born in 1981. MSc. His main research interests include data mining and geographic information science.
Sun Yong 1,2 , Tan Wenan 1 , Jin Ting 1 , and Zhou Liangguang 2
1 ( College of Computer Science and Technology , Nanjing University of Aeronautics and Astronautics , Nanjing 211106) 2 ( Anhui Center for Collaborative Innovation in Geographical Information Integration and Application ( Chuzhou University ), Chuzhou , Anhui 239000)
Abstract Cloud computing has been successfully used to integrate various Web services for facilitating the automation of large-scale distributed applications. However, there exist numerous noise ratings given in service-oriented cloud applications by collusion groups. Collusion detection is one of the most import issues in the emerging service-oriented cloud applications. Especially with the emergence of massive Web services, it is still a tough challenge to identify collaborative collusion groups in large-scale cloud systems using the classical clustering algorithm with batch computing mode. To tackle the challenge, a novel online clustering-based detection method is proposed to find collaborative collusion groups in an efficient and effective manner. Firstly, a mini-batch K Means clustering method is employed to reduce the computational time for mining the large-scale service data; secondly, to improve the quality of the online clustering, a new and modified update rule is designed for the mini-batch K Means clustering method, which adaptively optimizes the clustering weights with variance through an iterative procedure; finally, based on measuring the behavior similarity and group ratings deviation of malicious peers, a binary decision diagram evaluation method is presented for detecting the bias and prestige of collusion groups in a visual manner. Theoretical analysis is conducted for validation purpose. Extensive experimentation and comparison with related work indicate that the proposed approach is feasible and effective.
Key words collaborative computing; collaborative collusion detection; online clustering; trust service computing; service-oriented cloud applications
摘 要 针对大规模服务计算环境中聚集反馈、协同作弊和虚假评价等问题，通过融合在线聚类与共谋欺骗检测技术，提出了一种支持大规模服务可信度分析的在线协同作弊用户发现方法.首先，根据大规模服务系统日志中用户反馈评分信息，综合考虑大规模服务计算的大数据特性问题，设计了一种新颖的基于改进更新规则的在线 K Means聚类算法：在基于随机梯度法的在线聚类算法的基础上，采用了一种改进的基于小批量学习的在线聚类方法；并且，通过自动修正权重的聚类分组方差计算，进行递减增量优化，提高了在线 K Means算法的聚类质量，同时保证了聚类算法的时间效率；然后，充分考虑了协同作弊团体的同谋行为特征和协同攻击现象，利用聚类分组的性质和同谋团体异常性的特征，检测出协同作弊团体.仿真实验结果表明：提出的基于在线聚类的协同作弊团体识别方法具有良好时间性能，有效地解决了大规模服务计算中虚假反馈的问题.
关键词 协同计算；协同作弊识别；在线聚类；可信服务计算；面向服务的云应用
中图法分类号 TP391.1
收稿日期 ： 2017-03-31；
修回日期： 2017-12-11
基金项目 ： 国家自然科学基金项目(61672022，61272036)；安徽省高校自然科学基金重点项目(KJ2017A414)
This work was supported by the National Natural Science Foundation of China (61672022, 61272036) and the Key Program of University Natural Science Foundation of Anhui Province (KJ2017A414).