Sometimes, just the combination is interesting in itself, as in the Barbie doll and candy bar example. But in other circumstances, it makes more sense to find an underlying rule of the form:

if condition, then result.

Notice that this is just shorthand. If the rule says,

if Barbie doll, then candy bar

then we read it as: if a customer purchases a Barbie doll, then the customer is also expected to purchase a candy bar. The general practice is to consider rules where there is just one item on the right-hand side.

Calculating Confidence

Constructs such as the co-occurrence table provide information about which combinations of items occur most commonly in the transactions. For the sake of illustration, lets say that the most common combination has three items, A, B, and C. Table 9.5 provides an example, showing the probabilities that items and various combinations are purchased.

The only rules to consider are those with all three items in the rule and with exactly one item in the result:

If A and B, then C

If A and C, then B

If B and C, then A

Because these three rules contain the same items, they have the same support in the data, 5 percent. What about their confidence level? Confidence is the ratio of the number of transactions with all the items in the rule to the number of transactions with just the items in the condition. The confidence for the three rules is shown in Table 9.6.

Table 9.5 Probabilities of Three Items and Their Combinations

Table 9.6 Confidence in Rules

What is confidence really saying? Saying that the rule if B and C then A has a confidence of 0.33 is equivalent to saying that when B and C appear in a transaction, there is a 33 percent chance that A also appears in it. That is, one time in three A occurs with B and C, and the other two times, B and C appear without A. The most confident rule is the best rule, so the best rule is if B and C then A.

Calculating Lift

As described earlier, lift is a good measure of how much better the rule is doing. It is the ratio of the density of the target (using the left hand side of the rule) to density of the target overall. So the formula is:

lift = (p(condition and result) / p (condition) ) / p(result) = p(condition and result) / (p(condition) p(result))

When lift is greater than 1, then the resulting rule is better at predicting the result than guessing whether the resultant item is present based on item frequencies in the data. When lift is less than 1, the rule is doing worse than informed guessing. The following table (Table 9.7) shows the lift for the three rules and for the rule with the best lift.

None of the rules with three items shows improved lift. The best rule in the data actually only has two items. When A is purchased, then B is 31 percent more likely to be in the transaction than if A is not purchased. In this case, as in many cases, the best rule actually contains fewer items than other rules being considered.

Table 9.7 Lift Measurements for Four Rules

The Negative Rule

When lift is less than 1, negating the result produces a better rule. If the rule

if B and C then A has a confidence of 0.33, then the rule

if B and C then NOT A

has a confidence of 0.67. Since A appears in 45 percent of the transactions, it does NOT occur in 55 percent of them. Applying the same lift measure shows that the lift of this new rule is 1.22 (0.67/0.55), resulting in a lift of 1.33, better than any of the other rules.

Overcoming Practical Limits

Generating association rules is a multistep process. The general algorithm is:

1. Generate the co-occurrence matrix for single items.

2. Generate the co-occurrence matrix for two items. Use this to find rules with two items.

3. Generate the co-occurrence matrix for three items. Use this to find rules with three items.

4. And so on.