学位论文 > 优秀研究生学位论文题录展示

不完备决策表求核算法研究

作　者: 曾艳燕
导　师: 徐章艳
学　校: 广西师范大学
专　业: 计算机应用技术
关键词: 核粗糙集差别矩阵知识粒度区分对象对
分类号: TP18
类　型: 硕士论文
年　份: 2012年
下　载: 36次
引　用: 0次
阅　读: 论文下载

内容摘要

在网络信息爆炸的时代,如何从大量的、杂乱无章的数据中发现潜在的、有价值的、简洁的知识已经成为当代人面临的重要问题。粗糙集理论作为一种能够对不完全和不确定信息进行处理的数学工具,被广泛应用于数据挖掘和人工智能等领域。与其他数学处理工具比起来,粗糙集理论的优势是在对海量信息进行处理加工的时候,不需要其他附加信息或先验知识,可直接对信息进行处理加工,找出人们所要的信息中隐含的知识。本文主要研究粗糙集理论中的对不完备决策表的求核,属性约简也是粗糙集理论的重要研究内容之一。核是决策表中所有属性约简的交集,一般求出的核都是由对决策表具有区分作用的重要属性组成,属性约简可以在已求出的核属性集的基础上通过启发信息扩展到最小约简。属性约简的主要目的是简化知识库中的知识,在保持知识库中的知识分类能力不变的情况下,减小知识库的规模,以尽可能少的属性对知识库进行分类。当前,研究者提出的大部分求核算法都是基于完备决策表,但是在实际应用中,由于人为的一些测量误差或数据获取时的限制等原因,获取到的信息系统大多都是不完备的,即信息系统中有些对象在有些属性上的取值是未知的。而对不完备决策表进行处理时,已研究出来的对完备决策表进行处理的粗糙集理论将不再适用。因此,研究对不完备决策表进行求核具有更实用的意义,更适合于运用到实际工作中。粒度计算是在人工智能领域新兴起的一个研究方向,它主要用来处理部分真的和海量信息及不确定的、不精确的、模糊的信息,核心思想是利用属性的不同粒度对问题进行求解。本文研究了对不完备决策表的求核算法,通过对粗糙集理论基础知识及当前研究人员研究出来的对完备决策表及不完备决策表进行核和属性约简的求解的算法研究及学习,文章对不完备决策表进行求核的创新点如下：(1)针对不完备决策表,提出不完备决策表的二进制差别矩阵构造方法,根据对象在不同属性下的确定值对对象进行划分,对对象在属性下的未知值则不考虑。在该差别矩阵的基础上,给出了一种对不完备决策表进行求核的算法,为不完备决策表处理提供了一种新的方法。(2)通过引入知识粒度的概念,提出了粒度二进制差别矩阵的构造方法。根据属性重要性的定义及核的定义,设计了基于粒度二进制差别矩阵的不完备决策表求核算法,其时间复杂度为max{O(|C‖U‖Upos｜),O(K｜C‖U|)}。优于同类算法的时间复杂度。(3)在知识粒度差别矩阵的基础上,利用区分对象对的思想对完备决策表进行处理,提出不完备决策表区分对象对集的定义,在此基础上提出了一种基于知识粒度区分对象对的不完备决策表求核算法,算法的时间复杂度为：max{O(｜C‖U‖Upos|),O(K|C‖U｜)},优于同类算法的时间复杂度。(4)传统的基于差别矩阵的决策表的求核,都是直接求出决策表的所有差别矩阵,不仅浪费存储空间而且浪费时间,为了解决这个问题,同时又用到差别矩阵的思想,在这里引入不完备决策表差别矩阵的及其核的定义,在此基础上,提出了不完备决策表的条件属性区分对象对集定义,给出了一种基于不完备决策表的区分对象对集求核算法。这里求出的区分对象对的个数远远小于差别矩阵元素个数,大大减少了计算差别矩阵的计算量及存储空间。

全文目录

摘要  3-5
Abstract  5-9
1 绪论  9-12
  1.1 国内外研究现状  9-10
    1.1.1 粗糙集理论的产生和发展  9
    1.1.2 粗糙集理论的研究内容及其应用  9-10
    1.1.3 粗糙集理论的特点  10
  1.2 论文研究的目的和意义  10-11
  1.3 论文的主要创新点  11
  1.4 论文的组织和安排  11-12
2 粗糙集理论基础  12-20
  2.1 完备决策表中的基本概念和相关定义  12-16
    2.1.1 知识表示及决策表的相关知识  12-14
    2.1.2 求核和属性约简的定义  14-15
    2.1.3 基于正区域的属性约简定义及相应核的定义  15
    2.1.4 基于信息熵的属性约简定义及相应核的定义  15-16
    2.1.5 基于Skowron差别矩阵的属性约简定义及相应核的定义  16
  2.2 不完备决策表中的基本概念和相关定义  16-17
  2.3 知识粒度的相关定义  17-18
  2.4 不完备决策表中的求核相关定义  18-19
    2.4.1 基于知识粒度的不完备决策表核相关定义  18
    2.4.2 基于正区域的不完备决策表核相关定义  18-19
    2.4.3 基于二进制差别矩阵的不完备决策表核相关定义  19
  2.5 本章小结  19-20
3 基于二进制差别矩阵的不完备决策表求核方法  20-28
  3.1 基于二进制差别矩阵的常见求核算法  20-21
  3.2 一种基于二进制差别矩阵的不完备决策表求核算法  21-26
    3.2.1 设计思想  21
    3.2.2 相关定义和证明  21-23
    3.2.3 基于二进制差别矩阵的求核算法  23-24
    3.2.4 实例分析  24-26
  3.3 本章小结  26-28
4 基于知识粒度的不完备决策表求核方法  28-34
  4.1 基于知识粒度的不完备决策表常见求核算法  28
  4.2 一种基于知识粒度的不完备决策表求核算法  28-33
    4.2.1 设计思想  28-29
    4.2.2 相关定义和证明  29-30
    4.2.3 基于知识粒度的求核算法  30-31
    4.2.4 实例分析  31-33
  4.3 本章小结  33-34
5 基于区分对象对的不完备决策表求核  34-46
  5.1 基于区分对象对的常见求核算法  34-35
  5.2 一种基于区分对象对的不完备决策表求核算法  35-40
    5.2.1 设计思想  35
    5.2.2 相关定义与证明  35-38
    5.2.3 基于区分对象对的求核算法  38-39
    5.2.4 实例分析  39-40
  5.3 基于差别矩阵的区分对象对集的不完备决策表求核算法  40-45
    5.3.1 设计思想  40
    5.3.2 相关定义与证明  40-43
    5.3.3 基于差别矩阵的区分对象对集的求核算法  43-44
    5.3.4 实例分析  44-45
  5.4 本章小结  45-46
6 结论与展望  46-48
  6.1 全文总结  46-47
  6.2 未来工作  47-48
参考文献  48-52
在学研究成果  52-53
致谢  53-54

不完备决策表求核算法研究

内容摘要

全文目录

相似论文