基于hadoop 平臺(tái)的數(shù)據(jù)挖掘算法實(shí)證研究*

高 飛

（廣西現(xiàn)代職業(yè)技術(shù)學(xué)院，廣西 河池 547000）

引言

隨著信息技術(shù)的不斷發(fā)展，信息系統(tǒng)及數(shù)據(jù)庫(kù)系統(tǒng)在許多領(lǐng)域得到了廣泛應(yīng)用[1]。從相對(duì)宏觀的角度分析，數(shù)據(jù)挖掘本身在學(xué)科構(gòu)成上具有較強(qiáng)的交叉性[2]，正是因?yàn)檫@一特點(diǎn)，使得其能夠在種類繁多的數(shù)據(jù)中實(shí)現(xiàn)對(duì)隱藏信息的有效提煉[3]。將數(shù)據(jù)隱藏信息轉(zhuǎn)化為一種可以被理解的結(jié)構(gòu)形式，可以對(duì)相關(guān)工作的開展起到重要的指導(dǎo)作用[4]。如王營(yíng)等通過對(duì)FP-growth 算法進(jìn)行改進(jìn)，提出了一種以售后服務(wù)數(shù)據(jù)為目標(biāo)的數(shù)據(jù)挖掘方法，提高了數(shù)據(jù)挖掘的全面性，使運(yùn)算效率存在提升空間[5]。李瑞峰等以具有離群屬性的數(shù)據(jù)為研究對(duì)象，通過將加權(quán)深度森林融入到數(shù)據(jù)挖掘的過程中，實(shí)現(xiàn)對(duì)數(shù)據(jù)的有效分類[6]。但是，上述文獻(xiàn)涉及的方法難以滿足大規(guī)模數(shù)據(jù)的計(jì)算需求。李珺等通過對(duì)K-means 算法進(jìn)行改進(jìn)，以具有關(guān)聯(lián)規(guī)則的數(shù)據(jù)為研究目標(biāo)，設(shè)計(jì)的數(shù)據(jù)挖掘算法，提高了算法的運(yùn)算效率[7]。但受數(shù)據(jù)規(guī)模的影響，該算法與實(shí)際需求之間仍存在差距。在數(shù)據(jù)挖掘算法可靠性相對(duì)完善的背景下，運(yùn)行效率是現(xiàn)階段數(shù)據(jù)挖掘算法需要重點(diǎn)攻克的難題之一[8]。為此，本文提出基于hadoop 平臺(tái)的數(shù)據(jù)挖掘算法，借助于hadoop 平臺(tái)的并行屬性，使得算法能夠?qū)崿F(xiàn)多節(jié)點(diǎn)并行運(yùn)算，以此提高其計(jì)算效率。

一、數(shù)據(jù)挖掘算法設(shè)計(jì)

（一） 基于hadoop 平臺(tái)的數(shù)據(jù)挖掘流程設(shè)計(jì)

在傳統(tǒng)的數(shù)據(jù)挖掘算法中，主要是采用基于深度優(yōu)先的策略來(lái)構(gòu)建數(shù)據(jù)分析決策樹。這種方式需要優(yōu)先為在每個(gè)節(jié)點(diǎn)創(chuàng)建對(duì)應(yīng)的子樹，在此基礎(chǔ)上再創(chuàng)建對(duì)側(cè)的子樹結(jié)構(gòu)。這就意味著在實(shí)施對(duì)目標(biāo)數(shù)據(jù)的分析計(jì)算階段中，需要對(duì)同一節(jié)點(diǎn)待處理數(shù)據(jù)集進(jìn)行多次、重復(fù)的讀取和處理。這不僅增加了算法執(zhí)行期間的計(jì)算時(shí)間，同時(shí)也影響了算法的執(zhí)行效率，使得對(duì)應(yīng)的時(shí)長(zhǎng)增加。

針對(duì)上述問題，本研究在利用hadoop 平臺(tái)進(jìn)行數(shù)據(jù)集挖掘算法設(shè)計(jì)階段，對(duì)于決策樹的構(gòu)造采用了廣度優(yōu)先策略，通過建立層級(jí)關(guān)系實(shí)現(xiàn)對(duì)待處理數(shù)據(jù)集的逐層處理，這樣既可以減少對(duì)磁盤讀取的次數(shù)，同時(shí)也可以降低算法執(zhí)行前進(jìn)的運(yùn)行負(fù)載。以此為基礎(chǔ)，本研究利用hadoop 平臺(tái)設(shè)計(jì)的數(shù)據(jù)挖掘算法執(zhí)行流程主要從兩個(gè)角度入手。首先，要確保執(zhí)行數(shù)據(jù)挖掘算法階段按照逐層構(gòu)造的方式對(duì)決策樹進(jìn)行分析，其次，在實(shí)施對(duì)數(shù)據(jù)挖掘算法對(duì)應(yīng)決策樹節(jié)點(diǎn)的分枝操作處理時(shí)，將hadoop 平臺(tái)的MapReduce 程序調(diào)用到其中，建立算法運(yùn)算期間的并行關(guān)系。

圖1 為本研究設(shè)計(jì)的具體數(shù)據(jù)挖掘算法執(zhí)行流程。按照?qǐng)D1 所示的數(shù)據(jù)挖掘算法的執(zhí)行流程。在執(zhí)行對(duì)每一輪數(shù)據(jù)的迭代計(jì)算前，本研究將上一層節(jié)點(diǎn)的劃分規(guī)則寫入到hadoop 平臺(tái)的HDFS文件中，此時(shí)的數(shù)據(jù)挖掘算法各個(gè)層級(jí)的計(jì)算結(jié)果將以并列的方式存在。在此基礎(chǔ)上，再調(diào)用hadoop 平臺(tái)的 MapReduce 程序，計(jì)算出HDFS 文件中數(shù)據(jù)挖掘算法決策樹各節(jié)點(diǎn)對(duì)相應(yīng)數(shù)據(jù)屬性的輸出結(jié)果。

圖1 基于hadoop 平臺(tái)的數(shù)據(jù)挖掘算法執(zhí)行流程圖

需要特別注意的是，由于決策樹本身已經(jīng)構(gòu)建了對(duì)應(yīng)的層級(jí)關(guān)系，因此MapReduce 程序在對(duì)輸出結(jié)果進(jìn)行存儲(chǔ)時(shí)，也要按照層級(jí)關(guān)系逐層存儲(chǔ)。以此為基礎(chǔ)，在具體的信息存儲(chǔ)階段，為了適應(yīng)hadoop 平臺(tái)的讀取模式，本研究將其轉(zhuǎn)化為Hash 表。最后，hadoop 平臺(tái)以Hash 表為基礎(chǔ)，結(jié)合常規(guī)的N 維空間歐式距離計(jì)算公式，根據(jù)分支屬性的權(quán)重參量，計(jì)算出每個(gè)節(jié)點(diǎn)的最佳分枝屬性，過程如下：

其中，dxixj表示根據(jù)Hash 表計(jì)算出的節(jié)點(diǎn)i和j節(jié)點(diǎn)對(duì)應(yīng)分枝屬性的加權(quán)歐氏距離，xi和xj分別表示節(jié)點(diǎn)i和j節(jié)點(diǎn)對(duì)應(yīng)分枝屬性參量，表示分支屬性的權(quán)重參量，n表示數(shù)據(jù)挖掘算法分支節(jié)點(diǎn)的總量。

結(jié)合數(shù)據(jù)挖掘的精度要求，本研究將加權(quán)歐氏距離的最小值mindxixj作為分枝操作的基準(zhǔn)參量，實(shí)施對(duì)決策樹節(jié)點(diǎn)的分枝處理。通過這樣的方式，實(shí)現(xiàn)對(duì)數(shù)據(jù)挖掘流程的設(shè)計(jì)，為挖掘算法在具體運(yùn)行期間的并行運(yùn)算提供有效保障。

（二） 基于hadoop 平臺(tái)的數(shù)據(jù)挖掘算法Map設(shè)計(jì)

對(duì)于數(shù)據(jù)挖掘算法Map 階段的設(shè)計(jì)，本研究首先按照決策樹中各個(gè)層節(jié)點(diǎn)對(duì)應(yīng)的劃分條件對(duì)待處理的數(shù)據(jù)進(jìn)行劃分。假設(shè)待分析的數(shù)據(jù)集為S，通過決策樹分支處理，生成的葉子節(jié)點(diǎn)的訓(xùn)練樣本數(shù)據(jù)集為S'，那么，根據(jù)條件概率，按數(shù)據(jù)屬性特征劃分在同一層級(jí)的節(jié)點(diǎn)，過程如下：

其中，Sm表示第m層級(jí)的節(jié)點(diǎn)構(gòu)成。需要注意的是，為了在算法執(zhí)行階段出現(xiàn)節(jié)點(diǎn)交叉或節(jié)點(diǎn)重復(fù)計(jì)算的情況，本研究為Sm建立了約束條件，及任意層級(jí)的節(jié)點(diǎn)構(gòu)成不存在包含關(guān)系，通過這樣的方式確保各個(gè)層級(jí)節(jié)點(diǎn)之間沒有交集。

在此基礎(chǔ)上，本研究對(duì)數(shù)據(jù)挖掘算法Map 函數(shù)的設(shè)計(jì)是以單個(gè)數(shù)據(jù)形式處理，以鍵值對(duì)的形式輸出，這就意味對(duì)于任意待分析的數(shù)據(jù)，利用Map 函數(shù)對(duì)其的處理方式可以表示為：

其中，M（Sm） 表示數(shù)據(jù)挖掘算法的Map 函數(shù)，Sm表示輸入的單個(gè)待分析數(shù)據(jù)參量，dmax表示決策樹的最大加權(quán)歐氏距離，dsm表示第m層級(jí)加權(quán)歐氏距離，通過這樣的方式，計(jì)算得到第m層級(jí)輸出的待分析數(shù)據(jù)對(duì)應(yīng) 鍵值對(duì)具體參量。

根據(jù)數(shù)據(jù)挖掘算法各個(gè)節(jié)點(diǎn)輸出鍵值對(duì)的違約情況即可實(shí)現(xiàn)對(duì)其對(duì)應(yīng)數(shù)據(jù)的分類。其具體的計(jì)算方式可以表示為：

其中，P表示設(shè)置的數(shù)據(jù)分類基準(zhǔn)參量，其具體的取值結(jié)果與數(shù)據(jù)的實(shí)際屬性和分類標(biāo)準(zhǔn)為基礎(chǔ)設(shè)置。在式（4） 中，對(duì)于分類結(jié)果的計(jì)算是以單一指標(biāo)為基礎(chǔ)進(jìn)行的，結(jié)合實(shí)際的數(shù)據(jù)處理需求，可以對(duì)P值進(jìn)行適應(yīng)性調(diào)節(jié)，包括其取值范圍、大小以及數(shù)量，以此來(lái)確保數(shù)據(jù)分析的結(jié)果能夠與實(shí)際分析需求之間具有較高的契合度。通過這樣的方式，數(shù)據(jù)挖掘算法決策樹能夠?qū)崿F(xiàn)對(duì)數(shù)據(jù)的分級(jí)并行處理，提高分析的效率。

二、應(yīng)用測(cè)試與分析

為進(jìn)一步分析本文設(shè)計(jì)的基于hadoop 平臺(tái)的數(shù)據(jù)挖掘算法的設(shè)計(jì)執(zhí)行效果，設(shè)計(jì)了如下應(yīng)用測(cè)試過程。

（一） 測(cè)試環(huán)境準(zhǔn)確

在本研究構(gòu)建的測(cè)試環(huán)境中，對(duì)應(yīng)集群的計(jì)算機(jī)器數(shù)量為4 臺(tái)，為每臺(tái)計(jì)算機(jī)硬件配置了千兆以太網(wǎng)，以此滿足其運(yùn)行的需求，對(duì)應(yīng)的CPU參數(shù)信息為Intel8 Core（IM） i5-2450M@4.0GHz?？紤]到參與測(cè)試數(shù)據(jù)規(guī)模較大，在8.0GB DDR3 內(nèi)存的基礎(chǔ)上，為計(jì)算機(jī)搭載了大小為500G 的普通硬盤裝置。其次就是對(duì)測(cè)試環(huán)境軟件的設(shè)置，本研究以red hat10.0 操作系統(tǒng)作為測(cè)試運(yùn)行的主體，利用Java_1.8.0_12 實(shí)施對(duì)相關(guān)邏輯指令的編碼，結(jié)合Hadoop2.5.0 和HBase 0.94.23 共同構(gòu)建測(cè)試環(huán)境的框架結(jié)構(gòu)。

在對(duì)Hadoop 云計(jì)算平臺(tái)進(jìn)行具體搭建的過程中，本研究將參與測(cè)試的4 臺(tái)計(jì)算機(jī)中的一臺(tái)作為NameNode 節(jié)點(diǎn)，其余則作為DataNode 節(jié)點(diǎn)，并且為了降低測(cè)試節(jié)點(diǎn)的時(shí)間開銷，為其配置了ssh，并設(shè)置了無(wú)密碼登陸機(jī)制，在此基礎(chǔ)上為其配置 core-site. xml、hdfis-sit.e xml、 mapred-site. Xml以此滿足測(cè)試階段對(duì)數(shù)據(jù)的處理需求。在運(yùn)行階段，通過啟動(dòng)NameNode 進(jìn)程使得sh Hadop/bin/stat-dfs.sh start 腳本能夠在主節(jié)點(diǎn)上順利運(yùn)行，對(duì)應(yīng)的DataNode 節(jié)點(diǎn)運(yùn)行DataNode 進(jìn)程。

（二） 測(cè)試數(shù)據(jù)準(zhǔn)備

在測(cè)試數(shù)據(jù)準(zhǔn)備階段，為了保障測(cè)試結(jié)果的可靠性，降低由于測(cè)試數(shù)據(jù)異常對(duì)此測(cè)試結(jié)果的影響，本研究以機(jī)器學(xué)習(xí)網(wǎng)站（htp://ftp.ics.uic. edu/pub/machine-learming-databases/iris） 中 的 權(quán) 威實(shí)驗(yàn)數(shù)據(jù)作為本文測(cè)試的數(shù)據(jù)信息。其中，數(shù)據(jù)集中包含元素的總量為210 個(gè)，根據(jù)元素類型可以將其劃分為三大類，對(duì)應(yīng)每個(gè)類別中包含元素?cái)?shù)量為70 個(gè)。在此基礎(chǔ)上，本研究結(jié)合海量數(shù)據(jù)挖掘算法的測(cè)試需求，按照不同類別數(shù)據(jù)的實(shí)際維度信息，利用代碼對(duì)上述數(shù)據(jù)進(jìn)行拓展處理，生成了3 組測(cè)試數(shù)據(jù)集，對(duì)應(yīng)的數(shù)據(jù)集大小及維度：測(cè)試數(shù)據(jù)集1 的數(shù)據(jù)規(guī)模為100.26M，維度為30；測(cè)試數(shù)據(jù)集2 的數(shù)據(jù)規(guī)模為500.33M，維度為40；測(cè)試數(shù)據(jù)集3 的數(shù)據(jù)規(guī)模為1.52GB，維度為50。

（三） 評(píng)價(jià)指標(biāo)設(shè)置

在對(duì)算法的執(zhí)行效果進(jìn)行評(píng)價(jià)階段，本研究結(jié)合數(shù)據(jù)挖掘的實(shí)際需求，分別以分類運(yùn)算的時(shí)間開銷以及加速比作為評(píng)價(jià)指標(biāo)。其中，分類運(yùn)算時(shí)間開銷主要算法計(jì)算開始執(zhí)行的時(shí)刻到結(jié)束的時(shí)刻之間的時(shí)間差，其直接體現(xiàn)了算法的運(yùn)算效率，具體的計(jì)算方式可以表示為：

其中，t表示算法執(zhí)行分類運(yùn)算的時(shí)間開銷，Te表示算法開始執(zhí)行運(yùn)算的時(shí)間參量，Ts表示算法完成運(yùn)算的時(shí)間參量。按照式（5） 所示，在以相同測(cè)試數(shù)據(jù)集進(jìn)行分類處理時(shí)，算法的時(shí)間開銷越小，表示算法的運(yùn)算速度越快，對(duì)應(yīng)的運(yùn)算效率越高。

其次就是算法的加速比，其主要是指在對(duì)同一個(gè)測(cè)試數(shù)據(jù)集進(jìn)行處理時(shí)，單計(jì)算節(jié)點(diǎn)和多節(jié)點(diǎn)并行對(duì)應(yīng)的時(shí)間開銷比值。其直接體現(xiàn)了算法的并行能力，具體的計(jì)算方式可以表示為：

其中，a表示算法的加速比，td表示單個(gè)運(yùn)算節(jié)點(diǎn)執(zhí)行運(yùn)算的時(shí)間開銷，tb表示運(yùn)算節(jié)點(diǎn)集群下執(zhí)行運(yùn)算的時(shí)間開銷。根據(jù)式（6） 可以看出，算法的加速比越大，表明其在處理大規(guī)模數(shù)據(jù)階段的性能越好。

（四） 測(cè)試結(jié)果與分析

在上述基礎(chǔ)上，本研究在測(cè)試結(jié)果引入了對(duì)照組，分別以文獻(xiàn)[6]中提出的以加權(quán)深度森林為基礎(chǔ)的數(shù)據(jù)挖掘算法和文獻(xiàn)[7]中提出的以改進(jìn)K-means 為基礎(chǔ)的數(shù)據(jù)挖掘算法作為對(duì)照組的應(yīng)用算法。在此基礎(chǔ)上，分別對(duì)比三種算法的執(zhí)行效果。其中，得到的分類運(yùn)算的時(shí)間開銷如表1 所示。

表1 不同算法分類運(yùn)算時(shí)間開銷對(duì)比表

從表1 中可以看出，對(duì)比三種算法的測(cè)試結(jié)果，其中，當(dāng)測(cè)試數(shù)據(jù)集的數(shù)據(jù)規(guī)模較小時(shí)（測(cè)試數(shù)據(jù)集1），三種算法對(duì)應(yīng)的分類運(yùn)算時(shí)間開銷并未表現(xiàn)出明顯差異，但是隨著測(cè)試數(shù)據(jù)集數(shù)據(jù)規(guī)模的不斷增加，文獻(xiàn)[6]和文獻(xiàn)[7]算法的時(shí)間開銷均呈現(xiàn)出了較為明顯的上升趨勢(shì)，在數(shù)據(jù)規(guī)模以接近倍數(shù)的模式增加時(shí)，時(shí)間開銷的上升幅度明顯高于數(shù)據(jù)規(guī)模的增長(zhǎng)幅度，當(dāng)測(cè)試數(shù)據(jù)集的數(shù)據(jù)規(guī)模達(dá)到1.52GB 時(shí)（測(cè)試數(shù)據(jù)集3），兩種算法的時(shí)間開銷均達(dá)到了100.0s 以上。相比之下，本研究設(shè)計(jì)算法的時(shí)間開銷表現(xiàn)出與數(shù)據(jù)規(guī)模的增長(zhǎng)幅度較高的一致性，其中，當(dāng)測(cè)試數(shù)據(jù)集的數(shù)據(jù)規(guī)模大小為100.26M 時(shí)（測(cè)試數(shù)據(jù)集1），分類運(yùn)算的時(shí)間開銷為4.55s，當(dāng)測(cè)試數(shù)據(jù)集的數(shù)據(jù)規(guī)模大小為1.52GB 時(shí)（測(cè)試數(shù)據(jù)集3），執(zhí)行分類運(yùn)算的時(shí)間開銷為62.44s，與文獻(xiàn)[6]和文獻(xiàn)[7]算法相比，分別降低了37.78s 和37.74s，具有較為明顯的優(yōu)勢(shì)。測(cè)試結(jié)果表明，本研究設(shè)計(jì)的基于hadoop 平臺(tái)的數(shù)據(jù)挖掘算法具有較高的運(yùn)算效率。

其次，本研究統(tǒng)計(jì)了三種算法在運(yùn)算過程中的加速比，得到的數(shù)據(jù)結(jié)果如圖2 所示。

圖2 不同算法加速比對(duì)比圖

在對(duì)加速比進(jìn)行測(cè)試的階段，本研究按照測(cè)試環(huán)境的設(shè)置情況，令集群節(jié)點(diǎn)數(shù)量為4 個(gè)。在此基礎(chǔ)上，對(duì)比圖2 中三種算法的加速比可以看出，文獻(xiàn)[6]算法對(duì)應(yīng)的加速比最大值為2.80，文獻(xiàn)[7]算法對(duì)應(yīng)的加速比最大值為3.12，相比之下，本研究設(shè)計(jì)算法的加速比最大值達(dá)到了3.96，明顯高于另外兩種對(duì)比方法。

上述測(cè)試結(jié)果表明，本研究設(shè)計(jì)的基于hadoop 平臺(tái)的數(shù)據(jù)挖掘算法具有較高加速比，能夠滿足海量數(shù)據(jù)在分析效率上的需求。

三、結(jié)語(yǔ)

在數(shù)據(jù)集規(guī)模不斷擴(kuò)大，數(shù)據(jù)復(fù)雜度不斷增加的環(huán)境下，如何實(shí)現(xiàn)對(duì)數(shù)據(jù)的快速處理成為了數(shù)據(jù)挖掘算法亟需解決的問題。在此基礎(chǔ)上，為了實(shí)現(xiàn)對(duì)海量數(shù)據(jù)中潛在價(jià)值的有效獲取，發(fā)揮其在實(shí)際工作中的作用，實(shí)施可靠的數(shù)據(jù)挖掘技術(shù)成為了重要的內(nèi)容之一。

Hadoop 作為一種開源分布式計(jì)算平臺(tái)，將其融入到數(shù)據(jù)挖掘算法中將提高其運(yùn)算效率。本研究提出基于hadoop 平臺(tái)的數(shù)據(jù)挖掘算法及實(shí)現(xiàn)研究，提高了算法在運(yùn)行階段的效率，能夠滿足海量數(shù)據(jù)的處理需求。通過本次研究以期為相關(guān)數(shù)據(jù)的處理工作提供參考借鑒，助力大數(shù)據(jù)在實(shí)際工作中發(fā)揮更大作用。