# Parallel Attribute Reduction Algorithm for Complex Heterogeneous Data Using MapReduce

Authors: Tengfei Zhang; Fumin Ma; Jie Cao; Chen Peng; Dong Yue
Journal: Complexity
 (2018)

---

## Abstract

Parallel attribute reduction is one of the most important topics in current research on rough set theory. Although some parallel algorithms were well documented, most of them are still faced with some challenges for effectively dealing with the complex heterogeneous data including categorical and numerical attributes. Aiming at this problem, a novel attribute reduction algorithm based on neighborhood multigranulation rough sets was developed to process the massive heterogeneous data in the parallel way. The MapReduce-based parallelization method for attribute reduction was proposed in the framework of neighborhood multigranulation rough sets. To improve the reduction efficiency, the hashing Map/Reduce functions were designed to speed up the positive region calculation. Thereafter, a quick parallel attribute reduction algorithm using MapReduce was developed. The effectiveness and superiority of this parallel algorithm were demonstrated by theoretical analysis and comparison experiments.


---

## Body

## 1. Introduction

With the rapid development of information technology, especially in the aspects of sensing, communication, network, and calculation, the amount of accumulated data in many fields is increasing at striking speeds. The inestimable value in big data has become a common understanding in academia and industry [1] and has garnered great attention in many counties; thus, big data technology development was announced as a national strategy by many countries [2]. However, most of the vast array of data that comes to us may be chaotic, irrelevant, and redundant. How to extract and express such implicit information in the form of explicit knowledge hidden in the given complex information systems has been an active area of research in the past number of decades. In practice, rough sets [3] have been widely used as a mathematical tool to deal with uncertain data. As one of the core research contents of rough set theory, attribute reduction can remove redundant attributes and reduce data dimensions under the premise of stable dependencies between decision attributes and conditional attributes in a decision table. Scholars have designed a large number of attribute reduction algorithms in recent years, which can generally be divided into three methods [4]: positive region [5–7], discernible matrix [8–11], and information entropy [12–15]. However, the execution of these algorithms is a typical serial operation. Although these kinds of algorithms with serial operation are possible to handle small data efficiently, their computational complexity, which depends on attribute number ∣C∣ and sample size ∣U∣, may inevitably lead to lower efficiency and/or even complete failure when facing massive data.In order to solve this problem, some scholars have proposed parallel algorithms for high-dimensional or large-scale data. Based on the divide and conquer strategy, Xiao et al. [16] used parallel computing to divide the reduction task into multiple processors that process simultaneously. Rough entropy was used to measure attribute significance by Lv et al. [17], and a parallel minimum reduction set algorithm was proposed. However, the dataset should be loaded at once into the memory when implementing these algorithms. To make up for the defects of the aforementioned parallel algorithms, the Google File System- (GFS-) based distributed file system and the MapReduce parallel programming model were utilized by Qian et al. [18, 19]. The decision table was divided into several subdecision tables, and thus, a large amount of data did not need to be loaded into a single memory bank when calculating attribute reduction. Moreover, the machines in the cluster can cooperate with each other to solve problems that the single machine could not address. Zhang et al. [20] proposed a parallel method for computing rough set approximations based on the MapReduce technique to deal with the massive data. The equivalence classes for each subdecision table were calculated parallelly in Map step; thereafter, these equivalence classes were combined in Reduce step if their information sets are the same. Qian et al. [21] further analyzed that the key to improving the reduction efficiency is the effective computation of equivalence classes and attribute significance. Consequently, a structure of <key, value> pair to speed up the computation of equivalence classes and attribute significance was designed and the traditional attribute reduction process was parallelized based on MapReduce mechanism. However, these abovementioned algorithms were based on the Pawlak’s classic rough set model with an equivalence relation, which is only suitable for categorical data.To break the limit of the equivalence relation, Lin [22] proposed the concept of the neighborhood model and adopted the neighborhood relation instead of the equivalent relation, which can directly deal with numerical data through the neighborhood granulation in the universe. The monotonic relation between the positive region and attribute set in the neighborhood rough set model was proved by Hu et al. [23, 24], and an attribute reduction algorithm with lower computational complexity, which is suitable for heterogeneous data including categorical and numerical attributes, was put forward. Qian et al. [25] extended Pawlak’s rough set model to a multigranulation rough set (MGRS) model, where the set approximations are defined by using multiple equivalence relations on the universe. Based on the pessimistic multigranulation rough set model, Sang and Qian [26] analyzed a granular space selection under multiple granular spaces, defined the importance measure of the granular space, and designed a granular space reduction algorithm. Subsequently, Lin et al. [27] expanded the neighborhood rough set model to multiple granular spaces and proposed the concept of a neighborhood multigranulation rough set (NMGRS) model by constructing the universe through a hierarchical division of attribute set sequences. Furthermore, Yong et al. [28] hashed a dataset by dividing data into a series of hash buckets according to the Euclidean distance, which dramatically decreased the calculation time and reduced time complexity to Om∣U∣ for getting positive regions. A quick and efficient attribute reduction algorithm with the time complexity of Om2∣U∣ was also given. In addition, Qian et al. discussed local rough set to deal with big data [29, 30]. However, these aforementioned algorithms based on different extended rough set models were still involved in the serial computation.To the best of our knowledge, it is still a challenging task to perform parallel attribute reduction on complex and massive data. In particular, the existing algorithms could not effectively deal with the complex heterogeneous data, which include categorical and numerical attributes, in the parallel way from the multiple granular computing perspectives. Due to the rampant existence of heterogeneous datasets in real-life applications, it is therefore necessary to investigate effective parallel approaches to deal with this issue. For the purpose of parallelizing the traditional attribute reduction algorithm for complex heterogeneous data, the neighborhood multigranulation rough set model was considered in this paper, and the parallelization points of the hashing, positive region calculating, and boundary objects pruning are analyzed based on MapReduce mechanism. Thereafter, a fast parallel attribute reduction algorithm is developed. The effectiveness and superiority of this parallel algorithm were demonstrated by theoretical analysis and comparison experiments.Different from available algorithms, the contribution of this paper is twofold. (1) Motivated by the aforementioned MapReduce technology, hash algorithm, and neighborhood multigranulation rough set model, the parallelization methods of multiple granular spaces and hashing Map/Reduce functions for heterogeneous data are brought to light; 2) a neighborhood multigranulation rough set model-based parallel attribute reduction algorithm using MapReduce, which has never been done before, is proposed.The paper is organized as follows. Section2 outlines some preliminary knowledge. In Section 3, we present the parallelization strategies of multiple granular spaces for heterogeneous data and the parallel fast attribute reduction algorithm based on the neighborhood multigranulation rough set model. Next, experiments are conducted to evaluate the efficiency of the proposed algorithm in Section 4. Finally, in Section 5, we present the conclusion and the future work.


## 2. Preliminary Knowledge

In this section, 1-type and 2-type neighborhood multigranulation rough sets and MapReduce programming model will be briefly described.


### 2.1. Neighborhood Multigranulation Rough Set

Neighborhood rough set model uses neighborhood relation to replace equivalence relation, which can directly process numerical data and heterogeneous data. For further processing heterogeneous data from the perspective of multiple granular spaces and multiple levels of granularity, neighborhood rough set theory has been extended from single attribute subset to multiple attribute subsets. Two types of neighborhood multigranulation rough set models have been developed [27].


#### 2.1.1. 1-Type Neighborhood Multigranulation Rough Sets (1-Type NMGRS)

Definition 1 (see [25]).
Let<U,Δ> be a nonempty metric space; U=x1,x2,…,xn is a nonempty finite set of objects, called the universe. A closed ball taking x∈U as its center and δ as its radius is called the δ neighborhood of x and is defined as follows:
(1)nx=y∈U∣Δx,y≤δ,where δ≥0, and Δ is a distance function. For two points in the universe, xi=xi1,xi2,…,xin and xj=xj1,xj2,…,xjn, the distance function can usually use the Euclidean distance formula.
(2)Δxi,xj=∑l=1nxil−xjl2.Definition 2 (see [25]).
Let<U,Δ> be a nonempty metric space. When categorical and numerical attributes coexist, let B1 and B2 be categorical and numerical attributes, respectively. The neighborhood of x can be defined as follows:
(3)nB1x=xi∈U∣ΔB1x,xi=0,nB2x=xi∈U∣ΔB2x,xi≤δ,nB1∪B2x=xi∈U∣ΔB1x,xi=0∧ΔB2x,xi≤δ.Definition 3 (see [25]).
Given a decision system,NIS=U,C∪D,V,f,N, where C=c1,c2,c3,…,cm is the set of condition attributes and D is the set of decision attributes, and C∩D=∅. V=∪a∈RVa is a set of attribute values and Va is a domain of the attribute a. f:U×R→V is a function such that fx,a∈Va for every a∈C and x∈U. N is the neighborhood relation. Let A⊆C be a categorical attribute set and B⊆C be a numerical attribute set, so A∪B⊆C is an mixed attribute set; U/A, U/B, and U/A∪B represent two partitions and a covering of the universe U, respectively. For any X⊆U, the optimistic multigranulation lower and upper approximations of X with respect to A and B in U are defined as follows:
(4)A+B¯OX=x∈U∣nAx⊆X∨nBx⊆X,A+B¯OX=~A+B¯O~X,whereas the pessimistic multigranulation lower and upper approximations of X are defined as follows:
(5)A+B¯PX=x∈U∣nAx⊆X∧nBx⊆X,A+B¯PX=~A+B¯P~X.


#### 2.1.2. 2-Type Neighborhood Multigranulation Rough Sets (2-Type NMGRS)

Comparing with that just the single neighborhood relation was used in the 1-type neighborhood multigranulation rough sets, multiple neighborhood relations were fully considered in the 2-type neighborhood multigranulation rough sets, which were denoted by 2-type NMGRS by Qian et al. [25].Definition 4 (see [27]).
Given a decision systemNIS=U,C∪D,V,f,N, let N=n1,n2,…,nm be a neighborhood m-relation on the universe U induced by Ai and Bi, where Ai is a categorical attribute subset, and Bi is a numerical attribute subset. For any X⊆U, the optimistic lower and upper approximations of X in U are defined as follows:
(6)∑i=1mNi¯OX=x∈U∣nA1+B1x⊆X∨⋯∨nAi+Bix⊆X∨⋯∨nAm+Bmx⊆X,∑i=1mNi¯OX=~∑i=1mNi¯O~X,whereas the pessimistic multigranulation lower and upper approximations of X are defined as follows:
(7)∑i=1mNi¯PX=x∈U∣nA1+B1x⊆X∧⋯∧nAi+Bix⊆X∧⋯∧nAm+Bmx⊆X,∑i=1mNi¯PX=~∑i=1mNi¯P~X.Definition 5 (see [31]).
Given a decision systemNIS=U,C∪D,V,f,N, let B=B1,B2,…,Bm be an attribute subset of C, Y=Y1,Y2,Λ,Yr is a partition of universe U induced by decision attribute D, and δ=δ1,δ2,…,δn is a set of n neighborhood radii. The attribute dependency of Bi for decision class Y with the neighborhood radius δj is defined as follows:
(8)γBiδjY=POSBiδjYU=∪NBiδj¯YkU.Definition 6 (see [31]).
Given a decision systemNIS=U,C∪D,V,f,N, let B=B1,B2,…,Bm be an attribute subset of C, Y=Y1,Y2,Λ,Yr is a partition of universe U induced by decision attribute D, and δ=δ1,δ2,…,δn is a set of n neighborhood radii. ∀a∈Bi, if γBi−aδjY<γBiδjY, then the attribute a is necessary for Bi; else, if γBi−aδjY=γBiδjY, then regardless of whether the attribute a is removed from Bi, the decision positive region of the system is unchanged; in other words, the attribute a is redundant for Bi.Given the attribute subsetR⊆Bi, ∀a∈R, if γR−aδjY<γRδjY, and γRδjY=γBiδjY, then R is a relative reduction of Bi with the neighborhood radius δj.Definition 7 (see [19]).
Given a decision systemNIS=U,C∪D,V,f,N, let S=∪i=1mSi=∪i=1mUi,C∪D,V,f,N, ∀j,k∈1,2,…,m and j≠k, if U=∪i=1mUi and Uj∩Uk=∅, the decision system NIS can be divided into m-subdecision systems, and Si is called the subsystem of S.


### 2.2. MapReduce Programming Model

MapReduce is a parallel processing framework that breaks down large tasks into many small tasks. With the small tasks independent of each other, big tasks and small tasks are just different in size. The MapReduce parallel programming model also breaks down the computational process into two main stages: the Map stage and the Reduce stage.In the MapReduce model, the whole dataset is split into many splits in natural sequence and then is passed to the Map stage. Data in the MapReduce programming model can be represented as <key, value> pairs. The Map function takes pairs <K1, V1> as input and generates a set of intermediate <K2, V2> pairs. The Reduce function groups together all intermediate values V2 associated with the same K2 and then merges together a set of values for each K2 to form a possibly smaller set of values and finally outputs <K3, V3> pairs. The Map and Reduce functions are given as follows:Map:<K1,V1>→<K2,V2>.Reduce:<K2,V2>→<K3,V3>.Here,Ki and Vi i=1,…,3 represent the user-defined data types;  is used to denote a list.


## 2.1. Neighborhood Multigranulation Rough Set

Neighborhood rough set model uses neighborhood relation to replace equivalence relation, which can directly process numerical data and heterogeneous data. For further processing heterogeneous data from the perspective of multiple granular spaces and multiple levels of granularity, neighborhood rough set theory has been extended from single attribute subset to multiple attribute subsets. Two types of neighborhood multigranulation rough set models have been developed [27].


### 2.1.1. 1-Type Neighborhood Multigranulation Rough Sets (1-Type NMGRS)

Definition 1 (see [25]).
Let<U,Δ> be a nonempty metric space; U=x1,x2,…,xn is a nonempty finite set of objects, called the universe. A closed ball taking x∈U as its center and δ as its radius is called the δ neighborhood of x and is defined as follows:
(1)nx=y∈U∣Δx,y≤δ,where δ≥0, and Δ is a distance function. For two points in the universe, xi=xi1,xi2,…,xin and xj=xj1,xj2,…,xjn, the distance function can usually use the Euclidean distance formula.
(2)Δxi,xj=∑l=1nxil−xjl2.Definition 2 (see [25]).
Let<U,Δ> be a nonempty metric space. When categorical and numerical attributes coexist, let B1 and B2 be categorical and numerical attributes, respectively. The neighborhood of x can be defined as follows:
(3)nB1x=xi∈U∣ΔB1x,xi=0,nB2x=xi∈U∣ΔB2x,xi≤δ,nB1∪B2x=xi∈U∣ΔB1x,xi=0∧ΔB2x,xi≤δ.Definition 3 (see [25]).
Given a decision system,NIS=U,C∪D,V,f,N, where C=c1,c2,c3,…,cm is the set of condition attributes and D is the set of decision attributes, and C∩D=∅. V=∪a∈RVa is a set of attribute values and Va is a domain of the attribute a. f:U×R→V is a function such that fx,a∈Va for every a∈C and x∈U. N is the neighborhood relation. Let A⊆C be a categorical attribute set and B⊆C be a numerical attribute set, so A∪B⊆C is an mixed attribute set; U/A, U/B, and U/A∪B represent two partitions and a covering of the universe U, respectively. For any X⊆U, the optimistic multigranulation lower and upper approximations of X with respect to A and B in U are defined as follows:
(4)A+B¯OX=x∈U∣nAx⊆X∨nBx⊆X,A+B¯OX=~A+B¯O~X,whereas the pessimistic multigranulation lower and upper approximations of X are defined as follows:
(5)A+B¯PX=x∈U∣nAx⊆X∧nBx⊆X,A+B¯PX=~A+B¯P~X.


### 2.1.2. 2-Type Neighborhood Multigranulation Rough Sets (2-Type NMGRS)

Comparing with that just the single neighborhood relation was used in the 1-type neighborhood multigranulation rough sets, multiple neighborhood relations were fully considered in the 2-type neighborhood multigranulation rough sets, which were denoted by 2-type NMGRS by Qian et al. [25].Definition 4 (see [27]).
Given a decision systemNIS=U,C∪D,V,f,N, let N=n1,n2,…,nm be a neighborhood m-relation on the universe U induced by Ai and Bi, where Ai is a categorical attribute subset, and Bi is a numerical attribute subset. For any X⊆U, the optimistic lower and upper approximations of X in U are defined as follows:
(6)∑i=1mNi¯OX=x∈U∣nA1+B1x⊆X∨⋯∨nAi+Bix⊆X∨⋯∨nAm+Bmx⊆X,∑i=1mNi¯OX=~∑i=1mNi¯O~X,whereas the pessimistic multigranulation lower and upper approximations of X are defined as follows:
(7)∑i=1mNi¯PX=x∈U∣nA1+B1x⊆X∧⋯∧nAi+Bix⊆X∧⋯∧nAm+Bmx⊆X,∑i=1mNi¯PX=~∑i=1mNi¯P~X.Definition 5 (see [31]).
Given a decision systemNIS=U,C∪D,V,f,N, let B=B1,B2,…,Bm be an attribute subset of C, Y=Y1,Y2,Λ,Yr is a partition of universe U induced by decision attribute D, and δ=δ1,δ2,…,δn is a set of n neighborhood radii. The attribute dependency of Bi for decision class Y with the neighborhood radius δj is defined as follows:
(8)γBiδjY=POSBiδjYU=∪NBiδj¯YkU.Definition 6 (see [31]).
Given a decision systemNIS=U,C∪D,V,f,N, let B=B1,B2,…,Bm be an attribute subset of C, Y=Y1,Y2,Λ,Yr is a partition of universe U induced by decision attribute D, and δ=δ1,δ2,…,δn is a set of n neighborhood radii. ∀a∈Bi, if γBi−aδjY<γBiδjY, then the attribute a is necessary for Bi; else, if γBi−aδjY=γBiδjY, then regardless of whether the attribute a is removed from Bi, the decision positive region of the system is unchanged; in other words, the attribute a is redundant for Bi.Given the attribute subsetR⊆Bi, ∀a∈R, if γR−aδjY<γRδjY, and γRδjY=γBiδjY, then R is a relative reduction of Bi with the neighborhood radius δj.Definition 7 (see [19]).
Given a decision systemNIS=U,C∪D,V,f,N, let S=∪i=1mSi=∪i=1mUi,C∪D,V,f,N, ∀j,k∈1,2,…,m and j≠k, if U=∪i=1mUi and Uj∩Uk=∅, the decision system NIS can be divided into m-subdecision systems, and Si is called the subsystem of S.


## 2.1.1. 1-Type Neighborhood Multigranulation Rough Sets (1-Type NMGRS)

Definition 1 (see [25]).
Let<U,Δ> be a nonempty metric space; U=x1,x2,…,xn is a nonempty finite set of objects, called the universe. A closed ball taking x∈U as its center and δ as its radius is called the δ neighborhood of x and is defined as follows:
(1)nx=y∈U∣Δx,y≤δ,where δ≥0, and Δ is a distance function. For two points in the universe, xi=xi1,xi2,…,xin and xj=xj1,xj2,…,xjn, the distance function can usually use the Euclidean distance formula.
(2)Δxi,xj=∑l=1nxil−xjl2.Definition 2 (see [25]).
Let<U,Δ> be a nonempty metric space. When categorical and numerical attributes coexist, let B1 and B2 be categorical and numerical attributes, respectively. The neighborhood of x can be defined as follows:
(3)nB1x=xi∈U∣ΔB1x,xi=0,nB2x=xi∈U∣ΔB2x,xi≤δ,nB1∪B2x=xi∈U∣ΔB1x,xi=0∧ΔB2x,xi≤δ.Definition 3 (see [25]).
Given a decision system,NIS=U,C∪D,V,f,N, where C=c1,c2,c3,…,cm is the set of condition attributes and D is the set of decision attributes, and C∩D=∅. V=∪a∈RVa is a set of attribute values and Va is a domain of the attribute a. f:U×R→V is a function such that fx,a∈Va for every a∈C and x∈U. N is the neighborhood relation. Let A⊆C be a categorical attribute set and B⊆C be a numerical attribute set, so A∪B⊆C is an mixed attribute set; U/A, U/B, and U/A∪B represent two partitions and a covering of the universe U, respectively. For any X⊆U, the optimistic multigranulation lower and upper approximations of X with respect to A and B in U are defined as follows:
(4)A+B¯OX=x∈U∣nAx⊆X∨nBx⊆X,A+B¯OX=~A+B¯O~X,whereas the pessimistic multigranulation lower and upper approximations of X are defined as follows:
(5)A+B¯PX=x∈U∣nAx⊆X∧nBx⊆X,A+B¯PX=~A+B¯P~X.


## 2.1.2. 2-Type Neighborhood Multigranulation Rough Sets (2-Type NMGRS)

Comparing with that just the single neighborhood relation was used in the 1-type neighborhood multigranulation rough sets, multiple neighborhood relations were fully considered in the 2-type neighborhood multigranulation rough sets, which were denoted by 2-type NMGRS by Qian et al. [25].Definition 4 (see [27]).
Given a decision systemNIS=U,C∪D,V,f,N, let N=n1,n2,…,nm be a neighborhood m-relation on the universe U induced by Ai and Bi, where Ai is a categorical attribute subset, and Bi is a numerical attribute subset. For any X⊆U, the optimistic lower and upper approximations of X in U are defined as follows:
(6)∑i=1mNi¯OX=x∈U∣nA1+B1x⊆X∨⋯∨nAi+Bix⊆X∨⋯∨nAm+Bmx⊆X,∑i=1mNi¯OX=~∑i=1mNi¯O~X,whereas the pessimistic multigranulation lower and upper approximations of X are defined as follows:
(7)∑i=1mNi¯PX=x∈U∣nA1+B1x⊆X∧⋯∧nAi+Bix⊆X∧⋯∧nAm+Bmx⊆X,∑i=1mNi¯PX=~∑i=1mNi¯P~X.Definition 5 (see [31]).
Given a decision systemNIS=U,C∪D,V,f,N, let B=B1,B2,…,Bm be an attribute subset of C, Y=Y1,Y2,Λ,Yr is a partition of universe U induced by decision attribute D, and δ=δ1,δ2,…,δn is a set of n neighborhood radii. The attribute dependency of Bi for decision class Y with the neighborhood radius δj is defined as follows:
(8)γBiδjY=POSBiδjYU=∪NBiδj¯YkU.Definition 6 (see [31]).
Given a decision systemNIS=U,C∪D,V,f,N, let B=B1,B2,…,Bm be an attribute subset of C, Y=Y1,Y2,Λ,Yr is a partition of universe U induced by decision attribute D, and δ=δ1,δ2,…,δn is a set of n neighborhood radii. ∀a∈Bi, if γBi−aδjY<γBiδjY, then the attribute a is necessary for Bi; else, if γBi−aδjY=γBiδjY, then regardless of whether the attribute a is removed from Bi, the decision positive region of the system is unchanged; in other words, the attribute a is redundant for Bi.Given the attribute subsetR⊆Bi, ∀a∈R, if γR−aδjY<γRδjY, and γRδjY=γBiδjY, then R is a relative reduction of Bi with the neighborhood radius δj.Definition 7 (see [19]).
Given a decision systemNIS=U,C∪D,V,f,N, let S=∪i=1mSi=∪i=1mUi,C∪D,V,f,N, ∀j,k∈1,2,…,m and j≠k, if U=∪i=1mUi and Uj∩Uk=∅, the decision system NIS can be divided into m-subdecision systems, and Si is called the subsystem of S.


## 2.2. MapReduce Programming Model

MapReduce is a parallel processing framework that breaks down large tasks into many small tasks. With the small tasks independent of each other, big tasks and small tasks are just different in size. The MapReduce parallel programming model also breaks down the computational process into two main stages: the Map stage and the Reduce stage.In the MapReduce model, the whole dataset is split into many splits in natural sequence and then is passed to the Map stage. Data in the MapReduce programming model can be represented as <key, value> pairs. The Map function takes pairs <K1, V1> as input and generates a set of intermediate <K2, V2> pairs. The Reduce function groups together all intermediate values V2 associated with the same K2 and then merges together a set of values for each K2 to form a possibly smaller set of values and finally outputs <K3, V3> pairs. The Map and Reduce functions are given as follows:Map:<K1,V1>→<K2,V2>.Reduce:<K2,V2>→<K3,V3>.Here,Ki and Vi i=1,…,3 represent the user-defined data types;  is used to denote a list.


## 3. Parallel Attribute Reduction Algorithm for NMGRS

Aiming at the numerical or the heterogeneous data, many attribute reduction algorithms based on neighborhood multigranulation rough sets have been developed. However, it is still a challenging task to parallelize these attribute reduction algorithms for massive heterogeneous data. Motivated by the works of Qian et al. [21] and Yong et al. [28], quick parallelization strategies to speed up the computation of neighborhood classes and positive regions are proposed, and a parallel attribute reduction algorithm is designed in this section.


### 3.1. Parallelization Strategies

To parallelize the attribute reduction algorithm based on the neighborhood multigranulation rough set model, the MapReduce model was adopted. Thus, it is the key point that how to design the Map and Reduce functions for quickly getting neighborhood classes and positive regions. The work of Yong et al. [28] demonstrated that the neighborhood of a sample can only exist in its adjacent hash buckets or its own hash bucket. Therefore, to find possible neighborhoods, it is only necessary to group the samples according to their hash values. So, in the Map function, the hash value of each sample could be firstly calculated, and then the hash values and sample IDs are output. In the Reduce function, the sample IDs in the hash bucket are merged according to the same hash value.Thus, the Map and Reduce functions for hash buckets calculation are designed as follows.Algorithm 1: Hash-Map function.
Input: condition attribute subset, C; a data split Si
Output: <KEYHM, VALUEHM> // let KEYHM be the set of hash value of each sample, and VALUEHM be the set of sample ID
begin
<KEYHM, VALUEHM>=∅
for eachxi∈U do
letkey=hash(xi);
//hashxi=Δx0,xi/δ =key, where x0 is a special sample in universe U, which is satisfied with ∀a∈C,xi∈Ufx0,a=minfxi,a, and f is the information function.
letvalue=the ID of xi
<KEYHM, VALUEHM>=<KEYHM, VALUEHM>= ∪ <key, value>
end for
endAlgorithm 2: Hash-Reduce function.
Input: <KEYHM, VALUEHM>
Output: <KEYHR, VALUEHR> // let KEYHR be the set of different hash value key', and VALUEHR be the set of sample IDs subset value' with the same hash value key'.
begin
<KEYHR, VALUEHR>=∅
for <key, value>in <KEYHM, VALUEHM>do
ifkey is not appeared in <KEYHR, VALUEHR>
<key', value'>=<key, value>
else
ifkey=key'k
<KEYHR, VALUEHR>=<KEYHR, VALUEHR>-<key', value'>
value'k=value'k ∪ value // combine samples with the same hash value, obtain the hash bucket
end if
end if
<KEYHR, VALUEHR>=<KEYHR, VALUEHR> ∪ <key', value'>
end for //output with multi-file; a file named after a hash value is a hash bucket
endExample 1.
We take the decision table shown in Table1 as an example to illustrate the calculation process of Algorithms 1 and 2, where the decision attribute is listed in the last column.Table 1
Decision table.
U
c1
c2
c3
c4
D
x1
0.10
0.20
0.61
0.20
Yes
x2
0.13
0.22
0.56
0.10
Yes
x3
0.14
0.23
0.40
0.31
No
x4
0.16
0.41
0.30
0.16
NoAccording to Definition7, the decision information system was divided into S1=U1,C∪D,V,f,N and S2=U2,C∪D,V,f,N, where U1=x1,x2, and U2=x3,x4. The neighborhood radius is given as 0.08, and the condition attribute subset is given as B=c1,c2.The Map process:The <KEYHM, VALUEHM> pairs that output from Map 1 are <0,1>, and <1,2>.The <KEYHM, VALUEHM> pairs that output from Map 2 are <1,3>, and <3,4>.The Reduce process:The <KEYHR, VALUEHR> pair that outputs from Reduce 1 is <0,{1}>.The <KEYHR, VALUEHR> pair that outputs from Reduce 2 is <1,{2,3}>.The <KEYHR, VALUEHR> pair that outputs from Reduce 3 is <3,{4}>.After Algorithms1 and 2, samples were hashed into three hash buckets with hash values of 0, 1, and 3.Next, we calculated the positive regions under the current subset. According to Definition4, the process of neighborhood computation and positive region judgment based on the multigranulation neighborhood rough sets could be divided into two parts. First, calculate the neighborhood of x under one condition attribute subset and then take the intersection of the positive region set of multiple condition subsets (applicable to the pessimistic neighborhood multigranulation rough set model) or take the union of the positive region set (applicable to the optimistic neighborhood multigranulation rough set model).As to the neighborhood calculation of a single condition attribute subset, according to the work in literature [26], whether the sample belongs to the positive region can be judged by a distance function after traversing the hash bucket where a neighborhood probably exists. The hash value of a sample was calculated by the Map function firstly, and then, possible hash buckets can be searched in the output files (named after the hash value) by Algorithm 2. Consequently, the sample can be judged whether it belongs to the positive region or not by scanning the found hash buckets of this sample according to the distance function and decision attribute, where key values of samples in the positive region were assigned by 1, while key values of samples in the boundary were assigned by 0. The positive region for the whole universe U could be obtained by combining each positive region of Si in the Reduce function.Map and Reduce functions for neighborhood calculation by a single condition attribute subset are designed as follows.Algorithm 3: Single condition attribute subset neighborhood-Map.
Input: Single condition attribute subset, C; the hash bucket B; and a data split Si
Output: <KEYM, VALUEM>
//key∗ represents whether the sample belongs to the positive region; let key∗ of the sample in positive region be 1, and key∗ of the sample in boundary be 0; value∗ represents all samples’ ID that have the same key∗
begin
<KEYM, VALUEM>=∅
for eachxi∈U do
letkey∗i=0 //assuming that this sample does not belongs to the positive region under C
letvalue∗=the ID of xi and given that xi∈Bk
for eachxj∈Bk−1∪Bk∪Bk+1 //traversing the hash bucket where a neighborhood probably exists
ifxj is the neighborhood of xi, but they have different decision attribute values
letkey∗i=1
else
break
end if
end for
<KEYM, VALUEM>=<KEYM, VALUEM> ∪ <key∗i, value∗i>
end for
endAlgorithm 4: Single condition attribute subset neighborhood-Reduce.
Input: <KEYM, VALUEM>
Output: <KEYR, VALUER>
// letKEYR be the set of different key∗, and VALUER be the set of sample IDs subset value' with the same key'.
begin
<KEYR, VALUER>=∅
for <key∗, value∗>in <KEYM, VALUEM>do
ifkey is not appeared in <KEYR, VALUER>
<key∗′, value∗′>=<key∗, value∗>
else
ifkey∗=key∗′k
<KEYR, VALUER>=<KEYR, VALUER>-<key∗′, value∗′>
value∗′k=value∗′k ∪ value∗ // combine samples with the same key∗
end if
end if
<KEYR, VALUER>=<KEYR, VALUER> ∪ <key∗′, value∗′>
end for
endThe positive region of the whole universeU under single attribute granularity can be obtained by this algorithm through the intersection or union of the single granularity positive region sequence. Thus, the significant attribute could be calculated and added to current reduction subsets.Example 2.
We continue using the decision table in Table1 and the same conditions as in Example 1 to illustrate the operation process.The Map process:The <KEYM, VALUEM> pairs that output from Map 1 are <0,1>, and <0,2>.The <KEYM, VALUEM> pairs that output from Map 2 are <0,3>, and <1,4>.The Reduce process:The <KEYR, VALUER> pair that outputs from Reduce 1 is <0,{1,2,3}>.The <KEYR, VALUER> pair that outputs from Reduce 2 is <1,{4}>.The above operation results show that the positive and boundary region of the current universe can be acquired by Algorithms3 and 4, where the positive region includes 4 and the boundary region includes 1,2,3.According to the monotonic proof of the work of Ma et al. [32] that the situation of one sample belonging to a certain positive region will not be changed when additional attributes are added. In other words, in this case, it is unnecessary that these samples are repeatedly calculated in the second Reduce stage. So the Reduce function could focus the boundary samples.The Map and Reduce functions for updating positive regions are designed as follows.Algorithm 5: U_REDUCE-Map.
Input: a data split Si
Output: <KEYUM, VALUEUM>
//key^ represents the sample does not belongs to the positive region; value^ represents the sequence of the sample’s attribute value
begin
<KEYUM, VALUEUM>=∅
for eachxi∈Si do
ifxi∉POS key^i=1, value^i=xi
elsekey^i=0, value^i=xi
end if
<KEYUM, VALUEUM>=<KEYUM, VALUEUM> ∪ <key^i, value^i>
end for
endAlgorithm 6: U_REDUCE-Reduce.
Input: <KEYUM, VALUEUM>
Output: <KEYUR, VALUEUR>
// letKEYUR be the sequence number in the case of key^=1, and VALUEUR be the set of value^ sequence subset.
begin
KEYUR=0 and VALUEUR=∅
ifkey^k=1
KEYUR=KEYUR++
VALUEUR=VALUEUR ∪ value^k
end if
endExample 3.
Here, we are taking Table1 and the results of Example 2 to illustrate the operation process on parallel boundary set updating and forming a new decision table.
It can be seen from Example2 that the current positive region set is 4, and thus, this update should remove the sample with the ID of 4 from the decision table.The Map process:The <KEYUM, VALUEUM> pairs that output from Map 1 are <1, (1 0.10 0.20 0.61 0.20 Yes)> and <1, (2 0.13 0.22 0.56 0.10 Yes)>.The <KEYUM, VALUEUM> pair that outputs from Map 2 is <1, (0.14 0.23 0.40 0.31 No)>.The Reduce process:The <KEYUR, VALUEUR> pairs that output from Reduce1 are <1 (0.10 0.20 0.61 0.20 Yes)>, <2 (0.13 0.22 0.56 0.10 Yes)>, and <0.14 (0.23 0.40 0.31 No)>.After the above operation, the boundary region updating was finished, and the actual storage situation is shown as follows:S1: 1 0.10 0.20 0.61 0.20 Yes2 0.13 0.22 0.56 0.10 YesS2: 0.14 0.23 0.40 0.31 NoThe above results show that the subsequent attribute reduction can be processed directly on the basis of the whole dataset without any extra splitting.


### 3.2. Parallel Attribute Reduction Algorithm

On the basis of parallel algorithms given in Section3.1, a neighborhood multigranulation rough set-based parallel attribute reduction algorithm using MapReduce is presented. For convenience, this algorithm is denoted as PARA_NMG in this paper.Algorithm 7: PARA_NMG algorithm.
Input:NIS=U,C∪D,V,f,N, β
Output: reduction reduct
begin
Step 1: initializereduct←∅, Q←U, Max_POS=∅;
Step 2: if (C-reduct)= ∅, go to Step 3; while if (C-reduct) ≠∅, execute the following loop operations:
Step 2.1: for each condition attributeck∈C−reduct, use algorithms 1~4 to calculate the positive region POSk of reduct∪ck;
Step 2.2: compare the positive regionPOSk of condition attribute subset reduct∪ck after each attribute ck added. Find current maximum positive region Max_POS; if ∣Max_POS∣=∅ then keep attribute reduction invariant, and go to Step 3. Otherwise, add ck into reduct, reduct=reduct∪ck;
Step 2.3: update boundary sample setQ with algorithms 5~6, Q=Q−Max_POS, and return to Step 2.1
Step 3: output reductionreduct
end.


### 3.3. Algorithm: Time Complexity Analysis

It is assumed that the neighborhood decision information system has∣U∣-samples and m-condition attributes. The positive region calculation is still the key step for the proposed PARA_NMG algorithm. In step 2.1, the calculation method in literature [28] is used to calculate the positive region of each attribute set, the time complexity of which is OmU. As to step 2.3, suppose that there are l-attributes eventually selected, with each attribute is added into the reduction subset, U/l-samples will convert from the boundary sample to the positive region (in term of probability). Therefore, the time complexity of serial calculation is OmUl+1. Furthermore, the MapReduce model was used in the PARA_NMG algorithm to parallelize the attribute reduction algorithm; assuming that there are k-nodes, the time complexity of the algorithm is OmUl+1/k, which is superior to the time complexity of maxOm2U∑t=1mlnct+lnd/k,Om2U/k in literature [22] and time complexity of OC2U2/k in literature [33].


## 3.1. Parallelization Strategies

To parallelize the attribute reduction algorithm based on the neighborhood multigranulation rough set model, the MapReduce model was adopted. Thus, it is the key point that how to design the Map and Reduce functions for quickly getting neighborhood classes and positive regions. The work of Yong et al. [28] demonstrated that the neighborhood of a sample can only exist in its adjacent hash buckets or its own hash bucket. Therefore, to find possible neighborhoods, it is only necessary to group the samples according to their hash values. So, in the Map function, the hash value of each sample could be firstly calculated, and then the hash values and sample IDs are output. In the Reduce function, the sample IDs in the hash bucket are merged according to the same hash value.Thus, the Map and Reduce functions for hash buckets calculation are designed as follows.Algorithm 1: Hash-Map function.
Input: condition attribute subset, C; a data split Si
Output: <KEYHM, VALUEHM> // let KEYHM be the set of hash value of each sample, and VALUEHM be the set of sample ID
begin
<KEYHM, VALUEHM>=∅
for eachxi∈U do
letkey=hash(xi);
//hashxi=Δx0,xi/δ =key, where x0 is a special sample in universe U, which is satisfied with ∀a∈C,xi∈Ufx0,a=minfxi,a, and f is the information function.
letvalue=the ID of xi
<KEYHM, VALUEHM>=<KEYHM, VALUEHM>= ∪ <key, value>
end for
endAlgorithm 2: Hash-Reduce function.
Input: <KEYHM, VALUEHM>
Output: <KEYHR, VALUEHR> // let KEYHR be the set of different hash value key', and VALUEHR be the set of sample IDs subset value' with the same hash value key'.
begin
<KEYHR, VALUEHR>=∅
for <key, value>in <KEYHM, VALUEHM>do
ifkey is not appeared in <KEYHR, VALUEHR>
<key', value'>=<key, value>
else
ifkey=key'k
<KEYHR, VALUEHR>=<KEYHR, VALUEHR>-<key', value'>
value'k=value'k ∪ value // combine samples with the same hash value, obtain the hash bucket
end if
end if
<KEYHR, VALUEHR>=<KEYHR, VALUEHR> ∪ <key', value'>
end for //output with multi-file; a file named after a hash value is a hash bucket
endExample 1.
We take the decision table shown in Table1 as an example to illustrate the calculation process of Algorithms 1 and 2, where the decision attribute is listed in the last column.Table 1
Decision table.
U
c1
c2
c3
c4
D
x1
0.10
0.20
0.61
0.20
Yes
x2
0.13
0.22
0.56
0.10
Yes
x3
0.14
0.23
0.40
0.31
No
x4
0.16
0.41
0.30
0.16
NoAccording to Definition7, the decision information system was divided into S1=U1,C∪D,V,f,N and S2=U2,C∪D,V,f,N, where U1=x1,x2, and U2=x3,x4. The neighborhood radius is given as 0.08, and the condition attribute subset is given as B=c1,c2.The Map process:The <KEYHM, VALUEHM> pairs that output from Map 1 are <0,1>, and <1,2>.The <KEYHM, VALUEHM> pairs that output from Map 2 are <1,3>, and <3,4>.The Reduce process:The <KEYHR, VALUEHR> pair that outputs from Reduce 1 is <0,{1}>.The <KEYHR, VALUEHR> pair that outputs from Reduce 2 is <1,{2,3}>.The <KEYHR, VALUEHR> pair that outputs from Reduce 3 is <3,{4}>.After Algorithms1 and 2, samples were hashed into three hash buckets with hash values of 0, 1, and 3.Next, we calculated the positive regions under the current subset. According to Definition4, the process of neighborhood computation and positive region judgment based on the multigranulation neighborhood rough sets could be divided into two parts. First, calculate the neighborhood of x under one condition attribute subset and then take the intersection of the positive region set of multiple condition subsets (applicable to the pessimistic neighborhood multigranulation rough set model) or take the union of the positive region set (applicable to the optimistic neighborhood multigranulation rough set model).As to the neighborhood calculation of a single condition attribute subset, according to the work in literature [26], whether the sample belongs to the positive region can be judged by a distance function after traversing the hash bucket where a neighborhood probably exists. The hash value of a sample was calculated by the Map function firstly, and then, possible hash buckets can be searched in the output files (named after the hash value) by Algorithm 2. Consequently, the sample can be judged whether it belongs to the positive region or not by scanning the found hash buckets of this sample according to the distance function and decision attribute, where key values of samples in the positive region were assigned by 1, while key values of samples in the boundary were assigned by 0. The positive region for the whole universe U could be obtained by combining each positive region of Si in the Reduce function.Map and Reduce functions for neighborhood calculation by a single condition attribute subset are designed as follows.Algorithm 3: Single condition attribute subset neighborhood-Map.
Input: Single condition attribute subset, C; the hash bucket B; and a data split Si
Output: <KEYM, VALUEM>
//key∗ represents whether the sample belongs to the positive region; let key∗ of the sample in positive region be 1, and key∗ of the sample in boundary be 0; value∗ represents all samples’ ID that have the same key∗
begin
<KEYM, VALUEM>=∅
for eachxi∈U do
letkey∗i=0 //assuming that this sample does not belongs to the positive region under C
letvalue∗=the ID of xi and given that xi∈Bk
for eachxj∈Bk−1∪Bk∪Bk+1 //traversing the hash bucket where a neighborhood probably exists
ifxj is the neighborhood of xi, but they have different decision attribute values
letkey∗i=1
else
break
end if
end for
<KEYM, VALUEM>=<KEYM, VALUEM> ∪ <key∗i, value∗i>
end for
endAlgorithm 4: Single condition attribute subset neighborhood-Reduce.
Input: <KEYM, VALUEM>
Output: <KEYR, VALUER>
// letKEYR be the set of different key∗, and VALUER be the set of sample IDs subset value' with the same key'.
begin
<KEYR, VALUER>=∅
for <key∗, value∗>in <KEYM, VALUEM>do
ifkey is not appeared in <KEYR, VALUER>
<key∗′, value∗′>=<key∗, value∗>
else
ifkey∗=key∗′k
<KEYR, VALUER>=<KEYR, VALUER>-<key∗′, value∗′>
value∗′k=value∗′k ∪ value∗ // combine samples with the same key∗
end if
end if
<KEYR, VALUER>=<KEYR, VALUER> ∪ <key∗′, value∗′>
end for
endThe positive region of the whole universeU under single attribute granularity can be obtained by this algorithm through the intersection or union of the single granularity positive region sequence. Thus, the significant attribute could be calculated and added to current reduction subsets.Example 2.
We continue using the decision table in Table1 and the same conditions as in Example 1 to illustrate the operation process.The Map process:The <KEYM, VALUEM> pairs that output from Map 1 are <0,1>, and <0,2>.The <KEYM, VALUEM> pairs that output from Map 2 are <0,3>, and <1,4>.The Reduce process:The <KEYR, VALUER> pair that outputs from Reduce 1 is <0,{1,2,3}>.The <KEYR, VALUER> pair that outputs from Reduce 2 is <1,{4}>.The above operation results show that the positive and boundary region of the current universe can be acquired by Algorithms3 and 4, where the positive region includes 4 and the boundary region includes 1,2,3.According to the monotonic proof of the work of Ma et al. [32] that the situation of one sample belonging to a certain positive region will not be changed when additional attributes are added. In other words, in this case, it is unnecessary that these samples are repeatedly calculated in the second Reduce stage. So the Reduce function could focus the boundary samples.The Map and Reduce functions for updating positive regions are designed as follows.Algorithm 5: U_REDUCE-Map.
Input: a data split Si
Output: <KEYUM, VALUEUM>
//key^ represents the sample does not belongs to the positive region; value^ represents the sequence of the sample’s attribute value
begin
<KEYUM, VALUEUM>=∅
for eachxi∈Si do
ifxi∉POS key^i=1, value^i=xi
elsekey^i=0, value^i=xi
end if
<KEYUM, VALUEUM>=<KEYUM, VALUEUM> ∪ <key^i, value^i>
end for
endAlgorithm 6: U_REDUCE-Reduce.
Input: <KEYUM, VALUEUM>
Output: <KEYUR, VALUEUR>
// letKEYUR be the sequence number in the case of key^=1, and VALUEUR be the set of value^ sequence subset.
begin
KEYUR=0 and VALUEUR=∅
ifkey^k=1
KEYUR=KEYUR++
VALUEUR=VALUEUR ∪ value^k
end if
endExample 3.
Here, we are taking Table1 and the results of Example 2 to illustrate the operation process on parallel boundary set updating and forming a new decision table.
It can be seen from Example2 that the current positive region set is 4, and thus, this update should remove the sample with the ID of 4 from the decision table.The Map process:The <KEYUM, VALUEUM> pairs that output from Map 1 are <1, (1 0.10 0.20 0.61 0.20 Yes)> and <1, (2 0.13 0.22 0.56 0.10 Yes)>.The <KEYUM, VALUEUM> pair that outputs from Map 2 is <1, (0.14 0.23 0.40 0.31 No)>.The Reduce process:The <KEYUR, VALUEUR> pairs that output from Reduce1 are <1 (0.10 0.20 0.61 0.20 Yes)>, <2 (0.13 0.22 0.56 0.10 Yes)>, and <0.14 (0.23 0.40 0.31 No)>.After the above operation, the boundary region updating was finished, and the actual storage situation is shown as follows:S1: 1 0.10 0.20 0.61 0.20 Yes2 0.13 0.22 0.56 0.10 YesS2: 0.14 0.23 0.40 0.31 NoThe above results show that the subsequent attribute reduction can be processed directly on the basis of the whole dataset without any extra splitting.


## 3.2. Parallel Attribute Reduction Algorithm

On the basis of parallel algorithms given in Section3.1, a neighborhood multigranulation rough set-based parallel attribute reduction algorithm using MapReduce is presented. For convenience, this algorithm is denoted as PARA_NMG in this paper.Algorithm 7: PARA_NMG algorithm.
Input:NIS=U,C∪D,V,f,N, β
Output: reduction reduct
begin
Step 1: initializereduct←∅, Q←U, Max_POS=∅;
Step 2: if (C-reduct)= ∅, go to Step 3; while if (C-reduct) ≠∅, execute the following loop operations:
Step 2.1: for each condition attributeck∈C−reduct, use algorithms 1~4 to calculate the positive region POSk of reduct∪ck;
Step 2.2: compare the positive regionPOSk of condition attribute subset reduct∪ck after each attribute ck added. Find current maximum positive region Max_POS; if ∣Max_POS∣=∅ then keep attribute reduction invariant, and go to Step 3. Otherwise, add ck into reduct, reduct=reduct∪ck;
Step 2.3: update boundary sample setQ with algorithms 5~6, Q=Q−Max_POS, and return to Step 2.1
Step 3: output reductionreduct
end.


## 3.3. Algorithm: Time Complexity Analysis

It is assumed that the neighborhood decision information system has∣U∣-samples and m-condition attributes. The positive region calculation is still the key step for the proposed PARA_NMG algorithm. In step 2.1, the calculation method in literature [28] is used to calculate the positive region of each attribute set, the time complexity of which is OmU. As to step 2.3, suppose that there are l-attributes eventually selected, with each attribute is added into the reduction subset, U/l-samples will convert from the boundary sample to the positive region (in term of probability). Therefore, the time complexity of serial calculation is OmUl+1. Furthermore, the MapReduce model was used in the PARA_NMG algorithm to parallelize the attribute reduction algorithm; assuming that there are k-nodes, the time complexity of the algorithm is OmUl+1/k, which is superior to the time complexity of maxOm2U∑t=1mlnct+lnd/k,Om2U/k in literature [22] and time complexity of OC2U2/k in literature [33].


## 4. Experiment Analysis

In this section, we conducted some numerical experiments to assess the efficiency of our proposed algorithm. The experiments were implemented on a PC cluster of nine nodes, where one was set as a master node and the rest were configured as slave nodes. Each node is equipped with Inter Core i5-2400M CPU (four cores in all, each 3.1 GHz), 4 GB RAM memory, and the software of Ubuntu 14.0, Hadoop 2.6.0, and Java 1.6.20. All algorithms were coded in Java.To illustrate the efficiency of our proposed PARA_NMG algorithm, the representative parallel algorithm for reduction algorithm based on positive region, which was denoted as PAAR_PR, proposed in literature [21] was used for comparisons. The difference is that the PAAR_PR algorithm is based on the classical rough set model, while the PARA_NMG algorithm is based on the neighborhood multigranulation rough set model.To test the efficiencies of above two algorithms on different types of data, the experiments were carried out with the real datasetsSoybean, US Census Data (1990), Susy, PAMAP2 Physical Activity Monitoring, and Poker Hand from UCI Machine Learning Repository [34] and another dataset KDD99. Here, Soybean and US Census Data (1990) are categorical datasets, Susy and PAMAP2 Physical Activity Monitoring are numerical datasets, and Poker Hand and KDD99 are heterogeneous datasets. To create a big data environment, the dataset Soybean was duplicated 100,000 times as a new dataset. For convenience, these above six datasets were denoted as DS1~DS6, respectively. The characteristics of these datasets are shown in Table 2.Table 2
Datasets.
Dataset
Record number
Attribute number
Class number
1
DS1
30,700,000
35
19
2
DS2
2,458,285
68
3
3
DS3
5,000,000
18
2
4
DS4
3,850,505
52
2
5
DS5
1,025,010
11
10
6
DS6
4,898,421
41
23


### 4.1. Comparison and Analysis of Reduction Results

For neighborhood rough set model, it is important to select a proper neighborhood radius when calculating neighborhood classes. According to the work of Hu et al. [24], the reasonable neighborhood radius should be selected in the interval 0.1,0.3. Qian et al. [29] analyzed the monotonicity of positive region with the neighborhood radius, and they found that the classification accuracy will be deduced with neighborhood radius increase. Considering these factors and characteristics of selected datasets, the neighborhood radius for our PARA_NMG algorithm was set to be 0.1 when facing numerical data. The reduction results of the PARA_NMG algorithm and the PAAR_PR algorithm are shown in Table 3.Table 3
Reduction results of the two algorithms.
Dataset
PAAR_PR
PARA_NMG
DS1
18, 26, 29, 1, 22, 3, 6, 10, 7, 9, 7, 17
18, 26, 29, 1, 22, 3, 6, 10, 7, 9, 4, 16
DS2
53, 25, 50, 14, 66
32, 67, 53, 35, 14
DS3
/
1, 17, 6
DS4
/
7, 19, 57, 2, 61, 5
DS5
/
4, 8, 2, 10
DS6
12, 6, 5, 3, 1, 23, 33, 36, 2, 24, 40
12, 6, 5, 3, 1, 23, 33, 36, 8, 11, 29, 34, 39, 27It can be seen from Table3 that the PAAR_PR algorithm obtained effective reduction results on categorical datasets DS1 and DS2. Notwithstanding that there are few numerical attributes in DS6, the equivalence classes could be obtained, so the PAAR_PR algorithm is still practicable. However, for numerical datasets DS3 and DS4 and heterogeneous dataset DS5, PAAR_PR could not get the reduction results because equivalent classes could not be obtained in these datasets. Thus, the applicability of PAAR_PR algorithm depends on the characteristics of datasets. Comparatively speaking, the PARA_NMG algorithm was not limited by data types when calculating attribute reduction on different datasets. Considering the rampant existence of heterogeneous datasets in real-life applications, the neighborhood multigranulation rough set-based PARA_NMG algorithm has better applicability.In addition, for datasets DS1, DS2, and DS6, although the attribute reduction results were all obtained, there was a little difference between the selected attribute subsets by both algorithms. To further analyze the two algorithms’ effects on reduction results from the perspective of classification accuracy, seven well-known typical classifiers, namely, sequential minimal optimization (SMO), naive Bayes, naive Bayesian model (NBM), logistic regression model (LRM), locally weighted learning (LWL), J48, and MultiClassClassifier , were selected to further test the classification accuracy associated with different attribute reduction subsets. The test results are shown in Table4.Table 4
Classification accuracies with two algorithms’ reduction results.
Classifier
Dataset
PAAR_PR
PARA_NMG
SMO
DS1
82.1037
86.4802
DS2
84.5962
87.6572
DS6
91.5151
97.9569
Naive Bayes
DS1
75.4451
84.7014
DS2
87.4395
93.1425
DS6
67.0616
75.6389
NBM
DS1
57.4696
77.7349
DS2
87.6570
89.6472
DS6
97.1868
97.9569
Logistic
DS1
83.6540
88.0672
DS2
87.7754
90.7764
DS6
99.9873
99.9898
LWL
DS1
91.7377
96.5833
DS2
70.9932
80.4851
DS6
67.0616
67.0616
J48
DS1
90.5104
97.9103
DS2
82
82
DS6
97.1868
98.1967
MultiClassClassifier
DS1
81.6033
82.8716
DS2
95.1595
98.5344
DS6
96.1977
99.9781We can see from Table4 that classification accuracies, according to the reduction subsets of PARA_NMG algorithm, are better for most of these classifiers. In fact, the classification accuracy is the important factor that should be considered in real-life applications. So, from a practical point of view, our neighborhood multigranulation rough set-based PARA_NMG algorithm also has better applicability.


### 4.2. Comparative Analysis on Computational Time

To illustrate the influence of the number of computer nodes on the two algorithms’ computational time, the experiments were implemented on a cluster with different number of nodes. The average running times of the two algorithms were recorded, which are shown in Table5 as follows. For datasets DS3~DS5, only the results of PARA_NMG algorithm are given.Table 5
Average computational time of two algorithms (s).
Dataset
Algorithm
Number of nodes
1
2
3
4
5
6
7
8
DS1
PARA_NMG
14,958
8499
6420
4953
4132
3596
3317
2968
PAAR_PR
1724
894
607
492
418
364
312
272
DS2
PARA_NMG
55,423
28,717
19,515
17,820
14,031
11,996
10,226
8854
PAAR_PR
8732
4961
3731
2960
2591
2140
2003
1815
DS3
PARA_NMG
64,035
34,992
24,820
19,583
16,504
14,927
13,481
12,338
DS4
PARA_NMG
16,006
8559
6428
4694
3942
3572
3163
2663
DS5
PARA_NMG
13,226
6961
4863
4032
3157
2738
2458
2249
DS6
PARA_NMG
21,371
11,264
7714
6333
5304
4847
3961
3533
PAAR_PR
2091
1384
1124
987
816
723
651
624As can be seen from Table5, PAAR_PR is faster than PARA_NMG because of the different rough set models were used. PAAR_PR is based on the classical rough set model, and the time complexity of the classical heuristic serial reduction algorithm based on the positive region is OmU2. Conversely, PARA_NMG is based on the neighborhood multigranulation rough set model, and the time complexity of the classical serial reduction algorithm is Om2U2. To minimize the times of computation for getting positive regions, the hash function was introduced into the Map and Reduce stages for neighborhood multigranulation rough sets, and the time complexity of our parallel attribute reduction algorithm was reduced to Om∣U∣l+1/k. To some extent, the computational time of our algorithm is still comparable.In fact, except for the computational time, the speedup is really an important performance index for evaluating the efficiency of a parallel algorithm, which is defined as follows:(9)Speedupp=T1Tp,where p is the number of nodes, T1 is the execution time at one node, and Tp is the execution time at p nodes.The speedup of two algorithms was tested with different number of nodes. To be more intuitive, the average speedup of two algorithms on each dataset with different computer nodes is presented in Figure1 as follows, where the x axis represents the number of computer nodes, the y axis represents the speedup, and the red star point denoted by liner represents the theoretical speedup of a parallel algorithm.Figure 1
Average speedup on different number of nodes.
(a)
(b)
(c)
(d)
(e)
(f)As shown in Figure1, the parallel reduction algorithm proposed in this paper could achieve better speedup on different data types. With the number of nodes increase, the superiority of our PARA_NMG algorithm in speedup is more and more obvious. Therefore, the PARA_NMG algorithm is more suitable for processing heterogeneous massive data parallelly on a large number of computing nodes.


## 4.1. Comparison and Analysis of Reduction Results

For neighborhood rough set model, it is important to select a proper neighborhood radius when calculating neighborhood classes. According to the work of Hu et al. [24], the reasonable neighborhood radius should be selected in the interval 0.1,0.3. Qian et al. [29] analyzed the monotonicity of positive region with the neighborhood radius, and they found that the classification accuracy will be deduced with neighborhood radius increase. Considering these factors and characteristics of selected datasets, the neighborhood radius for our PARA_NMG algorithm was set to be 0.1 when facing numerical data. The reduction results of the PARA_NMG algorithm and the PAAR_PR algorithm are shown in Table 3.Table 3
Reduction results of the two algorithms.
Dataset
PAAR_PR
PARA_NMG
DS1
18, 26, 29, 1, 22, 3, 6, 10, 7, 9, 7, 17
18, 26, 29, 1, 22, 3, 6, 10, 7, 9, 4, 16
DS2
53, 25, 50, 14, 66
32, 67, 53, 35, 14
DS3
/
1, 17, 6
DS4
/
7, 19, 57, 2, 61, 5
DS5
/
4, 8, 2, 10
DS6
12, 6, 5, 3, 1, 23, 33, 36, 2, 24, 40
12, 6, 5, 3, 1, 23, 33, 36, 8, 11, 29, 34, 39, 27It can be seen from Table3 that the PAAR_PR algorithm obtained effective reduction results on categorical datasets DS1 and DS2. Notwithstanding that there are few numerical attributes in DS6, the equivalence classes could be obtained, so the PAAR_PR algorithm is still practicable. However, for numerical datasets DS3 and DS4 and heterogeneous dataset DS5, PAAR_PR could not get the reduction results because equivalent classes could not be obtained in these datasets. Thus, the applicability of PAAR_PR algorithm depends on the characteristics of datasets. Comparatively speaking, the PARA_NMG algorithm was not limited by data types when calculating attribute reduction on different datasets. Considering the rampant existence of heterogeneous datasets in real-life applications, the neighborhood multigranulation rough set-based PARA_NMG algorithm has better applicability.In addition, for datasets DS1, DS2, and DS6, although the attribute reduction results were all obtained, there was a little difference between the selected attribute subsets by both algorithms. To further analyze the two algorithms’ effects on reduction results from the perspective of classification accuracy, seven well-known typical classifiers, namely, sequential minimal optimization (SMO), naive Bayes, naive Bayesian model (NBM), logistic regression model (LRM), locally weighted learning (LWL), J48, and MultiClassClassifier , were selected to further test the classification accuracy associated with different attribute reduction subsets. The test results are shown in Table4.Table 4
Classification accuracies with two algorithms’ reduction results.
Classifier
Dataset
PAAR_PR
PARA_NMG
SMO
DS1
82.1037
86.4802
DS2
84.5962
87.6572
DS6
91.5151
97.9569
Naive Bayes
DS1
75.4451
84.7014
DS2
87.4395
93.1425
DS6
67.0616
75.6389
NBM
DS1
57.4696
77.7349
DS2
87.6570
89.6472
DS6
97.1868
97.9569
Logistic
DS1
83.6540
88.0672
DS2
87.7754
90.7764
DS6
99.9873
99.9898
LWL
DS1
91.7377
96.5833
DS2
70.9932
80.4851
DS6
67.0616
67.0616
J48
DS1
90.5104
97.9103
DS2
82
82
DS6
97.1868
98.1967
MultiClassClassifier
DS1
81.6033
82.8716
DS2
95.1595
98.5344
DS6
96.1977
99.9781We can see from Table4 that classification accuracies, according to the reduction subsets of PARA_NMG algorithm, are better for most of these classifiers. In fact, the classification accuracy is the important factor that should be considered in real-life applications. So, from a practical point of view, our neighborhood multigranulation rough set-based PARA_NMG algorithm also has better applicability.


## 4.2. Comparative Analysis on Computational Time

To illustrate the influence of the number of computer nodes on the two algorithms’ computational time, the experiments were implemented on a cluster with different number of nodes. The average running times of the two algorithms were recorded, which are shown in Table5 as follows. For datasets DS3~DS5, only the results of PARA_NMG algorithm are given.Table 5
Average computational time of two algorithms (s).
Dataset
Algorithm
Number of nodes
1
2
3
4
5
6
7
8
DS1
PARA_NMG
14,958
8499
6420
4953
4132
3596
3317
2968
PAAR_PR
1724
894
607
492
418
364
312
272
DS2
PARA_NMG
55,423
28,717
19,515
17,820
14,031
11,996
10,226
8854
PAAR_PR
8732
4961
3731
2960
2591
2140
2003
1815
DS3
PARA_NMG
64,035
34,992
24,820
19,583
16,504
14,927
13,481
12,338
DS4
PARA_NMG
16,006
8559
6428
4694
3942
3572
3163
2663
DS5
PARA_NMG
13,226
6961
4863
4032
3157
2738
2458
2249
DS6
PARA_NMG
21,371
11,264
7714
6333
5304
4847
3961
3533
PAAR_PR
2091
1384
1124
987
816
723
651
624As can be seen from Table5, PAAR_PR is faster than PARA_NMG because of the different rough set models were used. PAAR_PR is based on the classical rough set model, and the time complexity of the classical heuristic serial reduction algorithm based on the positive region is OmU2. Conversely, PARA_NMG is based on the neighborhood multigranulation rough set model, and the time complexity of the classical serial reduction algorithm is Om2U2. To minimize the times of computation for getting positive regions, the hash function was introduced into the Map and Reduce stages for neighborhood multigranulation rough sets, and the time complexity of our parallel attribute reduction algorithm was reduced to Om∣U∣l+1/k. To some extent, the computational time of our algorithm is still comparable.In fact, except for the computational time, the speedup is really an important performance index for evaluating the efficiency of a parallel algorithm, which is defined as follows:(9)Speedupp=T1Tp,where p is the number of nodes, T1 is the execution time at one node, and Tp is the execution time at p nodes.The speedup of two algorithms was tested with different number of nodes. To be more intuitive, the average speedup of two algorithms on each dataset with different computer nodes is presented in Figure1 as follows, where the x axis represents the number of computer nodes, the y axis represents the speedup, and the red star point denoted by liner represents the theoretical speedup of a parallel algorithm.Figure 1
Average speedup on different number of nodes.
(a)
(b)
(c)
(d)
(e)
(f)As shown in Figure1, the parallel reduction algorithm proposed in this paper could achieve better speedup on different data types. With the number of nodes increase, the superiority of our PARA_NMG algorithm in speedup is more and more obvious. Therefore, the PARA_NMG algorithm is more suitable for processing heterogeneous massive data parallelly on a large number of computing nodes.


## 5. Conclusion

Attribute reduction is one of the important research issues in rough set theory. In current big data era, traditional attribute reduction algorithms are now faced with big challenges for dealing with massive data. Most existing parallel algorithms have seldom taken granular computing into consideration, especially for dealing with complex heterogeneous data including categorical attributes and numerical attributes. To address these issues, aiming at heterogeneous data, a quick parallel attribute reduction algorithm using MapReduce in the framework of neighborhood multigranulation rough sets was developed in this paper. The hash function was introduced into the Map and Reduce stages to speed up the positive region calculation. The effectiveness and superiority of the developed algorithm were verified by comparison analysis.However, just the static data was considered in this paper; in fact, datasets in real-world applications often vary dynamically over time. How to parallelize the incremental attribute reduction algorithm in the framework of neighborhood multigranulation rough sets is a focus for future research.



---

*Source: 8291650-2018-09-27.xml*