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

赵时海 等:用户群体满意度最大化的 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 algorithm is designed to solve the optimization problem and the obtained 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 reasonable time, so that the user group can make right service choice decision. In addition, the method can also
realize Top-k online service evaluation when users’ preferences are incomplete.
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] ,即用户可仅对其最偏爱的部分服务
进行排序,从而为解决偏好信息不完整情况下的在线服务评价提供了新的思路.