Researches On Quick Attribute Reduction Algorithms In Incomplete Decision Systems

The rapid development of computer technology and the Internet has produced the massive and complex information data.This kind of data with large scale and high dimensions is dynamic,and has complex data types,such as symbolic data,set-valued data,interval-valued data,and incomplete data.Acquiring knowledge quickly and efficiently from such large-scale and complex data has become one of the current research directions.As one of the important methods of knowledge acquisition,rough set theory can effectively deal with uncertain information.With the development of rough set theory,the attribute reduction is being applied to the different data backgrounds and reduction objectives,a large number of attribute reduction algorithms have been proposed.However,existing attribute reduction algorithms are inefficiency in handling such data.Therefore,in incomplete decision systems,this paper studies the discernibility matrix-based attribute reduction for generalized decision preservation,and incremental attribute reduction for conditional entropy preservation.The generalized decision preservation reduction algorithm for multi-specific decision classes in incomplete decision systems and the incremental attribute reduction algorithm based on conditional entropy in incomplete decision systems are proposed.The main research contributions are as follows:(1)In view of the fact that decision-makers may only interested in a few specific decision classes in some practical applications,the definitions of generalized decision preservation reduction for single-specific decision class and multi-specific decision classes in incomplete decision systems are given respectively,and the corresponding discernibility matrix is constructed.Based on the discernibility matrix,a generalized decision reduction algorithm for multi-specific decision classes is designed.Compared with the classical attribute reduction algorithm for all decision classes,the proposed algorithm can get shorter reducts when the selected decision classes are less,and the time and space consumption are reduced to different degrees in the computing process.(2)Aiming at the characteristics of dynamic changes in data,by analyzing the change of the tolerance classes and studying the influence of dynamically increasing objects on the original conditional entropy,the single and group incremental update mechanism of conditional entropy are constructed.The effectiveness and feasibility of these two mechanisms are proved.Based on the incremental update mechanism of the conditional entropy,the measure of attribute significance is proposed,and the process of attribute reduction is simplified.Based on this,incremental attribute reduction algorithms for conditional entropy in dynamic incomplete decision systems are proposed.In experiments,compared with the non-incremental traditional attribute reduction algorithm,the proposed algorithm can get the correct reduction result,and significantly improve the reduction efficiency.