協(xié)同過濾推薦算法綜述

李曉瑜

(安康學(xué)院 電子與信息工程學(xué)院，陜西 安康 725000)

0　引　言

協(xié)同過濾技術(shù)自1992年提出以來，發(fā)展迅速受到了學(xué)術(shù)界的廣泛關(guān)注，特別是在個(gè)性化推薦技術(shù)中引入?yún)f(xié)同過濾算法是近幾年比較熱門的研究趨勢(shì).協(xié)同過濾也稱為社會(huì)過濾，它計(jì)算用戶間偏好的相似性，在相似用戶的基礎(chǔ)上自動(dòng)地為目標(biāo)用戶進(jìn)行過濾和篩選，其基本思想為具有相同或相似的價(jià)值觀、思想觀、知識(shí)水平和興趣偏好的用戶，其對(duì)信息的需求也是相似的[1].協(xié)同過濾主要有兩種類型一種是基于用戶的，另一種是基于物品的.基于用戶的算法是將和目標(biāo)用戶有共同興趣愛好的用戶所喜歡的物品且目標(biāo)用戶沒有購買的物品推薦給目標(biāo)用戶，基于物品的算法是將與目標(biāo)用戶喜歡的物品相似的物品推薦給目標(biāo)用戶.協(xié)同過濾技術(shù)可以說是從用戶的角度來進(jìn)行相應(yīng)推薦的，且推薦的過程是完全自動(dòng)的，即用戶獲得的推薦其系統(tǒng)從購買模式或?yàn)g覽行為等隱式獲得的，不需要用戶努力地找到適合自己興趣的推薦信息，如填寫一些調(diào)查表格等[2].使用協(xié)同過濾推薦算法進(jìn)行推薦其主要步驟為建立用戶評(píng)分表，尋找相似用戶，推薦物品.協(xié)同過濾算法研究與基于內(nèi)容的推薦技術(shù)相比具有如下一些優(yōu)點(diǎn)[3]：

1)避免了傳統(tǒng)基于內(nèi)容過濾時(shí)，產(chǎn)品關(guān)鍵字提取不完全和不精確的問題，通過共享他人的經(jīng)驗(yàn)，能夠推薦一些難以進(jìn)行內(nèi)容分析的項(xiàng)目，比如信息質(zhì)量、個(gè)人品味等難以表述的概念，以及視頻，音樂和藝術(shù)品等商品；

2)具備發(fā)現(xiàn)用戶隱藏興趣的能力.基于內(nèi)容的過濾推薦得到的結(jié)果很多都是用戶本來就熟悉的內(nèi)容，而協(xié)同過濾可以發(fā)現(xiàn)用戶潛在的但自己尚未發(fā)現(xiàn)的興趣偏好，推薦的結(jié)果在內(nèi)容上可以是完全不相似的信息；

3)能夠有效地使用其他相似用戶的反饋信息，較少用戶的反饋量，加快個(gè)性化學(xué)習(xí)的速度.雖然協(xié)同過濾作為一種典型的推薦技術(shù)有其相當(dāng)?shù)膽?yīng)用，但協(xié)同過濾仍有許多的問題需要解決.最典型的問題有稀疏問題(Sparsity)和可擴(kuò)展問題(Scalability).

本文主要對(duì)協(xié)同過濾推薦算法中的關(guān)鍵技術(shù)進(jìn)行總結(jié)并分析了不同技術(shù)存在的問題，同時(shí)還對(duì)協(xié)同過濾技術(shù)的應(yīng)用前景進(jìn)行了展望.

1　近鄰選擇方法比較

計(jì)算用戶或項(xiàng)目的相似度是協(xié)同過濾推薦算法中重要的一個(gè)環(huán)節(jié).在協(xié)同過濾推薦技術(shù)中計(jì)算相似度常用到的方法主要有以下幾種：

1.1　杰卡德相似

1.1.1杰卡德系數(shù)[4]

Jaccard系數(shù)用來度量二值型數(shù)據(jù)的重疊程度，其定義如下：

(1)

其中，分子上是用戶i和用戶j的共有項(xiàng)目；分母上計(jì)算的是用戶i和用戶j的所有項(xiàng)目.在電子商務(wù)中，Jacerad系數(shù)通?？梢杂脕韺?duì)比不同用戶的購物車數(shù)據(jù)，而這種僅適用于二值型的相似性度量方法也限制了其在推薦系統(tǒng)中的進(jìn)一步應(yīng)用[4].

1.1.2杰卡德系數(shù)作為權(quán)重的相似性[4-5]

將杰卡德系數(shù)作為權(quán)重引入相似性計(jì)算.修正后的杰卡德系數(shù)考慮到活躍用戶和熱門項(xiàng)目的評(píng)分?jǐn)?shù)量應(yīng)得到懲罰，修正后的杰卡德系數(shù)表示為：

(2)

將修正后的Jaccard系數(shù)，作為原有的相似性度量方法的權(quán)重系數(shù)，以計(jì)算用戶相似度為例，設(shè)傳統(tǒng)的相似性度量方法用sim(i，j)表示，修正后的相似度用sim+(i，j)表示，則sim*(i，j)可表示為：

sim+(i,j)=J(i,j)sim(i,j)

(3)

這種方式不僅保留了原有方法的易用性，而且克服了傳統(tǒng)的方法面對(duì)稀疏數(shù)據(jù)的局限.

1.2　余弦相似性[6]

用戶評(píng)分被看做是n維項(xiàng)目空間上的向量如果用戶對(duì)項(xiàng)目沒有進(jìn)行評(píng)分，則將用戶對(duì)該項(xiàng)目的評(píng)分設(shè)為0，用戶間的相似性通過向量間的余弦夾角度量設(shè)用戶i和用戶j在n維項(xiàng)目空間上的評(píng)分分別表示為向量i,j，則用戶i和用戶j之間的相似性sim(i，j)為：

(4)

分子為兩個(gè)用戶評(píng)分向量的內(nèi)積，分母為兩個(gè)用戶向量模的乘積.其中Ri,c和Rj,c分別代表用戶i和用戶j對(duì)項(xiàng)目c的評(píng)分.然而在實(shí)際中不同的用戶打分的尺度不一致，有些用戶傾向于打高分，而有些用戶傾向于打低分，此時(shí)余弦相似性就不能準(zhǔn)確地度量用戶間的相似性.

1.3　修正的余弦相似性[6]

余弦相似性度量方法中沒有考慮不同用戶的評(píng)分尺度問題，修正的余弦相似性度量方法通過減去用戶對(duì)項(xiàng)目的平均評(píng)分來改善上述缺陷.其公式表示為：

(5)

在余弦相似性和修正的余弦相似度量方法中，對(duì)所有用戶沒有評(píng)分的項(xiàng)目都將評(píng)分假設(shè)為0.但事實(shí)上用戶對(duì)未評(píng)分商品的喜好程度不可能完全相同對(duì)這些項(xiàng)目的評(píng)分也不可能完全相同(全部為0).因此在用戶評(píng)分?jǐn)?shù)據(jù)極端稀疏的情況下，該方法就不能有效地計(jì)算用戶之間的相似性.

1.4　相關(guān)相似性

1.4.1皮爾遜相關(guān)

皮爾遜相關(guān)是一種度量?jī)蓚€(gè)變量間線性相關(guān)程度的方法.它是一個(gè)介于1和-1之間的值，其中，1表示變量完全正相關(guān)，0表示無關(guān)，-1表示完全負(fù)相關(guān).在協(xié)同過濾算法中，可以利用皮爾遜相關(guān)來計(jì)算兩個(gè)用戶或者兩個(gè)項(xiàng)目之間的相關(guān)性大小[7]；相關(guān)系數(shù)越高，則兩者的相似性越大，反之，則相似性越小.

設(shè)經(jīng)用戶i和用戶j共同評(píng)分的項(xiàng)目集合用Iij表示，則用戶i和用戶j之間的相似性sim(i，j)通過Pearson相關(guān)系數(shù)度量?jī)烧叩南嗨菩钥杀硎緸閇6]：

(6)

其中Ri，c，和Rj，c分別代表用戶i和用戶j對(duì)項(xiàng)目c的評(píng)分，Ri和Rj分別代表用戶i和用戶j在所有項(xiàng)目的評(píng)分平均值.

由于皮爾遜相關(guān)系數(shù)是通過線性回歸公式得到，需要數(shù)據(jù)之間滿足線性關(guān)系以及殘差相互獨(dú)立且均值為0等假設(shè).當(dāng)這些條件不滿足時(shí)，其計(jì)算準(zhǔn)確度將會(huì)降低.

1.4.2pearman秩相關(guān)

pearman秩相關(guān)是利用評(píng)分的等級(jí)來代替評(píng)分值，無需滿足Pearson相關(guān)的假設(shè)，比較適合于用戶評(píng)分?jǐn)?shù)據(jù)是離散的情況.其計(jì)算公式如下：

(7)

由于通常在推薦系統(tǒng)中，項(xiàng)目的評(píng)分等級(jí)非常有限[8]，影響了等級(jí)差異的顯著性，從而影響了最終的秩相關(guān)系數(shù)大小.

1.5　基于項(xiàng)目聚類的用戶最近鄰全局相似性[9]

基于項(xiàng)目聚類的用戶最近鄰全局相似性，先計(jì)算局部最近鄰用戶相似性.局部最近鄰用戶相似性是在k個(gè)項(xiàng)目聚類的基礎(chǔ)上，引入重疊度因子，并將其融合到計(jì)算用戶局部相似度的公式中.用戶u和用戶v在聚類Cj上的局部最近鄰用戶相似性可表示為：

(8)

(9)

其中，|Iu∩Iv∩Cj|指用戶u和用戶v在聚類Cj上共同評(píng)分的項(xiàng)目數(shù)，設(shè)置參數(shù)γ，當(dāng)用戶共同評(píng)分的項(xiàng)目數(shù)小于γ，即數(shù)據(jù)相對(duì)稀疏時(shí)，共同評(píng)價(jià)的項(xiàng)目數(shù)越多，因子值越大，從而保證只有共同評(píng)分項(xiàng)目較多且評(píng)分相似的用戶才有可能成為鄰居用戶.

全局最近鄰用戶相似性可以表示為：

(10)

基于項(xiàng)目聚類的用戶最近鄰全局相似性協(xié)同過濾算法，根據(jù)用戶共同評(píng)分的項(xiàng)目數(shù)量，引入重疊度因子，并將其融合到計(jì)算用戶局部相似度的公式中，來進(jìn)一步加強(qiáng)相似度的準(zhǔn)確性.

2　推薦方法比較

2.1　平均加權(quán)策略

目前大多數(shù)協(xié)同過濾推薦系統(tǒng)都采用平均加權(quán)策略產(chǎn)生推薦[8]，目標(biāo)用戶u對(duì)未評(píng)分項(xiàng)目i的預(yù)測(cè)評(píng)分為：

(11)

2.2　Top-N推薦策略

Top-N推薦策略是分別統(tǒng)計(jì)“最近鄰居”集中的用戶i對(duì)不同項(xiàng)的興趣度的加權(quán)平均值，取其中N個(gè)排在最前面且不屬于Ii(Ii表示用戶i評(píng)分的項(xiàng)目集合)的項(xiàng)作為Top-N推薦集.

3　推薦質(zhì)量評(píng)估方法比較

一個(gè)推薦系統(tǒng)的優(yōu)劣是由其預(yù)測(cè)結(jié)果來衡量的，目前在協(xié)同過濾推薦算法中常用到的評(píng)估策略主要有以下幾種.

3.1　平均絕對(duì)誤差(MAE)

平均絕對(duì)誤差是推薦系統(tǒng)中應(yīng)用最為廣泛的評(píng)估方法[10]，它是通過計(jì)算預(yù)測(cè)值和實(shí)際值之間的絕對(duì)誤差值得到的，計(jì)算公式為：

(12)

其中n為評(píng)分的總數(shù)，pij代表用戶i對(duì)項(xiàng)目j的預(yù)測(cè)評(píng)分，rij代表用戶i對(duì)項(xiàng)目j的實(shí)際評(píng)分，MAE值越小，推薦精度越高.

3.2　均方根誤差(RMSE)[11]

均方根誤差(RMSE)也稱標(biāo)準(zhǔn)平方差，反映評(píng)分?jǐn)?shù)據(jù)的離散程度，計(jì)算公式為：

(13)

其中n為評(píng)分的總數(shù)，pij代表用戶i對(duì)項(xiàng)目j的預(yù)測(cè)評(píng)分，rij代表用戶i對(duì)項(xiàng)目j的實(shí)際評(píng)分，RMSE值越小，推薦精度越高.

3.3　ROC曲線[12]

對(duì)于一個(gè)二分問題，將實(shí)例分成正類(positive)或負(fù)類(negative)，根據(jù)預(yù)測(cè)結(jié)果構(gòu)造以下的二維列聯(lián)表，其中1代表正類，0代表負(fù)類：

表1　二分問題列聯(lián)表

真正類率(true positive rate)TPR=TP/(TP+FN)，表示用戶所喜歡的項(xiàng)目被推薦的概率.

假正類率(false positive rate)FPR=FP/(FP+TN)，表示用戶不喜歡項(xiàng)目被推薦的概率.還有一個(gè)真負(fù)類率(True Negative Rate，TNR)，也稱為specificity，計(jì)算公式為TNR=TN/(FP+TN)=1-FPR.在繪制ROC曲線時(shí)，將FPR和TPR分別定義為X和Y軸，ROC曲線下面的面積越大，預(yù)測(cè)的準(zhǔn)確率越高.

3.4　召回率(Recall)[8]

召回率用于反映待推薦項(xiàng)目被推薦的比率，計(jì)算公式為：

(14)

其中test表示測(cè)試數(shù)據(jù)集中的項(xiàng)目數(shù)量，top-N表示系統(tǒng)推薦給用戶的N個(gè)項(xiàng)目.Recall值越大被推薦的機(jī)率越大.

4　結(jié)論與展望

本文主要介紹了采用協(xié)同過濾算法進(jìn)行推薦時(shí)，常用的近鄰選擇算法和推薦算法及推薦算法的評(píng)估策略.協(xié)同過濾推薦算法主要存在數(shù)據(jù)稀疏性、冷啟動(dòng)和魯棒性問題還有在大數(shù)據(jù)環(huán)境下的推薦效率問題，針對(duì)這些問題一些研究者已提出了多種解決方法，最常見的是將其他領(lǐng)域的方法引入進(jìn)來，協(xié)同過濾的跨學(xué)科研究也得到了進(jìn)一步的發(fā)展.隨著互聯(lián)網(wǎng)上信息的急劇增長(zhǎng)，協(xié)同過濾推薦系統(tǒng)常需要處理海量的數(shù)據(jù)，如何存儲(chǔ)以及如何依據(jù)大量的數(shù)據(jù)計(jì)算出推薦結(jié)果，是協(xié)同過濾推薦面臨的一個(gè)挑戰(zhàn)，可以將協(xié)同過濾技術(shù)與云計(jì)算技術(shù)相結(jié)合，這樣可以使協(xié)同過濾推薦系統(tǒng)具有更高的容錯(cuò)能力，實(shí)時(shí)推薦能力和更強(qiáng)的并行計(jì)算能力.為向用戶提供個(gè)性化的商品或服務(wù)，協(xié)同過濾系統(tǒng)需了解用戶的個(gè)人信息，這就涉及到用戶的隱私保護(hù)問題.對(duì)協(xié)同過濾推薦的隱私保護(hù)問題的研究還比較少，還需進(jìn)一步深化.