《软件学报》《软件学报》软件学报Journal of Software1000-98251000-9825《软件学报》编辑部10.13328/j.cnki.jos.004948TP181模式识别与人工智能COMPUTER NETWORKS AND INFORMATION SECURITY基于排序学习的推荐算法研究综述PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE黄震华*1huangzhenhua@tongji.edu.cn张佳雯1田春岐1孙圣力2向阳1HUANGZhen-Hua*1huangzhenhua@tongji.edu.cnZHANGJia-Wen1TIANChun-Qi1SUNSheng-Li2XIANGYang1同济大学电子与信息工程学院, 上海 201804;北京大学软件与微电子学院, 北京 102600College of Electronics and Information Engineering, Tongji University, Shanghai 201804, China;School of Software and Microelectronics, Peking University, Beijing 102600, China黄震华,E-mail:huangzhenhua@tongji.edu.cn25120162736917131202201514052015
Learning to rank(L2R) techniques try to solve sorting problems using machine learning methods, and have been well studied and widely used in various fields such as information retrieval, text mining, personalized recommendation, and biomedicine.The main task of L2R based recommendation algorithms is integrating L2R techniques into recommendation algorithms, and studying how to organize a large number of users and features of items, build more suitable user models according to user preferences requirements, and improve the performance and user satisfaction of recommendation algorithms.This paper surveys L2R based recommendation algorithms in recent years, summarizes the problem definition, compares key technologies and analyzes evaluation metrics and their applications.In addition, the paper discusses the future development trend of L2R based recommendation algorithms.
排序学习推荐算法机器学习兴趣模型个性化服务learning to rankrecommendation algorithmmachine learninginterest modelpersonalized service
近年来,随着物联网、云计算和社会网络等技术的迅猛发展,网络空间中所蕴含的信息量呈指数级增长[1].据国际数据公司IDC(Int’l data corporation)2012年报告显示:预计到2020年,全球数据总量将达到35.2ZB,这一数据量是2011年的22倍[2].推荐系统正是在这样的背景下被提出的,并且得到了学术界和工业界的广泛关注并加以应用,取得了许多相关的研究成果.推荐系统的核心是推荐算法,它通过挖掘用户与项目之间的二元关系,帮助用户从海量数据中便捷发现其感兴趣的对象(如信息、服务、物品等),并生成个性化推荐列表以满足其兴趣偏好.目前,推荐系统主要应用于在线电子商务[3](如Netflix、Amazon、eBay、阿里巴巴、豆瓣等),信息检索[4](如iGoogle、MyYahoo、GroupLens、百度等)、移动应用[5](Daily Learner,Appjoy等)、生活服务[6](如旅游服务Compass、博客推送M-CRS等)等各个领域.
在2012年的KDD会议(ACM SIGKDD Conf| on Knowledge Discovery And Data Mining)的推荐系统比赛中提出了3个挑战:(1) 数据的多元性和异构性;(2) 新用户的迅猛增长导致了严重的冷启动问题;(3) 挖掘用户偏好和物品流行度的及时性.针对上述3个挑战,Chen等人[36]提出了将基于特征的因式分解和叠加树模型[82]相结合的方式.基于特征的因式分解能够表示用户信息如社交关系、行为、用户关键词/标签以及物品的分类信息,可以解决矩阵稀疏的问题.而叠加树模型是基于决策树,在决策结果标注上不同用户的喜好程度,它能够表示用户的配置文档、浏览模式等信息,同时还可以表示连续性特征如年龄、时间戳等.由于用户-物品之间的交互行为如浏览模式等比较复杂,因此需要采用叠加森林模型即多棵叠加树来充分表达用户-物品的交互模式,如图8所示.叠加森林由多棵叠加树构成,每棵叠加树都能够得到用户对物品的不同喜好程度,有效解决新用户的冷启动问题.作者采用对级排序学习方法训练矩阵因式分解模型,并采用列表级排序学习算法LambdaRank[83]训练叠加树模型,以优化MAP评价准则.
叠加森林模型实例
Instance of superimposed forest model
图8Fig.84. 排序学习的效用评价准则
推荐算法中,排序学习的效用评价准则是通过如下方式来计算:排序学习模型预测的推荐列表中物品的得分与实际用户给物品的打分间的偏差.目前主要的效用评价标准有准确率(precision)[84]、召回率(recall)[84]、NDCG(normalized discounted cumulative gain)[85, 86]、MAP(mean average precision)[81]等.
由于在传统的推荐算法中,准确率只是考虑了推荐结果中用户感兴趣的物品个数,而没有考虑物品之间的排序.然而在实际应用中,推荐结果必然是有序的,与用户偏好越相关的物品排序越靠前越好,因此引入平均准确率MAP [81],主要由3个部分组成:Precision,Average Precision和Mean Average Precision.推荐列表中,某一位置k的准确率Precision定义为物品在推荐列表和用户在测试集上实际喜欢的物品列表的交集中的位置,除以该物品在推荐列表中的位置,见公式(24).
ReferencesGeorgeGHaasMRPentlandABig data and management2014572321326GantzJReinselDThe Digital Universe in 2020:Big Data, Bigger Digital Shadows, and Biggest Growth in the Far East2012116XuHZhangRLinCGanWConstruction of E-commerce recommendation system based on semantic annotation of ontology and user preference201412320282035GuptaYSainiASaxenaAKA new fuzzy logic based ranking function for efficient information retrieval system201542312231234Colombo-MendozaLOValencia-GarcíaRRodríguez-GonzálezASamper-ZapaterdJJRecomMetz:A context-aware knowledgebased mobile recommender system for movie showtimes201542312021222GavalasDKenterisMA Web-based pervasive recommendation system for mobile tourist guides2011157759770PopesculAPennockDMLawrenceSProbabilistic models for unified collaborative and content-based recommendation in sparse-data environments2001437444AroraGKumarADevreGSGhumareAMovie recommendation system based on users' similarity201434765770EkstrandMDRiedlJTKonstanJACollaborative filtering recommender systems20114281173LindenGSmithBYorkJAmazon.com recommendations:Item-to-Item collaborative filtering2003717680CaiYLeungHLiQMinHTangJLiHTypicality-Based collaborative filtering recommendation2014263766779BurkeRHybrid recommender systems:Survey and experiments2002124331370KagitaVRPujariAKPadmanabhanVVirtual user approach for group recommender systems using precedence relations20152941530ChenWNiuZZhaoXLiYA hybrid recommendation algorithm adapted in e-learning environments2014172271284PessiotJFTruongVUsunierNAminiMGallinariPLearning to rank for collaborative filtering2007145151KaratzoglouABaltrunasLShiYLearning to rank for recommender systems2013493494LiHLearning to Rank for Information Retrieval and Natural Language Processing20141121CaoZQinTLiuTYLearning to rank:From pairwise approach to listwise approach2007HangLIA short introduction to learning to rank2011941018541862XuJLiuTYLuMDirectly optimizing evaluation measures in learning to rank2008107114KangCYinDZhangRTorzecNHeJChangYLearning to rank related entities in Web search2015166309318WeimerMKaratzoglouALeQVSmolaACofirank maximum margin matrix factorization for collaborative ranking200718SharmaAYanBPairwise learning in recommendation:Experiments with community recommendation on linkedin2013193200ShiYLarsonMHanjalicAList-Wise learning to rank with matrix factorization for collaborative filtering2010269272ShiYKaratzoglouABaltrunasLLarsonMClimf:Learning to maximize reciprocal rank with collaborative less-is-more filtering2012139146ShiYKaratzoglouABaltrunasLLarsonMHanjalicAxCLiMF:Optimizing expected reciprocal rank for data with multiple levels of relevance2013434434CanutoSDBelémFMAlmeidaJMMarcosAA comparative study of learning-to-rank techniques for tag recommendation201343453462LvYMoonTKolariPZhengZHWangXHChangYLearning to model relatedness for news recommendation201157666YaoWHeJHuangGZhangYSoRank:Incorporating social information into learning to rank models for recommendation2014409410YaoWHeJWangHZhangYCCaoJCollaborative topic ranking:Leveraging item meta-data for sparsity reduction2015374380ZhouSLXuJGLearning to rank algorithm for microblogs based on analysis features and dynamic stepsize201324150161周诗龙徐俊刚基于分析特征与动态步长的微博排序学习算法201324150161HongLDoumithASDavisonBDCo-Factorization machines:Modeling user interests and predicting individual decisions in Twitter2013557566LiuNNYangQEigenrank:A ranking-oriented approach to collaborative filtering20088390ZhaoXWGuoYHeYJiangHWuYXLiXMWe know what you want to buy:A demographic-based system for product recommendation on microblogs201419351944WuHHuYLiHChenEHA new approach to query segmentation for relevance ranking in Web search20151812650ChenTTangLLiuQYangDYXieSNCaoXZWuCYYaoEPLiuZYJiangZSChenCKongWHYuYCombining factorization model and additive forest for collaborative followee recommendation2012YuJTaoDWangMRuiYLearning to rank using user clicks and visual features for image retrieval2015454767779DingYXYanZQFengWXuCLZhouDRank learning based on supervised topic model2015432333337丁宇新燕泽权冯威薛成龙周迪基于有监督主题模型的排序学习算法2015432333337SuXKhoshgoftaarTMA survey of collaborative filtering techniques20094AdomaviciusGTuzhilinAToward the next generation of recommender systems:A survey of the state-of-the-art and possible extensions2005176734749PazzaniMJBillsusDContent-Based recommendation systems2007325341BaltrunasLRicciFExperimental evaluation of context-dependent collaborative filtering using item splitting2014241-2734Klašnja-MilićevićAVesinBIvanovićMBudimacZE-Learning personalization based on hybrid recommendation strategy and learning style identification2011563885899WenHFangLGuanLA hybrid approach for personalized recommendation of news on the Web201239558065814NguyenTTSLuHYLuJWeb-Page recommendation based on Web usage and domain knowledge2014261025742587Blanco-FernándezYPazos-AriasJJGil-SollaARamos-CabrerMLopez-NoresMGarcia-DuqueJFernandez-VilasADiaz-Redondo RPBermejo-MunozJA flexible semantic inference methodology to reason about user preferences in knowledge-based recommender systems2008214305320MovahedianHKhayyambashiMRA semantic recommender system based on frequent tag pattern2015191109126SaltonGFoxEAWuHExtended Boolean information retrieval1983261110221036BerryMWDrmacZJessupERMatrices, vector spaces, and information retrieval1999412335362BleiDMProbabilistic topic models20125547784ZhaiCLaffertyJA study of smoothing methods for language models applied to information retrieval2004222179214CamposRDiasGJorgeAMJatowtASurvey of temporal information retrieval and related applications201447215ShawBSheaJSinhaSHogueALearning to rank for spatiotemporal search2013717726FuhrNOptimum polynomial retrieval functions based on the probability ranking principle198973183204CaoYXuJLiuTYLiHHuangYLHonHWAdapting ranking SVM to document retrieval2006186193CaoHVermaRNenkovaASpeaker-Sensitive emotion recognition via ranking:Studies on acted and spontaneous speech2015291186202SongYWangHHeXAdapting deep ranknet for personalized search20148392FreundYIyerRSchapireRESingerYAn efficient boosting algorithm for combining preferences20034933969MiaoZWangJZhouATangKRegularized boost for semi-supervised ranking2015643653LiuTYLearning to rank for information retrieval200933225331HüllermeierEFürnkranzJChengWBrinkerKLabel ranking by learning pairwise preferences20081721618971916HofmannKWhitesonSdeRijke MBalancing exploration and exploitation in listwise and pairwise online learning to rank for information retrieval20131616390XiaFLiuTYWangJLiHListwise approach to learning to rank:Theory and algorithm200811921199XieBTangXTangFHybrid recommendation base on learning to rank20155357KorenYBellRVolinskyCMatrix factorization techniques for recommender systems20094283037SotirasAResnickSMDavatzikosCFinding imaging patterns of structural covariance via non-negative matrix factorization2015108116BachFAdaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression2014151595627KorenYSillJOrdRec:An ordinal model for predicting personalized item rating distributions2011117124YinJWangZSLiQSuWJPersonalized recommendation based on large-scale implicit feedback201425919531966印鉴王智圣李琪苏伟杰基于大规模隐式反馈的个性化推荐201425919531966SunJKResearch and implementation of ranking based personalized recommender algorithms[M2014孙建凯面向排序的个性化推荐算法研究与实现2014CrouxCDehonCInfluence functions of the Spearman and Kendall correlation measures2010194497515PuthMTNeuhäuserMRuxtonGDEffective use of Spearman's and Kendall's correlation coefficients for association between two measured traits20151027784RendleSFreudenthalerCGantnerZSchmidt-ThiemeLBPR:Bayesian personalized ranking from implicit feedback2009452461PanWChenLCofiset:Collaborative filtering via learning pairwise preferences over item-sets2013180188TakácsGTikkDAlternating least squares for personalized ranking20128390YangSHLongBSmolaAJZhaHYZhengZHCollaborative competitive filtering:learning recommender using context of user choice2011295304LiuJWuCXiongYLiuWYList-Wise probabilistic matrix factorization for recommendation2014278434447CeberioJMendiburuALozanoJThe Plackett-Luce ranking model on permutation-based optimization problems2013494501LeQVSmolaAJDirect optimization of ranking measures2007RonkinLIJessen theorems for holomorphic, almost-periodic functions in tubular domains1987283510514ShiYKaratzoglouABaltrunasLLarsonMHanjalicAOliverNTFMAP:Optimizing MAP for top-n context-aware recommendation2012155164JohnsonRZhangTLearning nonlinear functions using regularized greedy forest2014365942954DonmezPSvoreKMBurgesCJCOn the local optimality of LambdaRank2009460467XiangLRecommender System Practice20124055项亮推荐系统实践20124055BurgesCShakedTRenshawELazierADeedsMHamiltonNHullenderGLearning to rank using gradient descent20058996JärvelinKKekäläinenJCumulated gain-based evaluation of IR techniques2002204422446MengXWLiuSDZhangYJHuXResearch on social recommender systems201526613561372孟祥武刘树栋张玉洁胡勋社会化推荐系统研究201526613561372DuanYJiangLQinTZhouMShumHYAn empirical study on learning to rank of tweets2010295303PengZHSunLHanXPShiBMicro-blog user recommendation using learning to rank201327496102彭泽环孙乐韩先培石贝基于排序学习的微博用户推荐201327496102ElmonguiHGMansourRMorsyHKhaterSEl-SharkasyAIbrahimRTRUPI:Twitter recommendation based on users' personal Interests2015272284LiuJBMicroblog recommender system based on collaborative filtering and behavior analysis[MS2014刘剑波基于协同过滤和行为分析的微博推荐系统2014McFeeBBarringtonLLanckrietGLearning content similarity for music recommendation201220822072218ZhaoXLiGWangMYuanJZhaZJLiZJChuaTSIntegrating rich information for video recommendation with multi-task rank aggregation201115211524WuLYangLYuNHuaXSLearning to tag2009361370RendleSSchmidt-ThiemeLPairwise interaction tensor factorization for personalized tag recommendation20108190ZhouYMLabel ranking methods based on Gaussian mixture model[MS2014周扬名基于高斯混合模型的标签排序算法研究2014LiCFengSShangWResearch on personalized recommendation algorithm for internet user to browse news2015LuZDouZLianJXieXYangQContent-Based collaborative filtering for news topic recommendation2015DeFrancisci Morales GGionisALuccheseCFrom chatter to headlines:harnessing the real-time Web for personalized news recommendation2012153162DasMDeFrancisci Morales GGionisAWeberILearning to question:Leveraging user preferences for shopping advice2013203211LiuSFengJSongZZhangTZHi, magic closet, tell me what to wear! In:Proc2012619628MengXWHuXWangLCZhangYJMobile recommender systems and their applications201324191108孟祥武胡勋王立才张玉洁移动推荐系统及其应用201324191108ZhengVWZhengYXieXQiangYTowards mobile intelligence:Learning from GPS history data for collaborative recommendation20121841737GloverFYeTPunnenAPKochenbergerGIntegrating tabu search and VLSN search to develop enhanced algorithms:A case study using bipartite Boolean quadratic programs20152413697707ZhuangJMeiTHoiSCHXyYQLiSPWhen recommendation meets mobile:Contextual and personalized recommendation on the go2011153162JiangKGeo-Referenced social media mining and its application[Ph.D. Thesis]2014蒋锴含地理位置信息的社交媒体挖掘及应用2014LianDFData mining on location-based social networks2014连德富基于位置社交网络的数据挖掘2014WangLLinJMetzlerDLearning to efficiently rank2010138145HanPXieBYangFShenRA scalable P2P recommender system based on distributed collaborative filtering2004272203210AbbasABilalKZhangLKhanSUA cloud based health insurance plan recommendation system:A user centered approach20154399109UedaNNakanoRGeneralization error of ensemble estimators19969095ZhangTIyengarVSRecommender systems using linear classifiers20022313334LiLZhengLYangFLiTModeling and broadening temporal user interest in personalized news recommendation201441731683177PfeifferJScholzMA low-effort recommendation system with high accuracy201356397408CenaFConsoleLGenaCGoyALeviGModeoSTorreIIntegrating heterogeneous adaptation techniques to build a flexible and usable mobile tourist guide2006194369384ZhangMLResearch on multi-task learning2011张敏灵多任务学习的研究2011CaruanaRMultitask learning19972814175PhuongNDPhuongTMCollaborative filtering by multi-task learning2008227232TanSBuJQinXChenCCaiDCross domain recommendation based on multi-type media fusion2014127124134SoldoFLeAMarkopoulouABlacklisting recommendation system:Using spatio-temporal patterns to predict future attacks201129714231437GaoYShenJChenCLiuCYYeJFA rank-based prediction algorithm of learning the intention of the query2009高莺沈洁陈沧刘春阳叶君峰一种基于排序学习的查询意图预测算法2009WangYZJinXLChengXQNetwork big data:Present and future201336611251138王元卓靳小龙程学旗网络大数据:现状与展望201336611251138LiJZYangWXiaJWCengXYSunLYLearning to rank method based on Hooke&Jeeves Pattern Search2015417215218李金忠杨威夏洁武曾小荟孙凌宇基于Hooke&Jeeves模式搜索的排序学习方法2015417215218YingYLiuYJChenCPersonalization recommender system based on cloud-computing technology20155113111117应毅刘亚军陈诚基于云计算技术的个性化推荐系统20155113111117HuangWCengSRA novel computer-aided diagnosis method for disease severity prediction based on image information and ranking learning techniques20153433337黄伟曾舒如基于图像信息和排序学习技术的疾病预测方法20153433337ChenKZouQPengZPKeWDCollaborative ranking friend recommendation algorithm in heterogeneous social network201435612701274陈珂邹权彭志平柯文德异质社交网络中协同排序的好友推荐算法201435612701274HawalahAFasliMDynamic user profiles for web personalisation201542525472569BobadillaJOrtegaFHernandoAGutierrezARecommender systems survey201346109132Tejeda-LorenteÁPorcelCPeisESanzRHerrera-ViedmaEA quality based recommender system to disseminate information in a university digital library20142615269LeeSParkSKahngMLeeSGPathrank:Ranking nodes on a heterogeneous graph for flexible hybrid recommender systems2013402684697