基于候選中心融合的多觀測點I-nice聚類算法

陳鴻杰 何玉林 黃哲學(xué) 尹劍飛

簇信息是用于理解、歸納和劃分?jǐn)?shù)據(jù)群體的重要統(tǒng)計信息，是度量數(shù)據(jù)群體復(fù)雜性的一種量化指標(biāo).在簇信息中，簇的個數(shù)和簇的中心是最核心的元素.例如,在已知兩者的情況下，可使用K-means[1]等聚類算法估計數(shù)據(jù)集上簇的成員關(guān)系、離散量化誤差等信息.在僅知道簇個數(shù)的情況下，可使用譜聚類[2]等聚類算法估計簇的成員關(guān)系、數(shù)據(jù)點圖的拉普拉斯矩陣特征值等信息.簇的成員關(guān)系信息又可進一步驅(qū)動數(shù)據(jù)處理的下游任務(wù)，如監(jiān)督分類和半監(jiān)督分類.因此簇的個數(shù)和簇的中心點通常是許多聚類算法關(guān)鍵的先驗參數(shù)，需要提前設(shè)定兩者或其一的聚類算法，稱為有參聚類算法，如K-means和譜聚類等.簇數(shù)和初始中心點設(shè)定的好壞對于聚類算法的精度和效率都有很大的影響[3].

為了提升聚類算法的自動化能力，必須解決簇的個數(shù)和簇的中心點的估計問題，目前也存在一些研究成果[4-8]，然而精確估計復(fù)雜大規(guī)模數(shù)據(jù)集所含簇個數(shù)和簇中心是一項富有挑戰(zhàn)性的任務(wù).因為簇的信息是關(guān)于數(shù)據(jù)群體的統(tǒng)計信息，通常能得到的是關(guān)于這個數(shù)據(jù)群體的某些樣本數(shù)據(jù)集，從樣本數(shù)據(jù)集出發(fā)，估計關(guān)于數(shù)據(jù)群體的信息存在固有的不確定性和偏置性.另一個原因是，簇的成員關(guān)系存在多樣性，即用于判定一個數(shù)據(jù)點是否隸屬于某個簇依賴于數(shù)據(jù)點之間的距離定義，而高維空間的距離定義千差萬別，常用的有歐氏距離、閔可夫斯基距離、正態(tài)分布距離、積分距離、Wasserstein距離等.

另外，當(dāng)面對較大復(fù)雜數(shù)據(jù)集時，現(xiàn)有的估計簇的個數(shù)和簇的中心點的聚類算法存在如下不足.

1)準(zhǔn)確估計簇個數(shù)的能力有限.基于貝葉斯非參的方法[9-10]通過迪利克雷隨機過程枚舉各個維度的隱藏變量，建立隨機過程模型，只能有效識別300多個簇.Elbow[11]被廣泛用于估計數(shù)據(jù)中的簇數(shù)，計算簇心和對應(yīng)簇內(nèi)對象的平均距離和，觀察以簇數(shù)為自變量、平均距離和為因變量的曲線，隨著簇數(shù)增加，平均距離和逐漸降低，其中曲線存在“肘部”，對應(yīng)簇數(shù)值即為結(jié)果.缺點在于曲線“肘部”的確定存在模糊性，一些數(shù)據(jù)集會出現(xiàn)沒有“肘部”曲線特征的情況.Silhouette[12]針對數(shù)據(jù)集中每個對象，計算簇不相似度與對象i到同簇其它對象的平均距離，即對象i到異簇內(nèi)對象的平均距離.兩者的差值即為輪廓系數(shù)，平均輪廓系數(shù)越小表示聚類效果越優(yōu).Silhouette和Elbow均僅可識別10多個簇.

2)估計簇個數(shù)和初始中心點的質(zhì)量較差.現(xiàn)有的無監(jiān)督的簇個數(shù)估計算法，如Silhouette和Elbow，在10個簇內(nèi)存在至少一位數(shù)的偏差.Tibshirani等[13]提出Gap Statistic，簡稱為Gap統(tǒng)計量，用于確定數(shù)據(jù)集中的簇數(shù)，在簇數(shù)K取不同值時，度量其簇內(nèi)離散值的對數(shù)值與相應(yīng)數(shù)學(xué)期望的差值Gap，進行簇數(shù)的合理選擇，差值最大時的K值為最佳的簇數(shù).但Gap統(tǒng)計量容易導(dǎo)致簇數(shù)的過高估計[14]，在一些情況下差值Gap呈單調(diào)遞增.另外這種方法無法較好地應(yīng)用于源自指數(shù)分布的數(shù)據(jù)集[15].Mohajer等[16]在原本的Gap統(tǒng)計量的基礎(chǔ)上進行修改，提出Gap*統(tǒng)計量，去除Gap值的對數(shù)操作，處理原Gap統(tǒng)計量中簇數(shù)過高估計的問題，但在簇間發(fā)生重疊的數(shù)據(jù)集上表現(xiàn)不如Gap統(tǒng)計量，并且在Gap統(tǒng)計量中差值單調(diào)遞增的數(shù)據(jù)集上也并不保證在Gap*統(tǒng)計量中得到合理結(jié)果，而是得出過小的簇數(shù)估計值.Sugar等[15]提出Jump method，度量每個維度上每個觀測值與其最近的簇中心之間的平均距離，確定簇數(shù).Jump method在計算上較高效，并且在一系列實驗中得到驗證，但其畸變曲線容易出現(xiàn)單調(diào)情況，導(dǎo)致計算全局最優(yōu)無法獲得一個合理的估計值.通過交叉驗證能在一定程度上解決該問題，但需付出昂貴的計算成本.此外,Yang等[17]提出M-means(Mountain Means Clustering Algorithm)，在數(shù)據(jù)集的樣本數(shù)超過500時，無法正確估計簇的個數(shù).另外，在數(shù)據(jù)集具有高維特征且簇數(shù)較多的情況下，聚類算法往往需要人工介入、設(shè)計與觀察各種漸進統(tǒng)計數(shù)據(jù)，如平均Silhouette寬度，才能獲得較優(yōu)的聚類結(jié)果.Maitra[3]尋找數(shù)據(jù)中的大量局部模式，選取分離程度最大的點作為初始中心點，在一系列實驗上均取得可觀結(jié)果.但當(dāng)數(shù)據(jù)存在大量坐標(biāo)(特征數(shù))時，奇異值分解計算過程變難，阻礙在高維數(shù)據(jù)上的應(yīng)用.

3)計算復(fù)雜度較高，不利于大規(guī)模數(shù)據(jù)應(yīng)用場景.例如，基于譜聚類的算法[18]需要求解圖拉普拉斯矩陣的特征根，計算復(fù)雜度為O(N2K)，其中，N為樣本點數(shù)量，K為簇數(shù).狄利克雷過程混合模型[19]采用狄利克雷過程作為聚類參數(shù)的先驗分布，在較大范圍內(nèi)搜索簇的個數(shù)K，并對整個數(shù)據(jù)集進行多次掃描，估計參數(shù)的后驗概率，時間復(fù)雜度很高，不適用于大規(guī)模數(shù)據(jù)聚類場景[20].此類算法對于大規(guī)模數(shù)據(jù)處理而言是計算不可行的.對于一些基于圖神經(jīng)網(wǎng)絡(luò)的聚類算法[21]，由于需要計算每對數(shù)據(jù)點之間的距離及斷開閾值，計算復(fù)雜度也較高，同時算法一般需要監(jiān)督信息，較適用于半監(jiān)督場景[22].一些基于密度的聚類算法可直接進行聚類而無需輸入簇數(shù)或初始中心作為參數(shù)[23-24]，但往往受較高計算復(fù)雜度或空間復(fù)雜度限制，難以在大規(guī)模或高維數(shù)據(jù)集上應(yīng)用.

I-nice(Identifying the Number of Clusters and Initial Cluster Centres)[25]是一種基于觀測點投影機制和混合伽馬模型數(shù)據(jù)子集劃分的無參聚類算法，可有效估計數(shù)據(jù)集的簇數(shù)和簇中心點并聚類.I-niceSO(I-nice with a Single Observation)和I-niceMO(I-nice with Multiple Observations)分別為I-nice的兩種基本模式，I-niceSO基于單觀測點投影.I-niceMO基于多觀測點投影形成分治聚類框架，得出若干候選中心,集成后得到最終簇數(shù)和簇心結(jié)果.實驗表明I-nice具有比Elbow和Silhouette更優(yōu)的簇數(shù)估計精度，I-niceMO表現(xiàn)最佳.但在面對如下場景時，I-nice的效果與性能明顯變差.

1)當(dāng)數(shù)據(jù)集的簇之間樣本量差異較大時，混合伽馬模型無法對不平衡數(shù)據(jù)集進行較好地擬合，導(dǎo)致數(shù)據(jù)子集劃分質(zhì)量較差，進而影響候選中心點的選取.

2)當(dāng)簇數(shù)規(guī)模較大時，遍歷搜索最佳高斯混合模型(Gaussian Mixture Model, GMM)的過程十分耗時.

3)當(dāng)簇之間的相對距離差異較大時，數(shù)據(jù)集得出的候選中心之間的距離關(guān)系更復(fù)雜，無法簡單基于候選中心之間的空間距離實現(xiàn)正確集成.

上述場景在實際應(yīng)用中經(jīng)常出現(xiàn)，如何使算法能在不同的數(shù)據(jù)集上保持穩(wěn)定的聚類效果及性能，是一個非常關(guān)鍵的主題.因此，本文提出基于候選中心融合的多觀測點I-nice聚類算法(Multi-obser-vation I-nice Clustering Algorithm Based on Candidate Centers Fusion, I-niceCF)，實現(xiàn)在各種數(shù)據(jù)集上的簇數(shù)和中心點的準(zhǔn)確估計.首先沿用I-niceMO多觀測點投影機制.然后基于GMM構(gòu)件進行數(shù)據(jù)子集劃分，提出粗細(xì)粒度結(jié)合的搜索策略,快速劃分?jǐn)?shù)據(jù)子集.在識別子集候選中心后，采用基于GMM構(gòu)件歸屬向量的融合方法,對來自多個子集的簇候選中心進行集成，最終得到數(shù)據(jù)集的簇數(shù)和簇中心點.在合成數(shù)據(jù)集和真實數(shù)據(jù)集上進行一系列實驗，結(jié)果表明I-niceCF能正確估計各類數(shù)據(jù)集的簇數(shù)和簇中心點，聚類效果較優(yōu).

1 基于候選中心融合的多觀測點I-nice聚類算法

1.1 多觀測點投影及數(shù)據(jù)子集劃分

本文沿用I-nice,使用多觀測點機制對高維數(shù)據(jù)集進行投影，得到對應(yīng)的距離數(shù)組.然后使用GMM擬合距離數(shù)組,實現(xiàn)數(shù)據(jù)集的劃分.

計算數(shù)據(jù)集的全部N個樣本點到某一觀測點的距離，得到對應(yīng)的距離數(shù)組

X=(x1,x2,…,xn)，

定義對應(yīng)GMM為

求解GMM參數(shù)，其中

Zi=j表示xi屬于GMM的第j個構(gòu)件，θn表示第n次迭代估計的參數(shù).求解參數(shù)，得到擬合后的GMM，并對數(shù)據(jù)集進行劃分.

通過單觀測點得到的GMM進行數(shù)據(jù)劃分，容易出現(xiàn)不同簇被歸為同一子集中的現(xiàn)象.設(shè)置多個不同的觀測點，分別基于其到數(shù)據(jù)集全部樣本點的距離數(shù)組擬合求解，得到多個GMM，每個GMM對數(shù)據(jù)集進行不同的劃分.

1.2 最佳混合模型搜索策略

在I-nice中，設(shè)M∈[Mmax-Δ1,Mmax+Δ2]，逐個遍歷求解得到M取不同值時的多個GMM，選取其中具有最小AICc值的混合模型為最佳模型GMMbest，構(gòu)件數(shù)為Mbest.Mmax是通過核密度估計(Kernel Density Estimation, KDE)擬合距離數(shù)組計算密度函數(shù)曲線的波峰個數(shù)得到，當(dāng)數(shù)據(jù)集上簇數(shù)較多時，KDE估計的Mmax和最佳模型構(gòu)件個數(shù)Mbest之間的偏差也會較大，Δ1和Δ2需要足夠大才能保證Mbest∈[Mmax-Δ1,Mmax+Δ2]，從而使遍歷搜索過程能得到最佳混合模型.具體而言，遍歷搜索最佳模型所需時間與數(shù)據(jù)集簇數(shù)之間存在超線性關(guān)系.根據(jù)實驗，可設(shè)

Mmax=(1-α)Mbest，

誤差率α為實數(shù)區(qū)間內(nèi)定值，對于遍歷搜索策略，需

Δ1=Δ2=αMbest

本文提出粗細(xì)粒度結(jié)合的最佳GMM模型搜索策略，具體見算法1.

算法1粗細(xì)粒度結(jié)合的最佳GMM搜索策略

輸入數(shù)據(jù)集Y對應(yīng)觀測點p的距離數(shù)組X

輸出近似最佳混合模型GMMbest

階段1粗粒度搜索

form=1;m

通過EM(Expectation-Maximization)算法求解

GMMm(X)；

計算AICcm；

ifAICc2-2m≤AICc2-3m&

AICc2-2m≤AICc2-1m≤AICcmthen

break

end for

階段2細(xì)粒度搜索

h=(2-3m-2-1m)/12

form′=2-3m+h;m′<2-1m;m′=m′+hdo

通過EM算法求解GMMm′(X)；

計算AICcm′；

ifAICc2-2m′≤AICc2-3m′&

AICc2-2m′≤AICc2-1m′≤AICcm′then

break

end for

GMMbest=GMM2-2m′

按兩個階段進行最佳混合模型的搜索，第1個階段進行粗粒度搜索，GMM構(gòu)件數(shù)以底數(shù)為2的冪快速增長，粗粒度搜索的第i步求解GMM的構(gòu)件數(shù)為2i，搜索可確定Mbest的近似區(qū)間.第2階段在近似區(qū)間內(nèi)進行一定步長的細(xì)粒度搜索.在2個搜索階段中，均以AICc的“山谷”趨勢作為搜索的結(jié)束特征.“山谷”趨勢定義為AICc下降一次，然后連續(xù)增加兩次的階段，即

AICci≤AICci-1,AICci≤AICci+1≤AICci+2.

粗粒度搜索階段需進行Mbest次求解，該階段總復(fù)雜度為

細(xì)粒度搜索階段在(2?log2Mbest」,2「log2Mbest?)區(qū)間進行，設(shè)搜索步長為區(qū)間長度的1/12，則細(xì)粒度搜索階段復(fù)雜度為

綜上所述，該搜索策略總計算復(fù)雜度為O(NMbest)，搜索所需時間隨簇數(shù)呈線性增加趨勢,以線性效率高效搜索求解近似最佳混合模型，顯著優(yōu)于I-nice的遍歷搜索策略，便于I-niceCF在大規(guī)模數(shù)據(jù)集上的應(yīng)用.

1.3 基于GMM構(gòu)件向量相異度的候選中心融合

本文提出基于候選中心融合的多觀測點I-nice聚類算法(I-niceCF)，準(zhǔn)確集成來自多個觀測點的候選中心.

經(jīng)過多觀測點投影及最佳GMM進行距離子集劃分后，將分別針對各個子集內(nèi)距離值對應(yīng)的原始樣本點執(zhí)行聚類任務(wù).每個子集任務(wù)內(nèi)可通過k近鄰法確定高密度區(qū)域，進一步選取k近鄰最大的數(shù)據(jù)點作為候選中心；或采用密度峰值聚類算法(Density Peak Clustering, DPC)[24]進行聚類,得出高密度點作為候選中心.每個子集均得到若干候選中心，最終需進行集成任務(wù)，即集成來自全部觀測點對應(yīng)的最佳GMM的各個構(gòu)件所得的候選中心.

I-nice通過基于候選中心距離度量的方法進行候選中心集成，即通過候選中心之間的空間距離度量候選中心之間的冗余度，距離越小表示冗余度越高，更應(yīng)將其合并以消除簇心冗余.

I-nice的缺點是只考慮候選中心的相對距離，忽略數(shù)據(jù)集的原始分布情況.在簇間距離較均勻時,已驗證是有效的，但當(dāng)簇間距離差異較大時，容易出現(xiàn)錯誤合并或漏合并候選中心的情況，使得到的集成結(jié)果較差，直接導(dǎo)致整個算法得出錯誤的簇數(shù)和簇中心.

圖1為在包含4個簇的數(shù)據(jù)集上得出的5個候選中心，虛線區(qū)域為對應(yīng)各簇樣本點的分布情況，5個填充點為待集成的候選中心，cb1、cb2歸屬于同個真實簇Gb，3個候選中心co、cg、cr分別歸屬于3個真實簇Go、Gg、Gr.候選中心cg、cr之間的距離小于候選中心cb1、cb2之間的距離，因此基于候選中心相對距離的集成方式無法同時保證合并cb1、cb2且保留cg、cr.按照I-niceMO,基于候選中心的相對距離進行集成，會出現(xiàn)兩種錯誤.第1種為過度合并，cb1、cb2合并，cg、cr合并，co保留，雖然成功消除真實簇Gb的候選中心冗余，但也錯誤合并來自不同簇的cg、cr候選中心，最終得出簇數(shù)為3的錯誤結(jié)果.第2種為合并不充分，所設(shè)候選中心合并的距離閾值過小，圖1中5個候選中心全部保留，導(dǎo)致最終得出簇數(shù)為5的錯誤結(jié)果.

圖1 待集成的候選中心Fig.1 Candidate centers to be integrated

I-niceMO這類集成方法僅考慮候選中心之間的相對距離，忽視數(shù)據(jù)集中各簇整體的分布情況，在簇間距離差異較大時，集成操作容易出現(xiàn)錯誤，因此有必要提出更合理的候選中心集成方法.

本文提出I-niceCF，可準(zhǔn)確度量候選中心之間的冗余度.對于每個候選中心ci，有構(gòu)件向量Ψi=[ζ1,ζ2,…,ζP]，記錄其分別在P個觀測點的混合模型中對應(yīng)的構(gòu)件索引ζ.并結(jié)合曼哈頓距離和切比雪夫距離設(shè)計閔可夫斯基距離對:

(1)

度量不同候選中心構(gòu)件向量之間的相異度，相異度越小表明冗余度越高.簡而言之，DMC的取值越小表明更多觀測點將該兩個候選中心劃分為相同的子集或相鄰的子集，這意味著它們在原始高維空間更趨向?qū)儆谕粋€簇.

相對設(shè)定的4個觀測點,圖1的5個候選中心可計算對應(yīng)的構(gòu)件向量，過程如圖2所示.

每個觀測點基于其到數(shù)據(jù)集所有點的距離數(shù)組，可解出對應(yīng)的混合高斯分布，圖2中虛線輪廓的填充區(qū)域?qū)?yīng)的是圖1中各真實簇內(nèi)樣本到觀測點的距離數(shù)組構(gòu)成的概率密度分布,各子圖橫軸下5個候選中心圖標(biāo)的位置對應(yīng)它們到觀測點的距離值.因為對于某特定觀測點，存在多個真實簇位于同一距離區(qū)間，因此求解的最佳GMM的構(gòu)件個數(shù)常不等于真實簇個數(shù)，會存在多個真實簇(對應(yīng)距離值)包含在求解GMM的單個構(gòu)件中，也會存在單個真實簇的各部分(對應(yīng)距離值)分別被包含在GMM的不同構(gòu)件中.

(a)觀測點1 (b)觀測點2 (c)觀測點3 (d)觀測點4(a)Observation point 1 (b)Observation point 2 (c)Observation point 3 (d)Observation point 4圖2 4個觀測點樣本距離值分布和混合模型概率密度曲線Fig.2 Distance distribution and probability density curves of GMMs of samples on 4 observation points

圖3(b)為基于DMC求解的5個候選中心的相異度矩陣.I-nice錯誤合并cg和cr，在此處計算得出

DMC(Ψg,Ψr)=〈3,1〉，

而候選中心cb1、cb2的相異度

DMC(Ψb1,Ψb2)=〈0,0〉.

顯而易見，2個冗余的候選中心cb1、cb2之間的相異度與其它候選中心之間的相異度差距明顯，可容易設(shè)定標(biāo)準(zhǔn)以融合相異度小于一定范圍的候選中心點對.具體地，設(shè)定

其中P為觀測點數(shù)量.當(dāng)2個候選中心的相異度DMC同時滿足

DMC[0]

則這2個候選中心應(yīng)進行融合.

(a)構(gòu)件向量 (b)相異度矩陣(a)Component vectors (b)Dissimilarity matrix圖3 5個候選中心點的混合模型構(gòu)件向量及相異度矩陣Fig.3 Mixed model component vectors and dissimilarity

matrix of 5 candidate centers

總之，對于全部候選中心計算相異度矩陣，矩陣元素滿足上述兩個條件，表明對應(yīng)的兩個候選中心存在可融合連接.最終構(gòu)成以全部候選中心為節(jié)點、以可融合連接為邊的無向圖，計算其連通分量，得出最終的簇數(shù)和簇心.基于GMM構(gòu)件向量的候選中心融合方法步驟詳見算法2.

算法2基于GMM構(gòu)件向量的候選中心融合方法

輸入候選中心c1,c2,…,cm，觀測點O1,O2,…,OP，

最佳模型GMM1(M1,π1,θ1),…,

GMMP(MP,πP,θP)

輸出融合中心c′1,c′2,…

step 1 對于c1,c2,…,cm,求各自對應(yīng)的構(gòu)件向量

其中

step 2 基于式(1)計算相異度矩陣

Φ=[DMC(Ψi,Ψj)]m×m, 1≤i≤m, 1≤j≤m.

step 4 計算矩陣

[boolean(φij<〈Tm,Tc〉)]m×m，

并生成對應(yīng)無向圖G.

step 5 求解得到連通分量CC1,CC2,…

step 6 計算每個連通分量所含候選中心樣本點的均值，得到融合后的中心c′1,c′2,…

在全部觀測點對應(yīng)GMM的各個構(gòu)件的候選中心集成之后，將得到最終的簇數(shù)和融合后的候選中心稱為初始中心點.將簇數(shù)及初始中心點作為先驗參數(shù)傳給K-means算法,得到數(shù)據(jù)集的聚類結(jié)果.

1.4 本文算法流程及復(fù)雜度分析

I-niceCF流程如圖4所示.

圖4 I-niceCF流程圖Fig.4 Flowchart of I-niceCF

設(shè)數(shù)據(jù)集D的樣本數(shù)為N,特征數(shù)為D′，真實簇數(shù)為K，觀測點數(shù)量為P.按照算法流程分步分析其時間復(fù)雜度.

1)計算P個觀測點到數(shù)據(jù)集D的全部樣本點距離的時間復(fù)雜度為O(PND′).

2)對于P組距離數(shù)組,分別進行近似最佳GMM搜索，設(shè)Mbest為距離數(shù)組對應(yīng)的最佳GMM構(gòu)件數(shù)量，1.2節(jié)中已推導(dǎo)得出搜索過程時間復(fù)雜度為O(NMbest)，則該步驟總時間復(fù)雜度為O(PNMbest).

3)對P個最佳GMM的每個構(gòu)件包含樣本進行候選中心點的選擇，具體采用DPC選取密度峰值點作為候選中心點.對于樣本為n的數(shù)據(jù)集，若直接計算距離矩陣，時間復(fù)雜度為O(n2)，通過R*-Tree[28]可快速計算與鄰近點的距離，DPC時間復(fù)雜度為O(nlog2n).每個構(gòu)件平均包含樣本數(shù)為N/Mbest，則該步驟總時間復(fù)雜度為

即

4)候選中心點個數(shù)為βK，β∈[1,P]，計算全部候選中心點的構(gòu)件分量的時間復(fù)雜度為O(βKP)，計算相異度矩陣,得出對應(yīng)融合無向圖的時間復(fù)雜度為O(β2K2)，求解對應(yīng)連通分量的時間復(fù)雜度為O(βK)，則總時間復(fù)雜度為O(P2K2).

5)融合后的初始中心點作為輸入?yún)?shù)進行K-means聚類，時間復(fù)雜度為O(KD′N).

I-niceCF所需觀測點數(shù)量P最多為D′+1，且Mbest∈[1,K].綜合上述步驟，I-niceCF的平均時間復(fù)雜度為O(Nlog2N)，最差時間復(fù)雜度為O(N2).相比其它不需輸入簇數(shù)作為先驗參數(shù)的傳統(tǒng)聚類算法，時間復(fù)雜度與DBSCAN(Density Based Spatial Clustering of Applications with Noise)[23]、點排序識別聚類結(jié)構(gòu)的聚類算法[29]、基于分布的大型空間數(shù)據(jù)庫聚類算法[30]相同，具有較優(yōu)的計算效率.該算法時間復(fù)雜度顯著優(yōu)于圍繞中心劃分的聚類算法[31]的O(N2K3)及譜聚類的O(N2K),差于K-means算法和BIRCH(Balanced Iterative Reducing and Clustering Using Hierarchies)[32]等需簇數(shù)作為參數(shù)的算法的時間復(fù)雜度，其中K-means算法時間復(fù)雜度為O(tKN)，t表示K-means算法的迭代次數(shù)，BIRCH的時間復(fù)雜度為O(N).

2 實驗及結(jié)果分析

2.1 實驗設(shè)置

本文實驗在真實場景數(shù)據(jù)集和合成數(shù)據(jù)集上進行.真實數(shù)據(jù)集來自加州大學(xué)歐文分校機器學(xué)習(xí)庫(http://archive.ics.uci.edu/ml)及開源手寫字體庫[33]，實驗前均剔除時間戳字段并進行歸一化，具有多標(biāo)簽的數(shù)據(jù)集只選用單個字段作為標(biāo)簽，Anuran數(shù)據(jù)集使用Species作為標(biāo)簽字段.合成數(shù)據(jù)集采用多個高斯分布生成.真實數(shù)據(jù)集與合成數(shù)據(jù)集的具體信息分別見表1和表2.

表1 真實數(shù)據(jù)集信息Table 1 Information of real-world datasets

表2 合成數(shù)據(jù)集信息Table 2 Information of synthetic datasets

本文選擇如下2個指標(biāo)進行聚類結(jié)果的評價：調(diào)整蘭德系數(shù)(Adjusted Rand Index, ARI)[34]和標(biāo)準(zhǔn)化互信息(Normalized Mutual Information, NMI)[35].

ARI計算公式如下:

設(shè)C={C1,C2,…,Cr}表示N個樣本到r個簇的一個劃分，Y={Y1,Y2,…,Ys}表示N個樣本到s個類的一個劃分.nij=|Ci∩Yj|，表示2個劃分中同時位于簇Ci和類Yj的樣本個數(shù)，ni表示簇Ci的總樣本個數(shù)，nj表示類Yj的總樣本個數(shù).NMI計算公式如下：

其中，C表示簇標(biāo)簽，Y表示類標(biāo)簽，H(·)表示熵，I(Y;C)表示其互信息.

ARI和NMI的指標(biāo)值越大，表示聚類結(jié)果越優(yōu).

實驗主機處理器信息為Intel Core i7-10700 CPU@2.90 GHz×16，內(nèi)存容量為15.4 GB，操作系統(tǒng)為ubuntu 16.04LTS 64-bit.實驗涉及程序均運行于Python 3.5.實驗進行時對I-niceMO和I-niceCF共有的參數(shù)賦予相同值，若無特別說明，觀測點數(shù)量均設(shè)為5,過濾系數(shù)設(shè)為(1,0.1).此外兩種算法分治環(huán)節(jié)的各構(gòu)件(或子集)內(nèi)的聚類任務(wù)均采用DPC.

2.2 合理性驗證

本節(jié)評估I-niceCF的簇數(shù)估計效果，與Elbow[11]、Silhouette[12]、Gap統(tǒng)計量[13]、Jump me-thod[15]、I-niceMO[25]進行對比.在5個真實數(shù)據(jù)集和5個合成數(shù)據(jù)集上進行實驗，結(jié)果如表3所示.

由表3可知，I-niceCF簇數(shù)估計效果明顯優(yōu)于包括I-niceMO在內(nèi)的其它算法.當(dāng)數(shù)據(jù)集簇數(shù)低于10時，Elbow和Silhouette存在約1～2的估計誤差.數(shù)據(jù)集簇數(shù)超過10時， Elbow開始失效，估計結(jié)果偏差很

表3 各算法在不同數(shù)據(jù)集上的簇數(shù)估計效果對比Table 3 Comparison of cluster number estimation results of different algorithms on different datasets

大或曲線無“肘部”特征，Silhouette估計結(jié)果誤差也逐漸增大.當(dāng)數(shù)據(jù)集簇數(shù)達(dá)到1 000時，估計誤差已達(dá)到202,而Gap統(tǒng)計量在數(shù)據(jù)集簇數(shù)超過10時已失效，曲線呈上漲趨勢.Jump method在5個簇數(shù)較大的合成數(shù)據(jù)集上的估計效果顯著優(yōu)于Elbow、Silhouette和Gap統(tǒng)計量，但在5個真實數(shù)據(jù)集上表現(xiàn)不佳.I-niceMO受維度較高和數(shù)據(jù)集不平衡的困擾，在真實數(shù)據(jù)集上存在個別誤差，在合成數(shù)據(jù)集上明顯優(yōu)于Elbow和Silhouette，但在簇數(shù)達(dá)到1 000時，I-niceMO無法在合理時間內(nèi)得出結(jié)果.I-niceCF幾乎準(zhǔn)確估計全部數(shù)據(jù)集的簇數(shù)，僅在面對具有1 000個簇的SID5數(shù)據(jù)集時，存在簇數(shù)估計偏差為3，I-niceCF估計出997個簇，此時其余算法除Jump method之外均已無法發(fā)揮作用，由此驗證I-niceCF的簇數(shù)估計效果.

2.3 可行性驗證

本節(jié)測試I-niceCF在不同數(shù)據(jù)集上的表現(xiàn)，驗證本文針對I-nice候選中心融合方法的改進對I-niceMO的提升,以及驗證I-niceCF在多種場景下的可行性.

考慮數(shù)據(jù)集的5個因素，分別為數(shù)據(jù)集的簇數(shù)K、單簇樣本量CN、數(shù)據(jù)集的維度D、簇心距離差異程度σncd、數(shù)據(jù)集平衡度S.其中簇心距離差異程度和數(shù)據(jù)集平衡度是評估的重點，此處分別定義2個指標(biāo)如下：

σncd計算每個簇的簇心ci與對應(yīng)最近簇心cnearest(i)的距離di，求得d1,d2,…,dK的標(biāo)準(zhǔn)差為σncd.簇數(shù)相同時，σncd越大表示對應(yīng)數(shù)據(jù)集的各簇心之間距離差異越大.S表示數(shù)據(jù)集的平衡程度，計算每個簇包含樣本數(shù)占數(shù)據(jù)集樣本總數(shù)的比例π1,π2,…,πK，計算得出對應(yīng)的熵，以此度量數(shù)據(jù)集平衡程度.簇數(shù)相同時，S越小表示數(shù)據(jù)集越不平衡，即不同簇所含樣本數(shù)差異越大.

圖5和圖6分別表示σncd和S取不同值時數(shù)據(jù)集情況.

基于這5個因素，每組分別生成4個合成數(shù)據(jù)集，5組共20個數(shù)據(jù)集，詳見表4.

(a)S=1.0 (b)S=0.65 (c)S=0.44 (d)S=0.19圖6 S不同時數(shù)據(jù)集情況Fig.6 Datasets with different S

(a)σncd=2.768 (b)σncd=19.06 (c)σncd=78.03 (d)σncd=142.9圖5 σncd不同時數(shù)據(jù)集的簇中心點圖Fig.5 Cluster centers of datasets with different σncd

表4 I-niceMO和I-niceCF在20個合成數(shù)據(jù)集上的簇數(shù)估計結(jié)果對比Table 4 Comparison of cluster number estimation results of I-niceMO and I-niceCF on 20 synthetic datasets

因素K生成的4個數(shù)據(jù)集簇數(shù)分別為5,15,25,50，每個數(shù)據(jù)集內(nèi)各簇樣本數(shù)相同，單簇樣本數(shù)均為100，數(shù)據(jù)維度(即特征數(shù))均為2.因素CN生成的數(shù)據(jù)集均為2維5簇，單簇樣本從100逐步增至2 000，每個數(shù)據(jù)集內(nèi)各簇大小相同.因素D生成的4個數(shù)據(jù)集維度逐步增加.因素σncd生成的4個數(shù)據(jù)集對應(yīng)σncd分別為2.786,19.06,78.03,142.9.因素S生成的4個數(shù)據(jù)集的平衡度依次減少，分別為2.322，1.914，1.635，1.213.

在20個合成數(shù)據(jù)集上使用I-niceMO和I-niceCF進行簇數(shù)估計，結(jié)果如表4所示.由表可知，在5組數(shù)據(jù)中，單簇樣本量CN、維度D的變動對于I-niceMO和I-niceCF性能無影響，10個數(shù)據(jù)集均能準(zhǔn)確估計簇數(shù).

簇數(shù)K增加至50時，I-niceMO性能出現(xiàn)一定波動，估計簇數(shù)為44，與真實簇數(shù)相差為6，I-niceCF估計簇數(shù)為51.在σncd影響下，盡管Std3、Std4數(shù)據(jù)集上真實簇數(shù)僅為5，但I-niceMO錯誤估計簇數(shù)為6和9，這是因為σncd(Std3)=78.03,σncd(Std4)=142.9，簇心距離差異較大，導(dǎo)致存在冗余的候選中心未被合并.

圖7為I-niceCF對Std1～Std4數(shù)據(jù)集的候選中心融合情況，I-niceCF準(zhǔn)確合并屬于同個真實簇的候選中心.

(a)Std1 (b)Std2 (c)Std3 (d)Std4圖7 I-niceCF在4個數(shù)據(jù)集上的候選中心融合情況Fig.7 Candidate center fusion for I-niceCF on 4 datasets

如圖7(d)所示,I-niceCF在簇間距離差異很大時仍保持候選中心的正確融合，準(zhǔn)確估計σncd生成的4個數(shù)據(jù)集的簇數(shù)，驗證針對候選中心的融合方法的有效性.在S影響下，I-niceMO伴隨著數(shù)據(jù)集平衡度的減小，性能出現(xiàn)下降，在數(shù)據(jù)集簇數(shù)僅為5時，分別做出簇數(shù)為8和11的錯誤估計，而I-niceCF對于S1～S4數(shù)據(jù)集均做出正確簇數(shù)估計.相比I-niceMO，I-niceCF在全部5個因素的20個數(shù)據(jù)集上始終保持穩(wěn)定準(zhǔn)確的簇數(shù)估計效果，驗證I-niceCF在面對多種類型數(shù)據(jù)集時的穩(wěn)定性能.

2.4 有效性驗證

本節(jié)通過計算ARI、NMI值，評估I-niceCF的聚類結(jié)果，并對比其它聚類算法，包括1)同類型的I-niceMO[25]，2)無需簇數(shù)作為先驗參數(shù)的DBSCAN[23]和DPC[24]，3)需要預(yù)先輸入正確簇數(shù)作為參數(shù)的FCM(FuzzyC-mean)[36-37]和K-means算法[1].

在實驗過程中，I-niceMO和I-niceCF的設(shè)置將遵照2.1節(jié)實驗設(shè)置，另外將真實簇數(shù)作為先驗參數(shù)賦予FCM和K-means.K-means算法重復(fù)10次實驗，每次均隨機生成對應(yīng)數(shù)量的初始中心點，取10次結(jié)果的ARI和NMI值的平均值作為K-means算法的最終結(jié)果.DBSCAN和DPC將以不同參數(shù)多次運行，取得最佳結(jié)果的一次用于對比，即

具體地，DBSCAN的參數(shù)minPts在1至50內(nèi)多次選擇，參數(shù)eps在dn至50dn的范圍內(nèi)[38]多次選擇，其中dn表示數(shù)據(jù)集每個樣本點到對應(yīng)的最近樣本點的平均距離.

各算法聚類實驗的ARI和NMI值如表5和表6所示，表中黑體數(shù)字表示最優(yōu)值.除了在USP40、WDBC數(shù)據(jù)集上I-niceCF的精度與輸入正確簇數(shù)的FCM和K-means的精度持平，在其余數(shù)據(jù)集上I-niceCF精度均優(yōu)于FCM和K-means.I-niceCF在全部數(shù)據(jù)集上都得到最高的ARI、NMI值，優(yōu)于包含I-niceMO在內(nèi)的其它對比算法,由此驗證I-niceCF的有效性.

表5 各算法的聚類結(jié)果對比Table 5 Comparison of clustering results by different algorithms

2.5 參數(shù)敏感性評估

本節(jié)考察I-niceCF的參數(shù)敏感性，I-niceCF的主要參數(shù)為觀測點數(shù)量P及過濾系數(shù)(fkde,fdpc).fkde表示在對各構(gòu)件所含樣本進行高密度點(候選中心)選擇前，對構(gòu)件內(nèi)樣本的過濾比例.具體是通過KDE擬合構(gòu)件對應(yīng)的距離數(shù)組得到對應(yīng)的密度值，保留較高密度值對應(yīng)的距離值，保留比例為fkde.該設(shè)置主要是在大規(guī)模數(shù)據(jù)上可通過過濾一定比例的低密度點，減少后續(xù)進行高密度點尋找的代價.本文的實驗環(huán)節(jié)均設(shè)置fkde=1.0，即全部保留.fdpc的取值則影響使用DPC對每個GMM構(gòu)件對應(yīng)樣本進行高密度點識別時的截斷距離dc，具體為

dc=disasc[ddpc·Len(disasc)]，

其中disasc為升序排序的樣本點間距離數(shù)組.DPC對應(yīng)于dc取值的魯棒性已得到說明[39],因此，本文重點考察I-niceCF關(guān)于參數(shù)觀測點數(shù)量P的敏感性.

對于D維空間中的2個不同樣本點a、b，必有多個觀測點o1,o2,…,oD+1，滿足

在20個不同數(shù)據(jù)集(數(shù)據(jù)集詳情見表4)上測試I-niceCF在不同觀測點數(shù)量時的聚類效果，ARI、NMI值如圖8所示.在(a)～(d)子圖中，當(dāng)P=2時，I-niceCF在4個數(shù)據(jù)集上均未取得正確結(jié)果，隨著觀測點的增加，I-niceCF的聚類性能變優(yōu)，P=4時已全部正確聚類.(e)～(h)、(q)～(t)子圖中的聚類表現(xiàn)類似，都能在P≤5時實現(xiàn)正確聚類.在(i)～(p)子圖中，D、σncd生成的8個數(shù)據(jù)集的ARI、NMI值上漲趨勢慢于其余12個數(shù)據(jù)集，尤其是在(k)～(l)子圖中，它們對應(yīng)的D3、D4數(shù)據(jù)集的特征數(shù)(維度)分別達(dá)到50和500，但最終也都在P≤5時實現(xiàn)正確聚類.由圖8可知，較少的觀測點數(shù)量P即可實現(xiàn)在不同數(shù)據(jù)集上的準(zhǔn)確聚類任務(wù)，包括高維數(shù)據(jù)集.

(a)K1 (b)K2 (c)K3

2.6 算法效率評估

本節(jié)測試I-niceCF和I-niceMO在不同規(guī)模數(shù)據(jù)集上的運行時間，結(jié)果如圖9所示.

圖9 I-niceCF和I-niceMO在不同規(guī)模數(shù)據(jù)集上的運行時間對比Fig.9 Running time comparison of I-niceCF and I-niceMO on datasets of different scales

I-niceCF平均時間復(fù)雜度為O(Nlog2N)，而I-niceMO的時間復(fù)雜度為O(N2)，運行時間增長趨勢顯著快于I-niceCF.此外數(shù)據(jù)規(guī)模大于30 000時，I-niceMO的運行時間和內(nèi)存占用非常大.I-niceMO的最佳GMM遍歷搜索策略不適應(yīng)于較大規(guī)模的數(shù)據(jù)，計算復(fù)雜度與數(shù)據(jù)集上真實簇數(shù)的平方成正比.I-niceCF的粗細(xì)粒度結(jié)合的搜索策略大幅降低算法的運行時間.

上述為單機情況下算法的效率評估，此外，I-niceCF的計算流程(見圖4)使其在當(dāng)下分布式平臺上更容易部署且更高效.

3 結(jié) 束 語

本文提出基于候選中心融合的多觀測點聚類算法(I-niceCF)，改進I-niceMO的聚類效果.I-niceMO在數(shù)據(jù)集內(nèi)簇大小不平衡或簇心距離差異過大時聚類性能出現(xiàn)波動.為了解決這些問題，本文提出粗細(xì)粒度結(jié)合的混合模型搜索策略，使I-niceCF可快速求解最佳混合高斯模型，并進行子集劃分，提升I-niceCF在不平衡數(shù)據(jù)集上的擬合精度和效率.基于GMM構(gòu)件向量,提出候選中心融合方法，進行I-nice候選中心之間的相異度度量與集成.

在真實數(shù)據(jù)集和合成數(shù)據(jù)集上評估I-niceCF的簇數(shù)估計效果,并基于5個因素(簇數(shù)、單簇樣本量、維度、數(shù)據(jù)集平衡度和簇心距離差異程度)驗證I-niceCF在不同數(shù)據(jù)集上的合理性，克服I-niceMO的缺點.此外，進行聚類精度對比實驗，結(jié)果表明I-niceCF的聚類效果較優(yōu).I-nice多觀測點投影機制適合在分布式環(huán)境下工作，結(jié)合候選中心融合方法，今后將探究如何將該方式應(yīng)用于其它聚類算法的分布式部署和集成.