That is a pretty common problem in machine learning. There are tons of solutions, but they are usually classifier specific. For example, if using a decision t

That is a pretty common problem in machine learning. There are tons of solutions, but they are usually classifier specific. For example, if using a decision tree, one can take test data and determine for each leaf node in the tree what fraction of instances are classified correctly. For leaf nodes with accuracy below X, change the output of that node to "give up".