I am reading through https://arxiv.org/pdf/1609.06676.pdf which presents an extension of the isolation forest algorithm so that categorical features may be taken into account. On page 5, the authors note:

... we extend the algorithm to consider categorical data. Our method only requires that for each categorical dimension, values have an ordering. The ordering may be arbitrary. Each value is then mapped to a numeric value, based on its ordering. For example the values true and false may be mapped to false = 0, true = 1. Having mapped the categorical values to numeric values, the categorical dimensions can be treated the same way as the numeric dimensions in the iForest algorithm.

Does this approach make sense?

At first I thought, doesn't this produce the exact same result as applying Scikit-Learn's LabelEncoder()? However, the authors seem to do it without creating a unique set before ordering. A different way would be One-Hot-Encoding, though this blows the feature space up very quickly for high-cardinal categorical features.


Yes, this sounds like label-encoding (a machine-learning term I never encountered in Statistics) and doesn't make much sense for unordered categorical variables. If the algorithm cannot cope with dummys, maybe try some variant of target/mean encoding (mentioned here).

Use first some linear model (maybe glmnet) with regularization appropriate for a categorical variable with many levels, see Principled way of collapsing categorical variables with many levels?, and then encode the categorical variable with the estimated coefficients for that variable from the linear model? That at least should be worth a try.

  • 1
    $\begingroup$ Thanks but it is not immediately obvious to me that this kind of label-encoding does not make sense in the context of the isolation forest model. The model works entirely without the computation of distance or density metrics. Therefore, any implied ordering caused by the label-encoding should not lead to troubles. The model instead (uniform-)randomly partitions the data set until all data samples are isolated. Unfortunately, in the context of unsupervised anomaly detection (for which the isolation model has been primarily developed), target/mean encoding is not really an option. $\endgroup$ – robot_2077198 Jul 5 '19 at 15:28

By iForest they mean Isolation Forest, an algorithm that

‘isolates’ observations by randomly selecting a feature and then randomly selecting a split value between the maximum and minimum values of the selected feature.

So categorical variable treated as numerical would be partitioned randomly a number of times, eventually grouping the categories into some arbitrary groups. I can see how this can work, but it doesn't sound very efficient if there is no meaningful ordering in the categories. On another hand, hashing trick introduces similar kind of randomization and grouping, while working very well, so this may work as well.

  • $\begingroup$ Hmm, hashing the categorical variables implies randomisation and also dimensionality reduction (assuming the number of features in the hasher are chosen to be less than the number of unique levels in the categorical feature), which would result in hash collisions. If on the other hand one would be interested in preserving the 'granularity' / 'individuality' of the categorical feature (which excludes dimensionality reduction), would the stated approach by the authors still be reasonable? $\endgroup$ – robot_2077198 Jul 5 '19 at 15:18
  • $\begingroup$ I am also not quite sure if I correctly understand the method used by the authors. Assume we are given a data set with 6 observations and the categorical feature takes level ['A', 'B', 'D', 'C, 'A', 'A']. Do the authors do: (1) order the level to ['A', 'A', 'A', 'B', 'C', 'D'] and transform them to [0, 1, 2, 3, 4, 5] (2) or to they obtain unique ordered levels ['A', 'B', 'C', 'D'] and transform them to to [0, 1, 2, 3] ? $\endgroup$ – robot_2077198 Jul 5 '19 at 15:22
  • $\begingroup$ @robot_2077198 your aim is to clarify something, so why would it matter that some categories get combined? As about coding, you transform levels, at least this is how they described it. $\endgroup$ – Tim Jul 5 '19 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.