IEEE Computational Intelligence Magazine - February 2021 - 88

the output values of a GP tree to predict the majority class and the minority
class. Usually, this classification threshold is set to be 0 to separate the original output values, or 0.5 if the output
values are converted into the range of
[0,1] [1]. However, this threshold setting method may not work effectively
in unbalanced classification. In costsensitive learning, the threshold-moving method is commonly used by
algorithms for unbalanced classification
[43]. The idea of the threshold-moving
method is straightforward, i.e., the classification threshold moves towards the
inexpensive instances with a lower misclassification cost, to enable expensive
instances with a higher cost to be easily
classified [43].
Figure 2 explains the thresholdmoving idea. In Figure 2, in Case 1,
when T H = 0.5 is used as a threshold,
two instances from the majority class
are mistakenly classified into the
minority class, while two -instances

-∞

The Majority Class

from the minority class are mistakenly
classified into the majority class. Note
that the two kinds of mistakes have different misclassification costs (i.e., the
cost of the minority class is greater
than or equal to that of the majority
class). After moving the classification
threshold towards the majority class,
like Case 2, two more instances from
the minority class can be correctly classified, contributing to the decreased
total cost. In cost-sensitive learning, the
classification threshold TH is calculated
based on the misclassification cost values, to ensure the minimum expected
cost of the classification predictions
[43]. In this paper, the proposed method adopts the threshold-moving idea,
based on class-dependent misclassification cost intervals.
A. Class-Dependent Misclassification
Cost Intervals

The class-dependent interval-based cost
matrix is given as:

TH

The Minority Class
ProgOut

+∞

+
×

f90

+

f53

f634

f4

Genetic Program: (f90×f53)+(f634+f4)
For instance x, if ProgOutx ≥ TH, then x is classified
into the minority class; otherwise it is classified into
the majority class.

The Majority Class

Case 1:
0

TH = 0.5

The Minority Class

1
The Majority Class

Case 2:
0

TH = ?

FIGURE 2 Threshold-moving idea.

88

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | FEBRUARY 2021

where CI 10 and CI 01 indicate cost intervals of a false negative and a false positive,
respectively. CI 00 and CI 11 indicate cost
intervals of a true positive and a true
negative, respectively.
In CI_M, we assume CI 00 = CI 11 = 0,
which indicates that no misclassification
cost is caused by the correct classification predictions. The cost of a false positive CI 01 is set to be 1, and the cost of a
false negative CI 10 is set to an interval
^C l, C uh ^C l $ 1 and C u $ 1 h . Then,
an interval-based cost matrix CI_M is
simplified to:
CI_M = ;

0
1
E
^ C l, C u h 0

where C l is the lower bound of CI 10 ,
while C u is the upper bound of CI 10 .
If no cost information is provided
by domain experts, the acquisition of a
cost matrix is still an open issue in
cost-sensitive learning [38]. Furthermore, a manually designed cost matrix
is often problem-specific. Therefore, it
is interesting and essential to investigate
how a cost matrix could be automatically obtained and used by the constructed classifiers.
Below, we will introduce the use of
strongly-typed genetic programming
(STGP) to automatically construct classifiers and learn cost intervals, i.e.,
^C l, C uh in CI_M.
B. Classifier Construction
and Cost Optimization

FIGURE 1 An example of a GP classifier.

The Minority Class

CI 00 CI 01
E
CI_M = ;
CI 10 CI 11

1

Different from the standard tree-based
GP, in STGP, every terminal has a data
type, and each function also has types for
its arguments and its returned values [9].
In a population, every individual cannot
violate the type constraints, so STGP
makes it possible to evolve the trees that
follow a pre-designed tree representation.
We use STGP to represent a GP tree,
where its left sub-tree is used to construct
a classifier, while its right sub-tree is used
for learning an optimal cost interval.
In the proposed method, the terminal set and the function set are reported
in Table 1.
IEEE Computational Intelligence Magazine - February 2021

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - February 2021
