面向不完整序数偏好的在线服务评价

付晓东,彭 俊,岳 昆,刘 骊+,刘利军,冯 勇

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

0 引言

以互联网作为载体，由服务提供者向用户所提供的服务，被称为在线服务[1]。随着互联网技术的蓬勃发展，在线服务在Web服务、电子商务、搜索引擎等众多领域得到了广泛应用[2]。相应地，互联网出现了众多功能相同的候选在线服务[3]，用户想从中选择出满足自身需求的服务，势必会花费大量的时间与精力[4]。首先，用户不可能与所有候选的在线服务进行交互，使其难以获取所有候选服务的相关信息；其次，由于服务与服务之间的竞争激烈，不排除服务提供者为了提升其服务的竞争力发布虚假服务信息的可能。因此，用户通常需要借助以第三方用户观点(即其他用户对服务的数值型评分、文本评论、序数偏好等偏好信息)为基础的在线服务评价方法对服务进行评价。此类方法将所有已知的第三方用户观点作为输入，并使用相应的评价算法对候选服务进行有效的排序，用于辅助用户进行服务选择。

以数值型评分为基础的评价方法[5-6]和以文本评论为基础的评价方法[7-8]，均假设所有用户具有相同的评价准则，忽视了用户对服务的评分事实上不可比较的问题，使得评价结果可能具有误导性和不可靠性[9]。因此，出现了以序数偏好为基础的评价方法[10]，此类方法结合了社会选择理论[11]，将在线服务评价问题定义为一个群决策问题，其核心目的是将用户的序数偏好聚合为群体偏好，以辅助用户进行服务选择。由于此类方法在进行偏好聚合时，是使用序数偏好作为用户的服务评价数据，而不是数值型评分形式的基数偏好，从而解决了因用户的评价准则不一致而导致评价结果存在误导和不可靠的问题。

由于候选服务的数量集巨大，使得不完整偏好成为了极其常见的现象。首先，用户不可能对所有候选服务进行交互获得交互体验，从而用户所能提供的偏好难以覆盖所有候选服务；其次，用户大多并非决策领域专家，即使其与所有候选服务均有过交互体验，但是仍然很难提供对所有候选服务的完整偏好；再次，用户可能会出于对自身隐私的考虑，不愿意提供其全部的已知偏好；最后，要求用户提供其关于所有候选服务的完整偏好，会造成大量且不必要的计算和认知负担[12]。

偏好聚合是社会选择理论的基本问题之一[13]，但阿罗不可能定理[14]证明了不可能存在完美的偏好聚合方法。尽管如此，依然可通过运用各种距离作为度量指标，寻找与所有个体偏好距离最小的群体偏好，用于解决偏好聚合问题[15]。在该场景中，若候选服务数量为m，则潜在群体偏好的原始解空间规模为m!。当用户偏好为完整偏好时，可通过借助群体偏好应满足的某些基础公理(例如多数准则、孔多塞性等)有效地缩小解空间规模[16];当用户偏好不完整时，将导致潜在群体偏好的数量剧增，并会降低最终聚合结果的质量[17]。以聚合序数偏好作为基础解决方案的现有在线服务评价方法在处理不完整偏好时，通常是仅基于已知偏好进行偏好聚合，并未考虑未知偏好对群体决策的潜在影响，使得已知偏好的代表性成为了影响评价结果质量的重要因素；或是限制用户偏好的表达形式从而降低了评价方法的普适性；或是使用协同过滤工具对未知偏好预先进行填充。然而在实际应用中，其可能会出现冷启动、时间复杂度受限于用户或服务规模的问题，且存在降低评价结果质量的风险。

为解决上述不完整偏好解决方案的潜在问题，本文提出一种面向不完整序数偏好的在线服务评价方法，首先通过定义面向不完整序数偏好的Kendall tau胜者距离(KWD)，实现了在不完整序数偏好场景下的在线服务评价，同时避免了现有方法对用户偏好表达形式的限制；然后开发了关于群体偏好的质量评估算法，以及由Kendall tau胜者距离驱动的偏好抽取策略，用于在需要时评估和快速优化服务评价结果的质量。通过理论分析，并在真实数据集、人工合成数据集上进行实验，验证了所提方法的有效性与合理性。

1 相关工作

近年来，以不同类型的在线服务评价数据为基础，国内外学者分别展开了一系列的服务评价研究。根据不同的服务评价数据类型，可将服务评价方法分为3类[18]：①以数值型评分为基础；②以文本评论为基础；③以序数偏好为基础。

累加法、平均值法两种基于数值型评分的服务评价方法，因其计算效率高、原理容易被用户理解，在电子商务领域中得到了广泛的应用[5]。文献[6]提出一种Beta信誉系统，其将用户的数值型评分与统计学中的β概率密度函数相结合，用于计算候选服务的评级。这类在线服务评价方法假定用户能够在相同的评价准则下对候选服务进行评分，忽视了因用户的评价准则不一致所造成的不同用户对同一服务的评分不可比较的情况，以至于评价结果可能具有误导性和不可靠性[9]。

由于文本评论相比于数值型评分所蕴涵的信息更丰富，使得在使用相同数量的评论数据时，其能提供一个相对更为准确的评价结果。因此，文献[7]提出了HFT(hidden factors as topics)模型，通过综合考虑文本评论数据与数值型评分数据，最终可更准确地对缺失的服务评分进行预测，为个性化的在线服务推荐提供了解决方案。文献[8]提出一种通过分析每个服务的已知文本评论，识别出其所拥有的特性并给出相对应的评分，当用户选择某个特性时，将该特性的评分作为评价指标对候选服务进行排序的评价方法。然而，该类方法仍然是建立在假设所有用户具有相同的评价准则的前提下[18]。

为了解决用户评价准则不一致的问题，文献[10]提出将数值型评分转换为成对的序数偏好，利用Kendall tau距离度量两个偏好之间的距离，使用遗传算法寻找与已知偏好距离最小的最优信誉向量;文献[19]提出一种基于Kendall tau距离的在线服务信誉度量方法，其构建了用户—服务评分矩阵，通过使用模拟退火法，寻找与用户—服务评分矩阵的Kendall tau距离最小的服务信誉向量;文献[20]提出一种基于支配关系的信誉计算模型，其通过多数准则确定候选服务对的支配关系，用于构造一个以候选服务为节点的有向无环图，并在图中寻找一条包含所有候选服务的路径，将其作为最终的服务排名;文献[18]使用协同过滤工具预先对未知的用户评分进行填充，构造完整的用户—服务评分矩阵，然后将评分矩阵转换成偏好关系，最终使用排序对(ranked pair)社会选择函数聚合用户偏好获得服务评价结果。

由于候选服务数量众多、用户认知能力以及隐私因素等问题的存在，使得不完整偏好在现实的在线服务评价中极其常见，而在线服务评价方法则是以所有已知的用户偏好作为输入，计算服务评价结果。因此，在线服务评价方法应当具备在不完整偏好场景下(尤其是用户偏好非常稀疏时)进行在线服务评价的能力。然而，现有研究在不完整偏好场景下进行在线服务评价时存在以下问题：

(1)一部分方法仅基于已知偏好进行偏好聚合，忽视了未知偏好对群体决策的潜在影响，如通过特定的策略构建及求解以服务为节点的有向无环图的评价方法，当已知偏好过于稀疏时，可能会导致无法构建包含所有节点的有向无环图，或者构建的有向无环图缺乏代表性。另一部分评价方法则是对用户偏好的表达形式进行限制，如要求用户必须给出关于所有候选服务的Top-K偏好，给用户附加了多余的认知与计算负担，并使得此类方法在用户所表达的不完整偏好不满足前提条件时会出现无法计算的情况，降低了评价方法的普适性。

(2)基于协同过滤工具的评价方法使得协同过滤的性能成为了影响评价结果质量的重要因素。因为协同过滤首先要求已知偏好具有一定的完整度，否则会出现冷启动等问题，严重影响预测结果的准确性；其次，用户或服务规模的增加将提高预测算法的时间复杂度，给评价方法附加了多余的限制；最后，无论何种评价方法的评价结果本就具有一定的误差，若再使用协同过滤预测未知偏好，相当于引入了二次误差，存在降低评价结果质量的风险。

综上所述，已有研究尚存在仅考虑已知偏好、限制用户偏好的表达形式、使用协同过滤工具预先填充未知偏好，以及假设用户具有相同的评价准则而导致评价结果具有误导性的问题，有必要研究性能更稳定、高效的服务评价方法。

2 问题定义

为方便描述不完整序数偏好场景下的在线服务评价问题，首先对相关概念定义如下：

定义1集合S={s1,s2,…,sm}为所有候选在线服务的集合，集合U={u1,u2,…,un}为所有用户的集合。其中：m为候选在线服务的数量，n为用户的数量。

定义2γh是从集合S中选出m个候选服务构成的一个由优至劣的排列；集合Γs={γh|h∈{1,2,…,m!}}是由所有可能的排列γh所构成的集合，即关于集合S的全排列序数偏好的集合，|Γs|=m!。例如，当m=3时，Γs={(s1,s2,s3),(s1,s3,s2),(s2,s1,s3),(s2,s3,s1),(s3,s1,s2),(s3,s2,s1)}，|Γs|=6。

定义3P={p1,p2,…,pn}为n个用户的已知序数偏好集。其中px是由|px|个成对偏好关系构成的关于用户ux的已知序数偏好，px⊆{(si,sj)|i,j∈{1,2,…,m},i≠j},且0≤|px|≤m(m-1)/2；若存在(si,sj)∈px则表示用户ux认为si优于sj,记为si≻xsj，且(sj,si)∉px。

当|px|=m×(m-1)/2时，表示用户ux的已知序数偏好px为完整序数偏好；当1≤|px|

定义4V={v1,v2,…,vn}为n个用户关于m个候选服务的完整序数偏好集，其中vx为用户ux的完整序数偏好，vx∈Γs；vx(si)表示si在用户ux偏好中的位置，若用户ux认为si≻xsj，则vx(si)

定义5C(px)是由以px作为基础，拓展出的所有可能的vx所构成的关于用户ux的潜在完整序数偏好集合；C(P)=C(p1)×C(p2)×…×C(pn)是由以P作为基础，拓展出的所有可能的V所构成的关于所有用户的潜在完整序数偏好集的集合。

例如，当m=3,n=2且p1={(s3,s1)},p2{(s2,s1),(s1,s3),(s2,s3)}时，则C(p1)={(s2,s3,s1),(s3,s2,s1),(s3,s1,s2)}，C(p2)={(s2,s1,s3)}；C(P)={{(s2,s3,s1),(s2,s1,s3)},{(s3,s2,s1),(s2,s1,s3)}，{(s3,s1,s2),(s2,s1,s3)}}且有|C(P)|=|C(p1)|×|C(p2)|=3，即若以当前的P作为基础，则可拓展出3种不同的V。

定义6KR=(ki|i∈{1,2,…,m})为以P作为基础评价数据所计算出的关于候选服务集合S中的所有候选服务的群体偏好，即服务评价结果。其中ki为候选服务si的有效评价值，若ki

本文所提方法能够直接以不完整序数偏好作为输入进行在线服务评价，且不限制用户偏好的表达形式，同时也不需要协同过滤工具对用户偏好进行预先填充。本文还设计了用于评估群体偏好(KR)质量的评估算法，当用户需要且KR质量未达要求时，可通过应用偏好抽取策略向用户进行少量但关键的偏好查询，适当地丰富已知序数偏好集P，从而快速优化KR的质量。

3 基于Kendall tau距离的在线服务评价

在线服务的实际应用场景中，庞大的候选服务数量使得不完整偏好已经成为了极其常见的现象。不同于现有的在线服务评价方法处理不完整偏好的解决方案，本文受到Kendall tau距离原始定义的启发，对其进行了拓展。首先，定义了完整序数偏好场景下的KWD，将其用于量化每个候选服务的质量；然后，将KWD拓展至不完整序数偏好的场景，并设计了相应的服务排序算法，用于计算服务评价结果KR，解决了现有评价方法在不完整序数偏好场景下进行服务评价的局限性；另外，由于在以P作为基础评价数据计算KR时，每个候选服务si均存在大量不同的可能有效评价值ki，且其规模通常均为阶乘级别，本文通过分析序数偏好的结构特点以及KWD的计算特点，开发了可快速计算有效评价值ki的算法，最终实现了能够直接以不完整序数偏好作为输入，并快速计算出相应的服务评价结果KR的在线服务评价方法。

3.1 面向完整序数偏好的KWD

以各种距离作为度量指标，寻找与所有个体偏好距离最小的群体偏好是解决偏好聚合问题的常见且被广泛应用的方案[15]。其中，以Kendall tau距离为基础的Kemeny方法[21]是解决偏好聚合问题的经典方法。然而，求解Kemeny排序是一个NP难问题，由于原始的Kendall tau距离仅能被用于衡量2个完整序数偏好之间的差异程度，即计算它们之间的逆序数作为距离值[22]，从而造成了Kemeny方法要求个体偏好必须为完整序数偏好。

本文以Kendall tau距离的核心思想，即利用逆序数计算差异为基础，定义了KWD来衡量每个候选服务成为群体偏好中的胜者的距离，而不是像原始的Kendall tau距离一样去衡量两个完整序数偏好之间的差异程度，为后续将KWD拓展至不完整序数偏好的场景提供了条件。

首先，通过假定si为群体偏好中的最优候选服务(胜者)，表示其在群体偏好中一定优于其他的所有候选服务。因此，可通过统计当前假定胜者si与其他所有候选服务在用户偏好vx中的逆序关系对的数量，即vx中优于si的候选服务数量，将其作为用户ux关于si的Kendall tau胜者距离，即uKWD(si,vx)。随后将每个用户关于si的Kendall tau胜者距离进行求和，并将结果作为所有用户关于si的Kendall tau胜者距离，即

(1)

(2)

式(1)中的1(…)为计数器，当vx中存在sj≻xsi偏好关系时返回1，否则返回0。

例如，当m=4且用户ui的v1=(s1,s2,s3,s4)时，若计算uKWD(s3,v1)：首先需假定s3为群体偏好中的胜者，则可推导出在群体偏好中存在如下包含s3的偏好关系对{(s3≻s1),(s3≻s2),(s3≻s4)}；其次根据v1可推导出如下包含s3的偏好关系对{(s1≻s3),(s2≻s3),(s3≻s4)}；最后统计上述2个偏好关系对集合中不一致的偏好关系对的数量，即逆序关系对的数量，其结果即为uKWD(s3,v1)，因此有uKWD(s3,v1)=2。最终仅需将所有用户的uKWD(s3,vx)进行求和，其结果即为KWD(s3,V)。

当以完整序数偏好集V为基础评价数据求解群体偏好时，仅需将每个候选服务的KWD值作为基准，并将所有候选服务按照由小至大的规则排列，即可形成关于所有候选服务的群体偏好，不存在计算困难的问题。

3.2 面向不完整序数偏好的KWD以及在线服务排序

为了使KWD能够基于不完整序数偏好的场景进行在线服务评价，以及为后续的质量评估算法与偏好抽取策略提供条件，需分别求解每个候选服务在P作为基础评价数据时的最大与最小KWD，记为MaxK(si,P)与MinK(si,P)：

(3)

(4)

式(3)中的MaxK(si,P)表示候选服务si在P中的最大KWD；式(4)中的MinK(si,P)表示候选服务si在P中的最小KWD。

由于KWD是基于距离的概念对每个候选服务的质量进行量化，KWD值越大，则表示该候选服务的质量越差，即成为胜者的可能性越小;反之亦然。

在不完整序数偏好的场景中，评价一个候选服务的优劣，存在大量的不确定因素，为了确保评价结果的稳定与准确，应使用其最低质量作为评价指标，而不是最高质量。因此，本文将每个候选服务的最大KWD作为该候选服务的有效评价值，即ki=MaxK(si,P)，并将该值作为排序因子，对所有候选服务按由小至大的规则排列，形成关于所有候选服务的群体偏好KR，即为在线服务排序结果。

3.3 最大与最小KWD计算

以P作为基础评价数据计算每个候选服务的最大或最小KWD时，均需从规模为|C(P)|=|C(p1)|×|C(p2)|×…×|C(pn)|的解空间中分别寻找到可令每个候选服务的KWD最大或最小化的V∈C(P)，然而C(P)的规模由P的稀疏程度决定，P越稀疏,C(P)的规模越大,且常为阶乘级别。若使用穷举法求解，将导致最大与最小KWD计算时间复杂度非常高。

因此，本文通过分析序数偏好的结构特点以及KWD的计算特点，设计了可快速计算每个候选服务si的最大与最小KWD的算法，构造了用户的已知序数偏好px基于si的拓扑结构，如图1所示。

由图1可见，px被划分为3个集合且|W|+|L|+|UK|=m-1：集合W={sj|(sj,si)∈px,sj∈S/si}，即集合W中所有候选服务均优于si；集合L={sj|(si,sj)∈px,sj∈S/si}，即集合L中的所有候选服务均劣于si；集合UK={sj|(sj,si)∉px∧(si,sj)∉px,sj∈S/si}，即集合UK中所有候选服务与si的优劣关系未知。

计算每个候选服务的最大或最小KWD时，首先需要分别计算每个用户关于该服务的最大或最小uKWD，然后仅需将所有用户关于该服务的最大或最小uKWD进行求和，即为该候选服务的最大或最小KWD：

(5)

(6)

式(5)为用户ux关于候选服务si的最大uKWD的计算公式；式(6)为用户ux关于候选服务si的最小uKWD的计算公式。

在计算最大和最小uKWD的过程中，由于uKWD的计算特点，无需关注集合W、L、UK中候选服务的具体偏好关系，仅需计算集合W与UK中的候选服务数量即可。

基于P计算任意一个候选服务si的最大与最小KWD时，首先需要以每个用户的px为基础，将集合S/si中的所有候选服务与si逐一进行比较，并将它们分类至集合W或L或UK中，从而计算出当前用户ux关于候选服务si的最大与最小uKWD，其时间复杂度为O(m)；然后，将所有用户关于候选服务si的最大与最小uKWD进行求和，获得候选服务si的最大与最小KWD，其时间复杂度为O(nm)。

基于P计算群体偏好KR时，需要分别计算每个候选服的有效评价值(最大KWD),并以此为基础求解KR，其时间复杂度为O(nm2+nlogn)。

4 质量评估算法与偏好抽取策略

群体偏好KR是以当前的P作为基础评价数据，并执行第3章提出的基于KWD在线服务评价方法所计算出的服务评价结果，但是针对一些对在线服务评价结果精度要求较高的场景，本文设计了用于评估KR质量的质量评估算法，以及由KWD驱动的偏好抽取策。当条件允许且用户需要时，可通过质量评估算法对KR的质量进行评估，若未能达标，则表示当前KR的质量存在进一步优化的空间。因此可通过向部分参与评价的用户执行偏好抽取策略，即通过偏好查询的方式向用户获取少量但关键的偏好信息用于快速优化服务评价结果KR的质量。

4.1 群体偏好KR的质量评估算法

以P作为基础评价数据计算出相应的KR后，可使用质量评估算法评估当前KR的质量是否达标。当质量未达标时，则可通过执行偏好抽取策略，提高KR的质量；当质量达标时，则应终止偏好抽取策略即时输出KR，且此时的KR已为近似最优解。

定义7初始Kendall tau胜者候选服务集合KWS={s1,s2,…,sm}，预设质量等级参数(QCP)，且1≤|KWS|≤m，1≤QCP≤m-1。

其中，集合KWS内的候选服务为KR中的Top-|KWS|候选服务(前|KWS|名候选服务)，且集合KWS中候选服务的MaxK(si,P)均小于集合S/KWS内所有候选服务的MinK(si,P)，即在最终的KR中，集合KWS内的候选服务一定优于集合S/KWS内的所有候选服务。

通过每个候选服务当前的MaxK(si,P)和MinK(si,P)维护KWS集合，并使用|KWS|的值表示当前KR的质量等级，用于判断KR的质量是否达标，以及决策是否需要执行偏好抽取策略。当|KWS|>QCP时，则当前KR的质量未达标，需继续执行偏好抽取策略；当|KWS|≤QCP时，则当前KR的质量已达标，可终止偏好抽取策略即时输出KR。QCP设置得越小，则最终KR的质量等级越高，反之亦然。

根据QCP以及每个候选服务当前的MaxK(si,P)和MinK(si,P)维护KWS并评估KR质量的具体过程，如算法1所示。

算法1群体偏好KR的质量评估算法。

输入：当前的P、KWS集合，QCP;

输出：False或Ture，False表示当前KR的质量未达标，Ture表示当前KR的质量已达标。

// ks1、ks2仅为程序中的普通变量

1. 找出KWS中MaxK(si,P)最小的候选服务，并记为ks1

2. for ks2∈KWS:ks1≠ ks2do

3. if MaxK(ks1,P)

4. KWS.remove(ks2)；//从集合KWS中删除ks2

5. end if

6. end for

7. if|KWS|≤QCP then

8. return Ture //当前KR质量已达标

9. else return False //当前KR质量未达标

10. end if

质量评估算法通过求解每个候选服务当前的MaxK(si,P)和MinK(si,P)以维护KWS集合。然而由于MaxK(si,P)的取值范围为0≤MaxK(si,P)≤n×(m-1)，P越稀疏时，MaxK(si,P)的初始值将越接近n×(m-1)，而MinK(si,P)越接近0，从而导致需要获取大量的用户偏好数据，才能使KR的质量达标。然而，本文目标是希望使用尽可能少的用户偏好数据即能计算出高质量的KR，以及可以根据不同的需求灵活地控制所使用的用户偏好数据量。因此，定义了MaxK(si,P,IUK)*，通过使用实时更新的全局参数IUK对MaxK(si,P,IUK)*的初始取值上限进行了限定，并在质量评估算法中使用MaxK(si,P,IUK)*代替MaxK(si,P)，缩小了求解质量达标的KR的原始解空间规模，算法仅需基于缩小后的解空间计算局部最优解即可。

MaxK(si,P,IUK)*=MaxK(si,P)×IUK。

(7)

式中IUK是一个实时更新且用于控制在计算局部最优解时的解空间规模的全局参数，对于所有候选服务均存在统一且实时更新的IUK，0

因此可知，若基于式(3)求解质量达标的KR，则其原始解空间的规模应为m×(n×(m-1))，而若在算法1中使用式(7)代替式(3)，即通过设置全局参数IUK进行局部求解，则可将原始解空间规模缩小为m×(n×(m-1)×IUK)。

同时，为了保证算法的准确率与效率，需根据不同的IUK设置不同的QCP：即IUK越小，所使用的用户偏好数据也越少，应提高质量等级以保证最终KR的质量；而IUK越大，则所使用的用户偏好数据也越多，应适当地降低质量等级以提高算法的计算效率。因此，需将QCP按照QCP=(m-1)×IUK的规则设置预设值。

另外，当出现任意一个候选服务si满足如下关系式，即gi>n×(m-1)×IUK时，其中gi=MinK(si,P)+(n×(m-1)-MaxK(si,P))，则表示当前的解空间过小，不足以计算出质量达标的KR，需通过提高IUK扩大解空间规模。因此，需按照IUK=gi/(n×(m-1))的规则实时地更新IUK，从而更新所有候选服务的MaxK(si,P,IUK)*。

在实际应用中，可根据不同的需求设置不同的IUK初始值，其值的大小决定了在计算局部最优解时所需搜索的解空间规模，即可通过IUK灵活地控制使用的用户偏好数据量：IUK越小，解空间规模越小，即允许忽略越多的用户偏好数据，使得求解质量达标的KR所需的用户偏好数据也越少；而IUK越大，解空间规模就越大，所需的用户偏好数据也越多。

4.2 KWD驱动的偏好抽取策略

偏好抽取策略通过分析已知的偏好信息和所使用的评价方法的特点，向用户生成有效的偏好查询，适当地提高不完整偏好的完整程度，辅助评价方法基于优化后的不完整偏好计算出准确的胜者或群体偏好。

然而，对于Borda计数、Copeland等可用于服务评价的社会选择机制，计算哪些用户偏好需要被抽取，即向用户生成哪些偏好查询才能有助于社会选择机制计算出准确的胜者是一个NP难问题[12]。尽管如此，却并不代表偏好抽取不具有实际应用的意义,可通过将计算高概率的胜者作为应用偏好抽取的目的，而不是计算准确的胜者[12]。

为了让偏好抽取策略的应用具有实际可行性，首先需要设计与所使用的评价方法相符且有效的质量评价指标(针对每个候选服务)；其次以该质量评价指标作为目标函数，通过分析已知偏好信息，向用户生成有效的偏好查询，优化该目标函数值, 从而尽快计算出近似最优解；最后设置合适的基准评估当前胜者或群体偏好的质量，用于判断是否终止偏好抽取策略(即最终胜者或群体偏好是否达到近似最优解)。

本文提出了由KWD驱动的偏好抽取策略，使用每个候选服务的最大与最小KWD作为该候选服务的质量评价指标。通过实时地分析当前的P以及每个用户的px，分别针对每个用户生成一个高效且稳定的成对比较查询，用于快速缩小该用户关于目标候选服务的最大uKWD或提高最小uKWD。使用4.1节中的质量评估算法1，评估当前群体偏好KR的质量是否达标。若算法1的返回值为False，则表示KR的质量未达标，需重复执行上述偏好抽取策略；若返回值为Ture，则表示KR的质量已达标，无需继续执行偏好抽取策略。

如何生成有效的偏好查询是偏好抽取策略的核心问题，本文使用成对比较作为偏好查询的类型，其由两个候选服务构成(st≻xsh)，其中st为目标候选服务，sh为最大效用候选服务。

因此，首先定义了uUKN(si,px)，表示在不完整序数偏好px中与候选服务si优劣关系未知的候选服务的数量(user Unknow Number, uUKN)；然后定义了UKN(si,P)，表示通过将每个用户的uUKN(si,px)进行求和计算在当前P中候选服务si的未知量(Unknow Number, UKN)；最后以当前的P作为基础评价数据，选择集合S中UKN最大的候选服务，并将其作为目标候选服务st：

uUKN(si,px)=|UK|，

(8)

(9)

(10)

在确定了st后，还需以px和st为基础，构建当前待查询用户ux的集合UK，并在UK中寻找可令用户ux关于st的最大或最小uKWD大幅度缩小或提高且稳定的最大效用候选服务sh。

因此，首先定义了Anc(si,px)表示在集合UK中优于si的已知候选服务数量，即si的前驱(Ancestors)数量，以及Des(si,px)表示在集合UK中劣于si的已知候选服务数量，即si的后继(Descendants)数量；然后定义了PotS(px)，其是由集合UK中前驱与后继的数量相同或仅相差±1的中位候选服务构成的集合；最后在集合PotS(px)中选择Anc(si,px)最大的候选服务，并将其作为最大效用候选服务sh：

(11)

(12)

PotS(px)={si|-1≤Anc(si,px)-

Des(si,px)≤1,si∈UK},

(13)

(14)

其中，式(11)和式(12)中的1(…)为计数器，当括号中的关系式为真时返回1，否则返回0。

例如，若当前px的集合UK={s1,s2,s3,s4,s5,s6,s7}，且由px可推导出序数偏好s2≻xs3≻xs4，s1≻xs3≻xs4，s5≻XS6≻xs7，则集合PotS(px)={s3,s6}，sh=s3。

另外，集合PotS(px)中的候选服务均为中位候选服务，即前驱与后继的数量相同或仅相差±1的候选服务，因此保证了对于生成的偏好查询st≻xsh，无论用户的回答是肯定或否定，均能有效地缩小或提高最大或最小uKWD，达到快速且稳定地提高KR质量的目标。

将质量评估算法1与由KWD驱动的偏好抽取策略相结合，计算最终服务评价结果KR的具体过程如算法2所示。

算法2最终服务评价结果KR的算法。

输入：初始的P、KWS、全局参数IUK;

输出：最终的群体偏好KR，即最终服务评价结果。

1. while算法1==False do //调用算法1，并根据返回值判断当前KR的质量是否达标

2. for x=1 to n do //遍历用户集合U中的所有用户

3. 基于式(10)与式(14)分别计算用户ux的st与sh

4. 向用户进行偏好查询，并更新px

5. end for

6. end while

7. returnKR//输出最终的群体偏好KR

5 实验

根据第3章提出的基于KWD的在线服务评价方法以及第4章提出的质量评估算法与偏好抽取策略，设计实现了面向不完整序数偏好的在线服务评价方法并进行实验分析。实验环境为PC机、Windows 10系统、Core i5处理器、8 GB内存。另外，为保证实验结果的准确性，所有实验均被重复运行30次，并取每个指标的平均值作为实验结果。

为验证本文方法的有效性和效率，实验分别采用AGH、Dublin、Sushi真实数据集以及Mallows[23]人工合成数据集。其中：AGH数据集由146条关于9门课程的完整序数偏好组成。Dublin数据集由3 800条关于9位候选人的完整序数偏好组成。Sushi数据集由5 000条关于10种寿司的完整序数偏好组成。Mallows是一个在序数偏好研究中被广泛应用及认可的偏好模型[24]，其可通过设置不同的参数σ与φ，随机生成属于各类不同分布情况下的序数偏好数据集，其中σ为一个由m个候选服务构成的完整序数偏好；φ∈(0,1]为离散参数，其控制了随机生成的用户序数偏好与σ的离散程度，当φ→0时，所生成的用户序数偏好均完全一致，当φ=1时，所生成的用户序数偏好则为一个均匀分布。通过设置不同的φ、用户数量n、服务数量m得到的Mallows人工合成数据集，用于验证本文方法的普适性、有效性以及效率。

首先，本文分别以上述完整数据集为基础随机生成了相对应的且偏好完整度为5%、10%、15%、20%、25%的不完整数据集，并以此作为评价方法的初始输入P；然后，分别设计了2个在线服务评价方案(记为方案F1、方案F2)用于进行实验：其中方案F1直接将当前已知的不完整数据集P作为输入，然后仅使用本文第3章所提出的基于KWD的在线服务评价方法计算在线服务评价结果KR；方案F2则是在方案F1的基础上配合执行在第4章提出的质量评估算法与偏好抽取策略(即执行算法2)，希望通过进行少量但关键的偏好查询实现对服务评价结果KR质量的快速优化。在利用方案F2进行实验时：会将完整数据集视为待查询数据集，即将每条序数偏好模拟为一个用户，用于回答偏好抽取策略所生成的偏好查询；同时还会按照如下规则设置全局参数IUK的初始值，例如，若不完整数据集初始的完整度为5%，则将全局参数IUK设置为0.1、若初始偏好完整度为10%，则将全局参数IUK设置为0.15。

5.1 有效性实验

基于Kemeny社会选择机制计算的Kemeny排序是真相排序的最大似然估计，其不仅在群体决策中得到广泛应用[25]，还被用于服务评价并取得良好效果[10,19]。因此，实验将Kemeny方法作为实验比较的基准方法，将本文方法所计算的KR与Kemeny排序相对比，计算它们之间的相似度，用于验证本文方法的有效性。

实验首先使用Kemeny方法基于每个数据集的完整序数偏好计算相应的Kemeny排序，并将其作为精确最优解(Exact Optimal Solution, EOS)；然后分别应用方案F1与方案F2计算服务评价结果KR；最后使用Kendall tau距离度量KR与EOS之间的相似度，记为S(KR,EOS)。S(KR,EOS)越大，KR与EOS越相似，即KR与EOS之间的Kendall tau距离越小，反之亦然。

实验首先基于AGH、Dublin、Sushi数据集分别执行了方案F1和F2，并记录了在初始偏好完整度为5%、10%、15%、20%、25%时的S(KR,EOS)，如图2a所示；然后采用5个离散参数φ值，在包含10个候选服务、100个用户的Mallows数据集分别执行方案F1和F2，并记录在初始偏好完整度为5%、10%、15%、20%、25%时的S(KR,EOS)，如图2b所示。

由图2可见，不论是在AGH、Dublin、Sushi数据集，还是5个Mallows数据集中，方案F1仅依据初始的不完整数据集就能够直接计算出较高的S(KR,EOS)的服务评价结果，并且在应用方案F2后可以发现最终的S(KR,EOS)也会较方案F1有所提高。另外，由图2b可见，除了数据集的初始偏好完整度会影响S(KR,EOS)的高低之外，数据集的离散参数φ也是影响S(KR,EOS)的主要因素，随着离散参数φ增大至接近1时(即用户偏好趋于均匀分布)，若单纯应用方案F1,可能导致S(KR,EOS)出现下降，但可通过应用方案F2在一定程度上缓解该问题。另外，根据文献[12]和文献[24]的结论可知，在现实中用户偏好的离散参数φ并不会趋于1(即用户偏好不会符合均匀分布)，通常为φ≤0.7，从而也进一步说明了本文方法的有效性。

同时，还生成了25个关于不同用户数量n和不同服务数量m，初始偏好完整度为5%，参数φ为0.7的Mallows数据集，用于验证本文方法在不同样本规模下的有效性，如图3所示。

由图3可见，不论是方案F1还是F2，均会随着用户数量n的增加使得S(KR,EOS)增加；而随着服务数量m的增加，S(KR,EOS)并不会发生明显的下降。考虑到在线服务场景中的用户数量和服务数量通常较大且会动态地发生变化，S(KR,EOS)只会因用户数量的增加而增加，并不会因服务数量的变化而导致S(KR,EOS)明显下降，该结果进一步验证了本文方法对在线服务评价的有效性。

此外，为了分析本文方法在用户偏好差异较大时的有效性，基于原始的Kendall tau距离定义了DIFF(vx,vy)=KT(vx,vy)/(m×(m-1)/2)，用于计算两个用户偏好之间的差异程度。其中，KT(vx,vy)为vx与vy之间的逆序数，即vx与vy的真实Kendall tau距离；(m×(m-1)/2)为vx与vy的逆序数取值上限，即vx与vy的理论最大Kendall tau距离。由此可见，DIFF(vx,vy)越大，vx与vy之间的差异也越大，反之亦然。

因此，实验以5个采用不同参数φ且包含10个候选服务、5 000个用户的Mallows数据集为基础。通过对每个数据集均进行5 000次的随机抽样，每次随机选取2个用户，并计算出相应的DIFF(vx,vy)，用于反映该数据集中的用户偏好之间的差异程度，如图4所示。

由图4可见，在Mallows数据集中，随着参数φ的增加，用户偏好之间的差异程度也会逐步扩大。由图2b可知，S(KR,EOS)虽然会因参数φ的增加而发生下降，在参数φ=0.9时，即使仅执行方案F1，S(KR,EOS)仍能够保持在80%以上，并且当执行方案F2时，S(KR,EOS)能够被提高至85%左右。另外，根据图3的结果可知，在使用方案F1进行服务评价时，随着用户数量的增加，S(KR,EOS)也会随之增加且提升明显，考虑到真实的互联网应用场景中的用户数量总是较多且增长较快，说明本文方法即使在用户偏好差异较大时除了可以通过执行方案F2提高评价结果质量，还能依靠用户数量的增加来缓解因用户偏好趋于均匀分布而造成的评价结果质量下降的问题。

5.2 偏好完整度实验

为验证本文方法在处理不完整序数偏好时的性能，实验首先基于AGH、Dublin、Sushi数据集执行方案F2，并记录了在初始偏好完整度为5%、10%、15%、20%、25%时计算最终服务评价结果KR所使用的偏好完整度，如图5a所示；然后采用5个φ值，在包含10个候选服务、100个用户的Mallows数据集执行方案F2，并记录了在初始偏好完整度为5%、10%、15%、20%、25%时计算最终服务评价结果KR所使用的偏好完整度，如图5b所示。

由图5可见，不论是在AGH、Dublin、Sushi数据集，还是5个Mallows数据集，PI(n,m,P)均会与初始全局参数IUK保持较小的差距。在大多数情况下PI(n,m,P)会小于IUK的初始值，仅在少数情况PI(n,m,P)会大于IUK的初始值，这是因为IUK是一个能够实时自动更新的全局参数，如果出现因IUK的初始值设置过小而导致解空间过小，无法计算出质量达标的KR时，IUK会通过自动更新并扩大解空间以完成求解。另外，由5.1节中的实验结果可知，按照预设规则设置IUK就已经能够实现高质量的求解，仅在少数的情况下，例如当用户偏好趋于均匀分布且用户数量也较少时才可能需要考虑通过提高IUK来提升最终服务评价结果KR的高质量。

5.3 性能测试

为验证本文方法的效率，实验首先基于AGH、Dublin、Sushi数据集分别执行方案F1和F2，并记录了初始偏好完整度为5%、10%、15%、20%、25%时计算最终服务评价结果KR的运行时间，如图6a所示；然后采用5个φ值，在包含10个候选服务、100个用户的Mallows数据集分别执行方案F1和F2，并记录初始偏好完整度为5%、10%、15%、20%、25%时计算最终服务评价结果KR的运行时间，如图6b所示。

由图6可见，不论是在AGH、Dublin、Sushi数据集，还是5个Mallows数据集中，方案F1和F2均能保持较高的运行效率，虽然运行时间会随着数据集的初始偏好完整度或者离散参数φ的提高而增加，但是并不会导致运行时间剧增。

此外，本文还生成了25个关于不同用户数量n和不同服务数量m，初始偏好完整度为5%，参数φ为0.7的Mallows数据集，用于验证本文方法在不同样本规模下的效率，如图7所示。

由图7可见，随着用户数量和服务数量的增加，方案F1和F2的运行时间均随之增加，但是在大多数情况下它们均能保持线性增长。考虑在线服务评价场景中用户数量和服务数量通常较大，该结果进一步验证了本文方法对在线服务评价的计算有效性。

6 结束语

本文提出一种面向不完整序数偏好的在线服务评价方法，以解决不完整序数偏好场景下的在线服务评价问题。方法通过定义KWD来量化每个候选服务的质量，并设计了基于KWD的近似算法用于计算服务评价结果KR，从而实现了在不完整序数偏好场景下的在线服务评价。同时还设计了质量评估算法与偏好抽取策略，用于在需要时评估和快速优化服务评价结果KR的质量，为不完整序数偏好场景下的在线服务评价提供了一种新的思路。理论分析及实验验证表明了该方法的有效性与合理性。但是，本方法在进行在线服务评价时并未考虑用户偏好可能会出现平局的情况，即用户可能会认为2个或多个候选服务之间无优劣差异。因此，下一步的工作将结合平局的情况，研究更加通用的在线服务评价方法。