# A Probabilistic Transformation of Distance-Based Outliers

David Muhr 1,2, Michael Affenzeller 2,3 and Josef Küng 4

###### Abstract

The scores of distance-based outlier detection methods are difficult to
interpret, making it challenging to determine a cut-off threshold between
normal and outlier data points without additional context. We describe a
generic transformation of distance-based outlier scores into interpretable,
probabilistic estimates. The transformation is ranking-stable and increases
the contrast between normal and outlier data points. Determining distance
relationships between data points is necessary to identify the nearest-
neighbor relationships in the data, yet, most of the computed distances are
typically discarded. We show that the distances to other data points can be
used to model distance probability distributions and, subsequently, use the
distributions to turn distance-based outlier scores into outlier
probabilities. Our experiments show that the probabilistic transformation does
not impact detection performance over numerous tabular and image benchmark
datasets but results in interpretable outlier scores with increased contrast
between normal and outlier samples. Our work generalizes to a wide range of
distance-based outlier detection methods, and because existing distance
computations are used, it adds no significant computational overhead.

##  1 Keywords:

anomaly detection, outlier detection, outlier score, anomaly score, score
normalization

##  2 Introduction

We propose a generic method to transform distance-based outlier detection
models into interpretable, probabilistic models. An outlier is often described
as “an observation (or subset of observations) which appears to be
inconsistent with the remainder of that set of data” Barnett and Lewis (1978).
The definition of an “inconsistent” observation is not uniform and varies
depending on the application and algorithm used. Inconsistency can mean that
the outlier object stems from a different distribution than the model
describing the data, which reflects the classical definition of outliers by
Hawkins (1980): “An outlier is an observation which deviates so much from the
other observations as to arouse suspicions that it was generated by a
different mechanism. ”. An outlier is also referred to as an anomaly or
novelty, sometimes interchangeably. Therefore, outlier detection is also
referred to as anomaly detection or novelty detection. Because the methods
used to detect outliers, anomalies, and novelties are mostly the same, we make
no distinction between these terms and refer to inconsistent instances as
outliers. In a distance-based setting, we can define outliers as objects
located far away from the remaining objects.

Notation
---
$\displaystyle a$ |  A scalar (integer or real)
$\displaystyle{\boldsymbol{a}}$ |  A vector
$\displaystyle{\boldsymbol{A}}$ |  A matrix
a |  A scalar random variable
$\displaystyle{\mathbb{A}}$ |  A set
$\displaystyle{\mathcal{A}}$ |  A space
$\displaystyle A$ |  A distribution
$\displaystyle\mathbb{R}$ |  The set of real numbers
$\displaystyle{\mathbb{X}}$ |  A dataset
$\displaystyle\\{0,1,\dots,n\\}$ |  The set of all integers between $0$ and $n$
$\displaystyle f(x):{\mathbb{A}}\rightarrow{\mathbb{B}}$ |  A function of $x$ with domain ${\mathbb{A}}$ and range ${\mathbb{B}}$

Specifically, given a metric space $({\mathcal{M}},d)$ with metric $d$, each
object ${\boldsymbol{x}}\in{\mathcal{M}}$ receives a real-valued outlier score
$s:=q({\boldsymbol{x}})$ via a function $q:{\mathcal{M}}\to{\mathbb{R}}$,
where the function depends on the distances to the other objects in the
dataset. To determine if an observation is considered an outlier, it is
necessary to to establish a threshold value converting outlier scores into
binary labels of normal and outlier data points. A major challenge in
distance-based outlier detection is the interpretation of the resulting
scores. The scores provided by distance-based methods differ widely in their
scale, range, and meaning. Even when considering only a single outlier
detection method, the same outlier score can describe different degrees of
outlierness depending on the kind of data. These challenges make the
interpretation and comparison of outlier scores difficult. Distance-based
outlier detection scores are typically derived from some neighborhood
representation given a distance matrix. We propose that the information
contained in the distance matrix can be used to derive a probabilistic
normalization of outlier scores such that they become interpretable. Based on
a large number of benchmark datasets, we test our approach in terms of
detection performance and interpretability and show that it is possible to
achieve interpretable, probabilistic outlier scores with no detriment to the
resulting detection performance. The rest of this paper is organized as
follows. Section 3 provides an overview of distance-based outlier detection
methods. In Section 4, we show score normalization schemes and their
application to distance-based methods. In Section 5, we describe our proposed
probabilistic normalization scheme, and in Section 6, we describe the results
of applying our scheme on benchmark datasets. Finally, in Section 7, we derive
conclusions and provide opportunities for future research.

##  3 Distance-based Outlier Detection

In this section, we introduce and review common distance-based outlier
detection methods and formalize them as a scoring function
$q:{\mathcal{M}}\to{\mathbb{R}}$ on a metric space $({\mathcal{M}},d)$, such
that an outlier detection method assigns a real-valued outlier score to an
observation. We further differentiate between the closed-world and open-world
outlier detection setting, an often disregarded yet highly relevant aspect of
distance-based outlier detection. The following outlier detection methods are
formulated in a closed-world setting, such that the observations in a dataset
${\mathbb{X}}$ are assigned an outlier score. Often, however, it is necessary
to assign an outlier score to unseen data, such that a model of normality is
determined based on a dataset ${\mathbb{X}}$, and the outlier score is
determined on unseen observations in a dataset ${\mathbb{X}}_{\mathrm{test}}$.
At the end of this section, we provide a simple approach to transfer said
closed-world outlier detection methods into an open-world setting.

###  3.1 $k$-th Nearest Neighbors

Knorr and Ng (1997, 1998); Knorr et al. (2000) first formalized a distanced-
based notion of outliers in which an object ${\boldsymbol{x}}\in{\mathbb{X}}$
is said to be a DB-outlier in a dataset of $n$ objects if
$\left|\\{{\boldsymbol{x}}^{\prime}\in{\mathbb{X}}\mid
d({\boldsymbol{x}},{\boldsymbol{x}}^{\prime})>\delta\\}\right|\geq\alpha n$
where $\alpha,\delta\in{\mathbb{R}}$ are parameters to be specified by the
user and $0\leq\alpha\leq 1$. In this specification, a fraction $\alpha$ of
all objects have a distance from ${\boldsymbol{x}}$ that is larger than
$\delta$. Chandola et al. (2009) point out that this method can be viewed as
global density estimation for each instance since it involves counting the
number of neighbors in a hypersphere of radius $\delta$. However, a major
drawback of this definition is that it is difficult to determine a distance
threshold $\delta$ and that the results do not determine a ranking of scores.

Ramaswamy et al. (2000) build upon the ideas presented in DB-outliers. To
determine the outlier score of an instance, they propose to use the distance
to its $k^{\mathrm{th}}$-nearest neighbor as a score; thus, we refer to the
method as $k^{\mathrm{th}}\mathrm{NN}$. Compared to DB-outliers, the main
benefit of this approach is that it does not require the user to specify a
distance $\delta$. The $k^{\mathrm{th}}\mathrm{NN}$ outlier score of an
observation ${\boldsymbol{x}}$ is defined as

$q_{k^{\mathrm{th}}\mathrm{NN}}({\boldsymbol{x}}):=d^{(k)}({\boldsymbol{x}},{\mathbb{X}})$
(1)

where ${\boldsymbol{x}}\in{\mathbb{X}}$ and
$d^{k}({\boldsymbol{x}},{\mathbb{X}})$ is the distance between
${\boldsymbol{x}}$ and its $k^{\mathrm{th}}$ nearest neighbor in
${\mathbb{X}}$.

Angiulli and Pizzuti (2002) adapt the $k^{\mathrm{th}}\mathrm{NN}$ approach to
use the average distance to the $k$-nearest neighbors of a point
${\boldsymbol{x}}$ instead of the $k^{\mathrm{th}}$ distance, which can also
be interpreted as the maximum distance. We refer to this method as
$k\mathrm{NN}$ and define it as follows

$q_{k\mathrm{NN}}({\boldsymbol{x}}):=\frac{1}{k}\sum_{i=1}^{k}d^{(i)}({\boldsymbol{x}},{\mathbb{X}})$
(2)

where ${\boldsymbol{x}}\in{\mathbb{X}}$ and
$d^{(i)}({\boldsymbol{x}},{\mathbb{X}})$ is the distance between
${\boldsymbol{x}}$ and its $i^{\mathrm{th}}$ nearest neighbor in
${\mathbb{X}}$.

We propose to generalize $k^{\mathrm{th}}\mathrm{NN}$ and $k\mathrm{NN}$ as
specific instances of weighting schemes for distance-based outlier detection.
Weighting schemes are commonly used in $k$-nearest neighbors classification,
where the schemes traditionally emphasize close neighbors and disregard
neighbors farther away Geler et al. (2016). However, as evident in
$k^{\mathrm{th}}\mathrm{NN}$-based outlier detection, where only the farthest
neighbor is considered, we propose to emphasize the neighbors farther away. A
further difference between weighted-neighbors classification and outlier is
the predicted result, which corresponds to class votes or outlier scores. To
keep the resulting outlier scores in the same range, we propose to sum-
normalize the weights such that the resulting weight vectors sum to one. The
resulting outlier scores can subsequently be interpreted as a (smoothened)
distance or distance probability. We adapt three of the weighting measures
investigated in Geler et al. (2016) to the outlier detection task and describe
$k^{\mathrm{th}}\mathrm{NN}$ as max-weighted and $k\mathrm{NN}$ as mean-
weighted outlier detection. The distance and rank schemes are adapted from
Dudani’s weighted nearest neighbor classification Dudani (1976), the
exponential scheme from Zavrel (1997), and the linear scheme from Macleod et
al. (1987). In all cases, we reverse the schemes such that the farthest
neighbor gets the largest weight. We define the schemes for a vector of
$k$-nearest neighbor distances ${\boldsymbol{d}}$ as follows

$\displaystyle{\boldsymbol{w}}_{\max}({\boldsymbol{d}})$
$\displaystyle=[0,0,\ldots,1]$ (3)
$\displaystyle{\boldsymbol{w}}_{\mathrm{mean}}({\boldsymbol{d}})$
$\displaystyle=\left[\frac{1}{k},\frac{1}{k},\ldots,\frac{1}{k}\right]$ (4)
$\displaystyle{\boldsymbol{w}}_{\mathrm{distance}}({\boldsymbol{d}},s)$
$\displaystyle=[d_{1}^{s},d_{2}^{s},\ldots,d_{n}^{s}]$ (5)
$\displaystyle{\boldsymbol{w}}_{\mathrm{exponential}}({\boldsymbol{d}},a,b)$
$\displaystyle=[\exp(ad_{1}^{b}),\exp(ad_{2}^{b}),\ldots,\exp(ad_{n}^{b})]$
(6) $\displaystyle{\boldsymbol{w}}_{\mathrm{linear}}({\boldsymbol{d}})$
$\displaystyle=[\mathrm{norm}(d_{1}),\mathrm{norm}(d_{2}),\ldots,\mathrm{norm}(d_{n})]$
(7) $\displaystyle{\boldsymbol{w}}_{\mathrm{rank}}({\boldsymbol{d}})$
$\displaystyle=[1,2,\ldots,k]$ (8)

where ${\boldsymbol{w}}_{\max}$ is $1$ only if $d_{i}=\max({\boldsymbol{d}})$,

$\mathrm{norm}=\frac{d_{i}-\min({\boldsymbol{d}})}{\max({\boldsymbol{d}})-\min({\boldsymbol{d}})},$
(9)

and $s$, $a$ and $b$ are hyperparameters of the respective weighting schemes.
We show how the weights influence the determination of an outlier score based
on a three-nearest-neighbors example in Figure 1.

Figure 1:  Different weighting schemes for three nearest neighbors with
distances $\exp([0.5,1.0,1.5])$ and fixed hyperparameters $s=a=b=1$.

Because outlier scores are assumed to be positive values derived from
distances, sum-normalization is possible by dividing each element in the
weight vector by its sum as defined in Equation 10. Sum-normalization ensures
that the weight vector sums to one and the weighted outlier score can be
interpreted as a weighted distance. We further use the proposed weighting
scheme to define a generic weighted $k$-nearest neighbor approach as
$\mathrm{kNNW}$, which serves as a basis for our tabular outlier detection
experiments in Section 6.

$q_{\mathrm{kNNW}}({\boldsymbol{x}}):=\frac{{\boldsymbol{d}}\cdot{\boldsymbol{w}}}{\sum_{i=1}^{k}w_{i}}$
(10)

where ${\boldsymbol{d}}$ is the vector of $k$-nearest neighbor distances,
${\boldsymbol{w}}$ is the $k$-dimensional weight vector and $\cdot$ denotes
the dot product between the distance- and weight vector.

More recently, authors proposed various sampling schemes to improve the
efficiency of the described techniques. Wu and Jermaine (2006) propose an
iterative sampling scheme to approximate the $k^{\mathrm{th}}\mathrm{NN}$
score, which we designate as $k^{\mathrm{th}}$ iteratively sampled nearest
neighbor $k^{\mathrm{th}}\mathrm{ISNN}$.

$q_{k^{\mathrm{th}}\mathrm{ISNN}}({\boldsymbol{x}}):=d^{(k)}({\boldsymbol{x}},S_{{\boldsymbol{x}}}({\mathbb{X}}))$
(11)

where $S_{{\boldsymbol{x}}}({\mathbb{X}})$ is a randomly sampled subset of
${\mathbb{X}}$ excluding ${\boldsymbol{x}}$. The subsampling is determined
individually for each point ${\boldsymbol{x}}^{\prime}$ processed with
$q_{k^{\mathrm{th}}\mathrm{ISNN}}({\boldsymbol{x}}^{\prime})$; therefore, it
is referred to as iterative sampling.

Sugiyama and Borgwardt (2013) show that a simplification of
$k^{\mathrm{th}}\mathrm{ISNN}$ leads to better detection performance over 16
different datasets. The authors propose to remove the iterative aspect of
$k^{\mathrm{th}}\mathrm{ISNN}$ and, instead, sample only once for all data
points and identify the first nearest neighbor, which we describe as the
sampled nearest neighbor or $\mathrm{SNN}$.

$q_{\mathrm{SNN}}({\boldsymbol{x}}):=\underset{{\boldsymbol{x}}^{\prime}\in
S({\mathbb{X}})}{\min}d({\boldsymbol{x}},{\boldsymbol{x}}^{\prime})$ (12)

where $S({\mathbb{X}})$ is an independent random subset of the data that is
determined once. In other words, for a point ${\boldsymbol{x}}$, this method
uses the distance to its closest point ${\boldsymbol{x}}^{\prime}$ in a fixed
sample $S({\mathbb{X}})$ as an outlier score.

Pang et al. (2015) extend the $\mathrm{SNN}$ approach by repeatedly sampling
random subsets of the data, which we term repeatedly sampled nearest neighbor
$\mathrm{RSNN}$.

$q_{\mathrm{RSNN}}({\boldsymbol{x}}):=\frac{1}{r}\sum_{i=1}^{r}\underset{{\boldsymbol{x}}^{\prime}\in
S_{i}({\mathbb{X}})}{\min}d({\boldsymbol{x}},{\boldsymbol{x}}^{\prime})$ (13)

where $r$ is the number of random subsets to sample and $S_{i}({\mathbb{X}})$
is the $i$-th random sample. This method essentially represents an ensemble of
nearest neighbor outlier detection models and, therefore, expectedly improves
upon $\mathrm{SNN}$, which the authors empirically show using 11 datasets. It
can be argued that $k$-nearest neighbors ensembles with data subsampling are a
generalization of $\mathrm{RSNN}$, which are well-known techniques to improve
neighbor-based outlier detection Zimek et al. (2013); Aggarwal and Sathe
(2015); Muhr and Affenzeller (2022b).

In addition to data sampling techniques, other authors use randomized sampling
to determine feature subspaces as initially motivated by Aggarwal and Yu
(2002). Kriegel et al. (2009b) define a set of reference points based on the
concept of shared nearest neighbors. The reference points characterize a
subspace hyperplane, and the outlier scores are determined by the Euclidean
distance of a point ${\boldsymbol{x}}$ to the subspace hyperplane, weighted by
an indicator function that determines the relevance of a dimension. Agrawal
(2009) proposes a very similar distance-based subspacing approach. Zhang et
al. (2015) also use a shared nearest neighbor reference set to determine
subspaces, using an angle-based approach to compute the outlier scores.
Trittenbach and Böhm (2019) propose a method to determine subspaces that
considers the relationship between subspaces. Keller et al. (2012) propose to
determine high-contrast subspaces for outlier detection as a form of data pre-
processing. Cabero et al. (2021) also determine the subspaces as a data pre-
processing step based on archetypal analysis followed by a
$k^{\mathrm{th}}\mathrm{NN}$ approach.

Some authors combine distance-based outlier detection with dimensionality
reduction techniques such as principal component analysis Dang et al. (2015)
for high-dimensional data. In image-based outlier detection, authors use
neural networks to evaluate the neighborhood search in latent spaces
describing entire images Bergman et al. (2020), image sub-features Cohen and
Hoshen (2021), or image patch-features Roth et al. (2022).

Another option to model distance-based outliers is to use reverse nearest
neighbors or natural neighbors relationships. For example, Outlier Detection
using Indegree Number (ODIN) Hautamaki et al. (2004) models the nearest
neighbor relationships as a directed graph and defines the outlier score as
the in-degree number in the graph such that a low in-degree number defines an
outlier. Radovanović et al. (2015) analyze the concept of hubness, which
appears in reverse nearest neighbors outlier detection, and propose an outlier
detection method based on anti-hubs; points that do not occur in the nearest
neighbors of any other points. Natural neighbors approaches discard the
$k$-nearest neighbors parameter and instead perform a search over $\lambda$
rounds to identify an appropriate number of neighbors such that a shared
neighbor relationship is found Zhu et al. (2016); Wahid and Annavarapu (2021).
A further extension is described by extended nearest neighbor approaches,
which combine the nearest neighbors with reverse nearest neighbors and shared
nearest neighbors Tang and He (2015, 2017).

###  3.2 Local Outlier Factor

In contrast to the previously described techniques, referred to as global
outlier detection techniques, the Local Outlier Factor (LOF) Breunig et al.
(2000) model introduces the concept of local outliers. Schubert et al. (2014b)
formalize distance-based outlier detection models such that an outlier score
is determined based on some context set, typically the $k$-nearest neighbors
of a point ${\boldsymbol{x}}$. To compare the resulting outlier scores,
another set of points is used, which is referred to as the reference set.
Global methods compare the resulting score from the context set to all other
points in the reference set, the dataset ${\mathbb{X}}$. Because the
comparison of scores is global, those methods ignore differences in the local
densities of the data. Local methods use a different reference set to compare
the scores to, typically, the $k$-nearest neighbors as in the context set.
Local methods convert the distance information from the local neighborhood
into some form of density; therefore, the methods are sometimes also referred
to as density-based. LOF can be defined as a scoring function

$q_{\mathrm{LOF}}({\boldsymbol{x}}):=p({\boldsymbol{x}})^{-1}\left(\left|N^{k}({\boldsymbol{x}})\right|^{-1}\sum_{{\boldsymbol{x}}^{\prime}\in
N^{k}({\boldsymbol{x}})}p({\boldsymbol{x}}^{\prime})\right)$ (14)

where $N^{k}({\boldsymbol{x}})$ is the set of $k$-nearest neighbors of
${\boldsymbol{x}}$ and $p$ is the local reachability density of
${\boldsymbol{x}}$ defined as
$p({\boldsymbol{x}}):=|N^{k}({\boldsymbol{x}})|^{-1}\sum_{{\boldsymbol{x}}^{\prime}\in
N^{k}({\boldsymbol{x}})}\max\\{d^{k}({\boldsymbol{x}}^{\prime},{\mathbb{X}}),d({\boldsymbol{x}},{\boldsymbol{x}}^{\prime})\\}$.
Note that $N^{k}({\boldsymbol{x}})$ includes all objects inside the
$k^{\mathrm{th}}$-distance, which can, in the case of a “tie”, be more than
$k$ objects. The local reachability density can be seen as an average inverse
distance of a point ${\boldsymbol{x}}$ normalized such that the distance
cannot be smaller than the $k^{\mathrm{th}}$-distance. According to the
authors, the local reachability density stabilizes and prevents statistical
fluctuations, a fact later analyzed in more detail by Schubert et al. (2014a).
The local outlier factor then compares $p({\boldsymbol{x}})$, the density of
the context set, to the average reachability density of the points in the
reference set. If the average reachability density in the reference set is
higher than the point density obtained from the context set, then the score of
the local outlier factor is above one and considered less normal.

Schubert et al. (2014b) propose a simplified version of the local outlier
factor where $p$ is the inverse $k^{\mathrm{th}}$-distance
$p({\boldsymbol{x}}):=d^{k}({\boldsymbol{x}},{\mathbb{X}})^{-1}$, which
represents a simpler density estimate as compared to the local reachability
density in $\mathrm{LOF}$. To better illustrate the general concept of local
outlier detection, the simplified local outlier factor ($\mathrm{SLOF}$) can
be stated as follows

$q_{\mathrm{SLOF}}({\boldsymbol{x}}):=\frac{\underset{{\boldsymbol{x}}^{\prime}\in
N^{k}({\boldsymbol{x}})}{\mathrm{mean}}(d^{k}({\boldsymbol{x}}^{\prime},{\mathbb{X}})^{-1})}{d^{k}({\boldsymbol{x}},{\mathbb{X}})^{-1}}.$
(15)

The authors show that many local outlier models can be considered variations
of the simplified local outlier factor model. For example, LDOF proposed by
Zhang et al. (2009) is a variation of the simplified LOF model using an
average distance as in $k\mathrm{NN}$ instead of the
$k^{\mathrm{th}}$-distance. Influence Outlierness (INFLO) Jin et al. (2006) is
another variation of the simplified LOF, which diverges by using a different
context set that includes reverse nearest neighbors. Another method that can
be seen as an extension of the simplified LOF is Local Outlier Probabilities
(LoOP) Kriegel et al. (2009a), which adds a probabilistic normalization to
$\mathrm{SLOF}$. Many more local outlier detection methods have been described
in the literature covering entire literature reviews Alghushairy et al.
(2021). Schubert et al. (2014a) note that local outlier detection methods can
be differentiated using their order of locality, and Goodge et al. (2022) show
that the methods can be generalized as message-passing algorithms on a nearest
neighbors graph.

###  3.3 Closed-world and Open-world

Distance-based outlier detection methods are typically defined in a closed-
world setting; however, there is an important difference between the closed-
world and open-world specification such that, for two equal points
${\boldsymbol{x}}\in{\mathbb{X}}$,
${\boldsymbol{x}}^{\prime}\in{\mathbb{X}}_{\mathrm{test}}$ and
${\boldsymbol{x}}={\boldsymbol{x}}^{\prime}$, the $k^{\mathrm{th}}$ nearest
neighbor in ${\mathbb{X}}$ is different. In the closed-world or transductive
setting, the search for the $k$-nearest neighbors does not include the
searched-for point ${\boldsymbol{x}}$; in other words, the nearest neighbors
graph does not include self-loops. In the open-world setting, it is not known
if ${\boldsymbol{x}}^{\prime}$ is contained in the reference set
${\mathbb{X}}$, and therefore all points in ${\mathbb{X}}$ are included in the
$k$-nearest neighbors search. All of the referenced methods are described in a
closed-world setting and do not explicitly state how to perform inductive
outlier detection, yet commonly used toolkits for (distance-based) outlier
detection focus on the open-world setting Zhao et al. (2019); Muhr et al.
(2022), with no clear guidelines on how to transfer the transductive tasks to
inductive tasks. In Section 5, we describe our method in the transductive,
closed-world, and inductive, open-world setting.

##  4 Outlier Score Normalization

As mentioned in the introduction, the outlier scores resulting from distance-
based approaches differ widely in their meaning and are challenging to
interpret. In some cases, even within a data set, the scores for two different
observations can denote different degrees of outlierness, depending on
different local data distributions, a core motivation for local outlier
detection methods. Some distance-based methods provide probability estimates,
for example, Kriegel et al. (2009a, 2012); Janssens et al. (2012); van Stein
et al. (2016), but these probabilistic interpretations are a core part of the
underlying algorithms and cannot easily be transferred to other algorithmic
approaches. Latecki et al. (2007) developed an outlier detection model based
on local kernel density estimates. Schubert et al. (2014a) more generally
analyze the connection of density-based outlier detection algorithms, such as
the local distance-based methods, to kernel density estimation. The authors
show that distance-based density estimation is closely related to kernel
density estimation and claim that local outlier detection methods use
heuristics to determine, perhaps coincidentally, something similar to a
statistical kernel for density estimation.

Instead of algorithm-specific probabilistic interpretations, some authors
propose outlier score normalization schemes independent of the underlying
algorithm. A simple way of bringing outlier scores to a common scale is to
apply a linear transformation as defined in Equation 9, such that the minimum
score is mapped to 0 and the maximum score is mapped to 1. However, such a
min-max scaling approach does not yield a useful probabilistic interpretation.
Gao and Tan (2006) propose two approaches to model outlier scores as
probabilities. In the first approach, they assume that the posterior
probabilities follow a logistic sigmoid function. In the second approach, they
assume that the outlier scores follow a mixture of exponential and Gaussian
distributions. In both cases, the authors propose to use an expectation
maximization approach to learn the parameters. Kriegel et al. (2011) point out
that expectation maximization approaches to score normalization often converge
to a “no outliers” or “all outlier” solution and, instead, propose to use the
cumulative distribution function of a Gaussian or Gamma distribution to
normalize the scores. Additionally, the authors show the usefulness of post-
processing techniques to ensure an expected value of 0 for normal data points
or to increase the contrast between normal and outlier data points. Schubert
et al. (2012) note that a rank-based normalization can be useful if little
knowledge available about the actual scores and score distributions.

###  4.1 Interpretability, Explanation, and Trustworthiness

The interpretability of outlier predictions should not be confused with the
explanation of outlier detection models or the trustworthiness of predictions;
therefore, for the ongoing discussion, we differentiate the terms as follows
and describe them in detail following our differentiation.

  * •

Interpretability: The ability to judge the relevance of a prediction.

  * •

Explanation: The ability to explain the reasoning behind a prediction.

  * •

Trustworthiness The ability to describe the confidence behind a prediction.

Explanation is sometimes also referred to as interpretation, but this kind of
interpretation is separate from interpretability. Explanation algorithms
reveal how models make decisions, but interpretability refers to the intrinsic
property in which degree an inference result is understandable to human beings
Li et al. (2022). There is a growing interest in methods for deriving
explanations of outliers, that is, “[…] to give the users of some outlier
detection method further aid in understanding and evaluating the result with
respect to their domain.” Zimek and Filzmoser (2018). Explanations highlight
why a specific outlier detection model reaches a particular prediction. A
common approach to explain outlier predictions is to compare normal data
points and outliers in attribute subspaces in which the given outliers show
separability from the normal data Micenková et al. (2013); Vinh et al. (2016);
Macha and Akoglu (2018). Other authors derive explanations from statistical
models of the normal and outlier data using minimum distance estimation
Angiulli et al. (2013). The explanation of learning methods and outlier
detection methods is discussed extensively in a research field known as
Explainable Artificial Intelligence, or XAI Samek et al. (2019). Explanations
can uncover hidden weaknesses of a model, also known as “Clever Hanses”
Lapuschkin et al. (2019). The Clever Hans Effect occurs when the learned model
produces correct predictions based on the “wrong” features, which appears to
be a widespread problem in outlier detection Kauffmann et al. (2020). Another
critical aspect of outlier detection predictions is trustworthiness.
Trustworthiness describes an understanding of when a prediction should or
should not be trusted Lee and See (2004); Jiang et al. (2018); Ovadia et al.
(2019). To achieve better trustworthiness in outlier detection predictions,
Perini et al. (2021) propose to use a Bayesian approach to add probabilistic
uncertainty estimates to outlier scores, enabling the detector to assign a
confidence score to each prediction, which captures its uncertainty in that
prediction.

##  5 Probabilistic Outlier Scores

In this section, we derive a generic scheme to transform distance-based
outlier detection scores into interpretable outlier scores based on distance
probabilities. In the generic score normalization approaches mentioned in
Section 4.1, only the actual scores are used for normalization. Conversely,
the algorithm-specific normalization schemes are generally not easily
transferrable to other algorithms. A common theme across a vast majority of
distance-based outlier detection methods is the determination of nearest
neighbors relationships between data points. Determining exact nearest
neighbors relationships typically utilizes the computation of all distance
relationships between data points resulting in a distance matrix
${\boldsymbol{M}}$. Additionally, it has been shown that brute-force distance
computation is preferable to index methods except for low-dimensional
similarity search problems Muhr and Affenzeller (2022a). We note that
approximate nearest neighbors approaches are also used for distance-based
outlier detection strategies Kirner et al. (2017), but this represents a small
minority of methods and is not the focus of our study. In the closed-world
setting, the distance matrix corresponds to a square matrix of
${\mathbb{R}}^{n\times n}$ values for $n$ points in the dataset. In the open-
world setting, the distance matrix between $n$ reference points
${\mathbb{R}}^{n\times n}$ has to be differentiated from the distance matrix
of $m$ query points to $n$ reference points ${\mathbb{R}}^{m\times n}$. For a
point ${\boldsymbol{x}}_{i}$ and a point ${\boldsymbol{x}}_{j}$, a value
$v_{i,j}$ in the distance matrix corresponds to the distance
$d({\boldsymbol{x}}_{i},{\boldsymbol{x}}_{j})$. Most distance-based approaches
use the $k$-nearest neighbors as a context set to determine the outlier score
Schubert et al. (2014b), and any probabilistic estimate of those scores would
be based on the limited information present in the context set. In contrast to
previous approaches, we assume that the additional information contained in
the distance matrix is useful for normalization. More concretely, we
hypothesize that the additional information can be used to transform outlier
scores into interpretable probabilistic estimates.

Based on a distance matrix of reference points, we define the concept of a
normalization set. A normalization set describes a subset of the distance
matrix used for the probabilistic score normalization. In the simplest case
the entire distance matrix is used as a baseline normalization set; hence, the
normalization set is defined as the distances contained in the distance matrix
${\boldsymbol{M}}$ between all reference points excluding self-loops in the
matrix diagonal. Additionally, if the distance measure is symmetric, the
normalization set from the distance matrix can be reduced to its upper or
lower triangular set of values.

Figure 2:  Visualization of the reference points as a normalization set, where
the dotted blue lines indicate the connection of the query point to its
nearest neighbors in the reference set, and the gray lines indicate the
distance relationships between the reference points.

We propose using the normalization set to determine a distance probability
distribution. For example, in the parametric case, we estimate the parameters
of a distribution $P$ based on the distances in the normalization set. The
distribution of distances has been investigated in the context of feature
similarity Burghouts et al. (2007), hubness reduction Schnitzer et al. (2012),
local intrinsic dimensionality Houle (2013) or compact sets Lellouche and
Souris (2020). Pekalska and Duin (2000) show, based on the central limit
theorem, that distances are approximately normally distributed for independent
and identically distributed feature vectors. Under the assumption that the
distances in the normalization set follow an unknown continuous probability
distribution, we define a random variable ${\textnormal{r}}\sim P$ that
describes the normalization set. Given a probability density function $p$ on
r, any distance $d({\boldsymbol{x}},{\boldsymbol{x}}^{\prime})$ can be
interpreted as the distance density between ${\boldsymbol{x}}$ and
${\boldsymbol{x}}^{\prime}$ denoted
$p(d({\boldsymbol{x}},{\boldsymbol{x}}^{\prime}))$ or, in short,
$p({\boldsymbol{x}},{\boldsymbol{x}}^{\prime})$. The cumulative distance
distribution
$f({\boldsymbol{x}},{\boldsymbol{x}}^{\prime}):=P({\textnormal{r}}\leq
d({\boldsymbol{x}},{\boldsymbol{x}}^{\prime}))$ describes the probability of a
distance in the normalization set being smaller or equal to
$d({\boldsymbol{x}},{\boldsymbol{x}}^{\prime})$. A query point with some
distance-based outlier score can be directly interpreted using its distance
distribution, where a probability of 99% means that the distance is in the
Top-1% of distances observed in the normalization set.

In summary, we hypothesize that it is possible to transform distances to
interpretable distance distributions without adverse effects on detection
performance. We use the Receiver Operating Characteristic (ROC) Area Under the
Curve (AUC) to measure outlier detection performance. A perfect ranking
results in a ROC AUC value of 1, whereas an inverted perfect ranking would
result in a value of 0. A value of $1/2$ can be interpreted as random guessing
Campos et al. (2016). To investigate our assumption, we test our approach in
tabular datasets Campos et al. (2016); Muhr and Affenzeller (2022c), and a
common image-based outlier detection dataset Bergmann et al. (2019, 2021).

##  6 Results

To evaluate the probabilistic transformation on tabular data, we use the
proposed weighted $k$-nearest neighbor approach ($\mathrm{kNNW}$). The
datasets used stem from the DAMI Campos et al. (2016) library and the UTSD
single-concept benchmark Muhr and Affenzeller (2022c). For both dataset
collections, we only use the datasets with five percent of outliers, each
consisting of ten randomly sampled variants, resulting in the dataset list
shown in Table 1. For DAMI, we use the normalized and deduplicated variants,
and for UTSD, we pre-process the data points with min-max scaling. We use two-
fold, stratified cross-validation to determine a ROC AUC estimate of the
resulting distance-based and probabilistic estimates. We use Euclidean
distance for all evaluations and fix the hyperparameters for the weighting
schemes as $s=a=b=1$, as shown in Figure 1. For the number of neighbors $k$ of
our tested $\mathrm{kNNW}$ method, we pick the best parameter from all
possible values of $k\in[1,2,\ldots,100]$.

Table 1: The datasets used for $k$-nearest neighbors evaluation, where $N$ denotes the number of samples, $O$ the number of outliers, and $d$ the dimensionality of the dataset. Dataset | $N$ | $O$ | $d$ | Source | Ref.
---|---|---|---|---|---
Annthyroid | 6942 | 347 | 21 | ELKI | Dua and Graff (2017)
Arrhythmia | 256 | 12 | 259 | ELKI | Dua and Graff (2017)
Cardiotocography | 1734 | 86 | 21 | ELKI | Dua and Graff (2017)
CinCECGTorso | 373 | 18 | 1639 | UTSD | Goldberger et al. (2000)
Crop | 1052 | 52 | 46 | UTSD | Tan et al. (2017)
Earthquakes | 387 | 19 | 512 | UTSD | Dau et al. (2019)
ECG5000 | 3072 | 153 | 140 | UTSD | Goldberger et al. (2000)
ECGFiveDays | 465 | 23 | 136 | UTSD | Dau et al. (2019)
ElectricDevices | 4500 | 225 | 96 | UTSD | Dau et al. (2019)
FaceAll | 344 | 17 | 131 | UTSD | Dau et al. (2019)
FordA | 2660 | 133 | 500 | UTSD | Dau et al. (2019)
FordB | 2380 | 119 | 500 | UTSD | Dau et al. (2019)
FreezerRegularTrain | 1578 | 78 | 301 | UTSD | Murray et al. (2015)
HandOutlines | 921 | 46 | 2709 | UTSD | Davis (2013)
HeartDisease | 157 | 7 | 13 | ELKI | Dua and Graff (2017)
Hepatitis | 70 | 3 | 19 | ELKI | Dua and Graff (2017)
InternetAds | 1682 | 84 | 1555 | ELKI | Dua and Graff (2017)
ItalyPowerDemand | 575 | 28 | 24 | UTSD | Keogh et al. (2006)
MedicalImages | 625 | 31 | 99 | UTSD | Dau et al. (2019)
MixedShapesRegularTrain | 793 | 39 | 1024 | UTSD | Wang et al. (2010)
MoteStrain | 721 | 36 | 84 | UTSD | Sun et al. (2005)
PageBlocks | 5139 | 256 | 10 | ELKI | Dua and Graff (2017)
Parkinson | 50 | 2 | 22 | ELKI | Dua and Graff (2017)
PhalangesOutlinesCorrect | 1787 | 89 | 80 | UTSD | Davis (2013)
Pima | 526 | 26 | 8 | ELKI | Dua and Graff (2017)
SemgHandGenderCh2 | 568 | 28 | 1500 | UTSD | Sapsanis et al. (2013)
SonyAIBORobotSurface2 | 635 | 31 | 65 | UTSD | Mueen et al. (2011)
SpamBase | 2661 | 133 | 57 | ELKI | Dua and Graff (2017)
Stamps | 325 | 16 | 9 | ELKI | Micenková et al. (2015)
StarLightCurves | 5607 | 280 | 1024 | UTSD | Rebbapragada et al. (2009)
Strawberry | 369 | 18 | 235 | UTSD | Dau et al. (2019)
TwoLeadECG | 611 | 30 | 82 | UTSD | Goldberger et al. (2000)
UWaveGestureLibraryAll | 589 | 29 | 945 | UTSD | Liu et al. (2009)
Wafer | 6738 | 336 | 152 | UTSD | Olszewski (2001)
Yoga | 1863 | 93 | 426 | UTSD | Dau et al. (2019)
|  |  |  |  |

In our first analysis, we compare the performance of different weighting
schemes over all described datasets. We find that, over all datasets, there is
no difference in predictive performance between the different weighting
schemes. There can be more considerable weighting scheme differences for
individual datasets; however, those are dataset-specific and must be
investigated case-by-case, as shown in Figure 3. We also note that weighting-
scheme hyperparameter optimization might yield additional improvements, which
we did not address in our analysis. In our second analysis, we investigate the
impact of score normalization using different probability distributions. We
examine a normal, exponential, and empirical distribution and compare it to
the base case where no distribution is used for normalization. Because the
cumulative distribution functions are monotonically non-decreasing, the
ranking should be stable after the transformation, but due to the limited
precision of the computations, it is not guaranteed that the transformation is
ranking stable. In Figure 4, we show that the ROC AUC result after the
transformation matches the original result and the transformation is indeed
ranking stable. From an interpretability perspective, there are datasets where
using the entire distance matrix as a normalization set results in useful
probabilistic estimates, for example, the Crop dataset shown in Figure 5.

Figure 3:  ROC AUC results of the different weighting schemes for each dataset
over all examined distributions.  Figure 4:  ROC AUC results of different
probability distributions for each dataset over all weighting schemes, where
’none’ denotes the original scores without normalization.  Figure 5:
Transformation of distances to an exponential cumulative distance distribution
for the first variant of the Crop dataset.

However, using the entire distance matrix for normalization often leads to low
probabilistic estimates for normal and outlier data points. The reason is that
the resulting weighted neighbor distance is consistently low compared to all
other distances in the dataset, even for outliers. In this case, a different
normalization set has to be extracted from the distance matrix; for example,
the $m$-neighborhood consisting of the distances to the $m$-closest reference
points.

It is possible to analyze multiple normalization sets for a single prediction
to provide more context for interpretation. For example, a prediction can be
interpreted using different neighborhood probabilities from
$m\in[1,2,\ldots,200]$ to determine an appropriate cut-off threshold. The cut-
off decision always relies on the data characteristics and domain knowledge.
In Figure 8, we plot the optimal cut-off threshold for different neighborhood
sizes, but note that this optimal threshold is often difficult to determine.
To evaluate an optimal cut-off threshold, it is necessary to evaluate it
against a performance metric such as the F1-score requiring normal and outlier
labeled data, which is often unavailable. However, using a probabilistic
neighborhood analysis as shown in Figure 8 drastically simplifies the
identification of a cut-off value, even when labels are unavailable. Thus, in
addition to the improved interpretability, choosing an appropriate
normalization set allows for a flexible definition of a cut-off threshold to
transform outlier scores into class labels. Furthermore, it is possible to
increase the contrast between normal and outlier data points using the right
normalization set and distribution. Using statistical distances as a measure
of contrast between normal and outlier scores, we can identify an optimal
normalization set size. To give an example for the TwoLeadECG dataset, the
statistical measures of contrast result in a contrast-optimal neighborhood
size of $m=90$ or $m=99$ depending on the statistical distance used, with a
cut-off threshold of approximately 95%, as shown in Figure 8. In Figure 6 and
Figure 7, we compare the initial probabilistic estimates using the entire
distance matrix to the smaller, local normalization set identified in Figure 8
and clearly demonstrate the increased contrast using a smaller normalization
set.

Figure 6:  Transformation of distances to an exponential distance distribution
for the first variant of the TwoLeadECG dataset showing low outlier
probability.  Figure 7:  Exponential distance distribution using the 99
element neighborhood as a normalization set for the first variant of the
TwoLeadECG dataset to achieve a suitable cut-off threshold and increased
contrast.  Figure 8:  Each blue line refers to the probabilistic outlier score
of the first TwoLeadECG dataset variant. The green and red lines show the
statistical distance between the normal score distribution and the outlier
score distribution, with the dashed vertical lines depicting the corresponding
maximum contrast value. The orange dashed line shows the F1-score optimal cut-
off.

For image-based datasets, we extend the PatchCore methodology Roth et al.
(2022) to ProbabilisticPatchCore. We evaluate the model on the datasets
provided by MVTecAD, as shown in Table 2. A major difference between tabular
$k$-nearest neighbors outlier detection and image outlier detection is that
the image models may result in pixel-wise and image-wise outlier scores. In
the pixel-wise case, each pixel of an observation is scored and in the image-
wise case a single score is obtained for the entire image.

Table 2: MVTecAD Bergmann et al. (2021) image datasets for the evaluation of ProbabilisticPatchCore. Dataset | Train (normal) | Test (normal) | Test (outlier) | Masks | Groups | Shape
---|---|---|---|---|---|---
Carpet | 280 | 28 | 89 | 97 | 5 | $1024\times 1024$
Grid | 264 | 21 | 57 | 170 | 5 | $1024\times 1024$
Leather | 245 | 32 | 92 | 99 | 5 | $1024\times 1024$
Tile | 230 | 33 | 84 | 86 | 5 | $840\times 840$
Wood | 247 | 19 | 60 | 168 | 5 | $1024\times 1024$
Bottle | 209 | 20 | 63 | 68 | 3 | $900\times 900$
Cable | 224 | 58 | 92 | 151 | 8 | $1024\times 1024$
Capsule | 219 | 23 | 109 | 114 | 5 | $1000\times 1000$
Hazelnut | 391 | 40 | 70 | 136 | 4 | $1024\times 1024$
Metal Nut | 220 | 22 | 93 | 132 | 4 | $700\times 700$
Pill | 267 | 26 | 141 | 245 | 7 | $800\times 800$
Screw | 320 | 41 | 119 | 135 | 5 | $1024\times 1024$
Toothbrush | 60 | 12 | 30 | 66 | 1 | $1024\times 1024$
Transistor | 213 | 60 | 40 | 44 | 4 | $1024\times 1024$
Zipper | 240 | 32 | 119 | 177 | 7 | $1024\times 1024$
|  |  |  |  |  |

The PatchCore model is similar to $k^{\mathrm{th}}\mathrm{NN}$, but uses a
core-set sampled memory bank of patch-wise feature vectors that are generated
using a pre-trained neural network. For PatchCore, the pixel-wise scores are
determined through interpolation of the patch-wise scores; thus, it is not
necessary to estimate a distance distribution per pixel, but one distribution
per patch. Like the authors, we use the second and third layer of a
WideResNet50 trained on ImageNet Deng et al. (2009) to determine $28\times 28$
patches. To transform the pixel-wise scores into probabilistic estimates, we
learn a patch-wise distributions and transform the scores to probabilistic
estimates accordingly. In Figure 9, we highlight the challenge of
interpretability based on a normal data sample; without additional context, it
is not clear how to interpret the resulting distance-based scores. In addition
to the improved interpretability, we find that the probabilistic normalization
greatly increases the contrast between normal and outlier data points in the
image detection tasks as visible in Figure 10.

Figure 9:  Patch-wise scores of a normal sample of the Bottle dataset showing
interpretability differences.  Figure 10:  Patch-wise scores of an outlier
sample of the Bottle dataset exhibiting increased contrast.

##  7 Conclusion

We show that it is possible to transform distance-based outlier scores into
interpretable probabilistic estimates. To demonstrate the viability of our
approach, we derive and test a generalized, weighted $k$-nearest neighbors
outlier detection model on a several tabular datasets and a probabilistic
PatchCore model on image datasets. We show that the resulting probabilistic
scores increase the contrast between normal and outlier data points and can
easily be added to existing distance-based outlier detection methods. In
contrast to previous score normalization techniques, which use solely the
information contained in the outlier scores to derive a normalization, we make
use of the distances to other data points as an additional source of
information for normalization. Another interesting aspect of our analysis is
showing that the probabilistic transformation increases the contrast between
normal and outlier points, which should be further explored. Specifically, we
find that there might be an optimal normalization set that maximially
increases the contrast between normal and outlier points and future research
is necessary to define measures of contrast and methods to identify an optimal
normalization set for a given contrast measure. Because distance-based outlier
detection techniques rely on distance computations for nearest neighbors
search, our approach can be applied to a wide range of detection techniques.
In our experiments, we use the common Euclidean distance metric, but other,
possibly non-metric, distance measures are also used for outlier detection,
and should also be investigated using our probabilistic score transformation.
We investigated only the most apparent normalization sets, but there may be
various other useful normalization sets hidden in the distances between
points. Another limitation of our examination is the usage of real-world
datasets, which limits the theoretical analysis of our approach, such as the
normalization behaviour under specific dataset distributions. Our proposed
normalization approach should be investigated more thoroughly in a theoretical
setting to identify the limits of our approach and potentially proof some of
the properties observed in our evaluation. Our proposed generalization of
weighted nearest neighbors outlier detection should be analysed in more detail
to thoroughly compare weighting strategies and weighting hyperparameters. A
large body of research investigates sampling and subspacing techniques for
distance-based outlier detection and future researchers should evaluate the
usefulness of probabilistic intepretations for such models. Another important
area of outlier detection research is how to combine different detection
models into ensembles that improve upon the individual models, which typically
necessitates score normalization and, therefore, could benefit from
probabilistic normalization. We further highlight the importance of a
distinction between the open-world and closed-world setting for distance-based
outlier detection and propose such a distinction for future distance-based
methods.

## Conflict of Interest Statement

The authors declare that the research was conducted in the absence of any
commercial or financial relationships that could be construed as a potential
conflict of interest.

## Author Contributions

DM devised the ideas presented in this paper and wrote the first draft of the
manuscript. All authors contributed to manuscript revision, read, and approved
the submitted version.

## Data Availability Statement

The datasets for this investigation can be found in DAMI, UTSD, and MVTecAD.
The code to reproduce the experiments can be found on GitHub.

## References

  * Aggarwal and Yu (2002) Aggarwal, C. and Yu, P. (2002).  Outlier Detection for High Dimensional Data.  _ACM SIGMOD Record_ 30\.  10.1145/376284.375668
  * Aggarwal and Sathe (2015) Aggarwal, C. C. and Sathe, S. (2015).  Theoretical Foundations and Algorithms for Outlier Ensembles.  _SIGKDD Explor. Newsl._ 17\.  10.1145/2830544.2830549
  * Agrawal (2009) Agrawal, A. (2009).  Local Subspace Based Outlier Detection.  In _Contemporary Computing_ , eds. S. Ranka, S. Aluru, R. Buyya, Y.-C. Chung, S. Dua, A. Grama, S. K. S. Gupta, R. Kumar, and V. V. Phoha (Berlin, Heidelberg: Springer Berlin Heidelberg), Communications in Computer and Information Science.  10.1007/978-3-642-03547-0_15
  * Alghushairy et al. (2021) Alghushairy, O., Alsini, R., Soule, T., and Ma, X. (2021).  A Review of Local Outlier Factor Algorithms for Outlier Detection in Big Data Streams.  _BDCC_ 5\.  10.3390/bdcc5010001
  * Angiulli et al. (2013) Angiulli, F., Fassetti, F., and Palopoli, L. (2013).  Discovering Characterizations of the Behavior of Anomalous Subpopulations.  _IEEE Transactions on Knowledge and Data Engineering_ 25\.  10.1109/TKDE.2012.58
  * Angiulli and Pizzuti (2002) Angiulli, F. and Pizzuti, C. (2002).  Fast Outlier Detection in High Dimensional Spaces.  In _Principles of Data Mining and Knowledge Discovery_ , eds. G. Goos, J. Hartmanis, J. van Leeuwen, J. G. Carbonell, J. Siekmann, T. Elomaa, H. Mannila, and H. Toivonen (Berlin, Heidelberg: Springer Berlin Heidelberg), Lecture Notes in Computer Science.  10.1007/3-540-45681-3_2
  * Barnett and Lewis (1978) Barnett, V. and Lewis, T. (1978).  _Outliers in Statistical Data_ (John Wiley & Sons, Inc)
  * Bergman et al. (2020) Bergman, L., Cohen, N., and Hoshen, Y. (2020).  Deep nearest neighbor anomaly detection.  _CoRR_ abs/2002.10445
  * Bergmann et al. (2021) Bergmann, P., Batzner, K., Fauser, M., Sattlegger, D., and Steger, C. (2021).  The MVTec Anomaly Detection Dataset: A Comprehensive Real-World Dataset for Unsupervised Anomaly Detection.  _Int J Comput Vis_ 129\.  10.1007/s11263-020-01400-4
  * Bergmann et al. (2019) Bergmann, P., Fauser, M., Sattlegger, D., and Steger, C. (2019).  MVTec AD — A Comprehensive Real-World Dataset for Unsupervised Anomaly Detection.  In _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_.  10.1109/CVPR.2019.00982
  * Breunig et al. (2000) Breunig, M. M., Kriegel, H.-P., Ng, R. T., and Sander, J. (2000).  LOF: Identifying Density-Based Local Outliers.  In _Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data: 2000, Dallas, Texas, United States, May 15- 8, 2000_ , eds. M. Dunham, J. F. Naughton, W. Chen, and N. Koudas (New York, NY, USA: Association for Computing Machinery).  10.1145/342009.335388
  * Burghouts et al. (2007) Burghouts, G., Smeulders, A., and Geusebroek, J.-m. (2007).  The Distribution Family of Similarity Distances.  In _Advances in Neural Information Processing Systems_ (Curran Associates, Inc.), vol. 20
  * Cabero et al. (2021) Cabero, I., Epifanio, I., Piérola, A., and Ballester, A. (2021).  Archetype analysis: A new subspace outlier detection approach.  _Knowledge-Based Systems_ 217\.  10.1016/j.knosys.2021.106830
  * Campos et al. (2016) Campos, G. O., Zimek, A., Sander, J., Campello, R. J. G. B., Micenková, B., Schubert, E., et al. (2016).  On the evaluation of unsupervised outlier detection: Measures, datasets, and an empirical study.  _Data Min Knowl Disc_ 30\.  10.1007/s10618-015-0444-8
  * Chandola et al. (2009) Chandola, V., Banerjee, A., and Kumar, V. (2009).  Anomaly detection.  _ACM Comput. Surv._ 41\.  10.1145/1541880.1541882
  * Cohen and Hoshen (2021) [Dataset] Cohen, N. and Hoshen, Y. (2021).  Sub-Image Anomaly Detection with Deep Pyramid Correspondences
  * Dang et al. (2015) Dang, T. T., Ngan, H. Y., and Liu, W. (2015).  Distance-based k-nearest neighbors outlier detection method in large-scale traffic data.  In _2015 IEEE International Conference on Digital Signal Processing (DSP)_.  10.1109/ICDSP.2015.7251924
  * Dau et al. (2019) Dau, H. A., Bagnall, A., Kamgar, K., Yeh, C.-C. M., Zhu, Y., Gharghabi, S., et al. (2019).  The UCR time series archive.  _IEEE/CAA Journal of Automatica Sinica_ 6\.  10.1109/JAS.2019.1911747
  * Davis (2013) Davis, L. M. (2013).  _Predictive Modelling of Bone Ageing_.  Doctoral, University of East Anglia
  * Deng et al. (2009) Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L. (2009).  ImageNet: A large-scale hierarchical image database.  In _2009 IEEE Conference on Computer Vision and Pattern Recognition_.  10.1109/CVPR.2009.5206848
  * Dua and Graff (2017) [Dataset] Dua, D. and Graff, C. (2017).  UCI Machine Learning Repository
  * Dudani (1976) Dudani, S. A. (1976).  The Distance-Weighted k-Nearest-Neighbor Rule.  _IEEE Transactions on Systems, Man, and Cybernetics_ SMC-6.  10.1109/TSMC.1976.5408784
  * Gao and Tan (2006) Gao, J. and Tan, P.-n. (2006).  Converting Output Scores from Outlier Detection Algorithms into Probability Estimates.  In _Sixth International Conference on Data Mining (ICDM’06)_.  10.1109/ICDM.2006.43
  * Geler et al. (2016) Geler, Z., Kurbalija, V., Radovanović, M., and Ivanović, M. (2016).  Comparison of different weighting schemes for the kNN classifier on time-series data.  _Knowl Inf Syst_ 48\.  10.1007/s10115-015-0881-0
  * Goldberger et al. (2000) Goldberger, A. L., Amaral, L. A. N., Glass, L., Hausdorff, J. M., Ivanov, P. C., Mark, R. G., et al. (2000).  PhysioBank, PhysioToolkit, and PhysioNet: Components of a New Research Resource for Complex Physiologic Signals.  _Circulation_ 101\.  10.1161/01.CIR.101.23.e215
  * Goodge et al. (2022) Goodge, A., Hooi, B., Ng, S. K., and Ng, W. S. (2022).  LUNAR: Unifying Local Outlier Detection Methods via Graph Neural Networks.  In _Proceedings of the First MiniCon Conference_
  * Hautamaki et al. (2004) Hautamaki, V., Karkkainen, I., and Franti, P. (2004).  Outlier detection using k-nearest neighbour graph.  In _Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004._ vol. 3.  10.1109/ICPR.2004.1334558
  * Hawkins (1980) Hawkins, D. M. (1980).  _Identification of Outliers_ (Dordrecht: Springer Netherlands).  10.1007/978-94-015-3994-4
  * Houle (2013) Houle, M. E. (2013).  Dimensionality, Discriminability, Density and Distance Distributions.  In _2013 IEEE 13th International Conference on Data Mining Workshops_.  10.1109/ICDMW.2013.139
  * Janssens et al. (2012) Janssens, J., Huszár, F., and Postma, E. (2012).  _Stochastic Outlier Selection_.  Tech. Rep. TiCC TR 2012–001, Tilburg University
  * Jiang et al. (2018) Jiang, H., Kim, B., Guan, M., and Gupta, M. (2018).  To Trust Or Not To Trust A Classifier.  In _Advances in Neural Information Processing Systems_ (Curran Associates, Inc.), vol. 31
  * Jin et al. (2006) Jin, W., Tung, A. K. H., Han, J., and Wang, W. (2006).  Ranking Outliers Using Symmetric Neighborhood Relationship.  In _Advances in Knowledge Discovery and Data Mining_ , eds. W.-K. Ng, M. Kitsuregawa, J. Li, and K. Chang (Berlin, Heidelberg: Springer), Lecture Notes in Computer Science.  10.1007/11731139_68
  * Kauffmann et al. (2020) [Dataset] Kauffmann, J., Ruff, L., Montavon, G., and Müller, K.-R. (2020).  The Clever Hans Effect in Anomaly Detection
  * Keller et al. (2012) Keller, F., Muller, E., and Bohm, K. (2012).  HiCS: High Contrast Subspaces for Density-Based Outlier Ranking.  In _2012 IEEE 28th International Conference on Data Engineering_.  10.1109/ICDE.2012.88
  * Keogh et al. (2006) Keogh, E., Wei, L., Xi, X., Lonardi, S., Shieh, J., and Sirowy, S. (2006).  Intelligent Icons: Integrating Lite-Weight Data Mining and Visualization into GUI Operating Systems.  In _Sixth International Conference on Data Mining (ICDM’06)_.  10.1109/ICDM.2006.90
  * Kirner et al. (2017) Kirner, E., Schubert, E., and Zimek, A. (2017).  Good and Bad Neighborhood Approximations for Outlier Detection Ensembles.  _Lecture Notes in Computer Science_ 10609\.  10.1007/978-3-319-68474-1_12
  * Knorr and Ng (1997) Knorr, E. M. and Ng, R. T. (1997).  A Unified Approach for Mining Outliers.  In _CASCON ’97: Proceedings of the 1997 Conference of the Centre for Advanced Studies on Collaborative Research_ (IBM Press), CASCON ’97.  10.5555/782010.782021
  * Knorr and Ng (1998) Knorr, E. M. and Ng, R. T. (1998).  Algorithms for Mining Distance-Based Outliers in Large Datasets.  In _Proceedings of the 24rd International Conference on Very Large Data Bases_ (San Francisco, CA, USA: Morgan Kaufmann Publishers Inc), VLDB ’98
  * Knorr et al. (2000) Knorr, E. M., Ng, R. T., and Tucakov, V. (2000).  Distance-based outliers: Algorithms and applications.  _The VLDB Journal The International Journal on Very Large Data Bases_ 8\.  10.1007/s007780050006
  * Kriegel et al. (2009a) Kriegel, H.-P., Kröger, P., Schubert, E., and Zimek, A. (2009a).  LoOP: Local Outlier Probabilities.  In _Proceedings of the 18th ACM Conference on Information and Knowledge Management_ , eds. D. W.-L. Cheung, I.-Y. Song, W. W. Chu, X. Hu, and J. J. Lin (New York, NY, USA: Association for Computing Machinery).  10.1145/1645953.1646195
  * Kriegel et al. (2009b) Kriegel, H.-P., Kröger, P., Schubert, E., and Zimek, A. (2009b).  Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data.  In _Advances in Knowledge Discovery and Data Mining_ , eds. T. Theeramunkong, B. Kijsirikul, N. Cercone, and T.-B. Ho (Berlin, Heidelberg: Springer Berlin Heidelberg), Lecture Notes in Computer Science.  10.1007/978-3-642-01307-2_86
  * Kriegel et al. (2011) Kriegel, H.-P., Kroger, P., Schubert, E., and Zimek, A. (2011).  Interpreting and Unifying Outlier Scores.  In _Proceedings of the 2011 SIAM International Conference on Data Mining_ , eds. B. Liu, H. Liu, C. Clifton, T. Washio, and C. Kamath (Philadelphia, PA, USA: Society for Industrial and Applied Mathematics).  10.1137/1.9781611972818.2
  * Kriegel et al. (2012) Kriegel, H.-P., Kröger, P., Schubert, E., and Zimek, A. (2012).  Outlier Detection in Arbitrarily Oriented Subspaces.  In _2012 IEEE 12th International Conference on Data Mining_.  10.1109/ICDM.2012.21
  * Lapuschkin et al. (2019) Lapuschkin, S., Wäldchen, S., Binder, A., Montavon, G., Samek, W., and Müller, K.-R. (2019).  Unmasking Clever Hans predictors and assessing what machines really learn.  _Nat Commun_ 10\.  10.1038/s41467-019-08987-4
  * Latecki et al. (2007) Latecki, L. J., Lazarevic, A., and Pokrajac, D. (2007).  Outlier Detection with Kernel Density Functions.  In _Machine Learning and Data Mining in Pattern Recognition_ , ed. P. Perner (Berlin, Heidelberg: Springer), Lecture Notes in Computer Science.  10.1007/978-3-540-73499-4_6
  * Lee and See (2004) Lee, J. D. and See, K. A. (2004).  Trust in Automation: Designing for Appropriate Reliance.  _Hum Factors_ 46\.  10.1518/hfes.46.1.50_30392
  * Lellouche and Souris (2020) Lellouche, S. and Souris, M. (2020).  Distribution of Distances between Elements in a Compact Set.  _Stats_ 3\.  10.3390/stats3010001
  * Li et al. (2022) Li, X., Xiong, H., Li, X., Wu, X., Zhang, X., Liu, J., et al. (2022).  Interpretable deep learning: Interpretation, interpretability, trustworthiness, and beyond.  _Knowl Inf Syst_ 64\.  10.1007/s10115-022-01756-8
  * Liu et al. (2009) Liu, J., Zhong, L., Wickramasuriya, J., and Vasudevan, V. (2009).  uWave: Accelerometer-based personalized gesture recognition and its applications.  _Pervasive and Mobile Computing_ 5\.  10.1016/j.pmcj.2009.07.007
  * Macha and Akoglu (2018) Macha, M. and Akoglu, L. (2018).  Explaining anomalies in groups with characterizing subspace rules.  _Data Min. Knowl. Discov._ 32\.  10.1007/s10618-018-0585-7
  * Macleod et al. (1987) Macleod, J. E. S., Luk, A., and Titterington, D. M. (1987).  A Re-Examination of the Distance-Weighted k-Nearest Neighbor Classification Rule.  _IEEE Transactions on Systems, Man, and Cybernetics_ 17\.  10.1109/TSMC.1987.289362
  * Micenková et al. (2015) Micenková, B., van Beusekom, J., and Shafait, F. (2015).  Stamp Verification for Automated Document Authentication.  In _Computational Forensics: 5th International Workshop, IWCF 2012, Tsukuba, Japan, November 11, 2012 and 6th International Workshop, IWCF 2014, Stockholm, Sweden, August 24, 2014, Revised Selected Papers / Utpal Garain, Faisal Shafait (Eds.)_ , eds. U. Garain and F. Shafait (Cham: Springer), vol. 8915 of _Lecture Notes in Computer Science, 0302-9743_.  10.1007/978-3-319-20125-2_11
  * Micenková et al. (2013) Micenková, B., Ng, R. T., Dang, X.-H., and Assent, I. (2013).  Explaining Outliers by Subspace Separability.  In _2013 IEEE 13th International Conference on Data Mining_.  10.1109/ICDM.2013.132
  * Mueen et al. (2011) Mueen, A., Keogh, E., and Young, N. (2011).  Logical-shapelets: An expressive primitive for time series classification.  In _Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (San Diego California USA: ACM).  10.1145/2020408.2020587
  * Muhr and Affenzeller (2022a) Muhr, D. and Affenzeller, M. (2022a).  Hybrid (CPU/GPU) Exact Nearest Neighbors Search in High-Dimensional Spaces.  In _Artificial Intelligence Applications and Innovations_ , eds. I. Maglogiannis, L. Iliadis, J. Macintyre, and P. Cortez (Cham: Springer International Publishing), IFIP Advances in Information and Communication Technology.  10.1007/978-3-031-08337-2_10
  * Muhr and Affenzeller (2022b) Muhr, D. and Affenzeller, M. (2022b).  Little data is often enough for distance-based outlier detection.  _Procedia Computer Science_ 200\.  10.1016/j.procs.2022.01.297
  * Muhr and Affenzeller (2022c) Muhr, D. and Affenzeller, M. (2022c).  Outlier/Anomaly Detection of Univariate Time Series: A Dataset Collection and Benchmark.  In _Big Data Analytics and Knowledge Discovery_ , eds. R. Wrembel, J. Gamper, G. Kotsis, A. M. Tjoa, and I. Khalil (Cham: Springer International Publishing), Lecture Notes in Computer Science.  10.1007/978-3-031-12670-3_14
  * Muhr et al. (2022) [Dataset] Muhr, D., Affenzeller, M., and Blaom, A. D. (2022).  OutlierDetection.jl: A modular outlier detection ecosystem for the Julia programming language
  * Murray et al. (2015) Murray, D., Liao, J., Stankovic, L., Stankovic, V., Hauxwell-Baldwin, R., Wilson, C., et al. (2015).  A data management platform for personalised real-time energy feedback.  In _8th International Conference on Energy Efficiency in Domestic Appliances and Lighting_ (GBR: IET)
  * Olszewski (2001) Olszewski, R. T. (2001).  _Generalized Feature Extraction for Structural Pattern Recognition in Time-Series Data_.  Ph.D. thesis, Carnegie Mellon University, USA
  * Ovadia et al. (2019) Ovadia, Y., Fertig, E., Ren, J., Nado, Z., Sculley, D., Nowozin, S., et al. (2019).  Can you trust your model’ s uncertainty? Evaluating predictive uncertainty under dataset shift.  In _Advances in Neural Information Processing Systems_ (Curran Associates, Inc.), vol. 32
  * Pang et al. (2015) Pang, G., Ting, K. M., and Albrecht, D. (2015).  LeSiNN: Detecting Anomalies by Identifying Least Similar Nearest Neighbours.  In _2015 IEEE International Conference on Data Mining Workshop (ICDMW)_.  10.1109/ICDMW.2015.62
  * Pekalska and Duin (2000) Pekalska, E. and Duin, R. (2000).  Classifiers for dissimilarity-based pattern recognition.  In _Proceedings 15th International Conference on Pattern Recognition. ICPR-2000_. vol. 2.  10.1109/ICPR.2000.906008
  * Perini et al. (2021) Perini, L., Vercruyssen, V., and Davis, J. (2021).  Quantifying the Confidence of Anomaly Detectors in Their Example-Wise Predictions.  In _Machine Learning and Knowledge Discovery in Databases_ , eds. F. Hutter, K. Kersting, J. Lijffijt, and I. Valera (Cham: Springer International Publishing), Lecture Notes in Computer Science.  10.1007/978-3-030-67664-3_14
  * Radovanović et al. (2015) Radovanović, M., Nanopoulos, A., and Ivanović, M. (2015).  Reverse Nearest Neighbors in Unsupervised Distance-Based Outlier Detection.  _IEEE Transactions on Knowledge and Data Engineering_ 27\.  10.1109/TKDE.2014.2365790
  * Ramaswamy et al. (2000) Ramaswamy, S., Rastogi, R., and Shim, K. (2000).  Efficient Algorithms for Mining Outliers from Large Data Sets.  _SIGMOD Rec_ 29\.  10.1145/335191.335437
  * Rebbapragada et al. (2009) Rebbapragada, U., Protopapas, P., Brodley, C. E., and Alcock, C. (2009).  Finding anomalous periodic time series: An application to catalogs of periodic variable stars.  _Mach Learn_ 74\.  10.1007/s10994-008-5093-3
  * Roth et al. (2022) Roth, K., Pemula, L., Zepeda, J., Scholkopf, B., Brox, T., and Gehler, P. (2022).  Towards Total Recall in Industrial Anomaly Detection.  In _2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ (New Orleans, LA, USA: IEEE).  10.1109/CVPR52688.2022.01392
  * Samek et al. (2019) Samek, W., Montavon, G., Vedaldi, A., Hansen, L. K., and Müller, K.-R. (eds.) (2019).  _Explainable AI: Interpreting, Explaining and Visualizing Deep Learning_ , vol. 11700 of _Lecture Notes in Computer Science_ (Cham: Springer International Publishing).  10.1007/978-3-030-28954-6
  * Sapsanis et al. (2013) Sapsanis, C., Georgoulas, G., Tzes, A., and Lymberopoulos, D. (2013).  Improving EMG based classification of basic hand movements using EMD.  _Annu Int Conf IEEE Eng Med Biol Soc_ 2013\.  10.1109/EMBC.2013.6610858
  * Schnitzer et al. (2012) Schnitzer, D., Flexer, A., Schedl, M., and Widmer, G. (2012).  Local and Global Scaling Reduce Hubs in Space.  _Journal of Machine Learning Research_ 13
  * Schubert et al. (2012) Schubert, E., Wojdanowski, R., Zimek, A., and Kriegel, H.-P. (2012).  On Evaluation of Outlier Rankings and Outlier Scores.  In _Proceedings of the 2012 SIAM International Conference on Data Mining_ , eds. J. Ghosh, H. Liu, I. Davidson, C. Domeniconi, and C. Kamath (Philadelphia, PA: Society for Industrial and Applied Mathematics).  10.1137/1.9781611972825.90
  * Schubert et al. (2014a) Schubert, E., Zimek, A., and Kriegel, H.-P. (2014a).  Generalized Outlier Detection with Flexible Kernel Density Estimates.  In _Proceedings of the 2014 SIAM International Conference on Data Mining_ , eds. M. Zaki, Z. Obradovic, P. N. Tan, A. Banerjee, C. Kamath, and S. Parthasarathy (Philadelphia, PA: Society for Industrial and Applied Mathematics).  10.1137/1.9781611973440.63
  * Schubert et al. (2014b) Schubert, E., Zimek, A., and Kriegel, H.-P. (2014b).  Local outlier detection reconsidered: A generalized view on locality with applications to spatial, video, and network outlier detection.  _Data Min Knowl Disc_ 28\.  10.1007/s10618-012-0300-z
  * van Stein et al. (2016) van Stein, B., van Leeuwen, M., and Bäck, T. (2016).  Local subspace-based outlier detection using global neighbourhoods.  In _2016 IEEE International Conference on Big Data (Big Data)_.  10.1109/BigData.2016.7840717
  * Sugiyama and Borgwardt (2013) Sugiyama, M. and Borgwardt, K. (2013).  Rapid Distance-Based Outlier Detection via Sampling.  In _Advances in Neural Information Processing Systems_ (Curran Associates, Inc.), vol. 26
  * Sun et al. (2005) Sun, J., Papadimitriou, S., and Faloutsos, C. (2005).  Online Latent Variable Detection in Sensor Networks.  In _Proceedings of the 21st International Conference on Data Engineering_ (USA: IEEE Computer Society), ICDE ’05.  10.1109/ICDE.2005.100
  * Tan et al. (2017) Tan, C. W., Webb, G. I., and Petitjean, F. (2017).  Indexing and classifying gigabytes of time series under time warping.  In _Proceedings of the 2017 SIAM International Conference on Data Mining (SDM)_ (Society for Industrial and Applied Mathematics), Proceedings.  10.1137/1.9781611974973.32
  * Tang and He (2015) Tang, B. and He, H. (2015).  ENN: Extended Nearest Neighbor Method for Pattern Recognition [Research Frontier].  _IEEE Computational Intelligence Magazine_ 10\.  10.1109/MCI.2015.2437512
  * Tang and He (2017) Tang, B. and He, H. (2017).  A local density-based approach for outlier detection.  _Neurocomputing_ 241\.  10.1016/j.neucom.2017.02.039
  * Trittenbach and Böhm (2019) Trittenbach, H. and Böhm, K. (2019).  Dimension-based subspace search for outlier detection.  _Int J Data Sci Anal_ 7\.  10.1007/s41060-018-0137-7
  * Vinh et al. (2016) Vinh, N. X., Chan, J., Romano, S., Bailey, J., Leckie, C., Ramamohanarao, K., et al. (2016).  Discovering outlying aspects in large datasets.  _Data Min Knowl Disc_ 30\.  10.1007/s10618-016-0453-2
  * Wahid and Annavarapu (2021) Wahid, A. and Annavarapu, C. S. R. (2021).  NaNOD: A natural neighbour-based outlier detection algorithm.  _Neural Comput & Applic_ 33\.  10.1007/s00521-020-05068-2
  * Wang et al. (2010) Wang, X., Ye, L., Keogh, E. J., and Shelton, C. R. (2010).  Annotating Historical Archives of Images.  _IJDLS_ 1\.  10.4018/jdls.2010040104
  * Wu and Jermaine (2006) Wu, M. and Jermaine, C. (2006).  Outlier detection by sampling with accuracy guarantees.  In _Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (Philadelphia PA USA: ACM).  10.1145/1150402.1150501
  * Zavrel (1997) Zavrel, J. (1997).  An Empirical Re-Examination of Weighted Voting for k-NN.  In _BENELEARN-97 Proceedings of the 7th Belgian-Dutch Conference on Machine Learning_ , eds. W. Daelemans, P. Flach, and A. van den Bosch (Tilburg: Tilburg University)
  * Zhang et al. (2009) Zhang, K., Hutter, M., and Jin, H. (2009).  A New Local Distance-Based Outlier Detection Approach for Scattered Real-World Data.  In _Advances in Knowledge Discovery and Data Mining: 13th Pacific-Asia Conference, PAKDD 2009 Bangkok, Thailand, April 27-30, 2009 Proceedings_ , eds. T. Theeramunkong, B. Kijsirikul, N. Cercone, and T.-B. Ho (Berlin, Heidelberg: Springer Berlin Heidelberg), vol. 5476 of _Lecture Notes in Computer Science. 0302-9743_
  * Zhang et al. (2015) Zhang, L., Lin, J., and Karim, R. (2015).  An angle-based subspace anomaly detection approach to high-dimensional data: With an application to industrial fault detection.  _Reliability Engineering & System Safety_ 142\.  10.1016/j.ress.2015.05.025
  * Zhao et al. (2019) Zhao, Y., Nasrullah, Z., and Li, Z. (2019).  PyOD: A python toolbox for scalable outlier detection.  _Journal of Machine Learning Research_ 20
  * Zhu et al. (2016) Zhu, Q., Feng, J., and Huang, J. (2016).  Natural neighbor: A self-adaptive neighborhood method without parameter K.  _Pattern Recognition Letters_ 80\.  10.1016/j.patrec.2016.05.007
  * Zimek and Filzmoser (2018) Zimek, A. and Filzmoser, P. (2018).  There and back again: Outlier detection between statistical reasoning and data mining algorithms.  _WIREs Data Mining and Knowledge Discovery_ 8\.  10.1002/widm.1280
  * Zimek et al. (2013) Zimek, A., Gaudet, M., Campello, R. J., and Sander, J. (2013).  Subsampling for efficient and effective unsupervised outlier detection ensembles.  In _Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (New York, NY, USA: Association for Computing Machinery), KDD ’13.  10.1145/2487575.2487676