張栩晨

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

張栩晨

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

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

0　引言

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

個(gè)性化推薦是推薦系統(tǒng)的核心，對(duì)于不同的用戶(hù)，用戶(hù)興趣千差萬(wàn)別，用戶(hù)需求隨之存在巨大差距，為此個(gè)性化推薦系統(tǒng)應(yīng)運(yùn)而生。個(gè)性化推薦系統(tǒng)可以根據(jù)不同的用戶(hù)建立不同的模型，建?？梢杂玫接脩?hù)自己填寫(xiě)的興趣、愛(ài)好等，也可以利用用戶(hù)的購(gòu)買(mǎi)記錄及評(píng)分、瀏覽記錄、搜索記錄、客戶(hù)所在城市等等。個(gè)性化推薦系統(tǒng)是真正意義上的推薦系統(tǒng)，可以根據(jù)用戶(hù)歷史行為為用戶(hù)量身定制推薦，所以，個(gè)性化推薦系統(tǒng)較以往的非個(gè)性化推薦系統(tǒng)有著更好的推薦效果。

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

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

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

1　相關(guān)工作

1.1 協(xié)同過(guò)濾

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

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

2.2SVD model算法

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

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

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

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

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

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

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

Prank算法具體過(guò)程如圖1所示：

圖1　Prank算法流程

2.2Prank的應(yīng)用

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

對(duì)任何一個(gè)用戶(hù)u進(jìn)行如下過(guò)程

Top-N推薦預(yù)測(cè)過(guò)程：

3　實(shí)驗(yàn)

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

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

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

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

其中T代表實(shí)際用戶(hù)購(gòu)買(mǎi)的商品，R代表所有做出的推薦。

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

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

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

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

在1M數(shù)據(jù)集上做Top-N=10推薦，Prank算法準(zhǔn)確度達(dá)到0.119，而Item-based算法準(zhǔn)確度達(dá)到0.177。在Top-N=20推薦上，Prank算法準(zhǔn)確度達(dá)到0.096，SVD model算法達(dá)到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)于推薦多樣性，我們觀(guān)察在Top-N=10，100k數(shù)據(jù)集上，Prank算法與Item-based算法在推薦商品被購(gòu)買(mǎi)次數(shù)區(qū)間與推薦次數(shù)的關(guān)系圖表。如表1所示：

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

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

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

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

4　總結(jié)

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

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

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

關(guān)于推薦多樣性：由于Prank算法訓(xùn)練的獨(dú)特性，它推薦的物品與存在嚴(yán)重單一化推薦的Item-based算法相比具有更強(qiáng)的多樣性。這是因?yàn)镻rank算法采用的是將所有用戶(hù)的意見(jiàn)加權(quán)聽(tīng)取意見(jiàn)的方式，而有的意見(jiàn)有正面效果，有的意見(jiàn)有負(fù)面效果，所以并不會(huì)出現(xiàn)Item-based算法中被購(gòu)買(mǎi)多的物品之間的距離往往更小帶來(lái)的連帶推薦效應(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］ 任看看， 錢(qián)雪忠. 協(xié)同過(guò)濾算法中的用戶(hù)相似性度量方法研究［J］. 計(jì)算機(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］ 曾瑋. 文獻(xiàn)排名預(yù)測(cè)算法及作者影響力評(píng)估算法研究［D］. 西南大學(xué)， 2014.

［7］ 黃梅娟. 協(xié)同過(guò)濾算法在個(gè)性化就業(yè)推薦系統(tǒng)中研究［J］. 電腦知識(shí)與技術(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)與機(jī)器學(xué)習(xí)，上海，201203