Isolation Forest (iForest) is one of the most widely used tree-based unsupervised algorithms for anomaly detection, isolating anomalous points through recursive random axis-aligned partitioning. In its original formulation from Liu et al. in 2008, split values are sampled uniformly along a randomly chosen feature, not accounting for the local density and spacing between data points. The present thesis work investigates the theoretical foundations and empirical properties of the Probabilistic Generalization of Isolation Forest (PGIF) proposed by Tokovarov and Karczmarek in 2022, which modifies the split generation procedure by weighting consecutive intervals via a Kernel function. The work shows that classical iForest can be derived from PGIF when using a uniform Kernel and setting the weighting parameter to zero. Through an experimental evaluation on five benchmark datasets and synthetic datasets, it analyzes how non-uniform splitting affects anomaly ranking metrics and computational cost. The results indicate that PGIF significantly enhances anomaly detection when anomalies lie in sparse gaps between dense clusters of normal observations. Instead, when anomalies are spatially close to inliers, the strong gap-prioritization yields no significant performance benefit. Finally, it demonstrates that while the operation of sorting projected points increases the theoretical construction cost per split, the resulting smaller and unbalanced iTree structures can partially compensate for the execution time in the experiments, yielding smaller computational costs compared to the theoretical expectations.
Isolation Forest (iForest) is one of the most widely used tree-based unsupervised algorithms for anomaly detection, isolating anomalous points through recursive random axis-aligned partitioning. In its original formulation from Liu et al. in 2008, split values are sampled uniformly along a randomly chosen feature, not accounting for the local density and spacing between data points. The present thesis work investigates the theoretical foundations and empirical properties of the Probabilistic Generalization of Isolation Forest (PGIF) proposed by Tokovarov and Karczmarek in 2022, which modifies the split generation procedure by weighting consecutive intervals via a Kernel function. The work shows that classical iForest can be derived from PGIF when using a uniform Kernel and setting the weighting parameter to zero. Through an experimental evaluation on five benchmark datasets and synthetic datasets, it analyzes how non-uniform splitting affects anomaly ranking metrics and computational cost. The results indicate that PGIF significantly enhances anomaly detection when anomalies lie in sparse gaps between dense clusters of normal observations. Instead, when anomalies are spatially close to inliers, the strong gap-prioritization yields no significant performance benefit. Finally, it demonstrates that while the operation of sorting projected points increases the theoretical construction cost per split, the resulting smaller and unbalanced iTree structures can partially compensate for the execution time in the experiments, yielding smaller computational costs compared to the theoretical expectations.
Isolation Forest for Anomaly Detection: From Uniform to Probabilistic Split Generation
MENEGUZZO, ANDRÉS CHRISTIAN
2025/2026
Abstract
Isolation Forest (iForest) is one of the most widely used tree-based unsupervised algorithms for anomaly detection, isolating anomalous points through recursive random axis-aligned partitioning. In its original formulation from Liu et al. in 2008, split values are sampled uniformly along a randomly chosen feature, not accounting for the local density and spacing between data points. The present thesis work investigates the theoretical foundations and empirical properties of the Probabilistic Generalization of Isolation Forest (PGIF) proposed by Tokovarov and Karczmarek in 2022, which modifies the split generation procedure by weighting consecutive intervals via a Kernel function. The work shows that classical iForest can be derived from PGIF when using a uniform Kernel and setting the weighting parameter to zero. Through an experimental evaluation on five benchmark datasets and synthetic datasets, it analyzes how non-uniform splitting affects anomaly ranking metrics and computational cost. The results indicate that PGIF significantly enhances anomaly detection when anomalies lie in sparse gaps between dense clusters of normal observations. Instead, when anomalies are spatially close to inliers, the strong gap-prioritization yields no significant performance benefit. Finally, it demonstrates that while the operation of sorting projected points increases the theoretical construction cost per split, the resulting smaller and unbalanced iTree structures can partially compensate for the execution time in the experiments, yielding smaller computational costs compared to the theoretical expectations.| File | Dimensione | Formato | |
|---|---|---|---|
|
Isolation_Forest_for_Anomaly_Detection_From_Uniform_to_Probabilistic_Split_Generation.pdf
accesso aperto
Dimensione
758.22 kB
Formato
Adobe PDF
|
758.22 kB | Adobe PDF | Visualizza/Apri |
The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License
https://hdl.handle.net/20.500.12608/119570