# Positive Macroscopic Approximation for Fast Attribute Reduction

Authors: Zheng-Cai Lu; Zheng Qin; Qiao Jing; Lai-Xiang Shan
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Attribute reduction is one of the challenging problems facing the effective application of computational intelligence technology for artificial intelligence. Its task is to eliminate dispensable attributes and search for a feature subset that possesses the same classification capacity as that of the original attribute set. To accomplish efficient attribute reduction, many heuristic search algorithms have been developed. Most of them are based on the model that the approximation of all the target concepts associated with a decision system is dividable into that of a single target concept represented by a pair of definable concepts known as lower and upper approximations. This paper proposes a novel model called macroscopic approximation, considering all the target concepts as an indivisible whole to be approximated by rough set boundary region derived from inconsistent tolerance blocks, as well as an efficient approximation framework called positive macroscopic approximation (PMA), addressing macroscopic approximations with respect to a series of attribute subsets. Based on PMA, a fast heuristic search algorithm for attribute reduction in incomplete decision systems is designed and achieves obviously better computational efficiency than other available algorithms, which is also demonstrated by the experimental results.


---

## Body

## 1. Introduction

Rough set theory (RST) [1] is a powerful mathematical tool for dealing with imprecision, uncertainty, and vagueness. As an extension of traditional set theory supporting approximation in decision making, RST provides a well-established model that the approximation of an indefinable target concept is represented by a pair of definable concepts known as lower and upper approximations. In recent years, more and more attention has been paid to RST, and much success of its applications has already covered a variety of fields such as artificial intelligence, machine learning, and knowledge discovery [2–6].Attribute reduction is one of the key topics in RST, viewed as the strongest and most important result to distinguish RST from other theories [7]. Its task is just to eliminate reducible or dispensable attributes and search for a feature subset with the same classification capacity as that of the original attribute set. Much use has been made of attribute reduction as a preprocessing stage prior to classification of decision systems, making analysis algorithms more efficient and learned classifiers more compact.In attribute reduction, we encounter four general search strategies. The most intuitive one is the exhaustive search, which checks all the possible candidate subsets and retrieves those that satisfy the given criteria. The exhaustive search results in high time complexity and has been proved to be an NP-hard problem [8]. Another alternative way characterized by the incomplete search applies mapping and pruning techniques to minimization. It is achieved by mapping pertinent elements to a structured model and pruning useless branches in the search space [9, 10]. Similar to the exhaustive search, the incomplete search finds the minimal reduct at the expense of great computational effort. The third strategy for attribute reduction conducts a random search using the techniques such as genetic algorithm [11], ant colony optimization [12], and particle swarm optimization [13]. The random search provides a robust solution but is also computationally very expensive. The fourth and most practical strategy discovers feature subsets by the heuristic search, where attributes with high quality are preferred as heuristics according to an evaluation function [14–18]. The heuristic search has the ability to seek out an optimal or suboptimal reduct as well as acceptable computational complexity, playing an important role in the attribute reduction community.To accomplish efficient attribute reduction, much work has been devoted to developing heuristic search algorithms. From the viewpoint of evaluation functions, they can be classified into three main categories: positive region-based reduction [19–25], combination-based reduction [26–30], and entropy-based reduction [31–33].The positive region-based reduction takes the change of rough set positive region caused by the addition of an attribute as the significance of the attribute. Attributes with the highest significance are selected as heuristics to guide the search process. One of the classic instances is the quick reduct algorithm proposed by Chouchoulas and Shen [19], which can pick the best path to a reduct from the whole search space and receive many improved versions [20–22]. By using decomposition and sorting techniques to calculate positive region, Meng and Shi [23] put forward a fast positive region-based algorithm for feature selection from incomplete decision systems. Qian et al. [24, 25] constructed an efficient accelerator for heuristic search using a series of positive regions to approximate a given target decision on the gradually reduced universe. It can be incorporated into heuristic attribute reduction algorithms and make the modified versions capable of greatly reducing computational time.Unlike the positive region-based reduction, the combination-based reduction considers positive region as well as other available information such as rule support and boundary region. An attribute is evaluated by combined measure generated by positive region and additional information. With consideration of the overall quality of the potential set of rules, Zhang and Yao [27] introduced rule support into the evaluation function and proposed a support-oriented algorithm called parameterized average support heuristic (PASH), which selects features causing high average support of rule over all decision classes. Parthaláin and Shen [28] used distance metric to qualify the objects in the boundary region with regard to their proximity to the lower approximation and presented the distance metric-assisted tolerance rough set attribute reduction algorithm, which employs a new evaluation measure created by combining the distance metric and the dependency degree.Different from the above two categories, the entropy-based reduction gives the evaluation functions from the information view, such as combination entropy and rough entropy. Qian and Liang [32] presented the concept of combination entropy for describing the uncertainty of information systems and used its condition entropy to select a feature subset. Sun et al. [33] utilized rough entropy-based uncertainty measures to evaluate the roughness and accuracy of knowledge and then constructed a heuristic search algorithm with low computational complexity for attribute reduction in incomplete decision systems.These investigations have offered interesting insights into attribute reduction. When dealing with large incomplete data, however, they still suffer from computational inefficiency. A more efficient and feasible attribute reduction approach is really desirable. This paper just intends to provide such a solution.One can observe that most of heuristic attribute reduction algorithms are based on the model that the approximation of all the target concepts from a decision system is dividable into that of a single target concept represented by lower and upper approximations. Little work has hitherto taken the approximation problem into account at the macroscopic level. In this paper, we propose a novel model called macroscopic approximation, considering all the target concepts of a decision system as an indivisible whole to be approximated by rough set boundary region derived from inconsistent blocks, as well as an efficient approximation framework called positive macroscopic approximation (PMA), addressing macroscopic approximations with respect to a series of attribute subsets. Based on PMA, a fast heuristic attribute reduction algorithm for incomplete decision systems is designed and achieves obviously better computational efficiency than other available algorithms, which is also demonstrated by the experimental results.The remainder of this paper is organized as follows. In Section2, we review some basic concepts of RST and outline the quick reduct algorithm. Section 3 investigates macroscopic approximation and positive macroscopic approximation. In Section 4, a fast heuristic attribute reduction algorithm based on positive macroscopic approximation is devised and illustrated by a worked example. In Section 5, some experiments are practiced to validate the time efficiency of the proposed algorithm. Finally, we give a concise conclusion in Section 6.


## 2. Preliminaries

In this section, we briefly recall some basic concepts, such as incomplete decision system, tolerance relation, tolerance block, tolerance class, positive region, and boundary region, together with the quick reduct algorithm, needed in the following sections.


### 2.1. Basic Concepts

A decision system is an information system with distinction between decision attributes and condition attributes. It is generally formulated by a data table where columns are referred to as attributes and rows as objects of interest. If there exist objects that contain missing data, the decision system is incomplete; otherwise, it is complete.An incomplete decision system is a tupleS=(U,A), where U, called the universe of discourse, is a nonempty finite object set and A is an attribute set that consists of a condition attribute subset C and a decision attribute subset D. For any a∈A, there is a mapping f, f:U→Va, where Va is the value domain of a. VC={Va∣a∈C}∪{*} (where “*” stands for missing values) and VD={Vd∣d∈D} are the value domains of C and D, respectively. For convenience, the tuple S=(U,A) is usually denoted as S=(U,C∪D).LetS=(U,C∪D) be an incomplete decision system. For any subset P⊆C, P determines a binary relation, denoted by SIM(P), which is defined as
(1)SIM(P)={(u,v)∈U×U∣∀a∈P,f(u,a)=f(v,a)orf(u,a)=*orf(v,a)=*}.It is easily known that the binary relation is reflexive, symmetric, and intransitive, so it is a tolerance relation. UsingP-tolerance relation, the universe can be divided into many tolerance blocks such that πP={X∣X∈U/SIM(P)}, where X is a P-tolerance block and πP is the family of all the P-tolerance blocks on U, called a P-approximation space. A P-tolerance block depicts the collection of objects which are possibly indiscernible from each other with respect to P. If there does not exist another P-tolerance block Y such that X⊂Y, then X is called a maximal P-tolerance block [34].For any objectu∈U, P-tolerance relation determines the tolerance class of u, denoted by SP(u), that is, SP(u)={v∈U∣(u,v)∈SIM(P)}, describing the maximal set of objects which are probably indistinguishable to u with respect to P. There is a relationship between the tolerance class and the maximal tolerance block, shown as follows [34]:
(2)SP(u)=⋃X∈πmP(u)X,
where πmP(u) is the family of maximal P-tolerance blocks containing u. Then, it is easy to prove that
(3)SP(u)=⋃X∈πP(u)X,
where πP(u) is the family of P-tolerance blocks containing u.Consider a partitionπD={Di∣i=1,2,…,j} of U determined by D. πD is the family of all the decision classes derived from the decision system. Each decision class can be viewed as a target concept approximated by a pair of precise concepts which are known as lower and upper approximations. The dual approximations of a target concept Di are defined, respectively, as
(4)P_(Di)={u∈U∣SP(u)⊆Di},P-(Di)={u∈U∣SP(u)∩Di≠∅}.
The low approximation of Di is regarded as the maximal P-definable set contained in Di, whereas the upper approximation of Di is considered as the minimal P-definable set containing Di. If P_(Di)=P-(Di), then Di is a P-exact set; otherwise, it is a P-rough set.By the dual approximations, the universe of the decision system is partitioned into two mutually exclusive crisp regions: positive region and boundary region, defined, respectively, as(5)POSP(πD)=⋃i=1jP_(Di),(6)BNDP(πD)=⋃i=1j(P-(Di)-P_(Di)).
It can be perceived that the positive region is the collection of objects which are classified without any ambiguity into the target concepts using P-tolerance relation, while the boundary region is, in a sense, the undeterminable area of the universe, where none of the objects are classified with certainty into the target concepts as far as P is concerned. It is apparent that POSP(πD)∪BNDP(πD)=U and POSP(πD)∩BNDP(πD)=∅. If BNDP(πD)=∅ or POSP(πD)=U, we say that S is consistent; otherwise, it is inconsistent.


### 2.2. Rough Set Attribute Reduction

In RST environment, dependency degree of decision attribute setD to condition attribute set  P(P⊆C) is definable in terms of positive region:
(7)γP(D)=|POSP(πD)||U|,
where |POSP(πD)| and |U| are the cardinalities of POSP(πD) and U, respectively. If γP(D)=1, we say that D totally depends on P. If γP(D)<1, we say that D partially depends on P. If γP(D)=0, we say that D is completely independent of P. RST describes a variation of dependency degree caused by the addition of attribute a to P as the significance of a such that
(8)Sig(a,P,D)=γP∪{a}(D)-γP(D).
The bigger the significance value is, the more informative the attribute is. Accordingly, the quick reduct algorithm [19], regarded as a classical rough set attribute reduction algorithm, is constructed by iteratively adding the attribute with the highest significance to an attribute pool which begins with an empty set until the dependency value of the pool equals that of the set of the whole condition attributes. This process can be outlined by Algorithm 1.Algorithm 1:Quick reduct.
Inputs:
U: the universe
C: C={c1,c2,…,cn},  a condition attribute set
D: D={d}, a decision attribute set
Output:
red: a reduct ofC
Begin
Step  1.  Let red=∅ and R=C
Step  2.  Whileγred(D)≠γC(D) and R≠∅ do
Select an attributea∈R with Sig(a,red,D)=max(Sig(a,red,D)) where ai∈R
R=R-{a}
red=red∪{a}
Step  3. Outputred
End.


## 2.1. Basic Concepts

A decision system is an information system with distinction between decision attributes and condition attributes. It is generally formulated by a data table where columns are referred to as attributes and rows as objects of interest. If there exist objects that contain missing data, the decision system is incomplete; otherwise, it is complete.An incomplete decision system is a tupleS=(U,A), where U, called the universe of discourse, is a nonempty finite object set and A is an attribute set that consists of a condition attribute subset C and a decision attribute subset D. For any a∈A, there is a mapping f, f:U→Va, where Va is the value domain of a. VC={Va∣a∈C}∪{*} (where “*” stands for missing values) and VD={Vd∣d∈D} are the value domains of C and D, respectively. For convenience, the tuple S=(U,A) is usually denoted as S=(U,C∪D).LetS=(U,C∪D) be an incomplete decision system. For any subset P⊆C, P determines a binary relation, denoted by SIM(P), which is defined as
(1)SIM(P)={(u,v)∈U×U∣∀a∈P,f(u,a)=f(v,a)orf(u,a)=*orf(v,a)=*}.It is easily known that the binary relation is reflexive, symmetric, and intransitive, so it is a tolerance relation. UsingP-tolerance relation, the universe can be divided into many tolerance blocks such that πP={X∣X∈U/SIM(P)}, where X is a P-tolerance block and πP is the family of all the P-tolerance blocks on U, called a P-approximation space. A P-tolerance block depicts the collection of objects which are possibly indiscernible from each other with respect to P. If there does not exist another P-tolerance block Y such that X⊂Y, then X is called a maximal P-tolerance block [34].For any objectu∈U, P-tolerance relation determines the tolerance class of u, denoted by SP(u), that is, SP(u)={v∈U∣(u,v)∈SIM(P)}, describing the maximal set of objects which are probably indistinguishable to u with respect to P. There is a relationship between the tolerance class and the maximal tolerance block, shown as follows [34]:
(2)SP(u)=⋃X∈πmP(u)X,
where πmP(u) is the family of maximal P-tolerance blocks containing u. Then, it is easy to prove that
(3)SP(u)=⋃X∈πP(u)X,
where πP(u) is the family of P-tolerance blocks containing u.Consider a partitionπD={Di∣i=1,2,…,j} of U determined by D. πD is the family of all the decision classes derived from the decision system. Each decision class can be viewed as a target concept approximated by a pair of precise concepts which are known as lower and upper approximations. The dual approximations of a target concept Di are defined, respectively, as
(4)P_(Di)={u∈U∣SP(u)⊆Di},P-(Di)={u∈U∣SP(u)∩Di≠∅}.
The low approximation of Di is regarded as the maximal P-definable set contained in Di, whereas the upper approximation of Di is considered as the minimal P-definable set containing Di. If P_(Di)=P-(Di), then Di is a P-exact set; otherwise, it is a P-rough set.By the dual approximations, the universe of the decision system is partitioned into two mutually exclusive crisp regions: positive region and boundary region, defined, respectively, as(5)POSP(πD)=⋃i=1jP_(Di),(6)BNDP(πD)=⋃i=1j(P-(Di)-P_(Di)).
It can be perceived that the positive region is the collection of objects which are classified without any ambiguity into the target concepts using P-tolerance relation, while the boundary region is, in a sense, the undeterminable area of the universe, where none of the objects are classified with certainty into the target concepts as far as P is concerned. It is apparent that POSP(πD)∪BNDP(πD)=U and POSP(πD)∩BNDP(πD)=∅. If BNDP(πD)=∅ or POSP(πD)=U, we say that S is consistent; otherwise, it is inconsistent.


## 2.2. Rough Set Attribute Reduction

In RST environment, dependency degree of decision attribute setD to condition attribute set  P(P⊆C) is definable in terms of positive region:
(7)γP(D)=|POSP(πD)||U|,
where |POSP(πD)| and |U| are the cardinalities of POSP(πD) and U, respectively. If γP(D)=1, we say that D totally depends on P. If γP(D)<1, we say that D partially depends on P. If γP(D)=0, we say that D is completely independent of P. RST describes a variation of dependency degree caused by the addition of attribute a to P as the significance of a such that
(8)Sig(a,P,D)=γP∪{a}(D)-γP(D).
The bigger the significance value is, the more informative the attribute is. Accordingly, the quick reduct algorithm [19], regarded as a classical rough set attribute reduction algorithm, is constructed by iteratively adding the attribute with the highest significance to an attribute pool which begins with an empty set until the dependency value of the pool equals that of the set of the whole condition attributes. This process can be outlined by Algorithm 1.Algorithm 1:Quick reduct.
Inputs:
U: the universe
C: C={c1,c2,…,cn},  a condition attribute set
D: D={d}, a decision attribute set
Output:
red: a reduct ofC
Begin
Step  1.  Let red=∅ and R=C
Step  2.  Whileγred(D)≠γC(D) and R≠∅ do
Select an attributea∈R with Sig(a,red,D)=max(Sig(a,red,D)) where ai∈R
R=R-{a}
red=red∪{a}
Step  3. Outputred
End.


## 3. Positive Macroscopic Approximation

It is well known that approximation is one of the core ideas of RST. A target concept is approximated by the low and upper approximations. Likewise, a decision system can be viewed as a super concept to be approximated by the low and upper super approximations, where the family of all the target concepts from the decision system is considered as the super concept, the positive region or the complementary set of the boundary region of the decision system acts as the low super approximation, and the universe of the decision system serves as the upper super approximation. If the low super approximation equals the upper super approximation, the decision system is consistent or exact; otherwise, it is inconsistent or rough. From the observation, it is easily understood that the approximation of a decision system can be represented by the positive region or the boundary region.RST offers a feasible way to obtain the approximation of a decision system by means of that of a single target concept represented by lower and upper approximations as stated by (5) and (6). For convenience, this model is called microcosmic approximation. As opposed to microcosmic approximation, this section introduces a novel model called macroscopic approximation, where the approximation of a decision system is achieved by regarding all the target concepts as an inseparable entity to be approximated by the boundary region. Furthermore, we explore positive macroscopic approximation (PMA), which considers macroscopic approximations with respect to a series of attribute sets.


### 3.1. Macroscopic Approximation

Macrocosmic approximation is an alternative way to arrive at the approximation of a decision system by the boundary region. Due to an integral consideration of all the target concepts associated with a decision system, the low and upper approximations are unavailable. Affirmably, an attempt is deserved to pioneer a new avenue to macroscopic approximation. An inconsistent tolerance block, introduced in the following context, is capable of offering such a feasible solution.Definition 1.
LetS=(U,C∪D), P⊆C, and X∈πP. Then, X is said an inconsistent tolerance block (IT-block) if |λ(X)|>1 or a consistent tolerance block (CT-block), where λ(X)={f(u,d)∣u∈X} and |λ(X)| is the cardinality of λ(X).An IT-block describes a set ofP-definable objects with diverse class labels, implying that a group of P-indistinguishable objects have the divergence of decision making, whereas a CT-block depicts a collection of P-definable objects with the same class label, indicating that a group of P-indiscernible objects share the same decision making. Accordingly, πP are classified into two mutually exclusive crisp subfamilies. One is the consistent family, denoted by πPCT, collecting all the CT-blocks from πP such that πPCT={Y∈πP∣|λ(Y)|=1}. The other is the inconsistent family, denoted by πPIT, gathering all the IT-blocks from πP such that πPIT={Y∈πP∣|λ(Y)|>1}. Obviously, πPCT∪πPIT=πP and πPCT∩πPIT={∅}.It is worth noting the distinction between the boundary region and the IT-block. The former consists of objects of which tolerance classes cannot be entirely contained in target concepts, while the latter is such an entity that overlaps two or more target concepts. The following lemmas are used to investigate the relationship between them.Lemma 2.
LetS=(U,C∪D) and P⊆C. For any u∈BNDP(πD), there must exist at least one IT-block containing u.Proof.
This proof is done by contradiction. For anyu∈BNDP(πD), suppose that there does not exist any IT-block containing u. That is to say, any X∈πP(u) is a CT-block, which implies that there must exist some decision value d0 (d0∈VD) such that λ(X)=d0. d0 corresponds to a certain decision class D0 (D0∈πD) containing all the objects whose decision values are equal to d0, and then X⊆D0 and ⋃X∈πP(u)X⊆D0. So, SP(u)=⋃X∈πP(u)X⊆D0. This means that u∈POSP(πD), contradicted with u∈BNDP(πD). Hence, for any u∈BNDP(πD), there must exist at least one IT-block containing u. The lemma holds.Lemma 3.
LetS=(U,C∪D) and P⊆C. For any X∈πPIT, X⊆BNDP(πD).Proof.
For anyu∈X, we have SP(u)=SP′(u)∪X, where SP′(u)=⋃X′∈πP(u)X′. Since X∈πPIT, there is X⊄D0 for any D0∈πD (or if X⊆D0, then |λ(X)|=|λ(D0)|=1, and thereby X∈πPCT, contradicted with X∈πPIT). Hence, SP(u)=SP′(u)∪X⊄D0, which gives u∉POSP(πD). As POSP(πD)∪BNDP(πD)=U and POSP(πD)∩BNDP(πD)=∅ in S, u∉POSP(πD) implies that u∈BNDP(πD). Therefore, for any X∈πPIT and u∈X, there is u∈BNDP(πD). This means that X⊆BNDP(πD) for any X∈πPIT. The lemma holds.Theorem 4.
LetS=(U,C∪D) and P⊆C. Then, BNDP(πD)=⋃X∈πPITX.Proof.
For anyu∈BNDP(πD), according to Lemma 2, there must exist at least one tolerance block X containing u such that X∈πPIT, which yields BNDP(πD)⊆⋃X∈πPITX. On the other hand, for any X∈πPIT, by Lemma 3, we have X⊆BNDP(πD), which gives ⋃X∈πPITX⊆BNDP(πD). In summary, BNDP(πD)=⋃X∈πPITX. The theorem holds.Theorem4 reveals the relationship that the boundary region is the union of IT-blocks, which is in essence the materialization of macroscopic approximation by integrally approximating all the target concepts using the boundary region derived from IT-blocks. Unlike the microscopic approximation stated by (6), the macroscopic approximation is directly constructed on the elementary members of the approximation space rather than the low and upper approximations, making the calculation of the approximation of the decision system more efficient.


### 3.2. PMA

For a given decision system, we can build a series of attribute subsets according to the following rule. The first set has only one attribute selected from the set of the whole attributes, the union of the first set and another attribute chosen from the remaining attributes is regarded as the second set, and so on. The newly generated attribute subsets form an ascending order of the sequence, called a positive sequence. If a sequence is organized by a descending order, it is called a converse sequence. Assume that attribute subsetsA and B are two arbitrary elements of a positive sequence. If A contains B, we say that the tolerance relation determined by A is finer than that determined by B. Conversely, if A is contained in B, we say that the tolerance relation determined by A is coarser than that determined by B. Accordingly, a positive sequence determines a train of tolerance relations stretching from coarse to fine.In this subsection, we explore positive macroscopic approximation (PMA), which addresses macroscopic approximations with respect to a positive sequence. To construct an efficient PMA, the following relevant definitions and lemmas are needed.Definition 5.
LetS=(U,C∪D), P⊆C, a∈C-P, and X∈πP. Then, the family of subblocks determined by a on X is defined as
(9)θa(X)={{u∈X∣f(u,a)=borf(u,a)=*}∣b∈Va}.
The consistent and inconsistent subfamilies of θa(X) are defined as θaCT(X)={Y∈θa(X)∣|λ(Y)|=1} and θaIT(X)={Y∈θa(X)∣|λ(Y)|>1}, respectively. Apparently, θaCT(X)∪θaIT(X)=θa(X) and θaCT(X)∩θaIT(X)={∅}.Lemma 6.
LetS=(U,C∪D), P⊆C, a∈C-P, and X a CT-block. Then, any Y∈θa(X) is a CT-block and θaCT(X)=θa(X), θaIT(X)={∅}.Proof.
SinceX is a CT-block, |λ(X)|=1. Suppose that λ(X)=d0 (d0∈Vd), then f(u,d)=d0 for any u∈X. Y∈θa(X) means that Y⊆X, so we have v∈X for any v∈Y and f(v,d)=d0. Hence, λ(Y)=d0 and |λ(Y)|=1, which yields that Y is a CT-block. Moreover, θaCT(X)={Y∈θa(X)∣|λ(Y)|=1}=θa(X) and θaIT(X)={Y∈θa(X)∣|λ(Y)|>1}={∅}. The lemma holds.This lemma shows that any subblock derived from a CT-block is also a CT-block. In other words, inconsistent tolerance subblocks are derivable only from IT-blocks.Definition 7.
LetS=(U,C∪D), P⊆C, a∈C-P, and W a family of P-tolerance blocks. Then, the family of subblocks determined by a on W is defined as
(10)ωa(W)={θa(X)∣X∈W}.
The consistent and inconsistent subfamilies of ωa(W) are defined as ωaCT(W)={Y∈ωa(W)∣|λ(Y)|=1} and ωaIT(W)={Y∈ωa(W)∣|λ(Y)|>1}, respectively. Clearly, ωaCT(W)∪ωaIT(W)=ωa(W) and ωaCT(W)∩ωaIT(W)={∅}.Lemma 8.
LetS=(U,C∪D), P⊆C, a∈C-P, and W a family of CT-blocks. Then, any Y∈ωa(W) is a CT-block and ωaCT(W)=ωa(W), ωaIT(W)={∅}.Proof.
For anyX∈W, X is a CT-block. By Lemma 6, any Z∈θa(X) is also a CT-block, which yields that any Y∈{θa(X)∣X∈W}=ωa(W) is a CT-block. Since |λ(Y)|=1, ωaCT(W)={Y∈ωa(W)∣|λ(Y)|=1}=ωa(W) and ωaIT(W)={Y∈ωa(W)∣|λ(Y)|>1}={∅}. The lemma holds.Theorem 9.
LetS=(U,C∪D), P⊆C, and a∈C-P. Then, πP∪{a}IT=ωaIT(πPIT).Proof.
Assume thatP={a1,a2,…,at}. By (9) and (10), we have πP=ωat(⋯(ωa2(θa1(U)))⋯) and πP∪{a}=ωa(ωat(⋯(ωa2(θa1(U)))⋯)). Then, πP∪{a}=ωa(πP)=ωa(πPIT)∪ωa(πPCT). 									(11)πP∪{a}IT={X∈πP∪{a}∣|λ(X)|>1}={X∈ωa(πPIT)∪ωa(πPCT)∣|λ(X)|>1}={X∈ωa(πPIT)∣|λ(X)|>1}∪{X∈ωa(πPCT)∣|λ(X)|>1}=ωaIT(πPIT)∪ωaIT(πPCT).
By Lemma 8, ωaIT(πPCT)={∅}, and then πP∪{a}IT=ωaIT(πPIT). The theorem holds.Theorem9 indicates that πP∪{a}IT can be deduced by πPIT, which implies that the IT-blocks determined by the finer tolerance relation can be achieved by successively decomposing the IT-blocks determined by the coarser tolerance relation, regardless of corresponding CT-blocks. By Theorem 9, we arrive at an efficient PMA, embodied by Definition 10.Definition 10.
LetS=(U,C∪D), P⊆C with P={a1,a2,…,at}, and ρt=〈P1,P2,…,Pt〉 a positive sequence, where P1={a1}, P2={a1,a2},…, and Pt={a1,a2,…,at}. Then, PMA with respect to ρt can be defined as
(12)PMA(ρt)=〈BNDPt(πD)∣1≤i≤t〉,
where BNDPt(πD)=⋃X∈πPtITX, πPtIT=ωatIT(πPt-1IT), and πP1IT=ωa1IT({U})=θa1IT(U).PMA is in fact a sequence of boundary regions, each of which denotes the approximation of the decision system with respect to some attribute subset. Since the tolerance relations determined by the positive sequence are from coarse to fine, it is easily proved that corresponding boundary regions stretch from broad to narrow. In other words, PMA is the sequence of gradually reduced boundary regions. WhenP=C, PMA portrays in detail the evolution of boundary region becoming narrower and narrower until reaching the boundary region with respect to the set of the whole condition attributes.PMA provides an efficient approximation framework where a decision system is consecutively approximated by the boundary region derived from IT-blocks according to a positive sequence. This mechanism can be visualized in Figure1.Figure 1
Mechanism of PMA.PMA considers the universeU as a root IT-block and evaluates the boundary regions by repeatedly dividing the IT-blocks into the smaller ones with the positive sequence. For the attribute set P1, the attribute a1 works on the root IT-block and then outputs the consistent family πP1CT and the inconsistent family πP1IT. The former is pruned, while the latter is used to produce the boundary region BNDP1(πD) and serves as father IT-blocks for next operation. As for P2, πP2CT and πP2IT are generated by employing a2 to operate on πP1IT, and then BNDP2(πD) is derived from πP2IT. Likewise, we can obtain πPtCT and πPtIT calculated by using at to split πPt-1IT along with BNDPt(πD) induced by πPtIT. The detailed steps of this process are shown in Algorithm 2.Algorithm 2:PMA.
Inputs:
U: the universe
P

:
P
=
{
a
1
,
a
2
,
…
,
a
t
}
⊆
C, a condition attribute subset
D

:
D
=
{
d
}, a decision attribute set
Output:
PMA

(
ρ
t
): a family of boundary regions
Begin
Sept  1.PMA(ρt)=〈∅〉,  P0=∅,πP0IT={U} // regard the universe as a root IT-block
Step  2. Fori=1 to t do
Pi=Pi-1∪{ai}      // generate an element Pi of a positive sequence
πPiIT=ωaiIT(πPi-1IT)      // derive IT-blocks with respect to Pi from those with respect to Pi-1
BNDPi(πD)=∪{X∈πPiIT} // obtain the boundary region by means of IT-blocks
PMA(ρt)=PMA(ρt)+{BNDPi(πD)} // add the boundary region to the sequence
Step  3. OutputPMA(ρt)
End.PMA starts with an empty sequence; boundary regions with respect to a positive sequence are added incrementally. This process continues until all the attributes are traversed. For each loop, the boundary region is derivable from the corresponding IT-blocks obtained by operating on their predecessors with a single attribute.There are several highlights decorating PMA. First, the inconsistent family with respect to some attribute subsets inherits from its predecessor rather than starting all over again, which makes efficient use of the intermediate results. Second, the cardinality of the boundary region with respect to a fine tolerance relation is not more than the cardinality of the boundary region with respect to a coarse tolerance relation, indicating that PMA works on a gradually reduced universe. Finally, obtaining a series of boundary regions needs to traverse the entire condition attribute set just only once. All the advantages are beneficial for PMA to achieve better computational efficiency, which can be visible in the process of attribute reduction addressed in the next section. The following example is employed to illustrate this idea.Example 11.
Consider an incomplete decision systemS=(U,C∪D) showed in Table 1, where U={u1,u2,…,u6}, C={a1,a2,a3,a4}, and D={d}. The attributes a1,a2,a3,a4, and d stand for price, mileage, size, max-speed, and acceleration, respectively. Note that Table 1 is somewhat different from that in the literature [23, 34].Table 1
An incomplete decision system.
Car
Price
Mileage
Size
Max speed
Acceleration
u
1
High
High
Full
Low
Good
u
2
*
*
Full
Low
Good
u
3
*
*
Compact
Low
Poor
u
4
Low
*
Full
High
Good
u
5
*
*
Full
High
Excellent
u
6
High
High
Full
*
GoodLetP={a1,a2,a3,a4}. We can build a positive sequence ρ4 such that ρ4={P1,P2,P3,P4}, where P1={a1}, P2={a1,a2}, P3={a1,a2,a3}, and P4={a1,a2,a3,a4}. Applying a1 to the universe, we can get πP1IT and then BNDP1(πD):
(13)πP1IT={{u1,u2,u3,u5,u6},{u2,u3,u4,u5}},BNDP1(πD)={u1,u2,u3,u4,u5,u6}.
For P2, the attribute a2 is used to operate on πP1IT for πP2IT. The corresponding results are generated:
(14)πP2IT={{u1,u2,u3,u5,u6},{u2,u3,u4,u5}},BNDP2(πD)={u1,u2,u3,u4,u5,u6}.
Similarly, the results with respect to P3 and P4 are produced as follows:
(15)πP3IT={{u1,u2,u5,u6},{u2,u4,u5}},BNDP3(πD)={u1,u2,u4,u5,u6},πP4IT={{u4,u5},{u5,u6}},BNDP4(πD)={u4,u5,u6}.
Therefore, PMA with respect to ρ4 is achieved:(16)PMA(ρ4)=〈BNDP1(πD),BNDP2(πD),BNDP3(πD),BNDP4(πD)〉=〈{u1,u2,u3,u4,u5,u6},{u1,u2,u3,u4,u5,u6},{u1,u2,u4,u5,u6},{u4,u5,u6}〉.
It is clear that BNDP1(πD)⊇BNDP2(πD)⊇BNDP3(πD)⊇BNDP4(πD), which confirms the fact that the boundary region of PMA is gradually reduced in accordance with the positive sequence and finally catches up to the minimal boundary region (BNDC(πD)={u4,u5,u6}).


## 3.1. Macroscopic Approximation

Macrocosmic approximation is an alternative way to arrive at the approximation of a decision system by the boundary region. Due to an integral consideration of all the target concepts associated with a decision system, the low and upper approximations are unavailable. Affirmably, an attempt is deserved to pioneer a new avenue to macroscopic approximation. An inconsistent tolerance block, introduced in the following context, is capable of offering such a feasible solution.Definition 1.
LetS=(U,C∪D), P⊆C, and X∈πP. Then, X is said an inconsistent tolerance block (IT-block) if |λ(X)|>1 or a consistent tolerance block (CT-block), where λ(X)={f(u,d)∣u∈X} and |λ(X)| is the cardinality of λ(X).An IT-block describes a set ofP-definable objects with diverse class labels, implying that a group of P-indistinguishable objects have the divergence of decision making, whereas a CT-block depicts a collection of P-definable objects with the same class label, indicating that a group of P-indiscernible objects share the same decision making. Accordingly, πP are classified into two mutually exclusive crisp subfamilies. One is the consistent family, denoted by πPCT, collecting all the CT-blocks from πP such that πPCT={Y∈πP∣|λ(Y)|=1}. The other is the inconsistent family, denoted by πPIT, gathering all the IT-blocks from πP such that πPIT={Y∈πP∣|λ(Y)|>1}. Obviously, πPCT∪πPIT=πP and πPCT∩πPIT={∅}.It is worth noting the distinction between the boundary region and the IT-block. The former consists of objects of which tolerance classes cannot be entirely contained in target concepts, while the latter is such an entity that overlaps two or more target concepts. The following lemmas are used to investigate the relationship between them.Lemma 2.
LetS=(U,C∪D) and P⊆C. For any u∈BNDP(πD), there must exist at least one IT-block containing u.Proof.
This proof is done by contradiction. For anyu∈BNDP(πD), suppose that there does not exist any IT-block containing u. That is to say, any X∈πP(u) is a CT-block, which implies that there must exist some decision value d0 (d0∈VD) such that λ(X)=d0. d0 corresponds to a certain decision class D0 (D0∈πD) containing all the objects whose decision values are equal to d0, and then X⊆D0 and ⋃X∈πP(u)X⊆D0. So, SP(u)=⋃X∈πP(u)X⊆D0. This means that u∈POSP(πD), contradicted with u∈BNDP(πD). Hence, for any u∈BNDP(πD), there must exist at least one IT-block containing u. The lemma holds.Lemma 3.
LetS=(U,C∪D) and P⊆C. For any X∈πPIT, X⊆BNDP(πD).Proof.
For anyu∈X, we have SP(u)=SP′(u)∪X, where SP′(u)=⋃X′∈πP(u)X′. Since X∈πPIT, there is X⊄D0 for any D0∈πD (or if X⊆D0, then |λ(X)|=|λ(D0)|=1, and thereby X∈πPCT, contradicted with X∈πPIT). Hence, SP(u)=SP′(u)∪X⊄D0, which gives u∉POSP(πD). As POSP(πD)∪BNDP(πD)=U and POSP(πD)∩BNDP(πD)=∅ in S, u∉POSP(πD) implies that u∈BNDP(πD). Therefore, for any X∈πPIT and u∈X, there is u∈BNDP(πD). This means that X⊆BNDP(πD) for any X∈πPIT. The lemma holds.Theorem 4.
LetS=(U,C∪D) and P⊆C. Then, BNDP(πD)=⋃X∈πPITX.Proof.
For anyu∈BNDP(πD), according to Lemma 2, there must exist at least one tolerance block X containing u such that X∈πPIT, which yields BNDP(πD)⊆⋃X∈πPITX. On the other hand, for any X∈πPIT, by Lemma 3, we have X⊆BNDP(πD), which gives ⋃X∈πPITX⊆BNDP(πD). In summary, BNDP(πD)=⋃X∈πPITX. The theorem holds.Theorem4 reveals the relationship that the boundary region is the union of IT-blocks, which is in essence the materialization of macroscopic approximation by integrally approximating all the target concepts using the boundary region derived from IT-blocks. Unlike the microscopic approximation stated by (6), the macroscopic approximation is directly constructed on the elementary members of the approximation space rather than the low and upper approximations, making the calculation of the approximation of the decision system more efficient.


## 3.2. PMA

For a given decision system, we can build a series of attribute subsets according to the following rule. The first set has only one attribute selected from the set of the whole attributes, the union of the first set and another attribute chosen from the remaining attributes is regarded as the second set, and so on. The newly generated attribute subsets form an ascending order of the sequence, called a positive sequence. If a sequence is organized by a descending order, it is called a converse sequence. Assume that attribute subsetsA and B are two arbitrary elements of a positive sequence. If A contains B, we say that the tolerance relation determined by A is finer than that determined by B. Conversely, if A is contained in B, we say that the tolerance relation determined by A is coarser than that determined by B. Accordingly, a positive sequence determines a train of tolerance relations stretching from coarse to fine.In this subsection, we explore positive macroscopic approximation (PMA), which addresses macroscopic approximations with respect to a positive sequence. To construct an efficient PMA, the following relevant definitions and lemmas are needed.Definition 5.
LetS=(U,C∪D), P⊆C, a∈C-P, and X∈πP. Then, the family of subblocks determined by a on X is defined as
(9)θa(X)={{u∈X∣f(u,a)=borf(u,a)=*}∣b∈Va}.
The consistent and inconsistent subfamilies of θa(X) are defined as θaCT(X)={Y∈θa(X)∣|λ(Y)|=1} and θaIT(X)={Y∈θa(X)∣|λ(Y)|>1}, respectively. Apparently, θaCT(X)∪θaIT(X)=θa(X) and θaCT(X)∩θaIT(X)={∅}.Lemma 6.
LetS=(U,C∪D), P⊆C, a∈C-P, and X a CT-block. Then, any Y∈θa(X) is a CT-block and θaCT(X)=θa(X), θaIT(X)={∅}.Proof.
SinceX is a CT-block, |λ(X)|=1. Suppose that λ(X)=d0 (d0∈Vd), then f(u,d)=d0 for any u∈X. Y∈θa(X) means that Y⊆X, so we have v∈X for any v∈Y and f(v,d)=d0. Hence, λ(Y)=d0 and |λ(Y)|=1, which yields that Y is a CT-block. Moreover, θaCT(X)={Y∈θa(X)∣|λ(Y)|=1}=θa(X) and θaIT(X)={Y∈θa(X)∣|λ(Y)|>1}={∅}. The lemma holds.This lemma shows that any subblock derived from a CT-block is also a CT-block. In other words, inconsistent tolerance subblocks are derivable only from IT-blocks.Definition 7.
LetS=(U,C∪D), P⊆C, a∈C-P, and W a family of P-tolerance blocks. Then, the family of subblocks determined by a on W is defined as
(10)ωa(W)={θa(X)∣X∈W}.
The consistent and inconsistent subfamilies of ωa(W) are defined as ωaCT(W)={Y∈ωa(W)∣|λ(Y)|=1} and ωaIT(W)={Y∈ωa(W)∣|λ(Y)|>1}, respectively. Clearly, ωaCT(W)∪ωaIT(W)=ωa(W) and ωaCT(W)∩ωaIT(W)={∅}.Lemma 8.
LetS=(U,C∪D), P⊆C, a∈C-P, and W a family of CT-blocks. Then, any Y∈ωa(W) is a CT-block and ωaCT(W)=ωa(W), ωaIT(W)={∅}.Proof.
For anyX∈W, X is a CT-block. By Lemma 6, any Z∈θa(X) is also a CT-block, which yields that any Y∈{θa(X)∣X∈W}=ωa(W) is a CT-block. Since |λ(Y)|=1, ωaCT(W)={Y∈ωa(W)∣|λ(Y)|=1}=ωa(W) and ωaIT(W)={Y∈ωa(W)∣|λ(Y)|>1}={∅}. The lemma holds.Theorem 9.
LetS=(U,C∪D), P⊆C, and a∈C-P. Then, πP∪{a}IT=ωaIT(πPIT).Proof.
Assume thatP={a1,a2,…,at}. By (9) and (10), we have πP=ωat(⋯(ωa2(θa1(U)))⋯) and πP∪{a}=ωa(ωat(⋯(ωa2(θa1(U)))⋯)). Then, πP∪{a}=ωa(πP)=ωa(πPIT)∪ωa(πPCT). 									(11)πP∪{a}IT={X∈πP∪{a}∣|λ(X)|>1}={X∈ωa(πPIT)∪ωa(πPCT)∣|λ(X)|>1}={X∈ωa(πPIT)∣|λ(X)|>1}∪{X∈ωa(πPCT)∣|λ(X)|>1}=ωaIT(πPIT)∪ωaIT(πPCT).
By Lemma 8, ωaIT(πPCT)={∅}, and then πP∪{a}IT=ωaIT(πPIT). The theorem holds.Theorem9 indicates that πP∪{a}IT can be deduced by πPIT, which implies that the IT-blocks determined by the finer tolerance relation can be achieved by successively decomposing the IT-blocks determined by the coarser tolerance relation, regardless of corresponding CT-blocks. By Theorem 9, we arrive at an efficient PMA, embodied by Definition 10.Definition 10.
LetS=(U,C∪D), P⊆C with P={a1,a2,…,at}, and ρt=〈P1,P2,…,Pt〉 a positive sequence, where P1={a1}, P2={a1,a2},…, and Pt={a1,a2,…,at}. Then, PMA with respect to ρt can be defined as
(12)PMA(ρt)=〈BNDPt(πD)∣1≤i≤t〉,
where BNDPt(πD)=⋃X∈πPtITX, πPtIT=ωatIT(πPt-1IT), and πP1IT=ωa1IT({U})=θa1IT(U).PMA is in fact a sequence of boundary regions, each of which denotes the approximation of the decision system with respect to some attribute subset. Since the tolerance relations determined by the positive sequence are from coarse to fine, it is easily proved that corresponding boundary regions stretch from broad to narrow. In other words, PMA is the sequence of gradually reduced boundary regions. WhenP=C, PMA portrays in detail the evolution of boundary region becoming narrower and narrower until reaching the boundary region with respect to the set of the whole condition attributes.PMA provides an efficient approximation framework where a decision system is consecutively approximated by the boundary region derived from IT-blocks according to a positive sequence. This mechanism can be visualized in Figure1.Figure 1
Mechanism of PMA.PMA considers the universeU as a root IT-block and evaluates the boundary regions by repeatedly dividing the IT-blocks into the smaller ones with the positive sequence. For the attribute set P1, the attribute a1 works on the root IT-block and then outputs the consistent family πP1CT and the inconsistent family πP1IT. The former is pruned, while the latter is used to produce the boundary region BNDP1(πD) and serves as father IT-blocks for next operation. As for P2, πP2CT and πP2IT are generated by employing a2 to operate on πP1IT, and then BNDP2(πD) is derived from πP2IT. Likewise, we can obtain πPtCT and πPtIT calculated by using at to split πPt-1IT along with BNDPt(πD) induced by πPtIT. The detailed steps of this process are shown in Algorithm 2.Algorithm 2:PMA.
Inputs:
U: the universe
P

:
P
=
{
a
1
,
a
2
,
…
,
a
t
}
⊆
C, a condition attribute subset
D

:
D
=
{
d
}, a decision attribute set
Output:
PMA

(
ρ
t
): a family of boundary regions
Begin
Sept  1.PMA(ρt)=〈∅〉,  P0=∅,πP0IT={U} // regard the universe as a root IT-block
Step  2. Fori=1 to t do
Pi=Pi-1∪{ai}      // generate an element Pi of a positive sequence
πPiIT=ωaiIT(πPi-1IT)      // derive IT-blocks with respect to Pi from those with respect to Pi-1
BNDPi(πD)=∪{X∈πPiIT} // obtain the boundary region by means of IT-blocks
PMA(ρt)=PMA(ρt)+{BNDPi(πD)} // add the boundary region to the sequence
Step  3. OutputPMA(ρt)
End.PMA starts with an empty sequence; boundary regions with respect to a positive sequence are added incrementally. This process continues until all the attributes are traversed. For each loop, the boundary region is derivable from the corresponding IT-blocks obtained by operating on their predecessors with a single attribute.There are several highlights decorating PMA. First, the inconsistent family with respect to some attribute subsets inherits from its predecessor rather than starting all over again, which makes efficient use of the intermediate results. Second, the cardinality of the boundary region with respect to a fine tolerance relation is not more than the cardinality of the boundary region with respect to a coarse tolerance relation, indicating that PMA works on a gradually reduced universe. Finally, obtaining a series of boundary regions needs to traverse the entire condition attribute set just only once. All the advantages are beneficial for PMA to achieve better computational efficiency, which can be visible in the process of attribute reduction addressed in the next section. The following example is employed to illustrate this idea.Example 11.
Consider an incomplete decision systemS=(U,C∪D) showed in Table 1, where U={u1,u2,…,u6}, C={a1,a2,a3,a4}, and D={d}. The attributes a1,a2,a3,a4, and d stand for price, mileage, size, max-speed, and acceleration, respectively. Note that Table 1 is somewhat different from that in the literature [23, 34].Table 1
An incomplete decision system.
Car
Price
Mileage
Size
Max speed
Acceleration
u
1
High
High
Full
Low
Good
u
2
*
*
Full
Low
Good
u
3
*
*
Compact
Low
Poor
u
4
Low
*
Full
High
Good
u
5
*
*
Full
High
Excellent
u
6
High
High
Full
*
GoodLetP={a1,a2,a3,a4}. We can build a positive sequence ρ4 such that ρ4={P1,P2,P3,P4}, where P1={a1}, P2={a1,a2}, P3={a1,a2,a3}, and P4={a1,a2,a3,a4}. Applying a1 to the universe, we can get πP1IT and then BNDP1(πD):
(13)πP1IT={{u1,u2,u3,u5,u6},{u2,u3,u4,u5}},BNDP1(πD)={u1,u2,u3,u4,u5,u6}.
For P2, the attribute a2 is used to operate on πP1IT for πP2IT. The corresponding results are generated:
(14)πP2IT={{u1,u2,u3,u5,u6},{u2,u3,u4,u5}},BNDP2(πD)={u1,u2,u3,u4,u5,u6}.
Similarly, the results with respect to P3 and P4 are produced as follows:
(15)πP3IT={{u1,u2,u5,u6},{u2,u4,u5}},BNDP3(πD)={u1,u2,u4,u5,u6},πP4IT={{u4,u5},{u5,u6}},BNDP4(πD)={u4,u5,u6}.
Therefore, PMA with respect to ρ4 is achieved:(16)PMA(ρ4)=〈BNDP1(πD),BNDP2(πD),BNDP3(πD),BNDP4(πD)〉=〈{u1,u2,u3,u4,u5,u6},{u1,u2,u3,u4,u5,u6},{u1,u2,u4,u5,u6},{u4,u5,u6}〉.
It is clear that BNDP1(πD)⊇BNDP2(πD)⊇BNDP3(πD)⊇BNDP4(πD), which confirms the fact that the boundary region of PMA is gradually reduced in accordance with the positive sequence and finally catches up to the minimal boundary region (BNDC(πD)={u4,u5,u6}).


## 4. PMA-Based Attribute Reduction

As mentioned previously, PMA offers a sequence of the boundary regions in descending order. If each selected attribute is so informative that it makes the boundary region narrowed remarkably, the boundary region with respect to some attribute subsets can keep up with the boundary region with respect to the set of all the attributes. In other words, a reduct is the attribute subset with the minimal number that creates the same approximation of the decision system as the original attribute set. Following the observation, we design a heuristic attribute reduction algorithm based on PMA, called PMA-AR. Before elaborating PMA-AR, we give a redefinition of the attribute dependency.In (7), the dependency degree is definable in terms of positive region. Since positive region and boundary region are complementary within the universe of a decision system, the dependency degree can also be defined in terms of boundary region.Definition 12.
LetS=(U,C∪D), P⊆C, and a∈C-P, and the dependency degree of decision attribute set D to condition attribute set P is defined as
(17)γP(D)=1-|BNDP(πD)||U|.
Then, the significance of the attribute a is also equivalently redefined as
(18)Sig(a,P,D)=|BNDP(πD)|-|BNDP∪{a}(πD)||U|.
The significance expresses how the boundary region will be affected if the attribute a is added to the set P. In general, an attribute with a maximal significance value is preferentially selected to guide the search process.PMA-AR is in essence an extension of the quick reduct algorithm indicated previously. It marries PMA and the boundary region-based significance. The former provides an efficient way to compute the boundary region, and the latter acts as a router to determine the optimal search path. This effective combination allows PMA-AR to have the ability to locate a reduct efficiently. Algorithm3 gives the detailed description of PMA-AR.Algorithm 3:PMA-AR.
Inputs:
U: the universe
C

:
C
=
{
a
1
,
a
2
,
…
,
a
n
}, a condition attribute set
D

:
D
=
{
d
}, a decision attribute set
Output:
red: a reduct ofC
Begin
Sept  1.P=∅,πPIT={U},BNDP(πD)=U,R=C
Sept  2. ComputeBNDC(πD) by Algorithm 2
Step  3. WhileBNDP(πD)≠BNDC(πD) and R≠∅ do {
amax=null,πmaxIT=∅,BNDmax(πD)=∅,Sig(amax,P,D)=-1
For  i=1 to |R| do {
πP∪{ri}IT=ωriIT(πPIT) // ri denotes the No. i attribute in R
BNDP∪{ri}(πD)=∪{X∈πP∪{ri}IT}
Sig(ri,P,D)=(|BNDP(πD)|-|BNDP∪{ri}(πD)|)/|U|
If Sig(ri,P,D)>Sig(amax,P,D) then {
amax=ri,πmaxIT=πP∪{ri}IT,BNDmax(πD)=BNDP∪{ri}(πD)
Sig(amax,P,D)=Sig(ri,P,D)
} //end If
}//end For
P=P∪{amax},πPIT=πmaxIT,BNDP(πD)=BNDmax(πD),R=R-{amax}
}//end While
Step  4. Letred=PPMA-AR is constructed on PMA and employs the boundary region-based significance as the evaluation function to determine the positive sequence. A new attribute subset is achieved by this way. Each of the unselected attributes is used to work on the IT-blocks generated by the current attribute subset, and then corresponding boundary region is derived from the resulted IT-blocks. By evaluating the boundary region-based significance, the attribute with the biggest significance value is selected and added to the current attribute subset, which creates the expected attribute subset. This process continues until the boundary region with respect to the newly generated attribute subset equals the boundary region with respect to the set of all the attributes; equivalently, the dependency degree of the decision attribute set to the newly generated attribute subset is equal to that of the decision attribute set to the original attribute set.PMA-AR produces the shortest positive sequence together with the fastest evolution of the boundary regions from maximal to minimal. A hidden reduct is uncovered which makes use of the minimal attributes to describe the approximation of the decision system with respect to the set of all the attributes.Note that the time complexity of PMA-AR isO(|C||U|+∑i=1red(|C|-i)·|BNDPi(πD)|), which is dependent on Step 2 with O(|C||U|) and Step 3 with O(∑i=1red(|C|-i)·|BNDPi(πD)|), where |C| and |U| are the cardinalities of C and U, respectively. In the worst case where BNDPi(πD)=U and red=C, it is theoretically possible that PMA-AR takes time O(|C|2|U|). In fact, according to Algorithm 3, if BNDPi(πD)=U or red=C, PMA-AR costs time O(|C||U|), which implies that the practical time consumption is much less than O(|C|2|U|). Compared with the existing attribute reduction algorithms for incomplete decision systems with time complexities not less than O(|C|2|U|log|U|) [23, 33], PMA-AR achieves obviously lower time complexity. The following example is employed to illustrate the working process of PMA-AR.Example 13.
ConsiderS=(U,C∪D) described in Table 1, where U={u1,u2,…,u6}, C={a1,a2,a3,a4}, and D={d}. The attributes a1,a2,a3,a4, and d stand for price, mileage, size, max-speed, and acceleration, respectively.Unlike Example11, the positive sequence associated with PMA-AR is dynamically generated by iteratively selecting the attribute with the maximal significance value. To this end, the following results are produced:
(19)πP0∪{a1}IT={{u1,u2,u3,u5,u6},{u2,u3,u4,u5}},BNDP0∪{a1}(πD)={u1,u2,u3,u4,u5,u6},Sig(a1,P0,D)=0,πP0∪{a2}IT={{u1,u2,u3,u4,u5,u6}},BNDP0∪{a2}(πD)={u1,u2,u3,u4,u5,u6},Sig(a2,P0,D)=0,πP0∪{a3}IT={{u1,u2,u4,u5,u6}},BNDP0∪{a3}(πD)={u1,u2,u4,u5,u6},Sig(a3,P0,D)=16,πP0∪{a4}IT={{u1,u2,u3,u6},{u4,u5,u6}},BNDP0∪{a4}(πD)={u1,u2,u3,u4,u5,u6},Sig(a4,P0,D)=0.It is evident that the attributea3 with the maximal significance value is available and can be used to create the attribute subset P1={a3}. Then, πP1IT={{u1,u2,u4,u5,u6}} and BNDP1(πD)={u1,u2,u4,u5,u6}. Now, πP1IT is regarded as father IT-blocks to breed son IT-blocks by adding one of the remaining attributes to P1. From the newly generated IT-blocks, the boundary region is derivable. By evaluating the boundary region-based significance, the next expected attribute can be selected from the set of remaining attributes {a1,a2,a4}. The corresponding results are exhibited as follows:
(20)πP1∪{a1}IT={{u1,u2,u5,u6},{u2,u4,u5}},BNDP1∪{a1}(πD)={u1,u2,u4,u5,u6},Sig(a1,P1,D)=0,πP1∪{a2}IT={{u1,u2,u4,u5,u6}},BNDP1∪{a2}(πD)={u1,u2,u4,u5,u6},Sig(a2,P1,D)=0,πP1∪{a4}IT={{u4,u5},{u5,u6}},BNDP1∪{a4}(πD)={u4,u5,u6},Sig(a4,P1,D)=13.Thus, the attributea4 with the maximal significance value is preferably selected and used to generate another attribute subset P2={a3,a4}. Then, πP2IT={{u4,u5},{u5,u6}} and BNDP2(πD)={u4,u5,u6}. Since BNDP2(πD) is equal to BNDC(πD), P2 is just a reduct.As a result, the reduct of the decision system is{a3,a4}.


## 5. Experimental Evaluation

In the following, we carry out several experiments on a personal computer with Windows XP, 2.53 GHZ CPU, and 2.0 G memory so as to evaluate PMA-AR in terms of the number of selected features and running time.There are many heuristic search algorithms for attribute reduction in incomplete decision systems [17, 20, 23–25, 28, 33], of which three state-of-the-art algorithms are appropriate for comparison with PMA-AR. They are positive region-based algorithm (PRA) [23], distance metric-assisted algorithm (DMA) [28], and rough entropy-based algorithm (REA) [33], qualified as the representatives of positive region based reduction, combination-based reduction, and entropy-based reduction, respectively.Our experiments employ eight publicly accessible datasets from UCI repository of machine learning databases [35]. Each of them is a discrete dataset with only one decision attribute. Since PMA-AR is designed to deal with incomplete data, five complete datasets, such as balance scale weight and distance, tic-tac-toe end game, car evaluation, chess end game, and nursery, are all turned into incomplete ones by randomly replacing some known attribute values with missing ones. In addition, an identifier attribute of standardized audiology is removed. The characteristics of these datasets are described in Table 2.Table 2
Description of datasets.
No.
Dataset
Objects
Attributes
Classes
1
Lung cancer
32
56
3
2
Standardized audiology
200
69
24
3
Congressional voting
435
16
2
4
Balance scale weight and distance
625
4
3
5
Tic-tac-toe end game
958
9
2
6
Car evaluation
1728
6
4
7
Chess end game
3196
36
2
8
Nursery
12960
8
5The experiments are performed by applying the four algorithms (PRA, DMA, REA, and PMA-AR) to the eight datasets shown in Table2. The resulted number of selected features and running time expressed in seconds is exhibited in Tables 3 and 4, respectively.Table 3
Number of features selected by four algorithms.
No.
Dataset
DMA
REA
PRA
PMA-AR
1
Lung cancer
4
4
4
4
2
Standardized audiology
21
21
22
22
3
Congressional voting
8
8
9
9
4
Balance scale weight and distance
4
4
4
4
5
Tic-tac-toe end game
7
8
8
8
6
Car evaluation
6
6
6
6
7
Chess end game
26
28
29
29
8
Nursery
8
8
8
8Table 4
Running time of four algorithms.
No.
Dataset
DMA
REA
PRA
PMA-AR
1
Lung cancer
1.054
0.817
0.849
0.808
2
Standardized audiology
7.132
3.167
3.363
1.564
3
Congressional voting
2.657
1.301
1.365
1.107
4
Balance scale weight and distance
2.548
1.211
1.306
0.910
5
Tic-tac-toe end game
14.745
6.694
7.703
1.834
6
Car evaluation
46.889
15.660
17.503
2.303
7
Chess end game
384.416
105.985
128.153
8.445
8
Nursery
569.490
139.974
179.430
9.224From Table3, it can be observed that the number of features selected by PMA-AR is the same as that by PRA but not less than those by DMA and REA. On the whole, the numbers by the four algorithms are relatively approximate. This indicates that the performances of the four algorithms are very close, though DMA and REA perform a little better than PMA-AR and PRA.On the other hand, Table4 shows that for each dataset, DMA needs the most time, PRA and REA get the second and third place, respectively, and PMA-AR need the lest. Moreover, the running time of DMA, PRA, and REA increases much more rapidly than that of PMA-AR. The differences can be illustrated by plotting the ratios of DMA, PRA, and REA to PMA-AR, respectively, as shown in Figure 2.Figure 2
Ratios of DMA, PRA, and REA to PMA-AR.From Figure2, we can find that the curve corresponding to DMA/PMA-AR increases most rapidly, and the curve corresponding to PRA/PMA-AR increases slightly rapidly than that corresponding to REA/PMA-AR. The experimental result coincides with the theoretical analysis that the time complexity of DMA is not less than O(|C|2|U|2), which is the highest among all four algorithms; the second one is PRA, of which the time complexity is O(|C|2|U|log|U|). Following PRA, REA has the time complexity not more than O(|C|2|U|log|U|), and the most efficient one is PMA-AR with the time complexity much less than O(|C|2|U|). It is verified that PMA-AR achieves the best performance in terms of time efficiency.One can also observe that although each curve tends to increase with size of datasets, it is not strictly monotonic, namely, the curves fluctuate significantly. This can be seen from the case that the ratio of DMA to PMA-AR on Dataset 2 is higher than that on Dataset 3. The main reason is that the attribute number of datasets is different, and more importantly, the number of selected features is also different. For example, Dataset 2 has 69 attributes, of which 21 features are selected, while Dataset 3 has 16 attributes, and 8 features are selected. Furthermore, the curves also indicate that when the number of attributes is far less than that of objects, the running time mainly relies on the latter. This supports the conclusion that PMA-AR is more suitable for feature selection from large data than the other three algorithms because it is proportional to|U|.


## 6. Conclusions

Attribute reduction in incomplete decision systems has been a hotspot of rough set-based data analysis. To efficiently obtain a feature subset, many heuristic attribute reduction algorithms have been studied. Unfortunately, these algorithms are still computationally costly for large data. This paper has developed PMA-AR, which has the ability to find a feature subset as well as obviously better computational efficiency.Unlike other algorithms featured by microcosmic approximation, PMA-AR adopts a novel model called macrocosmic approximation, which considers all the target concepts of a decision system as an indivisible whole to be approximated by rough set boundary region derived from IT-blocks. Constructed on PMA which serves as an accelerator for calculation of boundary region, PMA-AR is capable of efficiently identifying a reduct by using the boundary region-based significance as the evaluation function. Both theoretical analysis and experimental results demonstrate that PMA-AR indeed outperforms other available algorithms with regard to time efficiency.



---

*Source: 837281-2013-05-14.xml*