作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (19): 179-182,187. doi: 10.3969/j.issn.1000-3428.2012.19.046

• 人工智能及识别技术 • 上一篇    下一篇

基于区分对象对集的不完备决策表求核算法

张 姣,曾艳燕,王 驹,徐章艳   

  1. (广西师范大学计算机科学与信息工程学院,广西 桂林 541004)
  • 收稿日期:2011-11-25 出版日期:2012-10-05 发布日期:2012-09-29
  • 作者简介:张 姣(1986-),女,硕士研究生,主研方向:粗糙集理论,语义网信息处理;曾艳燕,硕士研究生;王 驹、徐章艳,教授、博士
  • 基金资助:
    国家自然科学基金资助项目(60963008, 60573010, 61103169);广西自然科学基金资助项目(2011GXNSFA018163);广西研究生教育创新计划基金资助项目(2011106020812M60)

Computing Core Algorithm Based on Discernibility Object Pair Set in Incomplete Decision Table

ZHANG Jiao, ZENG Yan-yan, WANG Ju, XU Zhang-yan   

  1. (School of Computer Science and Information Engineering, Guangxi Normal University, Guilin 541004, China)
  • Received:2011-11-25 Online:2012-10-05 Published:2012-09-29

摘要: 在不完备决策表中对求核算法的研究较少,且时间复杂度都相对较高。为此,根据不完备决策表中差别矩阵及其核的定义,给出条件属性的区分对象对集的定义,并得出其与决策表核属性的关系,从理论上证明求解不完备决策表的核可以转化到求条件属性的区分对象对集上。结合不完备决策表差别矩阵核的性质,提出一种基于区分对象对集的不完备决策表求核算法。实验结果表明,该算法的时间复杂度优于同类算法的时间复杂度。

关键词: 不完备决策表, 差别矩阵, 区分对象对集, 时间复杂度, 粗糙集

Abstract: The research on computing core in incomplete decision table is not much, and some of them usually have high complexity. In view of the above questions, according to the definition of discernibility matrix and the core correspond to discernibility matrix, the definition of discernibility object pair set of condition attribute in incomplete decision table is proposed. Based on the relationship between the discernibility object pair set and the core of decision table, it proves theoretically that computing the core of decision table is equal to computing the discernibility object pair set. Considering the property of the core in incomplete decision table correspond to discernibility matrix, a new algorithm for computing core based on the discernibility object pair set in incompelete decision table is designed. And experimental results show that its time complexity is better than the time complexity of the same kind of algorithms.

Key words: incomplete decision table, discernibility matrix, discernibility object pair set, time complexity, rough set

中图分类号: