鄧然然,李 偉,楊榮新

(長(zhǎng)安大學(xué) 信息工程學(xué)院,西安 710064)

聚類是一種常用的屬于無(wú)監(jiān)督學(xué)習(xí)的數(shù)據(jù)處理方法,由聚類所挖掘出的信息可以為進(jìn)一步深入地分析數(shù)據(jù)提供理論基礎(chǔ)[1].聚類采用定量數(shù)學(xué)思想,按照數(shù)據(jù)間的相似程度將其歸到幾個(gè)群,其結(jié)果滿足各個(gè)群內(nèi)相似性較強(qiáng),而各群體之間相似性較小的特點(diǎn).同一組樣本有時(shí)會(huì)因?yàn)椴煌哪康?、?shù)據(jù)輸入方式、所選的分群特征或數(shù)據(jù)屬性,形成不同的分群結(jié)果.聚類是數(shù)據(jù)挖掘的重要手段[2],聚類算法分為:劃分聚類、層次聚類、密度聚類、網(wǎng)格聚類、圖論聚類等[3].

快速峰值算法是2014年6月Rodriguez Alex 在Science 上提出的一種新型聚類算法,該算法能自動(dòng)選出樣本的類中心,而且能克服一般方法對(duì)數(shù)據(jù)要求的缺陷,可以實(shí)現(xiàn)對(duì)非球形數(shù)據(jù)進(jìn)行高效聚類[4].該算法選定聚類中心:1)較大的局部密度,即中心點(diǎn)相鄰點(diǎn)的密度值均小于該點(diǎn);2)與其他密度更高的點(diǎn)之間的“距離”較大.DPC算法原理簡(jiǎn)單、聚類高效[5],在各個(gè)領(lǐng)域都有廣泛的應(yīng)用[6,7],例如應(yīng)用于高速公路收費(fèi)數(shù)據(jù)分析[8]及異常事件挖掘[9]等.然而,通過(guò)聚類算法的評(píng)價(jià)[10],DPC算法的缺點(diǎn)也十分明顯,需要根據(jù)經(jīng)驗(yàn)值設(shè)定參數(shù)截?cái)嗑嚯x;需要根據(jù)計(jì)算出的局部密度以及距離兩個(gè)值生成用于選擇聚類中心的決策圖,并人為在其中選取這兩個(gè)值都較大的點(diǎn)為聚類中心.這種選擇存在較高的主觀性與不穩(wěn)定性,嚴(yán)重影響后續(xù)非中心點(diǎn)的分配、優(yōu)化以及噪聲點(diǎn)的發(fā)現(xiàn)[11].

現(xiàn)今為止,已有多種改進(jìn)的DPC算法,例如:K 近鄰密度峰值聚類[12-14],結(jié)合K 近鄰的概念重新定義截?cái)嗑嚯x和局部密度的度量方法,避免截止距離的人為設(shè)置;基于果蠅算法的密度峰值聚類[15-17],利用果蠅優(yōu)化算法得到最優(yōu)截止距離,進(jìn)而完成對(duì)局部密度和與密度更高的點(diǎn)的距離的計(jì)算;布谷鳥(niǎo)優(yōu)化的密度峰值快速搜索聚類算法[18],利用布谷鳥(niǎo)優(yōu)化截止距離,引入余弦相似度原理,將方向與實(shí)際距離相結(jié)合,能夠更好的劃分邊界區(qū)域內(nèi)的數(shù)據(jù)點(diǎn);除此之外,還有熱擴(kuò)散密度峰值聚類[19]、自適應(yīng)聚合策略優(yōu)化的密度峰值聚類算法[20]等等.但是現(xiàn)有的改進(jìn)算法仍有改進(jìn)的余地.

果蠅優(yōu)化算法(Fruit fly Optimization Algorithm,FOA)是一種新的群體智能方法[21,22],通過(guò)迭代搜索尋找最優(yōu)解.與此同時(shí),已有諸多學(xué)者致力于改進(jìn)FOA算法,例如新型改進(jìn)果蠅優(yōu)化算法[23]、改進(jìn)的變步長(zhǎng)果蠅優(yōu)化算法[24]、改進(jìn)步長(zhǎng)與策略的果蠅優(yōu)化算法[25]等.但是果蠅優(yōu)化算法還存在許多不足.

本文引入改進(jìn)的自調(diào)節(jié)步長(zhǎng)果蠅優(yōu)化算法[26],該算法根據(jù)當(dāng)前濃度差值變化率,對(duì)步長(zhǎng)進(jìn)行相應(yīng)調(diào)整,用過(guò)迭代計(jì)算,得到最佳截止距離.本文以更高的效率與準(zhǔn)確率的得到這一關(guān)鍵參數(shù),并計(jì)算密度與距離的乘積,根據(jù)乘積值自適應(yīng)的選出備選聚類中心,再?gòu)膫溥x聚類中心中,以同一類僅有一個(gè)中心為原則選出真正的聚類中心,然后對(duì)其他非中心數(shù)據(jù)點(diǎn)進(jìn)行分配,最后通過(guò)類的邊緣區(qū)域?qū)垲惤Y(jié)果進(jìn)行優(yōu)化.

1 算法原理

1.1 密度峰值聚類算法

DPC算法主要分3 個(gè)步驟進(jìn)行:計(jì)算距離矩陣、選取聚類中心、剩余點(diǎn)的分配及優(yōu)化.

1.1.1 計(jì)算距離矩陣

密度峰值算法的輸入為待處理數(shù)據(jù)點(diǎn)的距離矩陣,即每個(gè)點(diǎn)之間相似性.在進(jìn)行距離計(jì)算之前,首先將原始數(shù)據(jù)的不同字段進(jìn)行標(biāo)準(zhǔn)化處理,使各維度的數(shù)據(jù)具有相同的量級(jí);然后計(jì)算數(shù)據(jù)間的距離,最后輸出距離矩陣.本文選取歐幾里得方式來(lái)計(jì)算距離d (xi,xj),并輸出為若干行、三列的矩陣,其中前兩列表示兩個(gè)數(shù)據(jù)點(diǎn)的序號(hào),第三列為前兩列表示的兩個(gè)數(shù)據(jù)點(diǎn)之間的距離,例如矩陣的第1 行為:1 號(hào)數(shù)據(jù)、2 號(hào)數(shù)據(jù)、1 號(hào)2 號(hào)數(shù)據(jù)間的距離,第2 行為:1 號(hào)數(shù)據(jù)、3 號(hào)數(shù)據(jù)、1 號(hào)3 號(hào)數(shù)據(jù)間的距離,以此類推,與此距離矩陣即為快速峰值算法的輸入.

1.1.2 聚類中心的選擇

聚類中心的特征是局部密度大而且與其它密度更大的點(diǎn)相距很遠(yuǎn).

某點(diǎn)的局部密度 ρi是以截止距離為半徑的圓內(nèi)的點(diǎn)的個(gè)數(shù):

式中,i 與 j為兩個(gè)互異的數(shù)據(jù)點(diǎn),當(dāng)a 小于0 時(shí),χ(a)=1,反之χ (a)=0.dij為i 點(diǎn)與 j 點(diǎn)之間的距離,dc為截止距離,由用戶根據(jù)經(jīng)驗(yàn)值設(shè)定.一般而言 dc的選取原則為:將距離 δi按遞增方式進(jìn)行排序并編號(hào),找出所有距離個(gè)數(shù)的1%～2%所對(duì)應(yīng)的序號(hào),將dc設(shè)置為該序號(hào)對(duì)應(yīng)的距離值.

某一數(shù)據(jù)的δi值被定義為:

對(duì)于密度最高的點(diǎn),由于不存在更高點(diǎn),故將其δi值定義為該點(diǎn)與其余所有的數(shù)據(jù)之間距離的最大值.

計(jì)算出各點(diǎn)的這兩個(gè)量之后,將所有的數(shù)據(jù)點(diǎn)以ρ 和 δ 作為兩個(gè)維度進(jìn)行可視化輸出,所輸出的圖形稱為決策圖.

1.1.3 非聚類中心點(diǎn)的分配及優(yōu)化

在找到聚類中心之后,確定類的數(shù)量,然后合理分配剩余點(diǎn).分配原則是:每個(gè)剩余點(diǎn)逐個(gè)被分到與其距離最近的有較高密度的點(diǎn)所在的類簇,且此操作以單步執(zhí)行,直到把所有的點(diǎn)全部分配到對(duì)應(yīng)的類為止.

一般的聚類方法優(yōu)化都是以使目標(biāo)函數(shù)在每一次的迭代中達(dá)到最優(yōu)為原則而實(shí)現(xiàn)的.本文提出的算法中優(yōu)化的方法為:先為每個(gè)類劃分一個(gè)邊界區(qū)域,邊界區(qū)域的定義是分配給某一類簇的點(diǎn)距離另一類簇的點(diǎn)的距離小于截止距離 dc;接著在每個(gè)邊界區(qū)域內(nèi)找出密度最高的點(diǎn)并標(biāo)記其密度為 ρb,遍歷類內(nèi)的各個(gè)點(diǎn),密度大于ρb的點(diǎn)被分到類內(nèi),反之被標(biāo)記為噪聲.

1.2 自調(diào)節(jié)步長(zhǎng)果蠅優(yōu)化算法

1.2.1 果蠅優(yōu)化算法

FOA 模仿果蠅搜尋食物源,果蠅通過(guò)嗅覺(jué)可以輕易的捕捉到范圍內(nèi)目標(biāo)源散發(fā)的氣味,然后利用其視覺(jué)進(jìn)行追蹤,不斷的更新果蠅群位置,逐漸靠近目標(biāo)源.算法的主要步驟如下:

1)初始化種群:

果蠅數(shù)量為 Size_num和算法所需循環(huán)執(zhí)行總次數(shù)Max_times.在確定活動(dòng)區(qū)域中隨機(jī)給定果蠅群體一個(gè)起點(diǎn)Start_X,Start_Y.

2)給每個(gè)果蠅個(gè)體隨機(jī)的方向與距離,用嗅覺(jué)尋找食物:

3)計(jì)算果蠅到坐標(biāo)原點(diǎn)的距離 Di以及味道濃度判別值Si:

4)將濃度判別值 Si帶入判定函數(shù) Function(Si)求出其Smell_i,此處判定函數(shù)為使用果蠅優(yōu)化算法對(duì)某一函數(shù)求解最優(yōu)解時(shí)的判定函數(shù),根據(jù)實(shí)際被求解函數(shù)而定:

5)找出群體中濃度最優(yōu)的果蠅(本文以最小值為最優(yōu)解):

6)保留最佳濃度值Smell_best與其坐標(biāo),果蠅群體根據(jù)視覺(jué)飛往最優(yōu)位置:

7)迭代尋優(yōu):重復(fù)步驟2)、3)、4)、5),判斷:Smell_best_i ＜Smell_best_i-1,如果上式取值為真,則轉(zhuǎn)到步驟6),否則繼續(xù)迭代進(jìn)行優(yōu)化.

1.2.2 自調(diào)節(jié)步長(zhǎng)果蠅優(yōu)化算法(SFO)

傳統(tǒng)的FOA算法的搜索半徑是固定不變的,即每一代果蠅以固定步長(zhǎng)隨機(jī)在尋找食物.在算法迭代開(kāi)始時(shí),較大的步長(zhǎng)有利于全局搜索尋優(yōu),而且可以有效的跳出局部最優(yōu).但是,尋優(yōu)后期,較大的步長(zhǎng)會(huì)導(dǎo)致較弱的局部搜索,可能會(huì)錯(cuò)過(guò)最佳值,同時(shí)收斂精度也會(huì)減小.較小的步長(zhǎng)雖然可以提升收斂度,但是在迭代前期降低了尋優(yōu)速率.傳統(tǒng)的FOA算法難以權(quán)衡全局搜索能力和局部探索能力,自調(diào)節(jié)步長(zhǎng)果蠅優(yōu)化算法根據(jù)濃度差值變化率的大小對(duì)步長(zhǎng)進(jìn)行動(dòng)態(tài)更改;并且在改變步長(zhǎng)過(guò)程中引入指數(shù)與三角函數(shù)機(jī)制,使步長(zhǎng)變化具有非均勻性和隨機(jī)性.在迭代初期為了加快全局搜索速率,適當(dāng)增加步長(zhǎng)值,迭代后期為了能讓算法能對(duì)局部進(jìn)行精細(xì)搜索,適當(dāng)減小步長(zhǎng)值,該算法針對(duì)原果蠅算法的全局尋優(yōu)速率慢和局部收斂精度不高而做出了改良.算法的主要改進(jìn)步驟如下:

本文將最小值設(shè)為最優(yōu)值,將最大值設(shè)為差值.由圖1 可以看出果蠅尋優(yōu)迭代前期的濃度差值變化率變化較大,需要適當(dāng)增加步長(zhǎng)加快全局尋優(yōu),而隨著進(jìn)入迭代后期,濃度差值變化率變小,逐漸趨近于1,并穩(wěn)定在0.7～1.3 的范圍內(nèi),說(shuō)明果蠅群體距離食物源已經(jīng)非?？拷?濃度波動(dòng)較小,這時(shí)需要減小步長(zhǎng),以提升精確度.

2)步長(zhǎng)改進(jìn):根據(jù)SRate的 取值范圍,對(duì)步長(zhǎng)進(jìn)行相應(yīng)的修改:

如果SRate≤0.7 或 者SRate≥1.3:

圖1 濃度差值變化率

步長(zhǎng)調(diào)節(jié)因子:

如果0.7 ＜SRate＜1.3:

步長(zhǎng)調(diào)節(jié)因子:

式中,Li與Li-1分別為當(dāng)前果蠅尋優(yōu)迭代步長(zhǎng)和上一次果蠅尋優(yōu)迭代步長(zhǎng);mup和mdown分別在不同所屬濃度差值變化率時(shí)所采用的步長(zhǎng)動(dòng)態(tài)變化參數(shù),需要增大步長(zhǎng)時(shí)采用 mup(取值大于1,本文取1.3),需要減小步長(zhǎng)時(shí)采用mdown(取值為(0,1),本文取0.7);times_i為當(dāng)前執(zhí)行算法所處的運(yùn)行次數(shù);Maxtimes為算法所需循環(huán)執(zhí)行次數(shù)的最大值.根據(jù)每次求的濃度差值變化率 SRate,確定其所屬范圍,對(duì)步長(zhǎng)進(jìn)行相應(yīng)的修改.

圖2 為步長(zhǎng)調(diào)節(jié)因子在取值連續(xù)的情況下所顯示的結(jié)果.指數(shù)機(jī)制可以使步長(zhǎng)變化具有非均勻性,在果蠅尋優(yōu)迭代過(guò)程中,如果濃度變化較大,那么要適當(dāng)增加步長(zhǎng),非均勻變化的步長(zhǎng)相對(duì)于原果蠅算法中的固定步長(zhǎng)更容易捕捉到最優(yōu)值,有利于全局搜索.

3)果蠅個(gè)體位置計(jì)算:

當(dāng)濃度差值變化率較小時(shí),濃度變化率比較穩(wěn)定,這時(shí)候果蠅迭代尋優(yōu)可能進(jìn)入兩種狀態(tài),第一種狀態(tài)是進(jìn)入迭代后期,要適當(dāng)?shù)臏p小步長(zhǎng)進(jìn)行局部探索,第二種狀態(tài)是果蠅尋優(yōu)迭代陷入局部最優(yōu)化,那么引入三角函數(shù)機(jī)制是利用三角函數(shù)變化的特性,使得步長(zhǎng)變化隨機(jī),提高了算法跳出局部極值的能力.

圖2 步長(zhǎng)調(diào)節(jié)因子變化曲線

在同樣設(shè)置種群規(guī)模為20,最大迭代次數(shù)為1000 時(shí),對(duì)比FOA 和SFO 的測(cè)試性能,采用平均值代表平均精度值,方差代表測(cè)試穩(wěn)定性.對(duì)于不同的測(cè)試函數(shù),FOA 在多數(shù)猜測(cè)是函數(shù)下未能達(dá)到理想精度,容易陷入局部最佳,SFO算法均達(dá)到了目標(biāo)精度,且方差相對(duì)較小,證明本文算法具有更好的穩(wěn)定性和優(yōu)越性.

1.3 基于自調(diào)節(jié)步長(zhǎng)果蠅優(yōu)化的自適應(yīng)密度峰值聚類算法

1.3.1 信息熵

信息熵為系統(tǒng)不穩(wěn)定性的度量.已知空間中的數(shù)據(jù)集 D ={x1,x2,···,xn}包含n 個(gè)數(shù)據(jù),每個(gè)數(shù)據(jù)的密度函數(shù)值為:

則密度估計(jì)可以定義為:

1.3.2 基于自調(diào)節(jié)步長(zhǎng)果蠅優(yōu)化的自適應(yīng)密度峰值聚類

對(duì)小規(guī)模數(shù)據(jù)集進(jìn)行聚類時(shí),密度峰值聚類算法采取指數(shù)方式計(jì)算數(shù)據(jù)密度,計(jì)算公式如下:

對(duì)比式(20)、(22)發(fā)現(xiàn),如果選擇高斯核函數(shù)進(jìn)行每個(gè)數(shù)據(jù)點(diǎn)密度的計(jì)算,截?cái)嗑嚯x參數(shù)dc與σ 具有的意義是統(tǒng)一的,優(yōu)化 σ本質(zhì)上就是對(duì)截?cái)嗑嚯x參數(shù)dc的優(yōu)化.而且,若將整個(gè)數(shù)據(jù)集看成一個(gè)系統(tǒng),一個(gè)好的聚類結(jié)果是系統(tǒng)最穩(wěn)定,數(shù)據(jù)間關(guān)系確定性最好的狀態(tài),因此,以信息熵最小值為判定依據(jù),利用FOA算法的全局尋優(yōu)特性,對(duì) σ進(jìn)行優(yōu)化,優(yōu)化后得出的σ 值即為最優(yōu)的截?cái)嗑嚯x參數(shù)dc.

將式(21)所示的信息熵函數(shù)作為自調(diào)節(jié)步長(zhǎng)果蠅優(yōu)化算法的濃度判定函數(shù) Function(Si)進(jìn)行優(yōu)化,求出最優(yōu) σ值,即截?cái)嗑嚯xdc.按式(1)～(3)計(jì)算得到ρi和δi后,自適應(yīng)的選擇聚類中心.

聚類中心的 ρi和 δi兩 個(gè)值都較大,本文引入γi

則 γi較大的點(diǎn),就很有可能是聚類中心;換言之,聚類中心的 γi一定較大,可以先挑出 γi值較大的點(diǎn),在從中去選擇真正的聚類中心.將 γi值按降序排序.定義臨界點(diǎn) P ,表示γ[1～P]與 γ[P～n]變 化程度最大的點(diǎn),本文用γi值降序排列圖的斜率來(lái)表示其變化程度,則P 服從以下條件:

式中,ki表示第i 個(gè)點(diǎn)和第i +1個(gè)點(diǎn)之間的線段的斜率;α(j)表示在γi值降序排列圖中兩個(gè)鄰居點(diǎn)的斜率差的總和;β表示斜率差的平均值;i是斜率差大于等于均值β的點(diǎn)中序號(hào)最大的點(diǎn)及臨界點(diǎn).

那么聚類中心就可能存在于式(27)表示的范圍內(nèi),稱這個(gè)范圍內(nèi)的點(diǎn)為偽中心.

在同一范圍內(nèi)存在多個(gè)偽中心,因此需要將同一范圍內(nèi)多余的偽聚類中心排除.在密度峰值算法中,聚類中心與密度點(diǎn)更高的點(diǎn)相距較遠(yuǎn),因此,本文取同一區(qū)域中的第1 個(gè)偽中心作為聚類中心,判斷其他的偽中心到該點(diǎn)的距離,若小于d (xi,Nk(xi))則將其消除;如果大于,則將其作為新的聚類中心.在聚類過(guò)程中自適應(yīng)的根據(jù)實(shí)際數(shù)據(jù)選出聚類中心,聚類中心個(gè)數(shù)即為最終聚類數(shù)目.

1.4 算法流程及復(fù)雜度分析

1.4.1 算法流程

?

1.4.2 算法復(fù)雜度分析

假設(shè)果蠅群體大小為S,最大迭代次數(shù)為M,個(gè)體濃度跟新計(jì)算量為O(1),計(jì)算濃度差值變化率所需的時(shí)間復(fù)雜度為O(M),并且動(dòng)態(tài)調(diào)整步長(zhǎng)的時(shí)間復(fù)雜度為O(M),所以計(jì)算最優(yōu)截止距離部分的時(shí)間復(fù)雜度為O((N+2)*M).假設(shè)由自調(diào)節(jié)步長(zhǎng)果蠅優(yōu)化的自適應(yīng)密度峰值聚類算法(Adaptive Density Peak Clustering based on Fruit fly Optimization of Self-adjusting stepsize,SFO-ADPC)處理的數(shù)據(jù)集有N 個(gè)數(shù)據(jù)點(diǎn),則存儲(chǔ)每個(gè)數(shù)據(jù)點(diǎn)與其他點(diǎn)的距離的時(shí)間復(fù)雜度為O(N2),計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的局部密度及距離所需的時(shí)間復(fù)雜度為O(2N),計(jì)算邊界區(qū)域需要的時(shí)間復(fù)雜度為O(N2).綜上,本文所提算法的時(shí)間復(fù)雜度為O((N+2)*M+(N+1)*N).

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

2.1 實(shí)驗(yàn)數(shù)據(jù)集

為測(cè)試所提SFO-ADPC算法的準(zhǔn)確性和有效性,本文選擇了5 個(gè)人工數(shù)據(jù)集和5 個(gè)常用于聚類測(cè)試的真實(shí)數(shù)據(jù)集.表1 中為本文所用數(shù)據(jù)集,包括環(huán)形、月牙形、聚集、火焰、螺旋形、Iris、Wine 和Soybean 數(shù)據(jù)集.5 個(gè)人工數(shù)據(jù)集的數(shù)據(jù)分布情況如圖3 所示,圖中數(shù)據(jù)點(diǎn)橫縱坐標(biāo)均為數(shù)值,無(wú)具體物理意義,故無(wú)單位.

聚集和火焰數(shù)據(jù)是典型的聚類算法性能測(cè)試數(shù)據(jù),環(huán)形、月牙形和螺旋形數(shù)據(jù)為測(cè)試算法能否準(zhǔn)確地對(duì)非球形數(shù)據(jù)聚類的典型數(shù)據(jù)集.Iris 是鳶尾花卉數(shù)據(jù)集,其中有150 個(gè)樣本,屬于3 個(gè)類別,每個(gè)類別有50 個(gè)樣本,每個(gè)樣本具有4 個(gè)屬性,即花萼長(zhǎng)寬以及花瓣長(zhǎng)寬.3 個(gè)類別分別為Setosa,Versicolour 和Virginica.Wine 是酒數(shù)據(jù)集,有178 個(gè)樣本,每個(gè)樣本有13 個(gè)屬性,屬于3 個(gè)類別,每個(gè)類別數(shù)量不同.Soybean 數(shù)據(jù)集是大豆疾病數(shù)據(jù)集,包含47 個(gè)數(shù)據(jù),每個(gè)數(shù)據(jù)包含35 個(gè)屬性,分為4 類,是線性可分的,其所有屬性都可作為分類屬性.Ecoli 數(shù)據(jù)集是大腸桿菌數(shù)據(jù),由336 個(gè)樣本組成,每個(gè)樣本有7 個(gè)屬性,分為8 類.Seeds 數(shù)據(jù)集包含210 個(gè)樣本,每個(gè)樣本有7 個(gè)屬性,每個(gè)樣本分為3 個(gè)類.

表1 實(shí)驗(yàn)數(shù)據(jù)集

圖3 原始數(shù)據(jù)集

2.2 實(shí)驗(yàn)數(shù)據(jù)集

本文主要使用兩個(gè)評(píng)價(jià)指標(biāo)來(lái)測(cè)試所提的算法:內(nèi)部輪廓系數(shù)(Silhouette)和外部F 值(F-measure).

1)Silhouette 指標(biāo)

對(duì)于其中的一個(gè)樣本點(diǎn) i來(lái)說(shuō),需要計(jì)算兩個(gè)量:a(i)與 b (i),

那么i 向量輪廓系數(shù)就如下式:

a(i)i:向量與同一類中每個(gè)點(diǎn)的不相似性的平均值.

b(i)i:向量與其他類的點(diǎn)的不相似性的最小平均值.

使用所有數(shù)據(jù)S 平均值評(píng)估簇的緊密性和可索引性.S 介于-1 和1 范圍內(nèi),對(duì)于同一數(shù)據(jù)集,S 越大聚類越好.

2)F-measure 指標(biāo)

F-measure 是一種結(jié)合準(zhǔn)確率和召回率的外部評(píng)估指標(biāo).對(duì)于真實(shí)類 Pj與聚類所產(chǎn)生的類Ci,分別定義準(zhǔn)確率P (i,j)和召回率R (i,j).其表示為:

P(i,j)和R (i,j)的都介于0 和1 之間,且兩者的數(shù)值大小與相對(duì)應(yīng)的正確率和召回率成正比.

相應(yīng)的F-measure 指標(biāo)計(jì)算:

將各類F-measure 指標(biāo)作平均則可以求出最終Fmeasure 值,其表示為:

上述公式中N 為數(shù)據(jù)總個(gè)數(shù),計(jì)算所得F-measure值越大,則算法準(zhǔn)確程度越高.

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

本文將所提算法SFO-ADPC 與FODPC、DPC、DBSCAN、K-Means 在數(shù)據(jù)集上比較.圖4 中分別為K-Means 在環(huán)形、月牙形、聚集、火焰、以及螺旋數(shù)據(jù)集上的聚類結(jié)果,圖5 中分別為DBSCAN 在環(huán)形、月牙形、聚集、火焰、以及螺旋數(shù)據(jù)集上的聚類結(jié)果,圖6 中分別為DPC 在環(huán)形、月牙形、聚集、火焰、以及螺旋數(shù)據(jù)集上的聚類結(jié)果,圖7 中分別為FODPC在環(huán)形、月牙形、聚集、火焰、以及螺旋數(shù)據(jù)集上的聚類結(jié)果,圖8 中分別為SFO-ADPC 在環(huán)形、月牙形、聚集、火焰、以及螺旋數(shù)據(jù)集上的聚類結(jié)果.

圖4 K-Means算法聚類結(jié)果

測(cè)試算法中使用的數(shù)據(jù)集分布大多為非球形的,K-Means 無(wú)法準(zhǔn)確對(duì)其進(jìn)行聚類,同時(shí),聚集數(shù)據(jù)集雖然是球形分布的,但由于樣本量分布不均勻,K-Means仍然無(wú)法達(dá)到最好的聚類效果.DBSCAN 可以有效地對(duì)測(cè)試數(shù)據(jù)集進(jìn)行聚類,但其參數(shù)確定過(guò)程較為繁瑣,不同的數(shù)據(jù)集的聚類參數(shù)相差較大,用戶需要花費(fèi)大量的時(shí)間用于調(diào)參.

DPC 及其改進(jìn)算法可以有效對(duì)非球形數(shù)據(jù)進(jìn)行聚類,同時(shí)聚類的準(zhǔn)確率大大提高,FODPC 及本文提出的SCFO-ADPC 給出了更好的截?cái)嗑嚯x,克服DPC 需要人工設(shè)置截?cái)嗑嚯x的缺陷;同時(shí),本文算法提供的截?cái)嗑嚯x更好,提升了聚類準(zhǔn)確率.并且,本文所提算法能夠自適應(yīng)的選擇聚類中心,改善了原始DPC算法需要手動(dòng)選取聚類中心的缺陷.

表2 中列出了上述5 種算法在5 個(gè)人工數(shù)據(jù)集及5 個(gè)真實(shí)數(shù)據(jù)集的聚類效果評(píng)價(jià)得分.

圖5 DBSCAN算法聚類結(jié)果

圖6 DPC算法聚類結(jié)果

圖7 FODPC算法聚類結(jié)果

圖8 SCFO-ADPC算法聚類結(jié)果

上述5 種聚類算法應(yīng)用于實(shí)際數(shù)據(jù)時(shí),SCFO-ADPC的準(zhǔn)確率及召回率更高,本文所提算法能有效的對(duì)任何形狀的數(shù)據(jù)進(jìn)行聚類,對(duì)于具有較高維度的數(shù)據(jù)集也可有效進(jìn)行聚類,并且聚類效率及效果有一定提高.

表2 聚類結(jié)果評(píng)價(jià)

3 結(jié)語(yǔ)

本文提出了一種基于自調(diào)節(jié)步長(zhǎng)果蠅優(yōu)化的自適應(yīng)密度峰值聚類算法(SCFO-DPC).SCFO-DPC算法通過(guò)可自調(diào)節(jié)步長(zhǎng)的果蠅優(yōu)化算法得到最佳截止距離,解決了需要根據(jù)人工設(shè)置截止距離參數(shù)的問(wèn)題,并且得到的參數(shù)優(yōu)于其他優(yōu)化算法;能夠自適應(yīng)的選擇聚類中心,有效的解決了人工選擇聚類中心為聚類算法帶來(lái)的不穩(wěn)定性.通過(guò)測(cè)試,SCFO-DPC算法在對(duì)人工數(shù)據(jù)集、UCI 真實(shí)數(shù)據(jù)集的處理上具有相當(dāng)大的優(yōu)越性,比FODPC、DPC、DBSCAN 和K-Means算法更準(zhǔn)確有效,且受人為影響更少.