反向近鄰構(gòu)造連通圖的聚類算法

龍建武，王 強

重慶理工大學(xué) 計算機科學(xué)與工程學(xué)院，重慶 400054

聚類[1]，作為最常用的無監(jiān)督學(xué)習(xí)方法，在數(shù)據(jù)挖掘與機器學(xué)習(xí)領(lǐng)域具有廣泛的研究和應(yīng)用。聚類算法的目的是利用簇內(nèi)數(shù)據(jù)具有較高的相似度，簇間數(shù)據(jù)相似度較低的特性將數(shù)據(jù)集按照某種方式劃分成不同的類別[2]。隨著人工智能時代的發(fā)展，聚類的應(yīng)用場景越來越廣泛，包括數(shù)據(jù)挖掘[3]、人工智能[4]、文檔聚類[5]、模式識別[6]、社交網(wǎng)絡(luò)[7]和圖像分割[8]等領(lǐng)域。目前已經(jīng)提出了許多應(yīng)用廣泛的聚類算法，根據(jù)算法實現(xiàn)方式的不同可以分為：基于劃分的方法[9-11]、基于密度的方法[12-15]、基于分層的方法[16-17]、基于圖的方法[18-20]等。不同類型的算法各有其特點和應(yīng)用場景。

K-means 算法[9,21-22]是最典型的基于劃分的聚類算法，該算法在初始化聚類中心后，多次迭代將點劃分到對應(yīng)聚類中心所在的簇中。該算法思想簡單，但它無法擬合非凸數(shù)據(jù)以及對噪聲數(shù)據(jù)敏感。Kmeans算法屬于硬劃分算法，即對于數(shù)據(jù)集中的每個點，只能將其劃分到一個簇中。此外，還有一種軟劃分算法，如FCM（fuzzy C-means clustering algorithm）[23]，該算法認為數(shù)據(jù)集中的點相對于每個簇都有一個隸屬度，一個點屬于不同簇的隸屬度之和為1。FCM算法同樣具有劃分聚類算法的缺陷，即需要初始化聚類中心且無法擬合非凸數(shù)據(jù)集。

典型的基于密度的算法是DBSCAN（density based spatial clustering of applications with noise）算法[24]，它將數(shù)據(jù)定義為由稀疏區(qū)域分隔開的密集區(qū)域，通過設(shè)定兩個參數(shù)鄰域半徑Eps和密度閾值MinPts進行聚類。孫璐等人[25]提出融合網(wǎng)格劃分和DBSCAN的改進聚類算法，采用網(wǎng)格劃分技術(shù)劃分稀疏和密集區(qū)域，降低復(fù)雜度。Rodriguez等人[26]提出了DPC（clustering by fast search and find of density peaks）算法，通過構(gòu)造決策圖初始化局部密度最大值的點作為聚類中心，再將其他點分配到距離其最近且密度比其更大的聚類中心所在的類中，但該算法無法擬合非凸形狀的簇。劉娟等人[15]提出了采用反向最近鄰計算出的局部密度和密度自適應(yīng)距離構(gòu)建決策圖進行聚類的密度峰值聚類算法。

譜聚類算法[19-20]是基于圖的聚類算法。該算法利用圖論的基礎(chǔ)將數(shù)據(jù)聚類問題轉(zhuǎn)化為圖劃分問題，其往往具有較高的時間復(fù)雜度。Huang等人[27]提出一種可伸縮譜聚類（ultra-scalable spectral clustering，USPEC）算法，通過混合代表選擇策略和k近鄰快速逼近的方式構(gòu)造稀疏親和子矩陣，然后將稀疏子矩陣解釋成二部圖，對圖通過有效的分割進行聚類，但是其隨機選擇候選代表的方式使得算法穩(wěn)定性較差。Li等人[28]提出基于圖的CutPC（cut point clustering algorithm）算法，通過對去噪后的數(shù)據(jù)構(gòu)造自然鄰接圖進行聚類，但是該算法無法識別部分無噪數(shù)據(jù)。

針對上述聚類算法不能很好地擬合非凸數(shù)據(jù)集以及對噪聲敏感的缺陷，提出一種反向近鄰構(gòu)造連通圖的聚類算法。首先，考慮到噪點對聚類的影響，利用自然鄰居搜索達到穩(wěn)定狀態(tài)時的反向鄰居最大值設(shè)計一種密度公式計算點的密度，為有效去噪，利用密度均值和標(biāo)準(zhǔn)差函數(shù)設(shè)計一種動態(tài)的噪聲判別器，利用該判別器有效識別噪點，對數(shù)據(jù)進行去噪；其次，根據(jù)“距離越近的點具有越強的相關(guān)性”這一特點設(shè)計一種通過去噪后數(shù)據(jù)點的反向鄰居數(shù)作為限制條件構(gòu)造反向近鄰連通圖進行聚類的方法得到初步聚類結(jié)果，并根據(jù)給定的聚類數(shù)合并初始簇得到無噪數(shù)據(jù)的聚類結(jié)果；最后，對噪點劃分聚類得到最終的聚類結(jié)果。

1 自然鄰居

自然鄰居的概念首次由Zhu 等人[29-30]提出，其目的是為了解決數(shù)據(jù)點最近鄰范圍內(nèi)的參數(shù)選擇問題，其思想來源于現(xiàn)實社會中人類之間的友誼，自然社會中，一個人真正擁有多少朋友取決于有多少人把他當(dāng)作朋友。自然鄰居的搜索過程是通過不斷地擴大搜索范圍尋找數(shù)據(jù)點反向鄰居的過程?；谧匀秽従拥乃枷?，數(shù)據(jù)點越密集的地方擁有的反向鄰居越多，越稀疏的地方擁有的反向鄰居越少。

定義1（k近鄰）對于數(shù)據(jù)集D中的一點a，若點b是其第k個最近鄰居，則點a的k近鄰定義為：

其中，dist(a,b)表示數(shù)據(jù)點a和b之間的歐式距離。

定義2（反向鄰居）對于數(shù)據(jù)集D中的一個點a，其反向鄰居定義如下：

其中，d是D中的一個點，點a是點d的k近鄰，點a的反向鄰居為D中一組點d的集合。

定義3（自然特征值λ）自然鄰居搜索過程是被動查找所有數(shù)據(jù)點反向鄰居的過程。當(dāng)滿足以下兩個條件之一時，自然鄰居搜索達到穩(wěn)定狀態(tài)：（1）自然鄰居搜索范圍由k=1 到n逐漸擴大的過程中，若在連續(xù)兩次迭代過程中，擁有反向鄰居的數(shù)據(jù)點的個數(shù)保持不變；（2）數(shù)據(jù)集D中的任意一個點都擁有反向鄰居。若滿足上述兩個條件中的任意一個，則自然鄰居搜索停止，此時的狀態(tài)定義為自然鄰居穩(wěn)定狀態(tài)。自然鄰居搜索達到穩(wěn)定狀態(tài)時的k值定義為自然特征值λ，具體如下：

其中，k初始化為1，后續(xù)逐漸遞增，直至自然鄰居搜索達到穩(wěn)定狀態(tài)。nbk(xi)是數(shù)據(jù)集D中的點xi第k次迭代時的反向鄰居數(shù)量，函數(shù)f(x)用來統(tǒng)計D中擁有反向鄰居的點的個數(shù)，定義如下：

自然鄰居搜索過程的算法如算法1所示，自然鄰居搜索達到穩(wěn)定狀態(tài)時的自然特征值能夠克服傳統(tǒng)的KNN 算法k值選取不合理的情況，在數(shù)據(jù)挖掘和聚類分析領(lǐng)域具有良好的性能。

算法1自然鄰居搜索過程

2 提出的方法

由于目前的許多聚類方法在非凸數(shù)據(jù)集上的聚類效果較差，而現(xiàn)有的基于圖的方法如譜聚類算法常常具有較高的時間復(fù)雜度，因而限制了其在聚類分析領(lǐng)域的應(yīng)用。本文通過對自然鄰居思想的理解，發(fā)現(xiàn)自然鄰居搜索過程是不斷擴大搜索范圍尋找數(shù)據(jù)點反向鄰居的過程，考慮到核心區(qū)域的點擁有較多的反向鄰居，而邊緣區(qū)域的點擁有的反向鄰居較少或為0，提出一種反向近鄰構(gòu)造連通圖的聚類算法。通過對去噪后數(shù)據(jù)構(gòu)造反向近鄰連通圖來識別數(shù)據(jù)結(jié)構(gòu)特征，進行聚類。構(gòu)造反向近鄰連通圖進行聚類的方式只需考慮數(shù)據(jù)點與周圍一定范圍內(nèi)的其他點之間的聯(lián)系，具有較高的計算效率。

算法分為三部分：首先，利用自然鄰居搜索達到穩(wěn)定狀態(tài)時所有數(shù)據(jù)點的反向鄰居數(shù)最大值設(shè)計密度公式計算點的密度，并構(gòu)建一種動態(tài)的噪聲判別器利用給定的噪聲參數(shù)計算出合適的噪聲閾值進行去噪。然后，提出一種反向近鄰構(gòu)造連通圖進行聚類的方法，利用自然鄰居搜索達到穩(wěn)定狀態(tài)時數(shù)據(jù)點的反向鄰居數(shù)作為限制條件構(gòu)造反向近鄰連通圖，記錄構(gòu)圖完成時的極大連通子圖個數(shù)，得到初步聚類結(jié)果，并通過給定的聚類數(shù)對得到的初步聚類結(jié)果按照簇間距離從小到大合并聚類。最后，對噪點劃分聚類，得到最終的聚類結(jié)果。

2.1 反向密度去噪

聚類數(shù)據(jù)中，大部分數(shù)據(jù)集都包含噪點，這也導(dǎo)致很多對噪點比較敏感的聚類方法如K-means 算法的聚類效果較差。為解決這個問題，必須采用合適的方法識別噪聲數(shù)據(jù)。

傳統(tǒng)的聚類算法如DPC 算法[26]采用的是ε近鄰的方式來計算密度，通常有兩種計算方式：第一種采用的是計算截斷距離dc范圍內(nèi)數(shù)據(jù)點的個數(shù)作為點的密度，但這種計算方式得出的密度是離散值，通常無法取得較好的聚類效果，并且由于數(shù)據(jù)分布的多樣性，難以人為給出合理的截斷距離dc值。另一種方式采用高斯核函數(shù)計算密度，雖然能夠保證計算得到連續(xù)的密度值，但是這種密度計算方式仍然沒有解決截斷距離dc難以給定的缺陷。

由于稠密區(qū)域比稀疏區(qū)域點的密度更大，具有自適應(yīng)性特點的k近鄰方式相比難以確定合適取值的ε近鄰更具優(yōu)勢?；谏鲜鲇^點，使用數(shù)據(jù)點k近鄰方式相比ε近鄰計算密度的效果更好。傳統(tǒng)的k近鄰方式通常需要人為給定k值，而數(shù)據(jù)的復(fù)雜多樣性又導(dǎo)致往往難以給定合理的k取值，因此，使用一種能夠針對不同數(shù)據(jù)集自動確定k取值的方式計算密度就顯得尤為重要。

本文通過觀察，發(fā)現(xiàn)聚類數(shù)據(jù)具備以下特點：“位于稀疏區(qū)域的點具有較小的密度，位于稠密區(qū)域點的密度較大”。根據(jù)數(shù)據(jù)的這一特點利用自然鄰居搜索停止時的反向鄰居數(shù)設(shè)計密度公式計算點的密度信息，然后構(gòu)建一種動態(tài)的噪聲識別器利用噪聲參數(shù)計算合適的噪聲閾值對數(shù)據(jù)集進行去噪。

定義4（反向密度）對于D中的點a，其反向密度計算方式定義如下：

其中，μ為自然鄰居搜索達到穩(wěn)定狀態(tài)的反向鄰居數(shù)最大值，定義如下：

λ為該狀態(tài)下的自然特征值。nbλ(D)表示該狀態(tài)下所有點的反向鄰居數(shù)。

本文采取的密度計算方式，對自然鄰居搜索達到穩(wěn)定狀態(tài)時的反向鄰居數(shù)最大值μ以及μ近鄰的歐式距離之和的比值取對數(shù)來計算數(shù)據(jù)的密度。由于不同數(shù)據(jù)集自然鄰居搜索達到穩(wěn)定狀態(tài)時的反向鄰居數(shù)最大值并不相同，因此本文的密度計算方式能夠針對不同數(shù)據(jù)集得到不同的反向鄰居數(shù)最大值，從而避免人工選擇k值不合理的缺陷。

通過式（5）計算出數(shù)據(jù)的密度后，觀察噪點數(shù)據(jù)與非噪點數(shù)據(jù)之間的密度差異，利用密度均值和標(biāo)準(zhǔn)差構(gòu)造一種動態(tài)的噪聲判別器，根據(jù)提供的噪聲參數(shù)計算出噪聲密度閾值，識別噪點，對數(shù)據(jù)集進行去噪。

定義5（噪聲判別器）對于D中的點a，若點a屬于噪點，則點a需要滿足的條件定義為：

其中，τ(β)是噪聲密度閾值，定義如下：

利用式（8），將數(shù)據(jù)集中所有密度小于τ(β)的點均識別為噪點。mean(ρ(D))表示數(shù)據(jù)集D的密度均值，Φ-1(?)表示標(biāo)準(zhǔn)正態(tài)分布的分位數(shù)函數(shù)，β表示噪聲參數(shù)，由人工根據(jù)數(shù)據(jù)集的含噪情況給定，β∈[0,1)，σ(?)表示標(biāo)準(zhǔn)差函數(shù)。數(shù)據(jù)集的噪點越多，識別噪點的噪聲閾值τ(β)就越大，因而需要給定較大的噪聲參數(shù)β。

由于不同數(shù)據(jù)集的噪點含量并不相同，有些數(shù)據(jù)集含噪較多，也有些數(shù)據(jù)集含噪點較少或者不包含噪點。基于這種情況，設(shè)計一種能夠根據(jù)數(shù)據(jù)集含噪程度調(diào)節(jié)噪聲參數(shù)控制去噪比例的噪聲識別器就顯得尤為重要。本文式（8）中的噪聲判別器，通過密度均值獲得數(shù)據(jù)點密度的總體分布，然后利用噪聲參數(shù)β來調(diào)節(jié)判別器識別出的噪點數(shù)量。上述條件使得噪聲判別器針對不同噪點含量的數(shù)據(jù)集都能達到較好的去噪效果，因此能夠適應(yīng)于各種類型的含噪數(shù)據(jù)集，解決噪點對聚類過程的影響。

通過上述的噪聲判別器設(shè)置合適的噪聲參數(shù)對數(shù)據(jù)集進行去噪，去噪過程如算法2 所示，去噪后的數(shù)據(jù)集能很好地保留點之間的結(jié)構(gòu)信息，便于后續(xù)進行聚類。例如對于圖1中的數(shù)據(jù)集，該數(shù)據(jù)集共有1 532 個樣本，利用式（8）設(shè)置噪聲參數(shù)為0.12，識別噪點，對數(shù)據(jù)集進行去噪。該圖中紅色點表示去噪后保留的數(shù)據(jù)，灰色點表示噪點，經(jīng)過去噪后的數(shù)據(jù)集簇內(nèi)與簇間的結(jié)構(gòu)信息明顯地體現(xiàn)出來。接下來，將去噪后的數(shù)據(jù)利用2.2節(jié)中提出的方法進行聚類。

圖1 去噪后的數(shù)據(jù)可視化效果圖Fig.1 Data visualization after denoising

算法2反向密度去噪算法

2.2 反向鄰居構(gòu)圖劃分聚類

對數(shù)據(jù)集去噪后，能夠得到比較干凈的數(shù)據(jù)。接下來，對得到的數(shù)據(jù)利用自然鄰居搜索過程尋找每個點的反向鄰居。由于點的密度各不相同，位于核心區(qū)域的點擁有較多的反向鄰居，位于邊緣的點擁有的反向鄰居數(shù)目較少，甚至沒有反向鄰居。例如對于圖2中的數(shù)據(jù)集，將自然鄰居搜索過程應(yīng)用在該數(shù)據(jù)集上，得到每個點的反向鄰居。該數(shù)據(jù)集在自然鄰居搜索達到穩(wěn)定狀態(tài)時的自然特征值λ=8，其中點p位于數(shù)據(jù)集的核心區(qū)域，自然鄰居搜索停止時該點擁有的反向鄰居數(shù)為13，而對于點q，由于其位于邊緣區(qū)域，自然鄰居搜索停止時該點僅擁有1個反向鄰居。接下來，利用點的反向鄰居數(shù)作為限制條件構(gòu)造反向近鄰連通圖劃分聚類。

圖2 點p 和q 的反向鄰居（點p 和q 的反向鄰居數(shù)分別為13和1）Fig.2 Reverse neighbors of point p and q(The number of reverse neighbors of points p and q are 13 and 1,respectively)

定義6（反向近鄰連通圖）對于D*中的一個點d，通過自然鄰居搜索得到d的反向鄰居數(shù)目為nb[d]，將點d與其周圍nb[d]個近鄰的數(shù)據(jù)點進行連接構(gòu)造的連通圖。

由于不同數(shù)據(jù)點的反向鄰居數(shù)各不相同，核心位置的點具有更多的反向鄰居，它與周圍點之間的聯(lián)系更密切，而邊緣位置的點具有的反向鄰居數(shù)較少，這也使得它只與自身周圍少部分點之間存在聯(lián)系?；谶@種結(jié)論，設(shè)計一種反向近鄰構(gòu)造連通圖的聚類算法，利用點的反向鄰居數(shù)作為限制條件構(gòu)造連通圖。反向近鄰構(gòu)圖與傳統(tǒng)的k近鄰構(gòu)圖有著明顯的區(qū)別，傳統(tǒng)的k近鄰方式進行構(gòu)圖，數(shù)據(jù)集中的每個點均需要與其最近的k個鄰居相連，而反向近鄰連通圖是對傳統(tǒng)k近鄰方式構(gòu)圖的一種改進，它利用數(shù)據(jù)點的反向鄰居數(shù)作為構(gòu)造k近鄰圖k取值的限制條件，也就是說，對于不同的點，在構(gòu)造反向近鄰連通圖時所選擇的近鄰個數(shù)是不相同的。位于核心區(qū)域的數(shù)據(jù)點構(gòu)造反向近鄰連通圖時選擇的近鄰個數(shù)較多，位于邊緣區(qū)域的數(shù)據(jù)點構(gòu)造反向近鄰連通圖時選擇的近鄰個數(shù)較少甚至為0。傳統(tǒng)k近鄰方式構(gòu)圖時對所有點取相同的k值容易導(dǎo)致將本不屬于同一個聚類的邊緣點進行連接，影響聚類效果，而利用反向鄰居數(shù)作為限制條件構(gòu)造連通圖能夠有效避免k近鄰方式構(gòu)圖的缺陷，聚類效果更好。對于去噪后數(shù)據(jù)集利用反向近鄰構(gòu)圖劃分聚類的具體算法流程可描述如下：

（1）利用自然鄰居搜索的方式尋找去噪后數(shù)據(jù)集D*的反向鄰居數(shù)，記錄為nb[D*]。

（2）對D*中的每個數(shù)據(jù)點構(gòu)造反向近鄰連通圖，具體方式為：對于D*中的一點d，利用KNN算法對k取值從1 開始，若點d的反向鄰居數(shù)目nb[d]大于等于k，就將點d與其周圍的k近鄰范圍內(nèi)的點連接起來，若nb[d]小于k，則不進行連接，隨后對k進行加1操作。不斷重復(fù)該過程，直到k達到所有數(shù)據(jù)點反向鄰居數(shù)最大值max(nb[D*])時停止。

（3）統(tǒng)計（2）所得結(jié)果中的極大連通子圖的個數(shù)（number of maximal connected subgraphs，NMCS）得到初步的聚類結(jié)果。

（4）利用給定的聚類數(shù)將上述得到的簇合并成對應(yīng)聚類數(shù)的聚類結(jié)果。

在構(gòu)造反向近鄰連通圖時，針對不同數(shù)據(jù)點構(gòu)圖時選取的近鄰個數(shù)不同。對于數(shù)據(jù)集D*中的一個點d，取其nb[d]個近鄰的數(shù)據(jù)點構(gòu)造反向近鄰連通圖，其中nb[d]表示自然鄰居搜索達到穩(wěn)定狀態(tài)時點d的反向鄰居個數(shù)。當(dāng)所有數(shù)據(jù)點構(gòu)造反向近鄰連通圖完成時算法停止，統(tǒng)計此時的極大連通子圖的個數(shù)，得到初步的聚類結(jié)果。例如對于圖2中的數(shù)據(jù)集，自然鄰居搜索達到穩(wěn)定狀態(tài)時該數(shù)據(jù)集中所有數(shù)據(jù)點的反向鄰居數(shù)最大值為15，將每個數(shù)據(jù)點的反向鄰居數(shù)作為構(gòu)造k近鄰連通圖對應(yīng)該點k取值的限制條件，利用KNN算法對于k取[1,15]之間的所有整數(shù)時，不同k值得到的極大連通子圖的數(shù)量（NMCS）變化情況如圖3（a）～（g）所示。根據(jù)圖3（g）中的結(jié)果，得到反向近鄰構(gòu)圖完成時的極大連通子圖數(shù)量為3，因此利用反向近鄰構(gòu)圖劃分聚類得到初始聚類數(shù)為3。根據(jù)初步的聚類結(jié)果發(fā)現(xiàn)，利用反向近鄰連通圖進行聚類的過程已經(jīng)識別出該無噪數(shù)據(jù)集的基本結(jié)構(gòu)。

圖3 不同k 值的NMCS變化情況Fig.3 Change of NMCS for different values of k

利用反向近鄰構(gòu)圖劃分聚類的過程中可能會產(chǎn)生部分小簇或者孤立點，針對這種情況，根據(jù)設(shè)定好的聚類數(shù)對初始聚類結(jié)果進行合并，依次選擇簇間距離最近的兩個簇合并，直到達到設(shè)定的聚類數(shù)為止。對于圖2中的數(shù)據(jù)集，其真實聚類數(shù)為2，通過構(gòu)造反向近鄰連通圖得到的初始聚類結(jié)果包含3個簇，利用給定的聚類數(shù)依次合并簇間距離最近的簇后得到的聚類結(jié)果如圖3（h）所示。利用反向近鄰構(gòu)造連通圖劃分聚類的具體算法如算法3所示。

算法3反向近鄰構(gòu)造連通圖劃分聚類

2.3 噪點劃分聚類

通過構(gòu)造反向近鄰連通圖劃分聚類得到去噪后數(shù)據(jù)的聚類結(jié)果后，將去掉的噪點劃分到對應(yīng)的聚類中，在劃分噪點時，考慮到噪點分布在簇間的范圍比較廣，單純將其分配到距離最近的簇所在的類別中可能導(dǎo)致劃分不準(zhǔn)確，影響聚類結(jié)果。因此，考慮數(shù)據(jù)的密度信息，將噪點分配規(guī)則定義如下：

噪點劃分規(guī)則（noise division rules，NDR）：針對噪點數(shù)據(jù)，將其劃分到距離其最近的非噪點所在的類別中，同時要求該非噪點的密度大于當(dāng)前待分配的噪點。

通過將密度信息考慮到噪點劃分中，可使得噪點劃分的結(jié)果更準(zhǔn)確，最終的聚類效果更好，噪點劃分聚類的原理如算法4所示。

算法4噪點劃分聚類

2.4 時間復(fù)雜度

對于提出算法，假設(shè)數(shù)據(jù)集有n個對象，經(jīng)過構(gòu)建KD 樹后自然鄰居搜索過程時間復(fù)雜度為O(nlgn)，去噪過程需要判斷每個點是否為噪點，時間復(fù)雜度為O(n)，構(gòu)造反向近鄰連通圖時對每個點與其最近的nb[d]點進行連接，時間復(fù)雜度為O(nlgn)，噪點劃分聚類時需要尋找每個點周圍距離最近的高密度點，時間復(fù)雜度為O(nlgn)。因此，本文算法的時間復(fù)雜度為O(nlgn)。

3 實驗

為驗證提出方法的有效性，在9個合成數(shù)據(jù)集和5個真實數(shù)據(jù)集上進行實驗，并將本文方法與其他聚類算法在上述數(shù)據(jù)集上的聚類結(jié)果進行對比。合成數(shù)據(jù)集來自文獻[28]（https://github.com/lintao6/CutPC/tree/master/datasets），真實數(shù)據(jù)集來自UCI官網(wǎng)（https://archive.ics.uci.edu/ml/index.php）。實驗中將所有的數(shù)據(jù)集進行標(biāo)準(zhǔn)化處理，對比算法包括K-means算法[9]、DBSCAN 算 法[24]、DPC 算 法[26]、USPEC 算 法[27]以 及CutPC算法[28]。

聚類評價指標(biāo)通常被用來衡量聚類結(jié)果的質(zhì)量，一般來說，聚類評價指標(biāo)分為兩種：內(nèi)部評價指標(biāo)和外部評價指標(biāo)。內(nèi)部評價指標(biāo)利用簇的內(nèi)部結(jié)構(gòu)信息設(shè)計不同的內(nèi)部評價標(biāo)準(zhǔn)對聚類結(jié)果的優(yōu)劣進行評判，而外部評價指標(biāo)通常需引入外部信息來評價聚類效果，如聚類的真實標(biāo)簽。常用的外部評價指標(biāo)有聚類精度（cluster accuracy，Acc）、標(biāo)準(zhǔn)化互信息（normalized mutual information，NMI）等，實驗中采用上述兩種外部評價指標(biāo)對聚類結(jié)果進行評價，以評估提出方法的有效性。

3.1 外部評價指標(biāo)

聚類精度（Acc）是最常用的聚類外部評價指標(biāo)之一，它是利用映射后的預(yù)測標(biāo)簽與真實聚類標(biāo)簽的差異性對聚類效果進行評估。聚類精度能夠直觀地評價聚類結(jié)果的準(zhǔn)確率，得到聚類結(jié)果正確數(shù)據(jù)的比例。具體計算方式定義如下：

其中，n為數(shù)據(jù)樣本個數(shù)，ti和pi分別代表真實的聚類標(biāo)簽和預(yù)測的聚類標(biāo)簽，map(?)是一個映射函數(shù)，作為預(yù)測標(biāo)簽和真實標(biāo)簽的映射，用來解決聚類過程中預(yù)測標(biāo)簽和真實標(biāo)簽不匹配的問題，采用匈牙利算法實現(xiàn)。δ(a,b)定義為：

Acc∈[0,1]，Acc的值越大，聚類效果越好。

另一個評價聚類效果的外部指標(biāo)是標(biāo)準(zhǔn)化互信息（NMI），該指標(biāo)是評估聚類算法優(yōu)劣的一個常用的指標(biāo)，計算方式定義為：

其中，X和Y分別代表真實聚類標(biāo)簽和預(yù)測標(biāo)簽的集合，I(X,Y)表示兩個隨機變量X和Y之間的互信息，H(?)表示隨機變量的熵，NMI 指標(biāo)的取值范圍為[0,1]。NMI 指標(biāo)利用信息論來量化聚類分區(qū)的差異，NMI的值越大，聚類的效果越好。

3.2 合成數(shù)據(jù)集實驗

實驗中選擇9 個合成數(shù)據(jù)集來驗證提出方法的有效性，9 個合成數(shù)據(jù)集均包含部分噪點。將5 種對比算法和本文方法應(yīng)用在合成數(shù)據(jù)集上進行聚類，對比聚類結(jié)果。9個合成數(shù)據(jù)集的基本信息如表1所示。

表1 9個合成數(shù)據(jù)集的基本信息Table 1 Basic information of 9 synthetic datasets

由于9個合成數(shù)據(jù)集均包含部分噪點，需利用提出的去噪方式對數(shù)據(jù)集進行去噪，去噪后的數(shù)據(jù)能夠體現(xiàn)出簇的結(jié)構(gòu)信息。對9 個合成數(shù)據(jù)集設(shè)置的噪聲參數(shù)如表2 所示。對于數(shù)據(jù)集D7，其包含噪點較多，故設(shè)置噪聲參數(shù)為0.18，其他8 個合成數(shù)據(jù)集設(shè)置噪聲參數(shù)為0.12。去噪前后的數(shù)據(jù)集可視化效果圖如圖4所示。觀察發(fā)現(xiàn)，去噪后的數(shù)據(jù)集接近理想數(shù)據(jù)集。為展示提出算法的有效性，實驗中與其他5 個算法的聚類效果進行對比，5 種對比算法在9個合成數(shù)據(jù)集上的參數(shù)如表2 所示。其中DBSCAN算法對參數(shù)非常敏感，調(diào)參過程比較復(fù)雜，為得到較好的聚類結(jié)果需要對參數(shù)精心選取。

表2 不同聚類算法在9個合成數(shù)據(jù)集上的參數(shù)Table 2 Parameters of different clustering algorithms on 9 synthetic datasets

圖4 9個合成數(shù)據(jù)集去噪后的數(shù)據(jù)可視化效果Fig.4 Data visualization after denoising of 9 synthetic datasets

對9個合成數(shù)據(jù)集去噪后，利用去噪后的數(shù)據(jù)構(gòu)造反向近鄰連通圖進行聚類，通過反向近鄰連通圖得到初步聚類結(jié)果后，再根據(jù)輸入的聚類數(shù)將部分較小簇或者孤立點合并，得到去噪后數(shù)據(jù)對應(yīng)于給定聚類數(shù)的聚類結(jié)果，最后對噪點數(shù)據(jù)劃分聚類，得到最終的聚類結(jié)果。本文方法在9 個合成數(shù)據(jù)集上應(yīng)用后得到的聚類結(jié)果可視化效果圖如圖5 所示。通過觀察發(fā)現(xiàn)，本文方法在9個合成數(shù)據(jù)集上均能夠準(zhǔn)確地區(qū)分出不同的簇，聚類效果較好。

圖5 數(shù)據(jù)集D1～D9的最終聚類結(jié)果Fig.5 Final clustering results of datasets D1 to D9

此外，將本文方法應(yīng)用在上述9個合成數(shù)據(jù)集上的聚類效果和其他5種聚類方法進行對比，并采用Kmeans、DBSCAN、DPC、USPEC、CutPC 共5 種聚類算法作為對比方法進行實驗。其中K-means 算法是基于分區(qū)的聚類算法，該算法通常無法較好地劃分非凸數(shù)據(jù)集，并且對噪聲數(shù)據(jù)比較敏感。DBSCAN 算法是基于密度的算法，通過對鄰域半徑Eps和密度閾值MinPts的多次調(diào)參進行聚類，但是其往往會因為數(shù)據(jù)密度不均勻?qū)е戮垲愋Ч^差。DPC算法通過計算數(shù)據(jù)點的密度以及到高密度點的最小距離構(gòu)造決策圖尋找聚類中心進行聚類，但是其同K-means算法一樣對非凸數(shù)據(jù)集擬合較差。USPEC算法在選擇候選代表時使用了隨機選擇策略，因此會導(dǎo)致聚類效果具有隨機性，算法穩(wěn)定性較差。CutPC算法是基于圖的方法，但是其只對于特定噪聲范圍內(nèi)的數(shù)據(jù)集有效，無法識別部分無噪數(shù)據(jù)集。相比而言，本文方法能夠避免上述五種對比方法的缺陷，對9個合成數(shù)據(jù)集的聚類效果較好。

為了更直觀地描述本文方法相對其他幾種對比算法的優(yōu)勢，實驗中采用了外部評價指標(biāo)聚類精度（Acc）和標(biāo)準(zhǔn)化互信息（NMI）進行聚類效果的評判，6種算法應(yīng)用在9個合成數(shù)據(jù)集上的Acc和NMI指標(biāo)如表3所示。

表3 6種方法應(yīng)用在9個合成數(shù)據(jù)集上的Acc和NMITable 3 Acc and NMI of 6 methods applied on 9 synthetic datasets

通過6 種聚類方法在合成數(shù)據(jù)集上的聚類效果對比，采用聚類精度（Acc）和標(biāo)準(zhǔn)化互信息（NMI）作為驗證指標(biāo)進行聚類效果的驗證后發(fā)現(xiàn)，其他五種聚類算法由于各自存在的缺陷，無法達到較優(yōu)的結(jié)果，而本文方法先對數(shù)據(jù)集去噪后，對不包含噪點的數(shù)據(jù)集進行聚類能夠準(zhǔn)確識別非凸形狀數(shù)據(jù)集的內(nèi)部結(jié)構(gòu)信息，在9 個合成數(shù)據(jù)集上均具有較好的聚類效果。

表4展示了6種聚類算法在9個合成數(shù)據(jù)集上的運行時間。通過對比發(fā)現(xiàn)，本文算法在9個合成數(shù)據(jù)集上的運行時間相比K-means 算法以及DBSCAN 算法的運行時間稍長，在數(shù)據(jù)量較小的時候，本文算法的運行時間相比DPC 算法和USPEC 算法具有明顯的優(yōu)勢，而在數(shù)據(jù)量較大的時候，例如對于數(shù)據(jù)集D9，本文算法的運行時間高于USPEC 算法，但依舊低于DPC算法。此外，不論數(shù)據(jù)量的大小，本文算法都遠低于CutPC算法的運行時間。綜上得出，本文方法不僅能在9 個合成數(shù)據(jù)集上具有比較好的聚類效果，同時還能擁有較快的計算速度。

表4 6種方法應(yīng)用在9個合成數(shù)據(jù)集上的運行時間Table 4 Runtime of 6 methods applied on 9 synthetic datasets 單位：s

3.3 真實數(shù)據(jù)集實驗

另外，實驗中還將本文方法應(yīng)用在真實數(shù)據(jù)上，利用UCI 提供的真實數(shù)據(jù)集進行本文方法的實驗。實驗過程中將6 種聚類算法應(yīng)用在5 個真實數(shù)據(jù)集上的聚類效果進行對比，5個真實數(shù)據(jù)集分別為iris、cancer、seeds、banknote 和heart，5 個真實數(shù)據(jù)集的基本信息如表5所示。

表5 5個真實數(shù)據(jù)集的基本信息Table 5 Basic information of 5 real datasets

實驗中將本文方法和5 個對比算法應(yīng)用在5 個真實數(shù)據(jù)集上，不同方法對應(yīng)5種真實數(shù)據(jù)集的參數(shù)設(shè)置如表6所示。和合成數(shù)據(jù)集一樣，仍然采用聚類精度（Acc）和標(biāo)準(zhǔn)化互信息（NMI）兩種聚類評價指標(biāo)進行聚類效果的評估。6 種算法應(yīng)用在真實數(shù)據(jù)集上的Acc和NMI指標(biāo)如表7所示。

表6 6種方法應(yīng)用在5個真實數(shù)據(jù)集上的參數(shù)Table 6 Parameters of 6 methods applied on 5 real datasets

表7 6種方法應(yīng)用在5個真實數(shù)據(jù)集上的Acc和NMITable 7 Acc and NMI of 6 methods applied on 5 real datasets

通過將本文方法與其他5 種對比算法在5 個真實數(shù)據(jù)集上進行實驗得到的聚類精度（Acc）和標(biāo)準(zhǔn)化互信息（NMI）指標(biāo)結(jié)果表明，對于iris 數(shù)據(jù)集，USPEC算法在兩種聚類指標(biāo)上優(yōu)于其他5種方法，而對于cancer、seeds、banknote和heart數(shù)據(jù)集，本文方法的聚類精度（Acc）和標(biāo)準(zhǔn)化互信息（NMI）指標(biāo)均優(yōu)于其他5 種對比方法。另外對于iris 數(shù)據(jù)集，本文方法的聚類結(jié)果也接近于最優(yōu)方法所得結(jié)果。綜上所述，本文方法在5個真實數(shù)據(jù)集上的聚類效果優(yōu)于其他5種對比算法。

表8展示了6種算法在5個真實數(shù)據(jù)集上進行聚類消耗的時間。通過對比發(fā)現(xiàn)：當(dāng)數(shù)據(jù)量較小時，本文算法進行聚類時所消耗的時間非常少，例如在對iris、seeds 和heart 數(shù)據(jù)集聚類時，消耗的時間是6 種聚類方法中最少的；當(dāng)數(shù)據(jù)集較大時，比如在對banknote 數(shù)據(jù)集進行聚類時，所消耗的時間明顯增長，接近于DPC和USPEC算法，但仍然遠小于CutPC算法消耗的時間，這是由于數(shù)據(jù)量較大時，在尋找反向鄰居的過程、去噪的過程以及合并聚類時需要進行一系列的計算，因而會增加時間的消耗。總的來說，本文方法能夠在達到較好聚類效果的同時還能夠?qū)崿F(xiàn)較少的計算時間。

表8 6種方法應(yīng)用在5個真實數(shù)據(jù)集上的運行時間Table 8 Runtime of 6 methods applied on 5 real datasets 單位：s

3.4 參數(shù)魯棒性實驗

為驗證噪聲參數(shù)β的魯棒性，實驗中對9個合成數(shù)據(jù)集采用提出的方法在β從0.08～0.20范圍內(nèi)每間隔0.02的取值做一次實驗，計算β每次變化時9個合成數(shù)據(jù)集的Acc和NMI指標(biāo)的平均值來評價提出算法的參數(shù)魯棒性，噪聲參數(shù)β在上述范圍內(nèi)改變時的Acc 和NMI 指標(biāo)均值變化情況如圖6 所示。紅色折線代表9個合成數(shù)據(jù)集Acc指標(biāo)均值的變化情況，藍色折線代表9 個合成數(shù)據(jù)集NMI 指標(biāo)均值的變化情況。

圖6 合成數(shù)據(jù)集的Acc和NMI均值隨著β 的變化Fig.6 Changes of Acc and NMI mean values of synthetic datasets with β

觀察發(fā)現(xiàn)，當(dāng)噪聲參數(shù)β在0.08～0.20 范圍內(nèi)變化時，本文方法應(yīng)用在9個合成數(shù)據(jù)集上進行聚類的Acc和NMI指標(biāo)的均值僅在β較大時出現(xiàn)較小的變化。而β較大時聚類指標(biāo)均值下降的主要原因在于數(shù)據(jù)集D4的外圍環(huán)狀簇的數(shù)據(jù)點個數(shù)相對于中間3個球形簇較少，噪聲參數(shù)較大時會去除環(huán)狀簇內(nèi)部密度較小點，使得環(huán)狀簇斷開，從而影響聚類效果?？偟膩碚f，噪聲參數(shù)β在一定范圍內(nèi)變化時本文算法依然具有較好的聚類效果。因此，本文方法在參數(shù)選擇上具有較強的魯棒性。

4 結(jié)束語

本文提出一種反向近鄰構(gòu)造連通圖的聚類算法。該算法對去噪后的數(shù)據(jù)采用反向鄰居數(shù)作為限制條件構(gòu)造反向近鄰連通圖進行初步聚類，然后利用給定的聚類數(shù)將初步聚類結(jié)果按照簇間距離從小到大合并成對應(yīng)聚類數(shù)的結(jié)果，最后劃分噪點得到最終的聚類結(jié)果。通過構(gòu)造反向近鄰連通圖能夠避免傳統(tǒng)k近鄰圖由于對每個點取相同的k值導(dǎo)致聚類劃分不準(zhǔn)確的問題，能夠擬合非凸形狀等復(fù)雜結(jié)構(gòu)的數(shù)據(jù)集。另外，實驗中將本文方法應(yīng)用在9個合成數(shù)據(jù)集和5個真實數(shù)據(jù)集上，并利用兩種聚類外部指標(biāo)進行評價，結(jié)果表明，本文方法在合成數(shù)據(jù)集和真實數(shù)據(jù)集上均能夠取得較好的聚類效果。

然而，當(dāng)噪聲參數(shù)設(shè)置過小導(dǎo)致去噪不完全時，可能會導(dǎo)致本文方法無法得到較好的聚類結(jié)果。這是因為若噪聲參數(shù)設(shè)置過小則會導(dǎo)致構(gòu)造反向近鄰連通圖時將不同簇的數(shù)據(jù)連接，導(dǎo)致簇劃分錯誤，影響最終的聚類結(jié)果。另外，需要人工給定聚類數(shù)也是本文方法的不足之處，這也是現(xiàn)有的大多數(shù)聚類方法存在的共性問題，后續(xù)將針對以上問題做進一步的研究。