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

吳雯雯，陳振林

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

0 引言

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

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

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

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

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

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

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

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

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

1 蒙特卡洛K-means算法

聚類分析是一種重要的數據挖掘技術，是依據“物以類聚”的思想，對樣本或者指標進行分類。其目的是把大量數據點的集合分成若干類自然分組，使得組內相似度最大化，組間相似度最小化，將目標集合分成由類似的個體組成的多個類的無監督分析過程，可有效地分析數據分布，廣泛應用于模式識別、機器學習、航空航天等多個領域。聚類分析的分析思路為：在一批樣本的多個觀測指標中，找出一個統計量，該統計量可以度量樣本間或者指標間的相似程度，構成一個對稱的相似性矩陣，以此為基礎，將各樣本逐一歸類。

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

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

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

最終結果可表示為:

(1)

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

(2)

2 算法流程

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

(3)

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

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

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

4)選取SSE來作為誤差檢驗指標。SSE是擬合數據和原始數據對應點的誤差的平方和，計算公式為:

(4)

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

該統計參數是預測數據和原始數據對應點誤差的平方和的均值，計算公式為:

(5)

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

(6)

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

3 仿真試驗與比較

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

表1 儀表器材年消耗數據

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

3.1 經典k-means聚類分析

經典k-means聚類過程如下：

首先，初始化質心。隨機初始化k個質心。

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

(7)

各點找到相距最近的質心之后，就歸屬于該簇，數據空間就被劃分成k個子區域。

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

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

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

表2 最終聚類中心

圖2 K-means聚類圖

3.2 蒙特卡洛k-means算法

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

表3 最終聚類中心

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

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

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

表4 聚類成員

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

圖4 器材分類消耗折線圖

4 結束語

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