3
$\begingroup$

I’m working on an application where I have data points that can assigned to one of two classes, say positive and negative, where positive occurs very infrequently.

I need to build a classifier that takes a point and returns 1 if it is extremely confident that it is a positive instance, and 0 otherwise. The goal here is to keep a 0 false positive rate while maximizing recall.

This is essentially an anomaly detection problem where I have training data but cannot afford false positives. Given this constraint, I'd like to maximize the accuracy/recall. Are there algorithms that are best-suited for this? I’ve been experimenting with logistic regression as it provides a probability of classification, but am not completely satisfied with the results.

I believe a somewhat ideal solution would be a decision tree-like algorithm whose optimization goal was to create as many completely homogenous leaves of a size above a configurable threshold. However I’m not aware of any such algorithm, and suspect the problem is likely NP-hard anyway (to determine the optimal tree at least)…

$\endgroup$
3
  • $\begingroup$ What is FP a false positive rate? Decision tree methods like CART are not computationally difficult. $\endgroup$ Apr 25, 2017 at 22:36
  • $\begingroup$ Yes, I've updated the title to be more clear. CART trees are effiicient but will not always yield homogenous leaves, as they don't optimize for it. If there was an opportunity to split into two low-entropy leaves or split into one homogenous leaf and a high-entropy leaf, CART trees would choose the former while I'd prefer the latter. I'd much rather than a few large homogenous leaves and terrible classification on the rest of the data versus decent classification across all leaves. Also, the class imbalance in my dataset may yield to poor FP results in normal trees as well. $\endgroup$
    – Ryan C.
    Apr 25, 2017 at 22:47
  • $\begingroup$ CART has more than one splitting rule. Also trimming is an important aspect of it. Random Forests is considered to be an improvement over CART although it is more complicated. $\endgroup$ Apr 25, 2017 at 23:32

2 Answers 2

3
$\begingroup$

The only way to achieve a false positive rate of zero is never calling something a positive case. If this is not a satisfactory solution, then it becomes a matter of balancing the consequences of wrong decisions.

It sounds like false positives in this situation are terrible. If the consequences are absolutely awful, you might not be willing to risk a false positive and choose to consider everything a negative. This position can be defended. Someone could argue, "I'm never going skydiving. It looks fun, but there's always a chance the parachute won't deploy, and then I'd die. I'm not risking dying just for a few minutes of fun."

And it's possible to argue that skydiving is so fun that it's worth the small risk of dying.

$\endgroup$
0
$\begingroup$

You don't need any particular algorithm to do this, you just need to tweak the objective function that's being optimized. Any optimization algorithm will attempt to optimize some particular value, whether that's accuracy, sum-of-squares error, etc. To optimize the false positive rate, you just need to upweight errors of a particular class. When optimizing accuracy, we don't care whether we call a positive a negative or vice versa, each misclassification counts equally and adds the same amount to the objective score. Instead, you can apply weights to particular misclassifications, for example a false negative adds 1 to the objective score while a false positive adds 100 to the objective score. With this weighting, the classifier will prefer having 99 false negatives to having even a single false positive.

You can set your weighting to reflect the relative cost of false positives/negatives. In the limit of an arbitrarily high weight ratio, you'll find false positives absolutely unacceptable, resulting in a degenerate classifier that calls everything negative, as that's the only way to be sure you'll never find a false positive.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.