/* ----------------------------------------------------------------------- *//**
*
* @file assoc_rules.sql_in
*
* @brief The \ref assoc_rules function computes association rules for a given
* set of data. The data is assumed to have two dimensions; items (between which
* we are trying to discover associations), and a transaction id. This tranaction
* id groups the items by event and could also be a user id, date, etc. depending
* on the context of the data. This function assumes the data is stored in two
* columns with one transaction id and one item per row.
* @date June 2011
* @date August 2012
*
* @sa For a brief introduction to the association rules implementation, see the module
* description \ref grp_assoc_rules.
*
*//* ----------------------------------------------------------------------- */
m4_include(`SQLCommon.m4')
/**
@addtogroup grp_assoc_rules
@brief Computes association rules for a given set of data.
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 identification, 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
...
@anchor rules
@par 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
\f[
S (X) = \frac{Total X}{Total transactions}
\f]
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
\f[
S (X \Rightarrow Y) = \frac{Total(X \cup Y)}{Total transactions}
\f]
- Confidence: The ratio of transactions that contain \f$ X,Y \f$ to
transactions that contain \f$ X \f$. One could view this metric as the
conditional probability of \f$ Y \f$ , given \f$ X \f$ . \f$ P(Y|X) \f$
\f[
C (X \Rightarrow Y) = \frac{s(X \cap Y )}{s(X)}
\f]
- Lift: The ratio of observed support of \f$ X,Y \f$ to the expected support of
\f$ X,Y \f$ , assuming \f$ X \f$ and \f$ Y \f$ are independent.
\f[
L (X \Rightarrow Y) = \frac{s(X \cap Y )}{s(X) \cdot s(Y)}
\f]
- Conviction: The ratio of expected support of \f$ X \f$ occurring without
\f$ Y \f$ assuming \f$ X \f$ and \f$ \neg Y \f$ are independent, to the
observed support of \f$ X \f$ occuring without \f$ Y \f$. If conviction is
greater than 1, then this metric shows that incorrect predictions ( \f$ X
\Rightarrow Y \f$ ) 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.)
\f[
Conv (X \Rightarrow Y) = \frac{1 - S(Y)}{1 - C(X \Rightarrow Y)}
\f]
@anchor algorithm
@par 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 \f$ n \f$ are generated from sets of order \f$ n - 1 \f$.
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:
\e Initial \e step
-# Generate all itemsets of order 1.
-# Eliminate itemsets that have support less than minimum support.
\e Main \e algorithm
-# For \f$ n \ge 2 \f$, generate itemsets of order \f$ n \f$ by combining the
itemsets of order \f$ n - 1 \f$.
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.
\e Association \e rule \e generation
Given a frequent itemset \f$ A \f$ generated from the Apriori algorithm, and all
subsets \f$ B \f$ , we generate rules such that \f$ B \Rightarrow (A - B) \f$
meets minimum confidence requirements.
@anchor syntax
@par Function Syntax
Association rules has the following syntax:
assoc_rules( support,
confidence,
tid_col,
item_col,
input_table,
output_schema,
verbose,
max_itemset_size
);
This generates all association rules that satisfy the specified minimum
support and confidence.
\b 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 \c assoc_rules in the schema
specified by \c 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 or Apache HAWQ, the table is distributed by the \c ruleid column.
The \c pre and \c post columns are the itemsets of left and right hand sides of the
association rule respectively. The \c support, \c confidence, \c lift, and
\c conviction columns are calculated as described earlier.
- verbose
- BOOLEAN, default: FALSE. Determines if details are printed for each iteration
as the algorithm progresses.
- max_itemset_size
- INTEGER, default: generate itemsets of all sizes. 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.
@anchor examples
@examp
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');
INSERT INTO test_data VALUES (1, 'diapers');
INSERT INTO test_data VALUES (1, 'chips');
INSERT INTO test_data VALUES (2, 'beer');
INSERT INTO test_data VALUES (2, 'diapers');
INSERT INTO test_data VALUES (3, 'beer');
INSERT INTO test_data VALUES (3, 'diapers');
INSERT INTO test_data VALUES (4, 'beer');
INSERT INTO test_data VALUES (4, 'chips');
INSERT INTO test_data VALUES (5, 'beer');
INSERT INTO test_data VALUES (6, 'beer');
INSERT INTO test_data VALUES (6, 'diapers');
INSERT INTO test_data VALUES (6, 'chips');
INSERT INTO test_data VALUES (7, 'beer');
INSERT INTO test_data VALUES (7, 'diapers');
-# Let \f$ min(support) = .25 \f$ and \f$ min(confidence) = .5 \f$, and the
output schema is set to \c 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:
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:
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)
@anchor notes
@par Notes
The association rules function always creates a table named \c assoc_rules.
Make a copy of this table before running the function again if you would
like to keep multiple association rule tables.
@anchor literature
@literature
[1] https://en.wikipedia.org/wiki/Apriori_algorithm
@anchor related
@par Related Topics
File assoc_rules.sql_in documenting the SQL function.
*/
/*
* @brief The result data type for the association rule API
*
* output_schema the name of the output schema.
* output_table the name of the output table.
* total_rules the number of total rules.
* total_time the running time.
*/
DROP TYPE IF EXISTS MADLIB_SCHEMA.assoc_rules_results CASCADE;
CREATE TYPE MADLIB_SCHEMA.assoc_rules_results AS
(
output_schema TEXT,
output_table TEXT,
total_rules INT,
total_time INTERVAL
);
/*
* @brief Given the text form of a closed frequent pattern (cfp), this function
* generates the association rules for that pattern. We use text format
* because text values are hash joinable. The output is a set of text
* array. For example, assuming the input pattern is '1,2,3'.
* The result rules:
* array['1', '2,3']
* array['2', '1,3']
* array['3', '1,2']
* array['1,2', '3']
* array['1,3', '2']
* array['2,3', '1']
* Note that two meaningless rules will be excluded:
* array['1,2,3', NULL]
* array[NULL, '1,2,3']
*
* @param arg 1 The text form of a closed frequent pattern.
* @param arg 2 The number of items in the pattern.
*
* @return A set of text array. Each array has two elements, corresponding to
* the left and right parts of an association rule.
*
*/
CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.gen_rules_from_cfp
(
TEXT,
INT
)
RETURNS SETOF TEXT[] AS 'MODULE_PATHNAME'
LANGUAGE C STRICT IMMUTABLE
m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `');
/**
*
* @param support minimum level of support needed for each itemset to
* be included in result
* @param confidence minimum level of confidence needed for each rule to
* be included in result
* @param tid_col name of the column storing the transaction ids
* @param item_col name of the column storing the products
* @param input_table name of the table where the data is stored
* @param output_schema name of the schema where the final results will be stored
* @param verbose determining if output contains comments
*
* @returns The schema and table name containing association rules,
* and total number of rules found.
*
* This function computes the association rules between products in a data set.
* It reads the name of the table, the column names of the product and ids, and
* computes ssociation rules using the Apriori algorithm, and subject to the
* support and confidence constraints as input by the user. This version of
* association rules has verbose functionality. When verbose is true, output of
* function includes iteration steps and comments on Apriori algorithm steps.
*
*/
CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.assoc_rules
(
support FLOAT8,
confidence FLOAT8,
tid_col TEXT,
item_col TEXT,
input_table TEXT,
output_schema TEXT,
verbose BOOLEAN,
max_itemset_size INTEGER
)
RETURNS MADLIB_SCHEMA.assoc_rules_results
AS $$
PythonFunctionBodyOnly(`assoc_rules', `assoc_rules')
plpy.execute("SET client_min_messages = error;")
# schema_madlib comes from PythonFunctionBodyOnly
return assoc_rules.assoc_rules(
schema_madlib,
support,
confidence,
tid_col,
item_col,
input_table,
output_schema,
verbose,
max_itemset_size
);
$$ LANGUAGE plpythonu
m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `');
/**
*
* @brief The short form of the above function with vobose removed.
*
*/
CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.assoc_rules
(
support FLOAT8,
confidence FLOAT8,
tid_col TEXT,
item_col TEXT,
input_table TEXT,
output_schema TEXT
)
RETURNS MADLIB_SCHEMA.assoc_rules_results
AS $$
PythonFunctionBodyOnly(`assoc_rules', `assoc_rules')
plpy.execute("SET client_min_messages = error;")
# schema_madlib comes from PythonFunctionBodyOnly
return assoc_rules.assoc_rules(
schema_madlib,
support,
confidence,
tid_col,
item_col,
input_table,
output_schema,
False,
'NULL'
);
$$ LANGUAGE plpythonu
m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `');
CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.assoc_rules
(
support FLOAT8,
confidence FLOAT8,
tid_col TEXT,
item_col TEXT,
input_table TEXT,
output_schema TEXT,
verbose BOOLEAN
)
RETURNS MADLIB_SCHEMA.assoc_rules_results
AS $$
PythonFunctionBodyOnly(`assoc_rules', `assoc_rules')
plpy.execute("SET client_min_messages = error;")
# schema_madlib comes from PythonFunctionBodyOnly
return assoc_rules.assoc_rules(
schema_madlib,
support,
confidence,
tid_col,
item_col,
input_table,
output_schema,
verbose,
'NULL'
);
$$ LANGUAGE plpythonu
m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `');
--------------------------------------------------------------------------
CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.assoc_rules(message TEXT)
RETURNS text AS $$
PythonFunction(assoc_rules, assoc_rules, assoc_rules_help_message)
$$ language plpythonu
m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `CONTAINS SQL', `');
CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.assoc_rules()
RETURNS text AS $$
SELECT MADLIB_SCHEMA.assoc_rules('');
$$ language SQL
m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `CONTAINS SQL', `');