PaperlayerView exact revision on arXiv

Source-linked AI summary

Precision-Recall Curve (PRC) Classification Trees

Jiaju Miao, Wei Zhu

arXiv:2011.07640v1stat.MLcs.LG

TL;DR

Imbalanced class distributions challenge classifiers designed for balanced data, especially in applications requiring minority-class identification. The paper proposes PRC-based tree and forest methods that use AUPRC and F-measure during tree building, and reports superiority over rival tree-based algorithms for skewed classification problems.

  • Problem

    Class-imbalanced data challenge standard classification algorithms and are common in applications such as disease diagnosis, fraud detection, bankruptcy prediction, and suspect identification.

  • Method

    The PRC classification tree selects node variables by maximizing AUPRC and thresholds by maximizing the F-measure, with PRC random forests using PRC trees as base classifiers.

  • Results

    The proposed methods are reported as superior to other tree-based algorithms for skewed classification problems across the evaluated datasets.

  • Takeaways & Limitations

    PRC trees, PRC random forests, and PRC-ROC combinations show promise for identifying the minority class in imbalanced data.

Abstract

from arXiv · show

The classification of imbalanced data has presented a significant challenge for most well-known classification algorithms that were often designed for data with relatively balanced class distributions. Nevertheless skewed class distribution is a common feature in real world problems. It is especially prevalent in certain application domains with great need for machine learning and better predictive analysis such as disease diagnosis, fraud detection, bankruptcy prediction, and suspect identification. In this paper, we propose a novel tree-based algorithm based on the area under the precision-recall curve (AUPRC) for variable selection in the classification context. Our algorithm, named as the "Precision-Recall Curve classification tree", or simply the "PRC classification tree" modifies two crucial stages in tree building. The first stage is to maximize the area under the precision-recall curve in node variable selection. The second stage is to maximize the harmonic mean of recall and precision (F-measure) for threshold selection. We found the proposed PRC classification tree, and its subsequent extension, the PRC random forest, work well especially for class-imbalanced data sets. We have demonstrated that our methods outperform their classic counterparts, the usual CART and random forest for both synthetic and real data. Furthermore, the ROC classification tree proposed by our group previously has shown good performance in imbalanced data. The combination of them, the PRC-ROC tree, also shows great promise in identifying the minority class.

1 Introduction

KDD develops methods for extracting useful information from data, with classification serving as a supervised-learning tool for predicting class labels. Decision trees represent decisions through feature-threshold splits and terminal-node class labels, while random forests add bootstrap and feature-selection randomness.

  • KDD focuses on methodologies for extracting useful information from data.
  • Classification is supervised learning that predicts class labels from correctly identified training observations.
  • Decision trees represent features and thresholds as branching nodes that end in class-labeled leaves.
  • Random forests use bootstrap samples and randomly selected feature subsets during tree construction.
  • Randomly selecting features reduces correlation between trees and can reduce overfitting.

2 Class imbalance problem

Class imbalance requires methods that account for unequal misclassification costs, data distributions, and minority-class performance. The paper reviews cost-sensitive, resampling, algorithmic, and ensemble approaches alongside precision, recall, and F-measure evaluation.

  • Class imbalance approaches: Class-imbalance solutions include cost-sensitive learning, data-level methods, and algorithm-level approaches.
  • Cost-sensitive learning: Cost-sensitive learning assigns different penalties to false positives and false negatives, often emphasizing minority-class errors.
  • Data-level approaches: Resampling balances classes by undersampling the majority or oversampling the minority, but undersampling can remove valuable information.
  • Algorithm-level approaches: ROC-based tree and forest methods modify training procedures to identify rare cases, while PRC trees and forests develop a different perspective.
  • Performance evaluation: Accuracy can be misleading on unbalanced data because assigning every observation the prevalent label may yield high accuracy but poor rare-class performance.
  • Performance evaluation: Recall measures correctly classified positive samples, precision measures correctly classified predicted positives, and F-measure combines both through their harmonic mean.

3 Methodology

The methodology evaluates ROC performance across classification thresholds using TPR and FPR, then estimates the area under the curve with trapezoidal subareas. The trajectory is partitioned into n-1 sections for this approximation.

  • ROC curve: A ROC curve connects TPR and FPR pairs generated at different classification thresholds.
  • ROC curve: ROC performance uses TPR on the y-axis and FPR on the x-axis to compare classifier separability.
  • AUC estimation: The analysis estimates AUC by approximating the entire area as a sum of trapezoidal subareas.
  • AUC estimation: The ROC trajectory is partitioned into n-1 sections for the area approximation.

3.2 PRC and the area under the precision-recall curve (AUPRC)

The precision-recall curve evaluates positive-class performance by plotting precision against recall across thresholds. AUPRC provides a comparison measure, with higher area indicating better classifier performance.

  • Precision measures the fraction of predicted-positive observations that are truly positive, while recall measures the fraction of actual positives predicted positive.
  • A perfect classifier’s PRC passes through the upper-right corner, representing 100% precision and 100% recall.
  • AUPRC is the stated measure for comparing classifiers using precision-recall curves, with higher values indicating better performance.
  • The PRC trajectory is partitioned into n-1 sections, and AUPRC is estimated using a trapezoidal approach.
  • The AUPRC calculation algorithm sorts observations by a feature, computes precision and recall at unique values, and returns the feature’s area.
  • Unlike ROC construction, PRC does not use true-negative results and is not affected by adding disease-free patients.

3.3 Feature selection

PRC classification trees select node-splitting variables according to their AUPRC. The feature with the largest AUPRC is selected from the candidate set.

  • Feature selection determines which variables enter the model, and these choices strongly influence tree-based model performance.
  • At each tree-node split, the PRC classification tree uses AUPRC to assess which feature variable is useful.
  • The feature-selection procedure evaluates each candidate feature with AUPRC_calculation and returns the feature with the largest AUPRC.

3.4 Threshold selection

PRC trees select each split threshold by maximizing the F1-score on the chosen feature. F1-score is the harmonic mean of precision and recall and excludes true negatives.

  • The optimum threshold for each PRC Tree split is selected by finding the largest F1-score for the chosen feature variable.
  • F1-score combines precision and recall through their harmonic mean.
  • Because F1-score does not account for true negatives, the paper describes it as more effective for classification with imbalanced data.
  • The threshold-selection algorithm evaluates F1-score across unique split values and returns the threshold with the maximum score.

3.5 PRC Tree algorithm

The PRC Tree algorithm combines AUPRC-based feature selection and F1-score-based threshold selection to recursively construct tree splits. It continues until nodes are pure or a stopping criterion is reached.

  • PRC Tree replaces traditional Gini impurity or information gain with AUPRC for feature selection and F1-score for threshold selection.
  • Each terminal partition is formed by products of up to L indicator functions for features selected by the AUPRC algorithm.
  • The algorithm takes training data, features, targets, stopping criteria, and the number of features sampled at each split as inputs.
  • At each recursive stage, the tree samples Nf features, selects the best feature by AUPRC, and chooses its splitting threshold by F1-score.
  • The selected split partitions the data into left and right subsets, then PRC_Tree is applied recursively to those subsets.

3.6 PRC random forest algorithm

The PRC random forest extends the PRC tree into an ensemble by combining bootstrap sampling with random feature selection across multiple trees.

  • PRC random forest uses the PRC tree as its base classifier and is described as providing competitive predictive performance and reliable feature importance estimates.
  • The forest parameter Nt determines the number of trees constructed.
  • Each tree is trained on a bootstrap sample, while Nf features are randomly selected for each node split.

3.7 PRC-ROC Classification Trees

The PRC-ROC classification tree combines precision-recall and ROC information for feature selection, then chooses thresholds using a harmonic-mean criterion. Its random-forest extension uses these trees as base classifiers and retains the ensemble structure of random forests.

  • 3.7.1 Feature selection: The weighting parameter can be tuned from training data and out-of-bag accuracy information.The paper describes OOB samples as enabling performance judgments from training data only.
  • 3.7.1 Feature selection: The PRC-ROC tree selects node features using a weighted average of AUPRC and AUC rather than AUPRC alone.The feature with the largest weighted average is selected for each split.
  • 3.7.2 AUC calculation: The AUC calculation sorts each feature’s data, evaluates threshold-specific true-positive and false-positive counts, and accumulates the area under the curve.
  • 3.7.3 Threshold selection: For the selected feature, the splitting threshold maximizes the harmonic mean of recall, precision, and specificity.Algorithm 8 compares the harmonic-mean score across the feature’s unique split values.
  • 3.7.3 PRC-ROC classification tree: The PRC-ROC tree recursively applies feature selection and threshold selection until nodes are pure or a stopping criterion is met.Stopping criteria include maximum tree depth and minimum leaf size.
  • 3.7.4 PRC-ROC random forest algorithm: The PRC-ROC random forest treats the PRC-ROC tree as its base classifier and is described as offering competitive prediction and reliable feature-importance estimates.Randomly choosing Nf features for each node split is described as potentially decreasing prediction error.

3.8 Complexity of algorithm

The proposed random-forest algorithms have computational complexity determined by the number of trees, sampled features, and observations.

  • O(Nt ∗ Nf ∗ nlog(n)) is the stated random-forest complexity, with Nt trees, Nf features per split, and n observations.The stated per-tree complexity is O(Nf ∗ nlog(n)).

4 Experimental Studies

Experiments evaluate the proposed methods on simulated and real-world imbalanced datasets using five performance metrics. Across scenarios, PRC-based trees and random forests generally improve minority-class identification compared with conventional counterparts.

  • Experimental design: Experiments cover simulated binary-class datasets and several real-world datasets, evaluated with accuracy, specificity, precision, recall, and F1-score.Simulation varies imbalance severity, feature dimension, class separability, and noise; real-world data include financial distress, client default, and breast cancer diagnosis.
  • Scenario 1: Mild imbalance, low dimension: 30% minority-class observations and five Gaussian features define the easy, mildly imbalanced scenario; PRC methods outperform ROC methods in F1-score and accuracy.PRC is slightly better than CART, while PRC-ROC achieves the best performance across metrics among single-tree methods.
  • Scenario 2: Moderate imbalance, higher dimension: Under moderate imbalance with 5-to-15 features, PRC outperforms CART, PRC-ROC improves on PRC in the five-dimensional evaluation, and weighted RF performs best among forests.ROC Tree has perfect specificity and precision but comparatively weak recall in this scenario.
  • Scenario 3: Extreme imbalance, low dimension: With only 1% minority observations, PRC methods outperform CART and ROC particularly in recall, while PRC-ROC leads tree methods in specificity, precision, and F1-score.Among random forests, PRC-ROC RF has the highest recall, accuracy, and F1-score, whereas weighted RF has the best specificity and precision.
  • Scenarios 4–5: Hard classification with noise: In the noisy, hard-to-classify mild-imbalance setting, PRC-ROC surpasses other tree algorithms on every metric except recall, and PRC-ROC RF outperforms the other forests.The setting uses overlapping classes, higher feature dimension, and noisy features.
  • Real-world datasets: Across real-world datasets, PRC random forest generally achieves higher recall and F1-score than traditional random forest, while PRC-ROC RF performs strongly on later datasets.PRC RF achieves the largest accuracy and F1-score in one case, and PRC-ROC achieves the highest precision; in the final two cases, PRC-ROC RF has higher accuracy and F1-score than the other algorithms.

5 Conclusion

The paper studies PRC-based tree and forest methods for skewed classification, including PRC-ROC extensions that combine AUPRC and AUC. Its methods outperform competing algorithms in experiments, while remaining limited to binary classification and models without interaction terms.

  • 5 Conclusion: Four proposed algorithms—PRC Tree, PRC RF, PRC-ROC Tree, and PRC-ROC Tree RF—are studied for skewed classification problems.The PRC-ROC methods use an additional weight parameter to select a weighted combination of AUPRC and AUC from training data.
  • 5 Conclusion: The proposed methods are reported to be superior to other competing algorithms across the evaluated datasets.The conclusion cites F1-score comparisons against other tree-based algorithms.
  • 5 Conclusion: The current PRC tree, PRC forest, PRC-ROC tree, and PRC-ROC forest are designed only for binary classification.The authors identify extension to multiple-class classification as a future research issue.
  • 5 Conclusion: The experiments do not consider interaction terms, leaving interaction-effect discovery as another related research task.The stated future work is to uncover interaction effects within the PRC classification-tree framework.
Loading 2011.07640v1…