## A Comparison of Commonly Used Interest Measures for Association Rules

> Research on Association Rules
On this page I collected some commonly used measures of
significance and interestingness for association rules and
itemsets. To make the measures comparable all measures are
defined using probabilities. The probability **P(Z)** of
the event that the itemset **Z**
(for simplicity of notation we use **Z** to
denote the itemset but also the event that **Z** is
contained in a transactions)
is contained in a
transaction can be estimated from a database **D**
using maximum likelihood estimation (MLE) by

**P(Z)=freq(Z)/|D|**

where **freq(Z)** is the number of transactions that
contain the itemset **Z** and **|D|** is the size
(number of transactions) of the database.
**Note:** The probability estimate using MLE
will be very poor for itemsets with low observed frequencies.
This effects all measured discussed below.

When we talk about an (association) rule we use the notation
**X -> Y**, where **X** and **Y** are disjoint
itemsets.

A good overview of different association rules measures is provided by: Pang-Ning Tan, Vipin Kumar, and Jaideep Srivastava. Selecting the right objective measure for association analysis. Information Systems, 29(4):293-313, 2004 and Liqiang Geng and Howard J. Hamilton. Interestingness measures for data mining: A survey. ACM Computing Surveys, 38(3):9, 2006.

### Measures for the support-confidence framework for mining association rules:

### Some alternative measures:

- All-confidence
- Collective strength
- Conviction
- Coverage
- Leverage
- Lift (originally called interest)
- Other measures

## Support

Introduced by R. Agrawal, T. Imielinski, and A. Swami. Mining associations between sets of items in large databases. In Proc. of the ACM SIGMOD Int'l Conference on Management of Data, pages 207-216, Washington D.C., May 1993.

**supp(Z) = P(Z)**

Support is defined on itemsets and gives the proportion of
transactions which contain **Z**. It is used as a measure
of significance (importance) of an itemset. Since it
basically uses the count of transactions it is often called a
*frequency constraint.* An itemset with a support > a
set min. support threshold is called a *frequent or large
itemset.*

Supports main feature is that it possesses the *down-ward
closure property (anti-monotonicity)* which means that all
sub sets of a frequent set (support > min. support
threshold) are also frequent. This property (actually, the
fact that no super set of a infrequent set can be frequent)
is used to prune the search space (usually thought of as a
lattice or tree of item sets with increasing size) in
level-wise algorithms (e.g., the Apriori algorithm).

The disadvantage of support is the *rare item problem.*
Items that occur very infrequently in the data set are pruned
although they would still produce interesting and potentially
valuable rules. The rare item problem is important for
transaction data which usually have a very uneven
distribution of support for the individual items (typical
is a power-law distribution where few items
are used all the time and most item are rarely used).

## Confidence (also called strength)

Introduced by R. Agrawal, T. Imielinski, and A. Swami. Mining associations between sets of items in large databases. In Proc. of the ACM SIGMOD Int'l Conference on Management of Data, pages 207-216, Washington D.C., May 1993.

**conf(X -> Y) = supp(X -> Y)/supp(X) = P(X and Y)/P(X) = P(Y | X)**

**X -> Y**and

**Y -> X**.

Confidence is not down-ward closed and was developed together with support by Agrawal et al. (the so-called support-confidence framework). Support is first used to find frequent (significant) itemsets exploiting its down-ward closure property to prune the search space. Then confidence is used in a second step to produce rules from the frequent itemsets that exceed a min. confidence threshold.

A problem with confidence is that it is sensitive to the frequency of the consequent (

**Y**) in the database. Caused by the way confidence is calculated, consequents with higher support will automatically produce higher confidence values even if there exists no association between the items.

## All-confidence

Introduced by Edward R. Omiecinski. Alternative interest measures for mining associations in databases. IEEE Transactions on Knowledge and Data Engineering, 15(1):57-69, Jan/Feb 2003.

**all-confidence(Z) = supp(Z) / max(support(z element of Z)) = P(Z) / max(P(z element of Z))**

**max(support(z element of Z))**is the support of the item with the highest support in

**Z**. All-confidence means that all rules which can be generated from itemset

**Z**have at least a confidence of

**all-confidence(Z)**. All-confidence possesses the downward-closed closure property.

## Collective strength

Introduced by C. C. Aggarwal and P. S. Yu. A new framework for itemset generation. In PODS 98, Symposium on Principles of Database Systems, pages 18-24, Seattle, WA, USA, 1998.

**C(Z) = (1-v(Z))/(1-E[v(Z)]) * E[v(Z)]/v(Z)**

**v(Z)**is the violation rate and

**E[]**is the expected value for independent items. The violation rate is defined as the fraction of transactions which contain some of the items in an itemset but not all. Collective strength gives 0 for perfectly negative correlated items, infinity for perfectly positive correlated items, and 1 if the items co-occur as expected under independence.

Problematic is that for items with medium to low probabilities the observations of the expected values of the violation rate is dominated by the proportion of transactions which do not contain any of the items in

**Z**. For such itemsets collective strength produces values close to one, even if the itemset appears several times more often than expected together.

## Coverage

**coverage(X -> Y) = supp(X) = P(X)**

**X -> Y**is applicable in a database.

## Conviction

Introduced by Sergey Brin, Rajeev Motwani, Jeffrey D. Ullman, and Shalom Tsur. Dynamic itemset counting and implication rules for market basket data. In SIGMOD 1997, Proceedings ACM SIGMOD International Conference on Management of Data, pages 255-264, Tucson, Arizona, USA, May 1997.

**conviction(X -> Y) =(1-supp(Y))/(1-conf(X -> Y)) = P(X)P(not Y)/P(X and not Y)**

**X**appears without

**Y**if they were dependent with the actual frequency of the appearance of

**X**without

**Y**. In that respect it is similar to lift (see section about lift on this page), however, it contrast to lift it is a directed measure since it also uses the information of the absence of the consequent. An interesting fact is that conviction is monotone in confidence and lift.

## Leverage

Introduced by Piatetsky-Shapiro, G., Discovery, analysis, and presentation of strong rules. Knowledge Discovery in Databases, 1991: p. 229-248.

**leverage(X -> Y) = P(X and Y) - (P(X)P(Y))**

Leverage measures the difference of **X** and **Y**
appearing together in the data set and what would be expected
if **X** and **Y** where statistically dependent. The
rational in a sales setting is to find out how many more
units (items **X** and **Y** together) are sold than
expected from the independent sells.

Using min. leverage thresholds at the same time incorporates
an implicit frequency constraint. E.g., for setting a min.
leverage thresholds to 0.01% (corresponds to 10 occurrence in
a data set with 100,000 transactions) one first can use an
algorithm to find all itemsets with min. support of 0.01% and
then filter the found item sets using the leverage
constraint. Because of this property leverage also can suffer
from the rare item problem.

## Lift (originally called interest)

Introduced by S. Brin, R. Motwani, J. D. Ullman, and S. Tsur. Dynamic itemset counting and implication rules for market basket data. In Proc. of the ACM SIGMOD Int'l Conf. on Management of Data (ACM SIGMOD '97), pages 265-276, 1997.

**lift(X -> Y) = lift(Y -> X) = conf(X -> Y)/supp(Y) = conf(Y -> X)/supp(X) = P(X and Y)/(P(X)P(Y))**

Lift measures how many times more often **X** and **Y**
occur together than expected if they where statistically
independent.

Lift is not down-ward closed and does not suffer from the
rare item problem. Also lift is susceptible to noise in small
databases. Rare itemsets with low counts (low probability)
which per chance occur a few times (or only once) together
can produce enormous lift values.

## Other measures

cross support ratio, chi-square statistic, cosine/IS measure, gini index, hyper-lift, hyper-confidence, improvement, phi (correlation), odds ratio.

*© Michael Hahsler, last modified*