仇上正 張曦煌

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

一種改進(jìn)的基于核密度估計(jì)的DPC算法

仇上正 張曦煌

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

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

概率密度估計(jì) 核密度估計(jì) 類簇中心 聚類

0 引 言

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

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

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

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

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

1 相關(guān)研究

1.1 DPC算法

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

(1)

其中:dij為樣本i,j之間的歐氏距離，dc為截?cái)嗑嚯x，當(dāng)x<0時(shí)，χ(x)=1，否則χ(x)=0。

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

(2)

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

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

(3)

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

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

圖2 聚類中心決策圖

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

1.2 核密度估計(jì)

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

(4)

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

(5)

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

(6)

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

2 改進(jìn)的DPC算法

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

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

(2) 根據(jù)h計(jì)算每個(gè)點(diǎn)的密度ρ；

(3) 計(jì)算出每個(gè)點(diǎn)的距離δ；

(4) 畫出決策圖；

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

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

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

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

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

上面提到評(píng)價(jià)h優(yōu)劣的標(biāo)準(zhǔn)為MISE，在弱假設(shè)下，其中AMISE為漸進(jìn)的MISE,而AMISE如下：

(7)

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

(8)

其中:

通過式(8)得：

(9)

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

(10)

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

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

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

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

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

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

對(duì)于s的確定，我們采用如下標(biāo)準(zhǔn)：

其中:n為樣本觀察值的個(gè)數(shù)，σ為樣本觀察值的標(biāo)準(zhǔn)差。

2.2 算法性能分析

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

為了評(píng)估我們提出的KDE-DPC方法的效果，我們將提出方法的實(shí)驗(yàn)結(jié)果與DPC算法的結(jié)果作對(duì)比。所用的人工數(shù)據(jù)集如表1所示。DPC 算法是文獻(xiàn)[7]作者提供的源代碼。本文KDE-DPC算法采用 Matlab R2010a實(shí)現(xiàn)。本實(shí)驗(yàn)的所有實(shí)驗(yàn)運(yù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)本算法的效果，我們采用對(duì)比實(shí)驗(yàn)來分析算法。圖3展現(xiàn)的是提出的KDE-DPC算法與DPC算法分別在D31數(shù)據(jù)集和R15數(shù)據(jù)集上做縱向?qū)Ρ葘?shí)驗(yàn)的結(jié)果。

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

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

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

表2 對(duì)比DPC和KDE-DPC檢測核心點(diǎn)和錯(cuò)誤點(diǎn)的分類情況

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

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

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

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

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

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

4 結(jié) 語

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

在決策圖中，需要人工肉眼來選擇聚類中心，在很多情況下，聚類中心難以分辨，容易造成錯(cuò)誤的聚類中心或者聚類中心的缺失。未來，我們將進(jìn)一步優(yōu)化該算法，能夠?qū)崿F(xiàn)自動(dòng)準(zhǔ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)學(xué)研合作項(xiàng)目(BY2015019-30)。仇上正，碩士生，主研領(lǐng)域：計(jì)算機(jī)應(yīng)用技術(shù)。張曦煌，教授。

TP391

A

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