一種改進的基于核密度估計的DPC算法

仇上正 張曦煌

(江南大學物聯(lián)網(wǎng)工程學院 江蘇 無錫 214000)

一種改進的基于核密度估計的DPC算法

仇上正 張曦煌

(江南大學物聯(lián)網(wǎng)工程學院 江蘇 無錫 214000)

快速搜索和找到密度峰DPC(clustering by fast search and find of density peaks)的聚類是一種新穎的算法，它通過找到密度峰來有效地發(fā)現(xiàn)聚類的中心。 DPC算法的精度取決于對給定數(shù)據(jù)集的密度的精確估計以及對截止距離dc(cutoff distance)的選擇。dc主要是用于計算每個數(shù)據(jù)點的密度和識別集群中的邊界點，而DPC算法中dc的估計值卻主要取決于主觀經(jīng)驗值。提出一種基于核密度估計的DPC方法(KDE-DPC)來確定最合適的dc值。該方法通過引用一種新的Solve-the-Equation方法進行窗寬優(yōu)化，根據(jù)不同數(shù)據(jù)集的概率分布，計算出最適合的dc。標準聚類基準數(shù)據(jù)集的實驗結(jié)果證實了所提出的方法優(yōu)越于DPC算法以及經(jīng)典的K-means算法、DBSCAN算法和AP算法。

概率密度估計 核密度估計 類簇中心 聚類

0 引 言

聚類在知識發(fā)現(xiàn)和數(shù)據(jù)挖掘的領(lǐng)域中起著重要作用。聚類算法試圖將大量數(shù)據(jù)分配成不同的不相交的類別，其中更相似的數(shù)據(jù)點被分配到同一群集中，而不相似的數(shù)據(jù)點被分組到不同的群集中[1]。聚類分析是一種無監(jiān)督的機器學習方法，在數(shù)據(jù)挖掘中，有著很重要的應用，在目前是重要的研究方向之一[2]。人們借助聚類分析，不僅可以從大量數(shù)據(jù)中發(fā)現(xiàn)所需的知識與信息，還可以降低工作量，提升工作效率。

目前，世界上存在的聚類算法有層次聚類方法、分層聚類方法、基于密度的聚類方法和基于網(wǎng)格的聚類方法，以及集成式聚類算法。在基于劃分的算法中，K-means算法是目前運用最廣泛的算法之一[3]。然而，嚴重依賴于初始聚類中心使得K-means算法的聚類結(jié)果難以滿足目前人們的需求。

首先K-means算法很難發(fā)現(xiàn)非凸形狀的簇，對噪聲點和離群點敏感，而且嚴重依賴初始設(shè)定的K值。目前，K-means算法存在很大缺陷，文獻[4-6]提出了GKM(Global K-means)算法等一系列改進的方法，來優(yōu)化K-means算法。

2014年6月，由Alex和Laio在《Science》上發(fā)表了一種自動確定類簇數(shù)量和類簇中心的新型快速聚類算法，簡稱 DPC[7]。DPC算法存在兩個優(yōu)點：能快速發(fā)現(xiàn)任意形狀數(shù)據(jù)集的密度峰值點 (即類簇中心)，并且能夠高效進行樣本點分配，還可以快速進行離群點剔除工作。因此，DPC算法適用于大規(guī)模數(shù)據(jù)的聚類分析。然而，該算法存在一個重大的問題，在度量樣本密度的時候，該算法根據(jù)主觀經(jīng)驗，原文作者Alex選擇2%作為截斷距離參數(shù)dc的值，對聚類結(jié)果影響較大，可能丟失聚類中心，也可能無法識別所有核心點。

為了彌補該算法的不足，本文提出了一種改進的基于核密度估計的DPC算法(KDE-DPC)。為了減少因人為經(jīng)驗選取截斷距離參數(shù)dc的因素對聚類結(jié)果造成的影響，在計算核密度的時候，我們通過引用一種新的Solve-the-Equation方法[8]來進行窗寬優(yōu)化，然后設(shè)計一套迭代算法得出最優(yōu)窗寬，利用最優(yōu)窗寬從而產(chǎn)生較好的核密度估計結(jié)果。該方法避免了人工輸入經(jīng)驗參數(shù)dc值的弊端，根據(jù)不同數(shù)據(jù)集，自動計算出最優(yōu)窗寬，提高了核密度計算的準確性，同時還提高了樣本分配邊界點的結(jié)果。實驗結(jié)果表明，該算法能夠提高聚類的準確性，能準確識別所有聚類中心，還能更好地分配邊界點。

1 相關(guān)研究

1.1 DPC算法

快速搜索和發(fā)現(xiàn)樣本密度峰值的聚類算法(DPC)能自動發(fā)現(xiàn)數(shù)據(jù)集樣本的類簇中心, 實現(xiàn)任意形狀數(shù)據(jù)集樣本的高效聚類。其基本原理是:理想的類簇中心(density peaks)具備兩個基本特征:1) 與鄰居數(shù)據(jù)點相比，類簇的中心點具有更大的密度;2) 與其他數(shù)據(jù)點相比，類簇中心點之間的距離相對較大。對于一個數(shù)據(jù)集，DPC 算法引入了樣本i的局部密度ρi和樣本i到局部密度比它大且距離它最近的樣本j的距離δi，來找到同時滿足上述條件的類簇中心，DPC算法的有效性很大程度上取決于密度和dc的準確估計。其定義如式(1)和式(2)所示:

(1)

其中:dij為樣本i,j之間的歐氏距離，dc為截斷距離，當x<0時，χ(x)=1，否則χ(x)=0。

δi=minj:ρj>ρi(dij)

(2)

對于局部密度最大的樣本i，其δi=maxdij。

由式(1)可知,文獻[7]引入的樣本局部密度受截斷距離dc影響。DPC算法中dc的選擇基于啟發(fā)式方法。數(shù)據(jù)集中的每個點鄰居的平均數(shù)量應該僅為整個數(shù)據(jù)集的1%～2%。因此，截斷距離dc與用戶關(guān)于數(shù)據(jù)集性質(zhì)的觀察有關(guān)。為了避免截斷距離對樣本局部密度乃至聚類結(jié)果的影響, DPC 算法采用指數(shù)核[13]計算樣本密度：

(3)

根據(jù)聚類心中定義，聚類中心有較大的密度ρi和較大的距離δi。選取28個據(jù)點以遞減的密度順序顯示在圖1中。根據(jù)計算每個數(shù)據(jù)點的值畫出決策圖，如圖2所示。

圖1 數(shù)據(jù)點分布圖

圖2 聚類中心決策圖

從決策圖中可以發(fā)現(xiàn)點1和10具有較大的密度值和距離值，根據(jù)聚類中心定義，可以確定這兩個點位聚類中心。由于點26、27和28是孤立的，它們具有較高的δ和較低的ρ，可以被認為是噪聲或異常值。 因此，使用決策圖，可以容易地識別出期望的聚類中心。 在成功識別聚類中心之后，DPC算法基于它們在單個回合中的δ值，將剩余的數(shù)據(jù)點分配給最近的聚類中心，從而完成聚類。

1.2 核密度估計

核密度估計，是一種用于估計概率密度函數(shù)的非參數(shù)方法[9]，為獨立同分布F的n個樣本點，設(shè)其概率密度函數(shù)為f，核密度估計為公式：

(4)

高斯核密度估計是一種常用的核密度估計方法：

(5)

式(5)的性能在很大程度上取決于窗寬h的選擇。均方積分誤差被用來衡量估計h的最佳標準：

(6)

高斯核密度估計具有一些限制，例如，敏感的參數(shù)h(帶寬)難以選擇、邊界偏置，以及欠平滑或過平滑等缺點。

2 改進的DPC算法

針對上述DPC算法的問題，本文提出一種改進的基于核密度估計的密度峰快速聚類算法(KDE-DPC)。該算法包括各步驟：

(1) 計算出核密度的最佳帶寬h；

(2) 根據(jù)h計算每個點的密度ρ；

(3) 計算出每個點的距離δ；

(4) 畫出決策圖；

(5) 從決策圖中選取聚類中心；

(6) 將點分配給聚類中心；

(7) 檢查邊界點，形成聚類簇。

2.1 最優(yōu)帶寬h的選擇

由文獻[8]給出的核指數(shù)密度計算公式和核密度估計函數(shù)公式可以發(fā)現(xiàn)，dc相當于核密度估計函數(shù)公式中的窗寬h，我們想要得到最優(yōu)的dc，可以轉(zhuǎn)變?yōu)榈玫阶顑?yōu)的窗寬h。

上面提到評價h優(yōu)劣的標準為MISE，在弱假設(shè)下，其中AMISE為漸進的MISE,而AMISE如下：

(7)

為了使MISE最小，則轉(zhuǎn)化為求極小值問題，如下：

(8)

其中:

通過式(8)得：

(9)

對于高斯核函數(shù)，R(K)=1，m2(K)=1。對于R(f″),我們引入一種新的方法Solve-the-Equation方法對R(f″)求解得：

(10)

由于式(10)中，在最優(yōu)化hopt的表達式中含有未知量h，因此，我們設(shè)計一套迭代算法來計算最優(yōu)的窗口值。令hopt=F(h),則計算最優(yōu)窗口寬度值如下：

Step1h1=F(h0),h0=s,對于s的初始值我們對在后面闡述。初始化參數(shù)k，其中k為一極小值。

Step2當|h1-h0|>k時，循環(huán)執(zhí)行下面步驟：

(1) 將h1的值賦給h0，即執(zhí)行h0=h1；

(2) 對于新的h0值，利用表達式h1=F(h0)計算出新的h1值；

Step3返回窗口寬度最優(yōu)值hopt=h1。

對于s的確定，我們采用如下標準：

其中:n為樣本觀察值的個數(shù)，σ為樣本觀察值的標準差。

2.2 算法性能分析

本文改進的算法復雜度主要由下面幾個方面決定：1) 計算樣本之間的距離，此過程的時間復雜度為O(n2)；2) 計算hopt，時間復雜度為O(n2)；3) 迭代求出最優(yōu)h，時間復雜度為O(n)。

因此經(jīng)過對比分析，相比于原算法，改進后的算法復雜度一樣。

3 實驗結(jié)果與分析

3.1 人工數(shù)據(jù)集實驗結(jié)果分析

為了評估我們提出的KDE-DPC方法的效果，我們將提出方法的實驗結(jié)果與DPC算法的結(jié)果作對比。所用的人工數(shù)據(jù)集如表1所示。DPC 算法是文獻[7]作者提供的源代碼。本文KDE-DPC算法采用 Matlab R2010a實現(xiàn)。本實驗的所有實驗運行環(huán)境均為Win 8 64 bit操作系統(tǒng),Matlab R2010a軟件,12 GB內(nèi)存,Intel(R) Core(TM)2 Quad CPU I5-5200U@2.7 GHz。

表1 數(shù)據(jù)集的基本信息

為了能更全面地展現(xiàn)本算法的效果，我們采用對比實驗來分析算法。圖3展現(xiàn)的是提出的KDE-DPC算法與DPC算法分別在D31數(shù)據(jù)集和R15數(shù)據(jù)集上做縱向?qū)Ρ葘嶒灥慕Y(jié)果。

圖3 DPC算法與KDE-DPC算法對R15數(shù)據(jù)集和D31數(shù)據(jù)集的聚類結(jié)果

從圖3中，我們可以發(fā)現(xiàn)提出的KDE-DPC算法能夠更好地處理噪聲點，準確分配樣本點。

表2展示了本文提出的KDE-DPC算法與DPC算法在識別聚類點和錯誤分類點方面的詳細比較。從表中可以發(fā)現(xiàn)KDE-DPC算法無論數(shù)據(jù)集的性質(zhì)如何，都能準確識別聚類群的核心點。

表2 對比DPC和KDE-DPC檢測核心點和錯誤點的分類情況

因此，本文提出的KDE-DPC算法是一種能適用于不同數(shù)據(jù)集的有效的聚類通用解決方案。

3.2 真實數(shù)據(jù)集實驗結(jié)果分析

本文還采用真實的UCI數(shù)據(jù)集來驗證改進的KDE-DPC算法的聚類性能，并采用Acc、AMI和ARI三個聚類指標來做綜合評價。表3給出了本文KDE-DPC算法，以及對比算法DPC、AP、K-means、DBSCAN算法在真實UCI數(shù)據(jù)集上的聚類結(jié)果。

表3 DPC、AP、K-means、DBSCAN算法在真實UCI數(shù)據(jù)集上的實驗結(jié)果

從表3中可以明顯看出我們提出的KDE-DPC算法在Acc、AMI和ARI三項指標明顯優(yōu)越于DPC、AP、DBSCAN，以及K-means等經(jīng)典算法。

總之，本文提出的KDE-DPC算法在復雜度上與DPC算法相同，但在精度上明顯優(yōu)越于DPC算法以及其他經(jīng)典算法。

4 結(jié) 語

DPC算法思想新穎，而且簡單快速的特點。算法效率上明顯優(yōu)越于其他經(jīng)典算法，但是在參數(shù)dc的選擇上有很大的缺點。本文通過基于核密度估計優(yōu)化的思想改進了該算法，達到了不錯的效果。并且，通過對人工數(shù)據(jù)以及真實數(shù)據(jù)的測試，驗證了本算法的優(yōu)點。

在決策圖中，需要人工肉眼來選擇聚類中心，在很多情況下，聚類中心難以分辨，容易造成錯誤的聚類中心或者聚類中心的缺失。未來，我們將進一步優(yōu)化該算法，能夠?qū)崿F(xiàn)自動準確選取聚類中心的功能。

[1] Han J W,Kamber M.Data Mining Concepts and Techniques[M].2nd ed.New York:Elsevier Inc,2006:383-424.

[2] Lu J,Liong V E,Zhou X,et al.Learning Compact Binary Face Descriptor for Face Recognition[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2015,37(10):2041-2056.

[3] Jain A K.Data Clustering:50 Years Beyond K-means[M]//Machine Learning and Knowledge Discovery in Databases.Springer Berlin Heidelberg,2008:651-666.

[4] Likas A,Vlassis N,Verbeek J J.The global k-means clustering algorithm[J].Pattern Recognition,2003,36(2):451-461.

[5] Xie J,Jiang S,Xie W,et al.An Efficient Global K-means Clustering Algorithm[J].Journal of Computers,2011,6(2):271-279.

[6] Ester M,Kriegel H P,Sander J,et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of ACM SIGKDD’96,Portland,1996:226-231.

[7] Rodriguez A,Laio A.Machine learning.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.

[8] Alexandre L A.A Solve-the-Equation Approach for Unidimensional Data Kernel Bandwidth Selection[OL].2008.http://www.di.ubi.pt/～lfbaa/entnetsPubs/bandwidth.pdf.

[9] Alan Julian Izenman.Review Papers:Recent Developments in Nonparametric Density Estimation[J].Journal of the American Statistical Association,1991,86(413):205-224.

[10] Gionis A,Mannila H,Tsaparas P.Clustering Aggregation[J].Acm Transactions on Knowledge Discovery from Data,2007,1(1):4.

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

[12] Veenman C J,Reinders M J T,Backer E.A maximum variance cluster algorithm[J].Pattern Analysis & Machine Intelligence IEEE Transactions on,2002,24(9):1273-1280.

[13] Fu L,Medico E.FLAME,a novel fuzzy clustering method for the analysis of DNA microarray data[J].Bmc Bioinformatics,2007,8(1):3.

[14] Pedregosa F,Gramfort A,Michel V,et al.Scikit-learn:Machine Learning in Python[J].Journal of Machine Learning Research,2011,12(10):2825-2830.

ANIMPROVEDDPCALGORITHMBASEDONKERNELDENSITYESTIMATION

Qiu Shangzheng Zhang Xihuang

(SchoolofInternetofThingsEngineering,JiangnanUniversity,Wuxi214000,Jiangsu,China)

Clustering by fast search and find of density peaks (DPC) is a novel algorithm that efficiently discovers the centers of clusters by finding the density peaks. The accuracy of DPC depends on the accurate estimation of densities for a given dataset and also on the selection of the cutoff distance (dc). Mainly, dc is used to calculate the density of each data point and to identify the border points in the clusters. However, the estimation of dc largely depends on subjective experience. This paper presents a method based on kernel density estimation (KDE-DPC) to determine the most suitable dc. This method performs window width optimization by referencing a new Solve-the-Equation method. According to the probability distributions of the different data sets, the optimal dc is obtained. The experimental results of standard clustering benchmark data sets confirm that the proposed method is superior to DPC algorithm, as well as classic K-means algorithm, DBSCAN algorithm and AP algorithm.

Probability density estimation Kernel density estimation Cluster center Clustering

2016-12-22。江蘇省產(chǎn)學研合作項目(BY2015019-30)。仇上正，碩士生，主研領(lǐng)域：計算機應用技術(shù)。張曦煌，教授。

TP391

A

10.3969/j.issn.1000-386x.2017.12.053