Back to Search
Start Over
Robustness Can Be Cheap: A Highly Efficient Approach to Discover Outliers under High Outlier Ratios
- Source :
- AAAI
- Publication Year :
- 2019
- Publisher :
- Association for the Advancement of Artificial Intelligence (AAAI), 2019.
-
Abstract
- Efficient detection of outliers from massive data with a high outlier ratio is challenging but not explicitly discussed yet. In such a case, existing methods either suffer from poor robustness or require expensive computations. This paper proposes a Low-rank based Efficient Outlier Detection (LEOD) framework to achieve favorable robustness against high outlier ratios with much cheaper computations. Specifically, it is worth highlighting the following aspects of LEOD: (1) Our framework exploits the low-rank structure embedded in the similarity matrix and considers inliers/outliers equally based on this low-rank structure, which facilitates us to encourage satisfying robustness with low computational cost later; (2) A novel re-weighting algorithm is derived as a new general solution to the constrained eigenvalue problem, which is a major bottleneck for the optimization process. Instead of the high space and time complexity (O((2n)2)/O((2n)3)) required by the classic solution, our algorithm enjoys O(n) space complexity and a faster optimization speed in the experiments; (3) A new alternative formulation is proposed for further acceleration of the solution process, where a cheap closed-form solution can be obtained. Experiments show that LEOD achieves strong robustness under an outlier ratio from 20% to 60%, while it is at most 100 times more memory efficient and 1000 times faster than its previous counterpart that attains comparable performance. The codes of LEOD are publicly available at https://github.com/demonzyj56/LEOD.
- Subjects :
- 0209 industrial biotechnology
Computer science
Similarity matrix
02 engineering and technology
General Medicine
Bottleneck
020901 industrial engineering & automation
Robustness (computer science)
Outlier
0202 electrical engineering, electronic engineering, information engineering
020201 artificial intelligence & image processing
Anomaly detection
Algorithm
Eigenvalues and eigenvectors
Subjects
Details
- ISSN :
- 23743468 and 21595399
- Volume :
- 33
- Database :
- OpenAIRE
- Journal :
- Proceedings of the AAAI Conference on Artificial Intelligence
- Accession number :
- edsair.doi...........cc3b897c74c2a230ea2f219120c4c2bf