Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (36): 160-163.DOI: 10.3778/j.issn.1002-8331.2008.36.045

• 数据库、信号与信息处理 • Previous Articles     Next Articles

Research on technologies for improvement and implementation of attribute reduct algorithm CARRDG

CHEN Ke-ying1,2,ZENG Wen-hua1,SHI Ming-hui3   

  1. 1.School of Software,Xiamen University,Xiamen,Fujian 361005,China
    2.Xianmen Huaxia College,Xiamen,Fujian 361005,China
    3.Department of Cognition Science,Xiamen University,Xiamen,Fujian 361005,China
  • Received:2008-08-25 Revised:2008-10-27 Online:2008-12-21 Published:2008-12-21
  • Contact: CHEN Ke-ying

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

陈可赢1,2,曾文华1,施明辉3   

  1. 1.厦门大学 软件学院,福建 厦门 361005
    2.厦门华厦学院,福建 厦门 361005
    3.厦门大学 智能科学与技术系,福建 厦门 361005
  • 通讯作者: 陈可赢

Abstract: The attribute reduct algorithm CARRDG,which can efficiently compute total attribute reducts for large scale information system,has been proposed recently.Although it has rigorous theoretical foundation,further improvement may be possible,especially in the implementation level.In addition to the existed three heuristic deep-first searching principles(Member Executive Principle MEP,Friend Persuade Principle FPP,Stranger Enter Principle SEP) based on reduct discernibility graph,a mew heuristic searching principle——Blocking Layer Block Principle(BLBP) has been proposed in this paper to improve the searching efficiency.Since the reasonable data structures have been developed,BLBP will not increase the implementing complexity of the algorithm.In contrast,the experimental results by using UCI data show that BLBP exceeds MEP and FPP in trimming efficiency for some large information systems.

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