陳鴻杰 何玉林 黃哲學(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ù)點(diǎn)圖的拉普拉斯矩陣特征值等信息.簇的成員關(guān)系信息又可進(jìn)一步驅(qū)動數(shù)據(jù)處理的下游任務(wù)，如監(jiān)督分類和半監(jiān)督分類.因此簇的個數(shù)和簇的中心點(diǎn)通常是許多聚類算法關(guān)鍵的先驗(yàn)參數(shù)，需要提前設(shè)定兩者或其一的聚類算法，稱為有參聚類算法，如K-means和譜聚類等.簇數(shù)和初始中心點(diǎn)設(shè)定的好壞對于聚類算法的精度和效率都有很大的影響[3].

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

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

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

2)估計簇個數(shù)和初始中心點(diǎn)的質(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，進(jìn)行簇數(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ǔ)上進(jìn)行修改，提出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在計算上較高效，并且在一系列實(shí)驗(yàn)中得到驗(yàn)證，但其畸變曲線容易出現(xiàn)單調(diào)情況，導(dǎo)致計算全局最優(yōu)無法獲得一個合理的估計值.通過交叉驗(yàn)證能在一定程度上解決該問題，但需付出昂貴的計算成本.此外,Yang等[17]提出M-means(Mountain Means Clustering Algorithm)，在數(shù)據(jù)集的樣本數(shù)超過500時，無法正確估計簇的個數(shù).另外，在數(shù)據(jù)集具有高維特征且簇數(shù)較多的情況下，聚類算法往往需要人工介入、設(shè)計與觀察各種漸進(jìn)統(tǒng)計數(shù)據(jù)，如平均Silhouette寬度，才能獲得較優(yōu)的聚類結(jié)果.Maitra[3]尋找數(shù)據(jù)中的大量局部模式，選取分離程度最大的點(diǎn)作為初始中心點(diǎn)，在一系列實(shí)驗(yàn)上均取得可觀結(jié)果.但當(dāng)數(shù)據(jù)存在大量坐標(biāo)(特征數(shù))時，奇異值分解計算過程變難，阻礙在高維數(shù)據(jù)上的應(yīng)用.

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

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

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

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

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

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

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

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

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

計算數(shù)據(jù)集的全部N個樣本點(diǎn)到某一觀測點(diǎ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ù)集進(jìn)行劃分.

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

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í)驗(yàn)，可設(shè)

Mmax=(1-α)Mbest，

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

Δ1=Δ2=αMbest

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

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

輸入數(shù)據(jù)集Y對應(yīng)觀測點(diǎn)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′

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

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

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

細(xì)粒度搜索階段在(2?log2Mbest」,2「log2Mbest?)區(qū)間進(jìn)行，設(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)件向量相異度的候選中心融合

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

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

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

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

圖1為在包含4個簇的數(shù)據(jù)集上得出的5個候選中心，虛線區(qū)域?yàn)閷?yīng)各簇樣本點(diǎn)的分布情況，5個填充點(diǎn)為待集成的候選中心，cb1、cb2歸屬于同個真實(shí)簇Gb，3個候選中心co、cg、cr分別歸屬于3個真實(shí)簇Go、Gg、Gr.候選中心cg、cr之間的距離小于候選中心cb1、cb2之間的距離，因此基于候選中心相對距離的集成方式無法同時保證合并cb1、cb2且保留cg、cr.按照I-niceMO,基于候選中心的相對距離進(jìn)行集成，會出現(xiàn)兩種錯誤.第1種為過度合并，cb1、cb2合并，cg、cr合并，co保留，雖然成功消除真實(shí)簇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個觀測點(diǎn)的混合模型中對應(yīng)的構(gòu)件索引ζ.并結(jié)合曼哈頓距離和切比雪夫距離設(shè)計閔可夫斯基距離對:

(1)

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

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

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

(a)觀測點(diǎn)1 (b)觀測點(diǎn)2 (c)觀測點(diǎn)3 (d)觀測點(diǎn)4(a)Observation point 1 (b)Observation point 2 (c)Observation point 3 (d)Observation point 4圖2 4個觀測點(diǎn)樣本距離值分布和混合模型概率密度曲線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)以融合相異度小于一定范圍的候選中心點(diǎn)對.具體地，設(shè)定

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

DMC[0]

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

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

matrix of 5 candidate centers

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

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

輸入候選中心c1,c2,…,cm，觀測點(diǎn)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 計算每個連通分量所含候選中心樣本點(diǎn)的均值，得到融合后的中心c′1,c′2,…

在全部觀測點(diǎn)對應(yīng)GMM的各個構(gòu)件的候選中心集成之后，將得到最終的簇數(shù)和融合后的候選中心稱為初始中心點(diǎn).將簇數(shù)及初始中心點(diǎn)作為先驗(yàn)參數(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í)簇數(shù)為K，觀測點(diǎn)數(shù)量為P.按照算法流程分步分析其時間復(fù)雜度.

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

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

即

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

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

I-niceCF所需觀測點(diǎn)數(shù)量P最多為D′+1，且Mbest∈[1,K].綜合上述步驟，I-niceCF的平均時間復(fù)雜度為O(Nlog2N)，最差時間復(fù)雜度為O(N2).相比其它不需輸入簇數(shù)作為先驗(yàn)參數(shù)的傳統(tǒng)聚類算法，時間復(fù)雜度與DBSCAN(Density Based Spatial Clustering of Applications with Noise)[23]、點(diǎn)排序識別聚類結(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 實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

本文選擇如下2個指標(biāo)進(jìn)行聚類結(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).

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

2.2 合理性驗(yàn)證

本節(jié)評估I-niceCF的簇數(shù)估計效果，與Elbow[11]、Silhouette[12]、Gap統(tǒng)計量[13]、Jump me-thod[15]、I-niceMO[25]進(jìn)行對比.在5個真實(shí)數(shù)據(jù)集和5個合成數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(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í)數(shù)據(jù)集上表現(xiàn)不佳.I-niceMO受維度較高和數(shù)據(jù)集不平衡的困擾，在真實(shí)數(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ā)揮作用，由此驗(yàn)證I-niceCF的簇數(shù)估計效果.

2.3 可行性驗(yàn)證

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

考慮數(shù)據(jù)集的5個因素，分別為數(shù)據(jù)集的簇數(shù)K、單簇樣本量CN、數(shù)據(jù)集的維度D、簇心距離差異程度σncd、數(shù)據(jù)集平衡度S.其中簇心距離差異程度和數(shù)據(jù)集平衡度是評估的重點(diǎn)，此處分別定義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ù)集的簇中心點(diǎn)圖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進(jìn)行簇數(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í)簇數(shù)相差為6，I-niceCF估計簇數(shù)為51.在σncd影響下，盡管Std3、Std4數(shù)據(jù)集上真實(shí)簇數(shù)僅為5，但I(xiàn)-niceMO錯誤估計簇數(shù)為6和9，這是因?yàn)棣襫cd(Std3)=78.03,σncd(Std4)=142.9，簇心距離差異較大，導(dǎo)致存在冗余的候選中心未被合并.

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

(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ù)，驗(yàn)證針對候選中心的融合方法的有效性.在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ù)估計效果，驗(yàn)證I-niceCF在面對多種類型數(shù)據(jù)集時的穩(wěn)定性能.

2.4 有效性驗(yàn)證

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

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

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

各算法聚類實(shí)驗(yàn)的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)的其它對比算法,由此驗(yàn)證I-niceCF的有效性.

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

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

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

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

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

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

在20個不同數(shù)據(jù)集(數(shù)據(jù)集詳情見表4)上測試I-niceCF在不同觀測點(diǎn)數(shù)量時的聚類效果，ARI、NMI值如圖8所示.在(a)～(d)子圖中，當(dāng)P=2時，I-niceCF在4個數(shù)據(jù)集上均未取得正確結(jié)果，隨著觀測點(diǎn)的增加，I-niceCF的聚類性能變優(yōu)，P=4時已全部正確聚類.(e)～(h)、(q)～(t)子圖中的聚類表現(xiàn)類似，都能在P≤5時實(shí)現(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時實(shí)現(xiàn)正確聚類.由圖8可知，較少的觀測點(diǎn)數(shù)量P即可實(shí)現(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ù)集上的運(yùn)行時間，結(jié)果如圖9所示.

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

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

3 結(jié) 束 語

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

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