余曉東,雷英杰,宋亞飛,岳韶華,申曉勇

(空軍工程大學(xué)防空反導(dǎo)學(xué)院,陜西西安 710051)

?

基于核距離的直覺模糊c均值聚類算法

余曉東,雷英杰,宋亞飛,岳韶華,申曉勇

(空軍工程大學(xué)防空反導(dǎo)學(xué)院,陜西西安 710051)

針對現(xiàn)有直覺模糊c均值聚類算法無法發(fā)現(xiàn)非凸聚類結(jié)構(gòu)的缺陷,提出了一種基于核化距離的直覺模糊c均值聚類算法.算法在定義了基于核的直覺模糊歐式距離基礎(chǔ)上,通過把聚類樣本映射到高維特征空間,使原來沒有顯現(xiàn)的特征突現(xiàn)出來,從而能夠更好地聚類.實驗選擇一組人工數(shù)據(jù)集及一組UCI數(shù)據(jù)集測試了本文算法,并將其與五種經(jīng)典的聚類算法進行了比較.實驗結(jié)果充分表明了該算法的有效性及優(yōu)越性.

直覺模糊集;直覺模糊聚類;核方法;無監(jiān)督學(xué)習(xí)

1 引言

著名學(xué)者Ruspini[1]首先提出模糊劃分的概念,將Zadeh模糊集理論引入到聚類分析中來.隨后,研究者們提出了多種模糊聚類分析方法,主要包括基于模糊等價關(guān)系的傳遞閉包方法、基于相似性關(guān)系和模糊關(guān)系的方法以及基于模糊圖論的最大樹方法等,但是這些方法計算復(fù)雜度高,難以應(yīng)用于大數(shù)據(jù)問題及實時性要求較高的領(lǐng)域,因而在實際應(yīng)用與研究中已逐步減少[2].模糊c均值算法[3](Fuzzyc-Means,FCM)是一種基于目標(biāo)函數(shù)的聚類方法,它能夠通過優(yōu)化目標(biāo)函數(shù)得到各樣本相對各聚類中心的隸屬度,從而達到自動分類的目的,而廣泛應(yīng)用于模式識別、信息融合、網(wǎng)絡(luò)安全、圖像處理等領(lǐng)域.隨著Zadeh模糊集以及模糊聚類方法的日趨成熟,其隸屬度單一的局限性也逐漸顯現(xiàn)[4].直覺模糊集(Intuitionistic Fuzzy Sets,IFS)作為Zadeh模糊理論最重要的拓展形式之一,因其增加了猶豫度屬性參數(shù),從而進一步擴展和增強了模糊集理論對復(fù)雜不確定性知識的描述與處理功能,為模糊不確定性信息的建模與處理提供了新的思路和方法[5,6].文獻[7]將聚類對象及聚類中心點用直覺模糊集表示,提出來基于直覺模糊集合的模糊c均值(Intuitionistic Fuzzyc-means Clustering,IFCM)算法.目前,IFCM算法雖然取得了一些較好的應(yīng)用效果,但同樣也繼承了經(jīng)典FCM算法的一些缺點,如對噪聲和野值敏感,并且過于依賴樣本數(shù)據(jù)的分布結(jié)構(gòu),對復(fù)雜的數(shù)據(jù)結(jié)構(gòu)顯得無能為力.

針對這個問題,核方法被引入到此類算法中來.1995年,Cortes和Vapnik[8]提出了支持向量機(Support Vector Machine,SVM)理論,SVM在很多領(lǐng)域都體現(xiàn)出比傳統(tǒng)分類器更好的性能,使得核方法逐漸受到重視并被應(yīng)用到機器學(xué)習(xí)領(lǐng)域的各個方面[9,10].Girolami[11]創(chuàng)造性地提出了模糊核c均值算法(Fuzzy Kenelc-Means,FKCM)算法,解決FCM算法不能發(fā)現(xiàn)非凸聚類結(jié)構(gòu)的問題.文獻[12]提出了一種直覺模糊核聚類算法(Intuitionistic Fuzzy Kernel c-means Clustering Algorithm,IFKCM),但該方法為方便計算令樣本相對各類別隸屬度之和為1,與直覺模糊思想不符.文獻[13]通過提取核空間的幾何特性,提出了一種自適應(yīng)確定聚類數(shù)的核聚類方法.文獻[14,15]在經(jīng)典FCM算法中引入折中權(quán)重模糊因子和核距離度量,提出了一種基于模糊因子的核聚類算法,并將其應(yīng)用于圖像分割領(lǐng)域.鑒于此,本文嘗試將核方法與直覺模糊聚類方法理論相結(jié)合,并給出一種基于核化距離的直覺模糊c均值聚類算法(Kernel-based Intuitionistic Fuzzyc-means Clustering Algorithm,K-IFCM).

2 基于核的直覺模糊距離度量

定義1(直覺模糊歐式距離度量[5]) 若樣本x=(x1,x2,…,xn)和樣本y=(y1,y2,…,yn)均可用直覺模糊集表示,則它們之間的直覺模糊歐式距離可定義如下:

(1)

目前,絕大多數(shù)直覺模糊聚類算法均使用模式空間的直覺模糊歐式距離作為距離測度,然而現(xiàn)實中大多數(shù)聚類問題往往具備了直覺模糊歐式距離無法反映的復(fù)雜結(jié)構(gòu).圖1給出了一個簡單的示例,圖中的數(shù)據(jù)為人工同心圓樣本數(shù)據(jù),采用直覺模糊歐式距離測度后的聚類效果如圖1所示.可以看出,基于直覺模糊歐式距離,具有復(fù)雜數(shù)據(jù)結(jié)構(gòu)的聚類樣本在低維模式空間線性不可分.

基于以上分析,我們嘗試將樣本間的直覺模糊歐式距離投影到特征空間,并基于核方法

‖Φ(x)-Φ(y)‖2=K(x,y)-2K(x,y)+K(x,y)

(2)

給出基于核的直覺模糊歐式距離.

定義2(基于核的直覺模糊歐式距離度量) 若樣本x=(x1,x2,…,xn)和樣本y=(y1,y2,…,yn)均可用直覺模糊集表示,則它們之間基于核的直覺模糊歐式距離可定義如下:

(3)

3 基于核的直覺模糊c均值聚類算法

3.1 公式推導(dǎo)

設(shè)X={x1,x2,…,xn}?Rs為模式空間內(nèi)的一組有限觀測樣本集,假定每個樣本的特征均為s維的直覺模糊集,可表示為xi={,,…,}.將樣本集分成c類,c個聚類中心P=(p1,p2,…pc)也為直覺模糊集,可表示為pi={pμi1,pγi1,pπi1>,,…,}.

樣本xi與聚類中心pi之間的關(guān)系為模糊關(guān)系,對樣本X的分類結(jié)果仍然是一個模糊矩陣U=(μij)c×n,且滿足條件:

通過求出適當(dāng)?shù)闹庇X模糊分類矩陣U和聚類中心P,使目標(biāo)函數(shù)

(4)

最小,其中m稱作平滑參數(shù),‖Φ(xi)-Φ(pi)‖2為樣本xi與聚類中心pi之間核距離,本文在這里采用定義2給出的基于核的直覺模糊歐式距離度量,將式(3)帶入式(4)得目標(biāo)函數(shù)為:

(5)

注意到式(5)并沒有選擇特定的核函數(shù),因此任何滿足Mercer條件[9]的核函數(shù)K(x,y)都可適用該式.下面是兩個常用的Mercer核函數(shù):

高斯核函數(shù):KG(x,y)=exp(-‖x-y‖2/σ2),σ為自定義的參數(shù).

多項式核:KD(x,y)=(x·y+b)d,b,d為自定義的整數(shù)參數(shù).

由于高斯核函數(shù)對應(yīng)的是無窮維的特征空間,而有限樣本數(shù)據(jù)在無窮維特征空間一定線性可分的,因此,在實際應(yīng)用中通常采取高斯核函數(shù).而對于高斯核函數(shù),有?x∈X,KG(x,x)=1,因此基于高斯核的直覺模糊歐式距離可以簡化為

(6)

這是一個關(guān)于自變量(U,P)的約束優(yōu)化問題,由拉格朗日乘數(shù)法可得目標(biāo)函數(shù)為:

(7)

其中,λ為拉格朗日乘數(shù).由極值點的KT必要條件可得:

(8)

(9)

·(-2(xμj-pμj)))=0

(10)

·(-2(xμj-pμj)))=0

(11)

若?i,i=1,2,…c,使得DK-IFE(xj,pi)>0,則

(12)

若?i,i=1,2,…c,使得DK-IFE(xj,pi)=0,則

(13)

同理,可得聚類中心的迭代公式為:

(14)

(15)

3.2 算法步驟

下面給出基于核化距離的直覺模糊c均值聚類算法的詳細步驟:

算法1 基于核化距離的直覺模糊c均值聚類算法

輸入:樣本數(shù)據(jù)集X,聚類類別數(shù)c,平滑參數(shù)m,核函數(shù)及其參數(shù),最大迭代次數(shù)k,迭代停止閾值η.

輸出:劃分隸屬矩陣U,聚類中心P,迭代次數(shù)k.

Step1:初始化聚類中心P,令迭代次數(shù)t=1;

Step2:根據(jù)式(12)、(13)計算劃分隸屬矩陣U;

Step3:根據(jù)式(14)、(15)計算新的聚類中心點;

Step4:判斷是否滿足終止條件,若滿足,則停止迭代,輸出劃分隸屬矩陣U,聚類中心P,迭代次數(shù)t;否則,t=t+1,轉(zhuǎn)至Step2.結(jié)束條件為到達最大進化代數(shù)k,或目標(biāo)函數(shù)|Uk-Uk-1|≤η.

本文方法還涉及平滑參數(shù)m及核參數(shù)σ的選取.Bezdek給出了參數(shù)m的一個經(jīng)驗范圍[1.1,5],但沒有給出嚴格的證明[3],通常情況下參數(shù)m取值為2.如何對核參數(shù)σ進行取值,目前同樣缺乏理論支持,更多的是依靠經(jīng)驗取值,通常的解決方法是用一組專門的驗證數(shù)據(jù)集來確定核參數(shù)σ.

3.3 算法復(fù)雜度分析

本小節(jié)對本文算法的算法復(fù)雜度進行簡要分析.通過對算法步驟進行觀察,在整個運算過程中,計算最復(fù)雜的過程在Step2根據(jù)式(12)計算劃分隸屬矩陣U.由于算法的具體運算過程與核函數(shù)的選取有關(guān),因此這里令基本運算為DK-IFE(xj,pi)/DK-IFE(xj,pk),設(shè)m=2,則算法迭代一次,基本運算的計算次數(shù)為n·c·c,時間復(fù)雜度為T(n)=O(c2·n).算法運行過程中所需保存的數(shù)據(jù)包括樣本集內(nèi)的n個樣本,c個聚類中心以及模糊分類矩陣U,因此算法的空間復(fù)雜度為S(n)=O(c·n).

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

為了對算法性能進行驗證,本文選擇不同的樣本集合進行試驗,為了避免隨機誤差,每次試驗分別進行50次蒙特卡洛仿真.實驗前需要對數(shù)據(jù)進行直覺模糊化處理,在這里使用一種相對簡單的算法,即取各維樣本最大值的隸屬度值為1,其他樣本與最大值的比值為其隸屬度值,簡單起見,令猶豫度為0即可.實驗環(huán)境:操作系統(tǒng)Window XP,編程軟件Matlab7.6,Pentium(R)Core(TM)i7-3770 CPU @ 3.4GHz,3.46 GB的內(nèi)存.

4.1 同心圓樣本聚類實驗

采用如下參數(shù)方程產(chǎn)生兩類交錯的同心圓樣本進行試驗.

(16)

兩類樣本的半徑參數(shù)ρ均服從均勻分布,分別為[0,10]和[50,60],總隨機產(chǎn)生兩類樣本共120個.本文選取高斯核作為核函數(shù)進行試驗,由于不同的核參數(shù)σ的取值對算法的影響較大,本文專門取出一組驗證數(shù)據(jù)集對核函數(shù)σ的取值進行驗證.令平滑參數(shù)m分別取1.5,2和2.5,迭代誤差η=1e-5,最大迭代代數(shù)k=200,核參數(shù)σ在[1,100]等間隔取樣100次,σ對分類識別率的影響如圖2所示.為了模糊參數(shù)m的取值進行驗證,令核參數(shù)σ分別取5,10和15,迭代誤差η=1e-5,最大迭代代數(shù)k=200,模糊參數(shù)m在[1.1,11]等間隔取樣100次,m對分類識別率的影響如圖3所示.

經(jīng)過驗證,令模糊參數(shù)m=2.5,高斯核參數(shù)σ=10,迭代誤差η=1e-5,最大迭代代數(shù)k=200.為了驗證算法的有效性,我們將IFCM算法[7]、FKCM算法[11]、IFKCM算法[12]、ILKFCM算法[14]和本文方法(K-IFCM)進行對比.按設(shè)定參數(shù)進行50次蒙特卡洛仿真實驗,實驗結(jié)果如下表1所示.

表1 各算法聚類性能對比

4.2 Iris數(shù)據(jù)集聚類實驗

為了驗證算法在實際數(shù)據(jù)集上的聚類性能,選擇UCI數(shù)據(jù)集中經(jīng)典的Iris數(shù)據(jù)集對進行仿真實驗.實驗選取高斯核作為核函數(shù)進行試驗,令平滑參數(shù)m分別取1.5,2和2.5,迭代誤差η=1e-5,最大迭代代數(shù)k=200,核參數(shù)σ在[0.01,1]等間隔取樣100次,σ對分類識別率的影響如圖4所示.為了模糊參數(shù)m的取值進行驗證,令核參數(shù)σ分別取0.3,0.4和0.5,迭代誤差η=1e-5,最大迭代代數(shù)k=200,模糊參數(shù)m在[1.1,11]等間隔取樣100次,m對分類識別率的影響如圖5所示.

經(jīng)過驗證,令高斯核參數(shù)σ=0.4,模糊參數(shù)m=2,迭代誤差η=1e-5,最大迭代代數(shù)k=200.為了驗證算法的有效性,我們將本文方法與IFCM算法[7]、FKCM算法[11]、IFKCM算法[12]、ILKFCM算法[14]、Ng-Jordan譜聚類算法[16]及進行對比.按設(shè)定參數(shù)進行50次蒙特卡洛仿真實驗,實驗結(jié)果如下表2所示.

表2 各算法聚類性能對比

4.3 實驗結(jié)果分析

從以上兩組實驗的參數(shù)驗證情況來看,核參數(shù)σ相對模糊參數(shù)m對識別率的影響更大;甚至當(dāng)核參數(shù)σ取到一定值時,改變模糊參數(shù)m不會對算法的識別率產(chǎn)生影響.此外,模糊參數(shù)m在[1.1,5]之間取值時,算法的識別率較為穩(wěn)定,這與Bezdek給出了模糊參數(shù)m的經(jīng)驗范圍吻合.

從第一組對人工同心圓數(shù)據(jù)的實驗結(jié)果來看,IFCM算法雖然所需的聚類時間較短,但不具備發(fā)現(xiàn)非凸聚類結(jié)構(gòu)的能力,分類效果最差.引入核方法后,FKCM算法雖然也取得了較好的聚類效果,但因其隸屬度單一的缺陷,其分類的成功率仍然無法令人滿意.而IFKCM算法的正確率則相對一般,要遜于ILKFCM算法及K-IFCM算法,且算法的一次迭代時間最長,這是由于IFKCM算法雖然也把核方法引入到直覺模糊聚類算法,但在具體計算時,為方便計算令樣本相對各類別隸屬度之和為1,明顯違背了直覺模糊思想,再將分類樣本與聚類中心的關(guān)系推廣為直覺模糊關(guān)系時,又大大增加了算法的時間復(fù)雜度.ILKFCM算法正確率與K-IFCM算法基本相當(dāng),但其一次迭代時間則相對K-IFCM算法較長.這是因為ILKFCM算法在目標(biāo)函數(shù)中引入了一個權(quán)重模糊因子,提高算法的分類精度的同時也導(dǎo)致了計算量的增加.K-IFCM算法則充分結(jié)合了IFCM及FKCM兩者算法的優(yōu)點,將FKCM算法拓展到直覺模糊領(lǐng)域后,獲得了更多的樣本分類信息,聚類效果最好.同時,本文算法僅是改變了樣本間距離度量函數(shù),與其他核方法相比,算法的時間復(fù)雜度相對較小.此外,第二組對Iris數(shù)據(jù)集的實驗中我們增加了與Ng-Jordan譜聚類算法的對比,本文方法無論是聚類精度還是時間復(fù)雜度上均要優(yōu)于Ng-Jordan譜聚類算法,其余實驗結(jié)果與前兩組對人工樣本的實驗結(jié)果基本吻合,說明對該算法在實際數(shù)據(jù)集上同樣具有更好的聚類效果.

5 結(jié)論

本文將核方法與直覺模糊聚類算法進行有效結(jié)合,通過提出一種基于核的直覺模糊歐式距離,并以此作為直覺模糊聚類算法的距離度量,給出了一種基于核化距離的直覺模糊c均值聚類算法,解決了原有直覺模糊c均值聚類算法無法發(fā)現(xiàn)非凸聚類結(jié)構(gòu)的問題.實驗階段對核參數(shù)σ和平滑參數(shù)m的選取進行了探討,從實驗結(jié)果分析,本文方法在聚類性能上要優(yōu)于其他聚類算法.但是,該算法仍有一些需要改進及完善的地方,如引入核方法后,造成了算法時間復(fù)雜度的增加.此外,如何根據(jù)聚類樣本集選取參數(shù)均是下一步亟待解決的問題.

[1]Ruspini E H.A new approach to clustering[J].Information and Control,1969,15(1):22-32.

[2]Ceccarelli M,Maratea A.Improving fuzzy clustering of biological data by metric learning with side information[J].Int'l Journal of Approximate Reasoning,2008,47(1):45-57.

[3]Bezdek J C.Pattern recognition with fuzzy objective function algorithms[M].New York:Plenum Press,1981.

[4]雷英杰,王寶樹,苗啟廣.直覺模糊關(guān)系及其合成運算[J].系統(tǒng)工程理論與實踐,2005,25 (2):113-118,133.

Lei Y J,Wang B S,MIAO Q G.On the intuitionistic fuzzy relations with compositional operations[J].Systems Engineering Theory and Practice,2005,25 (2):113-118,133.(in Chinese)

[5]Song Y F,Wang X D,Lei L,Xue A J.Combination of interval-valued belief structures based on intuitionistic fuzzy set[J].Knowledge-Based Systems,2014,67:61-70.

[6]余曉東,雷英杰,孟飛翔,雷陽.基于PS-IFKCM的彈道中段目標(biāo)識別方法[J].系統(tǒng)工程與電子技術(shù),2015,37(1):17-23.

Yu X D,Lei Y J,Meng F X,Lei Y.Techniques for target recognition based on particle swarm-based intuitionistic fuzzy kernel clustering[J].Systems Engineering and Electronics,2015,37(1):17-23.(in Chinese)

[7]賀正洪,雷英杰.直覺模糊C均值聚類算法研究[J].控制與決策,2011,26(6):847-850,856.

He Z H,Lei Y J.Research on intuitionistic fuzzy C-means clustering algorithm[J].Control and Decision,2011,26(6):847-850,856.(in Chinese)

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

[9]Saket A,Sushil M,Oncel T,Peter M.Semi-supervised kernel mean shift clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2014,36(6):1201-1215.

[10]Nikhil R P,Kaushik S.What and when can we gain from the kernel versions of c-means algorithm?[J].IEEE Transactions on Fuzzy Systems,2014,22(2):363-379.

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

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

Fan C L,Xing Q H,Fu Q,et al.Technique for target recognition in ballistic midcourse based on intuitionistic fuzzy kernel clustering[J].Systems Engineering and Electronics,2013,35(7):1362-1367.(in Chinese)

[13]PiciarelliC,Micheloni C,Foresti G L.Kernel-based clustering[J].Electronics Letters,2013,49(2):113-114.

[14]XiangD L,Tang T,Hu C B,Li Y,Su Y.A kernel clustering algorithm with fuzzy factor:application to SAR image segmentation[J].IEEE Geoscience and Remote Sensing Letters,2014,11(7):1290-1294.

[15]Gong M G,et al.Fuzzy c-means clustering with local information and kernel metric for image segmentation[J].IEEE Transactions on Image Processing,2013,22(2):573-584.

[16]Ng A Y,Jordan M I,Weiss Y.On spectral clustering:analysis and an algorithm[A].Proceedings of Advances in Neural Information Processing Systems[C].Cambridge,MA:MIT Press,2002.849-856.

余曉東 男,1989年出生,江西九江人,空軍工程大學(xué)博士研究生,主要研究方向為模式識別、智能信息處理等.

E-mail:1438894571@qq.com

雷英杰 男,1956年出生,陜西渭南人,空軍工程大學(xué)教授,博士生導(dǎo)師,主要研究方向為智能信息處理與智能決策.

Intuitionistic Fuzzy c-means Clustering Algorithm Based on Kernelled Distance

YU Xiao-dong,LEI Ying-jie,SONG Ya-fei,YUE Shao-hua,SHEN Xiao-yong

(AirandMissileDefenseCollege,AirForceEngineeringUniversity,Xi’an,Shaanxi710051,China)

The intuitionistic fuzzyc-means clustering algorithm cannot discover the non-convex cluster structure.To alleviate this problem,an intuitionistic fuzzyc-means clustering algorithm based on kernelled distance is proposed.By defining the intuitionistic fuzzy Euclid distance,we map the sample to a high-dimension feature space.So the former features can be reflected thoroughly,which is helpful for clustering.Experiments executed on one artificial data sets and one UCI data sets demonstrate the performance of the proposed method.Compared with the five classical cluster algorithms,our method is of obvious effectiveness and superiority.

intuitionistic fuzzy set;intuitionistic fuzzy clustering;kernel method;unsupervised learning

2015-02-04;

2015-06-08;責(zé)任編輯：李勇鋒

國家自然科學(xué)基金(No.61272011，No.61309022);陜西省自然科學(xué)青年基金(No.2013JQ8031)

TP182;TP391

A

0372-2112 (2016)10-2530-05

??學(xué)報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.10.035