How can I have an "undefined" category in multi-class classification

Question

I'm trying to classify several websites by category (finance, health-care, IT, etc...). I have at my disposal the content of the pages of the websites, and I use the words to classify. For now, I have manually classified some website to train a naive bayes model.

As I'm mostly interested in a high precision (e.g a classified website must be in the right category), I would like to add an "undefined" category in which a website would end up if it is not close enough to the other categories. To be clear, it's not a problem for me if a website is not classified, it's a problem if it is misclassified.

Are there algorithms that would allow this, or a way to train an "undefined" category ?

My best guess for now is to train something like a random forest and define a "minimum score" below which a website is "undefined".

Answer 1

Absolutely you can create an approach that forces high-precision class tagging algorithm (at the natural cost of recall). What's more- you can do this with (at least) any method that provides a percentage calue for predictions, which is the vast majority of classifiers. The key is, as you mention, to find the minimum acceptable value of precision and cut the predictions at that value.

If a minimum precision is your only constraint and your solution is not sensitive to the recall (getting all or the highest possible proportion of the websites correctly classified), this is a very simple matter. Some lower percentage of your observations will be classified, but those that are will be more likely to be correctly classified.

For example- if your Precision floor is 70%, your cut could look something like this:

Obeservation predictions falling into the green segment could be classified as positive examples, and predictions falling into the red segment would be unclassified.

This approach would be sufficient for Naive Bayes. Some other approaches (SVM, gradient boosting machines etc) may benefit from a custom loss function definition, in which you define a function that disproportionately punishes false positive predictions.

Something like:

$(y_i = 0) \rightarrow (d = s)\wedge (y_i = 1) \rightarrow (d=1)$

$L(p) = \frac {\sum_i\frac{(p_i-y_i)^2}{d}}{n_i}$

$L(p)$ = loss function

$p_i$ = predicted class likelihood

$y_i$ = actual class (0 for negative example, 1 for positive)

$n_i$ = number of observations

$s$ = Penalty parameter for false positives.

Would heavily punish false positives relative to false negatives. It can also be adjusted to your needs, to more or less heavily punish false positives. For $s = .5$, the function looks something like:

Please note that this function does not necessarily define the approach you should take, but only one possible approach. To create a custom loss function perfectly tailored to your use case, you'd want to know the relative cost of a false positive and a false negative, and customize the function accordingly.

Answer 2

Thomas Cleberg's approach sounds reasonable, but another very simple approach would be to explicitly code an "undefined" category. This is common when dealing with text datasets where a word might be new or too rare to stand on its own.

With a large enough collection of websites, surely there are website that are not cleanly classified in one of your categories. Worst case you could simply search for such websites manually and augment your dataset. This approach wouldn't require any changes to how you train your models.