2.1. Monotonic Classification

Ordinal classification problems are those in which the class is neither numeric nor nominal. Instead, the class values are ordered. For instance, a worker can be described as “excellent”, “good” or “bad”, and a bond can be evaluated as “AAA”, “AA”, “A”, “A-”, etc. Similar to a numeric scale, an ordinal scale has an order, but it does not possess a precise concept of distance. Ordinal classification problems are important, since they are fairly common in our daily life. Employee selection and promotion, determining credit rating, bond rating, economic performance of countries, industries and firms, and insurance underwriting, are examples of ordinal problem-solving in business. Rating manuscripts, evaluating lecturers, student admissions, and scholarships decisions for students, are examples of ordinal decision-making in academic life. Ordinal problems have been investigated in scientific disciplines such as information retrieval, psychology, and statistics for many decades ⁴.

A monotonic classifier is one that will not violate monotonicity constraints. Informally, the monotonic classification implies that the assigned class values are monotonically non-decreasing (in ordinal order) with the attribute values. More formally, let {x_i, class(x_i)} denote a set of examples with attribute vector x_i = (x_i,1,…,x_i,m) and a class, class(x_i), being n the number of instances and m the number of attributes. Let x_i ≻ x_h iff ∀_j=1,…,m, x_i,j ≥ x_h,j.

A data set {x_i, class(x_i)} is monotonic if and only if all the pairs of examples i, h are monotonic with respect to each other ¹⁰ (see equation 1).

Some monotonic ordinal classifiers require monotonic data sets to successfully learn, although there are others that are capable of learning from non-monotonic data sets as well.

2.2. Monotonic Classification Methods

Four monotonic learning methods are pioneers and well-known in the field of monotonic classification. In the following, we will discuss each one in detail.

• •

  The Ordinal Learning Model (OLM) ¹⁵ is a very simple algorithm that learns ordinal concepts by eliminating non-monotonic pairwise inconsistencies. The generated concepts can be viewed as rules. During the learning phase, each example is checked against every rule in a rule-base, which is initially empty. If an example is inconsistent with a rule in the rule-base, one of them is selected at random while the other is discarded, but if the example is selected, it must be checked for consistency against all the other monotonicity rules. If it passes this consistency test, it is added as a rule. Consequently, the rule-base is kept monotonic at all times. Classification is done conservatively. All the rules are checked in decreasing order of class values against an attribute vector, and the vector is classified as the class of the first rule that covers it. If such a rule does not exist, the attribute vector is assigned the lowest possible class.

• •

  As its name implies, Ordinal Stochastic Dominance Learner (OSDL) ¹⁶, is based on the concept of Ordinal Stochastic Dominance (OSD). The rationale behind OSD can be given through an example: In life insurance, one may expect a stochastically greater risk to the insurer from older and sicker applicants than from younger and healthier ones. Higher premiums should reflect greater risks and vice versa. There are several definitions of stochastic ordering. The stochastic order computes when a random variable is bigger than another. Considering this order, stochastic dominance can be established as a form of stochastic order. In this case, a probability distribution over possible predictions can be ranked. The ranking depends of the nature of the data set. Stochastic dominance refers to a set of relations that may hold between a pair of distributions.

  The most commonly used, as stochastic ordering, is first OSD, which was used by ³⁶ in the OSDL. For each vector x_i, the OSDL computes two mapping functions: one that is based on the examples that are stochastically dominated by x_i with the maximum label (of that subset), and the second is based on the examples that cover (i.e., dominate) x_i, with the smallest label. Later, an interpolation between the two class values (based on their position) is returned as a class.

• •

  The monotonic kNN (Mk-NN) was proposed in ¹⁷. This method consists of two steps. In the first step, the training data is made monotone by relabeling as few cases as possible. This relabeled data set may be considered as the monotone classifier with the smallest error index in the training data. In the second step, we use a modified nearest neighbour rule to predict the class labels of new data so that violations of the restrictions of monotonicity will not occur. Considering the monotonic nearest neighbor rule, the class label assigned to a new data point x₀ must lie in the interval [class_min,class_max], where

  (2)classmin=max {class(xi)|{xi, class(xi)}∧xi≤x0}

  and

  (3)classmax=min {class(xi)|{xi, class(xi)}∧x0≤xi}

  where {x_i, class(x_i)} is the monotone data set. To conserve the monotonicity the choice of the class value for x₀ must be in this interval.

• •

  A monotone extension of ID3 (MID) was proposed by Ben-David ¹⁰ using an additional impurity measure for splitting, the total ambiguity score. However, the resulting tree may not be monotone anymore even when starting from a monotone data set. MID defines the total-ambiguity-score as the sum of the entropy score of ID3 and the order-ambiguity-score. This last score is defined in terms of the non-monotonicity index of the tree, which computes the number of pair branches that are non-monotonic regarding the total possible non-monotonic pairs there may be.

2.3. NGE Learning

NGE is a learning paradigm based on class exemplars, where an induced hypothesis has the graphical shape of a set of hyperrectangles in ℝⁿ. Exemplars of classes are either hyperrectangles or single instances ²⁰. The input of an NGE system is a set of training examples, each described as a vector of pairs numeric_attribute/value and an associated class. Attributes can either be numerical or categorical. Numerical attributes are usually normalized in the [0,1] interval.

In NGE, an initial set of hyperrectangles in ℝⁿ formed by single points directly taken from the data is generalized into a smaller set of hyperrectangles regarding the elements that it contains. Choosing which hyperrectangle is generalized from a subset of points or other hyperrectangles and how it is generalized depends on the concrete NGE algorithm employed.

The matching process is one of the central features in NGE learning and it allows some customization, if desired. Generally speaking, this process computes the distance between a new example and an exemplar memory object (a generalized example). Let the example to be classified be termed as x₀ and the generalized example as G, regardless of whether G is formed by a single point or if it has some volume.

The model computes a match score between x₀ and G by measuring the Euclidean distance between two objects. The Euclidean distance is well-known when G is a single point. Otherwise, the distance is computed as follows (considering numerical attributes):

The distance measure represents the length of a line dropped perpendicularly from the point x₀ to the nearest surface, edge or corner of G. Note that internal points in a hyperrectangle have a distance of 0 to that rectangle. In the case of overlapping rectangles, several strategies could be implemented, but it is usually accepted that a point falling in the overlapping area belongs to the smaller rectangle (the size of a hyperrectangle is defined in terms of volume). The volume is computed following the indications given in ²³. In nominal attributes, the distance is 0 when two attributes have the same categorical label, and 1 on the contrary.

3.1. Definitions

We represent each instance with x_i = (x_i,1; x_i,2;.……;x_i,m;class(x_i)), where x_i,j is the input value of the instance i in the attribute j, m is the total number of input attributes and class(x_i) is the class or output value of the instance i. Let the hyperrectangles be denoted by H : (∏jAj;C) , where A_j is a condition belonging to the antecedent and C is the response. A formal definition is given next:

The hyperrectangles should not break monotonicity in the sense we saw in Subsection 2.1. Hence, we define a partial order relation in the set of disjoint hyperrectangles, deciding when a precedent is higher than, lower than or equal to another:

Then let two hyperrectangles H and H′ be defined as:

Two hyperrectangles are comparable if H ≺ H′ or H ≻ H′, and non-comparable in contrary case, since we cannot establish an order between them. Hence, an hyperrectangle H:(∏jAj,C) will be non-monotonic with respect to another H′:(∏jAj′,C′) if:

The distance between an instance x_i and an hyperrectangle H is defined as follows:

If the attribute is nominal:

The distance between two hyperrectangles H and H′ is defined as:

3.2. Getting the Initial Set of Hyperrectangles

We start from a training set TR with n instances which consists of pairs (x_i, class(x_i)), i = 1, …, n. Each one of the n instances has m input attributes.

In this first phase will get a hyperrectangle set HS with N hyperrectangles whose rule representation consists of pairs (H_i, class(H_i)), i = 1, …, N, where H_i defines a set of conditions (A₁,A₂, …, A_m) and class(H_i) defines the associated class label of the hyperrectangle. Each one of the N hyperrectangles has m conditions which can be numerical conditions, expressed in terms of minimum and maximum values in intervals [0,1]; or they can be categorical conditions, by using a set of possible values A_i = {v_1i, v_2i, …, v_vi}, assuming that it has vi different values. Note that we make no distinction between a hyperrectangle with volume and minimal hyperrectangles formed by isolated points.

In this first stage of our method, we have used a simple heuristic which is fast and yields acceptable results. The heuristic yields a hyperrectangle from each example in the training set. For each one, it finds the k − 1 nearest neighbors being the k−th neighbor an example of a different class. Then, each hyperrectangle is expanded considering these k − 1 neighbors by using, in the case of numerical attributes, the minimal and maximal values as the limits of the interval defined, or getting all the different categorical values, in the case of nominal attributes, to form a subset of possible values from them.

Once all the hyperrectangles are obtained, the duplicated ones are removed, keeping one representative in each case. Hence |HS| ≤ |TR|. Note that point hyperrectangles are possible to be obtained using this heuristic when the nearest neighbor of an instance belongs to a different class.

3.3. CHC Model

As an evolutionary computation method, we have used the CHC model ³². CHC is a classical evolutionary model that introduces important aspects to obtain a trade-off between exploration and exploitation; such as incest prevention, restoration of the search process when it becomes locked and the fight among parents and offspring into the replacement process.

During each generation the CHC realizes the following stages:

• •

  NC children born after mating of NC individuals of the father population.

• •

  Then, among the 2NC individuals formed by parents and children takes place a struggle for survival in which only remain NC individuals for the new generation.

CHC also implements a form of heterogeneous recombination using HUX, a special recombination operator ³². HUX exchanges half of the bits that differ between parents, where the bit position to be exchanged is randomly determined. CHC also employs a method of incest prevention. Before applying HUX to the two parents, the Hamming distance between them is measured. Only those parents who differ from each other by some number of bits (mating threshold) are mated. The initial threshold is set at L/4, where L is the length of the chromosomes. If no offspring are inserted into the new population then the threshold is reduced by one.

CHC also performs a form of heterogeneous HUX recombination using a special operator recombination ³². HUX exchanged half the bits that differ between parents, where the bit position to exchange is determined randomly. CHC also employs a method of preventing incest. Before applying HUX to the both parents, the Hamming distance between them is measured. Only parents who are distinguished by some number of bits (mating threshold) are coupled. The initial threshold is stable at L / 4, where L is the length of the chromosomes. If no offspring are inserted into the new population then the threshold it decrements by one.

No mutation is applied during the recombination phase. Instead, when the population converges or the search stops making progress (i.e., the difference threshold has dropped to zero and no new offspring are being generated which are better than any member of the parent population) the population is reinitialized to introduce new diversity to the search. The chromosome representing the best solution found over the course of the search is used as a template to reseed the population. Reseeding of the population is accomplished by randomly changing 35% of the bits in the template chromosome to form each of the other NC – 1 new chromosomes in the population. The search is then resumed.

3.4. Representation and Fitness Function

Let S ⊆ HS be the subset of selected hyperrectangles that result from the run of a hyperrectangle selection algorithm. Hyperrectangle selection can be considered as a search problem to which EAs can be applied. We take into account two important issues: the specification of the representation of the solutions and the definition of the fitness function.

• •

  Representation: We use a binary representation, a chromosome consists of N genes (one from each hyperrectangle in HS) with two possible values: 0 and 1. If the gene is 1, the associated hyperrectangle is included in the subset represented by S. If this is 0, this is not included.

• •

  Fitness Function: Let S be a subset of hyperrectangles of HS and be coded by a chromosome. We define a fitness function based on the accuracy (classification rate) and the Non-Monotonic Index (NMI) evaluated over TR through the formula.

  (16)Fitness(S)=(1−λ)·(β·(α·clas_rat+(1−α)·perc_red)+(1−β)·cover)+λ·NMI_red.

  clas_rat means the percentage of correctly classified objects from TR using S. perc_red is defined as

  (17)perc_red=100·|HS|−|S||HS|·

  cover refers the total coverage of examples in TR in the subset of selected hyperrectangles or, in other words, the number of examples of TR whose distance value has been equal to 0 (examples covered by hyperrectangles in S).

  NMI_red is defined as

  (18)NMI_red=50*NMI_initial−NMI_currentNMI_inital

  where NMI_initial is the number of monotonic violations computed by the predictions made for all the rules derived from the training set and divided by the total number of pairs of examples. NMI_current is similarly computed to NMI_initial, but instead using the rules selected by the chromosome. NMI_red represents the relative reduction of NMI achieved by each chromosome and it is weighted by a constant factor of 50 due to the fact that this measure represents low values with respect to classification and reduction rates.

The objective of the EAs is to maximize the fitness function defined, i.e., maximize the classification rate and coverage while minimizing the number of hyperrectangles selected and the anti-monotonic index. Although the fitness function defined is focused on discarding single trivial hyperrectangles (points), exceptions could be present in special cases where points are necessary to achieve high rates of accuracy. Thus, the necessity of using single hyperrectangles or not will be determined by the tradeoff accuracy-coverage and will be conditioned by the problem tackled.

Regarding the parameters, we preserved the value of α = 0.5 as the best choice, due to the fact that it was analyzed in previous works related to instance selection ^33,34,35. We have conducted several experimental evaluations to estimate the best values of these parameters. For the sake of shortness, we determined that a suitable value for β should fall near 0.66 and the value for λ should be close to 0.25.

It is worth mentioning that our objective is to identify the best values of the parameters that configure the evolutionary approach in a general set up. It is true that for a specific classification problem, these values could be tuned in order to optimize the results achieved, but this may affect to other aspects, like efficiency or simplicity. General rules can be given about this topic:

• •

  The number of evaluations and population size are the main factors for yielding good results in accuracy and simplicity. The raise of these values has a negative effect on efficiency. In larger problems, it may be necessary to increase both values, but we will show in the experimental study that values of 10,000 and 50 work appropriately, respectively.

• •

  Parameters α and β allow us to obtain a desired trade-off between the accuracy and the number of hyperrectangles created. In the case of obtaining poor accuracy rates in a specific problem we have to increase α or decrease β. In contrary case, when the rules yielded are numerous and we are interested in producing simpler models, we have to increase β or decrease α. Besides, a large value of λ penalizes the maximization of the accuracy and minimization of the number of hyperrectangles in favor of the loss of anti-monotonic index.

Regarding to the specification of the classification conflicts, we employ the same mechanisms as shown in ²⁰. In short, they are:

• •

  If no hyperrectangle covers the example, the class of the nearest hyperrectangle defines the prediction.

• •

  If various hyperrectangles cover the example, the one with lowest volume is the chosen to predict the class, allowing exceptions within generalizations.

  Our approach computes the volume of a hyperrectangle in the following way:

  (19)VH=∏jmLj,

  where L_j is computed for each condition as

  (20)Lj={Hupper−Hlower if numeric and Hupper≠Hlower,1 if numeric and Hupper=Hlower,num. values selectedvi if nominal.

4.1. Experimental methodology

The elements included in the framework are the following:

• •

  Data sets: The study includes a total of 30 data sets, as a result of the joint selection of standard classification data sets (CLAS) whose class attribute is transformed into an ordinal attribute, assigning each category a number in such a way that the number of pairs of non-monotonic examples is minimized, and regression data sets (REGR) whose class attribute is discretized into 4 or 10 categorical values, keeping the class distribution balanced. Also, four classical ordinal classification data sets (ORD) are included in this study (era, esl, lev and swd) ¹. Their main characteristics are described in Table 1. They are classical data sets used in the classification scope and extracted from the UCI and KEEL repositories ^37,38. The run of the algorithms has been done following a 10-fold cross validation procedure (10-fcv).

  Table 1 shows the name of the data sets and their number of instances, variables and classes. In case of containing missing values, the total number of instances of the original data set appears in parenthesis. In this paper, these instances have been ignored.

• •

  Evaluation metrics:

  • •

    Accuracy (Acc), defined as the number of successful hits relative to the total number of classifications. It has been by far the most commonly used metric for assessing the performance of classifiers for years ³⁹.

  • •

    Mean Absolute Error (MAE), calculated as the sum of the absolute values of the errors and then dividing it by the number of classifications. The errors between the real label and the predicted label are estimated by the difference between the ordinal class values. Various studies conclude that MAE is one of the best performance metrics in ordered classification ⁴⁰.

  • •

    Monotonic Accuracy (MAcc), computed as standard Acc, but only considering those examples that completely fulfill the monotonicity constraints. In other words, non-monotonic comparable examples do not take part in the calculation of MAcc. The sense behind this is to simulate that future examples to be classified will check the monotonicity assumption. This metric serves as a manner of monotonicity level measurement of the predictions carried out. To address this, the process followed is presented in Figure 1 where the partitions used in 10-fcv are modified conserving the training data sets but removing the non-monotonic instances in the test data sets. We must point out that in the new validation data sets the test instances belong to the original data set, they are real instances, not artificial. In the same way for this new data sets obtained, we must highlight that the test data sets have been generated using different strategies than the noise removal filter or relabeling, searching to fair comparisons. The process presented in Figure 1 does not present any kind of randomness due to it is based in a deterministic greedy algorithm (see Algorithm 1).

  • •

    Monotonic Mean Absolute Error (MMAE), used to pursue the same goal of MAcc, but using MAE instead of Acc. Obviously, the data sets used in this case are the same than in the MAcc analysis.

  • •

    Non-Monotonicity Index (NMI) ⁴¹, defined as the number of clash-pairs divided by the total number of pairs of examples in the predictions made by an algorithm:

    (21)NMI=1n(n−1)∑x∈DNClash(x),

    where x is an example from the data set D. NClash(x) is the number of examples from D that do not meet the monotonicity restrictions (or clash) with x and n is the number of instances in D.

  • •

    Number of Rules (NRules), number of rules/hyperrectangles that compose the models produced by the algorithms.

• •

  Parameters configuration: See Table 2.

• •

  Statistical procedures: Several hypothesis testing procedures are considered to determine the most relevant differences found among the methods ³⁰. The use of non-parametric tests will be preferred to parametric ones, since the initial conditions that guarantee the reliability of the latter may not be satisfied. This could cause the statistical analysis to lose credibility. Friedman ranks test ³¹ is used to contrast the behavior of each algorithm. It highlights the significant differences between methods if they appear.

Figure 1:

Process of transformation the 10-fcv to the new one by removing the non-monotonic instances from the test data sets.

 function GreedyRemove(T - dataset)

   while NumberOfTotalCollisions(T)>0 do

     maxColis=0, instancSelec=0;

     for each instance i in T do

       Colis=NumberOfCollisionsProduced(i,T);

       if Colis>maxColis then

         maxColis=Colis, instancSelec=i;

       end if

     end for

     T = T - instancSelec;

   end while

   return T

 end function