PIDT: A novel decision tree algorithm based on parameterised impurities and statistical pruning approaches

TY - CHAP

T1 - PIDT

T2 - 14th IFIP WG 12.5 International Conference on Artificial Intelligence Applications and Innovations, AIAI 2018

AU - Stamate, Daniel

AU - Alghamdi, Wajdi

AU - Stahl, Daniel

AU - Logofatu, Doina

AU - Zamyatin, Alexander

PY - 2018/5/22

Y1 - 2018/5/22

N2 - In the process of constructing a decision tree, the criteria for selecting the splitting attributes influence the performance of the model produced by the decision tree algorithm. The most well-known criteria such as Shannon entropy and Gini index, suffer from the lack of adaptability to the datasets. This paper presents novel splitting attribute selection criteria based on some families of parameterised impurities that we proposed here to be used in the construction of optimal decision trees. These criteria rely on families of strict concave functions that define the new generalised parameterised impurity measures which we applied in devising and implementing our PIDT novel decision tree algorithm. This paper proposes also the S-condition based on statistical permutation tests, whose purpose is to ensure that the reduction in impurity, or gain, for the selected attribute is statistically significant. We implemented the S-pruning procedure based on the S-condition, to prevent model overfitting. These methods were evaluated on a number of simulated and benchmark datasets. Experimental results suggest that by tuning the parameters of the impurity measures and by using our S-pruning method, we obtain better decision tree classifiers with the PIDT algorithm.

AB - In the process of constructing a decision tree, the criteria for selecting the splitting attributes influence the performance of the model produced by the decision tree algorithm. The most well-known criteria such as Shannon entropy and Gini index, suffer from the lack of adaptability to the datasets. This paper presents novel splitting attribute selection criteria based on some families of parameterised impurities that we proposed here to be used in the construction of optimal decision trees. These criteria rely on families of strict concave functions that define the new generalised parameterised impurity measures which we applied in devising and implementing our PIDT novel decision tree algorithm. This paper proposes also the S-condition based on statistical permutation tests, whose purpose is to ensure that the reduction in impurity, or gain, for the selected attribute is statistically significant. We implemented the S-pruning procedure based on the S-condition, to prevent model overfitting. These methods were evaluated on a number of simulated and benchmark datasets. Experimental results suggest that by tuning the parameters of the impurity measures and by using our S-pruning method, we obtain better decision tree classifiers with the PIDT algorithm.

KW - Concave functions

KW - Decision trees

KW - Machine learning

KW - Optimisation

KW - Parameterised impurity measures

KW - Permutation test

KW - Preventing overfitting

KW - Significance level

KW - Statistical pruning

UR - http://www.scopus.com/inward/record.url?scp=85049573675&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-92007-8_24

DO - 10.1007/978-3-319-92007-8_24

M3 - Conference paper

AN - SCOPUS:85049573675

SN - 9783319920061

T3 - IFIP Advances in Information and Communication Technology

SP - 273

EP - 284

BT - Artificial Intelligence Applications and Innovations - 14th IFIP WG 12.5 International Conference, AIAI 2018, Proceedings

PB - Springer New York LLC

Y2 - 25 May 2018 through 27 May 2018

ER -