基于Hadoop的推薦算法研究

孫亭　賈元江　張永勝　侯秀艷　于鑫

摘 要：本文通過對(duì)云計(jì)算和推薦系統(tǒng)的研究，構(gòu)建了一種基于Hadoop平臺(tái)的混合推薦算法。文中介紹了改進(jìn)的混合推進(jìn)算法，并結(jié)合Hadoop平臺(tái)的MapReduce編程模型來實(shí)現(xiàn)。通過實(shí)驗(yàn)驗(yàn)證，該算法能精確的預(yù)測用戶的偏好，向用戶推薦感興趣的信息。其次，Hadoop能滿足對(duì)大量數(shù)據(jù)處理的要求，結(jié)合改進(jìn)的混合推薦算法，能夠大大提高推薦系統(tǒng)的性能。

關(guān)鍵詞：云計(jì)算；推薦算法；混合推薦算法

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract：In this paper，through studying the recommendation system and cloud computation，we established the hybrid recommendation algorithm based on Hadoop.In this paper，we introduces a improved hybrid recommended algorithm and combine MapReduce programming which is used on Hadoop platform.Through practices，the improved algorithm can accurately acquiring user preferences， provide the user with recommendation when the user browse the web page.Finally Hadoop can meet the demand of massive data processing，and achieve a highly performance system by making use of the data reprocessing method.

Keywords：cloud computing；recommended algorithm；hybrid algorithm

1 引言（Introduction）

隨著互聯(lián)網(wǎng)的迅速發(fā)展和Web2.0技術(shù)的普及，網(wǎng)絡(luò)中的信息量急劇上升，從海量的數(shù)據(jù)中快速找到用戶感興趣或?qū)ζ溆袃r(jià)值的信息，無論對(duì)于消費(fèi)者還是商家來說都是十分重要的，而推薦系統(tǒng)就是一個(gè)非常有效的工具。作為一項(xiàng)廣泛應(yīng)用的機(jī)器學(xué)習(xí)技術(shù)，推薦系統(tǒng)通過了解用戶的歷史行為推斷用戶的喜好，向用戶推薦其感興趣的書、電影、文章等未知項(xiàng)目。如今很多網(wǎng)站都提供了推薦服務(wù)，例如：新浪微博、優(yōu)酷、Amazon、Youtube等。

與搜索引擎不同，推薦系統(tǒng)不需要用戶提供明確的搜索要求，而是通過對(duì)用戶歷史行為的記錄分析去挖掘其興趣，從而主動(dòng)的向用戶推薦符合他們興趣和要求的信息[1]。因此，推薦系統(tǒng)需要大量的數(shù)據(jù)為前提，云計(jì)算可以很好地解決大容量數(shù)據(jù)存儲(chǔ)的問題。

Hadoop平臺(tái)是Apache分布式計(jì)算編程系統(tǒng)下的一個(gè)開放資源，是目前使用最廣泛的云計(jì)算平臺(tái)[2]，它主要包含兩大方面：分布式文件系統(tǒng)HDFS和分布式計(jì)算模型MapReduce[3]。由于Hadoop平臺(tái)具有成本低、效率高等優(yōu)勢(shì)，基于Hadoop平臺(tái)的應(yīng)用已經(jīng)在互聯(lián)網(wǎng)領(lǐng)域迅速發(fā)展[4]。本文設(shè)計(jì)并實(shí)現(xiàn)了一種基于MapReduce編程模型的混合推薦算法并將其應(yīng)用到推薦系統(tǒng)中。

2 系統(tǒng)架構(gòu)設(shè)計(jì)（Architecture design of system）

2.1 Hadoop平臺(tái)

Hadoop分布式系統(tǒng)的基礎(chǔ)框架由HDFS、MapReduce和HBase組成。其中，HDFS是Hadoop軟件框架中的分布式文件系統(tǒng)，MapReduce是用于大規(guī)模數(shù)據(jù)處理的分布式計(jì)算模型，HBase是一個(gè)高可靠性、高性能、面向列、可伸縮的分布式存儲(chǔ)系統(tǒng)[5]。Hadoop分布式系統(tǒng)的主要結(jié)構(gòu)如圖1所示。

如圖1所示，DataNode節(jié)點(diǎn)主要負(fù)責(zé)對(duì)Hadoop分布式文件系統(tǒng)的數(shù)據(jù)進(jìn)行存儲(chǔ)，NameNode節(jié)點(diǎn)主要負(fù)責(zé)管理Hadoop文件系統(tǒng)的命名空間，并控制外部用戶對(duì)文件系統(tǒng)的訪問[6]。總之，Hadoop分布式文件系統(tǒng)是一個(gè)真實(shí)可靠的分布式文件存儲(chǔ)系統(tǒng)，用戶可以在其中存儲(chǔ)他們的信息數(shù)據(jù)。

2.2 推薦系統(tǒng)的體系結(jié)構(gòu)

推薦系統(tǒng)主要包括三個(gè)部分：用戶、推薦算法和推薦對(duì)象。推薦算法是推薦系統(tǒng)的核心。隨著互聯(lián)網(wǎng)的發(fā)展，推薦系統(tǒng)已經(jīng)被應(yīng)用到很多領(lǐng)域，它具有比搜索引擎更高的用戶體驗(yàn)，推薦系統(tǒng)結(jié)合了搜索引擎的優(yōu)勢(shì)發(fā)現(xiàn)用戶的歷史搜索并對(duì)結(jié)果進(jìn)行排序，根據(jù)用戶的歷史行為收集用戶的偏好數(shù)據(jù)并向用戶推薦其感興趣的內(nèi)容。一般推薦系統(tǒng)的架構(gòu)如圖2所示。

2.3 基于用戶的協(xié)同過濾推薦算法

基于用戶的協(xié)同過濾推薦算法的基本原理是通過收集用戶的歷史行為，根據(jù)用戶之間的相似性進(jìn)行推薦，具體過程[8]詳見表1。

2.4 基于項(xiàng)目的推薦算法

基于項(xiàng)目的推薦是從項(xiàng)目之間的相似性中得出的，它與基于用戶的推薦類似，具體過程[9]詳見表2。

基于項(xiàng)目的推薦算法與基于用戶的推薦算法類似，但不完全相同。兩者之間最顯著的差異在于：基于項(xiàng)目的推薦算法的時(shí)間復(fù)雜度主要取決于項(xiàng)目的數(shù)量，而基于用戶的推薦算法的時(shí)間復(fù)雜度主要取決于用戶的數(shù)量[10]。

3 混合推薦算法的設(shè)計(jì)（Design of hybrid recommendation algorithm）

通過對(duì)基于用戶的協(xié)同過濾推薦算法和基于項(xiàng)目的推薦算法的比較發(fā)現(xiàn)，單純使用一種推薦方法很難滿足大數(shù)據(jù)量和高準(zhǔn)確度的要求。混合推薦算法組合這兩種不同的推薦算法并搭載hadoop平臺(tái)。

如圖3所示，混合推薦算法的基本思想是將基于用戶的協(xié)同過濾推薦算法和基于項(xiàng)目的推薦算法相結(jié)合使用。首先，采用基于項(xiàng)目推薦算法來預(yù)測用戶對(duì)目標(biāo)項(xiàng)目的評(píng)分。然后根據(jù)預(yù)測填補(bǔ)基于用戶的協(xié)同過濾中的稀疏矩陣，主要是填補(bǔ)矩陣中缺失的數(shù)據(jù)。這樣就有效地解決了協(xié)同過濾算法中的數(shù)據(jù)稀疏問題。

本文中混合推薦算法是結(jié)合MapReduce編程模型實(shí)現(xiàn)的，MapReduce被用于分布式計(jì)算，輸入和輸出采用鍵—值對(duì)的形式。我們使用三組MapReduce計(jì)算最終得分以此得到推薦項(xiàng)目名單，詳見表3。

該算法共進(jìn)行了三組MapReduce，每一個(gè)過程是MapReduce并行執(zhí)行的一個(gè)周期。與傳統(tǒng)的協(xié)同過濾算法相比，雖然形式大致相同，但加入的混合推薦技術(shù)顯著提高了推薦的準(zhǔn)確性，并能在大型集群環(huán)境中運(yùn)行。

4 實(shí)驗(yàn)和評(píng)估（Experimentation and evaluation）

MAE絕對(duì)偏差公式表示實(shí)際值與預(yù)測值之間平均絕對(duì)偏差。通過MAE可以在評(píng)估推薦算法的質(zhì)量。

從圖6中可以看出，混合推薦算法的MAE值基本穩(wěn)定在0.63，與其兩種推薦算法的MAE值相比較，混合推薦算法可以有效地提高推薦系統(tǒng)的推薦質(zhì)量。

圖7顯示的是隨著輸入數(shù)據(jù)的增加算法響應(yīng)時(shí)間的變化情況。在實(shí)驗(yàn)過程中，輸入用戶數(shù)量從100k到1M被劃分為10等份，可見，發(fā)現(xiàn)算法的執(zhí)行時(shí)間隨著用戶數(shù)量的增加緩慢增加，并且該算法的效率隨著數(shù)據(jù)規(guī)模的增大而提高。上文提到的Hadoop云平臺(tái)處理海量數(shù)據(jù)時(shí)優(yōu)勢(shì)明顯。為了確保實(shí)驗(yàn)準(zhǔn)確順利完成，Hadoop能夠動(dòng)態(tài)地處理數(shù)據(jù)冗余及存儲(chǔ)節(jié)點(diǎn)，以此提高數(shù)據(jù)的處理速度和計(jì)算效率。當(dāng)數(shù)據(jù)量較小時(shí)，算法消耗時(shí)間增長的幅度較快；隨著數(shù)據(jù)規(guī)模的增大，算法消耗時(shí)間的增幅可逐漸被忽略。

圖8顯示的是，在偽分布式環(huán)境中，混合算法響應(yīng)時(shí)間隨機(jī)器數(shù)量增加的變化情況。可以看出，隨著節(jié)點(diǎn)數(shù)量的增加，響應(yīng)時(shí)間顯著降低，達(dá)到兩臺(tái)機(jī)器后，響應(yīng)時(shí)間繼續(xù)降低，但降低的幅度減小。這是因?yàn)樵趥畏植际江h(huán)境，利用單一的PC同時(shí)作為主節(jié)點(diǎn)和從屬節(jié)點(diǎn)時(shí)存在計(jì)算量大的問題，而利用兩臺(tái)PC充分體現(xiàn)了分布式環(huán)境的優(yōu)勢(shì)，可以更好地解決這個(gè)問題。通過實(shí)驗(yàn)的曲線變化趨勢(shì)我們可以得出，Hadoop的分布式計(jì)算環(huán)境顯著提高了算法的性能。同時(shí)我們還可以發(fā)現(xiàn)，從一臺(tái)PC到多臺(tái)PC算法的性能變化更加明顯，這都?xì)w功于分布式計(jì)算。因此Hadoop集群環(huán)境可以使分布式計(jì)算取得顯著效果。

5 結(jié)論（Conclusion）

當(dāng)今云計(jì)算已成為學(xué)術(shù)界關(guān)注的焦點(diǎn)，它是未來計(jì)算機(jī)研究的主要方向。隨著云計(jì)算技術(shù)在各個(gè)領(lǐng)域的成熟發(fā)展，云計(jì)算平臺(tái)的優(yōu)勢(shì)越來越明顯，應(yīng)用也越來越廣泛。開源平臺(tái)，如Hadoop，已成為現(xiàn)在的最理想的數(shù)據(jù)處理平臺(tái)，學(xué)術(shù)界越來越重視對(duì)Hadoop的研究，Hadoop已成為云平臺(tái)的典型代表。

通過對(duì)Hadoop架構(gòu)特點(diǎn)的學(xué)習(xí)與研究，我們將開發(fā)一個(gè)基于Hadoop平臺(tái)的推薦系統(tǒng)，充分利用Hadoop平臺(tái)的優(yōu)勢(shì)，為用戶提供良好的推薦服務(wù)。同時(shí)在推薦系統(tǒng)的設(shè)計(jì)中，我們?cè)O(shè)計(jì)了一種混合推薦算法，通過與其他不同推薦算法的比較，驗(yàn)證了基于MapReduce的混合推薦算法的優(yōu)勢(shì)。

但是，本文系統(tǒng)也有存在的缺陷，實(shí)驗(yàn)僅利用的集群環(huán)境中僅有三臺(tái)PC，將來我們會(huì)考慮增加更多的機(jī)器。另外，實(shí)驗(yàn)數(shù)據(jù)直接保存在分布式文件系統(tǒng)HDFS，沒有仔細(xì)考慮輸入數(shù)據(jù)的形式，也沒有在用戶界面上做出太多的設(shè)計(jì)，所以用戶體驗(yàn)度不高。如何解決這些問題，將是今后重點(diǎn)研究的問題。

參考文獻(xiàn)（References）

[1] 項(xiàng)亮.推薦系統(tǒng)實(shí)踐[M].北京：人民郵電出版社，2012.

[2] Jeffrey Dean，Sanjay Ghemawat.MapReduce：simplified data processing on large clusters[J].Commun.2008，51（1）：107-113.

[3] Sean Owen，Robin Anil，Ted Dunning，Ellen Friedman.Mahoutin Action.Manning Publications[M].2010，11：12-108.

[4] Badrul Sarwar，George Karypis，Joseph Konstan，et al.Analysis of Recommendation Algorithms for E-Commerce[C].Proceedings of EC'00，2000：158-167.

[5] 孫少陵，羅治國，徐萌.云計(jì)算及應(yīng)用的研究與實(shí)現(xiàn)[J].電信工程技術(shù)與標(biāo)準(zhǔn)化，2009（11）：2-7.

[6] 吳吉義，傅建慶，平玲娣.一種對(duì)等的云存儲(chǔ)系統(tǒng)研究[J].電子學(xué)報(bào).2011，39（5）：1100-1107.

[7] R.D.Lawrence，G.S.Almasi，V.Kotlyar.Personalization ofSupermarket Product Recommendations[J].Data Mining and Knowledge Discovery.2001，5（1）：11-32.

[8] Wei-Po Lee，Chih-Hung Liu，Cheng-Che Lu.IntelligentAgent-Based Systems for Personalized Recommendations[J].Expert Systems with Applications.2002，22（2）：275-284.

[9] 鄧愛林，朱揚(yáng)勇，施伯樂.基于項(xiàng)目評(píng)分預(yù)測的協(xié)同過濾推薦算法[J].軟件學(xué)報(bào)，2003，14（9）：1621-1628.

[10] 孫遠(yuǎn)帥，陳垚，劉向榮.基于項(xiàng)目層次相似性的推薦算法[J].山東大學(xué)學(xué)報(bào)，2014，44（3）：8-14.

作者簡介：

孫 亭（1989-），女，碩士生.研究領(lǐng)域：軟件工程.

賈元江（1968-），男，學(xué)士.高級(jí)工程師.研究領(lǐng)域：計(jì)算機(jī)應(yīng)用.

張永勝（1962-），男，碩士，教授，碩士生導(dǎo)師.研究領(lǐng)域：數(shù)據(jù)庫技術(shù)，網(wǎng)絡(luò)信息安全.

侯秀艷（1990-），女，碩士生.研究領(lǐng)域：信息安全.

于 鑫（1994-），女，學(xué)士生.研究領(lǐng)域：通信工程.