利用序关系求差别矩阵的核的高效算法

目前设计基于差别矩阵的求核算法的主要方法是差别矩阵方法.在该种方法中,是通过搜索差别矩阵的所有差别元素得到核.由于是在所有的差别元素上搜索,故该方法比较耗时.本文在简化决策表和简化差别矩阵的基础上,将具有核属性的差别元素集归纳在某一相对较小的集合上,故新算法只需搜索和检查简化差别矩阵的少量差别元素就可以得到核算属性集.设计了一个高效求核算法,其时间复杂度为max{O(|C|2|U/C|),O(|C||U|)},其空间复杂度为O(|U|).由于新算法只判断简化差别矩阵的少量差别元素就可以找到核算属性集,故新算法的效率得到了有效地改善.

An Efficient Algorithm for Computing the Core of Skowron Discernibility Matrix with Order Relation

At present,the main method of designing algorithm for computing the core of discernibility matrix 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.For improving the efficient of computing the core based on discernibility matrix,Will have a set of core attributes of different elements mapped to a smaller search space,the new algorithm only determine the difference between a small number of simplified discernibility matrix elements can be found the set of the core.Then,an efficient computing core is designed.The time complexity and space complexity are max{O(|C|2|U/C|),O(|C||U|)} and O(|U|),respectively.Since the core can be found by searching a small quantity of discerniblity elements of discernibility matrix in the new algorithm,the efficiency of the new algorithm is improved.Finally,an example is used to illustrate the effectively of the proposed algorithm.The experimental results show our algorithm is not only efficient,but also is suitable for dealing with large decision table.