基于Prank算法的推薦技術(shù)研究與應(yīng)用

張栩晨

基于Prank算法的推薦技術(shù)研究與應(yīng)用

張栩晨

隨著互聯(lián)網(wǎng)的普及與發(fā)展，網(wǎng)絡(luò)上信息與日俱增，但用戶卻越來越難以在有限時間內(nèi)找尋到想要的信息。推薦系統(tǒng)是解決這一問題的重要方法之一，推薦系統(tǒng)可以根據(jù)用戶歷史行為分析出用戶需求來進行推薦，使用戶快速的、準(zhǔn)確的做出選擇。研究在推薦系統(tǒng)上應(yīng)用Prank算法，Prank算法是信息檢索領(lǐng)域經(jīng)典的排序?qū)W習(xí)算法。它可以快速地訓(xùn)練一組特征與排序的關(guān)系，做出準(zhǔn)確的預(yù)測。本文將Prank算法改進以適應(yīng)Top-N推薦問題，與推薦系統(tǒng)上著名的Item-based，User-based，SVD model算法進行橫向比較，通過大量實驗給出各算法的優(yōu)缺點。Prank算法在推薦準(zhǔn)確度，推薦多樣性問題上取得了較為不錯的實驗結(jié)果。

推薦系統(tǒng)；Prank算法；推薦模型；排序?qū)W習(xí)

0　引言

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

個性化推薦是推薦系統(tǒng)的核心，對于不同的用戶，用戶興趣千差萬別，用戶需求隨之存在巨大差距，為此個性化推薦系統(tǒng)應(yīng)運而生。個性化推薦系統(tǒng)可以根據(jù)不同的用戶建立不同的模型，建?？梢杂玫接脩糇约禾顚懙呐d趣、愛好等，也可以利用用戶的購買記錄及評分、瀏覽記錄、搜索記錄、客戶所在城市等等。個性化推薦系統(tǒng)是真正意義上的推薦系統(tǒng)，可以根據(jù)用戶歷史行為為用戶量身定制推薦，所以，個性化推薦系統(tǒng)較以往的非個性化推薦系統(tǒng)有著更好的推薦效果。

本文所做工作是將排序?qū)W習(xí)的經(jīng)典算法Prank［1-2］應(yīng)用到推薦系統(tǒng)上，并加以改進進而實現(xiàn)個性化推薦。在推薦系統(tǒng)中，對用戶進行Top-N推薦是研究的熱點，Top-N推薦可以理解為根據(jù)用戶歷史行為給用戶以一定序列推薦N個物品。它實質(zhì)上是排序問題，將待推薦商品進行評估、排序后推薦。以這個點出發(fā)，本文將在信息檢索與排序?qū)W習(xí)領(lǐng)域熱門算法Prank應(yīng)用到推薦系統(tǒng)上來，并予以改進應(yīng)用。Prank算法的特點是可以較為清晰的描述用戶特征，能夠?qū)ε判蜃龊芫_的預(yù)測。本文首先改進應(yīng)用Prank算法，以用戶歷史購買記錄作為商品特征進行訓(xùn)練出模型，利用模型推薦以達到個性化推薦的目的。其次，將Prank算法與當(dāng)下流行的Item-based［3］，User-based［4］，SVD model推薦算法進行橫向比較，Prank算法在Top-N推薦多樣化問題上得到了較為不錯的結(jié)果。本文的核心貢獻如下：

1）實現(xiàn)Prank算法并設(shè)計其應(yīng)用到推薦系統(tǒng)的方式。

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

1　相關(guān)工作

1.1 協(xié)同過濾

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

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

2.2SVD model算法

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

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

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

參數(shù)更新法則如公式（2-5）

其中a為學(xué)習(xí)速率。

2　Prank算法在推薦系統(tǒng)上的應(yīng)用

2.1排序?qū)W習(xí)與Prank算法

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

圖1　Prank算法流程

2.2Prank的應(yīng)用

模型訓(xùn)練過程：

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

Top-N推薦預(yù)測過程：

3　實驗

3.1數(shù)據(jù)集與Top-N推薦測試方法

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

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

在信息檢索領(lǐng)域，準(zhǔn)確度precision是衡量系統(tǒng)準(zhǔn)確性的重要指標(biāo)。定義如下：

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

2）推薦準(zhǔn)確度的比較

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

圖2　4種算法在100k數(shù)據(jù)集上Top-10推薦準(zhǔn)確度比較

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

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

圖4　4種算法在1M數(shù)據(jù)集上Top-10推薦準(zhǔn)確度比較

圖5　4種算法在1M數(shù)據(jù)集上Top-20推薦準(zhǔn)確度比較

3）推薦多樣性的比較

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

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

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

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

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

4　總結(jié)

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

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

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

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

［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］ 任看看， 錢雪忠. 協(xié)同過濾算法中的用戶相似性度量方法研究［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］ 曾瑋. 文獻排名預(yù)測算法及作者影響力評估算法研究［D］. 西南大學(xué)， 2014.

［7］ 黃梅娟. 協(xié)同過濾算法在個性化就業(yè)推薦系統(tǒng)中研究［J］. 電腦知識與技術(shù)， 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-），男，復(fù)旦大學(xué)，碩士研究生，研究方向：推薦系統(tǒng)與機器學(xué)習(xí)，上海，201203