基于模型的非凸聚類算法

鐘卓輝,陳黎飛,3

(1.福建師范大學(xué)計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院,福建 福州 350117;2.數(shù)字福建環(huán)境監(jiān)測(cè)物聯(lián)網(wǎng)實(shí)驗(yàn)室,福建 福州 350117;3.福建省應(yīng)用數(shù)學(xué)中心,福建 福州 350117)

1 引言

將一組數(shù)據(jù)劃分成若干子集(每個(gè)子集為一個(gè)簇)的任務(wù)歸為聚類的范疇,要求不同簇中的數(shù)據(jù)盡可能相異,而同一簇中的數(shù)據(jù)盡可能相似[1,2]。迄今,研究人員已提出多種聚類算法。這些聚類算法可粗略地劃分為層次聚類、基于劃分聚類、基于密度聚類、基于模型聚類以及其他聚類算法[1]。然而,在譬如醫(yī)療診斷等的許多科學(xué)領(lǐng)域,簇結(jié)構(gòu)往往呈現(xiàn)非對(duì)稱多峰等非凸特性,多數(shù)算法依賴于范數(shù)距離最小等原則,往往導(dǎo)致生成的簇傾向于具有凸?fàn)罱Y(jié)構(gòu)。因此,大多數(shù)傳統(tǒng)的聚類算法在這類非凸簇或被稱為非規(guī)則簇的聚類問(wèn)題時(shí)功能受限[3]。針對(duì)該類挑戰(zhàn),研究人員提出了多種解決方法?，F(xiàn)有的非凸聚類方法大致分為基于原始空間的方法[4-6]和基于空間變換[7-9]的方法。

第1類方法直接在原始空間內(nèi)定義聚類算法,適用于非凸簇結(jié)構(gòu)的問(wèn)題。具有代表性的方法是基于密度的聚類,其原理是在原始?xì)W氏空間中找到被空的或稀疏的區(qū)域分隔開的集中區(qū)域。譬如DBSCAN(Density-Based Spatial Clustering of Applications with Noise)[5],其以每個(gè)樣本為中心在原始局部線性空間中,在事先指定鄰域閾值參數(shù)ε的歐氏距離半徑內(nèi)計(jì)算樣本的個(gè)數(shù)作為密度,基于密度可達(dá)距離的概念將樣本點(diǎn)相連成簇。另外,Mean Shift[6,10]及其變體考慮一種更為魯棒的連續(xù)性密度,通過(guò)核密度估計(jì)方法計(jì)算樣本的密度。最新研究表明,密度峰值聚類DPC(Density Peak Clustering)[4]是Mean Shift的一種變步長(zhǎng)的特殊變種[11]。

在這類方法中,隨著維度d的增加,數(shù)據(jù)點(diǎn)在空間的分布變得越來(lái)越稀疏,此時(shí)基于一些常用的距離度量方法,如歐氏距離,數(shù)據(jù)點(diǎn)之間的距離將趨于相等,從而導(dǎo)致所謂的“差距趨零”現(xiàn)象。這種空間對(duì)象的稀疏分布特性同樣會(huì)影響到譬如鄰域閾值ε的概念,不適用于較高維的數(shù)據(jù)[12,13]。

第2類方法將原始空間中的數(shù)據(jù)進(jìn)行空間變換,使得簇在原始空間中可能具有的非凸形狀在新空間中接近于球形,然后在這個(gè)新空間中使用傳統(tǒng)的K-Means[14]算法或其他經(jīng)典算法進(jìn)行聚類。代表算法包括譜聚類[7]、核聚類[8]和子空間聚類[9]等。Kernel-K-means[15]算法以核函數(shù)為橋梁進(jìn)行空間映射,以黑盒方式對(duì)原始空間中樣本的特征進(jìn)行組合,放大數(shù)據(jù)之間的差異,使樣本分布在新空間中變得規(guī)則。子空間聚類的基本思想是：使用一個(gè)隨機(jī)的變換矩陣將原始數(shù)據(jù)的每個(gè)列向量投影到一個(gè)單位向量長(zhǎng)度的低維空間,達(dá)到維度約簡(jiǎn)目的的同時(shí)可使簇的形狀接近于規(guī)則的球形[16]。

另一方面,聚類分析作為一種描述性數(shù)據(jù)挖掘方法,數(shù)據(jù)聚類的目的應(yīng)不僅限于揭示數(shù)據(jù)中潛在的簇結(jié)構(gòu),還需提供理解和產(chǎn)生這種簇結(jié)構(gòu)的潛在機(jī)制[1,17],比如簇類的描述性模型。基于這種描述性模型的算法稱為基于模型的聚類算法[18-20]。從統(tǒng)計(jì)學(xué)的角度,譜聚類和K-means[14]等都可以視作一種基于模型的方法。比如K-means所學(xué)習(xí)的模型實(shí)際上就是以方差等參數(shù)為常數(shù)的一類簡(jiǎn)化高斯混合模型[20]。

然而,這些方法都沒有顯式地構(gòu)造數(shù)據(jù)背后的描述性統(tǒng)計(jì)模型。而這種描述性建模過(guò)程有利于充分發(fā)揮聚類分析的潛力,挖掘數(shù)據(jù)中重要信息。比如,可以應(yīng)用一些統(tǒng)計(jì)方法,如最大似然估計(jì)等分析數(shù)據(jù)的分組,對(duì)生成的簇進(jìn)行顯式的統(tǒng)計(jì)刻畫,為每個(gè)分量提供概率分布描述每個(gè)樣本,提供關(guān)于樣本-簇劃分的概率向量等。另外,這樣的模型還可用于聚類有效性問(wèn)題的研究[12]。

當(dāng)前,基于模型的方法應(yīng)用于非凸簇聚類存在的困難有2個(gè)方面。首先,該方法本質(zhì)上是將樣本空間劃分成K個(gè)Voronoi區(qū)域,決定了劃分結(jié)果中的K個(gè)簇一定是凸集(球形或橢球)。其次,由于高維數(shù)據(jù)分布本質(zhì)上是稀疏的,在這種情況下,這些源自多元高斯分布的樣本在其“中心”附近的占比將迅速下降到0,產(chǎn)生所謂的“空空間現(xiàn)象”[21]。

本文提出一種基于模型的非凸聚類算法MNCC(Model-based method for Non-Convex Clustering),以彌補(bǔ)上述方法存在的缺陷。MNCC從不同密度極大值的覆蓋區(qū)域?qū)С龃氐膭澐譁?zhǔn)則,從模型建立和優(yōu)化2個(gè)方面實(shí)現(xiàn)基于模型的非凸聚類且無(wú)需事先給定簇的數(shù)目。本文主要工作有：

(1)提出了一個(gè)模型來(lái)描述非凸結(jié)構(gòu)的簇。以非參數(shù)估計(jì)方法替代參數(shù)化分布,避免對(duì)總體分布的假定,直接以所有樣本實(shí)例的函數(shù)定義總體數(shù)據(jù)混合形式的密度,并定義了樣本權(quán)重和特征權(quán)重用于衡量樣本和特征對(duì)密度函數(shù)的重要程度,以此建立模型。

(2)基于模型以最大化樣本似然為目標(biāo)推導(dǎo)優(yōu)化目標(biāo)函數(shù),并提出一個(gè)期望最大化EM(Expectation Maximization)類型求解密度函數(shù)密度極大值的優(yōu)化算法。通過(guò)概率描述簇,可以應(yīng)用最大似然估計(jì)等統(tǒng)計(jì)方法推導(dǎo)模型參數(shù)的計(jì)算公式,用于優(yōu)化目標(biāo)函數(shù)。此外,簇的數(shù)目不需人為設(shè)定,而是在優(yōu)化模型參數(shù)后根據(jù)密度極大值確定。

2 基于模型的非凸聚類

本節(jié)介紹一種非凸聚類的模型和聚類目標(biāo)優(yōu)化函數(shù),并提出一種求解該目標(biāo)函數(shù)的算法。給定數(shù)據(jù)集X={x1,x2,…,xi,…,xN},其中,N為數(shù)據(jù)樣本點(diǎn)數(shù)目,任一D維數(shù)據(jù)樣本點(diǎn)表示為xi=(xi1,xi2,…,xid,…,xiD)。給定N個(gè)對(duì)象,聚類算法將其劃分為K個(gè)不相交的非空子集C1,…,Ck,…,CK,每個(gè)子集為一個(gè)簇,第k個(gè)簇Ck包含的樣本點(diǎn)數(shù)記為nk。

2.1 高斯核密度混合模型

高斯混合是許多基于模型的聚類算法對(duì)數(shù)據(jù)分布模型做出的基本假設(shè)[22]。在這種情況下,數(shù)據(jù)點(diǎn)被認(rèn)為來(lái)自各種(有限個(gè))各自特定的高斯分布。采用這種有限混合模型的聚類需要一個(gè)假設(shè),即每個(gè)簇對(duì)應(yīng)于其簇內(nèi)數(shù)據(jù)的概率密度函數(shù)都是單峰分布,使得每個(gè)混合成分能夠捕獲一個(gè)單獨(dú)的峰值[23]。然而,在非凸聚類問(wèn)題中,簇形狀往往呈現(xiàn)多峰特性,這違背了傳統(tǒng)有限混合模型的假設(shè),無(wú)法有效地刻畫非凸簇的形狀。除此之外,由于維度災(zāi)難[11,21],高斯混合分布模型常用于描述低維空間中的簇類,并不適用于高維空間。一種與之不同的思路是,通過(guò)高斯核密度估計(jì)方法對(duì)數(shù)據(jù)進(jìn)行非參數(shù)估計(jì)建模[24],借助眾數(shù)概念將簇定義為總體概率密度函數(shù)的密度極大值所覆蓋的區(qū)域[25]。首先給出基于高斯核密度估計(jì)的總體密度函數(shù),如式(1)所示：

(1)

(2)

(3)

(4)

(5)

將式(1)與式(5)相比可知,后者借助核函數(shù)K(·)對(duì)原始數(shù)據(jù)進(jìn)行“核化”,在非線性概率空間中考慮了特征之間的聯(lián)系,且在映射后的概率空間中通過(guò)權(quán)重wd進(jìn)行了特征選擇,同時(shí)還以參數(shù)αj考慮了不同樣本點(diǎn)對(duì)總體密度函數(shù)的貢獻(xiàn)程度。這種概率空間的映射與核聚類或譜聚類方法是不同的,其能夠通過(guò)顯式模型進(jìn)行描述。當(dāng)αj=1/N,j=1,2,…,N且wd=1/D,d=1,2,…,D時(shí),式(5)退化為一般的核密度估計(jì)式。顯然,式(1)是所提概率模型的一種特殊情況。

2.2 聚類準(zhǔn)測(cè)

(6)

(7)

由Jensen不等式[1]可知：

(8)

(9)

可以看到,式(8)的右邊是一個(gè)帶約束的非線性優(yōu)化問(wèn)題。記上述關(guān)于wd,aj,zij的約束條件分別如式(10)～式(12)所示：

(10)

(11)

(12)

應(yīng)用拉格朗日乘子法,結(jié)合上述定義,則優(yōu)化目標(biāo)如式(13)所示：

J(X,h,Θ,Z)≥J1(X,h,Θ,Z)

(13)

J1(X,h,Θ,Z)=

(14)

(15)

h(t+1),Θ(t+1),X(t+1)=

(16)

(17)

證明當(dāng)F(x,x,h,αj,W)/zij為常數(shù)β時(shí)有式(18)：

(18)

式(18)同時(shí)乘以zij并關(guān)于j進(jìn)行求和有：

(19)

將式(19)代入式(18)有：

(20)

聯(lián)立式(20)和式(9)進(jìn)行約簡(jiǎn)后得式(17)。

當(dāng)zij滿足式(17)時(shí),F(xi,xj,h,αj,W)/zij為常數(shù),此時(shí)關(guān)于式(13)的等號(hào)成立,對(duì)目標(biāo)函數(shù)J1(·)的優(yōu)化即是對(duì)原始對(duì)數(shù)似然的優(yōu)化。下面證明式(16)為J1(·)關(guān)于隱變量Z的局部最優(yōu)解。根據(jù)式(16),可以定義N個(gè)獨(dú)立的子優(yōu)化目標(biāo)函數(shù),如式(21)所示：

Ji(zi,ξi)=

(21)

(22)

聯(lián)立式(22)和式(9)可得式(17)。

□

3 MCNN聚類算法

本節(jié)給出MCNN算法的具體描述。所提算法的優(yōu)化步驟分別對(duì)應(yīng)E-step和M-step 2個(gè)局部?jī)?yōu)化問(wèn)題,對(duì)目標(biāo)函數(shù)的每組參數(shù)進(jìn)行局部?jī)?yōu)化。第2節(jié)已經(jīng)給出了E-step關(guān)于Z的局部?jī)?yōu)化問(wèn)題的具體細(xì)節(jié)。在M-step步驟中將式(16)的最優(yōu)化問(wèn)題分解為3個(gè)分別關(guān)于樣本點(diǎn)集合X、帶寬h和權(quán)重參數(shù)集合Θ的局部?jī)?yōu)化問(wèn)題,具體依據(jù)是以下3個(gè)定理。

(23)

(24)

(25)

(26)

聯(lián)立式(25)和式(26),可分別得到式(23)和式(24)。

□

(27)

(28)

□

(29)

(30)

聯(lián)立式(29)與式(12)可得式(30)。

□

根據(jù)上述參數(shù)的求解方法,當(dāng)任意樣本點(diǎn)不再改變時(shí),所有樣本點(diǎn)收斂于某個(gè)局部區(qū)域的極大值。從收斂后的所有數(shù)據(jù)點(diǎn)中提取不相同的數(shù)據(jù)點(diǎn)作為密度極大值的集合M={mk|k=1,2,…,K},這樣簇的數(shù)量也同時(shí)能夠自動(dòng)確定,即為集合M的長(zhǎng)度K,即密度極大值的數(shù)目。樣本點(diǎn)關(guān)于簇的劃分遵循如式(31)所示的規(guī)則：

(31)

在實(shí)際訓(xùn)練過(guò)程中,需要給定一個(gè)閾值ε,當(dāng)一對(duì)樣本間的距離小于這個(gè)閾值時(shí),認(rèn)為其屬于同一個(gè)密度極大值點(diǎn)。綜上所述,MCNN算法具體過(guò)程如算法1所示。

算法1 MNCC輸入：X,并記為X(0)。輸出：聚類劃分{C1,C2,…,Ck}。初始化： 令t為迭代次數(shù),初始化t=0; 令Z={zij=1/N|i,j=1,2,…,N},并記為Z(0); 令W={wd=1/D|d=1,2,…,D},并記為W(0);repeat： 根據(jù)式(26)更新帶寬h并記為h(t+1); 根據(jù)式(22)和式(23)更新權(quán)重向量W和先驗(yàn)A,并記其集合為Θ(t+1); 根據(jù)式(17)更新隱變量Z并記為Z(t+1); 根據(jù)式(28)更新樣本點(diǎn)X并記為X(t+1); 更新迭代次數(shù)t：t=t+1;Until X(t+1)-X(t)<10e-5 從X(t+1)中提取密度極大值的集合M。遍歷X,根據(jù)式(30)將樣本xi劃分至Ck中。

從算法結(jié)構(gòu)可知每一次迭代過(guò)程的時(shí)間復(fù)雜度為O(N2D),假設(shè)算法迭代次數(shù)為T,則該算法時(shí)間復(fù)雜度為O(N2DT)。算法在每一次迭代過(guò)程中提高目標(biāo)函數(shù)值,又因?yàn)樗迫缓瘮?shù)有界,因此在有限的迭代次數(shù)下算法是收斂的。關(guān)于該算法的嚴(yán)格收斂性證明可參照關(guān)于EM算法的收斂性證明[27]。

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

本節(jié)評(píng)估了所提出的MCNN聚類算法在人工數(shù)據(jù)集和實(shí)際數(shù)據(jù)集上的性能,并通過(guò)實(shí)驗(yàn)將 MCNN與一些經(jīng)典的或最新的聚類算法進(jìn)行比較。

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)選擇了5種聚類算法進(jìn)行對(duì)比,包括DBSCAN[5]、DPC[4]、Kernel-K-means[15]、SCSM (Spectral Clustering for Single and Multi-view data)[28]和GMCM(Gaussian Mixture Copula Models)[29]。其中,DBSCAN以樣本點(diǎn)的密度可達(dá)概念劃分不同的簇,為鄰域密度聚類中最具代表的算法之一;DPC利用數(shù)據(jù)的局部密度以及相對(duì)距離屬性快速確定聚類中心,已經(jīng)成為密度聚類的研究熱點(diǎn)之一;Kernel-K-means在K-means的基礎(chǔ)上引入了核函數(shù),實(shí)現(xiàn)原始數(shù)據(jù)空間非線性映射;SCSM是一種最近提出的譜聚類算法,通過(guò)提出的自適應(yīng)密度感知內(nèi)核增強(qiáng)共享共同最近鄰居的點(diǎn)之間的相似性,并以此構(gòu)造相似矩陣。Kernel-K-means與SCSM代表了基于空間變換的2種非凸聚類主流算法。實(shí)驗(yàn)還選擇了最近提出的GMCM算法,其使用高斯混合 Copula-meta 模型進(jìn)行聚類,與本文算法的相似點(diǎn)在于二者都是基于模型的聚類算法。所有對(duì)比算法都需要人為設(shè)置參數(shù)值。在本文實(shí)驗(yàn)中,對(duì)這些參數(shù)使用了最常見的設(shè)置或推薦值。不同算法的參數(shù)設(shè)置情況如下所示。

對(duì)于DBSCAN的密集區(qū)域所需最小點(diǎn)個(gè)數(shù)MinPts和鄰域半徑ε,根據(jù)文獻(xiàn)的推薦設(shè)置MinPts的搜索范圍為MP={mp|D+1≤mp≤2D,mp∈N};對(duì)于給定的mp,以關(guān)于該mp的k-distance圖的值域作為ε的搜索范圍。DPC算法通過(guò)計(jì)算特定距離矩陣的距離截止值dc(即截?cái)嗑嚯x),使平均相鄰率(距離截止值內(nèi)的點(diǎn)數(shù))落在提供的范圍之內(nèi)。需要的截?cái)嗑嚯x參數(shù)dc由所有點(diǎn)的鄰居數(shù)量的平均值占數(shù)據(jù)點(diǎn)總量的百分比nr確定。根據(jù)文獻(xiàn)推薦,nr的取值為0.2%,0.4%,0.6%,1%,2%,4%,6%,8%,因此本文以0.1%為步長(zhǎng)在[0.2%,8%]進(jìn)行搜索。對(duì)于Kernel-K-means,其核函數(shù)的參數(shù)σ設(shè)置搜索范圍為[0,1],搜索的步長(zhǎng)設(shè)置為0.01。對(duì)于SCSM中特征分解近鄰數(shù)等參數(shù)及GMCM的參數(shù),使用原文獻(xiàn)中推薦的默認(rèn)值。此外,Kernel-K-means和GMCM算法需要設(shè)置簇?cái)?shù)K,實(shí)驗(yàn)中使用真實(shí)簇?cái)?shù)目作為輸入。

為了驗(yàn)證MCNN聚類算法的性能,實(shí)驗(yàn)采用人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集進(jìn)行測(cè)試。由于已知各數(shù)據(jù)集類別標(biāo)簽,本文選擇外部聚類評(píng)價(jià)指標(biāo)：規(guī)范化互信息熵NMI(Normalized Mutual Information)[30]和F-Score[20]評(píng)估算法的聚類性能,其計(jì)算公式分別如式(32)和式(33)所示：

(32)

(33)

其中,nl為數(shù)據(jù)集第l類的樣本數(shù),Rk,l為聚類結(jié)果中簇ck與第l類匹配的樣本數(shù),Rel,k和Pel,k分別為第l類與聚類結(jié)果中簇ck相比較的準(zhǔn)確率和召回率。NMI和F-Score的值越大,表示聚類結(jié)果質(zhì)量越好。

各對(duì)比算法均通過(guò)設(shè)置參數(shù)組進(jìn)行多次實(shí)驗(yàn)獲取參數(shù)最優(yōu)值,以取得NMI值最大的參數(shù)作為最優(yōu)參數(shù)。對(duì)于具有隨機(jī)性的算法,隨機(jī)初始化參數(shù)后進(jìn)行50次實(shí)驗(yàn),并選擇獲得NMI值最大的參數(shù)作為最優(yōu)參數(shù)。為了實(shí)驗(yàn)的公平性,所有非隨機(jī)性的算法均取其最優(yōu)參數(shù)下的聚類結(jié)果。具有隨機(jī)性的算法取其最優(yōu)參數(shù)下100次實(shí)驗(yàn)中對(duì)應(yīng)最大NMI值的聚類結(jié)果。

4.2 人工數(shù)據(jù)集實(shí)驗(yàn)

為了測(cè)試MNCC算法的可行性,本節(jié)在4個(gè)著名的非凸簇人工數(shù)據(jù)集上進(jìn)行測(cè)試,包括Jain、Aggregation、D31和Four-lines,數(shù)據(jù)維度均為二維,這有助于對(duì)聚類結(jié)果進(jìn)行可視化展示。表1給出了各數(shù)據(jù)集的具體信息。

Table 1 Information of artificial datasets

圖1給出了4個(gè)數(shù)據(jù)集的初始樣本分布情況,其中Jain(圖1a)數(shù)據(jù)集包含了2類密度差較大的非凸?fàn)畲?在原始數(shù)據(jù)空間中無(wú)法線性可分,呈現(xiàn)月牙狀分布;Aggregation(圖1b)包含了7個(gè)形狀大小不一的簇,其密度較為均勻,但簇間存在各種異常點(diǎn)和干擾點(diǎn);D31(圖1c)包含了31個(gè)緊密相連的簇,且簇間有明顯的重疊現(xiàn)象;Four-lines(圖1d)包含了4個(gè)呈現(xiàn)條狀的簇,且簇的大小和密度不一。

Figure 1 Initial distribution of samples in four artificial datasets圖1 4個(gè)人工數(shù)據(jù)集的樣本初始分布情況

圖2展示了本文提出的MNCC聚類算法在4個(gè)人工數(shù)據(jù)集上的聚類可視化結(jié)果?？梢钥闯?MNCC算法在上述4個(gè)不同類型的人工數(shù)據(jù)集上表現(xiàn)優(yōu)異,其中在Jain和Four-lines上聚類結(jié)果完全正確;在Aggregation和D31數(shù)據(jù)集上聚類結(jié)果幾乎完全正確。部分對(duì)比算法的最優(yōu)參數(shù)如表2所示。各對(duì)比算法與MNCC算法的聚類性能對(duì)比情況如表3所示,表內(nèi)粗體數(shù)字為各數(shù)據(jù)集上最高的指標(biāo)值。

Figure 2 Clustering results of MNCC algorithm on four artificial datasets圖2 MNCC算法在4個(gè)人工數(shù)據(jù)集上的聚類結(jié)果

Table 2 Optimal parameters of some comparative algorithms on four artificial datasets

Table 3 Performance comparison of six algorithms on four artificial datasets

總體而言,MNCC在4個(gè)數(shù)據(jù)集上獲得了相對(duì)于對(duì)比算法更高的聚類質(zhì)量,表明本文算法在處理非凸聚類問(wèn)題時(shí)具有很高的可行性。除此之外,GMCM在Jain和Four-lines數(shù)據(jù)集上的NMI值最低,側(cè)面反映了傳統(tǒng)的基于模型的聚類方法無(wú)法勝任非凸聚類問(wèn)題。

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

為進(jìn)一步測(cè)試 MCNN 算法的聚類性能,本節(jié)還在真實(shí)數(shù)據(jù)集上進(jìn)行測(cè)試。實(shí)驗(yàn)采用來(lái)自加州大學(xué)歐文分校UCI(University of California Irvine)數(shù)據(jù)庫(kù)(http：//Archiveics.uci.edu/ml/datasets.html)的6個(gè)真實(shí)數(shù)據(jù)集,其詳細(xì)信息如表4所示。

Table 4 Information of six UCI real-world datasets

表5展示了部分對(duì)比算法的最優(yōu)參數(shù),表6給出了各算法在真實(shí)數(shù)據(jù)集上的聚類性能對(duì)比情況。

Table 5 Optimal parameters of some algorithms on 6 real-world datasets

Table 6 Performance comparison of six algorithms on six real datasets

從表6可知,與對(duì)比算法相比,MCNN算法在除Wine外的其余真實(shí)數(shù)據(jù)集上均獲得了NMI最大的聚類性能,特別是在Soybean-Small和Olive數(shù)據(jù)集上聚類結(jié)果完全正確。值得注意的是,在類別數(shù)較高和相對(duì)高維的SoybeanLarge數(shù)據(jù)集上,MNCC的NMI和F-Score值高于其他對(duì)比算法的甚多,說(shuō)明了所提算法具有良好的適應(yīng)性。

Figure 3 Feature weight distribution obtained by MNCC on five real datasets圖3 MNCC獲得的5個(gè)真實(shí)數(shù)據(jù)集上的特征權(quán)重分布

以SoybeanSmall數(shù)據(jù)集為例,從MCNN算法的一次聚類結(jié)果中提取特征權(quán)重信息作進(jìn)一步分析。圖4給出了數(shù)據(jù)空間中特征權(quán)重的對(duì)數(shù)尺度直方圖,其中y軸上的值是權(quán)重在特定范圍內(nèi)的對(duì)數(shù)。權(quán)重小于0.1的屬性數(shù)量為27,這表明只有8個(gè)屬性(A2,A12,A23,A24,A26,A27,A28,A35)對(duì)聚類效果有較大貢獻(xiàn),因此以0.1為閾值提取原始特征集合的子集,通過(guò)新構(gòu)造的特征子集(soybean_8)測(cè)試MCNN算法和5種對(duì)比算法的性能。表7給出了有關(guān)算法的最優(yōu)參數(shù),表8給出了算法在SoybeanSmall上的原始特征集合和新特征子集上的聚類對(duì)比情況。

Figure 4 Feature weight distribution obtained by MCNN on Soybeansmall dataset圖4 MCNN獲得的Soybeansmall數(shù)據(jù)集上的特征權(quán)重分布

Table 7 Optimal parameters of some algorithms on soybean_8

Table 8 Performance comparison of six algorithms on Soybean and its feature subsets

表8的聚類結(jié)果表明,大多數(shù)算法基于MCNN挖掘的特征子集能夠有效提高聚類性能,從而提高了高維數(shù)據(jù)上非凸聚類問(wèn)題的聚類性能。

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

針對(duì)非規(guī)則簇的聚類問(wèn)題,本文提出了一種基于模型的非凸聚類算法MNCC。所提算法在概率框架下進(jìn)行,給出了一種簇類的描述性模型,這是其他非凸聚類算法所不具備的。所提算法基于高斯核密度估計(jì),構(gòu)造了一種基于核密度估計(jì)的混合模型,在非線性概率空間中挖掘?qū)傩蚤g關(guān)系,同時(shí)進(jìn)行屬性重要程度的估計(jì),然后基于上述模型,提出了一種期望最大化的爬山優(yōu)化方法,進(jìn)而提出了新的聚類算法MNCC。在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,與現(xiàn)有的其他非凸聚類算法相比,MNCC算法有效提高了聚類質(zhì)量。