基于改进差别矩阵的属性约简增量式更新算法

Incremental Updating Algorithm for Attribute Reduction Based on Improved Discernibility Matrix

针对目前基于差别矩阵的属性约简算法需要耗费大量的时间和空间,粗糙集中求属性核和属性约简更新效率低以及有关属性约简的增量式更新算法目前还比较少等问题,提出了一种基于改进差别矩阵的属性约简增量式更新算法。该算法在更新差别矩阵时,仅须插入某一行及某一列,或删除某一行并修改相应的列,因而可有效地提高核和属性约简的更新效率。然后在分析新增对象x与原决策系统对象的关系的基础上,给出了属性约简增量更新算法。理论与实验分析表明,提出的算法提高了属性约简的更新效率,明显降低了时间和空间复杂度。

In order to solve the problem that the attribute reduction algorithm based on discernibility matrix spends a lot of time and space and the efficiency of the attribute core and the attribute reduction update of the rough set are slow, what is more, it lacks the incremental updating algorithm for attribute reduction,this paper proposed an incremental up- dating algorithm for attribute reduction based on the discernibility matrix. When the algorithm updates the discernibility matrix, it only needs to insert a row and a column, or delete a row and modify the corresponding column, which can effectively improve the updating efficiency of core and attribute reduction~ We analyzed the relationship of the new object x with the original decision system object, giving out the updating algorithm of the attribute reduction increment. Theo- retical and experimental analysis shows that the proposed algorithm can improve the updating efficiency of attribute reduction, reducing the time and space complexity significantly.