基于Hadoop平臺的FCM算法并行化設(shè)計

陳陽

?

基于Hadoop平臺的FCM算法并行化設(shè)計

陳陽

（廣東省科技基礎(chǔ)條件平臺中心）

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

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

0　引言

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

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

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

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

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

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

圖1　MapReduce處理流程圖

2　模糊C均值聚類算法

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

圖2　FCM算法基本流程圖

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

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

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

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

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

3　FCM算法并行化設(shè)計

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

在Hadoop平臺中，F(xiàn)CM算法的并行化設(shè)計和實現(xiàn)，實質(zhì)就是將算法進(jìn)行MapReduce化，即實現(xiàn)Map和Reduce過程，具體工作包括：1）輸入和輸出鍵值對設(shè)計；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ù)和當(dāng)前個聚類中心的值，并計算各個數(shù)據(jù)分別對個聚類中心的距離、隸屬度、隸屬度與數(shù)據(jù)的乘積和。Map函數(shù)形式為鍵值對，其中是當(dāng)前數(shù)據(jù)的行偏移量；是當(dāng)前對象各個維度坐標(biāo)值的行記錄。Map函數(shù)的實現(xiàn)過程就是從字符串中得到源數(shù)據(jù)/對象與個聚類中心的隸屬度，最后輸出形如<2,2>的返回值。

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

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

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

從中解析出當(dāng)前數(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ù)的輸出結(jié)果（隸屬度和隸屬度與數(shù)據(jù)點的乘積和集）進(jìn)行整理和排序，從而保證后續(xù)Reduce函數(shù)的輸入?yún)?shù)能夠按照值對Map階段的輸出結(jié)果進(jìn)行分組。因此，Combine函數(shù)的輸入?yún)?shù)為Map函數(shù)的輸出22，其中，2代表當(dāng)前C聚類中心的ID；2代表隸屬度的值以及數(shù)據(jù)點的乘積和。

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

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

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

for(=1;≤;++){

for(=1;≤;++);

While(value.hasNext()){

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

將調(diào)出來的數(shù)據(jù)存入到對應(yīng)的數(shù)組中；

}

}

3=2;

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

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

}

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

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

Reduce函數(shù)設(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　應(yīng)用實例

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

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

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

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

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

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

6　結(jié)語

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

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

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

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

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

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

[6] 潘玉娜,陳進(jìn),李興林.基于模糊c-均值的設(shè)備性能退化評估方法[J].上海交通大學(xué)學(xué)報,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年生，本科，高級工程師，主要研究方向：計算機、電子信息技術(shù)應(yīng)用等。E-mail: gdcc_chenyang@foxmail.com