Classification with unknown class

Question

I would like to know how to train a classifier that is able to recognize a couple of classes and records that do not belong to any of the existing classes.

Let's say there are 2 classes:

• High
• Low

But it can happen that some records do not belong to either of those classes, so we need a third state, like not recognized or other:

• High
• Low
• Other

How to train such a classifier? I'm guessing that this question could also be related to anomaly detection, since you identify examples that differ from what is expected.

Answer 1

A viable alternative is to create two models:

• High vs. Low & Other
• Low vs. High & Other

You'll get probabilities $\text{P(High|Data)}$ and $\text{P(Low|Data)}$. If neither probability is higher than a threshold (say $50\%$) you can label the instance as $\text{Unknown}$ instead.

---

Example in R

An example in R using kernlab's ksvm (any probabilistic classifier would work).

library(kernlab)

#our data
x = as.matrix(iris[,-c(2,4,5)])
y = iris$Species

#our new classes
ysetosa = (y == "setosa") + 0
yversic = (y == "versicolor") + 0

#our two models
fitsetosa = ksvm(y = ysetosa, x = x, type = "C-bsvc", prob.model = TRUE)
fitversic = ksvm(y = yversic, x = x, type = "C-bsvc", prob.model = TRUE)

#the class predictions
predsetosa = predict(fitsetosa, x, type = "probabilities")
predversic = predict(fitversic, x, type = "probabilities")

#the unknown probability is 1 minus the other probabilities
pred = cbind(setosa = predsetosa[,2L], versicolor = predversic[,2L], unknown = 1 - predsetosa[,2L] - predversic[,2L])

tail(pred)

#> tail(pred)
#            setosa  versicolor   unknown
#[145,] 0.009275878 0.005356246 0.9853679
#[146,] 0.009058278 0.141930931 0.8490108
#[147,] 0.009945749 0.101307355 0.8887469
#[148,] 0.009903443 0.034164283 0.9559323
#[149,] 0.009027848 0.002268708 0.9887034
#[150,] 0.009679991 0.028774113 0.9615459

We know the last 50 examples in iris are neither setosa nor versicolor, and this is reflected in the respective probabilities.

---

Issues

The difference can generate negative probabilities. Better methods for probability coupling exist and should be used instead. I'm fairly sure you can edit kernlab ones (mostly based on binary probabilities) to not sum to 1, which in practice would result in the example I created.

Answer 2

Yes, looks like anomaly detection problem. What you could also try is to generate artificial samples for your third class and train your model using them. Of course, the other question is how you generate it. But this highly depends on problem you solve.

Answer 3

This depends on your classifier. Any method that assigns weights to each class and then use a decision rule could be modified to your method. For instance, a random forest typically uses majority voting. Say you have one with 1000 decision trees. You could modify the method so as to use majority vote only if one of your classes is predicted by at least, say, 600 decision trees, otherwise output "Unknown" if the vote counts are too close, i.e. both are between 400 and 600.

Answer 4

Probably you don't need to change your classifier at all, just the way how you interpret results. E. g. if you have 2 classifiers and first one predict 10% probability that training sample belongs to it's class and the second one predict 9% probability, then it seems that training sample doesn't belong to any of that classes, so you can just label it as "other".