# Boosted Fuzzy Granular Regression Trees

Authors: Wei Li; Youmeng Luo; Chao Tang; Kaiqiang Zhang; Xiaoyu Ma
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

The regression problem is a valued problem in the domain of machine learning, and it has been widely employed in many fields such as meteorology, transportation, and material. Granular computing (GrC) is a good approach of exploring human intelligent information processing, which has the superiority of knowledge discovery. Ensemble learning is easy to execute parallelly. Based on granular computing and ensemble learning, we convert the regression problem into granular space equivalently to solve and proposed boosted fuzzy granular regression trees (BFGRT) to predict a test instance. The thought of BFGRT is as follows. First, a clustering algorithm with automatic optimization of clustering centers is presented. Next, in terms of the clustering algorithm, we employ MapReduce to parallelly implement fuzzy granulation of the data. Then, we design new operators and metrics of fuzzy granules to build fuzzy granular rule base. Finally, a fuzzy granular regression tree (FGRT) in the fuzzy granular space is presented. In the light of these, BFGRT can be designed by parallelly combing multiple FGRTs via random sampling attributes and MapReduce. Theory and experiments show that BFGRT is accurate, efficient, and robust.


---

## Body

## 1. Introduction

Learning ability is the basic feature of human intelligence. Prediction is the ability of humans to judge the future based on learning, and it is also a concrete manifestation of human learning ability. Prediction has two concrete forms, regression and classification, which is also one of the substance problems in machine learning, data mining, and statistics. How to train a learner on the basis of existing data is the primary research purpose of the regression problem. It can help people discover the laws of development and change of things from massive historical data, so as to make scientific and quantitative predictions about the future. In the classification problem, the target output is to take values in a finite discrete space, and these values can be either ordered or disordered. In regression problems, the range of output variables is ordered and continuous.Research on regression problems based on ensemble learning is a hot topic in machine learning research in recent years and has received extensive attention. Nevertheless, the application of ensemble learning to regression problems is still unsatisfactory and needs further research. The regression problem to be solved in reality often comes from a very complex social economic system, and various intricate internal and external factors have linear or nonlinear effects on it. Some are inherent factors, and some are accidental factors. A single learner can only learn for a certain type of data, and it is difficult to get satisfied learning results. Especially in the big data environment, traditional regression learning algorithms are not able to meet the learning requirements of massive complex data in terms of predictive performance and scalability. Although a great progress has been made in the related theoretical research and technology of machine learning, how to continuously improve the generalization ability and learning efficiency of learners is still an important issue and continuous pursuit of machine learning research.GrC is an effective method for simulating problem-solving thinking of human and processing analysis tasks of big data. It abstracts and divides complex problems into several simpler ones, which helps to better analyze and solve problems. Combining granular computing with ensemble learning to solve regression problems is a good idea.As the first of the four main research directions in machine learning, ensemble learning learns several different single learners on the training dataset and then combines the respective prediction results as the final output one. Therefore, in most cases, it can perform better than a single learner on generalization and stability [1]. The weak learner can be upgraded to a strong learner is one of the main theoretical foundations of ensemble learning. Kearns and Valiant gave the concepts of weak learning and strong learning from the perspective of classification problems [2]. Avnimelech and Intrator introduced the above concepts into the regression problem and gave a proof of the equivalence of the strong and weak learning of the one [3]. Another major theoretical basis for ensemble learning is the “No free lunch” theory proposed by Wolpert [4]. The implementation method of ensemble learning has received extensive attention from researchers and has achieved some research results. These results can be summarized into two categories: one is the direct strategy and the other is the overproduce and choose approach. Liu and his colleagues proposed an ensemble learning method via negative correlation learning [5]. Fang et al. proposed a selective boosting ensemble learning algorithm [6]. Breiman obtained multiple different training datasets by repeatedly sampling the original sample dataset [7]. Schapire proposed the boosting method, whose main idea is to continuously strengthen the learning of “difficult samples” in the iterative learning process [8]. Ho presented the random subspace method that uses different subsets of the feature space to train and generate multiple learners [9]. This method is different from bootstrap sampling, boosting, and cross-validation approaches and emphasizes the differences between different feature subsets. Breiman designed the output smearing method for regression problems. The primary thought is to inject Gaussian noise into the output variable [10]. The same method is also used to manipulate input variables [11]. Gheyas and Simith presented a dynamic weighted combination method, which is to dynamically adjust the corresponding weights through the predictive performance of the individual learner [12]. The research of ensemble learning on regression problems started late, and there are relatively few research results in applications, such as power load forecasting [13, 14].Granular computing is a very popular research direction in the field of computational intelligence in the past few decades. The core task of GrC is to construct, represent, and process information granules. Information granule is the foundational element of GrC. It is a set of some elements gathered together according to indistinguishability, similarity, or functionality. As a key component of knowledge representation and processing, information granules always appear with information granulation, and information granulation occurs in the process of abstracting data or inducing knowledge from information. Information (data) forms information granules through information granulation. The representation forms of information granules often include interval [15], fuzzy set [16], and rough set [17]. The purpose of information granulation is to separate complex problems into several simpler problems. This way can make us capture the details of the problem. Information granulation and information granules are almost infiltrated in various human cognition, decision-making, and reasoning processes and are closely related to information granularity. For example, in daily life and work, people usually use different time intervals such as day, month, and year to granulate time to obtain information granules of different sizes, and the size of the formed information granules implies the level of information granularity used in granulation. Through the abstraction of the problem, the “finer” and “more special” information granules are transformed into “more coarse” and “more general” information granules and “more coarse” and “more general” information granules can be refined into “finer” and “more special” information granules. GrC helps people analyze and watch the similar problem from extremely different granularities through the transformation between information granules and finally find the most suitable level of analysis and problem solving. The basic composition of GrC mainly includes three parts: granule, granular layer, and granular structure [18]. Granules are the foundational elements of GrC models [19]. The granular layer is an abstract description of the problem space according to a certain granulation criterion [20]. Granular structure is an abstract description of all granular layers. One granulation criterion corresponds to one granular layer, and different granulation rules correspond to multiple granular layers. It shows that people observe, comprehend, and solve problems from various views. All the interconnections between the granular layers form an interactive structure called the granular structure [21]. There are two basic problems in GrC: granulation and calculation based on granulation [22]. Granulation is the first step of GrC to solve the problem, and it is a process of constructing a problem-solving knowledge space. The human brain’s cognitive process of external things is a typical granulation, that is, from the overall and rough cognition, through the continuous processing and refinement of information, it finally forms a partial and detailed analysis and reasoning. The granulation process mainly involves granulation criteria, granulation methods, granule descriptions, and other issues [23]. Granularization-based computing refers to solving the original problem or logical reasoning with granules as the object of operation and the granularity level as the carrier. It is mainly divided into two types: mutual reasoning between granules on the same granular layer and conversion between granules on different granular layers. After years of study and growth, many models of GrC and their extended models have been proposed. The most representative ones are three theoretical models: the fuzzy set model, rough set model, and quotient space model.


### 1.1. Fuzzy Set Model

Zadeh presented the fuzzy set theory in 1965. He pointed out that a single element always belongs to a set to some extent and may also belong to several sets to a different degree [16]. Under the fuzzy set theory system, he presented a GrC model on the basis of word computing. The core idea of this method is to use words for calculation and reasoning instead of numbers, to achieve fuzzy reasoning, and control of complex information systems, which is in line with human thinking. In addition, Wang employed natural language knowledge to establish a linguistic dynamics system based on word computing and designed a computational theoretical framework for a linguistic dynamic system based on word computing by fusing concepts and schemes in multiple fields [24].


### 1.2. Rough Set Model

The degree to an object belonging to a certain set varies with the granularity of the attribute. In order to better characterize the ambiguity of set boundaries, Pawlak proposed the rough set theory in the 1980s. Its essential idea is to adopt indistinguishable relations (equivalence relations) to establish a division of the universe of equivalence classes to establish an approximate space. In the approximate space, upper approximate set and lower approximate set are employed to approximate a set with fuzzy boundaries [17]. The classic rough set theory is mainly aimed at a thorough information system where all feature values of the object processed are understood. In order to make the rough set theory be suitable for handling of uncomplete information systems, there are currently two main ways: one is to fill incomplete data and the other is to expand the classic rough set model. Kryszkiewicz proposed an extended rough set model via tolerance relations [25]. Stefanowski and his teamwork presented an extended rough set model on the basis of asymmetric similarity relations and an extended rough set model by quantitative tolerance relations [26]. Wang analyzed the shortcomings of the previous two expansion models and designed a rough set model based on the restricted tolerance relationship. He found that the tolerance relationship and the asymmetric similarity relationship are the two extremes of the indistinguishable relationship expansion, that is, the condition of the tolerance relationship is too loose, the condition of the asymmetric similar relationship is too tight, and the limit tolerance relationship is between them [27]. Pawlak employed the idea that elements in the equivalent category have the same membership function and explored the structure and granularity of knowledge granules [28]. Polkowski and Skowron adopted the rough mereology method, neural network technology, and the idea of knowledge granulation to design a rough neural computing model, which combines the division block of the rough set and the neural network to form an efficient neural computing method [29]. Peters and his colleagues employed the indistinguishable relationship to divide the real number into multiple subintervals and divided a whole area into several grid units, and each unit was regarded as a granule, and proposed metric is between two information granules on the adjacent relationship and the containment relationship, respectively [30].


### 1.3. Quotient Space Theory Model

B. Zhang and L. Zhang presented the theory of quotient space when studying problem solving. They said that “the recognized feature of quasi-intelligence is that human can analyze and watch the same problem from different granularity” [31]. The quotient space theory established a formal system of quotient structure and proposed a series of theories and approaches to solve problems in the fields of heuristic search, information fusion, reasoning, and path planning. There were some related research and applications [32, 33].In addition, many new models have been proposed, such as granular matrices for reduction and evaluation [34], three-way decision model [35–37], and ensemble learning for big data based on MapReduce [38–44]. In this study, we adopt parallel granulation and ensemble learning based on MapReduce to solve the regression problem from granular computing angle and enhance the performance of regression and efficiency of granulation.


## 1.1. Fuzzy Set Model

Zadeh presented the fuzzy set theory in 1965. He pointed out that a single element always belongs to a set to some extent and may also belong to several sets to a different degree [16]. Under the fuzzy set theory system, he presented a GrC model on the basis of word computing. The core idea of this method is to use words for calculation and reasoning instead of numbers, to achieve fuzzy reasoning, and control of complex information systems, which is in line with human thinking. In addition, Wang employed natural language knowledge to establish a linguistic dynamics system based on word computing and designed a computational theoretical framework for a linguistic dynamic system based on word computing by fusing concepts and schemes in multiple fields [24].


## 1.2. Rough Set Model

The degree to an object belonging to a certain set varies with the granularity of the attribute. In order to better characterize the ambiguity of set boundaries, Pawlak proposed the rough set theory in the 1980s. Its essential idea is to adopt indistinguishable relations (equivalence relations) to establish a division of the universe of equivalence classes to establish an approximate space. In the approximate space, upper approximate set and lower approximate set are employed to approximate a set with fuzzy boundaries [17]. The classic rough set theory is mainly aimed at a thorough information system where all feature values of the object processed are understood. In order to make the rough set theory be suitable for handling of uncomplete information systems, there are currently two main ways: one is to fill incomplete data and the other is to expand the classic rough set model. Kryszkiewicz proposed an extended rough set model via tolerance relations [25]. Stefanowski and his teamwork presented an extended rough set model on the basis of asymmetric similarity relations and an extended rough set model by quantitative tolerance relations [26]. Wang analyzed the shortcomings of the previous two expansion models and designed a rough set model based on the restricted tolerance relationship. He found that the tolerance relationship and the asymmetric similarity relationship are the two extremes of the indistinguishable relationship expansion, that is, the condition of the tolerance relationship is too loose, the condition of the asymmetric similar relationship is too tight, and the limit tolerance relationship is between them [27]. Pawlak employed the idea that elements in the equivalent category have the same membership function and explored the structure and granularity of knowledge granules [28]. Polkowski and Skowron adopted the rough mereology method, neural network technology, and the idea of knowledge granulation to design a rough neural computing model, which combines the division block of the rough set and the neural network to form an efficient neural computing method [29]. Peters and his colleagues employed the indistinguishable relationship to divide the real number into multiple subintervals and divided a whole area into several grid units, and each unit was regarded as a granule, and proposed metric is between two information granules on the adjacent relationship and the containment relationship, respectively [30].


## 1.3. Quotient Space Theory Model

B. Zhang and L. Zhang presented the theory of quotient space when studying problem solving. They said that “the recognized feature of quasi-intelligence is that human can analyze and watch the same problem from different granularity” [31]. The quotient space theory established a formal system of quotient structure and proposed a series of theories and approaches to solve problems in the fields of heuristic search, information fusion, reasoning, and path planning. There were some related research and applications [32, 33].In addition, many new models have been proposed, such as granular matrices for reduction and evaluation [34], three-way decision model [35–37], and ensemble learning for big data based on MapReduce [38–44]. In this study, we adopt parallel granulation and ensemble learning based on MapReduce to solve the regression problem from granular computing angle and enhance the performance of regression and efficiency of granulation.


## 2. Contributions

In this study, a regression problem is equivalently transformed into the fuzzy granular space solution, and BFGRT are constructed from angle of GrC and ensemble learning to solve the regression problem. The main contributions are as follows.(i)
First, an adaptive clustering algorithm is proposed, which can adaptively find the optimal cluster centers. It is a global optimization algorithm that solves the problem that classic clustering algorithms rely heavily on the initial cluster centers and are easy to fall into local optimal solution.(ii)
Second, parallel fuzzy granulation of data based on the above clustering algorithm combined with MapReduce is presented, which solves the problem of high complexity of traditional granulation and enhances granulation efficiency(iii)
Third, we define fuzzy granules and related metric operators, design a loss function, construct an individual fuzzy granular regression tree in the granular space by optimizing the loss function, and then parallelly integrate multiple fuzzy granular regression trees built by different attributes into a stronger learner based on MapReduce to accurately solve the regression problem


## 3. The Regression Problem

The regression problem is divided into two processes: learning and prediction. Suppose thatS=T,A,Y,h,V be a regression system, where T=x1,y1,x2,y2,…,xn,yn is the set of instances (xi∈ℝm, yi∈ℝ), A=a1,a2,…,am is the attribute set, V=∪h∈HVa is the set of range, Va is range of the attribute a, and h:X×A⟶V is an information function (it assigns a value to each instance on each attribute, namely, ∀h∈H,x∈X,hx,a∈Va). Let X=x1,x2,…,xn and Y=y1,y2,…,yn, where yi corresponds to the output of xii=1,2,…,n. The learning system constructs a model Y=fX based on the instance set. For the test instance xn+1, the learning system can predict the corresponding output yn+1 by Y=fX.


## 4. The Primary Algorithm

In order to find the solution of the problem mentioned above, the algorithm will be presented through three stages. First, cluster the data. The purpose is to prepare for the parallel fuzzy granulation of the data. In this process, we design a novel clustering algorithm that adaptively optimizes the cluster center. According to the algorithm, cluster centers of instances are automatically calculated instead of giving the number of clusters in advance. Next, these cluster centers can be used as reference objects independent of the data to granulate data parallelly. Finally, we transform this instance regression problem into a fuzzy granular regression problem in the granular space. In the fuzzy granular space, we design related operators and loss functions, construct multiple weak fuzzy granular regression trees by optimizing the loss function, and then integrate these weak fuzzy granular regression trees into a strong learner to predict the regression value. The process is shown in Figure1.Figure 1
Overview of BFGRT.


### 4.1. Clustering Algorithm with Automatic Optimization of Cluster Centers

Classic clustering algorithms need to specify the number of cluster centers in advance to obtain clustering results. The methods depend heavily on the above parameter. If the number of cluster centers is not suitable, it will fall into a local minimum solution. An adaptive clustering algorithm that adaptively selects the number of cluster centers is presented, which is a global optimization algorithm. The principle is as follows. As well-known, if the standard deviationδ of cluster centers is larger and the standard deviation σk within clusters is smaller, then the performance is better. Therefore, a loss function Lσ,δ,K=log∑k=1Kσk2−logδ2 is designed as the evaluation criterion, where σk denotes the standard deviation of the kth cluster and K represents the number of cluster centers. The aim is to decrease the loss function value by adjusting cluster centers until the maximum iteration is achieved or the loss function value hardly changes. In each iteration, a set of cluster centers corresponding to loss function value can be obtained and be integrated as an evaluated set. In each iteration, the ratio of the farthest distance from the remaining instance points to cluster centers and the sum of the farthest distances from all instance points to each cluster center is the probability selected as the next cluster center. When the termination condition is achieved, find a set of cluster centers corresponding to the minimum cost function from this evaluation set, which is what is required.Step 1: remove the instances missing some attribute valuesStep 2: normalize instancesStep 3: initialize parameters, such as maximum iterationI, evaluated set EV=ϕ (contains cluster centers and loss function value), and current iteration i=1Step 4: initialize current cluster center setCi=ϕ and randomly select one instance point as the cluster center c1=xi, k=1Step 5: calculate the farthest distance between the remaining instance points and all cluster centers and letdxj=max1≤k≤idisck,xj, and the probability of the instance selected as the next cluster center is pxj=dxj2/∑i=1ndxi2,j=1,2,…,n.Step 6: ifxj is selected as a cluster center, then(1)ck=xj,Ci=Ci∪ck,k=k+1.Step 7: ifk<i+1, go Step 5. Otherwise, go Step 8.Step 8: calculate loss functionLiδ,σ,k and update the evaluated set EV=EV∪Ci,Lδ,σ,iStep 9: update iterationi=i+1Step 10: ifi>I or ∀N∈1,i−j,Lδ,σ,j−Lδ,σ,j+N2<ϵ, go Step 11 (here, j+N<i, ϵ is a small positive number). Otherwise, go Step 4.Step 11: in the evaluated set EV, select the cluster centers according to(2)C∗=argmin1≤j≤iLδ,σ,j,Namely,C∗=c1,c2,…,cC∗ and the optimization number of cluster centers K=C∗ (⋅ expresses the number of elements of the set).Step 12: end.Algorithm1 shows the pseudocode of this principle.Algorithm 1: Clustering algorithm with automatic optimization of cluster centers.
Input: instance setX, maximum iteration I, threshold value ϵ,NOutput: optimization cluster center setC∗(1)
Remove instances missing some attribute values.(2)
Normalize each attribute value into0,1.(3)
EV=ϕ\\Let evaluated set be an empty set.(4)
i=1\\Initialize current iteration.(5)
WHILEi<I+1 OR Lδ,σ,i−Lδ,σ,i+N2>ϵ(6)
Ci=ϕ. Initialize the current cluster center set.(7)
k=1. Initialize the number of cluster center.(8)
ck=RandomSelectX,1\\Random choose 1 instance point as cluster center.(9)
Ci=Ci∪ck(10)
k=k+1(11)
WHILEk<i+1(12)
∀j∈X,dxj=max1≤k≤ndisck,xj(13)
pxj=dxj2/∑t=1ndck,xt2.\\The probability of xj that is selected as next cluster center(14)
p = GenProb(); \\Random generate a probability.(15)
IFpxj>p THEN ck=xj;Ci=Ci∪xj;k=k+1;(16)
END WHILE\\k<i+1(17)
EV=EV∪Ci,Lδ,σ,i. Calculate the loss function value and cluster center in this iteration and update the evaluated set.(18)
i=i+1.\\Update the current iteration.(19)
END WHILE\\i<I+1(20)
C∗=argmax1≤j≤iLδ,σ,j. In the evaluated set EV, choose the cluster center set with minimum loss function value.Return the optimization cluster centers and their number.(21)
C∗=c1,c2,…,cC∗, k∗=C∗ (⋅ represents the number of elements of the set).


### 4.2. Parallel Fuzzy Granulation

In granulation, serial granulation is adopted in most methods. To enhance efficiency, we propose parallel fuzzy granulation. First, cluster centers can be obtained by the approach mentioned above. Then, instances are divided into a set of instance subsets, which are fuzzy granulated by cluster centers. This process is executed parallelly by MapReduce. According to Algorithm1, the cluster center set C=c1,c2,…,cK can be obtained.For∀xi∈X, ∀aj∈A, and ∀ck∈C, the distance between xi and ck on the attribute aj can be written as follows:(3)sxi,aj,ck=11+exp−hxi,aj−hck,aj,where 0≤hxi,aj≤1, 0≤hck,aj≤1, and 0≤sxi,aj,ck≤1 are established. A fuzzy granule induced by the instance xi and the cluster center cj can be written as follows:(4)q¯xi,aj=sxi,aj,c1c1+sxi,aj,c2c2+⋯+sxi,aj,cKcK.For simplicity, the fuzzy granule uses also the following equation to denote.(5)q¯xi,aj=∑t=1Ksxi,aj,ctct.Here, symbol “−” is a separator and symbol “+” is an union operation, that is, fuzzy granule q¯xi,aj denotes the distance set between instance xi and cluster centers. Its cardinal can be written as(6)q¯xi,aj=∑t=1Ksxi,aj,ct.Four operators of fuzzy granule can be designed. For∀e,f∈R, operator ∪ and operator ∩ can be written as follows:(7)e∪f=e+f−ef−1−νefν+1−ν1−ef,e∩f=efν+1−νe+f−ef,where ν∈0,∞ is a parameter. For ∀x,x′∈X, and ∀a∈A, the operators between the fuzzy granule formed by x and the one induced by x′ are written as follows:(8)q¯x,a∪q¯x′,a=∑t=1Ksx,a,ct∪sx′,a,ctct,q¯x,a∩q¯x′,a=∑t=1Ksx,a,ct∩sx′,a,ctct,q¯x,a−q¯x′,a=∑t=1Ksx,a,ct−sx′,a,ctct,q¯x,a⊕q¯x′,a=q¯x,a∪q¯x′,a−q¯x,a∩q¯x′,a.For∀U⊆A and U=a1,a2,…,aUU≤A, fuzzy granular vector induced by x on the attribute set U can be written as(9)Q¯x,U=Q¯x,a1a1+Q¯x,a2a2+⋯+Q¯x,aUaU=∑t=1Uq¯x,rtat,where symbol “+” denotes an union operation and symbol “−” represents a separator. Its cardinal can be obtained as follows:(10)Q¯x,U=∑t=1Uq¯x,at.Operators of fuzzy granular vector are written as follows:(11)Q¯x,U∪Q¯x′,U=∑t=1Uq¯x,at∪q¯x′,atat,Q¯x,U∩Q¯x′,U=∑t=1Uq¯x,at∩q¯x′,atat,Q¯x,U−Q¯x′,U=∑t=1Uq¯x,at−q¯x′,atat,Q¯x,U⊕Q¯x′,U=∑t=1Uq¯x,at⊕q¯x′,atat.According to the definitions, the distance between the two fuzzy granular vectors is given by(12)sQ¯x,U,Q¯x′,U=1U∗C∑a∈UQ¯x,a⊕Q¯x′,aQ¯x,r∪Q¯x′,r.From the above fuzzy granulation, it can be seen that the fuzzy granules are obtained by calculating instances and cluster centers using the fuzzy operators, and fuzzy granular space consists of these fuzzy granules.Theorem 1.
For∀x,x′∈X, ∀U⊆A, and ∀a∈U, the distance between fuzzy granular vectors satisfies(13)0≤sQ¯x,U,Q¯x′,U≤1.Proof.
According to the definition of fuzzy granule, we haveq¯x,a=∑t=1Ksx,a,ct/ct and q¯x′,a=∑t=1Ksx′,a,ct/ct. Also, from equation (3), we get 0≤sx,a,ct≤1 and 0≤sx′,a,ct≤1. Because of q¯x,a=∑ct∈Csx,a,ct and q¯x′,a=∑ct∈Csx,a′,ct, the inequalities 0≤q¯x,a≤C and 0≤q¯x′,a≤C can be obtained. Equation (9) shows Qx,U=∑t=1Uq¯x,rt/rt and Qx′,U=∑t=1Uqx′,rt. We can further obtain 0≤Q¯x,U≤U∗C and 0≤Q¯x′,U≤U∗C. From q¯x,a⊕q¯x′,a=qxi,r∪qxj,r−qxi,r∩qx,a, we get(14)0≤∑r∈Uqxi,r⊕qxj,rqx,r∪qx′,r≤U∗C.
We divide both sides of the formula byU∗C to achieve 0≤1/U∗C∑a∈Uq¯x,a⊕q¯x′,a/q¯x,a∪q¯x′,a≤1, that is, we prove(15)0≤sQ¯x,U,Q¯x′,U≤1.Theorem 2.
For∀x∈X, the attribute subsets U and V satisfy U⊆V⊆A. Let Q¯x,V and Q¯x,U be fuzzy granular vectors of x on V and U, respectively. Then, Q¯x,U≤Q¯x,V has been proven.Proof.
For∀at∈U, equation (9) shows that Q¯x,U=∑t=1Uq¯x,at/at. Thanks to U⊆V, we have that for ∀at∈V, Q¯x,V=∑t=1Vq¯x,at/at. Because of U⊆V⊆A, for a∈U, we get a∈V and U≤V, that is, if q¯x,a∈Q¯x,U, we can obtain q¯x,a∈Qx,V. In sum, Q¯x,U≤Q¯x,V is proved.Now, we take a case to describe the fuzzy granulation process.Example 1.
As illustrated in Table1, given an instance set X=x1,x2,x3,x4, an attribute set A=a1,a2,a3, regression value set Y=y1,y2,y3,y4, cluster center set C=c1,c2, and parameter ν=0.5, the fuzzy granulation is as follows.
We take instancex1 as an example. The distances between x1 and the cluster centers c1 and c2 on the attributes a1, a2, and a3 are given as follows:sx1,a1,c1=1/1+exp−0.20−0.25=0.5125sx1,a1,c2=1/1+exp−0.20−0.15=0.5125sx1,a2,c1=1/1+exp−0.30−0.35=0.5125sx1,a2,c2=1/1+exp−0.30−0.45=0.5374sx1,a3,c1=1/1+exp−0.10−0.30=0.5498sx1,a3,c2=1/1+exp−0.10−0.60=0.6225
Equation (5) shows that fuzzy granules of x1 on a1, a2, and a3 are calculated as follows:q¯x1,a1=0.5125/c1+0.5125/c2q¯x1,a2=0.5125/c1+0.5374/c2q¯x1,a3=0.5498/c1+0.6225/c2
In the same way, fuzzy granules ofx2 on A are obtained as follows:q¯x2,a1=0.5125/c1+0.5374/c2q¯x2,a2=0.5374/c1+0.5622/c2q¯x2,a3=0.5250/c1+0.5987/c2
According toq¯x1,a1∪q¯x2,a1=∑j=1Ke+f−ef−1−νef/ν+1−ν1−ef/cj, here ν=0.5. When j=1, suppose that e=dx1,a1,c1 and f=dx2,a1,c1. When j=2, suppose that e=dx1,a1,c2 and f=dx2,a1,c2), we have(16)q¯x1,a1∪q¯x2,a1=∑j=12e+f−ef−1−νef/ν+1−ν1−efcj=0.5125+0.5125−0.5125∗0.5125−1−0.5∗0.5125∗0.5125/0.5+1−0.51−0.5125∗0.5125c1+0.5125+0.5374−0.5125∗0.5374−1−0.5∗0.5125∗0.5374/0.5+1−0.51−0.5125∗0.5374c2=0.7164c1+0.7385c2,q¯x1,a1∩q¯x2,a1=∑j=12ef/ν+1−νe+f−efcj=0.5125∗0.5125/0.5+1−0.50.5125+0.5125−0.5125∗0.5125c1+0.5125∗0.5374/0.5+1−0.50.5125+0.5374−0.5125∗0.5374c2=0.2981c1+0.3024c2,q¯x1,a1⊕q¯x2,a1=q¯x1,a1∪q¯x2,a1−q¯x1,a1∩q¯x2,a1=0.7164−0.2981c1+0.7385−0.3024c2=0.4183c1+0.4361c2,q¯x1,a1⊕q¯x2,a1=q¯x1,a1∪q¯x2,a1−q¯x1,a1∩q¯x2,a1=04183c1+0.4361c2=0.8544.
Similarly, we can get(17)q¯x1,a2⊕q¯x2,a2=0.4280c1+0.4253c2=0.8533,q¯x1,a3⊕q¯x2,a3=0.4269c1+0.4106c2=0.8375.
Thus, we can obtain the distance between fuzzy granular vectors ofx1 and x2 on A with ν=0.5 by(18)sQ¯x1,A,Q¯x2,A=1A∗C∑a∈Aq¯x1,a⊕q¯x2,aq¯x1,a∩q¯x2,a=0.8544+0.8533+0.83753∗2≈0.42.Table 1
Fuzzy granulation and metric.
X|C|AYνa1a2a3yνx10.200.300.100.300.50x20.300.200.200.200.50x30.400.200.300.500.50x40.100.100.400.400.50c10.250.350.30——c20.150.450.60——


### 4.3. Fuzzy Granular Regression Tree

After the above fuzzy granulation, the data can be transformed into fuzzy granules. In fuzzy granular space, we give the following definition.Definition 1.
Suppose thatS=T,A,C,Y is a regression system, where T=x1,y1,x2,y2,…,xn,yn is a instance set, xi is a input variable, and yi is output variable corresponding to xi. Let X=xi|i=1,2,…,n, and Y=yi|i=1,2,…,n. C=ci|i=1,2,…,K is a cluster center set and A=ai|i=1,2,…,m an attribute set. For ∀aj∈A,xi∈X, we can obtain fuzzy granule q¯xi,aj via fuzzy granulation (the following is abbreviated as q¯). Fuzzy granules and operators can create new fuzzy granules, such as g¯=w¯∩q¯∪h¯. Repeating this process can expand a fuzzy granular space G¯ on T. According to training data, a fuzzy granular rule base can be generated as(19)R=ri|ri=<Q¯xi,A,yi>,xi∈X,yi∈Y.
A fuzzy granular regression tree corresponds to a division of the fuzzy granular space and output value on the divided unit.
Suppose that the input space has been splitted intod units D1,D2,…,Dd, and there is a fixed output value zi on each unit Di. Thus, the fuzzy granular regression tree can be expressed as(20)fQ¯=∑i=1dziIQ¯∈Di.
Here,Q¯ is a fuzzy granular vector and I is an indicative function, which can be written as(21)I=1,ifQ¯∈Di,0,otherwise,zi=1Di∑Q¯j∈Diyj,where Di denotes the number of the fuzzy granular vector. The question becomes how to divide the fuzzy granular space.
Here, we use a heuristic method to select featureaj as the segmentation variable and the cardinal of fuzzy granule q¯xs,aj as the optimal segmentation point. Two areas are defined by(22)D1j,s=Q¯x,Aq¯x,aj|≤q¯xs,aj,D2j,s=Q¯x,Aq¯x,aj|>q¯xs,aj.
Then, find the optimal segmentation variableaj and point q¯xs,aj. Specifically, solve the loss function(23)minj,sminz1∑Q¯i∈D1j,syi−z12+minz2∑Q¯i∈D2j,syi−z22.
For input variableaj, the optimal segmentation point s can be calculated as(24)z^1=1D1j,s∑Q¯i∈D1j,syi,z^2=1D2j,s∑Q¯i∈D2j,syi,where ⋅ denotes the number of elements.
Traverse all input variables and find the optimal segmentation variablej to form a pair j,s. Divide the input space into two areas in turn. Then, repeat the above division process for each area until the terminal condition is met. In this way, a fuzzy granule regression tree is generated. The algorithm is described in Algorithm 2.Algorithm 2: Fuzzy granular regression tree.
Input: instance setX, regression value set YOutput: fuzzy granular treef(1)
Remove the instances missing some attribute values.(2)
Normalize each attribute value.(3)
Calculate the cluster center setC∗=c1,c2,…,cK (Algorithm 1).(4)
X1∪X2∪⋯∪Xp=X and ∀Xl,Xt∈X,Xl∩Xt=ϕ. // Parallel distributed fuzzy granulation.(5)
∀Xt⊂X//This is parallel process. Here, take Xt as example.FORi=1 to Xt∃xi∈XtFORj=1 to m∃a∈A, sample x is fuzzy granulated as q¯xi,a=∑j=1Ksxi,a,cj/cjEND FORBuild a fuzzy granular vectorQ¯x,A=∑j=1Aq¯x,aj/aj;Get label ofxi, yi;A fuzzy granular rule can be built.ri=<Q¯xi,A,yi>;END FOR(6)
Select the optimal segmentation variablej (i.e., the attribute aj) and segmentation point s (i.e., q¯xs,aj) by solving equation minj,sminz1∑Q¯i∈D1j,syi−z12+minz2∑Q¯i∈D2j,syi−z22That is, traverse variablej to find the pair j,s that minimizes the loss function by fixing the segmentation variable j and scanning segmentation point s.(7)
Divide the area with the selected pairj,s and decide output value as follows:z^1=1/D1j,s∑Q¯i∈D1j,syiz^2=1/D2j,s∑Q¯i∈D2j,syiD1j,s=Q¯x,A‖q¯x,aj|≤q¯xs,ajD2j,s=Q¯x,A‖q¯x,aj|>q¯xs,aj(8)
Continue to call Step 6 and Step 7 for the two subregions until the number of split nodes isA.(9)
Divide the input fuzzy granular space intod regions D1,D2,…,Dd and generate a fuzzy granular regression treefQ¯=∑i=1dz^iIQ¯∈Di


### 4.4. Boosted Fuzzy Granular Regression Trees

BFGRT can be an algorithm that integrates multiple fuzzy granular regression trees through the idea of ensemble learning to draw conclusions. It does not rely on only one fuzzy granular regression tree but adopts many fuzzy granular regression trees to solve the task together, using the weighted average of the regression values of multiple fuzzy granular regression trees as the final regression value. Assuming thatT is the instance set, fuzzy granular space is G¯, fuzzy granular rule base is R, the number of instances is n, and the number of attributes is m, we construct parallelly t fuzzy granular regression trees as follows: Step 1: createJmap tasksStep 2: instance set extraction: randomly drawn fuzzy granular vectors from R with replacement and repeat them n times. The probability of each fuzzy granular vector being selected is 1/n. The unselected fuzzy granular vectors form the out of bag data as the test set.Step 3: attribute extraction: extractt attributes from A to compose attribute subset BB⊂AStep 4: attribute selection: calculate the optimal segmentation attributeaj and the optimal segmentation point q¯xs,aj in the data set of node, divide the node into two child nodes, and allocate the remaining fuzzy granular vectors to the child nodesStep 5: generate a fuzzy granular tree. Repeat Step 3 in the fuzzy granular vector set of each child node to recursively split the nodes until all leaf nodes are generated.Step 6: repeat steps 2–5 to getJ different fuzzy granular regression trees, which correspond to JMap tasksStep 7: BFGRT can consist ofJ fuzzy granular regression trees and the process can be executed by reduce task, that is,(25)FQ¯=∑j=1Jωj⋅fjQ¯,Whereωj=1−expδj/∑i=1Jexpδi, and δj represents the root mean square error (RMSE) of jth fuzzy granular tree. This detail of the algorithm can be illustrated in Algorithm 3.Algorithm 3: Boosted fuzzy granular regression trees.
Input: instance setX, regression value set Y, the number of fuzzy granular regression tree JOutput: boosted fuzzy granular regression treesF(1)
Get a fuzzy granular vector rule baseR by parallel fuzzy granulation of the dataset (see Algorithm 2, Algorithm 4, and Algorithm 5.)(2)
CreateJ tasks, namely, map1,map2,…,mapJ(3)
Execute the following operations for each independent task (j=1,2,…,J):MapFunction(key, value), where key = offset of instance andvalue=n,t indicates that n fuzzy granular vectors are randomly//selected fromR.//Randomly selectt attributes from the attribute set A (constitutes attribute subset Bjt, that is, Bjt⊂A)//Form a fuzzy granular rule setRj, build a fuzzy granular regression tree fj, and get its RMSEδj=1/n∑i=1nz^i−yi2, where z^i=fjQ¯xi,Bjt,yi∈Rj.(4)
FORi=1 to instances-total-number(5)
SubsetID =i mod J(6)
context.write(SubsetID, FuzzyGranularVector)(7)
END FOREND MapFunction(8)
ReduceFunction(key, value)//Here, key = SubsetID, value = FuzzyGranualrVector(9)
Job.addCache(FuzzyGranularVector[SubsetID])(10)
fSubsetID,δSubsetID = train(SubsetID, FuzzyGranularVector)//(See Step 6–Step 9 of Algorithm 2.)(11)
context.write(1,(fSubsetID,δSubsetID))END ReduceFunction(12)
F⋅=∑j=1Jωj⋅fj⋅//Calculate BFGRT F composed of the linear combination of J fuzzy granular regression trees.Whereωj=1−expδj/∑i=1Jexpδi.Algorithm 4: Map function of parallel fuzzy granulation.
Input: <offset, instance> andt (the number of divided instance sets)Output: <SubsetID, instance>(1)
FORi=1 to instances-total-number(2)
SubsetID =i mod t(3)
context.write(SubsetID, instance)(4)
END FORAlgorithm 5: Reduce function of parallel fuzzy granulation.
Input: SubSetID, ClusterSet C, and instance subset X[SubSetID]Output: Fuzzy Granular Set(1)
Job.addCache(X[SubSetID])(2)
FuzzyGranularSubSetSubSetID = Granulation(X[SubSetID],C)//See Step 5 of Algorithm 2.(3)
FuzzyGranularSet = context.write(1FuzzyGranularSubsetSubSetID)


### 4.5. Regression

Given a test instance, we fuzzy granulate the test instance to get a fuzzy granular vector. Then, use BFGRT to predict the fuzzy granular vector to achieve the regression value. Algorithm6 demonstrates the algorithm.Algorithm 6: The algorithm of prediction.
Input: test instancex, cluster center set C, BFGRT F=f1,f2,…,fJ;ω1,ω2,…,ωJ.Output: regression valuey^∗ of instance x(1)
Granulatex to fuzzy granular vector Q¯x,A(2)
Forj=1 to Jy^j=fjQ¯x,Aj, where according to the parameters of fj, attribute set selected satisfies Aj⊂Aj=j+1End For(3)
FQx,A=∑j=1Jωj⋅y^j(4)
y^∗=FQx,A(5)
Returny^∗


## 4.1. Clustering Algorithm with Automatic Optimization of Cluster Centers

Classic clustering algorithms need to specify the number of cluster centers in advance to obtain clustering results. The methods depend heavily on the above parameter. If the number of cluster centers is not suitable, it will fall into a local minimum solution. An adaptive clustering algorithm that adaptively selects the number of cluster centers is presented, which is a global optimization algorithm. The principle is as follows. As well-known, if the standard deviationδ of cluster centers is larger and the standard deviation σk within clusters is smaller, then the performance is better. Therefore, a loss function Lσ,δ,K=log∑k=1Kσk2−logδ2 is designed as the evaluation criterion, where σk denotes the standard deviation of the kth cluster and K represents the number of cluster centers. The aim is to decrease the loss function value by adjusting cluster centers until the maximum iteration is achieved or the loss function value hardly changes. In each iteration, a set of cluster centers corresponding to loss function value can be obtained and be integrated as an evaluated set. In each iteration, the ratio of the farthest distance from the remaining instance points to cluster centers and the sum of the farthest distances from all instance points to each cluster center is the probability selected as the next cluster center. When the termination condition is achieved, find a set of cluster centers corresponding to the minimum cost function from this evaluation set, which is what is required.Step 1: remove the instances missing some attribute valuesStep 2: normalize instancesStep 3: initialize parameters, such as maximum iterationI, evaluated set EV=ϕ (contains cluster centers and loss function value), and current iteration i=1Step 4: initialize current cluster center setCi=ϕ and randomly select one instance point as the cluster center c1=xi, k=1Step 5: calculate the farthest distance between the remaining instance points and all cluster centers and letdxj=max1≤k≤idisck,xj, and the probability of the instance selected as the next cluster center is pxj=dxj2/∑i=1ndxi2,j=1,2,…,n.Step 6: ifxj is selected as a cluster center, then(1)ck=xj,Ci=Ci∪ck,k=k+1.Step 7: ifk<i+1, go Step 5. Otherwise, go Step 8.Step 8: calculate loss functionLiδ,σ,k and update the evaluated set EV=EV∪Ci,Lδ,σ,iStep 9: update iterationi=i+1Step 10: ifi>I or ∀N∈1,i−j,Lδ,σ,j−Lδ,σ,j+N2<ϵ, go Step 11 (here, j+N<i, ϵ is a small positive number). Otherwise, go Step 4.Step 11: in the evaluated set EV, select the cluster centers according to(2)C∗=argmin1≤j≤iLδ,σ,j,Namely,C∗=c1,c2,…,cC∗ and the optimization number of cluster centers K=C∗ (⋅ expresses the number of elements of the set).Step 12: end.Algorithm1 shows the pseudocode of this principle.Algorithm 1: Clustering algorithm with automatic optimization of cluster centers.
Input: instance setX, maximum iteration I, threshold value ϵ,NOutput: optimization cluster center setC∗(1)
Remove instances missing some attribute values.(2)
Normalize each attribute value into0,1.(3)
EV=ϕ\\Let evaluated set be an empty set.(4)
i=1\\Initialize current iteration.(5)
WHILEi<I+1 OR Lδ,σ,i−Lδ,σ,i+N2>ϵ(6)
Ci=ϕ. Initialize the current cluster center set.(7)
k=1. Initialize the number of cluster center.(8)
ck=RandomSelectX,1\\Random choose 1 instance point as cluster center.(9)
Ci=Ci∪ck(10)
k=k+1(11)
WHILEk<i+1(12)
∀j∈X,dxj=max1≤k≤ndisck,xj(13)
pxj=dxj2/∑t=1ndck,xt2.\\The probability of xj that is selected as next cluster center(14)
p = GenProb(); \\Random generate a probability.(15)
IFpxj>p THEN ck=xj;Ci=Ci∪xj;k=k+1;(16)
END WHILE\\k<i+1(17)
EV=EV∪Ci,Lδ,σ,i. Calculate the loss function value and cluster center in this iteration and update the evaluated set.(18)
i=i+1.\\Update the current iteration.(19)
END WHILE\\i<I+1(20)
C∗=argmax1≤j≤iLδ,σ,j. In the evaluated set EV, choose the cluster center set with minimum loss function value.Return the optimization cluster centers and their number.(21)
C∗=c1,c2,…,cC∗, k∗=C∗ (⋅ represents the number of elements of the set).


## 4.2. Parallel Fuzzy Granulation

In granulation, serial granulation is adopted in most methods. To enhance efficiency, we propose parallel fuzzy granulation. First, cluster centers can be obtained by the approach mentioned above. Then, instances are divided into a set of instance subsets, which are fuzzy granulated by cluster centers. This process is executed parallelly by MapReduce. According to Algorithm1, the cluster center set C=c1,c2,…,cK can be obtained.For∀xi∈X, ∀aj∈A, and ∀ck∈C, the distance between xi and ck on the attribute aj can be written as follows:(3)sxi,aj,ck=11+exp−hxi,aj−hck,aj,where 0≤hxi,aj≤1, 0≤hck,aj≤1, and 0≤sxi,aj,ck≤1 are established. A fuzzy granule induced by the instance xi and the cluster center cj can be written as follows:(4)q¯xi,aj=sxi,aj,c1c1+sxi,aj,c2c2+⋯+sxi,aj,cKcK.For simplicity, the fuzzy granule uses also the following equation to denote.(5)q¯xi,aj=∑t=1Ksxi,aj,ctct.Here, symbol “−” is a separator and symbol “+” is an union operation, that is, fuzzy granule q¯xi,aj denotes the distance set between instance xi and cluster centers. Its cardinal can be written as(6)q¯xi,aj=∑t=1Ksxi,aj,ct.Four operators of fuzzy granule can be designed. For∀e,f∈R, operator ∪ and operator ∩ can be written as follows:(7)e∪f=e+f−ef−1−νefν+1−ν1−ef,e∩f=efν+1−νe+f−ef,where ν∈0,∞ is a parameter. For ∀x,x′∈X, and ∀a∈A, the operators between the fuzzy granule formed by x and the one induced by x′ are written as follows:(8)q¯x,a∪q¯x′,a=∑t=1Ksx,a,ct∪sx′,a,ctct,q¯x,a∩q¯x′,a=∑t=1Ksx,a,ct∩sx′,a,ctct,q¯x,a−q¯x′,a=∑t=1Ksx,a,ct−sx′,a,ctct,q¯x,a⊕q¯x′,a=q¯x,a∪q¯x′,a−q¯x,a∩q¯x′,a.For∀U⊆A and U=a1,a2,…,aUU≤A, fuzzy granular vector induced by x on the attribute set U can be written as(9)Q¯x,U=Q¯x,a1a1+Q¯x,a2a2+⋯+Q¯x,aUaU=∑t=1Uq¯x,rtat,where symbol “+” denotes an union operation and symbol “−” represents a separator. Its cardinal can be obtained as follows:(10)Q¯x,U=∑t=1Uq¯x,at.Operators of fuzzy granular vector are written as follows:(11)Q¯x,U∪Q¯x′,U=∑t=1Uq¯x,at∪q¯x′,atat,Q¯x,U∩Q¯x′,U=∑t=1Uq¯x,at∩q¯x′,atat,Q¯x,U−Q¯x′,U=∑t=1Uq¯x,at−q¯x′,atat,Q¯x,U⊕Q¯x′,U=∑t=1Uq¯x,at⊕q¯x′,atat.According to the definitions, the distance between the two fuzzy granular vectors is given by(12)sQ¯x,U,Q¯x′,U=1U∗C∑a∈UQ¯x,a⊕Q¯x′,aQ¯x,r∪Q¯x′,r.From the above fuzzy granulation, it can be seen that the fuzzy granules are obtained by calculating instances and cluster centers using the fuzzy operators, and fuzzy granular space consists of these fuzzy granules.Theorem 1.
For∀x,x′∈X, ∀U⊆A, and ∀a∈U, the distance between fuzzy granular vectors satisfies(13)0≤sQ¯x,U,Q¯x′,U≤1.Proof.
According to the definition of fuzzy granule, we haveq¯x,a=∑t=1Ksx,a,ct/ct and q¯x′,a=∑t=1Ksx′,a,ct/ct. Also, from equation (3), we get 0≤sx,a,ct≤1 and 0≤sx′,a,ct≤1. Because of q¯x,a=∑ct∈Csx,a,ct and q¯x′,a=∑ct∈Csx,a′,ct, the inequalities 0≤q¯x,a≤C and 0≤q¯x′,a≤C can be obtained. Equation (9) shows Qx,U=∑t=1Uq¯x,rt/rt and Qx′,U=∑t=1Uqx′,rt. We can further obtain 0≤Q¯x,U≤U∗C and 0≤Q¯x′,U≤U∗C. From q¯x,a⊕q¯x′,a=qxi,r∪qxj,r−qxi,r∩qx,a, we get(14)0≤∑r∈Uqxi,r⊕qxj,rqx,r∪qx′,r≤U∗C.
We divide both sides of the formula byU∗C to achieve 0≤1/U∗C∑a∈Uq¯x,a⊕q¯x′,a/q¯x,a∪q¯x′,a≤1, that is, we prove(15)0≤sQ¯x,U,Q¯x′,U≤1.Theorem 2.
For∀x∈X, the attribute subsets U and V satisfy U⊆V⊆A. Let Q¯x,V and Q¯x,U be fuzzy granular vectors of x on V and U, respectively. Then, Q¯x,U≤Q¯x,V has been proven.Proof.
For∀at∈U, equation (9) shows that Q¯x,U=∑t=1Uq¯x,at/at. Thanks to U⊆V, we have that for ∀at∈V, Q¯x,V=∑t=1Vq¯x,at/at. Because of U⊆V⊆A, for a∈U, we get a∈V and U≤V, that is, if q¯x,a∈Q¯x,U, we can obtain q¯x,a∈Qx,V. In sum, Q¯x,U≤Q¯x,V is proved.Now, we take a case to describe the fuzzy granulation process.Example 1.
As illustrated in Table1, given an instance set X=x1,x2,x3,x4, an attribute set A=a1,a2,a3, regression value set Y=y1,y2,y3,y4, cluster center set C=c1,c2, and parameter ν=0.5, the fuzzy granulation is as follows.
We take instancex1 as an example. The distances between x1 and the cluster centers c1 and c2 on the attributes a1, a2, and a3 are given as follows:sx1,a1,c1=1/1+exp−0.20−0.25=0.5125sx1,a1,c2=1/1+exp−0.20−0.15=0.5125sx1,a2,c1=1/1+exp−0.30−0.35=0.5125sx1,a2,c2=1/1+exp−0.30−0.45=0.5374sx1,a3,c1=1/1+exp−0.10−0.30=0.5498sx1,a3,c2=1/1+exp−0.10−0.60=0.6225
Equation (5) shows that fuzzy granules of x1 on a1, a2, and a3 are calculated as follows:q¯x1,a1=0.5125/c1+0.5125/c2q¯x1,a2=0.5125/c1+0.5374/c2q¯x1,a3=0.5498/c1+0.6225/c2
In the same way, fuzzy granules ofx2 on A are obtained as follows:q¯x2,a1=0.5125/c1+0.5374/c2q¯x2,a2=0.5374/c1+0.5622/c2q¯x2,a3=0.5250/c1+0.5987/c2
According toq¯x1,a1∪q¯x2,a1=∑j=1Ke+f−ef−1−νef/ν+1−ν1−ef/cj, here ν=0.5. When j=1, suppose that e=dx1,a1,c1 and f=dx2,a1,c1. When j=2, suppose that e=dx1,a1,c2 and f=dx2,a1,c2), we have(16)q¯x1,a1∪q¯x2,a1=∑j=12e+f−ef−1−νef/ν+1−ν1−efcj=0.5125+0.5125−0.5125∗0.5125−1−0.5∗0.5125∗0.5125/0.5+1−0.51−0.5125∗0.5125c1+0.5125+0.5374−0.5125∗0.5374−1−0.5∗0.5125∗0.5374/0.5+1−0.51−0.5125∗0.5374c2=0.7164c1+0.7385c2,q¯x1,a1∩q¯x2,a1=∑j=12ef/ν+1−νe+f−efcj=0.5125∗0.5125/0.5+1−0.50.5125+0.5125−0.5125∗0.5125c1+0.5125∗0.5374/0.5+1−0.50.5125+0.5374−0.5125∗0.5374c2=0.2981c1+0.3024c2,q¯x1,a1⊕q¯x2,a1=q¯x1,a1∪q¯x2,a1−q¯x1,a1∩q¯x2,a1=0.7164−0.2981c1+0.7385−0.3024c2=0.4183c1+0.4361c2,q¯x1,a1⊕q¯x2,a1=q¯x1,a1∪q¯x2,a1−q¯x1,a1∩q¯x2,a1=04183c1+0.4361c2=0.8544.
Similarly, we can get(17)q¯x1,a2⊕q¯x2,a2=0.4280c1+0.4253c2=0.8533,q¯x1,a3⊕q¯x2,a3=0.4269c1+0.4106c2=0.8375.
Thus, we can obtain the distance between fuzzy granular vectors ofx1 and x2 on A with ν=0.5 by(18)sQ¯x1,A,Q¯x2,A=1A∗C∑a∈Aq¯x1,a⊕q¯x2,aq¯x1,a∩q¯x2,a=0.8544+0.8533+0.83753∗2≈0.42.Table 1
Fuzzy granulation and metric.
X|C|AYνa1a2a3yνx10.200.300.100.300.50x20.300.200.200.200.50x30.400.200.300.500.50x40.100.100.400.400.50c10.250.350.30——c20.150.450.60——


## 4.3. Fuzzy Granular Regression Tree

After the above fuzzy granulation, the data can be transformed into fuzzy granules. In fuzzy granular space, we give the following definition.Definition 1.
Suppose thatS=T,A,C,Y is a regression system, where T=x1,y1,x2,y2,…,xn,yn is a instance set, xi is a input variable, and yi is output variable corresponding to xi. Let X=xi|i=1,2,…,n, and Y=yi|i=1,2,…,n. C=ci|i=1,2,…,K is a cluster center set and A=ai|i=1,2,…,m an attribute set. For ∀aj∈A,xi∈X, we can obtain fuzzy granule q¯xi,aj via fuzzy granulation (the following is abbreviated as q¯). Fuzzy granules and operators can create new fuzzy granules, such as g¯=w¯∩q¯∪h¯. Repeating this process can expand a fuzzy granular space G¯ on T. According to training data, a fuzzy granular rule base can be generated as(19)R=ri|ri=<Q¯xi,A,yi>,xi∈X,yi∈Y.
A fuzzy granular regression tree corresponds to a division of the fuzzy granular space and output value on the divided unit.
Suppose that the input space has been splitted intod units D1,D2,…,Dd, and there is a fixed output value zi on each unit Di. Thus, the fuzzy granular regression tree can be expressed as(20)fQ¯=∑i=1dziIQ¯∈Di.
Here,Q¯ is a fuzzy granular vector and I is an indicative function, which can be written as(21)I=1,ifQ¯∈Di,0,otherwise,zi=1Di∑Q¯j∈Diyj,where Di denotes the number of the fuzzy granular vector. The question becomes how to divide the fuzzy granular space.
Here, we use a heuristic method to select featureaj as the segmentation variable and the cardinal of fuzzy granule q¯xs,aj as the optimal segmentation point. Two areas are defined by(22)D1j,s=Q¯x,Aq¯x,aj|≤q¯xs,aj,D2j,s=Q¯x,Aq¯x,aj|>q¯xs,aj.
Then, find the optimal segmentation variableaj and point q¯xs,aj. Specifically, solve the loss function(23)minj,sminz1∑Q¯i∈D1j,syi−z12+minz2∑Q¯i∈D2j,syi−z22.
For input variableaj, the optimal segmentation point s can be calculated as(24)z^1=1D1j,s∑Q¯i∈D1j,syi,z^2=1D2j,s∑Q¯i∈D2j,syi,where ⋅ denotes the number of elements.
Traverse all input variables and find the optimal segmentation variablej to form a pair j,s. Divide the input space into two areas in turn. Then, repeat the above division process for each area until the terminal condition is met. In this way, a fuzzy granule regression tree is generated. The algorithm is described in Algorithm 2.Algorithm 2: Fuzzy granular regression tree.
Input: instance setX, regression value set YOutput: fuzzy granular treef(1)
Remove the instances missing some attribute values.(2)
Normalize each attribute value.(3)
Calculate the cluster center setC∗=c1,c2,…,cK (Algorithm 1).(4)
X1∪X2∪⋯∪Xp=X and ∀Xl,Xt∈X,Xl∩Xt=ϕ. // Parallel distributed fuzzy granulation.(5)
∀Xt⊂X//This is parallel process. Here, take Xt as example.FORi=1 to Xt∃xi∈XtFORj=1 to m∃a∈A, sample x is fuzzy granulated as q¯xi,a=∑j=1Ksxi,a,cj/cjEND FORBuild a fuzzy granular vectorQ¯x,A=∑j=1Aq¯x,aj/aj;Get label ofxi, yi;A fuzzy granular rule can be built.ri=<Q¯xi,A,yi>;END FOR(6)
Select the optimal segmentation variablej (i.e., the attribute aj) and segmentation point s (i.e., q¯xs,aj) by solving equation minj,sminz1∑Q¯i∈D1j,syi−z12+minz2∑Q¯i∈D2j,syi−z22That is, traverse variablej to find the pair j,s that minimizes the loss function by fixing the segmentation variable j and scanning segmentation point s.(7)
Divide the area with the selected pairj,s and decide output value as follows:z^1=1/D1j,s∑Q¯i∈D1j,syiz^2=1/D2j,s∑Q¯i∈D2j,syiD1j,s=Q¯x,A‖q¯x,aj|≤q¯xs,ajD2j,s=Q¯x,A‖q¯x,aj|>q¯xs,aj(8)
Continue to call Step 6 and Step 7 for the two subregions until the number of split nodes isA.(9)
Divide the input fuzzy granular space intod regions D1,D2,…,Dd and generate a fuzzy granular regression treefQ¯=∑i=1dz^iIQ¯∈Di


## 4.4. Boosted Fuzzy Granular Regression Trees

BFGRT can be an algorithm that integrates multiple fuzzy granular regression trees through the idea of ensemble learning to draw conclusions. It does not rely on only one fuzzy granular regression tree but adopts many fuzzy granular regression trees to solve the task together, using the weighted average of the regression values of multiple fuzzy granular regression trees as the final regression value. Assuming thatT is the instance set, fuzzy granular space is G¯, fuzzy granular rule base is R, the number of instances is n, and the number of attributes is m, we construct parallelly t fuzzy granular regression trees as follows: Step 1: createJmap tasksStep 2: instance set extraction: randomly drawn fuzzy granular vectors from R with replacement and repeat them n times. The probability of each fuzzy granular vector being selected is 1/n. The unselected fuzzy granular vectors form the out of bag data as the test set.Step 3: attribute extraction: extractt attributes from A to compose attribute subset BB⊂AStep 4: attribute selection: calculate the optimal segmentation attributeaj and the optimal segmentation point q¯xs,aj in the data set of node, divide the node into two child nodes, and allocate the remaining fuzzy granular vectors to the child nodesStep 5: generate a fuzzy granular tree. Repeat Step 3 in the fuzzy granular vector set of each child node to recursively split the nodes until all leaf nodes are generated.Step 6: repeat steps 2–5 to getJ different fuzzy granular regression trees, which correspond to JMap tasksStep 7: BFGRT can consist ofJ fuzzy granular regression trees and the process can be executed by reduce task, that is,(25)FQ¯=∑j=1Jωj⋅fjQ¯,Whereωj=1−expδj/∑i=1Jexpδi, and δj represents the root mean square error (RMSE) of jth fuzzy granular tree. This detail of the algorithm can be illustrated in Algorithm 3.Algorithm 3: Boosted fuzzy granular regression trees.
Input: instance setX, regression value set Y, the number of fuzzy granular regression tree JOutput: boosted fuzzy granular regression treesF(1)
Get a fuzzy granular vector rule baseR by parallel fuzzy granulation of the dataset (see Algorithm 2, Algorithm 4, and Algorithm 5.)(2)
CreateJ tasks, namely, map1,map2,…,mapJ(3)
Execute the following operations for each independent task (j=1,2,…,J):MapFunction(key, value), where key = offset of instance andvalue=n,t indicates that n fuzzy granular vectors are randomly//selected fromR.//Randomly selectt attributes from the attribute set A (constitutes attribute subset Bjt, that is, Bjt⊂A)//Form a fuzzy granular rule setRj, build a fuzzy granular regression tree fj, and get its RMSEδj=1/n∑i=1nz^i−yi2, where z^i=fjQ¯xi,Bjt,yi∈Rj.(4)
FORi=1 to instances-total-number(5)
SubsetID =i mod J(6)
context.write(SubsetID, FuzzyGranularVector)(7)
END FOREND MapFunction(8)
ReduceFunction(key, value)//Here, key = SubsetID, value = FuzzyGranualrVector(9)
Job.addCache(FuzzyGranularVector[SubsetID])(10)
fSubsetID,δSubsetID = train(SubsetID, FuzzyGranularVector)//(See Step 6–Step 9 of Algorithm 2.)(11)
context.write(1,(fSubsetID,δSubsetID))END ReduceFunction(12)
F⋅=∑j=1Jωj⋅fj⋅//Calculate BFGRT F composed of the linear combination of J fuzzy granular regression trees.Whereωj=1−expδj/∑i=1Jexpδi.Algorithm 4: Map function of parallel fuzzy granulation.
Input: <offset, instance> andt (the number of divided instance sets)Output: <SubsetID, instance>(1)
FORi=1 to instances-total-number(2)
SubsetID =i mod t(3)
context.write(SubsetID, instance)(4)
END FORAlgorithm 5: Reduce function of parallel fuzzy granulation.
Input: SubSetID, ClusterSet C, and instance subset X[SubSetID]Output: Fuzzy Granular Set(1)
Job.addCache(X[SubSetID])(2)
FuzzyGranularSubSetSubSetID = Granulation(X[SubSetID],C)//See Step 5 of Algorithm 2.(3)
FuzzyGranularSet = context.write(1FuzzyGranularSubsetSubSetID)


## 4.5. Regression

Given a test instance, we fuzzy granulate the test instance to get a fuzzy granular vector. Then, use BFGRT to predict the fuzzy granular vector to achieve the regression value. Algorithm6 demonstrates the algorithm.Algorithm 6: The algorithm of prediction.
Input: test instancex, cluster center set C, BFGRT F=f1,f2,…,fJ;ω1,ω2,…,ωJ.Output: regression valuey^∗ of instance x(1)
Granulatex to fuzzy granular vector Q¯x,A(2)
Forj=1 to Jy^j=fjQ¯x,Aj, where according to the parameters of fj, attribute set selected satisfies Aj⊂Aj=j+1End For(3)
FQx,A=∑j=1Jωj⋅y^j(4)
y^∗=FQx,A(5)
Returny^∗


## 5. Experimental Analysis

In this experiment, the results presented are generated on the server of 2∗Intel Xeon Gold6248R@2.50 GHz with 64 GB memory. Datasets include 3 datasets gathered from the UC Irvine Machine Learning Repository and 3 datasets with 1% noise constructed (Table2), and 10-fold cross-validation which belongs to sampling without replacement was adopted to test the performance of BFGRT, as illustrated in Algorithm 3. The basic idea of 10-fold cross-validation is to partition the dataset into nonoverlapping L equal parts. In the training process, one part of dataset is selected to verify the generalization ability of the learner, and the remaining L−1 parts are used as a training learner. After training L times, L learners can be obtained. This method is very similar to the bagging method and also supports parallel learning. Root mean square error (RMSE) and execution time are the metrics of the performance. We compared classic fuzzy granulation with parallel fuzzy granulation proposed in Figure 2 and analyzed the performance of support vector regression (SVR), random forest (RF), long short-term memory (LSTM), and BFGRT proposed in Figures 3–5 . We also gave the relation between the number of cluster centers and RMSE.Table 2
Datasets from the UC Irvine Machine Learning Repository.
DatasetNumber of instanceNumber of attributesRegression attributeBias correction of numerical prediction model temperature forecast775025Next_TminBias correction of numerical prediction model temperature forecast with noise775025Next_TminCombined cycle power plant95684EPCombined cycle power plant with noise95684EPMetro interstate traffic volume482049Traffic volumeMetro interstate traffic volume with noise482049Traffic volumeClickstream data for online shopping16547414PriceClickstream data for online shopping with noise16547414PriceFigure 2
Comparison of executing time.Figure 3
Comparison of dataset (a) combined cycle power plant and (b) combined cycle power plant with noise of 1%.
(a)(b)Figure 4
Comparison of dataset (a) bias correction of numerical prediction model temperature forecast and (b) bias correction of numerical prediction model temperature forecast with noise of 1%.
(a)(b)Figure 5
Comparison of dataset (a) metro interstate traffic volume and (b) metro interstate traffic volume with noise of 1%.
(a)(b)Fuzzy granulation of data is an important process of modeling. Some traditional fuzzy granulation methods do not require clustering, of which idea is to construct a matrix using the similarity of each sample to other samples. This kind of thinking does not have the conditions for parallel execution and can only be executed serially, and its time complexity isOn2∗m, where n is the number of instances and m is the number of attributes. Parallel fuzzy granulation proposed is executed as follows. First, we obtain cluster centers by the clustering algorithm designed in the study. Next, we need to construct fuzzy granules through each instance and each cluster center. This process can be executed parallelly by MapReduce. The time complexity is On∗k∗m/t, where k denotes the number of cluster centers k<n, and t represents the number of parallel tasks. Theoretically, the efficiency of BFGRT is nt/k−1∗100% (k<n) higher than that of traditional fuzzy granulation.MapReduce can be used for parallel fuzzy granulation. The main thought is as follows: partition the sequence file job into multiple independently runnable map tasks, assign them to several processors to execute, produce intermediate results, and then collect the reduce task operations to generate the final output. Map tasks and reduce tasks can be both parallelly executed. The MapReduce process is divided into two parts, i.e., map and reduce. Map function and reduce function of the fuzzy granulation process are shown in Algorithm4 and Algorithm 5, respectively. The results of parallel granulation are demonstrated in Table 3. As demonstrated in Figure 2, when the number of parallel tasks is 3, parallel fuzzy granulation performs better than classic fuzzy granulation by about 252%, 647%, and 438% regarding the metrics, minimum efficiency, maximum efficiency, and average efficiency, respectively.Table 3
Parallel fuzzy granulation output.
KeyValueIDx1Ga1x1,Ga2x1,…,Gamx1IDx2Ga1x2,Ga2x2,…,Gamx2……IDxnGa1xn,Ga2xn,…,GamxnAs shown in Figure3(a), tested on dataset combined cycle power plant, BFGRT show a shape that is low in the middle and high on both sides. When the number of cluster centers is between 3000 and 6000, the RMSE of BFGRT is lower than the other three methods. When the number of cluster centers is within 3000, the RMSE of BFGRT drops quickly, and the slope of the curve drops significantly. When the number of cluster centers is higher than 5000, the curve of BFGRT shows a small local oscillation, which is lower than the other three methods. In particular, when the number of cluster centers is 3986, the RMSE of BFGRT achieves the minimum value of 3.1151, which is about 46.88%, 4.22%, and 32.85% better than SVR, RF, and LSTM, respectively. BFGRT is slightly better than RF and far better than SVR and LSTM. When the number of cluster centers is 1006, the RMSE of BFGRT reaches the maximum value of 3.4681, which is about 24.20% and 25.24% better than RF and LSTM, respectively, and is about 6.64% worse than RF. On average, the RMSE of BFGRT is 3.2441, which is better than 4.5753 of SVR, 3.2522 of RF, and 4.6389 of LSTM (i.e., 29.10%, 0.25%, and 30.07% improvement, respectively).After we added 1% noise to the dataset, as illustrated in Figure3(b), the curve of BFGRT resembles an inverted “Mexican straw hat.” When the number of cluster centers is 3986, the RMSE of BFGRT gets the minimum value of 3.3151, while that of SVR, RF, and LSTM are 4.8946, 3.5322, and 4.9289 (i.e., 32.27%, 6.15%, and 32.74% improvement, respectively). When the number of cluster centers is 9360, BFGRT obtain the maximum value of 3.5651, which improves the performance by about 27.16% and 27.67% compared with SVR and LSTM, respectively, and is about 0.93% worse than RF. On average, the RMSE of BFGRT is 3.4300, which performs about 29.92%, 2.89%, and 30.41% better than SVR, RF, and LSTM, respectively. In terms of the degree of noise influence, the RMSE of SVR, RF, LSTM, and BFGRT on the noisy dataset increases by about 6.98%, 8.61%, 6.25%, and 5.73%, respectively. BFGRT is less affected by noise and more robust than the other three algorithms.As demonstrated in Figure4(a), in the dataset bias correction of numerical prediction model temperature forecast, there are 7750 instances and 25 features. The shape of RMSE of BFGRT can be roughly divided into two segments with the number of cluster centers of 4000 as the cutting point. The part of less than 4000 is a descending curve and that of greater than 4000 is an ascending one. When the number of cluster centers gets 4021, the minimum value of RMSE of BFGRT is 0.7013, while SVR, RF, and LSTM just get 0.9129, 0.7292, and 0.9734 (that is, 23.18%, 3.83%, and 27.95% improvement, respectively). When the number of cluster centers is 1592, RMSE of BFGRT reach the maximum value of 0.7387, which is about 1.30% more than RF and 19.08% and 24.11% less than SVR and LSTM, respectively. The average RMSE of BFGRT is 0.7189, which is better than 21.25%, 1.42%, and 26.15% than SVR, RF, and LSTM, respectively.The performance on a noisy dataset is shown in Figure4(b). The RMSE of BFGRT is lower than the other three algorithms. The RMSE of BFGRT has a minimum value of 0.9016, a maximum value of 0.9397, and an average value of 0.9221. By contrast, the RMSE of SVR, RF, and LSTM is 1.2143, 1.0297, and 1.2745, respectively. The mean value of the RMSE of BFGRT is about 24.07%, 10.45%, and 27.65% better than SVR, RF, and LSTM, respectively. The performance of the algorithms analyzed in the dataset containing noise is as follows: SVR, RF, LSTM, and BFGRT have increased by 33.02%, 41.21%, 30.93%, and 27.48%, respectively. It can be seen that BFGRT can be less sensitive to noise than the other three algorithms.The number of instances in dataset metro interstate traffic volume is more than 4 times that of datasets mentioned above. As illustrated in Figure5(a), the maximum value of RMSE of BFGRT is 2259.1858, while that of SVR is 3050.0148 and that of RF is 2435.1646 (i.e., 25.93% and 7.23% improvement, respectively). Compared with LSTM, BFGRT decrease by about 2.27%. The minimum value of RMSE of BFGRT is 2154.1888, which performs 29.37%, 11.54%, and 2.49% better than SVR, RF, and LSTM, respectively. The mean value of RMSE of BFGRT is 2202.8738, which is 27.77%, 9.54%, and 0.28% better than SVR, RF, and LSTM, respectively. From the dataset containing 1% noise, as shown in Figure5(b), BFGRT improve the performance by about 29.08%, 11.20%, and 1.86% than SVR, RF, and LSTM, respectively. SVR, RF, LSTM, and BFGRT have increased by 2.04%, 2.07%, 2.10%, and 0.20% (the mean value of RMSE) on the noisy dataset, respectively. Compared with the other three algorithms, BFGRT is the algorithm least affected by noise.The number of instances in dataset online shopping is more than 160000. As shown in Figure6(a), the maximum value of RMSE of BFGRT is 1.88, while that of SVR is 2.12, that of RF is 2.03, and that of LSTM is 1.89 (i.e., 11.32%, 7.39%, and 0.53% improvement, respectively). From the dataset containing 1% noise, as shown in Figure 6(b), the maximum value of RMSE of BFGRT is 1.94, which has improved by about 16.01%, 9.77%, and 0.51%, respectively, compared with SVR, RF, and LSTM.Figure 6
Comparison of (a) clickstream data for online shopping and (b) clickstream data for online shopping with noise of 1%.
(a)(b)From the above analysis, it can be seen that BFGRT outperforms SVR, RF, and LSTM in the six datasets. In particular, it is stable on the three datasets with noise and is less disturbed by noise. Judging from the shape of the RMSE of BFGRT, it presents a form of low middle and high sides. When the number of cluster centers is close to the median of the number of instances, the performance can be optimal. For datasets that contain noise, we also found that BFGRT has the better robustness. The main reason is that BFGRT contains global comparison ideas in the fuzzy granulation process, which can overcome the noisy interference to some extent. This is also a great advantage of BFGRT designed.


## 6. Conclusion

In this study, we propose BFGRT suitable for the regression problem. In the algorithm, the idea of parallel fuzzy granulation is introduced to further improve the efficiency of data granulation. In the process of parallel fuzzy granulation, we design a clustering algorithm with automatic optimization of cluster centers. Through parallel fuzzy granulation, a regression problem can be solved in the fuzzy granular space where we present new operators and metrics between fuzzy granules. In the fuzzy granular space, we design a loss function to select optimal attribute as split point and construct recursively a fuzzy granular regression tree. Based on these, we build multiple fuzzy granular regression trees according to different attributes to form BFGRT to predict a test instance. In the future, BFGRT can be combined with cloud computing and thing of Internet to process the big data.



---

*Source: 9958427-2021-07-22.xml*