張柏愷,楊德剛,2,馮 驥,2

(1.重慶師范大學(xué)計(jì)算機(jī)與信息科學(xué)學(xué)院，重慶 401331； 2.教育大數(shù)據(jù)智能感知與應(yīng)用重慶市工程研究中心，重慶 401331)

1 引言

隨著大數(shù)據(jù)與智能化的發(fā)展，人工智能領(lǐng)域的聚類技術(shù)也被賦予了更為重要的現(xiàn)實(shí)意義，在商業(yè)選址、金融產(chǎn)品推薦、異常檢測等方面也有廣泛應(yīng)用。聚類算法的目標(biāo)在于無監(jiān)督地將數(shù)據(jù)集分割成不同的類或簇，使得同一簇內(nèi)數(shù)據(jù)的相似性盡可能大，同時(shí)保證簇間數(shù)據(jù)的差異性也盡可能大。在眾多聚類算法中，基于最近鄰居的聚類算法在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、圖像處理和模式識別等多個(gè)領(lǐng)域有著十分廣泛的應(yīng)用，并且取得了很多不錯(cuò)的成果。

在基于最近鄰居的聚類算法中，如何自動(dòng)推斷聚類個(gè)數(shù)與鄰域參數(shù)，降低對先驗(yàn)知識的依賴是聚類算法面臨的一個(gè)挑戰(zhàn)。為了獲取更為準(zhǔn)確的聚類結(jié)果，現(xiàn)有聚類算法一般需要預(yù)先指定聚類個(gè)數(shù)。而在針對聚類方法的現(xiàn)實(shí)應(yīng)用中，很難在聚類算法運(yùn)行之前對聚類個(gè)數(shù)進(jìn)行準(zhǔn)確的預(yù)估。在另一方面，無論是基于k-最近鄰居KNN(K-Nearest Neighbor) 原則還是ε-最近鄰居ε-NN(ε-Nearest Neighbor)原則，其各自對應(yīng)的鄰域參數(shù)k或ε的選取與數(shù)據(jù)集的分布特點(diǎn)密切相關(guān)，算法的性能也會(huì)因?yàn)閰?shù)的不同取值而產(chǎn)生急劇變化。

針對上述參數(shù)選擇問題，本文提出了基于自然鄰居NaN(Nature Neighbor)[2,3]的邊界剝離聚類算法NaN-BP(Natural Neighbor based Border Peeling clustering algorithm)。NaN-BP算法結(jié)合自然鄰居的思想，擺脫了鄰域參數(shù)的選擇問題。通過自然鄰居的思想，鄰域參數(shù)的選擇可以不需要大量先驗(yàn)知識的積累。NaN-BP算法通過對數(shù)自然穩(wěn)定狀態(tài)和對數(shù)自然鄰居特征值建立具有魯棒性的自然鄰居關(guān)系，并在其基礎(chǔ)之上以自適應(yīng)的邊界剝離方法完成數(shù)據(jù)集的聚類分析。因此，NaN-BP算法的整個(gè)聚類過程不僅無需人為設(shè)置聚類數(shù)量和鄰域大小，還能夠根據(jù)數(shù)據(jù)集自身的分布規(guī)律進(jìn)行邊界剝離，進(jìn)而取得更好的聚類效果。

本文的主要貢獻(xiàn)如下：

(1)在自然鄰居的概念中，根據(jù)數(shù)據(jù)集的數(shù)據(jù)分布特點(diǎn)創(chuàng)新性地提出了對數(shù)自然穩(wěn)定狀態(tài)和對數(shù)自然特征值的概念和規(guī)范定義，并且給出了特性分析，給自然鄰居思想補(bǔ)充了新的理論概念。

(2)針對目標(biāo)數(shù)據(jù)集的特性，提出了一種魯棒的自然搜索算法，通過這種算法能得到符合數(shù)據(jù)分布規(guī)律的對數(shù)自然特征值。

(3)結(jié)合對數(shù)自然穩(wěn)定狀態(tài)等概念提出了無需鄰域參數(shù)的邊界剝離聚類算法NaN-BP。該算法消除了鄰域參數(shù)固定選擇的弊端，使得改進(jìn)后的算法能夠?qū)Σ煌螤顢?shù)據(jù)集進(jìn)行自適應(yīng)聚類，大幅度提高了算法的自適應(yīng)性。

(4)NaN-BP算法能夠自適應(yīng)地對不同密度不同分布的數(shù)據(jù)集進(jìn)行聚類分析，并且通過實(shí)驗(yàn)結(jié)果驗(yàn)證了其自適應(yīng)性和聚類結(jié)果的準(zhǔn)確性。

2 相關(guān)工作

2.1 自然鄰居

最近鄰居的思想被廣泛應(yīng)用于聚類算法中，幾乎所有聚類算法都或多或少地使用了最近鄰居思想，且其核心方法均基于KNN和ε-NN[1]。這2種方法都使用了鄰域參數(shù)，而鄰域參數(shù)的取值只能憑借經(jīng)驗(yàn)或者多次嘗試才能確定，且嚴(yán)重依賴數(shù)據(jù)分布情況。針對這一問題，自然鄰居方法利用自適應(yīng)的鄰域思想，提出了解決參數(shù)問題的新思路。

自然鄰居NaN是一種新的鄰居概念，這種概念產(chǎn)生于客觀現(xiàn)實(shí)的認(rèn)知。自然鄰居與KNN和ε-NN最大的不同之處在于自然鄰居不需要設(shè)置或固定某個(gè)參數(shù)k或者ε，使得數(shù)據(jù)集中每個(gè)數(shù)據(jù)的自然鄰居數(shù)目不盡相同，所以自然鄰居是一種無尺度的鄰居概念[4]。

將自然鄰居的概念融入到聚類算法的思想已經(jīng)有很多的成果，并且在各個(gè)領(lǐng)域中都具備良好的實(shí)驗(yàn)效果，例如基于噪聲去除的分層聚類算法[5]、基于自然鄰域的自適應(yīng)光譜聚類算法[6]、基于自然鄰居的聚類方法[7]和基于自然鄰域圖的聚類和離群檢測算法[8]等。在自然鄰居的構(gòu)建算法中，KNN[9]和逆k近鄰RKNN (Reverse K-Nearest Neighbor)[10]2種最近鄰居的搜索算法也被廣泛應(yīng)用。

2.2 聚類算法

聚類是將數(shù)據(jù)點(diǎn)分類為組或簇的任務(wù)，并通過簇的概念直觀展示簇間數(shù)據(jù)的差異性和簇內(nèi)數(shù)據(jù)的相似性。隨著數(shù)據(jù)分析的關(guān)注度逐漸提高，越來越多的聚類算法也被提出。其中基于劃分的聚類算法的核心思想是：按照全局優(yōu)化的標(biāo)準(zhǔn)把數(shù)據(jù)集劃分為若干類。由于基于劃分的聚類算法具有很好的理論研究基礎(chǔ)且對凸形數(shù)據(jù)集的聚類效果非常理想，是早期非常經(jīng)典的聚類思路[11]。但是，由于基于劃分的聚類算法自身的全局優(yōu)化函數(shù)的局限性，存在不適用具有流形和凹形數(shù)據(jù)集等許多問題。基于密度的聚類算法理論上能夠適用于任何形狀的數(shù)據(jù)集，但是基于密度的聚類算法對參數(shù)比較敏感，不適用于簇之間密度較大或具有復(fù)雜流形的數(shù)據(jù)集[12]?；趯哟蔚木垲愃惴ê诵乃枷胧峭ㄟ^某種相似性測度計(jì)算節(jié)點(diǎn)之間的相似性，并按相似度由高到低排序，逐步重新連接各個(gè)節(jié)點(diǎn)[13]。層次聚類的優(yōu)點(diǎn)是距離和規(guī)則的相似度容易定義，限制少，不需要預(yù)先設(shè)定聚類數(shù)，但層次聚類復(fù)雜度高，奇異值也能產(chǎn)生很大影響。譜聚類算法包含嚴(yán)密的數(shù)學(xué)邏輯，通過圖分割的方法對數(shù)據(jù)集進(jìn)行劃分，理論上能夠解決流形數(shù)據(jù)問題[14]，然而譜聚類算法很難得到真實(shí)的最優(yōu)解，且算法復(fù)雜度較高。

在上述聚類算法中，基于密度的聚類算法的聚類結(jié)果更接近日常應(yīng)用場景，研究人員也針對不同應(yīng)用領(lǐng)域提出了大量的改進(jìn)算法，Rodriguez等[15]基于密度聚類算法提出了新穎的CFDP(Clus- tering by Fast search and find of Density Peaks)聚類算法，能夠更準(zhǔn)確快速地描述密度峰值聚類，且算法復(fù)雜度更低。之后在DBSCAN(Density-Based Spatial Clustering of Applications with Noise)[16]的基礎(chǔ)上,Ding等[17]基于密度聚類算法對參數(shù)敏感的問題進(jìn)行了改進(jìn)，提出了一種新的基于密度的OPTICS(Ordering Points To Identify the Clustering Structure)聚類算法，降低了算法對參數(shù)的敏感度。Qiu等[18]提出了Grid-based Clustering 算法，主要通過掃描數(shù)據(jù)集，將數(shù)據(jù)空間根據(jù)所選屬性劃分為數(shù)個(gè)網(wǎng)格單元，并將樣本點(diǎn)劃分到相應(yīng)的單元中，最后根據(jù)單元的密度形成類簇。由于最終的簇是根據(jù)網(wǎng)格單元?jiǎng)澐值?，所以該算法對于密度閾值非常敏感，很容易丟失類簇，當(dāng)數(shù)據(jù)集存在密度相差較大的簇時(shí)，閾值設(shè)置得過高可能會(huì)丟失一部分簇，設(shè)置得過低則有可能使得本應(yīng)分開的2個(gè)類簇合并。為了進(jìn)一步提高基于密度聚類算法的效果，Huang等[19]基于聚類中心方法查找中心點(diǎn)提出了QCC(Quasi-Cluster Centers)聚類算法。Campello等[20]在DBSCAN和OPTICS基礎(chǔ)上提出了HDBSCAN(Hierarchical Density-Based Spatial Clustering of Applications with Noise)聚類算法，算法只需要一個(gè)最小集群參數(shù)就能夠自動(dòng)選擇密度閾值，但對于噪聲點(diǎn)不夠敏感。Cheng[21]使用核密度估計(jì)函數(shù)提出了Mean-Shift聚類算法對數(shù)據(jù)點(diǎn)進(jìn)行聚類，迭代地將每個(gè)數(shù)據(jù)點(diǎn)移動(dòng)到其鄰近的稠密區(qū)域，然后對移動(dòng)的數(shù)據(jù)點(diǎn)進(jìn)行聚類，但該算法往往依賴于核密度估計(jì)器的帶寬參數(shù)。Shimshoni等[22]提出了自適應(yīng)Mean-Shift方法，通過根據(jù)每個(gè)數(shù)據(jù)點(diǎn)的局部鄰域估計(jì)每個(gè)數(shù)據(jù)點(diǎn)的不同帶寬來克服Mean-Shift核密度估計(jì)器依賴的問題，但這種方法通常容易對數(shù)據(jù)進(jìn)行過度的聚類劃分。Averbuch-Elor等[23]利用邊界剝離的思想提出了一種全新的基于中心點(diǎn)的邊界剝離聚類算法，并取得了極佳的聚類效果。

邊界剝離聚類算法的核心思想是通過KNN和RKNN算法找到每個(gè)數(shù)據(jù)點(diǎn)的最近鄰居，然后取逆鄰居數(shù)排序的前1%的數(shù)據(jù)作為邊界剝離迭代的初始邊界點(diǎn)，在初始邊界點(diǎn)的基礎(chǔ)上迭代剝離數(shù)據(jù)點(diǎn)，當(dāng)所識別的邊界點(diǎn)的“邊界性”方面嚴(yán)格弱于迭代中所識別的邊界點(diǎn)時(shí)，剝離迭代終止，剩下的便是核心點(diǎn)集。最后使用簡化版本的DBSCAN將這些核心點(diǎn)分組到數(shù)據(jù)簇中，根據(jù)每次迭代建立的邊界點(diǎn)與非邊界點(diǎn)的關(guān)聯(lián)完成自下而上的聚類。

然而邊界剝離聚類算法在不同形狀數(shù)據(jù)集上選取的初始邊界點(diǎn)極其依賴鄰域參數(shù)k的選擇，從而使得在邊界點(diǎn)迭代剝離的過程中從邊界點(diǎn)到核心點(diǎn)的過程存在產(chǎn)生偏差的可能，進(jìn)而影響聚類的結(jié)果，甚至在部分?jǐn)?shù)據(jù)集中出現(xiàn)極為不合理的數(shù)據(jù)簇劃分?；谏鲜鰡栴}，本文提出了一種新的將自然鄰居與邊界剝離聚類算法相結(jié)合的算法——NaN-BP。該算法既能夠保留原來邊界剝離聚類的優(yōu)勢，又彌補(bǔ)了邊界剝離聚類算法中始終存在鄰域參數(shù)的缺陷，在不同形狀的數(shù)據(jù)集上都無需設(shè)置鄰域參數(shù)，并自適應(yīng)得到符合數(shù)據(jù)分布特征的聚類結(jié)果。

3 基于自然鄰居思想的邊界剝離聚類算法

3.1 自然鄰居思想

假設(shè)數(shù)據(jù)集X={x1,x2,x3,…,xn},其中，數(shù)據(jù)集長度為n，之后涉及的數(shù)據(jù)集默認(rèn)為此形式。

定義1(自然鄰居) 當(dāng)數(shù)據(jù)集處在自然穩(wěn)定狀態(tài)時(shí)，互為鄰居的點(diǎn)即互為自然鄰居。即對于任意xi,xj，都有：

xj∈NaN(xi)?(xi∈KNNλ(xj))∧

(xj∈KNNλ(xi))

其中，KNNλ(xj)代表數(shù)據(jù)點(diǎn)xj的λ最近鄰域，即xj的前λ個(gè)最近鄰居組成的集合，λ為自然特征值，其定義如定義3所示。

自然鄰居與傳統(tǒng)的最近鄰居有著很大的區(qū)別，在整個(gè)自然鄰居搜索過程中，不需要鄰域參數(shù)，根據(jù)數(shù)據(jù)集的分布規(guī)律找到每個(gè)點(diǎn)的鄰居，每個(gè)點(diǎn)的自然鄰居個(gè)數(shù)都不一定相同，其鄰居的數(shù)量取決于數(shù)據(jù)集的分布，而且能夠根據(jù)數(shù)據(jù)集找到每個(gè)點(diǎn)的合適的鄰居個(gè)數(shù)。

定義2(自然穩(wěn)定狀態(tài)) 依次取k=1,2,3,…,n對數(shù)據(jù)集X進(jìn)行KNN查找，在算法查找過程中，當(dāng)k=r時(shí)，數(shù)據(jù)集中任意一點(diǎn)至少存在另一個(gè)數(shù)據(jù)點(diǎn)與其互為鄰居，此時(shí)數(shù)據(jù)集所處的狀態(tài)為自然穩(wěn)定狀態(tài)。

定義3(自然特征值) 當(dāng)數(shù)據(jù)集X處于自然穩(wěn)定狀態(tài)時(shí)，自然鄰居特征值λ即為當(dāng)前的KNN鄰域大小r。在整個(gè)搜索過程中，自然特征值是實(shí)際運(yùn)行過程的最大循環(huán)次數(shù)，反映了數(shù)據(jù)集的分布規(guī)律。

3.2 邊界剝離聚類基本原理

下面給出邊界剝離聚類的相關(guān)符號定義和概念。

在邊界剝離的迭代過程中，第t次迭代時(shí)邊界點(diǎn)的集合定義為：

下一次未剝離的邊界點(diǎn)集合為:

X(t+1)=X(t)

在識別邊界點(diǎn)之后，將每一個(gè)邊界點(diǎn)與一個(gè)離其最近的非邊界點(diǎn)相關(guān)聯(lián)，非邊界點(diǎn)用關(guān)聯(lián)結(jié)點(diǎn)ρi∈X(t+1)來表示。在這一過程中，算法也會(huì)將部分點(diǎn)標(biāo)記為離群點(diǎn)，這些點(diǎn)不屬于任何簇。關(guān)聯(lián)節(jié)點(diǎn)ρi定義為：

其中,li是一個(gè)可變的閾值，若邊界點(diǎn)xi到非邊界點(diǎn)集合中最近的非邊界點(diǎn)xj的距離δ(xi,xj)超過可變閾值li，xi則會(huì)標(biāo)記為離群點(diǎn)，若在可變閾值之內(nèi)，那么ρi就是距離xi最近的非邊界點(diǎn)。

最后經(jīng)過數(shù)次迭代剝離邊界點(diǎn)，最終剩余的非邊界點(diǎn)就是核心點(diǎn)，每個(gè)核心點(diǎn)都有到最初邊界點(diǎn)的傳遞關(guān)聯(lián)，通過文獻(xiàn)[22]的方法，逐漸合并每一對可達(dá)的核心點(diǎn)，最終通過與核心點(diǎn)的邊界點(diǎn)關(guān)聯(lián)和鏈接來定義候選類簇，同時(shí)為了更好地濾除離群點(diǎn)，使用用戶定義的最小集群大小值將小集群標(biāo)記為噪聲，返回最后一組的類簇。

3.3 基于自然鄰居的邊界剝離聚類算法

對于給定數(shù)據(jù)集X，基于自然鄰居的邊界剝離聚類方法會(huì)先根據(jù)數(shù)據(jù)集的特點(diǎn)，進(jìn)行魯棒的自然鄰居搜索，找到數(shù)據(jù)集的對數(shù)自然穩(wěn)定狀態(tài)，并且當(dāng)數(shù)據(jù)集達(dá)到對數(shù)自然穩(wěn)定狀態(tài)時(shí)，得到數(shù)據(jù)集的對數(shù)自然特征值。整個(gè)自然鄰居思想都是非參數(shù)的，沒有指定集群個(gè)數(shù)的鄰域參數(shù)，之后使用對數(shù)自然特征值來取代邊界剝離的鄰域參數(shù)k，確定初始的邊界點(diǎn)，通過反復(fù)剝離邊界點(diǎn)，最終剩下的點(diǎn)為核心點(diǎn)，最后核心點(diǎn)根據(jù)與邊界點(diǎn)之間的傳遞關(guān)聯(lián)，自底向上完成整個(gè)聚類。

整個(gè)算法分為2個(gè)部分，首先用魯棒的自然鄰居搜索算法對數(shù)據(jù)集進(jìn)行對數(shù)自然鄰居搜索，使數(shù)據(jù)集達(dá)到對數(shù)自然穩(wěn)定狀態(tài)，得到數(shù)據(jù)集的對數(shù)自然特征值；其次根據(jù)數(shù)據(jù)的分布規(guī)律得出對數(shù)自然特征值，生成合理的初始邊界點(diǎn)，然后進(jìn)行邊界點(diǎn)迭代剝離并逐步完成聚類。

定義4(噪聲點(diǎn)集-NOS) 對數(shù)據(jù)集進(jìn)行自然鄰居搜索，當(dāng)搜索迭代次數(shù)達(dá)到λ時(shí)，噪聲點(diǎn)集中任意數(shù)據(jù)點(diǎn)沒有對數(shù)自然鄰居,其形式化定義為:

xi∈NOS?KNNλ(xi)=?

定義5(對數(shù)自然穩(wěn)定狀態(tài)) 給定數(shù)據(jù)集X={x1,x2,x3,…,xn}，在自然穩(wěn)定狀態(tài)的查找過程中，數(shù)據(jù)集除了噪聲點(diǎn)外，其他數(shù)據(jù)點(diǎn)在搜索查找深度達(dá)到λ+lnn時(shí)，都存在至少一個(gè)自然鄰居，稱之為對數(shù)自然穩(wěn)定狀態(tài)，其形式化定義如下：

?xi,xj∈NOS?(xj?KNNλ(xi))∧

(xj?KNNλ+ln n(xi))

當(dāng)數(shù)據(jù)集中存在噪聲點(diǎn)時(shí)，會(huì)大大增加自然鄰居的搜索難度，所以將數(shù)據(jù)集的長度的自然對數(shù)與自然特征值λ的和(λ+lnn)作為搜索次數(shù)的閾值。使用魯棒的自然鄰居搜索算法，當(dāng)自然鄰居的個(gè)數(shù)不變次數(shù)超過閾值，便認(rèn)為已達(dá)到對數(shù)自然穩(wěn)定狀態(tài)。

定義6(對數(shù)自然特征值) 當(dāng)數(shù)據(jù)集X處于對數(shù)自然穩(wěn)定狀態(tài)時(shí)，針對對數(shù)自然穩(wěn)定狀態(tài)，本文提出了對數(shù)自然特征值，其形式化定義如下：

r=(λ+lnn)λ∈N,ln n∈N{λ|?(xi,xj?NOS)∧

?(xj∈KNNλ+ln n(xi))∧(xi≠xj)→

?(xi∈KNNλ+ln n(xj))}

其中,λ+lnn表示魯棒的自然鄰居搜索算法查找的深度，對數(shù)自然特征值根據(jù)數(shù)據(jù)集的分布特點(diǎn)，同時(shí)也可以作為傳統(tǒng)KNN鄰域參數(shù)的參考。

定義7(對數(shù)自然鄰居) 當(dāng)數(shù)據(jù)集處在對數(shù)自然穩(wěn)定狀態(tài)時(shí)，互為鄰居的點(diǎn)即互為對數(shù)自然鄰居。即對于任意xi,xj都有：

xj∈NaN(xi)?

(xj∈KNNλ(xi))∧(xi∈KNNλ(xj))

本文所提出的魯棒的自然鄰居搜索算法如算法1所示：

算法1自然鄰居搜索算法

Input:X={x1,x2,x3,…,xn}∈Rd。

Output:自然特征值λ,逆鄰居數(shù)Rnum(i)。

/*初始化逆鄰居數(shù)Rnum(i)，r-最近鄰域KNNr(xi)和逆r-最近鄰域RKNNr(xi)*/

Initialization:

r=1,Rnum(i)=0,KNNr(xi)=?,RKNNr(xi)=?;

//計(jì)算數(shù)據(jù)集的長度，并取自然對數(shù)得到終止閾值

ξ=ln(n);

//創(chuàng)建一棵KD-樹

KD-tree=creatKDTree(X);

While(Flag= 0)

//利用KD-樹搜索數(shù)據(jù)xi的第r個(gè)鄰居yr

Rnum(yr)=Rnum(yr)+1;

KNNr(xi)=KNNr(xi)∪{yr};

RKNNr(x)=RKNNr(xi)∪{xi};

計(jì)算Rnum(i)=0的元素個(gè)數(shù)Rzero;

IFRzero不變

T=T+1;

EndIF

IF(T<ξ)

r=r+1;

Else

Flag= 1;

EndIF

EndWhile

λ=r;

算法1中KNNr(xi)表示由數(shù)據(jù)xi最近的r個(gè)最近鄰居組成的r-最近鄰域。RKNNr(xi)表示由數(shù)據(jù)xi最近的r個(gè)逆最近鄰居組成的逆r-最近鄰域。魯棒的自然鄰居搜索算法首先給每個(gè)數(shù)據(jù)點(diǎn)找1個(gè)鄰居，然后計(jì)算數(shù)據(jù)集中逆鄰居點(diǎn)為0的點(diǎn)數(shù)，再給每個(gè)數(shù)據(jù)點(diǎn)找2個(gè)鄰居，計(jì)算數(shù)據(jù)集中逆鄰居點(diǎn)為0的數(shù)據(jù)點(diǎn)的數(shù)量Rzero。鄰居搜索過程中，算法不斷增加每個(gè)數(shù)據(jù)點(diǎn)鄰居的個(gè)數(shù)，并且更新逆鄰居點(diǎn)為0的數(shù)據(jù)點(diǎn)數(shù)量Rzero。若逆鄰居數(shù)為0的點(diǎn)數(shù)在ξ次沒有發(fā)生變化，算法便判定當(dāng)前搜索達(dá)到對數(shù)自然穩(wěn)定狀態(tài)，此時(shí)所尋找的鄰居數(shù)即為對數(shù)自然特征值λ。

圖1展示了NaN-BP算法中初始邊界點(diǎn)選取的優(yōu)越性。通過對比可以看到，NaN-BP算法中用深色點(diǎn)標(biāo)識的初始的邊界點(diǎn)更符合邊界點(diǎn)的定義。特別是在圖中標(biāo)注的圓圈內(nèi)，從直觀上可以看出，其處于簇心位置，明顯應(yīng)該是核心點(diǎn)的候選，而不應(yīng)該被當(dāng)前步驟標(biāo)記為邊緣點(diǎn)。NaN-BP算法確定的邊界點(diǎn)在這幾處基本為零，而BP算法將部分核心點(diǎn)判定為不合理的邊界點(diǎn)。圖1形象地證明了在不同形狀的數(shù)據(jù)集上，使用NaN-BP算法產(chǎn)生的初始邊界點(diǎn)要比BP聚類算法產(chǎn)生的初始邊界點(diǎn)更加合理，初始的邊界點(diǎn)除去遠(yuǎn)離類簇的噪聲點(diǎn)，基本上都合理地分布在類簇邊緣。而BP聚類算法在不同形狀的數(shù)據(jù)集上初始邊界點(diǎn)的確定不夠理想，導(dǎo)致了對數(shù)據(jù)集的自適應(yīng)能力不足，進(jìn)而嚴(yán)重影響后續(xù)算法中核心點(diǎn)的選取。

Figure 1 Comparison of initial border points in two algorithms圖1 2個(gè)算法的初始邊界點(diǎn)對比

定義8(相似性度量) NaN-BP算法采用歐幾里得距離和高斯核σj構(gòu)建函數(shù)相似性度量f來反映數(shù)據(jù)點(diǎn)之間的距離，其定義如下：

基于對數(shù)自然特征值的邊界點(diǎn)迭代剝離聚類算法NaN-BP如算法2所示：

算法2基于自然鄰居的邊界剝離聚類算法NaN-BP

Input:X={x1,x2,x3,…,xn}∈Rd。

Output:Cluster indicesC。

r←Algorithm 1;

//通過對數(shù)自然特征值生成初始邊界剝離點(diǎn)

X1←X;

Forpeeling iteration 1 ≤t≤Tdo

Foreach pointxi∈Xtdo

EndFor

X(t+1)←X(t);

ρi←ASSOCIATEPOINT(xi,X(t+1))

EndFor

EndFor

//根據(jù)核心點(diǎn)的關(guān)聯(lián)完成聚類，ρ的ρi組成的集合

整個(gè)算法的核心步驟由以下2部分組成：(1)自適應(yīng)數(shù)據(jù)集達(dá)到對數(shù)自然穩(wěn)定狀態(tài)，生成對數(shù)自然特征值；(2)利用對數(shù)自然特征值確定合理的初始邊界點(diǎn)，進(jìn)行邊界剝離聚類。算法1和算法2的偽代碼對其步驟進(jìn)行了詳細(xì)的描述。NaN-BP算法首先解決了原有BP聚類算法固有鄰域參數(shù)的缺陷。算法利用魯棒的自然搜索算法使數(shù)據(jù)集達(dá)到對數(shù)自然穩(wěn)定狀態(tài)，同時(shí)得到對數(shù)自然特征值和對數(shù)自然鄰居，能根據(jù)不同形狀的數(shù)據(jù)集產(chǎn)生不同的對數(shù)自然特征值。在此基礎(chǔ)上，算法用對數(shù)自然特征值取代原有BP聚類算法鄰域參數(shù)，因此能夠在不同數(shù)據(jù)集上得到更好地聚類效果。其次，NaN-BP算法得到的鄰域參數(shù)能更好地適應(yīng)數(shù)據(jù)集分布規(guī)律，在邊界點(diǎn)迭代剝離的過程中能夠建立良好的初始邊界點(diǎn)。在邊界點(diǎn)剝離的過程中，初始邊界點(diǎn)的確立對于不同形狀數(shù)據(jù)集的最終聚類效果有很大的影響。BP聚類算法采用固有的鄰域參數(shù)，當(dāng)面對不同形狀數(shù)據(jù)集時(shí)，初始邊界點(diǎn)確立的自適應(yīng)能力明顯不夠。而NaN-BP算法很好地解決了這個(gè)問題，并在后續(xù)實(shí)驗(yàn)中形象地展示了其優(yōu)越性。

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

為了評估基于自然鄰居的邊界剝離聚類算法更加具有普適性，本文選取了6個(gè)不同形狀的數(shù)據(jù)集(flame、R15[22]、Compound、D31、data_DBScan和artificialdata[4])進(jìn)行了測試，并將其與邊界剝離聚類算法進(jìn)行了性能對比。邊界剝離聚類算法的最終聚類效果很大程度上依賴于初始邊界點(diǎn)的確定，初始邊界點(diǎn)的確定與鄰域參數(shù)k有著直接關(guān)系，所以本文在不同形狀的數(shù)據(jù)集上對邊界剝離聚類算法依舊保留原有的固定參數(shù)。算法根據(jù)數(shù)據(jù)特征自適應(yīng)得到的可變鄰域能對邊界剝離的初始邊界點(diǎn)進(jìn)行更為準(zhǔn)確的判斷，因此在無需預(yù)設(shè)參數(shù)的情況下，算法在不同形狀的數(shù)據(jù)集上都有很好的效果。

實(shí)驗(yàn)部分按照數(shù)據(jù)集的特性，分別從有監(jiān)督、無監(jiān)督和高維大數(shù)據(jù)3個(gè)角度展開了對比，在多種評價(jià)維度上驗(yàn)證了本文提出的NaN-BP算法的優(yōu)越性。

4.1 有監(jiān)督數(shù)據(jù)集實(shí)驗(yàn)

為了驗(yàn)證本文NaN-BP算法的優(yōu)越性，選取了BP聚類算法中使用過的人工數(shù)據(jù)集進(jìn)行對比實(shí)驗(yàn)。實(shí)驗(yàn)選取的4個(gè)數(shù)據(jù)集均帶有真實(shí)標(biāo)簽，評價(jià)指標(biāo)為ARI和AMI。

ARI是描述隨機(jī)分配類簇標(biāo)記向量的相似度指標(biāo)，定義為:

其中，E表示期望，max表示取最大值，RI是蘭德系數(shù)。

AMI是基于預(yù)測簇向量與真實(shí)簇向量的互信息分?jǐn)?shù)來衡量其相似度的，AMI越大相似度越高，定義為:

其中,E{MI(U,V)}為互信息MI(U,V)的期望，H(U)和H(V)為信息熵。

在數(shù)據(jù)集(flame、R15、Compound和D31)上的實(shí)驗(yàn)結(jié)果如圖2所示，在數(shù)據(jù)集flame和R15上，本文NaN-BP算法有不弱于原有BP聚類算法的競爭力，在R15數(shù)據(jù)集上甚至效果更好。在另外2個(gè)不同形狀的數(shù)據(jù)集Compound和D31上，本文算法的優(yōu)勢非常明顯。Compound數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果顯示本文算法能夠較好地區(qū)分不同形狀數(shù)據(jù)集的類簇，而D31數(shù)據(jù)集上的結(jié)果表明本文算法對離群點(diǎn)的確定也更合理。

Figure 2 Experimental results comparison with BP clustering algorithm on flame,R15,Compound and D31 data sets圖2 與BP聚類算法在flame、R15、Compound和D31數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果比較

表1詳細(xì)列舉了圖2中前2個(gè)數(shù)據(jù)集(flame和R15)上的評價(jià)結(jié)果。圖中Det# 表示最終聚類的個(gè)數(shù)，K在BP算法中表示人為設(shè)置的鄰域參數(shù)，在NaN-BP算法中由于無需設(shè)置參數(shù)，因此其表示自適應(yīng)計(jì)算生成的自然鄰居特征值。可以直觀地看到，本文提出的NaN-BP聚類算法在原文使用的2個(gè)不同形狀的數(shù)據(jù)集上依然能表現(xiàn)出良好的效果，特別是在表中鄰域參數(shù)部分，BP算法是人為預(yù)設(shè)的參數(shù)，所以無法針對數(shù)據(jù)集的特征進(jìn)行調(diào)整，而NaN-BP算法無需設(shè)置這一參數(shù)，同時(shí)在ARI和AMI評價(jià)指標(biāo)上表現(xiàn)出更為優(yōu)秀的結(jié)果。

Table 1 Performance comparison on flame,R15 data sets

表2詳細(xì)列舉了圖2中后2個(gè)數(shù)據(jù)集(Compound，D31)上的評價(jià)結(jié)果。通過其可以直觀地看到，在另外2個(gè)不同形狀的有監(jiān)督數(shù)據(jù)集Compound和D31上，NaN-BP算法生成的對數(shù)自然特征值都很好地自適應(yīng)了數(shù)據(jù)分布規(guī)律，并且在ARI和AMI2個(gè)評價(jià)指標(biāo)上都超過了BP聚類算法，表明本文算法對不同形狀數(shù)據(jù)集具有很好的自適應(yīng)力。

Table 2 Performance comparison on Compound,D31 data sets表2 數(shù)據(jù)集Compound,D31上的性能比較

4.2 無監(jiān)督數(shù)據(jù)集實(shí)驗(yàn)

為了證明本文NaN-BP算法在無監(jiān)督數(shù)據(jù)集上依然具有很強(qiáng)的競爭力，接下來使用2個(gè)不同形狀的數(shù)據(jù)集(data_DBScan和artificialdata[4])分別對BP聚類算法和NaN-BP算法進(jìn)行了測試。在這種具有大量離群點(diǎn)的球型數(shù)據(jù)集上，NaN-BP算法取得了更為直觀和顯著的聚類效果提升。除了聚類結(jié)果之外，本文所提出的NaN-BP算法能夠根據(jù)不同的數(shù)據(jù)分布特征自適應(yīng)地進(jìn)行鄰域分析，從而使得邊界剝離的初始邊界點(diǎn)在數(shù)量和位置上都要比BP聚類算法更加優(yōu)越。

在數(shù)據(jù)集data_DBScan和artificialdata上的實(shí)驗(yàn)結(jié)果如圖3所示。本文所提出的NaN-BP算法表現(xiàn)出很強(qiáng)的自適應(yīng)性能，正確地恢復(fù)了原有的簇?cái)?shù)量，并且在離群點(diǎn)的確定上也有很好的效果。作為對比，BP聚類算法沒有得到有效的聚類結(jié)果，并且最終離群點(diǎn)的劃分也很不理想。這也說明了NaN-BP算法在不同形狀、不同聚類數(shù)量的數(shù)據(jù)集上具有自適應(yīng)能力，而這種自適應(yīng)產(chǎn)生鄰域參數(shù)的方法，在邊界剝離的過程中，能夠更好地確定初始邊界點(diǎn)，同時(shí)也在很大程度上優(yōu)化了最后的聚類結(jié)果和離群點(diǎn)的劃分。

Figure 3 Experimental results comparison with BP clustering algorithm on data_DBScan and artificialdata data sets圖3 與BP聚類算法在數(shù)據(jù)集data_DBScan和artificialdata上的實(shí)驗(yàn)結(jié)果比較

實(shí)驗(yàn)表明，在具有大量離群點(diǎn)的無監(jiān)督數(shù)據(jù)集上，在聚類數(shù)量和聚類質(zhì)量等多個(gè)方面，NaN-BP算法的聚類效果都要遠(yuǎn)優(yōu)于BP聚類算法的。

Figure 4 Comparison of embedding results between BP clustering algorithm and NaN-BP algorithm on three data sets圖4 BP聚類算法和NaN-BP算法在3個(gè)數(shù)據(jù)集上的聚類結(jié)果比較

4.3 大數(shù)據(jù)集上的實(shí)驗(yàn)

接下來本文將通過規(guī)模更大的數(shù)據(jù)集進(jìn)一步驗(yàn)證NaN-BP算法的優(yōu)越性。本文選用MNIST作為大規(guī)模高維數(shù)據(jù)的測試對象，并通過卷積神經(jīng)網(wǎng)絡(luò)CNN(Convolutional Neural Network)生成具有500維特征的有標(biāo)簽的高維多分類數(shù)據(jù)[24]。為了進(jìn)一步驗(yàn)證NaN-BP算法的自適應(yīng)性，在原始數(shù)據(jù)集的基礎(chǔ)上隨機(jī)生成簇?cái)?shù)未知并且形狀不定的數(shù)據(jù)集，并通過在大數(shù)據(jù)集上不同半徑內(nèi)數(shù)據(jù)隨機(jī)采樣的方法，最終得到3個(gè)數(shù)據(jù)集(D1、D2和D3)。這3個(gè)數(shù)據(jù)集的采樣半徑分別為120，130，140，每個(gè)數(shù)據(jù)集包括上千條數(shù)據(jù)，數(shù)據(jù)維度為500。再對采樣的數(shù)據(jù)進(jìn)行降維處理，將原始數(shù)據(jù)的維度從500降至30。通過分析圖4可以看出，針對3個(gè)不同形狀數(shù)據(jù)集的特點(diǎn)，本文NaN-BP算法依然能自適應(yīng)生成對數(shù)自然特征值，使得邊界剝離的初始邊界點(diǎn)選取更具有普適性，而且在離群點(diǎn)的確定上本文算法更加合理。尤其在D2和D3數(shù)據(jù)集上本文算法的聚類效果表現(xiàn)出比原有BP聚類算法更好的競爭力。

表3所示為BP算法和NaN-BP算法在數(shù)據(jù)集上進(jìn)行10次聚類分析得到的結(jié)果平均值。從表3的實(shí)驗(yàn)結(jié)果可以看出，NaN-BP算法產(chǎn)生的結(jié)果在高維數(shù)據(jù)集上有著很好的表現(xiàn)，雖然在數(shù)據(jù)集D1上NaN-BP算法略差于BP聚類算法，但最后的聚類評價(jià)指標(biāo)差距不大。在數(shù)據(jù)集D2和D3上本文算法各個(gè)性能都超過了BP聚類算法，最終表現(xiàn)的聚類效果也更好。

4.4 算法性能和運(yùn)行細(xì)節(jié)

Table 3 Performance comparison with BP clustering algorithm on MNIST data set 表3 在MNIST數(shù)據(jù)集上與BP聚類算法的性能比較

2.30 GHz Intel Core i5的Windows 10系統(tǒng)上實(shí)現(xiàn)的，在運(yùn)行時(shí)間上，因?yàn)槭褂米匀秽従拥母倪M(jìn)，整體的運(yùn)算時(shí)間要比BP聚類算法稍長，但相對最后比較理想的效果來說，運(yùn)行時(shí)間的增加完全可以忽略。

4.5 實(shí)驗(yàn)小結(jié)

為了證明NaN-BP算法對數(shù)據(jù)集的自適應(yīng)聚類結(jié)果，本文在各種不同形狀、不同維度的數(shù)據(jù)集上都做了對比實(shí)驗(yàn)。多組實(shí)驗(yàn)結(jié)果表明，NaN-BP算法能夠自適應(yīng)地解決不同數(shù)據(jù)集的鄰域參數(shù)設(shè)定問題，得到了效果良好的初始邊界點(diǎn)，并取得了令人滿意的聚類效果。同時(shí)，NaN-BP算法與BP聚類算法的對比結(jié)果也表明了本文算法在面對不同形狀的數(shù)據(jù)集聚類時(shí)，具有更好的自適應(yīng)性和穩(wěn)定性。

5 結(jié)束語

本文針對聚類算法中聚類數(shù)目和鄰域參數(shù)等參數(shù)自適應(yīng)問題，提出了一種基于自然鄰居思想的邊界剝離聚類算法——NaN-BP算法。NaN-BP算法通過魯棒的自然搜索算法，自適應(yīng)不同形狀的數(shù)據(jù)集，生成反映數(shù)據(jù)集分布規(guī)律的對數(shù)自然特征值，利用對數(shù)自然特征值取代固定的鄰域參數(shù)。當(dāng)數(shù)據(jù)集達(dá)到對數(shù)自然穩(wěn)定狀態(tài)時(shí)，同時(shí)得到數(shù)據(jù)集的對數(shù)自然特征值和對數(shù)自然鄰居，對數(shù)自然特征值也體現(xiàn)了數(shù)據(jù)的分布規(guī)律。當(dāng)達(dá)到對數(shù)自然穩(wěn)定狀態(tài)時(shí)，每個(gè)數(shù)據(jù)點(diǎn)的對數(shù)自然鄰居數(shù)不一定相同，不同的鄰居數(shù)更進(jìn)一步體現(xiàn)了數(shù)據(jù)集的數(shù)據(jù)分布規(guī)律。NaN-BP算法使用自然特征值能夠根據(jù)不同形狀的數(shù)據(jù)集確定更理想的初始邊界點(diǎn)，使得在邊界剝離的逐次迭代中邊界點(diǎn)與核心點(diǎn)的關(guān)聯(lián)更加合理，最后自下而上的聚類便能產(chǎn)生很好的效果。

與其他聚類算法不同的是，本文算法使用自然鄰居思想，能夠根據(jù)不同形狀的數(shù)據(jù)集自適應(yīng)產(chǎn)生理想的初始邊界點(diǎn)，實(shí)驗(yàn)也表明初始邊界點(diǎn)分布對最終的聚類效果有很重要的影響。在整個(gè)實(shí)驗(yàn)中，不論在BP聚類算法原有的實(shí)驗(yàn)數(shù)據(jù)集上，還是在其他大量不同形狀的數(shù)據(jù)集上，本文算法都比原有的BP聚類算法更具競爭力，自適應(yīng)能力也更加理想。

雖然NaN-BP算法在參數(shù)自適應(yīng)和聚類結(jié)果上都取得了令人滿意的成果，但其仍然有進(jìn)一步提升的空間。在后續(xù)的工作中，將在保持算法無需鄰域參數(shù)的核心優(yōu)勢的同時(shí)，嘗試通過算法的優(yōu)化進(jìn)一步提高NaN-BP算法在半監(jiān)督數(shù)據(jù)集上的聚類結(jié)果，并進(jìn)一步加強(qiáng)針對現(xiàn)實(shí)場景中聚類分析的普適性研究。同時(shí)，在自適應(yīng)鄰居關(guān)系的構(gòu)建方面，將探索流形數(shù)據(jù)交疊與自動(dòng)數(shù)據(jù)標(biāo)記等問題，嘗試對自然鄰居思想進(jìn)行有針對性的改進(jìn)與優(yōu)化，探索自然鄰域圖和動(dòng)態(tài)鄰居等思想對聚類算法的改進(jìn)與提高。