Association Rules

Properties2

Type	Concept
Note created	Feb 17, 2025

Association rule inference consists on generating rules that batch together items that are typically batched together out of several different item sets.

Metrics

There are different metrics that are used to evaluate the rules generated, as per mlxtend documentation:

Support of an Item Set

The support of an item set is defined as the number of total transactions that include a given item set. When working with association rules, the support of the given rule is computed as the support of the union for both the antecedent and the consequents set, as per:

$$\text{support}(A\to C)=\text{support}(A\cup C)$$Link to original

Confidence of an Association Rule

The confidence of an association rule $A\to C$ is a metric measuring the probability of seeing the consequent in a transaction where the antecedent appears. It lies in the range $[0,1]$ and can be defined using the support as:

$$\text{confidence}(A\to C)=\frac{\text{support}(A\to C)}{\text{support}(A)}$$Link to original

Lift of an Association Rule

The lift metric of an association rule measures how much more often the antecedent and consequent of a rule $A\to C$ occur together than we would expect if they were statistically independent. It is computed based on the confidence and support as per:

$$\text{lift}(A\to C)=\frac{\text{confidence}(A\to C)}{\text{support}(C)}$$

It lies in the $[0,\infty ]$; if $A$ and $C$ are independent, the lift score will be exactly 1. If the lift score is 2, $C$ is twice as likely to appear when $A$ appears.

Link to original

Leverage of an Association Rule

When working with association rules, the leverage metric computes the difference between the observed frequency of an antecedent set and consequent set appearing together and the frequency that would be expected if they were independent. It is derived from the support as:

$$\text{leverage}(A\to C)=\text{support}(A\to C)-\text{support}(A)\times \text{support}(C)$$

It lies in the $[-1,1]$ interval and a leverage value of 0 indicates independence.

Link to original

Conviction of an Association Rule

When working with association rules, a high conviction metric means that the consequent is highly depending on the antecedent. It can be derived from the support and confidence metrics as:

$$\text{conviction}(A\to C)=\frac{1-\text{support}(C)}{1-\text{confidence}(A\to C)}$$

In the case of a perfect confidence score, the denominator becomes 0 and the conviction $\infty$. Similar to lift, if items are independent, the conviction is 1.

Link to original

Zhang's Metric for Association Rules

In association rules, Zhang’s metric is a metric that measures both association and dissociation. It is computed using the leverage and support as:

$$\text{zhangs metric}(A\to C)=\frac{\text{leverage}(A\to C)}{\max \{\begin{array}{l}\text{support}(A\to C)\times (1-\text{support}(A)),\\ \text{support}(A)\times (\text{support}(C)-\text{support}(A\to C))\end{array}}$$

Lies within the $[-1,1]$ interval, and a positive value indicates association while a negative value indicate dissociation.

Link to original

Algorithms

Apriori

The Apriori algorithm is a popular algorithm developed by Agrawal, Rakesh and Ramakrishnan that for extracting frequent item sets to be used in association rule learning. It is a sensible default, although its runtime can be quite large (especially when there are a high number of unique items). In such case, it is possible to use some alternative like FP-Growth or FP-Max.

The algorithm provides a support value, which represents the fraction of transactions in the database that include a given item set. For example, a support of 0.5 represents that 50% of the transactions include the given item set.

Link to original

FP-Growth

FP-Growth is a frequent pattern generation algorithm, which is normally used to find frequent item sets that are later used to association rule learning.

It inserts items into a pattern search tree, which allows it to have a linear increase in runtime with respect of the number of unique items.

Link to original

FP-Max

FP-Max is a variant of the FP-Growth algorithm, used as a basis for association rule learning, that focuses on obtaining maximal item sets: an item set $X$ is said to be maximal if $X$ is frequent and there is no frequent super-pattern containing $X$. In other words, $X$ cannot be a sub-pattern of a larger frequent pattern to be understood as maximal.

Link to original