摘 要：在協(xié)同過(guò)濾算法研究基礎(chǔ)上，通過(guò)壓縮稀疏矩陣的方式，綜合考慮用戶之間的關(guān)聯(lián)性和項(xiàng)目之間的關(guān)聯(lián)性，提出了一種混合協(xié)同過(guò)濾個(gè)性化推薦算法。通過(guò)在Bookcrossing數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，在矩陣規(guī)模較大并且稀疏的情況下，本算法比傳統(tǒng)的基于用戶和項(xiàng)目的協(xié)同過(guò)濾算法更有效的提高預(yù)測(cè)精度和覆蓋率。

關(guān)鍵詞：混合協(xié)同過(guò)濾；個(gè)性化；稀疏矩陣

中圖分類(lèi)號(hào)：TP301.6

在個(gè)性化系統(tǒng)面世前，利用用戶行為數(shù)據(jù)的許多應(yīng)用已經(jīng)在網(wǎng)絡(luò)上非常流行，其中最經(jīng)典的就是書(shū)籍資料，音樂(lè)電影等排行榜或推薦榜。在個(gè)性化推薦算法中，利用用戶的行為進(jìn)行分析是一個(gè)比較重要的方面，而平常學(xué)術(shù)界將其稱(chēng)為協(xié)同過(guò)濾算法。學(xué)術(shù)界對(duì)該算法進(jìn)行了詳細(xì)的研究，并提出了較多的方法，例如基于鄰域的算法?[1]，隱語(yǔ)義模型?[2]，基于圖的隨機(jī)游走算法?[3]。其中，基于鄰域的算法?得到最廣泛應(yīng)用，并且研究最多的算法，主要包括基于用戶的協(xié)同過(guò)濾算法和基于項(xiàng)目的協(xié)同過(guò)濾算法。

1 基于鄰域的算法

基于鄰域的算法是推薦算法中最重要的算法之一，它在學(xué)術(shù)界及業(yè)界都得到了廣泛的應(yīng)用。該算法主要包括基于用戶的協(xié)同過(guò)濾算法和基于項(xiàng)目的協(xié)同過(guò)濾算法。下面幾節(jié)將對(duì)這兩種算法進(jìn)行基本的介紹，并對(duì)比他們的優(yōu)缺點(diǎn)提出改進(jìn)方案。

1.1 基于用戶的協(xié)同過(guò)濾算法

基于用戶的協(xié)同過(guò)濾算法?[4]包括下面幾個(gè)步驟。

（1）數(shù)據(jù)的表示。在協(xié)同過(guò)濾推薦系統(tǒng)中，可以將輸入數(shù)據(jù)表示為m×n的用戶-項(xiàng)目評(píng)分矩陣R，其中m是用戶數(shù)，n為項(xiàng)目數(shù)，rij是第i個(gè)用戶對(duì)敵j個(gè)項(xiàng)目的評(píng)分。評(píng)分的值與項(xiàng)目的內(nèi)容有關(guān)。

（2）找到與目標(biāo)用戶相似的用戶的集合。本文通過(guò)余弦相似度計(jì)算這兩個(gè)用戶之間的相似度。

（3）在用戶相似度集合中找到跟目標(biāo)用戶相似的用戶，并將該用戶喜歡的但目標(biāo)用戶沒(méi)用喜歡過(guò)的物品或項(xiàng)目推薦給當(dāng)前用戶。算法用下面的公式來(lái)計(jì)算用戶u對(duì)項(xiàng)目i的感興趣程度：

（1）

在公式（1）中的S（u，K）表示跟用戶u最相思的前K個(gè)用戶的集合，N（i）表示對(duì)物品i有過(guò)行為的用戶的集合，rvi表示用戶v對(duì)物品i的感興趣程度，即用戶v對(duì)物品i的評(píng)分。

1.2 基于項(xiàng)目的協(xié)同過(guò)濾算法

隨著用戶數(shù)目的日漸增長(zhǎng)，用戶間興趣相似度的計(jì)算越來(lái)越困難，著名的電子商務(wù)公司亞馬遜提出了基于項(xiàng)目的協(xié)同過(guò)濾算法?[5]。該算法分為下面幾個(gè)步驟。

（1）物品之間相似度的計(jì)算。計(jì)算物品之間相似度的公式如下所示，其中U（i）表示喜歡物品i的用戶集合：

（2）

但是上面的公式存在一個(gè)問(wèn)題，如果物品j很流行，那么wij會(huì)無(wú)限接近1，這時(shí)流行物品會(huì)對(duì)推薦的結(jié)果造成一定的影響，為了避免出現(xiàn)上面的狀況，可用下面的公式：

（3）

（2）根據(jù)計(jì)算出的物品之間的相似度，可用下面的公式?[1]計(jì)算用戶u對(duì)物品j的感興趣程度：

（4）

在公式（4）中，N（u）表示用戶u喜歡的物品集合，S（j，K）表示跟物品j相似的前K個(gè)物品的集合，wji表示物品i和物品j之間的相似度，rui表示用戶u對(duì)物品i的喜歡程度，即用戶u對(duì)物品i的評(píng)分。

2 矩陣壓縮下兩種算法的結(jié)合

2.1 兩種算法的優(yōu)勢(shì)與不足

文獻(xiàn)[6]提到，基于用戶的協(xié)同過(guò)濾算法通過(guò)計(jì)算用戶之間的相似性從而提供個(gè)性化程度較高的推薦，但是推薦精度比基于物品的協(xié)同過(guò)濾算法要稍低，并且在用戶群較大的情況下，用戶間興趣相似度的計(jì)算將越來(lái)越困難。而基于物品的協(xié)同過(guò)濾算法通過(guò)計(jì)算物品之間的相似性從而實(shí)現(xiàn)更精確的推薦，但是卻削弱了用戶的個(gè)性化程度，從而無(wú)法提供一個(gè)個(gè)性化程度較高的推薦。

因此本文通過(guò)壓縮稀疏矩陣的方式，將兩種算法結(jié)合在一起，此算法不僅考慮到了用戶之間的關(guān)聯(lián)性，而且考慮到了項(xiàng)目之間的關(guān)聯(lián)性，使得推薦精度得到了相應(yīng)的提高。

2.2 改進(jìn)的推薦算法思路

改進(jìn)的推薦算法主要有以下幾個(gè)思路。

（1）稀疏矩陣的壓縮。一般推薦算法的輸入都為m×n的用戶-項(xiàng)目評(píng)分矩陣，但是在大多數(shù)的商務(wù)系統(tǒng)中，該矩陣是稀疏并且巨大的，因此本文通過(guò)對(duì)用戶進(jìn)行分類(lèi)，即對(duì)用戶集合進(jìn)行壓縮，從而使得算法的輸入矩陣進(jìn)行了壓縮。

（2）利用第一步得到的壓縮矩陣，對(duì)當(dāng)前用戶進(jìn)行推薦。在此過(guò)程中，需要在分類(lèi)的用戶集合中找到跟當(dāng)前用戶興趣度相似的集合，然后在所有的用戶喜歡的所有的物品集合中，計(jì)算物品兩兩之間的相似度，最后得到當(dāng)前用戶的推薦結(jié)果。本文利用公式（3）計(jì)算物品之間的相似度時(shí)，為了減少耗時(shí)，可用下面的思路進(jìn)行：首先對(duì)每個(gè)用戶建立一個(gè)他所喜歡的物品列表。矩陣C為n×n階矩陣，然后對(duì)于每個(gè)用戶，將倒排表中的物品兩兩在矩陣C中加1，最后得到物品之間的余弦相似度矩陣?[1]。下圖為利用該思路計(jì)算物品相似度的例子：

圖1 計(jì)算物品相似度的例子

2.3 用戶活躍度對(duì)算法的影響

用戶活躍度指的是某些用戶為了某些目的在某一商務(wù)系統(tǒng)中購(gòu)買(mǎi)或喜歡了很多書(shū)籍，那么該用戶對(duì)于他所購(gòu)買(mǎi)的書(shū)籍兩兩之間的相似度的貢獻(xiàn)將會(huì)影響到最后的推薦結(jié)果，此時(shí)，該用戶就屬于噪聲用戶。

文獻(xiàn)?[7]提出了一個(gè)稱(chēng)為IUF（Inverse User Frequence）的參數(shù)，該參數(shù)為用戶活躍度對(duì)數(shù)的倒數(shù)，為了降低噪聲用戶對(duì)推薦結(jié)果的影響，文獻(xiàn)[7]提出應(yīng)增加IUF參數(shù)來(lái)修正物品相似度的計(jì)算公式：

（5）

從公式（5）可以看出，用戶u喜歡的物品集合越大，即用戶越活躍，則其對(duì)用戶相似度造成的影響越小。

2.4 混合協(xié)同過(guò)濾算法流程

將改進(jìn)的推薦算法的思路進(jìn)行進(jìn)一步的擴(kuò)展，并且考慮到用戶活躍度對(duì)算法的影響，從而得到混合協(xié)同過(guò)濾算法的流程。

（1）建立用戶-項(xiàng)目評(píng)分矩陣。傳統(tǒng)協(xié)同過(guò)濾算法采用m×n的用戶-項(xiàng)目評(píng)分矩陣R用來(lái)表示輸入數(shù)據(jù)，其中rij是第i個(gè)用戶對(duì)第j個(gè)項(xiàng)目的評(píng)分。

（2）得到用戶的分類(lèi)集合。利用用戶余弦相似度公式計(jì)算兩兩之間的相似度，將最為相似的前N（本文取N=1000）個(gè)用戶分為一類(lèi)，得到用戶分類(lèi)集合。

（3）得到壓縮用戶-項(xiàng)目評(píng)分矩陣R1。和當(dāng)前用戶最相似的用戶集合作為輸入數(shù)據(jù)的用戶，將這部分用戶喜歡的項(xiàng)目集合作為輸入數(shù)據(jù)的項(xiàng)目，從而得到用戶-項(xiàng)目評(píng)分矩陣R1。

（4）將R1作為基于項(xiàng)目的協(xié)同過(guò)濾算法的輸入矩陣，考慮到用戶活躍度對(duì)算法的影響，用公式（5）計(jì)算物品相似度，并利用倒排表的思想簡(jiǎn)化計(jì)算。

（5）利用公式（4）計(jì)算當(dāng)前用戶對(duì)于物品的感興趣程度。

3 實(shí)驗(yàn)結(jié)果及分析

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

本文采用了Book-Crossing數(shù)據(jù)集，該數(shù)據(jù)集是由Cai-Nicolas Ziegler使用爬蟲(chóng)程序在2004年從BookCrossing圖書(shū)社區(qū)上采集的，其中包括278858個(gè)用戶對(duì)271397本圖書(shū)進(jìn)行的評(píng)分，評(píng)分值為1-10，數(shù)值越高，表明用戶對(duì)圖書(shū)的偏愛(ài)度越高。本數(shù)據(jù)集沒(méi)有經(jīng)過(guò)任何的人為去除噪聲數(shù)據(jù)，因此推薦結(jié)果更加符合實(shí)際情況。

在對(duì)推薦算法進(jìn)行驗(yàn)證時(shí)，選取了50000條評(píng)分?jǐn)?shù)據(jù)，并將評(píng)分?jǐn)?shù)據(jù)集隨機(jī)分成8份，7份即43750條數(shù)據(jù)作為訓(xùn)練集，剩下的一份即6250條數(shù)據(jù)作為測(cè)試集。

3.2 評(píng)測(cè)指標(biāo)

本文應(yīng)用了召回率/準(zhǔn)確率-精度評(píng)測(cè)方法。文獻(xiàn)?[6]提到，現(xiàn)在大家關(guān)注的問(wèn)題大多是精度方面的問(wèn)題，現(xiàn)在評(píng)測(cè)一個(gè)推薦算法的性能，除了精度外，新穎性、多樣性、覆蓋率等更多指標(biāo)越來(lái)越受到重視。

（1）準(zhǔn)確率/召回率。對(duì)用戶u推薦了N個(gè)物品，記為R（u），令用戶u在測(cè)試集上喜歡的物品集合為T(mén)（u），則準(zhǔn)確率和召回率的公式分別如下所示：

（6）

（7）

（2）覆蓋率。該評(píng)測(cè)指標(biāo)跟用戶活躍度的影響有直接聯(lián)系，它反映了算法是否將所有物品至少推薦給了一個(gè)用戶，即給用戶推薦的是否都是流行用戶喜歡的物品。下面的公式來(lái)定義覆蓋率：

（8）

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

本實(shí)驗(yàn)算法的編程語(yǔ)言為python，將三個(gè)算法進(jìn)行了對(duì)比，改進(jìn)的協(xié)同過(guò)濾算法跟當(dāng)前用戶最相似的用戶集合的大小N=1000，并且將三者之間的覆蓋率進(jìn)行了比較，基于項(xiàng)目的和改進(jìn)的協(xié)同過(guò)濾算法的相似度計(jì)算公式應(yīng)用了公式（5），最近鄰居個(gè)數(shù)K依次為5，10，15，20，25，30，35，實(shí)驗(yàn)結(jié)果表明，改進(jìn)的用戶分類(lèi)下兩個(gè)算法的結(jié)合在提高了用戶個(gè)性化程度的同時(shí)，比傳統(tǒng)的兩個(gè)算法的精確度要高，同時(shí)，預(yù)測(cè)的質(zhì)量也隨著最近鄰居K的值而變化?；谟脩舻膮f(xié)同過(guò)濾算法召回率和精確率在K=20達(dá)到最大值，后面沒(méi)有改變。而且在K=30時(shí)，三個(gè)算法的精確率和召回率都達(dá)到了最大值，并且改進(jìn)的推薦算法得到推薦結(jié)果最精確。同時(shí)，在應(yīng)用了文獻(xiàn)?[7]提出的IUF參數(shù)后，覆蓋率也有了相應(yīng)的改善，對(duì)比圖如下所示：

圖2 召回率對(duì)比圖

圖3 精確率對(duì)比圖

圖4 覆蓋率對(duì)比圖

兩個(gè)算法都應(yīng)用了文獻(xiàn)?[7]出的參數(shù)，但改進(jìn)的算法顯然要比傳統(tǒng)算法的覆蓋率高。因此，當(dāng)評(píng)分矩陣極其稀疏的情況下，本文利用用戶集合分類(lèi)從而壓縮稀疏矩陣的方法，考慮到了用戶之間的關(guān)聯(lián)性和項(xiàng)目之間的關(guān)聯(lián)性，得到了較好的推薦結(jié)果。

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

本文在傳統(tǒng)協(xié)同過(guò)濾算法的基礎(chǔ)上，提出了用戶分類(lèi)下兩種算法相結(jié)合的算法，利用用戶分類(lèi)使得輸入的稀疏矩陣得到了相應(yīng)的壓縮，考慮到了用戶間的關(guān)聯(lián)性及項(xiàng)目間的關(guān)聯(lián)性，并且考慮到了用戶活躍度對(duì)于推薦的影響。實(shí)驗(yàn)證明，混合協(xié)同過(guò)濾算法的確提高了推薦準(zhǔn)確度，并且使得覆蓋率也得到了進(jìn)一步的提高。未來(lái)的研究工作主要是怎么減小噪音用戶對(duì)推薦結(jié)果的影響，得到更好的推薦結(jié)果。

參考文獻(xiàn)：

[1]項(xiàng)亮.推薦系統(tǒng)實(shí)踐[M].北京：人民郵電出版社，2012.

[2]魯權(quán)，王如龍，張錦.融合領(lǐng)域模型與隱語(yǔ)義模型的推薦算法[J].計(jì)算機(jī)工程與應(yīng)用，2013（19）：100-105.

[3]李芳，李永進(jìn).一種基于隨機(jī)游走的多維數(shù)據(jù)推薦算法[J].計(jì)算機(jī)科學(xué)，2013（11）：304-307.

[4]蔡孟松，李學(xué)明，尹衍騰.基于社交用戶標(biāo)簽的混合top-N推薦方法[J].計(jì)算機(jī)應(yīng)用研究，2013（05）：1319-1322.

[5]Greg Linden，Brent Smith，Jeremy York.Amazon.com Recommendations：Item-to-Item Collaborative Filtering.IEEE Internet Computing，7（01），2003.2：76-80.

[6]Karypis G.Evaluation of Item-Based Top-N Recommendation Algorithms：Proceedings of the tenth international conference on Information and knowledge management，2001[C]，New York.

[7]Breese J，Hecherman D，Kadie C.Empirical analysis of predictive algorithms for collaborative filtering[C]：Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence，1998，San Francisco，461（08）：43-50.

作者簡(jiǎn)介：黃瓊（1989-），女，山東淄博人，碩士研究生，研究方向：個(gè)性化推薦；馮軍煥（1962-），男，陜西扶風(fēng)人，導(dǎo)師，教授，工學(xué)博士，研究方向：計(jì)算機(jī)軟件、計(jì)算機(jī)網(wǎng)絡(luò)、Internet技術(shù)與應(yīng)用。

作者單位：西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 610031