属性约简算法CARRDG的改进及其实现技术研究

摘要

属性约简算法CARRDG是近来提出的能计算大型信息系统中所有属性约简的高效算法.针对属性约简算法CARRDG在实现技术层面上的可改进之处,在原有的三种约简分辨图深度优先搜索原则(成员独占原则、友人劝阻原则、陌生人吸纳原则)的基础上,增加新的深度优先搜索原则--阻挡层阻挡原则.由于采用了恰当的数据结构和实现技术,使得增加阻挡层阻挡原则不会增加原算法的程序实现的复杂性,也几乎不会增加程序的运行时阃.相反,UCI数据实验结果表明,阻挡层阻挡原则对于某些大型信息系统的约简分辨图的剪枝效率超过了成员独占原则与友人劝阻原则.