Discernibility matrix simplification for constructing attribute reducts

This paper proposes a reduct construction method based on discernibility matrix simplification. The method works in a similar way to the classical Gaussian elimination method for solving a system of linear equations. Elementary matrix simplification operations-are introduced. Each operation transforms a matrix into a simpler form. By applying these operations a finite number of times, one can transform a discernibility matrix into one of its minimum (i.e., the simplest) forms. Elements of a minimum discernibility matrix are either the empty set or singleton subsets, in which the union derives a reduct. With respect to an ordering of attributes, which is either computed based on a certain measure of attributes or directly given by a user, two heuristic reduct construction algorithms are presented. One algorithm attempts to exclude unimportant attributes from a reduct, and the other attempts to include important attributes in a reduct. (C) 2008 Elsevier Inc. All rights reserved.