Dual-Regularized Multi-View Outlier Detection

1 Introduction

Outlier detection (or anomaly detection) is a fundamental data analysis problem in machine learning and data mining fields. With its aim to identify the abnormal samples in the given sample set, it has a wide range of applications, such as image/video surveillance [Krausz and Herpers, 2010], network failure [Ding et al., 2012], email and web spam [Castillo et al., 2007], and many others [Breunig et al., 2000; Angiulli et al., 2003; Koufakou and Georgiopoulos, 2010;

∗This research is supported in part by the NSF CNS award 1314484, ONR award N00014-12-1-1028, ONR Young Investigator Award N00014-14-1-0484, and U.S. Army Research Office Young Investigator Award W911NF-14-1-0218.

View 1 View 2

Attribute-outlier Class-outlier

Figure 1: Illustration of attribute-/class- outliers. Both views derive from the same original objects. Here, red circle represents attribute-outlier, and blue triangle denotes class-outlier, respectively.

Hido et al., 2008; Liu and Lam, 2012]. For more details, we highly recommend readers refer to the surveys [Chandola et al., 2009; Akoglu et al., 2014]. These methods usually analyze the distribution or density of a data set, and identify outliers via some well-defined criteria. However, they only work for single-view data like many other conventional machine learning methods. Nowadays, data are usually collected from diverse domains or obtained from various feature extractors, and each group of features is regarded as a particular view [Xu et al., 2013]. Due to the complicated organization and distribution of data, outlier detection from multi-view data is very challenging.

To date, there are a few methods designed to detect outliers for multi-view data. Das et al. [Das et al., 2010] proposed a heterogeneous outlier detection method using multiple kernel learning. Janeja et al. developed a multi-domain anomaly detection method to find outliers from spatial datasets [Janeja and Palanisamy, 2013]. Muller et al. presented an outlier ranking algorithm for multi-view data by leveraging subspace analysis [M¨uller et al., 2012]. The most related literatures to our proposed method are cluster-based multi-view outlier detection approaches [Gao et al., 2011; 2013] and [Alvarez et al., 2013].

Although a number of methods have been proposed in either single-view or multi-view category, they can only deal with certain patterns of outliers respectively. We claim that by representing the multi-view data with latent coefficients and sample-specific errors, our proposed model DMOD can identify all the outliers simultaneously. Before we make a further comparison, we first define two kinds of outliers as follows:

Definition 1. Class-outlier is an outlier that exhibits inconsistent characteristics (e.g., cluster membership) across different views, as the blue triangle shown in Figure 1.

Definition 2. Attribute-outlier is an outlier that exhibits consistent abnormal behaviors in each view, as the red circle shown in Figure 1.

We argue that, on one hand, the existing multi-view methods [Gao et al., 2011; 2013; Alvarez et al., 2013] are only designed for class-outlier outliers. One the other hand, the existing single-view outlier detection methods can only handle attribute-outliers [Liu et al., 2012; Xiong et al., 2011]. However, by representing both kinds of outliers in two different spaces, i.e. latent space and original feature space, our approach can detect both class- and attribute- outliers jointly. In sum, the contributions of our method are summarized as:

• We propose a novel dual-regularized multi-view outlier detection method. To the best of our knowledge, this is the pioneer work to achieve identifying both class- and attribute- outliers simultaneously for multi-view data.
• Outliers are identified from the perspective of data representation, i.e. the coefficient in latent space and samplespecific error in original feature space with a novel cross-view outlier measurement criterion.
• The consistent superior results on five benchmark datasets demonstrate the effectiveness of our method. Specifically, in database letter, we raise the performance bar by around 26.13%.

2 RelatedWorks

In this section, we only focus on the most relevant works: multi-view outlier detection methods.

Identifying the abnormal behaviours with multi-view data is a relatively new topic in the outlier detection field. Only a few methods are recently proposed to deal with it [Gao et al., 2011; 2013; Alvarez et al., 2013]. Gao et al. presented a multi-view anomaly detection algorithm named horizontal anomaly detection (HOAD) [Gao et al., 2011; 2013]. Several different data sources are exploited to identify outliers from the dataset. The intuition of HOAD is to detect sample whose behavior is inconsistent among different sources, and treat it as anomaly. An ensemble similarity matrix is firstly constructed by the similarity matrices from multiple views, and then spectral embedding is computed for the samples. The anomalous score is computed based on the cosine distance between different embeddings. However, it is worth noticing that HOAD is only designed to deal with the class-outlier, i.e. identify inconsistent behaviors across different views.

Most recently, Alvarez et al. proposed a cluster-based multi-view anomaly detection algorithm [Alvarez et al., 2013]. By measuring the differences between each sample and its neighborhoods in different views, the outlier is detected. Four kinds of strategies are provided for anomaly scores estimation. Specifically, for each view, clustering is firstly performed. Then cluster-based affinity vectors are calculated for each sample. Similar to [Gao et al., 2011; 2013], this algorithm only detects the class-outliers, while our approach is able to detect both class- and attribute- outliers simultaneously by virtue of data representation.

3 DMOD: Dual-regularizedMulti-view Outlier Detection Method

In this section, before proposing our method, we introduce the preliminary knowledge of clustering indicator based formulation first. Based on that, we propose our novel Dualregularized Multi-view Outlier Detection (DMOD) method.

3.1 Preliminary Knowledge

The effectiveness of k-means clustering method has been well demonstrated in data representation with its objective using the clustering indicators as:

where X ∈ Rd×n is the input data with n samples and d dimensional features. Here, H ∈ Rd×K is known as the cluster centroid matrix, and G ∈ RK×n is cluster assignment matrix in latent space. Note that the sum of each column of G should equal one, because each data sample xl has to be assigned to one single cluster. Specifically, if xl is assigned to k-th cluster, then Gkl = 1, otherwise Gkl = 0, which is known as 1-of-K coding scheme. Although traditional k-means has a wide range of applications, it suffers from the vulnerability to outliers, especially for multi-view data [Bickel and Scheffer, 2004]. This derives one of our motivations to propose a robust outlier detection method for multi-view data.

3.2 The proposed DMOD

Inspired by the success of ℓ2,1-norm in feature selection [Nie et al., 2010] and error modeling [Liu et al., 2010], we propose a new dual-regularized multi-view outlier detection method for heterogeneous source data. We denote the sample set X = {X(1) , . . . ,X(i) , . . . ,X(V )}, where V is the number of views and X(i) ∈ Rdi×n . H(i) ∈ Rdi×K is the centroid matrix for i-th view. G(i) ∈ RK×n is the clustering indicator matrix for i-th view.

Then our model is formulated as:

where β is a trade-off parameter, Mij denotes the alignment matrix between two different views, and S(i) is the construction error for i-th each view.

Remark 1: Due to the heterogeneous data X(i) , different G(i) should be similar. Accordingly, a dual-regularization term ‖G(i) -MijG(j) ‖2F, (i ̸= j) is employed so as to align the indicator matrixes G(i) and G(j) in two different views. Recall that Gi and Gj are orderless clusters, which means even though they are exactly the same, ‖G(i) -G(j)‖2F cannot be zero without the alignment matrix Mij .

Remark 2: The ℓ2,1-norm is defined as ‖S‖2,1 = ∑nq=1 √∑dp=1 |Spq|2 , where |Spq| is the element of S in pth row and q-th column. Note that ℓ2,1-norm has the power to ensure the matrix sparse in row, making it particularly suitable for sample-specific anomaly detection. This robust representation solves the outlier sensitivity problem in Eq. (1). Consequently, the regularization term ‖S(i)‖2,1 is able to identify the attribute-outliers for i-th view.

Remark 3: In order to detect the class-outlier, i.e. sample inconsistent behaviour across different views, the inconsistency with respect to each view needs to be measured. We argue that the following representation ∑nk=1 G(i) kl G(j) kl in latent space can well quantify the inconsistency of sample l across different views i and j. The detailed illustration can be found in the following sub-section.

3.3 Outlier Measurement Criterion

We have discussed the ability of our method in characterizing two kinds of outliers. In order to make the quantitative estimation of inconsistency, we propose a novel outlier measurement function ϕ(l) for sample l as

where ‖ · ‖ denotes ℓ2-norm and γ is a trade-off parameter.

The criterion Eq. (3) helps us identify attribute-/class- outliers jointly. Take two-view as an example, the first termmeasures the anomaly of the l-th sample across view 1 and view 2. When the l-th sample behaves normally in both views, the coefficients in G(1) and G(2) should be consistent. Consequently, ∑nk=1 G(1) kl G(2) kl should be relatively large. In contrast, if the l-th sample behaves inconsistently, the coefficients G(1) and G(2) would result in a small value of the first term, which means it is a class-outlier.

The second term γ‖S(i) l ‖‖S(j) l ‖ identifies the attributeoutliers. If the l-th sample behaves normally in at least one view, γ‖S(1) l ‖‖S(2) l ‖ is close to zero, which means the overall score ϕ(l) will not decrease much by the second term. On the contrary, if the l-th sample is an attribute-outlier behaves abnormally in both views, the value of the second term increases, which leads to a decreased outlier score ϕ(l).

4 Optimization

So far we have proposed the dual-regularized outlier detection model with a quantitative outlier measurement criterion. In this section, we illustrate the optimization solution to problem (2). Obviously, it is hard to find the global optimizers, since it is not jointly convex with respect to all the variables. Thus, we employ inexact augmented Lagrange method (ALM) [Lin et al., 2009] to optimize each variable iteratively.

4.1 AlgorithmDerivation

There are two difficulties to solve the proposed objective. First, ℓ2,1-norm is non-smooth. Second, each element of the indicator matrix G(i) is a binary integer, and each column vector has to satisfy 1-of-K coding scheme.

By introducing the Lagrange multiplier Y (i) for each view, the augmented Lagrange function for problem (2) is written as:

where µ > 0 is the penalty parameter, and 〈·〉 denotes the inner product of two matrices, i.e. 〈A,B〉 = tr(ATB). Then we optimize the variables independently in an iterative manner. Specifically, the variables S(i) , H(i) , G(i) , and Mij are updated as follows:

Update S(i) : Fix H(i) , G(i) , Mij, the Lagrange function with respect to S(i) is written as:

which equalizes the following equation:

Here, ̂ S(i) = X(i) - H(i)G(i) + Y (i) µ . This term S(i) can be solved by the shrinkage operator [Yang et al., 2009].

Update H(i) : Fix S(i) , G(i) , and Mij , and take the derivative L with respect to H(i) , we get

Setting Eq. (7) as zero, we can update H(i) :

where G(i) † denotes the pseudo inverse of G(i) .

Update G(i) : Fix S(i) , H(i) , and Mij, update the cluster indicator matrix G(i) , we have

As mentioned above, G(i) satisfies 1-of-K coding scheme. We can solve the above problem by decoupling the data and determine each column g(i) m ∈ RK×1 one by one, where m is the specified column index and G(i) = [g(i) 1 , . . . , g(i) m , . . . , g(i) n ]. Thus for each g(i) m , it satisfies the following equation:

where g(j) m , y(i) m , s(i) m and x(i) m are the m-th column of matrix G(j) , Y (i) , S(i) and X(i) , respectively.

To find the solution of Eq. (10), we do an exhaustive search in the feasible solution set, which is composed of all the columns of identity matrix IK = [e1, e2, . . . , eK].

UpdateMij: Fix S(i) , H(i) and G(i) , update the alignment matrixMij between G(i) and G(j) as

Finally, the complete optimization algorithm to solve the problem in Eq. (2) is summarized in Algorithm 1. The initializations for each variable is also shown in the algorithm. The entire DMOD algorithm for multi-view outlier detection is outlined in Algorithm 2.

Algorithm 1. Optimization Solution of Problem (2)

Input: multi-view data X = {X(1) , . . . , X(K)},

parameter β, the expected number of classes K.

Initialize: Set iteration time t = 0

while not converged do

1. Fix the others and update S(i) via Eq. (6).
2. Fix the others and update H(i) via Eq. (8).
3. Fix the others and update each vector g(i) m of G(i) using Eq. (9) and (10).
4. Fix the others and update Mij using Eq. (11).
5. Update the multiplier Y (i) via Y (i) = Y (i) + µ(X(i) - H(i)G(i) - S(i) ).
6. Update the parameter µ by µ = min(ρµ, µmax).
7. Check the convergence condition by
8. ‖X(i) - H(i)G(i) - S(i)‖∞ < ϵ.
9. t = t +1.

end while

Output: S(i) ,H(i) ,G(i)

Algorithm 2. DMOD for Multi-view Outlier Detection

Input: Multi-view data X, parameter τ

1. Normalize data x(v) i by x(v) i = x(v) i /‖x(v) i ‖.
2. Solve problem (2) by Algorithm 1, and get the optimal G(v) and S(v) .
3. Compute the outlier scores for all samples by Eq. (3).
4. Generate the binary outlier label L, if ϕ(i) > τ , L(i) = 0; otherwise, L(i) = 1.

Output: Binary outlier label vector L.

4.2 Complexity Analysis

In this section, we make the time complexity analysis of our model. The most time-consuming parts of Algorithm 1 are the matrix multiplication and pseudo inverse operations in Step 2, 3 and 4. For each view and each iteration, the pseudo inverse operations in Eq. (8) and Eq. (11) take O(K2n + K3 ) in the worst case. Usually K ≪ n, then the asymptotic upper-bound for pseudo inverse operation can be expressed as O(K2n). The multiplication operations take O(dnK). Suppose L is the iteration time, V is the number of views. In general, the time complexity of our algorithm is O(LVK2n + LVKdn). It is worth noticing that L and V are usually much smaller than n. Thus we claim that our proposed method is linear time complexity with respect to the number of samples n.

5 Experiments

In this section, we collect five benchmark datasets to evaluate the performance. Among them, four are from UCI Machine Learning Repository 1 , i.e. iris, breast, ionosphere, and letter. The fifth one VisNir is from BUAA database [Di Huang and Wang, 2012]. Important statistics are tabulated in Table 1. To generate both types of outliers, we do data pre-processing as follows: for class-outlier, we follow the strategy in [Gao et al., 2011]: (a) split the object feature representation into two subsets, where each subset is considered as one view of the data; (b) take two objects from two different classes and swap the subsets in one view but not in the other. In order to generate attribute-outlier, we randomly select a sample, and replace its features in all views by random values.

We compare the proposed method with both the singleview and multi-view outlier detection baselines as follows:

• Direct Robust Matrix Factorization (DRMF) [Xiong et al., 2011] is a single-view outlier detection method which has demonstrated its superiority to several other single-view baselines, i.e. robust PCA [Cand`es et al., 2011], Stable Principal Component Pursuit [Zhou et al., 2010], and Outlier Pursuit [Xu et al., 2010].
• Low-Rank Representation (LRR) [Liu et al., 2012] is a representative outlier detection method for single-view data. There is a trade-off parameter balancing the lowrank term and error term, which we fine-tune in the range of [0.01, 1] and report the best result.
• HOrizontal Anomaly Detection (HOAD) [Gao et al., 2013] is a cluster-based outlier detection method identifying the inconsistency among multiple sources. Two parameters, i.e. edge-weight m and the number of classes k are fine-tuned to get the best performance.

1 http://archive.ics.uci.edu/ml/

• Anomaly detection using Affinity Propagation (AP) [Alvarez et al., 2013]. AP is the most recent outlier detection approach for multi-view data. Two affinity matrices and four anomaly measurement strategies are presented. In this paper, ℓ-2 distance and Hilbert-Schmidt Independence Criterion (HSIC) are used, since this combination usually performs better than others.

As suggested in [Alvarez et al., 2013; Liu et al., 2012], AUC is reported (area under Receiver Operating Characteristic (ROC) curve) as the evaluation metric. We also adopt ROC curve, representing the trade-off between hit rate and false alarm rate. The hit rate (TPR) and false alarm rate (FPR) are defined as:

where TP, FN, TN and FP represent true positives, false negatives, true negatives, and false positives, respectively.

5.1 UCI Databases

For each dataset, we strictly follow [Alvarez et al., 2013; Gao et al., 2011; 2013]. The outliers are firstly generated randomly for 50 times. Then the performance of each method is evaluated on those 50 sets. Finally the average results are reported. To simulate the real-world applications happening in different circumstances, we conduct three settings by mixing both outliers with different ratios: (1) 2% class-outlier of the total sample number + 8% attribute-outlier of the total sample number, represented in format "DatasetName-2-8"; (2) 5% class-outlier + 5% attribute-outlier in format "DatasetName5-5"; (3) 8% class-outlier + 2% attribute-outlier in format "DatasetName-8-2".

Table 2 reports the AUC values ( mean ± standard deviations) on four datasets with different outlier settings. Based on Table 2, we have the following observations and discussions.

• Our proposed method DMOD consistently outperforms all the other baselines in all settings.
• In most cases, single-view based methods have superior performance to multi-view based methods in outlier setting "DatasetName-2-8".
• In the experiments with setting "DatasetName-8-2", multi-view based methods perform better than singleview methods in most cases.

Discussion: All the observations are expected, as multi-view based methods are strong in dealing with the class-outliers, while single-view based methods are designed to identify the sample inconsistency in all views. By virtue of the dualregularized multi-view data representation, both class- and attribute- outliers are well characterized within the proposed DMOD model. Thus a stable and encouraging performance on UCI datasets has been observed. Specifically, in letter dataset, we raise the performance by around 26.13%.

5.2 BUAA-VisNir Database

We make another evaluation on the BUAA VisNir database, which consists of two types of data captured from visual spectral (VIS) and near infrared (NIR) sensors. There are 150 subjects, with the original image size of 287×287 pixels. In order to fasten the computation and keep the key features, we Figure 3: Convergence (red line) and AUC (blue line) curves with respect to iteration time on iris database with parameters β and γ setting as 0.5 and 0.1, respectively.

vectorize the images, and project the data matrix into 100dimension for each view by PCA. It is worth noticing that this pre-processing also helps remove the noise.

To generate 5% class-outliers and 5% attribute-outliers, the same strategies are employed as UCI datasets. Figure 2 and Table 3 show the ROC curves and the corresponding AUC values (mean ± standard deviation). It is observed that our approach also outperforms all other single-view and multiview outlier detection algorithms.

5.3 Convergence and Parameter Analysis

To testify the robustness and stability, we conduct four experiments to study the detection performance in terms of convergence and model parameters. Without explicit specification, all the experiments are conducted on iris dataset with the setting of 5% class-outliers and 5% attribute-outliers. Three parameters β, γ and K are set to 0.5, 0.1 and 3, respectively.

Convergence analysis. To show the convergence property, we compute the relative error of stop criterion ‖X(v) - H(v)G(v) -S(v)‖∞ in each iteration, the convergence curve of our model is drawn in red as shown in Figure 3. It is observed that the relative error drops steadily, and then meets the convergency at around #30 iteration. We also plot the average AUC during each iteration. From the observation, there are three stages before converging: the first stage (from #1 to #15), the AUC goes up steadily; second stage (from #16 to #30), the AUC bumps in a small range; the final stage (from #31 to the end), the AUC achieves the best at the convergence point. Note that our method might converge to the local minimum as k-means does, we employ the strategy to run each set of data 10 times to find the best optimizer.

Parameter analysis. There are three major parameters in our approach, i.e. β, γ and K. Figure 4(a) shows the experiment of outlier detection accuracy with respect to the parameter β under different outlier settings. We set the parameter β in the range of [0.1, 1.0] with the step of 0.1. It is observed that our method reaches the best when β equals 0.7 under different outlier settings, and generally the performance is quite stable in the range of [0.4, 0.9]. Thus in our experiments, we set parameter β = 0.5 as default.

The experiment shown in Figure 4(b) is designed to testify the robustness of our model in terms of parameter γ. Due to possible amplitude variations of two terms in Eq. 3, we evaluate γ within the following set {0, 10-3 , 10-2 , 10-1 , 100 , 101 , 102 }. As we observe, the average AUCs in three different settings are relatively steady when γ = {10-3 , 10-2 , 10-1 , 100 }. In practical, we choose γ = 0.1 as default for all experiments.

Another important parameter in our proposed model is the intrinsic dimension K in matrix factorization step. The intrinsic dimension K of iris dataset is 3 since it has three classes. Therefore we make the evaluation in the range of [1, 8]. The boxplot of average AUC is shown in Figure 5. It is easily observed that our proposed method works well when K is around the true intrinsic dimension, i.e. K is in the range of [2, 5]. However, when K is too small, the performance drops dramatically due to the information lost in the matrix decomposition step. When K is too large, i.e. K > 5, the AUC also drops because of introducing more noisy redundant information. Note that, same with [Gao et al., 2011], K is essential and varies depending on data. While we argue that instead of manually searching the best K for each dataset, we can utilize several off-the-shelf methods to predict K [Tibshirani et al., 2000]. A steady and robust performance has been verified as long as the predicted K is not far from the ground-truth.

6 Conclusion

In this paper, we proposed a novel dual-regularized multiview outlier detection method from the perspective of data representation, named DMOD. An outlier estimation criterion was also presented to measure the inconsistency of each data sample. We introduced an optimization algorithm to effectively solve the proposed objective based on 1-of-K coding scheme. Extensive experiments on four UCI datasets and one BUAA VisNir database with various outlier settings were conducted. The consistently superior results to four state-ofthe-arts demonstrated the effectiveness of our method.