基于Hadoop平臺的FCM算法并行化設計

陳陽

?

基于Hadoop平臺的FCM算法并行化設計

陳陽

（廣東省科技基礎條件平臺中心）

基于云計算平臺Hadoop的主要功能和MapReduce處理流程，設計FCM算法的并行化處理過程。

模糊C均值；MES；數(shù)據(jù)挖掘；并行化處理

0　引言

近年來，隨著移動互聯(lián)網(wǎng)、云計算、大數(shù)據(jù)等技術的快速發(fā)展及計算機計算能力的大幅提升，現(xiàn)代制造業(yè)逐漸走上了信息化、智能化轉型和升級的道路[1]。其中，制造企業(yè)生產(chǎn)過程執(zhí)行系統(tǒng)（manufacturing execution system，MES）智能化改造是企業(yè)信息化和智能化進程的關鍵內容之一。利用MES中的生產(chǎn)實時數(shù)據(jù)，結合大數(shù)據(jù)挖掘技術，跟蹤產(chǎn)品質量管理和生產(chǎn)過程，是提高生產(chǎn)效率及智能化的關鍵。

然而，MES數(shù)據(jù)量較大，大數(shù)據(jù)挖掘處理速度亟待解決。目前提高大數(shù)據(jù)挖掘處理速度的技術主要包括云計算平臺的分布式挖掘和智能算法2方面。

本文以Hadoop分布式框架為基礎，研究基于模糊C均值聚類的數(shù)據(jù)挖掘算法并行處理技術，以提高大數(shù)據(jù)挖掘處理速度。

1　基于Hadoop的海量數(shù)據(jù)分布式處理平臺

數(shù)據(jù)挖掘（data mining，DM）是指從大型數(shù)據(jù)庫或者數(shù)據(jù)倉庫中找出隱含的、當前未知的、非凡的以及有潛在應用價值的信息或者模式[2]。數(shù)據(jù)挖掘主要經(jīng)歷基于網(wǎng)格計算的分布式挖掘和基于云計算平臺的分布式挖掘2個階段。目前數(shù)據(jù)挖掘研究大多集中在云計算平臺，其主要特點是使用多個計算節(jié)點對算法進行運算，分配規(guī)則是根據(jù)算法所需要的資源，在云端實現(xiàn)數(shù)據(jù)存儲和運算。其中基于Hadoop分布式框架的云計算分布式挖掘是當前研究熱點[3]。

Hadoop平臺主要由MapReduce，Pig，HDFS，Hive和HBase等部分組成[4]。其中MapReduce（分布式計算）是算法處理核心，主要包括Map和Reduce 2個計算過程，處理流程圖如圖1所示[5]。此外，目前對于海量數(shù)據(jù)的處理，借助Combine函數(shù)對Map函數(shù)的輸出進行合并，以減少傳輸?shù)絉educe函數(shù)的數(shù)據(jù)量，從而提高數(shù)據(jù)處理效率。

圖1　MapReduce處理流程圖

2　模糊C均值聚類算法

聚類算法是數(shù)據(jù)挖掘技術中的一類常用、高效的算法。模糊C均值聚類（Fuzzy C-Means，F(xiàn)CM）算法是以類內加權誤差平方和作為目標函數(shù)的一類聚類方法[6]，算法基本流程如圖2所示。

圖2　FCM算法基本流程圖

FCM算法的具體步驟描述如下：

1）初始化，對個樣本={1,2,3,…,x}進行類劃分，設置迭代定制閾值和最大迭代次數(shù)；初始化聚類原型矩陣，給定加權指數(shù)；初始化迭代起始數(shù)，即給置0；

2）利用式(1)計算或更新劃分矩陣

3）利用式(2)更新聚類原型矩陣

4）利用式(3)計算當前目標函數(shù)值，若目標函數(shù)值小于閾值或達到迭代次數(shù)，則輸出劃分矩陣和聚類原型矩陣的值；否則，令=+1，轉步驟2）。

3　FCM算法并行化設計

根據(jù)FCM算法原理，每個數(shù)據(jù)對象到個聚類中心的隸屬度計算是相互獨立的，且比較耗費計算資源。因此，對這一過程進行并行化設計。

在Hadoop平臺中，F(xiàn)CM算法的并行化設計和實現(xiàn)，實質就是將算法進行MapReduce化，即實現(xiàn)Map和Reduce過程，具體工作包括：1）輸入和輸出鍵值對設計；2）函數(shù)的具體實現(xiàn)邏輯。基于Hadoop平臺的FCM算法并行化過程如圖3所示。

4　FCM算法并行化實現(xiàn)

基于Hadoop平臺的FCM算法并行化實現(xiàn)主要步驟：1） Map函數(shù)實現(xiàn)；2） Combine函數(shù)實現(xiàn)；3） Reduce函數(shù)實現(xiàn)。

1） Map函數(shù)實現(xiàn)

Map函數(shù)的作用是讀取待分類數(shù)據(jù)和當前個聚類中心的值，并計算各個數(shù)據(jù)分別對個聚類中心的距離、隸屬度、隸屬度與數(shù)據(jù)的乘積和。Map函數(shù)形式為鍵值對，其中是當前數(shù)據(jù)的行偏移量；是當前對象各個維度坐標值的行記錄。Map函數(shù)的實現(xiàn)過程就是從字符串中得到源數(shù)據(jù)/對象與個聚類中心的隸屬度，最后輸出形如<2,2>的返回值。

圖3　基于Hadoop平臺的FCM算法并行化過程圖

Map函數(shù)設計與實現(xiàn)的偽代碼為：

map(<,>,<2,2>){

從中解析出當前數(shù)據(jù)對象，記為Source={S|1,2,…,S}；

得到個聚類中心={v|1,2,…,v}；

初始化各數(shù)據(jù)點到個聚類中心的距離總和SUM_Distance=0

for(=1;≤;++){

_distance[]=Math.norm([])；

SUM_Distance=SUM_Distance+Math.pow(1/(_ distance[]*_distance[]),-1);

}

for(1){

_menbership[]= Math.pow(1/(_distance[]*_distance[]),-1)/SUM_Distance;

}

for(=1;++){

Temp_P[]= Math.pow(_menbership[], b)*[];

}

2個聚類中心的ID

2= (_menbership[], Temp_P[])；

函數(shù)返回<22>；

}

2）Combine函數(shù)實現(xiàn)

Combine函數(shù)的主要作用是對Map函數(shù)的輸出結果（隸屬度和隸屬度與數(shù)據(jù)點的乘積和集）進行整理和排序，從而保證后續(xù)Reduce函數(shù)的輸入?yún)?shù)能夠按照值對Map階段的輸出結果進行分組。因此，Combine函數(shù)的輸入?yún)?shù)為Map函數(shù)的輸出22，其中，2代表當前C聚類中心的ID；2代表隸屬度的值以及數(shù)據(jù)點的乘積和。

Combine函數(shù)設計與實現(xiàn)的偽代碼為：

map(<2,2>,<3,3>){

創(chuàng)建一個存儲空間，存儲同一個聚類中心的相關數(shù)據(jù)；

for(=1;≤;++){

for(=1;≤;++);

While(value.hasNext()){

調用value.nex()得到屬于第個聚類中心的數(shù)據(jù)；

將調出來的數(shù)據(jù)存入到對應的數(shù)組中；

}

}

3=2;

3=重新分配的數(shù)據(jù)組；

函數(shù)返回<3,3>；

}

3）Reduce函數(shù)實現(xiàn)

Map函數(shù)和Combine函數(shù)的處理結果經(jīng)過Reduce函數(shù)的計算得到聚類更新后的聚類中心點，然后進行迭代，即進入新一輪的Map，Reduce過程。Reduce函數(shù)的輸入?yún)?shù)格式為<33>鍵值對，其中3值表示聚類中心下標，3是Combine函數(shù)的計算結果。

Reduce函數(shù)設計與實現(xiàn)的偽代碼為：

map(<3,3>,<4,4>){

初始化所有數(shù)據(jù)點與隸屬度乘積和的總和為SUM1=0；

初始化所有數(shù)據(jù)點的隸屬度總和為SUM2=0；

for(=1;≤;++){

SUM1[]=SUM1[]+Temp_P[];

SUM2=SUM2[]+_menbership[];

}

for(=1;≤;++){

New_C[]=SUM1[]/SUM2[];

}

4=3;

3=更新后的個聚類中心的ID；

函數(shù)返回<4,4>；

}

5　應用實例

本實驗數(shù)據(jù)是某塑料制品加工企業(yè)MES中存儲的手機前蓋加工數(shù)據(jù)，包括生產(chǎn)設備信息、塑料原料信息、料筒溫度信息、合模壓力信息、鎖模壓力信息、螺桿位置信息、頂針位置信息、模具位置信息和制品檢測信息等。通過對這些數(shù)據(jù)進行基于模糊C均值聚類的MapReduce并行化處理，實現(xiàn)手機前蓋加工質量等級的分類。將該加工數(shù)據(jù)按樣本大小逐級遞增分為3組，如表1所示，要求生成3個聚類，分別是合格、次品和廢品。

表1 實驗數(shù)據(jù)集分組情況

加速比是算法在單節(jié)點與多節(jié)點上聚類給定數(shù)據(jù)集中數(shù)據(jù)對象執(zhí)行時間的比值，是衡量并行系統(tǒng)性能或程序并行化效果和擴展性的重要指標[7]。本文利用加速比來驗證算法的并行化效果。

分別設置1到10個節(jié)點進行運算，得到的實驗結果如圖4所示。

圖4 基于模糊C均值聚類的MapReduce并行化處理實驗結果

實驗結果表明：該算法的加速比隨著節(jié)點數(shù)的增加呈相對線性增長，即具有良好的加速比性能，且對于不同大小的數(shù)據(jù)集，加速比性能穩(wěn)定。

6　結語

本文介紹了FCM在Hadoop平臺的MapReduce并行化處理過程的設計與實現(xiàn)，為MES的數(shù)據(jù)挖掘算法并行處理技術提供借鑒和參考。

[1] 白艷玲,殷子焱.智能化制造業(yè)發(fā)展的戰(zhàn)略思考[J].科技創(chuàng)新與生產(chǎn)力,2015(7):11-12.

[2] 張誠,郭毅.數(shù)據(jù)挖掘與云計算——專訪中國科學院計算技術研究所何清博士[J].數(shù)字通信,2011,38(3):5-7.

[3] 賀瑤,王文慶,薛飛.基于云計算的海量數(shù)據(jù)挖掘研究[J].計算機技術與發(fā)展,2013,23(2):69-72.

[4] 林琳.揭秘Hadoop生態(tài)圈[J].科技視界,2016(26):247,231.

[5] 石慧芳,陳陽.基于大數(shù)據(jù)的制造業(yè)企業(yè)信息化數(shù)據(jù)分析及應用技術研究[J].現(xiàn)代計算機(專業(yè)版),2016(16):50-54

[6] 潘玉娜,陳進,李興林.基于模糊c-均值的設備性能退化評估方法[J].上海交通大學學報,2009,43(11):1794-1797

[7] Susanne Englert, Jim Gray, Terrye Kocher, et al. A benchmark of NonStop SQL release 2 demonstrating near-linear speedup and scaleup on large database[J]. ACM SIGMETRICS Performance Evaluation Review, 1990,18(1): 245-246.

Parallel Design of FCM Algorithm Based on Hadoop Platform

Chen Yang

(Guangdong Science & Technology Infrastructure Center)

The parallel design and implementation of MES data mining algorithm based on fuzzy c-means clustering was deeply studied in this paper. Firstly, the main functions of Hadoop, the cloud computing platform supporting data mining technology, and the processing flow of MapReduce, which realizes algorithm operation, was introduced. Then, the fuzzy c-means clustering algorithm, which is different from k-means clustering algorithm, was introduced. Finally, the parallel processing of MapReduce based on fuzzy c-means clustering algorithm was designed and implemented.

Key Works: Fuzzy CMeans; MES; Data Mining; Parallelization

陳陽，男，1984年生，本科，高級工程師，主要研究方向：計算機、電子信息技術應用等。E-mail: gdcc_chenyang@foxmail.com