基于分布式環(huán)境的數(shù)據(jù)挖掘算法研究

姜文秀

摘要：隨著海量數(shù)據(jù)處理的關(guān)注程度逐漸提升，分布式數(shù)據(jù)挖掘算法也成為一個(gè)熱點(diǎn)研究領(lǐng)域。在實(shí)際挖掘特定興趣時(shí)，會(huì)用到數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則，數(shù)據(jù)的海量性必然要求采用分布式挖掘方法，以此減輕計(jì)算壓力。分布式環(huán)境中的數(shù)據(jù)挖掘可以將數(shù)據(jù)分發(fā)到不同節(jié)點(diǎn)進(jìn)行處理，最后將局部結(jié)果匯總，從而完成整個(gè)計(jì)算過程。

關(guān)鍵詞：分布式;數(shù)據(jù)挖掘;關(guān)聯(lián)規(guī)則;分類;聚類

中圖分類號(hào)：G642? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? 文章編號(hào)：1009-3044（2019）02-0232-02

隨著知識(shí)發(fā)現(xiàn)應(yīng)用于各個(gè)領(lǐng)域，數(shù)據(jù)挖掘技術(shù)扮演的角色也越來越重要;由于通常會(huì)涉及海量的數(shù)據(jù)，因此實(shí)際應(yīng)用數(shù)據(jù)挖掘過程中通常會(huì)采取分布式技術(shù)，以緩解海量數(shù)據(jù)帶來的計(jì)算壓力。

傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)存在一個(gè)中央服務(wù)器，將其他各個(gè)節(jié)點(diǎn)采集到的數(shù)據(jù)通過數(shù)據(jù)倉(cāng)庫(kù)匯總到中心服務(wù)器后，再進(jìn)行數(shù)據(jù)挖掘或其他運(yùn)算;但是，這種中心化的節(jié)點(diǎn)在面臨龐大的數(shù)據(jù)量時(shí)可能會(huì)存在性能瓶頸;除此之外，其他節(jié)點(diǎn)同時(shí)將大量的數(shù)據(jù)匯總到中心服務(wù)器時(shí)也會(huì)需要大量的帶寬，而且匯總過程中也還會(huì)面臨一定的數(shù)據(jù)安全問題。

分布式數(shù)據(jù)挖掘算法可以克服傳統(tǒng)的數(shù)據(jù)挖掘算法中存在的中心化單點(diǎn)問題，另外，由于分布式數(shù)據(jù)挖掘環(huán)境是建立在多個(gè)服務(wù)器上的，因此這種并行計(jì)算能力提高了整體的數(shù)據(jù)挖掘效率;相比傳統(tǒng)的數(shù)據(jù)挖掘算法而言，分布式數(shù)據(jù)挖掘算法在處理的數(shù)據(jù)量以及效率方面都有很大的優(yōu)勢(shì)。

1 分布式技術(shù)

作為基于分布式計(jì)算環(huán)境的軟件，Hadoop能夠在很大程度上解決數(shù)據(jù)不斷增長(zhǎng)的問題：有一個(gè)分布式文件系統(tǒng)HDFS以及分布式編程模型MapReduce。新一代架構(gòu)的Hadoop2.0支持集群橫向擴(kuò)展，甚至可以支持成千上萬(wàn)臺(tái)服務(wù)器機(jī)器，大大提高了計(jì)算能力;HDFS文件系統(tǒng)不僅可以處理常見的文本數(shù)據(jù)，還能夠處理結(jié)構(gòu)化及非結(jié)構(gòu)化數(shù)據(jù)。最重要的是，Hadoop具有強(qiáng)大的容錯(cuò)機(jī)制，其冗余備份機(jī)制能夠有效處理集群節(jié)點(diǎn)的異常突發(fā)情況。

Hadoop中包含一個(gè)分布式存儲(chǔ)HDFS，提供了相應(yīng)的api，以完成諸如創(chuàng)建文件、讀寫文件、刪除/移動(dòng)文件等操作。Hadoop集群中有一個(gè)主控服務(wù)器Namenode，負(fù)責(zé)維護(hù)整個(gè)HDFS文件系統(tǒng)的目錄結(jié)構(gòu)，并管理數(shù)據(jù)block和其他數(shù)據(jù)節(jié)點(diǎn)之間的關(guān)系，還會(huì)保存一些元數(shù)據(jù)信息，比如文件名、文件副本數(shù)目和位置等[1]。Hadoop集群中的其他節(jié)點(diǎn)是數(shù)據(jù)節(jié)點(diǎn)Datanode，主要功能是存放數(shù)據(jù)副本。為了實(shí)現(xiàn)冗余備份的目的，每個(gè)文件都會(huì)有多個(gè)數(shù)據(jù)副本。

傳統(tǒng)的數(shù)據(jù)挖掘計(jì)算模型中，計(jì)算操作一般都是在一臺(tái)中心服務(wù)器上進(jìn)行，但是單機(jī)環(huán)境勢(shì)必會(huì)存在計(jì)算瓶頸。Hadoop中的MapReduce計(jì)算框架可以克服傳統(tǒng)的中心式計(jì)算的缺陷，在將數(shù)據(jù)量很大的計(jì)算任務(wù)分塊存儲(chǔ)后，把計(jì)算問題分解成多個(gè)子任務(wù)，以此轉(zhuǎn)換為支持并行運(yùn)行的Map任務(wù)和Reduce任務(wù)。

可以使用一個(gè)計(jì)算單詞數(shù)目的經(jīng)典程序來分析MapReduce計(jì)算模型的分布式計(jì)算思想。WordCount程序的設(shè)計(jì)思路是：把文本文件的內(nèi)容以單詞為依據(jù)進(jìn)行劃分，并統(tǒng)計(jì)相同單詞出現(xiàn)的次數(shù)。具體的MapReduce分布式計(jì)算過程是[2]：（1）Mapper過程。此階段的主要任務(wù)是從HDFS文件系統(tǒng)中讀取數(shù)據(jù)，并把這些數(shù)據(jù)轉(zhuǎn)換為數(shù)據(jù)挖掘算法可以處理的結(jié)構(gòu);這一階段會(huì)把文本信息以單詞為粒度進(jìn)行拆分，得到形如key-value形式的結(jié)果;以拆分的單詞Hello出現(xiàn)1次為例，保存結(jié)果就是。（2）Reduce過程。同一機(jī)器上Map操作的結(jié)果中，相同key的值在經(jīng)過合并后作為Reduce的輸入，在經(jīng)過排序后得到最終的結(jié)果。

2 分布式數(shù)據(jù)挖掘方法

分布式數(shù)據(jù)挖掘方法涉及很多方面，接下來主要介紹分布式文本分類算法、關(guān)聯(lián)規(guī)則算法以及分布式聚類算法。

分布式文本分類算法的基礎(chǔ)是MapReduce計(jì)算思想，并結(jié)合了樸素貝葉斯分類算法。樸素貝葉斯分類算法的思想如圖1所示：

在樸素貝葉斯分類算法的基礎(chǔ)上，分布式貝葉斯分類算法主要包括三個(gè)過程：使用訓(xùn)練集進(jìn)行Map操作，使用訓(xùn)練集進(jìn)行Reduce操作，使用測(cè)試集進(jìn)行Map操作。具體的分類流程是[3]：（1）將文件序列化。Hadoop將普通的文本文件處理為使用key-value格式進(jìn)行存儲(chǔ)的文件類型，key存放目錄名或文件名，value存放文件內(nèi)容。（2）向量化序列文件。把上一步得到的序列化轉(zhuǎn)換為有序字符串列表，即為經(jīng)過分詞后的有序文本信息。用這些有序文本信息生成詞頻向量，在計(jì)算每個(gè)詞匯出現(xiàn)次數(shù)的基礎(chǔ)上，把結(jié)果保存在wordcount文件內(nèi)。把序列化文件進(jìn)行向量化的算法如圖2所示。（3）使用訓(xùn)練集生成訓(xùn)練器。根據(jù)向量化的序列文件創(chuàng)建緩存，以便存儲(chǔ)每個(gè)分類label對(duì)應(yīng)的ID，并把每個(gè)分類label對(duì)應(yīng)的所有向量匯總起來，得到每個(gè)特征的權(quán)重。（4）進(jìn)行分類。前面步驟中得到的中，key就是分類類別，value是此分類對(duì)應(yīng)的分值?？梢愿鶕?jù)分類的最高分確定類別。

數(shù)據(jù)挖掘中，關(guān)聯(lián)規(guī)則算法的目的是找出數(shù)據(jù)集中的頻繁項(xiàng)集合。FP-Growth是一種常用的關(guān)聯(lián)規(guī)則算法，會(huì)執(zhí)行兩次遍歷數(shù)據(jù)庫(kù)的操作：第一次是開始的時(shí)候遍歷數(shù)據(jù)庫(kù)生成單項(xiàng)頻繁項(xiàng)集，第二次是進(jìn)行分布式關(guān)聯(lián)優(yōu)化，以緩解單機(jī)的壓力。其主要流程是[4]：（1）樣本被分塊輸入到Hadoop集群中的各個(gè)節(jié)點(diǎn)，Map程序從HDFS系統(tǒng)中得到本節(jié)點(diǎn)的，mapper后得到形如的數(shù)據(jù)記錄，輸出是。Reduce程序的輸入是，。value值會(huì)被累加，這樣就可以將項(xiàng)Ri按照支持度從大到小的順序進(jìn)行排序。同時(shí)，按照key的不同分為多個(gè)組，每個(gè)組有一個(gè)唯一標(biāo)識(shí)group_id。（2）把和上一步得到的項(xiàng)支持度表組成一個(gè)數(shù)據(jù)表，并把group_id相同的數(shù)據(jù)盡量發(fā)送到同一個(gè)節(jié)點(diǎn)。在這個(gè)節(jié)點(diǎn)上挖掘頻繁模式，得到形如的結(jié)果。（3）改進(jìn)與優(yōu)化。在根據(jù)group_id分配數(shù)據(jù)時(shí)，可能會(huì)使同一個(gè)group_id的數(shù)據(jù)被分配到不同節(jié)點(diǎn)上，因此會(huì)導(dǎo)致某一key=item的頻繁項(xiàng)集合不在本地節(jié)點(diǎn)上。為了解決這一問題，可以將mapper的輸入key修改為FP-tree上的item，mapper的輸出為，最終的結(jié)果就是。

3 分布式數(shù)據(jù)挖掘算法的應(yīng)用

可以將分布式數(shù)據(jù)挖掘算法應(yīng)用于微博熱點(diǎn)分析，包括數(shù)據(jù)預(yù)處理、文本預(yù)處理、特征提取處理、熱點(diǎn)分析等步驟。

在分析微博熱點(diǎn)時(shí)，本文采用的是阿里巴巴天池比賽的新浪微博預(yù)測(cè)大賽數(shù)據(jù)，包括了一定時(shí)間內(nèi)新浪微博的用戶轉(zhuǎn)發(fā)數(shù)、評(píng)論數(shù)以及點(diǎn)贊數(shù)等，能夠真實(shí)反映微博用戶的關(guān)注領(lǐng)域、評(píng)論的心理特征等。

數(shù)據(jù)預(yù)處理是分布式數(shù)據(jù)挖掘的基礎(chǔ)，對(duì)于微博數(shù)據(jù)來說，需要對(duì)以下數(shù)據(jù)進(jìn)行預(yù)處理：一天之內(nèi)的重復(fù)微博數(shù)據(jù)、以URL為主體的數(shù)據(jù)。以URL為主體的微博數(shù)據(jù)可能是網(wǎng)站推廣或廣告營(yíng)銷，這樣的數(shù)據(jù)如果大量存在，則可以采取過濾刪除的處理方式。對(duì)于一天內(nèi)的重復(fù)微博數(shù)據(jù)，則需要根據(jù)實(shí)際的微博內(nèi)容進(jìn)行合并處理。Hadoop平臺(tái)中的Hive組件可以針對(duì)結(jié)構(gòu)化數(shù)據(jù)文件完成sql操作，sql語(yǔ)句被轉(zhuǎn)換為MapReduce任務(wù)運(yùn)行，實(shí)現(xiàn)對(duì)數(shù)據(jù)的預(yù)處理。

針對(duì)微博數(shù)據(jù)的短文本特性，從效率方面選擇IKAnalyzer分詞器對(duì)微博數(shù)據(jù)進(jìn)行處理。整個(gè)數(shù)據(jù)集分為9個(gè)大類，每個(gè)類中包括2000個(gè)左右訓(xùn)練樣本。對(duì)于每類數(shù)據(jù)都挖掘其頻繁項(xiàng)，以此作為微博熱點(diǎn)博文進(jìn)行展示。為了去除沒有實(shí)際意義的詞匯，諸如“你”“我”“的”等，在為FP-Growth算法選擇輸入時(shí)，把按照主題劃分的分詞數(shù)據(jù)作為輸入。

采用k-means算法劃分微博的主題，其基本原理是[5]：初始選擇若干個(gè)聚類中心，然后根據(jù)數(shù)據(jù)和聚類中心的距離，把每個(gè)數(shù)據(jù)劃分到最近的聚類;然后計(jì)算每個(gè)聚類中所有數(shù)據(jù)的均值，作為新的聚類中心，迭代進(jìn)行若干次運(yùn)算，直到滿足終止條件。

選擇微博數(shù)據(jù)的轉(zhuǎn)發(fā)數(shù)、點(diǎn)贊數(shù)以及評(píng)論數(shù)作為特征向量，使用此特征向量實(shí)現(xiàn)分布式數(shù)據(jù)挖掘k-means算法。

4 總結(jié)

本文對(duì)分布式的數(shù)據(jù)挖掘算法進(jìn)行研究，首先簡(jiǎn)要介紹了分布式技術(shù)，并以此為基礎(chǔ)闡述了分布式數(shù)據(jù)挖掘算法;最后，對(duì)分布式數(shù)據(jù)挖掘算法的應(yīng)用進(jìn)行了研究。

參考文獻(xiàn)：

[1]方少卿，周劍，張明新.基于Map/Reduee的改進(jìn)選擇算法在云計(jì)算的Web數(shù)據(jù)挖掘中的研究[J].計(jì)算機(jī)應(yīng)用研究，2018， 14（2）：255-279.

[2] 周奇年，張振浩，徐登彩.用于中文文本分類的基于類別區(qū)分詞的特征選擇方法[J].計(jì)算機(jī)應(yīng)用與軟件，2017（3）：15-26.

[3] 陳湘濤，張超，韓茜.基于Hadoop的并行共享決策樹挖掘算法研究[f].計(jì)算機(jī)科學(xué)，2013（11）：36-39.

[4] Trap N L， Dugauthier Q， Skhiri S. A Distributed Data Mining Framework Accelerated with Graphics Processing Units[C]. International Conference on Cloud Computing & Big Data. IEEE Computer Society， 2017：366-372.

[5]馬青霞，王智鋼，李廣水.基于RESTFUL的面向服務(wù)數(shù)據(jù)挖掘原型系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用與軟件，2016（2）：41-43.