你好,游客 登录 注册 发布搜索
背景:
阅读文章:

粗糙集的约简算法

[收录:2013-09-04] [作者:王金诚 李德胜 李忠杰] [服务:论文代写代发] [字体: ]
内容摘要:

粗糙集的约简算法,摘要:粗糙集理论作为数据挖掘的一种有效的手段,现已成为学术界的一个前沿研究领域。本文概要介绍RS核心思想、基本概念;对各种约简算法进行了描述。

关键词:粗糙集;数据挖掘;离散与约简

网络信息时代,如何从杂乱无章的海量数据中挖掘潜在的有利用价值的信息,这给人类的智能信息处理提出了前所未有的挑战,由此产生了人工智能的一个崭新领域——数据挖掘(DM)和数据库知识发现(KDD)。在数据挖掘和数据库知识发现的诸多研究方法中解决不确定性和不完备的问题,应用得最广泛的是概率论、模糊集、证据理论和粗糙集理论以及这些方法的相互渗透和补充。本文由教育大论文下载中心WwW.JiaoYuDa.CoM整理

粗糙集理论具有一些独特的观点特别适合于进行数据分析,与其他软件计算工具相比,粗糙集不需要预先给定某些特征或属性的数量描述,即参数,如统计学中的概率分布、模糊集理论中的隶属函数等,而是直接从给定的信息出发,通过不可分辨关系确定问题的近似域,找到隐含在数据中的内在规律。

在知识表达系统中,知识(属性)并不是同等重要的,甚至某些知识是冗余的。属性约简的任务就是在保持知识表达系统中分类能力不变的情况下,删除其中不相关或不重要的知识。

定义1 一个知识表达系统是一个四元组 ,其中U={ }为对象的非空有限集,称为论域; 为属性的非空有限集, , 是属性 的值域: 是一个信息函数,它为每个对象的每个属性赋予一个信息值,即 。知识表达系统也称为信息系统。通常也用 来表示。如果 有条件属性 和决策属性 组成。且满足 ,则称 为一决策系统。知识表达系统的数据以关系表的形式表示,其中行表示对象,列表示属性。对象的信息是通过指定对象的各属性值来表达。

定义2 知识表示系统 对于任意属性 。若满足 ,则称 为 中关于 不必要的。否则称为 中关于 必要的,其中 表示利用不可分辨 关系能正确地划分到 各等价类的所有对象的集合,即由 导出的等价类关于的 正域。如果 中的每个属性 都是必要的,则称 为 独立的.

定义3知识表示系统 , ,若 且 是 独立的,则称 为 相对于 的约简。记为redD(C)。需要指出 的约简是不唯一的, 的所有约简的交集,称为 的 核,记为 [3]。

约简是粗糙集用于数据分析的重要概念,然而最小约简的计算是NP-hard的。因此运用启发信息来简化计算是必要的。事实上,计算最小约简的问题有些类似于机器学习中的最小属性子集问题,如前所述粗糙集中的约简计算可转化成布尔函数化简问题,因此可以使用许多布尔函数化简中的技巧及算法。这里我们介绍一些典型算法。

算法1(基本算法) 基本算法首先构造区分矩阵。在区分矩阵的基础上得出区分函数然后应用吸收律对区分函数进行化简,使之成为析取范式,则每个主蕴含是均为约简。基本算法可以求出所有约简,但是只适合于非常小的数据集,基本算法的时间复杂度为O(2|x||A||U|lg|U|)。

算法 2(属性的重要性) 由Hu.X提出。该算法非常简单和直观。他使用核作为计算约简的出发点。计算一个最好的或者用户指定的最小约简。算法将属性的重要性作为启发规则。首先按照属性的重要程度从小到大逐个加入属性,直至该集合是一个约简为止。接着检查该集合中的每个属性,看移走该属性是否会改变该集合的对决策属性的依赖度。如果不影响,则将其删除。此算法的最坏复杂度在O(|A|2|A||U|lg|U|)。因为循环的执行次数最多为|A|,而求属性间的依赖程度的复杂度和计算正区域相同。

打印 | 录入:meihua | 阅读:1
本文评论   查看全部评论 (0)
表情: 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款
站内搜索:
本站搜索:
搜索文章:
关键词论文内容作者