Outlier detection methods that support categorical data and provide explanations for flagged outliers
Outlier detection is a common task in machine learning, specifically a type of unsupervised machine learning that analyzes unlabeled data. It is the act of finding items in a dataset that are anomalous compared to other items in the dataset.
There are many reasons why you might want to identify outliers in your data. If the data you're investigating are accounting records and you want to find errors or fraud, there are usually too many transactions in the data to investigate each one manually, so you want to select a manageable small number of transactions to investigate. Finding and investigating the most unusual records is a good starting point. The idea is that both errors and fraud should be rare enough to stand out as outliers.
So while not all outliers are interesting, errors and fraud are likely to be outliers, making identifying them a very practical technique when looking for them.
Or the data might include credit card transactions, sensor readings, weather measurements, biological data, or website logs. In any case, it is useful to identify the records that indicate errors or other problems or that are the most interesting.
Outlier detection is often used as part of business or scientific discovery to gain a deeper understanding of the data and the processes it describes. For example, with scientific data, we are often interested in finding the most unusual records, because those are likely to be the most scientifically interesting.
The Need for Interpretability in Outlier Detection
In classification and regression problems, it is often preferable to use an interpretable model. This may result in lower accuracy (with tabular data, the highest accuracy is usually obtained with boosted models that are completely uninterpretable), but it is also safer, since you know what the model will do with unseen data. However, in classification and regression problems, it is often not necessary to understand why each individual prediction is made; as long as the model is reasonably accurate, it may be sufficient to just let it make predictions.
With outlier detection, however, the need for interpretability is much higher: if the outlier detector predicts that a record is highly anomalous, and it's not clear why, it may not be clear what to do with the item, or whether to even believe it is anomalous.
In fact, in many cases, performing outlier detection is of limited value without a good understanding of why an item flagged as an outlier was flagged. If you are checking a dataset of credit card transactions and your outlier detection routine identifies a series of purchases as highly anomalous and suspicious, you can effectively investigate these if you know what is anomalous. In some cases, this may be obvious, or may only become apparent after investigating over time, but it is much more effective and efficient if the nature of the anomaly is clear from the time it is discovered.
As with classification and regression, when interpretation is not possible we often try to understand the predictions using what are called post-hoc explanations, using XAI (Explainable AI) techniques such as feature importance, proxy models and ALE plots. These are also very useful and will be covered in future posts, but there is also a huge advantage to having clear results in the first place.
In this article, we focus specifically on tabular data, but later articles will cover other modalities as well. There are a number of algorithms currently in common use for outlier detection in tabular data, including Isolation Forests, Local Outlier Factor (LOF), KNN, One-Class SVM, etc. These algorithms often work very well, but unfortunately, they rarely provide an explanation for the outliers they detect.
Most outlier detection methods are easy to understand at the algorithmic level, but it can still be difficult to determine why some records were ranked highly by the detector and others were not. For example, when processing a financial transaction dataset with Isolation Forest, you can tell which records are the most anomalous, but you might not know why, especially if the table has many features, if an outlier contains a rare combination of multiple features, or if an outlier is a case where no features are highly anomalous but multiple features are moderately anomalous.
Frequent Pattern Outlier Factor (FPOF)
This is a brief introduction to outlier detection and interpretability. The remainder of this article is an excerpt from my book, Outlier Detection in Python (https://www.manning.com/books/outlier-detection-in-python), which discusses FPOF specifically.
FPOF (FP-outlier: frequent pattern based outlier detection) is one of the few detectors that can provide some interpretability for outlier detection and is worthy of further use in outlier detection.
They also have the attractive property that they are designed to work with categorical data rather than numerical data: Most real-world tabular data is mixed data containing both numerical and categorical columns; however, most detectors assume that all columns are numerical, and require all categorical columns to be numerically encoded (using one-hot, ordinal, or another encoding).
Detectors such as FPOF assume that your data is categorical, but have the inverse problem: you need to collapse all your numerical features into a categorical form. Either is doable, but if your data is primarily categorical, it's useful to be able to use a detector such as FPOF.
Also, when doing outlier detection, it has the advantage of being able to use both numeric and categorical detectors. Unfortunately, categorical detectors are relatively scarce, so FPOF can be useful in this regard even if interpretability is not required.
FPOF Algorithm
FPOF is Frequent Item Sets (FIS) are found in tables. These are either very common values within a single feature, or a set of values that appear together frequently across multiple columns.
Almost every table contains a significant collection of FISs. FISs based on a single value occur whenever some values in a column are significantly more common than other values, which is nearly always the case. Additionally, FISs based on multiple columns occur whenever there is association between the columns, that is, certain values (or ranges of numbers) tend to be associated with other values (or ranges of numbers) in other columns.
FPOF is based on the idea that as long as a dataset has many frequent itemsets (which is the case in almost all datasets), most rows will contain multiple frequent itemsets and normal (usual) records will contain significantly more frequent itemsets than outlier rows. This can be exploited to identify outliers as rows that contain much fewer, much less frequent FISs than most rows.
Example using real-world data
As a practical example of FPOF usage, let’s look at the SpeedDating set from OpenML (https://www.openml.org/search?type=data&sort=nr_of_likes&status=active&id=40536, CC BY 4.0 DEED license).
The execution of FPOF starts with mining the FIS from the dataset. There are many libraries in Python that support this. In this example, we use mlxtend (https://rasbt.github.io/mlxtend/), a general-purpose library for machine learning. This library provides several algorithms for identifying frequent itemsets. Here, A priori.
First, we collect the data from OpenML. Typically, we would use all categorical features as well as (binned) numerical features, but for simplicity, we only use a small number of features.
As mentioned before, FPOF requires binning of numeric features. Typically, you would use a small number of equal-width bins (perhaps 5-20) per numeric column. The pandas cut() method is useful for this. This example is a bit simpler, as it only deals with categorical columns.
from mlxtend.frequent_patterns import apriori
import pandas as pd
from sklearn.datasets import fetch_openml
import warningswarnings.filterwarnings(action='ignore', category=DeprecationWarning)
data = fetch_openml('SpeedDating', version=1, parser='auto')
data_df = pd.DataFrame(data.data, columns=data.feature_names)
data_df = data_df[['d_pref_o_attractive', 'd_pref_o_sincere',
'd_pref_o_intelligence', 'd_pref_o_funny',
'd_pref_o_ambitious', 'd_pref_o_shared_interests']]
data_df = pd.get_dummies(data_df)
for col_name in data_df.columns:
data_df[col_name] = data_df[col_name].map({0: False, 1: True})
frequent_itemsets = apriori(data_df, min_support=0.3, use_colnames=True)
data_df['FPOF_Score'] = 0
for fis_idx in frequent_itemsets.index:
fis = frequent_itemsets.loc[fis_idx, 'itemsets']
support = frequent_itemsets.loc[fis_idx, 'support']
col_list = (list(fis))
cond = True
for col_name in col_list:
cond = cond & (data_df[col_name])
data_df.loc[data_df[cond].index, 'FPOF_Score'] += support
min_score = data_df['FPOF_Score'].min()
max_score = data_df['FPOF_Score'].max()
data_df['FPOF_Score'] = [(max_score - x) / (max_score - min_score)
for x in data_df['FPOF_Score']]
The apriori algorithm requires that all features be one-hot encoded, for which we use pandas' get_dummies() method.
Next, we call the apriori method to determine the frequent itemsets. To do this, we need to specify the minimum support, that is, the minimum percentage of rows in which the FIS appears. If this value is too high, records (even strong inliers) will contain fewer FISs and will be difficult to distinguish from outliers. If this value is too low, the FIS will not be meaningful and outliers may have as many FISs as inliers. A low minimum support can cause a very large number of FISs generated by apriori, slowing down execution and reducing interpretability. In this example, we use 0.3.
It is possible, and sometimes even done, to place limits on the size of the FIS, relating it to a minimum and maximum number of columns, which may help narrow down the forms of outliers that are of most interest.
The frequent itemset is then returned in a pandas dataframe containing a column of support and a list of column values (in the form of a one-hot encoded column showing both the original column and the value).
To interpret the results, first look at the frequently_itemsets shown below. To include the length of each FIS, add:
frequent_itemsets['length'] = \
frequent_itemsets['itemsets'].apply(lambda x: len(x))
24 FISs were found, the longest covering three features. The following table shows the first 10 lines ordered by support:
We then loop through each frequent itemset and increment the score of each row that contains a frequent itemset by its support. This can optionally be adjusted to favor longer frequent itemsets (the idea is that an FIS that has support 0.4 and covers 5 columns is more relevant than an FIS that has support 0.4 and covers 2 columns, all else being equal), but for now we simply use the number of FISs and the support for each row.
This actually produces a normality score, not an outlier, so if you normalize the scores to be between 0.0 and 1.0, the order is reversed: the rows with the highest scores are the strongest outliers, that is, the rows with the fewest frequent itemsets and therefore the least common.
If you add a score column to your original dataframe and sort by score, the most healthy rows will be visible.
We can see that the values in this row match well with FIS. The value of d_pref_o_attractive is [21–100]This is FIS (support 0.36) and the values of d_pref_o_ambitious and d_pref_o_shared_interests are [0–15] and [0–15]This is also the FIS (support 0.59). The other values tend to be consistent with the FIS.
The most abnormal line is displayed next, which does not match any of the identified FIS.
This method has the advantage of producing reasonably interpretable results, since the frequent itemsets themselves are quite easy to understand, but this advantage is less true when using large numbers of frequent itemsets.
Outliers are identified by their absence of an FIS, not their presence or absence, making them less interpretable; that is, explaining the score of a row is equivalent to listing all the FIS that are not included. However, it is not strictly necessary to list all FIS that are missing to explain each outlier. Listing a small set of the most common FIS that are missing provides an adequate level of explanation for the outliers for most purposes. Statistics about the FIS present and the normal number and frequency of FIS present in a row provide an appropriate context for comparison.
One variation of this method uses rare itemsets rather than frequent itemsets and scores each row by the number and rarity of rare itemsets it contains. This method still produces useful results, but is significantly more computationally expensive because many more itemsets must be mined and each row is tested against many FISs. However, the final score is easier to interpret because it is based on the itemsets found, rather than missing, in each row.
Conclusion
Other than the code presented here, I am not aware of any implementations of FPOF in Python, but there are several in R. The majority of the work in FPOF is mining FIS, and there are a number of Python tools for this, including the mlxtend library used here. As shown above, the remaining code for FPOF is very simple.
Given the importance of interpretability in outlier detection, FPOF is very often worth trying.
In future articles, we will also discuss other interpretable methods for outlier detection.
All images are by the author
