鄧然然,李 偉,楊榮新

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

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

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

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

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

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

1 算法原理

1.1 密度峰值聚類算法

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

1.1.1 計算距離矩陣

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

1.1.2 聚類中心的選擇

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

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

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

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

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

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

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

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

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

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

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

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

1)初始化種群:

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

2)給每個果蠅個體隨機的方向與距離,用嗅覺尋找食物:

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

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

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

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

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

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

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

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

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

如果SRate≤0.7 或 者SRate≥1.3:

圖1 濃度差值變化率

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

如果0.7 ＜SRate＜1.3:

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

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

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

3)果蠅個體位置計算:

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

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

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

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

1.3.1 信息熵

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

則密度估計可以定義為:

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

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

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

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

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

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

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

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

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

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

1.4.1 算法流程

?

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

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

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

2.1 實驗數(shù)據(jù)集

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

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

表1 實驗數(shù)據(jù)集

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

2.2 實驗數(shù)據(jù)集

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

1)Silhouette 指標(biāo)

對于其中的一個樣本點 i來說,需要計算兩個量:a(i)與 b (i),

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

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

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

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

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

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

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

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

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

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

2.3 實驗結(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é)果

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

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

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

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

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

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

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

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

表2 聚類結(jié)果評價

3 結(jié)語

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