一種免疫動態模糊聚類算法

摘要：為了在聚類數不確定的情況下實現聚類分析，通過借鑒生物免疫系統中的克隆選擇原理并結合聚類有效性分析，提出一種免疫模糊動態聚類算法。本算法不但可以根據數據自動確定聚類類目及中心位置，而且克服了傳統聚類算法容易陷入局部極小值，對初始值敏感的缺點。仿真實驗結果表明了本算法的有效性。

關鍵詞：人工免疫； 克隆選擇； 聚類有效性分析； 動態聚類

中圖分類號：TP391文獻標志碼：A

文章編號：1001－3695(2007)08－0053－03

聚類分析是數據挖掘的一個重要分支。所謂聚類，就是將數據對象分組成多個類或簇，在同一個類中的對象之間具有較高的相似度，而不同類中的對象差別較大[1]。聚類分析主要解決兩個問題，即數據集中存在多少聚類簇以及這些簇的位置。如果分析前已知簇的數量就稱為靜態聚類(static clustering)；否則，要在分析過程中獲得簇的數量就稱為動態聚類(dynamic clustering)[2]。在聚類的相關問題中，聚類數c往往是最關鍵的。因為對于一個給定的數據集，尋找一個正確的解空間比起解空間確定后通過聚類分析尋求子結構(或各個類)要重要得多。許多現有聚類算法的最主要缺陷是，不管數據的結構如何，給定一個特定的聚類數c，總將數據集分成c類，而不考慮數據集是否具有可分性，也不管分成的c類是否合理。

根據生物免疫理論中的克隆選擇原理提出的克隆選擇算法(clonal selection algorithm， CLONALG)[3，4]，由于其繼承了生物免疫系統的眾多屬性，并具有自組織、自學習、自識別、自記憶的能力，它不僅能快速提供達到最優解的搜索范圍，而且能得到全局最優的結果。為此，本文將克隆選擇算法應用到聚類分析中，并結合聚類有效性準則提出一種免疫動態模糊聚類算法。本算法不但可以根據數據自動確定聚類類目及中心位置，而且克服了傳統聚類算法容易陷入局部極小值，對初始值敏感的缺點。

1克隆選擇原理及算法

克隆選擇原理最先由Jerne提出，后由Burnet于1959年予以完整闡述；到現在為止，克隆選擇理論已經成為免疫學界普遍接受的基本理論。其大致內容為：當淋巴細胞實現對抗原的識別(即抗體抗原的親和度超過一定閾值)后，B細胞被激活并增殖復制產生B細胞克隆；隨后克隆細胞經歷變異過程，產生對抗原具有特異性的抗體。克隆選擇理論描述了獲得性免疫的基本特性，并且聲明只有成功識別抗原的免疫細胞才得以增殖。經歷變異后的免疫細胞分化為效應細胞(抗體)和記憶細胞兩種。克隆選擇的主要特征是免疫細胞在抗原刺激下產生克隆增殖，隨后通過遺傳變異分化為多樣性效應細胞(如抗體細胞)和記憶細胞。克隆選擇對應著一個親和度成熟(affini￣ty maturation) 的過程，即對抗原親和度較低的個體在克隆選擇機制的作用下，經歷增殖復制和變異操作后，其親和度逐步提高而成熟的過程。

De Castro 和Von Zuben依據克隆選擇理論基本原理，提出了克隆選擇算法。該算法重點強調了當今免疫系統研究已經證實了的一個證據，即通過在生物體內部累積變異和選擇，可以成功實現個體發育的適應性變化。因此他們提出的CLONALG模型沒有采用交叉(重組) 操作，而只用了克隆、變異和部分新個體的補充等操作。克隆選擇算法在數字符號的識別、多目標優化和TSP等問題上均取得了良好的效果[3，4 ]。

2模糊C均值算法

3基于克隆選擇算法的動態免疫聚類算法

基于免疫原理的聚類算法就是將聚類問題轉換為一個在滿足式(1)的約束條件下，使目標函數(抗體—抗原親和度函數)取得最小的優化問題。在基于克隆選擇算法的聚類分析中，把要分類的數據對象視為抗原，把聚類中心看做是免疫系統中的抗體；數據對象的聚類過程就是免疫系統不斷產生抗體、識別抗原，最后產生出可以捕獲抗原的最佳抗體過程。

為了利用克隆選擇算法求解數據集的模糊聚類問題，首先需要解決三個問題：如何將聚類問題的解編碼到抗體中；如何構造抗體—抗原親和度函數來度量每個抗體對聚類問題的響應程度；如何選擇克隆算子，確定操作參數的取值，以確保快速收斂到最優解。

3．1編碼方式

第一種方案的搜索空間為cn。通常情況下，數據集樣本較大，采用這種編碼方案的搜索空間就很大。因此本文采用第二種編碼方式。這種編碼方式物理意義明確、直觀，避免了二進制編碼在運算時需要反復進行譯碼、編碼操作及長度受限等麻煩。

3．2抗體—抗原親和度函數

3．3克隆變異算子

3．4C搜索算子

除了克隆變異算子外，本文還利用FCM的局部尋優能力定義了一個新的算子，即C搜索算子。對于每個記憶細胞，先按式(4)求出其對應模糊劃分矩陣U；然后再按式(5)更新各中心，用更新后的中心構成新的個體。

3．5聚類有效性分析

當選定聚類方式(即如何對特征空間進行劃分的問題)后，還需要確定一個指標來評價聚類的結果(即到底把樣本集劃分成多少類是最佳的問題)。習慣上，把評價聚類結果的問題稱為聚類有效性分析(clustervalidity analysis)[5]，即需要分析聚類結果是不是最好的以及是不是可以信賴的。一般來說，聚類模式的衡量標準是聚類中心的模式盡量緊密，各聚類之間要盡量獨立。

Zadeh于1965年給出了一個聚類有效性量度，即分離度。但是后來發現它對模糊聚類有效性的判斷并不十分有用。1974年，Bezdek提出了劃分系數的概念，才真正構成第一個有用的度量聚類有效性的泛函。但其主要缺點是它的單調趨勢以及與數據集的某些特性缺少直接聯系。以后又提出了劃分熵、比例指數和分離系數等方法，但直到1989 年Xie和Beni提出了XieBeni方法，聚類有效性問題才得到進一步發展。

4仿真實驗

4．1人工數據集上的實驗結果

為了直觀地顯示實驗結果，首先使用兩個在簇中心附近產生的高斯分布的人工數據集進行試驗。數據集1是包含四個簇的二維數據集，且每個簇具有不是方差和數據點，共300個數據點；數據集2是包含八個簇的三維數據集，每個簇包含100個樣本。

設初始抗體數P=20，記憶細胞在抗體集所占比例為10%，每個記憶細胞所產生的臨時抗體數為100，進化的終止條件為記憶細胞中最佳個體的親和度連續50代未得到改善，或達到最大進化代數300。對上述兩個數據集進行10次免疫動態模糊聚類。結果表明，本算法100 %地收斂到正確的聚類數，并獲得最佳聚類中心集的位置。其中一次的實驗結果如圖1所示。

4．2IRIS 數據集上的實驗結果

為了進一步驗證算法的有效性，使用UCI機器學習庫中的IRIS植物樣本數據集。該數據集由分別屬于三種植物的150個樣本組成，每個樣本均為四維模式向量，代表植物的四種特征數據。其中根據其數據特征，第2類和第3類之間區域相互覆蓋。應用與上面相同的參數設定，對IRIS數據集進行10次免疫動態模糊聚類。結果表明，本算法不但可以正確給出其最佳聚類數3，而且平均分類正確率為95.6%，較文獻[7]所給出的標準FCM和遺傳FCM高。表1是其中一次實驗結果中，聚類有效性函數Ic在不同分類數下的對應值。其中式(8)中E1取100。

5結束語

聚類問題在一定條件下可以歸結為一個帶約束的優化問題。基于生物免疫理論提出的克隆選擇算法作為一種魯棒性很強的優化算法不僅能快速提供達到最優解的搜索范圍，而且能得到全局最優的結果。將其應用到聚類分析中，并結合聚類有效性準則提出一種免疫動態模糊聚類算法。仿真實驗表明，本算法不但可以根據數據自動確定聚類類目及中心位置，而且克服了傳統聚類算法容易陷入局部極小值、對初始值敏感的缺點，具有廣闊的應用前景。

參考文獻：

［1］HAN Jiawei， KAMBER M. Data mining:concepts and techniques[M].San Francisco:Morgan Kaufmann，2000:212－227.

[2］FRANTI K. Dynamic local search for clustering with unknown number of clusters [C]//IEEE the 16th International Conference on Pattern Recognition. Quebec， Canada: IEEE， 2002:240－243.

[3］DeCASTRO L N， Von ZUBEN F J. Clonal selection algorithm with engineering applications[C]//Proc of Genetic and Evolutionary Computation Conference. Las Vegas:[s.n.]，2000:36－37.

[4］DeCASTRO L N， Von ZUBEN F J. Learning and optimization using the clonal selection principle [J]. IEEE Trans on Evolutionary Computation， 2002，6(3):239－250.

[5］PAKHIRA M K， BANDYOPADHYAY A， MAULIK U. Validity index for crisp and fuzzy clustering [J]．Pattern Recognition， 2004，37(3):487－501.

[6］MAULIK U， BANDYOPADHYAY S. Performance evaluation of some clustering algorithms and validity indices [J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 2002，24(12):16501654.

[7］時念云，蔣紅芬，徐九韻. 改進遺傳算法在模糊文本聚類中的應用研究[J]. 科學技術與工程， 2005，24 (5):18981902.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”