# On Finding Bi-objective Pareto-optimal Fraud Prevention Rule Sets for
Fintech Applications

Chengyao Wen  Ant GroupChengduChina<EMAIL_ADDRESS>and  Yin Lou
Ant GroupSunnyvale, CAUSA<EMAIL_ADDRESS>
(2018)

###### Abstract.

Rules are widely used in Fintech institutions to make fraud prevention
decisions, since rules are highly interpretable thanks to their intuitive if-
then structure. In practice, a two-stage framework of fraud prevention
decision rule set mining is usually employed in large Fintech institutions.
This paper is concerned with finding high-quality rule subsets in a bi-
objective space (such as precision and recall) from an initial pool of rules.
To this end, we adopt the concept of Pareto optimality and aim to find a set
of non-dominated rule subsets, which constitutes a Pareto front. We propose a
heuristic-based framework called PORS and we identify that the core of PORS is
the problem of solution selection on the front (SSF). We provide a systematic
categorization of the SSF problem and a thorough empirical evaluation of
various SSF methods on both public and proprietary datasets. We also introduce
a novel variant of sequential covering algorithm called SpectralRules to
encourage the diversity of the initial rule set and we empirically find that
SpectralRules further improves the quality of the found Pareto front. On two
real application scenarios within Alipay, we demonstrate the advantages of our
proposed methodology compared to existing work.

multi-objective optimization, Pareto front, rule subset selection

††copyright: acmcopyright††journalyear: 2018††doi:
XXXXXXX.XXXXXXX††conference: Make sure to enter the correct conference title
from your rights confirmation emai; June 03–05, 2018; Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06††ccs: Computing methodologies Rule
learning

##  1\. Introduction

Fraud prevention is an important task in Fintech applications. Fraudulent
activities usually include identity theft, money laundering, fraudulent
payment transactions, etc. Whenever a fraud is committed, the loss is not only
incurred by the victim who is exploited, but the reputation of the financial
institution involved also takes a hit.

In many Fintech fraud prevention applications, interpretability is usually a
must-have requirement in addition to predictive accuracy. Therefore, rule-
based models are widely used for such applications to make fraud prevention
decisions, since rules can offer intuitive representation of knowledge, thanks
to their simple if-then structure. In practice, decision rule sets (also known
as disjunctive normal form) are often favored over decision rule list due to
their flatter representation (Lakkaraju et al., 2016); rule set models make
positive prediction for a transaction whenever any rule in the set is
satisfied. During any stage in a transaction, whenever an alert is made from
the rule set (i.e., at least one rule predicts positive on this transaction),
the transaction is interrupted and the user may be asked to submit additional
information to verify the legitimacy for this transaction.

In practice, a two-stage framework of rule set mining is commonly employed in
Fintech institutions (e.g., Alipay111https://www.alipay.com/) (Li et al.,
2022). In Stage 1, a (potentially large) pool of rules is generated. Stage 2
is to produce a refined rule subset according to some criteria. Note that in
this paper we use rule set to refer to rules generated by Stage 1 and rule
subset to refer to a refined subset of the initial pool of rules _after_ Stage
1.

There are many methods for generating the initial pool of rules for Stage 1.
Tree based approaches, such as decision tree (Breiman et al., 1984; Quinlan,
1993) or random forests (Breiman, 2001), extract rules for each path in the
tree. Another class of approaches, on the other hand, focuses on direct rule
induction to form rule sets. Popular methods in this category include
sequential covering (Molnar, 2020) (e.g., CN2 (Clark and Niblett, 1989) and
RIPPER (Cohen, 1995)) and association rule mining (Agrawal et al., 1993).

For Stage 2, it is widely accepted that rule subsets are evaluated by their
precision and recall (Li et al., 2022). Precision in our context is negatively
correlated with the frequency that a user experiences an interruption for a
transaction, and recall relates to the amount of fraudulent activities that
can be prevented for a financial institution. Note that these two objectives
are naturally conflicting with each other, and in practice one either seeks to
maximize recall constrained on some level of precision (Li et al., 2022), or
combines the two metrics into a single generalized $F$ score that can balance
the effects of the two objectives. $F$ score uses a parameter $\beta$ to
control the contribution of the two inputs; $\beta$ is chosen such that recall
is considered $\beta$ times as important as precision (Van Rijsbergen, 1979).
A large $\beta$ weighs recall higher than precision and a small $\beta$ is
more biased towards precision. The commonly used $F_{1}$ score is just a
special case when $\beta=1$. For fraud prevention problems in Fintech
applications, typically a small $\beta$ (e.g., 0.1) is used to give more
weights on precision, since usually fraudulent ratio is low.

In practice, however, one rarely knows beforehand the best constraint
threshold or $\beta$ for a particular problem, and rule mining is an
_explorative_ and _iterative_ process. For example, one might experiment
multiple precision thresholds and choose the selected rule subset according to
subjective preferences or domain knowledge (Li et al., 2022). In such cases,
multiple trials of the rule subset selection algorithm are necessary, which is
quite time consuming. Therefore, in this work we aim to find a set of Pareto-
optimal solutions in a bi-objective space of precision and recall, i.e., rule
subsets in which one objective cannot be improved without worsening the other
one. A solution (rule subset) Pareto-dominates another one if both its
precision and recall are no worse and at least one is strictly better. The
image of this non-dominated solution set in the objective space is the so-
called Pareto front.

Finding Pareto-optimal rule subsets can be viewed as an intermediate step
between Stage 1 and Stage 2. It takes the initial pool of rules from Stage 1
and generates a set of non-dominated rule subsets. Finally, one can easily
experiment different precision thresholds or $\beta$ on the (already
generated) Pareto-optimal solution set and choose one as the final output for
Stage 2. For example, if the goal is to maximize recall constrained on
precision $>=$ 0.9, one can simply filter all Pareto-optimal solutions whose
precision is lower than 0.9 and choose the one with the highest recall.

The hypervolume indicator (HV) is one of the most widely used evaluation
metric for the quality of a Pareto front (Li and Yao, 2019). It measures the
“size of the dominated space” (Zitzler, 1999), and therefore our goal is to
find Pareto front of large HV. In this work, we mainly focus on a bi-objective
space of precision and recall, and measure the dominated space referenced by
(0, 0) (See Figure 1 for a visual example). Each solution on a Pareto front
forms a rule subset.

This problem can be solved by standard evolutionary multi-objective
optimization (EMO) algorithms, since bi-objective optimization is just a
special case (Li et al., 2015; Tanabe et al., 2017). Popular EMO algorithms
include NSGA-II (Deb et al., 2002), MOEA/D (Zhang and Li, 2007), etc. However,
we empirically find EMO algorithms are less efficient on our problem.

In this work, we propose a heuristic-based framework called PORS of finding
Pareto-optimal solutions for rule subset selection problem. PORS gradually
“expands” the Pareto front by adding one rule to a solution (rule subset) on
the front to see whether it expands the front (thereby improves HV), and it
terminates when no expansion of the current front can move the needle. Due to
the combinatorial nature of this problem, it is computationally expensive to
enumerate all rule subsets on the current Pareto front, and therefore we only
select a set of _representative_ solutions on the current front as candidates
for expansion to avoid exponential growth. We refer to this problem as
solution selection on the front (SSF).

A closely related problem of SSF is the so-called subset selection of Pareto-
optimal solutions, in which the goal is to reduce the number of solutions on a
Pareto front to a user specified number while achieving some desired
properties (e.g., a high HV approximation of the original Pareto front).
Popular methods of Pareto subset selection include HV-SS (Chen et al., 2021b),
IGD/IGD+-SS (Chen et al., 2021b), etc. Our motivation is different in that we
are interested in finding a small set of promising solutions to expand on the
current front so as to achieve a high HV when PORS terminates. We can,
nevertheless, employ existing algorithms in PORS.

Since finding a small set of most promising solutions to expand on the current
front is at the core of our framework, as one of our contributions, we propose
a systematic categorization of solutions to this problem, map existing methods
into different categories, and conduct a thorough empirical evaluation of
methods in each category for SSF problem to study their effects on the quality
of final Pareto front. If we think of the front as a “curve” in some space, we
can broadly classify methods into two categories; uniform or non-uniform
sampling on the “curve.” The space could be the objective space (e.g., bi-
objective space of precision and recall in this paper) which is usually a
coordinate system, or non-objective space (and therefore potentially non-
coordinate system) where only distance metric of two rule subsets is defined
(e.g., Jaccard distance between two rule subsets). Table 1 summarizes existing
methods and the methods proposed in this paper into each category.

Sampling | Space | Method
---|---|---
Uniform | Objective |  equi-spaced (Pereyra et al., 2013)
equi-dist (this paper)
Non-objective |  equi-jaccard (this paper)
Non- uniform | Objective |  hv-ss (Chen et al., 2021b)
igd-ss (Chen et al., 2021b)
igd+-ss (Chen et al., 2021b)
hvc-ss (this paper)
|  k-medoids-pr (Chen et al., 2021a)
Non-objective |  k-medoids-jaccard (this paper)
Table 1. Categorization of SSF methods.

Although there are benchmark studies on subset selection of Pareto-optimal
solutions (Shang et al., 2022) in the context of EMO, there is little research
of finding Pareto-optimal rule subsets; not only EMO-based methods but greedy
heuristic-based approaches considered in this paper as well. We believe our
work provides a valuable piece of research in this area. Our empirical study
on both public datasets and proprietary datasets from Alipay reveals that the
proposed hvc-ss is the best SSF method, which achieves highest HV on almost
all cases. In addition, we also propose a novel variant of the sequential
covering algorithm (Molnar, 2020) called SpectralRules that encourages the
diversity of rules for Stage 1; SpectralRules generates a set of rules with
different levels of precision and recall. We empirically find that
SpectralRules further improves HV, and benefits Stage 2 accordingly with final
rule subsets of higher quality.

In summary, we make the following contributions in this paper.

  * •

We propose a heuristic-based framework called PORS for finding Pareto-optimal
rule subsets in a bi-objective space. At the core of this framework is the SSF
problem.

  * •

We provide a systematic categorization of the SSF problem and a thorough
empirical evaluation of various SSF methods on both public and proprietary
datasets. We find that the proposed hvc-ss is the best method for our problem.

  * •

We propose a novel variant of the sequential covering algorithm called
SpectralRules to encourage the diversity of the initial pool rules, and
demonstrate on both public and proprietary datasets that SpectralRules further
improves HV.

  * •

We present two case studies of using PORS in this paper to produce fraud
prevention rule subsets for applications inside Alipay, and demonstrate the
advantages of our methodology compared to existing work.

  * •

We release a repository of code that can fully reproduce our results on public
datasets in this study to promote research efforts in this area (git, 2023).

The rest of this paper is organized as follows. Section 2 presents related
work. We present preliminaries in Section 3. Our approach is discussed in
Section 4. Experimental results are presented in Section 5 and we conclude the
paper in Section 6.

##  2\. Related Work

###  2.1. Rule Set Mining

There are generally two classes of approaches to generating rule sets. Tree
based approaches, such as decision tree (Breiman et al., 1984; Quinlan, 1993)
or random forests (Breiman, 2001), extract rules for each path in the tree or
tree ensemble. The other class of approaches focuses on direct rule induction
to form rule sets. Popular methods of this category include sequential
covering (Molnar, 2020) (e.g., CN2 (Clark and Niblett, 1989) and RIPPER
(Cohen, 1995)) and association rule mining (Agrawal et al., 1993). Recently
there is another line of research that focuses on the diversity of rule sets
(Lakkaraju et al., 2016; Zhang and Gionis, 2020). In practice, a two-stage
framework of rule set mining is used in Fintech institutions such as Alipay
(Li et al., 2022). The aforementioned methods are usually employed to generate
an initial rule set, followed by a rule subset selection procedure that
produces a refined rule subset according to some criteria.

###  2.2. Evolutionary Multi-Objective Optimization

The evolutionary multi-objective optimization (EMO) algorithm is a popular
choice for solving multi-objective optimization problems (Li et al., 2015;
Tanabe et al., 2017). EMO algorithms can be roughly classified into three
categories; dominance-based approach, decomposition-based approach and
indicator-based approach. Dominance based EMO algorithms commonly use Pareto
dominance relationship and distance-based density estimation in the objective
space for offspring generation and environmental selections. NSGA-II (Deb et
al., 2002) and SPEA2 (Zitzler et al., 2001) are well-known and widely used
dominance based EMO algorithms, which are believed to be very suitable for
problems under 4 objectives (Tanabe et al., 2017). Decomposition based
approach decomposes a given multi-objective problem into single-objective sub-
problems. MOEA/D is a representative decomposition based EMO algorithm (Zhang
and Li, 2007). Indicator based approaches employ a quantity indicator to
evaluate or rank solutions. Popular approaches in this category include SMS-
EMOA (Beume et al., 2007), HypE (Bader and Zitzler, 2011), etc. EMO algorithms
are, however, typically inefficient on large problems. This paper employs a
heuristic-based approach that achieves higher efficiency with better Pareto
fronts.

###  2.3. Subset Selection of Pareto-optimal Solutions

Since the number of Pareto-optimal solutions can be very large for
combinatorial optimization problems and infinity for continuous optimization
problems, subset selection of Pareto-optimal solutions is usually an essential
step. It is regarded as one of the most important topics in EMO domain, since
it is involved in many phases of EMO algorithms (Chen et al., 2021a, b). It is
also studied in the context of discrete approximation to the Pareto front for
continuous optimization problems (Pereyra et al., 2013). Some previous studies
favor uniform sampling of the Pareto front (Pereyra et al., 2013) while others
favor non-uniform sampling (Chen et al., 2021a, b; Guerreiro et al., 2020).

In this work, we further extend this categorization into 4 categories as
listed in Table 1, which is not revealed in existing literature. Under this
view, we present 4 new methods (one for each category) and perform a thorough
empirical evaluation on both public and proprietary datasets in the context of
fraud prevention rule set mining for Fintech applications.

##  3\. Preliminaries

Let $\mathcal{D}=\\{(\boldsymbol{x}_{i},y_{i})\\}_{i=1}^{N}$ denote a dataset
of size $N$, where $\boldsymbol{x}_{i}=(x_{i1},...,$ $x_{ip})$ is a feature
vector with $p$ features for a transaction, and $y_{i}\in\\{0,1\\}$ indicates
whether the corresponding transaction is reported fraud or not. We use
$\mathcal{P}=\\{i|y_{i}=1\\}$ to denote the set of points with positive
labels. We use $\delta=|\mathcal{P}|/N$ to denote the positive ratio of
$\mathcal{D}$.

A rule $r$ has two parts; a conjunction of conditions and a prediction. A
condition is of the form (feature, operator, value), e.g., age > 50\. A rule
makes a certain prediction when all conditions are satisfied for a given
$\boldsymbol{x}_{i}$. In this case, we say the rule covers
$\boldsymbol{x}_{i}$. Since typically the positive ratio $\delta$ for fraud in
Fintech applications is very low, we only consider positive-class rules.
Hence, $r(\boldsymbol{x}_{i})=1$ iff $r$ covers $\boldsymbol{x}_{i}$.

A rule set $\mathcal{R}$ makes a positive prediction on $\boldsymbol{x}_{i}$
if there exists a rule $r\in\mathcal{R}$ such that $r(\boldsymbol{x}_{i})=1$.
We use $\mathcal{D}(\mathcal{R})=\\{i|R(\boldsymbol{x}_{i})=1\\}$ to denote
the set of data points covered by $\mathcal{R}$.

###### Definition 3.1 (Precision).

We define the precision of a rule set $\mathcal{R}$ as the percentage that
$\mathcal{R}$ correctly finds fraud,

(1)
$\displaystyle\mbox{Prec}(\mathcal{R})=\frac{|\mathcal{D}(\mathcal{R})\cap\mathcal{P}|}{|\mathcal{D}(\mathcal{R})|}.$

###### Definition 3.2 (Recall).

We define the recall of a rule set $\mathcal{R}$ as the ratio of the frauds
covered by $\mathcal{R}$ among all fraudulent transactions,

(2)
$\displaystyle\mbox{Rec}(\mathcal{R})=\frac{|\mathcal{D}(\mathcal{R})\cap\mathcal{P}|}{|\mathcal{P}|}.$

###### Definition 3.3 ($F_{\beta}$ score).

The general $F_{\beta}$ score of precision and recall is defined as,

(3) $\displaystyle
F_{\beta}=(1+\beta^{2})\frac{\mbox{precision}\times\mbox{recall}}{(\beta^{2}\times\mbox{precision})+\mbox{recall}}.$

A large $\beta$ weighs recall higher than precision, and a small $\beta$
weighs precision higher than recall. For fraud prevention problems in Fintech
applications, typically a small $\beta$ (e.g., 0.1) is used to give more
weights on precision, since usually the positive ratio (fraudulent ratio) is
low.

Given a rule set $\mathcal{R}$, this paper is mostly concerned with finding
high-quality rule subsets of $\mathcal{R}$ in this bi-objective space of
precision and recall.222Nevertheless, our methodology can be easily extended
to metrics other than precision and recall. To this end, we first introduce
the concept of Pareto dominance.

###### Definition 3.4 (Pareto dominance).

A rule subset $\mathcal{R}_{1}$ is dominated by another rule subset
$\mathcal{R}_{2}$ if
$\mbox{Prec}(\mathcal{R}_{1})\leq\mbox{Prec}(\mathcal{R}_{2})\wedge\mbox{Rec}(\mathcal{R}_{1})\leq\mbox{Rec}(\mathcal{R}_{2})$
with at least one objective dimension (precision or recall) is strictly
better. Under the context of Pareto dominance, we use rule subset and solution
interchangeably.

###### Definition 3.5 (Pareto optimality).

A set of solutions (rule subsets) is called Pareto-optimal if no solution
Pareto-dominates another.

PrecisionRecall$(0,0)$ Figure 1. Illustration of Pareto dominance. A set of 5
non-dominated solutions (green square) constitutes the Pareto front (red
line). Hypervolume of those 5 solutions is the size of the light yellow
region. The hypervolume contribution of the solution (red square) to those 5
solutions is the size of the light grey region.

###### Definition 3.6 (Hypervolume Indicator).

Given a solution set $\mathcal{S}$ in a bi-objective space of precision and
recall, the hypervolume indicator $HV(\mathcal{S})$ is the measure of region
dominated by $\mathcal{S}$, referenced by (0, 0).

Note that Pareto optimality only defines the situation where no solution can
Pareto-dominate another _within_ a solution set. One can, nevertheless,
compare two sets of solutions that are both Pareto-optimal (via HV).

###### Definition 3.7 (Hypervolume Contribution).

Given two solution sets $\mathcal{S}$ and $\mathcal{T}$ in a bi-objective
space of precision and recall, the hypervolume contribution of $\mathcal{T}$
to $\mathcal{S}$ referenced by (0, 0) is,

(4) $\displaystyle
HVC(\mathcal{T},\mathcal{S})=HV(\mathcal{T}\cup\mathcal{S})-HV(\mathcal{S}\setminus\mathcal{T}).$

Figure 1 illustrates a set of 5 non-dominated solutions (green square) in a
precision-recall space, which constitutes the Pareto front (red line).
Hypervolume of those 5 solutions is the size of the light yellow region. The
hypervolume contribution of a new solution (red square) to those 5 solutions
is the size of the light grey region.

##  4\. Our Approach

In this section, we describe our methodology for finding Pareto-optimal rule
subsets given an initial pool of rules $\mathcal{R}$. We first introduce a
heuristic-based framework called PORS that gradually “expands” the Pareto
front (Section 4.1). We identify solution selection on the front (SSF) as the
core problem of this framework, and provide a systematic categorization of
this problem. In Section 4.2, we map existing work into different category,
and present new methods in each category. In addition, we introduce a novel
variant of sequential covering algorithm called SpectralRules that encourages
the diversity of the initial pool of rules $\mathcal{R}$ for Stage 1 in
Section 4.3.

###  4.1. The PORS Framework

PORS gradually “expands” the current Pareto front by adding one rule to a
solution (rule subset) on the front to form a new set of solutions. Due to the
combinatorial nature of this problem, it is computationally expensive to
enumerate all rule subsets on the current Pareto front, and therefore we only
select a set of _representative_ solutions on the current front as candidates
for expansion. We refer to this problem as solution selection on the front
(SSF).

Algorithm 1 summarizes the proposed PORS framework for finding Pareto-optimal
rule subsets given an initial pool of rules $\mathcal{R}$. The framework
starts with singleton sets for each rule in $\mathcal{R}$, and then makes them
a Pareto front via makePF procedure by retaining only non-dominated solutions
(Line 1). PORS applies some SSF method to sample $k$ solutions on the current
front in order to avoid exponential growth (Line 5). Those $k$ solutions are
then expanded by adding one rule from the initial pool of rules $\mathcal{R}$
to form new solutions (Line 6-10). The expanded solutions are then put
together with the solutions from last front to form a new Pareto front by
retaining only non-dominated solutions (Line 11). The framework terminates
when the current Pareto front does not change after expansion (Line 12),
otherwise the current front is ready for the next iteration (Line 13).

Algorithm 1 The Pareto Optimal Rule Subset Selection Framework

1:$\mathcal{F}\leftarrow\textsc{makePF}(\\{\\{r\\}|r\in\mathcal{R}\\})$

2:converged $\leftarrow\texttt{false}$

3:while not converged do

4: converged $\leftarrow\texttt{true}$

5: $\mathcal{F}_{0}\leftarrow\textsc{SSF}(\mathcal{F},k)$

6: $\mathcal{F}^{\prime}\leftarrow\emptyset$

7: for $S\in\mathcal{F}_{0}$ do

8: for $r\in\mathcal{R}$ do

9: $S^{\prime}\leftarrow S\cup\\{r\\}$

10: $\mathcal{F}^{\prime}\leftarrow\mathcal{F}^{\prime}\cup\\{S^{\prime}\\}$

11:
$\mathcal{F}^{\prime}\leftarrow\textsc{makePF}(\mathcal{F}^{\prime}\cup\mathcal{F})$

12: $\texttt{converged}\leftarrow\mathcal{F}^{\prime}==\mathcal{F}$

13: $\mathcal{F}\leftarrow\mathcal{F}^{\prime}$ return $\mathcal{F}$

It is obvious that the performance of PORS is largely affected by the efficacy
of the SSF method, and therefore we discuss different candidate SSF methods in
the next Section.

###  4.2. SSF Methods

We broadly classify SSF methods into two categories; uniform or non-uniform
sampling on the “curve” of a Pareto front. Under each category, we identify
two sub-categories depending on whether the “distance measure” is in the
original objective space or not.

####  4.2.1. Uniform Sampling

We first discuss methods by uniform sampling in the objective space. We
consider two methods in this paper as follows.

  * •

equi-spaced (Pereyra et al., 2013). (Pereyra et al., 2013) considers uniform
sampling of the Pareto front in the objective space on continuous problems. In
our problem, it is equivalent to uniform sampling of $k$ solutions by walking
along a Pareto front curve with roughly the same Manhattan distance for two
consecutive samples.

  * •

equi-dist. Following the same idea, we consider in this work uniform sampling
of $k$ solutions on a Pareto front with roughly the same Euclidean distance
for two consecutive samples.

|
---|---
(a) equi-spaced | (b) equi-dist
Figure 2. Illustration of sampled solutions (green squares) by equi-spaced and
equi-dist. equi-spaced uniformly samples solutions by walking along a Pareto
front curve (red line) with roughly the same Manhattan distance. equi-dist
uniformly samples solutions on a curve with roughly the same Euclidean
distance.

Figure 2 illustrates sampled solutions from equi-spaced and equi-dist. The
main difference is whether the distance is measured on curve (Manhattan) or
not (Euclidean).

We now describe a method called equi-jaccard that performs uniform sampling in
non-objective space. We employ Jaccard distance to measure the dissimilarity
between the coverage of two rule subsets. Formally, for two rule subsets
$\mathcal{R}_{1}$ and $\mathcal{R}_{2}$, their Jaccard distance is defined as
$\texttt{Jaccard}(\mathcal{R}_{1},\mathcal{R}_{2})=1-\frac{|\mathcal{D}(\mathcal{R}_{1})\cap\mathcal{D}(\mathcal{R}_{2})|}{|\mathcal{D}(\mathcal{R}_{1})\cup\mathcal{D}(\mathcal{R}_{2})|}$.

Since this is a non-coordinate system, we think of all solutions on a Pareto
front as a clique where edges between two solutions are weighed by their
Jaccard distance. Now we can generate a traversal of all solutions on this
graph to form a “curve” in this space, and then apply the same idea of equi-
spaced so that Jaccard distance is roughly the same for two consecutive
samples. There are many ways to perform a traversal. We can perform depth-
first search on this graph to minimize or maximize the Jaccard distance of the
overall path. We can also search for minimum sum of Jaccard distance of the
traversal using the travelling salesperson (TSP) algorithm.333TSP generates a
loop with minimized overall distance. We cut the edge with the largest Jaccard
distance on the loop to form a traversal path. During our early investigation,
we found that different methods lead to similar HV performance of the final
Pareto front generated by PORS. Therefore, we only report results of equi-
jaccard on a traversal generated by TSP algorithm.

####  4.2.2. Non-uniform Sampling

We consider the following methods of non-uniform sampling in the objective
space.

  * •

hv-ss (Chen et al., 2021b). hv-ss aims to select $k$ solutions so that their
hypervolume is maximized.

  * •

igd/igd+-ss (Chen et al., 2021b). igd/igd+-ss aims to select $k$ solutions so
that their Inverted Generational Distance (IGD) or Inverted Generational
Distance plus (IGD+) is minimized.

  * •

hvc-ss. In this work, we propose to select $k$ solutions so that their
hypervolume contribution to the Pareto front in the last iteration is
maximized. This is achieved using a greedy forward stepwise method to select
$k$ solutions.

  * •

k-medoids-pr (Chen et al., 2021a) (or k-med.-pr for short). This is the
standard $k$-medoids clustering performed in the objective space (of precision
and recall), with distance measured by Euclidean distance.

We also consider $k$-medoids clustering performed on Jaccard distance measure,
and introduce a non-uniform sampling in non-objective space method called
k-medoids-jaccard (or k-med.-j. for short).

Since all those SSF methods have very efficient implementation, the complexity
of each iteration of PORS is dominated by $O(k|\mathcal{R}|+c)$, where
$\mathcal{R}$ is the set of initial rules and $c$ denotes the complexity of
computing Pareto front (for Line 13 in Algorithm 1, and its worst case
complexity is usually quadratic). Note that the time complexity mainly depends
on the number of input rules, and depends less on dataset size. As we will see
in Section 5.3.2, empirically we found all SSF methods are very efficient for
different values of $k$.

Some of the aforementioned methods are studied in previous research in the
context of EMO on continuous problems (Shang et al., 2022), but there is
little research of all those 9 methods (covering 4 categories of the SSF
problem) for combinatorial problems of finding Pareto-optimal rule subsets
considered in this paper. To this end, we provide a thorough evaluation of
those 9 methods in Section 5.

###  4.3. SpectralRules

The quality of initial rule set from Stage 1 may also impact the performance
of Pareto-optimal rule subset selection. Existing approaches employ variants
of tree ensemble to extract the initial rule set (Li et al., 2022), which may
generate a lot of “homogeneous” rules that look alike each other. Therefore,
we introduce in this work a novel variant of sequential covering algorithm
called SpectralRules to promote the diversity of the initial pool of rules for
Stage 1.

We first review the sequential covering algorithm. Sequential covering is a
“separate-and-conquer” procedure that repeatedly learns a single rule to
create a rule set that covers the entire dataset rule by rule (Lakkaraju et
al., 2016). Algorithm 2 summarizes the classic sequential covering algorithm
used in this work. We start with empty rule set $\mathcal{R}$ and whole
dataset $\mathcal{D}$ (Line 2-3). We iteratively learn a rule $r$ using
standard rule induction that employs $F_{\beta}$ as the evaluation metric to
grow a rule up to a pre-specified length $len$, and then remove all points
covered by $r$ from the remaining dataset, until we find $n$ rules (Line 4-7).

Algorithm 2 Sequential Covering

1:procedure SequentialCovering($\mathcal{D}$, $n$, $len$, $\beta$)

2: $\mathcal{R}\leftarrow\emptyset$

3: $\mathcal{D}^{\prime}\leftarrow\mathcal{D}$

4: for $i=1$ to $n$ do

5: $r\leftarrow\textsc{RuleInduction}(len,\beta,\mathcal{D}^{\prime})$

6:
$\mathcal{D}^{\prime}\leftarrow\mathcal{D}^{\prime}\setminus\\{\boldsymbol{x}~{}|~{}r~{}\mbox{covers}~{}\boldsymbol{x},\boldsymbol{x}\in\mathcal{D}^{\prime}\\}$

7: $\mathcal{R}\leftarrow\mathcal{R}\cup\\{r\\}$ return $\mathcal{R}$

Algorithm 3 SpectralRules

1:procedure SpectralRules($\mathcal{D}$, $n$, $len$, $\mathcal{B}$)

2: $\mathcal{R}\leftarrow\emptyset$

3: for $\beta\in\mathcal{B}$ do

4:
$\mathcal{R}\leftarrow\mathcal{R}\cup\textsc{SequentialCovering}(\mathcal{D},\left\lceil\frac{n}{|\mathcal{B}|}\right\rceil,len,\beta)$
return $\mathcal{R}$

A very small $\beta$ (e.g., 0.1) can be employed to focus on mining high
precision rules. However, recall of the rules produced by sequential covering
might be quite limited in this case. As a result, we may end up with many
rules of high precision and low recall, leading to a suboptimal rule set. To
this end, we propose SpectralRules to encourage the diversity among rules. By
diversity we mean rules of different level of precision and recall. This is
achieved through multiple trials of Algorithm 2 with $\beta$ ranging from
small number (such as 0.01) to large number (such as 1).

Algorithm 3 summarizes the SpectralRules procedure. We are given a set
$\mathcal{B}$ with multiple $\beta$’s. For each $\beta\in\mathcal{B}$, we run
Algorithm 2 with this specific $\beta$ to generate at most
$\left\lceil\frac{n}{|\mathcal{B}|}\right\rceil$ rules (Line 3-4). The
resulting rule set $\mathcal{R}$ is composed of rules with different level of
precision and recall. In this paper, we fix
$\mathcal{B}=\\{0.01,0.02,0.04,0.06,0.08,0.10,0.20,0.40,0.60,0.80\\}$ and as
we will see in our experiments, SpectralRules usually leads to Pareto fronts
with higher HV (Section 5.2), and benefits Stage 2 accordingly with final rule
subsets of higher quality (Section 5.4).

##  5\. Experiments

We report our results on both public datasets and proprietary datasets from
Alipay. We release a repository of code that can fully reproduce the results
(including tables and figures) in this section on public datasets (git, 2023).

Dataset | Size | Attributes | Pos. Rate
---|---|---|---
Default | 30,000 | 24 | 22.12%
Credit | 150,000 | 11 | 6.68%
Fraud | 284,807 | 31 | 0.17%
Bank | 45,211 | 17 | 11.70%
A1 | 6,609,266 | 731 | $\delta_{1}$
A2 | 990,798 | 210 | $\delta_{2}$
A3 | 9,837,541 | 176 | $\delta_{3}$
Table 2. Datasets.

###  5.1. Datasets

Table 2 summarizes the datasets used in our experiments. We use 4 public
Fintech-related datasets in this paper. “Default” and “Bank” are from the UCI
repository.444http://archive.ics.uci.edu/ml/ “Credit” is a binary
classification problem that predicts the probability that somebody will
experience financial distress in the next two
years.555https://www.kaggle.com/c/GiveMeSomeCredit/data “Fraud” is a Kaggle
competition problem that aims to recognize fraudulent credit card
transactions.666https://www.kaggle.com/mlg-ulb/creditcardfraud

“A1”, “A2” and “A3” are three proprietary fraud prevention problems inside
Alipay, representing three different fraudulent activities such as fraudulent
payment transactions, identity theft, etc. Those datasets are large in scale
and we do not reveal the positive ratio of each proprietary dataset by using
$\delta$ to symbolize the actual number.

###  5.2. Pareto-optimal Rule Subsets Evaluation

We first conduct a thorough evaluation of finding Pareto-optimal rule subsets.
We consider classical EMO algorithm NSGA-II (Deb et al., 2002) which is
believed to perform well for bi-objective optimization problems (Tanabe et
al., 2017).777We use pyMultiobjective package at
https://github.com/Valdecy/pyMultiobjective Following standard practice (Chen
et al., 2021b), we equip NSGA-II with an unbounded external archive (UEA) to
store all non-dominated solutions examined during the execution of the
algorithm. We found that NSGA-II with UEA consistently achieves higher
performance. We set the parameter $mutation\\_rate$ to 0.02 and $generations$
to 1000 while using default values for other parameters. We observe this
parameter setup often achieves the best results for NSGA-II. For our PORS
framework, we consider all SSF methods listed in Section 4.2 to implement the
framework. We use $k=10$ as the number of samples for SSF, which is the only
parameter to set for SSF methods.

We consider two candidates for generating the initial rule set in Stage 1. We
follow the same approach in (Li et al., 2022) that uses a variant of tree
ensemble (called TreeEns). We also employ SpectralRules proposed in this paper
to generate the initial set of rules. For both methods, maximum rule length is
fixed to 6 and we generate (up to) 500 rules from each method to form the
initial rule set $\mathcal{R}$.

We use hypervolume indicator (HV) to measure the quality of Pareto-optimal
rule subsets. For all experiments, we randomly partition the dataset into
training (60% of the data), validation (20% of the data) and test sets (20% of
the data). We generate the initial rule set in Stage 1 using training set. We
then apply our 9 PORS algorithms and NSGA-II on the training set, select the
best Pareto front with highest HV on the validation set and collect its HV on
test set. All experiments are repeated 5 times and we report mean and standard
deviation of the evaluation results on test sets.

Type | Method | Default | Credit | Fraud | Bank | A1 | A2 | A3
---|---|---|---|---|---|---|---|---
EMO |  NSGA-II (Deb et al., 2002) |  0.524$\pm$0.013 |  0.322$\pm$0.023 |  0.786$\pm$0.027 |  0.533$\pm$0.018 |  0.296$\pm$0.010 |  0.169$\pm$0.006 |  0.032$\pm$0.006
unif. | obj. |  equi-spaced (Pereyra et al., 2013) |  0.515$\pm$0.008 |  0.323$\pm$0.021 |  0.783$\pm$0.020 |  0.517$\pm$0.020 |  0.299$\pm$0.011 |  0.172$\pm$0.006 |  0.033$\pm$0.006
equi-dist |  0.517$\pm$0.010 |  0.324$\pm$0.022 |  0.786$\pm$0.021 |  0.528$\pm$0.014 |  0.298$\pm$0.010 |  0.173$\pm$0.006 |  0.034$\pm$0.006
non-obj. | equi-jaccard |  0.509$\pm$0.007 |  0.308$\pm$0.018 |  0.789$\pm$0.032 |  0.516$\pm$0.019 |  0.296$\pm$0.012 |  0.166$\pm$0.009 |  0.033$\pm$0.006
non- unif. | obj. |  hv-ss (Chen et al., 2021b) |  0.519$\pm$0.009 |  0.325$\pm$0.022 |  0.783$\pm$0.037 |  0.530$\pm$0.021 |  0.298$\pm$0.007 |  0.165$\pm$0.007 |  0.034$\pm$0.005
igd-ss (Chen et al., 2021b) |  0.496$\pm$0.012 |  0.297$\pm$0.023 |  0.790$\pm$0.038 |  0.499$\pm$0.021 |  0.297$\pm$0.012 |  0.163$\pm$0.006 |  0.031$\pm$0.007
igd+-ss (Chen et al., 2021b) |  0.491$\pm$0.010 |  0.281$\pm$0.018 |  0.789$\pm$0.031 |  0.480$\pm$0.025 |  0.289$\pm$0.011 |  0.147$\pm$0.008 |  0.027$\pm$0.004
hvc-ss | 0.524$\pm$0.011 | 0.325$\pm$0.022 | 0.798$\pm$0.040 | 0.533$\pm$0.015 | 0.301$\pm$0.012 | 0.176$\pm$0.006 | 0.036$\pm$0.006
|  k-medoids-pr (Chen et al., 2021a) |  0.501$\pm$0.013 |  0.303$\pm$0.025 |  0.785$\pm$0.027 |  0.511$\pm$0.020 |  0.296$\pm$0.014 |  0.170$\pm$0.005 |  0.031$\pm$0.007
| non-obj. | k-medoids-jaccard |  0.472$\pm$0.016 |  0.258$\pm$0.035 |  0.792$\pm$0.034 |  0.479$\pm$0.026 |  0.284$\pm$0.012 |  0.142$\pm$0.006 |  0.024$\pm$0.010
Table 3. The hypervolume (HV) performance (mean$\pm$std) of the Pareto front for different methods on test set of each problem. Higher HV is better and best method for each dataset is marked in bold. TreeEns (Li et al., 2022) is employed in Stage 1 to produce the initial 500 rules. Type | Method | Default | Credit | Fraud | Bank | A1 | A2 | A3
---|---|---|---|---|---|---|---|---
EMO |  NSGA-II (Deb et al., 2002) |  0.526$\pm$0.013 |  0.350$\pm$0.011 |  0.789$\pm$0.036 |  0.585$\pm$0.011 |  0.313$\pm$0.004 |  0.188$\pm$0.005 |  0.033$\pm$0.004
unif. | obj. |  equi-spaced (Pereyra et al., 2013) |  0.534$\pm$0.012 |  0.350$\pm$0.014 |  0.796$\pm$0.037 |  0.570$\pm$0.009 |  0.313$\pm$0.006 |  0.183$\pm$0.007 |  0.035$\pm$0.006
equi-dist |  0.535$\pm$0.011 |  0.352$\pm$0.015 |  0.805$\pm$0.025 |  0.575$\pm$0.009 |  0.315$\pm$0.005 |  0.180$\pm$0.008 |  0.034$\pm$0.006
non-obj. | equi-jaccard |  0.535$\pm$0.014 |  0.357$\pm$0.014 |  0.803$\pm$0.028 |  0.577$\pm$0.013 |  0.314$\pm$0.009 |  0.176$\pm$0.008 |  0.034$\pm$0.007
non- unif. | obj. |  hv-ss (Chen et al., 2021b) |  0.534$\pm$0.011 |  0.357$\pm$0.016 |  0.801$\pm$0.033 |  0.582$\pm$0.008 |  0.318$\pm$0.004 |  0.184$\pm$0.006 |  0.035$\pm$0.005
igd-ss (Chen et al., 2021b) |  0.516$\pm$0.015 |  0.346$\pm$0.016 |  0.798$\pm$0.045 |  0.560$\pm$0.012 |  0.317$\pm$0.006 |  0.185$\pm$0.006 |  0.033$\pm$0.007
igd+-ss (Chen et al., 2021b) |  0.515$\pm$0.016 |  0.338$\pm$0.012 |  0.793$\pm$0.024 |  0.553$\pm$0.017 |  0.308$\pm$0.005 |  0.160$\pm$0.007 |  0.029$\pm$0.004
hvc-ss | 0.540$\pm$0.012 | 0.359$\pm$0.013 | 0.808$\pm$0.030 | 0.593$\pm$0.012 | 0.319$\pm$0.006 | 0.192$\pm$0.007 | 0.036$\pm$0.005
|  k-medoids-pr (Chen et al., 2021a) |  0.515$\pm$0.013 |  0.343$\pm$0.014 |  0.801$\pm$0.033 |  0.563$\pm$0.009 |  0.317$\pm$0.004 |  0.184$\pm$0.005 |  0.033$\pm$0.006
| non-obj. | k-medoids-jaccard |  0.507$\pm$0.016 |  0.333$\pm$0.011 |  0.791$\pm$0.030 |  0.521$\pm$0.014 |  0.301$\pm$0.011 |  0.151$\pm$0.006 |  0.028$\pm$0.008
Table 4. The hypervolume (HV) performance (mean$\pm$std) of the Pareto front
for different methods on test set of each problem. Higher HV is better and
best method for each dataset is marked in bold. SpectralRules is employed in
Stage 1 to produce the initial 500 rules.

Table 3 and 4 shows the HV results on test set for each dataset when the
initial rule set is generated by TreeEns and SpectralRules, respectively. We
first observe that PORS with hvc-ss as its SSF method consistently achieves
the highest HV for both cases. In addition, we also observe that employing
SpectralRules in Stage 1 leads to higher HV of the final Pareto front by
comparing the best values in Table 3 and 4. Therefore, we recommend
implementing PORS framework with hvc-ss as its SSF method, and with some abuse
of notation, we now refer to this particular combination as the PORS
algorithm.

Intuitive explanation of why hvc-ss performs the best. PORS framework can be
viewed as a greedy forward stage-wise algorithm, with maximizing HV as its
objective, by gradually expanding Pareto fronts. Among all SSF methods, hvc-ss
achieves the largest HV increase (by definition) for each iteration (Pareto
front expansion), and therefore it should work well inside PORS framework.
Because of the greedy nature of the framework, other SSF methods might also
work well. Our empirical study complements the picture and shows hvc-ss indeed
achieves the best results on most cases.

Dataset | k | hvc-ss | hv-ss | igd-ss | igd+-ss | k-med.-pr | k-med.-j. | equi-j. | equi-spaced | equi-dist
---|---|---|---|---|---|---|---|---|---|---
Bank | 5 |  0.575$\pm$0.009 | 0.583$\pm$0.011 |  0.531$\pm$0.014 |  0.502$\pm$0.025 |  0.549$\pm$0.012 |  0.493$\pm$0.022 |  0.552$\pm$0.012 |  0.555$\pm$0.009 |  0.561$\pm$0.01
10 | 0.591$\pm$0.012 |  0.580$\pm$0.009 |  0.546$\pm$0.017 |  0.539$\pm$0.016 |  0.562$\pm$0.010 |  0.512$\pm$0.013 |  0.564$\pm$0.015 |  0.571$\pm$0.009 |  0.571$\pm$0.010
15 | 0.596$\pm$0.011 |  0.582$\pm$0.010 |  0.564$\pm$0.013 |  0.553$\pm$0.014 |  0.566$\pm$0.008 |  0.533$\pm$0.018 |  0.567$\pm$0.012 |  0.574$\pm$0.006 |  0.577$\pm$0.008
20 | 0.594$\pm$0.011 |  0.583$\pm$0.010 |  0.561$\pm$0.011 |  0.554$\pm$0.013 |  0.571$\pm$0.011 |  0.531$\pm$0.011 |  0.568$\pm$0.014 |  0.574$\pm$0.006 |  0.578$\pm$0.008
Credit | 5 |  0.347$\pm$0.012 | 0.350$\pm$0.011 |  0.333$\pm$0.010 |  0.325$\pm$0.012 |  0.337$\pm$0.010 |  0.316$\pm$0.008 |  0.342$\pm$0.016 |  0.340$\pm$0.016 |  0.341$\pm$0.012
10 | 0.357$\pm$0.012 |  0.356$\pm$0.015 |  0.345$\pm$0.014 |  0.336$\pm$0.011 |  0.345$\pm$0.011 |  0.331$\pm$0.011 |  0.355$\pm$0.013 |  0.350$\pm$0.013 |  0.351$\pm$0.015
15 | 0.359$\pm$0.015 |  0.358$\pm$0.014 |  0.348$\pm$0.014 |  0.340$\pm$0.012 |  0.349$\pm$0.013 |  0.337$\pm$0.011 |  0.356$\pm$0.013 |  0.353$\pm$0.013 |  0.356$\pm$0.014
20 | 0.359$\pm$0.015 |  0.358$\pm$0.014 |  0.352$\pm$0.014 |  0.342$\pm$0.011 |  0.350$\pm$0.014 |  0.341$\pm$0.012 |  0.356$\pm$0.013 |  0.355$\pm$0.013 |  0.357$\pm$0.013
Default | 5 | 0.541$\pm$0.014 |  0.532$\pm$0.013 |  0.501$\pm$0.021 |  0.509$\pm$0.022 |  0.512$\pm$0.014 |  0.495$\pm$0.019 |  0.532$\pm$0.010 |  0.529$\pm$0.012 |  0.534$\pm$0.012
10 | 0.540$\pm$0.012 |  0.535$\pm$0.010 |  0.517$\pm$0.015 |  0.515$\pm$0.016 |  0.515$\pm$0.013 |  0.504$\pm$0.021 |  0.535$\pm$0.009 |  0.534$\pm$0.012 |  0.535$\pm$0.011
15 | 0.536$\pm$0.012 |  0.535$\pm$0.011 |  0.524$\pm$0.016 |  0.525$\pm$0.018 |  0.523$\pm$0.015 |  0.510$\pm$0.015 |  0.535$\pm$0.010 |  0.536$\pm$0.011 |  0.536$\pm$0.010
20 |  0.533$\pm$0.011 | 0.537$\pm$0.010 |  0.525$\pm$0.012 |  0.525$\pm$0.013 |  0.527$\pm$0.014 |  0.514$\pm$0.015 |  0.534$\pm$0.012 |  0.536$\pm$0.011 | 0.537$\pm$0.010
Fraud | 5 | 0.805$\pm$0.031 |  0.794$\pm$0.034 |  0.801$\pm$0.026 |  0.798$\pm$0.024 |  0.802$\pm$0.030 |  0.786$\pm$0.035 |  0.794$\pm$0.027 |  0.793$\pm$0.039 |  0.790$\pm$0.034
10 | 0.808$\pm$0.030 |  0.801$\pm$0.033 |  0.798$\pm$0.045 |  0.794$\pm$0.026 |  0.793$\pm$0.032 |  0.800$\pm$0.029 |  0.803$\pm$0.028 |  0.796$\pm$0.037 |  0.805$\pm$0.025
15 |  0.806$\pm$0.032 |  0.801$\pm$0.032 | 0.809$\pm$0.030 |  0.806$\pm$0.032 |  0.802$\pm$0.035 |  0.804$\pm$0.029 |  0.808$\pm$0.025 |  0.797$\pm$0.036 |  0.807$\pm$0.028
20 |  0.801$\pm$0.037 |  0.797$\pm$0.045 |  0.797$\pm$0.048 |  0.807$\pm$0.026 | 0.808$\pm$0.033 |  0.797$\pm$0.035 |  0.793$\pm$0.047 |  0.806$\pm$0.033 |  0.804$\pm$0.040
Table 5. The hypervolume (HV) performance (mean$\pm$std) of the Pareto front for different methods on test set of each problem. Higher HV is better. SpectralRules is employed in Stage 1 to produce the initial 500 rules. The maximum round running of PORS is set to 30 to avoid early stopping, i.e., each experiment trial fully completed 30 iterations. Dataset | k | hvc-ss | hv-ss | igd-ss | igd+-ss | k-med.-pr | k-med.-j. | equi-j. | equi-spaced | equi-dist
---|---|---|---|---|---|---|---|---|---|---
Bank | 5 |  47.36$\pm$2.00 |  47.36$\pm$2.00 |  46.71$\pm$0.80 |  47.09$\pm$2.13 |  44.85$\pm$0.94 |  59.33$\pm$3.25 |  48.10$\pm$4.76 |  44.02$\pm$1.68 |  44.65$\pm$1.73
10 |  64.27$\pm$4.08 |  53.61$\pm$3.08 |  57.44$\pm$2.16 |  58.02$\pm$2.95 |  53.62$\pm$3.05 |  73.65$\pm$2.70 |  65.63$\pm$2.55 |  52.64$\pm$2.19 |  52.21$\pm$2.59
15 |  83.45$\pm$4.23 |  57.56$\pm$1.82 |  69.57$\pm$4.38 |  66.63$\pm$3.65 |  60.31$\pm$3.89 |  93.31$\pm$3.93 |  73.08$\pm$1.16 |  55.72$\pm$1.29 |  56.26$\pm$2.15
20 |  113.47$\pm$4.22 |  62.71$\pm$1.11 |  80.73$\pm$4.80 |  75.91$\pm$1.23 |  62.19$\pm$2.07 |  110.80$\pm$4.50 |  81.95$\pm$4.08 |  62.28$\pm$2.74 |  61.53$\pm$2.47
Credit | 5 |  57.45$\pm$6.17 |  48.92$\pm$5.83 |  58.95$\pm$6.63 |  49.92$\pm$2.17 |  48.03$\pm$3.61 |  125.73$\pm$15.02 |  68.48$\pm$5.81 |  45.31$\pm$1.19 |  48.92$\pm$3.68
10 |  93.31$\pm$9.57 |  63.53$\pm$4.56 |  90.76$\pm$6.50 |  73.82$\pm$4.17 |  61.64$\pm$4.28 |  238.02$\pm$25.20 |  121.91$\pm$12.10 |  57.66$\pm$3.41 |  61.02$\pm$8.11
15 |  140.18$\pm$10.64 |  70.92$\pm$4.03 |  121.71$\pm$12.48 |  93.68$\pm$2.77 |  68.72$\pm$4.27 |  350.31$\pm$22.91 |  161.11$\pm$8.78 |  66.79$\pm$2.86 |  71.79$\pm$11.58
20 |  185.67$\pm$8.33 |  81.91$\pm$8.87 |  164.50$\pm$13.35 |  119.50$\pm$8.09 |  74.65$\pm$4.09 |  512.19$\pm$48.05 |  196.48$\pm$18.93 |  76.58$\pm$3.32 |  79.19$\pm$7.05
Default | 5 |  49.19$\pm$2.19 |  43.57$\pm$2.35 |  49.69$\pm$2.29 |  47.44$\pm$1.78 |  41.26$\pm$1.07 |  53.80$\pm$3.85 |  57.73$\pm$2.32 |  41.82$\pm$1.03 |  43.08$\pm$1.74
10 |  71.33$\pm$4.34 |  54.12$\pm$5.40 |  66.04$\pm$4.95 |  63.25$\pm$3.70 |  49.20$\pm$3.36 |  71.20$\pm$2.21 |  79.19$\pm$3.06 |  51.53$\pm$2.41 |  49.99$\pm$1.75
15 |  99.13$\pm$3.36 |  60.22$\pm$4.73 |  80.24$\pm$1.89 |  79.72$\pm$6.15 |  54.43$\pm$2.38 |  93.06$\pm$6.31 |  96.18$\pm$4.66 |  56.71$\pm$2.01 |  55.31$\pm$1.72
20 |  133.09$\pm$10.86 |  67.49$\pm$5.00 |  101.47$\pm$2.29 |  98.13$\pm$3.53 |  61.73$\pm$3.17 |  116.56$\pm$4.28 |  113.25$\pm$5.85 |  61.16$\pm$1.81 |  61.50$\pm$1.45
Fraud | 5 |  40.42$\pm$0.16 |  40.81$\pm$1.03 |  41.35$\pm$1.05 |  42.23$\pm$0.81 |  41.15$\pm$0.55 |  61.24$\pm$1.63 |  42.40$\pm$0.52 |  42.23$\pm$0.54 |  42.20$\pm$0.55
10 |  45.75$\pm$1.00 |  45.62$\pm$1.14 |  46.94$\pm$0.74 |  47.88$\pm$1.52 |  46.68$\pm$0.81 |  74.92$\pm$1.87 |  48.86$\pm$1.23 |  47.35$\pm$1.36 |  47.44$\pm$1.85
15 |  50.88$\pm$0.84 |  50.06$\pm$0.43 |  51.90$\pm$1.41 |  52.43$\pm$0.80 |  50.34$\pm$0.52 |  87.41$\pm$2.18 |  51.62$\pm$1.31 |  50.27$\pm$0.31 |  50.49$\pm$0.91
20 |  56.71$\pm$2.46 |  53.91$\pm$0.63 |  55.59$\pm$1.22 |  56.99$\pm$0.99 |  54.65$\pm$0.68 |  100.30$\pm$1.85 |  55.06$\pm$1.58 |  54.12$\pm$0.58 |  53.56$\pm$0.41
Table 6. The running time (mean$\pm$std) for different methods on test set of
each problem. SpectralRules is employed in Stage 1 to produce the initial 500
rules. The maximum round running of PORS is set to 30 to avoid early stopping,
i.e., each experiment trial fully completed 30 iterations.

###  5.3. Discussion

In this section, we provide more experimental results to shed light on
properties of different combinations of methods.

####  5.3.1. Comparison of SpectralRules and TreeEns

It is apparent that the quality of the initial rule set $\mathcal{R}$ from
Stage 1 may have significant impact for the final Pareto front; it is
impossible to find high-quality rule subsets when some key rules are not
present in $\mathcal{R}$ in the first place. Section 5.2 demonstrates that
SpectralRules outperforms TreeEns when the size of $\mathcal{R}$ is set to
500. In this section, we provide further investigation on the effects of
SpectralRules and TreeEns when the size of $\mathcal{R}$ varies. In this
experiment, we use PORS algorithm as our method to find Pareto-optimal rule
subsets.

Figure 3. HV of PORS algorithm on Bank dataset when using SpectralRules or
TreeEns to produce rule set in Stage 1.

Figure 3 illustrates the HV performance on Bank dataset when the size of
$\mathcal{R}$ increases. Results are aggregated over 5 trials of random
partitioning of the dataset. We observe that SpectralRules outperforms TreeEns
for all $|\mathcal{R}|\leq 500$. SpectralRules cannot produce a larger rule
set since all positive points are already covered with 500 rules. We also
observe that even if we give more budget on the number of rules to TreeEns, it
cannot catch up with the level of HV achieved by SpectralRules. Similar
patterns are observed on other datasets.

There exist some key differences between SpectralRules and TreeEns. TreeEns
extracts rules from a tree ensemble, and therefore we expect that there are
many “homogeneous” rules (in terms of the distribution of precision and recall
for all rules in the set) that look alike each other. This not only hurts the
efficiency of the subsequent subset selection but the efficacy of that also
takes a hit. On the other hand, SpectralRules employs direct rule induction
and focuses on promoting the diversity of $\mathcal{R}$, leading to a more
compact rule set of higher quality. On Bank dataset, for $|\mathcal{R}|=500$,
we observe the mean and standard deviation for precision (recall) of TreeEns
and SpectralRules is $0.5461\pm 0.1604$ ($0.0225\pm 0.0330$) and $0.6376\pm
0.1823$ ($0.0381\pm 0.0699$), respectively. We see that not only the mean of
precision (recall) from SpectralRules is higher, its standard deviation is
larger as well. Hence, for the rest of this paper, we use SpectralRules for
Stage 1 by default unless otherwise mentioned.

Figure 4. Efficiency of NSGA-II vs. PORS on Bank dataset.

####  5.3.2. Impact of Different Values of $k$

To further evaluate the impact of different values of $k$ on PORS with
different SSF methods, including running time and HV, we set $k$ to 5, 10, 15,
20 respectively and apply those 9 PORS algorithms on the 4 public datasets.
According to previous sections, SpectralRules is employed in Stage 1 and the
maximum round running of PORS is set to 30 to avoid early stopping, i.e., each
experiment trial fully completed 30 iterations. All experiments are repeated 5
times.

Table 5 shows the HV results on test set of different PORS algorithms for each
$k$. Once again, we observe that PORS with hvc-ss as its SSF method achieves
the highest HV on most cases. For all SSF methods, a larger value of $k$
usually leads to a higher HV as expected. However, once the $k$ exceeds 10,
the increase in HV usually becomes so tiny to be significant.

The running time of PORS is positively correlated to the value of $k$ as shown
in Table 6. Considering the trade-off between performance and efficiency, we
recommend to use $k=10$ in practice.

####  5.3.3. Efficiency Evaluation for EMO and PORS Algorithm

From Section 5.2 we observe that NSGA-II as an EMO algorithm is a very
competitive to PORS algorithm. In this section, we conduct efficiency
evaluation for these two methods. We run both algorithms on a standard server
with 16GB memory using 4 threads.

Figure 4 shows how HV changes on train, valid and test sets of Bank dataset
over wall clock time for NSGA-II and PORS algorithm. We can see that PORS
algorithm quickly converges while NSGA-II is less efficient. Similar patterns
are observed on other datasets.

In particular, on our largest dataset A3, PORS takes 146 seconds to finish
while NSGA-II takes 1610 seconds on the same server with 16GB using 4 threads.
This suggests a heuristic-based algorithm can be highly efficient.

###  5.4. Case Study

In this section, we provide two case studies within Alipay where the
requirement of the final rule subset of Stage 2 differs, and demonstrate how
finding Pareto-optimal rule sets as an intermediate stage between Stage 1 and
Stage 2 can benefit the eventual result.

To study the relationship of HV (as an intermediate evaluation metric) and
final objective, we consider three implementations of PORS framework in this
section; hvc-ss for high HV, equi-spaced for medium HV, and k-med.-j. for low
HV.

####  5.4.1. Confidence-Constrained Rule Set Learning

We consider confidence-constrained rule set learning (CRSL) (Li et al., 2022)
as our first case study. This learning paradigm seeks to maximize recall
constrained on some precision threshold, and there are many similar
application scenarios inside Alipay that fall in this paradigm. Note that CRSL
only works on TreeEns as it needs a large candidate set to select from, and we
compare it with PORS algorithms using SpectralRules for Stage 1.

Dataset | Prec | CRSL (Li et al., 2022) | PORS
---|---|---|---
hvc-ss | equi-spaced | k-med.-j.
(High HV) | (Med. HV) | (Low HV)
Default | 0.3 |  0.765$\pm$0.025 | 0.854$\pm$0.010 |  0.853$\pm$0.013 |  0.835$\pm$0.014
0.5 |  0.519$\pm$0.012 |  0.557$\pm$0.020 | 0.564$\pm$0.005 |  0.543$\pm$0.017
0.7 |  0.238$\pm$0.038 |  0.260$\pm$0.040 | 0.262$\pm$0.052 |  0.257$\pm$0.045
Credit | 0.3 |  0.555$\pm$0.030 | 0.584$\pm$0.013 |  0.581$\pm$0.015 |  0.538$\pm$0.012
0.5 |  0.269$\pm$0.059 | 0.289$\pm$0.017 |  0.279$\pm$0.037 |  0.273$\pm$0.030
0.7 |  0.038$\pm$0.021 | 0.041$\pm$0.013 |  0.025$\pm$0.023 |  0.024$\pm$0.023
Fraud | 0.3 |  0.840$\pm$0.038 | 0.851$\pm$0.045 |  0.847$\pm$0.035 |  0.8364$\pm$0.037
0.5 |  0.816$\pm$0.024 |  0.822$\pm$0.035 |  0.822$\pm$0.038 | 0.822$\pm$0.024
0.7 |  0.812$\pm$0.032 |  0.814$\pm$0.021 | 0.818$\pm$0.033 |  0.808$\pm$0.034
Bank | 0.3 |  0.907$\pm$0.015 | 0.951$\pm$0.007 |  0.945$\pm$0.009 |  0.813$\pm$0.034
0.5 |  0.630$\pm$0.075 | 0.781$\pm$0.018 |  0.764$\pm$0.034 |  0.679$\pm$0.050
0.7 | 0.337$\pm$0.044 |  0.264$\pm$0.044 |  0.243$\pm$0.038 |  0.253$\pm$0.055
A1 |  5$\delta_{1}$ |  0.789$\pm$0.023 | 0.824$\pm$0.013 |  0.794$\pm$0.016 |  0.775$\pm$0.021
10$\delta_{1}$ |  0.624$\pm$0.016 | 0.657$\pm$0.011 |  0.640$\pm$0.012 |  0.614$\pm$0.018
20$\delta_{1}$ |  0.499$\pm$0.008 | 0.510$\pm$0.009 |  0.501$\pm$0.006 |  0.487$\pm$0.009
A2 |  5$\delta_{2}$ |  0.828$\pm$0.019 | 0.831$\pm$0.007 |  0.767$\pm$0.012 |  0.726$\pm$0.009
10$\delta_{2}$ |  0.483$\pm$0.072 | 0.593$\pm$0.008 |  0.578$\pm$0.008 |  0.545$\pm$0.009
20$\delta_{2}$ |  0.263$\pm$0.079 |  0.324$\pm$0.017 | 0.326$\pm$0.006 |  0.292$\pm$0.006
A3 |  5$\delta_{3}$ | 0.581$\pm$0.022 |  0.563$\pm$0.019 |  0.543$\pm$0.054 |  0.483$\pm$0.034
10$\delta_{3}$ |  0.531$\pm$0.028 | 0.560$\pm$0.021 |  0.526$\pm$0.037 |  0.453$\pm$0.034
20$\delta_{3}$ |  0.387$\pm$0.033 | 0.414$\pm$0.011 |  0.402$\pm$0.0233 |  0.381$\pm$0.021
Table 7. CRSL vs PORS. Each cell represents the recall on test set (mean$\pm$
std) under a corresponding precision threshold. For propriety datasets, we use
the precision threshold of 5x, 10x, 20x of the positive rate of the dataset.
The best method is marked in bold for each case.

Table 7 summarizes results on both public and propriety datasets for CRSL and
PORS algorithms. We observe that on both public and propriety datasets, PORS
with hvc-ss outperforms CRSL on most cases. In addition, we observe that there
is a positive correlation between HV (as an intermediate evaluation metric)
and recall (as a final objective).

Note that CRSL needs to run on each precision threshold to produce a rule
subset, while PORS algorithm only needs to run once and it generates a set of
rule subsets that can be readily picked up for different precision thresholds.
Such flexibility is usually appreciated in real development of rule subsets as
rule mining in practice is typically an explorative and iterative process.

####  5.4.2. Rule Set Learning Using $F_{\beta}$ Score

As our second case study, we use $F_{\beta}$ score to select the final rule
subsets for Stage 2 (which is also widely used inside Alipay). Note that for
Fintech applications, a small $\beta$ is usually favored so that the metric is
more biased towards precision. We compare PORS with standard greedy forward
stepwise algorithm for subset selection (Greedy), both using SpectralRules to
produce a initial rule set of 500 rules in Stage 1. The greedy algorithm
iteratively adds one rule from the initial rule set so as to achieve the
highest metric value. To avoid running into local optima, we equip Greedy with
beam search of width 10.

Dataset | $\beta$ | Greedy | PORS
---|---|---|---
hvc-ss | equi-spaced | k-med.-j.
(High HV) | (Med. HV) | (Low HV)
Default | 0.1 |  0.743$\pm$0.039 | 0.762$\pm$0.033 |  0.747$\pm$0.022 |  0.732$\pm$0.007
0.2 |  0.685$\pm$0.015 |  0.687$\pm$0.015 | 0.692$\pm$0.019 |  0.685$\pm$0.012
0.5 |  0.573$\pm$0.014 |  0.578$\pm$0.008 |  0.577$\pm$0.011 | 0.582$\pm$0.014
Credit | 0.1 |  0.608$\pm$0.043 | 0.616$\pm$0.035 |  0.608$\pm$0.039 |  0.611$\pm$0.034
0.2 |  0.523$\pm$0.020 |  0.536$\pm$0.015 | 0.540$\pm$0.025 |  0.534$\pm$0.025
0.5 |  0.431$\pm$0.011 |  0.433$\pm$0.009 | 0.434$\pm$0.007 |  0.426$\pm$0.011
Fraud | 0.1 | 0.973$\pm$0.006 |  0.968$\pm$0.013 |  0.959$\pm$0.023 |  0.957$\pm$0.011
0.2 |  0.935$\pm$0.029 | 0.950$\pm$0.007 |  0.941$\pm$0.016 |  0.946$\pm$0.008
0.5 |  0.838$\pm$0.032 | 0.888$\pm$0.021 |  0.887$\pm$0.021 |  0.873$\pm$0.019
Bank | 0.1 |  0.755$\pm$0.017 | 0.763$\pm$0.020 |  0.709$\pm$0.016 |  0.729$\pm$0.016
0.2 |  0.652$\pm$0.017 | 0.682$\pm$0.015 |  0.666$\pm$0.018 |  0.656$\pm$0.017
0.5 |  0.596$\pm$0.009 | 0.603$\pm$0.010 |  0.596$\pm$0.012 |  0.586$\pm$0.010
A1 | 0.1 |  0.689$\pm$0.011 | 0.695$\pm$0.009 |  0.682$\pm$0.009 |  0.674$\pm$0.010
0.2 |  0.592$\pm$0.010 | 0.599$\pm$0.006 |  0.599$\pm$0.009 |  0.590$\pm$0.010
0.5 |  0.446$\pm$0.004 | 0.451$\pm$0.006 |  0.443$\pm$0.003 |  0.439$\pm$0.007
A2 | 0.1 |  0.543$\pm$0.045 | 0.547$\pm$0.039 |  0.543$\pm$0.044 |  0.535$\pm$0.020
0.2 |  0.443$\pm$0.018 | 0.446$\pm$0.025 |  0.438$\pm$0.024 |  0.429$\pm$0.017
0.5 |  0.290$\pm$0.012 |  0.290$\pm$0.012 | 0.304$\pm$0.011 |  0.289$\pm$0.009
A3 | 0.1 | 0.257$\pm$0.183 |  0.250$\pm$0.114 |  0.240$\pm$0.119 |  0.222$\pm$0.139
0.2 |  0.119$\pm$0.076 | 0.127$\pm$0.062 |  0.126$\pm$0.060 |  0.119$\pm$0.068
0.5 |  0.067$\pm$0.029 | 0.074$\pm$0.019 |  0.065$\pm$0.017 |  0.063$\pm$0.009
Table 8. Greedy vs PORS. Each cell represents the $F_{\beta}$ score on test
set (mean$\pm$ std) under a particular $\beta$. The best method is marked in
bold for each case.

Table 8 summarizes results on both public and propriety datasets for Greedy
and PORS algorithms. We can see that PORS with hvc-ss outperforms Greedy by
finding rule subsets with higher $F_{\beta}$ on most cases. We again observe
that the positive correlation between HV (as an intermediate evaluation
metric) and $F_{\beta}$ (as a final objective). Note that Greedy needs to run
multiple times (one for each $\beta$) while PORS only needs to run once and it
generates a set of Pareto-optimal rule subsets. It gives more flexibility for
human to quickly experiment different $\beta$s without additional effort.

We note that both Greedy and PORS adds one rule for each iteration, and
therefore we can compare the running time in a relatively fair fashion. Hence,
we run both Greedy and PORS (with hvc-ss) algorithm on a standard server with
16GB memory using 4 threads. Figure 5 illustrates the running time for PORS
and Greedy $F_{0.1}$, $F_{0.2}$, and $F_{0.5}$ on Bank dataset. As expected,
$\beta$ has little impact on the running time for Greedy. Since PORS aims to
generate a set of rule subsets while Greedy only focuses on one single metric,
PORS needs to do more work for each iteration and we empirically observe PORS
takes 2x to 3x more time than single run of Greedy for each iteration. This is
acceptable in practice given the flexibility offered by PORS.

Figure 5. Running time for Greedy and PORS on Bank dataset.

##  6\. Conclusion

In practice, a two-stage framework of fraud prevention decision rule set
mining is usually employed in large Fintech institutions. This paper aims to
find high-quality rule subsets in a bi-objective space of precision and recall
when some initial pool of rules are given. To this end, we adopt the concept
of Pareto optimality and aim to find a set of non-dominated rule subsets,
which constitutes a Pareto front. We propose a heuristic-based framework
called PORS and we identify that the core of PORS is the problem of solution
selection on the front (SSF). We provide a systematic categorization of the
SSF problem and a thorough empirical evaluation of various SSF methods. We
also propose a novel variant of sequential covering algorithm called
SpectralRules to encourage the diversity of the initial rule set and we
empirically find that SpectralRules further improves the quality of the found
Pareto front. On two real application scenarios within Alipay, we demonstrate
the advantages of our proposed methodology compared to existing work.

## References

  * (1)
  * git (2023) 2023\.  _Github repo_.  https://github.com/ChengyaoWen/PORS/
  * Agrawal et al. (1993) R. Agrawal, T. Imieliński, and A. Swami. 1993\.  Mining association rules between sets of items in large databases. In _SIGMOD_.
  * Bader and Zitzler (2011) J. Bader and E. Zitzler. 2011.  HypE: An algorithm for fast hypervolume-based many-objective optimization.  _Evolutionary computation_ 19, 1 (2011), 45–76.
  * Beume et al. (2007) N. Beume, B. Naujoks, and M. Emmerich. 2007.  SMS-EMOA: Multiobjective selection based on dominated hypervolume.  _European Journal of Operational Research_ 181, 3 (2007), 1653–1669.
  * Breiman (2001) L. Breiman. 2001\.  Random forests.  _Machine learning_ 45, 1 (2001), 5–32.
  * Breiman et al. (1984) L. Breiman, J.H. Friedman, C.J. Stone, and R.A. Olshen. 1984.  _Classification and regression trees_.  Chapman and Hall/CRC.
  * Chen et al. (2021a) W. Chen, H. Ishibuchi, and K. Shang. 2021a.  Clustering-based subset selection in evolutionary multiobjective optimization. In _SMC_.
  * Chen et al. (2021b) W. Chen, H. Ishibuchi, and K. Shang. 2021b.  Fast Greedy Subset Selection From Large Candidate Solution Sets in Evolutionary Multiobjective Optimization.  _IEEE Transactions on Evolutionary Computation_ 26, 4 (2021), 750–764.
  * Clark and Niblett (1989) P. Clark and T. Niblett. 1989.  The CN2 induction algorithm.  _Machine learning_ 3, 4 (1989), 261–283.
  * Cohen (1995) W.W. Cohen. 1995\.  Fast effective rule induction. In _ICML_.
  * Deb et al. (2002) K. Deb, A. Pratap, S. Agarwal, and T Meyarivan. 2002\.  A fast and elitist multiobjective genetic algorithm: NSGA-II.  _IEEE Transactions on Evolutionary Computation_ 6, 2 (2002), 182–197.
  * Guerreiro et al. (2020) A.P. Guerreiro, C.M. Fonseca, and L. Paquete. 2020\.  The Hypervolume Indicator: Problems and Algorithms.  _arXiv preprint arXiv:2005.00515_ (2020).
  * Lakkaraju et al. (2016) H. Lakkaraju, S.H. Bach, and J. Leskovec. 2016.  Interpretable decision sets: A joint framework for description and prediction. In _KDD_.
  * Li et al. (2015) B. Li, J. Li, K. Tang, and X. Yao. 2015\.  Many-objective evolutionary algorithms: A survey.  _ACM Computing Surveys (CSUR)_ 48, 1 (2015), 1–35.
  * Li and Yao (2019) M. Li and X. Yao. 2019\.  Quality evaluation of solution sets in multiobjective optimisation: A survey.  _Comput. Surveys_ 52, 2 (2019), 1–38.
  * Li et al. (2022) M. Li, L. Yu, Y.-L. Zhang, X Huang, Q. Shi, Q. Cui, X. Yang, L. Li, W. Zhu, Y. Fang, and J. Zhou. 2022.  An Adaptive Framework for Confidence-constraint Rule Set Learning Algorithm in Large Dataset. In _CIKM_.
  * Molnar (2020) C. Molnar. 2020\.  _Interpretable Machine Learning_.  Lulu. com.
  * Pereyra et al. (2013) V. Pereyra, M. Saunders, and J. Castillo. 2013.  Equispaced Pareto front construction for constrained bi-objective optimization.  _Mathematical and Computer Modelling_ 57, 9-10 (2013), 2122–2131.
  * Quinlan (1993) J.R. Quinlan. 1993\.  _C4. 5: programs for machine learning_.  Morgan Kaufmann Publishers.
  * Shang et al. (2022) K. Shang, T. Shu, H. Ishibuchi, Y. Nan, and L.M. Pang. 2022.  Benchmarking subset selection from large candidate solution sets in evolutionary multi-objective optimization.  _arXiv preprint arXiv:2201.06700_ (2022).
  * Tanabe et al. (2017) R. Tanabe, H. Ishibuchi, and A. Oyama. 2017.  Benchmarking multi-and many-objective evolutionary algorithms under two optimization scenarios.  _IEEE Access_ 5 (2017), 19597–19619.
  * Van Rijsbergen (1979) C.J. Van Rijsbergen. 1979\.  _Information Retrieval_.  Butterworth-Heinemann.
  * Zhang and Gionis (2020) G. Zhang and A. Gionis. 2020.  Diverse Rule Sets. In _KDD_.
  * Zhang and Li (2007) Q. Zhang and H. Li. 2007\.  MOEA/D: A multiobjective evolutionary algorithm based on decomposition.  _IEEE Transactions on evolutionary computation_ 11, 6 (2007), 712–731.
  * Zitzler (1999) E. Zitzler. 1999\.  _Evolutionary algorithms for multiobjective optimization: Methods and applications_.  Ph. D. Dissertation. ETH Zurich, Switzerland.
  * Zitzler et al. (2001) E. Zitzler, M. Laumanns, and L. Thiele. 2001.  _SPEA2: Improving the strength Pareto evolutionary algorithm_.  Technical Report. ETHZ, Zürich, Switzerland.