結(jié)合蝙蝠算法改進(jìn)的密度峰值聚類算法

吳辰文,劉曉光,魏立鑫

(蘭州交通大學(xué) 電子與信息工程學(xué)院,甘肅 蘭州 730070)

在科技迅猛發(fā)展的今天,計(jì)算機(jī),信息,互聯(lián)網(wǎng)技術(shù)已經(jīng)不僅僅是某一門學(xué)科或某一類職業(yè)的專屬,更是廣泛的融入到醫(yī)學(xué)[1],商業(yè)[2],工農(nóng)業(yè)[3-4]等各個(gè)領(lǐng)域之中。這些領(lǐng)域伴隨著計(jì)算機(jī)技術(shù)的應(yīng)用,每天都會(huì)產(chǎn)生海量的數(shù)據(jù)。由于計(jì)算機(jī)硬件技術(shù)的不斷升級,這些數(shù)據(jù)產(chǎn)生的速度也不斷加快,這也就是平時(shí)我們所說的大數(shù)據(jù)時(shí)代的數(shù)據(jù)爆炸增長。

如何在大規(guī)模的數(shù)據(jù)之中提取到有用的知識(shí)成為了研究的重點(diǎn)，數(shù)據(jù)挖掘技術(shù)便應(yīng)運(yùn)而生。數(shù)據(jù)挖掘技術(shù)通過一系列算法來搜索那些隱藏于大數(shù)據(jù)之中的信息。而聚類分析作為數(shù)據(jù)挖掘最重要的研究內(nèi)容之一,旨在將數(shù)據(jù)集分為多組組內(nèi)具有相同特性、組間具有不同特性的簇。聚類分析的算法可以分為劃分法[5](partitioning methods)、層次法[6](hierarchical methods)、基于密度的方法[7](density-based methods)、基于網(wǎng)格的方法[8](grid-based methods)、基于模型的方法[9](model-based methods)。

Alex Rodriguez和Alessandro Laio在2014年提出了一種基于密度的聚類方法[10],該算法相比于其他同類算法的優(yōu)勢在于對于任意形狀的數(shù)據(jù)集,其均可以快速、高效地發(fā)現(xiàn)數(shù)據(jù)集的類簇中心，并進(jìn)行非類簇中心樣本點(diǎn)的分配,在大規(guī)模數(shù)據(jù)集上表現(xiàn)良好。該算法的主要思想是尋找被低密度區(qū)域分離的高密度區(qū)域。目前,已有許多專家學(xué)者針對密度峰值聚類算法進(jìn)行改進(jìn):WANG Shuliang等人將密度峰值聚類算法結(jié)合信息熵理論,使其可以自動(dòng)從數(shù)據(jù)集中提取截?cái)嗑嚯x參數(shù)[11]。薛小娜等人提出了一種基于K近鄰和多類合并的密度峰值聚類算法,以提高算法聚類精度[12]。高詩瑩等人將DPC算法和密度比的概念相結(jié)合,從而解決了DPC算法在密度分布不均衡的數(shù)據(jù)集上表現(xiàn)不佳的問題[13]。董曉君等人利用無參核密度估計(jì)來分析數(shù)據(jù)并自適應(yīng)地選取截?cái)嗑嚯x[14]。盡管這些算法在一定程度上解決了DPC算法的部分缺陷,但依舊存在諸如模型復(fù)雜、真實(shí)數(shù)據(jù)集上表現(xiàn)不佳等問題。本文要解決的DPC算法的主要問題在于:算法的結(jié)果依賴于截?cái)嗑嚯x的選取,但目前選取截?cái)嗑嚯x的方法主要還是人工選取,主觀性太強(qiáng)。而將DPC算法與啟發(fā)式優(yōu)化算法相結(jié)合,配合適應(yīng)度函數(shù),對截?cái)嗑嚯x參數(shù)進(jìn)行尋優(yōu),可以有效解決此類問題。

蝙蝠算法(bat algorithm,BA)是由YANG Xinshe于2010年提出的一種高效生物啟發(fā)式算法[15],該算法假設(shè)每個(gè)虛擬蝙蝠在位置xi均有隨機(jī)的飛行速度vi,同時(shí)每只蝙蝠具有不同的頻率f或波長λ、響度Ai和脈沖發(fā)射速率r。蝙蝠發(fā)現(xiàn)自己的獵物時(shí),通過改變脈沖發(fā)射速率、響度以及頻率來對獵物定位,進(jìn)行最優(yōu)解(位置xi)的選擇,直到目標(biāo)停止或條件得到滿足。本質(zhì)上就是使用調(diào)諧技術(shù)來控制蝙蝠群的動(dòng)態(tài)行為,平衡調(diào)整算法的相關(guān)參數(shù),以取得蝙蝠算法的最優(yōu)解。BA在工程設(shè)計(jì)、分類等方面得到了廣泛的應(yīng)用[16-17]。BA同遺傳算法和粒子群算法等傳統(tǒng)的尋優(yōu)算法進(jìn)行比較,也具有較大的優(yōu)勢，但BA依舊存在缺陷,在收斂的過程中,算法后期的收斂速度會(huì)逐漸變慢,同時(shí)容易陷入局部最優(yōu)。許多專家學(xué)者對蝙蝠算法進(jìn)行了改進(jìn)研究:王海軍等人將蝙蝠算法和BP神經(jīng)網(wǎng)絡(luò)相結(jié)合對圖像進(jìn)行去噪處理[18]；劉振等人提出了一種自適應(yīng)進(jìn)化的蝙蝠算法對原算法的收斂性進(jìn)行改進(jìn)[19]；王馨等人基于負(fù)梯度理論，通過調(diào)整蝙蝠算法的速度更新策略來改進(jìn)蝙蝠算法的全局尋優(yōu)能力[20]。

針對以上兩種算法的優(yōu)點(diǎn)和缺陷，本文提出了結(jié)合蝙蝠算法改進(jìn)的密度峰值聚類算法(weighted bat algorithm denisity peaks clustering,WBADPC)。首先，對蝙蝠算法的蝙蝠速度和位置公式進(jìn)行改進(jìn)；然后，運(yùn)用改進(jìn)后的蝙蝠算法對密度峰值聚類的截?cái)鄥?shù)進(jìn)行優(yōu)化,使用聚類評判準(zhǔn)則函數(shù)作為適應(yīng)度函數(shù),利用蝙蝠算法較強(qiáng)的全局尋優(yōu)能力在截?cái)嗑嚯x取值范圍內(nèi)選取使得適應(yīng)度函數(shù)取值盡可能大地截?cái)嗑嚯x參數(shù),再運(yùn)用密度峰值聚類算法進(jìn)行聚類；最后，通過評判準(zhǔn)則函數(shù)與傳統(tǒng)的密度峰值聚類算法以及其他傳統(tǒng)的聚類算法進(jìn)行比較,并在多種數(shù)據(jù)集上進(jìn)行驗(yàn)證。實(shí)驗(yàn)結(jié)果表明,使用蝙蝠算法優(yōu)化的密度峰值聚類算法與其他聚類算法相比,具有較好的聚類效果。

1 相關(guān)算法介紹

1.1 DPC算法

DPC算法基于如下假設(shè)[21]：①類簇中心點(diǎn)的密度大于周圍鄰居點(diǎn)的密度;②類簇中心點(diǎn)與更高密度點(diǎn)之間的距離相對較大。為了尋找滿足上述假設(shè)的類簇中心點(diǎn),DPC算法需要引入兩個(gè)參數(shù):數(shù)據(jù)點(diǎn)i的局部密度ρi;局部密度大于數(shù)據(jù)點(diǎn)i的點(diǎn)集之中距離點(diǎn)i最近的點(diǎn)與點(diǎn)i之間的距離δi。數(shù)據(jù)點(diǎn)i的局部密度ρi的計(jì)算有兩種方式,當(dāng)數(shù)據(jù)集規(guī)模較大時(shí):

ρi=∑χ(dij-dc)。

(1)

其中，dij為點(diǎn)i與點(diǎn)j之間的距離,dc為密度峰值聚類算法的截?cái)嗑嚯x參數(shù)。函數(shù)χ為

(2)

面對較小規(guī)模數(shù)據(jù)集時(shí),局部密度ρi可以利用指數(shù)核函數(shù)來進(jìn)行計(jì)算，

(3)

點(diǎn)i與較高密度點(diǎn)的最小距離為

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

(4)

當(dāng)點(diǎn)i為局部密度最高的點(diǎn)時(shí)，

δi=maxj(dij)。

(5)

在選取聚類中心時(shí),由DPC算法的前提假設(shè)可以知道,當(dāng)點(diǎn)i的局部密度ρi以及與較高密度點(diǎn)的最小距離δi均較大時(shí),點(diǎn)i才可能被選為聚類中心點(diǎn)。在文獻(xiàn)[10]中使用決策圖的方法來選取聚類中心,即將每點(diǎn)的ρ值和δ值于坐標(biāo)平面內(nèi)繪出,然后，將ρ和δ值都較大的點(diǎn)作為聚類中心。但是，當(dāng)數(shù)據(jù)點(diǎn)分布較為稀疏時(shí),就很難只通過ρ和δ值來確定聚類中心,此時(shí)需要引入另一個(gè)參數(shù)γ，

γ=ρ×δ，

(6)

將γ值較高的k個(gè)點(diǎn)選為聚類中心。

DPC算法的具體步驟如下:

1)計(jì)算數(shù)據(jù)點(diǎn)之間的距離,并求得距離矩陣;

2)人工選取截?cái)嗑嚯x,計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的局部密度ρ,以及與較高數(shù)據(jù)點(diǎn)之間的最小距離δ;

3)通過得出的ρ和δ的值來計(jì)算每個(gè)點(diǎn)的γ值并排序,選取前k個(gè)作為聚類中心點(diǎn);

4)對剩余非聚類中心點(diǎn)依照距離最近原則進(jìn)行歸類。

1.2 蝙蝠算法

蝙蝠算法是一種模擬蝙蝠在飛行過程中通過發(fā)射超聲波以及反射的回聲來定位搜索獵物的元啟發(fā)式算法。此算法基于如下假設(shè):

1)蝙蝠以速度vi飛行在位置xi(解)附近,并且可以根據(jù)與目標(biāo)的距離自動(dòng)調(diào)整脈沖頻率;

2)蝙蝠發(fā)出的超聲波的響度A從大到小變化。

在該算法的實(shí)際應(yīng)用中,通過頻率f控制波長λ的變化來調(diào)整蝙蝠飛行的距離。當(dāng)蝙蝠越靠近獵物時(shí),波長取值越小,飛行距離越短。

在一個(gè)N維的搜索空間中,在第t次迭代時(shí),第i個(gè)蝙蝠的速度和位置公式分別為

fi=fmin+(fmax-fmin)β，

(7)

(8)

(9)

其中，β的取值范圍在0到1之間,是一個(gè)隨機(jī)向量，x*是當(dāng)前全局最優(yōu)解。在求解問題前,在[fmin,fmax]的范圍內(nèi)為蝙蝠的脈沖發(fā)射頻率初始化賦值。求解問題時(shí),在保證波長不變的同時(shí)，在取值范圍內(nèi)改變蝙蝠的脈沖發(fā)射頻率。開始搜索之后,每只蝙蝠的位置為

xnew=xold+εAt。

(10)

其中，ε為在-1到1范圍之間的隨機(jī)數(shù),At為在第t次迭代時(shí),所有蝙蝠的平均響度。在迭代過程中,蝙蝠的脈沖發(fā)射響度A和速率r的更新公式為

(11)

(12)

其中α和γ是響度和速率更新的比率，通常α取值在0到1之間，γ取值不小于0。蝙蝠脈沖發(fā)射響度和速率會(huì)在不斷地趨近于最優(yōu)解的過程中更新。基于以上公式和分析,蝙蝠算法的步驟描述如下:

1)對算法參數(shù)進(jìn)行初始化:蝙蝠初始位置和速度、目標(biāo)函數(shù)、脈沖發(fā)射頻率范圍、蝙蝠種群數(shù)量以及響度和速率;

2)通過調(diào)整蝙蝠的脈沖發(fā)射頻率進(jìn)而改變波長,產(chǎn)生新的解,并根據(jù)新解的值改變蝙蝠位置和速度;

3)產(chǎn)生一個(gè)隨機(jī)數(shù),如果隨機(jī)數(shù)大于速率r,就從最佳解集中選取一個(gè)解在其附近形成局部解;

4)通過隨機(jī)飛行產(chǎn)生一個(gè)新解;

5)產(chǎn)生隨機(jī)數(shù),如果隨機(jī)數(shù)小于此時(shí)的響度,并且新解對應(yīng)的適應(yīng)度的值要優(yōu)于之前的解對應(yīng)的適應(yīng)度的值,用新解替換之前的解,并更新響度和速率;

6)將蝙蝠當(dāng)前的位置進(jìn)行排列并選取當(dāng)前的最優(yōu)解,若滿足結(jié)束條件,跳出并輸出當(dāng)前最優(yōu)解,否則轉(zhuǎn)回步驟2)。

2 結(jié)合蝙蝠算法改進(jìn)的密度峰值聚類算法

本文通過改進(jìn)后的蝙蝠算法對密度峰值聚類需要人工選取截?cái)嗑嚯x的缺陷進(jìn)行改進(jìn),主要思想是通過蝙蝠算法較強(qiáng)的全局最優(yōu)解的尋優(yōu)能力,將一個(gè)評價(jià)聚類指標(biāo)的函數(shù)作為適應(yīng)度函數(shù),在解的空間中進(jìn)行尋優(yōu),從而避免DPC算法中由于需要手動(dòng)給出截?cái)嗑嚯x而產(chǎn)生的不確定性。

2.1 蝙蝠算法的改進(jìn)

在基本的蝙蝠算法之中,蝙蝠的速度是根據(jù)前一代的速度和位置進(jìn)行更新的,但隨著迭代次數(shù)的增加,蝙蝠的速度會(huì)逐漸減緩,甚至蝙蝠種群可能會(huì)出現(xiàn)進(jìn)化停滯。受到文獻(xiàn)[16]的啟發(fā),為了解決這一問題,本文對蝙蝠的速度更新公式(8)加入自適應(yīng)慣性權(quán)重,將式(8)修改為

(13)

其中，

(14)

ωmax和ωmin分別代表最大最小自適應(yīng)慣性權(quán)重,t代表當(dāng)前迭代次數(shù),N代表最大迭代次數(shù)。加入權(quán)重后,在迭代之初,ω較大,算法的全局搜索能力較強(qiáng),有利于跳出局部最優(yōu),在算法迭代的后期，ω會(huì)逐漸減小,有利于在最優(yōu)解的鄰域內(nèi)進(jìn)行局部尋優(yōu),并加速算法的收斂。將蝙蝠種群設(shè)置為10,迭代次數(shù)設(shè)置為1 000,利用兩種算法對同一適應(yīng)度函數(shù)進(jìn)行迭代實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果顯示,雖然改進(jìn)前后的算法都能在一定循環(huán)次數(shù)內(nèi)找到最優(yōu)解,但改進(jìn)后的算法收斂到最優(yōu)解所需要的迭代次數(shù)大大減少,算法的收斂性增強(qiáng),較好地克服了基本蝙蝠算法易過早陷入局部最優(yōu)的缺陷。

2.2 結(jié)合加權(quán)蝙蝠算法優(yōu)化截?cái)嗑嚯x參數(shù)

在傳統(tǒng)的DPC算法中,由式(3)和式(4)可知,密度峰值聚類的兩個(gè)重要參數(shù)，局部密度和與高密度點(diǎn)之間的最小距離均與截?cái)嗑嚯x有關(guān)。但截?cái)嗑嚯xdc往往由人工給出,dc取值過大,會(huì)導(dǎo)致聚類個(gè)數(shù)多于真實(shí)簇類數(shù)；相反,dc取值過小，導(dǎo)致聚類個(gè)數(shù)少于真實(shí)簇類數(shù)。本文提出的WBADPC算法將聚類算法的Silhouette指標(biāo)[22]作為適應(yīng)度函數(shù)。Silhouette指標(biāo)最早由Peter J. Rousseeuw在1986年提出。它結(jié)合內(nèi)聚度和分離度兩種因素，可以用來在相同原始數(shù)據(jù)的基礎(chǔ)上評價(jià)不同算法、或者算法不同運(yùn)行方式對聚類結(jié)果所產(chǎn)生的影響。對于單個(gè)樣本,設(shè)α是與它同類別中其他樣本的平均距離,b是與它距離最近不同類別中樣本的平均距離,Silhouette指標(biāo)為

(15)

Silhouette指標(biāo)的取值范圍在[-1,1]之間,其值越接近1,說明聚類的結(jié)果就越合理。Silhouette指標(biāo)結(jié)合了聚類結(jié)果的類間距離和類內(nèi)距離,對于聚類結(jié)果能產(chǎn)生準(zhǔn)確的評判,并且不需要先驗(yàn)知識(shí),所以，本文采用Silhouette指標(biāo)作為適應(yīng)度函數(shù)。

本文所提出算法通過蝙蝠算法較強(qiáng)的尋優(yōu)能力,通過多次迭代,找出能使DPC算法的Silhouette指標(biāo)最大的截?cái)嗑嚯x作為對于當(dāng)前數(shù)據(jù)集最合適的截?cái)嗑嚯xdc,算法的具體步驟如下。

輸入:數(shù)據(jù)集Data,蝙蝠數(shù)量,最大迭代次數(shù),響度,速率,頻率的變化范圍,自適應(yīng)慣性權(quán)重的最大和最小值。

輸出:聚類結(jié)果C。

1)數(shù)據(jù)預(yù)處理;

2)計(jì)算樣本間的歐氏距離矩陣,根據(jù)距離矩陣確定截?cái)嗑嚯x的搜索空間,并生成初始解;

3)執(zhí)行DPC算法,根據(jù)聚類結(jié)果生成Silhouette指標(biāo)的值;

4)調(diào)整改進(jìn)后的蝙蝠算法參數(shù)生成新的解,計(jì)算每個(gè)解所對應(yīng)的Silhouette指標(biāo);

5)產(chǎn)生隨機(jī)數(shù),如果新解對應(yīng)的適應(yīng)度的值要優(yōu)于之前的解對應(yīng)的適應(yīng)度的值,用新解替換之前的解,并更新響度和速率。否則保持原來的解不變;

6)若滿足迭代終止條件,跳出循環(huán)并得到最優(yōu)截?cái)嗑嚯x,否則轉(zhuǎn)回3);

7)用所得到的最優(yōu)截?cái)嗑嚯x進(jìn)行密度峰值聚類,輸出聚類結(jié)果。

算法的流程圖如圖1所示。

圖1 WBADPC算法流程圖Fig.1 A schematic diagram of WBADPC

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

為了驗(yàn)證算法的有效性,本文采用6個(gè)數(shù)據(jù)集對WBADPC算法進(jìn)行測試和評價(jià)。實(shí)驗(yàn)環(huán)境如表1所示,所采用的數(shù)據(jù)集屬性如表2所示。

3.1 評價(jià)指標(biāo)

由于本文所提算法的評價(jià)指標(biāo)采用Silhouette指標(biāo),為了避免重復(fù)計(jì)算Silhouette指標(biāo)帶來的影響,本次實(shí)驗(yàn)的評價(jià)指標(biāo)主要采用調(diào)整互信息(adjusted mutual information,AMI)指標(biāo)和調(diào)整蘭德指數(shù)(adjusted Rand index,ARI)對聚類結(jié)果進(jìn)行評價(jià)。

3.1.1 AMI指標(biāo) 互信息MI(mutual information based scores)是一個(gè)基于信息論的概念,可以用作聚類結(jié)果的評價(jià)指標(biāo),主要用來對一些有先驗(yàn)知識(shí)的數(shù)據(jù)集的聚類結(jié)果進(jìn)行評判。互信息可以用來衡量兩個(gè)數(shù)據(jù)分布的吻合情況,如果A和B分別是M個(gè)樣本的同一個(gè)數(shù)據(jù)集用兩種不同聚類方法所得到的類別標(biāo)簽,則這兩個(gè)類別標(biāo)簽的熵分別為

(16)

(17)

(18)

(19)

Ai和Bj分別代表,在A和B的標(biāo)簽之中第i類和第j類的標(biāo)簽,A與B之間的互信息可以定義為

(20)

而調(diào)整互信息AMI就可以表示為

(21)

MI的取值范圍為[0,1],E(MI)是對MI的數(shù)學(xué)期望。AMI同樣基于信息論,是對MI的一種改進(jìn),它的取值范圍為[-1,1]。相比于MI來說,AMI具有更高的區(qū)分度,它的取值越接近1,說明聚類效果越好。

3.1.2 ARI指標(biāo) 蘭德系數(shù)(Rand index,RI)和調(diào)整蘭德系數(shù)經(jīng)常被用來做聚類的模型評估,在RI中,假設(shè)U是樣本真實(shí)標(biāo)簽,而V代表聚類結(jié)果,則a為在U中屬于同一類且在V中也屬于同一類的數(shù)據(jù)點(diǎn)對數(shù),b代表在U中屬于同一類但在V中不屬于同一類的數(shù)據(jù)點(diǎn)對數(shù),c表示在U中不為同一類但在V中屬于同一類的數(shù)據(jù)點(diǎn)對數(shù),d即為在U和V中均不屬于同一類的數(shù)據(jù)點(diǎn)對數(shù)。蘭德系數(shù)RI可表示為

(22)

蘭德系數(shù)的取值范圍在[0,1]之間。為了使RI具有更高的區(qū)分度,引入ARI作為RI的改進(jìn),ARI可表示為

(23)

ARI的取值范圍在[-1,1]之間，其結(jié)果越接近1,說明聚類結(jié)果越接近數(shù)據(jù)集的原始標(biāo)簽。

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

本文選用了D31，R15和Aggregation 3個(gè)人工數(shù)據(jù)集以及Iris和Wine兩個(gè)UCI數(shù)據(jù)集,和文獻(xiàn)[23]所提供的白血病數(shù)據(jù)集Leukemia,數(shù)據(jù)集的屬性如表2所示。R15,Aggregation和D31數(shù)據(jù)集均為2維數(shù)據(jù)集,D31的樣本數(shù)量較多,Iris和Wine數(shù)據(jù)集為多維數(shù)據(jù)集,Leukemia數(shù)據(jù)集為基因表達(dá)數(shù)據(jù)的高維數(shù)據(jù)集,可分為3個(gè)類簇。文獻(xiàn)[24]提出了一種基于 K 近鄰的快速密度峰值搜索并高效分配樣本的聚類算法(KNN-DPC)。該算法利用樣本點(diǎn)的K近鄰信息定義樣本局部密度, 搜索和發(fā)現(xiàn)樣本的密度峰值, 以峰值點(diǎn)樣本作為初始類簇中心。將本文提出的WBADPC算法與KNN-DPC算法、標(biāo)準(zhǔn)DPC算法和DBSCAN算法進(jìn)行比較。WBADPC和DPC算法在聚類中心點(diǎn)選取時(shí)，將所有數(shù)據(jù)點(diǎn)的γ值從大到小排列,選取前k個(gè),直到滿足條件

(24)

表1 實(shí)驗(yàn)環(huán)境Tab.1 Simulation environment

表2 所用數(shù)據(jù)集屬性Tab.2 Data set attribute

表3 4種算法在6個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Tab.3 Simulation results of four algorithms on six data sets

對于Aggregation和R15兩個(gè)二維數(shù)據(jù)集來說,數(shù)據(jù)集的類簇間隔較大,樣本數(shù)量較少,有利于聚類,從而會(huì)使4種算法在這兩個(gè)數(shù)據(jù)集上的表現(xiàn)相近。而D31數(shù)據(jù)集樣本數(shù)量較多,數(shù)據(jù)集整體分布復(fù)雜。從圖2中可以看出,在D31數(shù)據(jù)集上前3種算法的聚類結(jié)果較好,但DBSCAN算法出現(xiàn)部分?jǐn)?shù)據(jù)點(diǎn)錯(cuò)誤聚類的情況。在Wine和Leukemia數(shù)據(jù)集上,利用主成分分析法提取主成分進(jìn)行可視化,在圖2中可以看出,WBADPC算法的效果略優(yōu)于KNN-DPC,并且明顯好于其余兩種算法。4種算法在全部6個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如表3所示。圖3和圖4分別表示了AMI和ARI指標(biāo)的對比情況，可以看出，在Iris和Wine兩個(gè)多維數(shù)據(jù)集上,本文提出的WBADPC算法表現(xiàn)最優(yōu),KNN-DPC算法略低,DPC算法在Iris數(shù)據(jù)集上性能要差于DBSCAN。綜合來看,在兩個(gè)UCI的多維數(shù)據(jù)集上,WBADPC算法聚類結(jié)果準(zhǔn)確率最高,其次是KNN-DPC,第3是DPC算法,最后是DBSCAN算法。而在高維數(shù)據(jù)集Leukemia上,WBADPC算法依舊保持良好的聚類性能,而其余3種算法的性能明顯下降。

本文提出的算法在復(fù)雜度方面不僅和問題規(guī)模有關(guān),還與蝙蝠算法的迭代次數(shù)以及適應(yīng)度函數(shù)有關(guān),所以，在提升算法準(zhǔn)確率的基礎(chǔ)上,在時(shí)間復(fù)雜度上略高于其余3種算法,而KNN-DPC算法則略高于DPC算法和DBSCAN算法,DPC算法和DBSCAN算法在時(shí)間復(fù)雜度上最優(yōu)。4種算法空間復(fù)雜度的主要來源均為存儲(chǔ)距離矩陣,對于樣本規(guī)模為n的數(shù)據(jù)集,空間復(fù)雜度均為O(n2),量級相同。所以，本文算法在算法復(fù)雜度方面略高于其他算法,但是在準(zhǔn)確率方面有明顯的提升。

圖2 4種算法在3個(gè)數(shù)據(jù)集上的聚類結(jié)果Fig.2 The clustering results of the four algorithms on the three data sets

圖3 4種算法在6個(gè)數(shù)據(jù)集上的AMI對比圖Fig.3 AMI comparison chart of four algorithms on 6 data sets

圖4 4種算法在6個(gè)數(shù)據(jù)集上的ARI對比圖Fig.4 ARI comparison chart of four algorithms on 6 data sets

4 結(jié) 語

為了改進(jìn)密度峰值聚類算法無法自動(dòng)確定截?cái)嗑嚯x的問題，本文提出一種結(jié)合蝙蝠算法改進(jìn)的密度峰值聚類算法,該算法利用蝙蝠算法較強(qiáng)的全局尋優(yōu)能力,將Silhouette指標(biāo)作為適應(yīng)度函數(shù),在一定的范圍內(nèi),對截?cái)嗑嚯x進(jìn)行尋優(yōu)。通過在人工數(shù)據(jù)集、UCI數(shù)據(jù)集以及基因表達(dá)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證,可以得出結(jié)論:本文所提出的結(jié)合蝙蝠算法改進(jìn)的密度峰值聚類算法能更準(zhǔn)確地發(fā)現(xiàn)聚類中心點(diǎn),并將非聚類中心點(diǎn)樣本分配到合適的類簇,是一種有效的自適應(yīng)聚類算法,能發(fā)現(xiàn)任意形狀的類簇。可用于聚類任意維度、任意規(guī)模的數(shù)據(jù)。下一步研究的目標(biāo)是通過優(yōu)化算法有效降低算法的時(shí)間復(fù)雜度。