一種基于協(xié)同矩陣分解的用戶冷啟動推薦算法

高玉凱 王新華 郭 磊 陳竹敏

1(山東師范大學(xué)信息科學(xué)與工程學(xué)院 濟南 250358) 2(山東師范大學(xué)管理科學(xué)與工程學(xué)院 濟南 250358) 3 (山東大學(xué)計算機科學(xué)與技術(shù)學(xué)院 濟南 250101) (ykgao.cs@gmail.com)

一種基于協(xié)同矩陣分解的用戶冷啟動推薦算法

高玉凱1王新華1郭 磊2陳竹敏3

1(山東師范大學(xué)信息科學(xué)與工程學(xué)院 濟南 250358)2(山東師范大學(xué)管理科學(xué)與工程學(xué)院 濟南 250358)3(山東大學(xué)計算機科學(xué)與技術(shù)學(xué)院 濟南 250101) (ykgao.cs@gmail.com)

位置服務(wù)作為一種信息共享平臺，在方便人們交流和共享信息的同時，也因為用戶數(shù)量的不斷增加，而面臨著嚴重的信息過載問題.如何利用推薦技術(shù)對信息進行過濾和篩選，幫助用戶在位置服務(wù)中發(fā)現(xiàn)有價值的信息成為近年來研究的熱點.但目前已有的推薦算法，在只有消費記錄這種隱性數(shù)據(jù)情況下，針對用戶較少活動區(qū)域或新用戶的推薦效率較低，無法最大化挖掘隱性數(shù)據(jù)所帶的信息.針對以上問題，結(jié)合位置服務(wù)平臺的特點，針對用戶冷啟動問題，提出了一種結(jié)合協(xié)同概率矩陣分解與迭代決策樹(gradient boosting decision tree, GBDT)的推薦算法.該方法首先使用多層協(xié)同概率矩陣分解在多個維度上得到用戶潛在特征，然后使用GBDT學(xué)習(xí)算法對特征和標簽進行訓(xùn)練得到用戶對項目的偏好，最后使用考慮約束問題的top-N推薦產(chǎn)生推薦列表.在真實數(shù)據(jù)集上的實驗結(jié)果表明，與目前較為流行的方法相比，提出的方法能在準確率、F1值上取得較好的結(jié)果，能更好地緩解位置服務(wù)中的冷啟動問題.

推薦系統(tǒng)；位置服務(wù)；概率矩陣分解；冷啟動問題；約束

隨著移動設(shè)備和位置定位技術(shù)的發(fā)展，能夠聯(lián)系線上和線下社會，方便人們共享和交流位置信息的位置服務(wù)(location based service, LBS)[1]受到人們的廣泛關(guān)注.越來越多的人愿意通過位置服務(wù)平臺來分享他們的實時位置、共享信息，使用位置服務(wù)提升自己的生活(如導(dǎo)航、餐飲消費、購電影票等)水平.但由于用戶數(shù)量不斷增加，所產(chǎn)生的信息不斷增多，位置服務(wù)平臺同樣面臨著嚴重的信息過載問題.推薦系統(tǒng)作為一種有效的信息過濾技術(shù)，由于使我們可以更好地探索用戶的偏好，幫助人們發(fā)現(xiàn)他們想要的服務(wù)和需求，受到研究者們的廣泛關(guān)注[2].

與傳統(tǒng)的推薦算法相比，LBS中的推薦問題面臨嚴重的用戶冷啟動問題.報告顯示*TalkingData-2015年餐飲O2O移動應(yīng)用行業(yè)報告(http://mi.talkingdata.com/)國內(nèi)LBS平臺美團與大眾點評2014年新用戶的增長率都超過300%.如何在用戶消費的商家或位置信息很少時(用戶冷啟動問題)，為他們推薦感興趣的商家已經(jīng)成為當前LBS推薦中亟需解決的關(guān)鍵問題.目前已有很多研究人員針對此問題進行了廣泛的研究.例如，Zhang等人[3]提出上下文感知的半監(jiān)督協(xié)同訓(xùn)練模型(CSEL)，算法通過不同的上下文信息建立不同的弱預(yù)測模型，然后利用協(xié)同訓(xùn)練策略，每個模型學(xué)習(xí)其他模型的結(jié)果.Vairachilai等人[4]基于社區(qū)檢測算法提出解決冷啟動問題的方法，通過社區(qū)檢測算法在社交網(wǎng)絡(luò)上區(qū)分用戶的相似度.Zhou等人[5]使用基于用戶的協(xié)同過濾和決策樹算法預(yù)測新用戶偏好.但目前針對用戶冷啟動問題的研究大多是針對通用算法的優(yōu)化，很少直接研究LBS中的用戶冷啟動問題[6].在LBS推薦系統(tǒng)中，用戶位置信息的極度稀疏和顯式數(shù)據(jù)的缺乏，導(dǎo)致傳統(tǒng)基于協(xié)同過濾的方法推薦效果較差.因此研究針對LBS的用戶冷啟動問題還存在較大挑戰(zhàn).

另一方面，在現(xiàn)實生活中，LBS提供商(例如一個景點或者餐館)的服務(wù)能力通常受到其自身規(guī)模的限制，當消費者的數(shù)量超過其服務(wù)能力時其服務(wù)質(zhì)量會下降，用戶也會有較低的滿意度[7].因此，為了進一步提升用戶滿意度和推薦效果，需要將商家的服務(wù)能力(約束)也同時考慮到推薦系統(tǒng)中，研究基于實際約束的推薦問題.

針對上述存在的問題，本文提出一種結(jié)合多層協(xié)同概率矩陣分解與迭代決策樹(gradient boosting decision tree, GBDT)學(xué)習(xí)算法的推薦算法，使用用戶在其他系統(tǒng)的線上消費記錄來豐富用戶信息，緩解冷啟動問題.該方法首先利用多層協(xié)同概率矩陣分解將LBS數(shù)據(jù)、線上消費數(shù)據(jù)相結(jié)合，綜合使用LBS商家、線上商家和線上商家類別3種維度的信息來學(xué)習(xí)用戶的潛在特征.然后使用GBDT學(xué)習(xí)算法對特征和標簽進行訓(xùn)練得到用戶對項目的偏好.在生成推薦列表時，考慮實際環(huán)境下的商家約束問題，通過改進top-N推薦來獲得較好的推薦效果，具體來說，商家每被推薦一次，其約束值要根據(jù)預(yù)測結(jié)果進行相應(yīng)地調(diào)整，當其約束值小于0時，則不能被推薦.

本文的主要貢獻有3方面:

1) 提出了一種多層概率矩陣分解算法(multi probabilistic matrix factorization, MPMF).該算法同時對多個矩陣進行分解，共享用戶的潛在特征矩陣，從多個信息維度更加準確地對用戶潛在特征進行估計.同時該方法作為一種通用的特征學(xué)習(xí)方法，可以在不依賴專業(yè)知識的情況下獲取用戶特征，因此具有較強的可擴展性；

2) 針對現(xiàn)實社會中的“約束”問題，將約束信息考慮到推薦結(jié)果中，使算法在推薦過程中能同時考慮到LBS商家的服務(wù)能力，提升用戶的滿意度；

3) 在多層概率矩陣分解算法的基礎(chǔ)上，通過將用戶特征與GBDT學(xué)習(xí)算法相結(jié)合，提出一種有效緩解用戶冷啟動的推薦模型，并在真實數(shù)據(jù)集上驗證了算法的有效性.

1 相關(guān)工作

傳統(tǒng)的推薦算法根據(jù)使用的信息類型主要可以分為:基于內(nèi)容的推薦(content-based recommendation)和基于協(xié)同過濾的推薦 (collaborative filtering-based recommendation).其中，基于內(nèi)容過濾的推薦，通過發(fā)現(xiàn)項目內(nèi)容之間的相似性，然后根據(jù)用戶以往的喜好記錄，推薦給用戶相似的項目.基于協(xié)同過濾的推薦主要可以分為3種：

1) 基于用戶的協(xié)同過濾，使用用戶對物品的偏好找到其相似鄰居用戶，然后將鄰居用戶喜歡的推薦給當前用戶；

2) 基于項目的協(xié)同過濾，利用用戶對物品的偏好找到相似的物品，然后根據(jù)用戶的歷史偏好，推薦相似的物品；

3) 基于模型的協(xié)同過濾，利用樣本的用戶喜好信息，訓(xùn)練一個推薦模型，然后根據(jù)用戶喜好的信息進行預(yù)測，計算推薦.

2種方法的優(yōu)缺點比較如表1所示.基于協(xié)同過濾的推薦簡單、高效，并且應(yīng)用廣泛，但其難以為沒有任何記錄的用戶或者歷史記錄稀疏的用戶發(fā)現(xiàn)相似用戶，導(dǎo)致不能為其給出準確的推薦，稱為用戶冷啟動問題[8].

Table 1 Comparison of Recommendation Methods表1 推薦方法優(yōu)缺點比較

在LBS推薦系統(tǒng)中，由于用戶位置信息的極度稀疏性，LBS推薦面臨嚴重的數(shù)據(jù)稀疏問題.同時由于LBS的發(fā)展迅速產(chǎn)生大量的新用戶，面臨嚴重的用戶冷啟動問題.本文主要針對用戶冷啟動問題，引入額外用戶數(shù)據(jù)與LBS數(shù)據(jù)相結(jié)合，提出結(jié)合多層協(xié)同概率矩陣分解與GBDT學(xué)習(xí)算法的推薦算法.

已有的解決用戶冷啟動問題的方法，大致可以分為3類:

1) 使用額外數(shù)據(jù)源，如用戶屬性數(shù)據(jù)、用戶的觀點、社會標簽等，從而更好地選擇新用戶的鄰居.例如，Lin等人[9]使用社交網(wǎng)絡(luò)數(shù)據(jù)解決APP推薦中冷啟動問題；Lika等人[10]利用人口統(tǒng)計學(xué)信息，首先對用戶進行聚類，得到用戶分組，在分組中計算用戶在不同屬性上的相似度，得到整體相似度，得到用戶的鄰居集，然后將相似度加入到預(yù)測評分進行推薦；Zhang等人[3]提出上下文感知的半監(jiān)督協(xié)同訓(xùn)練模型(CSEL)，算法通過不同的上下文信息建立不同的弱預(yù)測模型，然后利用協(xié)同訓(xùn)練策略，每個模型學(xué)習(xí)其他模型的結(jié)果；Meng等人[11]使用子社區(qū)和實體決策模型等額外信息，幫助解決冷啟動情況下的推薦問題.

2) 選擇最具可信度的相似鄰居，其核心思想是改進確定用戶鄰居的方法.例如Zhang等人[12]利用評分可信度來對物品評分矩陣進行降維.其中物品和用戶被共同聚類，處于每個用戶簇中的評分被分散處理，從而克服數(shù)據(jù)稀疏性問題，基于物品和用戶簇來預(yù)測用戶偏好；Vairachilai等人[4]基于社區(qū)檢測算法提出解決冷啟動問題的方法，通過社區(qū)檢測算法在該社交網(wǎng)絡(luò)上區(qū)分用戶的相似度.

3) 使用混合方法改進預(yù)測評分，其核心思想是在確定和新用戶相似的用戶之后，運用混合方法計算相似性或者產(chǎn)生預(yù)測評分.例如Le等人[13]提出新穎的混合推薦方法HU-FCF++，包含2個過程：①通過人口統(tǒng)計學(xué)的信息計算出一個評分；②計算在列表中的評分，通過對人口統(tǒng)計學(xué)信息的聚類將用戶分組，并找出分組中的新用戶.Wang等人[14]提出一個混合推薦框架來解決用戶冷啟動問題.首先利用當前用戶特征、用戶上下文和操作記錄用于將用戶進行分類.然后，根據(jù)用戶的類型動態(tài)的選擇合適的推薦算法，產(chǎn)生推薦列表.

使用額外數(shù)據(jù)源是一種簡單高效解決用戶冷啟動的方法.但是如何使用額外的數(shù)據(jù)或者將額外的數(shù)據(jù)與原有數(shù)據(jù)相結(jié)合，是仍需研究的問題.著名研究者Singh和Gordon[15]提出協(xié)同矩陣分解的方法，即同時對2個矩陣進行分解，共享用戶潛在特征矩陣U，在2個信息維度上求用戶的潛在特征.Ji等人[16]提出一種包含3種因素的矩陣分解模型，用于提高推薦準確度和解決冷啟動問題；Forsati等人[17]提出一種矩陣分解模型，將信任關(guān)系與不信任關(guān)系結(jié)合起來，提高推薦效果的同時緩解冷啟動問題；Ma等人[18]提出了SoRec算法，該算法將評分矩陣R與社會關(guān)系矩陣D聯(lián)系起來，實驗取得較好結(jié)果，特別是在用戶很少評分甚至沒有評分的情況下.上述研究表明協(xié)同矩陣分解技術(shù)可以有效結(jié)合2方面信息，使用共享用戶特征矩陣的方式，得到用戶在兩個信息維度上的特征.

2 推薦模型

本文算法首先使用多層概率矩陣分解算法學(xué)習(xí)用戶特征，然后使用GBDT學(xué)習(xí)算法訓(xùn)練用戶特征得到用戶對項目的預(yù)測評分，最后采用考慮“約束”問題的top-N推薦方法生成推薦列表.

2.1問題描述

在本文中，我們以真實業(yè)務(wù)場景“口碑”平臺中的商家推薦問題作為主要研究對象.“口碑”平臺是一個新興的LBS平臺，由于存在較多的新用戶與新商家，而面臨嚴重的用戶冷啟動問題.其中多數(shù)用戶直接由成熟線上網(wǎng)購平臺“淘寶”轉(zhuǎn)化而來，而這些用戶在“淘寶”中均具有較多的線上消費記錄，這為解決新用戶冷啟動問題提供了新的思路.我們可以使用豐富的淘寶信息學(xué)習(xí)用戶的偏好，然后應(yīng)用到口碑系統(tǒng)的推薦中.我們將淘寶數(shù)據(jù)稱為線上數(shù)據(jù)，口碑數(shù)據(jù)成為線下數(shù)據(jù).用戶的線上記錄形式如表2所示，例如其一條數(shù)據(jù)為(u1,s1,apple,fruits,1,t)表示用戶u1在時間t購買了商家s1中種類為fruits的商品apple.在口碑中，用戶通過線上購買商家服務(wù)線下體驗的方式與商家產(chǎn)生關(guān)系.其日志記錄形式為表3所示.令U={u1,u2,…,um},M={m1,m2,…,mn},L={l1,l2,…,lp} 分別表示用戶的集合、商家的集合和位置的集合.當用戶u1購買并消費l1位置的商家m1，則系統(tǒng)會產(chǎn)生(u1,m1,l1,t)的日志記錄，t為購買時間.

我們設(shè)計的推薦算法根據(jù)用戶的數(shù)據(jù)信息將用戶分為3類:1)老用戶(old user)，也就是存在口碑數(shù)據(jù)的用戶；2)新用戶(new user)，也就是不存在口碑數(shù)據(jù)但存在淘寶數(shù)據(jù)的用戶；3)完全的新用戶(absolutely new user)，也就是既不存在口碑數(shù)據(jù)也不存在淘寶數(shù)據(jù)的用戶.對上述3類用戶分別采用適合的推薦方法，從而提升總體的推薦效率.第1類與第2類用戶采用多層協(xié)同概率矩陣分解與GBDT結(jié)合的方法，第3類用戶采用基于商家流行度的方法.本文模型主要針對2個問題：1)探究如何利用大量的線上數(shù)據(jù)來豐富用戶信息促進線下商家的推薦效果.2)根據(jù)實際的業(yè)務(wù)場景，需要考慮跟LBS相關(guān)的實際約束，比如商家的服務(wù)能力、商家能夠提供的折扣數(shù)量等.

Table 2 Online User Behavior

Table 3 Users’ Shopping Records at Brick-and-Mortar Stores表3 用戶線下歷史數(shù)據(jù)格式

2.2評分預(yù)測方法

為了有效地利用信息，緩解冷啟動問題，我們采用準確度較高的迭代決策樹(gradient boosting deci-sion tree, GBDT)[19]作為基本評分預(yù)測方法.GBDT是一種迭代的決策樹算法，其輸出由所有的決策樹結(jié)論累加產(chǎn)生.在測試集中訓(xùn)練用戶特征與標簽，學(xué)習(xí)得到特征與標簽的關(guān)系，然后預(yù)測測試集中用戶特征對應(yīng)的標簽.GBDT方法具有良好的準確性和擴展性，并且其使用了迭代計算方式，所需的特征向量維度較低，計算時間復(fù)雜度較低.使用GBDT學(xué)習(xí)算法需要對用戶數(shù)據(jù)進行特征提取.根據(jù)文獻[20]與生活經(jīng)驗，主要從4個維度提取特征：

1)用戶特征.描述用戶的特征，主要包括消費間隔、重復(fù)購買行為、最近購買行為等.

2)商家特征.描述商家的特征，主要包括生命周期、實際限制、日均銷量等.

3)用戶-商家特征.描述用戶對特定商家的偏好特征，主要包括最近購買、生命周期、在該用戶的購買排名等.

4)商家-位置特征.描述在商家在當前位置的特征，主要包括被購買次數(shù)、該商家占當前位置的比例、該商家在當前位置的排名等.

Table 4 Merchant Information表4 線下商家數(shù)據(jù)格式

當維度上升之后訓(xùn)練效率較低，耗時較長，同時GBDT不需要太大的維度提升準確度.我們利用隨機森林算法(random forest, RF)[21]對提取的32維特征進行選擇，保留10維最有效的特征.雖然GBDT方法可以獲得比較好的結(jié)果，但是只能用于老用戶.新用戶沒有歷史數(shù)據(jù)無法獲得其相關(guān)特征，導(dǎo)致方法無法使用.第2.3節(jié)和第3節(jié)主要介紹如何在大量的淘寶數(shù)據(jù)中學(xué)習(xí)用戶的偏好.

2.3用戶特征學(xué)習(xí)

針對上述對新用戶進行推薦時產(chǎn)生的冷啟動問題，本文采用了遷移學(xué)習(xí)的思想進行解決.即在線上數(shù)據(jù)學(xué)習(xí)用戶特征，然后作為GBDT算法的輸入，為新用戶進行推薦.

雖然淘寶商家與口碑商家具有相似之處，但仍然存在不可忽視的差異.用戶在LBS的線下偏好與純網(wǎng)絡(luò)購物的線上偏好存在差異.因此直接使用人工提取特征的方式在線上數(shù)據(jù)中提取用戶特征應(yīng)用到線下數(shù)據(jù)的推薦中是不合適的.并且人工選取出來的特征依賴人力和專業(yè)知識，不利于推廣.于是我們通過機器學(xué)習(xí)算法來學(xué)習(xí)特征，促進特征工程的工作更加快速.結(jié)合本文問題，綜合考慮多種有監(jiān)督學(xué)習(xí)算法，最終我們選擇概率矩陣分解算法PMF作為基礎(chǔ)的特征學(xué)習(xí)算法.在協(xié)同矩陣分解的基礎(chǔ)上，考慮本文問題，需要在線上和線下數(shù)據(jù)中學(xué)習(xí)用戶潛在特征，提出多層協(xié)同概率矩陣分解算法(multi probabilistic matrix factorization, MPMF).MPMF算法作為本文的主要創(chuàng)新點，其具體細節(jié)將在第3節(jié)進行詳細描述.

2.4生成推薦列表

本文研究的問題，存在‘約束’這一獨特的因素.商家的約束信息主要指服務(wù)能力，即其約束值就是可接待用戶數(shù)量.我們希望用戶量盡可能地接近或等于“約束”值，但不能超過.為了提高推薦準確度，并滿足約束條件，我們改進top-N推薦用于推薦列表的生成環(huán)節(jié).生成推薦包括如下4個步驟:

4) 上述步驟執(zhí)行完畢時，遍歷user-id確定用戶的推薦列表.

經(jīng)過上面的步驟便能得到每個用戶的推薦列表，并滿足3個條件：1)預(yù)測評分大于閾值，這樣做是為了獲得較高的準確度；2)用戶的推薦列表長度小于4，這是我們數(shù)據(jù)中得到的結(jié)果，在實驗部分會解釋；3)商家被推薦的次數(shù)與其“約束”值與用戶對其預(yù)測評分有關(guān)，每次商家被添加到推薦列表時都要保證用戶對其預(yù)測評分在當前序列是最高的.

3 用戶特征學(xué)習(xí)

我們采用協(xié)同矩陣分解的方式在多維數(shù)據(jù)上學(xué)習(xí)用戶潛在特征，緩解用戶冷啟動問題.提出一種多層協(xié)同概率矩陣(MPMF)學(xué)習(xí)算法，該算法基于協(xié)同矩陣分解與概率矩陣分解.本節(jié)首先介紹PMF算法的定義與原理.然后介紹一個協(xié)同矩陣分解在推薦系統(tǒng)上的經(jīng)典應(yīng)用——SoRec算法，該算法將評分矩陣R與社會關(guān)系矩陣D聯(lián)系起來，提高推薦效果.最后給出MPMF算法的圖模型、目標函數(shù)以及最優(yōu)化求解方式.

3.1PMF算法介紹

我們采用概率矩陣分解(PMF)[22]方法對用戶-項目矩陣進行分解，得到用戶潛在特征矩陣和項目潛在特征矩陣，其中的每一行或每一列都可以表示一個用戶或項目的潛在特征.另外，PMF一般產(chǎn)生的特征向量維度較低，計算復(fù)雜度較低，可以適用于大規(guī)模數(shù)據(jù)集[23].

假設(shè)用戶的評分矩陣R中有m個用戶，n個推薦對象，其中ri j∈[0,1]表示用戶ui對推薦對象vj的偏好.U和V分別表示分解得到的與用戶和推薦對象相關(guān)的l維特征矩陣，其列向量Ui和Vj則分別表示相對應(yīng)的潛在特征向量.由于PMF假設(shè)可觀測評分是由概率線性模型UiVj和高斯觀測噪聲組成的，因此評分矩陣R的條件概率分布可以定義為

(1)

(2)

(3)

經(jīng)過貝葉斯推斷，可得到U和V的聯(lián)合后驗概率分布為

(4)

PMF算法雖然準確得到用戶和項目的潛在特征，但只能利用評分矩陣一方面信息，無法滿足我們在多維信息上學(xué)習(xí)用戶特征的要求.Ma等人提出的SoRec算法是利用協(xié)同矩陣分解的經(jīng)典算法，該算法結(jié)合評分數(shù)據(jù)與用戶間的社交關(guān)系數(shù)據(jù)，實驗表明可以提升推薦準確度.該算法適用于本文問題，下面進行詳細介紹.

3.2基于協(xié)同概率矩陣分解的SoRec算法

Ma等人提出的SoRec算法通過對用戶-項目評分矩陣R與用戶社會關(guān)系矩陣D的協(xié)同分解，得到用戶的潛在特征矩陣Ui.與前面提到的評分矩陣R的概率矩陣分解相似，社會關(guān)系矩陣D的條件概率分布定義為

(5)

(6)

(7)

通過對2部分信息的聯(lián)合分解，將2部分信息結(jié)合起來.概率圖模型如圖1所示，U,V,Q的聯(lián)合后驗概率分布可以表示為

(8)

Fig. 1 Graphic model for SoRec圖1 SoRec概率圖模型

3.3多層的協(xié)同概率矩陣分解算法MPMF

本文在協(xié)同概率矩陣分解的基礎(chǔ)上，提出多層的協(xié)同概率矩陣分解.結(jié)合本文研究問題，參考相關(guān)文獻[24-25]在用戶-項目矩陣R、用戶-類別矩陣C和用戶-店鋪矩陣S三個維度信息上學(xué)習(xí)用戶特征.該方法通過將上述3個矩陣協(xié)同時分解，得到的用戶潛在特征結(jié)合3方面信息，并且更加準確，通過實驗證明可以提升推薦效果.其概率圖模型如圖2所示:

Fig. 2 Graphic model for MPMF圖2 MPMF圖模型

R,C,S的對數(shù)聯(lián)合后驗概率分布表示為

(9)

其中,a為常量，當參數(shù)確定時，最大化式(9)，相當于最小化損失函數(shù)式為

(10)

(11)

(12)

(13)

(14)

其中，g′(x)=exp(x)/(1+exp(x))2是回歸函數(shù)g(x)的導(dǎo)數(shù).

4 實 驗

在實驗中，為驗證我們所提出算法的有效性，主要驗證了2個問題：1)比較MPMF方法與已有推薦算法對冷啟動用戶的推薦效果.2)方法中參數(shù)對實驗結(jié)果的影響.

4.1數(shù)據(jù)集

數(shù)據(jù)為由阿里天池大數(shù)據(jù)科研平臺提供*https://tianchi.aliyun.com.該數(shù)據(jù)集共包括3部分：1)線上(淘寶)部分交易記錄，共963 923用戶的44 528 127條記錄；2)線下(口碑)數(shù)據(jù)，包括測試集與訓(xùn)練集兩部分.其中訓(xùn)練集中包括1 081 724條數(shù)據(jù)、230 783用戶、6 039商家、426個位置，測試集包括473 533用戶-位置對，但是僅有24.5%出現(xiàn)在訓(xùn)練集中即測試集中的老用戶僅有24.5%；3)口碑商家數(shù)據(jù)，包括商家實際“約束”與商家的分布位置.

經(jīng)過簡單的數(shù)據(jù)分析顯示，用戶平均訪問1.05個位置與1.25個商家，表明用戶趨向于消費同一商家.由此我們確定推薦列表的長度不超過4.口碑數(shù)據(jù)中新用戶的比例為75.5%，用戶占比、商家周活躍度、用戶周活躍度如圖3～5所示.上述數(shù)據(jù)均表明口碑網(wǎng)是快速發(fā)展的，存在嚴重的冷啟動問題.

Fig. 3 User Scale圖3 用戶比例

Fig. 4 Merchant week activity圖4 商家周活躍度

Fig. 5 User week activity圖5 用戶周活躍度

圖4表明商家的數(shù)量不斷增加，且增幅較大.圖5中C表示一個周的有記錄用戶數(shù)，即口碑網(wǎng)的周活躍用戶量；S表示一個周的記錄數(shù)(左垂直坐標軸)，即口碑網(wǎng)的銷量；則S/C代表平均一個用戶的購買數(shù)(右垂直坐標軸).橫坐標表示時間，距離數(shù)據(jù)最早時間(2015.07.01)的周數(shù).通過圖5可以看出銷量增長迅速.

圖6為一個位置所含商家的數(shù)量的關(guān)系，如圖所示超過75%的位置所含商家數(shù)量少于20，所以我們預(yù)測用戶對其當前所在位置的所有商家的評分是可行的.

Fig. 6 Merchant number in location圖6 位置所含商家數(shù)量分布

4.2評價方法

本文使用準確率、召回率和F1值作為評價指標.本文采用的F1值計算方法與傳統(tǒng)有差異，主要是為了考慮具體問題中的商家“budget”因素，計算為

(15)

(16)

(17)

4.3結(jié)果比較

為了驗證提出方法的有效性，我們比較了User-CF,GBDT,PMF,SoRec等主流的推薦算法.由于數(shù)據(jù)集的格式為日志記錄，我們首先對數(shù)據(jù)進行了預(yù)處理，將其轉(zhuǎn)化為評分形式.

淘寶數(shù)據(jù)的處理方法為：1)用戶對項目(商品、商家、類別)有過點擊行為，但沒有購買行為，其評分為0.2)有過購買行為，則用用戶對項目的購買次數(shù)與該項目被單一用戶購買次數(shù)最大值的比值作為用戶對項目的評分.經(jīng)過上述處理，評分的取值區(qū)間為[0,1].

口碑數(shù)據(jù)的處理方法：1)與淘寶數(shù)據(jù)相似，用戶對項目的購買次數(shù)與該項目被單一用戶購買次數(shù)最大值的比值作為用戶對項目的評分.2)口碑數(shù)據(jù)為購買記錄，可以認為全為正例，因此需要生成負例(GBDT算法需要).方法為：用戶到過的位置的銷量前3的商家中，如果存在用戶未對其有購買行為，則代表用戶可能不喜歡，其評分為0.我們選擇銷量前3的原因為銷量大被用戶知道的可能性越大.在用戶知道商家存在的前提而未購買，則很可能是不喜歡的.

本文方法按照數(shù)據(jù)來源將用戶分為3類，其中第3類用戶不具有任何歷史數(shù)據(jù)，所以采用基于商家流行度的方法.具體為將用戶當前所在位置的最流行的前3名商家作為候選集.我們選擇前3的數(shù)據(jù)依據(jù)，歷史數(shù)據(jù)顯示某一位置銷量前3名的商家的總銷量占當前位置總銷量比率超過65%的幾率為82%，這說明絕大多數(shù)位置用戶選擇前3流行商家的可能性大于65%.商家流行度的計算即為商家總銷量比上當前位置的總銷量.SoRec方法的實現(xiàn)在本文有2種選擇：1)用戶-項目矩陣R加用戶-類別矩陣C;2)用戶-項目矩陣R加用戶-店鋪矩陣S.在淘寶數(shù)據(jù)集上經(jīng)過實驗證明，第2種R加S效果優(yōu)于第1種.下面涉及的SoRec算法均為R加S的協(xié)同概率矩陣分解.

GBDT算法的參數(shù)設(shè)置：樹的個數(shù)為100，步長為0.01，深度為8.MPMF的參數(shù)設(shè)置：λS=10，λU=λV=λW=λZ=0.01.在MPMF算法中參數(shù)λC非常重要，它決定了矩陣C與矩陣S對用戶特征的影響權(quán)重.當λC=0時，該方法僅使用R加S，即成為SoRec方法；當λC?λS時，相當于僅使用R加C，其結(jié)果差于SoRec方法.下面將對λC的取值進行討論，以獲得較好的結(jié)果.圖7為λC取值與F1值的關(guān)系，分別取λC的值為0，1，5，10，15，當λC=5時結(jié)果最優(yōu).

Fig. 7 The relationship of λC圖7 MPMF結(jié)果與λC取值的關(guān)系

由于最終的推薦結(jié)果要經(jīng)過“約束”信息與閾值的篩選，導(dǎo)致針對某一用戶的可推薦商家數(shù)目不定，所以我們不固定推薦列表的長度，但是設(shè)置其長度的最大值，保證推薦的準確度.根據(jù)前文所述的數(shù)據(jù)分析結(jié)果，我們將推薦列表長度的最大值設(shè)置為4.表5表示了當推薦列表長度最大值為4，閾值為0.2時各種方法的結(jié)果(α=0.2為多次試驗取最好結(jié)果時的選擇，實驗中我們將α初值設(shè)置為0，每次加0.05,最大值為0.5).結(jié)果表明:本文提出的方法GBDT+MPMF在準確度和F1值上均優(yōu)于對比算法，證明其有效性.本文方法對用戶進行分類，針對不同類別采用合適的方法，不同方法取得的實驗結(jié)果如表6所示.

Table 5 The Results of Method表5 結(jié)果比較(推薦列表的長度L=4,α=0.2)

Table 6 The Results of Diffient User Categories表6 不同用戶分類方法的結(jié)果

由于商家“約束”信息的存在，推薦系統(tǒng)盡量推薦用戶最可能消費的商家.使用2.4節(jié)描述的方法，將所有候選推薦集合按照預(yù)測概率由大到小排序，并經(jīng)過閾值的篩選.這樣可以在保證一定準確度的情況下，平衡準確度與召回率，以獲得較好的F1值.“約束”信息會篩掉一部分候選集對召回率影響較大.不考慮“約束”信息時我們的方法效果如表7所示.與不考慮“約束”信息相比，考慮約束信息時，算法的準確率、召回率、F1值均下降，算法的整體性能降低了接近15%.

Table 7 The Influence of Budget表7 Budget對推薦效果的影響

5 總 結(jié)

本文提出了結(jié)合多維信息的推薦方法，該方法結(jié)合多層概率矩陣分解與GBDT算法，并給出了將多層信息結(jié)合到一起的推薦框架.同時，考慮實際問題中的“實際限制”.在真實數(shù)據(jù)集上的實驗結(jié)果表明，該方法比已有方法取得更好的推薦效果.雖然該算法是在具體問題中得到啟發(fā)，但使用特征學(xué)習(xí)算法學(xué)習(xí)用戶特征，不依賴專業(yè)的行業(yè)知識和GBDT學(xué)習(xí)算法本身的通用性，使得本文的方法具有較強的可擴展性.

本文研究問題中的“約束”因素具有很強研究性，在未來的工作中我們將會更多考慮這個因素，比如設(shè)計在算法的損失函數(shù)中.

[1] Liu Shudong, Meng Xiangwu. Approach to network services recommendation based on mobile users’ location[J]. Journal of Software, 2014, 25(11): 2556-2574 (in Chinese)(劉樹棟, 孟祥武. 一種基于移動用戶位置的網(wǎng)絡(luò)服務(wù)推薦方法[J]. 軟件學(xué)報, 2014(11): 2556-2574)

[2] Kang Zhao, Peng Chong, Cheng Qiang. Top-Nrecommender system via matrix completion[C] //Proc of the 30th AAAI Conf on Artificial Intelligence (AAAI-16). Menlo Park, CA: AAAI, 2016: 179-185

[3] Zhang Mi, Tang Jie, Zhang Xuchen, et al.Addressing cold start in recommender systems: A semi-supervised co-training algorithm[C] //Proc of the 37th Int ACM SIGIR Conf on Research & Development in Information Retrieval. New York: ACM, 2014: 73-82

[4] Vairachilai S, Kavithadevi M, Raja M. Alleviating the cold start problem in recommender systems based on modularity maximization community detection algorithm[J]. Circuits and Systems, 2016, 7(8): 1268-1279

[5] Zhou Ke, Yang Shuanghong, Zha Hongyuan. Functional matrix factorizations for cold-start recommendation[C] //Proc of the 34th Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2011: 315-324

[6] Yao Yichen, Li Zhongjie. Cold-start solution to location-based entity shop recommender systems using online sales records[C] //Proc of the 2nd Int Workshop on Social Influence Analysis(SocInf 2016). Menlo Park, CA: AAAI, 2016: 57-67

[7] Hu Ke, Li Xiangyang, Wu Chaotian. Cold start purchase prediction with budgets constraints[C] //Proc of the 2nd Int Workshop on Social Influence Analysis(SocInf 2016). Menlo Park, CA: AAAI, 2016: 68-80

[8] Li xin, Liu Guiquan, Li Lin, et al. Circle-based and social connection embedded recommendation in LBSN[J]. Journal of Computer Research and Development, 2017, 54(2): 394-404 (in Chinese)(李鑫, 劉貴全, 李琳, 等. LBSN上基于興趣圈中社會關(guān)系挖掘的推薦算法[J].計算機研究與發(fā)展, 2017, 54(2): 394-404)

[9] Liu N N, Meng Xiangrui, Liu Chao, et al. Wisdom of the better few: Cold start recommendation via representative based rating elicitation[C] //Proc of the 5th ACM Conf on Recommender Systems. New York: ACM, 2011: 37-44

[10] Lika B, Kolomvatsos K, Hadjiefthymiades S. Facing the cold start problem in recommender systems[J]. Expert Systems with Applications, 2014, 41(4): 2065-2073

[11] Meng Chen, Yang Cheng, Chen Jiechao, et al. A method to solve cold-start problem in recommendation system based on social network sub-community and ontology decision model[J]. Acta Neurochirurgica, 2013, 156(3): 577-580

[12] Zhang Daqing, Zou Qin, Xiong Haoyi. CRUC: Cold-start recommendations using collaborative filtering in Internet of things[J]. Computer Science, 2013, 13(6): 3454-3461

[13] Le H S. HU-FCF++: A novel hybrid method for the new user cold-start problem in recommender systems[J]. Engineering Applications of Artificial Intelligence, 2015, 41(3): 207-222

[14] Wang J H, Chen Yihao. A distributed hybrid recommendation framework to address the new-user cold-start problem[C] //Proc of the 13th IEEE Int Conf on Ubiquitous Intelligence and Computing. Piscataway, NJ: IEEE, 2015: 1686-1691

[15] Singh A P, Gordon K. Relational learning via collective matrix factorization[C] //Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 650-658

[16] Ji Ke, Shen Hong. Addressing cold-start: Scalable recommendation with tags and keywords[J]. Knowledge-Based Systems, 2015, 83(1): 42-50

[17] Forsati R, Mahdavi M, Shamsfard M, et al. Matrix factorization with explicit trust and distrust side information for improved social recommendation[J]. ACM Trans on Information Systems, 2014, 32(4): No.17

[18] Ma Hao, Yang Haixuan, Lyu M R, et al. SoRec: Social recommendation using probabilistic matrix factorization[C] //Proc of the 18th ACM Conf on Information and Knowledge Management. New York: ACM, 2008: 931-940

[19] Xie Jianjun, Coggeshall S. Prediction of transfers to tertiary care and hospital mortality: A gradient boosting decision tree approach[J]. Statistical Analysis & Data Mining, 2010, 3(4): 253-258[20]Wei Hao, Shi Bei, Chen Junwen. Location based services recommendation with budget constraints[C] //Proc of the 2nd Int Workshop on Social Influence Analysis (SocInf 2016). Menlo Park, CA: AAAI, 2016: 48-56

[21] Breiman L. Random forest[J]. Machine Learning, 2001, 45(3): 5-32

[22] Salakhutdinov R, Mnih A. Probabilistic matrix factorization[C] //Proc of the 20th Int Conf on Neural Information Processing Systems. New York: Curran Associates Inc, 2007: 1257-1264

[23] Guo Lei, Ma Jun, Chen Zhumin, et al. Incorporating item relations for social recommendation[J]. Chinese Journal of Computers, 2014, 37(1): 219-228 (in Chinese)(郭磊, 馬軍, 陳竹敏, 等. 一種結(jié)合推薦對象間關(guān)聯(lián)關(guān)系的社會化推薦算法[J]. 計算機學(xué)報, 2014, 37(1): 219-228)

[24] Zhang Weiyu, Wu Bin, Geng Yushui, et al. Joint rating and trust prediction based on collective matrix factorization[J]. Chinese Journal of Electronics, 2016, 44(7): 1581-1586 (in Chinese)(張維玉, 吳斌, 耿玉水, 等. 基于協(xié)同矩陣分解的評分與信任聯(lián)合預(yù)測[J]. 電子學(xué)報, 2016, 44(7): 1581-1586)

[25] Hernando A, Bobadilla J, Ortega F, et al. A probabilistic model for recommending to new cold-start non-registered users[J]. Information Sciences, 2016, 376(1): 216-232

LearningtoRecommendwithCollaborativeMatrixFactorizationforNewUsers

Gao Yukai1, Wang Xinhua1, Guo Lei2, and Chen Zhumin3

1(SchoolofInformationScience&Engineering,ShandongNormalUniversity,Jinan250358)2(SchoolofManagementScience&Engineering,ShandongNormalUniversity,Jinan250358)3(SchoolofComputerScienceandTechnology,ShandongUniversity,Jinan250101)

Location-based service (LBS) as an information sharing platform can help people obtain more useful information. But with the increasing number of users, LBS is faced with a serious problem of information overload. Using the recommender system to filter information and help users to find valuable information has become a hot research topic in recent years. In LBS, only positive implicit feedback is available and user cold-start problem in this scenario is not well studied. Based on the observations, we consider the characteristics of location-based services platform and propose a recommender algorithm, which combines collaborative PMF (probabilistic matrix factorization) with GBDT (gradient boosting decision tree), to solve the cold start problem. The algorithm first use multi probabilistic matrix factorization to learn user latent feature in different dimension, and then use gradient boosting decision tree to train the factor and label to learn the user’s preference, finally use the improved top-Nrecommender which considers the budget problem to produce the recommendation list. The experimental results on the real data show that the proposed algorithm can achieve better results in accuracy andF1 than other popular methods, and can solve the cold-start problem in LBS recommendation.

recommender system; location-based service; probabilistic matrix factorization; cold-start problem; budget

?born in 1983.

his PhD degree in computer architecture from Shandong University, Jinan, in 2015. His main research interests include information retrieval, social network and recommender system.

Gao Yukai, born in 1993. Master candidate of Shandong Normal University. Student member of CCF. His main research interests include recommender system and POI recommendation.

Wang Xinhua, born in 1970. Professor and master supervisor in Shandong Normal University. Received his master’s degree from Dalian University of Technology. His main research interest include distributed network and recommendation system.

Chen Zhumin, born in 1977. Associate professor and master supervisor in Shandong University. Senior member of CCF. His main research interests include Web information retrieval, data mining.

2017-03-16；

：2017-06-08

國家自然科學(xué)基金項目(61602282,61602284);中國博士后科學(xué)基金項目(2016M602181);國家社會科學(xué)基金項目(14BTQ049) This work was supported by the National Natural Science Foundation of China (61602282, 61602284), the Postdoctoral Science Foundation of China (2016M602181), and the National Social Science Foundation of China (14BTQ049).

郭磊(guolei@sdnu.edu.cn)

TP391