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

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

目前设计基于正区域的求核算法的主要方法是差别矩阵方法。该方法通过搜索差别矩阵的所有差别元素来得到核,故比较耗时。为此,在简化决策表和简化差别矩阵的基础上,若将其对象按条件属性值看成一个数,则对象是有序的。利用这个序,可将具有核属性的差别元素集映射到一个较小的搜索空间上,故只需判断简化差别矩阵的少量差别元素就可以找到核属性集。在此基础上,利用基数排序的思想,设计了一个高效求核算法,其时间复杂度为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.