ROUGH SET THEORY

THEORY AND PRACTICE

 ROUGH SET THEORY
OVERVIEW

INFORMATION &
DECISION SYSTEMS

INDISCERNIBILITY APPROXIMATION OF
RELATION & CLASSES &
EQUIVALENCE CLASS PROPERTIES

DISCERNIBILITY RULES GENERATION &

RELATION, FUNCTION & FRAMEWORK
REDUCTS

CLASSIFICATION DEFAULT RULES

GENERATION
FRAMEWORK
ROUGH SET THEORY

AN OVERVIEW
 ROUGH SET THEORY
 Rough-Set concept was introduced by Polish logician, Professor Zdzisław
Pawlak in early eighties.

 Recently, it is one of the most developing AI method.

 techniques for the identification and recognition of common patterns in

data, especially in the case of uncertain and incomplete data.

 The mathematical foundations of this method are based on the set

approximation of the classification space.
 ROUGH SET THEORY

 The rough set philosophy is founded on the assumption

that with every of the universe of discourse we
associate some information (data, knowledge). E.g., if
objects are patients suffering from a certain disease,
symptoms of the disease form information about
patients.
 ROUGH SET THEORY
 Objects characterized by the same information are
indiscernible (similar) in view of the available
information about them.
 The indiscernibility relation generated in this way is the
mathematical basis of rough set theory.
 Any set of all indiscernible (similar) objects is called
elementary set, and form basic granule (atom) of
knowledge about the universe.
 Any union of some elementary sets is referred to as
crisp (precise) set - otherwise a set is rough (imprecise,
vague).
ROUGH SET THEORY

Rough set

Indiscernible
objects
Crisp
data set
knowledge
Elementary
set
 ROUGH SET THEORY

 Precise concept - objects can be characterized

through information available.

 vague concept, cannot be characterized in terms

of information about their elements - replaced by
a pair of precise concepts - called the lower and
the upper approximation of the vague concept.
 ROUGH SET THEORY
 lower approximation - consists of all objects
which surely/certainly belong to the concept

 upper approximation - contains all objects which

possibly belong to the concept.

 the difference between the upper and the lower

approximation constitute the boundary region of
the vague concept.
 

CLASSIFICATION OF OBJECTS
X
BX

BX

The set of X

The B-Lower Approximation of X

 

The B-Upper Approximation of X

 
 ROUGH SET AS KNOWLEDGE BASE
 Knowledge base for Rough-Set processing is stored as a table
containing conditional and decision attributes. The table represents
given knowledge in form of IF-THEN rules.

 However, some elements of knowledge can be uncertain and

inconsistent. In such a case, decision table become inconsistent
and some rules become uncertain.

 Rough-Set reasoning is made over discrete data. Therefore, a

discretization is used for data preprocessing.
ROUGH SET AS KNOWLEDGE BASE

 Indiscernibility Relations
 Equivalence Class
 Discernibility Matrix
 Discernibility Matrix Modulo
 Discernibility Function
 Reducts
 KNOWLEDGE REPRESENTATION

 a method of knowledge representation is very

important for Rough-Set data processing.

 Data are stored in a decision table as follows:

columns represent attributes, rows represent objects
whereas every cell contains attribute value for
corresponding objects and attributes.

 Decision tables are also called information systems.

 ROUGH CLASSIFICATION METHOD

Projection of
Classes

Raw Data Training Reducer Generate Rules

Set Reducts

0121 Split
1012
---------- Rules

Preprocessing Discretization

Testing
Test
Set
 ROUGH CLASSIFICATION METHOD
 Important Features

 Upper and lower approximation

 Membership Values
 Number of Rules
 Length of Rules
 Accuracy
 Coverage
 Support
ROUGH SET THEORY
AN EXAMPLE
Knowledge Representation (IS)
Studies Education Works
1 Poor SPM Poor
2 Poor SPM Good
3 Moderate SPM Poor
4 Moderate Diploma Poor
5 Poor SPM Poor
6 Moderate Diploma Poor
7 Good MSC Good
:
99 Poor SPM Good
100Moderate Diploma Poor
Knowledge Representation (DS)
Studies Education Works Income (D)
1 Poor SPM Poor None
2 Poor SPM Good Low
3 Moderate SPM Poor Low
4 Moderate Diploma Poor Low
5 Poor SPM Poor None
6 Moderate Diploma Poor Low
7 Good MSC Good Medium
:
99 Poor SPM Good Low
100Moderate Diploma Poor Low
STEPS FOR ROUGH CLASSIFICATION
MODELING
 Indiscernibility Relations

 Equivalence Class

 Discernibility Matrix

 Discernibility Matrix Modulo

 Discernibility Function

 Reducts
 Indiscernibility Relation
The concept of indiscernibility captures the
discernibility phenomenon and allows us to
partition the universe into disjoint subsets
where each subset contains objects that are
‘equal’, or indiscernible from each other using
the selected attribute subset.

 
IND ( B)  {( x , x )  U | a  B, (a( x )  a( x ))}
A i j
2
i j
Equivalence Class
Class Studies Education Works Income num_obj

E1 Poor SPM Poor None 50

E2 Poor SPM Good Low 5

E3 Moderate SPM Poor Low 30

E4 Moderate Diploma Poor Low 10

E5,1 Good MSC Good Medium 4

E5,2 Good MSC Good High 1

 
Equivalence Class :
Numerical Representation
Class a b c dec num_obj

E1 1 2 3 1 50
E2 1 2 1 2 5
E3 2 2 3 2 30
E4 2 3 3 2 10
E5,1 3 5 1 3 4
E5,2 3 5 1 4 1
Discernibility Matrix
  E1 E2 E3 E4 E5
E1 x {c} {a} {a, b} {a, b, c}

E2 {c} x {a ,c} {a, b, c} {a, b}

E3 {a} {a, c} x {b} {a, b, c}

E4 {a, b} {a, b, c} {b} x {a, b, c}

E5 {a, b, c} {a, b} {a, b, c} {a, b, c} x
Discernibility Matrix Modulo
E1 E2 E3 E4 E5

E1 x {c} {a} {a, b} {a, b, c}

E2 {c} x x x {a, b}

E3 {a} x x x {a, b, c}

E4 {a, b} x x x {a, b, c}

E5 {a, b, c} {a, b} {a, b, c} {a, b, c} x

 Discernibility Function
  E1 E2 E3 E4 E5 f

E1 x {c} {a} {a, b} {a, b, c} {a, c}

E2 {c} x {a ,c} {a, b, c} {a, b} {a, c},{b, c}

E3 {a} {a, c} x {b} {a, b, c} {a},{b}

E4 {a, b} {a, b, c} {b} x {a, b, c} {b}

E5 {a, b, c} {a, b} {a, b, c} {a, b, c} x {a},{b}

 Discernibility Function Modulo
E1 E2 E3 E4 E5 f

E1 x {c} {a} {a, b} {a, b, c} {a, c}

E2 {c} x x x {a, b} {a, c},{b, c}

E3 {a} x x x {a, b, c} {a}

E4 {a, b} x x x {a, b, c} {a},{b}

E5 {a, b, c} {a, b} {a, b, c} {a, b, c} x {a},{b}

 Discernibility Function
Class CNF of boolean function [Link]

E1 c  a  (a  b)  (a  b  c) ac
E2 c  (a  b) c  (a  b)
E3 a  (a  b c) a
E4 (a  b)  (a  b  c) ab
E5 (a  b  c)  (a  b) ab
 
Reduct
 Reducts are minimal selection of attributes within the IS/DS that
are more important/interesting than others.

 based on the concept of discernibility relation in the classes of the

DS

 object reduct : reduct of every class in the IS/DS

 full reduct : reduct of the system; the most important atrributes in

the IS/DS
 Reduct
Class CNF of boolean function Disc. Function Reducts

E1 c  a  (a  b)  (a  b  c) ac { a, c }
E2 c  (a  b) c (a  b) {a,c},{b, c}
E3 a  (a  b c) a {a}
E4 (a  b)  (a  b  c) ab {a},{b}
E5 (a  b  c)  (a  b) ab {a},{b}

 
Reduct
Reduct of the system??
Reduct Computation Methods
Genetic Reducer
Dynamic Reducer
Johnson Reducer
Holte1R
Exhaustive
SIP/DRIP
Generation of Rules
[E1, {a, c}], Class a b c dec
[E2, {a, c},{b,c}],
[E3, {a}], E1 1 2 3 1
[E4, {a}{b}], E2 1 2 1 2
[E5, {a}{b}] E3 2 2 3 2
Reducts E4 2 3 3 2
E5,1 3 5 1 3
E5,2 3 5 1 4

Equivalence Classes
a1c3  d1
a1c1  d2,b2c1  d2
a2  d2
b3  d2
a3  d3,a3  d4
b5  d3,b5  d4
Rules
 Generation of Rules
Class Rules Membership Degree
E1 a1c3  d1 50/50 = 1
E2 a1c1  d2 5/5 = 1
E2 b2c1  d2 5/5 = 1
E3, E4 a2  d2 40/40 = 1
E4 b3  d2 10/10 = 1
E5 a3  d3 4/5 = 0.8
E5 a3  d4 1/5 = 0.2
E5 b5  d3 4/5 = 0.8
E5 b5  d4 1/5 = 0.2
 
 Rules Measurements : Support
Given a description contains a conditional part  and the decision part , denoting
a decision rule   . The support of the pattern  is a number of objects in
the information system A has the property described by .
 
 
The support of  is the number of object in the IS A that have the decision
described by . sup port ( )  
 

The support for the decision rule    is the probability of that an object covered
by the description is belongs to the class.
  sup port (  )  

sup port (   )  sup port (   )

Rules Measurement : Accuracy

The quantity accuracy (  ) gives a measure of how

trustworthy the rule is in the condition . It is the probability that
an arbitrary object covered by the description belongs to the
class. It is identical to the value of rough membership function
applied to an object x that match . Thus accuracy measures
the degree of membership of x in X using attribute B.

sup port (   )
Accuracy(   ) 
sup port ( )
 Rules Measurement : Coverage

Coverage gives measure of how well the pattern 

describes the decision class defined through . It is
a probability that an arbitrary object, belonging to the
class C is covered by the description D.

sup port (   )
Coverage(   ) 
sup port (  )
Complete, Deterministic and Correct Rules

The rules are said to be complete if any object

belonging to the class is covered by the
description coverage is 1 while deterministic
rules are rules with the accuracy is 1. The
correct rules are rules with both coverage
and accuracy is 1.
 Classification of Rules

Two folds:

to determine the performance of classification

with other test set

making decision toward new cases without

decision
 Classification

Classification
rules

Test data
Studies Education Works Income (D)
Moderate Diploma Poor Low
Poor SPM Poor None
New data
Moderate Diploma Poor Low studies=“poor” and
Good MSC Good Medium work=“poor”
:

classify

poor
 Classification of Rules (Scheme)
 When a classifier is presented with a new case, the rule set is scanned
to find applicable rules; rules that the predecessors match the case.

 If no rule is found, the most frequent outcome in the training data is

chosen.

 If more than one rules match, these may in turn indicate more than one
possible outcome.

 A voting process is the performed among the rules that match in order
to resolve conflicts and to rank the predicted outcomes.
Classification of Rules (Method)

 First Rule
 Highest Accuracy
 Simple Voting
 Quadratic Voting
 Exponential Voting
 Weight of Evidence
 Default Rules Generation
Framework
 rules that uses more default knowledge for situation when
the information is incomplete.

 simpler in structure; a few condition attributes

 better when handling unseen cases with missing values

 a preliminary conclusion can be made although not with

certain degree of certainty, a decision can be made whether
to uphold the decision or to gather more information
Default Rules Generation
Framework
START

Decision
System

Equivalence
Classes

Discernibility
Projection of Relation
Classes

Reducts
Computation

Rules Generation
(Definite/Default)

END
Default Rules Generation Framework

 default rules are generated through creating the

indeterminacy in a DS

 The underlying idea is to search for default rules by

destroying reducts of the original system

 generation of indeterminacy is done through selecting of

projections over the condition attributes allowing certain
attributes to be excluded from consideration
Default Rules Generation

Class a b c decision num_obj

E1 1 2 3 1 50

E2 1 2 1 2 5

E3 2 2 3 2 30

E4 2 3 3 2 10

E5,1 3 5 1 3 4

E5,2 3 5 1 4 1
Default Rules Generation

Projection (Cpr) Remove (Ccut) Indeterminacy Joining

{a, b, c} - E1, E2, E3, E4, E5

{b, c} a {E1, E3}, E2, E4, E5

{a, c} b no indeterminacy

{a, b} c {E1, E2, E3}, E4, E5

{c} a, b {E1, E3, E4}, {E2,E5}

{b} a, c {E1, E2, E3}

{} a, b, c {U}
Default Rules Generation Framework
{a, b, c} ac

a c a c
{b, c} E[1,3] E[1,2]
bc {a, c} {a, b} a
c a
b
b c a

E[1,3,4] E[1,2,3]
{c} c b {a} E[2,5]
{b} c
c b b

{} U=E[1,2,3,4,5]
 Definite & Default Rules
Definite Rules Membership() Default Rules Membership()

a1c3  d1 50/50 = 1 a3  d3 4/5 = 0.8

a1c1  d2 5/5 = 1 a3  d4 1/5 = 0.2
b2c1  d2 5/5 = 1 b5  d3 4/5 = 0.8
a2  d2 40/40 = 1 b5  d4 1/5 = 0.2
a1  d1 50/50 = 1 a3  d3 4/5 = 0.8
b3  d2 10/10 = 1 a3  d4 1/5 = 0.2
b2  d1 50/80 =0.625
b2  d2 30/80 =0.375
c1  d2 5/10 =0.5
c1  d3 4/10 =0.4
c1  d4 1/10 =0.1
a1  d1 50/55 =0.91
a1  d2 5/55 =0.09
 Rough Classifier

Projection of
Classes

Raw Data Training Reducer Generate Rules

Set Reducts

0121 Split
1012
---------- Rules

Preprocessing Discretization

Testing
Test
Set
Experiments

 ROugh SET Toolkit for data Analysis (ROSETTA)

 Implement the default rules generation framework introduced by (Mollestad,

1997)

 provide utilities
 data preprocessing,
 data discretization
 rule based knowledge
 statistical analysis
 embedded with C++, Prolog, MathLab programs.
 EXPERIMENTAL RESULTS ON SEVERAL ROUGH
DATA MINING SYSTEMS

AUS CLEV LYM

Method ACC NR M_L  ACC NR M_L ACC NR M_L

SIP/DRIP 98.48 118 3 82.35 111 6 88.76 71 3

GA 84.44 767 6 83.82 1014 7 87.64 947 4
Johnson 82.93 87 4 77.45 68 4 84.27 40 2
Holte1R 85.52 56 1 80.88 43 1 86.51 57 1
Dynamic 85.09 2305 7 84.31 106140 9 86.51 4195 7
Exhaustive 84.88 786 7 82.84 1106 7 86.51 1749 6
 EXPERIMENTAL RESULTS ON SEVERAL ROUGH
DATA MINING SYSTEMS

BCO GERM
Method ACC NR M_L  ACC NR M_L

SIP/DRIP 95.10 34 2 75.417 52 4

GA 95.10 297 4 74.250 4511 6
Johnson 94.49 28 2 74.250 69 4
Holte1R 84.69 81 1 71.750 48 1
Dynamic 90.61 444 4 - -
Exhaustive 95.10 297 4 - -
THANK YOU
 Set Approximation of Classification
 The primary notions : approximation space and lower
and upper approximations of a set.

 classification of the domain of interest into disjoint

categories.

 formally represents knowledge about the domain: an

ability to characterize all classes of the classification,
for example, in terms of features of objects belonging to
the domain.
Set Approximation of Classification

 Objects belonging to the same category are not

distinguishable, which means that their
membership status with respect to an arbitrary
subset of the domain may not always be clearly
definable.

 Any subset defined through its lower and upper

approximations is called a rough set.
 Set Approximation of Classification
Lower Approximation

 The lower approximation is a description of the domain

objects which are known with certainty to belong to the subset
of interest. Given an IS A = (U,A), let X Í U be a set of
objects and B Í A be a selected set of attributes. B-lower
approximation BX
 
BX = { x  U : [x]B X }
 
 Set Approximation of Classification
Lower Approximation

 The lower approximation is the set of objects which can

certainly be classified into decision X. These objects must
have their equivalence class totally contained in the set X.
This means that in a lower approximation, all objects can be
discerned from those outside the set BX
Set Approximation of Classification
Upper Approximation
 The upper approximation is a description of the objects which possibly
belong to the subset.
 
B X  {x U : [ x]  X  0}
B

 The upper approximation of those objects that can possibly be classified

into X. These objects are indiscernible from one or more elements in X.
The upper approximation is a superset of the lower approximation and
X.
 
 Classification of objects

 
POSB(X) = BX B-positive region of X

NEGB(X) = BX B-negative region of X

BNB(X) = B X - BX B-boundary region of X

 Classification of objects
 

X
BX

BX

The set of X

The B-Lower Approximation of X

 

The B-Upper Approximation of X

 
 A Simple Example
Table 1.5 . A Decision System of 12 Objects Table 1.6. The Equivalence Class

objects a b c dec class a b c d [Link]

1 1 2 3 1 E1 1 2 3 1 3
2 1 2 1 2 E2 1 2 1 2 2
3 2 2 3 2 E3 2 2 3 2 1
4 2 3 3 2 E4 2 3 3 2 3
5 1 2 3 1 E5,1 3 5 1 3 2
6 1 2 3 1 E5,2 3 5 1 4 1
7 2 3 3 2
8 3 5 1 3
9 3 5 1 3
10 3 5 1 4
11 1 2 1 2
12 2 3 3 2

Table 1.7: Set of objects in the equivalence class Table 1.8: The set of objects mapped to
decision Xi

Class Object Decision Objects

E1 {x1, x5, x6 } X1 {x1, x5, x6 }
E2 {x2, x11 } X2 {x2, x11, x3, x4, x7, x12}
E3 {x3 } X3 {x8, x9 }
E4 {x4, x7, x12 } X4 {x10 }
E5 {x8, x9, x10 }
Lower and Upper Approximation
B X1  E1  { x1, x5 , x6 }
B X 2  E2 U E3 U E 4  { x2 , x3 , x 4 , x7 , x11, x12 }
BX3  
BX 4  

B X 1  E1  { x1, x 5 , x 6 }
B X 2  E 2 U E 3 U E 4  { x 2 , x 3 , x 4 , x 7 , x11, x12 }
B X 3  E 5  { x 8 , x 9 , x10 }
B X 4  E 5  { x 8 , x 9 , x10 }
 A Simple Example
X3 X4
X1
X2
x9
x1 x2
x5
x10
x6 x3 x4
x8
x7
x11

x12
 Accuracy Coefficient

The accuracy coefficient is used for finding the ratio of

possibly correct decisions using the knowledge we have
from class X. In many cases we have many possible
classes, we can calculate the ratio of possibly correct
decisions when classifying objects employing
knowledge F by calculating another new accuracy
coefficient
  | BX | | POS B ( X ) |
B (X )   , 0  B (X )  1
| BX | | POS B ( X ) |  | BN B ( X ) |
Accuracy of Approximation
Objects that are not perceived to any objects in the upper
approximation of F cannot be assigned to any classes.
To measure the percentage of objects that can be
correctly classified to classes of F employing the same
knowledge, we must compute a measure for the quality.
n

 | BX
i 1
i |
 B (F )  n
, 0   B (F )  1
 | BX
i 1
i |
Quality of Approximation of F

 This measure how good our classes are defined with

respect to how much information is stored in the
decision table. A problem with the upper and lower
approximation is that we do not know anything about
how strong the different objects in the boundary region
belong to it.
 
n

 | BX |
i 1
i
 B (F ) 
|U |
 Rough Membership Function
The rough membership function expresses how strongly
an element x belongs to the rough set X in view of
information about the element expressed by the set of
attributes B.
 

| X  [ x] B |
 XB ( x)  , 0   XB ( x)  1
| [ x] B |