Dominance-based rough set approach

The dominance-based rough set approach (DRSA) is an extension of rough set theory for multi-criteria decision analysis (MCDA), introduced by Greco, Matarazzo and Słowiński. The main change compared to the classical rough sets is the substitution for the indiscernibility relation by a dominance relation, which permits one to deal with inconsistencies typical to consideration of criteria and preference-ordered decision classes. The dominance-based rough set approach (DRSA) is an extension of rough set theory for multi-criteria decision analysis (MCDA), introduced by Greco, Matarazzo and Słowiński. The main change compared to the classical rough sets is the substitution for the indiscernibility relation by a dominance relation, which permits one to deal with inconsistencies typical to consideration of criteria and preference-ordered decision classes. Multicriteria classification (sorting) is one of the problems considered within MCDA and can be stated as follows: given a set of objects evaluated by a set of criteria (attributes with preference-order domains), assign these objects to some pre-defined and preference-ordered decision classes, such that each object is assigned to exactly one class. Due to the preference ordering, improvement of evaluations of an object on the criteria should not worsen its class assignment. The sorting problem is very similar to the problem of classification, however, in the latter, the objects are evaluated by regular attributes and the decision classes are not necessarily preference ordered. The problem of multicriteria classification is also referred to as ordinal classification problem with monotonicity constraints and often appears in real-life application when ordinal and monotone properties follow from the domain knowledge about the problem. As an illustrative example, consider the problem of evaluation in a high school. The director of the school wants to assign students (objects) to three classes: bad, medium and good (notice that class good is preferred to medium and medium is preferred to bad). Each student is described by three criteria: level in Physics, Mathematics and Literature, each taking one of three possible values bad, medium and good. Criteria are preference-ordered and improving the level from one of the subjects should not result in worse global evaluation (class). As a more serious example, consider classification of bank clients, from the viewpoint of bankruptcy risk, into classes safe and risky. This may involve such characteristics as 'return on equity (ROE)', 'return on investment (ROI)' and 'return on sales (ROS)'. The domains of these attributes are not simply ordered but involve a preference order since, from the viewpoint of bank managers, greater values of ROE, ROI or ROS are better for clients being analysed for bankruptcy risk . Thus, these attributes are criteria. Neglecting this information in knowledge discovery may lead to wrong conclusions. In DRSA, data are often presented using a particular form of decision table. Formally, a DRSA decision table is a 4-tuple S = ⟨ U , Q , V , f ⟩ {displaystyle S=langle U,Q,V,f angle } , where U {displaystyle U,!} is a finite set of objects, Q {displaystyle Q,!} is a finite set of criteria, V = ⋃ q ∈ Q V q {displaystyle V=igcup {}_{qin Q}V_{q}} where V q {displaystyle V_{q},!} is the domain of the criterion q {displaystyle q,!} and f : U × Q → V {displaystyle fcolon U imes Q o V} is an information function such that f ( x , q ) ∈ V q {displaystyle f(x,q)in V_{q}} for every ( x , q ) ∈ U × Q {displaystyle (x,q)in U imes Q} . The set Q {displaystyle Q,!} is divided into condition criteria (set C ≠ ∅ {displaystyle C eq emptyset } ) and the decision criterion (class) d {displaystyle d,!} . Notice, that f ( x , q ) {displaystyle f(x,q),!} is an evaluation of object x {displaystyle x,!} on criterion q ∈ C {displaystyle qin C} , while f ( x , d ) {displaystyle f(x,d),!} is the class assignment (decision value) of the object. An example of decision table is shown in Table 1 below. It is assumed that the domain of a criterion q ∈ Q {displaystyle qin Q} is completely preordered by an outranking relation ⪰ q {displaystyle succeq _{q}} ; x ⪰ q y {displaystyle xsucceq _{q}y} means that x {displaystyle x,!} is at least as good as (outranks) y {displaystyle y,!} with respect to the criterion q {displaystyle q,!} . Without loss of generality, we assume that the domain of q {displaystyle q,!} is a subset of reals, V q ⊆ R {displaystyle V_{q}subseteq mathbb {R} } , and that the outranking relation is a simple order between real numbers ≥ {displaystyle geq ,!} such that the following relation holds: x ⪰ q y ⟺ f ( x , q ) ≥ f ( y , q ) {displaystyle xsucceq _{q}yiff f(x,q)geq f(y,q)} . This relation is straightforward for gain-type ('the more, the better') criterion, e.g. company profit. For cost-type ('the less, the better') criterion, e.g. product price, this relation can be satisfied by negating the values from V q {displaystyle V_{q},!} . Let T = { 1 , … , n } {displaystyle T={1,ldots ,n},!} . The domain of decision criterion, V d {displaystyle V_{d},!} consist of n {displaystyle n,!} elements (without loss of generality we assume V d = T {displaystyle V_{d}=T,!} ) and induces a partition of U {displaystyle U,!} into n {displaystyle n,!} classes Cl = { C l t , t ∈ T } {displaystyle { extbf {Cl}}={Cl_{t},tin T}} , where C l t = { x ∈ U : f ( x , d ) = t } {displaystyle Cl_{t}={xin Ucolon f(x,d)=t}} . Each object x ∈ U {displaystyle xin U} is assigned to one and only one class C l t , t ∈ T {displaystyle Cl_{t},tin T} . The classes are preference-ordered according to an increasing order of class indices, i.e. for all r , s ∈ T {displaystyle r,sin T} such that r ≥ s {displaystyle rgeq s,!} , the objects from C l r {displaystyle Cl_{r},!} are strictly preferred to the objects from C l s {displaystyle Cl_{s},!} . For this reason, we can consider the upward and downward unions of classes, defined respectively, as: We say that x {displaystyle x,!} dominates y {displaystyle y,!} with respect to P ⊆ C {displaystyle Psubseteq C} , denoted by x D p y {displaystyle xD_{p}y,!} , if x {displaystyle x,!} is better than y {displaystyle y,!} on every criterion from P {displaystyle P,!} , x ⪰ q y , ∀ q ∈ P {displaystyle xsucceq _{q}y,,forall qin P} . For each P ⊆ C {displaystyle Psubseteq C} , the dominance relation D P {displaystyle D_{P},!} is reflexive and transitive, i.e. it is a partial pre-order. Given P ⊆ C {displaystyle Psubseteq C} and x ∈ U {displaystyle xin U} , let represent P-dominating set and P-dominated set with respect to x ∈ U {displaystyle xin U} , respectively.