/ 
Sim-OPT-0.957
/ Sim::OPT::ClusterMedoid

NAME

Sim::OPT::ClusterMedoid - Hybrid similarity clustering and medoid selection for discrete Sim::OPT problem landscapes.

SYNOPSIS

use Sim::OPT::ClusterMedoid;

my $result = cluster_medoid(
    search_config => 'search2x.pl',
    results_file  => 'search2-report-0-0.csv',
    output_prefix => 'search2-landscape',
);

print "clusters: $result->{clusters}\n";
print "first medoid: $result->{medoids}[0]{instance}\n";

From the shell, after installation:

simopt-clustermedoid search2x.pl search2-report-0-0.csv search2-landscape

DESCRIPTION

Sim::OPT::ClusterMedoid partitions a discrete set of simulated or otherwise evaluated instances into clusters and selects one medoid for each cluster. A medoid is an actual observed instance whose total dissimilarity from the other members of its cluster is minimal. It is therefore suitable as a representative instance when an artificial average configuration would not correspond to a valid model.

The module reads the same Perl configuration file used by Sim::OPT. It uses $mypath and $file to recognize the instance names, and it obtains the variable identifiers and their numbers of levels directly from @varinumbers. Clustering-specific options are supplied in %landscapecluster.

Variables may be divided into context variables and problem variables. If context_variables is absent or empty, all non-fixed variables are treated as problem variables. Variables declared with exactly one level are accepted as fixed coordinates. Re-embedded landscapes may additionally declare fixed_levels => { variable => level, ... } so that a coordinate fixed at a non-1 global lattice level is validated but omitted from the distance metric. Performance is read from the selected CSV column. Negative column numbers use Perl array semantics, so -4 means the fourth column from the end of a row.

RATIONALE AND DISTANCE CALCULATION

The calculation is designed to avoid two opposite failure modes. A purely arithmetic aggregation is compensatory: a very good match in some components can offset a poor match in another. A pure product is conjunctive but may be too severe: one zero or near-zero component can collapse the whole similarity. Sim::OPT::ClusterMedoid therefore mixes arithmetic and geometric aggregation.

For an ordered discrete variable v having L_v levels, two instances i and j have normalized variable dissimilarity

d_v(i,j) = log(1 + |l_iv - l_jv|) / log(L_v)

and similarity

s_v(i,j) = 1 - d_v(i,j).

Thus s_v lies in [0,1]. Equal levels give similarity 1, while the maximum possible level separation gives similarity 0.

Within a semantic group, such as the problem variables or the context variables, the weighted arithmetic similarity is

A = sum(w_v s_v) / sum(w_v)

and the weighted geometric similarity is

G = exp( sum(w_v log(s_v)) / sum(w_v) ).

If any positively weighted similarity is zero, G is zero. The group similarity is

H = (1 - lambda) A + lambda G,

with lambda = 0.5 by default. lambda = 0 gives a purely arithmetic aggregation; lambda = 1 gives a geometric aggregation. Intermediate values trade compensability against conjunctiveness.

Performance is converted to a normalized logarithmic similarity on an analogous virtual level scale. If the performance span is divided into N divisions, one virtual step is

step = |worst - best| / N.

For performance values y_i and y_j,

d_y = log(1 + |y_i-y_j|/step) / log(1 + N)
s_y = 1 - d_y,

with the step difference clipped to N. If best and worst are not specified, the observed minimum and maximum performances are used.

The same arithmetic-geometric hybrid operator is then applied to the available high-level components: context similarity, problem similarity, and performance similarity. The final clustering dissimilarity is

D(i,j) = 1 - H_overall(i,j).

This module was motivated by the distance-based treatment of discrete design spaces in Sim::OPT::Interlinear, but the present formula is not a literal reimplementation of Interlinear. In the supplied Sim::OPT 0.921 source, Interlinear normalizes level increments by 1/(L-1), combines them with a Pythagorean distance, and then normalizes by the maximum distance. Interlinear's logarithmic option concerns the relaxation/weighting of neighbours. ClusterMedoid retains the logarithmic level mapping developed specifically for this clustering method.

CLUSTERING

The pairwise dissimilarity matrix is clustered by a pure-Perl k-medoids procedure. Initial medoids are chosen deterministically: first the globally most central observation, then observations that are farthest from the medoids already selected. Instances are assigned to their nearest medoid, and each medoid is repeatedly replaced by the member minimizing the total within-cluster dissimilarity until convergence or max_iterations is reached.

If clustering => { clusters => 'auto' } is used, candidate values of k are evaluated by the mean silhouette coefficient and the best candidate is retained. Alternatively, a fixed number of clusters may be specified.

CONFIGURATION

Add a clearly delimited block such as the following to the normal Sim::OPT configuration file:

##############################################################################
############ SIM::OPT::CLUSTERMEDOID SETTINGS - BEGIN ########################

%landscapecluster = (
    sweep_index         => 0,
    combination_column  => 0,
    performance_column  => -4,

    # [] means that every variable in @varinumbers is a problem variable.
    # [ 1, 2 ] makes variables 1 and 2 context variables and all remaining
    # variables problem variables.
    context_variables   => [ 1, 2 ],

    # 0 = arithmetic, 1 = geometric, 0.5 = equal hybrid.
    lambda              => 0.5,

    performance => {
        divisions => 100,
        # best  => 60,   # optional; observed minimum is used if omitted
        # worst => 80,   # optional; observed maximum is used if omitted
    },

    clustering => {
        clusters          => 'auto',
        k_min             => 2,
        k_max             => 12,
        max_iterations    => 50,
        silhouette_sample => 600,
    },
);

############ SIM::OPT::CLUSTERMEDOID SETTINGS - END ##########################
##############################################################################

variable_weights and component_weights may optionally be added. For example:

variable_weights => { 1 => 2, 2 => 2, 9 => 0.5 },

component_weights => {
    context     => 1,
    problem     => 1,
    performance => 1,
},

All weights must be positive.

OUTPUT FILES

Four files are written using the requested output prefix:

  • .clustered.csv

    The original dataset with appended cluster and is_medoid columns.

  • .medoids.csv

    One row for each cluster, containing the source CSV row, instance name, performance, and variable levels of the medoid.

  • .silhouette.csv

    The candidate k values and the silhouette score used for selection.

  • .info.txt

    A concise record of the metric, configuration, selected number of clusters, silhouette, cluster sizes, and medoid source rows.

FUNCTION

cluster_medoid

my $result = cluster_medoid(
    search_config => $configuration_file,
    results_file  => $csv_file,
    output_prefix => $prefix,       # optional
    verbose       => 1,             # optional
);

Returns a hash reference containing the selected cluster count, silhouette, medoid records, variable classification, and paths of the files written.

run_cli

run_cli is exported only on request and implements the installed simopt-clustermedoid command.

MEMORY AND COMPUTATIONAL COST

The implementation stores the complete pairwise distance matrix. Its memory requirement is therefore O(n^2), and exact medoid updates can also be expensive for large datasets. The method is intended primarily for discrete experimental or simulation landscapes of moderate size, where retaining the actual medoid observations is valuable.

SEE ALSO

Sim::OPT, Sim::OPT::Interlinear, Sim::OPT::Morph, Sim::OPT::Descend.

AUTHOR

Gian Luca Brunetti, <gianluca.brunetti@polimi.it>

ACKNOWLEDGEMENTS

The initial design and implementation of ClusterMedoid were developed by Gian Luca Brunetti with assistance from AI.

COPYRIGHT AND LICENSE

Copyright (C) 2008-2025 by Gian Luca Brunetti, gianluca.brunetti@gmail.com. This software is distributed under a dual licence, open-source (GPL v3) and proprietary. The present copy is GPL. By consequence, this is free software. You can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 3.