# Dominance-based Rough Set Approach

**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 Greco, S., Matarazzo, B., Słowiński, R.: Rough sets theory for multicriteria decision analysis. European Journal of Operational Research,**129**, 1 (2001) 1--47] [*Greco, S., Matarazzo, B., Słowiński, R.: Multicriteria classification bydominance-based rough set approach. In: W.Kloesgen and J.Zytkow (eds.), Handbook of Data Mining and Knowledge Discovery, Oxford University Press, New York, 2002*] [*Słowiński, R., Greco, S., Matarazzo, B.: Rough set based decision support. Chapter 16 [in] : E.K. Burke and G. Kendall (eds.), Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, Springer-Verlag , New York (2005) 475-527*] . The main change comparing to the classicalrough sets is the substitution of the indiscernibility relation by a dominance relation, which permits to deal with inconsistencies typical to consideration of**criteria**and**preference-ordered decision classes**.**Multicriteria Classification (Sorting)**(sorting) is one of the problems considered withinMulticriteria classification 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 asordinal classification problem with monotonicity constraints and often appears in real-life application whenordinal 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 inknowledge discovery may lead to wrong conclusions.**Data Representation****Decision Table**In DRSA, data are often presented in the form of

**decision table**. Formally, a decision table is the 4-touple $S\; =\; langle\; U,\; Q,\; V,\; f\; angle$, where $U,!$ is a finite set of objects, $Q,!$ is a finite set of criteria, $V=igcup\; \{\}\_\{q\; in\; Q\}\; V\_q$ where $V\_q,!$ is the domain of the criterion $q,!$ and $f\; colon\; U\; imes\; Q\; o\; V$ is an "information function" such that $f(x,q)\; in\; V\_q$ for every $(x,q)\; in\; U\; imes\; Q$. The set $Q,!$ is divided into "condition criteria" (set $C\; eq\; emptyset$) and the "decision criterion" ("class") $d,!$. Notice, that $f(x,q),!$ is an evaluation of object $x,!$ on criterion $q\; in\; C$, while $f(x,d),!$ is the class assignment (decision value) of the object. An example of decision table is shown in Table 1 below.**Outranking Relation**It is assumed that the domain of a criterion $q\; in\; Q$ is completely

preorder ed by an$succeq\_q$; $x\; succeq\_q\; y$ means that $x,!$ is at least as good as (outranks) $y,!$ with respect to the criterion $q,!$. Without loss of generality, we assume that the domain of $q,!$ is a subset of reals, $V\_q\; subseteq\; mathbb\{R\}$, and that the outranking relation is a simple order between real numbers $geq,!$ such that the following relation holds: $x\; succeq\_q\; y\; iff\; 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,!$.outranking relation **Decision Classes and Class Unions**Let $T\; =\; \{1,ldots,n\},!$. The domain of decision criterion, $V\_d,!$ consist of $n,!$ elements (without loss of generality we assume $V\_d\; =\; T,!$) and induces a partition of $U,!$ into $n,!$ classes $extbf\{Cl\}=\{Cl\_t,\; t\; in\; T\}$, where $Cl\_t\; =\; \{x\; in\; U\; colon\; f(x,d)\; =\; t\}$. Each object $x\; in\; U$ is assigned to one and only one class $Cl\_t,\; t\; in\; T$. The classes are preference-ordered according to an increasing order of class indices, i.e. for all $r,s\; in\; T$ such that $r\; geq\; s,!$, the objects from $Cl\_r,!$ are strictly preferred to the objects from $Cl\_s,!$. For this reason, we can consider the

**upward and downward unions of classes**, defined respectively, as::$Cl^\{geq\}\_t\; =\; igcup\_\{s\; geq\; t\}\; Cl\_s\; qquad\; Cl^\{leq\}\_t\; igcup\_\{s\; leq\; t\}\; Cl\_s\; qquad\; t\; in\; T$

**Main Concepts****Dominance**We say that $x,!$

**dominates**$y,!$ with respect to $P\; subseteq\; C$, denoted by $x\; D\_p\; y,!$, if $x,!$ is better than $y,!$ on every criterion from $P,!$, $x\; succeq\_q\; y,\; ,\; forall\; q\; in\; P$. For each $P\; subseteq\; C$, the dominance relation $D\_P,!$ is reflexive and transitive, i.e. it is a partial pre-order. Given $P\; subseteq\; C$ and $x\; in\; U$, let:$D\_P^+(x)\; =\; \{y\; in\; U\; colon\; y\; D\_p\; x\; \}$

:$D\_P^-(x)\; =\; \{y\; in\; U\; colon\; x\; D\_p\; y\; \}$

represent

**"P"-dominating**set and**"P"-dominated**set with respect to $x\; in\; U$, respectively.**Rough Approximations**The key idea of the

rough set philosophy is approximation of one knowledge by another knowledge. In DRSA, the knowledge being approximated is a collection of upward and downward unions of decision classes and the "granules of knowledge" used for approximation are "P"-dominating and "P"-dominated sets.The

**"P"-lower**and the**"P"-upper approximation**of $Cl\_t^\{geq\},\; t\; in\; T$ with respect to $P\; subseteq\; C$, denoted as $underline\{P\}(Cl\_t^\{geq\})$ and $overline\{P\}(Cl\_t^\{geq\})$, respectively, are defined as::$underline\{P\}(Cl\_t^\{geq\})\; =\; \{x\; in\; U\; colon\; D\_P^+(x)\; subseteq\; Cl\_t^\{geq\}\; \}$

:$overline\{P\}(Cl\_t^\{geq\})\; =\; \{x\; in\; U\; colon\; D\_P^-(x)\; cap\; Cl\_t^\{geq\}\; eq\; emptyset\}$

Analogously, the "P"-lower and the "P"-upper approximation of $Cl\_t^\{leq\},\; t\; in\; T$ with respect to $P\; subseteq\; C$, denoted as $underline\{P\}(Cl\_t^\{leq\})$ and $overline\{P\}(Cl\_t^\{leq\})$, respectively, are defined as:

:$underline\{P\}(Cl\_t^\{leq\})\; =\; \{x\; in\; U\; colon\; D\_P^-(x)\; subseteq\; Cl\_t^\{leq\}\; \}$

:$overline\{P\}(Cl\_t^\{leq\})\; =\; \{x\; in\; U\; colon\; D\_P^+(x)\; cap\; Cl\_t^\{leq\}\; eq\; emptyset\}$

Lower approximations group the objects which "certainly" belong to class union $Cl^\{ge\}\_t$ (respectively $Cl^\{le\}\_t$). This certainty comes from the fact, that object $x\; in\; U$ belongs to the lower approximation $underline\{P\}(Cl^\{ge\}\_t)$ (respectively $underline\{P\}(Cl^\{le\}\_t)$), if no other object in $U,!$ contradicts this claim, i.e. every object $y\; in\; U$ which "P"-dominates $x,!$, also belong to the class union $Cl^\{ge\}\_t$ (respectively $Cl^\{le\}\_t$). Upper approximations group the objects which "could belong" to $Cl^\{ge\}\_t$ (respectively $Cl^\{le\}\_t$), since object $x\; in\; U$ belongs to the upper approximation $overline\{P\}(Cl^\{ge\}\_t)$ (respectively $overline\{P\}(Cl^\{le\}\_t)$), if there exist another object $y\; in\; U$

*P**-dominated by $x,!$ from class union $Cl^\{ge\}\_t$ (respectively $Cl^\{le\}\_t$).**The "P"-lower and "P"-upper approximations defined as above satisfy the following properties for all $t\; in\; T$ and for any $P\; subseteq\; C$:**:$underline\{P\}(Cl\_t^\{geq\})\; subseteq\; Cl\_t^\{geq\}\; subseteq\; overline\{P\}(Cl\_t^\{geq\})$**:$underline\{P\}(Cl\_t^\{leq\})\; subseteq\; Cl\_t^\{leq\}\; subseteq\; overline\{P\}(Cl\_t^\{leq\})$**The***"P"-boundaries**("P-doubtful regions") of $Cl\_t^\{geq\}$ and $Cl\_t^\{leq\}$ are defined as:*:$Bn\_P(Cl\_t^\{geq\})\; =\; overline\{P\}(Cl\_t^\{geq\})-underline\{P\}(Cl\_t^\{geq\})$**:$Bn\_P(Cl\_t^\{leq\})\; =\; overline\{P\}(Cl\_t^\{leq\})-underline\{P\}(Cl\_t^\{leq\})$***Quality of Approximation and Reducts***The ratio**:$gamma\_P(\; extbf\{Cl\})\; =\; frac\{left|U\; -\; left(\; left(\; igcup\_\{t\; in\; T\}\; Bn\_P(Cl\_t^\{geq\})\; ight)\; cup\; left(\; igcup\_\{t\; in\; T\}\; Bn\_P(Cl\_t^\{leq\})\; ight)\; ight)\; ight$**defines the***quality of approximation**of the partition $extbf\{Cl\},!$ into classes by means of the set of criteria $P,!$. This ratio express the relation between all the "P"-correctly classified objects and all the objects in the table.*Every minimal subset $P\; subseteq\; C$ such that $gamma\_P(mathbf\{Cl\})\; =\; gamma\_C(mathbf\{Cl\}),!$ is called a*of $C,!$ and is denoted by $RED\_\{mathbf\{Cl(P)$. A decision table may have more than one reduct. The intersection of all reducts is known as the "core".reduct **Decision Rules***On the basis of the approximations obtained by means of the dominance relations, it is possible to induce a generalized description of the preferential information contained in the decision table, in terms of*. The decision rules are expressions of the form "if" [condition] "then" [consequent] , that represent a form of dependency between condition criteria and decision criteria. Procedures for generating decision rules from a decision table use an inducive learning principle. We can distinguish three types of rules: certain, possible and approximate. Certain rules are generated from lower approximations of unions of classes; possible rules are generated from upper approximations of unions of classes and approximate rules are generated from boundary regions.decision rules *Certain rules has the following form:**:if $f(x,q\_1)\; geq\; r\_1,!$ and $f(x,q\_2)\; geq\; r\_2,!$ and $ldots\; f(x,q\_p)\; geq\; r\_p,!$ then $x\; in\; Cl\_t^\{geq\}$**:if $f(x,q\_1)\; leq\; r\_1,!$ and $f(x,q\_2)\; leq\; r\_2,!$ and $ldots\; f(x,q\_p)\; leq\; r\_p,!$ then $x\; in\; Cl\_t^\{leq\}$**Possible rules has a similar syntax, however the "consequent" part of the rule has the form: $x,!$ "could belong to" $Cl\_t^\{geq\}$ or the form: $x,!$ "could belong to" $Cl\_t^\{leq\}$.**Finally, approximate rules has the syntax:**:if $f(x,q\_1)\; geq\; r\_1,!$ and $f(x,q\_2)\; geq\; r\_2,!$ and $ldots\; f(x,q\_k)\; geq\; r\_k,!$ and $f(x,q\_\{k+1\})\; leq\; r\_\{k+1\},!$ and $f(x,q\_\{k+2\})\; leq\; r\_\{k+2\},!$ and $ldots\; f(x,q\_p)\; leq\; r\_p,!$then $x\; in\; Cl\_s\; cup\; Cl\_\{s+1\}\; cup\; Cl\_t$**The certain, possible and approximate rules represent certain, possible and ambiguous knowledge extracted from the decision table.**Each decision rule should be minimal. Since a decision rule is animplication, by a minimal decision rule we understand such an implication that there isno other implication with an antecedent of at least the same weakness (in other words,rule using a subset of elementary conditions or/and weaker elementary conditions)and a consequent of at least the same strength (in other words, rule assigning objectsto the same union or sub-union of classes).**A set of decision rules is "complete" if it is able to cover all objects from the decision table in such a way that consistent objects are re-classified to their original classes and inconsistent objects are classified to clusters of classes referring to this inconsistency. We call "minimal" each set of decision rules that is complete and non-redundant, i.e. exclusion of any rule from this set makes it non-complete.One of three induction strategies can be adopted to obtain a set of decision rules [**Stefanowski, J.: On rough set based approach to induction of decision rules. In Skowron, A., Polkowski, L. (eds.): Rough Set in Knowledge Discovering, Physica Verlag, Heidelberg (1998) 500--529*] :** generation of a minimal description, i.e. a minimal set of rules,*** generation of an exhaustive description, i.e. all rules for a given data matrix,*** generation of a characteristic description, i.e. a set of rules covering relatively many objects each, however, all together not necessarily all objects from the decision table**The most popular rule induction algorithm for dominance-based rough set approach is DOMLEM [**Greco S., Matarazzo, B., Słowiński, R., Stefanowski, J.: An Algorithm for Induction of Decision Rules Consistent with the Dominance Principle. In W. Ziarko, Y. Yao (eds.): Rough Sets and Current Trends in Computing. Lecture Notes in Artificial Intelligence*] , which generates minimal set of rules.**2005**(2001) 304--313. Springer-Verlag**Example***Consider the following problem of high school students evaluations:**:**Each object (student) is described by three criteria $q\_1,q\_2,q\_3,!$, related to the levels in Mathematics, Physics and Literatire, respectively. According to the decision attribute, the students are divided into three preference-ordered classes: $Cl\_1\; =\; \{bad\}$, $Cl\_2\; =\; \{medium\}$ and $Cl\_3\; =\; \{good\}$. Thus, the following unions of classes were approximated:*** $Cl\_1^\{leq\}$ i.e. the class of (at most) bad students,*** $Cl\_2^\{leq\}$ i.e. the class of at most medium students,*** $Cl\_2^\{geq\}$ i.e. the class of at least medium students,*** $Cl\_3^\{geq\}$ i.e. the class of (at least) good students.**Notice that evaluations of objects $x\_4,!$ and $x\_6,!$ are inconsistent, because $x\_4,!$ has better evaluations on all three criteria than $x\_6,!$ but worse global score.**Therefore, lower approximations of class unions consist of the following objects:**:$underline\{P\}(Cl\_1^\{leq\})\; =\; \{x\_1,x\_5\}$**:$underline\{P\}(Cl\_2^\{leq\})\; =\; \{x\_1,x\_2,x\_3,x\_4,x\_5,x\_6,x\_8\}\; =\; Cl\_2^\{leq\}$**:$underline\{P\}(Cl\_2^\{geq\})\; =\; \{x\_2,x\_3,x\_7,x\_8,x\_9,x\_\{10\}\}$**:$underline\{P\}(Cl\_3^\{geq\})\; =\; \{x\_7,x\_9,x\_\{10\}\}\; =\; Cl\_3^\{geq\}$**Thus, only classes $Cl\_1^\{leq\}$ and $Cl\_2^\{geq\}$ cannot be approximated precisely. Their upper approximations are as follows:**:$overline\{P\}(Cl\_1^\{leq\})\; =\; \{x\_1,x\_4,x\_5,x\_6\}$**:$overline\{P\}(Cl\_2^\{geq\})\; =\; \{x\_2,x\_3,x\_4,x\_6,x\_7,x\_8,x\_9,x\_\{10\}\}$**while their boundary regions are:**:$Bn\_P(Cl\_1^\{leq\})\; =\; Bn\_P(Cl\_2^\{geq\})\; =\; \{x\_4,x\_6\}$**Of course, since $Cl\_2^\{leq\}$ and $Cl\_3^\{geq\}$ are approximated precisely, we have $overline\{P\}(Cl\_2^\{leq\})=Cl\_2^\{leq\}$, $overline\{P\}(Cl\_3^\{geq\})=Cl\_3^\{geq\}$ and $Bn\_P(Cl\_2^\{leq\})\; =\; Bn\_P(Cl\_3^\{geq\})\; =\; emptyset$**The following minimal set of 9 rules can be induced from the decision table:**# "if" $Physics\; leq\; bad$ "then" $student\; leq\; bad$*

# "if" $Literature\; leq\; bad$ "and" $Physics\; leq\; medium$ "and" $Math\; leq\; medium$ "then" $student\; leq\; bad$

# "if" $Math\; leq\; bad$ "then" $student\; leq\; medium$

# "if" $Literature\; leq\; medium$ "then" $student\; leq\; medium$

# "if" $Literature\; geq\; good$ "and" $Math\; geq\; medium$ "then" $student\; geq\; good$

# "if" $Physics\; geq\; good$ "and" $Math\; geq\; good$ "then" $student\; geq\; good$

# "if" $Math\; geq\; good$ "then" $student\; geq\; medium$

# "if" $Physics\; geq\; good$ "then" $student\; geq\; medium$

# "if" $Math\; leq\; bad$ "and" $Physics\; geq\; medium$ "then" $student\; =\; bad\; lor\; medium$*The last rule is approximate, while the rest are certain.***Extensions****Multicriteria Choice and Ranking Problems***The other two problems considered within*Multicriteria Decision Analysis ,Multicriteria Choice andRanking Problems, can also be solved using dominance-based rough set approach. This is done by converting the decision table intopairwise comparison table (PCT).**Variable-consistency DRSA***The definitions of rough approximations are based on a strict application of the dominance principle. However, when defining non-ambiguous objects, it is reasonable to accept a limited proportion of negative examples, particularly for large decision tables. Such extended version of DRSA is called*[Variable-Consistency DRSA model (VC-DRSA)*Greco, S., B. Matarazzo, R. Slowinski and J. Stefanowski: Variable consistency model of dominance-based rough set approach. In W.Ziarko, Y.Yao (eds.): Rough Sets and Current Trends in Computing. Lecture Notes in Artificial Intelligence*]**2005**(2001) 170-181. Springer-Verlag**tochastic DRSA***In real-life data, particularly for large datasets, the notions of rough approximations were found to be excessively restrictive. Therefore an extension of DRSA, based on stochastic model (***Stochastic DRSA**), which allows inconsistencies to some degree, has been introduced [*Dembczyński, K., Greco, S., Kotłowski, W., Słowiński, R.: Statistical model for rough set approach to multicriteria classification. In Kok, J.N., Koronacki, J., de Mantaras, R.L., Matwin, S., Mladenic, D., Skowron, A. (eds.): Knowledge Discovery in Databases: PKDD 2007, Warsaw, Poland. Lecture Notes in Computer Science*] . Having stated the probabilistic model for ordinal classification problems with monotonicity constraints, the concepts of lower approximations are extended to thestochastic case. The method is based on estimating the conditional probabilities using the nonparametric**4702**(2007) 164--175.maximum likelihood method which leadsto the problem ofisotonic regression .*Stochastic dominance-based rough sets can also be regarded as a sort of variable-consistency model.***Software***[**http://idss.cs.put.poznan.pl/site/software.html 4eMka2*] is adecision support system for multiple criteria classification problems based on dominance-based rough sets (DRSA). [*http://idss.cs.put.poznan.pl/site/jamm.html JAMM*] is a much more advanced successor of 4eMka2. Both systems are freely available for non-profit purposes on the [*http://idss.cs.put.poznan.pl Laboratory of Intelligent Decision Support Systems (IDSS)*] website.**See also*****Rough sets

*Soft computing

*Granular computing

* Multicriteria Decision Analysis (MCDA)**References****External links**** [**http://www.roughsets.org The International Rough Set Society*]

* [*http://idss.cs.put.poznan.pl Laboratory of Intelligent Decision Support Systems (IDSS)*] at [*http://put.poznan.pl Poznań University of Technology*] .

* Extensive list of DRSA references on the [*http://idss.cs.put.poznan.pl/site/rslowinski.html Roman Słowiński*] home page.

*Wikimedia Foundation.
2010.*

*
*### Look at other dictionaries:

**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. [1][2][3] The main change comparing to the classical rough sets is the substitution of the indiscernibility… … Wikipedia**Rough set**— A rough set originated by prof. Zdzisław I. Pawlak is a formal approximation of a crisp set (i.e., conventional set ) in terms of a pair of sets which give the lower and the upper approximation of the original set. The lower and upper… … Wikipedia**Multi-criteria decision analysis**— Multiple criteria decision making or multiple criteria decision analysis is a sub discipline of operations research that explicitly considers multiple criteria in decision making environments. Whether in our daily lives or in professional… … Wikipedia**Multicriteria classification**— In multiple criteria decision aiding (MCDA), multicriteria classification (or sorting) involves problems where a finite set of alternative actions should be assigned into a predefined set of preferentially ordered categories (classes).[1] For… … Wikipedia**Multi-Criteria Decision Analysis**— (MCDA), or Multi Criteria Decision Making (MCDM), is a discipline aimed at supporting decision makers who are faced with making numerous and conflicting evaluations. MCDA aims at highlighting these conflicts and deriving a way to come to a… … Wikipedia**Decision table**— Decision tables are a precise yet compact way to model complicated logic.[1] Decision tables, like flowcharts and if then else and switch case statements, associate conditions with actions to perform, but in many cases do so in a more elegant way … Wikipedia**Decision-making paradox**— The word paradox (parádoxon (παράδοξον) in Greek) comes from the Greek words para (meaning against, contrary to) and doksa or doxa (meaning belief, understanding). A paradox is a seemingly true statement or group of statements that lead to a… … Wikipedia**DRSA**— may refer to: Dominance based rough set approach (theoretical computer science) Deep River Science Academy (an organization in Ontario, Canada) This disambiguation page lists articles associated with the same title. If an … Wikipedia**South Asian arts**— Literary, performing, and visual arts of India, Pakistan, Bangladesh, and Sri Lanka. Myths of the popular gods, Vishnu and Shiva, in the Puranas (ancient tales) and the Mahabharata and Ramayana epics, supply material for representational and… … Universalium**American literature**— Introduction the body of written works produced in the English language in the United States. Like other national literatures, American literature was shaped by the history of the country that produced it. For almost a century and a… … Universalium