Decision trees for anomaly detection

Question

Problem

From what I understand, a common method in anomaly detection consists in building a predictive model trained on non-anomalous training data, and perform anomaly detection using the error of the model when predicting on the observed data. This method requires the user to identify non-anomalous data beforehand.

• What if it's not possible to label non-anomalous data to train the model?
• Is there anything in literature that explain how to overcome this issue?

I have an idea, but I was wondering if someone has heard for something similar before, and could point me to the right direction (link papers/blogs, or explain existing methods).

Idea

I'd like to train a decision tree on a dataset $X$ with $N$ rows, $p$ columns, having a real valued target variable $Y$ (it's a regression problem). The dataset $X$ contains both anomalous and non-anomalous objects. The decision tree training process generates groups of objects, splitting the dataset iteratively along one dimension, at each iterations. The decision trees during prediction assigns an object to a specific leaf node. Each leaf node will have a certain distribution of values of the target variable Y. An anomalous object in this problem it's the one which doesn't perform well, more precisely an object for which Y is too low.

• Can I use the distribution in a leaf node to perform anomaly detection?
• Assuming that a bigger value for Y is preferred, can I say that the entities in the lowest 5th percentile of Y in a node are outliers?

Example

The decision tree assigns to the node j the objects following the rule: $2 <= x_1 < 4$ and $5 <= x_2 < 7$, where $x_1$ and $x_2$ are two columns of the dataset. If I run a prediction on the entire dataset, the values of Y in the node j have have a gaussian distribution (mean=25, std=3), and I consider the values with $Y < 20.5$ outliers. The idea is that objects with $x_1$ and $x_2$ within a range, should perform similarly, and never below a target value.

Considerations

*First of all, I can see that this problem can be generalized to other methods. However, I find decision trees easier to explain here, moreover, I find the hard clustering property of trees useful for my problem, as I also need to cluster objects together. *Second, I can see the issue of training the model with both anomalous and non-anomalous data. Though, I'm wondering whether due to some property, with a big amount of data, the leaf node's distribution move's toward the optimal (value of Y of the non-anomalous objects). But I guess this depends on the ration between anomalous vs non-anomalous objects.

Any hint in the right direction would help.

Answer 1

Can I use the distribution in a leaf node to perform anomaly detection?

Yes, in principle you can, but it might not be a good idea to use terminal-node-specific distributions to define outliers. Selected splits can be unstable, and thereby the minima, maxima, 1st and 3rd quartiles of the distributions in the terminal node, too.

Assuming that a bigger value for Y is preferred, can I say that the entities in the lowest 5th percentile of Y in a node are outliers?

No. Unless you want to have 5% of observations classified as outliers, by default. A general (and probably more appropriate) rule-of-thumb for defining outliers is based on the inter-quartile range (IQR), according to which all values below Q1-1.5*IQR and Q3+1.5IQR would be outliers.

It sounds a bit like you are reinventing residual analysis. Why not compute residuals ($\hat{y} - y$), and inspect the distribution of those values to see if there are outliers (e.g., using the IQR-based rule above)? IMHO, such checking of residuals should be performed after fitting any predictive model.

Answer 2

Existing data is usually assumed to be non-anomalous, not labeled. One can have a bit of anomalous data in there as well without too much of an issue (contamination). Some anomaly detection algorithms allows to specify an estimate of the ratio of contamination. For example in scikit-learn IsolationForest or LocalOutlierFactir.