Outlier Detection in Complex Categorical Data by Modeling the Feature Value Couplings

1 Introduction

Outliers (or anomalies) are rare data objects, i.e., those objects with rare combinations of feature values, compared to the majority of objects. Detecting outliers in categorical data has wide applications in various domains, such as intrusion detection, fraud detection, and early detection of diseases, where categorical features are the only or indispensable features for describing data objects [Chandola et al., 2009].

Many real-world categorical data sets own one or both of the following key characteristics: (i) there are diversified frequency distributions across different features (e.g., different mode frequencies), resulting in different semantics of the frequencies of different patterns (i.e., combinations of feature values); (ii) they contain a large proportion of noisy features - features in which normal objects contain infrequent behaviours while outliers contain frequent behaviours.

Most unsupervised outlier detection methods for categorical data (e.g., [He et al., 2005; Das and Schneider, 2007; Akoglu et al., 2012]) are pattern-based methods, which search for outlying/normal patterns and employ pattern frequency as a direct outlierness measure to detect outliers (i.e., patterns have the same outlierness if they have the same frequency). These methods are ineffective in handling data sets with aforementioned characteristics, as the semantic of each pattern and its frequency are different from one another and a proportion of the patterns they obtain are misleading. We call such data as complex data in the sense that outliers cannot be easily identified by patterns.

In a fraud detection example shown in Table 1, the feature values 'bachelor' and 'divorced' have the same outlierness in pattern-based methods since they have the same frequency 16 , but the frequency can indicate different outlierness in the features 'Education' and 'Marriage' (e.g., having different deviations from the mode frequencies 12 and 5 12 , respectively). Also, by only examining the features 'Marriage' and 'Income', it is easy to derive some patterns (e.g., one is divorced and has low income) to successfully spot the cheater, while it is difficult to derive effective outlying/normal patterns with the presence of the noisy features 'Gender' and 'Education'.

In this paper, we introduce a new unsupervised outlier detection method, namely Coupled Biased Random Walk (CBRW), to identify outliers in those complex data. CBRW estimates the outlierness of each feature value by capturing both intra- and inter-feature value couplings. By intrafeature value couplings, we consider the within-feature frequency distribution to manifest the outlierness semantic of a value frequency in diversified frequency distributions. For example, the resultant outlierness of 'bachelor' is 0▷58 while that of 'divorced' is 0▷59, considering the two different frequency distributions taken by the features 'Education' and 'Marriage', i.e., ¶ 12 ↪ 13 ↪ 16 ♦ and ¶ 5 12 ↪ 5 12 ↪ 16 ♦, respectively.

By inter-feature value couplings, we score feature values based on its interactions with values of other features. Motivated by examples in diffusion networks, e.g., if someone has an overweight friend, his/her chance of becoming obese increases by 57% [Christakis and Fowler, 2007], we employ an iterative process to model outlierness propagation between feature values: a feature value has high outlierness if it has strong couplings (e.g., high conditional probabilities) with many other outlying values. This enables CBRW to distinct outlying values from noisy feature values, as noisy values are supposed to have weak couplings with outlying values. For example, compared to the noisy value 'bachelor', although the outlying value 'low' has lower outlierness by only considering intra-feature value couplings, it has much higher outlierness when adding inter-feature value couplings, because it has stronger couplings with the exceptional value 'divorced'.

These two value-level couplings, which carry intrinsic data characteristics, are data-driven factors and are fed into a biased random walk model [G´omez-Garde˜nes and Latora, 2008] to handle the complex data.

Note that CBRW is fundamentally different from another method that computes the value outlier scores by using the marginal probabilities of the feature values [Das and Schneider, 2007], which ignores the interactions within and between features. As a result, it fails to work on complex data sets.

Accordingly, two major contributions are made:

1. We propose a novel coupled unsupervised outlier detection method CBRW. It estimates the outlierness of each feature value by modelling intra- and inter-feature value couplings via biased random walks on an attribute graph to tackle the two aforementioned issues.
2. The estimated outlier scores of feature values can either detect outliers directly or determine feature selection for subsequent outlier detection. To the best of our knowledge, this is the first work having such a characteristic.

Substantial experiments show that (1) our CBRW-based outlier detection method significantly outperforms the stateof-the-art methods on complex data sets; (2) without the costly pattern searching, our method runs much faster than the pattern-based methods; and (3) the CBRW-based feature selection method greatly lifts the pattern-based outlier detectors on data sets with many noisy features in terms of both accuracy and efficiency.

The rest of this paper is organised as follows. We discuss the related work in Section 2. CBRW is detailed in Section 3. The use of CBRW for outlier detection is presented in Section 4. Experiments and evaluation are provided in Section 5. We conclude this work in Section 6.

2 RelatedWork

Many unsupervised outlier detection methods were designed for numeric data [Breunig et al., 2000; Ramaswamy et al., 2000; Bay and Schwabacher, 2003]. By contrast, significantly less research has been conducted on categorical data. Existing methods on categorical data are mainly patternbased methods, which search for infrequent/frequent patterns as outlying/normal patterns through different methods (e.g., frequent pattern mining [Ghoting et al., 2004; He et al., 2005; Koufakou and Georgiopoulos, 2010; Smets and Vreeken, 2011], information-theoretic measures [Akoglu et al., 2012; Wu and Wang, 2013], and probability tests [Das and Schneider, 2007]) to build respective detection models. The objects with infrequent behaviours are identified as outliers. However, for a data set with many noisy features, these methods identify a large proportion of misleading patterns, leading to high false positive error. Also, the resultant patterns are derived from different feature combinations, which can have very different frequency distributions. Therefore, the semantic and importance of pattern frequency differ significantly for different patterns, and thus pattern frequency-based methods cannot appropriately capture the outlierness in data sets with diversified frequency distributions.

In addition, the pattern searching has time and space complexities that are exponential to the number of features. A heuristic search is used in [Akoglu et al., 2012] to reduce the complexities from exponential to quadratic, but the search is still computationally intensive in high dimensional data.

Proper feature selection can remove noisy/irrelevant features to improve the performance of outlier detection on complex data. However, existing feature selection research focuses on regression, classification and clustering [Liu and Yu, 2005; Hesterberg et al., 2008]. Very limited feature selection methods have been designed for outlier detection. The work in [Azmandian et al., 2012] is an early attempt, but their proposed method is supervised and it is for numeric data.

Coupling analysis has been successfully employed to tackle complex problems in different domains, e.g., temporal outlying behaviour detection [Cao et al., 2012] and similarity analysis [Wang et al., 2015]. This work extends this methodology by integrating the coupling analysis via a graph-based ranking model to identify outliers in categorical data.

3 CBRW for Estimating Outlier Scores of Feature Values

The proposed method CBRW first maps the categorical data into a value-value attribute graph. The topological structure of the graph is built on inter-feature value couplings, while the node property is obtained based on intra-feature value couplings. The task of estimating the value outlierness is then transformed to solve a graph-based ranking problem (i.e., to rank the nodes). We finally build biased random walks on the graph to obtain outlier scores of feature values.

3.1 Preliminaries

Let X = ¶x1↪ x2↪ · · · ↪ xN♦ be a set of data objects with size N, described by a set of D categorical features F = ¶f1↪ f2↪ · · · ↪ fD♦. Each feature f 2 F has a domain dom(f) = ¶v1↪ v2↪ · · · ♦, which consists of a finite set of possible feature values. The value of an object x in a feature f is denoted by gf(x). Each feature f is associated with a categorical distribution, where f takes on one of the possible values v 2 dom(f) with a frequency p(v) = ♣¶x2X♣gf (x)=v♦♣ N .

The domains between features are distinct, i.e., dom(fi) \ dom(fj) = ;↪ 8i 6= j, and the whole set of feature values V is the union of all the feature domains: V = [f2Fdom(f).

Let G =< V↪ E > be a directed and weighted graph, each node v 2 V in G represents a feature value, and entries in the out-degree adjacent matrix A of G represent weights assigned to edges. Since G is a value-value graph, the terms 'feature value' and 'node' are used interchangeably hereafter.

3.2 Node Property Based on Intra-feature Value Couplings

In the constructed graph, each node is associated with a node property, which is defined based on the value frequency and the frequency of the mode within a feature.

Definition 1. A mode of a categorical distribution of a feature f 2 F, denoted as m, is defined as a feature value vi 2 dom(f) such that p(vi) = max(p(v1)↪ · · · ↪ p(vK)), where K is the number of possible values in f.

Proposition 1. Given any two modes mi and mj of features fi and fj , and their frequencies p(mi) and p(mj), if p(mi) 6= p(mj), then p(u) is not directly comparable to p(v) in terms of their outlierness, 8u 2 dom(fi)↪ v 2 dom(fj).

It is assumed that outliers are rare objects compared to the majority of objects. In the same spirit, the rarity of a feature value should be evaluated against the frequencies of other values. The modes are the central tendency of the features, and their frequencies represent the majority. p(mi) 6= p(mj) indicates that fi and fj have different rarity evaluation benchmarks, and thus p(u) and p(v) are not directly comparable.

Definition 2. The intra-feature outlierness of a feature value v 2 dom(f) is defined by the sum of the deviation of the value frequency from the mode frequency, dev(v), and the outlierness of the feature mode m, base(m):

where dev(v) = p(m)-p(v) p(m) and base(m) = 1-p(m).

The intra-feature outlierness δ is in the range (0↪ 1) 1 . It is defined to make values from different frequency distributions semantically comparable. In this measure, the outlierness of the feature mode is employed as a base, and the more the frequency of a feature value deviates from the mode frequency, the more outlying the value is. Any function that guarantees a monotonic decreasing relation between base(m) and p(m) can be used to compute the outlierness of m. Our empirical results show that base(m) = 1 - p(m) performs more stably than other functions, so we use this specification.

3.3 Graph Topological Structure Based on Inter-feature Value Couplings

We extract information from the inter-feature value couplings to examine whether the values of a feature are coupled with the outlying behaviours of the rest of features.

Definition 3. The entry A(u↪ v) is a weight assigned to the edge from node u to node v and is defined as:

1 We neglect features which have p(m) = 1, as those features contain no information for outlier detection.

where p(u↪ v) denotes the co-occurrence frequency of the values u and v, 8u↪ v 2 V .

The entry A(u↪ v) can be interpreted as that outlierness is propagated from u to v at the rate of p(u♣v). In other words, if u↪ v has a strong coupling and u has high outlierness, the outlierness propagating from u to v would be high; and v has high outlierness if and only if there are many nodes having a similar relation as u to v. In this sense, the outlierness of v is also dependent on the behaviours of its co-occurred values. This makes our method less sensitive to noisy features. Note that if u and v are values of the same feature, we have A(u↪ v) = 0 due to p(u↪ v) = 0. Thus, A can be regarded as a matrix of inter-feature outlierness.

The adjacent matrix A is built on conditional probabilities between every two nodes. This is different from the conventional adjacent matrix construction that fills the matrix based on similarities between the nodes. Our way is because the conditional probabilities are simple and they fully capture the desired co-occurrence behaviours, while the similarities between two values in different features are not well defined.

3.4 Biased RandomWalks on the Attribute Graph

In building unbiased random walks (URWs), after obtaining A, we can then obtain transition matrix W as:

where D is the diagonal matrix of A with its u-th diagonal entry d(u) = Pv2V A(u↪ v). The entry W(u↪ v) = A(u↪v) d(u) , which represents the probability of the transition from node u to node v, and it satisfies that Pv2V W(u↪ v) = 1. This transition matrix neglects the intra-feature outlierness, i.e., the node property.

Here we build biased random walks (BRWs) to introduce a bias into the random walking process, and define the entry of the transition matrix as follows:

Wb(u↪ v) indicates that the transition from node u to node v has a probability proportional to δ(v)A(u↪ v). Therefore, every random move is biased by the values of δ associated with the nodes.

Let the column vector ⇡t 2 R♣V ♣ denote the probability distribution of the biased randomwalk at time step t, i.e., the probability of a random walker visiting any given node at the t-th step. Then we have:

where [·]| is the matrix transpose operation, that is, ⇡t+1(v) = Pu2V Wb(u↪ v)⇡t(u).

Corollary 1. If G is irreducible and aperiodic, ⇡ converges to a unique stationary probability ⇡⇤ s.t. ⇡⇤ =W| b ⇡⇤ .

Proof. It is easy to see that BRWs usingWb is equivalent to URWs on a graph Ge with an adjacent matrix Ae, where the entry Ae(u↪ v) = δ(u)A(u↪ v)δ(v), as the transition matrix We of Ge satisfies: We ⌘Wb.

Since δ is always positive, Ae and A have the same irreducibility and aperiodicity [Aldous and Fill, 2002]. If G is irreducible and aperiodic, so does Ge. Based on the Perron-Frobenius Theorem [Aldous and Fill, 2002], we have ⇡⇤ =W| e ⇡⇤ =W| b ⇡⇤ . ⌅

This states that the stationary probabilities of nodes are independent of initialisations of ⇡, and they are proportional to the in-degree weights of the nodes. Motivated by this, we define the outlier score of a feature value as follows.

Definition 4. The outlier score of node v is defined by its stationary probability:

The value v has a large outlier score if and only if it demonstrates outlying behaviour within the feature as well as cooccurs with many outlying values, since ⇡⇤ (v) is proportional to Wb(u↪ v), which is determined by δ(v) and A(u↪ v).

3.5 The Algorithm of CBRW

Algorithm 1 presents the procedures of the coupled biased random walk model (CBRW). Steps (1-8) are performed to obtain the information of the intra- and inter-feature value couplings. The matrixWb is then generated based on Equations (2) and (4).

Algorithm 1 Estimate Value Outlierness (X, ↵)

Input: X - data objects, ↵ - damping factor Output: ⇡⇤ - the stationary probability distribution

• 1: for i = 1 to D do
• 2: Compute p(v) for each v 2 dom(fi)
• 3: Find the mode of fi
• 4: Compute δ(v)
• 5: for j = i +1 to D do
• 6: Compute p(u↪ v), 8u 2 dom(fj)
• 7: end for
• 8: end for
• 9: Generate the matrixWb
• 10: Initialise ⇡⇤ as a uniform distribution
• 11: repeat
• 13: until Convergence, i.e., ♣♣⇡⇤t -⇡⇤t-1 ♣♣1  0▷001 or reach the maximum iteration Imax = 100
• 12: ⇡⇤ (1-↵) 1 ♣V ♣ 1 + ↵W| b ⇡⇤
• 14: return ⇡⇤

Note that our constructed graph could be reducible (e.g., if there are isolated groups of nodes) or periodic (e.g., G is a bipartite graph if a data set has two features only). In Step (12), following [Page et al., 1998], a damping factor ↵, is introduced into Equation (5) to guarantee the convergence:

We employ ↵ = 0▷95 in our experiments, but our empirical results show that CBRW performs stably with the varying of ↵, e.g., ↵ 2 [0▷85↪ 0▷99].

CBRW requires only one scanning over the data objects to obtain the value couplings information in Steps (1-8). The random walks in Steps (11-13) has O(♣E♣Imax). The data size N is often far larger than ♣E♣Imax, so the runtime is determined by N, which is linear to the data size. Theoretically, our method has O(D2 ), as two loops are required in order to obtain the value co-occurrence information. However, the computation within the inner loop (i.e., Step (6)) is just a simple counting, leading to a nearly linear time complexity to the number of features in practice.

4 Outlier Detection using CBRW

Two basic applications of outlier scores of feature values are the vertical and horizontal summation.

4.1 FeatureWeighting and Selection for Outlier Detection

Vertically, the sum of the outlier scores of the values in a feature can be utilised to weight and select features.

In outlier detection, relevant features are the features where the outliers demonstrate outlying behaviours and are distinguishable from normal objects. Thus, the feature relevance can be measured by the sum of outlierness carried by each value of the feature.

Definition 5. The relevance of a feature f is defined as:

Large rel(·) indicates high relevance of the feature to outlier detection. Top-ranked features are the most relevant features, while the bottom-ranked are noisy/irrelevant features.

Our CBRW-based feature selection method (denoted as CBRW FS) selects top-ranked features for each data set. Outlier detectors can then work on the newly obtained data sets with the selected features for enhancing their robustness to noisy features and/or reducing their computation time on high dimensional data. These relevance weights can also be embedded in the outlier scoring function of an outlier detector as a feature weighting.

4.2 Direct Outlier Detection

Horizontally, the outlier scores of feature values can measure the outlierness of an object as follows.

Definition 6. The outlier score of an object x is defined as:

Our CBRW-based outlier detection method (denoted as CBRW OD) employs Equation (9) to rank the data objects. Outliers are data objects having large outlier scores.

The outlier score of an object is the weighted sum of the outlier scores of the values contained by the object, with a relevance weighting factor to highlight the importance of value score(·) in highly relevant features.

The component value score(·) has taken account of the diversified frequency distributions and noisy feature issues. The feature weighting in Equation (9) can further enhance the robustness of our outlier detection method to noisy features.

5 Experiments

5.1 Outlier Detectors and Its Parameter Settings

Our method CBRW was evaluated against three state-of-theart outlier detectors: the frequent pattern-based FPOF [He et al., 2005], the information-theoretic-based CompreX (denoted as COMP) [Akoglu et al., 2012], and the probability test-based MarP [Das and Schneider, 2007].

CBRW used ↵ = 0▷95 by default. Following [He et al., 2005], FPOF was used with the minimum support threshold min sup = 0▷1 and the maximum pattern length l = 5. Both COMP and MarP are parameter-free.

CBRW, FPOF and MarP were implemented in JAVA in WEKA [Hall et al., 2009]. COMP was obtained from the authors of [Akoglu et al., 2012] in MATLAB. All the experiments were performed at a node in a 3.4GHz Phoenix Cluster with 32GB memory.

5.2 Performance EvaluationMethod

All the outlier detectors produce a ranking based on their outlier scores, i.e., top ranked objects are the most likely outliers. The area under ROC curve (AUC) was derived based on the ranking [Hand and Till, 2001]. Higher AUC indicates better accuracy. We compare the efficiency in our scale-up test.

A commonly used evaluation method for unsupervised learning was taken here, namely, detectors were trained and evaluated on the same data set, but it was assumed that the ground truth is unavailable in the training. The ground truth was only involved in computing the AUC in the evaluation.

5.3 Data Sets

Eleven publicly available real-world data sets were used, which cover diverse domains, e.g., intrusion detection, text classification and image object recognition, as shown in Table 2. Probe and U2R were derived from KDDCUP99 data sets using probe and user-to-root attacks as outliers against the normal class, respectively. Other data sets were transformed from extremely imbalanced data, where the rare classes were treated as outliers versus the rest of classes as normal class [Lazarevic and Kumar, 2005; Chen et al., 2009]. The percentage of outliers in each data set ranges from 0.1% to 6.2%.

Data factor refers to underlying data characteristics of data sets, which are associated with the detection performance of outlier detectors. Two key data factors are presented below, and their quantisation results are reported in Table 2.

• ÷ Feature noise level noise. We computed the AUC using MarP for each individual feature. A feature is regarded as a noisy feature if the AUC is less than 0.5. We report the percentage of noisy features.
• ÷ Variation among the frequencies of modes mode. The modes of all the D features were sorted based on their frequencies in descending order ¶mk1 ↪ · · · ↪mkD ♦ where 1  k1 < kD  D, and an average variation extent is obtained as: 2 D(D-1) Pki<kj p(mki ) p(mkj ) 2 [1↪1).

5.4 Evaluation Results

The AUC results of CBRW OD, FPOF, COMP and MarP on 11 data sets with different noise and mode are presented in Table 2. The p-value results are based on paired two-tailed t-test using the null hypothesis that the AUC results of CBRW and another detector come from distributions with equal means.

Detection Performance Summary

CBRW OD achieves the best detection performance on seven data sets, and performs equally well with all other detectors on two data sets, with two close to the best (having the difference in AUC no more than 0.02). The significance test results show that CBRW OD outperforms its three contenders significantly at the 95% confidence level.

Handling Data Sets with High noise

CBRW OD performs substantially better than the other three detectors in all the four data sets with high noise (e.g., noise > 35%) (i.e., aPascal, Census, CelebA and CMC). On average, it obtains more than 12%, 13% and 19% AUC improvement over FPOF, COMP and MarP, respectively.

We also evaluated our method in terms of handling noisy features by using it to select features (e.g., removing noisy/irrelevant features) for subsequent outlier detection.

Figure 1 shows that the AUC results of the four detectors with or without using our feature selection method (CRBW FS) on Census and aPascal, which have the largest percentage of noisy features. All the four enhanced detectors can obtain substantial AUC improvement by working on data sets with selected top-ranked features over a wide range of selection options.

To observe the effect of using CRBW FS on AUC performance and runtime, we examined the results over a range of feature selection options indicated by the inclusive areas of vertical pink lines in Figure 1 and report the average results in Table 3.

Table 3 shows that, on average, FPOF, COMP and MarP can obtain 5% to 36% AUC improvement. Since CBRW OD

has the ability to handle noisy features without using feature selection, its AUC improvement is much smaller than the other three detectors. Also, by working on data sets with reduced number of features, some detectors might obtain substantial efficiency improvement, e.g., on average, FPOF can run four orders of magnitude faster on Census with the topranked features than that working on the full feature set.

Handling Data Sets with High mode

CBRW OD outperforms FPOF, COMP and MarP substantially on all the four data sets with high mode (e.g., mode > 1▷50) (i.e., Census, CMC, Chess and Solar Flare). On average, it obtains more than 13%, 11% and 14% AUC improvement over FPOF, COMP and MarP, respectively.

Handling Simple Data Sets with Low noise and mode

All the four detectors perform very well on data sets with low noise and mode. This is particularly true for data sets with extremely low noise or mode. For example, all the four detectors, including the most simple detector MarP, obtain the AUC of (or nearly) one on Linkage and Probe with noise = 0, and Reuters10 and CoverType with mode  1▷10.

Scalability Test

The scale-up test results are presented in Figure 2. The results reported in the left panel show that all the four detectors have runtime linear to data size. The runtime of COMP increases by a factor of more than 3,000 when the data size increases by a factor of 256; while that of CBRW OD increases by less than 60. Therefore, though CBRW OD and COMP were implemented in different programming languages, the difference in runtime ratio indicates that CBRW OD runs much faster than COMP by a factor of more than 50.

The results reported in the right panel in Figure 2 show that CBRW OD runs more than five orders of magnitude faster than FPOF, and it runs slower than MarP by a factor of more than 30. As indicated by runtime ratio, CBRW OD runs much faster than COMP by a factor of more than 500.

5.5 Discussions

Below, we briefly discuss the impact of feature weighting and other data factors.

• ÷ Feature weighting. The outlier scoring function in Equation (9) includes a feature weighting component. The empirical results show that the unweighted version performs slightly less effectively than the weighted version on the four data sets with high feature noise level, but it still substantially outperforms the three contenders on these four data sets, and it has the same performance as the weighted version on other data sets. Those results are omitted due to the space limit.
• ÷ Other key data factors. There are some other key data factors, e.g., the minimum length of outlying patterns. That is, some outliers are detectable only by looking at combinations of no less than k features. In data sets where the pattern length factor is a dominant factor, e.g., U2R, our outlier detector performs less effective than the pattern-based methods that search for patterns of all possible lengths (e.g., COMP).

6 Conclusions

This paper introduces a new unsupervised outlier detection method CBRW for detecting outliers in complex categorical data. Compared to the pattern-based methods, CBRW is datadriven, which learns from low-level intra- and inter-feature value couplings to estimate outlier scores of feature values. Substantial experiments show that our CBRW-based outlier detector (CBRW OD) can significantly outperform other detectors including FPOF, COMP and MarP on complex data. Further, our CBRW-based feature selection method (CRBW FS) can greatly improve the performance of existing detectors on data sets with many noisy features. CBRW OD runs more than two to five orders of magnitude faster than COMP and FPOF. We are further enhancing the efficiency of CBRW, and extending its applicability, e.g., by integrating the pattern length factor.

Acknowledgements

We would like to thank anonymous reviewers for their helpful and constructive comments. This work is partially supported by the ARC Discovery Project under Grant NO.DP130102691 and No.DP140100545.