云計算下基于改進遺傳算法的聚類融合算法

徐占洋，鄭克長

(南京信息工程大學(xué) 計算機與軟件學(xué)院，南京 210044)(*通信作者電子郵箱983119701@qq.com)

0　引言

隨著數(shù)據(jù)量的日益增長，要處理的數(shù)據(jù)信息規(guī)模也隨之增大，傳統(tǒng)模式的大數(shù)據(jù)挖掘處理技術(shù)已經(jīng)無法滿足現(xiàn)在對于算法效率和準(zhǔn)確度的要求。云計算為大數(shù)據(jù)的挖掘與處理提供了便利的服務(wù)，而Hadoop則為大數(shù)據(jù)處理技術(shù)提供了很好的解決方案。對于無監(jiān)督數(shù)據(jù)聚類，不同的數(shù)據(jù)集需要選擇不同的、合適的聚類算法，這無疑增加了工作量與工作難度。為了解決上述問題，Strehl等[1]提出了合并獨立聚類算法的思想，這就是聚類融合的由來。相比單一聚類算法，聚類融合具有以下優(yōu)點：

1)魯棒性。許多研究實驗表明，聚類融合在不同領(lǐng)域和不同數(shù)據(jù)集上的表現(xiàn)都優(yōu)于獨立的聚類算法。也就是說，聚類融合的算法性能，即最終劃分的準(zhǔn)確度優(yōu)于單一聚類算法。

2)穩(wěn)定性。單一聚類算法大多受噪聲數(shù)據(jù)、異常值、數(shù)據(jù)分布等影響，而聚類融合對于這些因素則不敏感。

3)可并行性和可擴展性。并不是每個聚類算法都可以并行，但聚類融合可以并行；同時，聚類融合可以從多個分布式數(shù)據(jù)源上集成基聚類。

遺傳算法(Genetic Algorithm, GA)[2]是受自然選擇過程啟發(fā)設(shè)計的一種進化算法，它通常依靠交叉、變異和選擇等操作優(yōu)化和搜索問題。在實際應(yīng)用中，遺傳算法經(jīng)常被用來解決全局優(yōu)化問題。在處理大量的多維數(shù)據(jù)集時，時間和空間的高復(fù)雜度是串行聚類融合算法的一個不足之處。本文主要從以下兩個方面設(shè)計實現(xiàn)云計算下基于改進遺傳算法的聚類融合算法(Clustering Ensemble algorithm based on Improved Genetic Algorithm, CEIGA)：

1)聚類融合要求基聚類具有多樣性，基于此本文設(shè)計了新的選擇算子用于遺傳算法。同時，本文將改進后的遺傳算法作為聚類融合的一致性集成函數(shù)，合并基聚類生成最終聚類結(jié)果，從而提高一般聚類融合算法的性能，降低算法的空間復(fù)雜度。

2)本文采用Hadoop分布式框架實現(xiàn)基于改進遺傳算法的并行聚類融合算法。MapReduce編程模型是Hadoop框架中的一個核心部分，它能夠提高基于改進遺傳算法的并行聚類融合算法的計算效率，降低算法的時間復(fù)雜度。

1　相關(guān)工作

由于不同的聚類算法在同一個數(shù)據(jù)集上會得到不同的聚類結(jié)果，Strehl等[1]提出了聚類融合這一概念，并對其進行了定義：對同一數(shù)據(jù)集進行聚類得到多個有差別的基聚類劃分，再將其進行合并以得到一個統(tǒng)一的改進的共識劃分，并且不使用數(shù)據(jù)集原有的屬性特征。聚類融合的出現(xiàn)在數(shù)據(jù)挖掘領(lǐng)域也掀起了研究熱潮。近年來,學(xué)者們從不同方面進行探索，如基聚類的生成機制(同一種算法不同參數(shù)、不同算法、不同數(shù)據(jù)子集、不同特征子集等)[1,3-5]，一致性集成函數(shù)(投票法、基于矩陣的方法、基于圖的方法等)[1,6-9]，基聚類的評估與選擇(聚類評價函數(shù)和成員選擇等)[9-10]和聚類融合的應(yīng)用(圖像視頻識別、醫(yī)學(xué)診斷、入侵檢測等)[8,11-12]。

遺傳算法是由Turing[2]根據(jù)生物學(xué)的優(yōu)勝劣汰、適者生存進化機制發(fā)展而來的用于解決多目標(biāo)優(yōu)化問題的方案，目前已被應(yīng)用于組合優(yōu)化、機器學(xué)習(xí)和人工智能等領(lǐng)域。文獻[13-15]將遺傳算法用于聚類融合，并將基聚類劃分作為目標(biāo)，進行優(yōu)化得到全局最優(yōu)的共識劃分。遺傳算法雖然可以有效地解決聚類融合中的全局優(yōu)化問題，但是如何構(gòu)造簡單有效的編碼方式,如何選擇合適的適應(yīng)度函數(shù),如何設(shè)計恰當(dāng)?shù)倪x擇、交叉和變異算子等是改進基于遺傳算法的聚類融合算法的關(guān)鍵。

隨著時代的發(fā)展，數(shù)據(jù)量越來越大，傳統(tǒng)的數(shù)據(jù)挖掘算法執(zhí)行起來費時耗力。Hadoop平臺上的MapReduce框架經(jīng)常用于解決大數(shù)據(jù)集的分布式存儲的并行計算問題[16]。一個MapReduce程序由一個map函數(shù)進行過濾和排序操作，一個reduce函數(shù)進行匯總操作。吳曉璇等[17]將數(shù)據(jù)空間中的分形維數(shù)用于聚類融合，同時在云計算環(huán)境下實現(xiàn)了其并行化；Benmounah等[18]提出了一個聚類融合并行分布式系統(tǒng)用于醫(yī)療疾病的診斷。

本文針對無監(jiān)督聚類缺少先驗信息以及聚類融合要求基聚類具有高準(zhǔn)確性的問題，提出了基于改進遺傳算法的聚類融合算法(CEIGA)。針對聚類融合算法時間復(fù)雜度高的問題，利用Hadoop設(shè)計實現(xiàn)了基于改進遺傳算法的并行聚類融合算法(Parallel Clustering Ensemble algorithm based on Improved Genetic Algorithm, PCEIGA)。

2　基于改進遺傳算法的聚類融合算法

2.1　基聚類生成機制

本文選擇K-Means算法作為基聚類生成機制的主要算法，它是數(shù)據(jù)挖掘領(lǐng)域非常流行的一種聚類方法。給定一個數(shù)據(jù)集X={x1,x2,…,xn}，數(shù)據(jù)集中的每條數(shù)據(jù)都有d個屬性，K-Means算法的目標(biāo)是把數(shù)據(jù)集中的n個對象劃分成k(k≤n)個簇同時使得簇內(nèi)平方和最小、簇間平方和最大。

首先，K-Means算法會從原始數(shù)據(jù)集中隨機選擇k個數(shù)據(jù)作為初始簇中心；接著根據(jù)歐幾里得公式計算每個數(shù)據(jù)到當(dāng)前k個簇中心的距離，并根據(jù)計算得到的歐幾里得距離將每個數(shù)據(jù)分配到離它最近的簇中心所在的簇。由于這一步操作會導(dǎo)致簇的分布發(fā)生變化，進而引起簇中心變化，因此，需要重新計算簇中心。簇中心的計算公式如下所示：

(1)

其中|Ci|是簇Ci內(nèi)數(shù)據(jù)的數(shù)量。最后，計算出新的簇中心后，判斷前后兩次簇中心是否變化，如果沒有變化，則K-Means算法停止；否則繼續(xù)迭代。重復(fù)上述K-Means算法m次，就會得到關(guān)于原始數(shù)據(jù)集X的m次聚類劃分，即m個基聚類。

2.2　基聚類簇標(biāo)簽轉(zhuǎn)化

在采用遺傳算法得到最終結(jié)果之前，必須解決基聚類的簇標(biāo)簽不一致問題。對于聚類劃分{1,1,1,2,2,3,3,3}和{2,2,2,3,3,1,1,1}，雖然它們的表達方式不一樣，但是表示的卻是同一個劃分。聚類融合的基聚類之間必須通過匹配建立相互的對應(yīng)關(guān)系。

2.3　改進遺傳算法

傳統(tǒng)的聚類融合算法一般采用基于相似性矩陣的聚類算法作為一致性集成函數(shù)，但是一般的聚類算法容易陷入局部最優(yōu)，同時在算法應(yīng)用前需要創(chuàng)建關(guān)于數(shù)據(jù)或基聚類的相似性矩陣，空間和時間復(fù)雜度高。針對上述問題，本文利用改進的遺傳算法作為一致性集成函數(shù)。遺傳算法作為一致性集成函數(shù)的優(yōu)點主要有：1)遺傳算法通過進化迭代地尋找全局最優(yōu)解；2)通過改進遺傳算法的選擇算子，選擇合適的染色體進行交叉和變異操作，能使基聚類滿足多樣性和準(zhǔn)確性；3)遺傳算法的可并行特點是其作為一致性集成函數(shù)的重要因素之一。

遺傳算法主要包括基因編碼、適應(yīng)度函數(shù)、選擇算子、交叉和變異操作和精英策略五部分。

2.3.1基因編碼

本文采用字符串編碼策略。每一個基聚類會編碼成一個整數(shù)字符串，其中字符串中的每一個整數(shù)表示的是當(dāng)前位置的數(shù)據(jù)所被分到的簇的標(biāo)簽。例如，對于有5個數(shù)據(jù)的數(shù)據(jù)集，染色體(12221)表示的數(shù)據(jù)的劃分是{{x1,x5},{x2,x3,x4}}。

2.3.2適應(yīng)度函數(shù)

聚類融合的目標(biāo)是找到一個劃分使得簇內(nèi)數(shù)據(jù)的相似性較高，而簇與簇之間的數(shù)據(jù)相似性較低?；谏鲜瞿繕?biāo)，本文提出使用平均簇內(nèi)適應(yīng)度和平均簇間適應(yīng)度的差值表示每條染色體的適應(yīng)度:

(2)

式(3)和式(4)分別計算了簇Ck的簇內(nèi)適應(yīng)度和Ca與Cb的簇間適應(yīng)度:

(3)

(4)

其中：coij是數(shù)據(jù)xi和xj在所有劃分中一起出現(xiàn)的頻率，|Ck|是第k個簇的數(shù)據(jù)的數(shù)量，|P|是基聚類P中的簇的數(shù)量。

2.3.3選擇算子

選擇算子用于選擇進行交叉和變異的個體。一般遺傳算法采用輪盤賭作為選擇算子，但是輪盤賭根據(jù)適應(yīng)度隨機選擇染色體進行交叉變異操作，具有不確定性。針對輪盤賭的不確定性，本文根據(jù)聚類融合對于基聚類多樣性的要求提出使用最多重疊數(shù)量作為選擇算子。其主要思想是：對于兩個基聚類，如果兩者重疊元素越多，則選中進行交叉變異操作的概率越大；反之，重疊元素越少，選中進行交叉變異操作的概率越小。聚類融合對于基聚類生成機制產(chǎn)生的基聚類的要求是多樣性和準(zhǔn)確性，即基聚類之間互相不同且準(zhǔn)確度高。本文提出的選擇算子根據(jù)基聚類之間的重疊元素數(shù)量選擇出重疊元素最多的兩個基聚類進行交叉操作，生成不同的后代染色體，滿足了聚類融合的多樣性；選出上述兩個基聚類中的適應(yīng)度低的基聚類進行變異操作，滿足了聚類融合的準(zhǔn)確性。

圖1　選擇算子運算實例Fig. 1　Example of selecting operator

2.3.4交叉和變異操作

通過選擇算子選擇出用于交叉的染色體子集后，接下來會對選中的兩個染色體進行交叉操作。由于種群中的每個染色體所表示的劃分的簇的個數(shù)都相同，本文選用單點交叉的方法。單點交叉是在兩個父母染色體的基因上隨機選擇一個位置點i，從位置點i以后的基因進行交換產(chǎn)生兩個后代染色體，并加入當(dāng)前種群中。

通過選擇算子選擇出染色體子集后，會從中選擇適應(yīng)度較低的一個染色體進行變異操作。在要變異的染色體上，隨機選擇一個位置點i突變?yōu)椋?/p>

其中d(xi,Cj)是數(shù)據(jù)xi到簇Cj的歐幾里得距離。

2.3.5精英策略

精英策略用于從當(dāng)前種群及其交叉變異產(chǎn)生的后代中選擇優(yōu)良染色體生成下一代種群。過高的交叉率可能導(dǎo)致遺傳算法過早收斂，如果不采用精英選擇，那么變異率過高會導(dǎo)致好的解決方案的丟失。本文所使用的精英策略是在適應(yīng)度函數(shù)(詳見式(2))的基礎(chǔ)上，選擇前m個適應(yīng)度高的染色體作為下一代種群進行下一步操作。

2.4　CEIGA

CEIGA主要包括三部分：1)采用不同初始中心的K-Means算法生成m個不同的基聚類；2)以其中一個基聚類作為基準(zhǔn)基聚類，將其他基聚類與其建立對應(yīng)關(guān)系，解決簇標(biāo)簽不一致問題；3)將解決標(biāo)簽不一致問題后的基聚類進行基因編碼，作為改進遺傳算法的初始種群輸入，并且利用改進遺傳算法的選擇算子選擇染色體進行交叉和變異保證基聚類的多樣性和準(zhǔn)確性，進而得到最優(yōu)的解決方案，即聚類融合對于數(shù)據(jù)集的最終劃分。其偽代碼如算法1所示。

算法1CEIGA。

輸入有n個數(shù)據(jù)的數(shù)據(jù)集X，基聚類數(shù)量m，最大進化次數(shù)tmax，交叉變異率α。

輸出關(guān)于數(shù)據(jù)集X的劃分。

1)運行K-Means算法m次生成m個基聚類；

2)解決m個基聚類的標(biāo)簽不一致問題。

3)根據(jù)字符串組編碼策略對基聚類進行基因編碼，得到初始種群并設(shè)置當(dāng)前種群代數(shù)t=1。

4)計算每個染色體子集的重疊元素，選出m×α個染色體子集。

5)將步驟4)選擇的染色體子集進行交叉操作得到染色體后代，加入當(dāng)前種群。

6)根據(jù)式(2)計算當(dāng)前種群中每個染色體的適應(yīng)度值。

7)將步驟4)選擇的每個染色體子集中適應(yīng)度低的染色體進行變異操作得到后代，計算其適應(yīng)度值并加入當(dāng)前種群。

8)從當(dāng)前種群中選擇適應(yīng)度最高的m條染色體生成下一代種群，t=t+1。

9)判斷t是否等于tmax，如果滿足，則選擇當(dāng)前種群中適應(yīng)度值最高的染色體輸出,否則返回步驟4)。

3　基于改進遺傳算法的并行聚類融合算法

縱觀大數(shù)據(jù)領(lǐng)域的發(fā)展可知，當(dāng)前的大數(shù)據(jù)處理一直在向著近似于傳統(tǒng)數(shù)據(jù)庫體驗的方向發(fā)展。云計算及其Hadoop平臺的產(chǎn)生使得普通機器能夠建立穩(wěn)定的處理TB級數(shù)據(jù)的集群，從而實現(xiàn)并行計算。Hadoop平臺上的MapReduce編程模型是并行、分布式計算的發(fā)展。MapReduce采用“分而治之”的思想，把對大規(guī)模數(shù)據(jù)集的操作派發(fā)給一個主節(jié)點管理的各分節(jié)點共同完成，然后在主節(jié)點上整合分節(jié)點的結(jié)果得到最終結(jié)果。MapReduce就是任務(wù)的分解與結(jié)果的匯總,這兩個階段分別由map函數(shù)和reduce函數(shù)完成：map函數(shù)負責(zé)把一個大型任務(wù)分解成若干個小任務(wù)，而reduce函數(shù)則負責(zé)把每個小任務(wù)的結(jié)果匯總起來。基于改進遺傳算法的聚類融合算法通過改進的遺傳算法對基聚類進化得到比單一聚類算法結(jié)果更準(zhǔn)確的聚類劃分,這一思想符合云計算環(huán)境下MapReduce“分而治之”的思想，因此，在基于改進遺傳算法的聚類融合算法基礎(chǔ)上，本文利用MapReduce模型設(shè)計了云計算下基于改進遺傳算法的聚類融合算法(PCEIGA)。如何在云計算環(huán)境下利用MapReduce模型實現(xiàn)PCEIGA的并行聚類、提高算法聚類結(jié)果的準(zhǔn)確性是本文的研究重點。

圖2是PCEIGA在Hadoop平臺上并行實現(xiàn)的框架圖，主要包括兩個MapReduce過程：基聚類的并行和改進遺傳算法的并行。本文第一個MapReduce過程完成基聚類的生成。首先，每個節(jié)點上的map()函數(shù)將原始數(shù)據(jù)集復(fù)制到該節(jié)點上，使得每個節(jié)點上都有一份數(shù)據(jù)，然后reduce()函數(shù)對節(jié)點上的數(shù)據(jù)集進行K-Means聚類得到基聚類。在本文中有m個節(jié)點并行地執(zhí)行此過程，產(chǎn)生m個基聚類P={P1,P2,…,Pm}；接下來，隨機選擇一個基聚類作為基準(zhǔn)基聚類對其他基聚類標(biāo)簽轉(zhuǎn)化，使得m個基聚類簇標(biāo)簽對應(yīng)；然后將標(biāo)簽轉(zhuǎn)化后的m個基聚類進行基因編碼，產(chǎn)生初始種群，作為第二個MapReduce過程的輸入。第二個MapReduce過程主要完成改進遺傳算法的并行。首先，對基因編碼得到的種群進行數(shù)據(jù)分片，分配給s個節(jié)點；然后，節(jié)點上的map()函數(shù)會讀取數(shù)據(jù)獲得染色體相關(guān)信息，計算每條染色體的適應(yīng)度值，輸出〈key(染色體id),value(適應(yīng)度值)〉對。為了提高算法效率，本文在第二個MapReduce過程中加入了Combine操作。Combine的作用是對Mapper2的輸出數(shù)據(jù)進行處理，降低〈key,value〉對的數(shù)量，減少節(jié)點之間要傳輸?shù)臄?shù)據(jù)，減少網(wǎng)絡(luò)流量，從而達到降低節(jié)點通信的目的。第二個MapReduce過程的combine()函數(shù)根據(jù)選擇算子和適應(yīng)度值將染色體分為保留、交叉和變異三類，每個reduce()函數(shù)在收到關(guān)于染色體的信息后會根據(jù)相關(guān)信息對染色體進行相應(yīng)的保留、交叉或變異操作后輸出〈key(染色體id),value(適應(yīng)度值)〉對。將reduce()函數(shù)的〈key(染色體id),value(適應(yīng)度值)〉對合并形成下一代種群，如此迭代重復(fù)直至滿足最大進化次數(shù)后停止，選擇當(dāng)前種群中適應(yīng)度最高的染色體作為最終聚類結(jié)果輸出。

圖2　云計算下PCEIGA框架Fig. 2　Framework of PCEIGA algorithm in cloud computing

4　實驗與分析

本文實驗的Hadoop平臺是自行搭建的，采用完全分布式模式。在Windows 7(64位)操作系統(tǒng)上，用VritualBox軟件創(chuàng)建6臺虛擬機搭建Hadoop平臺，其中1臺虛擬機作為MasterNode(JobTracker)節(jié)點用于維護和管理集群中各節(jié)點，其余5臺作為DataNode(TaskTracker)節(jié)點用于存儲數(shù)據(jù)。各節(jié)點通過定義主機名與IP地址之間的對應(yīng)關(guān)系，配置SSH(Secure Shell)，實現(xiàn)相互通信。節(jié)點的硬件環(huán)境是AMD FX- 6300 CPU 3.50 GHz，4.00 GB內(nèi)存，200 GB硬盤，每個節(jié)點裝有Ubuntu- 14.04.4-desktop-amd64操作系統(tǒng)，其中Hadoop版本為hadoop- 2.6.0 binary，Java版本為Java- 1.7.0_101，Eclipse版本為Juno Service Release 2。

實驗數(shù)據(jù)選取的是6個常用UCI數(shù)據(jù)集，詳細信息如表1所示。本文選取了不同數(shù)量大小的數(shù)據(jù)集以測試數(shù)據(jù)集大小對CEIGA和PCEIGA的影響。UCI數(shù)據(jù)集有數(shù)據(jù)的真實劃分信息可以利用，但本文只將數(shù)據(jù)集的真實劃分信息用于最后算法性能分析，算法本身并沒有使用到這些信息。

表1　實驗中使用的UCI數(shù)據(jù)集Tab. 1　UCI datasets used in experiment

為了對算法的聚類結(jié)果進行有效評價，計算算法的最終結(jié)果與數(shù)據(jù)集真實劃分之間的ARI(Adjusted Rand Index)值來評價算法性能。ARI的計算公式如下：

ARI(A,B)=

(5)

其中：nij是劃分A的第i個簇和劃分B的第j個簇的重疊元素的個數(shù)，ai是劃分A的第i個簇內(nèi)元素的個數(shù)，bj是劃分B的第j個簇內(nèi)元素的個數(shù)，n是數(shù)據(jù)集的數(shù)據(jù)個數(shù)。ARI值越大表示劃分A和B的相似性越高。

4.1　CEIGA性能分析

選擇與CEIGA進行對比的先進聚類融合算法包括：文獻[19]的基于投票法的聚類融合(Clustering Ensemble based on Voting, CEV)、基于CSPA的聚類融合(Clustering Ensemble based on Cluster-based Similarity Partitioning Algorithm, CECSPA)、基于平均鏈的聚類融合(Clustering Ensemble based on Average Linkage, CEAL)和文獻[20]中的基于Dempster-Shafer證據(jù)理論的聚類融合(Clustering Ensemble based on Dempster-Shafer, CEDS)。圖3記錄了上述算法的結(jié)果與數(shù)據(jù)集真實劃分的ARI值。

圖3　五種算法的ARI值對比Fig. 3　ARI value comparison of five algorithms

從圖3可以看出，五個算法中表現(xiàn)最好的是CEIGA：在Iris、TSE、Waveform和WLE數(shù)據(jù)集上，CEIGA明顯優(yōu)于其他四個先進聚類融合算法；在LM和Wine數(shù)據(jù)集上，CEIGA以微弱優(yōu)勢勝出CEDS算法。五個算法中表現(xiàn)最差的是CEV算法；CECSPA和CEAL表現(xiàn)旗鼓相當(dāng)；CEDS算法表現(xiàn)最不穩(wěn)定，在Iris、LM、WLE和Wine數(shù)據(jù)集上表現(xiàn)極好，但在TSE和Waveform數(shù)據(jù)集上表現(xiàn)較差。分析產(chǎn)生上述現(xiàn)象主要是因為作為基聚類生成機制的K-Means算法極易陷入局部最優(yōu)，故而生成的基聚類大部分會受這一現(xiàn)象影響而產(chǎn)生局部較優(yōu)的結(jié)果，因此在使用投票法、CSPA、平均鏈凝聚層次聚類和Dempster-Shafer證據(jù)理論作為一致性集成函數(shù)時，得到的最終聚類結(jié)果是局部最優(yōu)的結(jié)果。本文提出的CEIGA使用改進遺傳算法作為共識函數(shù)，通過交叉和變異操作對基聚類進化得到適應(yīng)度值高(簇內(nèi)更近和簇間更遠)的基聚類從而達到全局最優(yōu)、避免局部最優(yōu)。這也是CEIGA明顯優(yōu)于其他四個先進聚類融合算法的主要原因。

4.2　PCEIGA性能分析

為了比較云計算下PCEIGA的性能，將不同規(guī)模的Hadoop集群上并行運行PCEIGA的加速比進行了比較。加速比的計算公式如下：

(6)

加速比越大，算法運行時間越少，則算法性能越好。不同規(guī)模Hadoop集群上PCEIGA的加速比如圖4所示，測試所用Hadoop集群除主節(jié)點外并行節(jié)點數(shù)從1到5。

圖4　不同規(guī)模Hadoop集群上PCEIGA的加速比對比Fig. 4　Speedup comparison of PCEIGA on Hadoop platform with different cluster size

從圖4可以看出，在WLE和TSE數(shù)據(jù)集上，PCEIGA的運行加速比隨著機器節(jié)點數(shù)的增加而快速上升，表明算法運行時間逐漸減少。主要是因為，PCEIGA的兩個MapReduce過程中設(shè)計的〈key,value〉鍵值對合理，使算法能夠高效運行；PCEIGA在對改進遺傳算法進行MapReduce并行時使用combine函數(shù)合并map函數(shù)的輸出，減少了寫入磁盤以及通過網(wǎng)絡(luò)傳輸?shù)絩educe函數(shù)的數(shù)據(jù)量，從而能提高算法運行速度，提高算法加速比。在Iris、LM、Waveform和Wine數(shù)據(jù)集上，隨著節(jié)點數(shù)的增加，PCEIGA的加速比上升比較緩慢。主要是由于對于數(shù)據(jù)量較小的數(shù)據(jù)集采用并行框架會增加時間開支和節(jié)點間的通信開銷，從而降低算法效率。相比小型數(shù)據(jù)集，采用Hadoop并行框架運行PCEIGA更適合于大型數(shù)據(jù)集。但受Hadoop的MapReduce本身開銷的影響，加速比的提升是有上限的。為了進一步分析PCEIGA的性能，計算不同規(guī)模Hadoop集群并行運行PCEIGA的聚類結(jié)果與數(shù)據(jù)集真實劃分的ARI，結(jié)果如圖5所示。

圖5　云計算下Hadoop框架運行PCEIGA準(zhǔn)確度分析Fig. 5　Accuracy analysis about PCEIGA algorithm on Hadoop platform in cloud computing

由圖5可知，PCEIGA在LM、TSE和WLE數(shù)據(jù)集上多個節(jié)點的算法ARI值并不低于單個節(jié)點的ARI值，甚至在LM和TSE數(shù)據(jù)集上，節(jié)點數(shù)據(jù)為2和3時算法的聚類質(zhì)量明顯高于單個節(jié)點的PCEIGA的結(jié)果質(zhì)量；在WLE數(shù)據(jù)集上，節(jié)點數(shù)據(jù)為3時算法的聚類質(zhì)量明顯高于單個節(jié)點的PCEIGA的結(jié)果質(zhì)量。在Iris、Waveform和Wine數(shù)據(jù)集上，單個節(jié)點上PCEIGA的ARI值以0.04的優(yōu)勢勝于多個節(jié)點的PCEIGA。出現(xiàn)這種現(xiàn)象的原因是，與單個節(jié)點的算法運行相比，多個節(jié)點并行時，節(jié)點之間的通信產(chǎn)生的誤差也會導(dǎo)致最終聚類結(jié)果質(zhì)量的下降，但這個誤差在可控范圍內(nèi)。因此，可以看出，隨著節(jié)點數(shù)的增加，PCEIGA的聚類準(zhǔn)確度會輕微上下浮動，但是在提高運行速度的前提下，這一現(xiàn)象是可以接受的。

綜上所述，隨著Hadoop框架下節(jié)點數(shù)的增加，PCEIGA聚類性能并不會明顯降低，同時算法運行的加速比明顯提升。

5　結(jié)語

本文結(jié)合聚類融合的特點提出了CEIGA，設(shè)計了基于重疊元素數(shù)量的選擇算子。對遺傳算法選擇算子的改進優(yōu)化使得遺傳算法作為聚類融合的一致性集成函數(shù)不僅保證了基聚類的多樣性，還使得最終聚類結(jié)果達到全局最優(yōu)。

根據(jù)聚類融合和改進遺傳算法的可并行性提出了PCEIGA，設(shè)計了云計算下PCEIGA的Map-Reduce并行模型,通過對基聚類生成機制和改進遺傳算法的并行處理，以及Combine過程的加入，能有效提高算法運行效率。

最后在自行搭建的Hadoop分布式平臺上完成了CEIGA和PCEIGA的性能分析。實驗結(jié)果表明，CEIGA在準(zhǔn)確度和穩(wěn)定性上都明顯優(yōu)于CEV、CECSPA、CEAL和CEDS算法，而PCEIGA也能在不影響算法質(zhì)量的情況下縮短算法運行時間，有利于進行海量數(shù)據(jù)挖掘。

使用MapReduce模型實現(xiàn)PCEIGA的結(jié)果表明，隨著節(jié)點數(shù)的增加，PCEIGA運行加速比的提升會減弱甚至下降，因此，Hadoop中并行節(jié)點的數(shù)量選擇會是一個重要的研究方向。而遺傳算法作為一致性集成函數(shù)，除了受選擇算子影響外，適應(yīng)度函數(shù)的設(shè)計也很重要。適應(yīng)度函數(shù)很復(fù)雜時，會對算法復(fù)雜度產(chǎn)生影響；反之，適應(yīng)度函數(shù)很簡單時，會影響最終結(jié)果準(zhǔn)確度。因此，后續(xù)工作將研究設(shè)計一個恰當(dāng)?shù)倪m應(yīng)度函數(shù)，以進一步提高算法運行速度和準(zhǔn)確度。

參考文獻(References)

[1]STREHL A, GHOSH J. Cluster ensembles: a knowledge reuse framework for combining multiple partitions [J]. Journal of Machine Learning Research, 2003, 3(3): 583-617.

[2]TURING A M. Computing machinery and intelligence [J]. Mind, 1950, 59(236): 433-460.

[3]WANG D X, LI L, YU Z W, et al. AP2CE: double affinity propagation based cluster ensemble [C]// Proceedings of the 2013 International Conference on Machine Learning and Cybernetics. Piscataway, NJ: IEEE, 2013:16-23.

[4]YU Z W, HAN G Q, LI L, et al. Adaptive noise immune cluster ensemble using affinity propagation [C]// ICDE 2016: Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering. Piscataway, NJ: IEEE, 2016: 1454-1455.

[5]KAO L J, HUANG Y P. Ejecting outliers to enhance robustness of fuzzy cluster ensemble [C]// Proceedings of the 2013 IEEE International Conference on Systems, Man, and Cybernetics. Piscataway, NJ: IEEE, 2013: 3790-3795.

[6]IAM-ON N, BOONGOEN T, GARRETT S, et al. A link-based approach to the cluster ensemble problem [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2011, 33(12): 2396-2409.

[7]ZHONG C M, YUE X D, ZHANG Z H, et al. A clustering ensemble: two-level-refined co-association matrix with path-based transformation [J]. Pattern Recognition, 2015, 48(8): 2699-2709.

[8]WANG L, ZHANG G Y. Cluster ensemble based image segmentation algorithm [C]// ICICSE 2015: Proceedings of the 2015 Eighth International Conference on Internet Computing for Science and Engineering. Piscataway, NJ: IEEE, 2015: 68-73.

[9]YU Z W, LUO P N, YOU J, et al. Incremental semi-supervised clustering ensemble for high dimensional data clustering [J]. IEEE Transactions on Knowledge & Data Engineering, 2016, 28(3): 701-714.

[10]ZHANG S H, YANG L, XIE D Q. Unsupervised evaluation of cluster ensemble solutions [C]// ICACI 2015: Proceedings of the 2015 Seventh International Conference on Advanced Computational Intelligence. Piscataway, NJ: IEEE, 2015: 101-106.

[11]BANERJEE B, BOVOLO F, BHATTACHARYA A, et al. A new self-training-based unsupervised satellite image classification technique using cluster ensemble strategy [J]. IEEE Geoscience & Remote Sensing Letters, 2015, 12(4): 741-745.

[12]YU Z W, CHEN H T, YOU J, et al. Hybrid fuzzy cluster ensemble framework for tumor clustering from biomolecular data [J]. IEEE/ACM Transactions on Computational Biology & Bioinformatics, 2013, 10(3): 657-670.

[13]GOSWAMI J P, MAHANTA A K. A genetic algorithm based ensemble approach for categorical data clustering [C]// INDICON 2015: Proceedings of the 2015 Annual IEEE India Conference. Piscataway, NJ: IEEE, 2015: 1-6.

[14]ALFRED R, CHIYE G J, OBIT J H, et al. A genetic algorithm based clustering ensemble approach to learning relational databases [J]. Advanced Science Letters, 2015, 21(10): 3313-3317.

[15]劉朋歡.基于生成模型的聚類融合算法[D].青島：中國海洋大學(xué),2014. (LIU P H. Generative approaches for ensemble clustering [D]. Qingdao: Ocean University of China, 2014.)

[16]DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters [C]// Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation. Berkeley, CA: USENIX Association, 2008: 10-10.

[17]吳曉璇,倪志偉,倪麗萍.云計算環(huán)境下基于分形的聚類融合算法研究[J].計算機工程與應(yīng)用,2015,51(14):1-6. (WU X X, NI Z W, NI L P. Research on fractal clustering ensemble algorithm based on cloud computing environment [J]. Computer Engineering and Applications, 2015, 51(14): 1-6.)

[18]BENMOUNAH Z, BATOUCHE M. A parallel distributed system for gene expression profiling based on clustering ensemble and distributed optimization [C]// ICA3PP 2013: Proceedings of the 13th International Conference on Algorithms and Architectures for Parallel Processing, LNCS 8285. Cham: Springer, 2013: 176-185.

[19]IAM-ON N, BOONGOEN T. Comparative study of matrix refinement approaches for ensemble clustering [J]. Machine Learning, 2015, 98(1/2): 269-300.

[20]LI F J, QIAN Y H, WANG J T, et al. Multigranulation information fusion: a Dempster-Shafer evidence theory based clustering ensemble method [C]// Proceedings of the 2015 IEEE International Conference on Machine Learning and Cybernetics. Piscataway, NJ: IEEE, 2015: 58-63.