# A Distributed Algorithm for the Cluster-Based Outlier Detection Using Unsupervised Extreme Learning Machines

Authors: Xite Wang; Mei Bai; Derong Shen; Tiezheng Nie; Yue Kou; Ge Yu
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

Outlier detection is an important data mining task, whose target is to find the abnormal or atypical objects from a given dataset. The techniques for detecting outliers have a lot of applications, such as credit card fraud detection and environment monitoring. Our previous work proposed the Cluster-Based (CB) outlier and gave a centralized method using unsupervised extreme learning machines to compute CB outliers. In this paper, we propose a new distributed algorithm for the CB outlier detection (DACB). On the master node, we collect a small number of points from the slave nodes to obtain a threshold. On each slave node, we design a new filtering method that can use the threshold to efficiently speed up the computation. Furthermore, we also propose a ranking method to optimize the order of cluster scanning. At last, the effectiveness and efficiency of the proposed approaches are verified through a plenty of simulation experiments.


---

## Body

## 1. Introduction

Outlier detection is an important issue of data mining, and it has been widely studied by many scholars for years. According to the description in [1], “an outlier is an observation in a dataset which appears to be inconsistent with the remainder of that set of data.” The techniques for mining outliers can be applied to many fields, such as credit card fraud detection, network intrusion detection, and environment monitoring.There exist two primary missions in the outlier detection. First, we need to define what data are considered as outliers in a given set. Second, an efficient method to compute these outliers needs to be designed. The outlier problem is first studied by the statistics community [2, 3]. They assume that the given dataset follows a distribution, and an object is considered as an outlier if it shows distinct deviation from this distribution. However, it is almost an impossible task to find an appropriate distribution for high-dimensional data. To overcome the drawback above, some model-free approaches are proposed by the data management community. Examples include distance-based outliers [4–6] and the density-based outlier [7]. Unfortunately, although these definitions do not need any assumption on the dataset, some shortcomings still exist in them. Therefore, in this paper, we propose a new definition, the Cluster-Based (CB) outlier. The following example discusses the weaknesses of the existing model-free approaches and the motivation of our work.As Figure1 shows, there are a denser cluster C1 and a sparse cluster C2 in a two-dimensional dataset. Intuitively, points p1 and p2 are the outliers because they show obvious differences from the other points. However, in the definitions of the distance-based outliers, a point p is marked as an outlier depending on the distances from p to its k-nearest neighbors. Then, most of the points in the sparse cluster C2 are more likely to be outliers, whereas the real outlier p1 will be missed. In fact, we must consider thelocalization of outliers. In other words, to determine whether a point p in a cluster C is an outlier, we should only consider the points in C, since the points in the same cluster usually have similar characters. Therefore, in Figure 1, p1 from C1 and p2 from C2 can be selected correctly. The density-based outlier [7] also considers the localization of outliers. For each point p, they use the Local Outlier Factor (LOF) to measure the degree of being an outlier. To compute the LOF of p, we need to find the set of its k-nearest neighbors nnk(p) and all the k-nearest neighbors of each point in nnk(p). The expensive computational cost limits the practicability of the density-based outlier. Therefore, we propose the CB outlier to conquer the above deficiencies. The formal definition will be described in Section 3.Figure 1
Example of outliers.To detect CB outliers in a given set, the data need to be clustered first. In this paper, we employ the unsupervised extreme learning machine (UELM) [8] for clustering. The extreme learning machine (ELM) is a novel technique proposed by Huang et al. [9–11] for pattern classification, which shows better predicting accuracy than the traditional Support Vector Machines (SVMs) [12–15]. Thus far, the ELM techniques have attracted the attention of many scholars and various extensions of ELM have been proposed [16]. UELM [8] is designed for dealing with the unlabeled data, and it can efficiently handle clustering tasks. The authors show that UELM provides favorable performance compared with the state-of-the-art clustering algorithms [17–20].In [21], we have studied the problem of CB outlier detection using UELM in a centralized environment. Faced with the increasing data scale, the performance of the centralized method becomes too limited to meet the timeliness requirements. Therefore, in this paper, we develop a new efficient distributed algorithm for the CB outlier detection (DACB). The main contributions are summarized as follows:(1)
We propose a framework of distributed CB outlier detection, which adopts a master-slave architecture. The master node keeps monitoring the points with large weights on each slave node and obtains a thresholdLB. The slave nodes can use LB to efficiently filter the unpromising points and accelerate the computational efficiency.(2)
We propose a new algorithm to compute the point weights on each slave node. Compared with our previous method in [21], the new algorithm adopts a filtering technique to further improve the efficiency. We can filter out a large number of unpromising points, instead of computing their exact weights.(3)
We propose a new method to optimize the order of cluster scanning on each slave node. With the help of this method, we can obtain a largeLB early and improve the filtering performance.The rest of the paper is organized as follows. Section2 gives brief overviews of ELM and UELM. Section 3 formally defines the CB outlier. Section 4 gives the framework of DACB. Section 5 illustrates the details of DACB. Section 6 analyzes the experimental results. Section 7 gives the related work of outlier detection. Section 8 concludes the paper.


## 2. Preliminaries

### 2.1. Brief Introduction to ELM

The target of ELM is to train a single layer feedforward network from a training set withN samples, {X,Y}={xi,yi}i=1N. Here, xi∈Rd, and yi is an M-dimensional binary vector where only one entry is “1” to represent the class that xi belongs to.The training process of ELM includes two stages. In the first stage, we build the hidden layer withL nodes using a number of mapping neurons. In detail, for the jth hidden layer node, a d-dimensional vector aj and a parameter bj are randomly generated. Then, for each input vector xi, the relevant output value on the jth hidden layer node can be acquired using an activation function such as the Sigmoid function below:(1)gxi,aj,bj=11+exp⁡-ajT×xi+bj.Then, the matrix outputted by the hidden layer is(2)H=gx1,a1,b1⋯gx1,aL,bL⋮⋮gxN,a1,b1⋯gxN,aL,bLN×L.In the second stage, anM-dimensional vector βj is the output weight that connects the jth hidden layer with the output node. The output matrix Y is acquired by (3)H·β=Y,where(4)β=β1⋮βLL×M,Y=y1⋮yNN×M.We have known the matricesH and Y. The target of ELM is to solve the output weights β by minimizing the square losses of the prediction errors, leading to the following equation:(5)
m
i
n
β
∈
R
L
×
M
L
E
L
M
=
1
2
β
2
+
C
2
Y
-
H
β
2
s
.
t
.
H
β
=
Y
-
e
,where · denotes the Euclidean norm, e=Y-Hβ=e1T,…,eNT∈RN×M is the error vector with respect to the training samples, and C is a penalty coefficient on the training errors. The first term in the objective function is a regularization term against overfitting.IfN≥L, which means H has more rows than columns and it is full of column rank, (6) is the solution for (5). Hence,(6)β∗=HTH+ILC-1HTY.IfN<L, a restriction that β is a linear combination of the rows of H: β=HTαα∈RN×M is considered. Then, β can be calculated by (7)β∗=HTα∗=HTHHT+INC-1Y,where IL and IN are the identity matrices of dimensions L and N, respectively.


### 2.2. Unsupervised ELM

Huang et al. [8] proposed UELM to process an unsupervised dataset, which shows good performance in clustering tasks. The unsupervised learning is based on the following assumption: if two points x1 and x2 are close to each other, their conditional probabilities Py∣x1 and Py∣x2 should be similar. To enforce this assumption on the data, we acquire the following equation:(8)Lm=12∑i,jwijPy∣xi-Py∣xj2,where wij is the pairwise similarity between xi and xj, which can be calculated by Gaussian function exp⁡(-xi-xj2/2σ2).Since it is difficult to calculate the conditional probabilities, the following can approximate (8):(9)L^m=TrY^TLY^,where Tr(·) denotes the trace of a matrix, Y^ is the predictions of the unlabeled dataset, L=D-W is known as graph Laplacian, and D is a diagonal matrix with its diagonal elements Dii=∑j=1uwij.In the unsupervised learning, the datasetX=xii=1N is unlabeled. Substituting (9) into (5), the objective function of UELM is acquired:(10)minβ∈RL×Mβ2+λTrβTHTLHβ,where λ is a tradeoff parameter. In most cases, (10) reaches its minimum value at β=0. In [18], Belkin and Niyogi introduced an additional constraint (Hβ)THβ=IM. On the base of the conclusion in [8], if L≤N, we can obtain the following equation:(11)IL+λHTLHv=γHTHv.Letγi be the ith smallest eigenvalues of (11) and vi be the corresponding eigenvectors. Then, the solution of the output weights β is given by(12)β∗=v~2,v~3,…,v~M+1,where v~i=vi/Hvi,  i=2,…,M+1, are the normalized eigenvectors.IfL>N, (11) is underdetermined. We obtain the alternative formulation below:(13)IN+λLHHTu=γHHTu.Again, letui be the generalized eigenvectors corresponding to the ith smallest eigenvalues of (13). Then, the final solution is(14)β∗=HTu~2,u~3,…,u~M+1,where u~i=u~i/HHTu~i,  i=2,…,M+1, are the normalized eigenvectors. Algorithm 1 shows the process of UELM.Algorithm 1:UELM algorithm [8].
Input. The training data: X∈RN×d.
Output. The label vector of cluster yi corresponding to xi
(1) (a) Construct the graph Laplacian L of X;
(2) (b) Generate a pair of random values {ai,bi} for each hidden neuron,
and calculate the output matrixH∈RN×L;
(3) (c)
(4) ifL≤Nthen
(5)   Find the generalized eigenvectors v2,…,vM+1 of Equation (11). Let
β=v~2,v~3,…,v~M+1.
(6) else
(7)   Find the generalized eigenvectors u2,…,uM+1 of Equation (13). Let
β=HTu~2,u~3,…,u~M+1;
(8) (d) Calculate the embedding matrix: E=Hβ;
(9) (e) Treat each row of E as a point, and cluster the N points into K
clusters using thek-means algorithm. Let Y be the label
vector of cluster index for all the points.
(10) returnY;


## 2.1. Brief Introduction to ELM

The target of ELM is to train a single layer feedforward network from a training set withN samples, {X,Y}={xi,yi}i=1N. Here, xi∈Rd, and yi is an M-dimensional binary vector where only one entry is “1” to represent the class that xi belongs to.The training process of ELM includes two stages. In the first stage, we build the hidden layer withL nodes using a number of mapping neurons. In detail, for the jth hidden layer node, a d-dimensional vector aj and a parameter bj are randomly generated. Then, for each input vector xi, the relevant output value on the jth hidden layer node can be acquired using an activation function such as the Sigmoid function below:(1)gxi,aj,bj=11+exp⁡-ajT×xi+bj.Then, the matrix outputted by the hidden layer is(2)H=gx1,a1,b1⋯gx1,aL,bL⋮⋮gxN,a1,b1⋯gxN,aL,bLN×L.In the second stage, anM-dimensional vector βj is the output weight that connects the jth hidden layer with the output node. The output matrix Y is acquired by (3)H·β=Y,where(4)β=β1⋮βLL×M,Y=y1⋮yNN×M.We have known the matricesH and Y. The target of ELM is to solve the output weights β by minimizing the square losses of the prediction errors, leading to the following equation:(5)
m
i
n
β
∈
R
L
×
M
L
E
L
M
=
1
2
β
2
+
C
2
Y
-
H
β
2
s
.
t
.
H
β
=
Y
-
e
,where · denotes the Euclidean norm, e=Y-Hβ=e1T,…,eNT∈RN×M is the error vector with respect to the training samples, and C is a penalty coefficient on the training errors. The first term in the objective function is a regularization term against overfitting.IfN≥L, which means H has more rows than columns and it is full of column rank, (6) is the solution for (5). Hence,(6)β∗=HTH+ILC-1HTY.IfN<L, a restriction that β is a linear combination of the rows of H: β=HTαα∈RN×M is considered. Then, β can be calculated by (7)β∗=HTα∗=HTHHT+INC-1Y,where IL and IN are the identity matrices of dimensions L and N, respectively.


## 2.2. Unsupervised ELM

Huang et al. [8] proposed UELM to process an unsupervised dataset, which shows good performance in clustering tasks. The unsupervised learning is based on the following assumption: if two points x1 and x2 are close to each other, their conditional probabilities Py∣x1 and Py∣x2 should be similar. To enforce this assumption on the data, we acquire the following equation:(8)Lm=12∑i,jwijPy∣xi-Py∣xj2,where wij is the pairwise similarity between xi and xj, which can be calculated by Gaussian function exp⁡(-xi-xj2/2σ2).Since it is difficult to calculate the conditional probabilities, the following can approximate (8):(9)L^m=TrY^TLY^,where Tr(·) denotes the trace of a matrix, Y^ is the predictions of the unlabeled dataset, L=D-W is known as graph Laplacian, and D is a diagonal matrix with its diagonal elements Dii=∑j=1uwij.In the unsupervised learning, the datasetX=xii=1N is unlabeled. Substituting (9) into (5), the objective function of UELM is acquired:(10)minβ∈RL×Mβ2+λTrβTHTLHβ,where λ is a tradeoff parameter. In most cases, (10) reaches its minimum value at β=0. In [18], Belkin and Niyogi introduced an additional constraint (Hβ)THβ=IM. On the base of the conclusion in [8], if L≤N, we can obtain the following equation:(11)IL+λHTLHv=γHTHv.Letγi be the ith smallest eigenvalues of (11) and vi be the corresponding eigenvectors. Then, the solution of the output weights β is given by(12)β∗=v~2,v~3,…,v~M+1,where v~i=vi/Hvi,  i=2,…,M+1, are the normalized eigenvectors.IfL>N, (11) is underdetermined. We obtain the alternative formulation below:(13)IN+λLHHTu=γHHTu.Again, letui be the generalized eigenvectors corresponding to the ith smallest eigenvalues of (13). Then, the final solution is(14)β∗=HTu~2,u~3,…,u~M+1,where u~i=u~i/HHTu~i,  i=2,…,M+1, are the normalized eigenvectors. Algorithm 1 shows the process of UELM.Algorithm 1:UELM algorithm [8].
Input. The training data: X∈RN×d.
Output. The label vector of cluster yi corresponding to xi
(1) (a) Construct the graph Laplacian L of X;
(2) (b) Generate a pair of random values {ai,bi} for each hidden neuron,
and calculate the output matrixH∈RN×L;
(3) (c)
(4) ifL≤Nthen
(5)   Find the generalized eigenvectors v2,…,vM+1 of Equation (11). Let
β=v~2,v~3,…,v~M+1.
(6) else
(7)   Find the generalized eigenvectors u2,…,uM+1 of Equation (13). Let
β=HTu~2,u~3,…,u~M+1;
(8) (d) Calculate the embedding matrix: E=Hβ;
(9) (e) Treat each row of E as a point, and cluster the N points into K
clusters using thek-means algorithm. Let Y be the label
vector of cluster index for all the points.
(10) returnY;


## 3. Defining CB Outliers

For a given datasetP in a d-dimensional space, a point p is denoted by p=p1,p2,…,pd. The distance between two points p1 and p2 is dis(p1,p2)=∑i=1d(p1[i]-p2[i])2. Suppose that there are m clusters C1,C2,…,Cm in P outputted by UELM. For each cluster Ci, the centroid point Ci.centr can be computed by the following equation:(15)Ci.centri=∑p∈CipiCi.Intuitively, in a clusterC, most of thenormal points are closely around the centroid point of C. In contrast, anabnormal point p (i.e., outlier) is usually far from the centroid point and the number of points close to p is quite small. Based on this observation, the weight of a point is defined as follows.Definition 1 (weight of a point).
Given an integerk, for a point p in cluster C, one uses nnk(p) to denote the set of the k-nearest neighbors of p in C. Then, the weight of p is(16)wp=disp,C.centr×k∑q∈nnkpdisq,C.centr.Definition 2 (result set of CB outlier detection).
For a datasetP, given two integers k and n, let RCB be a subset of P with n points. If, ∀p∈RCB, there is no point q∈P∖RCB that w(q)>w(p), RCB is the result set of CB outlier detection.For example, in Figure1, in cluster C2, the centroid point is marked in red. For k=2, the k-nearest neighbors of p2 are p4 and  p5. Because p2 is an abnormal point and it is far from the centroid point, dis(C2.centr,p2) is much larger than dis(C2.centr,p4) and dis(C2.centr,p5). Hence, the weight of p2 is large. In contrast, for a normal point p3 deep in the cluster, the distances from C2.centr to its k-nearest neighbors are similar to dis(C2.centr,p3). The weight of p3 is close to 1. Therefore, p2 is more likely to be considered as a CB outlier.


## 4. Framework of Distributed CB Outlier Detection

The target of this paper is to detect CB outliers in a distributed environment, which is constituted by a master node and a number of slave nodes. The master node is the coordinator, and it can communicate with all the slave nodes. Each slave node reserves a subset of the clusters inP outputted by UELM, and it is the main worker in the outlier detection. Figure 2 shows the framework of the distributed algorithm for CB outlier detection (DACB) proposed in this paper.Figure 2
The framework of DACB.When a request of outlier detection arrives, each slave node starts to scan the local clusters. Basically, in a clusterC, we need to search the kNNs of each point p in C to compute the weight of p. Obviously, computing the kNNs of all the points is very time-consuming. Therefore, in our DACB, we propose a filtering method to accelerate the computation. Specifically, each slave node keeps tracking the local top-n points with the largest weights in the scanned points and sends them to the master node. From the received points, the master reserves the global top-n points with the largest weights. We choose the smallest one from these n weights as a threshold LB. The master broadcasts LB to the slave nodes to efficiently filter the unpromising points (the detailed filtering method is described in Section 5.1). On each slave node, if there emerges a point with weight larger than LB, the point will be sent to the master. The master termly updates the global top-n points and the threshold LB. At last, the n points stored in the master node are the CB outliers.


## 5. DACB Description

### 5.1. The Computation of Point Weight

In this section, we introduce the techniques to compute the point weights on each slave node. According to Definitions1 and 2, to determine whether a point p in a cluster C is an outlier, we need to search the k-nearest neighbors (kNNs) of p in C. In order to accelerate the kNN searching, we design an efficient method to prune the searching space.For a clusterC, suppose that the points in C have been sorted according to the distances to the centroid point in an ascending order. For a point p in C, we scan the points to search to its kNNs. Let nnktemp(p) be the set of k points that are the nearest to p from the scanned points, and let kdistemp(p) be the maximum value of the distances from the points in nnktemp(p) to p. Then, the pruning method is described as follows.Theorem 3.
For a pointq in front of p, if dis(q,C.centr)<dis(p,C.centr)-kdistemp(p), the points in front of q and q itself cannot be the kNNs of p.Proof.
For a pointq′ in front of q, because the points in C have been sorted, dis(q′,C.centr)<dis(q,C.centr). Then, according to the triangle inequality, the distance from q′ to p: dis(q′,p)>dis(p,C.centr)-dis(q′,C.centr)>dis(p,C.centr)-dis(q,C.centr)>dis(p,C.centr)-(dis(p,C.centr)-kdistemp(p))=kdistemp(p). Clearly, there exist k points closer to p than q′, and thus q′ cannot be the kNN of p.Similarly, for a pointq at the back of p, if dis(q,C.centr)>dis(p,C.centr)+kdistemp(p), the points at the back of q and q itself cannot be the kNNs of p. For example, Figure 3 shows a portion of points in a cluster C. First, we sort the points according to the distances to the centroid point and obtain a point sequence p9,  p7,  p5,  p3,  p1,  p,  p2,  p4,  p6,  p8. For point p, we search its kNNs from p to both sides (k=2). After p1,  p2, and  p3 are visited, p1 and p3 are the current top-k nearest neighbors for p, and thus kdistemp(p)=dis(p,p1). When we visit p4, dis(p4,C.centr)>dis(p,C.centr)+kdistemp(p). Hence, the points behind p4 in the sequence (i.e., p4,p6,p8) cannot be the kNNs of p. Similarly, when p5 is visited, we do not need to further scan the points before p5 in the sequence because dis(p5,C.centr)<dis(p,C.centr)-kdistemp(p). Therefore, the kNN searching stops, and the exact kNNs of p are p1 and p3.Figure 3
Example ofkNN searching.Furthermore, after the weights of some points have been computed, we send the current top-n points with the largest weights to the master node to obtain the threshold LB (mentioned in Section 4). We can use LB to filter the points that cannot be the CB outliers, instead of searching the exact kNNs. The detailed method is stated as follows.Theorem 4.
In thekNN searching of p in a cluster C, nnktemp(p) is the set of the current k-nearest neighbors of p from the scanned points. nnk(p) is the set of the exact k-nearest neighbors. One sorts the points in nnk(p) and nnktemp(p) according to the distances to p in an ascending order, respectively. Then, for the ith point in nnk(p): q and the ith point in nnktemp(p): q′, one asserts that dis(q,C.centr)>dis(p,C.centr)-dis(p,q′).Proof.
Ifq and q′ are the same point, the theorem can be proven easily. Otherwise, dis(p,q)<dis(p,q′). Using the triangle inequality, dis(q,C.centr)>dis(p,C.centr)-dis(p,q)>dis(p,C.centr)-dis(p,q′). The theorem is proven.Corollary 5.
For a pointp, if the current k-nearest neighbor set nnktemp(p) meets the following condition, p cannot be the CB outlier:(17)disp,C.centr×k∑q∈nnktemppdisp,C.centr-disp,q≤LB.Proof.
If (17) holds, the weight upper bound of p is smaller than or equal to LB according to Theorem 4. Therefore, p is not a CB outlier.By utilizing Corollary5, a large number of points can be filtered out safely, and we do not need to compute the exact kNNs of them. For example, in Figure 4, for k=2, we search the kNNs of q. After q1,  q2, and  q3 are visited, the current k-nearest neighbors are q1 and q3. dis(C.centr,q)×k/(2×dis(C.centr,q)-dis(q1,q)-dis(q3,q))≈1.57<LB. Then, we can assert that q is not a CB outlier even if the exact kNNs are not found. Therefore, q can be filtered out safely.Figure 4
Example of filtering.Algorithm2 shows the process of CB outlier detection on each slave node. For each cluster Ci in SETS, the points in Ci are sorted according to the distances to the centroid point in an ascending order (line (2)). Then, we scan the points in reversed order (line (3)), since the points far from the centroid point are more likely to have large weights and a good threshold LB can be obtained early. For each scanned point p, we visit the points from p to both sides to search the kNNs (line (8)). If the visited point q meets Theorem 3, a number of points can be erased from the visited list since they cannot be the kNNs of p (lines (10)–(13)). If the current kNNs of p meet Corollary 5, p is not an outlier, so we do not further search its kNNs (lines (16)–(18)). After all points are visited, we send p to the master node if p is still not filtered out (lines (19) and (20)). At last, the n points on the master node are the CB outliers.Algorithm 2:CB outlier detection on each slave node.
Input. The cluster set SETS reserved on slave node S, integers k, n, the threshold LB
Output. The CB outliers in P
(1) for each cluster Ci in SETSdo
(2)   Sort the points in Ci according to the distances to the centroid point
in ascending order;
(3)   Scan the points in reversed order;
(4)   for each scanned point pdo
(5)    Initialize a heap nn; // to reserve the current kNNs of p
(6)    kdistemp=∞; // the largest distance from the points in nn to p
(7)   boolean potential_outlier = true;
(8)   Visit the points from p to the both sides to search p’s kNNs;
(9)   for each visited point qdo
(10)      ifq is before p and
dis(q,C.centr)<dis(p,C.centr)-kdistempthen
(11)       Erase the points before q from the visited list;
(12)      else ifq is behind p and
dis(q,C.centr)>dis(p,C.centr)+kdistempthen
(13)       Erase the points behind q from the visited list;
(14)      else
(15)       Update nn and kdistemp;
(16)      ifnn meets the condition of Corollary 5then
(17)       potential_outlier = false;
(18)       break
(19)    ifpotential_outlierthen
(20)     Send p to the master node to update LB;


### 5.2. The Order of Cluster Scanning

As Section4 describes, each slave node needs to visit the local clusters one by one, and it computes the weights of points in each visited cluster. Meanwhile, the global top-n points with the largest weights thus far are kept in order to obtain the threshold LB. Clearly, the filtering effectiveness can be significantly improved if we obtain a large LB early, whereas a large LB is unlikely to be obtained if we visit the clusters in a random order, because we cannot guarantee that the early scanned points have large weights. As a consequence, we design a new ranking method for the clusters. Figure 5 illustrates the main idea of the ranking method.Figure 5
The ranking method of clusters.
(a)
A sparse cluster
(b)
A dense clusterA common idea is that points with large weights possibly emerge in a sparse cluster (the distance between every two points is large). However, this idea does not work well in many cases. For example, in Figure5(a), the distances from the points to the centroid point in the sparse cluster are almost identical, and thus the weights of these points are not large. However, in Figure 5(b), in the dense cluster, although most of the points are very close, two abnormal points q1 and  q2 are far from the centroid point, whose weights are large and suitable for the LB computation. From the observation in Figure 5(b), we can see that the distances of the points with large weights to the centroid point are large and quite different with those of the other points. Besides, note that we only need n large weights to compute LB. based on the description above, we propose the following ranking method.Definition 6 (the outlier factor of a cluster).
For a clusterC, suppose that the points have been sorted according to the distance to C.centr in a descending order. One uses dis0C to denote the distance between the first point and C.centr and disnC to denote the distance between the (n+1)th point and C.centr. Then, the outlier factor of C is(18)OFC=disnCdis0C.For example, in Figure5(a), n=2, which means we consider at most 2 points in a cluster to obtain LB. Thus, we sort the points according to the distance to C1.centr in a descending order, and we obtain the top-3 points, p1,  p2, and  p3. Then, we compute the distance between the first point p1 and C1.centr: dis(p1,C1.centr), and the distance between the third point p3 and C1.centr: dis(p3,C1.centr). The outlier factor of C1 is OF(C1)=dis(p3,C1.centr)/dis(p1,C1.centr)=0.95. Similarly, we get OF(C2)=dis(q3,C2.centr)/dis(q1,C2.centr)=0.5. Comparing the two outlier factors, we can see that OF(C1) is large, which means many points are far from C1.centr and they have similar distances to C1.centr. Therefore, we can hardly know whether there are points with large weights in C1. Conversely, the value of OF(C2) is small. We can assert that, in C2, most of the points closely surround the centroid point and there is at least one abnormal point (e.g., p1, p2) far from C2.centr. The weights of these abnormal points are large, and they contribute to selecting a large LB.As a consequence, we preferentially visit the clusters with small outlier factors, instead of visiting in a random order. This method helps us to obtain a largeLB early and improves the filtering effectiveness.


## 5.1. The Computation of Point Weight

In this section, we introduce the techniques to compute the point weights on each slave node. According to Definitions1 and 2, to determine whether a point p in a cluster C is an outlier, we need to search the k-nearest neighbors (kNNs) of p in C. In order to accelerate the kNN searching, we design an efficient method to prune the searching space.For a clusterC, suppose that the points in C have been sorted according to the distances to the centroid point in an ascending order. For a point p in C, we scan the points to search to its kNNs. Let nnktemp(p) be the set of k points that are the nearest to p from the scanned points, and let kdistemp(p) be the maximum value of the distances from the points in nnktemp(p) to p. Then, the pruning method is described as follows.Theorem 3.
For a pointq in front of p, if dis(q,C.centr)<dis(p,C.centr)-kdistemp(p), the points in front of q and q itself cannot be the kNNs of p.Proof.
For a pointq′ in front of q, because the points in C have been sorted, dis(q′,C.centr)<dis(q,C.centr). Then, according to the triangle inequality, the distance from q′ to p: dis(q′,p)>dis(p,C.centr)-dis(q′,C.centr)>dis(p,C.centr)-dis(q,C.centr)>dis(p,C.centr)-(dis(p,C.centr)-kdistemp(p))=kdistemp(p). Clearly, there exist k points closer to p than q′, and thus q′ cannot be the kNN of p.Similarly, for a pointq at the back of p, if dis(q,C.centr)>dis(p,C.centr)+kdistemp(p), the points at the back of q and q itself cannot be the kNNs of p. For example, Figure 3 shows a portion of points in a cluster C. First, we sort the points according to the distances to the centroid point and obtain a point sequence p9,  p7,  p5,  p3,  p1,  p,  p2,  p4,  p6,  p8. For point p, we search its kNNs from p to both sides (k=2). After p1,  p2, and  p3 are visited, p1 and p3 are the current top-k nearest neighbors for p, and thus kdistemp(p)=dis(p,p1). When we visit p4, dis(p4,C.centr)>dis(p,C.centr)+kdistemp(p). Hence, the points behind p4 in the sequence (i.e., p4,p6,p8) cannot be the kNNs of p. Similarly, when p5 is visited, we do not need to further scan the points before p5 in the sequence because dis(p5,C.centr)<dis(p,C.centr)-kdistemp(p). Therefore, the kNN searching stops, and the exact kNNs of p are p1 and p3.Figure 3
Example ofkNN searching.Furthermore, after the weights of some points have been computed, we send the current top-n points with the largest weights to the master node to obtain the threshold LB (mentioned in Section 4). We can use LB to filter the points that cannot be the CB outliers, instead of searching the exact kNNs. The detailed method is stated as follows.Theorem 4.
In thekNN searching of p in a cluster C, nnktemp(p) is the set of the current k-nearest neighbors of p from the scanned points. nnk(p) is the set of the exact k-nearest neighbors. One sorts the points in nnk(p) and nnktemp(p) according to the distances to p in an ascending order, respectively. Then, for the ith point in nnk(p): q and the ith point in nnktemp(p): q′, one asserts that dis(q,C.centr)>dis(p,C.centr)-dis(p,q′).Proof.
Ifq and q′ are the same point, the theorem can be proven easily. Otherwise, dis(p,q)<dis(p,q′). Using the triangle inequality, dis(q,C.centr)>dis(p,C.centr)-dis(p,q)>dis(p,C.centr)-dis(p,q′). The theorem is proven.Corollary 5.
For a pointp, if the current k-nearest neighbor set nnktemp(p) meets the following condition, p cannot be the CB outlier:(17)disp,C.centr×k∑q∈nnktemppdisp,C.centr-disp,q≤LB.Proof.
If (17) holds, the weight upper bound of p is smaller than or equal to LB according to Theorem 4. Therefore, p is not a CB outlier.By utilizing Corollary5, a large number of points can be filtered out safely, and we do not need to compute the exact kNNs of them. For example, in Figure 4, for k=2, we search the kNNs of q. After q1,  q2, and  q3 are visited, the current k-nearest neighbors are q1 and q3. dis(C.centr,q)×k/(2×dis(C.centr,q)-dis(q1,q)-dis(q3,q))≈1.57<LB. Then, we can assert that q is not a CB outlier even if the exact kNNs are not found. Therefore, q can be filtered out safely.Figure 4
Example of filtering.Algorithm2 shows the process of CB outlier detection on each slave node. For each cluster Ci in SETS, the points in Ci are sorted according to the distances to the centroid point in an ascending order (line (2)). Then, we scan the points in reversed order (line (3)), since the points far from the centroid point are more likely to have large weights and a good threshold LB can be obtained early. For each scanned point p, we visit the points from p to both sides to search the kNNs (line (8)). If the visited point q meets Theorem 3, a number of points can be erased from the visited list since they cannot be the kNNs of p (lines (10)–(13)). If the current kNNs of p meet Corollary 5, p is not an outlier, so we do not further search its kNNs (lines (16)–(18)). After all points are visited, we send p to the master node if p is still not filtered out (lines (19) and (20)). At last, the n points on the master node are the CB outliers.Algorithm 2:CB outlier detection on each slave node.
Input. The cluster set SETS reserved on slave node S, integers k, n, the threshold LB
Output. The CB outliers in P
(1) for each cluster Ci in SETSdo
(2)   Sort the points in Ci according to the distances to the centroid point
in ascending order;
(3)   Scan the points in reversed order;
(4)   for each scanned point pdo
(5)    Initialize a heap nn; // to reserve the current kNNs of p
(6)    kdistemp=∞; // the largest distance from the points in nn to p
(7)   boolean potential_outlier = true;
(8)   Visit the points from p to the both sides to search p’s kNNs;
(9)   for each visited point qdo
(10)      ifq is before p and
dis(q,C.centr)<dis(p,C.centr)-kdistempthen
(11)       Erase the points before q from the visited list;
(12)      else ifq is behind p and
dis(q,C.centr)>dis(p,C.centr)+kdistempthen
(13)       Erase the points behind q from the visited list;
(14)      else
(15)       Update nn and kdistemp;
(16)      ifnn meets the condition of Corollary 5then
(17)       potential_outlier = false;
(18)       break
(19)    ifpotential_outlierthen
(20)     Send p to the master node to update LB;


## 5.2. The Order of Cluster Scanning

As Section4 describes, each slave node needs to visit the local clusters one by one, and it computes the weights of points in each visited cluster. Meanwhile, the global top-n points with the largest weights thus far are kept in order to obtain the threshold LB. Clearly, the filtering effectiveness can be significantly improved if we obtain a large LB early, whereas a large LB is unlikely to be obtained if we visit the clusters in a random order, because we cannot guarantee that the early scanned points have large weights. As a consequence, we design a new ranking method for the clusters. Figure 5 illustrates the main idea of the ranking method.Figure 5
The ranking method of clusters.
(a)
A sparse cluster
(b)
A dense clusterA common idea is that points with large weights possibly emerge in a sparse cluster (the distance between every two points is large). However, this idea does not work well in many cases. For example, in Figure5(a), the distances from the points to the centroid point in the sparse cluster are almost identical, and thus the weights of these points are not large. However, in Figure 5(b), in the dense cluster, although most of the points are very close, two abnormal points q1 and  q2 are far from the centroid point, whose weights are large and suitable for the LB computation. From the observation in Figure 5(b), we can see that the distances of the points with large weights to the centroid point are large and quite different with those of the other points. Besides, note that we only need n large weights to compute LB. based on the description above, we propose the following ranking method.Definition 6 (the outlier factor of a cluster).
For a clusterC, suppose that the points have been sorted according to the distance to C.centr in a descending order. One uses dis0C to denote the distance between the first point and C.centr and disnC to denote the distance between the (n+1)th point and C.centr. Then, the outlier factor of C is(18)OFC=disnCdis0C.For example, in Figure5(a), n=2, which means we consider at most 2 points in a cluster to obtain LB. Thus, we sort the points according to the distance to C1.centr in a descending order, and we obtain the top-3 points, p1,  p2, and  p3. Then, we compute the distance between the first point p1 and C1.centr: dis(p1,C1.centr), and the distance between the third point p3 and C1.centr: dis(p3,C1.centr). The outlier factor of C1 is OF(C1)=dis(p3,C1.centr)/dis(p1,C1.centr)=0.95. Similarly, we get OF(C2)=dis(q3,C2.centr)/dis(q1,C2.centr)=0.5. Comparing the two outlier factors, we can see that OF(C1) is large, which means many points are far from C1.centr and they have similar distances to C1.centr. Therefore, we can hardly know whether there are points with large weights in C1. Conversely, the value of OF(C2) is small. We can assert that, in C2, most of the points closely surround the centroid point and there is at least one abnormal point (e.g., p1, p2) far from C2.centr. The weights of these abnormal points are large, and they contribute to selecting a large LB.As a consequence, we preferentially visit the clusters with small outlier factors, instead of visiting in a random order. This method helps us to obtain a largeLB early and improves the filtering effectiveness.


## 6. Experimental Evaluation

### 6.1. Method to Define Distance between Points

We use the method in [4] to define the distance between points in practical applications. First, we use a point with several measurable attributes to represent an object in the real world. All the objects can be mapped into European space. Then, for point p1 representing object o1 and point  p2 representing object o2, we use the distance between p1 and p2 to measure the difference between o1 and o2. Thus, a point with large distances to others is more likely to be an outlier.


### 6.2. Result Analysis for the Centralized Algorithm

In this section, we first evaluate the performance of the proposed algorithm in a centralized environment using a PC with an Intel Core i7-2600 @3.4 GHz CPU, 8 GB main memory, and 1 TB hard disk. A synthetic dataset is used for the experiments. In detail, given the data sizeN, we generate N/1000-1 clusters and randomly assign each of them a center point and a radius. In average, each cluster has 1000 points following Gaussian distribution. At last, the remaining 1000 points are scattered into the space. We implement the proposed method to detect CB outliers (DACB) using JAVA programming language. A naive method (naive) is also implemented as a comparing algorithm, where we simply search each point’s kNNs and compute its weight. In the experiments, we are mainly concerned with the runtime to represent the computational efficiency and the point accessing times (PATs) to indicate the disk IO cost. The parameters’ default values and their variations are shown in Table 1.Table 1
Parameter settings for the centralized algorithm.
Parameter
Default
Range of variation
k
20
15–35
n
30
20–40
Data sizeP  (×106)
1
0.5–2.5
Dimensionalityd
3
3–15As Figure6(a) shows, DACB is much more efficient than the naive method because of the pruning and filtering strategies proposed in this paper. With the increase of k, we need to keep tracking more neighbors for a point, so the runtime of the naive method and the DACB becomes larger. Figure 6(b) shows the effect of k on the PATs. For the naive method, each point needs to visit all the other points in the cluster to find its kNNs. Hence, PATs are large. In contrast, for DACB, a point does not have to visit all the other points (Theorem 3), and a large number of points can be filtered out, instead of finding their exact kNNs (Corollary 5). Therefore, the PATs are much smaller.Figure 6
The effect ofk for the centralized algorithm.
(a)
Time cost versusk
(b)
Point accessing times versuskFigure7 describes the effect of n. As n increases, more outliers are reported. Thus, the runtime of the naive method and the DACB becomes larger. The effect on the PATs is shown in Figure 7(b), whose trend is similar to that in Figure 6(b). Note that the PATs of DACB increase slightly with n, whereas the PATs of the naive method keep unchanged.Figure 7
The effect ofn for the centralized algorithm.
(a)
Time cost versusn
(b)
Point accessing times versusnIn Figure8, with the increase of the dimensionality, a number of operations (e.g., computing the distance of two points) become more time-consuming. Hence, the time cost of the two methods becomes larger. But the variation of the dimensionality does not affect the PATs. The effect of the data size is described in Figure 9. Clearly, with the increase of the data size, we need to scan more points to find the outliers. Therefore, both of the runtime and the PATs are linear to the data size.Figure 8
The effect of dimensionality for the centralized algorithm.
(a)
Time cost versusd
(b)
Point accessing times versusdFigure 9
The effect of data size for the centralized algorithm.
(a)
Time cost versusP
(b)
Point accessing times versusP


### 6.3. Result Analysis for the Distributed Algorithm

In this section, we further evaluate the performance of the proposed algorithm for distributed outlier detection. In the experiments, we mainly consider the time cost and the network transmission quantity (NTQ). The data size and the cluster scale are shown in Table2. The other parameters settings are identical to those described in Section 6.2.Table 2
Parameter settings for the distributed algorithm.
Parameter
Default
Range of variation
Data size (×107)
1
0.5–2.5
Number of slave nodes
10
6–14Figure10 shows the effect of parameter k. The curve “with SOO” represents the DACB algorithm. The curve “without SOO” represents a basic distributed algorithm for outlier detection without the Scanning Order Optimization (SOO) method described in Section 5.2. As we can see, as the value of k increases, both algorithms cost more time (the reason has been discussed in Section 6.2). But LB is not sensitive to k, and thus NTQ changes very slightly. Comparing the two algorithms, we can see that, with the help of SOO, a large LB can be obtained early and a lot more points can be filtered out efficiently. As a result, we can reduce the network overhead and improve the computing efficiency.Figure 10
The effect ofk for the distributed algorithm.
(a)
Time cost versusk
(b)
Network transmission quantity versuskIn Figure11, we evaluate the effect of parameter n. With the increase of n, we consider more points as outliers. Thus, the threshold LB becomes smaller and the filtering performance decreases. On the other hand, since a large n means that more points will be transmitted to the master node to compute LB, NTQ also increases.Figure 11
The effect ofn for the distributed algorithm.
(a)
Time cost versusn
(b)
Network transmission quantity versusnFigure12(a) evaluates the effect of the dimensionality on the time cost, which shows the same trend as the result in Figure 8(a). In Figure 12(b), we test the effect of the dimensionality on NTQ. Clearly, each slave node needs to send the local top-n points with the largest weights to the master node. The transmission contents include points’ ID, the values of all the dimensionality, and the weights. Therefore, more dimensionality leads to higher transmission quantity.Figure 12
The effect of dimensionality for the distributed algorithm.
(a)
Time cost versus dimensionality
(b)
Network transmission quantity versus dimensionalityAs Figure13(a) shows, with the increase of the data size, more points need to be scanned to find the outliers; thus, the time cost becomes larger. We can also see that, in Figure 13(b), NTQ increases with the data size, but the change is very small. This is because the value of LB becomes stable after a certain amount of calculation, and it is not sensitive to the data size.Figure 13
The effect of data size for the distributed algorithm.
(a)
Time cost versus data size
(b)
Network transmission quantity versus data sizeThe effect of the cluster scale is tested in Figure14. As more slave nodes are used, the workload on each node becomes smaller, and thus the computing speed is improved. However, to compute LB, the master node needs to collect n points from each slave node. Therefore, NTQ increases with the cluster scale. Note that, for the dataset with 107 points, NTQ is still maintained at a KB level. The network overhead of DACB is acceptable.Figure 14
The effect of number of slave nodes for the distributed algorithm.
(a)
Time cost versus number of slave nodes
(b)
Network transmission quantity versus number of slave nodes


## 6.1. Method to Define Distance between Points

We use the method in [4] to define the distance between points in practical applications. First, we use a point with several measurable attributes to represent an object in the real world. All the objects can be mapped into European space. Then, for point p1 representing object o1 and point  p2 representing object o2, we use the distance between p1 and p2 to measure the difference between o1 and o2. Thus, a point with large distances to others is more likely to be an outlier.


## 6.2. Result Analysis for the Centralized Algorithm

In this section, we first evaluate the performance of the proposed algorithm in a centralized environment using a PC with an Intel Core i7-2600 @3.4 GHz CPU, 8 GB main memory, and 1 TB hard disk. A synthetic dataset is used for the experiments. In detail, given the data sizeN, we generate N/1000-1 clusters and randomly assign each of them a center point and a radius. In average, each cluster has 1000 points following Gaussian distribution. At last, the remaining 1000 points are scattered into the space. We implement the proposed method to detect CB outliers (DACB) using JAVA programming language. A naive method (naive) is also implemented as a comparing algorithm, where we simply search each point’s kNNs and compute its weight. In the experiments, we are mainly concerned with the runtime to represent the computational efficiency and the point accessing times (PATs) to indicate the disk IO cost. The parameters’ default values and their variations are shown in Table 1.Table 1
Parameter settings for the centralized algorithm.
Parameter
Default
Range of variation
k
20
15–35
n
30
20–40
Data sizeP  (×106)
1
0.5–2.5
Dimensionalityd
3
3–15As Figure6(a) shows, DACB is much more efficient than the naive method because of the pruning and filtering strategies proposed in this paper. With the increase of k, we need to keep tracking more neighbors for a point, so the runtime of the naive method and the DACB becomes larger. Figure 6(b) shows the effect of k on the PATs. For the naive method, each point needs to visit all the other points in the cluster to find its kNNs. Hence, PATs are large. In contrast, for DACB, a point does not have to visit all the other points (Theorem 3), and a large number of points can be filtered out, instead of finding their exact kNNs (Corollary 5). Therefore, the PATs are much smaller.Figure 6
The effect ofk for the centralized algorithm.
(a)
Time cost versusk
(b)
Point accessing times versuskFigure7 describes the effect of n. As n increases, more outliers are reported. Thus, the runtime of the naive method and the DACB becomes larger. The effect on the PATs is shown in Figure 7(b), whose trend is similar to that in Figure 6(b). Note that the PATs of DACB increase slightly with n, whereas the PATs of the naive method keep unchanged.Figure 7
The effect ofn for the centralized algorithm.
(a)
Time cost versusn
(b)
Point accessing times versusnIn Figure8, with the increase of the dimensionality, a number of operations (e.g., computing the distance of two points) become more time-consuming. Hence, the time cost of the two methods becomes larger. But the variation of the dimensionality does not affect the PATs. The effect of the data size is described in Figure 9. Clearly, with the increase of the data size, we need to scan more points to find the outliers. Therefore, both of the runtime and the PATs are linear to the data size.Figure 8
The effect of dimensionality for the centralized algorithm.
(a)
Time cost versusd
(b)
Point accessing times versusdFigure 9
The effect of data size for the centralized algorithm.
(a)
Time cost versusP
(b)
Point accessing times versusP


## 6.3. Result Analysis for the Distributed Algorithm

In this section, we further evaluate the performance of the proposed algorithm for distributed outlier detection. In the experiments, we mainly consider the time cost and the network transmission quantity (NTQ). The data size and the cluster scale are shown in Table2. The other parameters settings are identical to those described in Section 6.2.Table 2
Parameter settings for the distributed algorithm.
Parameter
Default
Range of variation
Data size (×107)
1
0.5–2.5
Number of slave nodes
10
6–14Figure10 shows the effect of parameter k. The curve “with SOO” represents the DACB algorithm. The curve “without SOO” represents a basic distributed algorithm for outlier detection without the Scanning Order Optimization (SOO) method described in Section 5.2. As we can see, as the value of k increases, both algorithms cost more time (the reason has been discussed in Section 6.2). But LB is not sensitive to k, and thus NTQ changes very slightly. Comparing the two algorithms, we can see that, with the help of SOO, a large LB can be obtained early and a lot more points can be filtered out efficiently. As a result, we can reduce the network overhead and improve the computing efficiency.Figure 10
The effect ofk for the distributed algorithm.
(a)
Time cost versusk
(b)
Network transmission quantity versuskIn Figure11, we evaluate the effect of parameter n. With the increase of n, we consider more points as outliers. Thus, the threshold LB becomes smaller and the filtering performance decreases. On the other hand, since a large n means that more points will be transmitted to the master node to compute LB, NTQ also increases.Figure 11
The effect ofn for the distributed algorithm.
(a)
Time cost versusn
(b)
Network transmission quantity versusnFigure12(a) evaluates the effect of the dimensionality on the time cost, which shows the same trend as the result in Figure 8(a). In Figure 12(b), we test the effect of the dimensionality on NTQ. Clearly, each slave node needs to send the local top-n points with the largest weights to the master node. The transmission contents include points’ ID, the values of all the dimensionality, and the weights. Therefore, more dimensionality leads to higher transmission quantity.Figure 12
The effect of dimensionality for the distributed algorithm.
(a)
Time cost versus dimensionality
(b)
Network transmission quantity versus dimensionalityAs Figure13(a) shows, with the increase of the data size, more points need to be scanned to find the outliers; thus, the time cost becomes larger. We can also see that, in Figure 13(b), NTQ increases with the data size, but the change is very small. This is because the value of LB becomes stable after a certain amount of calculation, and it is not sensitive to the data size.Figure 13
The effect of data size for the distributed algorithm.
(a)
Time cost versus data size
(b)
Network transmission quantity versus data sizeThe effect of the cluster scale is tested in Figure14. As more slave nodes are used, the workload on each node becomes smaller, and thus the computing speed is improved. However, to compute LB, the master node needs to collect n points from each slave node. Therefore, NTQ increases with the cluster scale. Note that, for the dataset with 107 points, NTQ is still maintained at a KB level. The network overhead of DACB is acceptable.Figure 14
The effect of number of slave nodes for the distributed algorithm.
(a)
Time cost versus number of slave nodes
(b)
Network transmission quantity versus number of slave nodes


## 7. Related Work

Outlier detection is an important task in the area of data management, whose target is to find the abnormal objects in a given dataset. The statistics community [2, 3] proposed the model-based outliers. The dataset is assumed to follow a distribution. An outlier is the object that shows obvious deviation from the assumed distribution. Later, the data management community pointed out that building a reasonable distribution is almost an impossible task for high-dimensional datasets. To overcome this weakness, they proposed several model-free approaches [22], including distance-based outliers [4–6] and density-based outliers [7].A number of studies focus on developing efficient methods to detect outliers. Knorr and Ng [4] proposed the well-known nested-loop (NL) algorithm to compute distance-based outliers. Bay and Schwabacher [23] proposed an improved nested-loop approach, called ORCA. The approach efficiently prunes the searching space by randomizing the dataset before outlier detection. Angiulli and Fassetti [24] proposed DOLPHIN, which can reduce the disk IO cost through maintaining a small subset of the input data in main memory. Several researchers adopt the spatial indexes to further improve the computing efficiency. Examples include R-tree [25], M-tree [26], and grids. However, the performance of these methods is quite sensitive to the dimensionality. To improve the computing efficiency, some researchers attempt to use a distributed or parallel method to detect outliers. Examples include [27–29].


## 8. Conclusion

In this paper, we studied the problem of CB outlier detection in a distributed environment and proposed an efficient algorithm, called DACB. This algorithm adopts a master-slave architecture. The master node monitors the points with large weights on each slave node and computes a threshold. On each slave node, we designed a pruning method to speed up thekNN searching and a filtering method that can use the threshold to filter out a large number of unpromising points. We also designed an optimization method for cluster scanning, which can significantly improve the filtering performance of the threshold. Finally, we evaluated the performance of the proposed approaches through a series of simulation experiments. The experimental results show that our method can effectively reduce the runtime and the network transmission quantity for distributed CB outlier detection.



---

*Source: 2649535-2017-04-09.xml*