協(xié)同過(guò)濾的一種個(gè)性化推薦算法研究

摘要：在分析傳統(tǒng)推薦算法不足的基礎(chǔ)上，提出一種稀疏矩陣下的個(gè)性化改進(jìn)策略。首先進(jìn)行一對(duì)一的個(gè)性化預(yù)測(cè)，得到虛擬用戶(hù)評(píng)分矩陣，在此基礎(chǔ)上再進(jìn)行綜合預(yù)測(cè)。該方法避免了傳統(tǒng)推薦算法中推薦值與用戶(hù)相似度不密切相關(guān)的弊端，提高了協(xié)同過(guò)濾的預(yù)測(cè)精度，尤其是在矩陣極端稀疏情況下的預(yù)測(cè)精度。最后通過(guò)實(shí)驗(yàn)驗(yàn)證了算法的有效性和優(yōu)越性。

關(guān)鍵詞：協(xié)同過(guò)濾；稀疏矩陣；相似度；個(gè)性化推薦

中圖分類(lèi)號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)01－0039－03

協(xié)同過(guò)濾算法不依賴(lài)于商品的語(yǔ)義描述，只根據(jù)用戶(hù)的意見(jiàn)或行為即能產(chǎn)生推薦，是目前推薦系統(tǒng)(recommender system)中應(yīng)用最廣泛和成功的技術(shù)。但是協(xié)同過(guò)濾推薦系統(tǒng)中項(xiàng)目空間巨大，導(dǎo)致矩陣極端稀疏。傳統(tǒng)的推薦算法在高維稀疏矩陣上進(jìn)行運(yùn)算往往導(dǎo)致不準(zhǔn)確的推薦，從而影響系統(tǒng)的應(yīng)用和推廣。本文從協(xié)同過(guò)濾的推薦算法入手，指出傳統(tǒng)推薦算法在矩陣稀疏情況下的不足，進(jìn)而提出一種新的個(gè)性化推薦策略，通過(guò)算法進(jìn)行模擬，改進(jìn)了精度。

1協(xié)同過(guò)濾算法及分析

1．1協(xié)同過(guò)濾工作原理

在實(shí)際生活中，對(duì)于不熟悉的問(wèn)題或事物，人們往往要咨詢(xún)自己的朋友或是信任的人，根據(jù)他們的判斷和看法和作出自己的選擇。 

協(xié)同過(guò)濾就是模擬這個(gè)過(guò)程，根據(jù)用戶(hù)的行為和其他用戶(hù)的行為（評(píng)分、評(píng)論、購(gòu)買(mǎi)歷史、瀏覽次數(shù)、在某一網(wǎng)頁(yè)上的停留時(shí)間等）的比較，找出最相似的鄰居，根據(jù)與之最相似鄰居的興趣或偏好預(yù)測(cè)出該用戶(hù)的興趣或偏好，以幫助其進(jìn)行決策的一種算法。

圖1顯示了協(xié)同過(guò)濾的原理[1]。其中用戶(hù)1、2和3都對(duì)項(xiàng)目A、B和C表現(xiàn)出興趣，如這三個(gè)用戶(hù)都評(píng)價(jià)了電影A、B和C，這種重合表明他們有相似的興趣。因此，可以認(rèn)為向用戶(hù)2推薦D和E是比較可行的，因?yàn)镈和E都被用戶(hù)1和3所喜歡。

協(xié)同過(guò)濾基于以下假設(shè)：人與人之間存在偏好和興趣上的相似；人對(duì)事物的偏好是具有穩(wěn)定性的，因此可根據(jù)過(guò)去的偏好預(yù)測(cè)未來(lái)的選擇。

1．2協(xié)同過(guò)濾算法的步驟

一般說(shuō)來(lái)，協(xié)同過(guò)濾算法可以分為構(gòu)建用戶(hù)檔案、尋找最近鄰、產(chǎn)生推薦[2]三步。

1)構(gòu)建用戶(hù)檔案收集用戶(hù)的評(píng)分、評(píng)價(jià)行為等，并進(jìn)行數(shù)據(jù)清理、轉(zhuǎn)換和錄入，最終形成用戶(hù)對(duì)各種項(xiàng)目的評(píng)價(jià)矩陣，如表1所示。其中：Rij代表第i個(gè)用戶(hù)Ui對(duì)商品Ij的評(píng)分。一般說(shuō)來(lái)，0≤Rij≤5。分?jǐn)?shù)越高，用戶(hù)對(duì)該項(xiàng)目的認(rèn)可度越高。

更進(jìn)一步，如果這個(gè)向量代表的用戶(hù)i是許多乃至所有用戶(hù)的最近鄰居，那么對(duì)所有目標(biāo)用戶(hù)而言，對(duì)某一項(xiàng)目的推薦值都為這個(gè)用戶(hù)的原始評(píng)價(jià)值。如果這個(gè)用戶(hù)對(duì)某一項(xiàng)目的評(píng)價(jià)為5，那么所有用戶(hù)都會(huì)根據(jù)這個(gè)用戶(hù)的評(píng)價(jià)值得到為5的推薦值。這個(gè)項(xiàng)目將成為排行榜上的第一名（top one），這是不準(zhǔn)確的。因?yàn)檫@個(gè)推薦僅僅是根據(jù)一個(gè)用戶(hù)對(duì)這個(gè)項(xiàng)目產(chǎn)生的比較極端的評(píng)價(jià)；相反，如果這個(gè)用戶(hù)對(duì)某一項(xiàng)目產(chǎn)生一個(gè)極端低的評(píng)價(jià)，如1，那么這個(gè)項(xiàng)目也就永遠(yuǎn)不能有機(jī)會(huì)推薦給其他人。這兩種情況都是非常不符合實(shí)際情況的。上述兩種情況由于數(shù)據(jù)集的巨大而時(shí)有發(fā)生。傳統(tǒng)的推薦算法在矩陣稀疏的情況下，嚴(yán)重影響了系統(tǒng)的推薦精度，降低了系統(tǒng)的可信度。

2改進(jìn)的個(gè)性化推薦策略及算法

2．1個(gè)性化的推薦策略及原理

在矩陣稀疏的情況下，傳統(tǒng)推薦算法在一定程度上抹煞了用戶(hù)間的相似度對(duì)推薦結(jié)果的影響。尤其是當(dāng)最近鄰居集內(nèi)只有一個(gè)用戶(hù)對(duì)某個(gè)項(xiàng)目產(chǎn)生評(píng)價(jià)時(shí)，最后的推薦精度大大降低。

在現(xiàn)實(shí)世界中，人們常常咨詢(xún)朋友或信任的人。他們的推薦往往是一對(duì)一的行為，即找到一個(gè)相似的用戶(hù)，根據(jù)目標(biāo)客戶(hù)與相似客戶(hù)的相似度產(chǎn)生對(duì)某一項(xiàng)目的預(yù)測(cè)值；再找到一個(gè)相似的用戶(hù)，根據(jù)它們之間的相似程度產(chǎn)生一個(gè)預(yù)測(cè)值……，直到找完所有的相似用戶(hù)；最后根據(jù)每個(gè)相似用戶(hù)產(chǎn)生的預(yù)測(cè)值產(chǎn)生最后的預(yù)測(cè)值。這個(gè)過(guò)程如圖2右側(cè)所示；左側(cè)部分為傳統(tǒng)推薦算法的推薦過(guò)程。

2．2個(gè)性化推薦算法

根據(jù)2.1節(jié)的分析，個(gè)性化推薦算法可分為兩個(gè)步驟，即一對(duì)一的個(gè)性化預(yù)測(cè)和綜合相似度的最終預(yù)測(cè)。

根據(jù)一對(duì)一的原理，本文對(duì)傳統(tǒng)的兩種推薦算法進(jìn)行改進(jìn)，即目標(biāo)客戶(hù)對(duì)某個(gè)項(xiàng)目的評(píng)價(jià)是根據(jù)最近鄰居集內(nèi)的每個(gè)鄰居產(chǎn)生一個(gè)評(píng)價(jià)；最后根據(jù)所有對(duì)這個(gè)項(xiàng)目產(chǎn)生過(guò)評(píng)價(jià)的最近鄰居再次引入相似度，產(chǎn)生一個(gè)綜合評(píng)價(jià)。這個(gè)個(gè)性化的推薦算法如式(8)所示。

3．3實(shí)驗(yàn)過(guò)程

1）相似度公式的選取

式(1)~(3)是協(xié)同過(guò)濾算法常用的三種度量相似度的公式。為了獲得較好的實(shí)驗(yàn)結(jié)果，本文分別用這三種公式對(duì)測(cè)試集和訓(xùn)練集用戶(hù)之間的相似性進(jìn)行計(jì)算。值的分布如表2所示。

從表2中可以看出，相似度分布最差的是修正的余弦相似度。在0~1內(nèi)，分布比較集中在[0，0.15]，比例高達(dá)87%，這說(shuō)明用此公式計(jì)算出的用戶(hù)之間的相似度過(guò)低。用這種公式得不到計(jì)算結(jié)果的占1.5%，計(jì)算結(jié)果小于等于0的占11.2。之所以這樣，是因?yàn)樾拚挠嘞蚁嗨菩怨降姆肿硬糠忠?jì)算兩個(gè)用戶(hù)之間共同評(píng)價(jià)過(guò)的項(xiàng)目。而在稀疏矩陣的情況下，兩個(gè)用戶(hù)共同評(píng)價(jià)過(guò)的項(xiàng)目非常少，分子的值非常小，甚至沒(méi)有；余弦相似性的分母部分是兩個(gè)用戶(hù)共同評(píng)價(jià)過(guò)的項(xiàng)目空間，這部分值相對(duì)于分母而言顯得過(guò)大。因此導(dǎo)致整個(gè)相似度公式的值非常小，與實(shí)際情況不相符。Pearson相關(guān)度和余弦相似度計(jì)算公式各有優(yōu)缺點(diǎn)。余弦相似度公式可以得出所有用戶(hù)之間的相似度，但相似度值相對(duì)來(lái)說(shuō)集中在[0，0.5]。Pearson相關(guān)性相似度公式由于在分子分母上計(jì)算的都是兩個(gè)用戶(hù)共同評(píng)價(jià)過(guò)的項(xiàng)目，相似度值相對(duì)來(lái)說(shuō)分布較分散。從表中可看出[0，1]內(nèi)都有分布。另一方面，由于要計(jì)算兩個(gè)用戶(hù)共同評(píng)價(jià)過(guò)的項(xiàng)目，pearson相關(guān)相似性公式得不出計(jì)算結(jié)果的為2．31%。

在以上分析的基礎(chǔ)上，通過(guò)對(duì)余弦相似度和pearson相關(guān)相似度兩種公式對(duì)的預(yù)測(cè)精度進(jìn)行比較，結(jié)果如圖3所示。

從圖3中可以看出，不論應(yīng)用哪一種傳統(tǒng)的預(yù)測(cè)算法（考慮評(píng)價(jià)風(fēng)格與否），余弦相似度都表現(xiàn)出比pearson相關(guān)相似度良好的預(yù)測(cè)精度。這是因?yàn)樵谙∈杈仃図?xiàng)目空間下運(yùn)算，兩個(gè)用戶(hù)共同評(píng)價(jià)過(guò)的項(xiàng)目數(shù)量很少，根據(jù)很少的共同評(píng)價(jià)過(guò)的項(xiàng)目來(lái)判斷兩個(gè)用戶(hù)相似與否，可信度并不高。所以雖然表1的pearson相似度表現(xiàn)出良好的分布特性，但實(shí)際的預(yù)測(cè)值并不理想。另一方面，圖3再次證明余弦相似度的有效性。

基于以上分析，筆者在以后的實(shí)驗(yàn)中，采用余弦相似性對(duì)用戶(hù)的相似度進(jìn)行度量。

2）實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證本文算法的有效性，以式（4）和（5）作為對(duì)照，分別以余弦相似性和pearson相關(guān)相似性作為相似度度量標(biāo)準(zhǔn)計(jì)算其MAE。最近鄰居個(gè)數(shù)為1~30，與本文提出的個(gè)性化推薦算法（PCF）進(jìn)行比較。實(shí)驗(yàn)結(jié)果如圖4所示。其中：TCF1代表傳統(tǒng)的協(xié)同過(guò)濾算法且不考慮評(píng)價(jià)風(fēng)格的影響，即式（4）所示；TCF2代表傳統(tǒng)的協(xié)同過(guò)濾算法并且考慮評(píng)價(jià)風(fēng)格的影響，即式（5）所示；PCF為本文提出的個(gè)性化協(xié)同過(guò)濾算法。從圖中可以看出，PCF的預(yù)測(cè)精度是最好的，并在不同鄰居個(gè)數(shù)的情況下表現(xiàn)出良好的穩(wěn)定型；TCF1次之；TCF2精度最差。

另外，在鄰居個(gè)數(shù)很少的情況下，本文的個(gè)性化推薦算法的精度與傳統(tǒng)推薦算法相比有著明顯的優(yōu)越性。當(dāng)選取的最近鄰超過(guò)12個(gè)時(shí)，本文算法的預(yù)測(cè)精度與傳統(tǒng)推薦算法（考慮不同用戶(hù)之間的評(píng)價(jià)風(fēng)格）的預(yù)測(cè)精度相比，保持了一致。當(dāng)用戶(hù)個(gè)數(shù)大于12后，無(wú)論是哪種算法，預(yù)測(cè)精度都沒(méi)有明顯的變化。

通過(guò)分析可知，當(dāng)用戶(hù)的最近鄰個(gè)數(shù)很少時(shí)，對(duì)要預(yù)測(cè)的項(xiàng)目往往只有更少的用戶(hù)對(duì)之作出評(píng)價(jià)，即此時(shí)對(duì)這個(gè)項(xiàng)目的評(píng)價(jià)是極端稀疏的。本文算法由于充分考慮了用戶(hù)的相似度對(duì)最后結(jié)果的影響，取得了較好的推薦結(jié)果。

4結(jié)束語(yǔ)

在分析協(xié)同過(guò)濾推薦原理的基礎(chǔ)上，筆者提出了一種個(gè)性化的推薦策略和算法，即在最近鄰居集的范圍內(nèi)，根據(jù)每個(gè)最近鄰居與目標(biāo)客戶(hù)的相似度，先對(duì)各個(gè)項(xiàng)目產(chǎn)生一個(gè)預(yù)測(cè)值；然后根據(jù)各自的相似度，在預(yù)測(cè)值的基礎(chǔ)上產(chǎn)生一個(gè)綜合的最后推薦值。實(shí)驗(yàn)證明這種算法在矩陣稀疏的情況下，可以取得很好的推薦精度，并且在不同鄰居個(gè)數(shù)的情況下，結(jié)果比較穩(wěn)定。下一步的工作是把該算法應(yīng)用到具體的系統(tǒng)中，檢驗(yàn)其實(shí)際運(yùn)行的效果。

參考文獻(xiàn)：

［1］HERLOCKER J，KONSTAN J，BORCHERS A，et al.An algorithmic framework for performing collaborative filtering[C]//Proc of Confe rence on Research and Development in Information Retrieval.New York：Springer，1999：263－266.

[2]GOLDBERG D，NICHOLS D，OKI B M，et al.Using collaborative filtering to weave an information tapestry[J].Communications of the ACM，1992，35（12）：61 70.

[3]SARWAR B，KARYPIS G，KONSTAN J，et al.Item based collaborative filtering recommendation algorithms[C]//Proc of the 10th International World Wide WebConference.New York：Springer，2001:285－295. [4]鄧愛(ài)林，朱楊勇，施伯樂(lè).基于項(xiàng)目評(píng)分預(yù)測(cè)的協(xié)同過(guò)濾算法[J].軟件學(xué)報(bào)，2003，14（9）：1621 1628.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”