New Algorithm for Computing the Core Based on Skowron´s Discernibility Matrix

Designing efficient algorithm for computing the core of decision table is a very meaningful work because the core is the foundation of constructing attribute reduction of the decision table and multi-variable decision tree. To improve the efficiency of the algorithm for computing the core based on Skowron´s discernibility matrix, simplified decision table and the definition of the core based the Skowron´s simplified discernibility matrix is defined. And it is proved that the new core is the same as the core based on Skowron´s discernibility matrix. Then a new property of the simplified decision table which can improve the efficiency of computing the core is proposed. On this condition, an efficient algorithm for computing the core is designed whose time complexity is O(|C||U|) + O(|C|²|U/C|). Finally, the experiment results show the new algorithm cost least in the comparative algorithms.