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

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

Table 2 Satisfaction matrix of user-service
表 2 用户-服务满意度矩阵
在线服务
用户
s 1 s 2 s 3 s 4
u 1 3 2 1 0
u 2 3 1 2 0
u 3 3 0 1 2
3 2 0 1
u 4
u 5 1 3 2 0
u 6 0 1 3 2

3.2 基于Monroe规则的Top-k在线服务评价
给定 n 个用户、m 个在线服务以及所有用户对在线服务的偏好排序,本文提出的 Top-k 在线服务评价方法
首先依据第 3.1 节中介绍的满意度计算方法计算用户-服务满意度矩阵,然后利用 Monroe 规则返回指定数量的
Top-k 在线服务集合.该方法将用户按比例动态地分为 k 组,每组最多包含⎡n/k⎤个用户,每个用户分别被分配给一
个在线服务作为该用户的代表,并计算用户满意度,且每个服务最多只能代表⎡n/k⎤个用户,或者不能作为代表.
寻找在分配过程中最大化用户群体满意度的 k 个在线服务作为评价结果.
根据上述 Monroe 规则的分配思想,可借助集合间的映射关系来理解.用户集合 U 中每个用户 u i ,在服务集
合 S 中均有唯一在线服务 s j 与之对应,建立从用户集合 U 到在线服务集合 S 的多对一映射,记为 f:U→S.当 k=m
时,映射 f 为满射;当 k<m 时,该映射为非满射.在线服务集合 S 中,某个在线服务 s j 代表 n/k 个用户,或者不代表任
何用户,即⎣n/k⎦≤n′(s j )≤⎡n/k⎤或 n′(s j )=0.其中,n′(s j )表示在映射中服务 s j 对应的集合 U 中的用户数量.结合例 1
得到可能的一个映射如图 1 所示.

u 1
s 1
u 2
s 2
u 3
u 4
s 3
u 5
u 6 s 4

Fig.1 Mapping of set U to set S
图 1 集合 U 到集合 S 的映射

由图 1 的映射过程可知,基于 Monroe 规则的 Top-k 在线服务评价可以理解为建立集合 U 到集合 S 的一种
可能的最佳映射.最佳映射为集合 U 中的用户匹配集合 S 中的 k 个在线服务所得用户群体满意度最大时的对应
关系.聚合映射中所有用户对 Top-k 在线服务集合的满意度得到用户群体满意度,即用户群体满意度为每个用
户对应的其代表服务的满意度的累加结果.用户群体满意度计算公式如公式(3)所示.
n
A ( )Φ Sat ij ( pos i ( ( )))iΦ = ∑ (3)
i= 1
其中,Φ表示局部分配任务,Φ(i)表示能代表用户 u i 的在线服务,pos i (Φ(i))表示能代表用户 u i 的服务在用户 u i 的
偏好排序中的位置.
基于上述分析,我们可以为 Top-k 在线服务评价建立一个最优化模型.其中,
• 变量 s ij 表示在线服务 s j 能否代表用户 u i :能代表,用 1 表示;不能代表,用 0 表示.
• 变量 x j 表示在线服务 s j 是否在 Top-k 在线服务集合中,取值为 0 或 1:在集合中,则用 1 表示;不在集合
中,用 0 表示.
最优化模型用数学公式表达如公式(4)所示.
n
A
max ( )Φ = ∑ Sat ij ( pos i ( ))s j s ij (4)
i= 1