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
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.
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.
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).
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.
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.
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.
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.
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.
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.
Sometimes called antecedent support. It measures how often a rule X -> Y is applicable in a database.
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 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.
Introduced by Piatetsky-Shapiro, G., Discovery, analysis, and presentation of strong rules. Knowledge Discovery in Databases, 1991: p. 229-248.
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.
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 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.
cross support ratio, chi-square statistic, cosine/IS measure, gini index, hyper-lift, hyper-confidence, improvement, phi (correlation), odds ratio.