利用混合Plackett-Luce模型的不完整序数偏好预测

doi:10.11772/j.issn.1001-9081.2023101378

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (10): 3105-3113.DOI: 10.11772/j.issn.1001-9081.2023101378

利用混合Plackett-Luce模型的不完整序数偏好预测

郑升旻¹, 付晓东¹^,²()

^1.昆明理工大学信息工程与自动化学院，昆明 650500
^2.云南省计算机应用技术重点实验室（昆明理工大学），昆明 650500

收稿日期:2023-10-13 修回日期:2023-12-31 接受日期:2024-01-05 发布日期:2024-10-15 出版日期:2024-10-10
通讯作者: 付晓东
作者简介:郑升旻（1997—），男，四川自贡人，硕士研究生，主要研究方向：服务计算、偏好预测
付晓东（1975—），男，云南镇雄人，教授，博士，CCF会员，主要研究方向：服务计算、智能决策 xiaodong_fu@hotmail.com。
基金资助:
国家自然科学基金资助项目(61962030);云南省中青年学术和技术带头人后备人才培养计划项目(202005AC160036)

Incomplete ordinal preference prediction using mixture of Plackett-Luce models

Shengmin ZHENG¹, Xiaodong FU¹^,²()

^1.Faculty of Information Engineering and Automation，Kunming University of Science and Technology，Kunming Yunnan 650500，China
^2.Yunnan Key Laboratory of Computer Technology Applications （Kunming University of Science and Technology），Kunming Yunnan 650500，China

Received:2023-10-13 Revised:2023-12-31 Accepted:2024-01-05 Online:2024-10-15 Published:2024-10-10
Contact: Xiaodong FU
About author:ZHENG Shengmin， born in 1997， M. S. candidate. His research interests include service computing， preference prediction.
Supported by:
National Natural Science Foundation of China(61962030);Yunnan Provincial Foundation for Leaders of Disciplines in Science and Technology(202005AC160036)

摘要/Abstract

摘要：

聚合不同用户的偏好时，基于序数偏好可以解决不同用户评价准则不一致问题。但用户因为候选项目过多、沟通成本高等原因不能提供完整序数偏好，影响了在线服务信誉度量、群体决策等场景中聚合结果的可靠性和准确性，而现有的预测方法未充分考虑用户群体偏好分布的多样性。针对这一问题，提出一种利用混合Plackett-Luce（PL）模型的不完整序数偏好预测（MixPLPP）方法。首先基于用户现有偏好采样完整拓展排序，其次使用采样的完整排序学习混合PL模型，再次设计基于后验概率最大化的模型选择策略为用户选择模型，最后利用所选模型预测用户完整偏好。在公开数据集Movielens上的实验结果表明，所提方法的预测准确率和Kendall秩相关系数（Kendall CC），相较于向量相似度排序（VSRank）算法提升了5.0%和9.2%；相较于基于确定性的偏好补全（CPC）提升了1.5%和3.5%；相较于BayesMallows-4提升了0.9%和2.2%。实验结果验证了所提方法具有良好的预测能力，在多个数据集上的预测效果都更好。

关键词: 不完整序数偏好, 偏好预测, 成对比较, 排序模型, 混合Plackett-Luce模型

Abstract:

When aggregating the preferences of different users， the problem of inconsistent evaluation criteria among users can be solved based on ordinal preferences. However， users are unable to provide complete ordinal preferences due to the large number of candidate programs and high communication costs， which affects the reliability and accuracy of aggregation results in scenarios such as online service reputation measurement and group decision making. Therefore， there is a need to predict users’ complete ordinal preferences， but existing prediction methods do not fully consider the diversity of user group preference distribution. To address this problem， a Mixture of Plackett-Luce （PL） Preference Prediction for incomplete ordinal preference （MixPLPP） was proposed. First， the linear extensions were sampled based on the user’s existing preferences. Then， a mixture of PL models was learned using the sampled linear extensions. Next， a model selection strategy based on maximization of posterior probability was designed to select a model for the user. Finally， the user’s complete preferences were predicted based on the selected model. The experimental results on the public dataset Movielens show that the proposed method improves the prediction accuracy and Kendall rank Correlation Coefficient （Kendall CC） by 5.0% and 9.2% compared to VSRank （Vector Similarity Rank） algorithm； 1.5% and 3.5% compared to Certainty-based Preference Completion （CPC）； 0.9% and 2.2% compared to BayesMallows-4. The experimental results verify that the proposed method has good prediction ability and shows better prediction effect on multiple datasets and multiple measurements.

Key words: incomplete ordinal preference, preference prediction, pairwise comparison, ranking model, mixture of Plackett-Luce (PL) models

中图分类号:

TP274

郑升旻, 付晓东. 利用混合Plackett-Luce模型的不完整序数偏好预测[J]. 计算机应用, 2024, 44(10): 3105-3113.

Shengmin ZHENG, Xiaodong FU. Incomplete ordinal preference prediction using mixture of Plackett-Luce models[J]. Journal of Computer Applications, 2024, 44(10): 3105-3113.

图/表 6

参考文献 26

1	ZAJONC R B， MARKUS H. Affective and cognitive factors in preferences［J］. Journal of Consumer Research， 1982，9（2）：123-131.
2	赵时海，付晓东，岳昆，等.用户群体满意度最大化的Top-k在线服务评价［J］. 软件学报， 2021， 32（11）：3388-3403.
	ZHAO S H， FU X D， YUE K， et al. Top-k online service evaluating to maximize satisfaction of user group［J］. Journal of Software， 2021，32（11）： 3388-3403.
3	徐海燕，姜瑛.针对复杂用户评论的代码质量属性判断［J］. 软件学报，2021，32（7）：2183-2203.
	XU H Y， JIANG Y. Determination of code quality attribute for complex user’s comments［J］. Journal of Software，2021，32（7）：2183-2203.
4	ZHOU S， DAI X， CHEN H， et al. Interactive recommender system via knowledge graph-enhanced reinforcement learning［C］// Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval， Virtual Event China. New York： ACM， 2020： 179-188.
5	吴宾，陈允，孙中川，等.联合成对排序的物品推荐模型［J］.通信学报，2019，40（9）：193-206.
	WU B， CHEN Y， SUN Z C， et al. Co-pairwise ranking model for item recommendation［J］. Journal on Communications， 2019， 40（9）： 193-206.
6	孙肖依，刘华锋，景丽萍，等. 基于列表级排序的深度生成推荐方法［J］.计算机研究与发展，2020，57（8）：1697-1706.
	SUN X Y， LIU H F， JING L P， et al. Deep generative recommendation based on list-wise ranking［J］. Journal of Computer Research and Development， 2020， 57（8）： 1697-1706.
7	FU X， YUE K， LIU L， et al. Aggregating ordinal user preferences for effective reputation computation of online services［C］//Proceedings of the 2016 IEEE International Conference on Web Services. Piscataway： IEEE， 2016：554-561.
8	付晓东，彭俊，岳昆，等.面向不完整序数偏好的在线服务评价［J］.计算机集成制造系统， 2021， 27（10）：2774-2785.
	FU X D， PENG J， YUE K， et al. Online service evaluation for incomplete ordinal preference［J］. Computer Integrated Manufacturing Systems， 2021， 27（10）：2774-2785.
9	HUANG S， WANG S， LIU T-Y， et al. Listwise collaborative filtering［C］// Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2015：343-352.
10	UREÑA R， CHICLANA F， MORENTE-MOLINERA J A， et al. Managing incomplete preference relations in decision making： a review and future trends［J］. Information Sciences， 2015， 302：14-32.
11	FELIX B， VINCENT C， ULLE E， et al. Handbook of Computational Social Choice［M］. Cambridge： Cambridge University Press， 2016：223-256.
12	SEPLIARSKAIA A， KISELEVA J， RADLINSKI F， et al. Preference elicitation as an optimization problem［C］// Proceedings of the 12th ACM Conference on Recommender Systems. New York： ACM， 2018：172-180.
13	LU T， BOUTILIER C. Robust approximation and incremental elicitation in voting protocols［C］// Proceedings of the 22nd International Joint Conference on Artificial Intelligence. Menlo Park： AAAI Press， 2011： 287-293.
14	ZHANG X， CUI L， WANG Y. CommTrust： computing multi-dimensional trust by mining e-commerce feedback comments［J］. IEEE Transactions on Knowledge and Data Engineering， 2014， 26（7）： 1631-1643.
15	WANG S， SUN J， GAO B J， et al. VSRank： a novel framework for ranking-based collaborative filtering［J］. ACM Transactions on Intelligent Systems and Technology， 2014， 5（3）： Article No. 51.
16	GUIVER J， SNELSON E. Bayesian inference for Plackett-Luce ranking models［C］// Proceedings of the 26th Annual International Conference on Machine Learning. New York： ACM， 2009：377-384.
17	ZHAO Z， VILLAMIL T， XIA L. Learning mixtures of random utility models［C］// Proceedings of the 32nd AAAI Conference on Artificial Intelligence. Menlo Park： AAAI Press， 2018： 4530-4538.
18	VITELLI V， ØYSTEIN S， CRISPINO M， et al. Probabilistic preference learning with the Mallows rank model［J］. The Journal of Machine Learning Research， 2017， 18（1）： 5796-5844.
19	PRIYOGI B. Preference elicitation strategy for conversational recommender system［C］// Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining. New York： ACM， 2019：824-825.
20	BU Y， ZOU S， LIANG Y， et al. Estimation of KL divergence： optimal minimax rate［J］. IEEE Transactions on Information Theory， 2018， 64（4）： 2648-2674.
21	LI L， XUE M， ZHANG Z， et al. Certainty-based preference completion［J］. Data Intelligence， 2022， 4（1）：112-133.
22	LU T， BOUTILIER C. Effective sampling and learning for Mallows models with pairwise-preference data［J］. The Journal of Machine Learning Research， 2014，15（1）：3783-3829.
23	LIU A， ZHAO Z， LIAO C. Learning Plackett-Luce mixtures from partial preferences［C］// Proceedings of the 33rd AAAI Conference on Artificial Intelligence. Menlo Park： AAAI Press， 2019：4328-4335.
24	MAYSTRE L， GROSSGLAUSER M. Fast and accurate inference of Plackett-Luce models［C］// Proceedings of the 28th International Conference on Neural Information Processing Systems. Cambridge： MIT Press， 2015：172-180.
25	TKACHENKO M， LAUW W H. Plackett-Luce regression mixture model for heterogeneous rankings ［C］// Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. New York： ACM， 2016：237-246.
26	MATTEI N， WALSH T. PrefLib： a library for preferences data［C］// Proceedings of the 3rd International Conference on Algorithmic Decision Theory. Cham： Springer， 2013： 259-270.

模型数	缺失率/%	ACC	模型数	缺失率/%	ACC
1	20	0.876	3	20	0.880
	30	0.860		30	0.863
	40	0.839		40	0.845
	50	0.811		50	0.818
	60	0.780		60	0.791
	70	0.732		70	0.744
	80	0.677		80	0.699
2	20	0.878	4	20	0.882
	30	0.861		30	0.866
	40	0.844		40	0.847
	50	0.816		50	0.819
	60	0.790		60	0.794
	70	0.744		70	0.749
	80	0.697		80	0.704

模型数	缺失率/%	ACC	模型数	缺失率/%	ACC
1	20	0.876	3	20	0.880
	30	0.860		30	0.863
	40	0.839		40	0.845
	50	0.811		50	0.818
	60	0.780		60	0.791
	70	0.732		70	0.744
	80	0.677		80	0.699
2	20	0.878	4	20	0.882
	30	0.861		30	0.866
	40	0.844		40	0.847
	50	0.816		50	0.819
	60	0.790		60	0.794
	70	0.744		70	0.749
	80	0.697		80	0.704

LEs	缺失率/%	ACC	LEs	缺失率/%	ACC
5	20	0.879 0	15	20	0.881 0
	30	0.864 4		30	0.865 8
	40	0.845 5		40	0.845 7
	50	0.817 5		50	0.818 9
	60	0.792 2		60	0.793 0
	70	0.744 8		70	0.748 8
	80	0.699 2		80	0.702 5
10	20	0.879 3	20	20	0.882 6
	30	0.865 1		30	0.866 4
	40	0.845 6		40	0.847 0
	50	0.818 5		50	0.819 4
	60	0.792 7		60	0.793 7
	70	0.746 9		70	0.749 9
	80	0.701 8		80	0.704 0

LEs	缺失率/%	ACC	LEs	缺失率/%	ACC
5	20	0.879 0	15	20	0.881 0
	30	0.864 4		30	0.865 8
	40	0.845 5		40	0.845 7
	50	0.817 5		50	0.818 9
	60	0.792 2		60	0.793 0
	70	0.744 8		70	0.748 8
	80	0.699 2		80	0.702 5
10	20	0.879 3	20	20	0.882 6
	30	0.865 1		30	0.866 4
	40	0.845 6		40	0.847 0
	50	0.818 5		50	0.819 4
	60	0.792 7		60	0.793 7
	70	0.746 9		70	0.749 9
	80	0.701 8		80	0.704 0

方法	Movielens		sushi
方法	ACC	Kendall CC	ACC	Kendall CC
Mallows	0.884	0.839	0.671	0.497
VSRank	0.887	0.837	0.675	0.506
CPC	0.917	0.883	0.692	0.531
BayesMallows-1	0.898	0.863	0.688	0.519
MixPLPP-1	0.891	0.852	0.677	0.516
BayesMallows-4	0.923	0.895	0.697	0.538
MixPLPP-4	0.931	0.914	0.704	0.552

利用混合Plackett-Luce模型的不完整序数偏好预测

Incomplete ordinal preference prediction using mixture of Plackett-Luce models

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 26

相关文章 15

编辑推荐

Metrics

模型数	缺失率/%	ACC
模型数	缺失率/%	MixPLPP	BayesMallows
1	20	0.876	0.875
	30	0.860	0.858
	40	0.839	0.841
	50	0.811	0.813
	60	0.780	0.783
	70	0.732	0.733
	80	0.677	0.688
2	20	0.878	0.878
	30	0.861	0.860
	40	0.844	0.845
	50	0.816	0.815
	60	0.790	0.791
	70	0.744	0.739
	80	0.697	0.696
3	20	0.880	0.878
	30	0.863	0.861
	40	0.845	0.845
	50	0.818	0.816
	60	0.791	0.791
	70	0.744	0.740
	80	0.699	0.697
4	20	0.882	0.879
	30	0.866	0.861
	40	0.847	0.846
	50	0.819	0.816
	60	0.794	0.792
	70	0.749	0.742
	80	0.704	0.697

[1]	郭秋亚张兆功胡本然彭宇孙迪关心. 数据融合在能源互联网故障诊断中的应用[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	夏慧雯, 赵中雨, 王卓尔, 张清勇, 彭峰. 基于边缘计算的公共交通工具疫情监测系统[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2132-2138.
[3]	佘维, 郑倩, 田钊, 刘炜, 李英豪. 基于双重检测的气门识别方法[J]. 《计算机应用》唯一官方网站, 2022, 42(1): 273-279.
[4]	陆荣秀, 陈明明, 杨辉, 朱建勇. 基于溶液图像时序特征的元素组分含量动态监测系统[J]. 计算机应用, 2021, 41(10): 3075-3081.
[5]	成其伟, 陈启买, 贺超波, 刘海. 基于改进对称二值非负矩阵分解的重叠社区发现方法[J]. 计算机应用, 2020, 40(11): 3203-3210.
[6]	王思宇, 高炜欣, 李璐. 环口焊X射线焊缝图像质量评定模型[J]. 计算机应用, 2020, 40(9): 2748-2753.
[7]	苗晟, 董亮, 董建娥, 钟丽辉. 基于蜂窝网结构的多目标自动辨识定位方法[J]. 计算机应用, 2019, 39(11): 3343-3348.
[8]	纪丽娜, 陈凯, 于彦伟, 宋鹏, 王淑莹, 王成锐. 基于城市交通大数据的车辆类别挖掘及应用分析[J]. 计算机应用, 2019, 39(5): 1343-1350.
[9]	郭方方, 潮洛蒙, 朱建文. 基于相似连接的多源数据并行预处理方法[J]. 计算机应用, 2019, 39(1): 57-60.
[10]	高金刚, 刘智勇, 张爽, 侯岱双, 刘孝峰. 双目立体视觉在动车车身关键尺寸检测中的应用[J]. 计算机应用, 2018, 38(9): 2673-2677.
[11]	伍秋玉, 张明新, 刘永俊, 郑金龙. 基于改进迭代收缩阈值算法的微观3D重建方法[J]. 计算机应用, 2018, 38(8): 2398-2404.
[12]	袁钟, 冯山. 基于邻域值差异度量的离群点检测算法[J]. 计算机应用, 2018, 38(7): 1905-1909.
[13]	乔建华, 张雪英. 基于均衡分簇的无线传感器网络压缩数据收集[J]. 计算机应用, 2018, 38(6): 1691-1697.
[14]	毕崇春, 孟祥福, 张霄雁, 唐延欢, 唐晓亮, 梁海波. 基于耦合相关度的空间数据查询结果自动分类方法[J]. 计算机应用, 2018, 38(1): 152-158.
[15]	张承畅, 张华誉, 罗建昌, 何丰. 基于云计算和改进K-means算法的海量用电数据分析方法[J]. 计算机应用, 2018, 38(1): 159-164.