基于數(shù)據(jù)流的聚類趨勢(shì)分析算法

樊仲欣

（大氣科學(xué)與環(huán)境氣象國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心（南京信息工程大學(xué)），江蘇南京210044）

0 引言

聚類是數(shù)據(jù)挖掘的一個(gè)重要研究領(lǐng)域，它通過(guò)對(duì)無(wú)類別標(biāo)簽數(shù)據(jù)的屬性（如距離、密度、分布等）進(jìn)行無(wú)監(jiān)督學(xué)習(xí)，從而將數(shù)據(jù)劃分成多個(gè)簇，并使得簇內(nèi)的數(shù)據(jù)在屬性上具有高相似性，而簇間的數(shù)據(jù)則在屬性上相似性低。聚類趨勢(shì)分析是聚類的前期預(yù)處理步驟，其意義在于確定數(shù)據(jù)是否具備可聚類性，及其可聚類性的強(qiáng)弱，以便于在此基礎(chǔ)上判斷是否有繼續(xù)進(jìn)行聚類操作的必要性以及聚類結(jié)果的可信程度，這對(duì)于必然會(huì)得到一個(gè)聚類結(jié)果的各種聚類算法來(lái)說(shuō)不僅能節(jié)省計(jì)算成本（尤其是大數(shù)據(jù)集的計(jì)算成本），而且也可以作為聚類的一個(gè)先驗(yàn)指標(biāo)。

目前聚類趨勢(shì)分析研究主要分三個(gè)方面［1］：1）基于統(tǒng)計(jì)檢驗(yàn)的方法，以 Hopkins［2］、Cow-Lewis［3］、T-平方（T-squared）［4-5］和 Elberhardt［6］統(tǒng)計(jì)量為主要代表；2）基于圖論的方法，以 IC聚類趨勢(shì)指數(shù)（Clustering Tendency Index）［7］為代表；3）基于可視化分析的方法，以VAT（Visual Assessment of cluster Tendency）［8］、sVAT（scalable VAT）［9］、bigVAT（VAT for large datasets）［10］、SpecVAT（Spectral VAT）［11］、cSpecVAT（cosine metric SpecVAT）和 GMMMVS-VAT（Gaussian Mixture Model and Multi-Viewpoint based Similarity VAT）［12］為代表。這些方法中統(tǒng)計(jì)檢驗(yàn)依賴于假設(shè)檢驗(yàn)，應(yīng)用空間抽樣原理基于不同的最近鄰模式建立Hopkins 等各種統(tǒng)計(jì)量。由于該方法實(shí)現(xiàn)簡(jiǎn)單且時(shí)間空間復(fù)雜度低，所以實(shí)踐應(yīng)用較多，其中Hopkins統(tǒng)計(jì)量應(yīng)用在電力負(fù)荷預(yù)測(cè)［13］、UCI 機(jī)器學(xué)習(xí)庫(kù)的混合型數(shù)據(jù)聚類［14］，T-平方統(tǒng)計(jì)量應(yīng)用在電鐵W 牽引負(fù)載模型建模［15］等方面都已有成功先例。圖論方法將多維空間的數(shù)據(jù)看作是一個(gè)無(wú)向圖，如果圖中不同簇的頂點(diǎn)都是相鄰的，那么稱其為K部完全圖，算法利用地圖著色原理提出了IC指數(shù)，該指數(shù)表示建立K部完全圖需要增加的邊數(shù)。可視化分析方法通過(guò)將數(shù)據(jù)的相異度信息用灰度圖像的形式進(jìn)行展示以判斷是否具有潛在聚類結(jié)構(gòu)。最初的VAT 方法因?yàn)楦邥r(shí)間復(fù)雜度（數(shù)據(jù)量的平方）而不適用于大樣本或關(guān)聯(lián)數(shù)據(jù)集，因此改進(jìn)的sVAT 和bigVAT 算法用采樣技術(shù)以及二維剖面圖代替相異度圖的辦法在一定程度上解決了上述問(wèn)題，而后來(lái)SpecVAT、cSpecVAT、GMMMVS-VAT 方法的提出又進(jìn)一步提高了可視化方法的聚類效果判斷精準(zhǔn)度，并將其適用的數(shù)據(jù)集類型擴(kuò)展到了圖像和視頻上。

然而，上述各種聚類趨勢(shì)分析算法均存在兩個(gè)問(wèn)題有待解決：

1）抽樣導(dǎo)致的聚類趨勢(shì)指標(biāo)不穩(wěn)定以及片面性。Hopkins 統(tǒng)計(jì)量需要隨機(jī)均勻抽樣，因此指標(biāo)穩(wěn)定性差，尤其是在高維度稀疏數(shù)據(jù)集的情況下；Cow-Lewis雖然在高維空間檢測(cè)有優(yōu)勢(shì)，但有時(shí)的結(jié)果片面不穩(wěn)定；T-平方在實(shí)踐中效果相對(duì)較好，但是抽樣窗口在高維度空間中的設(shè)置難度很大，容易導(dǎo)致指標(biāo)不穩(wěn)定；而Elberhardt 也和T-平方存在同樣的問(wèn)題［1］。

2）現(xiàn)有的聚類趨勢(shì)算法是針對(duì)離線數(shù)據(jù)設(shè)計(jì)的，因此不適用于數(shù)據(jù)流這種在線動(dòng)態(tài)增量數(shù)據(jù)的聚類。近年來(lái)，基于實(shí)時(shí)數(shù)據(jù)的數(shù)據(jù)挖掘越來(lái)越受重視，因此涌現(xiàn)出了不少基于數(shù)據(jù)流的聚類方法，如在具有噪聲的基于密度的聚類方法（Density-Based Spatial Clustering of Applications with Noise，DBSCAN）［16］的基礎(chǔ)上出現(xiàn)了增量 DBSCAN［17］和批量增量DBSCAN［18］的 算 法 ，以 及 其 改 進(jìn) 算 法 R-DBSCAN（Rough-DBSCAN）［19］、DG2CEP（Density-Grid Clustering using Complex Event Processing）［20］等用于流數(shù)據(jù)識(shí)別［19，21］，但是這些算法都忽視了聚類趨勢(shì)分析的重要性，所以只能實(shí)現(xiàn)定量數(shù)據(jù)（單個(gè)數(shù)據(jù)或固定量多個(gè)數(shù)據(jù)）的增量聚類。而現(xiàn)有的聚類趨勢(shì)分析算法中，抽樣技術(shù)應(yīng)用于遞增數(shù)據(jù)序列時(shí)需要每增一項(xiàng)數(shù)據(jù)就重復(fù)進(jìn)行一次抽樣，這樣無(wú)法充分利用數(shù)據(jù)的動(dòng)態(tài)特性。圖論方法構(gòu)造K 部完全圖需要數(shù)據(jù)完備，因此也不適合應(yīng)用在動(dòng)態(tài)增量數(shù)據(jù)序列上?？梢暬治龇椒ㄔ缙诘腣AT、sVAT和bigVAT 效率低、耗時(shí)長(zhǎng)，且只適用于相異度矩陣是方陣的情況，后來(lái)提出的 SpecVAT、cSpecVAT、GMMMVS-VAT 方法雖然提高了適用范圍和準(zhǔn)確性，但是由于使用到了譜方法（需要數(shù)據(jù)一次性到齊）并且需要確定特征向量的選取個(gè)數(shù)，因此算法復(fù)雜且耗時(shí)更久，也不適用于增量性的數(shù)據(jù)流。

因此，本文提出了一種可以適應(yīng)數(shù)據(jù)流的基于全體數(shù)據(jù)最小距離連通圖（Minimum Distance Connected Graph，MDCG）的聚類趨勢(shì)算法——MDCG-CTI（Clustering Tendency Index analysis algorithm based on MDCG）來(lái)解決上述問(wèn)題。

1 聚類趨勢(shì)算法原理

本文算法的實(shí)現(xiàn)原理如下：

1）針對(duì)全體數(shù)據(jù)生成MDCG，同時(shí)使圖的生成可以適應(yīng)數(shù)據(jù)流的遞增數(shù)據(jù)序列進(jìn)行動(dòng)態(tài)調(diào)整，從而大幅度降低時(shí)間復(fù)雜度；

2）以MDCG為基礎(chǔ)，用肘閾值分割出簇間和簇內(nèi)的邊，再綜合變異系數(shù)、均值等統(tǒng)計(jì)量，計(jì)算增量數(shù)據(jù)序列的聚類趨勢(shì)指數(shù)；

3）根據(jù)聚類趨勢(shì)指數(shù)動(dòng)態(tài)決定批量遞增的數(shù)據(jù)量，確保后續(xù)聚類的有效性及運(yùn)行效率。

1.1 建立遞增數(shù)據(jù)序列的MDCG

定義1 最小距離連通圖（MDCG）。由n 個(gè)頂點(diǎn)的唯一標(biāo)識(shí)集合ID 和n - 1 條連接頂點(diǎn)的邊集E 組成的圖中，如果圖無(wú)向無(wú)環(huán)，且這n - 1 條邊是n 個(gè)頂點(diǎn)按照最鄰近距離連接而成的，其中任意兩個(gè)頂點(diǎn)間都有一條唯一的最鄰近路徑，則稱該圖為最小距離連通圖MDCG［ID，E］，如圖1。

圖1 最小距離連通圖示意圖Fig. 1 Schematic diagram of MDCG

基于增量數(shù)據(jù)動(dòng)態(tài)生成最小距離連通圖MDCG［ID，E］：

步驟1 初始頂點(diǎn)數(shù)據(jù)X 為空，MDCG 的唯一標(biāo)識(shí)集合ID 和最鄰近邊集 E 也為空，新增數(shù)據(jù) x1={x11，x12，…，x1m，id1}后，X =[x11，x12，…，x1m，id1]，ID ={id1}，后 ， X =其中：m表示頂點(diǎn)數(shù)據(jù)的維度；d21表示第1個(gè)和第2個(gè)頂點(diǎn)間的歐氏距離（簡(jiǎn)稱頂點(diǎn)距離）；id1和id2表示第1 個(gè)和第2 個(gè)頂點(diǎn)數(shù)據(jù)的唯一標(biāo)識(shí)（簡(jiǎn)稱頂點(diǎn)）。按new=｛3，4，…，n｝的順序依次執(zhí)行步驟2～6。

步驟 2 計(jì)算新增數(shù)據(jù) xnew={xnew1，xnew2，…，xnewm，idnew}（new=｛3，4，… ，n｝）和 X 的 所 有 歐 氏 距 離 集 合 D ={dnew1，dnew2，…，dnew(new-1)}，并同時(shí)記錄下D的首個(gè)最小頂點(diǎn)距離 dnewi以及其對(duì)應(yīng)的頂點(diǎn) idi作為新增邊 [idnew，idi，dnewi]加入最鄰近邊集E成為新增行。

步驟 3 令棧數(shù)據(jù)結(jié)構(gòu) ST 為空，將邊[idnew，idi，dnewi]作為一項(xiàng)數(shù)據(jù)入棧，再設(shè)置檢索排除頂點(diǎn)數(shù)據(jù)唯一標(biāo)識(shí)集合為EXI ={idnew}。

步驟4 棧ST 數(shù)據(jù)出棧，出棧的數(shù)據(jù)項(xiàng)表示為[idj，idk，djk]，EXI = EXI ∪ {idk}，然后在最鄰近邊集 E 中檢索出1 條一個(gè)頂點(diǎn)為idk且另一頂點(diǎn)idka不在集合EXI 中的邊ek。如果 ek存在，則將剛出棧的數(shù)據(jù)[idj，idk，djk]入棧，以及將 ek中的頂點(diǎn)順序調(diào)整為{idk，idka}后再將[idk，idka，dkka]入棧，調(diào)用步驟5 并返回。如果ek不存在且棧ST也為空（此時(shí)出棧的數(shù)據(jù)項(xiàng) [idj，idk，djk]=[idnew，idi，dnewi]且idk無(wú)法拓展出EXI以外的頂點(diǎn)），則在最鄰近邊集E中檢索出1 條一個(gè)頂點(diǎn)為idj且另一頂點(diǎn)idja不在集合EXI中的邊ej。如果ej存在，則將ej中的頂點(diǎn)順序調(diào)整為{idj，idja}后再將 [idj，idja，djja]入棧，調(diào)用步驟 5并返回。重復(fù)本步驟直到EXI=ID∪{idnew}，或者距離集合D中小于最鄰近邊集E的頂點(diǎn)距離最大值的所有距離D2 ={dnewp，dnewq，…，dnewq}（D2 ?D）對(duì) 應(yīng) 的ID2 ={idp，idq，…，idq}（ID2 ?ID）全部屬于EXI，則進(jìn)入步驟6。

步驟5 遍歷棧ST，獲取棧的各條邊數(shù)據(jù)中頂點(diǎn)距離的首個(gè)最大值dm1m2所在邊em1m2=[idm1，idm2，dm1m2]，如果dm1m2大 于 距 離 集 合D中idnew到idm2（idm2∈ID）的 距 離dnewm2（dnewm2∈D），則從最鄰近邊集E中刪除邊em1m2并新增邊enewm2=[idnew，idm2，dnewm2]，同時(shí)清空棧ST和EXI，并將新增邊enewm2入棧再設(shè)置EXI={idnew}。

步驟6 將xnew加入到X中，將idnew加入到ID中，生成當(dāng)前的頂點(diǎn)數(shù)據(jù)X以及最小距離連通圖MDCG［ID，E］。

步驟1～6 計(jì)算新增頂點(diǎn)的MDCG 流程在于用棧數(shù)據(jù)結(jié)構(gòu)記錄從新增頂點(diǎn)深度優(yōu)先遍歷到當(dāng)前任意一個(gè)已有頂點(diǎn)idexist的最鄰近路徑（該路徑從最鄰近邊集E中選取，因此棧ST的每條邊都包含在最鄰近邊集E的各邊中，但棧中各條邊頂點(diǎn)的先后順序會(huì)根據(jù)路徑拓展順序而有所調(diào)整），然后如果該最鄰近路徑的距離最大值大于了新增頂點(diǎn)到idexist的直接距離，則表示有更短的最鄰近路徑可以生成，因此需要更新E，并清空棧ST和EXI后重新開(kāi)始遍歷。由于使用棧的遍歷過(guò)程中新增頂點(diǎn)到idexist的直接距離在總體趨勢(shì)上是不斷增大的，因此當(dāng)其大于E的最大頂點(diǎn)距離時(shí)便不會(huì)有更短的最鄰近路徑可以生成，此時(shí)E的更新已完成可以提前結(jié)束遍歷。

1.2 基于MDCG計(jì)算聚類趨勢(shì)指數(shù)

定義2 肘閾值。在最小距離連通圖MDCG［ID，E］的最鄰近邊集E中，計(jì)算得到頂點(diǎn)距離差分最大值的連續(xù)相鄰兩個(gè)距離值的均值即為肘閾值。

肘閾值反映的是數(shù)據(jù)序列變化的最大差異閾值，應(yīng)用在MDCG 上即可以分割出簇間距離（大于肘閾值的距離）和簇內(nèi)距離（小于肘閾值的距離），對(duì)于一個(gè)具有明顯聚類趨勢(shì)的MDCG來(lái)說(shuō)，應(yīng)該具有以下三個(gè)特性：

1）簇內(nèi)距離數(shù)量遠(yuǎn)大于簇間距離數(shù)量。

2）簇內(nèi)距離的均值遠(yuǎn)小于簇間距離均值。

3）簇內(nèi)距離的變異系數(shù)遠(yuǎn)小于整體距離的變異系數(shù)。

上述三個(gè)特性中：第1 點(diǎn)反映的是簇內(nèi)可聚類數(shù)據(jù)的數(shù)據(jù)量，越大越好；第2 點(diǎn)反映的是簇內(nèi)和簇間距離的差異性，越大越好；第3 點(diǎn)反映的是簇內(nèi)和數(shù)據(jù)總體在離散程度上的差異性，越大越好。因此得出聚類趨勢(shì)指數(shù)RMDCGCTI如下：

其中：num_s表示簇內(nèi)距離數(shù)量，num_b表示簇間距離數(shù)量；mean_s表示簇內(nèi)距離均值，mean_b表示簇間距離均值；cv_s表示簇內(nèi)距離變異系數(shù)，cv_a表示全部距離變異系數(shù)。式（4）對(duì)式（1）～（3）求均值，RMDCGCTI的數(shù)據(jù)范圍是[-1，1)。

為確定RMDCGCTI的聚類趨勢(shì)閾值，使用eye 數(shù)據(jù)集進(jìn)行逐項(xiàng)遞增數(shù)據(jù)的聚類趨勢(shì)指數(shù)分析，該數(shù)據(jù)集有6 000個(gè)二維數(shù)據(jù)，其整體分布如圖2（a），其中簇1至簇3（位于圖2（a）的中心部位）的分布如圖2（b），具有多簇和大量噪點(diǎn)，且各簇的體積不均，形狀也不同。

為方便分析，圖2 的eye 數(shù)據(jù)集數(shù)據(jù)的遞增順序?yàn)榇?（2 500 個(gè)數(shù)據(jù)）、簇 2（250 個(gè)數(shù)據(jù)）、簇 3（250 個(gè)數(shù)據(jù)）、噪點(diǎn)（3 000個(gè)數(shù)據(jù)）。其num_i、mean_i、cv_i和RMDCGCTI隨數(shù)據(jù)量遞增的變化情況如圖3所示。

圖2 eye數(shù)據(jù)集的分布Fig.2 Distribution of eye dataset

通過(guò)分析圖3 可以發(fā)現(xiàn)，當(dāng)數(shù)據(jù)在簇1 中隨機(jī)遞增時(shí)，一開(kāi)始的統(tǒng)計(jì)量波動(dòng)都很大，這是因?yàn)樵跀?shù)據(jù)量極少的情況下，數(shù)據(jù)聚類趨勢(shì)很不明顯，因此各統(tǒng)計(jì)量都會(huì)偏向于極值。但當(dāng)數(shù)據(jù)量超過(guò)100以后各統(tǒng)計(jì)量便基本穩(wěn)定下來(lái)，其中num_i在0.7至0.9的范圍內(nèi)波動(dòng)，mean_i和cv_i在0左右浮動(dòng)，因此RMDCGCTI取值在0.2 至0.4，此時(shí)由于只有單簇簇1，聚類趨勢(shì)是不顯著的，所以RMDCGCTI統(tǒng)計(jì)量較小。但當(dāng)數(shù)據(jù)量超過(guò)2 500，遞增到簇2 和簇3 時(shí)，由于多簇具有顯著的聚類趨勢(shì)，因此mean_i 統(tǒng)計(jì)量上升明顯，num_i略有上升并達(dá)到最大值，cv_i 則有小幅度波動(dòng)，導(dǎo)致了RMDCGCTI統(tǒng)計(jì)量大幅度上升至0.6 左右，此時(shí)具有了顯著的聚類趨勢(shì)。此外值得注意的是在2 500 個(gè)和2 750 個(gè)數(shù)據(jù)（遞增到了新簇簇2 和簇3）的位置時(shí)，mean_i 和cv_i 均有一個(gè)抬升回落的峰值現(xiàn)象，從而使得RMDCGCTI也出現(xiàn)同樣的情況，這是因?yàn)樵谛麓財(cái)?shù)據(jù)量極少時(shí)會(huì)被判定為噪點(diǎn)，而噪點(diǎn)具有數(shù)據(jù)非常分散的特點(diǎn)，因此導(dǎo)致了肘閾值分割后簇間距離（大于肘閾值的距離）數(shù)量的大幅度增加，而后面隨著新簇?cái)?shù)據(jù)量增加簇間距離數(shù)量會(huì)快速減少并達(dá)到穩(wěn)定，因此mean_i 和cv_i 統(tǒng)計(jì)量才出現(xiàn)了峰值。最后在數(shù)據(jù)量超過(guò)3 000 剛剛遞增到噪點(diǎn)時(shí)，mean_i 和cv_i 又出現(xiàn)了峰值，這和數(shù)據(jù)量剛剛遞增到簇2時(shí)情況類似，此時(shí)的RMDCGCTI值亦有所增加，在0.7 至0.8（由于多簇含少量噪點(diǎn)依然是具有顯著聚類趨勢(shì)的，因此RMDCGCTI值的變化是合理的）；但是此后隨著噪點(diǎn)不斷增多，num_i 和mean_i 便逐步下降（mean_i 穩(wěn)步下降，num_i 則在噪點(diǎn)量達(dá)到約1 500 時(shí)會(huì)突然驟降），cv_i則基本保持不變，因此RMDCGCTI也逐步下降并在接近4 500 個(gè)數(shù)據(jù)前降至了0.5 以下，考慮到此時(shí)噪點(diǎn)的數(shù)量已近1 500個(gè)，約為簇?cái)?shù)據(jù)量的50%，而大量的噪點(diǎn)（多噪點(diǎn)）導(dǎo)致了簇的聚類趨勢(shì)不再明顯，所以RMDCGCTI值低于0.5 正體現(xiàn)了這種非顯著性的聚類趨勢(shì)。

圖3 eye數(shù)據(jù)集隨數(shù)據(jù)量遞增的統(tǒng)計(jì)量變化情況Fig. 3 Statistics of eye dataset varying with incremental data

綜上所述，RMDCGCTI統(tǒng)計(jì)量在單簇和多簇的情況下主要受mean_i和cv_i的影響而呈現(xiàn)單簇取值低于0.5，多簇取值高于0.5 的現(xiàn)象，其中mean_i 決定了RMDCGCTI的總體變化趨勢(shì)，cv_i則提升了RMDCGCTI對(duì)新簇出現(xiàn)的敏感性。同時(shí)RMDCGCTI在噪點(diǎn)增多的情況下主要受num_i和mean_i的影響而呈現(xiàn)取值遞減的現(xiàn)象，并最終在大量噪點(diǎn)使得聚類趨勢(shì)不顯著時(shí)減至0.5以下，其中mean_i依然決定了RMDCGCTI的總體變化趨勢(shì)，num_i則進(jìn)一步提升了RMDCGCTI對(duì)噪點(diǎn)減弱聚類趨勢(shì)的敏感性。因此可以認(rèn)為：RMDCGCTI≤0 時(shí)沒(méi)有聚類趨勢(shì)（不可聚類）；RMDCGCTI∈(0，0.5]時(shí)具有不顯著的聚類趨勢(shì)（非顯著可聚類）；RMDCGCTI＞0.5時(shí)則具有顯著聚類趨勢(shì)（顯著可聚類）。

結(jié)合聚類趨勢(shì)分析的批量增量數(shù)據(jù)聚類趨勢(shì)分析的目的是為聚類算法服務(wù)的，因此為了說(shuō)明本文的MDCG-CTI 算法如何與具體的DBSCAN 聚類算法相結(jié)合，給出算法流程如圖4 所示。圖4 的步驟一為MDCG-CTI 算法，預(yù)處理部分要讀取增量DBSCAN 的區(qū)域半徑Eps 和鄰域?qū)ο髷?shù)量MinPts 閾值，以及不斷地在線讀取新增數(shù)據(jù)（m 維數(shù)據(jù)值及其唯一標(biāo)識(shí)符）和刪除數(shù)據(jù)（唯一標(biāo)識(shí)符），然后經(jīng)MDCG-CTI 算法后判斷RMDCGCTI，如 RMDCGCTI≤ 0.5 則將新增的數(shù)據(jù)放入 ΔC 數(shù)據(jù)集合。步驟二，如果RMDCGCTI＞0.5，則要對(duì)ΔC 的新增數(shù)據(jù)進(jìn)行批量增量 DBSCAN［18］。由此可見(jiàn)，由于 MDCG-CTI 算法能檢驗(yàn)出數(shù)據(jù)是否具備可聚類性，因此在批量增量DBSCAN 前先使用MDCG-CTI 算法作為前期步驟，可以實(shí)現(xiàn)先驗(yàn)性的非固定量增量數(shù)據(jù)聚類，這不僅解決了批量增量的數(shù)據(jù)量不易確定的問(wèn)題，而且還可以避免無(wú)效聚類，提高聚類結(jié)果的有效性。

圖4 結(jié)合MDCG-CTI算法的批量增量DBSCAN流程Fig. 4 Flowchart of batch incremental DBSCAN combined with MDCG-CTI algorithm

2 時(shí)間空間復(fù)雜度

首先，MDCG 新增和刪除單個(gè)頂點(diǎn)數(shù)據(jù)的空間復(fù)雜度主要為O(n(m + 2) + n(n - 1)/2 + 3(n - 1))。新增頂點(diǎn)的時(shí)間復(fù)雜度主要為其中：n表示已有數(shù)據(jù)數(shù)量；m 表示數(shù)據(jù)維度；si表示棧ST 的深度；t表示從新增頂點(diǎn)數(shù)據(jù)出發(fā)，在已有數(shù)據(jù)的最鄰近邊集E上深度優(yōu)先地搜索到所有頂點(diǎn)的最鄰近路徑，直到D 中小于E 的最大頂點(diǎn)距離的距離集合D2(D2 ?D)對(duì)應(yīng)的頂點(diǎn)集合ID2(ID2 ?ID)都完成遍歷后的頂點(diǎn)遍歷個(gè)數(shù)，當(dāng)數(shù)據(jù)量足夠大時(shí)，O(t)是遠(yuǎn)小于O(n)的。

其次在MDCG-CTI 算法結(jié)合DBSCAN 增量聚類的運(yùn)行效率方面，先比較新增數(shù)據(jù)情況下增加MDCG-CTI 算法前后的時(shí)間復(fù)雜度。一次nn個(gè)數(shù)據(jù)增量DBSCAN 需要將nn個(gè)數(shù)據(jù)依次加入到已有數(shù)據(jù)的DBSCAN 聚類結(jié)果中（增量過(guò)程：先遍歷已有數(shù)據(jù)查找新增數(shù)據(jù)鄰域半徑Eps 內(nèi)的鄰域?qū)ο驩N1并判斷其數(shù)量是否大于鄰域?qū)ο髷?shù)閾值MinPts，然后再針對(duì)ON1內(nèi)的每個(gè)對(duì)象做一次遍歷，判斷因新增數(shù)據(jù)而增加了鄰域?qū)ο髷?shù)的ON1內(nèi)的每個(gè)對(duì)象，其鄰域半徑Eps內(nèi)的鄰域?qū)ο髷?shù)是否超過(guò)閾值 MinPts），因此其時(shí)間復(fù)雜度為O(nn(nm + nmk1))，其中：n 為已有數(shù)據(jù)量，m 表示數(shù)據(jù)維度，k1為ON1的數(shù)據(jù)量。由此可見(jiàn)，nn次使用增量數(shù)據(jù)MDCG-CTI算法增加的時(shí)間復(fù)雜度為O可能相應(yīng)減少一次無(wú)效的nn個(gè)數(shù)據(jù)增量DBSCAN 的時(shí)間復(fù)雜度O(nn(nm +nmk1))，因?yàn)樵黾覯DCG-CTI 算法后在n 很大的情況下會(huì) 遠(yuǎn) 小 于 O(nmk1)，即 增 加 MDCG-CTI 算 法 后DBSCAN 的時(shí)間增加量會(huì)明顯小于減少量，所以MDCG-CTI算法可以減少時(shí)間消耗、提高聚類的運(yùn)行效率。

3 聚類趨勢(shì)算法應(yīng)用

本文算法使用Windows 10（64 位）和Matlab R2014b 基于一臺(tái) CPU AMD Ryzen9 3900X（12 核）4.6 GHz，內(nèi)存 32 GB 的計(jì)算機(jī)實(shí)現(xiàn)。

選取7個(gè)數(shù)據(jù)集進(jìn)行測(cè)試，比較MDCG-CTI算法和常用聚類趨勢(shì)分析算法Hopkins、T-平方、SpecVAT 之間的運(yùn)行結(jié)果及耗時(shí)情況。數(shù)據(jù)集1～4 是自定義數(shù)據(jù)集，如圖5 所示，其中數(shù)據(jù)集1 如圖5（a），是2 500 個(gè)二維數(shù)據(jù)，呈現(xiàn)單簇?zé)o噪點(diǎn)的分布；數(shù)據(jù)集 2 如圖 5（b），是 5 101 個(gè)二維數(shù)據(jù)，在數(shù)據(jù)集 1 的基礎(chǔ)上增加了2 601個(gè)噪點(diǎn)，呈現(xiàn)單簇多噪點(diǎn)且噪點(diǎn)基本均勻的分布；數(shù)據(jù)集3如圖5（c），是400個(gè)二維數(shù)據(jù)，呈現(xiàn)三個(gè)簇?zé)o噪點(diǎn)的分布；數(shù)據(jù)集4 如圖5（d），是800 個(gè)二維數(shù)據(jù)，在數(shù)據(jù)集3的基礎(chǔ)上增加了400個(gè)噪點(diǎn)，呈現(xiàn)多簇多噪點(diǎn)且噪點(diǎn)非均勻的分布。數(shù)據(jù)集5～7 是加州大學(xué)歐文分校機(jī)器學(xué)習(xí)庫(kù)UCI的 3 個(gè)數(shù)據(jù)集：iris、pendigits 和 avila，其中：iris 也稱鳶尾花卉數(shù)據(jù)集，由150 個(gè)花卉樣本組成，每個(gè)樣本包含4 個(gè)維度；pendigits 是手寫字體數(shù)據(jù)集，由10 992 個(gè)手寫體文字的圖像特征組成，每個(gè)文字的圖像特征有16 個(gè)維度；avila 由阿維拉圣經(jīng)中提取的20 867 個(gè)文字的圖像特征組成，每個(gè)文字的圖像特征有10個(gè)維度。

圖5 自定義數(shù)據(jù)集的分布Fig. 5 Distribution of self-built datasets

表1的4個(gè)數(shù)據(jù)集中，數(shù)據(jù)集1是單簇不可聚類，數(shù)據(jù)集3多簇顯著可聚類，數(shù)據(jù)集2 和4 因?yàn)樵朦c(diǎn)過(guò)多（噪點(diǎn)量大于等于簇?cái)?shù)據(jù)量）所以非顯著可聚類。從這四種聚類趨勢(shì)算法的比較中可以看出，MDCG-CTI 算法對(duì)聚類趨勢(shì)的判斷是完全正確的，但其余三種算法因?yàn)橹粚ふ覕?shù)據(jù)中的自然簇而忽視了噪點(diǎn)過(guò)多會(huì)導(dǎo)致大量數(shù)據(jù)無(wú)法聚類成簇，因此聚類趨勢(shì)不顯著的問(wèn)題，所以Hopkins、T-平方和SpecVAT 對(duì)數(shù)據(jù)集2 和4的聚類趨勢(shì)判斷都不準(zhǔn)確；此外Hopkins 和T-平方對(duì)數(shù)據(jù)集1的聚類趨勢(shì)判斷也是錯(cuò)誤的，這是因?yàn)閮煞N算法均認(rèn)為單簇分布是具有聚類趨勢(shì)的［22］。運(yùn)行耗時(shí)方面，Hopkins和T-平方是具有明顯優(yōu)勢(shì)的，這是因?yàn)槌闃臃椒o(wú)需遍歷全體數(shù)據(jù)，而其耗時(shí)主要取決于抽樣始點(diǎn)個(gè)數(shù)的設(shè)置，設(shè)置得越多抽樣密度越高，結(jié)果的準(zhǔn)確性就相對(duì)越好，但相應(yīng)的耗時(shí)也會(huì)增加。SpecVAT 和MDCG-CTI 相比，前者的耗時(shí)較多，且當(dāng)數(shù)據(jù)量越大時(shí)越明顯，這是因?yàn)樵撍惴ㄒ?jì)算特征向量（時(shí)間復(fù)雜度為數(shù)據(jù)量的三次方），且有可視化操作步驟（需要從不同特征向量個(gè)數(shù)的SpecVAT 相異度圖中用ADNC 算法自動(dòng)確定簇?cái)?shù)）的關(guān)系。因此，綜合準(zhǔn)確性和運(yùn)行耗時(shí)來(lái)看，MDCG-CTI 算法是具有明顯優(yōu)勢(shì)的，其適用于增量數(shù)據(jù)序列的特點(diǎn)不僅帶來(lái)了耗時(shí)相對(duì)較少的優(yōu)點(diǎn)，而且還可以分析全體數(shù)據(jù)（并非抽樣分析）以提高聚類趨勢(shì)判斷的準(zhǔn)確性。

從表2 可以看出，Hopkins 和T-平方在遞增數(shù)據(jù)序列上的表現(xiàn)是100 次運(yùn)行的平均可聚類比率AR（可聚類比率指數(shù)據(jù)在遞增過(guò)程中可聚類判斷次數(shù)占總聚類趨勢(shì)判斷次數(shù)的比值）大于94%，SpecVAT 則在87%以上，這都明顯高于MDCGCTI 的平均顯著可聚類比率，究其原因：一方面是因?yàn)檎`認(rèn)為單簇分布是可聚類的，另一方面則是將含大量噪點(diǎn)的數(shù)據(jù)集判斷為可聚類。所以相比之下，MDCG-CTI 對(duì)聚類趨勢(shì)的判斷要更準(zhǔn)確，從而其相對(duì)較低的可聚類比率在后續(xù)的批量增量DBSCAN 中便可以更有效地減少無(wú)效聚類，降低聚類耗時(shí)，同時(shí)提高聚類結(jié)果的有效性。而從算法各運(yùn)行100 次的可聚類比率標(biāo)準(zhǔn)差ER上來(lái)看，Hopkins 和T-平方基本上在0.01 左右，SpecVAT 在 0.006 左右，MDCG-CTI 則約為 0.003，可見(jiàn)MDCG-CTI 算法的波動(dòng)幅度最小，穩(wěn)定性最高，而Hopkins 和T-平方則因?yàn)槌闃拥年P(guān)系導(dǎo)致結(jié)果相對(duì)片面和不穩(wěn)定。

此外平均累計(jì)耗時(shí)AT方面，Hopkins 和T-平方較低，MDCG-CTI 居中，SpecVAT 最高（SpecVAT 采用的譜方法每增一次數(shù)據(jù)就需要重新計(jì)算一次特征向量和自動(dòng)確定一次簇?cái)?shù)），這和單次的聚類趨勢(shì)計(jì)算耗時(shí)情況（如表1）是一致的，尤 其 在 大 數(shù) 據(jù) 集 pendigits 和 avila 上 ，MDCG-CTI 相 較SpecVAT數(shù)據(jù)遞增平均累計(jì)耗時(shí)降低了38%和42%。

表3 列出了四種聚類趨勢(shì)算法結(jié)合批量增量DBSCAN［18］的聚類結(jié)果，其中Hopkins、T-平方、SpecVAT、MDCG-CTI 四種算法的參數(shù)如表2，DBSCAN 參數(shù)Eps和MinPts采用自適應(yīng)算法［23］自動(dòng)生成，平均準(zhǔn)確率CR計(jì)算如下：

其中：Ni表示第i次隨機(jī)遞增且可聚類的累計(jì)數(shù)據(jù)量，Ci表示Ni中被DBSCAN 正確劃分類別的數(shù)據(jù)量，Nnc表示不可聚類次數(shù)。

表3 中在數(shù)據(jù)按照數(shù)據(jù)量Nadd隨機(jī)遞增的過(guò)程中，由于增加聚類趨勢(shì)算法所減少的若干次不具有聚類趨勢(shì)（不可聚類）的DBSCAN 聚類，其結(jié)果大多是聚類成單簇或噪點(diǎn)過(guò)多而導(dǎo)致準(zhǔn)確率不高，所以用了聚類趨勢(shì)分析算法以后聚類的CR便會(huì)提高，而因MDCG-CTI 的平均可聚類比率AR是最低的（見(jiàn)表2），所以其后續(xù)DBSCAN的聚類CR也就相應(yīng)最高，相較SpecVAT+DBSCAN 在數(shù)據(jù)集pendigits 和avila 上分別提高了6和11個(gè)百分點(diǎn)。此外聚類累計(jì)耗時(shí)T方面，iris數(shù)據(jù)集由于數(shù)據(jù)量小而聚類耗時(shí)很短，所以使用聚類趨勢(shì)算法后耗時(shí)均比不使用要多，且以SpecVAT 最為突出；但是在pendigits和avila兩個(gè)大數(shù)據(jù)集上，聚類趨勢(shì)算法減少DBSCAN 聚類耗時(shí)的優(yōu)點(diǎn)則顯露了出來(lái)，其中Hopkins 由于100%可聚類的關(guān)系（見(jiàn)表2）所以耗時(shí)比只用DBSCAN 多，而其余三種聚類趨勢(shì)算法結(jié)合DBSCAN 后累計(jì)耗時(shí)T都有所減少，且MDCG-CTI 減少得最為明顯，相較SpecVAT+DBSCAN 的聚類累計(jì)耗時(shí)分別降低了7%和8%。

表2 UCI數(shù)據(jù)集上不同算法的平均可聚類比率分布和運(yùn)行耗時(shí)比較（算法各運(yùn)行100次）Tab.2 Comparison of clusterable rate distribution and running time of different algorithms on UCI datasets（100 runs for each algorithm）

表3 UCI數(shù)據(jù)集上不同算法結(jié)合DBSCAN的聚類結(jié)果比較Tab.3 Comparison of clustering results of different algorithms combined with DBSCAN on UCI datasets

4 結(jié)語(yǔ)

本文提出的MDCG-CTI 算法能夠利用動(dòng)態(tài)遞增數(shù)據(jù)的特點(diǎn)，基于數(shù)據(jù)的最小距離連通圖計(jì)算出聚類趨勢(shì)指數(shù)，并通過(guò)實(shí)驗(yàn)分析得出以下結(jié)論：RMDCGCTI≤0 時(shí)不可聚類；0 ＜RMDCGCTI≤ 0.5 時(shí)非顯著可聚類；RMDCGCTI＞ 0.5 則顯著可聚類。時(shí)間復(fù)雜度分析及實(shí)驗(yàn)表明，MDCG-CTI 算法可以提高后續(xù)批量增量DBSCAN 的結(jié)果有效性及運(yùn)行效率；同時(shí)在多個(gè)數(shù)據(jù)集上的比較則表明，MDCG-CTI 算法在損失有限運(yùn)算時(shí)間的前提下可以有效提高聚類趨勢(shì)判斷的準(zhǔn)確性，特別是在處理大數(shù)據(jù)集時(shí)具有不錯(cuò)的性能表現(xiàn)。

未來(lái)的研究將進(jìn)一步提高M(jìn)DCG-CTI 算法在處理大數(shù)據(jù)集上的效率優(yōu)勢(shì)，計(jì)劃從兩個(gè)方面進(jìn)行算法的并行化：一是利用CPU 的多核運(yùn)算能力同時(shí)計(jì)算以頂點(diǎn)idi為出發(fā)點(diǎn)的多條深度優(yōu)先遍歷的最鄰近路徑；二是把算法分為在線和離線兩部分，在線生成最小距離連通圖MDCG［ID，E］，離線統(tǒng)計(jì)聚類趨勢(shì)指數(shù)RMDCGCTI，實(shí)現(xiàn)按需判斷多批量增量數(shù)據(jù)的聚類趨勢(shì)。