Three-way Decision Model In An Incomplete Information System

It's one of the hot topics for data analysis to find out useful knowledge from data and make reasonable decisions.Three-way decision is a decision model consistent with human cognition.It is widely used in rough set theory to study classification and acquisition rules.Three-way decision model replaces the two-way decision model and allows the third decision: non-commitment decision,which makes the decision more flexible and reliable.In many situations,information may be incomplete and we may not know their actual values,which are denoted as incomplete information.An information system with incomplete information is called an incomplete information system.Although incomplete information is a well-studied topic in rough set theory,there still does not exist a general agreement on the semantics of various types of incomplete information.This leads us to face a common challenge in formulating decision rules.This thesis addresses semantics issues related to incomplete information and generalizes computational and conceptual formulations into three-way decision with incomplete information,and presents different incremental algorithms for incrementally updating approximability when an incomplete information system changes.The main results as follows:(1)Three-way decision with incomplete information from computational and conceptual formu- lations based on crisp set.The computational formulation focus on discussing the definitions of similarity relations between objects and similarity classes of objects.Two methods for studying similarity are proposed: One is to definite similarity relations and corresponding similarity classes in an incomplete information system based on the semantics of incom- plete information.The other is to discuss similarity of objects in a set-valued information system,which is transferred by an incomplete information system based on the possible- world semantics.Studies of set-valued information systems fall into two broad classes.One class of the studies directly defines similarity between sets as similarity relations between objects and gets the corresponding similarity classes of objects.The other class defines similarity relations from a family of equivalence relations in all completions of a set-valued information system and gets the corresponding similarity classes of objects.The concep- tual formulation focus on discussing the satisfiability of logic formulas.The description of objects based on the semantics of incomplete information is studied.Based on it,one can get similarity class of each object in which objects satisfy the logic formula of the object's description.In an incomplete information system,similarity classes are definable sets.By using the descriptions of definable sets,the definition of three-way decisions in an incom- plete information system is studied.(2)Three-way decision with incomplete information from computational and conceptual formu- lations based on fuzzy set.First of all,based on the possible-world semantics,an incomplete information system is transferred to a set-valued information system.For the computational formulation,a new measure of similarity degree of objects is proposed as a generalization of equivalence relations.Based on it,two approaches to three-way decision using ?-similarity classes and approximability of objects are discussed.For the conceptual formulation,a measure of satisfiability degree of formulas is proposed as a quantitative generalization of satisfiability with complete information.Based on it,two approaches for obtaining three- way decision rules by using ?-meaning sets of formulas and confidence of formulas are studied.(3)In an incomplete information system with “Do-not-care values”,a three-way decision model based on the graded tolerance relation is proposed.First of all,a definition of graded toler- ance relation in an incomplete information system with “Do-not-care values” is proposed. Besides,fuzzy logical operators can be used to calculate the positive and negative approx- imability of objects based on the graded tolerance relation.A relation matrix is proposed to efficiently computing the approximability of objects.By applying a threshold on the ap- proximability of objects,the positive and negative description regions can be constructed. Furthermore,three-way decision rules are obtained.In order to effectively obtain the deci- sion rules when an incomplete information system changes,incrementally updating meth- ods to update approximability based on the graded tolerance relation are studied.Therefore, different incremental algorithms for incrementally updating approximability by incremen- tally updating the relation matrix when adding or removing attributes,adding or removing objects,and changing an attribute value of an object are respectively discussed.Finally,the time consuming between incremental algorithms and the non-incremental algorithm on the different data sets from UCI are compared.