PhD Thesis Review, No.8

学位論文紹介A Study on Distance-based Outlier Detection on Uncertain Data
Salman Ahmed Shaikh
Graduate School of Systems and Information Engineering, University of Tsukuba, Japan
Email: salman@kde.cs.tsukuba.ac.jp
Uncertain data management, querying and mining havebecome important because the majority of real world data is
accompanied with uncertainty these days. Uncertainty in data
is often caused by the deficiency in underlying data collecting
equipments or sometimes manually introduced to preserve data
privacy. The uncertainty information in the data is useful andcan be used to improve the quality of the underlying results.
Therefore in this dissertation, three problems are being solved
related to outlier detection on uncertain data. 1) Distancebased outlier detection on uncertain data: In this research, wegive a novel definition of distance-based outliers on uncertain
data. Since the distance probability computation is expensive,a cell-based approach is proposed to index the dataset objects
and to speed up the outlier detection process. The cell-based
approach identifies and prunes the cells containing only inliers
based on its bounds on outlier score (#D-neighbors). Similarly
it can also detect the cells containing only outliers. 2) Topk outlier detection on uncertain data: In this work, a topk distance-based outlier detection approach is presented. Inorder to detect top-k outliers from uncertain data efficiently,
we propose a data structure, populated-cells list (PC-list).
Using the PC-list, the top-k outlier detection algorithm needs
to consider only a fraction of the dataset objects and hence
quickly identifies candidate objects for the top-k outliers. 3)
Continuous outlier detection on uncertain data streams: In
this part of the dissertation, a distance-based approach is
proposed to detect outliers continuously from a set of uncertain
objects’ states that are originated synchronously from a groupof data sources (e.g., sensors in WSN). A set of objects’ states
at a timestamp is called a state set. Usually, the duration
between two consecutive timestamps is very short and thestate of all the objects may not change much in this duration.
Therefore, to eliminate the unnecessary computation at every
timestamp, an incremental approach of outlier detection is
proposed which makes use of outlier detection results obtained
from the previous timestamp to detect outliers in the current
timestamp. Finally, extensive experimental evaluations on realand synthetic datasets are presented for each of the proposed
outlier detection approaches, to prove their accuracy, efficiency
and scalability.
I. Introduction
Outlier detection is a fundamental problem in data mining.
It has applications in many domains including credit card fraud
detection, network intrusion detection, environment monitoring, medical sciences etc. Several definitions of outlier havebeen given in past, but there exists no universally agreed upondefinition. Hawkins [1] defines an outlier as an observationthat deviates so much from other observations as to arousesuspicion that it was generated by a different mechanism.
In statistics, one can find over 100 outlier detection techniques. These have been developed for different data distributions, parameters, desired number of outliers and typeof expected outliers [2]. However, most of the statisticaltechniques are not useful due to several reasons. For example,
the majority of the statistical techniques are univariate, in sometechniques parameters are difficult to determine, and in othertechniques outliers cannot be obtained until the underlying
data distribution is known. In order to overcome these problems, several outlier detection techniques have been proposedin the data mining including nearest-neighbour based, densitybased, clustering-based and distance-based [3], [5]. In thisdissertation, our focus is the distance-based approach because
the distance-based approach is the simplest and the mostcommonly used. It can be used as preprocessing before applying more sophisticated application dependent outlier detection
techniques. Moreover, it coincides well with other data-mining
techniques, e.g., k-NN, clustering, etc.
The very first definition of distance-based outlier was given
by Knorr, et al. [3]. They defined an object o to be an outlier
if at most M = N(1 − p) objects are within D-distance ofo, where N is the number of objects in the dataset and pis the fraction of objects that lie farther than the D-distanceof o. They also presented a cell-based approach to efficiently
compute the distance-based outliers. S. Ramaswamy, et al. [5]formulated distance-based outliers as the top-t data objects
whose distances to their kth nearest neighbour is largest.
Angiulli et al. [6] gave a slightly different definition of outliers
than S. Ramaswamy, et al. [5] by considering the average
distance to their k nearest neighbours. Beside these, there aresome works on the detection of the distance-based outliers overstream data [7], [8]. These works are based on the definitionof distance-based outliers by Knorr, et al. [3]. Furthermore, F.
Angiulli, et al. [7] gave an approximate algorithm to reducethe memory space required by its exact counterpart. Later on
M. Kontaki, et al. [8] extended F. Angiulli, et al. work [7] byadding the concepts of multi-query and micro-cluster based
distance-based outlier detection. However all these approaches
were given for the deterministic data and cannot handle theuncertain data.
Due to the increasing usage of sensors, RFIDs, GPS andsimilar devices for data collection these days, data contains
certain degree of inherent uncertainty [4]. The causes of
uncertainty may include but are not limited to limitation ofequipments, absence of data, inconsistent supply voltage anddelay or loss of data in transfer [4]. In order to get reliable8-1

日本データベース学会

PhD Thesis Review, No.8

学位論文紹介results from such data, uncertainty needs to be considered in
calculation.
Driven by emerging requirements, recently a lot of research
has focused on managing, querying and mining of the uncertain data. The problem of outlier detection on the uncertain
data was first studied by Aggarwal, et al. [9]. According tothem, an uncertain object o is a density-based (δ, η) outlier,if the probability of existence of the o in some subspace of aregion with density at least η is less than δ. In order to compute(δ, η) outliers, firstly density of all the subspaces needs to becomputed and then the η-probability of each o in the dataset
is computed to tell if o is an outlier. Since this computation isvery expensive, a sampling procedure is used to approximate
the η-probability. In contrast to the Aggarwal, et al. work[9], this work addresses the detection of the distance-based
outliers in full space, where the distance probability between
two uncertain objects is computed by the Gaussian difference
distribution [10]. Therefore, the problem definition is quite
different from Aggarwal, et al. [9].
In this dissertation, our focus is the distance-based outlier
detection from the uncertain data of the Gaussian distribution.
We mainly used a cell-based technique to speed-up the outlier
detection process. Our main contributions are summarized asfollows.
• UDB-Outlier Detection: A cell-based approach of the
distance-based outlier detection on uncertain static data,summarized in Section II.
• kUDB Outlier Detection: A top-k outlier detection approach on uncertain data, summarized in Section III.
• CUDB-Outlier Detection: A continuous outlier detection
approach on uncertain data streams, presented in SectionIV.
II. Distance-based Outlier Detection on Uncertain Data
(UDB Outlier Detection)
In this section, a distance-based outlier detection approachon uncertain static data is presented. To obtain distance-based
outliers, distance probability needs to be computed between
uncertain data objects. However this computation is very
costly. Therefore a cell-grid structure is used to index dataset
objects and prune inliers and identify outliers.
In this work, d-dimensional uncertain objects oi are consid−→
ered, with attribute Ai = (xi,1 , ..., xi,d ) following the Gaussian−
PDF with mean →µi = (µi,1 , ..., µi,d ) and co-variance matrix−→
Σi = diag(σ2i,1 , ..., σ2i,d ), respectively. Namely, the vector Ai
is a random variable that follows the Gaussian distribution−→−−
Ai ∼ N(→µi , Σi ). Note that →µi denotes the observed coordinates(attribute values) of object oi . The complete database consistsof a set of such objects, GDB = {o1 , ..., oN }, where N = |GDB|.
Hence a distance-based outlier on the uncertain dataset isdefined as follows.
Definition 1: An uncertain object o in a database GDB isa distance-based outlier, if the expected number of objectsoi ∈ GDB (including o itself) lying within D-distance of o isless than or equal to threshold θ = N(1 − p), where N is thenumber of uncertain objects in database GDB, and p is thefraction of objects in GDB that lies farther than D-distance ofo.
The objects that lie within the D-distance of oi are called
its D-neighbors, and the set of the D-neighbors of oi andthe number of D-neighbours are denoted by DN(oi ) and #Dneighbors(oi), respectively. The distance probability between
two uncertain objects (oi and o j ) following the Gaussian
distribution is computed using the difference between two
Gaussian distributions, which is given by another distribution−→ −→known as the Gaussian difference distribution [10], |Ai − A j | =→−→−N(µi − µ j , Σi +Σ j ) [10]. Let Pr(oi , o j , D) denotes the probability
that the o j ∈ DN(oi ) and is defined as follows.
Z
→
−
−
−
Pr(oi , o j , D) =N(→µi − →µ j , Σi + Σ j )dA ,
(1)
R

−
−
where R is a sphere with centre (→µi − →µ j ) and radius D.
Cell-based Approach: Since the naive approach of the
distance-based outlier detection makes use of nested loop andis very expensive, a cell-based approach of outlier detection is
proposed in this work. To identify the distance-based outliers
using the cell-based approach, each object in GDB is quantized
to a 2-dimensional grid G that is partitioned into cells of lengthl (l is user-defined parameter). Let C x,y be a cell in G, where
positive integers x and y denote the cell indices. The layers(L1 , ..., Ln ) of C x,y ∈ G are the neighbouring cells of C x,y andare defined as follows.
L1 (C x,y ) ={Cu,v |u = x ± 1, v = y ± 1, Cu,v , C x,y }.

L2 (C x,y ) ={Cu,v |u = x ± 2, v = y ± 2, Cu,v < L1 (C x,y ), Cu,v , C x,y }.

L3 (C x,y ), ..., Ln(C x,y ) are defined in a similar way. In the sequel,
we will use C to denote C x,y when there is no confusion. To
identify the cells C ∈ G, containing only inliers or outliers,
their bounds on the #D-neighbours are used. The upper boundof a cell C, U B(C), binds the maximum #D-neighbors forany object in C, while the lower bound, LB(C), binds theminimum #D-neighbours for any object in C. To compute acell bounds, its and its layers object count, minimum andmaximum ordinary Euclidean distances between C and its
layers and pre-computed Pr(α, D) values are used. Interested
readers may refer to our work [11] for the details on bounds
calculation.
Based on the bounds, a cell C ∈ G can be pruned as inlier
if LB(C) > θ. On the other hand, if U B(C) ≤ θ, the C is
identified as an outlier cell. There may be some un-pruned
objects in the un-pruned cells even after the cell-basedpruning, for all such objects, the naive computation is used.

III. Top-k Outlier Detection on Uncertain Data (kUDB
Outlier Detection)
In the approach presented in Section II, an object can beeither classified as an outlier or an inlier. Different parameter
combinations return varying number of outliers and no outlier
ranking is available. Therefore in this section, a top-k approach8-2

日本データベース学会

PhD Thesis Review, No.8

学位論文紹介of the distance-based outliers on uncertain data is presented
and is defined as follows.
Definition 2: The top-k distance-based outliers are the kuncertain objects in the dataset GDB for which the expected
number of objects oi ∈ GDB lying within the D-distance issmallest.
To identify the top-k outliers efficiently, a populated-cells
list (PC-list) based approach is presented. A PC-list is an arrayof non-empty cells of the grid G, where grid is used to index
dataset objects. The cell-grid used in this section is similar
to the one defined in Section II except the regions RD−tσ andRD+tσ .

√ − 1 neighThe RD−tσ (C) denotes a region formed by D−tσl dbouring layers of C ∈ G as shown in Fig.2. The region
RD−tσ (C) is chosen in such a way that for each oi ∈ C
and o j ∈ RD−tσ (C), Pr(oi , o lj , D) ≈m 1. Similarly, the RD+tσ (C)denotes a region formed by D+tσ
neighbouring layers of celll
C ∈ G as shown in Fig.1. Region RD+tσ (C) is chosen in sucha way that for each oi ∈ C and o j < RD+tσ (C), the Pr(oi , o j , D)approaches zero.
Let N(C) be the number of objects in C, and ND−tσ (C)be the number of objects within cells in the region RD−tσ (C)(including C itself). Then the PC-list (PC) is a sorted list
containing N(C) and ND−tσ (C) for each non-empty cell C ∈ G
as shown in Fig.2. The tuples in the PC-list are sorted in
an ascending order of ND−tσ (C) column. The idea behindsorting is that outliers tend to exist in sparse regions. Sorting
tuples in the PC-list, lets us identify cells with few number ofneighbouring objects or cells in sparse regions.
A cell C can be pruned as the inlier cell or identified as thecell containing the top-k outlier candidates using its bounds on
the #D-neighbors. To compute the cell bounds, the minimum
and the maximum ordinary Euclidean distances between cells
are required. Besides this, the object count of each C ∈ PC
and the Pr(α, D) values for α ranging from the minimum tothe maximum ordinary Euclidean distances between cells in
the G are also required. The Pr(α, D) values are precomputed
and stored in a look-up table to be used by the top-k outlier
detection algorithm.
Let Ccell is a list for holding the candidate outlier cells fromthe PC-list, sorted in an ascending order of the U B(C). Let
C k ∈ Ccell is a cell with the minimum upper bound containing
the kth object. A C ∈ PC is a candidate outlier cell wheneverP′kC′ ∈Ccell N(C ) < k or LB(C) ≤ θ, where θ = U B(C ) denotes
the threshold.
For a C ∈ PC, if the LB(C) > θ, the C cannot contain anyof the top-k outliers and can be pruned. On the other hand,
if the LB(C) ≤ θ, the C may contain top-k outliers. The C
is added to the Ccell , such that the Ccell remain sorted of its
U B(C) attribute. Set the θ = U B(C k ) and remove the C ′ from
Ccell , such that the LB(C ′ ) > θ, as they cannot contain the
top-k outliers.
The PC-list is scanned from top to bottom for the candidate
outlier cells. During the scanning, if a C ′ ∈ PC is found suchthat Pr(D − tσ, D) ∗ ND−tσ (C ′ ) > θ, which is a lower bound on#D-neighbours of C ′ , the C ′ cannot contain the top-k outliersand can be pruned. Since the PC-list is sorted of the ND−tσ (C),any cell after the C ′ must have ND−tσ (C) ≥ ND−tσ (C ′ ). Hencethe lower bound of C ∈ PC after C ′ must be greater than orequal to the lower bound of C ′ ∈ PC and cannot contain the
top-k outliers. Hence the PC-list scanning can be stopped at
this point.
Finally, exact #D-neighbors is computed for each object in
the candidate outlier cells to find the top-k outliers and theirranking. Two approximate top-k outlier detection algorithms
are also presented in this work to increase the efficiency ofthe outlier detection. The first approximate algorithm only
approximates the candidate objects’ #D-neighbors, while thesecond approximate algorithm makes use of the bounded
Gaussian uncertainty to increase the efficiency of the top-k
outlier detection algorithm.
IV. Continuous Outlier Detection on Uncertain Data
Streams (CUDB Outlier Detection)
Since the data obtained from sensors, RFIDs and similar
devices is continuous and contain certain degree of uncertainty,
this section presents a continuous outliers detection approachon uncertain data streams. Here streams are the sequencesof objects’ states generated over time. Like the previous
works, this work assumes that the object’s uncertainty follows
the Gaussian distribution. Assuming that there are N objects−−→−−→
whose states may change over time and let S j = {A1j , ..., ANj }denotes a set of such objects at time t j , then the distance-based
outlier in uncertain data streams is defined as follows.
Definition 3: An uncertain object oi is a distance-based
outlier at time t j , if the expected number of objects in S j lying
within the D-distance of oi are less than or equal threshold toθ = N(1 − p), where N is the number of objects, and p is
the fraction of objects that lie farther than the D-distance ofoi ∈ S j .
A straightforward approach to identify the distance-based
outliers from the set of objects S j at every time t j , is to
execute the cell-based algorithm of Section II on S j at every
time instance. However according to our assumption, statesremain unchanged between two time instances for most of theobjects. Hence, processing all the objects in all the state setsis meaningless. Therefore, we propose an incremental outlier
detection approach based on change between S j−1 and S jusing the cell-based algorithm.
Let SC-Object denotes an object whose state have changed
from t j−1 to t j and S C j denotes a set of such objects at timet j . A differential processing is used to detect outliers from
S C j . The idea is to process only the objects which are either
themselves SC-Objects or are affected by the SC-Objects. In
this work, the cell-based approach of Section II is utilized toprocess the SC-Objects.
To simplify the problem, consider the case with one SCj
Object, o p . Let oi ∈ C x,yrepresent a cell C x,y containing oi attime t j . As a result of state change, o p ∈ G can move in thefollowing two ways.

8-3

日本データベース学会

PhD Thesis Review, No.8
o‹’’

z:o;

zp?šÌ :o;

%56

2

7

%55

1

10

%76

1

10

%66

2

13

1

%74

3

13

0

学位論文紹介

%64

3

14

%75

5

16

%65

2

19

4
ð6
2 3

Min distance
between o and xÛ

4½?ç :%56 ;& E Pê

%.5.6

4½>ç :%;

0.á

Fig. 1: Cell Layers and Bounds

1

2 3
ð5

4

Fig. 2: PC-list building[Case 1] o p moved to a different cell:
j−1
j
j−1
j
o p ∈ C x,y, o p ∈ C x,y, C x,y, C x,y.

j−1
jIn this case, o p affects cells C x,y, C x,y, their RD−tσ and RD+tσ
neighboring regions and all the objects in the un-pruned cells.
[Case 2] o p moved within a cell:
j−1
j
j−1
j
o p ∈ C x,y, o p ∈ C x,y, C x,y= C x,y.
j

Since the number of objects in the C x,y remain same asa result of the o p movement, the cell-based pruned cells
are not affected. However all the objects in the un-pruned
cells are affected, because the objects in the un-pruned cells
require the computation of their #D-neighbors. Since the #Dneighbors computation of an object o p require the Pr(o p , oq , D)computation of o p and each oq ∈ S j , even a slight movement
in any dataset object can influence its #D-neighbors.
In practise, there are more than one SC-Objects from timet j−1 to t j . Therefore, we expand the above idea to more thanone SC-Objects. For the incremental outlier processing, thecells requiring re-processing as a result of state change are
identified. Such cells are called the Target cells. Hence there
are following three types of target cells.
Type A: Cells containing SC-Objects which have moved toor from another cell at time t j .
Type B: RD−tσ and RD+tσ neighbouring cells of Type A cells,
except those classified as Type A cells.
Type C: Un-pruned cells of the grid G. Type C cells may
include Type A and B cells.
All three cell types, i.e., A, B and C require re-outlier detection
at time instance t j .
The main cost of the proposed approach lies in the processing of un-pruned objects in the Type C cells. The unpruned objects processing require the computation of their #Dneighbors. This is very expensive because the #D-neighbors
computation of an object o p require the Pr(o p , oq , D) computation of o p and each oq ∈ S . In the incremental algorithm, thiscost can be reduced by utilizing the #D-neighbors computedin the previous state. Namely, a Hash table is used to store
the Pr(o p , oq , D) values computed at time t j−1 . At time t j ,these values can be retrieved from the Hash table in O(1)time. Hence at time t j , the Pr(o p , oq , D) values need to becomputed only in two cases; 1) States of o p , oq or both havechanged, 2) Pr(o p , oq , D) is not available in the Hash table.
Since the un-pruned objects form a fraction of the complete
dataset, the memory required to hold the Hash table is not
significant. However it saves a lot of computation time. An

approximate approach using the bounded Gaussian uncertainty
is also proposed to increase the outlier detection efficiency.
V. Conclusions and Future WorkIn this work, we addressed the problem of distance-based
outlier detection on uncertain static data and uncertain data
streams and proposed three approaches. The UDB-Outlier andthe kUDB-Outlier are proposed for uncertain static data while
the CUDB-Outlier for uncertain data streams. The accuracy,efficiency and scalability of the proposed approaches areproved by extensive experiments on real and synthetic datasets(Please refer to the thesis for the detailed experiments).
In the future, one of the natural extension of this work is
the detection of the top-k outliers from uncertain data streams.
Since in the current work, object’s uncertainty is given by theGaussian distribution, its extension to other uncertainty models could be another interesting future direction. Moreover,extension of this work to handle very high dimensional data
is another useful future direction.
References[1] Hawkins, D.: Identification of Outliers. Chapman and Hall,
London (1980)[2] Maimon, O., Rockach, L.: Data Mining and Knowledge Discovery Handbook: A Complete Guide for Practitioners andResearchers. Kluwer Academic, Norwell (2005)[3] Knorr, E.M., Ng, R.T., Tucakov, V.: Distance-based outliers:
algorithms and applications. VLDBJ. 8(3-4), 237-253 (2000)[4] Sharma, A.B., Golubchik, L., Govindan, R.: Sensor faults:
detection methods and prevalence in real-world datasets. ACM
Trans. Sens. Netw. 6(3), 23:1-39 (2010)[5] Ramaswamy, S., Rastogi, R., Shim, K.: Efficient algorithms formining outliers from large datasets. In: ACM SIGMOD, pp.
427-438 (2000)[6] Angiulli, F., Pizzuti, C.: Fast outlier detection in high dim.
spaces. In: PKDD, pp. 15-26 (2002)[7] Angiulli, F., Fassetti, F.: Detecting distance-based outliers instreams of data. In: CIKM, pp. 811-820 (2007)[8] Kontaki, M., Gounaris, A., Papadopoulos, A.N., Tsichlas, K.,
Manolopoulos, Y.: Continuous monitoring of distance-based
outliers over data streams. In: ICDE, pp. 135-146 (2011)[9] Aggarwal, C.C., Yu, P.S.: Outlier detection with uncertain data.
In: SIAM International Conference on Data Mining, pp. 483-493(2008)[10] Weisstein,
E.W.:
NormalDifference
Distribution. From MathWorldA Wolfram Web Resource.
http://mathworld.wolfram.com/NormalDifferenceDistribution.
Accessed 27 Jan 2012[11] Shaikh, S.A., Kitagawa, H.: Efficient Distance-based Outlier
Detection on Uncertain Datasets of Gaussian Distribution. World
Wide Web, pp. 1–28 (2013)8-4

日本データベース学会