Decision-theoretic rough sets

Template:Short description Template:Multiple issues In the mathematical theory of decisions, decision-theoretic rough sets (DTRS) is a probabilistic extension of rough set classification. First created in 1990 by Dr. Yiyu Yao, the extension makes use of loss functions to derive $\alpha$ and $\beta$ region parameters. Like rough sets, the lower and upper approximations of a set are used.

Definitions

The following contains the basic principles of decision-theoretic rough sets.

Conditional risk

Using the Bayesian decision procedure, the decision-theoretic rough set (DTRS) approach allows for minimum-risk decision making based on observed evidence. Let $A=\{a_1,\dots ,a_m\}$ be a finite set of $m$ possible actions and let $\mathrm{\Omega }=\{w_1,\dots ,w_s\}$ be a finite set of $s$ states. $P(w_j\mid [x])$ is calculated as the conditional probability of an object $x$ being in state $w_j$ given the object description $[x]$. $\lambda (a_i\mid w_j)$ denotes the loss, or cost, for performing action $a_i$ when the state is $w_j$. The expected loss (conditional risk) associated with taking action $a_i$ is given by:

$R(a_i\mid [x])=\sum _{j=1}^s\lambda (a_i\mid w_j)P(w_j\mid [x]).$

Object classification with the approximation operators can be fitted into the Bayesian decision framework. The set of actions is given by $A=\{a_P,a_N,a_B\}$, where $a_P$, $a_N$, and $a_B$ represent the three actions in classifying an object into POS($A$), NEG($A$), and BND($A$) respectively. To indicate whether an element is in $A$ or not in $A$, the set of states is given by $\mathrm{\Omega }=\{A,A^c\}$. Let $\lambda (a_{\diamond }\mid A)$ denote the loss incurred by taking action $a_{\diamond }$ when an object belongs to $A$, and let $\lambda (a_{\diamond }\mid A^c)$ denote the loss incurred by take the same action when the object belongs to $A^c$.

Loss functions

Let ${\lambda }_{PP}$ denote the loss function for classifying an object in $A$ into the POS region, ${\lambda }_{BP}$ denote the loss function for classifying an object in $A$ into the BND region, and let ${\lambda }_{NP}$ denote the loss function for classifying an object in $A$ into the NEG region. A loss function ${\lambda }_{\diamond N}$ denotes the loss of classifying an object that does not belong to $A$ into the regions specified by $\diamond$.

Taking individual can be associated with the expected loss $R(a_{\diamond }\mid [x])$actions and can be expressed as:

$R(a_P\mid [x])={\lambda }_{PP}P(A\mid [x])+{\lambda }_{PN}P(A^c\mid [x]),$

$R(a_N\mid [x])={\lambda }_{NP}P(A\mid [x])+{\lambda }_{NN}P(A^c\mid [x]),$

$R(a_B\mid [x])={\lambda }_{BP}P(A\mid [x])+{\lambda }_{BN}P(A^c\mid [x]),$

where ${\lambda }_{\diamond P}=\lambda (a_{\diamond }\mid A)$, ${\lambda }_{\diamond N}=\lambda (a_{\diamond }\mid A^c)$, and $\diamond =P$, $N$, or $B$.

Minimum-risk decision rules

If we consider the loss functions ${\lambda }_{PP}\le {\lambda }_{BP}<{\lambda }_{NP}$ and ${\lambda }_{NN}\le {\lambda }_{BN}<{\lambda }_{PN}$, the following decision rules are formulated (P, N, B):

• P: If $P(A\mid [x])\ge \gamma$ and $P(A\mid [x])\ge \alpha$, decide POS($A$);
• N: If $P(A\mid [x])\le \beta$ and $P(A\mid [x])\le \gamma$, decide NEG($A$);
• B: If $\beta \le P(A\mid [x])\le \alpha$, decide BND($A$);

where,

$\alpha =\frac{{\lambda }_{PN}-{\lambda }_{BN}}{({\lambda }_{BP}-{\lambda }_{BN})-({\lambda }_{PP}-{\lambda }_{PN})},$

$\gamma =\frac{{\lambda }_{PN}-{\lambda }_{NN}}{({\lambda }_{NP}-{\lambda }_{NN})-({\lambda }_{PP}-{\lambda }_{PN})},$

$\beta =\frac{{\lambda }_{BN}-{\lambda }_{NN}}{({\lambda }_{NP}-{\lambda }_{NN})-({\lambda }_{BP}-{\lambda }_{BN})}.$

The $\alpha$, $\beta$, and $\gamma$ values define the three different regions, giving us an associated risk for classifying an object. When $\alpha >\beta$, we get $\alpha >\gamma >\beta$ and can simplify (P, N, B) into (P1, N1, B1):

• P1: If $P(A\mid [x])\ge \alpha$, decide POS($A$);
• N1: If $P(A\mid [x])\le \beta$, decide NEG($A$);
• B1: If $\beta <P(A\mid [x])<\alpha$, decide BND($A$).

When $\alpha =\beta =\gamma$, we can simplify the rules (P-B) into (P2-B2), which divide the regions based solely on $\alpha$:

• P2: If $P(A\mid [x])>\alpha$, decide POS($A$);
• N2: If $P(A\mid [x])<\alpha$, decide NEG($A$);
• B2: If $P(A\mid [x])=\alpha$, decide BND($A$).

Data mining, feature selection, information retrieval, and classifications are just some of the applications in which the DTRS approach has been successfully used.

See also

• Rough sets
• Granular computing
• Fuzzy set theory

External links

• The International Rough Set Society Template:Webarchive
• The Decision-theoretic Rough Set Portal