徐占洋，鄭克長

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

0　引言

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

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

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

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

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

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

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

1　相關(guān)工作

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

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

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

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

2　基于改進(jìn)遺傳算法的聚類融合算法

2.1　基聚類生成機(jī)制

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

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

(1)

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

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

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

2.3　改進(jìn)遺傳算法

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

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

2.3.1基因編碼

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

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

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

(2)

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

(3)

(4)

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

2.3.3選擇算子

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

圖1　選擇算子運(yùn)算實(shí)例Fig. 1　Example of selecting operator

2.3.4交叉和變異操作

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

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

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

2.3.5精英策略

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

2.4　CEIGA

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

算法1CEIGA。

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

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

1)運(yùn)行K-Means算法m次生成m個(gè)基聚類；

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

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

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

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

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

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

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

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

3　基于改進(jìn)遺傳算法的并行聚類融合算法

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

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

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

4　實(shí)驗(yàn)與分析

本文實(shí)驗(yàn)的Hadoop平臺(tái)是自行搭建的，采用完全分布式模式。在Windows 7(64位)操作系統(tǒng)上，用VritualBox軟件創(chuàng)建6臺(tái)虛擬機(jī)搭建Hadoop平臺(tái)，其中1臺(tái)虛擬機(jī)作為MasterNode(JobTracker)節(jié)點(diǎn)用于維護(hù)和管理集群中各節(jié)點(diǎn)，其余5臺(tái)作為DataNode(TaskTracker)節(jié)點(diǎn)用于存儲(chǔ)數(shù)據(jù)。各節(jié)點(diǎn)通過定義主機(jī)名與IP地址之間的對(duì)應(yīng)關(guān)系，配置SSH(Secure Shell)，實(shí)現(xiàn)相互通信。節(jié)點(diǎn)的硬件環(huán)境是AMD FX- 6300 CPU 3.50 GHz，4.00 GB內(nèi)存，200 GB硬盤，每個(gè)節(jié)點(diǎn)裝有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í)驗(yàn)數(shù)據(jù)選取的是6個(gè)常用UCI數(shù)據(jù)集，詳細(xì)信息如表1所示。本文選取了不同數(shù)量大小的數(shù)據(jù)集以測試數(shù)據(jù)集大小對(duì)CEIGA和PCEIGA的影響。UCI數(shù)據(jù)集有數(shù)據(jù)的真實(shí)劃分信息可以利用，但本文只將數(shù)據(jù)集的真實(shí)劃分信息用于最后算法性能分析，算法本身并沒有使用到這些信息。

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

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

ARI(A,B)=

(5)

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

4.1　CEIGA性能分析

選擇與CEIGA進(jìn)行對(duì)比的先進(jìn)聚類融合算法包括：文獻(xiàn)[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)和文獻(xiàn)[20]中的基于Dempster-Shafer證據(jù)理論的聚類融合(Clustering Ensemble based on Dempster-Shafer, CEDS)。圖3記錄了上述算法的結(jié)果與數(shù)據(jù)集真實(shí)劃分的ARI值。

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

從圖3可以看出，五個(gè)算法中表現(xiàn)最好的是CEIGA：在Iris、TSE、Waveform和WLE數(shù)據(jù)集上，CEIGA明顯優(yōu)于其他四個(gè)先進(jìn)聚類融合算法；在LM和Wine數(shù)據(jù)集上，CEIGA以微弱優(yōu)勢(shì)勝出CEDS算法。五個(gè)算法中表現(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)象主要是因?yàn)樽鳛榛垲惿蓹C(jī)制的K-Means算法極易陷入局部最優(yōu)，故而生成的基聚類大部分會(huì)受這一現(xiàn)象影響而產(chǎn)生局部較優(yōu)的結(jié)果，因此在使用投票法、CSPA、平均鏈凝聚層次聚類和Dempster-Shafer證據(jù)理論作為一致性集成函數(shù)時(shí)，得到的最終聚類結(jié)果是局部最優(yōu)的結(jié)果。本文提出的CEIGA使用改進(jìn)遺傳算法作為共識(shí)函數(shù)，通過交叉和變異操作對(duì)基聚類進(jìn)化得到適應(yīng)度值高(簇內(nèi)更近和簇間更遠(yuǎn))的基聚類從而達(dá)到全局最優(yōu)、避免局部最優(yōu)。這也是CEIGA明顯優(yōu)于其他四個(gè)先進(jìn)聚類融合算法的主要原因。

4.2　PCEIGA性能分析

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

(6)

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

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

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

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

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

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

5　結(jié)語

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

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

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

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

參考文獻(xià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]吳曉璇,倪志偉,倪麗萍.云計(jì)算環(huán)境下基于分形的聚類融合算法研究[J].計(jì)算機(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.