Conference Paper2019Cited by 20

Inter-node Hellinger Distance based Decision Tree.

Pritom Saha Akash, Md Eusha Kadir, Amin Ahsan Ali, Mohammad Shoyaib

IJCAI

International Joint Conferences on Artificial Intelligence Organization, pp. 1967–1973

DOI: 10.24963/ijcai.2019/272Open AccessURL

Abstract

This paper introduces a new splitting criterion called Inter-node Hellinger Distance (iHD) and a weighted version of it (iHDw) for constructing decision trees. iHD measures the distance between the parent and each of the child nodes in a split using Hellinger distance. We prove that this ensures the mutual exclusiveness between the child nodes. The weight term in iHDw is concerned with the purity of individual child node considering the class imbalance problem. The combination of the distance and weight term in iHDw thus favors a partition where child nodes are purer and mutually exclusive, and skew insensitive. We perform an experiment over twenty balanced and twenty imbalanced datasets. The results show that decision trees based on iHD win against six other state-of-the-art methods on at least 14 balanced and 10 imbalanced datasets. We also observe that adding the weight to iHD improves the performance of decision trees on imbalanced datasets. Moreover, according to the result of the Friedman test, this improvement is statistically significant compared to other methods.

Keywords

  • Hellinger distance
  • class imbalance

CCDS Authors

Amin Ahsan Ali, PhD
Amin Ahsan Ali, PhD

Amin Ahsan Ali, PhD

  • Director, AI/ML Wing

Professor

Department of Computer Science and Engineering

Independent University, Bangladesh

Published at

ACL, CHI, UbiComp, ECCV, IJCAI, ECAI, WACV, IPSN, PAKDD, LREC, IJCNN, ICPR, ICIP, BEA, BLP, ICMLA, Scientific Reports, Scientific Data, Pattern Recognition, Information Sciences, Ad Hoc Networks, Drug and Alcohol Dependence, PLOS ONE

Research Interests

Artificial Intelligence, Machine Learning

References

  1. 1.Arthur Asuncion. (2007). UCI Machine Learning Repository. Medical Entomology and Zoology
  2. 2.J.R. Quinlan. (1986). Induction of Decision Trees. Machine Learning, 1(1), 81–106[10.1023/a:1022643204877]
  3. 3.J. R. Quinlan. (1986). Induction of decision trees. Machine Learning, 1(1), 81–106[10.1007/bf00116251]
  4. 4.Janez Demšar. (2006). Statistical Comparisons of Classifiers over Multiple Data Sets. , 7(1), 1–30
  5. 5.J. Praagman. (1985). Classification and regression trees. European Journal of Operational Research, 19(1), 144[10.1016/0377-2217(85)90321-2]
  6. 6.Milton Friedman. (1937). The Use of Ranks to Avoid the Assumption of Normality Implicit in the Analysis of Variance. Journal of the American Statistical Association, 32(200), 675–701[10.1080/01621459.1937.10503522]
  7. 7.Sotiris Kotsiantis. (2007). Supervised Machine Learning: A Review of Classification Techniques. , 160(3), 249–24
  8. 8.Milton Friedman. (1940). A Comparison of Alternative Tests of Significance for the Problem of $m$ Rankings. The Annals of Mathematical Statistics, 11(1), 86–92[10.1214/aoms/1177731944]
  9. 9.Jesús Alcalá‐Fdez, Alberto Fernández, Julián Luengo, J. Derrac, Salvador García, Luciano Sánchez, Francisco Herrera. (2011). KEEL Data-Mining Software Tool: Data Set Repository, Integration of Algorithms and Experimental Analysis Framework. , 17, 255–287
  10. 10.David J. Hand, Robert J. Till. (2001). A Simple Generalisation of the Area Under the ROC Curve for Multiple Class Classification Problems. Machine Learning, 45(2), 171–186[10.1023/a:1010920819831]
  11. 11.Ronald L. Iman, James M. Davenport. (1980). Approximations of the critical region of the fbietkan statistic. Communication in Statistics- Theory and Methods, 9(6), 571–595[10.1080/03610928008827904]
  12. 12.Andrzej Cichocki, Shun-ichi Amari. (2010). Families of Alpha- Beta- and Gamma- Divergences: Flexible and Robust Measures of Similarities. Entropy, 12(6), 1532–1568[10.3390/e12061532]
  13. 13.David A. Cieslak, T. Ryan Hoens, Nitesh V. Chawla, W. Philip Kegelmeyer. (2011). Hellinger distance decision trees are robust and skew-insensitive. Data Mining and Knowledge Discovery, 24(1), 136–158[10.1007/s10618-011-0222-1]
  14. 14.David A. Cieslak, Nitesh V. Chawla. (2008). Learning Decision Trees for Unbalanced Data. Lecture notes in computer science, 241–256[10.1007/978-3-540-87479-9_34]
  15. 15.Chris Drummond, Robert C. Holte. (2000). Exploiting the Cost (In)sensitivity of Decision Tree Splitting Criteria. , 239–246
  16. 16.Wei Liu, Sanjay Chawla, David A. Cieslak, Nitesh V. Chawla. (2010). A Robust Decision Tree Algorithm for Imbalanced Data Sets. , 766–777[10.1137/1.9781611972801.67]
  17. 17.Sadia Sharmin, Mohammad Shoyaib, Amin Ahsan Ali, Muhammad Asif Hossain Khan, Oksam Chae. (2019). Simultaneous feature selection and discretization based on mutual information. Pattern Recognition, 91, 162–174[10.1016/j.patcog.2019.02.016]
  18. 18.B. Chandra, Ravi Kothari, Pallath Paul. (2010). A new node splitting measure for decision tree construction. Pattern Recognition, 43(8), 2725–2731[10.1016/j.patcog.2010.02.025]
  19. 19.T. Ryan Hoens, Qi Qian, Nitesh V. Chawla, Zhi-Hua Zhou. (2012). Building Decision Trees for the Multi-class Imbalance Problem. Lecture notes in computer science, 122–134[10.1007/978-3-642-30217-6_11]
  20. 20.Paul C. Taylor, Bernard W. Silverman. (1993). Block diagrams and splitting criteria for classification trees. Statistics and Computing, 3(4), 147–161[10.1007/bf00141771]
  21. 21.Md Tauhid Bin Iqbal, Mohammad Shoyaib, Byungyong Ryu, M. Abdullah-Al-Wadud, Oksam Chae. (2017). Directional Age-Primitive Pattern (DAPP) for Human Age Group Recognition and Age Estimation. IEEE Transactions on Information Forensics and Security, 12(11), 2505–2517[10.1109/tifs.2017.2695456]
  22. 22.Chong Su, Jie Cao. (2018). Improving lazy decision tree for imbalanced classification by using skew-insensitive criteria. Applied Intelligence, 49(3), 1127–1145[10.1007/s10489-018-1314-z]
  23. 23.J. R. Quinlan. (1992). C4.5: Programs for Machine Learning.
  24. 24.Nitesh V. Chawla, Nathalie Japkowicz, Aleksander Kołcz. (2004). SPECIAL ISSUE ON LEARNING FROM IMBALANCED DATA SETS. , 6(1), 1–6

Cited By

  1. 1.Swagatam Das, Sankha Subhra Mullick, Ivan Zelinka. (2022). On Supervised Class-Imbalanced Learning: An Updated Perspective and Some Key Challenges. IEEE Transactions on Artificial Intelligence, 3(6), 973–993[10.1109/tai.2022.3160658]
  2. 2.Tanujit Chakraborty, Ashis Kumar Chakraborty. (2020). Hellinger Net: A Hybrid Imbalance Learning Model to Improve Software Defect Prediction. IEEE Transactions on Reliability, 70(2), 481–494[10.1109/tr.2020.3020238]
  3. 3.Wanan Liu, Hong Fan, Meng Xia. (2022). Tree-based heterogeneous cascade ensemble model for credit scoring. International Journal of Forecasting, 39(4), 1593–1614[10.1016/j.ijforecast.2022.07.007]
  4. 4.Bartosz Krawczyk, Colin Bellinger, Roberto Corizzo, Nathalie Japkowicz. (2021). Undersampling with Support Vectors for Multi-Class Imbalanced Data Classification. , 1–7[10.1109/ijcnn52387.2021.9533379]
  5. 5.Md. Eusha Kadir, Pritom Saha Akash, Sadia Sharmin, Amin Ahsan Ali, Mohammad Shoyaib. (2019). Can a simple approach identify complex nurse care activity?. , 736–740[10.1145/3341162.3344859]
  6. 6.Md. Nazmul Haque, Mahir Mahbub, Md. Hasan Tarek, Lutfun Nahar Lota, Amin Ahsan Ali. (2019). Nurse care activity recognition. , 719–723[10.1145/3341162.3344848]
  7. 7.Md. Eusha Kadir, Pritom Saha Akash, Sadia Sharmin, Amin Ahsan Ali, Mohammad Shoyaib. (2020). A Proximity Weighted Evidential k Nearest Neighbor Classifier for Imbalanced Data. Lecture notes in computer science, 71–83[10.1007/978-3-030-47436-2_6]
  8. 8.Michael J. Siers, Md Zahidul Islam. (2020). Class Imbalance and Cost-Sensitive Decision Trees. ACM Transactions on Knowledge Discovery from Data, 15(1), 1–31[10.1145/3415156]
  9. 9.Avivit Levy, B. Riva Shalom, Michal Chalamish. (2025). A guide to similarity measures and their data science applications. Journal Of Big Data, 12(1)[10.1186/s40537-025-01227-1]
  10. 10.Somayeh Abolhosseini, Mohammad Khorashadizadeh, Majid Chahkandi, Mousa Golalizadeh. (2024). A modified ID3 decision tree algorithm based on cumulative residual entropy. Expert Systems with Applications, 255, 124821[10.1016/j.eswa.2024.124821]
  11. 11.Carlos Ortega Vázquez, Seppe vanden Broucke, Jochen De Weerdt. (2023). Hellinger distance decision trees for PU learning in imbalanced data sets. Machine Learning, 113(7), 4547–4578[10.1007/s10994-023-06323-y]
  12. 12.Chakraborty, Tanujit, Chakraborty, Ashis Kumar. (2018). Superensemble Classifier for Improving Predictions in Imbalanced Datasets. arXiv (Cornell University)[10.1080/23737484.2020.1740065]
  13. 13.Ming Liu, Minggang Dong, Chao Jing. (2020). A modified real-value negative selection detector-based oversampling approach for multiclass imbalance problems. Information Sciences, 556, 160–176[10.1016/j.ins.2020.12.058]
  14. 14.Minggang Dong, Ming Liu, Chao Jing. (2022). One-against-all-based Hellinger distance decision tree for multiclass imbalanced learning. Frontiers of Information Technology & Electronic Engineering, 23(2), 278–290[10.1631/fitee.2000417]
  15. 15.Yiqun Zhang, Shenghong Cai, Zihua Yang, Sen Feng, Yuzhu Ji, Haijun Zhang. (2026). One-Shot Federated Clustering of Non-Independent Completely Distributed Data. IEEE Internet of Things Journal, 13(7), 14964–14978[10.1109/jiot.2026.3650778]
  16. 16.Ashis Kumar Chakraborty, Barin Karmakar. (2023). Software Defect Prediction Through a Hybrid Approach Comprising of a Statistical Tool and a Machine Learning Model. Lecture notes in operations research, 1–19[10.1007/978-981-19-8012-1_1]
  17. 17.Takeru Araki, Yuan Luo, Minyi Guo. (2022). Performance Improvement Validation of Decision Tree Algorithms with Non-normalized Information Distance in Experiments. Lecture notes in computer science, 450–464[10.1007/978-3-031-20862-1_33]
  18. 18.S. Abolhosseini, Mohammad Khorashadizadeh, M. Golalizadeh, M. Chahkandi. (2024). A Modified Id3 Decision Tree Algorithm Based on Cumulative Residual Entropy. SSRN Electronic Journal[10.2139/ssrn.4682847]
  19. 19.Dan Li, Songcan Chen. (2022). A Novel Splitting Criterion Inspired by Geometric Mean Metric Learning for Decision Tree. 2022 26th International Conference on Pattern Recognition (ICPR), 5, 4808–4814[10.1109/icpr56361.2022.9956124]
  20. 20.Md. Eusha Kadir, Md. Mumtahin Habib Ullah Mazumder, Muhammad Mahbub Alam, Mohammad Shoyaib. (2026). An Evidential Dynamic Neighborhood Approach to Learn from Imbalanced Data. Annals of Data Science[10.1007/s40745-026-00709-0]
← All publications