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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義對(duì)應(yīng)GMM為

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

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

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

1.2 最佳混合模型搜索策略

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

Mmax=(1-α)Mbest，

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

Δ1=Δ2=αMbest

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

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

輸入數(shù)據(jù)集Y對(duì)應(yīng)觀測(cè)點(diǎn)p的距離數(shù)組X

輸出近似最佳混合模型GMMbest

階段1粗粒度搜索

form=1;m

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

GMMm(X)；

計(jì)算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

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

計(jì)算AICcm′；

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

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

break

end for

GMMbest=GMM2-2m′

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

DMC[0]

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

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

matrix of 5 candidate centers

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

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

輸入候選中心c1,c2,…,cm，觀測(cè)點(diǎn)O1,O2,…,OP，

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

GMMP(MP,πP,θP)

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

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

其中

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

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

step 4 計(jì)算矩陣

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

并生成對(duì)應(yīng)無(wú)向圖G.

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

step 6 計(jì)算每個(gè)連通分量所含候選中心樣本點(diǎn)的均值，得到融合后的中心c′1,c′2,…

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

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

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

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

即

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

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

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

2 實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

ARI計(jì)算公式如下:

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

其中，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)行時(shí)對(duì)I-niceMO和I-niceCF共有的參數(shù)賦予相同值，若無(wú)特別說(shuō)明，觀測(cè)點(diǎn)數(shù)量均設(shè)為5,過(guò)濾系數(shù)設(shè)為(1,0.1).此外兩種算法分治環(huán)節(jié)的各構(gòu)件(或子集)內(nèi)的聚類任務(wù)均采用DPC.

2.2 合理性驗(yàn)證

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

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

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

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

2.3 可行性驗(yàn)證

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

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

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

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

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

(a)S=1.0 (b)S=0.65 (c)S=0.44 (d)S=0.19圖6 S不同時(shí)數(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í)數(shù)據(jù)集的簇中心點(diǎn)圖Fig.5 Cluster centers of datasets with different σncd

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

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

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

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

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

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

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

2.4 有效性驗(yàn)證

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

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

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

各算法聚類實(shí)驗(yàn)的ARI和NMI值如表5和表6所示，表中黑體數(shù)字表示最優(yōu)值.除了在USP40、WDBC數(shù)據(jù)集上I-niceCF的精度與輸入正確簇?cái)?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)的其它對(duì)比算法,由此驗(yàn)證I-niceCF的有效性.

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

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

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

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

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

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

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

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

2.6 算法效率評(píng)估

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

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

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

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

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

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

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