基于改進(jìn)的模糊C-均值聚類算法的接線箱分配設(shè)計(jì)與應(yīng)用

劉迪成 王 建 王敏昊

(中國海誠工程科技股份有限公司，上海 200031)

基于改進(jìn)的模糊C-均值聚類算法的接線箱分配設(shè)計(jì)與應(yīng)用

劉迪成 王 建 王敏昊

(中國海誠工程科技股份有限公司，上海 200031)

為了解決工程設(shè)計(jì)中接線箱分配最優(yōu)化的問題，通過分析和比較各種聚類方法，對模糊C-均值聚類算法進(jìn)行改進(jìn)和參數(shù)設(shè)置，通過初始化、迭代、解模糊及分裂等步驟，實(shí)現(xiàn)了接線箱的自動(dòng)分配功能。并設(shè)計(jì)了一種基于改進(jìn)的模糊C-均值聚類算法的接線箱分配輔助軟件，可以根據(jù)不同要求自動(dòng)分配接線箱的功能，給出了軟件流程，分析了實(shí)驗(yàn)結(jié)果，并在某設(shè)計(jì)院項(xiàng)目接線箱的實(shí)際布置中成功應(yīng)用。

模糊C-均值聚類 接線箱自動(dòng)分配 模糊聚類 軟件流程

工程設(shè)計(jì)流程具有事情多、時(shí)間緊、任務(wù)重的特點(diǎn)。其中，接線箱分配是工程設(shè)計(jì)中重要的一環(huán)，需要考慮箱柜的位置、數(shù)量及電纜的總長度等問題，這不僅占用了工程師大量的時(shí)間，同時(shí)由于所涉及的數(shù)據(jù)量巨大，即使有經(jīng)驗(yàn)的工程師也很難做到線纜布置的最優(yōu)化，而由于不同的配線方案所產(chǎn)生的電纜變化量往往能達(dá)到10%～20%，這不僅直接影響到工程造價(jià)，而且效率低、浪費(fèi)嚴(yán)重。因此，解決接線箱的優(yōu)化分配設(shè)計(jì)問題具有重要的實(shí)際意義。

聚類，就是把具有相似性質(zhì)的事物區(qū)分開來加以分類。聚類分析就是用數(shù)學(xué)方法研究和處理給定對象的分類。模糊聚類建立了樣本對類別的不確定性描述，能夠有效地對類與類之間交叉的數(shù)據(jù)集進(jìn)行聚類，能夠更客觀地反映現(xiàn)實(shí)世界，因而成為聚類分析研究的主流。模糊聚類算法作為應(yīng)用最廣泛的聚類算法之一，具有簡單、收斂速度快及能夠處理大規(guī)模數(shù)據(jù)等優(yōu)點(diǎn)，因此，該算法不僅被有效地應(yīng)用于數(shù)據(jù)挖掘、模式識(shí)別及決策支持等領(lǐng)域[1,2]，在工程設(shè)計(jì)領(lǐng)域也有著廣泛的應(yīng)用。如耿志強(qiáng)和朱群雄將C-means聚類應(yīng)用于乙烯裂解爐的生產(chǎn)過程優(yōu)化中，通過引入Mercer條件的核函數(shù)，克服模糊C-均值聚類在各分量方差分布不均或交叉分布情況下存在的錯(cuò)分現(xiàn)象[3]；劉遠(yuǎn)紅等利用k-means聚類算法識(shí)別原油油水界面[4]；周強(qiáng)和韓九強(qiáng)將動(dòng)態(tài)聚類用于紙張緊度的在線檢測，通過K均值聚類算法預(yù)處理訓(xùn)練樣本，以平滑優(yōu)化途徑[5]；俞樹榮等結(jié)合模糊聚類方法與人工神經(jīng)網(wǎng)絡(luò)技術(shù)，提高了壓力容器安全評定的可靠性和水平[6]。

在接線箱優(yōu)化分配設(shè)計(jì)過程中，由于每個(gè)接線箱中端子排的數(shù)量、每個(gè)端子排的端子數(shù)都有設(shè)定的最大值，因此屬于每一類樣本數(shù)固定，而分類數(shù)不確定的動(dòng)態(tài)模糊聚類。然而，由于閾值無法確定，無法簡單地基于模糊等價(jià)矩陣按要求做到有效的分類。模糊C-均值(FCM)聚類是最為經(jīng)典的分類數(shù)給定的聚類算法[7，8]，但也有著很大的局限性，如聚類數(shù)、聚類初始中心和加權(quán)指數(shù)的選擇都極大地影響著聚類效果[9，10]。筆者針對工程設(shè)計(jì)中接線箱優(yōu)化分配的實(shí)際問題，提出一種基于改進(jìn)的模糊C-均值聚類的接線箱最優(yōu)分配模型。改進(jìn)了文獻(xiàn)[7，8]中的模糊C-均值聚類算法，同時(shí)進(jìn)行參數(shù)設(shè)置，將分配問題轉(zhuǎn)換為目標(biāo)函數(shù)的優(yōu)化問題，給出了求解算法，還給出了基于改進(jìn)模糊C-均值聚類算法的接線箱分配輔助軟件流程的設(shè)計(jì)方案，并分析了實(shí)驗(yàn)結(jié)果。

1 FCM聚類算法

FCM將n個(gè)向量分成c個(gè)模糊組，定義每一個(gè)類有一個(gè)聚類中心，再根據(jù)向量與聚類中心的距離，形成隸屬度的模糊數(shù)據(jù)集，其和總等于1，即：

(1)

(2)

利用拉格朗日乘數(shù)法，得出最佳模糊隸屬度矩陣uij和對應(yīng)的聚類中心ci的計(jì)算式如下：

(3)

(4)

FCM算法是一個(gè)簡單的迭代過程，其步驟如下：

a. 初始化聚類中心；

b. 根據(jù)式(3)計(jì)算模糊隸屬度矩陣；

c. 根據(jù)式(4)計(jì)算新的聚類中心；

2 FCM聚類算法的參數(shù)設(shè)置與算法改進(jìn)

影響FCM聚類算法的重要參數(shù)有兩個(gè)，在進(jìn)行接線箱分配時(shí)，二者的設(shè)置方法具體如下：

a. 對于加權(quán)模糊指數(shù)m的設(shè)置，Bezdek給出的經(jīng)驗(yàn)范圍是1≤m≤5；此后又得到m=2時(shí)FCM算法的物理解釋，認(rèn)為m=2最合適[11]。

b. 對于分類數(shù)c，由總樣本個(gè)數(shù)與每個(gè)聚類點(diǎn)最大值相除進(jìn)行估算，即將初始目標(biāo)設(shè)定為盡量使用最少的接線箱個(gè)數(shù)。

在FCM聚類算法迭代結(jié)束后，每個(gè)聚類中的樣本個(gè)數(shù)不一定滿足小于最大值的要求。對此，可以通過兩種方法予以解決：第1種是對每一個(gè)聚類點(diǎn)進(jìn)行解模糊運(yùn)算時(shí)，當(dāng)一個(gè)聚類點(diǎn)數(shù)量已滿后，將其他本屬于該聚類點(diǎn)的樣本放入下一個(gè)最近的聚類點(diǎn)(即一個(gè)接線箱放滿后，將放不下的測量點(diǎn)分配至下一個(gè)最近的接線箱)；第2種方法是解模糊后，對聚類進(jìn)行分裂處理，將超過最大值的聚類分成多個(gè)。顯然，第1種方法可以得到更少的聚類點(diǎn)數(shù)量(即接線箱數(shù)量)，第2種方法可以得到更小的價(jià)值函數(shù)值(即電纜總長度)。在實(shí)際工程中，權(quán)衡接線箱和電纜的成本后，再?zèng)Q定所使用的方法。

對于初始聚類中心的選取，由于該算法對初始點(diǎn)的依賴大，如果初始分類選擇不當(dāng)，將會(huì)收斂成為一個(gè)局部最小的函數(shù)，導(dǎo)致結(jié)果不穩(wěn)定[12～14]。通過密度法選擇初始聚類中心，首先計(jì)算每個(gè)樣本的密度(即以該樣本為中心的一個(gè)球形區(qū)域內(nèi)樣本點(diǎn)的個(gè)數(shù))，選取密度最大的樣本作為第1個(gè)初始聚類中心；然后在離開第1個(gè)初始聚類中心的球形區(qū)域外，選擇密度第2大的點(diǎn)作為第2個(gè)聚類中心，這樣就避免了聚類中心過分集中的現(xiàn)象。依此類推，選出所有的初始聚類中心。

3 系統(tǒng)實(shí)現(xiàn)

3.1系統(tǒng)結(jié)構(gòu)

基于改進(jìn)的模糊C-均值聚類算法的接線箱分配系統(tǒng)的軟件流程(圖1)分為兩個(gè)步驟：首先通過模糊C-均值算法將測量點(diǎn)聚類成端子排；然后通過同樣的算法將端子排聚類成接線箱。

圖1 基于改進(jìn)的模糊C-均值聚類算法的接線箱分配系統(tǒng)程序流程

3.2軟件實(shí)現(xiàn)

基于改進(jìn)的模糊C-均值聚類算法的接線箱分配系統(tǒng)軟件采用VBA語言編寫，適用于Windows平臺(tái)。在實(shí)際應(yīng)用中，該軟件在AutoCAD下運(yùn)行，采用Access作為數(shù)據(jù)庫進(jìn)行數(shù)據(jù)處理。工程師在對話框輸入對現(xiàn)場接線箱的要求，該軟件將根據(jù)要求讀取布置圖中的測量點(diǎn)信息，寫入Access數(shù)據(jù)庫；然后通過改進(jìn)的FCM算法得出接線箱的數(shù)量、分配和布置。

先由工程師輸入設(shè)計(jì)需求：模擬量輸入(AI)、輸出(AO)信號(hào)是否可在同一個(gè)端子排中；能否包含三線制溫度計(jì)(RTD)的端子排；模擬量信號(hào)和數(shù)字量信號(hào)能否放進(jìn)同一個(gè)接線箱；每個(gè)端子排最多包含的回路數(shù)；每個(gè)接線箱最多包含的端子排數(shù)；電磁閥箱最多包含的回路數(shù)等信息。按照上述要求實(shí)現(xiàn)的界面如圖2所示。

圖2 箱柜分配清單界面

通過自動(dòng)運(yùn)算可以得出箱柜清單、每個(gè)箱柜中端子排的清單和每個(gè)端子排上的儀表清單，并在布置圖中標(biāo)示出接線箱的參考位置，為設(shè)計(jì)提供決策支持，如圖3所示。

圖3 箱柜參考位置

4 運(yùn)行結(jié)果分析

使用某項(xiàng)目手工進(jìn)行接線箱分配的結(jié)果與基于改進(jìn)模糊C-均值聚類算法的分配結(jié)果進(jìn)行比較，詳見表1。在實(shí)際測試中，歐氏距離和電纜長度之間存在相當(dāng)高的一致性，使用基于改進(jìn)的模糊C-均值聚類算法的計(jì)算結(jié)果比人工分配節(jié)省了10%～15%的電纜，并得到了更優(yōu)化的分配方案。

表1 手工與改進(jìn)FCM接線箱分配結(jié)果對比

以某項(xiàng)目中電磁閥箱的分類為例，圖4、5分別表示手工分配和改進(jìn)的模糊C-均值聚類算法分析的效果。可以明顯看出，使用本軟件后，樣本根據(jù)空間中的位置被有效分割。

圖4 人工聚類結(jié)果

圖5 改進(jìn)的模糊C-均值聚類結(jié)果

5 結(jié)束語

根據(jù)某設(shè)計(jì)院實(shí)際項(xiàng)目接線箱的布置圖數(shù)據(jù)，采用改進(jìn)的模糊C-均值聚類算法對它進(jìn)行分類，得到隸屬度矩陣和聚類中心。根據(jù)隸屬度矩陣進(jìn)行分類，克服了人工分類方法效率低、主觀隨意性強(qiáng)、速度緩慢及無法得出最優(yōu)解等問題。另外，通過該軟件計(jì)算出來的聚類點(diǎn)坐標(biāo)，可以就近確定接線箱的位置，提高了施工圖設(shè)計(jì)效率，節(jié)省了項(xiàng)目成本。基于改進(jìn)的模糊C-均值聚類的接線箱分配系統(tǒng)，對接線箱優(yōu)化分配設(shè)計(jì)的方法具有一定的通用性和擴(kuò)展性。

[1] Bezdek J C,Robert E,William F.The Fuzzy C-Means Clustering Algorithm[J].Computers and Geosciences,1994,10(2):191～203.

[2] Dave R N.Robust Fuzzy Clustering Algorithms[C].Second IEEE International Conference on Fuzzy System.San Francisco:IEEE,1993:1281～1286.

[3] 耿志強(qiáng),朱群雄.動(dòng)態(tài)核聚類算法在乙烯生產(chǎn)中的優(yōu)化模式識(shí)別[J].化工自動(dòng)化及儀表,2005,32(2):5～8.

[4] 劉遠(yuǎn)紅,習(xí)玉陽,吳華遠(yuǎn),等.k-means聚類算法在油水界面檢測中的應(yīng)用[J].化工自動(dòng)化及儀表,2014,41(1):19～21.

[5] 周強(qiáng),韓九強(qiáng).基于動(dòng)態(tài)聚類算法的CWNN在紙張緊度檢測中的應(yīng)用[J].化工自動(dòng)化及儀表,2006,33(4):14～18.

[6] 俞樹榮,李爾國,梁瑞.基于人工神經(jīng)網(wǎng)絡(luò)的壓力容器安全評定可靠度的模糊分析[J].化工機(jī)械,2000,27(6):333～335.

[7] Dunn J C.A Fuzzy Relative of the ISODATA Process and Its Use in Detectiong Compact Well-separated Clusters[J].Journal of Cybernetics,1973,3(3):32～57.

[8] Bezdek J C.Pattern Recognition with Fuzzy Objective Function Algorithms[M].New York:Plenum Press,1981.

[9] 高新波,謝維信.模糊C-均值聚類算法中加權(quán)指數(shù)m的研究[J].電子學(xué)報(bào),2000,28(4):80～83.

[10] 張姣玲.利用FCM求解最佳聚類數(shù)的算法[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(22):65～67.

[11] Castleman K R,著,朱志剛,林學(xué)閆,石定機(jī),等,譯.數(shù)字圖像處理[M].北京:電子工業(yè)出版社,1998:378～379.

[12] Bradley P S,Fayyad U M.Refining Initial Points for k-Means Clustering[C].Proceedings of the 15th International Conference on Machine Learning.San Francisco:Morgan Kaufmann,1998:91～99.

[13] Berkhin P.Survey of Clustering Data Mining Techniques[M].San Jose:Accrue Software Inc,2002.

[14] Duda R O,Hart P E.Pattern Classification and Scene Analysis[M].New York:Wiley,1973.

JunctionBoxesAllocationandApplicationBasedonImprovedFuzzyC-meansClusteringAlgorithm

LIU Di-cheng, WANG Jian, WANG Min-hao

(ChinaHaisumEngineeringCo.,Ltd.,Shanghai200031,China)

To optimize the allocation of junction boxes in engineering design, various clustering methods were analyzed and compared; and fuzzy C-means clustering algorithm was improved and relevant parameters were set; through initialization, iteration, defuzzification and split operation, the auto-allocation of junction boxes was realized. An improved C-means clustering algorithm-based assistive software for the auto-allocation of junction boxes was developed to allocate junction boxes as requested automatically; and the software flow chart was presented, including experimental results. This software enjoys successfully application in a design institute.

fuzzy C-means clustering,auto-allocation of junction boxes, fuzzy clustering, software flow chart

TH862+.7

B

1000-3932(2016)09-0962-04

2016-06-11(修改稿)