一种基于决策表的核增量式高效更新算法  

Efficient Incremental Updating Algorithm for Computing Core of Decision Table

作　　者：钱文彬[1] 徐章艳[1,2] 杨炳儒[2] 黄丽宇[1] 

机构地区：[1]广西师范大学计算机科学与信息工程学院,广西桂林541004 [2]北京科技大学信息工程学院,北京100083

出　　处：《小型微型计算机系统》2010年第4期739-743,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60463003;60963008)资助;广西研究生教育创新计划项目(200910620813M61)资助;广西省教育厅科研基金项目(200626)资助;广西师大博士启动基金资助课题

摘　　要：引入简化决策表,结合简化二进制差别矩阵设计思想,提出一种基于决策表的核增量式高效更新算法.该算法在更新简化的二进制差别矩阵时,只需在原决策表基础上对记录进行相应的更新,不需要重复计算原决策表的二进制差别矩阵.采用边更新简化二进制差别矩阵边计算核,显著地提高了算法的效率和灵活性.新算法的时间复杂度和空间复杂度分别为O(|C||U′|)和O(|C||U′pos||U′|).最后用一个实例说明了新算法的高效性.Firstly,the concept of simplified decision table is introduced.Then an efficient incremental updating algorithm for computing core of decision table is designed with simplified binary discernibility matrix.The new algorithm only inserts some new binary records,or deletes some binary records on the basis of the previous binary discernibility matrix when updating the simplified binary discernibility matrix.It doesn′t need to compute the binary discernibility matrix of the old decision table when the old decision table is changed.Core of the decision table is computing when the simplified binary discernibility matrix of the decision table is been dynamically updating.For this reason,the efficiency and flexibleness of the new algorithm is remarkably improved.The time complexity and space complexity of the new algorithm are O（｜C｜｜U′｜） and O（｜C｜｜U′pos｜｜U′｜） respectively.At last,an example is used to illustrate the efficiency of the new algorithm.

关 键 词：粗糙集 核 增量式更新 简化的二进制差别矩阵 算法复杂度 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]