一種去除聚類數(shù)量和鄰域參數(shù)設(shè)置的自適應(yīng)聚類算法 *

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

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

1 引言

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

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

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

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

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

(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)行聚類分析，并且通過實驗結(jié)果驗證了其自適應(yīng)性和聚類結(jié)果的準(zhǔn)確性。

2 相關(guān)工作

2.1 自然鄰居

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

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

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

2.2 聚類算法

聚類是將數(shù)據(jù)點分類為組或簇的任務(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ù)集等許多問題?；诿芏鹊木垲愃惴ɡ碚撋夏軌蜻m用于任何形狀的數(shù)據(jù)集，但是基于密度的聚類算法對參數(shù)比較敏感，不適用于簇之間密度較大或具有復(fù)雜流形的數(shù)據(jù)集[12]?；趯哟蔚木垲愃惴ê诵乃枷胧峭ㄟ^某種相似性測度計算節(jié)點之間的相似性，并按相似度由高到低排序，逐步重新連接各個節(jié)點[13]。層次聚類的優(yōu)點是距離和規(guī)則的相似度容易定義，限制少，不需要預(yù)先設(shè)定聚類數(shù)，但層次聚類復(fù)雜度高，奇異值也能產(chǎn)生很大影響。譜聚類算法包含嚴(yán)密的數(shù)學(xué)邏輯，通過圖分割的方法對數(shù)據(jù)集進(jìn)行劃分，理論上能夠解決流形數(shù)據(jù)問題[14]，然而譜聚類算法很難得到真實的最優(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ù)個網(wǎng)格單元，并將樣本點劃分到相應(yīng)的單元中，最后根據(jù)單元的密度形成類簇。由于最終的簇是根據(jù)網(wǎng)格單元劃分的，所以該算法對于密度閾值非常敏感，很容易丟失類簇，當(dāng)數(shù)據(jù)集存在密度相差較大的簇時，閾值設(shè)置得過高可能會丟失一部分簇，設(shè)置得過低則有可能使得本應(yīng)分開的2個類簇合并。為了進(jìn)一步提高基于密度聚類算法的效果，Huang等[19]基于聚類中心方法查找中心點提出了QCC(Quasi-Cluster Centers)聚類算法。Campello等[20]在DBSCAN和OPTICS基礎(chǔ)上提出了HDBSCAN(Hierarchical Density-Based Spatial Clustering of Applications with Noise)聚類算法，算法只需要一個最小集群參數(shù)就能夠自動選擇密度閾值，但對于噪聲點不夠敏感。Cheng[21]使用核密度估計函數(shù)提出了Mean-Shift聚類算法對數(shù)據(jù)點進(jìn)行聚類，迭代地將每個數(shù)據(jù)點移動到其鄰近的稠密區(qū)域，然后對移動的數(shù)據(jù)點進(jìn)行聚類，但該算法往往依賴于核密度估計器的帶寬參數(shù)。Shimshoni等[22]提出了自適應(yīng)Mean-Shift方法，通過根據(jù)每個數(shù)據(jù)點的局部鄰域估計每個數(shù)據(jù)點的不同帶寬來克服Mean-Shift核密度估計器依賴的問題，但這種方法通常容易對數(shù)據(jù)進(jìn)行過度的聚類劃分。Averbuch-Elor等[23]利用邊界剝離的思想提出了一種全新的基于中心點的邊界剝離聚類算法，并取得了極佳的聚類效果。

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

然而邊界剝離聚類算法在不同形狀數(shù)據(jù)集上選取的初始邊界點極其依賴鄰域參數(shù)k的選擇，從而使得在邊界點迭代剝離的過程中從邊界點到核心點的過程存在產(chǎn)生偏差的可能，進(jìn)而影響聚類的結(jié)果，甚至在部分?jǐn)?shù)據(jù)集中出現(xiàn)極為不合理的數(shù)據(jù)簇劃分。基于上述問題，本文提出了一種新的將自然鄰居與邊界剝離聚類算法相結(jié)合的算法——NaN-BP。該算法既能夠保留原來邊界剝離聚類的優(yōu)勢，又彌補了邊界剝離聚類算法中始終存在鄰域參數(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)時，互為鄰居的點即互為自然鄰居。即對于任意xi,xj，都有：

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

(xj∈KNNλ(xi))

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

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

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

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

3.2 邊界剝離聚類基本原理

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

在邊界剝離的迭代過程中，第t次迭代時邊界點的集合定義為：

下一次未剝離的邊界點集合為:

X(t+1)=X(t)

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

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

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

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

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

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

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

xi∈NOS?KNNλ(xi)=?

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

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

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

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

定義6(對數(shù)自然特征值) 當(dāng)數(shù)據(jù)集X處于對數(shù)自然穩(wěn)定狀態(tài)時，針對對數(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ù)集的分布特點，同時也可以作為傳統(tǒng)KNN鄰域參數(shù)的參考。

定義7(對數(shù)自然鄰居) 當(dāng)數(shù)據(jù)集處在對數(shù)自然穩(wěn)定狀態(tài)時，互為鄰居的點即互為對數(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)=?;

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

ξ=ln(n);

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

KD-tree=creatKDTree(X);

While(Flag= 0)

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

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

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

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

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

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

Figure 1 Comparison of initial border points in two algorithms圖1 2個算法的初始邊界點對比

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

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

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

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

Output:Cluster indicesC。

r←Algorithm 1;

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

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ù)核心點的關(guān)聯(lián)完成聚類，ρ的ρi組成的集合

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

4 實驗

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

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

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

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

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

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

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

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

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

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ù)集上的實驗結(jié)果比較

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

Table 1 Performance comparison on flame,R15 data sets

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

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

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

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

實驗表明，在具有大量離群點的無監(jiān)督數(shù)據(jù)集上，在聚類數(shù)量和聚類質(zhì)量等多個方面，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個數(shù)據(jù)集上的聚類結(jié)果比較

4.3 大數(shù)據(jù)集上的實驗

接下來本文將通過規(guī)模更大的數(shù)據(jù)集進(jì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)一步驗證NaN-BP算法的自適應(yīng)性，在原始數(shù)據(jù)集的基礎(chǔ)上隨機生成簇數(shù)未知并且形狀不定的數(shù)據(jù)集，并通過在大數(shù)據(jù)集上不同半徑內(nèi)數(shù)據(jù)隨機采樣的方法，最終得到3個數(shù)據(jù)集(D1、D2和D3)。這3個數(shù)據(jù)集的采樣半徑分別為120，130，140，每個數(shù)據(jù)集包括上千條數(shù)據(jù)，數(shù)據(jù)維度為500。再對采樣的數(shù)據(jù)進(jìn)行降維處理，將原始數(shù)據(jù)的維度從500降至30。通過分析圖4可以看出，針對3個不同形狀數(shù)據(jù)集的特點，本文NaN-BP算法依然能自適應(yīng)生成對數(shù)自然特征值，使得邊界剝離的初始邊界點選取更具有普適性，而且在離群點的確定上本文算法更加合理。尤其在D2和D3數(shù)據(jù)集上本文算法的聚類效果表現(xiàn)出比原有BP聚類算法更好的競爭力。

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

4.4 算法性能和運行細(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)上實現(xiàn)的，在運行時間上，因為使用自然鄰居的改進(jìn)，整體的運算時間要比BP聚類算法稍長，但相對最后比較理想的效果來說，運行時間的增加完全可以忽略。

4.5 實驗小結(jié)

為了證明NaN-BP算法對數(shù)據(jù)集的自適應(yīng)聚類結(jié)果，本文在各種不同形狀、不同維度的數(shù)據(jù)集上都做了對比實驗。多組實驗結(jié)果表明，NaN-BP算法能夠自適應(yīng)地解決不同數(shù)據(jù)集的鄰域參數(shù)設(shè)定問題，得到了效果良好的初始邊界點，并取得了令人滿意的聚類效果。同時，NaN-BP算法與BP聚類算法的對比結(jié)果也表明了本文算法在面對不同形狀的數(shù)據(jù)集聚類時，具有更好的自適應(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ù)據(jù)集的對數(shù)自然特征值和對數(shù)自然鄰居，對數(shù)自然特征值也體現(xiàn)了數(shù)據(jù)的分布規(guī)律。當(dāng)達(dá)到對數(shù)自然穩(wěn)定狀態(tài)時，每個數(shù)據(jù)點的對數(shù)自然鄰居數(shù)不一定相同，不同的鄰居數(shù)更進(jìn)一步體現(xiàn)了數(shù)據(jù)集的數(shù)據(jù)分布規(guī)律。NaN-BP算法使用自然特征值能夠根據(jù)不同形狀的數(shù)據(jù)集確定更理想的初始邊界點，使得在邊界剝離的逐次迭代中邊界點與核心點的關(guān)聯(lián)更加合理，最后自下而上的聚類便能產(chǎn)生很好的效果。

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

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