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

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

[7]
服务推荐中的 STV 方法 进行多角度对比,验证该方法的有效性.由于整数规划方法易于理解且被广泛应用于
计算 Monroe 多胜者问题 [23] ,因此我们将整数规划方法(ILP 方法)作为小数据集实验的基准对比方法,其得到的
*
用户群体满意度用 C opt 表示.本文方法用 G 表示,由其获得的用户群体满意度用 C 表示.然而,ILP 方法在实验数
据规模较大时的运行时间呈指数增加,因此在小数据集上同时设计将理想上界作为对比指标的实验.理想上界
为假设每个用户均匹配到最喜欢的在线服务时用户群体的满意度,即每个用户排在其偏好序首位的服务均被
选中.根据 Borda 规则,每个用户满意度为 m−1.理想上界是用户群体理论上可能达到的最大满意程度,用 C ideal
表示,则 C ideal =(m−1)n.
通过小数据集上的实验,分析本文方法分别与整数规划方法和理想上界得到的用户群体满意度的比值,并
根据 C 分别与 C opt 和 C ideal 的比值来衡量本文方法得到的用户群体满意度.比值越趋向于 1,说明用本文方法所
得用户群体满意度越大.
5.2.1 小规模数据实验
每次实验分别在数据集 S 1 、S 2 、MV、IC 及 ML 中随机选择 100 个用户和 10 个在线服务进行实验,由于 k≤m,
*
则任取 k=3 和 k=6,每个数据集上进行 30 次实验并取平均值,记录方法 G 与整数规划方法 ILP 的用户群体满意
*
度比值 C/C opt ,结果见表 3.同样的数据集和参数设置,分别进行 30 次实取平均值,记录方法 G 与用户群体满意度
理想上界的比值 C/C ideal ,见表 4.
*
Table 3 Satisfaction ratio of user group for methods G and ILP (C/C opt )
*
表 3 方法 G 与 ILP 的用户群体满意度比值(C/C opt )
S 1 S 2 MV IC ML
k=3 0.93 0.94 0.95 0.93 0.93
k=6 0.94 0.93 0.94 0.94 0.95
*
Table 4 Satisfaction ratio of user group for methods G and C ideal (C/C ideal )
*
表 4 方法 G 与 C ideal 的用户群体满意度比值(C/C ideal )
S 1 S 2 MV IC ML
k=3 0.84 0.85 0.88 0.81 0.82
k=6 0.91 0.88 0.86 0.91 0.91
从表 3 中可看出,用本文方法计算的用户群体满意度非常接近整数规划方法计算得到的用户群体满意度.
说明该方法在数据量较小的情况下能获得相对最优的用户群体满意度.另外,根据表 3 和表 4,分别计算 k=3 和
k=6 两种情况下的 C/C opt 与 C/C ideal 之间的标准差,标准差在 0.01~0.02 之间.这说明每组实验在不同数据集上得
到的用户群体满意度的比值较稳定,即本文的方法是一种稳定的方法.同时,结合表 3 和表 4,同比之下表 4 的比
值与表 3 的比值差距较小,表明用 C ideal 作为计算本文方法得到的近似比是合理的.因此,在较大规模数据集上的
实验均采用 C ideal 作为本方法的对比指标.
5.2.2 较大规模数据实验
在 Top-k 在线服务评价场景中,用户和服务的规模通常非常大.同时,结合第 3.3 节对用户群体满意度理论下
界的分析,在较大规模的服务评价场景中,k/m 对方法的效果影响较大.因此,为验证本文方法在用户和在线服务
数量及 k 值较大时的有效性,以 k/m,n 和 m 作为实验参数,基于数据集 ML,IC 及 ML 分别设计了 3 组实验:C/C ideal
与 k/m 之间的关系;C/C ideal 与用户数量 n 之间的关系;C/C ideal 与在线服务 m 之间的关系.每次实验重复 30 次并
取平均值.
根据第 3.3 节中对本文方法的用户群体满意度的理论下界分析可知,对于 f:P→W,当 k 值较小时,H k /k 较大, k
值是影响 C/C ideal 的主要因素;然而,当 k 值较大时,H k /k 值较小,C/C ideal 主要与(k−1)/(2(m−1))有关.因此,实验首先
验证 C/C ideal 与 k/m 之间的关系.在数据集 MV、IC 和 ML 上随机抽取 900 个用户,固定在线服务数量为 100,模
拟 k/m 的取值从 0.1 增加到 0.5 的实验,实验结果如图 2 所示.
分析图 2 可知,固定用户数量和在线服务数量,当 k/m 为 0.1(即 k 值较小)时,C/C ideal 受 H k /k 影响较大.随着
k/m 逐渐增大,C 与 C ideal 的比值逐渐提高,在 k/m=0.3 时,C/C ideal 最高随后有所降低.因此,在本文 Top-k 在线服务