第八章 粗糙集决策方法

决策理论与方法（DecisionMakingTheoryandMethods）《决策理论与方法》编写组教育部高等学校管理科学与工程类学科专业教学指导委员会推荐教材《决策理论与方法》第2页第2页第八章粗糙集决策方法《决策理论与方法》第3页第3页学习目的了解知识、等价类、上近似、下近似、粗糙集、属性约简和核的概念；掌握完备决策系统和不完备决策系统的属性约简及获取决策规则的方法；掌握基于优势关系和扩展优势关系的属性约简及获取决策规则的方法。《决策理论与方法》第4页第4页本讲内容粗糙集理论的基本概念完备决策系统的粗糙决策分析方法不完备决策系统的粗糙决策分析方法基于优势关系的粗糙决策分析方法基于扩展优势关系的粗糙决策分析方法《决策理论与方法》第5页第5页8.1粗糙集理论的基本概念8.1.1知识与知识表示1.知识的含义粗糙集方法是将数据转化为知识的一种规范的方法,把知识视为分类的能力。定义8.1.1设是研究对象的有限集合，称为中的一个概念或范畴,中的一个概念族称为关于的知识，其中空集也认为是一个概念。UUXUUnXXXF,,,21U,,iiXUX,jiXXji,,,2,1,nji,UXi《决策理论与方法》第6页第6页定义8.1.2设是的一个等价关系，表示的所有等价类，我们用表示包含元素的的等价类。上的一族划分称为的一个知识库。一个知识库就是一个系统，记为其中为非空有限集，为上的一簇等价关系。RUnXXXRU,,,21RRx][xRUU),,(RUKURU《决策理论与方法》第7页第7页2.知识的表示知识的表示通过知识表达系统来完成。知识表达系统可以表达为:其中为对象的集合；为属性的非空有限集合；为属性值域，是属性的值域；为信息函数，它为每个对象的每个属性赋予一个属性值当信息系统中属性其中为条件属性集，为决策属性集时，信息系统也称为决策系统。S),,,,(fVAUSnxxxU,,,21AV,aAaVVaVaVAUf:,DCACD《决策理论与方法》第8页第8页例8-1-1设决策系统如下表所示，对象为8部小汽车，条件属性：空间、颜色、价格；决策属性为销售量1c2c3cd《决策理论与方法》第9页第9页在此决策系统中每个属性相当于一个等价关系，有等价关系得到的等价类为：827365411,,,,,,,/xxxxxxxxcU638527412,,,,,,,/xxxxxxxxcU765843213,,,,,,,/xxxxxxxxcU76538241,,,,,,,/xxxxxxxxCU67382541,,,,,,,/xxxxxxxxdU《决策理论与方法》第10页第10页8.1.2近似与粗糙集设为上的等价关系，当能表示为某些基本范畴并时，称是可定义集；否则称是不可定义集。可定义集是论域的子集，它可在知识库中精确地定义，而不可定义集不能在这个知识库中被定义。可定义集也称为精确集(ExactSets),而不可定义集也称为粗糙集（RoughSets)。对于粗糙集可以近似地定义，我们使用粗糙集的,UXRUXRXRRRRRR《决策理论与方法》第11页第11页上近似和下近似来描述。定义8.1.3给定知识库对于每个子集和一个等价关系定义两个子集：分别称它们为的下近似和上近似。下近似和上近似也可以用下面的等式表达：,KUX,RXYRUYXR/)(XYRUYXR/)(XRR《决策理论与方法》第12页第12页分别称为的边界域、正域和负域。从上述定义，可得到下近似和上近似的性质：(1)(2)(3),][)(XxUxXRRXxUxXRR][)(),()()(XRXRXBNR)()(XRUXNEGR),()(XRXPOSRXRRR)()(XRXXR),()(RR)()(URXUR，)()()(YRXRYXR),()()(YRXRYXR《决策理论与方法》第13页第13页(3)(4)(5)(6)(7)X粗糙集的概念可以用下面的示意图来表示：),()()(YRXRYXR),()()(YRXRYXR)()()(YRXRYXR),()(YRXRYX()()RXRY),()(XRXR)()(XRXR),())(())((XRXRRXRR)())(())((XRXRRXRR)()()(YRXRYXR《决策理论与方法》第14页第14页《决策理论与方法》第15页第15页8.1.3近似精度与粗糙度定义8.1.4设集合是论域上一个关于的粗糙集，定义的近似精度和粗糙度分别为：近似精度反映根据现有知识对的理解程度。显然当时，集合相对于是精确的，当时，集合相对于是粗糙的。,1)(0XRXURXR,)()()(XRXRXR)(1)(XXRRX1)(XRXRXR1)(XR《决策理论与方法》第16页第16页8.1.4属性的重要性、属性约简和核1.属性的重要性定义8.1.5设有决策系统其中分别为条件属性集和决策属性集，则决策属性在条件属性下的正域（简称的正域）定义为的正域是中通过用分类表达的知识能够确定地划入类的对象集合。),,,,(fVDCUSDC,DC)()(/XCDPOSDUXCDCDCCU/DU/《决策理论与方法》第17页第17页定义8.1.6决策属性对条件属性的依赖度定义为依赖度表示在条件属性集下能够确切划入决策分类的对象占论域中的总对象数的比率，表达了决策属性对条件属性的依赖程度。定义8.1.7设有决策系统其中分别为条件属性集和决策属性集，属性子集的属性重要度定义为DCUDPOSDkCC)()(DU/),,,(fVDCUSDC,CC《决策理论与方法》第18页第18页特别当时，属性关于的重要性为2.属性约简属性约简是粗糙集理论中的核心内容之一，决策表中的属性并不是同等重要的，甚至有些属性是冗余的，所谓属性约简，就是保持决策表条件属性)()()(,DDCCCCDCaCCaD)()()(,DDaaCCDC《决策理论与方法》第19页第19页和决策属性之间的依赖关系不发生变化的前提下,删除其中不相关的或不重要的属性。定义8.1.8对于一给定的决策系统若则称属性为中可省略，否则属性为中不可省略的。定义8.1.9对于一给定的决策系统，条件属性集的约简是的一个非空子集。若满足),,,,(fVDCUS)()(DPOSDPOSaCCCDaaCDCDCP《决策理论与方法》第20页第20页（1）都是不可省略的（2）则称是的一个约简。中所有约简的集合记作，中所有不可省略属性的集合称的核，记为8.1.5决策规则和算法决策表中的每一个对象都可以看作是一条决策规则。因此，决策表实际上是一组逻辑规则的组合。,PaaD)()(DPOSDPOSCPPCC)(CREDDCC)(CCORED《决策理论与方法》第21页第21页定义8.1.10在逻辑语言中，蕴含称为决策逻辑语言中的决策规则，和分别称为决策规则的前件和后件。定义8.1.11形式化定义其中且称为基本公式。定义8.1.12当为一个决策规则时，且和分别为基本公式和基本公式，时，则),,(),(),(2211nnvavava,iaiVv,,,,21Paaan,APPCDADC,《决策理论与方法》第22页第22页决策规则称为基本决策规则。定义8.1.18当且仅当对于中任何一决策规则蕴含时，则决策算法中的决策规则是中相容的，否则是不相容的。定义8.1.19如果一个决策表中所有的决策规则都是相容的，则决策表是相容的，否则是不相容的。定义8.1.20任何一个决策系统可以看做是一组“ifCD),(DCCD,,CDCDS《决策理论与方法》第23页第23页…then…”的决策规则，当条件能唯一确定决策时，该条规则为确定性决策规则，否则为不确定性决策规则。定义8.1.21在决策系统中，和分别代表与中各等价类。表示对等价类的描述，表示对等价类的描述。决策规则为：),,,(fVDCUSiXjYCU/DU/)(iXdexiX)(jYdexjY),()(iiYdexXdexjiYX《决策理论与方法》第24页第24页该规则的确定性因子为：当是确定性规则；当是不确定性规则。8.1.6算例分析考察下面决策系统进行属性约简及获取决策规则。iijjiXXYYX),(1),(jiYX1),(0jiYX《决策理论与方法》第25页第25页表8-1-2决策表《决策理论与方法》第26页第26页我们可以算出：所以是条件属性集的约简。4321,,,)(xxxxDPOSC)(,,)(4211DPOSxxxDPOSCcC)(,,,)(43212DPOSxxxxDPOSCcC)()(3DPOSDPOSCcC)(,)(41,21DPOSxxDPOSCccC)()(23,DPOSDPOSCccC31,ccCD《决策理论与方法》第27页第27页确定性决策规则有：不确定性决策规则有：且各不确定性决策规则的确定性因子均为0.5。);0,()1,()1,(31dcc);1,()2,()1,(31dcc);1,()3,()1,(31dcc);0,()1,()0,(31dcc)0,()2,()0,(31dcc);1,()2,()0,(31dcc);1,()3,()0,(31dcc)0,()3,()0,(31dcc《决策理论与方法》第28页第28页8.2不完备决策系统的粗糙决策分析方法8.2.1不完备决策系统定义8.2.1不完备决策系统对象集合为；为属性集合，为属性值集且，其中是条件属性值集，是决策属性值集；为一个信息函数，表示对每一个如果至少有一个中包含空值，则称为不完备决策系统。在不完备决策系统中，用*表示空值。),,,,(fVAUSnxxxU,,,21)(DCAAVDCVVVCaVVaC:DdVVdD:VAUf:.),(,,aVaxfUxAaaVCa,S《决策理论与方法》第29页第29页定义8.2.2给定不完备决策系统假定对象在下的二元关系定义为:令表示对象集合为属性下与可能不可区分的最大对象集合;表示对象集合为属性下与可能可区分的最大对象集合。表示),,,,(fVAUSUyxCP,,P)(PSIM),(,),),(),(,),()(ayfaxfayfaxfPaUUyxPSIM或（或)(xSP)(),(PSIMyxUyPx)(xDP)(),(PSIMyxUyPxUxxSPSIMUP)()(/《决策理论与方法》第30页第30页分类，中的任何元素称为相容类。定义8.2.3假设在相容关系下的下近似和上近似分别定义为集合称为在相容关系下的边界域。)(/PSIMU,,CPUXX)(PSIMXxSUxXPP)()(XxSUxXPP)()()()()(XPXPXBNPX)(PSIM《决策理论与方法》第31页第31页有上述定义可以得到在下的下近似和上近似的下列性质。定理8.2.1如果则有（1）（2）（3）（4）)(PSIM,,,CPUYX)()(XPXXP),()(YPXPYX)()(YPXP),()()(YPXPYXP)()()(YPXPYXP),()()(YPXPYXP)()()(YPXPYXP《决策理论与方法》第32页第32页8.2.2属性约简与决策规则获取定义8.2.4给定不完备决策系统假定函数为称为中的广义决