李 洋 黃樹(shù)成

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212003）

1 引言

隨著信息化時(shí)代的發(fā)展，人們生活與工作中所產(chǎn)生、接收的信息量越來(lái)越龐大，對(duì)信息的處理和過(guò)濾就顯得尤為重要。信息的過(guò)濾可以通過(guò)推薦算法來(lái)實(shí)現(xiàn)。好的推薦算法對(duì)整個(gè)系統(tǒng)的推薦準(zhǔn)確度以及系統(tǒng)性能提升有很大的幫助。近年來(lái)，國(guó)內(nèi)外涌現(xiàn)了不少高效的推薦算法，有內(nèi)容關(guān)聯(lián)算法、K-means聚類算法等［1］。隨著大數(shù)據(jù)時(shí)代來(lái)臨，推薦系統(tǒng)中的數(shù)據(jù)量和需要推薦的商品數(shù)量呈指數(shù)倍增長(zhǎng)，使得大量數(shù)據(jù)的處理速度過(guò)慢，因此推薦算法領(lǐng)域中產(chǎn)生了分布式推薦算法這一研究方向。

在信息泛濫的網(wǎng)絡(luò)世界中，只有擁有對(duì)大數(shù)據(jù)的處理能力，才能快速高效地對(duì)海量數(shù)據(jù)進(jìn)行過(guò)濾、篩選，并在極短的時(shí)間內(nèi)對(duì)用戶的需求做出響應(yīng)。在本文中，將會(huì)介紹傳統(tǒng)協(xié)同過(guò)濾推薦算法（Collaborative filtering recommendation），并對(duì)User?Based算法和ItemBased算法分別加以介紹，對(duì)兩種算法的優(yōu)缺點(diǎn)進(jìn)行分析，并修改原有的ItemBased算法來(lái)提升算法的性能、優(yōu)化其短板［2］。

2 協(xié)同過(guò)濾算法

協(xié)同過(guò)濾推薦算法的原理是統(tǒng)計(jì)與目標(biāo)用戶有著相同興趣的用戶，或者有同樣的經(jīng)驗(yàn)的用戶群體，歸納該用戶群體感興趣的信息，將這些信息推薦給目標(biāo)用戶［3］。個(gè)人用戶能夠通過(guò)反饋一定的信息（如評(píng)價(jià)）能夠?yàn)槠渌脩舻耐扑]提供一定的幫助。協(xié)同過(guò)濾算法能夠幫助目標(biāo)用戶發(fā)現(xiàn)他們潛在的興趣或者可能喜歡的物品，并且這種推薦算法推薦的質(zhì)量都比較高。

協(xié)同過(guò)濾算法分為以用戶為基礎(chǔ)（UserBased）的協(xié)同過(guò)濾和以項(xiàng)目為基礎(chǔ)（ItemBased）的協(xié)同過(guò)濾兩大類。

以用戶為基礎(chǔ)的協(xié)同過(guò)濾算法，通過(guò)使用相似統(tǒng)計(jì)的方法，獲取到具有相似興趣的相鄰用戶進(jìn)行推薦，因此該算法又稱為基于鄰居的協(xié)同過(guò)濾算法（Neighbor-based Collaborative Filtering）。

以項(xiàng)目為基礎(chǔ)的協(xié)同過(guò)濾算法，通過(guò)統(tǒng)計(jì)用戶本來(lái)喜好的、評(píng)分高的項(xiàng)目，再找到與之相似的項(xiàng)目，通過(guò)計(jì)算項(xiàng)目之間的相似性，達(dá)到來(lái)代替用戶之間的相似性。該算法認(rèn)為通過(guò)這種方法找到的項(xiàng)目更能夠引起用戶的興趣。同時(shí)，以用戶為基礎(chǔ)的協(xié)同過(guò)濾算法在用戶數(shù)量增加的時(shí)候，算法的計(jì)算時(shí)間會(huì)變得更長(zhǎng)，而已項(xiàng)目為基礎(chǔ)的協(xié)同過(guò)濾算法剛好能夠解決這一問(wèn)題。在本文中，也正是需要對(duì)這一算法進(jìn)行改進(jìn)。

該方法需要以下幾個(gè)步驟。

1）收集用戶信息

這里的用戶信息主要指的是用戶對(duì)于不同項(xiàng)目的興趣信息，比如說(shuō)有許多網(wǎng)站會(huì)讓用戶在使用過(guò)后進(jìn)行評(píng)價(jià)，根據(jù)用戶的評(píng)價(jià)好壞以及評(píng)價(jià)等級(jí)來(lái)判斷用戶的喜好程度［4］。除此之外，可以根據(jù)用戶在網(wǎng)上的行為進(jìn)行收集信息，系統(tǒng)根據(jù)用戶的行為進(jìn)行喜好程度評(píng)價(jià)，比如用戶點(diǎn)贊、收藏、分享等行為，或者在次使用等行為，都能夠讓系統(tǒng)進(jìn)行自動(dòng)評(píng)價(jià)，不需要用戶去主動(dòng)地進(jìn)行評(píng)價(jià)操作或者輸入相關(guān)的評(píng)價(jià)數(shù)據(jù)。由于在電子商務(wù)網(wǎng)站有許多用戶的商品購(gòu)買及使用操作記錄，這種算法在電子商務(wù)網(wǎng)站上有很大的優(yōu)勢(shì)［5］。

2）針對(duì)物品的最近鄰搜索

將待測(cè)物品和已評(píng)價(jià)的物品的相似度作為權(quán)重，加權(quán)已評(píng)價(jià)物品的分?jǐn)?shù)，就能夠得到待預(yù)測(cè)物品的預(yù)測(cè)值。比如要同時(shí)對(duì)A和B兩個(gè)物品進(jìn)行計(jì)算，就要先找到同時(shí)對(duì)A和B進(jìn)行評(píng)價(jià)過(guò)的用戶，用這些用戶的組合進(jìn)行計(jì)算。目前較為常見(jiàn)的相似度算法有皮爾森相關(guān)系數(shù)公式、余弦相似度公式以及修正的余弦相似度公式等。

設(shè)現(xiàn)有兩件物品a和b，用戶u，物品a和物品b都評(píng)價(jià)過(guò)的用戶集合為Uab，用戶u對(duì)物品a和物品b的評(píng)價(jià)分別為rua和rub，物品a和物品b的評(píng)分期望值分別為`rˉa和`rˉb，則根據(jù)皮爾森相關(guān)系數(shù)公式可得，物品a和b之間的相似度SIM（a，b）的值如式（1）所示：

3）產(chǎn)生推薦結(jié)果

根據(jù)用戶已評(píng)價(jià)的物品和待測(cè)物品間的相似度，計(jì)算出適合推薦的物品作為推薦結(jié)果，進(jìn)而推送給對(duì)應(yīng)的用戶［6］。與UserBased推薦算法相比，ItemBased協(xié)同過(guò)濾推薦算法在進(jìn)行推薦計(jì)算是不需要使用目標(biāo)用戶的歷史數(shù)據(jù)，因此推薦的精準(zhǔn)度不會(huì)受到冷啟動(dòng)的影響。一般情況下不同的物品之間的相似性非常穩(wěn)定，受到用戶數(shù)量變化的影響很小，因此許多關(guān)于推薦計(jì)算的步驟可以離線完成［9］，不會(huì)影響在線用戶的體驗(yàn)，效率比UserBased算法要高。當(dāng)然，這一算法更適用于用戶數(shù)量多于數(shù)量的情況。

3 基于Hadoop平臺(tái)的ItemBased推薦算法

與其他推薦算法相比，傳統(tǒng)的協(xié)同過(guò)濾推薦算法有自己的優(yōu)勢(shì)，但是仍然還存在些許不足之處［10］。主要表現(xiàn)在以下幾個(gè)方面。

1）冷啟動(dòng)推薦精準(zhǔn)度不夠

一般的推薦系統(tǒng)在進(jìn)行推薦的時(shí)候需要使用大量用戶的歷史評(píng)價(jià)數(shù)據(jù)，尤其是傳統(tǒng)的User?Based推薦算法，對(duì)數(shù)據(jù)的需求尤為明顯。在本文中使用的ItemBased推薦算法對(duì)用戶的歷史評(píng)價(jià)記錄依賴程度并不高，受到冷啟動(dòng)問(wèn)題的影響也不大。

2）稀疏數(shù)據(jù)推薦可靠性低

在協(xié)同過(guò)濾推薦系統(tǒng)中，用戶評(píng)價(jià)的數(shù)據(jù)越多，最終根據(jù)算法得出的推薦結(jié)果越可靠，但是當(dāng)用戶的評(píng)價(jià)數(shù)量很少的時(shí)候，或者兩個(gè)項(xiàng)目之間共同評(píng)價(jià)的用戶的數(shù)量很少甚至沒(méi)有的時(shí)候，通過(guò)皮爾森相關(guān)系數(shù)公式計(jì)算出的推薦結(jié)果可靠性就會(huì)大幅下降。很明顯，數(shù)據(jù)的稀疏性［7］對(duì)于推薦的可靠性有非常大的影響。因此在原公式修改為式（2）：

其中λ是對(duì)當(dāng)前推薦結(jié)果的可靠性的度量，它的值為原始評(píng)價(jià)矩陣中項(xiàng)目間評(píng)分用戶交集個(gè)數(shù)與項(xiàng)目間評(píng)分用戶交集大小閾值的商，取值范圍為（0，1］。當(dāng)用戶評(píng)價(jià)的交集越大，推薦的準(zhǔn)確度越高，λ值也就越大。

3）可擴(kuò)展性問(wèn)題

隨著系統(tǒng)的不斷使用，產(chǎn)生的數(shù)據(jù)量會(huì)不斷增多，處理數(shù)據(jù)的時(shí)間也會(huì)相應(yīng)地變長(zhǎng)。這時(shí)，算法的可擴(kuò)展性就顯得尤為重要［8］。近年來(lái)，越來(lái)越多的推薦系統(tǒng)中都遇到了這一問(wèn)題，推薦算法的可擴(kuò)展性也受到了越來(lái)越多人的關(guān)注［11］。為了解決這一問(wèn)題，本文中使用了Hadoop集群實(shí)現(xiàn)對(duì)數(shù)據(jù)的分布式計(jì)算和存儲(chǔ)。

Hadoop是一個(gè)開(kāi)源的分布式計(jì)算框架，它提供了分布式文件系統(tǒng)HDFS（Hadoop Distributed File System）和MapReduce分布式計(jì)算的軟件架構(gòu)。MapReduce框架的計(jì)算過(guò)程分為Map和Re?duce兩個(gè)階段。在MapReduce作業(yè)中，輸入的數(shù)據(jù)集被且分為若干獨(dú)立的數(shù)據(jù)塊，現(xiàn)有Map任務(wù)并行處理，對(duì)Map的輸出數(shù)據(jù)排序后，再作為輸入數(shù)據(jù)交由Reduce任務(wù)處理，最終輸出計(jì)算結(jié)果。每個(gè)階段的輸入輸出數(shù)據(jù)格式是以形式呈現(xiàn)的鍵值對(duì)。開(kāi)發(fā)者只需要編寫Map和Reduce階段的映射函數(shù)即可，任務(wù)裝載、調(diào)度和節(jié)點(diǎn)間的通信由Hadoop自動(dòng)完成。該集群的工作流程如圖1所示。

圖1 算法工作流程圖

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

4.1 實(shí)驗(yàn)平臺(tái)及數(shù)據(jù)說(shuō)明

根據(jù)上述研究，利用7臺(tái)計(jì)算機(jī)作為硬件，其中有1個(gè)Master節(jié)點(diǎn)和6個(gè)Salave節(jié)點(diǎn)。計(jì)算機(jī)統(tǒng)一搭載Ubuntu 15.04，Hadoop版本為3.1.2，JDK版本為1.8.0_181。

本文中的實(shí)驗(yàn)選取了MovieLens中的電影評(píng)價(jià)數(shù)據(jù)集，并分別下載了大小為100KB、1MB、10MB的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集的詳細(xì)信息如下：1）100KB：包括943個(gè)用戶對(duì)1628部電影的100000條評(píng)分記錄；2）1MB：包括6040個(gè)用戶對(duì)3900部電影的1000209條評(píng)分記錄；3）10MB：包括71567個(gè)用戶對(duì)10681部電影的1000054條評(píng)分記錄，評(píng)分范圍為1～5，每個(gè)用戶至少對(duì)20部電影進(jìn)行過(guò)評(píng)價(jià)。

4.2 實(shí)驗(yàn)結(jié)果評(píng)估指標(biāo)

本文中的實(shí)驗(yàn)結(jié)果評(píng)估指標(biāo)主要有兩項(xiàng)：加速比和平均絕對(duì)偏差MAE。

加速比就是指在相同的系統(tǒng)環(huán)境下使用同樣的數(shù)據(jù)集對(duì)目標(biāo)商品進(jìn)行選擇推薦，單機(jī)運(yùn)行串行算法與集群運(yùn)行并行算法所需時(shí)間之比。設(shè)程序的串行時(shí)間為T1，在N個(gè)節(jié)點(diǎn)上的并行時(shí)間為TN，則加速比的公式如式（3）所示。

平均絕對(duì)偏差MAE在本文中用來(lái)衡量推薦準(zhǔn)確度。其基本思想是通過(guò)計(jì)算預(yù)測(cè)值和真實(shí)值之間的平均絕對(duì)偏差來(lái)衡量算法的最終運(yùn)行結(jié)果和真實(shí)值的偏差大小。MAE的值越小，就代表推薦值和真實(shí)值之間的誤差就越小，推薦結(jié)果也就越準(zhǔn)確。設(shè)Pi為項(xiàng)目的預(yù)測(cè)評(píng)分值，Ri為項(xiàng)目的真實(shí)評(píng)分值，N為實(shí)驗(yàn)中的項(xiàng)目個(gè)數(shù)，則MAE值的公式見(jiàn)式（4）。

4.3 結(jié)果分析

本文選取平均絕對(duì)誤差（MAE）作為算法推薦質(zhì)量的衡量指標(biāo)。MAE值越小，意味著推薦結(jié)果的準(zhǔn)確度越高。從100KB數(shù)據(jù)集中，分別選取用戶數(shù)量為50、200、400、800和943作為5組實(shí)驗(yàn)數(shù)據(jù)。實(shí)驗(yàn)結(jié)果見(jiàn)表1。

表1 數(shù)據(jù)集詳細(xì)數(shù)據(jù)

在5組實(shí)驗(yàn)數(shù)據(jù)下將本文提出的算法分別放在非分布式環(huán)境和分布式環(huán)境下進(jìn)行推薦，計(jì)算MAE值，最終結(jié)果如圖2所示。

圖中，縱軸為MAE值，橫軸為5組實(shí)驗(yàn)數(shù)據(jù)的編號(hào)，根據(jù)圖中的折線圖可以看出，本文提出的基于Hadoop平臺(tái)的ItemBased推薦算法的MAE值要低于另外兩種算法，并且三種算法最終的MAE值都隨著實(shí)驗(yàn)數(shù)據(jù)量的增大而減小，推薦精度也越高。兩種ItemBased算法在第一組數(shù)據(jù)中存在著一定的數(shù)據(jù)稀疏性的問(wèn)題，尤其是分布式ItemBased算法，其第一組數(shù)據(jù)中的稀疏性問(wèn)題頗為嚴(yán)重［12］。而本文的算法在第一組數(shù)據(jù)中克服了數(shù)據(jù)稀疏性的問(wèn)題，MAE值遠(yuǎn)低于另外兩種算法。這說(shuō)明本文提出的算法能夠很好地解決數(shù)據(jù)稀疏性問(wèn)題。

另外，本文使用加速比來(lái)比較Hadoop集群對(duì)于多種不同規(guī)模數(shù)據(jù)的執(zhí)行效率。由上文可知加速比S=T1/Tn，T1為單個(gè)節(jié)點(diǎn)的運(yùn)算時(shí)間，Tn為n個(gè)節(jié)點(diǎn)的運(yùn)算時(shí)間。在實(shí)驗(yàn)過(guò)程中分別啟動(dòng)1～7臺(tái)運(yùn)算節(jié)點(diǎn)，分別根據(jù)運(yùn)行時(shí)間繪制曲線圖如圖3。

圖3 數(shù)據(jù)集處理加速比變化

該圖顯示三個(gè)不同大小的數(shù)據(jù)集在Hadoop集群上進(jìn)行算法處理的加速比變化。這表明，針對(duì)同一數(shù)據(jù)集，增加節(jié)點(diǎn)數(shù)量可以提高算法效率。這種效率的提升在節(jié)點(diǎn)數(shù)量少的時(shí)候還不明顯，當(dāng)節(jié)點(diǎn)數(shù)量多之后，效率的提升效果就會(huì)非常明顯。因此基于Hadoop集群的ItemBased推薦算法在大數(shù)據(jù)規(guī)模下?lián)碛辛己玫目蓴U(kuò)展性。

5 結(jié)語(yǔ)

傳統(tǒng)的協(xié)同過(guò)濾推薦算法中存在著數(shù)據(jù)稀疏性和可擴(kuò)展性兩個(gè)問(wèn)題［13］，本文針對(duì)這兩個(gè)問(wèn)題進(jìn)行了深入的研究，并通過(guò)實(shí)驗(yàn)驗(yàn)證了自己的優(yōu)化方案。本文將ItemBased推薦算法稍作改進(jìn)，增加了推薦結(jié)果可靠性的權(quán)值，并根據(jù)Hadoop集群的分布式計(jì)算特點(diǎn)將算法移植到Hadoop集群進(jìn)行Ma?pReduce化處理。通過(guò)實(shí)驗(yàn)證明，改算法能夠顯著改善推薦算法的數(shù)據(jù)稀疏性和可擴(kuò)展性，從而提高大數(shù)據(jù)環(huán)境下的數(shù)據(jù)處理能力。