Matrix-based Incremental Updating Approximations Algorithm Research In Multigranulation Rough Set

Rough set theory as a mathematical method for dealing with uncertainties and incomplete data was originally proposed by Z.Pawlak in 1982.The classical rough set theory divides the sets by a single binary relationship and uses two exact sets of upper approximation and lower approximation to describe the uncertainty of the data.However,from the perspective of granular computing,the classical rough set model is based on single-granulation and single-level,which ignores the hierarchical nature of the actual data itself.In order to overcome the shortcomings of the classical rough set theory,Qian et al.proposed multigranulation rough set model by combining the idea of granular computing.Multigranulation rough set is an extension of the classical rough set model,which describes the approximations by multiple equivalence relations on the universe.Therefore,it is possible to better understand the nature of the problem by analyzing the problem different perspectives and different levels.However,in various practical situations,there may be cases where the variation of objects,attributes or attribute value causes the dynamic variation of information system.At this time,it is very time-consuming to calculate the approximations by using the traditional non-incremental method in multigranulation environment.How to overcome such problems in multigranulation environment and effectively obtain potential information is still the focus of research in the field of rough sets.Therefore,this paper takes the multigranulation rough set and its extended model as the research object,matrix as the main computing tool,approximations update based on dynamic information system as the main research purpose,and makes the following research:(1)Neighborhood multigranulation rough set,constructed by a family of neighborhood relations,can effectively process numerical data and is therefore widely used.However,the variation of universe in neighborhood information system will lead to the variation of granularity in multigranulation environment,which will lead to the change of knowledge,such as the positive,negative and boundary regions in neighborhood multigranulation rough set.At this point,using the non-incremental method to calculate the three regions requires re-traversing the entire universe,so it takes a lot of time.In order to solve the problem of low efficiency of knowledge update,this paper presents matrix-based incremental approaches to update knowledge with the variation of universe.First,the matrix updating strategies in the neighborhood multigranulation rough set is given.Then,it proves that there is redundancy calculation in the process of updating knowledge when universe variation,and the calculation method of updating neighborhood granularity matrix is redefined.According to the matrix method defined in this paper,corresponding matrix-based incremental algorithms for updating positive,negative and boundary regions in neighborhood multigranulation rough set are proposed.The proposed method reduces the time complexity and effectively improve the execution efficiency of algorithms.Finally,the specific data set and comparison experiments verify that the proposed algorithms are effective.(2)In practical situations,there are several types of variation such as object variation,attribute variation or attribute value variation,which simultaneously vary and cause the approximation to change.However,the current research mainly focuses on the approximation set update problem under a single type variation.Considering the limitation of updating the approximations in the current single variation mode,we extend the varied problem of information system to two-dimensional,and discuss how to update lower and upper approximations in multigranulation rough set when objects and attributes vary simultaneously and objects and attribute values vary simultaneously in information system.In this paper,two matrix incremental update approximate set algorithms based on two-dimensional variation in multigranulation environment are proposed.First,the representation of matrix and approximations in MGRS are developed.Then,the matrix-based dynamic strategies are proposed to update the approximations in optimistic and pessimistic MGRS under objects and attributes vary simultaneously,objects and attribute values vary simultaneously.Based on the proposed updating strategies,two matrix-based incremental algorithms are provided for maintaining approximations when objects and attributes vary simultaneously,objects and attribute values vary simultaneously.Finally,the effectiveness of the proposed algorithm is verified by specific experimental data and comparative experiments.