Intelligent Information Ma nagement, 2011, 3, 131-136
doi:10.4236/iim.2011.34016 Published Online July 2011 (http://www.SciRP.org/journal/iim)
Rough Computational Approach to UAR based on
Dominance Matrix in IOIS
Xiaoyan Zhang, Weihua Xu 1
Chongqing University of Technology, Chongqing, China
Received March 28, 2011; revised June 30, 2011; accepted July 7, 2011
Abstract
Rough set theory is a new mathematical tool to deal with vagueness and uncertainty. The classical rough set
theory based on equivalence relation has made a great progress, while the equivalence relation is too harsh to
meet and is extended to dominance relation in real world. It is important to investigate rough computational
methods for rough set theory, which is one of the bottleneck problems in the development of rough set theory.
In this article, rough computational approach to upper approximation reduction (UAR) is discussed based on
dominance matrix in inconsistent ordered information systems (IOIS). The algorithm of upper approximation
reduction is obtained, from which we can provide approach to upper approximation reduction operated sim-
ply in inconsistent systems based on dominance relations. Finally, an example illustrates the validity of this
method, and shows the method is excellent to a complicated information system.
Keywords: Dominance Relation, Information System, Rough Set, Upper Approximation Reduction
1. Introduction
The rough set theory, proposed by Pawlak in the early
1980s [1], is an extension of the classical set theory for
modeling uncertainty or imprecision information. The re-
search has recently roused great interest in the theoretical
and application fronts, such as machine learning, pattern
recognition, data analysis, and so on.
Attributes reduction is one of the hot research topics of
rough set theory. Much study on this area had been re-
ported and many useful results were obtained until now
[2-7]. However, most work was based on consistent infor-
mation systems, and the main methodology has been de-
veloped under equivalence relations (indiscernibility rela-
tions). In practice, most of information systems are not
only inconsistent, but also based on dominance relations
because of various factors. The ordering of properties of
attributes plays a crucial role in those systems. For this
reason, Greco, Matarazzo, and Slowinski [8-13] proposed
an extension rough sets theory, called the dominance-based
rough sets approach (DRSA) to take into account the or-
dering properties of attributes. This innovation is mainly
based on substitution of the indiscernibility relation by a
dominance relation. In DRSA, where condition attributes
and classes are preference orde red. And many studies have
been made in DRSA [14-19]. But simpler results of knowl-
edge reductions are very poor in inconsistent ordered in-
formation sy stems until now.
In this paper, the method operated simply for upper ap-
proximation reduction is introduced in inconsistent is ob-
tained, from which we can provide new approach to know-
ledge reductions in inconsistent systems based on domi-
nance relations. Finally, an example illustrates the validity
of this method, and shows the method is excellent to a
complicat ed information system .
2. Rough Sets and OIS
The following recalls necessary concepts and prelimi-
naries required in the sequel of our work. Detailed de-
scription of the theory can be found in [4,5].
An information system with decisions is an ordered
quadruple


,,,UA DFG, where


12
,,,
n
Uxx x is a non-empty finite set of ob-
jects;
A
D is a non-empty finite attributes set;


12
,,,
p
A
aa a denotes the set of condition at-
tributes;


12
,,,
q
Ddd d denotes the set of decision attrib-
utes, and AD


;

 
|,,
kk k
F
fUVkpfx is the value of k a
on ,k
x
UV

is the domain of ,
kk
aa A;

X. Y. ZHANG ET AL. 132
 
|,,
kk k
GgUVkqgx
 
  is the value of k
d

on ,k
x
UV  is the domain of ,
kk
dd D

.
In an information system, if the domain of a attribute
is ordered according to a decreasing or increasing pref-
erence, then the attribute is a criterion.
Definition 2.1 (See [4]) An information system is
called an ordered information system (OIS) if all condi-
tion attributes are criterions.
Assumed that the domain of a criterion aA

is
complete pre-ordered by an outranking relation a
, then
a
x
y means that
x
is at least as good as y with
respect to criterion a. And we can say that
x
domi-
nates y. In the following, without any loss of generality,
we consider condition and decision criterions having a
numerical domain, that is, a
V ( d enotes the se t
of real numbers).
We define
x
y by


,,
f
xaf ya according
to increasing preference, where aA and,
x
yU

.
For a subset of attributesBA, B
x
y means that
a
x
y for any aB. That is to say
x
dominates y
with respect to all attributes in B. Furthermore, we de-
note B
x
y by B
x
Ry
. In general, we indicate a or-
dered information system s with decision by

,,,UA DFG

.
Thus the following definition can be obtained.
Let

,,,UA DFG

 be an ordered informa-
tion system with decisions, for BA, denote




,| ,
Bij liljl
RxxUUfxfxaB 





,| ,
Dij mimjm
RxxUUgxgxdD 

.
B
R and
D
R are called dominance relations of in-
formation system 
.
If we denote
[] {|(,)}
iBjj iB
x
xUxx R 

{|()(), };
jljlil
x
UfxfxaB
[] {|(,)}
iDjj iD
x
xUxx R 

{|()(), },
jmjmim
x
Ug xg xdD
then the following properties of a dominance relation are
trivial.
Proposition 2.1 (See [4]) Let A R be a dominance
relation. The following hold.
1) A R is reflexive, transitive, but not symmetric, so it
is not a equivalence relation.
2) If BA, then AB
RR

.
3) If BA, then
 
ii
AB
x
x

.
4) If

ji
A
x
x, then

ji
A
A
x
x



 and

iA
x



|
jji
A
A
xxx
 

.
5)

ji
A
A
x
x



 iff






,,
ij
f
xafxaa A .
6)



|
A
x
xU 

 constitute a covering of U.
For any subset
X
of U, and
A
of   define
 


|;
AA
RX xUxX 


 


|
AA
RX xUx X







A
RX
 and

A
Rx
are said to be the lower and up-
per approximation of
X
with respect to a dominance
relation A R. And the approximations have also some
properties which are similar to those of Pawlak approxi-
mation spaces.
Definition 2.2 (See [4]) For a ordered information
system with decisions

,,,UA DFG

, if
AD
RR

, then this information system is consistent,
otherwise, this information system is inconsistent.
For simple description, the following information sys-
tems with decisions are based on dominance relations, i.e.
ordered information systems.
Let


,,,UA DFG

 be an inconsistent or-
dered information system, and denote



,1,2,,
kD
DUR kr

12
((),(),,())
BB BBr
RDRD RD  
 
the following definition is gave.
Definition 2.3 (See [5]) If
B
A

 , for all BA, we
say that B is an upper approximation consistent set of

. If B is an upper approx imation consistent set, and
no proper subset of B is upper approximation consis-
tent set, then B is called an upper approximation con-
sistent reduction of  .
From the above, we can find that an upper approxima-
tion consistent set preserves the upper approximation of
every decision class.
Theorem 2.1 (See [5]) Let  =

,,,UA DFG be
an information system, BA, then B is an upper
approximation consistent set if and only if there exist
bB

such that


bb
f
xfy when

Ak
x
RD

and

Ak
yRD for every
kD
DUR

1, 2,,kr.
From the theorem, authors have provided approach to
upper approximation reduction in inconsistent ordered
systems based on indiscernable matrixes in [5]. We can
find that it is not convenient to use the method by com-
puters. So we will propose the approach to upper ap-
proximation reduction operated simply by computers.

X. Y. ZHANG ET AL. 133
3. Rough Computational Approach to UAR
Based on Dominance Matrix
3.1. Dominance Matrices and Upper
Approximation Decision Matrices
In this section, the dominance matrices and upper ap-
proximation decision matrices are proposed, and some
properties are obtained.
Definition 3.1 Let


,,,UA DFG

be an or-
dered information system, and denote

,
Bij
nn
Mm


where

1, ,
0, otherwise.
ji
B
ij xx
m





The matrix
B
M
is called dominance matrix of attrib-
utes setBA. If ||Bl, we say that the order of
B
M
is l.
Definition 3.2 Let


,,,UA DFG

be an or-
dered information system, and dominance matrices
B
M
,
C
M
of attributes sets ,BCA. The intersection of
B
M
and C
M
is defined by

 BC ijij
nn nn
MM mm



 


min ,.
ij ij nn
mm



The following properties are obviously.
Proposition 3.1 Let
B
M
, C
M
be dominance matri-
ces of attributes sets ,BCA, the following results
always hold.
1) 1
ii
m.
2) If
B
M
, C
M
, then
B
CBC
M
MM
.
Definition 3.3 Let

,,,UA DFG

 be an or-
dered information system, and denote

,
Dij
nn
Mr


where
 

00
0
0, and hold
at same time for some1,2,,.
1, otherwise.
iAkjAk
ij
xRD xRD
rkr











The matrix
D
M
is called upper approximation deci-
sion matrix of  .
From the above, we can see that the dominance rela-
tion of objects is decided by dominance matrices, and
different decisions of objects is decided by upper ap-
proximation decision matrix.
Definition 3.4 Let


12
,,,
n
aa a  and



12
,,,
n
bb bbe two n dimension vectors. If

,1,2,,
ii
abi n, we say vector

is less than
vector

, denoted by

 .
Definition 3.5 Let

12
,,, T
An
M    and
B
M


12
,,, ,
T
n
  be two matrices, i

and i

be row vectors respectively. If ii

 , we say A
M
is
less than
B
M
, denoted by AB
M
M.
By the definitions, dominance matrices have the fol-
lowing properties straightly.
Proposition 3.2 Let

,,,UA DFG

 be an
ordered information system, and BA. If A
M
and
B
M
are the dominance matrices, then AB
M
M.
3.2. Theories of Matrix Computation for Upper
Approximation Reduction
In the following, we will give the theory of matrix com-
putation for upper approximation reduction in ordered
information systems.
Theorem 3.1 Let  =


,,,UA DFGbe an infor-
mation system, BA, then B is an upper approxi-
mation consistent set if and only if
B
D
M
M.Proof
“” quad we need prove that if
B
A



holds for
BA then
B
D
M
M

. So we only prove1
ij
r

, when
1
ij
m

. In fact, we can have that

1
ijj i
B
mxx 

ji
B
B
x
x



One can obtain that if

0
iAk
xRD
then


0
jAk
xRD
 for


01, 2,,kr

That is to say


0
iAk
xRD
 and


0
iAk
xRD
 don not hold at same
time. Hence, we have 1
ij
r

.
“

” Suppose B be not an upper approximation co-
nsistent set, then there must exist some
0
k
D
 
0
/, 1,2,,
D
UR kr

such that


0
Ak
RD




0
Bk
RD
.
That is to say there

0
iAk
x
RD
, but


0
iBk
x
RD.
So we have

0
ik
A
xD



 and

0
ik
B
xD



.
On the other hand, we know that
 
ii
AB
x
x

. So
there exists

ji
B
x
x and 0
j
k
x
D. Since
jj
A
xx





, so 0
jk
A
xD





.
Thus

0
jAk
xRD.
From above, we have


0
iAk
x
RD
 and
j
x


0
Ak
RD
.

X. Y. ZHANG ET AL. 134
That means 0
ij
r. Since
B
D
M
M, so we have
0
ij
m. However, we have obtained

ji
B
x
x, which is
a contradiction with0
ij
m.
Hence, B is an upper approximation consistent set
of
I
 if
B
D
M
M.
The theorem is proved.
Corollary 3.1 Let

,,,UA DFG

 be an or-
dered information system, and BA. B is a upper
approximation reduction of
I
if and only if
B
D
M
Mand
B
D
M
M

does not hold for all proper subset 'Bof B.
3.3. Algorithm of Matrix Computation for
Upper Approximation Reduction
Let

,,,UA DFG

 be an ordered information
system. We denote the dominance matrix of attributes
sets B by

12
,,, T
Bn
M

, and upper approxi-
mation decision matrix of
I
by

12
,,, T
Dn
M
 
,
where ,
ii

is the ith row vectors of
B
M
and
D
M
respectively, and T
X
means transposed matrix of ma-
trix
X
. So we can obtain the following algorithm by
Theorem 3.1 and Corollary 3.1.
Algorithm Algorithm of matrix computation for upper
approximation reduction in inconsistent ordered infor-
mation systems is described as follows:
Input: An inconsistent ordered information sys-
tem

,,,UA DFG

, where

12
,,,
n
Uxxx
and

12
,,,
p
A
aa a.
Output: Upper approximation reductions of

,,,UA DFG

.
Step 1. Simplify the system by combining the objects
with same values of every attribute.
Step 2. Calculate upper approximation decision matrix
of  :

12
,,, T
Dn
M
 
.
Step 3. For all

,1
l
aA lp, calculate the first
order dominance matrices,

(1)(1) (1)(1)
{}{}12
,,,
ll
T
aa n
MM    .
For 1i to n.
If (1)
0ii

 
, then let(1) 0
i


,
Denote the new matrix by (1)
{}
l
a
FM , and turn into next
step.
Step 4. Call matrix

(1)(1) (1)(1)
{}12
,,,,
l
T
an
FM   

,1
l
aA lp to be the first order upper ap-
proximation matrix. If (1)
{} 0
l
a
FM , then obtain an the
first order upper approximation reduction:


l
a. Other-
wise, turn into next step.
Step 5. Calculate the intersection of all the first order
nonzero matrix which are obtained in step 3, and call
new matrices to be the second order dominance matrices,
denoted by
(2)
{}
ls
aa
M,


(2)(1) (2)(1)
{}{}{}{}
,
lsl lss
aaa aaa
MMMM

.
Go back to step 3 and calculate all the second order
upper approximation reductions.
Step 6. Obtain the higher order upper approximation
reductions by repeating step 5. If the new matrices are
zero matrices, then output all upper approximation re-
ductions and terminate the algorithm.
From the above algorith m, we can know that the com-
plication of times is


2||
||2
A
OU easily.
3. An Example
Example Given an ordered information system in the
following Table.
From the table, we can compute the dominance matrices
and upper approximation decision m atrices, which are
1
{}
111111
010011
111111
010111
010011
010011
a
M





















2
{}
110011
110011
111111
111111
000010
110011
a
M





















3
{}
111111
011111
011111
000101
011111
000101
a
M





















{}
111111
111111
111111
000101
111111
000001
Dd
MM





















By comparing matrices 123
{} {}{}
,,
aaa
MMM and {}d
M
,
we can find that vectors of the first, second, third, and
5th row in matrix 1
{}a
M and 2
{}a
M are less then those
in matrix {}d M respectively. So the system has not the
first order upper approximation reduction. Thus the first
order upper approximation matrices are as follows:

X. Y. ZHANG ET AL. 135
Table 1. An ordered information system.
U 1
a 2 a 3 a d
1
x
1 2 1 3
2
x
3 2 2 2
3
x
1 1 2 1
4
x
2 1 3 2
5
x
3 3 2 3
6
x
3 2 3 1
1
(1)
{}
000000
000000
000000
010111
000000
010011
a
FM










;
2
(1)
{}
000000
000000
000000
111111
000000
110011
a
FM










;
3
(1)
{}
000000
000000
000000
000000
000000
000101
a
FM










Furthermore, the second order upper approximation
matrices are
121 2
(2)(1) (1)
{,}{} {}
000000
000000
000000
010111
000000
010011
aaa a
MFMFM












131 3
(2)(1) (1)
{,}{}{}
000000
000000
000000
000000
000000
000001
aaa a
MFMFM












232 3
(2)(1) (1)
{,}{} {}
000000
000000
000000
000000
000000
000001
aa a a
MFMFM












So, we can see that 13 23
(2) (2)
{} {} aa aa
MM, and the 6th row
vectors of them are less then those of {}d
M respectively,
by comparing 12
(2)
{} aa
M, 13
(2)
{} aa
M, 23
(2)
{} aa
M and {}d
M
.
Hence, we can obtain all the second order upper ap-
proximation reductions, which are

13 23
,,,aaaa.
In the next, we have
13 23
(2) (2)
{,} {,}
000000
000000
000000
000000
000000
000000
aa aa
FM FM











So, the algorithm is terminated.
Thus, all upper approximation reductions are




13 23
,,,aaaa in the system of above example, which
are consistent with ref.[5].
From the example, we can find that the algorithm is
valid, and operated simply, for systems with a great deal
of objects and attributes
5. Conclusions
It is well known that most of information systems are
based on dominance relations because of various factors
in practice. Therefore, it is meaningful to study the
knowledge reductions in inconsistent ordered informa-
tion system. In this article, the dominance matrix and
upper approximation decision matrix are introduced in
information systems based on dominance relations. Fur-
thermore, the algorithm of upper approximation reduc-
tion is obtained, from which we can provide new ap-
proach to knowledge reductions in inconsistent systems
based on dominance relations. Finally, an example illus-
trates the validity of this method, and shows the method
is applicable to a complicated information system.
6. References
[1] Z. Pawlak, “Rough Sets,” International Journal of
Computer and Information Science, Vol. 11 , N o. 5, 1982,
pp. 341-356. HH0UUdoi:10.1007/BF01001956U
[2] Y. Leuang, W. Z. Wu and W. X. Zhang, “Knowledge Ac-
quisition in Incomplete Information Systems: A Rough
Set Approach,” European Journal of Operational Re-

X. Y. ZHANG ET AL. 136
search, Vol. 168, No. 1, 2006, pp. 164-180.
HH1UUdoi:10.1016/j.ejor.2004.03.032U
[3] W. H. Xu and W. X. Zhang, “Measuring Roughness of
Generalized Rough Sets Induced by a Covering,” Fuzzy
Sets and Systems, Vol. 158, No. 22, 2007, pp. 2443-2455.
HH2UUdoi:10.1016/j.fss.2007.03.018U
[4] W. X. Zhang, W. Z. Wu, J. Y. Liang and D. Y. Li, “Theory
and Method of Rough Sets,” Science Press, Beijing,
2001.
[5] W. H. Xu, X. Y. Zhang and W. X. Zhang, “Upper Ap-
proximation Reduction in Inconsistent Information Sys-
tems Based on Dominance Relations,” Computer Engi-
neering, Vol. 35, No. 18, 2009, pp. 191-193.
[6] W. H. Xu, X. Y. Zhang and W. X. Zhang, “Knowledge
Granulation, Knowledge Entropy and Knowledge Uncer-
tainty Measure in Information Systems,” Applied Soft
Computing, Vol. 9, No. 4, 2009, pp. 1244-1251.
HH3UUdoi:10.1016/j.asoc.2009.03.007U
[7] W. H. Xu, X. Y. Zhang, J. M. Zhong and W. X. Zhang,
“Attribute Reduction in Ordered Information Systems
Based on Evidence Theory,” Knowledge and Information
Systems, Vol. 25, No. 1, 2010, pp. 169-184.
HH4UUdoi:10.1007/s10115-009-0248-5U
[8] W. H. Xu and W. X. Zhang, “Knowledge Reduction and
Matrix Computation in Inconsistent Ordered Information
Systems,” International Journal Business Intelligence
and Data Mining, Vol. 3, No. 4, 2008, pp. 409-425.
HH5UUdoi:10.1504/IJBIDM.2008.022737U
[9] W. H. Xu, M. W. Shao and W. X. Zhang, “Knowledge
Reduction Based on Evidence Reasoning Theory in Or-
dered Information Systems,” Lecture Notes in Artificial
Intelligence, Vol. 4092, 2006, pp. 535-547.
[10] W. H. Xu and W. X. Zhang, “Methods for Knowledge
Reduction in Inconsistent Ordered Information Systems,”
Journal of Applied Mathematics & Computing, Vol. 26,
No. 1-2, 2008, pp. 313-323.
[11] W. Z. Wu, M. Zhang, H. Z. Li and J. S. Mi, “Attribute
Reduction in Random Information Systems Via Demp-
ster-Shafer Theory of Evidence,” Information Sciences,
Vol. 174, No. 3-4, 2005, pp. 143-164.
HH6UUdoi:10.1016/j.ins.2004.09.002U
[12] M. Zhang, L. D. Xu, W. X Zhang and H. Z. Li, “A Rough
Set Approach to Knowledge Reduction Based on Inclu-
sion Degree and Evidence Reasoning Theory,” Expert
Systems, Vol. 20, No. 5, 2003, pp. 298-304.
HH7UUdoi:10.1111/1468-0394.00254U
[13] S. Greco, B. Matarazzo and R. Slowingski, “Rough Ap-
proximation of a Preference Relatioin by Bominance Re-
latioin,” European Journal of Operational Research, Vol.
117, No. 1, 1999, pp. 63-83.
HH8UUdoi:10.1016/S0377-2217(98)00127-1U
[14] S. Greco, B. Matarazzo and R. Slowingski, “A New
Rough Set Approach to Multicriteria and Multiattribute
Classificatioin. In: Rough Sets and Current Trends in
Computing (RSCTC'98),” Springer-Verlag, Berlin, 1998.
pp. 60-67.
[15] S. Greco, B. Matarazzo and R. Slowingski, “Rough Sets
Theory for Multicriteria Decision Analysis,” European
Journal of Operational Research, Vol. 129, No. 1, 2001,
pp. 11-47. HH9UUdoi:10.1016/S0377-2217(00)00167-3U
[16] S. Greco, B. Matarazzo, R. Slowingski, “Rough Sets
Methodology for Sorting Problems in Presence of Mul-
tiple Attributes and Criteria,” European Journal of Op-
erational Research, Vol. 138, No. 2, 2002, pp. 247-259.
HH1UUdoi:10.1016/S0377-2217(01)00244-2U
[17] K. Dembczynski, R. Pindur and R. Susmaga, “Genera-
tion of Exhaustive Set of Rules within Dominance-
Based Rough Set Approach,” Electronic Notes Theory
Compute Sciences, Vol. 82, No. 4, 2003.
[18] Y. Sai, Y. Y. Yao and N. Zhong, “Data Analysis and
Mining in Ordered Information Tables,” IEEE Com-
puter Society Press, San Jose, 2001, pp. 497-504.
[19] M. W. Shao and W. X. Zhang, “Dominance Relation and
Rules in an Incomplete Ordered Information System,”
International Journal of Intelligent Systems, Vol. 20, No.
2005, pp. 13-27.
HH1UUdoi:10.1016/S0377-2217(01)00244-2UHHH