基于Hadoop平臺的優化協同過濾推薦算法研究

申晉祥，鮑美英

?

基于Hadoop平臺的優化協同過濾推薦算法研究

申晉祥，鮑美英

（山西大同大學計算機與網絡工程學院，山西 大同 037009）

針對協同過濾推薦算法在大數據環境下存在的數據稀疏性和可擴展性問題，在分析研究Hadoop分布式平臺與協同過濾推薦算法后，本文提出一種基于Hadoop平臺的優化協同過濾推薦算法。該推薦算法將相似度高的用戶或項目聚為一類，再設計用戶和項目矩陣，以更有效的獲得各自的最近鄰居集，采用加權系數處理兩者的預測評分，并對設計矩陣完成MapReduce并行化實現，這種加權系數處理后的推薦架構，很好的緩和了數據稀疏性且提高了預測精度。實驗驗證該算法能有效提高推薦系統的推薦效率，同時獲得良好的可擴展性。

協同過濾推薦算法；Hadoop；數據稀疏性；擴展性

0 引言

隨著互聯網的迅速發展，人們將會面對海量數據信息，大量的網絡信息在給人們帶來方便的同時，信息過載問題也會越來越突顯[1-2]。如何在海量信息中獲得自己想要的內容是目前急待解決的問題。作為信息過濾的重要手段，推薦技術[3-4]是完成這一任務的有效方法，其中推薦算法是整個推薦系統中最核心、最關鍵的部分，而協同過濾推薦CFR（Collaborative filtering recommendation）是推薦算法中最為廣泛，也是最成功的方法之一，同時也是目前研究的熱點問題[5]。Hadoop作為一個分布式和可并行處理大規模數據的云計算平臺，給推薦系統提供了很好的解決方案[6-7]。Hadoop充分利用集群進行計算[8]，有利于處理海量數據，也是對傳統單機模式的補益。

大數據時代的到來，使網絡中的信息、用戶以及推薦對象的數量都會海量涌現，海量數據的存儲和計算的快慢將起到決定性作用。傳統模式的協同過濾算法將越來越難滿足海量數據的運算需求，因此優化協同過濾推薦算法將是一個新的研究方向。近年來有一些高效的協同過濾推薦研究，比如Pan R[9]等人提出的基于ALS（Alternating Least Squares）的協同過濾算法。Jeong B[10]等人提出基于融合的方法對預測評分數據進行填補，來緩和數據稀疏性。鄧[11]等人基于項目屬性研究進行評分，依據項目間的關聯度最終產生推薦對象，很好的改善了數據稀疏性問題。

針對協同過濾推薦算法在大數據環境下存在的數據稀疏性和可擴展性問題，本文提出一種基于Hadoop平臺的優化協同過濾推薦算法。該推薦算法綜合考慮了基于用戶（User-based）的協同過濾算法的預測評分和基于項目（Item-based）的協同過濾算法的預測評分，構建User和Item矩陣，有效的獲得各自的最近鄰居集，采用加權系數處理兩者的預測評分，這種推薦架構，很好的緩和了數據稀疏性且提高了預測精度，同時獲得良好的可擴展性。

1 基于Hadoop平臺的優化協同過濾推薦算法

1.1 算法流程

本文所提出的優化協同過濾算法是一種基于用戶和項目的綜合考慮的協同過濾算法架構，主要完成聚類模塊、User和Item矩陣構建模塊、最近鄰居查找模塊、預測評分處理模塊，流程如圖1所示。

圖1 優化協同過濾算法流程

結合以上流程可知，該算法同時考慮了用戶和項目兩方面信息，在一定程度上緩和數據稀疏性問題。設計User矩陣和Item矩陣，更好的找到最近鄰居集，提高推薦的準確性。綜合考慮使系統的多樣性（即推薦對象的覆蓋率）更好，同時也可較好的應對冷啟動問題。

1.2 算法設計

該算法從用戶的評分信息中展開數據挖掘，選取目標User（或Item）相似度最高的最近鄰居，從中預測評分然后產生推薦。

聚類設計，我們知道K-means算法存在K值不好確定以及聚類結果不穩定的問題。本文所提算法分別對用戶和項目進行聚類，將偏好相近的用戶或項目聚為一類，再從中選出鄰居用戶集和鄰居項目集，進行偏好度預測，提供推薦。基于用戶聚類如表1所示。基于項目聚類如表2所示。

表1 基于用戶聚類的示例

Tab.1 Examples based on user clustering

表2 基于項目聚類的示例

Tab.2 Examples based on item clustering

表中U（即User）表示用戶，I（即Item）表示項目，Rating表示用戶對項目的評分，表1根據所有用戶對Item的Rating，對這些用戶進行聚類操作，將Rating相似的用戶聚為一類。表2根據當前User對Item的Rating，對這些Item進行聚類操作，將Rating相似的項目聚為一類。

User和Item矩陣設計，User矩陣如表3所示，根據每一Item中User的聚類情況，計算兩兩User相聚一類的次數。Item矩陣如表4所示，根據每一User中Item的聚類情況，計算兩兩Item相聚一類的次數。次數越多表示他們之間的關系度越大。

最近鄰居集的形成，本算法采取預定值法，預先取一個適當的K值，將相似度排前K位的對象作為最近鄰居集合。對于User矩陣而言，行表示即定用戶，列表示對應的鄰居用戶，值即為兩兩相聚一次的結果用CR計數，CR的值越大表示之間的偏好越相似。然后對CR進行排序，取前K個作為即定用戶的最近鄰居集Neighbors（user）。如表3的User矩陣中，對即定用戶U1取前3個相似度最大的最近鄰居集為{U3，U6，U2}。對于Item矩陣同理求得最近鄰居集Neighbors(item)。

表3 User矩陣的示例

Tab.3 Examples of the User matrix

表4 Item矩陣的示例

Tab.4 Examples of the Item matrix

評分預測及加權系數處理，本算法計算相似度的方法采用Pearson相關系數。基于用戶的協同過濾算法的預測評分如公式（1）和公式（2）所示。

基于項目的協同過濾算法的預測評分如公式（3）和公式（4）所示。

以上公式中，用U表示是同時對項目和共同評過分的用戶集合，用r和r分別表示用戶對項目和的評分，用r和r上加一橫線分別表示所有用戶對項目和的評分均值，用r和r上加一橫線分別表示用戶和用戶對項目的評分均值，用I表示用戶和同時評過分的項目集合，用N和N分別表示項目和用戶的最近鄰居集。

本文采用系數C（Coefficient，C）對基于用戶和基于項目的兩種計算得出的預測評分進行加權處理，如公式（5）所示。

P(,)=CP(,)+(1-)P(,) （5）

將最終得出的評分預測值排前K位的項目作為推薦結果。

1.3 優化算法的MapReduce并行化實現

MapReduce是Google提出的一個軟件編程框架，用于大規模數據集的并行運算。對算法進行并行化實現主要是對User和Item矩陣設計部分進行實現，使其更利于大數據量的處理。MapReduce并行化實現過程中相關的數據存放在Hadoop平臺下對稀疏性數據有良好支持的HBase分布式開源數據庫中。具體涉及User矩陣并行化和Item矩陣并行化兩項工作。

User矩陣并行化主要包括一個Map和一個Reduce操作過程。Map過程如下：

（1）Map(key,value){//value:將HBase中的用戶偏好模型表uim作為Map的輸入；

（2）user+item=value.getRow()

rating=value.getValue(data:rating)

fu=value.getValue(data:fu)

//得到user、item和fu（基于用戶聚類時的標記）的信息；

（3）Outputkeyvalue(item+fu,user)

//輸出形式為；

（4）Combine(key,values){

For each value1 in values

For each value2 in values

IF(value1.user!=value2.user)

Outputkeyvalue(value1.user+

value2.user,1)

End IF

End For

End For

}//在這里Combiner得到的輸入形式為>，把每個得到List的用戶按照ArrayList一種形式進行存儲，經過遍歷以后，把不同的兩兩用戶以一種形式輸出；

Reduce過程如下：

(1) Reduce(key,values){

For each value in values

CR+=value

End For //輸入是通過Shuffle過程得到的>，對List中的1相加，得到兩兩用戶相聚一類的次數；

(2) Store(key,CR) into table userMatrix

//存入HBase的user矩陣表userMatrix中；

Item矩陣并行化過程同理。

2 實驗結果與分析

2.1 實驗數據集

本實驗采用GroupLens提供的MovieLens電影評分數據集，相關數據有用戶特征信息、電影屬性信息、用戶對項目的評分信息等，用戶對項目的評分值是從1到5的整數，實驗采用1MB的數據集，其中包括6040個用戶對3900部電影的1000209條評分記錄。

2.2 實驗評估標準

本實驗通過平均絕對偏差（MAE）和均方根誤差（RMSE）計算評分預測的準確度，MAE是算法計算得出的預測評分值和用戶對項目的實際評分值之間的偏差，RMSE是計算預測評分與真實評分之間的偏差的均方根值。MAE值和RMSE值越小，說明預測值和真實值之間的誤差越小，預測的準確度越高。用N表示實驗測試項目數，Pi表示預測評分值，Ri表示實際評分值，MAE和RMSE的計算如公式（5）和公式（6）所示。

2.3 實驗結果

（1）最近鄰數的影響

將本文提出的優化協同過濾推薦算法（OCFRA）和采用K-means算法實現基于用戶和項目雙重聚類的協同過濾算法（KCFRA）、基于用戶聚類的協同過濾算法（UCFRA）、基于項目聚類的協同過濾算法（ICFRA）進行對照，驗證最近鄰數對MAE和RMSE的影響。實驗結果如圖2和圖3所示。

圖2 最近鄰數對MAE值的影響

圖3 最近鄰數對RMSE值的影響

實驗結果可以看出，隨著最近鄰數的增加，各種算法的MAE值和RMSE值都在減少，本優化算法相比其它算法要更小，有更好的推薦效果。

（2）矩陣密度的影響

將本文提出的優化協同過濾推薦算法（OCFRA）和采用K-means算法實現基于用戶和項目雙重聚類的協同過濾算法（KCFRA）進行對照，驗證不同的矩陣密度對MAE和RMSE的影響。實驗結果如圖4和圖5所示。

圖4 矩陣密度對MAE值的影響

圖5 矩陣密度對RMSE值的影響

實驗結果可以看出，隨著矩陣密度的不斷增大，各種算法的MAE值和RMSE值都會受到影響而下降，本優化算法在不同矩陣密度下效果最好，有更高的預測準確度。

3 結論

本文針對協同過濾推薦算法在大數據環境下存在的數據稀疏性和可擴展性問題，結合Hadoop分布式計算的特點以及目前已有的研究現狀，提出了一種基于Hadoop平臺的優化協同過濾推薦算法。該算法對用戶和項目的聚類再進一步設計User矩陣和Item矩陣，并完成MapReduce并行化實現，最后加權系數處理預測評分。通過實驗驗證了該推薦算法的優勢，良好的改善了數據稀疏性和可擴展性，為用戶提供更加準確和優質的推薦對象。

[1] Duan Miao. Collaborative filtering recommendation algorithm[J]. International Journal of Security & Its Applications, 2015, 9(7): 99-108.

[2] 翁小蘭, 王志堅. 協同過濾推薦算法研究進展[J]. 計算機工程與應用, 2018, 54(1): 25-31.

[3] Luo Qi, Miu Xin-jie, Wei Qian. Further research on collaborative filtering algorithm for sparse data[J]. Computer Science, 2014, 41(6): 264-268.

[4] 彭石, 周志彬, 王國軍. 基于評分矩陣預填充的協同過濾算法[J]. 計算機工程, 2013, 39(1): 175-182.

[5] 孫輝, 馬躍, 楊海波. 一種相似度改進的用戶聚類協同過濾算法[J]. 小型微型計算機系統, 2014, 35(9): 1967-1970.

[6] Manolis G, Vozalis, Angelos M, et al. Collaborative filtering through SVD-based and hierarchical nonlinear PCA[J]. Artificial Neural Networks ICANN, 2010, 6 396-399.

[7] 黃震華, 張佳雯, 田春岐, 等. 基于排序學習的推薦算法研究綜述[J]. 軟件學報, 2016, 27(3): 693-708.

[8] KYONG-HA LEE. Parallel Data Processing With MapReduce: A Survey[J]. SIGMOD Record, 2011, 40(4): 15-19.

[9] Pan R, Zhou Y, Cao B, et al. One-class collaborative filtering[C]//Proceedings of the Eighth IEEE International Conference on Data Mining, 2008: 505-510.

[10] Jeong B, Lee J, Cho H. An iterative semi-explicit rating method for building collaborative recommender systems[J]. Expert Systems with Applications, 2009, 36(3): 6182-6185.

[11] Deng Ai-lin, Zuo Zi-ye, Zhu Yang-yong. Collaborative filtering recommendation algorithm based on item clustering[J]. Journal of Chinese Computer Systems, 2004, 25(9): 1666- 1765. (in Chinese).

Research on Optimized Collaborative Filtering Recommendation Algorithm Based on Hadoop Platform

SHEN Jin-xiang, BAO Mei-ying

(College of Computer and Network Engineering, Shanxi Datong University, Datong Shanxi 037009, China)

In order to solve the problem of data sparsity and scalability in big data environment, a collaborative filtering recommendation algorithm based on Hadoop platform is proposed in this paper after analyzing and researching the Hadoop distributed platform and collaborative filtering recommendation. The recommendation algorithm can aggregate users or projects with high similarity into one class, then designs users and project matrices to get their nearest neighbors more effectively. The weighted scores are used to deal with the prediction scores, and the design matrix is parallelized by MapReduce. The recommended architecture of this weighting coefficient has greatly alleviated the sparsity of data and improved the prediction accuracy. Experiments show that the proposed algorithm can effectively improve the recommendation efficiency of the recommendation system and obtain good scalability.

Collaborative filtering recommendation algorithm; Hadoop; Data sparsity; Scalability

TP391

A

10.3969/j.issn.1003-6970.2018.12.001

國家自然科學基金項目（11871314）；山西省青年科技基金（2015021101）；山西大同大學校級科研項目（2017K7）

申晉祥（1977-），男，講師，碩士，主要研究方向：大數據，云計算。鮑美英（1975-），女，副教授，碩士，主要研究方向：網格計算，云計算。

申晉祥，鮑美英. 基于Hadoop平臺的優化協同過濾推薦算法研究[J]. 軟件，2018，39（12）：01-05