基于蒙特卡洛k-means聚類算法的艦船器材分類研究

吳雯雯，陳振林

(海軍航空大學(xué) 岸防兵學(xué)院，山東 煙臺 264001)

0 引言

儀表器材是指用于檢出、測量、觀察、計算各種物理量、物質(zhì)成分、物性參數(shù)等的器具。艦船儀表器材按照工作原理可以分為電磁式與機(jī)械式，按照測量類型可以分為力學(xué)、電磁、熱工、化學(xué)、幾何量、時頻等六大類。遍布艦船各個工作部位，其主要作用是監(jiān)測艦船運(yùn)行狀態(tài)，為艦船運(yùn)行提供壓力、電流、舵角、溫度、風(fēng)速、功率等信息。儀表器材的精確化保障對艦船運(yùn)行至關(guān)重要。

艦船儀表種類繁多，數(shù)量龐大，消耗規(guī)律復(fù)雜，針對每一類器材進(jìn)行分類預(yù)測并不現(xiàn)實，對儀表器材合理分類是提高效率的重要手段，是消耗預(yù)測的基礎(chǔ)[1-4]。目前，針對器材的分類方法有定性方法與定量方法：定性方法有ABC分類法、VED分類法等，這類方法操作簡單，只需要考慮價值、關(guān)鍵性等一個或少數(shù)幾個準(zhǔn)則就能分類，但也存在過于粗放的問題；定量方法有基于器材消耗規(guī)律的SBC分類法、考慮多種分類因素的模糊綜合評價法、層次分析法等，這些方法適用于樣本容量大，影響因素復(fù)雜的情況。隨著研究的不斷深入，定性與定量相結(jié)合以及數(shù)據(jù)挖掘技術(shù)成為熱點(diǎn)。

基于VED的ABC分類法將備件所屬設(shè)備的重要程度等因素納入了考慮范圍[5-6]。文獻(xiàn)[7-8]對備件品種的主要影響因素運(yùn)用模糊綜合評估方法進(jìn)行綜合評價，采用專家系統(tǒng)量化主要指標(biāo)。基于AHP的ABC分類法，在兩種方法結(jié)合的過程中，可以將定性因素和定量因素都轉(zhuǎn)化成數(shù)值形式加以對比，在一定程度上能改進(jìn)管理，但是備件關(guān)鍵性因素的確定受主觀影響較大，不可避免地包含了主觀性的不利影響[9-12]。

文獻(xiàn)[13-14]采取基于屬性的備件品種確定方法，將關(guān)鍵性、可更換性、消耗性、維修性等因素引入備件決策，利用粗糙集理論對備件屬性進(jìn)行因素選取，體現(xiàn)了定量與定性相結(jié)合的特點(diǎn)，有較好的工程實用性。

由英國學(xué)者Syntetos等人提出的SBC分類法[15]應(yīng)用廣泛。該方法基于器材消耗規(guī)律進(jìn)行分類，通過兩個截斷值A(chǔ)DI和CV2(x)將需求分為4類。其中ADI(average demand interval)是需求發(fā)生時間間隔的平均值，反應(yīng)的是0需求量發(fā)生的頻率，ADI值越大，說明需求中0需求發(fā)生的越頻繁，間斷性越明顯；CV(coefficient of variation)為需求量變異程度系數(shù)，反映非零序列偏離均值的嚴(yán)重度，值越大，序列越不穩(wěn)定。圖1中的A、B、C、D分別代表不穩(wěn)定型消耗、塊狀型消耗、平穩(wěn)型消耗、間斷型消耗。

圖1 基于SBC分類法的備件消耗類型圖

SBC方法在處理大量數(shù)據(jù)時有著較為優(yōu)越的解釋效果，但在處理少量數(shù)據(jù)集的時候，往往容易產(chǎn)生較大的誤差。雖然SBC方法對本文所研究的數(shù)據(jù)不太適用，但是它所包含的4種器材類型對有一定的通用指導(dǎo)意義。例如一部分價格昂貴、更換周期較長的儀表，就符合間斷型消耗器材的特征，工作環(huán)境惡劣、大批量消耗的儀表其消耗特征也與平穩(wěn)型消耗類型比較接近。

對于種類多、品種雜、消耗規(guī)律多樣的器材，聚類分析作為一種定量方法，從數(shù)據(jù)分析角度，給出了更準(zhǔn)確、細(xì)致的分類[16-17]。文獻(xiàn)[18]運(yùn)用主成分分析對分類準(zhǔn)則進(jìn)行降維，得到約簡后準(zhǔn)則再進(jìn)行聚類處理。文獻(xiàn)[19]從同一類器材中選擇樣本對網(wǎng)絡(luò)進(jìn)行訓(xùn)練，然后再用該網(wǎng)絡(luò)對該類器材進(jìn)行消耗預(yù)測，節(jié)省了訓(xùn)練時間。文獻(xiàn)[20]基于器材消耗波動性進(jìn)行聚類分析，采用層次劃分聚類，使算法更穩(wěn)定高效。

分析某型艦船儀表器材消耗數(shù)據(jù)，聚類分析方法適用性更好，主要有以下原因：1)某型艦船服役年限較短，數(shù)據(jù)量過少，器材屬性、可靠性、影響因素等信息缺乏相關(guān)數(shù)據(jù)。如果采取AHP、主成分分析法、灰色關(guān)聯(lián)分析、支持向量機(jī)等方法，在數(shù)據(jù)量過少時，容易產(chǎn)生過擬合問題；2)儀表器材長期處于高溫、高濕、高鹽的工作環(huán)境，變化規(guī)律比較復(fù)雜，其損耗往往具有很大的偶然性，各種不同工況的影響或者操作的失誤都有可能直接或間接地產(chǎn)生噪聲影響。作為具有多量值特征的器材，采用聚類方法對其數(shù)學(xué)特征進(jìn)行分析處理會更加準(zhǔn)確、方便、科學(xué)。

1 蒙特卡洛K-means算法

聚類分析是一種重要的數(shù)據(jù)挖掘技術(shù)，是依據(jù)“物以類聚”的思想，對樣本或者指標(biāo)進(jìn)行分類。其目的是把大量數(shù)據(jù)點(diǎn)的集合分成若干類自然分組，使得組內(nèi)相似度最大化，組間相似度最小化，將目標(biāo)集合分成由類似的個體組成的多個類的無監(jiān)督分析過程，可有效地分析數(shù)據(jù)分布，廣泛應(yīng)用于模式識別、機(jī)器學(xué)習(xí)、航空航天等多個領(lǐng)域。聚類分析的分析思路為：在一批樣本的多個觀測指標(biāo)中，找出一個統(tǒng)計量，該統(tǒng)計量可以度量樣本間或者指標(biāo)間的相似程度，構(gòu)成一個對稱的相似性矩陣，以此為基礎(chǔ)，將各樣本逐一歸類。

k-means聚類是最為常用的一種聚類方法，是基于原型的聚類。每一個簇都由某個中心點(diǎn)數(shù)據(jù)代表，這個中心點(diǎn)就是所謂的原型，該算法事先設(shè)置簇的個數(shù)，即k的值，k-means聚類的目標(biāo)是找出各簇的質(zhì)心，然后與各質(zhì)心相鄰的數(shù)據(jù)點(diǎn)聚成各簇，以實現(xiàn)聚類。將所有點(diǎn)的均值作為簇的質(zhì)心。k-means聚類的優(yōu)勢在于對低維度數(shù)據(jù)聚類有著良好的解釋效果，適用于數(shù)據(jù)的初步分析，是一種較為成熟的聚類方法。

k-means聚類實現(xiàn)過程非常便捷，但它的一大弊端在于，該方法對初始聚類中心的選擇十分敏感，不同的初始中心點(diǎn)會造成聚類結(jié)果的波動。隨機(jī)初始化質(zhì)心是該算法的基礎(chǔ)，之后的工作都是圍繞這一基礎(chǔ)開展的，如果更換不同的初始化設(shè)置，那么就有可能得到更好的解。對于給定的數(shù)據(jù)，局部最優(yōu)解往往不是全局最優(yōu)解，因此，質(zhì)心初始化對k-means聚類的結(jié)果有直接影響。為了有效地克服局部最優(yōu)問題，可以采取多次初始化的方法。k-means聚類在處理高維數(shù)據(jù)分類問題時，它更多表示為點(diǎn)的數(shù)據(jù)特性，而對多元線性的聚類列則存在缺陷，導(dǎo)致聚類中心散列，效果不佳。因此，本文通過引入Monte-Carlo(MC)法對質(zhì)心進(jìn)行多次初始化，選出最好的那一次作為最終聚類中心。

MC法亦被稱作隨機(jī)抽樣技術(shù)，廣泛應(yīng)用于對物理過程或生化過程的模擬，也可以求解一些最優(yōu)化問題。在利用計算機(jī)在統(tǒng)計抽樣理論的基礎(chǔ)上，通過有關(guān)隨機(jī)變量的統(tǒng)計抽樣檢驗或隨機(jī)模擬，估計和描述函數(shù)的統(tǒng)計量、求解問題近似解的一種數(shù)值計算方法。MC法不但能夠解決隨機(jī)性問題，也能解決確定性問題。其基本原理是：為解決某一實際問題，首先建立與所求解問題相應(yīng)的一個隨機(jī)模型，形成隨機(jī)變量，使隨機(jī)變量的某個數(shù)字特征(如期望值等)正好是問題的解；然后按照模型進(jìn)行大量的隨機(jī)實驗，以獲得隨機(jī)變量的大量抽樣值，用統(tǒng)計方法作出所求數(shù)字特征的估計值，就得到問題的解。MC法計算程序簡單，其收斂是統(tǒng)計意義上的收斂，收斂速度和問題維數(shù)無關(guān)。MC法誤差僅與方差和樣本容量有關(guān)，而與樣本中元素所在的空間無關(guān)[21]。MC法具有程序結(jié)構(gòu)簡單、不受問題條件限制、模擬過程靈活、適于求解多維問題等優(yōu)點(diǎn)，所以有著廣泛的應(yīng)用。

最終結(jié)果可表示為:

(1)

其中:SSE代表方差函數(shù)，Zt表示在時間為t年下的模型所得誤差，隨后引入變量j∈(1,2)，如果t+1下的模型誤差比t模型下的誤差更小，則替代模型為:

(2)

2 算法流程

1)對數(shù)據(jù)進(jìn)行特征選擇。艦船器材具有品種繁多、影響因素多、波動性大的特點(diǎn)，器材的消耗因為影響因素的變動會存在一定程度的波動。艦船器材因其應(yīng)用目的的特殊性，其影響因素復(fù)雜多變，使得波動性表現(xiàn)得更加明顯，主要體現(xiàn)在消耗的規(guī)模波動和結(jié)構(gòu)波動兩方面。規(guī)模波動是指需求總量的波動，包含收縮和擴(kuò)張兩種情況；結(jié)構(gòu)波動則比較復(fù)雜，主要體現(xiàn)在器材品種的不斷改變。SBC方法中的用到了兩個波動性指標(biāo)：需求發(fā)生間隔的平均值、需求量變異程度系數(shù)。但是分析本文數(shù)據(jù)可知，目前對該型艦船儀表器材的消耗數(shù)據(jù)是以年為單位進(jìn)行統(tǒng)計，若采取SBC方法分類指標(biāo)，數(shù)據(jù)過少，將會出現(xiàn)很大誤差。因此，本文采用計算樣本總體方差描述器材波動性。表達(dá)式為:

(3)

能夠反應(yīng)出曲線的變化規(guī)律和數(shù)據(jù)離散的分布特性，因此適用于k-means聚類。該方法的優(yōu)點(diǎn)在于，解決了k-means處理多維數(shù)據(jù)噪聲過大以及消耗器材數(shù)據(jù)時間軸數(shù)據(jù)過少無法采用合適模型的問題，同時為后期的模型更新做出了鋪墊。

2)確定k值，即聚類種類。直觀地看k-means就是把數(shù)據(jù)空間劃分為k個區(qū)域或者劃出k條邊界，其中各區(qū)域以其原型為質(zhì)心。通常情況下，增大k值就能減小SSE，但這種方法容易出現(xiàn)過擬合，失去聚類分析的意義。k值要事先指定，并且在很大程度上影響聚類結(jié)果。在先驗知識不足的情況下，該參數(shù)的選取比較困難，需要進(jìn)行多次試驗才能找到最佳類別數(shù)。在實際應(yīng)用中，往往需要與別的算法組合使用來確定合適的類別數(shù)，這些算法可能比K-means算法要復(fù)雜得多，抵消了K-means算法簡便易行的優(yōu)勢。因此，本文根據(jù)對某型艦船機(jī)電儀表器材屬性、工作原理及消耗情況的大致了解，參考SBC分類法的種類數(shù)，令聚類種類k=4，使得聚類結(jié)果更加貼合器材管理實際。

3)利用MC法確定初始聚類中心，通過迭代，利用計算機(jī)快速運(yùn)算，不斷進(jìn)行重復(fù)性操作，重復(fù)執(zhí)行建立初始質(zhì)心預(yù)測模型，在每次執(zhí)行這組命令時，都從變量的原值推斷出它的新值，直到各數(shù)據(jù)點(diǎn)不再變更自己所屬的簇，或者這個變更不再顯著，這樣最后確定的質(zhì)心就是數(shù)據(jù)內(nèi)部各簇的代表或者原型。

4)選取SSE來作為誤差檢驗指標(biāo)。SSE是擬合數(shù)據(jù)和原始數(shù)據(jù)對應(yīng)點(diǎn)的誤差的平方和，計算公式為:

(4)

SSE越接近于0，則模型選擇和擬合更好，數(shù)據(jù)預(yù)測也越成功。

該統(tǒng)計參數(shù)是預(yù)測數(shù)據(jù)和原始數(shù)據(jù)對應(yīng)點(diǎn)誤差的平方和的均值，計算公式為:

(5)

對于樣本集D={xi,xi,…,xm}。K-means聚類方法將聚類劃分為C={C1,C2,…,Ck}，最小平方誤差為:

(6)

公式(6)刻畫了簇內(nèi)樣本圍繞簇均值向量的緊密程度，E值越小，簇內(nèi)樣本的相似度越高。

3 仿真試驗與比較

現(xiàn)以某型艦船2015～2019年49種儀表器材年消耗數(shù)據(jù)為例進(jìn)行分析。使用Matlab軟件進(jìn)行仿真試驗，通過STDEVP函數(shù)計算樣本總體方差，得到結(jié)果如表1所示。

表1 儀表器材年消耗數(shù)據(jù)

從表1可以看出，數(shù)據(jù)方差σ2總體偏小，在一定范圍內(nèi)波動，對此建立需求方差變量T= [σ12σ22…σ492]。對該變量分別進(jìn)行經(jīng)典k-means聚類及蒙特卡洛k-means聚類分析，對比兩種方法的結(jié)果，驗證本文方法的有效性和精確性。

3.1 經(jīng)典k-means聚類分析

經(jīng)典k-means聚類過程如下：

首先，初始化質(zhì)心。隨機(jī)初始化k個質(zhì)心。

第二步，劃分?jǐn)?shù)據(jù)點(diǎn)，質(zhì)心確定后，找出距離最近質(zhì)心的數(shù)據(jù)點(diǎn)，形成簇，此處采取歐氏距離進(jìn)行度量，有n個特征的數(shù)據(jù)點(diǎn)X(x1,x2,…,xn)與點(diǎn)C(c1,c2,…,cn)之間的歐式距離計算公式為:

(7)

各點(diǎn)找到相距最近的質(zhì)心之后，就歸屬于該簇，數(shù)據(jù)空間就被劃分成k個子區(qū)域。

第三步，找出該簇最有代表性的點(diǎn)，作為新的質(zhì)心，即求解所有點(diǎn)到質(zhì)心距離誤差平方和最小化問題。

第四步，反復(fù)計算并更新質(zhì)心。新的質(zhì)心確定之后，更新各數(shù)據(jù)點(diǎn)至最近的質(zhì)心，確定新簇并再一次更新質(zhì)心。重復(fù)這個過程。直至各數(shù)據(jù)點(diǎn)所從屬的簇不再變化或者變化不再顯著，那么最后確定的質(zhì)心就是各簇的代表，可以描述整個模型。

使用Matlab軟件進(jìn)行k-means聚類,所得結(jié)果見表2，聚類圖如圖2所示。從表2中可以看出，k-means方法針對每年數(shù)據(jù)都產(chǎn)生不同的聚類中心。從圖2可以看出，k-means聚類無法合理處理多維數(shù)據(jù)，聚類效果不明顯。

表2 最終聚類中心

圖2 K-means聚類圖

3.2 蒙特卡洛k-means算法

對器材消耗進(jìn)行蒙特卡洛k-means 聚類分析，得到聚類結(jié)果見表3，聚類圖如圖3。從圖3中可以看出，聚類效果顯著，第2、3類消耗器材在總體樣本中占比較高。

表3 最終聚類中心

圖3 蒙特卡洛K-means聚類圖

對比以上兩種聚類結(jié)果及散點(diǎn)圖可以看出，未進(jìn)行蒙特卡洛k-means聚類結(jié)果散列，聚類圖分類不明顯，受時間序列的影響較大，不能夠直觀地分析出結(jié)果，而處理過后的數(shù)據(jù)聚類效果明顯，該方法很好地將低數(shù)據(jù)量的消耗器材映射到了三維空間，同時解決了k-means算法無法處理高維數(shù)據(jù)的問題。

以(2.56,0.85,1.73,4.69)作為聚類中心得到聚類結(jié)果見表4。

表4 聚類成員

根據(jù)4種器材年消耗相對值，得出器材分類消耗折線圖，如圖4所示。從圖中可以看出，2015～2019年4類器材消耗均呈上升趨勢，這與艦船遂行任務(wù)增多以及儀表到壽更換的客觀事實是吻合的。從需求間隔和需求量上看，第1類與第3類器材波動性最強(qiáng)，第4類次之，第2類最為平穩(wěn)。

圖4 器材分類消耗折線圖

4 結(jié)束語

準(zhǔn)確的分類是消耗預(yù)測的基礎(chǔ)，利用消耗波動性對器材進(jìn)行分類符合實際工作需要，具有很強(qiáng)的借鑒意義。本文著力研究艦船儀表器材分類問題，針對某型艦船儀表器材數(shù)據(jù)量稀疏，采取需求量變異程度系數(shù)等其他波動性指標(biāo)易造成過擬合的情況，考慮利用樣本方差來體現(xiàn)器材消耗波動性，無需計算器材內(nèi)在屬性，不需要對數(shù)據(jù)進(jìn)行時間序列AR建模，簡化了儀表器材消耗分類模型，能夠有效解決數(shù)據(jù)量過少時模型建立困難的問題，避免了復(fù)雜模型放大誤差。本文基于蒙特卡洛法改進(jìn)了初始聚類中心的選擇，有效避免了傳統(tǒng)算法隨機(jī)選擇初始聚類中心導(dǎo)致的結(jié)果不穩(wěn)定性。與多尺度最小二乘SVM模型、AHP理論相比，采用本文的方法，對數(shù)據(jù)不足的模型有著較好的適用性。后續(xù)研究將結(jié)合其他分類方法，對聚類結(jié)果進(jìn)一步的量化分析。