一种基于粗集理论的增量式属性约简算法

An Algorithm of Incremental Attribute Reduction Based on Rough Sets Theory

要在信息系统中,有新的研究对象加入系统时,若其条件属性和决策属性不改变,为求信息系统的条件属性约简集,传统办法是对加入新对象后的决策表中全部数据从头计算,但此办法复杂度较高。本文提出了一种增量式属性约简算法,采取分而治之法,把处理一个复杂的大问题,转化成处理多个简单的小问题。从而极大地降低了属性约简算法的时空复杂度。当条件属性和决策属性不变而不断增加对象时,通过该算法可动态地实现属性约简,且求得的属性约简价值较高,通过具体例子证明了所提算法是正确有效的。

In order to obtain the reduced attributes of an information system when some new objects are added to the information system without the change of condition attribute and decision attribute,all the data in the new decision table will be recalculated in the traditional method.Clearly,this method is more complex.An incremental attribute reduction algorithm is proposed,by which a complex problem is divided into several simple problems to be solved.So the temporal and spatial complexity of the algorithm is reduced greatly.The attribute reduction of the new information system can be got by the algorithm in the dynamic mode when the objects are added to the information system without the change of condition attribute and the decision attribute.The algorithm is demonstrated to be correct and effective with the specific examples and the new attribute reduction is valuable in applications.