一種基于Spark的改進協同過濾算法研究

許智宏 蔣新宇 董永峰 趙嘉偉

1(河北工業大學計算機科學與軟件學院 天津 300401)2(河北省大數據計算重點實驗室 天津 300401)

一種基于Spark的改進協同過濾算法研究

許智宏1,2蔣新宇1董永峰1,2趙嘉偉1

1(河北工業大學計算機科學與軟件學院 天津 300401)2(河北省大數據計算重點實驗室 天津 300401)

為提高協同過濾算法在大數據環境下的可擴展性以及在高維稀疏數據下的推薦精度，基于Spark平臺實現了一種分層聯合聚類協同過濾算法。利用聯合聚類對數據集進行稀疏性處理并構建聚類模型，運用層次分析模型并結合評分密集度分析聯合聚類模型中用戶和項目潛在類別權重，由此進行項目相似度計算并構建項目最近鄰居集合，完成在線推薦。通過在GroupLens提供的不同規模MovieLens數據集上實驗表明，改進后的算法能夠明顯提高推薦的準確度，并且在分布式環境下具有良好的推薦效率和可擴展性。

協同過濾 聯合聚類 層次分析模型 Spark

0 引 言

互聯網的普及和快速發展為用戶提供了大量的信息，滿足了用戶的信息需求，但用戶在海量信息中如何獲取對自己有用的信息成為了一個急需解決的問題，個性化推薦系統的出現使得這一問題得到改善。

常見的個性化推薦系統，如協同過濾、內容過濾和社會化推薦系統[1]等。其中，基于協同過濾的推薦系統最為成熟、有效并且應用廣泛。它根據目標用戶對推薦對象最近鄰居的評價來預測對推薦對象的評價。通常包括：基于用戶的協同過濾[2]、基于項目的協同過濾[3]。

基于項目的協同過濾推薦算法需要計算項目間相似性搜索被推薦項目的最近鄰居，從而為目標用戶進行評分預測和推薦。由于用戶和項目數量的不斷增長，協同過濾算法面臨著嚴重的數據稀疏性和數據規模可擴展性問題。

針對數據稀疏性問題，許多研究者從不同的角度對協同過濾提出了改進方法，如文獻[4]從相似度傳播的角度對數據稀疏性問題進行了相關研究，但該算法的復雜度較高，時空開銷較大。文獻[5]通過融入社交網絡好友信任關系，有效緩解了數據的稀疏性問題，文獻[6]使用奇異值分解來降低評分矩陣的維數從而達到降低矩陣稀疏性的目的，但該方法計算量較大，而且降維也會導致信息缺失。通過聚類技術降低稀疏度的方法，如文獻[7]首先通過k-means算法進行基于項目的聚類，然后在項目聚類的基礎上計算最近鄰用戶全局相似度。文獻[8]提出了基于雙向聚類的協同過濾推薦算法，利用雙向聚類平滑填充的方法去解決數據稀疏性問題。

針對傳統協同過濾算法在處理大規模數據所遇到的可擴展性問題，許多研究者采用分布式計算實現協同過濾算法來改善算法的可擴展性。文獻[9]將基于用戶的協同過濾算法部署在Hadoop分布式處理平臺上。文獻[10]將改進的基于項目的協同過濾推薦算法，在Hadoop平臺下實現了并行化。文獻[11]提出了一種基于Hadoop平臺的k-means和slope one的混合協同過濾推薦算法。文獻[12]分別在Hadoop和Spark平臺上實現了基于項目的協同過濾算法，并在Spark平臺上獲得了更高的執行效率。

本文針對傳統協同過濾算法的稀疏性和可擴展性問題展開研究，在基于項目的協同過濾算法基礎上，引入聯合聚類、評分密集度、層次分析模型，提出了一種分層的聯合聚類協同過濾算法(AHCCF)，并基于Spark平臺實現AHCCF算法并行化。通過基于用戶維度的聚類將數據劃分為不同用戶族，緩解數據稀疏性對相似度計算的影響。在每個不同用戶簇中計算項目的相似性，再根據聯合聚類和層次分析模型計算用戶簇的權重，進而得到項目的最終相似性，提高了推薦的準確性。通過Spark平臺構建推薦算法，可以充分利用Spark基于RDD的內存計算優勢，在并行計算階段進行高效的數據共享，使算法能夠具有良好的可擴展性和執行效率。

1 一種分層的聯合聚類協同過濾算法

1.1 構建用戶模型

協同過濾算法的用戶模型通常是一個m×n的評分矩陣Rmn，用來表示m個用戶數對n個項目的興趣偏好。其中，用戶的興趣偏好可通過評分值來表示，如rij可用來表示用戶i對項目j的評分，評分高低決定了用戶對項目感興趣程度。

1.2 項目相似性度量

項目的相似性計算，AHCCF算法主要采用皮爾森相關相似性[13]，其中皮爾森相關相似性是目前采用比較廣泛的度量方法。皮爾森相關系數公式如下：

(1)

傳統基于項目的協同過濾算法僅僅采用了單一的相似度來描述項目之間對于所有用戶的相似程度，而沒有考慮到用戶所屬類別的不同對相似度產生的影響。日常經驗告訴我們，在一個喜好程度相近的用戶群中，由于其共同喜好，用戶群中的用戶對感興趣的項目評分比較密集。因此用戶群感興趣的兩個項目之間的相似性能夠比較真實地反映這兩個項目的實際的相似性，因此可以在不同的用戶群中考慮項目的相似性，最后通過用戶群的權重獲得項目最終的相似性。

為了改善數據稀疏性在相似度計算過程中所帶來的影響，AHCCF算法在皮爾森相關系數的基礎上提出了一種新的項目相似性計算方法。通過對評分矩陣R進行用戶聚類得到k個用戶潛在類別，在每個用戶潛在類別的評分矩陣當中運用式(1)進行項目相似性計算，進而得到每個用戶聚類的相似度矩陣集合simUC={simUC1,simUC2,…,simUCk}，使用層次分析模型計算得到用戶潛在類別權重向量WUC，根據式(2)得到最終項目之間的相似度。權重向量WUC需要通過聯合聚類對原始評分矩陣分塊，評估分塊矩陣的評分密集度，構造分層模型計算得到。

(2)

1.2.1 聯合聚類

聚類是將具有相同類別屬性的內容聚集在一起的機器學習方法，是一種處理海量、稀疏數據的有效方法。聯合聚類(Co-Clustering)是對于行列相關的二維矩陣數據模型[14]，從行、列兩個角度進行聚類。相對于傳統僅考慮一維相關信息的單聚類算法，該算法能夠更加有效地挖掘出數據模型當中的潛在類別。

如圖1所示，AHCCF算法采用聯合聚類分別對用戶維和項目維聚類得到用戶潛在類別、項目潛在類別，其中用戶聚類UC={UC1,UC2,…,UCk}、項目聚類IC={IC1,IC2,…,ICk}。經過聯合聚類，可從用戶和項目兩個維度上將評分矩陣劃分成分塊矩陣BC=[BC11,BC12,…,BC1k;…;BCk1,BCk2,BCkk]。通過聯合聚類，可獲取用戶類別在項目維度上的評分分布情況以及項目類別在用戶維度上的評分分布情況。一般來說，一個用戶群在一個項目類別中的評分越密集，表示該類項目更能體現用戶的興趣偏好，計算的項目相似度越真實。因此，可通過分析分塊矩陣以及項目類別矩陣的評分分布情況，來計算每個用戶群在相似度計算過程中所占權重。

圖1 聯合聚類

AHCCF算法采用k-means算法，從用戶和項目兩個維度上進行聯合聚類(CoCluster)，算法具體步驟如下所示：

聯合聚類CoCluster流程:

function [UCIndex, UC, ICIndex,IC] = CoCluster(data, kUCluster, kICluster)

1. UCIndex =kmeans(data, kUCluster);

//用戶維聚類劃分

2. for i = 1: kUCluster

//循環遍歷用戶維聚類

3. UCUserIds = find(UCIndex == i);

//生成用戶類簇所包含的userId集

4. for j=1:length(UCUserIds)

5. uc(j,:)=data(UCUserIds(j),:);

//獲取用戶類簇包含的評分向量集

6. end

7. UC{i}=uc;

//保存所有用戶類簇的評分向量集UC

8. end

9. data = data’;

//轉置生成項目-用戶矩陣

10. ICIndex =kmeans(data,kICluster);

//項目維聚類劃分

11. for i = 1: kICluster

//循環遍歷項目維聚類

12. ICItemIds = find(ICIndex == i);

//生成項目類簇所包含的itemId集

13. for j=1:length(ICItemIds)

14. ic(j,:)=data(ICItemIds(j),:);

//獲取項目類簇包含的評分向量集

15. end

16. IC{i}=ic;

//保存所有項目類簇的評分向量集IC

17. end

1.2.2 評分密集度

分塊矩陣的評分密集度(Rating Intensity)能夠反映分塊矩陣在項目相似度計算上的真實性，一般評分密集度越高的矩陣計算的項目相似度越真實。因此，可通過評分密集度來評價分塊矩陣中的評分分布情況。評分密集度的計算方法：

ri=n/N

(3)

其中n為分塊矩陣中非零評分的個數，N為分塊矩陣中所有評分的個數。

根據式(3)計算基于項目維度的每個聚類IC1,IC2,…,ICk的評分密集度，并構造向量RIIC=(riIC1,riIC2,…,riICk)T，計算每個分塊矩陣BC(i,j)的評分密集度，進而得到評分密集度矩陣RIBC=(αIC1,αIC2,…,αICk)，其中的每個列向量為αICk=(riUC1,riUC2,…,riUCk)T，即αICk是圖1中ICk列各分塊矩陣的評分密集度構成的向量。

AHCCF算法，根據CoCluster的計算結果：用戶聚類評分矩陣(UC)、項目聚類評分矩陣(IC)以及項目聚類所包含的項目索引矩陣(ICIndex)，可計算出分塊矩陣(block)和評分密集度(RatingIntensity)。之后，在AHP中便可通過評分密集度，生成相應的判斷矩陣，計算用戶類簇的相似度計算權重。評分密集度計算的具體步驟如下所示：

評分密集度計算流程：

function [blockIntensityMat, ICIVector]=RatingIndensity(UC, IC, ICIndex)

1. for i=1: kICluster

//項目維聚類遍歷

2. ICItemIds=find(ICIndex ==i);

//查找項目簇包含的ItemIds集

3. for j=1: kUCluster

//用戶維聚類遍歷

4. for k=1:length(ICItemIds)

5. block(:,k)=UC{j}(:,ICItemIds(k));

//構建分塊矩陣

6. end

//計算分塊矩陣評分密集度矩陣

7. blockIntensityMat (j,i)=nnz(block)/numel(block);

8. end

//計算項目聚類評分密集度向量

9. ICIVector(i)=nnz(IC{i})/numel(IC{i});

10. end

1.2.3 層次分析模型

層次分析法是20世紀70年代由美國運籌學家Saaty提出的一種層次權重決策分析方法。通過建立層次分析模型，進行定量計算權重的方法。AHCCF算法通過層次分析模型，并根據1.2.2節中的項目類別評分密集度以及分塊矩陣評分密集度來分析用戶類別在項目相似度計算過程中所占權重。

AHCCF算法以項目聚類的各個潛在類別作為準則層，各個用戶潛在類別作為方案層，通過每個項目潛在類別中的各個分塊矩陣的評分密集度作比較，可以得到每個用戶潛在類別在當前項目潛在類別中的權重，最后綜合各項目潛在類別的權重得到用戶潛在類別的權重。計算用戶潛在類別權重WUC按照下面3個步驟進行：

(1) 構建層次結構模型

分層過程中將用戶潛在類別權重作為目標層，項目潛在類別作為準則層，用戶潛在類別作為方案層，如圖2所示。

圖2 層次分析結構圖

(2) 構造各層次的判斷矩陣

通過聯合聚類過程將用戶和項目劃分成k個潛在類別，每個潛在類別的評分密集度分別為ri1,ri2,…,rik，把這些評分密集度兩兩比較，得到表示相對關系的判斷矩陣：

將權重向量w右乘矩陣A，則有：

(3) 層次單排序和總排序

根據步驟(2)得到的項目潛在類別權重向量WIC和每個項目潛在類別中用戶潛在類別權重矩陣WBC，依據式(4)計算得到用戶潛在類別權重WUC。

WUC=WBC·WIC

(4)

在用戶和項目聚類數均為3時，AHP的層次排序過程，如表1所示。

表1 AHP層次排序

AHCCF算法，采用AHP計算用戶潛在類別在項目相似度計算時所占權重，權重計算的具體步驟如下所示：

用戶潛在類別權重計算：

function [Wuc]=UCWeight (blockIntensityMat, ICIVector, kICluster)

1. for i=1:kICluster;

//計算每個項目類別中的每個分塊矩陣權重向量

2. w=AHP(blockIntensityMat(:,i));

3. Wbc(:,i)=w;

//將每個項目類別分塊矩陣權重向量放入權重矩陣

4. end

5. Wic=AHP(ICIVector)

//計算項目類別權重向量

6. Wuc= Wbc* Wic

//層次總排序，計算用戶類別權重向量

1.2.4 項目相似度

AHCCF算法，經過CoCluster處理后將喜好程度相近的用戶劃分到同一個簇中。在該用戶族中計算項目相似性，能夠更加反應項目真實相似性。AHCCF算法，在CoCluster生成的每個用戶類簇中，運用式(1)進行項目間相似度計算。然后，根據1.2.3節計算出的用戶潛在類別權重，計算出項目的最終相似度。算法的具體步驟如下所示：

項目相似度計算：

function [sim]=computeSim (UC, kUCluster)

1. for i = 1: kUCluster

//循環遍歷用戶維聚類

2. uc = UC{i};

//獲取某個用戶類簇評分矩陣

//皮爾森相似度計算

3. for i=1:size(uc,2)

4. for j=1:size(uc,2)

5. temp=find(uc(:,i)～=0 & uc (:,j)～=0);

//查找item共同評分記錄

6. Rui=data(temp,i);

//獲取item i的共同評分信息

7. Ruj=data(temp,j);

//獲取item j的共同評分信息

8. Ri=mean(data(:,i));

//獲取item i的共同評分均值

9. Rj=mean(data(:,j));

//獲取item j的共同評分均值

10. D(i,j)=(Rui-Ri)'*(Ruj-Rj)/(norm(Rui-Ri)*norm(Ruj-Rj));

11. if isnan(D(i,j))

12. D(i,j)=0;

13. end

14. D(i,j)=abs(D(i,j));

15. D(i,i)=0;

16. end

17. end

18. ucSims(i)=D

//保存每個用戶類簇的相似度計算結果

19. end

20. sim=itemSim(ucSims,Wuc)

//根據用戶聚類權重，計算項目最終相似度

1.3 評分預測

根據1.2節計算出的項目間相似度，找出與目標項目最相似的最近鄰居集合，即為其生成一個相似度遞減排列的最近鄰居列表Ni。該過程分兩步完成：首先，采用1.2.4節中的方式計算項目之間的相似度；其次，將最相似的前k個項目作為最近鄰居集合。

經過項目相似度計算，并生成最近鄰居集Ni后，可對目標用戶u的未評分項目進行評分預測，計算方法如下：

(5)

1.4 算法流程

整個AHCCF算法的流程如圖3所示。

圖3 AHCCF算法流程圖

輸入：目標用戶u，用戶-項目評分矩陣Rm×n，聚類數k

輸出：目標用戶對每個項目的預測評分Pu,j，Top-N推薦

Step1 對用戶-項目評分矩陣Rm×n進行用戶聚類劃分得到k個用戶聚類UC1,UC2,…,UCk，利用式(1)計算每個聚類中項目與項目之間的相似度得到項目相似度矩陣集合simUC={simUC1,simUC2,…,simUCk}。

Step2 對用戶-項目評分矩陣Rm×n進行項目聚類劃分得到k個項目聚類IC1,IC2,…,ICk，根據式(3)計算每個聚類的評分密集度得到RIIC=(riIC1,riIC2,…,riICk)T。

Step3 根據步驟1和步驟2將評分矩陣Rm×n分塊得到分塊矩陣BC=[BC11,BC12,…,BC1k;…;BCk1,BCk2,BCkk]，計算每個分塊矩陣BCij的評分密集度得到評分密集度矩陣RIBC=(αIC1,αIC2,…,αICk)，αICk=(riUC1,riUC2,…,riUCk)T。

Step4 利用層次分析模型(AHP)對Step2、Step3得到的RIIC和RIBC的列向量αICk構造判斷矩陣并計算特征向量，得到項目潛在類別權重向量WIC=(wIC1,wIC2,…,wICk)T和每個項目潛在類別中用戶潛在類別的權重向量所構成的矩陣WBC=(βIC1,βIC2,…,βICk)。

Step5 利用式(4)計算得到用戶潛在類別的權重，再根據Step1計算得到的每個用戶潛在類別中項目之間的相似度，利用式(2)計算得到項目間的最終相似度矩陣Sim。

Step6 在Sim中求得目標項目i的最近鄰集合Ni={n1,n2,…,nk}。

Step7 根據用戶u對i的最近鄰集合Ni的評分值，利用式(5)預測用戶u對目標項目i的評分，產生Top-N推薦列表。

2 基于Spark平臺AHCCF算法并行化

AHCCF算法，在Spark分布式計算平臺下實現算法的并行化。通過基于RDD的內存計算以及數據共享等技術優勢，能夠有效提高AHCCF算法的可擴展性和執行效率。

并行化AHCCF算法，可分為如圖4所示的三個階段。階段一，利用基于Spark平臺的k-means聚類算法[12]分別從用戶維度和項目維度對數據集進行聚類劃分，并生成相應的聚類模型。階段二，對用戶-項目評分記錄進行聚類劃分，并進行用戶聚類相似度計算以及利用AHP計算用戶潛在類別權重。其中AHP的特征值求解，在Spark平臺下基于冪法并行求解實現。階段三，根據用戶潛在類別項目相似度以及用戶潛在類別權重，計算項目最終相似度。然后，生成項目最近鄰居集合，進行評分預測及推薦。

圖4 基于Spark的AHCCF算法流程

AHCCF算法并行化，采用如上圖所示的三個階段來完成。在階段一，需要將訓練集中的每個用戶或項目的評分記錄(userId,ItemID,rate)，轉化為相應的評分向量(userID,Vector)/ (itemID,Vector)。進而進行用戶和項目維度的聚類。由于推薦系統中的評分矩陣是稀疏矩陣，平均每個用戶所包含的評分記錄很少。若在計算過程中，直接存儲或傳輸這樣的矩陣將會占用過多的內存和網絡資源。因此，在加載用戶-項目評分矩陣時，為減少內存消耗以及網絡通信量，采用稀疏向量存儲用戶-項目評分矩陣中的每行記錄。Spark中SparseVector結構如圖5所示。

圖5 稠密向量和稀疏向量

SparkVector對應的實例化簽名為newSparseVector(valsize:Int,valindices:Array[Int],valvalues:Array[Double])。其中，size表示向量長度，indices表示非零元素索引，values表示非零元素值。因此，采用稀疏向量存儲n×n的稀疏矩陣時，空間復雜度由O(n2)降為O(nk)，遍歷矩陣的時間復雜度由O(n2)降為O(nk)。其中，k為每行的非零元素個數。

階段二中，項目聚類劃分結果(UClusterRDD)和用戶聚類劃分結果(IClusterRDD)，需要被重用。因此通過Spark的cache算子將其緩存。當下次使用該RDD時，不會進行重算，直接從緩存中獲取該RDD，提高算法執行效率。

在進行分塊矩陣評分密集度計算時，需要根據用戶類簇評分矩陣信息UClusterRDD(UCId，Vector)以及每個項目類簇所包含的項目索引信息ICIndexRDD(ICId，ICItemIndex)，進行分塊矩陣劃分以及評分密集度計算。在Spark平臺下，需要將UClusterRDD和ICIndexRDD進行笛卡兒積(Cartesian)，獲取每個用戶類簇中的項目類簇信息，然后進行分塊矩陣劃分以及評分密集度計算。少量數據時，Cartesian性能良好。當數據量相對較大時，Cartesian操作，一方面會占用大量網絡資源；另一方面，在Cartesian后會增加RDD分片數量，可能會增加額外的調度開銷。因此Cartesian操作之后一般需要調整分區(repartition)，然后再通過map、reduceByKey等算子統計評分密集度。然而repartition同樣會造成額外的shuffle開銷。 因此，需要對Cartesian進一步優化。

經分析發現，參與笛卡兒積的ICIndexRDD其維度要遠小于UClusterRDD，ICIndexRDD中僅包含每個項目類簇的編號(ICId)以及該項目類簇對應的項目索引(ICItemIndex)，占用空間較少可視為小表。因此可將ICIndexRDD內容轉換為一個HashMap結構：ICMap(ICId,ICItemIndex)。通過Spark廣播機制，將ICMap廣播發送到每個節點上來共享該信息。進而RDD中的每個分片均可訪問到ICMap，在map-side本地即可完成Cartesian操作，具體流程如圖6所示。

圖6 評分密集度計算

如圖6所示，經broadcast機制優化后，與ICIndexRDD的關聯操作在本地即可完成，降低了網絡IO，而且不影響原始分區數量，一般不需要repartition，使得運行效率大幅度提高。其中，每個節點的平均網絡IO由O(nc′)變為O(c′)，n為節點中的分片數量，c′為小表容量，c′≤nc′。

在階段三中，不管是近鄰集合選取還是推薦列表計算，均需要生成一個遞減排序的列表項。然后從中選取前k個列表項，即TopK。在少量數據情況下，可通過groupBy算子進行分組后，再通過flatMap算子選取每個分組的前k個列表項。在數據量較大的情況下，由于groupBy沒有本地combine特性直接進行分組，shuffle過程中的網絡通信量較高，影響算法性能。

因此當數據量較大時，可通過mapPartition算子實現以數據分片為粒度，進行TopK計算。可以在每個分片中維護一個大小為k的大根堆，然后對大根堆進行不斷調整。經過mapPartition處理后，便可求出每個分區的TopK。最后，通過reduceBykey算子，將每個Key所對應的多個分區的TopK進行合并，即可生成每個Key的最終列表項，具體流程如圖7所示。

圖7 計算每個Key對應的TopK Value

經過mapPartition計算，可過濾大量信息。因此可降低shuffle過程中網絡IO，由O(nc)降到O(nk)。其中，n表示分片數量，c表示每個分片中原始數據量，k表示每個分片經過TopK處理后的數據量，k?c。

3 實驗分析

3.1 數據集與實驗環境

為了驗證AHCCF算法的基本表現和分布式環境下的并行效率，本文選取明尼蘇達大學的GroupLens項目組提供的一組中等規模和兩組較大規模的數據集，具體描述如表2所示。

表2 數據集信息

AHCCF算法，在一個配備有5個節點的Spark集群進行實驗。1個主節點，4個從節點。在集群的每個節點中，操作系統為Ubuntu14.04，Spark版本為1.3.0，Hadoop版本為2.6.0。

3.2 算法精準度實驗

AHCCF算法采用平均絕對偏差MAE，作為算法精準的評價指標。其計算公式定義如下：

(6)

其中，N表示項目數量，pi表示項目的實際分數，qi表示項目的預測分數。MAE越小，推薦質量越高。

AHCCF算法選取MovieLensA數據集，來對算法的精準度進行驗證。設計兩組實驗：AHCCF算法在不同聯合聚類數k下的準確度、在數據不同稀疏度下AHCCF算法與IBCF算法[3]、GBCF算法[7]、BSCF算法[8]的對比。

實驗1 測試不同聯合聚類數k對推薦結果的影響，k分別取5、10、20、30、40、50，最近鄰居數取5、10、20、30、40、50、60、70、80、90、100，結果如圖8所示。

圖8 不同聯合聚類參數K下算法精度

實驗結果表明：算法精度受參數k所影響，聯合聚類數k過大、過小都會使推薦精度不理想。一般聚類數越接近項目真實類別數，結果越精確，本實驗中當k=30時算法性能最好，在較少項目最近鄰的情況下，算法很快收斂到誤差最小的推薦結果。

實驗2 測試AHCCF算法在不同稀疏度下的準確度，并通過與IBCF算法、BSCF算法、GBCF算法對比來驗證算法的有效性。實驗過程中，通過調整訓練集和測試集所占評分比重，觀測數據稀疏度對算法精度的影響，實驗結果如表3所示。

表3 算法運行結果

實驗結果表明：隨著訓練集在整個數據集中所占比重的提高，數據的稀疏度逐漸減小，幾個算法的MAE值都在減小，即幾個算法的準確度不斷提升。其中，BSCF算法、GBCF算法的準確度均高于傳統IBCF算法，表明兩者在一定程度上緩解了數據稀疏性問題，提高了算法的準確度。本文提出的AHCCF算法在每種稀疏度情況下，其MAE值均低于BSCF和GBCF算法，表明AHCCF算法能夠更加有效地處理數據的稀疏性問題，提供更高的推薦效率。

3.3 算法并行實驗

AHCCF算法通過采用加速比，來驗證通過對Spark集群的擴展能有效提高不同數據規模下AHCCF算法的執行效率。其計算定義公式如下：

(7)

其中，T1表示在單節點情況下算法運行時間，Tn表示n個節點算法的運行時間。理想情況下，依次增加節點時S將與y=x重合。

AHCCF算法選取表1中不同規模的MovieLens數據集來對算法的并行效率進行驗證。設計兩組實驗：相同數據集下AHCCF算法在Hadoop平臺與Spark平臺執行時間對比、不同規模數據集下AHCCF算法的加速比對比。

實驗3 測試在相同數據集下AHCCF算法在Hadoop平臺與Spark平臺上的執行效率。本實驗選取MovieLensB數據集，在Hadoop和Spark兩種計算平臺上實驗，結果如圖9所示。

圖14 Hadoop與Spark平臺運行效率對比

從圖9實驗結果可以看出，隨著節點數量的增加，AHCCF算法在兩種計算平臺上的執行時間逐漸減少。其中，在Spark計算平臺上算法獲得更好的執行效率，表明了AHCCF算法在Spark平臺上更具有優勢，基于Spark的并行方案是有效的。

實驗4 測試不同規模數據集下AHCCF算法加速比隨集群大小的變化情況，集群大小取1～5。偽分布模式下，集群只有一個節點，master和slave為同一節點，集群大小大于等于2時，為完全分布模式，結果如圖10所示。

圖10 不同規模數據集的加速比對比

實驗結果表明，隨著集群節點數量的增加，三個數據集的加速比曲線在不斷增大。相同數據集在節點數量較少時，算法效率提升不是很明顯。這是因為在少量節點時，節點要分擔一定計算任務的同時，也要分擔一定的資源調度等任務，影響節點的計算性能。在節點個數大于3時，算法效率提升的更為明顯。與此同時，可以看出在相同節點情況下，算法效率在規模較大的數據集上提升更為明顯，加速比曲線逐漸向線性靠攏，這也說明了并行化的AHCCF算法在處理大數據集時更有優勢。

4 結 語

AHCCF算法針對傳統協同過濾算法存在的稀疏性以及可擴展性問題展開研究，在基于項目的協同過濾算法基礎上，提出了一種分層的聯合聚類協同過濾算法(AHCCF)，并在Spark平臺下實現了AHCCF算法的并行化。實驗表明，AHCCF算法改善了傳統協同過濾算法的性能，提高了算的推薦精度，并在Spark分布式平臺具有良好的執行效率和可擴展性。下一步研究需要對算法進行嚴格的理論推導，同時研究不同維聚類個數的選取以及在更大規模數據上算法的并行效率。

[1] 郭磊,馬軍,陳竹敏,等.一種結合推薦對象間關聯關系的社會化推薦算法[J].計算機學報,2014,37(1):219-228.

[2]WangJ,VriesAPD,ReindersMJT.Unifyinguser-basedanditem-basedcollaborativefilteringapproachesbysimilarityfusion[C]//Proceedingsofthe29thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.ACM,2006:501-508.

[3] Sarwar B,Karypis G,Konstan J,et al.Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th Internationnal World Wide Web Conference.New York,NY,USA:ACM Press,2001:285-295.

[4] 趙琴琴,魯凱,王斌.SPCF:一種基于內存的傳播式協同過濾推薦算法[J].計算機學報,2013,36(3):671-676.

[5] 何潔月,馬貝.利用社交關系的實值條件受限玻爾茲曼機協同過濾推薦算法[J].計算機學報,2016,39(1):183-195.

[6] Kumar R,Verma B K,Rastogi S S.Social popularity based SVD++ recommender system[J].International Journal of Computer Applications,2014,87(14):33-37.

[7] Wei S,Ye N,Zhang S,et al.Collaborative filtering recommendation algorithm based on item clustering and global similarity[C]//Proceedings of the 5th International Conference on Business Intelligence and Financial Engineering.IEEE,2012:69-72.

[8] Wang J,Song H,Zhou X.A collaborative filtering recommendation algorithm based on biclustering[C]//Cyber Technology in Automation,Control and Intelligent Systems (CYBER),2015 IEEE Internationa Conference on.IEEE,2015:803-807.

[9] Zhao Z D,Shang M S.User-based collaborative filtering recommendation algorithms on Hadoop[C]//Proceedings of the 2010 Third International Conference on Knowledge Discovery and Data Mining,2010:478-481.

[10] Fan L,Li H,Li C.The improvement and implementation of distributed item-based collaborative filtering algorithm on Hadoop[C]//2015 34th Chinese Control Conference (CCC).IEEE,2015:9078-9083.

[11] Lin K,Wang J,Wang M,et al.A hybrid recommendation algorithm based on Hadoop[C]//2014 9thInternational Conference on Computer Sicence and Education,2014:540-543.

[12] Kupisz B,Unold O.Collaborative filtering recommendation algorithm based on Hadoop and Spark[C]//Industrial Technology (ICIT),2015 IEEE International Conference on.IEEE,2015:1510-1514.

[13] 朱銳,王懷民,馮大為.基于偏好推薦的可信服務選擇[J].軟件學報,2011,22(5):852-864.

[14] 吳湖,王永吉,王哲,等.兩階段聯合聚類協同過濾算法[J].軟件學報,2010,21(5):1042-1054.

[15] Ketu S,Agarwal S.Performance enhancement of distributed K-Means clustering for big data analytics through in-memory computation[C]//Contemporary Computing (IC3),2015 Eighth International Conference on.IEEE,2015:318-324.

AN IMPROVED COLLABORATIVE FILTERING ALGORITHM BASED ON SPARK

Xu Zhihong1,2Jiang Xinyu1Dong Yongfeng1,2Zhao Jiawei1

1(SchoolofComputerScienceandEngineering,HebeiUniversityofTechnology,Tianjin300401,China)2(HebeiProvinceKeyLaboratoryofBigDataCalculation,Tianjin300401,China)

In order to improve the scalability of collaborative filtering algorithm in big data environment and the recommendation accuracy in high dimensional sparse data, a hierarchical co-clustering collaborative filtering algorithm based on spark is implemented. The data sets are sparsely processed by using co-clustering and the clustering model is constructed. The potential categories weight of users and projects in the co-clustering model are analyzed by using the analytic hierarchy model combined with the score-density analysis. The project similarity is calculated and the project nearest neighbor set is constructed to complete the online recommendation. The experiments different scale MovieLens datasets provided by GroupLens show that the improved algorithm can significantly improve the accuracy of recommendation, and it has good recommendation efficiency and expansibility in distributed environment.

Collaborative filtering Co-clustering Analytic hierarchy model Spark

2016-04-07。天津市科技計劃項目(14ZCDGSF00124)；河北省青年科學基金項目(F2015202311)。許智宏，副教授，主研領域：分布式技術，智能信息處理。蔣新宇，碩士。董永峰，副教授。趙嘉偉，碩士。

TP3

A

10.3969/j.issn.1000-386x.2017.05.043