周治平 朱書偉 張道文

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院 江蘇無錫 214122) (zzp@jiangnan.edu.cn)

?

分類數(shù)據(jù)的多目標(biāo)模糊中心點聚類算法

周治平 朱書偉 張道文

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院 江蘇無錫 214122) (zzp@jiangnan.edu.cn)

針對傳統(tǒng)面向分類屬性數(shù)據(jù)的聚類算法大多是對單一指標(biāo)優(yōu)化而存在的局限性，將類內(nèi)和類間信息同時引入到優(yōu)化過程中，結(jié)合多目標(biāo)優(yōu)化算法與模糊中心點聚類，提出一種新穎的多目標(biāo)模糊聚類算法.與傳統(tǒng)的基于遺傳算法的混合聚類方法不同的是，采用模糊隸屬度對染色體進(jìn)行編碼，同時優(yōu)化2個相對的聚類目標(biāo)函數(shù)獲得一組最優(yōu)解集，并且采用了一種提前終止準(zhǔn)則判斷算法是否達(dá)到穩(wěn)定狀態(tài)并停止操作，以減少不必要的計算開銷.為了進(jìn)一步提高算法的效率，通過采樣子集計算出相應(yīng)的模糊中心點作為類的表達(dá)，然后以這些模糊中心點計算出全體樣本的隸屬度矩陣即可獲得最終的聚類結(jié)果.對10種數(shù)據(jù)集的實驗結(jié)果表明:所提方法在聚類精度和穩(wěn)定性方面優(yōu)于當(dāng)前最新的多目標(biāo)聚類算法，且計算效率也獲得較大的提升.

分類數(shù)據(jù)；聚類；多目標(biāo)優(yōu)化；模糊中心點；最優(yōu)解集

聚類分析是一種無監(jiān)督的數(shù)據(jù)分析方法，在數(shù)據(jù)挖掘、模式識別、信息檢索等領(lǐng)域應(yīng)用十分廣泛.數(shù)據(jù)的屬性類型通常包括數(shù)值屬性、分類屬性以及混合屬性，其中數(shù)值型數(shù)據(jù)可直接采用相應(yīng)的距離度量探索其幾何特性，且現(xiàn)有的大部分聚類算法都是對數(shù)值型數(shù)據(jù)進(jìn)行分析.然而，對于屬性值為離散型的分類數(shù)據(jù)，無法通過距離度量的方式進(jìn)行分析，近來關(guān)于分類數(shù)據(jù)聚類算法的研究得到越來越多學(xué)者的關(guān)注.

最經(jīng)典的分類數(shù)據(jù)聚類算法是對K-means原型進(jìn)行拓展的K-modes(KMd)算法[1]及其模糊版本的fuzzyK-modes(FKMd)算法[2]，隨后Kim等人[3]針對FKMd中硬中心點的不足，提出基于模糊類中心集的模糊中心點(fuzzy centroids, Fcentroids)的算法.由于K-modes型算法具有處理大數(shù)據(jù)集的能力，現(xiàn)已成為分析分類數(shù)據(jù)最廣泛的聚類算法.然而，K-modes中采用簡單匹配相異性度量無法有效區(qū)分不同的屬性值，一些更有效的相異性度量方式[4-7]相繼被提出.為了能夠有效避免局部最優(yōu)，Gan等人[8]提出基于遺傳算法的GA-FKM(genetic algorithm fuzzyK-modes)；Maulik等人[9]結(jié)合改進(jìn)的差分進(jìn)化算法與模糊c中心點(c-medoids)算法提出一種新穎的混合聚類算法.考慮到聚類過程中不同屬性的重要性不同，Chan等人[10]提出一種屬性加權(quán)聚類算法.Bai等人[11]對其進(jìn)行拓展，提出一種混合屬性加權(quán)聚類算法，能夠有效地用于高維分類數(shù)據(jù).近來，他們針對傳統(tǒng)K-modes型算法僅考慮簇內(nèi)信息的不足，引入簇間信息建立了新的目標(biāo)函數(shù)分別提出模糊版本[12]和非模糊版本[13]的新算法.然而，在新的目標(biāo)函數(shù)中對平衡參數(shù)的取值仍然難以確定.

通常多目標(biāo)聚類算法能夠有效克服僅對單一指標(biāo)優(yōu)化的不足，同時兼顧多個聚類指標(biāo)且不引入新的參數(shù)，自提出以來得到了廣泛的研究.Mukhopadhyay等人[14]基于非支配排序遺傳算法(nondominated sorting genetic algorithm-Ⅱ, NSGA-Ⅱ)首次提出了面向分類數(shù)據(jù)的多目標(biāo)模糊聚類算法，對全局緊密度與模糊分離度2個指標(biāo)同時優(yōu)化，具有重要的指導(dǎo)意義.近來，Saha等人[15]采用改進(jìn)多目標(biāo)差分進(jìn)化算法提出了基于增量學(xué)習(xí)機(jī)制的多目標(biāo)聚類方法；Yang等人[16]基于NSGA-Ⅱ并采用模糊隸屬度的染色體編碼機(jī)制提出新穎的NSGA-FMC(non-dominated sorting genetic algorithm-fuzzy membership chromosome)，均能夠獲得更佳的聚類結(jié)果.此外，與多目標(biāo)聚類提出背景相近的聚類集成技術(shù)在分類數(shù)據(jù)中也得到了一定的關(guān)注，如一種基于鏈接的聚類集成方法[17]、基于粗糙集子空間的聚類集成方法[18]、基于集成的粗糙模糊集聚類算法[19]等.

現(xiàn)有的分類數(shù)據(jù)多目標(biāo)聚類算法都是以FKMd為原型，本文以一般情況下準(zhǔn)確度更高的Fcentroids為原型提出一種新穎的多目標(biāo)聚類算法.以最新提出的NSGA-FMC為基礎(chǔ)，將NSGA-Ⅱ融入Fcentroids以進(jìn)一步改善算法的性能.通過與NSGA-FMC及其他5種算法的實驗對比分析表明了本文算法在聚類準(zhǔn)確度與穩(wěn)定性方面的優(yōu)勢，并且其對模糊參數(shù)的敏感性相對較低，擁有較高的魯棒性.

1 傳統(tǒng)的分類數(shù)據(jù)聚類算法

1.1 FKMd聚類的概念

模糊聚類是一種軟劃分的聚類方法，即每個樣本未明確規(guī)定到某一個類，而是根據(jù)一個模糊隸屬度值uki(0≤uki≤1)確定某個樣本xi屬于第k個類的程度.經(jīng)典的FKMd算法的目標(biāo)函數(shù)為[2]

(1)

其中，m為模糊指數(shù)，一般m>1；ck為第k個mode的位置;D(ck,xi)為第i個數(shù)據(jù)與第k個mode之間的相異性度量，采用簡單匹配的度量方法：

(2)

模糊隸屬度uki表示了第i個數(shù)據(jù)隸屬于第k個類的程度，其更新過程如式(3)所示[2]：

(3)

此外，若modes中心ck(1≤k≤K)的第j(1≤j≤D)維屬性具有t個屬性值，則ckj的更新過程為[2]

(4)

通過更新隸屬度和modes中心使目標(biāo)函數(shù)F(U,C)的值不斷減小直至不再發(fā)生明顯變化則停止運(yùn)行，通過U求出每個點的最大隸屬度以確定其所屬的類別.由于K-modes型的聚類算法是以K-means為原型，同樣存在2個主要缺點：1)對初始modes的選取非常敏感；2)容易陷入局部最優(yōu)解.目前，關(guān)于初始modes值選取方面已取得了許多不錯的研究成果[20-22].

1.2 Fcentroids聚類的概念

Fcentroids算法是一種基于模糊集理論的聚類方式，其目標(biāo)函數(shù)的形式與式(1)相同，但與傳統(tǒng)的硬中心點不同的是，每個centroid的每一維屬性采用一個模糊集來表示，若第k個centroid向量為[3]

ck={ck1,ck2,…,ckD}, 1≤k≤K，

(5)

由式(5)可見模糊中心點的每一維屬性對應(yīng)一個集合，不再是一個確定的值，其相異性度量方式也隨之改變，定義為式(6):

(6)

(7)

此外，與FKMd不同的是這里不存在數(shù)據(jù)樣本與centroids相等的情況，因此uki的更新過程為[3]

(8)

除了上述內(nèi)容，F(xiàn)centroids的原理與FKMd基本相同，相對于后者其具有很高的穩(wěn)定性，但是它同樣存在陷于局部最優(yōu)的問題.目前相關(guān)的研究相對較少，Ji等人[23-24]分別基于模糊聚類和子空間聚類提出2種面向混合數(shù)據(jù)的改進(jìn)K-prototype算法模型，其目標(biāo)函數(shù)中以Fcentroids對分類屬性部分進(jìn)行分析.

2 基于多目標(biāo)進(jìn)化算法的模糊中心點聚類

多目標(biāo)優(yōu)化問題就是在決策向量空間中，均衡考慮具有對立性的多個指標(biāo)并獲得最優(yōu)解集.對于最小化問題而言，若2個決策向量分別為xk和xl，當(dāng)且僅當(dāng)?i∈{1,2,…,n}使得解f(xk)≤f(xl)，?j∈{1,2,…,n}使得解f(xk)

2.1 染色體編碼

由于MOFcentroids的centroids是由一組模糊集表示的，因此無法直接通過某個特定的屬性值代表其某一維屬性，即無法像文獻(xiàn)[9,14-15,25-27]中那樣基于聚類中心對染色體的基因位編碼.在文獻(xiàn)[8,16]中均采用的是基于模糊隸屬度的編碼方式，因此本文采用模糊隸屬度作為染色體的基因位.每個個體向量表示為x=(u11,u21,…,uK1,u12,u22,…,uK2,…,u1n,u2n,…,uKn)，可以看出它是K×n列的行向量，其中K為類數(shù)，n為數(shù)據(jù)的個數(shù)，所有數(shù)據(jù)的隸屬度必須滿足式(1)中約束條件.通過搜索到最佳的屬性權(quán)重向量的同時可以獲得較優(yōu)的centroids，并能夠得到相應(yīng)的聚類結(jié)果.在計算過程中需將每個染色體向量轉(zhuǎn)化為一個K行n列的矩陣以方便操作，模糊隸屬度矩陣為

(9)

2.2 目標(biāo)函數(shù)的選取

多目標(biāo)聚類算法的性能在很大程度上取決于目標(biāo)函數(shù)的選取，現(xiàn)有文獻(xiàn)中大部分選取2個目標(biāo)函數(shù)進(jìn)行優(yōu)化并且主要考慮的是劃分的緊密性和分離性的性能.本文中MOFcentroids的目標(biāo)函數(shù)并沒有采用文獻(xiàn)[14,16]的模糊緊密性與模糊分離性，而是選取F(U,C)和XB(Xie-Beni)指數(shù)，其中F(U,C)如式(1)所示.XB為結(jié)合類內(nèi)和類間信息的目標(biāo)函數(shù)，在現(xiàn)有的各種類型多目標(biāo)聚類算法[15,25-27]中已被證明非常有效，它的形式如式(10)所示，其分子部分與F(U,C)相同，分母部分n表示數(shù)據(jù)的個數(shù)，D(ci,ck)為第i個類與第k個類之間的相異度.

(10)

對于F(U,C)和XB，本文在計算D(ck,xi)時都采用的是式(6)的方式，但是其中的置信度并沒有根據(jù)式(7)確定，而是做了適當(dāng)調(diào)整[23-24]：

(11)

此外，XB分母中D(ci,ck)的計算為

(12)

2.3 染色體選擇

由于Fcentroids是一種相對比較穩(wěn)定的算法，而NSGA-FMC是以FKMd為基礎(chǔ)，本文算法對于某些數(shù)據(jù)集并不會像NSGA-FMC那樣產(chǎn)生包括較多最優(yōu)解的解集，因此NSGA-FMC中基于輪盤賭的選取方式無法滿足要求，這里仍然采用的是二進(jìn)制錦標(biāo)賽的選取方式.對所有的父代種群進(jìn)行非支配排序，其中互不支配的個體通過擁擠度距離判斷其優(yōu)先等級，若第i個染色體的非支配等級ir以及擁擠度距離id，則擁擠性比較算子n可定義為

如果irjd，則:

inj,

(13)

此外，由于在后續(xù)的內(nèi)容中需要采用文獻(xiàn)[8,16]中的輪盤賭選取方式，這里主要介紹其中的基于等級的評估函數(shù)[8,16]：

F(xi)=β(1-β)ir-1，

(14)

其中，xi為第i個染色體向量；β∈[0,1]為預(yù)定義的常數(shù)，用來表明算法的選擇強(qiáng)度.

2.4 交叉過程

當(dāng)所有染色體被選出后，需對其執(zhí)行交叉操作，與GA-FKM中的一步FKMd相類似，本文算法采用一步Fcentroids作為交叉算子，其過程為

fori=1 toNdo

根據(jù)式(9)將xi轉(zhuǎn)化為隸屬度矩陣Ut；

利用Ut并通過式(11)計算出矩陣ω即可確定所有的centroids；

利用ω表示的centroids并通過式(8)更新模糊隸屬度矩陣表示為Ut+1；

將Ut+1轉(zhuǎn)化為一個行向量獲得新的染色體;

end for

2.5 變異過程

在變異過程中，每個基因以概率Pmu發(fā)生變化：

fori=1 toNdo

染色體為xi=(u11,…,uK1,…,u1n,…,uKn)；

fors=1 tondo

產(chǎn)生一個在[0,1]內(nèi)的隨機(jī)數(shù)r；

ifr

產(chǎn)生K個在[0,1]內(nèi)隨機(jī)數(shù)v1s,v2s,…vKs；

end if

end for

end for

2.6 停止準(zhǔn)則

本文首先設(shè)置了最大迭代數(shù)作為停止判斷標(biāo)準(zhǔn)，需要注意的是雖然Fcentroids設(shè)置了最大迭代次數(shù)，但大多情況下會由于目標(biāo)函數(shù)值沒有明顯的降低而提前停止.同樣地，當(dāng)MOFcentroids運(yùn)行到一定階段時達(dá)到穩(wěn)定使其PF不會發(fā)生明顯的變化，若達(dá)到最大迭代次數(shù)才停止則會增加不必要的計算開銷.這里進(jìn)一步采用了一種對PF進(jìn)行動態(tài)評價的方法，分別計算每次迭代后PF所對應(yīng)的各目標(biāo)函數(shù)值的最優(yōu)值，若第t次迭代后分別為Fbest(t)和XBbest(t)，則Δπ1=Fbest(t)-Fbest(t+1)和Δπ2=XBbest(t)-XBbest(t+1)分別表示下一次迭代后各個目標(biāo)函數(shù)最優(yōu)值的變化程度，設(shè)定一個很小的閾值ε=10-4，若連續(xù)T1次迭代滿足Δπ1+Δπ2≤ε則可判斷PF已處于穩(wěn)定狀態(tài)，算法提前終止，本文將這種方法稱為提前終止準(zhǔn)則.

2.7 最終解的選取

當(dāng)多目標(biāo)聚類算法停止以后，需通過PS確定最終的聚類解，目前使用比較廣泛的方法主要有2種：1)通過聚類有效性指標(biāo)對PS中的每個解進(jìn)行評估并選取一個最優(yōu)解獲得聚類結(jié)果[25-26]；2)結(jié)合機(jī)器學(xué)習(xí)與聚類集成方法通過綜合PS中的所有解以確定最終的聚類結(jié)果[14-15,27]，目前具有更好的前景但也存在計算開銷大的問題.而在NSGA-FMC中提出了一種簡單高效的方法，由于其每一個非支配解可轉(zhuǎn)化為相應(yīng)的模糊隸屬度矩陣，通過每個數(shù)據(jù)對應(yīng)的最大隸屬度值即可確定其所屬的類別，將這些隸屬度值相加得到隸屬度總和，最后比較所有非支配解對應(yīng)的隸屬度總和并選取其中最大的值以確定聚類解.本文算法同樣采用的是基于模糊隸屬度的編碼方式，因此采用這種方法從PS中選取最終解.

2.8 算法具體流程

算法1. MOFcentroids算法.

Step1. 初始化當(dāng)前迭代次數(shù)Iter=0，最大迭代次數(shù)Tmax、種群規(guī)模N、聚類數(shù)K、模糊指數(shù)m、交叉概率Pc、變異概率Pmu，對于每個染色體從數(shù)據(jù)集中隨機(jī)選出K個數(shù)據(jù)確定初始的ck(1

Step2. 根據(jù)初始的置信度ω以及隸屬度矩陣U分別計算目標(biāo)函數(shù)F(U,C)和XB，并以n對種群進(jìn)行非支配排序.

Step3. 采用二進(jìn)制錦標(biāo)賽機(jī)制選出N個染色體分別執(zhí)行交叉、變異操作得到子代種群.

Step4. 對子代種群利用式(11)和式(8)分別更新ω以及U并計算相應(yīng)的F(U,C)和XB.

Step5. 執(zhí)行精英保留機(jī)制，將父代種群與子代種群混合，再次采用n對它們進(jìn)行非支配排序并從中選出前N個染色體作為下一次迭代的父代種群.

Step6. 判斷是否滿足提前終止準(zhǔn)則，若滿足則停止并輸出最優(yōu)解集，并轉(zhuǎn)Step8，否則轉(zhuǎn)Step7.

Step7.Iter=Iter+1，若Iter

Step8. 將每一個非支配解轉(zhuǎn)化為相應(yīng)的模糊隸屬度矩陣，計算最大隸屬度總和選出最終的聚類解.

此外，這里為了使初始時ck(1≤k≤K)每一維屬性對應(yīng)的屬性值都具有一定的代表性，在Step1中根據(jù)隨機(jī)選出的K個數(shù)據(jù)確定初始ck的規(guī)則如下：

(15)

2.9 基于采樣選取模糊類中心點

由于多目標(biāo)聚類算法的計算時間相對較長，除了提前終止準(zhǔn)則外，本文采用一種基于采樣的技術(shù)[28]以進(jìn)一步提高其計算效率，即聚類前從整體數(shù)據(jù)集X中隨機(jī)采樣n′個樣本X′，并用MOFcentroids計算出最能代表X′的centroids集合Θ′，其原理基于這樣的假設(shè)：如果采樣的X′能夠代表X中的數(shù)據(jù)點的統(tǒng)計分布，Θ′將會很好地逼近X的centroids集合Θ，結(jié)果是MOFcentroids在整個數(shù)據(jù)集上運(yùn)行.將Θ′與X帶入式(1)中計算出使其值最小的隸屬度矩陣U，這可以看作以Θ′作為Fcentroids的初始ck(1≤k≤K)，并執(zhí)行一步確定X的隸屬度矩陣U，通過U即可求出最終的聚類結(jié)果.實驗中發(fā)現(xiàn)，通過采樣方法獲得的Θ′接近于在整個數(shù)據(jù)集上獲得的Θ，當(dāng)采樣個數(shù)n′達(dá)到一定規(guī)模時不但沒有降低算法的聚類性能，還能夠有效提高其效率.需要注意的是部分屬性中的部分屬性值所占比例很少，本文中稱其為稀有屬性值，采樣可能無法獲得包含這些稀有屬性值的樣本，使得Θ′中不能夠包含全體數(shù)據(jù)集所有的ω.

為了分析稀有屬性值在聚類過程中的作用，對數(shù)據(jù)集Heart和Dermatology進(jìn)行分析，用dj(k)表示第k個屬性中的第j個屬性值.Heart包含2個類并擁有303個樣本和8個屬性，其中第4個屬性擁有3個屬性值分別用d1(4)，d2(4)，d3(4)表示，其個數(shù)分別為151，4，148，顯然其中的d2(4)為稀有屬性值，采用Fcentriods運(yùn)行后對各個類的置信度如表1所示.Dermatology包含6個類并擁有366個樣本和33個屬性，其中稀有屬性值包括個數(shù)分別為4，6，4的d1(1)，d4(23)，d4(30)等，采用Fcentriods行后對各個類的置信度如表2所示.由表1和表2可見各稀有屬性值的置信度在相應(yīng)屬性中均為最小，表明其對聚類的作用很小.另外，存在一些屬性值的作用是完全可以忽略的，將其稱為噪聲屬性值，如Dermatology的d2(6)只有1個，發(fā)現(xiàn)其置信度值非常小，在聚類前隨機(jī)選取第6個屬性的其他屬性值將其替換.

Table 1 The Confidence of Rare Attribute Value in Heart

Table 2 The Confidence of Partial Rare Attribute Value in Dermatology

(16)

(17)

然后計算缺失屬性值的置信度和新的置信度向量如式(18)，且需對新向量歸一化使元素的和為1.

(18)

需要說明的是在本文實驗中尚未遇到稀有屬性值的置信度較大的情況，按照算法原理，通常稀有屬性值的置信度相對較小，這里加以分析說明以更好地應(yīng)對實際問題中可能遇到的特殊情況.

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

3.1 實驗數(shù)據(jù)集

本文通過分類型人工數(shù)據(jù)生成器*http://www.datgen.com產(chǎn)生2個較高維的人工數(shù)據(jù)集500_50_3和1000_50_4，其中每個屬性均具有4個屬性值.選取UCI數(shù)據(jù)庫的8個常用的真實數(shù)據(jù)集Soybean，Zoo，Promotor，Heart，Votes，Dermatology，DNA，Mushroom進(jìn)行分析.其中，缺失屬性值和噪聲屬性值隨機(jī)選取相關(guān)屬性的其他屬性值替換，混合型的Heart只考慮其中的分類屬性部分.各數(shù)據(jù)集的相關(guān)特性如表3所示：

Table 3 The Feature of Experimental Datasets

3.2 聚類性能評估標(biāo)準(zhǔn)

聚類結(jié)果通過聚類準(zhǔn)確度(accuracy，Acc)和調(diào)整的蘭特指數(shù)(adjusted rand index,ARI)這2種指標(biāo)進(jìn)行評價.若用ai表示被正確分到第i個類中的目標(biāo)數(shù)量，n表示所有目標(biāo)的數(shù)量，則Acc的定義為

(19)

ARI將類別看成是樣本之間的一種關(guān)系，通過統(tǒng)計正確決策樣本對數(shù)來評價聚類算法的性能.若ni表示類i中數(shù)據(jù)點的個數(shù)，nj表示簇j中數(shù)據(jù)點的個數(shù)，nij表示同時在類i和簇j中的數(shù)據(jù)點的個數(shù)，則ARI如式(20)所示，其取值最大為1，且越大的值表明聚類的結(jié)果越好.

(20)

3.3 對比算法相關(guān)過程描述

本文算法與FKMd[2]，NgFKMd[29]，F(xiàn)centriods[3]，GAFcentriods(genetic algorithm fuzzy centriods)，NSGA-FMC[16]這5個算法的聚類性能進(jìn)行對比分析.NgKMd是由Ng等人[4]對KMd的簡單匹配方式進(jìn)行改進(jìn)的一種算法，由于本文均為模糊聚類算法，其模糊版本NgFKMd的相異性度量為

(21)

3.4 結(jié)果比較與分析

各算法通過MATLAB2010b編程運(yùn)行，計算機(jī)的硬件配置為：Intel Core P7450，CPU主頻為2.13 GHz，RAM為2 GB.對上述的5個算法以及本文算法MOFcentroids進(jìn)行分析，求出聚類性能指標(biāo)Acc和ARI.算法參數(shù)設(shè)置為：GAFcentriods與MOFcentriods的種群規(guī)模N=20，最大迭代數(shù)Tmax=40，此外T1=8，T2=10，而NSGA-FMC種群數(shù)取50，最大迭代數(shù)取50；所有GA型算法交叉概率均為Pc=0.8，變異概率Pmu=0.1.依據(jù)文獻(xiàn)[2]中的建議，本文中FKMd及NgFKMd的模糊指數(shù)為m=1.1，其他算法的模糊指數(shù)一般均為m=1.2，某些明顯具有更好效果的特殊取值在相關(guān)算法后標(biāo)明.Fcentriods的最大迭代次數(shù)Maxgen=50，F(xiàn)KMd和NgFKMd的最大迭代次數(shù)Maxgen=100，且目標(biāo)函數(shù)值不發(fā)生明顯變化則停止，此外，式(15)中的β=0.1.數(shù)據(jù)集Soybean，Promotor，Zoo的規(guī)模較小，本文中均未執(zhí)行采樣操作；對其余7個數(shù)據(jù)集均執(zhí)行采樣操作，且采樣規(guī)模均為n′=0.3n，以保證絕大部分屬性的屬性值都能被選取到，無法選取到的即為稀有屬性值.各算法分別運(yùn)行30次，記錄并計算出Acc和ARI的均值及標(biāo)準(zhǔn)差如表4所示，其中對每個數(shù)據(jù)的最優(yōu)指標(biāo)值加粗，且有多個最優(yōu)值時優(yōu)先標(biāo)明本文算法.為了更直觀地比較各算法結(jié)果的統(tǒng)計分布情況，各算法對10種數(shù)據(jù)集ARI指標(biāo)的箱線圖如圖1所示，并在圖1中標(biāo)明均值.

Table 4 The Experimental Results of All Algorithms

Continued (Table 4)

Fig. 1 Boxplot of ARI values for different algorithms executed on the 10 datasets.

根據(jù)表4中的實驗結(jié)果，首先比較Fcentriods與FKMd的各項指標(biāo)值可以發(fā)現(xiàn)Fcentriods在聚類準(zhǔn)確度與穩(wěn)定性方面均具有較明顯的優(yōu)勢，這也成為了本文算法能夠獲得比較滿意結(jié)果的原因之一.由于Fcentriods對Soybean的聚類指標(biāo)已達(dá)到最優(yōu)無提升空間，對Votes和Mushroom的聚類指標(biāo)也較高以致相關(guān)改進(jìn)算法難以獲得提升，這里可見本文算法對較小數(shù)據(jù)集和較大數(shù)據(jù)集均具有良好的聚類性能.對于數(shù)據(jù)集500_50_3，1000_50_4，Zoo，Promotor，Heart，Dermatology，DNA，本文算法相對于Fcentriods的Acc和ARI均具有比較明顯的提升.其中可以發(fā)現(xiàn)尤其對2個人工數(shù)據(jù)集的提升效果非常明顯，對于Acc分別提升了21.1%，26.2%；對于ARI分別提升了32.2%，20.47%.這是由于Fcentriods算法對這2個數(shù)據(jù)集的性能很不穩(wěn)定，對于500_50_3能夠獲得Acc指標(biāo)的最大值為0.70，最小值為0.34；對于1000_50_4能夠獲得Acc指標(biāo)的最大值為0.86，最小值為0.26，因此其標(biāo)準(zhǔn)差較大分別為0.163和0.233.融入單目標(biāo)和多目標(biāo)進(jìn)化算法之后均使其穩(wěn)定性獲得了較大的提升，有效改善了算法的聚類性能.而算法FKMd以及相應(yīng)的2種改進(jìn)算法對這2個人工數(shù)據(jù)集幾乎是無效的，其原因值得進(jìn)一步研究.在UCI的真實數(shù)據(jù)集中，3種FKMd型算法對數(shù)據(jù)DNA均可看作無效，且對Promotor僅獲得很小的ARI值(對于NgFKMd和NSGA-FMC甚至為負(fù)數(shù)).Fcentriods算法對這2個數(shù)據(jù)集均具有一定的優(yōu)勢，不過其對DNA的Acc值雖然為0.501，高于FKMd的0.388，而ARI值僅為0.002，低于FKMd，這里表明采用多個指標(biāo)的必要性，本文算法同時對這2個指標(biāo)提升至0.528和0.116.進(jìn)一步比較可見，NSGA-FMC的性能相對于FKMd有顯著的提高，且相對于NgFKMd也有一定的提高.而本文算法對于各個數(shù)據(jù)集的Acc和ARI均高于NSGA-FMC，這也間接體現(xiàn)了Fcentriods相對于FKMd的優(yōu)勢.綜合對比可見，除了少數(shù)情況外，本文算法的聚類指標(biāo)值均為最大并已在表4中加粗標(biāo)明，并且對多個數(shù)據(jù)集的標(biāo)準(zhǔn)差也很小，表明其具有較高的穩(wěn)定性，因此可以判斷出其具有最佳的聚類性能.

由圖1可見，F(xiàn)centriods算法對2種人工數(shù)據(jù)集的上下限范圍較大，與上文所提到的穩(wěn)定性差相對應(yīng)，并且其對數(shù)據(jù)集Soybean，Heart，Votes和Mushroom的上下限均相等，表現(xiàn)出非常高的穩(wěn)定性.雖然本文算法對Heart和Mushroom的穩(wěn)定性有較小的下降，但更高的上限值表明多目標(biāo)聚類算法具有搜索到更精確解的能力.相對于Fcentriods而言，本文算法明顯提高了對Zoo和Promotor的指標(biāo)，而GAFcentriods對它們的聚類指標(biāo)比Fcentriods更差，這里體現(xiàn)出將多目標(biāo)引入到聚類過程中的優(yōu)勢.對于Dermatology和DNA，本文算法以及GAFcentriods的結(jié)果均獲得了明顯的改善.此外，值得注意的是圖1中NSGA-FMC對Zoo的ARI均值與本文算法很接近，但是本文算法的Acc均值0.892明顯高于NSGA-FMC的0.866，進(jìn)一步表明了采用多個聚類評估指標(biāo)的必要性.

由于算法Fcentriods對模糊指數(shù)m的選取比較敏感，這里分別取m為1.1，1.2，1.3，將Fcentriods和MOFcentriods對各數(shù)據(jù)集分別執(zhí)行30次并求出Acc的均值及標(biāo)準(zhǔn)差記錄至表5中.此外，由于2種算法對Votes的Acc值始終為0.881，對Soybean除Fcentroids在m=1.1時的Acc均值為0.979，其余均為1.000，表5中未給出相應(yīng)的結(jié)果.由表5可見，F(xiàn)centriods受m值的影響很明顯，尤其是對數(shù)據(jù)集Zoo，Promotor，Dermatology，取值不當(dāng)會使算法性能很差，因此魯棒性較差.本文通過先驗的類標(biāo)簽信息可確定Fcentriods對于不同數(shù)據(jù)集的最佳m值，如表4中對Zoo的指標(biāo)值是取m=1.1的結(jié)果，而現(xiàn)實的數(shù)據(jù)沒有先驗信息.本文算法在不同m值下均能夠獲得較高的Acc值，顯示了較好的魯棒性.因此，在Fcentriods中融入多目標(biāo)進(jìn)化算法能夠有效解決對參數(shù)m敏感的問題，本文算法始終使用的是m=1.2.

此外，在MATLAB編程環(huán)境下，NgFKMd改進(jìn)的相異性度量與Fcentriods基于置信度的相異性度量均需循環(huán)操作比較每一維而無法簡化，NSGA-FMC中簡單匹配相異性度量可通過MATLAB語句簡化以提高效率，即只需執(zhí)行一步計算數(shù)據(jù)向量與類中心向量不相等元素的長度作為相異性距離.因此，本文僅通過時間復(fù)雜度對各算法進(jìn)行比較，用K表示類數(shù)，n表示樣本個數(shù)(n′表示采樣樣本個數(shù))，D表示屬性維數(shù)，s表示各算法的最大迭代數(shù)，N表示種群個數(shù).由于各算法的時間計算主要依賴于每次迭代中類中心和劃分矩陣的更新，F(xiàn)KMd更新類中心和劃分矩陣的時間復(fù)雜度[2]分別為O(KnM)和O(knD)，其中M為所有屬性值個數(shù)總和，故其總體時間復(fù)雜度為O(Kn(D+M)s)；Fcentriods更新模糊類中心和劃分矩陣的時間復(fù)雜度[3]分別為O(KnD)和O(KTnD)，其中T=max(nl)，nl(1≤l≤D)為D維屬性中各自包含的屬性值的個數(shù)，故其總體時間復(fù)雜度為O(sKnD(T+1)).由于幾種混合聚類算法的交叉算子均執(zhí)行一步基算法，變異算子的計算可以忽略，故NSGA-FMC的總體時間復(fù)雜度為O(s(1+Pc)Kn(D+M)N)；GAFcentriods和MOFcentriods在采樣子集上的總體時間復(fù)雜度為O(s(1+Pc)Kn′D(T+1)N).本文算法的時間復(fù)雜度與類數(shù)、樣本數(shù)及屬性數(shù)均成線性關(guān)系，因此能夠用于分析較大數(shù)據(jù)集.需要注意的是多數(shù)情況下無需達(dá)到最大迭代數(shù)即停止，如本文算法最少迭代10次左右便提前終止.Fcentriods和MOFcentriods對各數(shù)據(jù)集的平均運(yùn)行時間的對比如表6所示：

Table 5 The Acc of Fcentroids and MOFcentroids with Different Values of m

Table 6 Average Runtime of Fcentroids and MOFcentroids

表6中，對數(shù)據(jù)集Soybean，Zoo，Promotor均未執(zhí)行采樣，其他7個數(shù)據(jù)集均給出執(zhí)行采樣和不執(zhí)行采樣的平均運(yùn)行時間，并且在不同情況下提前終止時的迭代數(shù)不一致導(dǎo)致前者的運(yùn)行時間并不一定是后者的0.3.在Fcentriods運(yùn)行中其目標(biāo)函數(shù)值只要相對于前一次迭代無明顯變化即停止，而本文算法連續(xù)T1=8次迭代PF的最優(yōu)值無明顯變化才會停止.由表6可見，本文算法的運(yùn)行時間均未達(dá)到Fcentriods的(1+Pc)N倍.當(dāng)不執(zhí)行采樣操作時本文算法的運(yùn)行時間相對較長，尤其對較大數(shù)據(jù)集DNA(維數(shù)也較高)和Mushroom的時間非常長，這也是現(xiàn)有的多目標(biāo)聚類算法[14-16,25-27]均存在的問題.如在文獻(xiàn)[16]中給出NSGA-FMC在未考慮任何時間效率方面的優(yōu)化時對規(guī)模并不大的Soybean，Zoo，Votes的運(yùn)行時間分別為76.56 s，220.69 s，191.52 s，而在文獻(xiàn)[14]中給出對這3個數(shù)據(jù)集的運(yùn)行時間甚至分別達(dá)到了120.49 s，530.47 s，780.28 s.本文通過采樣以及提前終止準(zhǔn)則能夠較大程度地縮短時間，并且不會降低算法的聚類性能，硬件配置并不如文獻(xiàn)[16]，能夠獲得較滿意的結(jié)果，MOFcent-riods較Fcentriods的最大倍數(shù)僅為對數(shù)據(jù)集Votes的8倍.此外，表6中均為執(zhí)行提前終止準(zhǔn)則的結(jié)果，為了分析其對算法運(yùn)行效率的提升，圖2給出了不執(zhí)行提前終止準(zhǔn)則(Termination1)和執(zhí)行提前終止準(zhǔn)則(Termination2)下的運(yùn)行時間對比.

Fig. 2 The average runtime of MOFcentroids for different algorithms with two kinds of terminations.圖2 MOFcentroids對各數(shù)據(jù)集采用2種不同終止準(zhǔn)則的平均運(yùn)行時間

由圖2可見，對于所有數(shù)據(jù)集，提前終止準(zhǔn)則均有效地減少了運(yùn)行時間，對于Promotor，1000_50_4，DNA，Mushroom這4個數(shù)據(jù)集而言，Termination 1比Termination 2的時間高了接近3倍，表明其迭代10多次即停止，若迭代40次則增加了大量不必要的計算開銷，從而影響了算法的運(yùn)行效率.

3.5 統(tǒng)計顯著性分析

為了驗證本文算法所獲得的更佳聚類結(jié)果是統(tǒng)計顯著的，本文采用t-test統(tǒng)計顯著性測試進(jìn)行分析，并在5%的顯著性水平下計算出相應(yīng)的p-value記錄到表7中.這里對指標(biāo)值A(chǔ)cc進(jìn)行分析，比較本文算法與其他算法之間的p-values.首先，本文算法與其他算法之間的Acc不存在統(tǒng)計顯著性差異作為零假設(shè)，那么備擇假設(shè)即為在它們之間存在顯著性差異.從表7可見,幾乎所有的p-values均小于0.05，并且大部分情況下遠(yuǎn)小于該值，這表明零假設(shè)不成立，因此接受備擇假設(shè)，即本文算法的Acc結(jié)果與其他算法間存在統(tǒng)計顯著性差異而不是偶然發(fā)生的，類似的結(jié)果同樣存在于ARI中.此外，對于GAFcentroids算法出現(xiàn)了比較多的統(tǒng)計不顯著現(xiàn)象是符合規(guī)律的，因為對于這些不顯著的數(shù)據(jù)集，其改進(jìn)作用與本文算法比較相近，從表4和圖1的結(jié)果可以看出兩者的結(jié)果較接近，具有相似的統(tǒng)計分布.但是，GAFcentroids通過唯一的最優(yōu)解確定聚類結(jié)果，而本文算法從非支配解集中確定聚類結(jié)果，因此其性能更可靠，從而對各數(shù)據(jù)集均能夠獲得較滿意的聚類結(jié)果，體現(xiàn)出采用多目標(biāo)優(yōu)化的優(yōu)勢.

Table 7 p-value Produced by t-test For Acc

4 結(jié)束語

本文將多目標(biāo)優(yōu)化理論引入到分類數(shù)據(jù)聚類算法Fcentriods中，提出一種新穎的多目標(biāo)模糊中心點聚類算法MOFcentriods.通過與傳統(tǒng)的單目標(biāo)聚類算法以及目前最新的多目標(biāo)聚類算法NSGA-FMC的實驗對比，表明本文算法在聚類準(zhǔn)確性與穩(wěn)定性方面具有較高的優(yōu)勢，且其魯棒性也較高.與此同時，針對多目標(biāo)聚類算法通常時間較長的問題，本文采用一種基于采樣的方法，在能夠代表數(shù)據(jù)點統(tǒng)計分布的樣本子集上獲得逼近整體數(shù)據(jù)集的聚類表達(dá)，有效提高了算法的效率.不過，由于多目標(biāo)聚類算法在時間方面高于傳統(tǒng)的聚類算法，不適用于處理規(guī)模很大的數(shù)據(jù)集.并且，由于分類數(shù)據(jù)中屬性為離散型，若在聚類迭代過程中執(zhí)行采樣將使算法無法順利執(zhí)行，而對于屬性為連續(xù)型的數(shù)值數(shù)據(jù)則不會產(chǎn)生相應(yīng)的問題，接下來可結(jié)合聚類過程中的采樣以進(jìn)一步研究能夠有效面向較大規(guī)模數(shù)值數(shù)據(jù)的多目標(biāo)聚類算法.

[1]Huang Z. Extensions to thek-means algorithm for clustering large data sets with categorical values[J]. Data Mining and Knowledge Discovery, 1998, 2(3): 283-304

[2]Huang Z, Ng M K. A fuzzyk-modes algorithm for clustering categorical data[J]. IEEE Trans on Fuzzy Systems, 1999, 7(4): 446-452

[3]Kim D W, Lee K H, Lee D. Fuzzy clustering of categorical data using fuzzy centroids[J]. Pattern Recognition Letters, 2004, 25(11): 1263-1271

[4]Ng M K, Li M J, Huang J Z, et al. On the impact of dissimilarity measure ink-modes clustering algorithm[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2007, 29(3): 503-507

[5]Liang Jiye, Bai Liang, Cao Fuyuan.K-modes clustering algorithm based on a new distance measure[J]. Journal of Computer Research and Development, 2010, 47(10): 1749-1755 (in Chinese)

(梁吉業(yè), 白亮, 曹付元. 基于新的距離度量的K-Modes聚類算法[J]. 計算機(jī)研究與發(fā)展, 2010, 47(10): 1749-1755)

[6]He Zengyou, Xu Xiaofei, Deng Shengchun. Attribute value weighting ink-modes clustering[J]. Expert Systems with Applications, 2011, 38(12): 15365-15369

[7]Cao Fuyuan, Liang Jiye, Li Deyu, et al. A dissimilarity measure for thek-modes clustering algorithm[J]. Knowledge-Based Systems, 2012, 26: 120-127

[8]Gan G, Wu J, Yang Z. A genetic fuzzyk-modes algorithm for clustering categorical data[J]. Expert Systems with Applications, 2009, 36(2): 1615-1620

[9]Maulik U, Bandyopadhyay S, Saha I. Integrating clustering and supervised learning for categorical data analysis[J]. IEEE Trans on Systems, Man and Cybernetics, Part A: Systems and Humans, 2010, 40(4): 664-675

[10]Chan E Y, Ching W K, Ng M K, et al. An optimization algorithm for clustering using weighted dissimilarity measures[J]. Pattern Recognition, 2004, 37(5): 943-952

[11]Bai Liang, Liang Jiye, Dang Chuangyin, et al. A novel attribute weighting algorithm for clustering high-dimensional categorical data[J]. Pattern Recognition, 2011, 44(12): 2843-2861

[12]Bai Liang, Liang Jiye, Dang Chuangyin, et al. A novel fuzzy clustering algorithm with between-cluster information for categorical data[J]. Fuzzy Sets and Systems, 2013, 215: 55-73

[13]Bai Liang, Liang Jiye. Thek-modes type clustering plus between-cluster information for categorical data[J]. Neurocomputing, 2014, 133: 111-121

[14]Mukhopadhyay A, Maulik U, Bandyopadhyay S. Multiobjective genetic algorithm-based fuzzy clustering of categorical attributes[J]. IEEE Trans on Evolutionary Computation, 2009, 13(5): 991-1005

[15]Saha I, Maulik U. Incremental learning based multiobjective fuzzy clustering for categorical data[J]. Information Sciences, 2014, 267: 35-57

[16]Yang C L, Kuo R, Chien C H, et al. Non-dominated sorting genetic algorithm using fuzzy membership chromosome for categorical data clustering[J]. Applied Soft Computing, 2015, 30: 113-122

[17]Iam-On N, Boongeon T, Garrett S, et al. A link-based cluster ensemble approach for categorical data clustering[J]. IEEE Trans on Knowledge and Data Engineering, 2012, 24(3): 413-425

[18]Can Gao, Pedrycz W, Miao Duoqian. Rough subspace-based clustering ensemble for categorical data[J]. Soft Computing, 2013, 17(9): 1643-1658

[19]Saha I, Sarkar J P, Maulik U. Ensemble based rough fuzzy clustering for categorical data[J]. Knowledge-Based Systems, 2015, 77: 114-127

[20]Cao Fuyuan, Liang Jiye, Bai Liang. A new initialization method for categorical data clustering[J]. Expert Systems with Applications, 2009, 36(7): 10223-10228

[21]Bai Liang, Liang Jiye, Dang Chuangyin, et al. A cluster centers initialization method for clustering categorical data[J]. Expert Systems with Applications, 2012, 39(9): 8022-8029

[22]Khan S S, Ahmad A. Cluster center initialization algorithm fork-modes clustering[J]. Expert Systems with Applications, 2013, 40(18): 7444-7456

[23]Ji Jinchao, Pang Wei, Zhou Chunguang, et al. A fuzzyk-prototype clustering algorithm for mixed numeric and categorical data[J]. Knowledge-Based Systems, 2012, 30: 129-135

[24]Ji Jinchao, Bai Tian, Zhou Chunguang, et al. An improvedk-prototypes clustering algorithm for mixed numeric and categorical data[J]. Neurocomputing, 2013, 120: 590-596

[25]Bandyopadhyay S, Maulik U, Mukhopadhyay A. Multiobjective genetic clustering for pixel classification in remote sensing imagery[J]. IEEE Trans on Geoscience and Remote Sensing, 2007, 45(5): 1506-1511

[26]Saha I, Maulik U, Plewczynski D. A new multi-objective technique for differential fuzzy clustering[J]. Applied Soft Computing, 2011, 11(2): 2765-2776

[27]Ma Ailong, Zhong Yanfei, Zhang Liangpei. Adaptive multiobjective memetic fuzzy clustering algorithm for remote sensing imagery[J]. IEEE Trans on Geoscience and Remote Sensing, 2015, 53(8): 4202-4217

[28]Ng R T, Han Jiawei. Clarans: A method for clustering objects for spatial data mining[J]. IEEE Trans on Knowledge and Data Engineering, 2002, 14(5): 1003-1016

[29]Ng M K, Jing Liping. A new fuzzyk-modes clustering algorithm for categorical data[J]. International Journal of Granular Computing, Rough Sets and Intelligent Systems, 2009, 1(1): 105-119

Zhou Zhiping, born in 1962. PhD, professor in the School of Internet of Things Engineering, Jiangnan University. His main research interests include intelligent detection, information safety, image processing.

Zhu Shuwei, born in 1990. Master from Jiangnan University. Student member of China Computer Federation. His main research interests include pattern recognition and data mining (zswjiang@163.com).

Zhang Daowen, born in 1989. Master candidate in Jiangnan University. Student member of China Computer Federation. His main research interests include data mining (zdwjndx@gmail.com).

Multiobjective Clustering Algorithm with Fuzzy Centroids for Categorical Data

Zhou Zhiping, Zhu Shuwei, and Zhang Daowen

(SchoolofInternetofThingsEngineering,JiangnanUniversity,Wuxi,Jiangsu214122)

It has been shown that most traditional clustering algorithms for categorical data that only optimize a single criteria suffer from some limitations, thus a novel multiobjective fuzzy clustering is proposed, which simultaneously considers within-cluster and between-cluster information. The lately reported algorithms are all based onK-modes, and the more accurate algorithm fuzzy centroids is utilized as the base algorithm to design the proposed method. Fuzzy membership is used as chromosome that is different from traditional genetic based hybrid algorithms, and a set of optimal clustering solutions can be produced by optimizing two conflicting objectives simultaneously. Meanwhile, a termination criterion in advance which can reduce unnecessary computing cost is used to judge whether the algorithm is steady or not. To further improve the efficiency of the proposed method, fuzzy centroids can be calculated using a subset of the dataset, and then the membership matrix can be calculated by these centroids to obtain the final clustering result. The experimental results of 10 datasets show that the clustering accuracy and stability of the proposed algorithm is better than the state of art multiobjective algorithm, and also the computing efficiency is improved to a large extern.

categorical data; clustering; multiobjective optimization; fuzzy centroids; Pareto-optimal solutions

2015-06-10；

2015-12-22

國家自然科學(xué)基金項目(61373126)；江蘇省自然科學(xué)基金項目(BK20131107)；江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金-前瞻性聯(lián)合研究基金項目(BY2013015-33)

TP181

This work was supported by the National Natural Science Foundation of China (61373126), the Natural Science Foundation of Jiangsu Province of China (BK20131107), and the Cooperative Industry-Academy-Research Innovation Foundation of Jiangsu Province of China (BY2013015-33).