Contents

This module implements the association rules data mining technique on a transactional data set. Given the names of a table and the columns, minimum support and confidence values, this function generates all single and multidimensional association rules that meet the minimum thresholds.

Association rule mining is a widely used technique for discovering relationships between variables in a large data set (e.g., items in a store that are commonly purchased together). The classic market basket analysis example using association rules is the "beer and diapers" rule. According to data mining urban legend, a study of customer purchase behavior in a supermarket found that men often purchased beer and diapers together. After making this discovery, the managers strategically placed beer and diapers closer together on the shelves and saw a dramatic increase in sales. In addition to market basket analysis, association rules are also used in bioinformatics, web analytics, and several other fields.

This type of data mining algorithm uses transactional data. Every transaction event has a unique identifier, and each transaction consists of a set of items (or itemset). Purchases are considered binary (either it was purchased or not), and this implementation does not take into consideration the quantity of each item. For the MADlib association rules function, it is assumed that the data is stored in two columns with one item and transaction id per row. Transactions with multiple items will span multiple rows with one row per item.

    trans_id | product
    ---------+---------
           1 | 1
           1 | 2
           1 | 3
           1 | 4
           2 | 3
           2 | 4
           2 | 5
           3 | 1
           3 | 4
           3 | 6
    ...

Rules

Association rules take the form "If X, then Y", where X and Y are non-empty itemsets. X and Y are called the antecedent and consequent, or the left-hand-side and right-hand-side, of the rule respectively. Using our previous example, the association rule may state "If {diapers}, then {beer}" with .2 support and .85 confidence.

The following metrics are defined for any given itemset "X".

Count: The number of transactions that contain X
Support: The ratio of transactions that contain X to all transactions, T
\[ S (X) = \frac{Total X}{Total transactions} \]

Given any association rule "If X, then Y", the association rules function will also calculate the following metrics:

Count: The number of transactions that contain X,Y
Support: The ratio of transactions that contain X,Y to all transactions, T
\[ S (X \Rightarrow Y) = \frac{Total(X \cup Y)}{Total transactions} \]
Confidence: The ratio of transactions that contain \( X,Y \) to transactions that contain \( X \). One could view this metric as the conditional probability of \( Y \) , given \( X \) . \( P(Y|X) \)
\[ C (X \Rightarrow Y) = \frac{s(X \cap Y )}{s(X)} \]
Lift: The ratio of observed support of \( X,Y \) to the expected support of \( X,Y \) , assuming \( X \) and \( Y \) are independent.
\[ L (X \Rightarrow Y) = \frac{s(X \cap Y )}{s(X) \cdot s(Y)} \]
Conviction: The ratio of expected support of \( X \) occurring without \( Y \) assuming \( X \) and \( \neg Y \) are independent, to the observed support of \( X \) occuring without \( Y \). If conviction is greater than 1, then this metric shows that incorrect predictions ( \( X \Rightarrow Y \) ) occur less often than if these two actions were independent. This metric can be viewed as the ratio that the association rule would be incorrect if the actions were independent (i.e. a conviction of 1.5 indicates that if the variables were independent, this rule would be incorrect 50% more often.)

\[ Conv (X \Rightarrow Y) = \frac{1 - S(Y)}{1 - C(X \Rightarrow Y)} \]

Apriori Algorithm

Although there are many algorithms that generate association rules, the classic algorithm is called Apriori [1] which we have implemented in this module. It is a breadth-first search, as opposed to depth-first searches like Eclat. Frequent itemsets of order \( n \) are generated from sets of order \( n - 1 \). Using the downward closure property, all sets must have frequent subsets. There are two steps in this algorithm; generating frequent itemsets, and using these itemsets to construct the association rules. A simplified version of the algorithm is as follows, and assumes a minimum level of support and confidence is provided:

Initial step

Generate all itemsets of order 1.
Eliminate itemsets that have support less than minimum support.

Main algorithm

For \( n \ge 2 \), generate itemsets of order \( n \) by combining the itemsets of order \( n - 1 \). This is done by doing the union of two itemsets that have identical items except one.
Eliminate itemsets that have (n-1) order subsets with insufficient support.
Eliminate itemsets with insufficient support.
Repeat until itemsets cannot be generated, or maximum itemset size is exceeded.

Association rule generation

Given a frequent itemset \( A \) generated from the Apriori algorithm, and all subsets \( B \) , we generate rules such that \( B \Rightarrow (A - B) \) meets minimum confidence requirements.

Note: Beware of combinatorial explosion. The Apriori algorithm can potentially generate a huge number of rules, even for fairly simple data sets, resulting in run times that are unreasonably long. To avoid this, it is recommended to cap the maximum itemset size to a small number to start with, then increase it gradually. Similarly, max_LHS_size and max_RHS_size limit the number of items on the LHS and RHS of the rules and can significantly reduce run times. Support and confidence values are parameters that can also be used to control rule generation.

Function Syntax

Association rules has the following syntax:

assoc_rules( support,
             confidence,
             tid_col,
             item_col,
             input_table,
             output_schema,
             verbose,
             max_itemset_size,
             max_LHS_size,
             max_RHS_size
           );

This generates all association rules that satisfy the specified minimum support and confidence.

Arguments

support

Minimum level of support needed for each itemset to be included in result.

confidence

Minimum level of confidence needed for each rule to be included in result.

tid_col

Name of the column storing the transaction ids.

item_col

Name of the column storing the products.

input_table

Name of the table containing the input data.

The input data is expected to be of the following form:

{TABLE|VIEW} input_table (
    trans_id INTEGER,
    product TEXT
)

The algorithm maps the product names to consecutive integer ids starting at 1. If they are already structured this way, then the ids will not change.

output_schema

The name of the schema where the final results will be stored. The schema must be created before calling the function. Alternatively, use NULL to output to the current schema.

The results containing the rules, support, count, confidence, lift, and conviction are stored in the table assoc_rules in the schema specified by output_schema.

The table has the following columns.

ruleid	integer
pre	text
post	text
count	integer
support	double
confidence	double
lift	double
conviction	double

On Greenplum Database, the table is distributed by the ruleid column.

The pre and post columns are the itemsets of left and right hand sides of the association rule respectively. The support, confidence, lift, and conviction columns are calculated as described earlier.

verbose (optional)

BOOLEAN, default: FALSE. Determines if details are printed for each iteration as the algorithm progresses.

max_itemset_size (optional)

INTEGER, default: 10. Determines the maximum size of frequent itemsets that are used for generating association rules. Must be 2 or more. This parameter can be used to reduce run time for data sets where itemset size is large, which is a common situation. If your query is not returning or is running too long, try using a lower value for this parameter.

max_LHS_size (optional)

INTEGER, default: NULL. Determines the maximum size of the left hand side of the rule. Must be 1 or more. This parameter can be used to reduce run time.

max_RHS_size (optional)

INTEGER, default: NULL. Determines the maximum size of the right hand side of the rule. Must be 1 or more. This parameter can be used to reduce run time. For example, setting to 1 can significantly reduce run time if this makes sense for your use case. (The apriori algorithm in the R package arules [2] only supports a RHS of 1.)

Examples

Let's look at some sample transactional data and generate association rules.

Create an input dataset:

DROP TABLE IF EXISTS test_data;
CREATE TABLE test_data (
    trans_id INT,
    product TEXT
);
INSERT INTO test_data VALUES
(1, 'beer'),
(1, 'diapers'),
(1, 'chips'),
(2, 'beer'),
(2, 'diapers'),
(3, 'beer'),
(3, 'diapers'),
(4, 'beer'),
(4, 'chips'),
(5, 'beer'),
(6, 'beer'),
(6, 'diapers'),
(6, 'chips'),
(7, 'beer'),
(7, 'diapers');

Let \( min(support) = .25 \) and \( min(confidence) = .5 \), and the output schema is set to NULL indicating output to the current schema. In this example we set verbose to TRUE so that we have some insight into progress of the function. We can now generate association rules as follows:

DROP TABLE IF EXISTS assoc_rules;
SELECT * FROM madlib.assoc_rules( .25,            -- Support
                                  .5,             -- Confidence
                                  'trans_id',     -- Transaction id col
                                  'product',      -- Product col
                                  'test_data',    -- Input data
                                  NULL,           -- Output schema
                                  TRUE            -- Verbose output
                                );

Result (iteration details not shown):

 output_schema | output_table | total_rules |   total_time
---------------+--------------+-------------+-----------------
 public        | assoc_rules  |           7 | 00:00:00.569254
(1 row)

The association rules are stored in the assoc_rules table:

SELECT * FROM assoc_rules
ORDER BY support DESC, confidence DESC;

Result:

 ruleid |       pre       |      post      | count |      support      |    confidence     |       lift        |    conviction
--------+-----------------+----------------+-------+-------------------+-------------------+-------------------+-------------------
      2 | {diapers}       | {beer}         |     5 | 0.714285714285714 |                 1 |                 1 |                 0
      6 | {beer}          | {diapers}      |     5 | 0.714285714285714 | 0.714285714285714 |                 1 |                 1
      5 | {chips}         | {beer}         |     3 | 0.428571428571429 |                 1 |                 1 |                 0
      4 | {chips,diapers} | {beer}         |     2 | 0.285714285714286 |                 1 |                 1 |                 0
      1 | {chips}         | {diapers,beer} |     2 | 0.285714285714286 | 0.666666666666667 | 0.933333333333333 | 0.857142857142857
      7 | {chips}         | {diapers}      |     2 | 0.285714285714286 | 0.666666666666667 | 0.933333333333333 | 0.857142857142857
      3 | {beer,chips}    | {diapers}      |     2 | 0.285714285714286 | 0.666666666666667 | 0.933333333333333 | 0.857142857142857
(7 rows)

Limit association rules generated from itemsets of size at most 2. This parameter is a good way to reduce long run times.

DROP TABLE IF EXISTS assoc_rules;
SELECT * FROM madlib.assoc_rules( .25,            -- Support
                                  .5,             -- Confidence
                                  'trans_id',     -- Transaction id col
                                  'product',      -- Product col
                                  'test_data',    -- Input data
                                  NULL,           -- Output schema
                                  TRUE,           -- Verbose output
                                  2               -- Max itemset size
                                );

Result (iteration details not shown):

 output_schema | output_table | total_rules |   total_time
---------------+--------------+-------------+-----------------
 public        | assoc_rules  |           4 | 00:00:00.565176
(1 row)

The association rules are again stored in the assoc_rules table:

SELECT * FROM assoc_rules
ORDER BY support DESC, confidence DESC;

Result:

 ruleid |    pre    |   post    | count |      support      |    confidence     |       lift        |    conviction
--------+-----------+-----------+-------+-------------------+-------------------+-------------------+-------------------
      1 | {diapers} | {beer}    |     5 | 0.714285714285714 |                 1 |                 1 |                 0
      2 | {beer}    | {diapers} |     5 | 0.714285714285714 | 0.714285714285714 |                 1 |                 1
      3 | {chips}   | {beer}    |     3 | 0.428571428571429 |                 1 |                 1 |                 0
      4 | {chips}   | {diapers} |     2 | 0.285714285714286 | 0.666666666666667 | 0.933333333333333 | 0.857142857142857
(4 rows)

Post-processing can now be done on the output table in the case that you want to filter the results. For example, if you want any single item on the left hand side and a particular item on the right hand side:

SELECT * FROM assoc_rules WHERE array_upper(pre,1) = 1 AND post = array['beer'];

Result:

 ruleid |    pre    |  post  | count |      support      | confidence | lift | conviction
--------+-----------+--------+-------+-------------------+------------+------+------------
      1 | {diapers} | {beer} |     5 | 0.714285714285714 |          1 |    1 |          0
      3 | {chips}   | {beer} |     3 | 0.428571428571429 |          1 |    1 |          0
(2 rows)

Limit the size of right hand side to 1. This parameter is a good way to reduce long run times.

DROP TABLE IF EXISTS assoc_rules;
SELECT * FROM madlib.assoc_rules( .25,            -- Support
                                  .5,             -- Confidence
                                  'trans_id',     -- Transaction id col
                                  'product',      -- Product col
                                  'test_data',    -- Input data
                                  NULL,           -- Output schema
                                  TRUE,           -- Verbose output
                                  NULL,           -- Max itemset size
                                  NULL,           -- Max LHS size
                                  1               -- Max RHS size
                                );

Result (iteration details not shown):

 output_schema | output_table | total_rules |   total_time
---------------+--------------+-------------+-----------------
 public        | assoc_rules  |           6 | 00:00:00.031362
(1 row)

The association rules are again stored in the assoc_rules table:

SELECT * FROM assoc_rules
ORDER BY support DESC, confidence DESC;

Result:

 ruleid |       pre       |   post    | count |      support      |    confidence     |       lift        |    conviction
--------+-----------------+-----------+-------+-------------------+-------------------+-------------------+-------------------
      4 | {diapers}       | {beer}    |     5 | 0.714285714285714 |                 1 |                 1 |                 0
      3 | {beer}          | {diapers} |     5 | 0.714285714285714 | 0.714285714285714 |                 1 |                 1
      1 | {chips}         | {beer}    |     3 | 0.428571428571429 |                 1 |                 1 |                 0
      6 | {diapers,chips} | {beer}    |     2 | 0.285714285714286 |                 1 |                 1 |                 0
      2 | {chips}         | {diapers} |     2 | 0.285714285714286 | 0.666666666666667 | 0.933333333333333 | 0.857142857142857
      5 | {beer,chips}    | {diapers} |     2 | 0.285714285714286 | 0.666666666666667 | 0.933333333333333 | 0.857142857142857
(6 rows)

Notes

The association rules function always creates a table named assoc_rules. Make a copy of this table before running the function again if you would like to keep multiple association rule tables. This behavior will be improved in a later release.

Literature

[1] https://en.wikipedia.org/wiki/Apriori_algorithm

[2] https://cran.r-project.org/web/packages/arules/arules.pdf

Related Topics

File assoc_rules.sql_in documenting the SQL function.