一種多類原型模糊聚類的初始化方法

一種多類原型模糊聚類的初始化方法

模糊聚類是非監(jiān)督模式分類的一個重要分支，在模式識別和圖像處理中已經(jīng)得到了廣泛的應(yīng)用.但現(xiàn)有模糊聚類算法大都需要聚類數(shù)的先驗知識，而且對初始化極為敏感，從而限制了它們的實際應(yīng)用.此外對于多類原型樣本集的聚類分析，還需要事先已知原型的類型及相應(yīng)數(shù)目.為了克服這些限制，本文提出一種聚類原型先驗知識的獲取方法，并用來初始化多類原型模糊聚類，取得了較好的效果.
　　關(guān)鍵詞:模糊聚類；數(shù)學形態(tài)學；細化；曲線擬合

An Initialization Method for Multi-Type Prototype Fuzzy Clustering

GAO Xin-bao,XUE Zhong,LI Jie,XIE Wei-xin
(School of Electronics Engineering,Xidian University,Xi'an 710071,China)

　　Abstract:Fuzzy clustering is an important branch of unsupervised classification,and has been widely used in pattern recognition and image processing.However,most of exiting fuzzy clustering algorithms are sensitive to initialization,and strongly depend on the number of clusters,which limits their applications.Moreover,it also needs to know the type and number of prototypes in advance in multi-type prototype fuzzy clustering.To overcome these limitation,a method for acquiring a priori knowledge about clustering prototype is proposed in this paper,which obtains better performance in initializing multi-type prototype fuzzy clustering.
　　Key words:fuzzy clustering;mathematical morphology;thinning;curve fitting

一、引　　言
　　聚類分析是非監(jiān)督模式分類的一個分支，其基本任務(wù)是把特征空間中一個未標記的模式樣本集按照某種相似性準則劃分到若干個子集中，使相似的樣本盡量歸為一類.傳統(tǒng)的聚類分析是基于硬劃分的，每個樣本屬于且只屬于某一類.1973年Dunn［1］引入模糊集理論，定義了基于目標函數(shù)J2(U,v)的模糊c-均值聚類算法.后來，Bezdek［2］又推廣到了一個目標函數(shù)的無限族，此后模糊c-均值聚類算法成為研究的主流.在模糊聚類中，樣本不再僅屬于某一類，而是以不同的程度分屬于每一類，表達出了樣本間的相近信息及事物在性態(tài)和類屬方面的中介性，從而更符合人的分類方式.
　　隨著模糊c-均值算法理論和應(yīng)用的發(fā)展［3］，為檢測橢球狀分布以外的模式子集，該算法被逐步推廣到模糊c-線［4］、模糊c-殼［5］以及模糊c-二次曲線［6］等新型算法.新算法把聚類原型從點擴展到了線、面、殼等幾何結(jié)構(gòu)，把模糊聚類的應(yīng)用范圍從簡單的模式分類拓寬到基元檢測、曲線擬合等眾多領(lǐng)域.作為上述算法的集成和統(tǒng)一，最近提出了一種多類原型模糊聚類算法［7］，該算法中聚類原型不再是單一的形式，而是多類原型的混合，因此可以同時檢測呈不同幾何結(jié)構(gòu)分布的樣本子集.
　　然而上述各類算法大都依賴于聚類原型和聚類數(shù)的先驗知識，即必須事先已知樣本子集分布的幾何結(jié)構(gòu)及類別數(shù)，這限制了它們在生產(chǎn)自動化中的應(yīng)用.此外，這些算法均采用局部搜索技術(shù)，因此對初始化極為敏感，即使在聚類原型和聚類數(shù)給定的情況下，如果種子點選擇不當，也很容易陷于局部極值點，得不到最佳分類.
　　針對以上限制及缺點，本文提出了一種結(jié)合數(shù)學形態(tài)學、圖像描述及曲線擬合等技術(shù)的初始化方法.本方法不僅可以估計各類原型的位置，而且能夠自動獲取原型的結(jié)構(gòu)參數(shù)及數(shù)目，從而使聚類分析成為真正的機器自動學習算法.
　　以下，第二部分簡要介紹多類原型的模糊聚類分析，第三部分引入幾個數(shù)學形態(tài)學算子，第四部分給出聚類原型參數(shù)的自動獲取方法，第五部分為實驗結(jié)果及討論，最后是結(jié)論及后續(xù)工作.

二、多類原型的模糊聚類
　　多類原型的模糊聚類［7］是傳統(tǒng)模糊聚類的集成和統(tǒng)一，在這種分析方法中聚類原型不再是單一的形式，而是呈現(xiàn)多樣化.它不僅能完成現(xiàn)有各種聚類算法的功能，即檢測單一模式樣本子集，而且可以用來分析呈多種幾何結(jié)構(gòu)分布的特征集.除模式分類外，該算法還能實現(xiàn)基元檢測、物體識別等多種功能.
　　設(shè)x為Rp中的一個子集x={x1,x2,…,xn}Rp,xk=(xk1，xk2，…，xkp)∈Rp稱為特征矢量或模式矢量，xkj為觀測樣本xk的第j個特征.設(shè)Vcn是所有c×n階的矩陣集合，c為［2,n)區(qū)間內(nèi)的整數(shù)，則x的模糊c-劃分空間為：

　(1)

其中U矩陣的元素uik表示第k個樣本xk屬于第i個聚類的程度.設(shè)B={β1，β2，…,βc}為聚類原型集，其中為第i個模糊子集的模式原型，則多類原型的模糊劃分可以通過極小化如下的目標函數(shù)而得到：

　(2)

式中，m為模糊指數(shù)，m越大分類的模糊度越大，當時，退化為硬聚類算法；D(xk,βi)為樣本xk與第i個原型βi的相似性測度，當c個原型βi(i=1,…,c)均為RP空間中的點、線或殼時，該算法分別退化為模糊c-均值、模糊c-線或模糊c-殼聚類.
　　Jm(U,B)通過U與B的迭代沿著一子序列而逐漸收斂到初始B(0)附近的極值點或鞍點［8］，由于Jm(U,B)是一個多峰的復(fù)雜函數(shù)，因此原型B的初始化就變得尤為重要，一個隨機的初始化，可能導(dǎo)致分類的錯誤.而如果初始化B(0)落到包含有最佳B*的收斂子序列中，則能保證Jm(U,B)最終收斂到全局最優(yōu)點.此外，對于多類原型的模糊聚類算法必須事先已知原型的類型及相應(yīng)的數(shù)目，否則將無法得到正確的聚類結(jié)果.因此需要有效的初始化方法來提供有關(guān)聚類原型的信息.

三、數(shù)學形態(tài)學的基本算子
　　為了設(shè)計一種多類原型模糊聚類的初始化方法，需要引入數(shù)學形態(tài)學中的幾個基本算子和基本操作.首先介紹幾個習慣表示符，令帶有下劃線的大寫字母“A，B，…”表示N維離散空間中的二值點集；集合中的點定義為N維整數(shù)坐標的矢量，用相應(yīng)的大寫字母表示為“A,B，…”；并用帶有下標的小寫字母“a1，a2,…,aN”表示矢量A的各個分量，比如：A=(a1,a2,…,an,…,aN)T.
　　1.膨脹與腐蝕算子
　　設(shè)X，S，…ZN，且元素X=(x1,x2,…,xn,…,xN)T和S=(s1,s2,…,sn,…,sN)T都是具有離散坐標的N元組，如果用

(X)s={T∈ZN|T=X+S,X∈X}　(3)

表示點集X平移S，則X被S膨脹可基于Minkowski加法而定義為：

　(4)

同樣，基于Minkowski減法可以定義S對X的腐蝕操作

　(5)

其中S稱為結(jié)構(gòu)元素.
　　2.開、閉運算
　　在實際中，膨脹、腐蝕算子很少單獨使用，而是相互結(jié)合成對使用，這就是常見的數(shù)學形態(tài)學中的開運算和閉運算.設(shè)我們用XS表示集合X相對于S的結(jié)構(gòu)開，則開運算Xs為集合X相對于結(jié)構(gòu)元素S先腐蝕后膨脹的結(jié)果，即有

　(6)

開運算具有平滑功能，它能消除集合X幾何結(jié)構(gòu)中孤立的小點，毛刺和小橋，使XS變成一個邊緣相對光滑、簡單的結(jié)構(gòu).
　　由對偶性，集合X相對于S的結(jié)構(gòu)閉XS，即為先膨脹后腐蝕的結(jié)果，有

　(7)

閉運算也具有過濾功能，能填平集合X幾何結(jié)構(gòu)中的孔洞、彌補小裂縫.
　　實驗中，我們發(fā)現(xiàn)對集合X先相對于S作膨脹操作，然后再作開運算就不再改變其大體結(jié)構(gòu).因此下一節(jié)中我們將構(gòu)造開、閉運算的鏈式操作來刪除待聚類數(shù)據(jù)集中的細節(jié)，而保留模式子集結(jié)構(gòu)的總體形狀，以便獲取聚類原型的有關(guān)信息.

四、聚類原型及聚類數(shù)的自動獲取
　　在呈多類原型分布的模式集中，特征矢量在特征空間中的分布可用如下模型描述：

xk=βi+εi，xk∈ci,εi∈N(0,σi)　(8)

其中xk為特征矢量；ci為矢量xk最貼近的模式子集，即有uik=maxcj=1uij;βi為模式子集或聚類ci的原型；N(0,σi)表示高斯分布.也就是說，貼近于同一個聚類的矢量按照正態(tài)分布模式聚集在原型的附近，σi反映了其聚散程度.由高斯分布的特點可知，聚類ci中的樣本絕大多數(shù)都散布在鄰域Δ內(nèi)，因此定義聚類ci的厚度為3σi.基于樣本分布的這些形態(tài)特征，可以借助形態(tài)處理來提取聚類原型信息.
　　一個聚類原型信息自動獲取的流程可由圖1所示的框圖來表示：