Help language development. Donate to The Perl Foundation

ML::AssociationRuleLearning zef:antononcube last updated on 2022-08-20

README.md
# Raku ML::AssociationRuleLearning

[![SparkyCI](http://sparrowhub.io:2222/project/gh-antononcube-Raku-ML-AssociationRuleLearning/badge)](http://sparrowhub.io:2222)
[![License: Artistic-2.0](https://img.shields.io/badge/License-Artistic%202.0-0298c3.svg)](https://opensource.org/licenses/Artistic-2.0)

This repository has the code of a Raku package for
[Association Rule Learning (ARL)](https://en.wikipedia.org/wiki/Association_rule_learning)
functions, [Wk1].

The ARL framework includes the algorithms 
[Apriori](https://en.wikipedia.org/wiki/Apriori_algorithm) 
and 
[Eclat](https://en.wikipedia.org/wiki/Association_rule_learning#Eclat_algorithm), 
and the measures 
[confidence](https://en.wikipedia.org/wiki/Association_rule_learning#Confidence),
[lift](https://en.wikipedia.org/wiki/Association_rule_learning#Lift), and 
[conviction](https://en.wikipedia.org/wiki/Association_rule_learning#Conviction), 
(and others.)

For computational introduction to ARL utilization (in Mathematica) see the article
["Movie genre associations"](https://mathematicaforprediction.wordpress.com/2013/10/06/movie-genre-associations/),
[AA1].

The examples below use the packages
["Data::Generators"](https://raku.land/cpan:ANTONOV/Data::Generators),
["Data::Reshapers"](https://raku.land/cpan:ANTONOV/Data::Reshapers), and
["Data::Summarizers"](https://raku.land/cpan:ANTONOV/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/),
[AA2].

-------

## Installation

Via zef-ecosystem:

```shell
zef install ML::AssociationRuleLearning
```

From GitHub:

```shell
zef install https://github.com/antononcube/Raku-ML-AssociationRuleLearning
```

-------

## Frequent sets finding 

Here we get the Titanic dataset (from "Data::Reshapers") and summarize it:

```perl6
use Data::Reshapers;
use Data::Summarizers;
my @dsTitanic = get-titanic-dataset();
records-summary(@dsTitanic);
```
```
# +-------------------+----------------+----------------+---------------+-----------------+
# | passengerSurvival | passengerAge   | passengerClass | passengerSex  | id              |
# +-------------------+----------------+----------------+---------------+-----------------+
# | died     => 809   | 20      => 334 | 3rd => 709     | male   => 843 | 1036    => 1    |
# | survived => 500   | -1      => 263 | 1st => 323     | female => 466 | 655     => 1    |
# |                   | 30      => 258 | 2nd => 277     |               | 50      => 1    |
# |                   | 40      => 190 |                |               | 1230    => 1    |
# |                   | 50      => 88  |                |               | 320     => 1    |
# |                   | 60      => 57  |                |               | 1126    => 1    |
# |                   | 0       => 56  |                |               | 779     => 1    |
# |                   | (Other) => 63  |                |               | (Other) => 1302 |
# +-------------------+----------------+----------------+---------------+-----------------+
```

**Problem:** Find all combinations of values of the variables "passengerAge", "passengerClass", "passengerSex", and
"passengerSurvival" that appear more than 200 times in the Titanic dataset.

Here is how we use the function `frequent-sets` to give an answer:

```perl6
use ML::AssociationRuleLearning;
my @freqSets = frequent-sets(@dsTitanic, min-support => 200, min-number-of-items => 2, max-number-of-items => Inf):counts;
@freqSets.elems
```
```
# 11
```

The function `frequent-sets` returns the frequent sets together with their support.

Here we tabulate the result:

```perl6
say to-pretty-table(@freqSets.map({ %( Frequent-set => $_.key.join(' '), Count => $_.value) }), align => 'l');
```
```
# +-------+-------------------------------------------------------------+
# | Count | Frequent-set                                                |
# +-------+-------------------------------------------------------------+
# | 208   | passengerAge:-1 passengerClass:3rd                          |
# | 206   | passengerAge:20 passengerClass:3rd                          |
# | 207   | passengerAge:20 passengerSex:male                           |
# | 207   | passengerAge:20 passengerSurvival:died                      |
# | 200   | passengerClass:1st passengerSurvival:survived               |
# | 216   | passengerClass:3rd passengerSex:female                      |
# | 493   | passengerClass:3rd passengerSex:male                        |
# | 418   | passengerClass:3rd passengerSex:male passengerSurvival:died |
# | 528   | passengerClass:3rd passengerSurvival:died                   |
# | 339   | passengerSex:female passengerSurvival:survived              |
# | 682   | passengerSex:male passengerSurvival:died                    |
# +-------+-------------------------------------------------------------+
```

We can verify the result by looking into these group counts, [AA2]:

```perl6
my $obj = group-by( @dsTitanic, <passengerClass passengerSex>);
.say for $obj>>.elems.grep({ $_.value >= 200 });
$obj = group-by( @dsTitanic, <passengerClass passengerSurvival passengerSex>);
.say for $obj>>.elems.grep({ $_.value >= 200 });
```
```
# 3rd.male => 493
# 3rd.female => 216
# 3rd.died.male => 418
```

Or these contingency tables:

```perl6
my $obj = group-by( @dsTitanic, "passengerClass") ;
$obj = $obj.map({ $_.key => cross-tabulate( $_.value, "passengerSex", "passengerSurvival" ) });
.say for $obj.Array;
```
```
# 1st => {female => {died => 5, survived => 139}, male => {died => 118, survived => 61}}
# 2nd => {female => {died => 12, survived => 94}, male => {died => 146, survived => 25}}
# 3rd => {female => {died => 110, survived => 106}, male => {died => 418, survived => 75}}
```

**Remark:** For datasets -- i.e. arrays of hashes -- `frequent-sets` preprocesses the data by concatenating
column names with corresponding column values. This is done in order to prevent "collisions" of same values 
coming from different columns. If that concatenation is not desired then manual preprocessing like this can be used:

```{perl6, eval=FALSE}
@dsTitanic.map({ $_.values.List }).Array
```

**Remark:** `frequent-sets`'s argument `min-support` can take both integers greater than 1 and frequencies between 0 and 1.
(If an integer greater than one is given, then the corresponding frequency is derived.)

**Remark:** By default `frequent-sets` uses the Eclat algorithm. The functions `apriori` and `eclat`
call `frequent-sets` with the option settings `method=>'Apriori'` and `method=>'Eclat'` respectively.

-------

## Association rules finding

Here we find association rules with min support 0.3 and min confidence 0.7:

```perl6
association-rules(@dsTitanic, min-support => 0.3, min-confidence => 0.7)
==> to-pretty-table
```
```
# +------------------------+-------+----------+-------------------------------------------+----------+------------+------------+----------+
# |       consequent       | count | support  |                antecendent                | leverage | conviction | confidence |   lift   |
# +------------------------+-------+----------+-------------------------------------------+----------+------------+------------+----------+
# | passengerSurvival:died |  528  | 0.403361 |             passengerClass:3rd            | 0.068615 |  1.496229  |  0.744711  | 1.204977 |
# | passengerSurvival:died |  682  | 0.521008 |             passengerSex:male             | 0.122996 |  2.000009  |  0.809015  | 1.309025 |
# |   passengerSex:male    |  682  | 0.521008 |           passengerSurvival:died          | 0.122996 |  2.267729  |  0.843016  | 1.309025 |
# | passengerSurvival:died |  418  | 0.319328 |    passengerClass:3rd passengerSex:male   | 0.086564 |  2.510823  |  0.847870  | 1.371894 |
# |   passengerSex:male    |  418  | 0.319328 | passengerClass:3rd passengerSurvival:died | 0.059562 |  1.708785  |  0.791667  | 1.229290 |
# +------------------------+-------+----------+-------------------------------------------+----------+------------+------------+----------+
```

### Reusing found frequent sets

The function `frequent-sets` takes the adverb ":object" that makes `frequent-sets` return an object of type
`ML::AssociationRuleLearning::Apriori` or `ML::AssociationRuleLearning::Eclat`, 
which can be "pipelined" to find association rules.

Here we find frequent sets, return the corresponding object, and retrieve the result:

```perl6
my $eclatObj = frequent-sets(@dsTitanic.map({ $_.values.List }).Array, min-support => 0.12, min-number-of-items => 2, max-number-of-items => 6):object;
$eclatObj.result.elems
```
```
# 23
```

Here we find association rules and pretty-print them:

```perl6
$eclatObj.find-rules(min-confidence=>0.7)
==> to-pretty-table 
```
```
# +------------+-------+-------------+----------+----------+------------+----------+------------+
# | confidence | count | antecendent | leverage |   lift   | consequent | support  | conviction |
# +------------+-------+-------------+----------+----------+------------+----------+------------+
# |  0.790875  |  208  |      -1     | 0.050076 | 1.460162 |    3rd     | 0.158900 |  2.191819  |
# |  0.703422  |  185  |      -1     | 0.011938 | 1.092265 |    male    | 0.141329 |  1.200349  |
# |  0.843016  |  682  |     died    | 0.122996 | 1.309025 |    male    | 0.521008 |  2.267729  |
# |  0.809015  |  682  |     male    | 0.122996 | 1.309025 |    died    | 0.521008 |  2.000009  |
# |  0.791667  |  418  |   3rd died  | 0.059562 | 1.229290 |    male    | 0.319328 |  1.708785  |
# |  0.847870  |  418  |   3rd male  | 0.086564 | 1.371894 |    died    | 0.319328 |  2.510823  |
# |  0.836842  |  159  |   -1 died   | 0.027990 | 1.299438 |    male    | 0.121467 |  2.181917  |
# |  0.859459  |  159  |   -1 male   | 0.034121 | 1.390646 |    died    | 0.121467 |  2.717870  |
# |  0.846154  |  176  |   20 died   | 0.032122 | 1.313897 |    male    | 0.134454 |  2.313980  |
# |  0.846154  |  176  |   20 male   | 0.036249 | 1.369117 |    died    | 0.134454 |  2.482811  |
# |  0.727468  |  339  |    female   | 0.122996 | 1.904511 |  survived  | 0.258976 |  2.267729  |
# |  0.744711  |  528  |     3rd     | 0.068615 | 1.204977 |    died    | 0.403361 |  1.496229  |
# |  0.759615  |  158  |    -1 3rd   | 0.022498 | 1.229093 |    died    | 0.120703 |  1.588999  |
# |  0.831579  |  158  |   -1 died   | 0.042085 | 1.535313 |    3rd     | 0.120703 |  2.721543  |
# |  0.722433  |  190  |      -1     | 0.020977 | 1.168931 |    died    | 0.145149 |  1.376142  |
# +------------+-------+-------------+----------+----------+------------+----------+------------+
```

**Remark:** Note that because of the specified min confidence, the number of association rules is "contained" --
a (much) larger number of rules would be produced with, say, `min-confidence=>0.2`.


-------

## Implementation considerations

### UML diagram

Here is a UML diagram that shows package's structure:

![](./resources/class-diagram.png)


The
[PlantUML spec](./resources/class-diagram.puml)
and
[diagram](./resources/class-diagram.png)
were obtained with the CLI script `to-uml-spec` of the package "UML::Translators", [AAp6].

Here we get the [PlantUML spec](./resources/class-diagram.puml):

```shell
to-uml-spec ML::AssociationRuleLearning > ./resources/class-diagram.puml
```

Here get the [diagram](./resources/class-diagram.png):

```shell
to-uml-spec ML::AssociationRuleLearning | java -jar ~/PlantUML/plantuml-1.2022.5.jar -pipe > ./resources/class-diagram.png
```

**Remark:** Maybe it is a good idea to have an abstract class named, say,
`ML::AssociationRuleLearning::AbstractFinder` that is a parent of both
`ML::AssociationRuleLearning::Apriori` and `ML::AssociationRuleLearning::Eclat`,
but I have not found to be necessary. (At this point of development.)

### Eclat

We can say that Eclat uses a "vertical database representation" of the transactions.

Eclat is based on Raku's 
[sets, bags, and mixes](https://docs.raku.org/language/setbagmix)
functionalities.

Eclat represents the transactions as a hash of sets:

- The keys of the hash are items

- The elements of the sets are transaction identifiers.

(In other words, for each item an inverse index is made.)

This representation allows for quick calculations of item combinations support.

### Apriori 

Apriori uses the standard, horizontal database transactions representation.

We can say that Apriori:

- Generates candidates for item frequent sets using the routine 
  [`combinations`](https://docs.raku.org/routine/combinations)

- Filters candidates by 
  [Tries with frequencies](https://github.com/antononcube/Raku-ML-TriesWithFrequencies) 
  creation and removal by threshold

Apriori is usually (much) slower than Eclat. 
Historically, Apriori is the first ARL method, and its implementation in the package is didactic.

### Association rules

We can say that the association rule finding function is a general one, but that function
does require fast computation of confidence, lift, etc. Hence Eclat's transactions representation
is used.

Association rules finding with Apriori is the same as with Eclat. 
The package function `assocition-rules` with the option setting `method=>'Apriori'`
simply sends frequent sets found with Apriori to the Eclat based association rule finding.

-------

## References

### Articles

[Wk1] Wikipedia entry, ["Association Rule Learning"](https://en.wikipedia.org/wiki/Association_rule_learning).

[AA1] Anton Antonov,
["Movie genre associations"](https://mathematicaforprediction.wordpress.com/2013/10/06/movie-genre-associations/),
(2013),
[MathematicaForPrediction at WordPress](https://mathematicaforprediction.wordpress.com).

[AA2] 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).

### Packages

[AAp1] Anton Antonov,
[Implementation of the Apriori algorithm in Mathematica](https://github.com/antononcube/MathematicaForPrediction/blob/master/AprioriAlgorithm.m),
(2014-2016),
[MathematicaForPrediction at GitHub/antononcube](https://github.com/antononcube/MathematicaForPrediction/).

[AAp1a] Anton Antonov
[Implementation of the Apriori algorithm via Tries in Mathematica](https://github.com/antononcube/MathematicaForPrediction/blob/master/Misc/AprioriAlgorithmViaTries.m),
(2022),
[MathematicaForPrediction at GitHub/antononcube](https://github.com/antononcube/MathematicaForPrediction/).

[AAp2] Anton Antonov,
[Implementation of the Eclat algorithm in Mathematica](https://github.com/antononcube/MathematicaForPrediction/blob/master/EclatAlgorithm.m),
(2022),
[MathematicaForPrediction at GitHub/antononcube](https://github.com/antononcube/MathematicaForPrediction/).

[AAp3] Anton Antonov,
[Data::Generators Raku package](https://raku.land/cpan:ANTONOV/Data::Generators),
(2021),
[GitHub/antononcube](https://github.com/antononcube).

[AAp4] Anton Antonov,
[Data::Reshapers Raku package](https://raku.land/cpan:ANTONOV/Data::Reshapers),
(2021),
[GitHub/antononcube](https://github.com/antononcube).

[AAp5] Anton Antonov,
[Data::Summarizers Raku package](https://raku.land/cpan:ANTONOV/Data::Summarizers),
(2021),
[GitHub/antononcube](https://github.com/antononcube).

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

[AAp7] Anton Antonov,
[ML::TrieWithFrequencies Raku package](https://raku.land/cpan:ANTONOV/ML::TriesWithFrequencies),
(2021),
[GitHub/antononcube](https://github.com/antononcube).