聚類算法在艦載機(jī)加載系統(tǒng)設(shè)計(jì)的改進(jìn)應(yīng)用?

李幸運(yùn) 劉佳銘

（1.武漢數(shù)字工程研究所 武漢 430074）（2.海裝艦船辦 北京 100071）

1 引言

在艦載機(jī)加載系統(tǒng)設(shè)計(jì)中，加載點(diǎn)的分區(qū)、杠桿連接是其重要工作內(nèi)容。在艦載機(jī)不同的加載部位上所需加載的載荷點(diǎn)數(shù)量是不同的，像機(jī)翼這類主要受力的部件加載面上載荷點(diǎn)少則幾十個(gè)，多則上百個(gè)［1～3］。對(duì)此只用一個(gè)作動(dòng)筒加載會(huì)造成加載系統(tǒng)級(jí)數(shù)過(guò)多，重量過(guò)大，不方便杠桿安裝等問(wèn)題，影響加載精度，因此對(duì)加載點(diǎn)進(jìn)行合理的分區(qū)非常重要。目前設(shè)計(jì)人員大多是按照加載部件的結(jié)構(gòu)切面或是根據(jù)經(jīng)驗(yàn)來(lái)進(jìn)行人工劃分分區(qū)，由于分區(qū)過(guò)程沒(méi)有考慮到載荷點(diǎn)位置和載荷的影響，得到的分區(qū)會(huì)出現(xiàn)配重過(guò)多、過(guò)大的情況，對(duì)杠桿加載系統(tǒng)的重量會(huì)產(chǎn)生很大的影響。

杠桿連接在杠桿加載系統(tǒng)設(shè)計(jì)中起著重要作用，一個(gè)合理高效的杠桿連接形式能夠大幅地減少杠桿系統(tǒng)的配重，以及整個(gè)加載系統(tǒng)重量，減少安裝工作量。但目前仍沒(méi)有合適的方法能夠精確求解杠桿連接這種復(fù)雜組合優(yōu)化問(wèn)題的最優(yōu)解［4～6］。傳統(tǒng)辦法是設(shè)計(jì)人員用CAD軟件按加載點(diǎn)位置和載荷大小逐級(jí)計(jì)算連接，這樣不但工作量大、效率低，而且人為影響較大，結(jié)果不夠理想，無(wú)法保證系統(tǒng)級(jí)數(shù)低、配重少的要求。邊蒲亞［7］提出基于遺傳算法的杠桿加載系統(tǒng)優(yōu)化設(shè)計(jì)，然而無(wú)法避免遺傳算法早熟、效率低、穩(wěn)定性差的缺陷。

本文針對(duì)以上問(wèn)題，結(jié)合載荷點(diǎn)在分區(qū)和杠桿連接過(guò)程的特點(diǎn)，提出改進(jìn)的聚類算法，將試驗(yàn)加載點(diǎn)看作待聚類樣本，其坐標(biāo)位置、加載載荷等特征看作樣本指標(biāo)，考慮載荷點(diǎn)自身特征對(duì)其進(jìn)行聚類，利用聚類算法的聚類特性獲取載荷點(diǎn)的分區(qū)情況和連接順序，以此解決加載系統(tǒng)設(shè)計(jì)中加載點(diǎn)的分區(qū)和杠桿的連接順序的問(wèn)題。

2 基本層次聚類算法

聚類（Clustering）簡(jiǎn)單地說(shuō)就是把相似的東西分到一組，聚類的時(shí)候，并不關(guān)心某一類是什么，需要實(shí)現(xiàn)的目標(biāo)只是把相似的東西聚到一起［8～9］。因此通常一個(gè)聚類算法只需要知道如何計(jì)算相似度就可以開(kāi)始工作，而并不需要使用訓(xùn)練數(shù)據(jù)進(jìn)行學(xué)習(xí)，這在機(jī)器學(xué)習(xí)中屬于無(wú)監(jiān)督學(xué)習(xí)算法。層次聚類是聚類算法中的一種，它采用一種迭代控制策略，使聚類逐步優(yōu)化，通過(guò)計(jì)算不同類別數(shù)據(jù)點(diǎn)間的相似度從而形成一棵有層次的嵌套聚類樹(shù)［10～11］。根據(jù)層次聚類過(guò)程是自底而上還是自頂而下進(jìn)行的，層次聚類算法可以進(jìn)一步分為凝聚型和分裂型兩種方法。以凝聚的層次聚類法為例來(lái)介紹層次聚類算法的基本原理，其基本聚類步驟為

1）初始化，把每個(gè)樣本歸為一類，計(jì)算每?jī)蓚€(gè)類之間的距離，形成初始距離矩陣；

2）尋找各個(gè)類之間距離最近的兩個(gè)類，把它們歸為一類，此時(shí)類的總數(shù)減少了一個(gè)；

3）重新計(jì)算其它類與新類之間的距離，更新距離矩陣；

4）重復(fù)2）和3）直到所有樣本點(diǎn)都?xì)w為一類，結(jié)束。

3 基于凝聚的層次聚類算法的改進(jìn)及優(yōu)化

3.1 改進(jìn)算法的提出

聚類算法的選擇與其適用的應(yīng)用領(lǐng)域關(guān)系極大，在杠桿加載設(shè)計(jì)中，考慮到在杠桿加載中分區(qū)問(wèn)題與加載點(diǎn)的空間位置關(guān)系緊密，同時(shí)杠桿連接時(shí)其連接結(jié)構(gòu)也是層次型的，很方便通過(guò)樹(shù)形圖來(lái)表達(dá)，層次方法既能從空間位置關(guān)系對(duì)加載點(diǎn)進(jìn)行劃分，解決分區(qū)問(wèn)題，又能通過(guò)獲取聚類過(guò)程的層次結(jié)構(gòu)來(lái)確定杠桿的連接順序，與解決杠桿加載問(wèn)題的需求上十分吻合，因此可針對(duì)杠桿加載中的實(shí)際問(wèn)題對(duì)層次聚類算法進(jìn)行適當(dāng)改進(jìn)，對(duì)其改進(jìn)作出以下幾點(diǎn)考慮：

1）將初始加載點(diǎn)看作樣本點(diǎn)，加載點(diǎn)的位置、載荷信息看作樣本點(diǎn)的指標(biāo)；

2）加載點(diǎn)的位置指標(biāo)和載荷指標(biāo)對(duì)相似度計(jì)算的貢獻(xiàn)形式并不一樣，計(jì)算相似度矩陣需對(duì)相似度的計(jì)算進(jìn)行相應(yīng)的改進(jìn)；

3）每次更新距離矩陣時(shí)，類間距離的計(jì)算同樣要綜合考慮類中加載點(diǎn)的位置及載荷信息，需要對(duì)類間距離的計(jì)算方法進(jìn)行相應(yīng)的改進(jìn)；

4）為了提高聚類效果，考慮每次聚類對(duì)下一步聚類的影響，需對(duì)聚類點(diǎn)的選取策略進(jìn)行優(yōu)化。

3.2 相似性度量改進(jìn)

在聚類算法中，相似度矩陣用來(lái)存儲(chǔ)各個(gè)對(duì)象兩兩之間的相似度，常用作計(jì)算初始距離矩陣。本文聚類分析中處理的數(shù)據(jù)對(duì)象為加載系統(tǒng)的初始加載點(diǎn)信息，因此需要計(jì)算初始加載點(diǎn)對(duì)象之間的距離，形成初始距離矩陣。常用的距離形式有曼哈頓距離、閔可夫斯基距離和馬氏距離。對(duì)于聚類算法來(lái)說(shuō)，不同距離形式的選取會(huì)直接影響著聚類的最終效果。在杠桿加載設(shè)計(jì)中，初始加載點(diǎn)的信息主要包括位置坐標(biāo)和加載載荷，傳統(tǒng)的歐氏距離描述的僅僅是對(duì)象間的幾何距離，無(wú)法涵蓋初始加載點(diǎn)的所有信息。

因此，針對(duì)傳統(tǒng)的距離計(jì)算形式在表達(dá)杠桿加載中初始加載點(diǎn)之間的相似程度上的不足，本文進(jìn)行相似性度量改進(jìn)，初始加載點(diǎn)的位置指標(biāo)和載荷指標(biāo)對(duì)相似度的貢獻(xiàn)形式并不相同，位置指標(biāo)可采用歐氏距離來(lái)表現(xiàn)，而載荷指標(biāo)則可將兩對(duì)象之間的載荷的比值，即杠桿的力臂比作為權(quán)重系數(shù)參與距離的計(jì)算，這樣既不存在指標(biāo)間量綱不同的問(wèn)題，也不需要考慮指標(biāo)間的相關(guān)性，同時(shí)兼顧了加載點(diǎn)的位置和載荷信息。據(jù)此提出基于杠桿力臂比的加權(quán)的歐氏距離的形式來(lái)計(jì)算聚類的初始距離矩陣。

杠桿系統(tǒng)中，配重問(wèn)題的產(chǎn)生是由于未考慮加載系統(tǒng)自身（如杠桿、連接件等）的重量而導(dǎo)致系統(tǒng)重心與載荷合力點(diǎn)不重合造成的，一般可通過(guò)力矩法［12］來(lái)解決。設(shè)杠桿配重ΔG，杠桿重量為G1，其單位長(zhǎng)度重量為ρ，則在該級(jí)杠桿系統(tǒng)中，系統(tǒng)重量為

其中，n為杠桿長(zhǎng)力臂與短力臂之比，l為杠桿長(zhǎng)度，也可認(rèn)為是杠桿兩端加載點(diǎn)在加載平面上的幾何距離。ρ可看作常量，不作考慮，因此可定義改進(jìn)的歐氏距離為

其中，xi1、xi2為加載點(diǎn)i的前兩個(gè)指標(biāo)值，即該加載點(diǎn)在其加載平面上的兩個(gè)坐標(biāo)值；xi3為加載點(diǎn)i的第三個(gè)指標(biāo)值，即該加載點(diǎn)的加載載荷，其載荷方向一般與坐標(biāo)系中某一坐標(biāo)軸平行，垂直于其加載平面。

3.3 類間距離改進(jìn)

在聚類過(guò)程中，初始距離矩陣由計(jì)算相似度矩陣得到，但在之后的迭代合并新類時(shí)，聚類得到的新類所包含的對(duì)象不止一個(gè)，已經(jīng)不能通過(guò)計(jì)算相似度來(lái)更新距離矩陣，對(duì)此需要定義類間距離來(lái)確定類與類之間的關(guān)系，常見(jiàn)的的類間距離有以下幾種：1）最小距離：類間距離為兩個(gè)類中所有樣本之間的最短距離。2）最大距離：類間距離為兩個(gè)類中所有樣本之間的最遠(yuǎn)距離。3）重心距離：類間距離為兩個(gè)類重心（均值）間的平方歐氏距離。4）類平均距離：類間距離為兩個(gè)類中所有樣本之間距離的平均距離。

圖1 杠桿原理示意圖

以上幾種類間距離中，類平均法得到的聚類效果較好，但將它應(yīng)用到杠桿加載中仍然不能反映真實(shí)的杠桿加載點(diǎn)之間的位置關(guān)系。在杠桿加載設(shè)計(jì)中，類間距離表示的是杠桿加載點(diǎn)之間的關(guān)系，杠桿加載點(diǎn)的位置信息是可以根據(jù)杠桿原理來(lái)確定，如圖1所示。加載載荷與z軸平行時(shí)，加載平面即為xy平面，在已知加載點(diǎn)A、B的x、y坐標(biāo)時(shí)即可根據(jù)杠桿原理確定合力點(diǎn)o位置。

加載點(diǎn)A、B的在加載平面xy上的坐標(biāo)即為其前兩個(gè)指標(biāo)值，分別記為為該杠桿的力臂比，則合力點(diǎn)o位置為

在杠桿連接中，下級(jí)杠桿合力點(diǎn)在高一級(jí)的加載杠桿中是作為杠桿加載點(diǎn)進(jìn)行加載。上式中，杠桿合力點(diǎn)是綜合其兩加載點(diǎn)的三個(gè)指標(biāo)值得到的，能夠代表兩加載點(diǎn)的綜合信息，因此在聚類過(guò)程中，可計(jì)算每次合并得到的新類中的合力點(diǎn)，即杠桿加載點(diǎn)，將該點(diǎn)看作新類的代表點(diǎn)，使得每次聚類得到的新類都可以由一個(gè)杠桿加載點(diǎn)來(lái)代表，那么類間距離只需通過(guò)計(jì)算兩個(gè)類之間代表點(diǎn)之間的距離來(lái)確定，該距離的計(jì)算仍采用改進(jìn)的歐氏距離形式，與式（2）一致，Xp、Xp分別為類p、類q代表點(diǎn)，則新的類間距離定義形式為

新的類間距離形式不僅能夠表現(xiàn)杠桿連接中杠桿加載點(diǎn)之間的相關(guān)性，還將聚類算法中相似度和類間距離兩種不同概念在形式上統(tǒng)一化，使算法更易于理解，同時(shí)反映了初始加載點(diǎn)和杠桿加載點(diǎn)在本質(zhì)上的一致性，更符合杠桿加載設(shè)計(jì)的實(shí)際情況。

3.4 待聚類點(diǎn)選取策略優(yōu)化

在基本的層次聚類算法中，每次聚類都是選擇距離矩陣中距離最短的兩個(gè)類，為避免算法過(guò)早地陷入局部最優(yōu)，減小合并新類對(duì)后續(xù)聚類產(chǎn)生的不利影響，對(duì)待合并的聚類點(diǎn)選取策略進(jìn)行適當(dāng)優(yōu)化，確定影響較小、結(jié)果更優(yōu)的兩個(gè)待合并類。優(yōu)化過(guò)程如下：

1）聚類開(kāi)始時(shí)尋找距離矩陣中距離最短的兩個(gè)類，記錄其編號(hào)i、j及其包含加載點(diǎn)個(gè)數(shù)Ni、Nj，計(jì)算連接i、j時(shí)力臂比 nij；

2）根據(jù)距離矩陣尋找除類j以外與類i距離最近的類m及其包含的加載點(diǎn)個(gè)數(shù)Nm，計(jì)算力臂比nim；

3）根據(jù)距離矩陣尋找除類i以外與類j距離最近的類，記錄其編號(hào)為n及其包含的加載點(diǎn)個(gè)數(shù)Nn，計(jì)算力臂比njn；

4）考慮連接i、j后再連接 m時(shí)，力臂比則在這種連接順序下的總力臂比為同理計(jì)算連接i、j后再連接n時(shí)，總力臂比連接i、m后再連接j時(shí)，總力臂比連接 j、n后再連接i時(shí)，總力臂比

3.5 改進(jìn)算法流程

通過(guò)以上對(duì)算法的改進(jìn)及優(yōu)化，形成本文改進(jìn)的層次聚類算法，其具體步驟如下：

1）獲取初始加載點(diǎn)信息數(shù)據(jù)，存入數(shù)據(jù)矩陣data中；

2）根據(jù)改進(jìn)歐氏距離計(jì)算初始數(shù)據(jù)兩兩之間相似度，得到初始距離矩陣distmatrix；

3）查找距離矩陣distmatrix中距離最小值對(duì)應(yīng)的兩個(gè)類 i、j；

4）利用優(yōu)化的聚類點(diǎn)選取策略確定最終待聚類的兩個(gè)類is、js；

5）將類is、js合并為一個(gè)新類，更新數(shù)據(jù)矩陣，采用改進(jìn)的類間距離公式重新計(jì)算其它類與新類的類間距離，更新距離矩陣；

圖2 改進(jìn)算法流程圖

6）重復(fù)步驟3）～5）直至所有數(shù)據(jù)處理完畢，此時(shí)所有加載點(diǎn)都被合并到一個(gè)類中，得到描述整個(gè)聚類過(guò)程的聚類樹(shù)；

7）獲取分區(qū)個(gè)數(shù)k，將聚類樹(shù)剪切為k個(gè)類簇，獲取每個(gè)類簇的子聚類樹(shù)，即可得到相應(yīng)分區(qū)內(nèi)所有加載點(diǎn)的連接順序，輸出k個(gè)分區(qū)及其連接層次結(jié)構(gòu)，聚類結(jié)束。

算法流程圖如圖2所示。

4 聚類實(shí)驗(yàn)對(duì)比

為了驗(yàn)證改進(jìn)算法的有效性和準(zhǔn)確性，進(jìn)行聚類對(duì)比實(shí)驗(yàn)：在常規(guī)層次聚類算法中，類平均法是效率較高的一種算法，因此本次實(shí)驗(yàn)選擇類平均法與本文改進(jìn)的層次聚類算法進(jìn)行對(duì)比，對(duì)某部件一加載切面上6個(gè)加載點(diǎn)進(jìn)行杠桿連接設(shè)計(jì)。使用上述兩種算法分別對(duì)上表中加載點(diǎn)進(jìn)行聚類分析，所得結(jié)果分別如圖3、圖4所示。

圖3 類平均法杠桿連接示意圖

圖4 改進(jìn)算法杠桿連接示意圖

從上圖可看出，兩種算法得到的杠桿連接形式不同：類平均法每次都是將平均距離最短的兩個(gè)加載點(diǎn)合并，但沒(méi)有考慮加載點(diǎn)載荷的影響，會(huì)使得類簇之間載荷相差較大，如將類1_7與類1_8合并為類2_10再將類2_10與類1_9合并為類3_10后，會(huì)因?yàn)閮蓚€(gè)類載荷相差較大而產(chǎn)生配重偏大的問(wèn)題。而改進(jìn)算法能夠避免這種不合理情況發(fā)生，使聚類順序和聚類點(diǎn)的選取更加合理，如將類1_8與加載點(diǎn)11011合并為類2_9，類1_7與加載點(diǎn)11012合并為類2_10，兩者合力相近，使得最后合并這兩個(gè)類時(shí)力臂比趨向于1，減小配重。相較于類平均法，改進(jìn)算法更加有效地減少杠桿系統(tǒng)的配重和總重量。

5 結(jié)語(yǔ)

本文針對(duì)艦載機(jī)加載系統(tǒng)中加載點(diǎn)區(qū)分、杠桿連接等問(wèn)題，綜合考慮初始加載點(diǎn)位置、載荷等指標(biāo)，對(duì)凝聚的層次聚類算法進(jìn)行改進(jìn)和優(yōu)化，提出一種適用于杠桿加載的改進(jìn)聚類算法。改進(jìn)的聚類算法不僅能夠很好地解決杠桿加載中存在的問(wèn)題，還能夠更加有效地減少杠桿系統(tǒng)的配重，快速完成加載點(diǎn)分區(qū)、杠桿連接的工作，得到滿意的結(jié)果，解決傳統(tǒng)加載設(shè)計(jì)方法中工作量大、效率低以及設(shè)計(jì)精度低等問(wèn)題，大大縮短加載系統(tǒng)設(shè)計(jì)周期和成本，提高設(shè)計(jì)效率。