view release on metacpan or  search on metacpan

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

	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} };

	my $params = {
		n_trees          => $self->{n_trees},
		window_size      => $self->{window_size},
		max_leaf_samples => $self->{max_leaf_samples},
		growth           => $self->{growth},
		subsample        => $self->{subsample},
	};
	$params->{contamination} = $self->{contamination} if defined $self->{contamination};

	return JSON::PP->new->canonical(1)->encode(
		{
			format             => 'Algorithm::Classifier::IsolationForest::Prototype',
			version            => 1,
			class              => 'online',
			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

Filippo Leveni, Guilherme Weigert Cassales, Bernhard Pfahringer, Albert
Bifet, Giacomo Boracchi (2024). Online Isolation Forest.

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
###
###

sub _check_learned {
	my ($self) = @_;
	croak "model has not learned any data yet; call learn() first"
		unless $self->{seen} > 0;
}

# Validate one incoming sample, apply the missing-value strategy, and
# return a fresh dense copy (the window owns its rows; the caller may
# reuse or mutate the original).  Locks in n_features on first contact.
sub _prep_row {
	my ( $self, $row, $caller ) = @_;
	croak "$caller: each sample must be an arrayref of features"
		unless ref $row eq 'ARRAY' && @$row;

	if ( !defined $self->{n_features} ) {
		$self->{n_features} = scalar @$row;
	} elsif ( scalar @$row != $self->{n_features} ) {
		croak "$caller: sample has " . scalar(@$row) . " features but model expects " . $self->{n_features};
	}

	if ( $self->{missing} eq 'die' ) {
		for my $f ( 0 .. $#$row ) {
			next if defined $row->[$f];
			croak "$caller: undef feature value at column $f; "
				. "construct with missing => 'zero' to learn from data with missing values";
		}
		return [@$row];
	}

	# zero: a missing cell counts as the value 0.
	return [ map { $_ // 0 } @$row ];
} ## end sub _prep_row

# The depth budget for n points: how deep a tree fed n points is allowed
# (learn) or expected (scoring normalisation, per-leaf adjustment) to
# go.  log base 4 = log(2 * branching_factor) with binary trees.  Under
# max_leaf_samples points there is nothing to isolate: 0.
sub _rpl {
	my ( $self, $n ) = @_;
	my $eta = $self->{max_leaf_samples};
	return 0 if $n < $eta;
	return log( $n / $eta ) / _LOG4;
}

# How many points a node at $depth needs before it may split (or below
# which, on forgetting, it collapses back into a leaf).
sub _split_threshold {
	my ( $self, $depth ) = @_;
	return $self->{max_leaf_samples} * ( $self->{growth} eq 'adaptive' ? 2**$depth : 1 );
}

# Number of points the model currently reflects: the window fill, or the
# whole stream when forgetting is disabled.
sub _data_size {
	my ($self) = @_;
	return $self->{window_size} ? scalar @{ $self->{window} } : $self->{seen};
}

# exp() multiplier turning a per-sample depth SUM into the normalised
# anomaly score: 2**(-(sum/t)/norm) == exp(-sum * log(2)/(t*norm)).
# _EPS keeps a zero normaliser (fewer than max_leaf_samples points seen)
# well-defined; every depth is 0 then, so everything scores 1.0.
sub _score_inv {
	my ($self) = @_;
	my $norm = $self->_rpl( $self->_data_size * $self->{subsample} );
	return _LOG2 / ( $self->{n_trees} * ( $norm + _EPS ) );
}

#-------------------------------------------------------------------------------

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

	return exp( -$sum * $self->_score_inv );
} ## end sub _score_row

#-------------------------------------------------------------------------------
# C-accelerated scoring.
#
# The parent class's Inline::C scorer walks immutable packed node buffers;
# online trees mutate on every learned point.  The bridge is a lazily
# built snapshot: the first scoring call after any mutation flattens the
# live trees into the parent's packed node layout (below) and every
# scoring call until the next mutation reuses it.  _learn_row -- the one
# choke point all mutations flow through -- drops the snapshot.
#
# Online trees are axis-only, so they map onto the parent's 6-double node
# records directly:
#
#   leaf:  [0, count, _rpl(count), 0, 0, 0]
#   axis:  [1, attr,  split,       li, ri, 0]
#
# The parent packs c(leaf size) into slot 2 and its C walker returns
# depth + slot2 at a leaf; packing the online depth-budget adjustment
# _rpl(count) there instead makes score_all_xs compute exactly the
# pure-Perl _depth_of value, so every downstream C helper (finalize_*,
# predict_sums_xs, score_predict_*) applies unchanged.  The per-tree
# coefficient buffers are empty -- there are no oblique nodes -- and only
# exist because score_all_xs expects them.
#
# score_learn deliberately never uses this path: it mutates the trees
# after every single point, so the snapshot could never be reused and
# repacking per point would cost more than the walks it replaces.
#-------------------------------------------------------------------------------

# Drop the packed snapshot; called on every mutation.
sub _invalidate_c_trees {
	delete @{ $_[0] }{qw(_c_nodes _c_coef_idx _c_coef_val)};
	return;
}

# Build (or reuse) the packed snapshot.  Returns true when the C scoring
# path may be taken, false when the caller must use the pure-Perl walk.
sub _ensure_c_trees {
	my ($self) = @_;
	return 0 unless $self->{_use_c};
	return 1 if $self->{_c_nodes};

	my ( @c_nodes, @c_coef_idx, @c_coef_val );
	my $empty_idx = pack('l*');
	my $empty_val = pack('d*');
	for my $tree ( @{ $self->{trees} } ) {
		push @c_nodes,    $self->_pack_online_tree( $tree->{root} );
		push @c_coef_idx, $empty_idx;
		push @c_coef_val, $empty_val;
	}
	$self->{_c_nodes}    = \@c_nodes;
	$self->{_c_coef_idx} = \@c_coef_idx;
	$self->{_c_coef_val} = \@c_coef_val;
	return 1;
} ## end sub _ensure_c_trees

# Flatten one live tree into the parent's packed node buffer (DFS
# pre-order, root at index 0 -- the origin score_all_xs walks from).
sub _pack_online_tree {
	my ( $self, $root ) = @_;

	# A tree that has not learned anything walks as depth 0 with a zero
	# adjustment: one empty leaf record.
	return pack( 'd*', 0.0, 0.0, 0.0, 0.0, 0.0, 0.0 ) unless defined $root;

	my @node_data;
	my $assign;
	$assign = sub {
		my ($node) = @_;
		my $my_idx = scalar @node_data;
		push @node_data, undef;    # reserve slot; filled in after children
		if ( $node->[_N_TYPE] == _NT_LEAF ) {
			$node_data[$my_idx]
				= [ 0.0, $node->[_N_COUNT] + 0.0, $self->_rpl( $node->[_N_COUNT] ) + 0.0, 0.0, 0.0, 0.0 ];
		} else {
			my $li = $assign->( $node->[_N_LEFT] );
			my $ri = $assign->( $node->[_N_RIGHT] );
			$node_data[$my_idx]
				= [ 1.0, $node->[_N_ATTR] + 0.0, $node->[_N_SPLIT] + 0.0, $li + 0.0, $ri + 0.0, 0.0 ];
		}
		return $my_idx;
	}; ## end $assign = sub
	$assign->($root);
	return pack( 'd*', map { @$_ } @node_data );
} ## end sub _pack_online_tree

# Pack the query rows into the row-major double buffer score_all_xs
# reads, via the parent's C row walker.  miss_mode 0 maps an undef cell
# to 0.0, matching the pure-Perl walk's "// 0".
sub _pack_input {
	my ( $self, $data ) = @_;
	my $n_pts    = scalar @$data;
	my $nf       = $self->{n_features};
	my $x_packed = "\0" x ( $n_pts * $nf * 8 );
	Algorithm::Classifier::IsolationForest::pack_input_xs( $data, $x_packed, $n_pts, $nf, 0, '' );
	return ( $n_pts, $x_packed );
}

# Lazily learn the contamination threshold from the current window the
# first time a predict-family method needs it.  A model with no retained
# window (window_size 0) stays on the 0.5 fallback until the caller runs
# relearn_threshold with data.
sub _ensure_threshold {
	my ($self) = @_;
	return
		   if !defined $self->{contamination}
		|| defined $self->{threshold}
		|| !@{ $self->{window} };
	$self->relearn_threshold;
	return;
}

1;