基于雙重閾值近鄰查找的協(xié)同過濾算法

李 穎, 李永麗, 蔡觀洋

(1. 吉林師范大學 計算機學院, 吉林 四平 136000； 2. 東北師范大學 計算機科學與信息技術學院, 長春 130117；3. 吉林大學 計算機科學與技術學院, 長春 130012)

0 引 言

個性化推薦在當前互聯(lián)網(wǎng)服務行業(yè)的地位越來越重要, 它是解決信息過載的重要方式。協(xié)同過濾算法則是個性化推薦算法中應用最成功的一種技術, 該算法實現(xiàn)簡單, 部署方便, 在商業(yè)領域得到廣泛應用[1], 很多學者對其進行了深入全面地研究, 以克服該算法在應用過程中的不足。

協(xié)同過濾算法, 也叫社會過濾算法, 它充分利用“人”這個元素的社會屬性。社會中的每個人都有一些和自己興趣相似的個體, 本算法基于這樣的假設： 一個人可能更喜歡和他興趣相投的人所感興趣的項目。該算法是在系統(tǒng)的所有用戶行為數(shù)據(jù)上進行學習的, 不需要考慮項目的內(nèi)容信息。因此, 對非結(jié)構化的信息, 如電影、 音樂和視頻等, 可以產(chǎn)生不錯的推薦結(jié)果。但是, 該算法仍存在許多不足, 如由數(shù)據(jù)稀疏性導致的推薦精度不高, 用戶/項目冷啟動和推薦多樣性等問題[2]。其中推薦精度作為衡量個性化推薦算法的重要指標, 得到了學者的重視, 并提出了許多方式用以提高推薦精度。

George等[3]為了降低活躍用戶對推薦結(jié)果影響, 通過歸一化用戶評分項目組的出現(xiàn)頻率, 對用戶的每個評分項目都添加一個歸一化因子, 然后參與到用戶/項目間的相似性計算中。因此, 降低了那些被活躍用戶評價過的項目在推薦過程中的重要度。Yue等[4]提出了“細粒度”的相似性分析法, 期望挖掘那些興趣與目標用戶部分一致的用戶, 提高推薦精度。除了上述針對如何充分利用用戶項目評分矩陣信息外, 還有其他一些方式用以提高推薦精度, 如Sarwar等[5]提出的奇異值分解技術能降低稀疏評分矩陣的維數(shù), 提高項目或用戶間的相似性準確度, 從而提高推薦精度。

這些方法雖然都從協(xié)同過濾算法的基礎----項目/用戶間的相似性計算準確度提出了有效方法, 但都沒有考慮最終近鄰用戶組或近鄰項目組從候選集的篩選過程, 由于最終的推薦結(jié)果是以近鄰用戶組/項目組為計算依據(jù)的, 因此它們的質(zhì)量直接關系著推薦精度。筆者從近鄰用戶/項目組的篩選入手, 分析了近鄰用戶組與推薦精度間的關系, 提出了基于雙重閾值的近鄰查找方法, 并將此方法應用在基于用戶的協(xié)同過濾算法(UBCF: User Based Collaborative Filtering)和基于項目的協(xié)同過濾算法(IBCF: Item Based Collaborative Filtering), 通過離線實驗證明了該方法可有效提高推薦精度。

1 相關知識

1.1 協(xié)同過濾算法步驟

協(xié)同過濾算法是目前研究最熱的一種個性化推薦技術, 一般分為3個步驟： 用戶信息數(shù)據(jù)表示; 鄰居用戶組/項目組的查找; 生成推薦列表。下面以基于用戶的協(xié)同過濾為例說明每個步驟實現(xiàn)細節(jié)。

1) 用戶信息數(shù)據(jù)收集與表示。用U={u1,u2,…,um}表示用戶集合,I={i1,i2,…,in}表示系統(tǒng)中的項目集合, 其中系統(tǒng)中共有m個用戶,n個項目, 用矩陣Rm×n表示系統(tǒng)中所有的用戶對項目的評分信息[6], 矩陣中的元素Rui表示用戶u對項目i的評分信息。

2) 鄰居用戶/項目的查找。查找鄰居用戶組/項目組是協(xié)同過濾算法中最重要的一步, 其主要是用戶集合中找出與目標用戶u興趣最相似的k個用戶N={u1,u2,…,uk}, 使Ssim(u,u1,…,k)>Ssim(u,uk+1,…,m),Ssim(u,v)表示用戶u和用戶v的相似度。常用的相似性計算有3種： 余弦相似性, Pearson相關相似性和修正的余弦相似性[7,8]。

3) 生成推薦列表。根據(jù)第2步生成的鄰居集合, 可以依據(jù)鄰居的評分信息預測目標項目的評分信息, 推薦結(jié)果有兩種展示形式： 產(chǎn)生用戶的TopN推薦； 生成目標用戶的每個未評分項目的預測評分, 按從高到低的順序排列。

1.2 近鄰用戶評價指標

筆者提出了近鄰組相似度和參考近鄰比例兩個指標評估算法選出的近鄰組的質(zhì)量。

近鄰組相似度

(1)

其中N(u,m)表示用戶u在計算項目m的評分信息時近鄰用戶組, |N(u,m)|表示此近鄰用戶組的元素個數(shù), 若計算系統(tǒng)的近鄰用戶組相似度, 則將測試集中所有記錄的SNsim(u,m)相加再求平均值即可。

參考近鄰比例

(2)

其中K表示計算過程中輸入的近鄰個數(shù)。系統(tǒng)的整體參考近鄰比例為測試集中所有RNiebr(u,m)的平均值。

1.3 傳統(tǒng)算法存在的不足

傳統(tǒng)協(xié)同過濾算法在選擇近鄰用戶組時, 或者選擇全局最優(yōu)的K個用戶, 或者選擇那些既評價過目標項目又與目標用戶相似的K個用戶, 但由于數(shù)據(jù)的稀疏性導致這些用戶不能參與到預測評分的計算。因此, 如何充分利用現(xiàn)有用戶評分矩陣所提供的信息, 選擇合適的近鄰用戶組是協(xié)同過濾算法的關鍵。

2 算 法

2.1 雙重閾值近鄰查找策略

由1.3節(jié)的分析可知選擇合適的策略找出一些相似性較高的項目或用戶作為目標用戶的近鄰用戶組對系統(tǒng)性能的影響也非常重要, 如果選擇的近鄰用戶組并非與目標用戶相近, 則會直接影響推薦質(zhì)量?；赯hang等[9]提出的近鄰用戶選擇策略的啟示, 筆者提出了雙重閾值近鄰查找法(DT: Dual Threhold)。

采用雙重閾值近鄰查找法查找目標用戶或項目的K個近鄰的具體步驟如下：

1) 首先將目標用戶/項目與用戶集或項目集中所有其他用戶或項目的相似性從高到低排序。選擇前N個項目或用戶作為候選集C1；

2) 計算候選集C1中用戶和項目的平均相似度作為相似度閾值, 再以此閾值為基礎, 選擇相似性大于等于此閾值的用戶或項目添加到候選集C2中；

3) 從候選集C2中選擇對目標項目有評分信息的用戶, 或目標用戶對項目有評分信息的項目, 且最相似的K個元素添加到近鄰組C3中；

4) 如果近鄰組C3的長度小于K, 則從C2中優(yōu)先選擇相似度最高且未出現(xiàn)在C3中的元素添加到C3中。

2.2 雙重閾值近鄰查找策略分析

以基于用戶的協(xié)同過濾算法為例分析此近鄰查找方法的優(yōu)勢。設針對每個目標用戶, 需要查找k個近鄰用戶, 對目標項目評價過的用戶個數(shù)為r, 用戶集合的大小為M, 項目集合的大小為N。因為查找近鄰的過程就是掃描所有用戶集合的過程, 所以通過考察查找近鄰時需要查看用戶的個數(shù)為基礎比較算法的時間復雜度。以計算目標用戶U1對目標項目I1的運算為例, 雙重閾值近鄰算法中假設在查找相似度閾值時考察β×k個相似性最高的用戶, 只需目標用戶U1對應的鏈表行L1即可。此鏈表表示目標用戶與用戶集合中其他用戶間的相似性組成的節(jié)點鏈, 且鏈表已按相似性降序排序, 因此只需考察2βk個用戶即可。當選擇對目標項目已評分且與目標用戶U1最相似的k個用戶作為近鄰時(SR1: Similarity and Rating), 若仍舊按優(yōu)化方式存儲用戶間相似性, 由于對目標項目已評分的用戶隨機分布在鏈表L1中, 可假設r個用戶將鏈表中的用戶分成(r+1)份, 而每個用戶都是等概率分布在各個份中的, 所以每份中大概有(M-r)/(r+1)個用戶。當找到最相似的前k個且對目標項目有評分的用戶需要訪問大約k(M-r)/(r+1)個鏈表中的元素。此時若筆者提出的近鄰查找方法DT的性能要優(yōu)于上述策略SR1, 則需要滿足2βk

2.3 雙重閾值的基于用戶的協(xié)同過濾算法

為了測試此近鄰選擇策略的有效性, 將該方法應用于基于用戶的協(xié)同過濾算法中, 形成新的算法----基于雙重閾值的用戶協(xié)同過濾算法(DT-UBCF: Dual Threshold User-Based Collaborative Filtering), 以提高算法的推薦精度。

與1.1節(jié)中的協(xié)同過濾算法步驟類似, 只是筆者的算法利用了雙重閾值近鄰查找方法, 因此, 每個步驟的實現(xiàn)細節(jié)略有差異。

1) 近鄰用戶組選擇。采用2.2節(jié)中的雙重閾值近鄰查找策略； 用戶間的相似性計算采用性能較好的Pearson相關相似性計算[7]。Herlocker等[10,11]通過增加一個相關重要性權重因子降低共同評分信息少的用戶/項目間的相似性, 因此, 采用優(yōu)化后的相似性計算公式度量用戶間的關系。

用戶向量u和v之間的Pearson相關相似性為Ssim(u,v)′、 最終相似性為Ssim(u,v)

Ssim(u,v)=αSsim(u,v)′

(3)

其中|u|表示兩個用戶間的共同評分項目個數(shù),γ代表公共評分項目閾值, 是一個正整數(shù)或0。

2) 計算目標用戶對目標項目的預測評分。由于近鄰用戶組可能由與目標用戶相似性高且對目標項目有評分行為的用戶以及相似性最高但并沒有評價過目標項目的用戶兩部分用戶組成。因此, 計算預測評分時可通過設置一個參數(shù)μ調(diào)整這兩部分近鄰用戶對計算的貢獻度。由于第2部分近鄰用戶并沒有對目標項目進行評分, 因此采用該用戶的平均分取整, 并隨機加0或加1作為該用戶對目標項目的評分參與計算, 其公式如下

(4)

雙重閾值的基于用戶的協(xié)同過濾算法偽代碼：

算法名稱： DT-UBCF算法

輸入： 目標用戶userid, 目標項目itemid, 近鄰用戶個數(shù)neibnum, 共同評分項目閾值commRate, 計算相似性閾值的參考近鄰比例belta, 兩種近鄰用戶的貢獻比例ratio, 訓練集用戶—項目評分矩陣trainMatrix

輸出： 目標用戶對目標項目的預測得分predictRate

算法描述：

DTUBCF(userid, itemid, neibnum, commRate, belta, ratio, trainMatrix)//雙重閾值UBCF

//計算userid與其他用戶間的相似性

simUser ← GETSIMILARITY(userid, commRate, trainMatrix)

neighbors ← GETNEIGHBOR (simUser, belta, neibnum, itemid, trainM)

//計算目標用戶對目標項目的預測得分

rate ← GETPRERATE (userid, itemid, neighbors,ratio,trainM)

return rate

GETNEIGHBOR (simList, belta, neibnum, itemid, tMatrix)//查找目標用戶的鄰居

tmpList ←simList[0…belta*neibnum]

SsimThre ← AVERAGE(SsimT[tmpList])//相似性閾值

foreach cell in tmpList do

if len[neighbors_1]=neibnum then

exit

if simT[cell]≥simThre and tMatrix[user[cell]][itemid]≠0 then

INSERT(neighbors_1, cell)

if len[neighbors_1]

foreach cell in tmpList do

if len[neighbors_2]=neibnum-len[neighbor_1] then

exit

if cell not in neighbors and tMatrix[user[cell]][itemid]≠0 then

INSERT(neighbors_2, cell)

return (neighbors_1, neighbors_2)

由于基于項目的協(xié)同過濾算法與基于用戶的協(xié)同過濾算法類似, 只是考察的方向不同, IBCF同樣需要尋找目標項目的近鄰項目組, 也可通過將雙重閾值近鄰查找策略應用在IBCF中形成雙重閾值的基于項目的協(xié)同過濾算法(DT-IBCF: Dual Threshold Item-Based Collaborative Filtering), IBCF與UBCF算法步驟大體一致, 此處不做詳細介紹。

3 實 驗

3.1 實驗方法

筆者的研究重點是近鄰的選擇對算法推薦精度的影響, 因此, 實驗過程中, 主要測試采用不同的近鄰選擇方法時對基于用戶的協(xié)同過濾和基于項目的協(xié)同過濾算法精度的影響。協(xié)同過濾算法也要求用戶輸入一些參數(shù)信息, 因此實驗還需測試不同參數(shù)對算法性能的影響。

實驗采用5折交叉驗證方法, 將MovieLens數(shù)據(jù)集均勻隨機分成5份, 輪流將其中的4份作為訓練集, 1份作為測試集, 所以訓練集和測試集大約分別占所有評分信息的80%和20%。取5次實驗結(jié)果的平均值作為此算法的最終性能結(jié)果[12]。算法性能的評估可通過對預測分值與項目的真實分值做比較得到。

3.2 評估指標

筆者提出的算法是進行評分預測推薦的, 針對預測評分推薦的評估, 主要通過度量系統(tǒng)產(chǎn)生的預測分值與用戶對項目的真實評價分值之間的差額大小評判推薦系統(tǒng)的表現(xiàn), 差額越小, 說明推薦結(jié)果越準確; 反之, 則推薦性能越差。為了評估協(xié)同過濾算法的推薦精度, 學者提出了很多方法, 如MAE(Mean Absolute Error), MSE(Mean Squared Error), RMSE(Root Mean Squared Error)等, 而更多的研究者使用MAE作為度量標準[13], 實驗中也采用該方法評價算法的性能, 其計算如下

(4)

其中Rui是用戶u對項目i的評分,rui是推薦系統(tǒng)的預測評分信息,T代表測試集合。

3.3 實驗結(jié)果與分析

近鄰的選擇策略直接影響算法的推薦精度, 通過實驗比較以下4種近鄰選擇策略對算法的影響。

1) ST-1： 選擇全局相似性最靠前的k個用戶作為近鄰用戶；

2) ST-2： 選擇對目標項目有評分信息, 且相似性最高的k個用戶作為鄰居；

3) ST-3： 設定一個相似度閾值SsimT, 大于此閾值且對目標項目有評分信息的都作為近鄰參與計算；

4) ST-4： 取相似性最靠前的βk個用戶, 以他們的相似性均值作為相似性閾值, 然后取相似性大于相似性閾值, 且對目標項目有評分的用戶加入近鄰用戶組, 如果近鄰個數(shù)不足k個, 則選擇相似性最高的用戶作為補充, 而新補充的用戶對目標項目的評分為用戶評分均值整數(shù)部分。

圖1 不同近鄰選擇策略下算法的性能

以上4種策略對應不同的協(xié)同過濾算法, 由于ST-1,ST-2和ST-4都受參數(shù)k的影響, 因此, 實驗中比較了在不同k值下算法的性能。實驗中k的取值分別為10,20,30,40,80,β的取值在數(shù)據(jù)集movielens上為[10,20]效果最優(yōu), 因此, 選取10,SsimT值在本實驗中取0.45時效果最優(yōu), 實驗結(jié)果如圖1所示。

通過實驗可以看出, 近鄰選擇策略對算法性能的影響較大, 使用近鄰選擇策略ST-4, 算法的EMAE值最小, 即筆者提出的算法DT-UBCF的性能最好。這是由于此時算法通過相似性閾值, 去除了相關性不強的近鄰用戶對預測結(jié)果的影響, 同時為了保證有盡量多的近鄰參與計算, 又選擇了對目標項目沒有評分信息, 但與目標用戶關聯(lián)性較強的用戶參與計算, 為了更詳細地說明其中的變化, 表1給出了不同算法在性能最優(yōu)情況下參考近鄰比例和近鄰用戶組的平均相似度。

表1 不同算法的近鄰用戶組相似度(SNsim)和參考近鄰比例(RNeibr)

從表1可以看出, UBCF-2的SNsim值最低。這是由于此近鄰選擇策略選擇那些對目標項目有評分的用戶, 導致有些用戶與目標用戶相似性接近0, 或為負值, 從而拉動整體的平均相似度, 而其他3種策略都避免了此方法。從參考近鄰比例這個指標看, UBCF-1的值最低。雖然算法以全局最優(yōu)的用戶最為近鄰, 但這些近鄰并非都對目標項目有評分信息, DT-UBCF在考慮相似性的同時, 還考慮了近鄰用戶對目標項目的評分信息, 因此其各個指標都能達到一個不錯的值, 算法的最終性能較好。

基于項目的協(xié)同過濾算法思想與基于用戶的協(xié)同過濾相似, 因此, 只給出了DT-IBCF與傳統(tǒng)IBCF在不同k值下算法性能的比較, 與其他算法的對比實驗結(jié)果沒有列出。圖2為不同k值下IBCF算法推薦精度對比。從圖2中可以看出, 改進后的算法推薦精度當近鄰個數(shù)大于等于60時也有很大的提高。

圖2 不同k值下IBCF算法推薦精度對比

從圖2中推薦精度的趨勢也可以看出, 當近鄰個數(shù)大于100時, IBCF-1和IBCF-2算法的EMAE值趨于平緩狀態(tài), 因為滿足條件的近鄰數(shù)量是有限的, 即使要求的近鄰個數(shù)再多, 也不能從稀疏的用戶項目評分矩陣中找出滿足數(shù)量的近鄰。而DT-IBCF算法在近鄰個數(shù)較少的情況下, 算法推薦精度不如IBCF-2, 是由于在開始的相似度閾值篩選過程中, 把目標用戶有評分的項目但與目標項目相關度不算很強的項目排除在外了, 而引入了大量的與目標項目相關, 而目標用戶并沒有評分信息的項目, 增大了誤差, 從而導致算法的EMAE值過低。

4 結(jié) 語

筆者提出了近鄰組相似度和參考近鄰比例兩個指標, 用以評估協(xié)同過濾算法選出的近鄰用戶組或近鄰項目組的質(zhì)量, 通過這些指標從量化的角度揭示了傳統(tǒng)協(xié)同過濾算法的不足, 并提出了雙重閾值近鄰查找法, 以發(fā)掘與目標用戶或項目相關, 且能參與到最終預測評分計算的候選項目或用戶, 充分利用現(xiàn)有稀疏的用戶評分矩陣信息。并將此策略應用于基于近鄰的協(xié)同過濾算法中, 通過實驗分析, 可以看出, 該方法可有效提高推薦系統(tǒng)的推薦精度。對實際商業(yè)應用有一定參考價值。

參考文獻：

[1]GLODBCRG D, NICHOLS D, OKI B M, et al. Using Collaborative Filtering to Weave an Information Tapcstry [J]. Communication of the ACM, 1992, 35(12): 61-70.

[2]NADAV GOLBANDI, YEHUDA KOREN, RONNY LEMPEL. Adaptive Bootstrapping of Recommender Systems Using Decision Trees [C]∥Proceeding of the Forth ACM International Conference on Web Search and Data Mining. New York, USA: ACM, 2011: 595-604.

[3]GEORGE KARYPIS. Evaluation of Item-Based Top-N Recommendation Algorithms [C]∥CIKM’01: Proceedings of the Theth International Conference on Information and Knowledge Management. New York, USA: ACM, 2001: 247-254.

[4]YUE SHI, MARTHA LARSON, ALAN HANJALIC. Exploiting User Similarity Based on Rated-Item Pools for Imprrved User-Based Collaborative Filtering [C]∥RecSys’09: Proceedings of the third ACM Conference on Recommender Systems. New York, USA: ACM, 2009: 125-132.

[5]SARWAR B, KARYPIS G, KONSTAN J, et al. Application of Dimensionality Reduction in Recommender System: A Case Study [C]∥Proceeding of the ACM Web KDD Workshop on Web Mining for E Commerce. New York, USA: ACM, 2000: 82-90.

[6]PREM MELVILLE, RAYMOND J MOONEY, RAMADASS NAGARAJAN. Content-Boosted Collaborative Filtering for Improved Recommendations [C]∥Proceedings of the Eighteenth National Conference on Artificial Intelligence(AAAI-2002). Edmonton, Canada: American Association for Artificial Intelligence, 2002: 187-192.

[7]KOHRS A, MERIALDO B. Creating User-Adapted Websites by the Use of Collaborative Filtering [J]. Interacting with Computers, 2001, 13(6): 695-716.

[8]SARWAR B M. Sparsity, Scalability and Distribution in Recommender System [D]. Minncapolis, MN: University of Minnesota, 2001.

[9]ZHANG Ji-yong, PEARL PU. A Recursive Prediction Algorithm for Collaborative Filtering Recommender Systems [C]∥Proceedings of ACM Conference on Recommender Systems. [S.l.]: ACM, 2007: 57-64.

[10]HERLOCKER J, KONSTAN J A, RIEDL J. An Empirical Analysis of Design Choices in Neigborhood-Based Collaborative Filtering Algorithms [J]. Information Retrieval, 2002, 5(4): 287-310.

[11]HERLOCKER J L, KONSTAN J A, BORCHERS A, et al. An Algorithmic Framework for Performing Collaborative Filtering [C]∥Proceding of ACM SIGIR’99. [S.l.]: ACM, 1999: 230-237.

[12]SARWAR B, KARYPIS G, KONSTAN J, et al. Item-Based Collaborative Filtering Recommendation Algorithms [C]∥Proceeding 10thInt, Conference on World Wide Web. New York, USA: ACM, 2001: 285-295.

[13]SYMENOIDIS P, NANOPOULOS A, PAPADOPOULOS A N, et al. Collaborative Filtering: Fallacies and Insights in Measuring Similarity [C]∥Proceddings of the 10th PKDD Workshop on Web Mining(WEBMine 2006). Berlin, Germany: [s.n.], 2006: 56-67.