基于核KMeans和SOM神經網絡算法的海況聚類分析

陳曉曼, 蘇 歡

(哈爾濱工業大學(威海) 理學院, 山東 威海 264209)

0 引言

海況是海洋與大氣、海洋與海冰之間耦合的關鍵組成部分,對海上的運輸、生產和海洋資源的開發使用等有著至關重要的作用[1,2].研究者們[3-6]通常使用有效波高作為海洋活動中海況的使用指標,而海況對于船舶的影響往往是多種海況參數非線性耦合的結果.Dodet等[7]表示在未來的研究中,多源數據的使用將為復雜現象提供更加完整的描述.海況數據用戶在研究和工程應用中仍然主要依賴于數值波浪模型[8],為了能夠更加合理且高質量地使用海況數據,考慮利用機器學習方法對海況參數進行聚類,從而得到更加全面可靠的結果.

目前國內外有一些研究通過數據挖掘對海況參數進行聚類和智能識別從而實現航速優化[9-11].王壯[12]利用KMeans算法對海況數據進行聚類,智能地根據不同海況采用最佳經濟航速,實驗結果表明該方法能夠有效地實現航速優化.然而KMeans聚類算法對于高維非線性數據的聚類效果并不理想,故而對于實現海況參數聚類的方法也還有待改進.

在眾多的聚類算法中KMeans[13]聚類算法應用最為廣泛,自組織映射(Self-organizing Mapping,SOM)神經網絡算法是全局排序的且被認為對于任意數據具有魯棒性[14].為克服KMeans算法難以處理復雜數據的不足,有學者提出利用核方法將數據嵌入高維流形,將歐氏距離替換成非線性核距離來衡量相似度[15-17].因此本文基于KMeans、SOM神經網絡算法、核技巧,構建了自組織映射混合核KMeans(SOM-Gaussian and Polynomial Kernel-KMeans,SGPK-Kmeans)算法.針對單核KMeans無法全面準確地反映數據內在聯系的問題,將高斯核函數與多項式核函數進行線性組合,得到兼顧學習能力和泛化能力的混合核KMeans來更合理的描述數據的內部聯系從而提升聚類效果;由SOM神經網絡算法確定混合核KMeans的初始聚類中心以及聚類數目,可以有效避免隨機選擇初始聚類中心導致的聚類效果不穩定以及易陷入局部最優的問題.

本文構建了SGPK-KMeans聚類算法,使用夏威夷群島北部的浮標,以1小時為分辨率選取從2021年1月到12月的數據共8 588組進行海況參數的聚類分析,并綜合考慮SC(Silhouette Coefficient)分數、CH(Calinski Harabaz)分數以及DBI(Davies Bouldin Index)指數對聚類的效果進行評估.實驗表明,使用SGPK-KMeans算法對數據進行聚類所得到的聚類評估效果最好,從而本文構建的算法可以為海況的智能識別、航速優化提供更加全面準確的聚類結果,也可以為其他受海況影響的應用提供更加可靠的海況聚類結果.

1 預備知識

1.1 KMeans算法

KMeans是一種基于劃分的聚類算法,旨在最小化數據點和聚類中心之間的平均平方距離[18].該聚類方法的思想可以歸結為對樣本集合X={x1,x2,…,xn}的劃分,xi(i=1,2,…,n)表示數據集中第i個樣本數據.通常使用歐氏距離作為距離度量.但該方法在復雜和未知形狀組織的數據中表現得并不理想[19].KMeans通過最小化損失函數:

(1)

1.2 核函數

定義1[20]設χ是輸入空間,H是特征空間,若存在映射φ(y):χ→H使得對于任意y,z,∈χ,函數κ(y,z)滿足κ(y,z)=φ(y)·φ(z),則稱κ(y,z)為核函數,φ(y)為映射函數,式中·表示內積運算.

定義2[21]令χ為輸入空間,κ(·,·)是定義在χ×χ上的對稱函數,若κ是核函數,對于任意數據x=(x1,x2,…,xm),稱矩陣:

為核矩陣.由文獻[20]知,只要一個對稱函數對應的核矩陣半正定,該函數就可以作為核函數使用.常用的核函數有多項式核函數:

κ(y,z)=(βy·z+γ)p

(2)

高斯核函數:

(3)

定理1假設κ1,κ2是核函數,λ∈(0,1),那么λκ1+(1-λκ2)也是核函數.

證明:由κ1,κ2均為核函數,知κ1,κ2均為對稱函數且生成的核矩陣K1,K2半正定,則

κ(xi,xj)=λκ1(xi,xj)+(1-λ)κ2(xi,xj)=λκ1(xj,xi)+(1-λ)κ2(xj,xi)=κ(xj,xi)

即κ(xi,xj)是對稱函數,下證該對稱函數對應的矩陣K半正定.

由于K=λK1+(1-λ)K2,其中K1,K2半正定且λ∈(0,1),故對稱函數κ對應的矩陣K半正定,從而由定理知該函數是核函數.

若核函數選取不當,會將輸入空間映射到不恰當的特征空間使得聚類效果不佳.高斯核函數學習能力較強泛化能力較弱;多項式核函數學習能力較弱泛化能力較強.基于此,考慮將高斯核函數與多項式核函數相結合,使用這兩種核函數的線性組合生成新的核函數構造核矩陣,能夠同時保證算法的學習能力和泛化能力,從而提升聚類效果.本文構造的核函數為:

(4)

式(4)中:λ∈(0,1).

1.3 SOM神經網絡算法

SOM神經網絡算法是芬蘭的Kohonen教授[22]提出的一種由全連接的神經元列陣組成的神經網絡理論,神經網絡的輸入層和競爭層之間通過權重向量實現全連接.能夠根據輸入空間中數據集的概率分布密度形成與此概率密度相對應的輸出的分布關系[23].在學習過程中,競爭層的神經元節點通過相互的側向交互作用競爭成為與輸入神經元節點最相似的那個節點,相似度最高的節點為獲勝神經元.獲勝神經元會根據權重調整公式進行更新調整,周圍的神經元也會受到其影響調整權重,故而SOM神經網絡算法在實現聚類的同時保持了輸入空間的拓撲結構.SOM神經網絡通過大量神經元同時作用,容錯性好、魯棒性強,但是網絡結構比較固定,可能會出現“死神經元”.SOM神經網絡拓撲結構如圖1所示.

圖1 SOM神經網絡拓撲結構圖

2 SGPK-KMeans算法

2.1 核KMeans算法

KMeans聚類算法能夠很好的確定線性聚類邊界,但當簇間的邊界為非線性的復雜形狀時,該聚類算法不能很好地發揮作用.因此,引入非線性變換,將數據集映射到高維特征空間,在高維特征空間利用KMeans聚類,便能得到更好的聚類結果.通過核函數,隱式地實現了從低維到高維的映射,巧妙地避開了非線性映射φ的顯式選取.核KMeans算法以核距離:

(5)

取代原本的歐氏距離,其中xi,xj是輸入的第i,j個樣本數據,κ(·,·)是核函數.相應的要求解的最優化問題轉換為:

(6)

其中φ是非線性映射,滿足:

κ(xi,xj)=<φ(xi),φ(xj)>.

(7)

核KMeans算法克服了KMeans算法只能處理超球形數據的不足,但是該算法仍然需要事先確定聚類數目且對于初始聚類中心十分敏感,隨機選取的初始聚類中心有可能使得KMeans算法陷入局部最優.

2.2 SGPK-KMeans算法

將SOM神經網絡算法引入核KMeans,由SOM神經網絡算法確定初始聚類中心和k值,從而克服核KMeans不能確定聚類數目和初始聚類中心選取不當的不足.對于k值的確定,綜合考慮了三種聚類內部評價指標:SC分數、CH分數以及DBI指數.

SC分數為:

(8)

式(8)中:a(i)表示向量i到它所屬簇中所有其他點的距離的均值,b(i)表示向量i到它不屬于的簇中所有點的平均距離的最小值,聚類結果總的SC分數是將所有點的SC分數求平均.由公式可知當SC分數越接近1說明聚類效果越好.

CH分數為:

(9)

式(9)中:h為簇的數目,N為輸入空間中樣本的個數,Bh為簇間色散矩陣,Wh為簇內色散矩陣,Bh,Wh公式如下:

(10)

式(10)中:Cl為簇l中點集,nl為簇l中的點數,cl為簇l的中心,c為E的中心,x為cl中的數據.由公式可知若簇內數據的協方差越小,簇間的協方差越大,則CH分數越大,說明聚類效果好.即聚類結果中同類別的樣本距離近,不同類別的樣本之間距離遠.

DBI指數為:

(11)

2.3 算法實現流程

SGPK-KMeans算法具體實現如下:

(1)對于輸入空間數據X={x1,x2,…,xn}使用SOM神經網絡算法,依據肘部法綜合考慮三種聚類評價內部指標:SC分數、CH分數以及DBI指數確定聚類數目和初始聚類中心.

(2)根據第(1)步得到的結果,初始化核KMeans算法的聚類數目h及初始聚類中心c1,c2,…,ch.

(4)將xj,j=1,2,…,n劃分到與之距離最小的聚類心所屬的類別中,計算每一個類別中所有數據點的均值作為新的聚類中心,不斷更新聚類中心及每個類.

SGPK-KMeans算法實現流程如圖2所示.

圖2 SGPK-KMeans聚類流程圖

3 海況聚類實驗及結果分析

3.1 實驗描述及數據預處理

為了實現海況的聚類并驗證提出算法的有效性,本文采取來自美國國家資料浮標中心的夏威夷群島北部地理位置(23.528 N,153.792 W)的浮標從2021年1月到2021年12月共8 588組數據(以1小時為時間分辨率)進行聚類(部分數據如表1所示).該數據集有八個特征,分別為:風向、風速、波高、陣風、大氣壓力、空氣溫度、水溫、露點溫度.由于特征量綱不同,在進行聚類前需要先對數據進行無量綱化,本文采用的無量綱化處理是Z-Score標準化.具體過程通過Python實現.

表1 部分實驗數據

3.2 SOM神經網絡聚類

利用SOM神經網絡算法,綜合考慮CH分數、SC分數以及DBI指數,得到聚類數目以及聚類中心,其中聚類數目確定為12.三種評估指標部分結果如表2所示,折線圖如圖3、圖4所示.

表2 SOM算法得到的部分評估指標結果

圖3 CH分數評估指標結果

圖4 SC分數及DBI指標評估結果折線圖

根據確定聚類數目的拐點檢測原理,本文利用機器學習中投票法的思想認為當兩個指標同時達到拐點且第三個指標值處于所有該值的均值以上水平時,選擇此時的k值作為聚類數目,相應的聚類中心為初始聚類中心.由表2及圖3、4知,CH分數、DBI指數在k取12時達到拐點且SC分數的值高于所有SC分數的均值,故可確定聚類數目為12.

3.3 核KMeans聚類

分別利用傳統KMeans算法、高斯核KMeans算法、多項式核KMeans算法、混合核KMeans算法以及SGPK-KMeans算法進行聚類,并將五種方法以及SOM神經網絡得到聚類結果的SC分數、CH分數以及DBI指數進行對比.其中由于KMeans和混合核KMeans初始聚類中心是隨機選取的,為避免偶然性,取七次評估平均值作為最終評估結果.表3是七次KMeans聚類評估結果,表4是七次高斯核聚類評估結果,表5是七次多項式核聚類評估結果,表6是混合核KMeans七次聚類評估結果,表7是6種不同聚類算法三個評估指標的比較結果,表8、表9分別是使用KMeans算法和SGPK-KMeans算法得到的各聚類類別數目.

3.4 結果分析

由表7可知,對于本文所用數據,高斯核KMeans聚類效果差于經典的KMeans算法和SOM神經網絡算法,說明樣本被映射到了不合適的特征空間.多項式核KMeans比經典KMeans聚類算法和SOM神經網絡算法以及高斯核KMeans相比都有了很大改善,說明多項式核函數映射得到的特征空間是合理的,能夠提升聚類效果.兼顧了學習能力和泛化能力的混合核KMeans的CH分數相比于多項式核函數提升了1.56%,DBI指數效果改善了6.02%,SC分數沒有提升但相差很小,說明該核函數的設計是合理的,聚類效果有所提升.本文提出的SGPK-KMeans的聚類效果是這六種方法中最好的,三種指標均優于前五種方法,其中CH分數比傳統KMeans方法提升了一倍左右,比經典SOM神經網絡算法提升了1.57%,比混合核KMeans提升了0.53%;SC分數比傳統KMeans提升了8.09%,比經典SOM神經網絡算法提升了17.19%,比混合核KMeans提升了5.03%;DBI指數比傳統KMeans改善了9.92%,比經典SOM神經網絡算法改善了2.68%,比混合核KMeans改善了2.79%,因此本文提出的方法是有效且合理的.

表3 KMeans七次聚類評估結果

表4 高斯核KMeans七次聚類評估結果

表5 多項式核KMeans七次聚類評估結果

表6 混合核KMeans七次聚類評估結果

表7 6種算法聚類評估指標對比

表8 KMeans得到的各類別樣本數目

表9 SGPK-KMeans得到的各類別樣本數目

由表8、表9分別得到了使用KMeans和SGPK-KMeans聚類得到的每個類別樣本的數目,通過觀察表9發現其中類別1、類別2、類別3以及類別9的樣本數目較少,返回到原數據發現類別1中數據空氣溫度特征和露點溫度特征數據存在異常;類別2中數據的三個特征:風速、風向、陣風存在異常;類別3中波高特征數據存在異常;類別9中水溫特征數據存在異常,其余類別中數據均無異常.對比KMeans聚類得到的結果,發現KMeans算法不能有效的識別出異常值,聚類效果要差于SGPK-KMeans.一方面,這說明了SGPK-KMeans聚類的有效性以及準確性,能夠將某一個特征或者某幾個特征有異常的數據聚在一起;另一方面,也為海況的識別提供了更多的背景情況.因此聚類得到的12個類別中有4類相當于對有異常值的數據進行了聚類,其余的8類為正常數據的海況聚類結果,即利用海洋的風速、波高等數據,應用本文提出的聚類方法,將海況分成了8類.

結合以上的實驗和分析可以得出結論:SGPK-KMeans算法在聚類效果和異常值檢測方面可以得到更加優化的結果,能夠有效的應用于海況數據的聚類中,滿足實際應用的需要.

4 結論

本文構造的SGPK-KMeans算法的聚類性能確實優于高斯核KMeans以及多項式核KMeans且顯著優于傳統KMeans聚類算法以及經典SOM神經網絡算法.SGPK-KMeans算法對于海況數據的聚類結果更加穩定,而且還能有效的識別出數據中的異常值.應用所提聚類方法于海況聚類中,利用海面數據,將無異常值的真實海況聚成了8類,可以為海況的智能識別、異常值檢測以及航速優化等提供更加全面準確的聚類效果.