文傳軍 詹永照

1(常州工學(xué)院數(shù)理與化工學(xué)院 江蘇 常州 213002) 2(江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院 江蘇 鎮(zhèn)江 212013)

?

Gauss誘導(dǎo)核模糊c均值聚類算法

文傳軍1詹永照2

1(常州工學(xué)院數(shù)理與化工學(xué)院 江蘇 常州 213002)2(江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院 江蘇 鎮(zhèn)江 212013)

針對(duì)核模糊聚類算法優(yōu)異的非線性表達(dá)能力，提出一種Gauss誘導(dǎo)核模糊c均值聚類算法(GIKFCMs)。首先，基于核目標(biāo)函數(shù)和梯度法，得到特征空間聚類中心表達(dá)式，并通過內(nèi)積運(yùn)算得到聚類中心與樣本的核矩陣表達(dá)式。其次，取核目標(biāo)函數(shù)中的核函數(shù)為Gauss核函數(shù)，并利用梯度法得到輸入空間聚類中心表達(dá)式。最后將聚類中心與樣本的核矩陣代入輸入空間聚類中心表達(dá)式中，從而得到GIKFCMs核聚類中心計(jì)算方法，同時(shí)得到相應(yīng)的GIKFCMs核聚類算法。研究GIKFCMs算法的相關(guān)性質(zhì)，分析算法的收斂性和初始化約束。GIKFCMs算法克服了原有核聚類算法在收斂性與初始化約束方面的缺陷。通過仿真實(shí)驗(yàn)驗(yàn)證了該算法的有效性。

核方法 模糊聚類 非線性映射 核聚類中心 算法等價(jià)性證明

0 引 言

自核方法被成功地應(yīng)用于分類器支持向量機(jī)(SVM)[1]以來，即受到機(jī)器學(xué)習(xí)和模式分類領(lǐng)域研究者的廣泛關(guān)注和研究，并進(jìn)一步將其推廣應(yīng)用到特征提取[2]、模糊聚類[3]等領(lǐng)域。

核方法將輸入空間的非線性關(guān)系通過非線性映射轉(zhuǎn)換為高維特征空間的線性關(guān)系，增大了模式間的差異性刻畫。且利用核函數(shù)表示高維特征空間中的內(nèi)積運(yùn)算，無需明確知道具體的非線性映射形式，克服了機(jī)器學(xué)習(xí)的維數(shù)災(zāi)難問題，所以在模糊聚類領(lǐng)域有著廣泛而成功的應(yīng)用。

由于核方法利用核函數(shù)表達(dá)特征空間中的內(nèi)積運(yùn)算，且特征空間中的空間距離可轉(zhuǎn)換為內(nèi)積運(yùn)算形式。所以核方法適合于在特征空間中僅存在內(nèi)積和距離運(yùn)算的算法。聚類中心是模糊聚類算法[4]的重要組成部分，由于核方法中非線性映射的無具體形式給出，因此在模糊聚類算法中應(yīng)用核方法時(shí)，一個(gè)關(guān)鍵性的問題是如何表示核聚類中心。

自文獻(xiàn)[5-6]提出硬核聚類算法以來，將核方法應(yīng)用于聚類算法的各種核模糊聚類算法應(yīng)運(yùn)而生[7-9]。通過對(duì)比研究可以發(fā)現(xiàn)，這些核模糊聚類算法的根本原理都是相同的，即在各種模糊聚類算法中結(jié)合應(yīng)用核方法。這些核模糊聚類算法的聚類目標(biāo)函數(shù)和模糊隸屬度公式在形式上是一致的，不同之處在于核聚類中心的推導(dǎo)原理及表現(xiàn)形式的不同。

本文在上述研究工作的基礎(chǔ)上，以核聚類中心推導(dǎo)原理為分類標(biāo)準(zhǔn)，歸納總結(jié)了現(xiàn)有的三種基本核模糊聚類算法。在此基礎(chǔ)上推導(dǎo)得到一種新的核聚類中心計(jì)算方法，稱所對(duì)應(yīng)的核聚類算法為Guass誘導(dǎo)核模糊c均值聚類算法(GIKFCMs)。GIKFCMs首先基于高斯核函數(shù)和核聚類目標(biāo)函數(shù)，并利用梯度法分別得到特征空間和輸入空間的聚類中心表示式。然后借助核方法和內(nèi)積運(yùn)算得到樣本與特征空間聚類中心的核矩陣。最后通過該核矩陣將特征空間和輸入空間的聚類中心表示式結(jié)合起來，從而得到了GIKFCMs算法的核聚類中心計(jì)算方法。GIKFCMs算法的核聚類中心與一般核模糊聚類目標(biāo)函數(shù)及核模糊隸屬度組成了GIKFCMs核模糊聚類算法。所提出的GIKFCMs算法克服了原有聚類算法在收斂性和初始化方面的缺陷，仿真實(shí)驗(yàn)驗(yàn)證了所提出算法的有效性。

對(duì)于已知的三種核模糊聚類算法，它們的推導(dǎo)原理和算法實(shí)現(xiàn)機(jī)制是不同的，但目前沒有文獻(xiàn)研究對(duì)它們的原理和實(shí)現(xiàn)進(jìn)行歸納比較分析。

1 模糊c均值聚類算法及核模糊c均值聚類算法

模糊c均值聚類算法(FCM)是一種典型的并成功應(yīng)用的模糊聚類算法。眾多模糊或核模糊聚類算法都是在其基礎(chǔ)之上改進(jìn)得到的，基于FCM算法可直觀簡(jiǎn)潔地闡述核模糊聚類算法的原理和性質(zhì)，核模糊c均值聚類算法(KFCM)相應(yīng)結(jié)論可平行推廣到其他核模糊聚類算法。

1.1 模糊c均值聚類(FCM)

設(shè)X={x1,x2,…,xn}為樣本空間Rd中的一個(gè)有限數(shù)據(jù)集，xj為該樣本空間中的一個(gè)樣本向量。 FCM采用模糊劃分的方法，用值在0到1之間的隸屬度確定每個(gè)樣本屬于各組聚簇的程度，并將數(shù)據(jù)集X劃分為c個(gè)模糊聚簇。FCM最優(yōu)化準(zhǔn)則即為最小化目標(biāo)函數(shù)，可表示為：

(1)

(2)

其中V=[vi]c×d為聚類中心矩陣，dij=‖xj-vi‖表示xj與vi在樣本輸入空間中的距離，一般采用歐氏距離(Euclid)表示。U=[uij]c×n表示模糊隸屬度矩陣，uij(0≤uij≤1)表示樣本xj屬于第i組聚簇的隸屬程度；m(m>1)稱為模糊指標(biāo)。通過梯度法得到FCM模糊隸屬度及聚類中心迭代公式，如式(3)、式(4)所示：

(3)

?i=1,…,c?j=1,…,n

(4)

?i=1,…,c

由于FCM算法在輸入空間中采用歐氏距離，所以僅可對(duì)在輸入空間中具有超球體結(jié)構(gòu)的可分?jǐn)?shù)據(jù)集作有效聚類，而對(duì)蘊(yùn)含非線性可分關(guān)系的數(shù)據(jù)集不能作有效聚類[7]。

1.2 核方法(NM)

對(duì)于X={x1,x2,…,xn}，xj∈Rd，函數(shù)K:X×X→R在滿足對(duì)稱正定的條件下稱為Mercer核函數(shù)，任一核函數(shù)總可以表示為：

K(xi,xj)=Φ(xi)·Φ(xj)

(5)

其中Φ為從低維輸入空間X到高維特征空間F的非線性映射，即有：

Φ:X→F

(6)

非線性映射Φ的形式并不需要明確給出，數(shù)據(jù)集X通過Φ映射到空間F，可表示為Φ(X)={Φ(x1),Φ(x2),…,Φ(xn)}，由式(5)知可利用核函數(shù)表示高維特征空間中向量間的歐氏距離。

‖Φ(xi)-Φ(xj)‖2=

(Φ(xi)-Φ(xj))·(Φ(xi)-Φ(xj))=

Φ(xi)·Φ(xi)+Φ(xj)·Φ(xj)-2Φ(xi)·Φ(xj)=

K(xi,xi)+K(xj,xj)-2K(xi,xj)

(7)

利用核函數(shù)表示高維特征空間中向量間距離關(guān)系，即稱之為核方法。核方法適合于在高維特征空間中僅存在點(diǎn)積運(yùn)算和距離關(guān)系的算法。

常用的核函數(shù)包括：

(1) 多項(xiàng)式核函數(shù)：KP(xi,xj)=(xi·xj+b)d，b>0，d∈N。當(dāng)b=0，d=1時(shí)，得到線性核函數(shù)，即有KL(xi,xj)=xi·xj。

(2) Sigmoid核函數(shù)：KS(xi,xj)=tanh(α(xi·xj)+β)，α,β>0。

1.3 核模糊c均值聚類算法(KFCM)

核模糊c均值聚類算法(KFCM)即是將核方法應(yīng)用于模糊c均值聚類算法。模糊聚類算法主要由目標(biāo)函數(shù)、模糊隸屬度和聚類中心三部分構(gòu)成，由式(1)、式(3)可知，目標(biāo)函數(shù)和模糊隸屬度僅含有距離運(yùn)算，滿足應(yīng)用核方法的要求。由式(4)可知，聚類中心并不滿足應(yīng)用核方法的條件，因此不能直接使用核方法處理聚類中心。目前主要有三種不同的聚類中心表現(xiàn)方法，將在第2節(jié)中進(jìn)行介紹，這里主要給出核方法在聚類目標(biāo)函數(shù)和模糊隸屬度中的應(yīng)用。

由式(1)、式(7)可知，KFCM算法目標(biāo)函數(shù)可表達(dá)為：

(8)

其中dKij=‖Φ(xj)-Φ(vi)‖表示特征空間中向量Φ(xj)與聚類中心Φ(vi)的歐氏距離，且可利用核函數(shù)表達(dá)出來。即有：

(9)

由式(3)、式(7)可知，KFCM算法模糊隸屬度可表達(dá)為：

(10)

?i=1,…,c?j=1,…,n

對(duì)比式(1)、式(8)、式(3)和式(10)可知，F(xiàn)CM與KFCM算法的目標(biāo)函數(shù)和模糊隸屬度表達(dá)形式基本一致。

2 核聚類算法分類

核聚類中心的表示是FCM算法與核方法結(jié)合生成KFCM算法的關(guān)鍵，現(xiàn)有研究文獻(xiàn)主要包含了三種不同的核聚類中心表現(xiàn)方法。本文根據(jù)其推理原理的不同分別做了這三種核聚類中心的命名和分類。由于這些核聚類算法的目標(biāo)函數(shù)和模糊隸屬度是相同的，所以以核聚類中心命名相應(yīng)的核模糊聚類算法，并在2.1至2.3節(jié)中進(jìn)行了闡述。

2.1 隱核模糊c均值聚類算法(HKFCMs)

文獻(xiàn)[7]在硬核聚類算法的基礎(chǔ)上提出了一種核模糊聚類算法。在這種核聚類算法中，核聚類中心Φ(vi)利用梯度法以隱式形式表現(xiàn)在核矩陣中，因此將該算法核聚類中心命名為隱核聚類中心，相應(yīng)的核聚類算法為隱核模糊c均值聚類算法(HKFCMs)。

令式(8)對(duì)特征空間聚類中心Φ(vi)求偏導(dǎo)，并令求導(dǎo)結(jié)果等于0，則有：

(11)

由于非線性映射Φ具體形式不可知，所以不能顯式計(jì)算Φ(vi)，將Φ(vi)與Φ(vi)、Φ(xh)分別作內(nèi)積運(yùn)算并利用核函數(shù)表示出來，得到：

(12)

(13)

類似FCM算法參數(shù)迭代估計(jì)流程，利用式(8)、式(10)與式(12)、式(13)及AO交替迭代算法，可對(duì)數(shù)據(jù)集X給出模糊聚類劃分。在式(12)、式(13)中，特征空間聚類中心Φ(vi)并沒有顯式給出，但特征空間聚類中心信息已蘊(yùn)藏在K(vi,vi)及K(xh,vi)中。在最小化目標(biāo)函數(shù)的過程中，HKFCMs算法利用了核聚類目標(biāo)函數(shù)對(duì)Φ(vi)的梯度信息，且該算法由式(8)、式(10)、式(12)及式(13)確定。HKFCMs算法沒有聚類中心的顯示計(jì)算公式，所以在算法迭代時(shí)只能對(duì)模糊隸屬度做初始化，從而由式(10)、式(12)及式(13)生成交替迭代序列。

2.2 Gauss核模糊c均值聚類算法(GKFCMs)

文獻(xiàn)[8]利用Gauss核函數(shù)提出了一種模糊聚類算法，其聚類中心依賴于Gauss核函數(shù)計(jì)算得到，所以稱其為Gauss核聚類中心，稱相應(yīng)的核聚類算法為Gauss核模糊c均值聚類算法(GKFCMs)。

根據(jù)Gauss核函數(shù)的定義，可以得到式(14)：

(14)

其中KG表示高斯核函數(shù)。

對(duì)于KFCM目標(biāo)函數(shù)式(8)，取核函數(shù)為高斯核函數(shù)，由式(8)及式(14)可得到：

(15)

令式(10)中核函數(shù)K取為高斯核函數(shù)KG,可得到：

(16)

令式(15)對(duì)輸入空間聚類中心vi求偏導(dǎo)，并令求導(dǎo)結(jié)果等于0，則有：

(17)

GKFCMs算法由式(15)-式(17)構(gòu)成。GKFCMs算法給出了核聚類算法在輸入空間中原始聚類中心vi的顯式表達(dá)。在最小化目標(biāo)函數(shù)的過程中，GKFCMs算法利用了核聚類目標(biāo)函數(shù)對(duì)vi的梯度信息。由于GKFCMs算法聚類中心式(17)的右端含有聚類中心vi本身，所以該聚類算法不滿足一般聚類算法收斂性證明的基本條件，即要求聚類中心僅為模糊隸屬度的函數(shù)。因?yàn)镚KFCMs算法聚類中心式(17)右端既有vi且有uij，初始化uij無法計(jì)算聚類中心vi，所以在算法迭代時(shí)只能對(duì)聚類中心vi作初始化。

2.3 PSO核模糊c均值聚類算法(PSO-KFCMs)

生物進(jìn)化算法越來越多的被引入到模糊聚類算法中，用于模型的參數(shù)估計(jì)和目標(biāo)函數(shù)求解。此類算法的優(yōu)勢(shì)在于全局優(yōu)解搜索性能和不依賴于梯度信息，適合于非線性、不可微和多峰值復(fù)雜問題的優(yōu)化。由于粒子群(PSO)算法是基于實(shí)數(shù)域編碼并在輸入解空間全局搜索優(yōu)解的，適合于對(duì)模糊聚類算法聚類中心估計(jì)尋優(yōu)。文獻(xiàn)[10-11]利用PSO算法對(duì)聚類中心進(jìn)行編碼尋優(yōu)求解，文獻(xiàn)[9]進(jìn)一步將其與核方法結(jié)合起來，稱這樣的聚類中心為PSO核聚類中心，相應(yīng)的核聚類算法為PSO核模糊c均值聚類算法(PSO-KFCMs)?；綪SO在每次迭代中粒子根據(jù)自身pbest和全局gbest來修正自身飛行速度。

粒子的速度及位置更新公式分別為：

vij(t+1)=wvij(t)+c1r1[pij(t)-xij(t)]+

c2r2[gij(t)-xij(t)]

(18)

xij(t+1)=xij(t)+vij(t+1)

(19)

其中c1、c2為加速因子，取為正的常數(shù)；r1、r2為[0,1]之間的隨機(jī)數(shù)，w稱為慣性因子。

模糊聚類算法一般定義式(20)為PSO適應(yīng)度函數(shù)。

(20)

PSO-KFCMs算法在輸入空間中對(duì)聚類中心vi尋優(yōu)，沒有利用核目標(biāo)函數(shù)對(duì)于Φ(vi)或vi的梯度信息，而僅是在適應(yīng)度函數(shù)的指引下修正迭代尋優(yōu)路徑和速度。PSO-KFCMs算法利用PSO算法對(duì)聚類中心尋優(yōu)，其模糊隸屬度和目標(biāo)函數(shù)由式(8)和式(10)確定。PSO-KFCMs算法沒有聚類中心的計(jì)算公式，其聚類中心取值依賴于PSO算法在解空間中的搜索，所以在算法迭代時(shí)只能對(duì)聚類中心做初始化。

3 Gauss誘導(dǎo)核模糊聚類算法(GIKFCMs)

3.1 Gauss誘導(dǎo)核模糊聚類算法

GKFCMs算法由于其聚類中心公式的右端含有聚類中心本身，所以不滿足聚類算法收斂性條件，且HKFCMs算法和GKFCMs算法在迭代初始化上存在缺陷。在2.1節(jié)隱核聚類中心和2.2節(jié)Gauss核聚類中心的基礎(chǔ)上，推導(dǎo)出了一種新的核聚類中心計(jì)算方法，并稱所得到的聚類中心為Gauss誘導(dǎo)核聚類中心，相應(yīng)的核聚類算法為Gauss誘導(dǎo)核模糊c均值聚類算法(GIKFCMs)。

類似HKFCMs算法，令核目標(biāo)函數(shù)式(8)對(duì)特征空間聚類中心Φ(vi)求偏導(dǎo)，并令求導(dǎo)結(jié)果等于0，則有：

(21)

對(duì)式(21)兩邊乘以Φ(xj)，得到：

(22)

令式(22)中核函數(shù)取為Gauss核函數(shù)，得到：

(23)

類似GKFCMs算法，令核目標(biāo)函數(shù)式(8)中的核函數(shù)為Gauss核函數(shù)，得到：

(24)

令式(24)對(duì)輸入空間聚類中心vi求偏導(dǎo)，并令求導(dǎo)結(jié)果等于0，則有：

(25)

再將式(23)代入式(25)右端，即有：

(26)

根據(jù)GIKFCMs算法聚類中心推導(dǎo)過程可知，該聚類中心既利用了隱核聚類中心對(duì)Φ(vi)的梯度信息，又使用了GKFCMs聚類中心對(duì)vi的梯度信息，且聚類中心vi在輸入空間顯式表示，所以是一種新的核聚類中心確定方法。特別強(qiáng)調(diào)的是，如式(26)所示，GIKFCMs聚類中心vi的顯式表達(dá)式右端并不包含聚類中心vi，這是與GKFCMs算法聚類中心式(17)所截然不同的，從而使得GIKFCMs算法滿足聚類算法收斂性證明的要求。同時(shí)也使得GIKFCMs算法可類似FCM算法，不僅可以對(duì)聚類中心作初始化，而且可以對(duì)模糊隸屬度作初始化。

很顯然，GIKFCMs算法的目標(biāo)函數(shù)和模糊隸屬度與GKFCMs算法相同，所以該算法由式(16)、式(24)和式(26)構(gòu)成。

3.2 Gauss誘導(dǎo)核模糊聚類算法迭代流程

GIKFCMs用下列步驟確定聚類中心vi和隸屬矩陣U=(uij)c×n：

步驟2用式(26)計(jì)算c個(gè)聚類中心vi，i=1,…,c。

步驟3根據(jù)式(24)計(jì)算代價(jià)函數(shù)。如果它小于某個(gè)確定的閾值，或它相對(duì)上次價(jià)值函數(shù)值的改變量小于某個(gè)閾值，則算法停止。

步驟4用式(16)計(jì)算新的U矩陣。返回步驟2。

上述迭代算法也可以先初始化聚類中心，然后再執(zhí)行迭代過程。

為了避免分母為0不可運(yùn)算，若某樣本xj與某聚類中心vi重合，則規(guī)定該樣本歸于該類的隸屬度為1，歸于其他類的隸屬度為0即可。

4 各核模糊聚類算法性質(zhì)分析

4.1 各核聚類算法聚類中心確定方法的性質(zhì)

四種推導(dǎo)原理不同的核聚類中心計(jì)算方法，引出了四種不同的核模糊聚類算法。這些核模糊聚類算法的目標(biāo)函數(shù)和模糊隸屬度表現(xiàn)形式是一致的。

HKFCMs算法將核目標(biāo)函數(shù)JKFCM(U,V)對(duì)特征空間聚類中心Φ(vi)求偏導(dǎo)計(jì)算極值點(diǎn)，得到Φ(vi)的顯式表達(dá)式，但由于非線性變換Φ的映射形式不可知，使得算法不能直接利用Φ(vi)的顯式信息。因此，將Φ(vi)與Φ(vi)及Φ(xj)作點(diǎn)積運(yùn)算，并利用核函數(shù)得到Φ(vi)的隱示表達(dá)式。隱核聚類中心聚類算法利用的是目標(biāo)函數(shù)關(guān)于Φ(vi)對(duì)梯度信息進(jìn)行參數(shù)優(yōu)化估計(jì)，該算法的核函數(shù)具有一般性，能夠選擇任意核函數(shù)。

GKFCMs算法令核函數(shù)為Gauss核函數(shù)，利用Gauss核函數(shù)中蘊(yùn)藏‖x-y‖2的特殊性，將核目標(biāo)函數(shù)對(duì)輸入空間聚類中心vi求導(dǎo)，得到vi的顯示表達(dá)式。因此GKFCMs算法聚類中心方法只能選取Gauss核函數(shù)。在Gauss核聚類中心公式的右端，還包含了聚類中心vi本身，不滿足聚類算法收斂性證明的條件，因此不能仿照FCM算法證明其算法收斂性[4]。

PSO-KFCMs算法聚類中心確定方法與PSO-FCMs聚類中心確定原理和計(jì)算流程相同，即利用PSO生物進(jìn)化算法在輸入空間中依適應(yīng)度函數(shù)值迭代尋優(yōu)聚類中心。該算法和HKFCMs算法一樣，可以選擇任意核函數(shù)。

GIKFCMs算法首先利用Gauss核函數(shù)及隱核聚類中心式(11)，得到式(23)的結(jié)論，然后將其與Gauss核聚類中心表達(dá)式(25)相結(jié)合，得到Gauss核誘導(dǎo)聚類中心式(26)。在Gauss核誘導(dǎo)聚類中心的推導(dǎo)過程中，既利用了隱核聚類中心關(guān)于Φ(vi)對(duì)梯度信息，又結(jié)合了Gauss核聚類中心關(guān)于vi對(duì)梯度信息，且在輸入空間中顯式表達(dá)vi，所以是一種與前述三種方法所不同的核聚類中心計(jì)算方法。很顯然，GIKFCMs算法和GKFCMs算法一樣，也只能選取Gauss核函數(shù)，但GIKFCMs算法聚類中心公式右端不包含聚類中心vi，僅為模糊隸屬度uij的函數(shù)，這與GKFCMs算法聚類中心截然不同，從而滿足了一般模糊聚類算法收斂性證明的要求，進(jìn)而保證了算法的收斂性[4]。

另外HKFCMs算法和PSO-KFCMs算法的目標(biāo)函數(shù)和模糊隸屬度公式是一致的，即采用一般核函數(shù)所定義距離生成的目標(biāo)函數(shù)和模糊隸屬度。而GKFCMs算法與GIKFCMs算法的目標(biāo)函數(shù)及模糊隸屬度公式是相同的，即取核函數(shù)為Gauss核函數(shù)的特殊情況。

4.2 各核聚類算法的收斂性分析

傳統(tǒng)FCM算法是利用梯度算法推導(dǎo)出來的，文獻(xiàn)[4]給出了FCM算法收斂性的嚴(yán)謹(jǐn)證明，F(xiàn)CM算法及其改進(jìn)算法均可以類似得到聚類算法的收斂性。因此可直接根據(jù)文獻(xiàn)[4]所提供方法證明隱核及Gauss核誘導(dǎo)聚類中心聚類算法的收斂性，這兩種核模糊聚類算法所產(chǎn)生的迭代序列將收斂于核目標(biāo)函數(shù)的極小值點(diǎn)或鞍點(diǎn)。對(duì)于PSO核模糊聚類中心聚類算法而言，由于核模糊聚類目標(biāo)函數(shù)轉(zhuǎn)換為PSO算法的適應(yīng)度函數(shù)，所以聚類算法的收斂性由PSO算法的收斂性決定。

對(duì)于GKFCMs算法，并不能夠運(yùn)用文獻(xiàn)[4]的方法判定聚類算法的迭代收斂性，因?yàn)槲墨I(xiàn)[4]收斂性證明方法要求聚類中心僅為模糊隸屬度的函數(shù)。而GKFCMs算法聚類中心公式右端包含聚類中心本身，并不滿足聚類算法迭代收斂條件，其算法收斂性的理論證明需要作進(jìn)一步研究。

4.3 各核聚類算法迭代初始化的要求

GKFCMs算法由式(15)-式(17)確定，其聚類中心式(17)右端含有聚類中心vi，因此不能利用模糊隸屬度的初始化計(jì)算GKFCMs算法聚類中心。所以GKFCMs算法只能先對(duì)聚類中心進(jìn)行初始化，否則無法進(jìn)行算法的迭代計(jì)算。HKFCMs算法由式(12)、式(13)、式(15)和(16)確定，對(duì)于HKFCMs算法而言，由于其在核映射空間中以核矩陣形式隱式表達(dá)聚類中心，沒有顯示的聚類中心表示和計(jì)算公式，所以HKFCMs算法只能對(duì)模糊隸屬度作初始化。而GIKFCMs算法由式(16)、式(24)和式(26)確定，其迭代方式和FCM算法類似，既可以對(duì)聚類中心進(jìn)行初始化，也可以對(duì)模糊隸屬度進(jìn)行初始化，反映了該算法的迭代通用性。對(duì)于PSO-KFCMs算法而言，它在輸入空間中利用PSO算法搜索聚類中心優(yōu)解，不能利用模糊隸屬度求解聚類中心。因此該算法僅能對(duì)聚類中心作初始化并根據(jù)適應(yīng)函數(shù)取值進(jìn)行迭代更新。

5 仿真實(shí)驗(yàn)

為了驗(yàn)證本文所提出的GIKFCMs 算法的有效性，將GIKFCMs算法與在第2節(jié)中所歸納的核聚類算法做對(duì)比測(cè)試。在第2節(jié)中，GIKFCMs算法和HKFCMs 、GKFCMs算法的推導(dǎo)原理相似，都是利用梯度法得到聚類算法參數(shù)計(jì)算公式，并通過AO交替迭代流程進(jìn)行參數(shù)估計(jì)。這三種算法進(jìn)行對(duì)比測(cè)試具有可比性，因此選用HKFCMs 、GKFCMs算法與GIKFCMs算法做對(duì)比測(cè)試。

5.1 公共測(cè)試數(shù)據(jù)集

基于UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的公共數(shù)據(jù)集進(jìn)行算法比對(duì)測(cè)試，所選數(shù)據(jù)集為Iris數(shù)據(jù)集，數(shù)據(jù)集的信息如表1所示。

表1 iris實(shí)驗(yàn)數(shù)據(jù)集

5.2 仿真實(shí)驗(yàn)說明

在測(cè)試時(shí)，三種核聚類算法都選用Gauss核函數(shù)，Gauss核函數(shù)需要對(duì)Gauss核參數(shù)σ賦值，取核參數(shù)σ取值范圍為[21,22,23,24]，聚類算法模糊指標(biāo)m取值為[2,3,4]。在取核函數(shù)為Gauss核函數(shù)的情況下，HKFCMs算法由式(13)、式(15)、式(16)作聚類運(yùn)算，GKFCMs算法由式(15)-式(17)作聚類運(yùn)算，而GIKFCMs算法由式(16)、式(24)、式(26)作聚類運(yùn)算。每種聚類算法根據(jù)參數(shù)和數(shù)據(jù)集進(jìn)行10次測(cè)試，計(jì)算各類聚類平均精度。很顯然這三種核聚類算法的核模糊隸屬度及聚類目標(biāo)函數(shù)是相同的，區(qū)別在于聚類中心的表達(dá)上，其中GKFCMs和GIKFCMs算法在輸入空間中尋找聚類中心，而HKFCMs算法在核映射空間中隱式表現(xiàn)了聚類中心。在算法迭代的初始化方面，如4.3節(jié)分析所述，GKFCMs、GIKFCMs算法選擇對(duì)聚類中心做初始化，HKFCMs算法選擇對(duì)模糊隸屬度做初始化。

5.3 實(shí)驗(yàn)結(jié)果及分析

由于三種核聚類算法中存在參數(shù)σ和m的設(shè)置，且這兩個(gè)參數(shù)的取值對(duì)聚類結(jié)果有著重要的影響，所以依參數(shù)不同取值表現(xiàn)算法聚類結(jié)果，三模型聚類結(jié)果分別如表2-表4所示。

表2 GIKFCMs算法基于Iris數(shù)據(jù)集的分類精度 %

表3 GKFCMs算法基于Iris數(shù)據(jù)集的測(cè)試結(jié)果 %

表4 HKFCMs算法基于Iris數(shù)據(jù)集的分類精度 %

GIKFCMs算法基于數(shù)據(jù)集iris的最高平均分類精度為92.67%，在參數(shù)σ=2，m=4時(shí)取得；最低平均分類精度為89.33%，分別在參數(shù)σ=8，m=2和σ=16，m=2。在聚類平均精度的基礎(chǔ)上，再取聚類平均精度的平均為90.422 5%。

GKFCMs算法基于數(shù)據(jù)集iris的最高平均分類精度為92.53%，在參數(shù)σ=2，m=4時(shí)取得；最低平均分類精度為89.33%，分別在參數(shù)σ=8，m=2和σ=16，m=2。在聚類平均精度的基礎(chǔ)上，再取聚類平均精度的平均為90.39%。

HKFCMs算法基于數(shù)據(jù)集iris的最高平均分類精度為90.00%，在參數(shù)σ=16，m=3時(shí)取得，最低平均分類精度為66.67%，分別在參數(shù)σ=2，m=3和σ=2，m=4。在聚類平均精度的基礎(chǔ)上，再取聚類平均精度的平均為80.51%。

由表2和表3可知，GIKFCMs和GKFCMs算法對(duì)于iris數(shù)據(jù)集都能取得較好的聚類結(jié)果，在不同的參數(shù)取值情況下，GIKFCMs和GKFCMs算法聚類結(jié)果之間各有高低。如當(dāng)σ=2，m=4時(shí)，GIKFCMs平均聚類精度92.67%高于GKFCMs平均聚類精度92.53%；而在σ=4，m=4時(shí)，GIKFCMs平均聚類精度90.80%低于GKFCMs平均聚類精度90.93%。但在最高平均分類精度上和聚類平均精度的平均上，GIKFCMs算法是高于GKFCMs算法的，體現(xiàn)了GIKFCMs算法的有效性。由表4可知，HKFCMs算法基于數(shù)據(jù)集iris的測(cè)試結(jié)果并不理想，體現(xiàn)在該算法對(duì)模糊指標(biāo)m異常敏感，隨著參數(shù)m的變化，HKFCMs算法聚類結(jié)果波動(dòng)較大，且聚類結(jié)果表現(xiàn)不好。

6 線性KFCM與FCM算法等價(jià)性證明的修正

6.1 原等價(jià)性證明存在的問題

文獻(xiàn)[7]提出命題：對(duì)于核模糊c均值聚類算法，若取核函數(shù)為線性核函數(shù)，即KL(xi,xj)=xi·xj時(shí)，KFCM算法等價(jià)于FCM算法。雖然這個(gè)命題并沒有錯(cuò)誤，但文中在證明聚類中心等價(jià)性時(shí)存在錯(cuò)誤，因此其證明過程并不能嚴(yán)謹(jǐn)推導(dǎo)出KFCM算法與FCM算法等價(jià)的結(jié)論。

文獻(xiàn)[7]利用線性核函數(shù)，得到了：

Φ(xj)·Φ(vi)=K(xj,vi)=xj·vi

(27)

文獻(xiàn)[7]由式(27)認(rèn)為特征空間聚類中心Φ(vi)與輸入空間聚類中心vi等價(jià)，由核函數(shù)性質(zhì)可知[12]，核函數(shù)對(duì)應(yīng)特征空間和特征映射Φ并不唯一，所以由式(27)并不能證明Φ(vi)與vi等價(jià)，即不能證明Φ(vi)=vi。

一個(gè)簡(jiǎn)單的反例，設(shè)xj=(xj1,xj2,…,xjd)T，取Φ1(xj)=(xj1,xj2,…,xjd,0)T，Φ2(xj)=(0,xj1,xj2,…xjd)T，Φ3(xj)=(xj1,0,xj2,…,xjd)T，很顯然特征映射Φ1、Φ2及Φ3皆滿足式(27)式約束，但并不能證明Φ1(vi)=Φ2(vi)=Φ3(vi)=vi。

6.2 FCM與線性KFCM算法等價(jià)的證明

由于文獻(xiàn)[7]所提出的核聚類算法是隱核聚類中心聚類算法，特征空間聚類中心Φ(vi)隱式給出，直接證明Φ(vi)與vi的等價(jià)性是非常困難的。因此在證明FCM及KFCM算法等價(jià)性時(shí)應(yīng)回避Φ(vi)與vi等價(jià)性討論。

類似隱核聚類中心展開FCM算法，由式(1)、式(3)、式(4)得到式(28)-式(31)：

(28)

(29)

(30)

(31)

即可用式(27)-式(31)表示FCM算法，在此種表示中聚類中心vi被隱藏起來。當(dāng)KFCM算法取為線性核函數(shù)式(27)時(shí)，KFCM算法表示式(8)、式(10)、式(12)及式(13)轉(zhuǎn)換為FCM算法式(28)-式(31)，從而證明了在線性核函數(shù)條件下，F(xiàn)CM算法與KFCM算法是等價(jià)的。

7 結(jié) 語

核方法具有良好的非線性區(qū)分性能，并在機(jī)器學(xué)習(xí)領(lǐng)域應(yīng)用廣泛。模糊聚類算法[13-14]在運(yùn)用核方法時(shí)，核聚類中心的有效表示是運(yùn)用核方法的關(guān)鍵。所提出的GIKFCMs核模糊聚類算法首先基于Gauss核目標(biāo)函數(shù)和梯度法，分別得到輸入空間和特征空間聚類中心表示式。然后借助核方法和內(nèi)積運(yùn)算得到樣本與特征空間聚類中心的核矩陣。最后應(yīng)用該核矩陣將特征空間和輸入空間的聚類中心表示式結(jié)合起來，從而得到了GIKFCMs算法的核聚類中心計(jì)算方法及相應(yīng)的GIKFCMs算法。GIKFCMs算法和HKFCMs、GKFCMs算法相比，不僅能對(duì)聚類中心初始化，也能對(duì)模糊隸屬度作初始化，且滿足聚類算法收斂性條件，仿真實(shí)驗(yàn)驗(yàn)證了所提出算法的聚類有效性。同時(shí)，對(duì)線性核KFCM算法與FCM算法聚類中心等價(jià)性證明提出反例，并對(duì)線性核KFCM算法與FCM算法等價(jià)性作了重新證明。由于Gauss核參數(shù)對(duì)于聚類算法的影響較大，下一步工作將對(duì)Guass核參數(shù)的恰當(dāng)選取問題進(jìn)行研究。

[1] Cortes C,Vapnik V.Support vector networks[J].Machine Learning,1995,20(3):273-297.

[2] Scholkopf B,Smola A J,Muller K R.Nonlinear component analysis as a kernel eigenvalue problem[J].Neural Computation,1998,10(5):1299-1319.

[3] Filippone M,Camastra F,Masulli F,et al.A Survey of Kernel and Spectral M ethods for Clustering[J].Pattern Recognition,2008,41(1):176-190.

[4] 文傳軍,汪慶淼,詹永照.隱隸屬度模糊C均值聚類算法[J].計(jì)算機(jī)應(yīng)用與軟件,2015,32(12),245-248.

[5] Girolami M.Mercer kernel based clustering in feature space[J].IEEE Trans on Neural Networks,2002,13(3):780-784.

[6] 張莉,周偉達(dá),焦李成.核聚類算法[J].計(jì)算機(jī)學(xué)報(bào),2002,25(6):587-590.

[7] 伍忠東,高新波,謝維信.基于核方法的模糊聚類算法[J].西安電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2004,31(4):533-537.

[8] Zhang D Q,Chen S C.Fuzzy clustering using kernel method[C]//International Conference on Control and Automation,2002.Icca.Final Program and Book of.IEEE,2002:162-163.

[9] 于德亮,唐海燕,丁寶,等.基于粒子群優(yōu)化模糊核聚類的電梯群交通模式識(shí)別[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2012,44(10):84-88.

[10] Niu Q,Huang X J.An improved fuzzy C-means clustering algorithm based on PSO[J].Journal of Software,2011,6(5):873-879.

[11] Kumar S,Singh S K.Hybrid BFO and PSO swarm intelligence spproach for niometric geature optimization[J].International Journal of Swarm Intelligence Research,2016,7(2):36-62.

[12] 王國勝.核函數(shù)的性質(zhì)及其構(gòu)造方法[J].計(jì)算機(jī)科學(xué),2006,33(6):172-178.

[13] Verma H,Agrawal R K,Sharan A.An improved intuitionistic fuzzy c-means clustering algorithm incorporating local information for brain image segmentation[J].Applied Soft Computing,2016,46(C):543-557.

[14] Parastar H,Bazrafshan A.Fuzzy C-means clustering for chromatographic fingerprints analysis:A gas chromatography-mass spectrometry case study[J].Journal of Chromatography A,2016,1438:236-243.

GAUSS-INDUCEDKERNELFUZZYC-MEANSCLUSTERINGALGORITHM

Wen Chuanjun1Zhan Yongzhao2
1(SchoolofMathematicalSciencesandChemicalEngineering,ChangzhouInstituteofTechnology,Changzhou213002,Jiangsu,China)2(SchoolofComputerScienceandCommunicationEngineering,JiangsuUniversity,Zhenjiang212013,Jiangsu,China)

Aiming at the excellent nonlinear expression ability of the kernel fuzzy clustering algorithm, this paper proposes a Gauss-induced kernel fuzzy c-means clustering algorithm. Firstly, based on the kernel objective function and the gradient method, the central expression of the feature space clustering is obtained, and the kernel matrix expression of the cluster center and the sample is obtained by the inner product operation. Secondly, the kernel function in the kernel objective function is Gauss kernel function, and the input spatial clustering center expression is obtained by using the gradient method. Finally, the kernel matrix of the clustering center and the sample is substituted into the input space clustering center expression to get the new clustering center calculation method of GIKFCMs, and the corresponding GIKFCMs kernel clustering algorithm is obtained. In this paper, we studied the properties of GIKFCMs and analyzed the convergence and initialization constraints of the algorithm. The algorithm overcomes the shortcomings of the original kernel clustering algorithm in convergence and initialization constraints. The effectiveness of the proposed algorithm is verified by simulation experiments. In addition, this paper also corrects the error of linear kernel FCM and FCM algorithm equivalence.

Kernel method Fuzzy clustering Non-linear mapping Kernel clustering center Algorithm equivalence proof

2016-10-28。國家自然科學(xué)基金項(xiàng)目(61170126)；常州工學(xué)院校級(jí)課題(YN1305)。文傳軍，博士，主研領(lǐng)域：數(shù)據(jù)挖掘，模式識(shí)別，模糊聚類。詹永照，教授。

TP391.41

A

10.3969/j.issn.1000-386x.2017.08.046