Approaches And Algorithms For Efficiently Updating Knowledge In Preference-Oroered Decision Systems

The main task of data mining is to discover useful knowledge from data. Granular com-puting is a new paradigm of knowledge discovery, and has been widely used in the data mining research. Rough sets theory is an important theory of granular computing. Its basic viewpoint is any rough concept can be approximated by two crisp concepts, namely, upper approximation and lower approximation. Then computation of approximations is a key step to solve the prob-lems with rough set methodologies. In recent years, increasingly complex data environment (dynamic data, composite data, etc.) has caused tremendous challenges to the computational efficiency of approximations. Accelerating computation of approximations has attracted the attention of many scholars.People have various preferences in their daily lives, which is the main reason why informa-tion systems from the real-world often include some attributes with preference-ordered domains (in the decision analysis research, these attributes are called criteria). The classical rough sets theory, however, cannot be used to process information with preference-ordered domains di-rectly. For this reason, Greco et al. replaced the indiscernibility relation in classical rough sets theory by a dominance relation. Accordingly, the Dominance-based Rough Set Approach (DRSA) was proposed. This approach has been widely applied in solving multi-criteria clas-sification problems and multi-criteria decision analysis problems. Accelerating computation of approximations in DRSA is helpful to improve the efficiency of solving these problems. In this dissertation, DRSA is taken as the object of study, and how variations in the object set, values of attributes and the attribute set in a dynamic information system cause alteration in approxi-mations are investigated. Combined with the incremental strategy, some outmoded results are updated to avoid the unnecessary recalculation so that the goal can be realized for efficiently updating approximations. In order to solve the multi-criteria classification and multi-criteria de-cision analysis problems with composite data, this dissertation presents a new rough set model based on tolerance and dominance relations, and proposes an incremental approach for updat-ing approximations. To achieve the aim of efficiently computing approximations, the strategies for computing them in parallel are investigated and the corresponding parallel algorithm is de-signed. The main achievements of this dissertation are as follows: (1) For variations in the object set, an approach is proposed for maintaining approximations in DRSA when adding (deleting) an object, and the corresponding incremental algorithm is designed. Experimental evaluations show that the incremental algorithm can distinctly improve the efficiency of updating approximations in contrast with the non-incremental one.(2) For some values of attributes changing in dynamic information systems, an approach is proposed for maintaining approximations and the corresponding incremental algorithm is designed. A numerical example is given to demonstrate this approach. By experimental evaluations, it is validated that the incremental algorithm can reduce the computational time when the percentage of the values changed is less than a threshold.(3) With regard to variations in the attribute set, an approach is proposed for maintaining ap-proximations when adding (deleting) some attributes simultaneously, and the correspond-ing incremental algorithm is designed. Experimental evaluations show that the incremental algorithm can improve the efficiency of updating approximations. Its performance is close-ly related to the numbers of objects and attributes.(4) For applying rough sets methodologies in classification problems with composite data, a new rough sets model based on tolerance and dominance relations is built. An incremental approach is also proposed for updating approximations in this model when some objects are added (deleted) and the corresponding incremental algorithm is designed. Experimental evaluations indicate that the incremental algorithm can improve the computational efficien-cy.(5) In order to accelerate computation of approximations in DRSA under a parallel mode, the parallel strategies for computing them are investigated and the corresponding parallel algorithm is designed. By experimental evaluations, it is shown that the parallel algorithm can reduce computational time on the multi-core environment. On the same data set, the more cores the computer has, the more time the parallel algorithm reduces.