Contextual Outlier Interpretation

1 Introduction

Outlier detection, which is to identify isolated instances that are different from the majority, has become an effective computational tool in real-world applications such as detecting spams [Liu et al., 2017b; Shah, 2017], disease outbreaks [Wong et al., 2002], and mis-behavioral IP sources in networks [Tong and Lin, 2011]. Numerious algorithms have been proposed for outlier detection, including density-based [Breunig et al., 2000; Aggarwal and Yu, 2001; Gao et al., 2010], distance-based [Knorr and Ng, 1999; Liu et al., 2012] and model-based methods [He et al., 2003; Tong and Lin, 2011; Li et al., 2017]. Some other work tackles the curse of dimensionality [Filzmoser et al., 2008], the massive data volumn [Ramaswamy et al., 2000; Lucic et al., 2016] and data heterogeneity [Chen et al., 2016]. However, the essential factors that result in the outliers being detected are usually ignored and cannot be revealed with the detection outcome to end users.

Complementing existing work, enabling interpretability could benefit outlier detection and analysis in several aspects. First, interpretation helps bridge the gap between detecting outliers and identifying domain-specific anomalies. Outlier detection can output data instances with rare and noteworthy patterns, but in many applications we still rely on domain experts to manually select domain-specific anomalies from outliers that they actually care about in the current application. For example, in e-commerce website monitoring, outlier detection can discover users or merchants with rare behaviors, but administrators need to check the results to select those involved in malicious activities such as fraud. Interpretation of the detected outliers, which provides reasons for outlierness, can significantly save the effort of such manual inspection. Second, interpretation can be used in the evaluation process to complement current metrics such as the area under ROC curve (AUC) and nDCG [Davis and Goadrich, 2006] which provide limited information about characteristics of the detected outliers. Third, a detection method that works well in one dataset or application is not guaranteed to have good performance in others. Unlike supervised learning methods, outlier detection is usually performed using unsupervised methods and cannot be evaluated in the same way. Thus, effective outlier interpretation would significantly facilitate the usability of outlier detection techniques in real-world applications.

One straightforward way for outlier interpretation is to apply feature selection to identify a subset of features that distinguish outliers from normal instances [Knorr and Ng, 1999; Micenkov´a et al., 2013; Duan et al., 2014; Vinh et al., 2016; Gao et al., 2017]. However, first it is difficult for some existing methods to efficiently handle datasets of large size or high dimensions, or effectively obtain interpretations from complex data types and distributions. Second, we measure the outlierness score of outliers through interpretation, which is important in many applications where some actions may be taken to outliers with higher priority. Some detectors only output binary labels indicating whether each data instance is an outlier. Sometimes continuous outlier scores are provided, but they are usually in different scales for different detection methods. A unified scoring mechanism by interpretation could facilitate the comparisons among various detectors. Third, besides identifying the notable attributes of outliers, we also analyze the context (e.g., contrastive neighborhood) in which outliers are detected. "It takes two to tango." Discovering the relations between an outlier and its context would provide richer information before taking actions to deal with the detected outliers in real applications.

To tackle the aforementioned challenges, in this paper, we propose a novel Contextual Outlier INterpretation (COIN) framework to provide explanations for outliers. We define the interpretation of an outlier from three aspects: abnormal attributes, the score of outlierness and the contrastive context with respect to the outlier. The first two elements are extracted from the relations between the outlier and its context. COIN can also be applied to existing outlier detection methods which already provide explanations for their results. In addition, prior knowledge about the roles of attributes in specific application scenarios can be easily incorporated with interpretation results, in order to enable end users to filter the given outliers and select the ones that are practically meaningful for the application. The contributions of this paper are summarized as follows:

• We define the interpretation of an outlier as three aspects: abnormal attributes, outlierness score, and the identification of the outlier's local context.
• We propose a novel model-agnostic framework to interpret outliers, as well as designing a concrete model within the framework to extract interpretation information.
• Comprehensive evaluations on interpretation quality, as well as case studies, are conducted through experiments on both real-world and synthetic datasets.

2 Preliminaries

Interpretation is receiving increasing attention in many machine learning applications. Some recent work gives explanation of the prediction results of classifiers [Ribeiro et al., 2016; Koh and Liang, 2017]. Also, some outlier detection methods provide explanation together with detection results [Perozzi et al., 2014; Liu et al., 2017a; Liang and Parthasarathy, 2016], but they cannot be simply adopted by all detection methods.

Problem Definition Here we formally define the outlier interpretation problem as follows. Given a dataset X = {xi ∈ RM |i ∈ [1, N]} and the query outliers O detected therefrom, the interpretation for each outlier oi ∈ O is defined as a composite set: Ei = {Ai, d(oi), Ci = {Ci,l|l ∈ [1,L]}}. Here Ci denotes the context (i.e., k-nearest normal instances) of the outlier, Ci,1, Ci,2, ..., Ci,L are clusters in Ci, and L is the number of clusters. Ai represents the abnormal attributes of oi in contrast to Ci. We use "inliers" and "normal instances" interchangeably in this paper. d(oi) ∈ R≥0 is the outlierness score of oi. The reason for clustering the context is illustrated in Figure 1. There are three clusters, each of which represents images of a digit. Red points are the detected outliers. Clusters of digit "2" and "5" compose the context of outlier o1. The interpretation of o1 can be obtained by comparing it with the two clusters respectively. However, it would be difficult to explain the outlierness of o1 if clusters of digit "2" and "5" are not differentiated.

3 Contextual Outlier Interpretation Framework

The general framework of Contextual Outlier INterpretation (COIN) is illustrated in Figure 2. Given a dataset X and a set of outliers O, we map the interpretation task to a classification problem. Then, the classification problem over the whole data is partitioned to a series of regional problems around each outlier query. Finally, interpretation is obtained from regional classification models.

3.1 Explaining Outlier Detector Using Classifiers

In this subsection, we establish the correlation between outlier detection and traditional supervised classification problems. Formally, an outlier detector can be denoted as h(x|θ,X), where θ denotes the parameters. Here X is also treated as parameters since data instances affect the outlierness of each other. The abnormality of input x is typically represented by either a binary or continuous score, while the latter case can be easily transformed to the former if a threshold is set to separate inliers and outliers. This motivates us to explain outlier detectors using classification models. Although outlier detection is usually tackled as an unsupervised learning problem, there exists an imaginary hyperplane specified by certain decision function f(x|θ′ ) : RM → {0, 1} that separates outliers from normal instances. Here θ′ represents the parameters of f. An example can be found in Step 1 of Figure 2. Blue points and red points are normal instances and outliers, respectively, while dotted curves indicate the decision boundaries. The problem of building the decision function f is formulated as below,

where L is the loss function including classification error and regularization terms. O and X-O represent outlier class and inlier class, respectively.

By utilizing the isolation property of outliers, we can further decompose the problem in Equation (1) into multiple regional tasks of explaining individual outliers:

In this way, the original problem is transformed to explaining each outlier oi with respect to its context counterpart Ci. Note that it is computationally efficient, given that the number of outliers is usually small. Here gi represents the local parts of f exclusively for classifying oi and Ci. In Figure 2, for example, gi is highlighted by the bold boundaries around o1 in Step 1, and Ci consists of the normal instances enclosed in the yellow circle in Step 2. Since there is a data imbalance between the two classes, we adopt synthetic sampling [He and Garcia, 2009] to expand oi to an outlier class Oi with comparable size to Ci. Local interpretation, encoded in gi, can be obtained by approximating the local behavior of h between Oi and Ci.

3.2 Resolving Context for Outlier Explanations

Now we focus on interpreting each single outlier oi by solving gi, from which we can extract interpretation results. Let pOi (x) and pCi (x) denote the probability density functions of the outlier class and inlier context class, respectively. Since the context Ci may contain complex cluster structures as shown in Figure 1, it is difficult to directly measure the degree of separation between Oi and Ci or to discover the attributes that discriminate the two classes. Therefore, we further decompose L(h, gi;Oi, Ci) to a set of simpler problems. According to Bayesian decision theory, the error of classifying between Oi and Ci is

Suppose we can split the context Ci into multiple clusters {Ci,l|l ∈ [1, L]} that are well separated from each other, then each term in the summation can be treated as an independent sub-problem without mutual inference. Oi,l is a subset of Oi close to Ci,l. By combining Equation (2) and Equation (3), our final interpretation task is formulated as:

By now we are able to classify Oi,l and Ci,l with a simple and explainable model gi,l such as linear models and decision trees, where the abnormal attributes Ai,l can be extracted from model parameters. The overall interpretation for oi is obtained by integrating the results across all Ci,l, l ∈ [1, L].

The estimated time complexity for implementing the framework above is O(|O| × L × Tg), where Tg is the average time cost of constructing gi,l. Due to the scarcity of outliers, |O| is expected to be small. Each gi,l involves Oi,l and Ci,l. Tg is also expected to be small since Ci,l and Oi,l are of small sizes. Moreover, the interpretation processes of different outliers are independent of each other, thus can be implemented in parallel to further reduce the time cost.

4 Distilling Interpretation fromModels

After introducing the general framework of mapping outlier interpretation into a collection of classification tasks around individual outliers, in this section, we propose a concrete model to explain each outlier, including discovering its abnormal attributes and measuring the outlierness score.

4.1 Context Identification and Clustering

Given an outlier oi spotted by the detector h, first we need to identify its context Ci in the data space. As introduced in Section 2, Ci consists of the nearest neighbors of oi. Here we use Euclidean distance as the point-to-point distance measure. The neighbors are chosen only from normal instances. The instances in Ci are regarded as the representatives for the local background around the outlier. Although Ci contains only a small number of data instances compared to the size of the whole dataset, they constitute the border regions of the inlier class and thus are adequate to discriminate between inlier and outlier classes, as shown in the Step 2 of Figure 2.

As local context may indicate some interesting structures (e.g., instances with similar semantics are located close to each other in the attribute space), we further segment Ci into multiple disjoint clusters. To determine the number of clusters L in Ci, we adopt the measure of prediction strength [Tibshirani and Walther, 2005] which shows good performance even when dealing with high-dimensional data. After choosing the value of L, common clustering algorithms such as K-means or hierarchical clustering are applied to divide Ci into multiple clusters as Ci = {Ci,1, Ci,2, · · · , Ci,L}. Clusters of small size, i.e., |Ci,l| ≤ 0.03 · |Ci|, are abandoned in subsequent procedures.

4.2 Maximal-Margin Linear Explanations

The concrete type of models chosen for gi,l should have the following properties. First, it is desirable to keep g ∈ G simple in form. For example, we may expect the number of nonzero weights to be small for linear models, or the rules to be concise in decision trees [Ribeiro et al., 2016]. Here we let g ∈ G belong to linear models, i.e., g(x) = wT x. We impose the l1-norm constraint on w, where attributes am that correspond to large |w[m]| values are regarded as abnormal. Second, since outliers are usually highly isolated from their context, there could be multiple solutions all of which could classify the outliers and inliers almost perfectly, but we want to choose the one that best reflects such isolation property. This motivates us to choose l1 norm support vector machine [Zhu et al., 2004] to build g. The local loss L(h, gi,l;Oi,l, Ci,l) to be minimized in Equation (4) is thus as below:

where Ni,l = |Oi,l ∪ Ci,l|, (.)+ is the hinge loss, ξn is the slack variable, b and c are the parameters. Here yn = 1 if xn ∈ Ci,l and yn = -1 if xn ∈ Oi,l.

From the parameters of the local model gi,l, we can find the abnormal attributes and compute the outlierness score with respect to Ci,l. Let wi,l denote the weight vector of gi,l, the importance of attribute am with respect to the context of Ci,l is thus defined as si,l(am) = |wi,l[m]|/γm i,l . Here γm i,l denotes the resolution of attribute am in Ci,l, i.e., the average distance along the mth axis between an instance in Ci,l and its closest neighbors. The overall score of am for oi is

which is the weighted average score for am over all L clusters. Attributes am with large si(am) are regarded as the abnormal attributes for oi (i.e., am ∈ Ai). For the outlierness score d(oi), we define it as:

This measure is robust to high dimensional data, as w is sparse and dl(oi) is calculated in a low dimensional space. An example is shown in Figure 3, where abnormal attributes are indicated from weight vector w and the outlierness score is shown. The overall outlierness score for oi across all context clusters is:

which is the weighted summation over different context clusters. Here the normalization term γi,l is the average distance from an instance to its closest neighbor in Ci,l. Now we have obtained all of the three aspects of interpretation Ei = { Ai, d(oi), Ci = {Ci,l|l ∈ [1, L]} }.

4.3 Filtering Outliers with Interpretation and Prior Knowledge

In real-world applications, the importance of different attributes varies according to different scenarios [Yang et al., 2011; Ntoulas et al., 2006]. Take social network spammer detection as an example. We have two account attributes: the number of followers (Nfer) and the ratio of tweets posted by API (RAPI). A spammer account tends to have a small Nfer value as it is socially inactive, but large RAPI to conveniently generate malevolent content. However, it is easy for spammers to intentionally increase their Nfer by purchasing followers, but manually decreasing RAPI is more difficult due to expensive human labors. In this sense, RAPI is more robust than Nfer in translating detected outliers as spammers. Therefore, we introduce two vectors β and p, where βm ∈ R≥0 denotes the prior knowledge about the robustness of am, and pm ∈ {-1, 0, 1} denotes the expected perturbation direction of a abnormal attribute. pm = -1 means we expect outliers to have small value for am (e.g., Nfer), pm = 1 means the opposite (e.g., RAPI), while pm = 0 means there is no preference. Thus, the outlierness score of oi with respect to Ci,l is refined as:

where the operator ◦ denotes element-wise multiplication, w′ [m] = min(0,w[m]) if pm = 1, and w′ [m] = max(0,w[m]) if pm = -1. If we label outliers with 1 and inliers with -1, the sign of p is reversed. The reason for introducing w′ is that, if interpretation does not conform with the prior knowledge, such as an outlier in spammer detection is interpreted as having lowRAPI, then the outlierness score of the outlier should be deducted.

5 Experiments

In this section, we present evaluation results to assess the effectiveness of our framework. We try to answer the following questions: 1) How accurate is the proposed framework in identifying abnormal attributes of given outliers? 2) Can we accurately measure the outlierness score of outliers? 3) How effective is the prior knowledge of attributes in refining outlier detection results?

5.1 Datasets

We use both real and synthetic datasets in experiments. We follow the procedures in [Keller et al., 2012] and create two synthetic datasets with ground-truth abnormal attributes for each outlier. In the first synthetic dataset, each outlier is close to only one normal cluster and far away from the others. In the second synthetic dataset, each outlier is in the vicinity of several normal clusters simultaneously, so the scenario is more complicated. The real-world datasets used in our experiments include Wisconsin Breast Cancer (WBC) dataset [Asuncion and Newman, 2007], MNIST dataset and Twitter spammer dataset [Yang et al., 2011]. WBC dataset records the measurements for breast cancer cases with two classes, i.e. benign and malignant. The former class is considered as normal, while we downsampled 25 malignant cases as the outliers. MNIST dataset includes a collection of 28 × 28 images of handwritten digits. Here we use the training set which contains 42,000 examples. Instead of using raw pixels as attributes, we build a Restricted Boltzmann Machine (RBM) with 150 latent units to map images to a lowdimensional space which is more proper for interpretation than raw pixels. A multi-label logistic classifier is then built to classify digits, and the ground-truth outliers are selected as the misclassified instances downsampled to 1, 000. The Twitter dataset contains information of normal users and spammers crawled from Twitter. Following [Yang et al., 2011], we divide attributes into two categories according to whether they are robust to the spammers in disguise. Attributes of low robustness refer to those which can be easily controlled by spammers to avoid being detected, while attributes of high robustness are the opposite.

5.2 Baseline Methods

We include some recent outlying-aspect mining and classifier interpretation methods as baseline methods:

• CA-lasso (CAL) [Micenkov´a et al., 2013]: An interpretation method that analyzes the separability between outlier and inliers as a linear classification problem solved with LASSO, without further clustering the context of outliers.
• IPS-BS [Vinh et al., 2016]: An interpretation method that applies isolation path score to measure outlierness. Beam Search is then applied to look for the abnormal attributes.
• LIME [Ribeiro et al., 2016]: A global classifier is first constructed to classify outliers and inliers. Then the abnormal attributes for each outlier is identified by locally interpreting the classification model around the outlier. A neural network is used as the global classifier for MNIST data, and SVMs with RBF kernel are used for other datasets.

5.3 Abnormal Attributes Evaluation

The goal of this experiment is to verify that the identified attributes indeed explain the abnormality. Since ground-truth abnormal attributes of real-world datasets are not available, we append M Gaussian-noise attributes to all real-world data instances. Noise attributes are not expected to be identified as abnormal as they are of small magnitudes. In our experiments, we choose 0.08 × N nearest neighbors of an outlier oi as its context Ci. The radius of synthetic sampling for building the outlier class Oi is set as half of the average distance to the inlier class Ci to avoid overlap between Oi and Ci. The parameters of SVMs are tuned by validation, where some samples from Oi and Ci are randomly selected as the validation set. The same parameter values are used for all outliers in the same dataset. We report the Precision, Recall and F1 score averaged over all the outliers in Table 2. Besides finding that COIN shows relatively better performance, some observations can be made as follows:

• In general, the Recall value of SYN2 is lower than that of SYN1, because the context of each outlier in SYN2 has several clusters, and the true abnormal attributes vary among different clusters. In this case, retrieving all groundtruth attributes is more challenging.
• IPS-BS is more cautious in making decisions. It tends to stop early if the discovered abnormal attributes already make the outlier query well isolated. Therefore, IPS-BS has high Precision, but only a small portion of true attributes are discovered (low Recall).
• The Recall scores are low for real-world data since we treat all original attributes to be the ground truth, so low Recall values do not necessarily mean bad performances.

5.4 Outlierness Score Evaluation

We evaluate if interpretation methods are able to accurately measure the outlierness score of outlier queries. For each dataset, we randomly sample the same number of inliers as the outliers, and use them together as queries to interpreters. The label is 1 for each true outlier, and 0 for each inlier. For each query, interpreters are asked to estimate its outlierness score. After that, we rank the instances in a descending order with respect to their outlierness scores. Since true outliers are more isolated, an effective interpreter should convert such isolation degree to larger scores.

We report the results in Table 3 with AUC as the evaluation metric. The proposed method achieves better performance than the baseline methods especially on SYN2 and MNIST. This can be explained by the more complex structures in these datasets, where an outlier may be close to several neighboring clusters. COIN resolves the contextual clusters around each outlier, so it can handle such scenario. This also explains why IPS BS is also more effective in complex datasets than the other two baseline methods. The isolation tree used in IPS BS can handle complex cluster structures.

5.5 Filtering Outliers with Prior Knowledge

In this experiment, we discuss if interpretations, together with prior knowledge, can help filtering existing outliers to satisfy the demand of specific applications.

The experiment has two parts. In the first part, we append M new noise attributes to data instances, so each instance is augmented to x ∈ R2M . Different from the noise attributes in Section 5.3 that are of small magnitude, the attributes here may turn inliers to "outliers". However, these new outliers are irrelevant to the ground truth. We sample 0.5 × |O| inliers, together with ground-truth outliers, as queries fed into COIN. We set p to be zero and run COIN with different β values. The weights corresponding to original attributes are fixed to 1 (βm = 1, m ∈ [1, M]), and we only vary the weights of noise attributes (βm = β,m ∈ [M + 1, 2M]). Similar to Section 5.4, we obtain the outlierness score for all queries and rank them in a descending order according to the score. Groundtruth outliers are expected to rank higher. The ranking performance is reported in Figure 4a. The plot indicates that as we increase the weights of noise attributes, the performance of the interpreter degrades for all datasets, because it is more difficult to distinguish between real outliers and noisy instances. From the opposite perspective, assigning large weights to important attributes will filter out mis-detected outliers.

The second part of the experiment uses the Twitter dataset in which features extracted from user profiles, posts and graph structures are used as attributes. According to [Yang et al., 2011], the robustness level varies for different attributes. Some attributes, such as the number of followers, hashtage ratio and reply ratio, can be easily controlled by spammers to avoid being captured, so they are of low robustness, while some other attributes such as account age, API ratio and URL ratio have high robustness. In this experiment, we fix the weight of low-robustness attributes to 1, and vary the weight βm of high-robustness attributes. The remaining procedures are the same as first part of the experiment discussed above. The result of outlierness ranking is reported in Figure 4b. The rising curve shows that as more emphasis is put on highrobust attributes, we are able to refine the performance of spammer identification. The experiment result indicates that by resorting to the interpretation of outliers, we can gain more insights on their characteristics, and adaptively select those that are in accordance with the specific application.

5.6 Case Studies

We conduct some case studies to illustrate interpretation results on MNIST. The attributes are the hidden features extracted by the RBM instead of raw pixels. The case study results are shown in Figure 5. There are three query outlier images shown in the first row. We choose two neighboring clusters for each query, and compute the average image of

• (a) Data with noise attributes
• (b) Twitter spammer data

Figure 5: Visualization of outlier interpretation on MNIST dataset.

each cluster, as shown in the second row. The average images can be seen as part of the contexts of outliers. Clear handwritten digits can be seen from the average images, so that the clusters are internally coherent. The third and fourth rows together indicate the noteworthy attributes of the query image with respect to the corresponding average images. The black strokes enclosed by red circles in third-row images represent positive abnormal attributes, i.e., the query image is regarded as an outlier instance because it possesses these attributes. The strokes enclosed by blue circles in fourth-row images are negative abnormal attributes, as the query outlier digit does not include them. These negative attributes, however, commonly appear in the neighbor images of the outlier. The positive and negative attributes together explain why the outlier image is different from its nearby normal images.

6 Conclusion and FutureWork

In this paper, we propose a model-agnostic outlier interpretation framework by resolving outliers' local context. We define the interpretation of an outlier from three aspects including the abnormal attributes, outlierness score and the outlier's context. Interpretation is distilled from the results of a series of classification tasks. Prior knowledge in different applications can be incorporated with interpretation results to refine the outlier detection result. Interesting extensions include applying hierarchical clustering to accurately partition the whole data space, considering heterogeneous data sources and incoporating deep models [He et al., 2017].

Acknowledgments

The work is, in part, supported by DARPA (#N66001-17-24031) and NSF (#IIS-1657196, #IIS-1718840). The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.