Discernibility matrix based incremental attribute reduction for dynamic data

摘要

Dynamic data, in which the values of objects vary over time, are ubiquitous in real applications. Although researchers have developed a few incremental attribute reduction algorithms to process dynamic data, the reducts obtained by these algorithms are usually not optimal. To overcome this deficiency, in this paper, we propose a discernibility matrix based incremental attribute reduction algorithm, through which all reducts, including the optimal reduct, of dynamic data can be incrementally acquired. Moreover, to enhance the efficiency of the discernibility matrix based incremental attribute reduction algorithm, another incremental attribute reduction algorithm is developed based on the discernibility matrix of a compact decision table. Theoretical analyses and experimental results indicate that the latter algorithm requires much less time to find reducts than the former, and that the same reducts can be output by both.