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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(11):3388−3403 [doi: 10.13328/j.cnki.jos.006089] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

∗
用户群体满意度最大化的 Top-k 在线服务评价

3
1
1,2
1
1
赵时海 , 付晓东 , 岳 昆 , 刘 骊 , 冯 勇 , 刘利军 1
1
(昆明理工大学 信息工程与自动化学院,云南 昆明 650504)
2
(云南省计算机应用技术重点实验室(昆明理工大学),云南 昆明 650504)
3 (云南大学 信息学院,云南 昆明 650504)
通讯作者: 付晓东, E-mail: xiaodong_fu@hotmail.com

摘 要: 考虑用户评价准则不一致的在线服务评价通常以服务的完整排序作为评价结果,而不是选择出使用户群
体满意度最大的 Top-k 在线服务集合,使评价结果难以满足 Top-k 在线服务评价场景的合理性和公平性需求.为此,
提出了一种用户群体满意度最大化的 Top-k 在线服务评价方法.该方法首先定义用户群体满意度指标,以衡量选择
的 k 个在线服务的合理性;其次,考虑用户评价准则不一致及用户偏好信息不完整的情况,采用 Borda 规则将用户对
在线服务的偏好关系构造为用户-服务满意度矩阵;然后借鉴 Monroe 比例代表思想,将 Top-k 在线服务评价问题建
模为寻找最大化用户群体满意度的在线服务集合的优化问题;最后采用贪心算法对该优化问题进行求解,将得到的
在线服务集合作为 Top-k 评价结果.通过理论分析和实验验证了该方法的合理性和有效性.理论分析表明,该方法满
足 Top-k 在线服务评价所需的比例代表性和公平性.同时,实验结果也表明,该方法能够在合理的时间内获得接近用
户群体满意度理想上界的评价结果,可以有效地辅助用户群体做出正确的服务选择决策.另外,该方法还可以在用户
偏好不完整的情况下实现 Top-k 在线服务评价.
关键词: 在线服务;Top-k 在线服务评价;用户偏好;Monroe 规则;贪心算法
中图法分类号: TP311

中文引用格式: 赵时海,付晓东,岳昆,刘骊,冯勇,刘利军.用户群体满意度最大化的 Top-k 在线服务评价.软件学报,2021,32(11):
3388−3403. http://www.jos.org.cn/1000-9825/6089.htm
英文引用格式: Zhao SH, Fu XD, Yue K, Liu L, Feng Y, Liu LJ. Top-k online service evaluating to maximize satisfaction of user
group. Ruan Jian Xue Bao/Journal of Software, 2021,32(11):3388−3403 (in Chinese). http://www.jos.org.cn/1000-9825/6089.htm

Top-k Online Service Evaluating to Maximize Satisfaction of User Group

1
1
3
1,2
1
ZHAO Shi-Hai , FU Xiao-Dong , YUE Kun , LIU Li , FENG Yong , LIU Li-Jun 1
1
(Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650504, China)
2
(Yunnan Key Laboratory of Computer Technology Application (Kunming University of Science and Technology), Kunming 650504,
China)
3
(School of Information Science and Engineering, Yunnan University, Kunming 650504, China)
Abstract: Online service evaluations that consider inconsistent user evaluation criteria usually use a complete ranking of services as the
evaluation result, instead of selecting the Top-k online service set that maximizes the satisfaction of the user group. Thus, it makes the
evaluation results cannot satisfy the rationality and fairness requirement in the scenario of Top-k online service evaluation. This study

∗ 基金项目: 国家自然科学基金(61962030, 61862036, 61860318); NSFC-云南联合基金(U1802271); 云南省基础研究计划
(2019FJ011); 云南省中青年学术和技术带头人后备人才培养计划(202005AC160036)
Foundation item: National Natural Science Foundation of China (61962030, 61862036, 61860318); Joint Fund of NSFC-Yunnan
(U1802271); Basic Research Program of Yunnan Province (2019FJ011); Young and Mid-aged Academic and Technical Talent Reserve
Training Program of Yunnan Province (202005AC160036)
收稿时间: 2019-11-18; 修改时间: 2020-02-07; 采用时间: 2020-05-18