Decision trees for anomaly detection

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.