江南　羅軍

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

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

中圖分類號：TP301 文獻(xiàn)標(biāo)志碼：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)緩解了信息過載問題，但是需要用戶有明確的需求，如何智能的挖掘用戶潛在的個(gè)性化信息進(jìn)而進(jìn)行信息過濾成為研究的熱點(diǎn)，推薦系統(tǒng)由此而生。

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

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

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

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

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

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

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

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

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

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

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

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

2.2 可信度的計(jì)算

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

針對問題⑴，如果我們在計(jì)算項(xiàng)目相似度的時(shí)候，將項(xiàng)目類型對相似度影響的大小作為項(xiàng)目相似性可信程度的一個(gè)度量因子，動態(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é)同過濾算法最重要的一步。本文根據(jù)式（12）計(jì)算項(xiàng)目之間的可信相似度，得出可信相似度矩陣Dsim，使用K近鄰算法從相似性矩陣中找出可信相似度值最高的K個(gè)項(xiàng)目作為目標(biāo)項(xiàng)目的最近鄰Neighbor。算法如下：

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

輸出：最近鄰Neighbor。

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

對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

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

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

2.5 評分預(yù)測

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

在傳統(tǒng)的基于項(xiàng)目的協(xié)同過濾算法中，項(xiàng)目間相似性計(jì)算的精確度是影響推薦質(zhì)量的關(guān)鍵因素。實(shí)際應(yīng)用中，數(shù)據(jù)的稀疏性對傳統(tǒng)的協(xié)同過濾算法產(chǎn)生了很大的影響。同時(shí)，最近鄰集合中項(xiàng)目的類型的不相似性也對推薦系統(tǒng)的推薦精度產(chǎn)生了消極的影響。本文針對傳統(tǒng)相似度計(jì)算的問題，提出了一種改進(jìn)的相似性度量方法，從項(xià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é)同過濾推薦算法[J].計(jì)算機(jī)研究與發(fā)展，2007.44（2）：296-301

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

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

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

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

[7] 彭石，周志彬，王國軍.基于評分矩陣預(yù)填充的協(xié)同過濾算法[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