# Michael Hahsler

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

> Research on Association Rules

This page contains a collection of commonly used measures of significance and interestingness for association rules and itemsets. All measures discussed on this page are implemented in the freely available R-extension package arules. Please contact me for corrections or if a measure is missing (on this page or implemented in arules).

## Introduction and Definitions

Agrawal, Imielinski, and Swami introduced the problem of association rule mining in the following way: Let $I=\{i_1, i_2,\ldots,i_m\}$ be a set of $m$ binary attributes called items. Let $D = \{t_1, t_2, \ldots, t_n\}$ be a set of transactions called the database. Each transaction $t \in D$ has an unique transaction ID and contains a subset of the items in $I$, i. e., $t \subseteq I$. A rule is defined as an implication of the form $X \Rightarrow Y$ where $X, Y \subseteq I$ and $X \cap Y = \emptyset$. The sets of items (for short itemsets) $X$ and $Y$ are called antecedent (left-hand-side or LHS) and consequent (right-hand-side or RHS) of the rule, respectively.

To make the measures comparable, all measures are also defined not only in terms of itemset support (see support below), but also in terms of probabilities and sometimes in terms of counts. The probability $P(E_X)$ of the event that all items in itemset $X$ are contained in an arbitrarily chosen transaction can be estimated from a database $D$ using maximum likelihood estimation (MLE) by $$\hat{P}(E_X) = \frac{|\{t \in D; X \subseteq t\}|}{n}$$ where $c_X = |\{t \in D; X \subseteq t\}|$ is the count of the number of transactions that contain the itemset $X$ and $n=|D|$ is the size (number of transactions) of the database. For conciseness of notation we will drop the hat and the $E$ from the notation and use in the following just $P(X)$ to mean $\hat{P}(E_X)$. Note: The used probability estimates will be very poor for itemsets with low observed frequencies. This needs to be always taken into account since it effects most measured discussed below.

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.

## 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(X) = \frac{|\{t \in D; X \subseteq t\}|}{|D|} = P(X)$$ Support is defined on itemsets and gives the proportion of transactions which contain $X$. 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 greater then a set minimum support threshold, $supp(X) > \sigma$, is called a frequent or large itemset.

For rules the support defined as the support of all items in the rule, i.e., $supp(X \Rightarrow Y) = supp(X \cup Y) = P(X \wedge Y)$.

Supports main feature is that it possesses the down-ward closure property (anti-monotonicity) which means that all sub sets of a frequent set 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).

Range: $[0, 1]$

## Confidence, 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 \Rightarrow Y) = \frac{supp(X \Rightarrow Y)}{supp(X)} = \frac{supp(X \cup Y)}{supp(X)} = \frac{P(X \wedge 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 \Rightarrow Y$ and $Y \Rightarrow X$. Association rules have to satisfy a minimum confidence constraint, $conf(X \Rightarrow Y) \ge \gamma$.

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.

Range: $[0, 1]$

## Added Value (AV), Pavillon Index, Centered Confidence

Defined as $$AV(X \Rightarrow Y)) = conf(X \Rightarrow Y) - supp(Y)$$

Range: $[-.5, 1]$

## 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 is defined on itemsets (not rules) as $$\textit{all-confidence}(X) = \frac{supp(X)}{max_{x \in X}(supp(x))} = \frac{P(X)}{max_{x \in X}(P(x))}$$ where $max_{x \in X}(supp(x \in X))$ is the support of the item with the highest support in $X$. All-confidence means that all rules which can be generated from itemset $X$ have at least a confidence of $\textit{all-confidence}(X)$. All-confidence possesses the downward-closed closure property and thus can be effectively used inside mining algorithms.

Range: $[0, 1]$

## Casual Confidence

Kodratoff (1999)

Confidence reinforced by negatives given by $$\textit{casual-conf} = \frac{1}{2} [P(Y|X) + P(\overline{Y}|\overline{X})]$$

Range: $[0, 1]$

## Casual Support

Kodratoff (1999)

Support improved by negatives given by $$\textit{casual-supp} = P(X \wedge Y) + P(\overline{X} \wedge \overline{Y})$$

Range: $[0, 2]$

## Certainty Factor (CF), Loevinger

Berzal et al. (2002)

The certainty factor is a measure of variation of the probability that $Y$ is in a transaction when only considering transactions with $X$. An increasing CF means a decrease of the probability that $Y$ is not in a transaction that $X$ is in. Negative CFs have a similar interpretation. $$CF(X \Rightarrow Y) = \frac{conf(X \Rightarrow Y)-supp(Y)}{supp(\overline{Y})} = \frac{P(Y|X)-P(Y)}{1-P(Y)}$$

Range: $[-1, 1]$ (0 indicates independence)

## Chi-Squared

The chi-squared statistic to test for independence between the lhs and rhs of the rule. The critical value of the chi-squared distribution with 1 degree of freedom (2x2 contingency table) at $\alpha=0.05$ is $3.84$; higher chi-squared values indicate that the lhs and the rhs are not independent. Note that the contingency table is likely to have cells with low expected values and that thus Fisher's Exact Test might be more appropriate.

Range: $[0, \infty]$

## Cross-Support Ratio

Introduced by Xiong et al., 2003. Defined on itemsets as the ratio of the support of the least frequent item to the support of the most frequent item, i.e., $$\textit{cross-support}(X) = \frac{min_{x \in X}(supp(x))}{max_{x \in X}(supp(x))}$$ a ratio smaller than a set threshold. Normally many found patterns are cross-support patterns which contain frequent as well as rare items. Such patterns often tend to be spurious.

Range: $[0, 1]$

## Collective Strength (S)

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. $$S(X) = \frac{1-v(X)}{1-E[v(X)]} \frac{E[v(X)]}{v(X)} = \frac{P(X \wedge Y)+P(\overline{Y}|\overline{X})} {P(X)P(Y)+P(\overline{X})P(\overline{Y})}$$ where $v(X)$ 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 $X$. For such itemsets collective strength produces values close to one, even if the itemset appears several times more often than expected together.

Range: $[0, \infty]$

## Conviction

Introduced by Sergey Brin, Rajeev Motwani, Jeffrey D. Ullman, and Shalom Turk. 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 \Rightarrow Y) =\frac{1-supp(Y)}{1-conf(X \Rightarrow Y)} = \frac{P(X)P(\overline{Y})}{P(X \wedge \overline{Y})}$$ where $E_{\neg Y}$ is the event that $Y$ does not appear in a transaction. 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.

Range: $[0, 1]$

## Cosine

Defined as $$cosine(X \Rightarrow Y) = \frac{supp(X \cup Y)}{\sqrt{(supp(X)supp(Y))}} = \frac{P(X \wedge Y)}{\sqrt{P(X)P(Y)}}$$

Range: $[0, 1]$

## Coverage

Coverage is sometimes called antecedent support or LHS support. It measures how often a rule $X \Rightarrow Y$ is applicable in a database. $$cover(X \Rightarrow Y) = supp(X) = P(X)$$

Range: $[0, 1]$

## Descriptive Confirmed Confidence

Kodratoff (1999)

Confidence confirmed by its negative defined as $$\textit{descriptive-conf} = conf(X \Rightarrow Y) - conf(X \Rightarrow \overline{Y}) = P(Y|X) - P(\overline{Y}|X)$$

Range: $[-1, 1]$

## Difference of Confidence

Hofmann and Wilhelm (2001)

Defined as $$doc(X \Rightarrow Y) = conf(X \Rightarrow Y) - conf(\overline{X} \Rightarrow Y) = P(Y|X) - P(Y|\overline{X})$$

Range: $[-1, 1]$

## Example and Counterexample Rate

Defined as $$ecr(X \Rightarrow Y) = \frac{P(X \wedge Y) - P(X \wedge \overline{Y})}{P(X \wedge Y)}$$

Range: $[0, 1]$

## Fisher's Exact Test

Statistical significance test used in the analysis of contingency tables where sample sizes are small. Returns the p-value.

Range: $[0, 1]$ (p-value scale)

## Gini Index

Measures quadratic entropy as $$gini(X \Rightarrow Y) = P(X) [P(Y|X)^2+P(\overline{Y}|X)^2] + P(\overline{X}) [P(B|\overline{X})^2+P(\overline{Y}|\overline{X})^2] - P(Y)^2 - P(\overline{Y})^2$$

Range: $[0, 1]$ (0 for independence)

## Hyper-Confidence

Confidence level for observation of too high/low counts for rules $X \Rightarrow Y$ using the hypergeometric model. Since the counts are drawn from a hypergeometric distribution (represented by the random variable $C_{XY}$ with known parameters given by the counts $c_X$ and $c_Y$, we can calculate a confidence interval for the observed counts $c_{XY}$ stemming from the distribution. Hyper-confidence reports the confidence level as $$\textit{hyper-conf}(X \Rightarrow Y) = 1 - P[C_{XY} >= c_{XY} | c_X, c_Y]$$ A confidence level of, e.g., $> 0.95$ indicates that there is only a 5% chance that the count for the rule was generated randomly. Range: $[0, 1]$

## Hyper-Lift

Adaptation of the lift measure which is more robust for low counts using a hypergeometric count model. Hyper-lift is defined as: $$\textit{hyper-lift}(X \Rightarrow Y) = \frac{c_{XY}}{Q_{\delta}[C_{XY}]}$$ where $c_{XY}$ is the number of transactions containing $X$ and $Y$ and $Q_{\delta}[C_{XY}]$ is the quantile of the hypergeometric distribution with parameters $c_X$ and $c_Y$ given by $\delta$ (typically the 99 or 95% quantile).

Range: $[0, \infty]$ (1 indicates independence)

## Imbalance Ratio (IR)

Wu, Chen and Han, (2010)

IR gauges the degree of imbalance between two events that the lhs and the rhs are contained in a transaction. The ratio is close to 0 if the conditional probabilities are similar (i.e., very balanced) and close to 1 if they are very different. It is defined as $$IB(X \Rightarrow Y) = \frac{|P(X|Y) - P(Y|X)|}{P(X|Y) + P(Y|X) - P(X|Y)P(Y|X))}$$

Range: $[0, 1]$ (0 indicates a balanced rule)

## Improvement

The improvement of a rule is the minimum difference between its confidence and the confidence of any proper sub-rule with the same consequent. The idea is that we only want to extend the LHS of the rule if this improves the rule sufficiently. $$improvement(X \Rightarrow Y) = min_{X' \subset X}(conf(X \Rightarrow Y) - conf(X' \Rightarrow Y))$$

Range: $[0, 1]$

## Jaccard coefficient

Tan and Kumar (2000)

Defined as $$jaccard(X \Rightarrow Y) = \frac{supp(X \cup Y)}{supp(X) + supp(Y) - supp(X \cup Y)}= \frac{P(X \wedge Y)}{P(X)+P(Y)-P(X \wedge Y)}$$

Range: $[-1, 1]$ (0 for independence)

## J-Measure (J)

Smyth and Goodman (1991)

Measures cross entropy as $$J(X \Rightarrow Y) = P(X \wedge Y) log(\frac{P(Y|X)}{P(Y)}) + P(X \wedge \overline{Y})log(\frac{P(\overline{Y}|X)}{P(\overline{Y})})$$

Range: $[0, 1]$ (0 for independence)

## Kappa ($\kappa$)

Tan and Kumar (2000)

Defined as $$\kappa(X \Rightarrow Y) = \frac{P(X \wedge Y) + P(\overline{X} \wedge \overline{Y}) - P(X)P(Y) - P(\overline{X})P(\overline{Y})}{1- P(X)P(Y) - P(\overline{X})P(\overline{Y})}$$

Range: $[-1,1]$ (0 means independence)

## Klosgen

Tan and Kumar (2000)

Defined as $$klosgen(X \Rightarrow Y) = \sqrt{supp(X \cup Y)}\,(conf(X \Rightarrow Y) - supp(Y)) = \sqrt{P(X \wedge Y)}\, (P(Y|X) - P(Y))$$

Range: $[-1, 1]$ (0 for independence)

## Kulczynski

Wu, Chen and Han (2007) based on Kulczynski (1927)

Calculate the null-invariant Kulczynski measure with a preference for skewed patterns. $$kulc(X \Rightarrow Y) = \frac{supp(X \cup Y)}{2} \left( \frac{1}{supp(X)} + \frac{1}{supp(Y)} \right) = \frac{P(X \wedge Y)}{2} \left( \frac{1}{P(X)} + \frac{1}{P(Y)} \right)$$

Range: $[0, 1]$

## Goodman-Kruskal ($\lambda$), Predictive Association

Tan and Kumar (2000) $$\lambda(X \Rightarrow Y) = \frac{\Sigma_{x \in X} max_{y \in Y} P(x \wedge y) - max_{y \in Y} P(y)} {n - max_{y \in Y} P(y)}$$

Range: $[0, 1]$

## Laplace Corrected Confidence (L)

Tan and Kumar (2000)

Corrected confidence estimate decreases with lower support to account for estimation uncertainty with low counts. $$L(X \Rightarrow Y) = \frac{c_{XY}+1}{c_X+2}$$

Range: $[0, 1]$

Aze and Kodratoff (2004)

$$\textit{least-contradiction}(X \Rightarrow Y) = \frac{supp(X \cup Y) - supp(X \cup \overline{Y})}{supp(Y)}= \frac{P(X \wedge Y) - P(X \wedge \overline{Y})}{P(Y)}$$ Range: $[-1, 1]$

## Lerman Similarity

Lerman (1981)

Defined as $$lerman(X \Rightarrow Y) = \sqrt{n} \frac{supp(X \cup Y) - supp(X)supp(Y)}{\sqrt{supp(X)supp(Y)}} = \frac{c_{XY} - \frac{c_X c_Y}{n}}{\sqrt{\frac{c_X c_Y}{n}}}$$ Range: $[0, 1]$

## Leverage, Piatetsky-Shapiro Measure (PS)

Introduced by Piatetsky-Shapiro, G., Discovery, analysis, and presentation of strong rules. Knowledge Discovery in Databases, 1991: p. 229-248. $$PS(X \Rightarrow Y) = leverage(X \Rightarrow Y) = supp(X \Rightarrow Y) - supp(X)supp(Y) = P(X \wedge 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.

Range: $[-1, 1]$ (0 indicates independence)

## Lift, 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 was originally called interest. It is defined as $$lift(X \Rightarrow Y) = lift(Y \Rightarrow X) = \frac{conf(X \Rightarrow Y)}{supp(Y)} = \frac{conf(Y \Rightarrow X)}{supp(X)} = \frac{P(X \wedge Y)}{P(X)P(Y)}$$ Lift measures how many times more often $X$ and $Y$ occur together than expected if they where statistically independent. A lift value of 1 indicates independence between $X$ and $Y$.

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.

Range: $[0, \infty]$ (1 means independence)

## Mutual Information (M), Uncertainty

Tan et al. (2002)

Measures the information gain for Y provided by X. $$M(X \Rightarrow Y) = \frac{\sum_{i \in \{X, \overline{X}\}} \sum_{j \in \{Y, \overline{Y}\}} \frac{c_{ij}}{n} log \frac{c_{ij}}{c_i c_j}}{min(-\sum_{i \in \{X, \overline{X}\}} \frac{c_i}{n} log \frac{c_i}{n}, -\sum_{j \in \{Y, \overline{Y}\}} \frac{c_j}{n} log \frac{c_j}{n})} = \frac{\sum_{i \in \{X, \overline{X}\}} \sum_{j \in \{Y, \overline{Y}\}} P(i \wedge j) log \frac{P(i \wedge j)}{P(i) P(j)}}{min(-\sum_{i \in \{X, \overline{X}\}} P(i) log P(i), -\sum_{j \in \{Y, \overline{Y}\}} P(j) log P(j))}$$ Range: $[0, 1]$ (0 for independence)

## Odds Ratio ($\alpha$)

The odds of finding X in transactions which contain Y divided by the odds of finding X in transactions which do not contain Y. $$\alpha(X \Rightarrow Y) = \frac{c_{XY} c_{\overline{X}\overline{Y}}} {c_{X\overline{Y}} c_{\overline{X}Y}} = \frac{P(X \wedge Y) P(\overline{X} \wedge \overline{Y})} {P(X \wedge \overline{Y}) P(\overline{X} \wedge Y)}$$ Range: $[0, \infty]$ (1 indicates that Y is not associated to X)

## Correlation Coefficient $\phi$

Equivalent to Pearson's Product Moment Correlation Coefficient $\rho$ since it is calculated on a $2 \times 2$ contingency table. $$\phi(X \Rightarrow Y) = \frac{n c_{XY} - c_X - c_Y}{\sqrt{c_X c_Y c_\overline{X} c_\overline{Y}}}$$ Range: $[-1, 1]$ (0 when X and Y are independent)}

## Ralambrodrainy Measure

Ralambrodrainy (1991) $$ralambrodrainy(X \Rightarrow Y) = \frac{c_{X\overline{Y}}}{n} = P(X \wedge \overline{Y})$$ Range: $[0, 1]$ (smaller is better)

Kenett and Salini (2008)

RLD evaluates the deviation of the support of the whole rule from the support expected under independence given the supports of X and Y.

Range: $[0, 1]$

## Sebag-Schoenauer measure

Sebag and Schoenauer (1988)

Defined as $$sebag(X \Rightarrow Y) = \frac{supp(X \cup Y)}{supp(X \cup \overline{Y})} = \frac{P(X \wedge Y)}{P(X \wedge \overline{Y})}$$ Range: $[0, 1]$

## Varying Rates Liaison

Bernard and Charron (1996)

Defined as $$VRL(X \Rightarrow Y) = \frac{supp(X \cup Y)}{supp(X)supp(Y)}-1 = \frac{P(X \wedge Y)}{P(X)P(Y)}-1 = lift(X \Rightarrow Y) -1$$ Range: $[-1, \infty]$ (0 for independence)

## Yule's Q and Yule's Y

Tan and Kumar (2000)

Defined as $$Q(X \Rightarrow Y) = \frac{\alpha-1}{\alpha+1}$$ $$Y(X \Rightarrow Y) = \frac{\sqrt{\alpha}-1}{\sqrt{\alpha}+1}$$ where $\alpha$ is the odds ratio.

Range: $[-1, 1]$