唐新宇,張新政,趙月愛

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

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

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

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

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

1 聚類分析

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

1.1 聚類分析的相關概念

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

(1)

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

(2)

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

(3)

1.2 模糊聚類分析

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

(4)

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

U={x1,x2,…,xn}

(5)

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

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

2 模糊C-均值聚類算法

模糊C-均值聚類算法采用了硬聚類的思想。設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進行分組成為C個子集Y={X1,X2,…,XC},C∈[2,n)。如果Y符合式(6)的要求，那么Y可以視為硬C分組[12]。

(6)

設樣本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-均值聚類算法的目標函數(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ù)較少且全局搜索能力較強，混合蛙跳算法示意圖如圖1所示。

圖1 混合蛙跳算法示意圖

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

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

i=1,2,…,m

(14)

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

i=1,2,…,m

(15)

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

3.2 算法融合思想和步驟

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

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

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

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

(16)

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

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

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

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

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

圖2 融合算法的流程

4 仿真實驗結(jié)果

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

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

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

4.2 聚類效果分析

在本文實驗過程中，設置最大迭代次數(shù)為500，子種群個數(shù)為5，子聚類數(shù)目為3，種群規(guī)模為30，模糊指數(shù)m=2，群內(nèi)迭代次數(shù)為5。將4種算法分別重復執(zhí)行40次，并計算每個指標的平均值。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-均值聚類算法聚類效果比較差；混合蛙跳算法雖然魯棒性和收斂速度較好且克服了局部極值問題，但是應對大數(shù)據(jù)聚類劃分問題時精度較低；PSO-FCM 算法將粒子群優(yōu)化算法與模糊C-均值聚類算法結(jié)合，利用群智優(yōu)化算法的優(yōu)點較好地提高了局部搜索能力，優(yōu)化了聚類效果，從而得到了較高的準確性。本文提出的融合算法利用混合蛙跳算法最優(yōu)解來調(diào)整模糊C-均值聚類中的聚類中心值，并合理選取適應度函數(shù)，提高了全局搜索能力和搜索精度，獲得了較好的聚類效果，與PSO-FCM算法的效果相近。

4.3 收斂速度比較

圖3～5是對Dataset1、Dataset2和Dataset3分別應用傳統(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ù)較少，因此能更準確、更快速地得到聚類中心，魯棒性強，收斂速度較快。

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

5 結(jié)束語

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