Abstract: In rough set theory, attribute reduction is a NP-hard problem. To solve this problem, a bisection method for attribute reduction is developed and the main opinion is to partition the universe into smaller ones to reduce the complexity. In realization, there are five major steps：find partition core set of information system, bisection the universe by using each attributes in partition core set, compute the partition discernibility set of un-distinguished objects, compute the minimal cover of the set family that is formed by the partition discernibility sets, and merge partition core set and the minimal cover to get the final result. Experiments and analysis show that, compared with the traditional un-bisection reduction algorithm, the developed bisection algorithm can significantly reduce computational time while maintaining their results the same as before.

Key words: information system, attribute reduction, normal form conversion, dichotomy algorithm

摘要： 属性约简是粗糙集理论的重要研究内容之一，并已经证明是一个NP难问题。为了提高算法的效率，提出了一个采用二分策略的属性约简方法，即计算信息系统的划分核心，利用划分核心将原始对象集逐次二分，对每个二分后的对象子集分别计算划分辨识集，计算划分辨识集的极小覆盖，通过合并极小覆盖与划分核心获得信息系统的属性约简。分析和实验结果表明随着划分核心数量的增长，使用二分法大幅度提高了算法的效率。

关键词: 信息系统, 属性约简, 范式转换, 二分法