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

基于粗糙集的属性约简和求核的算法研究

作　者: 舒文豪
导　师: 徐章艳
学　校: 广西师范大学
专　业: 计算机软件与理论
关键词: 粗糙集属性约简核算法复杂度
分类号: TP18
类　型: 硕士论文
年　份: 2011年
下　载: 101次
引　用: 3次
阅　读: 论文下载

内容摘要

粗糙集理论是一种分析模糊、不精确和不确定信息的数学工具。其主要特点是它不需要任何先验的知识,或任何其它附加的信息,便可直接对海量数据进行处理加工,从中发现所隐含的知识,即决策规则。目前,粗糙集理论已经在数据挖掘,知识发现、智能决策、过程控制、人工智能和专家系统等领域得到了较为广泛的应用。属性约简和求核是粗糙集理论及应用的重要研究内容之一。属性约简是指在保持知识库中数据分类能力不变的情况下,删除知识库中不相关或冗余的属性,使得知识库中的知识表示可以简化,而且又不丢失知识库中的基本重要信息。如果能将知识库中的冗余属性删除,这样可有效缩小知识库的处理规模,从而提高潜在知识在知识库中的清晰度。但由于在对决策表进行属性约简时,大多数约简算法都是首先以核为基础,然后在核的基础上利用启发信息求解属性约简。为此,如何设计出高效的属性约简和求核算法具有重要的研究意义。目前,很多学者提出了多种属性约简的算法,绝大多数都是以完备决策表作为研究对象。然而在实际应用中由于数据的测量误差、对知识获取的限制等各种原因,人们往往面对的是不完备决策表,即决策表可能存在某些属性的属性值是未知的。如今基于不完备决策表的属性约简和求核算法已成为粗糙集理论中的热点研究内容之一。但由于目前不完备决策表的属性约简算法的时间复杂度相对较高,这样使得算法不利于处理大规模数据,所以如何设计出不完备决策表的快速属性约简算法具有广泛的实际意义。本文首先简要阐述有关粗糙集理论的基础理论知识,并系统地概述了目前基于完备决策表和基于不完备决策表的属性约简和求核的常见模型及其相关算法,然后在学习和借鉴已有研究成果的基础上,做出如下主要的创新点内容：1)根据简化决策表中的对象关于属性值是有序的及核是简化差别矩阵中差别元素个数为1这两个性质,利用基数排序的思想,设计了一种高效的基于正区域的求核算法,其时间复杂度为O(│C│2│U/C)+O(│C‖U│),其空间复杂度为O(|U|)。在该算法中,可将具有核属性的差别元素集映射到一个较小的搜索空间上,只需判断简化差别矩阵中的少量差别元素就可找到核属性集,这样算法的效率得到了改善。并通过实例分析表明了新算法的高效性。2)给出一个Skowron简化差别矩阵的核定义,并分析证明了该定义与和基于Skowron差别矩阵的核定义是相等的。为求解Skowron简化差别矩阵,引入了一个快速求简化决策表的算法。然后提出了一种新的可有效提高计算核属性算法的性质,在此基础上设计了基于Skowron差别矩阵的高效求核算法,算法的时间复杂度为O(│C‖U│)+O(│C│2U/C│),并通过实验结果显示了新算法的效率优于典型的两种算法。3)为了尽可能地减少差别矩阵的存储空间,而又能同时利用差别矩阵的设计思想,结合区分对象对的方法,设计了一个新的基于信息熵的属性约简算法,该算法无需去计算差别矩阵,但同时又利用了差别矩阵的思想。为了有效降低算法的复杂度,在简化决策表的基础上,给出了区分对象对集的属性约简的定义,并从理论上证明了该定义与基于信息熵的属性约简的定义等价。在此基础上设计了基于区分对象对集的信息熵属性约简算法,其时间复杂度和空间复杂度分别为：O(│C‖U│)+O(│C‖U/C│2),和O(|U/C|2)+O(|U|)。4)在不完备决策表中,利用容差类的性质将计算容差TC(x)的算法时间复杂度降为O(K│U‖C│),同时给出了一个基于正区域模型下的差别矩阵及相应的属性约简定义,证明了该定义与基于正区域的属性约简的定义是等价的。然后将不完备决策表下的基于正区域的属性约简建立在该差别矩阵上,且由于该差别矩阵无需比较Uneg之间的对象,使得差别矩阵得以简化。在此基础上,设计了基于正区域的属性约简算法,时间复杂度为max{O│C│2│Upas‖U│),O(K│U‖C│)。最后通过具体的实例说明了算法的有效性。5)在不完备决策表中,给出了一个基于广义决策模型下的差别矩阵及相应的属性约简的定义,证明分析了该定义与广义决策的属性约简的定义是等价的。并将差别矩阵进行了有效地压缩,去掉了大量无用的空值元素,使得差别矩阵中只保留对算法有用的元素,从而节省大量的存贮空间,提高算法的效率。然后利用相应的差别矩阵设计了基于广义决策的属性约简算法,将时间复杂度降至O(|C|2|U|2),最后通过具体的实例来说明算法的有效性。

全文目录

摘要  3-5
ABSTRACT  5-10
第1章绪论  10-14
  1.1 国内外研究现状  10-11
    1.1.1 粗糙集理论的产生与发展  10
    1.1.2 粗糙集理论的研究内容及其应用  10-11
  1.2 论文研究的目的和意义  11-12
  1.3 论文的主要创新点  12
  1.4 论文的组织和安排  12-14
第2章粗糙集理论知识  14-22
  2.1 基本概念  14-18
    2.1.1 知识表示  14-15
    2.1.2 信息系统与决策表  15
    2.1.3 集合的近似与粗糙集  15-17
    2.1.4 近似分类度量与属性依赖  17
    2.1.5 属性约简  17-18
  2.2 完备决策表中的相关定义  18-20
    2.2.1 基于正区域的属性约简定义及相应核的定义  18-19
    2.2.2 基于Skowron的属性约简定义及相应核的定义  19
    2.2.3 基于信息熵的属性约简定义及相应核的定义  19-20
  2.3 不完备决策表中的相关定义  20-21
    2.3.1 基于正区域的属性约简定义  20
    2.3.2 基于广义决策的属性约简定义  20-21
  2.4 本章小结  21-22
第3章完备决策表的求核算法  22-35
  3.1 基于正区域的求核算法  22-28
    3.1.1 基本定义  22
    3.1.2 基于正区域的求核常见算法  22-23
    3.1.3 一种新的基于正区域的高效求核算法  23-28
  3.2 基于Skowron差别矩阵的求核算法  28-34
    3.2.1 基于Skowron差别矩阵的求核常见算法  28-29
    3.2.2 一种新的基于Skowron差别矩阵的高效求核算法  29-34
  3.3 本章小结  34-35
第4章完备决策表的属性约简算法  35-45
  4.1 基于正区域的常见属性约简算法  35-36
  4.2 基于差别矩阵的常见属性约简算法  36-38
  4.3 基于信息熵的常见属性约简算法  38-39
  4.4 一种基于区分对象对的信息熵的属性约简算法  39-44
    4.4.1 设计思想  39-40
    4.4.2 相关定义及定理  40-41
    4.4.3 两种属性约简的等价性分析  41-42
    4.4.4 基于区分对象对的信息熵的属性约简算法  42-43
    4.4.5 实例分析  43-44
  4.5 本章小结  44-45
第5章不完备决策表的属性约简算法  45-58
  5.1 一种快速的基于正区域的属性约简算法  45-52
    5.1.1 设计思想  45
    5.1.2 相关定义及定理  45-48
    5.1.3 算法描述  48-51
    5.1.4 实例分析  51-52
  5.2 一种有效的基于广义决策的属性约简算法  52-56
    5.2.1 设计思想  52
    5.2.2 相关定义及定理  52-54
    5.2.3 算法描述  54-55
    5.2.4 实例分析  55-56
  5.3 本章小结  56-58
第6章结论与展望  58-60
  6.1 全文总结  58-59
  6.2 未来工作  59-60
参考文献  60-64
攻读硕士学位期间的科研成果  64-66
致谢  66-67

基于粗糙集的属性约简和求核的算法研究

内容摘要

全文目录

相似论文