view release on metacpan or  search on metacpan

lib/Algorithm/Classifier/IsolationForest.pm  view on Meta::CPAN

=cut

sub to_prototype {
	my ($self) = @_;
	croak "to_prototype: this model has no feature_names; a prototype's variable " . "schema needs named features"
		unless ref $self->{feature_names} eq 'ARRAY' && @{ $self->{feature_names} };

	my $schema = {
		feature_names => $self->{feature_names},
		missing       => $self->{missing},
	};
	$schema->{feature_descriptions} = $self->{feature_descriptions}
		if ref $self->{feature_descriptions} eq 'HASH' && %{ $self->{feature_descriptions} };
	$schema->{mungers} = $self->{mungers}
		if ref $self->{mungers} eq 'HASH' && %{ $self->{mungers} };
	$schema->{impute_with} = $self->{impute_with}
		if defined $self->{missing} && $self->{missing} eq 'impute';

	my $params = {
		n_trees     => $self->{n_trees},
		sample_size => $self->{sample_size},
		mode        => $self->{mode},
		voting      => $self->{voting},
	};
	$params->{max_depth}       = $self->{max_depth} if defined $self->{max_depth};
	$params->{extension_level} = $self->{extension_level_used} // $self->{extension_level}
		if defined( $self->{extension_level_used} // $self->{extension_level} );
	$params->{contamination} = $self->{contamination} if defined $self->{contamination};

	return JSON::PP->new->canonical(1)->encode(
		{
			format             => 'Algorithm::Classifier::IsolationForest::Prototype',
			version            => 1,
			class              => 'batch',
			schema_version     => $self->{schema_version} // '0',
			schema_description => $self->{schema_description}
				// '(none recorded; describe this schema and bump schema_version)',
			schema => $schema,
			params => $params,
		}
	);
} ## end sub to_prototype

=head1 REFERENCES

Liu, Fei Tony & Ting, Kai & Zhou, Zhi-Hua. (2008). Isolation Forest. 413 - 422. 10.1109/ICDM.2008.17.

L<https://www.researchgate.net/publication/224384174_Isolation_Forest>

L<https://ieeexplore.ieee.org/abstract/document/4781136>

Sahand Hariri, Matias Carrasco Kind, Robert J. Brunner (2020). Extended Isolation Forest. 1479 - 1489. 10.1109/TKDE.2019.2947676

L<https://ieeexplore.ieee.org/document/8888179>

Yousra Chabchoub, Maurras Ulbricht Togbe, Aliou Boly, Raja Chiky (2022). An In-Depth Study and Improvement of Isolation Forest. IEEE Access, vol. 10, 10219 - 10237. 10.1109/ACCESS.2022.3144425 (the Majority Voting Isolation Forest implemented by C<< ...

L<https://ieeexplore.ieee.org/document/9684896>

Filippo Leveni, Guilherme Weigert Cassales, Bernhard Pfahringer, Albert Bifet, Giacomo Boracchi (2024). Online Isolation Forest. (the streaming variant implemented by L<Algorithm::Classifier::IsolationForest::Online>)

L<https://arxiv.org/abs/2505.09593>

L<https://github.com/ineveLoppiliF/Online-Isolation-Forest>

L<https://proceedings.mlr.press/v235/leveni24a.html>

=cut

###
###
### internal stuff below
###
###

#-------------------------------------------------------------------------------
# c(n): the expected path length of an unsuccessful search in a binary search
# tree of n nodes. Isolation Forest uses it (a) to adjust the path length when a
# leaf still holds more than one point (depth limit reached), and (b) to
# normalise the average path length into a 0..1 anomaly score.
#-------------------------------------------------------------------------------
sub _c {
	my ($n) = @_;
	return 0.0 if $n <= 1;
	return 1.0 if $n == 2;
	my $harmonic = log( $n - 1 ) + EULER;    # H(n-1) ~= ln(n-1) + gamma
	return 2.0 * $harmonic - ( 2.0 * ( $n - 1 ) / $n );
}

#-------------------------------------------------------------------------------
# Majority-voting (voting => 'majority') helpers.  MVIForest -- Chabchoub,
# Togbe, Boly & Chiky 2022 (see REFERENCES) -- has each tree vote a point
# anomalous when the tree's own score 2**(-h/c(psi)) clears the decision
# threshold, and takes the majority of the votes as the label.  Trees are
# untouched; only these scoring-time aggregation helpers differ from the
# classic mean-path-length pipeline.
#-------------------------------------------------------------------------------

# Depth-domain image of the per-tree score cutoff: a tree votes a point
# anomalous when 2**(-h/c) >= theta, i.e. h <= -c * log2(theta).  Doing the
# log once here keeps exp/log out of the per-point per-tree loops (both C
# and Perl compare raw path lengths against this cut).  Degenerate inputs
# pin the cut so `h <= cut` still behaves: theta <= 0 is cleared by every
# per-tree score (all in (0, 1]), so +inf lets every tree vote; c <= 0 only
# happens for psi <= 1 forests, whose score convention is a flat 0.5 (see
# score_samples), so all trees vote iff theta is at or below that pivot.
sub _depth_cut {
	my ( $theta, $c ) = @_;
	return ( $theta <= 0.5 ? 9**9**9 : -1.0 ) if $c <= 0;
	return 9**9**9                            if $theta <= 0;
	return -$c * log($theta) / log(2);
}

# Smallest number of per-tree anomaly votes that constitutes a majority:
# int(t/2) + 1, i.e. strictly more than half the trees for both odd and
# even tree counts (the paper's "t/2 + 1").
sub _min_votes { return int( $_[0] / 2 ) + 1 }

#-------------------------------------------------------------------------------
# Contamination threshold selection: given the training scores ranked