基于粗糙集理论的知识建模方法与焊接动态过程知识模型的研究

《基于粗糙集理论的知识建模方法与焊接动态过程知识模型的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

上海交通大学博士学位论文基于粗糙集理论的知识建模方法与焊接动态过程知识模型的研究姓名：王兵申请学位级别：博士专业：材料加工工程指导教师：陈善本20031001 上海交通大学博士学位论文基于粗糙集理论的知识建模方法与焊接动态过程知识模型的研究摘要智能控制理论的研究对象是具有大量不确定性的复杂过程在智能控制系统设计中获取复杂过程的知识模型是具有重要意义的众所周知电弧焊接过程是非线性多变量时变强耦合的并且涉及大量的不确定因素因而该过程是典型的复杂过程对电弧焊接过程采用经典的建模方法获取其精确的数学模型是极为困难的获取电弧焊接过程的知识模型进而实现该过程的智能控制是焊接技术发展的趋势之一近年来用模糊集方法神经网络方法以及两者相结合的方法获取焊接过程的知识模型成为科研人员关注的焦点并取得了许多有意义的成果但是这些方法仍存在不足不能完全满足实际需要有必要对这类复杂过程的建模方法做进一步的研究粗糙集理论是处理不确定性的有效数学工具该理论的出现为复杂过程的建模提供了新的方法本文以粗糙集理论为基础针对铝合金脉冲TIG焊接动态过程的复杂性提出了复杂过程的系统化的粗糙集知识建模方法并对其中的关键算法进行了深入的研究并通过验证实验证明了粗糙集知识建模方法可以有效的获取铝合金脉冲TIG焊接动态过程1 上海交通大学博士学位论文的知识模型和控制模型模型的复杂程度和精度都是可以满足要求的并且模型是易于理解的本文的主要研究成果如下第一提出了粗糙集方法中知识模型的概念在此基础上提出了粗糙集知识建模方法的步骤建模数据获取数据预处理连续属性离散化条件属性约简条件属性值约简规则约简和知识推理第二研究了建模方法中各步骤所涉及到的理论与算法问题并对其中一些问题进行了必要的形式化提出了相应的解决方法1建模数据获取为了满足粗糙集知识建模方法的假设条件即建模数据要覆盖系统输入空间必须保证足够的数据量和数据的有效性2数据预处理主要解决数据扩展的问题这是获得系统动态模型的前提本文提出了数据扩展的具体方法3连续属性离散化由于粗糙集理论的处理对象主要是符号数值对象必须经过离散化才可以利用粗糙集理论加以处理本文对决策表中连续属性的离散化进行了形式描述4条件属性约简提出了条件属性约简算法的分类方法总结了条件属性约简的不唯2 上海交通大学博士学位论文一性以及由此引出的条件属性约简最优解问题5条件属性值约简根据对条件属性值约简同条件属性约简在功能上的部分重叠的分析确定了这两个步骤的先后次序即条件属性约简在前条件属性值约简在后根据对条件属性值约简相对条件属性约简的特殊性的分析得出了条件属性值约简不能只求一种解的结论这一结论同条件属性值约简无法求全部解构成了条件属性值约简过程中的一对矛盾本文提出了利用条件属性值约简算法中的随机环节解决这一矛盾的策略6规则约简提出了模型原型的概念并给出了规则集合的直观表示形式同时定义了规则匹配度提出了模型输出形式转换的方法7知识推理在规则匹配度定义的基础上给出了知识推理的具体方法此外以知识模型为核心构成了粗糙集知识处理系统并对使用该知识处理系统预测系统输出的方法也进行了阐述第三分别证明了粗糙集理论中条件属性约简条件属性值约简以及规则约简同集合论中集合极小覆盖的有条件等价性从而阐明了三种约简的本质联系为根据条件属性约简算法构造条件属性值约简和规则约简算法提供了理论基础第四提出了三种条件属性约简算法即ARSEAARRSEA和3 上海交通大学博士学位论文ARPSEA已有条件属性约简算法所采用的策略可以分为两种其一是以核为基础按照一定的顺序添加条件属性直至满足算法结束条件其二是以全部条件属性为基础按照一定顺序从中删除可以删除的条件属性直至满足算法的结束条件本文中提出的条件属性约简算法将两种策略结合起来以核为基础按照一定的条件判断是添加条件属性还是删除条件属性直至满足算法的结束条件所提出的三种算法都是完备的文中给出了算法完备性的理论证明ARSEA是另外两种算法的基础ARRSEA采用随机环节降低了ARSEA的计算复杂性而ARPSEA则在ARRSEA的基础上通过定义条件属性集上的偏序关系使得该算法可以充分利用先验知识保证了算法的结果同实际经验的符合增强了最终模型的易理解性第五在ARRSEA和ARPSEA的基础上构造了两种条件属性值约简算法即VRRSEA和VRPSEA这两种算法也具有类似条件属性约简算法的完备性并且VRPSEA可以利用先验知识第六在ARSEA和ARRSEA的基础上构造了两种规则约简算法即RRSEA和RRRSEA第七设计并实现了粗糙集知识建模软件系统RSMS系统涵盖了粗糙集知识建模过程中的全部所需功能并集成了一些辅助的模型复杂程度和精度计算等功能第八进行了用粗糙集知识建模方法获取铝合金脉冲TIG焊接动态4 上海交通大学博士学位论文过程知识模型的验证实验验证实验结果表明对于电弧焊接过程这类具有大量不确定因素的复杂过程粗糙集知识建模方法可以有效的获取其过程模型第九利用铝合金脉冲TIG焊接动态过程的PID控制器和最小方差自适应控制器数据进行了用粗糙集知识建模方法获取相应控制器粗糙集知识模型描述的验证实验验证实验结果表明对于电弧焊接动态过程这类具有大量不确定因素的复杂过程粗糙集知识建模方法可以有效的获取其控制模型关键词粗糙集焊接过程建模知识模型铝合金脉冲TIG焊5 上海交通大学博士学位论文STUDYONKNOWLEDGEMODELINGMETHODBASEDONROUGHSETTHEORYANDKNOWLEDGEMODELSOFWELDINGDYNAMICPROCESSESABSTRACTIntelligentcontroltheoryismoresuitabletodealwithcomplexprocessesconcerningagreatnumberofuncertainties.Toobtainknowledgemodelsofthesecomplexprocessesisverysignificantforthedesignofintelligentcontrolsystem.Itiswellknownthatarcweldingprocessesarenonlinear,multivariable,timevaryingandstrongcoupledandalsoconcernmanyuncertainties.Thus,arcweldingprocessesaretypicalcomplexprocesses.Itistoohardtoobtainaccuratemathematicalmodelsofarcweldingprocessesusingclassicalmodelingmethods.Toobtainknowledgemodelsofarcweldingprocessesandrealizetheintelligentcontroloftheseprocessesisoneofthetrendsofdevelopmentofweldingtechnology.Inrecentyears,itisbecomingthefocusoftechnologistsandengineers6 上海交通大学博士学位论文togetknowledgemodelsofweldingprocesseswiththefuzzysetmethod,theneuralnetworkmethodortheircombination.Manyinterestingresultshavebeengot,however,disadvantagesofthesemethodsareobvious.Theycouldnotcompletelysatisfythepracticalneeds.Furtherresearchesarenecessary.Roughsettheoryisaneffectivemathematicaltooldealingwithuncertainties,whichprovidesanewmethodforthemodelingofcomplexprocesses.ConsideringcomplexitiesofthealuminumalloypulseTIGweldingdynamicprocess,thisdissertationproposesthesystematicalroughsetknowledgemodelingmethodofcomplexprocessesbasedontheroughsettheory.Keyalgorithmsofthemethodarestudiedindetail.Verifyingexperimentsarecarriedout,whichprovetheroughsetknowledgemethodcanobtaintheprocessmodelandcontrolmodelofthealuminumalloypulseTIGweldingdynamicprocess.Thecomplexitiesandprecisionsofmodelsaresatisfiedandmodelsareeasytobeunderstood.Mainresearchresultsarethefollowing:1.Thenotionoftheknowledgemodelintheroughsetmodelingmethodisgivenfirst.Thenmainstepsoftheroughsetknowledgemodelingmethodareproposed,whichincludemodelingdataacquisition,datapreprocessing,continuousattributediscretization,conditionattributereduction,conditionattributevaluereduction,rulereductionandmodelextension.7 上海交通大学博士学位论文2.Sometheoreticalandalgorithmicproblemsinvolvedineachsteparestudied.Afewofthemareformularizedandpracticalsolutionsaregiven.(1)ModelingdataacquisitionThequantityandthequalityofdatahavetobeensuredtosatisfythehypothesisoftheroughsetmodelingmethod,namely,themodelingdatashouldcovertheinputspaceofthesystem.(2)DatapreprocessingDatapreprocessingmainlysolvestheproblemofdataexpansion,whichisthepremiseofobtainingdynamicmodelofsystems.Themethodofdataexpansionisinvestigated.(3)ContinuousattributediscretizationBecauseroughsettheorycanonlydealwithsymbols,itisnecessarytodiscretizerealvaluesintosymbols.Formaldescriptionsofcontinuousattributediscretizationinroughsetknowledgemodelingmethodaregiven.(4)ConditionattributereductionWaysoftheclassificationofthealgorithmsofconditionattributereductionareputforward.Thecharacterthatoneconditionattributesetcanhavemorethanonereductionisanalyzedandtheoptimizationproblemderivedfromthecharacterisalsodiscussed.(5)Conditionattributevaluereduction8 上海交通大学博士学位论文Accordingtotheinvestigationofthepartialfunctionaloverlapofconditionattributereductionandconditionattributevaluereduction,theorderofthesetwostepsisdetermined,namely,theattributereductionshouldbetakenbeforetheattributevaluereduction.Thedifferencesbetweencomputingthereductionofconditionattributesandcomputingthereductionofconditionattributevaluesareanalyzedandtheconclusioniswecouldnotgetonlyonesolutionduringcomputingattributevaluereduction.Atthesametime,wecouldnotgetallsolutions.Thisisacontradictionand,inthisdissertation,weadoptarandomoperationintheattributevaluereductionalgorithmtosolvethecontradiction.(6)RulereductionThenotionoftheprototypeofthemodelandtheintuitionalwayoftheexpressionoftherulesetareproposed.Thedefinitionofthedegreeofthematchingofrulesisgiven.Thewayofconvertingtheformoftheoutputofthemodelisputforward.(7)KnowledgereasoningThedetailedmethodofreasoningisgivenbasedonthedefinitionofthedegreeofthematchingofrules.Inaddition,weconstructtheroughsetknowledgeprocessingsystemonthebasisoftherulemodelandgiventhewayofpredictingtheoutputofthe9 上海交通大学博士学位论文systemusingtheknowledgeprocessingsystem.3.Thisdissertationseparatelyprovesthatconditionattributereduction,conditionattributevaluereductionandrulereductioninroughsettheoryareequivalenttotheminimalsetcoverinsettheoryundercertainconditions.Thisclarifiestheessentialrelationshipbetweenthreekindsofreduction.Itisthetheoreticalbasisofconstructingconditionattributevaluereductionalgorithmsandrulereductionalgorithmsbyconditionattributereductionalgorithms.4.Threeconditionattributereductionalgorithmsareproposed,namelyARSEA,ARRSEAandARPSEA.Therearetwomainstrategiesadoptedbypresentedconditionattributereductionalgorithms.Oneisonthebasisofthecoreoftheconditionattributesandthealgorithmaddsconditionattributesintothecoreaccordingtocertainorderstilltheterminationconditionissatisfied.Theotherisonthebasisofthesetofconditionattributesandthealgorithmeliminatesavailableconditionattributesfromthissetaccordingtocertainorderstilltheterminationconditionissatisfied.Algorithmsinthisdissertationintegratebothstrategies,whichisonthebasisofthecoreanddecideswhethertoaddortoeliminateconditionattributesaccordingtoacertaincriteriontilltheterminationconditionissatisfied.Allofthreealgorithmsarecompleteandtheproofisgiveninthedissertation.ARSEAis10 上海交通大学博士学位论文thebasisoftheothertwoalgorithms.ThecomputationalcomplexityofARRSEAislowerthanthatofARSEA,sinceARRSEAadoptsonerandomoperation.BasedonARRSEA,ARPSEAcanmakefulluseofpriorknowledgebydefiningapartialorderrelationonthesetofconditionattributes,whichensurestheresultaccordswithpracticalexperienceandmakethemodeleasiertobeunderstood.5.Twoconditionattributevaluereductionalgorithms,VRRSEAandVRPSEA,areconstructedbasedonconditionattributereductionalgorithmsARRSEAandARPSEA.Bothalgorithmsarealsocompletejustlikeconditionattributereductionalgorithmsandthesecondalgorithmcanusepriorknowledgetoo.6.Tworulereductionalgorithms,RRSEAandRRRSEA,areconstructedbasedonconditionattributereductionalgorithmsARSEAandARRSEA.7.Theroughsetbasedmodelingsoftwaresystem(RSMS)isdesignedanddeveloped,whichincludesallfunctionsneededbytheroughsetknowledgemodelingmethodandintegratessomeauxiliaryfunctionssuchascomputingthecomplexityofthemodel,computingtheprecisionofthemodelandsoon.8.Verifyingexperimentsonobtainingknowledgemodelsofthe11 上海交通大学博士学位论文aluminumalloypulseTIGweldingdynamicprocessusingproposedroughsetknowledgemodelingmethodarecarriedout.Resultsofverifyingexperimentsshowthattheroughsetknowledgemodelingmethodcaneffectivelyobtaintheprocessmodelsofcomplexprocesseswithagreatnumberofuncertaintiessuchasarcweldingprocesses.9.UsingdataofthePIDcontrollerandtheminimumvarianceself-adaptivecontrollerofthealuminumalloypulseTIGweldingdynamicprocess,verifyingexperimentsonobtainingknowledgemodeldescriptionsofaccordingcontrollersusingproposedroughsetknowledgemodelingmethod.Resultsofverifyingexperimentsshowthattheroughsetknowledgemodelingmethodcaneffectivelyobtainthecontrolmodelsofcomplexprocesseswithagreatnumberofuncertaintiessuchasarcweldingprocesses.KEYWORDS:roughset,weldingprocess,modeling,knowledgemodel,aluminumalloypulseTIGwelding12 上海交通大学学位论文原创性声明本人郑重声明所呈交的学位论文是本人在导师的指导下独立进行研究工作所取得的成果除文中已经注明引用的内容外本论文不包含任何其他个人或集体已经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明本人完全意识到本声明的法律结果由本人承担学位论文作者签名日期年月日 上海交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留使用学位论文的规定同意学校保留并向国家有关部门或机构送交论文的复印件和电子版允许论文被查阅和借阅本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索可以采用影印缩印或扫描等复制手段保存和汇编本学位论文保密在年解密后适用本授权书本学位论文属于不保密请在以上方框内打学位论文作者签名指导教师签名日期年月日日期年月日 上海交通大学博士学位论文第一章绪论1.1引言焊接是制造业中最重要的加工工艺方法之一它在机械制造核工业航空航天能源交通石油化工及建筑和电子等行业中的应用越来越广泛随着相关科学技术如材料冶金物理化学机械电子等的发展焊接自动化机器人化以及智能化已成为焊接技术的发展趋势[1]研究焊接工人的智能行为对焊接自动化的发展具有重要的启发意义一个熟练的焊接工人所表现出的高度适应能力是任何焊接机器人所无法比拟的在手工和半自动焊接过程中一个高水平的焊工通过观察接头的位置熔池的行为电弧形状和焊道外观可以感知焊接状态如果实际焊接过程同最佳状态不一致可以手动调节各种规范参数使之达到最佳以获得高质量的焊缝如果希望焊接过程由机械装置来完成即实现焊接过程自动化首先需要类似人体感官的焊接传感器焊接传感器是一个基于对影响焊接结果的内部和外部条件的检测从而能检测和控制焊接操作的探测器其次需要类似于焊工的对焊接过程的认识即能够描述焊接过程各种状态的知识也就是对焊接过程模型化最后需类似于人脑思维的控制器以实现合理控制规律可见焊接过程的自动控制系统除去对焊接设备本身的性能要求外需要以下三方面的关键技术焊接传感器焊接过程模型和焊接过程控制器图1-1这三方面技术在焊接过程自动控制中缺一不可在闭环控制系统中传感器主要是用于监测过程状态为控制系统提供反映过程特征的信息因此传感信号必须真实可靠焊接过程模型用于提供对焊接过程的认识一个好的数学模型应该能较好地反映实际焊接过程据此设计的控制系统才能较好地执行控制任务因此焊接过程建模是焊接过程控制系统设计的前提条件控制系统中核心部分是控制器的设计在焊接过程中所设计的控制器必须能够解决多参数耦合模型非线性和过程时变等问题电弧焊接由于焊接接头质量好设备简单可靠已经成为一种最重要的焊接1 上海交通大学博士学位论文图1-1焊接过程控制系统中的关键技术Fig.1-1Keytechnologiesinthecontrolsystemoftheweldingprocess方法对电弧焊接过程的建模是科研人员的研究重点之一1.2复杂过程建模方法概况[2]电弧焊接过程涉及大量的不确定因素是典型的复杂过程对这类复杂过程[3]获取其精确的数学模型是极为困难的因而获取这类过程的知识模型具有重要意义主要方法包括模糊集建模方法神经网络建模方法以及两者相结合的方法一模糊集建模方法对模糊集FS建模方法的研究是模糊控制理论研究的重要组成部分模糊控制系统通过定义模糊变量模糊集合及相应的隶属函数采用一组if–then形式的模糊规则来描述系统的输入与输出之间的对应关系这种用模糊规则来表示的系统的输入和输出关系称为模糊模型也称为语言模型[4]当前模糊模型主要有两种Mamdani模型和Sugeno模型T–S模型以多输入单输出MISO控制系统为例在Mamdani模型中第i条规则形式如下Ri:ifx1isAi1and...andxkisAikthenyisBi其中Ri表示模型第i条规则x1...xk和y均为语言变量x1...xk是系统的输入y是系统的输出Ai1...Aik和Bi是相应语言变量在其论域上的语言变量值2 上海交通大学博士学位论文在Sugeno模型中模糊规则的前提部分与Mamdani模型中的模糊规则有相同的结构其结论部分是一个前提部分变量的多项式是前提变量的线性函数而不再是一个简单的模糊集合如下所示Ri:ifx1isAi1and...andxkisAiktheny=pi0+pi1x1+...+pikxkSugeno模型实际上是对非线性动态过程的局部线性化表示模糊集建模方法可以认为是在上述两种模型基础上的系统辨识由于Mamdani模型可以直接转换为模糊关系方程所以模糊集建模方法可以概括为两种基于模糊关系方程的辨识方法和基于的Sugeno模型的辨识方法相关的细节可以在文献[4-8]中找到二神经网络建模方法控制系统的神经网络模型不同于模糊模型模型是由一系列神经元以一定的结构和权值互相联接构成的神经网络模型的种类很多但在控制领域中运用最为[9]普遍的模型是多层前馈神经网络其中又分为正向模型和逆模型两种所谓正向模型是指利用多层前馈神经网络通过训练或学习使其能够表达系统正向动力学特性的模型图1-2给出了获得系统正向模型的网络结构示意图图中神经网络与被建模系统并联两者的输出误差e被用作网络的训练信号图1-2正向模型Fig.1-2Forwardmodel3 上海交通大学博士学位论文图1-3直接逆建模图1-4正—逆建模Fig.1-3DirectandconversemodelingFig.1-4Forward-conversemodeling建立动态系统的逆模型在神经网络控制中起着关键作用并且得到了极为广泛的应用基于逆模型的建模方法主要有直接逆建模广义逆学习和正–逆建模狭义逆学习两种分别如图1-3和1-4所示由图1-3可知被建模系统的输出作为神经网络的输入神经网络的输出与系统输入比较相应的输入误差用来进行训练使用这种方法建模要假定系统的可逆性在图1-4中神经网络位于被建模系统的前面并与之串联网络的输入为系统的期望输出训练误差或者为期望输出与系统实际输出之差或者为与已建模神经网络正向模型输出之差其中神经网络正向模型可用前面方法得到正—逆建模有三种不同的实现途径1直接利用系统实际输出与期望输出之差作为网络逆模型的训练误差2利用神经网络正向模型的输出同期望输出之差作为网络逆模型的训练误差3利用系统的实际输出与期望输出之差作为训练误差神经网络正向模型作为误差梯度信息的反向传播的通道除了多层前馈网络可以用来进行控制系统建模外动态递归网络也提供了一种极具潜力的选择文献[1011]也对基于神经网络的建模方法进行了研究三模糊集同神经网络相结合的建模方法[12]模糊集同神经网络相结合的建模方法获得的模型可以分为两类一类可以称4 上海交通大学博士学位论文G1X1X1¢mGXiXi¢2X2X2¢...Y´GiXi¢Xi...Xn¢GnXnx图1-5神经模糊网络中的神经元图1-6神经模糊网络中的加权操作Fig.1-5TheneuronintheneuralFig.1-6Theweightoperationfuzzynetworkintheneuralfuzzynetworkm1x1x1¢m2x2x2¢...mmixi¢´xi...mnxn¢xn图1-7模糊神经网络中的神经元Fig1-7TheneuroninthefuzzyneuralnetworkFirstlayerSecondlayerThirdlayerFourthlayerFifthlayer图1-8基于Mamdani模型的模糊神经网络模型Fig.1-8ThefuzzyneuralnetworkmodelbasedontheMamdanimodel为神经模糊网络模型另一类可以称为模糊神经网络模型在神经模糊网络模型中5 上海交通大学博士学位论文可以采用真正意义上的模糊神经元这种神经元的输入和输出都是模糊量如图1-5所示图中Xi和Xi¢以及Y都是模糊量Gi表示加权操作即Gi(Xi)=Xi¢它可以看成是对Xi隶属函数的修正图1-6而Ä是累积算子将所有修正了的输入累积起来产生一个模糊输出这一过程可以很复杂模糊神经网络中的神经元的输入和输出都是非模糊量如图1-7所示图中xi和xi¢以及m都是非模糊量mi表示加权操作实际上mi可以看成是隶属函数在控制系统建模中模糊神经网络模型得到了广泛应用从本质上讲模糊神经网络模型是一种模糊推理的神经网络实现因而在建模应用中同Mamdani模型和[13]Sugeno模型T–S模型相对应模糊神经网络模型也可以分为两种第一种是基于Mamdani模型的模糊神经网络模型由图1-8可以看出该模型由五层神经元组成第一层为输入层第二层每个结点表示一个语言变量值它的作用是计算各输入分量属于各语言变量值模糊集合的隶属度函数第三层用来匹配模糊规则前件计算出每条规则的适用度第四层用来完成归一化计算第五层实现清晰化计算第二种是基于Sugeno模型T–S模型的模糊神经网络模型图1-9该网络由前件网络和后件网络两部分组成前件网络用来匹配模糊规则前件后件网络用来产生模糊规则后件前件网络由四层神经元组成它与图1-8的前四层的结构完全相同后件网络由r个结构相同的并列子网络组成每个子网络产生一个输出量子网络的第一层是输入层第二层计算每条规则的后件第三层计算系统的输出前件网络的输出用作后件网络第三层的连接权值应用这两种模糊神经网络模型对控制系统建模的过程就是利用已经取得的足够样本数据按照一定的学习算法对神经网络进行训练的过程相关具体的方法可以在文献[14-17]中找到1.3电弧焊接过程建模现状[2]如前所述电弧焊接过程涉及大量不确定因素如1焊接电弧形状电弧斑点运动等的无规律变化6 上海交通大学博士学位论文SecondlayerFirstlayerThirdlayerConsequentAntecedentnetworkFirstlayerSecondlayerThirdlayerFourthlayer图1-9基于Sugeno模型的模糊神经网络模型Fig.1-9ThefuzzyneuralnetworkmodelbasedontheSugenomodel2网络电压波动导电嘴接触状况等原因使焊接电流变化而引起的热输入变化3焊枪运动过程中因焊工手动操作或因运行机构稳定性引起的弧长变化焊缝对中变化及焊接速度变化等4因工件结构或夹具固定引起的工件局部导热状态的变化5送丝系统可能出现的焊丝矫直情况变化引起的送丝偏离送丝机构或导7 上海交通大学博士学位论文管阻力变化引起的送丝速度变化6焊接过程的焊接变形所引起的对缝间隙变化对缝错边变化电极与工件距离的变化等在上述诸多因素的作用下电弧焊接过程必然是非线性时变强耦合的复杂过程根据控制理论的研究对于这类复杂过程用经典的建模方法获取其精确数学模型的局限性是很大的对此模糊集理论的创始人Zadeh教授在1973年提出的[3]不相容原理中这样描述随着系统复杂性的增长我们对其特性做出精确而有意义的描述能力相应地降低直到达到一个阈值一旦超过它精确性和有意义性几乎成为两个互相排斥的特征近年来随着人工智能技术的发展研究人员正尝试用模糊集方法神经网络方法和两者相结合的方法对电弧焊接过程建模90年代以来国内外的学者和工程技术人员对电弧焊接过程的模糊集和神经网络建模方法做了大量研究取得了许多有意义的成果一电弧焊接过程的模糊集建模1996年美国Kentucky大学的R.Kovacevic和Y.M.Zhang在这方面做了深入[18]的研究建立了熔池正面几何参数同背面熔池宽度之间的Sugeno模糊模型并且在建模过程中模糊模型的参数是通过神经网络方法获得的因而所获得的模型又被称为神经模糊模型NeurofuzzyModel实验证明该模型可以具有很高的精度[19][20]国内的华中理工大学的王伟等人和大连铁道学院的李文等人也进行了电弧焊接过程的模糊建模研究二电弧焊接过程的神经网络建模关于电弧焊接过程的神经网络建模的研究相对较多1990年美国田纳西州Vanderbilt大学的K.Andersen和G.E.Cook等人建立了GTAWGasTungstenArcWelding焊接过程中焊缝几何形状同直接焊接参数DWPDirectWeldParameters间的反向传播BPBackPropagation网络模型并用实际焊接数据对所建立模型的性能进行了检验证明了该模型的精度不低于使用传统数学方法获得的模型的精[21]度用同样的原理和方法1995年G.E.Cook和R.J.Barnett等人对NASA的马8 上海交通大学博士学位论文歇尔空间飞行中心MarshallSpaceFlightCenter建设中使用的铝的变极性等离子电弧焊接VPPAWVariablePolarityPlasmaArcWelding过程进行了建模获得了熔池底部和顶部宽度的BP神经网络模型取得了很好的效果其BP网络为三[22]层结构4-10-21999加拿大的B.Chan等人对金属熔化极气体保护堆焊焊接过程建立了3层BP网络模型用来预测焊接尺寸并且认为所给出的BP神经[23]网络建模方法可以推广到其它焊接过程的建模2002年韩国的I.S.Kim等人对金属熔化极气体保护多道焊接过程建立了焊缝余高的BP网络预测模型并将所建立的模型同用回归分析方法获得的模型做了比较证明BP网络模型具有更好的性[24]能同年印度的D.S.Nagesh等人对建立了金属熔化极气体保护焊接过程的四层BP网络模型6-10-9-4用于预测焊缝余高焊缝正面宽度熔透深度以及熔透[25]面积此外日本的B.Z.Jin等人KenjiOhshima等人新加坡的LiDi等人也[26-28]对焊接过程的BP网络建模做了研究在电弧焊接过程的神经网络建模中多[29]层感知器MLPMulti-LayerPerceptrons模型以及小脑模型关联控制器CMAC[30]CerebellumModelArticulationController网络模型也有应用国内的科研人员也对电弧焊接过程的神经网络建模做了有意义的研究1994年华南理工大学的黄石生等人用BP网络建立了GTAW过程中正面熔宽背面熔宽同焊接参数间的关系[31]初步证明焊接过程的神经网络建模方法具有容错性和通用性强抗干扰等优点上海交通大学的陈善本等人对焊接过程的BP网建模进行了比较系统而深入的研究建立了多种焊接规范下焊接过程的静态动态模型取得了一系列的研究成果1996年陈善本吴林等人建立了GTAW堆焊焊接过程的四层BP网5-10-10-1[32]动态模型给出了焊接电流同熔池正面宽度间的关系同年陈善本等研究了GTAW过程的BP网的在线和离线建模相关问题给出焊接速度同正面熔宽间关系[33]的动态模型相关的研究在文献[35-38]中也可以找到2000年陈善本娄亚军等人给出了脉冲GTAW堆焊的正面熔长正面熔宽的BP网动态模型和背面熔宽的[39]BP网动态模型模型的结构分别如图1-10和1-11所示同年陈善本赵冬斌等人又对脉冲GTAW平板对接焊过程进行了建模得到了熔池背面尺寸及形状的[40]BP网动态模型其结构如图1-12所示相关的研究在文献[4142]中也可以找9 上海交通大学博士学位论文图1-10正面熔宽和熔长BP网络模型Fig.1-10TheBPnetworkmodelofthewidthandlengthofthetopsideoftheweldpool图1-11背面熔宽的BP网络模型Fig.1-11TheBPnetworkmodelofthewidthofthebacksideoftheweldpool10 上海交通大学博士学位论文IpPeakvalueofpulsecurrentdDutycycleofpulsedurationVwWeldingcurrentUpArcvoltageSfmidAreaparameterofthetopsideoftheweldpoolLfmaxMaximumhalf-lengthofthetopsideoftheweldpoolWfiShapeparameterofthetopsideoftheweldpoolSbAreaparameterofthebacksideoftheweldpoolWbmaxMaximumwidthofthebacksideoftheweldpoolLbmaxMaximumhalf-lengthofthebacksideoftheweldpool图1-12背面熔池宽度长度和面积的BP网络模型Fig.1-12TheBPnetworkmodelofthewidth,lengthandareaofthebacksideoftheweldpool到哈尔滨工业大学的赵冬斌张广军和张勇等人都对不同工艺条件下的脉冲GTAW熔池动态过程进行了有效的BP网络建模获得了同实际过程符合较好的过[434445]程的静态和动态模型哈尔滨工业大学的刘中华王其隆等人则用BP网络[46]对等离子弧焊过程进行了建模特别指出台湾大学的Y.S.Tarng等人用重复传播网络CPNCounterPropagationNetwork对GTAW过程进行了建模这种网络为三层结构隐层为竟争层也可以称为Kohonen层采用无监督学习规则进行学习输出层称为Grossberg层与隐层全互连可用Grossberg规则或Widrow-Hoff11 上海交通大学博士学位论文[47]规则进行学习S.C.Juang等人通过实验比较了CPN同BP网络的性能认为两种网络都可以对GTAW过程有效建模CPN的学习能力略强而BP网络的归纳能[48]力略强模糊集建模方法存在较多的主观因素需要足够的先验知识虽然已经有很多方法来减少主观因素的影响其中包括神经网络方法但这些方法都没从根本上排除主观因素的影响RadovanKovacevic和YuM.Zhang的研究工作中仍然要首先根据经验假设模糊模型的基本结构已知然后在此基础上进行模糊参数的神经网络辨识模糊建模的另外一个不足之处在于随着语言变量个数以及每个语言变量取值个数的增加模糊模型的规模有可能变得无法控制导致规则爆炸这一点使得所建立的电弧焊接过程模型的输入和输出不可能太多事实上电弧焊接过程又是一个涉及多变量耦合的复杂过程所以这一点限制了模糊建模方法在电弧焊接过程建模中的应用神经网络建模方法由于神经网络本身是一个黑箱所以获得的模型物理意义不明确难以理解这导致了对模型的维护和修改的困难再有神经网络的收敛速度在某些情况下也是难以接受的此外神经网络的结构及参数的确定也大多依赖经验以前述的电弧焊接过程的BP神经网络建模研究工作为例其神经网络模型的结构或者为三层或者为四层究竟哪种更好是无法确定的隐层结点的个数在已有工作中多是通过试错实验确定的虽然可以得到一些经验公式来确定隐层结点个数但是无法从理论上加以证明另外一个更棘手的问题是神经网络训练所需样本数据的获得众所周知一组理想的样本数据对模型的性能是具有极大影响的但是如何得到这样的数据怎么判断所得数据是理想的都是现阶段无法解答的真正用模糊集和神经网络相结合的方法对电弧焊接过程建模的文献尚未查到但是可以预见上述问题仍将客观存在这促使我们寻找新的建模方法来对电弧焊接过程进行有效的建模RS理论的提出为我们提供了契机使得获取电弧焊接过程的知识模型成为可能12 上海交通大学博士学位论文1.4粗糙集理论及应用研究现状1.4.1粗糙集理论研究现状[49]粗糙集RSRoughSet理论是在1982年由波兰学者Z.Pawlak提出的能够有效地分析和处理数据的含糊性vagueness不精确性imprecision和不确定性uncertainty特别适合于进行决策分析经历了二十多年的迅速发展RS理论不断完善关于RS理论本身的研究非常多可以查到的文献数以千计这里不能一一枚举仅对重要的研究方向加以简单综述1颗粒计算RS理论的数学基础是等价关系等价关系将论域中的每个元素都同唯一的等价类对应起来如果将等价关系看成是关于论域的知识那么等价类可以被认为是知识的基本组块elementarybuildingblock或称为颗粒granule于是对论域中单独元素的考察就可以转换为对该元素所属组块的考察这样做的目的在于忽略不必要的细节以抓住事物的本质特征1998年RS理论的创始人Z.Pawlak指出RS理论的基础同颗粒性有着本质的联系并且讨论了RS理论中的一些基本概念同颗[50]粒性的联系同年波兰华沙理工大学的L.Polkowski和A.Skowron进一步在[51]RS框架内从理论角度对颗粒性进行了形式化并且以此为基础提出一个解决自适应决策算法的合成问题的方法相关的研究也可以在文献[52]中找到RS理论所反映的知识的颗粒性可以进一步推广2000年波兰波兹南理工大学的R.Slowinski和D.Vanderpooten以相似关系similarityrelation为基础即在等价关系不可分辨关系的三个条件自反性对称性传递性中只保留自反性得到了新的更概括的粗糙集的定义相似关系可以更准确地对含糊性ambiguity进行刻划以[53]等价关系为基础的粗糙集是以相似关系为基础的粗糙集的特例此外两人也对不同基础上的粗糙近似进行了比较1999年加拿大Regina大学的Y.Y.Yao用类似的方法将粗糙集中知识的颗粒性推广到邻域系统neighborhoodsystem中知识[54][55]的颗粒性同年Y.Y.Yao给出了不同的颗粒性同近似推理的关系现在颗粒计算granularcomputing已经成为一个新的研究热点这是RS理论深入发展的13 上海交通大学博士学位论文必然结果但是国内在这方面的研究成果尚未见到2粗糙集理论和模糊集理论RS理论同FS理论都是经典集合论的扩展因而对两者关系的研究是RS理论研究的一个重要方向1992年法国PaulSabatier大学的D.Dubois和H.Prade探讨了将RS理论同FS理论结合起来的不同方法给出了构造粗糙模糊集rough-fuzzyset模型和模糊粗糙集(fuzzy-roughset)模型的途径并对相关的性质进行了证明两种模型的不同在于前者是一种特殊的模糊集可以通过模糊集的粗糙化得到后[56]者是一种特殊的粗糙集通过粗糙集的模糊化得到1996年印度的M.Banerjee[57]和S.K.Pal给出了模糊集的一个粗糙测度从而将模糊集同粗糙集联系起来1998年加拿大的Y.Y.Yao分别用面向集合Set-oriented的观点和面向算子Operator-oriented的观点对RS理论和FS理论进行了比较在前一种观点下[58]RS理论同FS理论非常相似但在后一种观点下两种理论的区别较为显著同[59]年土耳其的D.Coker证明了模糊粗糙集同L-模糊集的相似性1999年美国[60]Creighton大学的J.N.Mordeson给出了粗糙模糊集理论中一些空间的代数性质2000年印度的K.Chakrabarty等人给出了一个粗糙集的模糊测度来达到粗糙集[61]模糊化的目的2002年波兰的A.M.Radzikowska和比利时的E.E.Kerre进一[62]步给出了粗糙集模糊化的更一般的方法同年日本的R.Intan和M.Mukaidono给出另外一种获得模糊粗糙集的方法即用弱模糊近似关系来代替等价关系推广[63]了粗糙近似及隶属函数的定义在国内也有关于RS理论和FS理论研究的成果2003年西安交通大学的吴伟志等人给出了新的上下近似算子验证了模糊关系同模糊粗糙近似算子的关系并用不同的公理集刻划了不同类的模糊粗糙近似算子[64]3粗糙集理论和神经网络RS理论和神经网络在功能上具有互补性因而对两者的研究是RS理论研究的另一个重要方向1995年波兰波兹南理工大学的J.Jelonek等人将粗糙集方法作为神经网络的数据预处理器对神经网络的训练样本数据进行约简属性约简和属性值域约简减小网络规模实验结果表明这样做可以使网络的收敛速度提高14 上海交通大学博士学位论文[65]4.72倍而分类误差的增长不超过11.06%这种方式是RS理论和神经网络相结合的最直接而且有效的方式1998年澳大利亚莫纳什大学的I.Jagielska2000年[6667]匈牙利的I.Bertalan和P.Kadar也分别在这方面做了研究1995年德国的R.Yasdi进一步给出了RS理论同神经网络相结合的另一种方式即先用粗糙集方法获得规则集并计算其中每条规则的依赖因子根据依赖因子设置网络神经元的联[68]结权值然后再用神经网络对规则集进行优化1999年美国韦恩州立大学的A.Lazar和L.K.Sethi给出了神经网络中知识的白化方法即用RS理论直接对神经网络的权值矩阵进行处理从而获得决策规则所获得的规则的理论意义虽然仍不明确但是提供了神经网络模型向基于规则的模型的转换方法进一步增强了神经[69]网络同RS理论的结合国内在RS理论同神经网络相结合的研究中也取得了丰硕的成果1998年华东船舶工业学院的王士同等人用神经网络对用粗糙集方法获[70]得的规则集进行了优化1999年陈遵德用自组织特征映射神经SOFMSelf-OrganizingfeatureMap网络对决策表中连续属性进行离散化然后进行基于[71]RS理论的处理用神经网络的聚类能力完成连续属性的离散化是RS理论同神经网络相结合的重要方式同年清华大学的李永敏等人给出了粗糙神经网络的构造方法即用神经网络实现基于RS理论的推理同基于Mamdani模型的模糊神经网络相似该粗糙神经网络分为四层第一层是输入层第二层是隶属函数层第三[72]层是推理层第四层是清晰化层2001年南京航空航天大学的许志兴等人进一[73]步证明了上述粗糙神经网络是全局逼近器同年清华大学的王玮和蔡连红对粗糙神经网络进行了更深入的研究定义了粗糙神经元以及两个粗糙神经元间的三种联结方式给出了两种粗糙神经网络模型一种只有输入层是粗糙神经元另一[74]种的输入层和隐层都是粗糙神经元2002年华中科技大学的陆光辉和肖人彬也[75]将粗糙集方法用于神经网络的数据预处理4粗糙集理论模糊集理论和神经网络的结合1997年和1998年印度的M.Banerjee等人讨论了RST同模糊神经网络相结合的知识嵌入knowledgeencoding方法该方法根据RS理论获取的知识设置模[7677]糊神经网络的初始权值可以较好的改进模糊神经网络的性能1998年印15 上海交通大学博士学位论文度的M.Sarkar和B.Yegnanarayana讨论了在径向基函数神经网络设计中用模糊粗糙[78]隶属函数确定径向基函数的中心的方法同年两人又通过模糊粗糙集方法确定[79]信息源的每个子集的重要程度进而对模块化的神经网络的结构加以改进1999年韩国的J.H.Yon等人用RS方法对模糊规则进行约简从而达到了优化模糊神[80]经网络的目的在国内2000年华东船舶工业学院的於东军和王士同2001年湛江海洋大学的刘璨等人研究了直接用RS理论获得决策规则然后构建模糊神[8182]经网络的方法同年西安交通大学的杜海峰等人用RS理论对模糊神经网络[83]的训练样本数据进行了预处理改进了网络性能5其它粗糙集理论研究[84-90]对RS理论中约简算法的研究也是RS理论研究的另一个重要内容在第四部分将做详细的综述此外文献[919293]对RS理论同概率统计理论的融合做了探讨文献[94-99]讨论了RS理论的公理化问题及其它一些逻辑问题文献[100101]讨论了RS理论中知识粗糙性同信息熵的关系综上所述关于RS理论的研究已经日渐完善这为RS理论的应用打下了坚实的基础1.4.2粗糙集理论应用现状RS理论的应用领域非常广泛主要包括1模式识别2000年韩国的D.Kim和S.Y.Bang采用容忍粗糙集tolerantroughset模型结合遗传算法对手写数字进行了识别仿真结果表明识别的效果略好于BP网络[102]的识别效果但速度要比BP网络快近2个数量级1997年印度的M.Sarkar和B.Yegnanarayana采用粗糙—模糊集模型在桥牌的叫牌过程中对手中不同牌[103]的组合进行了分类识别1998年两人采用粗糙集理论同模糊集理论和神经网[78]络结合的方法对元音进行了分类识别文献[104105]也在这方面做了积极的工作2医疗诊断及分析2000年日本的S.Tsumoto定义了两个概率测度probabilisticmeasure精确16 上海交通大学博士学位论文度accuracy和覆盖度(coverage)获得了由肯定规则positiverules和否定规则[106](negativerules)构成的推理模型用于从医学临床数据库中发现知识同年印度的P.MitraS.Mitra和S.K.Pal给出了基于RS理论和其它软计算方法相结合的新方法并应用于宫颈癌病情的分级应用结果表明同传统的多层感知器相比新[107]方法改进了分类效果减小了网络规模而且缩短了训练时间1999年日本的[108]S.Tsumoto使用RS理论对特定疾病的并发症进行了诊断相关的应用还可以在文献[109-114]中找到3图像处理2000年印度的A.Mohabey和A.K.Ray将RS理论成功应用于彩色图像的分[115]割国内在这方面的研究可以在文献[116]中找到4质量和故障诊断2000年重庆大学的孙颖楷等人将RS理论同神经网络相结合建立了板坯缺[117]陷知识库并应用于钢厂连铸坯表面缺陷类型的诊断及预测文献[118-120]也介绍了类似的应用5数据挖掘与知识发现1997年西班牙的M.C.Fernandez-Baizan使用改进的粗糙集数据挖掘系统从[121]相关的关系数据库中获得了不同国家的社会经济指标间的关系1998年中国科学院北京自动化研究所的王珏等人用RS理论对UCI机器学习数据库中的大部分数据进行了处理处理结果表明RS理论可以从大量繁杂的数据中获得有意义的[88]知识相关的研究在文献[122]中也可以找到6控制领域控制领域是RS理论应用极具潜力的领域1995年波兰的E.Czogala等人将RS理论同模糊集理论结合起来应用于小车—倒立摆系统这一经典控制问题建立了一个粗糙模糊控制器控制效果比模糊控制器略差但其控制模型极为简洁[123]仅含九条规则1997年日本的T.Munakata对粗糙控制RoughControl进行了展望指出了实际应用中粗糙控制潜力之所在并通过对模糊控制过程的分析给[124]出了粗糙控制的原则此外他还对粗糙控制进行了分类17 上海交通大学博士学位论文单纯的粗糙控制粗糙模糊系统模糊粗糙系统混合系统粗糙神经网络系统神经网络粗糙系统RS理论的创始人Z.Pawlak本人也对粗糙控制进行了深入研究1997年他给出了粗糙实函数的定义而粗糙实函数是粗糙控制器设计和分析的基础他指出粗糙控制的前提是假定控制过程是可以观测的有关控制过程的数据被用来产生控制算法进一步他认为控制算法的获得和优化都可以通过RS理论进行而且RS理论也很适合于这类任务同时他也认为RST可以对通过模糊集理论获得的控制算[125]法进行简化此外1995年加拿大的M.Arima给出了一个模糊逻辑同粗糙集[126]相结合的控制器用于调节室内的温度和湿度1998年加拿大的J.F.Peters等人提出了一个自适应的模糊粗糙控制器的设计方法并应用于小型卫星倾角的控[127]制1996年波兰的A.Mrozek等人讨论了同粗糙控制器的软件硬件相关的[128]问题可以预见粗糙控制将同模糊控制和神经控制一样成为控制领域中的重要分支特别地RS理论在焊接过程控制中的应用研究刚刚起步相关的研究工作还[129130]很少1999年大连铁道学院的李文给出了模糊系统的知识模型的概念将RS理论的核心概念推广到模糊系统的知识模型中提出了一种新的基于知识模型[129]的辨识方法应用于TIG焊接过程的建模中用所建立的模型进行熔池背面宽度预测的仿真实验表明基于知识模型的模糊系统辨识方法在数据不精确不完整和不确定的情况下能够有效地提出复杂过程的模糊模型从严格意义上讲这些研究工作还不属于粗糙控制的范畴而是模糊控制的范畴它仅仅是利用RS理论进行模糊系统的辨识但是这些工作在很大程度上证明了RS理论在焊接过程控制领域中的应用潜力18 上海交通大学博士学位论文7其它领域将RS理论应用于专家系统也是一个很活跃的研究方向文献[131132]中讨论了RS理论同神经网络相结合在专家系统中的应用问题此外文献[133]将RS理论用于定理证明的可视化文献[134]将粗糙集理论同模糊集理论相结合建立了城市水处理的监控系统文献[135]将粗糙集理论同模糊集理论起来对高压电缆除雪系统的风险进行了分析文献[136137]分别采用RS理论进行了软件分析文献[138]使用扩展的粗糙集模型获得了北美中等城市供水系统的需求关系模型综上所述RS理论广泛的应用于各种领域一方面证明了RS理论的理论优势另一方面这些应用结果及经验可以在进一步的工作中加以充分借鉴促进RS理论的更深入的应用1.5课题的意义电弧焊接过程是典型的复杂过程涉及大量不确定因素用经典建模方法难以有效获得其精确数学模型而焊接工人却可以熟练操纵焊接过程这启发研究人员用智能方法主要包括模糊集方法和神经网络方法来对焊接过程进行建模从而获得过程的知识模型但是如前所述这样做仍不能完全满足实际需要有必要对电弧焊接过程的建模方法做进一步探讨将RS理论应用于电弧焊接动态过程的建模对建模过程中的理论方法和实际问题进行研究的意义如下1有助于认识电弧焊接动态过程的规律获取焊工的操作经验知识从而实现电弧焊接过程的自动化和智能化2建模方法可以推广到其它涉及大量不确定因素的复杂过程促进系统建模理论的发展3完善RS理论研究拓展RS理论的应用领域1.6本文的研究内容本文的研究内容以电弧焊接动态过程的知识建模为主题针对电弧焊接动态过程的复杂性研究复杂过程的粗糙集知识建模方法有效获取电弧焊接动态过程及19 上海交通大学博士学位论文控制的知识模型具体的研究内容可以分为三部分1粗糙集知识建模方法的框架即建模步骤研究在其它领域中关于RS理论应用的具体方法已经有所研究但是电弧焊接动态过程有自身的特点因而RS理论在电弧焊接动态过程建模中的具体方法仍需进一步研究在这部分中主要研究建模的主要步骤以及在每一步骤中需要解决的问题采用的方法并对其中一些问题进行必要的形式化2粗糙集知识建模方法中的关键算法研究粗糙集知识建模方法中包括三个主要的步骤即条件属性约简条件属性值约简及规则约简这三种约简在本质上具有一致性其算法具有通用性在这部分研究中将从集合论的角度对三种约简的等价性进行理论研究给出相关理论证明同时对已有约简算法进行简要介绍给出新的约简算法并对算法的特性加以证明这一部分是本文的重点研究内容3粗糙集知识建模方法的实验验证以基于视觉传感的焊接工艺实验系统为基础一方面用粗糙集知识建模方法对铝合金脉冲TIG焊接动态过程进行建模获取其知识模型以验证粗糙集知识建模方法对焊接动态过程建模的可行性和有效性另一方面利用已有的PID和最小方差自适应控制器数据用粗糙集知识建模方法获得相应控制器的粗糙集知识模型描述以验证粗糙集知识建模方法建立焊接动态过程控制模型的可行性和有效性1.7论文结构本文结构如下第一章首先介绍了焊接过程建模对焊接过程自动化和智能化的重要性强调了电弧焊接过程的复杂性指出了经典建模方法的局限给出了模糊集和神经网络建模方法的一般原理并对电弧焊接过程的模糊集和神经网络建模情况进行了介绍分析了其中的不足引出了对电弧焊接过程建模方法进一步深入研究的必要性然后对RS理论和应用研究现状进行了介绍阐明了用粗糙集方法对电弧焊接动态过程建模的可行性最后明确了课题的意义本文的研究内容和论文结构20 上海交通大学博士学位论文第二章首先粗糙集知识建模方法的理论基础即粗糙集理论进行了介绍明确了粗糙集理论的基本思想和与本文相关的概念然后提出了粗糙集知识建模方法中知识模型的定义阐述了粗糙集知识建模方法的主要步骤并分别进行了论述第三章首先从集合论的角度证明了条件属性约简条件属性值约简以及规则约简的同集合极小覆盖的有条件等价性然后对已有条件属性约简算法进行了比较分析提出了新的条件属性约简算法并对算法的性质进行了理论证明在此基础上构造了条件属性值约简以及规则约简算法第四章在铝合金脉冲TIG焊接过程实验的硬件软件系统以及视觉传感系统熔池图像获取和处理方法介绍的基础上给出了铝合金脉冲TIG焊接动态过程的知识建模实验结果及分析证明了粗糙集知识建模方法对焊接动态过程建模的有效性第五章利用已有的PID控制器和最小方差自适应控制器的数据用粗糙集知识建模方法获得了相应控制器的粗糙集知识模型描述证明了粗糙集知识建模方法可以有效的获取焊接动态过程的控制模型第六章给出本文的结论参考文献1.陈善本等焊接过程现代控制技术哈尔滨哈尔滨工业大学出版社20012.王其隆弧焊过程质量实时传感与控制北京机械工业出版社20003.ZadehL.A.,Outlineofanewapproachtotheanalysisofcomplexsystemsanddecisionprocesses,IEEETransactiononSystems,ManandCybernetics,1973,3(1),28-444.李少远席裕庚陈增强袁著祉智能控制的新进展I控制与决策20001511-55.秦勇贾利民张锡第吴连伟多变量模糊系统建模与控制理论计算机仿真199916315-1821 上海交通大学博士学位论文6.张金明李人厚模糊控制的系统化设计和稳定性分析自动化学报1999254493-4977.李少远王群仙李焕芝陈增强袁著祉Sugeno模糊模型的辨识与控制自动化学报1999254487-4928.王宏伟马广富王子才模糊辨识理论与应用研究系统仿真学报200012287-909.孙增圻等智能控制理论与技术北京清华大学出版社199710.李少远席裕庚陈增强袁著祉智能控制的新进展II控制与决策2000152136-14011.李士勇模糊控制神经控制和智能控制论第二版哈尔滨哈尔滨工业大学出版社199812.王士同模糊系统模糊神经网络及应用程序设计上海上海科学技术文献出版社199813.孙增圻模糊神经网络及其在系统建模与控制中的应用南京化工大学学报20002241-614.於东军王士同新模糊神经网络模型及其建模应用研究华东船舶工业学院学报199812222-2815.马广富王宏伟王司基于模糊神经网络的系统模糊建模方法哈尔滨工业大学学报199931579-8516.何磊戴冠中基于模糊神经网络的模糊辨识方法及其应用研究西北工业大学学报1998162292-29617.何谦李宏光非线性系统建模的复合型模糊神经网研究北京化工大学学报200027467-7118.KovacevicR.andZhangY.M.,On-linemeasurementofweldfusionstateusingweldpoolimageandneurofuzzymodel,IEEEInternationalSymposiumonIntelligentControl-Proceedings,1996,307-31219.王伟朱六妹焊接电弧电压模糊模型的相关辨识电工技术学报19981322 上海交通大学博士学位论文159-6320.李文孙辉陈字刚模糊系统辨识方法在TIG焊过程建模中的应用控制理论与应用1998206111-11421.AndersenK.,CookG.E.,KarsaiG.andRamaswamyK.,Artificialneuralnetworksappliedtoarcweldingprocessmodelingandcontrol,1990,IEEETransactionsonIndustryApplications,26(5),824-83022.CookG.E.,BarnettR.J.,AndersenK.andStraussA.M.,Weldmodelingandcontrolusingartificialneuralnetworks,IEEETransactionsonIndustryApplications,1995,31(6),1484-149123.ChanB.,PaceyJ.andBibbyM.,Modellinggasmetalarcweldgeometryusingartificialneuralnetworktechno,CanadianMetallurgicalQuarterly,1999,38(1),43-5124.KimI.S.etc.,Astudyonpredictionofbeadheightinroboticarcweldingusinganeuralnetwork,JournalofMaterialsProcessingTechnology,2002,130-131,229-23425.NageshD.S.andDattaG.L.,Predictionofweldbeadgeometryandpenetrationinshieldedmetal-arcweldingusingartificialneuralnetworks,JournalofMaterialsProcessingTechnology,2002,123(2),303-31226.JinB.Z.,LiuW.H.andOhshimaK.J.,ControlofweldpoolwidthandcoolingrateincircumferentialGTAweldingofpipebyusingneuralnetworkmodel,InternationalIEEE/IASConferenceonIndustrialAutomationandControl:EmergingTechnologies,Proceedings,1995,41-4627.OhshimaK.J.etal.,Sensorfusionusingneuralnetworkintheroboticwelding,ConferenceRecord-IASAnnualMeeting(IEEEIndustryApplicationsSociety),1995,1764-176928.LiDi,SrikanthanT.,ChandelR.S.andKatsunoriI.,Neural-network-basedself-organizedfuzzylogiccontrolforarcwelding,EngineeringApplicationsof23 上海交通大学博士学位论文ArtificialIntelligence,2001,14,115-12429.LiP.,FangM.T.C.andLucasJ.,Modellingofsubmergedarcweldbeadsusingself-adaptiveoffsetneutralnetworks,JournalofMaterialsProcessingTechnology,1997,71(2),288-29830.LinR.H.andFischerG.W.,Anon-linearcweldingqualitymonitorandprocesscontrolsystem,InternationalIEEE/IASConferenceonIndustrialAutomationandControl:EmergingTechnologies,Proceedings,1995,22-2931.黄石生李迪宋永伦焊接过程的神经网络建模及控制研究机械工程学报199430324-3032.ChenS.B.,WuL.andWangQ.L.,Self-learningfuzzyneuralnetworksforcontrolofthearcweldingprocess,IEEEInternationalConferenceonNeuralNetworks-ConferenceProceedings,1996,1209-121433.陈善本吴林张铨张福恩具有时滞的不确性系统神经网络模糊自学习控制控制理论与应用1996133347-35534.ChenS.B.,WuL.andWangQ.L.,Self-learningfuzzyneuralnetworksforcontrolofuncertainsystemswithtimedelays,IEEETransactionsonSystems,Man,andCybernetics,PartB:Cybernetics,1997,27(1),142-14835.陈善本吴林李友善不确定对象的自学习模糊神经网络控制方法模糊系统与数学199711263-6936.陈善本吴林王其隆刘玉池脉冲TIG焊熔宽动态过程的自学习模糊神经网络控制机械工程学报199733470-7637.ChenS.B.,WuL.,WangQ.L.andLiuY.C.,Self-learningfuzzyneuralnetworksandcomputervisionforcontrolofpulsedGTAW,WeldingJournal,1997,76(5),201s-209s38.陈善本吴林王其隆刘玉池脉冲TIG焊熔宽动态过程模糊推理—神经网络控制方法焊接学报1997183159-16539.ChenS.B.,LouY.J.,WuL.andZhaoD.B.,Intelligentmethodologyforsensing,24 上海交通大学博士学位论文modelingandcontrolofpulsedGTAW:Part1—bead-on-platewelding,WeldingJournal,2000,79(6),151s-163s40.ChenS.B.,ZhaoD.B.,WuL.andLouY.J.,Intelligentmethodologyforsensing,modelingandcontrolofpulsedGTAW:Part2—buttjointwelding,WeldingJournal,2000,79(6),164s-174s41.陈善本娄亚军赵冬斌吴林脉冲GTAW熔池动态过程模糊神经网络建模与控制200228174-8242.ChenS.B.,ZhangY.,QiuT.andTaoT.,Roboticweldingsystemswithvision-sensingandself-learningneuroncontrolofarcweldingdynamicprocess,JournalofIntelligentandRoboticSystems,2003,36,191-20843.ZhaoD.B.,ChenS.B.,WuL.,DaiM.andChenQ.,IntelligentcontrolfortheshapeoftheweldpoolinpulsedGTAWwithfillermetal,WeldingJournal,2001,80(11),253s-260s44.ZhangG.J.,ChenS.B.andLiuX.D.,PredictingthebacksidewidthofweldpoolduringpulsedGTAWprocessbasedonaneuralnetworkmode,ProceedingsofSPIE-TheInternationalSocietyforOpticalEngineering,2001,4565,131-13745.张勇陈善本邱涛吴林赵冬斌焊接柔性加工单元中熔池的实时控制焊接学报20022341-546.LiuZ.H.,WangQ.L.andZhangB.,Processcontrolbasedondouble-sideimagesensingofthekeyholeinVPPAwelding,JournalofMaterialsProcessingTechnology,2001,115(3),373-37947.TarngY.S.,WuJ.L.,YenS.S.andJuangS.C.,Intelligentmodelingandoptimizationofthegastungstenarcwelding,JournalofIntelligentManufacturing,1999,10,73-7948.JuangS.C.,TarngY.S.andLiiH.R.,Acomparisonbetweentheback-propagationandcounter-propagationnetworksinthemodelingoftheTIGweldingprocess,1998,75,54-6225 上海交通大学博士学位论文49.PawlakZ.,Roughsets.InternationalJournalofInformationandComputerScience,1982,11(5),341-35650.PawlakZ.,Granularityofknowledge,indiscernibilityandroughsets,ProceedingsofIEEEInternationalConferenceonComputationalIntelligence,1998,2,933-93851.PolkowskiL.andSkowronA.,Towardsadaptivecalculusofgranules,ProceedingsofIEEEInternationalConferenceonComputationalIntelligence,1998,1,111-11652.PolkowskiL.andSkowronA.,Logicalcalculiofrough-setgranulesinproblemsofapproximatesynthesisindistributedsystems.ProceedingsofThirdInternationalConferenceonComputationalIntelligenceandMultimediaApplications,1999,223-22753.SlowinskiR.andVanderpootenD.,Ageneralizeddefinitionofroughapproximationsbasedonsimilarity,IEEETransactionsonKnowledgeandDataEngineering,2000,12(2),331-33654.YaoY.Y.,Roughsets,neighborhoodsystemsandgranularcomputing,ProceedignsofIEEECanadianConferenceonElectricalandComputerEngineering,1999,3,1553-155855.YaoY.Y.,Stratifiedroughsetsandgranularcomputing.Proceedingsofthe18thInternationalConferenceoftheNorthAmericanonFuzzyInformation,1999,800-80456.DuboisD.andPradeH.,Puttingroughsetsandfuzzysetstogether.in:IntelligentDecisionSupport-HandbookofApplicationsandAdvancesoftheRoughSetsTheory,KluwerAcademicPublisher,1992,203-23257.BanerjeeM.andPalS.K.,Roughnessofafuzzyset,InformationSciences,1996,93(3-4),235-24658.YaoY.Y.,Comparativestudyoffuzzysetsandroughsets,InformationSciences,1998,109(1-4),227-24259.CokerD.,FuzzyroughsetsareintuitionisticL-fuzzysets,FuzzySetsandSystems,26 上海交通大学博士学位论文1998,96(3),381-38360.MordesonJ.N.,Algebraicpropertiesofspacesinroughfuzzysettheory,AnnualConferenceoftheNorthAmericanFuzzyInformationProcessingSociety-NAFIPS,1999,56-5961.ChakrabartyK.,BiswasR.andNandaS.,Fuzzinessinroughsets,FuzzySetsandSystems,2000,110,247-25162.RadzikowskaA.M.andKerreE.E.,Acomparativestudyoffuzzyroughsets,FuzzySetsandSystems,2002,126,137-15563.IntanR.andMukaidonoM.,Generalizedfuzzyroughsetsbyconditionalprobabilityrelations,InternationalJournalofPatternRecognitionandArtificialIntelligence,2002,16(7),865-88164.WuW.Z.,MiJ.S.andZhangW.X.,Generalizedfuzzyroughsets,InformationSciences,2003,151,263-28265.JelonekJ.,KrawiecK.andSlowinskiR.,Roughsetreductionofattributesandtheirdomainsforneuralnetworks,ComputationalIntelligence,1995,11(2),339-34766.JagielskaI.,Hybridroughsets/neuralnetworkapproachtothedevelopmentofaDecisionSupportsystem,IEEEInternationalConferenceonNeuralNetworks-ConferenceProceedings,1998,1,24-2867.BertalanI.andKadarP.,ApplicationsofroughsettheoryfordeterminingthesignificantinputsofaANN,ProceedingsoftheMediterraneanElectrotechnicalConference,2000,2,582-58568.YasdiR.,Combiningroughsetslearning-andneurallearning-methodtodealwithuncertainandimpreciseinformation,Neurocomputing,1995,7(1),61-8469.LazarA.andSethiL.K.,Decisionruleextractionfromtrainedneuralnetworksusingroughsets,IntelligentEngineeringSystemsThroughArtificialNeuralNetworks,1999,9,493-49870.WangS.T.,ScottE.andGamermannA.,Extractrulesbyusingroughsetand27 上海交通大学博士学位论文knowledge-basedNN,JournalofComputerScienceandTechnology,1998,13(3),279-28471.陈遵德Roughset神经网络智能系统及其应用模式识别与人工智能19991211-572.李永敏朱善君陈湘晖韩曾晋孙增圻根据粗糙集理论进行BP网络设计的研究1999462-6973.许志兴丁运光陆金桂一种基于粗糙集理论的粗糙神经网络构造方法南京航空航天大学学报2001334355-35974.王玮蔡连红基于粗集理论的神经网络计算机工程200127565-6775.陆光辉肖人彬基于粗集理论和神经网络的集成化数据挖掘方法研究小型微型计算机系统2002235552-55776.BanerjeeM.,MitraS.andPalS.K.,Knowledge-basedfuzzyMLPwithroughsets,ProceedingsofInternationalConferenceonNeuralNetworks,1997,1,499-50477.BanerjeeM.,MitraS.andPalS.K.,RoughfuzzyMLP:knowledgeencodingandclassification,IEEETransactionsonNeuralNetworks,1998,9(6),1203-121678.SarkarM.andYegnanarayanaB.,Fuzzy-roughneuralnetworksforvowelclassification,ProceedingsoftheIEEEInternationalConferenceonSystems,ManandCybernetics,1998,5,4160-416579.SarkarM.andYegnanarayanaB.,Applicationoffuzzy-roughsetsinmodularneuralnetworks,IEEEInternationalConferenceonNeuralNetworks-ConferenceProceedings,1998,1,741-74680.YonJ.H.,YangS.M.andJeonH.T.,Structureoptimizationoffuzzy-neuralnetworkusingroughsettheory,IEEEInternationalConferenceonFuzzySystems,1999,3,1666-167081.於东军王士同基于粗糙集的模糊神经网络建模研究华东船舶工业学院学报20001431-682.刘璨陈统坚彭永红姚锡凡基于粗糙集理论的模糊神经网络建模方法研28 上海交通大学博士学位论文究中国机械工程200112111257-125983.杜海峰王孙安丁国峰基于粗糙集与模糊神经网络的多级压缩机诊断西安交通大学学报2001359940-94484.HuX.H.andCerconeN.,Miningknowledgerulesfromdatabases:aroughsetapproach,ProceedingsoftheTwelfthInternationalConferenceonDataEngineering,1996,96-10585.HuX.H.andCerconeN.,Learningmaximalgeneralizeddecisionrulesviadiscretization,generalizationandroughsetfeatureselection,ProceddingsoftheNinthIEEEInternationalConferenceonToolswithArtificialIntelligence,1997,548-55686.MiaoD.Q.andWangJ.,Information-basedalgorithmforreductionofKnowledge,Proceedingsofthe1997IEEEInternationalConferenceonIntelligentProcessingSystems,1997,2,1155-115887.ShaoJ.,Findingreductswithuserspecifiedcriteria,ProceedingsoftheEighthInternationalWorkshoponDatabaseandExpertSystemsApplications,1997,352-35788.王珏等基于RoughSet理论的数据浓缩计算机学报1998215390-34089.WangJ.andMiaoD.Q.,Analysisonattributereductionstrategiesofroughset,JournalofComputerScienceandTechnology,1998,13(2),189-19390.BautistaR.etc.,Anefficientimplementationtocalculaterelativecoreandreducts,thProceedingsofthe18InternationalConferenceoftheNorthAmericanonFuzzyInformation,1999,791-79491.StraussO.,Filteringandfusingcompassandgyrometerdatausingguessfilter,ProceedingsoftheSixthIEEEInternationalConferenceonFuzzySystems,1997,3,1593-159992.YaoY.Y.andWongS.K.M.,Generalizedprobabilisticroughsetmodels,Proceedingsofthe1996AsianFuzzySystemsSymposium,1996,158-16329 上海交通大学博士学位论文93.NingZ.etc.,Anincremental,probabilisticroughsetapproachtorulediscovery,Proceedingsofthe1998IEEEInternationalConferenceonFuzzySystemsProceedings,1998,933-93894.LinT.Y.etc.,Modelsforfirstorderroughlogicapplicationstodatamining,Proceedingsofthe1996AsianFuzzySystemsSymposium,1996,152-15795.TaniguchiH.etc.,Interactivelogicalpropertiesinmultimodelsemanticsfordataanalysisbasedonattributevaluesandtime,ProceedingsofIEEEInternationalConferenceonSystems,ManandCybernetics,1996,4,2947-295196.刘清算子Rough逻辑及其归结原理计算机学报1998215476-48097.祝峰何华灿粗集的公理化计算机学报2000233330-33398.ZhuF.andHeH.C.,Logicalpropertiesofroughsets,ProceedingsoftheFourthInternationalConference/ExhibitiononHighPerformanceComputingintheAsia-PacificRegion,2000,2,670-67199.孙辉刘大有李文粗集公理组的极小化计算机学报2002252202-209100.苗夺谦王珏粗糙集理论中知识粗糙性与信息熵关系的讨论模式识别与人工智能199811134-40101.苗夺谦王珏粗糙集理论中概念与运算的信息表示软件学报1999102113-116102.KimD.andBangS.Y.,Ahandwrittennumeralcharacterclassificationusingtolerantroughset,IEEETransactionsonPatternAnalysisandMachineIntelligence,2000,22(9),923-937103.SarkarM.andYegnanarayanaB.,Rough-fuzzysettheoreticapproachtoevaluatetheimportanceofinputfeaturesinclassification,ProceedingsofInternationalConferenceonNeuralNetworks,1997,3,1590-1595104.TaniguchiF.,KudoM.andShimboM.,Estimationofclassregionsinfeaturespaceusingroughsettheory,ProceedingsoftheInternationalConferenceonKnowledge-BasedIntelligentElectronicSystems,1997,2,373-37730 上海交通大学博士学位论文105.GermanoL.T.etc.,Classificationofpowersystemoperationpointusingroughsettechniques,ProceedingsofIEEEInternationalConferenceonSystems,ManandCybernetics,1996,3,1898-1903106.TsumotoS.,Automateddiscoveryofpositiveandnegativeknowledgeinclinicaldatabases,IEEEEngineeringinMedicineandBiologyMagazine,2000,19(4),56-62107.MitraP.,MitraS.andPalS.K.,Stagingofcervicalcancerwithsoftcomputing,IEEETransactionsonBiomedicalEngineering,2000,47(7),934-940108.TsumotoS.,Roughsetsandreasoningaboutcomplications-granularcomputationinthreasoning,Proceedingsofthe18InternationalConferenceoftheNorthAmericanonFuzzyInformation,1999,795-799109.NakayamaH.,HattoriY.andIshiiR.,Ruleextractionbasedonroughsettheoryanditsapplicationtomedicaldataanalysis,ProceedingsoftheInternationalConferenceonSystems,ManandCybernetics,1999,5,924-929110.ZarembaM.B.andWielgoszA.,Predictingoutcomeforhospitalizedcardiacpatientsusingacombinedneuralnetworksandroughsetapproach,ProceedingsoftheInternationalJointConferenceonNeuralNetworks,1999,5,3665-3668111.Perez-LieraC.etc.,Roughsetapproachfordataanalysisofanthracycline-inducedcardiotoxicity,ProceedingsoftheInternationalConferenceonSystems,ManandCybernetics,1997,1,951-957112.TsumotoS.andTanakaH.,Extractionofdomainknowledgefromdatabasesbasedonroughsettheory,ProceedingsoftheFifthIEEEInternationalConferenceonFuzzySystems,1996,2,748-754113.TsumotoS.andTanakaH.,Extractionofdiagnosticknowledgefromclinicaldatabasesbasedonroughsettheory,Proceedingsofthe1996AsianFuzzySystemsSymposium,1996,145-151114.MohamedA.S.A.,Applicationofartificialintelligenceforclinicaldecisionmakingandreasoning,ProceedingsoftheInternationalConferenceonSystems,Manand31 上海交通大学博士学位论文Cybernetics,1992,2,1075-1079115.MohabeyA.andRayA.K.,Roughsettheorybasedsegmentationofcolorimages,thProceedingsofthe19InternationalConferenceofNorthAmericanonFuzzyInformationProcessing2000338-342116.徐立中王慧敏刘美林杨锦堂粗糙集理论在图像增强中的应用数据采集与处理1999143307-310117.SunY.K.,CaoL.H.andCaoC.X.,SlabdefectdiagnosisandpredictingsysteminrdCCprocessingbasedonroughsettheory,Proceedingsofthe3WroldCongressonIntelligentControlandAutomation,2000,673-675118.HuT.,LuB.C.andChenG.J.,Arotarymachineryfaultdiagnosisapproachbasedrdonroughsettheory,Proceedingsofthe3WorldCongressonIntelligentControlandAutomation,2000,685-689119.LiX.L.andWuX.B.,Theapplicationofroughsettheoryinvehicletransmissionsystemsfaultdiagnosis,ProceedingsoftheIEEEInternationalVehicleElectronicsConference,1999,240-242120.KusiakA.andTsengT.I.,Datamininginengineeringdesign:acasestudy,rdProceedingsofthe3WorldCongressonIntelligentControlandAutomation,2000,2535-2539121.Fernandez-BaizanM.C.,RuizE.M.,SanchezJ.M.P.andMillanS.,UsingRSDMtominesocio-economicindicators,Proceedingsofthe1997IEEEInternationalConferenceonSystems,ManandCybernetics,1997,2,1385-1389122.FuS.X.,LuZ.X.,LuH.M.andLiY.,Roughsettheoryanditspracticeinrdknowledgediscovery,Proceedingsofthe3WorldCongressonIntelligentControlandAutomation,2000,2535-2539123.CzogalaE.,MrozekA.andPawlakZ.,Ideaofaroughfuzzycontrolleranditsapplicationtothestabilizationofapendulum-carsystem,FuzzySetsandSystems,1995,72(1),61-7332 上海交通大学博士学位论文124.MunakataT.,Roughcontrol:aperspective,in:RoughSetsandDataMining,1997,KluwerAcademicPublishers,USA,77-88125.PawlakZ.,Roughrealfunctionsandroughcontrollers,in:RoughSetsandDataMining,1997,KluwerAcademicPublishers,USA,139-147126.ArimaM.,HaraE.H.andKatzberyJ.D.,AfuzzylogicandroughsetscontrollerforHVACsystems.Communications,PowerandComputing,IEEEWESCANEX’95Proceedings,1995,133-138127.PetersJ.F.,ZiaeiK.,RamannaS.andEhikioyaS.A.,Adaptivefuzzyroughapproximatetimecontrollerdesignmethodology:concepts,petrinetmodelandapplication,IEEEInternationalConferenceonSystems,ManandCybernetics,1998,2101-2106128.MrozekA.,PlonkaL.andKedzieraJ.,Themethodologyofroughcontrollersynthesis,ProceedingsoftheFifthIEEEInternationalConferenceonFuzzySystems,1996,2,1135-1139129.李文模糊系统的知识模型与辨识方法[学位论文]哈尔滨哈尔滨工业大学1999130.李文孙辉陈善本一种建立模糊模型的粗糙集方法控制理论与应用200118169-75131.HongT.P.,WangT.T.,WangS.L.,andChienB.C.,Learningacoveragesetofmaximallygeneralfuzzyrulesbyroughsets,ExpertSystemswithApplication,2000,19(2),97-103132.YahiaM.E.,MahmodR.,SulaimanN.andAhmadF.,Roughneuralexpertsystems,ExpertSystemwithApplications,2000,18(2),87-99133.VigneronL.andWasilewskaA.,Roughsetsbasedproofsvisualization,Proceedingsthofthe18InternationalConferenceoftheNorthAmericanonFuzzyInformation,1999,805-808134.ShenQ.andChouchoulasA.,Data-drivenfuzzyruleinductionanditsapplicationto33 上海交通大学博士学位论文systemsmonitoring,FuzzySystemsConferenceProceedings,1999,2,928-933135.LiuP.andPetersJ.F.,Riskanalysisforhigh-voltagetransmissionlinedeicingsystem,Proceedingsofthe1999IEEECanadianConferenceElectricalandComputerEngineering,1999,3,1248-1252136.Chen-JimenezI.E.,KorneckiA.andZalewskiJ.,Softwaresafetyanalysisusingroughsets,ConferenceProceedings-IEEESOUTHEASTCON,199815-19137.RuheG.,Roughset-baseddataanalysisingoal-orientedsoftwaremeasurement,rdProceedingsofthe3InternationalConferenceonSoftwareMetricsSymposium,1996,10-19138.AnA.,ChanC.,ShanN.,CerconeN.andZiarkoW.,Applyingknowledgediscoverytopredictwater-supplyconsumption,IEEEExpert,1997,12(4),72-7834 上海交通大学博士学位论文第二章粗糙集知识建模方法2.1引言基于粗糙集理论的知识建模方法简称粗糙集知识建模方法是指用RS理论提供的决策表简化的方法从系统运行的经验数据中获得系统知识模型的方法在这一章中首先给出粗糙集知识建模方法的理论基础再提出粗糙集知识建模方法中知识模型的定义然后给出粗糙集知识建模方法的主要步骤最后对具体的建模步骤分别加以论述本章中除2.2节内容可以在相关参考文献中找到其中有些定义的形式同原有形式略有不同但本质相同此外其它内容如没有特别指出均为作者提出2.2粗糙集知识建模方法的理论基础粗糙集RSRoughSet理论是经典集合理论的拓展具有坚实的理论基础本节对粗糙集理论的基本思想和与本文研究内容相关的概念加以介绍在此之前先明确粗糙集理论所涉及的离散数学中的基本符号和定义2.2.1基本符号和定义集合或简称集是指具有某种特定性质的对象的全体在本文中集合用斜体大写TimesNewRoman字体的字母ABCXYZ等表示组成集合的对象称为集合的元素在本文中集合中元素用小写TimesNewRoman字体的字母abcxyz等表示元素a属于集合A表示为aÎA元素a不属于集合A表示为aÏA集合的元素也可以是已定义集合此时该集合可称为集族在本文中集族用大写CommercialScriptBT字体的字母ABCXYZ等表示集合A属于集族A表示为AÎA集合A不属于集族A表示为AÏA设A是一个集族则UA表示A中所有元素的并集而IA表示A中所有元素的交集集合A的基数Cardinality等于该集合元素的个数用ïAï表示在本文中讨35 上海交通大学博士学位论文论的集合如果不特别指出都是有限集合即集合中包含有限多个元素若把一个非空集合A分成若干个称为分块的非空子集使得A中每个元素至少属于一个分块那么这些分块的全体构成的集合叫做A的一个覆盖显然A的覆盖是一个集族对于A的一个覆盖如果A中每个元素属于且仅属于其中的一个分块则该覆盖称为A的一个划分或分划对覆盖和划分的形式定义如下设A为给定非空集合若集族S={S1S2Sm}其中SiÍASi¹Æ(i=12m)且US=A则集族S称为集合A的覆盖设A为给定非空集合若集族S={S1S2Sm}其中SiÍASi¹ÆSiÇSj¹Æ(ij=12mi¹j)且US=A则集族S称为集合A的划分两个具有固定次序的对象组成一个序偶用以表达两个对象之间的关系记为序偶可以看作是具有两个元素的集合但它与一般集合不同的是序偶具有确定的次序序偶中x称为第一元素y称为第二元素对任意的非空集合X和Y可以定义序偶的集合其中序偶的第一元素属于X第二元素属于Y该集合称为集合X和Y的直积记为X×Y直积的形式定义为X×Y={xÎX且yÎY}对任意的非空集合X和Y直积X×Y的子集R称作X到Y的二元关系简称关系特别地当X=Y时二元关系R是X×X的子集这时称R为X上的二元关系二元关系是序偶的集合二元关系可以进行集合的所有运算若ÎR则记xRy否则xRy下面给出集合A上的二元关系的几个性质1若对任意的xÎA都有xRx则称R在A上是自反的2若对任意的xÎAyÎA每当xRy时就有yRx则称R在A上是对称的3若对任意的xÎAyÎA每当xRyyRx时就有x=y则称R在A上是反对称的4若对任意的xÎAyÎAzÎA每当xRyyRz时就有xRz则称R在A36 上海交通大学博士学位论文上是传递的若集合A上的一个二元关系R是自反的对称的和传递的则R称为A上的等价关系若R为集合A上的等价关系对任何aÎA集合[a]R={xxÎAaRx}称为元素a形成的R等价类等价类的集合{[a]RaÎA}称为A关于R的商集记作A/R关于等价关系下面两个结论对本文是极为重要的1集合A上的一个等价关系R决定了A的一个划分该划分就是商集A/R2集合A的一个划分A确定A上的一个等价关系该等价关系为R=UX´XXÎA显然由上述两个定理可知在集合的划分同该集合上的等价关系之间存在着一一对应的关系设R为集合A上的一个二元关系若R是自反的反对称的传递的则R称为A上的偏序关系集合A和A上的一个偏序关系R组成的有序二元组称为偏序集设为一偏序集且BÍA若存在yÎB使得对任意的xÎB(x¹y)xRy成立则称y为B的极小元特别地当A=B时B的极小元也称为该偏序集的极小元关于经典集合论中相关内容的更深入讨论在参考文献[1]中可以找到类似的文献还有很多有些记号和定义的形式会略有不同但本质一样2.2.2粗糙集理论中的知识[2-7]关于知识的理论研究具有深远的历史直觉上知识可以被理解为是关于现实世界中我们感兴趣的信息的载体这种理解不能作为对知识的全面而准确的定义它不能反映不同学科领域对知识定义的特殊要求RS理论中没有给出关于知识的全面而准确的定义一方面因为知识的内涵太广太复杂在RS理论中给出这样的定义是不现实的另一方面给出关于知识的全面而37 上海交通大学博士学位论文准确的定义对RS理论本身来说没有太多的实际意义因而RS理论只是根据自身的需要在对知识独特理解的基础上针对知识某一方面的特性进行了定义在RS理论中认为知识同人类的分类能力有着本质的联系人类的分类行为体[8]现了人类所具有的知识根据数学观点分类可以用集合论中的划分的概念来刻划因而RS理论将非空有限集U论域上的划分理解为知识根据本章第一节可知划分是由U的子集构成的在RS理论中对任意的U的子集X都可以称为U中的一个概念即RS理论中知识是由特定的一些概念构成的即这些概念满足划分的定义由于等价关系和划分是一一对应的则U上的任意一个等价关系R在不引起混淆时可以直接称为关于U的知识即R—知识对任意的xÎUx形成的R等价类[x]R称为R—知识中的一个概念论域U和U上的等价关系的集合R构成的有序二元组称为知识库记为K设K=如果PÍR且P¹Æ则P也是一个等价关系称为P上的一个不可分辩关系记为IND(P)且有[x]=I[x]IND(P)RRÎP由于IND(P)是等价关系则U/IND(P)是U关于IND(P)的商集在不引起混淆时U/IND(P)可以简记为U/P特别地IND({a})可以简记为IND(a)设K=和K'=是两个知识库如果IND(R)=IND(P)或者U/R=U/P则称R和P(或知识库K和K')是等价的记为R@P(K@K')定义IND(K)={IND(Q)ïQ¹ÆQÍR}可以认为IND(K)包含了知识库中所有知识2.2.3粗糙集合设XÍU并且R是U上的一个等价关系称X是R—可定义的如果X是一些38 上海交通大学博士学位论文R的等价类的并集否则X是R—不可定义的R—可定义的集合也称R—确切集R—不可定义的集合也可称作是R—非确切的或R—粗糙集集合XÍU称为在知识库K中确切的如果存在一个等价关系RÎIND(K)使得X是R—确切的并且称X在K中是粗糙的如果X对于任意RÎIND(K)是R—粗糙的对于粗糙集可以将其理解为未知概念即用已有的知识不能对其精确描述而对于确切集可以将其理解为已知概念显然构成知识的概念一定是已知概念并且已知概念的并集仍是已知概念给定知识库K=对于每个集合XÍU和关系RÎIND(K)定义下面两个集合R*(X)={aÎU[a]RÍX}*R(X)={aÎU[a]RX¹Æ}分别称为集合X关于R的下逼近和上逼近其中R*(X)也称为X的正区记作POS(X)定义集合NEG(X)={aÎU[a]RX=Æ}称为X的负区显然*R(X)NEG(X)U集合X的边界区定义为*BN(X)=R(X)-R*(X)如果BN(X)=Æ则X是R—确切集反之如果BN(X)不是空集则X是R—粗糙集事实上下近似是一个确切集即一个未知概念所包含的最大的已知概念而上近似是包含该未知概念的最小的已知概念RS理论的基本思想就在于此即用两个特殊的已知概念来逼近未知概念这一基本思想可用图2-1来表示图2-1中不规则形状代表粗糙集合X即未知概念每个小正方形都代表一个等价类即已知概念颜色最深的小正方形构成了X的下近似即包含在X中的最大的已知概念颜色次深的小正形构成了X的边界区它们共同构成了X的上近似即包含X的最小39 上海交通大学博士学位论文的已知概念白色的小正方形构成了X的负区下近似和上近似是从内外两个不同方向逼近X的边界区的大小反映了逼近的程度也反映了X的粗糙程度图2-1粗糙集基本思想Fig.2-1Theideaoftheroughsettheory定义逼近精度aR(X)为|R(X)|a(X)=*R*|R(X)|显然0£aR(X)£1如果边界区为空集则aR(X)1此时集合X是R—确切集如果边界区为非空集则aR(X)<1此时集合X是R—粗糙集注意到如果图2-1中的小方块很小则边界区有可能变小逼近精度可能变大而知识库中知识增多即等价关系的个数增多方块才可能会变小所以可以认为当知识增多时粗糙集有可能变成精确集也即当知识增多时未知概念可能变成已知概念这符合人类的认知规律在经典集合论中集合X的隶属函数m(a)定义为1aÎXmX(a)=0aÏX该隶属函数只有两种取值是非此即彼的类似的可以给出粗糙隶属函数的定义40 上海交通大学博士学位论文|XI[a]|mR(a)=RX|[a]|RR显然0£m(a)£1即粗糙隶属函数可以在一个区间内取值从所周知模糊隶X属函数也是可以在一个区间内取值的因而粗糙集和模糊集都是经典集合论的拓展但是粗糙集理论中粗糙隶属函数的定义是不需要先验知识的这一点不同于模糊隶属函数的定义2.2.4知识的约简设R是等价关系的集合并且有RÎR如果IND(R)=IND(R-{R})称R是R中可略的否则称R是R中不可略的如果任意的RÎR都是R中不可略的称R是精简的否则称R是冗余的可以证明如果R是精简的并且PÍR则P也是精简的设P是等价关系的集合并且QÍP如果Q是精简的并且IND(P)=IND(Q)称Q是P的一个约简P中不可略的等价关系的集合称为P的核记为CORE(P)在P的约简和核之间有下面关系CORE(P)=RED(P)这里RED(P)是P的所有约简的集合设知识库K=P是R的一个约简则知识库K'=与知识库K是等价的2.2.5知识的相对约简设P和Q是U上的等价关系称POSP(Q)为Q的P—确定区且有41 上海交通大学博士学位论文POSP(Q)=UP*(X)XÎU/Q设P和Q是U上的等价关系集合称RÎP是P中Q—可略的如果POSIND(P)(IND(Q))=POSIND(P-{R})(IND(Q))否则R是P中Q—不可略的如果任意RÎP是P中Q—不可略的称P是Q—精简的设SP和Q是U上的等价关系族且SÍP称S是P的Q—约简当且仅当S是Q—精简的且POSS(Q)=POSP(Q)P中所有Q—不可略等价关系的集合称为P的Q—核记为COREQ(P)同样COREQ(P)=REDQ(P)其中REDQ(P)是P的所有Q—约简的集合2.2.6知识库中的依赖设知识库K=(UR)且PQÍR1当且仅当IND(P)ÍIND(Q)称Q依赖P记为PÞQ2当且仅当PÞQ且QÞP称P和Q是相等的记为PºQ3当且仅当Q不依赖P且P也不依赖Q称P和Q是独立的显然PºQ当且仅当IND(P)=IND(Q)下面命题成立1如果P是Q的一个约简则PÞQ-P且IND(P)=IND(Q)2如果P是冗余的则存在QÌP使得Q是P的一个约简3如果P是精简的则P的任意两个子集是两两独立的由命题1可知进行知识约简时没有包含在约简中的那部分知识是依赖于约42 上海交通大学博士学位论文简中的知识的由命题2可知一个冗余的知识库必可以进行知识约简由命题3可知一个精简的知识库中是不存在任何依赖的2.2.7知识表达系统知识表达系统又称属性表是一个四元组S=其中U是称为论域的非空有限集合A是属性的非空有限集合V=UVa•CŽ§Va•¥‘®•«a揑值域•aÎAfUAV是一个信息函数它为每个对象的每个属性赋予一个信息值对任意的aÎAxÎU有f(xa)ÎVa表2.1是一个知识表达系统U={x1x2x3x4x5x6x7}A={abcde}根据属性值的不同每个属性都可以唯一确定论域的一个划分即属性值相同的元素属于一个分块在表2-1中c将U分成两个分块d将U分成三个分块由于划分同等价关系的一一对应关系可以将每个属性理解成一个等价关系表2-1一个知识表达系统Table2-1AknowledgerepresentationsystemUabcdex110011x210001x300000x411010x511022x622022x722222在知识表达系统中设PÍA定义属性集P的不可分辨关系IND(P)为IND(P)={Î(U´U)任意的aÎPf(xa)=f(ya)}直觉上对某个属性来说如果两个元素的取值是相同的则该属性不能将这两个43 上海交通大学博士学位论文元素区分开这也是粗糙集理论中将等价关系称为不可分辨关系的原因如果ÎIND(P)即xIND(P)y则x和y是不可分辨的在不引起混淆的情况下IND(P)简记为PU/P表示IND(P)的商集[x]P是包含x的IND(P)的等价类至此可以将属性表转换为知识库则前面部分讨论的知识库的相应内容都适用于属性表简言之只要给出属性表就可确定一个知识库就可以计算正区负区边界区逼近精度等也可以求知识约简核等在对知识表达系统的讨论中可以将属性称为属性知识而知识约简可以称为属性约简2.2.8决策表决策表是一类特殊的知识表达系统即特殊的属性表决策表可以认为是明确的将属性区分为条件属性和决策属性两部分的属性表S=是属性表则决策表DT=是一个五元组CÇD=ÆCÈD=AC是条件属性的集合D是决策属性的集合设PÍAQÍA定义|POS(Q)|g(Q)=PP|U|若gC(D)=1则称决策表为一致决策表否则为不一致决策表决策表的条件属性并不都具有相同的地位设C¢ÍC定义C¢关于D的重要性s(C')=g(D)-g(D)CDCC-C'2.2.9决策表的简化决策表经过简化可以得到一系列的决策规则简化的方法主要有三种条件属性约简条件属性值约简和规则约简为了便于论文后面部分论述这部分中相关定义同文献[8]中原始定义在形式上略有不同一决策表的条件属性约简44 上海交通大学博士学位论文表2-2决策表Table2-2ThedecisiontableCDUabcdex110011x210001x300000x411010x511022x622022x722222决策表的条件属性约简是指决策表的条件属性相对决策属性的约简以表2-2中决策表为例C的唯一的一个D—约简即该决策表的唯一的一个条件属性约简为{abd}它也是C的D—核决策表的每个条件属性约简都可以构成一个新的决策表设决策表DT=C'是它的一个条件属性约简则可以构成一个新的决策表DT'=其中V'=UVaaÎC'而V是属性a的值域f'UC'UDV'并且f'(x)=f(x)表2-3中决策表是表2-2a中决策表条件属性约简后的决策表直觉上新决策表只包含原决策表中C的D—约简中的条件属性但是保持了原决策表中的全部有意义的信息二决策表的条件属性值约简在条件属性约简后可以通过条件属性值约简进一步简化决策表设决策表DT=GÍCÈD对任意的xÎU定义属性和属性45 上海交通大学博士学位论文值对的集合Gx={(af(xa))aÎG}•其中(af(xa))称为属性和属性值对以表2-3为例设G={ab}则Gx1={(a1)(b0)}表2-3条件属性约简后的决策表Table2-3ThedecisiontablewithreducedconditionattributesCDUabdex11011x21001x30000x41110x51122x62222x72222设GÍCxÎU并且I[x]GÍI[x]D对任意的aÎG如果I[x]G-{a}ÍI[x]D则称a是G中I[x]D—可略的否则称a是G中I[x]D—不可略的如果G中任意的a都是G中I[x]D—不可略的则称G在I[x]G中是I[x]D—独立的否则称G在I[x]G中是I[x]D—依赖的设GÍCxÎU并且I[x]CÍI[x]DGx是x的条件属性值约简当且仅当I[x]GÍI[x]D并且G在I[x]G中是I[x]D—独立的以表2-3中决策表为例x1的条件属性值约简有两个分别是{(a1)(b0)}和{(b0)(d1)}而x3的条件属性值约简只有一个即{(a0)}表2-3中决策46 上海交通大学博士学位论文表的全部条件属性值约简如表2-4所示表2-4条件属性值约简Table2-4TheconditionattributevaluereductionsU条件属性值约简{(a1)(b0)}x1{(b0)(d1)}{(a1)(b0)}x2{(a1)(d0)}x3{(a0)}x4{(b1)(d1)}x5{(d2)}{(a2)}x6{(b2)}{(d2)}{(a2)}x7{(b2)}{(d2)}需要指出对任意的x如果I[x]CÍI[x]D不成立则它没有条件属性值约简但是为了处理的一致性在不引起混淆的情况下认为它的条件属性值约简是其本身三决策表的规则约简在条件属性约简和条件属性值约简的基础上可以进行决策表的规则约简设决策表DT=GÍCÈD定义Ù(G)=gÙgÙ...ÙgÙ...•C其中gÎG•Bx12iix对任意的xÎU设Gx是x的一个值约简关于x的一条规则可以定义为47 上海交通大学博士学位论文Ù(Gx)®Ù(Dx)以表2-3为例{(a1)(b0)}是x1的一个条件属性值约简则Ù{(a1)(b0)}®Ù{(e1)}即(a1)Ù(b0)}®(e1)是关于x1的一条规则表2-3的全部规则如表2-5所示表2-5规则表Table2-5RuletableU规则(a1)Ù(b0)®(e1)x1(b0)Ù(d1)®(e1)(a1)Ù(b0)®(e1)x2(a1)Ù(d0)®(e1)x3(a0)®(e0)x4(b1)Ù(d1)®(e0)x5(d2)®(e2)(a2)®(e2)x6(b2)®(e2)(d2)®(e2)(a2)®(e2)x7(b2)®(e2)(d2)®(e2)设决策表DT=对任意的xÎU关于x的全部规则的集合记为Rule(x)对任意的XÍU定义Rule(X)=U{Rule(x)xÎX}设RDÍRule(U)如果对任意的xÎURDÇRule(x)¹Æ并且对任意的RD'ÌRDRD'ÇRule(x)¹Æ不成立则称RD为决策表的规则约简以表2-5为例其规则约简48 上海交通大学博士学位论文有两个如表2-6所示需指出对给定的决策表规则约简是依赖于特定的条件属性约简的表2-6规则约简Table2-6Rulereduction规则约简1规则约简2(b0)Ù(d1)®(e1)(a1)Ù(b0)®(e1)(a1)Ù(d0)®(e1)(a0)®(e0)(a0)®(e0)(b1)Ù(d1)®(e0)(b1)Ù(d1)®(e0)(d2)®(e2)(d2)®(e2)2.2.10差别矩阵[910]为了更有效的计算决策表的条件属性约简引入差别矩阵的概念对于决策表DT=设|U|=n决策表DT的差别矩阵MDT是一个n´n的矩阵其任一元素cij={aÎCf(xia)¹f(xja)且w(xixj)=1}其中1xiÎPOSC(D)且xjÏPOSC(D)1xiÏPOSC(D)且xjÎPOSC(D)w(xixj)=1xixjÎPOSC(D)且(xixj)ÏIND(D)0其它显然MDT是一个对称的矩阵表2-7中是一决策表其中C={abc}D={d}表2-8是其差别矩阵下面命题是成立的1对任意的PÍC若P同差别矩阵中任意的非空集元素的交集不为空集则P是条件属性约简2对差别矩阵中任意的元素Q若|Q|=1则Q中的元素是核C的D—核中的元素49 上海交通大学博士学位论文表2-7决策表Table2-7AdecisiontableCDUabcdx12201x21200x31201x40000x51010x62011表2-8差别矩阵Table2-8Thediscernibilitymatrix1234561Æ{a}{a}{ab}{abc}Æ2{a}ÆÆ{ab}{bc}{abc}3{a}ÆÆ{ab}{bc}{abc}4{ab}{ab}{ab}ÆÆ{ac}5{abc}{bc}{bc}ÆÆ{a}6Æ{abc}{abc}{ac}{a}Æ据此求条件属性约简和核的问题已经转换成简单的集合运算以表2-8为例{ab}和{ac}是条件属性约简{a}是核本节中出现的一些主要概念和符号的索引参见附录2.3知识模型粗糙集知识建模方法同神经网络建模方法和模糊集建模方法一样都不是基于对系统特性精确数学描述的因而粗糙集知识建模方法中系统模型的形式同经典模型理论中的模型形式也是不同的本节给出粗糙集知识建模方法中知识模型的定义50 上海交通大学博士学位论文设系统S有m个输入变量n个输出变量令X={x1x2xm}为S的输入空间令Y={y1y2yn}为S的输出空间设对系统的输入和输出进行了有限次测量t次后得到的输入和输出测量值构成如下矩阵Mt´(m+n)x11x12x1my11y12y1méùêx21x22x2my21y22y2múêút´(m+n)=êúêúêúëxt1xt2xtmyt1yt2ytmúû对该矩阵的每一行添加标号l1l2lt令L={l1l2lt}此时可以构造决策表DT=其中论域U=L且|U|=t条件属性集C=X={x1x2xm}且|C|=m决策属性集D=Y={y1y2yn}且|D|=n条件属性值的集合VC={xiji=1t且j=1m}决策属性值的集合VD={yiji=1t且j=1n}属性值的集合V=VCÈVD信息函数fU´CÈD®V且f(la)的值为矩阵Mt´(m+n)对应位置的值构造的决策表如表2-9所示对所构造的决策表用RS理论中的决策表简化方法加以简化得到一些形如Ù(Gl)®Ù(Dl)51 上海交通大学博士学位论文的规则的集合规则约简其中Gl是U中元素l的条件属性值约简由RS理论可知该规则的集合是无冗余的并且该规则的集合同原有决策表具有相等的信息量本文中将该规则的集合称为系统S的知识模型表2-9决策表Table2-9ThedecisiontableCDUx1x2xmy1y2ynl1x11x12x1my11y12y1nl2x21x22x2my21y22y2nltxt1xt2xtmyt1yt2ytn根据知识模型的定义可知关于粗糙集知识建模方法需要一个假设假设系统S的特性完全可以由有限次测量后得到的测量值组成的矩阵来表征有了这一假设后用粗糙集知识建模方法得到的知识模型才是有效的因为从理论上讲所获得的知识模型同原有决策表测量值的矩阵是具有等价性的之所以将获得的模型称为知识模型原因有二个一是因为所获得的模型是不依赖于精确的数学描述的另外一个重要原因是建模所采用的粗糙集方法完全是基于RS理论对知识的理解的2.4粗糙集知识建模方法的框架本文提出的粗糙集知识建模方法的主要步骤包括1建模数据获取2数据预处理3连续属性离散化4条件属性约简5条件属性值约简6规则约简52 上海交通大学博士学位论文7知识推理其中条件属性约简和条件属性值约简以及规则约简是模型获取的核心部分图2-2是粗糙集知识建模方法的示意图ModelingdataacquiringDatapreprocessingContinuousattributediscretizationConditionattributereductionConditionattributevaluereductionRulereductionKnowledgereasoning图2-2粗糙集建模方法主要步骤Fig.2-2Mainstepsoftheroughsetbasedmodelingmethod2.5建模数据的获取用于建模的数据可以长期积累的经验数据也可以是通过特别设计的实验批量获得的实验数据对长期积累的经验数据只能被动选择建模所需数据灵活性较小限制较多建模大多采用通过实验批量获得的实验数据如前所述粗糙集的建模方法需要一个假设系统S的特性完全可以由有限次测量后得到的测量值组成的矩阵来表征如果没有足够的建模数据则任何对建模方法的研究都是无意义的因而本文认为粗糙集知识建模方法需要解决的第一个问题即是建模数据的问题其中包括数据量和数据的有效性两个方面分别分析如下1数据量由于系统S的特性是用一个矩阵来表征的因而所谓的数据量包括两个方面53 上海交通大学博士学位论文一方面是矩阵的列数即系统的输入和输出变量的个数从RS理论本身的角度考虑系统的输入变量应该是尽可能多这样可以保证对系统S特性描述的精确性但是根据本文研究这种倾向会导致实际处理过程中计算复杂性超出可以接受的范围此外当S的输入变量增多时对其测量所需的传感系统及相关设备的要求相应增大这在实际中也要充分考虑事实上对输入变量的选择是极为复杂的但是相关的讨论已经超出本文的研究范围这里不进行深入讨论系统的输出变量的确定取决于建模的目的但是从RS理论本身的角度考虑输出变量的个数只涉及到模型的复杂程度输出变量越多模型趋向于越复杂但对建模过程本身并无影响另一方面是矩阵的行数即测量的次数在建模数据获取过程中必须保证足够的测量次数关于测量次数同系统输入和输出变量个数间关系的定量研究仍不充分并且不在本文研究范围内2数据的有效性建模数据的获取要保证数据有效性即尽量使得系统的所有可能状态能够通过数据反映出来数据的有效性同数据量之间存在必然联系设系统S有k种可能状态则至少需要对系统S进行k次测量如果数据量小于k则最终所获得的模型不可能有效的反映系统的本质但是即使数据量大于k如果有些数据反映是相同的系统状态则最终获得的模型同样不能有效的反映系统的本质可见数据有效性是以数据量为基础的在此基础上若要保证数据的有效性仍需考虑数据的分布情况使得数据覆盖系统的状态空间数据有效性在实际中是依赖于实验的设计的通过对实验的设计尽可能的激发系统所有的可能的状态2.6数据预处理我们认为在数据预处理过程主要解决下列问题1无效数据的过滤建模数据获取后可以确认有些数据是明显的干扰数据这些数据是需要被过滤掉的以电弧焊接过程为例实验过程中焊接的起弧和收弧阶段的数据是不稳定的可以认为是干扰数据可以在数据预处理阶段中将其略去本文研究证明这样54 上海交通大学博士学位论文做不仅可以减小建模过程的计算复杂性而且可以提高最终模型的有效性2数据扩展通常系统模型可以分为静态模型和动态模型两种用粗糙集知识建模方法获取系统的静态模型和动态模型本质上并无区别建模数据获取阶段得到的数据可以直接用来获得系统的静态模型这一点在2.3节的介绍中可以看出如果需要得到系统的动态模型本文的主要研究内容则在数据预处理过程需要对建模数据获取阶段获得的数据进行扩展本文给出的扩展方法如下设对系统S的输入和输出的第i次测量i时刻得到的数据为一向量di=[xi1xi2ximyi1yi2yim]且设i时刻系统状态同前k(k>0)个时刻系统的状态相关则扩展后第i时刻的数据为向量Di=[x(i-k)1x(i-k)2•D•D•Dx(i-k)my(i-k)1y(i-k)2•D•D•Dy(i-k)nx(i-k+1)1x(i-k+1)2•D•D•Dx(i-k+1)my(i-k+1)1y(i-k+1)2•D•D•Dy(i-k+1)n•D•D•Dxi1xi2•D•D•Dximyi1yi2•D•D•Dyin]其中k称为数据扩展系数对表2-9中决策表的第k+1行以后的所有行都可以按照上述方法进行扩展前k行数据由于无法进行扩展而略去表2-10这样扩展后的决策表DT'=中U'=U-{l1l2lk}且|U'|=|U|-k{x(k)x(k)x(k)(k)(k)(k)C'=yyy12m12n(k-1)(k-1)(k-1)(k-1)(k-1)(k-1)xxxyyy12m12n(0)(0)(0)xxx}且|C'|=(m+n)k+m•G12mf'U'´C'ÈD®V55 上海交通大学博士学位论文表2-10扩展的决策表Table2-10TheexpandeddecisiontableC'DU'(k)(k)(k)(k)(0)(0)x1xmy1ynx1xmy1ynl1x11x1my11y1nl2x21x2my21y2nlkx11x1mxk1xkmyk1yknlk+1x11x1mx21x2mx(k+1)1x(k+1)my(k+1)1y(k+1)nltx(t-k)1x(t-k)mx(t-k+1)1x(t-k+1)mxt1xtmyt1ytn2.7连续属性离散化在决策表中根据条件属性和决策属性的取值情况可是分成两种1连续属性这种属性的取值范围为一连续区间可取的值的个数是无限多的如焊接宽度的取值区间为[2mm6mm]2离散属性这种属性的取值范围为一有限集合可取的值的个数是有限多的如人的血型的取值范围为{ABABO}在实际中若属性的取值范围为一有限集合但是可取的值的个数很大如人的年龄的取值范围为{01150}可取的值为151个则通常将这类属性也作为连续属性处理在实际应用中RS理论可以处理的属性只能是离散属性对连续属性需要先进行离散化如果不进行离散化会导致计算复杂性超过限制本文给出粗糙集建模方法中决策表中连续属性离散化的形式描述如下设决策表DT=sÎCUDs是一连续属性其取值区间Vs=[a56 上海交通大学博士学位论文b]这里区间是一个左右都闭的闭区间事实上左右两侧的开或闭对问题的讨论并无影响因而本文中仅考虑左右都闭的闭区间对任意的cÎ[ab]称c为s的一个断点设Is为s的断点的集合且Is={c0cicr}|Is|=r+1a=c0称DT'=为决策表DT的离散化后决策表其中V'=UV's•若Cs是连续属性•C则V's是Vs的一个离散化•C否则V's=Vs•C而VsÎCÈD=UVs•GsÎCÈDf'U´CÈD®V'且对任意的lÎUsÎCUD若s是连续属性则f'(ls)是f(ls)离散化后的值否则f'(ls)=f(ls)从离散化的形式描述中可以看出对一个连续属性离散化的实质是确定断点的个数和位置离散化方法的研究对本文具有重要意义离散化会造成一些信息忽略有些信息的忽略不会影响模型的有效性但是有些信息的忽略会在很大程度上影响模型的有效性在保证模型有效性的前提下使得离散化的断点尽量少是粗糙集知[11]识建模方法对离散化的要求从理论上分析离散化问题是一个NP-hard问题对于这类问题无法有效的求取最优解在其它领域中离散化问题也是经常涉及的已有常用的离散化方法包括等区间[11-15]离散化方法等频离散化方法自组织映射神经网络离散化方法和二次离散化[16]方法下面对本文验证实验中使用的等区间离散化方法加以介绍57 上海交通大学博士学位论文等区间离散化方法又称等宽离散化方法该方法中断点的个数是确定的即子区间的个数是离散化之间确定的并且每个子区间的大小是相等的设连续属性s的取值区间为[ab]断点个数为k+2包括a和b则每个子区间的大小b-ad=k+1这样断点的集合Is={a+idi=0k+1}表2-11决策表Table2-11AdecisiontableCDUabcx10.82001x21.02030x31.32971x41.71691x52.14001x60.92010x71.62400表2-11是一决策表其中条件属性a和b是连续属性取值区间分别为[03]和[100500]对ab进行等区间离散化断点个数分别为7个和6个则断点集分别为{00.511.522.53}和{100180260340420500}表2-12是等区间离散化后的决策表58 上海交通大学博士学位论文表2-12离散化的决策表Table2-12AdiscretedecisiontableCDUabcx1221x2320x3331x4411x5541x6220x74202.8条件属性约简条件属性约简是本文提出的粗糙集知识建模方法中最重要的一个步骤对最终模型的复杂程度有极大的影响直观上条件属性约简可以缩短构成最终模型的全部规则的长度而规则越短在一定程度上表明该规则体现的规律性强在这一步骤中条件属性约简算法是至关重要的根据2.2中对条件属性约简的定义可知一个决策表的条件属性约简可以是不唯一的对该不唯一性的理解决定了条件属性约简算法求解目标的不同针对这一点本文给出以下三个方面的分析1从RS理论的角度看由不同的条件属性约简构成的新的决策表同原决策表包含的有意义的信息都是同样多的因而对这些条件属性约简是可以等同对待的同时用于求条件属性约简的算法简称属性约简算法除Z.Pawlak给出的理论算法之外没有任何一种属性约简算法可以同时求出全部条件属性约简甚至没有一种属性约简算法可以同时求出两种条件属性约简来绝大部分属性约简算法只能求一种属性约简这些算法只求一种条件属性约简也是基于决策表的全部属性约简具有同等重要性这一观点的2单纯从条件属性约简中包含的条件属性的个数来看可以认为包含的条件59 上海交通大学博士学位论文属性个数越少越好即包含条件属性个数最少的条件属性约简是最优的显然最优的条件属性约简也可能是不唯一的多数属性约简算法的目的是求一个最优的条件属性约简因为这已经是非常困难了所以更谈不到求所有最优的条件属性约简了迄今为至已知的可以求所有最优的条件属性约简的算法只有Z.Pawlak的理论算法但是该理论算法在实际中是不可行的因为其时间复杂性是指数形式的事实上可以根据计算复杂性理论证明求最优的条件属性约简是NP-hard的因而在实际中不可能找到可行的算法的来求最优的条件属性约简已有的属性算法大多只能近似求出最优的条件属性约简即不能保证在所有情况下都求得最优的条件属性约简并且对一些算法有些情况下所求得的结果甚至不能满足条件属性约简的定义3从实际应用的角度考虑不同的条件属性约简同样具有不同的地位在实际应用中条件属性约简中包含的条件属性的个数最少并不能表明它最适合实际应用假设条件属性约简A只包含一个条件属性a而条件属性约简B包含两个条件属性b和c但不能据此认定A优于B如果为了得到a的值需要一个精密的仪器其代价为ma而为了得到b和c的值只需要两个非常简单的仪器其代价为mb+mc而mb+mc是远远小于ma的此时认为B是优于A的因而在实际中判断一个条件属性约简的优劣需要另外定义相应的代价函数同样对于有代价函数的情况下也没有有效的属性约简算法求得最优的条件属性约简为了更深入的对条件属性约简算法进行研究有必要对条件属性约简算法进行系统的分类本文提出如下不同的分类方法1按照属性约简算法的时间复杂性分类可以分为多项式时间复杂性的属性约简算法和指数时间复杂性的属性约简算法两类Z.Pawlak的理论算法是指数时间复[8][17-23]杂性的而大多数算法是多项式时间复杂性的2按照属性约简算法是否采用决策表分类可以分为基于决策表的属性约简算[7-10][2124]法和基于判别矩阵的属性约算法3按照属性约简算法是否使用启发信息分类可以分为启发式属性约简算法[17-24][8]和非启发式属性约简算法在启发式属性约简算法中又可以分为静态启发式属性约简算法和动态启发式属性约简算法两类60 上海交通大学博士学位论文[824]4按照完备性分类可以分为完备属性约简算法和非完备属性约简算法[17-23]完备性的形式定义在下一章给出[24]5按照是否使用先验知识分类可以分为有先验知识属性约简算法和无先验[817-23]知识属性约简算法需指出启发信息同先验知识是不同的两个概念启发信息是在算法运行过程得到的而先验知识是算法运行前已经给出的表2-13是条件属性约简算法分类表表2-13属性约简算法分类Table2-13Classificationsofattributereductionalgorithms分类标准分类情况多项式时间复杂性属性约简算法时间复杂性指数时间复杂性属性约简算法基于决策表的属性约简算法是否采用决策表基于判别矩阵的属性约简算法非启发式属性约简算法静态启发式属性是否使用启发信息启发式属性约简算法约简算法动态启发式属性约简算法完备属性约简算法完备性非完备属性约简算法有先验知识属性约简算法是否使用先验知识无先验知识属性约简算法以Z.Pawlak的理论算法为例它是指数复杂性的基于决策表的非启发式的完备的无先验知识的属性约简算法文献[21]中的算法是多项式时间复杂性的基于差别矩阵的启发式的非完备的无先验知识的属性约简算法文献[24]中的算法是多项式时间复杂性的基于差别矩阵的非启发式的完备的有先验知识的61 上海交通大学博士学位论文属性约简算法本文后面部分构造条件属性约简算法的原则是构造多项式时间复杂性的基于差别矩阵的非启发式的完备的有先验知识的条件属性约简算法属性约简算法是粗糙集知识建模方法的最核心算法由于条件属性约简同条件属性值约简以及规则约简在本质上的一致性使得属性约简算法可以作为构造条件属性值约简算法和规则约简算法的基础关于属性约简算法的理论研究将在下一章进行2.9条件属性值约简条件属性值约简是粗糙集知识建模方法中一个重要步骤可以在一定程度上影响最终模型的复杂程度直观上条件属性值约简可以分别缩短每条模型中每条规则的长度从一定程度上可以认为条件属性约简对规则的缩短是全局性的而条件属性值约简对规则的缩短是局部性的根据2.2中对条件属性值约简的定义可知条件属性值约简同条件属性约简并无直接关系它们是两种不同约简但是由约简结果的比较分析可知两者之间在功能上存在部分重叠对此本文给出如下分析设决策表为DT=RED是DT的条件属性约简的集合任意的RÎRED决策表DT'=其中V'=UVaaÎR而V是属性a的值域f'UC'UDV'并且f'(x)=f(x)可以证明对任意的xÎUa若在决策表DT'中Gx是x的条件属性值约简则在决策表DT中Gx也是x的条件属性值约简反之则不成立如果DT只有唯一一个属性约简则可以证明在DT中Gx是x的条件属性值约简等价于在DT'中Gx是x的条件属性值约简以表2-14中决策表DT1=为例{abd}是它的一个条件属性约简对DT1进行条件属性约简后的决策表DT2=如表2-15所示在DT2中{(a1)(b0)}是x1的一个条件属性值约简在DT1中{(a1)(b0)}仍是x1的一个条件属性值约简表2-14决策表DT1Table2-14ThedecisiontableDT1CDUabcdex110011x210001x300000x411010x511022x622022x722222表2-15决策表DT2Table2-15ThedecisiontableDT2CDUabdex11011x21001x30000x41110x51122x62222x72222但是对表2-16中决策表DT3={ab}是它的条件属性约简对DT3进行条件属性约简后的决策表DT4=如表3-1063 上海交通大学博士学位论文所示在DT3中{(a1)(c1)}是x5的条件属性值约简而在DT4中只有{(a1)(b0)}是x5的条件属性值约简进一步分析可知DT3的条件属性值约简不唯一{ac}也是它的条件属性约简因而导致了上述情况的发生表2-16决策表DT3Table2-16ThedecisiontableDT3CDUabcdx12201x21200x31201x40000x51010x62011表2-17决策表DT4Table2-17ThedecisiontableDT4CDUabdx1221x2120x3121x4000x5100由于条件属性值约简和条件属性约简在功能上的重叠在本文给出的粗糙集知识建模方法中在进行条件属性约简之后再进行条件属性值约简如果直接进行条件属性值约简在理论上是可行的但是这样会导致计算复杂性的增加并且不利于最终获得有效的模型64 上海交通大学博士学位论文同条件属性约简类似求最优的条件属性值约简也是NP-hard的关于条件属性值约简算法可以简称属性值约简算法的研究相对属性约简算法的研究是比较少的一方面是因为条件属性值约简的理论意义相对较小另一方面是因为可以在属性约简的算法基础上构造属性值约简算法不需要直接研究属性值约简算法属性值约简算法同属性约简算法最大的不同之处在于通常条件属性约简求出一种即可事实上大部分属性约简算法只能做到这一步而条件属性值约简时根据本文研究对论域中任意元素只求出一种条件属性值约简就不能满足需要了根据第二章对规则约简的定义可知条件属性值约简是规则约简的基础条件属性值约简的结果会在很大程度上影响规则约简的结果影响到最终模型的复杂程度对此可通过表2-18中决策表DT=加以说明先对任意的xÎU求全部条件属性值约简如表2-19所示再对任意的xÎU只求一种条件属性值约简可能的一种结果如表2-20所示可能的另一种结果如表2-21所示根据表2-19进行规则约简可以得到两个规则约简如表2-22所示根据表2-20进行规则约简只能得到一个规则约简如表2-23所示根据表2-21进行规则约简也只能得到一个规则约简如表2-24所示表2-18决策表Table2-18ThedecisiontableCDUabdex11011x21001x30000x41110x51122x62122x7222265 上海交通大学博士学位论文表2-19条件属性值约简1Table2-19Theconditionattributevaluereductions1U条件属性值约简{(a1)(b0)}x1{(b0)(d1)}{(a1)(b0)}x2{(a1)(d0)}x3{(a0)}x4{(b1)(d1)}x5{(d2)}{(a2)}x6{(d2)}{(a2)}x7{(b2)}{(d2)}表2-20条件属性值约简2Table2-20Theconditionattributevaluereductions2U条件属性值约简x1{(a1)(b0)}x2{(a1)(d0)}x3{(a0)}x4{(b1)(d1)}x5{(d2)}x6{(a2)}x7{(b2)}66 上海交通大学博士学位论文表2-21条件属性值约简3Table2-21Theconditionattributevaluereductions3U条件属性值约简x1{(a1)(b0)}x2{(a1)(b0)}x3{(a0)}x4{(b1)(d1)}x5{(d2)}x6{(d2)}x7{(d2)}表2-22规则约简1Table2-22Rulereduction1规则约简1规则约简2(b0)Ù(d1)®(e1)(a1)Ù(b0)®(e1)(a1)Ù(d0)®(e1)(a0)®(e0)(a0)®(e0)(b1)Ù(d1)®(e0)(b1)Ù(d1)®(e0)(d2)®(e2)(d2)®(e2)表2-23规则约简2Table2-23Rulereduction2规则约简1(a1)Ù(b0)®(e1)(a1)Ù(d0)®(e1)(a0)®(e0)(b1)Ù(d1)®(e0)(a2)®(e2)67 上海交通大学博士学位论文(b2)®(e2)(d2)®(e2)表2-24规则约简3Table2-24Rulereduction3规则约简1(a1)Ù(b0)®(e1)(a0)®(e0)(b1)Ù(d1)®(e0)(d2)®(e2)对比表2-222-23和2-24可知如果只求一种条件属性值约简则最多求得一种规则约简并且有可能导致所求得的结果具有冗余的规则表2-23此时按照规则约简的定义所求得的结果已经不是原决策表的规则约简了如前所述在对任意的xÎU进行条件属性值约简时无法求得全部的条件属性值约简同时像进行条件属性约简时一样只求得一种条件属性值约简又可能导致不能求得正真意义上的规则约简为了有效的获取模型必须解决这一问题在本文中提出了一种折衷的方法构造一个属性值约简算法使得该算法每次运行的结果不同这一点可以通过在算法中加入一个随机环节来实现然后设置一个阈值T规定算法至多运行T次在算法的每次运行后对所求得的条件属性值约简进行检查如果新得到的条件属性值约简同已经求得的某个条件属性值约简相同则不再继续运行算法认为此时已经求得全部的条件属性值约简并且全部条件属性值约简的个数是小于T的如果算法被运行了T次仍没有求得重复的条件属性值约简则也不再继续运行算法认为全部条件属性值约简的个数是大于T的这样通过适当的调节T值的大小就可以在一定程度上解决上述问题获得满意的结果关于这种属性值约简算法的具体研究在下一章中给出2.10规则约简条件属性值约简是粗糙集知识建模方法中一个重要步骤可以在一定程度上影68 上海交通大学博士学位论文响最终模型的复杂程度直观上规则约简可以减少最终规则模型中规则的条数求最优的规则约简仍是NP-hard的规则约简算法的同属性值约简算法一样可以在属性约简算法的基础上构造因而关于规则约简算法的研究同样相对较少在下一章中将给出对规则约简算法的讨论规则约简的结果是一些规则的集合表2-18中决策表的一个规则约简如表2-24所示为了使得规则约简的结果更加直观本文给出一种类似决策表的更直观的表示方法表2-25表2-24中每一行对应于表2-25中每一行表2-24中出现的所有条件属性条件属性约简中的属性和决策属性都对应于表2-25中的一列如果表2-25中第j列对应的属性a出现在表2-24中第i条规则ÙGx®ÙDx中即(av)ÎGxÈDx其中xÎUvÎVaGx是决策DT=中x的一个条件属性值约简那么第i行第j列对应的值为v如果(av)ÏGxÈDx那么第i行第j列对应的值为Null表3-18规则约简Table3-18TherulereductionCD规则abde110Null120NullNull03Null1104NullNull22事实上表3-18中每一条规则也可以用类似模糊规则的IF-THEN语句表示如规则1可以表示为IFais1ANDbis0THENeis1如2.3中所述规则约简后得到的规则集合为系统的知识模型简称系统模型记为M设M中的一条规则r形如ÙGx®ÙDx称Gx为该规则的前件记为rA称Dx为该规则的后件记为rC又设系统S的一个输入为一向量s=[v1v2vm]经69 上海交通大学博士学位论文过数据扩展和离散化后得到s'=[v'1v'2v'(m+n)k+m]再将s'转换为属性和属性值对的集合的形式即(s')={(x1v'1)(x2v'2)(x(m+n)k+mv'(m+n)k+m)}这里(xivi)中xi和vi分别为条件属性和相应的条件属性值i=1(m+n)k+m在本文中对于规则r如果rAÍ(s')成立则称s同规则r匹配成功且rC为M相对s的输出此时rC仍为一属性和属性值对的集合系统模型M的这种输出形式还不能满足要求需要采取一定方法加以转换即将rC转换为向量的形式这里给出转换方法设系统模型M输出的属性和属性值对集合rC={(a1v1)(anvn)}其中a1an为决策属性也即系统的输出v1vn为相应决策属性的值则转换后的输出向量为Y=[v1v2vn]其中若ai(i=1n)为连续属性则vi为离散化以后的值即子区间的代表符号此时需进一步将vi转换为相应子区间中的某个真实值实质上这个转换过程是离散化的逆过程通常可以称为清晰化本文中用vi所代表的子区间的中值来代替vi即设vi所表的子区间为[ab]区间左右的开闭情况并不影响问题的讨论则用(a+b)/2代替vi关于清晰化方法的研究不属于本文的讨论范围并且清晰化方法同离散化方法不同并不影响系统模型的获得故不做详细介绍在下文中如不特别指出系统模型的输出都是指经过转换后的输出2.11知识推理如前所述粗糙集知识建模方法中假设系统S的特性完全可以由有限次测量后得到的测量值组成的矩阵来表征但是在实际应用中该假设条件并不能总是得到完全满足这有可能导致系统模型M的有效性受到限制对此可以通过知识推理加以解决从而提高模型的有效性在实际应用中用系统的输入数据s同系统模型M中规则进行依次匹配时有可能出现下述情况相应地本文提出了需要采取的不70 上海交通大学博士学位论文痂的处理方法，即知识推理策略，用来确定模型的最终输出。(1)S同M中唯一条规则，匹配成功模型M相对S的输出即为模型的最终输出。(2)S同M中多条规则匹配成功设规则的集合RGM，s同任意的规则，∈R都可以匹配成功，且月。{，】⋯．，7删)，其中r，(卢1⋯．，吲)的后件用前述的模型输出形式转换方法转换后为向量毕[v，lvd⋯v。]，”等于系统输出变量个数，且一中的离散化值都经过了清晰化。模型最终的输出为向量仁[Vl也⋯v。]，其中，吁=Ⅵ1(vu，吩⋯．，’，j劝，j=l⋯．，"。这里w(·)是个多元函数，该函数可以有不同形式，本文的验证实验中采用了平均值函数的形式，即!R}Zvij”，”(vU一。，”吲／)2莆(3)S同M中任何规则都不能匹配成功对任意的，eM，本文定义S同r的匹配度为五(，，。)：坚!型rA显然，^(，，J)∈[0，1]。如果s同r匹配成功，贝lJA(r，s)=1，硼lJ2(r，∞是一个五元组其中U是称为论域的非空有限集合C是条件属性的非空有限集合D是决策属性的非空有限集合CÈD=ACÇD=Æ79 上海交通大学博士学位论文fUAV是一个信息函数且对任意的aÎAxÎU有f(xa)ÎVaC'ÍC称C'是决策表DT的条件属性约简当且仅当C'是D—精简的并且POSC'(D)=POSC(D)C'是D—精简的是指对任意的aÎC'a是C'中D—不可略的即对任意的aÎC'POSC'-{a}(D)¹POSC(D)事实上对于C的任意子集的P和Q若PÍQ则POSP(D)ÍPOSQ(D)因此C'是D—精简的等价于对于任意的C''ÌC'POSC'(D)¹POSC''(D)即C'是D—精简的等价于不存在C''ÌC'使得POSC'(D)=POSC''(D)于是可以说C'(C'ÍC)是决策表DT的条件属性约简当且仅当POSC'(D)=POSC(D)并且不存在C''C''ÌC'使得POSC''(D)=POSC(D)条件属性约简的这种定义同前面的定义是等价的设GÍCxÎU并且I[x]CÍI[x]D称Gx是x的条件属性值约简当且仅当I[x]GÍI[x]D并且G在I[x]G中是I[x]D—独立的G在I[x]G中是I[x]D—独立的是指对任意的aÎGI[x]G-{a}ÍI[x]D都不成立即不存在G'G'ÌG使得[x]G'Í[x]D成立因此可以说Gx是x的条件属性值约简当且仅当I[x]GÍI[x]D并且不存在G'G'ÌG使得[x]G'Í[x]D成立条件属性值约简的这种定义同前面定义也是等价的在下面相关的证明中采用了上述条件属性约简和条件属性值约简的等价定义设RDÍRule(U)称RD为决策表DT的规则约简当且仅当对任意的xÎURDÇRule(x)¹Æ并且对任意的RD'ÌRDRD'ÇRule(x)¹Æ不成立设论域为U¹Æ给定集合XÍU和集族A={S1S2...Sm}其中SiÍUi=1...m且有UA=USi若UAÊX成立则称A是X的覆盖若不存在A'ÌA使得SÎAiA'是X的覆盖则称A是X的极小覆盖显然A是X的极小覆盖包含两个含义80 上海交通大学博士学位论文1A是X的覆盖2A的任何真子集都不是X的覆盖设A为一集族S为一集合若对任意的aÎS存在唯一的AaÎA与之对应并且A中任意的集合也都对应S中唯一的元素则称S为A的指标集显然S同A之间存在一一对应的关系3.2.2条件属性约简同集合极小覆盖的等价性在决策表DT=(UCDVf)中对任意的PÍC定义集合XP={(xy)ÎU´UxÎPOSP(D)}定义集族AP={SaaÎP}其中Sa=IND(a)UIND(D)这里符号X表示集合X的绝对补集即X所属论域同X的差集可以证明下列命题命题3.1对任意的PÍC和RÍCPOSP(D)=POSR(D)当且仅当XP=XR命题3.2对任意的PÍCXPÍIND(P)UIND(D)命题3.3对任意的PÍCUAP=IND(P)UIND(D)命题3.4对任意的PÍCAP是XP的覆盖命题3.5对任意的PÍCPOSP(D)=POSC(D)当且仅当AP是XC的覆盖命题3.6若C是AC的指标集对任意的PÍC和RÍCPÌR当且仅当APÌAR证明1根据定义XP={(xy)ÎU´UxÎPOSP(D)}显然命题3.1是正确的2设(x,y)ÎXP则xÎPOSP(D)根据POSP(D)的定义有[x]IND(P)Í[x]IND(D)若81 上海交通大学博士学位论文yÎ[x]IND(P)则yÎ[x]IND(D)即(xy)ÎIND(D)此时命题3.2成立若yÏ[x]IND(P)则(xy)ÎIND(P)命题3.2仍成立3因为UAp=USaaÎP=U(IND(a)UIND(D))aÎP=(UIND(a))UIND(D)aÎP=(IIND(a))UIND(D)aÎP=IND(P)UIND(D)故命题3.3成立4由命题3.2和命题3.3可以立即得到命题3.45分两部分证明先证明必要性Ü设xÎPOSC(D)因为AP是XC的覆盖XCÍUAp由XC的定义对任意的yÎU(xy)ÎXC成立即(xy)ÎUAP而由命题3.3有UAp=IND(P)UIND(D)故而(x•Cy)ÎIND(P)UIND(D)这表明若(xy)ÎIND(P)则必有(xy)ÎIND(D)也即[x]IND(P)Í[x]IND(D)因此xÎPOSP(D)进而POSC(D)ÍPOSP(D)由于PÍC故而POSP(D)ÍPOSC(D)是显然成立的于是POSP(D)=POSC(D)成立再证明充分性Þ因为POSP(D)=POSC(D)由命题3.3有XP=XC又根据命题3.4AP是XP的覆盖故而AP也是XC的覆盖82 上海交通大学博士学位论文6考虑到C是AC的指标集则命题3.6易证下面给出关于条件属性约简同集合极小覆盖的有条件等价的定理及其证明定理3.1若C是AC的指标集C'是属性约简当且仅当AC'是XC的极小覆盖证明分两部分证明先证明必要性Ü设AC'是XC的极小覆盖则根据命题3.5POSC'(D)=POSC(D)假设C'不是属性约简则存在C''ÌC'使得POSC''(D)=POSC(D)再由命题3.5知AC''也是XC的覆盖由命题3.6知AC''ÌAC'而这与AC'是XC的极小覆盖相矛盾故而假设不成立因此C'是属性约简再证明充分性Þ设C'是属性约简则根据定义有POSC'(D)=POSC(D)并且不存在C''ÌC'使得POSC''(D)=POSC(D)根据命题3.5知AC'是XC的覆盖并且不存在C''ÌC'使得AC''是XC的覆盖又根据命题3.6知AC''ÌAC'即不存在AC''ÌAC'使得AC''是XC的覆盖因此AC'是XC的极小覆盖3.2.3条件属性值约简同集合极小覆盖的等价性证明条件属性值约简同集合极小覆盖的等价性比证明条件属性约简同集合的极小覆盖的等价性要容易得多原因是条件属性约简需要同时考虑U中全部的元素而条件属性值约简只需要考虑U中的某一个元素这一点从两者的定义中可以看出在决策表DT=中对任意的xÎUPÍC定义集族x{[x]•FaP}•BAP=aÎx定理3.2对任意的xÎUC'ÍC若I[x]CÍI[x]D并且C是AC的指标集C'xx是x的条件属性值约简当且仅当AC'是[x]D的极小覆盖证明分两部分证明x先证明必要性Ü设AC'是[x]D的极小覆盖则83 上海交通大学博士学位论：必有亦即U。姑三k】DU《GMDn。《G[x]D同理，由于不存在彩，c蟛，使得《，是丽D的覆盖，同时C是《j的指标集，故而不存在C7'cC’，使得[X]c··c_G[X]D故而cj是x的条件属性值约简。再证明充分性(j)：设C二是值约简，则有故有网c·G[XlD[Xlc·三【X]D84 上海交通大学博士学位论文而=[]=[]x•C[x]C'IxaUxa=UAC'aÎC'aÎC'所以xÊ[x]•UAC'Dx即AC'是[x]D的覆盖同理因为C'x是值约简故不存在C''ÌC'使得[x]Í[x]•C''Dxxxxx即不存在AC''是[x]D的覆盖又因为C是AC的指标集所以AC''ÌAC'因此AC'是[x]D的极小覆盖3.2.4规则约简同集合极小覆盖的等价性对任意的rÎRule(U)定义集合IrÍUIr={xrÎRule(x)}对任意的RÍRule(U)定义集族AR={IrrÎR}定理3.3若Rule(U)是ARule(U)的指标集RD是决策表DT的规则约简当且仅当ARD是U的极小覆盖证明分两部分证明先证明必要性Ü设ARD是U的极小覆盖则UARDÊU那么对任意的xÎU存在IrÎARD且xÎIr根据Ir的定义知若xÎIr则rÎRule(x)又根据ARD的定义知若IrÎARD则rÎRD因此对任意的xÎUrÎRule(x)且rÎRD即rÎRule(x)IRD也即Rule(x)IRD¹Æ同理由于不存在ARD'ÌARD使得UARD'ÊU即不存在ARD'85 上海交通大学博士学位论文ÌARD对任意的xÎU使得Rule(x)IRD'¹Æ又因为Rule(U)是ARule(U)的指标集所以不存在RD'ÌRD对任意的xÎU使得Rule(x)IRD'¹Æ因此RD是决策表DT的规则约简再证明充分性Þ设RD是决策表DT的规则约简则对任意的xÎURule(x)IRD¹Æ成立即存在r使得rÎRD且rÎRule(x)即xÎIr且IrÎARD故xÎUARD所以UARÊU成立因此ARD是U的覆盖同理由于不存在RD'ÌRD对任意的xÎU使得Rule(x)IRD'¹Æ成立考虑到Rule(U)是ARule(U)的指标集则不存在ARD'ÌARD对任意的xÎU使得Rule(x)IRD'¹Æ成立即不存在ARD'ÌAR对任意的xÎU存在IrÎARD使得xÎIr亦即不存在ARD'ÌAR使得ARD'是U的覆盖故而ARD是U的极小覆盖3.2.5约简同集合极小覆盖的等价性的理论意义对约简同集合极小覆盖的等价性的研究的理论意义在于1这种等价性揭示了RS理论中这三种约简的内在联系2由于这种等价性的存在在其它领域中对集合极小覆盖问题的理论研究成果必然对RS理论中约简问题的进一步研究具有指导意义3由于这种等价性的存在在对RS理论中不同约简的算法的研究中可以借鉴已有的集合极小覆盖算法4这种等价性促使我们根据条件属性约简算法构造条件属性值算法和规则约简算法3.3条件属性约简算法[2-19]已有条件属性约简算法很多有代表性的算法主要有五种[2]1理论算法算法3.1[3]2基于属性粗糙度的算法算法3.2[7]3基于信息熵的算法算法3.386 上海交通大学博士学位论文[9]4基于属性频率的算法算法3.4[12]5基于属性序的算法算法3.5下面对这五种算法简要介绍然后给出三种新的属性约简算法3.3.1已有算法简介条件属性约简的理论算法的基本思路是首先求出条件属性集的幂集然后逐一判断该幂集中的元素是否是条件属性约简算法3.1理论算法1PÜÆ2求条件属性集C的幂集P(C)QÜP(C)3从Q任取一元素PQÜQ-{P}4如果POSP(D)=POSC(D)则PÜPU{P}5如果Q=Æ则算法结束P中所有元素都为条件属性约简否则转去执行3基于属性粗糙度的条件属性约简算法算法3.2的基本思路是在选择条件属性构成条件属性约简时根据条件属性的粗糙度确定选择的顺序设决策表DT=RÍCaÎC则条件属性a的粗糙度可以定义如下|POSRU{a}(D)-POSR(D)|Roughness(a•CR•CD)=•B|POSR(D)|基于信息熵的条件属性约简算法算法3.3的基本思路是在选择条件属性构成条件属性约简时根据条件属性的信息熵确定选择的顺序设决策表DT=QÍCUDRÍCUDU/IND(Q)={X1X2Xn}U/IND(R)={Y1Y2Ym}p(Xi)=|Xi|/|U|i=12np(Yi)=|Yj|/|U|j=12m定义R相对于Q的信息熵87 上海交通大学博士学位论文nmH(R|Q)=-åp(Xi)åp(Yj|Xi)log(p(Yj|Xi))•i=1j=1其中|YjIXi|p(Yj|Xi)=•Ci=1•C2•KCCn••Cj=1•C2•KC•Cm•B|Xi|设aÎCTÍC则属性a的信息熵可以定义如下Entropy(a•CT•CD)=H(D|T)-H(D|TU{a})•B算法3.3与算法3.2相比唯一的不同在于选择构成条件属性约简的条件属性时的标准不同算法3.2的选择属性粗糙度大的条件属性而算法3.3选择属性信息熵小的条件属性算法3.2和算法3.3求条件属性约简时都是以核即CORED(C)为出发点的在核的基础上不断地添加条件属性直至满足算法结束条件事实上也可以采用相反的方法即以条件属性的集合C为出发点不断地从中选择可以删除的条件属性加以删除直至满足算法结束条件此时选择的标准同算法3.2和算法3.3中相反的即选择属性粗糙度小的和属性信息熵大的条件属性在不同的情况下采用添加和删除方法的计算量是不同的基于属性频率的条件属性约简算法算法3.4的基本思路是选择条件属性构成条件属性约简时根据条件属性的属性频率确定选择的顺序设决策表DT=其差别矩阵为MDTM为任意一矩阵M中任意元素cijÍCaÎCa的属性频率p(aM)定义为a在M中出现的次数基于属性序的条件属性约简算法算法3.5的基本思路是先定义条件属性集上的一个全序关系然后根据该全序关系确定选择条件属性构成条件属性约简时的顺序全序关系的定义及使用方法比较复杂相关讨论可在文献[12]中找到[37912]算法3.2算法3.3算法3.4和算法3.5的描述可以在相关文献中找到88 上海交通大学博士学位论文这里也不再给出下面对上述5种算法做简要分析1从算法的时间复杂性角度考虑理论算法是指数复杂性的虽然该算法可以求出全部条件属性约简同时也可以求出最优的条件属性约简但是由于其复杂性使得该算法不具有实际意义其它四种算法都是多项式时间复杂性的具有实际意义2从算法的完备性角度考虑所谓算法是完备的是指该算法求得的结果P满足下面两个条件iPOSP(D)=POSC(D)ii对任意的aÎPPOSP-{a}(D)¹POSC(D)否则算法是不完备的这两个条件同下面两个条件是等价的i对任意的AÎMDTAIP¹Æii对任意的aÎP存在AÎMDT使得(P-{a})IA=Æ算法3.1和算法3.5是完备的而其它3个算法是非完备的对于这3个非完备的算法它们都是不满足完备性的条件ii这使得它们求得的结果P中有可能存在冗余的条件属性3从先验知识的角度考虑除算法3.5以外其它四个算法都是不考虑先验知识的算法3.5对先验知识的利用必须通过一个给定的全序关系来实现而在实际应用中定义一个全序关系是比较困难的因而算法3.5对先验知识的利用的局限性较大实际应用中所需的算法应该是多项式时间复杂性的完备的可以充分利用先验知识的算法根据上述分析可知已有算法并不能完全满足要求有必要对条件属性约简算法进行进一步研究下面本文提出了三种条件属性约简算法3.3.2条件属性约简算法已有算法在求得条件属性约简时或者以核为基础不断添加条件属性直至满足结束条件或者以全部条件属性为基础不断删除可以删除的条件属性直至满足89 上海交通大学博士学位论文结束条件本节给出的条件属性约简算法将这两种策略结合起来进行求解在给出算法前需要给出下列定义设决策表DT=DT的差别矩阵中非空集元素构成的集合称为DT的差别集记为ADT且有ADTÍP(C)P(C)是条件属性集C的幂集-定义3.1设AÍP(C)BÍCA的B—删除集A(B)={A'AÎAA'=A-B且A'¹Æ}+定义3.2设AÍP(C)BÍCA的B—选择集A(B)={AÎAAÇB=Æ}定义3.3设AÍP(C)aÎC若{a}ÎA则称a为A的必要属性并且称A的必要属性的集合为A的必要集记为ES(A)算法3.6条件属性约简的选择—删除算法ARSEA1PÜÆQÜÆTÜÆ2AÜADT3若A=Æ则算法结束P为条件属性约简4QÜES(A)5若Q=Æ则转6否则转86对任意的属性aÎC-(PUT)计算|ES(-({a})A)|7从C-(PUT)中选择使得|ES(-({a})-A)|最大的属性bAÜA({b})TÜTU{b}转3+8PÜPUQAÜA(P)转3算法3.6的流程图如图3-1所示在算法3.6中将全部条件属性的集合C被分成了三部分已经选择的条件属性集合P已经删除的条件属性集合T和备选条件属性集合C-(PUT)在算法开始时P=ÆT=Æ备选条件属性集为C在每次迭代过程中算法都要判断是否存在必90 上海交通大学博士学位论文图3-1算法3.6流程图Fig.3-1TheflowchartofAlgorithm3.6要属性如果存在必要属性则选择所有必要属性放入P中如果不存在必要属性则需要从备选条件属性集中删除一个条件属性在删除过程中算法使得删除91 上海交通大学博士学位论文某条件属性后在下次迭代中出现的必要属性最多若可以删除的条件属性不是唯一的则任选一个算法3.6的执行过程可以用表3-1中决策表加以说明表3-1决策表Table3-1AdecisiontableCDUabcdex112311x221232x333313x411124x512235x621316x722137表3-1中决策表DT中U={x1x2x3x4x5x6x7}C={abcd}D={e}ADT={{abcd}{ab}{bcd}{cd}{acd}{bc}{abd}{ac}}算法3.6第一次执行到6步时A=A-DT|ES(A({a}))|=|{bc}|=2|ES(-({b})--A)|=|{ac}|=2|ES(A({c}))|=|{abd}|=3|ES(A({d}))|=|{c}|=1所以此时算法选择c则A={{abd}{ab}{bd}{d}{ad}{b}{a}}T={c}接着在下次迭代中算法执行第8步则P={abd}A=Æ然后算法执行第3步算法结束为了对算法3.6的性能进行验证分别采用了两种类型的数据随机数据和通用数据一随机数据验证实验用随机数据验证时为了考察不同数据量的情况下算法3.6的性能进行了三组实验每组实验中包括50个随机决策表对第一组实验每个随机决策表中|U|=2092 上海交通大学博士学位论文|C|=4|D|=1对第二组实验每个随机决策表中|U|=100|C|=9|D|=1对第三组实验每个随机决策表中|U|=500|C|=14|D|=1产生随机决策表时只需先利用大多数高级编程语言都提供的伪随机函数产生|U|´(|C|+|D|)个伪随机数然后按照行优先的排列方法排成|U|行(|C|+|D|)列即可对所产生的随机决策表的所有属性进行等区间离散化离散化后的每个属性有10个属性值对每组实验先使用理论算法对每个随机决策表进行处理求得其所有条件属性约简然后分别用算法3.2算法3.3算法3.4和算法3.6进行处理设决策表的全部条件属性约简的集合为R上述四个算法中任意一个对该决策表的处理结果为P给出下面四个定义定义3.4若不存在RÎR使得RÍP成立则称P是错误的定义3.5若存在RÎR使得RÌP成立则称P是近似的定义3.6若RÎR则称P是正确的定义3.7若RÎR并且不存在RÎRR¹P使得RÌP成立则称P是最优的根据上述定义可以分别用错误率错误的P的个数同决策表的总数的比值近似率近似的P的个数同决策表的总数的比值正确率正确的P的个数同决策表的总数的比值和最优率最优的P的个数同决策表的总数的比值四个指标来衡量不同的算法的性能实验结果如表3-2所示由表3-2可知当数据量很小时第一组算法3.6的性能同其它三种算法的性能相近数据量增大时第二组算法3.6在近似率和正确率这两个指标上已经明显优于算法3.4而同算法3.2和算法3.3相差不多但在最优率这一指标上算法3.6明显优于其它三种算法当数据量进一步增大时第三组在近似率和正确率这两个指标上算法3.6略优于算法3.2和算法3.3明显优于算法3.4在最优率这一指标上算法3.6仍明显优于其它三种算法图3-2同时随着数据量的增大算法3.6的正确率始终为100%而其它三种算法的正确率都呈下降趋势图3-393 上海交通大学博士学位论文算法3.6的正确率能够保持100%是因为该算法的完备性对此将在下面部分中进行理论上的证明表3-2实验结果Table3-2Resultsofexperiments算法3.2算法3.3算法3.4算法3.6错误率%0000第近似率%0060一正确率%10010094100组最优率%989686100错误率%0000第近似率%410460二正确率%969054100组最优率%2842654错误率%0000第近似率%1416600三正确率%868440100组最优率%4650474%Algorithm3.2Algorithm3.3Algorithm3.4percentageAlgorithm3.6ptimalOGroup图3-2不同数据量时不同算法的最优率Fig.3-7Theoptimalpercentageofdifferentalgorithmswithdifferentdataquantity94 上海交通大学博士学位论文%Algorithm3.2Algorithm3.3Algorithm3.4Algorithm3.6CorrectpercentageGroup图3-3不同数据量时不同算法的正确率Fig.3-8Thecorrectpercentageofdifferentalgorithmswithdifferentdataquantity本文没有对更大数据量的数据进行实验原因是在第三组实验中使用理论算法处理一个决策表所需要的时间已经接近60分钟再加大数据量是已经没有实际意义了此外本文没有使用算法3.5进行实验原因是无法为该算法定义合适的全序关系二通用数据验证实验所谓通用数据是指UCI数据库中的数据这些数据是国际上共享的专门用于验证机器学习算法的数据本文从UCI数据库中选择了两个数据文件第一个数据文件记录了1984年美国国会民主和共和两党对不同议案投票情况组织成决策表后|U|=435|C|=16|D|=1所有属性都有两种取值但其中包括用表示的缺失的数据在实验中将缺失数据单独作为一种取值处理即实验中属性取值扩展为3个而不是原来的2个表3-3中是实验结果表中数字表示条件属性序号第二个数据文件记录一些动物园动物的数据组织成决策表后|C|=101|C|=17|D|=1全部的条件属性都有两种取值而决策属性有7种取值表3-4中是实验结果根据表3-3可知算法3.6并不比算法3.2和算法3.3差但是比算法3.4要好根据表3-4可知算法3.6不比算法3.3差但是比算法3.2和算法3.4要好根据随机数据和通用数据的验证实验可以得出这样的结论即算法3.6在特定情况下具有比算法3.2算法3.3和算法3.4更好的性能但是进一步分析可知95 上海交通大学博士学位论文表3-3实验结果1Table3-3Experimentresults1条件属性约简结果{1234911131516}理论算法{12346911131416}{12367910111213141516}算法3.2{1234911131516}算法3.3{1234911131516}算法3.4{123456789101112131416}算法3.6{1234911131516}表3-4实验结果2Table3-4Experimentresults2条件属性约简结果理论算法{346813}{346913}{3681013}共求得了33种条件属性约简{13681113}结果表中只列出部分{461011131415}算法3.2{469111316}算法3.3{4591213}算法3.4{135678910131416}算法3.6{3691316}算法3.6的时间复杂性比其它三种算法略大并且可知导致算法3.6的时间复杂性略大的原因是其第6步的操作即在选择一个条件属性删除时需要对所有备选条件属性进行计算算法3.7在这方面做了改进96 上海交通大学博士学位论文图3-4算法3.7流程图Fig.3-4TheflowchartofAlgorithm3.7算法3.7条件属性约简的随机选择—删除算法ARRSEA1PÜÆQÜÆTÜÆ2AÜADT3若A=Æ则算法结束P为条件属性约简4QÜES(A)5若Q=Æ则转6否则转797 上海交通大学博士学位论文6从C-(PUT)中随机选择一属性aAÜ-({a})ATÜTU{a}转37PÜPUQAÜ+(P)A转3算法3.7的流程图如图3-4所示可见算法3.7在删除的条件属性时被删除的条件属性是从备选条件属性集中随机选择的从而降低了算法的时间复杂性同时算法3.7同算法3.6一样具有的完备性算法3.7的3到7步构成了一个循环体由于算法3.7在经过有限步后必然结束是显然的故而设算法3.7运行过程中执行了k次循环即迭代了k次其中kÎZ且k³0在某次迭代中如果执行了第6步则称该次迭代为删除迭代否则执行了第7步则称该次迭代为选择迭代算法运行中用序列A0A1...Ai...Ak-1Ak表示A的变化情况其中Ai-1和Ai分别表示第i次迭代前和后A的取值第0次迭代除外且A0=ADTAk=Æ类似地用序列R0R1...Ri...Rk-1Rk表示R的变化情况并用序列T0T1...Ti...Tk-1Tk表示T的变化情况其中R0=ÆRk=RT0=Æ且若i£j则RiÍRjTiÍTj需指出C-R=T并不总成立命题3.7若第i次迭代是删除迭代则对任意的AÎAi-1存在A'ÎAi使得A'ÍA命题3.8若第i次迭代是选择迭代则对任意的AÎAi-1若AÏAi则AIRi¹Æ命题3.9对任意的AÎAi-1若不存在A'ÎAi使得A'ÍA则AIRi¹Æ命题3.10对任意的AÎAi若不存在A'ÎAj使得A'ÍA则AIRj¹Æ其中0£i0则R0=ÆA0=ADT98 上海交通大学博士学位论文Rk=RAk=Æ对任意的AÎADT有AÎA0而Ak=Æ即不存在A'ÎAk使得A'ÍA由命题3.10知AIRk¹Æ即AIR¹Æ故而定理3.4成立证毕命题3.11对任意的AÎAii=1k存在A'ÎA0使得AÍA'并且A'-AÍTi命题3.12TIR=Æ易证命题4.11和命题4.12定理3.5ADT是算法3.7的输入R是算法的输出则对任意的aÎR存在AÎADT使得AIR-{a}=Æ证明设算法迭代了k次若k=0定理3.5成立若k>0则R0=ÆA0=ADTRk=RAk=Æ对任意的aÎR必存在0的极小元的集合称为它的极小集记为ME(AR)算法3.8条件属性约简的偏序集选择—删除算法ARPSEA1PÜÆQÜÆ99 上海交通大学博士学位论文图3-5算法3.8流程图Fig.3-5TheflowchartofAlgorithm3.82AÜADT3若A=Æ则算法结束P为条件属性约简4QÜES(A)5若Q=Æ则转6否则转76从-ME(AR)中随机选择一个属性aAÜA({a})转4100 上海交通大学博士学位论文7PÜPUQAÜ+(P)A转4算法3.8的流程图如图3-5所示可见算法3.8同算法3.7的唯一区别在于第6步在算法3.7中被删除的条件属性是选自C-(PUT)的而在算法3.8中被删除的条件属性是选自ME(AR)的表3-5执行过程Table3-5TheexecutiveprocesskAPAttributeselected{{abd}{acd}{bcd}{ab0Æc}{ef}}1{{bd}{cd}{bcd}{bc}{ef}}Æa2{{d}{cd}{c}{ef}}Æb3{{ef}}{cd}4{{f}}{cd}e5Æ{cdf}设决策表DT=C={abcdef}ADT={{abd}{acd}{bcd}{abc}{ef}}定义C上的偏序关系R={