# Knowledge Reduction Based on Divide and Conquer Method in Rough Set Theory

Authors: Feng Hu; Guoyin Wang
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

The divide and conquer method is a typical granular computing method using multiple levels of abstraction and granulations. So far, although some achievements based on divided and conquer method in the rough set theory have been acquired, the systematic methods for knowledge reduction based on divide and conquer method are still absent. In this paper, the knowledge reduction approaches based on divide and conquer method, under equivalence relation and under tolerance relation, are presented, respectively. After that, a systematic approach, named as the abstract process for knowledge reduction based on divide and conquer method in rough set theory, is proposed. Based on the presented approach, two algorithms for knowledge reduction, including an algorithm for attribute reduction and an algorithm for attribute value reduction, are presented. Some experimental evaluations are done to test the methods on uci data sets and KDDCUP99 data sets. The experimental results illustrate that the proposed approaches are efficient to process large data sets with good recognition rate, compared with KNN, SVM, C4.5, Naive Bayes, and CART.


---

## Body

## 1. Introduction

In the search for new paradigms of computing, there is a recent surge of interest, under the name of granular computing [1–3], in computations using multiple levels of abstraction and granulation. To a large extent, the majority of existing studies include rough sets, fuzzy sets, cluster analysis, and classical divide and conquer methods [4, 5] and aim at solving specific problems [6].Rough set (RS) [7–10] is a valid mathematical theory for dealing with imprecise, uncertain, and vague information. It has been applied in such fields as machine learning, data mining, intelligent data analysis, and control algorithm acquiring, successfully since it was proposed by Pawlak and Skowron in 2007 [10]. Knowledge reduction is one of the most important contributions of rough set theory to machine learning, pattern recognition, and data mining. Although the problem of finding a minimal reduction of a given information system was proven to be an NP-hard problem [8], many promising heuristics have been developed that are promising. A variety of methods for knowledge reduction and their applications can be found in [2, 7–43]. Among these existing methods, one group method focuses on the indiscernibility relation in a universe that captures the equivalence of objects, while the other group considers the discernibility relation that explores the differences of objects [42]. For indiscernibility relation, one can employ it to induce a partition of the universe and thereby to construct positive regions whose objects can be undoubtedly classified into a certain class with respect to the selected attributes. Thus, knowledge reduction algorithms based on positive regions have been proposed in [8, 10, 15, 16, 21, 28, 30]. For discernibility relation, we have knowledge reduction algorithms based on a discernibility matrix and information entropy. Reduction methods based on discernibility matrix [34] have high cost of storage with space complexity O(m×n2) for a large decision table with n objects and m conditional attributes. Thus, storing and deleting the element cells in a discernibility matrix is a time-consuming process. Many researchers have studied discernibility matrix construction and contributed to a lot [10, 18, 28, 35, 38, 39, 43]. As well, knowledge reduction algorithms based on information entropy [20, 37, 42] have been developed. Although so many algorithms have been developed, it is valuable to study some new high efficient algorithms.Divide and conquer method is a simple granular computing method. When the algorithms are designed by divide and conquer method, the decision table can be divided into many subdecision tables recursively in attribute space. That's to say, an original big data set can be divided into many small ones. If the small ones can be processed one by one, instead the original big one is processed on a whole, it will save a lot time. Thus, it may be an effective way to process large data set. The divide and conquer method consists of three vital stages.Stage 1.
Divide the big original problem into many independent subproblems with the same structure.Stage 2.
Conquer the sub-problems recursively.Stage 3.
Merge the solutions of sub-problems into the one of original problem.So far, some good results for knowledge reduction based on divide and conquer method have been achieved, such as the computation of the attribute core and the computation of attribute reduction under given attribute order [12, 13]. Besides, decision tree-based methods [26, 27, 44] have been studied and are very popular. In fact, the construction of decision tree is a special case of divide and conquer method, because it can be generated from top to down recursively. In the methods based on decision tree, a tree should be constructed by using decomposition at first. It costs more in the first stage, which is convenient to the following stages, and costs less in the following two ones.However, the systematic method for knowledge reduction based on divide and conquer method is still absent, especially “how to keep invariance between the solution of original problem and the ones of sub-problems.” It results in the difficulty to design the high efficient algorithms for knowledge reduction based on divide and conquer method. Therefore, it is urgent to discuss the knowledge reduction method based on divide and conquer methods systematically and overall.Contributions of this work are (1) some principles for “keeping invariance between the solution of original problem and the ones of sub-problems” are concluded. Then, the abstract process for knowledge reduction based on divide and conquer method in the rough set theory is presented, which is helpful to design high efficient algorithm based on divide and conquer method. (2) Fast approaches for knowledge reduction based on divide and conquer method, including an algorithm for attribute reduction and an algorithm for attribute value reduction, are proposed. Experimental evaluations show that the presented methods are efficient.The remainder of this paper is organized as follows. The basic theory and methods dealing with the application of rough set theory in data mining are presented in Section2. Section 3 introduces the abstract process for knowledge reduction based on divide and conquer method in the rough set theory. A quick algorithm based on divide and conquer method for attribute reduction is presented in Section 4. In Section 5, a fast algorithm for attribute value reduction using divide and conquer method is proposed. Some simulation experimental evaluations are discussed to show the performance of the developed methods in Section 6. The paper ends with conclusion in Section 7.


## 2. Preliminaries

Rough set theory was introduced by Pawlak as a tool for concept approximation relative to uncertainty. Basically, the idea is to approximate a concept by three description sets, namely, the lower approximation, upper approximation, and boundary region. The approximation process begins by partitioning a given set of objects into equivalence classes called blocks, where the objects in each block are indiscernible from each other relative to their attribute values. The approximation and boundary region sets are derived from the blocks of a partition of the available objects. The boundary region is constituted by the difference between the lower approximation and upper approximation and provides a basis for measuring the “roughness” of an approximation. Central to the philosophy of the rough set approach to concept approximation is the minimization of the boundary region [28].For the convenience of description, some basic notions of decision tables are introduced here at first.Definition 2.1 (decision table [36]).
A decision table is defined asS=〈U,A,V,f〉, where U is a non-empty finite set of objects, called the universe, A is a nonempty finite set of attributes, A=C∪D, where C is the set of conditional attributes, and D is the set of decision attributes, D≠ϕ. For any attribute a∈A, Va denotes the domain of attribute a. Each attribute determines a mapping function f:U×A→V.Definition 2.2 (indiscernibility relation [36]).
Given a decision tableS=〈U,A,V,f〉, each subset of attribute B⊆A determines an indiscernibility relation IND(B) as follows: IND(B)={(x,y)∣(x,y)∈U×U,∀b∈B(b(x)=b(y))}.Definition 2.3 (lower approximation and upper approximation [36]).
Given a decision tableS=〈U,A,V,f〉, for any subset X⊆U and indiscernibility relation IND(B), the B lower approximation and upper approximation of X are defined as B-(X)=⋃Yi∈U/IND(B)∧Yi⊆XYi, B-(X)=⋃Yi∈U/IND(B)∧Yi∩X≠ϕYi.Definition 2.4 (positive region [36]).
Given a decision tableS=〈U,A,V,f〉, P⊆A, and Q⊆A, the P positive region of Q is defined as PosP(Q)=∪x∈U/QP(X).Definition 2.5 (relative core [36]).
Given a decision tableS=〈U,A,V,f〉, P⊆A, Q⊆A, r∈P, r is unnecessary in P relative to Q if and only if PosP(Q)=PosP-{r}(Q), otherwise r is unnecessary in P relative to Q. The core of P relative to Q is defined as COREQ(P)={r∣r∈P; r is necessary in P relative to Q}.Definition 2.6 (see [36]).
Given a decision tableS=〈U,A,V,f〉, P⊆A and Q⊆A, for all r∈P, if r is relatively necessary in P relative to Q, P is called independent relative to Q.Definition 2.7 (relative reduction [36]).
Given a decision tableS=〈U,A,V,f〉, P⊆A, Q⊆A, R∈P, if R is indispensable relative to Q and PosR(Q)=PosP(Q), R is called a reduction of P relative to Q.Definition 2.8 (see [18]).
Given a decision tableS=〈U,A,V,f〉, the element of discernibility matrix M can be defined as Bxys={a∈C∣f(x,a)≠f(y,a)∧w(x,y)=1}, where, x∈U, y∈U, and
(2.1)w(x,y)={1,x∈PosC(D),y∉PosC(D),1,x∉PosC(D),y∈PosC(D),1,x,y∈PosC(D),d(x)≠d(y),0,others.


## 3. The Abstract Process for Knowledge Reduction Based on Divide and Conquer Method in Rough Set Theory

### 3.1.  The Knowledge Reduction Based on Divide and Conquer Method under Equivalence Relation

In the research of rough set theory, the divide and conquer method is an effective method to design high effective algorithm. It can be used to compute equivalence classes, positive region, and attribute core of decision table (see Propositions3.1, 3.2, and 3.3) even execute some operators of discernibility matrix (see Propositions 3.4 and 3.5). In this section, the divide and conquer method under equivalence relation in rough set theory will be discussed.Proposition 3.1 (see [13]).
Given a decision tableS=〈U,A,V,f〉, for all c(c∈C), divide S into k(k=|IND(U/{c})|) subdecision tables S1,S2,…,Sk by U/{c}, where Si=〈Ui,(C∖{c})∪D,Vi,fi〉, which satisfies ∀x∈Ui∀y∈Uic(x)=c(y)(1≤i≤k) and ∀x∈Ui∀z∈Ujc(x)≠c(z)(1≤i<j≤k). Let R=C-{c}. Let us denote by PosRi(D)(1≤i≤k) the positive region of Si and the one of S by PosC(D), respectively. Then, PosC(D)=⋃1≤i≤kPosRi(D).Proposition3.1 presents the approach of computing equivalence classes or positive region by using divide and conquer method. Compared with decision tree-based method (without pruning), the approach allows us to generate “clear” leaves (with the same decision) for objects in the positive region and “unclear” leaves where objects are with different decisions and correspond to the boundary region. It may be an effective way to prevent overfitting, because “conquer” can play a role of pruning of tree. Furthermore, the approach needs less space because the construction of tree is not necessary.Proposition 3.2 (see [13]).
Given a decision tableS=〈U,A,V,f〉, for all c(c∈C), divide S into k(k=|IND(U/{c})|) sub-decision tables S1,S2,…,Sk by U/{c}, where Si=〈Ui,(C∖{c})∪D,Vi,fi〉, which satisfies ∀x∈Ui∀y∈Uic(x)=c(y)(1≤i≤k) and ∀x∈Ui∀z∈Ujc(x)≠c(z)(1≤i<j≤k). Let us denote by Corei(1≤i≤k) the attribute core of Si and the one of S by Core. Then, ⋃1≤i≤kCorei⊆Core⊆{c}∪⋃1≤i≤kCorei.Proposition 3.3 (see [13]).
Given a decision tableS-〈U,A,V,f〉, for all c(c∈C), divide S into k(k=|IND(U/{c})|) sub-decision tables S1,S2,…,Sk by U/{c}, where Si=〈Ui,(C∖{c})∪D,Vi,fi〉, which satisfies ∀x∈Ui∀y∈Uic(x)=c(y)(1≤i≤k) and ∀x∈Ui∀z∈Ujc(x)≠c(z)(1≤i<j≤k). Let us denote by redi(1≤i≤k) the attribute reduction of Si and the one of S by R. Let R=⋃1≤i≤kredi, R1={c}∪⋃1≤i≤kredi. Then, PosR(D)⊆PosC(D)=PosR1(D).Propositions3.2 and 3.3 present the approach of attribute core determining based on divide and conquer method. Compared with the method of computing attribute core on original decision table, it may be more efficient and can process bigger data set, since the big data set has been divided into many small data sets.Obviously, Propositions3.1, 3.2, and 3.3 hold.Discernibility matrix by Skowron is a useful method to design some algorithms in rough set theory. However, due to its high complexity of algorithms based on explicit computing of the discernibility matrices, the efficiency of algorithms based on discernibility matrix needs to be improved. In the literature some useful methods have been proposed (see [26–31] by Nguyen et al., and decomposition methods implemented in RSES). Our methods differ from the existing ones as follows.(1)
“How to keep invariance between the solution of original problem and the ones of sub-problems” is a key problem. We conclude some principles for computing positive region, attribute core, attribute reduction, and value reduction (see Propositions3.1, 3.2, 3.3, 3.4, 3.5, 3.11, and 3.12), which were not concluded before.(2)
Although the decision tree-based methods and our approaches both belong to divide and conquer method, our approaches cost more on “conquer” and “merge” while they cost less on “divide,” compared with the decision tree-based methods. Furthermore, our approaches need not to construct a tree, which maybe save space.(3)
The existing heuristic ones in [26–28] can improve the efficiency by measuring the discernibility degree of different objects quickly. In our approaches, the element cells of discernibility matrix can be deleted by dividing decision table fast without storing the discernibility matrix. Thus, it may be a quick one for operating discernibility matrix with small space (see Propositions 3.4 and 3.5).Given a decision tableS=〈U,A,V,f〉 and its discernibility matrix M (Definition 2.8); for all C1(C1⊆C), let us denote by M¯C1 a subset of element cells in M. M¯C1 can be labeled as {α1,α2,…,αt}(t=|M¯C1|), where(1)
∀αi∈M¯C1αi∈M(1≤i≤|M¯C1|);(2)
for allc∈C1, if ∃α∈M(c∈α), then α∈M¯C1.Proposition 3.4.
Given a decision tableS=〈U,A,V,f〉, for all c(c∈C), divide the decision table S into k(k=|IND(U/{c})|) sub-decision tables S1,S2,…,Sk by U/{c}, where Si=〈Ui,(C∖{c})∪D,Vi,fi〉. Let us denote by M the discernibility matrix of S and the discernibility matrix of Si(1≤i≤k) by Mi, respectively. Then, ⋃α∈Mα=⋃i=1k⋃β∈Miβ∪⋃γ∈M¯C1γ.(Note: If∀x,y∈Ui∀c1∈Cc1(x)=c1(y), then, Mi=ϕ)Proof.
First, prove⋃α∈Mα⊆⋃i=1k⋃β∈Miβ∪⋃γ∈M¯C1γ.
For allα∈M, then, ∃x,y∈Uα=BxyS (Definition 2.8). After the partition of U/C1, suppose x and y be divided into sub-decision tables Si(1≤i≤|U/C1|) and Sj(1≤j≤k), respectively.
Ifi=j, then, α∈Mi, that is, α∈⋃i=1k⋃β∈Miβ.
Ifi≠j, then, α∈M¯C1, that is, α∈⋃γ∈M¯C1γ.
Thus,α∈⋃i=1k⋃β∈Miβ∪⋃γ∈M¯C1γ. That is, ⋃α∈Mα⊆⋃i=1k⋃β∈Miβ∪⋃γ∈M¯C1γ.
Similarly, we can proof⋃α∈Mα⊇⋃i=1k⋃β∈Miβ∪⋃γ∈M¯C1γ.
Therefore, Proposition3.4 holds.Proposition 3.5.
Given a decision tableS=〈U,A,V,f〉, for all C1(C1⊆C), divide the decision table S into k(k=|IND(U/C1)|) sub-decision tables S1,S2,…,Sk by U/C1, where Si=〈Ui,(C∖C1)∪D,Vi,fi〉. Let us denote by M the discernibility matrix of S. Then, in the viewpoints of operating discernibility matrix, divide the decision table S by U/C1 on attribute set C1  if and only if  one deletes all the element cells of M¯C1from M one by one.According to Proposition3.4, it is easy to find that Proposition 3.5 holds.Propositions3.4 and 3.5 present the approach of deleting element cells of discernibility matrix. By using the approach, the element cells of discernibility matrix can be deleted quickly without constructing or storing the discernibility matrix. It may be an effective way to operate discernibility matrix quickly within small space. Thus, Propositions 3.4 and 3.5 can be used to design some efficient algorithms without explicit computing of discernibility matrix.


### 3.2. The Knowledge Reduction Based on Divide and Conquer Method under Tolerance Relation

In the course of attribute value reduction, tolerance relation is often adopted due to some attribute values on condition attribute being deleted. Thus, tolerance relation in attribute value reduction may be needed. A method is introduced by Kryszkiewicz and Rybinski [17] to process incomplete information system, where “*” is used to represent the missing values on condition attributes. Here, “*” can be also represent the deleted values on condition attributes. According to the tolerance relation by Kryszkiewicz, the divide and conquer method under the tolerance relation will be discussed.Definition 3.6 (see [17]).
Given an incomplete decision tableS=〈U,A,V,f〉, a tolerance relation T is defined as
(3.1)∀x,y∈U1∀B⊆R(TB(x,y)⟺∀b∈B((b(x)=b(y))∨(b(x)=*)∨(b(y)=*))).Definition 3.7 (see [17]).
The tolerance classTB(x) of an object x relative to an attribute set B is defined as TB(x)={y∣y∈U∧TB(x,y)}. In the tolerance relation-based extension of rough set theory, the lower approximation XBT and upper approximation XTB of an object set X relative to an attribute set B(B⊆C) are defined as XBT={x∈U∣TB(x)⊆X}, XTB={x∈U∣TB(x)∩X≠∅}.Definition 3.8 (the covering of the universe under tolerance relation).
Given a decision tableS=〈U,A,V,f〉 and condition attribute set C1(C1⊆C), according to the tolerance relation by Kryszkiewicz, the covering of the universe of S can be defined as U=U1∪U2∪⋯∪Uk, where ∀x,y∈Up(1≤p≤k)∀c∈C1(c(x)=c(y)∨c(x)=*∨c(y)=*), and ∀x∈Ur∀y∈Up(1≤r<p≤k)∃c∈C1((c(x)≠*∧c(y)≠*)⇒c(x)≠c(y)).Definition 3.9 (certain decision rule).
Given a decision tableS=〈U,A,V,f〉, for all xi∈PosC(D), the object xi can result in a certain decision rule di:des([xi]C)⇒des([xi]D), di(a)=a(xi), a∈C∪D. di∣C and di∣D are called the condition attribute set and decision attribute set of di, respectively.Definition 3.10 (see [36]).
Given a decision tableS=〈U,A,V,f〉, for arbitrary certain decision rule, there is [xi]C⊂[xi]D. For all a∈C, if [xi]C∖{a}⊆[xi]D does not hold, then, a is necessary in di; otherwise, a is not necessary in di.Proposition 3.11.
Given a decision tableS=〈U,A,V,f〉, and for all C1⊆C, given an decomposing order c1,c2,…cp(p=|C1|), according to the order and tolerance relation, S can be divided into k sub-decision tables S1,S2,…,Sk, where Si=〈Ui,A,V,f〉. Assume S and S1,S2,…,Sk be processed with the same way. For each sub-decision table Si(1≤i≤k), for all x(x∈Si∧x∈PosC(D)), let us denote by dx a decision rule relative to object x in Si and a decision rule relative to x in S by dx1, respectively. There is (1)
inSi, if ∃c(c∈C), c is necessary in dx. Then, c is necessary in dx1;(2)
inSi, if ∃c(c∈C), c is not necessary in dx. Then, c is not necessary in dx1;(3)
dx=dx1.Proposition 3.12.
Given a decision tableS=〈U,A,V,f〉, for all C1⊆C, given an decomposing order c1,c2,…cp(p=|C1|), and according to the order, S can be divided into k sub-decision tables S1,S2,…,Sk, where Si=〈Ui,A,V,f〉. Assume S and S1,S2,…,Sk be processed with the same. For each sub-decision table Si(1≤i≤k), let us denote by Rule the certain decision rule set of S and the one of Si by Rulei, respectively. Then, Rule=⋃i=1kRulei.Propositions3.11 and 3.12 present the approach of value reduction based on divide and conquer method. It can keep invariance between the solution of original decision table and the ones of sub-decision tables. By using the approach, it allows us to generate decision rules from sub-decision tables, not from original decision table. It may be a feasible way to process big data set.


### 3.3. The Abstract Process for Knowledge Reduction Based on Divide and Conquer Method in Rough Set Theory

According to the divide and conquer method under equivalence relation and tolerance relation, the abstract process for knowledge reduction in rough set theory based on the divide and conquer method APFKRDAC(P, S) will be discussed in this section.Algorithm 3.13 (APFKRDAC(P,S)).
Input: The problemP on S.
Output: The solutionSolu of the problem P.Step 1 (determine a similarity relation of different objects).
Determine a similarity relation between different objects, such as equivalence relation or tolerance relation. Generally, reflexivity and symmetry of different objects may be necessary.Step 2 (determine the decomposing order).
Determine the orderC1(C1⊆C) for decomposing the universe of decision table. Let C1={c1,c2,…,cp},(p=|C1|).Step 3 (determine the decomposing strategy).
(
3.1
)
Design a judgment criteriaCanBeDivide() for judging whether the universe can be decomposed.
(
3.2
)
Design a decompose functionDecomposingFunc(), which can be used to decompose the universe recursively.
(
3.3
)
Design a boolean functionIsEnoughSmall(), which can be used to judge if the size of problem is small enough to be processed easily.
(
3.4
)
Design a computation functionProcessSmallProblem(), which can be used to process small problems directly.
(
3.5
)
Design a computation functionMergingSolution(), which can be used to merge the solutions of sub-problems.Step 4 (process the problem based on divide and conquer method).
(4.1) IFIsEnoughSmall(S) THEN Solu=SolutionSubProblems(S),
goto Step  5.
(4.2) (Divide)
According to the decomposing order, divideS into k sub-decision tables
S1,S2,…,Sk on C1.
(4.3) (Conquer sub-problems recursively)
FORi=1 TO k DO
Solui=APFKRDAC(Pi,Si).
END FOR.
Where,Si=〈Ui,Ci∪D,V,f〉, Ci⊆C, Pi is the sub-problem of Si.
(4.4) (Merge the solutions of sub-problems)
Solu=MergingSolution(Solu1,Solu2,…,Soluk).Step 5 (optimize the solution).
If necessary, optimize the solutionSolu.Step 6 (return the solution).
RETURNSolu.Now, let us give an example for computing the positive region of decision table to explain Algorithm3.13 (see Algorithm 3.14: the algorithm for computing positive region based on divide and conquer method).Algorithm 3.14 (CPRDAC(P,S)).
Input: The problemP on S: compute positive region.
Output: The positive regionPosC(D) of S.Step 1 (Determine the similar relation).
equivalence relation.Step 2 (Determine the decomposing order).
c
1
,
c
2
,
…
,
c
m
(
m
=
|
C
|
).Step 3 (Determine the decomposing strategy).
(3.1) Design a judgment criteriaCanBeDivide():
On attributeci, for all Ui(Ui⊆U),
IF∃x∈Ui∃y∈Ui(ci(x)≠ci(y))∧∃z∈Ui∃w∈Ui(D(z)≠D(w)) THEN
CanbeDivide(ci)=true;
ELSECanBeDivide(ci)=false;
END IF
(3.2) Design a decompose functionDecomposingFunc():
According toU/C, S can be divided into k=|U/C| sub-decision tables
S1,S2,…,Sk on attributes c1,c2,…,cm recursively.
(3.3) Design a boolean functionIsEnoughSmall():
Letcr be the attribute on which the universe is being decomposed.
IF(|Ui|==1) or (r>m) or ∀x∈Ui∀y∈Ui(D(x)==D(y)) THEN
IsEnoughSmall(Si)=true.
END IF
(3.4) Design a computation functionProcessSmallProblem():
For arbitrary sub-decision tableSi and its universe Ui,
IF∀x∈Ui∀y∈Ui(D(x)==D(y)) THEN Ui⊆PosC(D)∧Solui=Ui;
ELSESolui=ϕ;
END IF
(3.5) Design a computation functionMergingSolution():
Solu=Solu1∪Solu2∪⋯∪Soluk;Step 4 (Process the problem based on the divide and conquer method).
(4.1) IFIsEnoughSmall(S) THEN Solu=ProcessSmallProblem(S); goto Step  5.
(4.2) (Divide)
According to the order{c1,c2,…,cm}, S can be divided into k sub-
decision tablesS1,S2,…,Sk on c1 by using U/IND({c1}).
(4.3) (Conquer sub-problems recursively)
FORi=1 TO k DO
Solui= CPRDAC(Pi,Si).
END FOR
Where,Si=〈Ui,(C-{c1})∪D,V,f〉, Pi denotes computing the positive region of
Si.
(4.4) (Merge the solutions of sub-problems)
Solu=Solu1∪Solu2∪⋯∪Soluk.Step 5 (Optimize the solution).
S
o
l
u is an optimized result.Step 6 (Return the solution).
RETURNSolu.Example 3.15.
Given a decision tableS=〈U,A,V,f〉, (U={x1,x2,x3, x4,x5,x6},C={c1,c2,c3}), now compute the positive region of S according to Algorithm 3.14. The whole process can be found in Figure 1.
Let us denote byPosC(D),PosC1(D),PosC2(D),…,PosC7(D) the positive region of S,S1,S2,…,S7, respectively.
DivideS into S1,S2,S3 on c1.
ConquerS1.
DivideS1 into S4,S5 on c2.
ConquerS4. PosC4(D)={x3,x5}.
ConquerS5. PosC5(D)={x6}.
Merge the solutions ofS4 and S5. PosC1(D)=PosC4(D)∪PosC5(D)={x3,x5,x6}.
Similarly, we can conquerS2 and S3.
ConquerS2. PosC2(D)={x4}.
ConquerS3. PosC3(D)=ϕ.
Merge the solutions ofS1, S2, and S3. 									(3.2)PosC(D)=PosC1(D)∪PosC2(D)∪PosC3(D)={x3,x4,x5,x6}.Figure 1
The course of computing positive region ofS.


## 3.1.  The Knowledge Reduction Based on Divide and Conquer Method under Equivalence Relation

In the research of rough set theory, the divide and conquer method is an effective method to design high effective algorithm. It can be used to compute equivalence classes, positive region, and attribute core of decision table (see Propositions3.1, 3.2, and 3.3) even execute some operators of discernibility matrix (see Propositions 3.4 and 3.5). In this section, the divide and conquer method under equivalence relation in rough set theory will be discussed.Proposition 3.1 (see [13]).
Given a decision tableS=〈U,A,V,f〉, for all c(c∈C), divide S into k(k=|IND(U/{c})|) subdecision tables S1,S2,…,Sk by U/{c}, where Si=〈Ui,(C∖{c})∪D,Vi,fi〉, which satisfies ∀x∈Ui∀y∈Uic(x)=c(y)(1≤i≤k) and ∀x∈Ui∀z∈Ujc(x)≠c(z)(1≤i<j≤k). Let R=C-{c}. Let us denote by PosRi(D)(1≤i≤k) the positive region of Si and the one of S by PosC(D), respectively. Then, PosC(D)=⋃1≤i≤kPosRi(D).Proposition3.1 presents the approach of computing equivalence classes or positive region by using divide and conquer method. Compared with decision tree-based method (without pruning), the approach allows us to generate “clear” leaves (with the same decision) for objects in the positive region and “unclear” leaves where objects are with different decisions and correspond to the boundary region. It may be an effective way to prevent overfitting, because “conquer” can play a role of pruning of tree. Furthermore, the approach needs less space because the construction of tree is not necessary.Proposition 3.2 (see [13]).
Given a decision tableS=〈U,A,V,f〉, for all c(c∈C), divide S into k(k=|IND(U/{c})|) sub-decision tables S1,S2,…,Sk by U/{c}, where Si=〈Ui,(C∖{c})∪D,Vi,fi〉, which satisfies ∀x∈Ui∀y∈Uic(x)=c(y)(1≤i≤k) and ∀x∈Ui∀z∈Ujc(x)≠c(z)(1≤i<j≤k). Let us denote by Corei(1≤i≤k) the attribute core of Si and the one of S by Core. Then, ⋃1≤i≤kCorei⊆Core⊆{c}∪⋃1≤i≤kCorei.Proposition 3.3 (see [13]).
Given a decision tableS-〈U,A,V,f〉, for all c(c∈C), divide S into k(k=|IND(U/{c})|) sub-decision tables S1,S2,…,Sk by U/{c}, where Si=〈Ui,(C∖{c})∪D,Vi,fi〉, which satisfies ∀x∈Ui∀y∈Uic(x)=c(y)(1≤i≤k) and ∀x∈Ui∀z∈Ujc(x)≠c(z)(1≤i<j≤k). Let us denote by redi(1≤i≤k) the attribute reduction of Si and the one of S by R. Let R=⋃1≤i≤kredi, R1={c}∪⋃1≤i≤kredi. Then, PosR(D)⊆PosC(D)=PosR1(D).Propositions3.2 and 3.3 present the approach of attribute core determining based on divide and conquer method. Compared with the method of computing attribute core on original decision table, it may be more efficient and can process bigger data set, since the big data set has been divided into many small data sets.Obviously, Propositions3.1, 3.2, and 3.3 hold.Discernibility matrix by Skowron is a useful method to design some algorithms in rough set theory. However, due to its high complexity of algorithms based on explicit computing of the discernibility matrices, the efficiency of algorithms based on discernibility matrix needs to be improved. In the literature some useful methods have been proposed (see [26–31] by Nguyen et al., and decomposition methods implemented in RSES). Our methods differ from the existing ones as follows.(1)
“How to keep invariance between the solution of original problem and the ones of sub-problems” is a key problem. We conclude some principles for computing positive region, attribute core, attribute reduction, and value reduction (see Propositions3.1, 3.2, 3.3, 3.4, 3.5, 3.11, and 3.12), which were not concluded before.(2)
Although the decision tree-based methods and our approaches both belong to divide and conquer method, our approaches cost more on “conquer” and “merge” while they cost less on “divide,” compared with the decision tree-based methods. Furthermore, our approaches need not to construct a tree, which maybe save space.(3)
The existing heuristic ones in [26–28] can improve the efficiency by measuring the discernibility degree of different objects quickly. In our approaches, the element cells of discernibility matrix can be deleted by dividing decision table fast without storing the discernibility matrix. Thus, it may be a quick one for operating discernibility matrix with small space (see Propositions 3.4 and 3.5).Given a decision tableS=〈U,A,V,f〉 and its discernibility matrix M (Definition 2.8); for all C1(C1⊆C), let us denote by M¯C1 a subset of element cells in M. M¯C1 can be labeled as {α1,α2,…,αt}(t=|M¯C1|), where(1)
∀αi∈M¯C1αi∈M(1≤i≤|M¯C1|);(2)
for allc∈C1, if ∃α∈M(c∈α), then α∈M¯C1.Proposition 3.4.
Given a decision tableS=〈U,A,V,f〉, for all c(c∈C), divide the decision table S into k(k=|IND(U/{c})|) sub-decision tables S1,S2,…,Sk by U/{c}, where Si=〈Ui,(C∖{c})∪D,Vi,fi〉. Let us denote by M the discernibility matrix of S and the discernibility matrix of Si(1≤i≤k) by Mi, respectively. Then, ⋃α∈Mα=⋃i=1k⋃β∈Miβ∪⋃γ∈M¯C1γ.(Note: If∀x,y∈Ui∀c1∈Cc1(x)=c1(y), then, Mi=ϕ)Proof.
First, prove⋃α∈Mα⊆⋃i=1k⋃β∈Miβ∪⋃γ∈M¯C1γ.
For allα∈M, then, ∃x,y∈Uα=BxyS (Definition 2.8). After the partition of U/C1, suppose x and y be divided into sub-decision tables Si(1≤i≤|U/C1|) and Sj(1≤j≤k), respectively.
Ifi=j, then, α∈Mi, that is, α∈⋃i=1k⋃β∈Miβ.
Ifi≠j, then, α∈M¯C1, that is, α∈⋃γ∈M¯C1γ.
Thus,α∈⋃i=1k⋃β∈Miβ∪⋃γ∈M¯C1γ. That is, ⋃α∈Mα⊆⋃i=1k⋃β∈Miβ∪⋃γ∈M¯C1γ.
Similarly, we can proof⋃α∈Mα⊇⋃i=1k⋃β∈Miβ∪⋃γ∈M¯C1γ.
Therefore, Proposition3.4 holds.Proposition 3.5.
Given a decision tableS=〈U,A,V,f〉, for all C1(C1⊆C), divide the decision table S into k(k=|IND(U/C1)|) sub-decision tables S1,S2,…,Sk by U/C1, where Si=〈Ui,(C∖C1)∪D,Vi,fi〉. Let us denote by M the discernibility matrix of S. Then, in the viewpoints of operating discernibility matrix, divide the decision table S by U/C1 on attribute set C1  if and only if  one deletes all the element cells of M¯C1from M one by one.According to Proposition3.4, it is easy to find that Proposition 3.5 holds.Propositions3.4 and 3.5 present the approach of deleting element cells of discernibility matrix. By using the approach, the element cells of discernibility matrix can be deleted quickly without constructing or storing the discernibility matrix. It may be an effective way to operate discernibility matrix quickly within small space. Thus, Propositions 3.4 and 3.5 can be used to design some efficient algorithms without explicit computing of discernibility matrix.


## 3.2. The Knowledge Reduction Based on Divide and Conquer Method under Tolerance Relation

In the course of attribute value reduction, tolerance relation is often adopted due to some attribute values on condition attribute being deleted. Thus, tolerance relation in attribute value reduction may be needed. A method is introduced by Kryszkiewicz and Rybinski [17] to process incomplete information system, where “*” is used to represent the missing values on condition attributes. Here, “*” can be also represent the deleted values on condition attributes. According to the tolerance relation by Kryszkiewicz, the divide and conquer method under the tolerance relation will be discussed.Definition 3.6 (see [17]).
Given an incomplete decision tableS=〈U,A,V,f〉, a tolerance relation T is defined as
(3.1)∀x,y∈U1∀B⊆R(TB(x,y)⟺∀b∈B((b(x)=b(y))∨(b(x)=*)∨(b(y)=*))).Definition 3.7 (see [17]).
The tolerance classTB(x) of an object x relative to an attribute set B is defined as TB(x)={y∣y∈U∧TB(x,y)}. In the tolerance relation-based extension of rough set theory, the lower approximation XBT and upper approximation XTB of an object set X relative to an attribute set B(B⊆C) are defined as XBT={x∈U∣TB(x)⊆X}, XTB={x∈U∣TB(x)∩X≠∅}.Definition 3.8 (the covering of the universe under tolerance relation).
Given a decision tableS=〈U,A,V,f〉 and condition attribute set C1(C1⊆C), according to the tolerance relation by Kryszkiewicz, the covering of the universe of S can be defined as U=U1∪U2∪⋯∪Uk, where ∀x,y∈Up(1≤p≤k)∀c∈C1(c(x)=c(y)∨c(x)=*∨c(y)=*), and ∀x∈Ur∀y∈Up(1≤r<p≤k)∃c∈C1((c(x)≠*∧c(y)≠*)⇒c(x)≠c(y)).Definition 3.9 (certain decision rule).
Given a decision tableS=〈U,A,V,f〉, for all xi∈PosC(D), the object xi can result in a certain decision rule di:des([xi]C)⇒des([xi]D), di(a)=a(xi), a∈C∪D. di∣C and di∣D are called the condition attribute set and decision attribute set of di, respectively.Definition 3.10 (see [36]).
Given a decision tableS=〈U,A,V,f〉, for arbitrary certain decision rule, there is [xi]C⊂[xi]D. For all a∈C, if [xi]C∖{a}⊆[xi]D does not hold, then, a is necessary in di; otherwise, a is not necessary in di.Proposition 3.11.
Given a decision tableS=〈U,A,V,f〉, and for all C1⊆C, given an decomposing order c1,c2,…cp(p=|C1|), according to the order and tolerance relation, S can be divided into k sub-decision tables S1,S2,…,Sk, where Si=〈Ui,A,V,f〉. Assume S and S1,S2,…,Sk be processed with the same way. For each sub-decision table Si(1≤i≤k), for all x(x∈Si∧x∈PosC(D)), let us denote by dx a decision rule relative to object x in Si and a decision rule relative to x in S by dx1, respectively. There is (1)
inSi, if ∃c(c∈C), c is necessary in dx. Then, c is necessary in dx1;(2)
inSi, if ∃c(c∈C), c is not necessary in dx. Then, c is not necessary in dx1;(3)
dx=dx1.Proposition 3.12.
Given a decision tableS=〈U,A,V,f〉, for all C1⊆C, given an decomposing order c1,c2,…cp(p=|C1|), and according to the order, S can be divided into k sub-decision tables S1,S2,…,Sk, where Si=〈Ui,A,V,f〉. Assume S and S1,S2,…,Sk be processed with the same. For each sub-decision table Si(1≤i≤k), let us denote by Rule the certain decision rule set of S and the one of Si by Rulei, respectively. Then, Rule=⋃i=1kRulei.Propositions3.11 and 3.12 present the approach of value reduction based on divide and conquer method. It can keep invariance between the solution of original decision table and the ones of sub-decision tables. By using the approach, it allows us to generate decision rules from sub-decision tables, not from original decision table. It may be a feasible way to process big data set.


## 3.3. The Abstract Process for Knowledge Reduction Based on Divide and Conquer Method in Rough Set Theory

According to the divide and conquer method under equivalence relation and tolerance relation, the abstract process for knowledge reduction in rough set theory based on the divide and conquer method APFKRDAC(P, S) will be discussed in this section.Algorithm 3.13 (APFKRDAC(P,S)).
Input: The problemP on S.
Output: The solutionSolu of the problem P.Step 1 (determine a similarity relation of different objects).
Determine a similarity relation between different objects, such as equivalence relation or tolerance relation. Generally, reflexivity and symmetry of different objects may be necessary.Step 2 (determine the decomposing order).
Determine the orderC1(C1⊆C) for decomposing the universe of decision table. Let C1={c1,c2,…,cp},(p=|C1|).Step 3 (determine the decomposing strategy).
(
3.1
)
Design a judgment criteriaCanBeDivide() for judging whether the universe can be decomposed.
(
3.2
)
Design a decompose functionDecomposingFunc(), which can be used to decompose the universe recursively.
(
3.3
)
Design a boolean functionIsEnoughSmall(), which can be used to judge if the size of problem is small enough to be processed easily.
(
3.4
)
Design a computation functionProcessSmallProblem(), which can be used to process small problems directly.
(
3.5
)
Design a computation functionMergingSolution(), which can be used to merge the solutions of sub-problems.Step 4 (process the problem based on divide and conquer method).
(4.1) IFIsEnoughSmall(S) THEN Solu=SolutionSubProblems(S),
goto Step  5.
(4.2) (Divide)
According to the decomposing order, divideS into k sub-decision tables
S1,S2,…,Sk on C1.
(4.3) (Conquer sub-problems recursively)
FORi=1 TO k DO
Solui=APFKRDAC(Pi,Si).
END FOR.
Where,Si=〈Ui,Ci∪D,V,f〉, Ci⊆C, Pi is the sub-problem of Si.
(4.4) (Merge the solutions of sub-problems)
Solu=MergingSolution(Solu1,Solu2,…,Soluk).Step 5 (optimize the solution).
If necessary, optimize the solutionSolu.Step 6 (return the solution).
RETURNSolu.Now, let us give an example for computing the positive region of decision table to explain Algorithm3.13 (see Algorithm 3.14: the algorithm for computing positive region based on divide and conquer method).Algorithm 3.14 (CPRDAC(P,S)).
Input: The problemP on S: compute positive region.
Output: The positive regionPosC(D) of S.Step 1 (Determine the similar relation).
equivalence relation.Step 2 (Determine the decomposing order).
c
1
,
c
2
,
…
,
c
m
(
m
=
|
C
|
).Step 3 (Determine the decomposing strategy).
(3.1) Design a judgment criteriaCanBeDivide():
On attributeci, for all Ui(Ui⊆U),
IF∃x∈Ui∃y∈Ui(ci(x)≠ci(y))∧∃z∈Ui∃w∈Ui(D(z)≠D(w)) THEN
CanbeDivide(ci)=true;
ELSECanBeDivide(ci)=false;
END IF
(3.2) Design a decompose functionDecomposingFunc():
According toU/C, S can be divided into k=|U/C| sub-decision tables
S1,S2,…,Sk on attributes c1,c2,…,cm recursively.
(3.3) Design a boolean functionIsEnoughSmall():
Letcr be the attribute on which the universe is being decomposed.
IF(|Ui|==1) or (r>m) or ∀x∈Ui∀y∈Ui(D(x)==D(y)) THEN
IsEnoughSmall(Si)=true.
END IF
(3.4) Design a computation functionProcessSmallProblem():
For arbitrary sub-decision tableSi and its universe Ui,
IF∀x∈Ui∀y∈Ui(D(x)==D(y)) THEN Ui⊆PosC(D)∧Solui=Ui;
ELSESolui=ϕ;
END IF
(3.5) Design a computation functionMergingSolution():
Solu=Solu1∪Solu2∪⋯∪Soluk;Step 4 (Process the problem based on the divide and conquer method).
(4.1) IFIsEnoughSmall(S) THEN Solu=ProcessSmallProblem(S); goto Step  5.
(4.2) (Divide)
According to the order{c1,c2,…,cm}, S can be divided into k sub-
decision tablesS1,S2,…,Sk on c1 by using U/IND({c1}).
(4.3) (Conquer sub-problems recursively)
FORi=1 TO k DO
Solui= CPRDAC(Pi,Si).
END FOR
Where,Si=〈Ui,(C-{c1})∪D,V,f〉, Pi denotes computing the positive region of
Si.
(4.4) (Merge the solutions of sub-problems)
Solu=Solu1∪Solu2∪⋯∪Soluk.Step 5 (Optimize the solution).
S
o
l
u is an optimized result.Step 6 (Return the solution).
RETURNSolu.Example 3.15.
Given a decision tableS=〈U,A,V,f〉, (U={x1,x2,x3, x4,x5,x6},C={c1,c2,c3}), now compute the positive region of S according to Algorithm 3.14. The whole process can be found in Figure 1.
Let us denote byPosC(D),PosC1(D),PosC2(D),…,PosC7(D) the positive region of S,S1,S2,…,S7, respectively.
DivideS into S1,S2,S3 on c1.
ConquerS1.
DivideS1 into S4,S5 on c2.
ConquerS4. PosC4(D)={x3,x5}.
ConquerS5. PosC5(D)={x6}.
Merge the solutions ofS4 and S5. PosC1(D)=PosC4(D)∪PosC5(D)={x3,x5,x6}.
Similarly, we can conquerS2 and S3.
ConquerS2. PosC2(D)={x4}.
ConquerS3. PosC3(D)=ϕ.
Merge the solutions ofS1, S2, and S3. 									(3.2)PosC(D)=PosC1(D)∪PosC2(D)∪PosC3(D)={x3,x4,x5,x6}.Figure 1
The course of computing positive region ofS.


## 4. A Fast Algorithm for Attribute Reduction Based on Divide and Conquer Method

Knowledge reduction is the key problem in rough set theory. When the divide and conquer method is used to design the algorithm for knowledge reduction, some good results may be obtained. However, implementing the knowledge reduction based on the divide and conquer method is very complex, though it is only a simple granular computing method. Here, we will discuss the quick algorithm for knowledge reduction based on divide and conquer method.In the course of attribute reduction, the divide and conquer method is used to compute the equivalence class, the positive region, and the non-empty label attribute set and delete the elements of discernibility matrix. Due to the complexity of attribute reduction, the following algorithm is not presented as Algorithm3.14 in details.According to Step  2 of Algorithm3.13, the attribute set and the order must be determined, on which the universe of decision table will be partitioned in turns. Generally speaking, the decomposing order depends on the problem which needs to be solved. Furthermore, if the order is not given by field experts, it can be computed by the weights in [10, 15, 23, 25, 26, 28, 33, 36, 37, 41]. Of course, if the attribute order is given, it will be more suitable for Algorithm 3.13. Most techniques discussed below are based on a given attribute order and divide and conquer method. In this section, a quick attribute reduction algorithm based on a given attribute order and divide and conquer method is proposed.


### 4.1. Attribute Order

In 2001, an algorithm for attribute reduction based on the given attribute order is proposed by Jue Wang and Ju Wang [38]. For the convenience of illustration, some basic notions about attribute order are introduced here.Given a decision tableS=〈U,A,V,f〉, an attribute order relation over C(SO:c1≺c2≺⋯≺c|C|) can be defined. Let us denote by M the discernibility matrix of S. For any δ∈M, the attributes of discernibility matrix δ inherit the order relation of SO from left to right, that is, δ=cjB, where cj∈C and B⊂(C-{a}), and cj is the first element of δ by SO, called the non-empty label attribute of δ [33].Forcj, a set L(SO)={δ∣δ=cjB, δ inherit the order relation of SO from left to right and δ∈M} is defined. Hence, M can be divided into equivalence classes by label attributes defining a partition {[1],[2],…,[|C|]} of M denoted by M/L(SO) [33]. Supposing N=max{k∣[k]∈M/L(SO)∧[k]≠ϕ}, its maximum non-empty label attribute is aN.


### 4.2. Attribute Reduction Based on the Divide and Conquer Method

Lemma 4.1.
∀
B
x
y
S
∈
M
(
B
x
y
S
≠
ϕ) (Definition 2.8) if and only if (x∈PosC(D)∧y∈PosC(D)∧(d(x)≠d(y))∨(x∈PosC(D)∧y∉PosC(D))∨(x∉PosC(D)∧y∈PosC(D)).According to Definition2.8, obviously Lemma 4.1 holds.Proposition 4.2.
Given a decision tableS=〈U,A,V,f〉, for all c∈C, let M be the discernibility matrix of S. Then, ∃α∈M(c∈α)   if and only if  the following conditions hold: (1) |U|>1; (2) ∃x∈U(x∈PosC(D)); (3) |VD|>1; (4) |V{c}|>1.Proof.
(Necessity) according to Lemma4.1, obviously Proposition 4.2 holds.
(Sufficiency):
for allx(x∈PosC(D)∧x∈U), according to (|U|>1)∧(|VD|>1), then,
∃y(y≠x)(y∈U∧D(x)≠D(y)).
Ifc(x)≠c(y), then c∈BxyS, that is, ∃α(α∈M)c∈α. The proposition holds.
Ifc(x)=c(y), then, there are two cases.Case1 (y∈PosC(D)). According to |V{c}|>1, ∃z(z≠x∧z≠y)(c(z)≠c(x)), thus (c∈BxzS)∨(c∈ByzS)=1.
That is,∃α(α∈M)c∈α. The proposition holds.
Case
2 (y∉PosC(D)). According to |V{c}|>1, ∃z(z≠x∧z≠y)(c(z)≠c(x)). If z∈PosC(D), then c∈ByzS;
ifz∉PosC(D), then c∈ByzS. Thus, the proposition holds.
Therefore, Proposition4.2 holds.According to the algorithm in [38], in order to compute the attribute reduction of a decision table, its non-empty label attribute set L(SO) should be first calculated. Using the divide and conquer method, an efficient algorithm for computing the non-empty label attribute set L(SO) is developed. A recursive function for computing the non-empty label attribute set is used in the algorithm.Function 1
NonEmptyLabelAttr(S,r)
//S is decision table. r is the number of attributes (1≤r≤|C|).Step 1 (Ending Condition).
According to Propositions4.2 and 5.1,
IFr=|C|+1 or |U|==1 or PosC(D)==ϕ or |VD|==1 THEN
return;
END IFStep 2 (Compute non-empty labels based on divide and conquer method).
Let NonEmptyLabel[] be an array used to store the solution.
Step2.1. IF |V{cr}|>1 THEN
Denote non-empty label attribute: NonEmptyLabel[r] = 1;
END IF
Step2.2 (Divide). Divide S into S1,S2,…,Sk by U/IND({cr});
Step2.3 (Conquer sub-problems). FOR i = 1 TO k DO
NonEmptyLabelAttr(Si,r+1);
END FOR.
Step2.4 (Merge the solutions). Here, there is no operation because the solutions are stored in the array NonEmptyLabel[].
END Function 1.Using the above recursive function, an algorithm for computing the non-empty label attribute set of a decision table is developed.Algorithm 4.3.
Computation of The Non-empty Label Attribute SetL(SO)
Input: A decision tableS and an attribute order SO:c1≺c2≺···≺c|C|
Output: The non-empty label attribute setR1 of S.Step 1.
R
1
=
ϕ; r=1;
FORj=1 TO |C| DO
NonEmptyLabel[j]=0;
END FORStep 2.
NonEmptyLabelAttr(S,1);Step 3.
FORj=1 TO |C| DO
IFNonEmptyLabel[j]==1 THEN R1=R1∪{cj};
END FORStep 4.
RETURNR1.Supposen=|U|, m=|C|. According to the conclusion of literature [45], the average time and space complexities of the Algorithm 4.3 are T=O(n×(m+logn)) and S=O(m+n).Obviously, Algorithm4.3 is an instance of Algorithm 3.13. Given an attribute order of the conditional attributes in a decision table, using the Algorithm 4.3 and divide and conquer method, an efficient attribute reduction algorithm is developed.Algorithm 4.4.
Computation of Attribute Reduction Based on Divide and Conquer Method
Input: A decision tableS=〈U,A,V,f〉 and an attribute order SO:c1≺c2≺···≺c|C|
Output: Attribute reductionR of S.Step 1.
U
1
1
=
U, R=ϕ.Step 2.
Compute the positive regionPosC(D), according to Algorithm 3.14.Step 3.
Compute the non-empty label attribute setR1 by Algorithm 4.3.Step 4.
//SupposecN be the maximum label attribute of R1.
R
=
R
∪
{
c
N
′
}
;
R
1
=
R
1
-
R;
IFR1==ϕ THEN RETURN R;
ELSE
Generate a new attribute order:
c11≺c21≺⋯≺c|R|1≺c12≺c22≺⋯≺c|R1|2;
Compute new non-empty label attribute setR1 of S by Algorithm 4.3;
GOTO Step  4.
END IFSupposen=|U| and m=|C|, the average time complexity of the Algorithm 4.4 is O(n×m×(m+logn)). Its space complexity is O(m+n).In Algorithm4.4, Step  1 is the initialization. In Step  2 of Algorithm 4.4, divide and conquer method is used to compute equivalence classes and positive region, thus Step  2 is an instance of Algorithm 3.13. In Step 3, Algorithm 4.3 is used to compute non-empty label attribute set (Algorithm 4.3 is also an instance of Algorithm 3.13). Step  4 is responding to Step  5 of Algorithm 3.13. In Step  4, Algorithm 4.3 is called repeatedly to reduce the redundant attribute set. That is, Algorithm 4.4 is composed of instances of Algorithm 4.3, which illustrates that Algorithm 4.4 is implemented by divide and conquer method. Basically, divide and conquer method is used primarily to compute equivalence classes, positive region, and non-empty label attribute set and delete element cells in discernibility matrix in Algorithm 4.4.


## 4.1. Attribute Order

In 2001, an algorithm for attribute reduction based on the given attribute order is proposed by Jue Wang and Ju Wang [38]. For the convenience of illustration, some basic notions about attribute order are introduced here.Given a decision tableS=〈U,A,V,f〉, an attribute order relation over C(SO:c1≺c2≺⋯≺c|C|) can be defined. Let us denote by M the discernibility matrix of S. For any δ∈M, the attributes of discernibility matrix δ inherit the order relation of SO from left to right, that is, δ=cjB, where cj∈C and B⊂(C-{a}), and cj is the first element of δ by SO, called the non-empty label attribute of δ [33].Forcj, a set L(SO)={δ∣δ=cjB, δ inherit the order relation of SO from left to right and δ∈M} is defined. Hence, M can be divided into equivalence classes by label attributes defining a partition {[1],[2],…,[|C|]} of M denoted by M/L(SO) [33]. Supposing N=max{k∣[k]∈M/L(SO)∧[k]≠ϕ}, its maximum non-empty label attribute is aN.


## 4.2. Attribute Reduction Based on the Divide and Conquer Method

Lemma 4.1.
∀
B
x
y
S
∈
M
(
B
x
y
S
≠
ϕ) (Definition 2.8) if and only if (x∈PosC(D)∧y∈PosC(D)∧(d(x)≠d(y))∨(x∈PosC(D)∧y∉PosC(D))∨(x∉PosC(D)∧y∈PosC(D)).According to Definition2.8, obviously Lemma 4.1 holds.Proposition 4.2.
Given a decision tableS=〈U,A,V,f〉, for all c∈C, let M be the discernibility matrix of S. Then, ∃α∈M(c∈α)   if and only if  the following conditions hold: (1) |U|>1; (2) ∃x∈U(x∈PosC(D)); (3) |VD|>1; (4) |V{c}|>1.Proof.
(Necessity) according to Lemma4.1, obviously Proposition 4.2 holds.
(Sufficiency):
for allx(x∈PosC(D)∧x∈U), according to (|U|>1)∧(|VD|>1), then,
∃y(y≠x)(y∈U∧D(x)≠D(y)).
Ifc(x)≠c(y), then c∈BxyS, that is, ∃α(α∈M)c∈α. The proposition holds.
Ifc(x)=c(y), then, there are two cases.Case1 (y∈PosC(D)). According to |V{c}|>1, ∃z(z≠x∧z≠y)(c(z)≠c(x)), thus (c∈BxzS)∨(c∈ByzS)=1.
That is,∃α(α∈M)c∈α. The proposition holds.
Case
2 (y∉PosC(D)). According to |V{c}|>1, ∃z(z≠x∧z≠y)(c(z)≠c(x)). If z∈PosC(D), then c∈ByzS;
ifz∉PosC(D), then c∈ByzS. Thus, the proposition holds.
Therefore, Proposition4.2 holds.According to the algorithm in [38], in order to compute the attribute reduction of a decision table, its non-empty label attribute set L(SO) should be first calculated. Using the divide and conquer method, an efficient algorithm for computing the non-empty label attribute set L(SO) is developed. A recursive function for computing the non-empty label attribute set is used in the algorithm.Function 1
NonEmptyLabelAttr(S,r)
//S is decision table. r is the number of attributes (1≤r≤|C|).Step 1 (Ending Condition).
According to Propositions4.2 and 5.1,
IFr=|C|+1 or |U|==1 or PosC(D)==ϕ or |VD|==1 THEN
return;
END IFStep 2 (Compute non-empty labels based on divide and conquer method).
Let NonEmptyLabel[] be an array used to store the solution.
Step2.1. IF |V{cr}|>1 THEN
Denote non-empty label attribute: NonEmptyLabel[r] = 1;
END IF
Step2.2 (Divide). Divide S into S1,S2,…,Sk by U/IND({cr});
Step2.3 (Conquer sub-problems). FOR i = 1 TO k DO
NonEmptyLabelAttr(Si,r+1);
END FOR.
Step2.4 (Merge the solutions). Here, there is no operation because the solutions are stored in the array NonEmptyLabel[].
END Function 1.Using the above recursive function, an algorithm for computing the non-empty label attribute set of a decision table is developed.Algorithm 4.3.
Computation of The Non-empty Label Attribute SetL(SO)
Input: A decision tableS and an attribute order SO:c1≺c2≺···≺c|C|
Output: The non-empty label attribute setR1 of S.Step 1.
R
1
=
ϕ; r=1;
FORj=1 TO |C| DO
NonEmptyLabel[j]=0;
END FORStep 2.
NonEmptyLabelAttr(S,1);Step 3.
FORj=1 TO |C| DO
IFNonEmptyLabel[j]==1 THEN R1=R1∪{cj};
END FORStep 4.
RETURNR1.Supposen=|U|, m=|C|. According to the conclusion of literature [45], the average time and space complexities of the Algorithm 4.3 are T=O(n×(m+logn)) and S=O(m+n).Obviously, Algorithm4.3 is an instance of Algorithm 3.13. Given an attribute order of the conditional attributes in a decision table, using the Algorithm 4.3 and divide and conquer method, an efficient attribute reduction algorithm is developed.Algorithm 4.4.
Computation of Attribute Reduction Based on Divide and Conquer Method
Input: A decision tableS=〈U,A,V,f〉 and an attribute order SO:c1≺c2≺···≺c|C|
Output: Attribute reductionR of S.Step 1.
U
1
1
=
U, R=ϕ.Step 2.
Compute the positive regionPosC(D), according to Algorithm 3.14.Step 3.
Compute the non-empty label attribute setR1 by Algorithm 4.3.Step 4.
//SupposecN be the maximum label attribute of R1.
R
=
R
∪
{
c
N
′
}
;
R
1
=
R
1
-
R;
IFR1==ϕ THEN RETURN R;
ELSE
Generate a new attribute order:
c11≺c21≺⋯≺c|R|1≺c12≺c22≺⋯≺c|R1|2;
Compute new non-empty label attribute setR1 of S by Algorithm 4.3;
GOTO Step  4.
END IFSupposen=|U| and m=|C|, the average time complexity of the Algorithm 4.4 is O(n×m×(m+logn)). Its space complexity is O(m+n).In Algorithm4.4, Step  1 is the initialization. In Step  2 of Algorithm 4.4, divide and conquer method is used to compute equivalence classes and positive region, thus Step  2 is an instance of Algorithm 3.13. In Step 3, Algorithm 4.3 is used to compute non-empty label attribute set (Algorithm 4.3 is also an instance of Algorithm 3.13). Step  4 is responding to Step  5 of Algorithm 3.13. In Step  4, Algorithm 4.3 is called repeatedly to reduce the redundant attribute set. That is, Algorithm 4.4 is composed of instances of Algorithm 4.3, which illustrates that Algorithm 4.4 is implemented by divide and conquer method. Basically, divide and conquer method is used primarily to compute equivalence classes, positive region, and non-empty label attribute set and delete element cells in discernibility matrix in Algorithm 4.4.


## 5. A Fast Algorithm for Value Reduction Based on Divide and Conquer Method

Proposition 5.1.
Given a decision tableS=〈U,A,V,f〉, for all x∈PosC(D), a certain rule can be induced by object x.Proposition 5.2.
Given a decision tableS=〈U,A,V,f〉, let us denote by DR a certain rule set of S. ∀di∈DR(1≤i≤|DR|)di, di must be induced by x(x∈PosC(D)).Proposition 5.3.
Given a decision tableS〈U,A,V,f〉, let us denote by DR certain rule set of S. For all x∈PosC(D), let us denote by d1 the certain rule by x. Let M1={Bxys∣y∈U}. Then, ∀α∈M1(M1≠ϕ)⇒∃c∈(d1∣C)(c∈α).According to Algorithm3.13, Propositions 5.1, 5.2, and 5.3, a recursive function and an algorithm for value reduction based on divide and conquer method are developed as follows.Function 2
DRAVDAC(S,cr)
//Denote by array CoreValueAttribute[] the result of value reduction of cr.
//The values of array CoreValueAttribute[] are all 0 initially.Step 1 (Ending Condition).
IF there is contradiction onS, THEN
return;
END IFStep 2 (Value reduction oncr based on divide and conquer method).
Step2.1 (Divide).
DivideS into k sub-decision tables S1,S2,…,Sk on attribute cr by using tolerance relation.
Step2.2 (Conquer sub-problems recursively).
Denote by arraySolui[|Ui|] the solution of Si.
Where,Si=〈Ui,(C-{cr})∪D,V,f〉.
FORi = 1 TO k DO
Solui = DRAVDAC(Si);
END FOR
Step2.3 (Merge the solutions).
FORj = 1 TO |U| DO
FORi =1 TO k DO
IFSolui[j] == 1 THEN break; END IF
END FOR
IFi==k+1 THEN CoreValueAttribute[j] =1 END IF
END FOR
END Function 2.Using Function 2, we present an algorithm for value reduction based on divide and conquer method (see Algorithm5.4).Algorithm 5.4.
An Algorithm for Value Reduction Based on Divide and Conquer Method
Input:A decision table S=〈U,A,V,f〉
Output: The certain rule setDR of S.Step 1 (Initiation).
A
S
e
t
=
ϕ, DR=ϕ.Step 2 (Compute the positive region).
According to Algorithm3.14, compute the positive region PosC(D) of S.Step 3 (Compute the non-empty label attribute).
Assume the order for dividing decision table bec1,c2,…,cm(m=|C|).
Compute the non-empty label attribute setASet by using Function 1.Step 4 (Value reduction on attribute setASet).
LetASet={c1′,c2′,…,c|ASet|′} and the divide order be c1′,c2′,…,c|ASet|′.
FOR i =|ASet| TO 1 DO
FORj = 1 TO |U| DO
CoreValueAttribute[j] = 0.
END FOR.
C=ASet.
Invoke Function 2: DRAVDAC(S,{ci′).
UpdateS, according to the array CoreValueAttribute[].
END FOR.Step 5 (Get the rule set).
FORi= 1 TO |U| DO
IFxi∈PosC(D) THEN
Construct a ruledi in terms with xi; DR=DR∪{di};
ENE IF
END FORStep 6.
RETURNDR.Suppose|C|=m,|U|=n. The time complexity of Step  1 is O(m+n). The average time complexities of Steps  2 and 3 are O(n×(m+logn)) [45]. The time complexities of Steps  5 and 6 are both O(m×n). Now, let us analyze the time complexity of Step  4.In Step  4, let the number of non-empty label attribute set beu. Then, the time complexity of Step  4 is O(u×(2n+T(1,n))), where T(1,n) is an instance of T(r,n) which can be expressed by the following recursive equation:
(5.1)T(r,n)={1.n==12n.r≥u2n+T(r+1,n).∀x,y∈U(TB(x,y)),(B={c1,c2,…,cr})pn+T(r,n1+n′)+T(r,n2+n′)+⋯+T(r,np+n′).(n1+n2+⋯+np+n′)=n,p=|{cr(x)∣cr(x)≠*,x∈U}|.T(1,n) is between O(u×n) and T(p1×p2×⋯×pu×n). So the time complexity of Step  4 is between O(u2×n) and T(u×p1×p2×⋯×pu×n). Thus, the time complexity of Algorithm 5.4 is between max(O(n×(m+logn)),O(u2×n)) and O(u×n×p1×p2×⋯×pu).Suppose the data obey the uniform distribution. The time complexity of Algorithm5.4 is O(nlog((p+1)/2)p×m)+O(n×m)=O(nlog((p+1)/2)p×m). When p≥2, the time complexity of Algorithm 5.4 is less than O(n2×m). When p≥5, the time complexity of Algorithm is less than O(n1.5×m).The space complexity of Algorithm5.4 is O(m×n).


## 6. Experimental Evaluations

In order to test the efficiency of knowledge reduction based on divide and conquer method, some experiments have been performed on a personal computer. The experiments are shown as follows.


### 6.1. The Experimental Evaluations on UCI Data Sets

In this experiment, some experimental evaluations are done to present the efficiency and recognition results of Algorithms4.4 and 5.4. In the mean time, some famous approaches for data mining are used to compare with our methods.The test course is as follows. First, 11 uci data sets (Zoo, Iris, Wine, Machine, Glass, Voting, Wdbc, Balance-scale, Breast, Crx, and Tic-tac-toe) are used. Second, our methods: the algorithm for discretization [14] (it is an improved one based on the discretization method in [28]), the algorithm for attribute reduction (Algorithm 4.4), and the algorithm for attribute value reduction (Algorithm 5.4) are used to test the 11 uci data sets. Third, 5 methods (KNN, SVM, C4.5, Naive Bayes, and CART) are also used to test the data sets, which belong to the “top 10 algorithms in data mining” [44], and their source codes are afforded by Weka software. Weka (http://en.wikipedia.org/wiki/Weka_(machine_l earning)) is used as the experimental plat and “Java Eclipse Weka” as the developing tool. The test method is LOOCV (Leave One Out Cross Validation). The specifications of the experimental computer are an Intel(R) Core(TM2) Quad CPU Q8200 @2.33 GHz CPU, 2 GB RAM, and Microsoft Windows 7. The specifications of 11 data sets and the experimental results are as follows.From Table1 and Figure 2, it can be found that the recognition results of our methods on the 11 uci data sets are closed to the ones of KNN and CART, which are better than Naive Bayes, C4.5, and SVM.Table 1
Specifications of 11 uci data sets.
Data sets
Number of records
Number of attributes
Number of decision values
Zoo
101
17
7
Iris
150
4
3
Wine
178
13
3
Machine
209
7
8
Glass
214
9
7
Voting
435
16
2
Wdbc
569
28
2
Balance scale
625
4
5
Breast
684
9
2
Crx
690
15
2
Tic-tac-toe
958
9
2Figure 2
Recognition result on uci data sets.


### 6.2. The Experimental Results on KDDCUP99 Data Sets

In order to test the efficiency of our methods for processing large data sets, some experiments are done on KDDCUP99 data sets with 4898432 records, 41 condition attributes, and 23 decision classifications (http://kdd.ics.uci.edu/databases//kddcup99/kddcup99.html). Our methods consist of the discretization algorithm [14], Algorithms 4.4, and 5.4 still. Weka is used as the experimental plat and “Java Eclipse Weka” as the developing tool (Table 2). The test method is 10 cross-validation. The specifications of the experimentation computer are an Intel(R) Core(TM2) Quad CPU Q8200 @2.33 GHz CPU, 4 GB RAM, and Microsoft Windows Server 2008. The experimental results are as follows.Table 2
The recognition of 6 algorithms on uci data sets.
Data sets
KNN
SVM
C4.5
Naive bayes
CART
Our methods
Zoo
0.9208
0.9603
0.8713
0.9702
0.9109
0.9208
Iris
0.9600
0.9467
0.9600
0.9533
0.9533
0.9467
Wine
0.9719
0.4887
0.8483
0.9775
0.8652
0.9607
Machine
0.8461
0.6490
0.8173
0.8173
0.8173
0.8894
Glass
0.7009
0.6963
0.5935
0.4953
0.7009
0.7149
Voting
0.9149
0.9333
0.9517
0.9425
0.9563
0.9333
Wdbc
0.9490
0.6274
0.9367
0.9349
0.9332
0.9139
Balance scale
0.9024
0.952
0.7488
0.9088
0.7920
0.7712
Breast
0.9570
0.3462
0.9399
0.9613
0.9399
0.9341
Crx
0.8710
0.5565
0.8232
0.7522
0.8406
0.7754
Tic-tac-toe
0.6952
1.0000
0.7328
0.7150
0.8779
0.9624
Average
0.8808
0.7415
0.8385
0.8571
0.8716
0.8839First, the experiments are done on 10 data sets (≤104 records) from the original KDDCUP99 data sets. The experimental evaluations are showed in Tables 3, 4, and 5, where the time unit is “ms” in Tables 4 and 5.Table 3
The recognition of 6 algorithms on KDDCUP99 data sets (≤104 records).
Number of records
KNN
SVM
C4.5
Naive bayes
CART
Our methods
1000
0.9950
0.9550
0.9800
0.9800
0.9870
0.9950
2000
0.9980
0.9700
0.9935
0.9925
0.9920
0.9935
3000
0.9977
0.9850
0.9947
0.9753
0.9950
0.9947
4000
0.9967
0.9750
0.9940
0.9483
0.9935
0.9940
5000
0.9984
0.9770
0.9956
0.9760
0.9958
0.9954
6000
0.9986
0.9791
0.9968
0.9553
0.9965
0.9975
7000
0.9980
0.9850
0.9958
0.9905
0.9951
0.9956
8000
0.9985
0.9831
0.9958
0.9555
0.9956
0.9965
9000
0.9983
0.9877
0.9970
0.9690
0.9955
0.9964
10000
0.9986
0.9880
0.9971
0.9449
0.9968
0.9971Table 4
The training time of 6 algorithms on KDDCUP99 data sets (≤104 records).
Number of records
KNN
SVM
C4.5
Naive bayes
CART
Our methods
1000
3
87
50
9
120
143
2000
3
259
47
12
173
78
3000
2
631
18
16
280
130
4000
0
1071
125
22
384
192
5000
0
1731
173
31
543
226
6000
0
2467
223
41
672
311
7000
0
3617
281
129
861
541
8000
2
4591
329
70
1155
822
9000
2
6171
364
178
1262
1261
10000
3
7496
378
96.7
1629
1415Table 5
The test time of 6 algorithms on KDDCUP99 data sets (≤104 records).
Number of records
KNN
SVM
C4.5
Naive bayes
CART
Our methods
1000
41
6
0
25
2
0
2000
122
9
0
34
0
0
3000
279
18
0
50
0
0
4000
495
40
0
67
0
0
5000
782
59
2
81
0
0
6000
1197
89
0
94
0
2
7000
1805
131
2
125
0
0
8000
2289
154
2
249
2
0
9000
2880
207
0
178
0
0
10000
3588
271
2
162
0
0From Tables3, 4, and 5, it can be found that it will cost much time to train by SVM, which shows that SVM is not a good way to process KDDCUP99 data sets with large records. Thus, in the following experiments, SVM will be not tested.Second, the experiments are done on 10 data sets (≤105 records) from the original KDDCUP99 data sets. The experimental evaluations are showed in Tables 6 and 7, where “Tr” is the training time, “Te” is the test time, and the time unit is “ms” in Table 7.Table 6
The recognition of 5 algorithms on KDDCUP99 data sets (≤105 records).
Number of records
KNN
C4.5
Naive bayes
CART
Our methods
10000
0.9985
0.9969
0.9804
0.9970
0.9973
20000
0.9987
0.9979
0.9490
0.9980
0.9980
30000
0.9990
0.9985
0.9560
0.9987
0.9987
40000
0.9989
0.9988
0.9365
0.9987
0.9989
50000
0.9991
0.9989
0.9613
0.9989
0.9989
60000
0.9992
0.9989
0.9627
0.9990
0.9989
70000
0.9992
0.9992
0.9438
0.9990
0.9990
80000
0.9992
0.9992
0.9249
0.9992
0.9992
90000
0.9992
0.9993
0.9097
0.9991
0.9992
100000
0.9992
0.9992
0.9118
0.9991
0.9992Table 7
The running time of 5 algorithms on KDDCUP99 data sets (≤105 records).
Number of records
KNN
C4.5
Naive bayes
CART
Our methods
Tr
Te
Tr
Te
Tr
Te
Tr
Te
Tr
Te
10000
2
3622
412
0
100
164
1632
0
1496
3
20000
3
15045
1225
0
281
321
4984
0
4367
0
30000
6
34592
2225
2
474
557
8964
0
8165
0
40000
9
60845
3582
5
704
774
15833
2
12815
5
50000
13
95023
5527
2
930
1045
19140
2
20003
6
60000
17
139299
7920
6
1167
1148
28805
2
30450
9
70000
22
196827
10084
9
1422
1438
31774
3
34909
2
80000
28
248624
12069
5
1688
2073
40056
3
39407
9
90000
27
310826
14461
10
1959
1716
44023
3
47688
6
100000
33
386018
16673
13
2185
2044
54288
3
49394
8From Tables6 and 7, it can be found that the recognition is lower than others by Naive Bayes and much test time is needed for KNN. Thus, Naive Bayes and KNN will be not tested in the following experiments.Third, the experiments are done on 10 data sets (≤106 records) from the original KDDCUP99 data sets. The experimental evaluations are showed in Table 8, where “RRate” is the recognition rate, “Tr” is the training time, “Te” is the testing time, and the time unit is “ms” in Table 8.Table 8
The experimental results of 3 algorithms on KDDCUP99 data sets (≤106 records).
Number of records
C4.5
CART
Our methods
RRate
Tr
Te
RRate
Tr
Te
RRate
Tr
Te
100000
0.9992
18730
31
0.9991
56208
8
0.9992
51692
24
200000
0.9997
52971
32
0.9994
113297
8
0.9995
113496
16
300000
0.9997
78118
47
0.9997
182997
0
0.9997
178769
31
400000
0.9998
111026
86
0.9997
327640
23
0.9997
313085
40
500000
0.9997
163746
94
0.9998
391179
16
0.9997
410342
55
600000
0.9998
218152
110
0.9996
446004
16
0.9997
538169
55
700000
0.9998
226879
125
0.9997
610749
24
0.9998
719630
78
800000
0.9999
387911
148
0.9999
1015165
32
0.9999
1143149
109
900000
0.9998
304466
195
0.9999
1595899
382
0.9998
1512619
133
1000000
0.9999
303403
203
0.9997
1583910
367
0.9998
1590494
140Fourth, the experiments are done on 10 data sets (<5×106 records) from the original KDDCUP99 data sets. The experimental results are showed in Table 9, where “RRate” is the recognition rate, “Tr” is the training time, “Te” is the testing time, “-” is the overflow of memory, and the time unit is “second” in Table 9.Table 9
The experimental results of 3 algorithms on KDDCUP99 data sets (<5 × 106 records).
Number of records
C4.5
CART
Our methods
RRate
Tr
Te
RRate
Tr
Te
RRate
Tr
Te
489843
0.9998
158
0.124
0.9997
386
0.031
0.9998
499
0.063
979686
0.9999
330
0.187
0.9998
1517
0.312
0.9998
1472
0.141
1469529
0.9999
706
0.312
0.9999
5851
5.554
0.9999
4026
0.156
1959372
0.9999
883
0.499
—
—
—
0.9999
6650
0.421
2449216
0.9999
1143
0.624
—
—
—
0.9999
11446
0.476
2939059
0.9999
1176
0.655
—
—
—
0.9999
14023
0.578
3428902
0.9999
1849
0.827
—
—
—
0.9999
35361
0.606
3918745
0.9999
2043
0.923
—
—
—
—
—
—
4408588
0.9999
2567
1.106
—
—
—
—
—
—
4898432
0.9999
2916
1.217
—
—
—
—
—
—From Tables8 and 9, it can be found that C4.5 is the best one and our method is the second best one among C4.5, CART, and our method. Due to the high complexity for discretization, our method can not complete the knowledge reduction of 4898432 records in this experiment.


### 6.3. The Conclusions of Experimental Evaluations

Now, we will give some conclusions for our approaches compared with KNN, SVM, C4.5, Naive Bayes, and CART, according to the LOOCV experimental results on the uci data sets and 10 cross-validation experimental results on KDDCUP99 data sets.(1)
Compared with KNN, SVM, and Naive Bayes, the LOOCV recognition results by our methods on uci data sets are better than KNN, SVM, and Bayes. Furthermore, our methods on KDDCUP99 data sets have higher efficiency than KNN, SVM, and Naive Bayes, while they also have good recognitions results.(2)
Compared with CART, the LOOCV recognition results by our methods on uci data sets are closed to CART. But our methods can process larger data sets than CART on KDDCUP99 data sets, while they both have good recognition results.(3)
Compared with C4.5, the LOOCV recognition results by our methods on uci data sets are better than C4.5. Furthermore, the test time by our methods on KDDCUP99 data sets is less than C4.5, while C4.5 can process larger data sets than our methods. After these two methods are analyzed, we find that our methods are more complex than C4.5, due to the complex discretization (C4.5 can process the decision table with continuous values directly, while the discretization should be necessary for our methods). As a coin has two sides, enough learning contributes to the better rule sets, thus less test time is needed by our methods than C4.5.Therefore, the knowledge reduction approaches based on divide and conquer method are efficient to process large data set, although they need to be improved further in the future.


## 6.1. The Experimental Evaluations on UCI Data Sets

In this experiment, some experimental evaluations are done to present the efficiency and recognition results of Algorithms4.4 and 5.4. In the mean time, some famous approaches for data mining are used to compare with our methods.The test course is as follows. First, 11 uci data sets (Zoo, Iris, Wine, Machine, Glass, Voting, Wdbc, Balance-scale, Breast, Crx, and Tic-tac-toe) are used. Second, our methods: the algorithm for discretization [14] (it is an improved one based on the discretization method in [28]), the algorithm for attribute reduction (Algorithm 4.4), and the algorithm for attribute value reduction (Algorithm 5.4) are used to test the 11 uci data sets. Third, 5 methods (KNN, SVM, C4.5, Naive Bayes, and CART) are also used to test the data sets, which belong to the “top 10 algorithms in data mining” [44], and their source codes are afforded by Weka software. Weka (http://en.wikipedia.org/wiki/Weka_(machine_l earning)) is used as the experimental plat and “Java Eclipse Weka” as the developing tool. The test method is LOOCV (Leave One Out Cross Validation). The specifications of the experimental computer are an Intel(R) Core(TM2) Quad CPU Q8200 @2.33 GHz CPU, 2 GB RAM, and Microsoft Windows 7. The specifications of 11 data sets and the experimental results are as follows.From Table1 and Figure 2, it can be found that the recognition results of our methods on the 11 uci data sets are closed to the ones of KNN and CART, which are better than Naive Bayes, C4.5, and SVM.Table 1
Specifications of 11 uci data sets.
Data sets
Number of records
Number of attributes
Number of decision values
Zoo
101
17
7
Iris
150
4
3
Wine
178
13
3
Machine
209
7
8
Glass
214
9
7
Voting
435
16
2
Wdbc
569
28
2
Balance scale
625
4
5
Breast
684
9
2
Crx
690
15
2
Tic-tac-toe
958
9
2Figure 2
Recognition result on uci data sets.


## 6.2. The Experimental Results on KDDCUP99 Data Sets

In order to test the efficiency of our methods for processing large data sets, some experiments are done on KDDCUP99 data sets with 4898432 records, 41 condition attributes, and 23 decision classifications (http://kdd.ics.uci.edu/databases//kddcup99/kddcup99.html). Our methods consist of the discretization algorithm [14], Algorithms 4.4, and 5.4 still. Weka is used as the experimental plat and “Java Eclipse Weka” as the developing tool (Table 2). The test method is 10 cross-validation. The specifications of the experimentation computer are an Intel(R) Core(TM2) Quad CPU Q8200 @2.33 GHz CPU, 4 GB RAM, and Microsoft Windows Server 2008. The experimental results are as follows.Table 2
The recognition of 6 algorithms on uci data sets.
Data sets
KNN
SVM
C4.5
Naive bayes
CART
Our methods
Zoo
0.9208
0.9603
0.8713
0.9702
0.9109
0.9208
Iris
0.9600
0.9467
0.9600
0.9533
0.9533
0.9467
Wine
0.9719
0.4887
0.8483
0.9775
0.8652
0.9607
Machine
0.8461
0.6490
0.8173
0.8173
0.8173
0.8894
Glass
0.7009
0.6963
0.5935
0.4953
0.7009
0.7149
Voting
0.9149
0.9333
0.9517
0.9425
0.9563
0.9333
Wdbc
0.9490
0.6274
0.9367
0.9349
0.9332
0.9139
Balance scale
0.9024
0.952
0.7488
0.9088
0.7920
0.7712
Breast
0.9570
0.3462
0.9399
0.9613
0.9399
0.9341
Crx
0.8710
0.5565
0.8232
0.7522
0.8406
0.7754
Tic-tac-toe
0.6952
1.0000
0.7328
0.7150
0.8779
0.9624
Average
0.8808
0.7415
0.8385
0.8571
0.8716
0.8839First, the experiments are done on 10 data sets (≤104 records) from the original KDDCUP99 data sets. The experimental evaluations are showed in Tables 3, 4, and 5, where the time unit is “ms” in Tables 4 and 5.Table 3
The recognition of 6 algorithms on KDDCUP99 data sets (≤104 records).
Number of records
KNN
SVM
C4.5
Naive bayes
CART
Our methods
1000
0.9950
0.9550
0.9800
0.9800
0.9870
0.9950
2000
0.9980
0.9700
0.9935
0.9925
0.9920
0.9935
3000
0.9977
0.9850
0.9947
0.9753
0.9950
0.9947
4000
0.9967
0.9750
0.9940
0.9483
0.9935
0.9940
5000
0.9984
0.9770
0.9956
0.9760
0.9958
0.9954
6000
0.9986
0.9791
0.9968
0.9553
0.9965
0.9975
7000
0.9980
0.9850
0.9958
0.9905
0.9951
0.9956
8000
0.9985
0.9831
0.9958
0.9555
0.9956
0.9965
9000
0.9983
0.9877
0.9970
0.9690
0.9955
0.9964
10000
0.9986
0.9880
0.9971
0.9449
0.9968
0.9971Table 4
The training time of 6 algorithms on KDDCUP99 data sets (≤104 records).
Number of records
KNN
SVM
C4.5
Naive bayes
CART
Our methods
1000
3
87
50
9
120
143
2000
3
259
47
12
173
78
3000
2
631
18
16
280
130
4000
0
1071
125
22
384
192
5000
0
1731
173
31
543
226
6000
0
2467
223
41
672
311
7000
0
3617
281
129
861
541
8000
2
4591
329
70
1155
822
9000
2
6171
364
178
1262
1261
10000
3
7496
378
96.7
1629
1415Table 5
The test time of 6 algorithms on KDDCUP99 data sets (≤104 records).
Number of records
KNN
SVM
C4.5
Naive bayes
CART
Our methods
1000
41
6
0
25
2
0
2000
122
9
0
34
0
0
3000
279
18
0
50
0
0
4000
495
40
0
67
0
0
5000
782
59
2
81
0
0
6000
1197
89
0
94
0
2
7000
1805
131
2
125
0
0
8000
2289
154
2
249
2
0
9000
2880
207
0
178
0
0
10000
3588
271
2
162
0
0From Tables3, 4, and 5, it can be found that it will cost much time to train by SVM, which shows that SVM is not a good way to process KDDCUP99 data sets with large records. Thus, in the following experiments, SVM will be not tested.Second, the experiments are done on 10 data sets (≤105 records) from the original KDDCUP99 data sets. The experimental evaluations are showed in Tables 6 and 7, where “Tr” is the training time, “Te” is the test time, and the time unit is “ms” in Table 7.Table 6
The recognition of 5 algorithms on KDDCUP99 data sets (≤105 records).
Number of records
KNN
C4.5
Naive bayes
CART
Our methods
10000
0.9985
0.9969
0.9804
0.9970
0.9973
20000
0.9987
0.9979
0.9490
0.9980
0.9980
30000
0.9990
0.9985
0.9560
0.9987
0.9987
40000
0.9989
0.9988
0.9365
0.9987
0.9989
50000
0.9991
0.9989
0.9613
0.9989
0.9989
60000
0.9992
0.9989
0.9627
0.9990
0.9989
70000
0.9992
0.9992
0.9438
0.9990
0.9990
80000
0.9992
0.9992
0.9249
0.9992
0.9992
90000
0.9992
0.9993
0.9097
0.9991
0.9992
100000
0.9992
0.9992
0.9118
0.9991
0.9992Table 7
The running time of 5 algorithms on KDDCUP99 data sets (≤105 records).
Number of records
KNN
C4.5
Naive bayes
CART
Our methods
Tr
Te
Tr
Te
Tr
Te
Tr
Te
Tr
Te
10000
2
3622
412
0
100
164
1632
0
1496
3
20000
3
15045
1225
0
281
321
4984
0
4367
0
30000
6
34592
2225
2
474
557
8964
0
8165
0
40000
9
60845
3582
5
704
774
15833
2
12815
5
50000
13
95023
5527
2
930
1045
19140
2
20003
6
60000
17
139299
7920
6
1167
1148
28805
2
30450
9
70000
22
196827
10084
9
1422
1438
31774
3
34909
2
80000
28
248624
12069
5
1688
2073
40056
3
39407
9
90000
27
310826
14461
10
1959
1716
44023
3
47688
6
100000
33
386018
16673
13
2185
2044
54288
3
49394
8From Tables6 and 7, it can be found that the recognition is lower than others by Naive Bayes and much test time is needed for KNN. Thus, Naive Bayes and KNN will be not tested in the following experiments.Third, the experiments are done on 10 data sets (≤106 records) from the original KDDCUP99 data sets. The experimental evaluations are showed in Table 8, where “RRate” is the recognition rate, “Tr” is the training time, “Te” is the testing time, and the time unit is “ms” in Table 8.Table 8
The experimental results of 3 algorithms on KDDCUP99 data sets (≤106 records).
Number of records
C4.5
CART
Our methods
RRate
Tr
Te
RRate
Tr
Te
RRate
Tr
Te
100000
0.9992
18730
31
0.9991
56208
8
0.9992
51692
24
200000
0.9997
52971
32
0.9994
113297
8
0.9995
113496
16
300000
0.9997
78118
47
0.9997
182997
0
0.9997
178769
31
400000
0.9998
111026
86
0.9997
327640
23
0.9997
313085
40
500000
0.9997
163746
94
0.9998
391179
16
0.9997
410342
55
600000
0.9998
218152
110
0.9996
446004
16
0.9997
538169
55
700000
0.9998
226879
125
0.9997
610749
24
0.9998
719630
78
800000
0.9999
387911
148
0.9999
1015165
32
0.9999
1143149
109
900000
0.9998
304466
195
0.9999
1595899
382
0.9998
1512619
133
1000000
0.9999
303403
203
0.9997
1583910
367
0.9998
1590494
140Fourth, the experiments are done on 10 data sets (<5×106 records) from the original KDDCUP99 data sets. The experimental results are showed in Table 9, where “RRate” is the recognition rate, “Tr” is the training time, “Te” is the testing time, “-” is the overflow of memory, and the time unit is “second” in Table 9.Table 9
The experimental results of 3 algorithms on KDDCUP99 data sets (<5 × 106 records).
Number of records
C4.5
CART
Our methods
RRate
Tr
Te
RRate
Tr
Te
RRate
Tr
Te
489843
0.9998
158
0.124
0.9997
386
0.031
0.9998
499
0.063
979686
0.9999
330
0.187
0.9998
1517
0.312
0.9998
1472
0.141
1469529
0.9999
706
0.312
0.9999
5851
5.554
0.9999
4026
0.156
1959372
0.9999
883
0.499
—
—
—
0.9999
6650
0.421
2449216
0.9999
1143
0.624
—
—
—
0.9999
11446
0.476
2939059
0.9999
1176
0.655
—
—
—
0.9999
14023
0.578
3428902
0.9999
1849
0.827
—
—
—
0.9999
35361
0.606
3918745
0.9999
2043
0.923
—
—
—
—
—
—
4408588
0.9999
2567
1.106
—
—
—
—
—
—
4898432
0.9999
2916
1.217
—
—
—
—
—
—From Tables8 and 9, it can be found that C4.5 is the best one and our method is the second best one among C4.5, CART, and our method. Due to the high complexity for discretization, our method can not complete the knowledge reduction of 4898432 records in this experiment.


## 6.3. The Conclusions of Experimental Evaluations

Now, we will give some conclusions for our approaches compared with KNN, SVM, C4.5, Naive Bayes, and CART, according to the LOOCV experimental results on the uci data sets and 10 cross-validation experimental results on KDDCUP99 data sets.(1)
Compared with KNN, SVM, and Naive Bayes, the LOOCV recognition results by our methods on uci data sets are better than KNN, SVM, and Bayes. Furthermore, our methods on KDDCUP99 data sets have higher efficiency than KNN, SVM, and Naive Bayes, while they also have good recognitions results.(2)
Compared with CART, the LOOCV recognition results by our methods on uci data sets are closed to CART. But our methods can process larger data sets than CART on KDDCUP99 data sets, while they both have good recognition results.(3)
Compared with C4.5, the LOOCV recognition results by our methods on uci data sets are better than C4.5. Furthermore, the test time by our methods on KDDCUP99 data sets is less than C4.5, while C4.5 can process larger data sets than our methods. After these two methods are analyzed, we find that our methods are more complex than C4.5, due to the complex discretization (C4.5 can process the decision table with continuous values directly, while the discretization should be necessary for our methods). As a coin has two sides, enough learning contributes to the better rule sets, thus less test time is needed by our methods than C4.5.Therefore, the knowledge reduction approaches based on divide and conquer method are efficient to process large data set, although they need to be improved further in the future.


## 7. Conclusions

In this paper, the abstract process of knowledge reduction based on divide and conquer method is concluded, which is original from the approaches under the equivalence relation and the one under the tolerance relation. Furthermore, an example for computing positive region of the decision table is introduced. After that, two algorithms for knowledge reduction based on divide and conquer method, including an algorithm for attribute reduction and an algorithm for attribute value reduction, are presented, respectively. The proposed algorithms are efficient to process the knowledge reduction on uci data sets and KDDCUP99 data set, according to the experimental evaluations. Therefore, the divide and conquer method is an efficient and, therefore, suitable method to be used to knowledge reduction algorithms in rough set theory. With this efficiency, widespread industrial application of rough set theory may become possible.



---

*Source: 864652-2012-11-29.xml*