基于可信相似度的協(xié)同過濾算法

江南　羅軍

摘 要： 傳統(tǒng)協(xié)同過濾算法在計算相似度的時候，未考慮數(shù)據(jù)稀疏性以及項目類型相似程度，從而影響推薦質(zhì)量。為了提高推薦精度，提出一種基于可信相似度的協(xié)同過濾算法。首先計算項目類型的相似程度與共同評分用戶數(shù)和所有評分用戶數(shù)之間的比例，然后根據(jù)類型相似程度和共同評分項的比例進行有機結(jié)合，計算相似可信度，形成合理的項目可信相似度。實驗結(jié)果表明，該算法能夠有效的提高推薦質(zhì)量。

關(guān)鍵詞： 推薦系統(tǒng)； 協(xié)同過濾； 相似度； 可信度

中圖分類號：TP301 文獻標志碼：A 文章編號：1006-8228（2015）04-23-04

Abstract： Traditional collaborative filtering algorithms do not consider the sparsity of the data and the similarity of the item's type. As a result， the systems may not recommend satisfactory items. To improve the recommendation precision， this paper proposes an algorithm based on the trustworthiness of similarity. First， it calculates similarity of item's type and the ratio between common rating user and all user that rated. Then， creating a reasonable item similarity based on the trustworthiness which dynamically combined by the type similarity and the ratio， and finally realize user rating recommendation. The experiment results show that the proposed algorithm can efficiently improve the recommendation quality.

Key words： recommendation system； collaborative filtering； similarity； trustworthiness

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，信息分享與獲取變得更加容易，豐富多彩的信息改變了人們的生活方式。然而，海量信息的蜂擁而至，也帶來數(shù)據(jù)和信息的指數(shù)級增長，人們漸漸迷失在信息的海洋中。搜索引擎的出現(xiàn)緩解了信息過載問題，但是需要用戶有明確的需求，如何智能的挖掘用戶潛在的個性化信息進而進行信息過濾成為研究的熱點，推薦系統(tǒng)由此而生。

推薦系統(tǒng)建立在信息檢索和信息過濾的基礎(chǔ)之上，是個性化推薦的重要實現(xiàn)形式。推薦算法可以分為基于內(nèi)容的算法、協(xié)同過濾算法和基于模型的算法。協(xié)同過濾推薦算法已經(jīng)成為迄今為止應(yīng)用最成功的個性化推薦技術(shù)之一[1]。其基本思想是相似的用戶之間具有相似的興趣愛好，只要找到目標用戶的鄰居用戶，就可以通過鄰居用戶對目標用戶的偏好進行預(yù)測。

經(jīng)過20多年的發(fā)展，協(xié)同過濾推薦技術(shù)已經(jīng)被廣泛使用，進入我們的日常生活，帶來了巨大的商業(yè)和社會價值。然而，隨著應(yīng)用范圍的擴大和信息量的不斷增大，協(xié)同過濾算法的一些弊端開始顯現(xiàn)，如冷啟動問題、稀疏性問題、可擴展性問題、推薦精度低等，為此學(xué)者進行了廣泛而深入的研究。文獻[2]通過引入基于時間的數(shù)據(jù)權(quán)重和基于資源相似度的數(shù)據(jù)權(quán)重，使得推薦系統(tǒng)能夠在一定程度上反映用戶的興趣變化。文獻[3]使用正則化約束來防止矩陣分解模型的過度擬合，并通過迭代最小二乘法來訓(xùn)練分解模型，改進后的算法在可擴展性和抗稀疏性方面都取得了一定的效果。文獻[4]提出一種基于情景的協(xié)同過濾推薦算法，通過引入項目情景模式相似度提高了協(xié)同過濾算法的推薦質(zhì)量。文獻[5]提出一種新的協(xié)同過濾評分矩陣的特征指標“資源關(guān)系密度”，進而提出一種虛擬用戶填充算法，提高了推薦精度和覆蓋率。針對冷啟動問題，文獻[6]運用基于內(nèi)容預(yù)測的方法預(yù)測缺失數(shù)據(jù)，然后使用協(xié)同過濾算法進行推薦。

本文的研究建立在基于項目的協(xié)同過濾算法上。傳統(tǒng)基于項目的協(xié)同過濾算法僅僅基于評分相似度來衡量項目之間的相似程度，而忽略了相似度計算值的可信程度，沒有考慮到目標項目與其最近鄰集合中項目的相似性以及共同評分項的個數(shù)對相似度計算的影響。針對這個問題，本文提出了基于可信相似度的協(xié)同過濾算法，在計算相似度的時候，綜合考慮評分可信度以及項目類型可信度，計算可信相似度，以此來提高預(yù)測的精度。

1 傳統(tǒng)相似性度量方法

評分相似度是傳統(tǒng)協(xié)同過濾算法用來衡量項目之間的相似程度的方法。余弦相似度，Pearson相關(guān)相似度和修正的余弦相似度是最為常用的計算方法。

⑴ 標準的余弦相似性

2 改進相似度計算方法的協(xié)同過濾算法

2.1 傳統(tǒng)相似度計算存在的問題

傳統(tǒng)的相似度計算方法建立在兩個項目的共同評分數(shù)據(jù)上，而忽略了用戶項目評分矩陣R的極度稀疏性以及項目類型的相關(guān)性，這會導(dǎo)致以下問題。

⑴ 傳統(tǒng)的相似性計算方法未考慮到項目類型的相似程度對項目相似性的影響。這會導(dǎo)致對于某一類型的項目，其最近鄰可能是很多各不相同的項目類型的集合。

例如計算用戶U（i）對恐怖片Ij的預(yù)測評分值，使用傳統(tǒng)的計算方法得到的電影Ij的最近鄰集合Pi，j有可能為Pi，j={喜劇片、愛情片、戰(zhàn)爭片、戰(zhàn)爭片、兒童片}。顯然，由于用戶對不同電影的喜好程度是不同的，僅憑借電影的評分，而忽略電影的類型相似信息，來計算電影之間的相似性，偏離了實際，相似度的計算結(jié)果就不夠可信。較好的方法是能夠找到和恐怖片類型最相似，且其與Ij的評分相似度又比較高的電影作為最近鄰計算預(yù)測評分。最近鄰中電影的類型越相似，其計算出來的相似度就越可信，預(yù)測評分的準確度也就越高。

⑵ 傳統(tǒng)的相似度的計算依賴于對項目進行共同評分的用戶數(shù)目。然而，在實際的推薦系統(tǒng)中，用戶的評分數(shù)據(jù)往往是極端稀疏的，共同評分的用戶數(shù)量很少。例如電影i和電影j只有兩個用戶進行了評分，而且這兩個用戶的評分又非常接近，那么用傳統(tǒng)方法計算出來的相似度就很高，顯然這和實際不相符，相似度的計算值不夠可信。相反，共同評分的用戶數(shù)量越多，那么相似度的可信度就越高，就越能夠反應(yīng)用戶的真實興趣偏好。

2.2 可信度的計算

基于以上分析，本文提出一種新的相似性計算方法，通過引入相似可信度來動態(tài)調(diào)節(jié)相似度的計算，以改進傳統(tǒng)相似性計算存在的問題。

針對問題⑴，如果我們在計算項目相似度的時候，將項目類型對相似度影響的大小作為項目相似性可信程度的一個度量因子，動態(tài)地調(diào)節(jié)傳統(tǒng)相似性計算的結(jié)果，那么可以使相似性的計算值更加趨近于實際。因此，本文提出，在計算項目相似度時，將項目類型的相似程度作為項目相似性的一個度量因子，我們稱之為項目類型可信度。

2.4 最近鄰的選擇

目標最近鄰的選擇，是協(xié)同過濾算法最重要的一步。本文根據(jù)式（12）計算項目之間的可信相似度，得出可信相似度矩陣Dsim，使用K近鄰算法從相似性矩陣中找出可信相似度值最高的K個項目作為目標項目的最近鄰Neighbor。算法如下：

輸入：用戶評分矩陣Rm×n，項目類別矩陣Ts×n，K，用戶參評矩陣Xm×n。

輸出：最近鄰Neighbor。

步驟一：可信相似度Dsim的計算

對Rm×n中的目標項目i：

⑴ 依次從Rm×n中選擇和i不同的項目j。

⑵ 根據(jù)式⑵計算項目i和項目j的Pearson相似度。

⑶ 根據(jù)式（11）計算項目i和項目j的可信度。

⑷ 利用公式（12）計算項目i和項目j的可信相似度，并更新Dsim的值。

⑸ 若Dsim計算全部完成，則執(zhí)行步驟二，若Dsim未完成計算，回到第1步。

步驟二：生成最近鄰集合Neighbor

對Rm×n中的每一個項目i：

從Dsim中，選擇最相似的K個項目作為項目i的最近鄰Neighbor。

2.5 評分預(yù)測

3 實驗與分析

3.1 實驗數(shù)據(jù)

MovieLens[8]是明尼蘇達大學(xué)Grouplens工作組于1997年創(chuàng)建的一個影片推薦系統(tǒng)，它通過收集和分析用戶評分和用戶對電影的喜好數(shù)據(jù)，形成推薦。本文選取公開的MovieLens數(shù)據(jù)集作為實驗數(shù)據(jù)，該數(shù)據(jù)由10萬條評分數(shù)據(jù)組成，評分數(shù)據(jù)是由943個用戶對1682個電影項目的評分組成的，每個用戶對至少20部電影進行了評分，評分的范圍為1-5。評分越高表示用戶的興趣度越高。每部電影都被分為18個電影類別中的一類或者幾類。

本文實驗將10萬條數(shù)據(jù)按照8：2的比例進行劃分，其中訓(xùn)練集占80%（100000×80%=80000條數(shù)據(jù)），測試集占20%（100000×20%=20000條數(shù)據(jù)）。實現(xiàn)語言采用Python。

3.2 評價標準

推薦系統(tǒng)的預(yù)測評分值與用戶的實際評分值越接近，其推薦質(zhì)量就越高。MAE（Mean Absolute Error）[9]是一種計算所有單個觀測值與算術(shù)平均值偏差的絕對值的平均值的方法。平均絕對誤差能較好地反映預(yù)測值與實際值誤差的真實情況。MAE的定義如式（14），通過累計計算實際的用戶評分與預(yù)測的用戶評分的偏差的平均值來度量預(yù)測的準確性，MAE值越小，表明算法越精確。

3.3 實驗結(jié)果

對于項目類型可信度的計算，需要先確定項目的屬性矩陣T。MovieLens數(shù)據(jù)集中的電影共有18種特征屬性，每部電影都可以同時具有一個或者多個屬性，實驗中，使用這些屬性構(gòu)造電影的屬性矩陣T。對于評分可信度的計算，我們使用式（9）根據(jù)用戶項目評分矩陣R構(gòu)造用戶參評矩陣X。

實驗中，不斷改變項目鄰居個數(shù)K的數(shù)目，使用可信相似度來度量項目間的相似性，以傳統(tǒng)的基于項目的協(xié)同過濾算法CF作為基準參考方法，對基于可信相似度的協(xié)同過濾算法MSCF進行了實驗，驗證優(yōu)化效果。實驗結(jié)果如圖1所示。

可以看出，一開始隨著最近鄰數(shù)目的增加，兩種相似度算法的MAE值都呈現(xiàn)下降的趨勢，并且隨著近鄰數(shù)量的不斷增大而趨于平穩(wěn)。在最近鄰數(shù)量相同的時候，MSCF的實驗效果好于CF的實驗效果。這是因為傳統(tǒng)相似性計算方法未考慮項目類型的相似性和共同評分用戶數(shù)量對相似性計算結(jié)果的影響，導(dǎo)致求得的最近鄰可能不符合實際，從而影響了推薦質(zhì)量。而改進的基于可信相似度的算法MSCF則綜合考慮了兩者對相似度計算的影響，因而具有較小的平均絕對偏差MAE。

實驗證明，本文提出的基于可信相似度的協(xié)同過濾算法的推薦效果要優(yōu)于傳統(tǒng)的協(xié)同過濾算法。

4 結(jié)束語

在傳統(tǒng)的基于項目的協(xié)同過濾算法中，項目間相似性計算的精確度是影響推薦質(zhì)量的關(guān)鍵因素。實際應(yīng)用中，數(shù)據(jù)的稀疏性對傳統(tǒng)的協(xié)同過濾算法產(chǎn)生了很大的影響。同時，最近鄰集合中項目的類型的不相似性也對推薦系統(tǒng)的推薦精度產(chǎn)生了消極的影響。本文針對傳統(tǒng)相似度計算的問題，提出了一種改進的相似性度量方法，從項目類型的相似性和共同評分的用戶數(shù)兩個方面考慮，計算可信相似度，并將改進的算法在真實數(shù)據(jù)集上進行了實驗。實驗的結(jié)果表明，改進的方法有效地提高了推薦質(zhì)量。

參考文獻：

[1] Sarvar B. Karypis G， Konstan J， et al. Item-based Collaborativefiltering recommendation algorithms[C]. Proceedings of the 10th International World Wild Web Conference. New York，2001：285-295

[2] 邢春曉，高鳳榮，思南等.適應(yīng)用戶興趣變化的協(xié)同過濾推薦算法[J].計算機研究與發(fā)展，2007.44（2）：296-301

[3] 李改，李磊.基于矩陣分解的協(xié)同過濾算法[J].計算機工程與應(yīng)用，2011.47（30）：4-7

[4] 李薈，謝強，丁秋林.一種基于情景的協(xié)同過濾推薦算法[J].計算機技術(shù)與發(fā)展，2014.24（10）：42-46

[5] 董麗，邢春曉，王克宏.協(xié)作過濾稀疏性算法[J].清華大學(xué)學(xué)報（自然科學(xué)版），2009.49（10）：154-157

[6] 郭艷紅，鄧貴仕.協(xié)同過濾系統(tǒng)項目冷啟動的混合推薦算法[J].計算機工程，2008.34（23）：11-13

[7] 彭石，周志彬，王國軍.基于評分矩陣預(yù)填充的協(xié)同過濾算法[J].計算機工程，2013.1（39）：175-178

[8] GroupLens lab at the University of Minnesota. MovieLens Dataset.Available at： http：//www.grouplens.org/node/12.

[9] B Jeong， J Lee， H Cho. Improving memory-based collaborativefiltering via similarity updating and prediction modulation[J].Information Sciences，2010.180（5）：602-612