樊仲欣

（大氣科學與環(huán)境氣象國家級實驗教學示范中心（南京信息工程大學），江蘇南京210044）

0 引言

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

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

然而，上述各種聚類趨勢分析算法均存在兩個問題有待解決：

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

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

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

1 聚類趨勢算法原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

上述三個特性中：第1 點反映的是簇內(nèi)可聚類數(shù)據(jù)的數(shù)據(jù)量，越大越好；第2 點反映的是簇內(nèi)和簇間距離的差異性，越大越好；第3 點反映的是簇內(nèi)和數(shù)據(jù)總體在離散程度上的差異性，越大越好。因此得出聚類趨勢指數(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）對式（1）～（3）求均值，RMDCGCTI的數(shù)據(jù)范圍是[-1，1)。

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

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

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

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

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

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

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

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

2 時間空間復雜度

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

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

3 聚類趨勢算法應用

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

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

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

表1的4個數(shù)據(jù)集中，數(shù)據(jù)集1是單簇不可聚類，數(shù)據(jù)集3多簇顯著可聚類，數(shù)據(jù)集2 和4 因為噪點過多（噪點量大于等于簇數(shù)據(jù)量）所以非顯著可聚類。從這四種聚類趨勢算法的比較中可以看出，MDCG-CTI 算法對聚類趨勢的判斷是完全正確的，但其余三種算法因為只尋找數(shù)據(jù)中的自然簇而忽視了噪點過多會導致大量數(shù)據(jù)無法聚類成簇，因此聚類趨勢不顯著的問題，所以Hopkins、T-平方和SpecVAT 對數(shù)據(jù)集2 和4的聚類趨勢判斷都不準確；此外Hopkins 和T-平方對數(shù)據(jù)集1的聚類趨勢判斷也是錯誤的，這是因為兩種算法均認為單簇分布是具有聚類趨勢的［22］。運行耗時方面，Hopkins和T-平方是具有明顯優(yōu)勢的，這是因為抽樣方法無需遍歷全體數(shù)據(jù)，而其耗時主要取決于抽樣始點個數(shù)的設(shè)置，設(shè)置得越多抽樣密度越高，結(jié)果的準確性就相對越好，但相應的耗時也會增加。SpecVAT 和MDCG-CTI 相比，前者的耗時較多，且當數(shù)據(jù)量越大時越明顯，這是因為該算法要計算特征向量（時間復雜度為數(shù)據(jù)量的三次方），且有可視化操作步驟（需要從不同特征向量個數(shù)的SpecVAT 相異度圖中用ADNC 算法自動確定簇數(shù)）的關(guān)系。因此，綜合準確性和運行耗時來看，MDCG-CTI 算法是具有明顯優(yōu)勢的，其適用于增量數(shù)據(jù)序列的特點不僅帶來了耗時相對較少的優(yōu)點，而且還可以分析全體數(shù)據(jù)（并非抽樣分析）以提高聚類趨勢判斷的準確性。

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

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

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

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

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

表2 UCI數(shù)據(jù)集上不同算法的平均可聚類比率分布和運行耗時比較（算法各運行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é)語

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

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