Classifier that optimizes performance on only a subset of the data?

Question

I'm working on machine learning problem where I'm only interested in getting high accuracy within a narrow band of my predicted likelihoods. Specifically, I want an algorithm that will score very accurately when it predicts a likelihood above a specific threshold.

A motivating example:

I'm presented with 1 million closed boxes, 10 percent of which contain a gold coin. The likelihood of a box containing a gold coin is associated with physical characteristics of the boxes. I'm allowed to open 500K boxes, chosen at random, to see which contain the coins. After this, I'm allowed to choose 100 of the remaining 500K boxes and keep any gold that I find.

I'm looking to build a classifier to solve this problem. Specifically, I'm looking for the correct way to incorporate the constraint that I am only able to open 100 boxes in the test sample. Put another way, my measure of performance is limited to a subsample of my test data, so I need a classifier that is highly accurate when it predicts the highest likelihoods. Prediction errors outside of these 100 boxes are of zero concern.

I'm aware of cost-weighted loss functions that penalize false positives/negatives differently, but I'm not familiar with any that solve this specific problem of optimizing for a localized accuracy.

Specifically, I'm trying to answer two questions:
1) Are there specific classification algorithms well suited for this type of problem? 2) Can I modify the loss function used on my training set to produce a high localized accuracy within these specific 100 boxes?

Answer 1

There are at least two approaches:

1. Train on a subsample of data. 100 positive examples and only 100 negative examples (randomly sampled from all negative samples).
2. Create a 2 pass system. 1st pass uses a high recall algorithm, selects reasonable options (eliminate options that are not reasonable). The 2nd pass is a high precision algorithm. It only looks possible options and selects the most likely options.

Answer 2

I want to clarify that the fact that you can pick only 100 boxes from the test dataset is NOT a limitation (like you describe it). You just need to see it from this perspective:

How to pick the 100 boxes (out of 500K) that MOST LIKELY contain gold?

A very suitable algorithm would be a Decision Tree classifier. By using the Information Gain (based on Entropy Reduction), it can learn which features can split the dataset more accurately into two classes, i.e. the one that contains gold and the one that doesn't, and neglect (prune) the weakest attributes. After that, you will not only have a trained classifier but also gain insight on which features are the most important to make the decision (very important information).