# Feature construction using explanations of individual predictions

Boštjan Vouk<EMAIL_ADDRESS>Matej Guid<EMAIL_ADDRESS>Marko
Robnik-Šikonja<EMAIL_ADDRESS>University of Ljubljana, Faculty of
Computer and Information Science,
Večna pot 113, 1000 Ljubljana, Slovenia

(November 22, 2022)

###### Abstract

Feature construction can contribute to comprehensibility and performance of
machine learning models. Unfortunately, it usually requires exhaustive search
in the attribute space or time-consuming human involvement to generate
meaningful features. We propose a novel heuristic approach for reducing the
search space based on aggregation of instance-based explanations of predictive
models. The proposed Explainable Feature Construction (EFC) methodology
identifies groups of co-occurring attributes exposed by popular explanation
methods, such as IME and SHAP. We empirically show that reducing the search to
these groups significantly reduces the time of feature construction using
logical, relational, Cartesian, numerical, and threshold (num-of-N and X-of-N)
constructive operators. An analysis on 10 transparent synthetic datasets shows
that EFC effectively identifies informative groups of attributes and
constructs relevant features. Using 30 real-world classification datasets, we
show significant improvements in classification accuracy for several
classifiers and demonstrate the feasibility of the proposed feature
construction even for large datasets. Finally, EFC generated interpretable
features on a real-world problem from the financial industry, which were
confirmed by a domain expert.

###### keywords:

explainable artificial intelligence , prediction explanation , feature
construction

††journal: Engineering Applications of Artificial Intelligence

##  1 Introduction

Explainable artificial intelligence (XAI) is an important area of machine
learning (ML) (Tjoa and Guan, 2021) and is one of crucial elements for
deploying artificial intelligence (AI) models in practice due to its ability
to assure trust of users (Arrieta et al., 2020). The main goals of XAI are
trustworthiness, causality, transferability, informativeness, confidence,
fairness, accessibility, interactivity, and privacy awareness (Arrieta et al.,
2020). Many of these goals can be achieved by transparent prediction models.
The need for powerful explainable models is exacerbated by the lack of
interpretability of currently dominant complex prediction models, such as deep
neural networks and boosting.

The motivation for this work stems from the observation that practically no
current learning system incorporates constructive induction (CI). This might
be the consequence of computational complexity of the existing CI approaches.
We address these issues by proposing a novel approach to constructive
induction with a reduced search space and a lower computational time, by
implementing more constructive operators than existing methods, and by making
the system freely accessible.

The inherently interpretable predictive models, such as decision trees, naïve
Bayes and linear models, lack predictive power due to inadequate
representation of raw data. While this can be amended by construction of
composite features, a generation of new features is computationally
problematic due to a huge search space. To overcome this issue, we propose a
novel approach to constructive induction that uses popular explanation methods
to identify groups of potentially interacting attributes that could provide
useful constructs. Limiting the search for new features to the identified
groups results in much smaller sets of high-quality candidates.

The research in perturbation-based explanation methods has produced several
useful methods, such as IME (Štrumbelj and Kononenko, 2010), LIME (Ribeiro et
al., 2016), and SHAP (Lundberg and Lee, 2017b). These methods provide
explanation for individual predictions of black-box models as contributions of
attributes to the prediction of a given class label. We hypothesise that
groups of attributes frequently appearing together in these explanations
identify potentially useful attribute interactions – the possibility that has
not been exploited in the existing research.

Feature engineering (FE) transforms an input problem space by constructing new
features to be used in ML models. A better representation of the underlying
problem often leads to improvements in the learning performance (Ozdemir and
Susarla, 2018). FE is usually time consuming and may lead to overfitting. The
most typical FE methods are feature transformation, feature extraction,
feature construction, feature selection, and feature analysis. This research
focuses on feature construction. We aim for human-interpretable features that
could be used in intrinsically human-comprehensible models, such as decision
trees. Using better features, such models could offer better performance and
better interpretation.

In the proposed EFC (Explainable Feature Construction) system, we construct
various types of features: operator-based features (using logical, relational,
Cartesian, and numerical operators), features from rule learning (Hühn and
Hüllermeier, 2009), and features based on a threshold for the presence of
several features (frequently called num-of-N and X-of-N) (Zheng, 2000). We
evaluate the constructed features on a set of synthetic and real-world
datasets. To show practical utility of the EFC approach, we demonstrate its
use on a real-world problem from the financial domain with human evaluation.

The main contributions of the paper are as follows.

  1. 1.

A novel heuristic for reducing the search space of constructive induction. The
proposed EFC constructive induction system searches in a small space of co-
occurring explanations generated by the perturbation-based explanation
methods. This space consists of groups of potentially interacting attributes.
By applying this novel idea, we reduce the exponential search space of
constructive induction to the linear space of co-occuring features.

  2. 2.

A range of constructs. Using an efficient search in the reduced space, the EFC
system can generate more types of constructs (logical, relational, Cartesian,
numerical, and threshold features) as other existing systems. EFC is freely
available111https://github.com/bostjanv76/featConstr.

  3. 3.

The use case from the financial industry shows that generated features are
similar or identical to human-created features in this domain. This hints at
applicability of the EFC method as a standalone approach or to support humans
in the knowledge discovery process.

  4. 4.

An extensive empirical evaluation using synthetic and real-world UCI datasets
shows the effectiveness of the proposed approach. The gains are visible in
terms of computational speed, prediction performance, and comprehensibility.

The remainder of the paper is structured into five sections. In Section 2, we
present a systematic literature review. Section 3 describes the proposed
methodology, where we first provide an outline, which is followed by the
formal definition of the problem and description of the components. Section 4
presents the datasets used in the study (the synthetic, the UCI, and the real-
world dataset from the financial domain) as well as the evaluation scenarios.
Section 5 reports the results. We present conclusions, strengths and
limitations of the approach, as well as the ideas for further work in Section
6.

##  2 Background and related work

We review the related work in two subsections. In Section 2.1, we overview the
research on feature construction, roughly divided into standalone feature
construction, embedded feature construction, and work on feature interactions.
Section 2.2 outlines applications of explanation methods related to our work.
Each subsection is accompanied by a table, summarising the listed references.

###  2.1 Feature construction

Feature construction (FC) is a process in which new features are constructed
from raw data or previously constructed features to improve model robustness,
interpretability, and/or generalization (He et al., 2021). In the process of
FC, we use constructive operators and existing attributes/features. As a
result, we get features that may better describe the target concept (Matheus
and Rendell, 1989).

Machine learning research has produced several feature construction
approaches, such as FICUS (Markovitch and Rosenstein, 2002), FCTree (Fan et
al., 2010), FEADIS (Dor and Reich, 2012), and, more recently, automated
feature engineering methods, e.g., ExploreKit (Katz et al., 2016), Data
Science Machine (Kanter and Veeramachaneni, 2015), One Button Machine (Lam et
al., 2017), and Auto-Sklearn (Feurer et al., 2015). These techniques construct
new features that better describe target concepts. Consequently, new features
can improve classifiers’ performance and comprehensibility. The above-
mentioned methods are summarised in Table 1 and described below, divided into
three categories: standalone (operator-based) feature construction, methods
embedded into automated ML, and methods focused on feature interactions.

####  2.1.1 Standalone feature construction

Feature construction consists of the following four steps: 1) generating a set
of candidate features, 2) ranking candidate features, 3) evaluating and
selecting high-ranked features, and 4) adding promising features to the
dataset (Katz et al., 2016). Process of FC is mostly guided by human experts
and is not as efficient as automatic feature construction (AFC) (Fang et al.,
2020), which can be used in multiple domains and applications, while (manual)
FC is problem- or domain-specific (Dong and Liu, 2018).

Markovitch and Rosenstein (2002) presented the FICUS algorithm for feature
construction. The input of the framework is a set of original attributes and a
set of construction functions. This method extends past methods (CITRE
(Matheus and Rendell, 1989), FRINGE (Bagallo and Haussler, 1990), IB3-CI (Aha,
1991), LFC (Ragavan et al., 1993)) that use only a minimal set of logical
operators ($\neg,\land$) to construct Boolean features. FICUS uses
mathematical operators ($+,-,/,*,=,avg,max,min,absDi\\!f\\!f$), standard
logical operators ($\land,\vee$), special logical operators (occurrence
counting), and interval operators (range test). In FICUS, the feature space is
reduced by a heuristic measure based on information gain in a decision tree,
and other surrogate measures of performance. There are two potential drawbacks
of this method. First, feature subset selection does not take into account
feature interactions, and second, it is difficult to supply a set of operators
suitable for a given problem beforehand.

FCTree (Fan et al., 2010) uses decision trees to partition the data with
original attributes or constructed features as splitting criteria. FCTree
divides the training data recursively based on the information gain criterion,
and constructs new features randomly.

The FEADIS (Dor and Reich, 2012) algorithm relies on a combination of random
feature generation and feature selection. It greedily adds constructed
features to the training set, and therefore requires many computationally
expensive evaluations.

Duan et al. (2018) leverage Fourier analysis of Boolean functions. From the
input attributes, they first generate features in the disjunctive normal form
(DNF) using the RIPPER decision rule learner (Cohen, 1995) and then extract
the resulting Boolean features. Afterwards, they apply Fourier analysis to
extracted features in order to generate new parity features, which are ranked
in descending order according to the absolute values of Fourier coefficients.
The authors suggest selecting up to 30 top-ranked features for each domain.

Možina (2009) proposed an argument-based machine learning algorithm ABCN2 for
feature construction (requiring human experts). Argumentation is used to
construct new features, e.g., from the argument Credit = no because money_bank
$<$ monthly_payment $\cdot$ num-of_payments … a new feature enough_money can
be created by an expert, covering the explanatory part. ABCN2 does not
automatically generate suggestions for new features. ABCN2 was used in an
intelligent tutoring system (Woolf, 2010) to teach students arguing strategies
(Guid et al., 2019). The intelligent system by Xing et al. (2022b) uses
feature extraction in semi-supervised learning and self-distillation; a
similar feature extractor was used in the federated distillation learning
system (Xing et al., 2022a). The last two methods are specific to time-series
classification and do not use explicit constructive operators.

Zupan et al. (1998) proposed a data-driven constructive induction method
called HINT (Hierarchy INduction Tool). The method hierarchically constructs
new features. In each step, the method tests all possible combinations of
variables (attributes) up to the prespecified length and selects the one from
which the function that minimises the search space can be constructed. It
replaces these variables with a new, derived variable and iteratively
continues. The method can discover a hierarchy of concepts by iteratively
transforming attributes into new concepts. The method does not need
constructive operators, therefore it can be termed as data-driven operator-
free constructive inducer. However, the lack of operators reduces the
comprehensibility of the induced representation. Unfortunately, this complex
method is no longer available in the authors’ Orange data mining suite (Demšar
et al., 2013).

####  2.1.2 Embedded feature construction

To reduce the exploration time and to improve the performance, the process of
feature construction can be automated (Katz et al., 2016; Kanter and
Veeramachaneni, 2015; Lam et al., 2017; Feurer et al., 2015). The frameworks
reviewed below try to automatically construct useful and comprehensible
features from the original set of attributes.

There are two approaches to constructing features automatically; the expand-
reduce approach and the wrapper approach. ExploreKit (Katz et al., 2016), Deep
Feature Synthesis (Kanter and Veeramachaneni, 2015), One button machine (Lam
et al., 2017), and Auto-Sklearn (Feurer et al., 2015) use the expand-reduce
method, which first generates a vast number of features, then evaluates them,
and after that reduces their number. The wrapper approach uses a prediction
method wrapped within a greedy heuristic search (e.g., forward selection,
backward elimination, hill-climbing, best-first search) to select the optimal
feature subset.

ExploreKit generates new feature candidates by combining the original
attributes and retaining the most promising ones. From a single attribute, it
generates unary features with normalisation and discrimination operators,
e.g., discretisation of attributes into segments. New features can be
combinations of two features, e.g., arithmetic operations $(+,-,*,/)$, or
combinations of several features, e.g., operators GroupByThenMax,
GroupByThenMin, GroupByThenAvg, GroupByThenStdev, and GroupByThenCount. The
aim of the method is to maximise the predictive performance. First, the
candidate features are ranked by a classifier, and then the method iteratively
selects the features with the highest rank. The features that reduce the
classification error for more than a user-defined threshold are added to the
feature set. The ranking classifiers require additional training data to avoid
overfitting and may be computationally expensive to train.

Data Science Machine (DSM) automatically synthesises features from relational
normalised datasets. Features are built by stacking predefined basic
aggregation functions (e.g., max, min, avg) across relationships in the
datasets. Each feature has a certain depth $d$ (e.g., $d=1$:
tableX.attributeA; $d=2$: sum(tableX.attributeA); $d=3$:
avg(tableY.sum(tableX.attributeA))). The system performs feature selection and
model optimisation on the enlarged dataset. The weakness of the framework is
that it does not support learning from unstructured data such as texts, i.e.,
it cannot handle complex data structures and features. Besides, the use of
exhaustive feature enumeration and selection is time and memory consuming and
may lead to overfitting due to generation of all possible features.

An extension of DSM is One Button Machine (OneBM), which supports structured
and unstructured data. It expands the types of feature quantizations from DSM
and uses embeddings. OneBM uses propositionalization (Lachiche, 2010), which
is a two-step process. In the first step, relational data are transformed into
a single table, and in the second step, a propositional learning algorithm is
applied to the transformed data. Another extension of DSM was proposed by Lam
et al. (2019), who used Recurrent Neural Networks as the aggregation
functions.

In Auto-Sklearn feature construction is embedded in meta learning phase where
Bayesian optimisation is used to determine both the optimal combination of
relevant features and model hyper-parameters to minimise the classification
error. All datasets are represented by 38 meta-features which are extracted
from preprocessed data. Meta-features are based on simple dataset
characteristics (e.g., number of classes, number of attributes, number of
instances), information-theoretic properties (e.g., class entropy), and
statistical characteristics (e.g., data skewness).

Our approach uses some of the above-listed constructive operators, e.g.,
decision rules, logical, relational, numerical, and threshold operators.
Decision rules also cover basic aggregation operators and interval operators.
We do not use all of the above operators, as some of them (e.g., parity
operators) are specific for certain types of datasets and problems.

The feature construction process is usually not fully automated. First, an
exhaustive search of the entire feature space for a given problem is
practically infeasible as the number of possible feature subsets increases
exponentially with respect to the number of original attributes. Further, the
potential feature space can be even larger if new features can be constructed
iteratively or with many operators (Zhao et al., 2009). One way to reduce the
number of potential subsets in feature construction is to consider
interactions between attributes.

Table 1: A summary of covered feature construction (FC) methods and their
strengths and weaknesses. We use the following category labels: OB (operator-
based FC), eML (FC embedded into auto ML), TS (FC for time-series
classification), and INT (interactions). The abbreviations used in the table
are as follows: DT (decision trees), FSS (forward sequential selection), BSS
(backward sequential selection), and IG (information gain).

FC Method | Category | Weakness | Strength
---|---|---|---
FICUS (Markovitch and Rosenstein, 2002) | OB |  Must be supplied a set of suitable operators for a given problem. Feature evaluation does not take into account feature interactions. |  Generality and flexibility. Construction of comprehensible features.
CITRE (Matheus and Rendell, 1989) | OB |  Supports only a minimal set of logical operators. Only applicable for specific learning algorithms such as DT. Limited to binary classification problems. Uses rigid domain-knowledge filtering. |  Comprehensibility.
FRINGE (Bagallo and Haussler, 1990) | OB |  Supports only a minimal set of logical operators. Only applicable for specific learning algorithms such as DT. Limited to binary classification problems. Tested only on synthetic datasets. |  Comprehensibility (reducing a tree size). Increased predictive accuracy.
IB3-CI (Aha, 1991) | OB |  Supports only a minimal set of logical operators. Sensitive to noise. |  Well adapted to board game problems. Uses domain knowledge to reach high generalization rate.
LFC (Ragavan et al., 1993) | OB |  Supports only a minimal set of logical operators. Generates a large set of attributes. |  Construction is heuristically guided by IG measure.
FCTree (Fan et al., 2010) | OB |  Not capable of composing transformations, i.e. it searches in a small space. |  Uses information-theoretic criteria to guide the search. Creates new features during the tree construction. The number of selected features is bounded.
FEADIS (Dor and Reich, 2012) | OB |  Requires many computationally expensive evaluations. Greedily adds constructed features. Dimensionality before feature selection can become huge. |  Flexibility, extendability, and simplicity. Requires no tuning parameters.
Duan (Duan et al., 2018) | OB |  Uses only parity features. |  Naive heuristic for selecting top-ranked features.
ABCN2 (Možina, 2009) | OB |  Suggestions for new features are not generated automatically and require a domain expert. |  Experts’ arguments reduce the search space. System automatically detects important examples and counter-examples.
HINT (Zupan et al., 1998) | OB |  A lack of constructive operators and comprehensibility. |  Identifies and eliminates redundant subsets of attributes.
ExploreKit (Katz et al., 2016) | eML |  Time and memory consuming. Prone to overfitting. Unable to infer domain knowledge. Issues of trust. Iterative algorithm is difficult to parallelise. |  Outperforms the IG-based methods both in ranking-only and ranking-and-evaluation settings. Robustness. More scalable than grid search.
DSM (Kanter and Veeramachaneni, 2015) | eML |  Time and memory consuming. Prone to overfitting. Unable to infer domain knowledge. Issues of trust. Does not support learning from unstructured data. |  Exploits structural relationships inherent in database design.
OneBM (Lam et al., 2017) | eML |  Time and memory consuming. Prone to overfitting. Unable to infer domain knowledge. Issues of trust. Uses a relatively restrictive bias. Suffers from performance and scalability bottleneck. |  Able to extract distinguishing features from relational databases. Scalability.
Auto-Sklearn (Feurer et al., 2015) | eML |  Time and memory consuming. Prone to overfitting. Inability to infer domain knowledge. Issues of trust. Acting as a black box. Weak models can remain in the ensemble. |  Optimizes hyperparameters. Meta-learning and ensemble building.
ResNet–LSTMaN (Xing et al., 2022b) | TS |  Works only on time series. |  Robustness.
EFDLS (Xing et al., 2022a) | TS |  Works only on time series. |  Multi-task time-series classification.
SNB (Kononenko, 1991) | INT |  Requires multiple iterations. |  Joins dependent attributes based on the Chebyshev theorem.
Pazzani (Pazzani, 1996) | INT |  Requires multiple iterations. |  Finds dependencies between the attributes with FSS, BSS, elimination, and joining.
Jakulin (Jakulin, 2005) | INT |  Uses greedy attribute selection. Only tested on synthetic domains. |  Heuristically detects attribute interactions.
IME (Štrumbelj et al., 2009) | INT |  Slow for large datasets. Interactions are not explicitly identified. Dependent on a prediction model. |  Graphical visualisation. Linear time complexity.
ASTRID (Henelius et al., 2017) | INT |  Computationally demanding. Only suitable for classification problems. |  Identifies interacting attributes. Can be applied to any model.

####  2.1.3 Feature interactions

Feature interaction refers to a situation where certain features are not
individually related to the target concept, unless they are in some way
combined with other features. To avoid construction of meaningless features,
methods search for possibly co-occurring attributes before the feature
construction process.

Jakulin and Bratko (2003b) defined feature interaction as the amount of
information that is common to all the random variables but not present in any
of them. According to this definition, the interaction information can be
negative, because the dependency among a set of variables can increase or
decrease with the knowledge of a new variable. Štrumbelj et al. (2009)
proposed interactions-based explanation method and defined feature-interaction
contributions as the contribution of interactions between subsets of
attributes to the model’s decision. Henelius et al. (2017) proposed the ASTRID
method, which interprets classifiers by detecting attribute interactions. The
main idea of the method is to examine attribute interactions for better
interpretation of the model’s predictions. The method searches for such
partitions of attributes into subsets that do not significantly decrease the
classifier’s accuracy (using certain subsets). This process may identify
interacting attributes. A drawback of the method is that it is computationally
demanding.

To improve prediction performance of naive Bayesian algorithm, Pazzani (1996)
and Kononenko (1991) used attribute interaction information to guide feature
construction. Both authors considered joining more than two attributes, but
this required multiple iterations.

Jakulin (2005) used interaction information to construct new features. He
proposed the following exhaustive methodology: 1) estimate interaction
information from all pairs of attributes, 2) select attribute pairs with the
highest interaction information, 3) use each previously selected pair and
construct new features.

Our approach differs from the above mentioned methods in the way we identify
possible interactions between attributes. We count attribute co-occurrence in
explanations of model predictions. We assume that used complex black-box
models (e.g., boosting) have captured some interactions between attributes and
that this information is reflected in explanations. The groups of co-occurring
attributes in explanations therefore potentially identify attribute
interactions. The reduction of search to these groups significantly reduces
the search space of constructive induction.

###  2.2 Applications of explanation methods

While simple predictive models are self-explanatory, complex models (including
decision trees or linear models) are beyond human comprehension. However,
simple models are often less accurate than complex ones. In order to trust
predictions of complex models, it is important to verify them with explanation
methods. These methods often use interpretable (local) approximations of the
original complex model. If a user can unravel inner workings of a black-box
model, its decisions are more trustworthy (Bohanec et al., 2017; Molnar,
2021).

Explanation methods can be classified into two groups. The first group
includes model-agnostic methods like SRV (Shapley Regression Values)
(Lipovetsky and Conklin, 2001), EXPLAIN (Robnik-Šikonja and Kononenko, 2008),
IME (Štrumbelj et al., 2009), LIME (Ribeiro et al., 2016), QII (Datta et al.,
2016), and SHAP (SHapley Additive exPlanations) (Lundberg and Lee, 2017b). The
second group consists of model-specific methods, such as interpreting random
forests (Saabas, 2014), Layer-wise Relevance Propagation (LRP) (Bach et al.,
2015), DeepLIFT (Shrikumar et al., 2017), and GAM (Ibrahim et al., 2019). Many
model-agnostic methods are based on game theory (SRV, QII, IME, LIME, and
SHAP). Bodria et al. (2021) present a recent survey of explanation methods.

Although the proposed EFC method is independent of a particular explanation
method we use IME (Štrumbelj and Kononenko, 2014) and SHAP (Lundberg and Lee,
2017b) in this study to identify groups of possible interacting attributes.
This is a novel use of explanation methods. Below we outline other
applications of explanation methods and summarise them in Table 2.

Table 2: Applications of explanation methods. The type label denotes either a model-specific (specific) or a model-agnostic (agnostic) approach. Explanation Method |  Type |  Applications
---|---|---
SRV (Lipovetsky and Conklin, 2001) |  agnostic |  telecommunications industry
EXPLAIN (Robnik-Šikonja and Kononenko, 2008) |  agnostic |  medicine, economics, electrical industry, airline industry, text categorisation problems
Lemaire’s method (Lemaire et al., 2008) |  agnostic |  telecommunications industry
IME (Štrumbelj et al., 2009) |  agnostic |  medicine, economics, electrical industry, airline industry, text categorisation problems
LIME (Ribeiro et al., 2016) |  agnostic |  text, image and tabular classification problems
QII (Datta et al., 2016) |  agnostic |  socioeconomics
SHAP (Lundberg and Lee, 2017b) |  agnostic |  medicine, economics, sports, aviation industry, software industry
Saabas’s method (Saabas, 2014) |  specific |  real estate industry
LRP (Bach et al., 2015) |  specific |  image classification problems
DeepLIFT (Shrikumar et al., 2017) |  specific |  biological problems
Arras’s method (Arras et al., 2017) |  specific |  text categorisation problems
GAM (Ibrahim et al., 2019) |  specific |  economics
RUDDER (Arjona-Medina et al., 2019) |  specific |  game industry

We first focus on perturbation-based methods. The SHAP method has been used in
the system called Prescience that deals with anesthesia safety (Lundberg et
al., 2018) and to calculate mortality risk factors in the general US
population. Lundberg et al. (2020) report several applications of the SHAP
method. It has been used to optimise performance in sports (NBA team Portland
Trail Blazers); Microsoft uses the method in its Cloud Pipeline; Cleveland
clinic uses SHAP to identify different subtypes of cancers; it has been used
for optimising manufacturing process for a jet engine at Rolls Royce where
they build complicated models and try to figure out what is breaking and why.
Bank of England uses SHAP values to improve collaboration between humans and
machines for decision-making and for financial risk prediction. Recently, SHAP
has been used in the Driverless AI commercial package (Hall et al., 2021). The
package also contains other explanatory methods, such as K-LIME.

The IME method has been initially applied to real-world medical problems
(Štrumbelj et al., 2010). We can find applications of IME in economics, more
precisely, in the context of B2B sales forecasting, where explanations are
used to validate and test user hypotheses. Besides the IME method, Bohanec et
al. (2017) also used the EXPLAIN method. Lemaire et al. (2008) applied
explanations in the telecommunications industry. Authors used instance level
explanations for immediate decisions in a customer relationship management
system.

Applicability of explanation methods is not limited to interpretability of
black-box models, but can be used for other tasks (e.g., feature selection and
stream mining). Štrumbelj et al. (2009) proposed to use the IME explanation
method as a filter method for feature selection. Explanation method proposed
by Lundberg and Lee (2017b) can also be used to calculate feature importance.
The EXPLAIN and IME explanation methods were used to explain a concept drift
in an incremental model for predicting flight delays and for predicting
changes of electricity prices (Demšar and Bosnić, 2018). Arjona-Medina et al.
(2019) used explanation in reinforcement learning, while Arras et al. (2017)
used explanations of word features to build a representation of a document.

To the best of our knowledge, no previous work has used explanation
methodology to identify groups of co-occurring attributes that could
constitute feature interactions. Additionally, we are not aware of any
application in the financial industry.

##  3 Methodology

We propose a methodology for efficient feature construction based on
explanation of individual predictions. Our aim is to construct human-
comprehensible features that will improve interpretability of ML models and
their prediction performance.

The proposed methodology consist of the following four steps illustrated in
Figure 1:

  1. 1.

Explanation of model predictions for individual instances, which is described
in Section 3.1.

  2. 2.

Identification of groups of attributes that commonly appear together in
explanations, which is presented in Section 3.2.

  3. 3.

Efficient creation of constructs from the identified groups, which is
described in Section 3.3.

  4. 4.

Evaluation of constructs and selection of the best as new features, which is
presented in Section 3.4.

Below, we first present the notation. After we outline the methodology in
Sections 3.1 \- 3.4, we analyse its computational complexity in Section 3.5
and give details of the implementation in 3.6. A worked example of the
methodology is demonstrated in Section 3.7. The evaluation scenario is
described in Section 4 and the results are presented in Section 5.

Figure 1: Illustration of the proposed EFC methodology.

We use the following notation. We assume two sets of instances, training and
explanation. Let $I^{t}=(X^{n\times m},Y^{1\times n})$ be the training data,
where $X^{n\times m}$ is an instance space of $n$ training instances and $m$
attributes. $Y^{1\times n}$ is a label space (vector of class label). We
denote the prediction model as $M$ and the class to explain as $c$ where
$c\in\\{1\dots C\\}$. In this work, if not stated otherwise, we explain the
minority class, which is frequently of more interest, e.g., in financial fraud
(Albashrawi, 2016). Let $I^{e}=(X^{e\times m},Y^{1\times e})$ be the data we
use for explanations (typically, this would be the training set or a part of
the training set consistent with $e$ instances). Let $E^{e\times m}$ be the
matrix of explanations obtained with the given explanation method from
prediction model $M$ using the explanation instances $I^{e}$. $E_{i}$ is an
explanation of individual instance $i$, and $E_{ij}$ is an estimated
contribution of attribute $j$ to the prediction of instance $i$ into class
$c$.

###  3.1 Generation of instance explanations

In Step 1 of EFC methodology (see Figure 1), we generate explanations $E$
based on the prediction model $M$ and explanation instances $I^{e}$. While we
can use any prediction model, we recommend using robust well-performing models
such as random forests or XGBoost. Namely, if the prediction model is wrong,
the produced explanations and constructs that exploit its information will
suffer and produce suboptimal results. In the next step, these explanations
are used to find the groups of attributes that often co-occur in explanations,
i.e., the candidate interactions. To produce explanations, we use any of the
before-mentioned instance explanation techniques. In this work, we work with
two state-of-the-art-methods, SHAP (Lundberg and Lee, 2017b), and IME
(Štrumbelj et al., 2009). The explanation methods return a vector of
explanations $E_{i}$ for each of the instances $i$. The dimension of
explanation vectors is equal to the number of attributes $m$. Each dimension
of the explanation vector represents an estimated contribution of one
attribute to the prediction of the instance into the selected class $c$. We
illustrate these explanations later, in Figure 3. The value of $E_{ij}$
represents the estimated contribution of attribute $j$ to the prediction of
instance $i$.

###  3.2 Identification of co-occurring attributes

In Step 2 (see Figure 1), we take the matrix of instance explanations $E$,
identify commonly co-occurring groups of attributes, and treat them as
possible interactions which could be expressed with constructs. The absolute
value of $E_{ij}$ represents the amplitude of the impact of attribute $j$ to
the classification of instance $i$ with model $M$. Each instance $i$ typically
has only a few large explanation values (either positive or negative), others
being close to zero. If the prediction model detects any interactions between
the attributes, the components of the interactions are expressed as large
explanation values in those instances where the interactions affect the
predictions. Large co-occurring explanation values might also be the result of
strongly correlated independent (non-interacting) attributes, so frequent co-
occurrence of attributes serves only as a heuristic guideline which attributes
to probe together in constructive induction. This intuition is the key to our
approach.

In the rows (representing instances) of matrix $E$, we search for commonly co-
occurring groups of large values (indicating possibly interacting attributes)
and take them as candidates for components of new features. In this way,
instead of using the huge space of the original attributes, the search for
useful constructs is conducted in the much smaller and more informative space
of co-occurring explanations. The search procedure is summarised in Figure 2.
The absolute values of explanations $E_{i}$ (for each instance) are normalised
to 1 and sorted in descending order (i.e., by decreasing impact on the
prediction). They are summed in that order and when they exceed a threshold
(parameter $thr$), we mark those that are part of the sum as important and the
rest as unimportant. For each threshold (from the lower bound $thr_{l}$ to the
upper bound $thr_{u}$ by the step $step$), we generate candidate feature
subsets and concatenate them. Due to potential noise in the prediction models
and explanation procedures, we might also collect a few false candidates.

Figure 2: Search of frequently co-occurring explanations.

The output of Step 2 is a collection of frequently co-occurring groups of
attributes stored in such a way that duplicates are avoided.

###  3.3 Efficient feature construction

In Step 3 of the EFC methodology (illustrated in Figure 1), we construct
several types of features, using individual groups of frequently co-occurring
attributes to reduce search space, thereby significantly reducing the
computational complexity of constructive induction in practical and
theoretical terms (see Section 3.5). The actual number of constructed features
depends on the prediction model used in explanations, the number and size of
the co-occurring groups of attributes, the depth of the construction, and the
number of operators. For logical features, generated from numerical
attributes, the number of discretisation intervals must be also taken into
account. We generate several types of features, e.g., operator-based features
(e.g., logical, relational, Cartesian, and numerical operators), features from
decision rule algorithms (we use the FURIA decision rule learner (Hühn and
Hüllermeier, 2009)), and threshold features (X-of-N, all-of-N, M-of-N, and
num-of-N (Zheng, 2000)). X-of-N construct is true if $X$ of $N$ specified
conditions are true, and all-of-N is true if all the argument conditions are
true. M-of-N is true if at least $M$ out of $N$ specified conditions are true.
Finally, num-of-N counts the number of true conditions and returns their
number.

In this way, we build an explicit and potentially more comprehensible
representation in the space of original attributes. The output of this step is
the set of constructed features, which is evaluated and reduced in the next
step.

###  3.4 Evaluation and selection of new features

In Step 4 (see the Figure 1), we evaluate the features constructed in the
previous step and select the most relevant ones. We evaluate features in the
original feature space using the MDL feature evaluation measure (Kononenko,
1995), which has a number of favourable properties compared to other impurity-
based measures (such as better-known gain ratio (Quinlan, 1986)), e.g., better
behaviour in multi-class scenario and fairer treatment of multi-valued
attributes. The reason to use impurity-based measure instead of ReliefF
measure (Robnik-Šikonja, 2003), which can detect conditionally interacting
features is that successful feature construction should generate features that
are directly related to the class and detectable with impurity-based measures.

Note that Figure 1 shows explanations and creation of new features based on
binary-class predictions focusing on the positive class. For multi-class
problems, it might be sensible to repeat the process for all class values and
harvest more constructs. We leave this exploration for further work.

###  3.5 Computational complexity

The computational complexity of EFC methodology consists of four parts:
generation of instance explanations, identification of groups of co-occurring
attributes in explanations, feature construction, and feature evaluation.

The time to generate instance explanations consists of two parts: the
construction of the prediction model and generation of explanations with the
explanation method (i.e., with IME or SHAP). We skip the analysis of the
prediction model complexity, which depends on the machine learning algorithm
used, e.g., for support vector machines it is between $\mathcal{O}(n^{2})$ and
$\mathcal{O}(n^{3})$ (Chapelle, 2007), for random forest $\mathcal{O}(m\cdot
n\cdot\log{(n)}\cdot k)$ (Hassine et al., 2019), for XGBoost
$\mathcal{O}(k\cdot d_{t}\cdot n^{\prime}\cdot\log{(n)})$ (Chen and Guestrin,
2016); here $k$ is number of trees, $n^{\prime}$ number of non-missing entries
in the training data, and $d_{t}$ the maximum depth of the tree.

In other analyses, we use the following notation. Let $n_{e}$ denotes the
number of explaining instances, $n_{t}$ the number of instances in the
training dataset, $g_{n}$ the number of groups of attributes for feature
construction, $g_{m}$ the number of attributes in the groups, $d_{f}$ the
depth of the construction, $op_{n}$ the number of operators, and $l_{max}$ the
maximum number of leaves in any tree.

The computational complexity of explanation methods (e.g., SHAP and IME) that
generate instance explanations is linear in the number of explained instances.
The computational complexity of computing SHAP values for $n_{e}$ instances
with boosting trees is $\mathcal{O}(n_{e}\cdot k\cdot l_{max}\cdot d_{t}^{2})$
(Lundberg and Lee, 2017a). In practice, $k$, $d_{t}$ and $l_{max}$
($l_{max}=2^{d_{t}}$) are constants; in this case we use $k=100$ and
$d_{t}=3$, which results in $\mathcal{O}(n_{e})$. For IME, the computational
complexity of generating explanations is likewise linear in the number of
explained instances and attributes $\mathcal{O}(n_{e}\cdot m)$ (Štrumbelj and
Kononenko, 2010).

The computational complexity for identifying groups of co-occurring attributes
in explanations is $\mathcal{O}(n_{e}\cdot m)$, and for constructing features
is $\mathcal{O}(g_{n}\cdot g_{m}^{d_{f}}\cdot op_{n})$, where we use
$max(d_{f})=3$. The evaluation part is bounded by $\mathcal{O}(n_{t}\cdot
g_{n}\cdot g_{m}^{d_{f}}\cdot op_{n}$). If we omit the computational
complexity of building the prediction model for explanations, the total
computational complexity of the EFC methodology is $\mathcal{O}(n_{e}\cdot
m+n_{e}\cdot m+g_{n}\cdot g_{m}^{d_{f}}\cdot op_{n}+n_{t}\cdot g_{n}\cdot
g_{m}^{d_{f}}\cdot op_{n})$. For all practical purposes $g_{n}\cdot
g_{m}^{d_{f}}\cdot op_{n}$ is constant (see distributions of these quantities
for a large collection of UCI datasets in Figure 9). The computational
complexity is therefore linear in the number of explanation instances and
attributes $\mathcal{O}(n_{e}\cdot m+n_{t})$.

###  3.6 Implementation of the proposed approach

In this section, we elaborate on the proposed methodology outlined above by
presenting the pseudo code of individual steps.

The main flow of the proposed approach is shown in Algorithm 1. The input
parameters are the explanation instances $I^{e}$, the training instances
$I^{t}$, the prediction model $M$, the class to explain $c$, the lower and
upper weight thresholds ($thr_{l}$, $thr_{u}$) with the step $step$, and the
noise threshold $noiseThr$. For each explanation threshold $q$, the algorithm
generates a group of candidate attributes $G_{temp}$ from the matrix of
explanations $E$ and then constructs a set of features $F$ from the set of
candidates $G$. The output of the algorithm is the set of constructed features
$F$.

The components of the EFC method are located as follows. Algorithm 2 shows
generation of instance explanations. Algorithm 3 and Algorithm 4 describe the
detection of the most frequently co-occurring groups of attributes in the
explanations. A set of features is generated from each group with Algorithms 5
and 6 and then evaluated.

Algorithm 1 EFC: Explanation-based Feature Construction

Explanation instances $I^{e}=(X^{e\times m},Y^{1\times e})$

Input:Training instances $I^{t}=(X^{n\times m},Y^{1\times n})$

Input:Prediction model $M$

Input:Class value to explain $c\in\\{1..C\\}$

Input:Explanation method $P$

Input:Weight threshold $thr_{l}$, $thr_{u}$, $step$ $\triangleright$
$0<thr_{l}<thr_{u}\leq 1$, $0<step<1$

Input:Noise threshold $noiseThr$$\triangleright$ Expected percentage of noise
in the target class.

Constructed features $F$

$G\leftarrow\\{\\}$$\triangleright$ set of candidate groups

$E\leftarrow$ getExplanations$(I^{e},M,c,P)$$\triangleright$ using Alg. 2

for $q\leftarrow thr_{l}$ to $thr_{u}$ by $step$ do$\triangleright$ defaults:
$thr_{l}=0.4$, $thr_{u}=0.8$, $step=0.1$

$W^{e\times m}\leftarrow$ setWeights$(E,q)$$\triangleright$ using Alg. 3

$G_{temp}\leftarrow$ getMostFqSubsets$(W,noiseThr)$$\triangleright$ using Alg.
4

$G\leftarrow G\cup G_{temp}$$\triangleright$ Using LinkedHashSet to avoid
duplicates

end for

$F\leftarrow$ constructFeatures$(X^{n\times m},G,c)$$\triangleright$ using
Alg. 5

evaluate$(F,X^{n\times m})$$\triangleright$ Evaluate features and keep only
useful ones

return $F$

Algorithm 2 explains each individual instance with an explanation method
(e.g., SHAP or IME) and returns the matrix of explanations $E$. The algorithm
inputs are the explanation instances $I^{e}$, the pre-trained model $M$, the
explanation method P, and the class to explain $c$. The output is the matrix
of instance explanations $E$.

Algorithm 2 Get explanations for one class

Explanation instances $I^{e}=(X^{e\times m},Y^{1\times e})$, Model $M$

Input:Class to explain $c$, Explanation method $P$

Explanations $E$

for all $x_{i}\in X$ do

$E_{i}\leftarrow$ explain$(x_{i},M,c,P)$

end for

Algorithm 3 selects groups of candidate interactions by setting their weights
to 1 and zeroing all the others. The input parameters are the matrix of
explanations $E$ and the explanation threshold $q$. The output of the
algorithm is the matrix of weights $W$ initialised to all zeros. The sum of
normalised explanations is:

$s_{j}=\sum_{j=1\atop a[o[j]]<q}^{m}a[o[j]]$ (1)

where $a$ is the vector of normalised explanations, $o$ the vector of indexes
and $q$ the weight threshold. The algorithm first normalises the absolute
values of explanations for each instance and then orders them in descending
order. The normalised values are summed (the highest values are taken first)
in $s_{j}$, see Equation 1, until the threshold value $q$ is exceeded. When
the normalised value of attribute is added to $s_{j}$, the weight of that
attribute is set to 1 in the weight vector $w_{i}$.

Algorithm 3 Select largest explanations

Explanations $E^{e\times m}$, Importance threshold $q$ Input:

$W^{e\times m}$ $\triangleright$ matrix of important explanations

$E\leftarrow|E|$ $\triangleright$ get absolute values of explanation scores

$W\leftarrow 0$ $\triangleright$ initialise all values to zero

for all $e_{i}\in E$ do $\triangleright$ for all instances $E_{i}$; $i=1..e$

$a\leftarrow||e_{i}||$$\triangleright$ normalise sum of explanations to 1

$o\leftarrow$ order$(a)$$\triangleright$ get descending order of explanations

$thrTmp\leftarrow 0$

for $j\leftarrow 1$ to $m$ do

if $thrTmp<q$ then

$thrTmp\mathrel{+}=a[o[j]]$$\triangleright$ add next biggest explanation

$W_{i,o[j]}\leftarrow 1$$\triangleright$ this explanation is above threshold

else

break $\triangleright$ When the sum of the normalised explanations exceeds the
threshold.

end if

end for

end for

return $W$

In Algorithm 4, we first generate sets of candidate groups $G^{e}$ from the
matrix $W$, and calculate the frequency of subsets taking into account all
possible subsets of given $G_{i}$. The subsets with frequency below the noise
threshold $noiseThr$ and subsets with only one attribute are removed. The
input parameters are the matrix of important explanations $W$ and the noise
threshold $noiseThr$ that determines the amount of required empirical support
for candidate groups, i.e. the minimal required frequency to accept
interaction as important. The output of the algorithm is a set of the most
common co-occurring subsets of attributes $U$ from the matrix $W$.

Algorithm 4 Get most frequent subsets

Matrix of important explanations $W^{e\times m}$, Noise threshold $noiseThr$

Set $U$$\triangleright$ set of interaction candidates

$G^{e}\leftarrow\\{\\}$ $\triangleright$ set of candidate interactions, one
for each instance

for all $w_{i}\in W$ do$\triangleright$ important explanation indicators for
instance i

for $j\leftarrow 1$ to $m$ do$\triangleright$ for all attributes

if $w_{i,j}=1$ then $\triangleright$ explanation above threshold

$G_{i}\leftarrow G_{i}\cup j$$\triangleright$ add to the set of candidate
interactions for explanation i

end if

end for

end for

$Q$ $\leftarrow$ frequencyMap$(G)$ $\triangleright$ get frequency of subsets

sortDesc$(Q)$$\triangleright$ sort by frequency of subsets

$U\leftarrow$ remove$(Q$, noiseThr) $\triangleright$ remove subsets below the
noise threshold and subsets with only one attribute

return $U$

The Algorithm 5 describes feature construction. The input parameters are the
training instances $I^{t}$, the collection of the most frequent candidate
interactions $U$, the class to explain $c$, the percentage of covered
instances $pci$, the threshold for certainty factor $cf$, the types of
features $R$, and the set of operators $O$. The algorithm constructs operator-
based features (using logical, relational, Cartesian, and numerical
operators), features from the FURIA decision rule learning algorithm (Hühn and
Hüllermeier, 2009), and threshold features using a threshold for presence of
several other features (e.g., num-of-N and X-of-N constructs). Algorithm 5
first generates operator-based features with Algorithm 6 and merges them with
features from FURIA. The merged set is used in the construction of threshold
features. Each constructed feature is tested for sufficient coverage. When the
number of covered instances reaches the threshold ($pci\times n_{c}$), feature
construction is stopped. The output of the algorithm is the set of constructed
features $S$.

Algorithm 5 Generate features  $\triangleright$ all types of features

Instances $I^{t}=(X^{n\times m},Y^{1\times n})$, Collection of the most
frequent candidate interactions $U$, Class to explain $c$, Percentage of
covered instances $pci$, Threshold for certainty factor $cf$, Types of
features $R$, Set of operators $O$

Set of features $S$

$S\leftarrow\\{\\}$

$F\leftarrow\\{\\}$ $\triangleright$ temporary features

for all $r_{i}\in R$ do $\triangleright$ construct different types of
features, using different operators

$S\leftarrow$ generateOperatorBasedFeatures($r_{i},op_{i}$) $\triangleright$
using Alg. 6

end for

for $i\leftarrow 1$ to $|U|$ do $\triangleright$ for all groups of frequently
interacting features

$F\leftarrow$ construct features from $U_{i}$ $\triangleright$ using Furia and
$cf$

for all $\phi_{i}\in F$ do$\triangleright$ interval and values using
$\land,\lor$

if $\phi_{i}\notin S$ then

$S\leftarrow S\cup\phi_{i}$$\triangleright$ add $\phi_{i}$ to $S$

remove instances covered by $\phi_{i}$ from $X$ where $Y=c$

end if

if $\phi_{i}$ contains $\land$ then

$args\leftarrow$ split($\phi_{i},\land$) $\triangleright$ array of
arguments/conditions

$S\leftarrow S$ $\cup$ createThresholdFeature($args$) $\triangleright$ num-
of-N

end if

end for

if # covered instances $\geq pci\times n_{c}$ then $\triangleright$ sufficient
amount of covered instances

break

end if

end for

return $S$

In Algorithm 6, we create different types of operator-based features using,
e.g., logical, relational, Cartesian, and numerical operators. Each d-element
subset of attributes is used for feature construction with operators $op$. For
logical $\lor$ and $\land$ we use d=3, for other logical operators and other
types of features we use d=2. Constructed features are added to $S$ if not
already present. The input parameters are the training instances $I^{t}$, the
collection of the most frequent candidate interactions $U$, the depth of
feature $d$, and the set of the operators $O$ for the chosen type of features.
The output of the algorithm is the set of operator-based features $S$.

Algorithm 6 Construct operator-based features

Instances $I^{t}=(X^{n\times m},Y^{1\times n})$

Input:Set $U$ $\triangleright$ set of candidate groups

Input:Depth of feature $d$$\triangleright$ e.g., d=2, $A_{1}\lor A_{2}$; d=3,
$A_{1}\lor A_{2}\lor A_{3}$

Input:Type of feature $r$$\triangleright$ e.g., logical operators, relational,
Cartesian, numerical

Input:Set $O$$\triangleright$ set of operators for the chosen type of features

Set of features $S$

$V\leftarrow\\{\\}$$\triangleright$ set of d-element subsets of attributes

for $i\leftarrow 1$ to $|U|$ do$\triangleright$ for all groups of interacting
attributes

$V\leftarrow$ generate d-element subsets from $U_{i}$

for all $v\in V$ do

for all $op\in O$ do

$\phi\leftarrow$ generateFeature($v,op,r$)

$S\leftarrow S\cup\phi$

end for

end for

end for

return $S$

###  3.7 A worked example

To illustrate the proposed methodology, we execute the steps in Figure 1 using
a toy dataset that consists of 6 binary attributes $A_{1},A_{2}\dots A_{6}$,
where the class $C$ is determined with the expression: if $A_{1}==0$ then
$C=A_{2}\land A_{3}$ else $C=A_{4}\land A_{5}$. $A_{6}$ is unrelated to the
binary class $C$. The attribute $A_{1}$ divides the problem space into two
subspaces. The dataset is imbalanced and consists of 1511 instances of
majority class 0 and 489 instances of minority class 1. We explain the
minority class. A few instances from the dataset are shown in Table 3.

Table 3: A few instances from the illustrative dataset. $i$ | $A_{1}$ | $A_{2}$ | $A_{3}$ | $A_{4}$ | $A_{5}$ | $A_{6}$ | $C$ |
---|---|---|---|---|---|---|---|---
51 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
52 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
53 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |  }-1.1-[instance from the first subspace]
54 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
55 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
56 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | }-1.1-[instance from the second subspace]
57 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
58 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
59 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
60 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |

As described in Section 3.1, we first train the classifier (in this example
this is a multilayer perceptron) using the above-described dataset, and
explain all instances from the minority class using the IME explanation
method. For example, as the explanation of instance 53 ($A_{1}=0$, $A_{2}=1$,
$A_{3}=1$, $A_{4}=1$, $A_{5}=0$, $A_{6}=1$) we get $E_{53}=$(0.209, 0.293,
0.297, 0.036, -0.074, 0.005). The explanation is illustrated in Figure 3,
which shows the contributions of attributes for classification of instance 53
into class 1.

Figure 3: Explanation of instance 53 from the first subspace of the
illustrative example.

On the left-hand side of the vertical axis, the names of the attributes are
listed, on the right-hand side (in boxes) the contributions of the attributes
for this instance, and on the far right the attribute values. The bars
correspond to the contributions of the attributes to the prediction. The first
three attributes satisfy the condition $A_{1}=0$ and $A_{2}=1$ and $A_{3}=1$
and are in favour of class 1. The model correctly predicted class 1 with the
probability of 0.997 and assigned a large positive contribution to the first
three attributes. The contributions of $A_{4}$ and $A_{5}$ are small and the
contribution of $A_{6}$ is almost zero.

The second step (see Section 3.2) determines the largest explanation scores
for each instance for different thresholds; we use lower threshold
$thr_{l}=0.6$, upper threshold $thr_{u}=0.8$, and $step=0.1$. For each
instance, we take the absolute values of the explanations, normalise them to
1, and sort them in descending order. The result for instance 53 is shown in
Figure 4.

Figure 4: Explanations normalised to 1 and ordered. $A_{3}$ | $A_{2}$ | $A_{1}$ | $A_{5}$ | $A_{4}$ | $A_{6}$
---|---|---|---|---|---
0.325 | 0.321 | 0.229 | 0.081 | 0.039 | 0.005

To determine groups of co-occurring attributes, we iteratively set weights of
the largest contributions to 1 until the sum of the normalised explanations
exceeds the threshold. For the instance 53 in Figure 3 and the threshold of
0.6, the sum of the first two explanations is $0.646$ and we mark $A_{2}$ and
$A_{3}$ as a candidate group by setting their weights to 1, as shown in Figure
5.

Figure 5: Instance weights after applying the threshold ($q=0.6$). $A_{1}$ | $A_{2}$ | $A_{3}$ | $A_{4}$ | $A_{5}$ | $A_{6}$
---|---|---|---|---|---
0 | 1 | 1 | 0 | 0 | 0

With the threshold 0.7, we add also $A_{1}$ to the group and the vector of
weights is $w_{53}=(1,1,1,0,0,0)$. The vector of weights now contains all
relevant attributes for this instance.

We select candidate groups of attributes for each threshold and each explained
instance. The results are presented in Table 4, which also shows the
frequencies of candidate groups. For example, for threshold $0.6$, $A_{2}$ and
$A_{3}$ appear together in 249 (50.9%) explanations. The result of candidate
groups identification step is as shown in Figure 6.

Table 4: Identification of frequently co-occurring groups of attributes for each threshold (sorted in descending order). $thr=0.6$ | $thr=0.7$ | $thr=0.8$ |
---|---|---|---
$A_{2},A_{3}$ | 249 | $A_{1},A_{2},A_{3}$ | 187 | $A_{1},A_{2},A_{3}$ | 187 |
$A_{4},A_{5}$ | 237 | $A_{1},A_{4},A_{5}$ | 180 | $A_{1},A_{4},A_{5}$ | 180 |
$A_{1},A_{2},A_{3}$ | 3 | $A_{2},A_{3}$ | 65 | $A_{3},A_{4},A_{5}$ | 36 |
|  | $A_{4},A_{5}$ | 57 | $A_{2},A_{3},A_{5}$ | 36 |
|  |  |  | $A_{2},A_{3},A_{4}$ | 29 |
|  |  |  | $A_{2},A_{4},A_{5}$ | 21 |
Figure 6: The collection of candidate groups. $A_{2},A_{3}$ | $A_{4},A_{5}$ | $A_{1},A_{2},A_{3}$ | $A_{1},A_{4},A_{5}$ | $A_{3},A_{4},A_{5}$ | $A_{2},A_{3},A_{5}$ | …
---|---|---|---|---|---|---

In the feature construction step (see Section 3.3), we generate operator-based
features (using logical operators {$\equiv,\oplus,\Rightarrow$}), features of
decision rule learner FURIA, and threshold features (num-of-N). We create 30
operator-based features using pairs of attributes from the candidate groups.
For the FURIA algorithm, we set the threshold for the certainty factor to
$cf=0.9$ and the threshold for the percentage of covered instances to
$pci=90\%$. In our method, the FURIA algorithm does not work on all
attributes, but searches for good rules using attributes from individual
candidate groups.

FURIA iterates through all groups of attributes, starting with the first
group, i.e., {$A_{2},A_{3}$}. The algorithm does not generate any features
from the first and second group. For the group {$A_{1},A_{2},A_{3}$}, the
algorithm generates feature ($A_{2}=1)\land(A_{3}=1)\land(A_{1}=0$) which
covers 225 out of 489 instances from class 1. The remaining 237 instances are
covered with the group {$A_{1},A_{4},A_{5}$} (see Algorithm 5 in Section 3.6
for details).

The threshold features are generated from the features previously generated by
FURIA. In this example, two threshold features are generated: num-
of-N$((A_{2}=1),(A_{3}=1),(A_{1}=0))$ and num-
of-N$((A_{4}=1),(A_{5}=1),(A_{1}=1))$. The num-of-N construct counts the true
conditions in the set of N specified conditions. In this case, possible values
for these features are integers from 0 to 3.

In the feature evaluation step (see Section 3.4), we use the MDL measure. The
results are shown in Table 5. We can see that two directly expressed parts of
the target concept are ranked first.

Table 5: The evaluation of generated features ordered by the decreasing MDL score. Constructs | MDL score
---|---
num-of-N$((A_{2}=1),(A_{3}=1),(A_{1}=0))$ | 0.32
$(A_{2}=1)\land(A_{3}=1)\land(A_{1}=0)$ | 0.30
num-of-N$((A_{4}=1),(A_{5}=1),(A_{1}=1))$ | 0.29
$(A_{4}=1)\land(A_{5}=1)\land(A_{1}=1)$ | 0.28
$A1\Rightarrow A5$ | 0.12
$A1\Rightarrow A4$ | 0.12
$A1\equiv A3$ | 0.08
$A1\oplus A3$ | 0.08
$A2\equiv A3$ | 0.07
$\vdots$ |
$A2\Rightarrow A4$ | 0

If we add some noise to the class value by reverting it in 5% of the cases, we
get the same results with the additional, irrelevant group
$\\{A_{3},A_{4},A_{5}\\}$. The FURIA constructs cover correctly classified
instances from class 1 and leave the noisy instances uncovered.

##  4 Evaluation settings

We evaluate the proposed methodology in three settings. Using synthetic
datasets, we analyse its properties. Using real-world UCI datasets, we compare
it to other constructive induction approaches and establish its performance.
The use case from the financial industry shows how our methodology can be
valuable in practice. We start by presenting the three groups of datasets
(synthetic, UCI, and real-world use case), followed by a short description of
compared feature construction methods and the experimental settings. Finally,
we present the settings of the methods used in the evaluation.

###  4.1 Datasets

The empirical evaluation uses several synthetic and real-world classification
datasets. The synthetic datasets are presented in Section 4.1.1 and summarised
in Table 6. The UCI datasets are presented in Section 4.1.2 and summarised in
Table 7. Finally, the dataset describing the financial use case is presented
in 4.1.3.

####  4.1.1 Synthetic data

With synthetic datasets we test the proposed methodology on different types of
concepts (conjunction, disjunction, xor, equivalence) and with different types
of dependencies between attributes (conditionally independent attributes,
redundant attributes, random attributes, etc.). The summary of these datasets
is given in Table 6. We created 10 synthetic datasets with numerical, nominal
and binary attributes. The numerical attributes contain values from [0,1]
interval. The values of nominal attributes can be 0, 1, or 2. Some of the
datasets were used in past studies related to explanation methodology (Robnik-
Šikonja and Kononenko, 2008; Štrumbelj and Kononenko, 2010, 2014; Štrumbelj et
al., 2009). Each dataset consists of 2000 instances. A short description of
datasets is presented below.

Table 6: The summary of synthetic datasets. The columns show the number of instances (#I), number of attributes (#A), number of unrelated attributes (#U), number of nominal attributes (#Nom), number of numeric attributes (#Num), number of classes (#C), and % of noise. Name | #I | #A | #U | #Nom | #Num | #C | Noise
---|---|---|---|---|---|---|---
LogicalConcB | 2000 | 7 | 1 | 7 | 0 | 2 | 0
LogicalConcBNoisy | 2000 | 7 | 1 | 7 | 0 | 2 | 5
BinClassDisAttr | 2000 | 5 | 1 | 5 | 0 | 2 | 0
BinClassNumBinAttr | 2000 | 5 | 1 | 2 | 3 | 2 | 0
BinClassNumDisAttr | 2000 | 5 | 1 | 2 | 3 | 2 | 0
DisjunctN | 2000 | 5 | 2 | 0 | 5 | 2 | 0
MultiVClassDisAttr | 2000 | 5 | 1 | 5 | 0 | 3 | 0
Concept | 2000 | 5 | 1 | 5 | 0 | 2 | 0
ModGroups | 2000 | 4 | 2 | 0 | 4 | 3 | 10
CondInd | 2000 | 8 | 4 | 8 | 0 | 2 | 0

LogicalConcB The dataset consists of 7 binary attributes, the last of which is
unrelated to the binary class $C$. Attribute $A_{2}$ divides the problem space
into two 2 subspaces:
if $A_{2}==0$ then $C=A_{1}\overline{A_{3}}$ else $C$=$A_{4}A_{5}\lor A_{6}$

LogicalConcBNoisy Dataset has the same concept as LogicalConcB, but contains
5% class noise.

BinClassDisAttr All five attributes are nominal, $A_{5}$ is unrelated to the
class, the class is binary. The attribute $A_{1}$ divides the problem space
into 3 sub-problems:
if $A_{1}==2$ then $C=(A_{2}==0)\land(A_{3}==1)$
else if $(A_{1}==1)$ then $C=(A_{4}==2)\lor(A_{3}==2)\lor(A_{2}\neq A_{1})$
else $C=(A_{4}==0)$

BinClassNumBinAttr The dataset consists of two binary attributes
($A_{1},A_{2}$) and three numerical attributes ($A_{3},A_{4},A_{5}$).
Attribute $A_{5}$ is unrelated to the class. The class value is binary.
if $A_{1}==0$ then $C=(A_{3}>0.3)\land(A_{4}<0.1)$
else $C=(A_{2}==0)\land(A_{3}>0.7)$

BinClassNumDisAttr Dataset is similar to dataset BinClassNumBinAttr. The
difference is that the first two attributes ($A_{1},A_{2}$) are nominal.
if $A_{2}==0$ then $C=(A_{3}<0.5)\land(A_{1}==0)$
else if $(A_{2}==1)$ then $C=(A_{4}>0.15)\land(A_{1}==2)$
else $C=(A_{3}>0.5)\land(A_{4}>0.5)\land(A_{1}==1)$

DisjunctN (disjunction with numerical attributes) The dataset consists of 5
numerical attributes. The first three are important for classification, the
last two are unrelated to the class. The class value is binary.
$C=(A_{1}>0.5\lor A_{2}>0.7\lor A_{3}<0.4)$

MultiVClassDisAttr All attributes in the data set are nominal, with the fifth
attribute ($A_{5}$) unrelated to the class. The dataset simulates a three-
class problem.
if $A_{1}==2$ then { if $(A_{2}==0)\land(A_{3}==1)$ then $C=1$ else $C=0$ }
else if $(A_{1}==1)$ { if $(A_{4}==2)\lor(A_{3}==2)\lor(A_{2}\neq A_{1})$ then
$C=2$ else $C=1$ }
else { if $(A_{4}==0)$ then $C=2$ else $C=0$ }

Concept The data set consists of 5 binary attributes, the last is unrelated to
the class. The class value is binary. The attribute $A_{2}$ divides the
problem space into two 2 subspaces:
if $A_{2}==0$ then $C=$ all-of-N$(A_{1}==1,A_{3}==0,A_{3}==A_{4})$
else $C=$ num-of-N$(A_{3}==1,A_{1}==A_{4})>0$

ModGroups (Robnik-Šikonja and Kononenko, 2008) The dataset consists of 4
numerical attributes. The first two $I_{1}$ and $I_{2}$ are important and
represent the x and y axes. The last two attributes are unrelated to the
class. The unit square is divided into nine equivalent squares, with each
square representing one of three possible class values. An instance is
correctly classified only if we have knowledge of both important attributes.
Dataset contains 10% noise; the noise was imputed by reverting 10% class
values.

CondInd (Robnik-Šikonja and Kononenko, 2008) The dataset consists of 8 binary
attributes, the first four are important and the other four are unrelated to
the class. The class value is binary and the probability of each class is 50%.
In 90, 80, 70 and 60% of the cases, the four important attributes correspond
to the class. This dataset contains no dependent attributes.

####  4.1.2 UCI datasets

The summary of UCI datasets can be found in Table 7. We collected datasets
from several papers related to constructive induction (Fan et al., 2010; Gama,
1999; Hammami et al., 2020; Katz et al., 2016; Markovitch and Rosenstein,
2002; Muharram and Smith, 2005; Nargesian et al., 2017; Pechenizkiy, 2005;
Zupan et al., 2001) and attribute interactions (Jakulin and Bratko, 2003a;
Murthy et al., 2018; Perez and Rendell, 1995; St. Amand and Huan, 2017; Tang
et al., 2019; Yazdani et al., 2017; Zeng et al., 2015). The Biological
response dataset (taken from the Kaggle repository) was chosen to show
usability of the methodology on the dataset with large number of attributes
(marked with asterisk).

Table 7: The summary of UCI datasets. The columns show the number of instances (#I), number of attributes (#A), number of nominal attributes (#Nom), number of numeric attributes (#Num), and number of classes (#C). Name | #I | #A | #Nom | #Num | #C
---|---|---|---|---|---
Australian credit | 690 | 14 | 8 | 6 | 2
Autos | 205 | 25 | 10 | 15 | 7
Balance scale | 625 | 4 | 0 | 4 | 3
Bank marketing | 4521 | 16 | 9 | 7 | 2
Biological response* | 3751 | 1776 | 0 | 1776 | 2
Car | 1728 | 6 | 6 | 0 | 4
CNAE-9 | 1080 | 856 | 0 | 856 | 9
Glass | 214 | 9 | 0 | 9 | 7
Heart | 270 | 13 | 0 | 13 | 2
Ionosphere | 351 | 34 | 0 | 34 | 2
Japanese credit | 690 | 15 | 9 | 6 | 2
Leukemia | 72 | 7129 | 0 | 7129 | 2
Liver disorders | 345 | 6 | 0 | 6 | 2
LSVT voice | 126 | 310 | 0 | 310 | 2
Lung cancer | 32 | 56 | 56 | 0 | 3
Mammographic mass | 961 | 5 | 0 | 5 | 2
Molecular promoters | 106 | 57 | 57 | 0 | 2
Monks1 | 432 | 6 | 6 | 0 | 2
Monks2 | 432 | 6 | 6 | 0 | 2
Nursery | 12960 | 8 | 8 | 0 | 5
Parkinsons | 195 | 22 | 0 | 22 | 2
QSAR biodegradation | 1055 | 41 | 0 | 41 | 2
Semeion | 1593 | 256 | 256 | 0 | 10
Sonar | 208 | 60 | 0 | 60 | 2
Spambase | 4601 | 57 | 0 | 57 | 2
Spect heart | 267 | 22 | 22 | 0 | 2
Spectf heart | 349 | 44 | 0 | 44 | 2
Tic-tac-toe | 958 | 9 | 9 | 0 | 2
Vehicle | 846 | 18 | 0 | 18 | 4
Voting | 435 | 16 | 16 | 0 | 2

####  4.1.3 Use case from the financial industry

Credit ratings and credit risk assessments plays an important role in ensuring
the financial health of financial and non-financial organisations.
Understanding the financial statements can be significantly improved by the
credit score arguments of a particular company (Ganguin and Bilardello, 2004).

We use a dataset of annual financial statements and credit scores for 223
Slovenian companies. The data were obtained from an institution that
specialises in issuing credit scores. Original (five class) dataset was split
into two classes (good and bad) to simplify the learning process of machine
learning approaches. The dataset contains 115 companies with the “bad“ score
and 108 companies with the “good“ score. The domain expert selected 22
attributes that describe each company; nine from the income statement (net
sales, cost of goods and services, cost of labor, depreciation, financial
expenses, interest, EBIT, EBITDA, net income), eleven from the balance sheet
(assets, equity, debt, cash, long-term assets, short-term assets, total
operating liabilities, short-term operating liabilities, long-term
liabilities, short-term liabilities, inventories), and two from the cash flow
statement (FFO - fund from operations, OCF - operating cash flow).

Beside these attributes, the financial expert introduced 9 new attributes
during the argument-based machine learning (ABML) process (Guid et al., 2012).
The additional attributes are: Debt to Total Assets Ratio, Current Ratio,
Long-Term Sales Growth Rate, Short-Term Sales Growth Rate, EBIT Margin Change,
Net Debt To EBITDA Ratio, Equity Ratio, TIE - Times Interest Earned, and ROA -
Return on Assets. Descriptions of these concepts can be found in financial
accounting literature, e.g., (Holt, 2001).

Table 8: Baseline financial indicators and expert attributes (in bold) from the credit scoring problem ordered by their decreasing MDL score. Original attributes | MDL score
---|---
(Debt - Cash) / EBITDA (Net Debt To EBITDA) | 0.548
EBIT / Interest (TIE) | 0.402
Net Income | 0.306
EBIT / Assets (ROA) | 0.294
FFO | 0.212
EBIT | 0.194
Equity / Assets (Equity Ratio) | 0.183
Short-Term Assets / Short-Term Liabilities (Current Ratio) | 0.166
EBITDA | 0.147
Short-Term Sales Growth | 0.107
Long-Term Sales Growth | 0.094
Equity | 0.091
OCF | 0.074
Cash | 0.072
EBIT Margin Change | 0.066
Debt | 0.052
Interest | 0.048
Financial expenses | 0.043
Total Operating Liabilities / Asset (Debt To Assets) | 0.033
Short-Term Liabilities | 0.021
Long-Term Liabilities | 0.018
Depreciation | 0.017
Short-Term Assets | 0.017
Assets | 0.017
Total Operating Liabilities | 0.013
Short-Term Operating Liabilities | 0.013
Long-Term Assets | 0.010
Cost Of Labor | 0.007
Cost Of Goods And Services | 0.005
Net Sales | 0.005
Inventories | 0.004

Table 8 lists all existing attributes in this domain, i.e., both baseline
financial indicators as well as expert-derived indicators (in bold). The
attributes are ordered by their MDL score (i.e., direct impact on the credit
score class value). The ordering shows that expert-derived attributes are
stronger predictors of the credit score, as evidenced from their dominance in
the upper part of the list.

###  4.2 Compared methods

We compare EFC methodology with baseline and other feature construction
methods. The only other constructive induction method we could find was
presented by Jakulin (2005). This method was implemented in one of the earlier
versions of Orange data mining suite (Orange
2.7)222https://orangedatamining.com/ but is no longer available. As the
implementation worked for larger datasets, we reimplemented it. This method is
based on the interaction information as described in Section 2.1.3. As
explained in Section 2.1, FICUS (Markovitch and Rosenstein, 2002) and HINT
(Zupan et al., 1998) constructive induction methods are no longer
available333We obtained this information from the authors, S. Markovitch and
J. Demšar.. These methods are complex and their reliable reimplementation is
questionable, so we omitted them from evaluation. Other constructive induction
methods (CITRE (Matheus and Rendell, 1989), FRINGE (Bagallo and Haussler,
1990), IB3-CI (Aha, 1991), and LFC (Ragavan et al., 1993)) can be simulated
with methodology by excluding the search space reduction based on explanations
and by reducing the set of constructive operators. We analyse these reductions
in Section 5.

As baselines we use i) comprehensible classifiers (decision trees and Naive
Bayes) without constructive induction, and ii) comprehensible classifiers
using constructive induction with the exhaustive search, where we use
constructive operators with all combinations of attributes. We also compare
the predictive performance of EFC with state-of-the-art non-interpretable
classifier (i.e., XGBoost). The results of XGBoost serve as an upper-bound of
predictive performance and are an indication of the loss suffered if we settle
for interpretable classifiers (with and without constructive induction). These
experiments use datasets from the UCI repository, summarised in Section 4.1.2.

###  4.3 Experimental settings

Unless mentioned otherwise, we use the following settings. As the explanation
method, we use SHAP in combination with the XGBoost prediction model using the
parameters numOfRounds=100, maxDepth=3, eta=0.3, and gamma=1. We explain the
minority class value $c$. The parameter $instThr$, which controls the minimum
number of explained instances, is set to 10% of instances in the dataset. If
the number of instances in the explained class $c$ is below $instThr$, we take
another class that has at least $instThr$ instances. We set the maximal number
of explained instances ($maxToExplain$) to 500. If the instances from class
$c$ exceed $maxToExplain$, we randomly sample $maxToExplain$ instances from
class $c$.

The minimum weight threshold ($thr_{l}$) is set to 0.1 and the maximum weight
threshold ($thr_{u}$) to 0.8, with the step 0.1. The noise threshold
($noiseThr$) for subgroups is set to 1%. When constructing features with the
FURIA learner, we use the certainty factor ($cf$) 0.6 and omit the coverage
parameter ($pci$) to get the maximal number of rules/features related to the
explained class.

All experiments used 2.93 GHz Intel Xeon X5670 CPU server with 32 GB RAM.
Algorithms are implemented in Java (v1.8.0). The classifiers are taken from
the Weka (Eibe et al., 2016) machine learning package using the default
settings.

##  5 Results

The results are presented in three subsections. Section 5.1 addresses the
synthetic data, Section 5.2 contains results on the UCI data, and Section 5.3
covers the financial industry use case.

###  5.1 Synthetic data

Experiments on synthetic datasets test components and properties of the
proposed methodology. We check detection of relevant attribute groups, and the
performance of resulting classifiers.

####  5.1.1 Detection of relevant attribute groups

We first check if EFC finds the relevant groups of attributes that appear in
the definitions of datasets (see Section 4.1.1). The identified groups are
essential for the success of feature construction phase and reduction of
search space. The results are presented in Table 9 where complete correct
expressions from definitions are marked with blue colour and groups containing
irrelevant attributes with red colour (e.g., in MultiVClassDisAttr and
ModGroups dataset). Detected parts of expressions are underlined. Groups in
black contain attributes from different subspaces of the problem, e.g., the
group {$A_{1},A_{3},A_{5}$} from LogicalConcB consists of attributes $A_{1}$
and $A_{3}$ from one subspace and $A_{5}$ from the other subspace. Obtaining
groups from mixed subspaces is not surprising as the group members were
detected as relevant by the prediction model.

Table 9: Detected groups of co-occurring attributes in synthetic datasets. Blue groups represent complete expressions from the dataset definitions, and underlined groups contain parts of expressions. Groups containing attributes unrelated to the class are marked with red. Groups of relevant attributes from mixed subspaces are in black.  Dataset |  Detected groups of attributes
---|---
LogicalConcB |  A1 A3, A2 A6, A2 A4, A4 A5, A2 A4 A5, A1 A3 A6, A4 A6, A5 A6, A1 A2 A3, A1 A3 A5, A4 A5 A6, A2 A4 A6, A3 A4 A6, A1 A3 A4, A2 A4 A5 A6, A1 A4 A6, A2 A5 A6, A1 A2 A3 A6, A1 A3 A4 A6, A2 A3 A4 A6, A1 A2 A3 A5, A1 A4 A5 A6, A1 A2 A4 A6
LogicalConcBNoisy |  A1 A3, A2 A6, A2 A5, A2 A4, A4 A5, A2 A4 A5, A4 A6, A5 A6, A2 A4 A6, A2 A5 A6, A4 A5 A6, A1 A3 A6, A1 A2 A3, A1 A3 A5, A1 A2 A6, A2 A4 A5 A6, A1 A2 A3 A6, A2 A3 A6, A1 A2 A3 A5, A1 A2 A4 A6, A1 A3 A5 A6, A1 A3 A4 A6, A1 A4 A5 A6
BinClassDisAttr |  A2 A3, A2 A4, A1 A2, A1 A3, A1 A2 A3, A1 A2 A4
BinClassNumBinAttr |  A2 A3, A1 A2 A3, A3 A4, A2 A3 A4, A1 A4
BinClassNumDisAttr |  A1 A3, A3 A4, A1 A2, A1 A3 A4, A1 A2 A3
DisjunctN |  A1 A3, A1 A2 A3
MultiVClassDisAttr |  A1 A5, A2 A5, A2 A4, A1 A2 A5, A1 A4 A5, A2 A4 A5
Concept |  A1 A2, A2 A4, A3 A4, A1 A3, A1 A3 A4, A2 A3 A4, A1 A2 A3
ModGroups |  I1 I2, I1 R2, I1 I2 R2
CondInd |  I90, I80 I90, I70 I80 I90, I60 I80 I90

The results show that EFC ignores irrelevant attributes present in the
datasets in 8 out of 10 cases. The robustness of the methodology was tested on
two noisy datasets (LogicalConcBNoisy and ModGroups). EFC extracts all correct
concepts from both datasets, however, for the ModGroups dataset it also
extracts two groups with an irrelevant attribute. An error at this stage is
not crucial, as the later stages of EFC can ignore irrelevant attributes.
However, inclusion of irrelevant attributes unnecessarily increases the search
space of construction.

The CondInd dataset contains no relevant attribute groups (all attributes are
conditionally independent of class). EFC correctly detects the attribute I90
which has the strongest connection with the class. Other groups contain
several attributes because their joint probabilities are high enough (e.g.,
the joint probability of I90 and I80 is $0.9\cdot 0.8=0.72$, which is still
strongly relevant for the class detection and was therefore used in the
prediction model). The results of the CondInd dataset show that EFC may detect
spurious attribute interactions, which will be removed later in the
construction and evaluation step.

####  5.1.2 Predictive performance on synthetic data

We check if constructed features improve classification accuracy (CA). We test
several interpretable classifiers: decision trees (DT), Naive Bayes (NB), and
classification rules obtained with the FURIA rule learner (FU). Besides these,
we include a black-box random forest (RF) classifier. We expect that
constructive induction will improve the performance of interpretable
classifiers (DT and NB). Here the constructs improve the representation and
should also improve the interpretability of models. RF uses feature
construction internally and we use it to estimate the upper bounds of
classification performance. FURIA is used internally by some of the
constructive operators, so we expect improvements only in datasets where
dataset definitions contain constructive operators not covered by FURIA rules.

Without using constructive induction as a baseline (Base), we compare six
types of constructed features. The first setting includes only logical
operators (Log); we use operators
$O_{l}=\\{\land,\vee,\equiv,\oplus,\Rightarrow\\}$. The second includes only
relational (Rel) operators; we use operators $O_{r}=\\{<,\neq\\}$. The third
setting tests only Cartesian product (Cart) features, where we form the
Cartesian product of values for a pair of attributes. The fourth setting uses
only decision rule and threshold (DrThr) features; the decision rule features
are expressions produced by the FURIA learner, and the threshold features
count the number of correct logical expressions entered as their arguments.
The fifth setting includes all the previously mentioned feature types (All),
and the last, sixth setting constructs all types of features but applies
feature selection (FS) using a validation dataset to measure their
performance. In the FS setting, the training dataset is internally split into
the training and validation part, allowing the search for optimal parameters
in the training part and testing them on the validation part using CA as the
criterion. The proportion of training and validation instances is a parameter
of the EFC; we use the ratio 75:25 which is commonly used by ML practitioners.
The best parameters are applied to the whole training dataset and the
resulting datasets and models are tested on the testing set. The method could
use other feature selection algorithms (e.g., MCEC (Azadifar et al., 2022),
(Rostami et al., 2022)), or any other method covered in a recent survey
(Rostami et al., 2021). In this experiment, we use the MDL feature evaluation
score (Kononenko, 1995) with three different thresholds (0, 0.25, and 0.5). In
all six settings, the MDL feature evaluation measure is used to calculate the
importance of generated features at the end of methodology, in the sixth
setting (FS), however, it is also used in the feature selection phase. We
leave testing and analysis of other parameters for future work.

The results are reported in Table 10. The best result for each dataset and
classifier is underlined and results better or equal than the baseline
(without feature construction) are typeset in bold.

Table 10: Classification accuracy on synthetic datasets. We report success of
different types of constructive operators: logical (Log), relational (Rel),
Cartesian product (Cart), decision rules and threshold (DrThr), all previously
mentioned (All), and all previously mentioned with feature selection (FS). As
a baseline, we use no construction (Base). The best results for each dataset
and classifier are underlined, the results better or equal than the baseline
are in bold.

Dataset | classif. | Base | Log | Rel | Cart | DrThr | All | FS
---|---|---|---|---|---|---|---|---
LogicalConcB | DT | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00
NB | 83.10 | 94.40 | 83.10 | 90.75 | 96.60 | 95.30 | 95.05
FU | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00
RF | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00
LogicalConcBNoisy | DT | 95.00 | 95.00 | 95.00 | 95.00 | 95.00 | 95.00 | 95.00
NB | 78.25 | 86.95 | 78.25 | 85.60 | 89.10 | 88.70 | 88.80
FU | 95.00 | 95.00 | 95.00 | 95.00 | 95.00 | 95.00 | 95.00
RF | 95.00 | 95.00 | 95.00 | 95.00 | 95.00 | 95.00 | 95.00
BinClassDisAttr | DT | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00
NB | 88.60 | 88.60 | 88.60 | 88.60 | 95.25 | 88.60 | 88.60
FU | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00
RF | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00
BinClassNumBinAttr | DT | 99.85 | 99.80 | 99.85 | 99.85 | 99.85 | 99.85 | 99.85
NB | 91.80 | 97.45 | 91.80 | 94.70 | 93.90 | 95.20 | 97.30
FU | 99.85 | 99.80 | 99.85 | 99.90 | 99.90 | 99.85 | 99.80
RF | 99.85 | 99.80 | 99.85 | 99.80 | 99.80 | 99.85 | 99.90
BinClassNumDisAttr | DT | 99.75 | 99.65 | 99.75 | 99.65 | 99.85 | 99.75 | 99.70
NB | 83.95 | 90.30 | 85.55 | 90.95 | 97.80 | 91.40 | 91.35
FU | 99.75 | 99.70 | 99.75 | 99.70 | 99.85 | 99.75 | 99.75
RF | 99.75 | 99.75 | 99.70 | 99.75 | 99.85 | 99.75 | 99.65
DisjunctN | DT | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00
NB | 94.55 | 100.00 | 93.15 | 100.00 | 100.00 | 100.00 | 100.00
FU | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00
RF | 100.00 | 100.00 | 99.95 | 100.00 | 100.00 | 100.00 | 100.00
MultiVClassDisAttr | DT | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00
NB | 90.80 | 86.70 | 90.80 | 93.35 | 89.90 | 86.65 | 90.60
FU | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00
RF | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00
Concept | DT | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00
NB | 68.25 | 86.30 | 68.25 | 80.45 | 80.90 | 92.35 | 92.35
FU | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00
RF | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00
ModGroups | DT | 33.85 | 33.85 | 88.40 | 33.85 | 88.20 | 87.55 | 88.45
NB | 42.85 | 42.85 | 39.35 | 42.85 | 63.05 | 64.10 | 63.10
FU | 88.70 | 88.70 | 88.90 | 88.70 | 88.25 | 88.35 | 88.50
RF | 88.55 | 88.55 | 88.75 | 88.55 | 88.85 | 88.80 | 88.80
CondInd | DT | 89.80 | 89.80 | 89.80 | 89.80 | 89.80 | 89.80 | 89.85
NB | 91.05 | 91.05 | 91.05 | 90.70 | 90.60 | 90.55 | 90.55
FU | 89.85 | 89.80 | 89.85 | 90.05 | 90.35 | 90.00 | 89.85
RF | 89.80 | 89.65 | 89.80 | 89.65 | 89.50 | 89.70 | 89.55

For NB classifiers, at least one operator setting improves CA in 9 out of 10
datasets, which shows the usefulness of constructed features. For DT, FURIA,
and RF, we cannot observe such benefits as the baseline methods are already
very successful on tested synthetic problems, often achieving 100% CA.
Unsurprisingly, the results on synthetic data are also inconclusive concerning
the constructive operators as they are all useful in at least some of the
datasets.

To summarise the findings on the synthetic data: _EFC effectively identifies
informative groups of attributes and ignores irrelevant attributes._

###  5.2 UCI datasets

In this section, we analyse the EFC method on selected UCI datasets using
different classifiers and various types of features. We first report
predictive performance of various constructive operators, followed by the
number of generated features and computational times used by different
settings.

####  5.2.1 Predictive performance on UCI datasets

Following the settings used on synthetic data, we tested the classification
accuracy of seven popular classifiers: DT, NB, FURIA, RF, k-nearest neighbours
(kNN) with k=10, support vector machines with linear kernel (SVM-lin) and
support vector machines with RBF kernel (SVM-RBF). In this section, we outline
the results of these classifiers and present statistical significance of the
differences between the approaches, while the complete tables with the results
are available in A. We calculated CA using 10-fold cross-validation.

Without using constructive induction as a baseline (Base), we compare the use
of logical operators (Log), relational operators (Rel), Cartesian product
(Cart), decision rule and threshold (DrThr) features, all types of features
(All), and all types of features with feature selection (FS). In addition to
these methods, we report results of feature construction with the method
proposed by Jakulin (2005) (Jak) and with the exhaustive search (Exh). For Exh
the ’-’ sign means that the result was not generated in feasible time (3 hours
per fold); in the averages, we replace these missing scores with the baselines
and mark them with *. We include results of XGBoost (XGB) ensemble as an
estimate of the upper bound. The best CA for each dataset (excluding XGBoost)
is marked with bold typeface. If none of the feature construction methods
improves the baseline result, bold typeface is omitted (see the tables in A).

Results for DT (Table 14) show that construction with DrThr, Log, and FS
settings outperforms the baseline (without feature construction) in 22 out of
30 datasets, the All method outperforms the base results in 20 datasets, and
the Rel and Cart method outperforms the base results in 12 out of 30 datasets.
In a few cases (8 out of 30), the DT classifier with one of feature
construction methods is the best method overall, superior even to XGB.
Statistical significance of the differences are reported later in this
section.

Using the NB classifier (Table 15), the FS outperforms the baseline in 21 out
of 30 datasets, the methods DrThr and All in 20 datasets, Log and Cart in 19,
and Rel in 13 out of 30 datasets. In 4 out of 30 cases the most efficient
approach is to use the NB classifier with one of the feature construction
methods.

Using the SVM-lin classifier (Table 16), the DrThr setting outperforms the
baseline in 19 out of 30 datasets, the FS setting outperforms the base results
in 18 datasets, the All in 17, the Cart in 15, the Log in 14, and the Rel
setting in 10 out of 30 datasets. In 11 out of 30 cases the most efficient
approach is to use the SVM-lin classifier with one of the feature construction
methods.

Using the SVM-RBF classifier (Table 17), the FS setting outperforms the
baseline in 26 out of 30 datasets, the DrThr method outperforms the base
results in 25 datasets, the All method in 22, the Cart and Log in 19, and the
Rel in 10 out of 30 datasets. In 7 out of 30 cases the most efficient approach
is to use the SVM-RBF classifier with one of the feature construction methods.

Using the kNN classifier (Table 18), the DrThr setting outperforms the
baseline in 19 out of 30 datasets, the FS method outperforms the base results
in 18 datasets, the Cart method in 17, the Log in 15, the All method in 14,
and the Rel in 11 out of 30 datasets. In 7 out of 30 cases the most efficient
approach is to use the kNN classifier with one of the feature construction
methods.

Using the FURIA classifier (Table 19), FS outperforms the baseline in 15 out
of 30 datasets, the All method outperforms the base results in 14 datasets,
Log and Rel in 13, DrThr in 11, and Cart in 10 out of 30 datasets. In 10 out
of 30 cases the most efficient approach is to use the FURIA classifier with
one of the feature construction methods.

Using the RF classifier (Table 20), the setting DrThr outperforms the baseline
in 11 out of 30 datasets, the methods Cart and FS in 10, Log and All in 9, and
Rel in 7 out of 30 datasets. In 15 out of 30 cases the most efficient approach
is to use the RF classifier with one of the feature construction methods; this
is the most of all classifiers tested.

As expected, we get the best average classification accuracy (86.75) with the
”upper-bound” XGBoost algorithm. When comparing only the feature construction
methods, the best average CA (84.04) for the DT classifier is obtained with
all constructed features, and for NB the best score is obtained with the FS
setting (79.93). With the FS setting, we also get the best CA for the SVM-RBF
(81.00) classifier and the kNN (82.33) classifier. For the SVM-lin classifier,
the best score is obtained with the setting All (84.62). For the FURIA
classifier, the best CA (86.02) is obtained with Exh setting, and for RF the
best score is obtained with the FS setting (86.88) which is even better than
with the XGBoost algorithm (86.75). Note that the average CA of baseline for
RF is 85.07.

To assess the statistical significance of the differences between the tested
feature construction methods, we perform a non-parametric Friedman test with
the Nemenyi correction (Demšar, 2006) for all classifiers (DT, NB, FURIA, RF,
kNN, SVM-lin, SVM-RBF). Figure 7(b) shows the critical difference (CD)
diagrams for CA of DT and NB classifiers and Figure 8(b) for the CA of the
SVM-RBF and kNN classifiers. The average rank of each method is marked on the
horizontal axis (lower ranks mean better CA). Groups of methods that are not
significantly different according to the Nemenyi test are connected with a
thick line. The length of the critical difference (e.g., CD = 1.92 for the DT
classifier) is shown above the axis.

Figure 7: Statistical significance of differences between feature construction
methods using the DT (a) and the NB (b) classifier. The critical distance
diagram shows the results of the Nemenyi post-hoc test at $\alpha=0.05$.

DrThr (3.33)All (3.65)Log (3.70)FS (3.93)Jak (4.90)Rel (5.28)Cart (5.57)Base
(5.63)CD = 1.9287654321

(a)

FS (2.88)DrThr (3.68)All (3.88)Log (4.63)Cart (4.77)Jak (4.98)Rel (5.28)Base
(5.88)CD = 1.9287654321

(b)

Figure 8: Statistical significance of differences between feature construction
methods using the SVM with the RBF kernel (a) and the kNN (b) classifier. The
critical distance diagram shows the results of the Nemenyi post-hoc test at
$\alpha=0.05$.

FS (3.22)DrThr (3.40)All (3.78)Jak (4.42)Cart (4.52)Log (4.62)Rel (5.83)Base
(6.22)CD = 1.9287654321

(a)

FS (2.98)DrThr (3.40)All (4.42)Cart (4.43)Base (4.92)Rel (5.12)Log (5.32)Jak
(5.42)CD = 1.9287654321

(b)

Using the DT classifier, operators DrThr, All, and Log significantly improve
CA compared to the baseline. The DrThr setting is superior also to constructs
composed of only Rel and Cart features (see Figure 7(a)). The NB classifier
returns similar results, the difference is in the method with the lowest rank
(see Figure 7(b)), which is FS for NB. The FS setting is superior also to
constructs composed of only Rel features. The SVM-RBF classifier returns
similar results as NB. The FS, DrThr, and All settings improve CA compared to
the baseline (see Figure 8(a)); all these settings are superior also to
constructs composed of only Rel features. Using the kNN classifier, the FS
operator significantly improves CA compared to the baseline and is superior
also to constructs composed of only Rel and Log features (see Figure 8(b)).
The results of the RF, FURIA, and SVM-lin classifiers show no statistical
differences between the construction methods, so we skip the graphs.

We can conclude that the proposed feature construction is beneficial. Using
the resulting constructs, the interpretable models, such as DT and NB as well
as the kNN and the SVM models become significantly better compared to
baselines without feature construction. Unsurprisingly, different datasets and
learning methods require different feature construction operators. As there is
no clear winner among the tested operators, we decided to use all operators
(the All setting) in further analyses.

####  5.2.2 Analysis of constructed features for UCI datasets

In this section, we analyse the properties of the obtained constructs. We
start with the identified groups of co-occurring attributes, followed by the
constructed features and features actually used in DT classifiers. We work
with all types of features (the All setting).

Figure 9: The summary of EFC’s ability to reduce the search space shown for
used UCI datasets. From left to right, the box-and-whiskers plots show the
distribution of the number of groups, number of attributes in groups, and
maximum length of groups. All numbers are small across all tested UCI
datasets.

Figure 9 shows the inner workings of the EFC method, namely the distribution
of the number of groups, number of attributes in groups and maximal length of
groups, obtained on the UCI datasets with the DT classifier.

As the box-and-whiskers plots show, EFC generates an average of 8.7 groups of
co-occurring attributes, which have the average size of 2.9 (number of
attributes in the group), with the maximum size of 4.3 attributes per group.
These numbers are relatively low and so is their variance. Comparison of the
number and sizes of discovered groups with the overall number of attributes in
Table 7 shows that EFC effectively reduces the search space. This finding is
confirmed in Section 5.2.3, where we measure the running times of EFC.

Table 11 shows the average number of the constructed features and features
actually used in the DT classifier (using All setting). The number of
generated features is proportional to the number of operators so EFC generates
the largest number of logical features (5 operators), followed by decision
rule features, threshold features, Cartesian product features, and relational
features.

The number of features actually used in the DT classifiers is moderately
correlated with the number of generated features (Spearman’s rank correlation
coefficient $\rho=0.487$ and $p=0.006$) so logical features are the most often
used. An exception is in the relational features, which are used more often,
and Cartesian product features, which are almost never used in All setting,
where other types of features are also available.

Table 11: Average numbers of constructed and actually used features for the All method and DT classifier. Columns show logical (Log), relational (Rel), Cartesian product (Cart), decision rule (Dr), and threshold features (Thr).  | constructed | actually used
---|---|---
Dataset | Log | Rel | Cart | Dr | Thr | Log | Rel | Cart | Dr | Thr
Aus. credit | 1191.4 | 13.3 | 18.8 | 10.2 | 9.0 | 11.8 | 1.8 | 0 | 2 | 0.2
Autos | 53.8 | 0.5 | 0.5 | 0.5 | 0.5 | 2.3 | 0 | 0 | 0.5 | 0.1
Balance scale | 46.4 | 12.0 | 6.0 | 35.0 | 32.9 | 2.4 | 12.5 | 0 | 10.7 | 2.8
Bank mark. | 197.0 | 0.2 | 1.1 | 1.2 | 0.4 | 13.6 | 0.2 | 0 | 1 | 0
Bio. resp. | 45.8 | 8.9 | 4.7 | 4.3 | 3.2 | 8.9 | 1.2 | 0.2 | 2.3 | 0.6
Car | 1095.5 | 0.0 | 9.0 | 48.4 | 48.4 | 27.1 | 0 | 0 | 0 | 0
CNAE-9 | 12.9 | 4.6 | 2.3 | 2.4 | 0.0 | 0.9 | 0 | 0 | 0 | 0
Glass | 299.4 | 9.3 | 10.5 | 2.4 | 1.4 | 4.8 | 1.2 | 0.1 | 0.8 | 1.4
Heart | 145.1 | 20.7 | 20.7 | 17.1 | 13.5 | 3.8 | 0.7 | 0.1 | 3.6 | 0.2
Ionosphere | 1816.5 | 20.0 | 10.0 | 10.0 | 4.4 | 4.6 | 0.3 | 0 | 1.3 | 0
Jap. credit | 595.8 | 15.2 | 19.9 | 10.8 | 9.7 | 9.9 | 0.7 | 0 | 3 | 0.3
Leukemia | 70.8 | 12.3 | 10.2 | 2.6 | 2.3 | 0.7 | 0 | 0 | 0.3 | 0
Liver dis. | 17.9 | 16.0 | 3.9 | 17.4 | 15.0 | 0.3 | 2.5 | 0 | 9.6 | 2.1
LSVT voice | 354.7 | 14.0 | 26.4 | 8.3 | 7.4 | 1.3 | 0 | 0 | 2.4 | 0
Lung cancer | 89.6 | 0.0 | 1.5 | 1.1 | 0.9 | 1.7 | 0 | 0 | 0 | 0
Mamm. mass | 256.1 | 6.9 | 6.0 | 8.8 | 4.8 | 4.9 | 0.6 | 0.1 | 2.2 | 0.4
Molecular | 6612.3 | 0.0 | 25.7 | 27.4 | 25.8 | 3.8 | 0 | 0 | 0 | 0
Monks1 | 136.5 | 0.0 | 1.8 | 11.7 | 9.6 | 2.6 | 0 | 0 | 0.1 | 0
Monks2 | 866.1 | 0.0 | 14.3 | 0.8 | 0.8 | 38.2 | 0 | 0 | 0 | 0
Nursery | 1471.0 | 0.0 | 9.4 | 33.2 | 32.2 | 138.1 | 0 | 0 | 0.1 | 0
Parkinsons | 436.2 | 1.4 | 17.8 | 18.7 | 16.9 | 1 | 0 | 0 | 3.3 | 0
QSAR | 308.6 | 11.3 | 9.1 | 15.4 | 12.3 | 8.4 | 2.5 | 0.1 | 7 | 0.8
Semeion | 489.8 | 0.0 | 45.8 | 11.1 | 10.9 | 10.6 | 0 | 0.4 | 1.5 | 0.1
Sonar | 45.6 | 7.9 | 7.2 | 6.8 | 3.4 | 1.9 | 0.1 | 0.1 | 2.7 | 0.2
Spambase | 335.0 | 10.8 | 6.9 | 12.9 | 5.0 | 22.3 | 0.7 | 0.1 | 4.5 | 0.5
Spect heart | 225.1 | 0.0 | 25.1 | 4.0 | 4.0 | 0.4 | 0 | 0 | 0.9 | 0
Spectf heart | 26.5 | 4.0 | 2.0 | 2.8 | 2.6 | 1.7 | 0.7 | 0 | 1.9 | 0.2
Tic-tac-toe | 3180.4 | 0.0 | 27.4 | 83.5 | 82.5 | 12.9 | 0 | 0 | 1.4 | 0
Vehicle | 5923.1 | 6.9 | 19.7 | 43.4 | 41.9 | 25 | 2.3 | 0.1 | 8.5 | 10.3
Voting | 64.7 | 0.0 | 9.5 | 3.6 | 2.6 | 1.6 | 0 | 0 | 0 | 0
Average | 880.3 | 6.5 | 12.4 | 15.2 | 13.5 | 12.25 | 0.93 | 0.04 | 2.39 | 0.67

We similarly analysed the learned decision rules and counted the number of
rules in the ruleset and the number of attributes in each rule. Comparing
rules produced on the originally selected UCI datasets and rules produced on
enriched datasets, the average number of rules dropped from 29.33 to 20.02.
However, the complexity of rules increased and the sum of attributes used in
all rules showed almost the same complexity, i.e., 116.05 for rules on the
original datasets and 114.10 for enriched dataset. The details are given in
Appendix B, see Table 21.

We can conclude that all types of features are useful in tested ML models but
their use depends on the ML algorithm and dataset. While the size of the
models is reduced with introduction of constructed features, the overall
complexity remains approximately the same.

####  5.2.3 Running times on UCI datasets

Since feature construction typically operates in very large search spaces, an
important practical consideration is its running time. We compare running
times of the EFC method in All setting (constructing all types of features)
with the exhaustive method, which does not use the proposed search space
reduction but is otherwise completely identical to EFC.

Figure 10: Running times (in seconds) of the feature construction part of the
EFC methodology compared to the exhaustive search on the UCI datasets. Times
of exhaustive search which exceed 3 hours per fold are dotted. EFC times for
many datasets are below 1 sec and are not visible on the graph.

Figure 10 illustrates that running times of EFC are significantly lower than
the times of the exhaustive method. The exhaustive method was unable to
terminate in the maximal allowed time (3 hours per one cross-validation fold)
in half of the datasets (indicated with the dashed line with an arrow). The
detailed running times and their standard deviations are presented in Appendix
C (see Table 22).

To summarise, _EFC significantly improves the CA of DT, NB, SVM-RBF and kNN
classifiers on UCI datasets, effectively reducing the search space and running
times compared to the exhaustive approach and enabling the use of feature
construction even for large datasets._

###  5.3 Use case in finance

In this section, we present an analysis of a use case from the financial
industry, namely the credit risk assessment. The use case demonstrates a
practical utility of the EFC method to generate human-comprehensible features.
The aim is not to produce the highest possible prediction accuracy but to help
human expert to better understand the risks associated with different types of
customers. We first use EFC to construct informative and practically relevant
features from the baseline financial indicators. The constructed features are
compared with known expert-designed (ED) features.

To construct informative features for credit risk assessment from raw
financial data, we explain both class values (the ”good” and the ”bad” credit
score). Besides the constructive operators presented previously, we also
include numerical operators $O_{n}=\\{+,-,/\\}$ which frequently appear in the
financial domain (thus, demonstrating the ease of adapting the EFC system to
new domains). We set the noise threshold $noiseThr=0$ to extract as much
information as possible.

We validate the obtained features in two ways: i) by expert assessment of the
constructed features in Section 5.3.1, and ii) by assessment of their
predictive performance in Section 5.3.2. We compare the predictive performance
of models using several combinations of only baseline financial indicators,
existing expert features, and constructed features.

####  5.3.1 Utility of constructed credit scoring features

In first evaluation of constructed features, we engaged a financial expert
(professor of finance) to assess the features. In Table 12, we compare the
expert’s numerical scores with the MDL scores. We show the strongest 25
constructed features (by the MDL score) obtained with EFC from the attributes
in Table 8 that use decision rules (13 rules) and quotients of financial
indicators (12 rules). Since the threshold values in the rules do not have
much meaning for the expert (they strongly depend on the examples in the
dataset and not on general knowledge), we simplified the operators and values
as follows: the decision rules with operator $<=$ was changed to ”= low”, and
with operator $>=$ to ”= high”. The expert scored the features on a 4-point
scale according to their impact on the credit scoring (0 - pointless, 1 -
weak, 2 - strong, 3 - very strong). As a control group, we added 10 constructs
that use sums, differences, or relations between attributes (these features
are expected to be less important in this domain). Pearson’s statistical test
showed that there is a significant linear correlation between the rankings of
the MDL scores and expert scores ($\rho=0.427$, $p=0.011$).

Table 12: Features (rules and ratios) constructed with EFC for the credit
scoring use case. The column Exp shows the expert’s opinion of the feature (0
- pointless, 1 - weak, 2 - strong, 3 - very strong). Column MDL shows the MDL
score, and column EDf marks if the ED features are included (letter $y$) or
excluded from EFC (letter $n$). Features from the control group are marked
with an asterisk (∗).

EFC Feature | Exp | MDL | EDf
---|---|---|---
((Net Debt / EBITDA) = low) and (Equity Ratio = high) | 2 | 0.633 | y
((Net Debt / EBITDA) = low) and ((Total Operating Liabilities / Assets) = low) | 2 | 0.608 | y
(TIE = high) and (Equity Ratio = high) and ((Net Debt / EBITDA) = low) | 3 | 0.575 | y
((Net Debt / EBITDA) = low) and ((Total Operating Liabilities / Assets) = low) and | 3 | 0.568 | y
(ROA = high) and (Current Ratio = high) |  |  |
∗(Net Debt / EBITDA) $-$ Current Ratio | 0 | 0.553 | y
∗(Net Debt / EBITDA) $-$ Equity Ratio | 1 | 0.548 | y
((Net Debt / EBITDA) = low) and (Current Ratio = high) and (TIE = high) and | 2 | 0.545 | y
((Total Operating Liabilities / Assets) = low) |  |  |
∗(Net Debt / EBITDA) $+$ Equity Ratio | 0 | 0.540 | y
∗TIE $-$ (Net Debt / EBITDA) | 0 | 0.535 | y
((Net Debt / EBITDA) = low) and (Current Ratio = high) and (FFO = high) | 3 | 0.529 | y
(TIE = high) and (Equity Ratio = high) and ((Net Debt / EBITDA) = low) | 3 | 0.529 | y
((Net Debt / EBITDA) = low)) and (Current Ratio = high) and (ROA = high) | 2 | 0.529 | y
((Net Debt / EBITDA) = low) and (Current Ratio = high) and | 3 | 0.524 | y
(ROA = high) and (Depreciation = high) |  |  |
EBITDA / Debt | 2 | 0.510 | n
Net Income / Debt | 2 | 0.482 | n
EBIT / Debt | 2 | 0.443 | n
∗Interest $-$ Net Income | 1 | 0.405 | n
FFO / Debt | 2 | 0.403 | n
EBIT / Interest | 3 | 0.402 | n
∗Financial Expenses $-$ Net Income | 1 | 0.394 | n
Net Income / Interest | 2 | 0.391 | n
Net Income / Financial Expenses | 2 | 0.382 | n
Net Income / Short-Term Liabilities | 2 | 0.382 | n
EBIT / Financial Expenses | 3 | 0.373 | n
EBITDA / Interest | 3 | 0.370 | n
(Net Income = high) and (Interest = low) and (Depreciation = high) | 3 | 0.366 | n
Net Income / Short-Term Operating Liabilities | 2 | 0.365 | n
(Net Income = high) and (Interest = low) | 3 | 0.364 | n
(Net Income = high) and (Interest = low) and (Long-Term Assets = high) | 3 | 0.358 | n
Net Income / Short-Term Assets | 1 | 0.346 | n
(Net Income = high) and (Short-Term Liabilities = low) | 3 | 0.344 | n
∗ROA $-$ Inventories | 0 | 0.004 | y
∗Equity $+$ Debt | 0 | 0.002 | n
∗Short-Term Assets $-$ EBIT | 0 | 0.002 | n
∗Current Ratio $<$ Equity Ratio | 0 | 0.000 | y

On average the expert rated the rules and quotients significantly higher
compared to the features in the control group. All conjunctive rules were
rated by the expert as strongly predictive, in 9 out of 13 cases even as very
strong. All quotients were marked as meaningful and for 11 of 12 quotients the
expert indicated that they have a strong predictive power for the assessment
of creditworthiness. On average, the obtained rules have higher predictive
power than the quotients. For 9 of the 12 quotients, we found explanations in
the financial literature (Calderon-Monge and Pastor-Sanz, 2017; Dang and Chuc,
2019; Gebauer et al., 2018; Hayes, 2021; Irfan et al., 2014; Jiangli et al.,
2004; Kenton, 2020; Koller et al., 2010; Lee and Lee, 2016), and for the
remaining three quotients, we have obtained very good approximations to the
standard financial ratios explained in the financial literature. We conclude
that EFC constructs useful features.

Expert-designed (ED) features show a strong relationship with credit score
prediction, as indicated by their high MDL scores (see Table 8). The EFC
system is able to generate identical features from the baseline attributes
only (see features with $n$ in the EDf column, e.g., ”EBIT / Interest” is
actually the same as the ED feature TIE). If we include the ED features into
the construction, EFC produces some complex features with MDL scores even
higher than those of the existing ED features. Observing features with $y$ in
the EDf column of Table 12, we can see that these complex features are not
difficult to comprehend when expressed as conjunctive rules. One of the common
constructs in these rules is related to net debt divided by EBITDA, which
indicates the number of years it takes a company to pay off its debt given its
current cash flow.

However, EFC may produce complex features with a very high MDL score, which
are more difficult to comprehend. An example of such a feature is ”(EBIT =
low) or (Net Debt / EBITDA = high) or (Equity Ratio = low)”, with the MDL
score of 0.684. Note that the operator OR is usually more difficult to
interpret even for domain experts, so we did not use it this experiment.

####  5.3.2 EFC for prediction in credit scoring

In Table 13, we present the classification accuracy of different models in the
credit scoring dataset. We compare predictive performance of models using a)
only baseline financial indicators, b) baseline indicators and existing expert
features, c) baseline indicators and constructed features, and d) baseline
indicators, constructed features, and expert-designed features.

CA of the models was calculated using 10-fold cross-validation. The bold value
in the tables means that it is greater than the baseline result for the
specific classifier. Due to the flexibility of EFC and specifics of the
domain, we decided to include numeric features in the All setting. We use the
same EFC settings as described in Section 4.3, except for $noiseThr$ which is
set to 0.

If we exclude the expert features (Table 13a) and use the DT, NB, SVM-lin,
SVM-RBF, kNN, or FU classifier, EFC improves CA over the baseline. If we use
much stronger but incomprehensible RF, there is no improvement. If we also
include ED features in the evaluation, the classifiers NB, SVM-lin, SVM-RBF,
kNN, FU and RF improve CA, while DT does not.

Table 13: Classification accuracy on the credit scoring use case when expert designed (ED) features are excluded (a) and included (b). | a | b
---|---|---
Algorithm | Base | EFC | Base | EFC
DT | 83.38 (±12.48) | 90.10 (±4.90) | 90.51 (±6.59) | 88.30 (±6.19)
NB | 50.63 (±6.48) | 82.43 (±8.01) | 68.99 (±6.15) | 90.57 (±6.23)
SVM-lin | 54.68 (±3.91) | 84.68 (±11.13) | 87.43 (±9.24) | 92.35 (±6.40)
SVM-RBF | 53.83 (±6.83) | 79.33 (±9.70) | 52.00 (±2.31) | 86,88 (±10.31)
kNN | 81.60 (±7.92) | 82.49 (±8.44) | 84.74 (±6.50) | 91.88 (±6.07)
FU | 81.94 (±13.06) | 91.03 (±4.07) | 88.77 (±6.17) | 91.42 (±5.18)
RF | 85.61 (±8.10) | 85.57 (±10.34) | 90.55 (±6.90) | 91.90 (±6.05)

To summarise, the findings in the financial use case show that _EFC is able to
construct useful human comprehensible features and significantly improves the
CA of several classifiers._

##  6 Conclusion

We presented a novel heuristic for reduction of search space in feature
construction. The proposed EFC method is based on explanations of predictive
models and reduces the search to groups of frequently co-occurring attributes
in explained instances. The method constructs meaningful, explainable features
which improve the interpretability of ML models and their prediction
performance. By limiting feature construction to these groups, we
significantly reduce the search space and allow feature construction for many
large datasets. The use case from the financial industry shows that EFC
generates many features similar or equivalent to the ones constructed by human
experts. Moreover, the domain expert assessed all the generated features
(rules and quotients) from the use-case domain as meaningful. Using EFC with
inherently interpretable ML models such as DT and NB improved their
performance, often to the level of complex black-box models such as XGBoost
and random forests. We have made the source code of EFC freely
available444https://github.com/bostjanv76/featConstr.

###  6.1 Limitations of the approach

The main limitation of the proposed approach is that the method fails when
there are no interactions between attributes in the dataset. The EFC method is
also sensitive to the settings of parameters, such as $noiseThr$ and the
number of discretisation intervals. If the $noiseThr$ parameter (the expected
noise in explanations affecting groups of co-occuring attributes) is set too
low, there is a risk of combinatorial explosion, especially with large
datasets. When constructing logical features from numerical attributes, the
potentially large number of discretisation intervals may increase the time and
space complexity of the FC process.

###  6.2 Future works

There are ample opportunities for future work. It seems sensible to test an
integration of feature complexity measures into the feature construction
process. This could further automate the feature construction process and
reduce the search space. Feature evaluation could be added during the FC
process for additional control of time and space complexity. We plan to
extensively test different parameters of EFC, including different explanation
methods. Since EFC uses many parameters, hyperparameter optimisation might
contribute to better performance. While we only use tabular data in
classification setting, we see no obstacles in applying the EFC approach to
regression problems and adapting it to the text classification. In the
financial use case, we used feature construction for both class values but a
more systematic analysis on multi-class problems should investigate the
effects of repeating the process for all classes. It would be interesting to
test EFC in domains like bioinformatics where are many interactive attributes
and fewer instances.

## CRediT authorship contribution statement

Boštjan Vouk: Conceptualisation, Methodology, Software, Validation, Formal
analysis, Visualisation, Writing - Original Draft. Matej Guid:
Conceptualisation, Validation, Writing - Review & Editing. Marko Robnik-
Šikonja: Conceptualisation, Methodology, Validation, Writing - Review &
Editing.

## Declaration of competing interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## Acknowledgements

The work was supported by the Slovenian Research Agency (ARRS) core research
programme P6-0411. We thank the domain expert (professor of finance) for
participating in the experiment, Saša Sirk for proofreading the paper, and
anonymous reviewers for useful comments.

##  Appendix A Additional results on the UCI datasets

Table 14: CA of the DT classifier on the UCI datasets: without feature
construction (Base), using only logical features (Log), relational features
(Rel), Cartesian product (Cart), decision rule and threshold features (DrThr),
all features (All), all with features selection (FS), exhaustive search (Exh),
Jakulin’s method (Jak), and ”upper bound” classifier XGBoost (XGB).

Dataset | Base | Log | Rel | Cart | DrThr | All | FS | Exh | Jak | XGB
---|---|---|---|---|---|---|---|---|---|---
Aus. credit | 86.09 | 83.62 | 85.36 | 85.36 | 86.38 | 85.22 | 84.64 | 83.62 | 85.51 | 86.81
Autos | 81.40 | 80.43 | 81.40 | 78.45 | 77.00 | 78.95 | 79.45 | - | 82.76 | 80.93
Balance scale | 76.65 | 81.93 | 98.08 | 79.05 | 82.57 | 86.89 | 89.12 | 91.54 | 78.57 | 88.80
Bank mark. | 88.98 | 89.52 | 88.96 | 88.83 | 89.43 | 89.32 | 88.98 | - | 89.71 | 89.78
Bio. resp. | 73.77 | 74.17 | 73.93 | 74.81 | 73.71 | 72.94 | 73.93 | - | 73.98 | 78.81
Car | 92.36 | 96.82 | 92.36 | 93.29 | 94.79 | 96.82 | 96.00 | 97.57 | 94.15 | 97.63
CNAE-9 | 88.80 | 89.44 | 88.98 | 88.80 | 88.89 | 89.44 | 88.89 | - | 89.07 | 91.85
Glass | 66.75 | 63.48 | 68.23 | 64.48 | 65.37 | 63.96 | 65.37 | 67.29 | 70.63 | 76.62
Heart | 76.67 | 80.00 | 77.04 | 79.63 | 80.37 | 78.52 | 80.00 | 81.85 | 79.26 | 80.74
Ionosphere | 91.46 | 92.32 | 87.17 | 91.46 | 91.17 | 92.32 | 92.32 | - | 89.75 | 93.75
Jap. credit | 85.94 | 82.75 | 86.23 | 84.64 | 87.39 | 85.51 | 87.39 | 84.06 | 86.09 | 87.54
Leukemia | 83.04 | 92.86 | 85.89 | 83.04 | 91.61 | 91.61 | 91.61 | - | 83.04 | 95.71
Liver dis. | 68.71 | 67.83 | 64.67 | 67.83 | 70.79 | 67.86 | 69.00 | 67.22 | 68.12 | 73.70
LSVT voice | 75.45 | 78.40 | 71.41 | 77.63 | 77.50 | 79.04 | 77.50 | - | 74.42 | 82.44
Lung cancer | 50.83 | 50.83 | 50.83 | 50.83 | 47.50 | 50.83 | 50.83 | - | 44.17 | 58.33
Mamm. mass | 82.10 | 82.21 | 82.62 | 81.48 | 83.66 | 82.00 | 82.52 | 82.21 | 81.79 | 83.46
Molecular | 80.82 | 85.73 | 80.82 | 75.36 | 89.55 | 85.73 | 83.82 | - | 80.82 | 87.64
Monks1 | 96.52 | 99.07 | 96.52 | 99.07 | 99.07 | 99.07 | 99.07 | 100.00 | 100.00 | 85.67
Monks2 | 67.14 | 95.62 | 67.14 | 67.14 | 66.21 | 95.62 | 93.78 | 92.86 | 67.14 | 87.30
Nursery | 97.05 | 98.50 | 97.05 | 96.06 | 98.36 | 98.52 | 98.38 | 99.51 | 96.50 | 99.94
Parkinsons | 80.50 | 84.66 | 80.00 | 81.55 | 89.26 | 87.79 | 86.79 | 88.71 | 86.71 | 93.34
QSAR | 82.37 | 83.31 | 83.51 | 84.36 | 83.79 | 83.70 | 82.18 | - | 82.57 | 86.64
Semeion | 75.32 | 77.03 | 75.32 | 75.51 | 76.33 | 76.40 | 76.02 | - | 75.51 | 91.15
Sonar | 71.17 | 74.00 | 72.14 | 73.10 | 74.07 | 72.17 | 72.19 | - | 68.71 | 83.60
Spambase | 92.98 | 92.81 | 93.33 | 92.81 | 92.87 | 92.94 | 92.85 | - | 92.52 | 95.35
Spect heart | 80.91 | 82.41 | 80.91 | 81.32 | 83.52 | 83.13 | 82.76 | 83.18 | 83.53 | 83.92
Spectf heart | 85.39 | 87.08 | 85.96 | 85.37 | 89.39 | 88.53 | 87.67 | - | 84.81 | 89.10
Tic-tac-toe | 84.55 | 97.60 | 84.55 | 74.22 | 97.91 | 97.39 | 97.18 | 96.87 | 78.60 | 98.33
Vehicle | 72.47 | 72.69 | 71.63 | 74.12 | 73.41 | 72.71 | 72.58 | - | 73.05 | 77.91
Voting | 96.33 | 96.33 | 96.33 | 95.87 | 96.33 | 96.33 | 96.33 | 94.96 | 96.33 | 95.63
Average | 81.08 | 83.78 | 81.61 | 80.85 | 83.27 | 84.04 | 83.97 | 83.52* | 81.26 | 86.75

Table 15: CA of the NB classifier on the UCI datasets: without feature
construction (Base), using only logical features (Log), relational features
(Rel), Cartesian product (Cart), decision rule and threshold features (DrThr),
all features (All), all with features selection (FS), exhaustive search (Exh),
Jakulin’s method (Jak), and ”upper bound” classifier XGBoost (XGB).

Dataset | Base | Log | Rel | Cart | DrThr | All | FS | Exh | Jak | XGB
---|---|---|---|---|---|---|---|---|---|---
Aus. credit | 77.54 | 85.51 | 78.26 | 84.78 | 86.09 | 86.67 | 85.80 | 85.07 | 82.61 | 86.81
Autos | 56.67 | 58.48 | 57.64 | 58.10 | 59.10 | 59.45 | 60.95 | - | 67.64 | 80.93
Balance scale | 90.39 | 76.17 | 88.97 | 82.89 | 78.26 | 78.26 | 90.39 | 79.37 | 82.73 | 88.80
Bank mark. | 86.88 | 78.04 | 86.93 | 86.88 | 87.28 | 77.88 | 86.88 | - | 86.07 | 89.78
Bio. resp. | 64.77 | 64.86 | 64.77 | 64.77 | 64.77 | 65.62 | 65.22 | - | 64.44 | 78.81
Car | 85.53 | 82.81 | 85.53 | 87.04 | 72.80 | 82.81 | 85.13 | 81.89 | 88.72 | 97.63
CNAE-9 | 93.15 | 92.41 | 92.96 | 92.78 | 92.96 | 92.50 | 92.59 | - | 91.94 | 91.85
Glass | 48.59 | 51.86 | 51.86 | 58.35 | 48.59 | 52.34 | 55.11 | 67.73 | 61.73 | 76.62
Heart | 83.70 | 83.33 | 83.70 | 82.22 | 84.07 | 83.70 | 84.81 | 82.22 | 80.74 | 80.74
Ionosphere | 82.62 | 90.60 | 85.45 | 92.03 | 89.47 | 90.60 | 92.60 | - | 88.89 | 93.75
Jap. credit | 77.68 | 85.07 | 79.42 | 84.64 | 86.52 | 85.51 | 86.23 | 84.49 | 82.32 | 87.54
Leukemia | 98.57 | 98.57 | 98.57 | 98.57 | 98.57 | 98.57 | 98.57 | - | 98.57 | 95.71
Liver dis. | 55.39 | 54.80 | 64.66 | 56.53 | 68.43 | 62.66 | 62.66 | 61.17 | 56.23 | 73.70
LSVT voice | 56.41 | 61.22 | 57.18 | 57.18 | 57.18 | 62.76 | 62.76 | - | 56.41 | 82.44
Lung cancer | 53.33 | 64.17 | 53.33 | 60.83 | 63.33 | 54.17 | 74.17 | - | 60.00 | 58.33
Mamm. mass | 78.36 | 82.83 | 77.53 | 82.21 | 83.04 | 82.62 | 82.73 | 82.83 | 80.75 | 83.46
Molecular | 90.27 | 92.36 | 90.27 | 90.27 | 88.45 | 92.36 | 91.36 | - | 91.45 | 87.64
Monks1 | 75.02 | 87.74 | 75.02 | 87.74 | 87.74 | 87.74 | 87.74 | 94.92 | 100.00 | 85.67
Monks2 | 66.44 | 53.23 | 66.44 | 53.22 | 62.25 | 52.76 | 65.98 | 53.25 | 53.48 | 87.30
Nursery | 90.32 | 54.80 | 90.32 | 88.13 | 78.87 | 53.85 | 90.22 | 89.86 | 87.25 | 99.94
Parkinsons | 69.34 | 80.18 | 69.34 | 76.61 | 78.13 | 81.24 | 82.26 | 80.66 | 70.84 | 93.34
QSAR | 75.94 | 79.24 | 77.46 | 79.35 | 81.71 | 79.71 | 79.71 | - | 78.11 | 86.64
Semeion | 85.56 | 64.84 | 85.56 | 81.23 | 84.74 | 61.89 | 85.25 | - | 86.00 | 91.15
Sonar | 67.88 | 74.57 | 70.26 | 75.10 | 72.19 | 77.00 | 76.52 | - | 72.69 | 83.60
Spambase | 79.29 | 88.18 | 79.57 | 80.09 | 80.18 | 89.05 | 88.98 | - | 80.00 | 95.35
Spect heart | 78.96 | 78.23 | 78.96 | 76.37 | 81.60 | 78.23 | 77.86 | 77.11 | 77.48 | 83.92
Spectf heart | 70.78 | 73.91 | 72.21 | 71.92 | 73.06 | 74.22 | 73.93 | - | 72.21 | 89.10
Tic-tac-toe | 69.62 | 72.65 | 69.62 | 70.36 | 79.22 | 73.28 | 72.03 | 71.93 | 70.15 | 98.33
Vehicle | 44.80 | 61.46 | 47.64 | 64.42 | 67.15 | 61.35 | 64.66 | - | 66.44 | 77.91
Voting | 90.14 | 94.27 | 90.14 | 93.36 | 94.95 | 95.42 | 94.73 | 91.06 | 90.36 | 95.63
Average | 74.80 | 75.55 | 75.65 | 77.27 | 77.69 | 75.81 | 79.93 | 76.35* | 77.54 | 86.75

Table 16: CA of the SVM classifier with linear kernel on the UCI datasets:
without feature construction (Base), using only logical features (Log),
relational features (Rel), Cartesian product (Cart), decision rule and
threshold features (DrThr), all features (All), all with features selection
(FS), exhaustive search (Exh), Jakulin’s method (Jak), and ”upper bound”
classifier XGBoost (XGB).

Dataset | Base | Log | Rel | Cart | DrThr | All | FS | Exh | Jak | XGB
---|---|---|---|---|---|---|---|---|---|---
Aus. credit | 84.64 | 82.32 | 84.93 | 83.62 | 86.67 | 82.32 | 85.22 | 77.10 | 83.33 | 86.81
Autos | 71.19 | 77.55 | 72.17 | 78.55 | 73.64 | 78.05 | 77.55 | - | 80.90 | 80.93
Balance scale | 87.68 | 86.25 | 93.76 | 86.09 | 94.07 | 96.48 | 95.67 | 96.79 | 87.20 | 88.80
Bank mark. | 89.29 | 89.67 | 89.29 | 89.63 | 89.38 | 89.65 | 89.52 | - | 89.85 | 89.78
Bio. resp. | 75.58 | 75.31 | 75.26 | 75.23 | 76.03 | 75.37 | 75.63 | - | 74.83 | 78.81
Car | 93.75 | 98.38 | 93.75 | 97.57 | 95.43 | 98.15 | 98.03 | 99.94 | 97.28 | 97.63
CNAE-9 | 94.17 | 93.80 | 93.89 | 93.89 | 94.17 | 93.80 | 93.70 | - | 92.41 | 91.85
Glass | 56.13 | 64.57 | 59.37 | 64.59 | 55.63 | 63.61 | 62.71 | 70.58 | 67.73 | 76.62
Heart | 84.07 | 81.11 | 82.22 | 81.48 | 81.85 | 80.00 | 82.59 | 77.04 | 84.07 | 80.74
Ionosphere | 88.60 | 92.32 | 90.60 | 92.89 | 92.60 | 91.74 | 91.46 | - | 91.48 | 93.75
Jap. credit | 84.93 | 83.04 | 84.49 | 84.20 | 87.10 | 84.06 | 84.93 | 76.81 | 82.90 | 87.54
Leukemia | 95.71 | 95.71 | 97.14 | 98.57 | 94.46 | 97.14 | 95.71 | - | 95.71 | 95.71
Liver dis. | 58.28 | 56.55 | 65.81 | 56.55 | 70.14 | 71.61 | 71.02 | 67.51 | 56.55 | 73.70
LSVT voice | 85.77 | 79.81 | 84.17 | 80.71 | 83.08 | 79.87 | 80.64 | - | 78.59 | 82.44
Lung cancer | 42.50 | 48.33 | 42.50 | 45.83 | 49.17 | 48.33 | 48.33 | - | 42.50 | 58.33
Mamm. mass | 79.29 | 83.14 | 81.68 | 82.42 | 83.14 | 82.52 | 81.48 | 82.31 | 81.79 | 83.46
Molecular | 93.27 | 87.45 | 93.27 | 90.36 | 91.36 | 87.45 | 89.27 | - | 94.27 | 87.64
Monks1 | 75.02 | 86.83 | 75.02 | 87.74 | 87.74 | 87.97 | 87.74 | 100.00 | 100.00 | 85.67
Monks2 | 67.14 | 95.39 | 67.14 | 95.40 | 67.14 | 95.39 | 88.45 | 100.00 | 68.30 | 87.30
Nursery | 93.13 | 97.30 | 93.13 | 97.15 | 93.01 | 97.30 | 97.23 | 99.97 | 95.32 | 99.94
Parkinsons | 87.18 | 80.03 | 87.68 | 82.13 | 89.32 | 87.29 | 86.79 | 87.18 | 83.13 | 93.34
QSAR | 85.59 | 83.50 | 84.55 | 83.50 | 85.12 | 85.22 | 84.55 | - | 84.83 | 86.64
Semeion | 93.85 | 93.60 | 93.85 | 93.72 | 94.10 | 92.90 | 93.66 | - | 94.04 | 91.15
Sonar | 75.95 | 76.98 | 76.93 | 79.38 | 77.43 | 74.50 | 76.90 | - | 79.43 | 83.60
Spambase | 90.41 | 91.31 | 90.00 | 91.33 | 91.18 | 91.72 | 91.37 | - | 91.35 | 95.35
Spect heart | 81.28 | 80.53 | 81.28 | 79.79 | 83.13 | 80.53 | 79.77 | 81.70 | 80.53 | 83.92
Spectf heart | 81.08 | 79.65 | 78.51 | 79.08 | 78.22 | 78.78 | 79.66 | - | 80.22 | 89.10
Tic-tac-toe | 98.33 | 99.69 | 98.33 | 98.95 | 98.64 | 99.79 | 99.90 | 99.58 | 98.33 | 98.33
Vehicle | 74.36 | 71.51 | 74.13 | 70.80 | 72.59 | 70.81 | 71.87 | - | 71.39 | 77.91
Voting | 95.87 | 96.33 | 95.87 | 96.56 | 96.33 | 96.33 | 96.10 | 95.40 | 95.64 | 95.63
Average | 82.13 | 83.60 | 82.69 | 83.92 | 83.73 | 84.62 | 84.58 | 84.97* | 83.46 | 86.75

Table 17: CA of the SVM classifier with RBF kernel on the UCI datasets:
without feature construction (Base), using only logical features (Log),
relational features (Rel), Cartesian product (Cart), decision rule and
threshold features (DrThr), all features (All), all with features selection
(FS), exhaustive search (Exh), Jakulin’s method (Jak), and ”upper bound”
classifier XGBoost (XGB).

Dataset | Base | Log | Rel | Cart | DrThr | All | FS | Exh | Jak | XGB
---|---|---|---|---|---|---|---|---|---|---
Aus. credit | 85.51 | 85.22 | 85.51 | 85.51 | 85.94 | 85.65 | 85.80 | 58.55 | 85.80 | 86.81
Autos | 46.31 | 56.12 | 45.81 | 48.26 | 46.79 | 56.12 | 56.12 | - | 52.10 | 80.93
Balance scale | 86.87 | 77.44 | 86.40 | 84.01 | 89.76 | 88.80 | 89.44 | 88.96 | 85.28 | 88.80
Bank mark. | 88.48 | 88.87 | 88.48 | 88.61 | 88.56 | 88.90 | 88.83 | - | 88.59 | 89.78
Bio. resp. | 78.22 | 78.54 | 78.35 | 78.43 | 78.54 | 78.62 | 78.27 | - | 78.65 | 78.81
Car | 84.66 | 93.40 | 84.66 | 90.34 | 87.10 | 93.35 | 93.87 | 75.75 | 88.31 | 97.63
CNAE-9 | 78.61 | 79.17 | 79.07 | 78.89 | 79.44 | 78.24 | 78.70 | - | 62.50 | 91.85
Glass | 35.52 | 58.90 | 41.10 | 59.39 | 40.63 | 58.90 | 58.03 | 70.13 | 61.80 | 76.62
Heart | 82.59 | 80.37 | 81.85 | 81.48 | 81.11 | 81.48 | 82.22 | 85.19 | 81.85 | 80.74
Ionosphere | 76.37 | 91.77 | 86.61 | 92.89 | 90.60 | 91.77 | 91.75 | - | 89.78 | 93.75
Jap. credit | 85.51 | 85.51 | 85.51 | 84.93 | 86.38 | 85.80 | 86.09 | 59.13 | 85.22 | 87.54
Leukemia | 65.36 | 65.36 | 65.36 | 65.36 | 65.36 | 65.36 | 65.36 | - | 65.36 | 95.71
Liver dis. | 57.98 | 56.25 | 57.98 | 55.96 | 67.58 | 67.87 | 67.29 | 68.12 | 56.55 | 73.70
LSVT voice | 68.21 | 83.08 | 77.69 | 83.14 | 83.97 | 82.31 | 81.41 | - | 76.73 | 82.44
Lung cancer | 40.00 | 56.67 | 40.00 | 40.00 | 43.33 | 56.67 | 56.67 | - | 43.33 | 58.33
Mamm. mass | 77.94 | 82.52 | 79.61 | 82.62 | 83.56 | 82.31 | 81.90 | 82.62 | 83.56 | 83.46
Molecular | 92.36 | 58.73 | 92.36 | 91.27 | 91.27 | 57.82 | 90.36 | - | 92.36 | 87.64
Monks1 | 75.02 | 89.60 | 75.02 | 75.72 | 87.74 | 89.60 | 87.74 | 100.00 | 75.95 | 85.67
Monks2 | 67.14 | 66.68 | 67.14 | 67.14 | 67.14 | 66.45 | 67.36 | 66.90 | 67.14 | 87.30
Nursery | 92.27 | 81.20 | 92.27 | 95.60 | 93.69 | 73.82 | 93.52 | 95.88 | 94.05 | 99.94
Parkinsons | 75.39 | 84.68 | 75.39 | 84.63 | 90.37 | 86.21 | 87.24 | 83.58 | 81.00 | 93.34
QSAR | 66.35 | 78.48 | 74.80 | 78.49 | 81.62 | 82.37 | 82.46 | - | 78.77 | 86.64
Semeion | 94.92 | 91.15 | 94.92 | 93.97 | 94.73 | 87.51 | 94.85 | - | 94.98 | 91.15
Sonar | 68.83 | 76.48 | 74.14 | 76.90 | 76.40 | 76.95 | 76.00 | - | 77.45 | 83.60
Spambase | 74.61 | 89.00 | 84.98 | 88.61 | 88.42 | 89.33 | 89.50 | - | 84.39 | 95.35
Spect heart | 79.42 | 81.64 | 79.42 | 82.04 | 82.41 | 82.39 | 82.39 | 82.81 | 79.42 | 83.92
Spectf heart | 72.78 | 73.64 | 72.78 | 72.21 | 78.50 | 77.93 | 77.93 | - | 73.92 | 89.10
Tic-tac-toe | 76.41 | 73.93 | 76.41 | 91.33 | 97.18 | 69.22 | 94.99 | 65.34 | 75.68 | 98.33
Vehicle | 39.48 | 65.24 | 48.10 | 67.38 | 66.56 | 65.95 | 68.32 | - | 65.72 | 77.91
Voting | 94.50 | 95.87 | 94.50 | 95.64 | 95.64 | 96.10 | 95.64 | 91.73 | 94.73 | 95.63