Information system framework

Let ${\displaystyle I=(\mathbb {U} ,\mathbb {A} )}$ be an information system (attribute–value system), where ${\displaystyle \mathbb {U} }$ is a non-empty, finite set of objects (the universe) and ${\displaystyle \mathbb {A} }$ is a non-empty, finite set of attributes such that ${\displaystyle I:\mathbb {U} \rightarrow V_{a}}$ for every ${\displaystyle a\in \mathbb {A} }$. ${\displaystyle V_{a}}$ is the set of values that attribute ${\displaystyle a}$ may take. The information table assigns a value ${\displaystyle a(x)}$ from ${\displaystyle V_{a}}$ to each attribute ${\displaystyle a}$ and object ${\displaystyle x}$ in the universe ${\displaystyle \mathbb {U} }$.

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

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

The relation ${\displaystyle \mathrm {IND} (P)}$ is called a ${\displaystyle P}$-indiscernibility relation. The partition of ${\displaystyle \mathbb {U} }$ is a family of all equivalence classes of ${\displaystyle \mathrm {IND} (P)}$ and is denoted by ${\displaystyle \mathbb {U} /\mathrm {IND} (P)}$ (or ${\displaystyle \mathbb {U} /P}$).

If ${\displaystyle (x,y)\in \mathrm {IND} (P)}$, then ${\displaystyle x}$ and ${\displaystyle y}$ are indiscernible (or indistinguishable) by attributes from ${\displaystyle P}$ .

The equivalence classes of the ${\displaystyle P}$-indiscernibility relation are denoted ${\displaystyle [x]_{P}}$.

Example: equivalence-class structure

For example, consider the following information table:

Sample Information System

Object	${\displaystyle P_{1}}$	${\displaystyle P_{2}}$	${\displaystyle P_{3}}$	${\displaystyle P_{4}}$	${\displaystyle P_{5}}$
${\displaystyle O_{1}}$	1	2	0	1	1
${\displaystyle O_{2}}$	1	2	0	1	1
${\displaystyle O_{3}}$	2	0	0	1	0
${\displaystyle O_{4}}$	0	0	1	2	1
${\displaystyle O_{5}}$	2	1	0	2	1
${\displaystyle O_{6}}$	0	0	1	2	2
${\displaystyle O_{7}}$	2	0	0	1	0
${\displaystyle O_{8}}$	0	1	2	2	1
${\displaystyle O_{9}}$	2	1	0	2	2
${\displaystyle O_{10}}$	2	0	0	1	0

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

${\displaystyle {\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, ${\displaystyle \{O_{1},O_{2}\}}$, cannot be distinguished from each other based on the available attributes, and the three objects within the second equivalence class, ${\displaystyle \{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.

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

${\displaystyle {\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 a rough set

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

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

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

${\displaystyle {\underline {P}}X=\{x\mid [x]_{P}\subseteq X\}}$

${\displaystyle {\overline {P}}X=\{x\mid [x]_{P}\cap X\neq \emptyset \}}$

Definability

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

• Set ${\displaystyle X}$ is internally undefinable if ${\displaystyle {\underline {P}}X=\emptyset }$ and ${\displaystyle {\overline {P}}X\neq \mathbb {U} }$. This means that on attribute set ${\displaystyle P}$, there are no objects which we can be certain belong to target set ${\displaystyle X}$, but there are objects which we can definitively exclude from set ${\displaystyle X}$.
• Set ${\displaystyle X}$ is externally undefinable if ${\displaystyle {\underline {P}}X\neq \emptyset }$ and ${\displaystyle {\overline {P}}X=\mathbb {U} }$. This means that on attribute set ${\displaystyle P}$, there are objects which we can be certain belong to target set ${\displaystyle X}$, but there are no objects which we can definitively exclude from set ${\displaystyle X}$.
• Set ${\displaystyle X}$ is totally undefinable if ${\displaystyle {\underline {P}}X=\emptyset }$ and ${\displaystyle {\overline {P}}X=\mathbb {U} }$. This means that on attribute set ${\displaystyle P}$, there are no objects which we can be certain belong to target set ${\displaystyle X}$, and there are no objects which we can definitively exclude from set ${\displaystyle X}$. Thus, on attribute set ${\displaystyle P}$, we cannot decide whether any object is, or is not, a member of ${\displaystyle 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 can, by itself, fully characterize the knowledge in the database; such an attribute set is called a reduct.

Formally, a reduct is a subset of attributes ${\displaystyle \mathrm {RED} \subseteq P}$ such that

• ${\displaystyle [x]_{\mathrm {RED} }}$ = ${\displaystyle [x]_{P}}$, that is, the equivalence classes induced by the reduced attribute set ${\displaystyle \mathrm {RED} }$ are the same as the equivalence class structure induced by the full attribute set ${\displaystyle P}$.
• the attribute set ${\displaystyle \mathrm {RED} }$ is minimal, in the sense that ${\displaystyle [x]_{(\mathrm {RED} -\{a\})}\neq [x]_{P}}$ for any attribute ${\displaystyle a\in \mathrm {RED} }$; in other words, no attribute can be removed from set ${\displaystyle \mathrm {RED} }$ without changing the equivalence classes ${\displaystyle [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 ${\displaystyle \{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:

${\displaystyle {\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 ${\displaystyle \{P_{3},P_{4},P_{5}\}}$ is a reduct because eliminating any of these attributes causes a collapse of the equivalence-class structure, with the result that ${\displaystyle [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 ${\displaystyle \{P_{1},P_{2},P_{5}\}}$, producing the same equivalence-class structure as ${\displaystyle [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 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 ${\displaystyle \{P_{5}\}}$; any one of the other attributes can be removed singly without damaging the equivalence-class structure, and hence these are all dispensable. However, removing ${\displaystyle \{P_{5}\}}$ by itself does change the equivalence-class structure, and thus ${\displaystyle \{P_{5}\}}$ is the indispensable attribute 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 such an 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 ${\displaystyle P}$ and set ${\displaystyle Q}$, and inquire what degree of dependency obtains between them. Each attribute set induces an (indiscernibility) equivalence class structure, the equivalence classes induced by ${\displaystyle P}$ given by ${\displaystyle [x]_{P}}$, and the equivalence classes induced by ${\displaystyle Q}$ given by ${\displaystyle [x]_{Q}}$.

Let ${\displaystyle [x]_{Q}=\{Q_{1},Q_{2},Q_{3},\dots ,Q_{N}\}}$, where ${\displaystyle Q_{i}}$ is a given equivalence class from the equivalence-class structure induced by attribute set ${\displaystyle Q}$. Then, the dependency of attribute set ${\displaystyle Q}$ on attribute set ${\displaystyle P}$, ${\displaystyle \gamma _{P}(Q)}$, is given by

${\displaystyle \gamma _{P}(Q)={\frac {\sum _{i=1}^{N}\left|{\underline {P}}Q_{i}\right|}{\left|\mathbb {U} \right|}}\leq 1}$

That is, for each equivalence class ${\displaystyle Q_{i}}$ in ${\displaystyle [x]_{Q}}$, we add up the size of its lower approximation by the attributes in ${\displaystyle P}$, i.e., ${\displaystyle {\underline {P}}Q_{i}}$. This approximation (as above, for arbitrary set ${\displaystyle X}$) is the number of objects which on attribute set ${\displaystyle P}$ can be positively identified as belonging to target set ${\displaystyle Q_{i}}$. Added across all equivalence classes in ${\displaystyle [x]_{Q}}$, the numerator above represents the total number of objects which – based on attribute set ${\displaystyle P}$ – can be positively categorized according to the classification induced by attributes ${\displaystyle Q}$. The dependency ratio therefore expresses the proportion (within the entire universe) of such classifiable objects. The dependency ${\displaystyle \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 ${\displaystyle P}$ to determine the values of attributes in ${\displaystyle Q}$".

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

Thus, this measure of dependency expresses the degree of functional (i.e., deterministic) dependency of attribute set ${\displaystyle Q}$ on attribute set ${\displaystyle 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, Quafafou & Boussouf 2000).

Decision matrices

Let us say that we wish to find the minimal set of consistent rules (logical implications) that characterize our sample system. For a set of condition attributes ${\displaystyle {\mathcal {P}}=\{P_{1},P_{2},P_{3},\dots ,P_{n}\}}$ and a decision attribute ${\displaystyle Q,Q\notin {\mathcal {P}}}$, these rules should have the form ${\displaystyle P_{i}^{a}P_{j}^{b}\dots P_{k}^{c}\to Q^{d}}$, or, spelled out,

${\displaystyle (P_{i}=a)\land (P_{j}=b)\land \dots \land (P_{k}=c)\to (Q=d)}$

where ${\displaystyle \{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 ${\displaystyle \mathbb {U} }$ which match the condition/antecedent is called the support for the rule. The method for extracting such rules given in Ziarko & Shan (1995) is to form a decision matrix corresponding to each individual value ${\displaystyle d}$ of decision attribute ${\displaystyle Q}$. Informally, the decision matrix for value ${\displaystyle d}$ of decision attribute ${\displaystyle Q}$ lists all attribute–value pairs that differ between objects having ${\displaystyle Q=d}$ and ${\displaystyle Q\neq d}$.

This is best explained by example (which also avoids a lot of notation). Consider the table above, and let ${\displaystyle P_{4}}$ be the decision variable (i.e., the variable on the right side of the implications) and let ${\displaystyle \{P_{1},P_{2},P_{3}\}}$ be the condition variables (on the left side of the implication). We note that the decision variable ${\displaystyle P_{4}}$ takes on two different values, namely ${\displaystyle \{1,2\}}$. We treat each case separately.

First, we look at the case ${\displaystyle P_{4}=1}$, and we divide up ${\displaystyle \mathbb {U} }$ into objects that have ${\displaystyle P_{4}=1}$ and those that have ${\displaystyle P_{4}\neq 1}$. (Note that objects with ${\displaystyle P_{4}\neq 1}$ in this case are simply the objects that have ${\displaystyle P_{4}=2}$, but in general, ${\displaystyle P_{4}\neq 1}$ would include all objects having any value for ${\displaystyle P_{4}}$ other than ${\displaystyle P_{4}=1}$, and there may be several such classes of objects (for example, those having ${\displaystyle P_{4}=2,3,4,etc.}$).) In this case, the objects having ${\displaystyle P_{4}=1}$ are ${\displaystyle \{O_{1},O_{2},O_{3},O_{7},O_{10}\}}$ while the objects which have ${\displaystyle P_{4}\neq 1}$ are ${\displaystyle \{O_{4},O_{5},O_{6},O_{8},O_{9}\}}$. The decision matrix for ${\displaystyle P_{4}=1}$ lists all the differences between the objects having ${\displaystyle P_{4}=1}$ and those having ${\displaystyle P_{4}\neq 1}$; that is, the decision matrix lists all the differences between ${\displaystyle \{O_{1},O_{2},O_{3},O_{7},O_{10}\}}$ and ${\displaystyle \{O_{4},O_{5},O_{6},O_{8},O_{9}\}}$. We put the "positive" objects (${\displaystyle P_{4}=1}$) as the rows, and the "negative" objects ${\displaystyle P_{4}\neq 1}$ as the columns.

Decision matrix for ${\displaystyle P_{4}=1}$

Object	${\displaystyle O_{4}}$	${\displaystyle O_{5}}$	${\displaystyle O_{6}}$	${\displaystyle O_{8}}$	${\displaystyle O_{9}}$
${\displaystyle O_{1}}$	${\displaystyle P_{1}^{1},P_{2}^{2},P_{3}^{0}}$	${\displaystyle P_{1}^{1},P_{2}^{2}}$	${\displaystyle P_{1}^{1},P_{2}^{2},P_{3}^{0}}$	${\displaystyle P_{1}^{1},P_{2}^{2},P_{3}^{0}}$	${\displaystyle P_{1}^{1},P_{2}^{2}}$
${\displaystyle O_{2}}$	${\displaystyle P_{1}^{1},P_{2}^{2},P_{3}^{0}}$	${\displaystyle P_{1}^{1},P_{2}^{2}}$	${\displaystyle P_{1}^{1},P_{2}^{2},P_{3}^{0}}$	${\displaystyle P_{1}^{1},P_{2}^{2},P_{3}^{0}}$	${\displaystyle P_{1}^{1},P_{2}^{2}}$
${\displaystyle O_{3}}$	${\displaystyle P_{1}^{2},P_{3}^{0}}$	${\displaystyle P_{2}^{0}}$	${\displaystyle P_{1}^{2},P_{3}^{0}}$	${\displaystyle P_{1}^{2},P_{2}^{0},P_{3}^{0}}$	${\displaystyle P_{2}^{0}}$
${\displaystyle O_{7}}$	${\displaystyle P_{1}^{2},P_{3}^{0}}$	${\displaystyle P_{2}^{0}}$	${\displaystyle P_{1}^{2},P_{3}^{0}}$	${\displaystyle P_{1}^{2},P_{2}^{0},P_{3}^{0}}$	${\displaystyle P_{2}^{0}}$
${\displaystyle O_{10}}$	${\displaystyle P_{1}^{2},P_{3}^{0}}$	${\displaystyle P_{2}^{0}}$	${\displaystyle P_{1}^{2},P_{3}^{0}}$	${\displaystyle P_{1}^{2},P_{2}^{0},P_{3}^{0}}$	${\displaystyle P_{2}^{0}}$

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

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:

${\displaystyle {\begin{cases}(P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2})\land (P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2})\\(P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2})\land (P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2})\\(P_{1}^{2}\lor P_{3}^{0})\land (P_{2}^{0})\land (P_{1}^{2}\lor P_{3}^{0})\land (P_{1}^{2}\lor P_{2}^{0}\lor P_{3}^{0})\land (P_{2}^{0})\\(P_{1}^{2}\lor P_{3}^{0})\land (P_{2}^{0})\land (P_{1}^{2}\lor P_{3}^{0})\land (P_{1}^{2}\lor P_{2}^{0}\lor P_{3}^{0})\land (P_{2}^{0})\\(P_{1}^{2}\lor P_{3}^{0})\land (P_{2}^{0})\land (P_{1}^{2}\lor P_{3}^{0})\land (P_{1}^{2}\lor P_{2}^{0}\lor P_{3}^{0})\land (P_{2}^{0})\end{cases}}}$

Each statement here is essentially a highly specific (probably too specific) rule governing the membership in class ${\displaystyle P_{4}=1}$ of the corresponding object. For example, the last statement, corresponding to object ${\displaystyle O_{10}}$, states that all the following must be satisfied:

1. Either ${\displaystyle P_{1}}$ must have value 2, or ${\displaystyle P_{3}}$ must have value 0, or both.
2. ${\displaystyle P_{2}}$ must have value 0.
3. Either ${\displaystyle P_{1}}$ must have value 2, or ${\displaystyle P_{3}}$ must have value 0, or both.
4. Either ${\displaystyle P_{1}}$ must have value 2, or ${\displaystyle P_{2}}$ must have value 0, or ${\displaystyle P_{3}}$ must have value 0, or any combination thereof.
5. ${\displaystyle 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 ${\displaystyle (P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2})\land (P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2})}$ corresponding to objects ${\displaystyle \{O_{1},O_{2}\}}$ simplifies to ${\displaystyle P_{1}^{1}\lor P_{2}^{2}}$, which yields the implication

${\displaystyle (P_{1}=1)\lor (P_{2}=2)\to (P_{4}=1)}$

Likewise, the statement ${\displaystyle (P_{1}^{2}\lor P_{3}^{0})\land (P_{2}^{0})\land (P_{1}^{2}\lor P_{3}^{0})\land (P_{1}^{2}\lor P_{2}^{0}\lor P_{3}^{0})\land (P_{2}^{0})}$ corresponding to objects ${\displaystyle \{O_{3},O_{7},O_{10}\}}$ simplifies to ${\displaystyle P_{1}^{2}P_{2}^{0}\lor P_{3}^{0}P_{2}^{0}}$. This gives us the implication

${\displaystyle (P_{1}=2\land P_{2}=0)\lor (P_{3}=0\land P_{2}=0)\to (P_{4}=1)}$

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

${\displaystyle {\begin{cases}(P_{1}=1)\to (P_{4}=1)\\(P_{2}=2)\to (P_{4}=1)\\(P_{1}=2)\land (P_{2}=0)\to (P_{4}=1)\\(P_{3}=0)\land (P_{2}=0)\to (P_{4}=1)\end{cases}}}$

It can be noted that each of the first two rules has a support of 1 (i.e., the antecedent matches two objects), while each of the last two rules has a support of 2. 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 ${\displaystyle P_{4}=2}$, thus yielding a new set of implications for that decision value (i.e., a set of implications with ${\displaystyle P_{4}=2}$ as the consequent). In general, the procedure will be repeated for each possible value of the decision variable.

LERS rule induction system

The data system LERS (Learning from Examples based on Rough Sets) Grzymala-Busse (1997) may induce rules from inconsistent data, i.e., data with conflicting objects. Two objects are conflicting when they are characterized by the same values of all attributes, but they belong to different concepts (classes). LERS uses rough set theory to compute lower and upper approximations for concepts involved in conflicts with other concepts.

Rules induced from the lower approximation of the concept certainly describe the concept, hence such rules are called certain. On the other hand, rules induced from the upper approximation of the concept describe the concept possibly, so these rules are called possible. For rule induction LERS uses three algorithms: LEM1, LEM2, and IRIM.

The LEM2 algorithm of LERS is frequently used for rule induction and is used not only in LERS but also in other systems, e.g., in RSES (Bazan et al. (2004). LEM2 explores the search space of attribute–value pairs. Its input data set is a lower or upper approximation of a concept, so its input data set is always consistent. In general, LEM2 computes a local covering and then converts it into a rule set. We will quote a few definitions to describe the LEM2 algorithm.

The LEM2 algorithm is based on an idea of an attribute–value pair block. Let ${\displaystyle X}$ be a nonempty lower or upper approximation of a concept represented by a decision-value pair ${\displaystyle (d,w)}$. Set ${\displaystyle X}$ depends on a set ${\displaystyle T}$ of attribute–value pairs ${\displaystyle t=(a,v)}$ if and only if

${\displaystyle \emptyset \neq [T]=\bigcap _{t\in T}[t]\subseteq X.}$

Set ${\displaystyle T}$ is a minimal complex of ${\displaystyle X}$ if and only if ${\displaystyle X}$ depends on ${\displaystyle T}$ and no proper subset ${\displaystyle S}$ of ${\displaystyle T}$ exists such that ${\displaystyle X}$ depends on ${\displaystyle S}$. Let ${\displaystyle \mathbb {T} }$ be a nonempty collection of nonempty sets of attribute–value pairs. Then ${\displaystyle \mathbb {T} }$ is a local covering of ${\displaystyle X}$ if and only if the following three conditions are satisfied:

each member ${\displaystyle T}$ of ${\displaystyle \mathbb {T} }$ is a minimal complex of ${\displaystyle X}$,

${\displaystyle \bigcup _{t\in \mathbb {T} }[T]=X,}$

${\displaystyle \mathbb {T} }$ is minimal, i.e., ${\displaystyle \mathbb {T} }$ has the smallest possible number of members.

For our sample information system, LEM2 will induce the following rules:

${\displaystyle {\begin{cases}(P_{1},1)\to (P_{4},1)\\(P_{5},0)\to (P_{4},1)\\(P_{1},0)\to (P_{4},2)\\(P_{2},1)\to (P_{4},2)\end{cases}}}$

Other rule-learning methods can be found, e.g., in Pawlak (1991), Stefanowski (1998), Bazan et al. (2004), etc.

Rough membership

Rough sets can be also defined, as a generalisation, by employing a rough membership function instead of objective approximation. The rough membership function expresses a conditional probability that ${\displaystyle x}$ belongs to ${\displaystyle X}$ given ${\displaystyle \textstyle \mathbb {R} }$. This can be interpreted as a degree that ${\displaystyle x}$ belongs to ${\displaystyle X}$ in terms of information about ${\displaystyle x}$ expressed by ${\displaystyle \textstyle \mathbb {R} }$.

Rough membership primarily differs from the fuzzy membership in that the membership of union and intersection of sets cannot, in general, be computed from their constituent membership as is the case of fuzzy sets. In this, rough membership is a generalization of fuzzy membership. Furthermore, the rough membership function is grounded more in probability than the conventionally held concepts of the fuzzy membership function.

Other generalizations

Several generalizations of rough sets have been introduced, studied and applied to solving problems. Here are some of these generalizations:

• rough multisets (Grzymala-Busse, 1987)
• fuzzy rough sets extend the rough set concept through the use of fuzzy equivalence classes(Nakamura, 1988)
• Alpha rough set theory (α-RST) - a generalization of rough set theory that allows approximation using of fuzzy concepts (Quafafou, 2000)
• intuitionistic fuzzy rough sets (Cornelis, De Cock and Kerre, 2003)
• generalized rough fuzzy sets (Feng, 2010)
• rough intuitionistic fuzzy sets (Thomas and Nair, 2011)
• soft rough fuzzy sets and soft fuzzy rough sets (Meng, Zhang and Qin, 2011)
• composite rough sets (Zhang, Li and Chen, 2014)