粗糙集理论及其应用 浙江大学人工智能研究所.pptVIP

粗糙集理论及其应用Rough Set Theory and its Applications 徐从富 浙江大学人工智能研究所 2002年11月8日第一稿 2005年9月修改补充 目录： Rough set快速入门方法 Rough set发展概述 Rough set理论 课后习题 课后研读论文 Rough set快速入门方法 认真研读Rough Set Theory的创始人、波兰数学家Z. Pawlak于1982年发表的第一篇论文“Rough Sets”。最好是直接阅读英文论文原文。 研读中科院自动化所的王珏等人于1996年在《模式识别与人工智能》上发表介绍粗糙集理论及其应用的综述性文章。 结合中科院计算所史忠植教授编著的《高级人工智能》、《知识发现》等教材中的讨论粗糙集的章节。 ? 一个申请信用卡的训练集： ? 申请人 编号 条件属性 ? 决策属性 d c1 账号 c2 余额 c3 职业 c4 月消费 1 银行 中(700) 有 低 接受 2 银行 低(300) 有 高 拒绝 3 无 低(0) 有 中 拒绝 4 其它机构 高(1200) 有 高 接受 5 其它机构 中(800) 有 高 拒绝 6 其它机构 高(1600) 有 低 接受 7 银行 高(3000) 无 中 接受 8 无 低(0) 无 低 拒绝 ? 原始属性集A = {c1, c2, c3, c4}的分类质量： 令R = {c2, c4}，重新计算分类质量 ，得 2.2.5 属性约简及“核” 属性约简(Attribute Reduction，简称AR)是粗糙集理论的一个重要概念。在一个信息系统S中，设?是S上的一个分类，经约简后的最小属性子集具有同原始属性集相同的分类质量，即存在R?P?Q，使得?R(?)=?P(?) ，称之为属性集P的?-约简，记作REDU?(P)。所有?-约简的交集称为?-核，即CORE?(P) = ?REDU?(P)，核是信息系统中一系列最重要的属性。 在大多数情况下，分类是由几个甚至一个属性来决定的，而不是由关系数据库中的所有属性的微小差异来决定。属性约简及核的概念为人们提取系统中重要属性及其值提供了有力的数学工具，而且这种约简是本着不破坏原始数据集的分类质量的，通俗地说，它是完全“保真”的。 关于核的计算，有人提出了差别矩阵（discernibility matrix，也译作可辨识矩阵）。在信息系统S = (U, C?D, V, f)中，C为条件属性，D为决策属性，设为对象全集U按决策属性D被分成不相交的类族，即 = {X1,X2,…,Xm}，则S中C的差别矩阵M(C) = {mi,j}nxn定义为 其中，1 ? i ? j ? n。 差别矩阵与信息系统的核有如下关系：对所有的c?C, c?CORE(C,D)的充要条件是，存在i, j(1 ? i ? j ? n)，使得mi,j = {c}。“含糊”是指分别属于两个不同类的对象具有完全相同的条件属性，在差别矩阵中，xi, xj是含糊的充要条件是存在i, j(1 ? i ? j ? n)，使得mi,j = {-1}。 ? 申请人 编号 条件属性 ? 决策属性 d c1 账号 c2 余额 c3 职业 c4 月消费 1 银行 中(700) 有 低 接受 2 银行 低(300) 有 高 拒绝 3 无 低(0) 有 中 拒绝 4 其它机构 高(1200) 有 高 接受 5 其它机构 中(800) 有 高 拒绝 6 其它机构 高(1600) 有 低 接受 7 银行 高(3000) 无 中 接受 8 无 低(0) 无 低 拒绝 因决策d = {接受，拒绝}，故上表按决策属性d可分为两个等价类：{x1, x4, x6, x7}和{x2, x3, x5, x8}。根据差别矩阵的计算公式可得： 差别矩阵与“核”有如下关系：属性c是条件属性C和决策属性D的“核”的充要条件是，存在i, j(1ijn)，使得mij = {c}。由上述矩阵可知，存在i=4, j=5，使得m4,5 = {c2}，故表1的“核”为{c2}。 实例：考虑下面的决策表5，条件属性为a,b,c,d，决策属性为e。 U/A a b c d e u1 1 0 2 1 0 u2 0 0 1 2 1 u3 2 0 2 1 0 u4 0 0 2 2 2 u5 1 1 2 1 0 u u1 u2 u3 u4 u5 u1 ? ? ?