Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 47 ยท Projects, Practice and Review

Project: Co-purchase Recommendations

Build a 'customers also bought' recommender with chained MapReduce jobs: pair counting, a top-N per item and a lift score to avoid popularity bias.

"Customers who bought this also bought..." is one of the most profitable features in online shopping, and the simplest version needs no machine learning at all: count how often two products appear in the same basket, then show each product's most frequent partners. At the scale of millions of baskets this is a perfect MapReduce workload, and a good example of chained jobs, where the output of one job feeds the next.

You will build the pipeline in three stages: count pairs, turn pair counts into a top-N list per item, and improve the ranking so that popular items do not dominate every list.

The jobs here run in a Python simulator, with a few dozen baskets in memory instead of billions of rows in HDFS. The mappers and reducers are the real logic. On a cluster each stage would be a separate MapReduce job (or one Spark program) with its input and output in HDFS.

The pipeline

Three chained jobs

Job 1 Basket to item pairs, count each pair.
Job 2 Regroup pairs by item, keep the best N.
Job 3 Re-rank with a lift score.

Each job writes to HDFS; the next one reads it.

1 / 2

Step 1: Counting pairs

A basket is a set of items. The mapper takes one basket and emits every unordered pair of distinct items with a count of 1. To make (milk, bread) and (bread, milk) the same key, sort the two items before emitting. The reducer sums, exactly as in word count, and a combiner does the same on the map side.

The cost to watch is the pair explosion: a basket of n items produces n(n-1)/2 pairs, so a basket of 100 items produces 4,950. Real pipelines cap basket size (ignore the rare huge ones), because they would flood the shuffle with pairs of low value.

Python Job 1: count co-purchased pairs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Step 2: Top-N partners per item

The pair counts are keyed by pair, but recommendations are looked up by item. Job 2 changes the key. Its mapper reads each ((a, b), count) record and emits it twice: (a, (b, count)) and (b, (a, count)), so both items learn about the relationship. After the shuffle, the reducer for item a receives all of its partners and keeps the best N.

Keeping the top N per key is a pattern with a memory-friendly solution: the reducer needs only the N best so far, not the whole list (heapq.nlargest in Python, a bounded priority queue in Java). It is the same shape as the per-group top-N in MapReduce Design Patterns.

Python Job 2: top 2 partners for each item

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You now have a usable recommender: serve top[item] from a key-value store such as HBase, Redis or a plain table (see HBase: Wide-Column Storage). But look at the output: bread is a partner of almost everything. That is not insight, it is just that bread is popular.

Step 3: Fixing popularity bias with lift

Raw counts favor popular products. A better question is: do these two items occur together more often than chance would predict? Lift answers it:

lift(a, b) = P(a and b) / (P(a) x P(b))

where P(a) is the share of baskets containing a, and P(a and b) the share containing both. A lift of 1 means "no relationship", above 1 means they are bought together more than expected, and below 1 means less. To compute it you need the item counts and the total basket count too, which is a small side output. In MapReduce it is distributed to the reducers as a small lookup table (a map-side join using the distributed cache), because it fits in memory even when the pair table does not.

Counting items needs one more simple job: the mapper emits (item, 1) for each distinct item in a basket, plus a counter for the number of baskets. Run both counts in the first stage to avoid reading the input twice.

Python Job 3: re-rank with lift

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compare the two chips lists: both put beer first, but lift gives bread only 0.67, below 1, because bread is in 6 of the 8 baskets and would be expected next to chips by chance alone. Lift also has a weakness: rare pairs can get a huge lift from a single basket. Production systems add a minimum support (ignore pairs seen fewer than, say, 5 times) and sometimes use smoothed variants or cosine similarity.

Operating the pipeline

  • Skew: the key for job 2 is an item, and bestsellers have far more partners than average. A combiner that keeps only the local top-N shrinks that traffic (it is safe: the global top N is contained in the union of local top Ns).
  • Freshness: recompute nightly from the last 30 to 90 days of baskets, or maintain counts incrementally.
  • Cold start: new items have no pairs; fall back to category-level or popularity lists.
  • Evaluation: hold out the last week of baskets and measure how often the recommended items were actually bought.
  • Next step: Spark's ALS or similar algorithms learn from user-item matrices, but the counting approach is explainable and a strong baseline.

Extensions to try

  1. Add a minimum support filter to job 3.
  2. Recommend for a basket by merging the top lists of its items and removing items already in it.
  3. Weight recent baskets higher by emitting a decayed weight instead of 1.
  4. Count triples (a, b, c) and observe how fast the counts explode.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many item pairs does a basket of 10 distinct items produce?

    10 x 9 / 2 = 45 unordered pairs. This quadratic growth is why huge baskets are capped.
  2. 2. Why does job 2 emit each pair record twice?

    Recommendations are looked up by item, so (a, b) must appear under key a and under key b.
  3. 3. What problem does lift fix compared with raw co-purchase counts?

    Lift compares the observed pair frequency with what independence would predict, so popularity alone no longer wins.
  4. 4. Is a combiner that keeps only the local top-N partners correct for a global top-N?

    Selecting the best N is safe to do in stages: the union of local top-N sets always contains the global top N.

Summary

  • Recommendations by co-purchase are counting problems: pairs per basket, then the best partners per item.
  • Sort the two items in each pair so both orders share one key; cap huge baskets to avoid pair explosion.
  • Chained jobs change the key between stages: pair first, then item.
  • Raw counts favor popular items; lift (and a minimum support) gives more useful rankings.
  • Small tables such as item counts are shared with reducers as lookup data instead of being joined through the shuffle.

Next: Project: Clickstream Sessionization.