Decision-theoretic rough sets

Decision-theoretic rough sets

Decision-theoretic rough sets (DTRS) is a probabilistic extension of rough set classification. First created in 1990 by Dr. Yiyu Yao[1], the extension makes use of loss functions to derive \textstyle \alpha and \textstyle \beta region parameters. Like rough sets, the lower and upper approximations of a set are used.



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 \textstyle A=\{a_1,\ldots,a_m\} be a finite set of \textstyle m possible actions and let \textstyle \Omega=\{w_1,\ldots, w_s\} be a finite set of s states. \textstyle P(w_j|[x]) is calculated as the conditional probability of an object \textstyle x being in state \textstyle w_j given the object description \textstyle [x]. \textstyle \lambda(a_i|w_j) denotes the loss, or cost, for performing action \textstyle a_i when the state is \textstyle w_j. The expected loss (conditional risk) associated with taking action \textstyle a_i is given by:

R(a_i|[x]) = \sum_{j=1}^{s}\lambda(a_i|w_j)P(w_j|[x]).

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

Loss Functions

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

Taking individual can be associated with the expected loss \textstyle R(a_\diamond|[x])actions and can be expressed as:

\textstyle R(a_P|[x]) = \lambda_{PP}P(A|[x]) + \lambda_{PN}P(A^c|[x]),

\textstyle R(a_N|[x]) = \lambda_{NP}P(A|[x]) + \lambda_{NN}P(A^c|[x]),

\textstyle R(a_B|[x]) = \lambda_{BP}P(A|[x]) + \lambda_{BN}P(A^c|[x]),

where \textstyle \lambda_{\diamond P}=\lambda(a_\diamond|A), \textstyle \lambda_{\diamond N}=\lambda(a_\diamond|A^c), and \textstyle \diamond=P, \textstyle N, or \textstyle B.

Minimum Risk Decision Rules

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

  • P: If \textstyle P(A|[x]) \geq \gamma and \textstyle P(A|[x]) \geq \alpha, decide POS(\textstyle A);
  • N: If \textstyle P(A|[x]) \leq \beta and \textstyle P(A|[x]) \leq \gamma, decide NEG(\textstyle A);
  • B: If \textstyle \beta \leq P(A|[x]) \leq \alpha, decide BND(\textstyle A);


\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 \textstyle \alpha, \textstyle \beta, and \textstyle \gamma values define the three different regions, giving us an associated risk for classifying an object. When \textstyle \alpha > \beta, we get \textstyle \alpha > \gamma > \beta and can simplify (P, N, B) into (P1, N1, B1):

  • P1: If \textstyle P(A|[x]) \geq \alpha, decide POS(\textstyle A);
  • N1: If \textstyle P(A|[x]) \leq \beta, decide NEG(\textstyle A);
  • B1: If \textstyle \beta < P(A|[x]) < \alpha, decide BND(\textstyle A).

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

  • P2: If \textstyle P(A|[x]) > \alpha, decide POS(\textstyle A);
  • N2: If \textstyle P(A|[x]) < \alpha, decide NEG(\textstyle A);
  • B2: If \textstyle P(A|[x]) = \alpha, decide BND(\textstyle 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


  1. ^ Yao, Y.Y.; Wong, S.K.M. and Lingras, P. (1990). "A decision-theoretic rough set model". Methodologies for Intelligent Systems, 5, Proceedings of the 5th International Symposium on Methodologies for Intelligent Systems (Knoxville, Tennessee, USA: North-Holland): 17–25. 

External links

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Info-gap decision theory — is a non probabilistic decision theory that seeks to optimize robustness to failure – or opportuneness for windfall – under severe uncertainty,[1][2] in particular applying sensitivity analysis of the stability radius type[3] to perturbations in… …   Wikipedia

  • Mathematical logic — (also known as symbolic logic) is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic.[1] The field includes both the mathematical study of logic and the… …   Wikipedia

  • Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… …   Wikipedia

  • Set theory — This article is about the branch of mathematics. For musical set theory, see Set theory (music). A Venn diagram illustrating the intersection of two sets. Set theory is the branch of mathematics that studies sets, which are collections of objects …   Wikipedia

  • probability theory — Math., Statistics. the theory of analyzing and making statements concerning the probability of the occurrence of uncertain events. Cf. probability (def. 4). [1830 40] * * * Branch of mathematics that deals with analysis of random events.… …   Universalium

  • Set (mathematics) — This article gives an introduction to what mathematicians call intuitive or naive set theory; for a more detailed account see Naive set theory. For a rigorous modern axiomatic treatment of sets, see Set theory. The intersection of two sets is… …   Wikipedia

  • Ferdinand Canning Scott Schiller — Infobox Philosopher region = Western Philosophy era = 19th/20th century philosophy color = #B0C4DE image caption = Ferdinand Canning Scott Schiller name = F.C.S. Schiller birth = August 16 1864 death = August 9 1937 school tradition = Pragmatism… …   Wikipedia

  • Deterrence theory — This article is about deterrent theories of punishment. For legal theory of justice, see Deterrence (legal). Deterrence theory gained increased prominence as a military strategy during the Cold War with regard to the use of nuclear weapons, and… …   Wikipedia

  • List of set theory topics — Logic portal Set theory portal …   Wikipedia

  • Ockham’s world and future — Arthur Gibson PHILOSOPHICAL BIOGRAPHY Ockham was born in about 1285, certainly before 1290, probably in the village of Ockham, Surrey, near London. If his epitaph is accurate, he died on 10 April 1347. Yet Conrad of Megenberg, when writing to… …   History of philosophy