计算机应用 ›› 2009, Vol. 29 ›› Issue (08): 2230-2263.

• 人工智能 • 上一篇    下一篇

高效的信息表求核算法—兄弟判断法

农修德,徐章艳   

  1. 广西师范大学计算机科学与信息工程学院;南宁师范高等专科学校
  • 收稿日期:2009-02-12 修回日期:2009-03-23 发布日期:2008-08-01 出版日期:2009-08-01
  • 通讯作者: 农修德
  • 基金资助:
    省部级基金

Brother judgement method —an efficient algorithm for computing the core of information table

  • Received:2009-02-12 Revised:2009-03-23 Online:2008-08-01 Published:2009-08-01

摘要: 目前的求核算法大多基于决策表,基于信息表的很少。为此,先寻求理论依据,说明了U/R与U/(R-{a})的内在关系,得出了[x]R-{a}/{a}细分[x]R-{a}的结论,证明了U/(R-{a})≠U/R与结论“U/R元素有兄弟”的等价性。然后基于二叉树设计思想,用兄弟存储结构设计了一个新的信息表求核算法,仅需生成较小的二叉树就能求核,时间复杂度和空间复杂度分别为O(|C|2(上标)|U|)和O(|U|)。算法的主要贡献是将求核问题转化为等价类生成过程中兄弟的有无判断问题。通过实例验证了算法的有效性。

关键词: 粗糙集, 信息表, 等价类, 兄弟判断, Rough Set (RS), equivalence class, brother judgement

Abstract: At present, algorithms for computing the core based on decision table are in the overwhelming majority, and based on information table are in the tiny minority.For this reason,beginning with seeking theoretical basis, the inherent correlation between U/R and U/(R-{a}) is explained, and the conclusion that [x]R-{a}/{a} subdividing [x]R-{a} is drew,.and the equivalence relation between U/(R-{a})≠U/R and the conclusion that an U/R element has a brother is discovered.Then basing on design principle of binary tree,and using the Child-brother storage structure form , a novel algorithm for computing the core of information table is designed, and the core is computed if only generating a small binary tree. The time complexity and the space complexity of the new algorithm are O(|C|2(上标)|U|) and O(|U|) respectively .The important contribution it made is that the way to get the core is transformed into judging whether it has a brother or not during the course of generating equivalence classes. It’s effectiveness is verified by the example.

Key words: information table