基于Prank算法的推薦技術研究與應用

張栩晨

基于Prank算法的推薦技術研究與應用

張栩晨

隨著互聯網的普及與發展，網絡上信息與日俱增，但用戶卻越來越難以在有限時間內找尋到想要的信息。推薦系統是解決這一問題的重要方法之一，推薦系統可以根據用戶歷史行為分析出用戶需求來進行推薦，使用戶快速的、準確的做出選擇。研究在推薦系統上應用Prank算法，Prank算法是信息檢索領域經典的排序學習算法。它可以快速地訓練一組特征與排序的關系，做出準確的預測。本文將Prank算法改進以適應Top-N推薦問題，與推薦系統上著名的Item-based，User-based，SVD model算法進行橫向比較，通過大量實驗給出各算法的優缺點。Prank算法在推薦準確度，推薦多樣性問題上取得了較為不錯的實驗結果。

推薦系統；Prank算法；推薦模型；排序學習

0　引言

隨著互聯網的普及和發展，互聯網上的信息與日俱增。用戶喜歡從海量信息中挖掘自己感興趣的信息，但負面效果是用戶很難從過于龐大的信息當中找到想要的信息，所花費的時間精力也與之相應增加。推薦系統是解決這一問題的切實可行的方法。從定義上說，推薦系統在電子商務網站上決定著給用戶提供哪些商品的信息，給用戶提供應該購買什么產品的建議，一定程度上是現實中商店售貨員給客戶推薦物品過程的模擬。推薦系統可以根據用戶不同的需求來進行推薦，推薦還可以根據用戶歷史購買記錄所呈現出的興趣對每個用戶建立不同的模型。一個成功的推薦系統是能夠發現用戶的潛在興趣，對用戶提供最優質的推薦服務，進而使用戶對推薦系統產生依賴感。另一方面，好的推薦系統并不一定為了提高用戶的購買量而只推薦那些熱門的商品，而同時考慮冷門商品帶給用戶的驚喜的可能性，進而提高用戶體驗，這被稱為推薦的多樣性［5］。

個性化推薦是推薦系統的核心，對于不同的用戶，用戶興趣千差萬別，用戶需求隨之存在巨大差距，為此個性化推薦系統應運而生。個性化推薦系統可以根據不同的用戶建立不同的模型，建模可以用到用戶自己填寫的興趣、愛好等，也可以利用用戶的購買記錄及評分、瀏覽記錄、搜索記錄、客戶所在城市等等。個性化推薦系統是真正意義上的推薦系統，可以根據用戶歷史行為為用戶量身定制推薦，所以，個性化推薦系統較以往的非個性化推薦系統有著更好的推薦效果。

本文所做工作是將排序學習的經典算法Prank［1-2］應用到推薦系統上，并加以改進進而實現個性化推薦。在推薦系統中，對用戶進行Top-N推薦是研究的熱點，Top-N推薦可以理解為根據用戶歷史行為給用戶以一定序列推薦N個物品。它實質上是排序問題，將待推薦商品進行評估、排序后推薦。以這個點出發，本文將在信息檢索與排序學習領域熱門算法Prank應用到推薦系統上來，并予以改進應用。Prank算法的特點是可以較為清晰的描述用戶特征，能夠對排序做很精確的預測。本文首先改進應用Prank算法，以用戶歷史購買記錄作為商品特征進行訓練出模型，利用模型推薦以達到個性化推薦的目的。其次，將Prank算法與當下流行的Item-based［3］，User-based［4］，SVD model推薦算法進行橫向比較，Prank算法在Top-N推薦多樣化問題上得到了較為不錯的結果。本文的核心貢獻如下：

1）實現Prank算法并設計其應用到推薦系統的方式。

2）利用大量實驗分析Prank算法在推薦準確度與推薦多樣性上的效果，Prank算法在個性化推薦上取得了不錯的效果。

1　相關工作

1.1 協同過濾

協同過濾［7］算法是推薦系統中最早的方法之一，直到今天推薦效果仍然很好，廣泛被工業界采用。它可以首先找出與此用戶興趣相似的用戶，這些興趣相似的用戶被稱為此用戶的近鄰，近鄰感興趣的內容會被推薦給此用戶。這與現實中接受親朋好友的推薦購買商品道理上是相通的。或者通過找出與此商品相似的被用戶歷史評價過的商品，來完成對此物品評分的估計。協同過濾往往利用該用戶的鄰居用戶（或該物品的鄰居物品）對商品的評價進行加權平均來獲得用戶對該商品的好感度，而這一好感度可以被用來排序，排在前面的商品會被推薦。

協同過濾會隱式地分析用戶的興趣，分析商品的特征，一些不符合用戶口味的商品就被過濾掉。另外，協同過濾與其他推薦算法相比，能夠潛在的發現用戶的興趣。典型的協同過濾算法分為Item-based算法和User-based算法，它們分別計算物品與物品、人與人之間的相似度，利用鄰居幫助預測用戶打分。

2.2SVD model算法

SVD model算法是基于模型的推薦算法中很重要的部分，它利用機器學習算法對每個用戶與商品訓練出一個向量，利用向量的積來表示用戶對該商品的喜愛程度，進而進行推薦。在用戶電影的數據集中，某一隱藏維度可能代表動作片，用戶向量在該維度上代表著他對此類電影的喜愛程度，而電影向量在該維度上代表著這個電影屬于動作片的程度。

SVD首先確定用戶與物品向量的維度k，對每個用戶u和物品i生成一個初始的向量pu和qi。對于每一個預測評分Rui=bu+bi+pTu?qi。其中bu是用戶u的偏好，q_i是物品i的被喜愛偏好。例如某一用戶喜歡比其他用戶平均分打出略低的分數，bu=-0.2。而《泰坦尼克號》特別受歡迎，qi=0.5。所有參數通過最小化損失函數，進行訓練，進而擬合模型。損失函數如公式（1）：

最小化損失函數使用隨機梯度下降方法，最小化上式，以達到擬合模型的目的，其中λ為防止過擬合參數，公式右側整項是為防止過擬合設置的懲罰項。

參數更新法則如公式（2-5）

其中a為學習速率。

2　Prank算法在推薦系統上的應用

2.1排序學習與Prank算法

Prank算法具體過程如圖1所示：

圖1　Prank算法流程

2.2Prank的應用

模型訓練過程：

對任何一個用戶u進行如下過程

Top-N推薦預測過程：

3　實驗

3.1數據集與Top-N推薦測試方法

實驗數據集為MovieLens，包含大小為100k，1M，10M 3個部分，本文主要采用100k，1M的數據集進行實驗與分析。每個數據集包含用戶對物品的評分。

對推薦系統進行評價的方法中，Top-N推薦是一個重要的研究方向，其含義是對用戶推薦N個物品，觀察用戶對這N個物品的態度。具體方法是對每個用戶購買過的物品，從中抽取10%放入測試集合，另外90%作為訓練集合，剩下的未購買物品與測試集合共同輸入給算法，算法從中挑選出N個物品作為Top-N推薦給用戶，觀察這Top-N個物品與測試集合的交集的數目與N的比值即為對該用戶的precision。將所有用戶的precision取平均數即為該算法的效果衡量指標。

在信息檢索領域，準確度precision是衡量系統準確性的重要指標。定義如下：

其中T代表實際用戶購買的商品，R代表所有做出的推薦。

2）推薦準確度的比較

通過對本文實驗數據的總結，在Top-N=10，20，數據集大小為100k，1M情況下，可以對4種算法做推薦取得的準確度進行對比，結果如圖2至圖3所示：

圖2　4種算法在100k數據集上Top-10推薦準確度比較

在100k數據集上做Top-N=10推薦，Prank算法準確度達到0.124，低于Item-based算法的0.194和SVD model算法的0.184。在Top-N=20推薦上，Prank算法準確度達到0.095。

在1M數據集上做Top-N=10推薦，Prank算法準確度達到0.119，而Item-based算法準確度達到0.177。在Top-N=20推薦上，Prank算法準確度達到0.096，SVD model算法達到0.109，略高于Prank算法。如圖4、圖5所示：

圖4　4種算法在1M數據集上Top-10推薦準確度比較

圖5　4種算法在1M數據集上Top-20推薦準確度比較

3）推薦多樣性的比較

關于推薦多樣性，我們觀察在Top-N=10，100k數據集上，Prank算法與Item-based算法在推薦商品被購買次數區間與推薦次數的關系圖表。如表1所示：

表1　Prank算法與Item-based算法100k數據集Top-10推薦多樣性比較

由表1可以看出，在［41，80］，［81，140］，［141，200］，［201，300］這些相對被購買數較少的物品區間，Prank算法能較多的推薦，在這些小眾物品上，Item-based算法由于其算法相似度公式的局限性，這些物品很難被推薦，如表2所示：

表2　Prank算法與Item-based算法在100k數據集Top20推薦多樣性比較

由表2可以看出，在Top-20推薦問題上，prank算法更多的推薦那些被購買數在［41，200］的商品，而Item-based算法對被購買區間在［0，140］的商品幾乎不推薦，而更多的推薦那些最受歡迎的產品。

4　總結

與現有推薦算法相比，Prank算法在推薦準確度方面上處于中游，但仍有改進空間。Prank算法在推薦多樣性上優勢較大，能夠給用戶帶來驚喜。

關于推薦準確性：Prank算法在訓練過程中，是針對不同的用戶訓練不同的模型，而該模型的訓練數據完全是用戶購買過的物品的集合。對該訓練數據特征的選取，除了可以采用評分向量以外，還可以采取物品本身特征等特性，這將是提高Prank算法推薦準確度的途徑。Prank算法在訓練迭代中不斷縮小預測排位與實際排位的差，以達到準確預測排位的目的。

從實現推薦的原理上看，Prank算法的應用與User-based算法在道理上極為相似。Prank算法訓練出的w向量中的每一維度恰好對應了一個用戶和自己的相似度，而預測值是由該相似度線性組合而成的，但它與User-based算法的區別在于它在訓練過程中是不斷擬合該用戶與自身的相似度的。而User-based算法是通過他們共同購買的物品向量的相似度而計算他們之間的相似度。所以，在最后推薦準確度上，Prank上要高于User-based算法。利用此想法，因為Prank算法能夠訓練出該用戶（物品）對未知物品（用戶）的評分是由哪些鄰居加權而來的。用戶和物品在評分矩陣上只是維度不同，如果將所有物品和用戶的位置互換做Prank，對每個物品建模，勢必會取得比Item-based更好的推薦準確度，這將是以后可以嘗試的工作。而Prank算法在訓練過程中，為了使訓練能更為迅速，更為準確，要采用合適的訓練參數，以防止出現訓練無法達到最佳精度與訓練次數過多導致模型過擬合等問題。這些問題同樣值得深入研究。

關于推薦多樣性：由于Prank算法訓練的獨特性，它推薦的物品與存在嚴重單一化推薦的Item-based算法相比具有更強的多樣性。這是因為Prank算法采用的是將所有用戶的意見加權聽取意見的方式，而有的意見有正面效果，有的意見有負面效果，所以并不會出現Item-based算法中被購買多的物品之間的距離往往更小帶來的連帶推薦效應而降低推薦多樣性。

［1］ Crammer K， Singer Y. Pranking with Ranking［J］. Advances in Neural Information Processing Systems， 2002，14：641--647.

［2］ Koren Y. Factorization meets the neighborhood： a multifaceted collaborative filtering model.［C］// Acm Sigkdd International Conference on Knowledge Discovery & Data Mining. 2008：426-434.

［3］ Deshpande M， Karypis G. Item-Based Top-N Recommendation Algorithms［J］. Acm Transactions on Information Systems， 2004， 22（1）：143--177.

［4］ 任看看， 錢雪忠. 協同過濾算法中的用戶相似性度量方法研究［J］. 計算機工程， 2015， 41（8）：18-22.

［5］ Zhang M， Hurley N. Avoiding monotony： improving the diversity of recommendation lists.［C］// Proceedings of the 2008 ACM conference on Recommender systems. ACM，2008：123-130.

［6］ 曾瑋. 文獻排名預測算法及作者影響力評估算法研究［D］. 西南大學， 2014.

［7］ 黃梅娟. 協同過濾算法在個性化就業推薦系統中研究［J］. 電腦知識與技術， 2015（08）.

Prank Algorithm-based Research and Application for Recommender System

Zhang Xuchen
（Fudan University， Shanghai 201203， China）

With the development of Internet， the information on the Internet grows with each passing day， but users are hard to get the wanted information in limited time. One way of solving this question is Recommender System， Recommender System could get users' requirements by users' history behaviors， and make user select quickly and accurately. In this essay， the main point is to apply the Prank algorithm to Recommender System， Prank algorithm is a classic learning-to-rank algorithm in Information Retrieval. It could train the relations between a set of features and rank， and make accurate predictions. In this essay， we make a slight improvement of Prank algorithm to adjust to top-N recommendation problem， compare Item-based algorithm， User-based algorithm， SVD model algorithm in Recommender System with Prank algorithm， and give the advantages and disadvantages between them. The Prank algorithm gets good experiment results on recommendation precision and recommendation diversity problem.

Recommender System； Prank Algorithm； Recommender Model； Learning to Rank

TP311

A

1007-757X（2016）06-0058-04

2015.12.22）

張栩晨（1990-），男，復旦大學，碩士研究生，研究方向：推薦系統與機器學習，上海，201203