. 61
( 137 .)


story. Instead, imagine a family going shopping. The purpose: finding a gift for
little Susie™s friend Emily, since her birthday is coming up. A Barbie doll is the
perfect gift. At checkout, little Jacob starts crying. He wants something too”a
candy bar fits the bill. Or perhaps Emily has a brother; he can™t be left out of the
gift-giving festivities. Maybe the candy bar is for Mom, since buying Barbie dolls
is a tiring activity and Mom needs some energy. These scenarios all suggest that
the candy bar is an impulse purchase added onto that of the Barbie doll.
Whether Wal-Mart can make use of this information is not clear. This rule
might suggest more prominent product placement, such as ensuring that cus­
tomers must walk through candy aisles on their way back from Barbie-land. It
might suggest product tie-ins and promotions offering candy bars and dolls
together. It might suggest particular ways to advertise the products. Because the
rule is easily understood, it suggests plausible causes and possible interventions.
Market Basket Analysis and Association Rules 297

Trivial Rules
Trivial results are already known by anyone at all familiar with the business. The sec­
ond example (“Customers who purchase maintenance agreements are very
likely to purchase large appliances”) is an example of a trivial rule. In fact, cus­
tomers typically purchase maintenance agreements and large appliances at the
same time. Why else would they purchase maintenance agreements? The two
are advertised together, and rarely sold separately (although when sold sepa­
rately, it is the large appliance that is sold without the agreement rather than
the agreement sold without the appliance). This rule, though, was found after
analyzing hundreds of thousands of point-of-sale transactions from Sears.
Although it is valid and well supported in the data, it is still useless. Similar
results abound: People who buy 2-by-4s also purchase nails; customers who
purchase paint buy paint brushes; oil and oil filters are purchased together, as
are hamburgers and hamburger buns, and charcoal and lighter fluid.
A subtler problem falls into the same category. A seemingly interesting
result”such as the fact that people who buy the three-way calling option on
their local telephone service almost always buy call waiting”may be the result
of past marketing programs and product bundles. In the case of telephone ser­
vice options, three-way calling is typically bundled with call waiting, so it is
difficult to order it separately. In this case, the analysis does not produce action­
able results; it is producing already acted-upon results. Although it is a danger
for any data mining technique, market basket analysis is particularly suscepti­
ble to reproducing the success of previous marketing campaigns because of its
dependence on unsummarized point-of-sale data”exactly the same data that
defines the success of the campaign. Results from market basket analysis may sim­
ply be measuring the success of previous marketing campaigns.
Trivial rules do have one use, although it is not directly a data mining use.
When a rule should appear 100 percent of the time, the few cases where it does
not hold provide a lot of information about data quality. That is, the exceptions
to trivial rules point to areas where business operations, data collection, and
processing may need to be further refined.

Inexplicable Rules
Inexplicable results seem to have no explanation and do not suggest a course of action.
The third pattern (“When a new hardware store opens, one of the most com­
monly sold items is toilet bowl cleaner”) is intriguing, tempting us with a new
fact but providing information that does not give insight into consumer behav­
ior or the merchandise or suggest further actions. In this case, a large hardware
company discovered the pattern for new store openings, but could not figure
out how to profit from it. Many items are on sale during the store openings,
but the toilet bowl cleaners stood out. More investigation might give some
298 Chapter 9

explanation: Is the discount on toilet bowl cleaners much larger than for other
products? Are they consistently placed in a high-traffic area for store openings
but hidden at other times? Is the result an anomaly from a handful of stores?
Are they difficult to find at other times? Whatever the cause, it is doubtful that
further analysis of just the market basket data can give a credible explanation.

WA R N I N G When applying market basket analysis, many of the results are
often either trivial or inexplicable. Trivial rules reproduce common knowledge
about the business, wasting the effort used to apply sophisticated analysis
techniques. Inexplicable rules are flukes in the data and are not actionable.


Perhaps the most talked about association rule ever “found” is the association
between beer and diapers. This is a famous story from the late 1980s or early
1990s, when computers were just getting powerful enough to analyze large
volumes of data. The setting is somewhere in the midwest, where a retailer is
analyzing point of sale data to find interesting patterns.
Lo and behold, lurking in all the transaction data, is the fact that beer and
diapers are selling together. This immediately sets marketing minds in motion
to figure out what is happening. A flash of insight provides the explanation:
beer drinkers do not want to interrupt their enjoyment of televised sports, so
they buy diapers to reduce trips to the bathroom. No, that™s not it. The more
likely story is that families with young children are preparing for the weekend,
diapers for the kids and beer for Dad. Dad probably knows that after he has a
couple of beers, Mom will change the diapers.
This is a powerful story. Setting aside the analytics, what can a retailer do
with this information? There are two competing views. One says to put the beer
and diapers close together, so when one is purchased, customers remember
to buy the other one. The other says to put them as far apart as possible, so
the customer must walk by as many stocked shelves as possible, having the
opportunity to buy yet more items. The store could also put higher-margin
diapers a bit closer to the beer, although mixing baby products and alcohol
would probably be unseemly.
The story is so powerful that the authors noticed at least four companies
using the story”IBM, Tandem (now part of HP), Oracle, and NCR Teradata. The
actual story was debunked on April 6, 1998 in an article in Forbes magazine
called “Beer-Diaper Syndrome.”
The debunked story still has a lesson. Apparently, the sales of beer and
diapers were known to be correlated (at least in some stores) based on
inventory. While doing a demonstration project, a sales manager suggested that
the demo show something interesting, like “beer and diapers” being sold
together. With this small hint, analysts were able to find evidence in the data.
Actually, the moral of the story is not about the power of association rules. It is
that hypothesis testing can be very persuasive and actionable.
Market Basket Analysis and Association Rules 299

How Good Is an Association Rule?

Association rules start with transactions containing one or more products or ser­
vice offerings and some rudimentary information about the transaction. For the
purpose of analysis, the products and service offerings are called items. Table 9.1
illustrates five transactions in a grocery store that carries five products.
These transactions have been simplified to include only the items pur­
chased. How to use information like the date and time and whether the cus­
tomer paid with cash or a credit card is discussed later in this chapter.
Each of these transactions gives us information about which products are
purchased with which other products. This is shown in a co-occurrence table
that tells the number of times that any pair of products was purchased
together (see Table 9.2). For instance, the box where the “Soda” row intersects
the “OJ” column has a value of “2,” meaning that two transactions contain
both soda and orange juice. This is easily verified against the original transac­
tion data, where customers 1 and 4 purchased both these items. The values
along the diagonal (for instance, the value in the “OJ” column and the “OJ”
row) represent the number of transactions containing that item.

Table 9.1 Grocery Point-of-Sale Transactions


1 Orange juice, soda

2 Milk, orange juice, window cleaner

3 Orange juice, detergent

4 Orange juice, detergent, soda

5 Window cleaner, soda

Table 9.2 Co-Occurrence of Products


OJ 4 1 1 1 2

Window Cleaner 1 2 1 1 0

Milk 1 1 1 0 0

Soda 2 1 0 3 3

Detergent 1 0 0 1 2
300 Chapter 9

This simple co-occurrence table already highlights some simple patterns:
Orange juice and soda are more likely to be purchased together than

any other two items.
Detergent is never purchased with window cleaner or milk.

Milk is never purchased with soda or detergent.

These observations are examples of associations and may suggest a formal
rule like: “If a customer purchases soda, then the customer also purchases orange
juice.” For now, let™s defer discussion of how to find the rule automatically, and
instead ask another question. How good is this rule?
In the data, two of the five transactions include both soda and orange juice.
These two transactions support the rule. The support for the rule is two out of
five or 40 percent. Since both the transactions that contain soda also contain
orange juice, there is a high degree of confidence in the rule as well. In fact, two
of the three transactions that contains soda also contains orange juice, so the
rule “if soda, then orange juice” has a confidence of 67 percent percent. The
inverse rule, “if orange juice, then soda,” has a lower confidence. Of the four
transactions with orange juice, only two also have soda. Its confidence, then, is
just 50 percent. More formally, confidence is the ratio of the number of the
transactions supporting the rule to the number of transactions where the con­
ditional part of the rule holds. Another way of saying this is that confidence is
the ratio of the number of transactions with all the items to the number of
transactions with just the “if” items.
Another question is how much better than chance the rule is. One way to
answer this is to calculate the lift (also called improvement), which tells us how
much better a rule is at predicting the result than just assuming the result in
the first place. Lift is the ratio of the density of the target after application of the
left-hand side to the density of the target in the population. Another way of
saying this is that lift is the ratio of the records that support the entire rule to
the number that would be expected, assuming that there is no relationship
between the products (the exact formula is given later in the chapter). A
similar measure, the excess, is the difference between the number of records
supported by the entire rule minus the expected value. Because the excess
is measured in the same units as the original sales, it is sometimes easier to
work with.
Figure 9.7 provides an example of lift, confidence, and support as provided
by Blue Martini, a company that specializes in tools for retailers. Their soft­
ware system includes a suite of analysis tools that includes association rules.
Market Basket Analysis and Association Rules 301

This particular example shows that a particular jacket is much more likely to
be purchased with a gift certificate, information that can be used for improv­
ing messaging for selling both gift certificates and jackets.
The ideas behind the co-occurrence table extend to combinations with any
number of items, not just pairs of items. For combinations of three items, imag­
ine a cube with each side split into five different parts, as shown in Figure 9.8.
Even with just five items in the data, there are already 125 different subcubes
to fill in. By playing with symmetries in the cube, this can be reduced a bit (by
a factor of six), but the number of subcubes for groups of three items is
proportional to the third power of the number of different items. In general,
the number of combinations with n items is proportional to the number of
items raised to the nth power”a number that gets very large, very fast.
And generating the co-occurrence table requires doing work for each of these

Figure 9.7 Blue Martini provides an interface that shows the support, confidence, and lift
of an association rule.
302 Chapter 9

1 0 0 1 1

2 0 0 2 1

1 1 1 0 0

1 1 1 0 0
4 1 1 2 1
OJ Cleaner

OJ Cleaner Milk Soda Detergent

Orange juice, milk, and
window cleaner appear
together in exactly one


. 61
( 137 .)