基于改進(jìn)K均值聚類的戰(zhàn)術(shù)導(dǎo)彈試驗(yàn)數(shù)據(jù)分析

黃偉愷，馬 行，劉 進(jìn)，李宇平，鄭丹力

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

0 引 言

開展戰(zhàn)術(shù)導(dǎo)彈振動(dòng)及應(yīng)力篩選試驗(yàn)時(shí)，通常是在比較寬的頻率范圍內(nèi)對(duì)導(dǎo)彈施加振動(dòng)，使導(dǎo)彈的多個(gè)共振點(diǎn)同時(shí)受到激勵(lì)而產(chǎn)生共振，從而發(fā)現(xiàn)扭曲、碰撞等作用可能對(duì)導(dǎo)彈造成的損壞，盡早暴露產(chǎn)品的早期設(shè)計(jì)缺陷。因此，針對(duì)戰(zhàn)術(shù)導(dǎo)彈的振動(dòng)及應(yīng)力篩選試驗(yàn)開展試驗(yàn)數(shù)據(jù)分析工作，可以為戰(zhàn)術(shù)導(dǎo)彈的研制以及相關(guān)測(cè)試系統(tǒng)的改進(jìn)提供分析依據(jù)或建議。

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

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

本文針對(duì)戰(zhàn)術(shù)導(dǎo)彈振動(dòng)及應(yīng)力篩選試驗(yàn)數(shù)據(jù)的分析和處理問題，對(duì)K均值聚類算法的缺陷進(jìn)行分析，以期從大數(shù)據(jù)量的試驗(yàn)數(shù)據(jù)中發(fā)現(xiàn)蘊(yùn)含價(jià)值的潛在規(guī)律，從而實(shí)現(xiàn)戰(zhàn)術(shù)導(dǎo)彈試驗(yàn)數(shù)據(jù)的自動(dòng)化處理和分析。

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

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

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

1) 隨機(jī)指定K個(gè)數(shù)據(jù)點(diǎn)作為算法的初始簇中心；

2) 計(jì)算數(shù)據(jù)集中所有數(shù)據(jù)點(diǎn)與初始簇中心的相似度，把各個(gè)數(shù)據(jù)點(diǎn)歸入最相似的簇；

3) 根據(jù)被歸入的數(shù)據(jù)點(diǎn)，重新計(jì)算各簇中心；

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

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

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

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

1) 隨機(jī)選擇的初始簇中心對(duì)聚類結(jié)果影響巨大。如圖 1所示，(a)和(b)對(duì)應(yīng)的聚類結(jié)果較(c)和(d)對(duì)應(yīng)的聚類結(jié)果要好，這是因?yàn)?a)和(b)所選擇的初始簇中心更接近真正的簇中心。通過(guò)上述對(duì)比可知，選擇初始簇中心不合適會(huì)導(dǎo)致聚類結(jié)果存在較大誤差。

2) 異常試驗(yàn)數(shù)據(jù)對(duì)聚類結(jié)果也存在重大影響。

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

試驗(yàn)數(shù)據(jù)中存在的異常數(shù)據(jù)會(huì)干擾聚類中心的計(jì)算，進(jìn)而影響聚類結(jié)果。

3) 隨機(jī)選擇的K值對(duì)聚類結(jié)果影響較大。不同的初始值K可能導(dǎo)致數(shù)據(jù)點(diǎn)被分配到不同的簇中，從而導(dǎo)致結(jié)果非確定。

2 異常試驗(yàn)數(shù)據(jù)篩查方法

2.1 改進(jìn)K均值聚類算法

為了解決初始簇中心的隨機(jī)性問題，應(yīng)遵循以下原則選擇初始簇中心：避免選擇異常數(shù)據(jù)點(diǎn)；在高密度且均勻分布區(qū)域內(nèi)進(jìn)行選擇。

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

例如，對(duì)于Rd空間上的數(shù)據(jù)集合X={x1,…,xi,…,xn}中的任一數(shù)據(jù)點(diǎn)xi，首先求其緊密度值為

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

(1)

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

(2)

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

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

2.2 異常試驗(yàn)數(shù)據(jù)篩查算法

根據(jù)K均值聚類算法特性，若在迭代過(guò)程中有離群點(diǎn)參與聚類中心計(jì)算過(guò)程，就會(huì)對(duì)聚類結(jié)果造成偏差。因此，基于對(duì)離群點(diǎn)敏感的特性，在改進(jìn)K均值聚類算法基礎(chǔ)上，提出異常試驗(yàn)數(shù)據(jù)篩查算法，利用迭代過(guò)程篩查并剔除異常試驗(yàn)數(shù)據(jù)點(diǎn)，算法流程如圖3所示。

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

算法輸出：聚類后的數(shù)據(jù)集C={c1,…,cj,…,cK}；數(shù)據(jù)xi的聚類標(biāo)簽L(xi)，異常數(shù)據(jù)點(diǎn)集合U。

初始化聚類準(zhǔn)則函數(shù)J0=0，數(shù)據(jù)xi的異常度值A(chǔ)(xi)=0，根據(jù)初始聚類中心選擇算法求得的K個(gè)初始聚類中心，分別對(duì)應(yīng)K個(gè)聚類ωj(j=1,…,K)。計(jì)算X中所有數(shù)據(jù)點(diǎn)與各個(gè)聚類中心之間的距離，距離測(cè)度選擇歐氏距離，則有

(3)

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

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

(4)

式中：pj為cj的數(shù)據(jù)點(diǎn)總數(shù)，則記A(x)+ +。計(jì)算聚類準(zhǔn)則函數(shù)為

圖3 異常試驗(yàn)數(shù)據(jù)篩查算法流程Fig.3 Flow chart of abnormal test data screening algorithm

(5)

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

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

(6)

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

3 實(shí)例驗(yàn)證

3.1 振動(dòng)及應(yīng)力篩選試驗(yàn)數(shù)據(jù)分析

以振動(dòng)及應(yīng)力篩選試驗(yàn)數(shù)據(jù)為例，選取其中-5 V無(wú)線電、引信輸出兩個(gè)通道數(shù)據(jù)對(duì)異常試驗(yàn)數(shù)據(jù)進(jìn)行篩查。單個(gè)通道的試驗(yàn)數(shù)據(jù)分別如圖4所示，采樣點(diǎn)均為175 000個(gè)。其中，異常試驗(yàn)數(shù)據(jù)出現(xiàn)于圖4(a)和(b)中紅色圓圈處。

根據(jù)改進(jìn)K均值聚類算法，對(duì)試驗(yàn)數(shù)據(jù)進(jìn)行聚類，結(jié)果如圖 5所示。為便于觀察，選取-5 V無(wú)線電與引信輸出兩個(gè)變量，圖5(a)為兩個(gè)變量的三維顯示結(jié)果，圖5(b)為聚類中心個(gè)數(shù)K=2時(shí)的聚類結(jié)果，聚類中心用紅色圓點(diǎn)標(biāo)出。聚類結(jié)果與圖4所示相一致，根據(jù)聚類結(jié)果，判斷遠(yuǎn)離聚類中心的數(shù)據(jù)點(diǎn)為異常數(shù)據(jù)點(diǎn)。圖5(b)中用虛線框標(biāo)出了由聚類結(jié)果判斷出的異常數(shù)據(jù)點(diǎn)，對(duì)應(yīng)的-5 V無(wú)線電值為-4.95 V，這與圖4(a)中的異常數(shù)據(jù)點(diǎn)也相一致；對(duì)應(yīng)的引信輸出值為4.50 V，這與圖4 (b)中的異常數(shù)據(jù)點(diǎn)也相一致。

圖4 振動(dòng)及應(yīng)力篩選試驗(yàn)數(shù)據(jù)Fig.4 Data of vibration and stress screening tests

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

3.2 算法性能比較

為了比較改進(jìn)K均值聚類算法與基本K均值聚類算法的性能，在試驗(yàn)數(shù)據(jù)中隨機(jī)加入10%的異常數(shù)據(jù)(在原始175 000個(gè)采樣點(diǎn)中，隨機(jī)疊加17 500個(gè)噪聲點(diǎn))，聚類中心個(gè)數(shù)K取2，分別進(jìn)行10組實(shí)驗(yàn)，統(tǒng)計(jì)兩種算法的檢測(cè)率、誤檢率、迭代次數(shù)以及算法運(yùn)行耗時(shí)等指標(biāo)數(shù)據(jù)，實(shí)驗(yàn)結(jié)果如表1所示。

從表1可以看出，基本K均值聚類算法進(jìn)行10次實(shí)驗(yàn)的平均檢測(cè)率為74.8%，平均誤檢率為15.6%，迭代次數(shù)約為19次，平均耗時(shí)為95 s，且10次實(shí)驗(yàn)的檢測(cè)率和誤檢率波動(dòng)較大。改進(jìn)K均值聚類算法進(jìn)行10次實(shí)驗(yàn)的檢測(cè)率、誤檢率、迭代次數(shù)以及耗時(shí)的均值都優(yōu)于基本K均值聚類，分別為84.3%、9.4%、10次、62 s，且檢測(cè)率和誤檢率波動(dòng)較小。

因此，與基本K均值聚類算法相比，改進(jìn)K均值聚類算法無(wú)論在檢測(cè)率還是誤檢率方面都得到了優(yōu)化，而且算法平均耗時(shí)較少，效率得到提升，同時(shí)指標(biāo)數(shù)據(jù)的波動(dòng)較小，算法運(yùn)行更加穩(wěn)定。

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

4 結(jié)束語(yǔ)

針對(duì)戰(zhàn)術(shù)導(dǎo)彈試驗(yàn)數(shù)據(jù)分析問題，本文引入數(shù)據(jù)挖掘技術(shù)，在分析K均值聚類算法局限性的基礎(chǔ)上，提出了基于改進(jìn)K均值聚類的異常試驗(yàn)數(shù)據(jù)篩查算法。通過(guò)選取距離真實(shí)聚類中心更近的數(shù)據(jù)點(diǎn)作為算法迭代起點(diǎn)，優(yōu)化初始聚類中心的選擇，以數(shù)據(jù)點(diǎn)與聚類中心的距離作為異常數(shù)據(jù)篩查判斷的依據(jù)。將導(dǎo)彈振動(dòng)及應(yīng)力篩選試驗(yàn)數(shù)據(jù)作為算例進(jìn)行分析，結(jié)果表明，與基本K均值聚類算法相比，本文提出的改進(jìn)K均值聚類的異常試驗(yàn)數(shù)據(jù)篩查算法在聚類準(zhǔn)確性和運(yùn)行性能方面都有較大的提升。