基于免疫遺傳算法的模糊C均值聚類算法應(yīng)用研究

李鵬松，石 卓，劉 欣

(東北電力大學(xué)理學(xué)院，吉林吉林132012)

模糊聚類算法［1］是將模糊理論應(yīng)用到硬聚類算法［2］中，為分析數(shù)據(jù)提供了模糊處理能力．模糊聚類算法給出每個(gè)樣本和各個(gè)類之間存在某種隸屬關(guān)系，把樣本對(duì)于各類的隸屬度由非0即1擴(kuò)展到區(qū)間［0，1］，能更有效地對(duì)各類之間有交叉的數(shù)據(jù)集聚類．由于模糊聚類算法能更準(zhǔn)確地描述模式間的不確定關(guān)系，成為近年來(lái)研究的熱點(diǎn)．隨著模糊聚類分析的不斷發(fā)展，模糊聚類技術(shù)已獲得了廣泛的應(yīng)用．在眾多模糊聚類算法中，模糊C均值聚類算法應(yīng)用最廣泛，模糊C均值聚類算法是一種基于劃分的聚類算法，它通過(guò)優(yōu)化目標(biāo)函數(shù)得到每個(gè)樣本點(diǎn)對(duì)所有類中心的隸屬度，從而決定樣本點(diǎn)的類屬以達(dá)到自動(dòng)對(duì)樣本數(shù)據(jù)進(jìn)行分類的目的．它的思想就是使得被劃分到同一類的對(duì)象之間相似度盡可能大，而不同類之間的相似度盡可能?。墨I(xiàn)［3～6］分別將其應(yīng)用在煤礦生產(chǎn)的回采工藝選擇、油氣識(shí)別、圖像智能識(shí)別、非規(guī)則程序劃分中，取得了較好的效果．

簡(jiǎn)單遺傳算法［7］是一種隨機(jī)搜索的全局優(yōu)化算法，以一個(gè)種群中的所有個(gè)體為對(duì)象，利用隨機(jī)化技術(shù)，在一個(gè)被編碼的參數(shù)空間進(jìn)行搜索，尋找最優(yōu)解．免疫遺傳算法將免疫算法和簡(jiǎn)單遺傳算法各自的優(yōu)點(diǎn)結(jié)合起來(lái)，既保留了簡(jiǎn)單遺傳算法的搜索特性，又利用了免疫算法快速收斂于全局最優(yōu)解的特性，在很大程度上避免了“早熟”(過(guò)早陷入局部最優(yōu))現(xiàn)象．文獻(xiàn)［8～11］針對(duì)控制參數(shù)的選取、早熟收斂問(wèn)題，對(duì)免疫遺傳算法進(jìn)行了改進(jìn)．

目前，國(guó)內(nèi)外大量學(xué)者將模糊聚類算法與簡(jiǎn)單遺傳算法相結(jié)合進(jìn)行研究，文獻(xiàn)［12～15］分別針對(duì)傳統(tǒng)數(shù)據(jù)關(guān)聯(lián)算法存在計(jì)算量偏大或關(guān)聯(lián)精度不高的問(wèn)題、逆向工程中的點(diǎn)云數(shù)據(jù)區(qū)域分割問(wèn)題，利用簡(jiǎn)單遺傳算法的全局優(yōu)化特征結(jié)合模糊聚類算法的局部搜索能力提高了算法的精度和效率．將免疫遺傳算法和模糊聚類算法相結(jié)合的已有研究較少，本文提出了一種基于免疫遺傳算法的模糊C均值聚類算法，充分發(fā)揮模糊聚類算法的局部搜索能力強(qiáng)、收斂速度快的特點(diǎn)，同時(shí)利用免疫遺傳算法的全局優(yōu)化特征和自適應(yīng)特性，克服了模糊聚類算法迭代時(shí)容易陷入局部極小的缺陷，極大地提高算法的精度和效率．

本文主要關(guān)注以下2個(gè)問(wèn)題:

(1)提出一種基于免疫遺傳算法的模糊C均值聚類算法，采用免疫遺傳算法對(duì)初始聚類中心進(jìn)行優(yōu)化，然后執(zhí)行模糊C均值聚類算法．

(2)將本文算法應(yīng)用于葡萄酒及鳶尾花數(shù)據(jù)集，得出分析結(jié)果，與基于簡(jiǎn)單遺傳算法的模糊C均值聚類算法的分類結(jié)果進(jìn)行比較，以說(shuō)明本文算法的有效性．

1 基于免疫遺傳算法的模糊C均值聚類算法流程圖

基于免疫遺傳算法的模糊C均值聚類算法的流程圖，如圖1所示．

2 結(jié)果分析及比較

目標(biāo)函數(shù)，即算出每個(gè)個(gè)體模糊聚類的Jb值．Jb值越小，個(gè)體的適應(yīng)度值越高．參數(shù)設(shè)定如表1所示．

表1 參數(shù)設(shè)定表

2．1 葡萄酒數(shù)據(jù)集分類結(jié)果分析及比較

選取葡萄酒數(shù)據(jù)集，數(shù)據(jù)個(gè)數(shù)為178，數(shù)據(jù)維數(shù)為12．將葡萄酒數(shù)據(jù)集聚為3類，在3類樣本數(shù)據(jù)中分別畫(huà)上不同記號(hào)．第1類標(biāo)記為圓圈(o)、第2類標(biāo)記為星號(hào)(*)、第3類標(biāo)記為加號(hào)(+)．

(1)基于簡(jiǎn)單遺傳算法的模糊C均值聚類算法實(shí)現(xiàn)．

算法迭代22次，得到的最優(yōu)目標(biāo)函數(shù)值Jb為1．791 9．每步迭代的目標(biāo)函數(shù)值，如表2所示．最終分類結(jié)果，如圖2所示．

圖1 基于免疫遺傳算法的模糊C均值聚類算法流程圖

表2 基于簡(jiǎn)單遺傳算法的模糊C均值聚類算法迭代22次目標(biāo)函數(shù)值變化表

(2)基于免疫遺傳算法的模糊C均值聚類算法實(shí)現(xiàn)．

算法迭代20次，得到的最優(yōu)目標(biāo)函數(shù)值Jb為1．7904．每步迭代的目標(biāo)函數(shù)值，如表3所示．最終分類結(jié)果，如圖3所示．

表3 基于免疫遺傳算法的模糊C均值聚類算法迭代20次目標(biāo)函數(shù)值變化表

基于免疫遺傳算法的模糊C均值聚類算法的迭代次數(shù)及最優(yōu)目標(biāo)函數(shù)值均較基于簡(jiǎn)單遺傳算法的模糊C均值聚類算法對(duì)應(yīng)的數(shù)值?。聦?shí)上，基于免疫遺傳算法的模糊C均值聚類算法迭代15次的目標(biāo)函數(shù)值已經(jīng)優(yōu)于基于簡(jiǎn)單遺傳算法的模糊C均值聚類算法的最優(yōu)目標(biāo)函數(shù)值．

圖2 基于簡(jiǎn)單遺傳算法的模糊C均值聚類算法對(duì)葡萄酒數(shù)據(jù)庫(kù)聚類結(jié)果展示圖

圖3 基于免疫遺傳算法的模糊C均值聚類算法對(duì)葡萄酒數(shù)據(jù)庫(kù)聚類結(jié)果展示圖

2．2 鳶尾花數(shù)據(jù)集分類結(jié)果分析及比較

選取鳶尾花數(shù)據(jù)集，數(shù)據(jù)個(gè)數(shù)為150，數(shù)據(jù)維數(shù)為5．將鳶尾花數(shù)據(jù)集聚為3類，在3類樣本數(shù)據(jù)中分別畫(huà)上不同記號(hào)．第1類標(biāo)記為圓圈(o)、第2類標(biāo)記為星號(hào)(*)、第3類標(biāo)記為加號(hào)(+)．

(1)基于簡(jiǎn)單遺傳算法的模糊C均值聚類算法實(shí)現(xiàn)．

算法迭代14次，得到的最優(yōu)目標(biāo)函數(shù)值為Jb=0．014 877．每步迭代的目標(biāo)函數(shù)值，如表4所示．最終分類結(jié)果，如圖4所示．

表4 基于簡(jiǎn)單遺傳算法的模糊C均值聚類算法迭代14次目標(biāo)函數(shù)值變化表

(2)基于免疫遺傳算法的模糊C均值聚類算法實(shí)現(xiàn)．

算法迭代12次，得到的最優(yōu)目標(biāo)函數(shù)值為Jb=0．014 845．每步迭代的目標(biāo)函數(shù)值，如表5所示．最終分類結(jié)果，如圖5所示．

基于免疫遺傳算法的模糊C均值聚類算法的迭代次數(shù)及最優(yōu)目標(biāo)函數(shù)值均較基于簡(jiǎn)單遺傳算法的模糊C均值聚類算法對(duì)應(yīng)的數(shù)值?。聦?shí)上，基于免疫遺傳算法的模糊C均值聚類算法迭代10次的目標(biāo)函數(shù)值已經(jīng)優(yōu)于基于簡(jiǎn)單遺傳算法的模糊C均值聚類算法的最優(yōu)目標(biāo)函數(shù)值．

圖4 基于簡(jiǎn)單遺傳算法的模糊C均值聚類算法對(duì)鳶尾花數(shù)據(jù)集聚類結(jié)果

圖5 基于免疫遺傳算法的模糊C均值聚類算法對(duì)鳶尾花數(shù)據(jù)庫(kù)聚類結(jié)果

3 結(jié) 論

將模糊C均值聚類算法和免疫遺傳算法相結(jié)合，能更有效地提高算法的效率，使獲得全局最優(yōu)解的可能性增大，克服了現(xiàn)有算法迭代時(shí)容易陷入局部極小的缺陷．將本文算法應(yīng)用于葡萄酒和鳶尾花數(shù)據(jù)集，說(shuō)明算法的有效性，實(shí)現(xiàn)對(duì)葡萄酒及鳶尾花數(shù)據(jù)集更客觀的分類．

當(dāng)數(shù)據(jù)量較大時(shí)，免疫遺傳算法的優(yōu)越性更加明顯．其主要原因是基于免疫遺傳算法的模糊C均值聚類算法在處理大規(guī)模數(shù)據(jù)時(shí)，更加容易收斂到局部最優(yōu)解．

［1］ 鄧冠男，宋蓮蓮．真域貼近模糊推理算法［J］．東北電力大學(xué)學(xué)報(bào)，2015，35(5):63－70．

［2］ 鄧冠男．聚類分析中的相似度研究［J］．東北電力大學(xué)學(xué)報(bào)，2013，33(1/2):156－161．

［3］ 孫臣良，侯旭江，宛洪順．基于模糊C－聚類分析的回采工藝選擇及MATLAB實(shí)現(xiàn)［J］．世界科技研究與發(fā)展，2012，34(1):58－61．

［4］ 李鐵軍，賀建，凌立蘇，等．油氣識(shí)別的模糊聚類與遺傳神經(jīng)網(wǎng)絡(luò)技術(shù)［J］．大慶石油地質(zhì)與開(kāi)發(fā)，2014，33(2):31－34．

［5］ 胡建平，李玲，謝琪，等．一種新的航拍玻璃絕緣子圖像分割方法［J］．東北電力大學(xué)學(xué)報(bào)，2018，38(2):87－92．

［6］ 李遠(yuǎn)成，陰培培，趙銀亮．基于模糊聚類的推測(cè)多線程劃分算法［J］．計(jì)算機(jī)學(xué)報(bào)，2014，37(3):580－592．

［7］ 汪民樂(lè)．遺傳算法的收斂性研究［J］．計(jì)算技術(shù)與自動(dòng)化，2015，34(1):58－62．

［8］ S．Prakash，D．P．Vidyarthi．A hybrid immune genetic algorithm for scheduling in computational grid［J］．Int．J．of Bio－Inspired Computation，2014，6(6):397－408．

［9］ J．A．M．Rodríguez，F(xiàn)．C．M．Alanís．Binocular self－calibration performed via adaptive genetic algorithm based on laser line imaging［J］．Journal of Modern Optics，2016，63(13):1219－1232．

［10］郭惠勇，李正良．免疫遺傳算法在結(jié)構(gòu)損傷識(shí)別中的應(yīng)用與改進(jìn)［J］．土木建筑與環(huán)境工程，2012，34(2):7－26．

［11］姜萍，王培光，郝靖宇．自抗擾控制器參數(shù)的免疫遺傳優(yōu)化及應(yīng)用［J］．控制工程，2012，19(2):286－289．

［12］ S．Wikaisuksakul．A multi－objective genetic algorithm with fuzzy c－means for automatic data clustering［J］．Applied Soft Computing Journal，2014，24:679－691．

［13］ D．D．Nguyen，L．T．Ngo，J．Watada．A genetic type－2 fuzzy C－means clustering approach to M－FISH segmentation［J］．Journal of Intelligent＆Fuzzy Systems，2014，27(6):3111－3122．

［14］胡傲，馮新喜，王冬旭，等．遺傳模糊聚類算法在數(shù)據(jù)關(guān)聯(lián)中的應(yīng)用［J］．電光與控制，2010，17(3):30－34．

［15］李海倫，黎榮，丁國(guó)富，等．應(yīng)用遺傳模糊聚類實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)區(qū)域分割［J］．計(jì)算機(jī)應(yīng)用研究，2012，29(5):1974－1976．