Algorithm-LinearManifoldDataClusterer
view release on metacpan or search on metacpan
lib/Algorithm/LinearManifoldDataClusterer.pm view on Meta::CPAN
if ($theta eq "0") {
push @eigenvec, $mag;
} elsif ($theta eq "pi") {
push @eigenvec, -1.0 * $mag;
} else {
die "Eigendecomposition produced a complex eigenvector -- " .
"which should not happen for a covariance matrix!";
}
}
print "Eigenvector $i: @eigenvec\n" if $self->{_debug};
push @all_my_eigenvecs, \@eigenvec;
}
my @largest_eigen_vec = $eigenvectors->[$largest_eigen_index]->as_list;
print "\nLargest eigenvector: @largest_eigen_vec\n" if $self->{_debug};
my @sorted_eigenvec_indexes = sort {$eigenvalues->[$b] <=> $eigenvalues->[$a]} 0..@all_my_eigenvecs-1;
my @sorted_eigenvecs;
my @sorted_eigenvals;
foreach my $i (0..@sorted_eigenvec_indexes-1) {
$sorted_eigenvecs[$i] = $all_my_eigenvecs[$sorted_eigenvec_indexes[$i]];
$sorted_eigenvals[$i] = $eigenvalues->[$sorted_eigenvec_indexes[$i]];
}
if ($self->{_debug}) {
print "\nHere come sorted eigenvectors --- from the largest to the smallest:\n";
foreach my $i (0..@sorted_eigenvecs-1) {
print "eigenvec: @{$sorted_eigenvecs[$i]} eigenvalue: $sorted_eigenvals[$i]\n";
}
}
return (\@sorted_eigenvecs, \@sorted_eigenvals);
}
sub auto_retry_clusterer {
my $self = shift;
$self->{_auto_retry_flag} = 1;
my $clusters;
$@ = 1;
my $retry_attempts = 1;
while ($@) {
eval {
$clusters = $self->linear_manifold_clusterer();
};
if ($@) {
if ($self->{_terminal_output}) {
print "Clustering failed. Trying again. --- $@";
print "\n\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n";
print "VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV\n\n";
}
$retry_attempts++;
} else {
print "\n\nNumber of retry attempts: $retry_attempts\n\n" if $self->{_terminal_output};
return $clusters;
}
}
}
sub linear_manifold_clusterer {
my $self = shift;
my $KM = $self->{_KM};
my @initial_cluster_center_tags;
my $visualization_msg;
my @initial_cluster_center_indexes = $self->initialize_cluster_centers($KM, $self->{_N});
print "Randomly selected indexes for cluster center tags: @initial_cluster_center_indexes\n"
if $self->{_debug};
@initial_cluster_center_tags = map {$self->{_data_tags}->[$_]} @initial_cluster_center_indexes;
my @initial_cluster_center_coords = map {$self->{_data_hash}->{$_}} @initial_cluster_center_tags;
if ($self->{_debug}) {
foreach my $centroid (@initial_cluster_center_coords) {
print "Initial cluster center coords: @{$centroid}\n";
}
}
my $initial_clusters = $self->assign_data_to_clusters_initial(\@initial_cluster_center_coords);
if ($self->{_data_dimensions} == 3) {
$visualization_msg = "initial_clusters";
$self->visualize_clusters_on_sphere($visualization_msg, $initial_clusters)
if $self->{_visualize_each_iteration};
$self->visualize_clusters_on_sphere($visualization_msg, $initial_clusters, "png")
if $self->{_make_png_for_each_iteration};
}
foreach my $cluster (@$initial_clusters) {
my ($mean, $covariance) = $self->estimate_mean_and_covariance($cluster);
display_mean_and_covariance($mean, $covariance) if $self->{_debug};
}
my @clusters = @$initial_clusters;
display_clusters(\@clusters) if $self->{_debug};
my $iteration_index = 0;
my $unimodal_correction_flag;
my $previous_min_value_for_unimodality_quotient;
while ($iteration_index < $self->{_max_iterations}) {
print "\n\n========================== STARTING ITERATION $iteration_index =====================\n\n"
if $self->{_terminal_output};
my $total_reconstruction_error_this_iteration = 0;
my @subspace_construction_errors_this_iteration;
my @trailing_eigenvec_matrices_for_all_subspaces;
my @reference_vecs_for_all_subspaces;
foreach my $cluster (@clusters) {
next if @$cluster == 0;
my ($mean, $covariance) = $self->estimate_mean_and_covariance($cluster);
display_mean_and_covariance($mean, $covariance) if $self->{_debug};
print "--------------end of displaying mean and covariance\n\n" if $self->{_debug};
my ($eigenvecs, $eigenvals) = $self->eigen_analysis_of_covariance($covariance);
my @trailing_eigenvecs = @{$eigenvecs}[$self->{_P} .. $self->{_data_dimensions}-1];
my @trailing_eigenvals = @{$eigenvals}[$self->{_P} .. $self->{_data_dimensions}-1];
my $subspace_construction_error = reduce {abs($a) + abs($b)} @trailing_eigenvals;
push @subspace_construction_errors_this_iteration, $subspace_construction_error;
my $trailing_eigenvec_matrix = Math::GSL::Matrix->new($self->{_data_dimensions},
scalar(@trailing_eigenvecs));
foreach my $j (0..@trailing_eigenvecs-1) {
print "trailing eigenvec column: @{$trailing_eigenvecs[$j]}\n" if $self->{_debug};
$trailing_eigenvec_matrix->set_col($j, $trailing_eigenvecs[$j]);
}
push @trailing_eigenvec_matrices_for_all_subspaces,$trailing_eigenvec_matrix;
push @reference_vecs_for_all_subspaces, $mean;
}
$self->set_termination_reconstruction_error_threshold(\@reference_vecs_for_all_subspaces);
my %best_subspace_based_partition_of_data;
foreach my $i (0..$self->{_KM}-1) {
$best_subspace_based_partition_of_data{$i} = [];
}
foreach my $data_tag (@{$self->{_data_tags}}) {
my $data_vec = Math::GSL::Matrix->new($self->{_data_dimensions},1);
$data_vec->set_col(0, $self->{_data_hash}->{$data_tag});
my @errors = map {$self->reconstruction_error($data_vec,
lib/Algorithm/LinearManifoldDataClusterer.pm view on Meta::CPAN
my @sorted_eigenvals;
foreach my $i (0..@sorted_eigenvec_indexes-1) {
$sorted_eigenvecs[$i] = $all_my_eigenvecs[$sorted_eigenvec_indexes[$i]];
$sorted_eigenvals[$i] = $eigenvalues->[$sorted_eigenvec_indexes[$i]];
}
if ($self->{_debug2}) {
print "\nHere come sorted eigenvectors for A --- from the largest to the smallest:\n";
foreach my $i (0..@sorted_eigenvecs-1) {
print "eigenvec: @{$sorted_eigenvecs[$i]} eigenvalue: $sorted_eigenvals[$i]\n";
}
}
my $best_partitioning_eigenvec = $sorted_eigenvecs[@sorted_eigenvec_indexes-2];
print "\nBest graph partitioning eigenvector: @$best_partitioning_eigenvec\n" if $self->{_terminal_output};
my $how_many_positive = reduce {$a + $b} map {$_ > 0 ? 1 : 0 } @$best_partitioning_eigenvec;
my $how_many_negative = scalar(@$best_partitioning_eigenvec) - $how_many_positive;
print "Have $how_many_positive positive and $how_many_negative negative elements in the partitioning vec\n"
if $self->{_terminal_output};
if ($how_many_clusters_looking_for <= 3) {
my @merged_cluster;
my $final_cluster;
my @newclusters;
if ($how_many_positive == 1) {
foreach my $i (0..@$clusters-1) {
if ($best_partitioning_eigenvec->[$i] > 0) {
$final_cluster = $clusters->[$i];
} else {
push @newclusters, $clusters->[$i];
}
}
return ([$final_cluster], \@newclusters);
} elsif ($how_many_negative == 1) {
foreach my $i (0..@$clusters-1) {
if ($best_partitioning_eigenvec->[$i] < 0) {
$final_cluster = $clusters->[$i];
} else {
push @newclusters, $clusters->[$i];
}
}
return ([$final_cluster], \@newclusters);
} elsif ($how_many_positive <= $self->{_cluster_search_multiplier}) {
foreach my $i (0..@$clusters-1) {
if ($best_partitioning_eigenvec->[$i] > 0) {
push @merged_cluster, @{$clusters->[$i]};
} else {
push @newclusters, $clusters->[$i];
}
}
return ([\@merged_cluster], \@newclusters);
} elsif ($how_many_negative <= $self->{_cluster_search_multiplier}) {
foreach my $i (0..@$clusters-1) {
if ($best_partitioning_eigenvec->[$i] < 0) {
push @merged_cluster, @{$clusters->[$i]};
} else {
push @newclusters, $clusters->[$i];
}
}
return ([\@merged_cluster], \@newclusters);
} else {
die "\n\nBailing out!\n\n" .
"No consensus support for dominant clusters in the graph partitioning step\n" .
"of the algorithm. This can be caused by bad random selection of initial\n" .
"cluster centers. Please run this program again.\n";
}
} else {
my @positive_clusters;
my @negative_clusters;
foreach my $i (0..@$clusters-1) {
if ($best_partitioning_eigenvec->[$i] > 0) {
push @positive_clusters, $clusters->[$i];
} else {
push @negative_clusters, $clusters->[$i];
}
}
return (\@positive_clusters, \@negative_clusters);
}
}
sub pairwise_cluster_similarity {
my $self = shift;
my $cluster1 = shift;
my $trailing_eigenvec_matrix_cluster1 = shift;
my $reference_vec_cluster1 = shift;
my $cluster2 = shift;
my $trailing_eigenvec_matrix_cluster2 = shift;
my $reference_vec_cluster2 = shift;
my $total_reconstruction_error_in_this_iteration = 0;
my @errors_for_1_on_2 = map {my $data_vec = Math::GSL::Matrix->new($self->{_data_dimensions},1);
$data_vec->set_col(0, $self->{_data_hash}->{$_});
$self->reconstruction_error($data_vec,
$trailing_eigenvec_matrix_cluster2,
$reference_vec_cluster2)}
@$cluster1;
my @errors_for_2_on_1 = map {my $data_vec = Math::GSL::Matrix->new($self->{_data_dimensions},1);
$data_vec->set_col(0, $self->{_data_hash}->{$_});
$self->reconstruction_error($data_vec,
$trailing_eigenvec_matrix_cluster1,
$reference_vec_cluster1)}
@$cluster2;
my $type_1_error = reduce {abs($a) + abs($b)} @errors_for_1_on_2;
my $type_2_error = reduce {abs($a) + abs($b)} @errors_for_2_on_1;
my $total_reconstruction_error = $type_1_error + $type_2_error;
my $diff_between_the_means = $reference_vec_cluster1 - $reference_vec_cluster2;
my $dist_squared = transpose($diff_between_the_means) * $diff_between_the_means;
my @dist_squared_as_list = $dist_squared->as_list();
my $dist_between_means_based_error = shift @dist_squared_as_list;
return ($total_reconstruction_error, $dist_between_means_based_error);
}
# delta ball
sub cluster_unimodality_quotient {
my $self = shift;
my $cluster = shift;
my $mean = shift;
my $delta = 0.4 * $self->{_scale_factor}; # Radius of the delta ball along each dimension
my @mean = $mean->as_list;
my @data_tags_for_range_tests;
foreach my $dimen (0..$self->{_data_dimensions}-1) {
my @values = map {$_->[$dimen]} map {$self->{_data_hash}->{$_}} @$cluster;
my ($min, $max) = (List::Util::min(@values), List::Util::max(@values));
my $range = $max - $min;
my $mean_along_this_dimen = $mean[$dimen];
lib/Algorithm/LinearManifoldDataClusterer.pm view on Meta::CPAN
my %tag_hash_for_this_dimen = map {$_ => 1} @{$data_tags_for_range_tests[$dimen]};
if ($dimen == 0) {
%intersection_hash = %tag_hash_for_this_dimen;
} else {
%intersection_hash = map {$_ => 1} grep {$tag_hash_for_this_dimen{$_}}
keys %intersection_hash;
}
}
my @intersection_set = keys %intersection_hash;
my $cluster_unimodality_index = scalar(@intersection_set) / scalar(@$cluster);
return $cluster_unimodality_index;
}
sub find_best_ref_vector {
my $self = shift;
my $cluster = shift;
my $trailing_eigenvec_matrix = shift;
my $mean = shift; # a GSL marix ref
my @min_bounds;
my @max_bounds;
my @ranges;
foreach my $dimen (0..$self->{_data_dimensions}-1) {
my @values = map {$_->[$dimen]} map {$self->{_data_hash}->{$_}} @$cluster;
my ($min, $max) = (List::Util::min(@values), List::Util::max(@values));
push @min_bounds, $min;
push @max_bounds, $max;
push @ranges, $max - $min;
}
print "min bounds are: @min_bounds\n";
print "max bounds are: @max_bounds\n";
my $max_iterations = 100;
my @random_points;
my $iteration = 0;
while ($iteration++ < $max_iterations) {
my @coordinate_vec;
foreach my $dimen (0..$self->{_data_dimensions}-1) {
push @coordinate_vec, $min_bounds[$dimen] + rand($ranges[$dimen]);
}
push @random_points, \@coordinate_vec;
}
if ($self->{_debug}) {
print "\nrandom points\n";
map {print "@$_\n"} @random_points;
}
my @mean = $mean->as_list;
unshift @random_points, \@mean;
my @reconstruction_errors;
foreach my $candidate_ref_vec (@random_points) {
my $ref_vec = Math::GSL::Matrix->new($self->{_data_dimensions},1);
$ref_vec->set_col(0, $candidate_ref_vec);
my $reconstruction_error_for_a_ref_vec = 0;
foreach my $data_tag (@{$self->{_data_tags}}) {
my $data_vec = Math::GSL::Matrix->new($self->{_data_dimensions},1);
$data_vec->set_col(0, $self->{_data_hash}->{$data_tag});
my $error = $self->reconstruction_error($data_vec,$trailing_eigenvec_matrix,$ref_vec);
$reconstruction_error_for_a_ref_vec += $error;
}
push @reconstruction_errors, $reconstruction_error_for_a_ref_vec;
}
my $recon_error_for_original_mean = shift @reconstruction_errors;
my $smallest_error_randomly_selected_ref_vecs = List::Util::min(@reconstruction_errors);
my $minindex = List::Util::first { $_ == $smallest_error_randomly_selected_ref_vecs }
@reconstruction_errors;
my $refvec = $random_points[$minindex];
return $refvec;
}
## The reconstruction error relates to the size of the perpendicular from a data
## point X to the hyperplane that defines a given subspace on the manifold.
sub reconstruction_error {
my $self = shift;
my $data_vec = shift;
my $trailing_eigenvecs = shift;
my $ref_vec = shift;
my $error_squared = transpose($data_vec - $ref_vec) * $trailing_eigenvecs *
transpose($trailing_eigenvecs) * ($data_vec - $ref_vec);
my @error_squared_as_list = $error_squared->as_list();
my $error_squared_as_scalar = shift @error_squared_as_list;
return $error_squared_as_scalar;
}
# Returns a set of KM random integers. These serve as indices to reach into the data
# array. A data element whose index is one of the random numbers returned by this
# routine serves as an initial cluster center. Note the quality check it runs on the
# list of the random integers constructed. We first make sure that all the random
# integers returned are different. Subsequently, we carry out a quality assessment
# of the random integers constructed. This quality measure consists of the ratio of
# the values spanned by the random integers to the value of N, the total number of
# data points to be clustered. Currently, if this ratio is less than 0.3, we discard
# the K integers and try again.
sub initialize_cluster_centers {
my $self = shift;
my $K = shift; # This value is set to the parameter KM in the call to this subroutine
my $data_store_size = shift;
my @cluster_center_indices;
while (1) {
foreach my $i (0..$K-1) {
$cluster_center_indices[$i] = int rand( $data_store_size );
next if $i == 0;
foreach my $j (0..$i-1) {
while ( $cluster_center_indices[$j] == $cluster_center_indices[$i] ) {
my $old = $cluster_center_indices[$i];
$cluster_center_indices[$i] = int rand($data_store_size);
}
}
}
my ($min,$max) = minmax(\@cluster_center_indices );
my $quality = ($max - $min) / $data_store_size;
last if $quality > 0.3;
}
return @cluster_center_indices;
}
# The purpose of this routine is to form initial clusters by assigning the data
# samples to the initial clusters formed by the previous routine on the basis of the
# best proximity of the data samples to the different cluster centers.
sub assign_data_to_clusters_initial {
my $self = shift;
my @cluster_centers = @{ shift @_ };
my @clusters;
foreach my $ele (@{$self->{_data_tags}}) {
my $best_cluster;
lib/Algorithm/LinearManifoldDataClusterer.pm view on Meta::CPAN
falls on a straight line when, in reality, it falls on a strongly curving arc. This
is exactly what happens with PCA --- it gives you a linear manifold approximation to
your data that may actually reside on a curved surface.
That brings us to the purpose of this module, which is to cluster data that resides
on a nonlinear manifold. Since a nonlinear manifold is locally linear, we can think
of each data cluster on a nonlinear manifold as falling on a locally linear portion
of the manifold, meaning on a hyperplane. The logic of the module is based on
finding a set of hyperplanes that best describes the data, with each hyperplane
derived from a local data cluster. This is like constructing a piecewise linear
approximation to data that falls on a curve as opposed to constructing a single
straight line approximation to all of the data. So whereas the frequently used PCA
algorithm gives you a single hyperplane approximation to all your data, what this
module returns is a set of hyperplane approximations, with each hyperplane derived by
applying the PCA algorithm locally to a data cluster.
That brings us to the problem of how to actually discover the best set of hyperplane
approximations to the data. What is probably the most popular algorithm today for
that purpose is based on the following key idea: Given a set of subspaces to which a
data element can be assigned, you assign it to that subspace for which the
B<reconstruction error> is the least. But what do we mean by a B<subspace> and what
is B<reconstruction error>?
To understand the notions of B<subspace> and B<reconstruction-error>, let's revisit
the traditional approach of dimensionality reduction by the PCA algorithm. The PCA
algorithm consists of: (1) Subtracting from each data element the global mean of the
data; (2) Calculating the covariance matrix of the data; (3) Carrying out an
eigendecomposition of the covariance matrix and ordering the eigenvectors according
to decreasing values of the corresponding eigenvalues; (4) Forming a B<subspace> by
discarding the trailing eigenvectors whose corresponding eigenvalues are relatively
small; and, finally, (5) projecting all the data elements into the subspace so
formed. The error incurred in representing a data element by its projection into the
subspace is known as the B<reconstruction error>. This error is the projection of
the data element into the space spanned by the discarded trailing eigenvectors.
I<In linear-manifold based machine learning, instead of constructing a single
subspace in the manner described above, we construct a set of subspaces, one for each
data cluster on the nonlinear manifold. After the subspaces have been constructed, a
data element is assigned to that subspace for which the reconstruction error is the
least.> On the face of it, this sounds like a chicken-and-egg sort of a problem. You
need to have already clustered the data in order to construct the subspaces at
different places on the manifold so that you can figure out which cluster to place a
data element in.
Such problems, when they do possess a solution, are best tackled through iterative
algorithms in which you start with a guess for the final solution, you rearrange the
measured data on the basis of the guess, and you then use the new arrangement of the
data to refine the guess. Subsequently, you iterate through the second and the third
steps until you do not see any discernible changes in the new arrangements of the
data. This forms the basis of the clustering algorithm that is described under
B<Phase 1> in the section that follows. This algorithm was first proposed in the
article "Dimension Reduction by Local Principal Component Analysis" by Kambhatla and
Leen that appeared in the journal Neural Computation in 1997.
Unfortunately, experiments show that the algorithm as proposed by Kambhatla and Leen
is much too sensitive to how the clusters are seeded initially. To get around this
limitation of the basic clustering-by-minimization-of-reconstruction-error, this
module implements a two phased approach. In B<Phase 1>, we introduce a multiplier
effect in our search for clusters by looking for C<M*K> clusters instead of the main
C<K> clusters. In this manner, we increase the odds that each original cluster will
be visited by one or more of the C<M*K> randomly selected seeds at the beginning,
where C<M> is the integer value given to the constructor parameter
C<cluster_search_multiplier>. Subsequently, we merge the clusters that belong
together in order to form the final C<K> clusters. That work is done in B<Phase 2>
of the algorithm.
For the cluster merging operation in Phase 2, we model the C<M*K> clusters as the
nodes of an attributed graph in which the weight given to an edge connecting a pair
of nodes is a measure of the similarity between the two clusters corresponding to the
two nodes. Subsequently, we use spectral clustering to merge the most similar nodes
in our quest to partition the data into C<K> clusters. For that purpose, we use the
Shi-Malik normalized cuts algorithm. The pairwise node similarity required by this
algorithm is measured by the C<pairwise_cluster_similarity()> method of the
C<LinearManifoldDataClusterer> class. The smaller the overall reconstruction error
when all of the data elements in one cluster are projected into the other's subspace
and vice versa, the greater the similarity between two clusters. Additionally, the
smaller the distance between the mean vectors of the clusters, the greater the
similarity between two clusters. The overall similarity between a pair of clusters
is a combination of these two similarity measures.
For additional information regarding the theoretical underpinnings of the algorithm
implemented in this module, visit
L<https://engineering.purdue.edu/kak/Tutorials/ClusteringDataOnManifolds.pdf>
=head1 SUMMARY OF THE ALGORITHM
We now present a summary of the two phases of the algorithm implemented in this
module. Note particularly the important role played by the constructor parameter
C<cluster_search_multiplier>. It is only when the integer value given to this
parameter is greater than 1 that Phase 2 of the algorithm kicks in.
=over 4
=item B<Phase 1:>
Through iterative minimization of the total reconstruction error, this phase of the
algorithm returns C<M*K> clusters where C<K> is the actual number of clusters you
expect to find in your data and where C<M> is the integer value given to the
constructor parameter C<cluster_search_multiplier>. As previously mentioned, on
account of the sensitivity of the reconstruction-error based clustering to how the
clusters are initially seeded, our goal is to look for C<M*K> clusters with the idea
of increasing the odds that each of the C<K> clusters will see at least one seed at
the beginning of the algorithm.
=over 4
=item Step 1:
Randomly choose C<M*K> data elements to serve as the seeds for that many clusters.
=item Step 2:
Construct initial C<M*K> clusters by assigning each data element to that cluster
whose seed it is closest to.
=item Step 3:
Calculate the mean and the covariance matrix for each of the C<M*K> clusters and
carry out an eigendecomposition of the covariance matrix. Order the eigenvectors in
decreasing order of the corresponding eigenvalues. The first C<P> eigenvectors
lib/Algorithm/LinearManifoldDataClusterer.pm view on Meta::CPAN
mask => $mask,
K => $K,
P => $P,
cluster_search_multiplier => $C,
max_iterations => $max_iter,
delta_reconstruction_error => 0.001,
terminal_output => 1,
write_clusters_to_files => 1,
visualize_each_iteration => 1,
show_hidden_in_3D_plots => 1,
make_png_for_each_iteration => 1,
);
A call to C<new()> constructs a new instance of the
C<Algorithm::LinearManifoldDataClusterer> class.
=back
=head2 Constructor Parameters
=over 8
=item C<datafile>:
This parameter names the data file that contains the multidimensional data records
you want the module to cluster. This file must be in CSV format and each record in
the file must include a symbolic tag for the record. Here are first few rows of such
a CSV file in the C<examples> directory:
d_161,0.0739248630173239,0.231119293395665,-0.970112873251437
a_59,0.459932215884786,0.0110216469739639,0.887885623314902
a_225,0.440503220903039,-0.00543366086464691,0.897734586447273
a_203,0.441656364946433,0.0437191337788422,0.896118459046532
...
...
What you see in the first column --- C<d_161>, C<a_59>, C<a_225>, C<a_203> --- are
the symbolic tags associated with four 3-dimensional data records.
=item C<mask>:
This parameter supplies the mask to be applied to the columns of your data file. For
the data file whose first few records are shown above, the mask should be C<N111>
since the symbolic tag is in the first column of the CSV file and since, presumably,
you want to cluster the data in the next three columns.
=item C<K>:
This parameter supplies the number of clusters you are looking for.
=item C<P>:
This parameter specifies the dimensionality of the manifold on which the data resides.
=item C<cluster_search_multiplier>:
As should be clear from the C<Summary of the Algorithm> section, this parameter plays
a very important role in the successful clustering of your data. As explained in
C<Description>, the basic algorithm used for clustering in Phase 1 --- clustering by
the minimization of the reconstruction error --- is sensitive to the choice of the
cluster seeds that are selected randomly at the beginning of the algorithm. Should
it happen that the seeds miss one or more of the clusters, the clustering produced is
likely to not be correct. By giving an integer value to C<cluster_search_multiplier>
that is greater than 1, you'll increase the odds that the randomly selected seeds
will see all clusters. When you set C<cluster_search_multiplier> to C<M>, you ask
Phase 1 of the algorithm to construct C<M*K> clusters as opposed to just C<K>
clusters. Subsequently, in Phase 2, the module uses inter-cluster similarity based
graph partitioning to merge the C<M*K> clusters into C<K> clusters.
=item C<max_iterations>:
This hard limits the number of iterations in Phase 1 of the algorithm. Ordinarily,
the iterations stop automatically when the change in the total reconstruction error
from one iteration to the next is less than the value specified by the parameter
C<delta_reconstruction_error>.
=item C<delta_reconstruction_error>:
It is this parameter that determines when the iterations will actually terminate in
Phase 1 of the algorithm. When the difference in the total reconstruction error from
one iteration to the next is less than the value given to this parameter, the
iterations come to an end. B<IMPORTANT: I have noticed that the larger the number of
data samples that need to be clustered, the larger must be the value give to this
parameter. That makes intuitive sense since the total reconstruction error is the
sum of all such errors for all of the data elements.> Unfortunately, the best value
for this parameter does NOT appear to depend linearly on the total number of data
records to be clustered.
=item C<terminal_output>:
When this parameter is set, you will see in your terminal window the different
clusters as lists of the symbolic tags associated with the data records. You will
also see in your terminal window the output produced by the different steps of the
graph partitioning algorithm as smaller clusters are merged to form the final C<K>
clusters --- assuming that you set the parameter C<cluster_search_multiplier> to an
integer value that is greater than 1.
=item C<visualize_each_iteration>:
As its name implies, when this option is set to 1, you'll see 3D plots of the
clustering results for each iteration --- but only if your data is 3-dimensional.
=item C<show_hidden_in_3D_plots>:
This parameter is important for controlling the visualization of the clusters on the
surface of a sphere. If the clusters are too spread out, seeing all of the clusters
all at once can be visually confusing. When you set this parameter, the clusters on
the back side of the sphere will not be visible. Note that no matter how you set
this parameter, you can interact with the 3D plot of the data and rotate it with your
mouse pointer to see all of the data that is output by the clustering code.
=item C<make_png_for_each_iteration>:
If you set this option to 1, the module will output a Gnuplot in the form of a PNG
image for each iteration in Phase 1 of the algorithm. In Phase 2, the module will
output the clustering result produced by the graph partitioning algorithm.
=back
=over
=item B<get_data_from_csv()>:
$clusterer->get_data_from_csv();
lib/Algorithm/LinearManifoldDataClusterer.pm view on Meta::CPAN
show_hidden_in_3D_plots => 0,
);
=back
=head2 Parameters for the DataGenerator constructor:
=over 8
=item C<output_file>:
The numeric values are generated using a bivariate Gaussian distribution whose two
independent variables are the azimuth and the elevation angles on the surface of a
unit sphere. The mean of each cluster is chosen randomly and its covariance set in
proportion to the value supplied for the C< cluster_width> parameter.
=item C<cluster_width>:
This parameter controls the spread of each cluster on the surface of the unit sphere.
=item C<total_number_of_samples_needed>:
As its name implies, this parameter specifies the total number of data samples that
will be written out to the output file --- provided this number is divisible by the
number of clusters you asked for. If the divisibility condition is not satisfied,
the number of data samples actually written out will be the closest it can be to the
number you specify for this parameter under the condition that equal number of
samples will be created for each cluster.
=item C<number_of_clusters_on_sphere>:
Again as its name implies, this parameters specifies the number of clusters that will
be produced on the surface of a unit sphere.
=item C<show_hidden_in_3D_plots>:
This parameter is important for the visualization of the clusters and it controls
whether you will see the generated data on the back side of the sphere. If the
clusters are not too spread out, you can set this parameter to 0 and see all the
clusters all at once. However, when the clusters are spread out, it can be visually
confusing to see the data on the back side of the sphere. Note that no matter how
you set this parameter, you can interact with the 3D plot of the data and rotate it
with your mouse pointer to see all of the data that is generated.
=back
=over 4
=item B<gen_data_and_write_to_csv()>:
$training_data_gen->gen_data_and_write_to_csv();
As its name implies, this method generates the data according to the parameters
specified in the DataGenerator constructor.
=item B<visualize_data_on_sphere()>:
$training_data_gen->visualize_data_on_sphere($output_file);
You can use this method to visualize the clusters produced by the data generator.
Since the clusters are located at randomly selected points on a unit sphere, by
looking at the output visually, you can quickly reject what the data generator has
produced and try again.
=back
=head1 HOW THE CLUSTERS ARE OUTPUT
When the option C<terminal_output> is set in the constructor of the
C<LinearManifoldDataClusterer> class, the clusters are displayed on the terminal
screen.
And, when the option C<write_clusters_to_files> is set in the same constructor, the
module dumps the clusters in files named
cluster0.txt
cluster1.txt
cluster2.txt
...
...
in the directory in which you execute the module. The number of such files will
equal the number of clusters formed. All such existing files in the directory are
destroyed before any fresh ones are created. Each cluster file contains the symbolic
tags of the data samples in that cluster.
Assuming that the data dimensionality is 3, if you have set the constructor parameter
C<visualize_each_iteration>, the module will deposit in your directory printable PNG
files that are point plots of the different clusters in the different iterations of
the algorithm. Such printable files are also generated for the initial clusters at
the beginning of the iterations and for the final clusters in Phase 1 of the
algorithm. You will also see in your directory a PNG file for the clustering result
produced by graph partitioning in Phase 2.
Also, as mentioned previously, a call to C<linear_manifold_clusterer()> in your own
code will return the clusters to you directly.
=head1 REQUIRED
This module requires the following modules:
List::Util
File::Basename
Math::Random
Graphics::GnuplotIF
Math::GSL::Matrix
POSIX
=head1 THE C<examples> DIRECTORY
The C<examples> directory contains the following four scripts that you might want to
play with in order to become familiar with the module:
example1.pl
example2.pl
example3.pl
example4.pl
( run in 1.028 second using v1.01-cache-2.11-cpan-97f6503c9c8 )