一种面向增删操作的粗糙集属性约简更新算法

An Attribute Reduction Update Algorithm for Object's Adding-Deleting Based on Rough Set Theory

属性约简是粗糙集理论的核心内容之一,在信息系统的对象信息不断出现增删等更新操作的环境下,如何进行快速有效的属性约简则是一个亟需解决的迫切问题.提出一种面向增删操作的属性约简更新算法,面向更新前后的决策表,首先分析了对象信息动态增加与删除情况下信息熵的变化机制以及约简属性对新增或删除对象的区分情况,然后提出基于区分情况的新条件熵值的计算方法,最后给出基于散列表的属性约简更新算法.实验结果证明,本文方法可以快速求解出增删更新后的属性约简结果,其性能较传统方法有较大优势.

Attribute reduction is one of the important topics in the research on rough set theory. When an object was added to or deleted from the original decision table,how to calculate attribute reduction fast and effectively is a pressing problem. This paper proposed an attribute reduction update algorithm. Firstly,the changing mechanism of conditional entropy was analyzed when object is added to or removed from the table,and then we divided the added or removed objects into different cases. Furthermore,we presented the update algorithm based on these cases and implemented it based on hash table. Experiment results show that our algorithm can calculate the attribute reduction fast and outperforms the existing methods.