# Index Based Hidden Outlier Detection in Metric Space

Authors: Honglong Xu; Rui Mao; Hao Liao; He Zhang; Minhua Lu; Guoliang Chen
Journal: Scientific Programming
 (2016)

---

## Abstract

Useless and noise information occupies large amount of big data, which increases our difficulty to extract worthy information. Therefore outlier detection attracts much attention recently, but if two points are far from other points but are relatively close to each other, they are less likely to be detected as outliers because of their adjacency to each other. In this situation, outliers are hidden by each other. In this paper, we propose a new perspective of hidden outlier. Experimental results show that it is more accurate than existing distance-based definitions of outliers. Accordingly, we exploit a candidate set based hidden outlier detection (HOD) algorithm. HOD algorithm achieves higher accuracy with comparable running time. Further, we develop an index based HOD (iHOD) algorithm to get higher detection speed.


---

## Body

## 1. Introduction

In recent years, the rapid growth of multidimensional data brings about increasing demand for knowledge discovery, in which outlier detection is an important task with wide applications, such as credit card fraud detection [1], online video detection [2], and network intrusion detection [3].As a matter of necessity, the wide use of outlier detection has aroused enthusiasm in many researchers. Over the past few decades, many outlier definitions and detection algorithms have been proposed in the literature [4–6]. Among these, statistics-based outlier detection [7, 8], which initiated a new era for data mining, has attracted an intensive study. Nevertheless, statistics-based outlier detection always depends on the probability distribution of the dataset, which is always priorly unknown.In order to overcome shortcoming of statistics-based method, Knorr and Ng et al. proposed distance-based definition and the corresponding detection method [9, 10]. According to his definition, an objectO in a datasetT is D
B
p
,
D outlier if at least fractionp of the objects inT lies greater than distanceD fromO [10]. Soon afterwards, a number of distance-based definitions had been presented [4, 6]. Based on these definitions and their relevant detection methods, many researches significantly improved both outlier detection accuracy and speed.However, by existing definitions, outliers tend to be far from their nearest neighbors. As a result, if a small number of outliers are close to each other but are far from other points, which also known as outlier cluster, they are not likely to be determined as outliers because of their adjacency to each other. In this case, these points are hidden by each other. In other words, outlier itself has bad influence on detection accuracy [11]. In this paper, we propose a new perspective of hidden outlier that can uncover those hidden ones by traditional definitions and also design a new detection algorithm. Specifically, we make the following contributions:(1)
A more accurate definition of outlier taking hidden outliers into consideration.
(2)
An effective detection algorithm for the definition proposed, with higher accuracy only at the cost of a little more time.
(3)
An index based HOD (iHOD) algorithm and getting much higher detection speed.
(4)
A simple but effective algorithm to select pivot for iHOD algorithm to avoid selecting outliers as pivots.The rest of this paper is organized as follows. In Section2, we will discuss several commonly used outlier definitions and relevant detection algorithms, along with their efficiency variants. Section 3 proposes the definition of hidden outlier and Section 4 proposes its detection algorithms. Experimental results are presented in Section 5, followed by conclusion and future work in Section 6.


## 2. Related Work

As mentioned in the introduction, there are many definitions and detection algorithms for outliers, among which Hawkins’s work [12] stands out as the first. Following this work, three major distance-based definitions of outliers have been proposed, namely,k-R outlier [9, 10],k-distance-based outlier [13], and distance sum-based outlier [14].k-R outlier [9, 10] in a dataset is a point that no more thank points are within distanceR to it, denoted as O
t
h
r
e
s
(
k
,
R
) [15]. Please note that the definition ofk-R outlier is essentially equivalent to definition D
B
p
,
D [9, 10], by which a point in a datasetT is an outlier if at least a fractionp of all points inT is beyond distanceD to it.k-distance-based [13] outlier in a dataset is the point whose distance to itskth nearest neighbor is the largest among all points. Usually, the distance of a point to itskth nearest neighbor is considered as its outlier degree, and then points with the largest outlier degrees are determined as outliers, denoted as O
k
m
a
x
(
k
,
n
) [15].The definition of distance sum-based outlier [14] considered the sum of distances from a point to itsk nearest neighbors as its outlier degree, and then points with the largest sums are determined as outliers which can be denoted as O
k
s
u
m
(
k
,
n
). Similarly, distance average-based outlier, an equivalent definition in which the average distance tok nearest neighbors is considered, can be defined and denoted as O
k
a
v
g
(
k
,
n
) [15]. BecausekNN method is easy to implement [16], the above three distance-based definitions become popular.In addition, density-based outlier is actually distance-based outlier; for example, LOF [17], the most famous density-based definition, was accomplished in detecting outliers from a dataset with different densities, while ordinary definitions are not qualified for this work.Distance-based outlier detection algorithm was always designed for one or several definitions. Over the past decades, many detection algorithms were proposed since the above definitions emerged, in which the most famous one is ORCA [18]. ORCA has been honoured as the state-of-art algorithm [18] because of its simplicity and efficiency. What is more, it supports any outlier definitions with monotonically decreasing function of the nearest neighbor distances such as O
k
m
a
x
(
k
,
n
) or O
k
a
v
g
(
k
,
n
). After that, many variants appeared in the literature, including solving set algorithm [19], MIRO [20], RCS [21], and iORCA [22]. It should be noted that not all the variants support the same definitions as ORCA [18]; for instance, iORCA [22] could not support O
k
a
v
g
(
k
,
n
) definition.For speeding upkNN search [16], some researchers exploit other research methods, for example, index based algorithm. Knorr et al. first bring forward index based method. According to their description,R-tree andk-d tree can be applied [10]. After that,k-d tree based method was proposed and had got a time complexity of O
n
k [23]. Other detection algorithms, including HilOut based algorithm [24],P tree based algorithm [25], LSH based algorithm [26, 27], and SFC index [28], use different index structure to speed up detection. Besides, sample method was applied to reduce distance computations [29].k-R outlier also attracted many researchers since Knorr and Ng et al. proposed D
B
p
,
D outlier definition and three relevant algorithms (nested-loop, index based, and cell-based algorithm) [9, 10]. For example, Tao et al.’s SNIF algorithm [30] can detect all outliers by scanning the dataset at most twice and even once in some cases. DOLPHIN algorithm [31] is also an efficient method to detectk-R outlier. However,k-R outlier has a shortcoming that parameters are difficult to set [13].Similarly, the research works for density-based detection algorithm started from their incipient definition, which is LOF [17]. The variants or improved algorithms included COF [32], MDEF [33], Ensemble method [34], and so forth.Since this paper aimed at outlier definition, we just took three most popular and simplest algorithms as comparison algorithm: ORCA [18], which is the state-of–art distance-based outlier detection algorithm, LOF [17], the most representative density-based outlier detection method, and iORCA [22], latest index based outlier detection algorithm in metric space. For ORCA and iORCA, O
k
s
u
m
(
k
,
n
) and O
k
m
a
x
(
k
,
n
) were used as outlier definition, respectively.


## 3. Definition of Hidden Outlier

In this section, we propose the new perspective of hidden outlier. The basic idea is that once an outlier is detected, exclude it from the nearest neighbors of other points.


### 3.1. Cause of Hidden Outlier

As is shown in Figure1, points A and B are outliers, but point C is not. In this case, if we set k
=
2 and detect TOP 2 outliers by distance sum-based outlier definition, A and C will be detected as outliers, other than B, which is a real outlier. However, A and C will be detected as outliers, other than B, which is a real outlier. The reason is that the existence of A reduces the outlier degree of B, leading to the mistake in detection.Figure 1
A simple 2-dimension dataset.


### 3.2. Definition of Hidden Outlier

If a small number (e.g., equal to or greater than 2) of points are close to each other but are far to other points, they are usually deemed as outliers. However, traditional distance-based definitions of outliers determine an outlier by its distances to its nearest neighbors. As a result, those small number of points close to each other are usually not outliers according to traditional definitions. In this situation, outliers seem to be hidden by each other, and they can be called hidden outliers.Our definition of outliers which include hidden ones, denoted asH
O
k
s
u
m
(
k
,
n
), is extended from the definition of distance-based outlier. Here we take distance sum-based outlier, O
k
s
u
m
(
k
,
n
), as example to give detailed description. Notation summarizes the notations and their description.LetD be a dataset, let dist be a distance function, letp be a point, and let n
n
i
(
p
,
D
) be theith nearest neighbor ofp inD. Please note that a point is not considered as a nearest neighbor of itself. Further, let D
i
,
k be theith outlier by O
k
s
u
m
(
k
,
n
) definition, let w
k
(
p
,
D
) be the outlier degree of p, and let D
n-outlier be the set of n outliers of the largest values of outlier degree. According to the definition of O
k
s
u
m
(
k
,
n
), w
k
(
p
,
D
) is given by(1)
w
k
p
,
D
=
∑
i
=
1
k
d
i
s
t
p
,
n
n
i
p
,
D
.LetH
D
i
,
k be theith outlier by our new definition, let H
w
k
(
p
,
D
) bep’s outlier degree, and let H
D
n-outlier be the set of firstn outliers.Definition 1.
The definition of outliers include hidden ones,H
O
k
s
u
m
(
k
,
n
), defines the outliers in an iterative way:(2)
H
D
1
,
k
=
argmax
p
⁡
w
k
p
,
D
H
D
i
,
k
=
a
r
g
m
a
x
p
w
k
p
,
D
-
H
D
i
-
1
-outlier
,
2
≤
i
≤
n
.Definition 2.
The outlier degree ofp by H
O
k
s
u
m
(
k
,
n
) definition, H
w
k
(
p
,
D
), is defined as(3)
H
w
k
p
,
D
=
w
k
D
1
,
k
,
D
,
if
p
=
D
1
,
k
w
k
p
,
D
-
H
D
i
-
1
-outlier
,
if
p
=
H
D
i
,
k
,
2
≤
i
≤
n
w
k
p
,
D
-
H
D
n
-outlier
,
otherwise.In other words,H
w
k
(
p
,
D
) is still the sum of distances fromp to itsk nearest neighbors, while outliers already detected are not considered asp’s nearest neighbors. Please note that the sequence of H
w
k
(
H
D
i
,
k
,
D
)
,
1
≤
i
≤
n, might not be in descending order.The other definition of outliers may be deduced by analogy. For example,O
k
m
a
x
(
k
,
n
), we can simply displace the outlier degree of O
k
s
u
m
(
k
,
n
) as that of O
k
m
a
x
(
k
,
n
), which is(4)
w
k
p
,
D
=
d
i
s
t
p
,
n
n
i
p
,
D
.Then we can give the same definition of hidden outlier and its degree as Definitions1 and 2. It is worth mentioning that, for simplicity, O
k
s
u
m
(
k
,
n
) based hidden outlier will be calledksum hidden outlier, while O
k
m
a
x
(
k
,
n
) hidden outlier will be calledkmax hidden outlier. Though both HOD (Section 4.1) and iHOD (Section 4.2) can apply these two definitions, for the limited space, they will only use one definition, respectively, in our experiments.


## 3.1. Cause of Hidden Outlier

As is shown in Figure1, points A and B are outliers, but point C is not. In this case, if we set k
=
2 and detect TOP 2 outliers by distance sum-based outlier definition, A and C will be detected as outliers, other than B, which is a real outlier. However, A and C will be detected as outliers, other than B, which is a real outlier. The reason is that the existence of A reduces the outlier degree of B, leading to the mistake in detection.Figure 1
A simple 2-dimension dataset.


## 3.2. Definition of Hidden Outlier

If a small number (e.g., equal to or greater than 2) of points are close to each other but are far to other points, they are usually deemed as outliers. However, traditional distance-based definitions of outliers determine an outlier by its distances to its nearest neighbors. As a result, those small number of points close to each other are usually not outliers according to traditional definitions. In this situation, outliers seem to be hidden by each other, and they can be called hidden outliers.Our definition of outliers which include hidden ones, denoted asH
O
k
s
u
m
(
k
,
n
), is extended from the definition of distance-based outlier. Here we take distance sum-based outlier, O
k
s
u
m
(
k
,
n
), as example to give detailed description. Notation summarizes the notations and their description.LetD be a dataset, let dist be a distance function, letp be a point, and let n
n
i
(
p
,
D
) be theith nearest neighbor ofp inD. Please note that a point is not considered as a nearest neighbor of itself. Further, let D
i
,
k be theith outlier by O
k
s
u
m
(
k
,
n
) definition, let w
k
(
p
,
D
) be the outlier degree of p, and let D
n-outlier be the set of n outliers of the largest values of outlier degree. According to the definition of O
k
s
u
m
(
k
,
n
), w
k
(
p
,
D
) is given by(1)
w
k
p
,
D
=
∑
i
=
1
k
d
i
s
t
p
,
n
n
i
p
,
D
.LetH
D
i
,
k be theith outlier by our new definition, let H
w
k
(
p
,
D
) bep’s outlier degree, and let H
D
n-outlier be the set of firstn outliers.Definition 1.
The definition of outliers include hidden ones,H
O
k
s
u
m
(
k
,
n
), defines the outliers in an iterative way:(2)
H
D
1
,
k
=
argmax
p
⁡
w
k
p
,
D
H
D
i
,
k
=
a
r
g
m
a
x
p
w
k
p
,
D
-
H
D
i
-
1
-outlier
,
2
≤
i
≤
n
.Definition 2.
The outlier degree ofp by H
O
k
s
u
m
(
k
,
n
) definition, H
w
k
(
p
,
D
), is defined as(3)
H
w
k
p
,
D
=
w
k
D
1
,
k
,
D
,
if
p
=
D
1
,
k
w
k
p
,
D
-
H
D
i
-
1
-outlier
,
if
p
=
H
D
i
,
k
,
2
≤
i
≤
n
w
k
p
,
D
-
H
D
n
-outlier
,
otherwise.In other words,H
w
k
(
p
,
D
) is still the sum of distances fromp to itsk nearest neighbors, while outliers already detected are not considered asp’s nearest neighbors. Please note that the sequence of H
w
k
(
H
D
i
,
k
,
D
)
,
1
≤
i
≤
n, might not be in descending order.The other definition of outliers may be deduced by analogy. For example,O
k
m
a
x
(
k
,
n
), we can simply displace the outlier degree of O
k
s
u
m
(
k
,
n
) as that of O
k
m
a
x
(
k
,
n
), which is(4)
w
k
p
,
D
=
d
i
s
t
p
,
n
n
i
p
,
D
.Then we can give the same definition of hidden outlier and its degree as Definitions1 and 2. It is worth mentioning that, for simplicity, O
k
s
u
m
(
k
,
n
) based hidden outlier will be calledksum hidden outlier, while O
k
m
a
x
(
k
,
n
) hidden outlier will be calledkmax hidden outlier. Though both HOD (Section 4.1) and iHOD (Section 4.2) can apply these two definitions, for the limited space, they will only use one definition, respectively, in our experiments.


## 4. Hidden Outlier Detection Algorithm

In this section, the detection algorithms designed for hidden outlier are proposed, together with several theorems and definitions.


### 4.1. Hidden Outlier Detection Algorithm

The detection algorithm ofH
O
k
s
u
m
(
k
,
n
) is presented in this section. We start from a few theorems and concepts together which can be used to speed up the detection.Theorem 3.
The hidden outlier degree is always no less than the outlier degree orH
w
k
(
p
,
D
)
≥
w
k
(
p
,
D
)
.The proof is straightforward from the definitions of both outlier degrees and is thus omitted.Theorem 4.
Theith hidden outlier’s outlier degree is no less than that of theith outlier by O
k
s
u
m
(
k
,
n
); that is, H
w
k
(
H
D
i
,
k
,
D
)
≥
w
k
(
D
i
,
k
,
D
)
,
1
≤
i
≤
n.Proof.
(1) if i
=
1, the equation clearly holds.
(2) If 2
≤
i
≤
n, one has the following.
(a) IfH
D
i
-outlier
=
D
i
-outlier, there must existt, such that H
D
i
,
k
=
D
t
,
k
,
1
≤
t
≤
i. From Theorem 3 and the definition of w
k
(
p
,
D
), (5)
H
w
k
H
D
i
,
k
,
D
≥
w
k
D
t
,
k
,
D
≥
w
k
D
i
,
k
,
D
.
(b) Otherwise, there must existt, such that D
t
,
k
∉
H
D
i-outlier, 1
≤
t
≤
i. From Definition 2, Theorem 3, and the definition of w
k
(
p
,
D
), (6)
H
w
k
H
D
i
,
k
,
D
≥
H
w
k
D
t
,
k
,
D
≥
w
k
D
t
,
k
,
D
≥
w
k
D
i
,
k
,
D
.For convenience, we introduce two more definitions,maximum possible outlier degree andhidden outlier candidate set, and related theorems to show their properties.Definition 5.
Themaximum possible outlier degree of p, M
P
W
n
,
k
(
p
,
D
), is the hidden outlier degree ofp assuming that all the first n
-
1 nearest neighbors ofp are detected as outliers and thus are excluded from contributing top’s hidden outlier degree. That is,(7)
M
P
W
n
,
k
p
,
D
=
∑
i
=
n
n
+
k
-
1
d
i
s
t
p
,
n
n
i
p
,
D
.From Definition 5, we give the following obvious theorem without proof.Theorem 6.
(8)
H
w
k
p
,
D
≤
M
P
W
n
,
k
p
,
D
.Definition 7.
The hidden outlier candidate set,C
S
n
,
k(D), is a subset ofD such that, for each p
∈
C
S
n
,
k
(
D
)
,
M
P
W
n
,
k
(
p
,
D
)
≥
w
k
(
D
n
,
k
,
D
).The following theorem shows the purpose in defining hidden outlier candidate set.Theorem 8.
The hidden outlier candidate sets,C
S
n
,
k(D), contains all of the outliers defined by H
O
k
s
u
m
(
k
,
n
).Proof.
For an arbitrary outlierp defined by H
O
k
s
u
m
(
k
,
n
), from definition and from Theorem 4, H
w
k
(
p
,
D
)
≥
w
k
(
p
,
D
).
From Theorem6, H
w
k
(
p
,
D
)
≤
M
P
W
n
,
k
(
p
,
D
).
As a result,M
P
W
n
,
k
p
,
D
≥
w
k
(
D
n
,
k
,
D
); that is, p
∈
C
S
n
,
k
(
D
).Our hidden outlier detection (HOD) algorithm (Algorithm1) is based on the ORCA algorithm [18]. HOD searches k
+
n
-
1 nearest neighbors (in consideration of performance,n must be small) of every data block (lines (
4
)
–
(
7
)). Once an object is impossible to become an outlier, it will be removed from data block (line (
8
)). After processing a data block, HOD gets current D
n
-outlier (line (
10
)) and updates cutoff valuec (line (
11
)) and then maintains hidden outlier candidate set at the same time (lines (
12
)
–
(
16
)), including deleting the objects with smallerMPW thanc (lines (
13
)-(
14
)) and adding the objects with largerMPW thanc (lines (
15
)-(
16
)). Finally the candidate set is filtered to get the final results (Algorithm 2).Algorithm 1:Hidden outlier detection algorithm.
Input: k, n, D
Output: H
D
n
-outlier
(1)c
←
0;
(2)D
n
-
o
u
t
l
i
e
r
←
ϕ;
(3)B
←
ϕ; //B is a data block of dataset D
(4)while  B
← get-next-block(D)
(5)for each d in D
(6)for each b in B
(7)d
i
s
←
d
i
s
t
(
b
,
d); update b.NN
(8)if  M
P
W
n
,
k
(
b
,
D
)
<
c remove b from B;
(9)for each b in B
(10)D
n
-
o
u
t
l
i
e
r
←
T
O
P
(
B
∪
D
n
-
o
u
t
l
i
e
r
,
n
) //update D
n
-
o
u
t
l
i
e
r;
(11)c
←
w
k
(
D
n
,
k
,
D
)  //update c;
(12)for each cs in C
S
n
,
k
(
D
)
(13)if (M
P
W
n
,
k
(
c
s
,
D
)
<
c)
(14)      deletecs from C
S
n
,
k
(
D
);
(15)if (M
P
W
n
,
k
(
b
,
D
)
>
c)
(16)     insertb to C
S
n
,
k
(
D
);
(17)H
D
n
-
o
u
t
l
i
e
r
←
f
i
l
t
e
r
i
n
g process(D
n
-
o
u
t
l
i
e
r
,
C
S
n
,
k
(
D
));
(18)  returnH
D
n
-
o
u
t
l
i
e
r;Algorithm 2:Filtering process.
Input:  D
n
-
o
u
t
l
i
e
r, C
S
n
,
k
(
D
)
Output:  H
D
n
-
o
u
t
l
i
e
r
(1)H
D
1
,
k
=
D
1
,
k, delete D
1
,
k from C
S
n
,
k
(
D
);
(2)  Seti
=
1;
(3)for each cso in C
S
n
,
k
(
D
)
(4)if  (H
D
i
,
k
∈
c
s
o
.
N
N) updatecso.NN and H
w
k
(
c
s
o
,
D
);
(5)i++; H
D
i
,
k
←
T
O
P(C
S
n
,
k
(
D
)
,
1), delete it from C
S
n
,
k
(
D
) and insert to H
D
n
-outlier;
(6)if  (i
<
n)  do
line (3)
(7)  returnH
D
n
-outlier;Algorithm2 shows how the candidate set is filtered to get the final results. D
1
,
k is first moved from C
S
n
,
k(D) to H
D
n
-outlier (line 1), because the first outlier of D
n
-outlier and first outlier H
D
n
-outlier are the same. Then the last outlier of H
D
n
-outlier is checked to see whether it is a nearest neighbor of some objects in C
S
n
,
k(D). If yes, it is deleted from that object’ nearest neighbors and the hidden outlier degree H
w
k
(
c
s
o
,
D
) (lines 2
–
(
4
)) is updated. Next, the object with the largest hidden outlier degree in C
S
n
,
k(D) is moved to H
D
n
-outlier (line (
5
)), and the process goes back to line (
2
) until there aren outliers (line (
6
)).As Bay and Schwabacher indicated, ORCA [18] has O
(
N
) time complexity on average and O
(
N
2
) in the worst case. In contrast to ORCA [18], HOD searches more nearest neighbors and thus costs more time and memory space. Further, HOD prunes less normal objects and results in more distance computations. However, these do not increase HOD’s time complexity because as more data blocks have been processed, the cutoff valuec becomes larger and more normal objects will be pruned. In other words, the pruning mechanism is the same as ORCA [18]. After searching a data block’s nearest neighbors, HOD maintains an outlier candidate set and updates it after updatingc, which can be implemented by a fast priority queue. In addition, experimental results show that the candidate set size keeps constant as a whole with various dataset sizes, limiting the overhead of filtering process described in Algorithm 2.


### 4.2. Index Based Hidden Outlier Detection Algorithm

In order to speed up HOD algorithm, we draw on the experience of iORCA and develop a simple index based hidden outlier detection algorithm. As we discussed in Section2, iORCA is a very excellent distance-based improvement from ORCA, which is the state-of-the-art method in outlier detection. It is worth mentioning that the build index process (Algorithm 3) of iORCA is very simple and almost costs little time. However, the only fly in the ointment is that iORCA is short of pivot selection method. Addressing this shortcoming, we propose a simple but efficient pivot selection algorithm (Algorithm 4).Algorithm 3:Build index.
Input: D, pivot
Output: index L
(1)L
←
ϕ;
(2)for each o in D
(3)L
(
o
)
←
d
i
s
t
(
p
i
v
o
t
,
o
);
(4) sort(L); //sorted by the distance value in
//descending order
(5) returnL;Algorithm 4:Pivot selection.
Input: D, p
i
v
o
t
N
u
m
Output: p
i
v
o
t
(1)b
l
o
c
k
I
n
d
e
x
←
ϕ;
(2)B
←
g
e
t
P
a
r
t
O
f
D
a
t
a
S
e
t(D); //B is usually a data block of dataset D
(3) blockIndex← buildIndex(B
,
B
[
0
]);
(4) divide blockIndex intopartNum equal segments; //p
a
r
t
N
u
m
⩾
2
∗
p
i
v
o
t
N
u
m
and 10, every segment has the same number of points
(5) getpivotNum segments with smallest skip distance;
(6)pivot
← middle object of every smallest segment;
(7) returnpivot;The most important idea of iORCA is to update the cutoff value faster. In Algorithm3, we can see that, in order to achieve this goal, iORCA simply calculates the distance between every object to pivot (lines (
2
)-(
3
)) and then sort them from large to small (line (
4
)). Obviously, both the time and memory consuming of this index are very small.The largest difference between similarity search and outlier detection is that similarity search procedure may be used many times, for searching different object, while outlier detection procedure may be used for only several times, even just one time. That is a decision that their pivot selection method for building index will be different. Since similarity search always follows the rules of Offline Construction and Online Search [35, 36], it can spend more time to select pivots and build index, other than outlier detection to save time in this stage.As Bhaduri et al. said that if we select inlier points as pivots, the points farthest from them will be more likely to be the outliers [22]. To benefit from this, the goal of our pivot selection algorithm is to select density points as pivots. However, the accurate search of density points is too expensive. So, in our pivot selection algorithm, we only find out the approximate density regions (lines (
4
)-(
5
)) and then choose the middle point of these regions (line (
6
)).In addition, we only take a part of dataset to select pivots, and usually a data block is enough. Due to the small percentage of outliers, it is almost impossible to select outliers as pivots via this subset using our method. The flowchart of iHOD algorithm is shown in Figure2.Figure 2
The flow chart of iHOD algorithm.The stopping rule (Theorem9) of iORCA can be applied in iHOD as well to quickly stop updating the cutoff value.Theorem 9 (iORCA stopping rule [22]).
LetD be the dataset, let c be the cutoff value, let p be the pivot, and let x
t be any test point currently being tested by iORCA (or iHOD); if (9)
d
i
s
t
x
t
,
p
+
d
i
s
t
p
,
n
n
k
p
,
D
<
cthen iORCA (or iHOD) can terminate with the correct D
n-outlier and cutoff value.
In addition, we propose other rules to reduce the distance computing times.Theorem 10.
Ifdist
⁡
x
t
,
p
+
dist
⁡
p
,
n
n
k
+
n
-
1
p
,
D
<
c, then iHOD can stop updating hidden outlier candidate set.Theorem10 can be proved similar to Theorem 9.Theorem 11.
If(10)
d
i
s
t
x
i
,
p
-
d
i
s
t
x
j
,
p
>
d
i
s
t
x
i
,
n
n
k
x
i
,
Dthen x
i is no longer thek nearest neighbors of x
i.Proof.
Using Triangle Inequality, there is(11)
d
i
s
t
x
i
,
x
j
≥
d
i
s
t
x
i
,
p
-
dist
⁡
x
j
,
pso we have (12)
d
i
s
t
x
i
,
x
j
>
d
i
s
t
x
i
,
n
n
k
x
i
,
D
.In other words, x
j is faster than the kth nearest neighbor of x
i. So x
j is no longer the k nearest neighbors of x
i.Our index based hidden outlier detection algorithm (Algorithm5) combines iORCA (lines (
3
)
–
(
9
)) and HOD (lines (
13
)
–(24)) algorithms and updates them with pivot selection algorithm (line (
2
)) and Theorem 11 (line (12)), finally resulting in its high performance.Algorithm 5:Index based hidden outlier detection algorithm.
Input: k, n, D
Output: H
D
n
-
o
u
t
l
i
e
r
(1)c
←
0; D
n
-
o
u
t
l
i
e
r
←
ϕ; B
←
ϕ; //B is a data block of dataset D
(2)  pivot← pivotSelection(D
,
1);
(3)L
←
b
u
i
l
d
I
n
d
e
x(D
,
p
i
v
o
t); //L is a data block of dataset D
(4)while  B
←
get-next-block
(
L
(
D
)
)
(5)if (Theorem10 holds for
B
(
1
)) then break;
(6)else
(7)µ
←
f
i
n
d
A
v
g
(
L
(
B
)
);
(8)s
t
a
r
t
I
D
←
f
i
n
d
(
L
⩾
µ
);
(9)o
r
d
e
r
←
s
p
i
r
a
l
O
r
d
e
r(L.id, startID);
(10)for each d in D with order
(11)for each b in B
(12)if (Theorem11 doesn’t hold for
d
and
b
)
(13)d
i
s
←
d
i
s
t
(
b
,
d
); update b.NN
(14)if  M
P
W
n
,
k
(
b
,
D
)
<
c remove b from B;
(15)for each b in B
(16)if (Theorem9 doesn’t holds for
B
(
1
))
(17)D
n
-
o
u
t
l
i
e
r
←
T
O
P(B
∪
D
n
-
o
u
t
l
i
e
r
,
n)  //update D
n
-
o
u
t
l
i
e
r;
(18)c
←
w
k
(
D
n
,
k
,
D
) //update c;
(19)for each cs in C
S
n
,
k
(
D
)
(20)if (M
P
W
n
,
k
(
c
s
,
D
)
<
c)
(21)      deletecs from C
S
n
,
k
(
D
);
(22)if (M
P
W
n
,
k
(
b
,
D
)
>
c)
(23)     insertb to C
S
n
,
k
(
D
);
(24)H
D
n
-
o
u
t
l
i
e
r
←
f
i
l
t
e
r
i
n
g process(D
n
-
o
u
t
l
i
e
r
,
C
S
n
,
k
(
D
));
(25)  returnH
D
n
-
o
u
t
l
i
e
r;


## 4.1. Hidden Outlier Detection Algorithm

The detection algorithm ofH
O
k
s
u
m
(
k
,
n
) is presented in this section. We start from a few theorems and concepts together which can be used to speed up the detection.Theorem 3.
The hidden outlier degree is always no less than the outlier degree orH
w
k
(
p
,
D
)
≥
w
k
(
p
,
D
)
.The proof is straightforward from the definitions of both outlier degrees and is thus omitted.Theorem 4.
Theith hidden outlier’s outlier degree is no less than that of theith outlier by O
k
s
u
m
(
k
,
n
); that is, H
w
k
(
H
D
i
,
k
,
D
)
≥
w
k
(
D
i
,
k
,
D
)
,
1
≤
i
≤
n.Proof.
(1) if i
=
1, the equation clearly holds.
(2) If 2
≤
i
≤
n, one has the following.
(a) IfH
D
i
-outlier
=
D
i
-outlier, there must existt, such that H
D
i
,
k
=
D
t
,
k
,
1
≤
t
≤
i. From Theorem 3 and the definition of w
k
(
p
,
D
), (5)
H
w
k
H
D
i
,
k
,
D
≥
w
k
D
t
,
k
,
D
≥
w
k
D
i
,
k
,
D
.
(b) Otherwise, there must existt, such that D
t
,
k
∉
H
D
i-outlier, 1
≤
t
≤
i. From Definition 2, Theorem 3, and the definition of w
k
(
p
,
D
), (6)
H
w
k
H
D
i
,
k
,
D
≥
H
w
k
D
t
,
k
,
D
≥
w
k
D
t
,
k
,
D
≥
w
k
D
i
,
k
,
D
.For convenience, we introduce two more definitions,maximum possible outlier degree andhidden outlier candidate set, and related theorems to show their properties.Definition 5.
Themaximum possible outlier degree of p, M
P
W
n
,
k
(
p
,
D
), is the hidden outlier degree ofp assuming that all the first n
-
1 nearest neighbors ofp are detected as outliers and thus are excluded from contributing top’s hidden outlier degree. That is,(7)
M
P
W
n
,
k
p
,
D
=
∑
i
=
n
n
+
k
-
1
d
i
s
t
p
,
n
n
i
p
,
D
.From Definition 5, we give the following obvious theorem without proof.Theorem 6.
(8)
H
w
k
p
,
D
≤
M
P
W
n
,
k
p
,
D
.Definition 7.
The hidden outlier candidate set,C
S
n
,
k(D), is a subset ofD such that, for each p
∈
C
S
n
,
k
(
D
)
,
M
P
W
n
,
k
(
p
,
D
)
≥
w
k
(
D
n
,
k
,
D
).The following theorem shows the purpose in defining hidden outlier candidate set.Theorem 8.
The hidden outlier candidate sets,C
S
n
,
k(D), contains all of the outliers defined by H
O
k
s
u
m
(
k
,
n
).Proof.
For an arbitrary outlierp defined by H
O
k
s
u
m
(
k
,
n
), from definition and from Theorem 4, H
w
k
(
p
,
D
)
≥
w
k
(
p
,
D
).
From Theorem6, H
w
k
(
p
,
D
)
≤
M
P
W
n
,
k
(
p
,
D
).
As a result,M
P
W
n
,
k
p
,
D
≥
w
k
(
D
n
,
k
,
D
); that is, p
∈
C
S
n
,
k
(
D
).Our hidden outlier detection (HOD) algorithm (Algorithm1) is based on the ORCA algorithm [18]. HOD searches k
+
n
-
1 nearest neighbors (in consideration of performance,n must be small) of every data block (lines (
4
)
–
(
7
)). Once an object is impossible to become an outlier, it will be removed from data block (line (
8
)). After processing a data block, HOD gets current D
n
-outlier (line (
10
)) and updates cutoff valuec (line (
11
)) and then maintains hidden outlier candidate set at the same time (lines (
12
)
–
(
16
)), including deleting the objects with smallerMPW thanc (lines (
13
)-(
14
)) and adding the objects with largerMPW thanc (lines (
15
)-(
16
)). Finally the candidate set is filtered to get the final results (Algorithm 2).Algorithm 1:Hidden outlier detection algorithm.
Input: k, n, D
Output: H
D
n
-outlier
(1)c
←
0;
(2)D
n
-
o
u
t
l
i
e
r
←
ϕ;
(3)B
←
ϕ; //B is a data block of dataset D
(4)while  B
← get-next-block(D)
(5)for each d in D
(6)for each b in B
(7)d
i
s
←
d
i
s
t
(
b
,
d); update b.NN
(8)if  M
P
W
n
,
k
(
b
,
D
)
<
c remove b from B;
(9)for each b in B
(10)D
n
-
o
u
t
l
i
e
r
←
T
O
P
(
B
∪
D
n
-
o
u
t
l
i
e
r
,
n
) //update D
n
-
o
u
t
l
i
e
r;
(11)c
←
w
k
(
D
n
,
k
,
D
)  //update c;
(12)for each cs in C
S
n
,
k
(
D
)
(13)if (M
P
W
n
,
k
(
c
s
,
D
)
<
c)
(14)      deletecs from C
S
n
,
k
(
D
);
(15)if (M
P
W
n
,
k
(
b
,
D
)
>
c)
(16)     insertb to C
S
n
,
k
(
D
);
(17)H
D
n
-
o
u
t
l
i
e
r
←
f
i
l
t
e
r
i
n
g process(D
n
-
o
u
t
l
i
e
r
,
C
S
n
,
k
(
D
));
(18)  returnH
D
n
-
o
u
t
l
i
e
r;Algorithm 2:Filtering process.
Input:  D
n
-
o
u
t
l
i
e
r, C
S
n
,
k
(
D
)
Output:  H
D
n
-
o
u
t
l
i
e
r
(1)H
D
1
,
k
=
D
1
,
k, delete D
1
,
k from C
S
n
,
k
(
D
);
(2)  Seti
=
1;
(3)for each cso in C
S
n
,
k
(
D
)
(4)if  (H
D
i
,
k
∈
c
s
o
.
N
N) updatecso.NN and H
w
k
(
c
s
o
,
D
);
(5)i++; H
D
i
,
k
←
T
O
P(C
S
n
,
k
(
D
)
,
1), delete it from C
S
n
,
k
(
D
) and insert to H
D
n
-outlier;
(6)if  (i
<
n)  do
line (3)
(7)  returnH
D
n
-outlier;Algorithm2 shows how the candidate set is filtered to get the final results. D
1
,
k is first moved from C
S
n
,
k(D) to H
D
n
-outlier (line 1), because the first outlier of D
n
-outlier and first outlier H
D
n
-outlier are the same. Then the last outlier of H
D
n
-outlier is checked to see whether it is a nearest neighbor of some objects in C
S
n
,
k(D). If yes, it is deleted from that object’ nearest neighbors and the hidden outlier degree H
w
k
(
c
s
o
,
D
) (lines 2
–
(
4
)) is updated. Next, the object with the largest hidden outlier degree in C
S
n
,
k(D) is moved to H
D
n
-outlier (line (
5
)), and the process goes back to line (
2
) until there aren outliers (line (
6
)).As Bay and Schwabacher indicated, ORCA [18] has O
(
N
) time complexity on average and O
(
N
2
) in the worst case. In contrast to ORCA [18], HOD searches more nearest neighbors and thus costs more time and memory space. Further, HOD prunes less normal objects and results in more distance computations. However, these do not increase HOD’s time complexity because as more data blocks have been processed, the cutoff valuec becomes larger and more normal objects will be pruned. In other words, the pruning mechanism is the same as ORCA [18]. After searching a data block’s nearest neighbors, HOD maintains an outlier candidate set and updates it after updatingc, which can be implemented by a fast priority queue. In addition, experimental results show that the candidate set size keeps constant as a whole with various dataset sizes, limiting the overhead of filtering process described in Algorithm 2.


## 4.2. Index Based Hidden Outlier Detection Algorithm

In order to speed up HOD algorithm, we draw on the experience of iORCA and develop a simple index based hidden outlier detection algorithm. As we discussed in Section2, iORCA is a very excellent distance-based improvement from ORCA, which is the state-of-the-art method in outlier detection. It is worth mentioning that the build index process (Algorithm 3) of iORCA is very simple and almost costs little time. However, the only fly in the ointment is that iORCA is short of pivot selection method. Addressing this shortcoming, we propose a simple but efficient pivot selection algorithm (Algorithm 4).Algorithm 3:Build index.
Input: D, pivot
Output: index L
(1)L
←
ϕ;
(2)for each o in D
(3)L
(
o
)
←
d
i
s
t
(
p
i
v
o
t
,
o
);
(4) sort(L); //sorted by the distance value in
//descending order
(5) returnL;Algorithm 4:Pivot selection.
Input: D, p
i
v
o
t
N
u
m
Output: p
i
v
o
t
(1)b
l
o
c
k
I
n
d
e
x
←
ϕ;
(2)B
←
g
e
t
P
a
r
t
O
f
D
a
t
a
S
e
t(D); //B is usually a data block of dataset D
(3) blockIndex← buildIndex(B
,
B
[
0
]);
(4) divide blockIndex intopartNum equal segments; //p
a
r
t
N
u
m
⩾
2
∗
p
i
v
o
t
N
u
m
and 10, every segment has the same number of points
(5) getpivotNum segments with smallest skip distance;
(6)pivot
← middle object of every smallest segment;
(7) returnpivot;The most important idea of iORCA is to update the cutoff value faster. In Algorithm3, we can see that, in order to achieve this goal, iORCA simply calculates the distance between every object to pivot (lines (
2
)-(
3
)) and then sort them from large to small (line (
4
)). Obviously, both the time and memory consuming of this index are very small.The largest difference between similarity search and outlier detection is that similarity search procedure may be used many times, for searching different object, while outlier detection procedure may be used for only several times, even just one time. That is a decision that their pivot selection method for building index will be different. Since similarity search always follows the rules of Offline Construction and Online Search [35, 36], it can spend more time to select pivots and build index, other than outlier detection to save time in this stage.As Bhaduri et al. said that if we select inlier points as pivots, the points farthest from them will be more likely to be the outliers [22]. To benefit from this, the goal of our pivot selection algorithm is to select density points as pivots. However, the accurate search of density points is too expensive. So, in our pivot selection algorithm, we only find out the approximate density regions (lines (
4
)-(
5
)) and then choose the middle point of these regions (line (
6
)).In addition, we only take a part of dataset to select pivots, and usually a data block is enough. Due to the small percentage of outliers, it is almost impossible to select outliers as pivots via this subset using our method. The flowchart of iHOD algorithm is shown in Figure2.Figure 2
The flow chart of iHOD algorithm.The stopping rule (Theorem9) of iORCA can be applied in iHOD as well to quickly stop updating the cutoff value.Theorem 9 (iORCA stopping rule [22]).
LetD be the dataset, let c be the cutoff value, let p be the pivot, and let x
t be any test point currently being tested by iORCA (or iHOD); if (9)
d
i
s
t
x
t
,
p
+
d
i
s
t
p
,
n
n
k
p
,
D
<
cthen iORCA (or iHOD) can terminate with the correct D
n-outlier and cutoff value.
In addition, we propose other rules to reduce the distance computing times.Theorem 10.
Ifdist
⁡
x
t
,
p
+
dist
⁡
p
,
n
n
k
+
n
-
1
p
,
D
<
c, then iHOD can stop updating hidden outlier candidate set.Theorem10 can be proved similar to Theorem 9.Theorem 11.
If(10)
d
i
s
t
x
i
,
p
-
d
i
s
t
x
j
,
p
>
d
i
s
t
x
i
,
n
n
k
x
i
,
Dthen x
i is no longer thek nearest neighbors of x
i.Proof.
Using Triangle Inequality, there is(11)
d
i
s
t
x
i
,
x
j
≥
d
i
s
t
x
i
,
p
-
dist
⁡
x
j
,
pso we have (12)
d
i
s
t
x
i
,
x
j
>
d
i
s
t
x
i
,
n
n
k
x
i
,
D
.In other words, x
j is faster than the kth nearest neighbor of x
i. So x
j is no longer the k nearest neighbors of x
i.Our index based hidden outlier detection algorithm (Algorithm5) combines iORCA (lines (
3
)
–
(
9
)) and HOD (lines (
13
)
–(24)) algorithms and updates them with pivot selection algorithm (line (
2
)) and Theorem 11 (line (12)), finally resulting in its high performance.Algorithm 5:Index based hidden outlier detection algorithm.
Input: k, n, D
Output: H
D
n
-
o
u
t
l
i
e
r
(1)c
←
0; D
n
-
o
u
t
l
i
e
r
←
ϕ; B
←
ϕ; //B is a data block of dataset D
(2)  pivot← pivotSelection(D
,
1);
(3)L
←
b
u
i
l
d
I
n
d
e
x(D
,
p
i
v
o
t); //L is a data block of dataset D
(4)while  B
←
get-next-block
(
L
(
D
)
)
(5)if (Theorem10 holds for
B
(
1
)) then break;
(6)else
(7)µ
←
f
i
n
d
A
v
g
(
L
(
B
)
);
(8)s
t
a
r
t
I
D
←
f
i
n
d
(
L
⩾
µ
);
(9)o
r
d
e
r
←
s
p
i
r
a
l
O
r
d
e
r(L.id, startID);
(10)for each d in D with order
(11)for each b in B
(12)if (Theorem11 doesn’t hold for
d
and
b
)
(13)d
i
s
←
d
i
s
t
(
b
,
d
); update b.NN
(14)if  M
P
W
n
,
k
(
b
,
D
)
<
c remove b from B;
(15)for each b in B
(16)if (Theorem9 doesn’t holds for
B
(
1
))
(17)D
n
-
o
u
t
l
i
e
r
←
T
O
P(B
∪
D
n
-
o
u
t
l
i
e
r
,
n)  //update D
n
-
o
u
t
l
i
e
r;
(18)c
←
w
k
(
D
n
,
k
,
D
) //update c;
(19)for each cs in C
S
n
,
k
(
D
)
(20)if (M
P
W
n
,
k
(
c
s
,
D
)
<
c)
(21)      deletecs from C
S
n
,
k
(
D
);
(22)if (M
P
W
n
,
k
(
b
,
D
)
>
c)
(23)     insertb to C
S
n
,
k
(
D
);
(24)H
D
n
-
o
u
t
l
i
e
r
←
f
i
l
t
e
r
i
n
g process(D
n
-
o
u
t
l
i
e
r
,
C
S
n
,
k
(
D
));
(25)  returnH
D
n
-
o
u
t
l
i
e
r;


## 5. Experimental Results

In this section, we compare HOD and iHOD algorithm with ORCA [18], iORCA [22], and LOF [17], three popular distance-based outlier detection algorithms, in both accuracy and efficiency.


### 5.1. Test Suite

We follow a common way [37] in constructing the test suite. Four popular real world classification datasets are picked from the UCI Machine Learning Repository [38], and then a few objects from a class of small cardinality together with other larger classes are finally picked as the test suite. The first dataset is from the KDD Cup 1999 dataset, used by Yang [37]. The first 20,000 TCP data of its ten percent version, which has 76 abnormal connections or outliers, are picked. The second dataset is from the Optdigits (short for Optical Recognition of Handwritten Digits) dataset. The first 10 records from class 0, served as outliers, together with other 3,447 records are picked. The third one is from the Breast Cancer Wisconsin (Diagnostic) dataset. The first 10 records of the malignant ones, served as outliers, are picked, making 367 as the total number of records. The last one is from the Heart Disease dataset. All records in class 4, serving as outliers, together with other records except in classes 1–3 are picked. Altogether, there are 203 records with 15 outliers in dataset 4.After a simple constructing, these four datasets are match for Hawkins’s outlier definition [12], which is generally acceptable.


### 5.2. Evaluation Methodology

In statistics, a receiver operating characteristic (ROC) or ROC curve is a graphical plot that illustrates the performance of a binary classifier system as its discrimination threshold is varied. The curve is created by plotting the true positive rate (TPR) against the false positive rate (FPR) at various threshold settings. Calculate the Area Under Curve (AUC), and the larger it is, the better it is.With regard to outlier detection, as mentioned before, letD be the dataset, let D be the dataset size, and let n be the various threshold setting parameter. In other words, when n is set as a specific value, the top-n outliers will be identified as outliers, and other |
D
|
-
n points in the dataset are regarded as inliers. So, for a specific n, we can get a couple value of TPR and FPR. Vary n from 0 to D; we can easily get the ROC curve and then calculate the AUC value.Obviously, the above calculation is in the case that neighbor numberk is specific. If we vary it, then we can get the AUC-k graphical plot, which make us easily see the outlier detection accuracy with regard to parameterk.


### 5.3. Experimental Results

The experiments were run on a desktop with Intel Core 3.40 GHz processor, 8 GB RAM, running Windows 7 Professional Service Pack 1. The algorithms were implemented in C++ and compiled with Visual Studio 2012 in Release Mode. Unless otherwise specified, both the parametersk in determining nearest neighbors and detecting outlier numbern are set as 10. The accuracy is first studied, then the running time and performance of pivot selection algorithm at last.


#### 5.3.1. Accuracy

The accuracy of the five algorithms, namely, HOD, ORCA [18], iHOD, iORCA [22], and LOF [17], is first studied by way of AUC. For each constant value ofk, the AUC values of the three algorithms with various values ofn are computed. Then the AUC values of various values ofk are plotted in Figure 3. Please note that ORCA uses O
k
s
u
m
(
k
,
n
) definition, and HOD uses its extensionalksum hidden outlier, while iORCA uses O
k
m
a
x
(
k
,
n
) definition, and iHOD useskmax hidden outlier.Figure 3
AUC values with various valuesk of five algorithms for four datasets.
(a)
KDD Cup 1999
(b)
Optdigits
(c)
Breast Cancer Wisconsin (Diagnostic)
(d)
Heart Disease DatasetIt can be seen that HOD and ORCA achieve higher AUC values than LOF for almost all of the cases, for the four datasets. Further, HOD is better than ORCA for most of the cases. For the cases when ORCA is better than HOD, the values are close to 1, and the difference is thus marginal. Also, we can see the appearance of iHOD and iORCA.To see the difference more clearly, we further compare the three algorithms by way of true positives (Figure4). Obviously, iHOD is the best in most cases while LOF is the worst for almost all of the cases. Particularly, the true positives of LOF are close to 0 for the KDD Cup 1999 and Optdigits dataset. In Figure 4(c), we can see that HOD and iHOD have got the true positives similar to ORCA and iORCA, respectively. This is because Breast Cancer Wisconsin (Diagnostic) dataset is free of outliers hidden by other ones.Figure 4
True positive values with various valuesn of five algorithms for four datasets.
(a)
KDD Cup 1999
(b)
Optdigits
(c)
Breast Cancer Wisconsin (Diagnostic)
(d)
Heart Disease DatasetIn order to see more details about the performance of iHOD, we also do some Non-Parametric Tests [39], including Friedman’s test [40] and Hochberg’s procedure [41]. However, even though Hochberg’s testing results show that the difference between iHOD and iORCA is insignificant, it can be seen from Figures 3 and 4 that iHOD has actually made improvements from iORCA, which is an excellent outlier detection algorithm. Table 1, which is the rankings of average true positives from Figure 4, also shows that iHOD outperforms iORCA.Table 1
Rankings obtained through Friedman’s test over average true positives of Figure4.
Algorithm
ORCA
HOD
LOF
iORCA
iHOD
Ranking
3.75
3.25
5
1.875
1.125


#### 5.3.2. Efficiency

As mentioned earlier, an extra piece of work of HOD and iHOD is to filter through the candidate set, which may cost much time if the candidate set size is too large. The candidate size with respect to values ofn (Figure 5) and dataset size (Figure 6) are plotted. The Breast Cancer Wisconsin (Diagnostic) dataset and the Heart Disease dataset are not included due to their tiny sizes. Clearly, the candidate set size is not strongly correlated to the dataset size, making its effect to the running time limited.Figure 5
HOD’s candidate set size with various values ofn.
(a)
KDD Cup 1999
(b)
OptdigitsFigure 6
HOD’s candidate set size with various dataset sizes.
(a)
KDD Cup 1999
(b)
OptdigitsThe running time of the seven algorithms for the KDD Cup 1999 dataset and the Optdigits dataset is listed in Figure7, respectively. Please note that HOD has better accuracy than ORCA [18] and LOF [17], while iHOD is better than almost all algorithms, as indicated in last section. To make the comparison fair, we extend ORCA and iORCA [22] to HORCA and HiORCA to achieve the same detection results of HOD and iHOD. That is, run ORCA or iORCAn times, while each time only one outlier is detected and is removed from following runs. The running time of HORCA and HiORCA is also listed in the tables.Figure 7
Running time (milliseconds) over KDD Cup 1999 and Optdigits datasets withk = 10 andn = 10.
(a)
KDD Cup 1999
(b)
OptdigitsThe figure shows clearly that the running time of LOF increases dramatically as the dataset size increases. HOD, with better accuracy, takes almost 1.5 times of the time as that of ORCA [18]. However, HORCA, with the equivalent accuracy as that of HOD, takes up to 9 times of the running time as that of HOD. To our surprise, iHOD runs even faster than iORCA [22]. This is because iHOD uses Theorem 10 to get a large reduction of distance calculation times.


#### 5.3.3. Performance of Pivot Selection Algorithm

In order to estimate the performance of pivot selection algorithm, we compare iORCA/iHOD with/without pivot selection algorithm, in both running time and distance calculation times. For the sake of accuracy, we ran every experiment setup for 10 times and then get their standard deviation and mean value.From Tables2 and 3, we can see that our pivot selection algorithm makes the experiment results very stable and even gets better results in mean value of running time and distance calculation times.Table 2
Standard deviation and mean value of running time (milliseconds) over KDD Cup 1999 dataset.
Size
5,000
10,000
15,000
20,000
Category
Standard deviation
Mean value
Standard deviation
Mean value
Standard deviation
Mean value
Standard deviation
Mean value
iORCA random
16.7
697.60
8.0
1,363.50
21.7
2,040.60
78.5
2,725.40
iORCA psm
4.9
688.10
8.1
1,379.10
34.6
2,098.20
26.1
2,717.60
iHOD random
39.0
216.70
96.4
368.10
54.6
405.60
33.6
458.80
iHOD psm
21.2
232.20
35.9
309.00
83.2
402.60
22.2
441.60Table 3
Standard deviation and mean value of distance calculation times (104 times) over KDD Cup 1999 dataset.
Size
5,000
10,000
15,000
20,000
Category
Standard deviation
Mean value
Standard deviation
Mean value
Standard deviation
Mean value
Standard deviation
Mean value
iORCA random
5.23
504.1
1.39
1,002.5
0.201
1,502.5
0.332
2,003.3
iORCA psm
0.00
501.4
0.059
1,002.0
0.048
1,502.5
0.157
2,003.0
iHOD random
30.04
124.4
56.23
197.7
28.54
209.8
20.85
223.2
iHOD psm
15.17
137.0
24.59
165.7
46.41
197.6
10.19
211.0As other popular outlier detection algorithms like ORCA [18], iORCA [22], and LOF [17], both HOD and iHOD have two parameters, which are nearest neighbor numberk and outlier numbern. However, for these two parameters, it is unwise to decrease their value in order to get improvement in efficiency, because it may seriously reduce the detection quality. In fact,k can be set refer to O
k
a
v
g
(
k
,
n
) an so on. Thoughn is in proportion to candidate set size, thereby increasing the running time. Fortunately,n depends on user’s requirement, so it is usually not large.


### 5.4. Analysis of Mistakenly Detection

As we all know, HOD and iHOD algorithms detect next outlier after excluding the detected outliers, so that they can detect more real outliers. Is there any possibility that the normal objects are mistakenly detected as outliers?To analyze easily, we letD be the dataset, let O
k
m
a
x
(
k
,
n
) be the original outlier definition, and let d be the dimension number of datasets; region D
1 with radius of r consists of n
1 objects, which include outlier p
1. Another region, D
2, with the same radius, consists of n
2 objects, including normal object p
2. According to distance-based outlier definition, there is n
1
<
n
2.The expected outlier degree ofp
1 and p
2, E
1
d
k and E
2
d
k, is as follows:(13)
E
1
d
k
=
r
k
n
1
1
/
d
E
2
d
k
=
r
k
n
2
1
/
d
.After taking outm objects from region D
1 and D
2 separately, the expected outlier degree of p
1 and p
2 becomes(14)
E
1
d
k
′
=
r
k
n
1
-
m
1
/
d
E
2
d
k
′
=
r
k
n
2
-
m
1
/
d
.The variation ofp
1 and p
2’s outlier degree should be(15)
Δ
1
=
r
k
n
1
-
m
1
/
d
-
r
k
n
1
1
/
d
Δ
2
=
r
k
n
2
-
m
1
/
d
-
r
k
n
2
1
/
d
.For ease of analysis, we can set(16)
n
1
-
m
=
n
1
m
1
n
2
-
m
=
n
2
m
2
.So that(17)
Δ
1
=
r
k
n
1
m
1
1
/
d
-
r
k
n
1
1
/
d
Δ
2
=
r
k
n
2
m
2
1
/
d
-
r
k
n
2
1
/
d
.BecauseΔ
1
>
0, Δ
2
>
0, we can compare their value via their ratio(18)
Δ
1
Δ
2
=
r
k
/
n
1
m
1
1
/
d
-
r
k
/
n
1
1
/
d
r
k
/
n
2
m
2
1
/
d
-
r
k
/
n
2
1
/
d
=
1
/
m
1
1
/
d
-
1
1
/
m
2
1
/
d
-
1
=
1
-
m
1
1
/
d
1
-
m
2
1
/
d
.Obviously, from formula (16), there is(19)
n
1
1
-
m
1
=
n
2
1
-
m
2
.Sincen
1
<
n
2, there is(20)
m
1
<
m
2
.As a result,Δ
1
/
Δ
2
>
1, which is Δ
1
>
Δ
2.In other words, the variation of outlier is larger than normal object, so that it is easier to be detected as outlier. However, owing to the complexity of dataset distribution and the limitations of distance-based outlier definition, it remains possible that a very few normal objects may be mistakenly detected.


## 5.1. Test Suite

We follow a common way [37] in constructing the test suite. Four popular real world classification datasets are picked from the UCI Machine Learning Repository [38], and then a few objects from a class of small cardinality together with other larger classes are finally picked as the test suite. The first dataset is from the KDD Cup 1999 dataset, used by Yang [37]. The first 20,000 TCP data of its ten percent version, which has 76 abnormal connections or outliers, are picked. The second dataset is from the Optdigits (short for Optical Recognition of Handwritten Digits) dataset. The first 10 records from class 0, served as outliers, together with other 3,447 records are picked. The third one is from the Breast Cancer Wisconsin (Diagnostic) dataset. The first 10 records of the malignant ones, served as outliers, are picked, making 367 as the total number of records. The last one is from the Heart Disease dataset. All records in class 4, serving as outliers, together with other records except in classes 1–3 are picked. Altogether, there are 203 records with 15 outliers in dataset 4.After a simple constructing, these four datasets are match for Hawkins’s outlier definition [12], which is generally acceptable.


## 5.2. Evaluation Methodology

In statistics, a receiver operating characteristic (ROC) or ROC curve is a graphical plot that illustrates the performance of a binary classifier system as its discrimination threshold is varied. The curve is created by plotting the true positive rate (TPR) against the false positive rate (FPR) at various threshold settings. Calculate the Area Under Curve (AUC), and the larger it is, the better it is.With regard to outlier detection, as mentioned before, letD be the dataset, let D be the dataset size, and let n be the various threshold setting parameter. In other words, when n is set as a specific value, the top-n outliers will be identified as outliers, and other |
D
|
-
n points in the dataset are regarded as inliers. So, for a specific n, we can get a couple value of TPR and FPR. Vary n from 0 to D; we can easily get the ROC curve and then calculate the AUC value.Obviously, the above calculation is in the case that neighbor numberk is specific. If we vary it, then we can get the AUC-k graphical plot, which make us easily see the outlier detection accuracy with regard to parameterk.


## 5.3. Experimental Results

The experiments were run on a desktop with Intel Core 3.40 GHz processor, 8 GB RAM, running Windows 7 Professional Service Pack 1. The algorithms were implemented in C++ and compiled with Visual Studio 2012 in Release Mode. Unless otherwise specified, both the parametersk in determining nearest neighbors and detecting outlier numbern are set as 10. The accuracy is first studied, then the running time and performance of pivot selection algorithm at last.


### 5.3.1. Accuracy

The accuracy of the five algorithms, namely, HOD, ORCA [18], iHOD, iORCA [22], and LOF [17], is first studied by way of AUC. For each constant value ofk, the AUC values of the three algorithms with various values ofn are computed. Then the AUC values of various values ofk are plotted in Figure 3. Please note that ORCA uses O
k
s
u
m
(
k
,
n
) definition, and HOD uses its extensionalksum hidden outlier, while iORCA uses O
k
m
a
x
(
k
,
n
) definition, and iHOD useskmax hidden outlier.Figure 3
AUC values with various valuesk of five algorithms for four datasets.
(a)
KDD Cup 1999
(b)
Optdigits
(c)
Breast Cancer Wisconsin (Diagnostic)
(d)
Heart Disease DatasetIt can be seen that HOD and ORCA achieve higher AUC values than LOF for almost all of the cases, for the four datasets. Further, HOD is better than ORCA for most of the cases. For the cases when ORCA is better than HOD, the values are close to 1, and the difference is thus marginal. Also, we can see the appearance of iHOD and iORCA.To see the difference more clearly, we further compare the three algorithms by way of true positives (Figure4). Obviously, iHOD is the best in most cases while LOF is the worst for almost all of the cases. Particularly, the true positives of LOF are close to 0 for the KDD Cup 1999 and Optdigits dataset. In Figure 4(c), we can see that HOD and iHOD have got the true positives similar to ORCA and iORCA, respectively. This is because Breast Cancer Wisconsin (Diagnostic) dataset is free of outliers hidden by other ones.Figure 4
True positive values with various valuesn of five algorithms for four datasets.
(a)
KDD Cup 1999
(b)
Optdigits
(c)
Breast Cancer Wisconsin (Diagnostic)
(d)
Heart Disease DatasetIn order to see more details about the performance of iHOD, we also do some Non-Parametric Tests [39], including Friedman’s test [40] and Hochberg’s procedure [41]. However, even though Hochberg’s testing results show that the difference between iHOD and iORCA is insignificant, it can be seen from Figures 3 and 4 that iHOD has actually made improvements from iORCA, which is an excellent outlier detection algorithm. Table 1, which is the rankings of average true positives from Figure 4, also shows that iHOD outperforms iORCA.Table 1
Rankings obtained through Friedman’s test over average true positives of Figure4.
Algorithm
ORCA
HOD
LOF
iORCA
iHOD
Ranking
3.75
3.25
5
1.875
1.125


### 5.3.2. Efficiency

As mentioned earlier, an extra piece of work of HOD and iHOD is to filter through the candidate set, which may cost much time if the candidate set size is too large. The candidate size with respect to values ofn (Figure 5) and dataset size (Figure 6) are plotted. The Breast Cancer Wisconsin (Diagnostic) dataset and the Heart Disease dataset are not included due to their tiny sizes. Clearly, the candidate set size is not strongly correlated to the dataset size, making its effect to the running time limited.Figure 5
HOD’s candidate set size with various values ofn.
(a)
KDD Cup 1999
(b)
OptdigitsFigure 6
HOD’s candidate set size with various dataset sizes.
(a)
KDD Cup 1999
(b)
OptdigitsThe running time of the seven algorithms for the KDD Cup 1999 dataset and the Optdigits dataset is listed in Figure7, respectively. Please note that HOD has better accuracy than ORCA [18] and LOF [17], while iHOD is better than almost all algorithms, as indicated in last section. To make the comparison fair, we extend ORCA and iORCA [22] to HORCA and HiORCA to achieve the same detection results of HOD and iHOD. That is, run ORCA or iORCAn times, while each time only one outlier is detected and is removed from following runs. The running time of HORCA and HiORCA is also listed in the tables.Figure 7
Running time (milliseconds) over KDD Cup 1999 and Optdigits datasets withk = 10 andn = 10.
(a)
KDD Cup 1999
(b)
OptdigitsThe figure shows clearly that the running time of LOF increases dramatically as the dataset size increases. HOD, with better accuracy, takes almost 1.5 times of the time as that of ORCA [18]. However, HORCA, with the equivalent accuracy as that of HOD, takes up to 9 times of the running time as that of HOD. To our surprise, iHOD runs even faster than iORCA [22]. This is because iHOD uses Theorem 10 to get a large reduction of distance calculation times.


### 5.3.3. Performance of Pivot Selection Algorithm

In order to estimate the performance of pivot selection algorithm, we compare iORCA/iHOD with/without pivot selection algorithm, in both running time and distance calculation times. For the sake of accuracy, we ran every experiment setup for 10 times and then get their standard deviation and mean value.From Tables2 and 3, we can see that our pivot selection algorithm makes the experiment results very stable and even gets better results in mean value of running time and distance calculation times.Table 2
Standard deviation and mean value of running time (milliseconds) over KDD Cup 1999 dataset.
Size
5,000
10,000
15,000
20,000
Category
Standard deviation
Mean value
Standard deviation
Mean value
Standard deviation
Mean value
Standard deviation
Mean value
iORCA random
16.7
697.60
8.0
1,363.50
21.7
2,040.60
78.5
2,725.40
iORCA psm
4.9
688.10
8.1
1,379.10
34.6
2,098.20
26.1
2,717.60
iHOD random
39.0
216.70
96.4
368.10
54.6
405.60
33.6
458.80
iHOD psm
21.2
232.20
35.9
309.00
83.2
402.60
22.2
441.60Table 3
Standard deviation and mean value of distance calculation times (104 times) over KDD Cup 1999 dataset.
Size
5,000
10,000
15,000
20,000
Category
Standard deviation
Mean value
Standard deviation
Mean value
Standard deviation
Mean value
Standard deviation
Mean value
iORCA random
5.23
504.1
1.39
1,002.5
0.201
1,502.5
0.332
2,003.3
iORCA psm
0.00
501.4
0.059
1,002.0
0.048
1,502.5
0.157
2,003.0
iHOD random
30.04
124.4
56.23
197.7
28.54
209.8
20.85
223.2
iHOD psm
15.17
137.0
24.59
165.7
46.41
197.6
10.19
211.0As other popular outlier detection algorithms like ORCA [18], iORCA [22], and LOF [17], both HOD and iHOD have two parameters, which are nearest neighbor numberk and outlier numbern. However, for these two parameters, it is unwise to decrease their value in order to get improvement in efficiency, because it may seriously reduce the detection quality. In fact,k can be set refer to O
k
a
v
g
(
k
,
n
) an so on. Thoughn is in proportion to candidate set size, thereby increasing the running time. Fortunately,n depends on user’s requirement, so it is usually not large.


## 5.3.1. Accuracy

The accuracy of the five algorithms, namely, HOD, ORCA [18], iHOD, iORCA [22], and LOF [17], is first studied by way of AUC. For each constant value ofk, the AUC values of the three algorithms with various values ofn are computed. Then the AUC values of various values ofk are plotted in Figure 3. Please note that ORCA uses O
k
s
u
m
(
k
,
n
) definition, and HOD uses its extensionalksum hidden outlier, while iORCA uses O
k
m
a
x
(
k
,
n
) definition, and iHOD useskmax hidden outlier.Figure 3
AUC values with various valuesk of five algorithms for four datasets.
(a)
KDD Cup 1999
(b)
Optdigits
(c)
Breast Cancer Wisconsin (Diagnostic)
(d)
Heart Disease DatasetIt can be seen that HOD and ORCA achieve higher AUC values than LOF for almost all of the cases, for the four datasets. Further, HOD is better than ORCA for most of the cases. For the cases when ORCA is better than HOD, the values are close to 1, and the difference is thus marginal. Also, we can see the appearance of iHOD and iORCA.To see the difference more clearly, we further compare the three algorithms by way of true positives (Figure4). Obviously, iHOD is the best in most cases while LOF is the worst for almost all of the cases. Particularly, the true positives of LOF are close to 0 for the KDD Cup 1999 and Optdigits dataset. In Figure 4(c), we can see that HOD and iHOD have got the true positives similar to ORCA and iORCA, respectively. This is because Breast Cancer Wisconsin (Diagnostic) dataset is free of outliers hidden by other ones.Figure 4
True positive values with various valuesn of five algorithms for four datasets.
(a)
KDD Cup 1999
(b)
Optdigits
(c)
Breast Cancer Wisconsin (Diagnostic)
(d)
Heart Disease DatasetIn order to see more details about the performance of iHOD, we also do some Non-Parametric Tests [39], including Friedman’s test [40] and Hochberg’s procedure [41]. However, even though Hochberg’s testing results show that the difference between iHOD and iORCA is insignificant, it can be seen from Figures 3 and 4 that iHOD has actually made improvements from iORCA, which is an excellent outlier detection algorithm. Table 1, which is the rankings of average true positives from Figure 4, also shows that iHOD outperforms iORCA.Table 1
Rankings obtained through Friedman’s test over average true positives of Figure4.
Algorithm
ORCA
HOD
LOF
iORCA
iHOD
Ranking
3.75
3.25
5
1.875
1.125


## 5.3.2. Efficiency

As mentioned earlier, an extra piece of work of HOD and iHOD is to filter through the candidate set, which may cost much time if the candidate set size is too large. The candidate size with respect to values ofn (Figure 5) and dataset size (Figure 6) are plotted. The Breast Cancer Wisconsin (Diagnostic) dataset and the Heart Disease dataset are not included due to their tiny sizes. Clearly, the candidate set size is not strongly correlated to the dataset size, making its effect to the running time limited.Figure 5
HOD’s candidate set size with various values ofn.
(a)
KDD Cup 1999
(b)
OptdigitsFigure 6
HOD’s candidate set size with various dataset sizes.
(a)
KDD Cup 1999
(b)
OptdigitsThe running time of the seven algorithms for the KDD Cup 1999 dataset and the Optdigits dataset is listed in Figure7, respectively. Please note that HOD has better accuracy than ORCA [18] and LOF [17], while iHOD is better than almost all algorithms, as indicated in last section. To make the comparison fair, we extend ORCA and iORCA [22] to HORCA and HiORCA to achieve the same detection results of HOD and iHOD. That is, run ORCA or iORCAn times, while each time only one outlier is detected and is removed from following runs. The running time of HORCA and HiORCA is also listed in the tables.Figure 7
Running time (milliseconds) over KDD Cup 1999 and Optdigits datasets withk = 10 andn = 10.
(a)
KDD Cup 1999
(b)
OptdigitsThe figure shows clearly that the running time of LOF increases dramatically as the dataset size increases. HOD, with better accuracy, takes almost 1.5 times of the time as that of ORCA [18]. However, HORCA, with the equivalent accuracy as that of HOD, takes up to 9 times of the running time as that of HOD. To our surprise, iHOD runs even faster than iORCA [22]. This is because iHOD uses Theorem 10 to get a large reduction of distance calculation times.


## 5.3.3. Performance of Pivot Selection Algorithm

In order to estimate the performance of pivot selection algorithm, we compare iORCA/iHOD with/without pivot selection algorithm, in both running time and distance calculation times. For the sake of accuracy, we ran every experiment setup for 10 times and then get their standard deviation and mean value.From Tables2 and 3, we can see that our pivot selection algorithm makes the experiment results very stable and even gets better results in mean value of running time and distance calculation times.Table 2
Standard deviation and mean value of running time (milliseconds) over KDD Cup 1999 dataset.
Size
5,000
10,000
15,000
20,000
Category
Standard deviation
Mean value
Standard deviation
Mean value
Standard deviation
Mean value
Standard deviation
Mean value
iORCA random
16.7
697.60
8.0
1,363.50
21.7
2,040.60
78.5
2,725.40
iORCA psm
4.9
688.10
8.1
1,379.10
34.6
2,098.20
26.1
2,717.60
iHOD random
39.0
216.70
96.4
368.10
54.6
405.60
33.6
458.80
iHOD psm
21.2
232.20
35.9
309.00
83.2
402.60
22.2
441.60Table 3
Standard deviation and mean value of distance calculation times (104 times) over KDD Cup 1999 dataset.
Size
5,000
10,000
15,000
20,000
Category
Standard deviation
Mean value
Standard deviation
Mean value
Standard deviation
Mean value
Standard deviation
Mean value
iORCA random
5.23
504.1
1.39
1,002.5
0.201
1,502.5
0.332
2,003.3
iORCA psm
0.00
501.4
0.059
1,002.0
0.048
1,502.5
0.157
2,003.0
iHOD random
30.04
124.4
56.23
197.7
28.54
209.8
20.85
223.2
iHOD psm
15.17
137.0
24.59
165.7
46.41
197.6
10.19
211.0As other popular outlier detection algorithms like ORCA [18], iORCA [22], and LOF [17], both HOD and iHOD have two parameters, which are nearest neighbor numberk and outlier numbern. However, for these two parameters, it is unwise to decrease their value in order to get improvement in efficiency, because it may seriously reduce the detection quality. In fact,k can be set refer to O
k
a
v
g
(
k
,
n
) an so on. Thoughn is in proportion to candidate set size, thereby increasing the running time. Fortunately,n depends on user’s requirement, so it is usually not large.


## 5.4. Analysis of Mistakenly Detection

As we all know, HOD and iHOD algorithms detect next outlier after excluding the detected outliers, so that they can detect more real outliers. Is there any possibility that the normal objects are mistakenly detected as outliers?To analyze easily, we letD be the dataset, let O
k
m
a
x
(
k
,
n
) be the original outlier definition, and let d be the dimension number of datasets; region D
1 with radius of r consists of n
1 objects, which include outlier p
1. Another region, D
2, with the same radius, consists of n
2 objects, including normal object p
2. According to distance-based outlier definition, there is n
1
<
n
2.The expected outlier degree ofp
1 and p
2, E
1
d
k and E
2
d
k, is as follows:(13)
E
1
d
k
=
r
k
n
1
1
/
d
E
2
d
k
=
r
k
n
2
1
/
d
.After taking outm objects from region D
1 and D
2 separately, the expected outlier degree of p
1 and p
2 becomes(14)
E
1
d
k
′
=
r
k
n
1
-
m
1
/
d
E
2
d
k
′
=
r
k
n
2
-
m
1
/
d
.The variation ofp
1 and p
2’s outlier degree should be(15)
Δ
1
=
r
k
n
1
-
m
1
/
d
-
r
k
n
1
1
/
d
Δ
2
=
r
k
n
2
-
m
1
/
d
-
r
k
n
2
1
/
d
.For ease of analysis, we can set(16)
n
1
-
m
=
n
1
m
1
n
2
-
m
=
n
2
m
2
.So that(17)
Δ
1
=
r
k
n
1
m
1
1
/
d
-
r
k
n
1
1
/
d
Δ
2
=
r
k
n
2
m
2
1
/
d
-
r
k
n
2
1
/
d
.BecauseΔ
1
>
0, Δ
2
>
0, we can compare their value via their ratio(18)
Δ
1
Δ
2
=
r
k
/
n
1
m
1
1
/
d
-
r
k
/
n
1
1
/
d
r
k
/
n
2
m
2
1
/
d
-
r
k
/
n
2
1
/
d
=
1
/
m
1
1
/
d
-
1
1
/
m
2
1
/
d
-
1
=
1
-
m
1
1
/
d
1
-
m
2
1
/
d
.Obviously, from formula (16), there is(19)
n
1
1
-
m
1
=
n
2
1
-
m
2
.Sincen
1
<
n
2, there is(20)
m
1
<
m
2
.As a result,Δ
1
/
Δ
2
>
1, which is Δ
1
>
Δ
2.In other words, the variation of outlier is larger than normal object, so that it is easier to be detected as outlier. However, owing to the complexity of dataset distribution and the limitations of distance-based outlier definition, it remains possible that a very few normal objects may be mistakenly detected.


## 6. Conclusions and Future Work

In this paper, we propose a new distance-based outlier definition to detect hidden outliers and design a corresponding detection algorithm, which excludes detected outliers to reduce their influence and improve the accuracy. Candidate set based method also avoids repeating detecting the whole dataset. Experimental results show that our HOD algorithm is more accurate than ORCA [18] and LOF [17]. Further, with better accuracy, HOD is much faster than LOF and is of comparable speed to that of ORCA. In addition, to achieve the same accuracy, ORCA takes up to 9 more times of running time than HOD. With the help of Triangle Inequality to reduce the distance calculation times, iHOD gets a much faster speed than iORCA and HiORCA. Moreover, we develop a pivot selection algorithm to avoid choosing outliers as pivots, and in experiments, we also show that our method can achieve stability of the results.Our definition and algorithm are extended from two distance-based outlier detection algorithms: ORCA [18] and iORCA [22]. The case of hidden outlier also exists for density-based outlier detection, which we will study in the future. Besides, we will further study how to choose right pivots to speed up our detection algorithm.



---

*Source: 8048246-2016-07-26.xml*