IEEE Computational Intelligence Magazine - February 2021 - 87

of costs before using rescaling to im--
prove the classification -performance.
However, for many existing methods,
the cost matrices are often manually
designed and problem-specific. The misclassification costs in a cost matrix are
often given as precise values. Unfortunately, it is usually not easy for domain
experts to accurately specify or assign
the precise cost values to different kinds
of mistakes. Liu et al. [6] investigate how
cost intervals and cost distributions can
be used to develop cost-sensitive SVMs.
Nevertheless, the proposed methods still
require domain experts to specify cost
intervals or cost distributions in advance.
If no cost information is available, the
easiest method is to use class imbalance
ratio to construct a cost matrix [38].
However, this method is often criticized
because it is over-simplified without considering the data characteristics [38]. Gu
et al. [39] propose a bi-parameter space
partition algorithm to fit all solutions for
each cost parameter pair, and then k
invariant regions are superposed to one
for calculating the global optimal solutions for cost-sensitive SVM. In [7], [8], a
cost matrix is optimized for developing
cost-sensitive classifiers when the cost
information is completely unknown.
GP with cost-sensitive learning has
been investigated for unbalanced classification [40], [41]. However, the main
limitation of the existing cost-sensitive
methods is the requirement for manually designed cost matrices. When the cost
information is not available, it is worth
further investigating the use of cost-sensitive learning with GP. The main differences between the proposed method
and methods in [40], [41] are summarized as follows:
❏❏ The type of cost information. In [40]
and [41], the cost information is cost
values, while the proposed method
investigates the use of cost intervals
with GP to construct cost-sensitive
classifiers.
❏❏ The provision of cost matrices. The
proposed method does not require
cost matrices to be given by do--
main experts, and can learn them
-au--tomatically. However, in [40], a
cost matrix is given by d o m a i n

experts and is problem-specific, and
in [41], the class imbalance ratio is
used to build a cost matrix.
❏❏ The method of how the cost information is used by a GP classifier. The
proposed method incorporates cost
intervals into the classification process
of GP classifiers by a threshold-moving
idea. In [41], two cost-sensitive GP
methods have been proposed, one of
which incorporates cost values into a
fitness function while the other incorporates cost values into the classification process of GP classifiers by
adopting a three-way decision idea.
III. Preliminaries
A. Making Optimal Classification
Predictions Based on a Cost
Matrix in Cost-Sensitive Learning

The minority class Class 0 and the majority class Class 1 are seen as the positive
set and the negative set, respectively. A
class-dependent cost matrix is shown as
following [32]:
C 00 C 01
E
C_M = ;
C 10 C 11
where C 10 is a cost of a false negative, C 01
is a cost of a false positive, C 00 and C 11 are
the costs of a true positive and a true negative, respectively. In C_M, C 10 $ C 01,
C 10 2 C 00 and C 01 2 C 11 [32].
For instance x, P ^ j|x h is the probability of instance x belonging to class j,
the expected cost R ^x, i h is [32]:
	

R ^x, i h = / P ^ j|x h C ij (1)
j

where C ij is a misclassification cost of
predicting instance x into class i when
its true class label is j. If i = j, then the
prediction is correct; if i ! j, then the
prediction is incorrect.
Based on Eq. (1), the expected costs
of classifying instance x to Class 0 or
Class 1 are [32]:
R ^x, 0 h = P ^0|x h C 00 + P ^1|x h C 01
R ^x, 1 h = P ^0|x h C 10 + P ^1|x h C 11
Instance x is predicted to Class 1 if
and only if R ^x, 1h # R ^x, 0h . Given
P ^1|x h = p, P ^0|x h = 1 - p, R ^x, 1h #

R ^x, 0 h & ^1 - p h C 10 + pC 11 # ^1 - p h
C 00 + pC 01 & p $ ^^C 10 - C 00h / ^C 10 C 00 + C 01 - C 11hh. Therefore, if P ^1|x h $
^^ C 10 - C 00h / ^C 10 - C 00 + C 01 - C 11hh,
then x is classified into Class 1 [32].
A classification threshold, which is
used to separate two classes, is defined as:
	

TH c =

C 10 - C 00
(2)
C 10 - C 00 + C 01 - C 11

For the purpose of simplification,
C 00 and C 11 are assumed to be 0, indicating no misclassification cost caused
by the correct predictions. The cost of a
false positive C01 is set to be 1, and the
cost of a false negative C 10 is set to be C
^C $ 1 h [42]. In other words, the cost
of a false negative is C times the cost of
a false positive. Accordingly, Eq. (2) is
simplified to:
	

TH c =

C (3)
C +1

B. How GP is Used for Classification?

A GP tree is constructed by nodes from
a function set and a terminal set. A
function set provides the internal nodes
of GP trees, which is a set of operators
or functions, e.g., arithmetic operators
and mathematical functions. All the
possible arguments for the internal
nodes consist of a terminal set. For classification tasks, features of a dataset are
usually fed to GP as its terminals.
In Figure 1, we show a GP classifier,
where # and + are taken from a function set, while f 90, f 53, f 634 and f 4 (i.e.,
features) are taken from a terminal set.
This GP tree can be translated into an
arithmetic expression ^ f 90 # f 53h +
^ f 634 + f 4 h . When an instance is
input to this arithmetic expression, an
output value (i.e., ProgOut) is obtained.
If this value is greater than or equal to a
threshold TH, this instance is classified
into the minority class; otherwise it is
classified into the majority class.
IV. The Proposed Method

This section is devoted to introducing
the proposed method, called Intervalbased Cost-Sensitive Genetic Programming (ICS-GP).
For binary classification, a classification
threshold TH is often used to separate

FEBRUARY 2021 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE

87
IEEE Computational Intelligence Magazine - February 2021

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