{'fraction_non_alphanumeric': 0.0261367318284912, 'fraction_numerical': 0.009576268135507795, 'mean_word_length': 4.830814441645676, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
RECol: Reconstruction Error Columns for Outlier Detection

Detecting outliers or anomalies is a common data analysis task. As a sub-field of unsupervised machine learning, a large variety of approaches exist, but the vast majority treats the input features as independent and often fails to recognize even simple (linear) relationships in the input feature space. Hence, we introduce RECol, a generic data pre-processing approach to generate additional columns in a leave-one-out-fashion: For each column, we try to predict its values based on the other columns, generating reconstruction error columns. We run experiments across a large variety of common baseline approaches and benchmark datasets with and without our RECol pre-processing method and show that the generated reconstruction error feature space generally seems to support common outlier detection methods and often considerably improves their ROC-AUC and PR-AUC values.


Introduction
Detecting outliers in data is an often occurring exercise in various domains. For example, the identification of certain diseases of patients or fraudulent behavior of individuals can often be supported by applying outlier detection algorithms to data. Many different algorithms can be found in the literature to identify these outliers in unsupervised settings where no label is available.
However, the existing approaches apply a certain definition of an outlier that might not be appropriate for detecting outliers in all relevant contexts. Using standard algorithms, outliers are typically defined as data points which are far apart from other data points in a global or local sense. However, one might actually be interested in data points that deviate from underlying relations in the data. While such deviations might coincide with points far apart from others, this must not be always the case.
We illustrate this issue in Figure 1 with a toy example in two dimensions. The points in the scatter plot constitute some data. Applying a common outlier detection algorithm to this data flags the red and green points as outliers. However, notice that in our example there is a simple linear relationship between the two attributes. Hence, we argue that an outlier could also be defined by points deviating markedly from the underlying (often latent) relationship in the data. In our example these are the points outside the 2σ interval of the linear relationship. As one can see, traditional approaches often flag points inside such a bandwidth as outliers and miss points outside of it.
To tackle this problem, we present an approach to map the data to a reconstruction error space and apply the outlier detection algorithm to a combination of the previous and this novel space. We do so by estimating a supervised model for each input feature using all other features as inputs. Consequently, for each input feature column in the original dataset, one receives an additional (derived) feature column containing the reconstruction errors. We can then use these new features as (additional) inputs for existing outlier detection algorithms. This enables the algorithms to easily identify data points that can hardly be reconstructed by the relationships in the data. In Figure 1 these would be the green and orange points, because their distance to the bandwidth is larger and therefore their reconstruction error is higher. In reconstruction error space they lie far apart from the other data points, making them suspicious to the outlier detection algorithm.
Therefore, we claim that by calculating additional reconstruction error columns (RECols) for each feature in the dataset, one can improve the detection of outliers in unsupervised contexts. Despite the simple example, one should note that our approach also can also be beneficial in case of more complex and non-linear relationships within the data: For the generation of RECols we can use any kind of supervised machine learning approach.
The remainder of this paper is structured as follows. After presenting related work in Section 2, we will provide an indepth description of our approach in Section 3 and evaluate our approach in Section 4 by comparing it to a variety of common approaches and benchmark datasets as described in Section 4.1. Section 4.2 then contains our findings and a discussion, before concluding this paper in Section 5.

Related Work
In the field of anomaly or outlier detection, many interesting approaches exist that try to detect irregularities of different kinds. Good overviews over the field can be found in (Gogoi et al., 2011;Goldstein & Uchida, 2016) and more recent in (Chalapathy & Chawla, 2019). In this paper we do not present another outlier detection algorithm. Instead, we present a general pre-processing idea and argue that our idea is beneficial across use-cases and existing approaches. Hence, we base our work on Goldstein et al (Goldstein & Uchida, 2016). They conduct a comprehensive study of unsupervised anomaly detection algorithms for multivariate data, in which they analyse 19 different unsupervised anomaly detection algorithms (cluster, distance, density, and statistics based) using 10 different standard datasets, resulting in a detailed analysis of the advantages and disadvantages of each algorithm. In this paper, we hence treat their models and results as baseline results and compare our approach with these baselines to analyze the advantages generated by our pre-processing approach for unsupervised anomaly detection in general.
Our approach is related to other techniques such as principle component analysis (PCA) or auto-encoders (AEs). PCA and AEs are often used as dimensionality reduction techniques. Errors generated by a reduced set of principle components of a PCA during the reconstruction of the original data have been used for outlier detection (Jablonski et al., 2015;Chen et al., 2009). Analogously, there are many approaches for outlier detection based on the reconstruction errors of AEs (Sakurada & Yairi, 2014;Zhou & Paffenroth, 2017;Xia et al., 2015;Gong et al., 2019;Amarbayasgalan et al., 2019). In contrast to PCA and AEs, our idea is not motivated by a dimensionality reduction or compression, but we instead (in general) increase the number of dimensions. Additionally, our approach results in one reconstruction error component per column for each sample and not just one (often difficult to decompose or to correctly attribute to its source) reconstruction error for the whole sample. Finally, our approach is not intended as a direct outlier detection algorithm, but as an enrichment of the input-space. In other words, our approach is intended as a pre-processing step for an arbitrary outlier detection algorithm that might follow.

Approach
The standard approach for detecting outliers in unsupervised settings follows this outline: (1) pre-processing, (2) outlier detection algorithm and (3) result evaluation. We extend this approach by expanding step (1): For each column in the dataset we use a supervised machine learning approach to predict this column based on all other features in the dataset (so excluding the one to be predicted, hence also denoted as a leave-one-out approach). After training of the supervised model for a specific column we calculate the reconstruction (or prediction) error for each data point (e.g., the mean squared error or some other metric of the prediction error) in the train and test set. Repeating this process, we arrive at a corresponding reconstruction error feature column (RECol) for each of the original columns, effectively doubling the number of features. After this adjusted first step, we can continue with (2), the outlier detection algorithm. However, one might consider to also pre-process the RECols first, e.g. scaling them appropriately.
Figure 2 illustrates our extended approach for outlier detection. In Figure 2 (A) we plot a dataset with two features, where outliers are marked in green and inliers in blue. In this dataset an outlier is a point that markedly deviates from the underlying relationship between the two features. By directly applying an outlier detection algorithm to the data one usually receives predictions as highlighted by the red and green points in Figure 2 (B), missing the orange outliers and delivering a dissatisfying performance. This is caused by the outlier detection algorithms focusing on labeling data points that are far away from others in the data space. By applying our approach where we create RECols and apply the outlier detection algorithm to these features, we are able to classify points as outliers that deviate from the underlying relationship, as can be seen in Figure  the true outliers are easier to separate in these new spaces introduced by our approach. Given these new representations, the following the outlier detection model is better able to classify outliers correctly, as can be seen in Figure 2 (D).

Possible Design Decisions
Aside from whether our approach leads to improvements in detecting outliers in data, our approach opens up a few questions regarding the specification of the input space for the outlier detection algorithm: (a) Should one use only the RECols for estimation or the combined feature space with the original features and additional RECols? If one is only concerned about outliers that are hard to reconstruct from the underlying relationship in the data one can in principle estimate the outlier detection model abolishing the initial data features. However, they might still contain valuable information for estimation. Therefore, in our evaluation we compare the results of the outlier detection algorithm on the initial data features only, the RECols only and the combined (concatenated) feature space.
(b) Can the RECols be used as an outlier detection algorithm directly by fusing the reconstruction errors appropriately? In principle, one could directly use the RECols and aggregate them to calculate an outlier score for each data point. To test whether this works we normalize the RECols and aggregate them to an outlier score by taking the average reconstruction error across columns. In the next section we compare our results from this exercise with standard outlier detection algorithms.
(c) How should the supervised algorithm to calculate RECols be specified? Ideally, we want to estimate the true hypothesis in the data. In practice, however, there is noise in the data and dataset is incomplete in the sense that relevant features are missing in the data. Therefore, we want to estimate a good approximation to the true underlying relationship. In our experiments we use a wide range of algorithms to check whether the choice of the supervised model affects the results.
(d) Finally, how should RECols be calculated and preprocessed and should all newly created columns be used for estimating the outlier detection algorithm? That is, which reconstruction error metric should be applied, e.g. mean squared error, mean absolute deviation, or some other prediction error metric? In terms of pre-processing one can think about scaling the attributes, dropping uninformative RECols or clipping RECol values.
To evaluate whether our RECol approach is beneficial and to answer these additional questions, we have run several experiments, as described in the following.

Experimental Setup
In this section we evaluate whether using RECols leads to improvements when looking for outliers in data. We measure the performance of an algorithm by either the area under the receiver operating characteristic (ROC-AUC) or the area under the precision recall curve (PR-AUC), which are standard metrics in the outlier detection domain. Before estimating RECols or applying an outlier detection model we split the dataset to a train set containing 70% of the data and a test set with the remaining 30% of data. Then we estimate the RECols and outlier detection model on the train set and evaluate them on the test set to avoid data dredging. We calculate RECols in the test data using the trained model and evaluate the outlier detection model with these data. Finally we perform three types of experiments: (a) Estimating baseline results using only normal data features, (b) using only RECols for estimation and (c) using both types of columns combined (concatenated) for estimating the outlier detection model.

BASELINES
We compare our results to those of (Goldstein & Uchida, 2016) using the same set of datasets and the most common outlier detection algorithms as in their paper. Similar to (Goldstein & Uchida, 2016) we optimize hyper-parameters using a grid search to reproduce their results. In the end we find very similar results and pick the best outlier detection model for each algorithm and each dataset to compare to our RECol approach. We apply the following algorithms: HBOS (Goldstein & Dengel, 2012), ISO (Liu et al., 2008), KNN (Ramaswamy et al., 2000), KthNN (Ramaswamy et al., 2000), LDCOF (Amer & Goldstein, 2012), LOF (Breunig et al., 2000), LOoP (Kriegel et al., 2009), Nu-OCSVM (Amer et al., 2013), OCSVM (Schölkopf et al., 2001), CBLOF (He et al., 2003), uCBLOF (He et al., 2003). These are typical outlier detection algorithms from the literature. We refer the reader to (Goldstein & Uchida, 2016) for a more detailed discussion of the different algorithms.
In addition to the aforementioned baseline results, we initially also experimented with several auto-encoder based approaches for outlier detection, such as (Sakurada & Yairi, 2014;Zhou & Paffenroth, 2017;Xia et al., 2015;Gong et al., 2019;Amarbayasgalan et al., 2019). However, despite experimenting with different architectures, varying the number of hidden layers and the size of the smallest compression layer we found that our auto-encoder based attempts were only ever among the best models (with negligible improvement) on the kdd99 dataset. We reason that this is likely due to the large amount of training data necessary for such approaches. Due to this and the large number of additional design decisions, we decided to leave an in-depth analysis of a combination of auto-encoders with our RECol approach on multiple larger datasets for future work.

DATASETS
As in (Goldstein & Uchida, 2016) we apply all of our experiments to the following ten datasets: aloi, annthyroid, breast-cancer, kdd99, letter, pen-global, pen-local, satellite, shuttle and speech (Bache & Lichman, 2013;Micenková et al., 2014;Geusebroek et al., 2005;Goldstein & Uchida, 2016). The datasets are very distinct, in particular in their number of observations, their dimensionality and their fraction of outliers in the dataset. This allows us to analyse the effect of RECols on a wide range of different types of datasets. A more detailed description of the datasets itself can be found in (Goldstein & Uchida, 2016).

PARAMETERS
To give an answer to question (a) whether one should use RECols for outlier detection we decided to run many different experiments. By applying different experiments we can also learn about question (c) how one should specify the supervised algorithm for our leave-one-out approach. Finally, to answer (d) we need to try out different approaches to generate and process RECols, like the distance metric and whether all RECol columns should be used for training the outlier detection model. In total, we evaluated 895 different ways of creating RECols for each fixed best parameter baseline OD model and dataset. We evaluated them against the corresponding fixed best parameter baseline OD model for all datasets, expect kdd99. For kdd99 we ran only eight experiments due to the size of the dataset and the time each experiment consumes. 1 We will discuss our results in the following subsection.

Results & Discussion
To evaluate whether RECols help to better detect outliers in data we make the following comparison and start with the ROC-AUC metric for evaluation. We define the best baseline model as the maximum ROC-AUC value across all standard outlier detection algorithms where we also optimized hyper-parameters using a grid search as in (Goldstein & Uchida, 2016). The best model is picked as the best ROC-AUC model in the train dataset while we then compare their performance in the test dataset. In Table 1 these values are shown in the second column. Similarly, we take the best RECol model by picking the best train model in terms of the ROC-AUC value across our experiments. However, we do not optimize hyper-parameters of the outlier detection model for RECol approach but take the same hyper-parameter specification as for the baseline. 2 The third column of Table 1 shows our results in the test sample. In total, we improve in 5 out of 10 datasets. In light of the fact that for half of the datasets the baseline is very close to 100 % (due to the low contamination in the dataset), this is a relatively strong result. We have also compared the best baseline against our RECol approach for each dataset and outlier detection algorithm separately. The average improvement in this setup is around 6 percentage points in terms of ROC-AUC and RECols improve the results in over 2/3 of cases. In over 1/3 of cases the improvement is even above 5 percentage points in the ROC-AUC metric. When we only look at baselines with a baseline metric below 95% ROC-AUC we see in almost 60% of settings an improvement of over 5 percentage points in the ROC-AUC metric by just adding RECols as additional input to the outlier detection model. A visualization of the different parameter choices for each dataset and 2 These choices can only harm us in that we restrict ourselves to less options compared to the baseline results. RECol based on each of the baseline OD algorithms can be found in Figure 3. In principle, one could further improve the results by optimizing hyper-parameters of each of the underlying OD models, after choosing the one of the 895 ways to generate RECols. However, due to combinatorial explosion of experiments, we decided to instead treat the OD models' parameters as fixed (to our disadvantage).
The ROC-AUC metric, however, has its weaknesses because when the outlier contamination in the data is low, the ROC-AUC value is high by construction. In particular, many datasets in our sample have a very low contamination which leads to very high ROC-AUC values independent from the quality of the outlier detection model. The comparison across algorithms and our RECol approach is still valid, but possible improvements can be very small by construction.
Therefore we perform the exact same experiments using the area under the precision recall curve (PR-AUC) to test whether using RECols improves the results compared to standard outlier detection algorithms. The PR-AUC is more stable when the dataset is very imbalanced. The results are shown in Table 2. The RECol approach leads to stunning improvements in five out of ten datasets while there is no improvement in the other five datasets. The average improvement in this setup is around 8.6 percentage points in terms of PR-AUC and RECols improve the results in over 75 percent of cases. In over 55 percent of cases the improvement is even above 5 percentage points in the PR-AUC metric. Hence, there are considerable improvements in the PR-AUC metric when RECols are added to the outlier detection algorithm. Notes: Performance of OD-model is measured in ROC-AUC metric. RECols Only is the best OD-Algorithm using exclusively RECol features. RECols is the best algorithm using combination of RECols and standard features in addition.

Possible Design Decisions
We will now attempt to answer the questions raised in Section 3.1.
(a) Should one replace standard columns with RECols or use both columns for training? In Table 3 we compare the results of outlier detection algorithms using RECols only and a combination of RECols and standard features on different datasets. In 4 out of 10 datasets RECols only approach outperforms the combination of RECols and standard features. The results using RECols only are still promising, but overall the combination of standard attributes and RECols delivers better results. We reason that this is the case because standard attributes might still contain valuable information for outlier detection. The larger dimensionality of the space with RECols has not led to problems in our experiments.
(b) Can RECols directly be used as an outlier detection algorithm? To test this we have applied the following approach: We normalize the RECols using a min-max scaler and take the average across all columns to receive an outlier score for each observation. When we take this outlier score and evaluate them using the ROC-AUC metric we can compare this to other outlier detection algorithms. The results for the ROC-AUC metric are summarized in Table 4. We find that for 2 out of 10 datasets such a simple fusion of the RECols from our approach, called RECol-OD in the following, outperforms all other baselines. When we compare RECol-OD to the average performance of other algorithms we see that in 9 out of 10 datasets the RECol-OD algorithm performs better. Overall, RECol-OD outperforms many standard algorithms by a significant amount. This is somewhat surprising in light of the simple fusion method we applied. As before, we do the same comparison using the PR-AUC metric for evaluation as can be seen in table Table 5. In 4 out of 10 datasets the RECol-OD algorithm is the most successful algorithm. In 7 out of 10 datasets the performance is considerably higher than the average algorithm.
(c) How should the supervised algorithm to calculate RECols be specified? One has many degrees of freedom to specify the RECol model, in particular the choice of algorithm could be important. Hence, we have tried various algorithms and found that random forests or gradient boosting are relatively robust and good benchmarks. Depending on the dataset at hand other RECol algorithms might be more beneficial though. We have also reasoned about whether the performance of the RECol model impacts the performance of the outlier detection, in particular one could think of an inverse u-shape here. This is because a RECol model with an accuracy of 100% delivers a RECol column full of zeros while a RECol model with an accuracy of 0% delivers the square of the feature to be predicted (in case of a mean squared error RECol). In both cases adding RECols should not improve outlier detection. Hence a model that is good but not perfect might be ideal. We have checked and indeed one finds a slight inverse u-shape relation between the RECol accuracy and the outlier detection ROC-AUC/PR-AUC but the relation is very modest. In general, it seems important that the RECols are properly specified and a good approximation to the underlying hypothesis while avoiding over-fitting.
(d) How should RECols be calculated and pre-processed? In addition to the choice of RECol algorithm one has many options to calculate and pre-process the created RECols. In terms of calculating we have tried mean squared errors and mean absolute deviations. We advise to try out both metrics because depending on the dataset and algorithm there were performance differences between the two methods. In principle one could think of other metrics too, like exponential distances. After having calculated the RECols it is important to scale them, for example by using a min-max scaler.
Clipping RECol values or dropping RECols with high or low R-squared values have no big effects on outcomes, but might be relevant depending on the dataset at hand.
Apart from an evaluation on the aforementioned public datasets, we also successfully applied our approach to financial data using German Bundesbank internal datasets such as the Investment Funds Statistics (IFS) (Blaschke & Haupenthal, 2020).

Parameter Recommendations
Based on the 88,693 experiments we ran to evaluate how to generate RECols across 10 standard datasets and 11 standard OD approaches for this study, we would now like to share some of our observations for practical use-cases, in which one might not want to run an equally comprehensive study.  Figure 3. Boxplot results by algorithm and data set. Each sub-figure shows the results for one dataset. The distributions of ROC-AUC are shown for our RECol approach based on each of the underlying OD algorithms. The red vertical line shows the best (maximum) baseline result (without RECol). By this we give the baselines the advantage of already picking the best parameters, while showing ROC-AUC values across 895 such parameters for the RECol approaches. Notes: The performance of the OD-models is measured in the ROC-AUC metric. The best baseline is the best OD-Algorithm using standard features only. Average baseline is the average ROC-AUC value across all standard OD-models. RECol-OD here is the direct fusion of the RECols from our approach into an outlier score. Notes: The performance of the OD-models is measured in the PR-AUC metric. The best baseline is the best OD-Algorithm using standard features only (picked on training split, which allows for the best value in test to be lower than the average, as can be seen in the speech dataset). Average baseline is the average PR-AUC value across all standard OD-models. RECol-OD here is the direct fusion of the RECols from our approach into an outlier score.
In general, we would recommend to start with a simple random forest regressor as supervised algorithm to create the RECols based on the MSE metric. This is due to our observation that this combination seems to be quite robust, often among the top performers and additionally has the advantage of only few parameters to tune. Wrt. scaling of input features and clipping the RECols the results are less conclusive, so we would recommend to experiment depending on the use case. Wrt. dropping RECols depending on R 2 , we in did not observe a clear pattern, but the differences were negligible in most cases. In case of many dimensions, we would hence suggest to drop the most uninformative RECols based on R 2 to reduce the load of downstream components.

Conclusion and Future Work
In this paper we introduced our RECol pre-processing approach. We showed how to calculate RECols and added them to the outlier detection algorithm as additional features. We find that adding RECols can often significantly improve model performance of unsupervised outlier detection models in terms of the ROC-AUC and PR-AUC metric and using them does rarely harm model performance. Based on more than 88k experiments, we also provide parameter recommendations to quickly try our approach in practical use-cases. Further, simply fusing RECols to an outlier score (RECol-OD) delivers a surprisingly simple algorithm that outperforms standard algorithms in many cases.
Our results also open up many further avenues for future research. So far we have not optimized hyper-parameters of the OD algorithms when using RECols. This could fur-ther improve our results. In addition one can experiment further in how to add RECols. Maybe aggregating RECols to fewer columns based on dimensionality reduction techniques might be helpful to condense the information in the RECols in fewer columns that need to be added for training. This is especially interesting as doubling the space of columns might be problematic in high-dimensional data. Next, we have only applied a very simple fusion approach for the RECol-OD algorithm. One can think of alternative and more complex approaches to fuse RECols that might improve the performance of the RECol-OD algorithm. Finally, applying our approach to additional datasets, combining it with auto-encoders and also in real world applications might help to strengthen our findings further.