Result:
found more than 1264 distributions - search limited to the first 2001 files matching your query
( run in 1.324 )
Algorithm-Bertsekas
view release on metacpan or search on metacpan
lib/Algorithm/Bertsekas.pm view on Meta::CPAN
my $matrix_value = $seen_ghost ? 0 : $matrix[$person]->[$object];
$current_value{$object} = $matrix_value - $price_object{$object};
push @updated_price, $object if ( $objects_desired_by_this{$person}{$object} == $current_value{$object} );
if ( $current_value{$object} > $Opt01ValForPersonI ) # search for the best 3 objects
{
$Opt03ValForPersonI = $Opt02ValForPersonI;
$Opt03ObjForPersonI = $Opt02ObjForPersonI;
$Opt02ValForPersonI = $Opt01ValForPersonI;
$Opt02ObjForPersonI = $Opt01ObjForPersonI;
lib/Algorithm/Bertsekas.pm view on Meta::CPAN
next if ( defined $current_value{$object} );
my $matrix_value = $seen_ghost ? 0 : $matrix[$person]->[$object];
$current_value{$object} = $matrix_value - $price_object{$object};
if ( $current_value{$object} > $Opt01ValForPersonI_new_list ) # to find the best 3 objects in the complementary subset <new list>
{
$Opt03ValForPersonI_new_list = $Opt02ValForPersonI_new_list;
$Opt03ObjForPersonI_new_list = $Opt02ObjForPersonI_new_list;
$Opt02ValForPersonI_new_list = $Opt01ValForPersonI_new_list;
$Opt02ObjForPersonI_new_list = $Opt01ObjForPersonI_new_list;
lib/Algorithm/Bertsekas.pm view on Meta::CPAN
$Opt02ValForPersonI_new_list, defined $Opt02ObjForPersonI_new_list ? $Opt02ObjForPersonI_new_list : '',
$Opt03ValForPersonI_new_list, defined $Opt03ObjForPersonI_new_list ? $Opt03ObjForPersonI_new_list : '';
}
}
# to find the best 3 out of 6 objects
if ( $Opt01ValForPersonI_new_list > $Opt01ValForPersonI )
{
$Opt03ValForPersonI = $Opt02ValForPersonI;
$Opt03ObjForPersonI = $Opt02ObjForPersonI;
lib/Algorithm/Bertsekas.pm view on Meta::CPAN
if ( $verbose >= 8 ){
my @old_list = sort { $a <=> $b } @objects_with_greater_benefits;
my @new_list = sort { $a <=> $b } keys %{$objects_desired_by_this{$person}};
@updated_price = sort { $a <=> $b } @updated_price;
my @best_3_objects = ( $Opt01ObjForPersonI, $Opt02ObjForPersonI, $Opt03ObjForPersonI );
my $msg = $locked_list{$person} ? '[locked list] ' : '';
@objects_with_same_values = sort { $a <=> $b } @objects_with_same_values;
$this_person_can_choose_n_different_objects{$person}{'objects'} = \@objects_with_same_values; #reference to an array
printf $output "<> PersonI = %3s ; %3s objects desired by this person (old list) = (@old_list) ; objects whose current values are still updated = (@updated_price) : %2s >= 1 ? \n", $person, scalar @old_list, scalar @updated_price;
printf $output "<> PersonI = %3s ; %3s objects desired by this person (new list) = (@new_list) $msg; \@best_3_objects = (@best_3_objects) \n", $person, scalar @new_list if ( defined $Opt03ObjForPersonI );
printf $output "<> PersonI = %3s chose ObjectJ = %3s ; \$bidForPersonI %10.5f = \$Opt01ValForPersonI %.5f - \$Opt02ValForPersonI %.5f + \$epsilon %.5f \n", $person, $Opt01ObjForPersonI, $bidForPersonI, $Opt01ValForPersonI, $Opt02ValForPersonI, $e...
printf $output "<> PersonI = %3s ; these objects (@objects_with_same_values) have the same values \$Opt01ValForPersonI = %10.5f ; \$Opt01ObjForPersonI = $Opt01ObjForPersonI ; *** equal values *** \n", $person, $Opt01ValForPersonI if (@objects_wit...
}
}
}
lib/Algorithm/Bertsekas.pm view on Meta::CPAN
assigned to. The numbers in the table are the costs associated with each particular assignment."
In Auction Algorithm (AA) the N persons iteratively submit the bids to M objects.
The AA take cost Matrix N×M = [aij] as an input and produce assignment as an output.
In the AA persons iteratively submit the bids to the objects which are then reassigned
to the bidders which offer them the best bid.
Another application is to find the (nearest/more distant) neighbors.
The distance between neighbors can be represented by a matrix or a weight function, for example:
1: f(i,j) = abs ($array1[i] - $array2[j])
2: f(i,j) = ($array1[i] - $array2[j]) ** 2
Algorithm-BestChoice
view release on metacpan or search on metacpan
lib/Algorithm/BestChoice.pm view on Meta::CPAN
use warnings;
use strict;
=head1 NAME
Algorithm::BestChoice - Choose the best
=head1 VERSION
Version 0.01
lib/Algorithm/BestChoice.pm view on Meta::CPAN
$chooser->add( match => purple, value => grape, rank => 20 ) # Delicious
$chooser->add( match => yellow, value => banana )
$chooser->add( match => yellow, value => lemon rank => -5 ) # Too sour
my $favorite;
$favorite = $chooser->best( red ) # apple is the favorite red
$favorite = $chooser->best( [ red, yellow, purple ] ) # grape is the favorite among red, yellow, and purple
=head1 DESCRIPTION
An Algorithm::BestChoice object is similar to a hash, except it returns a result based on a given key AND relative ranking. That is, you can associate multiple values
with a single key, and differentiate them by using a rank (or weight).
lib/Algorithm/BestChoice.pm view on Meta::CPAN
Add a possible choice to the chooser
The arguments are:
match The key for the choice, can be a string or a regular expression
value The value to associate with the key (what is returned by ->best)
rank An optional numeric weight, the default is 0 (>0 is better, <0 is worse)
=head2 $value = $chooser->best( <criterion> )
Given criterion, ->best will return the value that 1. has a matching matcher and 2. has the highest rank
=cut
# TODO: Document ->best() ->best( [ ... ] )
use Moose;
use Algorithm::BestChoice::Matcher;
use Algorithm::BestChoice::Ranker;
lib/Algorithm/BestChoice.pm view on Meta::CPAN
my $option = Algorithm::BestChoice::Option->new( matcher => $matcher, ranker => $ranker, value => $given{value} );
push @{ $self->options }, $option;
}
sub _best {
my $self = shift;
my $key = shift;
my @tally;
for my $option (@{ $self->options }) {
lib/Algorithm/BestChoice.pm view on Meta::CPAN
return @tally;
}
# TODO: Test for this multi-key ranker
# TODO: Probably want to give different weights to different keys!
sub best {
my $self = shift;
my @tally = map { $self->_best( $_ ) } @_ ? map { ref $_ eq 'ARRAY' ? @$_ : $_ } @_ : (undef);
@tally = sort { $b->rank <=> $a->rank } @tally;
@tally = map { $_->value } @tally;
return wantarray ? @tally : $tally[0];
}
lib/Algorithm/BestChoice.pm view on Meta::CPAN
Robert Krimen, C<< <rkrimen at cpan.org> >>
=head1 BUGS
Please report any bugs or feature requests to C<bug-algorithm-bestchoice at rt.cpan.org>, or through
the web interface at L<http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Algorithm-BestChoice>. I will be notified, and then you'll
automatically be notified of progress on your bug as I make changes.
Algorithm-BinPack-2D
view release on metacpan or search on metacpan
lib/Algorithm/BinPack/2D.pm view on Meta::CPAN
sub sort_items {
my $items = shift;
sort {
# Sorting by max(width, height) is the best heuristic.
my $abigger = $a->{width} > $a->{height} ? $a->{width} : $a->{height};
my $bbigger = $b->{width} > $b->{height} ? $b->{width} : $b->{height};
my $asmaller = $a->{width} <= $a->{height} ? $a->{width} : $a->{height};
my $bsmaller = $b->{width} <= $b->{height} ? $b->{width} : $b->{height};
Algorithm-BinPack
view release on metacpan or search on metacpan
t/Algorithm-BinPack.t view on Meta::CPAN
isa_ok($bp, "Algorithm::BinPack");
is($bp->{binsize}, 4);
$bp->add_item(label => 'one', size => 1);
$bp->add_item(label => 'two', size => 2);
$bp->add_item(label => 'three', size => 3, misc => "This item is the best");
$bp->add_item(label => 'four', size => 4, desc => "The fourth item");
my @bins = $bp->pack_bins;
# check pack order
t/Algorithm-BinPack.t view on Meta::CPAN
is($bins[3]{items}[0]{label}, "another");
is($bins[4]{items}[0]{label}, "two");
# check extra keys
is($bins[0]{items}[0]{desc}, "The fourth item");
is($bins[1]{items}[0]{misc}, "This item is the best");
is($bins[2]{items}[0]{manual}, "Item was added manually");
is($bins[3]{items}[0]{meta}, "data");
# capture and test warning messages
my $warning;
Algorithm-BloomFilter
view release on metacpan or search on metacpan
#ifndef IVSIZE
# ifdef LONGSIZE
# define IVSIZE LONGSIZE
# else
# define IVSIZE 4 /* A bold guess, but the best we can make. */
# endif
#endif
#ifndef UVTYPE
# define UVTYPE unsigned IVTYPE
#endif
#ifndef PERL_MAGIC_ext
# define PERL_MAGIC_ext '~'
#endif
/* That's the best we can do... */
#ifndef sv_catpvn_nomg
# define sv_catpvn_nomg sv_catpvn
#endif
#ifndef sv_catsv_nomg
Algorithm-BreakOverlappingRectangles
view release on metacpan or search on metacpan
BreakOverlappingRectangles.xs view on Meta::CPAN
sort_inplace(pTHX_ double **v, int size) {
sortsv((SV**)v, size, (SVCOMPARE_t)&double_cmp);
}
static NV
find_best_cut(pTHX_ AV *rects, I32 start, I32 end, int dir, NV *bestv) {
NV **v0, **v1, **vc0, **vc1;
NV v, med, best;
int op, cl;
int i;
SV **svs;
I32 size = end - start;
my_assert(bestv);
DUMP("fbc in", rects, start);
DP(fprintf(stderr, "end: %d\n", end));
Newx(v0, size + 1, NV *);
BreakOverlappingRectangles.xs view on Meta::CPAN
sort_inplace(aTHX_ v0, size);
sort_inplace(aTHX_ v1, size);
op = cl = 0;
med = 0.5 * size;
best = .24 * sqr(size);
my_assert(best >= 0);
while (*v0 && *v1) {
NV v, good;
NV l, r;
BreakOverlappingRectangles.xs view on Meta::CPAN
r = size - cl - med;
good = sqr(l) + sqr(r);
my_assert(good >= 0);
if (good < best) {
DP(fprintf(stderr, "find_best_cut l: %.2f, r: %.2f, good: %.2f\n", l, r, good));
best = good;
*bestv = v;
}
}
Safefree(vc0);
Safefree(vc1);
return best;
}
static void
_break(pTHX_ AV *rects, I32 start, AV *parts);
BreakOverlappingRectangles.xs view on Meta::CPAN
return;
}
static void
_break(pTHX_ AV *rects, I32 start, AV *parts) {
NV bestx, bestxx, besty, bestyy, div;
int off;
I32 i, j, middle, end;
SV **svs;
DUMP("break", rects, start);
BreakOverlappingRectangles.xs view on Meta::CPAN
end = av_len(rects) + 1;
if ((end - start) <= BRUTEFORCECUTOFF)
return _brute_force_break(aTHX_ rects, start, parts);
bestx = find_best_cut(aTHX_ rects, start, end, 'x', &bestxx);
besty = ((bestx == 0) ? 1 : find_best_cut(aTHX_ rects, start, end, 'y', &bestyy));
if (bestx < besty) {
off = X0;
div = bestxx;
DP(fprintf(stderr, "cutting at x=%.0f, best=%.2f\n", bestxx, bestx));
}
else {
off = Y0;
div = bestyy;
DP(fprintf(stderr, "cutting at y=%.0f, best=%.2f\n", bestyy, besty));
}
svs = AvARRAY(rects);
i = start;
middle = end;
Algorithm-Burg
view release on metacpan or search on metacpan
END OF TERMS AND CONDITIONS
Appendix: How to Apply These Terms to Your New Programs
If you develop a new program, and you want it to be of the greatest
possible use to humanity, the best way to achieve this is to make it
free software which everyone can redistribute and change under these
terms.
To do so, attach the following notices to the program. It is safest to
attach them to the start of each source file to most effectively convey
Algorithm-C3
view release on metacpan or search on metacpan
END OF TERMS AND CONDITIONS
Appendix: How to Apply These Terms to Your New Programs
If you develop a new program, and you want it to be of the greatest
possible use to humanity, the best way to achieve this is to make it
free software which everyone can redistribute and change under these
terms.
To do so, attach the following notices to the program. It is safest to
attach them to the start of each source file to most effectively convey
Algorithm-CP-IZ
view release on metacpan or search on metacpan
fallback/const-c.inc view on Meta::CPAN
static int
constant_16 (pTHX_ const char *name, IV *iv_return) {
/* When generated this function returned values for the list of names given
here. However, subsequent manual editing may have added or removed some.
CS_ERR_NO_MEMORY IZ_VERSION_MAJOR IZ_VERSION_MINOR IZ_VERSION_PATCH */
/* Offset 13 gives the best switch position. */
switch (name[13]) {
case 'J':
if (memEQ(name, "IZ_VERSION_MAJOR", 16)) {
/* ^ */
#ifdef IZ_VERSION_MAJOR
fallback/const-c.inc view on Meta::CPAN
}
break;
case 15:
/* Names all of length 15. */
/* CS_ERR_GETVALUE CS_ERR_OVERFLOW */
/* Offset 10 gives the best switch position. */
switch (name[10]) {
case 'R':
if (memEQ(name, "CS_ERR_OVERFLOW", 15)) {
/* ^ */
#ifdef CS_ERR_OVERFLOW
Algorithm-CRF
view release on metacpan or search on metacpan
t/test.data view on Meta::CPAN
said VBD O
1989 CD B
will MD O
be VB O
the DT B
best JJS I
year NN I
in IN O
its PRP$ B
history NN I
, , O
t/test.data view on Meta::CPAN
friends NNS B
that WDT O
patience NN B
is VBZ O
the DT B
best JJS I
weapon NN I
against IN O
the DT B
gringos NNS I
, , O
t/test.data view on Meta::CPAN
for IN O
5 NN B
% NN I
, , O
at IN O
best JJS O
, , O
of IN O
the DT B
station NN I
's POS B
t/test.data view on Meta::CPAN
patient NN I
not RB O
only RB O
the DT B
very RB I
best JJS I
therapy NN I
which WDT B
we PRP B
have VBP O
established VBN O
t/test.data view on Meta::CPAN
, , O
personal JJ B
finance NN I
, , O
the DT B
best JJS I
colleges NNS I
, , O
and CC O
investments NNS B
. . O
Algorithm-Closest-NetworkAddress
view release on metacpan or search on metacpan
lib/Algorithm/Closest/NetworkAddress.pm view on Meta::CPAN
Creates an object containing the list of addresses to compare against
=head2 $self->compare($network_address)
Will find the best match in the network_address_list for the network_address specified.
Returns the network address that best matches.
=cut
sub compare {
my ($self, $target) = @_;
carp "Must specify a target" unless defined $target;
my $best_na;
my $best_level = 0;
foreach my $na (@{$self->network_address_list}) {
my $r = $self->measure($na, $target);
if ($r > $best_level) {
$best_level = $r;
$best_na = $na;
}
}
return $best_na || 0;
}
=head1 AUTHOR
Ton Voon C<ton.voon@altinity.com>
Algorithm-Cluster-Thresh
view release on metacpan or search on metacpan
END OF TERMS AND CONDITIONS
Appendix: How to Apply These Terms to Your New Programs
If you develop a new program, and you want it to be of the greatest
possible use to humanity, the best way to achieve this is to make it
free software which everyone can redistribute and change under these
terms.
To do so, attach the following notices to the program. It is safest to
attach them to the start of each source file to most effectively convey
Algorithm-Cluster
view release on metacpan or search on metacpan
src/cluster.c view on Meta::CPAN
index[i] = ix;
}
/* Start the iteration */
for (iter = 0; iter < niter; iter++) {
int ixbest = 0;
int iybest = 0;
int iobject = iter % nelements;
iobject = index[iobject];
if (transpose == 0) {
double closest = metric(ndata, data, celldata[ixbest], mask,
dummymask, weights, iobject, iybest,
transpose);
double radius = maxradius * (1. - ((double)iter)/((double)niter));
double tau = inittau * (1. - ((double)iter)/((double)niter));
for (ix = 0; ix < nxgrid; ix++) {
for (iy = 0; iy < nygrid; iy++) {
double distance = metric(ndata, data, celldata[ix], mask,
dummymask, weights, iobject, iy,
transpose);
if (distance < closest) {
ixbest = ix;
iybest = iy;
closest = distance;
}
}
}
for (ix = 0; ix < nxgrid; ix++) {
for (iy = 0; iy < nygrid; iy++) {
if (sqrt((ix-ixbest)*(ix-ixbest)+(iy-iybest)*(iy-iybest)) <
radius) {
double sum = 0.;
for (i = 0; i < ndata; i++) {
if (mask[iobject][i] == 0) continue;
celldata[ix][iy][i] +=
src/cluster.c view on Meta::CPAN
double** celldatavector = malloc(ndata*sizeof(double*));
double radius = maxradius * (1. - ((double)iter)/((double)niter));
double tau = inittau * (1. - ((double)iter)/((double)niter));
for (i = 0; i < ndata; i++)
celldatavector[i] = &(celldata[ixbest][iybest][i]);
closest = metric(ndata, data, celldatavector, mask, dummymask,
weights, iobject, 0, transpose);
for (ix = 0; ix < nxgrid; ix++) {
for (iy = 0; iy < nygrid; iy++) {
double distance;
for (i = 0; i < ndata; i++)
celldatavector[i] = &(celldata[ixbest][iybest][i]);
distance = metric(ndata, data, celldatavector, mask,
dummymask, weights, iobject, 0,
transpose);
if (distance < closest) {
ixbest = ix;
iybest = iy;
closest = distance;
}
}
}
free(celldatavector);
for (ix = 0; ix < nxgrid; ix++) {
for (iy = 0; iy < nygrid; iy++) {
if (sqrt((ix-ixbest)*(ix-ixbest)+(iy-iybest)*(iy-iybest)) <
radius) {
double sum = 0.;
for (i = 0; i < ndata; i++) {
if (mask[i][iobject] == 0) continue;
celldata[ix][iy][i] +=
src/cluster.c view on Meta::CPAN
for (i = 0; i < nygrid; i++) {
dummymask[i] = malloc(ncolumns*sizeof(int));
for (j = 0; j < ncolumns; j++) dummymask[i][j] = 1;
}
for (i = 0; i < nrows; i++) {
int ixbest = 0;
int iybest = 0;
double closest = metric(ndata, data, celldata[ixbest], mask,
dummymask, weights, i, iybest, transpose);
int ix, iy;
for (ix = 0; ix < nxgrid; ix++) {
for (iy = 0; iy < nygrid; iy++) {
double distance = metric(ndata, data, celldata[ix], mask,
dummymask, weights, i, iy,
transpose);
if (distance < closest) {
ixbest = ix;
iybest = iy;
closest = distance;
}
}
}
clusterid[i][0] = ixbest;
clusterid[i][1] = iybest;
}
for (i = 0; i < nygrid; i++) free(dummymask[i]);
free(dummymask);
}
else {
double** celldatavector = malloc(ndata*sizeof(double*));
int** dummymask = malloc(nrows*sizeof(int*));
int ixbest = 0;
int iybest = 0;
for (i = 0; i < nrows; i++) {
dummymask[i] = malloc(sizeof(int));
dummymask[i][0] = 1;
}
for (i = 0; i < ncolumns; i++) {
double closest;
int ix, iy;
for (j = 0; j < ndata; j++)
celldatavector[j] = &(celldata[ixbest][iybest][j]);
closest = metric(ndata, data, celldatavector, mask, dummymask,
weights, i, 0, transpose);
for (ix = 0; ix < nxgrid; ix++) {
for (iy = 0; iy < nygrid; iy++) {
double distance;
for (j = 0; j < ndata; j++)
celldatavector[j] = &(celldata[ix][iy][j]);
distance = metric(ndata, data, celldatavector, mask,
dummymask, weights, i, 0, transpose);
if (distance < closest) {
ixbest = ix;
iybest = iy;
closest = distance;
}
}
}
clusterid[i][0] = ixbest;
clusterid[i][1] = iybest;
}
free(celldatavector);
for (i = 0; i < nrows; i++) free(dummymask[i]);
free(dummymask);
}
Algorithm-ConsistentHash-CHash
view release on metacpan or search on metacpan
END OF TERMS AND CONDITIONS
Appendix: How to Apply These Terms to Your New Programs
If you develop a new program, and you want it to be of the greatest
possible use to humanity, the best way to achieve this is to make it
free software which everyone can redistribute and change under these
terms.
To do so, attach the following notices to the program. It is safest to
attach them to the start of each source file to most effectively convey
Algorithm-ConsistentHash-JumpHash
view release on metacpan or search on metacpan
JumpHash.xs view on Meta::CPAN
* regardless of keys size.
*
* It is 64 bit only.
*/
/* Find best way to ROTL32/ROTL64 */
#ifndef ROTL64
#if defined(_MSC_VER)
#include <stdlib.h> /* Microsoft put _rotl declaration in here */
#define ROTL64(x,r) _rotl64(x,r)
#else
Algorithm-ContextVector
view release on metacpan or search on metacpan
lib/Algorithm/ContextVector.pm view on Meta::CPAN
return $features;
}
=head2 $self->train
Keeps the best features (top N) and norms the vectors.
=cut
sub train {
my $self = shift;
Algorithm-CouponCode
view release on metacpan or search on metacpan
END OF TERMS AND CONDITIONS
Appendix: How to Apply These Terms to Your New Programs
If you develop a new program, and you want it to be of the greatest
possible use to humanity, the best way to achieve this is to make it
free software which everyone can redistribute and change under these
terms.
To do so, attach the following notices to the program. It is safest to
attach them to the start of each source file to most effectively convey
Algorithm-Cron
view release on metacpan or search on metacpan
END OF TERMS AND CONDITIONS
Appendix: How to Apply These Terms to Your New Programs
If you develop a new program, and you want it to be of the greatest
possible use to humanity, the best way to achieve this is to make it
free software which everyone can redistribute and change under these
terms.
To do so, attach the following notices to the program. It is safest to
attach them to the start of each source file to most effectively convey
Algorithm-CurveFit-Simple
view release on metacpan or search on metacpan
lib/Algorithm/CurveFit/Simple.pm view on Meta::CPAN
our @ISA = qw(Exporter);
our @EXPORT_OK = qw(fit %STATS_H);
}
# fit() - only public function for this distribution
# Given at least parameter "xy", generate a best-fit curve within a time limit.
# Output: max deviation, avg deviation, implementation source string (perl or C, for now).
# Optional parameters and their defaults:
# terms => 3 # number of terms in formula, max is 10
# time_limit => 3 # number of seconds to try for better fit
# inv => 1 # invert sense of curve-fit, from x->y to y->x
lib/Algorithm/CurveFit/Simple.pm view on Meta::CPAN
=item * Support more programming languages for formula implementation: R, MATLAB, python
=item * Calculate the actual term sigfigs and set precision appropriately in the formula implementation instead of just "%.11f".
=item * Support trying a range of terms and returning whatever gives the best fit.
=item * Support piecewise output formulas.
=item * Work around L<Algorithm::CurveFit>'s occasional hang problem when using ten-term polynomials.
Algorithm-CurveFit
view release on metacpan or search on metacpan
lib/Algorithm/CurveFit.pm view on Meta::CPAN
name 'x' is default. (Hence 'xdata'.)
=item params
The parameters are the symbols in the formula whose value is varied by the
algorithm to find the best fit of the curve to the data. There may be
one or more parameters, but please keep in mind that the number of parameters
not only increases processing time, but also decreases the quality of the fit.
The value of this options should be an anonymous array. This array should
hold one anonymous array for each parameter. That array should hold (in order)
lib/Algorithm/CurveFit.pm view on Meta::CPAN
In order to prevent looping forever, you are strongly encouraged to make use of
the accuracy measure (see also: maximum_iterations).
The final set of parameters is B<not> returned from the subroutine but the
parameters are modified in-place. That means the original data structure will
hold the best estimate of the parameters.
=item xdata
This should be an array reference to an array holding the data for the
variable of the function. (Which defaults to 'x'.)
Algorithm-DecisionTree
view release on metacpan or search on metacpan
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
return \%answer;
}
###################################### Decision Tree Construction ####################################
## At the root node, we find the best feature that yields the greatest reduction in
## class entropy from the entropy based on just the class priors. The logic for
## finding this feature is different for symbolic features and for numeric features.
## That logic is built into the method shown later for best feature calculations.
sub construct_decision_tree_classifier {
print "\nConstructing the decision tree ...\n";
my $self = shift;
if ($self->{_debug3}) {
$self->determine_data_condition();
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
if ($existing_node_entropy < $self->{_entropy_threshold}) {
print "\nRD5 returning because existing node entropy is below threshold\n" if $self->{_debug3};
return;
}
my @copy_of_path_attributes = @{deep_copy_array(\@features_and_values_or_thresholds_on_branch)};
my ($best_feature, $best_feature_entropy, $best_feature_val_entropies, $decision_val) =
$self->best_feature_calculator(\@copy_of_path_attributes, $existing_node_entropy);
$node->set_feature($best_feature);
$node->display_node() if $self->{_debug3};
if (defined($self->{_max_depth_desired}) &&
(@features_and_values_or_thresholds_on_branch >= $self->{_max_depth_desired})) {
print "\nRD6 REACHED LEAF NODE AT MAXIMUM DEPTH ALLOWED\n" if $self->{_debug3};
return;
}
return if ! defined $best_feature;
if ($self->{_debug3}) {
print "\nRD7 Existing entropy at node: $existing_node_entropy\n";
print "\nRD8 Calculated best feature is $best_feature and its value $decision_val\n";
print "\nRD9 Best feature entropy: $best_feature_entropy\n";
print "\nRD10 Calculated entropies for different values of best feature: @$best_feature_val_entropies\n";
}
my $entropy_gain = $existing_node_entropy - $best_feature_entropy;
print "\nRD11 Expected entropy gain at this node: $entropy_gain\n" if $self->{_debug3};
if ($entropy_gain > $self->{_entropy_threshold}) {
if (exists $self->{_numeric_features_valuerange_hash}->{$best_feature} &&
$self->{_feature_values_how_many_uniques_hash}->{$best_feature} >
$self->{_symbolic_to_numeric_cardinality_threshold}) {
my $best_threshold = $decision_val; # as returned by best feature calculator
my ($best_entropy_for_less, $best_entropy_for_greater) = @$best_feature_val_entropies;
my @extended_branch_features_and_values_or_thresholds_for_lessthan_child =
@{deep_copy_array(\@features_and_values_or_thresholds_on_branch)};
my @extended_branch_features_and_values_or_thresholds_for_greaterthan_child =
@{deep_copy_array(\@features_and_values_or_thresholds_on_branch)};
my $feature_threshold_combo_for_less_than = "$best_feature" . '<' . "$best_threshold";
my $feature_threshold_combo_for_greater_than = "$best_feature" . '>' . "$best_threshold";
push @extended_branch_features_and_values_or_thresholds_for_lessthan_child,
$feature_threshold_combo_for_less_than;
push @extended_branch_features_and_values_or_thresholds_for_greaterthan_child,
$feature_threshold_combo_for_greater_than;
if ($self->{_debug3}) {
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
\@extended_branch_features_and_values_or_thresholds_for_lessthan_child)} @{$self->{_class_names}};
my @class_probabilities_for_greaterthan_child_node =
map {$self->probability_of_a_class_given_sequence_of_features_and_values_or_thresholds($_,
\@extended_branch_features_and_values_or_thresholds_for_greaterthan_child)} @{$self->{_class_names}};
if ($self->{_debug3}) {
print "\nRD14 class entropy for going down lessthan child: $best_entropy_for_less\n";
print "\nRD15 class_entropy_for_going_down_greaterthan_child: $best_entropy_for_greater\n";
}
if ($best_entropy_for_less < $existing_node_entropy - $self->{_entropy_threshold}) {
my $left_child_node = DTNode->new(undef, $best_entropy_for_less,
\@class_probabilities_for_lessthan_child_node,
\@extended_branch_features_and_values_or_thresholds_for_lessthan_child, $self);
$node->add_child_link($left_child_node);
$self->recursive_descent($left_child_node);
}
if ($best_entropy_for_greater < $existing_node_entropy - $self->{_entropy_threshold}) {
my $right_child_node = DTNode->new(undef, $best_entropy_for_greater,
\@class_probabilities_for_greaterthan_child_node,
\@extended_branch_features_and_values_or_thresholds_for_greaterthan_child, $self);
$node->add_child_link($right_child_node);
$self->recursive_descent($right_child_node);
}
} else {
print "\nRD16 RECURSIVE DESCENT: In section for symbolic features for creating children"
if $self->{_debug3};
my @values_for_feature = @{$self->{_features_and_unique_values_hash}->{$best_feature}};
print "\nRD17 Values for feature $best_feature are @values_for_feature\n" if $self->{_debug3};
my @feature_value_combos = sort map {"$best_feature" . '=' . $_} @values_for_feature;
my @class_entropies_for_children = ();
foreach my $feature_and_value_index (0..@feature_value_combos-1) {
print "\nRD18 Creating a child node for: $feature_value_combos[$feature_and_value_index]\n"
if $self->{_debug3};
my @extended_branch_features_and_values_or_thresholds;
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
return;
}
}
## This is the heart of the decision tree constructor. Its main job is to figure
## out the best feature to use for partitioning the training data samples that
## correspond to the current node. The search for the best feature is carried out
## differently for symbolic features and for numeric features. For a symbolic
## feature, the method estimates the entropy for each value of the feature and then
## averages out these entropies as a measure of the discriminatory power of that
## features. For a numeric feature, on the other hand, it estimates the entropy
## reduction that can be achieved if were to partition the set of training samples
## for each possible threshold. For a numeric feature, all possible sampling points
## relevant to the node in question are considered as candidates for thresholds.
sub best_feature_calculator {
my $self = shift;
my $features_and_values_or_thresholds_on_branch = shift;
my $existing_node_entropy = shift;
my @features_and_values_or_thresholds_on_branch = @$features_and_values_or_thresholds_on_branch;
my $pattern1 = '(.+)=(.+)';
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
@true_numeric_types_feature_names = grep {$_ if !$seen{$_}++} @true_numeric_types_feature_names;
%seen = ();
@symbolic_types_feature_names = grep {$_ if !$seen{$_}++} @symbolic_types_feature_names;
my @bounded_intervals_numeric_types =
@{$self->find_bounded_intervals_for_numeric_features(\@true_numeric_types)};
# Calculate the upper and the lower bounds to be used when searching for the best
# threshold for each of the numeric features that are in play at the current node:
my (%upperbound, %lowerbound);
foreach my $feature (@true_numeric_types_feature_names) {
$upperbound{$feature} = undef;
$lowerbound{$feature} = undef;
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
} elsif (defined($lowerbound{$feature_name})) {
foreach my $x (@values) {
push @newvalues, $x if $x > $lowerbound{$feature_name};
}
} else {
die "Error is bound specifications in best feature calculator";
}
} else {
@newvalues = @{deep_copy_array(\@values)};
}
next if @newvalues == 0;
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
$self->probability_of_a_sequence_of_features_and_values_or_thresholds(\@for_right_child);
push @partitioning_entropies, $partitioning_entropy;
$partitioning_point_child_entropies_hash{$feature_name}{$value} = [$entropy1, $entropy2];
}
my ($min_entropy, $best_partition_point_index) = minimum(\@partitioning_entropies);
if ($min_entropy < $existing_node_entropy) {
$partitioning_point_threshold{$feature_name} = $newvalues[$best_partition_point_index];
$entropy_values_for_different_features{$feature_name} = $min_entropy;
}
} else {
print "\nBFC2: Entering section reserved for symbolic features\n" if $self->{_debug3};
print "\nBFC3 Feature name: $feature_name\n" if $self->{_debug3};
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
if ($entropy < $existing_node_entropy) {
$entropy_values_for_different_features{$feature_name} = $entropy;
}
}
}
my $min_entropy_for_best_feature;
my $best_feature_name;
foreach my $feature_nom (keys %entropy_values_for_different_features) {
if (!defined($best_feature_name)) {
$best_feature_name = $feature_nom;
$min_entropy_for_best_feature = $entropy_values_for_different_features{$feature_nom};
} else {
if ($entropy_values_for_different_features{$feature_nom} < $min_entropy_for_best_feature) {
$best_feature_name = $feature_nom;
$min_entropy_for_best_feature = $entropy_values_for_different_features{$feature_nom};
}
}
}
my $threshold_for_best_feature;
if (exists $partitioning_point_threshold{$best_feature_name}) {
$threshold_for_best_feature = $partitioning_point_threshold{$best_feature_name};
} else {
$threshold_for_best_feature = undef;
}
my $best_feature_entropy = $min_entropy_for_best_feature;
my @val_based_entropies_to_be_returned;
my $decision_val_to_be_returned;
if (exists $self->{_numeric_features_valuerange_hash}->{$best_feature_name} &&
$self->{_feature_values_how_many_uniques_hash}->{$best_feature_name} >
$self->{_symbolic_to_numeric_cardinality_threshold}) {
@val_based_entropies_to_be_returned =
@{$partitioning_point_child_entropies_hash{$best_feature_name}{$threshold_for_best_feature}};
} else {
@val_based_entropies_to_be_returned = ();
}
if (exists $partitioning_point_threshold{$best_feature_name}) {
$decision_val_to_be_returned = $partitioning_point_threshold{$best_feature_name};
} else {
$decision_val_to_be_returned = undef;
}
print "\nBFC6 Val based entropies to be returned for feature $best_feature_name are " .
"@val_based_entropies_to_be_returned\n" if $self->{_debug3};
return ($best_feature_name, $best_feature_entropy, \@val_based_entropies_to_be_returned,
$decision_val_to_be_returned);
}
######################################### Entropy Calculators #####################################
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
my %seen2 = ();
@symbolic_types_feature_names = grep {$_ if !$seen2{$_}++} @symbolic_types_feature_names;
my $bounded_intervals_numeric_types = $self->find_bounded_intervals_for_numeric_features(\@true_numeric_types);
print_array_with_msg("POS: Answer returned by find_bounded: ",
$bounded_intervals_numeric_types) if $self->{_debug2};
# Calculate the upper and the lower bounds to be used when searching for the best
# threshold for each of the numeric features that are in play at the current node:
my (%upperbound, %lowerbound);
foreach my $feature_name (@true_numeric_types_feature_names) {
$upperbound{$feature_name} = undef;
$lowerbound{$feature_name} = undef;
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
my %seen2 = ();
@symbolic_types_feature_names = grep {$_ if !$seen2{$_}++} @symbolic_types_feature_names;
my $bounded_intervals_numeric_types = $self->find_bounded_intervals_for_numeric_features(\@true_numeric_types);
print_array_with_msg("POSC: Answer returned by find_bounded: ",
$bounded_intervals_numeric_types) if $self->{_debug2};
# Calculate the upper and the lower bounds to be used when searching for the best
# threshold for each of the numeric features that are in play at the current node:
my (%upperbound, %lowerbound);
foreach my $feature_name (@true_numeric_types_feature_names) {
$upperbound{$feature_name} = undef;
$lowerbound{$feature_name} = undef;
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
## training data by running a 10-fold cross-validation test on it. This test divides
## all of the training data into ten parts, with nine parts used for training a
## decision tree and one part used for testing its ability to classify correctly.
## This selection of nine parts for training and one part for testing is carried out
## in all of the ten different possible ways. This testing functionality can also
## be used to find the best values to use for the constructor parameters
## entropy_threshold, max_depth_desired, and
## symbolic_to_numeric_cardinality_threshold.
## Only the CSV training files can be evaluated in this manner (because only CSV
## training are allowed to have numeric features --- which is the more interesting
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
cross-validation test on the data. This test divides all of the training data into
ten parts, with nine parts used for training a decision tree and one part used for
testing its ability to classify correctly. This selection of nine parts for training
and one part for testing is carried out in all of the ten different ways that are
possible. This testing functionality in Version 2.1 can also be used to find the
best values to use for the constructor parameters C<entropy_threshold>,
C<max_depth_desired>, and C<symbolic_to_numeric_cardinality_threshold>.
B<Version 2.0 is a major rewrite of this module.> Now you can use both numeric and
symbolic features for constructing a decision tree. A feature is numeric if it can
take any floating-point value over an interval.
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
together to the data as partitioned by the feature test. You then drop from the root
node a set of child nodes, one for each partition of the training data created by the
feature test at the root node. When your features are purely symbolic, you'll have
one child node for each value of the feature chosen for the feature test at the root.
When the test at the root involves a numeric feature, you find the decision threshold
for the feature that best bipartitions the data and you drop from the root node two
child nodes, one for each partition. Now at each child node you pose the same
question that you posed when you found the best feature to use at the root: Which
feature at the child node in question would maximally disambiguate the class labels
associated with the training data corresponding to that child node?
As the reader would expect, the two key steps in any approach to decision-tree based
classification are the construction of the decision tree itself from a file
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
test set of data is a good way to develop greater proficiency with decision trees.
=head1 WHAT PRACTICAL PROBLEM IS SOLVED BY THIS MODULE
If you are new to the concept of a decision tree, their practical utility is best
understood with an example that only involves symbolic features. However, as
mentioned earlier, versions of the module higher than 2.0 allow you to use both
symbolic and numeric features.
Consider the following scenario: Let's say you are running a small investment company
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
my $root_node = $dt->construct_decision_tree_classifier();
Now you and your company (with practically no employees) are ready to service the
customers again. Suppose your computer needs to make a buy/sell decision about an
investment prospect that is best described by:
price_to_earnings_ratio = low
price_to_sales_ratio = very_low
return_on_equity = none
market_share = medium
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
The last statement above prints out a Confusion Matrix and the value of Training Data
Quality Index on a scale of 0 to 100, with 100 designating perfect training data.
The Confusion Matrix shows how the different classes were mislabeled in the 10-fold
cross-validation test.
This testing functionality can also be used to find the best values to use for the
constructor parameters C<entropy_threshold>, C<max_depth_desired>, and
C<symbolic_to_numeric_cardinality_threshold>.
The following two scripts in the C<Examples> directory illustrate the use of the
C<EvalTrainingData> class for testing the quality of your data:
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
explicitly giving a value to the 'C<number_of_histogram_bins>' parameter.
=back
You can choose the best values to use for the last three constructor parameters by
running a 10-fold cross-validation test on your training data through the class
C<EvalTrainingData> that comes with Versions 2.1 and higher of this module. See the
section "TESTING THE QUALITY OF YOUR TRAINING DATA" of this document page.
=over
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
why the decision tree classifier may associate significant probabilities with
multiple class labels is that you used inadequate number of training samples to
induce the decision tree. The good thing is that the classifier does not lie to you
(unlike, say, a hard classification rule that would return a single class label
corresponding to the partitioning of the underlying feature space). The decision
tree classifier give you the best classification that can be made given the training
data you fed into it.
=head1 USING BAGGING
lib/Algorithm/DecisionTree.pm view on Meta::CPAN
calculate the regression coefficients. When C<jacobian_choice> is set to 1, you get
a weak version of gradient descent in which the Jacobian is set to the "design
matrix" itself. Choosing 2 for C<jacobian_choice> results in a more reasonable
approximation to the Jacobian. That, however, is at a cost of much longer
computation time. B<NOTE:> For most cases, using 0 for C<jacobian_choice> is the
best choice. See my tutorial "I<Linear Regression and Regression Trees>" for why
that is the case.
=back
=head2 B<Methods defined for C<RegressionTree> class>
Algorithm-Dependency
view release on metacpan or search on metacpan
END OF TERMS AND CONDITIONS
Appendix: How to Apply These Terms to Your New Programs
If you develop a new program, and you want it to be of the greatest
possible use to humanity, the best way to achieve this is to make it
free software which everyone can redistribute and change under these
terms.
To do so, attach the following notices to the program. It is safest to
attach them to the start of each source file to most effectively convey
Algorithm-DependencySolver
view release on metacpan or search on metacpan
END OF TERMS AND CONDITIONS
Appendix: How to Apply These Terms to Your New Programs
If you develop a new program, and you want it to be of the greatest
possible use to humanity, the best way to achieve this is to make it
free software which everyone can redistribute and change under these
terms.
To do so, attach the following notices to the program. It is safest to
attach them to the start of each source file to most effectively convey
Algorithm-Diff-Any
view release on metacpan or search on metacpan
lib/Algorithm/Diff/Any.pm view on Meta::CPAN
}
}
=head1 DESCRIPTION
This is a simple module to select the best available implementation of the
standard C<diff> algorithm, which works by effectively trying to solve the
Longest Common Subsequence (LCS) problem. This algorithm is described in:
I<A Fast Algorithm for Computing Longest Common Subsequences>, CACM, vol.20,
no.5, pp.350-353, May 1977.
Algorithm-Diff-Callback
view release on metacpan or search on metacpan
END OF TERMS AND CONDITIONS
Appendix: How to Apply These Terms to Your New Programs
If you develop a new program, and you want it to be of the greatest
possible use to humanity, the best way to achieve this is to make it
free software which everyone can redistribute and change under these
terms.
To do so, attach the following notices to the program. It is safest to
attach them to the start of each source file to most effectively convey
Algorithm-Diff-JSON
view release on metacpan or search on metacpan
lib/Algorithm/Diff/JSON.pm view on Meta::CPAN
=back
=head1 FEEDBACK
I welcome feedback about my code, including constructive criticism, bug
reports, documentation improvements, and feature requests. The best bug reports
include files that I can add to the test suite, which fail with the current
code in my git repo and will pass once I've fixed the bug
Feature requests are far more likely to get implemented if you submit a patch
yourself.
Algorithm-Diff-XS
view release on metacpan or search on metacpan
#ifndef IVSIZE
# ifdef LONGSIZE
# define IVSIZE LONGSIZE
# else
# define IVSIZE 4 /* A bold guess, but the best we can make. */
# endif
#endif
#ifndef UVTYPE
# define UVTYPE unsigned IVTYPE
#endif
#ifndef PERL_MAGIC_ext
# define PERL_MAGIC_ext '~'
#endif
/* That's the best we can do... */
#ifndef SvPV_force_nomg
# define SvPV_force_nomg SvPV_force
#endif
#ifndef SvPV_nomg
Algorithm-DistanceMatrix
view release on metacpan or search on metacpan
END OF TERMS AND CONDITIONS
Appendix: How to Apply These Terms to Your New Programs
If you develop a new program, and you want it to be of the greatest
possible use to humanity, the best way to achieve this is to make it
free software which everyone can redistribute and change under these
terms.
To do so, attach the following notices to the program. It is safest to
attach them to the start of each source file to most effectively convey
Algorithm-Easing
view release on metacpan or search on metacpan
END OF TERMS AND CONDITIONS
Appendix: How to Apply These Terms to Your New Programs
If you develop a new program, and you want it to be of the greatest
possible use to humanity, the best way to achieve this is to make it
free software which everyone can redistribute and change under these
terms.
To do so, attach the following notices to the program. It is safest to
attach them to the start of each source file to most effectively convey
Algorithm-EquivalenceSets
view release on metacpan or search on metacpan
END OF TERMS AND CONDITIONS
Appendix: How to Apply These Terms to Your New Programs
If you develop a new program, and you want it to be of the greatest
possible use to humanity, the best way to achieve this is to make it
free software which everyone can redistribute and change under these
terms.
To do so, attach the following notices to the program. It is safest to
attach them to the start of each source file to most effectively convey
( run in 1.324 second using v1.01-cache-2.11-cpan-39bf76dae61 )