基于模型的非凸聚類算法

鐘卓輝,陳黎飛,3

(1.福建師范大學計算機與網絡空間安全學院,福建 福州 350117;2.數字福建環境監測物聯網實驗室,福建 福州 350117;3.福建省應用數學中心,福建 福州 350117)

1 引言

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

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

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

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

另一方面,聚類分析作為一種描述性數據挖掘方法,數據聚類的目的應不僅限于揭示數據中潛在的簇結構,還需提供理解和產生這種簇結構的潛在機制[1,17],比如簇類的描述性模型?；谶@種描述性模型的算法稱為基于模型的聚類算法[18-20]。從統計學的角度,譜聚類和K-means[14]等都可以視作一種基于模型的方法。比如K-means所學習的模型實際上就是以方差等參數為常數的一類簡化高斯混合模型[20]。

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

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

本文提出一種基于模型的非凸聚類算法MNCC(Model-based method for Non-Convex Clustering),以彌補上述方法存在的缺陷。MNCC從不同密度極大值的覆蓋區域導出簇的劃分準則,從模型建立和優化2個方面實現基于模型的非凸聚類且無需事先給定簇的數目。本文主要工作有：

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

(2)基于模型以最大化樣本似然為目標推導優化目標函數,并提出一個期望最大化EM(Expectation Maximization)類型求解密度函數密度極大值的優化算法。通過概率描述簇,可以應用最大似然估計等統計方法推導模型參數的計算公式,用于優化目標函數。此外,簇的數目不需人為設定,而是在優化模型參數后根據密度極大值確定。

2 基于模型的非凸聚類

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

2.1 高斯核密度混合模型

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

(1)

(2)

(3)

(4)

(5)

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

2.2 聚類準測

(6)

(7)

由Jensen不等式[1]可知：

(8)

(9)

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

(10)

(11)

(12)

應用拉格朗日乘子法,結合上述定義,則優化目標如式(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)

證明當F(x,x,h,αj,W)/zij為常數β時有式(18)：

(18)

式(18)同時乘以zij并關于j進行求和有：

(19)

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

(20)

聯立式(20)和式(9)進行約簡后得式(17)。

當zij滿足式(17)時,F(xi,xj,h,αj,W)/zij為常數,此時關于式(13)的等號成立,對目標函數J1(·)的優化即是對原始對數似然的優化。下面證明式(16)為J1(·)關于隱變量Z的局部最優解。根據式(16),可以定義N個獨立的子優化目標函數,如式(21)所示：

Ji(zi,ξi)=

(21)

(22)

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

□

3 MCNN聚類算法

本節給出MCNN算法的具體描述。所提算法的優化步驟分別對應E-step和M-step 2個局部優化問題,對目標函數的每組參數進行局部優化。第2節已經給出了E-step關于Z的局部優化問題的具體細節。在M-step步驟中將式(16)的最優化問題分解為3個分別關于樣本點集合X、帶寬h和權重參數集合Θ的局部優化問題,具體依據是以下3個定理。

(23)

(24)

(25)

(26)

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

□

(27)

(28)

□

(29)

(30)

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

□

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

(31)

在實際訓練過程中,需要給定一個閾值ε,當一對樣本間的距離小于這個閾值時,認為其屬于同一個密度極大值點。綜上所述,MCNN算法具體過程如算法1所示。

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

從算法結構可知每一次迭代過程的時間復雜度為O(N2D),假設算法迭代次數為T,則該算法時間復雜度為O(N2DT)。算法在每一次迭代過程中提高目標函數值,又因為似然函數有界,因此在有限的迭代次數下算法是收斂的。關于該算法的嚴格收斂性證明可參照關于EM算法的收斂性證明[27]。

4 實驗與結果分析

本節評估了所提出的MCNN聚類算法在人工數據集和實際數據集上的性能,并通過實驗將 MCNN與一些經典的或最新的聚類算法進行比較。

4.1 實驗設置

實驗選擇了5種聚類算法進行對比,包括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以樣本點的密度可達概念劃分不同的簇,為鄰域密度聚類中最具代表的算法之一;DPC利用數據的局部密度以及相對距離屬性快速確定聚類中心,已經成為密度聚類的研究熱點之一;Kernel-K-means在K-means的基礎上引入了核函數,實現原始數據空間非線性映射;SCSM是一種最近提出的譜聚類算法,通過提出的自適應密度感知內核增強共享共同最近鄰居的點之間的相似性,并以此構造相似矩陣。Kernel-K-means與SCSM代表了基于空間變換的2種非凸聚類主流算法。實驗還選擇了最近提出的GMCM算法,其使用高斯混合 Copula-meta 模型進行聚類,與本文算法的相似點在于二者都是基于模型的聚類算法。所有對比算法都需要人為設置參數值。在本文實驗中,對這些參數使用了最常見的設置或推薦值。不同算法的參數設置情況如下所示。

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

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

(32)

(33)

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

各對比算法均通過設置參數組進行多次實驗獲取參數最優值,以取得NMI值最大的參數作為最優參數。對于具有隨機性的算法,隨機初始化參數后進行50次實驗,并選擇獲得NMI值最大的參數作為最優參數。為了實驗的公平性,所有非隨機性的算法均取其最優參數下的聚類結果。具有隨機性的算法取其最優參數下100次實驗中對應最大NMI值的聚類結果。

4.2 人工數據集實驗

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

Table 1 Information of artificial datasets

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

Figure 1 Initial distribution of samples in four artificial datasets圖1 4個人工數據集的樣本初始分布情況

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

Figure 2 Clustering results of MNCC algorithm on four artificial datasets圖2 MNCC算法在4個人工數據集上的聚類結果

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個數據集上獲得了相對于對比算法更高的聚類質量,表明本文算法在處理非凸聚類問題時具有很高的可行性。除此之外,GMCM在Jain和Four-lines數據集上的NMI值最低,側面反映了傳統的基于模型的聚類方法無法勝任非凸聚類問題。

4.3 真實數據集實驗

為進一步測試 MCNN 算法的聚類性能,本節還在真實數據集上進行測試。實驗采用來自加州大學歐文分校UCI(University of California Irvine)數據庫(http：//Archiveics.uci.edu/ml/datasets.html)的6個真實數據集,其詳細信息如表4所示。

Table 4 Information of six UCI real-world datasets

表5展示了部分對比算法的最優參數,表6給出了各算法在真實數據集上的聚類性能對比情況。

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

Table 6 Performance comparison of six algorithms on six real datasets

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

Figure 3 Feature weight distribution obtained by MNCC on five real datasets圖3 MNCC獲得的5個真實數據集上的特征權重分布

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

Figure 4 Feature weight distribution obtained by MCNN on Soybeansmall dataset圖4 MCNN獲得的Soybeansmall數據集上的特征權重分布

Table 7 Optimal parameters of some algorithms on soybean_8

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

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

5 結束語

針對非規則簇的聚類問題,本文提出了一種基于模型的非凸聚類算法MNCC。所提算法在概率框架下進行,給出了一種簇類的描述性模型,這是其他非凸聚類算法所不具備的。所提算法基于高斯核密度估計,構造了一種基于核密度估計的混合模型,在非線性概率空間中挖掘屬性間關系,同時進行屬性重要程度的估計,然后基于上述模型,提出了一種期望最大化的爬山優化方法,進而提出了新的聚類算法MNCC。在人工數據集和真實數據集上的實驗結果表明,與現有的其他非凸聚類算法相比,MNCC算法有效提高了聚類質量。