王芙銀,張德生,張 曉
西安理工大學 理學院,西安710054
隨著互聯(lián)網技術的飛速發(fā)展,隨之產生的數(shù)據也以驚人的速度增加,這些海量的數(shù)據包含著豐富的信息。人們的日?;顒佣伎梢栽谝欢ㄐ问缴狭炕癁閿?shù)據的方式,但這些數(shù)據通常是毫無規(guī)律、雜亂無章的,隨著時間的推移,這些數(shù)據的積累就更加龐大,大數(shù)據的時代也就應運而生。怎樣從這些數(shù)據中獲得有價值的信息就變成了當今時代研究的熱點[1]。
聚類分析[2]在數(shù)據挖掘中扮演著重要的角色,它是無監(jiān)督機器學習的一種,在不需要先驗知識的情況下,根據數(shù)據的分布,計算數(shù)據間的相似性,將數(shù)據劃分成不同的集合,成為類簇。同一類簇間的數(shù)據有著較高的相似性,不同類簇間的數(shù)據有著較低的相似性。按照數(shù)據分布方式以及算法原理,目前常見的聚類算法大體可分為:基于劃分的聚類、基于層次的聚類、基于密度的聚類[3-4]、基于網格的聚類及基于模型的聚類等[3]。其中,基于密度的聚類算法可以在不同數(shù)據中發(fā)現(xiàn)各種形狀及各種大小的簇,其思想是在選定較高密度點后,將周邊與高密度點相近的點聚集為一類。
2014 年意大利學者Rodriguez 和Laio 在Science雜志上提出了一種快速搜索發(fā)現(xiàn)密度峰值聚類算法(Clustering by fast search and find of density peaks),這是一種基于密度的聚類算法,簡稱密度峰聚類算法(Density Peaks Clustering algorithm,DPC)[5]。該算法不需要事先確定類簇的個數(shù),在各種復雜的數(shù)據集中能有效識別出類簇,對噪聲點的識別也有一定的優(yōu)越性,且對于任意形狀的數(shù)據集都能達到很好的聚類效果,適用于大規(guī)模數(shù)據的聚類分析。基于這些優(yōu)勢,DPC算法目前越來越多地被應用于各個領域,其涉及的領域包括機器學習、模式識別、人工智能、圖像處理等多個方面[6]。
鯨魚優(yōu)化算法(Whale Optimization Algorithm,WOA)[7]是Mirjalili等人于2016年所提出的一種新型元啟發(fā)式算法,與其他智能算法相比具有多方面的優(yōu)勢。例如,文獻[7]通過對29 個數(shù)值優(yōu)化問題和6 個工程優(yōu)化問題進行測試,驗證了WOA 算法比模擬退火算法和差分進化算法等元啟發(fā)式算法具有更強的競爭力。另外,如文獻[8]所指出的那樣,與典型的群智能優(yōu)化算法相比,WOA 算法具有原理簡單、調節(jié)參數(shù)少、尋優(yōu)能力強等特點,且在收斂速度與收斂精度方面均明顯優(yōu)于引力搜索算法和粒子群優(yōu)化算法等。除此之外,WOA 算法在求解優(yōu)化問題時表現(xiàn)優(yōu)異,且應用領域廣泛。目前,國內外的研究學者將鯨魚優(yōu)化算法廣泛應用于生產優(yōu)化[8]、負載預測[9]、二次分配[10]、圖像分割[11]、社團檢測[12]等領域,在這些應用領域中,鯨魚優(yōu)化算法發(fā)揮了重要的作用,為各領域的優(yōu)化問題尋求了較好的解。
針對DPC 算法自身所存在的問題,許多學者對其做了相應的改進以適應不同的應用領域。例如,丁志成等人[13]提出一種基于KL 散度的密度峰值算法,該算法提出一種自動選取聚類中心的方法,利用KL 散度的差異性度量準則對聚類中心和非聚類中心進行清晰的劃分,以KL 排序圖中的拐點作為分界點實現(xiàn)對聚類中心的自動選??;文獻[14]在原算法確定類簇中心時,將模糊規(guī)則應用于其中,提出一種Fuzzy-CFSFDP算法,更有利于類簇中心的選擇,同時提高了聚類結果的準確率;文獻[15]提出將網格劃分和圓劃分的方法應用于DPC算法來篩選點,提出了GDPC 算法和CDPC 算法,都有效地降低了算法的復雜度,其中GDPC算法相比于DPC算法的計算時間更短,CDPC算法相對于DPC算法在大規(guī)模數(shù)據集上的準確度更高;杜沛等人[16]提出了基于K近鄰的比較密度峰值聚類算法,該算法結合K近鄰概念重新定義了截斷距離和局部密度的度量方法,對任意數(shù)據集能自適應地生成截斷距離,并使局部密度的計算結果更符合數(shù)據的真實分布,同時在決策圖中引入距離比較量代替原距離參數(shù),使類簇中心在決策圖上更加明顯;蔣禮青等人[17]提出基于近鄰距離曲線和類合并優(yōu)化的聚類算法,此算法利用近鄰距離曲線變化情況自動確定截斷距離,并利用計算值的方法指導類的合并,引入內聚程度衡量參數(shù)解決了類合并后不能撤銷的難題,從而實現(xiàn)對多密度峰值數(shù)據的正確聚類;高詩瑩等人[18]提出了基于密度比例峰值聚類算法,該算法將密度比例引入到密度峰值聚類算法中,通過計算樣本數(shù)據的密度比峰值來提高數(shù)據中密度較小類簇的辨識度,進而提升整體聚類的準確率。
以上幾種改進算法雖然較原DPC算法都具有較好的聚類表現(xiàn),但也存在著一定的問題:(1)沒有很好地克服原算法對截斷距離的依賴性,人為設定截斷距離使得最終的聚類結果具有很大的隨機性和主觀因素,不能保證截斷距離選取的有效性[19-20];(2)在決策圖生成后,需手動選擇聚類中心[19],對于某些數(shù)據集而言,可能會導致聚類中心多選或漏選的情況,這將會直接影響聚類結果。針對以上問題,本文提出了一種結合鯨魚優(yōu)化算法的自適應密度峰值聚類算法(WOA-DPC)。該算法首先根據加權的局部密度和相對距離乘積的斜率變化趨勢實現(xiàn)聚類中心的自動選擇,再建立以ACC 指標為目標函數(shù)的優(yōu)化問題,利用鯨魚優(yōu)化算法(WOA)有效地尋優(yōu)能力對目標函數(shù)進行優(yōu)化,尋找最佳的截斷距離dc。
密度峰值聚類算法(DPC)原理主要依據兩個直觀的假設:(1)聚類中心被一群密度較低的鄰居點包圍著;(2)聚類中心離比它密度更高的點的距離相對較大。該算法只需輸入截斷距離dc這一個參數(shù),通過人工手動選取聚類中心點,然后根據一步分配策略完成對剩余點的聚類和分配。DPC算法中,局部密度的計算有兩種方式,當數(shù)據集較大時,局部密度的計算如下:
當數(shù)據集較小時,局部密度的定義如下:
其中截斷距離:
式中,di為所有數(shù)據點中任意兩點間歐氏距離的升序排列。
定義相對距離為樣本點與最近高密度樣本點之間的距離,如式(5)所示:
DPC算法根據式(4)得出截斷距離dc,再將其代入局部密度ρ和距離δ的計算公式,根據ρ和δ繪制出一個二維空間的決策圖,通過決策圖手動選取出ρ和δ相對較大的值作為聚類中心,最后,根據一步分配策略,將剩余點分配到密度比它高且距離其最近的類簇當中。
WOA算法是通過模擬鯨魚捕食行為而提出的一種新型仿生算法,主要分為三個階段:獵物包圍階段、氣泡襲擊階段、獵物搜索階段[7]。
1.2.1 獵物包圍階段
在這個階段,鯨魚能夠識別獵物的位置并包圍它們以捕獲獵物。此階段鯨魚個體向當前最優(yōu)解移動并更新其位置,該行為的數(shù)學模型[7]如下:
式中,t是當前迭代次數(shù),X*(t) 是目前最優(yōu)解位置,X(t)是當前鯨魚位置,A、C是系數(shù)向量,r為[0,1]之間的隨機數(shù),a為從2到0的線性遞減參數(shù)。
1.2.2 氣泡襲擊階段
在此階段,通過收縮環(huán)繞和螺旋形路徑來設計鯨魚捕食吐氣泡的行為,其數(shù)學模型[7]為:
式中,b是定義對數(shù)螺旋線形狀的常量,l是[-1,1]之間的隨機數(shù)。
假設座頭鯨收縮環(huán)繞和螺旋形位置更新的概率均為50%。建立如下位置更新模型[7]:
式中,變量p是[0,1]之間的隨機數(shù)。
1.2.3 食物搜索階段
當|A|≥1 時,種群個體隨機選擇鯨魚個體作為參照更新其位置,強迫鯨魚個體遠離最優(yōu)參考鯨魚,這樣可以有效增強算法的全局探索能力,數(shù)學模型[7]如下:
式中,Xrand(t)是從當前種群中隨機選擇鯨魚個體。在具體問題優(yōu)化過程中,鯨魚個體根據不同的位置更新方式不斷向最優(yōu)解靠近。
WOA算法具體步驟如下:
步驟1在解空間中隨機初始化S個鯨魚個體位置,給出最大迭代次數(shù)T及當前迭代次數(shù)t。
步驟2通過目標函數(shù)計算每個個體適應度值,并保留最優(yōu)個體為X*(t)。
步驟3更新系數(shù)向量A及隨機數(shù)p,根據A及p的取值情況對所有個體進行相應的位置更新:
當|A|≥1,p <0.5 時,執(zhí)行公式(12)進行位置更新;
當|A|<1,p <0.5 時,執(zhí)行公式(6)進行位置更新;
當p≥0.5 時,執(zhí)行公式(9)進行位置更新。
步驟4計算更新后個體的適應度值,并更新保留最優(yōu)個體位置及最優(yōu)適應度值。
步驟5判斷t <T是否成立,若成立,令t=t+1,轉步驟2;否則,算法結束,輸出最優(yōu)解及最優(yōu)值。
本文主要從以下兩個方面進行改進:首先通過加權的局部密度和相對距離乘積的斜率變化趨勢實現(xiàn)聚類中心的自動選擇;其次,利用鯨魚優(yōu)化算法較強的尋優(yōu)能力對DPC算法中的截斷距離dc進行優(yōu)化。
原DPC 算法在選取聚類中心時,需要在決策圖中手動截取那些局部密度ρ和相對距離δ大的點為聚類中心,而截取過程中帶有一定的主觀性,例如,圖1所示類別數(shù)為7的Aggregation數(shù)據集的聚類決策圖,但從圖中看出同時具有較大的ρ和δ值的點并不容易確定,手動截取容易造成聚類中心個數(shù)選取不準確的問題,若選取聚類中心時出現(xiàn)了錯誤,那么在接下來的數(shù)據點分配類簇上會產生連鎖反應,最終使得聚類效果不理想。
圖1 Aggregation數(shù)據集的聚類決策圖
在實際問題中,也可能存在一些具有較大ρ與較小δ或有較小ρ與較大δ的數(shù)據點也為聚類中心。因此,需綜合考慮局部密度ρ和相對距離δ,定義如下度量:
其中N為數(shù)據集中樣本點個數(shù)。
為避免不同量級間的相互影響,對ρ和δ進行歸一化處理,得到新的γ定義如下:
將經歸一化處理所得到的γi(i=1,2,…,N)進行降序排列,取前40個點。下文中,為了記號方便,仍用γ1,γ2,…,γ40表示由大到小排序后的前40 個γ值。根據γ降序排列圖選取聚類中心,γ值越大的點越有可能是聚類中心,可以有效避免由于單獨考慮ρ和δ所帶來的誤差。然而,對于一些數(shù)據集使用該方法也會存在聚類中心選取不準確的問題。以文獻[5]中使用的類別為5 的GDP數(shù)據集為例,圖2為該數(shù)據集的γ降序排列圖。圖中γ值呈現(xiàn)先快速下降,再趨于穩(wěn)定變化的趨勢,且圖中存在多個拐點。直觀來看γ7之后的值趨于穩(wěn)定,會誤以為聚類中心的個數(shù)為7個,而實際上聚類中心只有5個。因此,僅根據γ降序排列圖有時也很難準確地選取出聚類中心。
圖2 GDP數(shù)據集的γ 降序排列圖
對此,本文將根據γ的斜率來選取聚類中心。一般地,對于歸一化到[0,1] 上的斜率值最大的點可選作聚類中心和其他點的分界點,即將所對應的數(shù)據點選取為聚類中心。但考慮到的前幾個值一般很大且呈現(xiàn)較強的跳躍性,仍不易準確選取聚類中心。如圖2 所示,容易看出γ1到γ2差值最大,而將γ1所對應的數(shù)據點選作聚類中心顯然是錯誤的。因此,這里引入加權的斜率度量如下:
其中,(i-1)可看作權值,隨著i的增大而增大,這樣可使γi值大的點擁有較小的權值,而γi值小的點擁有較大的權值,以降低前面一些過大值對聚類中心選取的影響,從而實現(xiàn)了聚類中心的自適應準確選取。綜上,本文所提的聚類中心選取策略分為兩步:
(2)將降序排列的前i0個γ值所對應的數(shù)據點選為聚類中心。
根據公式(15)得到的ki值描點作圖,稱其為加權γ斜率變化趨勢圖。圖3 為GDP 數(shù)據集的加權γ斜率變化趨勢圖。由此易知k5最大,故聚類中心個數(shù)為5,且將前5個γ值所對應的數(shù)據點選為聚類中心,解決了利用公式(14)選取聚類中心的問題。類似地,圖4、圖5分別為Spiral數(shù)據集和D31數(shù)據集利用公式(14)和(15)選取聚類中心的效果對比圖。由圖4(b)易知聚類中心個數(shù)為3,這和Spiral數(shù)據集的類別數(shù)3是一致的,而由圖4(a)在γi值趨于穩(wěn)定前會誤以為聚類中心的個數(shù)為5。雖然D31數(shù)據集的類別數(shù)較多,為31個,但由圖5(b)亦可準確選取出聚類中心的個數(shù)。此外,通過大量模擬試驗表明,利用公式(15)對大部分數(shù)據集均可客觀選取出聚類中心的個數(shù)。
圖3 GDP數(shù)據集的加權γ 斜率變化趨勢圖
圖4 Spiral數(shù)據集的聚類中心選取效果對比圖
圖5 D31數(shù)據集的聚類中心選取效果對比圖
原DPC 算法中截斷距離dc需要人為設定,且取值較為敏感。為了更直觀地反映此問題,以圖6中給出的R15數(shù)據集所得到的聚類結果圖為例,可以得出,dc的細微不同所得到的聚類結果存在較大的差異。因此,對截斷距離dc進行優(yōu)化就變得很有必要。
圖6 不同dc 所對應的聚類結果圖
本文利用WOA 算法較強的尋優(yōu)能力,來選取最佳的截斷距離dc。ACC 指標[21-23]是廣泛應用于統(tǒng)計學和信息檢索領域的評價指標,對聚類結果能夠產生準確的評判,假設Pj為已知人工標注的簇,Cj為經過聚類后的簇,則ACC指標的計算公式如下:
在優(yōu)化過程中,以ACC指標作為WOA算法的目標函數(shù),對DPC算法中的截斷距離dc進行優(yōu)化,所選取的目標函數(shù)ACC 指標是關于dc的一維函數(shù),即給定一個dc便可得到一個ACC 指標值,ACC 指標的取值范圍在[0,1]之間,其值越接近于1,說明聚類結果越好。
利用WOA算法多次迭代尋優(yōu),找出使DPC算法中ACC指標最大時的dc作為當前數(shù)據集最優(yōu)的dc,從而實現(xiàn)算法的聚類。
本文所提出的WOA-DPC算法的基本思想:首先根據γ的斜率變化趨勢圖選取聚類中心,從而避免了聚類中心需要手動選擇的缺陷;其次,將鯨魚優(yōu)化算法和聚類中心自適應的密度峰值聚類算法根據ACC指標函數(shù)有效地結合起來,對參數(shù)dc進行了優(yōu)化,克服了DPC算法對參數(shù)選取敏感的缺陷。算法具體步驟如下,流程圖如圖7所示。
輸入:實驗數(shù)據集U(x)={x1,x2,…,xn}。
輸出:聚類結果H={h1,h2,…,hm},m為數(shù)據集聚類結果類別數(shù)。
步驟1設置WOA算法的種群規(guī)模為S,最大迭代次數(shù)T。
步驟2數(shù)據預處理,計算數(shù)據集中樣本間的歐氏距離,確定dc的取值范圍。
步驟3初始化WOA算法的種群位置,即dc的值。
步驟4將dc代入式(3)及式(5)中,分別計算出所有點的局部密度ρi與相對距離δi。
步驟5根據式(15)得到γ斜率變化趨勢圖,并自動選取聚類中心。
步驟6引入如式(16)所示的評價指標ACC 作為WOA 的目標函數(shù),記ACC 指標最大時所對應的dc為。
步驟7利用WOA算法更新dc。
步驟8判斷WOA算法是否滿足迭代終止條件,若是,則結束迭代并轉步驟9。若否,則跳轉至步驟4繼續(xù)優(yōu)化尋優(yōu)。
步驟9將最優(yōu)截斷距離dc所對應的聚類結果進行除噪,得到最終聚類結果,完成聚類。
圖7 WOA-DPC算法流程圖
對于含有N個樣本點的數(shù)據集,DPC 算法的時間復雜度主要來自計算樣本點間的距離矩陣D的復雜度O(N2),對歐氏距離進行快排的復雜度O(N2lbN),計算局部密度ρ和最短距離δ的復雜度O(N2)組成。對于本文所提WOA-DPC 算法,算法復雜度主要體現(xiàn)在優(yōu)化過程。假設鯨魚群體規(guī)模為S,最大迭代系數(shù)為T,優(yōu)化截斷距離dc問題時維度為1,故優(yōu)化dc的復雜度為O(S·T)。在優(yōu)化過程中,由于dc的變化會導致局部密度ρ和相對距離δ的改變,故此過程的復雜度為O(N2·T)。綜上,本文所提算法的時間復雜度為。
為了評估本文所提算法的可行性和有效性,采用如表1所示的9個數(shù)據集對其進行驗證。
表1 人工合成數(shù)據集以及UCI數(shù)據集描述
為避免重復使用ACC 指標,本實驗采用FM 指數(shù)(FMI)、調整蘭德系數(shù)(ARI)和調整互信息(AMI)[21-23]三個評價指標來對各算法的聚類結果進行評估。假設C代表樣本真實標簽,C*代表聚類產生的結果。
(1)FMI指標
FMI是成對精度與召回率的幾何均值,定義式如下:
其中,a表示在C和C*中屬于同一類數(shù)據點的對數(shù),b表示在C中屬于同一類但在C*中不屬于同一類的數(shù)據點的對數(shù),c表示在C*中屬于不同類但在C中屬于同一類的數(shù)據點的對數(shù)。FMI 指標的取值范圍是[0,1],其數(shù)值越大代表聚類效果越好。
(2)ARI指標
蘭德指數(shù)(RI)的定義式為:
式中,a代表在C和C*中屬于同一類數(shù)據點的對數(shù),b代表在C*中屬于不同類但在C中屬于同一類的數(shù)據點的對數(shù),代表數(shù)據集中可組成總元素的對數(shù)。使用RI指標時,不能保證類別標簽在隨即分配的情況下,其值接近0。故引入調整蘭德指數(shù)(ARI)來解決這一問題,ARI指標的定義式為:
其中,E(RI) 表示RI 的數(shù)學期望,ARI 的取值范圍為[-1,1],值越大表示聚類結果越精準。
(3)AMI指標
與ARI 相似,AMI 也是一種常見的聚類評價指標,它的定義式為:
式中,H(A),H(B)表示兩個類別標簽的熵,AMI是基于互信息(MI)來衡量聚類效果的類別信息,E(MI)表示MI 的數(shù)學期望。AMI 的取值范圍是[-1,1],值越接近于1,表示聚類結果越好,即與真實結果越吻合。
對表1 所給出的數(shù)據集,使用WOA-DPC 算法與DPC 算法、DBSCAN 算法和K-Means 算法對其進行聚類,圖8~10 分別為四種對比算法在Spiral、Aggregation和Flame三種人工數(shù)據集上聚類效果圖,這三種數(shù)據集的總體分布情況和聚類的數(shù)目是截然不同的,它們可以更直觀地反映出四種聚類算法的聚類性能。圖中顏色不同的點被分配到不同的類簇中,其中,藍色星形表示聚類中心點,叉形表示噪聲點。
圖8 四種算法在Spiral數(shù)據集上的聚類效果圖
圖9 四種算法在Aggregation數(shù)據集上的聚類效果圖
圖10 四種算法在Flame數(shù)據集上的聚類效果圖
從圖8 對Spiral 數(shù)據集的螺旋形聚類效果圖中看出,除K-Means 算法外,其他三個算法均能夠準確地對其進行聚類,K-Means 算法的聚類結果出現(xiàn)明顯的錯誤,它將該數(shù)據集平均分為了三部分,且將每個部分的中心當作聚類中心。盡管K-Means 算法在該數(shù)據集上得到了正確的聚類數(shù)目,但無法進行正確的聚類,這表明K-Means 算法不能很好地對非凸分布的數(shù)據進行聚類。同時,其余三種算法均得到了正確的聚類結果,也可明顯可看出WOA-DPC 算法比DPC 算法的聚類中心的識別更為準確。
在圖9 的Aggregation 數(shù)據集聚類效果圖中,WOADPC算法和DPC算法均得到了正確的類簇,WOA-DPC算法也更精準地識別了聚類中心點。DBSCAN 算法雖然能夠識別出正確的聚類數(shù)目,但其中某些點被其標記為了噪聲點,導致聚類效果略差。而K-Means算法在一個集群中出現(xiàn)了兩個聚類中心,并出現(xiàn)了在三個藍色類簇之間選擇聚類中心的情況。從而使得聚類結果產生了較大的錯誤。因此,WOA-DPC算法能夠準確地識別出聚類中心,并有效地優(yōu)化了dc,從而得到了更加精準的聚類結果。
從圖10 的Flame 數(shù)據集的流形聚類效果圖可知,WOA-DPC 算法、DPC 算法和DBSCAN 算法都可正確地識別聚類數(shù)目,而DBSCAN 算法將左上邊的兩個點識別為了噪聲點,導致聚類準確率降低。K-Means算法將本該屬于紅色類簇的點分配給了綠色類簇,以使整個數(shù)據集看起來像是從對角線斜率切開的,從而產生了錯誤的聚類結果。因此,可以看出WOA-DPC算法不僅能夠得到正確的聚類數(shù)目,而且可以更精準地識別出聚類中心的位置,從而得到更佳的聚類效果圖。
表2 給出了WOA-DPC 算法與其他對比算法在各數(shù)據集上的聚類評價指標值。圖11~13 分別為四種算法在各種數(shù)據集上的指標對比圖。從表2 所得的評價指標值可以看出,通過對聚類中心選取策略改進和利用鯨魚優(yōu)化算法對截斷距離的優(yōu)化,WOA-DPC算法對九種數(shù)據集進行聚類所得的FMI、ARI和AMI指標值均得到了更好的結果。在Spiral 數(shù)據集和Flame 數(shù)據集中,WOA-DPC 算法和DPC 算法的聚類指標值都為1,而在其他幾個數(shù)據集上DPC 算法的聚類表現(xiàn)略差于WOADPC 算法,但優(yōu)于K-Means 算法。尤其在Jain 數(shù)據集中,WOA-DPC算法相較于DPC算法的AMI指標值提高了大概40%。DBSCAN 算法在九種數(shù)據集的聚類表現(xiàn)中,Spiral 數(shù)據集的聚類指標為1,表明對其聚類效果良好,在Jain數(shù)據集上,DBSCAN算法表現(xiàn)優(yōu)于DPC算法,而在另外七種數(shù)據集中,其聚類效果均差于WOA-DPC算法和DPC算法。K-Means算法在四種對比算法中,整體表現(xiàn)差于其他三種算法。同時,在維數(shù)比較大的Seeds和Waveform 數(shù)據集中,WOA-DPC 算法的準確率也較其他三種算法有了較大的提高,說明本文所提算法無論對于高維數(shù)據集還是低維數(shù)據集都有較好的聚類結果。
表2 WOA-DPC算法與其他算法的聚類結果比較
圖11 四種算法的FMI值對比圖
圖12 四種算法的ARI值對比圖
圖13 四種算法的AMI值對比圖
從圖11~13 中可以更直觀看出,WOA-DPC 算法不論是在人工數(shù)據集還是UCI 數(shù)據集上的聚類指標值明顯高于其他三種對比算法。相對于原DPC 算法,本文算法避免了人為設定截斷距離和手動選取聚類中心的缺陷,其聚類效果也遠遠優(yōu)于DPC算法。
本文針對DPC 算法存在的問題,從聚類中心自適應和優(yōu)化截斷距離兩個方面進行了改進。
(1)首先,引入局部密度和距離的乘積γ,來擴大聚類中心的選取范圍。其次,根據γ的加權斜率變化趨勢來選取正確的聚類中心個數(shù),從而實現(xiàn)聚類中心的自動選取。
(2)利用鯨魚優(yōu)化算法較強的尋優(yōu)能力來優(yōu)化截斷距離dc,將ACC 指標作為目標函數(shù),針對不同的數(shù)據集,尋找出使聚類準確率指標值最大時所對應的dc,從而避免了聚類結果對截斷距離dc較為敏感的問題。
通過實驗驗證,本文算法相較于原算法,不僅避免了人工選取截斷距離dc和手動選取聚類中心的缺陷,而且具有更高的準確率和更優(yōu)的聚類結果。下一步的研究目標是針對DPC對高維數(shù)據集聚類效果不佳和對剩余點的分配策略容錯性較高的問題進行改進,使其更好地應用于復雜結構的數(shù)據集。