# Parameterized Local Reduction of Decision Systems

Authors: Degang Chen; Yanyan Yang; Xiao Zhang
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

One important and valuable topic in rough sets is attribute reduction of a decision system. The existing attribute reductions are designed to just keep confidence of every certain rule as they cannot identify key conditional attributes explicitly for special decision rules. In this paper, we develop the concept ofθ-local reduction in order to offer a minimal description for special θ-possible decision rules. The approach of discernibility matrix is employed to investigate the structure of a θ-local reduction and compute all θ-local reductions. An example of medical diagnosis is employed to illustrate our idea of the θ-local reduction. Finally, numerical experiments are performed to show that our method proposed in this paper is feasible and valid.


---

## Body

## 1. Introduction

The concept of rough sets was originally proposed by Pawlak [1] as a mathematical approach to handle imprecision, vagueness, and uncertainty in data analysis. This theory has been demonstrated to have its usefulness and versatility in successfully solving a variety of problems [1]. The main application of rough set theory is attribute reduction in databases. Given a decision system with conditional and decision attributes, attribute reduction aims to find a subset of the original conditional attributes that contain the same information as the original one. The concept of attribute reduction can be viewed as the strongest and the most important result in rough set theory to distinguish itself from other theories.Along the line in [1], many research works have been concentrated on computing attribute reduction and developing other types of attribute reduction under the framework of rough sets [1–23]. For example, Skowron and Rauszer [12] employed the approach of discernibility matrix to set up mathematical foundation for finding reducts. Wang [15–17] characterized attribute reduction by information entropy. Possible rules and possible reduct of all decision classes were proposed to deal with inconsistence in an inconsistent decision table [4, 6]. In [5], in order to provide an underlying classification of knowledge reductions, five notions of knowledge reduction (possible reduct, approximation reduct, generalized decision reduct, μ-decision reduct, and μ-reduct) were investigated and compared in inconsistent systems. In fact, only two of them, possible reduct preserving upper approximations and μ-decision reduct preserving membership to all decision classes are essential because others are just equivalent to one of them, respectively. The notion of dynamic reducts was described in [2] as subsets of all reducts derived from both the original decision table and the majority of the randomly chosen decision subtables. In [10], α-reduct and α-relative reduct were proposed to allow occurrence of additional inconsistency that is controlled by means of the parameter α(α∈[0,1]). In [19] notions of the distribution reduct and maximum distribution reduction were proposed, and relationships among the maximum distribution reduct, the distribution reduct, and the possible reduct were discussed. In [3, 22], β-reduct was introduced to preserve the sum of objects in β-lower approximations of all decision classes (β∈(0.5,1.0]) based on variable precision rough sets (VPRS). However, Zhou et al. [24] pointed out that the dependency function may not be monotonic when computing β-reduct and decision rules derived by the β-reduct may be in conflict with those derived from the original system. To overcome this drawback, in [9] β-lower and β-upper distribution reducts were proposed to preserve β-lower approximations and β-upper approximations of all decision classes, respectively. It is proved that for some special thresholds, β-lower distribution reduct is equivalent to the maximum distribution reduct, whereas β-upper distribution reduct is equivalent to the possible reduct.These attribute reductions share the following two arguments. First they are developed in terms of all decision classes and cannot explicitly identify key conditional attributes for particular decision classes, so these reductions can be viewed as global reductions. However, in many practical problems people always pay more attention to some special decision classes rather than other ones, and condition attributes and decision rules with closed connection to these special decision classes always draw much attention. For example, in decision-making of medical diagnosis, key condition attributes related to the disease always draw much attention than other ones, and it is clearly meaningful to identify such key attributes. Second, as it is well known, certain and possible rules can be extracted from a decision system, and confidence of every certain rule is 1 while confidence of every possible rule is less than 1. But most of the existing attribute reductions only offer minimal conditional attributes to keep confidence of every certain rule invariant, and possible rules with bigger confidence are ignored. However, in most practical problems, possible rules with bigger confidence are always available and applied to decision making, so it is clearly meaningful to identify key conditional attributes for possible rules with bigger confidence.To improve these two arguments in the meantime, the definition ofθ-local reduction is presented in this paper. First we give the concept of θ-reduction (θ∈(0.5,1.0]) to keep the confidence of those possible rules,and then we further consider θ-local reduction to offer a minimal description and extract possible decision rules with bigger confidence for special decision classes. Approach of discernibility matrix is employed to characterize the structure of θ-local reduction. It is proven that the core of θ-reduction can be expressed as the union of the cores of θ-local reductions, and the discernibility matrix of θ-reduction can be obtained by composing discernibility matrices of θ-local reductions. An example of medical diagnosis is employed to illustrate our idea of θ-local reduction, and we also perform several experiments to demonstrate the effectiveness of the idea in this paper.The rest of this paper is structured as follows. In the next section we give some basic notions related to rough sets. In Section3 we define θ-local reduction, and approach of discernibility matrix is employed to find θ-local reduction. In Section 4, we perform numerical experiments to demonstrate that our method proposed in this paper is feasible to process massive data. We then conclude the paper in Section 5.


## 2. Basic Notions Related to Rough Sets

An information system is a pair(U,A), where U={x1,x2,…,xn} is a nonempty, finite set called the universe of discourse, and A={a1,a2,…,am} is a nonempty, finite set of attributes. With every subset of attributes B⊆A, we associate a binary relation IND(B), called a B-indiscernibility relation, and defined as IND(B)={(x,y)∈U×U:a(x)=a(y)foralla∈B}, then IND(B) is an equivalence relation and IND(B)=∩a∈BIND({a}). By [x]B, we denote the equivalence class of IND(B), including x. For X⊆U, sets {x∈X:[x]B⊆X} and {x∈X:[x]B∩X≠ϕ} are called B-lower and B-upper approximations of X in A and denoted as B_X and B¯X, respectively. If  B_X=B¯X, we say X is definable, otherwise it is indefinable.A decision table (DT) (sometimes called a decision system) is an information system(U,A∪D), where A∩D=ϕ, U/IND(D)={D1,D2,…,Dr}. A is a set of conditional attributes, while D is the decision attribute.SupposeA={a1,a2,…am}, then we have [x]A=∩i=1m[x]IND({ai}). If |Dl∩[x]A|≠ϕ, then for x∈Dl∩[x]A we can derive decision rule as (a1,a1(x))∧(a2,a2(x))∧⋯∧(am,am(x))→(D,D(x)). This rule can be denoted in terms of sets as [x]A→Dl and its confidence is computed as conf([x]A→Dl)=|Dl∩[x]A|/|[x]A|. Following we always call the decision rule of which confidence is not less than θ as θ-possible decision rule.


## 3.θ-Local Reduction of Decision Systems

In this section, we first introduce the definition ofθ-reduction as a global one to consider every θ-possible decision rule, and we then develop θ-local reduction as improvement of θ-reduction to address special θ-possible decision rules. Approach of discernibility matrix is employed to find θ-local reduction, and differences between θ-local reduction and β-reduct are explained.LetA*=(U,A∪D) be a decision system, U/IND(A)={M1,…,ML}, U/IND(D)={D1,…,Dr}, and DAθ(x)={Dl:conf([x]A→Dl)≥θ,l∈{1,…,r}},x∈U, θ∈(0.5,1.0]. If for any l∈{1,…,r}, conf([x]A→Dl)<θ, then DAθ(x)=∅. Obviously, DAθ(x) only includes a single element unless DAθ(x)=∅. For two θ-possible decision rules [x]A→Dl  and [y]A→Dl, if B⊆A satisfying [x]B=[y]B=[x]A∪[y]A, then clearly the rule [x]B→Dl is also a θ-possible decision rule, which implies DBθ(x)=DAθ(x), thus we have the definition of θ-reduction.Definition 3.1.
B
⊆
A is a θ-reduction of DT if and only if B is a minimal set such that DBθ(x)=DAθ(x) for  for all x∈U.Rule[x]B→Dl can be seemed as the reduced rule of the rule [x]A→Dl. A θ-reduction B is a set of conditional attributes that keeps confidence of every reduced rule of a θ-possible decision rule still not less than θ, since for any object xi satisfying conf([xi]A→Dl)≥θ, (l∈{1,…,r}), conf([xi]B→Dl)≥θ always holds. When θ=1, a θ-reduction is a classical attribute reduction which preserves lower approximations of all decision classes, namely, preserves confidences of all certain rules.θ-reduction is defined by considering all θ-possible decision rules; thus, it can be considered as a global one for the whole system. In many practical problems people always pay more attention to special θ-possible decision rules related to special decision classes, so we improve the θ-reduction to the θ-local reduction as following to capture key condition attributes for special decision rules.LetD(U,A)={X⊆U:A¯X=A_X}, that is, D(U,A) is the family of all definable sets related to  A. X is the set satisfying the following conditions: (1) X is a definable set, that is, X∈D(U,A); (2) every [x]A⊆X can derive a decision rule [x]A→Dl such that conf([x]A→Dl)≥θ. We denote the family of all these X satisfying the above two conditions as Qθ(U,A∪D). Clearly Qθ(U,A∪D) is a σ-algebra, and every element in Qθ(U,A∪D) is the union of several elements in {[x]A:conf([x]A→Dl)≥θ}, ∃l∈{1,…,r}.Definition 3.2.
SupposeA*=(U,A∪D) is a decision system, X={X1,…,XN} such that X⊆Qθ(U,A∪D). If X⊆Qθ(U,(A-{a})∪D),a∈A, then a is θ-dispensable in A for X, otherwise a is θ-indispensable in A for X. The collection of all the θ-indispensable elements in A is called the θ-local core of A* for X and denoted as CoreXθ(A∪D). We say that B⊆A is independent in A* for X if every attribute in B is θ-indispensable in B for X. A set B⊆A is called a θ-local reduction in A* for X if B is independent in A* for X and satisfying X⊆Qθ(U,B∪D), that is, B is the minimal subset of A keeping X⊆Qθ(U,B∪D).IfB is a θ-local reduction for X, then for every Xi∈X and x∈Xi, conf([x]A→Dl)≥θ implies conf([x]B→Dl)≥θ, that is, a θ-local reduction in A* for X keeps confidences of reduced rules of all θ-possible decision rules determined by elements in X not less than θ. Furthermore, for every x∈Xi we have DAθ(x)=DBθ(x), and ∪{DAθ(x):x∈Xi∈X} is just a group of decision classes, thus a θ-local reduction in A* for X aims to select key condition attributes for this group of decision classes rather than for all the decision classes. Let X={XA1,XA2,…,XAr} such that XAl=∪{[x]A:conf([x]A→Dl)≥θ}, l=1,…,r. If B is a θ-local reduction for X, then X⊆Qθ(U,B∪D), that is, XAl=XBl∈Qθ(U,B∪D) for l=1,…,r, thus DBθ(x)=DAθ(x) for every x∈U and B is a θ-reduction. This statement implies a θ-reduction is a special case of a θ-local reduction. The θ-reduction considers all θ-possible decision rules and decision classes, while θ-local reduction are developed in terms of special θ-possible decision rules and decision classes. Specially, for x∈U satisfying conf([x]A→Dl)≥θ, if X={[x]A}, then a θ-local reduction for X only considers one decision class Dl.Remark 3.3.
In [3, 22] β-reduct was developed to keep β-dependency function. It seems to have closed connection to θ-reduction in this paper. However, they are two different concepts. First, β-reduct is proposed in the framework of VPRS, while θ-reduction are developed within the framework of classical rough set and does not need new rough set model. Second, β-reduct was introduced to preserve the sum of objects in β-lower approximations of all decision classes, and θ-reduction aims to keep θ-lower approximation of every decision class. Third, β-reduct cannot keep confidence of reduced rules of some β-possible rules not less than β as pointed in [24], but a θ-reduction can avoid this drawback by keeping confidence of every θ-possible decision rule not less than θ. At last, in VPRS possible rules with bigger confidence are due to noise, when noise is ignored, these rules are believed as certain ones. However, if these kinds of possible rules are not due to noise but roughness, risk will be ignored when they are applied to practical problems as certain ones. Thus, β-reduct does not have the formulism to distinguish noise and roughness. Since θ-reduction still considers all possible rules as possible ones, it can handle either noise or uncertainty at the meantime. Since a θ-reduction is a special case of a θ-local reduction, thus it is obvious that a β-reduct and a θ-local reduction are certainly different. Furthermore, a θ-local reduction is proposed to capture key attributes for special decision classes, and a β-reduct cannot do this work since it has to consider all decision classes at the meantime. Following we first give an example to indicate that β-reduct and the θ-local reduction are really different.Example 3.4.
An inconsistent decision table is given as Table1.
Letβ=θ=0.6, {{c4},{c1,c3},{c3,c6},{c2,c5}} be the set of all 0.6-reducts, while {{c3,c4},{c1,c4,c5},{c2,c4,c5},{c4,c5,c6},{c2,c3,c5},{c1,c2,c5},{c2,c5,c6}} is the set of all 0.6-local reduction for X={X1={x1,x3},X2={x4,x5,x6,x7}}. Obviously, every 0.6-reduct is not a 0.6-local reduction, and every 0.6-local reduction is not a 0.6-reduct.Table 1
A decision table.
U
c
1
c
2
c
3
c
4
c
5
c
6
d
x
1
1
1
1
1
1
1
M
x
2
1
0
1
0
1
1
M
x
3
0
0
1
1
0
0
M
x
4
1
1
1
0
0
1
F
x
5
1
0
1
0
1
1
F
x
6
0
0
0
1
1
0
F
x
7
1
0
1
0
1
1
FFollowing we study the properties of theθ-local reduction. The set of all θ-local reductions in A* for X is denoted by RedXθ(A∪D), and we have the following theorem.Theorem 3.5.
Core
X
θ
(
A
∪
D
)
=
∩
Red
X
θ
(
A
∪
D
).Proof.
(1) For anya∈CoreXθ(A∪D), X⊄Qθ(U,(A-{a})∪D) holds. Suppose a∉∩RedXθ(A∪D), then there exists a θ-local reduction B for X s.t. B⊆A-{a}, such that X⊆Qθ(U,B∪D)⊆Qθ(U,(A-{a})∪D)⊆Qθ(U,A∪D), we get contradiction, hence a∈∩RedXθ(A∪D), namely CoreXθ(A∪D)⊆∩RedXθ(A∪D).
(2) For anya∈∩RedXθ(A∪D), suppose a∉CoreXθ(A∪D), then X⊆Qθ(U,(A-{a})∪D), therefore there exists a θ-local reduction B for X s.t. B⊆A-{a}, then a∉B, thus a∉∩RedXθ(A∪D), we get contradiction, hence a∈CoreXθ(A∪D), namely, ∩RedXθ(A∪D)⊆CoreXθ(A∪D). From (1), (2), we can prove Theorem 3.5.
According to Theorem3.5  θ-local core can be employed as the basis of finding all θ-local reductions for X since it is included in all θ-local reductions for X.
If elements inX={X1,…,XN} have nonempty overlaps, then there exists a X′ satisfying elements in X′ have empty overlaps and RedXθ(A∪D)=RedX′θ(A∪D). We only prove this statement when X={X1,X2}.Theorem 3.6.
SupposeX={X1,X2},X1∩X2≠ϕ, and X′={X1∩X2,X1-X2,X2-X1}, then RedXθ(A∪D)=RedX′θ(A∪D).Proof.
For anyB⊆A, X⊂Qθ(U,B∪D)⇔X′⊂Qθ(U,B∪D), thus we finish the proof.Following we always assume elements inX={X1,…,XN} have empty overlaps. We have the following theorem for the θ-local core.Theorem 3.7.
X
=
{
X
1
,
…
,
X
N
} and DAθ(x)={Dl:l≤r} for any x∈Xi(i=1,…,N), Xi∩Xj=ϕ, then we have CoreXθ(A∪D)=∪i=1NCore{Xi}θ(A∪D).Proof.
For anya∈CoreXθ(A∪D)⇔ there exists Xi satisfying Xi∉Qθ(U,(A-{a})∪D)⇔a∈Core{Xi}θ(A∪D)⇔a∈∪i=1NCore{Xi}θ(A∪D).
WhenX={XA1,…,XAr}, XAl=∪{[x]A:conf([x]A→Dl)≥θ}, l=1,…,r, a θ-local reduction for X is a θ-reduction. Thus, we get the core of θ-reduction can be expressed as the union of the cores of θ-local reductions for {XAl}(l=1,…,r). From Theorem 3.7 we can imply elements in the θ-local core for X are indispensable for certain group of decision classes. If we pay more attention to a special group of decision classes, then the θ-local reduction may offer less conditional attributes only being indispensable for them. This is the objective of θ-local reductions. Following we study the computing of θ-local reductions.Definition 3.8.
Let(U,A∪D) be a DT, U/IND(A)={M1,…,ML}, X={X1,…,XN}, and X⊆Qθ(U,A∪D). Denoted by ak(Mi) as the value of samples in Mi in terms of ak. Define
(3.1)Cij={{ak∈A:ak(Mi)≠ak(Mj)},(Mi∪Mj)⊄Xh,(Mi∪Mj)∩Xh≠φ,∃h∈{1,…,N}ϕ,otherwise
then MXθ(U,A∪D)=(Cij)L×L is called the θ-local discernibility matrix for X.From the definition ofθ-local discernibility matrix for X we can easily get MXθ(U,A∪D)=∪i=1NM{Xi}θ(U,A∪D), namely, MXθ(U,A∪D) can be expressed as the union of M{Xi}θ(U,A∪D). If X={XA1,…,XAr}, and XAl=∪{[x]A:conf([x]A→Dl)≥θ}, l=1,…,r, then the discernibility matrix for X can be obtained by composing discernibility matrices for {XAl}(l=1,…,r).Theorem 3.9.
M
X
θ
(
U
,
A
∪
D
)
=
(
C
i
j
)
L
×
L satisfies the following properties.(1)
It is a symmetric matrix, that is,Cij=Cji,foralli,j≤L.(2)
Cij=ϕ if Mi∪Mj⊆Xh or Mi∪Mj⊆(U-Xh) holds, specially Cii=ϕ, foralli,j≤L.The proofs of following two theorems are straightforward.Theorem 3.10.
Core
X
θ
(
A
∪
D
)
=
{
a
∈
A
:
C
i
j
=
{
a
}
,
i
,
j
≤
L
}.Theorem 3.11.
B
⊆
A includes a θ-local reduction for X if and only if B∩Cij≠ϕ for Cij≠ϕ.By Theorem3.10 the θ-local core is the set of single element of the θ-local discernibility matrix, thus, we can get CoreXθ(A∪D) from the θ-local discernibility matrix directly.Definition 3.12.
Let(U,A∪D) be a DT. A Boolean function is denoted by fXθ(U,A∪D)=∧(∨Cij), Cij≠ϕ, then fXθ(U,A∪D) is referred to the θ-local discernibility function for X.
LetgXθ(U,A∪D) be the reduced disjunctive form of fXθ(U,A∪D) by applying the distribution and absorption laws as many times as possible. Then there exist t and Ai⊆A for i=1,…,t such that gXθ(U,A∪D)=(∧A1)∨⋯∨(∧At), thus, we have the following theorem.Theorem 3.13.
Red
X
θ
(
A
∪
D
)
=
{
A
1
,
…
,
A
t
}.The proof of Theorem3.13 is similar to the one for traditional rough sets in [12].Following we employ an example to illustrate the idea ofθ-local reduction in this paper.Example 3.14.
When one suffers from a disease, certain symptoms can be observed. The doctor observes patients’ symptoms and signs to implement diagnosis. In the following decision table (as Table2 shown), ten patients’ symptoms were observed and recorded. We would like to know which symptom is closely related to the influenza
(3.2)U/IND(A)={{x1},{x2},{x3},{x4,x5,x6},{x7},{x8,x9},{x10}},U/IND(D)={D1={x1,x2,x4,x5,x7,x8},D2={x3,x6,x9,x10}}.
Letθ=0.6 and X={X1={x1,x2,x4,x5,x6,x7},X2={x3,x10}}, then DA0.6(x)={D1} for any x∈X1 and DA0.6(x)={D2} for any x∈X2. Thus, θ-local discernibility matrices for {X1},{X2} and X are as follows respectively:
(3.3)(ϕϕϕ{a,c}{a}ϕϕϕ{b,c}ϕϕϕ{c}ϕϕ{a,b}{a,b,c}ϕ{a}{a,b}ϕ{a}{a,c}ϕ{a,b}{a}ϕϕ),(ϕϕϕ{a,c}{a}ϕϕϕ{b,c}ϕϕϕ{c}ϕϕϕϕ{a,b,c}ϕϕϕ{a}{a,c}ϕ{a,b}{a}{b}ϕ),(ϕϕϕ{a,c}{a}ϕϕϕ{b,c}ϕϕϕ{c}ϕϕ{a,b}{a,b,c}{a,b,c}{a}{a,b}ϕ{a}{a,c}ϕ{a,b}{a}{b}ϕ).
Clearly everyCij in MXθ(U,A∪D) is the union of the corresponding elements in M{X1}0.6(U,A∪D) and M{X2}0.6(U,A∪D). Because of X={X1,X2}={XA1,XA2},XAl=∪{[x]A:conf([x]A→Dl)≥0.6,l=1,2.}, a θ-local reduction for X is a θ-reduction, in other words, the discernibility matrix of θ-reduction can be obtained by composing discernibility matrices of θ-local reductions. We can easily get the corresponding θ-local reduction for {X1} is Red{X1}0.6(A∪D)={{a,c}} and Core{X1}0.6(A∪D)={a,c}. Similarly, Red{X2}0.6(A∪D)={{a,b,c}}Core{X2}0.6(A∪D)={a,b,c} and RedX0.6(A∪D)={{a,b,c}}, CoreX0.6(A∪D)={a,b,c}.
If we pay much more attention to influenza than others, that is, we concentrate on the decision class with the value 1. Then the 0.6-local reduction{a,c} can be employed by doctor to judge whether a patient is with influenza. However, {a,b,c} is a 0.6-reduction and cannot explicitly identify key conditional attributes for particular decision class. On the other hand, a θ-local reduction keeps confidence of important θ-possible decision rules extracted from special decision classes not less than θ. For instance, we have the following  0.6-possible decision rules and their reduced ones related to D1.
The original 0.6-possible decision rules related toD1 are as follows:(i)
(a,1)∧(b,1)∧(c,1)→(d,1),conf(i)=1.(ii)
(a,1)∧(b,1)∧(c,0)→(d,1),conf(ii)=1.(iii)
(a,2)∧(b,0)∧(c,1)→(d,1),conf(iii)=2/3.(iv)
(a,2)∧(b,1)∧(c,1)→(d,1),conf(iv)=1.
The reduced rules are as follows:(α1)
(a,1)∧(c,1)→(d,1),conf(α1)=1.(α2)
(a,1)∧(c,0)→(d,1),conf(α2)=1.(α3)
(a,2)∧(c,1)→(d,1),conf(α3)=3/4.
From the above we know that aθ-local reduction keeps confidence of 0.6-possible decision rules for decision class D1. Thus, a θ-local reduction could explicitly identify key conditional attributes for particular decision classes and keeps confidence of θ-possible decision rules in terms of these decision classes not less than θ. Therefore, θ-local reduction can be selected as an effective method to deal with massive data.Table 2
The original decision table of patients’ symptoms.
U
A
Body Temperature
Dry cough
Headache
Influenza
conf
(
[
x
i
]
A
→
D
l
)
a
b
c
d
1
1
1
1
1
1
2
1
1
0
1
1
3
2
1
0
0
1
4
2
0
1
1
2
/
3
5
2
0
1
1
2
/
3
6
2
0
1
0
1
/
3
7
2
1
1
1
1
8
3
0
1
1
1
/
2
9
3
0
1
0
1
/
2
10
3
1
1
0
1
Note: in the table, body temperaturea: 1 means high, 2 means slightly higher, and 3 means normal; for dry cough b, headache c, influenza d: 1 means yes and 0 means no.


## 4. Algorithm to Find Oneθ-Local Reduction and Numerical Experiments

In this section, we develop an algorithm to find aθ-local reduction. Then we perform numerical experiments for massive data sets to demonstrate that we can reduce the number of condition attributes and keep classification accuracies of raw data with θ-local reduction, which initially implies that the method proposed in this paper is feasible to process massive data.


### 4.1. Algorithm to Find Oneθ-Local Reduction

In the subsection, we develop an algorithm (Heuristic) to find oneθ-local reduction by the approach of discernibility matrix proposed in Section 3.Algorithm 4.1.
To find oneθ-local reduction for XAl of a certain decision class the following should be carried out:Input:U,A,D,θ,XAl.Output: Oneθ-local reduction RedXAlθ(A∪D).Initialize:RedXAlθ(A∪D)=∅.Step 1: ComputeCij by Definition 3.8.Step 2: ComputeCoreXAlθ(A∪D)={a:Cij={a}}; and delete those Cij with nonempty overlap with CoreXAlθ(A∪D).Step 3: LetRedXAlθ(A∪D)=CoreXAlθ(A∪D).Step 4: Add the elementa whose frequency of occurrence is maximum in all Cij into RedXAlθ(A∪D); and delete those Cij with nonempty overlap with RedXAlθ(A∪D).Step 5: If there still exist someCij≠∅, go to Step 4; otherwise, go to Step 6.Step 6: IfRedXAlθ(A∪D) is not independent, delete the redundant elements in RedXAlθ(A∪D).Step 7: OutputRedXAlθ(A∪D).The computational complexity of this algorithm isO(|U|2×|A|). Here |U| is the size of universe, |A| is the number of condition attributes.


### 4.2. Numerical Experiments

In this subsection, we perform experiments to demonstrate that withθ-local reduction and θ-reduction, condition attributes of a massive data set can be reduced with a satisfied parameter θ. We also employ support vector machine (SVM) as a classifier to compare the classification accuracies of reduced and raw data sets. The experiments are set up as follows.


#### 4.2.1. Experimental Setup

Dataset
Six datasets from University of California, Irvine (UCI) Machine Learning Repository [25] are used (see Table 3).Table 3
Data sets description.
Datasets
Sample
Data type
Condition attributes
Decision classes
Breast Tissue
106
Real number
9
4
Credit Approval
653
Mix number
15
2
Ionosphere
351
Real number
34
2
Spect
267
Symbolic number
22
2
Wdbc
569
Real number
31
2
Wine
178
Real number
13
3Classifier
SVM in SVM-KM MATLAB Toolbox is employed as the classifier.Dataset Split
In the process of classification, 10-fold cross-validation is applied on the six datasets.Dataset Discretization
The fuzzy C-mean method proposed in [26] is used to discretize real valued condition attributes.Indices
They are (1) the number of selected attributes in the reduct, (2) classification accuracy of the reduct.Parameter Specification
From confidences of all decision rules, we randomly choose a confidence which is greater than 0.5 as our experimental parameter on a specific dataset.Accuracy
The accuracy in this paper is calculated byA/B, while A is the number of samples classified correctly in a certain decision class, and B is the number of samples in this decision class.First Table4 shows the detailed comparison of condition attributes in θ-local reduction and θ-reduction. Clearly θ-local reductions are different to θ-reductions. In most cases, θ-local reduction is subset of a certain θ-reduction. That is to say, the number of condition attributes in the θ-local reduction is often smaller than the one in the θ-reduction.Table 4
The comparisons on selected attributes betweenθ-local reduction and θ-reduction.
Class 1
Class 2
Class3
Class 4
Parameter
Breast tissue
0.6667
θ-local reduction
1, 6
1, 2, 3
4, 9
4, 6, 7, 9
θ-reduction
1, 6, 2, 3, 7, 8, 9
1,  2, 3,  6, 7, 8, 9
4, 9, 2, 3, 6, 7
4, 6, 7, 9, 2, 3
Wdbc
0.8333
θ-local reduction
1, 2, 4, 6, 7, 9, 11, 12, 14, 15, 22, 25, 27, 28, 29
1, 2, 7, 9, 10, 11, 12, 15, 19, 22, 23, 25, 27, 28, 29
θ-reduction
1, 2, 4, 6, 7, 9, 11, 12, 14, 15, 22, 25,  27, 28, 29
1, 2, 7, 9, 10, 11, 12, 15, 19, 22, 23, 25, 27, 28, 29, 30
Spect
0.8636
θ-local reduction
1, 2, 3, 4, 5, 9, 11, 12, 13, 14, 15, 17, 18, 20, 21, 22
1, 2, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 22
θ-reduction
1, 2, 3, 4, 5, 7, 8, 9, 11, 12, 13, 14, 15, 17, 18, 20, 21, 22
1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20,  21, 22Next, Table5 shows that though the average accuracy on θ-local reduction (i.e., 0.79466) is a little lower than average accuracy on raw data (i.e., 0.8147333), and much higher than average accuracy on θ-reduction (i.e., 0.75170666). This fact reveals that compared with θ-reduction and raw data, θ-local reduction can keep classification accuracy within a small perturbation. It is also easy to see from Table 5 that the number of attributes in the θ-local reduction (10.33333) is obviously less than the one in θ-reduction (12.066666) and far less than the one of raw data (20.66666). In particular for the dataset “BreastTissue,” the number of attributes in the θ-local reduction is far less than the one in the θ-reduction and raw data set on every decision class.Table 5
Comparison betweenθ-local reduction and θ-reduction.
Accuracy
Raw data
Number of selected attributes
Raw data
Parameter
θ-local-reduction
θ-reduction
θ-local-reduction
θ-reduction
Breast tissue
0.6415
9
0.6667
Class 1
0.6132
0.6151
2
6
Class 2
0.6208
0.6038
3
6
Class 3
0.5717
0.6528
2
6
Class 4
0.6472
0.6038
4
6
Wine
0.9640
13
0.75
Class 1
0.9685
0.9719
8
9
Class 2
0.9730
0.9652
9
10
Class 3
0.9337
0.9663
8
9
Credit approval
0.8071
15
0.8125
Class 1
0.8224
0.7994
14
15
Class 2
0.8009
0.7995
13
14
Ionosphere
0.8889
34
0.8750
Class 1
0.9090
0.9089
14
15
Class 2
0.8917
0.9032
16
17
Spect
0.6590
22
0.8636
Class 1
0.6932
0.6511
15
17
Class 2
0.6170
0.6510
17
18
Wdbc
0.9279
31
0.8333
Class 1
0.9297
0.9122
15
17
Class 2
0.9279
0.9225
15
16
Average
0.79466
0.75170666
0.8147333
10.33333
12.066666
20.66666These results initially imply that idea ofθ-local reduction is effective to deal with some massive data. However, we select different parameter θ for different data set, and how to select a suitable parameter for certain data set is a complex problem. We omit detailed discussion on this topic in this paper.


## 4.1. Algorithm to Find Oneθ-Local Reduction

In the subsection, we develop an algorithm (Heuristic) to find oneθ-local reduction by the approach of discernibility matrix proposed in Section 3.Algorithm 4.1.
To find oneθ-local reduction for XAl of a certain decision class the following should be carried out:Input:U,A,D,θ,XAl.Output: Oneθ-local reduction RedXAlθ(A∪D).Initialize:RedXAlθ(A∪D)=∅.Step 1: ComputeCij by Definition 3.8.Step 2: ComputeCoreXAlθ(A∪D)={a:Cij={a}}; and delete those Cij with nonempty overlap with CoreXAlθ(A∪D).Step 3: LetRedXAlθ(A∪D)=CoreXAlθ(A∪D).Step 4: Add the elementa whose frequency of occurrence is maximum in all Cij into RedXAlθ(A∪D); and delete those Cij with nonempty overlap with RedXAlθ(A∪D).Step 5: If there still exist someCij≠∅, go to Step 4; otherwise, go to Step 6.Step 6: IfRedXAlθ(A∪D) is not independent, delete the redundant elements in RedXAlθ(A∪D).Step 7: OutputRedXAlθ(A∪D).The computational complexity of this algorithm isO(|U|2×|A|). Here |U| is the size of universe, |A| is the number of condition attributes.


## 4.2. Numerical Experiments

In this subsection, we perform experiments to demonstrate that withθ-local reduction and θ-reduction, condition attributes of a massive data set can be reduced with a satisfied parameter θ. We also employ support vector machine (SVM) as a classifier to compare the classification accuracies of reduced and raw data sets. The experiments are set up as follows.


### 4.2.1. Experimental Setup

Dataset
Six datasets from University of California, Irvine (UCI) Machine Learning Repository [25] are used (see Table 3).Table 3
Data sets description.
Datasets
Sample
Data type
Condition attributes
Decision classes
Breast Tissue
106
Real number
9
4
Credit Approval
653
Mix number
15
2
Ionosphere
351
Real number
34
2
Spect
267
Symbolic number
22
2
Wdbc
569
Real number
31
2
Wine
178
Real number
13
3Classifier
SVM in SVM-KM MATLAB Toolbox is employed as the classifier.Dataset Split
In the process of classification, 10-fold cross-validation is applied on the six datasets.Dataset Discretization
The fuzzy C-mean method proposed in [26] is used to discretize real valued condition attributes.Indices
They are (1) the number of selected attributes in the reduct, (2) classification accuracy of the reduct.Parameter Specification
From confidences of all decision rules, we randomly choose a confidence which is greater than 0.5 as our experimental parameter on a specific dataset.Accuracy
The accuracy in this paper is calculated byA/B, while A is the number of samples classified correctly in a certain decision class, and B is the number of samples in this decision class.First Table4 shows the detailed comparison of condition attributes in θ-local reduction and θ-reduction. Clearly θ-local reductions are different to θ-reductions. In most cases, θ-local reduction is subset of a certain θ-reduction. That is to say, the number of condition attributes in the θ-local reduction is often smaller than the one in the θ-reduction.Table 4
The comparisons on selected attributes betweenθ-local reduction and θ-reduction.
Class 1
Class 2
Class3
Class 4
Parameter
Breast tissue
0.6667
θ-local reduction
1, 6
1, 2, 3
4, 9
4, 6, 7, 9
θ-reduction
1, 6, 2, 3, 7, 8, 9
1,  2, 3,  6, 7, 8, 9
4, 9, 2, 3, 6, 7
4, 6, 7, 9, 2, 3
Wdbc
0.8333
θ-local reduction
1, 2, 4, 6, 7, 9, 11, 12, 14, 15, 22, 25, 27, 28, 29
1, 2, 7, 9, 10, 11, 12, 15, 19, 22, 23, 25, 27, 28, 29
θ-reduction
1, 2, 4, 6, 7, 9, 11, 12, 14, 15, 22, 25,  27, 28, 29
1, 2, 7, 9, 10, 11, 12, 15, 19, 22, 23, 25, 27, 28, 29, 30
Spect
0.8636
θ-local reduction
1, 2, 3, 4, 5, 9, 11, 12, 13, 14, 15, 17, 18, 20, 21, 22
1, 2, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 22
θ-reduction
1, 2, 3, 4, 5, 7, 8, 9, 11, 12, 13, 14, 15, 17, 18, 20, 21, 22
1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20,  21, 22Next, Table5 shows that though the average accuracy on θ-local reduction (i.e., 0.79466) is a little lower than average accuracy on raw data (i.e., 0.8147333), and much higher than average accuracy on θ-reduction (i.e., 0.75170666). This fact reveals that compared with θ-reduction and raw data, θ-local reduction can keep classification accuracy within a small perturbation. It is also easy to see from Table 5 that the number of attributes in the θ-local reduction (10.33333) is obviously less than the one in θ-reduction (12.066666) and far less than the one of raw data (20.66666). In particular for the dataset “BreastTissue,” the number of attributes in the θ-local reduction is far less than the one in the θ-reduction and raw data set on every decision class.Table 5
Comparison betweenθ-local reduction and θ-reduction.
Accuracy
Raw data
Number of selected attributes
Raw data
Parameter
θ-local-reduction
θ-reduction
θ-local-reduction
θ-reduction
Breast tissue
0.6415
9
0.6667
Class 1
0.6132
0.6151
2
6
Class 2
0.6208
0.6038
3
6
Class 3
0.5717
0.6528
2
6
Class 4
0.6472
0.6038
4
6
Wine
0.9640
13
0.75
Class 1
0.9685
0.9719
8
9
Class 2
0.9730
0.9652
9
10
Class 3
0.9337
0.9663
8
9
Credit approval
0.8071
15
0.8125
Class 1
0.8224
0.7994
14
15
Class 2
0.8009
0.7995
13
14
Ionosphere
0.8889
34
0.8750
Class 1
0.9090
0.9089
14
15
Class 2
0.8917
0.9032
16
17
Spect
0.6590
22
0.8636
Class 1
0.6932
0.6511
15
17
Class 2
0.6170
0.6510
17
18
Wdbc
0.9279
31
0.8333
Class 1
0.9297
0.9122
15
17
Class 2
0.9279
0.9225
15
16
Average
0.79466
0.75170666
0.8147333
10.33333
12.066666
20.66666These results initially imply that idea ofθ-local reduction is effective to deal with some massive data. However, we select different parameter θ for different data set, and how to select a suitable parameter for certain data set is a complex problem. We omit detailed discussion on this topic in this paper.


## 4.2.1. Experimental Setup

Dataset
Six datasets from University of California, Irvine (UCI) Machine Learning Repository [25] are used (see Table 3).Table 3
Data sets description.
Datasets
Sample
Data type
Condition attributes
Decision classes
Breast Tissue
106
Real number
9
4
Credit Approval
653
Mix number
15
2
Ionosphere
351
Real number
34
2
Spect
267
Symbolic number
22
2
Wdbc
569
Real number
31
2
Wine
178
Real number
13
3Classifier
SVM in SVM-KM MATLAB Toolbox is employed as the classifier.Dataset Split
In the process of classification, 10-fold cross-validation is applied on the six datasets.Dataset Discretization
The fuzzy C-mean method proposed in [26] is used to discretize real valued condition attributes.Indices
They are (1) the number of selected attributes in the reduct, (2) classification accuracy of the reduct.Parameter Specification
From confidences of all decision rules, we randomly choose a confidence which is greater than 0.5 as our experimental parameter on a specific dataset.Accuracy
The accuracy in this paper is calculated byA/B, while A is the number of samples classified correctly in a certain decision class, and B is the number of samples in this decision class.First Table4 shows the detailed comparison of condition attributes in θ-local reduction and θ-reduction. Clearly θ-local reductions are different to θ-reductions. In most cases, θ-local reduction is subset of a certain θ-reduction. That is to say, the number of condition attributes in the θ-local reduction is often smaller than the one in the θ-reduction.Table 4
The comparisons on selected attributes betweenθ-local reduction and θ-reduction.
Class 1
Class 2
Class3
Class 4
Parameter
Breast tissue
0.6667
θ-local reduction
1, 6
1, 2, 3
4, 9
4, 6, 7, 9
θ-reduction
1, 6, 2, 3, 7, 8, 9
1,  2, 3,  6, 7, 8, 9
4, 9, 2, 3, 6, 7
4, 6, 7, 9, 2, 3
Wdbc
0.8333
θ-local reduction
1, 2, 4, 6, 7, 9, 11, 12, 14, 15, 22, 25, 27, 28, 29
1, 2, 7, 9, 10, 11, 12, 15, 19, 22, 23, 25, 27, 28, 29
θ-reduction
1, 2, 4, 6, 7, 9, 11, 12, 14, 15, 22, 25,  27, 28, 29
1, 2, 7, 9, 10, 11, 12, 15, 19, 22, 23, 25, 27, 28, 29, 30
Spect
0.8636
θ-local reduction
1, 2, 3, 4, 5, 9, 11, 12, 13, 14, 15, 17, 18, 20, 21, 22
1, 2, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 22
θ-reduction
1, 2, 3, 4, 5, 7, 8, 9, 11, 12, 13, 14, 15, 17, 18, 20, 21, 22
1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20,  21, 22Next, Table5 shows that though the average accuracy on θ-local reduction (i.e., 0.79466) is a little lower than average accuracy on raw data (i.e., 0.8147333), and much higher than average accuracy on θ-reduction (i.e., 0.75170666). This fact reveals that compared with θ-reduction and raw data, θ-local reduction can keep classification accuracy within a small perturbation. It is also easy to see from Table 5 that the number of attributes in the θ-local reduction (10.33333) is obviously less than the one in θ-reduction (12.066666) and far less than the one of raw data (20.66666). In particular for the dataset “BreastTissue,” the number of attributes in the θ-local reduction is far less than the one in the θ-reduction and raw data set on every decision class.Table 5
Comparison betweenθ-local reduction and θ-reduction.
Accuracy
Raw data
Number of selected attributes
Raw data
Parameter
θ-local-reduction
θ-reduction
θ-local-reduction
θ-reduction
Breast tissue
0.6415
9
0.6667
Class 1
0.6132
0.6151
2
6
Class 2
0.6208
0.6038
3
6
Class 3
0.5717
0.6528
2
6
Class 4
0.6472
0.6038
4
6
Wine
0.9640
13
0.75
Class 1
0.9685
0.9719
8
9
Class 2
0.9730
0.9652
9
10
Class 3
0.9337
0.9663
8
9
Credit approval
0.8071
15
0.8125
Class 1
0.8224
0.7994
14
15
Class 2
0.8009
0.7995
13
14
Ionosphere
0.8889
34
0.8750
Class 1
0.9090
0.9089
14
15
Class 2
0.8917
0.9032
16
17
Spect
0.6590
22
0.8636
Class 1
0.6932
0.6511
15
17
Class 2
0.6170
0.6510
17
18
Wdbc
0.9279
31
0.8333
Class 1
0.9297
0.9122
15
17
Class 2
0.9279
0.9225
15
16
Average
0.79466
0.75170666
0.8147333
10.33333
12.066666
20.66666These results initially imply that idea ofθ-local reduction is effective to deal with some massive data. However, we select different parameter θ for different data set, and how to select a suitable parameter for certain data set is a complex problem. We omit detailed discussion on this topic in this paper.


## 5. Conclusion

Attribute reduction is a key topic in rough set theory. And the existing methods of attribute reduction ignore possible rules and cannot capture key condition attribute for special decision classes. In this paper, we develop the concept ofθ-local reduction, by which possible rules with larger confidence are considered and key conditional attributes related to some special decision classes can be selected. Approach of discernibility matrix is employed to find θ-local reductions. Experiments are performed to demonstrate the effectiveness of the idea of θ-local reduction in this paper.



---

*Source: 857590-2012-11-18.xml*