一種面向訂單剩余完工時間預(yù)測的SOM-FWFCM特征選擇算法

劉道元 郭 宇 黃少華 方偉光 楊能俊 崔世婷

南京航空航天大學(xué)機電學(xué)院，南京，210016

0 引言

日益激烈的市場競爭和復(fù)雜多變的客戶需求對制造企業(yè)縮短產(chǎn)品生產(chǎn)周期、按時交付訂單提出了更高的要求，訂單剩余完工時間的準確預(yù)測能夠為動態(tài)的生產(chǎn)計劃調(diào)整、生產(chǎn)過程優(yōu)化提供合理的判別依據(jù)，對訂單產(chǎn)品的準時完工具有重要的指導(dǎo)意義[1]。在當前生產(chǎn)方式靈活、產(chǎn)品種類繁多的離散制造車間中，智能傳感器的大量應(yīng)用為預(yù)測訂單剩余完工時間提供了海量的生產(chǎn)數(shù)據(jù)[2]，但同時也帶來了“維度災(zāi)難”的問題，因此有必要設(shè)計一種合理的特征選擇方法來有效地從眾多特征中獲取關(guān)鍵特征，以降低求解問題的復(fù)雜度，提高預(yù)測模型與實際生產(chǎn)運行規(guī)律的擬合度，保證預(yù)測的準確性。

特征選擇是指從候選特征中挑選若干個具有代表性的特征組成關(guān)鍵特征子集，當前的主要研究方法包括封裝式和過濾式特征選擇算法。

封裝式特征選擇算法需要對每個特征子集進行學(xué)習(xí)器訓(xùn)練，根據(jù)學(xué)習(xí)器性能選擇關(guān)鍵特征子集。相關(guān)學(xué)者使用量子遺傳算法[3]、改進粒子群算法和禁忌搜索相結(jié)合[4]、粗糙集相對分類信息熵和粒子群算法相結(jié)合[5]的方法進行特征選擇，首先對每個特征進行編碼，然后根據(jù)學(xué)習(xí)器的預(yù)測結(jié)果計算適應(yīng)度值，不斷迭代至收斂，最后選擇適應(yīng)度值最高的特征子集作為關(guān)鍵特征子集。ZHONG等[6]使用SVM-RFE算法構(gòu)建特征空間，然后使用皮爾森系數(shù)剔除特征空間中有相同意義的特征，最終從26個候選特征中選擇6個特征組成最優(yōu)特征子集。DY等[7]使用期望最大化算法選擇特征，以特征子集的分散可分性和最大似然為評價指標，經(jīng)過多次修改算法參數(shù)，選擇評價最優(yōu)的特征子集。上述封裝式特征選擇算法能得到高質(zhì)量的特征子集，但每次迭代都需要訓(xùn)練學(xué)習(xí)器，導(dǎo)致計算復(fù)雜度高，不適合處理大規(guī)模數(shù)據(jù)[8]。

過濾式特征選擇算法直接通過某種準則選擇關(guān)鍵特征子集，再訓(xùn)練后續(xù)學(xué)習(xí)器，特征選擇過程與學(xué)習(xí)器無關(guān)，在處理大規(guī)模數(shù)據(jù)方面，降低了計算復(fù)雜度，運行效率較高。朱雪初等[9]使用運行效率高、對噪聲有一定容錯能力的ReliefF算法進行特征選擇，考慮各特征與預(yù)測目標的相關(guān)性但忽略了特征間的冗余性?；谧畲笙嚓P(guān)性-最小冗余性原則，PENG等[10]和夏虎等[11]分別使用互信息和皮爾森系數(shù)計算參數(shù)間的相關(guān)性和冗余性，完成最佳特征子集的選擇。為了提高關(guān)鍵特征子集的質(zhì)量和后續(xù)學(xué)習(xí)器的精度，特征選擇不僅要滿足最大相關(guān)性-最小冗余性原則，還需要最大化特征間的多樣性[12]。LIU等[13]通過互信息和關(guān)聯(lián)系數(shù)分別衡量類間和類內(nèi)距離，將標簽數(shù)據(jù)作為單獨一類，采用類似于凝聚層次聚類的算法確定關(guān)鍵特征子集。ZHOU等[14]以屬性間的最大信息系數(shù)作為距離矩陣，使用K-mode算法對屬性進行聚類完成特征選擇。WITTEN等[15]提出稀疏聚類框架，使用稀疏K均值聚類和稀疏層次聚類算法相結(jié)合的方法完成特征選擇。

在上述基于聚類的特征選擇方法中，減少了特征間的冗余性，保證了特征間的多樣性，但每個特征對預(yù)測目標解釋能力不同，需要根據(jù)特征的解釋能力來指導(dǎo)特征聚類。本文在特征聚類過程中引入描述特征對預(yù)測目標解釋能力的特征權(quán)重，解釋能力越強的特征在計算聚類中心時貢獻越大，選擇其為關(guān)鍵特征的概率越高，通過綜合考慮關(guān)鍵特征子集的冗余性、多樣性以及與目標的相關(guān)性，實現(xiàn)關(guān)鍵特征的準確選擇。

本文提出了一種基于自組織映射(self-organizing map, SOM)網(wǎng)絡(luò)-特征權(quán)重模糊C均值(feature weighted fuzzy C-means, FWFCM)聚類的過濾式特征選擇算法，利用SOM網(wǎng)絡(luò)為FWFCM算法提供初始簇中心，以避免FWFCM算法對初始聚類中心敏感、容易陷入局部最優(yōu)的問題；將基于互信息的特征與目標相似度作為特征權(quán)重，使特征聚類過程具有一定的導(dǎo)向性，進一步改善聚類效果和提高關(guān)鍵特征子集質(zhì)量。最后結(jié)合某航天機加工車間提供的19 428條具有1102個特征的生產(chǎn)數(shù)據(jù)，進行算法的實例驗證和對比分析，證明了所提方法的有效性。

1 問題描述

訂單剩余完工時間(order remaining completion time, ORCT)是指從當前時刻開始到訂單所有零件產(chǎn)出的時間長度，即TORC=Tfin-Tcur，其中，Tfin表示訂單所有零件產(chǎn)出時刻，Tcur表示當前時刻。在復(fù)雜離散制造系統(tǒng)中，影響訂單完工時間的不確定因素很多，為便于討論，本文考慮的制造過程遵循以下原則：①離散制造車間中有M個工位，用于生產(chǎn)P類不同零件，每個工位都包含一臺機床、一個入緩存區(qū)和一個出緩存區(qū)；②每個零件有唯一確定的加工路線；③每個在制品在同一臺機床上只加工一次；④選擇入/出緩存區(qū)在制品運輸/加工遵循先入先出的原則；⑤在制品準備加工時間包含在在制品加工時間內(nèi)，在制品在固定兩個工位之間的運輸時間設(shè)為常數(shù)。

基于上述原則，訂單剩余完工時間主要取決于在制品在入/出緩存區(qū)的等待時間和在制品在所有工位上的加工時間。緩存區(qū)在制品種類、數(shù)量和優(yōu)先級對訂單完成加工時間有著重要的影響[16]。在制品在某個工位的生產(chǎn)過程可以分為以下3個步驟：①在制品從上個工位運輸?shù)酱斯の?，進入入緩存區(qū)等待加工；②在機床上完成加工；③進入出緩存區(qū)等待運輸?shù)较乱粋€工位。

根據(jù)上述車間特點，將車間生產(chǎn)任務(wù)、實時生產(chǎn)狀態(tài)以及生產(chǎn)統(tǒng)計數(shù)據(jù)三類信息作為候選特征。定義所有候選特征組成的集合為候選特征集。車間生產(chǎn)任務(wù)包含一個/多個訂單中各類零件數(shù)量；實時生產(chǎn)狀態(tài)包括入/出緩存區(qū)在制品隊列、每臺機床正在加工的在制品種類以及正在運輸?shù)脑谥破沸畔⑺念愒谥破窢顟B(tài)信息，還包括設(shè)備狀態(tài)(“加工中”“等待中”“故障中”“維修中”)和設(shè)備負載兩類設(shè)備運行狀態(tài)信息；生產(chǎn)統(tǒng)計數(shù)據(jù)包括機床正在加工的在制品加工時長、機床利用率及其持續(xù)加工時長、訂單中各類未開工零件數(shù)。

車間各生產(chǎn)要素相互影響，部分數(shù)據(jù)特征相互依賴，候選特征集具有一定的冗余性。冗余特征會造成計算復(fù)雜度急劇上升、預(yù)測模型訓(xùn)練困難及精度下降等問題，所以提出一種基于SOM-FWFCM的特征選擇算法來實現(xiàn)關(guān)鍵特征選擇，減少計算復(fù)雜度，提高預(yù)測精度。

2 特征選擇算法

圖1 基于SOM-FWFCM算法的特征選擇流程圖Fig.1 Flow chart of feature selection based onSOM-FWFCM algorithm

SOM-FWFCM是一種在聚類過程中考慮特征與預(yù)測目標之間相關(guān)性的過濾式特征選擇算法，擺脫了FWFCM算法需設(shè)置初始聚類中心的困擾，避免了聚類過程的盲目性，實現(xiàn)了高質(zhì)量的關(guān)鍵特征選擇，算法的總體流程如圖1所示。首先通過互信息[17]量化特征與目標之間的關(guān)聯(lián)關(guān)系程度來定義任意特征對預(yù)測目標的重要因子，即特征權(quán)重；其次將候選特征集輸入SOM網(wǎng)絡(luò)，確定FWFCM的初始聚類中心和簇數(shù)；然后不斷迭代更新FWFCM的聚類中心和特征隸屬度，實現(xiàn)導(dǎo)向性特征聚類；最后剔除冗余特征，得到訂單剩余完工時間預(yù)測的關(guān)鍵特征子集。

2.1 特征權(quán)重

互信息是一個隨機變量包含另一個變量的信息量的度量，能夠表達任意特征與輸出向量之間的相關(guān)程度[18]。兩個隨機變量x和變量y的互信息定義如下：

(1)

其中，l表示隨機變量x或變量y的維數(shù)，x={x1,x2,…,xl}，y={y1,y2,…,yl}，I(x,y)表示變量x和變量y的互信息，p(xi,yj)表示x=xi且y=yj的概率，p(xi)表示x=xi的概率，p(yj)表示y=yj的概率。當變量x和變量y相互獨立時，p(xi,yj)=p(xi)p(yj)，互信息I(x,y)=0；變量x包含變量y信息量越多，互信息I(x,y)的值越大。

任意特征對預(yù)測目標的解釋能力可以用互信息衡量，換言之，互信息可以量化任意特征對預(yù)測目標的重要程度。定義描述特征重要程度的特征權(quán)重為

(2)

其中，wi表示第i個特征的權(quán)重，I(fxi,fy)表示第j個特征fxi與預(yù)測目標fy的互信息，n表示候選數(shù)據(jù)特征集的特征數(shù)。I(fxi,fy)的值越大，對目標的解釋能力越強，特征越重要，特征權(quán)重越大。

2.2 SOM-FWFCM算法

SOM網(wǎng)絡(luò)能夠自動對輸入數(shù)據(jù)進行聚類，并且容易實現(xiàn)，但精確度不高；而模糊C均值(FCM)算法具有良好的聚類準確度，但聚類前必須確定初始聚類中心或初始隸屬度。本文將SOM網(wǎng)絡(luò)和FCM算法相結(jié)合，保證FCM算法初始聚類中心的可靠性，提高聚類結(jié)果的準確度。

SOM網(wǎng)絡(luò)將高維特征集映射到低維空間(一般為二維)，并擁有在高維空間的拓撲結(jié)構(gòu)[19]。將某個特征輸入SOM網(wǎng)絡(luò)中，計算輸出層獲勝神經(jīng)元，即該特征在低維空間中的位置，映射在同一位置的輸入特征劃分為同一簇。在訓(xùn)練網(wǎng)絡(luò)過程中，首先確定輸出層拓撲結(jié)構(gòu)(a×a)，初始化權(quán)向量W，設(shè)定初始學(xué)習(xí)率及迭代次數(shù)；然后計算輸入特征對應(yīng)的獲勝神經(jīng)元，根據(jù)獲勝神經(jīng)元確定周邊興奮神經(jīng)元的空間位置，即優(yōu)勢領(lǐng)域；最后更新興奮神經(jīng)元攜帶的權(quán)向量，縮小權(quán)向量與輸入特征集之間的距離，不斷迭代直至最大迭代次數(shù)。權(quán)向量更新規(guī)則如下：

Wi,j=Wi,j+η(t)|pxi-Wi,j|

(3)

(4)

(5)

其中，Wi,j表示第i個輸入神經(jīng)元節(jié)點與第j個輸出神經(jīng)元之間的連接權(quán)重，η(t)表示第t次循環(huán)的學(xué)習(xí)率，pxi表示第i個輸入神經(jīng)元的輸入，η0表示初始學(xué)習(xí)率，r(t)表示t次循環(huán)的優(yōu)勢領(lǐng)域半徑，T表示最大迭代次數(shù)。

FCM算法[20]通過隸屬度確定每個對象屬于某個聚類的程度，最大化同一簇對象的相似度，同時最小化不同簇之間對象的相似度。與隸屬度只能為0或1的硬聚類算法相比，F(xiàn)CM算法更加符合現(xiàn)實要求，有著更好的聚類精度。FCM算法在訓(xùn)練迭代過程中，僅根據(jù)特征空間分布情況進行標記，完全獨立于預(yù)測目標，這導(dǎo)致聚類缺乏一定的導(dǎo)向性。特征權(quán)重搭建特征與預(yù)測目標關(guān)聯(lián)的橋梁，特征權(quán)重值越大，該特征對預(yù)測目標的影響越大，被選擇為特征代表的可能性越大，在聚類過程中將其加以考慮，提高關(guān)鍵特征選擇的有效性和預(yù)測準確度。本文稱引入特征權(quán)重的FCM算法為FWFCM算法。定義FWFCM算法的數(shù)學(xué)模型如下：

(6)

(7)

其中，J表示FWFCM算法的目標函數(shù)；kc表示聚類中心數(shù)；wj表示第j個特征權(quán)重；μi,j表示第j個特征屬于第i個聚類中心的隸屬度；m表示模糊權(quán)重，取值范圍為[1,∞]，通常取m=2[21]，ci表示第i個聚類中心。

將上述有條件極值問題轉(zhuǎn)化為無條件極值問題，構(gòu)造拉格朗日函數(shù)，引入拉格朗日因子，使得目標函數(shù)取得極小值，即

(8)

(9)

(10)

(11)

i=1,2,…,kcj=1,2,…,q

其中，λ表示拉格朗日因子，λ={λ1,λ2,…,λn}，Δf表示第t次相對于上次的隸屬度改變量最大值。FWFCM算法迭代過程如下：①使用式(10)～式(11)計算每個特征的權(quán)重；②根據(jù)SOM網(wǎng)絡(luò)得到初步的聚類結(jié)果及FWFCM的初始聚類中心，并初始化隸屬度矩陣；③計算每個特征的隸屬度，若Δf小于預(yù)設(shè)閾值，則算法結(jié)束，否則轉(zhuǎn)入步驟④；④更新kc個聚類中心，轉(zhuǎn)入步驟③。

FWFCM算法迭代結(jié)束后，根據(jù)隸屬度矩陣對各特征進行類別劃分，選取離簇中心最近的特征為該類的特征代表，構(gòu)成關(guān)鍵特征子集。

3 案例分析

本文以某航天機加車間的19 648條生產(chǎn)數(shù)據(jù)為例進行實例驗證，將候選特征集輸入SOM-FWFCM、FWFCM、SOM-FCM、層次聚類[13](hierarchical clustering, HC)和權(quán)重K均值(weighted K-means，WK-means)聚類五種特征選擇算法中，得到關(guān)鍵特征子集，以關(guān)鍵特征子集為輸入訓(xùn)練人工神經(jīng)網(wǎng)絡(luò)(artificial neural network, ANN)完成剩余完工時間預(yù)測，對比分析聚類性能和預(yù)測結(jié)果準確度，驗證本文所提方法的有效性。

通過反復(fù)試驗，選擇特征選擇算法性能較好的參數(shù)如下：SOM網(wǎng)絡(luò)結(jié)構(gòu)為15×15，迭代次數(shù)為100，初始學(xué)習(xí)率為0.5，F(xiàn)WFCM算法閾值為0.001。在聚類過程中，候選特征集屬于無類別標簽數(shù)據(jù)，選用Calinski-Harabaz(CH)系數(shù)和輪廓系數(shù)(silhouette coefficient, SC)度量聚類性能，計算公式如下：

(12)

(13)

(14)

(15)

表1 不同算法的聚類結(jié)果分析

根據(jù)SOM-FWFCM算法從1102個候選特征中選擇69個特征構(gòu)成關(guān)鍵特征子集，見表2，將其輸入ANN中，對比預(yù)測值與實際值的差值。若差值越小，表示預(yù)測越準確，所選特征越有效，特征選擇算法越具有優(yōu)越性。

表2 訂單剩余完工時間預(yù)測關(guān)鍵特征子集

本文使用常用的均方根誤差(root mean square error, RMSE)、平均絕對誤差(mean absolute error, MAE)、平均絕對百分比誤差(mean absolute percentage error, MAPE)來評價預(yù)測準確性，計算公式如下：

(16)

(17)

(18)

在ANN訓(xùn)練過程中，以RMSE值與L2正則項之和為損失函數(shù)，并加入Dropout層[22]，改善網(wǎng)絡(luò)的過擬合現(xiàn)象。如圖2所示，紅色線表示訓(xùn)練集優(yōu)化過程，藍色線表示測試集的測試過程。在網(wǎng)絡(luò)優(yōu)化過程中，模型以較快的收斂速度收斂至較小值，并且具有較強的泛化能力，即訓(xùn)練集預(yù)測誤差和測試集預(yù)測誤差接近。圖3描述的是從測試集中隨機挑選200個樣本作為預(yù)測對象，紅色線表示樣本真實值，藍色線表示對應(yīng)樣本的預(yù)測值。由圖3可以看出，預(yù)測值與實際值的變化方向和幅度非常接近，并且預(yù)測值與實際值幾乎重合。由于車間存在不確定的擾動，導(dǎo)致圖3中極小部分預(yù)測值偏離實際值，造成預(yù)測不準確的假象，但總體而言，本文方法得到的剩余完工時間

圖2 SOM-FWFCM-ANN的優(yōu)化過程Fig.2 Optimization process of SOM-FWFCM-ANN

圖3 SOM-FWFCM-ANN的預(yù)測結(jié)果Fig.3 Prediction results of SOM-FWFCM-ANN

預(yù)測值具有較高的準確度，能夠滿足現(xiàn)實車間生產(chǎn)要求。

為驗證本文所提出的特征選擇方法的有效性，進行以下實驗：使用上述5種特征選擇算法篩選得到相應(yīng)的具有69、62、91、102、100個特征的關(guān)鍵特征子集，對不同的關(guān)鍵特征子集搭建ANN，預(yù)測訂單剩余完工時間，5種算法分別簡稱為SOM-FWFCM-ANN、FWFCM-ANN、SOM-FCM-ANN、HC-ANN 、WK-means-ANN。如圖4所示，分別以藍色線、綠色線、紅色線、青色線、黃色線表示這5種算法在測試集上的測試過程，HC-ANN、WK-means-ANN雖然以較快的速度收斂，但由于關(guān)鍵特征子集質(zhì)量較差，導(dǎo)致推理能力欠缺，易陷入局部最優(yōu)解；相對而言前三者預(yù)測精度較高，尤其在聚類過程中引入特征權(quán)重，考慮特征與目標之間的相關(guān)性，使特征選擇過程具有一定的導(dǎo)向性，提高了關(guān)鍵特征子集質(zhì)量以及預(yù)測精度。表3通過RMSE、MAE、MAPE三個評價指標直觀地描述了5種模型與實際問題的擬合程度，可以看出SOM-FWFCM-ANN模型擬合程度最高、最準確，準確度從高到低依次是SOM-FWFCM-ANN、FWFCM-ANN、SOM-FCM-ANN、HC-ANN、WK-means-ANN。

圖4 不同模型的優(yōu)化過程Fig.4 Optimization process of different models

表3 不同模型的結(jié)果對比

從本實驗可以得到以下結(jié)論：①SOM網(wǎng)絡(luò)為FWFCM算法提供的初始聚類中心優(yōu)于隨機初始化聚類中心，提高了后者尋找最優(yōu)解的能力；②在聚類過程中考慮特征權(quán)重，增加了重要特征在迭代計算過程的影響力，提高了聚類質(zhì)量和特征選擇的有效性；③基于SOM-FWFCM的特征選擇模型能夠選擇反映車間運行規(guī)律的關(guān)鍵特征子集，減少了后續(xù)預(yù)測分析的運算復(fù)雜度，為訂單剩余完工時間的精準預(yù)測提供了基礎(chǔ)，證明了本文算法在復(fù)雜離散制造車間應(yīng)用的可行性。

4 結(jié)語

本文通過分析每個候選特征的重要程度和關(guān)鍵特征子集的冗余性和多樣性，提出了一種適用于大規(guī)模數(shù)據(jù)集的特征選擇算法，即SOM-FWFCM算法。通過分析5種特征選擇算法聚類結(jié)果的類內(nèi)凝聚度和類間分散度、訂單剩余完工時間預(yù)測值的準確度，驗證了本文所提算法的有效性。在后續(xù)研究中可以使用本文所選擇的關(guān)鍵特征進一步研究預(yù)測模型，提高預(yù)測的準確度，以及預(yù)測時發(fā)現(xiàn)車間生產(chǎn)任務(wù)不能按時完成，應(yīng)采取何種調(diào)整策略來保證訂單按時交付。