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

3392 Journal of Software 软件学报 Vol.32, No.11, November 2021

择结果达成最大的一致性,即用户群体满意度尽可能大.

3 用户群体满意度最大化的 Top-k 在线服务评价
Monroe 规则是代表制规则中一种非常有效的多胜者选举规则,最初被用于社会选择理论多胜者选举 [12] .给
定 n 个选民、m 个候选人,该规则在候选人中寻找最能代表选民的 k 个胜者,使获得的多胜者集合中每个候选人
均能代表等量的选民.其核心思想是:动态地将选民分为 k 部分,每部分包含 n/k 个用户,每部分由一名候选者代
表,使获得的 k 个候选者代表最大程度地体现选民的意愿,并保证选民群体满意度最大化,尽可能保证选举的公
平性及客观性.
目前,Monroe 规则被广泛应用于资源分配及推荐系统等领域 [13] ,其具有用户意见平等性、联盟稳定性和集
体一致性等公平属性 [23] .考虑到 Monroe 规则的多胜者选举具有 Top-k 在线服务评价场景所期望的上述公平属
性,故我们将 Monroe 应用到在线服务评价领域,辅助用户群体选择能使用户群体满意度最大化的 k 个在线服务.
基于以上分析,为了公平地聚合用户群体对在线服务的偏好得到 Top-k 在线服务集合,本文基于 Monroe 多
胜者选举规则提出了一种 Top-k 在线服务评价方法.方法首先基于用户对在线服务的偏好序列获取用户-服务
满意度分数矩阵,然后借鉴 Monroe 的比例代表思想将 Top-k 在线服务评价转化为一个寻优问题,最终获得的在
线服务集合使用户群体满意程度最大化.
3.1 获取用户对在线服务的满意度
为获取用户群体对 Top-k 在线服务评价集合 W 中服务的用户群体满意度,首先计算所有用户对每个服务的
满意度分数,然后构造用户-服务满意度矩阵.若拥有用户对在线服务完整排序的偏好数据集,则直接采用 Borda
规则 [22] 获取每个用户对在线服务的满意程度.然而,由于在线服务规模非常庞大,用户不可能对所有服务具有交
互经验.对于大量同类型的在线服务,用户通常只能对最偏爱的 Top-t 在线服务进行排序.在此情况下,本文同样
采用该规则计算给定偏好的 t 个在线服务的满意程度,但是对于截断排序中 t 个在线服务以外的服务,默认将其
标记为 s′.通过以上规则,将用户对在线服务的偏好关系转化为用户对在线服务的满意度分数,进而建立用户对
在线服务的满意度矩阵.
定义 4. 用户 u i 对在线服务 s j 的满意度分数表示为 Sat ij ,即用户 u i 对选择服务 s j 作为 Top-k 在线服务结果
的满意程度.所有用户对在线服务的满意度分数用矩阵 Sat=[Sat ij ] n×m 表示.
满意度分数 Sat ij 通过 Borda 规则计算,用参数 t 控制用户偏好排序的完整程度.当 t=m 时,表示用户 u i 对在
线服务有完整的偏好排序.用户 u i 对服务 s j 满意度计算如公式(1)所示.
Sat ij =m−pos i (s j ) (1)
定义 5. 将不包含于用户截断排序 Top-t 中的在线服务均表示为 s′.
当 t<m 时,表示用户 u i 仅对其最偏爱的 t 个在线服务进行部分排序:若服务 s j 包含在用户 u i 的 Top-t 排序中,
则获取该服务在偏好排序中的位置并计算满意度;若服务 s j 不在用户 u i 的 Top-t 排序中,则将该服务记为 s′,且默
认 pos i (s′)=m.用户 u i 对服务 s j 满意度计算公式为
⎧ ⎪ m − pos ( ),s s ∈ {s π | r = 1,2,..., }t
Sat = ⎨ i j j ()r (2)
ij 0, s ∉ | r =
⎪ ⎩ j {s π ()r 1,2,..., } t
其中,pos i (s j )表示在线服务 s j 在用户 u i 的偏好排序中的位置.由于同一用户对在线服务的评价准则相对稳定,因
而其对在线服务的偏好是可以比较的,且对于用户 u i 的服务偏好排序,越靠近排序前端的服务表明用户对其的

偏爱程度越大.因此,借鉴 Borda 规则计算用户对在线服务的满意度分数是合理的.例如:若在线服务 s j 是用户 u i
最喜欢的服务,则 pos i (s j )=1;若在线服务 s j 是用户 u i 最不喜欢的服务,则 pos i (s j )=t.显然,采用公式(2)计算用户-在
线服务满意程度,对于表 1 中的用户 u 1 对在线服务 s 1 ,s 2 ,s 3 ,s 4 的满意程度分别为 3,2,1,0.
分别计算所有用户对全部在线服务的满意度分数得到用户-服务满意度矩阵 Sat=[Sat ij ] 6×4 见表 2.