Inter-node Hellinger Distance based Decision Tree

1 Introduction

Three of the major tasks in machine learning are Feature Extraction, Feature Selection, and Classification [Iqbal et al., 2017; Sharmin et al., 2019; Kotsiantis et al., 2007]. In this study, we only focus on the classification task. One of the simplest and easily interpretable classification methods (also known as classifiers) is decision tree (DT) [Quinlan, 1986]. It is a tree-like representation of possible outcomes to a problem. Learning of a DT is a greedy approach. Nodes in a DT can be categorized into two types: decision nodes and leaf nodes. At each decision node, a locally best feature is selected to split the data into child nodes. This process is repeated until a leaf node is reached where the further splitting is not possible. The best feature is selected based on a splitting criterion which measures the goodness of a split. One of the most popular splitting criteria is Information Gain (IG) [Quinlan, 1986; Breiman et al., 1984] which is an impurity based splitting criterion (i.e., entropy and gini). DTs based on IG perform quite well for balanced datasets where the class distribution is uniform. However, as class prior probability is used to calculate the impurity of a node, in an imbalanced dataset, IG becomes biased towards the majority class which is also called skew sensitivity [Drummond and Holte, 2000].

To improve the performance of standard DTs, several splitting criteria are proposed to construct DTs in Distinct Class based Splitting Measure (DCSM) [Chandra et al., 2010], Hellinger Distance Decision Tree (HDDT) [Cieslak and Chawla, 2008] and Class Confidence Proportion Decision Tree (CCPDT) [Liu et al., 2010]. Besides these, to deal with class imbalance problem in Lazy DT construction, two skew insensitive split criteria based on Hellinger distance and K-L divergence are proposed in [Su and Cao, 2019]. Since Lazy DTs use the test instance to make splitting decisions, in this paper, we omit it from our discussion.

In DCSM, the number of distinct classes in a partition is incorporated. Trees generated with DCSM is smaller in size, however, DCSM is still skew sensitive because of its use of class prior probability. HDDT and CCPDT propose new splitting criteria to address the class imbalance problem. However, the Hellinger distance based criterion proposed in HDDT can perform poorly when training samples are more balanced [Cieslak and Chawla, 2008]. At the same time, HDDT fails more often to differentiate between two different splits (specifically for multiclass problems) which is illustrated in the following example:

Assume, there are 80 samples, 40 of class A, 20 of class B, 10 of class C and rest of class D. Two splits (split X and Y) are compared where each split has 50 observations on the left child and the rest on the right child. Split X channels all the samples of class A and class D into the left child, and the rest to the right child while Split Y places all the samples of class A, 5 each of classes C and D into the left child, and the rest to the right child. It is easily observable that, Split X is more exclusive than Split Y. However, HDDT cannot differentiate between these two splits and provides the same measure.

On the other hand, instead of using class probability, CCPDT calculates the splitting criteria like entropy and gini using a new measure called Class Confidence Proportion (CCP) which is skew insensitive. However, it uses HDDT to break ties while splits based on two different features provide the same split measure. Hence, CCPDT exhibits the same limitation as HDDT.

To address the limitations of the above methods, we propose a new splitting criterion called Inter-node Hellinger Distance (iHD) which is skew insensitive. We then propose iHDw which adds a weight to iHD to make sure child nodes are purer without forgoing skew insensitivity. Both iHD and iHDw exhibit exclusivity preference property defined in [Taylor and Silverman, 1993]. Rigorous experiments over a large number of datasets and statistical tests are performed to show the superiority of iHD and iHDw for the construction of DTs.

The rest of the paper is organized in the following manner. In Section 2, several related node splitting criteria for DTs are discussed. The new node splitting criteria are presented in Section 3. In Section 4, datasets, performance measures, and experimental results are described. Finally, Section 5 concludes the paper.

2 RelatedWork

In this section, we discuss several split criteria for DT related to our proposed measure.

2.1 Information Gain

Information Gain (IG) calculates how much "information" a feature gives about the class, and measures the decrease of impurity in a collection of examples after splitting into child nodes. IG for splitting a data, (X, y) with attribute A and threshold, T is calculated using (1).

where V is the number of partitions and Imp is the impurity measure. Widely used impurity metrics are Entropy [Quinlan, 1986] and Gini Index [Breiman et al., 1984] and calculated using (2) and (3) respectively.

where k is the number of classes. When data are balanced, IG gives a reasonably good splitting boundary. However, when there is an imbalanced distribution of classes in a dataset, IG becomes biased towards the majority classes [Drummond and Holte, 2000]. Another drawback of IG is that it favors attributes with a large number of distinct values. To reduce this bias, a new criterion called Gain Ratio (GR) [Quinlan, 1993] was proposed by taking account of the size of a split while choosing an attribute. GR defines the size of a split, g as (4).

GR is just the ratio between IG and g, defined in (5).

2.2 DCSM

Chandra et. al. proposed a new splitting criterion called Distinct Class based Split Measure (DCSM) that emphasizes the number of distinct classes in a partition [Chandra et al., 2010]. For a given attribute xj and V number of partitions, the measure M(xj) is defined as (6).

where C is the number of distinct classes in the dataset, u is the splitting node (parent) representing xj and v represents a partition (child node). D(v) denotes the number of distinct classes in a partition v, δ(v) is the ratio of the number of distinct classes in the partition v to that of u, i.e., D(v) D(u) and a(v) ωk is the probability of class ωk in the partition v.

The first term D(v) ∗ exp(D(v)) deals with the number of distinct classes in a partition. It increases when the number of distinct classes in a partition increases causing purer partitions to be preferred. The second term is a(v) ωk ∗ exp(δ(v) (1(a(v) ωk )2 )). Here, impurity decreases when δ(v) decreases. On the other hand, (1 - (a(v) ωk )2 )) decreases when there are more examples of a class compared to the total number of examples in a partition. Hence, the DCSM is intended to reduce the impurity of each partition when it is minimized.

The main difference between DCSM and other splitting criteria is that DCSM introduces the concept of distinct classes. The limitation of DCSM is same as IG. It cannot deal with imbalanced class distribution and thus, is biased towards the majority classes.

2.3 HDDT

Hellinger Distance Decision Trees (HDDT) uses Hellinger distance as the splitting criterion to solve the problem of class imbalance [Cieslak and Chawla, 2008; Cieslak et al., 2012]. The details of Hellinger distance is presented in Section 3. In HDDT, Hellinger distance (dH) is used as a split criterion to construct a DT. Assume a two-class problem (class + and class -) and, X+ and X- are the set of classes + and - respectively. Then, dH between the distributions, X+ and Xis calculated as (7).

Here, instead of using class probability, normalized frequencies aggregated over all the p partitions across classes are used. HDDT is strongly considered to be skew insensitive because of not using prior probability in the distance calculation. However, the split criterion defined in (7) only works on the binary classification problem. For the multiclass classification problem, a technique named Multi-Class HDDT [Hoens et al., 2012] is proposed. They decompose the multi-class problem into multiple binary class problems by using the similar of One-Versus-All (OVA) decomposition technique. For each binary class problem, they calculate DH and the maximum is taken as the split measure for an attribute. However, as HDDT tries to make pure leaves by capturing deviation between class conditionals which results in smaller coverage, thus can perform poorly for more balanced class distribution [Cieslak and Chawla, 2008].

2.4 CCPDT

Another decision tree algorithm named Class Confidence Proportion Decision Tree (CCPDT) is proposed in [Liu et al., 2010] where they introduce a new measure named Class Confidence Proportion (CCP) calculated as (8).

where Class Confidence (CC) is defined in (9).

CCP is insensitive to the skewness of class distribution because of not focusing on class priors. In CCPDT, CCP is used to replace p(y|X) in Entropy/Gini to calculate IG. Whenever there is a tie between two attributes in IG value, the Hellinger distance (same as in HDDT) is used to break the tie. For which, CCPDT has the same limitation as HDDT of performing poorly for more balanced datasets.

Different from the above approaches, we propose new splitting criteria for DTs which provide better results for both balanced and imbalanced datasets.

3 ProposedMethod

In this section, we propose two new splitting criteria named Inter-node Hellinger Distance (iHD) and wighted iHD (iHDw) for constructing DT classifiers.

3.1 Inter-node Hellinger Distance

We use squared Hellinger distance (D2H ) to measure the dissimilarity between the class probability distributions of the parent and each of the child nodes in a split. The distance is intended to be maximized so that the instances in the parent node are divided into mutually exclusive regions. Note that, the Hellinger distance is a divergence measure which is a member of α divergence family [Cichocki and Amari, 2010]. For two discrete probability mass functions, P = (p1, p2, ..., pk) and Q = (q1, q2, ..., qk), the α divergence is defined in (10).

where α /∈ {0, 1}. For α = 12 , we obtain DH from (11).

Hellinger distance has the following basic properties :

• DH is symmetric (DH(P||Q) = DH(Q||P)) and nonnegative.
• DH is in [0,1]. It takes its maximum value when ∑kj=1 pjqj = 0 and minimum value when pj = qj , ∀j.
• DH(P||Q) is convex with respect to both P and Q.
• DH satisfies the triangle inequality, DH(P||Z) ≤ DH (P||Q) + DH (Q||Z).

Suppose, there are N number of samples in a node distributed over k classes. For a binary split, N samples are divided into left (L) and right (R) child nodes which are NL and NR respectively. The class probability distribution for the parent node is P(p1, ..., pk) and, for the left and right child nodes are PL(pL1, ..., pLk) and PR(pR1, ..., pRk) respectively. D2H between the class probability distribution of the parent and left child D2H (PL||P) and, the parent and right child D2H (PR||P) are calculated using (12).

where k is the number of classes. From these distances, the proposed splitting criterion Inter-node Hellinger Distance (iHD) is defined as (13).

Note that, the difference between the use of Hellinger distance in iHD and HDDT is that, in iHD, the distance between the class probability distributions of the parent and child nodes are measured rather than the distance between the class pairs over all partitions. As a consequence of the triangle inequality of DH, maximizing the distance between the class probability distributions of the parent and the child nodes also maximizes the distance between the distributions of the two child nodes.

Properties of iHD

iHD has the exclusivity preference property (proved in Theorem 1) which is expected for a good splitting criterion [Taylor and Silverman, 1993; Shih, 1999]. This property is defined by the following two conditions:

1. Firstly, for a certain value of ρLρR, the criterion has the maximum value when ∑kj=1 pLjpRj = 0 which indicates that the two child nodes are mutually exclusive.
2. Secondly, regardless of ρLρR, it obtains its minimum value when the class probability distributions of child nodes are identical which can be defined as pLj = pRj = pj , ∀j.

Theorem 1. iHD has the exclusivity preference property.

Proof. From (13), iHD can be written as:

For a certain value of ρLρR, (14) is maximum when the value from the summation over all classes is minimum. In other words, (14) is maximum when we get the minimum value separately for each class in the summation. Let, for j th class, aj = pLj and bj = pRj for a fixed ρL = 1 - ρR ̸= 0. Thus, pj = ρLaj +ρRbj which is a nonzero constant. Now, the j th term in the summation can be expressed by a function of aj as follows:

The second derivative of f(aj) is:

Here, f ′′ (aj) < 0 in the interval of 0 ≤ aj ≤ pj ρL , thus is a concave function. Hence, f(aj) has the minimum value at one of the extreme points of the interval which is either aj = 0 or aj = pj ρL (equivalent to bj = 0). Now, for regardless of ρLρR, when pLj = pRj = pj , ∀j, (14) becomes:

Therefore, iHD is minimum when pLj = pRj = pj , ∀j.

From the exclusivity preference property of iHD, we can say that it is minimum when D2H (PL||P) = D2H (PR||P) = 0 which means the parent and child nodes have the same probability distribution. And iHD gets its maximum when the samples at the parent node are distributed among the child nodes as disjoint subsets of classes.

Moreover, iHD is skew insensitive in the sense that maximizing iHD in a split focuses on generating mutually exclusive child nodes whatever class distribution there is in the parent node.

3.2 Weighted Inter-node Hellinger Distance

To obtain purer child nodes in a split we also consider a weight, w for each partitioned node which is defined as (15).

where Nj and Ntj are the number of samples in a class j at the parent and the child node t respectively. Here, instead of using class probability, the proportion of instances of each class from the parent node placed in the child node t is used to calculate wt. For which, wt is not dependent on the prior probability of a class, thus, is not biased towards the majority classes. It is easy to say from (15) that for any value of ρt, wt will give maximum value of 1 when for any class j, ptj = 0. And, when the difference between the proportion of samples of classes of the parent node ( Ntj Nj ) increases in a child node t, wt increases, thus favors a purer partition. On the other hand, wt gives the minimum value of 0 when all the samples of a parent node come to a single child node t.

The distance measure and the weight (defined in (12) and (15) respectively) for each partition are combined to formulate the final proposed splitting criterion named weighted Inter-node Hellinger Distance (iHDw) as (16).

The weighted sum by the proportion of samples (ρt, i ∈ {L,R}) is taken to evaluate the contribution from each partition and to favor partitions with similar sizes. As the Hellinger distance DH and the weight w are both nonnegative, the proposed splitting criterion is also non-negative.

Properties of iHDw

Now, we prove that the splitting criterion iHDw also preserves the exclusivity preference property.

Theorem 2. iHDw has the exclusivity preference property.

Proof. As Theorem 1 states that iHD has the exclusivity preference property, it is enough to show that, after incorporating the weights to iHD, iHDw also provides the maximum value when the child nodes are mutually exclusive and minimum value when the parent and child nodes have identical class probability distributions.

Here, wt from (15) gives maximum value of 1 when for any class j, pLj = 0. Hence, for ∑kj=1 pLjpRj = 0, it is straightforward to say that wL = wR = 1, thus fulfills the first condition of the exclusivity preference property.

Regardless of the value of wL ∗ wR, iHDw gets its minimum value of 0 as D2H (PL||P) = D2H (PR||P) = 0 for pLj = pRj = pj, ∀j (second property of DH) which fulfills the second condition of the exclusivity preference property.

Therefore, the combination of the two terms prefers a split with child nodes purer and mutually exclusive. We also show the behavior of optimal splits using iHDw in Theorem 3.

Theorem 3. iHDw on its optimal split channels the classes to two disjoint subsets s and sc ⊂ {1, 2, ..., k} where s minimizes | ρL - 1 2 |.

Proof. From (16) we rewrite iHDw as

where wL = wR = 1. Let denote (17) as a function of ρL:

Second derivative of f(ρL) is:

Hence, f(ρL) is a concave function and is symmetric w.r.t pL = 1 2 , thus f(ρL) takes its maximum at ρL = 12 .

Algorithm 1 outlines the procedure of learning a binary DT using the proposed split criterion iHDw.

3.3 An Illustrative Example

Let consider a sample dataset with two classes (Class "A" and "B") having two features (f1 and f2) shown in Table 1. The number of samples for class "A" and "B" are 4 and 8 respectively, thus having imbalance class ratio. In Figures 1 and 2, two DTs constructed using iHD and iHDw are shown respectively. We observe that at the first split iHD and iHDw choose two different split points using feature f2 and unlike iHD, iHDw produces a pure child. In the final tree for iHDw, we find that none of the samples from the minority class is misclassified. On the other hand, although the final tree for iHD produces two pure leaf nodes, the minority class can be misclassified in the other leaf nodes. Moreover, the DT based on iHDw has fewer impure leaf nodes than that of iHD.

4 Experiments and Results

In this section, we first describe the datasets used in the experiments followed by the description of the performance measures. We then present the results obtained from the experiments with proper discussion.

4.1 Description of Datasets

Table 2 shows 40 datasets chosen from various areas like biology, medicine and finance. Datasets are grouped into two sets: Balanced datasets and Imbalanced datasets. These datasets are collected from two well-known public sources called UCI Machine Learning Repository [Dua and Graff, 2017] and KEEL Imbalanced Data Sets [Alcal´a-Fdez et al., 2011]. Imbalance Ratio (IR) between the samples of majority and minority classes is also shown in Table 2. The higher value of IR indicates the dataset is highly imbalanced.

4.2 Performances Measures

For each dataset, we build eight unpruned DT classifiers based on iHD, iHDw, information gain (using both Entropy and Gini), Gain Ratio (GR) and, the splitting criteria proposed in DCSM, HDDT and CCPDT respectively. For balanced datasets accuracy (%) is used as the performance measure. Since accuracy as an evaluation measure is inappropriate for class imbalance problem [Chawla et al., 2004], we use the area under the ROC curve (AUC) [Hand and Till, 2001] for imbalanced datasets. We conduct 10-fold cross-validation on each dataset to get the unbiased result.

The method proposed in [Demˇsar, 2006] is used to compare the performance of DT classifiers based on iHD and iHDw with other six methods. For comparing different classifiers over multiple datasets, Demsar proposed the use of Iman's F statistic [Iman and Davenport, 1980] using Friedman's χ2F statistic [Friedman, 1937; Friedman, 1940]. χ2F statistic is calculated as follows:

Iman's F statistic is then calculated from χ2F as (19).

where k is the number of compared classifiers and Ri is the average rank of ith classifier on N datasets. After rejecting the null hypothesis that all the classifiers are equivalent, a post-hoc test called Nemenyi test [Nemenyi, 1963] is used to determine the performance of which classifier is significantly better than the others. Based on the Nemenyi test, the performance of a classifier can be said significantly different than others if the difference between their corresponding average ranks is larger than a critical difference (CD) which is calculated as:

where qα is the critical value for the two-tailed Nemenyi test for k classifiers at α significance level.

4.3 Experimental Results

Tables 3 and 4 represent the comparison of eight classifiers on balanced and imbalanced datasets respectively. The results of Friedman test (Fr.T) with two "Base" classifiers (iHD and iHDw) are shown in the last two lines of the Tables 3 and 4. The " ✓" sign under a classifier indicates that the "Base" classifier significantly outperforms that classifier at 95% confidence level.

The average ranks based on the accuracy of the compared classifiers indicate that the iHDw is the best performing criterion compared to others on the balanced datasets. Friedman's χ2F statistic from these average ranks is 35.77 according to (18). From which, we get Iman's F statistic as 6.52 (using (19)). With eight classifiers and 20 balanced datasets, the critical value, F(7, 133) is 2.31 at 95% confidence level, thus rejects the null hypothesis (as FF > Fα=0.05) that, all the eight classifiers are equivalent. After conducting the posthoc Nemenyi test, we see that iHD significantly outperforms other compared methods except for Entropy and HDDT while iHDw outperforms all the compared methods.

For imbalanced datasets, the average ranks based on AUC also indicate the superiority of iHDw against other seven classifiers. Friedman's χ2F statistic is 32.42 followed by Iman's F statistic as FF = 5.72. Since at 95% confidence level FF is larger than the critical value, F(7, 133), the performance of the eight classifiers are not equivalent on the imbalanced datasets. The post-hoc Nemenyi test states that the iHDw is the best performing classifier by outperforming Entropy, Gini, DCSM, GR, HDDT and CCPDT while iHD only outperforms Gini.

Between iHD and iHDw, iHD performs better than iHDw on balanced datasets. However, the counts of Win/Tie/Loss (W/T/L) of iHD and iHDw against other classifiers suggests that DTs based on iHDw is the better performing classifier in most of the cases. Therefore, from the above results, we can say that although iHD gives better performance than iHDw on balanced datasets, taking account of the comparisons with other methods, iHDw is considerably better performing classifier on both balanced and imbalanced datasets. As unpruned DTs are constructed, we also compare the node size and tree construction time of the eight classifiers. However, we do not find major differences between iHD and iHDw compared to the best performing existing criterion on node size and construction time. Moreover, DT using iHDw provides superior performance without requiring much additional time to construct the tree than iHD.

5 Conclusion

In this paper, we propose two new splitting criteria for measuring the goodness of a split in a decision tree learning. The proposed splitting criteria favor mutually exclusive and purer partitions. Results over a large number of datasets provide the evidence that the decision trees constructed using proposed criteria are better than other six related splitting criteria on both balanced and imbalanced datasets. As future research direction, we will extend the work for tree-based ensemble classifiers and also want to investigate the effect of the proposed split criteria on pruning techniques.

Acknowledgments

This research is supported by the fellowship from ICT Division, Ministry of Posts, Telecommunications and Information Technology, Bangladesh. No - 56.00.0000.028.33.002.19.3; Dated 09.01.2019.