南　磊

(1.江蘇省信息中心　南京　210013)(2.計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué))　南京　210023)

基于Hadoop的圖書推薦系統(tǒng)研究與設(shè)計(jì)

南磊1,2

(1.江蘇省信息中心南京210013)(2.計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué))南京210023)

摘要經(jīng)過近些年的發(fā)展,圖書市場(chǎng)在種類規(guī)模和總體數(shù)量等方面有了長(zhǎng)足的進(jìn)步。但是同時(shí)也帶來了圖書過多,使得讀者難以選擇合適圖書的困難。常規(guī)的明細(xì)分類使得讀者可以針對(duì)每一種類型的書進(jìn)行選擇,但是其每個(gè)分類下依然有成千上萬中書籍。論文完成的是一種基于Apriori算法創(chuàng)建關(guān)聯(lián)規(guī)則的圖書推薦在Hadoop上的實(shí)現(xiàn)。利用在豆瓣讀書上獲取的圖書評(píng)論數(shù)據(jù),使用Hadoop生成圖書的K-頻繁集,并計(jì)算相關(guān)的圖書推薦置信度。論文實(shí)現(xiàn)的算法能夠高效地為讀者提供推薦服務(wù)。

關(guān)鍵詞MapReduce; 并行計(jì)算; 關(guān)聯(lián)規(guī)則; 圖書推薦; Hadoop

Class NumberTP311

1引言

近幾年,由于多終端接入網(wǎng)絡(luò)的便利性,越來越多的讀者開始利用因特網(wǎng)來記錄自己對(duì)各種事務(wù)的評(píng)價(jià),這就形成了針對(duì)不同商品的龐大的評(píng)論數(shù)據(jù)集。其中圖書的種類繁多,內(nèi)容相對(duì)于小商品、電影、音樂等需要比較長(zhǎng)的時(shí)間才可以被讀者體會(huì),利用其他讀者對(duì)不同書籍的評(píng)價(jià)和感興趣程度為其他讀者提供閱讀推薦成為推廣文化和擴(kuò)大書籍銷售的一種重要手段。

傳統(tǒng)上要實(shí)現(xiàn)這樣的推薦系統(tǒng)可以采用Apriori算法[2]。這個(gè)算法基于關(guān)聯(lián)規(guī)則,挖掘出數(shù)據(jù)集中有較大聯(lián)系的數(shù)據(jù)項(xiàng)。并以此作為依據(jù)給讀者推薦其可能感興趣的書籍。但Apriori算法存在一個(gè)問題,就是它需要不斷地去掃描整個(gè)數(shù)據(jù)庫(kù),效率很低。在面對(duì)一些訪問量較大的網(wǎng)站時(shí),客戶的數(shù)量和其留下的有用信息都是以百萬的數(shù)量級(jí)來表示的,在面對(duì)這種海量數(shù)據(jù)時(shí)Apriori算法在單機(jī)上的運(yùn)行比較慢,并且可能超出了普通主機(jī)、大型機(jī)的性能限制?；谝陨舷敕?我們采用了基于MapReduce的方法[1],用并行優(yōu)化后的算法來進(jìn)行處理,期望以一種可以接受的成本快速地實(shí)現(xiàn)Apriori算法在圖書推薦上的應(yīng)用。

2相關(guān)技術(shù)

2.1網(wǎng)絡(luò)爬蟲

網(wǎng)絡(luò)爬蟲是捜索引擎抓取系統(tǒng)的重要組成部分。爬蟲的主要目的是將互聯(lián)網(wǎng)上的網(wǎng)頁(yè)下載到本地形成一個(gè)或聯(lián)網(wǎng)內(nèi)容的鏡像備份[7]。

2.1.1網(wǎng)絡(luò)爬蟲的基本結(jié)構(gòu)及工作流程

一個(gè)通用的網(wǎng)絡(luò)爬蟲的框架如圖1所示。

圖1　網(wǎng)絡(luò)爬蟲基本原理圖

網(wǎng)絡(luò)爬蟲的基本工作流程如下:

1) 首先選取一部分精心挑選的種子URL;

2) 將這些URL放入待抓取URL隊(duì)列;

3) 從待抓取URL隊(duì)列中取出待抓取在URL,解析DNS,并且得到主機(jī)的IP,并將URL對(duì)應(yīng)的網(wǎng)頁(yè)下載下來,存儲(chǔ)進(jìn)已下載網(wǎng)頁(yè)庫(kù)中。此外,將這些URL放進(jìn)已抓取URL隊(duì)列;

4) 分析已抓取URL隊(duì)列中的URL,分析其中的其他URL,并且將URL放入待抓取URL隊(duì)列,從而進(jìn)入下一個(gè)循環(huán)。

2.1.2抓取策略

在爬蟲系統(tǒng)中,待抓取URL隊(duì)列是很重要的一部分。待抓取URL隊(duì)列中的URL以什么樣的順序排列也是一個(gè)很重要的問題,因?yàn)檫@涉及到先抓取那個(gè)頁(yè)面,后抓取哪個(gè)頁(yè)面。而決定這些URL排列順序的方法,叫做抓取策略。下面是幾種常見的抓取策略:

1) 深度優(yōu)先遍歷策略;

2) 寬度優(yōu)先遍歷策略;

3) 反向鏈接數(shù)策略;

4) Partial PageRank策略;

5) OPIC策略策略;

6) 大站優(yōu)先策略。

2.2數(shù)據(jù)挖掘相關(guān)算法

2.2.1關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則是用來描述事物之間的聯(lián)系,是用來挖掘事物之間的相關(guān)性。挖掘關(guān)聯(lián)規(guī)則的核心是通過統(tǒng)計(jì)數(shù)據(jù)項(xiàng)獲得頻繁項(xiàng)集,現(xiàn)有的算法主要有Apriori、PARTITION、FP2growth及抽樣算法等。

設(shè)I={i1,i2,…,im}是項(xiàng)的集合,設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫(kù)事務(wù)的集合,其中每個(gè)事務(wù)T是項(xiàng)的集合,使得A包含于I。每一個(gè)事務(wù)有一個(gè)標(biāo)志符,稱作TID,設(shè)A是一個(gè)項(xiàng)集,事務(wù)T包含A,關(guān)聯(lián)規(guī)則是形如A→B的蘊(yùn)涵式,并且A∩B=?。

定義1:可信度/置信度(Confidence)?？尚哦燃词恰爸档眯刨囆浴?。設(shè)A,B是項(xiàng)集,對(duì)于事務(wù)集D,A∈D,B∈D,A∩B=?,A→B的可信度定義為:可信度(A→B)=包含A和B的元組數(shù)/包含A的元組數(shù)。

定義2:支持度(Support)。支持度(A→B)=包含A和B的元組數(shù)/元組總數(shù)。支持度描述了A和B這兩個(gè)項(xiàng)集在所有事務(wù)中同時(shí)出現(xiàn)的概率。

定義3:強(qiáng)關(guān)聯(lián)規(guī)則。設(shè)min_sup是最小支持度閾值;min_conf是最小置信度閾值。如果事務(wù)集合T中的關(guān)聯(lián)規(guī)則A→B同時(shí)滿足Support(A→B)>=min_sup,Confidence(A→B)>=min_conf,則A→B稱為T中的強(qiáng)關(guān)聯(lián)規(guī)則。而關(guān)聯(lián)規(guī)則的挖掘就是在事務(wù)集合中挖掘強(qiáng)關(guān)聯(lián)規(guī)則。

2.2.2Apriori算法[1]

Apriori算法是R.Agrawal和R.Srikant在1994年提出的基本關(guān)聯(lián)規(guī)則挖掘算法。該算法的核心思想是基于頻集理論的一種遞推方法,目的是從數(shù)據(jù)庫(kù)中挖掘出那些支持度和信任度都不低于給定的最小支持度閾值和最小信任度閾值的關(guān)聯(lián)規(guī)則。

算法通過迭代的方法反復(fù)掃描數(shù)據(jù)庫(kù)來發(fā)現(xiàn)所有的頻繁項(xiàng)目集。通過頻繁項(xiàng)集的性質(zhì)知道,只有那些確認(rèn)是頻繁項(xiàng)的候選集所組成的超集才可能是頻繁項(xiàng)集。故只用頻繁項(xiàng)集生成下一趟掃描的候選集,即Li-1生成Ci(其中:L為頻繁項(xiàng)集的集合,C為候選項(xiàng)集的集合,i為當(dāng)前掃描數(shù)據(jù)庫(kù)的次數(shù)),在每次掃描數(shù)據(jù)庫(kù)時(shí)只考慮具有同數(shù)目數(shù)據(jù)項(xiàng)的集合。Apriori算法可以生成相對(duì)較少的候選數(shù)據(jù)項(xiàng)集,候選數(shù)據(jù)項(xiàng)集不必再反復(fù)地根據(jù)數(shù)據(jù)庫(kù)中的記錄產(chǎn)生,而是在尋找k頻繁數(shù)據(jù)項(xiàng)集的過程中由前一次循環(huán)產(chǎn)生的k-1頻繁數(shù)據(jù)項(xiàng)集一次產(chǎn)生。算法的描述如下所示。

k= 0;//k表示掃描的次數(shù)

L=?;

C1=I; //初始把所有的單個(gè)項(xiàng)目作為候選集

Repeat

k=k+ 1;

Lk=?;

For eachIi∈Ckdo

Ci= 0;//每個(gè)項(xiàng)目集的初始計(jì)數(shù)設(shè)為0

For eachtj∈Ddo

For eachIi∈Ckdo

IfIi∈tjthen

Ci=Ci+ 1;

For eachIi∈Ckdo

IfCi>=(s×|D|)then//|D|為數(shù)據(jù)庫(kù)中事務(wù)項(xiàng)的總數(shù)

Lk=Lk∪Ii;

L=L∪Lk;

Ck+ 1=Apriori-Gen(Lk);

UntilCk+ 1=?

2.3并行計(jì)算相關(guān)技術(shù)

2.3.1MapReduce[5]

MapReduce是一種編程模型,用于大規(guī)模數(shù)據(jù)集(大于1TB)的并行運(yùn)算。概念“Map(映射)”和“Reduce(化簡(jiǎn))”和它們的主要思想都是從函數(shù)式編程語(yǔ)言里借來的,還有從矢量編程語(yǔ)言里借來的特性。它極大地方便了編程人員在不會(huì)分布式并行編程的情況下,將自己的程序運(yùn)行在分布式系統(tǒng)上。當(dāng)前的軟件實(shí)現(xiàn)是指定一個(gè)Map(映射)函數(shù),用來把一組鍵值對(duì)映射成一組新的鍵值對(duì),指定并發(fā)的Reduce(化簡(jiǎn))函數(shù),用來保證所有映射的鍵值對(duì)中的每一個(gè)共享相同的鍵組。

2.3.2Hadoop[6～8]

Hadoop是一個(gè)分布式基礎(chǔ)架構(gòu),可以在不了解分布式底層信息的情況下,開發(fā)分布式或秉性應(yīng)用程序,充分利用集群的威力高速運(yùn)算和存儲(chǔ),它是云計(jì)算的主要架構(gòu)之一。Hadoop具有以下一些特點(diǎn):

· 擴(kuò)容能力:能可靠地存儲(chǔ)和處理PB級(jí)別數(shù)據(jù);

· 成本低:可以通過普通微機(jī)組成的集群來分發(fā)以及處理數(shù)據(jù)。這些服務(wù)器群總計(jì)可達(dá)數(shù)千個(gè)節(jié)點(diǎn);

· 高效率:通過分發(fā)數(shù)據(jù),Hadoop可以并行地處理數(shù)據(jù),這使得處理非常的快速;

· 可靠性:Hadoop能自動(dòng)地維護(hù)數(shù)據(jù)的多份復(fù)制,并且在任務(wù)失敗后能自動(dòng)地重新部署計(jì)算任務(wù)。

Hadoop是Google MapReduce算法的開源實(shí)現(xiàn),MapReduce的執(zhí)行流程主要包括Map和Reduce兩步。一個(gè)任務(wù)啟動(dòng)后,會(huì)在集群上按各個(gè)節(jié)點(diǎn)的能力配置產(chǎn)生相應(yīng)個(gè)數(shù)的Map進(jìn)程。每個(gè)Map進(jìn)程處理一個(gè)具有key-value特性的數(shù)據(jù)分塊,產(chǎn)生一組key-value對(duì)形式的結(jié)果。當(dāng)一個(gè)節(jié)點(diǎn)上的某個(gè)Map進(jìn)程執(zhí)行結(jié)束后,集群的Hadoop架構(gòu)會(huì)在這個(gè)節(jié)點(diǎn)上啟動(dòng)一個(gè)新的Map進(jìn)程處理下一個(gè)分塊。而Reduce進(jìn)程對(duì)每個(gè)Map進(jìn)程產(chǎn)生的key-value對(duì)進(jìn)行合并,完成計(jì)算。

3總體設(shè)計(jì)

通過以下幾個(gè)步驟實(shí)現(xiàn)圖書推薦系統(tǒng):

1) 網(wǎng)絡(luò)源數(shù)據(jù)獲取;

2) 對(duì)源數(shù)據(jù)進(jìn)行抽取和清洗,以達(dá)到實(shí)驗(yàn)算法的需求;

3) Apriori算法在Hadoop上的實(shí)現(xiàn);

4) 最終界面的實(shí)現(xiàn)以及相關(guān)測(cè)試。

其中數(shù)據(jù)來源有兩個(gè)部分:

1) 圖書列表由圖書館網(wǎng)站獲得;

2) 以圖書館圖書為基礎(chǔ),獲取每一本圖書在豆瓣讀書(book.douban.com)上的用戶評(píng)論。

3.1設(shè)計(jì)思路

基于MapReduce的Apriori并行策略,其候選項(xiàng)集的支持?jǐn)?shù)統(tǒng)計(jì)類似于單詞計(jì)數(shù)過程,因此在海量數(shù)據(jù)且支持度較低時(shí),算法產(chǎn)生了大量的候選項(xiàng)集,從而產(chǎn)生了大量〈itemset,1〉的〈鍵,值〉對(duì),增加了MapReduce系統(tǒng)的負(fù)擔(dān)。比較單詞計(jì)數(shù)與候選項(xiàng)集的支持?jǐn)?shù)統(tǒng)計(jì)不難看出,單詞計(jì)數(shù)要統(tǒng)計(jì)的單詞是未知,因此,單詞計(jì)數(shù)思想較適合找出1-頻繁項(xiàng)集。然而,候選項(xiàng)集的支持?jǐn)?shù)統(tǒng)計(jì)要統(tǒng)計(jì)的候選項(xiàng)集是已知的,它是由頻繁項(xiàng)集通過自身的連接而生成的。因此,為提高候選項(xiàng)集支持?jǐn)?shù)統(tǒng)計(jì)的效率,大量減少鍵/值對(duì)的產(chǎn)生,將Apriori數(shù)據(jù)分割的分組思想應(yīng)用在候選項(xiàng)集的支持?jǐn)?shù)統(tǒng)計(jì)階段,實(shí)現(xiàn)候選項(xiàng)集支持?jǐn)?shù)的分組統(tǒng)計(jì),較大幅度地提高了算法的運(yùn)行效率。實(shí)驗(yàn)擬采用的最基本的MapReduce并行的Apriori分組統(tǒng)計(jì)算法思路為:采用類似單詞計(jì)數(shù)的過程并行掃描數(shù)據(jù)庫(kù),找出滿足最小支持度的1-頻繁項(xiàng)集L1;L1通過自身連接產(chǎn)生2-候選項(xiàng)集C2,采用候選項(xiàng)集支持?jǐn)?shù)的分組統(tǒng)計(jì)算法統(tǒng)計(jì)C2的支持?jǐn)?shù),形成2-頻繁項(xiàng)集L2;相同步驟,L2產(chǎn)生L3,如此迭代循環(huán),直到?jīng)]有新的k-頻繁項(xiàng)集產(chǎn)生。

除此之外我們希望嘗試的另外一種可以加速運(yùn)行的算法的具體步驟為:將原數(shù)據(jù)庫(kù)劃分為n組,使各組數(shù)據(jù)足夠載入內(nèi)存運(yùn)行,并分別統(tǒng)計(jì)候選項(xiàng)集在各組數(shù)據(jù)中的支持?jǐn)?shù),稱為候選項(xiàng)集的局部支持?jǐn)?shù);合并候選項(xiàng)集在各組數(shù)據(jù)中的支持?jǐn)?shù),形成最后候選項(xiàng)集的全局支持?jǐn)?shù)。

3.2期望結(jié)果

我們計(jì)劃通過MapReduce的方式在Hadoop集群上求解出圖書推薦系統(tǒng)所需要的頻繁項(xiàng)集,之后以關(guān)系數(shù)據(jù)庫(kù)的形式來存放這些數(shù)據(jù)。當(dāng)用戶在網(wǎng)站上進(jìn)行圖書閱讀記錄時(shí)會(huì)根據(jù)由頻繁項(xiàng)集得到的圖書之間的關(guān)系給用戶提供可能感興趣的圖書推薦。這種推薦基于眾多用戶的真實(shí)體驗(yàn),利用簡(jiǎn)單的算法在大數(shù)據(jù)中更準(zhǔn)確地體現(xiàn)了用戶的需求。

4實(shí)現(xiàn)過程

4.1獲得數(shù)據(jù)

實(shí)驗(yàn)中需要大量圖書的評(píng)論作為Apriori算法挖掘關(guān)聯(lián)規(guī)則的源數(shù)據(jù),但是目前網(wǎng)上沒有國(guó)內(nèi)圖書評(píng)論的數(shù)據(jù)庫(kù)。因此本文采用南京大學(xué)圖書館的藏書作為圖書評(píng)論的源,并以此為基礎(chǔ)從國(guó)內(nèi)讀書比較流行的網(wǎng)站豆瓣讀書上來獲取用戶的評(píng)論。

在第一步獲取圖書館藏書列表時(shí),利用圖書館以《中圖法》為標(biāo)準(zhǔn)定義的分類檢索所有圖書的接口將圖書按類別進(jìn)行遍歷,獲取其中關(guān)于圖書的基本信息(ISBN,圖書名,作者等),共獲得圖書549621冊(cè)。按類別統(tǒng)計(jì)如表1所示。

表1　圖書總量

然后使用豆瓣讀書所提供的API來獲取所有圖書的評(píng)論信息,豆瓣讀書API如表2所示。

表2　豆瓣圖書API列表

之后共獲得圖書評(píng)論339621條,其中涉及圖書39186本。

4.2利用MapReduce實(shí)現(xiàn)Apriori算法

以上一部分所得數(shù)據(jù)為基礎(chǔ),采用Apriori算法來計(jì)算圖書推薦的關(guān)聯(lián)規(guī)則。根據(jù)上文所描寫的Apriori算法,獲得二項(xiàng)頻繁集的過程主要有三個(gè)部分: 1) 計(jì)算每本圖書的支持度; 2) 統(tǒng)計(jì)二項(xiàng)頻繁集每個(gè)元組的支持度; 3) 計(jì)算二元組中圖書A到圖書B的置信度。

1) 整理數(shù)據(jù)

由豆瓣讀書得到的數(shù)據(jù)為{ISBN,{{用戶ID,用戶名,評(píng)分},…}}的集合,為進(jìn)行二項(xiàng)頻繁集的統(tǒng)計(jì)我們需要將其轉(zhuǎn)換為{用戶ID,{{ISBN},…}}的形式。將爬取的以ISBN為區(qū)分的評(píng)分?jǐn)?shù)據(jù)轉(zhuǎn)換為以用戶ID為區(qū)分的數(shù)據(jù)。此處的MapReduce設(shè)計(jì)為在Map階段對(duì)每行數(shù)據(jù)進(jìn)行分析,然后以用戶ID為key,以ISBN為value將其傳入到下一階段的Reducer中;Reducer階段將key相同,即用戶ID相同的記錄進(jìn)行合并,合并為{用戶ID ISBN;ISBN;ISBN}的格式以方便之后支持度和二項(xiàng)頻繁集的計(jì)算,其主要代碼如下:

publicclassPreJobMapperextends Mapper〈Object, Text, Text, Text〉 {

//Input:“ISBNUser_ID/User_Name/Rate;…”

//Output: “User_ID ISBN Rate”

//用于將形如“ISBN User_ID/User_Name/Rate;…”的輸入轉(zhuǎn)換成形如“User_ID ISBN Rate”的輸出

publicvoidmap(Object key, Text value, Context context)

throwsIOException, InterruptedException {

String bookRate[] = value.toString().split(" ", 0);

String rates[] = bookRate[1].split(";", 0);//得到每一條ISBN的用戶評(píng)分集合

for(inti=0;I

String rateEntry = rates[i];//得到格式如下的字符串rateEntry:用戶ID,用戶名,評(píng)分

String rateUseID = rateEntry.split("/", 0)[0];//得到用戶ID

String rate = rateEntry.split("/", 0)[2];//得到用戶評(píng)分

context.write(new Text(rateUseID), new Text(bookRate[0]+" "+rate));//拼接如下格式的字符串作為輸出:用戶ID ISBN 評(píng)分

}

}

}

publicclassPreJobReducerextends Reducer〈Text, Text, Text, Text〉 {

//Input:“User_ID ISBN Rate”

//Output: “User_ID ISBN1;ISBN2;…”

//用于合并同一個(gè)用戶所評(píng)分的書

publicvoid reduce(Text key, Iterable〈Text〉 values, Context context)

throwsIOException, InterruptedException {

Text value = newText();

String strISBNs = "";

Iterator〈Text〉it=values.iterator();

while(it.hasNext()){

String isbn = it.next().toString().split(" ", 0)[0];

if(strISBNs==""||!strISBNs.contains(isbn))

strISBNs += isbn+";";

} //判斷當(dāng)前ISBN是否已存在于該用戶的ISBN列表中,如不存在,直接添加在該用戶列表后面

context.write(key, new Text(strISBNs));//以User_ID作為key,該用戶評(píng)過分的書目ISBN列表作為value輸出

}

}

2) 計(jì)算支持度

支持度是每本圖書在數(shù)據(jù)集中出現(xiàn)的次數(shù),即每本圖書的評(píng)論數(shù)量。計(jì)算支持度時(shí)需要在Map階段將第一部所得數(shù)據(jù)轉(zhuǎn)換成以ISBN為key,以數(shù)字1為value的記錄,在Reducer階段再統(tǒng)計(jì)相同ISBN的記錄條數(shù),即可得到圖書的支持度。

3) 計(jì)算二項(xiàng)頻繁集

publicclassFreqItemSet2Mappeextends Mapper〈Object, Text, Text, Text〉 {

//Input: “User_ID ISBN1;ISBN2;…”

//Output:“ISBN1;ISBN2 1”

//統(tǒng)計(jì)所有出現(xiàn)過的圖書二元組,例如一個(gè)用戶讀過A,B,C三本書,那么會(huì)產(chǎn)生(A,B),(A,C),(B,C)這三個(gè)二元組

publicvoidmap(Object key, Text value, Context context)

throwsIOException, InterruptedException {

Text newValue = newText();

String row[] = value.toString().split(" ", 0);

String allisbn[] = row[1].split(";", 0);//得到該用戶評(píng)分的所有ISBN列表

for (inti = 0; i

for (int j = i + 1; j

context.write(new Text(allisbn[i] + ";" + allisbn[j]), new Text("1;" + row[0]));

context.write(new Text(allisbn[j] + ";" + allisbn[i]), new Text("1;" + row[0]));

}//以(A,B)(B,A)作為兩種獨(dú)立的輸出,防止hadoop將其當(dāng)做不同的二元組造成支持度計(jì)算錯(cuò)誤

}

}

publicclassFreqItemSetReducerextends Reducer〈Text, Text, Text, Text〉 {

//Input: “ISBN1;ISBN2 1”

//Output:“ISBN1;ISBN2 support”

//合并計(jì)算相同的二元組出現(xiàn)的個(gè)數(shù),并計(jì)算支持度

publicvoid reduce(Text key, Iterable〈Text〉 values, Context context)

throwsIOException, InterruptedException {

int total=0;

Text value = newText();

String strUserIDs = "";

Iterator〈Text〉it=values.iterator();

while(it.hasNext()){

String temp = it.next().toString();

strUserIDs+= temp.split(";", 0)[1]+";";

++total;

} //統(tǒng)計(jì)相同的ISBN二元組出現(xiàn)的個(gè)數(shù),即有多少用戶同時(shí)讀過相同的兩本書

if(total>=2)

context.write(key, new Text(total+","+strUserIDs)); //選取支持度大于2的二元組

}

}

4) 計(jì)算置信度[1]

置信度是表示圖書之間相關(guān)性的屬性,是生成關(guān)聯(lián)規(guī)則的關(guān)鍵,表達(dá)的是從事物A產(chǎn)生事物B的可信度,其計(jì)算方式為式(1):

(1)

計(jì)算置信度需要知道二元組的支持度和每本圖書的支持度,為此需要步驟2)和3)中的數(shù)據(jù),需要兩個(gè)表關(guān)聯(lián)操作。將二項(xiàng)頻繁集中二元組{A,B}的支持度除以二元組中圖書A的支持度即可得到從圖書A生成圖書B的可信度。以二元組中圖書A的ISBN為Key,將圖書A的支持度和二元組{A,B}的支持度分別作為value,這樣在Reduce的過程中做好區(qū)分二元組和圖書A的支持度之后就可以計(jì)算出二元組{A,B}中圖書A對(duì)圖書B的置信度。

5) 其他

因?yàn)槠渌鸎-頻繁項(xiàng)集(K>2)都是2-頻繁項(xiàng)集的子集,只要將步驟3)中得到的2-頻繁項(xiàng)集數(shù)據(jù)處理為步驟1的結(jié)果,并再如步驟3)一樣處理就可以得到3-頻繁項(xiàng)集等。

4.3運(yùn)行結(jié)果

實(shí)驗(yàn)所得2-頻繁項(xiàng)集及其置信度數(shù)據(jù)如圖2所示。

為便于用戶使用,將該結(jié)果存儲(chǔ)在關(guān)系數(shù)據(jù)庫(kù)SQLServer2008中,并用ASP.Net MVC開發(fā)了一個(gè)搜索圖書推薦的網(wǎng)站。推薦網(wǎng)站的查詢界面如圖3所示,查詢結(jié)果如圖4所示。

圖2　2-頻繁項(xiàng)集及其置信度

圖3　圖書推薦系統(tǒng)查詢界面

圖4　查詢結(jié)果

4.4存在的問題及改進(jìn)

由于圖書推薦系統(tǒng)中圖書項(xiàng)是很龐大的,且用戶選擇讀書有一定的隨機(jī)性,所以想要生成滿足一定支持度和置信度的頻繁項(xiàng)集是很困難的,針對(duì)這個(gè)問題,做了如下改進(jìn):

1) 只生成到二次頻繁項(xiàng)集。因?yàn)槔^續(xù)往后生成更高的頻繁項(xiàng)集得到的結(jié)果會(huì)很少,對(duì)任意圖書的推薦并沒有很大的意義,且增加了計(jì)算量。而二次頻繁項(xiàng)集相對(duì)是比較容易生成,且基本涵蓋了大部分的圖書項(xiàng),方便對(duì)任意圖書進(jìn)行有效的推薦。

2) 不設(shè)定具體的最小支持度和最小置信度,只是統(tǒng)計(jì)二次頻繁項(xiàng)集時(shí)出現(xiàn)的具體個(gè)數(shù),在具體查詢某一具體書籍時(shí),尋找與它相關(guān)的所有二次頻繁項(xiàng)集,并查看相關(guān)二次頻繁項(xiàng)集的個(gè)數(shù),這個(gè)個(gè)數(shù)即可反應(yīng)出該二元組規(guī)則的一個(gè)支持度和置信度。我們根據(jù)這個(gè)個(gè)數(shù)進(jìn)行從大到小的排序,選取前五個(gè)作為推薦書籍。這樣一來,可以有效杜絕因?yàn)椴煌瑫霈F(xiàn)的頻次不同,導(dǎo)致有的書推薦很多,有的書無書可推的情況。

5結(jié)語(yǔ)

本文完成的是一種基于Apriori算法創(chuàng)建關(guān)聯(lián)規(guī)則的圖書推薦在Hadoop上的實(shí)現(xiàn)。利用在豆瓣讀書上獲取的圖書評(píng)論數(shù)據(jù),使用Hadoop生成圖書的K-頻繁集,并計(jì)算相關(guān)的圖書推薦置信度。通過簡(jiǎn)單的操作,就可以在其上實(shí)現(xiàn)Apriori算法,并且具有相當(dāng)高的運(yùn)行速度。項(xiàng)目中也表現(xiàn)出了圖書評(píng)論集中的問題,有相當(dāng)一部分的書籍由于沒有多少人閱讀和評(píng)論,出現(xiàn)了無法進(jìn)行推薦的情況。此外還有一部分?jǐn)?shù)據(jù)雖然ISBN等不相同,但是是同一本書的不同版本,也應(yīng)將其合并為同一本書進(jìn)行推薦,這部分會(huì)作為下一步工作的一部分進(jìn)行對(duì)該圖書的推薦。

參 考 文 獻(xiàn)

[1] 黃立勤,柳燕煌.基于MapReduce并行的Apriori算法改進(jìn)研究[J].福州大學(xué)學(xué)報(bào),2010,39(5):680-685.

HUANG Liqin, LIU Yanhuang. Research on improved parallel Apriori with MapReduce[J]. Journal of Fuzhou University,2010,39(5):680-685.

[2] 戎翔,李玲娟.基于MapReduce的頻繁項(xiàng)集挖掘方法[J].西安郵電學(xué)院學(xué)報(bào),2011(7):37-39.

RONG Xiang, LI Lingjuan. Frequent item set mining method based on MapReduce[J]. Journal of Xi’an University of Posts and Telecomunications,2011(7):37-39.

[3] 余楚禮,肖迎元,尹波.一種基于Hadoop的并行關(guān)聯(lián)規(guī)則算法[J].天津理工大學(xué)學(xué)報(bào),2011,27(1):26-30.

YU Chuli. A parallel algorithm for mining frequent item sets on Hadoop[J]. Journal of Tianjin University of Technology,2011,27(1):26-30.

[4] 鄭志嫻.基于云計(jì)算的Apriori算法設(shè)計(jì)[J].莆田學(xué)院學(xué)報(bào),2014,21(5):61-64.

ZHENG Zhixian. The Design of Apriori Algorithm Based on Cloud Computer[J]. Journal of Putian University,2014,21(5):61-64.

[5] 鄭祥云.基于主題模型的個(gè)性化圖書推薦算法[J].計(jì)算機(jī)應(yīng)用,2015,35(9):2569-2573.

ZHENG Xiangyun. Personalized book recommendation algorithm based on topic model[J]. Journal of Computer Applications,2015,35(9):2569-2573.

[6] 王東雷.基于MapReduce的大數(shù)據(jù)流程處理方法[J].計(jì)算機(jī)應(yīng)用,2013,33(S2):57-59,127.

WANG Donglei. MapReduce-based method for large data flow processing[J]. Journal of Computer Applications,2013,33(S2):57-59,127.

[7] 王淑芬.基于Hadoop的廣域網(wǎng)分布式主題爬蟲系統(tǒng)框架[J].計(jì)算機(jī)工程與科學(xué),2015,37(4):670-675.

WANG Shufen. A framework of WAN distributed topic crawling system based on Hadoop[J]. Computer Engineering & Science,2015,37(4):670-675.

[8] 李建江.MapReduce并行編程模型研究綜述[J].電子學(xué)報(bào),2011,39(11):2635-2640.

LI Jianjiang. Survey of MapReduce Parallel Programming Model[J]. Acta Electronic Sinica,2011,39(11):2635-2640.

[9] 杜江,張錚.MapReduce并行編程模型研究綜述[J].計(jì)算機(jī)科學(xué),2015,42(6):537-564.

DU Jiang, ZHANG Zheng. Survey of MapReduce Parallel Programming Model[J]. Computer Science,2015,42(6):537-564.

[10] 王雪蓉.云模式用戶行為關(guān)聯(lián)聚類的協(xié)同過濾推薦算法[J].計(jì)算機(jī)應(yīng)用,2011,31(9):2421-2425.

WANG Xuerong. Cloud pattern collaborative filtering recommender algorithm using user behavior correlation clustering[J]. Journal of Computer Application,2011,31(9):2421-2425.

Research and Design of Hadoop-Based Book Recommendation System

NAN Lei1,2

(1. Jiangsu Information Center, Nanjing210013)(2. State Key Laboratory for Novel Software Technology(Nanjing University), Nanjing210023)

AbstractAfter years of development, the book market in the type of scale and the overall number of such areas have made considerable progress. But at the same time, it brings too many books, which makes it difficult for readers to choose the right books. The general classification allows the reader to choose from each type of book, but there are still thousands of books under each category. In this paper, a kind of book recommendation based on the Apriori algorithm to create the association rules is realized in Hadoop. Using the book review data obtained from the book review, Hadoop is used to generate the K-frequent sets of books, and the relevant books recommended confidence is calculated. The algorithm can efficiently provide the recommendation service for readers.

Key WordsMapReduce, concurrent computation, association rules, book recommendation, Hadoop

收稿日期:2015年12月5日,修回日期:2016年1月26日

基金項(xiàng)目:國(guó)家自然科學(xué)基金面上項(xiàng)目(編號(hào):61272418)資助。

作者簡(jiǎn)介:南磊,男,博士研究生,助理研究員,研究方向:大數(shù)據(jù)、無線網(wǎng)絡(luò)、軟件工程等。

中圖分類號(hào)TP311

DOI:10.3969/j.issn.1672-9722.2016.06.016