Development of a Distributed Outlier Detection Method Based on the Alternating Direction Method of Multipliers

ADMM is a decomposition-coordination technique in which solutions to small local subproblems are coordinated to find the solution to a larger global problem [4]. Depending on the application, it is relatively simple to implement in distributed environments, making it applicable to big data problems [4, 10].

ADMM solves problems of the form: 1minimizef(x)+g(z)subject to: Ax+Bz=c

Where x ∈ ℝⁿ, z ∈ ℝ^m, A ∈ ℝ^p×n, B ∈ ℝ^p×m, and c ∈ ℝ^p. With f and g convex functions. The minimum value of problem (1) would be: p*=min(f(x)+g(z)∣Ax+Bz=c)

Where min refers to the minimum. The (augmented) Lagrangian for this problem would be: Lp(x,z,y)=f(x)+g(z)+yT(Ax+Bz−c)+ρ2‖Ax+Bz−c‖22

And the solution by ADMM consists of the iterations: 2xk+1:=argminxLp(x,zk,yk) 3zk+1:=argminzLp(xk+1,z,yk) 4yk+1:=yk+ρ(Axk+1+Bzk+1−c) with ρ > 0. As can be seen, the variables x and z are updated alternately, hence the name of the algorithm. The variable y is called the dual variable.

ADMM can be written in a different, often more convenient form, known as the scaled form: 5xk+1:=argminx(f(x)+ρ2‖ Ax+Bzk−c+uk ‖22) 6zk+1:=argminz(g(z)+ρ2‖ Axk+1+Bz−c+uk ‖22) 7uk+1:=uk+Axk+1+Bzk+1−c where u=1ρy . The dual variable is scaled.

Consensus problems are part of the field of distributed optimization and have historically been related to the ADMM. The consensus optimization problem consists of a single global variable with the objective and constraint terms divided into N parts: 8minimize∑i=1Nfi(xi)subject to: xi−z=0i=1…N

This is called the global consensus problem.

A common variation of the problem (8) is the introduction of a regularization term in the objective function g, which represents a regularization term: 9minimize∑i=1Nfi(xi)+g(z)subject to: xi−z=0i=1…N

The solution by ADMM to problem (9) would be (in the scaled form): 10xik+1:=argminxi(fi(xi)+ρ2‖ xi−zk+uik ‖22) 11zk+1:=argminz(g(z)+Nρ2‖ z−x¯k+1−u¯k ‖22) 12uik+1:=uik+xik+1−zk+1 where x_i are the local primal variables at each node, u_i are the local dual variables, z is the consensus (global) variable, and x¯ and u¯ are the averages of the primal and dual variables, respectively.

For ADMM with consensus, the residuals are in the form of vectors: rk=(x1k−zk,…,xNk−zk),sk=−ρ(zk−zk−1,…,zk−zk−1) whose quadratic norms are: ‖ rk ‖22=∑i=1N‖ xik−zk ‖22,‖ sk ‖22=Nρ2‖ zk−zk−1 ‖22

SVDD, proposed in [25], is an unsupervised learn-ing method that is very useful for data description and anomaly detection. To describe the dataset, this model finds a hypersphere that encloses most of the data, minimizing the possibility of accepting anoma-lous data within it.

SVDD is formulated as an optimization problem in the following way: Given a set of points x_i ∈ ℝ^d, i = 1…n: 13minimizeR,a,ξiR2+C∑i=1nξisubject to:‖ xi−a ‖2≤R2+ξi,i=1…nξi≥0,i=1…n

Where a is the center of the hypersphere, R is the radius, C is a control parameter, and ξ_i are slack variables. The distance from x_i to the center need not be less than or equal to R², and these large distances are penalized with margin errors ξ_i for each x_i. The parameter C controls the trade-off between the volume of the hypersphere and the errors, i.e., it controls the number of points included in the hypersphere.

Another approach to the data description problem can be found in [23,24]. Itis based on finding a hyperplane that separates the dataset from the origin with the maximum possible margin. The formulation would be: 14minimizew,ρ,ξi12‖w‖2−ρ+1vN∑i=1Nξisubject to: w·xi≥ρ−ξi∀iξi≥0

Where w is the weight vector of the hyperplane, ρ is the separation margin, x_i are the instances of the dataset, N is the number of instances, ξ_i are slack variables to account for possible errors, and v ∈ (0, 1) is a regularization parameter that indicates the fraction of data points that should be separated (equivalent to the C parameter). Because of this parameter, this method is known as v-SVC.

Although the hyperplane is not a closed boundary, it provides solutions comparable to the original SVDD problem when the data is preprocessed to unit norm [25].

Convex analysis methods have found increasing application in outlier detection and related areas. OCC can benefit from the robust algebraic and geometric approximations provided by convex analysis and optimization, allowing efficient solution computation through mathematical optimization [26].

Kernel Mean Matching (KMM) [13] is a method that assists in outlier detection by checking whether the training and test sets follow the same distribution. Its solution is formulated as a quadratic programming problem. A similar task to KMM can be performed with Least Square Importance Fitting (LSIF) [15]. In this case, it is also a quadratic programming problem directly related to the least squares problem.

The convex hull is one of the most commonly used convex analyses approaches in OD. This approach aims to find the smallest convex set that encloses a given set of points. Due to its inherent problem formulation, the convex hull has been used in OCC as a method for outlier detection [2,6].

In [8], the convex modeling of the SVDD prob-lem and its solution using Lagrange multipliers are analyzed. In addition, [23] presents an OCC based on support vector machines, where the model corresponds to a quadratic programming problem related to SVDD. These approaches are of interest in the present research.

In the field of convex optimization, many works focus on decomposition methods and decentralized algorithms [4,11,17], which naturally lend themselves to be approached from the perspective of distributed optimization algorithms.

When working with OD in big data, valuable information can be discovered and it is applicable in various domains. A fundamental challenge of OD in distributed systems is to minimize communication between nodes while maintaining the effectiveness of an algorithm [3]. In [14], an algorithm for OD based on data neighborhood is developed with a distributed and input stream focused approach. The algorithm is based on LOCI (Local Correlation Integral), which allows the detection of contextual outliers, i.e., instances that are considered outliers for a particular subset of the dataset. This work highlights the power of parallel processing for OD with input data streams.

In [22], an implementation for real-time OD using the PySpark variant of Spark for Python is proposed. In this work, the training data is stored in the cloud and a cluster-based solution is presented. Instances outside the formed clusters are considered outliers. The approach also includes a scheduler that periodically retrains the algorithm, allowing for reevaluation of decisions previously made on instances. Considering that distributed OD is a relatively unexplored area, [28] proposes Sparx, a new algorithm based on the xStream algorithm.

xStream was originally designed for a single processor, but this proposes a Map-Reduce design using Apache Spark in Python. The environment used does not exchange information between nodes, and the data is decentralized.

In [29,30], the Python library PyOD is proposed, which provides numerous OD algorithms. The library analyzes various characteristics of these algorithms, including their suitability for multicore processing. PyOD aims to provide a comprehensive set of OD techniques, making it easier for researchers and practitioners to experiment with and apply different outlier detection algorithms in Python.

The minimizations are performed using gradients (or subgradients if necessary) and would be as follows: 21wik+1=wk−uik+1α1∑j=1NIwixij<ρik(wi)xij where IA(x)={ 1,x∈A0,x∉A 22ρik+1={ ρk−vik,ρk−vik≤min(a→)ρk−vik−Nα2,ρk−vik−Nα2>max(a→)ρk−vik−Ntα2, otherwise 23wk+1=Jα11λ+Jα1(w¯k+1+u¯k) 24ρ=12λα2J+(ρ¯k+1+v¯k) 25uik+1:=uik+wik+1−wk+1 26vik+1:=vik+ρik+1−ρk+1

Based on the proposed updates, the solution algorithm would be as shown in Algorithm 1:

The variable stop models the proposed stopping conditions. The most general condition is the maximum number of iterations, which ensures that the algorithm stops.

It also checks whether the residuals do not exceed a tolerance value that combines absolute and relative variants. Finally, an early stopping criterion is introduced, where the algorithm is stopped if there is no improvement of the best value obtained so far for a given number of iterations.

Given the characteristics of consensus ADMM for the distributed architecture, one node should be used where the results are centralized and aggregated. The flow of the algorithm in each iteration would be to update the parameters w_i and b_i at each node independently using its own dataset and the values of w, b and the dual variables from the previous iteration. Once the w_i and b_i values of each node have been obtained, they are centralized and aggregated synchronously to give the w and b of the current iteration. Finally, the dual variables are updated. This workflow was implemented using a mapreduce methodology.

To evaluate the performance of the algorithm, we use five datasets: three synthetic, and two real. These datasets vary in the number of instances and dimensions. The synthetic datasets are generated based on probability distributions in the plane, which facilitates the construction of graphs to understand the behavior of the algorithm. The datasets are distributed equitably among the processing nodes.

Table 1 briefly describes the five datasets, the instances row defines the total number of elements in each dataset, while the outliers row defines how many of those instances are anomalous. The three synthetic sets corresponding to Experiments 1, 2 and 3 are constructed in the same way, the instances are (x,y) coordinates where most of the data is uniformly distributed around the points (-2,-2) and (2,2) with radius 1. The rest of the instances are normally distributed around the points (-2,-2) and (2,2) with radius 1. The remaining instances are normally distributed in the rectangle defined from (-4,-4) to (4,4) and are considered anomalous. Experiment 4 is performed on the Glass dataset, which has nine continuous features related to the concentrations of metals in the material. It is initially a classification problem with six classes, but class number 6 is in the minority and instances belonging to this class are considered anomalous.¹ Experiment 5 is carried out with a real dataset related to behavior reports for a physical system: Statlog (shuttle). For the experiments, a version is taken in which the main task is to distinguish the reports that are considered anomalous from those that are not.²

Preprocess The main step in data preprocessing is the use of the Nystroem approximation [19,27]. This step not only helps to reduce the dimensionality of the kernel matrix, but also allows for modeling the nonlinearity of the data. The kernel used is the Radial Basis Function (RBF) kernel [20].

In the experiments conducted, it was also found to be effective to scale the values before applying the kernel. For this purpose, the Robust Scaler from scikitlearn is used, which is more effective than standard scaling because the Robust Scaler is not sensitive to the presence of outliers [19].

Other common preprocessing steps can also apply if necessary, such as data type transformation and missing value handling [16].

The same methodology was used for all experiments: A labeled dataset is taken, with one class representing the outliers. The labels are stored and removed from the dataset. The classifier is trained on the unlabeled data, then used to classify the data, and the performance is evaluated using the original stored labels.

This process is performed for three One Class Support Vector Machine classifiers, two of which are available in the scikitlearn library: OCSVM and SGD-OC. The third classifier is the one proposed in this research (called ADMM-oc).

Another important aspect is that for the ADMM-oc and SGD-oc methods the data shown in the AUC-ROC in Table 1 are the result of the average of 10 runs in the first four experiments and 5 runs in the fifth experiment. This process is done because both methods are stochastic.

The OD problem can be viewed as a two-class classification problem, where one class represents the outliers and the other class represents the “normal” instances [21]. Even methods that return a score or degree can be reduced to a two-class problem by set-ting a threshold for the data, above which they are considered anomalous [7]. Therefore, scoring metrics for binary classification problems are valid. An important consideration is the typical class imbalance in such problems, which may cause certain metrics to be unrepresentative of the quality of a given algorithm. Therefore, the AUC-ROC metric is evaluated because it is not sensitive to imbalanced data [9,12].

Table 1 presents the results of the experiments, with a description of the datasets and some parameters used for each experiment. It can be observed that the AUC-ROC values remain similar to the other two methods compared, regardless of the variation in the datasets.

During Experiment 2, studies were conducted to verify the algorithm’s convergence. The results showed that the ADMM-OC algorithm achieves good convergence within a maximum of 20 iterations, as can be seen in Figures 1 and 2.

Figure 1.

Convergence Analysis

Figure 2.

Residuals and Tolerances

Considering the two-dimensionality of the dataset used in Experiment 3, a comparison of the contour plots of the classifiers is proposed in Figure 3. As can be observed, the contour plots are almost identical, which supports the similar AUC-ROC values obtained.

Figure 3.

Countour Lines

Visually the outermost contour line would repre-sent the boundary between anomalous and normal instances.

Based on the experimental study, it can be con-cluded that the algorithm maintains good effectiveness compared to other similar methods. The influence of data preprocessing, particularly the Nystroem approximation, on the performance of the algorithm was observed. For two-dimensional datasets, the results were evaluated graphically, visually confirming the effectiveness values obtained. Finally, a detailed analysis of the algorithm’s iterations allowed verification of aspects related to convergence and the consensus process.