粗糙集方法ppt.ppt

第8章集合论方法 一 粗糙集方法 8 1粗糙集方法 8 1 1粗糙集概念8 1 2属性约简的粗糙集理论8 1 3属性约简的粗糙集方法8 1 4粗糙集方法的规则获取8 1 5粗糙集方法的应用实例 8 1 1粗糙集概念 粗糙集 RoughSet 是波兰数学家Z Pawlak于1982年提出的 粗糙集以等价关系 不可分辨关系 为基础 用于分类问题 它用上 下近似两个集合来逼近任意一个集合 该集合的边界线区域被定义为上近似集和下近似集之差集 上 下近似集可以通过等价关系给出确定的描述 边界域的含糊元素数目可以被计算出来 模糊集 Fuzzy 是用隶属度来描述集合边界的不确定性 隶属度是人为给定的 不是计算出来的 粗糙集理论用在数据库中的知识发现主要体现在 1 利用等价关系对数据库进行属性约简 2 利用集合的上 下近似关系获取分类规则 1 信息表定义 信息表S U R V 的定义为 U 是一个非空有限对象 元组 集合 U x1x2 xn 其中xi为对象 元组 R 是对象的属性集合 分为两个不相交的子集 即条件属性C和决策属性D R CDV 是属性值的集合 Va是属性的值域 是的一个信息函数 它为每个对象x的每个属性a赋予一个属性值 即 2 等价关系定义 对于 A中包含一个或多个属性 它们的属性值相同 即 成立 称对象x和y是对属性A的等价关系 表示为 3 等价类定义 在U中 对属性集A中具有相同等价关系的元素集合称为等价关系的等价类 表示为 4 划分的定义 在U中对属性A的所有等价类形成的划分表示为 具有特性 i ii 当时 iii 例1 体温正常 体温正常 体温正常 体温高 体温高 体温很高 对于属性A 体温 的等价关系有 属性A的等价类有 U中对属性A的划分为 1 集合X的下近似定义 对任意一个子集属性A的等价类有 或表示等价类中的元素x都属于X 即 则x一定属于X 2 集合X的上近似定义 对任意一个子集 属性A的等价类有 或表示等价类中的元素x可能属于X 即 则x可能属于X 也可能不属于X 3 正域 负域和边界的定义 全集U可以划分为三个不相交的区域 即正域 Pos 负域 NEG 和边界 BND 从上面可见 用图说明正域 负域和边界 每一个小长方形表示一个等价类 图8 1正域 负域和边界 Pos X BND X X 任意一个元素 它一定属于X 任意一个元素 它一定不属于X 集合X的上近似是其正域和边界的并集 即对于元素 是无法确定其是否属于X 因此对任意元素 只知道x可能属于X 4 粗糙集定义 若 即即边界为空 称X为A的可定义集 否则X为A不可定义的 即 称X为A的Rough集 粗糙集 例2 对上例1的等价关系A有集合是粗糙集 计算集合X的下近似 上近似 正域 负域和边界 U中关于A的划分为 有 可知有 8 1 2属性约简的粗糙集理论 属性约简概念在信息表中根据等价关系 我们可以用等价类中的一个对象 元组 来代表整个等价类 这实际上是按纵方向约简了信息表中数据 对信息表中的数据按横方向进行约简就是看信息表中有无冗余的属性 即去除这些属性后能保持等价性 使对象分类能力不会下降 约简后的属性集称作属性约简集 约简集通常不唯一 求最小约简集 含属性个数最少的约简集 同样是一个困难问题 实际上它是一个NP hard问题 研究者提出了很多启发式算法 如基于遗传算法的方法等 1 约简定义给定一个信息表IT U A 若有属性集且满足 称B为A的一个约简 记为red A B red A 2 核定义属性集A的所有约简的交集称为A的核 记作Core A 是A中为保证信息表中对象可精确定义的必要属性组成的集合 为A中不能约简的重要属性 它是进行属性约简的基础 3 正域定义设决策属性D的划分 条件属性C相对于决策属性D的正域定义为 4 条件属性C相对于决策属性D的约简定义若 如果 则称c是C中相对于D不必要的 即可约简的 否则称c是C中相对于D必要的 5 条件属性C相对于决策属性D的核定义若 如果R中每一个都是相对于D必要的 则称R是相对于D独立的 如果R相对于D独立的 且 则称R是C中相对于D的约简 记为 所有这样简约的交称为C的D核 记为 一般情况下 信息系统的属性约简集有多个 但约简集中属性个数最少的最有意义 属性约简实例气候信息表是4个条件属性 天气a1 温度a2 湿度a3 风a4 和1个决策属性 类别d 见表8 1 令1 计算缺少一个属性的等价关系 计算减少一个条件属性相对决策属性的正域由此可知 属性a2 a3是相对于决策属性d可省略的 但不一定可以同时省略 属性a1和a4是相对决策属性不可省略的 因此 2 计算同时减少 a2 a3 的等价关系和正域说明 a2 a3 同时是不可省略的 3 在 a2 a3 中只能删除一个属性即存在两个约简 从实例计算可以看出 信息表的属性约简是在保持条件属性相对决策属性的分类能力不变的条件下 删除不必要的或不重要的属性 一般来讲 条件属性对于决策属性的相对约简不是唯一的 即可能存在多个相对约简 2020 3 16 32 可编辑 8 1 3粗糙集的属性约简方法 1 属性依赖度定义信息表中条件属性C和决策属性D 属性D依赖属性C的依赖度为 其中表示正域的元素个数 表示整个对象集合的个数 的性质 若 1 意味着 即已知条件C下 可将U上全部个体准确分类到决策属性D的类别中去 即D完全依赖于C 若0 1 则称D部分依赖于C DRough依赖于C 即在已知条件C下 只能将U上那些属于正域的个体分类到决策属性D的类别中去 若 0 则称D完全不依赖C 即利用条件C不能分类到D中的类别中去 2 属性重要度定义 DA C为条件属性集 D为决策属性集 a 属性a关于D的重要度定义为 其中表示在缺少属性a后 条件属性与决策属性的依赖程度 表示C中缺少属性a后 导致不能被准确分类的对象在系统中所占的比例 2 性质 1 0 1 2 若 0 表示属性a关于D是可省的 因为从属性集中去除属性a后 C a 中的信息 原来可被准确分类所有对象仍能准确划分到各决策类中去 3 0 表示属性a关于D是不可省的 因为为从属性集C中去除属性a后 某些原来可被准确分类的对象不再能被准确划分 3 最小属性集概念大多数情况下 数据库中存在一些不重要属性 我们希望找到一个最小的相关属性集 它具有与全部条件属性同样的区分决策属性所划分的决策类的能力 从最小属性集中产生的规则会更简练和更有意义 最小属性集定义 设C D分别是条件属性集和决策属性集 属性集是C的一个最小属性集 当且仅当并且若P是C的最小属性集 则P具有与C同样的区分决策类的能力 需要注意的是 C的最小属性集一般是不唯一的 而要找到所有的最小属性集是一个NP问题 在大多数应用中 没有必要找到所有的最小属性集 用户可以根据不同的原则来选择一个他认为最好的最小属性集 8 1 4粗糙集方法的规则获取 通过分析U中的两个划分和之间的关系 把C视为分类条件 D视为分类结论 我们可以得到下面的分类规则 1 当EYj 时 则有 rij 和分别是等价集Ei和等价集Yj中的特征描述 当EYj Ei时 Ei完全被Yj包含 即下近似 建立的规则rij是确定的 规则的可信度cf 1 0 当EYj Ei时 Ei部分被Yj包含 即上近似 建立的规则rij是不确定的 规则的可信度为 CF 2 当EiYj 时 Ei不被Yj包含 Ei和Yj不能建立规则 图8 2Ei和Yj的上 下近似关系 8 1 5粗糙集方法的应用实例 通过实例说明属性约简和规则获取方法 有表8 12的数据 表8 12流感实例数据 1 等价集下近似和依赖度的计算 1 条件属性C a b c 的等价集由于各元组 对象 之间不存在等价关系 每个元组组成一个等价集 共七个 E1 e1 E2 e2 E3 e3 E4 e4 E5 e5 E6 e6 E7 e7 2 决策属性D d 的等价集按属性取值 共有两个等价集 Y1 e1 e4 e5 Y2 e2 e3 e6 e7 3 决策属性的各等价集的下近似集为C Y1 E1 E4 E5 e1 e4 e5 C Y2 E2 E3 E6 E7 e2 e3 e6 e7 此例不存在上近似集 4 计算和 2 各属性重要度计算 1 a的重要度计算l条件属性C b c 的等价集E1 e1 e4 E2 e2 E3 e3 e6 E4 e5 e7 l决策属性D d 的等价集Y1 e1 e4 e5 Y2 e2 e3 e6 e7 l决策属性的各等价集的下近似集C Y1 E1 e1 e4 C Y2 E2 E3 e2 e3 e6 l计算和 l属性a的重要程度SGF C a D C D C a D 2 70结论 属性a是不可省略的 2 b的重要度计算l条件属性C a c 的等价集去掉属性b后 元组中只出现e2和e7的等价 其他元组均不等价 等价集共6个 E1 e1 E2 e2 e7 E3 e3 E4 e4 E5 e5 E6 e6 l决策属性D d 的等价集Y1 e1 e4 e5 Y2 e2 e3 e6 e7 l决策属性的各等价集的下近似集C Y1 E1 E4 E5 e1 e4 e5 C Y2 E2 E3 E6 e2 e7 e3 e6 POS C b D e1 e2 e3 e4 e5 e6 e7 POS C b D 7 C a D 1 l属性b的重要度SGF C b D C D C a D 0 l计算POS C b D l结论 属性b是可省略的 3 简化数据表 在原数据表中删除肌肉痛 b 属性后 元组e7和e2相同 合并成表8 13所示的简化数据表 表8 13流感数据简化表 4 等价集 上下近似集的计算 1 条件属性的等价集由于各元组之间不存在等价关系 故有6个等价集E1 e1 E2 e2 E3 e3 E4 e4 E5 e5 E6 e6 2 决策属性D d 的等价集按属性取值 共有两个等价集Y1 e1 e4 e5 Y2 e2 e3 e6 5