L1-depth revisited: A robust angle-based outlier factor in high-dimensional space

Ninh Pham

doi:10.1007/978-3-030-10925-7_7

L1-depth revisited: A robust angle-based outlier factor in high-dimensional space

Ninh Pham^*

^*Corresponding author for this work

1 Citation (Scopus)

Abstract

Angle-based outlier detection (ABOD) has been recently emerged as an effective method to detect outliers in high dimensions. Instead of examining neighborhoods as proximity-based concepts, ABOD assesses the broadness of angle spectrum of a point as an outlier factor. Despite being a parameter-free and robust measure in high-dimensional space, the exact solution of ABOD suffers from the cubic cost O(n³ regarding the data size n, hence cannot be used on large-scale data sets. In this work we present a conceptual relationship between the ABOD intuition and the L1-depth concept in statistics, one of the earliest methods used for detecting outliers. Deriving from this relationship, we propose to use L1-depth as a variant of angle-based outlier factors, since it only requires a quadratic computational time as proximity-based outlier factors. Empirically, L1-depth is competitive (often superior) to proximity-based and other proposed angle-based outlier factors on detecting high-dimensional outliers regarding both efficiency and accuracy. In order to avoid the quadratic computational time, we introduce a simple but efficient sampling method named SamDepth for estimating L1-depth measure. We also present theoretical analysis to guarantee the reliability of SamDepth. The empirical experiments on many real-world high-dimensional data sets demonstrate that SamDepth with √n samples often achieves very competitive accuracy and runs several orders of magnitude faster than other proximity-based and ABOD competitors. Data related to this paper are available at: https://www.dropbox.com/s/nk7nqmwmdsatizs/Datasets.zip. Code related to this paper is available at: https://github.com/NinhPham/Outlier.

Original language	English
Title of host publication	Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2018, Proceedings
Editors	Francesco Bonchi, Thomas Gärtner, Neil Hurley, Georgiana Ifrim, Michele Berlingerio
Number of pages	17
Volume	1
Publisher	Springer
Publication date	2019
Pages	105-121
ISBN (Print)	9783030109240
DOIs	https://doi.org/10.1007/978-3-030-10925-7_7
Publication status	Published - 2019
Event	European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML-PKDD 2018 - Dublin, Ireland Duration: 10 Sept 2018 → 14 Sept 2018

Conference

Conference	European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML-PKDD 2018
Country/Territory	Ireland
City	Dublin
Period	10/09/2018 → 14/09/2018

Series	Lecture notes in computer science
Volume	11051
ISSN	0302-9743

Access to Document

10.1007/978-3-030-10925-7_7

Cite this

Pham, N. (2019). L1-depth revisited: A robust angle-based outlier factor in high-dimensional space. In F. Bonchi, T. Gärtner, N. Hurley, G. Ifrim, & M. Berlingerio (Eds.), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2018, Proceedings (Vol. 1, pp. 105-121). Springer. Lecture notes in computer science Vol. 11051 https://doi.org/10.1007/978-3-030-10925-7_7

L1-depth revisited : A robust angle-based outlier factor in high-dimensional space. / Pham, Ninh.

Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2018, Proceedings. ed. / Francesco Bonchi; Thomas Gärtner; Neil Hurley; Georgiana Ifrim; Michele Berlingerio. Vol. 1 Springer, 2019. p. 105-121 (Lecture notes in computer science, Vol. 11051).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Pham, N 2019, L1-depth revisited: A robust angle-based outlier factor in high-dimensional space. in F Bonchi, T Gärtner, N Hurley, G Ifrim & M Berlingerio (eds), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2018, Proceedings. vol. 1, Springer, Lecture notes in computer science, vol. 11051, pp. 105-121, European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML-PKDD 2018, Dublin, Ireland, 10/09/2018. https://doi.org/10.1007/978-3-030-10925-7_7

Pham N. L1-depth revisited: A robust angle-based outlier factor in high-dimensional space. In Bonchi F, Gärtner T, Hurley N, Ifrim G, Berlingerio M, editors, Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2018, Proceedings. Vol. 1. Springer. 2019. p. 105-121. (Lecture notes in computer science, Vol. 11051). doi: 10.1007/978-3-030-10925-7_7

Pham, Ninh. / L1-depth revisited : A robust angle-based outlier factor in high-dimensional space. Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2018, Proceedings. editor / Francesco Bonchi ; Thomas Gärtner ; Neil Hurley ; Georgiana Ifrim ; Michele Berlingerio. Vol. 1 Springer, 2019. pp. 105-121 (Lecture notes in computer science, Vol. 11051).

@inproceedings{66cb914f0f5645c3a4044c26af4be041,

title = "L1-depth revisited: A robust angle-based outlier factor in high-dimensional space",

abstract = "Angle-based outlier detection (ABOD) has been recently emerged as an effective method to detect outliers in high dimensions. Instead of examining neighborhoods as proximity-based concepts, ABOD assesses the broadness of angle spectrum of a point as an outlier factor. Despite being a parameter-free and robust measure in high-dimensional space, the exact solution of ABOD suffers from the cubic cost O(n3 regarding the data size n, hence cannot be used on large-scale data sets. In this work we present a conceptual relationship between the ABOD intuition and the L1-depth concept in statistics, one of the earliest methods used for detecting outliers. Deriving from this relationship, we propose to use L1-depth as a variant of angle-based outlier factors, since it only requires a quadratic computational time as proximity-based outlier factors. Empirically, L1-depth is competitive (often superior) to proximity-based and other proposed angle-based outlier factors on detecting high-dimensional outliers regarding both efficiency and accuracy. In order to avoid the quadratic computational time, we introduce a simple but efficient sampling method named SamDepth for estimating L1-depth measure. We also present theoretical analysis to guarantee the reliability of SamDepth. The empirical experiments on many real-world high-dimensional data sets demonstrate that SamDepth with √n samples often achieves very competitive accuracy and runs several orders of magnitude faster than other proximity-based and ABOD competitors. Data related to this paper are available at: https://www.dropbox.com/s/nk7nqmwmdsatizs/Datasets.zip. Code related to this paper is available at: https://github.com/NinhPham/Outlier.",

author = "Ninh Pham",

year = "2019",

doi = "10.1007/978-3-030-10925-7_7",

language = "English",

isbn = "9783030109240",

volume = "1",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "105--121",

editor = "Francesco Bonchi and Thomas G{\"a}rtner and Neil Hurley and Georgiana Ifrim and Michele Berlingerio",

booktitle = "Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2018, Proceedings",

note = "European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML-PKDD 2018 ; Conference date: 10-09-2018 Through 14-09-2018",

}

TY - GEN

T1 - L1-depth revisited

T2 - European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML-PKDD 2018

AU - Pham, Ninh

PY - 2019

Y1 - 2019

N2 - Angle-based outlier detection (ABOD) has been recently emerged as an effective method to detect outliers in high dimensions. Instead of examining neighborhoods as proximity-based concepts, ABOD assesses the broadness of angle spectrum of a point as an outlier factor. Despite being a parameter-free and robust measure in high-dimensional space, the exact solution of ABOD suffers from the cubic cost O(n3 regarding the data size n, hence cannot be used on large-scale data sets. In this work we present a conceptual relationship between the ABOD intuition and the L1-depth concept in statistics, one of the earliest methods used for detecting outliers. Deriving from this relationship, we propose to use L1-depth as a variant of angle-based outlier factors, since it only requires a quadratic computational time as proximity-based outlier factors. Empirically, L1-depth is competitive (often superior) to proximity-based and other proposed angle-based outlier factors on detecting high-dimensional outliers regarding both efficiency and accuracy. In order to avoid the quadratic computational time, we introduce a simple but efficient sampling method named SamDepth for estimating L1-depth measure. We also present theoretical analysis to guarantee the reliability of SamDepth. The empirical experiments on many real-world high-dimensional data sets demonstrate that SamDepth with √n samples often achieves very competitive accuracy and runs several orders of magnitude faster than other proximity-based and ABOD competitors. Data related to this paper are available at: https://www.dropbox.com/s/nk7nqmwmdsatizs/Datasets.zip. Code related to this paper is available at: https://github.com/NinhPham/Outlier.

AB - Angle-based outlier detection (ABOD) has been recently emerged as an effective method to detect outliers in high dimensions. Instead of examining neighborhoods as proximity-based concepts, ABOD assesses the broadness of angle spectrum of a point as an outlier factor. Despite being a parameter-free and robust measure in high-dimensional space, the exact solution of ABOD suffers from the cubic cost O(n3 regarding the data size n, hence cannot be used on large-scale data sets. In this work we present a conceptual relationship between the ABOD intuition and the L1-depth concept in statistics, one of the earliest methods used for detecting outliers. Deriving from this relationship, we propose to use L1-depth as a variant of angle-based outlier factors, since it only requires a quadratic computational time as proximity-based outlier factors. Empirically, L1-depth is competitive (often superior) to proximity-based and other proposed angle-based outlier factors on detecting high-dimensional outliers regarding both efficiency and accuracy. In order to avoid the quadratic computational time, we introduce a simple but efficient sampling method named SamDepth for estimating L1-depth measure. We also present theoretical analysis to guarantee the reliability of SamDepth. The empirical experiments on many real-world high-dimensional data sets demonstrate that SamDepth with √n samples often achieves very competitive accuracy and runs several orders of magnitude faster than other proximity-based and ABOD competitors. Data related to this paper are available at: https://www.dropbox.com/s/nk7nqmwmdsatizs/Datasets.zip. Code related to this paper is available at: https://github.com/NinhPham/Outlier.

UR - http://www.scopus.com/inward/record.url?scp=85061153578&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-10925-7_7

DO - 10.1007/978-3-030-10925-7_7

M3 - Article in proceedings

AN - SCOPUS:85061153578

SN - 9783030109240

VL - 1

T3 - Lecture notes in computer science

SP - 105

EP - 121

BT - Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2018, Proceedings

A2 - Bonchi, Francesco

A2 - Gärtner, Thomas

A2 - Hurley, Neil

A2 - Ifrim, Georgiana

A2 - Berlingerio, Michele

PB - Springer

Y2 - 10 September 2018 through 14 September 2018

ER -

L1-depth revisited: A robust angle-based outlier factor in high-dimensional space

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this