A reduct derived from feature selection

In this paper, the relationship between a selected subset of attribute set of a decision system via feature selection by an optimal algorithm and a reduct of attribute set under the meaning of Pawlak’s rough set is discussed. This selected subset is considered as a solution of the optimal algorithm. It is verified that a locally optimal solution is surely not a reduct while a reduct must be a globally optimal solution. Based on these assertions, a new optimal algorithm, called blindly deleting algorithm with an inverse ordering (BDAIO), is proposed to find a real reduct of a decision information system by remedying the selected attribute subset. Several standard data sets from UCI repository are implemented showing validity of the proposal.

► The paper reveals a subset gained by feature selection is not always a real reduct.
► The relationship between optimal solutions and reducts is studied.
► A real reduct must be a globally optimal solution, but the inverse is not.
► An optimal algorithm is proposed to surely find a real reduct with theorems.
► With good classification accuracy, a real reduct plays a key role in rule extraction.