申晉祥，鮑美英

?

基于Hadoop平臺的優(yōu)化協(xié)同過濾推薦算法研究

申晉祥，鮑美英

（山西大同大學(xué)計算機與網(wǎng)絡(luò)工程學(xué)院，山西 大同 037009）

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

協(xié)同過濾推薦算法；Hadoop；數(shù)據(jù)稀疏性；擴展性

0 引言

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

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

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

1 基于Hadoop平臺的優(yōu)化協(xié)同過濾推薦算法

1.1 算法流程

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

圖1 優(yōu)化協(xié)同過濾算法流程

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

1.2 算法設(shè)計

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

聚類設(shè)計，我們知道K-means算法存在K值不好確定以及聚類結(jié)果不穩(wěn)定的問題。本文所提算法分別對用戶和項目進行聚類，將偏好相近的用戶或項目聚為一類，再從中選出鄰居用戶集和鄰居項目集，進行偏好度預(yù)測，提供推薦?；谟脩艟垲惾绫?所示?；陧椖烤垲惾绫?所示。

表1 基于用戶聚類的示例

Tab.1 Examples based on user clustering

表2 基于項目聚類的示例

Tab.2 Examples based on item clustering

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

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

最近鄰居集的形成，本算法采取預(yù)定值法，預(yù)先取一個適當(dāng)?shù)腒值，將相似度排前K位的對象作為最近鄰居集合。對于User矩陣而言，行表示即定用戶，列表示對應(yīng)的鄰居用戶，值即為兩兩相聚一次的結(jié)果用CR計數(shù)，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

評分預(yù)測及加權(quán)系數(shù)處理，本算法計算相似度的方法采用Pearson相關(guān)系數(shù)?；谟脩舻膮f(xié)同過濾算法的預(yù)測評分如公式（1）和公式（2）所示。

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

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

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

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

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

1.3 優(yōu)化算法的MapReduce并行化實現(xiàn)

MapReduce是Google提出的一個軟件編程框架，用于大規(guī)模數(shù)據(jù)集的并行運算。對算法進行并行化實現(xiàn)主要是對User和Item矩陣設(shè)計部分進行實現(xiàn)，使其更利于大數(shù)據(jù)量的處理。MapReduce并行化實現(xiàn)過程中相關(guān)的數(shù)據(jù)存放在Hadoop平臺下對稀疏性數(shù)據(jù)有良好支持的HBase分布式開源數(shù)據(jù)庫中。具體涉及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一種形式進行存儲，經(jīng)過遍歷以后，把不同的兩兩用戶以一種形式輸出；

Reduce過程如下：

(1) Reduce(key,values){

For each value in values

CR+=value

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

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

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

Item矩陣并行化過程同理。

2 實驗結(jié)果與分析

2.1 實驗數(shù)據(jù)集

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

2.2 實驗評估標準

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

2.3 實驗結(jié)果

（1）最近鄰數(shù)的影響

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

圖2 最近鄰數(shù)對MAE值的影響

圖3 最近鄰數(shù)對RMSE值的影響

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

（2）矩陣密度的影響

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

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

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

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

3 結(jié)論

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

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

[2] 翁小蘭, 王志堅. 協(xié)同過濾推薦算法研究進展[J]. 計算機工程與應(yīng)用, 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] 彭石, 周志彬, 王國軍. 基于評分矩陣預(yù)填充的協(xié)同過濾算法[J]. 計算機工程, 2013, 39(1): 175-182.

[5] 孫輝, 馬躍, 楊海波. 一種相似度改進的用戶聚類協(xié)同過濾算法[J]. 小型微型計算機系統(tǒng), 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] 黃震華, 張佳雯, 田春岐, 等. 基于排序?qū)W習(xí)的推薦算法研究綜述[J]. 軟件學(xué)報, 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

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

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

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