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 approximation sets themselves are crisp sets in the standard version of rough set theory (Pawlak 1991), but in other variations, the approximating sets may be fuzzy sets as well.

Definitions

This section contains an explanation of the basic framework of rough set theory (proposed originally by Zdzisław I. Pawlak), along with some of the key definitions. A review of this basic material can be found in sources such as Pawlak (1991), Ziarko (1998), Ziarko & Shan (1995), and many others.

Information system framework

Let $I\; =\; (mathbb\{U\},mathbb\{A\})$ be an information system (attribute-value system), where $mathbb\{U\}$ is a non-empty set of finite objects (the universe) and $mathbb\{A\}$ is a non-empty finite set of attributes such that $a:mathbb\{U\}\; ightarrow\; V\_a$ for every $a\; in\; mathbb\{A\}$. $V\_a$ is the set of values that attribute $a$ may take. In words, the information table simply assigns a value in $V\_a$ to each attribute $a$ of each object in universe $mathbb\{U\}$.

With any $P\; subseteq\; mathbb\{A\}$ there is an associated equivalence relation $mathrm\{IND\}(P)$:

:$mathrm\{IND\}(P)\; =\; left\{(x,y)\; in\; mathbb\{U\}^2\; mid\; forall\; a\; in\; P,\; a(x)=a(y)\; ight\}$

The partition of $mathbb\{U\}$ generated by $mathrm\{IND\}(P)$ isdenoted $mathbb\{U\}/mathrm\{IND\}(P)$ (or $mathbb\{U\}/P$) and can becalculated as follows:

:$mathbb\{U\}/mathrm\{IND\}(P)\; =\; otimes\; left\{mathbb\{U\}/mathrm\{IND\}(\{a\})\; mid\; ain\; P\; ight\},$

where

:$A\; otimes\; B\; =\; left\{Xcap\; Y\; mid\; forall\; X\; in\; A,\; forall\; Y\; in\; B,\; X\; cap\; Y\; eq\; emptyset\; ight\}$

If $(x,y)in\; mathrm\{IND\}(P)$, then $x$ and $y$ are indiscernible by attributes from $P$. In words, for any selected subset of attributes $P$, there will be sets of objects that are indiscernible based on those attributes. These indistinguishable sets of objects therefore define an equivalence or indiscernibility relation, referred to as the $P$-indiscernibility relation.

Example: equivalence class structure

For example, consider the following information table:

:

To read this decision matrix, look, for example, at the intersection of row $O\_\{3\}$ and column $O\_\{6\}$, showing $P\_1^2,P\_3^0$ in the cell. This means that "with regard to" decision value $P\_\{4\}=1$, object $O\_\{3\}$ differs from object $O\_\{6\}$ on attributes $P\_1$ and $P\_3$, and the particular values on these attributes for the positive object $O\_\{3\}$ are $P\_1=2$ and $P\_3=0$. This tells us that the correct classification of $O\_\{3\}$ as belonging to decision class $P\_\{4\}=1$ rests on attributes $P\_1$ and $P\_3$; although one or the other might be dispensable, we know that at least one of these attributes is indispensable.

Writing the rules

Next, from each decision matrix we form a set of Boolean expressions, one expression for each row of the matrix. The items within each cell are aggregated disjunctively, and the individuals cells are then aggregated conjunctively. Thus, for the above table we have the following five Boolean expressions:

:

Each statement here is essentially a highly specific (probably "too" specific) rule governing the membership in class $P\_\{4\}=1$ of the corresponding object. For example, the last statement, corresponding to object $O\_\{10\}$, states that all the following must be satisfied:
# Either $P\_1$ must have value 2, or $P\_3$ must have value 0, or both.
# $P\_2$ must have value 0.
# Either $P\_1$ must have value 2, or $P\_3$ must have value 0, or both.
# Either $P\_1$ must have value 2, or $P\_2$ must have value 0, or $P\_3$ must have value 0, or any combination thereof.
# $P\_2$ must have value 0.

It is clear that there is a large amount of redundancy here, and the next step is to simplify using traditional Boolean algebra. The statement $(P\_1^1\; or\; P\_2^2\; or\; P\_3^0)\; and\; (P\_1^1\; or\; P\_2^2)\; and\; (P\_1^1\; or\; P\_2^2\; or\; P\_3^0)\; and\; (P\_1^1\; or\; P\_2^2\; or\; P\_3^0)\; and\; (P\_1^1\; or\; P\_2^2)$ corresponding to objects $\{O\_\{1\},O\_\{2\}\}$ simplifies to $P\_1^1\; or\; P\_2^2$, which yields the implication

:$(P\_1=1)\; or\; (P\_2=2)\; o\; (P\_\{4\}=1)$

Likewise, the statement $(P\_1^2\; or\; P\_3^0)\; and\; (P\_2^0)\; and\; (P\_1^2\; or\; P\_3^0)\; and\; (P\_1^2\; or\; P\_2^0\; or\; P\_3^0)\; and\; (P\_2^0)$ corresponding to objects $\{O\_\{3\},O\_\{7\},O\_\{10\}\}$ simplifies to $P\_1^2\; P\_2^0\; or\; P\_3^0\; P\_2^0$. This gives us the implication

:$(P\_1=2\; and\; P\_2=0)\; or\; (P\_3=0\; and\; P\_2=0)\; o\; (P\_\{4\}=1)$

The above implications can also be written as the following rule set:

:

It can be noted that each of the first two rules has a "support" of 2 (i.e., the antecedent matches two objects), while each of the last two rules has a support of 3. To finish writing the rule set for this knowledge system, the same procedure as above (starting with writing a new decision matrix) should be followed for the case of $P\_\{4\}=2$, thus yielding a new set of implications for that decision value (i.e., a set of implications with $P\_\{4\}=2$ as the consequent). In general, the procedure will be repeated for each possible value of the decision variable. Other rule-learning methods can be found in Pawlak (1991), Stefanowski (1998), Bazan et al. (2004), etc.

Applications

Rough sets can be used as a theoretical basis for some problems in machine learning. They have found to be particularly useful for rule induction and feature selection (semantics-preserving dimensionality reduction). They have been used for missing data estimation as well as understanding HIV. They have also inspired some logical research.Fact|date=February 2007

Extensions

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 (2001). The main change comparing to the classical rough 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".

History

The idea of rough set was proposed by Pawlak (1991) as a new mathematical tool to deal with vague concepts. Comer, Grzymala-Busse, Iwinski, Nieminen, Novotny, Pawlak, Obtulowicz, and Pomykala have studied algebraic properties of rough sets. Different algebraic semantics have been developed by P. Pagliani, I. Duntsch, M. K. Chakraborty, M. Banerjee and A. Mani. These have been extended to more generalized rough sets by D. Cattaneo and A. Mani in particular. Rough sets can be used to represent ambiguity, vagueness and general uncertainty. Fuzzy-rough sets further extend the rough set concept through the use of fuzzy equivalence classes.

ee also

* Algebraic semantics
* Alternative set theory
* Description logic
* Fuzzy logic
* Fuzzy set theory
* Generalized rough set theory
* Granular computing
* Rough-fuzzy hybridization
* Semantics of rough set theory
* Soft computing
* Variable precision rough set
* Version space
* Dominance-based Rough Set Approach

References

*cite journal
last = Bazan
first = Jan
coauthors = Nguyen, Hung Son and Szczuka, Marcin
title = A view on rough set concept approximations
journal = Fundamenta Informaticae
volume = 59
pages = 107–118
date = 2004
*cite journal
last = Chanas
first = Stefan
coauthors = Kuchta, Dorota
title = Further remarks on the relation between rough and fuzzy sets
journal = Fuzzy Sets and Systems
volume = 47
issue = 3
pages = 391–394
date = 1992
doi = 10.1016/0165-0114(92)90305-N
*cite journal
last = Comer
first = Stephen D.
title = An algebraic approach to the approximation of information
journal = Fundamenta Informaticae
volume = 14
issue = 4
pages = 495–502
date = 1991
*cite journal
last = Dubois
first = D.
coauthor = Prade, H.
title = Rough fuzzy sets and fuzzy rough sets
journal = International Journal of General Systems
volume = 17
pages = 191–209
date = 1990
doi = 10.1080/03081079008935107
*cite journal
last = Greco
first = Salvatore
coauthors = Matarazzo, Benedetto and Słowiński, Roman
title = Rough sets theory for multicriteria decision analysis
journal = European Journal of Operational Research
volume = 129
issue = 1
date = 2001
pages = 1–47
doi = 10.1016/S0377-2217(00)00167-3
*cite journal
last = Jensen
first = Richard
coauthors = Shen, Qiang
title = Semantics-Preserving Dimensionality Reduction: Rough and Fuzzy-Rough Based Approaches
journal = IEEE Transactions on Knowledge and Data Engineering
volume = 16
issue = 12
pages = 1457–1471
date = 2004
doi = 10.1109/TKDE.2004.96
*cite journal
last = Nelwamondo
first = Vincent
coauthors = Marwala, Tshilidzi
title = Rough sets: Rough Set Theory for the Treatment of Incomplete Data
journal = Proceedings of the IEEE Conference on Fuzzy Systems.
pages = 338–343
date = 2007
*cite journal
last = Tettey
first = Thando
coauthors = Nelwamondo, F.V. and Marwala, Tshilidzi
title = Rough sets: HIV Data Analysis via Rule Extraction using Rough Sets
journal = Proceedings of IEEE International Conference on Intelligent Engineering Systems
pages = 105–110
date = 2007
*cite journal
last = Pawlak
first = Zdzisław
coauthors = Wong, S. K. M. and Ziarko, Wojciech
title = Rough sets: Probabilistic versus deterministic approach
journal = International Journal of Man-Machine Studies
volume = 29
pages = 81–95
date = 1988
*cite book
last = Pawlak
first = Zdzisław
title = Rough Sets: Theoretical Aspects of Reasoning About Data
publisher = Kluwer Academic Publishing
date = 1991
location = Dordrecht
id = ISBN 0-7923-1472-7
*cite conference
first = Jerzy
last = Stefanowski
title = On rough set based approaches to induction of decision rules
booktitle = Rough Sets in Knowledge Discovery 1: Methodology and Applications
pages = 500–529
publisher = Physica-Verlag
editor = Polkowski, Lech and Skowron, Andrzej
date = 1998
location = Heidelberg
*cite journal
last = Wong
first = S. K. M.
coauthors = Ziarko, Wojciech and Ye, R. Li
title = Comparison of rough-set and statistical methods in inductive learning
journal = International Journal of Man-Machine Studies
volume = 24
pages = 53–72
date = 1986
*cite conference
first = J. T.
last = Yao
coauthors = Yao, Y. Y.
title = Induction of classification rules by granular computing
booktitle = Proceedings of the Third International Conference on Rough Sets and Current Trends in Computing (TSCTC'02)
pages = 331–338
publisher = Springer-Verlag
date = 2002
location = London, UK
*cite conference
first = Wojciech
last = Ziarko
title = Rough sets as a methodology for data mining
booktitle = Rough Sets in Knowledge Discovery 1: Methodology and Applications
pages = 554–576
publisher = Physica-Verlag
date = 1998
location = Heidelberg
*cite conference
first = Wojciech
last = Ziarko
coauthors = Shan, Ning
title = Discovering attribute relationships, dependencies and rules by using rough sets
booktitle = Proceedings of the 28th Annual Hawaii International Conference on System Sciences (HICSS'95)
pages = 293–299
date = 1995
location = Hawaii

External links

* [http://www.roughsets.org The International Rough Set Society]
* [http://www.uit.edu.vn/forum/index.php?act=Attach&type=post&id=19757 Rough set tutorial]
* [http://www.ghastlyfop.com/blog/2006/01/rough-sets-quick-tutorial.html Example-based simple tutorial]