龍建武，王 強(qiáng)

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

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

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

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

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

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

1 自然鄰居

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

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

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

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

其中，d是D中的一個(gè)點(diǎn)，點(diǎn)a是點(diǎn)d的k近鄰，點(diǎn)a的反向鄰居為D中一組點(diǎn)d的集合。

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

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

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

算法1自然鄰居搜索過程

2 提出的方法

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

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

2.1 反向密度去噪

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

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

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

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

定義4（反向密度）對于D中的點(diǎn)a，其反向密度計(jì)算方式定義如下：

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

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

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

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

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

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

利用式（8），將數(shù)據(jù)集中所有密度小于τ(β)的點(diǎn)均識(shí)別為噪點(diǎn)。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ù)集的噪點(diǎn)越多，識(shí)別噪點(diǎn)的噪聲閾值τ(β)就越大，因而需要給定較大的噪聲參數(shù)β。

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

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

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

算法2反向密度去噪算法

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

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

圖2 點(diǎn)p 和q 的反向鄰居（點(diǎn)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*中的一個(gè)點(diǎn)d，通過自然鄰居搜索得到d的反向鄰居數(shù)目為nb[d]，將點(diǎn)d與其周圍nb[d]個(gè)近鄰的數(shù)據(jù)點(diǎn)進(jìn)行連接構(gòu)造的連通圖。

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

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

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

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

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

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

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

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

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

2.3 噪點(diǎn)劃分聚類

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

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

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

算法4噪點(diǎn)劃分聚類

2.4 時(shí)間復(fù)雜度

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

3 實(shí)驗(yàn)

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

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

3.1 外部評(píng)價(jià)指標(biāo)

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

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

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

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

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

3.2 合成數(shù)據(jù)集實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

表3 6種方法應(yīng)用在9個(gè)合成數(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）作為驗(yàn)證指標(biāo)進(jìn)行聚類效果的驗(yàn)證后發(fā)現(xiàn)，其他五種聚類算法由于各自存在的缺陷，無法達(dá)到較優(yōu)的結(jié)果，而本文方法先對數(shù)據(jù)集去噪后，對不包含噪點(diǎn)的數(shù)據(jù)集進(jìn)行聚類能夠準(zhǔn)確識(shí)別非凸形狀數(shù)據(jù)集的內(nèi)部結(jié)構(gòu)信息，在9 個(gè)合成數(shù)據(jù)集上均具有較好的聚類效果。

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

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

3.3 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

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

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

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

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

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

通過將本文方法與其他5 種對比算法在5 個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)得到的聚類精度（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個(gè)真實(shí)數(shù)據(jù)集上的聚類效果優(yōu)于其他5種對比算法。

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

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

3.4 參數(shù)魯棒性實(shí)驗(yàn)

為驗(yàn)證噪聲參數(shù)β的魯棒性，實(shí)驗(yàn)中對9個(gè)合成數(shù)據(jù)集采用提出的方法在β從0.08～0.20范圍內(nèi)每間隔0.02的取值做一次實(shí)驗(yàn)，計(jì)算β每次變化時(shí)9個(gè)合成數(shù)據(jù)集的Acc和NMI指標(biāo)的平均值來評(píng)價(jià)提出算法的參數(shù)魯棒性，噪聲參數(shù)β在上述范圍內(nèi)改變時(shí)的Acc 和NMI 指標(biāo)均值變化情況如圖6 所示。紅色折線代表9個(gè)合成數(shù)據(jù)集Acc指標(biāo)均值的變化情況，藍(lán)色折線代表9 個(gè)合成數(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)變化時(shí)，本文方法應(yīng)用在9個(gè)合成數(shù)據(jù)集上進(jìn)行聚類的Acc和NMI指標(biāo)的均值僅在β較大時(shí)出現(xiàn)較小的變化。而β較大時(shí)聚類指標(biāo)均值下降的主要原因在于數(shù)據(jù)集D4的外圍環(huán)狀簇的數(shù)據(jù)點(diǎn)個(gè)數(shù)相對于中間3個(gè)球形簇較少，噪聲參數(shù)較大時(shí)會(huì)去除環(huán)狀簇內(nèi)部密度較小點(diǎn)，使得環(huán)狀簇?cái)嚅_，從而影響聚類效果?？偟膩碚f，噪聲參數(shù)β在一定范圍內(nèi)變化時(shí)本文算法依然具有較好的聚類效果。因此，本文方法在參數(shù)選擇上具有較強(qiáng)的魯棒性。

4 結(jié)束語

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

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