湯正華

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

1 引 言

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

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

本文在原始蝙蝠算法中引入Levy飛行特征加強(qiáng)算法跳出局部最優(yōu)能力,使用Powell局部搜索加快算法收斂,以此改善蝙蝠算法易陷入局部最優(yōu)和收斂緩慢等問題,并利用改進(jìn)后的蝙蝠算法尋最優(yōu)蝙蝠位置,將此作為模糊C-均值聚類的聚類中心,進(jìn)行模糊聚類,兩個算法交叉迭代多次,以獲得最優(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ù)可能有多個極值點(diǎn),假若初始聚類中心只在一個極值附近,極易陷入局部最優(yōu);另外,傳統(tǒng)模糊C-均值算法需要指定聚類中心數(shù)目,對于龐大無序的數(shù)據(jù)集,很難人為精確地指定聚類中心數(shù)目。針對以上問題,本文將基于數(shù)據(jù)點(diǎn)密度峰值綜合衡量聚類中心外圍數(shù)據(jù)密集程度和聚類中心間距離,自動確定聚類中心和聚類數(shù)目,以此作為改進(jìn)蝙蝠算法的初始中心。

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

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

(4)

(5)

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

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

(6)

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

ECi=δi≥2σ(δi)

(7)

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

LCi=ECi≥μ(ρi)

(8)

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

3 蝙蝠算法及其改進(jìn)

3.1 蝙蝠算法

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

pi=pmin+(pmax-pmin)α

(9)

(10)

(11)

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

Xnew=Xold+δAt

(12)

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

(13)

(14)

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

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

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

(15)

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

3.3 Powell局部搜索

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

步驟1: 將此次迭代搜索到的結(jié)果作為初始點(diǎn)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)方向進(jìn)行一維搜索, 可得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í)數(shù)據(jù)編碼,一個編碼對應(yīng)一個可行解,每個蝙蝠由s個聚類中心構(gòu)成。設(shè)當(dāng)前數(shù)據(jù)需要分為s類,每個數(shù)據(jù)為q維特征,用于實(shí)數(shù)進(jìn)行編碼,以基于密度峰值模糊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-均值算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文改進(jìn)算法的優(yōu)越性,從兩個方面進(jìn)行對比仿真實(shí)驗(yàn):一是選取測試函數(shù)與其它智能優(yōu)化算法對比尋優(yōu)效果;二是選取經(jīng)典數(shù)據(jù)集與其它改進(jìn)的聚類算法對比聚類效果。仿真是在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,本文改進(jìn)算法的基本參數(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次。每種算法運(yùn)行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)象;而本文改進(jìn)的蝙蝠算法,隨著迭代次數(shù)的增加,不管對Sphere、Rosenbrock兩種單峰函數(shù)還是對Rastrigin、Ackley多峰函數(shù),都能在一定的迭代次數(shù)上得到理論最優(yōu)值,且尋優(yōu)精度高。

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

4.2 對比分析聚類效果

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

將本文聚類算法、DEABC-FCM和ACO-FCM分別在3個數(shù)據(jù)集上進(jìn)行聚類分析,其中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ù)集的密度程度,不僅實(shí)現(xiàn)了自動選取聚類中心和聚類數(shù)目,還利用蝙蝠算法的多次優(yōu)化得到了更好的分類效果。為了直觀地對比3種聚類算法的聚類效果,將3種聚類算法分別運(yùn)行100次,統(tǒng)計3種算法實(shí)現(xiàn)聚類的平均迭代次數(shù)、平均使用時間以及平均差錯率,詳細(xì)情況如表4所示。

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

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

4.3 對比分析聚類分割效果

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

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

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

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

(20)

式中:P為真實(shí)標(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é)果

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

4 結(jié) 論

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