改進(jìn)的協(xié)同過濾算法及其并行化實(shí)現(xiàn)

李 嵩，李書琴，劉 斌

(西北農(nóng)林科技大學(xué) 信息工程學(xué)院，陜西 楊凌 712100)

0 引 言

為了及時(shí)準(zhǔn)確地獲取有效信息，推薦系統(tǒng)不斷地發(fā)展。其中，協(xié)同過濾推薦算法應(yīng)用最為廣泛[1]。然而，隨著時(shí)代發(fā)展，數(shù)據(jù)量極速膨脹，推薦系統(tǒng)中的數(shù)據(jù)稀疏性和可擴(kuò)展性等問題在很大程度上影響著推薦的效果[2,3]，因此，國(guó)內(nèi)外相關(guān)學(xué)者從不同的角度出發(fā)，采用不同的方法來解決這些問題。楊興耀等[4]提出一種基于信任模型填充的協(xié)同過濾推薦模型；Guo等[5]提出使用用戶信任的鄰居評(píng)分填充和代表用戶偏好；針對(duì)算法的可擴(kuò)展性優(yōu)化，李華等[6]提出一種基于用戶情景模糊聚類，并用Slope One算法填充評(píng)分的方法；Wang等[7]通過融合遺傳算法改進(jìn)K-均值聚類，生成推薦；許偉等[8]提出基于聚類與矩陣分解技術(shù)結(jié)合的方式進(jìn)行協(xié)同過濾推薦；李淋淋等[9]提出用聚類方式生成最近鄰居集，并用加權(quán)的Slope One算法進(jìn)行推薦。

上述文獻(xiàn)中提出的算法仍存在填充后信息缺失或者聚類提取的信息量不夠的問題，也有的算法由于考慮因素過多，導(dǎo)致算法本身較為復(fù)雜，執(zhí)行時(shí)間過長(zhǎng)。且這些算法往往都忽略了用戶興趣與項(xiàng)目類別之間潛在的偏好關(guān)系，沒有充分挖掘用戶興趣。同時(shí)，以上大部分算法都側(cè)重于單節(jié)點(diǎn)實(shí)現(xiàn)，隨著數(shù)據(jù)量的指數(shù)級(jí)增長(zhǎng)，單節(jié)點(diǎn)計(jì)算已經(jīng)不能滿足需求。如今是大數(shù)據(jù)與云計(jì)算的時(shí)代，海量數(shù)據(jù)的多機(jī)并行化計(jì)算是一個(gè)不可避免的趨勢(shì)。因此，本文提出了基于GROUSE和用戶聚類的協(xié)同過濾算法，充分考慮用戶與項(xiàng)目類別之間的潛在關(guān)系，引入類別加權(quán)度的概念改進(jìn)相似度計(jì)算，并在Spark大數(shù)據(jù)計(jì)算平臺(tái)上對(duì)算法進(jìn)行設(shè)計(jì)與實(shí)現(xiàn)。

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

傳統(tǒng)基于項(xiàng)目的協(xié)同過濾算法(item-based CF)以評(píng)分相似性程度為核心，以最近鄰集合為載體進(jìn)行推薦。算法實(shí)現(xiàn)過程主要分為3個(gè)階段，首先構(gòu)建用戶項(xiàng)目評(píng)分模型，然后計(jì)算項(xiàng)目之間的相似度以產(chǎn)生最近鄰集合，最后預(yù)測(cè)評(píng)分產(chǎn)生推薦。具體步驟如下。

(1)建立用戶項(xiàng)目評(píng)分模型

本文構(gòu)建矩陣Rmn表示用戶對(duì)項(xiàng)目的評(píng)分，每一個(gè)行向量表示一位用戶的評(píng)分集合，共m個(gè)，每一個(gè)列向量表示一個(gè)項(xiàng)目的被評(píng)分集，共n個(gè)。矩陣中元素ru,i則表示用戶u對(duì)項(xiàng)目i的評(píng)分。評(píng)分矩陣可表示為

(2)計(jì)算相似度

相似度計(jì)算是協(xié)同過濾算法最重要的一步，其目的是為了描述項(xiàng)目間相似程度，產(chǎn)生最近鄰集合，其計(jì)算結(jié)果對(duì)推薦精度起著決定性作用。在常見的相似性計(jì)算模型中，皮爾遜相關(guān)系數(shù)因效果較好，最為常用[10]，其描述如式(1)所示

(1)

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

最終依據(jù)目標(biāo)未評(píng)分項(xiàng)目與其最近鄰中的項(xiàng)目間相似性計(jì)算用戶對(duì)其的預(yù)測(cè)評(píng)分。預(yù)測(cè)評(píng)分模型可用式(2)進(jìn)行計(jì)算

(2)

得到預(yù)測(cè)評(píng)分后，按照Top-N原則對(duì)用戶進(jìn)行推薦。

2 基于GROUSE和用戶聚類的改進(jìn)協(xié)同過濾算法

本文利用矩陣填充與對(duì)用戶做模糊聚類的思想，解決上述提到的數(shù)據(jù)稀疏性和可擴(kuò)展性問題，并結(jié)合兩步的處理結(jié)果構(gòu)造目標(biāo)用戶簇類的評(píng)分模型；同時(shí)，在算法中考慮用戶對(duì)不同項(xiàng)目類別的偏好不同，提出類別加權(quán)度的概念，用以改進(jìn)相似度計(jì)算，在減少計(jì)算規(guī)模的基礎(chǔ)上，有效地提高了推薦精度。本文算法處理流程如圖1所示。

圖1 基于GROUSE和用戶聚類的改進(jìn)協(xié)同過濾推薦

2.1 格拉斯曼秩1更新子空間估計(jì)法(GROUSE)

矩陣填充(matrix completion)是一個(gè)是通過尋找近似矩陣來逼近原缺失矩陣的技術(shù)。在強(qiáng)不相干條件下恢復(fù)低秩矩陣所要求的采樣數(shù)目是m>Crnlogn，其中m為可觀測(cè)元素?cái)?shù)，r為矩陣的秩，n為矩陣階數(shù)，C是正常數(shù)[11]。由于一個(gè)用戶評(píng)價(jià)過的項(xiàng)目相比較項(xiàng)目總數(shù)來說極其有限，因此用戶評(píng)分矩陣中可觀測(cè)元素非常少，可以認(rèn)為評(píng)分矩陣是一個(gè)低秩矩陣，具有用矩陣填充的方法解決數(shù)據(jù)稀疏性問題的可行性。

Balzano等[12]提出的格拉斯曼秩1更新子空間估計(jì)法(Grassmannian rank-one update subspace estimation，GROUSE)在相同的采樣下，對(duì)于高維低秩的數(shù)據(jù)矩陣，性能比IALM等常用的矩陣填充算法要好[13]。GROUSE算法基于代價(jià)函數(shù)的最小化，函數(shù)定義如式(3)所示

(3)

其中，S是觀測(cè)到的有缺失點(diǎn)的矩陣的一個(gè)子空間。由于GROUSE算法是一個(gè)追蹤子空間的算法，要適用于整個(gè)缺失矩陣的填充，還需要對(duì)算法做些改變。填充具體算法流程見表1。

表1 基于格拉斯曼秩1更新子空間估計(jì)的矩陣填充算法

(4)

2.2 用戶聚類

不同用戶對(duì)不同項(xiàng)目類別喜好程度不同，為了深入挖掘用戶興趣與項(xiàng)目類別間潛在關(guān)系，本文構(gòu)造m×l的用戶項(xiàng)目類別矩陣，并基于該矩陣對(duì)用戶進(jìn)行聚類。矩陣可表示為

該矩陣由n個(gè)l維的向量ti(i=1,…,n)構(gòu)成，其中n和l分別是用戶和項(xiàng)目類別的數(shù)目，矩陣中元素ti,g表示用戶i對(duì)類別g中項(xiàng)目的評(píng)分次數(shù)。

在此基礎(chǔ)上，本文使用FCM(fuzzy C-Means)算法對(duì)用戶聚類。該算法的基本思想是同一個(gè)用戶可以以不同的隸屬度屬于多個(gè)類別，其價(jià)值函數(shù)表達(dá)式如式(5)所示

(5)

(6)

(7)

本文中用戶聚類的FCM算法描述見表2。

表2 FCM算法

本文通過FCM算法做用戶聚類，有兩個(gè)優(yōu)點(diǎn)：其一，通過挖掘用戶興趣與項(xiàng)目類別之間的模糊特性，從本質(zhì)上體現(xiàn)出兩者的潛在關(guān)系；其二，在做推薦時(shí)，只需要判定目標(biāo)用戶所屬簇類，并在簇類內(nèi)部做協(xié)同過濾推薦即可，這種方式能夠大幅降低用戶項(xiàng)目評(píng)分矩陣的維度，減少協(xié)同過濾搜索鄰居用戶的范圍，從而減少計(jì)算復(fù)雜度，有效提高可擴(kuò)展性。

2.3 類別加權(quán)度的概念

傳統(tǒng)協(xié)同過濾算法僅僅以可觀測(cè)到的評(píng)分?jǐn)?shù)值為依據(jù)進(jìn)行計(jì)算，并沒有從其它角度挖掘用戶興趣，這種處理方式則會(huì)忽略一些有價(jià)值的潛在信息。以現(xiàn)實(shí)情況而言，用戶的興趣會(huì)有所偏好，對(duì)于不同的項(xiàng)目類別，用戶的偏好程度也不一樣。基于該實(shí)際情況，本文提出了類別加權(quán)度的概念，來表示用戶u對(duì)項(xiàng)目類別g的喜愛程度。具體的計(jì)算步驟如下：

步驟1 計(jì)算用戶u對(duì)項(xiàng)目類別g的評(píng)分權(quán)重

(8)

步驟2 計(jì)算用戶u對(duì)項(xiàng)目類別g的評(píng)分次數(shù)權(quán)重

(9)

步驟3 計(jì)算用戶u對(duì)項(xiàng)目類別g的類別加權(quán)度

(10)

其中，α是類別加權(quán)因子。

2.4 基于類別加權(quán)度改進(jìn)的相似度計(jì)算

(11)

(12)

根據(jù)式(1)和式(12)并結(jié)合用戶聚類的結(jié)果，改進(jìn)后的項(xiàng)目間相似度計(jì)算如式(13)所示

(13)

其中，Ui,j是用戶u所屬的簇類中對(duì)項(xiàng)目i和j都評(píng)價(jià)過的用戶集合。由此可見，類別加權(quán)度分別作用在原始評(píng)分與填充評(píng)分上使得用戶對(duì)不同類別的電影的評(píng)分有了不同的權(quán)重，考慮了用戶的興趣偏好，符合實(shí)際意義，且將用戶集合縮小為目標(biāo)用戶所屬的簇類，大大減少了相似度計(jì)算量，提高了算法的運(yùn)行效率，有效提高了算法的可擴(kuò)展性。

2.5 本文算法的流程

基于上述分析，本文提出基于GROUSE和用戶聚類的改進(jìn)協(xié)同過濾算法CF-GUC，結(jié)合圖1，算法流程如下：

(1)構(gòu)建用戶項(xiàng)目評(píng)分矩陣R和用戶項(xiàng)目類別矩陣T。

(2)利用表1算法對(duì)原始矩陣R進(jìn)行填充，得到近似矩陣R+。并用R+中元素補(bǔ)充R中相應(yīng)位置的不可觀測(cè)元素，R中已有的元素不變，形成完整的評(píng)分矩陣R*。

(3)利用表2算法基于用戶項(xiàng)目類別矩陣T對(duì)用戶進(jìn)行聚類，產(chǎn)生目標(biāo)用戶所屬簇類，并與R*中的所有行向量取交集，得到類內(nèi)評(píng)分矩陣R′。

(4)對(duì)于矩陣R′，利用式(11)基于類別加權(quán)度加權(quán)進(jìn)行計(jì)算，得到加權(quán)后的類內(nèi)評(píng)分矩陣記為R″。

(5)基于矩陣R″，利用式(13)計(jì)算項(xiàng)目間相似性，并產(chǎn)生目標(biāo)項(xiàng)目的最近鄰居集Ki。

(6)根據(jù)步驟(5)的計(jì)算結(jié)果，利用式(2)做評(píng)分預(yù)測(cè)，得到項(xiàng)目評(píng)分預(yù)測(cè)值pu,i。

2.6 算法特性總結(jié)

綜合上述對(duì)本文所提出算法的描述，該算法具有以下優(yōu)秀的特性：

(1)采用GROUSE算法矩陣填充，每次迭代時(shí)更新子空間的時(shí)間復(fù)雜度極小[13]，所需運(yùn)行時(shí)間大大減少，有效地緩解了數(shù)據(jù)稀疏性；

(2)對(duì)用戶基于類別權(quán)重矩陣進(jìn)行聚類，充分考慮了用戶興趣的偏好，且在目標(biāo)用戶的所屬簇類內(nèi)進(jìn)行相似度計(jì)算，避免了一些無意義的運(yùn)算，極大減少了計(jì)算復(fù)雜度，提高了算法的運(yùn)行時(shí)效；

(3)對(duì)于不同用戶對(duì)不同類別的項(xiàng)目在選擇時(shí)有偏好這一實(shí)際情況，本文引入了類別加權(quán)度的概念，深入挖掘用戶興趣與項(xiàng)目類別之間的潛在關(guān)系，并從評(píng)分高低與評(píng)分次數(shù)兩個(gè)角度將權(quán)值作用于矩陣填充的結(jié)果之上，從而在一定程度上減少直接使用填充值計(jì)算所帶來的計(jì)算誤差。

3 基于GROUSE和類別加權(quán)度的協(xié)同過濾算法在Spark上并行實(shí)現(xiàn)

3.1 Spark大數(shù)據(jù)計(jì)算平臺(tái)

Spark是一個(gè)處理海量數(shù)據(jù)的快速、通用的并行計(jì)算框架，其核心是彈性分布式數(shù)據(jù)集(resilient distributed datasets,RDD)。RDD的最大特點(diǎn)是基于內(nèi)存計(jì)算，可以降低硬盤I/O的帶來開銷，提高執(zhí)行效率。理論上利用Spark平臺(tái)可以突破因?yàn)楹Ａ繑?shù)據(jù)造成的存儲(chǔ)困難與計(jì)算復(fù)雜度高等限制，是提高系統(tǒng)可擴(kuò)展性的有效方式?；赟park實(shí)現(xiàn)的推薦算法有以下優(yōu)點(diǎn)：

(1)所有的運(yùn)算都基于RDD，其基于內(nèi)存計(jì)算和懶加載的特性，對(duì)于諸如相似度計(jì)算等需要大量迭代的算法，優(yōu)勢(shì)更加明顯，能夠大大減少推薦算法的執(zhí)行時(shí)間。

(2)Spark支持多種分布式存儲(chǔ)結(jié)構(gòu)，如HDFS、S3等，這為推薦系統(tǒng)在數(shù)據(jù)存儲(chǔ)上的無限擴(kuò)展提供了理論上的可能性，使得推薦系統(tǒng)據(jù)可擴(kuò)展性問題得到有效改善。

3.2 并行算法實(shí)現(xiàn)

3.2.1 矩陣填充的處理流程

GROUSE算法在進(jìn)行矩陣填充時(shí)，需要依次對(duì)子空間進(jìn)行迭代，盡管每次更新子空間的代價(jià)較小，但是在數(shù)據(jù)量極大的情況下依然會(huì)耗費(fèi)大量的時(shí)間，由于子空間相互獨(dú)立，因此算法可以在Spark平臺(tái)上進(jìn)行并行化的實(shí)現(xiàn)，以提高填充速度。本文參考吳文波等[14]關(guān)于奇異值分解的并行處理方法的研究，并結(jié)合GROUSE算法更新子空間代價(jià)函數(shù)每次只優(yōu)化一列的特點(diǎn)，采用如下的填充過程：首先根據(jù)數(shù)據(jù)集構(gòu)建轉(zhuǎn)置評(píng)分矩陣RT；然后將RT按列進(jìn)行分片，形成多個(gè)小的子矩陣；之后利用GROUSE算法分別對(duì)各個(gè)子矩陣進(jìn)行填充；最后合并各個(gè)填充子矩陣，生成填充矩陣，并與原始矩陣按照式(4)的規(guī)則進(jìn)行整合。

首先讀入評(píng)分?jǐn)?shù)據(jù)到RDD中，通過map操作將RDD中的每條記錄轉(zhuǎn)為鍵值對(duì)形式，其中鍵是用戶ID，值是一個(gè)Tuple(元組)，存儲(chǔ)形式為。然后通過groupByKey操作歸并，得到同一用戶ID的數(shù)據(jù)，放到新的RDD中，實(shí)現(xiàn)矩陣的分塊，在計(jì)算時(shí)Spark會(huì)把分塊派發(fā)給不同的節(jié)點(diǎn)，并根據(jù)GROUSE算法對(duì)矩陣進(jìn)行填充。由于后續(xù)步驟需要的是填充矩陣與原始評(píng)分矩陣的融合，因此還需要將填充后的各RDD與初始讀入文件形成的RDD進(jìn)行join與union操作，用填充數(shù)據(jù)來取代原本位置上沒有的數(shù)據(jù)，形成無缺失的數(shù)據(jù)矩陣，其輸出為新的評(píng)分?jǐn)?shù)據(jù)文件output1。

3.2.2 用戶聚類的處理流程

首先構(gòu)造用戶項(xiàng)目類別矩陣，讀入項(xiàng)目文件和評(píng)分文件，構(gòu)建的存儲(chǔ)結(jié)構(gòu)，其中g(shù)enre表示項(xiàng)目類別，times表示用戶對(duì)該類別中項(xiàng)目的評(píng)分次數(shù)，通過accumulator函數(shù)創(chuàng)建累加器變量來實(shí)現(xiàn)統(tǒng)計(jì)，形成用戶項(xiàng)目類別的RDD。然后根據(jù)表2的算法描述，對(duì)該RDD進(jìn)行聚類操作，聚類過程中借助Spark的broadcast(廣播變量)對(duì)共享變量廣播到各節(jié)點(diǎn)，通過map、reduceByKey等操作進(jìn)行距離、隸屬度與類中心的計(jì)算與合并，聚類過程中用兩次迭代的價(jià)值函數(shù)的變化值來確定聚類是否結(jié)束。算法結(jié)束時(shí)，生成最終的隸屬度RDD，存放所有用戶對(duì)于各簇類的隸屬度，格式為，命名為uRDD。

聚類完成后還需要獲得目標(biāo)用戶的所屬簇類。按照FCM算法最大隸屬度原則，找到目標(biāo)用戶最大可能性歸屬的簇類以及該簇類中的用戶集合，并與output1文件生成的RDD通過join操作形成簇類內(nèi)的評(píng)分RDD，命名為c_rRDD。

3.2.3 協(xié)同過濾推薦的處理流程

對(duì)目標(biāo)用戶進(jìn)行協(xié)同過濾推薦的過程，分為兩個(gè)階段：一是對(duì)簇類內(nèi)的評(píng)分?jǐn)?shù)據(jù)加權(quán)；二是進(jìn)行協(xié)同過濾的相關(guān)計(jì)算。這樣在計(jì)算的時(shí)候就將所有用戶數(shù)據(jù)集縮小為目標(biāo)用戶所屬簇類的數(shù)據(jù)集，達(dá)到了降維的目的，避免了一些無意義的計(jì)算，處理流程如下：

第一階段，構(gòu)造類別加權(quán)度，對(duì)目標(biāo)用戶所屬簇類中的評(píng)分?jǐn)?shù)據(jù)進(jìn)行加權(quán)。首先，對(duì)于評(píng)分權(quán)重w_ru,j，根據(jù)數(shù)據(jù)集構(gòu)造的RDD，存儲(chǔ)用戶對(duì)該項(xiàng)目類別下項(xiàng)目的總評(píng)分，通過累加器與map操作得到用戶對(duì)每個(gè)項(xiàng)目類別的評(píng)分權(quán)重，生成新的RDD，存儲(chǔ)格式為，命名為w_rRDD；對(duì)于評(píng)分次數(shù)權(quán)重t_ru,j，采取同樣的處理方式得到RDD，存儲(chǔ)格式為，命名為w_tRDD。然后將w_rRDD和w_tRDD用類別加權(quán)因子α加權(quán)求和，生成格式為的RDD。最后通過該RDD中的類別加權(quán)度對(duì)c_rRDD中對(duì)應(yīng)的評(píng)分進(jìn)行加權(quán)計(jì)算，生成簇類內(nèi)加權(quán)評(píng)分的RDD，格式為，命名為c_w_rRDD。

第二階段，進(jìn)行協(xié)同過濾相關(guān)的計(jì)算。首先，計(jì)算項(xiàng)目間相似度，在式(13)的基礎(chǔ)上對(duì)c_w_rRDD進(jìn)行轉(zhuǎn)換操作，計(jì)算元組中每個(gè)項(xiàng)目的評(píng)分均值以及評(píng)分與評(píng)分均值的差值，輸出為平均評(píng)分文件output2，用flatMap和aggregateByKey操作進(jìn)行項(xiàng)目間配對(duì)與歸并，并通過mapValues進(jìn)行配對(duì)項(xiàng)目間的相似度計(jì)算，形成simRDD。然后，計(jì)算最近鄰，轉(zhuǎn)換simRDD格式為，通過map操作對(duì)列表中的值進(jìn)行排序，選出項(xiàng)目的k近鄰集合為kNeiRDD。最后，預(yù)測(cè)評(píng)分，在kNeiRDD中過濾出目標(biāo)項(xiàng)目的近鄰集合，在c_w_rRDD中過濾出用戶對(duì)項(xiàng)目的實(shí)際評(píng)分，并將兩RDD做join操作，結(jié)合output2中的平均評(píng)分基于式(2)計(jì)算最終的預(yù)測(cè)評(píng)分。

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

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

本文實(shí)驗(yàn)數(shù)據(jù)集來自MovieLens推薦系統(tǒng)(http://movielens.org)，其近似數(shù)據(jù)量描述見表3。每條評(píng)分記錄包括用戶ID、項(xiàng)目ID、評(píng)分、時(shí)間戳等4個(gè)屬性，評(píng)分為1到5，評(píng)分越高表示用戶對(duì)該電影的喜愛度越高[15]。

表3 MovieLens數(shù)據(jù)集描述

4.2 度量標(biāo)準(zhǔn)和實(shí)驗(yàn)環(huán)境

本文用統(tǒng)計(jì)方法中的平均絕對(duì)誤差MAE(mean absolute error)度量指標(biāo)來描述推薦質(zhì)量，MAE值越小，則推薦精度越高。該指標(biāo)的計(jì)算方法如式(14)所示

(14)

其中，pi為預(yù)測(cè)評(píng)分，ri為實(shí)際評(píng)分。

本文實(shí)驗(yàn)所需的Spark環(huán)境分為單節(jié)點(diǎn)的本地模式和多節(jié)點(diǎn)集群模式，Spark版本1.6.1，Linux版本Cent OS 6.5。實(shí)驗(yàn)環(huán)境硬件配置見表4。

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

實(shí)驗(yàn)1：選取最優(yōu)類別加權(quán)因子α。本文以數(shù)據(jù)量為100 k的數(shù)據(jù)集為樣本確定參數(shù)α，訓(xùn)練集取其中80%，測(cè)試集取其中20%。參數(shù)確定的原則是通過控制變量，來比較不同α取值時(shí)MAE值的大小。圖2的實(shí)驗(yàn)結(jié)果是設(shè)置最近鄰個(gè)數(shù)k為50時(shí)取得，可以看到，當(dāng)α=0.4時(shí)，本文算法得到最小的MAE值。

表4 實(shí)驗(yàn)環(huán)境硬件配置

圖2 不同α取值下本文算法的MAE比較

實(shí)驗(yàn)2:算法對(duì)比實(shí)驗(yàn)

為了驗(yàn)證本文算法的推薦效果，將本文改進(jìn)算法與以下幾種常見的協(xié)同過濾推薦算法進(jìn)行對(duì)比實(shí)驗(yàn)：

(1)CF-mean：基于評(píng)分均值填充的CF算法；

(2)CF-UC：基于簡(jiǎn)單用戶聚類的CF算法；

(3)Pearson-CF：基于皮爾遜相關(guān)系數(shù)的CF算法；

(4)CF-GUC：本文提出的改進(jìn)算法。

按照實(shí)驗(yàn)1中參數(shù)選取的結(jié)果，CF-GUC算法設(shè)置類別加權(quán)因子α=0.4，圖3描述了不同鄰居數(shù)下以上幾種算法的MAE值對(duì)比?？梢娫趉>40時(shí)，基本所有的算法都趨于穩(wěn)定。由于本文算法能夠有針對(duì)性地解決數(shù)據(jù)矩陣稀疏性問題，且將用戶關(guān)于電影類別的興趣進(jìn)行了更深層次的挖掘，并依照用戶興趣對(duì)相似度計(jì)算進(jìn)行了改進(jìn)，可以看到在實(shí)驗(yàn)范圍內(nèi)的鄰居數(shù)目下，CF-GUC算法相比于其它算法推薦效果要好。當(dāng)最近鄰居數(shù)k取30到40時(shí)，CF-GUC算法相比于CF-mean算法、CF-UC算法、Pearson-CF算法，MAE值分別降低了約3.31%，3.02%，6.48%。

圖3 不同鄰居數(shù)目下各算法的MAE比較

實(shí)驗(yàn)3:算法執(zhí)行效率測(cè)試。實(shí)驗(yàn)環(huán)境如表4中所描述，比較表3中不同數(shù)據(jù)集在3種實(shí)驗(yàn)環(huán)境下的執(zhí)行時(shí)間。實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 不同環(huán)境下本文算法運(yùn)行時(shí)間比較

圖4中，縱軸表示本文算法的運(yùn)行時(shí)長(zhǎng)，單位為分鐘，橫軸表示3種規(guī)模不同的數(shù)據(jù)集。從圖4中可以觀察到，在數(shù)據(jù)量較小的時(shí)候，單節(jié)點(diǎn)與兩種Spark集群運(yùn)行時(shí)間基本差不多，這是因?yàn)镾park集群在計(jì)算的時(shí)候需要進(jìn)行任務(wù)拆分與合并，這種資源調(diào)度消耗了較多的運(yùn)行時(shí)間，因此在數(shù)據(jù)量較小的時(shí)候，集群的優(yōu)勢(shì)并不能體現(xiàn)出來，甚至有時(shí)候會(huì)比單節(jié)點(diǎn)執(zhí)行效率更低。隨著數(shù)據(jù)集規(guī)模的增大，集群的優(yōu)勢(shì)逐漸凸顯出來，特別是Spark基于內(nèi)存迭代計(jì)算的高效性也愈加明顯。在ml-1m的數(shù)據(jù)集上，3節(jié)點(diǎn)的Spark集群執(zhí)行效率比單節(jié)點(diǎn)高約40.6%，4節(jié)點(diǎn)的Spark集群執(zhí)行效率比單節(jié)點(diǎn)高約58.4%?？梢钥吹剑捎趍l-10m的數(shù)據(jù)集規(guī)模太大，在單機(jī)狀態(tài)下已經(jīng)無法進(jìn)行計(jì)算，故沒有數(shù)據(jù)，而Spark集群依然能高效地完成計(jì)算任務(wù)，且4節(jié)點(diǎn)的Spark集群相較于3節(jié)點(diǎn)的Spark集群，計(jì)算效率仍有提高。但是，這并不能說明集群中節(jié)點(diǎn)數(shù)越多越好，在數(shù)據(jù)規(guī)模一定的情況下，節(jié)點(diǎn)數(shù)多了，反而會(huì)因?yàn)橘Y源調(diào)度、網(wǎng)絡(luò)通信等過程降低執(zhí)行效率。在實(shí)驗(yàn)過程中，筆者還發(fā)現(xiàn)，大規(guī)模用戶聚類以及獲得目標(biāo)用戶簇類等過程會(huì)耗費(fèi)大量時(shí)間，因此從實(shí)際應(yīng)用的角度出發(fā)，對(duì)于諸如矩陣填充、用戶聚類等可以離線計(jì)算的過程，可以放在離線部分處理，能夠進(jìn)一步保證算法的執(zhí)行效率。

通過上述3個(gè)實(shí)驗(yàn)可以看出，本文提出的CF-GUC算法在推薦質(zhì)量上有很大提高，且算法在Spark集群上的并行化執(zhí)行，極大地縮短了其運(yùn)行時(shí)間，大大提高了系統(tǒng)的可擴(kuò)展性。

5 結(jié)束語

本文以解決傳統(tǒng)協(xié)同過濾推薦算法中存在的數(shù)據(jù)矩陣稀疏性問題和可擴(kuò)展性問題為出發(fā)點(diǎn)，提出了基于GROUSE和用戶聚類的改進(jìn)協(xié)同過濾推薦算法。算法首先通過GROUSE算法對(duì)評(píng)分矩陣做填充，以解決數(shù)據(jù)矩陣稀疏性問題，并引入類別加權(quán)度，對(duì)評(píng)分進(jìn)行加權(quán)；其次，構(gòu)造用戶電影類別矩陣，對(duì)用戶進(jìn)行聚類；再次，在協(xié)同過濾推薦階段，在目標(biāo)用戶所屬的簇類內(nèi)進(jìn)行相似度計(jì)算；最后實(shí)現(xiàn)了算法在Spark集群上的并行化，通過聚類技術(shù)和借助Spark計(jì)算平臺(tái)解決系統(tǒng)的可擴(kuò)展性問題。

實(shí)驗(yàn)結(jié)果表明，在同等條件下本文算法在推薦質(zhì)量方面表現(xiàn)優(yōu)秀，且通過聚類和算法在Spark集群上實(shí)現(xiàn)的手段，使得算法的執(zhí)行效率也有了大幅提高。但是聚類參數(shù)是影響推薦精度的重要條件，Spark的分片以及代碼分發(fā)等也是影響計(jì)算效率的重要因素，這些參數(shù)的調(diào)優(yōu)與配置有待進(jìn)一步實(shí)驗(yàn)與深入研究。