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

唐新宇,張新政,趙月愛

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

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

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

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

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

1 聚類分析

云計算環(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個維度為p的樣本數(shù)據(jù)，則絕對距離的計算方法如式(1)所示[10-11]。

(1)

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

(2)

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

(3)

1.2 模糊聚類分析

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

(4)

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

U={x1,x2,…,xn}

(5)

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

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

2 模糊C-均值聚類算法

模糊C-均值聚類算法采用了硬聚類的思想。設(shè)X={x1,x2,…,xn}?Rs表示一個數(shù)據(jù)集，xj={xl1,xj2,…,xjk,…,xjn}?Rs表示第j個數(shù)據(jù)樣本的s個特征向量，xjk表示第j個數(shù)據(jù)樣本在維度k上的特征值。將數(shù)據(jù)集X進(jìn)行分組成為C個子集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)

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

(9)

約束條件為：

(10)

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

dij=||xj-vi||

(11)

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

(12)

(13)

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

3.1 混合蛙跳算法

混合蛙跳算法能夠在解決局部搜索問題的時候同時考慮全局信息[15]。在有限空間中，混合蛙跳算法通過模擬青蛙種群的跳動覓食行為來解決組合優(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個大于0且小于1的隨機(jī)數(shù)；Di表示青蛙每次跳動的距離；Dmax表示青蛙每次跳動的最大距離；xb表示各個子種群中適應(yīng)度值最優(yōu)解；xw表示各個子種群中適應(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)計算各類的聚類中心，作為初始混合蛙跳算法中青蛙映射編碼。

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

(16)

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

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

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

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

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

圖2 融合算法的流程

4 仿真實驗結(jié)果

4.1 實驗數(shù)據(jù)集

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

表1 4組實驗數(shù)據(jù)集的各項參數(shù)

4.2 聚類效果分析

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

(17)

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

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

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

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

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

從表2～5可以看出：由于對初始值的敏感度較大，模糊C-均值聚類算法聚類效果比較差；混合蛙跳算法雖然魯棒性和收斂速度較好且克服了局部極值問題，但是應(yīng)對大數(shù)據(jù)聚類劃分問題時精度較低；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是對Dataset1、Dataset2和Dataset3分別應(yīng)用傳統(tǒng)模糊C-均值聚類算法[14]、混合蛙跳算法[15]、PSO-FCM算法[9]和本文算法得到的收斂速率對比結(jié)果。

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

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

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

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

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

5 結(jié)束語

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