基于免疫算法的非監督克隆選擇聚類算法研究

韋　靈（廣西科技大學鹿山學院電氣與計算機工程系，柳州545001）

基于免疫算法的非監督克隆選擇聚類算法研究

韋靈
（廣西科技大學鹿山學院電氣與計算機工程系，柳州545001）

在詳細分析克隆選擇算法的基礎上，提出非監督克隆選擇聚類算法。該算法是數據驅動的自適應調整其參數，它對數據進行分類的操作盡可能快，改善過早收斂的問題，提高數據聚類的速度。通過使用一些人工和現實生活中的數據集，比較非監督克隆選擇聚類算法與著名的K-means算法之間的性能優劣。實驗結果表明，該算法不僅解決K-means算法需事先確定的類數K和在次佳值卡住的缺點，而且在功能上比傳統的K-means分類算法具有較高的分類精度和更高的可靠性。

人工免疫系統；克隆選擇算法；聚類；多目標優化；K-means算法

0　引言

從信息處理的角度來看,免疫系統是與神經系統、遺傳系統并列的人體三大信息系統之一[1]。免疫是人體經過長期的進化所具有的特殊的保護性生理功能,通過免疫機制人體能夠識別“自己”,排除“非己”,以維持人體內環境的平衡和穩定。免疫是生物體的特異性生理反應,由具有免疫功能的器官、組織、細胞、免疫效應分子及基因等組成[2]。人工免疫系統（Artificial Immune Systems，AIS）是由免疫學理論和觀察到的免疫功能、原理和模型啟發而生成的適應性系統。這方面的研究最初從20世紀80年代中期的免疫學研究發展而來[3]。人工免疫系統是人工智能領域的最新研究成果之一，是模仿自然免疫系統功能的一種智能方法，它實現一種受生物免疫系統啟發，通過學習外界物質的自然防御機理的學習技術，提供噪聲忍耐、無教師學習、自組織、記憶等進化學習機理，結合了分類器、神經網絡和機器推理等系統的一些優點，因此具有提供新穎解決問題方法的潛力[4]。一些研究者基于遺傳算法提出了一些模仿生物機理的免疫算法[5]；人工免疫系統的應用問題也得到了研究[6]；還有一些學者研究了控制系統與免疫機制的關系[7]。目前國內外學者們針對抗體群多樣性特性的研究已經提出多種改進的人工免疫算法[8]，然而關于人工免疫算法中抗體的多樣性特性問題仍有待進一步深入研究。隨著人工智能和計算機技術的發展,一些新型的優化算法如：專家系統、Tabu搜索[9]、遺傳算法[10]等都取得了一定的成果。

聚類（clustering）就是按照一定的要求和規律，使數據集中具有相似特性的對象成為一類，從而達到相同類內的對象間的相似性最大，不同類間的對象相似性最小[15]。聚類分析已成為數據挖掘、圖像分割與壓縮、目標特征識別等領域研究的一個重要方面。目前有許多聚類算法，這些算法基本上可以分為兩類：分層和分塊。與層次聚類相比，其將產生集群迭代融合或分裂的連續程度，劃分聚類分配一組數據點為K個簇，沒有任何的層次結構。這個過程通常伴隨著準則函數的優化。K-means均值算法是廣泛使用的分塊算法之一，它是一種迭代的爬山算法。AIS應用包括以下幾個方面：聚類、分類、異常檢測、優化、控制、計算機安全、學習、生物信息學、圖像處理、機器人、病毒檢測和Web挖掘。

在這次研究中，試圖使用克隆選擇算法的隨機優化方法用于聚類的可能性，提出基于克隆選擇原理的非監督克隆選擇聚類算法，該算法是數據驅動的自適應調整其參數，它對數據進行分類的操作盡可能的快。該方法已經測試了幾個人工和現實生活中的數據集，把它的性能與已知K-means算法相比較。實驗結果表明，所提出的算法具有更高的可靠性，在功能上比傳統的分類方法具有較高的分類精度。

1　非監督的克隆選擇聚類算法

1.1基本原理

在非監督克隆選擇聚類算法中，聚類問題被視為優化問題，其目的是找到數據的最優分區，由此產生的聚類往往會盡可能緊密。非監督克隆選擇聚類算法使用的準則是聚類內擴散準則，為了得到良好聚類，這一準則要被最小化。與使用均方誤差準則測量聚類內擴散的K均值算法不同，非監督克隆選擇聚類算法使用各聚類質心的點的歐幾里德距離的總和作為分群量度，并用克隆選擇算法作為聚類算法，這可以確保找到全局最優，而不像K均值算法之類的大部分算法只能得到局部最優。K聚類的數目應該是已知的，并且必須找到恰當的聚類中心m1，m2，…，mk，才能夠使聚類度量J最小化。在數學上，K聚類C={C1，C2，…，CK}的聚類度量J由以下方程表示:

其中，χj∈Rd，j=1，…，N為數據點，Τ={Υij}為由公式（2）表示的分塊矩陣。M是由公式（3）表示的質心矩陣，mi∈Rd，i=1，…，K含Ni數據點的Ci聚類的平均值。

克隆選擇算法的任務是尋找適當的集群中心由此使J最小化。基于聚類準則，如果集群緊湊且呈現超球面形狀，非監督克隆選擇聚類算法給出的結果應該是正確的。

1.2克隆選擇算法

所有的克隆選擇算法具有相同的基本步驟，總結如下：

生成抗體的種群P（候選解）：

當不滿足停止準則時{

根據它們的親和度克隆P

對結果種群進行超變異方案

選擇最高親和度形成新的種群

維持種群的多樣性}

選擇最高親和力抗體形成免疫記憶；

以上是克隆選擇算法的偽代碼流程。

設計和運行一個克隆選擇算法時，必須考慮一些關鍵問題，例如：表現解決方案、保持種群多樣性、親和度度量和超變異機制。以上任一方面的微小變化都可能導致克隆選擇算法執行中產生相當大的改變。

非監督克隆選擇聚類算法偽代碼描述如下：

初始化：隨機生成N抗體的種群P（候選解）:

對每一個代{

種群P中所有抗體親和度測試

克隆P生成一個種群PC

對PC進行超變異方案，生成Pm，合并P&Pm

所有抗體親和度測試

重新選擇n最高親和度來形成種群P

生成新L個體（隨機）

在種群P中，用新個體取代最低L親和度抗體}

最后：選擇P種群中最高親和度抗體。

1.3解決方案

種群P中各抗體形成一串實數代表K聚類中心。D維空間中，數符串的長度是d*K數目，其中聚類中心的坐標逐一定位。

第一批數字d代表第一個聚類中心的d維度；下一批d位置代表第二個聚類中心的d維度，如此類推。

1.4親和度度量

測量一個抗體的親和度，會根據經考慮的抗體中的編碼中心形成聚類，這是通過將χj∈Rd，j=1，…，N每個點分配給聚類Ci的每個集群做到的，該聚類的中心最靠近點。該聚集完成后，新的聚類質心通過找各自聚類的平均點計算得到，然后聚集標準J由公式（1）計算得到。該親和度被定義為：

親和度最大值代表J最小值。如果任何聚類變為空，親和度用零表示。

1.5克隆

種群P的抗體比照其親和度正比被克隆，親和度越高，抗體生成的克隆數量越多。抗體按親和度降序排序，抗體生成的克隆數量由以下方程式表示：

其中，nci是克隆數量，β是克隆因素。

1.6超變異

PC種群中，每個抗體服從于一種與親和度成反比例的突變，這種突變按以下方程完成：

其中，Ab*是Ab變異所產生的抗體，N（0，1）是一個零均值且標準偏差為1的d*K高斯隨機變量的矩陣，aff是抗體的親和度，其被規范在[0，1]區間。α是一個調整高斯變異數值的因素，其與親和度成反比，親和度可控制α的范圍。為達到算法快速、數據驅動的目的，這個因素表示為以下方程式：

其中，最大數據和最小數據是所有維度中的數據特性的最大值和最小值。通過這種方式，突變概率取決于抗體親和度及搜索范圍。

1.7新抗體生成器

為生成新的隨機解，決定了搜索范圍，就是特征空間里的數據分布范圍。數據范圍用每個維度的數據上限和下限計算得到：

其中，rand是一個[0-1]區間含均等概率分布的d*K隨機變量的矩陣。該新隨機解生成器可用于確保非監督克隆選擇聚類算法快速、準確地執行，因為所有的解答都在搜索范圍之內，因而能加快算法的收斂速度。

其中，UL數據，LL數據分別是特征上限和下限的矩陣。新的隨機解依照以下方程式生成：

2　實驗

通過幾組人工數據集和實際數據集對非監督克隆選擇聚類算法進行測試，然后將其與眾所周知的K均值算法進行對比[1]。非監督克隆選擇聚類算法經以下參數進行測試，n=10，β=5，L=4，代的數目gen=30。K均值算法，在不正常終止的情況下，1000被作為最大迭代數。在每個實驗中，算法以不同的隨機初始配置進行100次。為提供執行情況的統計學評估，數據集描述如下：

2.1人工數據集

數據集1:由重疊的兩類（各為100模式）組成的人工數據集，其二元高斯密度用以下參數表示：m1=（0.1，0.1），m2=（0.35，0.1）。該數據集如圖1所示：

圖1　由兩類組成的人工數據集1

數據集2：由9類（各為25模式）組成的人工數據集，其二元高斯密度用以下參數表示：

m1=（0.1，0.1），m2=（0.1，0.5），m3=（0.1，0.9），m4=（0.5，0.1），m5=（0.5，0.5），m6=（0.5，0.9），m7=（0.9，0.1），m8=（0.9，0.5），m9=（0.9，0.9）。

該數據集如圖2所示。

數據集3：由3個類（各為50模式）組成的人工數據集，其二元高斯密度用以下參數表示：

m1=（1，1，1）

m2=（2，2.5，2.5）

m3=（2，3，3）

該數據集如圖3所示。

圖2　由九類組成的人工數據集2

圖3　由三類組成的人工數據集3

2.2世紀數據集

以下實際數據集已經被測試:

（1）玫瑰花數據集有150個四維模式，分為三個類（各50模式）組成，各代表有四個不同類別玫瑰花的特性值。這四個特征值代表花萼長度、萼片寬度、花瓣長度和花瓣寬帶，以厘米計算。這三個類是：數據類1、數據類2和數據類3。

（2）乳腺癌數據集有699個9維模式，分為兩個類組成，一類良性的（458模式）和一類惡性的（241模式）。9個特征是:腫塊厚度、細胞大小的均勻性、細胞形狀的均勻性、邊緣附著力、單上皮細胞大小、裸核、微受激染色質、正常核和有絲分裂。

3　實驗結果及分析

非監督克隆選擇聚類算法最佳分類結果和實驗運行100此后的K均值如表1所示，其中包括所獲的所有數據集分類精度。從表1中我們可以看出：非監督克隆選擇聚類算法比K均值算法更準確。

表1　所有數據集的分類結果

實驗表明，即使是簡單數據，K均值算法在次佳解就卡住了，但非監督克隆選擇聚類算法卻不會如此。表2展示了J的最佳值，及每個數據集中非監督克隆選擇聚類算法和K均值算法的總運行次數的J百分比。從表2我們可以看出，對于所有數據集，非監督克隆選擇聚類算法發現的解答比K均值算法發現的解答更好，并且由非監督克隆選擇聚類算法形成的聚類比由K均值形成的聚類更緊密。結果表明，非監督克隆選擇聚類算法比K均值算法更可靠，因為它始終能發現最佳解，而不像K均值算法并不能每一次都找到最佳解。

表2　不同數據集的J的值

所有實驗中，不到30代，非監督克隆選擇聚類算法就找到了解答。

4　結語

本文提出了基于克隆選擇原理的非監督克隆選擇聚類算法用來找到數據之間的最優分區。它使用聚類內傳播標準作為聚類標準。該標準基于聚類中數據之間的歐幾里德距離。新算法是數據驅動和自適應的，可根據數據調整參數，以實現盡可能快的分類操作。

通過幾組人工數據集和實際數據集對非監督克隆選擇聚類算法進行測試，然后將其與眾所周知的K均值算法進行對比。實驗表明，非監督克隆選擇聚類算法比K均值算法的分類精度更高，后者即使在簡單數據集中，在次佳值就卡住了。新算法在第30代就可以找到解答，而且使用的種群規模小n=10，而其他大多數評估算法需要至少為100的種群規模。如果聚類緊湊且呈超球面形狀，非監督克隆選擇聚類算法可以給出更好結果。

[1]高靜，應吉康.基于人工免疫系統的推薦系統[J].計算機技術與發展，2007，17（5）：180~183

[2]漆安慎，杜嬋英.免疫的非線性模型[M].上海：上海科技教育出版社，1998：7

[3]蔡自興，龔濤.免疫算法研究的進展[J].控制與決策，2004（8）：P842

[4]焦李成，尚榮華，馬文萍，公茂果等.多目標優化免疫算法、理論和應用[M].北京：科學出版社，2010：P43

[5]Jiao Licheng，Wang Lei.Novel Genetic Algorithm Based on Immunity[J].IEEE Trans on Systems，Man and Cybernetics-PartA:Systems and Humans，2000，30（5）:552~561

[6]Ha Daew on，Shin Dongwon，Koh Dwan-Hyeob，et al.Cost Effective Embedded DRAM Integration for High-Density Memory and High Performance Logic Using 0.15Lm Technology node and Beyond[J].IEEE Trans on Election Devices，2000，47（7）:1499~1506

[7]Ding Yong-sheng，Ren Li-hong.Fuzzy Self-Tuning Immune Feedback Controller for Tissue Hypert Hermia[A].IEEE Int.Conf.on Fuzzy Systems[C].San Antonio，2000，1:534~538

[8]顏偉，孫渝江，羅春雷，龍小平，黃尚廉.基于專家經驗的進化規劃方法及其在無功優化中的應用[J].中國電機工程學報，2003，23（7）：76~80

[9]劉玉田，馬莉.基于Tabu搜索方法的電力系統無功優化[J].電力系統自動化，2000，24（2）：61~64

[10]方鴿飛，王惠祥，黃曉爍.改進遺傳算法在無功優化中的應用[J].電力系統及其自動化學報，2003，（4）：15~18

Unsupervised Clonal Selection Clustering Algorithm Based on Immune Algorithm

WEI Ling

（Department of Electrical and Computer Engineering，Lushan College，Guangxi University of Science and Technology，Liuzhou 545006）

Based on the detailed analysis of clonal selection algorithm,proposes unsupervised clone selection clustering algorithm.Which is adaptive data driven by adjusting its parameters,it carries on the classification of data operations as soon as possible,improves the premature convergence problem,improves the speed of data clustering.By using several artificial and real-life data sets,comparing the performance between unsupervised clonal selection clustering algorithm K-means algorithm.The experimental results show that,this algorithm solves the K-means algorithm needs several classes of K determined in advance,and the second best value stuck faults,the classification accuracy,and it is much better than traditional K-means classification algorithm in function and with higher reliability.

Artificial Immune Systems;Clonal Selection Algorithms;Clustering;Multi-Objective Optimization;K-means Algorithm

廣西科技大學鹿山學院科學基金項目（No.2013LSZK05）

1007-1423（2015）11-0021-05

10.3969/j.issn.1007-1423.2015.11.004

韋靈（1979-），男，廣西柳州人，碩士，助教，研究方向為人工智能、數據處理、挖掘和分析

收謝日期：2015-02-052015-03-19