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

周治平 朱書偉 張道文

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

?

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

周治平 朱書偉 張道文

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

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

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

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

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

通常多目標(biāo)聚類算法能夠有效克服僅對(duì)單一指標(biāo)優(yōu)化的不足，同時(shí)兼顧多個(gè)聚類指標(biāo)且不引入新的參數(shù)，自提出以來(lái)得到了廣泛的研究.Mukhopadhyay等人[14]基于非支配排序遺傳算法(nondominated sorting genetic algorithm-Ⅱ, NSGA-Ⅱ)首次提出了面向分類數(shù)據(jù)的多目標(biāo)模糊聚類算法，對(duì)全局緊密度與模糊分離度2個(gè)指標(biāo)同時(shí)優(yōu)化，具有重要的指導(dǎo)意義.近來(lái)，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)一步改善算法的性能.通過(guò)與NSGA-FMC及其他5種算法的實(shí)驗(yàn)對(duì)比分析表明了本文算法在聚類準(zhǔn)確度與穩(wěn)定性方面的優(yōu)勢(shì)，并且其對(duì)模糊參數(shù)的敏感性相對(duì)較低，擁有較高的魯棒性.

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

1.1 FKMd聚類的概念

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

(1)

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

(2)

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

(3)

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

(4)

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

1.2 Fcentroids聚類的概念

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

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

(5)

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

(6)

(7)

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

(8)

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

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

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

2.1 染色體編碼

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

(9)

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

多目標(biāo)聚類算法的性能在很大程度上取決于目標(biāo)函數(shù)的選取，現(xiàn)有文獻(xiàn)中大部分選取2個(gè)目標(biāo)函數(shù)進(jìn)行優(yōu)化并且主要考慮的是劃分的緊密性和分離性的性能.本文中MOFcentroids的目標(biāo)函數(shù)并沒(méi)有采用文獻(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ù)的個(gè)數(shù)，D(ci,ck)為第i個(gè)類與第k個(gè)類之間的相異度.

(10)

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

(11)

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

(12)

2.3 染色體選擇

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

如果irjd，則:

inj,

(13)

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

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

(14)

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

2.4 交叉過(guò)程

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

fori=1 toNdo

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

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

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

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

end for

2.5 變異過(guò)程

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

fori=1 toNdo

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

fors=1 tondo

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

ifr

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

2.7 最終解的選取

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

2.8 算法具體流程

算法1. MOFcentroids算法.

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

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

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

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

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

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

Step7.Iter=Iter+1，若Iter

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

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

(15)

2.9 基于采樣選取模糊類中心點(diǎn)

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

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

Table 1 The Confidence of Rare Attribute Value in Heart

Table 2 The Confidence of Partial Rare Attribute Value in Dermatology

(16)

(17)

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

(18)

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文通過(guò)分類型人工數(shù)據(jù)生成器*http://www.datgen.com產(chǎn)生2個(gè)較高維的人工數(shù)據(jù)集500_50_3和1000_50_4，其中每個(gè)屬性均具有4個(gè)屬性值.選取UCI數(shù)據(jù)庫(kù)的8個(gè)常用的真實(shí)數(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 聚類性能評(píng)估標(biāo)準(zhǔn)

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

(19)

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

(20)

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

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

(21)

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

各算法通過(guò)MATLAB2010b編程運(yùn)行，計(jì)算機(jī)的硬件配置為：Intel Core P7450，CPU主頻為2.13 GHz，RAM為2 GB.對(duì)上述的5個(gè)算法以及本文算法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í)行采樣操作；對(duì)其余7個(gè)數(shù)據(jù)集均執(zhí)行采樣操作，且采樣規(guī)模均為n′=0.3n，以保證絕大部分屬性的屬性值都能被選取到，無(wú)法選取到的即為稀有屬性值.各算法分別運(yùn)行30次，記錄并計(jì)算出Acc和ARI的均值及標(biāo)準(zhǔn)差如表4所示，其中對(duì)每個(gè)數(shù)據(jù)的最優(yōu)指標(biāo)值加粗，且有多個(gè)最優(yōu)值時(shí)優(yōu)先標(biāo)明本文算法.為了更直觀地比較各算法結(jié)果的統(tǒng)計(jì)分布情況，各算法對(duì)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中的實(shí)驗(yàn)結(jié)果，首先比較Fcentriods與FKMd的各項(xiàng)指標(biāo)值可以發(fā)現(xiàn)Fcentriods在聚類準(zhǔn)確度與穩(wěn)定性方面均具有較明顯的優(yōu)勢(shì)，這也成為了本文算法能夠獲得比較滿意結(jié)果的原因之一.由于Fcentriods對(duì)Soybean的聚類指標(biāo)已達(dá)到最優(yōu)無(wú)提升空間，對(duì)Votes和Mushroom的聚類指標(biāo)也較高以致相關(guān)改進(jìn)算法難以獲得提升，這里可見(jiàn)本文算法對(duì)較小數(shù)據(jù)集和較大數(shù)據(jù)集均具有良好的聚類性能.對(duì)于數(shù)據(jù)集500_50_3，1000_50_4，Zoo，Promotor，Heart，Dermatology，DNA，本文算法相對(duì)于Fcentriods的Acc和ARI均具有比較明顯的提升.其中可以發(fā)現(xiàn)尤其對(duì)2個(gè)人工數(shù)據(jù)集的提升效果非常明顯，對(duì)于Acc分別提升了21.1%，26.2%；對(duì)于ARI分別提升了32.2%，20.47%.這是由于Fcentriods算法對(duì)這2個(gè)數(shù)據(jù)集的性能很不穩(wěn)定，對(duì)于500_50_3能夠獲得Acc指標(biāo)的最大值為0.70，最小值為0.34；對(duì)于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)算法對(duì)這2個(gè)人工數(shù)據(jù)集幾乎是無(wú)效的，其原因值得進(jìn)一步研究.在UCI的真實(shí)數(shù)據(jù)集中，3種FKMd型算法對(duì)數(shù)據(jù)DNA均可看作無(wú)效，且對(duì)Promotor僅獲得很小的ARI值(對(duì)于NgFKMd和NSGA-FMC甚至為負(fù)數(shù)).Fcentriods算法對(duì)這2個(gè)數(shù)據(jù)集均具有一定的優(yōu)勢(shì)，不過(guò)其對(duì)DNA的Acc值雖然為0.501，高于FKMd的0.388，而ARI值僅為0.002，低于FKMd，這里表明采用多個(gè)指標(biāo)的必要性，本文算法同時(shí)對(duì)這2個(gè)指標(biāo)提升至0.528和0.116.進(jìn)一步比較可見(jiàn)，NSGA-FMC的性能相對(duì)于FKMd有顯著的提高，且相對(duì)于NgFKMd也有一定的提高.而本文算法對(duì)于各個(gè)數(shù)據(jù)集的Acc和ARI均高于NSGA-FMC，這也間接體現(xiàn)了Fcentriods相對(duì)于FKMd的優(yōu)勢(shì).綜合對(duì)比可見(jiàn)，除了少數(shù)情況外，本文算法的聚類指標(biāo)值均為最大并已在表4中加粗標(biāo)明，并且對(duì)多個(gè)數(shù)據(jù)集的標(biāo)準(zhǔn)差也很小，表明其具有較高的穩(wěn)定性，因此可以判斷出其具有最佳的聚類性能.

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

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

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

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

Table 6 Average Runtime of Fcentroids and MOFcentroids

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

國(guó)家自然科學(xué)基金項(xiàng)目(61373126)；江蘇省自然科學(xué)基金項(xiàng)目(BK20131107)；江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金-前瞻性聯(lián)合研究基金項(xiàng)目(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).