基于改進K均值聚類的戰術導彈試驗數據分析

黃偉愷，馬 行，劉 進，李宇平，鄭丹力

(上海機電工程研究所，上海 201109)

0 引 言

開展戰術導彈振動及應力篩選試驗時，通常是在比較寬的頻率范圍內對導彈施加振動，使導彈的多個共振點同時受到激勵而產生共振，從而發現扭曲、碰撞等作用可能對導彈造成的損壞，盡早暴露產品的早期設計缺陷。因此，針對戰術導彈的振動及應力篩選試驗開展試驗數據分析工作，可以為戰術導彈的研制以及相關測試系統的改進提供分析依據或建議。

在試驗數據中，由于系統誤差、人為誤差或者數據變異等原因，部分試驗數據與總體試驗數據的行為特征、結構或者相關性不一致，則稱該部分試驗數據為異常試驗數據。通常，對異常試驗數據的篩查方法主要包括：基于統計的方法[1]、基于距離的方法[2]、基于偏度的方法[3]以及基于聚類的方法[4]。其中，聚類方法的復雜度低、效率較高，比較適用于數據量較大的異常試驗數據篩查。

K均值聚類算法在數據挖掘領域應用較為廣泛，但是，基本K均值算法在具體工程應用上有一些局限性，例如初始聚類中心選擇的隨機性、容易陷入局部最優等。很多學者致力于解決基本K均值聚類的缺陷：①陶瑩[5]采用全局化思想改進了K均值聚類算法，通過對比分析驗證了算法的穩定性，但是沒有解決K=1時初始聚類中心的隨機性問題，并且算法迭代過程效率不高；②馬晨光[6]建立了基于遺傳K均值算法的聚類分組模型，實現了聚類過程分組數目的自動學習，但沒有實現異常數據的檢測；③陳永波[7]改進了K均值聚類初始聚類中心的選取方法，在一定程度上解決了局部最優的問題，提高了動態心電分析的準確性和效率，但是所提出的改進K均值聚類算法不具備普適性；④由于試驗數據是典型的時間序列，霍緯綱[8]提出了一種基于升力系數 (lift ratio, LR)分量提取的多維時間序列 (multivariate time series, MTS)聚類算法，采用K均值算法對模型向量集進行聚類分析；⑤張乾君[9]針對多雷達數據融合問題，提出了基于時間序列的模糊聚類算法，解決了跟蹤目標較多算法效率低的問題。

本文針對戰術導彈振動及應力篩選試驗數據的分析和處理問題，對K均值聚類算法的缺陷進行分析，以期從大數據量的試驗數據中發現蘊含價值的潛在規律，從而實現戰術導彈試驗數據的自動化處理和分析。

1 K均值聚類算法原理和局限性分析

1.1 K均值聚類算法的基本原理

K均值聚類算法的基本原理如下：

1) 隨機指定K個數據點作為算法的初始簇中心；

2) 計算數據集中所有數據點與初始簇中心的相似度，把各個數據點歸入最相似的簇；

3) 根據被歸入的數據點，重新計算各簇中心；

4) 反復迭代2)、3)，至滿足收斂條件。

K均值聚類算法復雜度低，若以歐氏距離作為數據點的相似度測度，算法復雜度可表達為O(t·K·n·d)。其中：n為數據集的大小；K為聚類中心個數；d為數據的維度；t為迭代次數。通常，取t、K、d為常量，所以算法復雜度可簡化為O(n)。

1.2 K均值聚類算法的局限性

K均值聚類算法存在以下缺陷：

1) 隨機選擇的初始簇中心對聚類結果影響巨大。如圖 1所示，(a)和(b)對應的聚類結果較(c)和(d)對應的聚類結果要好，這是因為(a)和(b)所選擇的初始簇中心更接近真正的簇中心。通過上述對比可知，選擇初始簇中心不合適會導致聚類結果存在較大誤差。

2) 異常試驗數據對聚類結果也存在重大影響。

圖1 初始簇中心對K均值聚類結果的影響Fig.1 The influence of initial cluster center on K-means clustering

試驗數據中存在的異常數據會干擾聚類中心的計算，進而影響聚類結果。

3) 隨機選擇的K值對聚類結果影響較大。不同的初始值K可能導致數據點被分配到不同的簇中，從而導致結果非確定。

2 異常試驗數據篩查方法

2.1 改進K均值聚類算法

為了解決初始簇中心的隨機性問題，應遵循以下原則選擇初始簇中心：避免選擇異常數據點；在高密度且均勻分布區域內進行選擇。

改進K均值聚類算法的流程如圖 2所示。為選取合格的初始簇中心，執行以下步驟：①計算數據集中所有數據點的緊密程度，剔除較為稀疏的數據區域；②根據緊密程度，在數據密集區選擇數據點作為第1個初始簇中心；③在該區域內選擇與第1個初始簇中心距離最遠的數據點作為第2個初始簇中心；④以此類推，后續初始簇中心均選擇與已選簇中心距離最遠者，以保證各個簇中心分布均勻。

例如，對于Rd空間上的數據集合X={x1,…,xi,…,xn}中的任一數據點xi，首先求其緊密度值為

T(xi)=1/∑xj∈GD(xi,xj)

(1)

式中：G為xi的m個最近鄰數據點集合；D(xi,xj)為數據點xi與xj之間的距離。從數據集合X中剔除緊密度值小于∑xi∈XT(xi)/n的數據點，得到數據密集區集合X′。在X′中，取緊密度值最大者作為第1個初始聚類中心c1；取距離c1最遠的數據點作為第2個初始聚類中心c2；第m(m∈[3,K])個初始聚類中心cm所對應的xi滿足條件

(2)

改進K均值聚類算法可以有效避免選擇異常的離群點作為初始簇中心，從而保證算法的迭代初始起點不會大范圍地偏離真實的聚類中心。同時，以數據的緊密程度作為初始簇中心的選擇依據，更加符合最優聚類中心選擇方法。

圖2 初始聚類中心選擇算法流程Fig.2 Flow chart of initial cluster center selected algorithm

2.2 異常試驗數據篩查算法

根據K均值聚類算法特性，若在迭代過程中有離群點參與聚類中心計算過程，就會對聚類結果造成偏差。因此，基于對離群點敏感的特性，在改進K均值聚類算法基礎上，提出異常試驗數據篩查算法，利用迭代過程篩查并剔除異常試驗數據點，算法流程如圖3所示。

算法輸入：Rd空間上的數據集合X={x1,…,xi,…,xn}；聚類中心個數K；聚類收斂閾值ε；最近鄰個數m。

算法輸出：聚類后的數據集C={c1,…,cj,…,cK}；數據xi的聚類標簽L(xi)，異常數據點集合U。

初始化聚類準則函數J0=0，數據xi的異常度值A(xi)=0，根據初始聚類中心選擇算法求得的K個初始聚類中心，分別對應K個聚類ωj(j=1,…,K)。計算X中所有數據點與各個聚類中心之間的距離，距離測度選擇歐氏距離，則有

(3)

式中：i=1,…,n；j=1,…,K；k為聚類ωj中聚類中心數據點的標記。對數據點x，若有cj滿足D(x,cj)=Dmin(x,cj)，則將數據點x歸入cj所對應的聚類，即L(x)=ωj。在K個聚類中，若屬于該聚類的數據點x與聚類中心的距離大于平均距離，即

D(x,cj)>(1/pj)∑L(x)=ωjD(x,cj)

(4)

式中：pj為cj的數據點總數，則記A(x)+ +。計算聚類準則函數為

圖3 異常試驗數據篩查算法流程Fig.3 Flow chart of abnormal test data screening algorithm

(5)

若滿足|Jt-Jt-1|≤ε，對所有數據的異常度值A(xi)求取平均值，將A(x)值大于平均值的數據點加入異常數據點集合U，算法結束；否則，根據各聚類的數據值，重新計算聚類中心，然后根據式(6)繼續迭代。

cj(t)=(1/pj)∑L(x)=ωjx

(6)

上述算法基于改進K均值聚類算法，利用數據點與聚類中心的距離進行異常數據篩查判斷。準確選擇聚類中心是具備良好的異常數據篩查性能的基礎。通過優化初始聚類中心的選擇，選取距離真實聚類中心更近的數據點作為算法迭代起點，不僅可以提高聚類質量，而且可以提高異常數據篩查率。

3 實例驗證

3.1 振動及應力篩選試驗數據分析

以振動及應力篩選試驗數據為例，選取其中-5 V無線電、引信輸出兩個通道數據對異常試驗數據進行篩查。單個通道的試驗數據分別如圖4所示，采樣點均為175 000個。其中，異常試驗數據出現于圖4(a)和(b)中紅色圓圈處。

根據改進K均值聚類算法，對試驗數據進行聚類，結果如圖 5所示。為便于觀察，選取-5 V無線電與引信輸出兩個變量，圖5(a)為兩個變量的三維顯示結果，圖5(b)為聚類中心個數K=2時的聚類結果，聚類中心用紅色圓點標出。聚類結果與圖4所示相一致，根據聚類結果，判斷遠離聚類中心的數據點為異常數據點。圖5(b)中用虛線框標出了由聚類結果判斷出的異常數據點，對應的-5 V無線電值為-4.95 V，這與圖4(a)中的異常數據點也相一致；對應的引信輸出值為4.50 V，這與圖4 (b)中的異常數據點也相一致。

圖4 振動及應力篩選試驗數據Fig.4 Data of vibration and stress screening tests

圖5 -5 V無線電-引信輸出三維顯示和聚類結果Fig.5 3D plot and clustering result of -5V radio and fuze

3.2 算法性能比較

為了比較改進K均值聚類算法與基本K均值聚類算法的性能，在試驗數據中隨機加入10%的異常數據(在原始175 000個采樣點中，隨機疊加17 500個噪聲點)，聚類中心個數K取2，分別進行10組實驗，統計兩種算法的檢測率、誤檢率、迭代次數以及算法運行耗時等指標數據，實驗結果如表1所示。

從表1可以看出，基本K均值聚類算法進行10次實驗的平均檢測率為74.8%，平均誤檢率為15.6%，迭代次數約為19次，平均耗時為95 s，且10次實驗的檢測率和誤檢率波動較大。改進K均值聚類算法進行10次實驗的檢測率、誤檢率、迭代次數以及耗時的均值都優于基本K均值聚類，分別為84.3%、9.4%、10次、62 s，且檢測率和誤檢率波動較小。

因此，與基本K均值聚類算法相比，改進K均值聚類算法無論在檢測率還是誤檢率方面都得到了優化，而且算法平均耗時較少，效率得到提升，同時指標數據的波動較小，算法運行更加穩定。

表1 聚類算法性能比較Tab.1 Comparison of clustering algorithm performance

4 結束語

針對戰術導彈試驗數據分析問題，本文引入數據挖掘技術，在分析K均值聚類算法局限性的基礎上，提出了基于改進K均值聚類的異常試驗數據篩查算法。通過選取距離真實聚類中心更近的數據點作為算法迭代起點，優化初始聚類中心的選擇，以數據點與聚類中心的距離作為異常數據篩查判斷的依據。將導彈振動及應力篩選試驗數據作為算例進行分析，結果表明，與基本K均值聚類算法相比，本文提出的改進K均值聚類的異常試驗數據篩查算法在聚類準確性和運行性能方面都有較大的提升。