粗糙集理论及其应用.ppt

2020 4 19 1 粗糙集理论及其应用 2020 4 19 2 主要内容 粗糙集发展历程粗糙集的基本理论介绍 粗糙集的属性约简算法研究 粗糙集的扩展模型在文本分类中的应用现有工具简介 2020 4 19 3 粗糙集发展历程 1970s pawlak和波兰科学院 华沙大学的一些逻辑学家 在研究信息系统逻辑特性的基础上 提出了粗糙集理论的思想 在最初的几年里 由于大多数研究论文是用波兰文发表的 所以未引起国际计算机界的重视 研究地域仅限于东欧各国 1982年 pawlak发表经典论文 roughsets 标志着该理论正式诞生 1991年 pawlak的第一本关于粗糙集理论的专著 roughsets theoreticalaspectsofreasoningaboutdata 2020 4 19 4 粗糙集发展历程 1992年 slowinski主编的 intelligencedecisionsupport handbookofapplicationsandadvancesofroughsetstheory 的出版 奠定了粗糙集理论的基础 有力地推动了国际粗糙集理论与应用的深入研究 1992年 在波兰召开了第一届国际粗糙集理论研讨会 有15篇论文发表在1993年第18卷的 foundationofcomputinganddecisionsciences 上 1995年 pawlak等人在 acmcommunications 上发表 roughsets 极大地扩大了该理论的国际影响 2020 4 19 5 粗糙集发展历程 1996 1999年 分别在日本 美国 美国 日本召开了第4 7届粗糙集理论国际研讨会 2001 2002 中国分别在重庆 苏州召开第一 二届粗糙集与软计算学术会议 2003年 在重庆召开粗糙集与软计算国际研讨会 2004年 在瑞典召开rsctc国际会议 年会 2005年 在加拿大召开rsfdgrc国际会议 年会 2020 4 19 6 主要内容 粗糙集发展历程粗糙集的基本理论介绍 粗糙集的属性约简算法研究 粗糙集的扩展模型在文本分类中的应用现有工具简介 2020 4 19 7 粗糙集的基本理论介绍 主要优点除数据集之外 无需任何先验知识 或信息 对不确定性的描述与处理相对客观 说明 bayes理论 先验分布 证据理论 隶属度函数 等都需要先验知识 具有很大的主观性 2020 4 19 8 粗糙集理论在知识发现中的作用 在数据预处理过程中 粗糙集理论可以用于对特征更准确的提取在数据准备过程中 利用粗糙集理论的数据约简特性 对数据集进行降维操作 在数据挖掘阶段 可将粗糙集理论用于分类规则的发现 在解释与评估过程中 粗糙集理论可用于对所得到的结果进行统计评估 2020 4 19 9 粗糙集理论的基本概念 知识 的定义使用等价关系集r对离散表示的空间u进行划分 知识就是r对u划分的结果 知识库 的形式化定义等价关系集r中所有可能的关系对u的划分表示为 k u r 2020 4 19 10 粗糙集理论的基本概念 信息系统 的形式化定义s u a v f u 对象的有限集a 属性的有限集 a c d c是条件属性子集 d是决策属性子集v vp是属性p的域f u a v是总函数 使得对每个xi u q a 有f xi q vq一个关系数据库可看作一个信息系统 其 列 为 属性 行 为 对象 2020 4 19 11 粗糙集理论的基本概念 设p a xi xj u 定义二元关系ind p 称为等价关系 称xi xj在s中关于属性集p是等价的 当且仅当p xi p xj 对所有的p p成立 即xi xj不能用p中的属性加以区别 2020 4 19 12 等价关系示例 2020 4 19 13 等价关系示例 可知 u 1 2 3 4 5 6 r 2 weather road time accident 若p weather road 则 x ind p x ind weather x inp road 1 3 6 2 5 4 1 2 4 3 5 6 1 2 4 3 6 5 2020 4 19 14 集合的上近似 下近似 在信息系统s u a v f 中 设x u是个体全域上的子集 p a 则x的下和上近似集及边界区域分别为 x是x u上必然被分类的那些元素的集合 即包含在x内的最大可定义集 x是u上可能被分类的那些元素的集合 即包含x的最小可定义集 bndp x 是既不能在x u上被分类 又不能在u x上被分类的那些元素的集合 2020 4 19 15 集合的上 下近似概念示意图 x 2020 4 19 16 上 下近似关系举例 x1 u flu u yes u2 u3 u6 u7 rx1 u2 u3 u2 u3 u6 u7 u5 u8 x2 u flu u no u1 u4 u5 u8 rx2 u1 u4 u1 u4 u5 u8 u6 u7 由r headache temp 划分出来的等价类有 u1 u2 u3 u4 u5 u7 u6 u8 2020 4 19 17 近似精度 分类质量 设s u a v f 为一信息系统 且x u p a 则s上x的近似精度为 注 card x 表示集合x中元素个数设s为一信息系统 p a 且令 x1 x2 xn 是u的一个分类 子集族 其中xi u 则 的p 下近似和p 上近似分别表示为 2020 4 19 18 近似精度 分类质量 由属性子集p a确定的分类 的分类质量为 分类质量表示通过属性子集p正确分类的对象数与信息系统中所有对象数的比值 这是评价属性子集p的重要性的关键指标之一 2020 4 19 19 属性约简 核 属性约简 attributereduction 在一个信息系统s中 设 是s上的一个分类 经约简后的最小属性子集具有同原始属性集相同的分类质量 即存在r p q 使得 r p 称之为属性集p的 约简 记作redu p 所有 约简的交集称为 核 即core p redu p 核是信息系统中一系列最重要的属性之一 说明 在大多数情况下 分类是由几个甚至一个属性来决定的 而不是由关系数据库中的所有属性的微小差异来决定 属性约简及核的概念为提取系统中重要属性及其值提供了有力的数学工具 而且这种约简是本着不破坏原始数据集的分类质量的 通俗地说 它是完全 保真 的 2020 4 19 20 主要内容 粗糙集发展历程粗糙集的基本理论介绍 粗糙集的属性约简算法研究 粗糙集的扩展模型在文本分类中的应用现有工具简介 2020 4 19 21 利用区分矩阵进行属性约简 区分矩阵 discernibilitymatrix 在信息系统t u c d v f 中 c为条件属性 d为决策属性 设对象全集u按决策属性d被分成不相交的类族 即 x1 x2 xm 则s中c的区分矩阵m c mi j nxn定义为 其中 1 i j n 2020 4 19 22 利用区分矩阵进行属性约简 令m是决策表t的可辨识矩阵 a a1 a2 an 是t中所有条件属性的集合 s是m中所有属性组合的集合 且s中不包含重复项 令s中包含有s个属性组合 每个属性组合表示为bi 其公式化描述为 bi s bj s bi bj i j 1 2 s 令card bi m 则bi中每个条件属性表示为bi k bi k 1 2 m 令c0是m中的核属性集 则有c0a 2020 4 19 23 利用区分矩阵进行属性约简 算法步骤 第1步 将核属性列入属性约简后得到的属性集合 即red c0 第2步 在可辨识矩阵中找出所有不包含核属性的属性组合s 即第3步 将属性组合s与red表示为合取范式的形式 即p red bi k i 1 2 s k 1 2 m 第4步 将p转化为析取范式形式 第5步 根据需要选择满意的属性组合 如需属性数最少 可直接选择合取式中属性数最少的组合 如需规则最简或数据约简量最大 则需先进行属性值约简 观看演示 2020 4 19 24 利用区分矩阵进行属性约简 实例 t u a v f a a b c d e 2020 4 19 25 a c d a d a c d a d a b d 利用区分矩阵进行属性约简 区分矩阵 2020 4 19 26 利用区分矩阵进行属性约简 由上述差别矩阵很容易得到核为 c 区分函数fm s 为 c a d 即 a c c d 得到两个约简 a c 和 c d 2020 4 19 27 利用区分矩阵进行属性约简 根据得到的两个约简 可得两个约简后的新决策表 2020 4 19 28 利用启发式搜索进行属性约简 几个概念 正区域 在信息系统s u c d v f 中 设d x1 x2 xm 属性子集p c关于决策属性d的 正区域 定义为 p关于d的正区域表示那些根据属性子集p就能分入正确类别的所有对象 2020 4 19 29 利用启发式搜索进行属性约简 相关程度 条件属性子集p c与决策属性d的相关程度 也称依赖程度 定义为 显然 0 k p d 1 k p d 为计算条件属性子集p与决策属性d之间的相关程度提供了非常有力的手段 2020 4 19 30 利用启发式搜索进行属性约简 有效值 一个属性p p c的有效值 significantvalue 定义为 说明 属性p的有效值越大 说明其对条件属性与决策属性之间的影响越大 即其重要性也越大 2020 4 19 31 利用启发式搜索进行属性约简 性质1 若m n c 则posm d posn d 性质2 m n c x u 则对任意x u 若x posm d 则x posn d 2020 4 19 32 利用启发式搜索进行属性约简 算法步骤 第1步 a a 计算邻域关系 a 第2步 将 赋给red 第3步 对任意ai a red 计算 此处定义k d 0第4步 选择ak 其满足 sig ak red d maxi sig ai red d 第5步 如果sig ak red d 0 将reduak赋给red 返回第3步 否则 返回red 结束 观看演示 2020 4 19 33 主要内容 粗糙集发展历程粗糙集的基本理论介绍 粗糙集的属性约简算法研究 粗糙集的扩展模型在文本分类中的应用现有工具简介 2020 4 19 34 经典粗糙集存在的问题 经典粗糙集理论的主要存在的问题是 1 对原始数据本身的模糊性缺乏相应的处理力 2 对于粗糙集的边界区域的刻画过于简单 3 对属性为连续数值的情况缺乏好的解决办法 2020 4 19 35 可变精度粗糙集模型 w ziarko提出了一种称之为可变精度粗糙集模型 该模型给出了错误率低于预先给定值的分类策略 定义了该精度下的正区域 边界区域和负区域 下面扼要地介绍其思想 一般地 集合x包含于y并未反映出集合x的元素属于集合y的 多少 为此 vprs定义了它的量度 c x y 1 card x y card x 当card x 0 c x y 0当card x 0 c x y 表示把集合x归类于集合y的误分类度 即有c x y 100 的元素归类错误 显然 c x y 0时有x y 如此 可事先给定一错误分类率 0 0 5 基于上述定义 我们有x y 当且仅当c x y 2020 4 19 36 可变精度粗糙集模型 在此基础上 设u为论域且r为u上的等价关系 u r a x1 x2 ak 这样 可定义集合x的 下近似为r x xi c xi x i 1 2 k 并且r x称为集合x的 正区域 集合x的 上近似为r x xi c xi x 1 i 1 2 k 这样 边界区域就定义为 bnr x xi c xi x 1 负区域为 negr x xi c xi x 1 以此类推 我们还可以定义 依赖 约简等与传统粗糙集模型相对应的概念 2020 4 19 37 相似模型 在数据中存在缺失的属性值的时候 在数据库中很普遍 等价关系无法处理这种情形 为扩展粗糙集的能力 有许多作者提出了用相似关系来代替等价关系作为粗糙集的基础 在使用相似关系代替粗糙集的等价关系后 最重要的变化就是相似类不再形成对集合的划分了 它们之间是相互重叠的 类似于等价类 可以定义相似集 即所有和某各元素x在属性集合b上相似的集合simb x 值得注意的是simb x 中的元素不一定属于同一决策类 因此还需要定义相似决策类 即相似集对应的决策类集合 2020 4 19 38 邻域模型 作为一种有效的粒度计算模型 pawlak粗糙集定义在经典的等价关系和等价类基础上 只适合于处理名义型变量 对于现实应用中广泛存在的数值型数据却不能直接处理 在金融 医疗 科研和工程应用领域数值型变量无处不在 如振动分析中的频谱信号 变压器状态分析中的温度 电流 电压信号等 研究人员在引入粗糙集等机器学习方法来处理该类数据时 往往采用离散化算法把数值型属性转化为符号型属性 这一转换不可避免地带来了信息损失 计算处理的结果很大程度上取决于离散化的效果 2020 4 19 39 邻域模型 为解决上述问题 有人提出了邻域粗糙集模型 该模型以实数空间中的每一个点形成一个 邻域 邻域族构成了描述空间中任一概念的基本信息粒子 对于空间中的任一子集 通过基本邻域信息粒子进行逼近 并由此提出了邻域信息系统和邻域决策表模型 2020 4 19 40 主要内容 粗糙集发展历程粗糙集的基本理论介绍 粗糙集的属性约简算法研究 粗糙集的扩展模型在文本分类中的应用现有工具简介 2020 4 19 41 基于粗糙集的文本分类 利用可变精度粗糙集模型中的分类质量构造新的特征词权重计算公式 这种加权方法 相对于广泛使用的逆文本频率加权方法 大大改进了文本样本在整个空间中的分布 使得类内距离减少 类间距离增大 在理论上将提高样本的可分性 2020 4 19 42 逆文本频率加权 sparkjones提出的逆文本频率加权方法是目前广泛采用的一种 对于训练样本集k个文本u x1 x2 xk l个特征词t t1 t2 tl 加权公式为 2020 4 19 43 逆文本频率加权 n表示训练文本中出现第j个特征词的文本数 n代表所有训练文本的个数 第j个特征词的权重为log n n 表示的是特征词在越多的文本中出现 其对分类的区分性越差 其重要度则越小 如果此特征词在所有的文本中都出现了 则其加权值0 特征词的重要性正比于词频 反比于训练文本中出现该特征词的文本频率 2020 4 19 44 粗糙集加权 类比于逆文本频率权重计算公式 我们可以构造基于可变精度粗糙集模型的加权公式 wij表示第j个特征词在第i篇文本中的权重 tfij表示第j个特征词在第i篇文本中的出现频率 即特征词的局部权重 j u 为此特征词在整个语料库中对分类的重要程度 即全局权重 2020 4 19 45 粗糙集加权与逆文本频率加权的对比 逆