论文部分内容阅读
在粗糙集的众多应用中，属性约简是最核心的内容之一。所谓属性约简是在保持信息系统分类能力不变的前提下，删除冗余的属性。属性约简大大简化了数据库结构的复杂度，提高了人们对隐含在数据库庞大数据量下各种信息的认识程度。在粗糙集理论中，属性约简算法的研究具有很重要的理论和现实意义。 但是找出所有的约简或最小约简是NP-hard问题，这意味着对于较大规模的约简问题，不太可能在多项式时间内找到最优解，一般只能通过启发式算法快速求出次最优解。 现有的属性约简启发式算法，大多是注重对时间复杂度的改进，而对算法解结果的改进不多。随着现有硬件条件的不断提高，算法在运行时间上的差别越来越小，而启发式算法解的低精度在一定程度上限制了粗糙集理论的广泛应用。因此在时间复杂度差别不大的情况下，寻找较高精度的属性约简算法，尤其是在已有的各种算法基础上提高解精度具有更重要的实用价值。 本文致力于提高属性约简算法的解精度，通过深入分析传统贪婪算法搜索空间过于狭小的根源，提出三种基于粗糙集的高精度属性约简算法：探测性贪婪算法、回退型贪婪算法和随机初始化算法： 1、针对传统贪婪算法一旦做出选择就不能反悔的特性，提出一种允许有限步反悔的回退型贪婪算法，并通过实验比较对该算法进行分析。 2、将前景探测策略引入属性约简中，提出一种属性约简的探测性贪婪算法，并通过理论分析和实验比较证明了该算法的有效性。 3、提出一种针对属性约简的随机初始化搜索算法(RISA)。该算法在已得贪婪解的基础上多次迭代搜索，并通过初始点来动态调整搜索范围和跳出局部最优。实验结果表明，该算法所得解的精度较现有算法有显著提高。