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

基于免疫算法的非監(jiān)督克隆選擇聚類算法研究

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

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

人工免疫系統(tǒng)；克隆選擇算法；聚類；多目標(biāo)優(yōu)化；K-means算法

0　引言

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

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

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

1　非監(jiān)督的克隆選擇聚類算法

1.1基本原理

在非監(jiān)督克隆選擇聚類算法中，聚類問題被視為優(yōu)化問題，其目的是找到數(shù)據(jù)的最優(yōu)分區(qū)，由此產(chǎn)生的聚類往往會盡可能緊密。非監(jiān)督克隆選擇聚類算法使用的準(zhǔn)則是聚類內(nèi)擴(kuò)散準(zhǔn)則，為了得到良好聚類，這一準(zhǔn)則要被最小化。與使用均方誤差準(zhǔn)則測量聚類內(nèi)擴(kuò)散的K均值算法不同，非監(jiān)督克隆選擇聚類算法使用各聚類質(zhì)心的點的歐幾里德距離的總和作為分群量度，并用克隆選擇算法作為聚類算法，這可以確保找到全局最優(yōu)，而不像K均值算法之類的大部分算法只能得到局部最優(yōu)。K聚類的數(shù)目應(yīng)該是已知的，并且必須找到恰當(dāng)?shù)木垲愔行膍1，m2，…，mk，才能夠使聚類度量J最小化。在數(shù)學(xué)上，K聚類C={C1，C2，…，CK}的聚類度量J由以下方程表示:

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

克隆選擇算法的任務(wù)是尋找適當(dāng)?shù)募褐行挠纱耸笿最小化?；诰垲悳?zhǔn)則，如果集群緊湊且呈現(xiàn)超球面形狀，非監(jiān)督克隆選擇聚類算法給出的結(jié)果應(yīng)該是正確的。

1.2克隆選擇算法

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

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

當(dāng)不滿足停止準(zhǔn)則時{

根據(jù)它們的親和度克隆P

對結(jié)果種群進(jìn)行超變異方案

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

維持種群的多樣性}

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

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

設(shè)計和運行一個克隆選擇算法時，必須考慮一些關(guān)鍵問題，例如：表現(xiàn)解決方案、保持種群多樣性、親和度度量和超變異機(jī)制。以上任一方面的微小變化都可能導(dǎo)致克隆選擇算法執(zhí)行中產(chǎn)生相當(dāng)大的改變。

非監(jiān)督克隆選擇聚類算法偽代碼描述如下：

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

對每一個代{

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

克隆P生成一個種群PC

對PC進(jìn)行超變異方案，生成Pm，合并P&Pm

所有抗體親和度測試

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

生成新L個體（隨機(jī)）

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

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

1.3解決方案

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

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

1.4親和度度量

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

親和度最大值代表J最小值。如果任何聚類變?yōu)榭?，親和度用零表示。

1.5克隆

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

其中，nci是克隆數(shù)量，β是克隆因素。

1.6超變異

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

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

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

1.7新抗體生成器

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

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

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

2　實驗

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

2.1人工數(shù)據(jù)集

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

圖1　由兩類組成的人工數(shù)據(jù)集1

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

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）。

該數(shù)據(jù)集如圖2所示。

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

m1=（1，1，1）

m2=（2，2.5，2.5）

m3=（2，3，3）

該數(shù)據(jù)集如圖3所示。

圖2　由九類組成的人工數(shù)據(jù)集2

圖3　由三類組成的人工數(shù)據(jù)集3

2.2世紀(jì)數(shù)據(jù)集

以下實際數(shù)據(jù)集已經(jīng)被測試:

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

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

3　實驗結(jié)果及分析

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

表1　所有數(shù)據(jù)集的分類結(jié)果

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

表2　不同數(shù)據(jù)集的J的值

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

4　結(jié)語

本文提出了基于克隆選擇原理的非監(jiān)督克隆選擇聚類算法用來找到數(shù)據(jù)之間的最優(yōu)分區(qū)。它使用聚類內(nèi)傳播標(biāo)準(zhǔn)作為聚類標(biāo)準(zhǔn)。該標(biāo)準(zhǔn)基于聚類中數(shù)據(jù)之間的歐幾里德距離。新算法是數(shù)據(jù)驅(qū)動和自適應(yīng)的，可根據(jù)數(shù)據(jù)調(diào)整參數(shù)，以實現(xiàn)盡可能快的分類操作。

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

[1]高靜，應(yīng)吉康.基于人工免疫系統(tǒng)的推薦系統(tǒng)[J].計算機(jī)技術(shù)與發(fā)展，2007，17（5）：180~183

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

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

[4]焦李成，尚榮華，馬文萍，公茂果等.多目標(biāo)優(yōu)化免疫算法、理論和應(yīng)用[M].北京：科學(xué)出版社，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īng)驗的進(jìn)化規(guī)劃方法及其在無功優(yōu)化中的應(yīng)用[J].中國電機(jī)工程學(xué)報，2003，23（7）：76~80

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

[10]方鴿飛，王惠祥，黃曉爍.改進(jìn)遺傳算法在無功優(yōu)化中的應(yīng)用[J].電力系統(tǒng)及其自動化學(xué)報，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

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

1007-1423（2015）11-0021-05

10.3969/j.issn.1007-1423.2015.11.004

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

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