（计算机应用技术专业论文）基于粗集神经网络的故障诊断专家系统研究.pdf

基于粗集神经网络的故障诊断专家系统研究 朱万富( 计算机应用技术) 指导教师：赵仕俊副研究员 摘要 由于故障信号存在数量冗余、不准确、不完整等现象，导致了基于神经网络的故障 诊断专家系统的网络结构输入维数大，结构复杂，冗余部分多，因此网络训练速度慢， 不易收敛，推广能力差，限制了这种专家系统在各个场合的广泛应用。因此本文用粗集 来消除网络输入( 故障信号) 和网络结构中的冗余，提高专家系统的应用能力。 文章首先讨论了决策表中冗余对象对粗集约简的影响，然后提出了求最简决策表的 算法，算法利用对象频度的概念，删除决策表中的冗余对象，组建最简决策表，把求最 简决策表的算法与基于区分对象对集的约简算法结合起来，形成了一种能l 司时适用于一 致表与不一致表的粗集约简算法s d t r a 算法。 然后研究b p 网络的结构优化理论，分析了权衰减法、灵敏度法及相关性法等剪枝 法的优缺点，根据b p 网络学习与权值调整的特点，结合粗集能够优化约简冗余信息的 长处，提出了在网络的训练过程中构建决策表进行约简，最后根据约简的结果删除冗余 的连接和节点，得到一个求最优神经网络结构设计的新方法一粗集法。 最后在粗集约简理论与粗集优化神经网络理论的基础上，提出了- - * 十n 集集成神经 网络的故障诊断专家系统模型，模型先用粗集理论对诊断输入数掘进行约简，然后用它 来对神经网络进行剪枝优化。文章最后设计了一个基于粗集神经网络的柴油机气阀开度 故障诊断专家系统，实验表明该系统诊断时不仅速度快，而且证确率高，明显优于其它 系统，因此具有较好的工程应用价值。 关键词：粗集，最简决策表，神经网络，故障诊断，专家系统 r e s e a r c ho nr o u g hs e t sa n dn e u r a ln e t w o r ki nf a u l t d i a g n o s i se x p e r ts y s t e m z h uw a n f u ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db y a s s o c i a t ep r o f e s s o rz h a os h i - j u n a b s t r a c t f a u l td i a g n o s i sd a t a ，i no t h e rw o r d s ，t h ei n p u td a t ao fn e u r a ln e t w o r kh a v es o m e d i s a d v a n t a g e ， f o re x a m p l e ，d a t ai sw i d e l yr e d u n d a n c y 、i n c o m p a t i b i l i t y ，w h i c hc a u s e n e u r a ln e t w o r kt r a i n i n gs l o w l ya n dc o n v e r g e n c ed i f f c u l t 。a n di ta f f e c tn e u r a ln e t w o r k s f u r t h e ra p p l i c a t i o ni ne x p e r ts y s t e m i nt h i sp a p e rr o u g hs e t si su s e dt oe l i m i n a t er e d u n d a n c y o fn e t w o r ki n p u t ( f a u l td i a g n o s i sd a t a ) a n dn e t w o r ks t r u c t u r e ，i m p r o v et h ea p p l i c a t i o n e a p b i l i t yo fe x p e r ts y s t e m f i r s t l y ，i ti sd i s c u s s e dt h a tr e d u n d a n c yo b j e c t sa f f e c tr o u g hs e ta t t r i b u t i o ni nd e c i s i o nt a b l e o nt h i sc o n d i t i o n aa l g o r i t h mo fc o m p u t i n gt h es i m p l e s td e c i s i o nt a b l ei sp u tf o r w a r d w i t h t h ec o n c e p to fo b j e c tf r e q u e n c y , a l g o r i t h md e l e t e st h eo b j e c tw h i c hi ss a m eo ri n c o n s i s t e n t a n dl o wf r e q u e n c y , c o n s t r u c tt h es i m p l e s td e c i s i o nt a b l e t h i sa l g o r i t h mi si n t e g r a t e dw i t l l d i s t i n g u i s ho b j e c tg r o u pa l g o r i t h m i ti sn a m e ds d t r aa l g o r i t h m ，i tc o u l db ea p p l i e dn o to n l y c o n s i s t e n td e c i s i o nt a b l e b u ta l s oi n c o n s i s t e n td e c i s i o nt a b l e s e c o n d l y ，o p t i m i z a lt h e o r yo fb pn e t w o r ks t r u c t u r ei st h o r o u g h l yl u c u b r a t e d ，t h e a d v a n t a g ea n dd i s a d v a n t a g eo fw e i g h te l i m i n a t i o n ，s e n s i t i v i t yp r u n i n ga l g o r i t h ma n d c o r r e l a t i o np r u n i n ga l g o r i t h mi s a n a l y z e d f o rt h ec h a r a c t e ro fb pl e a r na n dw e i g h t a d j u s t m e n ta n dt h ee x c e l l e n c eo fr e d u n d a n c yi n f o r m a t i o nc a nb er e d u c e db yr o u g hs e t s ，i ti s s u p p o s e dt h a td e c i s i o n - m a k i n gt a b l ew o u l db ee s t a b l i s h e dw h e nt h en e t w o r ki st r a i n n i n g ， a f t e rt h et a b l ew o u l db er e d u c e d ，r e d u n d a n c yw e i g h ta n dn o d ec a nb ed e l e t e d ，a tl a s tab e s t o p t i m i z a ln e t w o r kw o u l db ea c q u i r e d i ti san e wm e t h o do fd e s i g n i n gn e u r a ln e t w o r k r o u g h s e t sm e t h o d f i n a l l y ， an e wm o d e lf o rf a u l td i a g n o s i se x p e r ts y s t e mb a s e do nr o u g hs e t si sp u t f o r w a r d ，w h i c hi sb a s e do nr e d u c t i o na l g o r i t h mo fr o u g hs e t sa n ds t r u c t u r ed e s i g nm e t h o do f n e u r a ln e t w o r k i ti sc o m b i n e dt i g h t l yb e t w e e nr o u g hs e t sa n dn e u r a ln e t w o r k ， r o u g hs e t si s u s e dt on o to n l yr e d u c t i n ga n do p t i m i z i n gt h ef a u l td i a g n o s i sd a t a ，b u ta l s op r u n i n ga n d o p t i m i z i n gt h es t r u c t u r eo fn e u r a ln e t w o r k 0 nt h i sc o n d i t i o n ， av a l v ec l e a r a n c ed i a g n o s i s e x p e r ts y s t e mo fd i e s e le n g i n ei si m p l e m e n t e d t h er e s u l t ss h o wt h a tt h ee x p e r ts y s t e mh a s b e t t e re f f i c i e n c ya n dd i a g n o s i sa c c u r a c yt h a nt h eo t h e rs y s t e m 。s oi ti se s t i m a t e dt h a tt h e e x p e r ts y s t e mw o u l db ea p p l i e di nf a u l td i a g n o s i s k e y w o r d s ：r o u g hs e t ，s i m p l e s td e c i s i o nt a b l e ，n e u r a ln e t w o r k ，f a u l td i a g n o s i s ，e x p e r t s y s t e m 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均己在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名去垄鲨帆m 7 年伽形日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数掘库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：盘垄叟 指导教师签名：1 至曼兰雏 f 1 期：瑚7 年，z 月，r 同期：呻年，1 月，6r 中国山油大学坝i 学位论义 第1 章绪论 1 1 课题的研究意义 基于传统的故障诊断专家系统已经在航空、航天、船舶、电力、机械、化工等许多 领域得到广泛应用，它具有不需要专家在现场进行诊断，诊断结果准确且速度快等优点。 但是，它的缺点也非常明显，如不具备联想及自学习能力，知识的更新、修改都非常麻 烦，即知识获取的“瓶颈”问题，当知识库非常庞大时，还容易产生搜索速度下降，规则 相互抵触，知识组合爆炸等问题。另一方面，神经网络技术具有自学习与联想能力、 知识更新修改很容易、搜索速度快、并行推理能力等特点，刚好可以与传统专家系统相 互补充，因此我们考虑将神经网络和专家系统两者结合起来，构成基于神经网络的故障 诊断专家系统。 由于故障诊断信号存在数量冗余、不准确、不完整等现象，如按一般的神经网络专 家系统的方法，将此故障信号输入神经网络进行训练，得到的神经网络结构输入维数大， 结构复杂，冗余部分多【2 】；另外，设计一个与实际应用相符的结构无冗余的神经网络， 一直是神经网络理论的难点，最早仅依靠经验或试探，效率很低，后来出现的各种设计 方法也各有不足，实用性较差。因此，网络输入冗余和网络结构冗余是当前基于神经网 络的专家系统两个很明显的缺点，它们限制了这种专家系统在各个场合的广泛应用【3 l o 粗集理论不需要先验知识，即能确定哪些知识是冗余的，消除信息中的噪声和冗余 对象，进行知识表达空问简化。利用半日集理论来约简神经网络的输入( 故障诊断数据) ， 不仅可以通过消除冗余的诊断数据，减小网络规模，减少网络的训练和学习负担，而且 还可以通过消除噪声提高神经网络诊断的准确性的目的。另外，神经网络结构设计其实 就是消除结构中的冗余部分，而这正是粗集的长处，因此可以用粗集来消除神经网络结 构中的冗余，进行剪枝，得到精简的网络结构，提高网络的收敛速度与泛化能力。 本课题首先研究粗集约简理论和神经网络结构优化设计理论，提出了一种高效的同 时适用于一致表和不一致表的粗集约简算法，然后用此算法来约简优化网络结构，最 后在此基础上将粗集与神经网络的集成起来，提出了一种新的基于粗集神经网络的故 障诊断专家系统模型，设计出了一个基于粗集神经网络的柴油机气阀丌度故障诊断专 家系统，因此本课题不仅在数据挖掘、神经网络与专家系统方面具有一定的理论价值， 还在工程应用方面具有较高的使用价值和经济价值。 1 2 国内外研究现状 1 粗集约简研究现状 第一章绪论 粗集约简是粗集理论中的核心内容，也是粗集理论中被研究较多的分支，人们总是 希望找出信息系统或决策表的最小的约简，然而早在1 9 8 5 年w o n gs k 和z i a r k o 就已经证 明了求最小约简是一个n p h a r d 问题【4 1 。 随着对粗集理论研究的不断深入，国内外许多学者提出了众多的属性约简的算法。 最早的属性约简的算法为粗集创始人z p a w l a k 提出的简单数据分析法| 5 】，利用数据人 工进行分析信息系统的决策表，依次对属性和属性值进行约简，它是一个典型的非形式 化的算法，不容易机械化，在实际应用中很难实现。波兰华沙大学著名的数学家s k o w r o n 提出了基于差别矩阵的算法1 6 】，该算法通过引入代数知识，把对信息系统或决策表的知 识约简问题转化为对差别矩阵的化简问题。同时s k o w r o n 严格证明，差别矩阵原理与 p a w l a k 的粗集理论等价【”。通过差别矩阵能很方便地求取核属性，以核属性为出发点， 再求取差别函数的最小析取范式，最后得到的每个析取分量对应着一个约简，因此，一 定可以得到最小约简。 s k o w r o n 的算法优点是简单、容易理解，能够一次求出决策表的全部属性约简，同 时在实际应用中较容易实现，其缺点首先是由于要求生成差别矩阵的中间环节，因此当 论域的对象与属性的规模较大时，差别矩阵将占有大量的存储空间( 对象数n 的二次 方) ；其次是差别函数的化简也是一个n p h a r d 问题，因此只要数据集稍大一点，s k o w r o n 的算法就不具备可操作性。为此，人们提出了各种改进的差别矩阵及属性约简方法，刘 清提出的对可辨矩阵方法进行简化的方法，不用生成差别矩阵，直接从信息系统中提取 属性值是分明的那些属性，构造成分明合取范式，然后作等价变换，直接得到最小的析 取范式，由于不用生成分明矩阵，从而节省了空间和时间，算法的效率也大大提高了【8 】； 申爱华提出的改进分明矩阵生成算法，在生成分明矩阵时的循环过程中利用吸收律及时 进行化简，在记录较多的情况下对于降低空间利用率，提高运算速度是有效的【9 】；另外 还有本质完全相同的两种算法：张媛提出的对称矩阵方法【1 0 1 与苗夺谦等人提出的帽异矩 阵方法】，这两种算法都是在差别矩阵的基础上提出相异矩阵( 对称矩阵) 的概念，直接 从决策表中构造相异矩阵( 对称矩阵) 来进行数据约简，与z p a w l a k 的数据分析法相比 较，容易实现，与差别矩阵方法相比较，省去计算最小析取范式的步骤；刘清提出的拓 广分明矩阵方法，该算法在简化差别矩阵的基础之上，将不同的个体分别置于不同的行 和列进行计算，通过构造关联图，然后直接进行数据约简【1 2 】；高学东提出对差别矩阵进 行改进，组成简化决策表，然后利用区分对象对集的概念进行约简，算法复杂度得以很 大程度地提耐1 3 】。 2 中国也油丈学硕i t 学位论文 以上这些基于差别矩阵的算法，均只考虑了通过改进差别矩阵来提升算法的性能， 而忽略了在决策表中，难免会有重复的数据和不一致对象，而差别矩阵的定义中，没有 充分考虑到决策表不相容性及其程度的影响，导致对不一致决策表的约简中，如果按 s k o w r o n 的方法，求得的属性核和约简可能是不j 下确的，大量的相同对象和不相容对象 还会导致约简算法效率的低下，结果可能会出现错误。例如最典型的x i a o h u ah u 给出 的利用改进分辨矩阵来确定核的方法，叶东毅和王希雷均指出这种求核方法在非一致 决策表中存在着不妥。叶东毅指出因为决策表中的不一致性，x i a o h u ah u 定义的分辨 矩阵在确定非一致性决策表核属性时产生错误，h u 的求核方法只能应用于一致性决策 裂”】。王希雷认为h u 提出的分辨矩阵对非一致性决策表具有部分处理能力的错误0 6 】。 针对x i a o h u ah u 算法的不足，尹一麒提出了基于分体策略的差别矩阵算法【 】，采用标志 位来实现对原决策表的分解，修正了原差别矩阵方法的不足，能较好地解决不一致表产 生的问题，在实际问题求解中有一定的应用价值，但算法比较复杂难懂，算法的复杂度 与效率还有提高的空间。 求取所有约简是一个n p h a r d 问题，因此运用启发信息来简化计算，找出最优或次 优约简显然是一种可取的方法。启发信息主要有属性重要性、属性频率、属性依赖度f 1 8 】 等信息。大多数启发式约简算法的基本步骤都是由信息系统或决策表的核为起始点，然 后根据属性重要性的某种测度，依次选择最重要的属性加人核中，直到满足终止条件， 便得到信息系统或决策表的一个约简f 1 9 】。利用启发式算法的确能够提高约简的求解速 度，在解空间不复杂的情况下有可能得到最优解或次优解，但在解空日j 较复杂或属性间 关系复杂的情况下，用这些方法找到的解极有可能陷人局部最优解，这种算法并非对所 有的知识表达系统都适用【2 们。 直到现在为止，国内外一些改进的差别矩阵优化算法仍可进一步完善，还没有一个 公认的比较满意的粗集约简算法，寻求一种高效的适用于所有数据的约简算法仍然是当 自口韦r 集研究的热点。 2 神经网络结构优化剪枝法研究现状 剪枝法被公认为是优化网络结构，提高网络泛化能力的有效办法。r e e d 对剪枝算 法做过分类【2 ”，最常用的三种剪枝方法为权衰减方法，灵敏度方法及相关性剪枝方法 1 2 2 1 。 权衰减法通过在网络目标函数中引入表示结构复杂性的j 下则化项来表示网络结构 复杂性例，由于正则化项的剪枝特性，训练过程中的一些冗余的连接权将衰减到零，从 第一帝绪论 而达到剪枝的目的。由于权衰减法中的正则化参数x 对神经网络的泛化能力有很大影 响，且比较难以整定，小川哲等采用进化策略来寻找正则化参数 ，较大的改进了网络 泛化能力”1 ，w e i g e n d 等人也给出了自己的j 下则化参数调整方法，用于剪除网络中冗余 的权值。权衰减法中典型的算法是w e i g e n d 等人提出的权消去法1 。 灵敏度方法是一种计算节点( 输入节点及隐节点) 或连接权对网络误差的贡献( 灵 敏度) ，删除那些贡献最小的节点或权的剪枝方法。对于灵敏度的计算，k a m i n 认为可 近似为每次权值调整时，误差e 变化时的累计【2 7 】，h a s s i b i 和s t o r k 提出了改进的计算灵 敏度的方法，但计算量较大【2 9 l 。对于节点何时被删除，m o z e r 和s m o l e n s k y 提出当某 一节点的灵敏度低于预定的阈值时，该节点应被删除，但却存在误删连接权的可能f 2 9 】； 松永丰等人重新定义了节点的灵敏度为有效度，这样可以在每次学习后直接删除有效度 最低的节点，或通过节点间的竞争，自动淘汰有效度低的节点。 根据节点问相关性( 或相互作用) 进行剪枝，这就是相关性剪枝法。节点的输出相 互能否线性表出表明了网络是否存在冗余节点，村用纯一等用它来找出并删除对网络输 出影响最小的一个节点，但该算法每删除一个节点均需重新训练权值；鹿山昌宏等把一 个节点由另外节点线性表出的程度量化，并用节点问不能相互表出的部分( 非线性部分) 之和作为最优隐节点数目，最后重新训练网络权值【3 0 l ；c a s t e l l a n o 等选择对所有模式输 出能量最小的隐节点为被删除的节点，然后调整以该被删除节点为输入节点的输入权 值，使这些节点的总输入保持不变，以保证整个网络在删除节点后保持不变川。 3 粗集与神经网络结合的研究现状 为了充分发挥粗集理论的决策能力，一些学者提出了将粗集理论与神经网络进行融 合的方法，有的利用粗集约简神经网络的输入，以减少网络规模，有的用粗集来进行神 经网络的结构设计或优化，其中比较典型的有：中国的陈遵德与新加坡国立大学的l i x i a n g s h e n 用粗集理论对属性进行优选，由此确定所含属性最少的网络输入，减小网络 规模，提高训练速度，优点是可明显提高分类的j 下确率，同时减少了分析测试指标数， 节省了测试费用和时间，缺点是粗集与神经网络的结合松散，样本中的冗余数据没有完 全排除1 3 2 ；法国的y a h i am e ，m a h m o d 3 3 l 和哈工大的郝丽娜【3 4 】，大庆石油学院的刘树 林等人提出的粗集神经网络方法仅从条件属性和样本数据的约简构造网络，没有考虑网 络内部结构优化；李永敏等人提出一种采用粗集理论从样本数据中发现规则，对隐层节 点进行b p 网络设计的方法，缺点是规则很多时网络结构会变得复杂庞大【3 5 】：杨建刚， 戴德成等人提出用粗集对b p 网络结构进行改进，在改进过程中需要计算样本信息熵及 4 中国石油大学硕1 ：学位论文 其闽值，而多数情况下信息熵的阂值并不易客观地确定【3 6 1 ；东南大学的凌维业采用粗集 理论优化b p 神经网络的特点是直接互连核元素及其对应输出层神经元，使核元素变化 直接反映神经网络的输出【3 7 】。 1 3 研究内容及创新点 1 3 1 课题研究内容 1 研究决策表中相同对象与不相容对象对约简的影响，提出了冗余对象，冗余决策 表，最简决策表，对象频度等概念，提出在决策表约简时应先求出最简决策表，然后在 最简决策表上进行约简，由此提出了求最简决策表的算法，算法利用了对象频度的概念， 删除了相同的对象和频度低的不相容对象，组建最简决策表，最后把求最简决策表的算 法与区分对象对集的算法结合起来，形成了一种粗集约简算法s d t r a ( s i m p l e s td e c i s i o n t a b l er e d u c t i o na l g o r i t h m ) 算法。 2 研究b p 网络的结构优化理论，分析了权衰减法、灵敏度法及相关性法等剪枝法的 特点，然后根据b p 网络学习与权值调整的特点，结合了粗集能够优化约简冗余信息的长 处，提出了在网络的训练过程中利用网络输出误差和权值调整来构建决策表，然后对此 决策表进行约简，最后根据约简的结果删除冗余的权值和节点，得到一个结构紧凑的网 络神经网络结构设计的新方法一粗集法。 3 在对粗集约简理论与粗集优化神经网络结构的基础上，构建基于神经网络的故障 诊断专家系统模型，并设计出一个诊断柴油机气阀开度故障诊断的专家系统。 1 3 2 课题创新点 1 本文提出了冗余对象，冗余决策表，最简决策表，对象频度等概念，然后在此基 础上，提出了求最简决策表的算法，算法利用了对象频度的概念，删除相同的对象和频 度低的不相容对象，组建最简决策表。然后把求最简决策表的算法与区分对象对集的算 法结合起来，形成了一种粗集约简算法s d t r a 算法。 2 本文提出了一种神经网络剪枝设计的新方法一粗集法。设计一个与实际应用相符 的结构无冗余的神经网络，以往多靠经验和试探，本文提出了一种利用粗集约简理论， 对有冗余的多层神经网络，用粗集约简剪枝多余的连接和神经元，最后得到结构无冗余 的神经网络的设计新方法。与现有的剪枝法相比较，证明了它是高效的剪枝方法。 3 本文提出的专家系统模型，粗集与神经网络的结合更为紧密，不仅用粗集约简故 障数据，消除了冗余，减少了神经网络的输入维数，而且对神经网络结构进行优化，使 得整个专家系统中没有冗余的部分，因此进行故障诊断时速度快，结果准确度更高。 第一帝绪论 1 4 论文的组织结构 本文的第1 章主要介绍了本课题的研究意义、国内外研究现状和本课题的研究内容 及创新性等。 第2 章首先对粗集理论进行了简单介绍，然后讨论了决策表中相同对象与不相容对 象对约简的影响，提出了冗余对象，冗余决策表，最简决策表，对象频度等概念，然后 提出了求最简决策表的算法与粗集约简算法s d t r a 算法。 第3 章首先简单介绍了b p 神经网络理论，然后对神经网络的结构优化进行了研究， 并提出了用粗集优化神经网络结构的原理，方法和算法步骤，并用实例证明，该算法能 快速有效地优化网络结构。 第4 章在2 、3 两章的基础上，提出了基于粗集神经网络的故障诊断专家系统模型， 构建了一个柴油机气阀开度故障诊断的专家系统，对基于神经网络的各种专家系统进行 了性能的对比分析。 第5 章为结论与展望，对本论文的所取得的研究成果进行总结，并对论文中的不足， 以后应进行的工作进行了展望。 6 中国石油大学硕士学位论文 第2 章粗集约简算法研究 2 1 粗集理论基础 波兰数学家z p a w l a k 提出的粗集理论，使用决策系统对问题进行描述，粗集的方 法和模型建立在一种非常直观的二维决策表的基础上。下面是有关基本概念的介绍【3 8 】： 定义2 1 决策系统称s = ( u ，c ，d ，v ，f ，d ) 为知识表示系统，其中u 为论域( 对 象集) ，c ，d 分别为条件属性集与决策属性集，u ，c ，d 均为非空有限集；v = u v a ， a e ( c u d ) ，v a 表示属性a 的值域；f iu x c v 和d ：u x d v 是信息函数。如果a 由条件属性集合c 和决策属性集合d 组成，c 、d 满足c u d = a ，c n d = 巾，则称s 为 决策系统，表示方法为s = ( u ，c u d ) 或s = ( u ，c u d ) ) 。在一个决策系统中，可以认 为u 的每个元素对应一条规则，规则的前件由c 及其取值决定，后件由d 及其取值决 定。 定义2 2 不可分辨关系对决策系统s = ( u ，cu d ) ) ，b c c 是条件属性集合的一 个子集，称二元关系n d ( b ， d ) ) = ( x ，y ) u x u ：d ( x ) = d ( y ) 或者v a b ，“x ) = a ( ” 为s 的不可分辩关系，其中，x ，y 为u 中的元素。不可分辨关系是一个等价关系，通 过一个不可分辨关系，可以得到决策系统的一个划分，我们称划分后的等价类为不可分 辨类，通常用口】i n d ( 8 ) 来表示包含元素x 的不可分辨类。在不引起混淆的情况下，我们 常常用i n d ( b ) 来表示不可分辨关系1 n d ( b ， d ) 。 定义2 3 上近似和下近似对于知识表示系统s = ( u ，a ) ，设b g a ，x c u ，我们称 b x = x u l x m d ( b ) c _ x ，百x = x u i 【x 】i n 叩) n x a 分别为x 的b 下近似 ( b l o w e r a p p r o x i m a t i o n ) 和b 一上近似( b u p p e r a p p r o x i m a t i o n ) 。 定义2 4 正域、负域和边界p o s 8 ( x ) - 旦x ，n e g b ( x ) = u 吾x ，b n b ( x ) = 百x - b x 分别称为x 在b 下的正域、负域和边界，它们的直观解释为：p o s a ( x ) 是o e e 根据现有的信息( 不 可分辨关系i n d ( b ) ) 可确定划归入x 的不可分辨类的元素的集合：n e g b ( x ) 是肯定不属 于朋0 不可分辨类的元素的集合；b n b 是根据现有的信息，可能属于z 也可能不属于x 元素的集合；而面积u 是所有可能属于x ( 包括确定属于x ，i i p b x ) 的不可分辨类的元素 的集合。 在一个决策系统中，各个条件属性之间往往存在着某些程度上的依赖或关联，也就 是说，一般存在c c c ，由c ，中的属性可以确定结论属性d 的取值。这也f 是我们在知识 第2 市辑i 集约 句算法研究 发现中感兴趣的问题，即从中发现那些简单的、概括化的知识。 定义2 5 简约对于一个给定的决策系统s = ( u ，c u d ) ，条件属性集合c 的简约是 c 的一个非空子集c ，它满足： 1 i n d ( c ， d ) ) = i n d ( c ， d ) ) 2 不存在c ”cc ，使i n d ( c ”， d ) = i n d ( c ， d ) c 的所有的简约的集合记作r e d ( c ) 。简约可以理解为：在不丢失信息的 筘提下，可 以最简单的表示决策系统的结论属性对条件属性的集合的依赖和关联。整个决策系统的 简约，在描述u 中的单个规则时，并不是每一个属性都是必需的，因此我们需要用相对 简约来表示这个问题。 定义2 6 相对可去除属性对于决策系统s = ( u ，cu d ) ) ，不可分辨关系i n d ( c ) 将u 划分为t 个不可分辨类x l ，x 2 ，x t ，令d ( x i ) 为x i 的所有结论属性d 的取值的集合， 0 0 d ( x i ) = v = d ( x ) ：x ) ( i ) ，如果d ( i n d ( c - a ”) = d ( x i ) ，条件属性a c 称为相对于不可 分辨类x i 可去除的。直观地理解，如果a 为相对于) ( i 可去除，s t j a 的存在与否不影响x i 的 结论值的集合。 定义2 7 相对简约对于决策系统s = ( u ，cu d ”，不可分辨关系i n d ( c ) 将u 划分为 t 个不可分辨类肌，尼，胤，琳为c 相对于不可分辨类x i 的简约，如果v a e c ， a 为相对于x i 不可去除。相对于x i 的所有简约的集合记作r e d ( c ，x i ) 。这样，通过一组 相对简约，我们可以得到决策系统s = ( u ，c u d ) ) 中最简单的规则集，其中每个相对简 约就是一条( 决策系统一致) 或一组规则( 决策系统不一致) 的f i 件。 从以上定义我们可以得出这样的结论：决策系统中的各个条件属性日j 往往存在着某 些程度上的依赖或关联，约简可以理解为在不影响分类的前提下，最简单地表示决策系 统结论属性的条件属性集合；决策表是约简的起点，在表中通常存在冗余属性，通过决 策表的属性约简既可去除这些冗余属性，又可保留原始决策系统的所有决策规则。 2 2 粗集约简算法s d t r a 算法 2 2 1 冗余对象定义 为了方便，本文首先定义讨论所涉及到的概念： 定义2 8 相同对象决策表中存在着两对象x ，y e u ，当x y 时 可推出结论f ( x ，d ) = f u ，d ) ，则我们说对象x 与对象y 是相同的对象。 定义2 9 不相容对象决策表中任意两对象x ，y u ，当x c y 时， 如果由f ( x ，c ) = f ( y ，c ) 如果f ( x ，c ) - - f ( y ，c ) 可 中国石油大学碗上学位论文 推出结论f ( x ，d ) c f ( y ，d ) ，则我们说对象x 与对象y 是不相容( 不一致) 的对象。 定义2 1 0 冗余对象决策表中可删除的相同对象和不相容对象统称为冗余对象。 定义2 1 1 冗余决策表存在着冗余对象的决策表，我们统称为冗余决策表。冗余 决策表中存在着可删除的冗余对象，丽当决策表中仅存在着相同对象时，一般称为相容 决策表( 一致决策表) ：当决策表中存在着不相容对象时，一般称为不相容决策表( 不 一致决策表) 。 冗余决策表中有的决策规则是相容的，但有的决策规则是不相容的。对相容决策 表，当对象在条件属性集上取值相同时，决策属性值也必定相同；不一致决策表中，至 少存在两个对象，它们在条件属性集上取值相同，但决策值却不相等；而冗余决策表中， 至少存在两个对象，它们在条件属性集上取值相同，但决策属性值可能相同，也有可能 不同。 2 2 2 冗余对象对约简的影响 现有的决策表中，存在着大量相同的对象和不相容的对象一冗余对象。这些冗余对 象对约简主要有以下影响： 1 由于目前的算法均没有充分考虑到决策表不相容性及其程度的影响，所以求得的 属性核和约简可能是不j 下确的，甚至会产生错误。 例如下表中： 表2 1 决策表1 t a b l e 2 1d e c i s i o nt a b l el abcd m 1l101 m 211oo m 3l00l m 4 1 oo o m 51 0 o2 m 6111l m 7o】l0 d 为决策属性，a 、b 、c 为条件属性，m 1 m 7 为对象，其中m 1 与m 2 ，m 3 与m 4 、m 5 为不相容对象，因此该决策表为冗余决策表，基于差别矩阵的约简算法得到的核属 9 第2 章轲1 集约简算法研究 性为 a , b ，c ，而很明显的是b 并不是核，由此产生的约简是错误的。 2 对于决策表中相同的对象与不相容对象，虽然目前的约简算法能够一次求出决 策表的全部属性约简，但算法将进行重复计算，因此算法的性能降低，算法的性 能也受到影响。 例如下表： 表2 - 2 决策表2 7 h b i e 2 2d e e i s i o nt a b l e2 a bcd d m l 3 4 24 2 m 22l2 3 3 m 3 3 4 241 m 4 322l3 m 5l3l2l m 621232 m 713l2l m 832 21 3 m 92l2 3 2 m 1 013 12 o m 1 l22l 2 l m 1 232 32o m 1 31111o m 1 422l21 表2 2 中有1 4 个对象，m 1 与m 3 是不相容的，m 2 与m 6 、m 9 是不相容的，m 5 与m 1 0 是不相容的，m 4 与m 8 相同，m 5 与m 7 相同，m 1 i 与m 1 4 相同，因此它是冗余的决策表。 一般的粗集约简算法，对这些对象一视同仁，进行约简，因此约简算法多花销了在这些 相同对象与不相容对象上进行约简的时自j ，算法的性能较低。 3 算法选择不相容对象时，如果选择不当，得到的决策规则有可能是错误的。 糯集算法的优点在于即使没有先验知识，经决策表约简后也能形成决策规则。i j 文 也讨论了冗余决策表中存在着不相容对象，尹一麒等在分体策略在差别矩阵优化中的 0 中国石油人学硕i 。学位论文 应用一文中认为，不一致的对象对决策规则的形成不起作用，其实这是错误的；考虑 到决策系统的完备性，我们必须考虑不相容对象的作用，而不相容对象中，到底选取那 一条对象来形成决策规则，则影响到整个决策系统的组成，目前的约简算法很少考虑甚 至根本没考虑到这个问题，因此选取不相容对象时，显然具有随意性，如高学东的高效 算法中其实选取了不相容对象中的第一个对象形成决策规则，而忽略了不相容对象中相 同对象的频度对决策的影响因素。 因此本文充分考虑了不相容对象的选择问题以及相同对象对约简算法性能的影响， 提出了一种粗集约简算法，首先把冗余决策表优化为一个最简决策表，然后仅对最简决 策表进行约简，这样由于约简算法中减少了对相同对象与不相容对象的约简时间，使得 约简算法的性能大大得到提高，实例证明了该算法不仅适用于不相容决策表，并且在时 间复杂度和空间复杂度上较现有的算法有一定的改进，更直观，更易于理解。 2 2 3 求最简决策表的算法 针对决策表中存在大量对象相同或不相容的问题，本文提出了删除这些相同或不相 容的对象，这样把冗余决策表变成了最简决策表，达到提高约简算法的性能的目的。由 决策表对象与属性的性质得知，属性值均相同的对象中任一个对象与其他对象产生的决 策规则是一样的，因此我们考虑决策表中只须保留这些相同对象中的任一对象即可。对 于不相容对象，由于它们中又存在着相容对象，因此情况稍微复杂一些，为了讨论方便， 我们先进行一些概念的定义： 定义2 1 2 对象频度g ( x ) 对象频度g ( x ) 就是对象x 在决策表中出现的次数。 对象频度烈x ) 概念的定义主要是为了本文提出的对不相容对象的选取而提出的，算 法将根据该对象的频度来选取不相容对象，即选取频度数最大的不相容对象来构建最筒 决策表，从而形成决策规则，这点不同于高学东的算法中暗含的选取最先出现的不相容 对象选择规则。这一点是毋庸置疑的，例如某决策表中有1 1 个对象的条件属性值相同， 而决策属性值不同，其中第1 个对象的决策属性值不同于后面的l o 个对象的决策属性值， 而这l o 个对象的值却相同，很明显后面这相同的l o 个对象对决策的影响应大于第1 条， 应选取入决策系统，但按照高学东等人提出的算法，却选取了第1 个对象进入决策系统， 因此以后可能形成错误的决策规则。 因此本文提出的算法中，选取频度数最大的不相容对象来构建最简决策表 定义2 1 3 最简决策表如果决策表s = ( u ，c u d ) ，对象x 、y e u ，如果当x y 时，对 任意的b c ，不存在f ( x ，b ) = f ( y ，b ) ，则我们称决策表s 为最简决策表。 第2 章租集约简算法研究 由最简决策表的定义我们得知： 最简决策表与冗余决策表其实是等价的，最简决策表的任一非空元素一定与冗余决 策表的一元素对应，这两种决策表的包含形成决策规则的对象是一样的，所拥有的信息 量也是相等的，但最简决策表中不存在着相同的对象与不相容的对象，因此我们约简时 可以将基于原冗余决策表上的属性约简转化到基于最简决策表上进行。 本文在以上讨论的基础上，根据高学东求u c 的算法把改进后得到了求最简决策表 的的算法，原算法只能求u c ，本文改进后算法不仅能求出u c ，还能求出最简决策表， 提出的算法步骤如下： 算法输入：冗余决策表s = ( u ，c ，d ，v ，f ，d ) 初始决策表： u = “，而，矗 为对象集合，共n 个对象； c = q ，c 2 ，e ) 为属性集合，共s 个属性。 算法输出：最简决策表s ，u c 第一步：- 令s e t t o = u ； 第二步：f o r ( i = l ；i s + l ；i + + ) s e t i = 矽； k = 1 ： w h i l e ( s e t i 一1 】i _ ) 取出s e t i 一1 】的第一个元素s ； s e t i l 】2s e t i l 】 s ) ： w h i l e ( s ! = 庐) 以下均为对s 的操作 ( h t = 扒 s 中的第一个元素x 并入士0 并在s 中删除元素x ； 对s 中的其他元素y ： i ff ( y ，q ) = f ( x ，q ) 2 中国山油人学坝l 。学位论义 将元素y 并入h , k ： 在s 中删除元素y ； s e t i 】= s e t i u e 女) ； k = k + l ； ) 第三步：设第二步得到的集合距r 【跚= ，以：，日。 ； f o r ( i 2 l ；i t + 1 ：i 十n w h i l e ( h 。妒) 依次取出h 。中的每一个对象x ： i f ( g ( x ) 0 ) g ( x ) = 1 ； 取出h 。，中的其他任一对象y i f ( f ( x ，d ) = f ( y ，d ) ) g ( x ) = g ( x ) + 1 ； 烈y ) = o ) 第四步：求解最简决策表与u c 。 = ；= 矽：u = 庐： f o r ( i 2 1 ：i 0 ； w 户一玎旦 ( 3 1 0 ) 酾j k 一瓦 ! ” 第3 章辋i 集优化神鲐嘲络结构方法研究 定义反向传播误差信号瓯为 o e ：生塑堕 ( 3 1 1