基于改進蝙蝠優(yōu)化自確定的模糊C-均值聚類算法

湯正華

(中共山東省委黨校 信息技術(shù)部,山東 濟南 250103)

1 引 言

聚類實質(zhì)是一種非監(jiān)督機器學(xué)習(xí)方法,通常作為數(shù)據(jù)挖掘中其他分析算法的預(yù)處理步驟,通過聚類使同一類簇內(nèi)數(shù)據(jù)具有較大的相似度,而不同類簇數(shù)據(jù)具有較小的數(shù)據(jù)相似度,以更好地揭示數(shù)據(jù)的分布情況[1]。不是所有的數(shù)據(jù)對象都能按照硬聚類劃分方法將其進行聚類劃分。Dunn J C[2]提出了模糊C-均值聚類算法(fuzzy C-means, FCM);Bezdek J C[3]將模糊C-均值聚類算法進一步地推廣并實際應(yīng)用到數(shù)據(jù)聚類分析中。

模糊C-均值聚類算法同K-mean聚類算法一樣具有算法簡單、聚類快的特點,但該算法也存在敏感于初始聚類中心、易陷入局部最優(yōu)和算法收斂緩慢等缺點。有鑒于此,國內(nèi)外學(xué)者進行了大量的研究和改進。文獻[4]利用密度峰值改進模糊C-均值聚類,使用密度峰值函數(shù)找出數(shù)據(jù)集中密度較大或距離較大的數(shù)據(jù)點作為初始聚類中心,既解決了算法敏感于初始中心,又確定了聚類數(shù)目;文獻[5]利用改進的自適應(yīng)遺傳算法優(yōu)化改進模糊C-均值聚類,有效避免了傳統(tǒng)模糊C-均值聚類易陷入局部最優(yōu);文獻[6]利用改進的人工蜂群算法對核C-均值聚類算法進行優(yōu)化,取得了魯棒性強和聚類精度高的聚類結(jié)果;文獻[7]通過引入差分進化算法中變異和交叉思想對人工蜂群進行改進,利用改進的人工蜂群優(yōu)化模糊C-均值聚類。群智能優(yōu)化算法因其實現(xiàn)簡單、擴展性強、優(yōu)化效果突出等優(yōu)點得到了廣泛的應(yīng)用和推廣。蝙蝠算法吸取了粒子群和模擬退火算法的優(yōu)點,具有算法簡單、可操作性強等優(yōu)點[8]。

本文在原始蝙蝠算法中引入Levy飛行特征加強算法跳出局部最優(yōu)能力,使用Powell局部搜索加快算法收斂,以此改善蝙蝠算法易陷入局部最優(yōu)和收斂緩慢等問題,并利用改進后的蝙蝠算法尋最優(yōu)蝙蝠位置,將此作為模糊C-均值聚類的聚類中心,進行模糊聚類,兩個算法交叉迭代多次,以獲得最優(yōu)的聚類結(jié)果。

2 模糊C-均值算法

2.1 傳統(tǒng)模糊C-均值算法

設(shè)數(shù)據(jù)集X={xi∈Rd,i=1,2,…,n},xi為d維向量即每個數(shù)據(jù)元素含有d個屬性,需要將數(shù)據(jù)集X劃分為c類(2≤c≤n),聚類中心為E={e1,e2,…,ec},模糊C-均值算法目標(biāo)函數(shù)定義如下:

(1)

步驟1:初始化參數(shù),設(shè)定模糊加權(quán)系數(shù)m,聚類數(shù)目c和聚類數(shù)據(jù)集合E;

步驟2:計算隸屬度矩陣U,

(2)

步驟3:更新聚類中心數(shù)據(jù)集E:

(3)

步驟4:若新聚類中心與前聚類中心距離小于給定的容許誤差ε時,算法迭代終止;否則轉(zhuǎn)向步驟2。

模糊C-均值算法利用梯度下降法求得最優(yōu)值,每一次迭代都是趨于目標(biāo)函數(shù)極小值方向,但目標(biāo)函數(shù)可能有多個極值點,假若初始聚類中心只在一個極值附近,極易陷入局部最優(yōu);另外,傳統(tǒng)模糊C-均值算法需要指定聚類中心數(shù)目,對于龐大無序的數(shù)據(jù)集,很難人為精確地指定聚類中心數(shù)目。針對以上問題,本文將基于數(shù)據(jù)點密度峰值綜合衡量聚類中心外圍數(shù)據(jù)密集程度和聚類中心間距離,自動確定聚類中心和聚類數(shù)目,以此作為改進蝙蝠算法的初始中心。

2.2 基于密度峰值確定聚類中心

Alex等提出了一種新的密度聚類算法(clustering by fast search and find of density peaks,CFSFDP)[9],該算法通過計算數(shù)據(jù)點密度,將具有局部密度較大的中心點作為聚類中心,實現(xiàn)大數(shù)據(jù)對聚類中心自動選取。但算法采用決策圖對預(yù)期的高局部密度和高密度距離進行手動選擇,當(dāng)單個集群存在多個密度峰值時,難以獲得聚類數(shù)。有鑒于此,本文通過計算數(shù)據(jù)點密度峰值綜合衡量聚類中心外圍數(shù)據(jù)密集程度和聚類中心間距離,以自動獲取較為準(zhǔn)確的聚類中心和聚類數(shù)目。原始CFSFDP算法中,數(shù)據(jù)點i的局部密度ρi為:

(4)

(5)

式中:dij表示數(shù)據(jù)點i、j間的距離;dcut為截斷距離,其值為經(jīng)驗值,一般取距離矩陣dij排序后1%～2%的值。δi表示局部密度大于點i的局部密度的點中與點i距離的最小值:

δi=minj:ρj>ρi(dij)

(6)

原始CFSFDP算法會構(gòu)造以局部密度ρi為橫軸,以δi為縱軸的決策圖。根據(jù)決策圖人工選擇局部密度ρi和高密度距離δi的數(shù)據(jù)點,將明顯遠離絕大部分樣本的右上角區(qū)域的密度峰值點作為一個聚類中心。這種采用手動確定聚類中心的方式存在人為的主觀性,本文利用數(shù)據(jù)集的密度程度,客觀自動地選取聚類中心和聚類數(shù)目。為了全方位體現(xiàn)數(shù)據(jù)集密集程度,對各數(shù)據(jù)點計算如下:

ECi=δi≥2σ(δi)

(7)

式中:σ(δi)表示所有高密度距離的標(biāo)準(zhǔn)差; ECi表示數(shù)據(jù)集i期望的聚類中心。根據(jù)CFSFDP算法的思想,聚類中心之間應(yīng)該具有較大的距離,因此聚類中其他數(shù)據(jù)點的高密度距離應(yīng)該不大于2σ(δi);但現(xiàn)實中也會存在具有較大的δi值而低局部密度的噪音聚類中心,這種噪音聚類中心一旦被選中極易干擾其它正常聚類中心定位選取,為此需要將此類噪音聚類中心予以剔除:

LCi=ECi≥μ(ρi)

(8)

式中:μ(ρi)表示ρi均值;LCi表示數(shù)據(jù)集i去噪后的聚類中心。通過利用式(8)的比較,剩余的聚類都比相鄰的數(shù)據(jù)點具有更高的局部密度和密度距離。

3 蝙蝠算法及其改進

3.1 蝙蝠算法

蝙蝠算法(bat algorithm,BA)通過模仿蝙蝠聲吶探物,不斷調(diào)整頻率、脈沖等因素在解空間中搜索最優(yōu)值。算法對蝙蝠位置和速度按照式(9)～式(11)進行迭代:

pi=pmin+(pmax-pmin)α

(9)

(10)

(11)

脈沖頻率pi的取值是隨機的,最大最小值分別為pmax、pmin,在進行局部搜索時,每只蝙蝠位置更新為:

Xnew=Xold+δAt

(12)

式中:δ為[-1,1]上的隨機數(shù);At為所有蝙蝠在t次迭代上的平均響度。隨著迭代的增加,蝙蝠的脈沖發(fā)射頻率和響度也會更新:

(13)

(14)

在求解無約束優(yōu)化問題上,蝙蝠算法優(yōu)于遺傳算法和粒子群優(yōu)化算法[10],但也存在易陷入局部最優(yōu)、收斂過慢等問題。為此,本文引入Levy飛行特征,以加強算法跳出局部最優(yōu)的能力;在得到最優(yōu)蝙蝠值后對其進行Powell局部搜索,加快算法收斂。

3.2 Levy飛行特征局部尋優(yōu)

Levy飛行過程具有隨機游走和隨機發(fā)現(xiàn)的特性,能夠節(jié)約活動成本和縮短活動距離,是一種有效提高活動效率的方式;其保持局部搜索能力的同時,可有效避免了陷入局部最優(yōu)的風(fēng)險。在智能算法中采用Levy飛行策略可以擴大算法的搜索范圍,種群的多樣性得到提高。本文將Levy飛行特性引入蝙蝠算法中,利用Levy飛行特性擴展搜索空間,對蝙蝠的位置進行改進:

(15)

式中:“·”表示點乘積;Levy(ξ)是隨機搜索路徑,步長的大小通過Levy分布隨機數(shù)產(chǎn)生且1≤ξ≤3。改進后蝙蝠算法的搜索脈沖頻率依舊決定蝙蝠移動的速度,與原算法的搜索行為一致,而引進Levy分布后擴展了蝙蝠的搜索空間,能夠避免陷入局部最優(yōu)。

3.3 Powell局部搜索

Powell算法又稱鮑威爾共軛方向法或方向加速算法,是直接利用函數(shù)值構(gòu)造共軛搜索方向的一種搜索算法。該方法不需要對目標(biāo)函數(shù)進行求導(dǎo),當(dāng)目標(biāo)函數(shù)的導(dǎo)數(shù)不連續(xù)時也能應(yīng)用,對于n維正定二次函數(shù),共軛搜索方向具有n次收斂的特性。本文利用密度峰值綜合數(shù)據(jù)集節(jié)點外圍數(shù)據(jù)密集程度,自動獲取較為準(zhǔn)確的聚類中心和聚類數(shù)目,提升初始蝙蝠種群的均勻度。鮑威爾共軛方向法步驟為:

步驟1: 將此次迭代搜索到的結(jié)果作為初始點c(0),設(shè)搜索精度為ε′,給定n個初始無關(guān)搜索方向d(i)(i=0,1,2,…,n-1),一般取n個坐標(biāo)軸方向,j=0。

步驟2: 令c(0)=c(j), 從c(0)開始依次沿d(i)(i=0,1,2,…,n-1)方向進行一維搜索, 可得c(i)(i=1,2,…,n):

f(c(i)+ωid(i))=minf(c(i)+ωd(i))

(16)

c(i+1)=c(i)+ωid(i),i=0,1,2,…,n

(17)

式中:ω、ωi為步長,其中ωi為精確搜索得到的一維最優(yōu)解。

步驟4: 確定搜索方向,按照式(18)計算指標(biāo)m:

(18)

步驟5 :若f(c(0))-2f(c(n))+f(2c(n)-c(0))≥2[f(c(m))-f(c(m+1))]成立,說明d(0),d(1),…,d(n-1)線性無關(guān),搜索方向不變,c(j+1)=c(n),j=j+1,返回步驟2,否則執(zhí)行下一步。

步驟6:說明以上搜索方向線性相關(guān),需調(diào)整方向,令d(m+i)=d(m+i+1)(i=0,1,…,m-n-1),保證新搜索方向線性無關(guān),c(0)=c(j+1),j++,返回步驟2。

3.4 適應(yīng)度函數(shù)及蝙蝠編碼

適應(yīng)度函數(shù)主要用來評價蝙蝠的優(yōu)劣程度,適應(yīng)度函數(shù)把蝙蝠算法與模糊C-均值算法聯(lián)系起來,對于模糊C-均值算法而言,最優(yōu)的結(jié)果就是使目標(biāo)函數(shù)即式(1)的值最小,而對于蝙蝠算法而言,最優(yōu)解就是使適應(yīng)度函數(shù)值最大,設(shè)適應(yīng)度函數(shù):

(19)

蝙蝠算法采用實數(shù)據(jù)編碼,一個編碼對應(yīng)一個可行解,每個蝙蝠由s個聚類中心構(gòu)成。設(shè)當(dāng)前數(shù)據(jù)需要分為s類,每個數(shù)據(jù)為q維特征,用于實數(shù)進行編碼,以基于密度峰值模糊C-均值算法獲得的聚類中心作為尋優(yōu)變量,每個可行解是由k個聚類中心構(gòu)成,由于解的維數(shù)是q維,這里可行解的位置為k×q維向量,可行解的編碼示例結(jié)構(gòu)如表1所示。

表1 蝙蝠算法編碼結(jié)構(gòu)

表1中Zk1,Zk2……Zkq代表第k類的q維聚類中心。

3.5 基于蝙蝠優(yōu)化的模糊C-均值算法

通過上述三個方面的改進,本文提出了一種基于改進蝙蝠優(yōu)化自確定的模糊C-均值聚類算法。算法的整體步驟為:

Step1:初始化蝙蝠種群的速度、脈沖頻率、脈沖響度和脈沖發(fā)射速率等基本參數(shù),模糊系數(shù)m,容許誤差ε。

Step2:求出數(shù)據(jù)集中各數(shù)據(jù)點間的距離dij,取距離矩陣dij排序后2%值為截斷距離dcut。

Step3:利用式(4)和式(6)計算各個數(shù)據(jù)點的ρi和δi。

Step4: 用式(7)和式(8)確定局部聚類中心,然后合并成數(shù)據(jù)集全局聚類中心,并作為后續(xù)蝙蝠算法的初始聚類中心,生成Num個蝙蝠的初始化種群。

Step5: 計算每個蝙蝠的適應(yīng)度值,找出最優(yōu)蝙蝠位置;并根據(jù)式(9)、式(10)、式(15)生成新的蝙蝠位置和速度。

Step6: 產(chǎn)生一個隨機數(shù)R1,if(R1>ri)則對當(dāng)前群體中最優(yōu)蝙蝠位置進行隨機擾動,用擾動得到的位置替換當(dāng)前蝙蝠位置。

Step7:生成隨機數(shù)R2,if(R2

Step8:對蝙蝠群體進行評估,將最優(yōu)蝙蝠位置進行Powell局部搜索。

Step9: 根據(jù)Powell局部搜索結(jié)果移動蝙蝠群體位置,找出當(dāng)前最優(yōu)蝙蝠。

Step10:將最優(yōu)蝙蝠位置作為新的聚類中心,判斷蝙蝠算法是否達到結(jié)束條件,若是,執(zhí)行下一步;否則,Num--,返回Step5。

Step11:將改進蝙蝠算法得到的新聚類中心作為模糊C-均值聚類算法的初始中心進行聚類劃分。

Step12: 判斷聚類算法是否達到結(jié)束條件;若是,執(zhí)行下一步,否則返回Step2。

Step13: 輸出聚類結(jié)果,算法結(jié)束。

4 仿真實驗與結(jié)果分析

為了驗證本文改進算法的優(yōu)越性,從兩個方面進行對比仿真實驗:一是選取測試函數(shù)與其它智能優(yōu)化算法對比尋優(yōu)效果;二是選取經(jīng)典數(shù)據(jù)集與其它改進的聚類算法對比聚類效果。仿真是在windows 7系統(tǒng)下使用MATLAB2014a,CPU:i5-6500@3.2G Hz,RAM:4GB。

4.1 對比分析尋優(yōu)性

將本文算法、粒子優(yōu)化算法(PSO)和蝙蝠算法(BA)在4個標(biāo)準(zhǔn)函數(shù)[11]上求解測試尋優(yōu)效果。BA參數(shù)設(shè)置如下:r0=0.8,A=0.25,κ=0.02,η=0.9,本文改進算法的基本參數(shù)與BA一致,其中飛行尺度參數(shù)ξ=1.5,模糊系數(shù)m=2。PSO參數(shù)設(shè)置為[17]c1=c2=1.496 2,ωmax=0.9,ωmin=0.4,種群規(guī)模為50,最大迭代次數(shù)100次。每種算法運行50次取平均值。

表2 4個標(biāo)準(zhǔn)函數(shù)

圖1為3種智能優(yōu)化算法對表2中4個標(biāo)準(zhǔn)函數(shù)的尋優(yōu)收斂曲線。

由3種智能優(yōu)化算法在4類標(biāo)準(zhǔn)函數(shù)上的尋優(yōu)曲線可以看出:BA和PSO對Sphere、Rosenbrock、Rastrigin 3種標(biāo)準(zhǔn)函數(shù)的尋優(yōu)效果一般;隨著迭代次數(shù)的增加,在多峰函數(shù)Ackley上,PSO收斂速度緩慢,尋優(yōu)精度不精。隨著迭代次數(shù)的增加,BA對Rastrigin、Ackley兩種多峰函數(shù),表現(xiàn)出收斂速度過快且易早熟的現(xiàn)象;而本文改進的蝙蝠算法,隨著迭代次數(shù)的增加,不管對Sphere、Rosenbrock兩種單峰函數(shù)還是對Rastrigin、Ackley多峰函數(shù),都能在一定的迭代次數(shù)上得到理論最優(yōu)值,且尋優(yōu)精度高。

圖1 3種智能優(yōu)化算法尋優(yōu)收斂曲線

4.2 對比分析聚類效果

為驗證本文改進聚類算法的聚類效果,將文獻[7](DEABC-FCM)、文獻[12](ACO-FCM)和本文算法在Aggregation[13]、R15[14]、D31[15]等3類標(biāo)準(zhǔn)數(shù)據(jù)集上進行聚類對比驗證。3個數(shù)據(jù)集的參數(shù)如表3所示。

將本文聚類算法、DEABC-FCM和ACO-FCM分別在3個數(shù)據(jù)集上進行聚類分析,其中DEABC-FCM和ACO-FCM兩種算法聚類數(shù)目需要手動確定,而本文算法的聚類數(shù)目自動生成。聚類結(jié)果如圖2所示。

表3 3個數(shù)據(jù)集參數(shù)

圖2 3種聚類算法的聚類圖譜

由圖2聚類圖譜可以看出,本文算法、DEABC-FCM及ACO-FCM都能將在Aggregation、R15、D31等3類數(shù)據(jù)集上將原始數(shù)據(jù)聚類成型,聚類結(jié)果較為準(zhǔn)確,但DEABC-FCM及ACO-FCM在處理多類別數(shù)據(jù)集時聚類邊界數(shù)據(jù)的歸類處理上不夠精確,比如圖2(c)中D31數(shù)據(jù)集三角標(biāo)記區(qū)域等,而本文算法計算數(shù)據(jù)集的密度程度,不僅實現(xiàn)了自動選取聚類中心和聚類數(shù)目,還利用蝙蝠算法的多次優(yōu)化得到了更好的分類效果。為了直觀地對比3種聚類算法的聚類效果,將3種聚類算法分別運行100次,統(tǒng)計3種算法實現(xiàn)聚類的平均迭代次數(shù)、平均使用時間以及平均差錯率,詳細情況如表4所示。

從表4的統(tǒng)計結(jié)果可以看出:本文聚類算法在3個數(shù)據(jù)集上的平均迭代次數(shù)比其它兩種算法至少減少了12%,平均差錯率比其它兩種算法至少降低了26.8%,說明本文聚類算法能快速收斂,尋優(yōu)聚類精度高;但本文算法耗時沒有較大幅度的縮減,

單次算法運行時間較長,這與本聚類算法計算數(shù)據(jù)集的密度程度和Powell局部搜索有關(guān)。

4.3 對比分析聚類分割效果

分割有效性是評價聚類算法的重要指標(biāo)[16～18],本文選取河流遙感圖像為實驗對象,將本文改進算法與文獻[19](AC-FCM)、文獻[7](DEABC-FCM)、文獻[20](PSO-FCM)和文獻[12](ACO-FCM)進行分割試驗,對比分析各算法的聚類分割效果,同時在選取的河流遙感圖像中人為添加不同等級乘性噪聲模擬斑點噪聲。利用分割準(zhǔn)確率評價各聚類分割算法抗噪能力。對河流遙感圖像分割結(jié)果如圖3所示。

表4 3種聚類算法在數(shù)據(jù)集上的統(tǒng)計結(jié)果

圖3 5種算法對河流遙感圖像的分割結(jié)果

PSO-FCM分割算法和AC-FCM分割算法均能得到大致輪廓,但分割結(jié)果中含有噪點,小尺度結(jié)構(gòu)區(qū)域識別質(zhì)量低;ACO-FCM分割邊緣模糊,紋理不夠清晰;DEABC-FCM分割算法和本文算法都得到了較好的分割效果,邊緣清晰,大尺度區(qū)域分割平滑,但DEABC-FCM分割中出現(xiàn)了噪點。用式(20)計算分割正確率η:

(20)

式中:P為真實標(biāo)準(zhǔn)分割集合;Q為算法分割結(jié)果集合;card(·)表示集合中的元素。在河流圖像中添加的噪聲方差為0.05,0.1,0.15,0.2,0.25,0.3,0.35,0.4,0.45,結(jié)果如圖4所示。

圖4 5種算法對噪聲河流遙感圖像的分割結(jié)果

隨著噪聲的增強,5種算法的準(zhǔn)確率都在下降,ACO-FCM分割算法的效果最差,準(zhǔn)確率降低的幅度最大,說明算法敏感于噪聲;本文算法的效果最好,隨著加入圖像噪聲等級的不斷增大,分割準(zhǔn)確率下降的幅度較小,其次是DEABC-FCM分割算法;PSO-FCM和AC-FCM分割準(zhǔn)確率下降趨勢居中。

4 結(jié) 論

本文提出了一種基于改進蝙蝠優(yōu)化自確定的模糊聚類C-均值算法,算法利用密度峰值綜合衡量聚類中心外圍數(shù)據(jù)密集程度和聚類中心間距離,解決了原始模糊聚類C-均值算法手動設(shè)定聚類數(shù)目的缺陷;在原始蝙蝠算法中引入Levy飛行特征提高蝙蝠算法局部尋優(yōu)能力,利用Powell局部搜索提升蝙蝠算法收斂的速度,并將利用改進后的蝙蝠算法對數(shù)據(jù)集進行尋優(yōu)。仿真結(jié)果表明:本文算法聚類精度高,收斂速度快,聚類分割抗噪能力較強。