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

高玉凱 王新華 郭 磊 陳竹敏

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

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

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

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

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

推薦系統；位置服務；概率矩陣分解；冷啟動問題；約束

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

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

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

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

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

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

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

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

1 相關工作

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

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

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

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

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

Table 1 Comparison of Recommendation Methods表1 推薦方法優缺點比較

在LBS推薦系統中，由于用戶位置信息的極度稀疏性，LBS推薦面臨嚴重的數據稀疏問題.同時由于LBS的發展迅速產生大量的新用戶，面臨嚴重的用戶冷啟動問題.本文主要針對用戶冷啟動問題，引入額外用戶數據與LBS數據相結合，提出結合多層協同概率矩陣分解與GBDT學習算法的推薦算法.

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

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

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

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

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

2 推薦模型

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

2.1問題描述

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

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

Table 2 Online User Behavior

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

2.2評分預測方法

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

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

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

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

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

Table 4 Merchant Information表4 線下商家數據格式

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

2.3用戶特征學習

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

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

2.4生成推薦列表

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

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

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

3 用戶特征學習

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

3.1PMF算法介紹

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

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

(1)

(2)

(3)

經過貝葉斯推斷，可得到U和V的聯合后驗概率分布為

(4)

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

3.2基于協同概率矩陣分解的SoRec算法

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

(5)

(6)

(7)

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

(8)

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

3.3多層的協同概率矩陣分解算法MPMF

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

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

R,C,S的對數聯合后驗概率分布表示為

(9)

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

(10)

(11)

(12)

(13)

(14)

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

4 實 驗

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

4.1數據集

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

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

Fig. 3 User Scale圖3 用戶比例

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

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

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

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

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

4.2評價方法

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

(15)

(16)

(17)

4.3結果比較

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

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

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

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

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

Fig. 7 The relationship of λC圖7 MPMF結果與λC取值的關系

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

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

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

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

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

5 總 結

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

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

[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)(劉樹棟, 孟祥武. 一種基于移動用戶位置的網絡服務推薦方法[J]. 軟件學報, 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上基于興趣圈中社會關系挖掘的推薦算法[J].計算機研究與發展, 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)(郭磊, 馬軍, 陳竹敏, 等. 一種結合推薦對象間關聯關系的社會化推薦算法[J]. 計算機學報, 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)(張維玉, 吳斌, 耿玉水, 等. 基于協同矩陣分解的評分與信任聯合預測[J]. 電子學報, 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

國家自然科學基金項目(61602282,61602284);中國博士后科學基金項目(2016M602181);國家社會科學基金項目(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