李 凱,曹 喆

(河北大學(xué)計算機科學(xué)與技術(shù)學(xué)院,河北保定,071000)

?

一種基于神經(jīng)網(wǎng)絡(luò)的廣義熵模糊聚類算法

李 凱,曹 喆

(河北大學(xué)計算機科學(xué)與技術(shù)學(xué)院,河北保定,071000)

以模糊聚類為基礎(chǔ),將廣義熵引入到模糊聚類的目標函數(shù)中,提出一種基于模糊熵的模糊聚類的統(tǒng)一形式,即廣義熵模糊聚類模型;利用增廣拉格朗日求解方法,以及Hopfield神經(jīng)網(wǎng)絡(luò)和復(fù)突觸神經(jīng)網(wǎng)絡(luò)解決了基于廣義熵的目標函數(shù)的優(yōu)化問題,提出了基于神經(jīng)網(wǎng)絡(luò)的廣義熵模糊聚類算法,表明了使用神經(jīng)網(wǎng)絡(luò)求解的收斂性;同時,給出一種用于確定增廣拉格朗日乘子的迭代方法.實驗中選取人工生成數(shù)據(jù)集和UCI標準數(shù)據(jù)集對提出的算法進行了實驗研究,并與常用的聚類算法進行了性能比較.

模糊聚類;廣義熵;增廣拉格朗日方法;神經(jīng)網(wǎng)絡(luò)

電子學(xué)報URL:http://www.ejournal.org.cn DOI:10.3969/j.issn.0372-2112.2016.08.016

1 引言

為了克服FCM對噪聲的影響,一些學(xué)者將模糊熵引入到目標函數(shù)J1(U,V) 中,提出了基于熵的聚類算法[7～11];另外,一些學(xué)者基于目標函數(shù)J2(U,V),通過加入調(diào)整項,提出了競爭凝聚算法CA,以此解決聚類數(shù)的自動確定問題[12],之后,學(xué)者們在CA聚類算法的基礎(chǔ)上,將約束條件或樣本間的度量引入到J2(U,V)中,提出了半監(jiān)督聚類算法[13-14];最近,Maraziotis[15]通過對約束進行量化,并將其引入到J2(U,V),提出了一種半監(jiān)督模糊聚類算法.可以看到,以上介紹的聚類算法,學(xué)者們主要采用Jm(U,V)的特殊形式J1(U,V)或J2(U,V),通過引入調(diào)整項,并借助拉格朗日方法,獲得相應(yīng)的模糊聚類算法.為了研究一般情形下的聚類算法,Pedrycz等[16]將監(jiān)督信息引入到Jm(U,V)中,給出了一般形式的目標函數(shù),然而,他們并未對此種優(yōu)化問題給出求解方法,只是使用了特殊的目標函數(shù)J2(U,V);另外,Wei等[17]試圖使用神經(jīng)網(wǎng)絡(luò)解決一般目標函數(shù)的模糊聚類,遺憾的是該方法卻存在一些問題[18].針對此種情況,本文研究了一般情形下的目標函數(shù)構(gòu)成的優(yōu)化問題的模糊聚類.

2 廣義熵模糊聚類的目標函數(shù)

(1)

其中α>0且α≠1,δ為參數(shù).因此,廣義熵模糊聚類的優(yōu)化問題為

(2)

由式(1)知,當m=1且α→1時,式(1)成為Karayiannis[9]等提出的聚類算法.當α→1時,式(1)為Wei等[17]提出的聚類算法,因此,優(yōu)化問題式(2)可以視為它們的統(tǒng)一形式.

另外,由式(2)中的目標函數(shù)可以知道,當m=α?xí)r,該優(yōu)化問題可以通過拉格朗日方法求解,對于此種情況,我們已經(jīng)進行了研究[19];然而,當m≠α?xí)r,使用傳統(tǒng)拉格朗日求極值方法對式(2)求解是不可行的.實際上,對于優(yōu)化問題式(2),可以使用啟發(fā)式方法求解,例如,禁忌搜索、變鄰域搜索等.本文主要使用神經(jīng)網(wǎng)絡(luò)方法對其進行求解.

3 廣義熵模糊聚類的神經(jīng)網(wǎng)絡(luò)方法

為了求解優(yōu)化問題式(2),本文使用增廣拉格朗日方法,Hopfield神經(jīng)網(wǎng)絡(luò)與復(fù)突觸神經(jīng)網(wǎng)絡(luò)求解.

3.1 使用Hopfield網(wǎng)絡(luò)求解聚類中心

對于優(yōu)化問題式(2),其增廣拉格朗日函數(shù)為

(3)

其中λk(k=1,2,…,n)為拉格朗日乘子,λ=(λ1,λ2,…,λn),γ是一個充分大的數(shù).由式(3)知道,它是一個關(guān)于聚類中心vi=(vi,1,vi,2,…,vi,N)(i=1,2,…,c)的二次函數(shù),通過將二維下標轉(zhuǎn)化為一維下標,且使用具有q=c×N個神經(jīng)元的Hopfield神經(jīng)網(wǎng)絡(luò)求解,下面給出了求解聚類中心的Hopfield神經(jīng)網(wǎng)絡(luò)的權(quán)值,外部輸入和激勵函數(shù).

NET=W·V+I

其中NET=(net1,net2,…,netq)T,

W=(wij)q×q,V=(v1,v2,…,vq)T,I=(i1,i2,…,iq)T,

(4)

i=1,2,…,c;l=1,2,…,N

(5)

j=1,2,…,q;i=1,2,…,q,

(6)

(7)

其中上角標的g為迭代次數(shù),δj是一個較小的可調(diào)正數(shù),詳細推導(dǎo)可參見文獻[17].

3.2 使用復(fù)突觸神經(jīng)網(wǎng)絡(luò)求解模糊隸屬度

令dik=‖xk-vi‖2,則式(3)變?yōu)?/p>

(8)

+(u(k-1)×c+c)md(k-1)×c+c

+γ(u(k-1)×c+1+u(k-1)×c+2+…+u(k-1)×c+c)2

+δ(21-α-1)-1((u(k-1)×c+1)α+(u(k-1)×c+2)α+…

+(u(k-1)×c+c)α)

+(λk-2γ)(u(k-1)×c+1+u(k-1)×c+2+…+u(k-1)×c+c)

+γ-λk-δ(21-α-1)-1]

(9)

由m和α的取值可知,函數(shù)式(9)可能為一個高次的函數(shù),鑒于此種情況,本文使用復(fù)突觸神經(jīng)網(wǎng)絡(luò)對其進行優(yōu)化.根據(jù)聚類中心vi(i=1,2,…,c)在第二層循環(huán)中其值不變以及最后一行為常數(shù),因此,在下面的優(yōu)化中對這些項進行刪除.

j=1,2,…,s

(10)

網(wǎng)絡(luò)輸入的矩陣形式可表示為:

NET=W·U+Z·U+Y·U+I

(11)

其中Z=(zij)s×s,Y=(yij)s×s,U=(u1,u2,…,us)T,I=(i1,i2,…,is)T,s=n×c.

定義矩陣U和Y<α-1>如下:

為了獲得求解隸屬度的神經(jīng)網(wǎng)絡(luò),利用式(11)得到如下的能量函數(shù):

(12)

比較式(9)和式(12),獲得了如下的對應(yīng)關(guān)系:

(13)

(14)

i,j=1,2,…,s

(15)

ij=2γ-λkj=1,2,…,s;k=「j/c?

(16)

其中「x?為不小于x的最小整數(shù).利用對稱矩陣和向量具有LTAR=RTAL關(guān)系(其中A為一個對稱矩陣,L和R分別為列向量),則式(12)變?yōu)?/p>

(17)

對于此式,可以理解為將-(1/m)UT、-(1/2)UT、-(1/α)UT和-UT分別乘以式(18)中右邊第一項、第二項、第三項和第四項,這就意味著將U反饋給權(quán)值W,將新的U反饋給權(quán)值Z,將U<α-1>反饋給權(quán)值Y,從而得到一種具體的復(fù)突觸神經(jīng)網(wǎng)絡(luò),其中網(wǎng)絡(luò)輸入的權(quán)值矩陣為:

NET=W·U+Z·U+Y·U<α-1>+I

(18)

激勵函數(shù)f按照如下方法確定,其中ωj是一個較小的可調(diào)整正數(shù),

j=1,2,…,s.

(19)

3.3 增廣拉格朗日乘子的確定

為了確定式(16)中的拉格朗日乘子,考慮如下的優(yōu)化問題:

(20)

其增廣拉格朗日函數(shù)為:

L(U,V;λ)

(21)

關(guān)于式(20)和(21)有如下結(jié)論[20]:如果U*,V*是問題式(20)的最優(yōu)解,λ*為由拉格朗日乘子構(gòu)成的向量,則當γ充分大時,U*,V*是式(21)的極小值點,且式(20)和(21)等價.為此,針對式(21),先給定λ*的一個初始值λ(p),并用該值求解優(yōu)化問題式(21),設(shè)其解為U(p+1),這樣可以得到如下等式:

▽UL(U(p+1),V;λ(p))

+2γφk(U(p+1)))▽φk(U(p+1))

=0

可以看到,如果U*是式(20)的最優(yōu)解,則有

從而有

(22)

3.4 廣義熵模糊聚類算法GEFCM

通過上面的推導(dǎo),下面給出具體的算法,并將該算法記為GEFCM(Generalized Entropy FCM):

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

為了表明提出的算法GEFCM的有效性,實驗中選取了7個數(shù)據(jù)集進行了研究,其中Arti3是人工生成的三維線性可分數(shù)據(jù)集,具有3個類別和150個數(shù)據(jù)樣本,且每類中的數(shù)據(jù)點個數(shù)均為50.另外6個數(shù)據(jù)集來自于UCI,分別為Iris,Breast-w,Wine,Heart,Ionosphere和Australian.實驗中選擇的參數(shù)值分別為γ=1000,δv=0.5,δu=0.2,ε=0.001,Δv=0.0001和Δu=0.0001.為了評價聚類的性能,實驗中選擇了聚類正確率作為評價指標,即正確聚類的個數(shù)除以樣本總數(shù).實驗結(jié)果如表1至表7所示.

表1 Arti3數(shù)據(jù)集的實驗結(jié)果

表2 Iris數(shù)據(jù)集的實驗結(jié)果

表3 Breast-w數(shù)據(jù)集實驗結(jié)果

表4 Wine數(shù)據(jù)集實驗結(jié)果

表5 Heart數(shù)據(jù)集實驗結(jié)果

表6 Ionosphere數(shù)據(jù)集實驗結(jié)果

表7 Australian數(shù)據(jù)集實驗結(jié)果

由實驗結(jié)果可以看到,對于可分性數(shù)據(jù)集Arti3,當加權(quán)指數(shù)和廣義熵指數(shù)相等且接近于1時,獲得了較好的聚類結(jié)果;然而,對于選擇的UCI標準數(shù)據(jù)集,當加權(quán)指數(shù)和廣義熵指數(shù)相等且接近于1或加權(quán)指數(shù)等于2時,其聚類結(jié)果并不一定是最好的,例如,對于Wine數(shù)據(jù)集,當m=2且α=2時,獲得了最好的聚類正確率85.96,然而,當α=2時,此時的廣義熵并不是模糊熵,表明了基于模糊熵的聚類未必獲得更好的聚類結(jié)果,從而充分說明引入廣義熵模糊聚類的重要性.

另外,為了驗證提出的算法GEFCM的性能,實驗中也選取了FCM、PPSO-FCM[21]以及SSWFCM算法[22]在標準數(shù)據(jù)集進行了比較,實驗結(jié)果如圖2所示.

可以看到,基于廣義熵的模糊聚類算法在選取的數(shù)據(jù)集上的聚類正確率都高于FCM、PPSO-FCM和SSWFCM,且此時加權(quán)指數(shù)m的取值并不僅限制在1或2兩個值,從而表明提出的廣義熵目標函數(shù)聚類的合理性.

5 結(jié)論

本文通過引入廣義熵,提出了廣義熵模糊聚類模型,統(tǒng)一了基于熵的模糊聚類算法,使用Hopfield神經(jīng)網(wǎng)絡(luò)和復(fù)突觸神經(jīng)網(wǎng)絡(luò)并結(jié)合增廣拉格朗日乘子法解決了基于廣義熵的模糊聚類問題,提出了基于神經(jīng)網(wǎng)絡(luò)的廣義熵模糊聚類算法,給出了拉格朗日乘子的確定方法.在實驗中,選取人工數(shù)據(jù)集和UCI數(shù)據(jù)集對提出的算法性能進行了測試,并與其它算法進行了性能比較,表明了提出的算法對數(shù)據(jù)聚類的有效性.

[1]Timothy C H,James C B,Christopher L,et al.Fuzzy c-Means algorithms for very large data[J].IEEE Transactions on Fuzzy Systems,2012,20(6):1130-1146.

[2]慕彩紅,霍利利,劉逸,劉若辰,焦李成.基于小波融合和PCA-核模糊聚類的遙感圖像變化檢測[J].電子學(xué)報,2015,43(7):1375-1381.

Mu Caihong,Huo Lili,Liu Yi,Jiao Licheng.Change detection for remote sensing images based on wavelet fusion and PCA-kernel fuzzy clustering[J].Acta Electronica Sinica,2015,43(7):1375-1381.(in Chinese)

[3]Yang M S,Tsai H S.A gaussian kernel-based fuzzy c-means algorithm with a spatial bias correction[J].Pattern Recognition Letters,2008,29(12):1713-1725.

[4]劉兵,夏士雄,周勇,韓旭東.基于樣本加權(quán)的可能性模糊聚類算法[J].電子學(xué)報,2012,40(2):371-375.

Liu Bing,Xia Shixiong,Zhou Yong,Han Xudong.A sample-weighted possibilistic fuzzy clustering algorithm[J].Acta Electronica Sinica,2012,40(2):371-375.(in Chinese)

[5]Jacek M L.Fuzzy c-ordered-means clustering[J].Fuzzy Sets and Systems,2016,286,114-133.

[6]Ding Y,Fu X.Kernel-based fuzzy c-means clustering algorithm based on genetic algorithm[J].Neurocomputing,doi:10.1016/j.neucom.2015.01.106.

[7]Krishnapuram R,Keller,J M.A possibilistic approach to clustering[J].IEEE Transactions on Fuzzy Systems,1993,1(2):98-110.

[8]Krishnapuram R,Keller J M.The possiblistic means algorithms:insights and recommendation[J].IEEE Transactions on Fuzzy Systems,1996,4(3):385-393.

[9]Karayiannis N B.MECA:maximum entropy clustering algorithm[A].IEEE world congress on computational intelligence,Proceedings of the third IEEE conference on fuzzy systems[C].Orlando:IEEE,1994.630-635.

[10]Ichihashi H,Miyagishi K,Honda K.Fuzzy c-means clustering with regularization by K-L information[A].Proceedings of the 10th IEEE international conference on fuzzy systems[C].Melbourne:IEEE,2001.924-927.

[11]Yasuda M,Furuhashi T,Matsuzaki M,et al.A study on statistical mechanical characteristics of fuzzy clustering[A].Proceedings of IEEE International Conference on Systems,Man,and Cybernetics[C].Tucson:IEEE,2001.2415-2420.

[12]Frigui H,Krishnapuram R.Clustering by competitive agglomeration[J].Pattern Recognition,1997,30 (7):1109-1119.

[13]Grira N,Crucianu M,Boujemaa N.Active semi-supervised fuzzy clustering[J].Pattern Recognition,2008,41 (5):1834-1844.

[14]Gao C F,Wu X J.A new semi-supervised clustering algorithm with pairwise constraints by competitive agglomeration[J].Applied Soft Computing,2011,11(8):5281-5291.

[15]Maraziotis I A.A semi-supervised fuzzy clustering algorithm applied to gene expression data[J].Pattern Recognition,2012,45:637-648.

[16]Pedrycz W,Amato A,Lecce V D,et al.Fuzzy clustering with partial supervision in organization and classification of digital images[J].IEEE Transactions on Fuzzy Systems,2008,16(4):1008-1026.

[17]Wei C,Fahn C.The multisynapse neural network and its application to fuzzy clustering[J].IEEE Transactions on Neural Networks,2002,13(3):600-618.

[18]Yu J,Hao P W.Comments on “The multisynapse neural network and its application to fuzzy clustering”[J].IEEE Transaction on Neural Networks,2005,16(3):777-778.

[19]Li K,Ma H Y,Wang Y.Unified model of fuzzy clustering algorithm based on entropy and its application to image segmentation[J].Journal of Computational Information Systems,2011,7(15):5476-5483.

[20]劉健,王曉明著.鞍點規(guī)劃與形位誤差評定[M].大連:大連理工大學(xué)出版社,1996.

Liu Jian,Wang Xiaoming.Saddle Point Programming and Geometric Error Evaluation[M].Dalian:Dalian University of Technology Press,1996.

[21]Liu H,Yih J M,Wu D B,Liu S W.Fuzzy c-mean clustering algorithms based on picard iteration and particle swarm optimization[A].Proceedings of International Workshop on Education Technology and Training[C].Washington:IEEE,2008.838-842.

[22]Zhang X B,Huang H,Zhang S.A FCM clustering algorithm based on semi-supervised and point density weighted[A].Proceedings of IEEE International Conference on Intelligent Computing and Intelligent Systems[C].Xiamen:IEEE,2010.710-713.

李 凱 男,1963年出生,河北保定人.2005年畢業(yè)于北京交通大學(xué)計算機與信息技術(shù)學(xué)院,并獲得工學(xué)博士學(xué)位.主要從事機器學(xué)習(xí)、模式識別、數(shù)據(jù)挖掘等方面的研究.

E-mail:likai@hbu.edu.cn

曹 喆 女,1991年出生,河北邢臺人,碩士研究生.主要從事機器學(xué)習(xí)和數(shù)據(jù)挖掘等方面的研究.

A Fuzzy Clustering Algorithm with Generalized Entropy Based on Neural Network

LI Kai,CAO Zhe

(SchoolofComputerScienceandTechnology,HebeiUniversity,Baoding,Hebei071000,China)

Based on fuzzy clustering,an unified form is presented for fuzzy clustering algorithm based on fuzzy entropy by introducing the generalized fuzzy entropy into objective function of fuzzy clustering,namely generalized entropy’s fuzzy clustering model.Optimization problem for generalized entropy’s objective function is solved using Hopfield neural network and multiple synapses based on augmented Lagrange method.After that,the generalized entropy’s fuzzy clustering algorithm based on neural network is presented.And convergence of neural network is shown.At the same time,iterative method is given to determine Lagrange multipliers.In experiments,a synthetic data set and some standard UCI data sets are chosen to conduct some experimental studies.And clustering performance is compared with commonly used clustering algorithms.

fuzzy clustering;generalized entropy;augmented Lagrange method;neural network

2015-12-08;

2016-03-18;責任編輯：藍紅杰

國家自然科學(xué)基金(No.61375075)

TP18

A

0372-2112 (2016)08-1881-06