云計(jì)算中基于群體智能算法的大數(shù)據(jù)聚類挖掘

唐新宇,張新政,趙月愛

(1.廣東工商職業(yè)學(xué)院 計(jì)算機(jī)應(yīng)用技術(shù)系， 廣東 肇慶 526040；2.廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院， 廣州 510090； 3.太原師范學(xué)院 計(jì)算機(jī)系， 山西 晉中 030619)

隨著計(jì)算機(jī)性能和網(wǎng)絡(luò)帶寬的不斷提高，云計(jì)算技術(shù)逐漸得到推廣和普及，與云計(jì)算相輔相成的物聯(lián)網(wǎng)技術(shù)也得到越來越多的關(guān)注[1-3]。與此同時(shí)，是隨之產(chǎn)生的爆發(fā)式的數(shù)據(jù)，如何利用數(shù)據(jù)挖掘技術(shù)對(duì)海量的數(shù)據(jù)進(jìn)行分析和處理成為備受關(guān)注的熱點(diǎn)。網(wǎng)上社交、人工智能和電子商務(wù)等各個(gè)行業(yè)對(duì)數(shù)據(jù)挖掘有較大的需求。數(shù)據(jù)挖掘作為一種新型的計(jì)算機(jī)科學(xué)技術(shù)，在社會(huì)需求的推動(dòng)下得到了快速的發(fā)展。研究人員通常構(gòu)建若干個(gè)模型和數(shù)據(jù)分析工具來提取數(shù)據(jù)間的隱藏關(guān)聯(lián)，并采用適當(dāng)?shù)囊?guī)則或算法采集感興趣的信息[4]。

目前，面向云計(jì)算的數(shù)據(jù)挖掘工具中最常用的是聚類分析技術(shù)，其目標(biāo)是把某一數(shù)據(jù)集分解為若干類，并滿足以下條件：① 處于相同類中的數(shù)據(jù)具有較高的相似性；② 處于不同類中的數(shù)據(jù)具有較小的相似性或沒有相似性[5]。現(xiàn)階段，聚類分析一般被劃分為2種類型：基本的聚類分析和模糊聚類分析。相比基本的聚類分析，模糊聚類分析在處理真實(shí)社會(huì)中的數(shù)據(jù)(較高的復(fù)雜性和多樣性)時(shí)表現(xiàn)出更好的適應(yīng)性和魯棒性。因此，文獻(xiàn)[6]提出了基于動(dòng)態(tài)時(shí)間規(guī)整距離的時(shí)間序列數(shù)據(jù)模糊聚類方法。文獻(xiàn)[7]提出了基于模糊聚類的RBF神經(jīng)網(wǎng)絡(luò)訓(xùn)練方法，有效提升了模型的預(yù)測(cè)準(zhǔn)確率。文獻(xiàn)[8]采用聚類分析法評(píng)價(jià)4個(gè)藍(lán)莓品種的感官品質(zhì)、營養(yǎng)品質(zhì)、加工品質(zhì)等指標(biāo)，從而篩選出品質(zhì)較佳的藍(lán)莓品種。但是，模糊聚類分析存在容易陷入局部極值等問題。

群智能優(yōu)化算法作為一種人工模仿動(dòng)物群體生活習(xí)性的仿生技術(shù)，在數(shù)據(jù)挖掘方面具有較大的應(yīng)用前景。例如，粒子群優(yōu)化算法作為群智優(yōu)化的重要方法之一，能夠模擬簡(jiǎn)單群落中個(gè)體以及個(gè)體之間的互動(dòng)行為來搜索全局最優(yōu)解。利用這個(gè)特性，文獻(xiàn)[9]提出了基于模糊聚類分析的云計(jì)算負(fù)載平衡策略，將粒子群優(yōu)化算法與模糊C均值聚類算法融合得到了PSO-FCM算法，有效提高了模糊C均值聚類算法的正確率。

在文獻(xiàn)[9]提出的融合思路基礎(chǔ)上，本文提出了一種基于群體智能算法大數(shù)據(jù)聚類挖掘算法。首先對(duì)聚類算法中的模糊C-均值聚類算法進(jìn)行了分析，然后將亞啟發(fā)式群智能優(yōu)化技術(shù)中的混合蛙跳算法與模糊C-均值聚類相結(jié)合，以便在調(diào)整參數(shù)少的條件下優(yōu)化全局搜索能力。仿真實(shí)驗(yàn)結(jié)果顯示，相比其他聚類挖掘算法，提出的算法能夠有效解決局部陷阱問題，從而具有較好的聚類效果、準(zhǔn)確率和收斂速度，同時(shí)算法的穩(wěn)定性較高。

1 聚類分析

云計(jì)算環(huán)境下聚類分析的目標(biāo)為數(shù)據(jù)的劃分，以便將具有較高相似性的數(shù)據(jù)劃分到相同的組中，并將具有較小相似性或沒有相似性的數(shù)據(jù)劃分到相同的組中。

1.1 聚類分析的相關(guān)概念

通過上述介紹可以看出，聚類分析的本質(zhì)是一種多維樣本分類問題。為了進(jìn)行樣本分類，需要確定數(shù)據(jù)樣本間的相似程度，并且不需要參數(shù)，如屬性、數(shù)量等。為此引入“距離”的概念。設(shè)X={x1,x2,…,xp}和Y={y1,y2,…,yp}為2個(gè)維度為p的樣本數(shù)據(jù)，則絕對(duì)距離的計(jì)算方法如式(1)所示[10-11]。

(1)

此外，還有契比雪夫距離、馬氏距離和歐式距離等計(jì)算方法。第i個(gè)樣本和第j個(gè)樣本間的相似系數(shù)可以由式(2)得到。

(2)

第i個(gè)指標(biāo)與第j個(gè)指標(biāo)間的相關(guān)系數(shù)可以由式(3)得到。

(3)

1.2 模糊聚類分析

模糊聚類方法通常用來解決一些不精確和不確定性的問題，例如天氣預(yù)報(bào)。模糊聚類分析的數(shù)據(jù)模型中，原始數(shù)據(jù)矩陣的定義如下：

(4)

為了對(duì)所有對(duì)象m的特征進(jìn)行劃分以便對(duì)數(shù)據(jù)集合進(jìn)行分組，定義數(shù)據(jù)對(duì)象的表達(dá)式如式(5)所示。

U={x1,x2,…,xn}

(5)

其中：xi={xi1,xi2,…,xim},i=1,2,…,n。

模糊聚類分析算法大致可以分為4種[12-14]：譜系聚類法、基于等價(jià)關(guān)系的聚類方法、圖論聚類方法和基于目標(biāo)函數(shù)的聚類方法。由于基于目標(biāo)函數(shù)的模糊聚類方法采用傳統(tǒng)的非線性規(guī)劃原理來處理數(shù)據(jù)挖掘問題，因此實(shí)現(xiàn)起來較為簡(jiǎn)單，得到了大多數(shù)研究機(jī)構(gòu)和科研人員的關(guān)注。模糊C-均值聚類算法屬于基于目標(biāo)函數(shù)的方法，在大數(shù)據(jù)量時(shí)表現(xiàn)出優(yōu)秀的性能。因此， 本文的研究對(duì)象為模糊C-均值聚類算法。

2 模糊C-均值聚類算法

模糊C-均值聚類算法采用了硬聚類的思想。設(shè)X={x1,x2,…,xn}?Rs表示一個(gè)數(shù)據(jù)集，xj={xl1,xj2,…,xjk,…,xjn}?Rs表示第j個(gè)數(shù)據(jù)樣本的s個(gè)特征向量，xjk表示第j個(gè)數(shù)據(jù)樣本在維度k上的特征值。將數(shù)據(jù)集X進(jìn)行分組成為C個(gè)子集Y={X1,X2,…,XC},C∈[2,n)。如果Y符合式(6)的要求，那么Y可以視為硬C分組[12]。

(6)

設(shè)樣本xj屬于子集Xi的隸屬度為uij，那么可以用隸屬矩陣U=[μij]C×n來表示硬C分組，其中μij∈{0,1}。因此， 數(shù)據(jù)集X的硬C分組可以用式(7)來表示。

?k;

(7)

因此， 模糊C分組可以用式(8)來表示。

(8)

對(duì)于數(shù)據(jù)集X={x1,x2,…,xk,…,xn}?Rs來說，n是數(shù)據(jù)集X中元素的數(shù)量，s是樣本xk中屬性值的個(gè)數(shù)。c個(gè)聚類中心組成1個(gè)矩陣V={v1,v2,…,vi,…,vc}S×C,其中vi={vi1,vi2,…,vis}為第i個(gè)聚類中心的元素，c為聚類的類別數(shù)，則模糊C-均值聚類算法的目標(biāo)函數(shù)為

(9)

約束條件為：

(10)

第j個(gè)樣本數(shù)據(jù)xj到第i個(gè)聚類中心vi的歐氏距離為：

dij=||xj-vi||

(11)

第i個(gè)聚類中心vi和隸屬度uij的計(jì)算方法分別如式(12)(13)所示。

(12)

(13)

3 混合蛙跳算法與模糊C-均值聚類算法的融合

3.1 混合蛙跳算法

混合蛙跳算法能夠在解決局部搜索問題的時(shí)候同時(shí)考慮全局信息[15]。在有限空間中，混合蛙跳算法通過模擬青蛙種群的跳動(dòng)覓食行為來解決組合優(yōu)化問題。該算法所需的調(diào)整參數(shù)較少且全局搜索能力較強(qiáng)，混合蛙跳算法示意圖如圖1所示。

圖1 混合蛙跳算法示意圖

混合蛙跳算法的流程為：① 算法各參數(shù)初始化；② 子種群的劃分；③ 組內(nèi)局部搜索進(jìn)化；④ 子種群混合。在局部搜索的每一次迭代步驟中，只需要更新一次子種群中最差解，具體方式為：

Di=rand()·(xb-xw),

i=1,2,…,m

(14)

xw=xw+Di,-Dmax≤Di≤Dmax,

i=1,2,…,m

(15)

其中: rand()表示1個(gè)大于0且小于1的隨機(jī)數(shù)；Di表示青蛙每次跳動(dòng)的距離；Dmax表示青蛙每次跳動(dòng)的最大距離；xb表示各個(gè)子種群中適應(yīng)度值最優(yōu)解；xw表示各個(gè)子種群中適應(yīng)度值最差解。

3.2 算法融合思想和步驟

如上所述，模糊C-均值聚類算法使用目標(biāo)函數(shù)優(yōu)化到最小值的方法來求解。但是這樣的方式容易使最終解陷入局部極小值點(diǎn)，且收斂速度慢。作為一種群體智能算法，混合蛙跳具有較強(qiáng)的全局搜索特性。因此，本文將混合蛙跳算法和模糊C-均值聚類算法進(jìn)行結(jié)合，來提高聚類效果和優(yōu)化精度。

基于混合蛙跳的模糊C-均值聚類算法步驟如下：

步驟1 初始化：初始化青蛙種群的數(shù)量N，聚類數(shù)目c，并設(shè)置隨機(jī)的隸屬度原始矩陣，視為初始的聚類劃分，根據(jù)式(12)計(jì)算各類的聚類中心，作為初始混合蛙跳算法中青蛙映射編碼。

步驟2 行為選擇：根據(jù)式(16)計(jì)算模擬執(zhí)行青蛙群體行為后所得的每只青蛙的適應(yīng)度函數(shù)值，并對(duì)青蛙按降序進(jìn)行排列和分組。

(16)

其中：q是一個(gè)隨機(jī)數(shù)，其取值范圍為[0,1]；Jm表示模糊C-均值聚類的目標(biāo)函數(shù)(式(9))。

步驟3 在每個(gè)子種群中進(jìn)行局部搜索并更新子種群中最差個(gè)體直至達(dá)到局部搜索最大迭代次數(shù)。

步驟4 將子種群混合并及時(shí)更新種群最優(yōu)解。

步驟5 重復(fù)步驟2～5，直到達(dá)到最大給定迭代次數(shù)，此時(shí)全局最優(yōu)解就是初始聚類中心。調(diào)用模糊C-均值聚類算法，獲得最終的聚類矩陣分組。最后采用最大隸屬度規(guī)則，對(duì)數(shù)據(jù)集中所有的樣本進(jìn)行屬類別標(biāo)注。

融合算法流程如圖2所示。

圖2 融合算法的流程

4 仿真實(shí)驗(yàn)結(jié)果

4.1 實(shí)驗(yàn)數(shù)據(jù)集

為了驗(yàn)證本文提出的融合算法的有效性和先進(jìn)性，用典型Iris數(shù)據(jù)集和3組人工數(shù)據(jù)集 Dataset1對(duì)傳統(tǒng)模糊C-均值聚類算法[14]、混合蛙跳算法[15]、PSO-FCM算法[9]和本文算法進(jìn)行了仿真實(shí)驗(yàn)。4組實(shí)驗(yàn)數(shù)據(jù)集的各項(xiàng)參數(shù)如表1所示。

表1 4組實(shí)驗(yàn)數(shù)據(jù)集的各項(xiàng)參數(shù)

4.2 聚類效果分析

在本文實(shí)驗(yàn)過程中，設(shè)置最大迭代次數(shù)為500，子種群個(gè)數(shù)為5，子聚類數(shù)目為3，種群規(guī)模為30，模糊指數(shù)m=2，群內(nèi)迭代次數(shù)為5。將4種算法分別重復(fù)執(zhí)行40次，并計(jì)算每個(gè)指標(biāo)的平均值。4種算法在不同數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果見表2～5。聚類結(jié)果的有效性用分類正確率來評(píng)估，分類正確率的計(jì)算方法如式(17)所示。

(17)

其中：M表示樣本聚類正確數(shù)；N表示數(shù)據(jù)集中所含數(shù)據(jù)對(duì)象的總個(gè)數(shù)。

表2 Iris 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

表3 Dataset1數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

表4 Dataset2數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

表5 Dataset3數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

從表2～5可以看出：由于對(duì)初始值的敏感度較大，模糊C-均值聚類算法聚類效果比較差；混合蛙跳算法雖然魯棒性和收斂速度較好且克服了局部極值問題，但是應(yīng)對(duì)大數(shù)據(jù)聚類劃分問題時(shí)精度較低；PSO-FCM 算法將粒子群優(yōu)化算法與模糊C-均值聚類算法結(jié)合，利用群智優(yōu)化算法的優(yōu)點(diǎn)較好地提高了局部搜索能力，優(yōu)化了聚類效果，從而得到了較高的準(zhǔn)確性。本文提出的融合算法利用混合蛙跳算法最優(yōu)解來調(diào)整模糊C-均值聚類中的聚類中心值，并合理選取適應(yīng)度函數(shù)，提高了全局搜索能力和搜索精度，獲得了較好的聚類效果，與PSO-FCM算法的效果相近。

4.3 收斂速度比較

圖3～5是對(duì)Dataset1、Dataset2和Dataset3分別應(yīng)用傳統(tǒng)模糊C-均值聚類算法[14]、混合蛙跳算法[15]、PSO-FCM算法[9]和本文算法得到的收斂速率對(duì)比結(jié)果。

圖3 Dataset1 數(shù)據(jù)集上的測(cè)試結(jié)果

圖4 Dataset2 數(shù)據(jù)集上的測(cè)試結(jié)果

圖5 Dataset3 數(shù)據(jù)集上的測(cè)試結(jié)果

由圖3～5可知，模糊C-均值聚類算法和混合蛙跳算法的收斂速度較慢；PSO-FCM 算法收斂速率有所提升。由于融合算法所需的調(diào)整參數(shù)較少，因此能更準(zhǔn)確、更快速地得到聚類中心，魯棒性強(qiáng)，收斂速度較快。

相比其他幾種算法，本文提出的融合算法在聚類效果、精確度、收斂速率、魯棒性上均表現(xiàn)最優(yōu)。

5 結(jié)束語

本文提出了一種基于群體智能算法的大數(shù)據(jù)聚類挖掘算法。首先對(duì)聚類算法中的模糊C-均值聚類算法進(jìn)行了分析，然后將亞啟發(fā)式群智能優(yōu)化技術(shù)中的混合蛙跳算法與模糊C-均值聚類相結(jié)合，以便在調(diào)整參數(shù)少的條件下優(yōu)化全局搜索能力。仿真實(shí)驗(yàn)結(jié)果顯示，相比其他聚類挖掘算法，提出的算法能夠有效解決局部陷阱問題，從而具有較好的聚類效果、準(zhǔn)確率和收斂速度，同時(shí)算法的穩(wěn)定性較高。