Research On Incremental Reduction Algorithm Based On Rough Sets

Rough sets theory, proposed by Pawlak in 1982, is a mathematic tool to deal with uncertain, incomplete and fuzzy data. It has been used to find the potential information which we want or derive decision of problem. Through 30 years development, Rough has been successfully implemented in Machine Learning, Knowledge Discovery, Decision Analysis, Pattern Recognition, etc.Knowledge reduction is the most important content. Reduction could reduce the dimension and size of knowledge warehouse which is special advantages in the background of knowledge explosion. Most of reduction algorithm currently used arithmetic is based upon static data which is contrary to the dynamic increasing characteristic of the realistic data. So it is of great urgency and necessary to research on incremental reduction algorithm.This article carries out further research on incremental reduction algorithm under the system of rough sets, among which the following works have been implemented:(1) This article introduce existing incremental algorithms based on discernibility matrix, and divided into three typical categories. Advantage and disadvantage of each types was analyzed, hopes to enhance its efficiency and rationality.(2) In the view of information theory, this article proposed a new a method based on conditional entropy. We found the change mechanism of conditional entropy when a new object is added to the original decision table. Based on this mechanism, divided the added objects into three cases. Furthermore, only the reduction has changed, we will need to calculate the new reduction.This article reaches some very valuable conclusions through further research on incremental reduction algorithm. These results will enrich rough sets theory, and provide some reference to the problem of incremental reduction based on rough sets.