|
| | | | |
| | | |
| Stat |
Members: 3669
Articles: 2'599'751
Articles rated: 2609
18 March 2025 |
|
| | | | |
|
Article overview
| |
|
|
Linear-time Outlier Detection via Sensitivity | | Mario Lucic
; Olivier Bachem
; Andreas Krause
; | | Date: |
2 May 2016 | | Abstract: | Outliers are ubiquitous in modern data sets. Distance-based techniques are a
popular non-parametric approach to outlier detection as they require no prior
assumptions on the data generating distribution and are simple to implement.
Scaling these techniques to massive data sets without sacrificing accuracy is a
challenging task. We propose a novel algorithm based on the intuition that
outliers have a significant influence on the quality of divergence-based
clustering solutions. We propose sensitivity - the worst-case impact of a data
point on the clustering objective - as a measure of outlierness. We then prove
that influence, a (non-trivial) upper-bound on the sensitivity, can be computed
by a simple linear time algorithm. To scale beyond a single machine, we propose
a communication efficient distributed algorithm. In an extensive experimental
evaluation, we demonstrate the effectiveness and establish the statistical
significance of the proposed approach. In particular, it outperforms the most
popular distance-based approaches while being several orders of magnitude
faster. | | Source: | arXiv, 1605.0519 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER