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

江南　羅軍

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

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

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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ā)展，信息分享與獲取變得更加容易，豐富多彩的信息改變了人們的生活方式。然而，海量信息的蜂擁而至，也帶來(lái)數(shù)據(jù)和信息的指數(shù)級(jí)增長(zhǎng)，人們漸漸迷失在信息的海洋中。搜索引擎的出現(xiàn)緩解了信息過(guò)載問(wèn)題，但是需要用戶有明確的需求，如何智能的挖掘用戶潛在的個(gè)性化信息進(jìn)而進(jìn)行信息過(guò)濾成為研究的熱點(diǎn)，推薦系統(tǒng)由此而生。

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

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

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

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

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

⑴ 標(biāo)準(zhǔn)的余弦相似性

2 改進(jìn)相似度計(jì)算方法的協(xié)同過(guò)濾算法

2.1 傳統(tǒng)相似度計(jì)算存在的問(wèn)題

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

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

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

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

2.2 可信度的計(jì)算

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

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

2.4 最近鄰的選擇

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

輸入：用戶評(píng)分矩陣Rm×n，項(xiàng)目類別矩陣Ts×n，K，用戶參評(píng)矩陣Xm×n。

輸出：最近鄰Neighbor。

步驟一：可信相似度Dsim的計(jì)算

對(duì)Rm×n中的目標(biāo)項(xiàng)目i：

⑴ 依次從Rm×n中選擇和i不同的項(xiàng)目j。

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

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

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

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

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

對(duì)Rm×n中的每一個(gè)項(xiàng)目i：

從Dsim中，選擇最相似的K個(gè)項(xiàng)目作為項(xiàng)目i的最近鄰Neighbor。

2.5 評(píng)分預(yù)測(cè)

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

3.3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

參考文獻(xiàn)：

[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é)同過(guò)濾推薦算法[J].計(jì)算機(jī)研究與發(fā)展，2007.44（2）：296-301

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

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

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

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

[7] 彭石，周志彬，王國(guó)軍.基于評(píng)分矩陣預(yù)填充的協(xié)同過(guò)濾算法[J].計(jì)算機(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