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

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

• 其次,为保证结果的公平性和合理性,评价结果中的每个服务需具备一定的代表性.
现有工作并未考虑到这两方面,使得其评价结果不适合用户群体共同决策选择出 k 个在线服务的场景.为
此,本文借鉴社会选择理论 [22] 思想,以用户对在线服务的序数偏好信息作为输入,采用 Monroe 规则对 Top-k 在线
服务评价问题进行建模,寻找能使用户群体满意度最大化的服务集合,以实现 Top-k 在线服务评价.

2 问题描述

2.1 问题定义
为更好地阐述并解决用户群体选择指定 k 个使群体满意程度最大化的 Top-k 在线服务评价问题,本文先对
相关概念进行说明.
定义 1. U={u i |i=1,2,…,n}为所有用户的集合,S={s j |j=1,2,…,m}为所有在线服务的集合.其中,n 表示用户数
量,m 表示在线服务数量.
定义 2. 每个用户根据自身对在线服务的偏好程度对服务进行排序.用户 u i 对在线服务的偏好序定义为β i =
s p(1) ; i s p(2) ; i …; i s p(t) ,用户群体偏好为集合 P={β i |i=1,2,…,n}.
其中,s p(1) ; i s p(2) 表示用户 u i 认为服务 s p(1) 优于服务 s p(2) .β i 表示用户 u i 对 t 个在线服务的某种排列,即从 m 个
在线服务中取出 t 个服务进行无重复线性排序,p(t)表示在线服务的序号.参数 t 控制用户偏好序完整程度,且
t≤m.当 t=m 时,β i 表示用户 u i 给出所有在线服务的完整偏好排序;当 t<m 时,β i 表示用户只给出在所有在线服务
中最偏爱的 Top-t 个服务的截断偏好排序.
定义 3. 集合 W={w l |l=1,2,…,k}为综合所有用户偏好后最终选择的 Top-k 在线服务集合.k 表示用户群体确
定需选择的 Top-k 在线服务数量,且 k≤t≤m.同时,集合 W 满足 W⊆S,即选择的 Top-k 在线服务集合 W 是在线服
务集合 S 的子集.
因此,Top-k 在线服务评价问题可表达为 f:P→W,即基于用户偏好 P 从候选在线服务集合 S 中选择一组包含
k 个在线服务的集合 W 作为 Top-k 在线服务评价结果.
2.2 问题示例
例 1:假设有 6 个用户 U={u i |i=1,2,…,6}分别对 4 个在线服务 S={s j |j=1,2,…,4}的偏好排序 P 见表 1,需选择
k=2 个在线服务推荐给用户群体.
Table 1 Users’ preference orders for online services
表 1 用户对在线服务的偏好排序
用户 偏好排序
u 1 β 1:s 1; 1s 2; 1s 3; 1s 4
u 2 β 2:s 1; 2s 3; 2s 2
u 3 β 3:s 1; 3s 4; 3s 3; 3s 2
u 4 β 4:s 1; 4s 2; 4s 4
u 5 β 5:s 2; 5s 3; 5s 1; 5s 4
u 6 β 6:s 3; 6s 4; 6s 2; 6s 1
由表 1 可见,用户对服务有不同的偏好排序,且部分用户的偏好排序不完整.现有在线服务评价方法 [1,9−11] 的
工作是集结全体用户的偏好得到全部服务的完整排名.但是,当用户群体共同决策只选择出有限个在线服务时,
[3]
用户群体满意度是衡量在线服务评价方法合理性的至关重要的指标 .在这种场景下,用户群体并不关心在线
服务的完整排序,而是关注得到的 k 个在线服务是否具备公平性以及群体的满意程度能否最大化.因此,目前完
整排序的在线服务评价方法不适用于 Top-k 在线服务评价.
本文考虑用户评价准则不一致情况下的用户偏好,采用 Monroe 社会选择规则 [12] 返回用户群体指定的 k 个
最大化群体满意度的在线服务,以实现 Top-k 在线服务评价.例 1 中,需选择 2 个在线服务,使得这 6 个用户对选