粗糙集理论是由波兰科学家Z.Pawlak在1982年提出的一种处理模糊、不精确知识和不完备信息的数学工具。该理论的特点是不需要任何先验的知识,或者任何附加的信息,就能有效地分析和处理这类数据,从中发现隐含的知识,揭示潜在的规律性,即决策规则。近年来,粗糙集理论在人工智能和认知科学领域具有重要的地位,特别是在知识发现、机器学习、决策分析、过程控制、模式识别、数据挖掘和专家系统等领域得到了广泛应用。在粗糙集理论中,属性约简和求核是重要的研究内容之一。属性约简,就是在保持知识库(决策表)中分类能力不变的情况下,删除知识库中无关或不重要的属性,使得知识库中的知识表示得到简化,而又不丢失其基本信息,如果能将冗余属性删除,则可以减小知识库规模,节约成本,并能提高知识库中潜在知识的清晰度。由于对知识库进行属性约简,很多算法都是以核为基础,然后在核的基础上逐步得到属性约简,因此,研究快速的属性约简和求核算法具有重要的理论意义和应用价值。目前,现有的大多数算法均是以静态决策表为基础而设计的,而针对动态决策表的算法的研究较少,但实际决策表中的对象通常是动态变化的,故原来的核和属性约简可能已经不再是新决策表的核和属性约简,为此需要对新决策表进行重新计算。在以静态决策表为基础的属性约简和求核算法中,对于更新后而变化不大的新决策表而言,将会使得原来算法中大量有用的信息没有得到有效的利用,特别是对一些实时性要求较高的场合,这种以静态决策表为基础的属性约简和求核算法往往不大适用,因此,研究高效的动态更新算法具有广泛的实际意义。本文首先简单介绍了粗糙集理论的研究动态和基础理论知识,然后系统地概述了现有的基于决策表的常见属性约简和求核的模型及相关算法,其中包括基于正区域的算法、基于差别矩阵的算法、基于信息熵的算法。本文在学习和借鉴已有研究成果的基础上,主要的创新点如下:1)利用位图和粒计算技术提出了一种改进的基于正区域的属性约简(Pawlak Reduction)新算法。在该属性约简算法中,设计了一种能减少粒计算数目的启发式信息,有效地减少了不影响属性约简结果的大量计算,并通过实例仿真和实验结果表明了新算法的有效性和正确性。2)给出一个简化二进制差别矩阵的属性约简定义,从理论上分析证明了该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出简化的二进制差别矩阵,采用了一个快速求简化决策表的算法。在此基础上,设计了基于信息熵的简化二进制差别矩阵属性约简算法,并分析了算法的时间复杂度和空间复杂度分别为max{O (| C || U |), O (| C |2 | U′|2 )}和max{O (| C || U′| 2), O (| U|)},并通过实例仿真显示新算法的效率优于典型的算法。3)分析了现有的常见求核增量式算法的不足,为了有效地提高动态决策表的核增量式更新效率,本文首先引入简化决策表,然后结合简化的二进制差别矩阵设计了一种新的基于决策表的核增量式高效更新算法。该算法在更新简化的二进制差别矩阵时,只需在原决策表基础上对记录进行相应的更新,不需要重复计算原决策表的二进制差别矩阵。采用边更新简化二进制差别矩阵边计算核,显著地提高了动态更新核的效率和灵活性。算法的时间复杂度和空间复杂度分别为O( | C || U′|)和O (| C || U′p os|| U′|),并通过实例仿真和实验性能对比表明了新算法的有效性。4)由于对决策表进行属性约简,很多算法都是以核为基础,然后逐步得到属性约简。本文在3)增量式更新核的基础上,利用位图技术,并结合简化的二进制差别矩阵设计了一种新的基于决策表的属性约简增量式快速更新算法,算法的时间复杂度和空间复杂度分别为max{O ( | Red || U′p os || U′|), O( | Red ?Core|2 | U′p os|| U′|)}和O (| C || U′p os|| U′|),并用实例仿真说明了新算法的有效性。