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

3396 Journal of Software 软件学报 Vol.32, No.11, November 2021

家餐厅只有少部分用户喜欢,但其属于集合 W,其他用户可能质疑该评价方法代表性不足且不公平.因此,Top-k
在线服务评价方法需要充分考虑服务的比例代表性.为衡量评价结果的比例代表性,本文给出两个公平性质:联
盟稳定性及集体一致性.
一个公平的 Top-k 在线服务评价方法的评价结果需要按比例表达用户群体意见的多样性.为形式化比例代
表思想,下面分别对联盟稳定性和集体一致性进行证明.
性质 1(联盟稳定性). 对于有 n 个用户、m 个在线服务的 Top-k 在线服务评价 f:P→W,如果至少有 n/k 个用
户将在线服务 s j 排在偏好序的第一位,则 s j ∈W.
证明:在 Top-k 在线服务评价过程中,至少有 n/k 个用户将在线服务 s j 排在各自偏好序的首位.由于 MGA 算
法在每次迭代中选择被 n/k 个用户排在偏好序首位且未被迭代选择过的在线服务,该算法会选择服务 s j .因此,
本方法满足联盟稳定性. □
性质 2(集体一致性). 对于 Top-k 在线服务评价 f:P→W,假设存在一个包含 k 个在线服务的集合 W,且 W⊆S.
若每个用户将集合 W 中的某些服务排在用户偏好序的第一位,且集合中所有服务均被 n/k 个用户排在偏好序前
面,则集合 W 为 Top-k 在线服务评价结果.
证明:根据 MGA 算法的贪心策略,每次迭代选择局部最大化⎡n/k⎤个用户满意度的服务.从而,集合 W 中被所
有用户排在其首位的服务及被 n/k 个用户排在偏好序前面的服务均被选中,即集合 W 为 Top-k 在线服务评价结
果.因此,本文 Top-k 在线服务评价方法满足集体一致性. □
5 实验结果与分析

为验证 Top-k 在线服务评价方法的有效性和性能,设计实现了相关实验并对实验结果进行分析.实验环境
为 Intel Core i5 处理器,8G 内存,64 位 Windows 8 专业版操作系统,开发环境为 PyCharm 2016.2.3,开发语言为
Python 3.6.
5.1 数据集
为避免实验的偏向性,实验同时采用真实数据集和合成数据集.真实数据集包含寿司数据集(http://www.
kamishima.net/sushi/) [28] 和 MovieLens 数据集(https://grouplens.org/datasets/movielens/) [29] ,合成数据集包含由
Impartial Culture 和 Mallow 模型 [30] 合成的偏好数据.
寿司数据集有 S 1 和 S 2 ,S 1 包含 5 000 个用户对 10 种寿司的完整偏好排序,S 2 包含 5 000 个用户对 100 种寿
司的 Top-10 寿司进行排序.MovieLens 数据集包含 943 名用户,1 682 部电影,10 万条左右的用户真实评分(1~5),
用 MV 表示.由于 MV 中用户对服务的评分非常稀疏,首先采用协同过滤方法对评分进行填充 [31] ,然后根据每个
用户对服务的评分对服务进行排序,若在线服务对应的评分相同,则采用随机法对评分相同的服务进行排序,最
终获得用户-服务偏好完整排序.对于用户偏好不完整的实验,在 MV 中截取用户完整排序的 Top-t 个在线服务,
构成截断排序的数据集.
为进一步验证本文方法的普适性和有效性,实验还设计了基于合成偏好数据集的相关实验.由 Impartial
Culture 模型 [13] 生成的数据集用 IC 表示.IC 是偏好相关实验常用的标准测试数据集 [13] ,其对于给定的服务集合
S,每个用户的偏好序是从所有可能的在线服务排序中随机均匀抽取而来.Mallow 模型在序数偏好研究中被广
泛认可并应用 [30] ,由其合成的偏好数据集用 ML 表示.在 Mallow 模型中设置两个参数:中心偏好序σ和离散参数
θ.其中,σ为由 m个在线服务构成的完整偏好排序;离散参数θ用于控制合成的偏好排序与中心偏好序σ的离散程
度,且θ∈(0,1].当θ→0 时,合成的偏好序趋向于与中心偏好序σ一致;当θ→1 时,合成的偏好序趋于均匀分布.本文
随机生成中心偏好序σ和θ值,设置不同的用户数量 n 及在线服务数量 m,利用 Mallow 模型合成不同的偏好数
据集.
5.2 有效性实验
本节设计基于小数据集和较大数据集的实验,并从不同维度验证实验的有效性;同时,将本文方法与 Top-k