粗糙集决策方法.ppt

粗糙集决策方法 钟映竑zhongyh 管理研究方法论 方法论 methodology 指处理问题的一般途径和程序 方法 method 指具体的做法 管理研究方法论 阐述管理学科研究工作的基本原则 途径和程序 在总结前人经验的基础上 提出有效的研究工作规范 包括问题阐述 文献综述 假设提出 数据收集 统计分析 信度和效度判断以及研究报告或论文的撰写等各个环节的规范 管理研究方法论的重要性 研究方法论是一种规范 逻辑 可以把研究工作提高到专业水平 正规学术训练 VS 野路子 新闻报道 工作报告 科学方法与科学研究 通过系统观测而获取客观知识的方法 客观性实证性规范性科学研究 满足以上特征的获取新知识的精确方法 研究对象具有可直接侧鲁昂和重复出现等特点 科学研究中应使用中性名词和语句 举例 贵重金属 稀有金属民族工业 本土工业经过艰苦不懈的努力研究 本文得到了重要结论 对我国低碳供应链的发展具有重要意义 思辨方法与思辨研究 涉及人的价值观和偏好的领域以及发现新知识的过程 不强调客观性和实证性 所得结果不必建立在直接观测和经验基础上 不必服从规范性 哲学 宗教 文学 艺术 音乐 目标函数是利润最大化 如何实现最优化 顿悟 赚钱的意义是什么 我为什么要赚那么多钱 VS 科学研究问题 思辨研究问题 天上的星空 心中的道德 康德 管理研究的分类 描述型研究 descriptionstudies 收集数据以检验有关亚久对象状态假设的工作过程 它回答who whatwhere howmuch之类的问题 旨在将现象和事件描述和识别清楚 管理研究的分类 解释型研究 explanationstudies 回答为什么 why 的问题 探索现象和事件之间的关联 弄清因果 描述型和解释型研究类似于医生看病的诊断过程 描述是基础 解释是后续 管理研究的分类 规范型研究 prescriptionstudies 回答 应该怎样 的问题 理工科背景的研究生偏爱规范型研究 管理研究设计 两个目的 辨识问题 提炼主题论证和验证主题 管理研究设计 问题辨析 研究问题从哪里来 聚焦研究主题 提出假设 建立假设树 假设论证或假设检验 理论研究 实证研究 统计研究 实地研究 实验研究等 建立假设树要注意的问题 假设树是一项研究工作创新点的结构化表述 不是工作提纲 假设树中任何一层假设的表述都应当是假设的形式 也就是变量和变量之间关系的陈述语句 下层次假设一定要支持上层次的假设 推荐阅读 管理研究方法论 李怀祖 西安交通大学出版社 2006 11 组织与管理研究的实证方法 陈晓萍 徐淑英 樊景立 北京大学出版社 2008 6 管理研究方法的来源 管理学不是一门纯粹的学问 它的学科基础很复杂 包括数学 计算机科学 工程学 经济学 社会学 人类学 心理学 行为科学 政治学 生物学 等等 学科来源的复杂多样化 导致管理研究方法的多样性 管理问题集 经济学方法 数学方法 计算机科学方法 工程学方法 社会学方法 人类学方法 心理学方法 行为科学方法 政治学方法 生物学方法 灯下寻找钥匙 避免方法论或方法的帝国主义或孤立主义 应当坚持 多元主义互补主义 管理问题 管理研究方法论 管理研究方法 管理的学科基础所提供的研究方法 数学 运筹学 统计学 经济学 博弈论计算机科学 数据挖掘方法 仿真 社会学 人类学 案例研究方法 统计方法 结构方程模型 工程学 系统工程方法 泰罗的科学管理 心理学 行为科学 实验方法 生物学 演化方法 纯粹管理学方法 处理大数据的方法 粗糙集决策理论与应用 粗糙集概述 在很多实际系统中均不同程度地存在着不确定性因素 采集到的数据常常包含着噪声 不精确甚至不完整 粗糙集理论是继概率论 模糊集 证据理论之后的又一个处理不确定性的数学工具 粗糙集在应用中的优点 粗糙集分析数据不需要先验知识 粗糙集理论是适合大数据集分析的强大工具 粗糙集提供了含糊概念的数学描述 并可计算 粗糙集的发展历程 1982年提出到80年代末 研究主要集中在东欧 1991年 Pawlak出版了第一部关于粗糙集的专著 RoughSets TheoreticalAspectsofReasoningaboutData 1992年 R Slowinski主编的关于粗糙集应用及其与相关方法比较研究的论文集的出版 推动了国际上对粗糙集理论与应用的深入研究 1992年在波兰Kiekrz召开了第一届国际粗糙集讨论会 以后每年一届 1995年 ACMCommunication将它列为新浮现的计算机科学的研究课题 1998年 国际信息科学杂志 InternationalJournalofInformationScience 为粗糙集理论的研究出了一期专刊 2004年 国际粗糙集协会主办的第一本粗糙集国际期刊 AdvancesinRoughSets 出版发行 国外主要研究机构 波兰华沙大学 工业大学 信息技术和管理大学和加拿大Regina大学和圣玛丽大学 英国Edinburgh大学 Ulster大学和Cardiff大学 意大利Catania大学 印度统计研究院 美国SanJose州立大学 2001年5月 第一届中国Rough集与软计算学术研讨会 邀请了创始人Z Pawlak教授做大会报告 重庆 重庆邮电大学 2002年10月 第二届中国Rough集与软计算学术研讨会 苏州 苏州大学 2003年5月 第三届中国Rough集与软计算学术研讨会 重庆 重庆邮电大学 注 同年 承办了第九届国际粗糙集 模糊集 数据挖掘与粒计算学术研讨会 中国人工智能学会也于同年正式成立粗糙集与软计算专业委员会 2004年10月 第四届中国Rough集与软计算学术研讨会 舟山 浙江海洋学院 2005年8月 第五届中国Rough集与软计算学术研讨会 鞍山 鞍山科技大学 2006年 第六届中国Rough集与软计算学术研讨会 金华 浙江师范大学 2007年 第七届Rough集与软计算 第一届Web智能 第一届粒计算联合学术会议 太原 山西大学 2008年 第八届中国Rough集与软计算学术会议 第二届中国Web智能学术研讨会 第二届中国粒计算学术研讨会联合学术会议 CRSSC CWI CGrC2008 新乡 河南师范大学 2009年8月 第九届中国Rough集与软计算学术会议在河北师范大学召开 石家庄 国内主要研究机构 中科院计算所 中科院自动化所 重庆邮电大学 南昌大学 西安交通大学 山西大学 合肥工业大学 北京工业大学 上海大学 山东大学 粗糙集基本概念 基本粗糙集理论认为知识就是人类所固有的分类能力 分类是推理 学习与决策中的关键问题 粗糙集理论假定知识是一种对对象进行分类的能力 知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在一起 这种特定部分称之为所讨论的全域或论域 universe 对于全域及知识的特性并没有任何特别假设 事实上 知识构成了某一感兴趣领域中各种分类模式的一个族集 family 这个族集提供了关于现实的显事实 以及能够从这些显事实中推导出隐事实的推理能力 粗糙集的思想基础 粗糙集基于这种认识 在分类机制的基础上建立 它将分类理解为在特定空间 论域U 上的等价关系 R 而等价关系构成了对该空间的划分 在特定空间上的等价关系反映了人们对该空间的认识 称为知识 U R 借用边界域的概念 粗糙集理论巧妙地表达了人们在认识事物时表现出的不确定性 粗糙概念的来源之一 集合与模糊 集合概念的提出 Cantor1883 集合是数学中的基本概念 也是大部分数学结构的依赖 如何表示和处理现实生活中的含糊现象 谓词逻辑的创始人G Frege 1904 提出了含糊 Vague 的概念 他把它归结到边界线上 也就是说在全域上存在一些个体既不能在其某个子集上分类 也不能在该子集的补集上分类 如何表示和处理现实生活中的含糊现象 Zadeh提出了模糊集 1965 但模糊集理论采用隶属度函数来处理模糊性 而基本的隶属度是凭经验或者由领域专家给出 所以具有相当的主观性 含糊 vagueness 和不确定 uncertainty 含糊是集合的性质 可以通过近似概念来描述 而不确定性是集合中元素的性质 可以通过隶属函数表达 通常二者也不加区分 称为模糊 注意 粗糙集的另一个来源 知识表达系统 Z Pawlak先提出了知识表达系统 1973 其中提出了按照属性分类的思想 后来他又提出了近似空间的概念 1981 试图用上下近似来描述集合 Z Pawlak InformationSystemsTheoreticalFoundations J InformationSystems 1981 6 3 205 218 1982年 Pawlak提出了粗糙集 RoughSets 他把那些无法确认分类的个体都归属于边界域 而这种边界域被定义为上近似集和下近似集之差集 由于它有确定的数学公式描述 完全由数据决定 所以更有客观性 Z Pawlak Roughsets InternationalJournalofComputerandInformationSciences 1982 11 5 341 356 基本概念 定义称一个二元组K U R 为一个近似空间 approximatespace 或知识库 其中U 为空集 是一个被称为全域或论域 universe 的所有要讨论的个体的集合 R是U上等价关系的一个族集 定义称一个二元关系R是不可分辨关系或等价关系 indiscerniblerelation 如果R满足 给定近似空间K U R 子集X U称为U上的一个概念 concept 空集也视为一个概念 非空子族集P R所产生的不分明关系IND P 的所有等价类关系的集合即U IND P 称为基本知识 basicknowledge 相应的等价类称为基本概念 basicconcept 特别地 若关系Q R 则关系Q就称为初等知识 elementaryknowledge 相应的等价类就称为初等概念 elementaryconcept 由定义可知 概念即对象的集合 概念的族集 分类 就是U上的知识 U上分类的族集可以认为是U上的一个知识库 或说知识库即是分类方法的集合 A x1 x2 x3 x4 x5 x6 x7 x8 每个积木块都有颜色属性 按照颜色的不同 我们能够把这堆积木分成R1 红 黄 兰 三个大类 那么所有红颜色的积木构成集合X1 x1 x2 x6 黄颜色的积木构成集合X2 x3 x4 兰颜色的积木构成集合X3 x5 x7 x8 按照颜色这个属性我们就把积木集合A进行了一个划分 所谓A的划分就是指对于A中的任意一个元素必然属于且仅属于一个分类 那么我们就说颜色属性就是一种知识 在这个例子中我们不难看到 一种对集合A的划分就对应着关于A中元素的一个知识 假如还有其他的属性 比如还有形状R2 三角 方块 圆形 大小R3 大 中 小 这样加上R1属性对A构成的划分分别为 A R1 X1 X2 X3 x1 x2 x6 x3 x4 x5 x7 x8 颜色分类 A R2 Y1 Y2 Y3 x1 x2 x5 x8 x3 x4 x6 x7 形状分类 A R3 Z1 Z2 Z3 x1 x2 x5 x6 x8 x3 x4 x7 大小分类 上面这些所有的分类合在一起就形成了一个基本的知识库 除了红的 x1 x2 x6 大的 x1 x2 x5 三角形的 x1 x2 这样的概念以外还可以表达例如大的且是三角形的 x1 x2 x5 x1 x2 x1 x2 大三角 x1 x2 x5 x1 x2 x1 x2 兰色的小的圆形 x5 x7 x8 x3 x4 x7 x3 x4 x6 x7 x7 兰色的或者中的积木 x5 x7 x8 x6 x8 x5 x6 x7 x8 而类似这样的概念可以通过求交运算得到 比如X1与Y1的交就表示红色的三角形 所有的这些能够用交 并表示的概念以及加上上面的三个基本知识 A R1 A R2 A R3 一起就构成了一个知识系统 记为R R1 R2 R3 它所决定的所有知识是A R x1 x2 x3 x4 x5 x6 x7 x8 以及A R中集合的并 粗糙集理论建立在这样一个前提上 即所考虑的论域中的每一个对象都包含某种信息 数据和知识 基本集 基本粒度 定义 所有不可区分的对象形成的集合解释 可区分 可分辨 如果Ui Uj就称这两个对象在其条件P下是可区分的 对于两个不同的对象至少有一个属性是不同的 否则即为不可区分 举例 对于右表来说 U中有四个对象 概念 而现在条件集合中只有一个属性 对于U1和U2来说 它们的p不同 所以可以通过p来区分 即u1 u2在p下可区分 而U2和U3虽然是不同的对象但是在P下却是相同的 即在p下不可区分 就成为不可区分的对象 信息系统 信息系统被定义为如下的四元组 S U A V f 其中S为知识表达系统 U x1 x2 xn 为对象的非空有限集合 也称为论域 A a1 a2 am 为属性的非空有限集合 V为属性值域 f U AV为一信息函数 当信息系统中属性A等于C并D 其中C为条件属性集 D为决策属性集时 信息系统也称为决策系统 决策表 等价关系举例 设信息系统如下表所示 对象为8辆汽车 条件属性分别为颜色 排放量和价格 决策属性为销售量 U a1 x1 x6 x2 x5 x8 x3 x4 x7 U a2 x1 x4 x2 x3 x6 x7 x5 x8 U a3 x1 x3 x5 x7 x8 x2 x6 x4 以上U a1 U a2 U a3取交集 得U C x1 x2 x3 x7 x4 x5 x8 x6 用决策属性d来划分 可得U d x1 x4 x2 x3 x7 x5 x6 x8 在每一等价类中 按现有的信息无法再区别开 例如 由所有的条件属性获得的信息无法区分x3与x7 也无法区分x5与x8 因而 这种知识是有粒度的 下近似和上近似 定义给定知识表达系统S 对于每个子集X U和一个等价关系R 可以根据R的基本集合描述来划分集合X R X x x U x R X R X x x U x R X R X 和R X 分别称为X的R下近似集和R上近似集 称BNR X R X R X 是X的边界域 若BNR X 则称X是粗糙的 下近似集是在那些所有的包含于X的知识库中的集合中求并得到的 而上近似则是将那些包含X的知识库中的集合求并得到的 正域 负域和边界域 POS X R X 称为集合X的R 正域 NEG X U R X 称为集合X的R 负域 集合的下近似是包含给定集合中所有基本集的集合 也就是所有一定能归入X的元素的集合 集合的上近似是包含给定集合元素中所有基本集的最小集合 上近似表示在知识R下 U中可能归入X的元素的集合 边界域表示在知识R下 U中既不能肯定归入X也不能肯定归入 X的元素的集合 关于正域的理解 把下近似求并 就是正域 举例 设属性Headache a1 Muscle pain a2 Temperature a3 Flu d 表中所有实例构成论域U U e1 e2 e3 e4 e5 e6 现设有一概念X e1 e2 e3 e4 e5 对于关系R 若R仅考虑属性a1 a2 则用R对U划分可得到如下不可区分的实例集合 U a1 e1 e2 e3 e4 e5 e6 U a2 e1 e2 e3 e4 e6 e5 U R e1 e2 e3 e4 e6 e5 这些集合称为基本集 U R中 肯定属于X的集合为下近似 R X e1 e2 e3 e5 e1 e2 e3 e5 U R中 所有有可能属于X的集合为上近似 R X e1 e2 e3 e4 e6 e5 UBNR X e4 e6 因此可以称X是R 粗糙集 当上近似等于下近似时 称集合X关于R是清晰的 当两者不相等时 称集合X关于R是粗糙的 yes yes no no e1 e2 e3 e5 e4 e6 上下近似实例 图 下近似也就是正域 正域外面的是负域 粗糙集首先从新的视角对知识进行了定义 把知识看作是关于论域的划分 从而认为知识是具有粒度 granularity 的 认为知识的不精确性是由知识粒度太大引起的 为处理数据 特别是带噪声 不精确或不完全数据 分类问题提供了一套严密的数学工具 使得对知识能够进行严密的分析和操作 又由于数据挖掘的深入研究和一些成功的商业运作 使得粗糙集理论和数据挖掘有了天然的联系 粗糙集在知识上的定义 属性约简 规则提取等理论 使得数据库上的数据挖掘有了深刻理论基础 从而为数据挖掘提供了一种崭新的工具 粗糙集不仅自己可以独特的挖掘知识 而且可以和其他的数据挖掘算法结合起来 从而产生了学多混合数据挖掘算法 大大开拓了数据挖掘的算法和技术 丰富了数据挖掘的工具 粗糙隶属函数 定义 信息系统论域中元素x对集合X的粗糙隶属函数定义为 粗糙隶属函数表示在关系R下 元素x对集合X的隶属程度 显然在0到1之间 绝对值符号称为集合的基数cardiny 粗糙隶属函数举例 U C 1 6 2 3 4 7 5 6 8 U d 1 2 6 7 3 4 5 8 X1 X2 求 x1 4 和 x1 7 所以 依赖度 依赖度表示在条件属性集C下 能确切地划入决策分类U D的对象占论域中的总对象数的比率 属性重要度 设有决策系统S U C D C f 其中 C D分别为条件属性和决策属性集 属性子集C 的属性重要度定义为 C D C C D C C D 当C 是属性 也可以有类似定义 可理解为 如果去掉属性 分类U D的正域受到的影响 属性约简 属性约简是粗糙集理论中的核心内容之一 决策表中的属性并不是同等重要的 甚至有些属性是冗余的 所谓属性约简 就是保持决策表条件属性和决策属性之间的依赖关系不变的前提下 删除其中的不相关或不重要的属性 定义 设有决策系统S U C D V f 若POSC D POSC D 则称属性 为C中D可省略的 否则属性 为C中D不可省略的 去掉 之后 正域不变 说明 是可以省略的 定义 对于一个给定的决策系统 条件属性集C的D约简是C的一个非空子集P 若满足1 对于P中的任何一个 都是D不可省略的 2 POSP D POSC D 则称P是C的一个约简 C中所有约简的集合记作REDD C 核 core C中所有不可省略属性的集合成为C的核 记为CORED C 则CORED C REDD C 决策表中的属性约简是指属性的最小不可省略子集 而属性的核是指最重要的属性集 属性的核可以是空集 决策规则的准确度 对于规则 所有具有属性 和决策 的规则的总数称为规则的支持数 support 在属性 的基础上 能得到决策 的准确性 称为决策规则的准确度 accuracy Accuracy support support 由条件 得到 的数量除以所有能得到 的数量 算例分析 求属性约简及决策规则 U c1 x1 x2 x3 x4 x5 x6 x7 x8 U c2 x1 x2 x3 x4 x6 x8 x5 x7 U c3 x1 x4 x2 x5 x7 x3 x6 x8 U C x1 x2 x3 x4 x5 x7 x6 x8 U d x1 x4 x5 x8 x2 x3 x6 x7 下近似R d1 x1 x4 下近似R d2 x2 x3 POSc D x1 x2 x3 x4 依赖度 4 8 0 5 令C C c1 c2 c3 U C x1 x4 x2 x3 x6 x8 x5 x7 d1 x1 x4 x5 x8 d2 x2 x3 x6 x7 R d1 x1 x4 R d2 x2 POSC c1 D x1 x2 x4 不等于POSc D U C 的某子集 元素与d1的交集仍然等于U C 的该子集 元素 则该子集 元素为下近似的一个子集或元素 令C C c2 c1 c3 U C x1 x2 x3 x4 x5 x7 x6 x8 d1 x1 x4 x5 x8 d2 x2 x3 x6 x7 R d1 x1 x4 R d2 x2 x3 POSC c2 D x1 x2 x3 x4 等于POSc D 令C C c3 c1 c2 U C x1 x2 x3 x4 x6 x8 x5 x7 d1 x1 x4 x5 x8 d2 x2 x3 x6 x7 R d1 R d2 POSC c3 D 不等于POSc D 令C 4 C c1 c2 c3 U c3 x1 x4 x2 x5 x7 x3 x6 x8 d1 x1 x4 x5 x8 d2 x2 x3 x6 x7 R d1 x1 x4 R d2 POSC c1 c2 D x1 x4 不等于POSc D 令C 5 C c2 c3 c1 U c1 x1 x2 x3 x4 x5 x6 x7 x8 d1 x1 x4 x5 x8 d2 x2 x3 x6 x7 R d1 R d2 POSC c2 c3 D 不等于POSc D 令C 6 C c1 c3 c2 U c2 x1 x2 x3 x4 x6 x8 x5 x7 d1 x1 x4 x5 x8 d2 x2 x3 x6 x7 R d1 R d2 POSC c1 c3 D 不等于POSc D c1 c3 是条件属性集C的D约简 并且属性约简唯一 决策规则 共有4条确定性决策规则 r1 c1 1 c3 1 d 0 r2 c1 1 c3 2 d 1 r3 c1 1 c3 3 d 1 r4 c1 0 c3 1 d 0 决策规则 共有4条不确定性规则 r5 c1 1 c3 2 d 0 r7 c1 1 c3 2 d 1 r6 c1 0 c3 3 d 1 r8 c1 0 c3 3 d 0 确定性因子为0 5 准确度为0 5 准确度举例 支持数和准确度的结果 小结 根据属性约简得到规则 规则的可信度由规则的支持数和准确度来衡量 练习 在航空兵部队中 飞机备件一般分为初始备件和后续备件 初始备件与后续备件的管理有所不同 因此 确定哪些备件为初始备件很重要 下表是决策信息表 其中对象为飞机器材 条件属性C a1 a2 a3 a4 分别为器材的关键性 故障修理间隔时间 MTBF 故障发生间隔时间 MTTR 及费用 决策属性d 是 否 分别表示该器材是否确定为初始备件 U a1 1 2 6 3 4 7 8 5 U a2 1 3 6 2 4 7 5 8 U a3 1 6 2 3 4 7 8 5 U a4 1 6 2 5 3 4 7 8 U C 1 6 2 3 4 7 5 8 U d 1 2 6 7 3 4 5 8 R d1 1 2 6 R d1 1 2 4 6 7 BNR d1 4 7 U C 1 6 2 3 4 7 5 8 U d 1 2 6 7 3 4 5 8 R d2 3 5 8 R d2 3 4 5 7 8 BNR d2 4 7 POSR d1 1 2 6 POSR d2 3 5 8 POSC d 1 2 3 5 6 8 练习 考虑以下决策系统 系统对象U 1 2 3 4 5 条件属性C a1 a2 a3 决策属性D d 求其约简与核 解 U a1 1 4 5 2 3 U a2 1 2 3 4 5 U a3 1 3 4 2 5 U C 1 2 3 4 5 U d 1 4 2 3 5 R d1 1 4 R d2 2 R d3 3 5 POSc d 1 2 3 4 5 U C a2 1 4 2 3 5 其正域为 1 2 3 4 5 所以可以删除a2 U C a1 1 2 3 4 5 其正域为 1 2 3 4 5 所以可以删除a1 得到2个约简 a1 a3 a2 a3 它们维持了原有条件属性C相同的分类能力 2个约简的交集是 a3 核是 a3 多值决策系统 设有决策系统S U A V f 其中U x1 x2 xn 为对象集 称为论域 A是属性集 A C D C为条件属性集 D为决策属性集 V为属性值集 其中VC Va a C 是条件属性值集 VD Vd d C 是决策属性值集 f U A V为一个信息函数 表示对每一个a A x U f x a Va 如果对于条件属性值vij Va Va是由几个属性值组成 并假定决策属性值为单值 则S为多值决策系统 多值决策系统的相容粗糙集 解读 两个对象 如果它们的所有属性的取值的交集不为空 则它们是相容关系 不完备决策系统的粗糙决策 定义 设有决策系统S U A V f 其中U为论域 A为属性集合 A C D C为条件属性集 D为决策属性集 V为属性值集 其中VC Va a C 是条件属性值集 VD Vd d C 是决策属性值集 f U A V为一个信息函数 表示对每一个a A x U f x a Va 如果至少有一个a C Va中包含空值 则称S为不完备决策系统 表示空值 相容关系 由相容关系SIM P 对论域U进行的划分可以表示为U SIM P 每一个划分称为一个相容类 相容类之间可能是子集 也可能重叠 但所有相容类的并集一定等于U Sp x 表示与x相容的所有对象的集合 对不完备决策系统相容关系的解读 对于两个对象 如果它们的所有属性的取值都相等 或者属性值为空值 则它们是相容关系 相容关系的下近似与上近似 求多值决策系统的相容粗糙集 X 1 2 3 4 5 6 7 8 C 1 2 3 U C 1 4 2 6 7 3 5 8 X的下近似 C X 1 4 8 X的上近似 多值决策系统和不完备决策系统的属性约简 多值决策系统和不完备决策系统的属性约简可以用差别矩阵及差别函数来求得 差别矩阵 如果属性集A C D 其中C为条件属性集 D为决策属性集 则可以定义 C D 差别矩阵如下 解读 如果两条记录的条件属性值和决策属性值都不相等 则差别矩阵的元素为属性值不同的条件属性的组合 如果条件属性值或决策