### ----------------------------------------------------
### -- ML::Clustering
### -- Licenses: Artistic-2.0
### -- Authors: Anton Antonov
### -- File: doc/K-means-function-page-work.md
### ----------------------------------------------------
# `k-means` function page

## Introduction

This computable document has explanations and examples of using the function `k-means` of the package
["ML::Clustering"](https://github.com/antononcube/Raku-ML-Clustering), [AAp1].

For an introduction to the [K-means](https://en.wikipedia.org/wiki/K-means_clustering) 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"](https://raku.land/zef:antononcube/Data::Generators),
["Data::Reshapers"](https://raku.land/zef:antononcube/Data::Reshapers), and
["Data::Summarizers"](https://raku.land/zef:antononcube/Data::Summarizers), described in the article
["Introduction to data wrangling with Raku"](https://rakuforprediction.wordpress.com/2021/12/31/introduction-to-data-wrangling-with-raku/)
,
[AA1].

The plots are made with the package
["Text::Plot"](https://raku.land/zef:antononcube/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:

| Argument                      | Default      | Description                                                                                                          |
|-------------------------------|--------------|----------------------------------------------------------------------------------------------------------------------|
| `@points`                     | _            | data points                                                                                                          |
| `$k`                          | _            | number of clusters                                                                                                   |
| `:$distance-function`         | 'Euclidean'  | points distance function                                                                                             |
| `:$learning-parameter`        | 0.01         | re-assignment learning parameter                                                                                     |
| `:$max-steps`                 | 1000         | maximum number of steps                                                                                              |
| `:$min-reassignment-fraction` | 0.005        | minimum re-assignments required to continue the iterations                                                           |
| `:$precision-goal`            | 6            | precision goal                                                                                                       |
| `:$prop`                      | 'Clusters'   | property to give as a result, one of 'MeanPoints', 'Clusters', 'ClusterLabels', 'IndexClusters', 'Properties', 'All' |

-------

## Basic examples

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

```perl6
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:

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

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

```perl6
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:

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

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

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

------

## Scope

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

```perl6
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:

```perl6
text-list-plot(@data2D5)
```

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

```perl6
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):

```perl6
%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`:

```perl6
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":

```perl6
<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":

```perl6
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:

```perl6
(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:

```perl6
(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:

```perl6
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:

```perl6
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):

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

Summarize:

```perl6
records-summary(@data2D2)
```

Cluster by body weight only:

```perl6
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:

```perl6
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:

```perl6
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:

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

------

## Properties and Relations

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

```perl6
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`:

```perl6
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:

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

Cluster and plot the clusters using different distance functions:

```perl6
<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"](https://en.wikipedia.org/wiki/K-means_clustering).

[AA1] Anton Antonov,
["Introduction to data wrangling with Raku"](https://rakuforprediction.wordpress.com/2021/12/31/introduction-to-data-wrangling-with-raku/)
,
(2021),
[RakuForPrediction at WordPress](https://rakuforprediction.wordpress.com).

[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](https://github.com/antononcube/Raku-ML-Clustering),
(2022),
[GitHub/antononcube](https://github.com/antononcube).

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

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

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

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

[AAp6] Anton Antonov,
[Text::Plot Raku package](https://raku.land/zef:antononcube/Text::Plot),
(2022),
[GitHub/antononcube](https://github.com/antononcube).


