Inter-node Hellinger Distance based Decision Tree

Pritom Saha Akash, Md. Eusha Kadir, Amin Ahsan Ali, Mohammad ShoyaibIJCAI 2019 · DOI

TL;DR

This paper introduces two novel splitting criteria for decision trees, Inter-node Hellinger Distance (iHD) and its weighted version (iHDw), designed to improve performance on imbalanced datasets. By focusing on the mutual exclusivity and purity of child nodes, these criteria demonstrate superior accuracy and robustness compared to existing methods across a wide range of datasets.

What Problem Does This Paper Address?

Decision trees (DTs) are a popular and interpretable machine learning algorithm for classification. However, traditional splitting criteria, like Information Gain (IG), suffer from "skew sensitivity." This means they are biased towards majority classes in imbalanced datasets, leading to suboptimal performance. While several criteria have been proposed to address this, such as Hellinger Distance Decision Trees (HDDT) and Class Confidence Proportion Decision Trees (CCPDT), they still have limitations, including performing poorly on balanced datasets or struggling to differentiate between splits in multiclass problems. This paper aims to bridge this gap by proposing new criteria that are both skew-insensitive and perform well on both balanced and imbalanced datasets.

Methods

The core contribution of this paper is the introduction of two new splitting criteria:

  • Inter-node Hellinger Distance (iHD): This criterion measures the dissimilarity between the class probability distributions of a parent node and its child nodes using the squared Hellinger distance. The goal is to maximize this distance, encouraging child nodes to represent mutually exclusive regions of the data. A key insight is that maximizing the distance between parent and child nodes indirectly maximizes the distance between the child nodes themselves, due to the properties of the Hellinger distance.
  • Weighted Inter-node Hellinger Distance (iHDw): This is an extension of iHD that incorporates a weight term. This weight is designed to further encourage purer child nodes by considering the proportion of instances from each class that are moved to a child node. This weighting mechanism is also skew-insensitive as it doesn't rely on class prior probabilities.

Both iHD and iHDw are proven to possess the "exclusivity preference property," a desirable characteristic for splitting criteria that ensures mutually exclusive child nodes are favored.

Datasets

The authors evaluated their proposed methods on a benchmark of 40 datasets. These datasets were divided into two categories:

  • 20 Balanced Datasets: Collected from publicly available sources.
  • 20 Imbalanced Datasets: Specifically chosen from the KEEL Imbalanced Data Sets repository, with the Imbalance Ratio (IR) provided for each.

Key Insights and Ideas

  • Mutual Exclusivity is Key: The paper highlights that focusing on the mutual exclusivity of child nodes, in addition to their purity, is crucial for robust decision tree performance, especially in imbalanced scenarios.
  • Hellinger Distance as a Bridge: The Hellinger distance, when applied between parent and child nodes, proves to be a powerful tool for achieving both exclusivity and skew-insensitivity.
  • Weighting for Purity: The iHDw criterion demonstrates that adding a carefully designed weight can further enhance child node purity without sacrificing skew-insensitivity, leading to improved overall performance.
  • Statistical Significance: The use of Friedman tests and Nemenyi post-hoc tests provides strong statistical evidence for the superiority of the proposed methods over existing ones.

Key Results

The paper reports significant improvements in decision tree performance using iHD and iHDw:

  • Balanced Datasets: iHD won against six other state-of-the-art methods on at least 14 datasets, while iHDw outperformed all compared methods.
  • Imbalanced Datasets: iHD won against six other state-of-the-art methods on at least 10 datasets, and iHDw significantly outperformed all other methods.
  • Statistical Significance: Friedman tests confirmed that the performance improvements of iHDw were statistically significant compared to other methods on both balanced and imbalanced datasets.
  • Illustrative Example: A small, imbalanced dataset example visually demonstrates how iHDw produces a purer tree with fewer misclassifications compared to iHD.

Limitations and Future Work

  • Unpruned Trees: The experiments were conducted on unpruned decision trees. The authors note that they did not find major differences in node size or construction time between iHD/iHDw and other methods, suggesting that iHDw offers superior performance without significant overhead.
  • Future Directions: The authors suggest extending their work to tree-based ensemble classifiers and investigating the effect of their proposed criteria on pruning techniques.

Summary updated

BibTeX
@inproceedings{akash2019inter,
  author = {Pritom Saha Akash and Md. Eusha Kadir and Amin Ahsan Ali and Mohammad Shoyaib},
  title = {{Inter-node Hellinger Distance based Decision Tree}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/272},
}
Figure