摘" 要： 為了應(yīng)對(duì)大數(shù)據(jù)環(huán)境下圖書館個(gè)性化信息服務(wù)的發(fā)展趨勢，提供更加精準(zhǔn)的用戶服務(wù)，構(gòu)建基于Hadoop云計(jì)算平臺(tái)的圖書館數(shù)據(jù)挖掘系統(tǒng)，并設(shè)計(jì)一種新型混合決策樹算法。首先，設(shè)計(jì)包含4個(gè)層次的數(shù)據(jù)挖掘系統(tǒng)架構(gòu)。然后，在算法層提出一種采用混合策略的決策樹算法，該算法結(jié)合分布式改進(jìn)的SPRINT算法和并行化的樸素貝葉斯算法，以便滿足HDFS和MapReduce的運(yùn)作方式，從而能夠在Hadoop平臺(tái)上進(jìn)行實(shí)現(xiàn)。Hadoop集群環(huán)境的用戶信息測試結(jié)果表明，相比單一的SPRINT算法和樸素貝葉斯算法，提出的新型混合決策樹算法具有最佳的數(shù)據(jù)挖掘分類性能。

關(guān)鍵詞： 大數(shù)據(jù); 云計(jì)算; Hadoop; SPRINT; 樸素貝葉斯; 決策樹

中圖分類號(hào)： TN911.2?34; TP393" " " " " " " " " "文獻(xiàn)標(biāo)識(shí)碼： A" " " " " " " " " " 文章編號(hào)： 1004?373X（2019）21?0036?05

Abstract： In order to deal with the development trend of library personalized information service in big data environment， a library user information mining system based on Hadoop cloud computing platform is constructed， and a new hybrid decision tree algorithm is designed. The data mining system architecture consisting of four levels （computing storage layer， Hadoop platform layer， algorithm layer and user interaction layer） is designed， and then， a decision tree algorithm based on hybrid strategy is proposed in the algorithm layer. The algorithm combines the improved distributed SPRINT algorithm and the parallelized naive Bayesian algorithm to meet the operation mode of HDFS and MapReduce， so that it can be used in Hadoop， and implemented on the Hadoop platform. The results of user information testing in Hadoop cluster environment show that the new hybrid decision tree algorithm has the best data mining classification performance in comparison with the single SPRINT algorithm and naive Bayes algorithm.

Keywords： big data; cloud computing; Hadoop; SPRINT; naive Bayes; decision tree

0" 引" 言

隨著全球互聯(lián)網(wǎng)和現(xiàn)代移動(dòng)網(wǎng)絡(luò)等技術(shù)的發(fā)展，數(shù)據(jù)呈現(xiàn)爆炸式增長的態(tài)勢，傳統(tǒng)數(shù)據(jù)庫系統(tǒng)己經(jīng)很難滿足大數(shù)據(jù)時(shí)代的需求。云計(jì)算的出現(xiàn)很好地解決了此類海量數(shù)據(jù)的存儲(chǔ)問題，并為相關(guān)數(shù)據(jù)挖掘處理應(yīng)用提供了技術(shù)支撐。然而，云計(jì)算信息數(shù)據(jù)時(shí)代的來臨，導(dǎo)致普通用戶在面對(duì)眾多圖書的選擇問題時(shí)無法快速找到自己需要的對(duì)象，這就是典型的圖書館個(gè)性化用戶信息服務(wù)需求。如何在海量的圖書館用戶信息中通過大數(shù)據(jù)挖掘技術(shù)尋找出符合用戶需求的結(jié)果，從而提供高精準(zhǔn)度的個(gè)性化需求服務(wù)，是現(xiàn)階段圖書管理領(lǐng)域的研究重點(diǎn)和難點(diǎn)[1?2]。

因此，本文設(shè)計(jì)一種基于Hadoop云計(jì)算平臺(tái)的圖書館數(shù)據(jù)挖掘系統(tǒng)。首先，利用Hadoop平臺(tái)的海量數(shù)據(jù)存儲(chǔ)和分布式計(jì)算能力，設(shè)計(jì)包含4個(gè)層次（計(jì)算存儲(chǔ)層、Hadoop平臺(tái)層、算法層和用戶交互層）的數(shù)據(jù)挖掘系統(tǒng)架構(gòu)。其次，為了提高數(shù)據(jù)的處理性能，本文在算法層中提出一種采用混合策略的決策樹算法，通過將SPRINT算法和樸素貝葉斯算法有效結(jié)合，并分別進(jìn)行并行化處理從而能夠在Hadoop平臺(tái)上運(yùn)作。測試結(jié)果驗(yàn)證了所提混合算法的可行性。

1" 研究問題與主要思想描述

目前，由Google提出的分布式計(jì)算模型Hadoop是主流的云計(jì)算平臺(tái)框架，具有經(jīng)濟(jì)、可靠、擴(kuò)容能力強(qiáng)、并行性好、效率高等諸多優(yōu)點(diǎn)[3]。Hadoop大數(shù)據(jù)平臺(tái)幫助政企、金融、教育等多個(gè)行業(yè)及領(lǐng)域?qū)崿F(xiàn)了海量數(shù)據(jù)的計(jì)算存儲(chǔ)管理、數(shù)據(jù)深度挖掘以及品牌輿情等多樣化。為了支持對(duì)應(yīng)用數(shù)據(jù)高吞吐量訪問，Hadoop采用了分布式文件系統(tǒng)（Hadoop Distributed File System，HDFS） [3]。此外，為了將數(shù)據(jù)分散到集群的各臺(tái)機(jī)器上，以便提高計(jì)算效率，Hadoop具有MapReduce并行運(yùn)行模型。然而，傳統(tǒng)的串行大數(shù)據(jù)挖掘算法不能有效地在Hadoop平臺(tái)上執(zhí)行，即無法應(yīng)對(duì)海量數(shù)據(jù)挖掘問題。

因此，研究人員為了解決上述問題提出了許多方法。文獻(xiàn)[4]提出一種面向大數(shù)據(jù)挖掘的Hadoop框架K均值聚類算法，將大數(shù)據(jù)劃分成許多數(shù)據(jù)塊，在Reduce和Map階段進(jìn)行加權(quán)融合。文獻(xiàn)[5]設(shè)計(jì)一種Hadoop下基于樸素貝葉斯分類的大數(shù)據(jù)挖掘方法，分析了MapReduce計(jì)算模型。文獻(xiàn)[6]通過Hadoop系統(tǒng)中的MapReduce模型對(duì)改進(jìn)支持向量機(jī)SVM過程進(jìn)行處理，提高了海量文本數(shù)據(jù)分類的效率。

但是上述單一的經(jīng)典數(shù)據(jù)挖掘分類算法（如決策樹算法、支持向量機(jī)SVM等）在處理海量圖書館用戶信息數(shù)據(jù)時(shí)總顯得力不從心，無法在準(zhǔn)確率方面獲得較好的結(jié)果。因此， 本文在圖書館用戶信息Hadoop挖掘系統(tǒng)中提出一種采用混合策略的決策樹算法，該算法結(jié)合了分布式改進(jìn)的SPRINT算法和并行化的樸素貝葉斯算法，從而符合HDFS和MapReduce的工作模式。

2" 基于Hadoop云計(jì)算平臺(tái)的信息挖掘系統(tǒng)設(shè)計(jì)

2.1" 關(guān)鍵技術(shù)

Hadoop云計(jì)算平臺(tái)包含分布式文件系統(tǒng)HDFS和MapReduce計(jì)算模型[7]兩個(gè)關(guān)鍵技術(shù)。分布式文件系統(tǒng)HDFS具有一次寫入多次讀取的能力，實(shí)現(xiàn)了高度容錯(cuò)，較大的訪問帶寬特點(diǎn)避免了網(wǎng)絡(luò)阻塞，降低了對(duì)硬件的要求，實(shí)現(xiàn)了一定意義上的數(shù)據(jù)批量處理。而MapReduce計(jì)算模型是Hadoop平臺(tái)實(shí)現(xiàn)超大規(guī)模數(shù)據(jù)并行運(yùn)算的關(guān)鍵，其本質(zhì)為一種軟件編程架構(gòu)（模式），能夠通過Hadoop集群上的多個(gè)節(jié)點(diǎn)訪問HDFS上存儲(chǔ)的分散數(shù)據(jù)且進(jìn)行并行計(jì)算，避免大量數(shù)據(jù)的復(fù)制傳輸操作，有效節(jié)約了網(wǎng)絡(luò)帶寬，其標(biāo)準(zhǔn)的運(yùn)作方式如圖1所示[8]。

2.2" 系統(tǒng)框架

基于Hadoop云計(jì)算平臺(tái)的信息挖掘系統(tǒng)必須充分發(fā)揮HDFS和MapReduce的作用，將數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)挖掘任務(wù)工作分配到Hadoop集群中的各個(gè)節(jié)點(diǎn)上。因此，本文設(shè)計(jì)的信息挖掘系統(tǒng)框架如圖2所示，主要包括計(jì)算存儲(chǔ)層、Hadoop平臺(tái)層、算法層和用戶交互層，其中算法層是研究的重點(diǎn)，負(fù)責(zé)快速有效地處完成數(shù)據(jù)的相應(yīng)挖掘任務(wù)。

3" 提出的新型圖書館大數(shù)據(jù)挖掘算法

經(jīng)過研究分析，傳統(tǒng)的經(jīng)典數(shù)據(jù)挖掘分類算法有許多在數(shù)據(jù)挖掘系統(tǒng)的算法層可以實(shí)現(xiàn)并行化，但是單一的分類算法在處理海量圖書館用戶信息數(shù)據(jù)時(shí)仍舊存在準(zhǔn)確率不夠理想的問題。因此本文提出一種新的混合型圖書館大數(shù)據(jù)挖掘算法，將SPRINT算法和樸素貝葉斯算法有效結(jié)合。

3.1" SPRINT算法的分布式改進(jìn)

首先，要對(duì)典型的SPRINT算法[9]進(jìn)行分布式改進(jìn)。SPRINT算法屬于決策樹算法，但是不同于ID3、C4.5和CART等算法，在對(duì)數(shù)據(jù)樣本集判斷最佳分裂屬性的度量時(shí)使用的是Gini指標(biāo)。Gini值的計(jì)算公式如下：

式中：[S]表示一個(gè)集合;[Pi]表示種類[i]出現(xiàn)的頻率;[n]為種類的總數(shù)。

如果將集合[S]分裂為兩個(gè)子集[S1]和[S2]，則兩者之間的Gini值為：

式中：[m]表示集合[S]中數(shù)據(jù)記錄的總行數(shù);[m1]和[m2]分別表示集合[S1]和[S2]中數(shù)據(jù)記錄的總行數(shù)。

為了有效利用圖1中MapReduce框架的映射功能（Map），需要進(jìn)行分布式改進(jìn)，因此，將SPRINT決策樹算法中位于相同層的所有Node樹節(jié)點(diǎn)的工作，映射到不同的Reducer進(jìn)行分布式操作。然后，僅需不斷迭代調(diào)用過程就能夠?qū)崿F(xiàn)所有節(jié)點(diǎn)的分裂，從而建立所需的決策樹。Map函數(shù)的偽代碼如下：

輸入：訓(xùn)練樣本集

輸出：根據(jù)Key排序后lt;Key，valuegt;鍵值對(duì)

格式化處理;

初始化lt;Key，valuegt;值，進(jìn)行combine操作;

處理后的鍵值對(duì)輸出到文件中;

3.2" 樸素貝葉斯算法的并行化

貝葉斯分類的基礎(chǔ)是概率推理[10]，可表示為[PCx1，x2，…，xn]，其中[C]表示類別變量，[X={x1，x2，…，xn}]表示屬性變量集合，[xi]為特征。根據(jù)貝葉斯定理，樸素貝葉斯概率模型的定義如下：

為了在Hadoop平臺(tái)上實(shí)現(xiàn)樸素貝葉斯算法，需要對(duì)其進(jìn)行并行化改進(jìn)。在Map階段的操作同SPRINT算法一致，而將Reduce階段分為兩個(gè)步驟。第一步需要獲取概率信息文件，即獲取每個(gè)屬性在不同類別變量中的平均值[E（X）]和標(biāo)準(zhǔn)差[D（X）]。假設(shè)連續(xù)屬性服從高斯分布，兩者的計(jì)算方式如下：

根據(jù)第一輪得到的有關(guān)概率文件，利用式（5）完成第二步的分類，得到不同類別的概率乘積并按照從小到大排序選取最小值對(duì)應(yīng)的結(jié)果作為樣本類別。

3.3" 混合決策樹算法的實(shí)現(xiàn)

利用SPRINT算法和樸素貝葉斯算法相結(jié)合的方法實(shí)現(xiàn)數(shù)據(jù)挖掘分類的流程如圖3所示?？梢钥闯?，混合決策樹算法的Map階段如3.1節(jié)偽代碼所示，Reduce階段利用SPRINT算法構(gòu)造決策樹，然后分別對(duì)其每個(gè)葉子節(jié)點(diǎn)上的數(shù)據(jù)集執(zhí)行3.2節(jié)中樸素貝葉斯算法的式（6）和式（7）得到有關(guān)概率文件，最后利用計(jì)算概率乘積并按照從小到大排序，選取最小值對(duì)應(yīng)的結(jié)果作為樣本類別。

4" 實(shí)驗(yàn)結(jié)果與分析

4.1" 實(shí)驗(yàn)環(huán)境

為了對(duì)本文提出的新型混合決策樹數(shù)據(jù)挖掘算法進(jìn)行分析和驗(yàn)證，進(jìn)行Hadoop集群測試。虛擬機(jī)中搭建一個(gè)包含3個(gè)節(jié)點(diǎn)的Hadoop集群環(huán)境（1個(gè)master，2個(gè)slaves）。每個(gè)集群節(jié)點(diǎn)的硬件環(huán)境為： Intel Core i5 2.8 GHz處理器，4 GB內(nèi)存，500 GB硬盤。軟件環(huán)境為：CentOS 6.0操作系統(tǒng)，Hadoop 1.0.4版本，Java JDK。

4.2" 數(shù)據(jù)預(yù)處理

實(shí)驗(yàn)采用某高校中圖書管理系統(tǒng)的數(shù)據(jù)庫數(shù)據(jù)集。該數(shù)據(jù)集包含圖書館2018年的用戶信息1 020 513條，如表1所示。

首先要將圖書館用戶信息數(shù)據(jù)劃分為訓(xùn)練集和測試集兩個(gè)部分。訓(xùn)練集中的所有書籍通過人工標(biāo)記分為E（計(jì)算機(jī)類）、H（英語類）、W（自動(dòng)類）、A（藝術(shù)類）、C（社會(huì)類）、J（文學(xué)類）六大類，對(duì)這六類圖書進(jìn)行數(shù)據(jù)泛化得到表2。

4.3" 評(píng)估指標(biāo)

為了對(duì)數(shù)據(jù)挖掘分類算法的性能進(jìn)行有效量化評(píng)估，本文采用三個(gè)評(píng)估指標(biāo)[12]：準(zhǔn)確率（Accuracy）、召回率（Recall）、[F]值（[F]?Measure）。準(zhǔn)確率計(jì)算公式為：

4.4" 分類性能分析

在測試數(shù)據(jù)集上進(jìn)行分類實(shí)驗(yàn)，基于樸素貝葉斯算法[5]、SPRINT算法[9]和本文混合決策樹數(shù)據(jù)挖掘算法的分類器結(jié)果對(duì)比如圖4～圖6所示。

從圖4～圖6可以看出，樸素貝葉斯分類算法的性能最差，SPRINT算法有所提升，本文混合決策樹數(shù)據(jù)挖掘算法的準(zhǔn)確率最高，且綜合評(píng)估指標(biāo)[F]值也最高，有效提供了更加精準(zhǔn)的用戶服務(wù)。

5" 結(jié)" 語

本文提出一種適用于Hadoop云計(jì)算平臺(tái)的混合決策樹數(shù)據(jù)挖掘分類算法，這種算法結(jié)合了分布式改進(jìn)的SPRINT算法和并行化的樸素貝葉斯算法，從而符合HDFS和MapReduce的工作模式。Hadoop集群環(huán)境的用戶信息測試結(jié)果驗(yàn)證了該算法的可行性和準(zhǔn)確性。但是在召回率指標(biāo)上，相比單一分類算法，混合算法的優(yōu)勢不突出。此外，算法運(yùn)行時(shí)間有所增加，后續(xù)將對(duì)如何在不降低精確度的條件下，提高運(yùn)行效率開展進(jìn)一步研究。

參考文獻(xiàn)

[1] HASHEM I A T， YAQOOB I， ANUAR N B， et al. The rise of “big data” on cloud computing： review and open research issues [J]. Information systems， 2015， 47（C）： 98?115.

[2] GANDOMI A， HAIDER M. Beyond the hype： big data concepts， methods， and analytics [J]. International journal of information management， 2015， 35（2）： 137?144.

[3] LYU Yisheng， DUAN Yanjie， KANG Wenwen， et al. Traffic flow prediction with big data： a deep learning approach [J]. IEEE transactions on intelligent transportation systems， 2015， 16（2）： 865?873.

[4] 李爽，陳瑞瑞，林楠.面向大數(shù)據(jù)挖掘的Hadoop框架K均值聚類算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2018， 39（12）：142?146.

LI Shuang， CHEN Ruirui， LIN Nan. K?means clustering algorithm of Hadoop framework for large data mining [J]. Computer engineering and design， 2018， 39（12）： 142?146.

[5] WU J， PAN S， ZHU X， et al. Self?adaptive attribute weighting for naive Bayes classification [J]. Expert systems with applications， 2015， 42（3）： 1487?1502.

[6] 趙穎.基于改進(jìn)SVM的文本混沌性分類優(yōu)化技術(shù)實(shí)現(xiàn)[J].現(xiàn)代電子技術(shù)，2016，39（20）：39?43.

ZHAO Ying. Realization of text chaotic classification optimization technology based on improved SVM [J]. Modern electronics technique， 2016， 39（20）： 39?43.

[7] GUO Y， JIA R， JIANG C， et al. Moving Hadoop into the cloud with flexible slot management and speculative execution [J]. IEEE transactions on parallel amp; distributed systems， 2017， 28（3）： 798?812.

[8] HUANG W， WANG H， ZHANG Y， et al. A novel cluster computing technique based on signal clustering and analytic hierarchy model using Hadoop [J]. Cluster computing， 2017（4）： 1?8.

[9] 楊潔，黃剛.基于云計(jì)算的SPRINT算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2017，27（3）：108?112.

YANG Jie， HUANG Gang. Research on SPRINT algorithm based on cloud computing [J]. Computer technology and deve?lopment， 2017， 27（3）： 108?112.

[10] 張晨陽，馬志強(qiáng)，劉利民，等.Hadoop下基于粗糙集與貝葉斯的氣象數(shù)據(jù)挖掘研究[J].計(jì)算機(jī)應(yīng)用與軟件， 2015（4）：72?76.

ZHANG Chenyang， MA Zhiqiang， LIU Limin， et al. Research on meteorological data mining based on rough set and Bayesian under Hadoop [J]. Computer application and software， 2015（4）： 72?76.

[11] WOLFSON J， BANDYOPADHYAY S， ELIDRISI M， et al. A naive Bayes machine learning approach to risk prediction using censored， time?to?event data [J]. Statistics in medicine， 2015， 34（21）： 2941?2957.

[12] BO Y， LEI Y， BEI Y. Distributed multi?human location algorithm using naive Bayes classifier for a binary pyroelectric infrared sensor tracking system [J]. IEEE sensors journal， 2015， 16（1）： 216?223.