# Reinforcement Learning-Based Genetic Algorithm in Optimizing Multidimensional Data Discretization Scheme

Authors: Qiong Chen; Mengxing Huang; Qiannan Xu; Hao Wang; Jinghui Wang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Feature discretization can reduce the complexity of data and improve the efficiency of data mining and machine learning. However, in the process of multidimensional data discretization, limited by the complex correlation among features and the performance bottleneck of traditional discretization criteria, the schemes obtained by most algorithms are not optimal in specific application scenarios and can even fail to meet the accuracy requirements of the system. Although some swarm intelligence algorithms can achieve better results, it is difficult to formulate appropriate strategies without prior knowledge, which will make the search in multidimensional space inefficient, consume many computing resources, and easily fall into local optima. To solve these problems, this paper proposes a genetic algorithm based on reinforcement learning to optimize the discretization scheme of multidimensional data. We use rough sets to construct the individual fitness function, and we design the control function to dynamically adjust population diversity. In addition, we introduce a reinforcement learning mechanism to crossover and mutation to determine the crossover fragments and mutation points of the discretization scheme to be optimized. We conduct simulation experiments on Landsat 8 and Gaofen-2 images, and we compare our method to the traditional genetic algorithm and state-of-the-art discretization methods. Experimental results show that the proposed optimization method can further reduce the number of intervals and simplify the multidimensional dataset without decreasing the data consistency and classification accuracy of discretization.


---

## Body

## 1. Introduction

The rapid development of the internet of things has produced massive amounts of large-scale data [1–5]. These are mainly from various types of sensors, with high-dimensional, incomplete, random, fuzzy, and strong interference and other characteristics [6]. Despite the growing body of artificial intelligence research, how to extract and analyze valuable information from these massive amounts of complex sensor data is still a huge challenge in the field of artificial intelligence [7–9]. As one of the most influential data preprocessing technologies, feature discretization can reduce the complexity of data by transforming the continuous features in massive data to discrete features and obtain shorter, more accurate, and more comprehensible rules, so as to improve the efficiency of data mining and machine learning [10–16]. Therefore, feature discretization plays a key role in the application of artificial intelligence technology to these data.With the development of artificial intelligence, more and more scholars are studying feature discretization [17–19]. Obtaining the optimal discretization scheme has been proved to be an NP complete problem [20]. The choice of a discretization method for a dataset will restrict the performance and accuracy of a posterior learning task. Discretization technology can be classified as either supervised or unsupervised, according to whether the data contain category information [21].EqualWidth and EqualFrequency are two commonly used unsupervised discretization methods [22]. They divide the entire attribute according to a given interval length and frequency. Although they are simple and convenient, they lead to uneven data distribution and loss of some important information. Supervised discretization has the advantage of making full use of the class label and target attribute information, and it facilitates finding the appropriate breakpoint position compared to unsupervised discretization.1R is the simplest supervised discretization algorithm [23]. It uses a greedy strategy to divide the attribute value range into intervals, each corresponding only to a decision class. However, because the partition standard of the interval is too simple, lacks flexibility, and does not consider the correlation between features, it cannot guarantee that the compatibility of an information system after discretization will not be destroyed.The information entropy-based method is based on the minimum length description principle (MDLP), and it uses the measure of information gain to determine the breakpoint [24]. Although it can largely ensure the consistency of samples in the interval, it is difficult to filter the noise by setting the threshold value of the partition.ChiMerge [25], Chi2 [26], and Extended Chi2 [27] discriminate and merge adjacent intervals by measuring the degree of association between condition attributes and target attributes. They have the advantage that the structures of adjacent intervals are distinct, but they are sensitive to parameters.CADD [28], CAIM [29], and CACC [30] use statistics to quantify class attribute correlation, which they can maximize after discretization, and they can obtain the minimum number of discrete intervals as much as possible. However, they only achieve the best discretization for a single attribute interval, lack the description of all of the data, do not consider the consistency of the data either before or after discretization, and will inevitably lose important information from the original data.These mainstream methods are obviously based on specific division criteria to achieve the discretization of continuous features. However, in the process of multidimensional data discretization, the distribution of target attribute values is usually difficult to know, and the features have complex correlations. In addition, the relatively fixed division criteria cannot provide a comprehensive measure of discrete intervals, and there will be some defects. Therefore, the discretization schemes obtained by most of the algorithms are not optimal in specific application scenarios, or they may even fail to meet the accuracy requirements of the system. A PSO algorithm was applied to feature selection based on discretization, which can generate more powerful and compact representations in high-dimensional datasets, and thus achieve better classification performance [31]. ACO [32] is used to solve the problem of discretization of continuous features to obtain more concise decision rules and higher prediction accuracy. RS-GA is a mature discretization method, which uses the individual fitness function based on rough sets to evaluate the uncertainty of an information system in a genetic algorithm and searches for the optimal discretization scheme through individual evolution [33]. Although these swarm intelligence algorithms can achieve better results, it is difficult to formulate appropriate strategies without prior knowledge, which will make the search in multidimensional space inefficient, consume computing resources, and easily fall into local optima.Aiming at these problems, this paper proposes a reinforcement learning-based genetic algorithm (RLGA) to optimize the discretization scheme of multidimensional data. First, we binary code the attribute values of the multidimensional data and initialize the population. The binary code method can build an efficient mathematical model suitable for the problem of feature discretization. Second, it is difficult to form a proper strategy without prior knowledge as guidance, which causes the search space to easily fall into local optima. We use rough sets [34] to construct individual fitness functions and a design control function to dynamically adjust the diversity of the population. Then, we introduce a reinforcement learning mechanism [35] to crossover and mutation to determine the crossover fragments and mutation points of the discretization scheme to be optimized. We compare our method to state-of-the-art discretization methods on GF-2 and Landsat 8 images. Experimental results show that the proposed method can reduce the number of intervals and simplify the multidimensional dataset without decreasing the data consistency and classification accuracy of a discretization scheme.The remainder of this paper is arranged as follows. Section2 describes basic concepts and reviews some related work. Section 3 explains the algorithm flow of the proposed work. Section 4 introduces the experimental environment and datasets. We analyze and discuss the experimental results in Section 5. Section 6 summarizes this paper and discusses future research.


## 2. Background and Related Work

We introduce the concept of feature discretization and present simple descriptions of rough sets, genetic algorithms, and reinforcement learning mechanisms. We also analyze problems that occur in the discretization of multidimensional data in the optimization process.


### 2.1. Definitions of Feature Discretization

Feature discretization is the process of dividing a continuous attribute value (also called a continuous feature value) into a finite number of intervals according to a rule, and associating these intervals with a set of discrete values [10]. Considering the problem of m-dimensional data classification, the discretization algorithm divides the attribute values on the i-th dimension into ni discrete, nonintersecting intervals:(1)Di=d0,d1,d1,d2,…,dni−1,dni,where d0 and dni are the minimum and maximum attribute values. All of the values are arranged in ascending order in Di, which is called a discretization scheme on the ith dimension. D=D1,D2,…,Di,…,Dm represents the whole discretization scheme of m-dimensional data. Obviously, the search space of m-dimensional data feature discretization is formed by all of the candidate breakpoints of each dimension, which are different attribute values of each dimension in the training set.


### 2.2. Genetic Algorithm Using Binary Coding

As a global optimization probability evolution algorithm, a genetic algorithm [36] has inherent implicit parallelism and a strong global search ability. It achieves good performance on many optimization problems [37]. We use binary encoding to encode the candidate breakpoint; the values 1 and 0 represent that the breakpoint is selected or discarded, respectively. Assuming that BPi=bpi1,bpi2,…,bpinii=1,2,…,m is a candidate breakpoint set of m-dimensional data in the ith dimension, the chromosome structure in the genetic algorithm is shown in Figure 1, where colors represent different features in the m-dimensional data. The length of each chromosome is ∑i=1mni. The set of selected candidate breakpoints is a discretization scheme, according to which attribute values are classified into discrete intervals formed by the candidate breakpoints in the set.Figure 1
Chromosome structure.


### 2.3. Fitness Function Based on Rough Set

A rough set [38] is based on the classification mechanism. It interprets the classification as indiscernible relations in the space of features, and these relations form the division of the space. Given decision table S=U,R,V,f, where U is a finite set of objects, i.e., a domain, R is an attribute set including condition attribute set C and decision attribute set D. For each attribute subset A⊆R, the indiscernible binary relation INDA and the equivalent classes of attribute subset A in domain U are defined as(2)INDA=x,yx,y∈U2,∀a∈Aax=ay,U|INDA=XX⊆U∧∀x∈X∀y∈X∀a∈Aax=ay.According to the abovementioned decision tableS, for each subset AinU and equivalent class of attribute subset X in U, the lower and upper approximation sets of X are defined as(3)A_X=∪YY∈UINDA∧Y⊆X,(4)A−X=∪YY∈UINDA∧Y∩X≠Ø.Since the principle of selecting the optimal breakpoint set is to minimize the number of breakpoints without changing the indiscernible relations of the decision table, the fitness function should be determined by the number of breakpoints and the indiscernible relations:(5)FitnessD=NI−NDNI×RD,where NI is the number of breakpoints in the initial breakpoint set, ND is the number of breakpoints obtained after chromosome decoding, and ΔN=NI−ND is the change of the number of breakpoints. RD takes the value 0 or 1, which, respectively, mean that the indiscernibility of the decision table changes or does not change after discretization. The judgment process is shown in Algorithm 1.Algorithm 1:Indiscernible relationship change judgement.
Input: Discretization scheme, original decision table
Output: Indiscernible relationship change
initialize: RD = 1;
begin
for each category ido
Compute the lower approximation setC−(di) of the original decision table before discretization using equation (3);
Compute the upper approximation set C−(di) of the original decision table before discretization using equation (4);
end
Discrete the original decision table by the discretization scheme;
for each category ido
Compute the lower approximation setC−(di)′ of the original decision table after discretization using equation (3);
Compute the upper approximation setC−(di)′ of the original decision table after discretization using equation (4);
end
for each category ido
ifC−(di)′ ≠ C−(di) or C−(di)′ ≠ C−(di) do
RD = 0;
break;
end
end
ReturnRD;
end


### 2.4. Reinforcement Learning

Reinforcement learning is a goal-driven, highly adaptive machine learning technique in the field of artificial intelligence [39], in which there are two basic elements: state and action. Performing an action in a certain state is a strategy. The learner must constantly explore to generate an optimal strategy. Different from supervised and unsupervised learning, it regards learning as a process of interaction between agents and the environment through exploration and evaluation. The operation mechanism is shown in Figure 2. The agent selects an action to be applied to the environment by sensing the current state of the environment. After the environment accepts the action, the state changes, and a reward is given to the agent. According to the new state of the environment, the agent continues to select the next action, and this is repeated until it reaches the terminated state. The goal of reinforcement learning is to maximize the accumulated rewards by adjusting strategies.Figure 2
Operation mechanism of reinforcement learning.Q-learning [40] is one of the most representative model-free reinforcement learning techniques. In the current state, the agent selects the next action according to the corresponding Q value of each action using the ε−greedy strategy and updates Q at each step in the learning process as(6)Qs,a=Rs,a+γ⋅maxa′∈AQs′,a′,where s and a are, respectively, the current state and behavior, s′,a′, and A are the next state and behavior, A is the action set, and 0≤γ≤1. Q-learning has broad application prospects in solving complex control and decision-making problems [41, 42]. We use Q-learning to determine the cross fragments and mutation points of the discretization scheme to be optimized.


### 2.5. Main Challenges

The complexity of multidimensional data feature discretization increases sharply with the length of the attribute value interval and the association between attributes [36]. When using the genetic algorithm [43] to optimize the discretization scheme of multidimensional data, the main challenges are as follows.(1)
Improper control of population diversity causes premature convergence.(2)
Because multidimensional data contain many features, cross fragments and mutation points tend to focus on features with larger value intervals, which decrease the opportunity for breakpoints on other features to evolve.(3)
Due to the complex correlations between features, the crossover and mutation operations are relatively blind without prior knowledge as guidance, making it highly likely that some high-quality fragments on features are destroyed in the next generation of evolutionary operations.


## 2.1. Definitions of Feature Discretization

Feature discretization is the process of dividing a continuous attribute value (also called a continuous feature value) into a finite number of intervals according to a rule, and associating these intervals with a set of discrete values [10]. Considering the problem of m-dimensional data classification, the discretization algorithm divides the attribute values on the i-th dimension into ni discrete, nonintersecting intervals:(1)Di=d0,d1,d1,d2,…,dni−1,dni,where d0 and dni are the minimum and maximum attribute values. All of the values are arranged in ascending order in Di, which is called a discretization scheme on the ith dimension. D=D1,D2,…,Di,…,Dm represents the whole discretization scheme of m-dimensional data. Obviously, the search space of m-dimensional data feature discretization is formed by all of the candidate breakpoints of each dimension, which are different attribute values of each dimension in the training set.


## 2.2. Genetic Algorithm Using Binary Coding

As a global optimization probability evolution algorithm, a genetic algorithm [36] has inherent implicit parallelism and a strong global search ability. It achieves good performance on many optimization problems [37]. We use binary encoding to encode the candidate breakpoint; the values 1 and 0 represent that the breakpoint is selected or discarded, respectively. Assuming that BPi=bpi1,bpi2,…,bpinii=1,2,…,m is a candidate breakpoint set of m-dimensional data in the ith dimension, the chromosome structure in the genetic algorithm is shown in Figure 1, where colors represent different features in the m-dimensional data. The length of each chromosome is ∑i=1mni. The set of selected candidate breakpoints is a discretization scheme, according to which attribute values are classified into discrete intervals formed by the candidate breakpoints in the set.Figure 1
Chromosome structure.


## 2.3. Fitness Function Based on Rough Set

A rough set [38] is based on the classification mechanism. It interprets the classification as indiscernible relations in the space of features, and these relations form the division of the space. Given decision table S=U,R,V,f, where U is a finite set of objects, i.e., a domain, R is an attribute set including condition attribute set C and decision attribute set D. For each attribute subset A⊆R, the indiscernible binary relation INDA and the equivalent classes of attribute subset A in domain U are defined as(2)INDA=x,yx,y∈U2,∀a∈Aax=ay,U|INDA=XX⊆U∧∀x∈X∀y∈X∀a∈Aax=ay.According to the abovementioned decision tableS, for each subset AinU and equivalent class of attribute subset X in U, the lower and upper approximation sets of X are defined as(3)A_X=∪YY∈UINDA∧Y⊆X,(4)A−X=∪YY∈UINDA∧Y∩X≠Ø.Since the principle of selecting the optimal breakpoint set is to minimize the number of breakpoints without changing the indiscernible relations of the decision table, the fitness function should be determined by the number of breakpoints and the indiscernible relations:(5)FitnessD=NI−NDNI×RD,where NI is the number of breakpoints in the initial breakpoint set, ND is the number of breakpoints obtained after chromosome decoding, and ΔN=NI−ND is the change of the number of breakpoints. RD takes the value 0 or 1, which, respectively, mean that the indiscernibility of the decision table changes or does not change after discretization. The judgment process is shown in Algorithm 1.Algorithm 1:Indiscernible relationship change judgement.
Input: Discretization scheme, original decision table
Output: Indiscernible relationship change
initialize: RD = 1;
begin
for each category ido
Compute the lower approximation setC−(di) of the original decision table before discretization using equation (3);
Compute the upper approximation set C−(di) of the original decision table before discretization using equation (4);
end
Discrete the original decision table by the discretization scheme;
for each category ido
Compute the lower approximation setC−(di)′ of the original decision table after discretization using equation (3);
Compute the upper approximation setC−(di)′ of the original decision table after discretization using equation (4);
end
for each category ido
ifC−(di)′ ≠ C−(di) or C−(di)′ ≠ C−(di) do
RD = 0;
break;
end
end
ReturnRD;
end


## 2.4. Reinforcement Learning

Reinforcement learning is a goal-driven, highly adaptive machine learning technique in the field of artificial intelligence [39], in which there are two basic elements: state and action. Performing an action in a certain state is a strategy. The learner must constantly explore to generate an optimal strategy. Different from supervised and unsupervised learning, it regards learning as a process of interaction between agents and the environment through exploration and evaluation. The operation mechanism is shown in Figure 2. The agent selects an action to be applied to the environment by sensing the current state of the environment. After the environment accepts the action, the state changes, and a reward is given to the agent. According to the new state of the environment, the agent continues to select the next action, and this is repeated until it reaches the terminated state. The goal of reinforcement learning is to maximize the accumulated rewards by adjusting strategies.Figure 2
Operation mechanism of reinforcement learning.Q-learning [40] is one of the most representative model-free reinforcement learning techniques. In the current state, the agent selects the next action according to the corresponding Q value of each action using the ε−greedy strategy and updates Q at each step in the learning process as(6)Qs,a=Rs,a+γ⋅maxa′∈AQs′,a′,where s and a are, respectively, the current state and behavior, s′,a′, and A are the next state and behavior, A is the action set, and 0≤γ≤1. Q-learning has broad application prospects in solving complex control and decision-making problems [41, 42]. We use Q-learning to determine the cross fragments and mutation points of the discretization scheme to be optimized.


## 2.5. Main Challenges

The complexity of multidimensional data feature discretization increases sharply with the length of the attribute value interval and the association between attributes [36]. When using the genetic algorithm [43] to optimize the discretization scheme of multidimensional data, the main challenges are as follows.(1)
Improper control of population diversity causes premature convergence.(2)
Because multidimensional data contain many features, cross fragments and mutation points tend to focus on features with larger value intervals, which decrease the opportunity for breakpoints on other features to evolve.(3)
Due to the complex correlations between features, the crossover and mutation operations are relatively blind without prior knowledge as guidance, making it highly likely that some high-quality fragments on features are destroyed in the next generation of evolutionary operations.


## 3. Reinforcement Learning-Based Genetic Algorithm

A genetic algorithm is a general method to search for the optimal solution in the field of artificial intelligence. We add a control function to the fitness function based on rough sets to dynamically adjust the diversity of the population. In addition, according to the characteristics of multidimensional data, we introduce a reinforcement learning mechanism to the crossover and mutation operation to determine the cross fragments and mutation points of the discretization scheme to be optimized, which greatly improves the accuracy and speed of convergence. Below, we discuss the flow of the algorithm.


### 3.1. Evolution of Discretization Scheme to Be Optimized

We perform evolutionary operations on the optimized discretization scheme and initial population, as shown in Figure3. The global variable preserves the best individual of the population, while the local variable preserves the historical best individual of the discretization scheme to be optimized. In each iteration, the fitness of the current population is calculated, the optimal individual is obtained, and the global variable is updated. Then, the discretization scheme to be optimized and the optimal individual of the population carry out the cross and mutation operations based on reinforcement learning, and the local variable is updated. If the termination condition is not reached, then the population will continue to carry out ordinary evolutionary operations. Otherwise, by comparing the global variable and local variable, the individual with the largest fitness will be output.Figure 3
Evolution of the discretization scheme to be optimized.


### 3.2. Selection Operator Based on the Control Function

The selection operation is based on the evaluation of individual fitness in the population. Individuals with higher fitness are generally more likely to be selected. Roulette [44] is a simple, efficient, probability-based method that is often used to select individuals. If the population size is n and the fitness value of individual i is fi, then the probability that individual i is selected is(7)Pi=fi∑j=1nfj.However, individuals with large fitness are more likely to be selected, which may result in the destruction of population diversity. SinceRD takes the value 0 or 1, individuals with fitness value 0 cannot be selected in the evolution of the population. Although these individuals are not feasible solutions at the initial stage, they may be close to the optimal feasible solution, and may eventually evolve into it. However, considering the randomness and evenness of the initial population, feasible solutions with RD = 1 and potential feasible solutions with RD = 0 tend to be quantitatively equivalent. Even with a small population, because of the complex correlation among the features of multidimensional data, there are far more potential feasible solutions with RD = 0 than with RD = 1. Therefore, when roulette is used for individual selection, the potential feasible solutions that are the majority of the population will be eliminated, thus destroying the diversity of the population. According to the abovementioned analysis, to ensure the diversity of the population in the early stage and accelerate convergence of individuals to the optimal solution in the late stage of evolution, we expand the fitness function by adding the control function on the original basis, and we determine the control factors according to the proportion of feasible solutions in the population in the current stage of evolution. The fitness function of chromosome x is thus expanded to(8)Fitness′x=NI−NDxNI×RDx+σp×φx.The control function consists of control itemφx and control factor σp, where σp is the proportion of the population consisting of potential feasible solutions with RD = 0, and σp is a function with p as an independent variable. The expressions for φx and σp are(9)φx=NI−NDxNIz,σp=0,μ=1,μ1−p,0<μ<1,12k×log2NI1−p,μ=0,μ=∑i=1ksetcmpC−di′,C−di+setcmpC−di',C−di2k,where NI is the number of breakpoints in the initial breakpoint set, NDx is the number of breakpoints obtained after chromosome x decoding, RDx is the change of the indiscernible relationship of the decision table after discretization by chromosome x, k is the number of classes, di is the ith class, C_di and C−di are, respectively, the lower and upper approximation sets of di before discretization, C_di′ and C−di are, respectively, the lower and upper approximation sets of di after discretization, and setcmpsetA,setB is a user-defined set comparison function. When setA and setB are equal, the function value is 1, and otherwise it is 0. Since each class corresponds to a lower and upper approximation set, the value range of μ is 0≤μ≤1. The following points are made regarding the extended fitness function.(1)
We want to prevent the unreasonable situation that when the number of breakpoints of the feasible solution withRD=1 is equal to that of the potential feasible solution with RD=0, the fitness value of the former is less than or equal to that of the latter. Hence we require that index z of the control item satisfies z>1. In this paper, z=2.(2)
It can be seen that the value range ofμ is actually 2K+1 discrete points from 0 to 1, with the interval 1/2k. When μ=0, the indiscernibility of the decision table is destroyed after discretization. If μ=0, then μ = 0, and the significance of adding a control function for potential feasible solutions with RD=0 is lost, since the control function has a smaller value than when μ takes the minimum nonnegative value μ=1/2K. Consequently, we change the expression μ1−p to 1/2k×log2N11−p. So, when μ=0, the value of the control function is not 0, and it is smaller than its value with μ=1/2k. However, because the chromosome is binary coded, taking “2” as the base number and N1 as the true number can ensure that the difference between the two control function values corresponding to μ=0 and μ=1/2k is not too large, and this controls the selection of individuals relatively reasonably.(3)
Whenμ=1, RD=1 and σp=0, indicating that this individual is a feasible solution, and the value of the control item is 0. When 0≤μ<1, 0≤μ<1 and σp is an increasing function with p as the independent variable. Consider that in the early stage of evolution, there are few or no feasible solutions in the population, i.e., p is large. At this time, σp should be relatively large, so the potential feasible solution can be selected with a large probability in roulette, and the search is gradually guided to the area of feasible solutions. As evolution progresses, more and more feasible solutions appear in the population, i.e., p becomes smaller and smaller. Accordingly, σp should become smaller and smaller, accelerating the movement from feasible to optimal solutions.


### 3.3. Crossover Operator Based on Q-Learning

The crossover operation in a genetic algorithm is the exchange of some genes between two matched chromosomes in a certain way, so as to form two new individuals. However, multidimensional data contain many features, and cross fragments tend to focus on features with large value intervals; hence, the breakpoints on other features lose the chance to cross. However, there are complex correlations among features. Without prior knowledge as a guide, the cross operation of the discretization scheme to be optimized becomes blind, which causes some high-quality fragments to have a high probability of being destroyed. To this end, we use the decision-making ability of Q-learning to select some features of the discretization scheme to be optimized in each iteration for the cross operation.(1)
State: according to the abovementioned analysis, the crossover operation will give each feature a certain probability of change. We define the set of changing features in the crossover operation as a state. Assuming that the multidimensional data haveN features, the search space is divided into 2N−1 states, each a combination of several features. For example, when N=3, there are seven states: f1, f2, f3, f1,f2, f1,f3, f2,f3, and f1,f2,f3, where fi is the ith feature of multidimensional data, 1≤i≤N, and the elements in ∗ represent the features corresponding to the loci of the most recent crossover or mutation operation.(2)
Action: since multidimensional data generally contain a large number of features, according to the abovementioned definition of states, the number of states will increase exponentially. The transition between two states corresponds to one action; so, many actions must be defined, which increases the computational complexity. According to the previous analysis, we mainly want to avoid the situation that in each crossover operation, cross segments focus on features with a larger value range, which makes some breakpoints lose the chance of crossing. In addition, some high-quality segments will be destroyed without prior knowledge as guidance. Therefore, for the current state, the next state to jump to after performing an action should be mainly considered from three aspects. First, the feature set of the next state is a subset of that of the previous state. Second, the feature set of the next state is a complement of that the previous state. Third, the intersection of the feature set of the next state and that of the previous state is not empty. Accordingly, there are three kinds of actions, represented byG, H, and I. The algorithm jumps to a new state by performing actions on the current state, and executes cross operations on all of the features contained in the new state. Suppose St is the current state and St+1 is the next state. GSt represents a random jump to one of all of the subsets of the current state, GSt is a random jump to one of all of the subsets of the complementary set of the current state, and HSt is a random jump to a set whose intersection with the current state is not empty and is not a subset of the current state, as shown below.(10)St+1=GSt,St+1∈SS⊆St∧S≠Ø,St+1=HSt,St+1∈SS∩St=Ø∧S≠Ø,St+1=ISt,St+1∈SS⊄St∧S≠St∧S∩St≠Ø.It is easy to see that the range of values forGSt, HSt, and ISt covers all of the states.(3)
Reward: to make a correct decision when selecting a feature set in each crossover operation so as to more quickly approach the optimal solution, we set a reward value for each state-action combination. The reward value is based on the change of individual fitness, which is mainly used to evaluate the search for the optimal solution of the algorithm. In the formula mentioned below,PSt⟶St+1At is the probability of jumping to the next state St+1 after performing action At in the current state St. This is related to the number Nstate of all of the possible states to jump to, which is 1/Nstate. fitSt and fitSt+1 are, respectively, the individual fitness of the current and next state, and lbest is the historical best fitness of the discretization scheme to be optimized.(11)Reward=5×PSt⟶St+1At,fitSt+1>lbest,1×PSt⟶St+1At,fitSt<fitSt+1≤lbest,0,fitSt+1=fitSt,−1×PSt⟶St+1At,fitSt+1<fitSt.According to the designed reward value, we can updateQ when the discretization scheme to be optimized has a cross operation.


### 3.4. Mutation Operator Based on Q-Learning

Like the crossover operator, we use the decision-making ability of Q-learning to select some features of the discretization scheme to be optimized in each iteration for the mutation operation. The state, action, and reward of the mutation and cross operation are consistent, the only difference being to change the cross operation on the feature to a mutation operation. They each maintain a Q-table. Figure4 shows the update process of two Q-tables of a discretization scheme with three features in one iteration.Figure 4
Updating process of two Q-tables of a discretization scheme with three features in one iteration.Both Q-tables are initialized to 0. After N iterations, the Q-tables corresponding to the cross and mutation operations are shown in Figures4(a) and 4(b), respectively. Assuming that the current state is f1,f3, action H is selected for the cross operation. Accordingly, the state jumps to f2, and Q’s value of 1 is updated to 6 in cross operation. Then, state f2 selects action f2,f3 for the mutation operation. Accordingly, the state randomly jumps to f2,f3, and Q′ s value of 2 is updated to 3 in the mutation operation. In this way, the two Q-tables are updated in one iteration.


### 3.5. Flow of RLGA Algorithm

Algorithm2 shows the flow of the proposed method. First, binary genetic coding is applied to the attribute values of the multidimensional data, and the state is generated according to the number of features. Then, in the current state of the discretization scheme to be optimized, the greedy algorithm is used to select the action, jump to the next state, and cross operate with the global optimal individual on the corresponding features. At the same time, the reward value is evaluated according to the fitness value after the cross operation, whose Q-table is then updated. Similarly, in the current state, an action is selected to continue the mutation operation, whose Q-table is updated. The population performs the conventional genetic operation and saves the global optimal individual in each iteration. Finally, the program outputs the maximum value of both the global and local variable. While the algorithm optimizes the given discretization scheme, other individuals of the population evolve to enlarge the search scope and improve the probability of obtaining the optimal solution.Algorithm 2:RLGA algorithm process.
Input: Multidimensional data discretization scheme
Output: Optimal discretization scheme
Initialize: global variable = 0, local variable = 0, crossover Q-Table = null, mutation Q-Table = null, t = 0;
begin
Get the initial breakpoints of the multidimensional data by sorting the values of each feature and removing duplicate values;
Binary encode the initial breakpoints of multidimensional data according to the method inPart B of Section 2;
Randomly generate initial populationP(t);
Calculate the fitness of each individual inP(t) using equation (8);
Update global variable with the optimal individual fitness value inP(t);
Generate state set based on the number of features of multidimensional data according to the definition of state inPart C of Section 3;
Choose a state from the state set as the initial stateS(t);
whilet is less than the user’s termination iterations do
Choose an action from the action set {G, H, I} by e-greedy strategy according to the definition of action in Part C of Section 3;
Execute the selected action on the current stateS(t) to jump to the next state S(t + 1);
Perform crossover operation with global variable on the features contained in stateS(t + 1);
Calculate the fitness of the multidimensional data discretization scheme after crossover operation using equation (5);
Measure the corresponding reward using equation (11) according to the definition of reward in Part C of Section 3;
Update crossover Q-Table using equation (6);
if the fitness of the multidimensional data discretization scheme > local variable do
Update local variable with the fitness of the multidimensional data discretization scheme;
end
Perform crossover operation inP(t);
Calculate the fitness of each individual inP(t) using equation (8);
Update global variable with the optimal individual fitness value inP(t);
S(t) = S(t + 1);
Choose an action from the action set {G, H, I} by e-greedy strategy according to the definition of action in Part C of Section 3;
Execute the selected action on the current stateS(t) to jump to the next state S(t + 1);
Perform mutation operation on the features contained in stateS(t + 1)
Calculate the fitness of the multidimensional data discretization scheme after mutation operation using equation (5);
Measure the corresponding reward using equation (11) according to the definition of reward in Part C of Section 3;
Update mutation Q-Table using equation (6);
if the fitness of the multidimensional data discretization scheme > local variable do
Update local variable with the fitness of the multidimensional data discretization scheme;
end
Perform mutation operation inP(t);
Calculate the fitness of each individual inP(t) using equation (8);
Update global variable with the optimal individual fitness value inP(t);
t = t + 1;
end
Return Max(global variable, local variable);
end


## 3.1. Evolution of Discretization Scheme to Be Optimized

We perform evolutionary operations on the optimized discretization scheme and initial population, as shown in Figure3. The global variable preserves the best individual of the population, while the local variable preserves the historical best individual of the discretization scheme to be optimized. In each iteration, the fitness of the current population is calculated, the optimal individual is obtained, and the global variable is updated. Then, the discretization scheme to be optimized and the optimal individual of the population carry out the cross and mutation operations based on reinforcement learning, and the local variable is updated. If the termination condition is not reached, then the population will continue to carry out ordinary evolutionary operations. Otherwise, by comparing the global variable and local variable, the individual with the largest fitness will be output.Figure 3
Evolution of the discretization scheme to be optimized.


## 3.2. Selection Operator Based on the Control Function

The selection operation is based on the evaluation of individual fitness in the population. Individuals with higher fitness are generally more likely to be selected. Roulette [44] is a simple, efficient, probability-based method that is often used to select individuals. If the population size is n and the fitness value of individual i is fi, then the probability that individual i is selected is(7)Pi=fi∑j=1nfj.However, individuals with large fitness are more likely to be selected, which may result in the destruction of population diversity. SinceRD takes the value 0 or 1, individuals with fitness value 0 cannot be selected in the evolution of the population. Although these individuals are not feasible solutions at the initial stage, they may be close to the optimal feasible solution, and may eventually evolve into it. However, considering the randomness and evenness of the initial population, feasible solutions with RD = 1 and potential feasible solutions with RD = 0 tend to be quantitatively equivalent. Even with a small population, because of the complex correlation among the features of multidimensional data, there are far more potential feasible solutions with RD = 0 than with RD = 1. Therefore, when roulette is used for individual selection, the potential feasible solutions that are the majority of the population will be eliminated, thus destroying the diversity of the population. According to the abovementioned analysis, to ensure the diversity of the population in the early stage and accelerate convergence of individuals to the optimal solution in the late stage of evolution, we expand the fitness function by adding the control function on the original basis, and we determine the control factors according to the proportion of feasible solutions in the population in the current stage of evolution. The fitness function of chromosome x is thus expanded to(8)Fitness′x=NI−NDxNI×RDx+σp×φx.The control function consists of control itemφx and control factor σp, where σp is the proportion of the population consisting of potential feasible solutions with RD = 0, and σp is a function with p as an independent variable. The expressions for φx and σp are(9)φx=NI−NDxNIz,σp=0,μ=1,μ1−p,0<μ<1,12k×log2NI1−p,μ=0,μ=∑i=1ksetcmpC−di′,C−di+setcmpC−di',C−di2k,where NI is the number of breakpoints in the initial breakpoint set, NDx is the number of breakpoints obtained after chromosome x decoding, RDx is the change of the indiscernible relationship of the decision table after discretization by chromosome x, k is the number of classes, di is the ith class, C_di and C−di are, respectively, the lower and upper approximation sets of di before discretization, C_di′ and C−di are, respectively, the lower and upper approximation sets of di after discretization, and setcmpsetA,setB is a user-defined set comparison function. When setA and setB are equal, the function value is 1, and otherwise it is 0. Since each class corresponds to a lower and upper approximation set, the value range of μ is 0≤μ≤1. The following points are made regarding the extended fitness function.(1)
We want to prevent the unreasonable situation that when the number of breakpoints of the feasible solution withRD=1 is equal to that of the potential feasible solution with RD=0, the fitness value of the former is less than or equal to that of the latter. Hence we require that index z of the control item satisfies z>1. In this paper, z=2.(2)
It can be seen that the value range ofμ is actually 2K+1 discrete points from 0 to 1, with the interval 1/2k. When μ=0, the indiscernibility of the decision table is destroyed after discretization. If μ=0, then μ = 0, and the significance of adding a control function for potential feasible solutions with RD=0 is lost, since the control function has a smaller value than when μ takes the minimum nonnegative value μ=1/2K. Consequently, we change the expression μ1−p to 1/2k×log2N11−p. So, when μ=0, the value of the control function is not 0, and it is smaller than its value with μ=1/2k. However, because the chromosome is binary coded, taking “2” as the base number and N1 as the true number can ensure that the difference between the two control function values corresponding to μ=0 and μ=1/2k is not too large, and this controls the selection of individuals relatively reasonably.(3)
Whenμ=1, RD=1 and σp=0, indicating that this individual is a feasible solution, and the value of the control item is 0. When 0≤μ<1, 0≤μ<1 and σp is an increasing function with p as the independent variable. Consider that in the early stage of evolution, there are few or no feasible solutions in the population, i.e., p is large. At this time, σp should be relatively large, so the potential feasible solution can be selected with a large probability in roulette, and the search is gradually guided to the area of feasible solutions. As evolution progresses, more and more feasible solutions appear in the population, i.e., p becomes smaller and smaller. Accordingly, σp should become smaller and smaller, accelerating the movement from feasible to optimal solutions.


## 3.3. Crossover Operator Based on Q-Learning

The crossover operation in a genetic algorithm is the exchange of some genes between two matched chromosomes in a certain way, so as to form two new individuals. However, multidimensional data contain many features, and cross fragments tend to focus on features with large value intervals; hence, the breakpoints on other features lose the chance to cross. However, there are complex correlations among features. Without prior knowledge as a guide, the cross operation of the discretization scheme to be optimized becomes blind, which causes some high-quality fragments to have a high probability of being destroyed. To this end, we use the decision-making ability of Q-learning to select some features of the discretization scheme to be optimized in each iteration for the cross operation.(1)
State: according to the abovementioned analysis, the crossover operation will give each feature a certain probability of change. We define the set of changing features in the crossover operation as a state. Assuming that the multidimensional data haveN features, the search space is divided into 2N−1 states, each a combination of several features. For example, when N=3, there are seven states: f1, f2, f3, f1,f2, f1,f3, f2,f3, and f1,f2,f3, where fi is the ith feature of multidimensional data, 1≤i≤N, and the elements in ∗ represent the features corresponding to the loci of the most recent crossover or mutation operation.(2)
Action: since multidimensional data generally contain a large number of features, according to the abovementioned definition of states, the number of states will increase exponentially. The transition between two states corresponds to one action; so, many actions must be defined, which increases the computational complexity. According to the previous analysis, we mainly want to avoid the situation that in each crossover operation, cross segments focus on features with a larger value range, which makes some breakpoints lose the chance of crossing. In addition, some high-quality segments will be destroyed without prior knowledge as guidance. Therefore, for the current state, the next state to jump to after performing an action should be mainly considered from three aspects. First, the feature set of the next state is a subset of that of the previous state. Second, the feature set of the next state is a complement of that the previous state. Third, the intersection of the feature set of the next state and that of the previous state is not empty. Accordingly, there are three kinds of actions, represented byG, H, and I. The algorithm jumps to a new state by performing actions on the current state, and executes cross operations on all of the features contained in the new state. Suppose St is the current state and St+1 is the next state. GSt represents a random jump to one of all of the subsets of the current state, GSt is a random jump to one of all of the subsets of the complementary set of the current state, and HSt is a random jump to a set whose intersection with the current state is not empty and is not a subset of the current state, as shown below.(10)St+1=GSt,St+1∈SS⊆St∧S≠Ø,St+1=HSt,St+1∈SS∩St=Ø∧S≠Ø,St+1=ISt,St+1∈SS⊄St∧S≠St∧S∩St≠Ø.It is easy to see that the range of values forGSt, HSt, and ISt covers all of the states.(3)
Reward: to make a correct decision when selecting a feature set in each crossover operation so as to more quickly approach the optimal solution, we set a reward value for each state-action combination. The reward value is based on the change of individual fitness, which is mainly used to evaluate the search for the optimal solution of the algorithm. In the formula mentioned below,PSt⟶St+1At is the probability of jumping to the next state St+1 after performing action At in the current state St. This is related to the number Nstate of all of the possible states to jump to, which is 1/Nstate. fitSt and fitSt+1 are, respectively, the individual fitness of the current and next state, and lbest is the historical best fitness of the discretization scheme to be optimized.(11)Reward=5×PSt⟶St+1At,fitSt+1>lbest,1×PSt⟶St+1At,fitSt<fitSt+1≤lbest,0,fitSt+1=fitSt,−1×PSt⟶St+1At,fitSt+1<fitSt.According to the designed reward value, we can updateQ when the discretization scheme to be optimized has a cross operation.


## 3.4. Mutation Operator Based on Q-Learning

Like the crossover operator, we use the decision-making ability of Q-learning to select some features of the discretization scheme to be optimized in each iteration for the mutation operation. The state, action, and reward of the mutation and cross operation are consistent, the only difference being to change the cross operation on the feature to a mutation operation. They each maintain a Q-table. Figure4 shows the update process of two Q-tables of a discretization scheme with three features in one iteration.Figure 4
Updating process of two Q-tables of a discretization scheme with three features in one iteration.Both Q-tables are initialized to 0. After N iterations, the Q-tables corresponding to the cross and mutation operations are shown in Figures4(a) and 4(b), respectively. Assuming that the current state is f1,f3, action H is selected for the cross operation. Accordingly, the state jumps to f2, and Q’s value of 1 is updated to 6 in cross operation. Then, state f2 selects action f2,f3 for the mutation operation. Accordingly, the state randomly jumps to f2,f3, and Q′ s value of 2 is updated to 3 in the mutation operation. In this way, the two Q-tables are updated in one iteration.


## 3.5. Flow of RLGA Algorithm

Algorithm2 shows the flow of the proposed method. First, binary genetic coding is applied to the attribute values of the multidimensional data, and the state is generated according to the number of features. Then, in the current state of the discretization scheme to be optimized, the greedy algorithm is used to select the action, jump to the next state, and cross operate with the global optimal individual on the corresponding features. At the same time, the reward value is evaluated according to the fitness value after the cross operation, whose Q-table is then updated. Similarly, in the current state, an action is selected to continue the mutation operation, whose Q-table is updated. The population performs the conventional genetic operation and saves the global optimal individual in each iteration. Finally, the program outputs the maximum value of both the global and local variable. While the algorithm optimizes the given discretization scheme, other individuals of the population evolve to enlarge the search scope and improve the probability of obtaining the optimal solution.Algorithm 2:RLGA algorithm process.
Input: Multidimensional data discretization scheme
Output: Optimal discretization scheme
Initialize: global variable = 0, local variable = 0, crossover Q-Table = null, mutation Q-Table = null, t = 0;
begin
Get the initial breakpoints of the multidimensional data by sorting the values of each feature and removing duplicate values;
Binary encode the initial breakpoints of multidimensional data according to the method inPart B of Section 2;
Randomly generate initial populationP(t);
Calculate the fitness of each individual inP(t) using equation (8);
Update global variable with the optimal individual fitness value inP(t);
Generate state set based on the number of features of multidimensional data according to the definition of state inPart C of Section 3;
Choose a state from the state set as the initial stateS(t);
whilet is less than the user’s termination iterations do
Choose an action from the action set {G, H, I} by e-greedy strategy according to the definition of action in Part C of Section 3;
Execute the selected action on the current stateS(t) to jump to the next state S(t + 1);
Perform crossover operation with global variable on the features contained in stateS(t + 1);
Calculate the fitness of the multidimensional data discretization scheme after crossover operation using equation (5);
Measure the corresponding reward using equation (11) according to the definition of reward in Part C of Section 3;
Update crossover Q-Table using equation (6);
if the fitness of the multidimensional data discretization scheme > local variable do
Update local variable with the fitness of the multidimensional data discretization scheme;
end
Perform crossover operation inP(t);
Calculate the fitness of each individual inP(t) using equation (8);
Update global variable with the optimal individual fitness value inP(t);
S(t) = S(t + 1);
Choose an action from the action set {G, H, I} by e-greedy strategy according to the definition of action in Part C of Section 3;
Execute the selected action on the current stateS(t) to jump to the next state S(t + 1);
Perform mutation operation on the features contained in stateS(t + 1)
Calculate the fitness of the multidimensional data discretization scheme after mutation operation using equation (5);
Measure the corresponding reward using equation (11) according to the definition of reward in Part C of Section 3;
Update mutation Q-Table using equation (6);
if the fitness of the multidimensional data discretization scheme > local variable do
Update local variable with the fitness of the multidimensional data discretization scheme;
end
Perform mutation operation inP(t);
Calculate the fitness of each individual inP(t) using equation (8);
Update global variable with the optimal individual fitness value inP(t);
t = t + 1;
end
Return Max(global variable, local variable);
end


## 4. Experimental Design

We introduce the experimental data source, experimental environment configuration, and dataset used in the experiment.


### 4.1. Data Source

The experimental data are from a Landsat 8 satellite image in the coastal area of the South China Sea on February 22, 2018, as shown in Figure5. The image consists of seven bands. In the experiment, the objects on the image are divided into five categories: impervious surface, construction, bare land, water, and vegetation.Figure 5
Area used for study.


### 4.2. Configuration of Experimental Environment

To verify the effectiveness of the algorithm in this paper, comparative experiments are carried out using an Intel Core i5-5200U CPU@2.20GHZ, 12 GB memory, and 512 GB hard disk. The visualization, programming, simulation, testing, and calculation are realized in MATLAB R2016a. The radiometric calibration and atmospheric correction of images, training of classifiers for discrete results, and comparison of classification prediction accuracy are completed in an ENVI5.3 environment.


### 4.3. Preparation of Experimental Datasets

We randomly select several areas from the image, covering the five categories specified above and integrate them into a set of experimental samples containing training and test sets. The training set includes 6331 samples, consisting of 935 impervious surface samples, 936 construction samples, 958 bare land samples, 2324 water samples, and 1178 vegetation samples. We sort the pixel values of the training set and delete duplicate values in each band to obtain the initial breakpoints of the seven bands, which are 1403, 1429, 1680, 1869, 2402, 2530, and 2240, for a total of 13553 breakpoints. We discretize this initial set and carry out the comparative experiments.We compare the proposed method to the classical genetic algorithm (GA) [33] based on the consistency principle of the decision system. Then, we compare the optimal set of breakpoints obtained by our method with those of current mainstream supervised discretization methods, such as EDiRa [45], ChiMerge [46], 1R [23], NCAIC [47], FUDC [48], Cramer’s V-Test [49], and Chi2 [50], mainly on the evaluation of the number of intervals and data consistency.In addition, we use the proposed method to optimize the discretization results of the MFD-mvtR algorithm [51]. Finally, we train the neural network classifiers with the discretized samples of all of the methods, and verify the effectiveness of our method by comparing the classification accuracy of each method.


## 4.1. Data Source

The experimental data are from a Landsat 8 satellite image in the coastal area of the South China Sea on February 22, 2018, as shown in Figure5. The image consists of seven bands. In the experiment, the objects on the image are divided into five categories: impervious surface, construction, bare land, water, and vegetation.Figure 5
Area used for study.


## 4.2. Configuration of Experimental Environment

To verify the effectiveness of the algorithm in this paper, comparative experiments are carried out using an Intel Core i5-5200U CPU@2.20GHZ, 12 GB memory, and 512 GB hard disk. The visualization, programming, simulation, testing, and calculation are realized in MATLAB R2016a. The radiometric calibration and atmospheric correction of images, training of classifiers for discrete results, and comparison of classification prediction accuracy are completed in an ENVI5.3 environment.


## 4.3. Preparation of Experimental Datasets

We randomly select several areas from the image, covering the five categories specified above and integrate them into a set of experimental samples containing training and test sets. The training set includes 6331 samples, consisting of 935 impervious surface samples, 936 construction samples, 958 bare land samples, 2324 water samples, and 1178 vegetation samples. We sort the pixel values of the training set and delete duplicate values in each band to obtain the initial breakpoints of the seven bands, which are 1403, 1429, 1680, 1869, 2402, 2530, and 2240, for a total of 13553 breakpoints. We discretize this initial set and carry out the comparative experiments.We compare the proposed method to the classical genetic algorithm (GA) [33] based on the consistency principle of the decision system. Then, we compare the optimal set of breakpoints obtained by our method with those of current mainstream supervised discretization methods, such as EDiRa [45], ChiMerge [46], 1R [23], NCAIC [47], FUDC [48], Cramer’s V-Test [49], and Chi2 [50], mainly on the evaluation of the number of intervals and data consistency.In addition, we use the proposed method to optimize the discretization results of the MFD-mvtR algorithm [51]. Finally, we train the neural network classifiers with the discretized samples of all of the methods, and verify the effectiveness of our method by comparing the classification accuracy of each method.


## 5. Results and Discussion

We compare the performance of our method with that of the classical genetic algorithm based on the consistency principle of the decision system, and we evaluate the results of seven state-of-the-art discretization methods on the Landsat 8 image. We also use our method to optimize the discretization results of MFD-mvtR [51] on the Gaofen-2 image. Finally, the effectiveness of our method is verified by comparing the classification accuracy of each method.


### 5.1. RLGA versus GA

We set the population size of the two algorithms at 30 and the number of iterations at 500, and we run them 10 times independently. Figure6 shows the number of iterations of the two algorithms to reach the theoretical optimal solution in 10 independent experiments. Table 1 compares the convergence rates of the two algorithms. The search efficiency is expressed as(12)E=1−AT,where A is the average number of iterations to obtain the optimal solution, T is the total number of iterations, and E is the search efficiency, i.e., the convergence speed. The larger the value, the faster the convergence.Figure 6
Iterations of the two algorithms to reach theoretical optimal solution.Table 1
Comparison of running time in one iteration.
Method
Iterations
Average
Search efficiency
RLGA
500
338.6
0.323
GA
500
425.3
0.149It can be seen from Table1 that the average number of iterations for GA to obtain the optimal solution is 425.3, and the search efficiency is 0.149. These numbers correspond, respectively, to 338.6 and 0.323 for our method, an obvious improvement in performance.


### 5.2. RLGA versus Mainstream Discretization Algorithms

We compare the optimal set of breakpoints obtained by our method to mainstream supervised discretization methods, including EDiRa [45], ChiMerge [46], 1R [23], NCAIC [47], FUDC [48], Cramer’s V-Test [49], and Chi2 [50], on the number of intervals and data consistency.Figure7 shows the number of discrete intervals obtained by the eight algorithms in each band. RLGA obtains the minimum number of breakpoints in each band. Table 2 compares the overall number of intervals and data consistency of the eight algorithms. We can see that the number of discrete intervals obtained by RLGA is 2247, which is the least among all of the algorithms, and there is no data error. EDiRa obtains 3909 discrete intervals with 4 data errors. The number of discrete intervals obtained by ChiMerge is 4947, and the number of data errors is also 4. The number of discrete intervals obtained by 1R is 3053, which is the least excepted for RLGA, but it has the most data errors among all of the algorithms, at 31. The number of discrete intervals obtained by NCAIC is the largest among all of the algorithms, at 5041, with 4 data errors. FUDC obtains 4072 discrete intervals, with 4 data errors. Cramer’s V-Test and Chi2 both obtain relatively small numbers of discrete intervals, 3858 and 3538, respectively, but there are also more data errors, 7 and 19, respectively. Considering the number of discrete intervals and the number of data errors, RLGA has the best discretization quality.Figure 7
Number of breakpoints of eight algorithms in different bands.Table 2
Comparison of the eight algorithms on intervals and inconsistencies.
Method
Intervals
Inconsistencies
RLGA
2247
0
EDiRa
3909
4
ChiMerge
4947
4
1R
3053
31
NCAIC
5041
4
FUDC
4936
4
V-Test
3858
7
Chi2
3538
19


### 5.3. Optimization of Breakpoints on Gaofen-2 Image

We use RLGA to optimize the discretization results obtained by the MFD-mvtR algorithm on the Gaofen-2 image [51]. Considering that this image contains only four bands, the search space is divided into 15 states, which is less than the 127 states obtained from 7 bands of the Landsat 8 image. Therefore, we can set the number of iterations of RLGA to only 100 to allow the algorithm to fully learn. The number of optimized breakpoints is shown in Tables 3 and 4.Table 3
Number of breakpoints optimized by RLGA.
Method
Band 1
Band 2
Band 3
Band 4
RLGA
310
301
222
198
MFD-mvtR
350
350
346
299
EDiRa
349
349
346
299
ChiMerge
442
433
298
299
1R
64
70
42
40
NCAIC
447
468
346
299
FUDC
397
439
312
258
V-Test
432
423
288
289
Chi2
410
438
325
272Table 4
Quality of the discretization scheme optimized by RLGA.
Method
Number of intervals
Inconsistencies
RLGA
1031
0
MFD-mvtR
1345
5
EDiRa
1343
16
ChiMerge
1472
7
1R
216
38
NCAIC
1560
7
FUDC
1406
7
V-Test
1432
7
Chi2
1445
7The MFD-mvtR algorithm [51] obtains 1345 breakpoints with 5 data errors on the Gaofen-2 image. Compared to other mainstream algorithms, the results of discretization are satisfactory. We take the results of MFD-mvtR as the discretization scheme to be optimized, use RLGA to perform the cross operation based on reinforcement learning with the optimal individuals in the population, and carry out its own mutation operation based on reinforcement learning. By further optimizing the results of MFD-mvtR, we can see that the numbers of breakpoints in the four bands are reduced to 310, 301, 222, and 198, respectively. The total number of breakpoints is 314 less than before optimization, and the number of data errors is reduced to 0.Table5 shows the classification accuracy of the neural network after training the discrete feature sets obtained by the abovementioned algorithms. We can see that after optimizing the discretization scheme of MFD-mvtR, the classification accuracy obtained by confusion matrix is about 6 percentage points higher than the original, and the kappa coefficient is 0.8925. Our method reduces the number of breakpoints in the discretization scheme of MFD-mvtR to a certain extent, while ensuring that there is no data error. It can simplify the dataset and effectively identify the five types of areas of impervious surface, construction, bare land, water, and vegetation on the image after training the classifier by the optimized discrete feature set, which improves the performance of the classifier.Table 5
Classification accuracy of discretization scheme optimized by RLGA.
Method
Overall accuracy (%)
Kappa coefficient
RLGA
91.0417
0.8925
MFD-mvtR
85.2083
0.8225
EDiRa
74.1667
0.6900
ChiMerge
80.2083
0.7625
1R
56.4583
0.4775
NCAIC
80.6250
0.7675
FUDC
76.2500
0.7150
V-Test
79.7917
0.7575
Chi2
79.3750
0.7525


## 5.1. RLGA versus GA

We set the population size of the two algorithms at 30 and the number of iterations at 500, and we run them 10 times independently. Figure6 shows the number of iterations of the two algorithms to reach the theoretical optimal solution in 10 independent experiments. Table 1 compares the convergence rates of the two algorithms. The search efficiency is expressed as(12)E=1−AT,where A is the average number of iterations to obtain the optimal solution, T is the total number of iterations, and E is the search efficiency, i.e., the convergence speed. The larger the value, the faster the convergence.Figure 6
Iterations of the two algorithms to reach theoretical optimal solution.Table 1
Comparison of running time in one iteration.
Method
Iterations
Average
Search efficiency
RLGA
500
338.6
0.323
GA
500
425.3
0.149It can be seen from Table1 that the average number of iterations for GA to obtain the optimal solution is 425.3, and the search efficiency is 0.149. These numbers correspond, respectively, to 338.6 and 0.323 for our method, an obvious improvement in performance.


## 5.2. RLGA versus Mainstream Discretization Algorithms

We compare the optimal set of breakpoints obtained by our method to mainstream supervised discretization methods, including EDiRa [45], ChiMerge [46], 1R [23], NCAIC [47], FUDC [48], Cramer’s V-Test [49], and Chi2 [50], on the number of intervals and data consistency.Figure7 shows the number of discrete intervals obtained by the eight algorithms in each band. RLGA obtains the minimum number of breakpoints in each band. Table 2 compares the overall number of intervals and data consistency of the eight algorithms. We can see that the number of discrete intervals obtained by RLGA is 2247, which is the least among all of the algorithms, and there is no data error. EDiRa obtains 3909 discrete intervals with 4 data errors. The number of discrete intervals obtained by ChiMerge is 4947, and the number of data errors is also 4. The number of discrete intervals obtained by 1R is 3053, which is the least excepted for RLGA, but it has the most data errors among all of the algorithms, at 31. The number of discrete intervals obtained by NCAIC is the largest among all of the algorithms, at 5041, with 4 data errors. FUDC obtains 4072 discrete intervals, with 4 data errors. Cramer’s V-Test and Chi2 both obtain relatively small numbers of discrete intervals, 3858 and 3538, respectively, but there are also more data errors, 7 and 19, respectively. Considering the number of discrete intervals and the number of data errors, RLGA has the best discretization quality.Figure 7
Number of breakpoints of eight algorithms in different bands.Table 2
Comparison of the eight algorithms on intervals and inconsistencies.
Method
Intervals
Inconsistencies
RLGA
2247
0
EDiRa
3909
4
ChiMerge
4947
4
1R
3053
31
NCAIC
5041
4
FUDC
4936
4
V-Test
3858
7
Chi2
3538
19


## 5.3. Optimization of Breakpoints on Gaofen-2 Image

We use RLGA to optimize the discretization results obtained by the MFD-mvtR algorithm on the Gaofen-2 image [51]. Considering that this image contains only four bands, the search space is divided into 15 states, which is less than the 127 states obtained from 7 bands of the Landsat 8 image. Therefore, we can set the number of iterations of RLGA to only 100 to allow the algorithm to fully learn. The number of optimized breakpoints is shown in Tables 3 and 4.Table 3
Number of breakpoints optimized by RLGA.
Method
Band 1
Band 2
Band 3
Band 4
RLGA
310
301
222
198
MFD-mvtR
350
350
346
299
EDiRa
349
349
346
299
ChiMerge
442
433
298
299
1R
64
70
42
40
NCAIC
447
468
346
299
FUDC
397
439
312
258
V-Test
432
423
288
289
Chi2
410
438
325
272Table 4
Quality of the discretization scheme optimized by RLGA.
Method
Number of intervals
Inconsistencies
RLGA
1031
0
MFD-mvtR
1345
5
EDiRa
1343
16
ChiMerge
1472
7
1R
216
38
NCAIC
1560
7
FUDC
1406
7
V-Test
1432
7
Chi2
1445
7The MFD-mvtR algorithm [51] obtains 1345 breakpoints with 5 data errors on the Gaofen-2 image. Compared to other mainstream algorithms, the results of discretization are satisfactory. We take the results of MFD-mvtR as the discretization scheme to be optimized, use RLGA to perform the cross operation based on reinforcement learning with the optimal individuals in the population, and carry out its own mutation operation based on reinforcement learning. By further optimizing the results of MFD-mvtR, we can see that the numbers of breakpoints in the four bands are reduced to 310, 301, 222, and 198, respectively. The total number of breakpoints is 314 less than before optimization, and the number of data errors is reduced to 0.Table5 shows the classification accuracy of the neural network after training the discrete feature sets obtained by the abovementioned algorithms. We can see that after optimizing the discretization scheme of MFD-mvtR, the classification accuracy obtained by confusion matrix is about 6 percentage points higher than the original, and the kappa coefficient is 0.8925. Our method reduces the number of breakpoints in the discretization scheme of MFD-mvtR to a certain extent, while ensuring that there is no data error. It can simplify the dataset and effectively identify the five types of areas of impervious surface, construction, bare land, water, and vegetation on the image after training the classifier by the optimized discrete feature set, which improves the performance of the classifier.Table 5
Classification accuracy of discretization scheme optimized by RLGA.
Method
Overall accuracy (%)
Kappa coefficient
RLGA
91.0417
0.8925
MFD-mvtR
85.2083
0.8225
EDiRa
74.1667
0.6900
ChiMerge
80.2083
0.7625
1R
56.4583
0.4775
NCAIC
80.6250
0.7675
FUDC
76.2500
0.7150
V-Test
79.7917
0.7575
Chi2
79.3750
0.7525


## 6. Conclusion and Future Work

In the process of multidimensional data discretization, due to the complex correlation among features and the performance bottleneck of the traditional discretization criteria, most discretization schemes obtained by the algorithms are not optimal in specific application scenarios or they may even fail to meet the accuracy requirements of the system. Some swarm intelligence algorithms can achieve better results, but without prior knowledge as a guide, it is difficult to formulate appropriate strategies, which will cause an inefficient search in multidimensional space, consume many computing resources, and easily fall into local optimization. To solve these problems, this paper proposes a reinforcement learning-based genetic algorithm to optimize the discretization of multidimensional data. First, we binary code the attribute values of the multidimensional data and initialize the population. Second, we use rough sets to construct individual fitness functions and design control functions to dynamically adjust the diversity of the population. Then, we introduce the Q-learning reinforcement learning mechanism to the crossover and mutation operations to determine the crossover fragments and mutation points of the discretization to be optimized. We conduct simulation experiments on Landsat 8 and Gaofen-2 images to compare RLGA to the traditional genetic algorithm and state-of-the-art discretization methods. The experimental results show that our method can reduce the number of breakpoints and simplify the multidimensional dataset without decreasing the data consistency and classification accuracy of a discretization scheme.Future research work includes the following: (1) test and improve the proposed method on different multidimensional datasets, expand its application scope, and make it more practical; (2) to ease the problems of high-dimensional datasets, improve the algorithm using deep Q-learning technology; and (3) improve the performance of the deep neural network by using RLGA to optimize its parameters.



---

*Source: 1698323-2020-03-30.xml*