一種去除聚類數量和鄰域參數設置的自適應聚類算法 *

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

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

1 引言

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

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

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

本文的主要貢獻如下：

(1)在自然鄰居的概念中，根據數據集的數據分布特點創新性地提出了對數自然穩定狀態和對數自然特征值的概念和規范定義，并且給出了特性分析，給自然鄰居思想補充了新的理論概念。

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

(3)結合對數自然穩定狀態等概念提出了無需鄰域參數的邊界剝離聚類算法NaN-BP。該算法消除了鄰域參數固定選擇的弊端，使得改進后的算法能夠對不同形狀數據集進行自適應聚類，大幅度提高了算法的自適應性。

(4)NaN-BP算法能夠自適應地對不同密度不同分布的數據集進行聚類分析，并且通過實驗結果驗證了其自適應性和聚類結果的準確性。

2 相關工作

2.1 自然鄰居

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

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

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

2.2 聚類算法

聚類是將數據點分類為組或簇的任務，并通過簇的概念直觀展示簇間數據的差異性和簇內數據的相似性。隨著數據分析的關注度逐漸提高，越來越多的聚類算法也被提出。其中基于劃分的聚類算法的核心思想是：按照全局優化的標準把數據集劃分為若干類。由于基于劃分的聚類算法具有很好的理論研究基礎且對凸形數據集的聚類效果非常理想，是早期非常經典的聚類思路[11]。但是，由于基于劃分的聚類算法自身的全局優化函數的局限性，存在不適用具有流形和凹形數據集等許多問題。基于密度的聚類算法理論上能夠適用于任何形狀的數據集，但是基于密度的聚類算法對參數比較敏感，不適用于簇之間密度較大或具有復雜流形的數據集[12]。基于層次的聚類算法核心思想是通過某種相似性測度計算節點之間的相似性，并按相似度由高到低排序，逐步重新連接各個節點[13]。層次聚類的優點是距離和規則的相似度容易定義，限制少，不需要預先設定聚類數，但層次聚類復雜度高，奇異值也能產生很大影響。譜聚類算法包含嚴密的數學邏輯，通過圖分割的方法對數據集進行劃分，理論上能夠解決流形數據問題[14]，然而譜聚類算法很難得到真實的最優解，且算法復雜度較高。

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

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

然而邊界剝離聚類算法在不同形狀數據集上選取的初始邊界點極其依賴鄰域參數k的選擇，從而使得在邊界點迭代剝離的過程中從邊界點到核心點的過程存在產生偏差的可能，進而影響聚類的結果，甚至在部分數據集中出現極為不合理的數據簇劃分。基于上述問題，本文提出了一種新的將自然鄰居與邊界剝離聚類算法相結合的算法——NaN-BP。該算法既能夠保留原來邊界剝離聚類的優勢，又彌補了邊界剝離聚類算法中始終存在鄰域參數的缺陷，在不同形狀的數據集上都無需設置鄰域參數，并自適應得到符合數據分布特征的聚類結果。

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

3.1 自然鄰居思想

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

定義1(自然鄰居) 當數據集處在自然穩定狀態時，互為鄰居的點即互為自然鄰居。即對于任意xi,xj，都有：

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

(xj∈KNNλ(xi))

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

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

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

定義3(自然特征值) 當數據集X處于自然穩定狀態時，自然鄰居特征值λ即為當前的KNN鄰域大小r。在整個搜索過程中，自然特征值是實際運行過程的最大循環次數，反映了數據集的分布規律。

3.2 邊界剝離聚類基本原理

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

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

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

X(t+1)=X(t)

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

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

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

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

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

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

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

xi∈NOS?KNNλ(xi)=?

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

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

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

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

定義6(對數自然特征值) 當數據集X處于對數自然穩定狀態時，針對對數自然穩定狀態，本文提出了對數自然特征值，其形式化定義如下：

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

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

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

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

定義7(對數自然鄰居) 當數據集處在對數自然穩定狀態時，互為鄰居的點即互為對數自然鄰居。即對于任意xi,xj都有：

xj∈NaN(xi)?

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

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

算法1自然鄰居搜索算法

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

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

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

Initialization:

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

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

ξ=ln(n);

//創建一棵KD-樹

KD-tree=creatKDTree(X);

While(Flag= 0)

//利用KD-樹搜索數據xi的第r個鄰居yr

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

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

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

計算Rnum(i)=0的元素個數Rzero;

IFRzero不變

T=T+1;

EndIF

IF(T<ξ)

r=r+1;

Else

Flag= 1;

EndIF

EndWhile

λ=r;

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

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

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

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

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

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

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

Output:Cluster indicesC。

r←Algorithm 1;

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

X1←X;

Forpeeling iteration 1 ≤t≤Tdo

Foreach pointxi∈Xtdo

EndFor

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

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

EndFor

EndFor

//根據核心點的關聯完成聚類，ρ的ρi組成的集合

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

4 實驗

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

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

4.1 有監督數據集實驗

為了驗證本文NaN-BP算法的優越性，選取了BP聚類算法中使用過的人工數據集進行對比實驗。實驗選取的4個數據集均帶有真實標簽，評價指標為ARI和AMI。

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

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

AMI是基于預測簇向量與真實簇向量的互信息分數來衡量其相似度的，AMI越大相似度越高，定義為:

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

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

Figure 2 Experimental results comparison with BP clustering algorithm on flame,R15,Compound and D31 data sets圖2 與BP聚類算法在flame、R15、Compound和D31數據集上的實驗結果比較

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

Table 1 Performance comparison on flame,R15 data sets

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

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

4.2 無監督數據集實驗

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

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

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

實驗表明，在具有大量離群點的無監督數據集上，在聚類數量和聚類質量等多個方面，NaN-BP算法的聚類效果都要遠優于BP聚類算法的。

Figure 4 Comparison of embedding results between BP clustering algorithm and NaN-BP algorithm on three data sets圖4 BP聚類算法和NaN-BP算法在3個數據集上的聚類結果比較

4.3 大數據集上的實驗

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

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

4.4 算法性能和運行細節

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

2.30 GHz Intel Core i5的Windows 10系統上實現的，在運行時間上，因為使用自然鄰居的改進，整體的運算時間要比BP聚類算法稍長，但相對最后比較理想的效果來說，運行時間的增加完全可以忽略。

4.5 實驗小結

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

5 結束語

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

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

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