Research On Algorithm Of Covering Rough Set Based On Matrix

Rough set theory,proposed by Z,Pawlak,is a kind of mathematical tool to deal with incomplete and imprecise information effectively.Classical rough set is based on equivalence relation and partition,attributes in the datasets can induce a partition of the universe,where every object can take a discrete value for every attribute.However,in the reality situation,there are multiple types of data in information systems,for example,set-valued ones,missing ones and real-valued ones,classical rough set can't deal with these data directly and correctly,and this limits the application of classical rough set,to overcome this limitation,generalization of classical rough set has been attracting more and more attention.In these generalized studies,Zakowski first proposed covering-based rough set model by relaxing partition of a universe to covering.Since the model was proposed,researches mainly focus on the study set approximations and attribute reduction,a lot of definitions of set approximations and algorithms of attribute reduction are proposed,while the time complexity of these methods is still high,aiming at this problem,this paper has done the following research:(1)The definitions of improved matrix-based lower approximation and positive region of a covering decision information system are proposed.Firstly,we prove that there exist unnecessary computation in the existing matrix-based methods for calculating lower approximation and positive region of a covering decision information system,which can lead to the high time complexity.Secondly,we define improved matrix-based lower approximation and positive region of a covering decision information system,which can reduce the running time of the original matrix-based methods for calculating lower approximation and positive region of a covering decision information system.Finally,example and experimental results demonstrates that the two methods are effective.(2)In order to overcome the problems of high time complexity for the existing algorithms for deriving all minimal elements in the discernibility matrix.We first define matrix-based the relative discernible relation of covering decision information system,then based on this definition,a matrix-based algorithm for deriving all minimal elements in the discernibility matrix is developed,which can greatly reduce the running time of calculating all reductions of covering decision information system.Finally,example and experimental results demonstrates that this algorithm in this paper is effective.(3)In practical situations,the change of attribute values can lead to a certain covering change in covering information system,this time,it is time-consuming to compute lower and upper approximations of sets with the non-incremental approaches,thus,we propose matrix-based incremental approaches to calculate lower and upper approximations of sets in dynamic covering information systems caused by variations of attribute values.Firstly,we propose incremental approaches to compute two kinds of characteristic matrix of dynamic covering.Then,we propose incremental algorithms to compute lower and upper approximations of sets based on the given two kinds of characteristic matrix,respectively,and use an example to show the calculation process of set approximations by the proposed algorithms in this paper.Finally,we use experiment to verify the effectiveness of the proposed incremental algorithms in this paper.