ROC-Tree Algorithm for Stratification of Binary Classifier Sets with Varied Discrimination Threshold

Introduction

Binary classifier systems where its elements are classified into two groups are used in multiple practical situations. These in-clude: medical testing or prognostic (risk prediction) models, quality control, fraud detection, and machine learning and in-formation retrial. However, evaluation of diagnostic ability of a binary classifier as its discrimination threshold is varied often requires data transformation by performing aggregation opera-tions. Aggregating individual observations into groups is used in a various field of sciences as a form of categorization when the discrete groups (strata) of data are created. Grouped data serves as a convenient means of summarizing or analyzing the data. Identification of discrete groups is one of the most important and difficult tasks of data mining, that is why finding a good classifier and classification algorithm is an important component of data mining. The selection of this threshold value (possibly subjective) can have dramatic effects on model accuracy [1]. One of the most used aggregation methods is division by percentiles (quartiles as a special case of percentiles division) which divides the data set at the equal by size subgroups independently from the structure of data. We developed a ROC-tree algorithm for selection of threshold values which is recursive downwards splitting of each group at the two subgroups (branches) by cut-off point of ROC curve.

We hypothesized that opposite to the percentiles division, the ROC-tree algorithm allows to define optimal (natural) boundar¬ies and number of groups.

Materials and Methods

The ‘Credit Card Fraud Detection’ dataset downloaded from https://www.kaggle.com/mlg-ulb/creditcardfraud was used for the illustration of algorithm. The datasets contain transactions made by credit cards in September 2013 by European cardholders.

As a pre-processing step we used we used ROC based feature selection to handle class imbalance classification problem. The AUC for all possible classifiers variables are presented in appendix, Table 1B. 

                    Table 1B: Selection of variable for the classification using ROC-tree algorithm.

The Youden Index (Bookmaker Informedness) was used for selection of cut-off points in recursive downwards dividing sub-group into two new subgroups (branches). An area under the curve less than 0.65 in at least one subgroup of iteration was considered as an exit condition while cut-off points and number of subgroups from the previous iteration were taken for further analysis (Figure 1).

Figure 1: Flowchart shows ROC-tree algorithm of data aggregation. The division of all data at the two subgroups by Youden index followed by the second round of division at the two sequential subgroups.

The iterative usage of traditional default threshold of 0.5 as the cut-off generated four discrete groups (quartiles) with equal number of observations.

The comparison of classification algorithms was made using methods similar to the evaluation of multiclass classification. Similar to the assessment of the multiclass classification algo-rithms in machine learning, the one-vs-one reduction was used (Appendix A, Fig A1). Where applicable, the derivations of the 2*2 confusion matrix are presented as their macro-averages of post-hoc procedure results (one-vs-one pairwise comparison). A macro-average is the average of a metric computed independently for each class while treating all classes equally. The confusion ma- trix for binary classification is presented in Fig A2 (Appendix A).

The 10-fold stratified cross-validation procedure, where each fold has the same proportion of observations with the class out¬come value, was used for internal validation of classification algorithm. The capabilities of algorithms were estimated as the average of performance metrics [2].

The list of variables used in the study and their equations are presented in Appendix A.

The R 3.6.3 for Windows with RStudio 1.2.5033 3 and standard packages with libraries ‘lattice’, ‘readr’ were used for the classification of data and calculation of derivates of contingency tables for the comparison of classification algorithms.

Results

Credit Card Fraud Detection’ data set presents transactions that occurred in two days, where was 492 case of frauds out of 284,807 transactions. The dataset is highly unbalanced, the positive class (frauds) account for 0.172% of all transactions. The Imbalance ratio, which value lies within the [0, ∞] range, having a value IR = 1 in the balanced case was close to 0 (IR = 0.002) and imbalance coefficient (δ = - 0.997) with expected values within the [ −1, 1] range, and 0 value for the perfectly balanced classes.

Iteration of ROC curve procedure through 28 discrimination parameters (Appendix B. Table 1B) uncover several variables with high AUC. Variable V4 (Figure 1, AUC 0,938) was used as a classifier for the ROC-tree downwards splitting. The density plot (Figure 2) shows that the distribution of cases with and without fraud by V4 parameter are different. Two-sample Kolm-ogorov-Smirnov test confirmed that V4 distribution is different in cases with and without fraud (D = 0.7664, p-value < 2.2e-16). However, Bhattacharyya distance for V4 case is 0.626 and Bhattacharyya coefficient (a measure of the amount of overlap between two statistical samples or populations) is 0,535.

Figure 2: Kernel Density Estimation plot whole data set. V4 (mean ± std 8.32E-13 ± 1,42; minimum -5.68; maximum 16.88).

Both methods of stratification create 4 groups (Tables 1 and 2) with statistically significant differences with expected distribu-tions. However, projection of cut-off point at the density chart (Fig.3) illustrates the fact that in case of quartiles algorithm most of fraud+ cases concentrated in group 4. ROC-tree algorithm provides more “fair” spreading cases with the highest density of fraud+ in the third  group (Figure 3)

Figure 3: Cut-off points an groups areas projected at the density graph. ROC-tree algorithm (a) provides more “fair” spreading cases with the highest density of fraud+ in the third group

                     Table 1: Stratification at 4 groups using ROC-tree algorithm.

                                          Table 2: Stratification at 4 quartiles groups.    

Distribution of cases with and without fraud by V4 using ROC-tree algorithm or quartiles division presented at the figure 4. The results of one-vs-one reduction for the assessment of the multi- class classifications are presented as macro-average of performance metrics (Table 3).

                                  Figure 4: Density plots though 10 generated folds are similar.

                                 Table 4: Number of cases and classifier* mean ± std per fold

Procedure of 10-fold cross-validation was done at the next way. Of the 10 folds, a single fold was reserved as the validation data for testing the model, and the remaining 9 subsamples were used as training sets of data. The cross-validation process is then re¬peated, with each of the 10 folds used exactly once as the validation data. The results from the folds were averaged to produce a single estimation.

The results of cross validation metrics included in the study are presented in the tables 2b ….16b, Appendix B. The differences between macro-average of metrics ROC-tree and quartiles algorithms of stratification were preserved during cross-validation procedure. However, the relative bias and mean square error of algorithm were statistically not different from 0 (One Sample t-test) and did not differ in ROC-tree vs Quartiles groups for all metrices included in the study. Additionally, computing confusion table metrics in control folds through cross-validation procedure of quartiles algorithm in 10% failed in comparison gr 3 vs 2, 3 vs 1 and 20% in comparison gr 2 vs 1 for GM, OP, and Youden index. This effect can be caused apparent to unsensitiv-ity of quartiles algorithm to the distribution of fraud -/fraud + cases and concentration of most of fraud+ in fourth group (Fig-ure.3).   

Discussion

We evaluated the quality of two classification (aggregation) al-gorithms: ROC-tree and division at quartiles. The universal na-ture of the aggregation task allows to use for the demonstration of the algorithm ‘Credit Card Fraud Detection’ dataset down-loaded from https://www.kaggle.com/mlg-ulb/creditcardfraud. This dataset contains much more cases than any available med¬ical dataset. ‘Credit Card Fraud Detection’ preserves the imbal¬ance structure inherent to the medical data. Furthermore, using dataset distant from the healthcare allows to avoid unnecessary discussion around acceptability of predictive scores (e.g. Euro-score, syntax score, CSA-AKI, Charlson comorbidity index, et cetera).

Classification methods are used in various fields of biological and medical sciences as a form of categorization when the dis- crete groups (strata) of data are created. Classification is one of the most important and difficult tasks of data mining, which is why finding a good classifier and classification algorithm is an important component of data mining. Classification into several tiers is the further step in the organization and understanding data. For example: division at high, medium, and low risk, based on scores of the patient cohort is an important step in the organization and understanding clinical contexts [4].

One of the most often used algorithm for division dataset into tiers is division at percentiles with creation of strata with similar number of cases or usage of early predefined cut-off points are traditional specially in medical investigations.

In the two-class classification task, the Receiver Operating Characteristic (ROC) curve is one of the most widely used tools to assess the performance of algorithms [5, 6]. The area under the receiver operating characteristic curve (AUC) (also referred to as the c statistic) is by far the most popular index of discrim¬ination ability ROC curves have an attractive property: they are insensitive to changes in class distribution [7]. The ROC curves are independent of the proportion of positive to negative instances in a test set [8].

Several researchers have investigated the application ROC curves not only as a metrics of classification successes. Ferri et al. (2002) altered decision trees to use the AUC-ROC as their splitting criterion [9,10]. Another example of binary decision tree construction algorithm based at c-statistics is developed by Hossain et al. (2008). These authors used an AUC measure to select a node based on its classification performance and then used the misclassification rate to choose a split point [11]. In our study, we adapted the idea of ROC-tree as a form of tree which divides the classification process at a number of smaller steps which are intuitive and generally easily interpretable [12]. However, we used the Youden index (Bookmaker Informedness) for the determination of the optimal cut-off point. The misclassi-fication rate as a complement of accuracy (one can be calculated from the other) can be misleading when the data are imbalanced, because of the dominating effect of the majority class [5, 13].

The Youden index, in contrast to the accuracy, directly includes a true positive and a true negative rate. This index is recognized as suitable performance metrics of the classification of imbalanced datasets [14].

 The selection of performance metrics is another issue considered in this study. Accuracy and error rate, sensitivity and specifici¬ty are the most often used metrics for summarizing the perfor-mance of classification models. Comparing different classifiers using these measures is easy, but it has many problems such as the sensitivity to imbalanced data and ignoring the performance of some classes [13, 15-17]. Class imbalance is one of the sig¬nificant issues which affect the performance of classifiers [18]. The determination of the most suitable performance metrics is a major issue in the classification of class imbalanced datasets [14]. In imbalanced datasets, not only is the class distribution skewed, the misclassification cost is often uneven too. The mi¬nority class examples are often more important than the majority class examples [5].

It is recommended to consider a combination of different mea-sures instead of relying on only one measure when dealing with class-imbalance data [13]. Hybrid threshold metrics, such as the Geometric Mean or the Bookmaker Informedness showed to be useful as performance metrics for imbalance datasets [14, 19]. The F-measure (harmonic mean) is also recommended as the measure in this case.19 However, it still completely ignores true negatives which can vary freely without affecting the statistic [20]. The Matthews correlation coefficient (MCC) described as least influenced by imbalanced data [13].

In our study, we used hybrid measures for comparison of clas-sification algorithms. The macro-average of the Youden index as a metric of discriminative power was significantly higher for the ROC-tree algorithm in the one-vs-one comparison (Table 3) [21]. Also, other hybrid threshold metrics such as optimized precision, geometric mean had difference with higher values of macro-averages for the ROC-tree algorithm in the one-vs-one comparison.

The “reproducibility” of cut-off points and metrices were tested by the 10-folds cross-validation which is more stable extension of split-sample validation [2, 22]. In this case cut-off points were determined in nine of the ten and testing in one of the ten, which is repeated ten times. In this way, all cases have served once to test the model. The performance is commonly estimated as the average of all assessments [2]. The cut-off points derived using the full dataset are accepted as unique and can be used for further evaluation [23].

Study Limitations

Extending the number of studied datasets could increase the power of derived conclusions. The power of conclusions could also be increased by including more known confusion table deri-vates which could lead to the selection of most effective com-bination of classification performance metrics. We defined an optimal cut-off point in ROC analysis using the Youden index. However, a comparision of stabilty of cut-off points computed by other known methods could help in selecting optimal metrics for the determination of the splitting point.

The effects of sampling techniques such as down-sampling with reducing the number of samples in majority class and the assessment the differences in proportion of minority class in datasets were not evaluated in our study. However, these methods are known and recognized as effective in machine leaning fields. To some extent, the development of ‘failure to rescue’ as a quality indicator is an example of down-sampling in health care [24, 25].

In our study, the metrics in the one-vs-one comparison of classes were computed independently for each class and then their av¬erages were compared. These macro-averages treated all classes equally. The combination of this approach with micro-average, which aggregates the contribution of all classes, to compute the average metric, could be effective in the evaluation of the effect of the individual classes.

Conclusion

Using algorithms sensitive to the distribution patterns, e.g. ROC-tree algorithm showed a better stratification at groups by natural cut-off points determined by the data set composition which is more convenient for summarizing or analyzing data in a vari¬ous fields of sciences. In health care described algorithm allows effective evaluation of mortality causes and quality control spe¬cialized medical care by hospitals. Declarations

Ethics Approval and Consent to Participate

Consent for Publication

Not applicable.

Availability of Data and Materials

The datasets generated and/or analyzed during the current study are available in the Kaggle repository, https://www.kaggle.com/ mlg-ulb/creditcardfraud

Competing interests

The authors declare that they have no competing interests

Funding

this work was not supported by any funding

References

1. Freeman, E. A., & Moisen, G. G. (2008). A comparison of the performance of threshold criteria for binary classifica­tion in terms of predicted prevalence and kappa. Ecological modelling, 217(1-2), 48-58.
2. Alonzo, T. A. (2009). Clinical prediction models: a practi­cal approach to development, validation, and updating: by Ewout W. Steyerberg.
3. Team, R. C. (2018). R: A language and environment for sta­tistical computing; 2018.
4. Wang, X., Wang, F., Hu, J., & Sorrentino, R. (2015). To-wards actionable risk stratification: A bilinear approach. Journal of biomedical informatics, 53, 147-155.
5. Weng, C. G., & Poon, J. (2008, November). A new evalua­tion measure for imbalanced datasets. In Proceedings of the 7th Australasian Data Mining Conference-Volume 87 (pp. 27-32).
6. Swamidass, S. J., Azencott, C. A., Daily, K., & Baldi, P. (2010). A CROC stronger than ROC: measuring, visualiz­ing and optimizing early retrieval. Bioinformatics, 26(10), 1348-1356.
7. Wu, Y. C., & Lee, W. C. (2014). Alternative performance measures for prediction models. PloS one, 9(3), e91249.
8. Fawcett, T. (2006). An introduction to ROC analysis. Pat­tern recognition letters, 27(8), 861-874.
9. Hand, D. J., & Till, R. J. (2001). A simple generalisation of the area under the ROC curve for multiple class classifica­tion problems. Machine learning, 45(2), 171-186.
10. Ferri, C., Flach, P., & Hernández-Orallo, J. (2002, July). Learning decision trees using the area under the ROC curve. In Icml (Vol. 2, pp. 139-146).
11. Hossain, M. M., Hassan, M. R., & Bailey, J. (2008, April). ROC-tree: A novel decision tree induction algorithm based on receiver operating characteristics to classify gene ex­pression data. In Proceedings of the 2008 SIAM Interna­tional Conference on Data Mining (pp. 455-465). Society for Industrial and Applied Mathematics.
12. HAN, Jiawei, PEI, Jian, et KAMBER, Micheline. Data min­ing: concepts and techniques. Elsevier, 2011.
13. Akosa, J. (2017, April). Predictive accuracy: A misleading performance measure for highly imbalanced data. In Pro­ceedings of the SAS Global Forum (Vol. 12).
14. LUQUE, Amalia, CARRASCO, Alejandro, MARTÍN, Ale­jandro, et al. The impact of class imbalance in classification performance metrics based on the binary confusion matrix. Pattern Recognition, 2019, vol. 91, p. 216-231.
15. THARWAT, A. Classification assessment methods. Appl Comput Inform 2018.
16. Sokolova, M., Japkowicz, N., & Szpakowicz, S. (2006, December). Beyond accuracy, F-score and ROC: a family of discriminant measures for performance evaluation. In Australasian joint conference on artificial intelligence (pp. 1015-1021). Springer, Berlin, Heidelberg.
17. Amin, A., Anwar, S., Adnan, A., Nawaz, M., Howard, N., Qadir, J., ... & Hussain, A. (2016). Comparing oversampling techniques to handle the class imbalance problem: A cus­tomer churn prediction case study. IEEE Access, 4, 7940-7957.
18. POTOLEA, Rodica et LEMNARU, Camelia. A Compre­hensive Study of the Effect of Class Imbalance on the Per­formance of Classifiers. In : ICEIS (1). 2011. p. 14-21.
19. HOSSIN, Mohammad et SULAIMAN, Md Nasir. A review on evaluation metrics for data classification evaluations. International journal of data mining & knowledge manage­ment process, 2015, vol. 5, no 2, p. 1.
20. Powers D and Ailab (2011) Evaluation: From precision, re­call and F-measure to ROC, informedness, markedness & correlation. J Mach Learn Technol, 2, 2229-3981.
21. YOUDEN, William J. Index for rating diagnostic tests. Cancer, 1950, vol. 3, no 1, p. 32-35.
22. Berrar D .(2018). Cross-Validation. Reference Module in Life Sciences
23. FARAGGI, David et SIMON, Richard. A simulation study of cross-validation for selecting an optimal cutpoint in uni-variate survival analysis. Statistics in medicine, 1996, vol. 15, no 20, p. 2203-2213.
24. FARJAH, Farhood, BACKHUS, Leah, CHENG, Aaron, et al. Failure to rescue and pulmonary resection for lung can­cer. The Journal of Thoracic and Cardiovascular Surgery, 2015, vol. 149, no 5, p. 1365-1373. e3.
25. Johnston, M. J., Arora, S., King, D., Bouras, G., Almoudaris,
26. A. M., Davis, R., & Darzi, A. (2015). A systematic review to identify the factors that affect failure to rescue and escala­tion of care in surgery. Surgery, 157(4), 752-763.