劉云恒

摘 ?要： 云計(jì)算從分布式存儲(chǔ)和分布式計(jì)算兩個(gè)方面為大數(shù)據(jù)處理提供了強(qiáng)力的支持，并逐漸成為大數(shù)據(jù)挖掘的主流平臺(tái)。但是在處理云平臺(tái)中的大規(guī)模數(shù)據(jù)集時(shí)典型聚類(lèi)挖掘算法存在一定不足，因此，提出一種基于群智能算法的大數(shù)據(jù)K?means聚類(lèi)挖掘算法。首先對(duì)云計(jì)算Hadoop框架的存儲(chǔ)數(shù)據(jù)能力和采用的Map Reduce計(jì)算模型進(jìn)行分析，然后采用群智能算法對(duì)傳統(tǒng)數(shù)據(jù)挖掘K?means聚類(lèi)算法進(jìn)行改進(jìn)，解決其容易陷入局部最優(yōu)問(wèn)題。實(shí)驗(yàn)結(jié)果表明，相比加權(quán)K?means聚類(lèi)算法，提出的改進(jìn)算法表現(xiàn)出更好的聚類(lèi)精度和運(yùn)行速度，可以適用于大規(guī)模數(shù)據(jù)的聚類(lèi)挖掘。

關(guān)鍵詞： 大數(shù)據(jù)聚類(lèi)挖掘; 云計(jì)算模型分析; 聚類(lèi)分析; 聚類(lèi)算法設(shè)計(jì); 算法優(yōu)化; 聚類(lèi)算法改進(jìn)

中圖分類(lèi)號(hào)： TN911.1?34; TP393 ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? 文章編號(hào)： 1004?373X（2019）09?0065?03

Cloud environment big data clustering mining technology

based on swarm intelligence algorithm

LIU Yunheng

（Nanjing Forest Police College， Nanjing 210023， China）

Abstract： Cloud computing provides strong support for big data processing in the aspects of distributed storage and distributed computing， and gradually becomes the mainstream platform of big data mining. However， the typical clustering mining algorithm has some shortcomings while dealing with the large?scale datasets in cloud platform. Therefore， a mining algorithm based on swarm intelligence algorithm is proposed for big data K?means clustering. The data storage capability of the cloud computing Hadoop framework and Map Reduce computing model are analyzed. The swarm intelligence algorithm is used to improve the traditional data mining K?means clustering algorithm to solve the problem that the algorithm is easy to fall into the local optimum. The experimental results show that， in comparison with the traditional weighing K?means clustering algorithm， the improved algorithm has higher clustering accuracy and faster running speed， and is suitable for clustering mining of large?scale data.

Keywords： big data clustering mining; cloud computing model analysis; clustering analysis; clustering algorithm design; algorithm optimization; clustering algorithm improvement

0 ?引 ?言

云計(jì)算（Cloud Computing）是大型計(jì)算機(jī)到客戶(hù)端?服務(wù)器的大轉(zhuǎn)變之后的又一種巨變，并被社會(huì)各界所認(rèn)可。由于出眾的計(jì)算性能，云計(jì)算得到了計(jì)算機(jī)領(lǐng)域的廣泛認(rèn)同，其接受程度和應(yīng)用范圍不斷擴(kuò)大[1?2]。近幾年來(lái)，云計(jì)算已經(jīng)對(duì)許多行業(yè)產(chǎn)生了巨大的革命性影響，并會(huì)完全改變IT產(chǎn)業(yè)的模型和運(yùn)行機(jī)制。隨著成本的不斷降低，低功耗和高性?xún)r(jià)比的云計(jì)算將逐漸替代眾多的傳統(tǒng)服務(wù)器硬件市場(chǎng)。具有高計(jì)算性能機(jī)、高存儲(chǔ)速度和大存儲(chǔ)空間的云計(jì)算數(shù)據(jù)中心將迅速大規(guī)模普及[3]。不久的將來(lái)，大部分應(yīng)用軟件將以服務(wù)的形式展現(xiàn)在人們面前，甚至大型的3D游戲也會(huì)在遠(yuǎn)程的云服務(wù)器中運(yùn)行。

伴隨著Internet網(wǎng)絡(luò)的飛速進(jìn)步及不斷普及，如今社會(huì)正以十分驚人的速度生成大量的數(shù)據(jù)。移動(dòng)通信、網(wǎng)頁(yè)瀏覽、辦公自動(dòng)化、在線購(gòu)物等，極度便利的網(wǎng)絡(luò)社交和商業(yè)活動(dòng)持續(xù)不斷地生成各類(lèi)數(shù)據(jù)，意味著世界已經(jīng)邁入了一個(gè)嶄新的時(shí)代，即爆炸性擴(kuò)張的大數(shù)據(jù)時(shí)代。數(shù)據(jù)挖掘（Data Mining）技術(shù)按照眾多事件的相關(guān)性，發(fā)掘解釋數(shù)據(jù)的一般規(guī)則集合，并利用訓(xùn)練和自學(xué)習(xí)，抽取隱含在數(shù)據(jù)中的新關(guān)系。上述數(shù)據(jù)的一般規(guī)則或相互關(guān)系能夠?yàn)閿?shù)據(jù)管理、信息查詢(xún)、決策判斷和優(yōu)化控制等應(yīng)用提供技術(shù)支撐。這些數(shù)據(jù)對(duì)于企業(yè)來(lái)說(shuō)具有巨大的經(jīng)濟(jì)價(jià)值，可以視為一個(gè)信息金庫(kù)[4?5]。云環(huán)境上的大數(shù)據(jù)分析已經(jīng)逐漸成為一個(gè)全新的商業(yè)模式。但是要實(shí)現(xiàn)云環(huán)境下的數(shù)據(jù)挖掘，首先要在云計(jì)算環(huán)境中實(shí)現(xiàn)傳統(tǒng)數(shù)據(jù)挖掘算法，其次需要解決現(xiàn)有傳統(tǒng)的數(shù)據(jù)挖掘算法無(wú)法適應(yīng)大規(guī)模數(shù)據(jù)的問(wèn)題。文獻(xiàn)[6]對(duì)基于粒子群算法的智能搜索引擎進(jìn)行研究，將粒子群算法引入智能搜索引擎中，以實(shí)現(xiàn)公安大數(shù)據(jù)的關(guān)聯(lián)搜索。文獻(xiàn)[7]采用的群體協(xié)同智能聚類(lèi)方法在粒子群算法中融入多種群協(xié)同進(jìn)化的方案，避免出現(xiàn)局部最優(yōu)解問(wèn)題，提高了數(shù)據(jù)聚類(lèi)的效率和精度，最終增強(qiáng)了大數(shù)據(jù)存儲(chǔ)性能，但是仍存在一定的局限性且不能較好地適用于云計(jì)算模型。

因此，為了進(jìn)一步提高云環(huán)境下聚類(lèi)算法的準(zhǔn)確率，本文提出一種基于群智能算法的大數(shù)據(jù)K?means聚類(lèi)挖掘算法。實(shí)驗(yàn)結(jié)果表明，相比加權(quán)K?means聚類(lèi)算法，本文提出的改進(jìn)算法表現(xiàn)出更好的聚類(lèi)效果。

1 ?云計(jì)算模型分析

1.1 ?云平臺(tái)體系

目前，云計(jì)算平臺(tái)主要具有基礎(chǔ)設(shè)施Server、平臺(tái)Server和軟件Server三種服務(wù)內(nèi)容[8]。云平臺(tái)典型體系如圖1所示。

圖1 ?云平臺(tái)典型體系

1.2 ?HDFS架構(gòu)及Map Reduce計(jì)算模型

作為Apache中的一個(gè)開(kāi)源項(xiàng)目，Hadoop分布式框架HDFS是現(xiàn)階段最流行的云計(jì)算服務(wù)架構(gòu)。HDFS主要由一個(gè)主從結(jié)構(gòu)構(gòu)成，完整的集群包含唯一的Name Node和2個(gè)以上的Data Node，如圖2所示[8]。

Hadoop分布式框架HDFS采用Map Reduce計(jì)算模型進(jìn)行Map階段和Reduce階段的執(zhí)行，從而把大數(shù)據(jù)集劃分成若干個(gè)小數(shù)據(jù)集。完整的Map Reduce作業(yè)步驟分為作業(yè)提交、作業(yè)初始化、任務(wù)分配、任務(wù)執(zhí)行和作業(yè)完成五個(gè)階段。

圖2 ?HDFS架構(gòu)

2 ?基于群智能的聚類(lèi)算法設(shè)計(jì)

2.1 ?聚類(lèi)分析基本模型

作為一種基于距離的劃分聚類(lèi)算法，K?means聚類(lèi)算法具有算法結(jié)構(gòu)簡(jiǎn)單、運(yùn)行效率高且適用范圍廣等優(yōu)點(diǎn)[9]?；贙?means聚類(lèi)算法的聚類(lèi)分析過(guò)程如圖3所示。

圖3 ?聚類(lèi)分析示意模型

可以看出，式（1）所示的目標(biāo)函數(shù)是一個(gè)誤差平方和計(jì)算過(guò)程。其中：E為聚類(lèi)準(zhǔn)則函數(shù);K為聚類(lèi)的總數(shù);[Cj，j=1，2，…，K]為聚類(lèi)中的簇;[x]為簇[Cj]中的一個(gè)聚類(lèi)目標(biāo);[mj]為簇[Cj]的平均大小。K?means聚類(lèi)算法的輸入?yún)?shù)為數(shù)值K和數(shù)據(jù)集X中聚類(lèi)目標(biāo)的數(shù)量n，輸出為使聚類(lèi)準(zhǔn)則函數(shù)E達(dá)到最小的K個(gè)聚類(lèi)。

2.2 ?狼群算法優(yōu)化設(shè)計(jì)

面對(duì)大數(shù)據(jù)環(huán)境下的復(fù)雜優(yōu)化問(wèn)題，傳統(tǒng)K?means聚類(lèi)算法在處理大規(guī)模數(shù)據(jù)時(shí)存在尋找全局最優(yōu)解較為困難的難題：在處理大規(guī)模數(shù)據(jù)集的挖掘任務(wù)時(shí)，K?means算法的聚類(lèi)效果對(duì)初始中心敏感，常常出現(xiàn)陷入局部最優(yōu)的問(wèn)題。

因此，基于混合聚類(lèi)的思路，本文引入智能群體算法中的狼群算法，輔以魯棒性更強(qiáng)的K?means算法優(yōu)化混合聚類(lèi)方法的聚集效果。設(shè)狼群中狼的總數(shù)為N，待尋優(yōu)的變量數(shù)為[D]。探狼在第d維空間中的位置更新方式如下[10]：

圖4 ?群智優(yōu)化的K?means聚類(lèi)算法流程

3 ?實(shí)驗(yàn)結(jié)果與分析

3.1 ?實(shí)驗(yàn)環(huán)境配置

為了驗(yàn)證所提算法的性能，本文搭建Hadoop云計(jì)算平臺(tái)，在Linux操作系統(tǒng)上進(jìn)行測(cè)試與分析。Hadoop集群所用軟件版本信息如表1所示。3個(gè)Hadoop集群實(shí)驗(yàn)根據(jù)不同IP分配設(shè)立3個(gè)主機(jī)節(jié)點(diǎn)，各節(jié)點(diǎn)配置信息如表2所示。在HDFS分布式文件系統(tǒng)中，集群包含唯一的Name Node和2個(gè)Data Node，其中Name Node實(shí)現(xiàn)數(shù)據(jù)管理功能，Data Node實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)功能。

使用一組人工數(shù)據(jù)集Dataset1對(duì)加權(quán)K?means聚類(lèi)算法[9]和提出的群智優(yōu)化K?means聚類(lèi)算法進(jìn)行仿真實(shí)驗(yàn)。該數(shù)據(jù)集Dataset1包含200個(gè)樣本，類(lèi)別數(shù)為3。實(shí)驗(yàn)中狼群算法誤差目標(biāo)值為0.000 1，人工狼的數(shù)目為50，最大進(jìn)化次數(shù)為100，更新比例因子為4。

表1 ?Hadoop集群所用軟件版本

表2 ?Hadoop集群中各節(jié)點(diǎn)配置信息

3.2 ?聚類(lèi)效果比較

采用聚類(lèi)正確率和聚類(lèi)錯(cuò)誤率兩個(gè)指標(biāo)對(duì)不同算法的聚類(lèi)效果進(jìn)行量化評(píng)估，計(jì)算公式如下：

加權(quán)K?means聚類(lèi)算法和本文提出的群智優(yōu)化K?means聚類(lèi)算法的聚類(lèi)精度比較結(jié)果如表3所示。從表3中可以看出，群智優(yōu)化K?means聚類(lèi)算法具有較好的全局優(yōu)化穩(wěn)定性，聚類(lèi)劃分更明確，獲得了更好的聚類(lèi)效果。

表3 ?聚類(lèi)精度比較

4 ?結(jié) ?語(yǔ)

本文提出一種基于群智能算法的大數(shù)據(jù)K?means聚類(lèi)挖掘算法。在云計(jì)算環(huán)境下采用群智能算法中的狼群算法對(duì)傳統(tǒng)數(shù)據(jù)挖掘K?means聚類(lèi)算法進(jìn)行改進(jìn)。得出如下結(jié)論：本文提出的混合聚類(lèi)算法解決了傳統(tǒng)聚類(lèi)算法對(duì)初始中心敏感、容易出現(xiàn)陷入局部最優(yōu)的問(wèn)題，獲得了較好的全局最優(yōu)解;相比加權(quán)K?means聚類(lèi)算法，提出的改進(jìn)算法表現(xiàn)出更好的聚類(lèi)效果，但是算法的迭代時(shí)間還有待改善和研究。

參考文獻(xiàn)

[1] BERA S， MISRA S， RODRIGUES J J P C. Cloud computing applications for smart grid： a survey [J]. IEEE transactions on parallel & distributed systems， 2015， 26（5）： 1477?1494.

[2] WHAIDUZZAMAN M， SOOKHAK M， GANI A， et al. A survey on vehicular cloud computing [J]. Journal of network & computer applications， 2014， 40（1）： 325?344.

[3] JULA A， SUNDARARAJAN E， OTHMAN Z. Cloud computing service composition： a systematic literature review [J]. Expert systems with applications， 2014， 41（8）： 3809?3824.

[4] LU H， SETIONO R， LIU H. Effective data mining using neural networks [J]. IEEE transactions on knowledge & data engineering， 2016， 8（6）： 957?961.

[5] LINDEN A， YARNOLD P R. Using data mining techniques to characterize participation in observational studies [J]. Journal of evaluation in clinical practice， 2016， 22（6）： 835?843.

[6] 胡存剛，程瑩.基于粒子群算法的大數(shù)據(jù)智能搜索引擎的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2015，25（12）：14?17.

HU Cungang， CHENG Ying. Research on big data intelligent search engine based on particle swarm optimization algorithm [J]. Computer technology and development， 2015， 25（12）： 14?17.

[7] 劉先花.基于群體協(xié)同智能聚類(lèi)的大數(shù)據(jù)存儲(chǔ)系統(tǒng)設(shè)計(jì)[J].現(xiàn)代電子技術(shù)，2017，40（23）：138?141.

LIU Xianhua. Design of big data storage system based on group collaborative intelligent clustering [J]. Modern electronics technique， 2017， 40（23）： 138?141.

[8] KHAN M， JIN Y， LI M， et al. Hadoop performance modeling for job estimation and resource provisioning [J]. IEEE transactions on parallel & distributed systems， 2016， 27（2）： 441?454.

[9] AMORIM R C D， MAKARENKOV V. Applying subclustering and Lp distance in weighted K?means with distributed centroids [J]. Neurocomputing， 2016， 173（3）： 700?707.

[10] YI T， LI H， WANG C. Multiaxial sensor placement optimization in structural health monitoring using distributed wolf algorithm [J]. Structural control & health monitoring， 2016， 23（4）： 719?734.