Algorithm-Classifier-IsolationForest
view release on metacpan or search on metacpan
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
Trains the model directly from a CSV file B<without loading it into RAM>,
for datasets too large to slurp. An Isolation Forest never trains on more
than C<n_trees * sample_size> rows -- each tree uses one independent
sub-sample of C<sample_size> points -- so the working set is bounded by the
model's parameters, not the file size.
The file is read in two (or three) passes:
=over 4
=item 1.
B<Census> -- count the rows (this is the true C<n> that fixes C<psi =
min(sample_size, n)>) and pin the feature width. By default this is an
I<index> pass (see C<index> below): a fast block-scan that also records each
data row's byte offset.
=item 2.
B<Gather> -- retain only the rows the trees actually sampled (chosen in
bounded memory via Floyd's algorithm), then build each tree from its
sub-sample exactly as L</fit> would. With the offset table from pass 1 this
B<seeks straight to the sampled rows> instead of re-scanning the file.
=item 3.
B<Threshold> (only when C<contamination> is set) -- score every row against
the built forest and place the cut at the contamination boundary. The cut
is B<exact>, not estimated: a single min-heap of the C<k+1> largest scores
(C<k = round(contamination * n)>) captures everything
L</decision_threshold> selection needs, with a rare extra pass to resolve a
tie block straddling the boundary. Under C<< use_c => 1 >> (the default when
the C backend is present) this pass runs through the C scorer, so it stays
fast even over millions of rows.
=back
Neither census variant parses cells into numbers or checks for missing
values: only the rows that actually train (via gather) or are scored (the
threshold pass) are validated, so a malformed or missing cell in a
never-used row is not reported. In particular, under C<< missing => 'die' >>
a missing cell is rejected exactly when it appears in a sampled training row.
Because rows are addressed by their position across passes, C<$path> must be
a stable, re-readable file (not a pipe or C<STDIN>).
The first line is skipped as a header when it holds any non-numeric text (a
feature-name row) or exactly matches the model's stored C<feature_names> --
data rows contain only numbers and empty cells. Pass C<< header => 1 >> to
force the first line to be skipped even when it is all-numeric.
Options:
=over 4
=item * C<< header => 1 >> -- always skip the first line as a column header
(otherwise a header is auto-detected as described above).
=item * C<< index => 0 >> -- disable the offset-index pass and use the
streaming two-pass reader instead. The index is on by default: it makes
gather a random-access read of just the sampled rows rather than a second
full scan, but costs an C<8 * n>-byte offset table. When that table would
exceed C<index_max> it is dropped automatically and the fit falls back to
streaming. (In index mode a blank line is one that is empty or contains only
whitespace, judged cheaply; pass C<< index => 0 >> for files where that
matters.)
=item * C<< index_max => bytes >> -- ceiling on the offset table (default
256 MiB). Above it, the index is abandoned mid-scan and gather streams.
=item * C<< c_scan => 0 >> -- validate each scored cell with
C<looks_like_number> in the threshold pass instead of letting the C packer
coerce it. C<c_scan> is on by default and takes effect only on the C
mean-voting scoring path, where it is a large saving over millions of rows;
it produces the identical result on valid data, but coerces a non-numeric
scored cell to C<0.0> (nudging the threshold) rather than dying on it.
=back
Every column is a feature; an empty cell is treated as a missing value and
handled by the model's C<missing> strategy. The resulting model is
identical in shape to one built by L</fit> and is fully deterministic given
the same file, C<seed>, and parameters (though not bit-identical to
L</fit>, whose RNG stream interleaves sampling and tree-building
differently).
Current limitations: C<mungers> and tagged/named columns are not supported
(load such data through L<fit_tagged|/fit_tagged(\@rows)>), and the trees are always built
serially in pure Perl -- C<parallel_fit>/C<use_openmp_fit> are ignored for
the build, though scoring is still accelerated when C<use_c> is on.
my $iforest = Algorithm::Classifier::IsolationForest->new(
n_trees => 100,
sample_size => 256,
contamination => 0.01,
seed => 42,
);
$iforest->fit_from_csv('huge.csv', header => 1);
=cut
sub fit_from_csv {
my ( $self, $path, %opt ) = @_;
croak "fit_from_csv() requires a path to a CSV file"
unless defined $path && length $path;
croak "fit_from_csv(): '$path' is not a readable file"
unless -f $path && -r _;
croak "fit_from_csv() does not support munger models; " . "load the data through fit_tagged/fit instead"
if _plan($self);
# Decide once whether the first line is a header, so every pass skips the
# same line and row indices stay aligned. header => 1 forces it; otherwise
# a first line carrying any non-numeric text (or matching stored
# feature_names) is a header -- data rows hold only numbers and blanks.
my $skip_first = $self->_detect_header( $path, $opt{header} );
# ---- Pass 1: census. Establish the true row count (which fixes psi) and
# pin the feature width. Neither census variant parses cells into numbers
# or checks for missing values -- only the rows that actually train
# (_numify_row, in gather) or get scored (the threshold pass) are validated,
# so a malformed or missing cell in a never-sampled row is not seen.
#
# By default the census is an "index" pass: a block-scan that also records
# each data row's byte offset, letting Pass 2 seek straight to the sampled
# rows instead of re-scanning the whole file. The offset table costs 8*n
# bytes; when that would top index_max (or index => 0 was passed) it is not
# built and both passes fall back to the streaming reader.
my $use_index = exists $opt{index} ? $opt{index} : 1;
my $index_max = defined $opt{index_max} ? $opt{index_max} : ( 256 * 1024 * 1024 );
my ( $n, $n_features, $offsets );
if ($use_index) {
( $n, $n_features, $offsets ) = $self->_index_pass( $path, $skip_first, $index_max );
} else {
( $n, $n_features ) = $self->_census_stream( $path, $skip_first );
}
croak "fit_from_csv(): no data rows in '$path'" unless $n;
# A stored feature_names schema fixes the expected column count.
if ( ref $self->{feature_names} eq 'ARRAY' && @{ $self->{feature_names} } ) {
my $want = scalar @{ $self->{feature_names} };
croak "fit_from_csv(): $want feature_names but CSV has $n_features columns"
unless $want == $n_features;
}
$self->{n_features} = $n_features;
my ( $psi, $limit ) = $self->_resolve_geometry( $n, $n_features );
# ---- Choose which row indices each tree trains on: an independent,
# uniform psi-subset drawn without replacement. Floyd's algorithm draws
# each subset in O(psi) memory, never materialising the 0..n-1 index
# vector _subsample() uses -- for an out-of-core n that vector would not
# fit either. %want maps each needed row index to the (tree, slot) pairs
# awaiting it, so a row several trees picked is gathered once and shared.
srand( $self->{seed} ) if defined $self->{seed};
my @tree_idx; # tree => [ chosen row indices ]
my %want; # row index => [ [tree, slot], ... ]
for my $t ( 0 .. $self->{n_trees} - 1 ) {
my @idx = _sample_indices_distinct( $n, $psi );
$tree_idx[$t] = \@idx;
push @{ $want{ $idx[$_] } }, [ $t, $_ ] for 0 .. $#idx;
}
# ---- Pass 2: gather the sampled rows (validated + coerced by _numify_row).
# With an offset table this seeks straight to them; otherwise it re-scans.
my $pool
= $offsets
? $self->_gather_indexed( $path, $offsets, \%want )
: $self->_gather_stream( $path, $skip_first, \%want );
# Baselines for ablation explanations, learned from the gathered
# sub-sample -- like the impute fill below, the only rows bounded-
# memory fitting ever holds. Before _apply_missing_to_pool, which
# densifies the pool in place (the medians must come from present
# values only, matching fit()). Median is an exact order statistic,
# so the hash-order values() walk cannot change the result.
$self->{feature_baselines} = $self->_compute_feature_baselines( [ values %$pool ] );
# Apply the missing-value strategy to the retained rows (see fit()'s
# _prepare_fit_data; the impute fill is learned from this training
# sub-sample, the only value bounded-memory fitting can compute).
$self->_apply_missing_to_pool($pool);
# ---- Build. Each tree trains on its gathered sub-sample -- structurally
# identical to fit()'s per-tree _build_tree(_subsample(...)).
my @trees;
for my $t ( 0 .. $self->{n_trees} - 1 ) {
my $sample = [ @{$pool}{ @{ $tree_idx[$t] } } ];
push @trees, $self->_build_tree( $sample, 0, $limit );
}
$self->{trees} = \@trees;
# Repack the just-built trees for the C scorer up front. fit() scores its
# learned threshold pure-Perl because its training set is small; the
# streaming contamination pass here may score millions of rows, so paying
# one repack now lets that pass run through the C path instead (bit-
# identical result, minutes -> seconds). The delete first clears any stale
# buffers from a prior fit so the repack reflects the new forest.
delete @$self{qw(_c_nodes _c_coef_idx _c_coef_val)};
$self->_rebuild_c_trees() if $self->{_use_c};
# c_scan (default on): let the C scorer's packer coerce raw cells via SvNV
# in the contamination pass instead of validating each with looks_like_number
# in Perl -- a large saving over millions of rows. It only takes effect on
# the C mean-voting path; see _stream_scores.
my $c_scan = exists $opt{c_scan} ? $opt{c_scan} : 1;
$self->_learn_contamination_threshold_streaming( $path, $skip_first, $n, $c_scan )
if defined $self->{contamination};
return $self;
} ## end sub fit_from_csv
=head2 pack_data(\@data)
Returns an opaque, blessed wrapper around the input dataset that the
scoring methods can use directly, skipping the per-call work of walking
the arrayref-of-arrayrefs and converting each cell into a double. At
high feature counts this is a meaningful win when the same dataset is
scored repeatedly (e.g. interactive threshold tuning, dashboards,
plotting that updates as parameters change).
Requires the Inline::C backend; croaks if C<use_c> is false.
my $packed = $forest->pack_data(\@data);
# Now any of these accept either an arrayref or the packed wrapper:
my $scores = $forest->score_samples($packed);
my $flags = $forest->predict($packed, 0.6);
my ($s, $l) = $forest->score_predict_split($packed);
The wrapper has C<n_pts> and C<n_feats> accessors for introspection.
The feature count is matched against the model on every call; passing a
packed dataset built for a different feature count is a fatal error.
=cut
=head2 path_lengths(\@data)
Returns an arrayref of the mean isolation depth per sample, for inspection.
my $lengths = $forest->path_lengths(\@data);
print "x, y, length\n";
my $int=0;
while (defined($data[$int])) {
print $data[$int][0].', '.$data[$int][1].', '.$lengths->[$int]."\n";
$int++;
}
=cut
sub path_lengths {
my ( $self, $data ) = @_;
$self->_check_fitted;
my $trees = $self->{trees};
my $t = scalar @$trees;
if ( $self->{_use_c} && $self->{_c_nodes} ) {
my ( $n_pts, $nf, $x_packed ) = $self->_resolve_input($data);
my $sums_packed = "\0" x ( $n_pts * 8 );
score_all_xs(
$self->{_c_nodes}, $self->{_c_coef_idx}, $self->{_c_coef_val},
$x_packed, $sums_packed, $n_pts,
$nf, $t, $self->{_use_openmp}
);
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
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>
Mattia Carletti, Matteo Terzi, Gian Antonio Susto (2023). Interpretable Anomaly Detection with DIFFI: Depth-based feature importance of Isolation Forest. Engineering Applications of Artificial Intelligence, vol. 119. 10.1016/j.engappai.2022.105730 (t...
L<https://arxiv.org/abs/2007.11117>
L<https://www.sciencedirect.com/science/article/pii/S0952197622007205>
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>
=head1 AUTHOR
Zane C. Bowers-Hadley, C<< <vvelox at vvelox.net> >>
=head1 LICENSE AND COPYRIGHT
Copyright 2026 Zane C. Bowers-Hadley.
This program is free software; you can redistribute it and/or modify it
under the terms of the GNU Lesser General Public License version 2.1 as
published by the Free Software Foundation.
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser
General Public License for more details.
=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.
#
# Args:
# $n :: a point count, non-negative integer. Either a leaf's size or the
# per-tree sub-sample size psi.
#
# Returns: the expected path length, a float. 0.0 for n <= 1 (nothing is
# left to search) and 1.0 for n == 2, both special-cased because the
# harmonic approximation is only accurate for larger n.
#
# Example:
# _c(1); # 0.0
# _c(256); # ~10.24 -- the normaliser for a default sample_size fit
#-------------------------------------------------------------------------------
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,
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
#
# Returns: arrayref of per-point pivots, each a float in (0, 1],
# positionally matching $data.
#
# Example:
# my $pivots = $self->_majority_pivot_scores( \@training_rows );
# # row i is flagged at per-tree cutoff theta exactly when
# # $pivots->[$i] >= theta
#-------------------------------------------------------------------------------
sub _majority_pivot_scores {
my ( $self, $data ) = @_;
my $trees = $self->{trees};
my $t = scalar @$trees;
my $c = $self->{c_psi};
my $maj = _min_votes($t);
my $rows = $self->_prepare_perl_input($data);
my $nan = $self->{missing} eq 'nan' ? 1 : 0;
# psi <= 1 degenerate forest: every per-tree score is pinned at 0.5
# (matching score_samples' convention), so every pivot is too.
return [ (0.5) x @$rows ] unless $c > 0;
my $inv = log(2) / $c;
my @pivots;
for my $x (@$rows) {
my @paths = sort { $a <=> $b } map { _path_length( $x, $_, 0, $nan ) } @$trees;
push @pivots, exp( -$paths[ $maj - 1 ] * $inv );
}
return \@pivots;
} ## end sub _majority_pivot_scores
# One draw from the standard normal N(0,1) via Box-Muller. Used to pick the
# random hyperplane orientations in Extended Isolation Forest mode.
#
# Args: none. Draws two uniforms from Perl's rand(), so the caller controls
# reproducibility through srand().
#
# Returns: one float from N(0,1), typically within +/-4. Consumes exactly
# two rand() draws, which is what keeps the Perl and C builders in step.
#
# Example:
# srand(42);
# my $coef = _randn(); # a hyperplane coefficient for one feature
sub _randn {
my $u1 = rand() || 1e-12;
my $u2 = rand();
return sqrt( -2.0 * log($u1) ) * cos( TWO_PI * $u2 ) if _NV_IS_DOUBLE;
# Wide-NV perls: round after every operation _c_randn() performs in
# double, so both backends draw the same coefficient bit patterns
# (up to libm's own double-vs-long-double disagreements on rare
# rounding ties).
my $s = _to_double( sqrt( -2.0 * _to_double( log($u1) ) ) );
my $c = _to_double( cos( _to_double( TWO_PI * $u2 ) ) );
return _to_double( $s * $c );
} ## end sub _randn
#-------------------------------------------------------------------------------
# Resolve the derived per-fit geometry from the sample count and feature width,
# storing it on the object and returning ($psi, $limit) for the build loop.
# Factored out of fit() so fit_from_csv() -- which learns n from a streaming
# census rather than an in-RAM array -- produces byte-identical psi/extension/
# depth values. Pure arithmetic: consumes no randomness.
#
# Args:
# $n :: total training rows available, a positive integer. From
# scalar @$data in fit(), or the census count in fit_from_csv().
# $n_features :: the feature width, a positive integer.
#
# Returns: the two-element list ($psi, $limit) -- the per-tree sub-sample
# size and the tree height limit. Also sets c_psi, psi_used,
# extension_level_used (undef outside extended mode) and max_depth_used on
# the object.
#
# Example:
# my ( $psi, $limit ) = $self->_resolve_geometry( 10_000, 4 );
# # ( 256, 8 ) at the default sample_size, since ceil(log2(256)) == 8
#-------------------------------------------------------------------------------
sub _resolve_geometry {
my ( $self, $n, $n_features ) = @_;
# The sub-sample cannot be larger than the data set itself.
my $psi = min( $self->{sample_size}, $n );
$self->{c_psi} = _c($psi);
$self->{psi_used} = $psi;
# Resolve the extension level against the data's dimensionality.
if ( $self->{mode} eq 'extended' ) {
my $max_ext = $n_features - 1;
my $ext
= defined $self->{extension_level}
? $self->{extension_level}
: $max_ext;
$ext = 0 if $ext < 0;
$ext = $max_ext if $ext > $max_ext;
$self->{extension_level_used} = $ext;
} else {
$self->{extension_level_used} = undef;
}
# Height limit: the average tree height ceil(log2(psi)). Past this depth the
# remaining points are scored using the c(size) adjustment instead.
my $limit
= defined $self->{max_depth}
? $self->{max_depth}
: ceil( log($psi) / log(2) );
$limit = 1 if $limit < 1;
$self->{max_depth_used} = $limit;
return ( $psi, $limit );
} ## end sub _resolve_geometry
#-------------------------------------------------------------------------------
# fit_from_csv() machinery.
#-------------------------------------------------------------------------------
# Inspect the first non-blank line and report whether it is a header to skip
# rather than train on. $forced (the header => option) makes it unconditional;
# otherwise a line is a header when it carries any non-numeric text -- data rows
# hold only numbers and empty cells -- or exactly matches stored feature_names.
#
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
#
# Args:
# $path :: path to the CSV file, which must be readable.
# $skip_first :: true to drop the first non-blank line as a header.
#
# Returns: the two-element list ($n, $nf) -- the data row count and the
# feature width taken from the first data row. Both undef-free, though $n
# is 0 and $nf undef for a file with no data rows. Croaks on a row whose
# column count disagrees with the first row's.
#
# Example:
# my ( $n, $nf ) = $self->_census_stream( 'train.csv', 1 ); # ( 1_000_000, 4 )
sub _census_stream {
my ( $self, $path, $skip_first ) = @_;
my $reader = $self->_csv_reader( $path, $skip_first, 0 );
my ( $n, $nf ) = ( 0, undef );
while ( my ( $row, $line ) = $reader->() ) {
$nf //= scalar @$row;
croak "fit_from_csv(): line $line of '$path' has " . scalar(@$row) . " columns but expected $nf"
unless @$row == $nf;
$n++;
}
return ( $n, $nf );
} ## end sub _census_stream
# Streaming gather (no offset table): re-scan the file, numifying only the
# sampled rows. Companion to _census_stream.
#
# Args:
# $path :: path to the CSV file, which must be readable.
# $skip_first :: true to drop the first non-blank line as a header.
# $want :: hashref used as a set -- its keys are the data row indices to
# keep, counting from 0 over the non-blank data lines.
#
# Returns: hashref keyed by the same indices, each value the numified row as
# an arrayref. Indices absent from the file simply do not appear.
#
# Example:
# my $pool = $self->_gather_stream( 'train.csv', 1, { 0 => 1, 7 => 1 } );
# # { 0 => [ 0.9, 0.4 ], 7 => [ 1.2, 0.3 ] }
sub _gather_stream {
my ( $self, $path, $skip_first, $want ) = @_;
my $reader = $self->_csv_reader( $path, $skip_first, 0 );
my %pool;
my $i = 0;
while ( my ( $row, $line ) = $reader->() ) {
if ( exists $want->{$i} ) {
$self->_numify_row( $row, "line $line" );
$pool{$i} = $row;
}
$i++;
}
return \%pool;
} ## end sub _gather_stream
# Index census: one block-scan that counts the data rows, pins the feature
# width, AND records each data row's byte offset so gather can seek straight to
# the sampled rows. Blank lines are skipped and the header dropped exactly as
# the reader does, so offset i is the i-th data row. The offset table costs
# 8*n bytes; once it would exceed $max_off it is dropped (returning undef) and
# only the count survives, so the caller falls back to the streaming gather.
#
# Args:
# $path :: path to the CSV file, which must be readable.
# $skip_first :: true to drop the first non-blank line as a header.
# $max_off :: byte ceiling for the offset table. 0 disables the table
# outright, making this a pure counting pass.
#
# Returns: the three-element list ($n, $nf, $offsets) -- the data row count,
# the feature width, and either an arrayref of per-row byte offsets (element
# i is data row i's start) or undef when the table was disabled or went over
# budget.
#
# Example:
# my ( $n, $nf, $off ) = $self->_index_pass( 'train.csv', 1, 64 * 1024 * 1024 );
# # ( 1_000_000, 4, [ 12, 31, 49, ... ] ), or $off undef past 8 MB of table
sub _index_pass {
my ( $self, $path, $skip_first, $max_off ) = @_;
open my $fh, '<', $path
or croak "fit_from_csv(): cannot open '$path': $!";
binmode $fh;
my @off;
my $store = $max_off > 0 ? 1 : 0;
my $cap = int( $max_off / 8 );
my $n = 0;
my $skipped = 0;
my $nf;
# Consider the line at ($$sref, $off .. $off+$len). To stay fast we avoid
# copying the line: a zero-length line is empty, and any line whose first
# byte is a digit/sign/dot (>= '!') is non-blank without further checks --
# only a line starting with whitespace (< '!') is materialised to apply the
# reader's /^\s*$/ blank test. $abs is its absolute byte offset.
my $feed = sub {
my ( $abs, $sref, $off, $len ) = @_;
return if $len == 0;
if ( substr( $$sref, $off, 1 ) lt '!' ) { # leading whitespace: maybe blank
return if substr( $$sref, $off, $len ) !~ /\S/;
}
if ( $skip_first && !$skipped ) { $skipped = 1; return; }
$nf //= scalar( () = split /,/, substr( $$sref, $off, $len ), -1 ); # width from row 1
$n++;
return unless $store;
push @off, $abs;
if ( @off > $cap ) { $store = 0; @off = () } # over budget: abandon the table
}; ## end $feed = sub
my ( $carry, $file_pos ) = ( '', 0 ); # $file_pos = abs offset of $carry's start
my $buf;
while ( my $got = read( $fh, $buf, 1 << 20 ) ) {
my $s = $carry . $buf;
my $p = 0;
my $nl;
while ( ( $nl = index( $s, "\n", $p ) ) >= 0 ) {
my $len = $nl - $p;
$len-- if $len && substr( $s, $nl - 1, 1 ) eq "\r"; # exclude a CRLF's CR
$feed->( $file_pos + $p, \$s, $p, $len );
$p = $nl + 1;
}
$carry = substr( $s, $p );
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
}
my @idx = sort { $a <=> $b } keys %seen;
return @idx;
} ## end sub _sample_indices_distinct
# Apply the missing-value strategy to the gathered pool (hashref index => row),
# densifying in place so the pure-Perl _build_tree sees defined cells. Mirrors
# _prepare_fit_data, except impute learns its fill from the training sub-sample
# rather than the full file -- the only fill bounded-memory fitting can form.
#
# Args:
# $pool :: hashref of row index => arrayref of cells, as returned by
# _gather_stream or _gather_indexed. Rewritten in place.
#
# Returns: nothing. Under zero/impute every row in $pool comes back dense;
# under impute the learned fill is also stored in $self->{missing_fill}.
# die and nan return untouched (die data is already dense, nan wants its
# undefs kept).
#
# Example:
# my $pool = $self->_gather_indexed( $path, $offsets, $want );
# $self->_apply_missing_to_pool($pool); # undef cells now carry the fill
sub _apply_missing_to_pool {
my ( $self, $pool ) = @_;
my $m = $self->{missing};
return if $m eq 'die' || $m eq 'nan'; # die: already dense; nan: keep undef
my $nf = $self->{n_features};
my $fill;
if ( $m eq 'impute' ) {
$fill = $self->_compute_impute_fill( [ values %$pool ] );
$self->{missing_fill} = $fill;
delete $self->{_fill_packed};
} else { # zero
$fill = [ (0) x $nf ];
}
for my $i ( keys %$pool ) {
my $r = $pool->{$i};
$pool->{$i} = [ map { defined $r->[$_] ? $r->[$_] : $fill->[$_] } 0 .. $nf - 1 ];
}
return;
} ## end sub _apply_missing_to_pool
# Streaming counterpart of _learn_contamination_threshold: learn the exact
# score cutoff for the contamination rate without holding every score. k+1
# largest scores are enough for _threshold_from_ranked's boundary logic; a
# min-heap keeps them in one scoring pass, and (only under a boundary tie) one
# extra pass resolves the tie block's edges.
#
# Args:
# $path :: path to the CSV file the model was just fitted from.
# $skip_first :: true to drop the first non-blank line as a header.
# $n :: the census row count, which fixes how many rows k stands for.
# $c_scan :: true to let the C packer coerce cells, skipping the Perl
# numeric validation on the scoring passes. See _stream_scores.
#
# Returns: nothing. Sets $self->{threshold} to the same value the in-RAM
# _learn_contamination_threshold would have produced for this data.
#
# Example:
# $self->_learn_contamination_threshold_streaming( 'train.csv', 1, 1_000_000, 1 );
sub _learn_contamination_threshold_streaming {
my ( $self, $path, $skip_first, $n, $c_scan ) = @_;
my $k = int( $self->{contamination} * $n + 0.5 );
$k = 1 if $k < 1;
$k = $n if $k > $n;
# Whole set flagged: sit the cut just below the global minimum score.
if ( $k >= $n ) {
my $min;
$self->_stream_scores( $path, $skip_first, sub { $min = $_[0] if !defined $min || $_[0] < $min }, $c_scan );
$self->{threshold} = $min - 1e-9;
return;
}
# One scoring pass keeps the k+1 largest scores (a min-heap rooted at the
# smallest kept). contamination <= 0.5 bounds k at n/2, so this tail is
# always the smaller side of the split.
my @heap;
my $cap = $k + 1;
$self->_stream_scores(
$path,
$skip_first,
sub {
my $s = $_[0];
if ( @heap < $cap ) { _heap_push( \@heap, $s ) }
elsif ( $s > $heap[0] ) { _heap_replace_root( \@heap, $s ) }
},
$c_scan
);
my @desc = sort { $b <=> $a } @heap; # k+1 largest, descending
my $v = $desc[ $k - 1 ]; # k-th largest
my $lo = $desc[$k]; # (k+1)-th largest
# Clean gap at the boundary: cut midway, exactly as _threshold_from_ranked.
if ( $lo < $v ) {
$self->{threshold} = ( $v + $lo ) / 2.0;
return;
}
# A tie block of value $v straddles rank k. Reproduce _threshold_from_ranked's
# tie branch: locate the block's edges (i = first index at $v, j = first
# index below it) and the neighbouring scores with one more pass.
my ( $cnt_gt, $cnt_eq, $above, $below ) = ( 0, 0, undef, undef );
$self->_stream_scores(
$path,
$skip_first,
sub {
my $s = $_[0];
if ( $s > $v ) {
$cnt_gt++;
$above = $s if !defined $above || $s < $above; # smallest > $v
} elsif ( $s == $v ) {
$cnt_eq++;
} else {
$below = $s if !defined $below || $s > $below; # largest < $v
}
},
$c_scan
);
my $i = $cnt_gt; # first rank holding $v
my $j = $cnt_gt + $cnt_eq; # first rank below $v
if ( $i > 0 && ( $k - $i ) < ( $j - $k ) ) {
$self->{threshold} = ( $above + $v ) / 2.0; # exclude the block
} elsif ( $j < $n ) {
$self->{threshold} = ( $v + $below ) / 2.0; # include the block
} else {
$self->{threshold} = $v - 1e-9; # block runs to the end
}
return;
} ## end sub _learn_contamination_threshold_streaming
# Stream the CSV, score rows in flat batches (through the same mean/majority
# path score_samples/predict use), and invoke $cb->($score) for each row.
# c_scan fast path: when scoring runs through the C packer (mean voting, use_c,
# trees packed) the packer coerces each cell via SvNV, so the reader can run
# raw (parse => 0) and skip the Perl looks_like_number validation. Every other
# path parses (parse => 1) so its Perl scorer sees real numbers.
#
# Args:
# $path :: path to the CSV file, which must be readable.
# $skip_first :: true to drop the first non-blank line as a header.
# $cb :: coderef invoked once per data row as $cb->($score), in file order.
# The score is the mean-mode anomaly score, or the majority pivot
# under voting => 'majority'.
# $c_scan :: true to allow the raw-cell fast path described above.
#
# Returns: nothing; everything is delivered through $cb.
#
# Example:
# my $max;
# $self->_stream_scores( 'train.csv', 1,
# sub { $max = $_[0] if !defined $max || $_[0] > $max }, 1 );
sub _stream_scores {
my ( $self, $path, $skip_first, $cb, $c_scan ) = @_;
my $majority = $self->{voting} eq 'majority' ? 1 : 0;
my $c_coerce = $c_scan && $self->{_use_c} && $self->{_c_nodes} && !$majority;
my $reader = $self->_csv_reader( $path, $skip_first, $c_coerce ? 0 : 1 );
# The c_coerce path lets the C packer turn any non-numeric cell into 0.0 via
# SvNV; silence the per-cell "isn't numeric" warnings that intentional
# coercion raises (clean data produces none). Other warnings pass through.
local $SIG{__WARN__};
$SIG{__WARN__} = sub { $_[0] =~ /isn't numeric/ or warn $_[0] }
if $c_coerce;
my @batch;
my $flush = sub {
return unless @batch;
my $scores
= $majority
? $self->_majority_pivot_scores( \@batch )
: $self->score_samples( \@batch );
$cb->($_) for @$scores;
@batch = ();
};
while ( my ($row) = $reader->() ) {
push @batch, $row;
$flush->() if @batch >= 8192;
}
$flush->();
return;
} ## end sub _stream_scores
# Minimal binary min-heap over a plain arrayref (root = smallest). Paired
# with _heap_replace_root to keep the k+1 largest scores of a stream in
# bounded memory -- push until full, then replace the root whenever a
# bigger value turns up.
#
# Append a value and sift it up into place.
#
( run in 1.027 second using v1.01-cache-2.11-cpan-9789f410c06 )