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) 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.
Data representation
Decision table
In DRSA, data are often presented using a particular form of decision table. Formally, a DRSA decision table is a 4-tuple , where is a finite set of objects, is a finite set of criteria, where is the domain of the criterion and is an information function such that for every . The set is divided into condition criteria (set ) and the decision criterion (class) . Notice, that is an evaluation of object on criterion , while 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 is completely preordered by an outranking relation ; means that is at least as good as (outranks) with respect to the criterion . Without loss of generality, we assume that the domain of is a subset of reals, , and that the outranking relation is a simple order between real numbers such that the following relation holds: . 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 .
Decision classes and class unions
Let . The domain of decision criterion, consist of elements (without loss of generality we assume ) and induces a partition of into classes , where . Each object is assigned to one and only one class . The classes are preference-ordered according to an increasing order of class indices, i.e. for all such that , the objects from are strictly preferred to the objects from . For this reason, we can consider the upward and downward unions of classes, defined respectively, as:
Main concepts
Dominance
We say that dominates with respect to , denoted by , if is better than on every criterion from , . For each , the dominance relation is reflexive and transitive, i.e. it is a partial pre-order. Given and , let
represent P-dominating set and P-dominated set with respect to , respectively.