Density biased sampling with locality sensitive hashing for outlier detection

Xuyun Zhang, Mahsa Salehi, Christopher Leckie, Yun Luo, Qiang He, Rui Zhou, Rao Kotagiri

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

Outlier or anomaly detection is one of the major challenges in big data analytics since unusual but insightful patterns are often hidden in massive data sets such as sensing data and social networks. Sampling techniques have been a focus for outlier detection to address scalability on big data. The recent study has shown uniform random sampling with ensemble can boost outlier detection performance. However, uniform sampling assumes that all points are of equal importance, which usually fails to hold for outlier detection because some points are more sensitive to sampling than others. Thus, it is necessary and promising to utilise the density information of points to reflect their importance for sampling based detection. In this paper, we formally investigate density biased sampling for outlier detection, and propose a novel density biased sampling approach. To attain scalable density estimation, we use Locality Sensitive Hashing (LSH) for counting the nearest neighbours of a point. Extensive experiments on both synthetic and real-world data sets show that our approach significantly outperforms existing outlier detection methods based on uniform sampling.

Original languageEnglish
Title of host publicationWeb Information Systems Engineering – WISE 2018
Subtitle of host publication19th International Conference, Dubai, United Arab Emirates, November 12–15, 2018 Proceedings, Part II
EditorsHakim Hacid, Wojciech Cellary, Hua Wang, Hye-Young Paik, Rui Zhou
Place of PublicationCham Switzerland
PublisherSpringer
Pages269-284
Number of pages16
ISBN (Electronic)9783030029258
ISBN (Print)9783030029241
DOIs
Publication statusPublished - 2018
EventInternational Conference on Web Information Systems Engineering 2018 - Dubai, United Arab Emirates
Duration: 12 Nov 201815 Nov 2018
Conference number: 19th
http://wise2018.connect.rs/index.html

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11234
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Web Information Systems Engineering 2018
Abbreviated titleWISE 2018
CountryUnited Arab Emirates
CityDubai
Period12/11/1815/11/18
Internet address

Keywords

  • Big data
  • Density biased sampling
  • Locality-Sensitive Hashing
  • Outlier/anomaly detection
  • Unsupervised learning

Cite this

Zhang, X., Salehi, M., Leckie, C., Luo, Y., He, Q., Zhou, R., & Kotagiri, R. (2018). Density biased sampling with locality sensitive hashing for outlier detection. In H. Hacid, W. Cellary, H. Wang, H-Y. Paik, & R. Zhou (Eds.), Web Information Systems Engineering – WISE 2018 : 19th International Conference, Dubai, United Arab Emirates, November 12–15, 2018 Proceedings, Part II (pp. 269-284). (Lecture Notes in Computer Science ; Vol. 11234 ). Cham Switzerland: Springer. https://doi.org/10.1007/978-3-030-02925-8_19
Zhang, Xuyun ; Salehi, Mahsa ; Leckie, Christopher ; Luo, Yun ; He, Qiang ; Zhou, Rui ; Kotagiri, Rao. / Density biased sampling with locality sensitive hashing for outlier detection. Web Information Systems Engineering – WISE 2018 : 19th International Conference, Dubai, United Arab Emirates, November 12–15, 2018 Proceedings, Part II . editor / Hakim Hacid ; Wojciech Cellary ; Hua Wang ; Hye-Young Paik ; Rui Zhou. Cham Switzerland : Springer, 2018. pp. 269-284 (Lecture Notes in Computer Science ).
@inproceedings{ab63947589b94666875385e3996cc46d,
title = "Density biased sampling with locality sensitive hashing for outlier detection",
abstract = "Outlier or anomaly detection is one of the major challenges in big data analytics since unusual but insightful patterns are often hidden in massive data sets such as sensing data and social networks. Sampling techniques have been a focus for outlier detection to address scalability on big data. The recent study has shown uniform random sampling with ensemble can boost outlier detection performance. However, uniform sampling assumes that all points are of equal importance, which usually fails to hold for outlier detection because some points are more sensitive to sampling than others. Thus, it is necessary and promising to utilise the density information of points to reflect their importance for sampling based detection. In this paper, we formally investigate density biased sampling for outlier detection, and propose a novel density biased sampling approach. To attain scalable density estimation, we use Locality Sensitive Hashing (LSH) for counting the nearest neighbours of a point. Extensive experiments on both synthetic and real-world data sets show that our approach significantly outperforms existing outlier detection methods based on uniform sampling.",
keywords = "Big data, Density biased sampling, Locality-Sensitive Hashing, Outlier/anomaly detection, Unsupervised learning",
author = "Xuyun Zhang and Mahsa Salehi and Christopher Leckie and Yun Luo and Qiang He and Rui Zhou and Rao Kotagiri",
year = "2018",
doi = "10.1007/978-3-030-02925-8_19",
language = "English",
isbn = "9783030029241",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "269--284",
editor = "Hakim Hacid and Wojciech Cellary and Hua Wang and Hye-Young Paik and Rui Zhou",
booktitle = "Web Information Systems Engineering – WISE 2018",

}

Zhang, X, Salehi, M, Leckie, C, Luo, Y, He, Q, Zhou, R & Kotagiri, R 2018, Density biased sampling with locality sensitive hashing for outlier detection. in H Hacid, W Cellary, H Wang, H-Y Paik & R Zhou (eds), Web Information Systems Engineering – WISE 2018 : 19th International Conference, Dubai, United Arab Emirates, November 12–15, 2018 Proceedings, Part II . Lecture Notes in Computer Science , vol. 11234 , Springer, Cham Switzerland, pp. 269-284, International Conference on Web Information Systems Engineering 2018, Dubai, United Arab Emirates, 12/11/18. https://doi.org/10.1007/978-3-030-02925-8_19

Density biased sampling with locality sensitive hashing for outlier detection. / Zhang, Xuyun; Salehi, Mahsa; Leckie, Christopher; Luo, Yun; He, Qiang; Zhou, Rui; Kotagiri, Rao.

Web Information Systems Engineering – WISE 2018 : 19th International Conference, Dubai, United Arab Emirates, November 12–15, 2018 Proceedings, Part II . ed. / Hakim Hacid; Wojciech Cellary; Hua Wang; Hye-Young Paik; Rui Zhou. Cham Switzerland : Springer, 2018. p. 269-284 (Lecture Notes in Computer Science ; Vol. 11234 ).

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

TY - GEN

T1 - Density biased sampling with locality sensitive hashing for outlier detection

AU - Zhang, Xuyun

AU - Salehi, Mahsa

AU - Leckie, Christopher

AU - Luo, Yun

AU - He, Qiang

AU - Zhou, Rui

AU - Kotagiri, Rao

PY - 2018

Y1 - 2018

N2 - Outlier or anomaly detection is one of the major challenges in big data analytics since unusual but insightful patterns are often hidden in massive data sets such as sensing data and social networks. Sampling techniques have been a focus for outlier detection to address scalability on big data. The recent study has shown uniform random sampling with ensemble can boost outlier detection performance. However, uniform sampling assumes that all points are of equal importance, which usually fails to hold for outlier detection because some points are more sensitive to sampling than others. Thus, it is necessary and promising to utilise the density information of points to reflect their importance for sampling based detection. In this paper, we formally investigate density biased sampling for outlier detection, and propose a novel density biased sampling approach. To attain scalable density estimation, we use Locality Sensitive Hashing (LSH) for counting the nearest neighbours of a point. Extensive experiments on both synthetic and real-world data sets show that our approach significantly outperforms existing outlier detection methods based on uniform sampling.

AB - Outlier or anomaly detection is one of the major challenges in big data analytics since unusual but insightful patterns are often hidden in massive data sets such as sensing data and social networks. Sampling techniques have been a focus for outlier detection to address scalability on big data. The recent study has shown uniform random sampling with ensemble can boost outlier detection performance. However, uniform sampling assumes that all points are of equal importance, which usually fails to hold for outlier detection because some points are more sensitive to sampling than others. Thus, it is necessary and promising to utilise the density information of points to reflect their importance for sampling based detection. In this paper, we formally investigate density biased sampling for outlier detection, and propose a novel density biased sampling approach. To attain scalable density estimation, we use Locality Sensitive Hashing (LSH) for counting the nearest neighbours of a point. Extensive experiments on both synthetic and real-world data sets show that our approach significantly outperforms existing outlier detection methods based on uniform sampling.

KW - Big data

KW - Density biased sampling

KW - Locality-Sensitive Hashing

KW - Outlier/anomaly detection

KW - Unsupervised learning

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

U2 - 10.1007/978-3-030-02925-8_19

DO - 10.1007/978-3-030-02925-8_19

M3 - Conference Paper

SN - 9783030029241

T3 - Lecture Notes in Computer Science

SP - 269

EP - 284

BT - Web Information Systems Engineering – WISE 2018

A2 - Hacid, Hakim

A2 - Cellary, Wojciech

A2 - Wang, Hua

A2 - Paik, Hye-Young

A2 - Zhou, Rui

PB - Springer

CY - Cham Switzerland

ER -

Zhang X, Salehi M, Leckie C, Luo Y, He Q, Zhou R et al. Density biased sampling with locality sensitive hashing for outlier detection. In Hacid H, Cellary W, Wang H, Paik H-Y, Zhou R, editors, Web Information Systems Engineering – WISE 2018 : 19th International Conference, Dubai, United Arab Emirates, November 12–15, 2018 Proceedings, Part II . Cham Switzerland: Springer. 2018. p. 269-284. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-030-02925-8_19