Page 69 - 《软件学报》2021年第11期

赵时海 等:用户群体满意度最大化的 Top-k 在线服务评价 3395

4. bests=[⋅];
5. FOR s j ∈S\Φ ←
←
6. users=sort U\Φ ;
7. bests[s j ]=取 users 中前 n/k 个用户;
8. score ()s = j ibests [ j s ] (m − ∑ pos i ( ))s j ;
∈
9. END FOR
10. S best = argmax j s ∈ \ S Φ ← score [ ]s ;
j
11. FOR i∈bests[S best ] DO
12. W[i]=S best ;
13. END FOR
14. END FOR
15. RETURN W
MGA 算法首先需要执行 k 次迭代;然后,在 k 次迭代过程中执行次数最多的步骤为遍历所有在线服务 m 次;
最后,在每次遍历在线服务的过程中,采用堆排序算法对用户进行排序的时间复杂度为 O(nlogn).综上,MGA 算
法总的时间复杂度为 O(kmnlogn).因此,该算法能够在多项式时间内计算 Top-k 在线服务评价结果.
通过分析 MGA 算法,每个用户对其分配的在线服务代表具有 1−(k−1)/(2(m−1))−H k /k 的平均偏好程度 [13] ,
进一步推论可得,用户群体满意度的理论下界比值为 1−(k−1)/(2(m−1))−H k /k.其中,H k 表示第 k 次的调和级数,
k ∑
H = k i= 1 1 i .由该理论值分析可知,当 Top-k 在线服务评价的 k 值较大时,用户群体满意度受 H k /k 值影响较小.因
此,当 k 值较大时,MGA 算法的用户群体满意度下界比值主要与(k−1)/(2(m−1))相关.从这个角度说,方法在考虑
用户群体满意度的同时综合考虑了用户个体的满意度.

4 评价模型满足的属性分析
本文将 Top-k 在线服务评价建模为一个 Monroe 代表的选举过程.在这一节中分析贪心策略下的 Monroe
规则的 3 个公平属性:用户意见平等性、联盟稳定性和集体一致性.
4.1 用户意见平等性

目前,大多数 Top-k 在线服务评价(例如,Yelp 网站十大最受欢迎餐厅的评选)可直观地归类为一种特殊的加
权投票选举系统 [25] ,也称简单多数投票 [26] .用户可以为任意数量的餐厅进行多次投票,获得最多投票的餐厅将
被选中进行推荐.因此,活跃的用户比不活跃的用户更容易影响评价结果.为避免上述问题,本文方法在进行服
务评价时,平等地对待所有用户,这个性质在社会选择理论中也称为匿名性 [27] .为实现匿名性,要求每个用户给
出其对一组在线服务的偏好排序,且 Top-k 在线服务评价结果与用户的先后次序无关,充分保障每个用户的意
见得以公平体现.
对于 Top-k 在线服务评价 f:P→W,若交换每对用户的偏好排序,即交换用户 u i 与任意用户 u′ 在用户群体偏
i
好 P 中的先后顺序得到 P′,由 f:P→W 与 f:P′→W 获得的用户群体满意度相同,则说明 f:P→W 满足用户意见平等
性.本方法的一个关键步骤是:根据同一服务 s j 在不同用户的用户偏好序中的位置对用户进行排序,位置靠前的
用户排在位置靠后的用户前.若用户对应服务 s j 的位置相同,则采用随机法对用户进行排序.因此,方法的评价结
果与用户在偏好序 P 中的先后次序无关,说明该方法满足用户意见平等性.用户意见平等性是公平对待每个用
户的必要条件,可避免部分用户独裁决定在线服务评价结果.
4.2 比例代表性

在实际的在线服务场景中,Top-k 在线服务评价方法选择 k 个在线服务代表用户群体,若少数用户喜欢但多
数用户不喜欢的服务被选中,会使评价结果缺乏公平性.比如 Yelp 点评网站推荐给用户群体 k 家餐厅,若其中一