基于文化基因算法和猶豫模糊集的聚類算法及其分布并行實現

王 超 英

(東莞職業技術學院 廣東 東莞 523808)

0 引 言

隨著醫院的信息化建設和普及，全國的醫療系統每天產生海量的數據，如何高效地管理醫療大數據成為了一個難題[1]。在醫學領域存在大量的高維小樣本數據，例如醫囑類文檔數據、病例類文檔數據、DNA微陣列數據[2-3]。海量高維小樣本數據集的聚類和分析需要大量的處理時間。以DNA微陣列數據為例，微陣列的維度高，且含有大量的冗余樣本和不相關樣本，嚴重影響聚類器的準確率[4]。

通過特征選擇處理能夠降低特征集的維度，刪除冗余特征和不相關特征，有助于提高數據聚類的準確率和速度，是當前高維小樣本數據挖掘領域的研究熱點[5]。為了解決上述高維小樣本數據集的瓶頸問題，許多研究人員進行了深入的分析[6]。文獻[7]基于隨機森林變量重要性分數提出了一種加權K-均值的基因微陣列數據聚類算法，以基因為對象、樣本為特征、基因的重要性分數為權重進行K-均值聚類，該算法提高了聚類結果的同質性和差異性。文獻[8]提出的高維微陣列數據混合特征選擇算法分為兩層：第一層使用信噪比方法計算全部基因的信噪比值，根據信噪比值選擇指定數目的信息基因，過濾無關基因；第二層使用改進的Lasso方法對第一層得到的信息基因候選子集進行特征選擇，剔除冗余基因。文獻[7-8]均采用了過濾式特征選擇算法，分別將隨機森林變量重要性分數和基因信噪比作為特征重要性的評價指標，此類傳統方法難以獲得最少的特征數量[9]。

DNA微陣列數據存在以下特點[10]：(1) 生物標志物的數量極低(低于1%);(2) 生物標志物能夠提高特征子集的聚類準確率;(3) 過濾式特征選擇可縮小搜索空間，但無法保證優質的特征選擇結果;(4) 樣本量少，聚類器訓練難度大。提取最少量、最高準確率的特征子集是特征選擇的兩個目標，采用元啟發式算法對兩個目標進行尋優是一個重要的研究方向，例如：量子進化算法[11]、飛蛾撲火優化算法[12]和人工蜂群優化算法[13]，但此類算法在全局搜索和局部開發之間未能實現較好的權衡，同時基于迭代的算法對于海量數據的處理速度較慢，效率較低。文化基因算法[14](Memetic Algorithm,MA)是一種基于種群全局搜索和基于個體局部啟發式開發的結合體，其搜索效率最高比遺傳算法快數個數量級。鑒于遞歸模型[15]在全局搜索和局部開發之間能夠實現較好的平衡，本文將文化基因算法和遞歸模型結合，設計了遞歸文化基因算法(Recursive Memetic Algorithm,RMA)。采用遞歸文化基因算法求解高維小樣本數據的特征選擇問題，但是基于迭代的尋優過程依然較為耗時。

分布式并行計算模型是加快大數據處理的有效方法，目前的大數據技術大多基于MapReduce框架，但該框架并不適合基于迭代的算法，原因主要有[16]：(1) 每次迭代作為獨立任務重新處理，需要重新讀寫數據和初始化數據；(2) 每次迭代需要重新從分布式文件系統加載程序，消耗I/O資源和CPU資源；(3) 前一次迭代必須全部結束并且數據全部寫入分布式文件系統，才能開始下一次迭代。Spark框架[17]則是基于內存的分布式并行計算模型，將數據緩存于各節點的內存中，從而縮短數據訪問的延遲。本文基于Spark架構設計和實現了遞歸文化基因算法，可以高效、準確地進行高維小樣本數據集的特征選擇處理。并且本文研究并提出了一種基于猶豫模糊集理論(Hesitant Fuzzy Set,HFS)的加權相關性指數度量基因的相似性，設計了基于HFS的密度聚類方法，HFS對噪聲具有魯棒性，設計了迭代Spark框架的彈性分布式數據集(Resilient Distributed Datasets,RDD)模塊將基因集聚類處理。

1 猶豫模糊集理論

HFS是一種擴展模糊集，其隸屬度不是確定值或服從確定分布，而是多個可能值，該理論對于群決策信息的處理具有優勢[18]。

1.1 HFS定義

設X={x1,x2,…,xn}為一個固定集，如果A滿足以下條件，則認為A是X的一個HFS。

A={〈x,hA(x)〉|x∈X}

(1)

設h、h1、h2為3個HFE，HFE支持以下三個運算：

(2)

(3)

(4)

給定h∈HFE(x)，x的下限和上限分別定義為：

LB:h-(x)=min(h(x))UB:h+(x)=max(h(x))

(5)

設Aenv(h)表示h的包絡線，表示為(h-,1-h+)。

1.2 HFS的相關性

設X={x1,x2,…,xn}為一個離散論域，A和B是X上的兩個HFS，表示為A={〈xi,hA(xi)〉|xi∈X,i=1,2,…,n}，B={〈xi,hB(xi)〉|xi∈X,i=1,2,…,n}。如果len(hA(xi))

(6)

兩個HFS的相關性定義為：

(7)

如果A,B∈HFS，那么CHFS(A,A)=EHFS(A),CHFS(A,B)=CHFS(B,A)。最終可計算出兩個HFS的相關系數：

(8)

HFS的相關系數具有以下屬性[19]：ρHFS(A,B)=ρHFS(B,A)，0≤ρHFS(A,B)≤1，如果A=B，那么ρHFS(A,B)=1。

2 聚類系統總體結構

本文的高維大數據聚類系統(見圖1)主要分為兩個部分：基于密度的聚類處理和遞歸文化基因的特征歸簡處理。兩個部分是遞歸迭代的關系。在每次迭代中，遞歸文化基因算法遞歸地化簡特征子集，將特征子集輸入聚類處理部分，根據聚類結果判斷特征子集的質量，實現了一種封裝式特征選擇方式。密度聚類處理應用特征子集做聚類處理，基于Spark框架提高處理的速度和效率。

圖1 高維大數據聚類系統的主要模塊圖

3 基于遞歸文化基因的特征歸簡

遞歸文化基因算法(RMA)進行特征選擇總體上重復執行文化基因算法(MA)，逐步縮小特征空間。MA采用精英機制，隨機建立種群，按聚類的適應度值(準確率)將染色體排列。首先，每個染色體做局部搜索處理，將其替換為更好的染色體；然后，采用輪盤賭選擇交叉算子的染色體，應用MA的交叉算子和變異算子。MA算法對于一般數據的特征選擇效果較好，但對高維微陣列數據的降維能力較弱，因此設計了RMA模型。

應用MA優化種群，選出適應度高于動態閾值θ的i個最優染色體，i個染色體和β%的最優特征合并組成新的特征空間，新特征子集的聚類準確率應當高于θ;再次應用MA處理上述特征子集，逐漸縮小特征空間，并且提高后續基于密度聚類的準確率。圖2為RMA的算法流程。

圖2 RMA的算法流程

(1) 局部搜索。初始化階段將排序的特征集輸入RMA做局部搜索處理，局部搜索包括ADD和DEL兩個算子。設cr為選擇的一個基因子集的染色體，P和Q分別為染色體cr選擇和排除的基因子集。ADD算子將Q的基因加入P中，DEL算子將基因從P放入Q中。局部搜索的主要問題是決定ADD、DEL算子的輸入基因集，首先采用ReliefF方法[20]將所有的特征排序，然后ADD算子選擇Q中最優的特征，加入P中，DEL算子選擇P中最差的特征，移至Q中。

(2) 交叉算子。交叉算子是一種遺傳算子，交叉算子的方式主要有單點交叉、兩點交叉、多點交叉、融合交叉和均勻交叉等，其中兩點交叉實現較為簡單，且無須設置交叉概率，因此采用兩點交叉算子。

(3) 變異算子。變異算子也是一種遺傳算子，有助于增強算法的全局搜索能力。變異率設為隨機變量q，每次迭代基于概率q應用變異算子。

(4) 綜合多目標的適應度函數。基因微陣列的聚類準確率結果作為主目標，特征數量作為次目標。具體方法為：設置一個誤差域值，在最大化次目標的情況下，保留其中準確率誤差小于閾值的染色體，刪除高于閾值的染色體。算法1所示為適應度評價算法，采用加權平均準確率和特征數量決定優質的染色體，其中γ=1-(選擇的特征數量/特征總數量)。

算法1適應度評價算法

輸入：染色體ci,cj。

輸出：優質染色體c。

1. if ((mod(acc(ci)-acc(cj))>α))

//mod表示模運算，acc()為準確率

2. if (acc(ci) >acc(cj))

//比較準確率

3. returnci;

4. else

5. returncj;

6. else

7.v=((w1×acc(ci))+(w2×γ(ci)))-((w1×acc(cj))+(w2×γ(cj)))

8. if (v>0)

9. returnci;

10. else

11. returncj

(5) 特征空間化簡。設一個動態閾值φ，種群的top-i染色體與φ作比較，如果染色體的適應度高于φ，則重建種群。通過調節φ將種群規模從100%調節至ρ%，重建種群時，φ設為top-i種群的平均值。算法2是φ的增加算法偽代碼，其中：r是種群重建的次數，φ隨著r遞增，參數l1,l2,l3,step等參數根據實驗確定。算法3是φ的衰減算法偽代碼，φ隨著recn增加而降低。如果處理測試集的特征集較小且準確率高，或者達到了預定義的最大遞歸次數，則停止遞歸模型。根據實驗結果將li值設為：l1=8,l2=6,l3=3,l4=10,l5=13。

算法2φ的遞增算法

輸入：top-i染色體的平均準確率：accavg。

輸出：動態閾值φ。

1.stepl=step×2；

2. if (r>l1)

3.φ=max(accavg,100-stepl);

4. else if (r>l2)

5.φ=max(accavg,100-2×stepl);

6. else if (r>l3)

7.φ=max(accavg,100-3×stepl);

8. end if

算法3φ的衰減算法

輸入：種群重建次數：recn。

輸出：動態閾值φ。

試驗過程中，每周從每個重復組中隨機選出1只小鼠，宰殺解剖后分別切取十二指腸段、空腸段、回腸段各3 cm左右。按照ELISA試劑盒使用說明書通過酶標儀進行測定腸道黏膜SIgA的表達水平。試劑盒購置于德國IBI分裝公司。

1. if (recn>l4&&φ≥ρ+step)

2.φ=φ-step;

3. if (recn>l5&&φ≥ρ-step)

4.φ=φ-step;

5. end if

4 基于密度的聚類系統

4.1 聚類算法

設ξ為類的最少成員數量，τ為類內成員之間的最大距離。本文的研究對象為DNA微陣列數據集，所以假設數據元素為基因數據。設Nτ(gi)表示與基因(gi)距離小于τ的基因集，如果(|Nτ(gi)|+1)≥ξ，則稱gi為一個核心基因(Core Gene,CG)，|Nτ(gi)|表示Nτ(gi)的大小。類中的非CG基因稱為邊緣基因(Border Gene,BG)。設G={g1,g2,…,gn}為一個基因集，如果gb∈CG且ga∈Nτ(gb)，那么ga由gb密度直達，將gb由ga密度直達表示為ga→gb，核心基因具有自我密度直達的性質。設一個基因序列為{g1,g2,…,gk}，如果存在一個密度直達序列滿足條件gi→gi+1，1≤i≤k-1，那么g1向gk密度可達，表示為g1?gk。密度可達具有對稱性，即g1?gk≡gk?g1。如果一個非CG與任意的CG均不是密度可達，那么該基因為孤立基因(Outlier Gene,OG)。CG的鄰居基因之間密度相連，并且所有可達基因均與CG密度相連。如果存在gk?gi，gk?gj，gk∈CG，那么gi和gj密度相連，本文將密度相連表示為gi?gj。對于聚類問題，同一個類的基因之間密度相連。

4.2 基于猶豫模糊理論的基因相似性度量

相似性度量是決定聚類準確性的關鍵因素，采用HFS相關系數度量基因的相似性。設Gj為m個HFS的元素，cor=(ρij)m×m為一個相關矩陣。根據式(8)，ρij表示Gi和Gj間的相關系數，ρij具有以下屬性[19]：(1) 0≤ρij≤1,i,j=1,2,…,m；(2)ρii=1,i=1,2,…,m；(3)ρij=ρji,i,j=1,2,…,m。

Gk={〈Col,hGk(Col)〉|Col∈Co,Gk∈G}

(9)

將表達譜值Exp做歸一化處理，即{0≤Exp≤1|Exp?hGk(Col)}，hGk(Col)是基因Gk在條件hGk(Col)下的猶豫模糊元素，表示為HFE(k,l)。

(10)

WCHFS(Ga,Gb)=

(11)

(12)

5 分布式聚類系統設計

采用基于密度的聚類算法對基因微陣列做聚類處理，基于Spark框架實現對聚類算法的分布式處理。基于Spark框架的分布式聚類算法如圖1所示，主要分為5步：① 數據預處理；② 特征歸簡；③ 計算距離；④ 建立子類；⑤ 最終融合。

Spark框架由1個master模塊和若干的worker模塊組成。Master為worker分配job，在driver的協助下控制計算程序。worker的job從RDD、分布式文件系統(Hadoop Distributed File System,HDFS)、數據幀(DataFrame)等存儲系統讀取數據，然后處理剩余數據并輸出結果。worker節點的每個job由多個階段組成，worker串行地完成各個階段，每個階段可能獨立或者依賴之前階段的輸出。Spark內部將數據分割為若干的分區，每個worker節點處理有權限的部分分區，輸出相應的結果。worker節點度量數據的相似性，Spark的平臺負責實現分布式處理程序的細節，例如：負載均衡、容錯機制、數據分布、尋址處理等。

Spark可獨立運行或者建立于Hadoop YARN、Apache Mesos和Amazon EC2等云計算平臺。Spark支持分布式數據存儲系統，包括HDFS、HBase等。本文在YARN和EC2上建立Spark，采用HDFS作為分布式數據存儲系統。

5.1 數據預處理

基因表達數據集的預處理內容主要為：采用表達譜對數變換處理[21]將輸入數據集歸一化，將一些數據做單位轉換和偏差轉換處理。如果實驗矩陣40%以上的行是空值，那么過濾這種表達譜矩陣。例如：如果{(Ga,Gb)∈HFS,leni(hGa(xi))

每個微陣列實驗是一個m×n的矩陣M，m是基因的數量，G=(G1,G2,…,Gm)，n是實驗條件的數量，Co=(Co1,Co2,…,Con)。假設共存在q個醫學實驗，最終共有n個條件下對m個基因的q次實驗結果。設置一個Spark driver程序歸一化矩陣每行的數據，計算每行數據的均值μ和方差σ。將舊的表達譜替換為新值，計算式表示為：

(13)

5.2 特征歸簡

采用第3節中基于遞歸文化基因的特征歸簡算法縮小特征空間。

5.3 計算距離

加權的HFS相關系數WρHFS(Ga,Gb)表示基因Ga和Gb之間行為的相似性，相關系數越高說明基因行為的相似度越高。從HDFS讀取基因表達譜矩陣，然后轉化為RDD格式。每個worker節點運行一個迭代程序，并行地計算全部基因的加權信息能量WEHFS(Gk)。最終，通過key函數的reduce累加全部的能量值，將基因的ID作為key，信息量是key操作的目標。計算加權相關系數之前，driver生成一個三角矩陣，稱為watch列表。master節點檢查watch列表，驗證兩個條件：(1) 計算不同基因集{Ga,Gb}之間的加權相關性；(2) 每一對基因的加權相關性應當僅計算一次，即WCHFS(Ga,Gb)=WCHFS(Gb,Ga)。

算法4所示是計算距離的偽代碼。在初始化階段為watch列表的每個元素設置一個預定值，作為是否已經計算的標記。逐漸將watch列表的元素替換為計算的加權相關系數，每個worker節點并行地計算基因的加權相關系數。最終master節點在每次迭代結束更新watch列表，master節點在watch列表的約束下修改RDD的內容。在watch列表中沒有相關系數記錄的基因對保存于相同的RDD中，然后計算它們的加權相關性并保存于watch列表中。重復該迭代程序，最終使所有基因對均具有相關性記錄。該程序具有可擴展性，能夠處理任意規模的輸入數據矩陣。

算法4計算距離的偽代碼

輸入：watch列表WLE。

1. for each (WLEi?WLE)

2. WLEi←0;

//初始化為缺省值

3. end for

4. while ((WLEi?WLE)==0)

5. shuffle_rdd()；

6. 計算WCHFS；

7. 更新WLEi；

8. 計算WρHFS；

9. 生成GPM；

10. 建立DRM

算法5是建立密度可達矩陣的偽代碼。由近似矩陣生成密度可達矩陣，因為密度可達具有對稱性，所以無須保存對稱的可達性，密度可達也是三角矩陣形式。基因分布于各個worker節點，近似矩陣中基因Gi的第i列和第m+1-i行元素加入一個向量中，稱為Vi，每個向量表示一個基因和其他所有基因的相似性，該向量被分配至各個worker節點。設計一個函數記錄Vi中加權相關系數高于閾值((WρHFS)i,j>τ)的基因數量Gj。每個節點并行地調用計數函數，將計數值高于ξ(|Nτ(Gi)|>ξ)的基因標記為核心基因。

算法5建立密度可達矩陣

1. for each (Gi?RDD)

2.CntGi=0；

//初始化計數器

3. for each (Gj∈vector(Gi),i≠j)

4. if [(WρHFS)i,j>τ]

5.CntGi=CntGi+1；

6. end for

7. end for

8. for each (Gi?RDD)

9. if (CntGi>ξ)

10.Gi.coregene=TRUE；

//Gi標記為核心基因

11. end for

12. fore ach (Gi?RDD &&Gi.coregene == TRUE)

13. for each(Gj∈vector(Gi),i≠j)

14. if ((WρHFS)i,j>τ)

15.Gi?Gj；

//更新RGL(Gi),RGL(Gj)

16. end for

17. end for

18. for each (Gi?RDD)

19. for each (Gj∈RGL(Gi),i≠j)

20. list(Gi)?list(Gj)；

//更新RGL()

21. end for

22. end for

標記完所有的核心基因之后，將所有加權相關系高于閾值τ的基因標記為對Gi直接密度可達，即{Gi→Gj|(Gj)∈Nτ(Gi),Gi∈CG}。可能某個基因對于多個基因密度可達，所以采用一個可達基因列表(Reachable Genes List,RGL)記錄對某個基因的密度可達基因。Gi被保存于Gj的可達基因列表中，Gj被保存于Gi的可達基因列表中。計算所有核心基因的直接密度可達之后，將直接密度可達泛化為密度可達。如果兩個基因之間密度直達，那么列表內所有基因均為間接密度可達。

5.4 子聚類階段

為每個基因Gi創建一個ID和數據結構，將序號i作為基因的ID，每個基因設置一個狀態記錄該基因是否被訪問，并且設置一個狀態記錄該基因是否為核心基因。每個基因的列表RGL記錄密度可達的鄰居基因，根據密度可達矩陣DRM計算RGL。設置一個狀態變量記錄該基因是否為邊緣基因，設置一個UID列表記錄子類的UID值，將屬于子類的基因添加到子類對應的UID列表中，如果基因的列表為空，說明該基因尚未被分配子類。

算法6是子聚類算法的偽代碼。master節點將密度可達矩陣中的基因分配至各個worker節點，worker開始并行迭代子聚類程序。基因作為子聚類程序的輸入，基因的子聚類結果作為輸出。子聚類程序將核心基因作為初始化子類的中心基因Gi，對應的UIDi將添加到核心基因Gi的UID列表中。如果一個密度可達基因Gf是核心基因，則將UIDi分配到Gf和Gf的所有密度可達基因。worker節點nextUID()函數生成唯一的UID，該函數保證不同worker程序UID值不相同。

算法6子聚類算法

輸入：RDD。

//Spark RDD數據庫

輸出：UID。

//基因的子類ID

1. for each (Gi?RDD&& CGstatus(Gi) == TRUE)

2. if (visiting_status(Gi) == UNVISITED)

//狀態未訪問

3. visiting_status(Gi) == VISITED;

//狀態已訪問

4. UID(i)←nextUID();

5. UIDlist(Gi) = UIDlist(Gi) + UID(i);

6. for eachGjin RGL_Gi

7. visiting_status(Gj) == VISITED;

8. UIDlist(Gk) = UIDlist(Gk) + UID(i);

9. if CGstatus(Gk) == TRUE

10.j=k；

11. end for

12. end if

13. end for

14. for each (Gi? RDD&&((UIDlist(Gi)== NULL)‖(visiting_status(Gj) == FALSE)))

15. BGstatus(Gi) = TRUE;

16. end for

每個子線程首先處理尚未訪問的核心基因Gj，為Gj分配新的UIDj和密度可達基因集，UIDj的基因訪問狀態變量修改為“訪問”，最終訪問完所有的基因。如果一個基因由兩個不同核心基因密度可達，則其UID列表中會存在多個UID值。

在程序結束階段將未被訪問的基因標記為邊緣基因BG。并且為每個子類指定一個骨架基因，骨架基因的決定方法為同一個UID列表中所有基因的HFE值，計算方法為：

(14)

式中：Gpro為骨架基因;hGPro是子類中所有基因的HFE;β是子類的基因數量。

5.5 融合階段

將分布式處理獲得的子類融合為總體的聚類。計算兩個子類UIDi、UIDj之間的相同成員，如果滿足以下任一條件：

(1) 子類UIDi和UIDj之間相同基因的數量大于ξ，即{Ga∈UIDi,Ga∈UIDj,i≠j,|Ga|>ξ}；

(2) 子類骨架基因之間的相似性大于τ，即{WρHFS(Gpro(UIDi),Gpro(UIDj))>τ,i≠j}。

那么將子類UIDi和UIDj合并為新子類UIDk。如果子類UIDi和UIDj合并為UIDk，那么UIDi和UIDj的類標簽替換為UIDk，UIDk的基因數量等于UIDi和UIDj之和。

6 實 驗

6.1 實驗環境和參數設置

(1) 實驗數據集和實驗環境。在Hadoop YARN集群管理平臺搭建獨立的Apache Spark 2.0軟件。單一的基因微陣列數據集對實驗的工具和環境具有敏感性，為了提高實驗結果的可靠性，減小噪聲影響，采用多個微陣列數據集測試算法的性能。這些數據集組成了多條件、多實驗下基因行為的猶豫模糊觀察樣本。

采用臨床數據和人工合成數據從多個角度測試算法的各個性能：臨床數據來自于不同的臨床實驗，設立相似的實驗條件以評價結果的精度和效果；人工合成數據為大規模數據集，加入噪聲數據測試算法的魯棒性和可擴展性。第一個臨床數據集[23]為肝臟組織的cDNA、核苷酸、表達譜數據，數據集包含430個基因芯片微陣列、cDNA微陣列和寡核苷酸，將該數據集簡稱為肝臟。第二個臨床數據集[24]簡稱為POM，是體內裂殖酵母全局細胞循環控制的基因微陣列數據集，該數據集是多組實驗的微陣列數據，并且是一個關于時間的函數。第三個數據集[25]簡稱為SPC，是一個大規模的數據集，測試本算法的可擴展性。

(2) RMA的參數設置。應用輪盤賭策略從種群中選擇染色體，種群大小設為15，每對染色體應用兩點交叉算子。染色體的第一個數量范圍為[n/2,3n/4]，n是種群的特征數量。采用精英機制保留父種群和子種群的最優染色體，準確率的權重設為特征數量權重的4倍，容錯度α=2。在RMA優化種群的過程中，保留種群中適應度高于動態閾值φ的i=3個最佳染色體。特征歸簡處理之后，收集β%個最佳的特征組成新的特征空間。根據實驗結果分析，將參數β設為定值5，最大迭代次數為20次，ρ=94.5，w1=4，w2=1，q=0.3，step=0.5，初始種群的特征數量范圍為[m/2, 3m/4]，m為染色體的特征數量。

(3) 聚類處理的性能指標。選擇3個常用的聚類算法性能評價指標，分別為： 鄧恩指數(Dunn Index,DI)、Davies-Bouldin指數(Davies-Bouldin Index,DBI)和Silhouette指數(Silhouette Index,SI)。

6.2 實驗結果與分析

選擇4種較新的聚類算法與本文算法做比較來綜合評價本文算法的性能，分別為MBC[25]、HRSC[26]、MOOC[27]、EGWOM[28]。其中MBC是基于建模的聚類算法，HRSC是基于Hessian矩陣的聚類算法，MOOC是基于多目標優化的聚類算法，EGWOM則是基于灰狼優化算法和MapReduce的聚類算法。

(1) 聚類性能結果。圖3、圖4、圖5分別為四個算法對于3個臨床數據集的實驗結果。DBI值越小表示聚類結果的簇內緊密，簇間分離大。觀察實驗結果可見，本文算法對于3個數據集的聚類準確率均優于其他4種算法，本文算法在聚類系統中采用猶豫模糊加權相關系數評估基因行為的相似性，根據基因的密度可達性將基因聚類，該設計對于高維小樣本的基因微陣列數據實現了較好的效果。在特征歸簡處理中，采用文化基因算法對特征空間進行封裝式的特征選擇，實現了較好的優化效果，降低了基因的冗余度且排除了噪聲基因。

圖3 肝臟數據集的聚類性能結果

圖4 POM數據集的聚類性能結果

圖5 MOOC數據集的聚類性能結果

(2) 擴展性實驗和計算效率。采用POM數據集作為人工數據集，測試算法的可擴展性和計算效率。將POM數據分別合成POM1、POM2、POM3、POM4四個數據集，POM1、POM2、POM3、POM4分別是將POM數據集復制1 000次、10 000次、100 000次和1 000 000次的數據集，結果如圖6所示。可以看出，隨著數據集規模10倍的擴展，SI指標并未呈現數倍的減低，數據規模增至1 000倍，SI指數大約降低0.1，DI指數大約降低0.15。結果證明了本文算法具有較好的可擴展性，對于大規模的數據集依然具有較好的聚類性能。

圖6 擴展性實驗的聚類性能結果

圖7為不同規模數據集相應的處理時間。可以看出，隨著數據集規模的指數級增長，處理時間也呈現出明顯的升高。比較POM1和POM4，數據集規模增加了1 000倍，但是時間僅提高了約10倍，所以本文算法在計算效率上也具有較好的擴展性。

圖7 擴展性實驗的處理時間結果

(3) 與其他算法的處理效率比較。圖8為5個聚類系統對于肝臟和SPC臨床數據集的處理時間結果。可以看出，MBC和HRSC兩個算法的處理時間均明顯高于其他三個算法，主要原因是這兩個算法是一種串行處理機制，雖然MBC算法通過多模型化簡減小了特征空間和數據維度，但是依然保持較高的計算時間。HRSC在Hessian矩陣的處理過程中需要大量的計算，具有較高的計算成本。MOOC是一種多目標優化的聚類算法，該算法基于分布式多目標框架加快了計算速度，EGWOM則基于MapReduce框架實現了分布式處理，但是MapReduce具有以下三點不足：① 每次迭代作為獨立任務重新處理，需要重新讀寫數據和初始化數據；② 每次迭代需要重新從分布式文件系統加載程序，消耗I/O資源和CPU資源；③ 前一次迭代必須全部結束并且數據全部寫入分布式文件系統，才能開始下一次迭代,不僅具有較大的I/O開銷，也導致了時間的延遲。本文算法基于Spark平臺實現了分布式的處理過程，對于迭代處理程序實現了較快的速度。

圖8 5個聚類系統的處理時間

7 結 語

為了支持海量高維小樣本數據的分析和挖掘，設計了基于遞歸文化基因和Spark分布式計算的高維大數據聚類系統。該系統每次迭代作為獨立任務重新處理，不需要重新讀寫數據和初始化數據；每次迭代直接從緩存系統加載程序，無須消耗額外的I/O資源和CPU資源。受益于遞歸文化基因算法和Spark分布式計算平臺的諸多優點，本文算法實驗獲得了較好的聚類和聚類效果。

Spark平臺將各個worker的數據緩存于內存中，無須消耗額外的I/O資源和CPU資源，但是增加了內存的負擔，在海量高維小樣本數據挖掘過程中產生大量的中間數據，導致不可忽略的內存負擔，未來將關注于降低聚類系統的內存消耗。