馮志豪,曹金鑫,黃嘉爽,鞠恒榮,程 純,丁衛(wèi)平

(南通大學(xué) 信息科學(xué)技術(shù)學(xué)院,江蘇 南通 226019)

1 引 言

現(xiàn)今,醫(yī)療技術(shù)人員使用無(wú)監(jiān)督學(xué)習(xí)技術(shù)對(duì)醫(yī)療數(shù)據(jù)進(jìn)行邏輯組的劃分,以實(shí)現(xiàn)醫(yī)療數(shù)據(jù)處理[1].現(xiàn)實(shí)醫(yī)療數(shù)據(jù)在類(lèi)屬關(guān)系存在模糊性,單純的邊緣聚類(lèi)效果不佳,針對(duì)上述問(wèn)題,L.A.Zadeh基于模糊集理論提出了模糊聚類(lèi)分析方法[2].在眾多模糊聚類(lèi)中,被廣泛使用的算法是模糊C均值聚類(lèi)(FCM).該算法是一種無(wú)監(jiān)督學(xué)習(xí)的軟聚類(lèi)方法,通常運(yùn)用一個(gè)模糊隸屬度函數(shù)值實(shí)現(xiàn)每個(gè)數(shù)據(jù)點(diǎn)與所有聚類(lèi)類(lèi)別關(guān)聯(lián)[3],進(jìn)一步分析數(shù)據(jù)中的描述對(duì)象及其關(guān)系信息,以描述對(duì)象進(jìn)行分組.雖然FCM作為聚類(lèi)分析中的一個(gè)重要研究領(lǐng)域,但該算法對(duì)初始聚類(lèi)中心敏感,魯棒性差,易陷入局部最優(yōu)解.

針對(duì)FCM算法的不足,廣大學(xué)者和專(zhuān)家提出眾多方法,如,Ines Lahmar等人[4]提出一種基于CF自適應(yīng)模糊C均值(SAFCM)聚類(lèi)的集成方法(SAFCM-CES),使用kappa度量值來(lái)定義一個(gè)良好的聚類(lèi),并將Ncut譜聚類(lèi)模型應(yīng)用于相似矩陣以得到標(biāo)注結(jié)果,最終獲得更高的聚類(lèi)質(zhì)量,但是,隨機(jī)初始化聚類(lèi)中心致使FCM算法缺失強(qiáng)自適應(yīng)性;Hatice Arslan等人[5]針對(duì)歐幾里得距離存在的缺點(diǎn),采用Chebsyhev距離函數(shù)來(lái)計(jì)算FCM算法涉及的距離度量,并采用BOA算法對(duì)初始聚類(lèi)中心進(jìn)行優(yōu)化,但在優(yōu)化時(shí)未能考慮BOA算法易早熟的影響;Quang-Thinh Bui等人[6]提出了一種基于形狀的模糊C均值(SFCM)算法,運(yùn)用模糊C均值構(gòu)造算法,使其具有mapper算法的特點(diǎn),不僅可以表現(xiàn)出與傳統(tǒng)算法相同的聚類(lèi)能力,而且突顯數(shù)據(jù)的一些物理關(guān)系,但其中FCM 算法的收斂速度和魯棒性方面仍存在提升的空間;R Venkat等人[7]的研究工作應(yīng)用了增強(qiáng)的FCM進(jìn)行聚類(lèi),涉及了基于萬(wàn)有引力定律和質(zhì)量感知的GSA以松弛限制,獲得更高的聚類(lèi)精度,但是,對(duì)醫(yī)療圖像數(shù)據(jù)中空間位置信息欠缺考慮;R.Vinodha等人[8]提出了一種基于模糊C均值聚類(lèi)(FCM)的調(diào)度器,將權(quán)值分配給局部PI控制器,以實(shí)現(xiàn)對(duì)大范圍工作的非線性過(guò)程的控制,并通過(guò)FCM算法得到的最優(yōu)模糊隸屬度函數(shù)調(diào)度局部控制器參數(shù),以提高了FCM的自適應(yīng)性,但沒(méi)有聚類(lèi)中心的初始化做考慮;雷濤等人[9]提出了一種基于形態(tài)重構(gòu)和隸屬度濾波的改進(jìn)FCM算法(FRFCM),該算法改進(jìn)后,算法速度提高、魯棒性變強(qiáng),對(duì)噪音MR圖像處理效果較好,但對(duì)FCM初始聚類(lèi)中心做出優(yōu)化后,導(dǎo)致簇?cái)?shù)無(wú)法很好的確定.雖然這些改進(jìn)都增強(qiáng)了FCM的聚類(lèi)效果,但大多數(shù)研究仍忽視了去減小初始中心點(diǎn)的影響和算法的自適應(yīng)性.

綜上所述,傳統(tǒng)進(jìn)化算法普遍缺乏自適應(yīng)能力,容易產(chǎn)生局部最優(yōu),導(dǎo)致聚類(lèi)中心優(yōu)化效果較差.為此,一些學(xué)者利用進(jìn)化算法取得了突破.例如Anter等人[10]設(shè)計(jì)了一種混合烏鴉搜索優(yōu)化算法[11],將混沌理論和模糊C-Means算法(CFCSA)結(jié)合起來(lái).提出的CFCSA算法利用全局優(yōu)化方法避免局部極值陷阱.Anter等人[12]也提出了一個(gè)版本的FFCM,其中使用烏鴉搜索優(yōu)化算法(CSA)來(lái)尋找聚類(lèi)過(guò)程中產(chǎn)生更精確結(jié)果的聚類(lèi)的質(zhì)心.ElSoud等人的[13]解決了一個(gè)新的子集特征選擇問(wèn)題,該問(wèn)題由一種新的社會(huì)蜘蛛優(yōu)化算法(SSOA)執(zhí)行,通過(guò)種群中個(gè)體的交互來(lái)尋找復(fù)雜搜索空間的最優(yōu)區(qū)域.Shi Y等人[14]提出了一種新的更新方程和一種改進(jìn)的蟻群優(yōu)化維度選擇策略,以在全局搜索和局部調(diào)整能力之間取得良好的平衡.

考慮到目前研究所需的是一種能夠?qū)さ酶鼉?yōu)聚類(lèi)中心的進(jìn)化算法,本文提出一種基于模糊衍生多種群遺傳進(jìn)化(DMGA)的FCM自適應(yīng)聚類(lèi)算法,根據(jù)生物遺傳進(jìn)化的衍生特性仿生模擬出衍生算子,并使用模糊控制對(duì)遺傳概率進(jìn)行自適應(yīng)調(diào)節(jié),來(lái)提高該遺傳進(jìn)化算法的自適應(yīng)性和全局搜索能力,使其對(duì)FCM的初始聚類(lèi)中心尋優(yōu)更為準(zhǔn)確,從而提高聚類(lèi)效果.

2 FCM聚類(lèi)算法

由James C.Bezdek等人[15]提出的模糊C均值聚類(lèi)(FCM),與K-means算法相比[16],FCM具有模糊程度取衡量所屬關(guān)系,這樣能很好的保留一些數(shù)據(jù)信息.FCM算法的基本思想[17,18]:

給定隸屬于c(2≤c≤n)組的數(shù)據(jù)集X={x1,x2,x3,…,xn},設(shè)定V={v1,v2,…,vc}為數(shù)據(jù)集X的c個(gè)聚類(lèi)中心.uij表示第i個(gè)數(shù)據(jù)點(diǎn)對(duì)第j類(lèi)的隸屬度,取值uij∈[0,1],并且每一個(gè)數(shù)據(jù)點(diǎn)對(duì)所有類(lèi)別的隸屬度之和要為1.隸屬度矩陣U形式化表示如下:

(1)

式中,uij表示數(shù)據(jù)點(diǎn)i屬于第j類(lèi)的程度,當(dāng)uij=0時(shí),表示完全不屬于,當(dāng)uij=1時(shí),表示完全屬于.FCM的目標(biāo)函數(shù)為:

(2)

(3)

(4)

算法通過(guò)公式(3)和公式(4)迭代計(jì)算,聚類(lèi)中心Vi和隸屬度矩陣U會(huì)不斷互相更新,直到求得目標(biāo)函數(shù)最小值,該算法的具體步驟如下[19]:

算法1.FCM

輸入：數(shù)據(jù)集X={x1,x2,x3,…,xn},聚類(lèi)簇個(gè)數(shù)c,模糊加權(quán)參數(shù)m,停止迭代條件δ;

輸出：聚類(lèi)結(jié)果(U,V).

1.先將數(shù)據(jù)集X分為c(2≤c≤n)組,并初始化設(shè)定V={v1,v2,…,vc}是c個(gè)聚類(lèi)中心;

2.使用公式(4)計(jì)算uij(i=1,2,…,c,n=1,2,…,n);

3.使用公式(3)計(jì)算Vi(i=1,2,…,c);

5.輸出聚類(lèi)結(jié)果(U,V).

當(dāng)FCM算法處理數(shù)據(jù)集分布較為均勻且類(lèi)別不明顯時(shí),往往因初始化中心點(diǎn)不同得到難以解釋的聚類(lèi)結(jié)果.對(duì)此,本文在現(xiàn)有進(jìn)化算法[20]中選擇更適合處理多特征數(shù)據(jù)的多種群遺傳算法,對(duì)其進(jìn)行改進(jìn)并提出了衍生多種群遺傳進(jìn)化算法.提出的算法通過(guò)增加衍生算子以提升種群間尋優(yōu)能力,同時(shí)使用模糊控制算子取代經(jīng)驗(yàn)設(shè)置模糊算子的概率參數(shù),以增加算法自適應(yīng)性,進(jìn)而使尋得的聚類(lèi)中心更優(yōu).

3 衍生多種群遺傳算法

3.1 MPGA

多種群遺傳算法(MPGA)是由Potts等人[21]提出,其優(yōu)化了最初的遺傳算法SGA因單個(gè)種群而發(fā)生的過(guò)早收斂問(wèn)題[22].與單種群的SGA比對(duì)而言,MPGA引入了多種群的概念,能在多個(gè)取值范圍內(nèi)進(jìn)行尋優(yōu),其搜索能力有所提升;同時(shí),MPGA算法還增加移民算子和人工選擇算子,使得種群間的能夠協(xié)同進(jìn)化,但是,MPGA的協(xié)同進(jìn)化能力仍存在進(jìn)一步提升的空間[23,24].

MPGA的尋優(yōu)流程圖如圖1所示.

針對(duì)多種群遺傳算法全局尋優(yōu)能力不足和缺少自適應(yīng)性、易出現(xiàn)過(guò)早收斂現(xiàn)象的問(wèn)題[25],本文首次提出衍生多種群遺傳算法(DMGA),DMGA算法先通過(guò)新增的衍生算子去初始化種群,再對(duì)每個(gè)子種群?jiǎn)为?dú)完成選擇、交叉和變異操作,通過(guò)模糊控制動(dòng)態(tài)取值計(jì)算其各概率,從而進(jìn)一步提高多種群遺傳算法的全局尋優(yōu)能力和自適應(yīng)性,尋找出的初始中心點(diǎn)更優(yōu).

圖1 MPGA的尋優(yōu)示意圖Fig.1 Flowchart of the MPGA′s search for excellence

3.2 衍生算子

傳統(tǒng)的多種群遺傳算法通過(guò)多個(gè)種群內(nèi),并發(fā)進(jìn)行選擇、交叉、變異3種算子[26],但種群內(nèi)經(jīng)過(guò)多次迭代進(jìn)化,個(gè)別種群會(huì)失去其多樣性,并且全局搜索能力降低,最終只能得到局部最優(yōu)結(jié)果[27].為了克服上述問(wèn)題,結(jié)合謝承旺等人[28]提出雙鏈結(jié)構(gòu)思想,提出一種基于種群間的衍生算子.該算子是將初始化種群,通過(guò)衍生算子生成另一個(gè)初始時(shí)個(gè)體平均適應(yīng)度更高的種群,然后這兩種群會(huì)同時(shí)進(jìn)行遺傳尋優(yōu).由于基于種群間,該算子突變效果明顯,既能去大面積的搜索全局最優(yōu),又能沖破局部峰值,從而提高算法的全局搜索能力,找出最優(yōu)解.

該衍生算子的變化過(guò)程如圖2所示.圖2(a)展示,當(dāng)種群適應(yīng)度高時(shí),衍生概率被模糊控制為較小值,衍生小部分的個(gè)體,保存多數(shù)優(yōu)秀個(gè)體.圖2(b)展示,當(dāng)適應(yīng)度值低時(shí),算子使用較大的衍生概率,只衍生大部分個(gè)體,多數(shù)個(gè)體發(fā)現(xiàn)演變,以達(dá)到衍生的目的.

圖2 衍生算子結(jié)構(gòu)示意圖Fig.2 Schematic diagram of the structure of the derivative operator

衍生算子步驟:

第1步.在初始化個(gè)體后,對(duì)所有個(gè)體按適應(yīng)度排序分組,每個(gè)種群計(jì)算各自個(gè)體的平均適應(yīng)度f(wàn)ovg,通過(guò)將單個(gè)個(gè)體的適應(yīng)度與種群內(nèi)平均適應(yīng)度比較,從而判斷該個(gè)體是不是保留到衍生種群中.個(gè)體被選中為d=1,反之為d=0.

(5)

第2步.被選中的個(gè)體,按照模糊控制調(diào)節(jié)的衍生概率 進(jìn)行公式(6)的計(jì)算,求得衍生變化后的個(gè)體.

amn=amn+(amax-amn)×pd

(6)

式中,amn為第m個(gè)染色體的第n位,amax為基因上界,pd為變異概率;

由此形成衍生種群,雙種群同時(shí)進(jìn)行后續(xù)操作.

該算子在自身的時(shí)間復(fù)雜度為O(n),但在整個(gè)算法中由于它沒(méi)有加入遞歸算法中,并不會(huì)導(dǎo)致整個(gè)算法的時(shí)間復(fù)雜度增加,算法的時(shí)間復(fù)雜度仍然為O(n2);其對(duì)空間復(fù)雜度的影響,需要申請(qǐng)額外的雙倍物理空間,所有算法的空間復(fù)雜度變?yōu)門(mén)(n).

3.3 模糊控制

為了取代傳統(tǒng)MPGA的概率參數(shù)經(jīng)驗(yàn)設(shè)置方式,本算法使用模糊控制[29]對(duì)遺傳算子的概率進(jìn)行模糊控制,這些概率的取值關(guān)乎優(yōu)秀個(gè)體保留和優(yōu)秀種群的穩(wěn)定,過(guò)大的話會(huì)丟失原有優(yōu)秀個(gè)體,過(guò)小的話又會(huì)搜索能力不足.模糊控制器的結(jié)構(gòu)圖如圖3所示.

圖3 模糊控制器結(jié)構(gòu)圖Fig.3 Structure of adaptive probabilistic fuzzy control operator

4 DMGA-FCM:衍生多種群遺傳進(jìn)化的FCM自適應(yīng)聚類(lèi)算法

為了FCM能夠得到更好的初始聚類(lèi)中心,本文提出的DMGA優(yōu)化算法來(lái)代替隨機(jī)初始化聚類(lèi)中心.

DMGA算法尋優(yōu)過(guò)程如下,流程圖如圖4所示.

Step1.采用二進(jìn)制編碼生成m個(gè)編碼長(zhǎng)度為L(zhǎng)的遺傳個(gè)體,L的計(jì)算方式如公式(7)所示:

L=C×N

(7)

式中,L為遺傳個(gè)體編碼長(zhǎng)度,C為聚類(lèi)中心數(shù),L為特征維數(shù);

設(shè)待編碼數(shù)據(jù)點(diǎn)x∈(-b,b),y表示x的二進(jìn)制,計(jì)算方式如公式(8)所示:

(8)

式中,x為聚類(lèi)中心Vi的任意一位數(shù)的十進(jìn)制形式,y為16位的編碼結(jié)果,v為x的定義域閾值;

Step2.在初始化個(gè)體后,所有個(gè)體按照適應(yīng)度排序并分組到原生子種群Pop中,通過(guò)衍生算子,生成衍生種群Pop′,合并Pop形成遺傳進(jìn)化初始種群;然后通過(guò)建立自適應(yīng)概率模糊控制算子,進(jìn)行動(dòng)態(tài)地調(diào)整pc、pm和pd;每個(gè)種群都通過(guò)交叉算子和變異算子計(jì)算,計(jì)算方式如公式(9)和公式(10)所示:

(9)

式中,ami為第m個(gè)染色體的第i位,ani為第n個(gè)染色體的第i位,pc為交叉概率;amn=amn+(amn-amax)×pm

(10)

式中,amn為第m個(gè)染色體的第n位,amax為基因上界,pm為變異概率;

Step3.各種群間進(jìn)行人工選擇算子,評(píng)判個(gè)體優(yōu)劣性,而后進(jìn)行遷移算子,即將遷出種群中最優(yōu)的個(gè)體替換遷入種群的最差個(gè)體;若算法滿足收斂條件,則停止尋優(yōu),并將最終值解碼得到FCM的初始聚類(lèi)中心,解碼計(jì)算方式如公式(11)所示,否則將按照適應(yīng)度排序的精英種群的個(gè)體依次去替換每個(gè)種群中差的個(gè)體進(jìn)行重新初始化,重新迭代計(jì)算.

圖4 DMGA尋優(yōu)流程圖Fig.4 Flowchart of DMGA optimization search

(11)

式中,x為聚類(lèi)中心Vi任意一個(gè)基因值的十進(jìn)制形式,y為16位的二進(jìn)制編碼結(jié)果,b為x的定義域閾值;

通過(guò)改進(jìn)的DMGA算法尋優(yōu),進(jìn)而確定更優(yōu)聚類(lèi)中心,使得FCM算法提升聚類(lèi)性能,DMGA-FCM算法具體步驟描述如下:

算法2.DMGA-FCM

輸入：數(shù)據(jù)集X={x1,x2,x3,…,xn},聚類(lèi)簇的個(gè)數(shù)c、模糊加權(quán)參數(shù)m、停止迭代條件δ、遺傳種群大小n、種群個(gè)數(shù)P;

輸出：聚類(lèi)結(jié)果(U,V).

1.隨機(jī)數(shù)填充初始參數(shù),交叉概率pc,變異概率pm,衍生概率pd,子種群個(gè)數(shù)K,以及終止.迭代代數(shù)T;

2.用隨機(jī)函數(shù)Rand初始化隸屬度矩陣然后采用公式(8)編碼生成m個(gè)編碼長(zhǎng)度為L(zhǎng)的個(gè)體,得到基因串b={β1,β2,…,βi,…,βL},隨機(jī)生成規(guī)模為n的種群;

3.將所有個(gè)體進(jìn)行聚類(lèi),生成P個(gè)子種群,初始化DMGA種群Pop,再衍生算子衍生孿生種群Pop′;

4.自適應(yīng)概率模糊控制算子調(diào)節(jié)pc、pm和pd3參數(shù),運(yùn)算選擇交叉變異算子每個(gè)子種群都進(jìn)行迭代尋優(yōu):

1)使用適應(yīng)度來(lái)評(píng)價(jià)所有個(gè)體;

2)利用最優(yōu)保留策略的比例完成該子種群父代個(gè)體的選擇,并對(duì)其執(zhí)行交叉操作;

3)根據(jù)pm對(duì)種群內(nèi)個(gè)體進(jìn)行變異操作,得到新一代種群;

4)進(jìn)行遷移操作選擇最優(yōu)的個(gè)體組成精英種群;

5)IF沒(méi)有達(dá)到給定迭代代數(shù),轉(zhuǎn)Step 4,THEN,轉(zhuǎn)Step 5;

5.IF不滿足終止條件,將所有子種群合并,轉(zhuǎn)Step 3,THEN,轉(zhuǎn)Step 6;

6.從每個(gè)子種群中選出最好個(gè)體作為最優(yōu)解,進(jìn)化過(guò)程結(jié)束,輸出最優(yōu)個(gè)體fa并使用公式(11)解碼得FCM的初始聚類(lèi)中心V;

7.得到優(yōu)化后的V={v1,v2,…,vc},為c個(gè)聚類(lèi)中心 ;

8.使用公式(4)計(jì)算uij(i=1,2,…,c,j=1,2,…,n);

9.使用公式(3)計(jì)算Vi(i=1,2,…,c);

11.輸出聚類(lèi)結(jié)果(U,V).

5 仿真實(shí)驗(yàn)及比較分析

5.1 函數(shù)測(cè)試DMGA性能

本文選用如公式(12)～公式(14)所示的3個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行尋優(yōu)測(cè)試來(lái)驗(yàn)證DMGA的性能及其有效性.其中,f1、f2、f33個(gè)函數(shù)都具有相同的搜索域,全局最小值也均為0,其也被學(xué)者常用于測(cè)試進(jìn)化算法的全局搜索能力.

(12)

(13)

f3(x,y)=y×(1+x)+|x+50y×(1-2x)|+
|y+50×(1-2y)|,x,y∈[-10,10]

(14)

函數(shù)測(cè)試主要選擇標(biāo)準(zhǔn)遺傳算法(SGA)、多種群遺傳算法(MPGA)及本文提出的算法(DMGA)對(duì)該函數(shù)進(jìn)行最小值進(jìn)行求解,通過(guò)進(jìn)化代數(shù),以及其最優(yōu)解尋得的耗時(shí)進(jìn)行比較,通過(guò)對(duì)比來(lái)驗(yàn)證各遺傳算法的性能,相應(yīng)參數(shù)設(shè)置如表1所示.

表1為各算法參數(shù)的設(shè)定,SGA為單種群優(yōu)化算法,將種群個(gè)數(shù)設(shè)為1;然后設(shè)定SGA和MPGA的衍生概率、交叉概率和變異概率,運(yùn)用動(dòng)態(tài)模糊控制設(shè)置DMGA算法的衍生概率、交叉概率和變異概率;設(shè)定算法都連續(xù)保留100代優(yōu)越種群的最優(yōu)個(gè)體,終止算法尋得最優(yōu)解.

本文選用迭代次數(shù)和耗時(shí)作為算法的比較指標(biāo).其中,收斂時(shí)迭代次數(shù)表示函數(shù)尋得極值,并且后面迭代中適應(yīng)度不再變化;運(yùn)行耗時(shí)即每次搜索的總用時(shí).以下測(cè)試環(huán)境為64位Windows 10專(zhuān)業(yè)版操作系統(tǒng),Intel Xeon E5-2660 v2處理器.

表1 各遺傳算法參數(shù)設(shè)置Table 1 Parameter settings of each genetic algorithm

測(cè)試結(jié)果如表2和圖5所示.

表2的測(cè)試結(jié)果表明,MPGA和DMGA都能對(duì)碗狀函數(shù)f1表現(xiàn)出良好的尋優(yōu)效果,DMGA平均耗時(shí)大于MPGA,主要因?yàn)镈MGA算法復(fù)雜度高于MPGA;SGA的搜索結(jié)果相比之下表現(xiàn)不佳.多峰函數(shù)f2的最優(yōu)值附近梯度變化相對(duì)f1較為平緩,同時(shí)因局部峰值多,尋優(yōu)難度高,DMGA并沒(méi)有比MGPA看出優(yōu)勢(shì),但和MPGA一樣明顯優(yōu)于SGA,SGA的適應(yīng)度值停止變化在0值以上說(shuō)明沒(méi)有能夠?qū)ふ业饺址逯?這主要?dú)w功于并行多種群計(jì)算尋優(yōu)方式,增加了算法尋優(yōu)效率.對(duì)于山崖?tīng)畹膯畏搴瘮?shù)f3,DMGA的收斂速度快于MPGA和SGA,其耗時(shí)也比SGA和MPGA更短,表明DMGA在

表2 各算法數(shù)測(cè)試結(jié)果表Table 2 Table of test results for each algorithm function

簡(jiǎn)單的單峰函數(shù)中受到其自身復(fù)雜度高的影響較小.

總體上,觀察圖5各種算法尋求最優(yōu)解的過(guò)程,本文提出的衍生多種群遺傳算法(DMGA)在單峰和多峰的復(fù)雜函數(shù)中,引入衍生算子保證尋優(yōu)效果,算子的相關(guān)計(jì)算略有耗時(shí).

此外,簡(jiǎn)單的懸崖?tīng)詈瘮?shù)中,DMGA的函數(shù)梯度巨大,縮小了自身復(fù)雜度高的問(wèn)題.這里實(shí)驗(yàn)的運(yùn)行時(shí)間主要受實(shí)驗(yàn)數(shù)據(jù)的大小、代碼的數(shù)量和算法的迭代次數(shù)的影響.在這里可以發(fā)現(xiàn),DMGA對(duì)個(gè)體自適應(yīng)值的計(jì)算也比其他算法大得多,并且所有的運(yùn)行時(shí)間都普遍增加.總體來(lái)說(shuō),DMGA在收斂速度和準(zhǔn)確度呈現(xiàn)優(yōu)秀的水平,可在復(fù)雜函數(shù)中更準(zhǔn)確的定位全局峰值,也可在簡(jiǎn)單函數(shù)中提高效率.

5.2 UCI醫(yī)學(xué)數(shù)據(jù)集聚類(lèi)測(cè)試

在驗(yàn)證DMGA-FCM對(duì)醫(yī)學(xué)數(shù)據(jù)集的聚類(lèi)效果實(shí)驗(yàn)中,本文選擇7個(gè)UCI數(shù)據(jù)集分別的對(duì)FCM[30]、MPGA-FCM[31]、PSO-FCM[32]和DMGA-FCM進(jìn)行了測(cè)試,以便更加全面的評(píng)價(jià)算法的性能.數(shù)據(jù)集來(lái)自UCI數(shù)據(jù)集(https://archive.ics.uci.edu/ml/index.php),其特征如表3所示.

為了有效評(píng)估實(shí)驗(yàn)結(jié)果,本文選用3個(gè)廣泛使用的評(píng)估方法對(duì)不同算法在7個(gè)數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)價(jià).評(píng)估方法如下:

1)準(zhǔn)確度(ACC)

(15)

式中,π是n個(gè)樣本的排列,Xt和X分別為聚類(lèi)準(zhǔn)確的樣本和所有測(cè)試樣本,如果點(diǎn)j屬于簇i,則它們的第i個(gè)條目等于1,否則為0.

2)標(biāo)準(zhǔn)化互信息(NMI)

NMI通常用于測(cè)量?jī)煞N聚類(lèi)結(jié)果在聚類(lèi)中的相似度.假設(shè)C為真實(shí)的聚類(lèi)集,而C*為計(jì)算出來(lái)的聚類(lèi)集.它們的互信息MI(C,C*)的定義如下:

(16)

式中,p(ci)和p(cj)是從數(shù)據(jù)集中任意選擇的數(shù)據(jù)點(diǎn),它們分別屬于群集ci和cj.p(ci,cj)是任意選擇的聯(lián)合概率,數(shù)據(jù)點(diǎn)同時(shí)屬于群集ci和cj.標(biāo)準(zhǔn)化互信息(NMI)的定義如下:

(17)

式中,H(C)和H(C*)分別是C和C*的熵.NMI越大,聚類(lèi)性能就越好.

3)調(diào)整蘭德系數(shù)(ARI)

ARI用于衡量?jī)蓚€(gè)數(shù)據(jù)分布之間的一致性.ARI的定義如下:

(18)

式中,a11表示將相同類(lèi)型的樣本分配給同一個(gè)集合,a00表示將不同類(lèi)型的樣本分配給不同的集合,a10表示將相同類(lèi)型的樣本分配給不同的集合,a01表示將不同類(lèi)型的樣本分配給同一個(gè)集合[33].

本文通過(guò)對(duì)每個(gè)數(shù)據(jù)集進(jìn)行50次實(shí)驗(yàn)后,計(jì)算并記錄每個(gè)數(shù)據(jù)集ACC、NMI和ARI的平均值.聚類(lèi)測(cè)試結(jié)果如表4所示.

表4 各方法在不同數(shù)據(jù)集中的ACC、NMI和ARI Table 4 ACC,NMI and ARI of each method in different data sets

通過(guò)上述測(cè)試實(shí)驗(yàn)的聚類(lèi)評(píng)價(jià)指標(biāo)柱狀圖可以發(fā)現(xiàn),DMGA-FCM算法在各數(shù)據(jù)集上均有著不同程度的性能提升,說(shuō)明以DMGA優(yōu)化的FCM算法的確能提升聚類(lèi)性能.

從表4中各數(shù)據(jù)集的聚類(lèi)準(zhǔn)確度(ACC)可以發(fā)現(xiàn),Cardiotocography、Heart Failure、Cancer-Int、Breast Cancer和 Heart Disease這7個(gè)數(shù)據(jù)集的聚類(lèi)效果較其他3種算法都有提高,由于Cryotherapy和Glass包含數(shù)據(jù)樣本少,不適合DMGA的復(fù)雜計(jì)算,導(dǎo)致聚類(lèi)中心點(diǎn)初始化不佳,從而無(wú)法準(zhǔn)確聚類(lèi).結(jié)合表4中的標(biāo)準(zhǔn)化互信息(NMI)指數(shù)和調(diào)整蘭德系數(shù)(ARI)指數(shù)綜合分析可得:DMGA-FCM的聚類(lèi)效果對(duì)比另外3種FCM算法有很大提升.

因此,實(shí)驗(yàn)結(jié)果分析可得,本文算法在面對(duì)不確定性特征較多的復(fù)雜數(shù)據(jù)時(shí),例如Cardiotocography、Cancer-Int和Breast Cancer數(shù)據(jù)集,這3個(gè)數(shù)據(jù)集的聚類(lèi)準(zhǔn)確度(ACC)提升明顯,可以說(shuō)明本文算法是適合對(duì)復(fù)雜多維數(shù)據(jù)進(jìn)行聚類(lèi)處理的,并不僅限于醫(yī)學(xué)數(shù)據(jù)集.

6 DMGA-FCM在MRI腦圖聚類(lèi)分割中應(yīng)用

當(dāng)醫(yī)學(xué)圖像處理不涉及大量數(shù)據(jù)集的時(shí)候,模糊C均值聚類(lèi)算法(Fuzzy C-Means,FCM)是最先考慮的分割方法,致使眾多學(xué)者對(duì)FCM不斷研究并提出大量關(guān)于FCM的圖像分割算法.但MRI腦圖分割領(lǐng)域仍然存在諸多挑戰(zhàn),例如分割精度和對(duì)圖像噪音的處理.為進(jìn)一步驗(yàn)證DMGA-FCM算法在實(shí)際應(yīng)用上的聚類(lèi)性能,本文將DMGA-FCM 算法在模擬人腦核磁共振圖像中做MRI聚類(lèi)實(shí)驗(yàn).在本節(jié)實(shí)驗(yàn)中,數(shù)據(jù)集選用由McGill大學(xué)Montreal神經(jīng)所公開(kāi)的BrainWeb腦MRI圖像公開(kāi)庫(kù)[34].該圖像庫(kù)仿真了腦MRI圖像的各種組織和結(jié)構(gòu),其包含了患有腦腫瘤的腦MRI數(shù)據(jù),圖像切片厚度為1mm,灰度取值在[0,255]之間.

MRI圖像具有模糊、灰度不均勻性等特點(diǎn),傳統(tǒng)的圖像聚類(lèi)算法在腦腫瘤MRI圖像上聚類(lèi)的效果往往不太理想,如相關(guān)實(shí)驗(yàn)結(jié)果圖6所示.可以發(fā)現(xiàn),傳統(tǒng)的FCM算法對(duì)腦腫瘤和腦組織的分界線判斷很模糊,分割效果不佳;改進(jìn)的PSO-FCM算法和MPGA-FCM算法能一定程度上進(jìn)行弱邊緣識(shí)別,但對(duì)于周?chē)写竺娣e破損腦組織的腦腫瘤邊界,依舊很難分割出來(lái);而DMGA-FCM算法能有效分辨腦腫瘤虛邊界,分割效果更好,精度要高于上述算法.

根據(jù)上述各算法的MRI圖像聚類(lèi)效果,實(shí)驗(yàn)數(shù)據(jù)分析主要從Jaccard Similarity和Sensitivity指標(biāo)對(duì)算法進(jìn)行評(píng)價(jià):

1)JS(Jaccard Similarity)表示分割的準(zhǔn)確性,計(jì)算公式如下:

(19)

2)Sensitivity表示對(duì)要分割區(qū)域敏感程度,計(jì)算公式如下:

(20)

在上述公式中,S1為需要判斷的分割結(jié)果,S2為準(zhǔn)確分割結(jié)果.

從分割結(jié)果圖像可以看出,DMGA-FCM算法的分割圖像區(qū)域的分割更為準(zhǔn)確,算法的性能更好,可靠性更高.從評(píng)價(jià)指標(biāo)表5可以看出,DMGA-FCM算法相較于對(duì)比算法分割的精度更高,最終平均精度可達(dá):Jaccard Similarity指數(shù)93.20%,Sensitivity指數(shù)89.23%,與傳統(tǒng)FCM相比,聚類(lèi)效果明顯增加,同時(shí),分別比PSO-FCM和MPGA-FCM兩個(gè)改進(jìn)的FCM算法,在Jaccard Similarity提高了2.98%和1.83%,在Sensitivity指數(shù)提高了3.79%和1.86%;DMGA-FCM算法復(fù)雜度較高,在Running time上高于其他對(duì)比算法.綜合來(lái)說(shuō),DMGA-FCM算法在不考慮耗時(shí)的情況下,整體上提高了FCM算法的性能,使得算法聚類(lèi)性能更優(yōu),能更好地分割腦圖像的腫瘤區(qū)域.

圖6 各算法MRI圖像聚類(lèi)效果圖Fig.6 Effect of clustering MRI images by algorithm

表5 不同方法進(jìn)行評(píng)價(jià)指標(biāo)比較Table 5 Different methods for comparing evaluation indicators

7 結(jié)束語(yǔ)

本文針對(duì)FCM聚類(lèi)算法存在的缺陷,提出了DMGA-FCM:衍生多種群遺傳進(jìn)化的FCM自適應(yīng)聚類(lèi)算法.該算法通過(guò)仿生物種衍生特征的衍生算子和結(jié)合模糊控制理念的自適應(yīng)概率模糊控制算子,擴(kuò)大算法的全局搜索范圍,增強(qiáng)算法自適應(yīng)性,從而取得更優(yōu)得初始化聚類(lèi)中心點(diǎn),減小初始化中心點(diǎn)對(duì)聚類(lèi)結(jié)果的影響.通過(guò)仿真結(jié)果表明,DMGA-FCM算法的聚類(lèi)效果相比另外3種算法得到提升,且在MRI腦圖分割的應(yīng)用中取得更準(zhǔn)確的分割精度.

本文提出改進(jìn)的衍生多種群遺傳算法因添加衍生算子和自適應(yīng)概率模糊控制算子,且對(duì)FCM進(jìn)行優(yōu)化,以導(dǎo)致新算法復(fù)雜度較高.因此,在未來(lái)工作中,本文將合理地平衡算子的引入、FCM優(yōu)化設(shè)計(jì)與算法時(shí)間復(fù)雜度之間的關(guān)系以及其他數(shù)據(jù)集的實(shí)驗(yàn)測(cè)試作為后續(xù)研究的關(guān)注點(diǎn).