Learning Homophily Couplings from Non-IID Data for Joint Feature Selection and Noise-Resilient Outlier Detection

1 Introduction

Outliers are rare or inconsistent objects, compared to the majority of objects. In recent applications such as insider trading, network intrusion detection and fraud detection, a key task is to detect unexpected objects in a sophisticated environment with noise and complex feature relations.

Unsupervised outlier detection methods assign each object an outlier score and report the top-ranked objects as outliers without using class labels. They have been receiving great attention due to the high cost of obtaining class labels in real-world applications. However, they face big challenges in handling data with a mixture of relevant and noisy features (such data is referred to as noisy data hereafter). In such data, outliers can be detected in relevant features while they are masked as normal objects with the inclusion of noisy features - features in which outliers may contain normal behaviors while normal objects may contain abnormal behaviors.

Subspace and feature selection are two major approaches to handle outlier detection in noisy data. Subspace outlier detection methods (e.g., FPOF [He et al., 2005] and COMP [Akoglu et al., 2012]) first identify a set of relevant feature subspaces/patterns and then apply outlier scoring functions to combine the outlierness (i.e., outlying degree) of objects in these subspaces. These methods separate subspace/pattern search from outlier scoring to facilitate modular design and the application of existing subspace/pattern discovery techniques into outlier detection. However, such search can be misled by noisy features and produce faulty subspaces/patterns, resulting in high false positives.

Outlying feature selection is to select relevant features for subsequent outlier detection. Limited work has been done in this area. Moreover, the existing work (i.e., [Pang et al., 2016a; 2016b]) on filter-based approaches [Li et al., 2016] selects a feature subset independently from subsequent learning methods. Consequently, the relevant features they retain can be noisy w.r.t. subsequent outlier detection methods. In contrast to filter-based approaches, wrapper-based approaches choose an optimal feature subset w.r.t. the learning methods [Kohavi and John, 1997]. However, although wrapper-based feature selection is popular for classification and clustering [Li et al., 2016], as far as we know, no such work has been reported on outlier detection.

This paper proposes a novel Wrapper-based Outlier Detection framework (WrapperOD) to detect outliers in noisy data. As shown in Figure 1, WrapperOD first defines an outlier scoring function to rank objects based on their outlierness in a given feature subset, and then designs an outlier ranking evaluation function to measure the relevance of the feature subset by the outlier ranking quality. These two steps are iteratively performed until the best feature subset (alternatively the best outlier ranking) is obtained. Essentially, WrapperOD unifies the outlier ranking quality with the feature subset relevance into one objective function and makes a joint optimization.

We further instantiate WrapperOD to a Homophily cOupling-based oUtlieR detection method, called HOUR, for categorical data which has been insufficiently explored. Many real-world data often demonstrates strong homophily coupling between outlying behaviors (i.e., feature values) [Chau et al., 2011; Pang et al., 2016a]. That is, outlying behaviors are not independent and they tend to be concurrent. As a result, the outlierness of a behavior is dependent on its coupled behaviors, i.e., a behavior has large outlierness if it has strong linkage to many outlying behaviors and vice versa. HOUR treats such data as data with non-independent and identically distributed (non-IID) behaviors [Cao, 2014] and specifies a homophily coupling-based outlier scoring function to capture such non-IID behaviors. It further specifies the outlier ranking evaluation function to guide the joint optimization by maximizing the margin between the top-ranked k objects and the other objects. A heuristic search is used to generate reliable feature subsets.

This work makes the following two major contributions.

• We propose a novel WrapperOD framework to identify outliers in noisy data. In contrast to existing solutions that search feature subset(s) independently from outlier scoring, WrapperOD simultaneously optimizes its outlier scoring and feature selection, which enables its outlier scoring function to produce a much more reliable outlier ranking in noisy data.
• The performance of WrapperOD is verified by an instance HOUR. HOUR models homophily couplings between outlying behaviors to construct a fast and noiseresilient outlier scoring function that empowers the joint optimization in WrapperOD. HOUR is guaranteed to obtain a 2-approximation outlier ranking w.r.t. a given outlier ranking evaluation measure.

Extensive experiments show that HOUR (i) significantly outperforms three state-of-the-art outlier detectors and their combination with two of the latest outlying feature selection methods in terms of AUC and/or P@n on 15 real-world data sets with a diverse range of noise levels; (ii) performs stably w.r.t. k in most cases; and (iii) obtains good scalability: it is linear to data size and quadratic to the number of features.

2 RelatedWork

Subspace outlier detection is a popular direction recently proposed to handle data with many noisy/irrelevant features [Zimek et al., 2012]. Traditional methods (e.g., distanceand density-based methods [Chandola et al., 2009]) identify outliers in original feature space and fail to work well in those data due to the meaningless distance with the presence of noisy/irrelevant features [Zimek et al., 2012]. In contrast, subspace-based methods [He et al., 2005; Lazarevic and Kumar, 2005; Angiulli et al., 2009; Keller et al., 2012; Akoglu et al., 2012; Pang et al., 2016c] compute outlier scores in subspaces. Most of these methods use heuristic search to identify outlying subspaces/patterns. This kind of search ignores subsequent outlier scoring functions. Consequently, noisy features may mislead the search, resulting in many faulty subspaces/patterns. The other methods work on a set of randomly generated subspaces and thus do not involve subspace search, but they include many noisy features into subspaces during the random generation of subspaces.

Feature selection has shown effective in removing noisy/irrelevant features for classification and clustering [Li et al., 2016], but limited work has been done on outlier detection. Some work has been conducted on semisupervised/supervised outlying feature selection [Azmandian et al., 2012; Jeong et al., 2012; Lorena et al., 2015]. In contrast, very limited unsupervised methods are available in the literature due to the challenges brought by extreme class imbalance and the unavailability of class labels. The earliest related work is the PALM method for unsupervised minority class analysis [He and Carbonell, 2010], which assumes the minority class objects are strongly self-similar. However, this assumption is opposite to that of outlier detection, in which many outliers are isolated objects and far away from each other. CBRW FS (denoted as CBFS) [Pang et al., 2016a] computes the weights of features for weighted outlier scoring, which can also determine outlying feature selection. As far as we know, DSFS [Pang et al., 2016b] is the first work specifically designed for unsupervised outlying feature selection. These two methods are filter-based approaches that evaluate feature subsets independently from subsequent outlier scoring functions and may retain many noisy features.

CBRW [Pang et al., 2016a] also models similar homophily couplings to estimate value outlierness for handling noisy features, but HOUR is fundamentally different from CBRW in two aspects below: (i) HOUR is a joint optimization of outlier scoring and feature selection while CBRW involves no optimization and works on full feature space; and (ii) CBRW requires iteration algorithms to compute value and object outlierness, whereas the outlier scoring function in HOUR has a closed-form solution and runs substantially faster.

Great effort has been made on non-IID learning in recent years [Cao et al., 2012; Cao, 2014; 2015; Cinbis et al., 2016], while limited work [Pang et al., 2016a; Chen et al., 2016] has been reported on non-IID outlier detection. This work exploits the non-IID outlying behaviors to enable noise-resilient outlier detection.

3 HOUR for Joint Outlier Detection and Outlying Feature Selection

Given a set of data objects X = {x1, x2, · · · , xN} with size N, described by D features F = {f1, f2, · · · , fD}, WrapperOD first defines an outlier scoring function φS to compute object outlierness in a given feature subset S ⊆ F and then sorts the objects based on their outlierness to obtain an outlier ranking RφS . WrapperOD further defines an outlier ranking evaluation function J to compute the quality of RφS and uses this ranking quality as the relevance indicator of the subset S. This means that the task of finding the best feature subset is equivalent to finding the best outlier ranking. WrapperOD

iteratively performs function φS and function J to obtain the best feature subset S ∗ and outlier ranking R∗φS∗ .

WrapperOD is fundamentally different from existing outlier detection and outlying feature selection frameworks in that: WrapperOD unifies the two correlated tasks, outlier detection and outlying feature selection, to simultaneously obtain the optimal outlier ranking and feature subset, while existing solutions treat these two tasks independently and are very sensitive to noisy features.

We further instantiate WrapperOD for categorical data by proposing HOUR. HOUR specifies its three components by a homophily coupling-based outlier scoring function φS, a score margin-based outlier ranking evaluation function J , and a heuristic feature subset search method:

3.1 Specifying φS with Homophily Couplings

The scoring function φS has to meet at least the two requirements: (i) being sufficiently resilient to noisy features, and it may opt for noisy features other than relevant features otherwise; and (ii) being very efficient as it will be repeatedly performed to evaluate a large number of feature subsets. Unfortunately, most outlier detectors are sensitive to noisy features and/or are computationally costly [Pang et al., 2016a].

HOUR exploits the homophily couplings between feature values to construct a fast and robust function φS. Let dom(f) = {v1, v2, · · · } be the domain of a feature f ∈ S, which consists of a finite set of unordered feature values, and V be the whole set of feature values in S: V = ∪f∈Sdom(f), where dom(f ) ∩ dom(f ′ ) = ∅, ∀f ̸= f ′ .

Definition 1 (Value Influence). The outlierness influence of a feature value v ∈ V is defined as follows.

where Nv denotes a set of values that co-occur with v and δ(·) : V ↦→ (0, 1) is an initial outlierness influence estimation of a value based on intra-feature frequency distribution.

We use δ(v) = 1 2 ( freq(m)-freq(v) freq(m) + 1 freq(m) ), ∀v ∈ dom(f), m is a value that occurs most frequently in f (i.e., the mode) and freq(·) is a frequency counting function. Such mode absolute deviation helps δ(·) address features with imbalanced frequency distributions.

Essentially, δ estimates the value outlierness influence independently from the values of other features. τ further utilizes the homophily couplings between values from different features to have a better estimation of value influence. This value influence is then used to infer the value outlierness based on the coupling strength between feature values.

Definition 2 (Value Outlierness). The outlierness of a feature value v ∈ V is defined as follows.

where ρ(u, v) = log p(u,v) p(u)p(v) is pointwise mutual information to measure the coupling strength between two values.

We further define the outlierness of an object below.

Definition 3 (Object Outlierness). The outlierness of an object x is defined as a weighted product of value outlierness.

where xf is the value contained by x in feature f and ω(f) = 1- ∏v∈dom(f) [1-ψ(v)] computes the weight of f.

Section 4.1 will discuss how this outlier scoring models the homophily couplings and why it is fast and noise-resilient.

3.2 Specifying J with Average Score Margin

The function J requires an internal evaluation measure for a given outlier ranking, i.e., evaluating outlier rankings without class labels. Internal evaluation measure has been extensively studied for clustering tasks, while very little work has been on outlier detection [Marques et al., 2015]. One related work is [Marques et al., 2015], which uses pseudo binary classification to evaluate the ranking quality. However, this method has O(N 3 ) time complexity, which is computationally prohibitive to be used here. Below we introduce a linear-time outlier ranking evaluation measure based on the distribution of object outlierness:

where O is a set of top-ranked k objects and φS(x′ ) is the median outlierness in the remaining objects. ∆S = 1k ∑x∈O [φS(x) - φS(x′ )] is the average score margin between the top-k objects and the center of the other objects, which also indicates the relevance of feature subset S. So maximizing J finds an outlier ranking that jointly maximizes the object outlierness margin and the feature subset relevance.

3.3 Recursive Search of Feature Subset S

Feature subset search methods includes complete search, sequential search, and random search [Li et al., 2016]. Although complete search outputs an optimal subset, it has exponential time complexity. Sequential search and random search may produce a suboptimal subset, but they are more practical than complete search as they run substantially faster.

A sequential search method, namely Recursive Backward Elimination (RBE), is used with the functions φS and J to search for an approximately best subset. RBE recursively eliminates one feature at a time until no feature remains, and only retains the feature subset that results in the largest J. RBE is used because it can guarantee a 2-approximate J to the optimal one (see Section 4.2).

3.4 The Algorithm and Its Time Complexity

Algorithm 1 presents the procedure of HOUR. Steps (1-3) evaluates the outlier ranking in the full feature set, followed by the evaluation of outlier rankings in feature subsets generated by RBE in Steps (4-14).

Steps (1-2) require one database scan to perform ψ and φS respectively, which is linear w.r.t. N. Step (3) needs to

Algorithm 1 HOUR(X , k)

Input: X - data objects, k - the number of targeted outliers Output: R - an outlier ranking of objects, S - a feature subset 1: ψ(v) ← ∑u∈Nv ρ(u, v)τ(u), ∀v ∈ V 2: Compute φF(x), ∀x ∈ X 3: r ← J(RφF , k) 4: while |F| > 0 do 5: for i = 1 to |F| do 6: Compute φF\fi (x), ∀x ∈ X 7: Compute Ji(R′φF , k) 8: end for 9: Find feature fi with the largest Ji(R′φF , k) 10: F ←F \ fi and update ψ(v) for all v contained in F 11: if Ji(R′φF , k) ≥ r then 12: R←R′ , S ←F and r ← Ji(R′φF , k) 13: end if 14: end while 15: return R and S

rank X, which has O(NlogN) in the worst case, and thus they have O(NlogN). The two loops in Steps (4-14) result in O(D2 ) in the worst case, and the core computation within the loops performs outlier scoring and ranking, which has the same time complexity as the first three steps. Hence, the worst time complexity of HOUR is O(D2NlogN).

4 Theoretical Analysis

4.1 Robustness w.r.t. Noisy Features

We analyze the robustness of HOUR from the value level to the feature level. At the value level, per definition of outliers, outlying values are infrequent values contained by outliers, while noisy values are also infrequent but contained by normal objects. In contrast, normal values are frequent values contained by both outliers and normal objects. Below we discuss how the outlier scoring function in HOUR can efficiently distinguish outlying values from normal and noisy values.

Theorem 1 (Homophily Coupling Modeling). The value influence estimation τ(v) in Eqn.(1) is equivalent to the stationary probability of visiting v in random walks on a strongly connected undirected value-value graph G =< V, E, η(·, ·) >, where a feature value v represents a graph node, e(u, v) ∈ E denotes an edge between two nodes u and v, and η(u, v) = δ(u)I(u, v)δ(v) (I(u, v) = 1 if u and v have occurrences, and I(u, v) = 0 otherwise) is the weight of edge e(u, v), ∀u, v ∈ V.

Proof. Let π∗ (v) be the stationary probability, P(u, v) be the transition probability from u to v, d(v) = ∑u∈Nv η(v, u) be the weighted degree of v and vol(G) = ∑v∈V d(v) = ∑v∈V ∑u∈Nv δ(v)δ(u) be the graph volume. Then we have:

and we obtain:

which completes the proof.

Theorem 1 indicates that given ∀u, v ∈ V, if value u has lower frequency and stronger couplings with other infrequent values compared to value v, i.e., d(u) > d(v), then τ(u) > τ(v). This essentially models the homophily couplings between outlying values. However, this homophily coupling modeling does not take account of the coupling strength between values. We further enhance the modeling by adding pointwise mutual information in Eqn. (3). There exist other ways to model homophily couplings. We use such a two-stage modeling because it has a closed-form solution which guarantees the efficiency of outlier scoring.

Outlying Values vs. Noisy Values. Noisy values have similarly low frequencies as outlying values, but they are supposed to co-occur randomly or follow a Gaussian distribution. Their homophily couplings are therefore weaker than that of outlying values. As a result, HOUR assigns smaller outlierness ψ to noisy values than outlying values.

Outlying Values vs. Normal Values. Normal values have much lower δ and τ than outlying values due to their high occurrence frequencies. Their high frequencies also result in weak couplings with infrequent values. As a result, they obtain substantially smaller outlierness ψ than outlying values.

At the feature level, HOUR prefers features that contain values of higher outlierness to maximize its objective function. Since outlying values have higher outlierness than normal or noisy values, the features HOUR iteratively eliminates are those containing normal and/or noisy values, resulting in a cleaned feature subset for its outlier scoring function.

4.2 Theoretical Bound

This section shows that HOUR is guaranteed to obtain an outlier ranking with the margin of at least half of the optimum value, provided that features are dependent on each other as in the homophily coupling modeling.

Theorem 2 (2-Approximation). Let R and S be the outlier ranking and feature subset returned by HOUR. Assume Θf be the contribution of feature f ∈ S to the outlier ranking R by integrating its conjunctive functions with other features θ(f ∧ f ′ ), i.e., Θf = ∑f ′∈S θ(f ∧ f ′ ), and ∆S = 1 2 ∑f∈S Θf . Then we have J(RφS , k) ≥ 1 2 Jopt , where Jopt is the optimum value of J.

Proof. Since Jopt is the optimum value of J, we have

We obtain Θf ≥ Jopt after some replacements. Let f ∈ S ∗ be the feature that HOUR removes first among those contained in S ∗ during the iteration of RBE and T be the feature set before f is removed, i.e., S ∗ ⊂ T . Since HOUR removes the least contributive feature at a time, we have Θf ′ ≥ Θf , ∀f ′ ∈ T when HOUR chooses to remove f, and thus Θf ′ ≥ Jopt . As a result, we obtain ∑f ′∈T Θf ′ ≥ Jopt |T |, and thus 2∆T ≥ Jopt |T |, resulting in J(R′φT , k) = ∆T |T | ≥ Jopt 2 . Since HOUR retains S that results in the largest J and T is one of the candidates, we finally obtain J(RφS , k) ≥ J(R′φT , k) ≥ Jopt 2 .

5 Experiments and Evaluation

5.1 Competitors and Parameter Settings

HOUR is evaluated against three representative outlier detectors for categorical data: FPOF [He et al., 2005], COMP [Akoglu et al., 2012] and CBRW [Pang et al., 2016a]. FPOF is chosen because it is the most popular pattern-based method. COMP is a state-of-the-art subspace method that captures arbitrary-length outlying behaviors. CBRW is a closely related value outlierness-based method. k in HOUR is set to the number of outliers by default. COMP is parameterfree. FPOF and CBRW are used with their default settings.

We also compare HOUR to the combination of outlier detectors with two of the most recently proposed outlying feature selection methods, CBFS [Pang et al., 2016a] and DSFS [Pang et al., 2016b]. CBFS returns a feature ranking. DSFS outputs a feature subset without any parameters. To have a fair comparison, CBFS selects the top-ranked |S| features so that CBFS and HOUR select the same number of features.

All methods are in Java in WEKA [Hall et al., 2009] except COMP which is in MATLAB. All these methods are executed on a node in a 3.4GHz Phoenix Cluster with 32GB memory.

5.2 Performance EvaluationMethod

Two of the most popular evaluation methods, the area under ROC curve (AUC) and precision at n, i.e., P@n (where we set n as the number of outliers in a data set), are used. All the outlier detectors produce an ascending ranking based on outlier scores. AUC evaluates the global ranking quality, while P@n considers the detection precision in the top n positions. Higher AUC or P@n indicates better performance.

Two data indicators, feature noise level (fnl ) and outlier separability (sep), are defined to evaluate data complexity before and after applying feature selection. fnl is defined by [Pang et al., 2016a; 2016b] as the percentage of individual noisy features. Inspired by the indicator feature efficiency in [Ho and Basu, 2002; Leyva et al., 2015], sep is defined as the maximum feature efficiency per data, in which the efficiency of a feature is quantified by the AUC performance of using frequency histogram to detect outliers on the single feature.

5.3 Data Sets

Fifteen publicly available real-world data sets with a range of feature noise levels are used, which cover diverse domains, e.g., image object recognition, intrusion detection and molecular screening, as shown in Table 1. These data sets are transformed from extremely imbalanced data, where the rare classes are treated as outliers versus the rest of classes as normal class [Lazarevic and Kumar, 2005; Pang et al., 2016a].

5.4 Findings and Analysis

1) Obtaining Significantly Better Global or Top-n Outlier Ranking Than Other Outlier Detectors: We compare HOUR with CBRW, COMP and FPOF in terms of AUC and P@n in Table 1. In terms of AUC, HOUR obtains the best performance on 11 data sets; and on average, it obtains about 2%, 7% and 21% improvement over CBRW, COMP and FPOF, respectively. HOUR significantly outperforms FPOF in AUC. In terms of P@n, HOUR performs significantly better than CBRW and COMP and obtains more than 30%, 37% and 90% improvements over CBRW, COMP and FPOF, respectively.

Using outlier scoring results to guide outlying feature selection enables HOUR to remove most, if not all, of the noisy features while having little or no loss in outlier separability on most data sets, i.e., the 11 data sets on which HOUR obtains the best AUC performance (see the fnl and sep results of HOUR in Table 2). Hence, although HOUR works with 69% less features than its competitors, it performs substantially better as it works on much cleaner data. Also, maximizing the margin of the top-k objects from the others helps rank more outliers in the top, resulting in significant improvement in P@n. On the other hand, HOUR opts for strongly relevant features that help rank outliers in the top, so it may remove weakly relevant features that distinguish outliers from normal objects in other positions. As a result, HOUR may obtain worse AUC performance while comparable P@n compared to its competitors, e.g., the results on AID362 and Census.

2) Defeating the Combination of Outlier Detectors with Outlying Feature Selection Methods: HOUR is compared with the combination of CBRW and COMP with outlying feature selection methods CBFS and DSFS in Table 2 1 . Although the two feature selection methods largely improve CBRW and COMP in terms of AUC and/or P@n, HOUR remains as the best performer on most data sets. HOUR obtains significantly better performance than the combination of CBRW and COMP with CBFS in AUC and significantly outperforms all the four different combinations in P@n.

The superiority of HOUR is because the wrapper-based feature selection scheme enables HOUR to remove substantially more noisy features than the filter-based methods CBFS and DSFS. This is verified by the fnl and sep differences between the full feature set and feature subsets selected by HOUR, CBFS and DSFS shown in Table 2. On average, HOUR removes over 50% of the noisy features, which outperforms CBFS (12%) and DSFS (22%) by a factor of more than four and two, respectively; while at the same time, it obtains a very comparable outlier separability. In addition, we observe that filter-based methods like DSFS generally retain many more features than HOUR. These extra features contain noisy features as well as relevant features. This is why DSFS obtains a smaller noise reduction level but a better outlier separability than HOUR in Table 2. The extra relevant features retained by DSFS enable CBRW and COMP to outperform HOUR in data sets where HOUR makes very aggressive feature reduction, e.g., on AID362 and Census.

1 The combination of FPOF with CBFS or DSFS underperforms that of CBRW and COMP and is omitted due to space limits.

3) Good Stability w.r.t. the Parameter k: We examine the stability of HOUR w.r.t. k in Figure 2. HOUR shows stable performance in most of the 15 data sets. Here we illustrate representative and interesting trends in its AUC performance w.r.t. a wide range of k on four data sets due to space limits. HOURperforms very stably onCelebA andCUP14. It is very challenging to rank outliers in the top-k positions in data sets which contain only a very small proportion of outliers but have many noisy features (e.g., CT), as the outliers are easily masked as normal objects in those data. Due to these false negatives, HOUR requires a large k (e.g., 0.5%) to perform well on CT. On the other hand, HOUR can identify outliers more accurately using a smaller k in Census which contains a larger proportion of outliers, as the use of a large k might lead to false positives. A general guideline is to set k = 0.5%×N to leverage the effect of false negatives and false positives.

4) Good Scalability w.r.t. Data Size and Dimensionality: The scale-up test results are presented in Figure 3. HOUR is linear w.r.t. data size and quadratic w.r.t. dimensionality. HOUR runs comparably fast to CBRW and FPOF w.r.t. different data sizes. In the right panel, HOUR runs five orders of magnitude faster than FPOF, while the iterative optimization process makes HOUR run considerably slower than CBRW.

6 Conclusions and Future work

A wrapper-based outlier detection framework WrapperOD and its instance HOUR are introduced to handle data with noisy features. HOUR is more plausible than its competitors: (i) it guarantees the margin between the top-k outliers and the other objects is a 2-approximation to the optimum value; (ii) it performs significantly better in global and/or local outlier ranking; and (iii) it obtains stable performance w.r.t. k and good scalability. The capability of returning the top k outliers with superior P@n performance makes HOUR a good candidate for real-world applications, since investigation resources are often only sufficient for limited suspicious objects.

Acknowledgments

This work is partially supported by the ARC Discovery Grants DP130102691 and DP140100545.