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

1、决策理论与方法（ Decision Making Theory and Methods ）,决策理论与方法编写组,第八章 粗糙集决策方法,学习目的,了解知识、等价类、上近似、下近似、粗糙集、属性约简和核的概念； 掌握完备决策系统和不完备决策系统的属性约简及获取决策规则的方法； 掌握基于优势关系和扩展优势关系的属性约简及获取决策规则的方法。,本讲内容,粗糙集理论的基本概念 完备决策系统的粗糙决策分析方法 不完备决策系统的粗糙决策分析方法 基于优势关系的粗糙决策分析方法 基于扩展优势关系的粗糙决策分析方法,8.1粗糙集理论的基本概念,8.1.1知识与知识表示 1.知识的含义 粗糙集方法是将数据转化

2、为知识的一种规范的方法, 把知识视为分类的能力。 定义8.1.1 设 是研究对象的有限集合， 称为 中的一个概念或范畴, 中的一个概念族 称为关于 的知识，其中 空集也认为是一个概念。,定义8.1.2 设 是 的一个等价关系， 表示 的所有等价类 ，我们用 表示包含元素 的 的等价类。 上的一族划分称为 的一个知识库。一个知识 库就是一个系统，记为 其中 为非空有限 集， 为 上的一簇等价关系。,2. 知识的表示 知识的表示通过知识表达系统来完成。知识表达 系统 可以表达为: 其中 为对象的集合； 为属性的非空有限集合； 为属性值 域， 是属性 的值域； 为信息 函数，它为每个对象的每个属性赋

3、予一个属性值 当信息系统中属性 其中 为条件属性集， 为决策属性集时，信息系统也称为决策系统。,例8-1-1 设决策系统如下表所示，对象为8部小汽车，条件 属性： 空间、 颜色、 价格；决策属性为销售量,在此决策系统中每个属性相当于一个等价关系， 有等价关系得到的等价类为：,8.1.2近似与粗糙集 设 为 上的等价关系，当 能表示为某 些基本范畴并时，称是 可定义集；否则称 是 不可定义集。 可定义集是论域的子集，它可在知识 库中精确地定义，而 不可定义集不能在这个知识 库中被定义。 可定义集也称为精确集(Exact Sets), 而 不可定义集也称为粗糙集（Rough Sets)。 对于粗糙

4、集可以近似地定义，我们使用粗糙集的,上近似和下近似来描述。 定义8.1.3 给定知识库 对于每个子集 和一个 等价关系 定义两个子集： 分别称它们为 的 下近似和 上近似。 下近似和上近似也可以用下面的等式表达：,分别称为 的 边界域 、正域 和负域。 从上述定义，可得到 下近似和 上近似的性质： (1) (2) (3),，,(3) (4) (5) (6) (7) X粗糙集的概念可以用下面的示意图来表示：,8.1.3近似精度与粗糙度 定义8.1.4 设集合 是论域 上一个关于 的粗糙 集，定义 的 近似精度和粗糙度分别为： 近似精度反映根据现有知识对 的理解程度。显 然 当 时，集合 相对 于

5、是精 确的，当 时，集合 相对于 是粗糙的。,8.1.4 属性的重要性、属性约简和核 1. 属性的重要性 定义8.1.5 设有决策系统 其中 分别为条件属性集和决策属性集，则决策属性 在 条件属性 下的正域（简称 的 正域）定义为 的 正域是中通过用分类 表达的知识能够确 定地划入 类的对象集合。,定义 8.1.6 决策属性 对条件属性 的依赖度定义为 依赖度表示在条件属性集下能够确切划入决策分类 的对象占论域中的总对象数的比率，表达了决 策属性对条件属性的依赖程度。 定义8.1.7 设有决策系统 其中 分别为条件属性集和决策属性集，属性子集 的属性重要度定义为,特别当 时，属性 关于 的重要

6、性为 2. 属性约简 属性约简是粗糙集理论中的核心内容之一，决 策表中的属性并不是同等重要的，甚至有些属性是 冗余的，所谓属性约简，就是保持决策表条件属性,和决策属性之间的依赖关系不发生变化的前提下, 删 除其中不相关的或不重要的属性。 定义8.1.8 对于一给定的决策系统 若 则称属性 为 中 可省略，否则 属性 为 中 不可省略的。 定义 8.1.9 对于一给定的决策系统，条件属性集 的 约简是 的一个非空子集 。若满足,（1） 都是 不可省略的 （2） 则称 是 的一个约简。 中所有约简的集合记作 ， 中所有不可 省略属性的集合称 的核，记为 8.1.5决策规则和算法 决策表中的每一个对

7、象都可以看作是一条决策规 则。因此，决策表实际上是一组逻辑规则的组合。,定义8.1.10 在逻辑语言中， 蕴含 称为决策逻辑 语言中的决策规则， 和 分别称为决策规则的前件 和后件。 定义8.1.11 形式化定义 其 中 且 称为 基本公式。 定义8.1.12 当 为一个决策规则时，且 和 分别为 基本公式和 基本公式， 时，则,决策规则 称为 基本决策规则。 定义8.1.18 当且仅当对于 中任何一 决策规则 蕴含 时，则 决策算法中的 决策规则 是 中相容的，否则是不相容的。 定义8.1.19 如果一个决策表中所有的决策规则都是相 容的，则决策表是相容的，否则是不相容的。 定义8.1.20

8、 任何一个决策系统可以看做是一组“ if, then”的决策规则，当条件能唯一确定决策时， 该条规则为确定性决策规则，否则为不确定性决策 规则。 定义8.1.21 在决策系统中 ， 和 分 别代表 与 中各等价类。 表示对等价 类 的描述， 表示 对等价类的描述。 决策规则为：,该规则的确定性因子为 ： 当 是确定性规则；当 是不 确定性规则。 8.1.6算例分析 考察下面决策系统进行属性约简及获取决策规则。,表8-1-2 决策表,我们可以算出： 所以是条件属性集 的 约简。,确定性决策规则有： 不确定性决策规则有： 且各不确定性决策规则的确定性因子均为0.5 。,8.2 不完备决策系统的粗

9、糙决策分析方法,8.2.1 不完备决策系统 定义 8.2.1不完备决策系统 对象集合为 ； 为属性集合， 为属性 值集且 ，其中 是条件属 性值集， 是决策属性值集； 为一个信息函数，表示对每一个 如果至少有一个 中包含空值，则称 为不完 备决策系统。在不完备决策系统中，用*表示空值。,定义 8.2.2 给定不完备决策系统 假定 对象在 下的二元关系 定义为: 令 表示对象集合 为属 性 下与 可能不可区分的最大对象集合; 表 示对象集合 为属性 下与 可能 可区分的最大对象集合。 表示,分类， 中的任何元素称为相容类。 定义 8.2.3 假设 在相容关系 下 的下近似和上近似分别定义为 集合

10、 称为 在相容关系 下 的边界域。,有上述定义可以得到在 下的下近似和上 近似的下列性质。 定理8.2.1 如果 则有 （1） （2） （3） （4）,8.2.2属性约简与决策规则获取 定义8.2.4 给定不完备决策系统 假定函数 为 称 为 中 的广义决策函数，其中 表示 的幂集。 定义8.2.5 设 若满足下列条件: 则称 为 的 约简，记为,决策规则的获取： 令 是具有性质 （其中， ）的对象 集，令 是具有性质 （其中 ）的对象集. 在不完备决策系统 中，决策规 则 为真，当且仅当 其中 是出现在规则的条件部分的所有属性构成的 集合。若决策规则 是最优的当且仅,当该规则为真且由出现在中

11、的和取与析取的真子集 构成任何规则均为假。 8.2.3实例分析 考察下面一个关于汽车性能综合评判的不完备决 策系统，找出属性约简及决策规则。,从表中得到： Size ，Max-Speed是上表描述的决策系统的一个约 简。并得到下面三个决策规则 : （Max-Speed，Low） (d，good)； （ Size，compact） (d，poor)； （Size，full） (d，good) (d，excel),8.3 基于优势关系的粗糙决策分析方法,经典的粗糙集方法是通过不可分辨关系来实现知 识的获取，对有偏好信息的多属性决策问题是不适 用的。为此Greco等学者提出了用优势关系代替不可 分辨

12、关系较好地解决了有偏好信息的决策问题，该 方法将决策者的偏好信息以知识的形式表现出来， 通过决策规则来实现分类。,8.3.1基于优势关系的粗糙近似 设 为在论域 上关于准则 的优势关系， 即对于 表示对于准则 不劣于 类 似地，严格优势关系 表示对于准则 比 绝 对优，记为 。此外，设 为 上的决策类集合，使得任一 属于一个类且 仅属于一个类 假设对所有的 如果,则 的任一元素均比 的所有元素优（严格优 “”或不严格优“”）。 定义8.3.1 决策类的 上并集和下并集分别定义为 其中， 则 意味着 至少属于类别 意味着 至多属于类别 。显然 中的每一个对象优于或至 少等于 中的每一个对象。并且

13、有 :,定义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我们可以得到分类质量的 另外一

14、种形式：,定义8.3.7 满足 的最小子集 称为 关于 的一个约简，记为 。 一个具有偏好信息的完备决策系统可能不止一个 属性约简，所有属性约简的交集称为属性的核，记 为 。 8.3.2决策规则 先计算决策系统的属性约简，然后由优势关系下,粗糙集的下近似可得到确定性的偏好决策规则，包 括 决策规则和 决策规则这两部分；由优势关 系下粗糙集边界域可得到可能性的偏好决策规则， 即 决策规则。 1. 决策规则 If 且 且 ，且 Then 。其中,且 这类规则被 的 下近似的所有对象支持。 决策规则 If 且 且 ，且 then 。其中 且 这类规则被 的 下近似的所有对象支持。,决策规则 If 且

15、 且 ，且 且 且 且 ，且 then 其中 和 可能相交， 且 满足 这类 规则被 和 的边界域的所有对象支持。,8.3.3应用实例 考察下面一个关于学生综合评判的完备信息的多 属性决策系统，找出属性约简及决策规则。,决策类关于条件属性集 的分类质量 为 。,根据属性约简的定义可以得到属性 为该决策系统 的属性约简。 由于边界域 和 均为空集，我们 可以得到下面两条确定性决策规则： if if,8.4基于扩展优势关系的粗糙决策分析方法,对于信息不完全的偏好多属性决策问题，本节将 严格意义上的优势关系条件放宽，提出了扩展优势 关系，从而获得粗糙集中的近似，获取决策规则。 8.4.1不完全信息的

16、偏好多属性分类问题 定义8.4.1设决策系统 为非空属 性集合， 、 分别为条件属性集和决策属性集。 是属性值集， 分别为条件属性值集和 决策属性值集，并且 和 具有偏好次序。,是一个信息函数，表示对于每一个 如果某些条件属性值取空值， 用*表示，并假定决策属性值 没有空值，称 为不 完全信息的偏好多属性决策系统。 现要求对不完全信息的多属性决策系统进行分 类。假设决策属性 把论域 分成有限的类， 则对象中的任一,属于一个且仅属于 假定这种分类是有序的， 即对于所有的 如果 则 中的对象优于 中的对象。 定义8.4.2 决策类 的向上累集和向下累集分别为 其中 ，则 意味着 至少属于类 别 意

17、味着 至多属于类别 。,由定义显然可以得到下面的性质: 、 、 8.4.2基于扩展优势关系的粗糙近似 定义8.4.3 设 定义扩展优势关系为 或 或 ,这时称“ 扩展优势于 ”,记为 。 定义8.4.4 对于 ,则 分别称为 的 扩展优势集和扩展被优势集。 定义8.4.5 给定集合 在优势扩展关系下 的 下近似和 上近似分别定义,类似地 的 下近似和 上近似分别定义 和 的 边界域分别定义为：,其中 即 要求 每个对象至少有一个非空属性。 定义8.4.6 决策类集合 在扩展优势关系下关于准 则集合 的近似质量定义为 简称分类质量。,定义8.4.7 满足 的最小子集 称 为 关于 的一个约简，记

18、为 。 一个决策系统可能不止一个属性约简，所有属性 约简的交集称为属性的核，记为 。 8.4.3 决策规则 由扩展优势关系下粗糙集的下近似可得到两条 确定性的偏好决策规则，包括 决策规则和 决,策规则这两部分；由扩展优势关系下粗糙集边界域 可得到可能性的偏好决策规则，即 决策规则。 1. 由 得到决策规则 ： If 且 且 ，且 Then 。其中 且 ,这类规则在扩展 优势关系下被 的 下近似的所有对象支持。,2.由 可得 决策规则： If 且 且 ，且 Then 。其中 且 ,这类规则在扩展 优势关系下被 的 下近似的所有对象支持。 3.由 可得 决策规则：,If 且 且 ，且 且 且 且 ,且 then ;其中 和 可能相交， 且 满足 , 这类 规则在扩展优势关系下被 和 的边界域的所有 对象支持。,8.4.3应用实例 考察下面一个关于学生综合评判的不完备信息 的多属性决策系统，找出属性约简及决策规则。,决策类关于条件属性集 的分类质量 为 。根据属性约简的定义可以得到