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

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

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

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

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

　(1)

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

　(2)

式中，m為模糊指數，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)是一個多峰的復雜函數，因此原型B的初始化就變得尤為重要，一個隨機的初始化，可能導致分類的錯誤.而如果初始化B(0)落到包含有最佳B*的收斂子序列中，則能保證Jm(U,B)最終收斂到全局最優點.此外，對于多類原型的模糊聚類算法必須事先已知原型的類型及相應的數目，否則將無法得到正確的聚類結果.因此需要有效的初始化方法來提供有關聚類原型的信息.

三、數學形態學的基本算子
　　為了設計一種多類原型模糊聚類的初始化方法，需要引入數學形態學中的幾個基本算子和基本操作.首先介紹幾個習慣表示符，令帶有下劃線的大寫字母“A，B，…”表示N維離散空間中的二值點集；集合中的點定義為N維整數坐標的矢量，用相應的大寫字母表示為“A,B，…”；并用帶有下標的小寫字母“a1，a2,…,aN”表示矢量A的各個分量，比如：A=(a1,a2,…,an,…,aN)T.
　　1.膨脹與腐蝕算子
　　設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稱為結構元素.
　　2.開、閉運算
　　在實際中，膨脹、腐蝕算子很少單獨使用，而是相互結合成對使用，這就是常見的數學形態學中的開運算和閉運算.設我們用XS表示集合X相對于S的結構開，則開運算Xs為集合X相對于結構元素S先腐蝕后膨脹的結果，即有

　(6)

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

　(7)

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

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

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

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