基于序关系的快速计算正区域核的算法  

Quick Algorithm for Computing Core of the Positive Region Based on Order Relation

作　　者：徐章艳[1,2] 舒文豪[1] 钱文彬[1] 杨炳儒[2] 

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

出　　处：《计算机科学》2010年第7期208-211,共4页Computer Science

基　　金：国家自然科学基金重点项目(69835001);广西教育厅基金项目(200807MS015);西师大博士启动基金项目资助

摘　　要：目前设计基于正区域的求核算法的主要方法是差别矩阵方法。该方法通过搜索差别矩阵的所有差别元素来得到核,故比较耗时。为此,在简化决策表和简化差别矩阵的基础上,若将其对象按条件属性值看成一个数,则对象是有序的。利用这个序,可将具有核属性的差别元素集映射到一个较小的搜索空间上,故只需判断简化差别矩阵的少量差别元素就可以找到核属性集。在此基础上,利用基数排序的思想,设计了一个高效求核算法,其时间复杂度为O(|C|2|U/C|)+O(|C||U|),空间复杂度为O(|U|)。由于新算法只需判断简化差别矩阵的少量差别元素就可以找到核算属性集,故算法的效率得到了改善。At present, the main method of designing algorithm for computing the core based on the positive region is discernibility matrix. In this method, the core is found by discovering all discernibility elements of discenibility matrix. So this method is very time consuming. On the foundation of the simplified decision table and simplified discernibility matrix, if the objects with condition attribute value of simplified decision table are looked as numbers, they are order. Using the order, the discernibility elements including the core may be turned into a mall quantity of research space. So the core based on the positive region can be found only by searching a small quantity of discernibility elements of the simplified discernibility matrix. On this condition, an efficient computing core was designed by integrating the idea of radix sorting. The time complexity and space complexity are O（ ｜ C ｜ ｜ U ｜ ） ＋ O（ ｜ C ｜^ 2 ｜ U/C｜ ） and O（ ｜ C ｜ ｜ U ｜ ） respectively. Since the core can be found by searching a small quantity of discerniblity elements of the simplified discernibility matrix in the new algorithm, the efficiency of the new algorithm is improved.

关 键 词：粗糙集 简化决策表 正区域 核 算法复杂度 

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