不完備信息條件下基于Roustida改進算法的診斷規則提取

李金艷, 余忠華

(1.江蘇科技大學經濟與管理學院, 鎮江 212003; 2.浙江大學機械工程學院, 杭州 310027)

診斷決策過程本質上為信息的處理過程。由于信息結構的復雜性和采集的局限性使得獲取的信息常常存在著缺失、模糊、冗余等不完備現象。如何基于不完備信息進行診斷決策已經成為重要的研究課題。

目前數據值缺失的處理主要有缺損信息刪除、可能值插補以及數據挖掘三種方式[1]。刪除含有缺失值樣本/信息項的方式在樣本量不充足或信息維度較高時,易造成信息浪費;數據挖掘方式則是利用貝葉斯[2]、模糊集[3]或證據理論[4]等方法通過建立概率密度函數、隸屬度函數或信任函數等直接進行知識挖掘,數據值缺失形成的不確定性對挖掘效果有較大影響的同時,計算復雜度和難度亦是需要考慮的問題[5];可能值插補[6]方式分為統計插補[7]和數據挖掘插補[8],均為數據背景下的估計補齊且均建立在大樣本的基礎上,插補結果滿足統計意義上的合理,工程實踐應用時往往無從解釋或修正。粗糙集理論(rough set,RS)初始對不完備信息的研究主要集中在缺失值屬性處理、不完備對象間相似關系模型建立等方面[9]。經后續基于容差關系、基于量化容差、基于相似關系以及基于限制容差關系等的擴展研究[10],文獻[11]認為擴展研究可以進一步實現探尋信息之間的內在聯系,數據插補可以提高信息的表層完整性,二者的結合則可以更好地為知識挖掘奠定基礎。屬性冗余一般指含有多余、無用的信息在其中,進行認知時需對信息降維以消除其中的冗余、噪聲等,常用方式有特征選擇與特征提取。特征選擇[12]是從數據集的原始特征中選擇一個特征子集,組成可反映原始特征的低維空間。特征提取[13]則是通過線性或者非線性的方式對原始數據空間進行映射變換,生成維數低且相互獨立的特征空間,提取后的新特征是原特征的映射。針對具有冗余性、相關性以及稀疏性等特征的數據集,特征提取可以規避以上缺點,提高數據處理效率的同時保持較好的分類精度,但并存的缺點是所得特征的可理解性差。在盡量不改變原數據信息構成的處理需求下,特征選擇更具優勢。

粗糙集理論對不確定知識的處理雖然有效[14],但未含處理不完備或不確定原始數據的機制,在解決專業領域問題時需要其他方法補充提高數據分類能力,如與統計方法[15]、證據理論[16]、貝葉斯[17]、遺傳算法[18]、模糊集[19]、Petri網[20]、神經網絡[21]等。圍繞通過問題聚類探尋診斷規則的目標,粗糙集與適當方法結合,從既定的相關情境信息和問題描述出發,通過辨識矩陣和等價類確定問題診斷的近似域,進而挖掘問題發生的隱含知識/規律,無論在理論上還是應用方面都有待深入研究的價值。為此,以信息不完備情形下的診斷決策為研究對象,基于粗糙集理論,首先針對Roustida算法在缺失值處理時存在的局限性進行改進,擴充其在工程實踐中的適用范圍;然后在擴充辨識矩陣一致性檢測的基礎上,利用遺傳算法和廣義診斷規則推理進行特征選擇與規則凝練,力求以相對較簡方式表達問題征兆與情境域信息之間的關聯關系,實現問題診斷決策的條件屬性約簡與規則提取。

1 信息表征與改進算法

1.1 信息表征

根據RS信息決策表的定義對診斷情境信息進行描述,確定由情境域構成的條件屬性集合和由問題征兆組成的決策屬性集合。

定義1四元組S=,其中:

(1)對象集合U={ui|i=1,2,…,n}為問題域。

(2)屬性集合A={ak|k=1,2,…,m},A=C∪D且C∩D=?,即屬性集合由條件屬性集合C與決策屬性集合D組成。

(3)值域集合V=∪Va,其中Va表示屬性a的值域。

(4)f為UA→V的函數,實現對象的屬性賦值。

數據值缺失類型從產生根源角度可分為:①無法取值——生產模式及相關工藝更新,加工要求產生變化,條件屬性隨著工藝的調整會發生“必要→一般→無關”的更迭變化,導致信息采集、統計時無法填入屬性值的現象。②存在但暫時無法獲知——條件限制,并非所有狀態信息都可以在既定的時間內獲得。研究數據信息缺失情況時,一般即指該類屬性值缺失。③待定——伴隨信息技術發展,大量高速、實時數據日趨常態化,加上工藝的復雜性和更新交替的快速性,認知和描述能力有限的情況下,一些診斷信息無法確定是暫時缺失還是本身便無法填入,需要隨著時間的推移方能確認。

1.2 改進算法

Roustida算法利用信息間的不可分辨關系選取相似樣本的相應值對缺失數據進行修補。該算法存在一定的局限性,以下情況無法處理:①存在缺失值的實例與其他任何樣本對象均不相似;②存在屬性值缺失的實例對象與多個樣本對象相似。因此,需要對該算法進行改進,以拓展其適用性。

定義2設ΞS=,A=C∪D,C∩D=?,缺失屬性集A*、屬性缺失對象集U*和不可辨識對象集IND分別為

(1)

(2)

U*={ui|?ak∈A[ak(ui)=*],i=1,2,…,n;k=1,2,…,m}

(3)

IND={indi},indi={uj|M(ui,uj)=?,i≠j}

(4)

其中辨識矩陣

(5)

式中:“∧”為邏輯與,表示同時成立的關系。

若ui與其他任何對象都不相似,即|indi|=?,傳統Roustida算法便無法處理,需結合相關領域背景知識對indi進行相似性拓展:通過問題歸類(決策屬性),利用其中與之相似程度較高的樣本對象的相應屬性值進行插補。

定義3擴展相似對象集ind′i:對象ui的擴展相似對象集為

ind′i={uj|D(ui)=D(uj),i≠j,j=1,2,…,n}

(6)

定義4相似度|simij|:?uj∈ind′i,對象uj與ui的等值屬性集為

simij={ak|ak(ui)=ak(uj)∧ak(ui)≠*∧ak(uj)≠*,k=1,2,…,m}

(7)

對象uj與ui的相似度為|simij|。

定義5次相似對象集ind″i:對象ui的次相似對象集

ind″i={uj|max|simij|,uj∈ind′i}

(8)

(9)

此時插補值是由群體值描述:將ui的其他完整屬性值與樣本集合中的每一個可能值進行組合,形成新的實例對象,改進算法的具體實施流程如圖1所示。

2 屬性約簡與規則提取

2.1 屬性約簡

設Ψ′=[ψ′C(ui,uj)]n×n為擴充辨識矩陣,其中ψ′C(ui,uj)表示擴充辨識矩陣中第i行第j列的元素(i,j=1,2,…,n),其取值為

圖1 Roustida改進算法的實施流程Fig.1 The implementation process of Roustida’s improved algorithm

(10)

Ψ′=[ψ′C(ui,uj)]n×n包含了所有實例對象的區分信息,其中?表示條件屬性相同,問題征兆(決策屬性)卻不同,信息表中含有矛盾信息,該條信息不可用。

針對含有的冗余信息,目前已有的約簡算法主要是圍繞條件屬性集C的核CoreD(C)通過啟發式搜索尋求最小約簡,隨著數據規模的增大,其復雜性呈指數倍增長。基于全局優化和隱含并行性的優勢,遺傳算法可以克服該問題實現求解。

設A′為擴充辨識矩陣Ψ′中所有屬性組合的集合:A′={ψ′C(ui,uj)|ui,uj∈U,i,j=1,2,…,n},不包含重復項:Bi∈A′,Bj∈A′,Bi≠Bj(i,j=1,2,…,|A′|)。結合擴充辨識矩陣Ψ′=[ψ′C(ui,uj)]n×n,獲取條件屬性最小約簡的步驟如下。

步驟1考慮情境域診斷信息特點和避免陷入局部最優,采用二進制編碼,形成|C|位二進制染色體依次對應條件屬性ci。隨機產生m個長度為|C|的二進制串作為初始種群,并進行修正以確保不存在編碼全為0的空集和全為1的全集。

步驟2圍繞診斷條件屬性約簡的目標,適應函數需要滿足:保持約簡后屬性集合的分類能力,同時確保約簡后條件屬性量相對最少。即

(11)

步驟3以f(R)為目標函數進行優化搜索。

2.2 廣義化規則提取

為實現“以相對較簡方式描述情境域信息和問題征兆之間的關聯關系”的目標,對所得規則進行如圖2所示的廣義化約簡。

圖2 廣義化約簡流程Fig.2 Generalized reduction process

2.3 評估指標

診斷規則的判斷能力可以分兩個環節來評估。

(1)屬性約簡率——評估約簡程度

(12)

P越大,原條件屬性集合中包含的冗余信息越多。

(2)覆蓋度——測度診斷效果

(13)

式(13)中:|C′(u)∩D(u)|為滿足規則ri的C′(u)和D(u)的實例數目,即支持規則ri的樣本量;|D(u)|為滿足診斷規則ri的相同問題征兆的實例數目。該指標反映了所得診斷規則的質量水平:在S中支持ri的實例在與ri具有相同問題的樣本實例中所占比率或該條規則ri是基于多少相同問題樣本提取所得。

3 應用與討論

以變進給切入式的滾動球軸承溝道磨削過程中的質量問題診斷為例,機床、砂輪、加工工藝參數等的執行狀態直接對加工結果形成影響。

3.1 信息表征

問題診斷信息表S=中各項信息如表1和表2所示。首先Va的離散化:決策屬性D={d1,d2},是否發生以{0,1}區分;條件屬性C={c1,c2,…,c8}以工藝基準(0)為依據,偏離分別記為{-1,1}。

表1 屬性-值域信息Table 1 Attribute-value range information

3.2 不完備信息處理

屬性缺失集、屬性值缺失對象集、不可辨識樣本對象集分別為

A*={c1,c3,c4,c5,c7}

(14)

U*={u1,u2,u3,u5,u8}

(15)

表2 診斷信息表Table 2 Diagnosis information table

ind1=ind2=ind3=ind5=ind8=?

(16)

因此,可知優先補齊對象|indi|=0,需通過擴展相似對象集求解,即

IND′={ind′1,ind′2,ind′3,ind′5,ind′8} ={(u4,u9,u11,u14,u15,u18),(u7,u12,u16), (u6,u10,u13,u17,u19,u20),(u7,u12,u16), (u4,u9,u11,u14,u15,u18)}

(17)

根據max|Simij|和ind″i可得c3(u1)=0,c1(u2)=0,c4(u3)=0,c5(u5)=0,c7(u8)=-1。

3.3 屬性約簡與規則提取

根據擴充辨識矩陣Ψ′=[ψ′C(ui,uj)]n×n的一致性檢測,ψ′C(u8,u17)與ψ′C(u13,u18)為?,即u8與u17、u13與u18分別為矛盾信息項。結合背景知識和原始數據分析,判斷u17與u18為無效信息項,在診斷信息表中予以剔除。因此,基于以上可得|C|=8,|A′|=|{ψ′C[ui,uj]}|=71,經f(R)優化搜索的條件屬性約簡集為C′={c2,c3,c4,c5,c8}。

經廣義化可得如表3所示診斷規則,其中對象u8:(c3,1)∧(c4,1)→d2,u11:(c3,1)→d2,u14:(c3,1)∧(c5,1)→d2,根據廣義化步驟{u8,u11,u14}同時支持(c3,1)→d2。因此,屬性約簡率P=37.5%。

3.4 診斷規則覆蓋度評估

以相同環境下的15個測試樣本對上述結果進行覆蓋度評估,測試樣本信息如表4所示。

根據表5測試結果可知,覆蓋度Cor(ri)=86.7%。

表3 診斷規則Table 3 Diagnosis rules

表4 測試實例信息Table 4 Test instance information

表5 測試結果比較Table 5 Comparison of test results

3.5 結果討論

(1)與其他方法的插補結果比較:如表6所示,K-近鄰算法c4(u3)=1,統計意義上無誤,但結合u3情境信息可知與實踐相悖,無從解釋或修正。Roustida算法的假設前提是缺失數據值的填補盡可能反映問題域的基本特征以及隱含的內在規律,使缺失值對象與其他相似對象的屬性值之間的差異盡可能小,改進后基于工程背景引入擴展相似對象集、次相似對象集及其相似性評估,避免了結果只滿足統計合理性。

表6 插補結果對比Table 6 Comparison of supplement results

(2)數據處理的影響分析:數據離散化本質上是通過某種斷點集合對決策系統的屬性進行劃分。為提高系統的聚類效果,增強對數據噪聲的魯棒性,采用盡可能少的區間劃分。故對源數據在偏差允許范圍內以工藝標準為基準做了{-1,0,1}的簡化劃分處理。診斷決策過程中各項情境信息度量要求較高時,勢必對不可辨識關系和辨識矩陣的精確性形成影響。

(3)測試結果的偏差分析:根據工藝c5與d1是反比關系,樣本u′3的(c5,1)→d1不成立,經校驗d1是由于粗進給形成誤差復映的同時光磨時間不足造成,即(c2,1)∧(c7,-1)→d1;樣本u′14實際校驗為砂輪在運轉一定時間后的平衡與表面鈍化問題導致,結合工藝應歸因于修整間隔不當,即(c1,1)→d2。

4 結論

就如何在屬性冗余、數據值缺失情形下通過問題聚類獲取診斷所需隱含知識的問題,針對信息補齊與屬性約簡策略進行了研究,取得了如下研究結果。

(1)針對Roustida算法在工程實踐中面臨的局限性,結合工程應用提出了相應的改進算法,擴充了不完備信息完整化功能的工程實踐范圍。

(2)針對診斷信息的不一致問題,利用擴充辨識矩陣剔除其中的矛盾信息項,并在此基礎上通過遺傳算法設計和廣義診斷規則推理實現了條件屬性約簡與規則提取。

(3)通過實例的驗證與測試表明該方法在一定程度上可以保障診斷知識覆蓋度;最后針對樣本測試結果,從與統計補齊方法比較、處理過程以及工藝分析等方面進行了補充討論。