淦文燕，劉沖

(解放軍理工大學(xué) 指揮信息系統(tǒng)學(xué)院，江蘇 南京 210007)

一種改進(jìn)的搜索密度峰值的聚類算法

淦文燕，劉沖

(解放軍理工大學(xué) 指揮信息系統(tǒng)學(xué)院，江蘇 南京 210007)

聚類是大數(shù)據(jù)分析與數(shù)據(jù)挖掘的基礎(chǔ)問(wèn)題?？窃?014年《Science》雜志上的文章《Clustering by fast search and find of density peaks》提出一種快速搜索密度峰值的聚類算法，算法簡(jiǎn)單實(shí)用，但聚類結(jié)果依賴于參數(shù)dc的經(jīng)驗(yàn)選擇。論文提出一種改進(jìn)的搜索密度峰值的聚類算法，引入密度估計(jì)熵自適應(yīng)優(yōu)化算法參數(shù)。對(duì)比實(shí)驗(yàn)結(jié)果表明，改進(jìn)方法不僅可以較好地解決原算法的參數(shù)人為確定的不足，而且具有相對(duì)更好的聚類性能。

數(shù)據(jù)挖掘；聚類算法；核密度估計(jì)；熵

互聯(lián)網(wǎng)時(shí)代，隨著社交網(wǎng)絡(luò)、電子商務(wù)與移動(dòng)通信等技術(shù)的蓬勃發(fā)展，人類社會(huì)進(jìn)入以PB級(jí)數(shù)據(jù)信息為特征的大數(shù)據(jù)時(shí)代。如何從海量復(fù)雜數(shù)據(jù)集中自動(dòng)發(fā)現(xiàn)新知識(shí)、新規(guī)律，實(shí)現(xiàn)從數(shù)據(jù)到知識(shí)到?jīng)Q策的挑戰(zhàn)與跨越[1-2]，成為各行各業(yè)普遍面臨的嚴(yán)峻技術(shù)挑戰(zhàn)。

所謂聚類,就是根據(jù)描述事物的某些屬性, 將事物聚集成若干類，使得類間相似性盡量小，類內(nèi)相似性盡量大[3]。與分類不同，聚類無(wú)須明確的類標(biāo)記，無(wú)須區(qū)分訓(xùn)練集與測(cè)試集，是一種尋求數(shù)據(jù)自然聚簇結(jié)構(gòu)的非監(jiān)督學(xué)習(xí)方法，可以產(chǎn)生問(wèn)題中數(shù)據(jù)的概括性描述，可以自動(dòng)構(gòu)建分類層次結(jié)構(gòu)，具有更好的普適性；同時(shí)，聚類又具有不確定性。對(duì)于給定的數(shù)據(jù)集，聚類結(jié)果不僅依賴于實(shí)際的數(shù)據(jù)分布，而且取決于問(wèn)題的應(yīng)用背景與目標(biāo)，不存在唯一正確的聚類劃分。正由于這種普適性與不確定性，使聚類問(wèn)題比分類問(wèn)題更復(fù)雜、更具挑戰(zhàn)性，被認(rèn)為是大數(shù)據(jù)分析與數(shù)據(jù)挖掘的基礎(chǔ)問(wèn)題，也成為統(tǒng)計(jì)、模式識(shí)別、機(jī)器學(xué)習(xí)、人工智能等諸多學(xué)科領(lǐng)域中一個(gè)非?；钴S且非常重要的研究熱點(diǎn)[3-5]。

2014年《Science》雜志上刊登了一篇題為《Clustering by fast search and find of density peaks》的論文[1]，論文提出一種快速搜索和發(fā)現(xiàn)密度峰值的聚類算法。算法將具有局部極大密度估計(jì)值的樣本點(diǎn)視為聚類中心，通過(guò)快速搜索聚類中心，將每一個(gè)非中心樣本點(diǎn)沿著密度遞增的最近鄰方向迭代劃分給相應(yīng)的聚類中心，實(shí)現(xiàn)數(shù)據(jù)劃分。算法思路新穎，簡(jiǎn)單實(shí)用，具有良好的聚類質(zhì)量，能夠發(fā)現(xiàn)任意形狀、大小和密度的聚類，能夠有效處理噪聲和離群數(shù)據(jù)，對(duì)人臉等高維非結(jié)構(gòu)化數(shù)據(jù)具有良好的適用性。雖然論文的局限性遭到眾多讀者的質(zhì)疑，如聚類結(jié)果嚴(yán)重依賴于密度參數(shù)dc的仔細(xì)選擇，但整體上可以為聚類算法設(shè)計(jì)提供一種新思路。

本文深入探討了快速搜索密度峰值點(diǎn)的聚類算法[1]的局限性，引入基于密度估計(jì)熵最小化的自適應(yīng)參數(shù)優(yōu)化方法彌補(bǔ)其核函數(shù)及其參數(shù)值人為確定的羈絆，提出一種改進(jìn)的搜索密度峰值點(diǎn)的聚類算法。在重現(xiàn)論文算法并獲得與原作者相同實(shí)驗(yàn)結(jié)果的基礎(chǔ)上，用改進(jìn)算法重新聚類。對(duì)比實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法不僅能有效解決原算法的參數(shù)優(yōu)選問(wèn)題，而且具有相對(duì)更好的聚類性能。

1 快速搜索密度峰值的聚類算法

1.1 局部密度估計(jì)與高密度最近鄰距離

?xi∈D,1≤i≤n,局部密度估計(jì)值dc定義為

(1)

(2)

2)高斯核估計(jì)

(3)

3)指數(shù)核估計(jì)

(4)

式中：dij為樣本點(diǎn)xi、xj間的距離，采用滿足三角不等式的距離度量，如歐氏距離；dc>0是預(yù)先指定的密度估計(jì)參數(shù)，相當(dāng)于核函數(shù)的窗寬。

高密度最近鄰距離δi則定義為xi到具有更大密度估計(jì)值的最近鄰樣本點(diǎn)的距離，即

(5)

顯然，具有全局最大密度估計(jì)值的樣本點(diǎn)不存在高密度最近鄰，可簡(jiǎn)單地令其高密度最近鄰距離等于所有樣本點(diǎn)間距離的最大值。

1.2 基于決策圖的聚類劃分

通過(guò)計(jì)算每個(gè)樣本點(diǎn)xi(1≤i≤n)的局部密度估計(jì)值dc和高密度最近鄰距離δi，算法將原始數(shù)據(jù)集D映射到由局部密度估計(jì)ρ和高密度最近鄰距離δ組成的二維特征空間中。直覺上，代表聚類中心的樣本點(diǎn)應(yīng)同時(shí)具有較大的局部密度估計(jì)值ρ和較大的高密度最近鄰距離ρ。由此，通過(guò)特征空間中決策圖的可視化，可以實(shí)現(xiàn)基于中心的聚類劃分。

圖1所示為論文實(shí)驗(yàn)采用的模擬測(cè)試數(shù)據(jù)集及其聚類結(jié)果[1]。測(cè)試數(shù)據(jù)包含4 000個(gè)樣本點(diǎn)，分別取自6個(gè)不同的二維正態(tài)分布，還有一些噪聲數(shù)據(jù)。圖1(a)所示為采用式(2)所示的截?cái)嗪斯烙?jì)且參數(shù)dc取最小2%的距離做截?cái)鄷r(shí)(即dc取值為所有樣本點(diǎn)間距離的最小2%的距離中的最大距離)，測(cè)試數(shù)據(jù)集投影到以局部密度估計(jì)ρ值為橫軸、以高密度最近鄰距離δ為縱軸的二維空間中形成的決策圖[1]；顯然，圖中虛線框選出的5個(gè)樣本點(diǎn)同時(shí)具有較大的局部密度估計(jì)值ρ和高密度最近鄰距離ρ，可以被選為5個(gè)聚類中心，相應(yīng)聚類結(jié)果如圖1(b)所示。4 000個(gè)樣本點(diǎn)被劃分為5個(gè)類和噪聲數(shù)據(jù)，每個(gè)類用與中心樣本點(diǎn)相同的數(shù)字來(lái)標(biāo)記。其中，第五類最大，包含多于1 500個(gè)樣本點(diǎn)，第一類最小，僅有200多個(gè)樣本點(diǎn)。顯然，算法具有良好的聚類質(zhì)量，可以發(fā)現(xiàn)不同形狀、大小和密度的聚類，可以有效處理噪聲數(shù)據(jù)。

但算法中存在一個(gè)重要參數(shù)，即密度參數(shù)dc。論文認(rèn)為，參數(shù)dc的取值雖然會(huì)影響樣本點(diǎn)的局部密度估計(jì)與高密度最近鄰距離，但不會(huì)嚴(yán)重影響最終的聚類結(jié)果，通常選取所有樣本點(diǎn)間距離的最小1%～2%做截?cái)嗉纯?即令dc取值為所有樣本點(diǎn)間距離的最小1%～2%的距離中的最大距離)。但重現(xiàn)論文算法及其實(shí)驗(yàn)結(jié)果時(shí)，我們發(fā)現(xiàn)，核函數(shù)的選擇及其參數(shù)dc的取值都會(huì)嚴(yán)重影響最終聚類結(jié)果。

(a) 決策圖

(b)聚類結(jié)果圖1 包含4 000個(gè)樣本點(diǎn)的測(cè)試數(shù)據(jù)集的聚類結(jié)果Fig.1 The clustering results of the test dataset containing 4 000 sample points

1.3 核函數(shù)及其參數(shù)選擇對(duì)聚類結(jié)果的影響

圖2所示為常用的兩個(gè)標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集。

(a) aggregation

(b)spiral圖2 兩個(gè)標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集Fig.2 Two standard test datasets: aggregation and spiral

圖2中，aggregation數(shù)據(jù)集[9]包含7個(gè)不同大小、形狀和密度的聚類，共788個(gè)樣本點(diǎn)；spiral數(shù)據(jù)集[10]包含3個(gè)螺旋形聚類，共312個(gè)樣本點(diǎn)。

采用快速搜索密度峰值點(diǎn)的聚類算法對(duì)其進(jìn)行聚類分析，聚類結(jié)果分別如圖3、4、5所示。

(a) 決策圖

(b)dc選取最小2%的距離做截?cái)?/p>

(c) dc選取最小5%的距離做截?cái)?/p>

(d)dc選取最小1%的距離做截?cái)鄨D3 aggregation數(shù)據(jù)集的聚類結(jié)果Fig.3 The clustering results for aggregation datasets

(a) 決策圖

(b)dc選取最小3%的距離做截?cái)鄨D4 spiral數(shù)據(jù)集的聚類結(jié)果(采用指數(shù)核估計(jì))Fig.4 The clustering results for aggregation datasets(using exponential kernel estimation)

(a)dc選取最小1%的距離做截?cái)?/p>

(b)dc選取最小2%的距離做截?cái)?圖5 spiral數(shù)據(jù)集的聚類結(jié)果(采用高斯核估計(jì))Fig.5 The clustering results for aggregation datasets(using gaussian kernel estimation)

圖3(a)、3(b)所示為采用式(4)的指數(shù)核估計(jì)且參數(shù)dc取最小2%的距離做截?cái)鄷r(shí)，aggregation數(shù)據(jù)集得到的聚類決策圖及相應(yīng)聚類結(jié)果。由圖3(b)可知，聚類算法可以正確識(shí)別aggregation數(shù)據(jù)集的7個(gè)不同大小、形狀和密度的聚類。但如果采用截?cái)嗪?，且令dc分別取最小5%或1%的距離做截?cái)?，聚類結(jié)果如圖3(c)、3(d)所示。圖3(c)中，聚類質(zhì)量明顯下降，很多樣本點(diǎn)被誤分噪聲數(shù)據(jù)。由此可見，聚類結(jié)果對(duì)參數(shù)dc的取值非常敏感，進(jìn)一步分析核函數(shù)選擇對(duì)聚類結(jié)果的影響。定性討論核函數(shù)及其參數(shù)dc的選擇對(duì)聚類結(jié)果的影響。給定包含n個(gè)樣本點(diǎn)的數(shù)據(jù)集D，根據(jù)式(1)，任一樣本點(diǎn)xiD處的局部密度估計(jì)值dc等價(jià)于以其他樣本點(diǎn)xjD為中心的、n-1個(gè)核函數(shù)的疊加，其中j≠i。這表示每個(gè)樣本點(diǎn)的局部密度估計(jì)值等于所有其他樣本點(diǎn)在該處的“貢獻(xiàn)”的疊加，“貢獻(xiàn)”的大小依賴于兩點(diǎn)間的距離。

圖4(a)、4(b)所示為采用指數(shù)核估計(jì)且dc選取最小2%的距離做截?cái)鄷r(shí)，spiral數(shù)據(jù)集得到聚類決策圖及其聚類結(jié)果，顯然聚類結(jié)果可以正確識(shí)別spiral數(shù)據(jù)集的3個(gè)螺旋形聚類。但如果采用式(5)所示的高斯核估計(jì)，令dc分別選取最小1%或2%的距離做截?cái)鄷r(shí)，聚類結(jié)果如圖5(a)、5(b)所示。顯然，當(dāng)dc取值固定時(shí)，聚類結(jié)果對(duì)核函數(shù)的選擇也非常敏感。事實(shí)上，采用高斯核估計(jì)對(duì)spiral數(shù)據(jù)集進(jìn)行聚類分析，dc要選取大于2%的距離做截?cái)?，才能得到相?duì)較好的聚類結(jié)果。而不是簡(jiǎn)單地令dc選取所有樣本點(diǎn)間距離的最小1%-2%做截?cái)嗉纯伞?/p>

圖6所示為dc=2時(shí)指數(shù)核與高斯核的截?cái)嗑嚯x比較，圖中指數(shù)核的截?cái)嗑嚯x遠(yuǎn)大于高斯核，這意味著：dc取值相同時(shí)，采用指數(shù)核估計(jì)樣本點(diǎn)的局部密度，有貢獻(xiàn)的近鄰樣本點(diǎn)相對(duì)更多；而采用高斯核估計(jì)進(jìn)行聚類分析時(shí)，參數(shù)dc的取值應(yīng)相對(duì)較大，才能產(chǎn)生與指數(shù)核估計(jì)相似的聚類結(jié)果。

圖6 指數(shù)核與高斯核的截?cái)嗑嚯x比較Fig.6 Comparison of truncative distance between exponential kernel and Gaussian kernel

綜上所述，快速搜索密度峰值點(diǎn)的聚類算法雖然具有良好的聚類質(zhì)量，可以發(fā)現(xiàn)不同形狀、大小和密度的聚類，可以有效處理噪聲數(shù)據(jù)，但聚類結(jié)果嚴(yán)重依賴于核函數(shù)及其參數(shù)dc的人為選擇，論文中沒(méi)有討論核函數(shù)選擇對(duì)密度估計(jì)乃至最終聚類結(jié)果的影響。事實(shí)上，參數(shù)dc的選擇不能脫離具體的核函數(shù)而單獨(dú)討論；即使針對(duì)特定的核函數(shù)，參數(shù)dc的取值通常也依賴于數(shù)據(jù)分布的具體特點(diǎn)，不存在適用于所有問(wèn)題的經(jīng)驗(yàn)策略?？紤]到實(shí)際應(yīng)用中，讓用戶選擇合適的核函數(shù)及參數(shù)顯然是不切實(shí)際的。下面，我們將引入一種基于密度估計(jì)熵最小化的自適應(yīng)參數(shù)優(yōu)化方法，根據(jù)核函數(shù)形態(tài)與底層數(shù)據(jù)分布特點(diǎn)自動(dòng)選擇合適的參數(shù)dc值，彌補(bǔ)核函數(shù)及其參數(shù)值人為確定的羈絆。同時(shí)，我們將引入局部密度估計(jì)值的近似計(jì)算方法改進(jìn)算法性能，由此得到改進(jìn)的快速搜索密度峰值點(diǎn)的聚類算法。

2 改進(jìn)的搜索密度峰值的聚類算法

2.1 基于密度估計(jì)熵最小化的自適應(yīng)參數(shù)優(yōu)選

信息論中用香農(nóng)熵作為系統(tǒng)不確定性的度量，熵越大，不確定性就越大。給定n個(gè)樣本點(diǎn)的局部密度估計(jì)值ρ1,ρ2,…,ρn，如果每個(gè)樣本點(diǎn)的密度估計(jì)值相等，我們對(duì)底層數(shù)據(jù)分布的不確定性最大，具有最大的香農(nóng)熵。反之，不確定性最小，具有最小的香農(nóng)熵。由此，可以引入如下的密度估計(jì)熵[7]衡量樣本點(diǎn)局部密度估計(jì)的合理性，即

(6)

對(duì)于給定的核函數(shù)形態(tài)，分析密度參數(shù)dc由0至+遞增過(guò)程中密度估計(jì)熵H的變化情況：當(dāng)dc0時(shí)，H趨近于Hmax=log(n)；隨著dc的增大，H首先減小，在某個(gè)優(yōu)化dc值處達(dá)到最小值，然后又逐漸增大，當(dāng)dc+時(shí)，再次趨近于最大值Hmax=log(n)。對(duì)應(yīng)最小密度估計(jì)熵的dc值可以看作參數(shù)優(yōu)化值。也就是說(shuō)，優(yōu)化dc值可以看作一個(gè)單變量非線性函數(shù)的最優(yōu)化問(wèn)題，即有

(7)

此類問(wèn)題存在很多標(biāo)準(zhǔn)算法，如簡(jiǎn)單試探法和模擬退火法等。實(shí)際應(yīng)用中可采用樣本容量的隨機(jī)抽樣方法降低優(yōu)化dc值的時(shí)間開銷。n很大時(shí)，可以采用抽樣率不小于2.5%的隨機(jī)抽樣方法來(lái)提高優(yōu)化算法的性能[5]。

理論上，對(duì)于用戶任意指定的核函數(shù)形態(tài)，采用基于密度估計(jì)熵最小化的參數(shù)優(yōu)化方法，都可以根據(jù)底層數(shù)據(jù)的分布特點(diǎn)自動(dòng)優(yōu)選合適的參數(shù)dc值。最終的密度估計(jì)結(jié)果取決于參數(shù)dc的優(yōu)化值，而與核函數(shù)的具體形態(tài)的相關(guān)性并不明顯?？紤]到高斯函數(shù)具有良好的數(shù)學(xué)性質(zhì)和普適性，建議采用式(3)所示的高斯核估計(jì)方法計(jì)算所有樣本點(diǎn)的局部密度估計(jì)值。

2.2 局部密度估計(jì)值的近似計(jì)算

給定包含n個(gè)樣本點(diǎn)的數(shù)據(jù)集D，考慮到計(jì)算每個(gè)樣本點(diǎn)xiD的局部密度估計(jì)值dc需要遍歷所有其他樣本點(diǎn)，算法復(fù)雜度較高，近似為。根據(jù)高斯函數(shù)的數(shù)學(xué)性質(zhì)，對(duì)于給定的參數(shù)dc值，當(dāng)樣本點(diǎn)間當(dāng)距離大于時(shí)，局部密度估計(jì)的貢獻(xiàn)會(huì)快速衰減為0，即每個(gè)樣本點(diǎn)的局部密度估計(jì)值取決于半徑為的鄰域范圍內(nèi)的近鄰樣本點(diǎn)的影響。由此，可以引入局部密度估計(jì)的近似計(jì)算改善聚類算法的性能。

計(jì)算任一樣本點(diǎn)xi(1≤i≤n)的局部密度估計(jì)值ρi時(shí)，只考慮樣本點(diǎn)xi所處網(wǎng)格單元cell(xi)及其鄰近網(wǎng)格單元neighbor(cell(xi))內(nèi)所有樣本點(diǎn)的影響，由此得到樣本點(diǎn)xi的局部密度估計(jì)值ρi的近似計(jì)算公式，即有

(8)

(9)

2.3 改進(jìn)算法描述

算法 改進(jìn)的搜索密度峰值的聚類算法(ICADEP)

算法步驟：

1)隨機(jī)抽取nsample個(gè)樣本點(diǎn)組成抽樣數(shù)據(jù)集SampleSet；

2)dc=Optimal_Parameter(SampleSet)；//用抽樣數(shù)據(jù)集優(yōu)化估計(jì)密度參數(shù)dc；

4)ρ=Density_Estimation(D, Map,dc)；//計(jì)算所有樣本點(diǎn)的局部密度估計(jì)值ρ1,ρ2,…,ρn；

5)δ=NN_Distance(D, Map,ρ)；//按照局部密度估從大到小的順序，計(jì)算所有樣本點(diǎn)的高密度最所鄰距離δ1,…,δn；

6)C=Decision_Graph(D,ρ,δ)；//形成決策圖，根據(jù)用戶交互，確定代表聚類中心的樣本子集；

3 實(shí)驗(yàn)結(jié)果與比較

這里采用圖1、2所示的測(cè)試數(shù)據(jù)集檢驗(yàn)改進(jìn)算法ICADEP的有效性。所有程序用軟件Matlab2011實(shí)現(xiàn)，測(cè)試在一臺(tái)PC機(jī)(i5-3210M CPU、8GHz內(nèi)存、Win7)上進(jìn)行，聚類結(jié)果如圖7～9所示。圖7所示的測(cè)試數(shù)據(jù)包含6個(gè)聚類和一些噪聲數(shù)據(jù)，共4 000個(gè)樣本點(diǎn)。圖7(a)所示為原算法[1]的聚類結(jié)果，其參數(shù)dc值是一個(gè)經(jīng)驗(yàn)值0.03，即選取最小2%的距離做截?cái)?；圖7(b)所示為改進(jìn)算法的聚類結(jié)果，其參數(shù)dc值是通過(guò)密度估計(jì)熵最小化得到的優(yōu)化值，略大于論文[1]實(shí)驗(yàn)采用的經(jīng)驗(yàn)值，但聚類質(zhì)量相對(duì)更好，而且抗噪聲能力更好。

(a)原算法[1](dc=0.03)

(b)ICADEP算法(dc=0.05)圖7 4 000個(gè)隨機(jī)樣本點(diǎn)的聚類結(jié)果比較Fig.7 Comparison of clustering results of 4 000 random sample points

圖8(a)所示為原算法聚類結(jié)果，參數(shù)dc選取最小2%的距離做截?cái)?，即dc=2.23；而圖8(b)所示的改進(jìn)算法聚類結(jié)果中，通過(guò)密度估計(jì)熵最小化得到的優(yōu)化dc值雖然略小于論文[1]實(shí)驗(yàn)的經(jīng)驗(yàn)值，即dc=2.02，但聚類結(jié)果同樣能夠正確識(shí)別原始數(shù)據(jù)分布的7個(gè)內(nèi)在的數(shù)據(jù)類。

(a)原算法[1](dc=2.23)

(b)ICADEP算法(dc=2.02)圖8 aggregation數(shù)據(jù)集的聚類結(jié)果比較Fig.8 Comparison of clustering results for aggregation datasets

圖9所示為spiral數(shù)據(jù)集的聚類結(jié)果比較。

(a) 原算法[1]的決策圖(dc =1.07)

(b)原算法[1]的相應(yīng)聚類結(jié)果(dc =1.07)

(c) ICADEP算法的決策圖(dc=0.866)

(d)ICADEP算法的相應(yīng)聚類結(jié)果(dc=0.866)圖9 spiral數(shù)據(jù)集的聚類結(jié)果比較Fig.9 Comparison of clustering results for spiral datasets

圖9(a)所示為原算法聚類結(jié)果，算法采用指數(shù)核估計(jì)，參數(shù)dc選取最小3%的距離做截?cái)啵从衐c=1.07；而圖9(b)所示的改進(jìn)算法聚類結(jié)果中，通過(guò)密度估計(jì)熵最小化得到的優(yōu)化dc值略小于論文[1]實(shí)驗(yàn)的經(jīng)驗(yàn)值，即有dc=0.866，聚類結(jié)果同樣能夠正確識(shí)別原數(shù)據(jù)集內(nèi)在的3個(gè)螺旋類。

4 結(jié)束語(yǔ)

聚類是大數(shù)據(jù)分析與數(shù)據(jù)挖掘的基礎(chǔ)問(wèn)題。2014年刊登在《Science》上的論文《Clustering by fast search and find of density peaks》提出一種快速搜索和發(fā)現(xiàn)密度峰值點(diǎn)的聚類算法。算法簡(jiǎn)單實(shí)用，能夠發(fā)現(xiàn)任意形狀、大小和密度的聚類，能夠有效處理噪聲和離群數(shù)據(jù)，但聚類結(jié)果依賴于核函數(shù)及其參數(shù)dc的人為選擇。論文提出一種改進(jìn)的快速搜索密度峰值的聚類算法，引入基于密度估計(jì)熵最小化的自適應(yīng)參數(shù)優(yōu)化方法，彌補(bǔ)核函數(shù)及其參數(shù)值人為確定的羈絆；引入局部密度估計(jì)值的近似計(jì)算方法，改善聚類算法性能。比較實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法不僅能有效解決原算法的參數(shù)優(yōu)選問(wèn)題，而且具有相對(duì)更好的聚類性能，算法時(shí)間復(fù)雜度近似為O(log(ngrid))，ngrid<

[1]RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496.

[2]MANYIKA J, CHUI M, BROWN B, et al. Big data: the next frontier for innovation, competition, and productivity[M]. McKinsey Global Institute, 2011.

[3]HAN Jiawei, KAMBER M, PEI Jian. Data mining: concepts and techniques[M]. 3rd ed. Burlington: Morgan Kaufmann, 2011.

[4]JAIN A K. Data clustering: 50 years beyond k-means[Z]. Pattern Recognition Letters, 2009.

[5]唐杰, 東昱曉, 蔣朦, 等. SIGKDD二十周年慶典[J]. 中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊, 2014, 10(10): 58-64.

[6]http://comments.sicencemag.org/content/10.1126/science.1242072 (請(qǐng)核對(duì)網(wǎng)址及補(bǔ)充文獻(xiàn)內(nèi)容)

[7]淦文燕, 李德毅. 基于核密度估計(jì)的層次聚類算法[J]. 系統(tǒng)仿真學(xué)報(bào), 2004, 16(2): 302-305. GAN Wenyan, LI Deyi. Hierarchical clustering based on kernel density estimation[J]. Journal of System Simulation, 2004, 16(2): 302-305.

[8]ESTER M, KRIEGEL H, SANDER J, et al. A density based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the 2nd international conference on knowledge discovery and data mining. Portland, 1996: 226-231.

[9]GIONIS A, MANNILA H, TSAPARAS P. Clustering aggregation[J]. ACM transactions on knowledge discovery from data, 2007, 1(1): Article No.4.

淦文燕，女，副教授。主要研究方向?yàn)槿斯ぶ悄?，?shù)據(jù)挖掘，機(jī)器學(xué)習(xí)。

劉沖，男，碩士研究生，主要研究方向?yàn)榇髷?shù)據(jù)分析，數(shù)據(jù)挖掘。

An improved clustering algorithm that searches and finds density peaks

GAN Wenyan， LIU Chong

(College of Command Information System, PLA University of Science and Technology, Nanjing 210007, China)

Clustering is a fundamental issue for big data analysis and data mining. In July 2014, a paper in the Journal of Science proposed a simple yet effective clustering algorithm based on the idea that cluster centers are characterized by a higher density than their neighbors and having a relatively large distance from points with higher densities. The proposed algorithm can detect clusters of arbitrary shapes and differing densities but is very sensitive to tunable parameterdc.Inthispaper,weproposeanimprovedclusteringalgorithmthatadaptivelyoptimizesparameterdc.Thetimecomplexityofouralgorithmwassuper-linearwithrespecttothesizeofthedataset.Further,ourtheoreticalanalysisandexperimentalresultsshowtheeffectivenessandefficiencyofourimprovedalgorithm.

data mining; clustering algorithms; kernel density estimation; entropy

2015-12-31.

國(guó)家自然科學(xué)基金項(xiàng)目(60974086).

劉沖. E-mail：lc1368542460@126.com.

10.11992/tis.201512036

TP

A

1673-4785(2017)02-0229-07

淦文燕，劉沖. 一種改進(jìn)的搜索密度峰值的聚類算法[J]. 智能系統(tǒng)學(xué)報(bào)， 2017, 12(2): 229-236.

英文引用格式： GAN Wenyan， LIU Chong. An improved clustering algorithm that searches and finds density peaks[J]. CAAI transactions on intelligent systems, 2017, 12(2): 229-236.