基于K近鄰的模糊密度峰值聚類算法研究

支 元，李 忠

?

基于K近鄰的模糊密度峰值聚類算法研究

支 元，李 忠

（江蘇聯合職業技術學院常州劉國鈞分院，江蘇常州 213000）

基于密度的聚類算法（Density Peak Clustering，DPC）廣泛使用在處理非球形數據集的聚類問題，算法使用較少的參數就能夠實現數據集的處理。但該算法存在這樣一些的不足：首先，全局變量的設定沒有考慮數據的局部結構，特別是當不同類別的局部密度差別很大的情況下，容易忽略一些密度較小的類別，聚類效果不理想。其次，DPC提出了一種通過決策圖來人工選取聚類中心點的方法，這也是DPC算法在人工智能數據分析的一個重大缺陷。為此，本文提出了基于K近鄰的模糊密度峰值聚類算法，算法針對這兩方面的不足進行了改進。最后本文使用人工數據集和UCI數據集進行了實驗，實驗結果表明本文所提出的算法，在不通過人工選取聚類中心的情況下，能夠正確地找出類別個數，并且保持著較高的聚類精確度，驗證了算法的有效性。

數據挖掘，聚類算法，密度峰值，K近鄰

0 引言

聚類作為一種無監督的學習方法，被廣泛應用到數據挖掘，模式識別，機器學習，圖像處理等領域。其主要目的是將數據集中的樣本劃分為若干個通常是不相交的子集，每個子集代表一個類別，同一類別的數據點之間具有較高的相似性，不同類的的數據點之間相似性較低。目前，很多不同形式的聚類算法被提出，根據其使用方法的不同，聚類算法可以劃分為如下幾類：劃分聚類算法[1-2]、層次聚類算法[3]、基于密度的聚類算法[4]、基于網格的聚類算法[5]以及基于模型的聚類算法[6]。每種聚類算法都其固有的優缺點和適用的數據集。

2014年Rodriguez A，Laio A在Science雜志上提出了一種新的聚類算法[7]，算法的核心思想在與對聚類中心的刻畫上。作者認為每個類別的聚類中心應該具有兩個特點：聚類中心本身的密度大，且被密度低的數據點包圍；聚類中心與其他密度更大的數據點之間的距離相對更大。在這篇文章中我們稱之為DPC（Density Peak Clustering）。在幾個測試實驗中，DPC可以較好的發現聚類中心，并且能夠將其余點分配到其對應的類中。但是，DPC同樣有一些不足。首先，對于截斷距離選擇的恰當與否直接影響到聚類的準確性，而的設置容易忽略數據的局部結構，對于類別密度差別比較大的聚類問題，容易忽略低密度的類別，效果不理想。其次，對于聚類中心點的選擇上，DPC算法通過決策圖來人為的選擇聚類中心點，而人工選擇聚類中心也是DPC算法在智能數據分析上的一個缺點。

為了克服這兩方面的不足，我們提出了基于K近鄰的模糊密度峰值聚類算法（KNN-FDPC）算法。首先，將高斯核函數與K近鄰算法[8]相結合，對密度進行計算。其次，我們提出一種自適應的方法，先通過限定公式，篩選出滿足條件的數據點，將其定義為局部聚類中心。在獲得局部聚類中心后，我們將剩余點進行歸類，然后再通過合并算法，對類別進行合并，最終得到聚類結果。整個算法過程省去人工選擇聚類中心的過程，大大降低了算法的運行時間，并且在人工數據集和UCI數據集的實驗結果表明，所提KNN-FDPC算法同樣擁有較高的聚類精確度，從而驗證了算法是有效可行的。

1 密度峰值聚類算法

不同于其它的密度聚類算法，Rodriguez A，Laio A提出的DPC算法[7]為聚類算法提供了一種新思路，這個算法將高于附近數據點的局部密度，且與更高局部密度的數據點距離相對較遠的數據點定義為聚類中心。算法依據這兩個特點，對數據集中的每一個數據點為其定義局部密度和所有局部密度大于的數據點中，與距離最小的數據點與之間距離。

（2）

（3）

DPC算法的具體流程如下：

方法：

1：計算距離矩陣；

4：生成決策圖，人工選擇聚類中心；

5：對非聚類中心的數據點進行歸類；

6：輸出每個樣本的類別標簽y；

2 K近鄰算法

K近鄰算法[8]是一種常用的監督學習方法，最早被用在分類算法中，KNN算法通過待分類樣本點距離的多數投票結果進行分類。這種方法已經在分類、聚類和其它的領域展現出很強的技巧性，該算法的主要目的是：找出每個數據點距離最近的K個數據點。

假設我們從一個m維空間中獲得一個由個數據點組成的數據集。我們使用歐式距離來計算點與點之間的距離，要想得到距離點最近的K個點，我們需要計算除數據點之外的所有數據點到的距離，選取距離最近的K個數據點，作為的K近鄰數據點。

3 基于K近鄰的模糊密度峰值聚類算法

3.1 局部密度計算

針對DPC算法中的一些不足之處，我們提出了相應的解決辦法。首先，在DPC算法中，對于截斷距離選擇的恰當與否直接影響到聚類的準確性，并且的設置具有全局性，數據的局部結構容易被忽略，對于局部差別比較大的聚類問題，效果不理想。在我們的工作中，我們使用核函數的方法來定義局部密度，并將KNN的思想運用到局部密度計算中，這在一定程度上體現了數據集的局部結構。

3.2 局部聚類中心獲取與類別合并

為了克服DPC算法通過決策圖人工選擇聚類中心的局限性，本文中我們提出了一種方法，使得在沒有人為干涉的情況下能夠正確地獲得聚類結果。我們先通過限定公式，獲得滿足條件的數據點，并將數據點定義為局部聚類中心，然后將剩余數據點進行分配得到局部聚類結束，最后通過提出的合并算法，對滿足合并條件的類進行合并，得到全局聚類結果。

根據DPC提出的聚類中心兩個特點：擁有高于附近點的局部密度，且與更高局部密度的點距離相對較遠。我們設置限定公式，對聚類中心進行初步的選取。通過公式（5）（6），分別計算所有數據點局部密度的平均值和距離的標準方差。如果一個數據點的距離滿足且局部密度滿足則認為數據點為局部聚類中心。

（6）

通過約束條件獲得的局部聚類中心同時擁有相對較大的局部密度和距離。在得到局部聚類中心后，我們使用DPC算法提出的歸類方法，對其余點進行歸類：對于所有數據點按局部密度大小降序排列，從局部密度大的數據點開始歸類，如果一個數據點不是局部聚類中心，則該數據點的類別與比其局部密度高的所有數據點中距離最近的數據點類別相同。我們將對剩余點歸類后的聚類結果，稱為局部聚類。為了將滿足合并條件的類進行合并，從而得到最終的全局聚類，我們在不增加其它變量的情況下提出了一個合并算法。

當一個類別中存在一個數據點，這個數據點K近鄰的點中存在不屬于該類別的點，則認為這樣的數據點為邊界點。

搜索每一個類別的邊界點的K個近鄰點，計算邊界點與不同類點的平均局部密度，取所有平均局部密度的最大值，作為該類別到另外一點所在類別的邊界密度。我們用表示類別A到類別B的邊界密度，如果兩個類相互間的邊界密度與相同，則將兩個類合并為一個類。

合并的過程我們采用一種策略：對于滿足合并條件的類別，由密度小的局部聚類中心所在類別向密度大的局部聚類中心所在類別合并，合并的過程中，不斷更新類與類的邊界密度，通過這種合并策略，最終的合并結果會得到準確地得到全局聚類結果。

KNN-FDPC算法的具體流程如下：

輸入：數據集X，k近鄰參數K

1：計算距離矩陣；

3：自動獲得滿足限定公式的聚類中心；

4：將其余點分配到相應類別中；

5：計算類與類邊界密度，并將局部聚類中心點按局部密度從小到大排序；

6：選取局部密度最小的局部中心所在類別，按局部密度從小到大的順序，依次與其它類別進行邊界密度比較：若滿足合并條件，將局部密度小的局部聚類中心所在的類合并到密度大的局部聚類中心所在的類中。將局部密度最小的局部聚類中心刪除。跳到步驟5；否則，結束算法；輸出：每個樣本的類別標簽y。

4 實驗結果與分析

本文使用聚類精確率[9]：

來評估算法對人工數據集和UCI數據集的聚類效果。

4.1 人工數據集實驗

4.1.1 人工數據集

使用二維人工數據集來測試我們實驗的性能，二維人工數據集的可視化，可以直觀的看出我們所提算法的性能。在人工數據集實驗部分，我們使用了4個常用的人工數據集，分別是：Spiral[10]、Flame[11]、Aggregation[12]、S1[13]。這4個數據集是測試聚類算法性能的常用數據集。數據集的大小，屬性的個數，類的個數，如表1所示。

表1 人工數據集描述

Tab.1 Description of synthetic data set

4.1.2 人工數據集聚類結果及評價

首先使用Flame數據集，來簡單、明確地說明整個KNN-FDPC算法的聚類過程，其次使用KNN- FDPC，DPC[7]，AP[14]，DBSCAN[4]，K-means[1]算法對上述4個數據集進行實驗對比，其中由于K- means算法的精確度的高低對初始中心點的選取有關，因此我們選取20次運行結果的平均值作為最終的聚類精確度，對于K-means，DPC，AP與DBSCAN算法，我們都使用作者提供的原始代碼進行實驗，在參數的選擇方面，我們都使用最優參數，以獲得最優的聚類精確度。5種算法的對不同數據集的聚類精確度對比如表5所示，S1數據集聚類結果如圖3所示。

我們先利用Flame數據集來詳細說明我們所提算法的整個聚類過程。Flame數據集如圖1(a)所示，我們設置參數K=9，生成的決策圖如圖1(b)所示。從數據集中第一個數據點開始，尋找滿足限制條件的數據點，并依次定義為：類別1，類別2，類別3……。所有數據點中，滿足局部聚類中心限制條件的數據點個數為4，如圖1(c)所示，不同的顏色對應不同的類別。將這4個點定義為局部聚類中心，4個局部聚類中心的局部密度從小到大排序依次為：類別2，類別3，類別1，類別4。在找到聚類中心后，我們將剩余數據點進行歸類，局部聚類結果如圖1(d)所示。

由合并算法，我們先計算出4個類相互間的邊界密度，如表2所示。其中第a行，第b個數據代表從類別a到類別b的邊界密度，用表示。我們先選取類別2依次與類別3，類別1，類別4進行邊界密度的比較，如表2所示，類別2與類別3滿足合并條件=，所以我們將類別為2的所有數據點合并到類別3中，如圖1(e)所示，然后刪除局部聚類中心2，并更新表2為表3。合并后剩余三個局部聚類中心，如圖1(f)所示。3個局部聚類中心的局部密度從小到大排序依次為：類別3，類別1，類別4。同樣的方法，我們先選取類別3依次與類別1，類別4進行邊界密度的比較，如表3所示，類別3與類別1滿足合并條件=，所以我們將類別為3的所有數據點合并到類別1中去，如圖1(g)所示，然后刪除局部聚類中心3，并更新表3為表4。合并后剩余三個聚類中心如圖1(h)所示。2個局部聚類中心的局部密度從小到大排序依次為：類別1，類別4。比較類別1與類別4的邊界密度，因為類別，所以終止合并過程。所以最終獲得的全局聚類結果如圖1(g)所示。

圖1 Flame數據集聚類過程。(a) Flame數據集。(b) KNN-FDPC算法生成決策圖。(c) KNN-FDPC算法獲得的局部聚類中心。(d)局部聚類結果(e)類別2合并到類別3后的聚類結果(f)類別2合并到類別3后的決策圖及局部聚類中心。(g)類別3合并到類別1后的聚類結果(h)類別3合并到類別1后的決策圖及局部聚類中心。

表2 4個類別相互間的邊界密度

Tab.2 Mutual boundary density of four categories

表3 2合并到類別3后的邊界密度

Tab.3 Mutual boundary density of three categories

表4 3和并到類別1后的邊界密度

Tab.4 Mutual boundary density of two categories

Aggregation數據集包含了7個不易察覺的類，圖2(a)中彩色點表示滿足約束條件的13個局部聚類中心。圖2(b)表示剩余數據點歸類后的，未合并的KNN-FDPC算法的局部聚類結果。圖2(c)表示KNN-FDPC算法最終的全局聚類結果。圖2(d)表示合并后剩余的局部聚類中心，也是最終的聚類中心。合并后局部聚類中心從13個減少到7個，恰好對應Aggregation數據集中的7個類。結果顯示，KNN-FDPC數據集準確的將Aggregation數據集分為了7個類。

圖2 Aggregation數據集聚類合并過程。(a) KNN-FDPC算法獲得的局部聚類中心。(b)未合并的KNN-FDPC算法聚類結果。(c) KNN-FDPC算法聚類結果。(d)合并后剩余的局部聚類中心。

表5 人工數據集實驗結果

Tab.5 Experimental results of synthetic data set

圖3 S1數據集聚類結果

分析實驗結果，與K-means算法不同，KNN- FDPC，DPC和DBSCAN算法對各種復雜形狀的數據集有著較好的聚類效果，而K-means算法只能對球狀分布的數據進行聚類所以聚類的精確度都相對較低。與DPC算法相比較，雖然KNN-FDPC是一種自適應獲取局部聚類中心，并通過合并算法將局部聚類合并為全局聚類，省去了手動選取聚類中心的步驟，但是KNN-FDPC算法同樣能夠準確的確定聚類中心，確保聚類結果擁有相仿的精確度。

4.2 UCI數據集實驗

4.2.1 UCI數據集

為了驗證算法在真實世界數據集的有效性，我們在UCI公共數據集上取出3個數據集進行了實驗。

從UCI中取出的數據集分別為Iris、Seeds和Wine，其中數據集Iris的屬性總數為4，有3個類別，各類別的樣本數為50:50:50；數據集Seeds屬性總數為7，有3個類別，各類別的樣本數為70:70: 70；數據集Wine屬性總數為13個，有三個類別，各類別的樣本數為59:70:47。

表6 UCI數據集描述

在實驗之前，我們使用min-max規則化，對實驗數據進行一次預處理，公式如下：

4.2.2 UCI數據集聚類結果及評價

如表7所示，KNN-FDPC算法可以自動獲得了每個數據集的聚類中心，而不需要手動地通過決策圖來選擇聚類中心。這是KNN-FDPC算法的最明顯的優勢。在精確率方面，KNN-FDPC算法相比較DPC算法，有相似或更好的精確率，說明KNN-FDP算法，在省去人工選擇聚類中心的步驟的同時，同樣可以保持著較高的精確率。

表7 UCI數據集實驗結果

Tab.7 Experimental results of UCI data set

5 總結與展望

本文設計了一種基于K近鄰的模糊密度峰值聚類算法。算法將高斯核函數與K近鄰算法相結合，對局部密度進行計算，可以有效的克服截取距離對密度影響的問題。其次，采用自適應的方法，對聚類中心進行初步選取，獲得局部聚類中心，并將剩余非局部聚類中心數據點歸類后，使用提出的合并算法對類別進行合并，獲得準確的聚類結果。相較于DPC算法，所提算法在不添加任何參數的情況下，能夠自動地發現聚類中心，并且很好的解決了由于截取距離設置的全局性，使得數據的局部結構被忽略的問題。KNN-FDPC算法在幾個人工數據集和UCI數據集上進行了實驗，實驗過程中KNN- FDPC算法準確的尋找到了聚類中心，并取得了很好的聚類精確度。但是，本文的研究工作還有待進一步深入和發展，比如如何對高維數據進行更穩定的合并。

[1] 基于機器視覺的動態多點手勢識別方法[J]. 李文生, 解梅, 鄧春健. 計算機工程與設計. 2012(05).

[2] 賈俊芳, 王秀義, 鄭建新. 基于模糊集的興趣發現新方法[J]. 軟件, 2016, 37(3): 04-08.

[3] LI Yugang. Research on The Generation of Current in A Test Basin for Deepwater Engineering[J]. The Journal of New Industrialization, 2014, 4(8): 9-14.

[4] 孟晨宇, 史淵, 王佳偉, 等. Windows內核級防護系統[J]. 軟件, 2016, 37(3): 16-20

[5] 基于向量內積不等式的分布式k均值聚類算法[J]. 倪巍偉, 陸介平, 孫志揮. 計算機研究與發展. 2005(09).

[6] 基于MapReduce的分布式近鄰傳播聚類算法[J]. 魯偉明, 杜晨陽, 魏寶剛, 沈春輝, 葉振超. 計算機研究與發展. 2012(08).

[7] ZHANG Chong, WANG Yankai. Orbit and Attitude Coupled Collaborative Control for Spacecraft Formation[J]. The Journal of New Industrialization, 2014, 4(8): 30-36.

[8] 基于K-means聚類的數字半色調算法[J]. 何自芬, 詹肇麟, 張印輝. 計算機應用研究. 2013(01).

[9] Ding S F, Jia H J, Shi Z Z. Spectral clustering algorithm based on adaptive Nystr?m sampling for big data analysis[J]. J Softw, 2014, 25(9): 2037-2049.

[10] Chang H, Yeung D Y. Robust path-based spectral clustering[J]. Pattern Recognition, 2008, 41(1): 191-203.

[11] 鄰域形態空間與檢測算法[J]. 張鳳斌, 席亮, 王大偉, 岳新. 控制與決策. 2011(10).

[12] WU Jin, SHANG Xiao, ZHANG Jinhuan. Design of GSM module in Target positioning monitor[J]. The Journal of New Industrialization, 2014, 4(8): 37-43.

[13] 夏新凱, 陳冬火. 基于KeY 的程序分析和驗證[J]. 軟件, 2016, 37(3): 74-78

[14] Frey B J, Dueck D. Clustering by passing messages between data points[J]. science, 2007, 315(5814): 972-976.

Fuzzy Density Peaks Clustering Algorithm Based on K-nearest Neighbors

ZHI Yuan, LI Zhong

(Jiangsu Union Technical Institute Changzhou Liu Guojun Branch, Changzhou 213000, China)

A novel clustering algorithm based on density (DPC) has been proposed recently, this algorithm can deal with non-spherical cluster and does not require too many parameters. But the algorithm has some defects. First the local structure of data has not been taken into account when it calculates the local density. It does not perform well when clusters have different densities. Secondly, this algorithm utilizes decision graph to manually select cluster centers. Manual selection of cluster centers is a big limitation of DPC in intelligent data analysis. In this paper, we propose an improved method. It has been improved for the deficiencies in these two aspects. We use synthetic data set and UCI data set to make the experiments. Experimental results show that our algorithms can correctly identify the number of categories without manually selecting cluster center and maintain a high clustering accuracy, which verifies that the proposed algorithm are effective and feasible.

Data mining; Clustering; Density peaks; K nearest neighbor

TP301.6

A

10.3969/j.issn.1003-6970.2017.04.015

2016年度江蘇省教育科學“十三五”重點資助規劃課題（項目編號：B-a/2016/03/06）

支元(1982-)，男，講師，主要研究方向：數據挖掘、智能控制。

支元，江蘇省常州市戚墅堰富民路296號信息(物聯網)工程系。

本文著錄格式：支元，李忠. 基于K近鄰的模糊密度峰值聚類算法研究[J]. 軟件，2017，38（4）：85-90