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 language | English |
|---|---|
| Title of host publication | Web Information Systems Engineering – WISE 2018 |
| Subtitle of host publication | 19th International Conference, Dubai, United Arab Emirates, November 12–15, 2018 Proceedings, Part II |
| Editors | Hakim Hacid, Wojciech Cellary, Hua Wang, Hye-Young Paik, Rui Zhou |
| Place of Publication | Cham Switzerland |
| Publisher | Springer |
| Pages | 269-284 |
| Number of pages | 16 |
| ISBN (Electronic) | 9783030029258 |
| ISBN (Print) | 9783030029241 |
| DOIs | |
| Publication status | Published - 2018 |
| Event | International Conference on Web Information Systems Engineering 2018 - Dubai, United Arab Emirates Duration: 12 Nov 2018 → 15 Nov 2018 Conference number: 19th http://wise2018.connect.rs/index.html |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| Volume | 11234 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | International Conference on Web Information Systems Engineering 2018 |
|---|---|
| Abbreviated title | WISE 2018 |
| Country | United Arab Emirates |
| City | Dubai |
| Period | 12/11/18 → 15/11/18 |
| Internet address |
Keywords
- Big data
- Density biased sampling
- Locality-Sensitive Hashing
- Outlier/anomaly detection
- Unsupervised learning
Cite this
}
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 proceeding › Conference Paper › Research › peer-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 -