基于Hadoop的改進型遺傳聚類算法①

潘俊輝,王 輝,張 強,王浩暢

(東北石油大學 計算機與信息技術學院,大慶 163318)

目前互聯網上產生了海量的數據,而單機串行處理海量數據時存在瓶頸,因此使用云計算、大數據對海量數據進行挖掘的技術不斷涌現.文本聚類可將相似的文本進行歸類處理,提取出文本中的關鍵信息,該技術目前被廣泛的應用在眾多領域[1,2].針對目前互聯網上的海量數據,采用Hadoop對海量數據并行化實現文本聚類可有效的解決單機處理數據效率低的缺點.

目前,國內外的一些學者對文本聚類的算法進行了研究.國內的賈瑞玉等[3,4]基于MapReduce 模型并行化實現了遺傳K-means 聚類算法;趙衛中等[5]通過對云計算平臺Hadoop 進行研究,將K-means 聚類算法與遺傳算法相結合并基于Hadoop 平臺進行了并行實現;而國外的Er和Erdo?an[6]通過改進遺傳算法中的染色體編碼和適應度函數來選取聚類算法中的最優K 值;文獻[7]中的Jiang為減少算法的計算量,以遺傳算法中染色體的基因編碼值作為K-means 聚類算法的簇中心.

本文針對K-means 聚類算法存在易陷入局部最優解等缺點,而遺傳算法所具備的特點正好可解決其缺點,由此提出并實現了一種基于Hadoop的改進型遺傳聚類算法.

1 Hadoop 平臺及文本聚類

1.1 Hadoop 平臺

Hadoop 平臺是由Apache Software Foundation 開發的開源項目[8,9].該平臺的核心組件是MapReduce和HDFS.

HDFS 以分布式的形式將劃分的數據塊存儲到多節點中.其中名字節點的工作用于管理名字空間和處理有關客戶端對數據的訪問等操作;數據節點的工作則用以完成所在節點的存儲、根據名字節點的要求實現對數據塊的創建和刪除等操作[10,11].

MapReduce的核心是map和reduce 函數,通過它們可實現對海量數據的并行化編程.MapReduce 中用戶輸入的鍵值對在map的映射下會得到新的鍵值對作為中間輸出結果,而該中間結果經過reduce 函數的規約處理后,可得到最終結果[12,13].

1.2 文本聚類

文本聚類是指將無序的對象作為輸入,使用相似性度量函數計算未知類別文本的相似性,輸出則為相似性文本組成的簇集.其聚類過程采用數學形式表示為:設文本數據集:D={d1,d2,…,di,…,dn},di為數據集中的文本,n為總文本數,聚類之后得到的簇集為:E={e1,e2,…,ej,…,ek},ej為相似文本聚成的簇,k為聚類個數.當滿足條件?di(di∈D),?ej(ej∈E),di∈ej,將語料庫D分為k個簇,使其滿足如下公式:且ei∩ej=φ.

2 基于Hadoop的改進型遺傳聚類算法

2.1 遺傳算法

遺傳算法由學者Holland 提出.該算法包括5 個不可缺少的成分:種群規模、編碼、種群初始化、適應度函數和遺傳操作.

2.1.1 編碼

常見的編碼方法有二進制編碼、浮點數編碼和符號編碼,因二進制編碼在編碼和解碼上操作簡單,易于實現,故最為常用.

2.1.2 種群初始化

編碼方式確定后,可對種群進行初始化,通常可采用兩種方法,一種是參數范圍內通過重復隨機選擇個體的方式達到種群所需的規模;另一種則在局部最優解區間內,根據經驗選出初始種群.

2.1.3 適應度函數

適應度函數的選擇通常和目標函數相關.當目標函數分別為求最小值和最大值問題時,適應度函數分別如式(1)和式(2)所示.

式中,Fmin為最小值,Fmax為最大值,f(x)均為適應度值[14].

2.1.4 遺傳操作

選擇算子通過選擇策略將種群中適應度值較大的個體選擇出來,將較優的個體傳給下一代.

交叉算子決定著遺傳算法的全局尋優能力,是算法的核心.在進行交叉操作時可通過單點交叉、兩點交叉和多點交叉等方式進行.

在種群規模較大時,可通過變異操作提高遺傳算法的局部搜索能力.一般變異概率取值均小于0.1.通常在二進制編碼中,變異操作就是互換0和1的操作.

2.2 改進型遺傳算法

針對遺傳算法存在的不足和增強遺傳算法的全局搜索能力,從而保證種群的多樣性,提出了一種新的改進型遺傳算法(Improved Genetic Agrithom,IGA),該算法分別在交叉算子、變異算子和自適應遺傳算子上做了相應的改進.

2.2.1 交叉算子、變異算子和遺傳算子的改進

遺傳算法在執行時不僅要提高收斂速度,也應在迭代過程中提高種群的多樣性以增強其全局尋優能力,因此本文對交叉算子進行了改進,分別通過進行族內交叉和族間交叉來實現.

變異算子并沒有直接選取所有變異后的個體,而是通過比較變異前后的個體已防止優秀的個體被破壞.

為防止算法陷入局部最優,本文采用的自適應算子如式(3)和式(4)所示.

式中,f′=(fmax+favg);f′′為要變異個體的適應度值;pcmax,pcmin,pmmax,pmmin均在(0,1)之間.

2.2.2 IGA 算法實現的具體步驟

Step 1.給出種群規模N,交叉概率Pc,變異概率Pm和最大迭代次數Gmax;

Step 2.生成初始種群,對初始種群進行二進制編碼;

Step 3.采用最小生成樹Prim 算法對種群規模為N的種群進行分類,得到的最小生成樹的每個子連通圖作為子類,對子類編號得到Ci(i=1,2,…,k);

Step 4.對個體Pi(i=1,2,…,N)的選擇采用輪盤賭選擇法;

Step 5.執行交叉操作,對個體Pi(i=1,2,…,N)的交叉過程為:

(1)在Pi所屬的類Cic(Cic∈{C1,C2,…,Ck})中進行查找,隨機選擇一個類Cic1(Cic1∈{C1,C2,…,Ck}且Cic≠Cic1)并從中選擇出適應度值最大對應的個體Pj,對Pi和Pj進行單點交叉,得出子個體表示為T1和T2;

(2)在Pi所屬的類Cic(Cic∈{C1,C2,…,Ck})中尋找據Cic最遠的類Cic2并隨機獲得一個最優的個體Pk,對Pi和Pk進行單點交叉,得出子個體表示為T3和T4;

(3)在Pi所屬的類Cic(Cic∈{C1,C2,…,Ck})內選擇最優個體Pn,對Pi和Pn進行單點交叉,得出子個體表示為T5和T6;

(4)對Ti,i∈(1,2,3,4,5,6)進行比較,從中得到最優子個體Ti并將Ti賦值給Pi.

Step 6.對Pi執行變異操作,將得到的新個體Pj的適應度值與Pi的進行比較,最優的賦值給Pi.

Step 7.比較Pi的數目與種群規模,如小于轉到Step 4,如相等則繼續;

Step 8.將迭代次數與設定的最大迭代次數Gmax進行比較,如相等,算法結束,否則轉向Step 3.

2.3 改進型遺傳聚類算法

將上述改進的遺傳算法與K-means 聚類算法相結合得到改進型的遺傳聚類算法IGA-K,在IGA-K 算法中將K-means 算法的聚類中心和聚類中心的個數分別作為遺傳算法的染色體的基因和染色體的長度,并對其適應度函數和編碼方式進行了改進.

2.3.1 適應度函數的設置

為得到合適的分類結果,將IGA-K 算法的適應度函數設置為式(5)所示:

為使類內更加緊湊,式中Dmin的值盡可能取大,而C(x)的值盡可能取小.

2.3.2 編碼方式的選擇

改進的遺傳聚類算法中編碼方式采用混合型編碼,具體為:

2.3.3 IGA-K 算法的基本步驟

改進型遺傳聚類算法(IGA-K)的具體實現過程如下:

Step 1.給出遺傳操作的基本參數;

Step 2.對初始種群采用改進的編碼形式實現編碼;

Step 3.采用K-means 聚類算法的初始聚類中心作為種群中的每個個體并實現對樣本的分類,依據結果計算得到適應度值.

Step 4.按照IGA 算法進行個體的分類和執行相應的遺傳操作;

Step 5.算法如滿足結束條件則結束,否則轉到Step 3 接著執行.

2.4 基于Hadoop的改進型遺傳聚類算法

由于K-means 算法和遺傳算法二者均具有并行性的特點,由此本文將改進型的遺傳聚類算法遷移到Hadoop 平臺上進行并行化的實現并將其命名為H-IGAK 算法.為并行化實現該算法必須實現兩個函數,其中一個關鍵函數為遺傳算法中用于求個體適應度的內部子函數(K-inner),另一個函數則是H-IGA-K 算法的主函數.

2.4.1 K-inner 內部子函數的實現

K-inner 中包含3 個函數,分別為Map、Combine和Reduce,其中Map 函數的功能為計算數據集中各個樣本所屬的類別,輸入輸出均為鍵值對.Map的輸入鍵值對中的key表示當前樣本相對于數據文件起始點的偏移量;value則為樣本屬性值生成的字符串;輸出鍵值對中的key'表示所屬類的序號,value'和value一樣,意義沒發生變化.

Combine 函數為計算本地節點中各類的樣本數及其屬性值組成的字符串.該函數的輸入鍵值對中的key表示樣本所屬類的序號,value為樣本屬性值生成的字符串;輸出鍵值對中的key'表示樣本所屬類的序號,value'則為樣本總數和樣本屬性值組成的字符串.

在K-inner 中,Reduce 函數的功能尤為重要,因此這里主要說明Reduce 實現的偽代碼.

2.4.2 H-IGA-K 算法主函數的實現

H-IGA-K 算法主函數實現的過程中的關鍵點同樣是Reduce 函數,下面是Reduce 實現過程的偽代碼.

3 實驗結果

本文對基于Hadoop的改進型遺傳聚類算法進行了實驗.實驗采用10 臺相同的計算機搭建了實驗平臺;該平臺使用的軟件為Hadoop-2.9.1.tar.gz、CentOS-7-x86_64-NetInstall-1804.iso和jdk-8u181-linux-x6.實驗用數據集為從UCI 數據庫的Iris、Glass 及Adult 三個數據集中選擇出的數據,并經人工構造而得,構造的3 個數據集Dataset1、Dataset2和Dataset3的規模分別為100、1000和5000,3 個數據集對應的分類數分別為3、5和10.H-IGA-K 算法參數分別為:Gmax=300、Pc=0.92、Pm=0.02、自適應算子中的pcmin、pmmin、pcmax和pmmax的取值分別為0.1,0.05,0.9和0.1.實驗分別從聚類準確性和聚類效率兩個方面進行了測試.

3.1 聚類準確性實驗

為測試基于Hadoop 改進型遺傳聚類算法的聚類準確性,本實驗使用基于Hadoop的K-means 算法和H-IGA-K 算法對實驗用數據集中的數據分別進行了處理,表1給出了二者的聚類準確率情況.

由表1可見,隨著數據規模的增加,兩種算法的聚類準確率均在下降,但下降的程度有所差距,并且在任何一個數據集下H-IGA-K 算法在聚類準確率上均比基于Hadoop的傳統K-means 聚類算法要高,特別是Dataset3 數據集,由此說明基于Hadoop的改進型遺傳聚類算法優于基于Hadoop的K-means 聚類算法,而且適用于處理大規模的數據集.

表1 聚類準確率比較

3.2 聚類效率實驗

為了測試基于Hadoop 改進型遺傳聚類算法的聚類效率,本實驗通過對3 個測試數據集Dataset1、Dataset2和Dataset3 分別在1、5、10 個節點構建的集群上進行了基于Hadoop的改進型遺傳聚類算法的實驗,表2給出了數據集Dataset1、Dataset2和Dataset3在不同節點個數上進行文本聚類時運行所需的時間比較.

表2 3 個測試數據集在不同節點進行文本聚類的運行時間(s)

由表2可見,對Dataset1、Dataset2和Dataset3 進行操作時,Hadoop 集群節點個數越多,程序運行時所需的總時間均在減少,節點個數增加越多,程序運行所需時間越少,并且隨著數據集規模增加,算法運行時消耗的時間減少的也越多,由此表明基于Hadoop的多節點的集群更適合處理大數據集,特別在節點個數達到10 個時,算法運行效率大大提高.

4 結論

本文提出了一種改進型的遺傳聚類算法,并針對單機串行對海量數據聚類效率低的問題,將改進型的遺傳聚類算法基于Hadoop 平臺進行了實現.實驗表明改進型的算法優于經典聚類算法,在聚類準確性和聚類效率上均有較大的提高,適用于處理大規模的數據集.本文主要針對傳統K-means 存在易陷入局部最優解的缺點進行的研究,而傳統的K-means 算法存在諸多不足,因此在接下來的研究中,還可嘗試解決K-means算法的其他不足點.