, 李俊1, 刘骊1, 岳昆3, 冯勇1, 刘利军1 1. 昆明理工大学 信息工程与自动化学院, 云南省计算机技术应用重点实验室, 昆明 650500;
2. 昆明理工大学 航空学院, 昆明 650500;
3. 云南大学信息学院, 昆明 650091
收稿日期：2018-04-08
基金项目：国家自然科学基金地区项目（61462056，61462051，81560296，61662042）；国家自然科学基金面上项目（61472345）；云南省应用基础研究计划项目（2014FA028）
作者简介：付晓东(1975-), 男, 教授, E-mail:xiaodong_fu@hotmail.com
摘要：不同用户具有不同的评价准则，导致不同用户对同一在线服务的评分不具可比性，使聚合服务评分得到的在线服务评价结果难以真实反映服务之间的优劣关系。为此，该文提出一种基于排序对（ranked pairs）社会选择函数的在线服务评价方法，根据用户对在线服务的偏好关系而不是传统评分计算在线服务评价结果。首先根据用户-服务评分矩阵获得每个用户对在线服务的偏好关系；然后基于多数准则确定服务优先关系，并根据服务优先关系建立服务对排序列表；最后构造以服务为节点的有向无环图，并在该有向无环图中寻找一条包含所有服务的路径，根据该路径的服务排序计算在线服务评价值。理论分析和实验结果验证了该方法的合理性和有效性。
关键词：在线服务评价不可比较评分排序对服务排序
Evaluating online services based on a ranked pairs social choice function
FU Xiaodong1,2
, LI Jun1, LIU Li1, YUE Kun3, FENG Yong1, LIU Lijun11.Yunnan Provincial Key Laboratory of Computer Technology Application, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China;
2.Faculty of Aeronautics, Kunming University of Science and Technology, Kunming 650500, China;
3.School of Information Science and Engineering, Yunnan University, Kunming 650091, China
Abstract: Different customers may have different evaluation criteria which leads to different ratings of online services. Thus, aggregation of the ratings cannot objectively evaluate the services. This paper presents an online services evaluation method based on a ranked pairs social choice function. The method uses preference relations rather than ratings to evaluate the online services. First, the preference relations of the customer are calculated based on a ratings matrix. Then, a list of online service pairs is established according to the service priority relationship determined from the majority rule. Finally, a directed acyclic graph is constructed and a path is found in the graph that contains all the online services. The service order in the path is then used to evaluate the services. A theoretical analysis and tests verify the reasonability and effectiveness of this method.
Key words: online services evaluationincomparable ratingsranked pairsservice ranking
在线服务是指利用互联网技术，向用户提供线上服务的方式。近些年，随着互联网的发展，在线服务规模显著增长，涵盖了网络搜索引擎、新闻门户网站、电子商务、Web服务等诸多领域[1]。因此，用户可以越来越方便地使用满足自身需求的在线服务。但是，由于越来越多的服务提供者将其服务发布到互联网上，使得在线服务数量和种类剧增，出现了许多具有相同功能的在线服务[2]。另外，由于受利益化的市场竞争的影响，不能保证服务提供者发布的服务是客观、真实、可信的[3]，导致用户在选择最适合自身需求的在线服务时需要反复进行搜索、比较，浪费大量时间。
用户与在线服务产生交互后往往会对该服务进行反馈评价来表明自己的满意程度，这些反馈评价能够帮助潜在用户更好地选择在线服务[4]。为此，在线服务提供平台为了提供更好的用户体验，为用户提供了多种基于第三方评价形成的在线服务排名方法来衡量在线服务的性能，进而辅助用户选择适合自身需求的在线服务。例如，电商平台、外卖平台、网约车平台等提供了多种服务排名方法如综合排名、销量排名、信用排名、价格排名、上架时间排名等，用户在选择在线服务的时候很大程度上会参考这些方法得到的排名结果。服务排名是一种基于服务性能对在线服务进行评价的方法，一种客观有效的在线服务评价方法能够辅助用户更好地选择在线服务。
目前采用的在线服务评价方法主要有累加法、平均值法、Beta信誉法、概率法、模糊法等[5-6]。上述方法基于假设所有用户具有相同的评价准则得到在线服务评价结果[7]。然而，不同用户与在线服务交互时具有不同的心理和偏好，有的用户注重在线服务的质量，有的用户注重与在线服务的交互体验。相同在线服务由于用户评价准则不一致得到不同的评分，导致不同用户对同一在线服务评分不具备公平的可比较性。另外，现有评价方法根据在线服务评分得到在线服务评价结果可能会出现有些服务提供者为了增加其所提供服务被选择的机会，给自身服务刷好评或者诋毁其他服务提供者所提供的服务，导致用户面临难以选择其真正需要的在线服务的风险[8]。
为了解决上述问题，本文提出了一种基于排序对(ranked pairs)社会选择函数[9]的在线服务评价方法，方法不假设不同用户具有完全一致的评价准则，根据用户对不同在线服务之间的偏好关系而不是传统的评分得到在线服务评价结果，能有效解决不同用户具有不同的评价准则导致不同用户对同一在线服务评分不可比较的问题。本文还通过理论分析和实验验证了该方法的有效性和合理性。
1 相关工作近年来，大量的研究工作围绕用户对在线服务的评价信息来判断在线服务之间优劣关系展开。评价信息是用户与在线服务产生交互后所产生的一种主观感受，是用户对在线服务满意程度的体现。服务评价信息主要分为文本型评价和数值型评分[10]。
基于文本型评价，文[11]提出了一种基于评论语言特征和支持回归向量的在线评价排序方法，从而帮助用户更好地了解评论的质量；文[12]提出一种评价方法，根据用户对在线服务的评论识别在线服务的特性，然后对每个服务特性分别进行评分，在用户指定某个服务特性进行排序时，该方法通过该特性评分将在线服务进行排序显示给用户；文[13]针对文本评论的各种评价因素进行量化评价，提出一种利用灰色评估理论分析用户情感满意度的评价方法，该方法通过引用相似性情感词匹配词对和对象对应服务的对应性热点词匹配词来构建用户对在线服务的满意度评测指标，能有效解决定性评价方法的不足，为用户选择在线服务提供更好的参考依据。随着在线服务规模的扩大，越来越多的评价信息让用户无法快速地从中选择对自己有用的服务评价，上述方法分别从评论质量、评论特性、评论情感对在线服务评论进行分析，让用户能够快速地选取对自己有用的评论，从而为自己选择高质量的在线服务提供更好的参考依据。
基于数值型评分，文[5]指出目前常用的评价方法有累加法与平均值法。累加法将某个在线服务得到的所有反馈评分进行累加，然后将得到的累加值作为该服务的总体信任度。易贝(eBay)和淘宝(Taobao)的评价方法基于累加法。平均值法首先将某个在线服务获得的所有反馈评分进行累加，然后除以评分次数，将所得结果作为该服务的总体信任度。亚马逊(Amazon)和天猫(Tmall)的评价方法基于平均值法。文[14]指出针对在线服务数值型评分的预测方法有加权平均值和中心加权平均值统计方法，其中加权平均值考虑当前用户基于邻居用户之间的相似性，对于与当前用户更为相似的用户在预测中给予更大的推荐权重，否则给予较小的推荐权重；中心加权平均值通过考虑不同用户的评分值、加权评分值与该用户平均评分之间的差值，从而得到预测结果的方法。文[15]提出了一种Beta信誉计算方法，该方法基于统计学理论，通过结合β概率密度函数和用户反馈评分得到在线服务评价结果。上述方法得到在线服务评价结果计算原理简单，可以快速地得到评价结果。
上述研究对在线服务进行评价时均假设不同用户对在线服务具有相同的评价准则[7]。然而，在开放的网络环境中，由于交互背景、交互心理等因素的影响，不同用户不可能具有完全一致的评价准则。因此，上述在线服务评价方法中所使用的评价信息其实是不可比较的，从而导致方法得到的在线服务评价结果难以真实反映不同服务之间的优劣关系。另外，如果在线服务评价信息被操纵，则根据用户评价值得到的在线服务评价结果也能被轻易改变。考虑上述研究中存在的不足，本文基于社会选择理论[16]的思想，在不假设不同用户评价准则一致的情况下，将同一用户对不同在线服务的评价转换成该用户对不同服务之间的偏好关系，然后利用社会选择函数分析用户个人偏好与用户集体偏好之间的关系，从而得到在线服务评价结果。
2 基于排序对的在线服务评价不同用户对同一在线服务评分不可比较使得不能简单地根据用户对在线服务的评分值大小判断不同服务之间的优劣关系。社会选择理论[16]认为在评价准则不一致时，考虑不同评价者对评价对象的偏好强度信息毫无意义。考虑到同一用户通常具有比较稳定的评价准则，因此可以根据用户对不同在线服务的评分判断该用户对不同服务之间的偏好关系。这样，就可以将不同偏好准则下用户对不同在线服务评分通过两两比较得到该用户对不同服务之间的偏好关系[17]，然后通过社会选择理论集结所有用户的偏好关系形成群体评价。
社会选择函数是将个人偏好关系集结为集体偏好的规则[18]。排序对是社会选择函数中唯一同时满足孔多赛(Condorcet)性、非负性、匿名性以及中立性的社会选择函数[19]。因此，本文利用排序对社会选择函数将用户偏好关系集结为用户集体对全部在线服务的整体偏好序列，得到在线服务评价结果。
2.1 问题定义为了研究用户评价准则不一致的在线服务评价问题，本文对在线服务评价问题定义如下：
定义1??用户集合为U={u1, u2, …, um}, 在线服务集合为P={p1, p2, …, pn}。其中, m表示用户人数, n表示在线服务数量。
定义2??用户-服务评分矩阵R=[rij]m×n。其中, rij表示用户ui对在线服务pj的评分, rij取值范围为1~5分, 若R中存在rij=0则表示用户ui未对在线服务pj进行评分。
定义3??在线服务整体排序O=(oq|q=1, 2, …, n)。其中, oq为第q个服务的评价值。oq > oh表示第q个服务在所有服务中的排序优于第h个在线服务。
本文针对用户评价准则不一致, 以不同评价准则下用户对在线服务的评分为基础, 首先获取用户对不同服务之间的偏好关系；然后确定不同服务之间的优先关系；最后通过排序对社会选择函数分析用户个人偏好与用户集体偏好之间的关系。这样, 得到的在线服务评价结果符合所有用户的偏好。
2.2 用户对在线服务偏好关系获取在线服务规模庞大, 用户一般都只对很少的在线服务进行评分, 造成整个用户-服务评分矩阵十分稀疏[20]。由于需要比较用户对不同服务的评分得到该用户对不同服务之间的偏好关系, 需要将用户-服务评分矩阵填充完整。为此, 利用协同过滤推荐方法[21-22]将用户-服务评分矩阵R填充完整, 然后通过两两比较R中用户对不同在线服务评分值大小, 得到该用户对不同在线服务之间的偏好关系, 并建立每个用户对在线服务的偏好关系矩阵。
定义4??用户-服务偏好关系矩阵Prei=[prexy]n×n(i=1, 2, …, m; x, y=1, 2, …, n; x≠y), 其中：
| $\text{pr}{{\text{e}}_{xy}}=\left\{ \begin{array}{*{35}{l}} 1,&{{r}_{ix}}>{{r}_{iy~}}; \\ 0,&{{r}_{ix}}={{r}_{iy}}; \\ -1,&{{r}_{ix}}<{{r}_{iy~}}. \\\end{array} \right.$ | (1) |
根据每个用户的偏好关系矩阵Prei, 分别统计m个用户中prexy=1的用户人数以及prexy=-1的用户人数, 然后基于多数准则确定当服务px和py成对比较时服务对(px, py)中的优先服务：
| $\left\{ \begin{align} &{{p}_{x}}\succ {{p}_{y}}, \sum\limits_{i=1}^{m}{(\text{pr}{{\text{e}}_{xy}}=1)>\sum\limits_{i=1}^{m}{(\text{pr}{{\text{e}}_{xy}}=-1);}} \\ &{{p}_{x}}\sim {{p}_{y}}, \text{ }\sum\limits_{i=1}^{m}{(\text{pr}{{\text{e}}_{xy}}=1)=\sum\limits_{i=1}^{m}{(\text{pr}{{\text{e}}_{xy}}=-1);}} \\ &{{p}_{x}}\prec {{p}_{y}}, \text{ }\sum\limits_{i=1}^{m}{(\text{pr}{{\text{e}}_{xy}}=1)<\sum\limits_{i=1}^{m}{(\text{pr}{{\text{e}}_{xy}}=-1).}} \\ \end{align} \right.$ | (2) |
得到每个服务对中不同在线服务之间的优先关系后, 建立服务-服务比较矩阵记录所有服务对中支持优先服务的用户及不支持优先服务的用户人数。
定义5??服务-服务比较矩阵CM=[cmxy]n×n(x, y=1, 2, …, n; x≠y)。其中：
| $\left\{ \begin{align} &\text{c}{{\text{m}}_{xy}}=\sum\limits_{i=1}^{m}{(\text{pr}{{\text{e}}_{xy}}=1)>0} \\ &且\text{c}{{\text{m}}_{yx}}=-\sum\limits_{i=1}^{m}{(\text{pr}{{\text{e}}_{xy}}=-1)<0, \ {{p}_{x}}\succ {{p}_{y}};}\text{ } \\ &\text{c}{{\text{m}}_{xy}}=\text{c}{{\text{m}}_{yx}}=\mathit{?} , ~{{p}_{x}}\tilde{\ }{{p}_{y}}; \\ &\text{c}{{\text{m}}_{yx}}=\sum\limits_{i=1}^{m}{(\text{pr}{{\text{e}}_{xy}}=-1)>0\text{ }} \\ &且\text{c}{{\text{m}}_{xy}}=-\sum\limits_{i=1}^{m}{(\text{pr}{{\text{e}}_{xy}}=1)\text{ }<0, ~{{p}_{y}}\succ ~{{p}_{x}}.} \\ \end{align} \right.$ | (3) |
 |
| 图 1 算法1 |
| 图选项 |
利用算法1得到CM后, 根据CM中每个服务对中支持优先服务的用户人数大小关系来对服务对进行排序。
2.3 在线服务排序定义6??服务对排序列表Listxy用来记录矩阵CM中服务对排序结果, 其中：
| $\left\{ \begin{align} &({{p}_{i}}, ~{{p}_{k}})\succ ({{p}_{i}}, ~{{p}_{j}}), \text{ c}{{\text{m}}_{pi, \text{ }pk}}>\text{c}{{\text{m}}_{pi, \ pj}};\text{ } \\ &({{p}_{i}}, ~{{p}_{k}})\prec ({{p}_{i}}, ~{{p}_{j}}), \ \text{c}{{\text{m}}_{pi, \ pk}}<\text{c}{{\text{m}}_{pi, \ pj}}. \\ \end{align} \right.$ | (4) |
| $\left\{ \begin{align} &({{p}_{i}}, ~{{p}_{k}})\succ ({{p}_{i}}, ~{{p}_{j}}), |\text{c}{{\text{m}}_{pk, \ pi}}\left| < \right|\text{c}{{\text{m}}_{pj, \ pi}}|;\text{ } \\ &({{p}_{i}}, ~{{p}_{k}})\sim ({{p}_{i}}, ~{{p}_{j}}), |\text{c}{{\text{m}}_{pk, \ pi}}\left| = \right|\text{c}{{\text{m}}_{pj, \ pi}}|;\text{ } \\ &({{p}_{i}}, ~{{p}_{k}})\prec ({{p}_{i}}, ~{{p}_{j}}), |\text{c}{{\text{m}}_{pk, \text{ }pi}}\left| > \right|\text{c}{{\text{m}}_{pj, \text{ }pi}}|. \\ \end{align} \right.$ | (5) |
 |
| 图 2 算法2 |
| 图选项 |
在得到列表Listxy后根据列表中服务对排列顺序建立以服务为节点的有向无环图, 然后根据有向无环图计算在线服务评价结果。
定义7??G=＜V, E＞为有向无环图。其中V=P={p1, p2, …, pn}为图G节点集合, E={＜ps, pe＞|(ps, pe)∈Listxy}为图G有向边集合。
在这里, 按顺序将服务对排序列表Listxy中服务对(ps, pe)∈Listxy作为从节点ps指向pe的有向边添加到图G有向边集E, 同时将节点ps、pe添加到图G节点集合V中。在构造有向无环图G时, 如果图G中已经存在一条从节点pe到ps的路径, 在添加有向边＜ps, pe＞后图G中将形成环路pe- > ps- > pe, 此时, 删除添加后使G形成环路的有向边＜ps, pe＞。重复上述步骤, 直到将列表Listxy中全部服务对作为有向边添加到图G有向边集E中为止。基于深度优先[23]的思想, 根据排序列表Listxy建立以服务为节点的有向无环图G的算法3如图 3所示。
 |
| 图 3 算法3 |
| 图选项 |
在建立有向无环图G后, 从图G中寻找一条包含全部在线服务p1到pn的最优路径：依次在图G中寻找入度为0的节点, 找到后将该节点添加到在线服务偏好序列中并且从图G节点集合V中删除该节点, 同时从有向边集E中删除所有以该节点为起始节点的有向边。重复上述步骤, 直到图G中不存在入度为0的节点时为止。此时, 寻找到的路径即为在线服务偏好序列。
定义8??S=(pk|k=1, 2, …, n)为在线服务偏好序列。其中, pk表示第k个在线服务在集结所有用户偏好关系得到的在线服务偏好序列中的次序。例如S=(p2, p3, …, p1)表示在偏好序列中p2?p3?…?p1。
在得到在线服务偏好序列S后, 根据序列S得到在线服务整体排序结果O：根据在线服务pk在S中的次序得到服务pk的评价值ok=n-k+1, 其中n为在线服务数量, k为在线服务在偏好序列S中的排列次序。例如S=(p2, p1, p3), 此时各在线服务评价值分别为o2=(3-1+1), o1=(3-2+1), o3=(3-3+1), 因此得到在线服务排序结果O=(o2, o1, o3)。根据有向图G得到在线服务排序结果O的算法4如图 4所示。
 |
| 图 4 算法4 |
| 图选项 |
3 评价模型理论分析为了通过理论验证本文方法的有效性和合理性, 需要对利用排序对社会选择函数得到的在线服务排序结果的孔多赛性、反转对称性、非独裁性、单调性以及操纵复杂性进行证明。
性质1??孔多赛性。如果存在服务px与其他任意服务py成对比较时，都有一半以上用户认为服务px优于py，则px为孔多赛候选服务。
证明??px与任意py比较，都有一半以上用户认为px优于py，即
性质1表明孔多赛候选服务满足多数用户的偏好，是多数用户意愿的体现，因此可以将孔多赛候选服务作为评价结果进行推荐。
性质2??反转对称性。对不同在线服务px、py，若每个用户ui都认为服务px优于py，那么排序结果为ox?oy。若每个用户都做出相反选择，即每个用户都认为服务py优于px，那么排序结果为ox?oy。即如果每个用户对所有在线服务评价偏好都发生反转，则得到的在线服务整体排序结果与用户偏好反转前相比要相应进行反转。
证明??如果每个用户ui对不同在线服务px、py偏好由px?py变为px?py，由式(2)在服务对(px, py)中服务之间的优先关系由px?py变为py?px，从而在矩阵CM中cmxy > 0变为cmxy < 0，导致在图G中寻找最优路径时节点遍历顺序由用户偏好反转前节点px优先py遍历变为py优先px遍历，即排序结果由ox?oy变为ox?oy。因此本方法满足反转对称性。
性质2表明本方法对在线服务评价的公平性，它防止用户偏袒某一在线服务，因为只有在每个用户都对两个在线服务作相反选择时，得到的排序结果才会作相反选择，即评价应同样对待所有在线服务。
性质3??非独裁性。不同在线服务px、py成对比较时，如果仅有一个用户认为服务px优于py，而其他用户认为服务py优于px，那么在排序结果中服务px的排序名次不会优于py。
证明??仅有一个用户认为服务px优于py，即
性质3表明不应该让某个用户特有的评价偏好而影响用户集体评价结果。
性质4??单调性。对任意不同在线服务px、py并且在排序结果中ox?oy。若用户持续给予服务px高评分而对py评分保持不变，那么服务px的排序名次不应该降低；若用户持续给予服务py低评分而对px评分保持不变，那么服务py排序名次不应该提升，并且排序结果仍然是ox?oy。
证明??如果在排序结果中ox?oy，若用户持续给予服务px高评分而对py评分保持不变，使得认为服务px优于py的人数增加，因此cmxy值不可能降低，所以在对图G进行遍历寻找最优路径时节点px优先py遍历，因此结果仍然是ox?oy。同理，若用户持续给予服务py低评分而对px评分保持不变，结果仍然是ox?oy。因此本方法满足单调性。
性质4表明若用户对某在线服务偏好向好的方面变化，而对其他服务偏好保持不变，那么该服务排序结果不应该降低；反之，排序结果不应该提升。
性质5??操纵复杂性。对任意在线服务py，增加对服务py高评分的不诚实用户操纵py评分，评价结果不变。
证明??如果存在服务px、py并且在排序结果中ox?oy，即在图G中遍历节点寻找最优路径时节点px优先py遍历，因此在矩阵CM中cmxy > 0，由式(2)在服务对(px, py)中px?py。增加少许对服务py高评分用户来操纵py评分，仍然有px?py，所以排序结果仍然是ox?oy。因此本方法评价结果具有抗操纵性。
4 实验与分析为了验证本文评价方法的有效性，在以下环境下进行实验验证：Intel Core I5 CPU，64位Win10操作系统，开发环境为pyCharm 2016.2.3，开发语言为Python 2.7。实验采用MovieLens[23]数据集，该数据集包含1 682部电影，943名用户，10万条左右的用户真实评分。本文使用现在3种比较流行的在线服务评价方法：累加(Sum)法、均值(Average)法以及Beta信誉系统方法[24]作为主要对比方法。实验验证了评价结果的孔多赛性、反转对称性、多数准则、单调性以及操纵复杂性。
4.1 孔多赛性实验如果一个评价方法得到的最优在线服务与孔多赛候选服务一致，则该方法得到的评价结果满足孔多赛性。为此，实验随机选取52个在线服务，依次编号为1~52，用户数量为943个，然后集中所有用户对不同在线服务的偏好关系，有一半以上的用户都认为8#服务优于其他任意一个在线服务，所以8#服务为孔多赛候选服务。本文方法聚合所有用户的偏好关系得到在线服务偏好序列，然后根据偏好序列得到在线服务评价结果如图 5a所示，Sum法、Average法、Beta法得到的评价结果分别如图 5b、5c、5d所示。
 |
| 图 5 孔多赛性验证 |
| 图选项 |
从图 5可以看出，本文方法得到8#服务评价值最高，与孔多赛候选服务一致，因此本文方法评价结果满足孔多赛性。同时，Sum法得到的最优在线服务与孔多赛候选服务一致，因此Sum法评价结果也满足孔多赛性。但是，Average法与Beta法得到的最优在线服务和孔多赛候选服务并不一致，因此Average法与Beta法评价结果不满足孔多赛性。
4.2 反转对称性实验当每个用户对两个在线服务作相反选择时，如果一个评价方法得到的排序结果也作相反选择，则该方法得到的评价结果满足反转对称性。为此，实验将943个用户对所有在线服务评价全都取反，然后分别计算用户初始评价与用户评价取反后的在线服务评价结果，如图 6所示。
 |
| 图 6 反转对称性验证 |
| 图选项 |
从图 6可以看出，用户评价取反前评价结果中评价值最大的服务在评价取反后得到的评价值最小；用户评价取反前评价结果中评价值最小的服务在评价取反后得到的评价值最大。所以在所有用户对全部在线服务作相反选择时，本文方法得到的评价结果也作相反选择。因此本文方法评价结果满足反转对称性。
4.3 多数准则实验根据用户的从众心理，本文验证了多数准则，但这里的多数准则是指在不同在线服务px、py成对比较时，如果认为服务px优于py的用户人数多于认为服务py优于px的用户人数，那么在评价结果中服务px排序名次优于py。为此，实验随机选取20~100个在线服务，用户数量为943个，分别统计本文方法、Sum法、Average法与Beta法在不同数量在线服务时得到的评价结果中各自满足多数准则的比例，结果如图 7所示。
 |
| 图 7 多数准则验证 |
| 图选项 |
从图 7可以看出，由于孔多赛悖论[25]的存在，结果不可能达到100%。比如，用户集合U={u1, u2, u3}, 在线服务集合P={p1, p2, p3}。其中, u1偏好为p1?p2?p3；u2偏好为p2?p3?p1；u3偏好为p3?p1?p2。由于u1、u2都认为服务p2?p3, 根据多数准则, 用户集体也应该认为p2?p3；由于u2、u3都认为服务p3?p1，用户集体也应该认为p3?p1。但是，由于u1、u3都认为服务p1?p2，因此出现矛盾。但是，本文方法在不同数量在线服务时满足多数准则的比例均达到98%以上，高于Sum法、Average法与Beta法满足多数准则的比例。
4.4 单调性实验随机选取某个在线服务，提高或者降低该服务评分而保持其他服务评分不变，如果一个评价方法得到的评价结果中提高在线服务评分时该服务排序名次没有降低，降低在线服务评分时该服务排序名次没有提升，则该方法得到的评价结果满足单调性。为此，实验随机选取两个在线服务，分别选择100~600个用户提高和降低其对在线服务的评分。本文方法得到在不改变在线服务评分以及在不同人数用户降低和提高在线服务评分时该服务评价值分别如图 8a和8b所示。
 |
| 图 8 单调性验证 |
| 图选项 |
从图 8可以看出，提高在线服务评分时本文方法得到该服务评价值呈上升趋势，即该服务排序名次会提高；降低在线服务评分时本文方法得到该服务评价值呈下降趋势，即该服务排序名次会降低。因此本文方法评价结果满足单调性。
4.5 操纵复杂性实验随机选取某服务，增加对其高评分与低评分的不诚实用户来操纵该服务评分，如果评价结果中，增加不诚实用户并不影响该服务的排序名次，则该方法得到的评价结果具有抗操纵性。为此，随机选取两个在线服务，用户数量为943个，分别增加10~100个不诚实用户。本文方法、Sum法、Average法以及Beta法分别计算在增加不同数量不诚实用户提高和降低在线服务评分时该在线服务的评价值，结果分别如图 9a和9b所示。
 |
| 图 9 操纵复杂性验证 |
| 图选项 |
从图 9可以看出，增加不同数量不诚实用户分别提高与降低其对在线服务评分时，本文方法得到的评价结果中该服务评价值几乎不变，即该服务排序名次几乎不受影响。但是，Sum法、Average法以及Beta法得到的评价结果中该服务评价值却大幅度提高或降低，即该服务排序名次将会提升或下降。因此，本文方法得到的评价结果具有更好的抗操纵性。
4.6 性能测试当在线服务数量固定时，依次选取943个用户中前20%、40%、60%、80%、100%的用户作为不同数据集进行实验。分别记录本文方法、Sum法、Average法与Beta法在不同数据集时得到在线服务评价结果运行时间，结果如图 10所示。
 |
| 图 10 运行时间 |
| 图选项 |
从图 10可以看出，随着用户人数的增加，计算用户评价的次数会相应增加，导致得到在线服务排序结果的计算量也会增加。但是，本文方法运行时间并不随用户数量增加成指数级增长，因此方法效率较高。另外，从图 10可知，与Sum法、Average法、Beta法运行时间相比，本文方法运行耗时相对较长，因此对本文评价方法进行操纵得到在线服务评价结果需要比其他3种方法消耗更长的时间，所以本文方法评价结果操纵难度高于其他3种方法。
5 结论本文基于社会选择的思想，提出一种基于排序对社会选择函数的在线服务评价方法，不需要假设不同用户具有完全一致的评价准则。首先将用户对不同在线服务评分转换成该用户对不同服务之间的偏好关系，然后利用排序对社会选择函数集结每个用户的偏好关系得到在线服务评价结果。理论分析和实验结果表明，本文方法在用户评价准则不一致时具有更好的合理性和有效性。
如何将协同过滤推荐方法与其他方法结合进一步提高数据填充的准确性从而得到更加准确的在线服务评价结果，是下一步要开展的研究工作。
参考文献
| [1] | KRAUSE A, HORVITZ E. A utility-theoretic approach to privacy in online services[J]. Journal of Artificial Intelligence Research, 2014, 39(1): 633-662. |
| [2] | 王尚广, 孙其博, 杨放春. Web服务选择中信誉度评估方法[J]. 软件学报, 2012, 23(6): 1350-1367. WANG S G, SUN Q B, YANG F C. Reputation evaluation approach in Web service selection[J]. Journal of Software, 2012, 23(6): 1350-1367. (in Chinese) |
| [3] | 蒋哲远, 韩江洪, 王钊. 动态的QoS感知Web服务选择和组合优化模型[J]. 计算机学报, 2009, 32(5): 1014-1025. JIANG Z Y, HAN J H, WANG Z. An optimization model for dynamic QoS-aware Web services selection and composition[J]. Chinese Journal of Computers, 2009, 32(5): 1014-1025. (in Chinese) |
| [4] | BHARGAVA K, GUJRAL T, CHAWLA M, et al. Comment based seller trust model for E-commerce[C]//Proceedings of 2016 International Conference on Computational Techniques in Information and Communication Technologies. New Delhi, India: IEEE, 2016: 387-391. |
| [5] | ZHANG X Z, CUI L S, WANG Y. Computing multi-dimensional trust by mining E-commerce feedback comments[J]. IEEE Transactions on Knowledge & Data Engineering, 2014, 26(7): 1631-1643. |
| [6] | YAO Y, RUOHOMAA S, XU F. Addressing common vulnerabilities of reputation systems for electronic commerce[J]. Journal of Theoretical & Applied Electronic Commerce Research, 2012, 7(1): 1-20. |
| [7] | FU X D, YUE K, LIU L, et al. Aggregating ordinal user preferences for effective reputation computation of online services[C]//Proceedings of 2016 IEEE International Conference on Web Services. San Francisco, USA: IEEE, 2016: 554-561. |
| [8] | 付晓东, 邹平, 姜瑛. 基于质量相似度的Web服务信誉度量[J]. 计算机集成制造系统, 2008, 14(3): 619-624. FU X D, ZOU P, JIANG Y. Web service reputation measurement based on quality of service similarity[J]. Computer Integrated Manufacturing Systems, 2008, 14(3): 619-624. (in Chinese) |
| [9] | DEY P, MISRA N, NARAHARI Y. Kernelization complexity of possible winner and coalitional manipulation problems in voting[J]. Theoretical Computer Science, 2016, 616(1): 111-125. |
| [10] | MCAULEY J, LESKOVEC J, JURAFSKY D. Learning attitudes and attributes from multi-aspect reviews[Z/OL]. (2012-11-31). https://arxiv.org/abs/1210.3926. |
| [11] | HSIEH H Y, WU S H. Ranking online customer reviews with the SVR model[C]//Proceedings of 2015 IEEE International Conference on Information Reuse and Integration. San Francisco, USA: IEEE, 2015: 550-555. |
| [12] | SCAFFIDI C, BIERHOFF K, CHANG E, et al. Red Opal: Product-feature scoring from reviews[C]//Proceedings of the 8th ACM Conference on Electronic Commerce. San Diego, USA: ACM, 2007: 182-191. |
| [13] | 吕品, 钟珞, 唐琨皓. 在线产品评论用户满意度综合评价研究[J]. 电子学报, 2014, 42(4): 740-746. Lü P, ZHONG L, TANG K H. Customer satisfaction degree evaluation of online product review[J]. Acta Electronica Sinica, 2014, 42(4): 740-746. (in Chinese) |
| [14] | 王玉祥, 乔秀全, 李晓峰, 等. 上下文感知的移动社交网络服务选择机制研究[J]. 计算机学报, 2010, 33(11): 2126-2135. WANG Y X, QIAO X Q, LI X F, et al. Research on context-awareness mobile SNS service selection mechanism[J]. Chinese Journal of Computers, 2010, 33(11): 2126-2135. (in Chinese) |
| [15] | JOSANG A, ISMAIL R. The beta reputation system[C/OL]. [2017-06-01]. http://aisel.aisnet.org/bled2002/41/. |
| [16] | ARROW K J. Social choice and individual values[M]. New Haven, USA: Yale university press, 2012. |
| [17] | DAVID H A. The method of paired comparisons[M]. 2nd ed. London, UK: Hodder Arnold, 1988. |
| [18] | OKASHA S. Theory choice and social choice:Kuhn versus Arrow[J]. Mind, 2011, 120(477): 83-115. DOI:10.1093/mind/fzr010 |
| [19] | TIDEMAN T N. Independence of clones as a criterion for voting rules[J]. Social Choice and Welfare, 1987, 4(3): 185-206. DOI:10.1007/BF00433944 |
| [20] | VIGLAS S D. Rate-based query optimization for streaming information sources[C]//Proceedings of 2002 ACM SIGMOD International Conference on Management of Data. Madison, USA: ACM, 2002: 37-48. |
| [21] | 张莉, 张斌, 黄利萍, 等. 基于服务调用特征模式的个性化Web服务QoS预测方法[J]. 计算机研究与发展, 2013, 50(5): 1066-1075. ZHANG L, ZHANG B, HUANG L P, et al. A personalized Web service quality prediction approach based on invoked feature model[J]. Journal of Computer Research & Development, 2013, 50(5): 1066-1075. DOI:10.7544/issn1000-1239.2013.20110928 (in Chinese) |
| [22] | ZHAO T, MCAULEY J, KING I. Leveraging social connections to improve personalized ranking for collaborative filtering[C]//Proceedings of the 23rd ACM International Conference on Conference on Information & Knowledge Management. Shanghai, China: ACM, 2014: 261-270. |
| [23] | HARPER F M, KONSTAN J A. The MovieLens datasets:History and context[J]. ACM Transactions on Interactive Intelligent Systems, 2015, 5(4): 19. |
| [24] | FANG W D, ZHANG C L, SHI Z D, et al. BTRES:Beta-based trust and reputation evaluation system for wireless sensor networks[J]. Journal of Network & Computer Applications, 2016, 59: 88-94. |
| [25] | HERINGS P J J, HOUBA H. The Condorcet paradox revisited[J]. Social Choice and Welfare, 2016, 47(1): 141-186. DOI:10.1007/s00355-016-0950-7 |
