编辑距离的数控机床故障诊断案例推理方法

沈 斌,赵淑玉

(同济大学 a.中德学院; b.机械与能源工程学院,上海 201804)

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

编辑距离的数控机床故障诊断案例推理方法

沈 斌a,赵淑玉b

(同济大学 a.中德学院; b.机械与能源工程学院,上海 201804)

为了解决数控机床故障诊断案例推理中的属性不匹配或者信息缺失的问题,从差异性的角度,将案例间的差异分为结构上的差异和内容上的差异,提出一种基于编辑距离的整体相似度计算方法.给出了结构相似度和混合属性相似度的计算公式,并进行了证明.然后进行了实例计算,最后通过对比实验验证了该方法的有效性.

数控机床; 故障诊断; 案例推理; 编辑距离

案例推理(Case-Based Reasoning,CBR)在数控机床故障诊断系统研究中一直是重要的方法.案例推理是人工智能学科的一个重要分支,起源于人类认知科学的研究,其核心思想是利用从前解决相同或者类似问题的经验知识,通过匹配推理求解新的问题.利用案例推理技术来解决故障诊断问题,是当今人工智能故障诊断领域的重要研究内容[1].

1 案例推理的属性不匹配问题

在案例推理过程中,相似度的计算是关键技术,通常采用局部-整体原则(Local-Global Principle),即先计算属性间的局部相似度,然后在局部相似度的基础上,通过加权计算得到案例的整体相似度.基于上述原则,局部相似度的计算需要案例之间具备一致对应的属性.

然而在实际的数控机床的故障诊断过程中,可能由于人为的原因对重要的故障信息没有重视,也可能由于缺乏某些检测仪器,某些数据无法采集,或者其他原因(如网络故障)造成了数据的丢失,就出现了属性不配对的情况.对此,研究人员在一些研究文献中提出了各自的解决方法.比如,Agre[2]通过属性所有的可能值的数量来计算不同案例之间对应属性的相似度,因为该研究仅限于字符型的属性,并且每个属性所可能的取值是有限的,该方法将属性a1和a2的差异度设定为Diff(a1,a2)=1/Si(1-1/Si),其中Si为第i个属性所有可能值的数量.Gu等[3]计算案例中缺失的属性的方法为:如果属性a1或者a2缺失,则它们的相似度Sim(a1,a2)=0.Ricci[4]的研究中,针对不匹配的属性,在属性a1或者a2缺失的情况下,将其相似度设为0.5.王凤梅等[5]通过近邻规则对数据进行补充.Shen等[6]在传统相似度基础上,提出了“缺失因子”来计算不匹配的属性的相似度.

总结这些研究可以发现,多数将缺失的属性用一个固定值或者近似值来代替.在不同的研究中,缺失的属性之间的相似度可以是0,0.5或者其他值,虽然这些处理过程都解决了各自的问题,但没有形成统一的方法.并且这些研究方法通常将各项属性及对应取值完全一致的案例作为完全相似案例,采用的方法无法反映由于权重的不同而造成案例之间的差异.

因此,本文从差异性的角度,将案例间的差异分为结构上的差异和内容上的差异,提出一种基于编辑距离(Edit Distance,ED)的整体相似度计算公式,用于解决案例相似度计算中的属性不匹配或者信息缺失的问题.

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

2.1案例结构的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的大小与发生编辑的字符在字符串的位置不同没有依赖关系.

2.1.2案例结构的编辑距离公式

ED的计算结果能够反映两个对象间差异的大小,所以ED可以用于案例间的相似度的计算.由于传统的ED方法能够处理的问题较为简单,不能满足案例相似度的要求,因此对其进行两方面的改进,分别为不匹配属性的结构编辑距离(Structure Edit Distance,SED)和可匹配属性的SED.

由于案例间属性重要程度存在差异,故对不同的属性进行相同的编辑操作会产生不同的ED.而在传统的ED的计算过程中,“删除”“添加”和“替换”的操作成本通常设定为某一固定值,这不符合案例中不同属性存在重要度差异的要求.

因此在考虑属性权重的基础上对原有的ED进行改进,得到案例间不匹配属性的SED为

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

(2)

本文认为可匹配属性的权重的不同也将导致案例的差异,因此考量可匹配属性的权重,给出可匹配属性的SED为

ED(ω)=∑g(w)

(3)

综上所述,本文认为案例间结构上的相似度包括2个方面:① 案例中不匹配属性的ED(C1,C2);② 案例中可匹配属性的ED(ω).因此,案例的SED为

(4)

式中:SED(C1,C2)为案例结构的ED;f(w)为权重函数;f(wn1)为被插入属性的权重函数;f(wn2)为被删除属性的权重函数;f(wn3)为被替换属性的权重函数;g(wn4)为权重的ED.上述公式应当满足如下条件:

当编辑操作为插入或者删除时,f(w)=w;当编辑操作为替换时,f(w)=(w1+w2)/2;当计算权重的ED时,g(w)=w1-w2,w1和w2分别为对应属性的权重.

2.1.3案例结构编辑距离公式的性质

案例的EDXSED(C1,C2)反映了案例之间的结构上的距离,SEC(C1,C2)越大,距离越大,相似度越小.SEC(C1,C2)应当满足距离的性质:非负性、对称性,传递性.

要满足上述条件,需要作出以下规定:① ED均为正数,即Ei≥0,Ed≥0和Es≥0;② 插入编辑距离和删除编辑距离相同,即Ei=Ed;③ 替换距离不小于插入距离和删除距离之和,即Es≤Ei+Ed.

在上述规定的基础上,给出相应的证明.

(1) 非负性

(2) 对称性

对称性即满足交换律,证明如下:

② 根据证明中的①部分,当删除属性时,假设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属性间的编辑距离计算方法

案例结构的ED只考虑了案例结构上的相似度,还应包含属性间的相似度,即局部相似度.局部相似度可以通过计算属性的距离得来,常见距离标准有欧氏距离、海明距离、明考斯基距离、方差加权距离和马氏距离等[7].

很多学者都对多类型的局部相似度进行了研究,比如Zhao等[8]对包含字符型、语言型、区间型属性的案例的混合相似性计算进行了研究.这些研究对案例的局部相似度的研究较为成熟,这里不再赘述.

2.3案例整体相似度计算方法

前面分别通过ED公式衡量了案例结构上的差异性和案例内容上的差异性.本文认为案例间的差异包含上述两个方面,并将属性间的差异度作为属性间的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实例计算

本实例的数据如图1所示,图中包含两个案例C1及案例C2,其中C1含有4项属性,分别为报警号码“700056” “风扇F-11转速” “电柜G-02温度” “电机M-05温度”;案例C2含有5项属性,分别为报警号码“700056” “风扇F-11转速” “电柜G-02温度” “电机M-07温度”及警号码“216016”,其中风扇F-11转速范围为[0,2 000].

图1 案例相似度计算实例Fig.1 Example of case similarity calculation

案例C1,C2结构编辑距离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.在案例推理性能的研究中,通常是按照最近邻结果进行评价,而Xie等[9]从案例的多项匹配(k=5)研究了案例推理的性能比较方法,取得了良好的效果.这里对此进一步细分,以匹配案例目标数分别为k=1,k=3,k=5对本文所提出的案例相似度计算方法的性能进行评价.

本实验中将选取案例库中的200个案例构建子案例库,即Nall=200,并保证该子案例中的所有案例的属性数量在5～20之间.将其中每一条案例进行单独编号No1～No200,并基于该子案例库进行案例匹配计算,并规定以下评价方法和评价指标.

当k=1时,如果某一案例能够匹配到子案例库中的自身,这里将其视作案例匹配成功,依此评判该方法的正确性,并基于该子案例库中所有的案例匹配情况计算其正确率R,即

(8)

式中:N为能够匹配到自身的案例的数量.

当k=3时,如果所匹配到的3个案例中出现案例自身,本文将其视作案例匹配成功,依此评判该方法的正确性,并基于该子案例库中所有的案例匹配情况计算其正确率R.

当k=5时,以所匹配到的5个案例中出现案例自身作为案例匹配成功.

为了更加全面地进行评估,将本实验分为3类:① 无缺失项;② 缺失项较少,即1～2项;③ 缺失项较多,即2～3项.具体规则如表1所示.

表1 缺失项数量的规则Tab.1 Rule of missing item number

3.2.2评价结果

在通过基于编辑成本的案例相似度计算方法进行案例匹配的同时,也按照其他方法进行计算,从而将计算结果进行对比,实验结果如下:

(1) 无缺失项

以案例No1的计算为例,如表2所示,在k=1,3,5的3种情况下,所有方法得到的结果都包含自身.

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

(2) 较少缺失项

在缺失项较少的情况下,当k=1时,案例No1通过本文方法可以匹配到案例自身,其他方法中仅1种匹配到案例自身,另外2种都匹配到了其他案例;当k=3和k=5时,4种方法的案例No1的匹配结果都正确,如表2所示.

表2 案例No1的计算结果对比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种方法的匹配结果正确,如表2所示.

在正确率方面,当k=1,k=3和k=5时,分别如表3、表4和表5所示,本文方法的正确率为分别为21%,61%和85%,高于其他3种方法.其中当k=1时,4种方法的正确率都出现了明显的下降,但本文所提出的方法的正确率为21%，还是要明显高于其他方法.

从上述计算结果可以看出,在没有缺失项和缺失项较少的情况下,本文所提出的基于编辑成本的案例相似度计算方法具有较高的正确率.虽然在缺失项较多的情况下,正确率并不很高,但对比于其他3种方法,本文的方法在案例推理过程中的正确率有了明显的提升,表现出了更好的性能.

4 结语

为了解决案例相似度计算中的属性不匹配问题,本文从差异性的角度进行研究,从结构上的差异度和内容上的差异度两个方面建立了相应的编辑成本计算方法,对差异性的性质进行了证明,并提出了基于ED的案例整体相似度的计算方法.最后结合实例阐述了其计算步骤,并通过对比计算验证了该算法的有效性.

[1] 宋志雄,朱红岗,李星星.基于案例推理的大型养路机械故障诊断系统[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] 王凤梅,胡丽霞.一种基于近邻规则的缺失数据填补方法[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