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

沈 斌,趙淑玉

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

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

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

沈 斌a,趙淑玉b

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

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

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

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

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

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

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

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

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

2 基于ED的案例相似度計(jì)算

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

2.1.1ED方法

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

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

(1)

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

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

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

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

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

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

(2)

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

ED(ω)=∑g(w)

(3)

綜上所述,本文認(rèn)為案例間結(jié)構(gòu)上的相似度包括2個(gè)方面:① 案例中不匹配屬性的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.上述公式應(yīng)當(dāng)滿足如下條件:

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

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

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

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

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

(1) 非負(fù)性

(2) 對稱性

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

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

(3) 傳遞性

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

由于Ei=Ed,Es≤Ei+Ed=2Ei,計(jì)算可得

即

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

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

2.2屬性間的編輯距離計(jì)算方法

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

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

2.3案例整體相似度計(jì)算方法

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

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 實(shí)例計(jì)算和對比實(shí)驗(yàn)

3.1實(shí)例計(jì)算

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

圖1 案例相似度計(jì)算實(shí)例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)=

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

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

3.2對比實(shí)驗(yàn)

3.2.1評價(jià)方法

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

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

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

(8)

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

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

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

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

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

3.2.2評價(jià)結(jié)果

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

(1) 無缺失項(xiàng)

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

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

(2) 較少缺失項(xiàng)

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

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

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

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

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

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

(3) 較多缺失項(xiàng)

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

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

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

4 結(jié)語

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

[1] 宋志雄,朱紅崗,李星星.基于案例推理的大型養(yǎng)路機(jī)械故障診斷系統(tǒng)[J].中國安全科學(xué)學(xué)報(bào),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ù)填補(bǔ)方法[J].計(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ì)算方法[J].情報(bào)科學(xué),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