用户群体满意度最大化的Top-_i_k__i_在线服务评价-赵时海，付晓东，岳昆，刘骊，冯勇，刘利军.pdf

上善若水

355

16页

0次

2022-05-26

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2021,32(11):3388−3403 [doi: 10.13 328/j.cnki.jos.006089] http://www.jos.org.cn

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

∗

赵时海

付晓东

1,2

岳

昆

刘

骊

冯

勇

刘利军

(昆明理工大学信息工程与自动化学院,云南昆明 650504)

(云南省计算机应用技术重点实验室(昆明理工大学),云南昆明 650504)

(云南大学信息学院,云南昆明 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/608 9.htm

Top-k Onli ne Serv ice Eva lua ting to Ma ximize Satis factio n of Use r Group

ZHAO Shi-Hai

, FU Xiao-Dong

1,2

, YUE Kun

, LIU Li

, FENG Yong

, LIU Li-Jun

(Faculty of Information Engineering and Auto mation, Kun ming University of S cience and Technology, Kunming 650504, Chin a)

(Yunnan Key Laboratory of Computer Technology Application (Kunming University of Science and Technology), Kunming 650504,

China)

(School of Information Science and Engineering, Yunnan Univ ersity, Kunming 650504, Chin a)

Abstra ct : Online service evaluations that consider inconsistent user eval uation 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 Progr am of Yunnan Province (202005AC160036)

收稿时间: 2019-11-18; 修改时间: 20 20-02-07; 采用时间: 2020-05-18

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

3389

proposes a Top-k online service evaluation method that maximizes the satisfaction of user group. Firstly, a metric of user group

satisfaction is defined to measure the rationality of the selected k online services. Secondly, considering the inconsistency of user

evaluation criteria and incomplete user preference information, the Borda rule is used to construct user-service matrix based on users’

preference relationship for online services. Then, inspired by the theory of Monroe proportional representation, the Top-k online service

evaluation problem is modeled as an optimization problem to find a set of online services that maximizes satisfaction of the user group.

Finally, a greedy algorith m is designed to so lve the optimization probl em and the obtain ed set of online services is served as the result of

Top-k services evaluation. The rationality and effectiveness of the method are verified by theoretical analysis and experiments study.

Theoretical analysis shows that the proposed method satisfies the proportional representation and fairness required for Top-k online

service evaluation. Meanwhile, experiments also show that the method can obtain the result close to the ideal upper bound of the user

group satisfaction in the reasonabl e time, so that the user group can make right service choice decision. In addition, the method can also

realize Top-k onlin e s erv i ce ev alu at io n wh en u s er s’ pr ef e ren c es ar e in complet e .

Key words: online service; Top-k online service evaluation; user preference; Monroe rule; greedy algorithm

随着互联网技术的迅猛发展,以此为依托的在线服务因其开放、便捷、共享等性质得到快速普及.在线服

务泛指以互联网技术为支撑向用户提供服务的方式,很多餐厅、酒店等线下服务也以互联网为媒介发布成为广

义在线服务.目前,在线服务被广泛应用于 Web 服务、电子商务、电子政务和在线学习等领域.然而,随着互联网

上功能相同或相似的在线服务的数量不断增加,用户选择满意的服务需要花费更多时间和精力

[1,2]

:首先,庞大

的在线服务数量使得用户不可能与所有服务进行交互,且一些用户可能不愿意对所有与之交互的服务做出评

价,导致用户难以获得在线服务的完整信息;其次,由于受利益驱动,某些用户或在线服务提供者可能提供虚假

的服务信息

[3,4]

.因此,用户通常需要借助以第三方评价信息为基础形成的在线服务评价方法,以辅助进行服务

选择.在线服务评价方法对在线服务的筛选具有非常重要的作用,可有效提升用户体验度、加强用户与服务提

供者之间的信任

[5]

用户与在线服务进行交互后,往往通过反馈信息表达对服务的偏好及满意程度

[6]

.聚合用户群体对在线服

务的偏好信息、帮助用户群体在大量具有相同或相似功能的在线服务中选择一组指定数量并满足用户群体需

求的在线服务集合,称为 Top-k 在线服务评价.例如:美国的点评网站 Yelp 和 TripAdvisor 集结所有用户对交互过

的餐厅或酒店的偏好信息,向用户展示十大最受欢迎的餐厅或酒店

[7]

;国内拼多多平台上的用户在拼团时,综合

用户群体对在线商品的偏好选择 k 个在线商品等.在上述用户群体共同决策的场景中,对在线服务进行评价时

需充分体现每个用户的满意度

[8]

.所有用户对评价结果的满意程度称为用户群体满意度.

当前,国内外学者针对在线服务评价问题开展了大量研究,提出了累加值法、平均值法、Beta 信誉度量法、

概率度量法、模糊度量法、基于社会选择理论的度量方法等多种评价方法

[1,9]

.这些方法主要侧重于聚合用户

的评价信息对在线服务进行整体评价,获得对服务的一个总体排序反馈给用户以辅助决策.其未考虑到用户群

体共同决策的 Top-k 在线服务评价场景中选择的在线服务的代表性和用户的群体需求,使得基于现有方法产生

的评价结果缺乏一定的合理性,且用户群体满意度较低.因此,现有方法不适用于 Top- k 在线服务评价场景.同时,

除基于社会选择理论的度量方法外,现有的在线服务评价方法均假设用户具有相同的评价准则

[10]

.然而,由于用

户交互心理和交互背景不同,用户评价准则不可能一致,进而导致用户评价信息不可比较.假设用户具有相同评

价准则的在线服务评价方法聚合用户偏好得到的评价结果具有一定的误导性

[11]

考虑到现有工作对 Top-k 在线服务评价研究的欠缺及用户评价准则相同导致用户评价信息不可比较的问

题,本文提出一种基于社会选择理论 Monore 规则

[12]

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

法考虑到用户对服务评价准则的不一致,基于用户对服务的偏好排序,将 Top-k 在线服务评价问题建模为

Monroe 规则下的比例代表模型,寻找最大化用户群体满意度的 Top-k 在线服务集合;同时确保该集合中的服务

具备一定的代表性,使评价结果更具合理性.由于基于 Monroe 规则的 Top-k 在线服务评价问题是一个 NP 难问

题,本文采用贪心算法

[13]

求其近似解.理论分析和实验结果表明,使用该方法能得到较好的近似结果.此外,该方

法中用户对服务的偏好序可以是对服务的完整排序,也可以为截断排序

[14]

,即用户可仅对其最偏爱的部分服务

进行排序,从而为解决偏好信息不完整情况下的在线服务评价提供了新的思路.

of 16

免费下载

软件学报计算机技术

关注

评论