# On Distribution Reduction and Algorithm Implementation in Inconsistent Ordered Information Systems

Authors: Yanqin Zhang
Journal: The Scientific World Journal
 (2014)

---

## Abstract

As one part of our work in ordered information systems, distribution reduction is studied in inconsistent ordered information systems (OISs). Some important properties on distribution reduction are studied and discussed. The dominance matrix is restated for reduction acquisition in dominance relations based information systems. Matrix algorithm for distribution reduction acquisition is stepped. And program is implemented by the algorithm. The approach provides an effective tool for the theoretical research and the applications for ordered information systems in practices. For more detailed and valid illustrations, cases are employed to explain and verify the algorithm and the program which shows the effectiveness of the algorithm in complicated information systems.


---

## Body

## 1. Introduction

In Pawlak’s original rough set theory [1], partition or equivalence (indiscernibility) is an important and primitive concept. However, partition or equivalence relation, as the indiscernibility relation in Pawlak’s original rough set theory, is still restrictive for many applications. To address this issue, several interesting and meaningful extensions to equivalence relation have been proposed in the past, such as neighborhood operators [2], tolerance relations [3], and others [4–10]. Moreover, the original rough set theory does not consider attributes with preference ordered domain, that is, criteria. In many real life practices, we often face problems in which the ordering of properties of the considered attributes plays a crucial role. One such type of problem is the ordering of objects. For this reason, Greco et al. proposed an extension rough set theory, called the dominance based rough set approach (DRSA), to take into account the ordering properties of criteria [11–16]. This innovation is mainly based on substitution of the indiscernibility relation by a dominance relation. Moreover, Greco et al. characterizes the DRSA and decision rules induced from rough approximations, while the usefulness of the DRSA and its advantages over the CRSA (classical rough set approach) are presented [11–16]. In DRSA, condition attributes are criteria and classes are preference ordered. Several studies have been made about properties and algorithmic implementations of DRSA [10, 17–19].Nevertheless, only a limited number of methods using DRSA to acquire knowledge in inconsistent ordered information systems have been proposed and studied. Pioneering work on inconsistent ordered information systems with the DRSA has been proposed by Greco et al. [11–16], but they did not clearly point out the semantic explanation of unknown values. Shao and Zhang [20] further proposed an extension of the dominance relation in incomplete ordered information systems. Their work was established on the basis of the assumption that all unknown values are lost. Despite this, they did not mention the underlying concept of attribute reduction in inconsistent ordered decision system but they mentioned an approach to attribute reduction in consistent ordered information systems. Therefore, the purpose of this paper is to develop approaches to attribute reductions in inconsistent ordered information systems (IOIS). In this paper, theories and approaches of distribution reduction are investigated in inconsistent ordered information systems. Furthermore, algorithm of matrix computation of distribution reduction is introduced, from which we can provide a new approach to attributes reductions in inconsistent ordered information systems.The rest of this paper is organized as follows. Some preliminary concepts are briefly recalled in Section2. In Section 3, theories and approaches of distribution reduction are investigated in IOIS. In Section 4, we restate the definition of dominance matrix in ordered information systems and step the matrix algorithm for distribution reduction acquisition. Preparations are implemented to place the algorithm and the program is designed. The algorithm and the corresponding program we designed can provide a tool to theoretical research and applications of criterion based information system. Cases are employed to illustrate the algorithm and the program in Section 5. It is shown that the algorithm and program are effective in complicated information system. Furthermore conclusions on what we study in this paper are drawn to understand this paper briefly.


## 2. Ordered Information Systems

The following recalls necessary concepts and preliminaries required in the sequel of our work. Detailed description of the theory can be found in [11–16].An information system with decisions is an ordered quadrupleI
=
(
U
,
A
∪
D
,
F
,
G
), where U
=
{
x
1
,
x
2
,
…
,
x
n
} is a nonempty finite set of objects; A
∪
D is a nonempty finite attributes set; A
=
{
a
1
,
a
2
,
…
,
a
p
} denotes the set of condition attributes; D
=
{
d
1
,
d
2
,
…
,
d
q
} denotes the set of decision attributes, A
∩
D
=
ϕ; F
=
{
f
k
∣
U
→
V
k
,
k
≤
p
}, f
k
(
x
) is the value of a
k on x
∈
U
;
V
k is the domain of a
k
,
a
k
∈
A; G
=
{
g
k
′
∣
U
→
V
k
′
,
k
′
≤
q
}, g
k
′
(
x
) is the value of d
k
′ on x
∈
U
,
V
k
′ is the domain of d
k
′
,
d
k
′
∈
D. In an information system, if the domain of an attribute is ordered according to a decreasing or increasing preference, then the attribute is a criterion. An information system is called an ordered information system (OIS) if all condition attributes are criterions.Assume that the domain of a criteriona
∈
A is completely preordered by an outranking relation ⪰
a; then x
⪰
a
y means that x is at least as good as y with respect to criterion a. And we can say that x dominates y. In the following, without any loss of generality, we consider condition and decision criterions having a numerical domain; that is, V
a
⊆
R (R denotes the set of real numbers).We definex
⪰
y by f
(
x
,
a
)
≥
f
(
y
,
a
) according to increasing preference, where a
∈
A and x
,
y
∈
U. For a subset of attributes B
⊆
A, x
⪰
B
y means that x
⪰
a
y for any a
∈
B. That is to say x dominates y with respect to all attributes in B. Furthermore, we denote x
⪰
B
y by x
R
B
≥
y. In general, we indicate an ordered information system with decision by I
⪰
=
(
U
,
A
∪
D
,
F
,
G
). Thus the following definition can be obtained.LetI
⪰
=
(
U
,
A
∪
D
,
F
,
G
) be an ordered information system with decisions, for B
⊆
A; denote
(1)
R
B
⪰
=
{
(
x
i
,
x
j
)
∈
U
×
U
∣
f
l
(
x
i
)
≥
f
l
(
x
j
)
,
∀
a
l
∈
B
}
;
R
D
⪰
=
{
(
x
i
,
x
j
)
∈
U
×
U
∣
g
m
(
x
i
)
≥
g
m
(
x
j
)
,
∀
d
m
∈
D
}
.
R
B
⪰ and R
D
⪰ are called dominance relations of information system I
⪰.If we denote(2)
[
x
i
]
B
⪰
=
{
x
j
∈
U
∣
(
x
j
,
x
i
)
∈
R
B
⪰
}
=
{
x
j
∈
U
∣
f
l
(
x
j
)
≥
f
l
(
x
i
)
,
∀
a
l
∈
B
}
,
[
x
i
]
D
⪰
=
{
x
j
∈
U
∣
(
x
j
,
x
i
)
∈
R
D
⪰
}
=
{
x
j
∈
U
∣
g
m
(
x
j
)
≥
g
m
(
x
i
)
,
∀
d
m
∈
D
}
,
then the following properties of a dominance relation are trivial.LetR
A
⪰ be a dominance relation. The following properties hold.(1)
R
A
⪰ is reflexive and transitive, but not symmetric, so it is not an equivalence relation.
(2)
IfB
⊆
A, then R
A
⪰
⊆
R
B
⪰.
(3)
IfB
⊆
A, then [
x
i
]
A
⪰
⊆
[
x
i
]
B
⪰.
(4)
Ifx
j
∈
[
x
i
]
A
⪰, then [
x
j
]
A
⪰
⊆
[
x
i
]
A
⪰ and [
x
i
]
A
⪰
=
∪
{
[
x
j
]
A
⪰
∣
x
j
∈
[
x
i
]
A
⪰
}.
(5)
[
x
j
]
A
⪰
=
[
x
i
]
A
⪰ if and only if f
(
x
i
,
a
)
=
f
(
x
j
,
a
)
(
∀
a
∈
A
).
(6)
J
=
∪
{
[
x
]
A
⪰
∣
x
∈
U
} constitute a covering of U.For any subsetX of U, and A of I
⪰, define
(3)
R
A
⪰
_
(
X
)
=
{
x
∈
U
[
x
]
A
⪰
⊆
X
}
,
R
A
⪰
¯
(
X
)
=
{
x
∈
U
∣
[
x
]
A
⪰
∩
X
≠
ϕ
}
.
R
A
⪰
_
(
X
) and R
A
⪰
¯
(
x
) are said to be the lower and upper approximations of X with respect to a dominance relation R
A
⪰. And the approximations have also some properties which are similar to those of Pawlak approximation spaces.For an ordered information system with decisionsI
⪰
=
(
U
,
A
∪
D
,
F
,
G
), if R
A
⪰
⊆
R
D
⪰, then this information system is consistent, otherwise, this information system is inconsistent (IOIS).Example 1.
An ordered information system is given in Table1.Table 1
An ordered information system.
U
a
1
a
2
a
3
d
x
1
1
2
1
3
x
2
3
2
2
2
x
3
1
1
2
1
x
4
2
1
3
2
x
5
3
3
2
3
x
6
3
2
3
1From the table, we have(4)
[
x
1
]
A
⪰
=
{
x
1
,
x
2
,
x
5
,
x
6
}
;
[
x
2
]
A
⪰
=
{
x
2
,
x
5
,
x
6
}
;
[
x
3
]
A
⪰
=
{
x
2
,
x
3
,
x
4
,
x
5
,
x
6
}
;
[
x
4
]
A
⪰
=
{
x
4
,
x
6
}
;
[
x
5
]
A
⪰
=
{
x
5
}
;
[
x
6
]
A
⪰
=
{
x
6
}
;
[
x
1
]
d
⪰
=
[
x
5
]
d
⪰
=
{
x
1
,
x
5
}
;
[
x
2
]
d
⪰
=
[
x
4
]
d
⪰
=
{
x
1
,
x
2
,
x
4
,
x
5
}
;
[
x
3
]
d
⪰
=
[
x
6
]
d
⪰
=
{
x
1
,
x
2
,
x
3
,
x
4
,
x
5
,
x
6
}
.Obviously, by the above, we haveR
A
⪰
⊈
R
d
⪰, so the system in Table 1 is inconsistent.For a simple description, the following information system with decisions is based on dominance relations, that is, ordered information system.


## 3. Theories of Distribution Reduction in Inconsistent Ordered Information Systems

LetI
⪰
=
(
U
,
A
∪
D
,
F
,
G
) be an information system with decisions, and R
B
⪰
,
R
D
⪰ dominance relations derived from condition attributes set B
⊆
A and decision attributes set D, respectively. For B
⊆
A, denote
(5)
U
R
B
⪰
=
{
[
x
i
]
B
⪰
∣
x
i
∈
U
}
,
U
R
d
⪰
=
{
D
1
,
D
2
,
…
,
D
r
}
,
μ
B
⪰
(
x
)
=
(
|
D
1
∩
[
x
]
B
⪰
|
|
U
|
,
|
D
2
∩
[
x
]
B
⪰
|
|
U
|
,
…
,
|
D
r
∩
[
x
]
B
⪰
|
|
U
|
)
,
γ
B
⪰
(
x
)
=
max
⁡
⁡
{
|
D
1
∩
[
x
]
B
⪰
|
|
U
|
,
|
D
2
∩
[
x
]
B
⪰
|
|
U
|
,
…
,
|
D
r
∩
[
x
]
B
⪰
|
|
U
|
}
,
where [
x
]
B
⪰
=
{
y
∈
U
∣
(
x
,
y
)
∈
R
B
⪰
}. Furthermore, we let μ
B
⪰
(
x
) be a distribution function about attributions set B and γ
B
⪰
(
x
) maximum distribution function about attributions set B.Definition 2.
Letα
=
(
a
1
,
a
2
,
…
,
a
n
) and β
=
(
b
1
,
b
2
,
…
,
b
n
) be two vectors with n dimensions. If a
i
=
b
i
,
(
i
=
1,2
,
…
,
n
), we say that α is equal to β and is denoted by α
=
β. If a
i
≤
b
i
,
(
i
=
1,2
,
…
,
n
), we say that α is less than β and is denoted by α
≤
β. Otherwise, if it exists i
0
(
i
0
∈
{
1,2
,
…
,
n
}
) such that a
i
0
>
b
i
0, we say α is not less than β and it is denoted by α
≰
β,
such as(
1,2
,
3
)
≰
(
1,1
,
4
) and (
1,1
,
4
)
≰
(
1,2
,
3
).
From the above, we can have the following propositions immediately.Proposition 3.
LetI
⪰
=
(
U
,
A
∪
D
,
F
,
G
) be an inconsistent information system.(1)
IfB
⊆
A, then μ
A
⪰
(
x
)
≤
μ
B
⪰
(
x
), ∀
x
∈
U.
(2)
IfB
⊆
A, then γ
A
⪰
(
x
)
≤
γ
B
⪰
(
x
), ∀
x
∈
U.
(3)
If[
y
]
B
⪰
⊇
[
x
]
B
⪰, then μ
B
⪰
(
y
)
≤
μ
B
⪰
(
x
), ∀
x
,
y
∈
U.
(4)
If[
y
]
B
⪰
⊇
[
x
]
B
⪰, then γ
B
⪰
(
y
)
≤
γ
B
⪰
(
x
), ∀
x
,
y
∈
U.Definition 4.
LetI
⪰
=
(
U
,
A
∪
D
,
F
,
G
) be an inconsistent information system. If μ
B
⪰
(
x
)
=
μ
A
⪰
(
x
), for all x
∈
U, we say that B is a distribution consistent set of I
⪰. If B is a distribution consistent set, and no proper subset of B is a distribution consistent set, then B is called a distribution consistent reduction of I
⪰.Definition 5.
LetI
⪰
=
(
U
,
A
∪
D
,
F
,
G
) be an inconsistent information system. If γ
B
⪰
(
x
)
=
γ
A
⪰
(
x
), for all x
∈
U, we say that B is a maximum distribution consistent set of I
⪰. If B is a maximum distribution set, and no proper subset of B is a maximum distribution consistent set, then B is called a maximum distribution consistent reduction of I
⪰.Example 6.
For the system in Table1, if we denote
(6)
D
1
=
[
x
1
]
d
⪰
=
[
x
5
]
d
⪰
,
D
2
=
[
x
2
]
d
⪰
=
[
x
4
]
d
⪰
,
D
3
=
[
x
3
]
d
⪰
=
[
x
6
]
d
⪰
,
then we can have
(7)
μ
A
⪰
(
x
1
)
=
(
1
3
,
1
2
,
2
3
)
;
μ
A
⪰
(
x
2
)
=
(
1
6
,
1
3
,
1
2
)
;
μ
A
⪰
(
x
3
)
=
(
1
6
,
1
2
,
5
6
)
;
μ
A
⪰
(
x
4
)
=
(
0
,
1
6
,
1
3
)
;
μ
A
⪰
(
x
5
)
=
(
1
6
,
1
6
,
1
6
)
;
μ
A
⪰
(
x
6
)
=
(
0,0
,
1
6
)
,
γ
A
⪰
(
x
1
)
=
2
3
;
γ
A
⪰
(
x
2
)
=
1
2
;
γ
A
⪰
(
x
3
)
=
5
6
;
γ
A
⪰
(
x
4
)
=
1
3
;
γ
A
⪰
(
x
5
)
=
1
6
;
γ
A
⪰
(
x
6
)
=
1
6
.
When B
=
{
a
2
,
a
3
}, it can be easily checked that [
x
]
A
⪰
=
[
x
]
B
⪰, for all x
∈
U, so thatμ
B
⪰
(
x
)
=
μ
A
⪰
(
x
) and γ
B
⪰
(
x
)
=
γ
A
⪰
(
x
) are true and B
=
{
a
2
,
a
3
} is a distribution consistent set of I
⪰. Furthermore, we can examine that {
a
2
} and {
a
3
} are not consistent sets of I
⪰. That is to say B
=
{
a
2
,
a
3
} is a distribution reduction and is a maximum distribution reduction of I
⪰.
Moreover, it can easily be calculated thatB
′
=
{
a
1
,
a
3
} and B
′′
=
{
a
1
,
a
2
} are not distribution consistent sets of I
⪰. Thus there exist only one distribution reduction and maximum distribution reduction of I
⪰ in the system of Table 1, which are {
a
2
,
a
3
}.
The distribution consistent set and the maximum distribution consistent set are related in the following theorem.Theorem 7.
LetI
⪰
=
(
U
,
A
∪
D
,
F
,
G
) be an ordered information system and B
⊆
A is a distribution consistent set of I
⪰ if and only if B is a maximum distribution consistent set of I
⪰.Proof.
It can be proved immediately from corresponding definitions and properties. From the definitions of distribution and maximum distribution consistent set, the key results of the implication is that[
x
]
B
⪰
=
[
x
]
A
⪰ always holds for any x
∈
U while B is a distribution consistent set or maximum distribution consistent set. Thus, the theorem can be acquired immediately.Theorem 8.
LetI
⪰
=
(
U
,
A
∪
D
,
F
,
G
) be an ordered information system.P
:B
⊆
A is a distribution consistent set of I
⪰.
Q: While μ
A
⪰
(
y
)
≰
μ
A
⪰
(
x
), [
y
]
B
⪰
⊈
[
x
]
B
⪰ holds for any x
,
y
∈
U.Then we have P
⇒
Q.Proof.
We will prove¬
Q
⇒
¬
P. Assume that when μ
A
⪰
(
y
)
≰
μ
A
⪰
(
x
), [
y
]
B
⪰
⊈
[
x
]
B
⪰ does not hold and that implies [
y
]
B
⪰
⊆
[
x
]
B
⪰. So we can obtain μ
B
⪰
(
y
)
≤
μ
B
⪰
(
x
) by Proposition 3(3). On the other hand, since B is a distribution consistent set of I
⪰, we have μ
A
⪰
(
x
)
=
μ
B
⪰
(
x
) and μ
A
⪰
(
y
)
=
μ
B
⪰
(
y
). Hence we can get μ
A
⪰
(
y
)
≤
μ
A
⪰
(
x
), which is a contradiction. The theorem is proved.The distribution consistent set requires that the classification ability of the consistent remains the same with the original data table. That is,B
⊂
A, which is a distribution consistent set of A, must satisfy the fact that [
x
]
B
⪰
=
[
x
]
A
⪰ holds for any x
∈
U. This is very strict and other reductions studied in [21] may not reach this special condition.


## 4. Matrix Algorithm for Distribution Reduction Acquisition in Inconsistent Ordered Information Systems

In this section, the dominance matrices will be put as a restatement and matrices will be employed to realize the calculation of distribution reductions.Definition 9.
LetI
⪰
=
(
U
,
A
∪
D
,
F
,
G
) be an ordered information system, and B
⊂
A. Denote
(8)
M
B
=
(
m
i
j
)
n
×
n
,
where
m
i
j
=
{
1
,
x
j
∈
[
x
i
]
B
⪰
,
0
,
otherwise
.
The matrix M
B is called dominance matrix of attributes set B
⊆
A. If |
B
|
=
l, we say that the order of M
B is l.Definition 10.
LetI
⪰
=
(
U
,
A
∪
D
,
F
,
G
) be an ordered information system and M
B and M
C are dominance matrices of attributes sets B
,
C
⊆
A. The intersection of M
B and M
C is defined by
(9)
M
B
∩
M
C
=
(
m
i
j
)
n
×
n
∩
(
m
i
j
′
)
n
×
n
=
(
min
⁡
⁡
{
m
i
j
,
m
i
j
′
}
)
n
×
n
.
The intersection defined above can be implemented by the operator“
.
*
” in Matlab platform, M
B
∩
M
C
=
M
B
.
*
M
C, that is, the product of elements in corresponding positions. Then the following properties are obvious.Proposition 11.
LetM
B, M
C be dominance matrices of attributes sets B
,
C
⊆
A; the following results always hold.(1)
m
i
i
=
1.
(2)
M
B
∪
C
=
M
B
∩
M
C.From the above, we can see that a dominance relation of objects has one-one correspondence to a dominance matrix. The combination of dominance relations can be realized by the corresponding matrices and the dominance relations can be compared by the corresponding matrices from the following definitions.Definition 12.
LetM
A
=
(
α
1
,
α
2
,
…
,
α
n
)
T and M
B
=
(
β
1
,
β
2
,
…
,
β
n
)
T be matrices with n
×
n dimensions and α
i and β
i row vectors, respectively. If α
i
≤
β
i holds, for any i
≤
n, we say that M
A is less than M
B and it is denoted by M
A
≤
M
B.
By the definitions, dominance matrices have the following properties straightly.Proposition 13.
LetI
⪰
=
(
U
,
A
∪
D
,
F
,
G
) be an ordered information system and B
⊆
A. The dominance matrices with respect to A and B are, respectively, M
A and M
B. Then M
A
≤
M
B.In the following, we give the preparation of matrix computation for distribution reductions in ordered information systems.Proposition 14.
LetI
⪰
=
(
U
,
A
∪
D
,
F
,
G
) be an ordered information system and U
=
{
x
1
,
x
2
,
…
,
x
n
} and A
=
{
a
1
,
a
2
,
…
,
a
p
}. Then
(10)
M
A
=
⋂
i
=
1
p
‍
M
{
a
i
}
=
(
a
11
a
12
⋯
a
1
n
a
21
a
22
⋯
a
2
n
⋮
⋮
⋱
⋮
a
n
1
a
n
2
⋯
a
n
n
)
and any vector α
i
=
(
a
i
1
,
a
i
2
,
…
,
a
i
n
) represents the dominance class of object x
i by the values 0 and 1, where 0 means the object not included in the class and 1 means the object included in the class.Theorem 15.
LetI
⪰
=
(
U
,
A
∪
D
,
F
,
G
) be an ordered information system and B
⊆
A. B is a consistent set if and only if M
B
=
M
A.Proof.
As is known,[
x
]
A
⪰
⊆
[
x
]
B
⪰ holds since B
⊆
A.
(⇒) For B is a distribution consistent set, one can haveμ
B
=
μ
A. Then, for any x and D
j, we have |
D
j
∩
[
x
]
A
⪰
|
=
|
D
j
∩
[
x
]
B
⪰
|. Since [
x
]
A
⪰
⊆
[
x
]
B
⪰, it is obvious that [
x
]
A
⪰
=
[
x
]
B
⪰. That is, the row vectors in M
B and M
A are correspondingly the same. Then M
B
=
M
A.
(⇐) Since M
B
=
M
A, we can easily obtain that [
x
]
A
⪰
=
[
x
]
B
⪰ holds for any x and D
j. Then |
D
j
∩
[
x
]
A
⪰
|
=
|
D
j
∩
[
x
]
B
⪰
| holds for any x and D
j. We can obtain that μ
B
⪰
(
x
)
=
μ
A
⪰
(
x
) holds for any x. That is, B is a distribution consistent set.
To acquire reductions in inconsistent ordered information system, the matrices can be the only forms of storage in computing. And we illustrate the progress to calculate the reductions as shown in Algorithm1.Algorithm 1
Input:  An inconsistent ordered information system I
⪰
=
(
U
,
A
∪
D
,
V
,
f
), where  U
=
{
x
1
,
x
2
,
…
,
x
n
} and  A
=
{
a
1
,
a
2
,
…
,
a
p
}.
Output: All distribution reductions of I
⪰.
Step  1.  Load the ordered information system and simplify the system by combining the objects with same values of every
attribute,
Step  2.  Classify by every single criterion and store then in separate matrices
M
a
i
=
(
a
11
i
a
12
i
⋯
a
1
n
i
a
21
i
a
22
i
⋯
a
2
n
i
⋮
⋮
⋱
⋮
a
n
1
i
a
n
2
i
⋯
a
n
n
i
).
M
d
=
(
d
11
d
12
⋯
d
1
n
d
21
d
22
⋯
d
2
n
⋮
⋮
⋱
⋮
d
n
1
d
n
2
⋯
d
n
n
).
Step  3.  Check the consistence of the information system
M
A
=
⋂
i
=
1
p
‍
M
a
i
=
M
a
1
.
*
M
a
2
.
*
⋯
.
*
M
a
p
=
(
a
11
a
12
⋯
a
1
n
a
21
a
22
⋯
a
2
n
⋮
⋮
⋱
⋮
a
n
1
a
n
2
⋯
a
n
n
).
where “.*” is the operator in Matlab platform. IfM
A
≤
M
d, the system is consistent, terminate the algorithm.
Else the system is inconsistent, go to the next step.
Step  4.  Acquire the consistent set. Let B
=
{
b
1
,
b
2
,
⋯
,
b
m
}
⊂
A
M
B
=
⋂
i
=
1
m
‍
B
i
=
B
1
.
*
B
2
.
*
⋯
.
*
B
m
.
=
(
b
11
b
12
⋯
b
1
n
b
21
b
22
⋯
b
2
n
⋮
⋮
⋱
⋮
b
n
1
b
n
2
⋯
b
n
n
).
IfM
B
=
M
A, B is a consistent set, store the set into the temporary storage cell. Else fetch another subset of A and repeat this step.
Calculate till all subsets ofA are verified, then go to the next step.
Step  5.  Sort the consistent sets in the storage cell and find out the minimum consistent sets which are just the reductions.
Output all reductions and terminate the algorithm.The algorithm and the distribution reduction allow us to calculate reductions which keep the classification ability the same with the original system in a brief way. And we do not need to acquire every approximation of the decisions. It shortens the computing time and provides an effective tool for knowledge acquisition in criterion based rough set theory. The flow chart of the Algorithm1 can be designed and it is placed in Figure 1.Figure 1
The flow chart of Algorithm1.Analysis to Time Complexity of Algorithm
1. Let I
⪰
=
(
U
,
A
∪
D
,
F
,
G
) be an ordered information system. U
=
{
x
1
,
x
2
,
…
,
x
n
} is the simplified universe. The number of objects in original information system not being simplified is denoted by n
1. There are m condition attributes in A; that is, |
A
|
=
m. The number of compressed decision classes is r. We take a variable t
i to stand for the time complexity in an implementation. In the next, we can analyze the time complexity of Algorithm 1 step by step.The time complexity to simplify the original information system isn
1
2 for any two objects being compared and is denoted by t
1
=
n
1
2. Since |
U
|
=
n, |
A
|
=
m, and |
D
|
=
1, the time complexities to be classified by condition attributes and decision D are, respectively, t
2
=
|
U
|
2
×
|
A
| and t
3
=
|
U
|
2. For decision classes being merged by comparing classes of any two objects, the time complexity is t
4
=
|
U
|
2. Now the consistency of the information system needs to be checked by comparing the condition class and decision class of any object. If the information system is consistent, the time complexity to check consistency is |
U
|. If the information system is inconsistent, the time complexity to check consistency is less than |
U
|. Thus, the time complexity to check consistency is no more than |
U
|; that is, it is presented as t
5
≤
|
U
|. Then, the possible and compatible distribution functions can be calculated and the time complexity is t
6
=
2
r
×
|
U
|. The time complexity to calculate each of these two functions is r
×
|
U
| and is denoted by t
6
σ
=
t
6
δ
=
r
×
|
U
|. The analysis to Step 1 is finished.For Step 2, the time complexity to calculate possible and compatible distribution decision matrices, respectively, is denoted byt
7
σ
=
t
7
δ
=
|
U
|
2. Thus, the time complexity to calculate distribution decision matrices is t
7
=
2
|
U
2
|. The time complexity of Step 2 is completed.The first two steps are preparations to calculate reductions. The next Step 3 to Step 5 are the steps which run the operations. There areC
m
1
=
m subsets {
a
l
} and the dominance matrices are with dimensions n
×
n. In addition, the representation C
m
i is the combinatorial number which means the number of selections to chose i elements from m ones. We consider that the judgement of a vector if it is zero runs one operation and the comparison of two vectors runs according to the dimension of the vectors. Therefore, the time complexities to compare M
d
σ and M
d
δ with M
{
a
l
}, respectively, are |
U
|
2. And the time complexity to compare every line vector of M
{
a
l
} with zero is |
U
|. The possible and compatible distribution matrices are obtained by reassignment values n times. And the time complexities to process possible and compatible distribution matrices, respectively, are both n. Then, we have that the total time complexity of Step 3 is t
8
=
C
m
1
×
(
3
|
U
|
2
+
3
|
U
|
). The judgement in Step 4 just need to run according to the number of {
a
l
} and the time complexity is t
9
=
2
C
m
1.Since we just need to compute the intersection of nonzero 1st order possible (or compatible) distribution matrices, the maximum time complexities can be analyzed in the next steps but not the true ones in computing. Therefore, the maximum time complexity relies on the number of attribute subsets2
|
C
|. The worst case is that no minimum reduction exists in the information system and all 2
|
C
| subsets are calculated in the algorithm. Thus, the maximum time complexity of Step 5 is t
10
=
2
C
m
2
×
|
U
|
2.From the above analysis, we can know that the maximum time complexity of the main part in the algorithm (Step 3 to Step 5) ist
main
=
t
8
+
t
9
+
t
10
=
|
A
|
×
(
|
U
|
2
+
|
U
|
).Hence, the maximum time complexity of the main algorithm is approximatelyO
(
(
|
U
|
2
+
2
|
U
|
)
×
|
A
|
).


## 5. Experimental Computing and Case Study

We design programs and employ two cases to demonstrate the effective of the method in the last section. This experimental computing program is running on a personal computer with the following hardware and software configuration. The configuration of the computer is a bit low but the program runs well and fast. It also shows the advantage of Algorithm1 and the corresponding computing program (see Table 2).Table 2
Names
Models
Parameters
CPU
Intel Core i3-380U
1.33 GHz
Memory
DDR3 SDRAM
2 × 2 GB 1333 MHz
Hard disk
TOSHIBA
320 GB
System
Windows 7
32 bit
Platform
Matlab
LeaseholdAn inconsistent ordered information system on animals sleep is presented in Table3.Table 3
I
⪰: An inconsistent ordered information system on animals sleep.
(
U
,
C
∪
{
d
}
)
a
1
a
2
a
3
a
4
a
5
a
6
a
7
a
8
a
9
d
x
1:
African giant pouched rat
1
6.6
6.3
2
8.3
4.5
42
3
1
3
x
2:
Asian elephant
2547
4603
2.1
1.8
3.9
69
624
3
5
4
x
3:
Baboon
10.55
179.5
9.1
0.7
9.8
27
180
4
4
4
x
4:
Big brown bat
0.023
0.3
15.8
3.9
19.7
19
35
1
1
1
x
5:
Brazilian tapir
160
169
5.2
1
6.2
30.4
392
4
5
4
x
6:
Cat
3.3
25.6
10.9
3.6
14.5
28
63
1
2
1
x
7:
Chimpanzee
52.16
440
8.3
1.4
9.7
50
230
1
1
1
x
8:
Chinchilla
0.425
6.4
11
1.5
12.5
7
112
5
4
4
x
9:
Cow
465
423
3.2
0.7
3.9
30
281
5
5
5
x
10:
Eastern American mole
0.075
1.2
6.3
2.1
8.4
3.5
42
1
1
1
x
11:
Echidna
3
25
8.6
0
8.6
50
28
2
2
2
x
12:
European hedgehog
0.785
3.5
6.6
4.1
10.7
6
42
2
2
2
x
13:
Galago
0.2
5
9.5
1.2
10.7
10.4
120
2
2
2
x
14:
Goat
27.66
115
3.3
0.5
3.8
20
148
5
5
5
x
15:
Golden hamster
0.12
1
11
3.4
14.4
3.9
16
3
1
2
x
16:
Gray seal
85
325
4.7
1.5
6.2
41
310
1
3
1
x
17:
Ground squirrel
0.101
4
10.4
3.4
13.8
9
28
5
1
3
x
18:
Guinea pig
1.04
5.5
7.4
0.8
8.2
7.6
68
5
3
4
x
19:
Horse
521
655
2.1
0.8
2.9
46
336
5
5
5
x
20:
Lesser short-tailed shrew
0.005
0.14
7.7
1.4
9.1
2.6
21.5
5
2
4
x
21:
Little brown bat
0.01
0.25
17.9
2
19.9
24
50
1
1
1
x
22:
Man
62
1320
6.1
1.9
8
100
267
1
1
1
x
23:
Mouse
0.023
0.4
11.9
1.3
13.2
3.2
19
4
1
3
x
24:
Musk shrew
0.048
0.33
10.8
2
12.8
2
30
4
1
3
x
25:
N. American opossum
1.7
6.3
13.8
5.6
19.4
5
12
2
1
1
x
26:
Nine-banded armadillo
3.5
10.8
14.3
3.1
17.4
6.5
120
2
1
1
x
27:
Owl monkey
0.48
15.5
15.2
1.8
17
12
140
2
2
2
x
28:
Patas monkey
10
115
10
0.9
10.9
20.2
170
4
4
4
x
29:
Phanlanger
1.62
11.4
11.9
1.8
13.7
13
17
2
1
2
x
30:
Pig
192
180
6.5
1.9
8.4
27
115
4
4
4
x
31:
Rabbit
2.5
12.1
7.5
0.9
8.4
18
31
5
5
5
x
32:
Rat
0.28
1.9
10.6
2.6
13.2
4.7
21
3
1
3
x
33:
Red fox
4.235
50.4
7.4
2.4
9.8
9.8
52
1
1
1
x
34:
Rhesus monkey
6.8
179
8.4
1.2
9.6
29
164
2
3
2
x
35:
Rock hyrax (Hetero.b)
0.75
12.3
5.7
0.9
6.6
7
225
2
2
2
x
36:
Rock hyrax (Procavia hab)
3.6
21
4.9
0.5
5.4
6
225
3
2
3
x
37:
Sheep
55.5
175
3.2
0.6
3.8
20
151
5
5
5
x
38:
Tenrec
0.9
2.6
11
2.3
13.3
4.5
60
2
1
2
x
39:
Tree hyrax
2
12.3
4.9
0.5
5.4
7.5
200
3
1
3
x
40:
Tree shrew
0.104
2.5
13.2
2.6
15.8
2.3
46
3
2
2
x
41:
Vervet
4.19
58
9.7
0.6
10.3
24
210
4
3
4
x
42:
Water opossum
3.5
3.9
12.8
6.6
19.4
3
14
2
1
1The information system is denoted byI
⪰
=
(
U
,
A
∪
{
d
}
,
V
,
f
), where A is the condition attribute set and d is the single dominance decision. There are 42 objects which represent the species of animals and 10 attributes with numerical values in the ordered information system. The animals’ names are showed in Table 3 and the interpretations of the attributes will be listed as follows. The interpretations and the units of attributes are represented as shown in Table 4.Table 4
a
1—Bodyweight in kg;
a
2—Brain weight in g;
a
3—Show wave (“nondreaming") sleep (hrs/day);
a
4—Paradoxical (“dreaming") sleep (hrs/day);
a
5—Total sleep (hrs/day);
a
6—Maximum life span (years);
a
7—Gestation time (days);
a
8—Predation index (1–5);
a
9—Sleep exposure index (1–5);
d—Overall danger index (1–5).By the experimental computing program, the distribution reductions of the system can be calculated and they are represented in the following. The operating time to compute this case is 0.158581 seconds.The distribution reductions are(11)
{
a
1
,
a
3
,
a
4
,
a
6
,
a
7
,
a
8
,
a
9
}
,
{
a
2
,
a
3
,
a
4
,
a
6
,
a
7
,
a
8
,
a
9
}
,
{
a
1
,
a
2
,
a
3
,
a
4
,
a
6
,
a
7
,
a
8
,
a
9
}
,
{
a
1
,
a
3
,
a
4
,
a
5
,
a
6
,
a
7
,
a
8
,
a
9
}
,
{
a
2
,
a
3
,
a
4
,
a
5
,
a
6
,
a
7
,
a
8
,
a
9
}
.And it can be verified by taking the computer as an assistant that the above sets are reductions of the data table. Detailed progress of the verifying are not arranged here. From the results, we can easily see that the reductions studied in this paper are different from the ones approached in since these reductions are{
a
3
,
a
4
,
a
6
,
a
7
}, {
a
4
,
a
5
,
a
6
,
a
7
}, {
a
6
,
a
8
,
a
9
}, and {
a
1
,
a
2
,
a
8
,
a
9
}. They are different kinds of reductions in ordered information systems and can adapt to different needs in practices. From the definition of different reductions, we can also easily obtain that possible and compatible reductions are usually subsets of distribution reduction. This is not strict and should be studied and verified separately and theatrically. And the work may be taken into account as one part of the future studies in our work.Finally, we take other inconsistent ordered information system to acquire the distribution reduction, respectively. And the descriptions on the data tables are listed in Table5.Table 5
Descriptions on the calculations.
Data name
Values
Objects
Conditions
Decisions
Reductions
Time
Operations
Body fat
Real
252
14
1
11
36.43723 s
10
Glass
Real
213
9
1
7
2.04624 s
10
Animal sleep
Real
42
9
1
5
0.13153 s
10From the results in Table5, we can obtain that the algorithm and the program we studied in this paper could be effective and useful to acquire distribution reductions in practice. The numbers of objects and attributes can increase the computing time. But the matrices storage has the ability to shorten the memory and computing time. And it can be helpful in research theoretically and it is applicable.


## 6. Conclusions

As is known, many information systems are data tables considering criteria for various factors in practise. Therefore, it is meaningful to study the attribute reductions in inconsistent information system on the basis of dominance relations. In this paper, distribution reduction is restated in inconsistent ordered information systems. Some properties and theorems are studied and discussed. A fact is certified that the distribution reduction is equivalent to the maximum distribution reduction in ordered information systems. Theorems on distribution reduction are implemented to create preparations for reduction acquisition and the dominance matrix is also restated to acquire distribution reductions in criterion based information systems. The matrix algorithm for distribution reduction acquisition is stepped and programmed. The algorithm can provide an approach and the program can be effective for theoretical research on knowledge reductions in criterion based inconsistent information systems. Dominance matrices are the only relied parameters which need to be considered without others such as approximations and subinformation systems being brought in. Furthermore, cases are employed to illustrate the validity of the matrix method and the program, which shows that the effectiveness of the algorithm in complicated information systems.



---

*Source: 307468-2014-08-28.xml*