A mathematical assessment of the isolation random forest method for anomaly detection in big data

We present the mathematical analysis of the Isolation Random Forest Method (IRF Method) for anomaly detection, proposed by Liu F.T., Ting K.M. and Zhou Z. H. in their seminal work as a heuristic method for anomaly detection in Big Data. We prove that the IRF space can be endowed with a probability i...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical methods in the applied sciences 2023-01, Vol.46 (1), p.1156-1177
Main Authors: Morales, Fernando A., Ramírez, Jorge M., Ramos, Edgar A.
Format: Article
Language:English
Subjects:
Algorithms
Anomalies
anomaly detection
Big Data
Heuristic methods
isolation random forest
Mathematical analysis
monte carlo methods
probabilistic algorithms
Probability theory
Statistical analysis
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present the mathematical analysis of the Isolation Random Forest Method (IRF Method) for anomaly detection, proposed by Liu F.T., Ting K.M. and Zhou Z. H. in their seminal work as a heuristic method for anomaly detection in Big Data. We prove that the IRF space can be endowed with a probability induced by the Isolation Tree algorithm (iTree). In this setting, the convergence of the IRF method is proved, using the Law of Large Numbers. A couple of counterexamples are presented to show that the method is inconclusive and no certificate of quality can be given, when using it as a means to detect anomalies. Hence, an alternative version of the method is proposed whose mathematical foundation is fully justified. Furthermore, a criterion for choosing the number of sampled trees needed to guarantee confidence intervals of the numerical results is presented. Finally, numerical experiments are presented to compare the performance of the classic method with the proposed one.
ISSN:0170-4214
1099-1476
DOI:10.1002/mma.8570