基于局部集成和克隆選擇的多目標聚類算法

曹萌萌，郭曉磊，劉曉斐

（1.開封大學 信息工程學院，河南 開封475004；2.中國礦業大學 安全工程學院，江蘇 徐州221116）

0 引 言

目前遺傳算法通過優化相應的相似度準則，已經被廣泛用于數據的聚類識別［1，2］。傳統的方法通常只優化某個單一準則，存在對樣本固有數據結構描述不全面的缺點［3］。演化多目標聚類技術可以用來更加全面地評價聚類的效果，在優化過程中容易產生一些無意義的聚類結果，出現極少量樣本為一類的情況，影響了優化方向和最優解的選取。人工免疫算法通常具有良好的全局性能和優化速度［4，5］，在多目標聚類中已經有一些應用［6－8］，但未能充分考慮聚類問題在優化過程中的特殊情況，如在整數型編碼中，每個基因位的整數取值對應一個樣本的類標號，若直接進行克隆和單點變異，由于某一基因位的取值變化只能影響單個樣本，使得克隆個體所代表的數據結構變化不大，產生了一些無意義的聚類結果，又使得聚類劃分的調整過程十分緩慢。為此，提出了一種基于局部集成和克隆選擇的多目標聚類算法 （MCALC），采用兩目標的模糊相似度準則來評價聚類解的優劣，設計了一種局部集成方法用以綜合目標函數取值相近的個體，得到某一類數下代表性的解，并重新設計了免疫克隆選擇中的變異算子，得到了加性變異算子 （解代表的聚類類數增加）、減性變異算子 （解代表的聚類類數減少）和保持變異算子 （僅調整樣本的歸屬情況）。

1 相關概念描述

聚類算法、多目標優化以及免疫克隆選擇算法三者之間的相互關系如圖1所示。

圖1 相關概念的關系

對于一組數據D＝ ｛aij｜i＝1，2，…，n；j＝1，2，…，m｝，n表示樣本數量，m 表示樣本維數，聚類算法依據某一相似度準則Ψ將數據劃分為C 類，使得D＝C1∪C2∪…∪CC且Ci∩Cj為空，i≠j。在聚類算法中用于評價數據劃分質量的目標函數是關于數據樣本取值以及相似度準則的函數，記為F＝ （D，Ψ）。在多目標聚類中，由于高維目標函數的優化難度較大，目標函數通常為兩個，即F1＝（D，Ψ1）和F2＝ （D，Ψ2），其中Ψ1和Ψ2可能相同也可能不同。而基于群體智能的優化算法采用編碼的方式將數據D的劃分描述轉換為一個向量編碼x，進而將多目標聚類問題轉化成一個多目標數值優化問題F1（x）和F2（x）。優化所得的每一個解x即對應數據D的一個聚類劃分結果，其中x屬于數據D映射而得的一個實數域φ（D），具體與x的編碼方式有關。

在多目標優化中，同時獲得F1和F2的最小值是無法實現的，二者之間通常存在一定的矛盾關系，一個函數值的變小會引起來令一個函數值的增大，最終得到的是一個折中解集S，稱為Pareto解集。對于除了S以外的域φ（D）中的任意解x，都存在解x0∈S解使得Fi（x0）≤Fi（x）且至少在一個目標函數上嚴格滿足Fi（x0）＜Fi（x），這一關系稱為Pareto支配。而在Pareto解集S的內部，則任意兩個解x1和x2都無法對對方形成Pareto支配關系，故稱為互不支配，這樣的解則稱為非劣解。

免疫克隆選擇算法則是通過在解域中不斷的搜索以找到最終的Pareto解集。其產生新解的方式為：首先將現有解x 進行克隆，得到多個復制個體Θ1（x），Θ2（x），…，Θp（x），再對每個復制個體獨立的執行變異操作，得到變異個體Θ1（x’），Θ2（x’），…，Θp（x’），最后從所有變異個體和原個體x 中依據Pareto支配關系以及密度評估方法選取最好的個體進入下一代種群中。

2 MCALC的設計

所提算法MCALC 采用整數型編碼，解x1＝ ｛x11，x12，…，x1n｝共有n個基因位，每個基因位的取值為1和C 之間的整數，x1i＝j即表示第i個樣本屬于第j 個類。由于描述樣本的m 維特征中可能存在無關特征，因此各類樣本在m 維空間中的分布往往是不規則的，會影響聚類算法的識別效果。為此，采取兩種方式去除樣本原始分布對聚類的影響。首先對數據進行主成分分析，以特征值累積貢獻率超過85%為標準，將原始m 維樣本映射為q 維樣本（q≤m），得到轉換后的數據D＝ ｛bij｜i＝1，2，…，n；j＝1，2，…，p｝，樣本的相似度準則Ψ即在q維空間上進行。其次，采用模糊的概念設計了兩個目標函數，進一步去除樣本不規則分布和類重疊的影響。

2.1 目標函數設計

算法所設計的第一個目標函數用于評價各類樣本內部的緊密程度，如式 （1）所示

式中：uki——第i個樣本與第k 類的隸屬程度，vk——第k個類的類中心，其計算方法為解x 所表示的屬于第k 類樣本的均值，Ψ（vk，bi）表示vk與bi的相似度準則，此處采用歐式距離準則，numk為屬于第k 類樣本的個數。

第二個目標函數借鑒文獻 ［9］的連接性指標，其思想是相鄰樣本應當盡可能多的被劃分為同一類，若未被劃分到同一類則對該劃分做出相應的懲罰，增大目標函數的取值。本文在此基礎上，有選擇的僅對部分樣本進行考察，并且引入了模糊隸屬度，具體如式 （2）所示

式中：nn（i，j）——將樣本i的近鄰樣本按照距離遠近升序排列后第j 個近鄰樣本的序號，L——總的近鄰數量，E——需要進行連接性指標計算的樣本集合。

集合E 的構建方法如下：依次檢驗每一個類的樣本，對于屬于第k類的所有樣本，計算其到類中心的歐式距離的均值，將大于該均值的樣本加入集合E。該方法的思想是：小于均值的樣本可認為是構成該類的核心成員，它們屬于其它類的可能性不大，通常是其它類樣本的遠鄰 （往往大于L）。若將這些樣本納入計算范圍，不僅意義不大，還會增大計算量，因此在連接性指標的計算中應予忽略。

2.2 局部集成方法的設計

由于智能算法中隨機搜索等因素，使得進化過程中出現一些不合理解，它們會誤導進化的方向，還會影響最終類數的確定，如圖2所示。

圖2 不合理解

圖2中解 “2”是理論上最合理的劃分，其鄰近解 “1”和解 “3”都包含有一個樣本的類，這些解在目標函數值上的變化是細微的。在選取最終劃分時，判別方法對這些解很敏感，容易受到干擾而認為解 “3”或解 “1”是最合理的。但解 “3”表示的類數是大于真實類數的，而解 “1”盡管所得類數正確，但樣本劃分卻是不合理的。

為此，提出在進化過程中采用局部集成的方法對當前的解集進行實時綜合，及時的過濾掉上述不合理的解。局部集成方法的操作流程為：

（1）算法從t0代開始，每隔t1代，將當前解集S中的所有解按照其所表示的類數分別劃入不同的子集中，其中Bi表示類數為i 的解所在的集合，i＝2，3，…，C，類數為1的解自動予以剔除；

（2）對于第i個解集Bi，選擇一個類數小于i且最近的非空解集Bj和一個類數大于i且最近的非空解集Bk，組成用于局部集成的集合B＝ ｛Bj，Bi，Bk｝，利用圖分割算法（本文選擇超圖分割算法HGPA［10］）根據集合B 中的樣本關系分別在指定類數為i－1，i和i＋1時進行圖分割，得到相應類數下的聚類結果，需要指出的是對于邊界上的解集 （即i＝2 和i＝C），則不在類數為1 或C＋1 下進行圖分割；

（3）這樣，類數i下將會得到兩個解y1和y2，計算其目標函數值并依照Pareto［11］支配關系得到支配解，若二者互不支配，則任選一個解，記為y，然后計算當前解集S中類數為i的所有解與y 的相似程度，并用y替換最不相似的一個解；

（4）所有類數下均完成上述操作后，按照Pareto支配關系更新解集S，剔除其中受支配的解。上述集成方法的思想是：鄰域解構成的集合B 能較為正確反映樣本的相互關系，而圖分割算法是完全依據樣本相似關系進行的，所以與解y不相似的個體往往對應不合理的劃分結果。

2.3 變異算子的設計

變異操作是克隆選擇算法產生新解的途徑。對于每一個解，將其克隆p 個，然后對每一個克隆個體進行變異。本文設計了3種變異算子，均依據同等的概率被選中，并用以變異操作。其中加性變異算子的操作方法為：選取解中某一類標號的所有樣本，按照k均值方法將這些樣本聚類為兩類，其中一類賦予原先的標號，另外一類賦予新的類標號。減性變異算子的操作方法為：首先計算各類樣本下的類中心v1，v2，…，vi，任意選取其中兩類樣本進行合并，并計算合并后的類中心vk，然后計算合并后的每一個樣本與類中心vk的距離以及與其它類中心的距離，按照距離最近原則調整樣本的歸屬。而保持變異算子的操作方法為：依據2.1節中目標函數設計的方法得到集合E，對于其中的樣本以設定概率r改變其對應的類標號，對應在表現型基因的操作上，即相應的基因位取值發生改變，由取值i變為j，i∈ ［2，C］，j∈ ［2，C］，j≠i。

2.4 算法流程的設計

MCALC的算法流程為：

（1）生成｜P｜個個體構成種群P，其中要求｜P｜＞C，從類數i＝2～C，每個類數下隨機生成一個個體，其余｜P｜－C＋1個個體則指定任意類數隨機生成，另外設置一個初始為空的集合A 用于存取Pareto支配解，設定當前代數t＝0；

（2）對P中每個個體執行克隆選擇和變異操作，得到由原個體和克隆個體組成的集合P’；

（3）將集合P’與A 合并，并按照Pareto支配關系和擁擠距離概念［12］更新集合A，只保留Pareto支配解，若超出集合A 的最大限定個數時，優先保留擁擠距離大的個體；

（4）若t＝t0或 （t－t0）%t1＝0，則對集合A 執行局部集成操作；

（5）更新種群P，具體為從更新后的集合A中選取｜P｜／2個解放入P中，另外｜P｜／2個個體隨機生成；

（6）若達到最大迭代代數T，則停止并輸出集合A 中的解，否則t＝t＋1，繼續執行步驟 （2）～步驟 （5）。

3 實驗與分析

選擇3 組人工數據集AD＿10＿2、Mixed＿5＿2 和Sym＿3＿2［13］，以及3組UCI數據集Wine、Newthyroid和Vehicle［14］驗證所提算法的有效性，這些數據的詳細信息見表1。

表1 測試數據集的信息描述

此外，選擇了兩種有代表性的算法來進行對比分析，分別為基于進化計算的多目標聚類算法MOCK 和基于模擬退火的多目標聚類算法AMOSA。在參數設置方面，MCALC的設置為：種群P 大小為20，集合A 為100，克隆個數p 為9，近鄰數L 為10，變異概率r為0.3，最大代數T 為200，參數t0和t1分別20和5。為了使對比更為有效，設定MOCK 和AMOSA 的停止條件為最大函數調用次數為1.9×104，與MCALC 的調用次數相近。對每一組數據，每種算法獨立運行30次，計算每次所得Pareto解集中每個解的RI指標，選擇類數正確且RI值最大的解作為該次的最優結果，再統計30次的均值，記為RIB。再利用控制線方法CDL （control data line）來從Pareto解集中自動選取最優解并確定類數，記自動選取最優解的RI均值為RIA，正確確定類數的次數為Cn。RIB和RIA均取值越大，說明結果越好。RIB取值表明了聚類算法所能找到最佳聚類結果的能力，而RIA取值則表明了聚類算法在不依靠類數等先驗信息條件下確定最佳聚類結果的能力。表2 是3種算法所得Pareto解集中最好解的測試結果，表3則是在自動選擇方法CDL下所確定的最好解的測試結果。

表2 3種算法所得最好解的測試結果

從表2和表3的結果可以得出以下結論：①MCALC所能找到的最佳聚類結果優于MOCK；②雖然MCALC 和AMOSA 在所能找到的最佳聚類結果上性能相近，但MCALC 具有更好的自動確定能力。首先，MCALC 在CDL方法下所確定的最佳聚類結果幾乎均好于對比算法（除Sym＿3＿2略差于AMOSA），并且與算法實際所能找到的最佳結果十分接近。其次，MCALC 在30次測試中正確判別類數的次數明顯高于對比算法，其中MCALC 在Sym＿3＿2數據上判別類數的準確率λ（準確次數與總次數的比值）為86.67%，而MOCK 僅為40%，高出46.67%；MCALC 在AD ＿10 ＿2 數據上判別類數的準確率為93.33%，而AMOSA 則為63.33%，最多高出30%。

表3 3種算法自動確定最好解的測試結果

此外，為了說明局部集成方法和變異算子的效力，還進行了相應的測試。在測試中，保持MCALC 的各項設置不變，改變調用局部集成方法的周期t1，其取值分別為1，2，…，10，以數據集Newthyroid為研究對象，結果如圖3所示。

圖3 周期t1 對局部集成方法效能的影響分析

圖3中RIA取值在t1取值偏小時明顯較差，說明頻繁的集成操作影響了正常的群體隨機搜索過程，使算法傾向于圖分割所得的局部極值。而類數判別的準確率λ在t1取值偏大時明顯較差，這是由于集成操作強度不夠而使得算法未能有效去除不合理的解，最終對自動選取過程產生了誤導。本文還以數據集Sym＿3＿2和Vehicle為研究對象，將MCALC中的變異算子替換為單點變異，記為MCALCone，還將變異算子替換為只采用保持變異算子，記為MCALC－r，結果見表4。

表4中結果顯示MCALC 所得RIB的取值更好，表明在整數型編碼下采用常規變異算子所得個體在改觀聚類劃分結果上的能力較差，導致算法尋優緩慢。

表4 變異算子對尋優速度影響的測試結果

4 結束語

設計的多目標聚類算法提出了局部集成的方法并在進化過程中周期性的使用，有效消除了不合理解對尋優結果的影響；還設計了3種新的變異算子，加強了克隆選擇算法的尋優能力和速度。通過多組人工數據和UCI數據的實驗結果驗證了算法的性能，該算法使得聚類結果的RI指標得到提升，顯著提高了類數判別的準確率，使得聚類算法有效避免了對類數需預先指定等先驗知識的需求，增強了算法的實用性。進一步的實驗測試給出了用以控制局部集成強度的參數t1的變化規律，減輕了相應參數的設置難度。

［1］HOU Yong，ZHENG Xuefeng.Enhanced clustering ensemble algorithm based on characteristics of data sets ［J］.Journal of Computer Applications，2013，33 （8）：2204－2207 （in Chinese）.［侯勇，鄭雪峰.基于數據集特點的增強聚類集成算法［J］.計算機應用，2013，33 （8）：2204－2207.］

［2］MENG Ying，LUO Ke，LIU Jianhua，et al.K－medoids clustering algorithm method based on differential evolution ［J］.Application Research of Computers，2012，29 （5）：1651－1653（in Chinese）.［孟穎，羅可，劉建華，等.一種基于差分演化的K－medoids 聚類算法［J］.計算機應用研究，2012，29（5）：1651－1653.］

［3］Hruschka E R，Campello R J G B，Freitas A A，et al.A survey of evolutionary algorithms for clustering ［J］.IEEE Transactions on Systems Man and Cybernetics Part C－Applications and Reviews，2009，39 （2）：133－155.

［4］MO Hongwei，ZUO Xingquan，BI Xiaojun.Advances in artificial immune systems ［J］.CAAI Transactions on Intelligent Systems，2009，4 （1）：21－29 （in Chinese）. ［莫宏偉，左興權，畢曉君.人工免疫系統研究進展 ［J］.智能系統學報，2009，4 （1）：21－29.］

［5］WANG Jianwen，TAO Rui.Application of artificial immune algorithm in wavelength choice for spectra analysis［J］.Com－puter Engineering and Design，2010，31 （10）：2287－2289 （in Chinese）.［王建文，陶瑞.基于人工免疫算法的波長選取在光譜分析中的應用 ［J］.計算機工程與設計，2010，31 （10）：2287－2289.］

［6］TAO Xinmin，FU Dandan，LIU Furong，et al.Multi－scale parallel immune clone optimization clustering algorithm ［J］.Control and Decision，2012，27 （6）：819－826 （in Chinese）.［陶新民，付丹丹，劉福榮，等.基于多尺度并行免疫克隆優化聚類算法 ［J］.控制與決策，2012，27 （6）：819－826.］

［7］QI Yutao，LIU Fang，LIU Jingle，et al.Hybrid immune algorithm with EDA for multi－objective optimization ［J］.Journal of Software，2013，24 （10）：2251－2266 （in Chineses）. ［戚玉濤，劉芳，劉靜樂，等.基于免疫算法和EDA 的混合多目標優化算法 ［J］.軟件學報，2013，24 （10）：2251－2266.］

［8］SHANG Ronghua，JIAO Licheng，WU Jianshe，et al.Immune clonal multi－objective algorithm for unsupervised feature selection ［J］.Journal of Xidian University，2010，37 （1）：18－22 （in Chinese）.［尚榮華，焦李成，吳建設，等.用于非監督特征選擇的免疫克隆多目標優化算法 ［J］.西安電子科技大學學報，2010，37 （1）：18－22.］

［9］ZHAO Xinyuan，WANG Neng.Overlap－based connectivity restoration approach for wireless sensor and actor network ［J］.Journal of Computer Applications，2011，31 （10）：2638－2643（in Chinese）.［趙新元，王能.基于重疊區域的無線傳感反應網絡連接性恢復機制 ［J］.計算機應用，2011，31 （10）：2638－2643.］

［10］Strehl A，Ghosh J.Cluster ensembles：A knowledge reuse framework for combining multiple partitions ［J］.Journal of Machine Learning Research，2008，3 （3）：583－617.

［11］HU Wang，Gary G YEN，ZHANG Xin.Multiobjective particle swarm optimization based on pareto entropy ［J］.Journal of Software，2014，25 （5）：1025－1050 （in Chinese）. ［胡旺，Gary G YEN，張鑫.基于Pareto熵的多目標粒子群優化算法 ［J］.軟件學報，2014，25 （5）：1025－1050.］

［12］YANG Lingen.Adaptive mutation evolutionary algorithm based on dynamic crowding distance ［J］.Computer Applications and Software，2012，29 （1）：280－283 （in Chinese）.［楊林根.基于動態擁擠距離的自適應變異演化算法 ［J］.計算機應用與軟件，2012，29 （1）：280－283.］

［13］Saha S，Bandyopadhyay S.A symmetry based multiobjective clustering technique for automatic evolution of clusters ［J］.Pattern Recognition，2010，43 （3）：738－751.

［14］University of California，Irvine.UCI machine learning repository［EB／OL］.［2013－02－05］.http：／／archive.ics.uci.edu／ml／datasets.html.