决策理论与方法教学第八章粗糙集决策.ppt

决策理论与方法 DecisionMakingTheoryandMethods 决策理论与方法 编写组 教育部高等学校管理科学与工程类学科专业教学指导委员会推荐教材 第八章粗糙集决策方法 学习目的 了解知识 等价类 上近似 下近似 粗糙集 属性约简和核的概念 掌握完备决策系统和不完备决策系统的属性约简及获取决策规则的方法 掌握基于优势关系和扩展优势关系的属性约简及获取决策规则的方法 本讲内容 粗糙集理论的基本概念完备决策系统的粗糙决策分析方法不完备决策系统的粗糙决策分析方法基于优势关系的粗糙决策分析方法基于扩展优势关系的粗糙决策分析方法 8 1粗糙集理论的基本概念 8 1 1知识与知识表示1 知识的含义粗糙集方法是将数据转化为知识的一种规范的方法 把知识视为分类的能力 定义8 1 1设是研究对象的有限集合 称为中的一个概念或范畴 中的一个概念族称为关于的知识 其中空集也认为是一个概念 定义8 1 2设是的一个等价关系 表示的所有等价类 我们用表示包含元素的的等价类 上的一族划分称为的一个知识库 一个知识库就是一个系统 记为其中为非空有限集 为上的一簇等价关系 2 知识的表示知识的表示通过知识表达系统来完成 知识表达系统可以表达为 其中为对象的集合 为属性的非空有限集合 为属性值域 是属性的值域 为信息函数 它为每个对象的每个属性赋予一个属性值当信息系统中属性其中为条件属性集 为决策属性集时 信息系统也称为决策系统 例8 1 1设决策系统如下表所示 对象为8部小汽车 条件属性 空间 颜色 价格 决策属性为销售量 在此决策系统中每个属性相当于一个等价关系 有等价关系得到的等价类为 8 1 2近似与粗糙集设为上的等价关系 当能表示为某些基本范畴并时 称是可定义集 否则称是不可定义集 可定义集是论域的子集 它可在知识库中精确地定义 而不可定义集不能在这个知识库中被定义 可定义集也称为精确集 ExactSets 而不可定义集也称为粗糙集 RoughSets 对于粗糙集可以近似地定义 我们使用粗糙集的 上近似和下近似来描述 定义8 1 3给定知识库对于每个子集和一个等价关系定义两个子集 分别称它们为的下近似和上近似 下近似和上近似也可以用下面的等式表达 分别称为的边界域 正域和负域 从上述定义 可得到下近似和上近似的性质 1 2 3 3 4 5 6 7 X粗糙集的概念可以用下面的示意图来表示 8 1 3近似精度与粗糙度定义8 1 4设集合是论域上一个关于的粗糙集 定义的近似精度和粗糙度分别为 近似精度反映根据现有知识对的理解程度 显然当时 集合相对于是精确的 当时 集合相对于是粗糙的 8 1 4属性的重要性 属性约简和核1 属性的重要性定义8 1 5设有决策系统其中分别为条件属性集和决策属性集 则决策属性在条件属性下的正域 简称的正域 定义为的正域是中通过用分类表达的知识能够确定地划入类的对象集合 定义8 1 6决策属性对条件属性的依赖度定义为依赖度表示在条件属性集下能够确切划入决策分类的对象占论域中的总对象数的比率 表达了决策属性对条件属性的依赖程度 定义8 1 7设有决策系统其中分别为条件属性集和决策属性集 属性子集的属性重要度定义为 特别当时 属性关于的重要性为2 属性约简属性约简是粗糙集理论中的核心内容之一 决策表中的属性并不是同等重要的 甚至有些属性是冗余的 所谓属性约简 就是保持决策表条件属性 和决策属性之间的依赖关系不发生变化的前提下 删除其中不相关的或不重要的属性 定义8 1 8对于一给定的决策系统若则称属性为中可省略 否则属性为中不可省略的 定义8 1 9对于一给定的决策系统 条件属性集的约简是的一个非空子集 若满足 1 都是不可省略的 2 则称是的一个约简 中所有约简的集合记作 中所有不可省略属性的集合称的核 记为8 1 5决策规则和算法决策表中的每一个对象都可以看作是一条决策规则 因此 决策表实际上是一组逻辑规则的组合 定义8 1 10在逻辑语言中 蕴含称为决策逻辑语言中的决策规则 和分别称为决策规则的前件和后件 定义8 1 11形式化定义其中且称为基本公式 定义8 1 12当为一个决策规则时 且和分别为基本公式和基本公式 时 则 决策规则称为基本决策规则 定义8 1 18当且仅当对于中任何一决策规则蕴含时 则决策算法中的决策规则是中相容的 否则是不相容的 定义8 1 19如果一个决策表中所有的决策规则都是相容的 则决策表是相容的 否则是不相容的 定义8 1 20任何一个决策系统可以看做是一组 if then 的决策规则 当条件能唯一确定决策时 该条规则为确定性决策规则 否则为不确定性决策规则 定义8 1 21在决策系统中 和分别代表与中各等价类 表示对等价类的描述 表示对等价类的描述 决策规则为 该规则的确定性因子为 当是确定性规则 当是不确定性规则 8 1 6算例分析考察下面决策系统进行属性约简及获取决策规则 表8 1 2决策表 我们可以算出 所以是条件属性集的约简 确定性决策规则有 不确定性决策规则有 且各不确定性决策规则的确定性因子均为0 5 8 2不完备决策系统的粗糙决策分析方法 8 2 1不完备决策系统定义8 2 1不完备决策系统对象集合为 为属性集合 为属性值集且 其中是条件属性值集 是决策属性值集 为一个信息函数 表示对每一个如果至少有一个中包含空值 则称为不完备决策系统 在不完备决策系统中 用 表示空值 定义8 2 2给定不完备决策系统假定对象在下的二元关系定义为 令表示对象集合为属性下与可能不可区分的最大对象集合 表示对象集合为属性下与可能可区分的最大对象集合 表示 分类 中的任何元素称为相容类 定义8 2 3假设在相容关系下的下近似和上近似分别定义为集合称为在相容关系下的边界域 有上述定义可以得到在下的下近似和上近似的下列性质 定理8 2 1如果则有 1 2 3 4 8 2 2属性约简与决策规则获取定义8 2 4给定不完备决策系统假定函数为称为中的广义决策函数 其中表示的幂集 定义8 2 5设若满足下列条件 则称为的约简 记为 决策规则的获取 令是具有性质 其中 的对象集 令是具有性质 其中 的对象集 在不完备决策系统中 决策规则为真 当且仅当其中是出现在规则的条件部分的所有属性构成的集合 若决策规则是最优的当且仅 当该规则为真且由出现在中的和取与析取的真子集构成任何规则均为假 8 2 3实例分析考察下面一个关于汽车性能综合评判的不完备决策系统 找出属性约简及决策规则 从表中得到 Size Max Speed 是上表描述的决策系统的一个约简 并得到下面三个决策规则 Max Speed Low d good Size compact d poor Size full d good d excel 8 3基于优势关系的粗糙决策分析方法 经典的粗糙集方法是通过不可分辨关系来实现知识的获取 对有偏好信息的多属性决策问题是不适用的 为此Greco等学者提出了用优势关系代替不可分辨关系较好地解决了有偏好信息的决策问题 该方法将决策者的偏好信息以知识的形式表现出来 通过决策规则来实现分类 8 3 1基于优势关系的粗糙近似设为在论域上关于准则的优势关系 即对于表示对于准则不劣于类似地 严格优势关系表示对于准则比绝对优 记为 此外 设为上的决策类集合 使得任一属于一个类且仅属于一个类假设对所有的如果 则的任一元素均比的所有元素优 严格优 或不严格优 定义8 3 1决策类的上并集和下并集分别定义为其中 则意味着至少属于类别意味着至多属于类别 显然中的每一个对象优于或至少等于中的每一个对象 并且有 定义8 3 2如果对于所有的有成立 则称关于准则集支配记为定义8 3 3设则分别称为的优势集和被优势集 定义8 3 4给定集合的下近似和上近似分别定义为 类似地的下近似和上近似分别定义为 和的边界域分别定义为 对所有和上述定义的下近似和上近似满足下列性质 定理8 3 1 1 2 3 4 5 6 定义8 3 5对所有和和的近似精度分别为 定义8 3 6决策类集合在优势关系下关于准则集合的近似质量定义为 简称分类质量 利用性质和定义8 3 6我们可以得到分类质量的另外一种形式 定义8 3 7满足的最小子集称为关于的一个约简 记为 一个具有偏好信息的完备决策系统可能不止一个属性约简 所有属性约简的交集称为属性的核 记为 8 3 2决策规则先计算决策系统的属性约简 然后由优势关系下 粗糙集的下近似可得到确定性的偏好决策规则 包括决策规则和决策规则这两部分 由优势关系下粗糙集边界域可得到可能性的偏好决策规则 即决策规则 1 决策规则If且且 且Then 其中 且这类规则被的下近似的所有对象支持 决策规则If且且 且then 其中且这类规则被的下近似的所有对象支持 决策规则If且且 且且且且 且then其中和可能相交 且满足这类规则被和的边界域的所有对象支持 8 3 3应用实例考察下面一个关于学生综合评判的完备信息的多属性决策系统 找出属性约简及决策规则 决策类关于条件属性集的分类质量为 根据属性约简的定义可以得到属性为该决策系统的属性约简 由于边界域和均为空集 我们可以得到下面两条确定性决策规则 ifif 8 4基于扩展优势关系的粗糙决策分析方法 对于信息不完全的偏好多属性决策问题 本节将严格意义上的优势关系条件放宽 提出了扩展优势关系 从而获得粗糙集中的近似 获取决策规则 8 4 1不完全信息的偏好多属性分类问题定义8 4 1设决策系统为非空属性集合 分别为条件属性集和决策属性集 是属性值集 分别为条件属性值集和决策属性值集 并且和具有偏好次序 是一个信息函数 表示对于每一个如果某些条件属性值取空值 用 表示 并假定决策属性值没有空值 称为不完全信息的偏好多属性决策系统 现要求对不完全信息的多属性决策系统进行分类 假设决策属性把论域分成有限的类 则对象中的任一 属于一个且仅属于假定这种分类是有序的 即对于所有的如果则中的对象优于中的对象 定义8 4 2决策类的向上累集和向下累集分别为其中 则意味着至少属于类别意味着至多属于类别 由定义显然可以得到下面的性质 8 4 2基于扩展优势关系的粗糙近似定义8 4 3设定义扩展优势关系为或或 这时称 扩展优势于 记为 定义8 4 4对于 则分别称为的扩展优势集和扩展被优势集 定义8 4 5给定集合在优势扩展关系下的下近似和上近似分别定义 类似地的下近似和上近似分别定义和的边界域分别定义为 其中即要求每个对象至少有一个非空属性 定义8 4 6决策类集合在扩展优势关系下关于准则集合的近似质量定义为简称分类质量 定义8 4 7满足的最小子集称为关于的一个约简 记为 一个决策系统可能不止一个属性约简 所有属性约简的交集称为属性的核 记为 8 4 3决策规则由扩展优势关系下粗糙集的下近似可得到两条确定性的偏好决策规则 包括决策规则和决 策规则这两部分 由扩展优势关系下粗糙集边界域可得到可能性的偏好决策规则 即决策规则 1 由得到决策规则 If且且 且Then 其中且 这类规则在扩展优势关系下被的下近似的所有对象支持 2 由可得决策规则 If且且 且Then 其中且 这类规则在扩展优势关系下被的下近似的所有对象支持 3 由可得决策规则 If且且 且且且且 且then 其中和可能相交 且满足 这类规则在扩展优势关系下被和的边界域的所有对象支持 8 4 3应用实例考察下面一个关于学生综合评判的不完备信息的多属性决策系统 找出属性约简及决策规则 决策类关于条件属性集的分类质量为 根据属性约简的定义可以得到属性为该决策系统的属性约