k-means function page

Introduction

This computable document has explanations and examples of using the function k-means of the package "ML::Clustering", [AAp1].

For an introduction to the K-means algorithm see [Wk1] or [AN1].

The implementation uses the distance functions Euclidean, Cosine, Hamming, Manhattan, and others.

The data in the examples below is generated and manipulated with the packages "Data::Generators", "Data::Reshapers", and "Data::Summarizers", described in the article "Introduction to data wrangling with Raku" , [AA1].

The plots are made with the package "Text::Plot", [AAp6].

Remark: By default find-clusters of [AAp1] uses the K-means algorithm. The function k-means calls find-clusters with the option setting method=>'K-means'.

In brief

The function k-means finds clusters using the K-means algorithm. Here are the arguments:

Basic examples

Here we derive a set of random points, and summarize it:

use Data::Generators;
use Data::Summarizers;
use Text::Plot;

my $n = 100;
my @data1 = (random-variate(NormalDistribution.new(5, 1.5), $n) X random-variate(NormalDistribution.new(5, 1), $n))
        .pick(30);
my @data2 = (random-variate(NormalDistribution.new(10, 1), $n) X random-variate(NormalDistribution.new(10, 1), $n))
        .pick(50);
my @data2D2 = [|@data1, |@data2].pick(*);
records-summary(@data2D2)

Here we plot the points:

use Text::Plot;
text-list-plot(@data2D2)

Here is how we use the function k-means to find clusters:

use ML::Clustering;
my @cls = |k-means(@data2D2, 2);
@cls>>.elems

Remark: The first argument is data points that is a list-of-numeric-lists. The second argument is a number of clusters to be found.

Remark: Here are sample points from each found cluster:

.say for @cls>>.pick(3);

We can verify the result by looking at the plot of the found clusters:

text-list-plot(@cls, point-char => <▽ ☐>, title => '▽ - 1st cluster; ☐ - 2nd cluster')

Scope

Here is more interesting looking two-dimensional data, data2D2:

use Data::Reshapers;
my $pointsPerCluster = 200;
my @data2D5 = [[10, 20, 4], [20, 60, 6], [40, 10, 6], [-30, 0, 4], [100, 100, 8]].map({
    random-variate(NormalDistribution.new($_[0], $_[2]), $pointsPerCluster) Z random-variate(NormalDistribution.new($_[1], $_[2]), $pointsPerCluster)
}).Array;
@data2D5 = flatten(@data2D5, max-level => 1).pick(*);
@data2D5.elems

Here is a plot of that data:

text-list-plot(@data2D5)

Here we find clusters and plot them together with their mean points:

srand(923);
my %clRes = find-clusters(@data2D5, 5, prop => 'All');
text-list-plot([|%clRes<Clusters>, %clRes<MeanPoints>], point-char => <1 2 3 4 5 ●>)

Remark: The function k-clusters can return results of different types controlled with the named argument "prop". Using prop => 'All' returns a hash with all properties of the cluster finding result.

Here are the centers of the clusters (the mean points):

%clRes<MeanPoints>

Control parameters (named arguments)

In this section we describe the named arguments of find-clusters that can be used to control the cluster finding process.

Distance function

The value of the argument distance-function specifies the distance function to be used -- close points tend to be placed in the same cluster. Here is example comparing the "standard" Geometry distance, euclidean-distance, with the "directional" distance, cosine-distance:

use ML::Clustering::DistanceFunctions;
('custom Euclidean' => -> @v1, @v2 { sqrt([+] (@v1 Z @v2).map({ ($_[0] - $_[1]) ** 2 })) },
 'built-in Cosine' => { ML::Clustering::DistanceFunctions.cosine-distance($^a, $^b) })
        .map({ say find-clusters(@data2D5, 3, distance-function => $_.value).&text-list-plot(
        title => 'distance function: ' ~ $_.key, point-char => <* ® o>), "\n" });

Instead of distance functions (subs) we can use string identifiers of "known functions":

<Euclidean Cosine>.map({ say find-clusters(@data2D5, 3, distance-function => $_).&text-list-plot(
        title => 'distance function: ' ~ $_, point-char => <* ® o>), "\n" });

Here is a list of identifiers corresponding to "known functions":

say ML::Clustering::DistanceFunctions.known-distance-function-specs():short;

Learning parameter

At a certain execution step of the algorithm the learning parameter specifies how much the current mean points have to be "pulled" in the direction of the estimated new points. Smaller values of the named argument learning-parameter correspond to more cautious learning:

(0.01, 0.1, 0.7).map({ say find-clusters(@data2D5, 2, learning-parameter => $_).&text-list-plot(
        title => 'learning-parameter:' ~ $_.Str, point-char => <* o>), "\n" });

We see the plots above that with smaller learning parameter better results are obtained. But keep in mind that in some situations that small learning parameters can make the computations too slow or produce worse clustering results.

Maximum steps

The value m of the named argument max-steps is used in the stopping criteria of the implemented K-means algorithm -- if in the number of iterations exceeds m then the algorithms stops. Here is example that shows better clustering results is obtained with larger max steps:

(1, 4, 100).map({ say find-clusters(@data2D5, 2, max-steps => $_).&text-list-plot(title => 'maximum steps: ' ~ $_.Str, point-char => <* o>), "\n" });

Minimum reassignments fraction

The value m of the option "min-reassignments-fraction" is used in the stopping criteria of the implemented K-means algorithm -- if in the last iteration step the fraction of the number of points that have changed clusters is less m then the algorithms stops. Here is example that shows better clustering results is obtained with a smaller fraction:

srand(9);
(0.01, 0.3).map({ say find-clusters(@data2D5, 3, min-reassigments-fraction => $_).&text-list-plot(
        title => 'min-reassigments-fraction: ' ~ $_.Str, point-char => Whatever), "\n" });

Precision goal

The value p of the named argument precision-goal is used specify in stopping criteria that evaluates the differences between the "old" and "new" clusters centers -- if the maximum of that difference is less than 10 ** (-p) then the cluster finding iterations stop. Here is example that shows using the different precision goals:

srand(1921);
(0.2, 5).map({ say find-clusters(@data2D5, 2, precision-goal => $_).&text-list-plot(title => 'precision goal: ' ~ $_.Str, point-char => Whatever), "\n" });

Applications

Animal weights clustering

Take animal weights data2D2 (and show data2D2 dimensions):

use Data::ExampleDatasets;
my @data2D2 = |example-dataset('https://raw.githubusercontent.com/antononcube/Raku-ML-Clustering/main/resources/dfAnimalWeights.csv');
say "dimensions: { dimensions(@data2D2) }";

Summarize:

records-summary(@data2D2)

Cluster by body weight only:

my %awRes1 = find-clusters(@data2D2.map({ [$_<BodyWeight>,] }), 4, prop => 'All');
.say for %awRes1<IndexClusters>.map({ to-pretty-table(@data2D2[|$_], field-names => <Species BodyWeight BodyWeight>, align => { :Species<l> }, float-format =>  '10.3f') });

Note that obtained clusters seem well separated by weight:

text-list-plot(((%awRes1<ClusterLabels>.Array >>+>> 1) Z @data2D2.map({ $_<BodyWeight> }))>>.log10.List)

Here we cluster using both body weight and brain weight -- for that combination of weights it makes sense to cluster with Cosine distance:

my %awRes2 = find-clusters(@data2D2.map({ $_<BodyWeight BrainWeight> }), 4, distance-function => 'Cosine', prop => 'All');
.say for %awRes2<IndexClusters>.map({ to-pretty-table(@data2D2[|$_], field-names => <Species BodyWeight BodyWeight>, align => { :Species<l> }, float-format =>  '10.3f') });

Note that obtained clusters seem well separated by body-brain weights directions:

text-list-plot(%awRes2<Clusters>>>.log10);

Properties and Relations

Often it is good idea to run k-means a few times:

for 1 ... 3 {
    say text-list-plot(k-means(@data2D5, 5), point-char => (1 .. 5)>>.Str, title => "run: { $_ }"), "\n";
}

Possible Issues

The initial mean points of the clusters are chosen at random. Hence, to reproduce clustering results srand has to be used.

Neat Examples

Extracted point-vectors from a rasterized formula x^2 + y^2 == 1:

my @blackPoints = [[11, 15], [40, 15], [9, 14], [10, 14], [11, 14], [12, 14], [13, 14], [38, 14], [39, 14], [40, 14], [41, 14], [42, 14], [9, 13], [10, 13], [12, 13], [13, 13], [38, 13], [39, 13], [41, 13], [42, 13], [12, 12], [13, 12], [41, 12], [42, 12], [11, 11], [12, 11], [40, 11], [41, 11], [64, 11], [65, 11], [66, 11], [67, 11], [10, 10], [11, 10], [12, 10], [39, 10], [40, 10], [41, 10], [64, 10], [65, 10], [66, 10], [67, 10], [2, 9], [3, 9], [6, 9], [7, 9], [9, 9], [10, 9], [11, 9], [12, 9], [13, 9], [30, 9], [31, 9], [35, 9], [36, 9], [37, 9], [38, 9], [39, 9], [40, 9], [41, 9], [42, 9], [66, 9], [67, 9], [2, 8], [3, 8], [4, 8], [5, 8], [6, 8], [7, 8], [22, 8], [23, 8], [31, 8], [32, 8], [35, 8], [36, 8], [66, 8], [67, 8], [3, 7], [4, 7], [5, 7], [6, 7], [22, 7], [23, 7], [31, 7], [32, 7], [35, 7], [36, 7], [50, 7], [51, 7], [52, 7], [53, 7], [54, 7], [55, 7], [56, 7], [57, 7], [58, 7], [66, 7], [67, 7], [3, 6], [4, 6], [5, 6], [20, 6], [21, 6], [22, 6], [23, 6], [24, 6], [25, 6], [31, 6], [32, 6], [33, 6], [34, 6], [35, 6], [36, 6], [50, 6], [51, 6], [52, 6], [53, 6], [54, 6], [55, 6], [56, 6], [57, 6], [66, 6], [67, 6], [3, 5], [4, 5], [5, 5], [6, 5], [20, 5], [21, 5], [22, 5], [23, 5], [24, 5], [25, 5], [32, 5], [33, 5], [34, 5], [35, 5], [50, 5], [51, 5], [52, 5], [53, 5], [55, 5], [56, 5], [57, 5], [66, 5], [67, 5], [2, 4], [3, 4], [4, 4], [5, 4], [6, 4], [7, 4], [22, 4], [23, 4], [32, 4], [33, 4], [34, 4], [35, 4], [50, 4], [51, 4], [52, 4], [53, 4], [54, 4], [55, 4], [56, 4], [57, 4], [58, 4], [64, 4], [65, 4], [66, 4], [67, 4], [68, 4], [69, 4], [1, 3], [2, 3], [3, 3], [6, 3], [7, 3], [22, 3], [23, 3], [33, 3], [34, 3], [64, 3], [65, 3], [66, 3], [67, 3], [68, 3], [69, 3], [33, 2], [34, 2], [31, 1], [32, 1], [33, 1], [34, 1], [30, 0], [31, 0], [32, 0], [33, 0]];

Plot the extracted point-vectors:

text-list-plot(@blackPoints, width => 76, height => 18)

Cluster and plot the clusters using different distance functions:

<Euclidean Cosine Chessboard Manhattan BrayCurtis Canberra>.map({
    say text-list-plot(
            k-means(@blackPoints, 7, distance-function => $_), 
            point-char => (1 .. 7)>>.Str, 
            title => $_, 
            width => 76, height => 18), "\n"
})

References

Articles, books

[Wk1] Wikipedia entry, "K-means clustering".

[AA1] Anton Antonov, "Introduction to data wrangling with Raku" , (2021), RakuForPrediction at WordPress.

[AN1] Amiya Nayak and Ivan Stojmenovic, "Handbook of Applied Algorithms: Solving Scientific, Engineering, and Practical Problems", Wiley, 2008. ISBN: 0470044926, 9780470044926.

Packages

[AAp1] Anton Antonov, ML::Clustering Raku package, (2022), GitHub/antononcube.

[AAp2] Anton Antonov, Data::Generators Raku package, (2021), GitHub/antononcube.

[AAp3] Anton Antonov, Data::Reshapers Raku package, (2021), GitHub/antononcube.

[AAp4] Anton Antonov, Data::Summarizers Raku package, (2021), GitHub/antononcube.

[AAp5] Anton Antonov, UML::Translators Raku package, (2022), GitHub/antononcube.

[AAp6] Anton Antonov, Text::Plot Raku package, (2022), GitHub/antononcube.