Encoding of categorical variables with high cardinality

Question

For unsupervised anomaly detection / fraud analytics on credit card data (where I don't have labeled fraudulent cases), there are a lot of variables to consider. The data is of mixed type with continuous/numerical variables (e.g. USD amount spent) as well as categorical variables (e.g. account number).

What is the most suitable way of including categorical variables that have a very large number of unique classes? My thoughts so far:

• Label Encoding (scikit-learn): i.e. mapping integers to classes. While it returns a nice single encoded feature column, it imposes a false sense of ordinal relationship (e.g. 135 > 72).
• One Hot / Dummy Encoding (scikit-learn): i.e. expanding the categorical feature into lots of dummy columns taking values in {0,1}. This is infeasible for categorical features having e.g. >10,000 unique values. I understand that models will struggle with the sparse and large data.

What other (more advanced?) suitable methods are there to include large categorical feature columns? Is it possible to still use One Hot Encoding with some tricks? I read about bin counting (Microsoft blog) though I haven't found any applications related to intrusion detection / fraud analytics.

P.S.: In my view, this problem seems very similar to encoding an IP-address feature column when dealing with unsupervised intrusion detection.

Answer 1

This link provides a very good summary and should be helpful. As you allude to, label-encoding should not be used for nominal variables at it introduces an artificial ordinality. Hashing is a potential alternative that is particularity suitable for features that have high cardinality.

You can also use a distributed representation, which has become very popular in the deep learning community. The most common example given for distributed representation is word embeddings in NLP. That is not to say you cannot utilise them in encoding other categorical features. Here is an example.

Finally, account number would not be a wise input as it is more a unique identifier rather than a generalisable (account) feature.

Answer 2

This might help Quantile Encoder: Tackling High Cardinality Categorical Features in Regression Problems: https://link.springer.com/chapter/10.1007%2F978-3-030-85529-1_14

The most well-known encoding for categorical features with low cardinality is One Hot Encoding [1]. This produces orthogonal and equidistant vectors for each category. However, when dealing with high cardinality categorical features, one hot encoding suffers from several shortcomings [20]: (a) the dimension of the input space increases with the cardinality of the encoded variable, (b) the created features are sparse - in many cases, most of the encoded vectors hardly appear in the data -, and (c) One Hot Encoding does not handle new and unseen categories.

An alternative encoding technique is Label/Ordinal Encoding [3] which uses a single column of integers to represent the different categorical values. These are assumed to have no true order and integers are selected at random. This encoding handles the problem of the high dimensional encoding found in One Hot Encoding but imposes an artificial order of the categories. This makes it harder for the model to extract meaningful information. For example, when using a linear model, this effect prevents the algorithm from assigning a high coefficient to this feature.

Alternatively, Target Encoding (or mean encoding) [15] works as an effective solution to overcome the issue of high cardinality. In target encoding, categorical features are replaced with the mean target value of each respective category. With this technique, the high cardinality problem is handled and categories are ordered allowing for easy extraction of the information and model simplification. The main drawback of Target Encoding appears when categories with few (even only one) samples are replaced by values close to the desired target. This biases the model to over-trust the target encoded feature and makes it prone to overfitting.

It is not your exact case but the introduction has a bit of lit review that can be helpful and the pitfalls of some of this techniques.

Also, in arxiv https://arxiv.org/abs/2105.13783

Answer 3

Zhubarb had a very nice answer. I just want to provide more details on embedding and hashing and add one common approach binning.

Starting with the binning, this is a very common approach used in many fields, the key idea is many data follows 80-20 rules, that even we have a feature with many values but most of the data will concentred in few values. One simple example is nationality. There are many nations in the world, but if we want to build a statistical model using nationality, we will not use / encoding all of them (there are many reasons behind this, but generally, we may have overfitting if we use all of them). Instead we will pick top nationalities, and bin others int Others category. Note that this approach is also widely used in Deep Learning, where a word will have OOV(out of vocabulary) label when it is in Other category. This is an interesting paper to read: How Large a Vocabulary Does Text Classification Need?, In this paper, the largest vocabulary size is 60K.

Embedding is a very nice idea from Deep Learning and NLP. Suppose we are building a model that vocabulary size is 60K, we do not want to do one hot embedding because the vector is very sparse and the distance between vectors are not meaningful. For example, if we encode the word cat into [0,0,....,1,0,0], a lot of space will be wasted (in real word if we use sparse vector instead of dense vector to store the data, it will still be OK, but sparse vector have its own computational challenges.). And the distance between the word "cat" and say "dog", will as same as the distance between cat and say "keyboard".

Embedding uses dense vector to do the encoding, and the general idea is the distance between the dense vectors will have meanings. For example, the distance between "cat" and "dog", will be much smaller than the distance between "cat" and "keyboard".

Hashing is another interesting idea, an example can be found in sklearn documentation here. The idea is we use hash functions to produce a fixed number of features. This approach will apply a hash function to the features to determine their column index in data / design matrices directly. The result is increased speed and reduced memory usage, at the expense of inspectability; the hasher does not remember what the input features looked like and has no inverse_transform method. In addition, there will be collisions if we set number of the output features small. (for example, the this trick make not be able to differentiate the word "cat" and "keyboard" as both of them mapped into same column index.)

Answer 4

This Medium article I wrote might help as well: 4 ways to encode categorical features with high cardinality. It explores four encoding methods applied to a dataset with 26 categorical features with cardinalities up to 40k (includes code):

Target encoding

• PROS: parameter free; no increase in feature space
• CONS: risk of target leakage (target leakage means using some information from target to predict the target itself); when categories have few samples, the target encoder would replace them by values very close to the target which makes the model prone to overfitting the training set; does not accept new values in testing set

Count encoding

• PROS: easy to understand and implement; parameter free; no increase in feature space
• CONS: risk of information loss when collision happens; can be too simplistic (the only information we keep from the categorical features is their frequency); does not accept new values in testing set

Feature hashing

• PROS: limited increase of feature space (as compared to one hot encoding); does not grow in size and accepts new values during inference as it does not maintain a dictionary of observed categories; captures interactions between features when feature hashing is applied on all categorical features combined to create a single hash
• CONS: need to tune the parameter of hashing space dimension; risk of collision when the dimension of hashing space is not big enough

Embedding

• PROS: limited increase of feature space (as compared to one hot encoding); accepts new values during inference; captures interactions between features and learns the similarities between categories
• CONS: need to tune the parameter of embedding size; the embeddings and a logistic regression model cannot be trained synergically in one phase, since logistic regression do not train with backpropagation. Rather, embeddings has to be trained in an initial phase, and then used as static inputs to the decision forest model.