ML Algorithms to discriminate "known" from "unknown" instances

Question

I'm classifying different electrical devices based on features extracted from their electricity consumption into a household-specific model built from around 10 devices. Now I want to detect whether a classified testing instance is coming from a device which has not been present in the training set, i.e. I want to discriminate known from unknown devices.

I'm working with Weka and use the Classifier.distributionForInstance() method to give me the (classifier-specific) probability distribution for those 10 possible classes for each instance.

Now, the problem is that some classifiers (SMO, NaiveBayes, J48 and other trees) most of the time classify a not known device with a high probability of almost 1 to a class, whereas RandomForest (preferably with high amount of trees) and IBk (kNN) perform rather well in giving back lower probabilities of classification/more uncertain results.

The questions I have: Can you think of alternative approaches or any other algorithms/methods? Why is it, that the first stated algorithms strongly decide for one class. I would have expected them to return unclearer results.

thx, regards

Answer 1

I would use a two-step pipeline where the first step discriminates between known and unknown and the second step performs the actual classification. This approach has a number of benefits.

1. Separating the two problems allows you to judge the accuracy of each step. You can assess the quality of your known/unknown discrimination independently of your actual classifier and vice versa. This will tell you where you need to focus your efforts.

2. You don't need to worry about your classifier being over confident for examples you aren't actually interested in since presumably you're taking care of this beforehand.

3. The known/unknown discrimination is just the problem of outlier detection. There are lots of ways to approach this and you may be able to find methods designed to work within your specific problem domain. I frequently hear 1-class SVMs (support vector machines) come up in this context, but have never worked with them personally.

If you think about the way decision trees work it is pretty easy to see why a single tree is going to be overconfident. There are lots of different ways to learn decision trees, but in general you can think about them as trying to make the leaves as pure as possible, i.e., we want the leaves to contain instances that all have the same class. Since an unknown example is just going to follow some path down the decision tree, it will end up in a leaf, which by construction, contains little class variability. From this observation it is easy to see why combining many different trees (like in Random Forests) is going to help avoid this problem.

As for why Naive Bayes is being overconfident, I would guess this is due to some combination of one of the class priors $P(y)$ being larger than the others, and/or having most features be unknown for your unknown example (so $P(x_i|y)$ is approximately the same for all $y$ and most $i$ if you're smoothing the estimates) and a couple show up in one class causing the $\prod_i P(x_i|y)$ term to blow up for one $y$ relative to the others. This is just a guess without the data.