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\}\; rightarrow\; 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)right}

The partition of $mathbb\{U\}$ generated by $mathrm\{IND\}(P)$ is denoted $mathbb\{U\}/mathrm\{IND\}(P)$ (or $mathbb\{U\}/P$) and can be calculated as follows:

$$

mathbb{U}/mathrm{IND}(P) = otimes left{mathbb{U}/mathrm{IND}({a}) mid ain P right},

where

$$

A otimes B = left{Xcap Y mid forall X in A, forall Y in B, X cap Y neq emptysetright}

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:

Sample Information System

Object	$P\_\{1\}$	$P\_\{2\}$	$P\_\{3\}$	$P\_\{4\}$	$P\_\{5\}$
$O\_\{1\}$	1	2	0	1	1
$O\_\{2\}$	1	2	0	1	1
$O\_\{3\}$	2	0	0	1	0
$O\_\{4\}$	0	0	1	2	1
$O\_\{5\}$	2	1	0	2	1
$O\_\{6\}$	0	0	1	2	2
$O\_\{7\}$	2	0	0	1	0
$O\_\{8\}$	0	1	2	2	1
$O\_\{9\}$	2	1	0	2	2
$O\_\{10\}$	2	0	0	1	0

When the full set of attributes $P\; =\; \{P\_\{1\},P\_\{2\},P\_\{3\},P\_\{4\},P\_\{5\}\}$ is considered, we see that we have the following seven equivalence classes:

$$

begin{cases} {O_{1},O_{2}} {O_{3},O_{7},O_{10}} {O_{4}} {O_{5}} {O_{6}} {O_{8}} {O_{9}} end{cases}

Thus, the two objects within the first equivalence class, $\{O\_\{1\},O\_\{2\}\}$, cannot be distinguished from one another based on the available attributes, and the three objects within the second equivalence class, $\{O\_\{3\},O\_\{7\},O\_\{10\}\}$, cannot be distinguished from one another based on the available attributes. The remaining five objects are each discernible from all other objects. The equivalence classes of the $P$-indiscernibility relation are denoted $[x]\_P$.

It is apparent that different attribute subset selections will in general lead to different indiscernibility classes. For example, if attribute $P\; =\; P\_\{1\}$ alone is selected, we obtain the following much coarser equivalence class structure:

$$

begin{cases} {O_{1},O_{2}} {O_{3},O_{5},O_{7},O_{9},O_{10}} {O_{4},O_{6},O_{8}} end{cases}

Definition of rough set

Let $X\; subseteq\; mathbb\{U\}$ be a target set that we wish to represent using attribute subset $P$. That is, we are told that an arbitrary set of objects $X$ comprising a single class, and we wish to express this class (i.e., this subset) using the equivalence classes induced by attribute subset $P$. In general, $X$ cannot be expressed exactly, because the set may include and exclude objects which are indistinguishable based on attributes $P$.

For example, consider the target set $X\; =\; \{O\_\{1\},O\_\{2\},O\_\{3\},O\_\{4\}\}$, and let attribute subset $P\; =\; \{P\_\{1\},\; P\_\{2\},\; P\_\{3\},\; P\_\{4\},\; P\_\{5\}\}$, the full available set of features. It will be noted that the set $X$ cannot be expressed exactly because in $[x]\_P,$ objects $\{O\_\{3\},\; O\_\{7\},\; O\_\{10\}\}$ are indiscernible. Thus, there is no way to represent any set $X$ which includes $O\_\{3\}$ but excludes objects $O\_\{7\}$ and $O\_\{10\}$.

However, the target set $X$ can be approximated using only the information contained within $P$ by constructing the $P$-lower and $P$-upper approximations of $X$:

$$

{underline P}X= {x mid [x]_P subseteq X}

$$

{overline P}X = {x mid [x]_P cap X neq emptyset }

Lower approximation and positive region

The $P$-lower approximation or positive region is the union of all equivalence classes in $[x]\_P$ which are contained by (i.e., are subsets of) the target set. In the example, $\{underline\; P\}X\; =\; \{O\_\{1\},\; O\_\{2\}\}\; cup\; \{O\_\{4\}\}$, the union of the two equivalence classes in $[x]\_P$ which are contained in the target set. The lower approximation is the complete set of objects in $mathbb\{U\}/P$ that can be positively (i.e., unambiguously) classified as belonging to target set $X$.

Upper approximation and negative region

The $P$-upper approximation is the union of all equivalence classes in $[x]\_P$ which have non-empty intersection with the target set. In the example, $\{overline\; P\}X\; =\; \{O\_\{1\},\; O\_\{2\}\}\; cup\; \{O\_\{4\}\}\; cup\; \{O\_\{3\},\; O\_\{7\},\; O\_\{10\}\}$, the union of the three equivalence classes in $[x]\_P$ that have non-empty intersection with the target set. The upper approximation is the complete set of objects that in $mathbb\{U\}/P$ that cannot be positively (i.e., unambiguously) classified as belonging to the complement of the target set $overline\; X$. In other words, the upper approximation is the complete set of objects that are possibly members of the target set $X$.

The set $mathbb\{U\}-\{overline\; P\}X$ therefore represents the negative region, containing the set of objects that can be definitely ruled out as members of the target set.

Boundary region

The boundary region, given by set difference $\{overline\; P\}X\; -\; \{underline\; P\}X$, consists of those objects that can neither be ruled in nor ruled out as members of the target set $X$.

In summary, the lower approximation of a target set is a conservative approximation consisting of only those objects which can positively be identified as members of the set. (These objects have no indiscernible "clones" which are excluded by the target set.) The upper approximation is a liberal approximation which includes all objects that might be members of target set. (Some objects in the upper approximation may not be members of the target set.) From the perspective of $mathbb\{U\}/P$, the lower approximation contains objects that are members of the target set with certainty (probability = 1), while the upper approximation contains objects that are members of the target set with nonzero probability (probability > 0).

The rough set

The tuple $langle\{underline\; P\}X,\{overline\; P\}Xrangle$ composed of the lower and upper approximation is called a rough set. Thus, a rough set is composed of two crisp sets, one representing a lower boundary of the target set $X$, and one representing an upper boundary of the target set $X$.

The accuracy of the rough set representation of the set $X$ can be given (Pawlak 1991) by the following:

$$

alpha_{P}(X) = frac{left | {underline P}X right {left | {overline P}X right

That is, the accuracy of the rough set representation of $X$, $alpha\_\{P\}(X)$, $0\; leq\; alpha\_\{P\}(X)\; leq\; 1$, is the ratio of the number of objects which can be positively placed in $X$ to the number of objects that can be possibly be placed in $X$. This provides a measure of how closely the rough set is approximating the target set. Clearly, when the upper and lower approximations are equal (i.e., boundary region empty), then $alpha\_\{P\}(X)\; =\; 1$, and the approximation is perfect. Whenever the lower approximation is empty, the accuracy is zero (regardless of the size of the upper approximation).

Formal properties of rough sets

The important formal properties of rough sets and boundaries are given in Pawlak (1991), and the other sources cited by that book.

Definability

In general, the upper and lower approximations are not equal. In such cases we say that target set $X$ is undefinable or roughly definable on attribute set $P$. When the upper and lower approximations are equal (i.e., the boundary is empty), $\{overline\; P\}X\; =\; \{underline\; P\}X$, then the target set $X$ is definable on attribute set $P$. We can distinguish the following special cases of undefinability (Pawlak, Wong, & Ziarko 1988):

• Set $X$ is internally definable if $\{underline\; P\}X\; neq\; emptyset$ and $\{overline\; P\}X\; =\; mathbb\{U\}$. This means that on attribute set $P$, there are objects which we can be certain belong to target set $X$, but there are no objects which we can definitively exclude from set $X$.
• Set $X$ is externally definable if $\{underline\; P\}X\; =\; emptyset$ and $\{overline\; P\}X\; neq\; mathbb\{U\}$. This means that on attribute set $P$, there are no objects which we can be certain belong to target set $X$, but there are objects which we can definitively exclude from set $X$.
• Set $X$ is totally non-definable if $\{underline\; P\}X\; =\; emptyset$ and $\{overline\; P\}X\; =\; mathbb\{U\}$. This means that on attribute set $P$, there are no objects which we can be certain belong to target set $X$, and there are no objects which we can definitively exclude from set $X$. Thus, on attribute set $P$, we cannot decide whether any object is, or is not, a member of $X$.

Reduct and core

An interesting question is whether there are attributes in the information system (attribute-value table) which are more important to the knowledge represented in the equivalence class structure than other attributes. Often we wonder whether there is a subset of attributes which by itself can fully characterize the knowledge in the database. Such an attribute set is called a reduct.

Formally (Ziarko & Shan 1995), a reduct is a subset of attributes $mathrm\{RED\}\; subseteq\; P$ such that

• $[x]\_\{mathrm\{RED\}\}$ = $[x]\_P$, that is, the equivalence classes induced by reduced attribute set $mathrm\{RED\}$ is the same as the equivalence class structure induced by full attribute set $P$.
• Attribute set $mathrm\{RED\}$ is minimal in the sense that $[x]\_\{(mathrm\{RED\}-\{a\})\}\; neq\; [x]\_P$ for any attribute $a\; in\; mathrm\{RED\}$. In other words, no attribute can be removed from set $mathrm\{RED\}$ without changing the equivalence classes $[x]\_P$.

A reduct can be thought of as a sufficient set of features; sufficient, that is, to represent the category structure. In the example table above, attribute set $\{P\_3,P\_4,P\_5\}$ is a reduct. The information system projected on just these attributes possesses the same equivalence class structure as that expressed by the full attribute set:

$$

begin{cases} {O_{1},O_{2}} {O_{3},O_{7},O_{10}} {O_{4}} {O_{5}} {O_{6}} {O_{8}} {O_{9}} end{cases}

Attribute set $\{P\_3,P\_4,P\_5\}$ is a legitimate reduct because eliminating any of these attributes causes a collapse of the equivalence class structure, with the result that $[x]\_\{mathrm\{RED\}\}\; neq\; [x]\_P$.

The reduct of an information system is not unique. There may be many subsets of attributes which preserve the equivalence class structure (i.e., the knowledge) expressed in the information system. In the example information system above, another reduct is $\{P\_1,P\_2,P\_5\}$, producing the same equivalence class structure as $[x]\_P$.

The set of attributes which is common to all reducts is called the core. The core is the set of attributes which is possessed by every legitimate reduct, and therefore consists of attributes which cannot be removed from the information system without causing collapse of the equivalence class structure. The core may be thought of as the set of necessary attributes; necessary, that is, for the category structure to be represented. In the example, the only such attribute is $\{P\_5\}$. Any one of the other attributes can be removed in isolation without damaging the equivalence class structure, and hence these are all dispensable. However, removing $\{P\_5\}$ in isolation does change the equivalence class structure, and thus $\{P\_5\}$ is the indispensable of this information system, and hence the core.

It is possible for the core to be empty, which means that there is no indispensable attribute. Any single attribute in the information system can be deleted without altering the equivalence class structure. In such cases, there is no essential or necessary attribute which is required for the class structure to be represented.

Attribute dependency

One of the most important aspects of database analysis or data acquisition is the discovery of attribute dependencies. That is, we wish to discover which variables are strongly related to which other variables. Generally, it is these strong relationships that will warrant further investigation, and that will ultimately be of use in predictive modeling.

In rough set theory, the notion of dependency is defined very simply. Let us take two (disjoint) sets of attributes, set $P$ and set $Q$, and inquire what degree of dependency obtains between them. Each attribute set induces an (indiscernibility) equivalence class structure, the equivalence classes induced by $P$ given by $[x]\_P$, and the equivalence classes induced by $Q$ given by $[x]\_Q$.

Let $[x]\_Q\; =\; \{Q\_1,\; Q\_2,\; Q\_3,\; dots,\; Q\_N\; \}$, where $Q\_i$ is a given equivalence class from the equivalence class structure induced by attribute set $Q$. Then, the dependency of attribute set $Q$ on attribute set $P$, $gamma\_\{P\}(Q)$, is given by

$$

gamma_{P}(Q) = frac{left | sum_{i=1}^N {underline P}Q_i right {left | mathbb{U} right leq 1

That is, for each equivalence class $Q\_i$ in $[x]\_Q$, we add up the size of its lower approximation by the attributes in $P$, i.e., $\{underline\; P\}Q\_i$. This approximation (as above, for arbitrary set $X$) is the number of objects which on attribute set $P$ can be positively identified as belonging to target set $Q\_i$. Added across all equivalence classes in $[x]\_Q$, the numerator above represents the total number of objects which – based on attribute set $P$ – can be positively categorized according to the classification induced by attributes $Q$. The dependency ratio therefore expresses the proportion (within the entire universe) of such classifiable objects. The dependency $gamma\_\{P\}(Q)$ "can be interpreted as a proportion of such objects in the information system for which it suffices to know the values of attributes in $P$ to determine the values of attributes in $Q$" (Ziarko & Shan 1995).

Another intuitive way to consider dependency is to take the partition induced by Q as the target class C, and consider P as the attribute set we wish to use in order to "re-construct" the target class C. If P can completely reconstruct C, then Q depends totally on P. If P results in a poor and perhaps a random reconstruction of C, then Q does not depend on P at all.

Thus, this measure of dependency expresses the degree of functional (i.e., deterministic) dependency of attribute set $Q$ on attribute set $P$. It is not symmetric. The relationship of this notion of attribute dependency to more traditional information-theoretic (i.e., entropic) notions of attribute dependence has been discussed in a number of sources (e.g., Pawlak, Wong, & Ziarko 1988; Yao & Yao 2002; Wong, Ziarko, & Ye 1986).

Rule extraction

The category representations discussed above are all extensional in nature. That is, a category or complex class is simply the sum of all its members. To represent a category is then just to be able to list or identify all the objects belonging to that category. However, extensional category representation have very limited practical use, because they provide no insight for deciding whether novel (never-before-seen) objects are members of the category. What is generally desired is an intentional description of the category, a representation of the category based on a set of rules that describe the scope of the category. The choice of such rules is not unique, and therein lies the issue of inductive bias. See Version space and Model selection for more about this issue.

Logical representation of decision tables

Here we present a simple rule extraction procedure based on Ziarko & Shan (1995). More advanced rough-set rule-learning systems can be found in the literature on rough association rule learning. First, let us reintroduce the sample information system from earlier:

We can first note that we can translate this knowledge system from tabular form to logical form by simply expressing the set of objects as the following disjunction, which corresponds to the disjunctive normal form (DNF) of propositional logic.

$$

begin{cases} left [(P_{1}=1) and (P_{2}=2) and (P_{3}=0) and (P_{4}=1) and (P_{5}=1) right] or dots left [(P_{1}=1) and (P_{2}=2) and (P_{3}=0) and (P_{4}=1) and (P_{5}=1) right] or dots left [(P_{1}=2) and (P_{2}=0) and (P_{3}=0) and (P_{4}=1) and (P_{5}=0) right] or dots left [(P_{1}=0) and (P_{2}=0) and (P_{3}=1) and (P_{4}=2) and (P_{5}=1) right] or dots left [(P_{1}=2) and (P_{2}=1) and (P_{3}=0) and (P_{4}=2) and (P_{5}=1) right] or dots left [(P_{1}=0) and (P_{2}=0) and (P_{3}=1) and (P_{4}=2) and (P_{5}=2) right] or dots left [(P_{1}=2) and (P_{2}=0) and (P_{3}=0) and (P_{4}=1) and (P_{5}=0) right] or dots left [(P_{1}=0) and (P_{2}=1) and (P_{3}=2) and (P_{4}=2) and (P_{5}=1) right] or dots left [(P_{1}=2) and (P_{2}=1) and (P_{3}=0) and (P_{4}=2) and (P_{5}=2) right] or dots left [(P_{1}=2) and (P_{2}=0) and (P_{3}=0) and (P_{4}=1) and (P_{5}=0) right] or dots end{cases}

which we can write much more compactly by using notation $P\_i^j$ for $(P\_i\; =\; j)$, and by representing conjunction implicitly (as algebraic product). For the sample knowledge system we then get the logical formula

$$

begin{align} (P_1^1 P_2^2 P_3^0 P_4^1 P_5^1) & or (P_1^1 P_2^2 P_3^0 P_4^1 P_5^1) or (P_1^2 P_2^0 P_3^0 P_4^1 P_5^0) or (P_1^0 P_2^0 P_3^1 P_4^2 P_5^1) or dots (P_1^2 P_2^1 P_3^0 P_4^2 P_5^1) & or (P_1^0 P_2^0 P_3^1 P_4^2 P_5^2) or (P_1^2 P_2^0 P_3^0 P_4^1 P_5^0) or (P_1^0 P_2^1 P_3^2 P_4^2 P_5^1) or dots (P_1^2 P_2^1 P_3^0 P_4^2 P_5^2) & or (P_1^2 P_2^0 P_3^0 P_4^1 P_5^0) end{align}

which (using the closed world assumption) basically states that on sampling objects from this universe, we must on each occasion select one of the specified ten objects; that is, the value of the disjunction above for this knowledge system is necessarily 1, or logical true.

Extracting rules

Now, we wish to find the minimal set of consistent rules (logical implications) that characterize the system (i.e., which can be expanded into the DNF form). For a set of condition attributes $mathcal\{P\}\; =\; \{P\_1,\; P\_2,\; P\_3,\; dots\; ,\; P\_n\}$ and a decision attribute $Q,\; Q\; notin\; mathcal\{P\}$, these rules should have the form $P\_i^a\; P\_j^b\; dots\; P\_k^c\; to\; Q^d$, or, spelled out,

$(P\_i=a)\; and\; (P\_j=b)\; and\; dots\; and\; (P\_k=c)\; to\; (Q=d)$

where $\{a,\; b,\; c,\; dots\}$ are legitimate values from the domains of their respective attributes. This is a form typical of association rules, and the number of items in $mathbb\{U\}$ which match the condition/antecedent is called the support for the rule. The method for extracting such rules given in is to form a decision matrix corresponding to each individual value $d$ of decision attribute $Q$. Informally, the decision matrix for value $d$ of decision attribute $Q$ lists all attribute-value pairs that differ between objects having $Q\; =\; d$ and $Q\; ne\; d$. This is best explained by example (which also avoids a lot of notation). Consider the table above, and let $P\_\{4\}$ be the decision variable (i.e., the variable on the right side of the implications) and let $\{P\_1,P\_2,P\_3\}$ be the condition variables (on the left side of the implication). We note that the decision variable $P\_\{4\}$ takes on two different values, namely $\{1,\; 2\}$. We treat each case separately.

The decision matrix

First we look at the case $P\_\{4\}=1$, and we divide up $mathbb\{U\}$ into objects that have $P\_\{4\}=1$ and those that have $P\_\{4\}\; ne\; 1$. [Note that objects with $P\_\{4\}\; ne\; 1$ in this case are simply the objects which have $P\_\{4\}=2$, but in general $P\_\{4\}\; ne\; 1$ would include all objects having any value for $P\_\{4\}$other than$P\_\{4\}=1$, and there may be several such classes of objects (for example, those having $P\_\{4\}=2,3,4,etc.$).] In this case, the objects having $P\_\{4\}=1$ are $\{O\_1,O\_2,O\_3,O\_7,O\_\{10\}\}$ while the objects which have $P\_\{4\}\; ne\; 1$ are $\{O\_4,O\_5,O\_6,O\_8,O\_9\}$. The decision matrix for $P\_\{4\}=1$ lists all the differences between the objects having $P\_\{4\}=1$ and those having $P\_\{4\}\; ne\; 1$; that is, the decision matrix lists all the differences between $\{O\_1,O\_2,O\_3,O\_7,O\_\{10\}\}$ and $\{O\_4,O\_5,O\_6,O\_8,O\_9\}$. We put the "positive" objects ($P\_\{4\}=1$) as the rows, and the negative objects $P\_\{4\}\; ne\; 1$ as the columns.

Sample Information System

Object	$P\_\{1\}$	$P\_\{2\}$	$P\_\{3\}$	$P\_\{4\}$	$P\_\{5\}$
$O\_\{1\}$	1	2	0	1	1
$O\_\{2\}$	1	2	0	1	1
$O\_\{3\}$	2	0	0	1	0
$O\_\{4\}$	0	0	1	2	1
$O\_\{5\}$	2	1	0	2	1
$O\_\{6\}$	0	0	1	2	2
$O\_\{7\}$	2	0	0	1	0
$O\_\{8\}$	0	1	2	2	1
$O\_\{9\}$	2	1	0	2	2
$O\_\{10\}$	2	0	0	1	0

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:

$$

begin{cases} (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) (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) (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) (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) (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) end{cases}

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:

1. Either $P\_1$ must have value 2, or $P\_3$ must have value 0, or both.
2. $P\_2$ must have value 0.
3. Either $P\_1$ must have value 2, or $P\_3$ must have value 0, or both.
4. 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.
5. $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)\; to\; (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)\; to\; (P\_\{4\}=1)$

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

$$

begin{cases} (P_1=1) to (P_{4}=1) (P_2=2) to (P_{4}=1) (P_1=2) and (P_2=0) to (P_{4}=1) (P_3=0) and (P_2=0) to (P_{4}=1) end{cases}

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.

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.

See 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

* * * * * * * * * * * * * * *

External links

• The International Rough Set Society
• Rough set tutorial
• Example-based simple tutorial

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)
This article is licensed under the GNU Free Documentation License.
Last updated on Tuesday October 07, 2008 at 11:20:38 PDT (GMT -0700)
View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Related Articles

Decision table for $P\_\{4\}=1$

Object	$O\_\{4\}$	$O\_\{5\}$	$O\_\{6\}$	$O\_\{8\}$	$O\_\{9\}$
$O\_\{1\}$	$P\_1^1,P\_2^2,P\_3^0$	$P\_1^1,P\_2^2$	$P\_1^1,P\_2^2,P\_3^0$	$P\_1^1,P\_2^2,P\_3^0$	$P\_1^1,P\_2^2$
$O\_\{2\}$	$P\_1^1,P\_2^2,P\_3^0$	$P\_1^1,P\_2^2$	$P\_1^1,P\_2^2,P\_3^0$	$P\_1^1,P\_2^2,P\_3^0$	$P\_1^1,P\_2^2$
$O\_\{3\}$	$P\_1^2,P\_3^0$	$P\_2^0$	$P\_1^2,P\_3^0$	$P\_1^2,P\_2^0,P\_3^0$	$P\_2^0$
$O\_\{7\}$	$P\_1^2,P\_3^0$	$P\_2^0$	$P\_1^2,P\_3^0$	$P\_1^2,P\_2^0,P\_3^0$	$P\_2^0$
$O\_\{10\}$	$P\_1^2,P\_3^0$	$P\_2^0$	$P\_1^2,P\_3^0$	$P\_1^2,P\_2^0,P\_3^0$	$P\_2^0$

WIPO ASSIGNS PATENT TO NEC FOR "FAULT ANALYSIS RULE EXTRACTION DEVICE, FAULT ANALYSIS RULE EXTRACTION METHOD, AND STORAGE MEDIUM" (JAPANESE INVENTOR) Sep 19, 2011; GENEVA, Sept. 19 -- Publication No. WO/2011/111599 was published on Sept. 15. Title of the invention: "FAULT ANALYSIS RULE... Read more with a free trial on HighBeam.com »

US Patent Issued to Hitachi on July 12 for "Association Rule Extraction Method and System" (Japanese Inventors) Jul 14, 2011; ALEXANDRIA, Va., July 14 -- United States Patent no. 7,979,473, issued on July 12, was assigned to Hitachi Ltd. (Tokyo).... Read more with a free trial on HighBeam.com »

Reports outline information technology study results from Auckland University of Technology. May 05, 2009; "This paper presents a constructive method for association rule extraction, where the knowledge of data is encoded into an SVM... Read more with a free trial on HighBeam.com »

A Data Mining Approach Using Incremental Rough Set Based Rule Induction Jan 01, 2008; Abstract The incremental technique is a way to solve the issue of new added-in data without re-implementing the legacy algorithm... Read more with a free trial on HighBeam.com »

Knowledge mining from trained neural networks Jul 01, 2002; ABSTRACT Despite their diverse applications in many domains, neural networks are difficult to interpret owning the lack of... Read more with a free trial on HighBeam.com »

HighBeam Research, Inc. © Copyright 2009.