0 引言

随着在线服务的爆炸性增长，用户面临着如何在大量的在线服务中选择偏爱的、优质的在线服务的问题。然而不同用户对服务质量的要求各有不同，面对大量功能相同或相近的在线服务^[1]，单个用户不可能与每一个服务都产生交互，更不可能对每一个服务都给予评价，越来越多的用户访问在线服务的所形成的经验表明，一个优质的在线服务要尽可能地满足绝大多数人的偏好，因此，优质的在线服务成为用户服务选择的自然需求。

在线服务的评价，是用户自身与该在线服务交互过程中所产生的一种主观感受^[2]，但是，用户的主观感受很难被客观地描述和获取，且对选择同一服务的不同用户而言，由于用户自身的背景、心理和偏好等因素的不同，使得用户之间的评价标准不一致^[1-2]，即使服务之间具有同样的服务质量表现，它们得到的评价也不尽然相同。用户的评价正是用户对于在线服务是否满足用户偏好的主观感受表现，因此，评价值的高低可以较好地反映用户使用在线服务的主观感受。文献[3]的研究中指出在线服务提供者选择必须考虑用户观点，由于不同用户之间的评价尺度不一致，即使在线服务使不同用户均感到满意，它们得到的评价也会不一致，进一步导致在线服务之间不具备公正的可比较性；另外，还有一些不法的用户和在线服务提供商为了提高或降低某些在线服务的影响力，采取欺骗手法恶意捏造用户评分数据而达到操纵服务信用的目的^[4]，扭曲在线服务的可信度，致使用户利用这种可信度进行服务选择时会产生不客观的结果，从而使用户面临不能选择到合适服务的风险。

针对用户评价标准不一致和偏好不一致导致网络空间中的在线服务之间不具备公正的可比较性问题。本文基于社会选择理论的基本思想，提出一种决策分析方法，该方法使个体偏好和群体决策达到最大一致。该方法不对任何用户的评价标准作任何假定，在充分考虑用户主观偏好选择和不同评价标准的条件下，通过集结个人偏好形成群决策，设计了从大量用户的偏好序中产生一个最优的在线服务优劣排序方法，最后通过理论分析和实验验证了该方法的有效性和合理性。

1 相关研究

近年来，大量的研究工作已经或正在围绕利用用户的评价信息判断服务质量优劣的问题展开。目前在线电子商务评价方法主要有累加法、平均法、概率法、模糊法、流程法等^[5]。文献[1]的研究指出目前的服务评分值的预测方法主要采用简单平均值、加权平均值、中心加权平均值3种统计的方法，但不同用户的评价值之间不可简单累加和求平均；文献[6]提出了一种基于可信评价的制造云服务选择方法，采用加权平均的方法计算制造云服务的整体可信度，能有效地识别云制造环境下的制造云服务实体，但加权平均的方法下的评价值不具备可比较性；文献[7]利用Beta信誉系统的信誉计算方法作为评价服务水平协议可信度的评价标准，虽在用户偏好不确定的条件下提高了云服务组合的兼容性精确度，但不能满多数人的偏好。推荐系统与信誉系统领域，文献[8]的研究指出现有的推荐系统假定不同用户间主观性的不一致导致评价不一致，现有信誉系统都假定所有用户具有一致的评价标准，然而用户对在线服务的偏好和评价不可能完全一致，甚至可能出现矛盾和冲突。对群决策而言，文献[9]的研究中分析了3种最常用的群组决策策略：Average Satisfaction、Minimum Misery、Maximum Satisfaction，但这三种策略均是同等地看待用户的评价；文献[10]的研究中指出Average Satisfaction可能导致更多的推荐偏见，Minimum Misery可能忽视大多数人的偏好；MusicFX^[11]是一个健身房背景音乐群组推荐系统，采用的是Maximum Satisfaction群组决策策略，它试图最大化群组成员的满意度，其关键的前提条件用户必须事先对所有音乐网站都给予评价，但对于大规模的音乐网站来说显得效率及其低下；文献[12]指出目前所有的推荐系统都面临着一些共性的重难点问题：评价数据稀疏^[13]和推荐系统的安全性即推荐攻击等问题，然而，这些问题都严重影响着推荐排序的优劣结果，不能给予用户更好的决策选择。文献[14]通过分析移动用户行为，提出一种基于信任度和链接预测的移动用户偏好预测方法，在一定程度上解决了稀疏性问题，但采用的是平均评分值，未考虑用户评价不一致性；文献[15]的研究提出社会选择理论与云计算相结合的方法应用于在线营销研究，与传统的方式相比，充分考虑了用户不一致的观点，帮助市场管理者作出高效而实际的决策；文献[16]指出用户使用在线服务后进行的主观评价, 易受自身因素影响, 不同用户对同一在线服务作出的评价可能存在较大差异，因此当用户根据前人经验评价进行服务选择时, 必须考虑用户主观因素对于评价值的影响。

上述研究很少考虑用户主观因素不一致导致的问题，大多数研究都是假定用户的评价标准和评价尺度一致的情况下基于用户对服务的评价来评估在线服务优劣，均是同等地看待每个用户的评价。考虑到现有研究中存在的不足，本文基于社会选择理论思想对在线服务进行群体评价，提出了利用Kemeny函数^[17]来计算在线服务的优劣排序的方法。Kemeny函数是社会选择理论中唯一的同时满足中性、一致性及孔多赛性的社会选择函数^[18]。在不需要假定用户评价标准和评价尺度一致的情况下，通过集结个人用户的历史评价结果形成聚合排序，对在线服务服务群体评价形成群决策，解决用户在偏好不一致及评价标准不一致情况下的服务优劣选择问题，一定程度上避免了用户评分数据极端稀疏的负面影响，又达到有效地抵制推荐攻击的目的。

2 问题描述

为了更好地阐述开放网络环境下的用户偏好不一致和评价准则不一致的在线服务评价问题，本文首先给出相关定义如下。

定义1  集合U={u_i|i=1, 2, …, m}为所有用户集合；集合S={s_j|j=1, 2, …, n}为用户与所有在线服务产生交互的服务集合。

定义2  所有用户对其评价的服务形成的矩阵为用户-服务评分矩阵R=[r_ij]_m*n；其中r_ij表示第i个用户对第j个服务的评价值且r_ij=[0, 5]，若r_ij=0则表明第i个用户对第j个服务未评价。

综合比较了现有的在线服务评价方法后，针对用户主观评价标准不一致的研究表明一种公正且有效的在线服务优劣评价方法应当满足以下特性：

1) 一致性。若结果的最优服务排序中服务s_x优于s_y，那么大多数用户均认为服务s_x优于s_y(或s_x至少不劣于s_y)。

2) 孔多赛性。当大多数用户认为服务s_x优于其他服务(该在线服务在逐对比较时优于其他所有服务)，那么s_x优于其他的在线服务。

3) 公平性(中性)。若每个用户对两个服务作相反评价时, 群体最优服务排序的结果也要作相反选择；公平性是对在线服务的公平性，它防止用户偏袒某一在线服务，因为它保证在每个用户都对两个在线服务作相反选择时，那排序结果应作相反的选择，亦即社会选择机制应同样对待所有在线服务。

4) 多数准则性。若认为服务s_x优于服务s_y的人数多于认为服务s_y优于服务s_x的人数，那么最优服务排序结果中服务s_x必须优于服务s_y。

5) 防操纵性。若操纵某些服务的评价时，即提高或者降低某些服务的评分时，那么最终的服务排序结果也应保持不变。

3 基于社会选择理论的在线服务评价方法

用户对在线服务的评分是用户的主观感受，故不同用户对同一在线服务评价标准存在较大差异，所以对于不同用户对同一在线服务的评价信息是不能用同等看待的。为此常用评价中的累加求和法(Sum)、求平均法(Average)和Beta信誉系统的信誉计算方法^[19]得出的评价结果具有误导性，而且若用户评价值一旦被攻击，那么累加和法、平均法和Beta信誉计算法得出的评价结果会极易被改变，因此，提出一种基于社会选择理论^[20]对在线服务进行群体评价的方法，将同一用户对不同在线的评价转换成用户对在线服务的偏好关系，然后集结所有用户的偏好，形成群体评价。

定义3  u_i是一个用户，其评价的在线服务之间的偏好关系：若r_ij>r_ik，则s_j≻_is_k；若r_ij=r_ik，则s_j~_is_k；若r_ij < r_ik，则s_j≺_is_k；其中，s_j≻_is_k表示用户u_i认为服务s_j优于服务s_k；s_j≺_is_k表示用户u_i认为服务s_k优于服务s_j；s_j~_is_k表示用户u_i认为服务s_j和服务s_k无差别。

定义4  用户的评价偏好排序O_i，其中，O_i={s_k|k=1, 2, …, t}, 1≤t≤n, 1≤i≤m，O_i表示第i个用户u_i依据用户偏好规则建立的在线服务偏好排序序列，如O_j={s₂, s₄, s₁, s₃, s₅, …}表示用户u_j认为s₂≻s₄≻s₁≻s₃≻s₅≻…。

定义5  用户偏好矩阵C=[c_ij]_n*n，其中：

$ {{c}_{ij}}=\sum\limits_{k=1}^{m}{I\left( {{s}_{i}}\succ {{s}_{j}} \right)};\ i, j=1, 2, \cdots, n $

(1)

其中：I(s_i≻s_j)为指示函数，即当s_i≻s_j时，I=1；否则I=0。

在这里，用户偏好矩阵C是将m个用户所评价的n个在线服务，根据用户评价偏好排序O_i对在线服务进行两两成对比较，统计m个用户中认为s_i≻s_j的次数；很显然，矩阵C的第i行表示在线服务i优于其他服务的次数，矩阵C的第j列表示在线服务j劣于其他服务的次数。

将每个在线服务与所有其他服务两两成对比较，只要一个服务在大多数用户投票上的得分高于另一个候选服务，那么它便击败了那个候选服务。击败所有其他服务的便是孔多塞赢家。这方法称为孔多赛标准^[21]。

由于用户自身的评价标准是一致的，所以用户自身评价各服务之间的评价值是具备可比较性的，不需要同等地看待不同用户的评价标准，不需假定用户之间具有一致性的标准，因此，有效地避免不同用户之间的评价标准与评价尺度不一致所产生评价值的比较；这就解决了由于用户评分准则不一致而导致的不同用户对同一在线服务的评分不可较的问题。

定义6  用户偏好比例矩阵E=[e_ij]_n*n，其中：

$ \mathit{\boldsymbol{E}} = {\left[{{e_{ij}}} \right]_{n*n}} = \left( {\mathit{\boldsymbol{C}} -{\mathit{\boldsymbol{C}}^{\rm{T}}}} \right)/m $

(2)

其中：e_ij表示群体m个用户中认为服务s_i优于服务s_j的人数比例与群体用户中认为服务s_i劣于s_j服务的人数比例之差；矩阵E反映了群体用户对各在线服务总的偏好。

定义7  社会选择的排序矩阵为P=[p_jk]_n*n，其中：

$ {p_{jk}} = \left\{ \begin{array}{l} 1, \;\;\;{s_j} \succ {s_k}\\ 0, \;\;\;{s_j} \prec {s_k} \end{array} \right. $

(3)

显然，对于n个在线服务而言，仅考虑严格的优于关系，n个在线服务的排序种类也达到n!个，根据排序关系(3) 它的每一种优劣排序都对应相应的排序矩阵P。

3.1 基于Kemeny社会选择函数的在线服务评价

基于Kemeny社会选择函数^[22]的在线服务评价的思想是将所有用户的个体偏好集结成群体偏好，以得出在线服务的一个群排序。对n个在线服务而言，需要先逐一地计算n!个社会选择排序矩阵，然后再计算出每一个排列矩阵的Kemeny数值，并将最大的函数值所对应的排列作为最符合群体偏好的排列。

3.1.1 Kemeny函数

〈E·P〉表示用户偏好比例矩阵与社会选择的排序矩阵的内积，$ \left\langle {\mathit{\boldsymbol{E}} \cdot \mathit{\boldsymbol{P}}} \right\rangle = \sum\limits_{j, k} {{e_{jk}}{p_{jk}}} $，Kemeny函数定义为：

$ {f_k}\left( \mathit{\boldsymbol{P}} \right) = \left\langle {\mathit{\boldsymbol{E}} \cdot \mathit{\boldsymbol{P}}} \right\rangle = \sum\limits_{j, k} {{e_{jk}}{p_{jk}}} $

(4)

式(4) 来衡量排列矩阵P与用户的群体偏好的一致性或相似性；这个模型依据是当P中的元素p_ij的符号尽可能多地与E中对应的元素e_ij的符号一致时，P所对应的最优排列将能更好地反映出群体的偏好；Kemeny函数是要找符合孔多塞标准的P，使得〈E·P〉取最大值的P^*：

$ {f_k}\left( {{\mathit{\boldsymbol{P}}^*}} \right) = {\rm{max}}\left\langle {\mathit{\boldsymbol{E}} \cdot \mathit{\boldsymbol{P}}} \right\rangle = {\rm{max}}\sum\limits_{j, k} {{e_{jk}}{p_{jk}}} $

(5)

即对任意P均满足：

$ {f_k}\left( \mathit{\boldsymbol{P}} \right) \le {f_k}\left( {{\mathit{\boldsymbol{P}}^*}} \right) $

(6)

3.1.2 Kemeny函数0-1整数规划

利用Kemeny函数进行群决策的最大困难是它较大的计算量，文献[23]指出Kemeny函数计算是个NP-hard问题。由于其计算的复杂性，本文采用0-1整数规划模型来求解Kemeny函数的最佳在线服务评价排序矩阵P^*；根据社会选择排序矩阵P中的排序关系式(3)，只需考虑排序矩阵P中右上角矩阵元素，即可求出所有的排序关系；又由于用户比例矩阵E为对角线为0的反对称矩阵，故：

$ {f_k}\left( \mathit{\boldsymbol{P}} \right) = {\rm{max}}\sum\limits_{j, k} {{e_{jk}}{p_{jk}} = 2{\rm{max}}\sum\limits_{j < k} {{e_{jk}}{p_{jk}}} } $

(7)

因此，对文献[24]提出的整数规划目标函数进行如下改进，Kemeny函数的0-1整数规划模型如下：

目标函数：

$ {f_k}\left( \mathit{\boldsymbol{P}} \right) = 2{\rm{max}}\sum\limits_{j < k} {{e_{jk}}{p_{jk}}} $

(8)

约束于:

$ \left\{ \begin{array}{l} {p_{hj}} + {p_{jk}}-{p_{hk}} \le 1, \\ -{p_{hj}}-{p_{jk}} + {p_{hk}} \le 0, \forall h < j < k\\ {p_{jk}} \in \left\{ {0, 1} \right\}, \end{array} \right. $

(9)

3.2 方法过程描述

根据以上分析, 本节设计了基于Kemeny函数的在线服务优劣排序方法; 集结用户偏好排序，产生一个整体的在线服务优劣排序, 用户可以选择最令人满意的在线服务。同时文献[17-19]表明Kemeny函数是满足中性、一致性及孔多赛性的社会选择函数。综上所述，设计求解不一致用户偏好序信息的最佳在线服务评价排序的计算方法如下。

步骤1  集结所有用户U评价的在线服务S，根据用户偏好评价值建立用户-服务评分矩阵R=[r_ij]_m*n。

步骤2  根据用户-服务评分矩阵R建立用户的在线服务评价偏好排序O_i。

步骤3  集结所有用户的服务评价偏好排序O_i计算用户偏好矩阵C=[c_ij]_n*n。

步骤4  依据用户偏好矩阵C计算用户偏好比例矩阵E=[e_ij]_n*n，构建Kemeny函数的0-1整数规划模型。

步骤5  求解构建的优化模型，得到最优解矩阵P^*=[p_ij^*]_n*n。

步骤6  依据最优解矩阵P^*和式(3) 中的对应关系，便可计算出最优的服务优劣排序或选择最优的在线服务。

4 评价模型理论分析

为了通过理论验证基于Kemeny函数的在线服务优劣排序方法的合理性和有效性，下面对Kemeny函数的孔多塞性、公平性、一致性和操纵复杂性进行证明。

定理1   孔多赛性。若∃服务s_i，使得大多数的用户均评价服务s_i优于其他所有在线服务s_j(∀j=1, 2, …, n, j≠i)有c_ki≥c_kj(k=1, 2, …, m)，则在线服务s_i是孔多赛赢者。

证明  若对大多数用户的偏好序O_k(k=1, 2, …, m)均认为s_i≻_ks_j，则必有$ \sum\limits_{k = 1}^m {I\left( {{s_i} \succ {s_j}} \right)} \ge \sum\limits_{k = 1}^m {I\left( {{s_j} \succ {s_i}} \right)} $，显然，c_ij≥c_ji, 即在线服务s_i是孔多赛赢者，优于其他服务，因此本方法满足孔多塞性。

定理2  公平性。对任意服务s_i和s_j，若每个用户均认为s_i≻_ks_j时，那么结果的整体排序中必有s_i≻s_j；若每个用户取相反评价s_i≺_ks_j时，那么结果的整体排序中必有s_i≺s_j，则群体评价Kemeny函数对候选服务具有公平性。

证明  若对每个用户的偏好序O_k(k=1, 2, …, m)均满足s_i≻s_j，必有c_ij≥c_ji，则有e_ij≥e_ji，又由于上文3.1.1节中的模型依据可知最终的排序结果p_ij与e_ij保持一致，则结果的整体排序中必有s_i≻s_j；相反可证若对每个用户的偏好序O_k均满足s_i≺s_j时，则结果的整体排序中必有s_i≺s_j，所以该函数满足一致性，故f_k(－P)=－f_k(P)。

定理3  一致性。对大多数服务s_i和s_j，若最终的排序结果中∃s_i≻s_j，那么大多数用户应均认为s_i≻s_j，排序结果应与大多数用户保持一致，则该函数满足一致性。

证明  根据定理1和2可知，最终的排序结果中s_i≻s_j，那么p_ij=1，则e_ij>0，必有c_ij≥c_ji，那么一定有$\sum\limits_{k = 1}^m {I\left( {{s_i} \succ {s_j}} \right)} \ge \sum\limits_{k = 1}^m {I\left( {{s_j} \succ {s_i}} \right)} $，所以大多数用户应均认为s_i≻s_j，因此该函数满足一致性。

定理4  防操纵性。对∀s_i服务而言，若增加对在线服务s_i给予低评分或者高评分的恶意欺诈用户数，最终的评价结果应不变。

证明  对于s_i，假设最终的评价结果中∃s_i≻s_j，增加些许恶意欺诈用户数的高评分(或低评分)评价偏好，则根据本文的在线服务排序方法并未改变c_ij，所以c_ij值不变，那么e_ij值不变，评价结果仍然是s_i≻s_j；故防操纵性强。

5 实验结果与分析

根据本文提出的基于Kemeny函数的在线服务评价方法，设计实现了在线服务评价方法，用于评价在线服务优劣，并对评价数据进行验证，验证评价方法的有效性及合理性。由于该方法基于用户的评分记录，因此必须建立用户评分数据集, 为使实验更为真实，参照MovieLens公开的数据集。在实验中，本文模拟了943个在线服务使用者和10~100个在线服务，以数据集里的评分模拟为电子商务中用户对服务表现的满意程度，采用电子商务评价机制中常用的5个等级，1~5级分别表示很不满意、不满意、一般、满意和很满意，数据集中的0值表示用户与该在线服务没有产生交互或没有评价。为了进一步验证在线商品评价模型的高效性，本文使用现在两种比较流行的在线服务评价方法: 累加和(Sum)方法、平均(Average)方法、Beta信誉系统的信誉计算方法^[25]作为本文的主要对比方法。

5.1 有效性实验

该实验用于验证本文方法的有效性。实验模拟了943个服务用户和10~100个在线服务，为验证该方法的有效性，对不同服务样本数量情况下算法记录了依据本方法得到的最优在线服务排序矩阵P^*时的Kemeny函数值，如表 1所示。

由表 1可见，固定用户数量，随着在线服务数量的增加，最优服务排序的Kemeny函数值越来越大，说明用户偏好比例矩阵E中的元素与服务排序矩阵P^*中的元素保持符号一致越来越多，也表明保持一致性的人数也越来越多。

5.2 一致性实验

该实验用于验证本文方法的一致性。若本文方法得到的整体排序结果与大多数用户对服务评价的排序趋势大致相同，则该方法具有一致性。为了验证该方法的一致性，本文选择Sum方法、Average方法、Beta方法以及本文方法，取这4种方法每次排序后的最优的两个在线服务，比较其一致性的人数，结果如图 1所示。由图 1可以看出，很明显在大多数情况下本文方法的排序结果比Sum方法、Average方法、Beta方法的排序结果保持一致性的人数多，因此，本文提出的基于Kemeny函数的在线服务优劣排序满足一致性，更能与群体的偏好保持最大的一致。

5.3 公平性实验

该实验用于验证本文方法的公平性。若每个用户对两个候选方案作相反选择时, 群体的选择结果也要作相反选择，即f_k(－P)=－f_k(P)。为了验证本方法的公平性，再利用Kemeny函数模型重新计算；例如一般情况下根据本文方法得到的最优服务排序为s₃≻s₅≻s₂≻s₄≻s₁；当用户取对服务的相反评价之后，再根据本文方法计算的最优服务排序为服务的群体排序为s₃≺s₅≺s₂≺s₄≺s₁。本次实验模拟了943个在线服务使用者和10~100个在线服务，初始评价与取相反评价后，比较其最优在线服务排序的Kemeny值，如表 2所示，实验表明如果用户作相反选择，那么群体排序结果也会相反，因此该方法对服务评价是公平的。

5.4 抗操纵性和抵制推荐攻击实验

为了验证该方法的抗操纵性，随机选择一个在线服务增加10~100个欺诈用户，将该在线服务的评价值同时提高到5分或者同时降低到1分来产生恶意攻击数据。与Sum方法、Average方法、Beta方法相比，本实验中对于这4种方法都选取原最终排序为第20的在线服务，如图 2(a)和2(b)所示，本文方法结果几乎不变，而Sum方法、Average方法随着不诚实用户数量的增多，使该在线服务的排序大量提前或推后了，Beta方法虽然开始变化不明显，但是随着不诚实用户人数大量增加，服务排序名次也退后了，因此本方法具有防操纵性。

一些不法的用户为了提高或降低某些对象的推荐概率，恶意捏造用户评分数据而达到目的，这也是推荐系统存在的一个安全问题，被称为推荐攻击^[26]。本实验随机选择943个用户中的20%的用户，再将其评价的在线服务的评价值同时提高到5分或者同时降低到1分来恶意攻击数据，结果如图 3(a)和图 3(b)所示。由图 3可知，随着服务数量的增加, 未恶意攻击评价数据与恶意攻击评价数据后，图中的未恶意攻击数据与恶意攻击数据后的点未发生非常明显的变化，几乎达到一致，本文方法产生的在线服务最佳排序几乎未被影响；由此可见，Kemeny函数得到的最优服务排序结果保持了多数用户的偏好选择，因此，本文方法能有效地抵制推荐攻击，具有较强的抗操纵性。

6 结语

本文提出了基于社会选择理论的在线服务评价方法，缓解了由用户偏好不一致和评价标准不一致，导致的用户对在线服务不具备公正的可比较性问题。本文方法根据用户已评价的在线服务，通过Kemeny函数集结用户评价排序求出满足群体偏好一致性的最优在线服务优劣排序, 不需要假定用户之间具有的评价标准和评价尺度一致性，保证了服务之间比较的公正性，并通过理论分析与实验验证了该方法的有效性、公平性、抗操纵性，能有效地抵制推荐攻击，新加入用户可直接选择最优在线服务。由于在实际应用中，不断有新用户和新在线服务加入网络空间，从而得到新的评价，因此群体最优评价排序也需要实时更新，下一步的工作中将研究满足用户和服务动态增长的在线服务群体评价方法；并且随着在线服务数量的大量增加，Kemeny函数的计算难度越来越大，下一步的工作也将研究如何优化算法性能。