王書文，皮炳坤，張弘強(qiáng)，馬　聰

?

一種基于模糊核聚類算法的圖像分類方法

王書文，皮炳坤，張弘強(qiáng)，馬聰

(西北民族大學(xué)電氣工程學(xué)院，甘肅蘭州730030)

聚類分析是數(shù)據(jù)分析的一個(gè)重要方法.通過引用核函數(shù)，將核方法應(yīng)用到模糊C均值(Fuzzy c-Means,FCM)算法中，優(yōu)化FCM算法的目標(biāo)函數(shù)，使樣本點(diǎn)被非線性變換映射到高維特征空間進(jìn)行聚類,不僅改善了聚類效果，而且增強(qiáng)了算法對(duì)噪聲的魯棒性.在真實(shí)樣本集上進(jìn)行了仿真實(shí)驗(yàn)，分類結(jié)果證實(shí)了該算法的有效性和普適性，因而是一種較為簡單和實(shí)用的圖像分類方法.

聚類分析；子空間聚類；核函數(shù)；核模糊聚類算法

近年來，模糊聚類分析技術(shù)是智能信息處理中的一個(gè)熱門課題,它用一種模糊數(shù)學(xué)方法來研究聚類問題,是一種無監(jiān)督的模糊模式識(shí)別方法,在模式識(shí)別及分類、圖形圖像處理、以及計(jì)算機(jī)視覺等領(lǐng)域有著廣泛的應(yīng)用[1-6].

目前普遍應(yīng)用的聚類分析方法有K-均值法[1]和模糊C-均值法[2]等.在多種模糊聚類分析算法中，由Dunn[3]首先提出后又被Bezdek[4]加以推廣的模糊C 均值算法是一種很有效的方法.模糊C-均值聚類算法因其算法簡單、收斂速度快等優(yōu)點(diǎn)受到廣泛關(guān)注.而Bezdek提出的模糊聚類算法FCM則通過引入像素聚類樣本到聚類中心的隸屬度來表示像素樣本的隸屬度，該類隸屬度的大小能夠客觀反映出算法中樣本點(diǎn)隸屬于某一類的程度[5].雖然FCM算法計(jì)算簡單，復(fù)雜度較低，但在很多情況下該算法對(duì)噪聲敏感.Girolami[6]和張莉等[7]將核函數(shù)引入到聚類分析中，在高維特征空間中進(jìn)行聚類；曲福恒等[8]利用Zangwill收斂性定理，證明了核模糊C-均值聚類算法(KFCM)的收斂性；范成禮等[9]對(duì)模糊核聚類算法進(jìn)行了直覺化擴(kuò)展，提出一種基于核化距離的直覺模糊聚類(IFKCM)算法，但其收斂速度較慢，易陷入局部最優(yōu)解等難題.

用核方法改造傳統(tǒng)的學(xué)習(xí)算法是當(dāng)今機(jī)器學(xué)習(xí)領(lǐng)域的一個(gè)熱點(diǎn).因此，模糊核聚類算法[10]在一定程度上能夠克服傳統(tǒng)FCM 算法不適合多種數(shù)據(jù)結(jié)構(gòu)的缺陷，并具有普適性，能夠容忍噪聲，具有廣泛的應(yīng)用價(jià)值.基于以上分析，本文將模糊核聚類算法應(yīng)用到低維空間中的子空間聚類問題來實(shí)現(xiàn)數(shù)據(jù)的分類.

1　核模糊C均值聚類算法

核模糊C均值聚類(KFCM)算法的基本思想是選取相應(yīng)的核函數(shù)替代FCM算法中的歐氏距離，將低維輸入空間的非線性問題轉(zhuǎn)換為高維特征空間的線性問題.而FCM的目標(biāo)函數(shù)為

(1)

(2)

引入核方法，則可將目標(biāo)函數(shù)轉(zhuǎn)化為

(3)

其中Φ為特征映射，根據(jù)核方法中的轉(zhuǎn)換技巧，可做如下轉(zhuǎn)換

(4)

在此選取高斯核函數(shù)

(5)

根據(jù)

(6)

結(jié)合K(x，x)= 1,則目標(biāo)函數(shù)可轉(zhuǎn)化為

(7)

為了最小化目標(biāo)函數(shù)，結(jié)合約束條件，得到聚類中心和隸屬度矩陣的更新公式為

(8)

(9)

根據(jù)上式不斷迭代求出滿足條件的隸屬度以及聚類中心，從而最小化目標(biāo)函數(shù).為保證算法收斂，KFCM算法具體步驟為:

1)設(shè)定類別的個(gè)數(shù)C和模糊系數(shù)m，初始化隸屬度矩陣且滿足歸一化條件；

2)根據(jù)(9)式確定聚類中心Vi；

3)根據(jù)(8)式更新隸屬度矩陣U；

4)根據(jù)矩陣范數(shù)比較迭代的隸屬度矩陣，若收斂，迭代停止，否則返回步驟2.

2　結(jié)果與分析

為了驗(yàn)證該算法的有效性和可行性,本文選取了一組三個(gè)低維空間中的子空間聚類問題和兩個(gè)實(shí)際應(yīng)用中的聚類問題[11]來進(jìn)行仿真實(shí)驗(yàn).實(shí)驗(yàn)在Matlab 7.0軟件環(huán)境下完成,利用改進(jìn)的核模糊C均值聚類KFCM算法可實(shí)現(xiàn)對(duì)數(shù)據(jù)的分類.

一組低維空間的樣本集采用改進(jìn)的核模糊C均值聚類KFCM算法，將其分為兩類的結(jié)果如圖1所示.其中，圖1(a)為兩條交點(diǎn)不在原點(diǎn)且互相垂直的直線;圖1(b)為兩條不相交的二次曲線;圖1(c)為兩條相交的螺旋線.為了測試FCM聚類算法和改進(jìn)的模糊核聚類算法的聚類性能，將上述兩個(gè)聚類算法在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)對(duì)比分析，其結(jié)果見表1.

表1　人工數(shù)據(jù)實(shí)驗(yàn)結(jié)果比較(20次隨機(jī)實(shí)驗(yàn))

圖1　不同算例原始圖及聚類結(jié)果

由表1可以看出，其分類結(jié)果較好.而模糊核聚類算法比FCM算法在各方面均有一定的改善，而提出的改進(jìn)模糊核聚類算法在正確率上有了提升，與一些FCM等聚類算法相比，明顯提高了聚類的穩(wěn)定性.

在實(shí)際應(yīng)用中，基于特征點(diǎn)軌跡的方法是重要的一類運(yùn)動(dòng)分割方法，有文獻(xiàn)指出同一運(yùn)動(dòng)的特征點(diǎn)軌跡在同一個(gè)線性流形上，而圖2(a)給出了視頻中的一幀，有三個(gè)不同運(yùn)動(dòng)的特征點(diǎn)軌跡被提取出來保存在了樣本文件中，利用改進(jìn)的核模糊C均值聚類KFCM算法，將這些特征點(diǎn)軌跡分成三類的結(jié)果見圖2(b)所示.

從圖中可以看出,其改進(jìn)的模糊核聚類算法的分類正確率也達(dá)到了94.62%，能有效防止小數(shù)據(jù)類被誤分的情況，進(jìn)而得出改進(jìn)的模糊核聚類(KFCM)算法的方法是有效的，能客觀反映其實(shí)際情況.

圖2　原始數(shù)據(jù)圖及分類結(jié)果

3　結(jié)束語

本文分析了一種改進(jìn)的模糊核聚類(KFCM)算法,通過核函數(shù)對(duì)數(shù)據(jù)進(jìn)行隱性的非線性映射，較好地實(shí)現(xiàn)了對(duì)差別微弱的樣本類之間的聚類，使得算法能取得良好的分類結(jié)果.該聚類方法在性能上比經(jīng)典聚類算法有所改進(jìn),具有較高的準(zhǔn)確度.仿真實(shí)驗(yàn)結(jié)果證實(shí)了算法的可行性和可靠性.而未來發(fā)展中，如何把KFCM算法與蟻群算法、粒子群等智能算法相結(jié)合是研究的重點(diǎn)，并如何根據(jù)實(shí)際問題選用合適的核函數(shù)及最優(yōu)參數(shù)也是一大重點(diǎn).今后將采用聚類有效性指標(biāo)作為適應(yīng)度函數(shù)，利用多目標(biāo)優(yōu)化算法進(jìn)行同時(shí)優(yōu)化，進(jìn)一步提升聚類方法的穩(wěn)定性.

[1]JAIN A K.Data clustering:50 years beyond K-means[J].PatternRecognitionLetters,2010,31(8):651.

[2]ZBAY Y,CEYLAN R,KARLIK B.Integration of type-2 fuzzy clustering and wavelet transform in a neural network based ECG classifier[J].ExpertSystemswithApplications,2011,38(1):1004.

[3]DUMN J C.A graph theoretic analysis of pattern classification via tamura’s fuzzy relation[J].IEEETransonFuzzySystem,1974,4(3):310.

[4]BEZDEK J C.PatternRecognitionwithFuzzyObjectiveFunctionAlgorithms[M].New York:New York Plenum Press,1981.

[5]CHUANG K S，TZENG H L，CHEN S，et al.Fuzzy c-means clustering with spatial information for image segmentation[J].JournaloftheComputerizedMedicalImagingSociety,2006,30(1):9.

[6]GIROLAMI M.Mercer kernel based clustering in feature space [J].IEEETransonNeuralNetworks,2002,13(3):780.

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

[8]曲福恒，胡雅婷，馬駟良,等.基于核的模糊C-均值聚類算法的收斂性定理[J].吉林大學(xué)學(xué)報(bào)(理學(xué)版)，2011，49(6)：1079.

[9]范成禮,邢清華,付強(qiáng),等.基于直覺模糊核聚類的彈道中段目標(biāo)識(shí)別方法[J].系統(tǒng)工程與電子技術(shù),2013,35(7):1362.

[10]彭建喜.一種基于C均值的模糊核聚類圖像分割算法[J].電視技術(shù)，2014,38(9):28.

[11]羅四維.視覺信息認(rèn)知計(jì)算理論[M].北京:科學(xué)出版社，2010.

(責(zé)任編輯孫對(duì)兄)

An image classification method based on fuzzy kernel clustering algorithm

WANG Shu-wen,PI Bing-kun，ZHANG Hong-qiang,MA Cong

(College of Electrical Engineering,Northwest University for Nationalities,Lanzhou 730030,Gansu,China)

The clustering analysis is a crucially important method for data analysis.By referring to kernel function,the kernel method is applied to the fuzzy C-means(fuzzy C-means, FCM) algorithm,optimizing objective function of FCM algorithm,sample points are mapped to high-dimensional feature space by the nonlinear transform cluster.The method can not only improve the clustering effect,but also enhance the algorithm robustness to noise.Simulated experiments are conducted on real sample set,the classification results prove the effectiveness and generalizability of the algorithm,so this algorithm is a relatively simple and practical method.

cluster analysis;subspace clustering;kernel function;nuclear fuzzy clustering algorithm

10.16783/j.cnki.nwnuz.2016.05.010

2016-03-08;修改稿收到日期:2016-07-03

國家自然科學(xué)基金資助項(xiàng)目(61261042)；西北民族大學(xué)中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助研究生項(xiàng)目(YXM2015215)

王書文(1965—)，男，河南扶溝人，教授，碩士研究生導(dǎo)師.主要研究方向?yàn)閳D像處理與密碼學(xué).

E-mail:294171424@qq.com

TP 311

A

1001-988Ⅹ(2016)05-0042-04