沈 斌,趙淑玉

(同濟大學 a.中德學院; b.機械與能源工程學院,上海 201804)

沈 斌(1955—),男,教授,博士.E-mail:bshen@#edu.cn

編輯距離的數(shù)控機床故障診斷案例推理方法

沈 斌a,趙淑玉b

(同濟大學 a.中德學院; b.機械與能源工程學院,上海 201804)

為了解決數(shù)控機床故障診斷案例推理中的屬性不匹配或者信息缺失的問題,從差異性的角度,將案例間的差異分為結(jié)構(gòu)上的差異和內(nèi)容上的差異,提出一種基于編輯距離的整體相似度計算方法.給出了結(jié)構(gòu)相似度和混合屬性相似度的計算公式,并進行了證明.然后進行了實例計算,最后通過對比實驗驗證了該方法的有效性.

數(shù)控機床; 故障診斷; 案例推理; 編輯距離

案例推理(Case-Based Reasoning,CBR)在數(shù)控機床故障診斷系統(tǒng)研究中一直是重要的方法.案例推理是人工智能學科的一個重要分支,起源于人類認知科學的研究,其核心思想是利用從前解決相同或者類似問題的經(jīng)驗知識,通過匹配推理求解新的問題.利用案例推理技術來解決故障診斷問題,是當今人工智能故障診斷領域的重要研究內(nèi)容[1].

1 案例推理的屬性不匹配問題

在案例推理過程中,相似度的計算是關鍵技術,通常采用局部-整體原則(Local-Global Principle),即先計算屬性間的局部相似度,然后在局部相似度的基礎上,通過加權(quán)計算得到案例的整體相似度.基于上述原則,局部相似度的計算需要案例之間具備一致對應的屬性.

然而在實際的數(shù)控機床的故障診斷過程中,可能由于人為的原因?qū)χ匾墓收闲畔]有重視,也可能由于缺乏某些檢測儀器,某些數(shù)據(jù)無法采集,或者其他原因(如網(wǎng)絡故障)造成了數(shù)據(jù)的丟失,就出現(xiàn)了屬性不配對的情況.對此,研究人員在一些研究文獻中提出了各自的解決方法.比如,Agre[2]通過屬性所有的可能值的數(shù)量來計算不同案例之間對應屬性的相似度,因為該研究僅限于字符型的屬性,并且每個屬性所可能的取值是有限的,該方法將屬性a1和a2的差異度設定為Diff(a1,a2)=1/Si(1-1/Si),其中Si為第i個屬性所有可能值的數(shù)量.Gu等[3]計算案例中缺失的屬性的方法為:如果屬性a1或者a2缺失,則它們的相似度Sim(a1,a2)=0.Ricci[4]的研究中,針對不匹配的屬性,在屬性a1或者a2缺失的情況下,將其相似度設為0.5.王鳳梅等[5]通過近鄰規(guī)則對數(shù)據(jù)進行補充.Shen等[6]在傳統(tǒng)相似度基礎上,提出了“缺失因子”來計算不匹配的屬性的相似度.

總結(jié)這些研究可以發(fā)現(xiàn),多數(shù)將缺失的屬性用一個固定值或者近似值來代替.在不同的研究中,缺失的屬性之間的相似度可以是0,0.5或者其他值,雖然這些處理過程都解決了各自的問題,但沒有形成統(tǒng)一的方法.并且這些研究方法通常將各項屬性及對應取值完全一致的案例作為完全相似案例,采用的方法無法反映由于權(quán)重的不同而造成案例之間的差異.

因此,本文從差異性的角度,將案例間的差異分為結(jié)構(gòu)上的差異和內(nèi)容上的差異,提出一種基于編輯距離(Edit Distance,ED)的整體相似度計算公式,用于解決案例相似度計算中的屬性不匹配或者信息缺失的問題.

2 基于ED的案例相似度計算

2.1案例結(jié)構(gòu)的ED計算方法

2.1.1ED方法

作為一種衡量不同對象間距離的計算方法,Levenshtein在1965年提出了編輯距離的理論.兩序列之間的編輯距離是指只用插入(Insert)、刪除(Delete)和替換(Substitute)3種基本操作,把某個字符串變換為不同字符串而必須的最少的編輯方法.

假設字符串X={x1,x2,…,xm}是一個長度為m的字符串,Y={y1,y2,…,yn}是長度為n的字符串,則字符串X和Y之間的ED表示為

(1)

式中:L=L1+L2+L3;E為編輯操作距離;Ei為插入操作距離;Ed為刪除操作距離;Es為替換操作距離.ED的大小與發(fā)生編輯的字符在字符串的位置不同沒有依賴關系.

2.1.2案例結(jié)構(gòu)的編輯距離公式

ED的計算結(jié)果能夠反映兩個對象間差異的大小,所以ED可以用于案例間的相似度的計算.由于傳統(tǒng)的ED方法能夠處理的問題較為簡單,不能滿足案例相似度的要求,因此對其進行兩方面的改進,分別為不匹配屬性的結(jié)構(gòu)編輯距離(Structure Edit Distance,SED)和可匹配屬性的SED.

由于案例間屬性重要程度存在差異,故對不同的屬性進行相同的編輯操作會產(chǎn)生不同的ED.而在傳統(tǒng)的ED的計算過程中,“刪除”“添加”和“替換”的操作成本通常設定為某一固定值,這不符合案例中不同屬性存在重要度差異的要求.

因此在考慮屬性權(quán)重的基礎上對原有的ED進行改進,得到案例間不匹配屬性的SED為

ED(C1,C2)=min∑Ef(w)

(2)

本文認為可匹配屬性的權(quán)重的不同也將導致案例的差異,因此考量可匹配屬性的權(quán)重,給出可匹配屬性的SED為

ED(ω)=∑g(w)

(3)

綜上所述,本文認為案例間結(jié)構(gòu)上的相似度包括2個方面:① 案例中不匹配屬性的ED(C1,C2);② 案例中可匹配屬性的ED(ω).因此,案例的SED為

(4)

式中:SED(C1,C2)為案例結(jié)構(gòu)的ED;f(w)為權(quán)重函數(shù);f(wn1)為被插入屬性的權(quán)重函數(shù);f(wn2)為被刪除屬性的權(quán)重函數(shù);f(wn3)為被替換屬性的權(quán)重函數(shù);g(wn4)為權(quán)重的ED.上述公式應當滿足如下條件:

當編輯操作為插入或者刪除時,f(w)=w;當編輯操作為替換時,f(w)=(w1+w2)/2;當計算權(quán)重的ED時,g(w)=w1-w2,w1和w2分別為對應屬性的權(quán)重.

2.1.3案例結(jié)構(gòu)編輯距離公式的性質(zhì)

案例的EDXSED(C1,C2)反映了案例之間的結(jié)構(gòu)上的距離,SEC(C1,C2)越大,距離越大,相似度越小.SEC(C1,C2)應當滿足距離的性質(zhì):非負性、對稱性,傳遞性.

要滿足上述條件,需要作出以下規(guī)定:① ED均為正數(shù),即Ei≥0,Ed≥0和Es≥0;② 插入編輯距離和刪除編輯距離相同,即Ei=Ed;③ 替換距離不小于插入距離和刪除距離之和,即Es≤Ei+Ed.

在上述規(guī)定的基礎上,給出相應的證明.

(1) 非負性

(2) 對稱性

對稱性即滿足交換律,證明如下:

② 根據(jù)證明中的①部分,當刪除屬性時,假設C2→C1的編輯操作為刪除屬性,滿足對稱性.

(3) 傳遞性

傳遞性即滿足三角不等式,SED(C1,C2)≤SED(C1,C3)+SED(C3,C2),證明如下:

由于Ei=Ed,Es≤Ei+Ed=2Ei,計算可得

即

SED(C1,C2)≤SED(C1,C3)+SED(C3,C2)

同上,由于ED是不同操作的線性組合,SED(X,Y)也滿足三角不等式.

2.2屬性間的編輯距離計算方法

案例結(jié)構(gòu)的ED只考慮了案例結(jié)構(gòu)上的相似度,還應包含屬性間的相似度,即局部相似度.局部相似度可以通過計算屬性的距離得來,常見距離標準有歐氏距離、海明距離、明考斯基距離、方差加權(quán)距離和馬氏距離等[7].

很多學者都對多類型的局部相似度進行了研究,比如Zhao等[8]對包含字符型、語言型、區(qū)間型屬性的案例的混合相似性計算進行了研究.這些研究對案例的局部相似度的研究較為成熟,這里不再贅述.

2.3案例整體相似度計算方法

前面分別通過ED公式衡量了案例結(jié)構(gòu)上的差異性和案例內(nèi)容上的差異性.本文認為案例間的差異包含上述兩個方面,并將屬性間的差異度作為屬性間的ED,從而建立案例的整體編輯距離(Global Edit Distance,GED)計算公式:

GED(C1,C2)=min[∑Ef(w)]+∑g(w)+

(5)

式中:GED(C1,C2)為案例的整體編輯距離;diff(c1,c2)為屬性取值的差異度.

那么案例的整體相似度SIM(C1,C2)為

SIM(C1,C2)=exp[-GEC(C1,C2)]

(6)

3 實例計算和對比實驗

3.1實例計算

本實例的數(shù)據(jù)如圖1所示,圖中包含兩個案例C1及案例C2,其中C1含有4項屬性,分別為報警號碼“700056” “風扇F-11轉(zhuǎn)速” “電柜G-02溫度” “電機M-05溫度”;案例C2含有5項屬性,分別為報警號碼“700056” “風扇F-11轉(zhuǎn)速” “電柜G-02溫度” “電機M-07溫度”及警號碼“216016”,其中風扇F-11轉(zhuǎn)速范圍為[0,2 000].

圖1 案例相似度計算實例Fig.1 Example of case similarity calculation

案例C1,C2結(jié)構(gòu)編輯距離WEC(C1,C2)為

WEC(C1,C2)=min[∑Ef(w)]+∑g(w)=

案例C1,C2混合屬性的ED為

(7)

式中:

案例C1,C2的整體相似度SIM(C1,C2)為

SIM(C1,C2)=

代入上述符號取值,得到案例C1,C2的整體相似度:

SIM(C1,C2)=exp(-1.688)=0.18

3.2對比實驗

3.2.1評價方法

下面通過實驗計算進行對比和驗證本文的方法.按照k近鄰算法,實際的案例推理目標可以是最近鄰案例,即k=1,也可以是多近鄰案例,即k>1.在案例推理性能的研究中,通常是按照最近鄰結(jié)果進行評價,而Xie等[9]從案例的多項匹配(k=5)研究了案例推理的性能比較方法,取得了良好的效果.這里對此進一步細分,以匹配案例目標數(shù)分別為k=1,k=3,k=5對本文所提出的案例相似度計算方法的性能進行評價.

本實驗中將選取案例庫中的200個案例構(gòu)建子案例庫,即Nall=200,并保證該子案例中的所有案例的屬性數(shù)量在5～20之間.將其中每一條案例進行單獨編號No1～No200,并基于該子案例庫進行案例匹配計算,并規(guī)定以下評價方法和評價指標.

當k=1時,如果某一案例能夠匹配到子案例庫中的自身,這里將其視作案例匹配成功,依此評判該方法的正確性,并基于該子案例庫中所有的案例匹配情況計算其正確率R,即

(8)

式中:N為能夠匹配到自身的案例的數(shù)量.

當k=3時,如果所匹配到的3個案例中出現(xiàn)案例自身,本文將其視作案例匹配成功,依此評判該方法的正確性,并基于該子案例庫中所有的案例匹配情況計算其正確率R.

當k=5時,以所匹配到的5個案例中出現(xiàn)案例自身作為案例匹配成功.

為了更加全面地進行評估,將本實驗分為3類:① 無缺失項;② 缺失項較少,即1～2項;③ 缺失項較多,即2～3項.具體規(guī)則如表1所示.

表1 缺失項數(shù)量的規(guī)則Tab.1 Rule of missing item number

3.2.2評價結(jié)果

在通過基于編輯成本的案例相似度計算方法進行案例匹配的同時,也按照其他方法進行計算,從而將計算結(jié)果進行對比,實驗結(jié)果如下:

(1) 無缺失項

以案例No1的計算為例,如表2所示,在k=1,3,5的3種情況下,所有方法得到的結(jié)果都包含自身.

在正確率方面,4種方法都能匹配到子案例庫中的自身案例,即具有100%的正確率,分別如表3、表4和表5所示.

(2) 較少缺失項

在缺失項較少的情況下,當k=1時,案例No1通過本文方法可以匹配到案例自身,其他方法中僅1種匹配到案例自身,另外2種都匹配到了其他案例;當k=3和k=5時,4種方法的案例No1的匹配結(jié)果都正確,如表2所示.

表2 案例No1的計算結(jié)果對比Tab.2 Calculation results comparison of Case No1

在正確率方面,當k=1,k=3和k=5時,本文方法的正確率為分別為65%,82%和93%,高于其他3種方法,分別如表3、表4和表5所示.

表3 k=1時正確率的對比 Tab.3 Comparison of accuracy rate when k=1 %

表4 k=3時正確率的對比 Tab.4 Comparison of accuracy rate when k=3 %

表5 k=5時正確率的對比 Tab.5 Comparison of accuracy rate when k=5 %

(3) 較多缺失項

在缺失項較少的情況下,當k=1時,案例No1通過本文方法可以匹配到案例自身,其他方法都只匹配到了其他案例;當k=3時,本文的方法匹配正確,而其他方法都只匹配到了其他案例;當k=5時,本文的方法匹配正確,而其他方法中只有1種方法的匹配結(jié)果正確,如表2所示.

在正確率方面,當k=1,k=3和k=5時,分別如表3、表4和表5所示,本文方法的正確率為分別為21%,61%和85%,高于其他3種方法.其中當k=1時,4種方法的正確率都出現(xiàn)了明顯的下降,但本文所提出的方法的正確率為21%，還是要明顯高于其他方法.

從上述計算結(jié)果可以看出,在沒有缺失項和缺失項較少的情況下,本文所提出的基于編輯成本的案例相似度計算方法具有較高的正確率.雖然在缺失項較多的情況下,正確率并不很高,但對比于其他3種方法,本文的方法在案例推理過程中的正確率有了明顯的提升,表現(xiàn)出了更好的性能.

4 結(jié)語

為了解決案例相似度計算中的屬性不匹配問題,本文從差異性的角度進行研究,從結(jié)構(gòu)上的差異度和內(nèi)容上的差異度兩個方面建立了相應的編輯成本計算方法,對差異性的性質(zhì)進行了證明,并提出了基于ED的案例整體相似度的計算方法.最后結(jié)合實例闡述了其計算步驟,并通過對比計算驗證了該算法的有效性.

[1] 宋志雄,朱紅崗,李星星.基于案例推理的大型養(yǎng)路機械故障診斷系統(tǒng)[J].中國安全科學學報,2012,22(12):41.

SONG Z X,ZHU H G,LI X X.Fault diagnosis and retrieval system of railway maintenance machinery based on case-based reasoning[J].China Safety Science Journal,2012,22(12):41.

[2] AGRE G.KBS maintenance as learning two-tiered domain representation[J].Lecture Notes in Artificial Intelligence,1997,1010:109-120.

[3] GU M,TONG X,AMODT A.Comparing similarity calculation methods in conversational CBR[C]// IEEE International Conference on Information Reuse & Integration Conf.2005:427-432.

[4] RICCI F,AVESANI P.Learning a local similarity metric for case-based reasoning[C]// Case-Based Reasoning Research and Development.Berlin Heidelberg:Springer,1995:301-312.

[5] 王鳳梅,胡麗霞.一種基于近鄰規(guī)則的缺失數(shù)據(jù)填補方法[J].計算機工程,2012,38(21):53-55.

WANG F M,HU L X.A missing data imputation method based on neighbor rules[J].Computer Engineering,2012,38(21):53-55.

[6] SHEN B,ZHAO S Y,WANG J H,et al.An improved case-based reasoning for fault diagnosis of CNC machine tool[J].Journal of Information & Computational Science,2015,12:2939-2949.

[7] 張騏,向陽,羅成,等.基于本體的中文案例相似度計算方法[J].情報科學,2014(11):77-81.

ZHANG Q,XIANG Y,LUO C,et al.Research on case similarity computing method based on ontology[J].Information Science,2014(11):77-81.

[8] ZHAO J S,LIN C,ZHAO L H,et al.Learning HAZOP expert system by case-based reasoning and ontology[J].Computers & Chemical Engineering,2009,33(1):371-378.

[9] GUO Y,HU J,PENG Y H.A CBR system for injection mould design based on ontology:a case study[J].Computer-Aided Design,2012,44(6):496-508.

Acase-basedreasoningmethodforfaultdiagnosisofCNCmachinetoolsbasedoneditdistance

SHENBina,ZHAOShuyub

(a.CDHK; b.College of Mechanical and Energy Engineering,Tongji University,Shanghai 201804, China)

In order to solve the attribute mismatch and information missing problem in the case similarity calculation of CNC machine tool fault diagnosis,the difference between cases is divided into structure difference and content difference.A case similarity calculation method is proposed based on edit distance,and the calculation formulas of structural similarity and mixed attribute similarity are given and proved.Then an example is calculated and finally the effectiveness of the method is verified by calculation experiments.

CNC machine tool; fault diagnosis; case-based reasoning; edit distance

TP 182

A

1672-5581(2017)04-0359-06