基于一致性聚类的在线服务信誉度量

刘艳丽，付晓东，2，岳 昆，刘 骊，冯 勇，刘利军

1(昆明理工大学 信息工程与自动化学院，昆明 650500) 2(昆明理工大学 云南省计算机技术应用重点实验室，昆明 650500) 3(云南大学 信息学院，昆明 650091)

1 引 言

在线服务是指运用互联网技术向用户提供线上服务的方式.随着互联网技术的迅速发展和普及，越来越多的设备被接入到互联网中，使在线服务规模显著增长.在线服务已广泛应用于Web服务、电子商务、移动多媒体、电子学习等领域[1].然而在面对许多功能相似或相同的在线服务时，用户不仅要考虑功能需求，还要考虑非功能需求，即服务质量(Quality of Service，QoS)[2].此外，由于互联网具有开放性和虚拟性，导致服务提供者可能发布不真实、不客观的服务信息[3].信誉作为衡量服务QoS的重要指标，反映的是用户对服务总体的信任程度[4].因此，研究准确、客观的在线服务信誉度量方法不仅能有效地帮助用户选择在线服务也能促使服务提供者改善其服务质量.

用户与在线服务进行交易后，会根据个人体验对在线服务进行反馈评分，信誉系统将用户反馈评分以特定的方式集结起来形成信誉[5].用户对服务的评分可看成是用户对服务的分类.例如，用户对服务{s1,s2,s3,s4,s5,s6,s7}的评分为(1，3，3，1，2，4，2)，体现出用户将服务分为4类，分别为{s1,s4}、{s2,s3}、{s5,s7}以及{s6}.因此基于评分的服务信誉度量本质上是集结各用户对服务的分类信息获得用户群体对服务分类结果的过程.由于用户具有不同的行为习惯和偏好，其对服务的分类具有明显的个性化特征.因此，提高用户对服务分类与最终获得的信誉之间的一致性是确保信誉度量质量的重要因素.一致性反映的是用户群体对评价结果达成一致的程度，是测量群体评价意见一致性程度的重要参数[6].现有累加法、均值法等已被广泛应用的信誉度量方法均未考虑到用户对服务分类与信誉之间的一致性关系.

随着互联网上在线服务数量的不断增长及类型的多样化，如何集结用户对服务的分类合理有效地进行在线服务信誉度量成为亟待解决的重要问题.针对上述问题，本文提出一种基于一致性聚类[7]的在线服务信誉度量方法.该方法将用户对服务的评分视为用户对服务的分类，通过聚合所有用户对服务的分类形成一个最终的服务聚类，使得到的最终信誉度量结果与用户对服务分类之间的一致性最大且聚类效果较好.首先，考虑到在计算服务分类中的簇间和簇内相似性时需要消耗大量的空间，方法使用二进制组成的位向量来存储在线服务分类中的每个簇，降低存储空间的消耗；其次，方法是在服务集群的分类级别上运行的，具有很高的可扩展性；最后，对在线服务的分类进行聚合的过程中，不需要输入任何参数，自动计算最终聚类中的聚类数量.有效地提高了在线服务信誉的合理性和有效性.

2 相关工作

信誉作为评价服务的重要QoS之一，对服务选择的决策起着重要作用.近年来，为了研究更加准确、理性的在线信誉度量，国内外学者开展了一系列的工作.目前的在线服务信誉度量方式主要分为基于用户反馈评分和综合多种因素对服务信誉的影响[8].

常见的基于用户反馈评分的在线信誉度量方式有累加法模型、平均法模型、模糊模型、Beta信誉模型等[9]，上述方法均以用户反馈评分为基础来计算服务信誉，其计算原理简单，可以快速得到信誉值.例如，eBay使用累加法将用户对在线服务做出的反馈评分进行累加得出服务信誉值，Amazon使用平均法，以服务获得的所有反馈评分为基础求取平均值计算服务信誉.文献[10]提出了一种基于模糊的大数据处理框架来评估云服务的信任级别，在用户反馈的基础上评估服务的信任级别；文献[11]提出了一种Beta信誉模型，该模型在统计学理论的基础上结合β概率密度函数和用户反馈的评分计算在线服务信誉；文献[12]提出了一种考虑用户隐私代价的服务选择模型，其运用模糊逻辑与服务信誉、用户隐私相结合来计算用户的隐私代价，从而实现对候选服务的排序.

基于用户反馈评分的信誉度量方法未考虑服务质量、社交网络关系等其他因素对服务信誉的影响[13].为此，文献[14]基于QoS相似度计算服务信誉，并由低到高对其进行排序，从而实现对Web服务的信誉评估；文献[15]基于用户属性的细度化提出了一种信誉度量方法，在不考虑用户身份的前提下，用户可以通过评价其他用户的属性来提高评价的信任度；文献[16]提出了一种新的信誉度量机制，它将用户的序数偏好聚合到信誉中.首先根据序数偏好定义服务之间的优势关系；然后基于服务对的优势关系构造一个有向无环图；最后从图中找出服务的排序.

上述研究虽然从多个方面对在线服务进行了信誉度量，但未考虑到将用户对服务的评分视为用户对服务的分类时用户对服务分类与信誉之间的一致性关系，导致在对分类进行聚合时会出现具有不同类别的聚类结果，聚类效果较差，不符合大部分用户的偏好，降低了服务信誉的稳定性和准确性.另外，如果用户对服务的反馈评分被操纵，则根据用户反馈评分得到的在线服务信誉度量结果也能被轻易改变.考虑到以上研究中存在的不足，本文提出一种基于一致性聚类的在线服务信誉度量方法.该方法是将所有用户对服务的分类结果进行聚类得到服务信誉的一个过程，在该过程中充分考虑了用户对服务的分类与信誉之间的一致性关系，使最终聚类的每个簇中的服务最大程度的相似，而不同簇中的服务相似性最小，从而使在线服务的真实性能得到客观地反映.最后，通过实验验证了本文方法的有效性和客观性.

3 问题描述

本文主要研究如何把所有用户对服务的分类进行聚合，最终形成一个服务聚类，并且使最终聚类获得的服务信誉与所有用户对服务分类之间的一致性达到最大，实现基于一致性聚类的在线服务信誉度量.

3.1 问题定义

为了研究所有用户对服务的分类结果与信誉之间的一致性关系问题，本文给出以下相关定义：

定义1.U={ui|i=1,2，…,m}为用户的有限集，S={sj|j=1,2，…,n}为在线服务的有限集.其中，m表示用户个数，n表示在线服务个数.

定义2.R=[rix]m×n为用户-服务评分矩阵，rix表示第i个用户对第x个在线服务的评分.当rix=riy时，表示用户ui把服务sx和sy归为同一类；当rix=N/A时，表示用户ui未对服务sx进行评分，即用户ui未对服务sx进行分类，即用户对服务的分类可以是不完整的.

定义3.矩阵R中的每行表示用户ui对在线服务集S的分类，用向量ri=(ri1,ri2,…,rin)表示.集合cip={sx∈S|rix=p}表示用户ui把在线服务集S中的服务sx放在等级为p的簇中.集合Ci={ci1,ci2,…,cih}为用户ui把在线服务集S分为h个等级簇的集合.集合C={Ci|,i=1,2,…,m}为所有用户U对服务集S分类中的簇集合.

定义4.将所有用户对服务的分类进行聚合，得到一个最终聚类.最终聚类中的每个簇用集合c*q={sy∈S|q=N}，其中q是经过多数投票后服务sy所在的簇标签，为自然数.最终聚类用集合π*表示，即π*={c*1,c*2,…,c*g}且1≤g≤h.

定义5.由用户对服务的分类得到的最终聚类用π*表示，π*中服务集S的信誉评级用向量rz=(rz1,rz2,…,rzn)表示，rz1,rz2,…,rzn分别表示服务s1,s2,…,sn的信誉级别，且rz1,rz2,…,rzn可由聚类中服务的评分计算获得.

定义6.在线服务分类中的簇间相似性ECS表示在一对服务簇之间服务对象的相似程度[17].其定义如下：

(1)

式(1)中，sim(sx,sy)是在线服务sx和sy在给定所有用户对服务分类C中被分配给相同簇的次数.ECS值越小，表明服务簇cip和cjk之间的相似性越小，分离性越大.

定义7.在线服务分类中的簇内相似性ICS表示在服务簇cip内服务对象的相似程度[17].其定义如下：

(2)

3.2 举例说明

例1.假设有4个用户U={ui|i=1,2，…,4}共同对6个在线服务S={sj|j=1，2，…，6}进行评分，评分矩阵R=[rix]4×6，如表1所示.其中表中的评分表示了用户对服务的满意程度，我们采用电子商务评价机制中常用的1-5的评分等级来表示很不满意、不满意、一般、满意、很满意.rix=N/A表示用户与服务未进行交互.

表1 用户-服务评分矩阵表

Table 1 Ratings matrix of user-service

Rs1s2s3s4s5s6u1112233u2332211u3111222u411N/AN/AN/A2

在本文中，将用户对服务的评分视为用户对服务的分类，即针对同一在线服务集，用户将评分相同的在线服务归为同一类，由此得出所有用户对在线服务的分类.由表1可见，对于6个在线服务，用户u1将服务s1～s6分成3类，即s1和s2、s3和s4、s5和s6.以此类推，u2把服务分成3类，u3把服务分成2类.由于用户不一定对所有服务进行评分，所以用户u4只对服务s1，s2，s6进行了评分，把服务分成2类.上述分类可用图1表示.

图1 多个用户对在线服务的分类

传统的在线服务信誉度量未考虑到用户对服务分类与信誉之间存在的一致性关系问题.例如，通过均值法计算用户对服务评分的平均值得到的信誉向量为ravg=(1.5，1.5，1.67，2，2，2).从ravg中可看出服务s1～s6被分成3类，且认为s4，s5，s6属于同一类.然而表1中所有用户对服务s4，s5，s6的评分不相同，认为s4与s5，s6不在同一类别中.使用均值法会使原本不在同一类别的服务被分到相同类别中，导致最终得到的信誉与所有用户对服务分类之间的不一致性较大，缺乏合理性.此外，如果将用户u1对服务s6的评分降低至1分，则发现通过均值法计算服务s6的信誉降低至1.5分，且其他服务的信誉未发生改变，这大大降低了服务s6的信誉等级，使其具有较差的抗操纵性.因此，本文提出了一种基于一致性聚类的在线服务信誉度量方法，有效地避免了因未考虑用户对服务分类与信誉之间的一致性关系导致的在线服务信誉等级划分不合理的问题，同时还提高了方法的抗操纵性.

4 基于一致性聚类的服务信誉度量

由于目前的在线服务信誉度量方法均未考虑到信誉结果与用户对服务分类之间的一致性关系，导致通过用户-服务评分计算得到的服务信誉准确性较低.因此，本文提出了一种基于一致性聚类的在线服务信誉度量方法.方法将用户对服务的评分视为用户对服务的分类，根据在线服务中的簇内和簇间相似性建立基于相似性的最小成本生成树(Similarity-based Minimum-cost Spanning Tree，SMST)[18]，从具有最小权重值的边开始，对SMST进行切割产生多种可能的聚类.然后通过一致性质量函数[19]来搜索所有可能的聚类以找到具有更好整体质量的最终聚类π*，使最终聚类π*拥有紧凑性最强和分离性最大的簇.

定义8.一致性质量函数.本文中用一致性质量函数φ来评价聚类πi的好与坏.定义如下：

(3)

(4)

其中，listmax是得到的一列值中的最大值，listmin是得到的一列值中的最小值.运用公式(4)，通过变换在[0，1]范围内所有用户对服务分类中的ICS和ECS值，减少了在计算簇内和簇间相似性的过程中大值和小值对计算结果的不利影响.

获得的最终聚类π*的一致性质量函数φ必须满足：

(5)

从式(5)可以看出聚类π*拥有最好的整体质量，使最终聚类π*中的簇内相似性最大，簇间相似性最小.其服务信誉度量结果相对于所有用户对服务分类的结果来说尽可能多地一致.

4.1 基于位向量的在线服务簇表示

本文采用的一致性聚类方法在聚合所有用户对服务的分类形成一个最终聚类的过程中，考虑到随着互联网的快速发展，在线服务数量不断增加，将导致在计算所有用户对服务分类之间的簇内和簇间相似性时需要占用很大的存储空间.因此，为了节省空间用由二进制组成的的位向量来存储在线服务中的每个簇[17].其中，每个簇中服务的存在由1表示，服务的缺失由0表示.每个用户对在线服务的分类表示与在线服务集|S|的大小一样长.

为了应对具有不同数量的在线服务分类，我们利用投票机制来组合分类结果，从而引出服务之间相似性的新度量[20].考虑到不同服务很可能共同存在于不同服务分类中的同一簇中，因此将同一簇中服务对的同时出现作为其关联的投票.在获得用户对服务分类的基础上，通过统计不同服务在所有用户对服务分类中被分配给相同簇中的次数得出共同关联矩阵(Co-association Matrix，SM)，并基于SM计算所有用户对服务分类中的簇间和簇内相似性.

定义9.共同关联矩阵为SM=[smxy]n×n，smxy表示服务sx和sy被分配给相同簇的次数.则：

smxy=votesxy/m

(6)

式(6)中，m为用户数量，votesxy是服务对(sx，sy)被分配给所有用户对服务分类中的相同簇的次数，即sx∈S，sy∈S.然后将分类中服务对同时出现在相同簇中的次数映射到|S|×|S|的共同关联矩阵中.最后根据得到的SM进一步计算在线服务中的簇间相似性和簇内相似性.

4.2 簇间和簇内相似性计算

在对获得的所有用户对在线服务分类进行聚合时，考虑到不同服务在分类中的相似程度不同，可以运用两个非常著名的无监督客观测量指标：簇间相似性和簇内相似性来实现对分类中的在线服务进行簇间和簇内相似性计算.在根据公式(1)和公式(2)进行相似性计算时，需要知道服务sx和sy同时出现在相同簇中的次数sim(sx，sy).由于本文中是运用SM来统计分类中服务sx和sy同时出现在相同簇中的次数，因此sim(sx，sy)=smxy.则在线服务分类中的簇间相似性计算如下：

(7)

在线服务分类中的簇内相似性计算如下：

(8)

根据例1中给出的在线服务分类，分别运用公式(7)和公式(8)计算分类中的ECS和ICS.由于ECS的计算是利用服务对象级别的信息来提供非常准确的分类级别信息，所以此时得到的ECS值非常有效.

由于本文中的信誉度量是将所有用户对服务的分类进行聚合得到一个聚类的过程，所以可以将在线服务分类中的ECS和ICS扩展为聚类πi的簇间相似性和簇内相似性.

定义10.聚类πi的簇间相似性定义如下：

(9)

定义11.聚类πi的簇内相似性定义如下：

(10)

式(10)中，ICSC(πi)值越大，表示πi的簇越紧凑.

4.3 基于用户对服务分类与信誉之间的一致性寻找最终聚类

为了使用户对服务分类结果与信誉之间的一致性达到最大，我们需要寻找具有紧凑且分离良好的簇的最终聚类.本文方法在不输入任何参数的情况下，以最小生成树的形式组织所有用户对服务的分类来处理分类聚合问题，因为它不仅可以保留原始的所有用户对服务的分类信息，而且是稀疏图，处理复杂度低.对于获得的SMST，它有d-1条边和最多d个不同的簇，其中d是输入的所有用户对服务分类中的总簇数.然后从SMST中具有权重值最小的边开始对其进行切割产生多种可能的聚类[21].为了从多个可能的聚类中获得拥有簇内相似性最大和簇间相似性最小的最终聚类π*，则必须找到一个一致性质量函数φ(πi)，使其满足公式(5)，用于确定具有更好整体质量的最终聚类π*.本文方法虽然不能保证产生的最终聚类是全局最优的，但通过实验结果表明采用本文中的算法产生的最终聚类较好.

本文方法中的最小成本生成树是由无向加权图G获得的.首先，根据SM获得服务分类中的簇间和簇内相似性；其次，用无向加权图G表示输入的所有用户对服务分类之间的关系.在图G中，每个顶点V代表所有用户对服务分类中的一个簇，每条边E代表分类中簇之间的关系，每条边上的权重W代表所有用户对服务分类中相应簇之间的ECS值.其定义如下：

定义12.G=(E，V，W)为无向加权图.其中E={(cip，cjk)|(cip，cjk)∈C}为图G中无向边集合，V={cip|cip∈Ci}为图G的顶点集合，W={ECS(cip，cjk)|(cip，cjk)∈C}为V的权重集合.

然后在图G上运行普里姆(Prim)算法[22]，考虑到边缘顶点之间的差异性和边缘权重值W具有反比关系，因此在图G上运行普里姆(Prim)算法时，以图中的某一顶点为起点，逐步寻找与之相连的各顶点之间拥有高相似度即最大权重值W的边，通过使用高相似度值表示低差异性成本来构建SMST.最后，基于SMST来寻找最终聚类.本文的一致性聚类算法如算法1.

算法1.一致性聚类算法

输入：输入所有用户对在线服务的分类U

输出：最终聚类π*

1.G：=(E，V，W); //初始化加权图

2.V：= Ø; //顶点集

3.E：= Ø; //边缘集

4.W：= Ø，W⊆E→; //边缘权重函数

5.FOR ALLCi∈CDO

6.FOR ALLcip∈CiDO

7.V=V∪cip;

8.FOR ALLcip∈VDO

9. FOR ALLcjk∈V，i≠j，p≠kDO

10.E：=E∪(cip，cjk);

11.W：=W∪(E，ECS(cip，cjk));//边缘顶点之间的差异性和W值具有反比关系

12.SMST:=Prim′s_Algorithm(G);

13.π*:=find_final_clustering(SMST);

14.RETURNπ*;

本文采用的一致性聚类算法的核心是寻找最终聚类的过程.对于获得的SMST，从SMST上具有权重值最小的边开始对其进行切割并产生元聚类，每个元聚类都是树的连通分量.为了在切割SMST产生的多个聚类中找到最终聚类π*，下面给出了寻找最终聚类过程的算法，如算法2.

算法2.寻找最终聚类

输入：基于相似度的最小成本生成树(SMST)

输出：簇号h

1.初始化空列表：ics，ecs，nics，necs，φ，π;

2.h：= 0; //存储边缘的编号

3.REPEAT

4.h:=h+1;

5. 从SMST中删除最小加权边

6.πMC是SMST的元聚类，每一个连接组件都是元聚类;

7.πh:=majority_voting(πMC);//多数投票

8.icsh:=ICSC(πh);

9.ecsh:=ECSC(πh);

10.UNTILSMST中有一些边;

11.nics:=normalize(ics);

12.necs:=normalize(ecs);

13.FORi= 1 tohDO

14.φi:=icsi-ecsi;

15.max_index:=maxi(φ);

16.RETURNπmax_index;

由算法2可知，在SMST中每切割一次SMST，相连接的服务簇之间会变得彼此更相似，使该聚类中的服务在所有用户对服务分类中共同存在同一类中多次.然后，在聚类上执行多数投票表决[23]，统计服务出现在每个类别中的次数，每个在线服务仅分配给最常存在的一个类别，以产生非重叠的最终聚类，提高了聚类的服务信誉级别划分的合理性.最后，对每次切割产生的聚类运用公式(3)计算其一致性质量函数φ(πi)，再根据公式(5)来寻找具有紧凑且良好分离的簇的最终聚类π*.

从具有权重值最小的边开始对SMST进行切割，每切割一次产生的聚类运用公式(3)对其进行一致性质量函数计算.在进行ICSC(πi)和ECSC(πi)计算时，为了减少在计算过程中产生的大值和小值对聚类结果准确度的影响，我们运用公式(4)对其进行归一化处理.具体过程如算法3.

算法3.归一化处理

输入：值列表list

输出：规范化列表normalized_list

1.max:=max(list);

2.min:=min(list);

3.normalized_list:=initialize empty list;//初始化空列表

4.FORi:=start_of(list)toend_of(list)DO

6.RETURNnormalized_list;

本文采用的一致性聚类算法在通过切割SMST寻找最终聚类的过程中需要运行h次.然后在每次计算一致性聚类函数寻找最终聚类的时间复杂度为O(|πi||C|+|πi|2|C|).因此，在运用一致性聚类算法聚合所有用户对服务的分类得到最终聚类的总体时间复杂度为O(h(|πi||C|+|πi|2|C|)).其中|πi|表示聚类πi中簇的个数，|C|表示所有用户U对服务集S分类的总簇数，且在大多数情况下|πi|2≪|S|，|C|≪|S|.

4.4 基于最终聚类的信誉度量

根据用户对服务的分类与信誉之间的一致性关系获得最终聚类π*，然后对π*进行信誉计算，进而得到服务集S的信誉等级rz=(rz1，rz2，…，rzn).

首先，根据最终聚类π*计算聚类中每个簇c*q内所有用户对服务sx评分的平均值avgx，avgx=(r1x+r2x+…+rmx)/m，接着将其簇内所有服务的平均值进行累加再求取平均值作为该簇的信誉值l*q，l*q=(avg1+avg2+…+avgn)/n.然后求出其余每个簇的信誉值，并对聚类π*中所有簇的信誉值L*=(l*1，l*2，…，l*g)进行比较大小，把信誉值最小的簇的簇号赋值为1，即该簇的信誉等级为1.以此类推，聚类中的每个簇都被赋予相应的信誉等级.最后，输出最终聚类中每个在线服务的信誉等级rz=(rz1，rz2，…，rzn).

图2 在线服务的最终聚类

例1中，通过计算得到的最终聚类为π*={c*1，c*2，c*3}，如图2所示.π*中在线服务s1，s2，s3，s4，s5，s6的信誉等级为rz=(1，1，2，2，3，3).因此最终聚类π*的信誉结果最大程度上符合所有用户对服务的分类C的结果，使最终聚类的服务信誉与所有用户对服务分类之间的一致性最大.

5 实验结果与分析

针对以上提出的基于一致性聚类的在线服务信誉度量方法，本部分设计实现了该信誉度量方法并展示了实验结果，以测试该方法的有效性和效率.

1https：//grouplens.org/datasets/movielens/

5.1 实验环境及数据集

本文方法的开发语言为Java，它提供了对位向量的内置支持以及对位向量的操作.实验采用Java语言的JDK 1.8软件开发工具包实现，在一台配置为Intel Core i5 3.3GHz CPU、8GB RAM的PC机上运行，操作系统为 Windows 10 专业版.

由于本文方法是基于用户-服务评分值，所以为了更加真实地反应实验结果，本文实验采用的数据集为MovieLens1数据集，目前MovieLens数据集被广泛应用于与服务相关的研究领域.该数据集包含电影1682部，943名用户以及10万条左右的用户对服务的真实评分(1～5)，每个用户参与的电影评分不得少于20部.考虑到用户不可能参与所有电影的评分，为确保信誉等级划分的合理性，如果用户对服务的分类少于两类，实验时不将这个用户对服务的分类加入到聚类中.本文将现在比较流行的3种在线服务信誉度量方法：平均(Average)法、累加(Sum)法以及Beta信誉系统方法[11]作为主要对比方法.实验验证了信誉度量结果的合理性和有效性.

5.2 评价标准

本文将基于一致性聚类的在线服务信誉度量问题视为基于用户对不同服务信誉类别的服务分类的聚类问题，可通过聚类有效性度量来进行最终聚类的质量评估.由于将每个用户对服务集S的评分视为服务具有的真实类标签，因此使用最常用的监督评估方法之一：调整后的兰德指数(Adjusted Rand Index，ARI)[24]即兰德指数(Rand Index，RI)的改进版本来进行聚类质量评估.本文使用ARI来测量由聚合服务分类得到的最终聚类的信誉结果与所有用户对服务分类之间的匹配程度，ARI值越大，表明它们之间的匹配程度越大，即聚类结果与用户对服务的分类结果越吻合，聚类效果越好.因此将具有最大ARI值对应的最终聚类的信誉向量作为服务信誉是合理的.所以，我们用ARI的大小来验证方法的有效性.具体定义如下：

(11)

ARIi取值范围为[-1，1]，值越大意味着聚类结果与用户对服务的分类结果越匹配，聚类效果越好.当ARIi最大取值为1时，表示用户ui对服务集S的分类Ci与经过聚合分类得到的最终聚类π*之间完全匹配，聚类效果最好；当ARIi为-1时，表示用户ui对服务集S的分类Ci与最终聚类π*之间完全独立，聚类效果最差.

本文中聚合服务分类得到的最终聚类π*与所有用户U对服务集S的分类C之间的匹配程度用ARI*表示，则：

ARI*=ARI1+ARI2+…+ARIm

(12)

此时，ARI*取值范围为[-m，m].同样，ARI*值越大意味着最终聚类的信誉度量结果与所有用户对服务的分类结果越吻合，聚类效果越佳.

表2 ARI列联表

Table 2 Abbreviations for ARI

ClassClusterc∗1c∗2…c∗QSumsci1n11n12…n1Qn1·ci2n21n22…n2Qn2·︙︙︙︙ciPnP1nP2…nPQnP·Sumsn·1n·2n·Qn··=n

5.3 有效性实验

观察公式(12)可知，所有用户对服务分类与最终聚类的信誉之间的ARI值越大，表示最终聚类的信誉与所有用户对服务的分类结果匹配度越大，聚类效果越好，得到的信誉度量结果越合理.实验模拟了在不同用户数量m(100≤m≤500)和不同服务数量n(10≤n≤50)下，记录本文方法得到的最终聚类的信誉向量rz、平均法的信誉向量ravg、累加法的信誉向量rsum、Beta法的信誉向量rbeta与所有用户对服务分类之间的ARI，分别用ARI*，ARIavg，ARIsum，ARIbeta表示，如图3所示.

图3 一致性验证

由图3(a)可见，随着用户数量和服务数量的增加，ARI*越来越大.说明服务和用户数量越大，通过本文方法聚合分类得到的聚类结果与用户对服务分类之间的匹配程度越高，使得到的最终聚类的信誉向量rz与所有用户对服务分类之间的一致性越大.

由图3(b)、图3(c)和图3(d)可见，ARIavg、ARIsum和ARIbeta并不都随着用户数量和服务数量的增加而增加.说明通过平均法、累加法和Beta法得到的信誉度量结果与所有用户对服务分类之间的匹配度较低，使信誉向量ravg，rsum和rbeta与所有用户对服务分类之间的不一致性较大.

此外，算法比较记录了在不同服务数量和用户样本规模下ARI*，ARIavg的差值、ARI*，ARIsum的差值以及ARI*，ARIbeta的差值，ARI*-ARIavg如图4(a)所示，ARI*-ARIsum如图4(b)所示，ARI*-ARIbeta的如图4(c)所示.

图4 信誉度量方法一致性比较

由图4(a)、图4(b)和图4(c)可见，在同样的服务数量和用户规模下，ARI*-ARIavg、ARI*-ARIsum和ARI*-ARIbeta的值始终大于0，即ARI*始终大于ARIavg、ARIsum和ARIbeta.虽然随着服务数量和用户规模的增大，ARI*与ARIavg、ARIsum、ARIbeta之间的差值在不断缩小，但始终位于0之上.说明本方法与其他三种方法相比得到最终聚类的信誉向量与所有用户对服务分类之间的ARI*最大，由此获得的信誉度量结果与所有用户对服务分类之间的一致性最大，得到的服务信誉较为合理.

5.4 操纵复杂性验证

对于随机选取的某服务，通过对其增加高评分或低评分的用户数量来进行服务评分操纵，若根据本文方法得到的服务信誉级别无明显变化，则通过该方法得到的信誉结果抗操纵性较强.为此，随机选取两个在线服务s1和s2，用户数量为500.我们选取不同比例的用户对服务进行评分操纵，分别为20%，40%，60%，80%，100%.通过分别提高s1的评分至5分和降低s2的评分至1分来观察这两个服务的信誉级别变化.Sum法、Average法、Beta法、本文方法分别计算在增加不同操纵用户比例时在线服务s1和s2的信誉级别，结果分别如图5(a)和图5(b)所示.

图5 抗操纵性能验证

根据图5(a)所示，随着操纵用户比例的增加，Average法、Sum法和Beta法中服务s1的信誉级别在不断地提高，而根据本文方法得到的服务s1的信誉级别一直保持不变，只有当操纵用户比例达到100%时，服务s1的信誉级别才提高.说明要对本方法中服务s1的信誉级别进行操纵需要消耗大量成本.

根据图5(b)所示，随着操纵评分数量的增加，Average法、Sum法和Beta法中服务s2的信誉级别在不断地降低，而根据本文方法得到的服务s2的信誉级别在操纵用户比例达到60%之前一直保持不变；然后当操纵用户比例达到80%时，服务s2的信誉级别降低；最后随着操纵用户比例的增加直到100%时，服务s2的信誉级别稳定不变.由此可以看出，本文方法得到的信誉度量结果具有更好的抗操纵性.

5.5 性能验证

为了测试方法的运行效率，实验模拟了m(100≤m≤500)个用户和n(10≤n≤50)个在线服务分别在不同用户数量和服务样本规模下进行信誉度量的实验，并且记录了每次实验的运行时间，如图6所示.此外，还比较了本方法、Average法、Sum法、Beta法在用户数量为500和服务数量为10～50的规模下的运行时间，如表3所示.

图6 不同用户数量和服务规模下的运行时间

观察图6可知，方法的运行时间会随着用户数量的增加而不断增加，原因是在服务数量一定时，计算用户对服务分类中的ECS和ICS的次数会随用户数量的增加而增加，导致根据公式(3)和公式(4)计算得到最终聚类的信誉度量结果的运行时间增加.但是在用户数量一定时，运行时间并不随服务数量的增加而增加，是因为在计算簇间和簇内相似性时，运行时间只与每对服务出现在相同簇中的次数有关，与服务数量无关.所以本文方法可通过控制用户数量来有效地提升信誉度量的效率.

表3 不同服务数量在不同方法下的运行时间(单位：秒)

Table 3 Runtime of different services in different methods(unit：seconds)

1020304050本文方法30294288813571156Average0.1720.2840.3280.5150.547Sum0.1560.2180.2800.4370.468Beta0.2170.3310.4480.5460.609

从表3可知，相对Average法、Sum法和Beta法的运行时间而言，本文方法虽然运行时间较长，但通过操纵该方法获得在线服务信誉度量结果所需的时间要比其他3种方法更长.因此，对本文方法获得的信誉度量结果进行操纵的难度要远高于其他三种方法.

6 结 论

本文提出一种基于一致性聚类的在线服务信誉度量方法，以解决由于未考虑到用户对服务的分类结果与信誉之间的一致性关系导致的最终聚类的服务信誉级别划分不合理的问题.方法在切割基于相似性的最小成本生成树时，会产生多种可能的聚类.然后用一致性质量函数来寻找具有更好整体质量的最终聚类，使其簇内的相似性最大，簇间的差异性最大，聚类效果较好.最后基于得到的最终聚类计算其服务信誉，使用户对服务分类与信誉结果之间的一致性达到最大，提供了一种研究在线服务信誉度量方法的新思路.同时，实验也验证了本文方法在进行服务分类聚合时具有较高的的有效性.

本文方法在进行聚类过程中只考虑了用户对在线服务的评分，未综合考虑其他因素在聚类过程中对在线服务信誉的影响.因此，下一步将从该方面研究一种使信誉等级划分更准确的在线服务信誉度量方法.