基于分布式環境的數據挖掘算法研究

姜文秀

摘要：隨著海量數據處理的關注程度逐漸提升，分布式數據挖掘算法也成為一個熱點研究領域。在實際挖掘特定興趣時，會用到數據挖掘中的關聯規則，數據的海量性必然要求采用分布式挖掘方法，以此減輕計算壓力。分布式環境中的數據挖掘可以將數據分發到不同節點進行處理，最后將局部結果匯總，從而完成整個計算過程。

關鍵詞：分布式;數據挖掘;關聯規則;分類;聚類

中圖分類號：G642? ? ? ? 文獻標識碼：A? ? ? ? 文章編號：1009-3044（2019）02-0232-02

隨著知識發現應用于各個領域，數據挖掘技術扮演的角色也越來越重要;由于通常會涉及海量的數據，因此實際應用數據挖掘過程中通常會采取分布式技術，以緩解海量數據帶來的計算壓力。

傳統的數據挖掘技術存在一個中央服務器，將其他各個節點采集到的數據通過數據倉庫匯總到中心服務器后，再進行數據挖掘或其他運算;但是，這種中心化的節點在面臨龐大的數據量時可能會存在性能瓶頸;除此之外，其他節點同時將大量的數據匯總到中心服務器時也會需要大量的帶寬，而且匯總過程中也還會面臨一定的數據安全問題。

分布式數據挖掘算法可以克服傳統的數據挖掘算法中存在的中心化單點問題，另外，由于分布式數據挖掘環境是建立在多個服務器上的，因此這種并行計算能力提高了整體的數據挖掘效率;相比傳統的數據挖掘算法而言，分布式數據挖掘算法在處理的數據量以及效率方面都有很大的優勢。

1 分布式技術

作為基于分布式計算環境的軟件，Hadoop能夠在很大程度上解決數據不斷增長的問題：有一個分布式文件系統HDFS以及分布式編程模型MapReduce。新一代架構的Hadoop2.0支持集群橫向擴展，甚至可以支持成千上萬臺服務器機器，大大提高了計算能力;HDFS文件系統不僅可以處理常見的文本數據，還能夠處理結構化及非結構化數據。最重要的是，Hadoop具有強大的容錯機制，其冗余備份機制能夠有效處理集群節點的異常突發情況。

Hadoop中包含一個分布式存儲HDFS，提供了相應的api，以完成諸如創建文件、讀寫文件、刪除/移動文件等操作。Hadoop集群中有一個主控服務器Namenode，負責維護整個HDFS文件系統的目錄結構，并管理數據block和其他數據節點之間的關系，還會保存一些元數據信息，比如文件名、文件副本數目和位置等[1]。Hadoop集群中的其他節點是數據節點Datanode，主要功能是存放數據副本。為了實現冗余備份的目的，每個文件都會有多個數據副本。

傳統的數據挖掘計算模型中，計算操作一般都是在一臺中心服務器上進行，但是單機環境勢必會存在計算瓶頸。Hadoop中的MapReduce計算框架可以克服傳統的中心式計算的缺陷，在將數據量很大的計算任務分塊存儲后，把計算問題分解成多個子任務，以此轉換為支持并行運行的Map任務和Reduce任務。

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

2 分布式數據挖掘方法

分布式數據挖掘方法涉及很多方面，接下來主要介紹分布式文本分類算法、關聯規則算法以及分布式聚類算法。

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

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

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

3 分布式數據挖掘算法的應用

可以將分布式數據挖掘算法應用于微博熱點分析，包括數據預處理、文本預處理、特征提取處理、熱點分析等步驟。

在分析微博熱點時，本文采用的是阿里巴巴天池比賽的新浪微博預測大賽數據，包括了一定時間內新浪微博的用戶轉發數、評論數以及點贊數等，能夠真實反映微博用戶的關注領域、評論的心理特征等。

數據預處理是分布式數據挖掘的基礎，對于微博數據來說，需要對以下數據進行預處理：一天之內的重復微博數據、以URL為主體的數據。以URL為主體的微博數據可能是網站推廣或廣告營銷，這樣的數據如果大量存在，則可以采取過濾刪除的處理方式。對于一天內的重復微博數據，則需要根據實際的微博內容進行合并處理。Hadoop平臺中的Hive組件可以針對結構化數據文件完成sql操作，sql語句被轉換為MapReduce任務運行，實現對數據的預處理。

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

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

選擇微博數據的轉發數、點贊數以及評論數作為特征向量，使用此特征向量實現分布式數據挖掘k-means算法。

4 總結

本文對分布式的數據挖掘算法進行研究，首先簡要介紹了分布式技術，并以此為基礎闡述了分布式數據挖掘算法;最后，對分布式數據挖掘算法的應用進行了研究。

參考文獻：

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

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

[3] 陳湘濤，張超，韓茜.基于Hadoop的并行共享決策樹挖掘算法研究[f].計算機科學，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的面向服務數據挖掘原型系統的設計與實現[J].計算機應用與軟件，2016（2）：41-43.