第11章 粗糙集理论.ppt

数据挖掘原理与SPSSClementine应用宝典元昌安主编邓松李文敬刘海涛编著电子工业出版社 第11章粗糙集理论 本章包括 粗糙集的基本概念知识表达粗糙集在数据预处理中的应用 粗糙集理论是由波兰华沙理工大学Pawlak教授于20世纪80年代初提出的一种研究不完整 不确定知识和数据的表达 学习 归纳的理论方法 它是一种刻画不完整性和不确定性的数学工具 能有效地分析不精确 不一致 inconslsteni 不完整 incomPlete 等各种不完备的信息 还可以对数据进行分析和推理 从中发现隐含的知识 揭示潜在的规律 粗糙集在机器学习 决策支持系统 机器发现 归纳推理 数据库中的知识发现 模式识别等领域都得到了广泛的应用 11 1粗糙集基本概念 粗糙集应用于数据挖掘领域 能提高对大型数据库中的不完整数据进行分析和学习的能力 具有广泛的应用前景和实用价值 粗糙集方法仅利用数据本身提供的信息 无须任何先验知识 粗糙集是一个强大的数据分析工具 它能表达和处理不完备信息 能在保留关键信息的前提下对数据进行化简并求得知识的最小表达式 能识别并评估数据之间的依赖关系 揭示出概念的简单模式 能从经验数据中获取易于证实的规则知识 粗糙集的研究对象是由一个多值属性 特征 症状 特性等 集合描述的一个对象 观察 病历等 集合 对于每个对象及其属性都有一个值作为其描述符号 对象 属性和描述符是表达决策问题的3个基本要素 粗糙集理论逐渐应用于数据挖掘领域中 并在对大型数据库中不完整数据进行分析和学习方面取得了显著的成果 使得粗糙集理论及数据挖掘的研究成为热点领域 最近几年 粗糙集理论越来越受到众多研究人员的重视 它的应用研究得到了很大的发展 11 1 1知识和知识库 知识是人类通过实践对客观世界的运动规律的认识 是人类实践经验的总结和提炼 具有抽象和普遍的特性 从认知科学的观点来看 知识来源于人类对客观事物的分类能力 概念是事物类别的描述或者符号 知识则是概念之间的关系和联系 任何一个物种都是由一些知识来描述与分类的 利用物种的不同属性知识描述来产生对物种的不同分类 集合上的等价关系和集合上的划分是一一对应 相互唯一决定的 从数学意义上讲 集合上的等价关系和集合的划分是等价的概念 即划分就是分类 定义11 1设讨论的对象组成的有限集合 称为论域 Universe 对于论域中由等价关系划分出来的任意子集 都可以称为论域U中的一个概念 concept 或范畴 category 为规范起见 认为空集必也是一个概念 论域U中的任意概念族称为关于论域的抽象知识 它代表了对论域中个体的分类 简称为知识 定义11 2K U R 其中K为知识库 U为全体对象的集合称为论域 R为论域U上的等价关系 等价关系与分类的概念等同 它是一种属性或多种属性的集合 可以根据不同的R对U进行不同形式的分类 知识库也被称作近似空间 定义11 3K U P 和M U Q 是两个知识库 若IND P IND Q 则称K和M 或Q和P 是等价的 记作 或者 因此 当K和M是同样的基本范畴集时 知识库K和M中的知识都能使我们确切地表达关于论域的完全相同的事实 这个概念意味着可以用不同的属性集对对象进行描述 以表达关于论域的完全相同的事实 对于两个知识库K U P 和M U Q 当时 称知识库P比知识库Q更精细 或者说Q比P更粗糙 当P比Q更精细时 我们称P为Q的特化 Q为P的推广 由以上可知 推广是将某些范畴组合在一起 而特化则是将范畴分割成更小的单元 11 1 2不可分辨关系 在粗糙集理论中 知识 被认为是一种分类的能力 不可分辨关系的概念是粗糙集理论的基石 它揭示出论域知识的颗粒状结构 假定关于论域的某种知识 并使用属性和属性值来描述论域中的对象 如果两个对象 或对象集合 具有相同的属性和属性值 则它们之间具有不可分辨关系 定义11 4设R是非空集合U上的二元系 如果它是自反的 对称的和可传递的 则称R为U上的等价关系 若 则称x与y有关系 记为 若 则称x与y没有关系 记为 等价关系的一个重要特点是用它可以构成U的一个划分 划分即是分类 将研究对象分成不同的类 这些类之间互不相交 且每一对象均包含在某一类中 定义11 5设U是一个论域 R是U上的等价关系 U R表示U上由R导出的所有等价类 表示包含元素x U的R等价类 一个知识库就是一个关系系统K U P 其中U是论域 P是U上的一个等价类簇 如果且 则 Q的所有等价类的交也是一个等价关系 称Q为不可分辨关系 记作IND Q 11 1 3上 下近似集 给定论域U 一族等价关系R将U划分为互不相交的基本等价类U R 令XgU为R上的一个等价关系 当能表达成某些基本等价类的并集时 称为可定义的 否则称为不可定义的 R可定义集能在这个知识库中被精确地定义 所以又称为R精确集 R不可定义集不能在这个知识库中被精确定义 只能通过集合逼近的方式来刻画 因此也称为R粗糙集 Roughset 两个精确集 即粗糙集的上近似集 UpperApproximation 和下近似集 LowerApproximation 来近似地定义粗糙集 粗糙集理论引入上近似和下近似等概念来刻画知识的不确定性和模糊性 定义11 6设集合 R是一个等价关系 称为集合X的R下近似集 称为集合X的R上近似集 称集合为X的R边界域 称为X的R正域 称为X的R负域 例11 1设论域 U上的一族等价关系R R1 R2 R1和R2是两个等价关系 根据这两个等价关系可以将论域U进行划分 和 U R1中的 代表的等价类 论域U被R划分的基本等价类为 集合是U上的一个子集 则X无法用基本等价类U R的并集精确表示 所以X是U上的一个粗糙集合 故有 X的下近似集为 X的上近似集为 X的负区域 11 2知识表达 知识表达在智能数据处理中占有十分重要的地位 在智能系统中 经常会碰到要处理的对象可能是用语言方式表达 也可能使用数据表达 可能是精确的数据 可能会有一些缺省的信息或者相互矛盾的信息 为了处理这些数据 我们需要进行知识的表达 即知识表达系统 决策表是特殊的知识表达系统 11 2 1知识表达系统 定义11 7一个知识表达系统S可以定义为 其中U为对象的集合 称为论域 R为属性集合 子集C和D分别称为条件属性和决策属性 为属性值的集合 表示了属性的属性值范围 是一个信息函数 它指定了U中每一对象x的属性值 知识表达系统的数据以关系表的形式表示 关系表的行对应要研究的对象 列对应对象的属性 对象的信息是通过指定对象的各属性值来表达 例11 2 表11 1是一个轿车信息决策表 条件属性集为 e1 e2 e3 e4 分别代表价格 油耗 速度和安全性 决策属性为d 表示质量 表11 1轿车信息决策表 11 2 2决策表 决策表包含了某一领域的大量数据 是领域的样本数据库 它记录了大量样本的属性值和决策情况 是领域知识的载体 知识获取的目的就是要通过分析这个实例库来得到该领域中有用的 规律性知识 决策表在决策应用中有十分重要的地位 可用于表达绝大多数决策问题 对于决策表 最重要的是决策规则的生成 定义11 8设U U1 U2 U3 Un 是一个论域 U i 1 2 n 是研究对象 P是属性集 P C D C为条件属性集 D为决策属性集 T U P C D 是决策表 决策表中每一行就是一条决策规则 dx C dx D dx B表示个体x关于属性集B的值 定义11 9若决策表T中任意的dx dy 由dx C dy C 可得dx D dy D 则称决策规则dx是一致的 否则 称决策规则dx是不一致的 如果T中每条决策规则都是一致的 则称决策表T是一致的 否则称决策表T是不一致的 定义11 10设T U P C D 是决策表 如果去掉条件属性Pi 得到的表T1 U P Pi C Pi D 与表T相比 有PosC D Pos D 则称属性Pi是关于D可省的 否则称属性Pi是关于D不可省的 是D关于B的正区域 其中 定义11 11如果决策表中每个条件属性都是关于D不可省的 则称条件属性集C是关于D独立的 否则称C是关于D依赖的 定义11 12决策表T U P C D 中条件属性集C的一个子集B是关于D独立的 并且PosB D PosC D 则称B是C的一个D约简 11 2 3属性约简 核集的求取 所谓属性约简 就是在保持知识库分类能力不变的条件下 删除其中不相关或不重要的属性 一个属性集合可能有多个约简 属性约简的目标就是要从条件属性集合中发现部分必要的条件属性 使得根据这部分条件属性形成的相对于决策属性的分类和所有条件属性所形成的相对于决策属性的分类一致 即和所有条件属性相对于决策属性D有相同的分类能力 属性集合P的所有约简的交集定义为P的核 Core 记作core P 核是表达知识必不可少的重要属性集 核的概念具有两方面的意义 l 因为核包含于所有约简之中 所以核可以作为所有约简的计算基础 2 核在知识约简中是不能消去的特征集合 直接由分辨矩阵来求取系统的核集Pc 不失一般性 假定系统T对于属性集P是可分辨的 则系统的核集由以下定理1确定 定理11 1P中任一属性P Pc 充要条件为 D P 中至少存在一个元素 满足 其中 元素都是属性集P的一个子集 元素Dij定义如下 其中i j 1 2 3 m 1 2 命题11 1从信息系统的决策表中将属性集P中逐一移去 每移去一个属性即刻检查其决策表 如果不出现新的不一致 则属性是可被约去的 否则属性不能约去 命题11 2全体不可约去属性集称为核集 属性集合的约简和核的关系如下 式中red P 表示P的所有约简 core P 含有P的全部约简中共同的等价关系 是属性集合P中不可缺少的重要属性集 11 2 4属性值约简 属性约简只是在一定程度上去掉了决策表中冗余属性 还是没有充分去掉决策表中的冗余信息 在判断某个对象属于某类时 其属性的取值不同 对分类产生的影响也不同 例如 判断人的体形 瘦 中 胖 时 体重是主要属性 但若体重属性值为75Kg时 此人的体形要结合其身高 性别等属性才能确定 如果体重属性值为160Kg时 几乎肯定其体形为胖 这时身高 性别已不重要 命题11 3设 是决策表上的一条决策规则 属性值v是一可被约去当且仅当 其中和均为决策表上的逻辑公式 8 11 2 5决策规则 6 决策表包含了某一领域的大量数据 是领域的样本数据库 它记录了大量样本的属性值和决策情况 是领域知识的载体 知识获取的目的就是要通过分析这个实例库来得到该领域中有用的 规律性知识 从决策表分析得到的规律性知识 通常采用决策规则的形式记录下来 下面给出决策规则的形式化描述 定义11 13定义公式如下 1 a v 或写为av a A v Va 表示属性a的取值为v 是公式且是原子公式 2 如果A和B都是公式 那么 A B都是公式 3 只有按定义 1 和 2 所组成的式子是公式 对于决策表是决策表 A C D属性集合 子集和分别为条件属性集和决策属性集 有关决策规则的定义如下 定义11 14公式称为P基本公式 这里 P 定义11 15 11 公式称为Q基本公式 这里 定义11 16 11 公式A B为决策规则 如果A是P基本公式且B是Q基本公式 则A B是基本决策规则 11 2 6基于可辨识矩阵属性约简算法 6 可辨识矩阵 也称分明矩阵 是由波兰数学家Skowron A教授提出的 定义11 17设相容决策表T A C D 和D d 分别为条件属性集和决策属性集 是论域 是样本在属性上的取值 表示可辨识矩阵中第i行j列的对象 则可辨识矩阵定义为 其中 由上述定义可以看出 可辨识矩阵是一个对称矩阵 当两个样本的决策属性取同时 对象值为0 当两个样本的决策属性不同且可以通过某些条件属性的取值加以区分时 对象值为这两个样本属性值不同的条件属性集合 一个数据集的所有约简可以通过构造可辨识并且化简由可辨识矩阵导出的区分函数而得到 所有的蕴含式包含的属性就是决策表的所有约简集合 算法11 1可辨识矩阵属性约简算法输入 相容决策表DT A C D是属性集合 输出 约简的属性集 步骤 Step1计算决策表的可辨识矩阵 根据分辨矩阵的定义求元素Step2对于可辨识矩阵中所有取值为非空集合的对象 建立相应的析取逻辑表达式 Step3将所有的析取逻辑表达式进行合取运算 得一个合取范式T 即 Step4将合取范式L转换为析取范式的形式 得 Step5输出属性约简结果 基于可辨识矩阵和逻辑运算的属性约简算法可以得到决策表的所有可能的属性约简结果 它实际上是将对属性组合情况的搜索演变成为逻辑公式的简化 11 2 7信息熵的属性约简 信息熵是信息论的核心内容 它最早应用于通信领域 由于信息熵可以刻画信息划分粒度的大小 也被广泛应用于信息不确定性的度量 设U为一个论域 可以认为U上任一属性集合 知识 等价关系簇 是定义在U上的子集组成的R代数上的一个随机变量 其概率分布可通过如下方法来确定 定义11 18设P Q在U上导出的划分分别为X Y则P Q在U的子集组成的代数上的概率分布为 其中 定义11 19知识P的熵H P 定义为 定义11 20决策信息系统S U A C D V F C D为U上的一个等价关系集合 C D在U上导出的划分分别为 则D相对于C的条件信息熵H D C 为 其中 定理11 2在信息系统S U A C D V F 中 若H D B H D B b 则称b为B中相对于D是可省的 不必要的 否则b为B中相对于D是不可省的 对 若其任一元素D都是必要的 则称B相对于D是独立的 定义11 21在决策信息系统S U A C D V F 中 若 H D B H D C 且B相对与D是独立的 则称B是C关于D的属性约简 推论11 1如果一个属性a不能为属性子集R的分类增加任何信息 即 就可以将这个属性约简 算法11 2信息熵的求核算法输入 相容决策表T A C D是属性集合 子集和D d 分别为条件属性集和决策属性集 输出 信息熵定义下的核属性 步骤 Begin 1 2 对于条件属性集C中的所有属性r 如果H D C H D C r 则 End CEBARKCC算法是一种比较典型的基于信息熵的属性约简算法 该算法是建立在决策属性集相对于条件属性集的条件熵的基础上的 以H D B a 作为启发式信息 以H D B H D C 作为算法的终止条件 CEBARKCC算法以决策表核属性集为起点 逐次选择使H D B a 最小的非核条件属性a添加到核属性集中 直到满足终止条件H D B H D C 算法11 3CEBARKCC算法输入 相容决策表T A C D是属性集合 子集和D d 分别为条件属性集和决策属性集 输出 该决策表的一个相对约简B 步骤 Step1计算决策表S中决策属性集D相对条件属性集C的条件熵H D C Step2计算条件属性集C中相对于决策属性集D的核属性Co Step3令B C0 a如果 B 0 则计算条件熵H D B 转d b对每个属性 计算决策属性集D相对条件属性集的条件熵 c选择使c 若同时有多个属性达到则从中选取一个与B的属性值组合数最少的属性 dIFH D B H D C Thenb 11 2 8基于信息熵的属性约简改进算法 2 定义11 22设S U A C D V F 是一个决策信息系统 其中C是条件属性集合 D是决策属性集合 且 则对于任意属性a C R的重要度的定义为 其中 算法11 4信息熵的属性约简改进算法输入 相容决策表T A C D是属性集合 子集和D d 分别为条件属性集和决策属性集 输出 决策表T的一个相对约简P 步骤 Step1计算决策表T中决策属性集D相对条件属性集C的条件熵H D C Step2计算条件属性集C中相对于决策属性集D的核属性Co Step3计算条件信息熵H D P 转Step6 Step4对i 1 n bi B中的每个属性计算条件熵H D P bi 求SGF bi P D H D P H D P bi 得到属性bi的重要度SGF bi P D Step5选择使SGF bi P D 最大的属性bi 若同时有多个属性达到最小值 则从中选取一个与P的属性值组合数最少的属性 把bi从B中删除 并把bi增加到P的尾部 同时从B中删除使SGF的值为零的属性bi Step6如果H D P H D C ThenStep4Step7从P的尾部开始 从后向前判别每个属性的a是否可约 如果 则从a开始向前的属性都是核属性 不可约 算法终止 否则 如果H D P a H D C 则a是可约简的 把a从A中删除 例11 4 根据表11 5决策表所示 根据算法11 4进行信息熵的属性约简计算 表11 5决策表Uabcdefe1101121e2001110e3110120e4010111e5122120e6210101 Step1求出H D C 0 Step2利用求核算法求出 情形一 Step3求出H D P 1 转Step6 ifH D P H D C ThenStep4Step4SGF a P D H D H D a 0 2075 SGF b P D H D H D b 0 2075 SGF c P D H D H D c 0 2075 SGF d P D H D H D d 0 SGF e P D H D H D e 0 2705 P a B b c e Step5选择属性a同时删除不必要的属性d 情形二 Step3H D P 0 7925 转Step6 ifH D P H D C ThenStep4Step4SGF b P D H D a H D a b 0 7925 SGF c P D H D a H D a c 0 7925 SGF e P D H D a H D a e 0 P a b B c Step5选择属性b的同时删除不必要的属性e H D P H D C 0Step6P中没有可删除属性 则相对约简集为P a b 11 3粗糙集在数据预处理中的应用 基于粗糙集理论的数据预处理方法 首先对原始数据 原始决策表 进行离散化 然后可以通过两种方法对离散化的决策表进行属性约简 最后进行属性值的约简 我们以一个医疗数据记录决策表为例子 给出属性约简求核和属性值约简的过程 11 3 1属性约简的两种方法 本节介绍属性约简的两种方法 分辨矩阵求核约简方法 直接求核集方法 方法一 分辨矩阵求核约简方法 设D是一个m m阶矩阵 其中每一个元素Dij都是P的一个子集 元素Dij定义如下 Dij dij1 dij2 dij3 dijn 其中i j 1 2 3 m 1 2 说明 U U表示决策表中第i行和第j行两个属性的值 k表示决策表的研究对象的个数 分辨矩阵D是一个对角线为0的对称矩阵 方法二 直接求核集方法 用命题11 1 命题11 2直接求核集 例11 3以下决策表11 2给出了一个医疗数据记录表 通过测量人的体温 咳嗽 头痛 周身痛等症状来确定是否患了流感 表11 2医疗记录表U体温咳嗽头痛周身痛流感1正常无无有无2正常无有无无3偏高无有无有4高有有无有5高有无无有6偏高有有无有 其中属性及属性值的含义为 体温 a 正常 0 偏高 1 高 2 咳嗽 b 无 0 有 1 头痛 c 无 0 有 1 周身痛 d 无 1 有 1 流感 e 无 0 有 1 通过对决策表11 2进行处理后 得到离散形式的决策表11 3如下所示 表11 3医疗决策表Uabcde100010200100310101421101521001611101其中 条件属性集为 a b c d 决策属性集为 e 根据粗糙集理论对表11 3医疗决策表进行数据预处理 处理过程分两个步骤进行 一是对决策表条件属性集进行约简求核 二是对条件属性值进行约简 Step1条件属性约简求核 下面讨论属性约简求核的两种方法 分辨矩阵直接求核约简法和用命题11 1 命题11 2求核约简法 首先 用分辨矩阵直接求核集 用以下举例说明分辨矩阵求核约简的方法 如表11 3医疗决策表所示是一个知识系统 U U1 U2 Un 是论域 C a b c d 是条件属性集 D e 是决策属性集 则其相应的分辨矩阵为 D 从上述分辨矩阵中可以得出 由于D e 是决策集 不需要约简 约简的是条件集合C 根据定理11 1直接求出该知识系统的核集为 a b c 该约简求核集的方法便于计算机上实现 其次 用方法二直接求核集集 还是以决策表11 3作为知识系统的例子 求核集的步骤为 1 去掉属性a 对比每一行属性值 第4 6行发生冲突 则属性a不可约 2 去掉属性b 对比每一行属性值 第4 6行发生冲突 则属性b不可约 3 去掉属性c 对比每一行属性值 第4 5行发生冲突 则属性c不可约 4 去掉属性d 对比每一行属性值 没有发生冲突 则属性d可约 若还有条件属性 则依次类推 经过约简后得到的核集为 a b c 比较两种求核集的方法 对于数据量大 采用分辨矩阵来求核集 方便计算机来实现 第二种方法简单易行 方便人工处理 Step2属性值约简 属性值约简是在核集基础上进行的 经约简后的核集用表11 4医疗核集决策表表示如下 表11 4医疗核集决策表Uabce100002001031011421115210161111根据命题11 3计算决策规则中条件属性的核值 并确定出一个最小决策算法 用逻辑语义表示 对于决策规则1 1 a 1 2 1 b 1 2 3 1 c 1 5 1 e 1 2 其中 1 a 1 b 1 2 1 2 3 1 2 1 e 则c0 表示c属性值为0 可约 1 a 1 c 1 2 1 5 1 1 e 则b0 表示b属性值为0 可约 1 b 1 c 1 2 3 1 5 1 1 e 则a0 表示a属性值为0 可约 对于决策规则2 2 a 1 2 2 b 1 2 3 2 c 2 3 4 6 2 e 1 2 其中 2 a 2 b 1 2 1 2 3 1 2 2 则c1是可约的 2 a 2 c 1 2 2 3 4 6 2 2 则b0是可约的 2 b 2 c 1 2 3 2 3 4 6 2 3 2 则a0不可约 其逻辑语义表示为 a0b0Va0c1 e0同理 决策规则3推出 a1不可约 b0可约 c1不可约 其逻辑语义为 a1b0Va1c1Vb0c1 e1决策规则4推出 a1 b1 c1均可约 决策规则5推出 a2 b1 c0均可约 决策规则6推出 a1 b1 c1均可约 经过上述属性和属性值的约简 得到了最小决策算法 它的逻辑语义为 a0b0Va0c1 e0和a1b0Va1c1Vb0c1 e1 相应的自然语言的语义是体温正常且不咳嗽或者体温正常且头痛的不患流感 体温偏高且不咳嗽或者体温偏高且头痛或者不咳嗽且头痛的患流感 11 3 3粗糙集在神经网络中的应用 粗神经网络算法 数据表示方法越明显 冗余数据越少 神经网络就越容易学习 神经网络的神经元节点个数越多 权值的个数越多 则它的训练时间就越长 而且神经网络的泛化能力就越差 通过粗糙集对数据进行约简 用约简后的数据集作为BP神经网络的设计依据及训练数据 这样得到的训练数据表示清晰 从而使得两种方法进行互补 既能利用粗糙集约简数据 减少BP神经网络训练时间 又能利用BP神经网络降低噪声影响 一方面提高了数据的代表性 减少了噪声的干扰 使训练出来的神经网络不容易出现过配现象 另一方面减少了训练数据 使训练时间得以减少 提高了效率 算法11 5粗神经网络算法输入 输入离散型决策表 输出 输出决策结果 步骤 Step1 确定问题 首先要对待解决的问题做出详细的调研 明确目标 然后考虑如何引入粗糙集从而更好地解决该问题 Step2 采集数据 对原始数据进行收集 Step3 数据处理 把要处理的数据建立成一张决策表 即一张二维表格 每一行描述一个对象 每一列描述对象的一种属性 在这一部分中 如果无法得到完备的数据表 就有必要将信息表进行完备化操作 如果初始数据是连续值 还要经过连续属性离散化操作 Step4 根据粗糙集理论对数据进行属性约简 去掉数据表中的冗余条件属性 同时消去重复的样本并处理矛盾的