A Comparison of Commonly Used Interest Measures for Association Rules

>> Home > Research > Association Rules > Measures

Preliminaries

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:


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)

Confidence is defined as the probability of seeing the rule's consequent under the condition that the transactions also contain the antecedent. Confidence is directed and gives different values for the rules 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)

where 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)

Sometimes called antecedent support. It measures how often a rule 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)

Conviction was developed as an alternative to confidence which was found to not capture direction of associations adequately. Conviction compares the probability that 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