基于排序學習的PRLMDF推薦算法

劉金花，焦 嘉（通信作者）

（湖南信息職業技術學院 湖南 長沙 410203）

0 引言

社交網絡環境下，如何合理利用大量的數據信息進行準確和高精度的興趣點（point of Interest, POI）推薦成為研究熱點[1]。興趣點推薦系統通過分析用戶的歷史簽到數據，得到用戶偏好和行為規律，并結合興趣點的屬性信息，向用戶推薦滿足個性化偏好的興趣點[2]。在位置社交網絡中，用戶訪問興趣點的概率受到多種情景因素（如時間、興趣點分類等）影響，導致興趣點推薦需要考慮多種復雜的因素，近年來，為處理多維信息和提高推薦的準確性，張量（高維擴展矩陣）被廣泛使用來進行建模，CHENG等[3]提出了基于局部區域的張量分解模型，該模型通過融合用戶從當前興趣點移動到下一個興趣點的地理距離信息，為用戶提供準確高效的連續興趣點推薦服務。ADOMAVICIUS等[4]提出了非線性變換，分別提取基于用戶和基于POI的空間意圖，以解決冷啟動問題。綜上所述，興趣點推薦是當前比較流行的研究領域，但仍存在地點的冷啟動問題和推薦的準確度低的缺點[5-7]。

1 多粒度級聯森林模型構建

文章使用多重加法回歸樹替代LambdaRank算法的神經網絡來優化目標函數，綜合考慮現有的技術，加入多粒度級聯森林，它是一個決策樹森林模型，每一個節點是一個項目或個體，加入了深度學習的池化技術，將需要考慮的特征自動組合輸入，提出了基于排序學習的PRLMDF推薦算法，從而更加提高算法的學習能力，達到提高準確度的效果。

1.1 數據集預處理

在興趣點預測預處理中，一般在給定的類別結果知道的情況下實現top-k的興趣點推薦。在預處理階段，將數據進行歸一化處理，使用縮放歸一化，將數據的每一個特征控制在[0， 1]的范圍，對每個維度的特征x：

其中min和max分別是數據樣本的某個特征在該樣本的所有值中的最小值和最大值，使得在計算和算法實現時的運算更加方便，具體在運算時，由于保持和運行的數據的變小，導致需要的內存更少。

1.2 模型結構構建

在處理排序問題上，用戶進行訓練階段有許多模型可以選擇，文章選擇決策樹，使用梯度提升樹來決策，在每次迭代后，生成多棵決策回歸樹，在迭代時，每次的層次結構會處理上層結構給出的結果信息，本層的處理結果輸出到結構的下一層，每次考慮一個特征，當無考慮特征時結束層次決策。在提升森林中，網絡的每層是由2個類別的隨機森林組成的，包括2棵隨機森林和2棵半隨機森林，在森林中包含很多的決策樹，通過分裂進行迭代下去，在模型中，完全的隨機森林不僅對特征進行列式采樣，還要進行水平采樣。如下圖1是多粒度級聯森林的結構圖。

當輸入數據進入模型結構，模型中的決策樹通過最小化殘差和來擬合結果數據，生成的數據結果將是以向量的形式構建的，它將與原始特征向量拼接，形成的數據結果統一輸入到多粒度級聯森林模型的下一層，在構建時，如果森林的樹是4，有2個森林的話會產生一個8的維度向量，在本層的平均值是本層的預測結果，和上一層的輸出結果的和是最終的預測結果。在實驗具體操作時，為了防止網絡爆炸現象，每層的隨機森林網絡都需進行交叉驗證，在進行訓練時，如果增益結果不好將停止訓練，對于訓練的網絡的層數是可以自動控制的。

2 PRLMDF排序算法

2.1 損失函數的梯度表示

在模型中使用直接的梯度下降方法進行最小化損失函數。輸入數據和輸出數據都是Listwise形式，對于任意的個性i，j，模型最終輸出的結果為ri和rj，損失函數可定義為：

其中，損失函數的梯度是：

在得到了梯度之后，由于梯度在迭代時是變化的，如何將梯度結合模型進行優化，對于提出的算法，需要的是對每層結構進行優化，我們接下來基于模型和梯度的公式，使用特征池化進行輸入數據的優化，在具體的迭代過程中，使用提升算法，得到結果進行排序。

2.2 決策樹描述

在多粒度森林模型中包含若干個決策樹，獲取隨機特征時，使用水平采樣方式進行，經過水平抽樣后集合變為{，yi}，從決策樹的root節點開始出發，去探索隨機特征，遞歸和循環地進行分裂節點，開始決策樹的模型建立，使得節點的損失函數最小和達到對應的分裂閾值，分裂的公式為：

在問題上轉化為求解minG，遍歷特征使得公式（4）最小，使用該特征進行左右分裂，左右葉子節點的輸出為：

節點的結束是由于無顯著變化和數據量少將停止迭代，最后將結果分為 M個節點的決策樹。

2.3 PRLMDF推薦算法

排序學習最早應用于信息檢索領域，使用訓練實例構建排序模型，結合機器學習思想，迭代優化模型參數，用訓練完成的排序模型進行推薦[8-10]。興趣點排序最初是以類別推薦的數據結果作為輸入的，將樣本數量m和學習率進行初始化，設置最大的迭代次數N，以及特征樹的窗口，使用minScan池化特征并為左右孩子賦初值。下列代碼為PRLMDF算法的偽代碼實現。

在每次迭代的時候，該層接收上層的輸出結果，與當前特征進行拼接，形成新的輸入，該層的數據擬合目標λi，對于森林模型，分別進行訓練，使用算法PRLMDF算法進行構建和推薦，輸出向量Lk，對所有的向量取均值，乘以學習率，更新最后的預測結果，迭代執行，直到循環終止，輸出排序推薦結果。

3 實驗結果與分析

3.1 評價標準

興趣點的推薦的評價標準是為了評價推薦系統的好壞，一個好的推薦系統是能夠滿足用戶需求，為用戶推薦準確滿意的內容，具體的量化指標是準確度和召回率，準確度的高低決定這預測的質量和算法的好壞，準確率和召回率如下面的公式所示：

通俗的來講：

TP是錯的，FN是預測是錯的，而結果是對的，TN是預測和真實值都是錯的，若預測好，TP和TN都要越大，Precision是預測出的地點結果a和選取N個地點類別的比值，對于本文來說，將采用準確度和召回率進行評價。召回率也叫作查全率。

3.2 實驗結果與準確度分析

本文使用Foursquare收集的洛杉磯和紐約的兩大規模數據集評估模型的性能，使用Foursquare提供的目錄來推斷從數千個地點到249個類別的映射。80%的數據用作訓練集，剩下20%的數據用作測試集，數據集統計信息詳見表1。

表1 數據統計

我們將興趣點推薦分為2步，先是預測出興趣點可能出現的類別，然后再進行具體的興趣點推薦，圖2是提出的方法和其他四個地點推薦方法的對比，分別在紐約和洛杉磯兩個城市進行實驗，實驗數據是公開的數據集，并分別對推薦地點個數為1，5，10，20，50，100進行了實驗，從圖2可以看出，PRLMDF方法在各個級別的推薦地點上，都有明顯的提高，相比最好的方法TAD_FPMC，在N=1時，在紐約和洛杉磯兩個城市的推薦精度分別提高了126%和317%，隨著N的增加，相應的推薦準確度越來越高，在實驗中發現，人們更加喜歡去屬于多個類別的地點，這是合理的，因為人們直觀地傾向于去一些中心，為了方便而提供多種類型的服務和產品的高可用性。

圖3為紐約和洛杉磯城市經過興趣點推薦算法PRLMDF和其他先進算法的興趣點的召回率的對比結果，相對應的實驗使用四階張量的算法TAD_FPMC和PRLMDF的召回率在各個選取值中效果都明顯好，而本文提出的算法在與TAD_FPMC比較時，也有明顯提升。

4 結語

針對興趣點推薦中面臨的挑戰，本文利用排序學習和分布式思想設計算法，提出了基于排序學習的PRLMDF推薦算法，將類別推薦結果經過預處理和使用多粒度級聯森林來構建推薦模型，在兩個真實數據集上的實驗結果表明，本文提出的方法可以大幅度提高興趣點推薦的精確度。