基于粗糙集和SAT算法的属性约简

The Attribute Reduce Based on Rough Sets and SAT Algorithm

粗糙集理论是80年代初由波兰数学家Z.Pawlak首先提出的一个分析数据的数学理论。该理论近几年来日益受到各领域的广泛关注,并已在机器学习、模式识别、决策分析、过程控制、数据库知识发现等广泛领域得到成功应用。论文提出了一种求最小约简的基于命题可满足性(简称SAT)算法的算法,提出一个解决SAT问题的分割和结合的算法。实验结果表明,论文所提算法在高度准确分类的基础上,所得约简中大大减少了规则的数目。

Rough set theory introduced by Z.Pawlak in the early 1980s,is a mathematical tool of reasoning about data. In recent years it has received much attention of the researchers around the world.Rough set theory has been successfully applied to many areas including machine learning,pattern recognition,decision analysis,process control, knowledge discovery from databases.An algorithm in finding minimal reducts based on Prepositional Satisfiability （abbreviated as SAT）algorithm is proposed.A branch and bound algorithm is presented to solve the proposed SAT problem.The experimental result shows that the proposed algorithm has significantly reduced the number of rules generated form the obtained reducts with high percentage of classification accuracy.