随着新型信息技术的迅猛发展,各行各业中数据快速的增长和变化形成了动态复杂数据。如何高效的从动态复杂数据中获取关键有用的信息已成为各领域重要研究课题之一。基于粗糙集理论的特征选择方法已成功应用于机器学习、数据挖掘、模式识别和知识发现等领域的数据预处理过程。在粗糙集领域中,特征选择被称为属性约简,其主要目的是在保持原始数据分类能力或近似刻画不变的前提下,从原始数据中删去冗余或者不必要的属性。基于粗糙集理论分析推理数据方法最大的优势在于它具有完善理论基础以及它无需任何先验信息指导下处理数据,因此在动态数据环境下,研究基于粗糙集理论的属性约简方法具有重要的现实意义。目前已经提出了很多面向静态数据的最优约简方法和面向动态数据的属性约简方法。然而,无论是最优约简还是一般属性约简问题,现有的方法存在如下问题:一是最优约简方法在大规模数据集上失效;二是动态数据并没有考虑标记值缺失的情况;三是将属性值动态变化简单看成是样本的变化。为了改进这些不足,本文以超图理论、增量更新近似集技术以及局部搜索算法为研究工具,以决策系统为研究对象,在动态数据环境下高效更新属性约简问题和粗糙集理论中具有挑战性的最优约简问题展开了研究与探索,取得的主要研究成果和创新点如下:（1）针对样本动态增多的部分标记数据,构建了部分标记数据的两类诱导超图模型,在诱导超图的基础上,设计了一个具有低复杂度的快速求极小顶点覆盖的方法,相应的提出了基于超图模型的静态部分标记数据属性约简方法。进一步,讨论了样本动态增多后,从部分标记数据提出的诱导超图的更新机制以及极小顶点覆盖的更新机制,并提出了样本动态增多后基于超图极小顶点覆盖的增量式属性约简方法。基于超图模型的方法为处理部分标记数据提供新型高效的解决办法,该方法能够在较短时间内获取较优的约简同时保持了较高的分类精度。（2）针对属性值变化的动态缺失数据中如何高效更新属性约简的问题,提出了基于不一致度为度量的属性重要性定义和属性约简定义,并利用不一致度作为启发启发信息设计了缺失数据中属性约简方法。进一步,讨论了属性值变化后,缺失数据容差类的更新策略:当少量对象的属性值变化时使用对象相关策略;当少量属性的大量对象的属性值变化时使用属性相关策略;当少量对象的少量属性值变化时使用同时相关策略。基于三种容差类更新策略分析了不一致度的更新机制,并提出了属性值变化的动态缺失数据中基于不一致度的增量式属性约简算法的框架。该框架改进了目前处理属性值动态变化数据的弊端,对于不同规模属性值的动态变化选择合适的更新策略能够提高算法的效率。（3）针对粗糙集理论中最优约简问题,设计了两种结合局部搜索算法的属性约简算法:基于随机寻找交换属性对策略的局部搜索算法和带反向增量验证机制的局部搜索算法。后者在前者的基础之上加入了反向增量验证机制和调整迭代过程规则来提高算法运行效率和寻优能力,其中反向增量验证机制通过逆向的增量更新正区域达到快速寻找合适的交换属性对的目的,而调整迭代过程规则是防止过多的冗余计算量和避免算法过早的陷入局部最优。基于局部搜索的属性约简算法能够在较短时间内获取较优约简甚至最优约简,它是目前已知的平均时间复杂度最低的完备属性约简算法。（4）为了进一步探索求解最优约简的方法,提出了一种最优属性约简问题的泛化问题:K-size部分属性约简问题,并设计了两种方法:枚举法和基于局部搜索的方法。基于局部搜索的方法在枚举法的基础上提出了三个改进:快速构造初始解、解的生成规则以及动态对象加权策略,这三个改进使得算法只需要少量迭代过程就能够获得较优解甚至最优解。最优属性约简问题可以称为一种特殊的K-size部分属性约简问题,因而在某种意义上为求解最优属性约简提高了新的思路和方法。本文利用增量约简思想,设计了两种类型的动态决策系统中增量式属性约简方法,给出了部分标记决策系统中的超图模型以及样本增多时诱导超图的更新机制,同时构建了三种面向属性值动态改变的不完备决策系统中容差类的更新策略。另外,结合局部搜索算法和增量更新近似集技术探索了粗糙集理论中具有挑战性的最优约简问题,并提出了两种基于局部搜索的解决方法。通过在基准数据集上大量实验结果验证了本文提出的算法的有效性和可行性。本课题的研究工作在一定程度上丰富了和完善了基于粗糙集理论动态知识发现的方法,同时也为最优属性约简问题提供了新的研究思路和解决方案。