# A Max-relevance-min-divergence Criterion for Data Discretization with
Applications on Naive Bayes

Shihe Wang  Jianfeng Ren  Ruibin Bai  Yuan Yao  Xudong Jiang  School of
Computer Science, University of Nottingham Ningbo China, Ningbo 315100, China
School of Electrical and Electronic Engineering, Nanyang Technological
University, 639798, Singapore

###### Abstract

In many classification models, data is discretized to better estimate its
distribution. Existing discretization methods often target at maximizing the
discriminant power of discretized data, while overlooking the fact that the
primary target of data discretization in classification is to improve the
generalization performance. As a result, the data tend to be over-split into
many small bins since the data without discretization retain the maximal
discriminant information. Thus, we propose a Max-Dependency-Min-Divergence
(MDmD) criterion that maximizes both the discriminant information and
generalization ability of the discretized data. More specifically, the Max-
Dependency criterion maximizes the statistical dependency between the
discretized data and the classification variable while the Min-Divergence
criterion explicitly minimizes the JS-divergence between the training data and
the validation data for a given discretization scheme. The proposed MDmD
criterion is technically appealing, but it is difficult to reliably estimate
the high-order joint distributions of attributes and the classification
variable. We hence further propose a more practical solution, Max-Relevance-
Min-Divergence (MRmD) discretization scheme, where each attribute is
discretized separately, by simultaneously maximizing the discriminant
information and the generalization ability of the discretized data. The
proposed MRmD is compared with the state-of-the-art discretization algorithms
under the naive Bayes classification framework on 45 machine-learning
benchmark datasets. It significantly outperforms all the compared methods on
most of the datasets.

###### keywords:

Data Discretization, Maximal Dependency, Maximal Relevance, Minimal
Divergence, Naive Bayes Classification

††journal: Pattern Recognition

##  1 Introduction

Data discretization has received much research attention in recent years [1,
2, 3, 4, 5]. Continuous attributes are often discretized to facilitate a
better estimation of the data distribution for subsequent classifiers. To
handle massive amounts of mixed-type data [6], many classifiers such as
decision tree [3, 7, 8, 9], fuzzy rule-based classifiers [10] and naive Bayes
[11, 12, 13] have been developed, where continuous data is transformed into
discrete one. The discrete features are easier to understand than continuous
ones because they are closer to knowledge-level representation [14]. Most
importantly, by discretizing similar values into one bin, the generalization
capability of a classifier could be enhanced [11, 12, 13].

Discretization methods can be broadly divided into three main categories:
supervised, unsupervised, and semi-supervised depending on whether the class
label is considered [15]. Equal-width and equal-frequency discretizations are
two representative unsupervised methods [3]. Supervised discretization methods
[16, 17, 18, 14, 2, 19] often produce features with more discriminant power by
using the class information, which can be further divided into filter-based
[16, 18, 17] and wrapper-based approaches [14, 2, 19]. Filter-based methods
are applied prior to classification algorithms [18, 16, 17], whereas wrapper-
based methods discretize the data by utilizing the classification feedback
[14, 2, 19]. Semi-supervised methods are less studied, e.g., a semi-supervised
framework based on Minimal Optimized Description Length (MODL) has been
developed to exploit a mixture of labeled and unlabeled data [20].

Data discretization aims to find a minimal set of cut points that optimally
discretize the continuous attributes to maximize the classification accuracy
[2, 1]. Existing methods often over-emphasize maximizing the discriminant
information, while neglecting the fact that the primary target of data
discretization is to improve the generalization performance by reducing the
noisy information that is harmful to reliable classification. In data
discretization, two opposing goals often compete with each other, i.e., the
generalization performance is maximized when all samples are discretized into
one bin so that there is no discrepancy between the distribution of training
data and that of testing data, but the discriminant information is totally
lost in this case. On the other hand, the discriminant information is
maximized when no discretization is performed on the data, but the
generalization performance in this case won’t be improved.

In literature, many discretization algorithms have been developed to maximize
the dependence between the discretized attribute and the classification
variable in terms of mutual information [4], information entropy [18],
contingency coefficient [21, 22], statistical interdependency [17, 23], and
many others [24, 14, 2, 25]. However, none of them explicitly maximizes the
generalization capability. Instead, they often restrict the number of
intervals after discretization to be small, in the hope of improving the
generalization ability, e.g., Class-Attribute Interdependence Maximization
(CAIM) [23] and Class-Attribute Contingency Coefficient (CACC) [21] both
restrict the number of intervals to the number of classes. Such a design does
not optimize the discretization scheme in terms of the generalization.

To tackle this problem, a Max-Dependency-Min-Divergence (MDmD) criterion is
proposed in this paper to simultaneously maximize the discriminant power and
the generalization ability. Many algorithms have been developed to maximize
the discriminant power of the discretized data, e.g., Minimum Description
Length Principle (MDLP) [26], CAIM [23], CACC [21] and Joint Bias Mutual
Information (JBMI) [4]. Among them, maximizing the mutual information between
the discretized data and the classification variable is one of the most
popular approaches, also known as Max-Dependency [4, 27]. Besides data
discretization, this criterion has also been widely used in feature selection
[28, 29, 30], feature weighting [31, 12] and feature extraction [32].

For the primary target of data discretization in classification, improving the
generalization ability, existing discretizers often simply choose to keep the
number of intervals small [23, 21, 14, 17, 2]. However, if the number of
intervals is too small, a significant amount of discriminant information will
be lost. On the other hand, if the number of intervals is too large, the
resulting discretization scheme may not generalize well to the testing data.
It is hence difficult to decide the optimal number of intervals. In this
paper, a Min-Divergence criterion is proposed to derive a discretization
scheme, which explicitly maximizes the generalization ability by minimizing
the divergence between the distribution of training data and that of
validation data. This criterion is integrated with the Max-Dependency
criterion to form the proposed Max-Dependency-Min-Divergence criterion, which
could achieve a better trade-off between the discriminant power and
generalization ability so that the subsequent classifier could work well.

The proposed MDmD criterion is technically appealing but difficult to be
applied in practice, as it is difficult to reliably estimate the high-order
joint distributions for attributes and the classification variable. To tackle
this problem, instead of maximizing the mutual information between all the
attributes and the classification variable, we propose to maximize the
summation of the mutual information between each attribute and the
classification variable, also known as Max-Relevance [27, 4]. At the same
time, we propose to minimize the summation of divergences between
distributions when one attribute is evaluated at a time. These two criteria
are combined to form the proposed Max-Relevance-Min-Divergence (MRmD)
criterion, which maximizes the discriminant power by maximizing the mutual
information between the discretized attributes and the classification
variable, and simultaneously maximizes the generalization ability by
minimizing the divergence between the distributions of training data and
validation data.

The proposed MRmD criterion is integrated with one of the most recent
developments of naive Bayes classifier, Regularized Naive Bayes (RNB) [11],
and compared with the state-of-the-art discretization methods and naive Bayes
classifiers on 45 benchmark machine-learning datasets for various
applications. The proposed method significantly outperforms the compared
methods on most of the datasets.

The main contributions of this paper can be summarized as follows. 1) We
identify the key limitations of existing discretization methods that they
often overemphasize maximizing the discriminative power, which limits the
improvement of the generalization ability. 2) To tackle this problem, a Max-
Dependency-Min-Divergence criterion is proposed to simultaneously maximize the
discriminant power and minimize the distribution discrepancy so that the
derived discretization scheme could generalize well to the data population. 3)
To tackle the challenges of reliable estimation of the joint probabilities in
MDmD, a more practical solution, Max-Relevance-Min-Divergence discretization
scheme, is proposed to derive the optimal discretization scheme for one
attribute at a time. 4) The proposed method is systematically evaluated on 45
machine-learning datasets and demonstrates superior performance compared with
the state-of-the-art discretization methods and naive Bayes classifiers.

##  2 Related work

Discretization methods have been deployed to extract knowledge from data in
many machine learning algorithms such as decision tree [33, 3], rule-based
learning [10] and naive Bayes [13, 11, 12]. Discretization methods can be
categorized according to many properties [15]. 1). Local vs. Global. Local
methods [18, 26] generate intervals based on partial data, whereas global ones
[17, 14, 23, 21] consider all available data. 2). Dynamic vs. Static. Dynamic
discretizers [4] interact with learning models whereas static ones [17, 16]
execute before the learning stage. 3). Splitting vs. Merging. This relates to
the top-down split [18, 23, 21] or bottom-up merge [16] strategy in producing
new intervals. 4). Univariate vs. Multivariate. Univariate algorithms [18, 17,
3] discretize each attribute separately whereas multivariate discretizers [14,
2] consider a combination of attributes when discretizing data. 5). Direct vs.
Incremental. Direct methods [34, 14] divide the range into several intervals
simultaneously, while incremental ones [17, 18, 21, 23, 26] begin with a
simple discretization and improve it gradually by using more criteria.

Depending on whether the class label is used, discretization methods can be
divided into supervised, semi-supervised and unsupervised methods [15].
Unsupervised methods include equal-width and equal-frequency discretization
[3]. Semi-supervised methods are comparatively less studied. One of the
representative methods is MODL, which derives the discretization scheme by
applying the Bayesian rule on both labeled and unlabeled data [20]. Supervised
methods can be further divided into wrapper-based methods [15, 2, 25] and
filter-based methods [18, 16, 17, 23, 21]. The former optimizes the
discretization scheme by utilizing the classification feedback [15, 2, 25],
while the latter optimizes some indirect target for data discretization, e.g.,
information entropy [18, 26], mutual information [4] and interdependency [17,
23, 21].

Wrapper-based methods [14, 2, 25, 35] often iteratively derive the optimal
discretization scheme by using the classification results as the feedback
signal. Among them, evolutionary algorithms are often utilized to select a set
of cut points to discretize data by maximizing the classification accuracy and
minimizing the number of intervals [14]. Recently, Tahan and Asadi developed
an evolutionary multi-objective discretization to handle the imbalanced
datasets [2]. To reduce the search space during discretization, Tran _et al._
firstly initialize the discretization scheme by using the MDLP criterion and
utilize barebones particle swarm optimization to fine-tune the derived scheme
[35]. In [25], the particle swarm optimization strategy is used to explore the
interaction between features to better discretize the data. To handle high-
resolution satellite remote sensing, Chen _et al._ developed a genetic
algorithm based on the fuzzy rough set to effectively explore the data
association [36].

Filter-based methods [18, 16, 23, 21, 37] have a strong theoretical background
and have gained popularity in recent years. MDLP discretizer has been widely
used in many classifiers [13, 12, 11]. It is one of the most popular top-down
discretization methods, which hierarchically partitions the data to maximize
the information entropy [26]. To avoid excessive splitting, it defines a stop
criterion derived from the theory of channel coding. Xun _et al._ developed a
multi-scale discretization method to obtain the set of cut points with
different granularity and utilized the MDLP criterion to determine the best
cut point [18]. Apart from entropy, other statistical measures have also been
widely deployed in data discretization [16, 17, 3]. Kurgan and Cios developed
a CAIM criterion based on a quanta matrix to select boundary points
iteratively within a pre-defined number of intervals [23]. Recently, Cano _et
al._ extended CAIM to discretize the multi-label data [17]. Tsai _et al._
introduced a discretization method based on CACC by taking the overall data
distribution into account [21]. In [5], low-frequency values are discretized
and the correlation between discrete attribute and continuous attribute is
used to guide the discretization process. Chi-square statistics such as
Modified Chi2 and extended Chi2 have been recently used to discretize data
[16], which measure the relationship between the discretized attribute and the
classification variable.

Most discretization methods [18, 17, 23, 21, 26] emphasize maximizing the
discriminant power, but they pay little attention to the generalization
capability, e.g., they often restrict the number of discrete intervals to be
small, in the hope of achieving a satisfactory generalization ability. If a
discretization method considers maximizing the discriminant power and the
generalization ability simultaneously, the subsequent classifier will achieve
a better classification performance on novel testing data.

##  3 Proposed discretization method

###  3.1 Analysis of existing discretization methods

Data discretization is crucial to improve the learning efficiency and
generalization of classifiers [15]. Many discretizers have been designed to
maximize the statistical dependency between the discretized features and the
classification variable [23, 21, 4, 18]. This dependency can be modeled in
many forms, e.g., information gain in MDLP [26, 18], class-attribute
dependency in CADD [38], and class-attribute interdependency in CAIM [23, 17].
Existing approaches often emphasize maximizing the discriminant information
while overlooking the fact that the primary target of data discretization in
classification is to improve generalization ability, i.e., by discretizing
similar values into one interval, the data distribution can be estimated less
over fitting the training data.

MDLP is one of the most widely used discretization methods [13, 11, 12], e.g.,
it is the default discretization method in Weka toolbox [39]. It
hierarchically splits the dynamic range into smaller ones. For each attribute,
a cut point $d$ that maximizes the information gain $G(\mathcal{S},d)$ is
selected to divide the current set $\mathcal{S}$ into two subsets
$\mathcal{S}_{1}$ and $\mathcal{S}_{2}$,

$G(\mathcal{S},d)=E(\mathcal{S})-\frac{|\mathcal{S}_{1}|}{|\mathcal{S}|}E(\mathcal{S}_{1})-\frac{|\mathcal{S}_{2}|}{|\mathcal{S}|}E(\mathcal{S}_{2}),$
(1)

where $E(\mathcal{S})=-\sum\limits_{c\in\mathcal{C}}P(c,\mathcal{S})\log
P(c,\mathcal{S})$ is the entropy, $P(c,\mathcal{S})$ is the probability of
class $c$ in $\mathcal{S}$ and $\mathcal{C}$ is the set of classes. It can be
shown that the accumulative information is equivalent to the mutual
information between the discretized attribute and the classification variable.
Greedily maximizing the information gain may excessively split the attribute
into too many small intervals with too few samples so that the likelihood
probabilities can’t be reliably estimated. To prevent this, MDLP requires the
information gain to be greater than a threshold that is derived from the
overhead of information encoding, which may not be in line with the
classification point of view. It often leads to an early stop during
splitting, and hence a significant loss in the discriminant information.

Class-Attribute Dependent Discretizer (CADD) [38] maximizes the discriminant
information via maximizing the following criterion,

$CADD(X,C)=\frac{I(X;C)}{E(X,C)},$ (2)

where $I(X;C)$ is the mutual information and $E(X,C)$ is the joint entropy.
Maximizing CADD tends to produce too many small discretization intervals. To
prevent this, a user-specified threshold is utilized to constrain the number
of intervals, but with no guarantee of optimality.

The CAIM discretization utilizes a heuristic measure to model the
interdependence between classes and attributes [23, 17],

$CAIM(X,C)=\frac{1}{n}\sum_{i=1}^{n}\frac{\max_{c\in\mathcal{C}}q_{i,c}^{2}}{M_{i}},$
(3)

where $q_{i,c}$ is the number of samples belonging to class $c$ in the $i$-th
interval, and $M_{i}$ is the number of samples in the $i$-th interval. The
number of intervals generated by CAIM is often close to the number of classes,
which may limit the performance of CAIM, especially when the number of classes
is small.

Existing approaches mainly focus on maximizing the discriminant information,
while this criterion often splits the attribute into too many small intervals,
which defeats the purpose of data discretization in classification, i.e., to
improve the generalization ability. To retain the generalization ability, they
often restrict the number of intervals to a predefined number or the number of
classes [23, 17, 21, 38], or require the information gain to be larger than a
threshold [26, 18]. These methods lack a measure to explicitly maximize the
generalization ability.

###  3.2 Maximal-dependency-minimal-divergence for data discretization

In this paper, the target is to derive an optimal discretization scheme
$\bm{\mathcal{D}}$ to transform continuous attributes $\bm{X}$ into discrete
ones $\bm{A}$, which simultaneously maximizes the discriminant power of the
discretized data and maximizes the generalization ability to the data not used
in training,

$\bm{A}=f_{D}(\bm{X},\bm{\mathcal{D}}),$ (4)

where $f_{D}$ denotes the discretization function.

$\bm{\mathcal{D}}=\\{\mathcal{D}_{1},\mathcal{D}_{2},...,\mathcal{D}_{m}\\},$
(5)

where $\bm{\mathcal{D}}$ contains the discretization schemes for $m$ features.

####  3.2.1 Maximal-dependency criterion

To maximize the discriminant information, we propose to maximize the mutual
information $I(\bm{A};C)$ between the discretized attributes $\bm{A}$ and the
classification variable $C$ given the discretization scheme
$\bm{\mathcal{D}}$,

$\bm{\mathcal{D}}^{*}=\operatorname{argmax}_{\bm{\mathcal{D}}}I(\bm{A};C),$
(6)
$I(\bm{A};C)=\sum_{c\in\mathcal{C}}\sum_{\bm{a}\in\bm{A}}P(\bm{a},c)\log\frac{P(\bm{a},c)}{P(\bm{a})P(c)},$
(7)

where $C$ is the class variable and $I(\bm{A};C)$ is the mutual information
defined in terms of the joint probability distribution $P(\bm{a},c)$ and the
respective marginal probabilities $P(\bm{a})$ and $P(c)$. This criterion is
often known as Max-Dependency [27, 4]. Apparently it is difficult to reliably
estimate both the joint probability distribution $P(\bm{a},c)$ and the
marginal probability distribution $P(\bm{a})$ due to the high dimensionality.
Furthermore, the Maximal-Dependency criterion tends to greedily maximize the
discriminant power and hence over-discretize the continuous data into too many
small intervals, i.e., each unique value in the numerical attribute may be
treated as a separate interval, in which the generalization capability won’t
be improved.

####  3.2.2 Minimal-divergence criterion

To maximize the generalization ability, we propose to minimize the Jensen-
Shannon (JS) divergence [40] between the training data distribution and test
data distribution. As the test data distribution is in general unknown, we
hence aim to minimize the distribution discrepancy between the training data
and validation data instead. The intuition behind is that by minimizing the JS
divergence $D_{JS}(P^{t}||P^{v})$ describing the similarity between the
distribution $P^{t}$ of the training data $\bm{A}^{t}$ and the distribution
$P^{v}$ of the validation data $\bm{A}^{v}$, the derived discretization scheme
$\bm{\mathcal{D}}$ could generalize well from the training data to the novel
testing data. Formally, $D_{JS}(P^{t}||P^{v})$ is defined as:

$D_{JS}(P^{t}||P^{v})=\frac{1}{2}(D_{KL}(P^{t}||P^{*})+D_{KL}(P^{v}||P^{*})),$
(8)

where $P^{*}=\frac{1}{2}(P^{t}+P^{v})$ and $D_{KL}(P^{t}||P^{*})$ is the
Kullback-Leibler divergence between $P^{t}$ and $P^{*}$,

$D_{KL}(P^{t}||P^{*})=\sum_{\bm{a}\in\mathcal{A}}P^{t}(\bm{a})\log\frac{P^{t}(\bm{a})}{P^{*}(\bm{a})}.$
(9)

Similarly, $D_{KL}(P^{v}||P^{*})$ is defined as:

$D_{KL}(P^{v}||P^{*})=\sum_{\bm{a}\in\mathcal{A}}P^{v}(\bm{a})\log\frac{P^{v}(\bm{a})}{P^{*}(\bm{a})}.$
(10)

$P^{t}(\bm{a})$, $P^{v}(\bm{a})$ and $P^{*}(\bm{a})$ are the probabilities of
taking a set of attribute values $\bm{a}$ given the attribute set
$\bm{A}^{t}$, $\bm{A}^{v}$ and $\bm{A}^{*}$ respectively.

The JS divergence has been utilized as a distance metric between two
distributions. It is symmetric, i.e.,
$D_{JS}(P^{t}||P^{v})=D_{JS}(P^{v}||P^{t})$, and
$D_{JS}(P^{t}||P^{v})\in[0,1]$. The smaller JS divergence represents the
higher similarity between these two distributions, and hence the derived
discretization scheme could generalize well to the novel testing data. The
Minimal-Divergence criterion is hence defined as:

$\bm{\mathcal{D}}^{*}=\operatorname{argmin}_{\bm{\mathcal{D}}}D_{JS}(P^{t}||P^{v})$
(11)

####  3.2.3 Maximal-dependency-minimal-divergence criterion

To simultaneously maximize the discriminant information and the generalization
ability of the discretized attributes, we propose to maximize the dependency
$I(\bm{A};C)$ between the discretized attributes $\bm{A}$ and the
classification variable $C$, and minimize the divergence
$D_{JS}(P^{t}||P^{v})$ between the distribution of the training data
$\bm{A}^{t}$ and that of validation data $\bm{A}^{v}$ at the same time given
the discretization scheme $\bm{\mathcal{D}}$,

$\bm{\mathcal{D}}^{*}=\operatorname{argmax}_{\bm{\mathcal{D}}}\lambda
I(\bm{A};C)-D_{JS}(P^{t}||P^{v}),$ (12)

where $\lambda$ is the hyper-parameter to balance the two terms. Note that the
two terms compete with each other. On the one hand, when all the data are
discretized into one bin, $I(\bm{A};C)=0$, indicating that the discriminant
information is totally lost, but $D_{JS}(P^{t}||P^{v})=0$, i.e., the two
distributions are identical, and hence the generalization ability is
maximized. On the other hand, when every sample of the data is discretized
into one bin, the discriminant information is maximized, while it doesn’t
improve the generalization ability. The proposed MDmD criterion provides a
solution to find the optimal trade-off between the discriminant power and the
generalization ability.

###  3.3 Maximal-relevance-minimal-divergence criterion for data
discretization

The proposed MDmD criterion is technically appealing but difficult to
implement in practice, as it is hard to reliably estimate the high-order joint
distribution $P(\bm{a},c)$, $P^{t}(\bm{a})$ and $P^{v}(\bm{a})$. In this
paper, we propose the Max-Relevance criterion for data discretization. More
specifically, instead of maximizing the mutual information $I(\bm{A};C)$ that
requires the estimation of high-order joint distributions between all the
attributes and the classification variable, we propose to maximize the
summation of the mutual information between each attribute and the
classification variable,

$\bm{\mathcal{D}}^{*}=\operatorname{argmax}_{\bm{\mathcal{D}}}\sum_{j=1}^{m}I({A}_{j};C),$
(13)

where $I({A}_{j};C)$ is the mutual information between the discretized
attribute ${A}_{j}$ and the classification variable $C$. The Max-Relevance
criterion has been used to approximate the Max-Dependency criterion [27] in
feature selection [4, 29], feature weighting [31, 12] and feature extraction
[32].

For the second term in Eqn. (12), instead of estimating the divergence between
two distributions $P^{t}$ and $P^{v}$ jointly considering all the attributes,
$D_{JS}(P^{t}||P^{v})$ can be estimated one by one as,

$\bm{\mathcal{D}}^{*}=\operatorname{argmin}_{\bm{\mathcal{D}}}\sum_{j=1}^{m}D_{JS}(P_{j}^{t}||P_{j}^{v}),$
(14)

where $D_{JS}(P_{j}^{t}||P_{j}^{v})$ is the JS divergence between the training
data distribution and validation data distribution for the $j$-th attribute
given the discretization scheme $\mathcal{D}_{j}$.

We combine Eqn. (13) and Eqn. (14) to form the proposed Maximal-Relevance-
Minimal-Divergence (MRmD) criterion,

$\bm{\mathcal{D}}^{*}=\operatorname{argmax}_{\bm{\mathcal{D}}}\sum_{j=1}^{m}\left[\lambda
I({A}_{j};C)-D_{JS}(P_{j}^{t}||P_{j}^{v})\right].$ (15)

The proposed MRmD criterion aims to find the optimal discretization scheme
$\bm{\mathcal{D}}^{*}$ that maximizes the relevance of the discretized
attributes with respect to the classification variable via the first term, and
maximizes the generalization ability of the discretization scheme by
minimizing the distribution discrepancy between the training data and
validation data via the second term.

To derive the optimal solution for Eqn. (15), it is not difficult to show that
each attribute $A_{j}$ can be processed separately to derive its optimal
discretization scheme $\mathcal{D}_{j}^{*}$,

$\mathcal{D}_{j}^{*}=\operatorname{argmax}_{\mathcal{D}_{j}}\Psi({A}_{j};C),$
(16)

where $\Psi({A}_{j};C)$ is defined as,

$\Psi({A}_{j};C)=\lambda I({A}_{j};C)-D_{JS}(P_{j}^{t}||P_{j}^{v}).$ (17)

After deriving the optimal solution for each attribute, the optimal
discretization scheme $\bm{\mathcal{D}}^{*}$ is obtained as,

$\bm{\mathcal{D}}^{*}=\\{\mathcal{D}_{1}^{*},\mathcal{D}_{2}^{*},...,\mathcal{D}_{m}^{*}\\}.$
(18)

###  3.4 Proposed MRmD data discretization

Figure 1: The proposed MRmD discretization framework. The optimal set of cut
points for each attribute is selected by maximizing the proposed MRmD
criterion, where the Max-Relevance criterion is designed to maximize the
discriminant information of the discretized data, and the Min-Divergence
criterion is designed to maximize the generalization by minimizing the
distribution discrepancy between training and validation data. More details on
the proposed MRmD discretization can be found in Alg. 1.

Based on the proposed maximal-relevance-minimal-divergence criterion, a MRmD
discretization method is proposed to discretize data, which simultaneously
maximizes the discriminant information and the generalization ability of the
discretized data. The block diagram of the proposed MRmD discretization scheme
is shown in Fig. 1. For each continuous attribute, the proposed method
iteratively determines the cut points for discretization by maximizing the
proposed MRmD criterion, where the Max-Relevance criterion is achieved by
maximizing the mutual information between the discretized attribute and the
classification variable, and the Min-Divergence criterion is achieved by
minimizing the distribution discrepancy between the training data and
validation data. Then, these two criteria are combined to form the Maximal-
Relevance-Minimal-Divergence criterion, to derive an optimal set of cut-points
to discretize the continuous attribute.

Following the design in MDLP [18, 26] and many others [23, 21, 17], a top-down
hierarchically split paradigm is designed to derive the optimal solution. More
specifically, for each attribute $\bm{x}_{j}$, we initialize its
discretization scheme $\mathcal{D}_{j}^{*}$ as an empty set,

$\mathcal{D}_{j}^{*}\leftarrow\emptyset.$ (19)

In this case, the whole dynamic range is initially treated as one interval,
and hence $I({A}_{j};C)=0$ and $D_{JS}(P^{t}_{j}||P^{v}_{j})=0$. The set of
potential cut points is initialized as,

$\mathcal{S}_{j}\leftarrow\mathcal{U}(\bm{x}_{j}),$ (20)

where $\mathcal{U}(\bm{x}_{j})$ returns the unique values of $\bm{x}_{j}$. It
can be shown that the number of possible discretization schemes for
$\bm{x}_{j}$ is $2^{|\mathcal{S}_{j}|}$. It is hence expensive to exhaustively
evaluate every feasible discretization scheme. $\forall
d_{k}\in\mathcal{S}_{j}$, $\mathcal{D}_{j}^{k}=\mathcal{D}_{j}^{*}\cup d_{k}$,
we select the cut point $d_{k_{max}}$ that maximizes the criterion defined in
Eqn. (17). Then, the optimal discretization scheme and candidate set are
updated as $\mathcal{D}_{j}^{*}=\mathcal{D}_{j}^{*}\cup d_{k_{max}}$ and
$\mathcal{S}_{j}=\mathcal{S}_{j}-d_{k_{max}}$, respectively. The proposed
method incrementally selects the cut point to divide the dynamic range into
intervals until the criterion defined in Eqn. (17) does not increase any more.

The proposed MRmD discretization is summarized in Algorithm 1. The continuous
attribute $\bm{x}_{j}\in\bm{X}$ is discretized by utilizing the proposed MRmD
criterion one after another. These discretization schemes
$\mathcal{D}_{j}^{*}$ for all attributes form the complete discretization
scheme $\bm{\mathcal{D}}^{*}$. The proposed MRmD discretization generates a
discretization scheme that simultaneously maximizes the discriminant
information and the generalization ability, and hence improve the
classification performance.

Algorithm 1 The proposed MRmD discretization scheme.

1:Input data $\bm{X}=\\{\bm{X}^{t},\bm{X}^{v}\\}$ with class label $\bm{c}$
for $\bm{X}$

2:Discretization scheme
$\bm{\mathcal{D}}^{*}=\\{\mathcal{D}_{1}^{*},\mathcal{D}_{2}^{*},...,\mathcal{D}_{m}^{*}\\}$

3:$\bm{\mathcal{D}}^{*}\leftarrow\emptyset$ $\triangleright$ Initialize
$\bm{\mathcal{D}}^{*}$ as an empty set

4:for $\bm{x}_{j}\in\bm{X}$ do $\triangleright$ Loop through all attributes

5: $\mathcal{D}_{j}^{*}\leftarrow\emptyset$ $\triangleright$ Initialize
$\mathcal{D}_{j}^{*}$ as an empty set

6: $\mathcal{S}_{j}\leftarrow\mathcal{U}(\bm{x}_{j})$ $\triangleright$
Initialize $\mathcal{S}_{j}$ as the set of unique values

7: $\Psi_{{max}}\leftarrow-\infty$ $\triangleright$ Initialize optimal ${\rm
MRmD}$ value

8: while $(\mathcal{S}_{j}\neq\emptyset)$ do $\triangleright$ Incrementally
select the cut point

9: for $d_{k}\in\bm{\mathcal{S}}_{j}$ do $\triangleright$ For each possible
cut point

10: $\mathcal{D}_{j}^{k}=\mathcal{D}_{j}^{*}\cup d_{k}$ $\triangleright$
Include $d_{k}$ as the cut point

11: $A_{j}=f_{D}(\bm{x}_{j},{D}_{j}^{k})$ $\triangleright$ Discretize
$\bm{x}_{j}$ using ${D}_{j}^{k}$

12: $\Psi_{k}=\lambda I({A}_{j};C)-D_{JS}(P_{j}^{t}||P_{j}^{v})$
$\triangleright$ Calculate $\Psi_{k}$

13: end for

14: $k_{max}=\operatorname{argmax}_{k}\Psi_{k}$ $\triangleright$ Derive
$d_{k_{max}}$ with maximal $\Psi_{k_{max}}$

15: if $\Psi_{k_{max}}\leq\Psi_{max}$ then

16: break;

17: end if

18: $\Psi_{max}\leftarrow\Psi_{k_{max}}$ $\triangleright$ Update $\Psi_{max}$

19: $\mathcal{D}_{j}^{*}\leftarrow\mathcal{D}_{j}^{*}\cup d_{k_{max}}$
$\triangleright$ Update $\mathcal{D}_{j}^{*}$

20: $\mathcal{S}_{j}\leftarrow\mathcal{S}_{j}-d_{k_{max}}$ $\triangleright$
Update $\mathcal{S}_{j}$

21: end while

22:
$\bm{\mathcal{D}}^{*}\leftarrow\bm{\mathcal{D}}^{*}\cup\mathcal{D}_{j}^{*}$
$\triangleright$ Add $\mathcal{D}_{j}^{*}$ into $\bm{\mathcal{D}}^{*}$

23:end for

24:return $\bm{\mathcal{D}}^{*}$

###  3.5 Analysis of hyper-parameter $\lambda$

The hyper-parameter $\lambda$ plays an important role in the proposed MRmD. As
discussed early, the MRmD value $\Psi({A}_{j};C)$ is initialized as zero at
the beginning of the top-down discretization. Both terms in Eqn. (17)
increases with the number of discretization intervals. It is hence difficult
to derive the optimal MRmD value. To tackle this problem, $\lambda$ is defined
as:

$\lambda=e^{-\frac{|\mathcal{D}_{j}^{*}|}{N_{D}}},$ (21)

where $|\mathcal{D}_{j}^{*}|$ is the number of cut points in the current
discretization scheme, and $N_{D}$ is empirically set to 50. The value of
$\lambda$ is between 0 and 1. In the earlier stage, when there are only a
small number of cut points in the discretization scheme, $\lambda$ will be
large and hence more emphasis is put on the first term in Eqn. (17), to
highlight the importance of maximizing the discriminant information. As more
cut points are added into the discretization scheme, $\lambda$ becomes smaller
and hence more emphasis is put on the second term of Eqn. (17). As a result,
the optimization focuses more on improving the generalization performance of
the discretization scheme. Such a design could help the proposed MRmD
discretization generate a discretization scheme that achieves an optimal
trade-off between the generalization capability and the discrimination
information for the discretized data.

##  4 Experimental results

###  4.1 Experimental settings

Two sets of experiments are conducted under the naive Bayes classification
framework. Firstly, the proposed MRmD discretization is compared with five
popular filter-based discretization methods, Ameva [22], CAIM [23], MDLP [26],
Modified Chi2 [24] and PKID (Proportional K-Interval Discretization) [34], and
a recent wrapper-based approach, EMD (Evolutionary Multivariate
Discretization) [14]. Ameva [22] and CAIM [23] are two popular methods for
discretization in credit scoring models for operational research [41]. MDLP
[26] and PKID [34] are widely used in state-of-the-art NB classifiers [11, 13,
12, 37] and feature-selection approaches [42, 35]. Modified Chi2 [24] has been
recently used to improve the ensemble classification methods [16]. EMD [14]
has been used in many applications recently, e.g., high-resolution remote
sensing [36, 1] and feature selction [25]. Secondly, the proposed MRmD is
integrated with one of the recent naive Bayes classifiers, RNB (regularized
naive Bayes) [11], denoted as MRmD-RNB. It is compared with state-of-the-art
NB classifiers including RNB [11], WANBIA (Weighting attributes to Alleviate
Naive Bayes’ Independence Assumption) [43], CAWNB (Class-specific Attribute
Weighted Naive Bayes) [13] and AIWNB (Attribute and Instance Weighted Naive
Bayes) [12]. As shown later, the proposed discretization scheme significantly
improves the classification performance of the state-of-the-art NB
classifiers.

Table 1: Description of compared methods: six discretization methods and four
state-of-the-art naive Bayes classifiers. Discretization methods
---
Ameva [22, 41] |  Filter-based statistical top-down discretization, maximizing the contingency coefficient based on Chi-square statistics.
CAIM [23, 17] |  Filter-based statistical top-down discretization, heuristically maximizing the class-attribute interdependency by using quanta matrix.
MDLP [18, 26, 11] |  Filter-based entropy-based top-down discretization, maximizing the information gain using the minimum description length principle.
Modified Chi2 [16, 24] |  Filter-based statistical bottom-up discretization, merging intervals dynamically by using the rough set theory.
PKID [37, 34] |  Filter-based unsupervised discretization, adjusting the number and size of intervals proportional to the number of training instances.
EMD [14, 1] |  Wrapper-based multivariate discretization, minimizing the classification error and the number of intervals using genetic algorithm.
Naive Bayes classifiers
RNB [11] |  Wrapper-based regularized attribute-weighting naive Bayes, simultaneously optimizing class-dependent and class-independent attribute weights by using the L-BFGS algorithm.
WANBIA [43] |  Wrapper-based attribute-weighting naive Bayes, optimizing class-independent attribute weights by using the L-BFGS algorithm.
CAWNB [13] |  Wrapper-based attribute-weighting naive Bayes, optimizing class-specific attribute weights by using the L-BFGS algorithm.
AIWNB [12] |  Filter-based attribute and instance-weighting naive Bayes, combining correlation-based attribute weights with frequency-based instance weights using eager learning AIWNBE and similarity-based instance weights using lazy learning AIWNBL.

The experiments are conducted on 45 machine-learning benchmark datasets in
various fields including healthcare, biology, disease diagnosis and business.
The datasets are extracted from the UCI machine learning repository
111https://archive.ics.uci.edu/ml/index.php. These datasets have been widely
used to evaluate the performance of discretization algorithms [14, 4, 3] and
naive Bayes classifiers [11, 13, 12]. Most datasets are collected from real-
world problems. The number of instances is distributed between 106 and 10992
and the number of attributes is distributed between 2 and 90. Some datasets
contain missing values which are replaced by the mean or mode of the
corresponding attribute. Besides, there are both nominal attributes and
numerical attributes in some datasets. These 45 datasets can provide a
comprehensive evaluation of the proposed methods. The statistics of these
datasets are summarized in Table 2. Similarly as in [14, 11, 12, 13], the
classification accuracy of each algorithm on each dataset is derived via
stratified 10-fold cross-validation. For the proposed method, only 8 out of 9
folds of training data are used in training while the remaining one fold
serves as validation data.

Table 2: Statistics of the benchmark datasets, where Inst., Attr., Class,
Num., Nom. and Missing denote the number of instances, attributes, classes,
numerical attributes, nominal attributes and whether the dataset contains
missing values, respectively. The number of instances is distributed between
106 and 10992, which provides a comprehensive evaluation on datasets of
different sizes. The number of attributes also varies across datasets. There
are both numerical and nominal attributes, and/or missing values in some of
the datasets, which makes the design of discretization scheme and subsequent
classifier more challenging.

| Inst. | Attr. | Class | Num. | Nom. | Missing |  | Inst. | Attr. | Class | Num. | Nom. | Missing
---|---|---|---|---|---|---|---|---|---|---|---|---|---
abalone | 4174 | 8 | 28 | 7 | 1 | N | movement | 360 | 90 | 15 | 90 | 0 | N
appendicitis | 106 | 7 | 2 | 7 | 0 | N | newthyroid | 215 | 5 | 3 | 5 | 0 | N
australian | 690 | 14 | 2 | 8 | 6 | N | pageblocks | 5472 | 10 | 5 | 10 | 0 | N
auto | 205 | 25 | 6 | 15 | 10 | Y | penbased | 10992 | 16 | 10 | 16 | 0 | N
balance | 625 | 4 | 3 | 4 | 0 | N | phoneme | 5404 | 5 | 2 | 5 | 0 | N
banana | 5300 | 2 | 2 | 2 | 0 | N | pima | 768 | 8 | 2 | 8 | 0 | N
bands | 539 | 19 | 2 | 19 | 0 | Y | saheart | 462 | 9 | 2 | 8 | 1 | N
banknote | 1372 | 5 | 2 | 5 | 0 | N | satimage | 6435 | 36 | 7 | 36 | 0 | N
bupa | 345 | 6 | 2 | 6 | 0 | N | segment | 2310 | 19 | 7 | 19 | 0 | N
clevland | 303 | 13 | 5 | 13 | 0 | Y | seismic | 2584 | 19 | 2 | 15 | 4 | N
climate | 540 | 18 | 2 | 18 | 0 | N | sonar | 208 | 60 | 2 | 60 | 0 | N
contraceptive | 1473 | 9 | 3 | 9 | 0 | N | spambase | 4597 | 57 | 2 | 57 | 0 | N
crx | 690 | 15 | 2 | 6 | 9 | Y | specfheart | 267 | 44 | 2 | 44 | 0 | N
dermatology | 366 | 34 | 6 | 34 | 0 | Y | tae | 151 | 5 | 3 | 5 | 0 | N
ecoli | 336 | 7 | 8 | 7 | 0 | N | thoracic | 470 | 17 | 2 | 3 | 14 | N
flare-solar | 1066 | 9 | 2 | 9 | 0 | N | titanic | 2201 | 3 | 2 | 3 | 0 | N
glass | 214 | 9 | 7 | 9 | 0 | N | transfusion | 748 | 5 | 2 | 5 | 0 | N
haberman | 306 | 3 | 2 | 3 | 0 | N | vehicle | 846 | 18 | 4 | 18 | 0 | N
hayes | 160 | 4 | 3 | 4 | 0 | N | vowel | 990 | 13 | 11 | 13 | 0 | N
heart | 270 | 13 | 2 | 13 | 0 | N | wine | 178 | 13 | 3 | 13 | 0 | N
hepatitis | 155 | 19 | 2 | 19 | 0 | Y | wisconsin | 699 | 9 | 2 | 9 | 0 | N
iris | 150 | 4 | 3 | 4 | 0 | N | yeast | 1484 | 8 | 10 | 8 | 0 | N
mammographic | 961 | 5 | 2 | 5 | 0 | N |  |  |  |  |  |  |

###  4.2 Comparisons to state-of-the-art discretization methods

The proposed discretization is compared with state-of-the-art discretization
methods, Ameva [22], CAIM [23], MDLP [26], Modified Chi2 [24], PKID [34] and
EMD [14] on the 45 datasets. The results are summarized in Table 3, where the
results of the compared methods are obtained by using KEEL tool [44]. The
highest classification accuracy on each dataset among all compared methods is
highlighted in bold. The average classification accuracy on all datasets for
each algorithm is summarized at the bottom of Table 3, which provides an
overall comparison.

Table 3: Comparisons of different discretization methods under the naive Bayes
classification framework. The proposed MRmD achieves the best average
classification accuracy, and outperforms the second best method, EMD [14], by
1.7% on average.

|  Ameva [22] |  CAIM [23] |  MDLP [26] |  Modified Chi2 [24] |  PKID [34] |  EMD [14] | MRmD
---|---|---|---|---|---|---|---
abalone | 0.2127 | 0.2585 | 0.2496 | 0.2429 |  0.2611 | 0.2578 | 0.2554
appendicitis |  0.8800 | 0.8709 | 0.8709 | 0.8518 | 0.8609 | 0.8709 | 0.8791
australian | 0.8507 |  0.8638 | 0.8449 | 0.8449 | 0.8551 | 0.8565 | 0.8637
auto | 0.6729 | 0.6497 | 0.6732 | 0.6488 | 0.7269 | 0.6606 |  0.7693
balance | 0.7968 | 0.8031 | 0.7266 | 0.9088 |  0.9120 | 0.8544 | 0.9104
banana | 0.7049 | 0.6049 | 0.7247 | 0.6300 | 0.7147 |  0.7357 | 0.7296
bands | 0.7255 | 0.6643 | 0.5045 | 0.7235 | 0.6865 | 0.6550 |  0.7364
banknote | 0.8943 | 0.8907 | 0.9205 | 0.9140 | 0.9220 |  0.9424 | 0.9155
bupa | 0.6599 | 0.6169 | 0.5715 | 0.6376 | 0.6277 | 0.6548 |  0.6842
clevland | 0.5778 | 0.5612 | 0.5545 | 0.5482 | 0.5544 | 0.5709 |  0.5807
climate | 0.9111 | 0.9167 | 0.9352 | 0.9130 | 0.9019 |  0.9352 | 0.9351
contraceptive | 0.5064 | 0.4963 | 0.5051 | 0.5024 | 0.5092 | 0.5200 |  0.5221
crx | 0.8551 | 0.8609 | 0.8565 | 0.8420 | 0.8522 | 0.8536 |  0.8623
dermatology | 0.9810 | 0.9755 | 0.9782 |  0.9865 | 0.9782 | 0.9482 | 0.9863
ecoli | 0.8127 | 0.8094 | 0.8216 | 0.7948 | 0.8038 | 0.7889 |  0.8428
flare-solar | 0.6557 | 0.6557 | 0.6754 | 0.6529 | 0.6548 | 0.6726 |  0.6829
glass | 0.4647 | 0.7034 | 0.7206 | 0.7199 | 0.7246 | 0.7124 |  0.7567
haberman | 0.7478 | 0.7352 | 0.7285 | 0.7220 | 0.7282 | 0.7449 |  0.7480
hayes | 0.7437 | 0.7437 | 0.5202 | 0.7937 | 0.7932 |  0.8157 | 0.8009
heart | 0.8370 | 0.8407 | 0.8407 | 0.8296 |  0.8444 | 0.8296 | 0.8407
hepatitis | 0.8196 | 0.8388 | 0.8383 | 0.8263 | 0.8071 | 0.8254 |  0.8654
iris | 0.9333 | 0.9400 | 0.9267 | 0.9333 | 0.9200 |  0.9533 | 0.9400
mammographic | 0.8148 | 0.8262 | 0.8221 | 0.8263 | 0.8325 |  0.8357 | 0.8336
movement | 0.6500 | 0.6528 | 0.6056 | 0.6250 | 0.6667 | 0.5583 |  0.6890
newthyroid | 0.9535 | 0.9582 | 0.9489 | 0.9582 | 0.9675 | 0.9494 |  0.9766
pageblocks | 0.9401 | 0.9342 | 0.9311 | 0.9375 | 0.9158 | 0.9406 |  0.9410
penbased | 0.8608 | 0.8712 | 0.8766 | 0.8771 | 0.8722 | 0.8708 |  0.8867
phoneme | 0.7889 | 0.7894 | 0.7689 | 0.7705 | 0.7742 |  0.7935 | 0.7913
pima | 0.7280 | 0.7320 | 0.7526 | 0.7397 | 0.7410 |  0.7722 | 0.7461
saheart | 0.6582 | 0.7035 | 0.6624 | 0.6777 | 0.6756 | 0.7079 |  0.7079
satimage | 0.2528 | 0.8169 | 0.8210 | 0.8222 | 0.8211 | 0.8199 |  0.8228
segment | 0.9126 | 0.9039 | 0.9104 | 0.8987 | 0.8909 |  0.9355 | 0.9229
seismic | 0.8224 | 0.8196 | 0.8200 | 0.8580 | 0.8247 | 0.9334 |  0.9342
sonar | 0.7788 | 0.7745 | 0.7688 | 0.7836 | 0.7452 | 0.7393 |  0.7840
spambase | 0.8995 | 0.8938 | 0.8989 | 0.9021 | 0.8945 |  0.9228 | 0.9053
specfheart | 0.7644 | 0.7682 | 0.7305 | 0.7496 | 0.7752 |  0.8128 | 0.7971
tae | 0.5113 | 0.4904 | 0.3442 | 0.5571 | 0.4904 | 0.5438 |  0.5657
thoracic | 0.8191 | 0.8213 | 0.8213 | 0.8298 | 0.8043 | 0.8213 |  0.8298
titanic | 0.7810 | 0.7783 | 0.7760 | 0.7788 | 0.7788 | 0.7787 |  0.7819
transfusion | 0.7687 | 0.7633 | 0.7500 | 0.7500 | 0.7499 | 0.7406 |  0.7794
vehicle | 0.6122 | 0.6064 | 0.5910 | 0.6241 | 0.6205 |  0.6419 | 0.6337
vowel | 0.6364 | 0.6222 | 0.6030 | 0.6515 | 0.5788 | 0.6343 |  0.6404
wine | 0.9830 | 0.9775 |  0.9886 | 0.9598 | 0.9663 | 0.9212 | 0.9830
wisconsin | 0.9671 | 0.9671 | 0.9728 | 0.9714 | 0.9728 | 0.9513 |  0.9736
yeast | 0.5695 | 0.5796 | 0.5695 | 0.5620 | 0.5519 | 0.5735 |  0.5883
AVG | 0.7493 | 0.7634 | 0.7494 | 0.7684 | 0.7678 | 0.7746 | 0.7916

As shown in Table 3, the naive Bayes classifier using the proposed MRmD
discretization scheme obtains the highest classification accuracy on 26
datasets. Compared with the previous filter-based approaches, Ameva [22], CAIM
[23], MDLP [26], Modified Chi2 [24] and PKID [34], the proposed MRmD
discretization obtains an average improvement of 4.23%, 2.83%, 4.22%, 2.32%
and 2.38%, respectively. As a filter-based method, the proposed MRmD
outperforms the previously best discretization method, the wrapper-based
algorithm, EMD [14], with an average improvement of 1.7% over the 45 datasets.
The performance improvements on some datasets are significant. For example,
the classification results of the proposed MRmD on “auto”, “bands” and
“movement” are more than 8% higher than EMD [14]. Both “auto” and “movement”
have a relatively small number of samples but a relatively large number of
attributes. The NB classifier is easily overfitting to these two datasets. By
maximizing the discriminant information and the generalization performance at
the same time, the proposed MRmD achieves a much better generalization
performance than EMD [14] that greedily maximizes the discriminant power for
small training sample size.

Table 4: Ranks of the Wilcoxon test when comparing various discretization
methods. Large rank values in the first row and small rank values in the first
column indicate that the proposed MRmD significantly outperforms all the
compared discretization methods.

Algorithm | MRmD | Ameva | CAIM | MDLP | Modified Chi2 | PKID | EMD
---|---|---|---|---|---|---|---
MRmD | - | 1030.5 | 1024.5 | 1007.5 | 1014.5 | 1009.0 | 797.5
Ameva | 4.5 | - | 546.5 | 606.5 | 499.0 | 545.0 | 348.0
CAIM | 10.5 | 488.5 | - | 654.0 | 485.0 | 522.0 | 339.0
MDLP | 27.5 | 428.5 | 381.0 | - | 456.0 | 470.5 | 306.5
Modified Chi2 | 21.0 | 536.0 | 550.0 | 579.0 | - | 522.5 | 362.5
PKID | 26.0 | 490.0 | 513.0 | 564.5 | 512.5 | - | 383.0
EMD | 237.5 | 687.0 | 696.0 | 728.5 | 672.5 | 652.0 | -

To evaluate the significance of the performance gains, we apply the Wilcoxon
signed-rank test [45] to thoroughly compare each pair of algorithms. The
Wilcoxon signed-rank test is a non-parametric statistical test, which ranks
the differences in the performance of any two algorithms for each dataset, and
compares the ranks for their differences. Table 4 presents the detailed ranks
computed by the Wilcoxon test. Each entry ${R}_{i,j}$ in Table 4 is the sum of
ranks for all datasets on which the algorithm in the $i$-th row is compared
with the algorithm in the $j$-th column. For the confidence level of
$\alpha=0.05$ and $N=45$, ${R}_{i,j}>692$ indicates that the algorithm in the
$i$-th row is significantly better than the algorithm in the $j$-th column. As
shown in Table 4, the proposed MRmD discretization significantly better than
Ameva (${R}_{1,2}=1030.5$), CAIM (${R}_{1,3}=1024.5$), MDLP
(${R}_{1,4}=1007.5$), Modified Chi2 (${R}_{1,5}=1014.5$), PKID
(${R}_{1,6}=1009$) and EMD (${R}_{1,7}=797.5$). These results clearly
demonstrate that the proposed MRmD significantly outperforms all the compared
discretization methods.

Table 5: Comparisons with the state-of-the-art NB classifiers. The proposed
MRmD-RNB significantly outperforms the previous best method, RNB [11], by
2.81% on average.

| WANBIA [43] | CAWNB [13] | AIWNBL [12] | AIWNBE [12] | RNB [11] | MRmD-RNB
---|---|---|---|---|---|---
abalone | 0.2641 | 0.2487 | 0.2583 | 0.2392 | 0.2674 |  0.2700
appendicitis | 0.8755 | 0.8755 | 0.8491 | 0.8491 | 0.8755 |  0.8864
australian | 0.8681 | 0.8681 | 0.8535 | 0.8477 | 0.8680 |  0.8694
auto | 0.7562 | 0.7615 | 0.7126 | 0.7131 | 0.8244 |  0.8435
balance | 0.7186 | 0.7186 | 0.7153 | 0.7008 | 0.7186 |  0.9104
banana | 0.7283 | 0.7338 | 0.7332 | 0.7198 |  0.7338 | 0.7336
bands | 0.7049 | 0.7069 | 0.7012 | 0.7012 | 0.7069 |  0.7531
banknote | 0.9213 | 0.9278 | 0.9257 | 0.9206 | 0.9278 |  0.9286
bupa | 0.5327 | 0.5327 | 0.4202 | 0.4202 | 0.5327 |  0.7049
clevland | 0.5773 | 0.5845 | 0.5717 | 0.5815 | 0.5857 |  0.5906
climate | 0.9426 | 0.9426 | 0.9426 | 0.9426 | 0.9426 |  0.9445
contraceptive | 0.5138 | 0.5186 | 0.5112 | 0.5072 | 0.5227 |  0.5343
crx |  0.8711 | 0.8667 | 0.8594 | 0.8521 | 0.8652 | 0.8682
dermatology | 0.9864 | 0.9837 | 0.9756 | 0.9756 | 0.9864 |  0.9865
ecoli | 0.8251 | 0.8338 | 0.8223 | 0.8223 | 0.8339 |  0.8459
flare-solar | 0.6801 | 0.6726 | 0.6820 | 0.6820 | 0.6820 |  0.6829
glass | 0.7113 | 0.7385 | 0.7428 | 0.7528 | 0.7197 |  0.7571
haberman | 0.7318 | 0.7318 | 0.2647 | 0.2647 | 0.7318 |  0.7480
hayes | 0.6003 | 0.6003 | 0.6003 | 0.6003 | 0.6003 |  0.8009
heart | 0.8519 | 0.8556 | 0.8370 | 0.8370 | 0.8519 |  0.8593
hepatitis | 0.8217 | 0.8342 | 0.8279 | 0.8213 | 0.8404 |  0.8725
iris | 0.9333 | 0.9333 | 0.9267 | 0.9267 | 0.9333 |  0.9400
mammographic | 0.8252 | 0.8252 | 0.8242 | 0.8232 | 0.8263 |  0.8336
movement | 0.6716 | 0.6842 | 0.6463 | 0.6712 | 0.6875 |  0.7181
newthyroid | 0.9580 | 0.9535 | 0.9576 | 0.9532 | 0.9580 |  0.9857
pageblocks | 0.9604 | 0.9638 | 0.9379 | 0.9302 | 0.9633 |  0.9646
penbased | 0.8988 | 0.9289 | 0.9360 | 0.8882 | 0.9311 |  0.9370
phoneme | 0.8027 | 0.8014 | 0.7979 | 0.7813 | 0.8022 |  0.8050
pima | 0.7421 | 0.7512 | 0.7369 | 0.7382 | 0.7486 |  0.7590
saheart | 0.7035 | 0.6991 | 0.6774 | 0.6774 | 0.7012 |  0.7338
satimage | 0.8440 | 0.8420 | 0.8544 | 0.8140 | 0.8577 |  0.8612
segment |  0.9472 | 0.9381 | 0.9420 | 0.9264 | 0.9459 | 0.9459
seismic | 0.9342 | 0.9342 | 0.8266 | 0.8119 | 0.9342 |  0.9346
sonar | 0.7837 | 0.7699 | 0.7649 | 0.7697 | 0.7742 |  0.8028
spambase | 0.9378 | 0.9411 | 0.9016 | 0.8994 | 0.9394 |  0.9446
specfheart | 0.7854 | 0.7856 | 0.7507 | 0.7507 | 0.8114 |  0.8270
tae | 0.3440 | 0.3440 | 0.3244 | 0.3244 | 0.3440 |  0.5857
thoracic | 0.8383 | 0.8340 | 0.8234 | 0.8191 | 0.8362 |  0.8426
titanic | 0.7760 | 0.7760 | 0.7760 | 0.7760 | 0.7760 |  0.7774
transfusion | 0.7621 | 0.7621 | 0.7447 | 0.7447 | 0.7621 |  0.7780
vehicle | 0.6562 | 0.6501 | 0.6136 | 0.6466 | 0.6774 |  0.6987
vowel | 0.6414 | 0.6364 | 0.6364 |  0.6687 | 0.6465 | 0.6515
wine | 0.9830 | 0.9719 | 0.9771 | 0.9660 | 0.9830 |  0.9830
wisconsin | 0.9693 | 0.9722 | 0.9736 | 0.9707 | 0.9722 |  0.9736
yeast | 0.5675 | 0.5756 | 0.5715 | 0.5715 | 0.5729 |  0.5930
AVG | 0.7722 | 0.7736 | 0.7495 | 0.7467 | 0.7778 | 0.8059

Table 6: Ranks of the Wilcoxon test when comparing state-of-the-art NB
classifiers. Large rank values in the first row and small rank values in the
first column indicate that MRmD-RNB significantly outperforms the compared NB
classifiers.

Algorithm | MRmD-RNB | WANBIA | CAWNB | AIWNBL | AIWNBE | RNB
---|---|---|---|---|---|---
MRmD-RNB | - | 1019.5 | 1034.0 | 1034.5 | 1021.0 | 1028.0
WANBIA | 15.5 | - | 587.5 | 183.0 | 122.0 | 807.0
CAWNB | 1.0 | 447.5 | - | 162.5 | 81.0 | 765.0
AIWNBL | 0.5 | 852.0 | 872.5 | - | 331.5 | 973.0
AIWNBE | 14.0 | 913.0 | 954.0 | 703.5 | - | 933.5
RNB | 7.0 | 228.0 | 266.0 | 62.0 | 101.5 | -

###  4.3 Comparisons to state-of-the-art naive Bayes classifiers

RNB [11] is a recent NB classifier achieving good classification performance,
which utilizes MDLP [26] as the discretization scheme. The proposed MRmD is
integrated with RNB [11], named MRmD-RNB, and compared with the state-of-the-
art NB classifiers including WANBIA [43], CAWNB [13], AIWNB [12] and RNB [11].
The results are summarized in Table 5. As shown in Table 5, the proposed MRmD-
RNB obtains the highest classification accuracy on 41 datasets out of 45
datasets among the state-of-the-art naive Bayes classifiers. Compared with the
recent attribute weighting methods, AIWNBL and AIWNBE [12], the proposed MRmD-
RNB achieves an average improvement of 5.64% and 5.93%, respectively. Compared
with the previous best approach, RNB [11], the proposed MRmD-RNB achieves an
average improvement of 2.81%. The performance gains on some of the datasets
are significant. For example, the performance gains on “balance”, “bupa”,
“hayes” and “tae” are more than 17% over the previous best method, RNB [11].
Among them, both “hayes” and “tae” have a relatively small number of instances
and attributes. The NB classifier may overfit these small datasets due to few
training samples. The proposed discretization method greatly enhances the
generalization ability of state-of-the-art NB classifiers and hence
significantly improves the classification performance.

We also evaluate the significance of the performance gains over other naive
Bayes classifiers using the Wilcoxon signed-rank test. As shown in Table 6,
the proposed MRmD-RNB significantly outperforms WANBIA ($R_{1,2}=1019.5$),
CAWNB ($R_{1,3}=1034$), AIWNBL ($R_{1,4}=1034.5$), AINWBE ($R_{1,5}=1021$) and
RNB ($R_{1,6}=1028$).

##  5 Conclusion

Previous data discretization methods often overemphasize maximizing the
discriminant information while overlooking the primary goal of data
discretization in classification, i.e., to enhance the generalization ability
of the classifier. To address this problem, a Maximal-Dependency-Minimal-
Divergence scheme is proposed to simultaneously maximize the generalization
capability and discriminant information. The proposed MDmD criterion is
difficult to implement in practice due to the difficulty in estimating the
high-order mutual information. We hence proposed a more practical solution,
Maximal-Relevance-Minimal-Divergence criterion, which discretizes one
attribute at a time in a top-down manner. The proposed MRmD criterion
generates a discretization scheme with a trade-off between retaining the
discriminant information and improving the generalization ability for the
subsequent classifier. Experimental results on the 45 machine-learning
datasets demonstrate that the proposed MRmD significantly outperforms all the
compared discretization methods and, by integrating the proposed MRmD with
RNB, the resulting MRmD-RNB significantly outperforms the state-of-the-art NB
classifiers.

## Acknowledgment

This work was supported in part by the National Natural Science Foundation of
China under Grant 72071116, and in part by the Ningbo Municipal Bureau Science
and Technology under Grants 2019B10026.

## References

  * [1] Q. Chen, W. Ding, X. Huang, H. Wang, Generalized interval type II fuzzy rough model based feature discretization for mixed pixels, IEEE Transactions on Fuzzy Systems (2022).
  * [2] M. H. Tahan, S. Asadi, EMDID: evolutionary multi-objective discretization for imbalanced datasets, Information Sciences 432 (2018) 442–461.
  * [3] C.-F. Tsai, Y.-C. Chen, The optimal combination of feature selection and data discretization: An empirical study, Information Sciences 505 (2019) 282–293.
  * [4] S. Sharmin, M. Shoyaib, A. A. Ali, M. A. H. Khan, O. Chae, Simultaneous feature selection and discretization based on mutual information, Pattern Recognition 91 (2019) 162–174.
  * [5] M. G. Rahman, M. Z. Islam, Discretization of continuous attributes through low frequency numerical values and attribute interdependency, Expert Systems with Applications 45 (2016) 410–423.
  * [6] T. Boeckling, G. D. Tré, A. Bronselaer, Efficient edit rule implication for nominal and ordinal data, Information Sciences 590 (2022) 179–197.
  * [7] D. García-Gil, S. Ramírez-Gallego, S. García, F. Herrera, Principal components analysis random discretization ensemble for big data, Knowledge-Based Systems 150 (2018) 166–174.
  * [8] F. Wang, Q. Wang, F. Nie, Z. Li, W. Yu, F. Ren, A linear multivariate binary decision tree classifier based on k-means splitting, Pattern Recognition 107 (2020) 107521.
  * [9] E. Adıyeke, M. G. Baydoğan, Semi-supervised extensions of multi-task tree ensembles, Pattern Recognition 123 (2022) 108393.
  * [10] Y. Mu, X. Liu, L. Wang, J. Zhou, A parallel fuzzy rule-base based decision tree in the framework of map-reduce, Pattern Recognition 103 (2020) 107326.
  * [11] S. Wang, J. Ren, R. Bai, A regularized attribute weighting framework for naive Bayes, IEEE Access 8 (2020) 225639–225649.
  * [12] H. Zhang, L. Jiang, L. Yu, Attribute and instance weighted naive Bayes, Pattern Recognition 111 (2021) 107674.
  * [13] L. Jiang, L. Zhang, L. Yu, D. Wang, Class-specific attribute weighted naive Bayes, Pattern Recognition 88 (2019) 321–330.
  * [14] S. Ramírez-Gallego, S. García, J. M. Benítez, F. Herrera, Multivariate discretization based on evolutionary cut points selection for classification, IEEE transactions on Cybernetics 46 (3) (2015) 595–608.
  * [15] S. Ramírez-Gallego, S. García, H. Mouriño-Talín, D. Martínez-Rego, V. Bolón-Canedo, A. Alonso-Betanzos, J. M. Benítez, F. Herrera, Data discretization: taxonomy and big data challenge, Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 6 (1) (2016) 5–21.
  * [16] N. Peker, C. Kubat, Application of chi-square discretization algorithms to ensemble classification methods, Expert Systems with Applications 185 (2021) 115540\.
  * [17] A. Cano, J. M. Luna, E. L. Gibaja, S. Ventura, LAIM discretization for multi-label data, Information Sciences 330 (2016) 370–384.
  * [18] Y. Xun, Q. Yin, J. Zhang, H. Yang, X. Cui, A novel discretization algorithm based on multi-scale and information entropy, Applied Intelligence 51 (2) (2021) 991–1009.
  * [19] M. H. Tahan, S. Asadi, MEMOD: a novel multivariate evolutionary multi-objective discretization, Soft Computing 22 (1) (2018) 301–323.
  * [20] A. Bondu, M. Boullé, V. Lemaire, A non-parametric semi-supervised discretization method, Knowledge and Information Systems 24 (1) (2010) 35–57.
  * [21] C.-J. Tsai, C.-I. Lee, W.-P. Yang, A discretization algorithm based on class-attribute contingency coefficient, Information Sciences 178 (3) (2008) 714–731.
  * [22] L. Gonzalez-Abril, F. J. Cuberos, F. Velasco, J. A. Ortega, Ameva: an autonomous discretization algorithm, Expert Systems with Applications 36 (3) (2009) 5327–5332.
  * [23] L. A. Kurgan, K. J. Cios, CAIM discretization algorithm, IEEE transactions on Knowledge and Data Engineering 16 (2) (2004) 145–153.
  * [24] F. E. Tay, L. Shen, A modified chi2 algorithm for discretization, IEEE Transactions on Knowledge and Data Engineering 14 (3) (2002) 666–670.
  * [25] Y. Zhou, J. Kang, S. Kwong, X. Wang, Q. Zhang, An evolutionary multi-objective optimization framework of discretization-based feature selection for classification, Swarm and Evolutionary Computation 60 (2021) 100770.
  * [26] U. Fayyad, Multi-interval discretization of continuous-valued attributes for classification learning, in: 13th International Joint Conference on Artificial Intelligence, Vol. 2, 1993, pp. 1022–1027.
  * [27] H. Peng, F. Long, C. Ding, Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy, IEEE Transactions on Pattern Analysis and Machine Intelligence 27 (8) (2005) 1226–1238.
  * [28] J. Dai, Y. Liu, J. Chen, Feature selection via max-independent ratio and min-redundant ratio based on adaptive weighted kernel density estimation, Information Sciences 568 (2021) 86–112.
  * [29] J. Wan, H. Chen, T. Li, W. Huang, M. Li, C. Luo, R2CI: Information theoretic-guided feature selection with multiple correlations, Pattern Recognition (2022) 108603.
  * [30] J. Ren, X. Jiang, J. Yuan, Learning LBP structure by maximizing the conditional mutual information, Pattern Recognition 48 (10) (2015) 3180–3190.
  * [31] L. Jiang, L. Zhang, C. Li, J. Wu, A correlation-based feature weighting filter for naive Bayes, IEEE transactions on Knowledge and Data Engineering 31 (2) (2018) 201–213.
  * [32] S. M. Ghosh, S. Bandyopadhyay, D. Mitra, Nonlinear classification of emotion from eeg signal based on maximized mutual information, Expert Systems with Applications 185 (2021) 115605.
  * [33] L. Breiman, J. H. Friedman, R. A. Olshen, C. J. Stone, Classification and regression trees, Routledge, 2017.
  * [34] Y. Yang, G. I. Webb, Proportional k-interval discretization for naive Bayes classifiers, in: European Conference on Machine Learning, Springer, 2001, pp. 564–575.
  * [35] B. Tran, B. Xue, M. Zhang, A new representation in PSO for discretization-based feature selection, IEEE Transactions on Cybernetics 48 (6) (2017) 1733–1746.
  * [36] Q. Chen, M. Huang, H. Wang, G. Xu, A feature discretization method based on fuzzy rough sets for high-resolution remote sensing big data under linear spectral model, IEEE Transactions on Fuzzy Systems (2021).
  * [37] J. J. Rivas, M. del Carmen Lara, L. Castrejon, J. Hernandez-Franco, F. Orihuela-Espina, L. Palafox, A. Williams, N. Berthouze, E. Sucar, Multi-label and multimodal classifier for affective states recognition in virtual rehabilitation, IEEE Transactions on Affective Computing (2021).
  * [38] J. Y. Ching, A. K. C. Wong, K. C. C. Chan, Class-dependent discretization for inductive learning from continuous and mixed-mode data, IEEE Transactions on Pattern Analysis and Machine Intelligence 17 (7) (1995) 641–651.
  * [39] I. H. Witten, E. Frank, Data mining: practical machine learning tools and techniques with Java implementations, ACM Sigmod Record 31 (1) (2002) 76–77.
  * [40] J. Deasy, N. Simidjievski, P. Liò, Constraining variational inference with geometric jensen-shannon divergence, Advances in Neural Information Processing Systems 33 (2020) 10647–10658.
  * [41] D. M. Silva, G. H. Pereira, T. M. Magalhães, A class of categorization methods for credit scoring models, European Journal of Operational Research 296 (1) (2022) 323–331.
  * [42] R. Said, M. Elarbi, S. Bechikh, C. A. C. Coello, L. B. Said, Discretization-based feature selection as a bi-level optimization problem, IEEE Transactions on Evolutionary Computation (2022).
  * [43] N. A. Zaidi, J. Cerquides, M. J. Carman, G. I. Webb, Alleviating naive Bayes attribute independence assumption by attribute weighting, The Journal of Machine Learning Research 14 (1) (2013) 1947–1988.
  * [44] J. Alcalá-Fdez, L. Sanchez, S. Garcia, M. J. del Jesus, S. Ventura, J. M. Garrell, J. Otero, C. Romero, J. Bacardit, V. M. Rivas, et al., KEEL: a software tool to assess evolutionary algorithms for data mining problems, Soft Computing 13 (3) (2009) 307–318.
  * [45] J. Demšar, Statistical comparisons of classifiers over multiple data sets, The Journal of Machine Learning Research 7 (2006) 1–30.